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 org.jikesrvm.compilers.opt.DefUse;
016    import org.jikesrvm.compilers.opt.Simple;
017    import org.jikesrvm.compilers.opt.driver.CompilerPhase;
018    import 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     */
025    class 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      public CompilerPhase newExecution(IR ir) {
036        return this;
037      }
038    
039      /**
040       * Return the name of this phase.
041       * @return "Global Value Number"
042       */
043      public final String getName() {
044        return "Global Value Number";
045      }
046    
047      /**
048       * Main driver for global value number-related computations
049       * <p> PRECONDITION: Array SSA form
050       * <p> POSTCONDITION: ir.valueNumbers holds global value number state
051       *
052       * @param ir the governing IR
053       */
054      public final void perform(IR ir) {
055        if (ir.desiredSSAOptions.getAbort()) return;
056    
057        // make sure the SSA computation completed successfully
058        // TODO if (!ir.SSAForm()) return;
059        DefUse.computeDU(ir);
060        DefUse.recomputeSSA(ir);
061    
062        // before doing global value numbering, get rid of
063        // some troublesome dead code: <MOVE a = a> will
064        // mess up GVN.  These opts also increase the power of GVN.
065        // TODO: restructure these in a composite compiler phase.
066        Simple.copyPropagation(ir);
067        Simple.eliminateDeadInstructions(ir, true);
068        //
069        // compute global value numbers
070        GlobalValueNumberState gvn = new GlobalValueNumberState(ir);
071    
072        if (DEBUG) {
073          gvn.printValueNumbers();
074        }
075        ir.HIRInfo.valueNumbers = gvn;
076      }
077    }