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.liveness;
014
015 import static org.jikesrvm.compilers.opt.ir.Operators.PHI;
016 import static org.jikesrvm.osr.OSRConstants.LongTypeCode;
017 import static org.jikesrvm.osr.OSRConstants.VoidTypeCode;
018
019 import java.lang.reflect.Constructor;
020 import java.util.ArrayList;
021 import java.util.Enumeration;
022 import java.util.HashSet;
023 import java.util.Iterator;
024 import java.util.LinkedList;
025 import java.util.List;
026 import java.util.Stack;
027
028 import org.jikesrvm.VM;
029 import org.jikesrvm.classloader.TypeReference;
030 import org.jikesrvm.compilers.opt.DefUse;
031 import org.jikesrvm.compilers.opt.driver.CompilerPhase;
032 import org.jikesrvm.compilers.opt.ir.BasicBlock;
033 import org.jikesrvm.compilers.opt.ir.BasicBlockEnumeration;
034 import org.jikesrvm.compilers.opt.ir.ExceptionHandlerBasicBlock;
035 import org.jikesrvm.compilers.opt.ir.GCIRMap;
036 import org.jikesrvm.compilers.opt.ir.IR;
037 import org.jikesrvm.compilers.opt.ir.Instruction;
038 import org.jikesrvm.compilers.opt.ir.OperandEnumeration;
039 import org.jikesrvm.compilers.opt.ir.OsrPoint;
040 import org.jikesrvm.compilers.opt.ir.Phi;
041 import org.jikesrvm.compilers.opt.ir.RegSpillListElement;
042 import org.jikesrvm.compilers.opt.ir.Register;
043 import org.jikesrvm.compilers.opt.ir.operand.BasicBlockOperand;
044 import org.jikesrvm.compilers.opt.ir.operand.InlinedOsrTypeInfoOperand;
045 import org.jikesrvm.compilers.opt.ir.operand.Operand;
046 import org.jikesrvm.compilers.opt.ir.operand.RegisterOperand;
047 import org.jikesrvm.compilers.opt.regalloc.LiveIntervalElement;
048 import org.jikesrvm.compilers.opt.util.EmptyIterator;
049 import org.jikesrvm.compilers.opt.util.SortedGraphIterator;
050 import org.jikesrvm.osr.OSRConstants;
051 import org.jikesrvm.osr.LocalRegPair;
052 import org.jikesrvm.osr.MethodVariables;
053 import org.jikesrvm.osr.VariableMap;
054
055 /**
056 * This class performs a flow-sensitive iterative live variable analysis.
057 * The result of this analysis is live ranges for each basic block.
058 * (@see BasicBlock)
059 * This class can also optionally construct GC maps. These GC maps
060 * are later used to create the final gc map (see OptReferenceMap.java).
061 *
062 * The bottom of the file contains comments regarding imprecise exceptions.
063 */
064 public final class LiveAnalysis extends CompilerPhase {
065 // Real Instance Variables
066 /**
067 * Should we also create GC maps while we are computing liveness
068 */
069 private final boolean createGCMaps;
070
071 /**
072 * Should we store liveness information at the top of each handler block?
073 */
074 private final boolean storeLiveAtHandlers;
075
076 /**
077 * Should we skip guard registers?
078 */
079 private final boolean skipGuards;
080
081 /**
082 * Should we skip the (final) local propagation phase?
083 */
084 private final boolean skipLocal;
085
086 /**
087 * The current LiveSet that we will carry around
088 */
089 private LiveSet currentSet;
090
091 /**
092 * Temporary live information associated with each basic block
093 */
094 private BBLiveElement[] bbLiveInfo;
095
096 /**
097 * The GC map associated with the IR, optionally filled by this class
098 */
099 private final GCIRMap map;
100
101 private final VariableMap osrMap;
102
103 /**
104 * For each register, the set of live interval elements describing the
105 * register.
106 */
107 private ArrayList<LiveIntervalElement>[] registerMap;
108
109 /** Debugging info */
110 private static final boolean DEBUG = false;
111
112 /** Even more debugging info */
113 private static final boolean VERBOSE = false;
114
115 public String getName() {
116 return "Live Analysis";
117 }
118
119 /**
120 * The constructor is used to specify whether GC maps should be computed
121 * along with live analysis.
122 *
123 * @param createGCMaps should we create GC maps?
124 * @param skipLocal should we skip the (final) local propagation phase?
125 */
126 public LiveAnalysis(boolean createGCMaps, boolean skipLocal) {
127 this(createGCMaps, skipLocal, false, true);
128 }
129
130 /**
131 * The constructor is used to specify whether GC maps should be computed
132 * along with live analysis.
133 *
134 * @param createGCMaps should we create GC maps?
135 * @param skipLocal should we skip the (final) local propagation phase?
136 * @param storeLiveAtHandlers should we store liveness info at the
137 * top of each handler block?
138 */
139 public LiveAnalysis(boolean createGCMaps, boolean skipLocal, boolean storeLiveAtHandlers) {
140 this(createGCMaps, skipLocal, storeLiveAtHandlers, true);
141 }
142
143 /**
144 * The constructor is used to specify whether GC maps should be computed
145 * along with live analysis.
146 *
147 * @param createGCMaps should we create GC maps?
148 * @param skipLocal should we skip the (final) local propagation phase?
149 * @param storeLiveAtHandlers should we store liveness info at the
150 * top of each handler block?
151 * @param skipGuards should we ignore validation registers?
152 */
153 public LiveAnalysis(boolean createGCMaps, boolean skipLocal, boolean storeLiveAtHandlers, boolean skipGuards) {
154 super(new Object[]{createGCMaps, skipLocal, storeLiveAtHandlers, skipGuards});
155 this.createGCMaps = createGCMaps;
156 this.skipLocal = skipLocal;
157 this.storeLiveAtHandlers = storeLiveAtHandlers;
158 this.skipGuards = skipGuards;
159 if (createGCMaps) {
160 // Create the IR-based Map we will use during compilation
161 // At a later phase this map is converted into the "runtime"
162 // map, which is called OptReferenceMap.
163 map = new GCIRMap();
164 osrMap = new VariableMap();
165 } else {
166 map = null;
167 osrMap = null;
168 }
169 }
170
171 /**
172 * By default we don't create GC maps and do perform the local prop phase
173 */
174 public LiveAnalysis() {
175 this(false, false, false, true);
176 }
177
178 /**
179 * Constructor for this compiler phase
180 */
181 private static final Constructor<CompilerPhase> constructor =
182 getCompilerPhaseConstructor(LiveAnalysis.class,
183 new Class[]{Boolean.TYPE, Boolean.TYPE, Boolean.TYPE, Boolean.TYPE});
184
185 /**
186 * Get a constructor object for this compiler phase
187 * @return compiler phase constructor
188 */
189 public Constructor<CompilerPhase> getClassConstructor() {
190 return constructor;
191 }
192
193 /**
194 * The entry point into this class
195 * Perform live variable analysis on this IR, constructing live
196 * range info and (optionally) GC map info as we go.
197 *
198 * @param ir the ir
199 */
200 public void perform(IR ir) {
201
202 // Debugging information
203 // Live Intervals, GC Maps, and fixed-point results
204 final boolean dumpFinalLiveIntervals = DEBUG ||
205 ir.options.PRINT_GC_MAPS &&
206 (!ir.options.hasMETHOD_TO_PRINT() ||
207 (ir.options.hasMETHOD_TO_PRINT() && ir.options.fuzzyMatchMETHOD_TO_PRINT(ir.method.toString()))
208 );
209 final boolean dumpFinalMaps = dumpFinalLiveIntervals;
210 final boolean dumpFixedPointResults = dumpFinalLiveIntervals;
211
212 // make sure IR info is up-to-date
213 DefUse.recomputeSpansBasicBlock(ir);
214 debugBegining(ir, createGCMaps, dumpFinalLiveIntervals, dumpFinalMaps, dumpFixedPointResults);
215 bbLiveInfo = new BBLiveElement[ir.cfg.numberOfNodes()];
216
217 for (int i = 0; i < ir.cfg.numberOfNodes(); i++) {
218 bbLiveInfo[i] = new BBLiveElement();
219 }
220
221 // allocate the "currentSet" which is used to cache the current results
222 currentSet = new LiveSet();
223 boolean reuseCurrentSet = false;
224
225 // make sure reverse top sort order is built
226 // currentBlock is the first node in the list
227 BasicBlock currentBlock = (BasicBlock) ir.cfg.buildRevTopSort();
228
229 // 2nd param: true means forward analysis; false means backward analysis
230 SortedGraphIterator bbIter = new SortedGraphIterator(currentBlock, false);
231 while (currentBlock != null) {
232 boolean changed = processBlock(currentBlock, reuseCurrentSet, ir);
233
234 // mark this block as processed and get the next one
235 BasicBlock nextBlock = (BasicBlock) bbIter.markAndGetNextTopSort(changed);
236
237 // check to see if nextBlock has only one successor, currentBlock.
238 // If so, we can reuse the current set and avoid performing a meet.
239 reuseCurrentSet = nextBlock != null && bbIter.isSinglePredecessor(currentBlock, nextBlock);
240 currentBlock = nextBlock;
241 }
242 debugPostGlobal(ir, dumpFinalLiveIntervals, dumpFinalMaps, dumpFixedPointResults);
243
244 // Now compute live ranges, using results from the fixed point computation
245 // Also, optionally create GC maps
246 // SSA doesn't need this part so we allow it to be optional.
247 // However, if we don't perform it than the final maps and intervals aren't
248 // created, so we can't print them.
249 if (!skipLocal) {
250 performLocalPropagation(ir, createGCMaps);
251
252 if (createGCMaps && dumpFinalMaps) {
253 System.out.println("**** START OF IR for method: " +
254 ir.method.getName() +
255 " in class: " +
256 ir.method.getDeclaringClass());
257 ir.printInstructions();
258 System.out.println("**** END OF IR INSTRUCTION DUMP ****");
259
260 printFinalMaps(ir);
261 }
262 if (dumpFinalLiveIntervals) {
263 printFinalLiveIntervals(ir);
264 }
265 // If we performed the local propagation, live interval information
266 // lives off of each basic block.
267 // Thus, we no longer need bbLiveInfo (the fixed points results)
268 // When we don't perform the local propagation, such as translating
269 // out of SSA, then we need to keep bbLiveInfo around
270 bbLiveInfo = null;
271
272 // compute the mapping from registers to live interval elements
273 computeRegisterMap(ir);
274 }
275
276 // No longer need currentSet, which is simply a cache of a LiveSet).
277 currentSet = null;
278
279 // This will be null if createGCMaps is false
280 if (createGCMaps) {
281 ir.MIRInfo.gcIRMap = map;
282 ir.MIRInfo.osrVarMap = osrMap;
283 }
284
285 // record whether or not we stored liveness information for handlers.
286 ir.setHandlerLivenessComputed(storeLiveAtHandlers);
287 }
288
289 /**
290 * Return an iterator over all the live interval elements for a given
291 * register.
292 */
293 public Iterator<LiveIntervalElement> iterateLiveIntervals(Register r) {
294 ArrayList<LiveIntervalElement> set = registerMap[r.getNumber()];
295 if (set == null) {
296 @SuppressWarnings("unchecked") // Can't type-check EmptyIterator.INSTANCE in java
297 Iterator<LiveIntervalElement> empty = (Iterator) EmptyIterator.INSTANCE;
298 return empty;
299 } else {
300 return set.iterator();
301 }
302 }
303
304 /**
305 * Update the data structures to reflect that all live intervals for r2
306 * are now intervals for r1.
307 */
308 public void merge(Register r1, Register r2) {
309 ArrayList<LiveIntervalElement> toRemove = new ArrayList<LiveIntervalElement>(5);
310
311 for (Iterator<LiveIntervalElement> i = iterateLiveIntervals(r2); i.hasNext();) {
312 LiveIntervalElement interval = i.next();
313 interval.setRegister(r1);
314 addToRegisterMap(r1, interval);
315 // defer removing the interval to avoid concurrent modification of
316 // the iterator's backing set.
317 toRemove.add(interval);
318 }
319 // perform deferred removals
320 for (LiveIntervalElement interval : toRemove) {
321 removeFromRegisterMap(r2, interval);
322 }
323 }
324
325 /**
326 * Set up a mapping from each register to the set of live intervals for
327 * the register.
328 * <p>
329 * Side effect: map each live interval element to its basic block.
330 */
331 @SuppressWarnings("unchecked")
332 private void computeRegisterMap(IR ir) {
333 registerMap = new ArrayList[ir.regpool.getNumberOfSymbolicRegisters()];
334 for (Enumeration e = ir.getBasicBlocks(); e.hasMoreElements();) {
335 BasicBlock bb = (BasicBlock) e.nextElement();
336 for (Enumeration i = bb.enumerateLiveIntervals(); i.hasMoreElements();) {
337 LiveIntervalElement lie = (LiveIntervalElement) i.nextElement();
338 lie.setBasicBlock(bb);
339 if (lie.getRegister().isSymbolic()) {
340 addToRegisterMap(lie.getRegister(), lie);
341 }
342 }
343 }
344 }
345
346 /**
347 * Add the live interval element i to the map for register r.
348 */
349 private void addToRegisterMap(Register r, LiveIntervalElement i) {
350 ArrayList<LiveIntervalElement> set = registerMap[r.getNumber()];
351 if (set == null) {
352 set = new ArrayList<LiveIntervalElement>(3);
353 registerMap[r.getNumber()] = set;
354 }
355 set.add(i);
356 }
357
358 /**
359 * Remove the live interval element i from the map for register r.
360 */
361 private void removeFromRegisterMap(Register r, LiveIntervalElement i) {
362 ArrayList<LiveIntervalElement> set = registerMap[r.getNumber()];
363 if (set != null) {
364 set.remove(i);
365 }
366 }
367
368 /**
369 * Compute summary (local) live variable analysis for a basic block, which
370 * is basically Gen and Kill information.
371 *
372 * @param bblock the basic block
373 * @param ir the governing if
374 * @see "Efficient and Precise Modeling of Exceptions for the
375 * Analysis of Java Programs" by Choi, Grove, Hind, Sarkar
376 * in ACM PASTE99 workshop (available at
377 * www.research.ibm.com/jalapeno)"
378 */
379 private void computeBlockGenAndKill(BasicBlock bblock, IR ir) {
380 if (VERBOSE) {
381 System.out.println(" --> Computing Gen/Kill for block " + bblock);
382 }
383
384 // Tells whether we've seen the first PEI
385 boolean seenFirstPEI = false;
386
387 // Because control flow may emanate from a potentially excepting
388 // instruction (PEI) out of the basic block, care must be taken
389 // when computing what can be killed by a basic block.
390 //
391 // S1: y =
392 // S2: <exception-raising inst>
393 // S3: x =
394 // For example in the block above, live variables coming from
395 // the normal exit of the block (i.e., after S3) can be killed
396 // by S1 or S3 (depending on the variable). However, live variables
397 // coming from the PEI edge (at S2) can only be killed by S1.
398 // Thus, when a block contains PEIs, we need to distinguish the
399 // kill sets. Namely, we need
400 // Kill_tot - what can be killed anywhere in the block
401 // Kill_n - what can be killed from PEI_n on up
402 // Kill_n-1 - what can be killed from PEI_n-1 on up
403 // ...
404 // Kill_1 - what can be killed from PEI_1 on up
405 // We would then compute In as follows
406 //
407 // In = Out_norm - Kill_tot (all vars entering from bottom are eligible
408 // to be killed)
409 // U Out_n - Kill_n
410 // U Out_n-1 - Kill_n-1
411 // ...
412 // U Out_1 - Kill_1
413 // U Gen
414 // where Out_n is the out information at PEI i, i.e., the IN information
415 // for whatever handlers may catch PEI i
416 // ...
417 // PEI 1
418 // ...
419 // PEI n-1
420 // ...
421 // PEI n
422 // ...
423 // If we conservatively assume all handlers for the block of interest
424 // can be reached by all PEIs in this block then the equation becomes
425 // In = (Out_norm - Kill_tot)
426 // U (Out_hand - Kill_n)
427 // U (Out_hand - Kill_n-1)
428 // ...
429 // U (Out_hand - Kill_1)
430 // U Gen
431 // where "Out_hand" is the union of the in sets for all handlers.
432 // Since Kill_i is a subset of Kill_j, for i < j, we can simplify to
433 // In = (Out_norm - Kill_tot)
434 // U (Out_hand - Kill_1) (1)
435 // U Gen
436 // Since kill_1 is a subset of kill_tot, we don't need the
437 // the parenthesis (and the intermediate set)
438 // If there are no handlers than (1) is empty and we don't need
439 // to compute Kill_1. We will take this approach for now.
440 // So for each block we will have at most 2 kill sets: Kill_tot and Kill_1
441 // This code finds the first PEI in the block
442
443 Instruction firstPEI = null;
444 if (bblock.canThrowExceptions()) {
445 for (Instruction inst = bblock.firstInstruction(); inst != bblock.lastInstruction(); inst =
446 inst.nextInstructionInCodeOrder()) {
447 if (inst.isPEI() && bblock.getApplicableExceptionalOut(inst).hasMoreElements()) {
448 firstPEI = inst;
449 // remember that this block has a PEI with a handler for use
450 // later in "processBlock"
451 bbLiveInfo[bblock.getNumber()].setContainsPEIWithHandler(true);
452 break;
453 }
454 }
455 }
456
457 // Get any uses from PHIs, which are in the successor blocks
458 getUsesFromPhis(bblock);
459
460 // Traverse instructions in reverse order within the basic block.
461 for (Instruction inst = bblock.lastInstruction(); inst != bblock.firstInstruction(); inst =
462 inst.prevInstructionInCodeOrder()) {
463
464 // traverse from defs to uses becauses uses happen after
465 // (in a backward sense) defs
466 OperandEnumeration defs = inst.getPureDefs();
467 while (defs.hasMoreElements()) {
468 Operand def = defs.next();
469 if (def instanceof RegisterOperand) {
470 RegisterOperand regOp = (RegisterOperand) def;
471
472 // Do we care about this reg?
473 if (isSkippableReg(regOp, ir)) {
474 continue;
475 }
476 TypeReference regType = regOp.getType();
477
478 // Because the summary we compute is used to propagate to other
479 // basic blocks, if a register is block local, we don't need to
480 // include it. It will be picked up later by local propagation phase.
481 if (regOp.getRegister().spansBasicBlock() && regType != null) {
482
483 // if it is a DEF we place it is the BBKillSet and remove it from
484 // the GEN set, (GEN should only contain upward-exposed uses,
485 // i.e., uses that are NOT dominated by a DEF).
486 // We don't need to worry about PEIs here because
487 // later instructions (traversing backwards like we are)
488 // will always dominate earlier instructions *of this block*
489 bbLiveInfo[bblock.getNumber()].BBKillSet().add(regOp);
490 bbLiveInfo[bblock.getNumber()].getGen().remove(regOp);
491
492 // However, if an exception can emanate from this basic block
493 // we are not guaranteed that all instructions will be executed
494 // in this block. We allow killing of instructions
495 // after the last (in a backwards sense) potential exception
496 // throwing statement. (PEI)
497 // If there are no PEIs in this block we don't bother to add
498 if (seenFirstPEI) {
499 bbLiveInfo[bblock.getNumber()].firstPEIKillSet().add(regOp);
500 }
501 }
502 }
503 }
504
505 // Now process the uses, unless this is a PHI operator
506 if (inst.operator() != PHI) {
507 for (OperandEnumeration uses = inst.getUses(); uses.hasMoreElements();) {
508 Operand use = uses.next();
509 if (use instanceof RegisterOperand) {
510 RegisterOperand regOp = (RegisterOperand) use;
511
512 // Do we care about this reg?
513 if (isSkippableReg(regOp, ir)) {
514 continue;
515 }
516
517 TypeReference regType = regOp.getType();
518
519 // Because the summary we compute is used to propagate to
520 // other basic blocks, if a register is block local,
521 // we don't need to include it. It will be picked up
522 // later by local propagation phase.
523 if (regOp.getRegister().spansBasicBlock() && regType != null) {
524 bbLiveInfo[bblock.getNumber()].getGen().add(regOp);
525 }
526 } // is RegOp
527 } // foreach use
528 } // not a PHI
529 // check whether the instruction we just processed is the first
530 // (last, thinking backwards) exception-raising instruction.
531 // If so, set the flag so we can start killing.
532 if (firstPEI == inst) {
533 seenFirstPEI = true;
534 }
535 } // foreach instruction in block
536 if (VERBOSE) {
537 System.out.println(" Gen: " + bbLiveInfo[bblock.getNumber()].getGen());
538 System.out.println(" Kill: " + bbLiveInfo[bblock.getNumber()].BBKillSet());
539 System.out.println(" 1st PEI Kill: " + bbLiveInfo[bblock.getNumber()].firstPEIKillSet());
540 System.out.println(" ---> Done computing Gen/Kill for block");
541 }
542 }
543
544 /**
545 * The rvals of phi nodes are logically uses in the phi's predecessor
546 * blocks, so here we collect phi rvals from the current block's
547 * successors into the gen set for this block, being careful to
548 * collect only the appropriate rval
549 *
550 * @param bblock the basic block of interest
551 *
552 * pre: Assumes the liveInfo array is allocated for this block
553 * post: May add to liveInfo for this block
554 */
555 private void getUsesFromPhis(BasicBlock bblock) {
556 Enumeration<BasicBlock> successors = bblock.getOut();
557 while (successors.hasMoreElements()) {
558 BasicBlock sb = successors.nextElement();
559 if (sb.isExit()) {
560 continue;
561 }
562
563 for (Instruction phi = sb.firstInstruction(); phi != sb.lastInstruction(); phi =
564 phi.nextInstructionInCodeOrder()) {
565 if (phi.operator() == PHI) {
566 for (int j = 0; j < Phi.getNumberOfValues(phi); j++) {
567 BasicBlockOperand bbop = Phi.getPred(phi, j);
568 if (bbop.block == bblock) {
569 Operand myRval = Phi.getValue(phi, j);
570 if (myRval instanceof RegisterOperand) {
571 RegisterOperand regOp = (RegisterOperand) myRval;
572 TypeReference regType = regOp.getType();
573 if (regOp.getRegister().spansBasicBlock() && regType != null) {
574 bbLiveInfo[bblock.getNumber()].getGen().add(regOp);
575 }
576 }
577 }
578 }
579 }
580 }
581 }
582 }
583
584 /**
585 * Compute the in set for this block given the out, gen, and kill set
586 * @param block the block of interest
587 * @param reuseCurrentSet whether we can reuse the "currentSet" or else
588 * clear it out and recompute the meet of our succs
589 * @param ir the governing ir
590 */
591 private boolean processBlock(BasicBlock block, boolean reuseCurrentSet, IR ir) {
592 if (VERBOSE) {
593 System.out.println(" *** processing block " + block + " # out edges: " + block.getNumberOfOut());
594 block.printExtended();
595 }
596
597 // We compute Gen and Kill the first time we process the block.
598 // This computation must happen early iun this method because it also computes
599 // summary information about the block (eg getContainsPEIWithHandler).
600 if (bbLiveInfo[block.getNumber()].BBKillSet() == null) {
601 bbLiveInfo[block.getNumber()].createKillAndGen();
602 computeBlockGenAndKill(block, ir);
603 }
604
605 // A summary of the IN sets of all exception handlers for the block
606 LiveSet exceptionBlockSummary = new LiveSet();
607
608 boolean blockHasHandlers = bbLiveInfo[block.getNumber()].getContainsPEIWithHandler();
609
610 // The computation of the Kill set takes into consideration exception
611 // semantics, i.e., that live information may flow into the middle
612 // of a basic block due to implicit edges at exception points.
613 // We keep 2 kill sets.
614 // BBKillSet() contains variables that are killed if the block
615 // is exited in the normal fashion
616 // firstPEIKillSet() contains variables that are definitely killed
617 // before the first PEI is executed.
618 // This set contains only variables that are definitely
619 // killed in this block despite the implicit exception edges.
620 //
621 if (!reuseCurrentSet) {
622 currentSet.clear();
623
624 // visit each successor, if it is a regular successor, add
625 // it to "currentSet". If it is a handler block, add it to
626 // ExceptionBlockSummary.
627 for (BasicBlockEnumeration bbEnum = block.getOut(); bbEnum.hasMoreElements();) {
628 BasicBlock succ = bbEnum.next();
629
630 // sometimes we may have a CFG edge to a handler, but no longer a
631 // PEI that can make the edge realizable. Thus, we have two
632 // conditions in the following test.
633 if (blockHasHandlers && succ.isExceptionHandlerBasicBlock()) {
634 exceptionBlockSummary.add(bbLiveInfo[succ.getNumber()].getIn());
635 } else {
636 currentSet.add(bbLiveInfo[succ.getNumber()].getIn());
637 }
638 }
639 }
640 if (VERBOSE) {
641 System.out.println("\t Before applying transfor function:");
642 System.out.println("\t currentSet: " + currentSet);
643 System.out.println("\t exceptionBlockSummary: " + exceptionBlockSummary);
644 }
645
646 // At this point, currentSet contains the union of our normal successors'
647 // IN sets.
648 // Compute: In = currentSet - BBKillSet
649 // U (exceptionBlockSummary - firstPEIKillSet) (1)
650 // U Gen
651 // Since firstPEIKillSet is a subset of BBKillSet, we don't need the
652 // the parenthesis (and the intermediate set)
653 //
654 // If there are no handlers than exceptionBlockSummary is empty and
655 // we don't need to perform line (1)
656
657 // currentSet = currentSet - BBKillSet
658 // first kill off variables that are killed anywhere in the block
659 currentSet.remove(bbLiveInfo[block.getNumber()].BBKillSet());
660 if (blockHasHandlers) {
661
662 // currentSet = currentSet U exceptionBlockSummary
663 // add in the IN sets for the handlers
664 currentSet.add(exceptionBlockSummary);
665
666 // currentSet = currentSet - firstPEIKillSet
667 // kill off variables that are definitely killed, i.e., killed before
668 // the first PEI
669 currentSet.remove(bbLiveInfo[block.getNumber()].firstPEIKillSet());
670 }
671
672 // currentSet = currentSet U gen
673 // add in the GEN set
674 currentSet.add(bbLiveInfo[block.getNumber()].getGen());
675
676 // since we have monotonicity, we can add currentSet to
677 // the previous In set. If it results in an addition we have
678 // a change and return true, otherwise return false.
679 if (bbLiveInfo[block.getNumber()].getIn().add(currentSet)) {
680 if (VERBOSE) {
681 System.out.println(" *** processBlock returning true, currentSet: " + currentSet);
682 }
683 return true;
684 } else {
685 if (VERBOSE) {
686 System.out.println(" *** processBlock returning false, currentSet: " + currentSet);
687 }
688 return false;
689 }
690 }
691
692 /**
693 * This method performs the last phase of the analysis, local propagation.
694 * It uses the results from the fixed point analysis to determine the
695 * local live information within a basic block.
696 *
697 * It walks the IR and, using the live information computed for each
698 * basic block, i.e., the results of the iterative solution, makes a single
699 * pass backward walk through the basic block, GENing and KILLing
700 * local information. This produces the set of live variables at each
701 * instruction.
702 *
703 * This information is saved into two data structures:
704 * - at all GC points, live references are recorded
705 * - at all instructions, live range information is recorded
706 *
707 * @param ir the IR
708 */
709 private void performLocalPropagation(IR ir, boolean createGCMaps) {
710 if (DEBUG) {
711 System.out.println(" .... starting local propagation\n");
712 }
713 Stack<MapElement> blockStack = null;
714 if (createGCMaps) {
715 // We want to add GC map entries in IR instruction order. However, we are
716 // visiting instructions in reverse order within a block. We solve this
717 // by pushing all additions to a local stack and pop (and add)
718 // the information to the GC map after the block has been processed.
719 blockStack = new Stack<MapElement>();
720 }
721 for (BasicBlock block = ir.firstBasicBlockInCodeOrder(); block != null; block =
722 block.nextBasicBlockInCodeOrder()) {
723 if (VERBOSE) {
724 System.out.print(" .... processing block # " + block.getNumber() + " ...");
725 }
726
727 // This set will hold the live variables for the current
728 // instruction. It is initialized from the "In" set of the block's
729 // successors and updated during the walk up the basic block.
730 LiveSet local = new LiveSet();
731
732 // The union of the IN sets of all exception blocks that can
733 // be reached (directly) from this block
734 LiveSet exceptionBlockSummary = new LiveSet();
735
736 // Create the out set by unioning the successors' in sets.
737 // During this processing we should NOT include exception-catching
738 // blocks, but instead remember them for use at exception-raising
739 // statements in this block
740 for (BasicBlockEnumeration bbEnum = block.getOut(); bbEnum.hasMoreElements();) {
741 BasicBlock succ = bbEnum.next();
742 if (succ.isExceptionHandlerBasicBlock()) {
743 exceptionBlockSummary.add(bbLiveInfo[succ.getNumber()].getIn());
744 } else {
745 local.add(bbLiveInfo[succ.getNumber()].getIn());
746 }
747 }
748 if (VERBOSE) {
749 System.out.println(" Completed succ walk. exceptionBlockSummary: " +
750 exceptionBlockSummary +
751 "\n local: " +
752 local);
753 }
754
755 // initialize live range for this block
756 block.initializeLiveRange();
757
758 // For each item in "local", create live interval info for this block.
759 LiveInterval.createEndLiveRange(local, block, null);
760
761 // Process the block, an instruction at a time.
762 for (Instruction inst = block.lastInstruction(); inst != block.firstInstruction(); inst =
763 inst.prevInstructionInCodeOrder()) {
764 if (VERBOSE) {
765 System.out.println("Processing: " + inst);
766 }
767
768 // If this instruction can raise an exception, then the catch
769 // block can be a direct successor to it
770 // To compensate this, we must first add in the live information
771 // for all such blocks, which we computed above and stored
772 // in "exceptionBlockSummary"
773 if (inst.isPEI()) {
774 local.add(exceptionBlockSummary);
775
776 // For each item in "exceptionBlockSummary", create live interval
777 // info for this block.
778 LiveInterval.createEndLiveRange(exceptionBlockSummary, block, inst);
779 }
780
781 // compute In set for this instruction & GC point info
782 // traverse from defs to uses, do "kill" then "gen" (backwards analysis)
783 // Def loop
784 for (OperandEnumeration defs = inst.getPureDefs(); defs.hasMoreElements();) {
785 Operand op = defs.next();
786 if (op instanceof RegisterOperand) {
787 RegisterOperand regOp = (RegisterOperand) op;
788 // Currently, clients of live information do not need to know
789 // about validation reges. (Reg Alloc cares about physical regs.)
790 if (isSkippableReg(regOp, ir)) {
791 continue;
792 }
793 if (regOp.getType() != null) {
794 // process the def as a kill
795 local.remove(regOp);
796 if (VERBOSE) {
797 System.out.println(" Killing: " + regOp + "\n local: " + local);
798 }
799
800 // mark this instruction as the start of the live range for reg
801 LiveInterval.setStartLiveRange(regOp.getRegister(), inst, block);
802 }
803 } // if operand is a Register
804 } // defs
805
806 // GC Map Code:
807 //
808 // Now that we have processed all of the defs, if any, we check
809 // if the instruction is a potential GC point, insert it into
810 // the map.
811 // We do this after processing the defs (remember, this is a backward
812 // analysis) because the GC will occur (at least in the case of calls)
813 // after the uses have occurred (in the forward sense). Thus, we
814 // don't yet factor in the uses for this instruction.
815 // For a statement like "x = y", we are capturing the program point
816 // "in the middle", i.e., during the execution, after the y has been
817 // fetched, but before the x has been defined.
818
819 // Above observation is not true for an OSR instruction. The current
820 // design of the OSR instruction requires the compiler build a GC map
821 // for variables used by the instruction.
822 // Otherwise, the compiler generates an empty gc map for the
823 // instruction. This results run away references if GC happens
824 // when a thread is being OSRed.
825 //
826 // TODO: better design of yieldpoint_osr instruction.
827 // -- Feng July 15, 2003
828 if (createGCMaps && !OsrPoint.conforms(inst) && inst.isGCPoint()) {
829 // make deep copy (and translate to regList) because we reuse
830 // local above.
831 // NOTE: this translation does some screening, see GCIRMap.java
832 List<RegSpillListElement> regList = map.createDU(local);
833 blockStack.push(new MapElement(inst, regList));
834 if (VERBOSE) { System.out.println("SAVING GC Map"); }
835 } // is GC instruction, and map not already made
836
837 // now process the uses
838 for (OperandEnumeration uses = inst.getUses(); uses.hasMoreElements();) {
839 Operand op = uses.next();
840 if (op instanceof RegisterOperand) {
841 RegisterOperand regOp = (RegisterOperand) op;
842 // Do we care about this reg?
843 if (isSkippableReg(regOp, ir)) {
844 continue;
845 }
846 TypeReference regType = regOp.getType();
847 // see Def loop comment about magics
848 if (regType != null) {
849 // process the use as a gen
850 local.add(regOp);
851 if (VERBOSE) {
852 System.out.println(" Gen-ing: " + regOp);
853 System.out.println("local: " + local);
854 }
855 // mark this instruction as the end of the live range for reg
856 LiveInterval.createEndLiveRange(regOp.getRegister(), block, inst);
857 }
858 } // if operand is a Register
859 } // uses
860
861 if (createGCMaps && OsrPoint.conforms(inst)) {
862 // delayed gc map generation for Osr instruction,
863 // see comments before processing uses -- Feng, July 15, 2003
864 List<RegSpillListElement> regList = map.createDU(local);
865 blockStack.push(new MapElement(inst, regList));
866
867 // collect osr info using live set
868 collectOsrInfo(inst, local);
869 }
870 } // end instruction loop
871
872 // The register allocator prefers that any registers that are live
873 // on entry be listed first. This call makes it so.
874 LiveInterval.moveUpwardExposedRegsToFront(block);
875 if (createGCMaps) {
876 // empty the stack, insert the information into the map
877 while (!blockStack.isEmpty()) {
878 MapElement elem = blockStack.pop();
879 map.insert(elem.getInst(), elem.getList());
880 }
881 }
882
883 if (storeLiveAtHandlers && block.isExceptionHandlerBasicBlock()) {
884 ExceptionHandlerBasicBlock handlerBlock = (ExceptionHandlerBasicBlock) block;
885
886 // use local because we need to get a fresh one anyway.
887 handlerBlock.setLiveSet(local);
888 local = null;
889 } else {
890
891 // clear the local set for the next block
892 local.clear();
893 }
894 } // end basic block for loop
895 if (DEBUG) {
896 System.out.println(" .... completed local propagation\n");
897 }
898 }
899
900 /**
901 * Should this register be included in the liveness solution?
902 *
903 * @param regOp the register operand to consider skipping
904 * @param ir the governing ir
905 * @return whether the register should be skipped, i.e., not be
906 * present in the liveness solution
907 */
908 private boolean isSkippableReg(RegisterOperand regOp, IR ir) {
909 // The old test would exclude all physical registers. However,
910 // register allocation needs to know about physical registers, except
911 // for the ones listed below. Such regs are inserted in the IR
912 // during call expansion.
913 return regOp.getRegister().isExcludedLiveA() || (regOp.getRegister().isValidation() && skipGuards);
914 }
915
916 /**
917 * Just a helper method to encapsulate the optional debugging info
918 * that is performed at the beginning of the perform method
919 * @param ir the IR
920 * @param createGCMaps are we creating GC maps?
921 * @param dumpFixedPointResults debug info
922 * @param dumpFinalMaps debug info
923 * @param dumpFinalLiveIntervals debug info
924 */
925 private void debugBegining(IR ir, boolean createGCMaps, boolean dumpFixedPointResults, boolean dumpFinalMaps, boolean dumpFinalLiveIntervals) {
926 if (dumpFixedPointResults || dumpFinalMaps || dumpFinalLiveIntervals) {
927 System.out.print("\n ====> Performing liveness analysis ");
928 if (createGCMaps) {
929 System.out.print("and GC Maps ");
930 }
931 System.out.println("for method: " + ir.method.getName() + " in class: " + ir.method.getDeclaringClass() + "\n");
932 System.out.println(" method has " + ir.cfg.numberOfNodes() + " basic blocks");
933 }
934 if (dumpFinalMaps) {
935 System.out.println("**** START OF IR for method: " +
936 ir.method.getName() +
937 " in class: " +
938 ir.method.getDeclaringClass());
939 ir.printInstructions();
940 System.out.println("**** END OF IR INSTRUCTION DUMP ****");
941 }
942 }
943
944 /**
945 * Just a helper method to encapsulate the optional debugging info
946 * that is performed after the global propagation step of "perform"
947 *
948 * @param ir the IR
949 * @param dumpFixedPointResults debug info
950 * @param dumpFinalMaps debug info
951 * @param dumpFinalLiveIntervals debug info
952 */
953 private void debugPostGlobal(IR ir, boolean dumpFixedPointResults, boolean dumpFinalMaps, boolean dumpFinalLiveIntervals) {
954 if (DEBUG) {
955 System.out.println(" .... Completed global live computation ....");
956 if (VERBOSE) {
957 // Print the basic blocks
958 System.out.println(" .... CFG:");
959 System.out.println(ir.cfg);
960 }
961 }
962 if (dumpFixedPointResults) {
963 printFixedPointResults(ir);
964 }
965 }
966
967 /**
968 * Prints the results of the fixed point computation.
969 * (Use printFinalMaps for the final GC map)
970 * @param ir the IR
971 */
972 private void printFixedPointResults(IR ir) {
973 System.out.println("\n ***** Fixed point results for IR-based GC Maps for " +
974 ir.method.getDeclaringClass() +
975 "." +
976 ir.method.getName());
977 int length = bbLiveInfo.length;
978 for (int i = 0; i < length; i++) {
979 System.out.println("Live Info for Block #" + i);
980 System.out.println(bbLiveInfo[i]);
981 }
982 }
983
984 /**
985 * Prints the final maps
986 * @param ir
987 */
988 private void printFinalMaps(IR ir) {
989 System.out.println("\n =-=-=-=-=- Final IR-based GC Maps for " +
990 ir.method.getDeclaringClass() +
991 "." +
992 ir.method.getName());
993 map.dump();
994 System.out.println(" =-=-=-=-=- End Final IR-based GC Maps\n");
995 }
996
997 /**
998 * Prints the Final Live Intervals
999 * @param ir the IR
1000 */
1001 private void printFinalLiveIntervals(IR ir) {
1002 ir.printInstructions();
1003 System.out.println("\n *+*+*+*+*+ Final Live Intervals for " +
1004 ir.method.getDeclaringClass() +
1005 "." +
1006 ir.method.getName());
1007 for (BasicBlock block = ir.firstBasicBlockInCodeOrder(); block != null; block =
1008 block.nextBasicBlockInCodeOrder()) {
1009 LiveInterval.printLiveIntervalList(block);
1010 }
1011 System.out.println(" *+*+*+*+*+ End Final Live Intervals\n");
1012 }
1013
1014 /**
1015 * REturns the live information for a particular block
1016 * @param bb the basic block of interest
1017 * @return the live information for the block
1018 */
1019 public BBLiveElement getLiveInfo(BasicBlock bb) {
1020 return bbLiveInfo[bb.getNumber()];
1021 }
1022
1023 /**
1024 * Return the set of registers that are live on the control-flow edge
1025 * basic block bb1 to basic block bb2
1026 */
1027 public HashSet<Register> getLiveRegistersOnEdge(BasicBlock bb1, BasicBlock bb2) {
1028 HashSet<Register> s1 = getLiveRegistersOnExit(bb1);
1029 HashSet<Register> s2 = getLiveRegistersOnEntry(bb2);
1030 s1.retainAll(s2);
1031 return s1;
1032 }
1033
1034 /**
1035 * Return the set of registers that are live across a basic block, and who
1036 * are live after the basic block exit.
1037 */
1038 HashSet<Register> getLiveRegistersOnExit(BasicBlock bb) {
1039 HashSet<Register> result = new HashSet<Register>(10);
1040 for (Enumeration<LiveIntervalElement> e = bb.enumerateLiveIntervals(); e.hasMoreElements();) {
1041 LiveIntervalElement lie = e.nextElement();
1042 Instruction end = lie.getEnd();
1043 if (end == null) result.add(lie.getRegister());
1044 }
1045 return result;
1046 }
1047
1048 /**
1049 * Return the set of registers that are live across a basic block, and who
1050 * are live before the basic block entry.
1051 */
1052 HashSet<Register> getLiveRegistersOnEntry(BasicBlock bb) {
1053 HashSet<Register> result = new HashSet<Register>(10);
1054 for (Enumeration<LiveIntervalElement> e = bb.enumerateLiveIntervals(); e.hasMoreElements();) {
1055 LiveIntervalElement lie = e.nextElement();
1056 Instruction begin = lie.getBegin();
1057 if (begin == null) result.add(lie.getRegister());
1058 }
1059 return result;
1060 }
1061
1062 // A simple class used to store live info
1063 public static final class BBLiveElement {
1064 private LiveSet gen;
1065 private LiveSet BBKillSet;
1066 private LiveSet firstPEIKillSet;
1067 private final LiveSet in;
1068 private boolean containsPEIWithHandler = false;
1069
1070 /**
1071 * The constructor
1072 */
1073 BBLiveElement() {
1074 in = new LiveSet();
1075 }
1076
1077 /**
1078 * Returns the kill set
1079 * @return the Kill set for this block
1080 */
1081 public LiveSet BBKillSet() {
1082 return BBKillSet;
1083 }
1084
1085 /**
1086 * Returns the first PEI kill set, i.e., the Kill set up to the first PEI
1087 * @return the Kill set up to the first PEI
1088 */
1089 public LiveSet firstPEIKillSet() {
1090 return firstPEIKillSet;
1091 }
1092
1093 /**
1094 * Returns the Gen set
1095 * @return the Gen set for this block
1096 */
1097 public LiveSet getGen() {
1098 return gen;
1099 }
1100
1101 /**
1102 * Returns the In set
1103 * @return the In set for this block
1104 */
1105 public LiveSet getIn() {
1106 return in;
1107 }
1108
1109 /**
1110 * Returns whether this block has a PEI with a handler in this method
1111 * @return whether this block has a PEI with a handler in this method
1112 */
1113 public boolean getContainsPEIWithHandler() {
1114 return containsPEIWithHandler;
1115 }
1116
1117 /**
1118 * @param value whether this block has a PEI with a handler in this method
1119 */
1120 public void setContainsPEIWithHandler(boolean value) {
1121 containsPEIWithHandler = value;
1122 }
1123
1124 /**
1125 * creates (allocates) the Gen and Kill Sets
1126 */
1127 public void createKillAndGen() {
1128 BBKillSet = new LiveSet();
1129 firstPEIKillSet = new LiveSet();
1130 gen = new LiveSet();
1131 }
1132
1133 /**
1134 * creates a string representation of this object
1135 * @return string representation of this object
1136 */
1137 public String toString() {
1138 StringBuilder buf = new StringBuilder("");
1139 buf.append(" Gen: ").append(gen).append("\n");
1140 buf.append(" BB Kill: ").append(BBKillSet).append("\n");
1141 buf.append(" first PEI Kill: ").append(firstPEIKillSet).append("\n");
1142 buf.append(" In: ").append(in).append("\n");
1143 return buf.toString();
1144 }
1145
1146 }
1147
1148 /**
1149 * A simple class used just in this file when creating GC maps
1150 */
1151 static final class MapElement {
1152
1153 private final Instruction inst;
1154 private final List<RegSpillListElement> list;
1155
1156 /**
1157 * constructor
1158 * @param inst
1159 * @param list
1160 */
1161 public MapElement(Instruction inst, List<RegSpillListElement> list) {
1162 this.inst = inst;
1163 this.list = list;
1164 }
1165
1166 /**
1167 * returns the instruction
1168 * @return the instruction
1169 */
1170 public Instruction getInst() {
1171 return inst;
1172 }
1173
1174 /**
1175 * returns the list
1176 * @return the list
1177 */
1178 public List<RegSpillListElement> getList() {
1179 return list;
1180 }
1181 }
1182
1183 /* collect osr info according to live information */
1184 private void collectOsrInfo(Instruction inst, LiveSet lives) {
1185 // create an entry to the OSRIRMap, order: callee => caller
1186 LinkedList<MethodVariables> mvarList = new LinkedList<MethodVariables>();
1187
1188 // get the type info for locals and stacks
1189 InlinedOsrTypeInfoOperand typeInfo = OsrPoint.getInlinedTypeInfo(inst);
1190
1191 /* iterator over type info and create LocalRegTuple
1192 * for each variable.
1193 * NOTE: we do not process LONG type register operand here,
1194 * which was splitted in BURS.
1195 */
1196 byte[][] ltypes = typeInfo.localTypeCodes;
1197 byte[][] stypes = typeInfo.stackTypeCodes;
1198
1199 int nummeth = typeInfo.methodids.length;
1200
1201 int elm_idx = 0;
1202 int snd_long_idx = typeInfo.validOps;
1203 for (int midx = 0; midx < nummeth; midx++) {
1204
1205 LinkedList<LocalRegPair> tupleList = new LinkedList<LocalRegPair>();
1206
1207 byte[] ls = ltypes[midx];
1208 byte[] ss = stypes[midx];
1209
1210 /* record maps for local variables, skip dead ones */
1211 for (int i = 0, n = ls.length; i < n; i++) {
1212 if (ls[i] != VoidTypeCode) {
1213 // check liveness
1214 Operand op = OsrPoint.getElement(inst, elm_idx++);
1215 LocalRegPair tuple = new LocalRegPair(OSRConstants.LOCAL, i, ls[i], op);
1216 // put it in the list
1217 tupleList.add(tuple);
1218
1219 // get another half of a long type operand
1220 if (VM.BuildFor32Addr && (ls[i] == LongTypeCode)) {
1221 Operand other_op = OsrPoint.getElement(inst, snd_long_idx++);
1222 tuple._otherHalf = new LocalRegPair(OSRConstants.LOCAL, i, ls[i], other_op);
1223
1224 }
1225 }
1226 }
1227
1228 /* record maps for stack slots */
1229 for (int i = 0, n = ss.length; i < n; i++) {
1230 if (ss[i] != VoidTypeCode) {
1231 LocalRegPair tuple =
1232 new LocalRegPair(OSRConstants.STACK, i, ss[i], OsrPoint.getElement(inst, elm_idx++));
1233
1234 tupleList.add(tuple);
1235
1236 if (VM.BuildFor32Addr && (ss[i] == LongTypeCode)) {
1237 tuple._otherHalf =
1238 new LocalRegPair(OSRConstants.STACK, i, ss[i], OsrPoint.getElement(inst, snd_long_idx++));
1239 }
1240 }
1241 }
1242
1243 // create MethodVariables
1244 MethodVariables mvar = new MethodVariables(typeInfo.methodids[midx], typeInfo.bcindexes[midx], tupleList);
1245 mvarList.add(mvar);
1246 }
1247
1248 // put the method variables for this OSR in the osrMap, encoding later.
1249 osrMap.insertFirst(inst, mvarList);
1250 }
1251 }
1252
1253 // Previously we used to be concerned that we didn't lose any
1254 // precision due to imprecise modeling of exceptions.
1255 // However, the troublesome situation cannot occur in Java
1256 // because the Java SPEC forces the compiler to declare a variable
1257 // as uninitialized.
1258 //
1259 // Conside the following ***ILLEGAL*** example:
1260 //
1261 // static void main(String arg[]) {
1262 // Object x;
1263 // try {
1264 // foo();
1265 // x = null;
1266 // bar();
1267 // }
1268 // catch (FooException e) {
1269 // }
1270 //
1271 // catch (BarException e) {
1272 // Object a = x;
1273 // }
1274 // }
1275 //
1276 // Here x is live in the Bar catch block, but not above the assignment
1277 // in the try block. Recall that we only kill off values coming from
1278 // catch blocks if they are in the first PEI region (above the call
1279 // to foo). Thus, our analysis will conservatively record that x
1280 // is live above the assignment.
1281 //
1282 // However, the Java SPEC requires compilers to state that x is uninitialized
1283 // here, even though it isn't. Thus, this scenario cannot occur.
1284 // Basically, every variable used in a catch block needs to be defined
1285 // before the TRY statement. (The SPEC doesn't explicitly state this, but
1286 // on page 398 (Sec 16.2.13) it says that
1287 // every variable used in a *finally* block needs to be defined
1288 // before the TRY statement, which is even more restrictive.
1289 // Bottomline: losing precision is not a concern!
1290