Source code

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