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 java.util.Enumeration;
016 import java.util.HashSet;
017 import java.util.NoSuchElementException;
018
019 import org.jikesrvm.VM;
020 import org.jikesrvm.classloader.BytecodeStream;
021 import org.jikesrvm.classloader.ExceptionHandlerMap;
022 import org.jikesrvm.classloader.TypeReference;
023 import org.jikesrvm.compilers.opt.OperationNotImplementedException;
024 import org.jikesrvm.compilers.opt.ir.BasicBlock;
025 import org.jikesrvm.compilers.opt.ir.ExceptionHandlerBasicBlock;
026 import org.jikesrvm.compilers.opt.ir.ExceptionHandlerBasicBlockBag;
027 import org.jikesrvm.compilers.opt.ir.IRTools;
028 import org.jikesrvm.compilers.opt.ir.Instruction;
029 import org.jikesrvm.compilers.opt.ir.Move;
030 import org.jikesrvm.compilers.opt.ir.operand.Operand;
031 import org.jikesrvm.compilers.opt.ir.operand.RegisterOperand;
032 import org.jikesrvm.compilers.opt.ir.operand.TypeOperand;
033
034 /**
035 * A somewhat complex subtask of IR generation is to discover and maintain
036 * the set of basic blocks that are being generated.
037 * This class encapsulates that functionality.
038 * The backing data store is a red/black tree, but there are a number of
039 * very specialized operations that are performed during search/insertion
040 * so we roll our own instead of using one from the standard library.
041 */
042 final class BBSet implements IRGenOptions {
043 /** root of the backing red/black tree*/
044 private BasicBlockLE root;
045
046 /**
047 * is it the case that we can ignore JSR processing because
048 * BC2IR has not yet generated a JSR bytecode in this method?
049 */
050 private boolean noJSR = true;
051
052 /** entry block of the CFG */
053 private final BasicBlockLE entry;
054
055 /** associated generation context */
056 private final GenerationContext gc;
057
058 /** associated bytecodes */
059 private final BytecodeStream bcodes;
060
061 // Fields to support generation/identification of catch blocks
062 /** Start bytecode index for each exception handler ranges */
063 private int[] startPCs;
064
065 /** End bytecode index for each exception handler range */
066 private int[] endPCs;
067
068 /** Start bytecode index of each the exception handler */
069 private int[] handlerPCs;
070
071 /** Type of exception handled by each exception handler range. */
072 private TypeOperand[] exceptionTypes;
073
074 /**
075 * Initialize the BBSet to handle basic block generation for the argument
076 * generation context and bytecode info.
077 * @param gc the generation context to generate blocks for
078 * @param bcodes the bytecodes of said generation context
079 * @param localState the state of the local variables for the block
080 * beginning at bytecode 0.
081 */
082 BBSet(GenerationContext gc, BytecodeStream bcodes, Operand[] localState) {
083 this.gc = gc;
084 this.bcodes = bcodes;
085
086 // Set up internal data structures to deal with exception handlers
087 parseExceptionTables();
088
089 // Create the entry block, setting root as a sideffect.
090 entry = _createBBLE(0, null, null, false);
091 entry.setStackKnown();
092 entry.copyIntoLocalState(localState);
093 }
094
095 /** return the entry BBLE */
096 BasicBlockLE getEntry() { return entry; }
097
098 /**
099 * Notify the BBSet that BC2IR has encountered a JSR bytecode.
100 * This enables more complex logic in getOrCreateBlock to drive
101 * the basic block specialization that is the key to JSR inlining.
102 */
103 void seenJSR() { noJSR = false; }
104
105 /**
106 * Return a enumeration of the BasicBlockLE's currently in the BBSet.
107 */
108 Enumeration<BasicBlockLE> contents() {
109 return TreeEnumerator.enumFromRoot(root);
110 }
111
112 /**
113 * Gets the bytecode index of the block in the set which has the
114 * next-higher bytecode index.
115 * Returns bcodes.length() if x is currently the block with the highest
116 * starting bytecode index.
117 * @param x basic block to start at.
118 */
119 int getNextBlockBytecodeIndex(BasicBlockLE x) {
120 BasicBlockLE nextBBLE = getSuccessor(x, x.low);
121 return nextBBLE == null ? bcodes.length() : nextBBLE.low;
122 }
123
124 /**
125 * Finds the next ungenerated block, starting at the argument
126 * block and searching forward, wrapping around to the beginning.
127 * If all blocks are generated, it returns null.
128 * @param start the basic block at which to start looking.
129 */
130 BasicBlockLE getNextEmptyBlock(BasicBlockLE start) {
131 if (DBG_BBSET) db("getting the next empty block after " + start);
132
133 // Look for an ungenerated block after start.
134 BBSet.TreeEnumerator e = TreeEnumerator.enumFromNode(start);
135 while (e.hasMoreElements()) {
136 BasicBlockLE block = e.next();
137 if (DBG_BBSET) {
138 db("Considering block " + block + " " + block.genState());
139 }
140 if (block.isReadyToGenerate()) {
141 if (DBG_BBSET) db("block " + block + " is not yet generated");
142 return block;
143 }
144 }
145
146 // There were none. Start looking from the beginning.
147 if (DBG_BBSET) db("at end of bytecodes, restarting at beginning");
148 e = TreeEnumerator.enumFromRoot(root);
149 while (true) {
150 BasicBlockLE block = e.next();
151 if (block == start) {
152 if (DBG_BBSET) db("wrapped around, no more empty blocks");
153 return null;
154 }
155 if (DBG_BBSET) {
156 db("Considering block " + block + " " + block.genState());
157 }
158 if (block.isReadyToGenerate()) {
159 if (DBG_BBSET) db("block " + block + " is not yet generated");
160 return block;
161 }
162 }
163 }
164
165 /**
166 * Get or create a block at the specified target.
167 * If simStack is non-null, rectifies stack state with target stack state.
168 * If simLocals is non-null, rectifies local state with target local state.
169 * Any instructions needed to rectify stack/local state are appended to
170 * from.
171 *
172 * @param target target index
173 * @param from the block from which control is being transfered
174 * and to which rectification instructions are added.
175 * @param simStack stack state to rectify, or null
176 * @param simLocals local state to rectify, or null
177 */
178 BasicBlockLE getOrCreateBlock(int target, BasicBlockLE from, OperandStack simStack, Operand[] simLocals) {
179 if (DBG_BB || BC2IR.DBG_SELECTED) {
180 db("getting block " +
181 target +
182 ", match stack: " +
183 (simStack != null) +
184 " match locals: " +
185 (simLocals != null));
186 }
187 return getOrCreateBlock(root, true, target, from, simStack, simLocals);
188 }
189
190 /**
191 * Mark a previously generated block for regeneration.
192 * We define this method here so that in the future
193 * we can implement a more efficient getNextEmptyBlock that
194 * (1) avoids generating lots of blocks when a CFG predecessor has a
195 * pending regeneration and (2) avoids the scan through all blocks when
196 * there are no more blocks left to generate.
197 */
198 private void markBlockForRegeneration(BasicBlockLE p) {
199 if (DBG_REGEN) db("marking " + p + " for regeneration");
200 if (p.fallThrough != null && p.fallThrough instanceof InliningBlockLE) {
201 // if the fallthrough out edge of this block is an
202 // InlineMethodBasicBlock, then the inlined method must also be
203 // regenerated. In preparation for this, we must delete all out
204 // edges from the inlined method to the caller.
205 // (These arise from thrown/caught exceptions.)
206 InliningBlockLE imbb = (InliningBlockLE) p.fallThrough;
207 imbb.deleteAllOutEdges();
208 }
209 // discard any "real" instructions in the block
210 if (!p.block.isEmpty()) {
211 p.block.discardInstructions();
212 }
213 p.setSelfRegen();
214 p.clearGenerated();
215 p.fallThrough = null;
216 // If p had a non-empty stack on entry, we need to go through it
217 // and copy all of its operands (they may point to instructions
218 // we just blew away, but then again they may not (may not be in p),
219 // so we can't simply null out the instruction field);
220 if (p.stackState != null) {
221 int i = p.stackState.getSize();
222 while (i-- > 0) {
223 Operand op = p.stackState.getFromTop(i);
224 p.stackState.replaceFromTop(i, op.copy());
225 }
226 }
227 }
228
229 /**
230 * Rectify the given stack state with the state contained in the given
231 * BBLE, adding the necessary move instructions to the end of the given
232 * basic block to make register numbers agree and rectify mis-matched constants.
233 * <p>
234 * @param block basic block to append move instructions to
235 * @param stack stack to copy
236 * @param p BBLE to copy stack state into
237 */
238 void rectifyStacks(BasicBlock block, OperandStack stack, BasicBlockLE p) {
239 if (stack == null || stack.isEmpty()) {
240 if (VM.VerifyAssertions) VM._assert(p.stackState == null);
241 if (!p.isStackKnown()) {
242 p.setStackKnown();
243 }
244 if (DBG_STACK || BC2IR.DBG_SELECTED) {
245 db("Rectified empty expression stack into " + p + "(" + p.block + ")");
246 }
247 return;
248 }
249 boolean generated = p.isGenerated();
250 // (1) Rectify the stacks.
251 if (!p.isStackKnown()) {
252 // First time we reached p. Thus, its expression stack
253 // is implicitly top and the meet degenerates to a copy operation
254 // with possibly some register renaming.
255 // (We need to ensure that non-local registers appear at
256 // most once on each expression stack).
257 if (DBG_STACK || BC2IR.DBG_SELECTED) {
258 db("First stack rectifiction for " + p + "(" + p.block + ") simply saving");
259 }
260 if (VM.VerifyAssertions) VM._assert(p.stackState == null);
261 p.stackState = new OperandStack(stack.getCapacity());
262 for (int i = stack.getSize() - 1; i >= 0; i--) {
263 Operand op = stack.getFromTop(i);
264 if (op == BC2IR.DUMMY) {
265 p.stackState.push(BC2IR.DUMMY);
266 } else if (op instanceof RegisterOperand) {
267 RegisterOperand rop = op.asRegister();
268 if (rop.getRegister().isLocal()) {
269 RegisterOperand temp = gc.temps.makeTemp(rop);
270 temp.setInheritableFlags(rop);
271 BC2IR.setGuard(temp, BC2IR.getGuard(rop));
272 Instruction move = Move.create(IRTools.getMoveOp(rop.getType()), temp, rop.copyRO());
273 move.bcIndex = BC2IR.RECTIFY_BCI;
274 move.position = gc.inlineSequence;
275 block.appendInstructionRespectingTerminalBranch(move);
276 p.stackState.push(temp.copy());
277 if (DBG_STACK || BC2IR.DBG_SELECTED) {
278 db("Inserted " + move + " into " + block + " to rename local");
279 }
280 } else {
281 p.stackState.push(rop.copy());
282 }
283 } else {
284 p.stackState.push(op.copy());
285 }
286 }
287 p.setStackKnown();
288 } else {
289 // A real rectification.
290 // We need to update mergedStack such that
291 // mergedStack[i] = meet(mergedStack[i], stack[i]).
292 if (DBG_STACK || BC2IR.DBG_SELECTED) db("rectifying stacks");
293 try {
294 if (VM.VerifyAssertions) {
295 VM._assert(stack.getSize() == p.stackState.getSize());
296 }
297 } catch (NullPointerException e) {
298 System.err.println("stack size " + stack.getSize());
299 System.err.println(stack);
300 System.err.println(p.stackState);
301 System.err.println(gc.method.toString());
302 block.printExtended();
303 p.block.printExtended();
304 throw e;
305 }
306 for (int i = 0; i < stack.getSize(); ++i) {
307 Operand sop = stack.getFromTop(i);
308 Operand mop = p.stackState.getFromTop(i);
309 if ((sop == BC2IR.DUMMY) || (sop instanceof ReturnAddressOperand)) {
310 if (VM.VerifyAssertions) VM._assert(mop.similar(sop));
311 continue;
312 } else if (sop.isConstant() || mop.isConstant()) {
313 if (mop.similar(sop)) {
314 continue; // constants are similar; so we don't have to do anything.
315 }
316 // sigh. Non-similar constants.
317 if (mop.isConstant()) {
318 // Insert move instructions in all predecessor
319 // blocks except 'block' to move mop into a register.
320 RegisterOperand mopTmp = gc.temps.makeTemp(mop);
321 if (DBG_STACK || BC2IR.DBG_SELECTED) db("Merged stack has constant operand " + mop);
322 for (Enumeration<BasicBlock> preds = p.block.getIn(); preds.hasMoreElements();) {
323 BasicBlock pred = preds.nextElement();
324 if (pred == block) continue;
325 injectMove(pred, mopTmp.copyRO(), mop.copy());
326 }
327 p.stackState.replaceFromTop(i, mopTmp.copy());
328 if (generated) {
329 if (DBG_STACK || BC2IR.DBG_SELECTED) {
330 db("\t...forced to regenerate " + p + " (" + p.block + ") because of this");
331 }
332 markBlockForRegeneration(p);
333 generated = false;
334 p.block.deleteOut();
335 if (DBG_CFG || BC2IR.DBG_SELECTED) db("Deleted all out edges of " + p.block);
336 }
337 mop = mopTmp;
338 }
339 if (sop.isConstant()) {
340 // Insert move instruction into block.
341 RegisterOperand sopTmp = gc.temps.makeTemp(sop);
342 if (DBG_STACK || BC2IR.DBG_SELECTED) db("incoming stack has constant operand " + sop);
343 injectMove(block, sopTmp, sop);
344 sop = sopTmp.copyRO();
345 }
346 }
347
348 // sop and mop are RegisterOperands (either originally or because
349 // we forced them to be above due to incompatible constants.
350 RegisterOperand rsop = sop.asRegister();
351 RegisterOperand rmop = mop.asRegister();
352 if (rmop.getRegister() != rsop.getRegister()) {
353 // must insert move at end of block to get register #s to match
354 RegisterOperand temp = rsop.copyRO();
355 temp.setRegister(rmop.getRegister());
356 injectMove(block, temp, rsop.copyRO());
357 }
358 Operand meet = Operand.meet(rmop, rsop, rmop.getRegister());
359 if (DBG_STACK || BC2IR.DBG_SELECTED) db("Meet of " + rmop + " and " + rsop + " is " + meet);
360 if (meet != rmop) {
361 if (generated) {
362 if (DBG_STACK || BC2IR.DBG_SELECTED) {
363 db("\t...forced to regenerate " + p + " (" + p.block + ") because of this");
364 }
365 markBlockForRegeneration(p);
366 generated = false;
367 p.block.deleteOut();
368 if (DBG_CFG || BC2IR.DBG_SELECTED) db("Deleted all out edges of " + p.block);
369 }
370 p.stackState.replaceFromTop(i, meet);
371 }
372 }
373 }
374 }
375
376 private void injectMove(BasicBlock block, RegisterOperand res, Operand val) {
377 Instruction move = Move.create(IRTools.getMoveOp(res.getType()), res, val);
378 move.bcIndex = BC2IR.RECTIFY_BCI;
379 move.position = gc.inlineSequence;
380 block.appendInstructionRespectingTerminalBranch(move);
381 if (DBG_STACK || BC2IR.DBG_SELECTED) {
382 db("Inserted " + move + " into " + block);
383 }
384 }
385
386 /**
387 * Rectify the given local variable state with the local variable state
388 * stored in the given BBLE.
389 *
390 * @param localState local variable state to rectify
391 * @param p target BBLE to rectify state to
392 */
393 void rectifyLocals(Operand[] localState, BasicBlockLE p) {
394 if (!p.isLocalKnown()) {
395 if (DBG_LOCAL || BC2IR.DBG_SELECTED) {
396 db("rectifying with heretofore unknown locals, changing to save");
397 }
398 p.copyIntoLocalState(localState);
399 return;
400 }
401 if (DBG_LOCAL || BC2IR.DBG_SELECTED) db("rectifying current local state with " + p);
402 boolean generated = p.isGenerated();
403 Operand[] incomingState = localState;
404 Operand[] presentState = p.localState;
405 if (VM.VerifyAssertions) {
406 VM._assert(incomingState.length == presentState.length);
407 }
408 for (int i = 0, n = incomingState.length; i < n; ++i) {
409 Operand pOP = presentState[i];
410 Operand iOP = incomingState[i];
411 if (pOP == iOP) {
412 if (DBG_LOCAL || BC2IR.DBG_SELECTED) {
413 db("local states have the exact same operand " + pOP + " for local " + i);
414 }
415 } else {
416 boolean untyped = (pOP == null || pOP == BC2IR.DUMMY || pOP instanceof ReturnAddressOperand);
417 Operand mOP = Operand.meet(pOP, iOP, untyped ? null : gc.localReg(i, pOP.getType()));
418 if (DBG_LOCAL || BC2IR.DBG_SELECTED) db("Meet of " + pOP + " and " + iOP + " is " + mOP);
419 if (mOP != pOP) {
420 if (generated) {
421 if (DBG_LOCAL || BC2IR.DBG_SELECTED) {
422 db("\t...forced to regenerate " + p + " (" + p.block + ") because of this");
423 }
424 markBlockForRegeneration(p);
425 generated = false;
426 p.block.deleteOut();
427 if (DBG_CFG || BC2IR.DBG_SELECTED) db("Deleted all out edges of " + p.block);
428 }
429 presentState[i] = mOP;
430 }
431 }
432 }
433 }
434
435 /**
436 * Do a final pass over the generated basic blocks to create
437 * the initial code ordering. All blocks generated for the method
438 * will be inserted after gc.prologue.<p>
439 *
440 * NOTE: Only some CFG edges are created here.....
441 * we're mainly just patching together a code linearization.
442 */
443 void finalPass(boolean inlinedSomething) {
444 BBSet.TreeEnumerator e = TreeEnumerator.enumFromRoot(root);
445 BasicBlock cop = gc.prologue;
446 BasicBlockLE curr = getEntry();
447 BasicBlockLE next = null;
448 top:
449 while (true) {
450 // Step 0: If curr is the first block in a catch block,
451 // inject synthetic entry block too.
452 if (curr instanceof HandlerBlockLE) {
453 // tell our caller that we actually put a handler in the final CFG.
454 gc.generatedExceptionHandlers = true;
455 HandlerBlockLE hcurr = (HandlerBlockLE) curr;
456 if (DBG_FLATTEN) {
457 db("injecting handler entry block " + hcurr.entryBlock + " before " + hcurr);
458 }
459 gc.cfg.insertAfterInCodeOrder(cop, hcurr.entryBlock);
460 cop = hcurr.entryBlock;
461 }
462 // Step 1: Insert curr in the code order (after cop, updating cop).
463 if (DBG_FLATTEN) db("flattening: " + curr + " (" + curr.block + ")");
464 curr.setInCodeOrder();
465 gc.cfg.insertAfterInCodeOrder(cop, curr.block);
466 cop = curr.block;
467 if (DBG_FLATTEN) {
468 db("Current Code order for " + gc.method + "\n");
469 for (BasicBlock bb = gc.prologue; bb != null; bb = (BasicBlock) bb.getNext()) {
470 VM.sysWrite(bb + "\n");
471 }
472 }
473 // Step 1.1 Sometimes (rarely) there will be an inscope
474 // exception handler that wasn't actually generated. If this happens,
475 // make a new, filtered EHBBB to avoid later confusion.
476 if (curr.handlers != null) {
477 int notGenerated = 0;
478 for (HandlerBlockLE handler : curr.handlers) {
479 if (!handler.isGenerated()) {
480 if (DBG_EX || DBG_FLATTEN) {
481 db("Will remove unreachable handler " + handler + " from " + curr);
482 }
483 notGenerated++;
484 }
485 }
486 if (notGenerated > 0) {
487 if (notGenerated == curr.handlers.length) {
488 if (DBG_EX || DBG_FLATTEN) {
489 db("No (local) handlers were actually reachable for " + curr + "; setting to caller");
490 }
491 curr.block.exceptionHandlers = curr.block.exceptionHandlers.getCaller();
492 } else {
493 ExceptionHandlerBasicBlock[] nlh =
494 new ExceptionHandlerBasicBlock[curr.handlers.length - notGenerated];
495 for (int i = 0, j = 0; i < curr.handlers.length; i++) {
496 if (curr.handlers[i].isGenerated()) {
497 nlh[j++] = curr.handlers[i].entryBlock;
498 } else {
499 if (VM.VerifyAssertions) {
500 VM._assert(curr.handlers[i].entryBlock.hasZeroIn(), "Non-generated handler with CFG edges");
501 }
502 }
503 }
504 curr.block.exceptionHandlers =
505 new ExceptionHandlerBasicBlockBag(nlh, curr.block.exceptionHandlers.getCaller());
506 }
507 }
508 }
509 // Step 2: Identify the next basic block to add to the code order.
510 // curr wants to fallthrough to an inlined method.
511 // Inject the entire inlined CFG in the code order.
512 // There's some fairly complicated coordination between this code,
513 // GenerationContext, and maybeInlineMethod. Sorry, but you'll
514 // have to take a close look at all of these to see how it
515 // all fits together....--dave
516 if (curr.fallThrough != null && curr.fallThrough instanceof InliningBlockLE) {
517 InliningBlockLE icurr = (InliningBlockLE) curr.fallThrough;
518 BasicBlock forw = cop.nextBasicBlockInCodeOrder();
519 BasicBlock calleeEntry = icurr.gc.cfg.firstInCodeOrder();
520 BasicBlock calleeExit = icurr.gc.cfg.lastInCodeOrder();
521 gc.cfg.breakCodeOrder(cop, forw);
522 gc.cfg.linkInCodeOrder(cop, icurr.gc.cfg.firstInCodeOrder());
523 gc.cfg.linkInCodeOrder(icurr.gc.cfg.lastInCodeOrder(), forw);
524 if (DBG_CFG || BC2IR.DBG_SELECTED) {
525 db("Added CFG edge from " + cop + " to " + calleeEntry);
526 }
527 if (icurr.epilogueBBLE != null) {
528 if (DBG_FLATTEN) {
529 db("injected " + icurr + " between " + curr + " and " + icurr.epilogueBBLE.fallThrough);
530 }
531 if (VM.VerifyAssertions) {
532 VM._assert(icurr.epilogueBBLE.block == icurr.gc.cfg.lastInCodeOrder());
533 }
534 curr = icurr.epilogueBBLE;
535 cop = curr.block;
536 } else {
537 if (DBG_FLATTEN) db("injected " + icurr + " after " + curr);
538 curr = icurr;
539 cop = calleeExit;
540 }
541 }
542 next = curr.fallThrough;
543 if (DBG_FLATTEN && next == null) {
544 db(curr + " has no fallthrough case, getting next block");
545 }
546 if (next != null) {
547 if (DBG_CFG || BC2IR.DBG_SELECTED) {
548 db("Added CFG edge from " + curr.block + " to " + next.block);
549 }
550 if (next.isInCodeOrder()) {
551 if (DBG_FLATTEN) {
552 db("fallthrough " + next + " is already flattened, adding goto");
553 }
554 curr.block.appendInstruction(next.block.makeGOTO());
555 // set next to null to indicate no "real" fall through
556 next = null;
557 }
558 }
559 if (next == null) {
560 // Can't process fallthroughblock, so get next BBLE from enumeration
561 while (true) {
562 if (!e.hasMoreElements()) {
563 // all done.
564 if (DBG_FLATTEN) db("no more blocks! all done");
565 break top;
566 }
567 next = e.next();
568 if (DBG_FLATTEN) db("looking at " + next);
569 if (!next.isGenerated()) {
570 if (DBG_FLATTEN) db("block " + next + " was not generated");
571 continue;
572 }
573 if (!next.isInCodeOrder()) {
574 break;
575 }
576 }
577 if (DBG_FLATTEN) db("found unflattened block: " + next);
578 }
579 curr = next;
580 }
581 // If the epilogue was unreachable, remove it from the code order and cfg
582 // and set gc.epilogue to null.
583 boolean removedSomethingFromCodeOrdering = inlinedSomething;
584 if (gc.epilogue.hasZeroIn()) {
585 if (DBG_FLATTEN || DBG_CFG) {
586 db("Deleting unreachable epilogue " + gc.epilogue);
587 }
588 gc.cfg.removeFromCodeOrder(gc.epilogue);
589 removedSomethingFromCodeOrdering = true;
590
591 // remove the node from the graph AND adjust its edge info
592 gc.epilogue.remove();
593 gc.epilogue.deleteIn();
594 gc.epilogue.deleteOut();
595 if (VM.VerifyAssertions) VM._assert(gc.epilogue.hasZeroOut());
596 gc.epilogue = null;
597 }
598 // if gc has an unlockAndRethrow block that was not used, then remove it
599 if (gc.unlockAndRethrow != null && gc.unlockAndRethrow.hasZeroIn()) {
600 gc.cfg.removeFromCFGAndCodeOrder(gc.unlockAndRethrow);
601 removedSomethingFromCodeOrdering = true;
602 gc.enclosingHandlers.remove(gc.unlockAndRethrow);
603 }
604 // if we removed a basic block then we should compact the node numbering
605 if (removedSomethingFromCodeOrdering) {
606 gc.cfg.compactNodeNumbering();
607 }
608
609 if (DBG_FLATTEN) {
610 db("Current Code order for " + gc.method + "\n");
611 for (BasicBlock bb = gc.prologue; bb != null; bb = (BasicBlock) bb.getNext()) {
612 bb.printExtended();
613 }
614 }
615 if (DBG_FLATTEN) {
616 db("Final CFG for " + gc.method + "\n");
617 gc.cfg.printDepthFirst();
618 }
619 }
620
621 //////////////////////////////////////////
622 // Gory implementation details of BBSet //
623 //////////////////////////////////////////
624
625 /**
626 * Print a debug string to the sysWrite stream.
627 * @param val string to print
628 */
629 private void db(String val) {
630 VM.sysWrite("IRGEN " + bcodes.getDeclaringClass() + "." + gc.method.getName() + ":" + val + "\n");
631 }
632
633 /**
634 * Initialize the global exception handler arrays for the method.<p>
635 */
636 private void parseExceptionTables() {
637 ExceptionHandlerMap eMap = gc.method.getExceptionHandlerMap();
638 if (DBG_EX) db("\texception handlers for " + gc.method + ": " + eMap);
639 if (eMap == null) return; // method has no exception handling ranges.
640 startPCs = eMap.getStartPC();
641 endPCs = eMap.getEndPC();
642 handlerPCs = eMap.getHandlerPC();
643 int numExceptionHandlers = startPCs.length;
644 exceptionTypes = new TypeOperand[numExceptionHandlers];
645 for (int i = 0; i < numExceptionHandlers; i++) {
646 exceptionTypes[i] = new TypeOperand(eMap.getExceptionType(i));
647 if (DBG_EX) db("\t\t[" + startPCs[i] + "," + endPCs[i] + "] " + eMap.getExceptionType(i));
648 }
649 }
650
651 /**
652 * Initialize bble's handlers array based on startPCs/endPCs.
653 * In the process, new HandlerBlockLE's may be created
654 * (by the call to getOrCreateBlock). <p>
655 * PRECONDITION: bble.low and bble.max have already been correctly
656 * set to reflect the invariant that a basic block is in exactly one
657 * "handler range."<p>
658 * Also initializes bble.block.exceptionHandlers.
659 */
660 private void initializeExceptionHandlers(BasicBlockLE bble, Operand[] simLocals) {
661 if (startPCs != null) {
662 HashSet<TypeReference> caughtTypes = new HashSet<TypeReference>();
663 for (int i = 0; i < startPCs.length; i++) {
664 TypeReference caughtType = exceptionTypes[i].getTypeRef();
665 if (bble.low >= startPCs[i] && bble.max <= endPCs[i] && !caughtTypes.contains(caughtType)) {
666 // bble's basic block is contained within this handler's range.
667 HandlerBlockLE eh = (HandlerBlockLE) getOrCreateBlock(handlerPCs[i], bble, null, simLocals);
668 if (DBG_EX) db("Adding handler " + eh + " to " + bble);
669 caughtTypes.add(caughtType);
670 bble.addHandler(eh);
671 }
672 }
673 }
674 if (bble.handlers != null) {
675 ExceptionHandlerBasicBlock[] ehbbs = new ExceptionHandlerBasicBlock[bble.handlers.length];
676 for (int i = 0; i < bble.handlers.length; i++) {
677 ehbbs[i] = bble.handlers[i].entryBlock;
678 }
679 bble.block.exceptionHandlers = new ExceptionHandlerBasicBlockBag(ehbbs, gc.enclosingHandlers);
680 } else {
681 bble.block.exceptionHandlers = gc.enclosingHandlers;
682 }
683 }
684
685 /**
686 * Given a starting bytecode index, find the greatest bcIndex that
687 * is still has the same inscope exception handlers.
688 * @param bcIndex the start bytecode index
689 */
690 private int exceptionEndRange(int bcIndex) {
691 int max = bcodes.length();
692 if (startPCs != null) {
693 for (int spc : startPCs) {
694 if (bcIndex < spc && max > spc) {
695 max = spc;
696 }
697 }
698 for (int epc : endPCs) {
699 if (bcIndex < epc && max > epc) {
700 max = epc;
701 }
702 }
703 }
704 return max;
705 }
706
707 /**
708 * We specialize basic blocks with respect to the return addresses
709 * they have on their expression stack and/or in their local variables
710 * on entry to the block. This has the effect of inlining the
711 * subroutine body at all of the JSR sites that invoke it.
712 * This is the key routine: it determines whether or not the
713 * argument simState (stack and locals) contains compatible
714 * return addresses as the candidate BasicBlockLE.
715 * <p>
716 * The main motivation for inlining away all JSR's is that it eliminates
717 * the "JSR problem" for type accurate GC. It is also simpler to
718 * implement and arguably results in more efficient generated code
719 * (assuming that we don't get horrific code bloat).
720 * To deal with the code bloat, we detect excessive code duplication and
721 * stop IR generation (bail out to the baseline compiler).
722 *
723 * @param simStack The expression stack to match
724 * @param simLocals The local variables to match
725 * @param candBBLE The candidate BaseicBlockLE
726 */
727 private boolean matchingJSRcontext(OperandStack simStack, Operand[] simLocals, BasicBlockLE candBBLE) {
728 if (DBG_INLINE_JSR) {
729 db("Matching JSR context of argument stack/locals against " + candBBLE);
730 }
731
732 int numRA = 0;
733 if (simStack != null && candBBLE.isStackKnown()) {
734 for (int i = simStack.getSize() - 1; i >= 0; i--) {
735 Operand op = simStack.getFromTop(i);
736 if (op instanceof ReturnAddressOperand) {
737 if (numRA++ > MAX_RETURN_ADDRESSES) {
738 throw new OperationNotImplementedException("Too many subroutines");
739 }
740 if (DBG_INLINE_JSR) db("simStack operand " + i + " is " + op);
741 Operand cop = candBBLE.stackState.getFromTop(i);
742 if (!Operand.conservativelyApproximates(cop, op)) {
743 if (DBG_INLINE_JSR) db("Not Matching: " + cop + " and " + op);
744 return false;
745 } else {
746 if (DBG_INLINE_JSR) db("operand " + cop + " is compatible with " + op);
747 }
748 }
749 }
750 }
751
752 if (simLocals != null && candBBLE.isLocalKnown()) {
753 for (int i = 0; i < simLocals.length; i++) {
754 Operand op = simLocals[i];
755 if (op instanceof ReturnAddressOperand) {
756 if (numRA++ > MAX_RETURN_ADDRESSES) {
757 throw new OperationNotImplementedException("Too many subroutines");
758 }
759 if (DBG_INLINE_JSR) db("simLocal " + i + " is " + op);
760 Operand cop = candBBLE.localState[i];
761 if (!Operand.conservativelyApproximates(cop, op)) {
762 if (DBG_INLINE_JSR) db("Not Matching: " + cop + " and " + op);
763 return false;
764 } else {
765 if (DBG_INLINE_JSR) db("operand " + cop + " is compatible with " + op);
766 }
767 }
768 }
769 }
770
771 if (DBG_INLINE_JSR) db("Found " + candBBLE + " to be compatible");
772 return true;
773 }
774
775 /**
776 * Get or create a block at the specified target.
777 * If simStack is non-null, rectifies stack state with target stack state.
778 * If simLocals is non-null, rectifies local state with target local state.
779 * Any instructions needed to rectify stack/local state are appended to
780 * from.
781 * As blocks are created, they are added to the red/black tree below x.
782 *
783 * @param x starting node for search.
784 * @param shouldCreate should we create the block if we run off the tree?
785 * @param target target index
786 * @param from the block from which control is being transfered
787 * and to which rectification instructions are added.
788 * @param simStack stack state to rectify, or {@code null}
789 * @param simLocals local state to rectify, or {@code null}
790 */
791 private BasicBlockLE getOrCreateBlock(BasicBlockLE x, boolean shouldCreate, int target, BasicBlockLE from,
792 OperandStack simStack, Operand[] simLocals) {
793 if (target < x.low) {
794 if (x.left == null) {
795 return condCreateAndInit(x, shouldCreate, target, from, simStack, simLocals, true);
796 } else {
797 if (DBG_BBSET) db("following left branch from " + x + " to " + x.left);
798 return getOrCreateBlock(x.left, shouldCreate, target, from, simStack, simLocals);
799 }
800 } else if (target > x.low) {
801 if ((x.low < target) && (target <= x.high)) {
802 // the target points to the middle of x; mark x for regen
803 if (DBG_BBSET) db("target points to middle of " + x);
804 markBlockForRegeneration(x);
805 x.high = x.low;
806 x.block.deleteOut();
807 if (DBG_CFG || BC2IR.DBG_SELECTED) db("Deleted all out edges of " + x.block);
808 }
809 if (x.right == null) {
810 return condCreateAndInit(x, shouldCreate, target, from, simStack, simLocals, false);
811 } else {
812 if (DBG_BBSET) db("following right branch from " + x + " to " + x.right);
813 return getOrCreateBlock(x.right, shouldCreate, target, from, simStack, simLocals);
814 }
815 } else {
816 // found a basic block at the target bytecode index.
817 if (noJSR || matchingJSRcontext(simStack, simLocals, x)) {
818 if (DBG_BBSET) db("found block " + x + " (" + x.block + ")");
819 if (simStack != null) rectifyStacks(from.block, simStack, x);
820 if (simLocals != null) rectifyLocals(simLocals, x);
821 return x;
822 }
823 if (DBG_BBSET) db("found block " + x + ", but JSR context didn't match");
824 if (x.left == null) {
825 if (x.right == null) {
826 return condCreateAndInit(x, shouldCreate, target, from, simStack, simLocals, true);
827 } else {
828 if (DBG_BBSET) {
829 db(x + " has only right child, continuing down that branch");
830 }
831 return getOrCreateBlock(x.right, shouldCreate, target, from, simStack, simLocals);
832 }
833 } else {
834 if (x.right == null) {
835 if (DBG_BBSET) {
836 db(x + " has only left child, continuing down that branch");
837 }
838 return getOrCreateBlock(x.left, shouldCreate, target, from, simStack, simLocals);
839 } else {
840 if (DBG_BBSET) {
841 db(x + " has two children, searching left branch first");
842 }
843 BasicBlockLE bble = getOrCreateBlock(x.left, false, target, from, simStack, simLocals);
844 if (bble != null) {
845 return bble;
846 } else {
847 if (DBG_BBSET) {
848 db("didn't find " + target + " on left branch, continuing down right branch");
849 }
850 return getOrCreateBlock(x.right, shouldCreate, target, from, simStack, simLocals);
851 }
852 }
853 }
854 }
855 }
856
857 /**
858 * Conditionally create a block at the specified target as a child of x.
859 * If simStack is non-{@code null}, rectifies stack state with target stack state.
860 * If simLocals is non-{@code null}, rectifies local state with target local state.
861 * Any instructions needed to rectify stack/local state are appended to
862 * from.
863 *
864 * @param x starting node for search.
865 * @param shouldCreate should we create the block if we run off the tree?
866 * @param target target index
867 * @param from the block from which control is being transfered
868 * and to which rectification instructions are added.
869 * @param simStack stack state to rectify, or {@code null}
870 * @param simLocals local state to rectify, or {@code null}
871 * @param left are we creating a left child of parent?
872 * @return the newly created block, or {@code null} if !shouldCreate
873 */
874 private BasicBlockLE condCreateAndInit(BasicBlockLE x, boolean shouldCreate, int target, BasicBlockLE from,
875 OperandStack simStack, Operand[] simLocals, boolean left) {
876 BasicBlockLE bble = null;
877 if (shouldCreate) {
878 bble = _createBBLE(target, simLocals, x, left);
879 if (simStack != null) {
880 rectifyStacks(from.block, simStack, bble);
881 }
882 if (simLocals != null) {
883 bble.copyIntoLocalState(simLocals);
884 }
885 }
886 return bble;
887 }
888
889 /**
890 * Allocate a new BBLE at the given bcIndex.
891 * If bcIndex is the start of an handler block,
892 * then a HandlerBlockLE is created.
893 * After the BBLE is created, its handlers data structure is initialized
894 * (which may cause other blocks to be created).
895 * @param bcIndex the bytecode index at which the block should be created.
896 * @param simLocals the localState to pass (via initializeExceptionHandler)to
897 * to getOrCreateBlock if we need to create BBLEs for
898 * exception handlers. This is only actually used if
899 * !noJSR. We don't need the expression stack, since
900 * the only thing on the expression stack on entry to
901 * a handler block is the exception object (and thus
902 * we can skip scanning the expression stack for
903 * return addresses when creating a handler block).
904 * @param parent parent in Red/Black tree
905 * @param left are we creating a left child of parent?
906 */
907 private BasicBlockLE _createBBLE(int bcIndex, Operand[] simLocals, BasicBlockLE parent, boolean left) {
908 BasicBlockLE newBBLE = null;
909 if (handlerPCs != null) {
910 for (int i = 0; i < handlerPCs.length; i++) {
911 if (handlerPCs[i] == bcIndex) {
912 if (newBBLE == null) {
913 newBBLE =
914 new HandlerBlockLE(bcIndex,
915 gc.inlineSequence,
916 exceptionTypes[i],
917 gc.temps,
918 gc.method.getOperandWords(),
919 gc.cfg);
920 ((HandlerBlockLE) newBBLE).entryBlock.firstRealInstruction().
921 position = gc.inlineSequence;
922 } else {
923 ((HandlerBlockLE) newBBLE).addCaughtException(exceptionTypes[i]);
924 }
925 }
926 }
927 }
928 if (newBBLE == null) {
929 newBBLE = new BasicBlockLE(bcIndex, gc.inlineSequence, gc.cfg);
930 }
931
932 // Set newBBLE.max to encode exception ranges
933 newBBLE.max = exceptionEndRange(bcIndex);
934
935 if (DBG_BBSET) db("Created " + newBBLE);
936
937 // Now, insert newBBLE into our backing Red/Black tree before we call
938 // initializeExceptionHandlers.
939 // We must do it in this order because initExHand may in turn call
940 // _createBBLE to create new handler blocks, and our tree must contain
941 // newBBLE before we can correctly insert another block.
942 treeInsert(parent, newBBLE, left);
943
944 initializeExceptionHandlers(newBBLE, simLocals);
945 return newBBLE;
946 }
947
948 /**
949 * Returns the basic block which has the next-higher bytecode index.
950 * Returns {@code null} if x is the highest block.
951 * @param x basic block at which to start the search for a higher block
952 * @param value the contents of x.low (makes tail call elim work better
953 * if we avoid the obvious 1 argument wrapper function)
954 */
955 private BasicBlockLE getSuccessor(BasicBlockLE x, int value) {
956 if (x.right != null) return minimumBB(x.right, value);
957 BasicBlockLE y = x.parent;
958 while ((y != null) && (x == y.right)) {
959 x = y;
960 y = x.parent;
961 }
962 // at this point either x is the root, or x is the left child of y
963 if ((y == null) || (y.low != value)) return y;
964 return getSuccessor(y, value);
965 }
966
967 private BasicBlockLE minimumBB(BasicBlockLE x, int value) {
968 if (x.left != null) return minimumBB(x.left, value);
969 if (value == x.low) return getSuccessor(x, value);
970 return x;
971 }
972
973 /**
974 * Insert <code>newBBLE</code> as a child of parent in our Red/Black tree.
975 * @param parent the parent node
976 * @param newBBLE the new child node
977 * @param left is the child the left or right child of parent?
978 */
979 private void treeInsert(BasicBlockLE parent, BasicBlockLE newBBLE, boolean left) {
980 if (parent == null) {
981 if (VM.VerifyAssertions) VM._assert(root == null);
982 root = newBBLE;
983 root.setBlack();
984 if (DBG_BBSET) db("inserted " + newBBLE + " as root of tree");
985 } else {
986 if (left) {
987 parent.left = newBBLE;
988 } else {
989 parent.right = newBBLE;
990 }
991 newBBLE.parent = parent;
992 if (DBG_BBSET) {
993 db("inserted new block " + newBBLE + " as " + (left ? "left" : "right") + " child of " + parent);
994 }
995 fixupBBSet(newBBLE);
996 }
997 }
998
999 /**
1000 * Performs tree fixup (restore Red/Black invariants) after adding a
1001 * new node to the tree.
1002 * @param x node that was added.
1003 */
1004 private void fixupBBSet(BasicBlockLE x) {
1005 if (DBG_BBSET) db("fixing up tree after inserting " + x);
1006 x.setRed();
1007 while (x != root) {
1008 BasicBlockLE xp = x.parent;
1009 if (xp.isBlack()) {
1010 break;
1011 }
1012 if (DBG_BBSET) db(x + " and its parent " + xp + " are both red");
1013 BasicBlockLE xpp = xp.parent;
1014 if (DBG_BBSET) db(xp + "'s parent is " + xpp);
1015 if (xp == xpp.left) {
1016 BasicBlockLE y = xpp.right;
1017 if ((y != null) && y.isRed()) {
1018 xp.setBlack();
1019 y.setBlack();
1020 xpp.setRed();
1021 x = xpp;
1022 } else {
1023 if (x == xp.right) {
1024 x = xp;
1025 leftRotateBBSet(xp);
1026 xp = x.parent;
1027 xpp = xp.parent;
1028 }
1029 xp.setBlack();
1030 xpp.setRed();
1031 rightRotateBBSet(xpp);
1032 }
1033 } else {
1034 BasicBlockLE y = xpp.left;
1035 if ((y != null) && y.isRed()) {
1036 xp.setBlack();
1037 y.setBlack();
1038 xpp.setRed();
1039 x = xpp;
1040 } else {
1041 if (x == xp.left) {
1042 x = xp;
1043 rightRotateBBSet(xp);
1044 xp = x.parent;
1045 xpp = xp.parent;
1046 }
1047 xp.setBlack();
1048 xpp.setRed();
1049 leftRotateBBSet(xpp);
1050 }
1051 }
1052 }
1053 root.setBlack();
1054 // verifyTree();
1055 }
1056
1057 private void leftRotateBBSet(BasicBlockLE x) {
1058 if (DBG_BBSET) db("performing left tree rotation");
1059 BasicBlockLE y = x.right;
1060 BasicBlockLE yl = y.left;
1061 x.right = yl;
1062 if (yl != null) {
1063 yl.parent = x;
1064 }
1065 BasicBlockLE xp = x.parent;
1066 y.parent = xp;
1067 if (xp == null) {
1068 root = y;
1069 } else if (x == xp.left) {
1070 xp.left = y;
1071 } else {
1072 xp.right = y;
1073 }
1074 y.left = x;
1075 x.parent = y;
1076 }
1077
1078 private void rightRotateBBSet(BasicBlockLE x) {
1079 if (DBG_BBSET) db("performing right tree rotation");
1080 BasicBlockLE y = x.left;
1081 BasicBlockLE yr = y.right;
1082 x.left = yr;
1083 if (yr != null) {
1084 yr.parent = x;
1085 }
1086 BasicBlockLE xp = x.parent;
1087 y.parent = xp;
1088 if (xp == null) {
1089 root = y;
1090 } else if (x == xp.right) {
1091 xp.right = y;
1092 } else {
1093 xp.left = y;
1094 }
1095 y.right = x;
1096 x.parent = y;
1097 }
1098
1099 @SuppressWarnings("unused")
1100 // here for debugging
1101 private void verifyTree() {
1102 if (VM.VerifyAssertions) {
1103 VM._assert(root.isBlack());
1104 verifyTree(root, -1, bcodes.length());
1105 countBlack(root);
1106 }
1107 }
1108
1109 private void verifyTree(BasicBlockLE node, int min, int max) {
1110 if (VM.VerifyAssertions) {
1111 VM._assert(node.low >= min);
1112 VM._assert(node.low <= max);
1113 if (node.left != null) {
1114 VM._assert(node.isBlack() || node.left.isBlack());
1115 VM._assert(node.left.parent == node);
1116 verifyTree(node.left, min, node.low);
1117 }
1118 if (node.right != null) {
1119 VM._assert(node.isBlack() || node.right.isBlack());
1120 VM._assert(node.right.parent == node);
1121 verifyTree(node.right, node.low, max);
1122 }
1123 }
1124 }
1125
1126 private int countBlack(BasicBlockLE node) {
1127 if (node == null) return 1;
1128 int left = countBlack(node.left);
1129 int right = countBlack(node.right);
1130 if (VM.VerifyAssertions) VM._assert(left == right);
1131 if (node.isBlack()) {
1132 left++;
1133 }
1134 return left;
1135 }
1136
1137 private static final class TreeEnumerator implements Enumeration<BasicBlockLE> {
1138 BasicBlockLE node;
1139
1140 static BBSet.TreeEnumerator enumFromRoot(BasicBlockLE root) {
1141 if (root.left != null) {
1142 do {
1143 root = root.left;
1144 } while (root.left != null);
1145 }
1146 return new TreeEnumerator(root);
1147 }
1148
1149 static BBSet.TreeEnumerator enumFromNode(BasicBlockLE node) {
1150 return new TreeEnumerator(node);
1151 }
1152
1153 private TreeEnumerator(BasicBlockLE node) {
1154 this.node = node;
1155 }
1156
1157 @Override
1158 public boolean hasMoreElements() {
1159 return (node != null);
1160 }
1161
1162 public BasicBlockLE next() {
1163 BasicBlockLE retVal = node;
1164 if (retVal == null) {
1165 throw new NoSuchElementException();
1166 }
1167 if (retVal.right != null) {
1168 node = retVal.right;
1169 while (node.left != null) {
1170 node = node.left;
1171 }
1172 } else {
1173 BasicBlockLE x = retVal;
1174 node = x.parent;
1175 while ((node != null) && (node.right == x)) {
1176 x = node;
1177 node = x.parent;
1178 }
1179 }
1180 return retVal;
1181 }
1182
1183 @Override
1184 public BasicBlockLE nextElement() {
1185 return next();
1186 }
1187 }
1188 }