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.hir2lir;
014
015import org.jikesrvm.VM;
016import org.jikesrvm.classloader.RVMArray;
017import org.jikesrvm.classloader.RVMClass;
018import org.jikesrvm.classloader.DynamicTypeCheck;
019import org.jikesrvm.classloader.RVMMethod;
020import org.jikesrvm.classloader.RVMType;
021import org.jikesrvm.classloader.TypeReference;
022import org.jikesrvm.compilers.opt.OptimizingCompilerException;
023import org.jikesrvm.compilers.opt.ir.ALoad;
024import org.jikesrvm.compilers.opt.ir.Binary;
025import org.jikesrvm.compilers.opt.ir.BooleanCmp;
026import org.jikesrvm.compilers.opt.ir.Call;
027import org.jikesrvm.compilers.opt.ir.Goto;
028import org.jikesrvm.compilers.opt.ir.IfCmp;
029import org.jikesrvm.compilers.opt.ir.IfCmp2;
030import org.jikesrvm.compilers.opt.ir.InstanceOf;
031import org.jikesrvm.compilers.opt.ir.Load;
032import org.jikesrvm.compilers.opt.ir.Move;
033import org.jikesrvm.compilers.opt.ir.BasicBlock;
034import org.jikesrvm.compilers.opt.ir.IR;
035import org.jikesrvm.compilers.opt.ir.Instruction;
036import static org.jikesrvm.compilers.opt.ir.Operators.ARRAYLENGTH;
037import static org.jikesrvm.compilers.opt.ir.Operators.BBEND;
038import static org.jikesrvm.compilers.opt.ir.Operators.BOOLEAN_CMP_ADDR;
039import static org.jikesrvm.compilers.opt.ir.Operators.CALL;
040import static org.jikesrvm.compilers.opt.ir.Operators.GET_ARRAY_ELEMENT_TIB_FROM_TIB;
041import static org.jikesrvm.compilers.opt.ir.Operators.GET_DOES_IMPLEMENT_FROM_TIB;
042import static org.jikesrvm.compilers.opt.ir.Operators.GET_SUPERCLASS_IDS_FROM_TIB;
043import static org.jikesrvm.compilers.opt.ir.Operators.GET_TYPE_FROM_TIB;
044import static org.jikesrvm.compilers.opt.ir.Operators.GOTO;
045import static org.jikesrvm.compilers.opt.ir.Operators.GUARD_COMBINE;
046import static org.jikesrvm.compilers.opt.ir.Operators.GUARD_MOVE;
047import static org.jikesrvm.compilers.opt.ir.Operators.INT_2ADDRZerExt;
048import static org.jikesrvm.compilers.opt.ir.Operators.INT_AND;
049import static org.jikesrvm.compilers.opt.ir.Operators.INT_IFCMP;
050import static org.jikesrvm.compilers.opt.ir.Operators.INT_IFCMP2;
051import static org.jikesrvm.compilers.opt.ir.Operators.INT_LOAD;
052import static org.jikesrvm.compilers.opt.ir.Operators.INT_MOVE;
053import static org.jikesrvm.compilers.opt.ir.Operators.INT_SHL;
054import static org.jikesrvm.compilers.opt.ir.Operators.REF_IFCMP;
055import static org.jikesrvm.compilers.opt.ir.Operators.REF_MOVE;
056import static org.jikesrvm.compilers.opt.ir.Operators.TRAP;
057import static org.jikesrvm.compilers.opt.ir.Operators.USHORT_ALOAD;
058import static org.jikesrvm.compilers.opt.ir.Operators.USHORT_LOAD;
059import org.jikesrvm.compilers.opt.ir.StoreCheck;
060import org.jikesrvm.compilers.opt.ir.Trap;
061import org.jikesrvm.compilers.opt.ir.TypeCheck;
062import org.jikesrvm.compilers.opt.ir.operand.BranchProfileOperand;
063import org.jikesrvm.compilers.opt.ir.operand.ConditionOperand;
064import org.jikesrvm.compilers.opt.ir.operand.IntConstantOperand;
065import org.jikesrvm.compilers.opt.ir.operand.LocationOperand;
066import org.jikesrvm.compilers.opt.ir.operand.MethodOperand;
067import org.jikesrvm.compilers.opt.ir.operand.NullConstantOperand;
068import org.jikesrvm.compilers.opt.ir.operand.Operand;
069import org.jikesrvm.compilers.opt.ir.operand.RegisterOperand;
070import org.jikesrvm.compilers.opt.ir.operand.TrapCodeOperand;
071import org.jikesrvm.compilers.opt.ir.operand.TrueGuardOperand;
072import org.jikesrvm.runtime.Entrypoints;
073import org.vmmagic.unboxed.Address;
074import org.vmmagic.unboxed.Offset;
075
076/**
077 * Expansion of Dynamic Type Checking operations.
078 *
079 * @see DynamicTypeCheck
080 */
081abstract class DynamicTypeCheckExpansion extends ConvertToLowLevelIR {
082
083  /**
084   * Expand an instanceof instruction into the LIR sequence that implements
085   * the dynamic type check.  Ref may contain a null ptr at runtime.
086   *
087   * @param s an INSTANCEOF or INSTANCEOF_UNRESOLVED instruction to expand
088   * @param ir the enclosing IR
089   * @return the last Instruction in the generated LIR sequence.
090   */
091  static Instruction instanceOf(Instruction s, IR ir) {
092    RegisterOperand result = InstanceOf.getClearResult(s);
093    TypeReference LHStype = InstanceOf.getType(s).getTypeRef();
094    Operand ref = InstanceOf.getClearRef(s);
095    Instruction next = s.nextInstructionInCodeOrder();
096    if (next.operator() == INT_IFCMP &&
097        IfCmp.getVal1(next) instanceof RegisterOperand &&
098        result.similar(IfCmp.getVal1(next))) {
099      // The result of instanceof is being consumed by a conditional branch.
100      // Optimize this case by generating a branching type check
101      // instead of producing a value.
102      // TODO: This is really not safe: suppose the if is NOT the
103      // only use of the result of the instanceof.
104      // The way to fix this is to add ifInstanceOf and ifNotInstanceOf
105      // operators to the IR and have Simple transform
106      // instanceof, intIfCmp based on the U/D chains.
107      // See defect 2114.
108      Operand val2 = IfCmp.getVal2(next);
109      if (VM.VerifyAssertions) VM._assert(val2.isIntConstant());
110      int ival2 = ((IntConstantOperand) val2).value;
111      ConditionOperand cond = IfCmp.getCond(next);
112      boolean branchCondition =
113          (((ival2 == 0) && (cond.isNOT_EQUAL() || cond.isLESS_EQUAL())) ||
114           ((ival2 == 1) && (cond.isEQUAL() || cond.isGREATER_EQUAL())));
115      BasicBlock branchBB = next.getBranchTarget();
116      RegisterOperand oldGuard = IfCmp.getGuardResult(next);
117      next.remove();
118      BasicBlock fallThroughBB = fallThroughBB(s, ir);
119      BasicBlock falseBranch = branchCondition ? fallThroughBB : branchBB;
120      BasicBlock trueBranch = branchCondition ? branchBB : fallThroughBB;
121      BranchProfileOperand bp = IfCmp.getClearBranchProfile(next);
122      if (branchCondition) bp = bp.flip();
123      Instruction nullComp =
124          IfCmp.create(REF_IFCMP,
125                       oldGuard.copyRO(),
126                       ref.copy(),
127                       new NullConstantOperand(),
128                       ConditionOperand.EQUAL(),
129                       falseBranch.makeJumpTarget(),
130                       BranchProfileOperand.unlikely());
131      s.insertBefore(nullComp);
132      BasicBlock myBlock = s.getBasicBlock();
133      BasicBlock instanceOfBlock = myBlock.splitNodeAt(nullComp, ir);
134      myBlock.insertOut(instanceOfBlock);
135      myBlock.insertOut(falseBranch);
136      ir.cfg.linkInCodeOrder(myBlock, instanceOfBlock);
137      Operand RHStib = getTIB(s, ir, ref, oldGuard.copyRO());
138      return generateBranchingTypeCheck(s, ir, ref.copy(), LHStype, RHStib, trueBranch, falseBranch, oldGuard, bp);
139    } else {
140      // Not a branching pattern
141      RegisterOperand guard = ir.regpool.makeTempValidation();
142      BasicBlock instanceOfBlock = s.getBasicBlock().segregateInstruction(s, ir);
143      BasicBlock prevBB = instanceOfBlock.prevBasicBlockInCodeOrder();
144      BasicBlock nextBB = instanceOfBlock.nextBasicBlockInCodeOrder();
145      BasicBlock nullCaseBB = instanceOfBlock.createSubBlock(s.bcIndex, ir, .01f);
146      prevBB.appendInstruction(IfCmp.create(REF_IFCMP,
147                                            guard,
148                                            ref.copy(),
149                                            new NullConstantOperand(),
150                                            ConditionOperand.EQUAL(),
151                                            nullCaseBB.makeJumpTarget(),
152                                            BranchProfileOperand.unlikely()));
153      nullCaseBB.appendInstruction(Move.create(INT_MOVE, result.copyD2D(), IC(0)));
154      nullCaseBB.appendInstruction(Goto.create(GOTO, nextBB.makeJumpTarget()));
155      // Stitch together the CFG; add nullCaseBB to the end of code array.
156      prevBB.insertOut(nullCaseBB);
157      nullCaseBB.insertOut(nextBB);
158      ir.cfg.addLastInCodeOrder(nullCaseBB);
159      Operand RHStib = getTIB(s, ir, ref, guard.copyD2U());
160      return generateValueProducingTypeCheck(s, ir, ref.copy(), LHStype, RHStib, result);
161    }
162  }
163
164  /**
165   * Expand an instanceof instruction into the LIR sequence that implements
166   * the dynamic type check.  Ref is known to never contain a null ptr at
167   * runtime.
168   *
169   * @param s an INSTANCEOF_NOTNULL instruction to expand
170   * @param ir the enclosing IR
171   * @return the last Instruction in the generated LIR sequence.
172   */
173  static Instruction instanceOfNotNull(Instruction s, IR ir) {
174    RegisterOperand result = InstanceOf.getClearResult(s);
175    TypeReference LHStype = InstanceOf.getType(s).getTypeRef();
176    Operand ref = InstanceOf.getClearRef(s);
177    Operand guard = InstanceOf.getClearGuard(s);
178    Instruction next = s.nextInstructionInCodeOrder();
179    if (next.operator() == INT_IFCMP &&
180        IfCmp.getVal1(next) instanceof RegisterOperand &&
181        result.similar(IfCmp.getVal1(next))) {
182      // The result of instanceof is being consumed by a conditional branch.
183      // Optimize this case by generating a branching type
184      // check instead of producing a value.
185      Operand val2 = IfCmp.getVal2(next);
186      if (VM.VerifyAssertions) {
187        VM._assert(val2.isIntConstant());
188      }
189      int ival2 = ((IntConstantOperand) val2).value;
190      ConditionOperand cond = IfCmp.getCond(next);
191      boolean branchCondition =
192          (((ival2 == 0) && (cond.isNOT_EQUAL() || cond.isLESS_EQUAL())) ||
193           ((ival2 == 1) && (cond.isEQUAL() || cond.isGREATER_EQUAL())));
194      BasicBlock branchBB = next.getBranchTarget();
195      RegisterOperand oldGuard = IfCmp.getGuardResult(next);
196      next.remove();
197      BasicBlock fallThroughBB = fallThroughBB(s, ir);
198      Operand RHStib = getTIB(s, ir, ref, guard);
199      if (branchCondition) {
200        return generateBranchingTypeCheck(s,
201                                          ir,
202                                          ref.copy(),
203                                          LHStype,
204                                          RHStib,
205                                          branchBB,
206                                          fallThroughBB,
207                                          oldGuard,
208                                          IfCmp.getClearBranchProfile(next).flip());
209      } else {
210        return generateBranchingTypeCheck(s,
211                                          ir,
212                                          ref.copy(),
213                                          LHStype,
214                                          RHStib,
215                                          fallThroughBB,
216                                          branchBB,
217                                          oldGuard,
218                                          IfCmp.getClearBranchProfile(next));
219      }
220    } else {
221      // Not a branching pattern
222      Operand RHStib = getTIB(s, ir, ref, guard);
223      return generateValueProducingTypeCheck(s, ir, ref.copy(), LHStype, RHStib, result);
224    }
225  }
226
227  /**
228   * Expand a checkcast instruction into the LIR sequence that implements the
229   * dynamic type check, raising a ClassCastException when the type check
230   * fails. Ref may contain a null ptr at runtime.
231   *
232   * @param s a CHECKCAST or CHECKCAST_UNRESOLVED instruction to expand
233   * @param ir the enclosing IR
234   * @return the last Instruction in the generated LIR sequence.
235   */
236  static Instruction checkcast(Instruction s, IR ir) {
237    Operand ref = TypeCheck.getClearRef(s);
238    TypeReference LHStype = TypeCheck.getType(s).getTypeRef();
239    RegisterOperand guard = ir.regpool.makeTempValidation();
240    Instruction nullCond =
241        IfCmp.create(REF_IFCMP,
242                     guard,
243                     ref.copy(),
244                     new NullConstantOperand(),
245                     ConditionOperand.EQUAL(),
246                     null,
247                     // KLUDGE...we haven't created the block yet!
248                     new BranchProfileOperand());
249    s.insertBefore(nullCond);
250    BasicBlock myBlock = s.getBasicBlock();
251    BasicBlock failBlock = myBlock.createSubBlock(s.bcIndex, ir, .0001f);
252    BasicBlock instanceOfBlock = myBlock.splitNodeAt(nullCond, ir);
253    BasicBlock succBlock = instanceOfBlock.splitNodeAt(s, ir);
254    succBlock.firstInstruction().insertAfter(Move.create(REF_MOVE, TypeCheck.getClearResult(s), ref.copy()));
255    IfCmp.setTarget(nullCond, succBlock.makeJumpTarget()); // fixup KLUDGE
256    myBlock.insertOut(instanceOfBlock);
257    myBlock.insertOut(succBlock);
258    instanceOfBlock.insertOut(failBlock);
259    instanceOfBlock.insertOut(succBlock);
260    ir.cfg.linkInCodeOrder(myBlock, instanceOfBlock);
261    ir.cfg.linkInCodeOrder(instanceOfBlock, succBlock);
262    ir.cfg.addLastInCodeOrder(failBlock);
263    Instruction raiseError = Trap.create(TRAP, null, TrapCodeOperand.CheckCast());
264    raiseError.copyPosition(s);
265    failBlock.appendInstruction(raiseError);
266    Operand RHStib = getTIB(s, ir, ref, guard.copyD2U());
267    return generateBranchingTypeCheck(s,
268                                      ir,
269                                      ref.copy(),
270                                      LHStype,
271                                      RHStib,
272                                      succBlock,
273                                      failBlock,
274                                      guard.copyRO(),
275                                      BranchProfileOperand.never());
276  }
277
278  /**
279   * Expand a checkcast instruction into the LIR sequence that implements the
280   * dynamic type check, raising a ClassCastException when the type check
281   * fails. Ref is known to never contain a null ptr at runtime.
282   *
283   * @param s a CHECKCAST_NOTNULL instruction to expand
284   * @param ir the enclosing IR
285   * @return the last Instruction in the generated LIR sequence.
286   */
287  static Instruction checkcastNotNull(Instruction s, IR ir) {
288    Operand ref = TypeCheck.getClearRef(s);
289    TypeReference LHStype = TypeCheck.getType(s).getTypeRef();
290    Operand guard = TypeCheck.getClearGuard(s);
291    BasicBlock myBlock = s.getBasicBlock();
292    BasicBlock failBlock = myBlock.createSubBlock(s.bcIndex, ir, .0001f);
293    BasicBlock succBlock = myBlock.splitNodeAt(s, ir);
294    succBlock.firstInstruction().insertAfter(Move.create(REF_MOVE, TypeCheck.getClearResult(s), ref.copy()));
295    myBlock.insertOut(failBlock);
296    myBlock.insertOut(succBlock);
297    ir.cfg.linkInCodeOrder(myBlock, succBlock);
298    ir.cfg.addLastInCodeOrder(failBlock);
299    Instruction raiseError = Trap.create(TRAP, null, TrapCodeOperand.CheckCast());
300    raiseError.copyPosition(s);
301    failBlock.appendInstruction(raiseError);
302    Operand RHStib = getTIB(s, ir, ref, guard);
303    return generateBranchingTypeCheck(s,
304                                      ir,
305                                      ref.copy(),
306                                      LHStype,
307                                      RHStib,
308                                      succBlock,
309                                      failBlock,
310                                      ir.regpool.makeTempValidation(),
311                                      BranchProfileOperand.never());
312  }
313
314  /**
315   * Expand a checkcastInterface instruction into the LIR sequence that
316   * implements the dynamic type check, raising an IncompataibleClassChangeError
317   * if the type check fails.
318   * Ref is known to never contain a null ptr at runtime.
319   *
320   * @param s a MUST_IMPLEMENT_INTERFACE instruction to expand
321   * @param ir the enclosing IR
322   * @return the last Instruction in the generated LIR sequence.
323   */
324  static Instruction mustImplementInterface(Instruction s, IR ir) {
325    Operand ref = TypeCheck.getClearRef(s);
326    RVMClass LHSClass = (RVMClass) TypeCheck.getType(s).getVMType();
327    if (VM.VerifyAssertions) VM._assert(LHSClass != null, "Should be resolvable...");
328    int interfaceIndex = LHSClass.getDoesImplementIndex();
329    int interfaceMask = LHSClass.getDoesImplementBitMask();
330    Operand guard = TypeCheck.getClearGuard(s);
331    BasicBlock myBlock = s.getBasicBlock();
332    BasicBlock failBlock = myBlock.createSubBlock(s.bcIndex, ir, .0001f);
333    BasicBlock succBlock = myBlock.splitNodeAt(s, ir);
334    succBlock.firstInstruction().insertAfter(Move.create(REF_MOVE, TypeCheck.getClearResult(s), ref.copy()));
335    myBlock.insertOut(failBlock);
336    myBlock.insertOut(succBlock);
337    ir.cfg.linkInCodeOrder(myBlock, succBlock);
338    ir.cfg.addLastInCodeOrder(failBlock);
339    Instruction raiseError = Trap.create(TRAP, null, TrapCodeOperand.MustImplement());
340    raiseError.copyPosition(s);
341    failBlock.appendInstruction(raiseError);
342
343    Operand RHStib = getTIB(s, ir, ref, guard);
344    RegisterOperand doesImpl = InsertUnary(s, ir, GET_DOES_IMPLEMENT_FROM_TIB, TypeReference.IntArray, RHStib);
345
346    if (DynamicTypeCheck.MIN_DOES_IMPLEMENT_SIZE <= interfaceIndex) {
347      RegisterOperand doesImplLength =
348          InsertGuardedUnary(s, ir, ARRAYLENGTH, TypeReference.Int, doesImpl.copyD2U(), TG());
349      Instruction lengthCheck =
350          IfCmp.create(INT_IFCMP,
351              ir.regpool.makeTempValidation(),
352              doesImplLength,
353              IC(interfaceIndex),
354              ConditionOperand.LESS_EQUAL(),
355              failBlock.makeJumpTarget(),
356              BranchProfileOperand.never());
357      s.insertBefore(lengthCheck);
358      myBlock.splitNodeWithLinksAt(lengthCheck, ir);
359      myBlock.insertOut(failBlock); // required due to splitNode!
360    }
361    RegisterOperand entry =
362        InsertLoadOffset(s,
363                         ir,
364                         INT_LOAD,
365                         TypeReference.Int,
366                         doesImpl,
367                         Offset.fromIntZeroExtend(interfaceIndex << 2),
368                         new LocationOperand(TypeReference.Int),
369                         TG());
370    RegisterOperand bit = insertBinary(s, ir, INT_AND, TypeReference.Int, entry, IC(interfaceMask));
371    IfCmp.mutate(s,
372                 INT_IFCMP,
373                 ir.regpool.makeTempValidation(),
374                 bit,
375                 IC(0),
376                 ConditionOperand.EQUAL(),
377                 failBlock.makeJumpTarget(),
378                 BranchProfileOperand.never());
379    return s;
380  }
381
382  /**
383   * Expand an object array store check into the LIR sequence that
384   * implements it.
385   *
386   * @param s an OBJARRAY_STORE_CHECK instruction to expand
387   * @param ir the enclosing IR
388   * @param couldBeNull is it possible that the element being stored is null?
389   * @return the last Instruction in the generated LIR sequence.
390   */
391  static Instruction arrayStoreCheck(Instruction s, IR ir, boolean couldBeNull) {
392    RegisterOperand guardResult = StoreCheck.getGuardResult(s);
393    Operand arrayRef = StoreCheck.getClearRef(s);
394    Operand elemRef = StoreCheck.getClearVal(s);
395    Operand guard = StoreCheck.getClearGuard(s);
396    if (elemRef instanceof NullConstantOperand) {
397      Instruction continueAt = s.prevInstructionInCodeOrder();
398      s.remove();
399      return continueAt;
400    }
401    BasicBlock myBlock = s.getBasicBlock();
402    BasicBlock contBlock = myBlock.splitNodeAt(s, ir);
403    BasicBlock trapBlock = myBlock.createSubBlock(s.bcIndex, ir, .0001f);
404    BasicBlock curBlock = myBlock;
405    Move.mutate(s, GUARD_MOVE, guardResult, new TrueGuardOperand());
406
407    // Set up a block with a trap instruction that we can jump to if the
408    // store check fails
409    Instruction trap = Trap.create(TRAP, null, TrapCodeOperand.StoreCheck());
410    trap.copyPosition(s);
411    trapBlock.appendInstruction(trap);
412    ir.cfg.addLastInCodeOrder(trapBlock);
413
414    Operand rhsGuard = guard;
415    if (couldBeNull) {
416      // if rhs is null, then the checkcast succeeds
417      rhsGuard = ir.regpool.makeTempValidation();
418      contBlock.prependInstruction(Binary.create(GUARD_COMBINE,
419                                                 guardResult.copyRO(),
420                                                 guardResult.copyRO(),
421                                                 rhsGuard.copy()));
422      curBlock.appendInstruction(IfCmp.create(REF_IFCMP,
423                                              rhsGuard.asRegister(),
424                                              elemRef,
425                                              new NullConstantOperand(),
426                                              ConditionOperand.EQUAL(),
427                                              contBlock.makeJumpTarget(),
428                                              new BranchProfileOperand()));
429      curBlock.insertOut(contBlock);
430      curBlock = advanceBlock(s.bcIndex, curBlock, ir);
431    }
432
433    // Find out what we think the compile time type of the lhs is.
434    // Based on this, we can do one of several things:
435    //  (1) If the compile time element type is a final proper class, then a
436    //      TIB comparision of the runtime elemRef type and the
437    //      compile time element type is definitive.
438    //  (2) If the compile time type is known to be the declared type,
439    //      then inject a short-circuit test to see if the
440    //      runtime lhs type is the same as the compile-time lhs type.
441    //  (3) If the compile time element type is a proper class other than
442    //      java.lang.Object, then a subclass test of the runtime LHS elem type
443    //      and the runtime elemRef type is definitive.  Note: we must exclude
444    //      java.lang.Object because if the compile time element type is
445    //      java.lang.Object, then the runtime-element type might actually be
446    //      an interface (ie not a proper class), and we won't be testing the right thing!
447    // If we think the compile time type is JavaLangObjectType then
448    // we lost type information due to unloaded classes causing
449    // imprecise meets.  This should only happen once in a blue moon,
450    // so don't bother trying anything clever when it does.
451    RVMType compType = arrayRef.getType().peekType();
452    if (compType != null && !compType.isJavaLangObjectType()) {
453      // optionally (1) from above
454      if (compType.getDimensionality() == 1) {
455        RVMClass etc = (RVMClass) compType.asArray().getElementType();
456        if (etc.isResolved() && etc.isFinal()) {
457          if (VM.VerifyAssertions) VM._assert(!etc.isInterface());
458          Operand rhsTIB = getTIB(curBlock.lastInstruction(), ir, elemRef.copy(), rhsGuard.copy());
459          Operand etTIB = getTIB(curBlock.lastInstruction(), ir, etc);
460          curBlock.appendInstruction(IfCmp.create(REF_IFCMP,
461                                                  guardResult.copyRO(),
462                                                  rhsTIB,
463                                                  etTIB,
464                                                  ConditionOperand.NOT_EQUAL(),
465                                                  trapBlock.makeJumpTarget(),
466                                                  BranchProfileOperand.never()));
467          curBlock.insertOut(trapBlock);
468          curBlock.insertOut(contBlock);
469          ir.cfg.linkInCodeOrder(curBlock, contBlock);
470          return curBlock.lastInstruction();
471        }
472      }
473
474      // optionally (2) from above
475      Operand lhsTIB = getTIB(curBlock.lastInstruction(), ir, arrayRef, guard);
476      if (((arrayRef instanceof RegisterOperand) && ((RegisterOperand) arrayRef).isDeclaredType()) ||
477          compType == RVMType.JavaLangObjectArrayType) {
478        Operand declTIB = getTIB(curBlock.lastInstruction(), ir, compType);
479        curBlock.appendInstruction(IfCmp.create(REF_IFCMP,
480                                                guardResult.copyRO(),
481                                                declTIB,
482                                                lhsTIB,
483                                                ConditionOperand.EQUAL(),
484                                                contBlock.makeJumpTarget(),
485                                                new BranchProfileOperand()));
486        curBlock.insertOut(contBlock);
487        curBlock = advanceBlock(s.bcIndex, curBlock, ir);
488      }
489
490      // On our way to doing (3) from above attempt another short-circuit.
491      // If lhsElemTIB == rhsTIB, then we are done.
492      Operand rhsTIB = getTIB(curBlock.lastInstruction(), ir, elemRef.copy(), rhsGuard.copy());
493      RegisterOperand lhsElemTIB =
494          InsertUnary(curBlock.lastInstruction(),
495                      ir,
496                      GET_ARRAY_ELEMENT_TIB_FROM_TIB,
497                      TypeReference.TIB,
498                      lhsTIB.copy());
499      curBlock.appendInstruction(IfCmp.create(REF_IFCMP,
500                                              guardResult.copyRO(),
501                                              rhsTIB,
502                                              lhsElemTIB,
503                                              ConditionOperand.EQUAL(),
504                                              contBlock.makeJumpTarget(),
505                                              new BranchProfileOperand()));
506      curBlock.insertOut(contBlock);
507      curBlock = advanceBlock(s.bcIndex, curBlock, ir);
508
509      // Optionally (3) from above
510      if (compType.getDimensionality() == 1) {
511        RVMClass etc = (RVMClass) compType.asArray().getElementType();
512        if (etc.isResolved() && !etc.isInterface() && !etc.isJavaLangObjectType()) {
513          RegisterOperand lhsElemType =
514              InsertUnary(curBlock.lastInstruction(),
515                          ir,
516                          GET_TYPE_FROM_TIB,
517                          TypeReference.Type,
518                          lhsElemTIB.copyU2U());
519          RegisterOperand rhsSuperclassIds =
520              InsertUnary(curBlock.lastInstruction(),
521                          ir,
522                          GET_SUPERCLASS_IDS_FROM_TIB,
523                          TypeReference.ShortArray,
524                          rhsTIB.copy());
525          RegisterOperand lhsElemDepth =
526              getField(curBlock.lastInstruction(), ir, lhsElemType, Entrypoints.depthField, TG());
527          RegisterOperand rhsSuperclassIdsLength =
528              InsertGuardedUnary(curBlock.lastInstruction(),
529                                 ir,
530                                 ARRAYLENGTH,
531                                 TypeReference.Int,
532                                 rhsSuperclassIds.copyD2U(),
533                                 TG());
534          curBlock.appendInstruction(IfCmp.create(INT_IFCMP,
535                                                  guardResult.copyRO(),
536                                                  lhsElemDepth,
537                                                  rhsSuperclassIdsLength,
538                                                  ConditionOperand.GREATER_EQUAL(),
539                                                  trapBlock.makeJumpTarget(),
540                                                  BranchProfileOperand.never()));
541          curBlock.insertOut(trapBlock);
542          curBlock = advanceBlock(s.bcIndex, curBlock, ir);
543
544          RegisterOperand lhsElemId =
545              getField(curBlock.lastInstruction(), ir, lhsElemType.copyD2U(), Entrypoints.idField, TG());
546          RegisterOperand refCandidate = ir.regpool.makeTemp(TypeReference.Short);
547          LocationOperand loc = new LocationOperand(TypeReference.Short);
548          if (LOWER_ARRAY_ACCESS) {
549            RegisterOperand lhsDepthOffset =
550                insertBinary(curBlock.lastInstruction(),
551                             ir,
552                             INT_SHL,
553                             TypeReference.Int,
554                             lhsElemDepth.copyD2U(),
555                             IC(1));
556            lhsDepthOffset =
557                InsertUnary(curBlock.lastInstruction(),
558                            ir,
559                            INT_2ADDRZerExt,
560                            TypeReference.Offset,
561                            lhsDepthOffset.copy());
562            curBlock.appendInstruction(Load.create(USHORT_LOAD,
563                                                   refCandidate,
564                                                   rhsSuperclassIds,
565                                                   lhsDepthOffset,
566                                                   loc,
567                                                   TG()));
568          } else {
569            curBlock.appendInstruction(ALoad.create(USHORT_ALOAD,
570                                                    refCandidate,
571                                                    rhsSuperclassIds,
572                                                    lhsElemDepth.copyRO(),
573                                                    loc,
574                                                    TG()));
575          }
576          curBlock.appendInstruction(IfCmp.create(INT_IFCMP,
577                                                  guardResult.copyRO(),
578                                                  refCandidate.copyD2U(),
579                                                  lhsElemId,
580                                                  ConditionOperand.NOT_EQUAL(),
581                                                  trapBlock.makeJumpTarget(),
582                                                  BranchProfileOperand.never()));
583          curBlock.insertOut(trapBlock);
584          curBlock.insertOut(contBlock);
585          ir.cfg.linkInCodeOrder(curBlock, contBlock);
586          return curBlock.lastInstruction();
587        }
588      }
589    }
590
591    // Call RuntimeEntrypoints.checkstore.
592    RVMMethod target = Entrypoints.checkstoreMethod;
593    Instruction call =
594        Call.create2(CALL,
595                     null,
596                     AC(target.getOffset()),
597                     MethodOperand.STATIC(target),
598                     rhsGuard.copy(),
599                     arrayRef.copy(),
600                     elemRef.copy());
601    call.copyPosition(s);
602    curBlock.appendInstruction(call);
603    curBlock.insertOut(contBlock);
604    ir.cfg.linkInCodeOrder(curBlock, contBlock);
605    return callHelper(call, ir);
606  }
607
608  /**
609   * Generate a value-producing dynamic type check.
610   * This routine assumes that the CFG and code order are
611   * already correctly established.
612   * This routine must either remove s or mutuate it.
613   *
614   * @param s        The Instruction that is to be replaced by
615   *                  a value producing type check
616   * @param ir       The IR containing the instruction to be expanded.
617   * @param RHSobj   The RegisterOperand containing the rhs object.
618   * @param LHStype  The RVMType to be tested against.
619   * @param RHStib   The Operand containing the TIB of the rhs.
620   * @param result   The RegisterOperand that the result of dynamic
621   *                 type check is to be stored in.
622   * @return the opt instruction immediately before the
623   *         instruction to continue expansion.
624   */
625  private static Instruction generateValueProducingTypeCheck(Instruction s, IR ir, Operand RHSobj,
626                                                                 TypeReference LHStype, Operand RHStib,
627                                                                 RegisterOperand result) {
628    // Is LHStype a class?
629    if (LHStype.isClassType()) {
630      RVMClass LHSclass = (RVMClass) LHStype.peekType();
631      if (LHSclass != null && LHSclass.isResolved()) {
632        // Cases 4, 5, and 6 of DynamicTypeCheck: LHSclass is a
633        // resolved class or interface
634        if (LHSclass.isInterface()) {
635          // A resolved interface (case 4)
636          int interfaceIndex = LHSclass.getDoesImplementIndex();
637          int interfaceMask = LHSclass.getDoesImplementBitMask();
638          RegisterOperand doesImpl =
639              InsertUnary(s, ir, GET_DOES_IMPLEMENT_FROM_TIB, TypeReference.IntArray, RHStib);
640          RegisterOperand entry =
641              InsertLoadOffset(s,
642                               ir,
643                               INT_LOAD,
644                               TypeReference.Int,
645                               doesImpl,
646                               Offset.fromIntZeroExtend(interfaceIndex << 2),
647                               new LocationOperand(TypeReference.Int),
648                               TG());
649          RegisterOperand bit = insertBinary(s, ir, INT_AND, TypeReference.Int, entry, IC(interfaceMask));
650          //save to use the cheaper ADDR version of BOOLEAN_CMP
651          s.insertBefore(BooleanCmp.create(BOOLEAN_CMP_ADDR,
652                                           result,
653                                           bit,
654                                           AC(Address.zero()),
655                                           ConditionOperand.NOT_EQUAL(),
656                                           new BranchProfileOperand()));
657
658          if (DynamicTypeCheck.MIN_DOES_IMPLEMENT_SIZE <= interfaceIndex) {
659            RegisterOperand doesImplLength =
660                InsertGuardedUnary(s, ir, ARRAYLENGTH, TypeReference.Int, doesImpl.copy(), TG());
661            RegisterOperand boundscheck = ir.regpool.makeTempInt();
662            //save to use the cheaper ADDR version of BOOLEAN_CMP
663            s.insertBefore(BooleanCmp.create(BOOLEAN_CMP_ADDR,
664                                             boundscheck,
665                                             doesImplLength,
666                                             AC(Address.fromIntSignExtend(interfaceIndex)),
667                                             ConditionOperand.GREATER(),
668                                             new BranchProfileOperand()));
669            s.insertBefore(Binary.create(INT_AND, result.copyD2D(), result.copyD2U(), boundscheck.copyD2U()));
670          }
671          Instruction continueAt = s.prevInstructionInCodeOrder();
672          s.remove();
673          return continueAt;
674        } else {
675          // A resolved class (cases 5 and 6 in DynamicTypeCheck)
676          if (LHSclass.isFinal()) {
677            // For a final class, we can do a PTR compare of
678            // rhsTIB and the TIB of the class
679            Operand classTIB = getTIB(s, ir, LHSclass);
680            BooleanCmp.mutate(s,
681                              BOOLEAN_CMP_ADDR,
682                              result,
683                              RHStib,
684                              classTIB,
685                              ConditionOperand.EQUAL(),
686                              new BranchProfileOperand());
687            return s.prevInstructionInCodeOrder();
688          } else {
689            // Do the full blown case 5 or 6 typecheck.
690            int LHSDepth = LHSclass.getTypeDepth();
691            int LHSId = LHSclass.getId();
692            RegisterOperand superclassIds =
693                InsertUnary(s, ir, GET_SUPERCLASS_IDS_FROM_TIB, TypeReference.ShortArray, RHStib);
694            RegisterOperand refCandidate =
695                InsertLoadOffset(s,
696                                 ir,
697                                 USHORT_LOAD,
698                                 TypeReference.Short,
699                                 superclassIds,
700                                 Offset.fromIntZeroExtend(LHSDepth << 1),
701                                 new LocationOperand(TypeReference.Short),
702                                 TG());
703            //save to use the cheaper ADDR version of BOOLEAN_CMP
704            s.insertBefore(BooleanCmp.create(BOOLEAN_CMP_ADDR,
705                                             result,
706                                             refCandidate,
707                                             AC(Address.fromIntZeroExtend(LHSId)),
708                                             ConditionOperand.EQUAL(),
709                                             new BranchProfileOperand()));
710            if (DynamicTypeCheck.MIN_SUPERCLASS_IDS_SIZE <= LHSDepth) {
711              RegisterOperand superclassIdsLength =
712                  InsertGuardedUnary(s, ir, ARRAYLENGTH, TypeReference.Int, superclassIds.copyD2U(), TG());
713              RegisterOperand boundscheck = ir.regpool.makeTempInt();
714              //save to use the cheaper ADDR version of BOOLEAN_CMP
715              s.insertBefore(BooleanCmp.create(BOOLEAN_CMP_ADDR,
716                                               boundscheck,
717                                               superclassIdsLength,
718                                               AC(Address.fromIntSignExtend(LHSDepth)),
719                                               ConditionOperand.GREATER(),
720                                               new BranchProfileOperand()));
721              s.insertBefore(Binary.create(INT_AND, result.copyD2D(), result.copyD2U(), boundscheck.copyD2U()));
722            }
723            Instruction continueAt = s.prevInstructionInCodeOrder();
724            s.remove();
725            return continueAt;
726          }
727        }
728      } else {
729        // A non-resolved class or interface.
730        // We expect these to be extremely uncommon in opt code in AOS.
731        // Mutate s into a call to RuntimeEntrypoints.instanceOf
732        RVMMethod target = Entrypoints.instanceOfMethod;
733        Call.mutate2(s,
734                     CALL,
735                     result,
736                     AC(target.getOffset()),
737                     MethodOperand.STATIC(target),
738                     RHSobj,
739                     IC(LHStype.getId()));
740        return callHelper(s, ir);
741      }
742    }
743    if (LHStype.isArrayType()) {
744      // Case 2 of DynamicTypeCheck: LHS is an array.
745      RVMArray LHSArray = (RVMArray) LHStype.peekType();
746      if (LHSArray != null) {
747        RVMType innermostElementType = LHSArray.getInnermostElementType();
748        if (innermostElementType.isPrimitiveType() || innermostElementType.isUnboxedType() ||
749            (innermostElementType.asClass().isResolved() && innermostElementType.asClass().isFinal())) {
750          // [^k of primitive or [^k of final class. Just like final classes,
751          // a PTR compare of rhsTIB and the TIB of the class gives the answer.
752          Operand classTIB = getTIB(s, ir, LHSArray);
753          BooleanCmp.mutate(s,
754                            BOOLEAN_CMP_ADDR,
755                            result,
756                            RHStib,
757                            classTIB,
758                            ConditionOperand.EQUAL(),
759                            new BranchProfileOperand());
760          return s;
761        }
762      }
763      // We're going to have to branch anyways, so reduce to a branching case
764      // and do the real work there.
765      return convertToBranchingTypeCheck(s, ir, RHSobj, LHStype, RHStib, result);
766    }
767    OptimizingCompilerException.UNREACHABLE();
768    return null;
769  }
770
771  /**
772   * Generate wrapper around branching type check to get a
773   * value producing type check.
774   * @param s        The Instruction that is to be replaced by
775   *                  a value producing type check
776   * @param ir       The IR containing the instruction to be expanded.
777   * @param RHSobj   The RegisterOperand containing the rhs object.
778   * @param LHStype  The TypeReference to be tested against.
779   * @param RHStib   The Operand containing the TIB of the rhs.
780   * @param result   The RegisterOperand that the result of dynamic
781   * @return the opt instruction immediately before the instruction to
782   *         continue expansion.
783   */
784  private static Instruction convertToBranchingTypeCheck(Instruction s, IR ir, Operand RHSobj,
785                                                             TypeReference LHStype, Operand RHStib,
786                                                             RegisterOperand result) {
787    BasicBlock myBlock = s.getBasicBlock();
788    BasicBlock contBlock = myBlock.splitNodeAt(s, ir);
789    BasicBlock trueBlock = myBlock.createSubBlock(s.bcIndex, ir);
790    BasicBlock falseBlock = myBlock.createSubBlock(s.bcIndex, ir);
791    myBlock.insertOut(trueBlock);
792    myBlock.insertOut(falseBlock);
793    trueBlock.insertOut(contBlock);
794    falseBlock.insertOut(contBlock);
795    ir.cfg.linkInCodeOrder(myBlock, trueBlock);
796    ir.cfg.linkInCodeOrder(trueBlock, falseBlock);
797    ir.cfg.linkInCodeOrder(falseBlock, contBlock);
798    trueBlock.appendInstruction(Move.create(INT_MOVE, result, IC(1)));
799    trueBlock.appendInstruction(Goto.create(GOTO, contBlock.makeJumpTarget()));
800    falseBlock.appendInstruction(Move.create(INT_MOVE, result.copyD2D(), IC(0)));
801    return generateBranchingTypeCheck(s,
802                                      ir,
803                                      RHSobj,
804                                      LHStype,
805                                      RHStib,
806                                      trueBlock,
807                                      falseBlock,
808                                      ir.regpool.makeTempValidation(),
809                                      new BranchProfileOperand());
810  }
811
812  /**
813   * Generate a branching dynamic type check.
814   * This routine assumes that the CFG and code order are already
815   * correctly established.
816   * This routine must either remove s or mutate it.
817   *
818   * @param s          The Instruction that is to be replaced by a
819   *                   branching type check
820   * @param ir         The IR containing the instruction to be expanded.
821   * @param RHSobj     The RegisterOperand containing the rhs object.
822   * @param LHStype    The TypeReference to be tested against.
823   * @param RHStib     The Operand containing the TIB of the rhs.
824   * @param trueBlock  The BasicBlock to continue at if the typecheck
825   *                   evaluates to true
826   * @param falseBlock The BasicBlock to continue at if the typecheck
827   *                   evaluates to false.
828   * @param oldGuard   A suitable guard operand (not necessarily related
829   *                   the instruction that is to be replaced).
830   * @param falseProb   The probability that typecheck will branch to the falseBlock
831   * @return the opt instruction immediately before the instruction to
832   *         continue expansion.
833   */
834  private static Instruction generateBranchingTypeCheck(Instruction s, IR ir, Operand RHSobj,
835                                                            TypeReference LHStype, Operand RHStib,
836                                                            BasicBlock trueBlock, BasicBlock falseBlock,
837                                                            RegisterOperand oldGuard,
838                                                            BranchProfileOperand falseProb) {
839    Instruction continueAt = Goto.create(GOTO, trueBlock.makeJumpTarget());
840    continueAt.copyPosition(s);
841    s.insertBefore(continueAt);
842    s.remove();
843
844    if (LHStype.isClassType()) {
845      RVMClass LHSclass = (RVMClass) LHStype.peekType();
846      if (LHSclass != null && LHSclass.isResolved()) {
847        // Cases 4, 5, and 6 of DynamicTypeCheck: LHSclass is a resolved
848        // class or interface
849        if (LHSclass.isInterface()) {
850          // A resolved interface (case 4)
851          int interfaceIndex = LHSclass.getDoesImplementIndex();
852          int interfaceMask = LHSclass.getDoesImplementBitMask();
853          RegisterOperand doesImpl =
854              InsertUnary(continueAt, ir, GET_DOES_IMPLEMENT_FROM_TIB, TypeReference.IntArray, RHStib);
855
856          if (DynamicTypeCheck.MIN_DOES_IMPLEMENT_SIZE <= interfaceIndex) {
857            RegisterOperand doesImplLength =
858                InsertGuardedUnary(continueAt, ir, ARRAYLENGTH, TypeReference.Int, doesImpl.copyD2U(), TG());
859            Instruction lengthCheck =
860                IfCmp.create(INT_IFCMP,
861                             oldGuard,
862                             doesImplLength,
863                             IC(interfaceIndex),
864                             ConditionOperand.LESS_EQUAL(),
865                             falseBlock.makeJumpTarget(),
866                             BranchProfileOperand.unlikely());
867            if (oldGuard != null) {
868              oldGuard = oldGuard.copyD2D();
869            }
870            continueAt.insertBefore(lengthCheck);
871            BasicBlock oldBlock = continueAt.getBasicBlock();
872            oldBlock.splitNodeWithLinksAt(lengthCheck, ir);
873            oldBlock.insertOut(falseBlock); // required due to splitNode!
874          }
875          RegisterOperand entry =
876              InsertLoadOffset(continueAt,
877                               ir,
878                               INT_LOAD,
879                               TypeReference.Int,
880                               doesImpl,
881                               Offset.fromIntZeroExtend(interfaceIndex << 2),
882                               new LocationOperand(TypeReference.Int),
883                               TG());
884          RegisterOperand bit =
885              insertBinary(continueAt, ir, INT_AND, TypeReference.Int, entry, IC(interfaceMask));
886          continueAt.insertBefore(IfCmp.create(INT_IFCMP,
887                                               oldGuard,
888                                               bit,
889                                               IC(0),
890                                               ConditionOperand.EQUAL(),
891                                               falseBlock.makeJumpTarget(),
892                                               falseProb));
893          return continueAt;
894        } else {
895          // A resolved class (cases 5 and 6 in DynamicTypeCheck)
896          if (LHSclass.isFinal()) {
897            // For a final class, we can do a PTR compare of
898            // rhsTIB and the TIB of the class
899            Operand classTIB = getTIB(continueAt, ir, LHSclass);
900            continueAt.insertBefore(IfCmp.create(REF_IFCMP,
901                                                 oldGuard,
902                                                 RHStib,
903                                                 classTIB,
904                                                 ConditionOperand.NOT_EQUAL(),
905                                                 falseBlock.makeJumpTarget(),
906                                                 falseProb));
907            return continueAt;
908          } else {
909            // Do the full blown case 5 or 6 typecheck.
910            int LHSDepth = LHSclass.getTypeDepth();
911            int LHSId = LHSclass.getId();
912            RegisterOperand superclassIds =
913                InsertUnary(continueAt, ir, GET_SUPERCLASS_IDS_FROM_TIB, TypeReference.ShortArray, RHStib);
914            if (DynamicTypeCheck.MIN_SUPERCLASS_IDS_SIZE <= LHSDepth) {
915              RegisterOperand superclassIdsLength =
916                  InsertGuardedUnary(continueAt, ir, ARRAYLENGTH, TypeReference.Int, superclassIds.copyD2U(), TG());
917              Instruction lengthCheck =
918                  IfCmp.create(INT_IFCMP,
919                               oldGuard,
920                               superclassIdsLength,
921                               IC(LHSDepth),
922                               ConditionOperand.LESS(),
923                               falseBlock.makeJumpTarget(),
924                               BranchProfileOperand.unlikely());
925              if (oldGuard != null) {
926                oldGuard = oldGuard.copyD2D();
927              }
928              continueAt.insertBefore(lengthCheck);
929              BasicBlock oldBlock = continueAt.getBasicBlock();
930              oldBlock.splitNodeWithLinksAt(lengthCheck, ir);
931              oldBlock.insertOut(falseBlock); // required due to splitNode!
932            }
933            RegisterOperand refCandidate =
934                InsertLoadOffset(continueAt,
935                                 ir,
936                                 USHORT_LOAD,
937                                 TypeReference.Short,
938                                 superclassIds,
939                                 Offset.fromIntZeroExtend(LHSDepth << 1),
940                                 new LocationOperand(TypeReference.Short),
941                                 TG());
942            continueAt.insertBefore(IfCmp.create(INT_IFCMP,
943                                                 oldGuard,
944                                                 refCandidate,
945                                                 IC(LHSId),
946                                                 ConditionOperand.NOT_EQUAL(),
947                                                 falseBlock.makeJumpTarget(),
948                                                 falseProb));
949            return continueAt;
950          }
951        }
952      } else {
953        // A non-resolved class or interface. Case 3 of DynamicTypeCheck
954        // Branch on the result of a call to
955        // RuntimeEntrypoints.instance
956        RegisterOperand result = ir.regpool.makeTempInt();
957        RVMMethod target = Entrypoints.instanceOfMethod;
958        Instruction call =
959            Call.create2(CALL,
960                         result,
961                         AC(target.getOffset()),
962                         MethodOperand.STATIC(target),
963                         RHSobj,
964                         IC(LHStype.getId()));
965        call.copyPosition(continueAt);
966        continueAt.insertBefore(call);
967        call = callHelper(call, ir);
968        continueAt.insertBefore(IfCmp.create(INT_IFCMP,
969                                             oldGuard,
970                                             result.copyD2U(),
971                                             IC(0),
972                                             ConditionOperand.EQUAL(),
973                                             falseBlock.makeJumpTarget(),
974                                             falseProb));
975        return continueAt;
976      }
977    }
978
979    if (LHStype.isArrayType()) {
980      // Case 2 of DynamicTypeCheck: LHS is an array.
981      RVMArray LHSArray = (RVMArray) LHStype.peekType();
982      if (LHSArray != null) {
983        Operand classTIB = getTIB(continueAt, ir, LHSArray);
984        RVMType innermostElementType = LHSArray.getInnermostElementType();
985        if (innermostElementType.isPrimitiveType() || innermostElementType.isUnboxedType() ||
986            (innermostElementType.asClass().isResolved() && innermostElementType.asClass().isFinal())) {
987          // [^k of primitive or [^k of final class. Just like final classes,
988          // a PTR compare of rhsTIB and the TIB of the class gives the answer.
989          continueAt.insertBefore(IfCmp.create(REF_IFCMP,
990                                               oldGuard,
991                                               RHStib,
992                                               classTIB,
993                                               ConditionOperand.NOT_EQUAL(),
994                                               falseBlock.makeJumpTarget(),
995                                               falseProb));
996          return continueAt;
997        }
998        // TODO: branch probability calculation is somewhat bogus for this case.
999        Instruction shortcircuit =
1000            IfCmp.create(REF_IFCMP,
1001                         oldGuard,
1002                         RHStib,
1003                         classTIB,
1004                         ConditionOperand.EQUAL(),
1005                         trueBlock.makeJumpTarget(),
1006                         new BranchProfileOperand());
1007        if (oldGuard != null) {
1008          oldGuard = oldGuard.copyD2D();
1009        }
1010        continueAt.insertBefore(shortcircuit);
1011        BasicBlock myBlock = shortcircuit.getBasicBlock();
1012        BasicBlock mainBlock = myBlock.splitNodeWithLinksAt(shortcircuit, ir);
1013        myBlock.insertOut(trueBlock);       // must come after the splitNodeAt
1014        RegisterOperand rhsType =
1015            InsertUnary(continueAt, ir, GET_TYPE_FROM_TIB, TypeReference.Type, RHStib.copy());
1016        if (innermostElementType.isJavaLangObjectType()) {
1017          IntConstantOperand lhsDimension = IC(LHStype.getDimensionality());
1018          RegisterOperand rhsDimension = getField(continueAt, ir, rhsType, Entrypoints.dimensionField);
1019          Instruction dimTest =
1020              IfCmp2.create(INT_IFCMP2,
1021                            oldGuard,
1022                            rhsDimension,
1023                            lhsDimension,
1024                            ConditionOperand.GREATER(),
1025                            trueBlock.makeJumpTarget(),
1026                            ((BranchProfileOperand) falseProb.copy()).flip(),
1027                            ConditionOperand.LESS(),
1028                            falseBlock.makeJumpTarget(),
1029                            (BranchProfileOperand) falseProb.copy());
1030          if (oldGuard != null) {
1031            oldGuard = oldGuard.copyD2D();
1032          }
1033          continueAt.insertBefore(dimTest);
1034          //BasicBlock testBlock =
1035          mainBlock.splitNodeWithLinksAt(dimTest, ir);
1036          mainBlock.insertOut(trueBlock);
1037          mainBlock.insertOut(falseBlock);
1038          RegisterOperand rhsInnermostElementTypeDimension =
1039              getField(continueAt, ir, rhsType.copyU2U(), Entrypoints.innermostElementTypeDimensionField);
1040          continueAt.insertBefore(IfCmp.create(INT_IFCMP,
1041                                               oldGuard,
1042                                               rhsInnermostElementTypeDimension,
1043                                               IC(0),
1044                                               ConditionOperand.NOT_EQUAL(),
1045                                               falseBlock.makeJumpTarget(),
1046                                               falseProb));
1047          return continueAt;
1048        }
1049      }
1050
1051      // Not a case we want to handle inline
1052      RVMMethod target = Entrypoints.instanceOfMethod;
1053      RegisterOperand callResult = ir.regpool.makeTempInt();
1054      Instruction call =
1055          Call.create2(CALL,
1056                       callResult,
1057                       AC(target.getOffset()),
1058                       MethodOperand.STATIC(target),
1059                       RHSobj,
1060                       IC(LHStype.getId()));
1061      call.copyPosition(continueAt);
1062      continueAt.insertBefore(call);
1063      call = callHelper(call, ir);
1064      continueAt.insertBefore(IfCmp.create(INT_IFCMP,
1065                                           oldGuard,
1066                                           callResult.copyD2U(),
1067                                           IC(0),
1068                                           ConditionOperand.EQUAL(),
1069                                           falseBlock.makeJumpTarget(),
1070                                           falseProb));
1071      return continueAt;
1072    }
1073    OptimizingCompilerException.UNREACHABLE();
1074    return null;
1075  }
1076
1077  // helper routine.
1078  // s is a conditional branch; Make it the last instruction in its block
1079  // if it isn't already and return the fallthrough block.
1080  private static BasicBlock fallThroughBB(Instruction s, IR ir) {
1081    Instruction next = s.nextInstructionInCodeOrder();
1082    if (next.operator() == BBEND) {
1083      return next.getBasicBlock().nextBasicBlockInCodeOrder();
1084    } else if (next.operator() == GOTO) {
1085      BasicBlock target = next.getBranchTarget();
1086      next.remove();
1087      return target;
1088    } else {
1089      BasicBlock myBlock = s.getBasicBlock();
1090      BasicBlock succBlock = myBlock.splitNodeAt(s, ir);
1091      myBlock.insertOut(succBlock);
1092      ir.cfg.linkInCodeOrder(myBlock, succBlock);
1093      return succBlock;
1094    }
1095  }
1096
1097  private static BasicBlock advanceBlock(int bcIndex, BasicBlock curBlock, IR ir) {
1098    BasicBlock newBlock = curBlock.createSubBlock(bcIndex, ir);
1099    curBlock.insertOut(newBlock);
1100    ir.cfg.linkInCodeOrder(curBlock, newBlock);
1101    return newBlock;
1102  }
1103
1104}