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 */
013package org.jikesrvm.compilers.opt.ssa;
014
015import java.util.Enumeration;
016import org.jikesrvm.compilers.opt.ir.Binary;
017import org.jikesrvm.compilers.opt.ir.IR;
018import org.jikesrvm.compilers.opt.ir.Instruction;
019import org.jikesrvm.compilers.opt.ir.operand.Operand;
020
021import static org.jikesrvm.compilers.opt.ir.Operators.INT_ADD;
022import static org.jikesrvm.compilers.opt.ir.Operators.INT_SUB;
023import static org.jikesrvm.compilers.opt.ir.Operators.LONG_ADD;
024import static org.jikesrvm.compilers.opt.ir.Operators.LONG_SUB;
025import static org.jikesrvm.compilers.opt.ir.Operators.REF_ADD;
026import 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 */
033class 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}