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 org.jikesrvm.compilers.opt.DefUse;
016import org.jikesrvm.compilers.opt.Simple;
017import org.jikesrvm.compilers.opt.driver.CompilerPhase;
018import org.jikesrvm.compilers.opt.ir.IR;
019
020/**
021 * This class implements global value numbering
022 * ala Alpern, Wegman and Zadeck, PoPL 88.
023 * See Muchnick p.348 for a nice discussion.
024 */
025class GlobalValueNumber extends CompilerPhase {
026  /** Print verbose debugging output? */
027  private static final boolean DEBUG = false;
028
029  /**
030   * Return this instance of this phase. This phase contains no
031   * per-compilation instance fields.
032   * @param ir not used
033   * @return this
034   */
035  @Override
036  public CompilerPhase newExecution(IR ir) {
037    return this;
038  }
039
040  /**
041   * Return the name of this phase.
042   * @return "Global Value Number"
043   */
044  @Override
045  public final String getName() {
046    return "Global Value Number";
047  }
048
049  /**
050   * Main driver for global value number-related computations
051   * <p> PRECONDITION: Array SSA form
052   * <p> POSTCONDITION: ir.valueNumbers holds global value number state
053   */
054  @Override
055  public final void perform(IR ir) {
056    if (ir.desiredSSAOptions.getAbort()) return;
057
058    // make sure the SSA computation completed successfully
059    // TODO if (!ir.SSAForm()) return;
060    DefUse.computeDU(ir);
061    DefUse.recomputeSSA(ir);
062
063    // before doing global value numbering, get rid of
064    // some troublesome dead code: <MOVE a = a> will
065    // mess up GVN.  These opts also increase the power of GVN.
066    // TODO: restructure these in a composite compiler phase.
067    Simple.copyPropagation(ir);
068    Simple.eliminateDeadInstructions(ir, true);
069    //
070    // compute global value numbers
071    GlobalValueNumberState gvn = new GlobalValueNumberState(ir);
072
073    if (DEBUG) {
074      gvn.printValueNumbers();
075    }
076    ir.HIRInfo.valueNumbers = gvn;
077  }
078}