001    /*
002     *  This file is part of the Jikes RVM project (http://jikesrvm.org).
003     *
004     *  This file is licensed to You under the Eclipse Public License (EPL);
005     *  You may not use this file except in compliance with the License. You
006     *  may obtain a copy of the License at
007     *
008     *      http://www.opensource.org/licenses/eclipse-1.0.php
009     *
010     *  See the COPYRIGHT.txt file distributed with this work for information
011     *  regarding copyright ownership.
012     */
013    package org.jikesrvm.compilers.opt.ssa;
014    
015    import java.util.Enumeration;
016    import org.jikesrvm.compilers.opt.ir.Binary;
017    import org.jikesrvm.compilers.opt.ir.IR;
018    import org.jikesrvm.compilers.opt.ir.Instruction;
019    import org.jikesrvm.compilers.opt.ir.operand.Operand;
020    
021    import static org.jikesrvm.compilers.opt.ir.Operators.INT_ADD;
022    import static org.jikesrvm.compilers.opt.ir.Operators.INT_SUB;
023    import static org.jikesrvm.compilers.opt.ir.Operators.LONG_ADD;
024    import static org.jikesrvm.compilers.opt.ir.Operators.LONG_SUB;
025    import static org.jikesrvm.compilers.opt.ir.Operators.REF_ADD;
026    import static org.jikesrvm.compilers.opt.ir.Operators.REF_SUB;
027    
028    /**
029     * This class implements index equivalence via global value numbering
030     * and 'uniformly generated expressions'.  See EURO-PAR 01 paper for
031     * more details.
032     */
033    class UniformlyGeneratedGVN {
034      static final boolean DEBUG = false;
035    
036      /**
037       * Compute Index Equivalence with uniformly generated global value
038       * numbers.
039       *
040       * <p> PRECONDITIONS: SSA form, register lists computed, SSA bit
041       * computed.
042       *
043       * <p> POSTCONDITION: ir.HIRInfo.uniformlyGeneratedValueNumbers
044       * holds results of the analysis. Does not modify the IR in any other way.
045       *
046       * @param ir the governing IR
047       */
048      public static void perform(IR ir) {
049    
050        // create 'standard' global value numbers.
051        GlobalValueNumberState gvn = null;
052        gvn = new GlobalValueNumberState(ir);
053    
054        // Merge classes related by a constant
055        for (Enumeration<Instruction> e = ir.forwardInstrEnumerator(); e.hasMoreElements();) {
056          Instruction s = e.nextElement();
057          // Check if s is a fixed-point add/subtract instruction with
058          // a constant second operand
059          if (s.operator == INT_ADD ||
060              s.operator == LONG_ADD ||
061              s.operator == REF_ADD ||
062              s.operator == REF_SUB ||
063              s.operator == INT_SUB ||
064              s.operator == LONG_SUB) {
065            Operand val2 = Binary.getVal2(s);
066            if (val2.isConstant()) {
067              Operand lhs = Binary.getResult(s);
068              Operand rhs = Binary.getVal1(s);
069              gvn.mergeClasses(gvn.valueGraph.getVertex(lhs), gvn.valueGraph.getVertex(rhs));
070            }
071          }
072        }
073    
074        if (DEBUG) {
075          System.out.println("@@@@ START OF INDEX EQUIVALENCE VALUE NUMBERS FOR " + ir.method + " @@@@");
076          gvn.printValueNumbers();
077          System.out.println("@@@@ END OF INDEX EQUIVALENCE VALUE NUMBERS FOR " + ir.method + " @@@@");
078        }
079    
080        ir.HIRInfo.uniformlyGeneratedValueNumbers = gvn;
081      }
082    }