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