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      @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    }