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