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