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.adaptive.recompilation.instrumentation;
014
015 import java.lang.reflect.Constructor;
016 import java.util.ArrayList;
017 import java.util.Enumeration;
018 import java.util.HashMap;
019 import java.util.HashSet;
020 import java.util.Map;
021 import org.jikesrvm.VM;
022 import org.jikesrvm.adaptive.AosEntrypoints;
023 import org.jikesrvm.compilers.opt.DefUse;
024 import org.jikesrvm.compilers.opt.OptOptions;
025 import org.jikesrvm.compilers.opt.Simple;
026 import org.jikesrvm.compilers.opt.controlflow.BranchOptimizations;
027 import org.jikesrvm.compilers.opt.driver.CompilerPhase;
028 import org.jikesrvm.compilers.opt.ir.Binary;
029 import org.jikesrvm.compilers.opt.ir.GetStatic;
030 import org.jikesrvm.compilers.opt.ir.Goto;
031 import org.jikesrvm.compilers.opt.ir.IfCmp;
032 import org.jikesrvm.compilers.opt.ir.InstrumentedCounter;
033 import org.jikesrvm.compilers.opt.ir.Load;
034 import org.jikesrvm.compilers.opt.ir.BasicBlock;
035 import org.jikesrvm.compilers.opt.ir.IR;
036 import org.jikesrvm.compilers.opt.ir.IRTools;
037 import org.jikesrvm.compilers.opt.ir.Instruction;
038 import org.jikesrvm.compilers.opt.ir.Operator;
039 import static org.jikesrvm.compilers.opt.ir.Operators.GETSTATIC;
040 import static org.jikesrvm.compilers.opt.ir.Operators.GOTO;
041 import static org.jikesrvm.compilers.opt.ir.Operators.INT_ADD;
042 import static org.jikesrvm.compilers.opt.ir.Operators.INT_IFCMP;
043 import static org.jikesrvm.compilers.opt.ir.Operators.INT_LOAD;
044 import static org.jikesrvm.compilers.opt.ir.Operators.INT_STORE;
045 import static org.jikesrvm.compilers.opt.ir.Operators.IR_PROLOGUE;
046 import static org.jikesrvm.compilers.opt.ir.Operators.LABEL;
047 import static org.jikesrvm.compilers.opt.ir.Operators.PUTSTATIC;
048 import static org.jikesrvm.compilers.opt.ir.Operators.YIELDPOINT_BACKEDGE;
049 import static org.jikesrvm.compilers.opt.ir.Operators.YIELDPOINT_PROLOGUE;
050 import org.jikesrvm.compilers.opt.ir.Register;
051 import org.jikesrvm.compilers.opt.ir.PutStatic;
052 import org.jikesrvm.compilers.opt.ir.Store;
053 import org.jikesrvm.compilers.opt.ir.operand.AddressConstantOperand;
054 import org.jikesrvm.compilers.opt.ir.operand.BranchOperand;
055 import org.jikesrvm.compilers.opt.ir.operand.BranchProfileOperand;
056 import org.jikesrvm.compilers.opt.ir.operand.ConditionOperand;
057 import org.jikesrvm.compilers.opt.ir.operand.IntConstantOperand;
058 import org.jikesrvm.compilers.opt.ir.operand.LocationOperand;
059 import org.jikesrvm.compilers.opt.ir.operand.Operand;
060 import org.jikesrvm.compilers.opt.ir.operand.RegisterOperand;
061
062 /**
063 * Transforms the method so that instrumentation is sampled, rather
064 * than executed exhaustively. Includes both the full-duplication
065 * and no-duplication variations. See Arnold-Ryder PLDI 2001, and
066 * the section 4.1 of Arnold's PhD thesis.
067 * <p>
068 * NOTE: This implementation uses yieldpoints to denote where checks
069 * should be placed (to transfer control into instrumented code). It
070 * is currently assumed that these are on method entries and
071 * backedges. When optimized yieldpoint placement exists either a)
072 * it should be turned off when using this phase, or b) this phase
073 * should detect its own check locations.
074 * <p>
075 * To avoid the complexity of duplicating exception handler maps,
076 * exception handler blocks are split and a check at the top of the
077 * handler. Thus exceptions from both the checking and duplicated
078 * code are handled by the same catch block, however the check at the
079 * top of the catch block ensures that the hander code has the
080 * opportunity to be sampled.
081 */
082 public final class InstrumentationSamplingFramework extends CompilerPhase {
083
084 /**
085 * These are local copies of optimizing compiler debug options that can be
086 * set via the command line arguments.
087 */
088 private static boolean DEBUG = false;
089 private static boolean DEBUG2 = false;
090
091 /**
092 * Temporary variables
093 */
094 private RegisterOperand cbsReg = null;
095
096 /**
097 * Constructor for this compiler phase
098 */
099 private static final Constructor<CompilerPhase> constructor =
100 getCompilerPhaseConstructor(InstrumentationSamplingFramework.class);
101
102 /**
103 * Get a constructor object for this compiler phase
104 * @return compiler phase constructor
105 */
106 @Override
107 public Constructor<CompilerPhase> getClassConstructor() {
108 return constructor;
109 }
110
111 @Override
112 public boolean shouldPerform(OptOptions options) {
113 return options.ADAPTIVE_INSTRUMENTATION_SAMPLING;
114 }
115
116 @Override
117 public String getName() { return "InstrumentationSamplingFramework"; }
118
119 /**
120 * Perform this phase
121 *
122 * @param ir the governing IR
123 */
124 @Override
125 public void perform(IR ir) {
126
127 DEBUG = ir.options.DEBUG_INSTRU_SAMPLING;
128 DEBUG2 = ir.options.DEBUG_INSTRU_SAMPLING_DETAIL;
129
130 // Temp code for selective debugging. Dump the whole IR if either DEBUG2 is set, or if a specific method name is specified.
131 if (DEBUG2 || (DEBUG && ir.options.fuzzyMatchMETHOD_TO_PRINT(ir.method.toString()))) {
132 dumpIR(ir, "Before instrumentation sampling transformation");
133 dumpCFG(ir);
134 }
135
136 // Perform the actual phase here.
137 if (ir.options.ADAPTIVE_NO_DUPLICATION) {
138 performVariationNoDuplication(ir);
139 } else {
140 performVariationFullDuplication(ir, this);
141 }
142
143 // Dump method again after phase completes
144 if (DEBUG2 || (DEBUG && ir.options.fuzzyMatchMETHOD_TO_PRINT(ir.method.toString()))) {
145 dumpIR(ir, "After instrumentation sampling transformation");
146 dumpCFG(ir);
147 }
148
149 cleanUp(ir);
150
151 }
152
153 // /**
154 // * Initialization to perform before the transformation is applied
155 // */
156 // private static void initialize(IR ir) {
157 //
158 // }
159
160 //
161
162 /**
163 * Initialization to perform after the transformation is applied
164 */
165 private void cleanUp(IR ir) {
166
167 // Clean up the ir with simple optimizations
168 Simple simple = new Simple(-1, false, false, false, false);
169 simple.perform(ir);
170
171 // Perform branch optimizations (level 0 is passed because if we
172 // always want to call it if we've used the sampling framework).
173 BranchOptimizations branchOpt = new BranchOptimizations(0, true, true);
174 branchOpt.perform(ir);
175
176 // Clear the static variables
177 cbsReg = null;
178
179 //
180 // RegisterInfo.computeRegisterList(ir);
181 DefUse.recomputeSpansBasicBlock(ir);
182 DefUse.recomputeSSA(ir);
183 }
184
185 /**
186 * Perform the full duplication algorithm
187 *
188 * @param ir the governing IR
189 */
190 private void performVariationFullDuplication(IR ir, CompilerPhase phaseObject) {
191
192 // Initialize
193
194 // Used to store mapping from original to duplicated blocks
195 HashMap<BasicBlock, BasicBlock> origToDupMap = new HashMap<BasicBlock, BasicBlock>();
196 // Used to remember all exception handler blocks
197 HashSet<BasicBlock> exceptionHandlerBlocks = new HashSet<BasicBlock>();
198 // The register containing the counter value to check
199 cbsReg = ir.regpool.makeTempInt();
200
201 // 1) Make a copy of all basic blocks
202 duplicateCode(ir, origToDupMap, exceptionHandlerBlocks);
203
204 // 2) Insert counter-based sampling checks (record blocks with YP's)
205 insertCBSChecks(ir, origToDupMap, exceptionHandlerBlocks);
206
207 // 3) Fix control flow edges in duplicated code
208 adjustPointersInDuplicatedCode(ir, origToDupMap);
209
210 // 4) Remove instrumentation from checking code
211 removeInstrumentationFromOrig(ir, origToDupMap);
212
213 if (ir.options.fuzzyMatchMETHOD_TO_PRINT(ir.method.toString())) {
214 ir.verify("End of Framework");
215 }
216
217 }
218
219 /**
220 * Make a duplicate of all basic blocks down at the bottom of the
221 * code order. For now, this is done in a slightly ackward way.
222 * After duplication, the control flow within the duplicated code is
223 * not complete because each block immediately transfers you back to
224 * the original code. This gets fixed in
225 * adjustPointersInDuplicatedCode
226 *
227 * @param ir the governing IR */
228 private void duplicateCode(IR ir, HashMap<BasicBlock, BasicBlock> origToDupMap,
229 HashSet<BasicBlock> exceptionHandlerBlocks) {
230
231 if (DEBUG) VM.sysWrite("In duplicate code\n");
232
233 // Iterate through all blocks and duplicate them. While
234 // iterating, loop until you see the block that was the *original*
235 // last block. (Need to do it this way because we're adding
236 // blocks to the end as we loop.)
237 BasicBlock origLastBlock = ir.cfg.lastInCodeOrder();
238 boolean done = false;
239 BasicBlock curBlock = ir.cfg.firstInCodeOrder();
240 while (!done && curBlock != null) {
241 if (curBlock == origLastBlock) {
242 // Stop after this iteration
243 done = true;
244 }
245
246 // Don't duplicate the exit node
247 if (curBlock == ir.cfg.exit()) {
248 // Next block
249 curBlock = curBlock.nextBasicBlockInCodeOrder();
250 continue;
251 }
252
253 // Check if the block needs to be split for later insertion of
254 // a check. We split the entry basic block (first basic block
255 // in the method) to insert the method-entry check, and also
256 // exception handler blocks to simplify handling
257 if (curBlock == ir.cfg.entry() || curBlock.isExceptionHandlerBasicBlock()) {
258
259 Instruction splitInstr = null;
260
261 if (curBlock == ir.cfg.entry()) {
262 splitInstr = getFirstInstWithOperator(IR_PROLOGUE, curBlock);
263 } else {
264 splitInstr = getFirstInstWithOperator(LABEL, curBlock);
265 }
266
267 // Split entry node so the split instr isn't duplicated, but rest
268 // of block is.
269 BasicBlock blockTail = curBlock.splitNodeWithLinksAt(splitInstr, ir);
270 curBlock.recomputeNormalOut(ir);
271
272 if (curBlock.isExceptionHandlerBasicBlock()) {
273 // Remember that the tail of the block we just split is an
274 // exception handler and we want to add a check here
275 exceptionHandlerBlocks.add(blockTail);
276 }
277
278 // proceed with the duplication using the second half of the split block.
279 curBlock = blockTail;
280
281 // Is this necessary? TODO: see if it can be removed.
282 DefUse.recomputeSpansBasicBlock(ir);
283 }
284
285 // Copy the basic block
286 BasicBlock dup = myCopyWithoutLinks(curBlock, ir);
287 dup.setInfrequent(); // duplicated code is known to be infrequent.
288
289 if (DEBUG2) {
290 VM.sysWrite("Copying bb: " + curBlock + " to be " + dup + "\n");
291 }
292
293 ir.cfg.addLastInCodeOrder(dup);
294
295 // Attach a goto to the duplicated code block, so that it
296 // doesn't fall through within the duplicated code, and jumps
297 // back to the checking code. This is a bit of a convoluted way
298 // of doing things and could be cleaned up. It was done
299 // originally done to make the remaining passes simpler.
300 BasicBlock fallthrough = curBlock.getFallThroughBlock();
301 if (fallthrough != null) {
302
303 Instruction g = Goto.create(GOTO, fallthrough.makeJumpTarget());
304 dup.appendInstruction(g);
305 }
306
307 dup.recomputeNormalOut(ir);
308
309 origToDupMap.put(curBlock, dup); // Remember that basic block "dup"
310
311 // Next block
312 curBlock = curBlock.nextBasicBlockInCodeOrder();
313 }
314 }
315
316 /**
317 * In the checking code, insert CBS checks at each yieldpoint, to
318 * transfer code into the duplicated (instrumented) code.
319 * For now, checks are inserted at all yieldpoints (See comment at
320 * top of file).
321 *
322 * @param ir the governing IR
323 */
324 private void insertCBSChecks(IR ir, HashMap<BasicBlock, BasicBlock> origToDupMap,
325 HashSet<BasicBlock> exceptionHandlerBlocks) {
326
327 // Iterate through the basic blocks in the original code
328 for (Map.Entry<BasicBlock, BasicBlock> entry : origToDupMap.entrySet()) {
329 BasicBlock bb = entry.getKey();
330 BasicBlock dup = entry.getValue();
331
332 if (dup == null) {
333 // Getting here means that for some reason the block was not duplicated.
334 if (DEBUG) {
335 VM.sysWrite("Debug: block " + bb + " was not duplicated\n");
336 }
337 continue;
338 }
339
340 // If you have a yieldpoint, or if you are the predecessor of a
341 // split exception handler when duplicating code) then insert a
342 // check
343
344 if (getFirstInstWithYieldPoint(bb) != null || // contains yieldpoint
345 exceptionHandlerBlocks.contains(bb)) { // is exception handler
346
347 BasicBlock checkBB = null;
348 BasicBlock prev = bb.prevBasicBlockInCodeOrder();
349 // Entry has been split, so any node containing a yieldpoint
350 // should not be first
351 if (VM.VerifyAssertions) {
352 VM._assert(prev != null);
353 }
354
355 // Make a new BB that contains the check itself (it needs to
356 // be a basic block because the duplicated code branches back
357 // to it).
358 checkBB = new BasicBlock(-1, null, ir.cfg);
359
360 // Break the code to insert the check logic
361 ir.cfg.breakCodeOrder(prev, bb);
362 ir.cfg.linkInCodeOrder(prev, checkBB);
363 ir.cfg.linkInCodeOrder(checkBB, bb);
364 if (DEBUG) {
365 VM.sysWrite("Creating check " + checkBB + " to preceed " + bb + " \n");
366 }
367
368 // Step 2, Make all of bb's predecessors point to the check instead
369 for (Enumeration<BasicBlock> preds = bb.getIn(); preds.hasMoreElements();) {
370 BasicBlock pred = preds.nextElement();
371 pred.redirectOuts(bb, checkBB, ir);
372 }
373
374 // Insert the check logic
375 createCheck(checkBB, bb, dup, false, ir);
376
377 }
378 }
379 }
380
381 /**
382 * Append a check to a basic block, and make it jump to the right places.
383 *
384 * @param checkBB The block to append the CBS check to.
385 * @param noInstBB The basic block to jump to if the CBS check fails
386 * @param instBB The basicBlock to jump to if the CBS check succeeds
387 * @param fallthroughToInstBB Should checkBB fallthrough to instBB
388 * (otherwise it must fallthrough to noInstBB)
389 */
390 private void createCheck(BasicBlock checkBB, BasicBlock noInstBB, BasicBlock instBB,
391 boolean fallthroughToInstBB, IR ir) {
392
393 appendLoad(checkBB, ir);
394
395 // Depending on where you fallthrough, set the condition correctly
396 ConditionOperand cond = null;
397 BranchOperand target = null;
398 BranchProfileOperand profileOperand = null;
399 if (fallthroughToInstBB) {
400 // The instrumented basic block is the fallthrough of checkBB,
401 // so make the branch jump to the non-instrumented block.
402 cond = ConditionOperand.GREATER();
403 target = noInstBB.makeJumpTarget();
404 profileOperand = new BranchProfileOperand(1.0f); // Taken frequently
405 } else {
406 // The non-instrumented basic block is the fallthrough of checkBB,
407 // so make the branch jump to the instrumented block.
408 cond = ConditionOperand.LESS_EQUAL();
409 target = instBB.makeJumpTarget();
410 profileOperand = new BranchProfileOperand(0.0f); // Taken infrequently
411 }
412 RegisterOperand guard = ir.regpool.makeTempValidation();
413 checkBB.appendInstruction(IfCmp.create(INT_IFCMP,
414 guard,
415 cbsReg.copyRO(),
416 new IntConstantOperand(0),
417 cond,
418 target,
419 profileOperand));
420 checkBB.recomputeNormalOut(ir);
421
422 // Insert the decrement and store in the block that is the
423 // successor of the check
424 prependStore(noInstBB, ir);
425 prependDecrement(noInstBB, ir);
426
427 // Insert a counter reset in the duplicated block.
428 prependCounterReset(instBB, ir);
429
430 }
431
432 /**
433 * Append a load of the global counter to the given basic block.
434 *
435 * WARNING: Tested for LIR only!
436 *
437 * @param bb The block to append the load to
438 * @param ir The IR */
439 private void appendLoad(BasicBlock bb, IR ir) {
440
441 if (DEBUG) VM.sysWrite("Adding load to " + bb + "\n");
442 Instruction load = null;
443 if (ir.options.ADAPTIVE_PROCESSOR_SPECIFIC_COUNTER) {
444 // Use one CBS counter per processor (better for multi threaded apps)
445
446 if (ir.IRStage == IR.HIR) {
447 // NOT IMPLEMENTED
448 } else {
449 // Phase is being used in LIR
450 // Insert the load instruction.
451 load =
452 Load.create(INT_LOAD,
453 cbsReg.copyRO(),
454 ir.regpool.makeTROp(),
455 IRTools.AC(AosEntrypoints.threadCBSField.getOffset()),
456 new LocationOperand(AosEntrypoints.threadCBSField));
457
458 bb.appendInstruction(load);
459 }
460 } else {
461 // Use global counter
462 if (ir.IRStage == IR.HIR) {
463 Operand offsetOp = new AddressConstantOperand(AosEntrypoints.globalCBSField.getOffset());
464 load =
465 GetStatic.create(GETSTATIC,
466 cbsReg.copyRO(),
467 offsetOp,
468 new LocationOperand(AosEntrypoints.globalCBSField));
469 bb.appendInstruction(load);
470 } else {
471 // LIR
472 Instruction dummy = Load.create(INT_LOAD, null, null, null, null);
473
474 bb.appendInstruction(dummy);
475 load =
476 Load.create(INT_LOAD,
477 cbsReg.copyRO(),
478 ir.regpool.makeJTOCOp(ir, dummy),
479 IRTools.AC(AosEntrypoints.globalCBSField.getOffset()),
480 new LocationOperand(AosEntrypoints.globalCBSField));
481
482 dummy.insertBefore(load);
483 dummy.remove();
484 }
485 }
486 }
487
488 /**
489 * Append a store of the global counter to the given basic block.
490 *
491 * WARNING: Tested in LIR only!
492 *
493 * @param bb The block to append the load to
494 * @param ir The IR */
495 private void prependStore(BasicBlock bb, IR ir) {
496
497 if (DEBUG) VM.sysWrite("Adding store to " + bb + "\n");
498 Instruction store = null;
499 if (ir.options.ADAPTIVE_PROCESSOR_SPECIFIC_COUNTER) {
500 store =
501 Store.create(INT_STORE,
502 cbsReg.copyRO(),
503 ir.regpool.makeTROp(),
504 IRTools.AC(AosEntrypoints.threadCBSField.getOffset()),
505 new LocationOperand(AosEntrypoints.threadCBSField));
506
507 bb.prependInstruction(store);
508 } else {
509 if (ir.IRStage == IR.HIR) {
510 store =
511 PutStatic.create(PUTSTATIC,
512 cbsReg.copyRO(),
513 new AddressConstantOperand(AosEntrypoints.globalCBSField.getOffset()),
514 new LocationOperand(AosEntrypoints.globalCBSField));
515
516 bb.prependInstruction(store);
517 } else {
518 Instruction dummy = Load.create(INT_LOAD, null, null, null, null);
519
520 bb.prependInstruction(dummy);
521 store =
522 Store.create(INT_STORE,
523 cbsReg.copyRO(),
524 ir.regpool.makeJTOCOp(ir, dummy),
525 IRTools.AC(AosEntrypoints.globalCBSField.getOffset()),
526 new LocationOperand(AosEntrypoints.globalCBSField));
527
528 dummy.insertBefore(store);
529 dummy.remove();
530 }
531 }
532 }
533
534 /**
535 * Append a decrement of the global counter to the given basic block.
536 *
537 * Tested in LIR only!
538 *
539 * @param bb The block to append the load to
540 * @param ir The IR
541 */
542 private void prependDecrement(BasicBlock bb, IR ir) {
543 if (DEBUG) VM.sysWrite("Adding Increment to " + bb + "\n");
544
545 RegisterOperand use = cbsReg.copyRO();
546 RegisterOperand def = use.copyU2D();
547 Instruction inc = Binary.create(INT_ADD, def, use, IRTools.IC(-1));
548 bb.prependInstruction(inc);
549 }
550
551 /**
552 * Prepend the code to reset the global counter to the given basic
553 * block.
554 *
555 * Warning: Tested in LIR only!
556 *
557 * @param bb The block to append the load to
558 * @param ir The IR */
559 private void prependCounterReset(BasicBlock bb, IR ir) {
560 Instruction load = null;
561 Instruction store = null;
562
563 if (ir.IRStage == IR.HIR) {
564 // Not tested
565 Operand offsetOp = new AddressConstantOperand(AosEntrypoints.cbsResetValueField.getOffset());
566 load =
567 GetStatic.create(GETSTATIC,
568 cbsReg.copyRO(),
569 offsetOp,
570 new LocationOperand(AosEntrypoints.cbsResetValueField));
571 store =
572 PutStatic.create(PUTSTATIC,
573 cbsReg.copyRO(),
574 new AddressConstantOperand(AosEntrypoints.globalCBSField.getOffset()),
575 new LocationOperand(AosEntrypoints.globalCBSField));
576 bb.prependInstruction(store);
577 bb.prependInstruction(load);
578 } else {
579 // LIR
580 Instruction dummy = Load.create(INT_LOAD, null, null, null, null);
581 bb.prependInstruction(dummy);
582 // Load the reset value
583 load =
584 Load.create(INT_LOAD,
585 cbsReg.copyRO(),
586 ir.regpool.makeJTOCOp(ir, dummy),
587 IRTools.AC(AosEntrypoints.cbsResetValueField.getOffset()),
588 new LocationOperand(AosEntrypoints.cbsResetValueField));
589
590 dummy.insertBefore(load);
591
592 // Store it in the counter register
593 if (ir.options.ADAPTIVE_PROCESSOR_SPECIFIC_COUNTER) {
594 store =
595 Store.create(INT_STORE,
596 cbsReg.copyRO(),
597 ir.regpool.makeTROp(),
598 IRTools.AC(AosEntrypoints.threadCBSField.getOffset()),
599 new LocationOperand(AosEntrypoints.threadCBSField));
600 } else {
601 // Use global counter
602 store =
603 Store.create(INT_STORE,
604 cbsReg.copyRO(),
605 ir.regpool.makeJTOCOp(ir, dummy),
606 IRTools.AC(AosEntrypoints.globalCBSField.getOffset()),
607 new LocationOperand(AosEntrypoints.globalCBSField));
608 }
609 dummy.insertBefore(store);
610 dummy.remove();
611 }
612
613 }
614
615 /**
616 * Go through all instructions and find the first with the given
617 * operator.
618 *
619 * @param operator The operator to look for
620 * @param bb The basic block in which to look
621 * @return The first instruction in bb that has operator operator. */
622 private static Instruction getFirstInstWithOperator(Operator operator, BasicBlock bb) {
623 for (Enumeration<Instruction> ie = bb.forwardInstrEnumerator(); ie.hasMoreElements();) {
624 Instruction i = ie.nextElement();
625
626 if (i.operator() == operator) {
627 return i;
628 }
629 }
630 return null;
631 }
632
633 /**
634 * Go through all instructions and find one that is a yield point
635 *
636 * @param bb The basic block in which to look
637 * @return The first instruction in bb that has a yield point
638 */
639 public static Instruction getFirstInstWithYieldPoint(BasicBlock bb) {
640 for (Enumeration<Instruction> ie = bb.forwardInstrEnumerator(); ie.hasMoreElements();) {
641 Instruction i = ie.nextElement();
642
643 if (isYieldpoint(i)) {
644 return i;
645 }
646 }
647 return null;
648 }
649
650 /**
651 * Is the given instruction a yieldpoint?
652 *
653 * For now we ignore epilogue yieldpoints since we are only concerned with
654 * method entries and backedges.
655 */
656 public static boolean isYieldpoint(Instruction i) {
657 return i.operator() == YIELDPOINT_PROLOGUE ||
658 // Skip epilogue yieldpoints. No checks needed for them
659 // i.operator() == YIELDPOINT_EPILOGUE ||
660 i.operator() == YIELDPOINT_BACKEDGE;
661
662 }
663
664 /**
665 * Go through all blocks in duplicated code and adjust the edges as
666 * follows:
667 * <ol>
668 * <li>All edges (in duplicated code) that go into a block with a
669 * yieldpoint must jump to back to the original code. This is
670 * actually already satisfied because we appended goto's to all
671 * duplicated bb's (the goto's go back to orig code)
672 * <li>All edges that do NOT go into a yieldpoint block must stay
673 * (either fallthrough or jump to a block in) in the duplicated
674 * code.
675 * </ol>
676 *
677 * @param ir the governing IR */
678 private static void adjustPointersInDuplicatedCode(IR ir, HashMap<BasicBlock, BasicBlock> origToDupMap) {
679
680 // Iterate over the original version of all duplicate blocks
681 for (BasicBlock dupBlock : origToDupMap.values()) {
682
683 // Look at the successors of duplicated Block.
684 for (Enumeration<BasicBlock> out = dupBlock.getNormalOut(); out.hasMoreElements();) {
685 BasicBlock origSucc = out.nextElement();
686
687 BasicBlock dupSucc = origToDupMap.get(origSucc);
688
689 // If the successor is not in the duplicated code, then
690 // redirect it to stay in the duplicated code. (dupSucc !=
691 // null implies that origSucc has a corresponding duplicated
692 // block, and thus origSucc is in the checking code.
693
694 if (dupSucc != null) {
695
696 dupBlock.redirectOuts(origSucc, dupSucc, ir);
697 if (DEBUG) {
698 VM.sysWrite("Source: " + dupBlock + "\n");
699 VM.sysWrite("============= FROM " + origSucc + " =============\n");
700 //origSucc.printExtended();
701 VM.sysWrite("============= TO " + dupSucc + "=============\n");
702 //dupSucc.printExtended();
703 }
704 } else {
705 if (DEBUG) {
706 VM.sysWrite("Not adjusting pointer from " + dupBlock + " to " + origSucc + " because dupSucc is null\n");
707 }
708 }
709 }
710
711 }
712 }
713
714 /**
715 * Remove instrumentation from the original version of all duplicated
716 * basic blocks.<p>
717 *
718 * The yieldpoints can also be removed from either the original or
719 * the duplicated code. If you remove them from the original, it
720 * will make it run faster (since it is executed more than the
721 * duplicated) however that means that you can't turn off the
722 * instrumentation or you could infinitely loop without executing
723 * yieldpoints!
724 *
725 * @param ir the governing IR */
726 private static void removeInstrumentationFromOrig(IR ir, HashMap<BasicBlock, BasicBlock> origToDupMap) {
727 // Iterate over the original version of all duplicate blocks
728
729 for (BasicBlock origBlock : origToDupMap.keySet()) {
730
731 // Remove all instrumentation instructions. They already have
732 // been transfered to the duplicated code.
733 for (Enumeration<Instruction> ie = origBlock.forwardInstrEnumerator(); ie.hasMoreElements();) {
734 Instruction i = ie.nextElement();
735 if (isInstrumentationInstruction(i) || (isYieldpoint(i) && ir.options.ADAPTIVE_REMOVE_YP_FROM_CHECKING)) {
736
737 if (DEBUG) VM.sysWrite("Removing " + i + "\n");
738 i.remove();
739 }
740 }
741 }
742 }
743
744 /**
745 * The same as BasicBlock.copyWithoutLinks except that it
746 * renames all temp variables that are never used outside the basic
747 * block. This 1) helps eliminate the artificially large live
748 * ranges that might have been created (assuming the reg allocator
749 * isn't too smart) and 2) it prevents BURS from crashing.
750 * <p>
751 * PRECONDITION: the spansBasicBlock bit must be correct by calling
752 * DefUse.recomputeSpansBasicBlock(IR);
753 */
754 private static BasicBlock myCopyWithoutLinks(BasicBlock bb, IR ir) {
755
756 BasicBlock newBlock = bb.copyWithoutLinks(ir);
757
758 // Without this, there were sanity errors at one point.
759 updateTemps(newBlock, ir);
760
761 return newBlock;
762 }
763
764 /**
765 * Given an basic block, rename all of the temporary registers that are local to the block.
766 */
767 private static void updateTemps(BasicBlock bb, IR ir) {
768
769 // Need to clear the scratch objects before we start using them
770 clearScratchObjects(bb, ir);
771
772 // For each instruction in the block
773 for (Enumeration<Instruction> ie = bb.forwardInstrEnumerator(); ie.hasMoreElements();) {
774 Instruction inst = ie.nextElement();
775
776 // Look at each register operand
777 int numOperands = inst.getNumberOfOperands();
778 for (int i = 0; i < numOperands; i++) {
779 Operand op = inst.getOperand(i);
780 if (op instanceof RegisterOperand) {
781 RegisterOperand ro = (RegisterOperand) op;
782 if (ro.getRegister().isTemp() && !ro.getRegister().spansBasicBlock()) {
783 // This register does not span multiple basic blocks, so
784 // replace it with a temp.
785 RegisterOperand newReg = getOrCreateDupReg(ro, ir);
786 if (DEBUG2) {
787 VM.sysWrite("Was " + ro + " and now it's " + newReg + "\n");
788 }
789 inst.putOperand(i, newReg);
790 }
791 }
792 }
793 }
794
795 // Clear them afterward also, otherwise register allocation fails.
796 // (TODO: Shouldn't they just be cleared before use in register
797 // allocation?)
798 clearScratchObjects(bb, ir);
799 }
800
801 /**
802 * Go through all statements in the basic block and clear the
803 * scratch objects.
804 */
805 private static void clearScratchObjects(BasicBlock bb, IR ir) {
806 // For each instruction in the block
807 for (Enumeration<Instruction> ie = bb.forwardInstrEnumerator(); ie.hasMoreElements();) {
808 Instruction inst = ie.nextElement();
809
810 // Look at each register operand
811 int numOperands = inst.getNumberOfOperands();
812 for (int i = 0; i < numOperands; i++) {
813 Operand op = inst.getOperand(i);
814 if (op instanceof RegisterOperand) {
815 RegisterOperand ro = (RegisterOperand) op;
816 if (ro.getRegister().isTemp() && !ro.getRegister().spansBasicBlock()) {
817
818 // This register does not span multiple basic blocks. It
819 // will be touched by the register duplication, so clear
820 // its scratch reg.
821 ro.getRegister().scratchObject = null;
822 }
823 }
824 }
825 }
826
827 }
828
829 /**
830 * The given register a) does not span multiple basic block, and b)
831 * is used in a basic block that is being duplicated. It is
832 * therefore safe to replace all occurrences of the register with a
833 * new register. This method returns the duplicated
834 * register that is associated with the given register. If a
835 * duplicated register does not exist, it is created and recorded.
836 */
837 private static RegisterOperand getOrCreateDupReg(RegisterOperand ro, IR ir) {
838
839 // Check if the register associated with this regOperand already
840 // has a paralles operand
841 if (ro.getRegister().scratchObject == null) {
842 // If no dup register exists, make a new one and remember it.
843 RegisterOperand dupRegOp = ir.regpool.makeTemp(ro.getType());
844 ro.getRegister().scratchObject = dupRegOp.getRegister();
845 }
846 return new RegisterOperand((Register) ro.getRegister().scratchObject, ro.getType());
847 }
848
849 /**
850 * Perform the NoDuplication version of the framework (see
851 * Arnold-Ryder PLDI 2001). Instrumentation operations are wrapped
852 * in a conditional, but no code duplication is performed.
853 */
854 private void performVariationNoDuplication(IR ir) {
855 // The register containing the counter value to check
856 cbsReg = ir.regpool.makeTempInt();
857
858 ArrayList<Instruction> instrumentationOperations = new ArrayList<Instruction>();
859 for (Enumeration<BasicBlock> allBB = ir.getBasicBlocks(); allBB.hasMoreElements();) {
860 BasicBlock bb = allBB.nextElement();
861
862 for (Enumeration<Instruction> ie = bb.forwardInstrEnumerator(); ie.hasMoreElements();) {
863 Instruction i = ie.nextElement();
864
865 // If it's an instrumentation operation, remember the instruction
866 if (isInstrumentationInstruction(i)) {
867 instrumentationOperations.add(i);
868 }
869 }
870 }
871
872 // for each instrumentation operation.
873 for (Instruction i : instrumentationOperations) {
874 BasicBlock bb = i.getBasicBlock();
875 conditionalizeInstrumentationOperation(ir, i, bb);
876 }
877 }
878
879 /**
880 * Take an instrumentation operation (an instruction) and guard it
881 * with a counter-based check.
882 * <ol>
883 * <li>split the basic block before and after the i
884 * to get A -> B -> C
885 * <li>Add check to A, making it go to B if it succeeds, otherwise C
886 * </ol>
887 */
888 private void conditionalizeInstrumentationOperation(IR ir, Instruction i, BasicBlock bb) {
889
890 // Create bb after instrumentation ('C', in comment above)
891 BasicBlock C = bb.splitNodeWithLinksAt(i, ir);
892 bb.recomputeNormalOut(ir);
893
894 // Create bb before instrumentation ('A', in comment above)
895 Instruction prev = i.prevInstructionInCodeOrder();
896
897 BasicBlock B = null;
898 try {
899 B = bb.splitNodeWithLinksAt(prev, ir);
900 } catch (RuntimeException e) {
901 VM.sysWrite("Bombed when I: " + i + " prev: " + prev + "\n");
902 bb.printExtended();
903 throw e;
904 }
905
906 bb.recomputeNormalOut(ir);
907
908 BasicBlock A = bb;
909
910 // Now, add check to A, that jumps to C
911 createCheck(A, C, B, true, ir);
912 }
913
914 /**
915 * How to determine whether a given instruction is an
916 * "instrumentation instruction". In other words, it should be
917 * executed only when a sample is being taken.
918 */
919 private static boolean isInstrumentationInstruction(Instruction i) {
920
921 // if (i.bcIndex == INSTRUMENTATION_BCI &&
922 // (Call.conforms(i) ||
923 // if (InstrumentedCounter.conforms(i)))
924
925 return InstrumentedCounter.conforms(i);
926 }
927
928 /**
929 * Temp debugging code
930 */
931 public static void dumpCFG(IR ir) {
932
933 for (Enumeration<BasicBlock> allBB = ir.getBasicBlocks(); allBB.hasMoreElements();) {
934 BasicBlock curBB = allBB.nextElement();
935 curBB.printExtended();
936 }
937 }
938 }
939
940
941