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.bc2ir;
014
015 import static org.jikesrvm.compilers.opt.ir.Operators.OSR_BARRIER_opcode;
016
017 import java.util.Enumeration;
018 import java.util.LinkedList;
019
020 import org.jikesrvm.VM;
021 import org.jikesrvm.classloader.NormalMethod;
022 import org.jikesrvm.compilers.opt.OptOptions;
023 import org.jikesrvm.compilers.opt.controlflow.BranchOptimizations;
024 import org.jikesrvm.compilers.opt.driver.CompilerPhase;
025 import org.jikesrvm.compilers.opt.ir.BasicBlock;
026 import org.jikesrvm.compilers.opt.ir.IR;
027 import org.jikesrvm.compilers.opt.ir.Instruction;
028 import org.jikesrvm.compilers.opt.ir.OsrBarrier;
029 import org.jikesrvm.compilers.opt.ir.OsrPoint;
030 import org.jikesrvm.compilers.opt.ir.operand.InlinedOsrTypeInfoOperand;
031 import org.jikesrvm.compilers.opt.ir.operand.Operand;
032 import org.jikesrvm.compilers.opt.ir.operand.OsrTypeInfoOperand;
033
034 /**
035 * A phase in the OPT compiler for construction OsrPoint instructions
036 * after inlining.
037 */
038 public class OsrPointConstructor extends CompilerPhase {
039
040 @Override
041 public final boolean shouldPerform(OptOptions options) {
042 return VM.runningVM && options.OSR_GUARDED_INLINING;
043 }
044
045 /**
046 * Return this instance of this phase. This phase contains no
047 * per-compilation instance fields.
048 * @param ir not used
049 * @return this
050 */
051 @Override
052 public CompilerPhase newExecution(IR ir) {
053 return this;
054 }
055
056 @Override
057 public final String getName() {
058 return "OsrPointConstructor";
059 }
060
061 /**
062 * Need to run branch optimizations after
063 */
064 private final BranchOptimizations branchOpts;
065
066 /**
067 * Constructor
068 */
069 public OsrPointConstructor() {
070 branchOpts = new BranchOptimizations(-1, false, false);
071 }
072
073 /**
074 * Goes through each instruction, reconstruct OsrPoint instructions.
075 */
076 @Override
077 public void perform(IR ir) {
078 // 1. collecting OsrPoint instructions
079 LinkedList<Instruction> osrs = collectOsrPoints(ir);
080
081 // new IRPrinter("before renovating osrs").perform(ir);
082
083 // 2. trace OsrBarrier for each OsrPoint, and rebuild OsrPoint
084 renovateOsrPoints(osrs, ir);
085
086 // new IRPrinter("before removing barriers").perform(ir);
087
088 // 3. remove OsrBarriers
089 removeOsrBarriers(ir);
090
091 // new IRPrinter("after removing barriers").perform(ir);
092
093 // 4. reconstruct CFG, cut off pieces after OsrPoint.
094 fixupCFGForOsr(osrs, ir);
095 /*
096 if (VM.TraceOnStackReplacement && (0 != osrs.size())) {
097 new IRPrinter("After OsrPointConstructor").perform(ir);
098 }
099 */
100 /*
101 if (VM.TraceOnStackReplacement && (0 != osrs.size())) {
102 verifyNoOsrBarriers(ir);
103 }
104 */
105 branchOpts.perform(ir);
106 }
107
108 /** Iterates instructions, build a list of OsrPoint instructions. */
109 private LinkedList<Instruction> collectOsrPoints(IR ir) {
110 LinkedList<Instruction> osrs = new LinkedList<Instruction>();
111
112 Enumeration<Instruction> instenum = ir.forwardInstrEnumerator();
113 while (instenum.hasMoreElements()) {
114 Instruction inst = instenum.nextElement();
115
116 if (OsrPoint.conforms(inst)) {
117 osrs.add(inst);
118 }
119 }
120
121 return osrs;
122 }
123
124 /**
125 * For each OsrPoint instruction, traces its OsrBarriers created by
126 * inlining. rebuild OsrPoint instruction to hold all necessary
127 * information to recover from inlined activation.
128 */
129 private void renovateOsrPoints(LinkedList<Instruction> osrs, IR ir) {
130
131 for (int osrIdx = 0, osrSize = osrs.size(); osrIdx < osrSize; osrIdx++) {
132 Instruction osr = osrs.get(osrIdx);
133 LinkedList<Instruction> barriers = new LinkedList<Instruction>();
134
135 // Step 1: collect barriers put before inlined method
136 // in the order of from inner to outer
137 {
138 Instruction bar = (Instruction) osr.scratchObject;
139
140 if (osr.position == null) osr.position = bar.position;
141
142 adjustBCIndex(osr);
143
144 while (bar != null) {
145
146 barriers.add(bar);
147
148 // verify each barrier is clean
149 if (VM.VerifyAssertions) {
150 if (!isBarrierClean(bar)) {
151 VM.sysWriteln("Barrier " + bar + " is not clean!");
152 }
153 VM._assert(isBarrierClean(bar));
154 }
155
156 Instruction callsite = bar.position.getCallSite();
157 if (callsite != null) {
158 bar = (Instruction) callsite.scratchObject;
159
160 if (bar == null) {
161 VM.sysWrite("call site :" + callsite);
162 if (VM.VerifyAssertions) VM._assert(VM.NOT_REACHED);
163 }
164
165 adjustBCIndex(bar);
166 } else {
167 bar = null;
168 }
169 }
170 }
171
172 int inlineDepth = barriers.size();
173
174 if (VM.VerifyAssertions) {
175 if (inlineDepth == 0) {
176 VM.sysWriteln("Inlining depth for " + osr + " is 0!");
177 }
178 VM._assert(inlineDepth != 0);
179 }
180
181 // Step 2: make a new InlinedOsrTypeOperand from barriers
182 int[] methodids = new int[inlineDepth];
183 int[] bcindexes = new int[inlineDepth];
184 byte[][] localTypeCodes = new byte[inlineDepth][];
185 byte[][] stackTypeCodes = new byte[inlineDepth][];
186
187 int totalOperands = 0;
188 // first iteration, count the size of total locals and stack sizes
189 for (int barIdx = 0, barSize = barriers.size(); barIdx < barSize; barIdx++) {
190
191 Instruction bar = barriers.get(barIdx);
192 methodids[barIdx] = bar.position.method.getId();
193 bcindexes[barIdx] = bar.bcIndex;
194
195 OsrTypeInfoOperand typeInfo = OsrBarrier.getTypeInfo(bar);
196 localTypeCodes[barIdx] = typeInfo.localTypeCodes;
197 stackTypeCodes[barIdx] = typeInfo.stackTypeCodes;
198
199 // count the number of operand, but ignore VoidTypeCode
200 totalOperands += OsrBarrier.getNumberOfElements(bar);
201
202 /*
203 if (VM.TraceOnStackReplacement) {
204 VM.sysWriteln("OsrBarrier : "+bar.bcIndex
205 +"@"+bar.position.method
206 +" "+typeInfo);
207 }
208 */
209 }
210
211 // new make InlinedOsrTypeInfoOperand
212 InlinedOsrTypeInfoOperand typeInfo =
213 new InlinedOsrTypeInfoOperand(methodids, bcindexes, localTypeCodes, stackTypeCodes);
214
215 OsrPoint.mutate(osr, osr.operator(), typeInfo, totalOperands);
216
217 // Step 3: second iteration, copy operands
218 int opIndex = 0;
219 for (int barIdx = 0, barSize = barriers.size(); barIdx < barSize; barIdx++) {
220
221 Instruction bar = barriers.get(barIdx);
222 for (int elmIdx = 0, elmSize = OsrBarrier.getNumberOfElements(bar); elmIdx < elmSize; elmIdx++) {
223
224 Operand op = OsrBarrier.getElement(bar, elmIdx);
225
226 if (VM.VerifyAssertions) {
227 if (op == null) {
228 VM.sysWriteln(elmIdx + "th Operand of " + bar + " is null!");
229 }
230 VM._assert(op != null);
231 }
232
233 if (op.isRegister()) {
234 op = op.asRegister().copyU2U();
235 } else {
236 op = op.copy();
237 }
238
239 OsrPoint.setElement(osr, opIndex, op);
240 opIndex++;
241 }
242 }
243 /*
244 if (VM.TraceOnStackReplacement) {
245 VM.sysWriteln("renovated OsrPoint instruction "+osr);
246 VM.sysWriteln(" position "+osr.bcIndex+"@"+osr.position.method);
247 }
248 */
249 // the last OsrBarrier should in the current method
250 if (VM.VerifyAssertions) {
251 Instruction lastBar = barriers.getLast();
252 if (ir.method != lastBar.position.method) {
253 VM.sysWriteln("The last barrier is not in the same method as osr:");
254 VM.sysWriteln(lastBar + "@" + lastBar.position.method);
255 VM.sysWriteln("current method @" + ir.method);
256 }
257 VM._assert(ir.method == lastBar.position.method);
258
259 if (opIndex != totalOperands) {
260 VM.sysWriteln("opIndex and totalOperands do not match:");
261 VM.sysWriteln("opIndex = " + opIndex);
262 VM.sysWriteln("totalOperands = " + totalOperands);
263 }
264 VM._assert(opIndex == totalOperands);
265 } // end of assertion
266 } // end of for loop
267 }
268
269 /**
270 * The OsrBarrier instruction is not in IR, so the bc index was not
271 * adjusted in OSR_AdjustBCIndex
272 */
273 private void adjustBCIndex(Instruction barrier) {
274 NormalMethod source = barrier.position.method;
275 if (source.isForOsrSpecialization()) {
276 barrier.bcIndex -= source.getOsrPrologueLength();
277 }
278 }
279
280 /** remove OsrBarrier instructions. */
281 private void removeOsrBarriers(IR ir) {
282 Enumeration<Instruction> instenum = ir.forwardInstrEnumerator();
283 while (instenum.hasMoreElements()) {
284 Instruction inst = instenum.nextElement();
285 // clean the scratObjects of each instruction
286 inst.scratchObject = null;
287 if (OsrBarrier.conforms(inst)) {
288 inst.remove();
289 }
290 }
291 }
292
293 @SuppressWarnings("unused")
294 // it's a debugging tool
295 private void verifyNoOsrBarriers(IR ir) {
296 VM.sysWrite("Verifying no osr barriers");
297 Enumeration<Instruction> instenum = ir.forwardInstrEnumerator();
298 while (instenum.hasMoreElements()) {
299 Instruction inst = instenum.nextElement();
300 if (inst.operator().opcode == OSR_BARRIER_opcode) {
301 VM.sysWriteln(" NOT SANE");
302 VM.sysWriteln(inst.toString());
303 if (VM.VerifyAssertions) VM._assert(VM.NOT_REACHED);
304 break;
305 }
306 }
307 VM.sysWriteln(" SANE");
308 }
309
310 /** verify barrier is clean by checking the number of valid operands */
311 private boolean isBarrierClean(Instruction barrier) {
312 OsrTypeInfoOperand typeInfo = OsrBarrier.getTypeInfo(barrier);
313 int totalOperands = countNonVoidTypes(typeInfo.localTypeCodes);
314 totalOperands += countNonVoidTypes(typeInfo.stackTypeCodes);
315 return (totalOperands == OsrBarrier.getNumberOfElements(barrier));
316 }
317
318 private int countNonVoidTypes(byte[] typeCodes) {
319 int count = 0;
320 for (int idx = 0, size = typeCodes.length; idx < size; idx++) {
321 if (typeCodes[idx] != org.jikesrvm.osr.OSRConstants.VoidTypeCode) {
322 count++;
323 }
324 }
325 return count;
326 }
327
328 /**
329 * Split each OsrPoint, and connect it to the exit point.
330 */
331 private void fixupCFGForOsr(LinkedList<Instruction> osrs, IR ir) {
332
333 for (int i = 0, n = osrs.size(); i < n; i++) {
334 Instruction osr = osrs.get(i);
335 BasicBlock bb = osr.getBasicBlock();
336 BasicBlock newBB = bb.segregateInstruction(osr, ir);
337 bb.recomputeNormalOut(ir);
338 newBB.recomputeNormalOut(ir);
339 }
340 }
341 }