report("6 while loop? ("+blocks+")\n"); return;}
report("6 while loop? ("+blocks+")\n"); return true;}
  static void unrollLeaf (OPT_LSTNode t, OPT_IR ir) {    int instructionsInLoop = 0;    OPT_BasicBlock exitBlock = null, succBlock = null, predBlock = null;    OPT_BitVector nloop = t.loop;    OPT_BasicBlock header = t.header;    OPT_Instruction tmp;        if (nloop == null) return;    // examine what we got...    report ("Leaf loop in " + ir.method + ": "+nloop+"\n");    if (ir.hasReachableExceptionHandlers()){      report ("0 IR may have exception handlers\n"); return;}    // determine loop structure by looking at its blocks    OPT_BasicBlockEnumeration loopBlocks = ir.getBasicBlocks(nloop);    int blocks = 0;    while (loopBlocks.hasMoreElements()) {      OPT_BasicBlock b = loopBlocks.next();      blocks++;      // check for size      instructionsInLoop += b.getNumberOfRealInstructions();      if (instructionsInLoop > MaxInstructions) {	report ("1 is too big\n"); return;}      // look at the in edges. We want the header to be the only      // block with out of loop incoming edges.      OPT_BasicBlockEnumeration e = b.getIn();      if (b != header) {	while (e.hasMoreElements()) {	  OPT_BasicBlock o = e.next();	  if (!nloop.get(o.getNumber())) {	    report ("2 interior pointers.\n"); return;}	}      } else {	// check the headers predecessors: there should be	// one out of loop input and one backedge.	// We can extend this for loops with several backedges,	// if they all have the same conditions.	int inEdges = 0;	while (e.hasMoreElements()) {	  inEdges++;	  OPT_BasicBlock o = e.next();	  if (!nloop.get(o.getNumber())) {	    if (predBlock == null) predBlock = o;	    else {report ("3 multi entry header.\n"); return;}	  } else {	    if (exitBlock == null) exitBlock = o;	    else {report ("4 multiple back edges.\n"); return;}	  }	}      }          }    // exitBlock must exit    while (exitBlock.getNumberOfOut() == 1 && exitBlock.getNumberOfIn() == 1)      exitBlock = exitBlock.getIn().next();      OPT_BasicBlockEnumeration e = exitBlock.getOut();    boolean exits = false;    while (e.hasMoreElements()) {      OPT_BasicBlock b = e.next();      if (!nloop.get(b.getNumber())) {exits = true; break;}    }    if (!exits) {report ("5 exitBlock doesn't exit\n"); return;}    if (exitBlock == header && blocks > 1) {      report("6 while loop? ("+blocks+")\n"); return;}    // So far, so good. Examine the exit test.    OPT_Instruction origBranch = exitBlock.firstBranchInstruction();    if (origBranch != exitBlock.lastRealInstruction()) {      OPT_Instruction aGoto = origBranch.nextInstructionInCodeOrder();      if (aGoto.operator.opcode != GOTO_opcode) {	report ("7 too complex exit\n"); return;}      succBlock = Label.getBlock(Goto.getTarget(aGoto).target).block;      if (VM.VerifyAssertions)	VM.assert (aGoto == exitBlock.lastRealInstruction());    } else {      succBlock = exitBlock.getFallThroughBlock();    }        if (origBranch.operator.opcode != INT_IFCMP_opcode) {      report("8 branch isn't int_ifcmp: "+origBranch.operator+".\n"); return;}    // examine operands:    OPT_Operand op1 = follow(IfCmp.getVal1(origBranch));    OPT_Operand op2 = follow(IfCmp.getVal2(origBranch));    OPT_ConditionOperand      cond = (OPT_ConditionOperand)IfCmp.getCond(origBranch).copy();    OPT_RegisterOperand ifcmpGuard = IfCmp.getGuardResult(origBranch);    double backBranchProbability      = IfCmp.getBranchProfile (origBranch).takenProbability;    if (!loopInvariant (op2, nloop)) {      if (loopInvariant (op1, nloop)) {	OPT_Operand op = op1;	op1 = op2;	op2 = op;	cond.flipOperands();      } else {	report ("8a op1 and op2 may not be loop invariant\n"); return;}    }    OPT_BasicBlock      target = Label.getBlock(IfCmp.getTarget(origBranch).target).block;    if (!(op1 instanceof OPT_RegisterOperand)) {      report ("9 op1 of ifcmp isn't a register\n"); return;}    OPT_RegisterOperand rop1 = (OPT_RegisterOperand) op1;    OPT_Register reg = rop1.register;    if (reg.isPhysical()) {report("10 loops over physical register\n"); return;}    if (succBlock == header && !nloop.get(target.getNumber())) {      succBlock = target;      target = header;      cond.flipCode();    }    if (target != header) {report ("11 ifcmp doesn't jump to header\n");return;}    OPT_Instruction iterator = null;    OPT_OperandEnumeration defs = new RealDefs (rop1);    while (defs.hasMoreElements()) {      OPT_Operand def = defs.next();      OPT_Instruction inst = def.instruction;      OPT_BasicBlock block = inst.getBasicBlock();      //VM.sysWrite (""+block+": "+inst+"\n");       if (nloop.get(block.getNumber())) {	if (iterator == null) {	  iterator = inst;	} else {report("12 iterator not unique.\n"); return;}      }    }        if (iterator == null) {report ("15 iterator not found.\n"); return;}          if (iterator.operator.opcode != INT_ADD_opcode) {      report ("16 iterator is no addition: "+iterator.operator+"\n"); return;}    if (!rop1.similar(follow(Binary.getVal1(iterator)))) {      //dumpIR (ir, "malformed");      report ("17 malformed iterator.\n"+iterator+"\n"); return;}    OPT_Operand strideOp = follow (Binary.getVal2(iterator));    if (!(strideOp instanceof OPT_IntConstantOperand)) {      report ("18 stride not constant\n"); return;}    int stride = ((OPT_IntConstantOperand)strideOp).value;    if (stride != 1	&& stride != -1	) {      report ("18b stride != +/-1 ("+stride+")\n"); return;}    if ((   stride ==  1	    && ((  cond.value != OPT_ConditionOperand.LESS)		&& cond.value != OPT_ConditionOperand.LESS_EQUAL		&& cond.value != OPT_ConditionOperand.NOT_EQUAL		))	|| (stride == -1	    && ((  cond.value != OPT_ConditionOperand.GREATER)		&& cond.value != OPT_ConditionOperand.GREATER_EQUAL		&& cond.value != OPT_ConditionOperand.NOT_EQUAL		))) {      report ("19 unexpected condition: "+cond+"\n"+iterator+"\n\n"); return;}    OPT_RegisterOperand outerGuard;    OPT_BasicBlock outer = predBlock;    while (outer.getNumberOfOut() == 1 && outer.getNumberOfIn() >= 1) {      if (outer.getNumberOfIn() == 0) break;      outer = outer.getIn().next();    }    if (outer.getNumberOfIn() > 0 && outer.getNumberOfOut() < 2) {      report ("23 no suitable outer guard found.\n"); return;}    tmp = outer.firstBranchInstruction();    if (tmp != null && GuardResultCarrier.conforms(tmp))      outerGuard = GuardResultCarrier.getGuardResult(tmp);    else {      outerGuard = ir.regpool.makeTempValidation();    }    ////////////    // transfom    // transform this:    //    // Orig:    //  B    //  if i CC b goto Orig    //  else goto exit    //    // exit:    //    // into this:    //////  stride == 1:           common:                      stride == -1://--------------------------------------------------------------------------//                          guard0://                           limit = b;//   if a > b goto Orig                                  if b > a goto Orig//                           else guard1                             //    // //                          guard 1:                             //   remainder = b - a;                                  remainder = a - b;// if cond == '<='                                    if cond == '>='//   remainder++;                                         remainder++;//                           remainder = remainder & 3                     //   limit = a + remainder                               limit = a - remainder// if cond == '<='                                    if cond == '>='//   limit--;                                            limit++;//                           if remainder == 0 goto mllp //                           goto Orig //                                                                     //                          Orig:                                //                           LOOP;                              //                           if i CC limit goto Orig //                           else guard2  //                                                //                          guard2: if i CC b goto mllp //                           else exit//                      //                           mllp: // landing pad//                           goto ml//                //                          ml:                                  //                           LOOP;LOOP;LOOP;LOOP;                             //                           if i CC b goto ml //                           else exit//                                                      //                          exit://--------------------------------------------------------------------------    theCnt++;    //if (theCnt > 0) return;    report ("...transforming.\n");    if (ir.options.hasMETHOD_TO_PRINT()	&& ir.options.fuzzyMatchMETHOD_TO_PRINT(ir.method.toString()))  {      //{report ("canceled\n"); return; }      // dumpIR(ir, "before unroll");    }            OPT_CFGTransformations.killFallThroughs (ir, nloop);    OPT_BasicBlock handles[] = makeSomeCopies(unrollFactor, ir, nloop, blocks,					      header, exitBlock, exitBlock);    OPT_BasicBlock mainHeader = handles[0];    OPT_BasicBlock mainExit = handles[1];    // test block for well formed bounds    OPT_BasicBlock guardBlock0      = header.createSubBlock(header.firstInstruction().bcIndex, ir);    predBlock.redirectOuts (header, guardBlock0, ir);          // test block for iteration alignemnt    OPT_BasicBlock guardBlock1      = header.createSubBlock(header.firstInstruction().bcIndex, ir);    OPT_BasicBlock predSucc = predBlock.nextBasicBlockInCodeOrder();    if (predSucc != null) {      ir.cfg.breakCodeOrder(predBlock, predSucc);      ir.cfg.linkInCodeOrder(guardBlock1, predSucc);    }    ir.cfg.linkInCodeOrder(predBlock, guardBlock0);    ir.cfg.linkInCodeOrder(guardBlock0, guardBlock1);        // guard block for main loop    OPT_BasicBlock guardBlock2      = header.createSubBlock(header.firstInstruction().bcIndex, ir);    // landing pad for main loop    OPT_BasicBlock landingPad      = header.createSubBlock(header.firstInstruction().bcIndex, ir);        OPT_BasicBlock mainLoop = exitBlock.nextBasicBlockInCodeOrder();    ir.cfg.breakCodeOrder (exitBlock,   mainLoop);    ir.cfg.linkInCodeOrder(exitBlock,   guardBlock2);    ir.cfg.linkInCodeOrder(guardBlock2, landingPad);    ir.cfg.linkInCodeOrder(landingPad,  mainLoop);        OPT_RegisterOperand remainder  =  ir.regpool.makeTemp(rop1.type);    OPT_RegisterOperand limit =  ir.regpool.makeTemp(rop1.type);    // test whether a <= b for stride == 1 and a >= b for stride == -1    tmp = guardBlock0.lastInstruction();    tmp.insertBefore (Move.create (INT_MOVE, limit, op2.copy()));    OPT_ConditionOperand g0cond = OPT_ConditionOperand.GREATER();    if   (stride == -1)  g0cond = OPT_ConditionOperand.LESS();        tmp.insertBefore      (IfCmp.create(INT_IFCMP, outerGuard.copyD2D(), rop1.copyD2U(),		    op2.copy(), g0cond, header.makeJumpTarget(),		    OPT_BranchProfileOperand.unlikely()));    tmp.insertBefore(Goto.create(GOTO, guardBlock1.makeJumpTarget()));          // jump over the original loop, if numbers of iteration is already aligned    tmp = guardBlock1.lastInstruction();    if (stride == 1)       tmp.insertBefore	(Binary.create(INT_SUB, remainder, op2.copy(), rop1.copyD2U()));    else       tmp.insertBefore	(Binary.create(INT_SUB, remainder, rop1.copyD2U(), op2.copy()));    if (cond.isGREATER_EQUAL() || cond.isLESS_EQUAL())       tmp.insertBefore	(Binary.create(INT_ADD, remainder.copyD2D(), remainder.copyD2U(),		       new OPT_IntConstantOperand(1)));        tmp.insertBefore      (Binary.create(INT_AND, remainder.copyD2D(), remainder.copyD2U(),		     new OPT_IntConstantOperand(unrollFactor-1)));    if (stride == 1)      tmp.insertBefore	(Binary.create(INT_ADD, limit.copyD2U(), op1.copy(),		       remainder.copyD2U()));     else      tmp.insertBefore	(Binary.create(INT_SUB, limit.copyD2U(), op1.copy(),		       remainder.copyD2U()));        if (cond.isLESS_EQUAL())       tmp.insertBefore	(Binary.create(INT_ADD, limit.copyD2D(), limit.copyD2U(),		       new OPT_IntConstantOperand(-1)));        if (cond.isGREATER_EQUAL())       tmp.insertBefore	(Binary.create(INT_ADD, limit.copyD2D(), limit.copyD2U(),		       new OPT_IntConstantOperand(1)));        tmp.insertBefore      (IfCmp.create(INT_IFCMP, outerGuard.copyD2D(), remainder.copyD2U(),		    new OPT_IntConstantOperand(0),		    OPT_ConditionOperand.EQUAL(),		    landingPad.makeJumpTarget(),		    new OPT_BranchProfileOperand(1.0/unrollFactor)));    tmp.insertBefore(Goto.create(GOTO,header.makeJumpTarget()));    // change the back branch in the original loop    deleteBranches (exitBlock);    tmp = exitBlock.lastInstruction();    tmp.insertBefore       (IfCmp.create (INT_IFCMP, outerGuard.copyD2D(),		     rop1.copyU2U(), limit.copyD2U(),		     (OPT_ConditionOperand) cond.copy(),		     header.makeJumpTarget(),		     new OPT_BranchProfileOperand(1.0 - 1.0 / unrollFactor)));    tmp.insertBefore      (Goto.create(GOTO,guardBlock2.makeJumpTarget()));    // jump over main loop if no iterations left    tmp = guardBlock2.lastInstruction();    tmp.insertBefore      (IfCmp.create (INT_IFCMP, outerGuard.copyD2D(),		     rop1.copyU2U(), op2.copy(),		     (OPT_ConditionOperand) cond.copy(),		     landingPad.makeJumpTarget(),		     new OPT_BranchProfileOperand(1.0-backBranchProbability)));    tmp.insertBefore (Goto.create (GOTO, succBlock.makeJumpTarget()));    // landing pad jumps to mainHeader    tmp = landingPad.lastInstruction();    tmp.insertBefore (Goto.create(GOTO, mainHeader.makeJumpTarget()));        // repair back edge in mainExit    if (VM.VerifyAssertions) VM.assert (mainExit != null);    tmp = mainExit.lastInstruction();    if (VM.VerifyAssertions)      VM.assert ((   mainExit.lastRealInstruction() == null)		 || !mainExit.lastRealInstruction().isBranch());    tmp.insertBefore      (IfCmp.create (INT_IFCMP, ifcmpGuard.copyU2U(),		     rop1.copyU2U(), op2.copy(),		     (OPT_ConditionOperand) cond.copy(),		     mainHeader.makeJumpTarget(),		     new OPT_BranchProfileOperand(1.0						  - (1.0-backBranchProbability)						  * unrollFactor)));    tmp.insertBefore    (Goto.create (GOTO, succBlock.makeJumpTarget()));    // recompute normal outs    guardBlock0.recomputeNormalOut(ir);    guardBlock1.recomputeNormalOut(ir);    guardBlock2.recomputeNormalOut(ir);    exitBlock.recomputeNormalOut(ir);    landingPad.recomputeNormalOut(ir);    mainExit.recomputeNormalOut(ir);    if (ir.options.hasMETHOD_TO_PRINT()	&& ir.options.fuzzyMatchMETHOD_TO_PRINT(ir.method.toString())) {      // dumpIR(ir, "after unroll");    }  }  static void report (String s) {    if (DEBUG) VM.sysWrite ("] "+s);  }  private static int theVisit = 1;  private static OPT_Operand follow (OPT_Operand use) {    theVisit++; return _follow(use);}