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.regalloc;
014
015import java.util.Enumeration;
016import java.util.HashSet;
017import java.util.Map;
018
019import org.jikesrvm.compilers.opt.DefUse;
020import org.jikesrvm.compilers.opt.OptOptions;
021import org.jikesrvm.compilers.opt.driver.CompilerPhase;
022import org.jikesrvm.compilers.opt.ir.IR;
023import org.jikesrvm.compilers.opt.ir.Instruction;
024import org.jikesrvm.compilers.opt.ir.Move;
025import org.jikesrvm.compilers.opt.ir.Register;
026import org.jikesrvm.compilers.opt.ir.operand.Operand;
027import org.jikesrvm.compilers.opt.liveness.LiveAnalysis;
028
029/**
030 * Coalesce registers in move instructions where possible.
031 */
032public class CoalesceMoves extends CompilerPhase {
033
034  /**
035   *  verbose debugging flag
036   */
037  static final boolean DEBUG = false;
038
039  /**
040   * Return this instance of this phase. This phase contains no
041   * per-compilation instance fields.
042   * @param ir not used
043   * @return this
044   */
045  @Override
046  public CompilerPhase newExecution(IR ir) {
047    return this;
048  }
049
050  /**
051   * Should we perform this phase?
052   * @return <code>true</code> iff move instructions should be
053   *  coalesced after leaving SSA
054   */
055  @Override
056  public final boolean shouldPerform(OptOptions options) {
057    return options.SSA_COALESCE_AFTER;
058  }
059
060  /**
061   * Return a string name for this phase.
062   * @return "Coalesce Moves"
063   */
064  @Override
065  public final String getName() {
066    return "Coalesce Moves";
067  }
068
069  @Override
070  public final void perform(IR ir) {
071    // Compute liveness.
072    LiveAnalysis live = new LiveAnalysis(false /* GC Maps */, false /* don't skip local
073                                                         propagation */);
074    live.perform(ir);
075    // TODO: As of August 2014, we're  saving the live analysis results in the
076    // LiveAnalysis instances. This means that we need to retain the compiler
077    // phase object even if we're only interested in the analysis results.
078    // We ought to save the results via the IR object so that we can throw away
079    // the phase object once it has performed its work.
080
081    // Compute def-use information.
082    DefUse.computeDU(ir);
083
084    Map<Instruction, Integer> instNumbers = ir.numberInstructionsViaMap();
085    Coalesce coalesce = new Coalesce(instNumbers);
086
087    // Maintain a set of dead move instructions.
088    HashSet<Instruction> dead = new HashSet<Instruction>(5);
089
090    // for each Move instruction ...
091    for (Enumeration<Instruction> e = ir.forwardInstrEnumerator(); e.hasMoreElements();) {
092      Instruction s = e.nextElement();
093      if (s.operator().isMove()) {
094        Register r = Move.getResult(s).asRegister().getRegister();
095        if (r.isSymbolic()) {
096          Operand val = Move.getVal(s);
097          if (val != null && val.isRegister()) {
098            Register r2 = val.asRegister().getRegister();
099            if (r2.isSymbolic()) {
100              if (coalesce.attempt(live, r, r2)) {
101                if (DEBUG) System.out.println("COALESCED " + r + " " + r2);
102                dead.add(s);
103              }
104            }
105          }
106        }
107      }
108    }
109
110    // Now remove all dead Move instructions.
111    for (Instruction s : dead) {
112      DefUse.removeInstructionAndUpdateDU(s);
113    }
114  }
115}