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.ia32;
014
015import static org.jikesrvm.compilers.opt.ir.Operators.IR_PROLOGUE;
016import static org.jikesrvm.compilers.opt.ir.ia32.ArchOperators.MIR_LOWTABLESWITCH_opcode;
017
018import java.util.Enumeration;
019
020import org.jikesrvm.compilers.opt.driver.CompilerPhase;
021import org.jikesrvm.compilers.opt.ir.BasicBlock;
022import org.jikesrvm.compilers.opt.ir.IR;
023import org.jikesrvm.compilers.opt.ir.Instruction;
024import org.jikesrvm.compilers.opt.ir.Register;
025import org.jikesrvm.compilers.opt.ir.ia32.MIR_LowTableSwitch;
026import org.jikesrvm.compilers.opt.ir.ia32.PhysicalRegisterTools;
027import org.jikesrvm.compilers.opt.ir.operand.Operand;
028import org.jikesrvm.compilers.opt.ir.operand.RegisterOperand;
029
030/**
031 * This class splits live ranges for certain special cases to ensure
032 * correctness during IA32 register allocation.
033 */
034public class MIRSplitRanges extends CompilerPhase {
035
036  /**
037   * Return this instance of this phase. This phase contains no
038   * per-compilation instance fields.
039   * @param ir not used
040   * @return this
041   */
042  @Override
043  public CompilerPhase newExecution(IR ir) {
044    return this;
045  }
046
047  /**
048   * Return the name of this phase
049   * @return "Live Range Splitting"
050   */
051  @Override
052  public final String getName() {
053    return "MIR Range Splitting";
054  }
055
056  /**
057   * The main method.<p>
058   *
059   * We split live ranges for registers around PEIs which have catch
060   * blocks.  Suppose we have a
061   * PEI s which uses a symbolic register r1.  We must ensure that after
062   * register allocation, r1 is NOT assigned to a scratch location in s,
063   * since this would mess up code in the catch block that uses r1.<p>
064   *
065   * So, instead, we introduce a new temporary r2 which holds the value of
066   * r1.  The live range for r2 spans only the instruction s.  Later, we
067   * will ensure that r2 is never spilled.<p>
068   *
069   * TODO: This could be implemented more efficiently.
070   *
071   * @param ir the governing IR
072   */
073  @Override
074  public final void perform(IR ir) {
075
076    java.util.HashMap<Register, Register> newMap = new java.util.HashMap<Register, Register>(5);
077
078    for (Enumeration<BasicBlock> be = ir.getBasicBlocks(); be.hasMoreElements();) {
079      BasicBlock bb = be.nextElement();
080      for (Enumeration<Instruction> ie = bb.forwardInstrEnumerator(); ie.hasMoreElements();) {
081        Instruction s = ie.nextElement();;
082
083        // clear the cache of register assignments
084        newMap.clear();
085
086        // Split live ranges at PEIs and a few special cases to
087        // make sure we can pin values that must be in registers.
088        // NOTE: Any operator that is an IA32 special case that must have
089        //       a particular operand in a register must be mentioned both
090        //       here and in RegisterRestrictions!
091        if (s.isPEI() && s.operator() != IR_PROLOGUE) {
092          if (bb.hasApplicableExceptionalOut(s) || !RegisterRestrictions.SCRATCH_IN_PEI) {
093            splitAllLiveRanges(s, newMap, ir, false);
094          }
095        }
096
097        // handle special cases for IA32
098        //  (1) Some operands must be in registers
099        switch (s.getOpcode()) {
100          case MIR_LOWTABLESWITCH_opcode: {
101            RegisterOperand rOp = MIR_LowTableSwitch.getIndex(s);
102            RegisterOperand temp = findOrCreateTemp(rOp, newMap, ir);
103            // NOTE: Index as marked as a DU because LowTableSwitch is
104            //       going to destroy the value in the register.
105            //       By construction (see ConvertToLowLevelIR), no one will
106            //       ever read the value computed by a LowTableSwitch.
107            //       Therefore, don't insert a move instruction after the
108            //       LowTableSwitch (which would cause IR verification
109            //       problems anyways, since LowTableSwitch is a branch).
110            insertMoveBefore(temp, rOp.copyRO(), s); // move r into 'temp' before s
111            rOp.setRegister(temp.getRegister());
112          }
113          break;
114        }
115      }
116    }
117  }
118
119  /**
120   * Split the live ranges of all register operands of an instruction
121   * @param s      the instruction to process
122   * @param newMap a mapping from symbolics to temporaries
123   * @param ir  the containing IR
124   * @param rootOnly only consider root operands?
125   */
126  private static void splitAllLiveRanges(Instruction s, java.util.HashMap<Register, Register> newMap,
127                                         IR ir, boolean rootOnly) {
128    // walk over each USE
129    for (Enumeration<Operand> u = rootOnly ? s.getRootUses() : s.getUses(); u.hasMoreElements();) {
130      Operand use = u.nextElement();
131      if (use.isRegister()) {
132        RegisterOperand rUse = use.asRegister();
133        RegisterOperand temp = findOrCreateTemp(rUse, newMap, ir);
134        // move 'use' into 'temp' before s
135        insertMoveBefore(temp, rUse.copyRO(), s);
136      }
137    }
138    // walk over each DEF (by defintion defs == root defs)
139    for (Enumeration<Operand> d = s.getDefs(); d.hasMoreElements();) {
140      Operand def = d.nextElement();
141      if (def.isRegister()) {
142        RegisterOperand rDef = def.asRegister();
143        RegisterOperand temp = findOrCreateTemp(rDef, newMap, ir);
144        // move 'temp' into 'r' after s
145        insertMoveAfter(rDef.copyRO(), temp, s);
146      }
147    }
148    // Now go back and replace the registers.
149    for (Enumeration<Operand> ops = rootOnly ? s.getRootOperands() : s.getOperands(); ops.hasMoreElements();) {
150      Operand op = ops.nextElement();
151      if (op.isRegister()) {
152        RegisterOperand rOp = op.asRegister();
153        Register r = rOp.getRegister();
154        Register newR = newMap.get(r);
155        if (newR != null) {
156          rOp.setRegister(newR);
157        }
158      }
159    }
160  }
161
162  /**
163   * Finds or creates a temporary register to cache a symbolic register.
164   *
165   * @param rOp the symbolic register operand
166   * @param map a mapping from symbolics to temporaries
167   * @param ir the governing IR
168   * @return a register operand to cache the symbolic register
169   */
170  private static RegisterOperand findOrCreateTemp(RegisterOperand rOp,
171                                                      java.util.HashMap<Register, Register> map, IR ir) {
172    Register tReg = map.get(rOp.getRegister());
173    if (tReg == null) {
174      RegisterOperand tOp = ir.regpool.makeTemp(rOp.getType());
175      map.put(rOp.getRegister(), tOp.getRegister());
176      return tOp;
177    } else {
178      return new RegisterOperand(tReg, rOp.getType());
179    }
180  }
181
182  /**
183   * Inserts an instruction to move r1 into r2 before instruction s.
184   *
185   * @param r1 the move source
186   * @param r2 the move target
187   * @param s the instruction before which the move needs to be inserted
188   */
189  private static void insertMoveBefore(RegisterOperand r2, RegisterOperand r1, Instruction s) {
190    Instruction m = PhysicalRegisterTools.makeMoveInstruction(r2, r1);
191    s.insertBefore(m);
192  }
193
194  /**
195   * Insert an instruction to move r1 into r2 after instruction s.
196   *
197   * @param r1 the move source
198   * @param r2 the move target
199   * @param s the instruction after which the move needs to be inserted
200   */
201  private static void insertMoveAfter(RegisterOperand r2, RegisterOperand r1, Instruction s) {
202    Instruction m = PhysicalRegisterTools.makeMoveInstruction(r2, r1);
203    s.insertAfter(m);
204  }
205}