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