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.ssa;
014
015 import static org.jikesrvm.compilers.opt.driver.OptConstants.SSA_SYNTH_BCI;
016 import static org.jikesrvm.compilers.opt.ir.Operators.PHI;
017 import static org.jikesrvm.compilers.opt.ir.Operators.READ_CEILING;
018 import static org.jikesrvm.compilers.opt.ir.Operators.UNINT_BEGIN_opcode;
019 import static org.jikesrvm.compilers.opt.ir.Operators.UNINT_END_opcode;
020 import static org.jikesrvm.compilers.opt.ir.Operators.WRITE_FLOOR;
021
022 import java.lang.reflect.Constructor;
023 import java.util.Enumeration;
024 import java.util.HashMap;
025 import java.util.HashSet;
026 import java.util.Iterator;
027 import java.util.Set;
028 import java.util.Stack;
029
030 import org.jikesrvm.VM;
031 import org.jikesrvm.classloader.TypeReference;
032 import org.jikesrvm.compilers.opt.ClassLoaderProxy;
033 import org.jikesrvm.compilers.opt.DefUse;
034 import org.jikesrvm.compilers.opt.OptOptions;
035 import org.jikesrvm.compilers.opt.OptimizingCompilerException;
036 import org.jikesrvm.compilers.opt.controlflow.DominanceFrontier;
037 import org.jikesrvm.compilers.opt.controlflow.DominatorTreeNode;
038 import org.jikesrvm.compilers.opt.driver.CompilerPhase;
039 import org.jikesrvm.compilers.opt.ir.Athrow;
040 import org.jikesrvm.compilers.opt.ir.Attempt;
041 import org.jikesrvm.compilers.opt.ir.BBend;
042 import org.jikesrvm.compilers.opt.ir.BasicBlock;
043 import org.jikesrvm.compilers.opt.ir.BasicBlockEnumeration;
044 import org.jikesrvm.compilers.opt.ir.CacheOp;
045 import org.jikesrvm.compilers.opt.ir.Call;
046 import org.jikesrvm.compilers.opt.ir.IR;
047 import org.jikesrvm.compilers.opt.ir.Instruction;
048 import org.jikesrvm.compilers.opt.ir.InstructionEnumeration;
049 import org.jikesrvm.compilers.opt.ir.Label;
050 import org.jikesrvm.compilers.opt.ir.MonitorOp;
051 import org.jikesrvm.compilers.opt.ir.OperandEnumeration;
052 import org.jikesrvm.compilers.opt.ir.Phi;
053 import org.jikesrvm.compilers.opt.ir.Prepare;
054 import org.jikesrvm.compilers.opt.ir.Register;
055 import org.jikesrvm.compilers.opt.ir.ResultCarrier;
056 import org.jikesrvm.compilers.opt.ir.Return;
057 import org.jikesrvm.compilers.opt.ir.operand.BasicBlockOperand;
058 import org.jikesrvm.compilers.opt.ir.operand.HeapOperand;
059 import org.jikesrvm.compilers.opt.ir.operand.Operand;
060 import org.jikesrvm.compilers.opt.ir.operand.RegisterOperand;
061 import org.jikesrvm.compilers.opt.ir.operand.UnreachableOperand;
062 import org.jikesrvm.compilers.opt.liveness.LiveAnalysis;
063 import org.jikesrvm.compilers.opt.liveness.LiveSet;
064 import org.jikesrvm.compilers.opt.util.TreeNode;
065 import org.jikesrvm.util.BitVector;
066 import org.jikesrvm.util.Pair;
067
068 /**
069 * This compiler phase constructs SSA form.
070 *
071 * <p> This module constructs SSA according to the SSA properties defined
072 * in </code> IR.desiredSSAOptions </code>. See <code> SSAOptions
073 * </code> for more details on supported options for SSA construction.
074 *
075 * <p>The SSA construction algorithm is the classic dominance frontier
076 * based algorithm from Cytron et al.'s 1991 TOPLAS paper.
077 *
078 * <p> See our SAS 2000 paper
079 * <a href="http://www.research.ibm.com/jalapeno/publication.html#sas00">
080 * Unified Analysis of Arrays and Object References in Strongly Typed
081 * Languages </a> for an overview of Array SSA form. More implementation
082 * details are documented in {@link SSA <code> SSA.java</code>}.
083 *
084 * @see SSA
085 * @see SSAOptions
086 * @see org.jikesrvm.compilers.opt.controlflow.LTDominators
087 */
088 public class EnterSSA extends CompilerPhase {
089 /**
090 * flag to optionally print verbose debugging messages
091 */
092 static final boolean DEBUG = false;
093
094 /**
095 * The governing IR
096 */
097 private IR ir;
098
099 /**
100 * Cached results of liveness analysis
101 */
102 private LiveAnalysis live;
103
104 /**
105 * A set of registers determined to span basic blocks
106 */
107 private HashSet<Register> nonLocalRegisters;
108
109 /**
110 * The set of scalar phi functions inserted
111 */
112 private final HashSet<Instruction> scalarPhis = new HashSet<Instruction>();
113
114 /**
115 * For each basic block, the number of predecessors that have been
116 * processed.
117 */
118 private int[] numPredProcessed;
119
120 /**
121 * Should this phase be performed under a guiding set of compiler
122 * options?
123 *
124 * @param options the controlling compiler options
125 * @return true iff SSA is enabled under the options
126 */
127 public final boolean shouldPerform(OptOptions options) {
128 return options.SSA;
129 }
130
131 /**
132 * Constructor for this compiler phase
133 */
134 private static final Constructor<CompilerPhase> constructor = getCompilerPhaseConstructor(EnterSSA.class);
135
136 /**
137 * Get a constructor object for this compiler phase
138 * @return compiler phase constructor
139 */
140 public Constructor<CompilerPhase> getClassConstructor() {
141 return constructor;
142 }
143
144 /**
145 * Return a string identifying this compiler phase.
146 * @return "Enter SSA"
147 */
148 public final String getName() {
149 return "Enter SSA";
150 }
151
152 /**
153 * Should the IR be printed either before or after performing this phase?
154 *
155 * @param options controlling compiler options
156 * @param before true iff querying before the phase
157 * @return true or false
158 */
159 public final boolean printingEnabled(OptOptions options, boolean before) {
160 return false;
161 }
162
163 /**
164 * Construct SSA form to satisfy the desired options in ir.desiredSSAOptions.
165 * This module is lazy; if the actual SSA options satisfy the desired options,
166 * then do nothing.
167 *
168 * @param ir the governing IR
169 */
170 public final void perform(IR ir) {
171
172 // Exit if we don't have to recompute SSA.
173 if (ir.desiredSSAOptions.getAbort()) return;
174 if (ir.actualSSAOptions != null) {
175 if (ir.actualSSAOptions.satisfies(ir.desiredSSAOptions)) {
176 return;
177 }
178 }
179 this.ir = ir;
180 boolean scalarsOnly = ir.desiredSSAOptions.getScalarsOnly();
181 boolean backwards = ir.desiredSSAOptions.getBackwards();
182 Set<Object> heapTypes = ir.desiredSSAOptions.getHeapTypes();
183 boolean insertUsePhis = ir.desiredSSAOptions.getInsertUsePhis();
184 boolean insertPEIDeps = ir.desiredSSAOptions.getInsertPEIDeps();
185 boolean excludeGuards = ir.desiredSSAOptions.getExcludeGuards();
186
187 // make sure the dominator computation completed successfully
188 if (!ir.HIRInfo.dominatorsAreComputed) {
189 throw new OptimizingCompilerException("Need dominators for SSA");
190 }
191 // reset SSA dictionary information
192 ir.HIRInfo.dictionary = new SSADictionary(null, true, false, ir);
193 // initialize as needed for SSA options
194 prepare();
195 // work around problem with PEI-generated values and handlers
196 if (true /* ir.options.UNFACTOR_FOR_SSA */) {
197 patchPEIgeneratedValues();
198 }
199 if (ir.options.PRINT_SSA) {
200 SSA.printInstructions(ir);
201 }
202 computeSSA(ir, scalarsOnly, backwards, heapTypes, insertUsePhis, insertPEIDeps, excludeGuards);
203 // reset the SSAOptions
204 ir.actualSSAOptions = new SSAOptions();
205 ir.actualSSAOptions.setScalarsOnly(scalarsOnly);
206 ir.actualSSAOptions.setBackwards(backwards);
207 ir.actualSSAOptions.setHeapTypes(heapTypes);
208 ir.actualSSAOptions.setInsertUsePhis(insertUsePhis);
209 ir.actualSSAOptions.setInsertPEIDeps(insertPEIDeps);
210 ir.actualSSAOptions.setExcludeGuards(excludeGuards);
211 ir.actualSSAOptions.setScalarValid(true);
212 ir.actualSSAOptions.setHeapValid(!scalarsOnly);
213 }
214
215 /**
216 * Perform some calculations to prepare for SSA construction.
217 * <ul>
218 * <li> If using pruned SSA, compute liveness.
219 * <li> If using semi-pruned SSA, compute non-local registers
220 * </ul>
221 */
222 private void prepare() {
223 live = new LiveAnalysis(false, // don't create GC maps
224 true, // skip (final) local propagation step
225 // of live analysis
226 false, // don't store live at handlers
227 ir.desiredSSAOptions.getExcludeGuards());
228 // don't skip guards
229 live.perform(ir);
230 }
231
232 /**
233 * Pass through the IR and calculate which registers are not
234 * local to a basic block. Store the result in the <code> nonLocalRegisters
235 * </code> field.
236 */
237 @SuppressWarnings("unused")
238 private void computeNonLocals() {
239 nonLocalRegisters = new HashSet<Register>(20);
240 BasicBlockEnumeration blocks = ir.getBasicBlocks();
241 while (blocks.hasMoreElements()) {
242 HashSet<Register> killed = new HashSet<Register>(5);
243 BasicBlock block = blocks.next();
244 InstructionEnumeration instrs = block.forwardRealInstrEnumerator();
245 while (instrs.hasMoreElements()) {
246 Instruction instr = instrs.next();
247 OperandEnumeration uses = instr.getUses();
248 while (uses.hasMoreElements()) {
249 Operand op = uses.next();
250 if (op instanceof RegisterOperand) {
251 if (!killed.contains(op.asRegister().getRegister())) {
252 nonLocalRegisters.add(op.asRegister().getRegister());
253 }
254 }
255 }
256 OperandEnumeration defs = instr.getDefs();
257 while (defs.hasMoreElements()) {
258 Operand op = defs.next();
259 if (op instanceof RegisterOperand) {
260 killed.add(op.asRegister().getRegister());
261 }
262 }
263 }
264 }
265 }
266
267 /**
268 * Work around some problems with PEI-generated values and
269 * handlers. Namely, if a PEI has a return value, rename the
270 * result register before and after the PEI in order to reflect the fact
271 * that the PEI may not actually assign the result register.
272 */
273 private void patchPEIgeneratedValues() {
274 // this only applies if there are exception handlers
275 if (!ir.hasReachableExceptionHandlers()) return;
276
277 HashSet<Pair<BasicBlock, RegisterOperand>> needed = new HashSet<Pair<BasicBlock,RegisterOperand>>(4);
278 BasicBlockEnumeration blocks = ir.getBasicBlocks();
279 while (blocks.hasMoreElements()) {
280 BasicBlock block = blocks.next();
281 if (block.getExceptionalOut().hasMoreElements()) {
282 Instruction pei = block.lastRealInstruction();
283 if (pei != null && pei.isPEI() && ResultCarrier.conforms(pei)) {
284 boolean copyNeeded = false;
285 RegisterOperand v = ResultCarrier.getResult(pei);
286 // void calls and the like... :(
287 if (v != null) {
288 Register orig = v.getRegister();
289 {
290 BasicBlockEnumeration out = block.getApplicableExceptionalOut(pei);
291 while (out.hasMoreElements()) {
292 BasicBlock exp = out.next();
293 LiveSet explive = live.getLiveInfo(exp).getIn();
294 if (explive.contains(orig)) {
295 copyNeeded = true;
296 break;
297 }
298 }
299 }
300 if (copyNeeded) {
301 BasicBlockEnumeration out = block.getApplicableExceptionalOut(pei);
302 while (out.hasMoreElements()) {
303 BasicBlock exp = out.next();
304 needed.add(new Pair<BasicBlock, RegisterOperand>(exp, v));
305 }
306 }
307 }
308 }
309 }
310 }
311 // having determine where copies should be inserted, now insert them.
312 if (!needed.isEmpty()) {
313 for (Pair<BasicBlock, RegisterOperand> copy : needed) {
314 BasicBlock inBlock = copy.first;
315 RegisterOperand registerOp = copy.second;
316 TypeReference type = registerOp.getType();
317 Register register = registerOp.getRegister();
318 Register temp = ir.regpool.getReg(register);
319 inBlock.prependInstruction(SSA.makeMoveInstruction(ir, register, temp, type));
320 BasicBlockEnumeration outBlocks = inBlock.getIn();
321 while (outBlocks.hasMoreElements()) {
322 BasicBlock outBlock = outBlocks.next();
323 Instruction x = SSA.makeMoveInstruction(ir, temp, register, type);
324 SSA.addAtEnd(ir, outBlock, x, true);
325 }
326 }
327 // Recompute liveness information. You might be tempted to incrementally
328 // update it, but it's tricky, so resist.....do the obvious, but easy thing!
329 prepare();
330 }
331 }
332
333 /**
334 * Calculate SSA form for an IR. This routine holds the guts of the
335 * transformation.
336 *
337 * @param ir the governing IR
338 * @param scalarsOnly should we compute SSA only for scalar variables?
339 * @param backwards If this is true, then every statement that
340 * can leave the procedure is considered to <em> use </em> every heap
341 * variable. This option is useful for backwards analyses such as dead
342 * store elimination.
343 * @param heapTypes If this variable is non-null, then heap array SSA
344 * form will restrict itself to this set of types. If this is null, build
345 * heap array SSA for all types.
346 * @param insertUsePhis Should we insert uphi functions for heap array
347 * SSA? ie., should we create a new name for each heap array at every use
348 * of the heap array? This option is useful for some analyses, such as
349 * our redundant load elimination algorithm.
350 * @param insertPEIDeps Should we model exceptions with an explicit
351 * heap variable for exception state? This option is useful for global
352 * code placement algorithms.
353 * @param excludeGuards Should we exclude guard registers from SSA?
354 */
355 private void computeSSA(IR ir, boolean scalarsOnly, boolean backwards, Set<Object> heapTypes,
356 boolean insertUsePhis, boolean insertPEIDeps, boolean excludeGuards) {
357 // if reads Kill. model this with uphis.
358 if (ir.options.READS_KILL) insertUsePhis = true;
359
360 // reset Array SSA information
361 if (!scalarsOnly) {
362 ir.HIRInfo.dictionary = new SSADictionary(heapTypes, insertUsePhis, insertPEIDeps, ir);
363 } else {
364 ir.HIRInfo.dictionary = new SSADictionary(null, insertUsePhis, insertPEIDeps, ir);
365 }
366 if (DEBUG) System.out.println("Computing register lists...");
367
368 // 1. re-compute the flow-insensitive isSSA flag for each register
369 DefUse.computeDU(ir);
370 DefUse.recomputeSSA(ir);
371
372 // 2. set up a mapping from symbolic register number to the
373 // register. !!TODO: factor this out and make it more
374 // useful.
375 Register[] symbolicRegisters = getSymbolicRegisters();
376
377 // 3. walk through the IR, and set up BitVectors representing the defs
378 // for each symbolic register (more efficient than using register
379 // lists)
380 if (DEBUG) System.out.println("Find defs for each register...");
381 BitVector[] defSets = getDefSets();
382
383 // 4. Insert phi functions for scalars
384 if (DEBUG) System.out.println("Insert phi functions...");
385 insertPhiFunctions(ir, defSets, symbolicRegisters, excludeGuards);
386
387 // 5. Insert heap variables into the Array SSA form
388 if (!scalarsOnly) {
389 insertHeapVariables(ir, backwards);
390 }
391 if (DEBUG) System.out.println("Before renaming...");
392 if (DEBUG) SSA.printInstructions(ir);
393 if (DEBUG) System.out.println("Renaming...");
394 renameSymbolicRegisters(symbolicRegisters);
395
396 if (!scalarsOnly) {
397 renameHeapVariables(ir);
398 }
399 if (DEBUG) System.out.println("SSA done.");
400 if (ir.options.PRINT_SSA) SSA.printInstructions(ir);
401 }
402
403 /**
404 * Insert heap variables needed for Array SSA form.
405 *
406 * @param ir the governing IR
407 * @param backwards if this is true, every statement that can leave the
408 * procedure <em> uses </em> every heap variable.
409 * This option is useful for backwards analyses
410 */
411 private void insertHeapVariables(IR ir, boolean backwards) {
412 // insert dphi functions where needed
413 registerHeapVariables(ir);
414
415 // insert heap defs and uses for CALL instructions
416 registerCalls(ir);
417
418 // register heap uses for instructions that can leave the procedure
419 if (backwards) {
420 registerExits(ir);
421 }
422
423 // insert phi funcions where needed
424 insertHeapPhiFunctions(ir);
425 }
426
427 /**
428 * Register every instruction that can leave this method with the
429 * implicit heap array SSA look aside structure.
430 *
431 * @param ir the governing IR
432 */
433 private void registerExits(IR ir) {
434 SSADictionary dictionary = ir.HIRInfo.dictionary;
435 for (BasicBlockEnumeration bbe = ir.getBasicBlocks(); bbe.hasMoreElements();) {
436 BasicBlock b = bbe.next();
437 for (InstructionEnumeration e = b.forwardInstrEnumerator(); e.hasMoreElements();) {
438 Instruction s = e.nextElement();
439 // we already handled calls in a previous pass.
440 if (Call.conforms(s)) {
441 continue;
442 }
443 if (Return.conforms(s) || Athrow.conforms(s) || s.isPEI()) {
444 dictionary.registerExit(s, b);
445 }
446 }
447 }
448 }
449
450 /**
451 * Register every CALL instruction in this method with the
452 * implicit heap array SSA look aside structure.
453 * Namely, mark that this instruction defs and uses <em> every </em>
454 * type of heap variable in the IR's SSA dictionary.
455 *
456 * @param ir the governing IR
457 */
458 private void registerCalls(IR ir) {
459 SSADictionary dictionary = ir.HIRInfo.dictionary;
460 for (BasicBlockEnumeration bbe = ir.getBasicBlocks(); bbe.hasMoreElements();) {
461 BasicBlock b = bbe.next();
462 for (InstructionEnumeration e = b.forwardInstrEnumerator(); e.hasMoreElements();) {
463 Instruction s = e.next();
464 boolean isSynch = (s.operator() == READ_CEILING) || (s.operator() == WRITE_FLOOR);
465 if (isSynch ||
466 Call.conforms(s) ||
467 MonitorOp.conforms(s) ||
468 Prepare.conforms(s) ||
469 Attempt.conforms(s) ||
470 CacheOp.conforms(s) ||
471 s.isDynamicLinkingPoint()) {
472 dictionary.registerUnknown(s, b);
473 }
474 }
475 }
476 }
477
478 /**
479 * Register every instruction in this method with the
480 * implicit heap array SSA lookaside structure.
481 *
482 * @param ir the governing IR
483 */
484 private void registerHeapVariables(IR ir) {
485 SSADictionary dictionary = ir.HIRInfo.dictionary;
486 for (BasicBlockEnumeration bbe = ir.getBasicBlocks(); bbe.hasMoreElements();) {
487 BasicBlock b = bbe.next();
488 for (InstructionEnumeration e = b.forwardInstrEnumerator(); e.hasMoreElements();) {
489 Instruction s = e.next();
490 if (s.isImplicitLoad() ||
491 s.isImplicitStore() ||
492 s.isAllocation() ||
493 Phi.conforms(s) ||
494 s.isPEI() ||
495 Label.conforms(s) ||
496 BBend.conforms(s) ||
497 s.operator.opcode == UNINT_BEGIN_opcode ||
498 s.operator.opcode == UNINT_END_opcode) {
499 dictionary.registerInstruction(s, b);
500 }
501 }
502 }
503 }
504
505 /**
506 * Insert phi functions for heap array SSA heap variables.
507 *
508 * @param ir the governing IR
509 */
510 private void insertHeapPhiFunctions(IR ir) {
511 Iterator<HeapVariable<Object>> e = ir.HIRInfo.dictionary.getHeapVariables();
512 while (e.hasNext()) {
513 HeapVariable<Object> H = e.next();
514
515 if (DEBUG) System.out.println("Inserting phis for Heap " + H);
516 if (DEBUG) System.out.println("Start iterated frontier...");
517
518 BitVector defH = H.getDefBlocks();
519 if (DEBUG) System.out.println(H + " DEFINED IN " + defH);
520
521 BitVector needsPhi = DominanceFrontier.
522 getIteratedDominanceFrontier(ir, defH);
523 if (DEBUG) System.out.println(H + " NEEDS PHI " + needsPhi);
524
525 if (DEBUG) System.out.println("Done.");
526 for (int b = 0; b < needsPhi.length(); b++) {
527 if (needsPhi.get(b)) {
528 BasicBlock bb = ir.getBasicBlock(b);
529 ir.HIRInfo.dictionary.createHeapPhiInstruction(bb, H);
530 }
531 }
532 }
533 }
534
535 /**
536 * Calculate the set of blocks that contain defs for each
537 * symbolic register in an IR. <em> Note: </em> This routine skips
538 * registers marked already having a single static
539 * definition, physical registers, and guard registeres.
540 *
541 * @return an array of BitVectors, where element <em>i</em> represents the
542 * basic blocks that contain defs for symbolic register <em>i</em>
543 */
544 private BitVector[] getDefSets() {
545 int nBlocks = ir.getMaxBasicBlockNumber();
546 BitVector[] result = new BitVector[ir.getNumberOfSymbolicRegisters()];
547
548 for (int i = 0; i < result.length; i++) {
549 result[i] = new BitVector(nBlocks + 1);
550 }
551
552 // loop over each basic block
553 for (BasicBlockEnumeration e = ir.getBasicBlocks(); e.hasMoreElements();) {
554 BasicBlock bb = e.next();
555 int bbNumber = bb.getNumber();
556 // visit each instruction in the basic block
557 for (InstructionEnumeration ie = bb.forwardInstrEnumerator(); ie.hasMoreElements();) {
558 Instruction s = ie.next();
559 // record each def in the instruction
560 // skip SSA defs
561 for (int j = 0; j < s.getNumberOfDefs(); j++) {
562 Operand operand = s.getOperand(j);
563 if (operand == null) continue;
564 if (!operand.isRegister()) continue;
565 if (operand.asRegister().getRegister().isSSA()) continue;
566 if (operand.asRegister().getRegister().isPhysical()) continue;
567
568 int reg = operand.asRegister().getRegister().getNumber();
569 result[reg].set(bbNumber);
570 }
571 }
572 }
573 return result;
574 }
575
576 /**
577 * Insert the necessary phi functions into an IR.
578 * <p> Algorithm:
579 * <p>For register r, let S be the set of all blocks that
580 * contain defs of r. Let D be the iterated dominance frontier
581 * of S. Each block in D needs a phi-function for r.
582 *
583 * <p> Special Java case: if node N dominates all defs of r, then N
584 * does not need a phi-function for r
585 *
586 * @param ir the governing IR
587 * @param defs defs[i] represents the basic blocks that define
588 * symbolic register i.
589 * @param symbolics symbolics[i] is symbolic register number i
590 */
591 private void insertPhiFunctions(IR ir, BitVector[] defs, Register[] symbolics, boolean excludeGuards) {
592 for (int r = 0; r < defs.length; r++) {
593 if (symbolics[r] == null) continue;
594 if (symbolics[r].isSSA()) continue;
595 if (symbolics[r].isPhysical()) continue;
596 if (excludeGuards && symbolics[r].isValidation()) continue;
597 if (DEBUG) System.out.println("Inserting phis for register " + r);
598 if (DEBUG) System.out.println("Start iterated frontier...");
599 BitVector needsPhi = DominanceFrontier.getIteratedDominanceFrontier(ir, defs[r]);
600 removePhisThatDominateAllDefs(needsPhi, ir, defs[r]);
601 if (DEBUG) System.out.println("Done.");
602
603 for (int b = 0; b < needsPhi.length(); b++) {
604 if (needsPhi.get(b)) {
605 BasicBlock bb = ir.getBasicBlock(b);
606 if (live.getLiveInfo(bb).getIn().contains(symbolics[r])) {
607 insertPhi(bb, symbolics[r]);
608 }
609 }
610 }
611 }
612 }
613
614 /**
615 * If node N dominates all defs of a register r, then N does
616 * not need a phi function for r; this function removes such
617 * nodes N from a Bit Set.
618 *
619 * @param needsPhi representation of set of nodes that
620 * need phi functions for a register r
621 * @param ir the governing IR
622 * @param defs set of nodes that define register r
623 */
624 private void removePhisThatDominateAllDefs(BitVector needsPhi, IR ir, BitVector defs) {
625 for (int i = 0; i < needsPhi.length(); i++) {
626 if (!needsPhi.get(i)) {
627 continue;
628 }
629 if (ir.HIRInfo.dominatorTree.dominates(i, defs)) {
630 needsPhi.clear(i);
631 }
632 }
633 }
634
635 /**
636 * Insert a phi function for a symbolic register at the head
637 * of a basic block.
638 *
639 * @param bb the basic block
640 * @param r the symbolic register that needs a phi function
641 */
642 private void insertPhi(BasicBlock bb, Register r) {
643 Instruction s = makePhiInstruction(r, bb);
644 bb.firstInstruction().insertAfter(s);
645 scalarPhis.add(s);
646 }
647
648 /**
649 * Create a phi-function instruction
650 *
651 * @param r the symbolic register
652 * @param bb the basic block holding the new phi function
653 * @return the instruction r = PHI null,null,..,null
654 */
655 private Instruction makePhiInstruction(Register r, BasicBlock bb) {
656 int n = bb.getNumberOfIn();
657 BasicBlockEnumeration in = bb.getIn();
658 TypeReference type = null;
659 Instruction s = Phi.create(PHI, new RegisterOperand(r, type), n);
660 for (int i = 0; i < n; i++) {
661 RegisterOperand junk = new RegisterOperand(r, type);
662 Phi.setValue(s, i, junk);
663 BasicBlock pred = in.next();
664 Phi.setPred(s, i, new BasicBlockOperand(pred));
665 }
666 s.position = ir.gc.inlineSequence;
667 s.bcIndex = SSA_SYNTH_BCI;
668 return s;
669 }
670
671 /**
672 * Set up a mapping from symbolic register number to the register.
673 * <p> TODO: put this functionality elsewhere.
674 *
675 * @return a mapping
676 */
677 private Register[] getSymbolicRegisters() {
678 Register[] map = new Register[ir.getNumberOfSymbolicRegisters()];
679 for (Register reg = ir.regpool.getFirstSymbolicRegister(); reg != null; reg = reg.getNext()) {
680 int number = reg.getNumber();
681 map[number] = reg;
682 }
683 return map;
684 }
685
686 /**
687 * Rename the symbolic registers so that each register has only one
688 * definition.
689 *
690 * <p><em> Note </em>: call this after phi functions have been inserted.
691 * <p> <b> Algorithm:</b> from Cytron et. al 91
692 * <pre>
693 * call search(entry)
694 *
695 * search(X):
696 * for each statement A in X do
697 * if A is not-phi
698 * for each r in RHS(A) do
699 * if !r.isSSA, replace r with TOP(S(r))
700 * done
701 * fi
702 * for each r in LHS(A) do
703 * if !r.isSSA
704 * r2 = new temp register
705 * push r2 onto S(r)
706 * replace r in A by r2
707 * fi
708 * done
709 * done (end of first loop)
710 * for each Y in succ(X) do
711 * j <- whichPred(Y,X)
712 * for each phi-function F in Y do
713 * replace the j-th operand (r) in RHS(F) with TOP(S(r))
714 * done
715 * done (end of second loop)
716 * for each Y in Children(X) do
717 * call search(Y)
718 * done (end of third loop)
719 * for each assignment A in X do
720 * for each r in LHS(A) do
721 * pop(S(r))
722 * done
723 * done (end of fourth loop)
724 * end
725 * <pre>
726 *
727 * @param symbolicRegisters mapping from integer to symbolic registers
728 */
729 private void renameSymbolicRegisters(Register[] symbolicRegisters) {
730 int n = ir.getNumberOfSymbolicRegisters();
731 @SuppressWarnings("unchecked") // the old covariant array-type problem
732 Stack<RegisterOperand>[] S = new Stack[n + 1];
733 for (int i = 0; i < S.length; i++) {
734 S[i] = new Stack<RegisterOperand>();
735 // populate the Stacks with initial names for
736 // each parameter, and push "null" for other symbolic registers
737 if (i >= symbolicRegisters.length) continue;
738 //Register r = symbolicRegisters[i];
739 // If a register's name is "null", that means the
740 // register has not yet been defined.
741 S[i].push(null);
742 }
743 BasicBlock entry = ir.cfg.entry();
744 DefUse.clearDU(ir);
745 numPredProcessed = new int[ir.getMaxBasicBlockNumber()];
746 search(entry, S);
747 DefUse.recomputeSSA(ir);
748 rectifyPhiTypes();
749 }
750
751 /**
752 * This routine is the guts of the SSA construction phase for scalars. See
753 * renameSymbolicRegisters for more details.
754 *
755 * @param X basic block to search dominator tree from
756 * @param S stack of names for each register
757 */
758 private void search(BasicBlock X, Stack<RegisterOperand>[] S) {
759 if (DEBUG) System.out.println("SEARCH " + X);
760 for (InstructionEnumeration ie = X.forwardInstrEnumerator(); ie.hasMoreElements();) {
761 Instruction A = ie.next();
762 if (A.operator() != PHI) {
763 // replace each use
764 for (int u = A.getNumberOfDefs(); u < A.getNumberOfOperands(); u++) {
765 Operand op = A.getOperand(u);
766 if (op instanceof RegisterOperand) {
767 RegisterOperand rop = (RegisterOperand) op;
768 Register r1 = rop.getRegister();
769 if (r1.isSSA()) continue;
770 if (r1.isPhysical()) continue;
771 RegisterOperand r2 = S[r1.getNumber()].peek();
772 if (DEBUG) System.out.println("REPLACE NORMAL USE " + r1 + " with " + r2);
773 if (r2 != null) {
774 rop.setRegister(r2.getRegister());
775 DefUse.recordUse(rop);
776 }
777 }
778 }
779 }
780 // replace each def
781 for (int d = 0; d < A.getNumberOfDefs(); d++) {
782 Operand op = A.getOperand(d);
783 if (op instanceof RegisterOperand) {
784 RegisterOperand rop = (RegisterOperand) op;
785 Register r1 = rop.getRegister();
786 if (r1.isSSA()) continue;
787 if (r1.isPhysical()) continue;
788 Register r2 = ir.regpool.getReg(r1);
789 if (DEBUG) System.out.println("PUSH " + r2 + " FOR " + r1 + " BECAUSE " + A);
790 S[r1.getNumber()].push(new RegisterOperand(r2, rop.getType()));
791 rop.setRegister(r2);
792 r2.scratchObject = r1;
793 }
794 }
795 } // end of first loop
796
797 if (DEBUG) System.out.println("SEARCH (second loop) " + X);
798 for (BasicBlockEnumeration y = X.getOut(); y.hasMoreElements();) {
799 BasicBlock Y = y.next();
800 if (DEBUG) System.out.println(" Successor: " + Y);
801 int j = numPredProcessed[Y.getNumber()]++;
802 if (Y.isExit()) continue;
803 Instruction s = Y.firstRealInstruction();
804 if (s == null) continue;
805 // replace use USE in each PHI instruction
806 if (DEBUG) System.out.println(" Predecessor: " + j);
807 while (s.operator() == PHI) {
808 Operand val = Phi.getValue(s, j);
809 if (val.isRegister()) {
810 Register r1 = ((RegisterOperand) Phi.getValue(s, j)).getRegister();
811 // ignore registers already marked SSA by a previous pass
812 if (!r1.isSSA()) {
813 RegisterOperand r2 = S[r1.getNumber()].peek();
814 if (r2 == null) {
815 // in this case, the register is never defined along
816 // this particular control flow path into the basic
817 // block.
818 Phi.setValue(s, j, new UnreachableOperand());
819 } else {
820 RegisterOperand rop = r2.copyRO();
821 Phi.setValue(s, j, rop);
822 DefUse.recordUse(rop);
823 }
824 Phi.setPred(s, j, new BasicBlockOperand(X));
825 }
826 }
827 s = s.nextInstructionInCodeOrder();
828 }
829 } // end of second loop
830
831 if (DEBUG) System.out.println("SEARCH (third loop) " + X);
832 for (Enumeration<TreeNode> c = ir.HIRInfo.dominatorTree.getChildren(X); c.hasMoreElements();) {
833 DominatorTreeNode v = (DominatorTreeNode) c.nextElement();
834 search(v.getBlock(), S);
835 } // end of third loop
836
837 if (DEBUG) System.out.println("SEARCH (fourth loop) " + X);
838 for (InstructionEnumeration a = X.forwardInstrEnumerator(); a.hasMoreElements();) {
839 Instruction A = a.next();
840 // loop over each def
841 for (int d = 0; d < A.getNumberOfDefs(); d++) {
842 Operand newOp = A.getOperand(d);
843 if (newOp == null) continue;
844 if (!newOp.isRegister()) continue;
845 Register newReg = newOp.asRegister().getRegister();
846 if (newReg.isSSA()) continue;
847 if (newReg.isPhysical()) continue;
848 Register r1 = (Register) newReg.scratchObject;
849 S[r1.getNumber()].pop();
850 if (DEBUG) System.out.println("POP " + r1);
851 }
852 } // end of fourth loop
853 if (DEBUG) System.out.println("FINISHED SEARCH " + X);
854 }
855
856 /**
857 * Rename the implicit heap variables in the SSA form so that
858 * each heap variable has only one definition.
859 *
860 * <p> Algorithm: Cytron et. al 91 (see renameSymbolicRegisters)
861 *
862 * @param ir the governing IR
863 */
864 private void renameHeapVariables(IR ir) {
865 int n = ir.HIRInfo.dictionary.getNumberOfHeapVariables();
866 if (n == 0) {
867 return;
868 }
869 // we maintain a stack of names for each type of heap variable
870 // stacks implements a mapping from type to Stack.
871 // Example: to get the stack of names for HEAP<int> variables,
872 // use stacks.get(ClassLoaderProxy.IntType);
873 HashMap<Object, Stack<HeapOperand<Object>>> stacks = new HashMap<Object, Stack<HeapOperand<Object>>>(n);
874 // populate the stacks variable with the initial heap variable
875 // names, currently stored in the SSADictionary
876 for (Iterator<HeapVariable<Object>> e = ir.HIRInfo.dictionary.getHeapVariables(); e.hasNext();) {
877 HeapVariable<Object> H = e.next();
878 Stack<HeapOperand<Object>> S = new Stack<HeapOperand<Object>>();
879 S.push(new HeapOperand<Object>(H));
880 Object heapType = H.getHeapType();
881 stacks.put(heapType, S);
882 }
883 BasicBlock entry = ir.cfg.entry();
884 numPredProcessed = new int[ir.getMaxBasicBlockNumber()];
885 search2(entry, stacks);
886 // registerRenamedHeapPhis(ir);
887 }
888
889 /**
890 * This routine is the guts of the SSA construction phase for heap array
891 * SSA. The renaming algorithm is analagous to the algorithm for
892 * scalars See <code> renameSymbolicRegisters </code> for more details.
893 *
894 * @param X the current basic block being traversed
895 * @param stacks a structure holding the current names for each heap
896 * variable
897 * used and defined by each instruction.
898 */
899 private void search2(BasicBlock X, HashMap<Object, Stack<HeapOperand<Object>>> stacks) {
900 if (DEBUG) System.out.println("SEARCH2 " + X);
901 SSADictionary dictionary = ir.HIRInfo.dictionary;
902 for (Enumeration<Instruction> ie = dictionary.getAllInstructions(X); ie.hasMoreElements();) {
903 Instruction A = ie.nextElement();
904 if (!dictionary.usesHeapVariable(A) && !dictionary.defsHeapVariable(A)) continue;
905 if (A.operator() != PHI) {
906 // replace the Heap variables USED by this instruction
907 HeapOperand<Object>[] uses = dictionary.getHeapUses(A);
908 if (uses != null) {
909 @SuppressWarnings("unchecked") // Generic array problem
910 HeapOperand<Object>[] newUses = new HeapOperand[uses.length];
911 for (int i = 0; i < uses.length; i++) {
912 Stack<HeapOperand<Object>> S = stacks.get(uses[i].getHeapType());
913 newUses[i] = S.peek().copy();
914 if (DEBUG) {
915 System.out.println("NORMAL USE PEEK " + newUses[i]);
916 }
917 }
918 dictionary.replaceUses(A, newUses);
919 }
920 }
921 // replace any Heap variable DEF
922 if (A.operator() != PHI) {
923 HeapOperand<Object>[] defs = dictionary.getHeapDefs(A);
924 if (defs != null) {
925 for (HeapOperand<Object> operand : dictionary.replaceDefs(A, X)) {
926 Stack<HeapOperand<Object>> S = stacks.get(operand.getHeapType());
927 S.push(operand);
928 if (DEBUG) System.out.println("PUSH " + operand + " FOR " + operand.getHeapType());
929 }
930 }
931 } else {
932 HeapOperand<Object>[] r = dictionary.replaceDefs(A, X);
933 Stack<HeapOperand<Object>> S = stacks.get(r[0].getHeapType());
934 S.push(r[0]);
935 if (DEBUG) System.out.println("PUSH " + r[0] + " FOR " + r[0].getHeapType());
936 }
937 } // end of first loop
938
939 for (BasicBlockEnumeration y = X.getOut(); y.hasMoreElements();) {
940 BasicBlock Y = y.next();
941 if (Y.isExit()) continue;
942 int j = numPredProcessed[Y.getNumber()]++;
943 // replace each USE in each HEAP-PHI function for Y
944 for (Iterator<Instruction> hp = dictionary.getHeapPhiInstructions(Y); hp.hasNext();) {
945 Instruction s = hp.next();
946 @SuppressWarnings("unchecked") // Down-cast to a generic type
947 HeapOperand<Object> H1 = (HeapOperand) Phi.getResult(s);
948 Stack<HeapOperand<Object>> S = stacks.get(H1.getHeapType());
949 HeapOperand<Object> H2 = S.peek();
950 Phi.setValue(s, j, new HeapOperand<Object>(H2.getHeapVariable()));
951 Phi.setPred(s, j, new BasicBlockOperand(X));
952 }
953 } // end of second loop
954
955 for (Enumeration<TreeNode> c = ir.HIRInfo.dominatorTree.getChildren(X); c.hasMoreElements();) {
956 DominatorTreeNode v = (DominatorTreeNode) c.nextElement();
957 search2(v.getBlock(), stacks);
958 } // end of third loop
959
960 for (Enumeration<Instruction> a = dictionary.getAllInstructions(X); a.hasMoreElements();) {
961 Instruction A = a.nextElement();
962 if (!dictionary.usesHeapVariable(A) && !dictionary.defsHeapVariable(A)) continue;
963 // retrieve the Heap Variables defined by A
964 if (A.operator != PHI) {
965 HeapOperand<Object>[] defs = dictionary.getHeapDefs(A);
966 if (defs != null) {
967 for (HeapOperand<Object> def : defs) {
968 Stack<HeapOperand<Object>> S = stacks.get(def.getHeapType());
969 S.pop();
970 if (DEBUG) System.out.println("POP " + def.getHeapType());
971 }
972 }
973 } else {
974 @SuppressWarnings("unchecked") // Down-cast to a generic type
975 HeapOperand<Object> H = (HeapOperand) Phi.getResult(A);
976 Stack<HeapOperand<Object>> S = stacks.get(H.getHeapType());
977 S.pop();
978 if (DEBUG) System.out.println("POP " + H.getHeapType());
979 }
980 } // end of fourth loop
981 if (DEBUG) System.out.println("END SEARCH2 " + X);
982 }
983
984 /**
985 * After performing renaming on heap phi functions, this
986 * routines notifies the SSA dictionary of the new names.
987 *
988 * FIXME - this was commented out: delete it ?? RJG
989 *
990 * @param ir the governing IR
991 */
992 @SuppressWarnings({"unused", "unchecked"})
993 // HeapOperand requires casts to a generic type
994 private void registerRenamedHeapPhis(IR ir) {
995 SSADictionary ssa = ir.HIRInfo.dictionary;
996 for (BasicBlockEnumeration e1 = ir.getBasicBlocks(); e1.hasMoreElements();) {
997 BasicBlock bb = e1.nextElement();
998 for (Enumeration<Instruction> e2 = ssa.getAllInstructions(bb); e2.hasMoreElements();) {
999 Instruction s = e2.nextElement();
1000 if (Phi.conforms(s)) {
1001 if (ssa.defsHeapVariable(s)) {
1002 int n = Phi.getNumberOfValues(s);
1003 HeapOperand<Object>[] uses = new HeapOperand[n];
1004 for (int i = 0; i < n; i++) {
1005 uses[i] = (HeapOperand) Phi.getValue(s, i);
1006 }
1007 ssa.replaceUses(s, uses);
1008 }
1009 }
1010 }
1011 }
1012 }
1013
1014 /**
1015 * Store a copy of the Heap variables each instruction defs.
1016 *
1017 * @param ir governing IR
1018 * @param store place to store copies
1019 */
1020 @SuppressWarnings("unused")
1021 private void copyHeapDefs(IR ir, HashMap<Instruction, HeapOperand<?>[]> store) {
1022 SSADictionary dictionary = ir.HIRInfo.dictionary;
1023 for (BasicBlockEnumeration be = ir.forwardBlockEnumerator(); be.hasMoreElements();) {
1024 BasicBlock bb = be.next();
1025 for (Enumeration<Instruction> e = dictionary.getAllInstructions(bb); e.hasMoreElements();) {
1026 Instruction s = e.nextElement();
1027 store.put(s, ir.HIRInfo.dictionary.getHeapDefs(s));
1028 }
1029 }
1030 }
1031
1032 /**
1033 * Compute type information for operands in each phi instruction.
1034 *
1035 * PRECONDITION: Def-use chains computed.
1036 * SIDE EFFECT: empties the scalarPhis set
1037 * SIDE EFFECT: bashes the Instruction scratch field.
1038 */
1039 private static final int NO_NULL_TYPE = 0;
1040 private static final int FOUND_NULL_TYPE = 1;
1041
1042 private void rectifyPhiTypes() {
1043 if (DEBUG) System.out.println("Rectify phi types.");
1044 removeAllUnreachablePhis(scalarPhis);
1045 while (!scalarPhis.isEmpty()) {
1046 boolean didSomething = false;
1047 for (Iterator<Instruction> i = scalarPhis.iterator(); i.hasNext();) {
1048 Instruction phi = i.next();
1049 phi.scratch = NO_NULL_TYPE;
1050 if (DEBUG) System.out.println("PHI: " + phi);
1051 TypeReference meet = meetPhiType(phi);
1052 if (DEBUG) System.out.println("MEET: " + meet);
1053 if (meet != null) {
1054 didSomething = true;
1055 if (phi.scratch == NO_NULL_TYPE) i.remove();
1056 RegisterOperand result = (RegisterOperand) Phi.getResult(phi);
1057 result.setType(meet);
1058 for (Enumeration<RegisterOperand> e = DefUse.uses(result.getRegister()); e.hasMoreElements();) {
1059 RegisterOperand rop = e.nextElement();
1060 if (rop.getType() != meet) {
1061 rop.clearPreciseType();
1062 rop.setType(meet);
1063 }
1064 }
1065 }
1066 }
1067 if (!didSomething) {
1068 // iteration has bottomed out.
1069 return;
1070 }
1071 }
1072 }
1073
1074 /**
1075 * Remove all phis that are unreachable
1076 */
1077 private void removeAllUnreachablePhis(HashSet<Instruction> scalarPhis) {
1078 boolean iterateAgain = false;
1079 do {
1080 iterateAgain = false;
1081 outer:
1082 for (Iterator<Instruction> i = scalarPhis.iterator(); i.hasNext();) {
1083 Instruction phi = i.next();
1084 for (int j = 0; j < Phi.getNumberOfValues(phi); j++) {
1085 Operand op = Phi.getValue(phi, j);
1086 if (!(op instanceof UnreachableOperand)) {
1087 continue outer;
1088 }
1089 }
1090 RegisterOperand result = Phi.getResult(phi).asRegister();
1091 i.remove();
1092 for (Enumeration<RegisterOperand> e = DefUse.uses(result.getRegister()); e.hasMoreElements();) {
1093 RegisterOperand use = e.nextElement();
1094 Instruction s = use.instruction;
1095 if (Phi.conforms(s)) {
1096 for (int k = 0; k < Phi.getNumberOfValues(phi); k++) {
1097 Operand op = Phi.getValue(phi, k);
1098 if (op != null && op.similar(result)) {
1099 Phi.setValue(phi, k, new UnreachableOperand());
1100 iterateAgain = true;
1101 }
1102 }
1103 }
1104 }
1105 }
1106 } while (iterateAgain);
1107 }
1108
1109 /**
1110 * Remove all unreachable operands from scalar phi functions
1111 *
1112 * NOT CURRENTLY USED
1113 */
1114 @SuppressWarnings("unused")
1115 private void removeUnreachableOperands(HashSet<Instruction> scalarPhis) {
1116 for (Instruction phi : scalarPhis) {
1117 boolean didSomething = true;
1118 while (didSomething) {
1119 didSomething = false;
1120 for (int j = 0; j < Phi.getNumberOfValues(phi); j++) {
1121 Operand v = Phi.getValue(phi, j);
1122 if (v instanceof UnreachableOperand) {
1123 // rewrite the phi instruction to remove the unreachable
1124 // operand
1125 didSomething = true;
1126 Instruction tmpPhi = phi.copyWithoutLinks();
1127 Phi.mutate(phi, PHI, Phi.getResult(tmpPhi), Phi.getNumberOfValues(phi) - 1);
1128 int m = 0;
1129 for (int k = 0; k < Phi.getNumberOfValues(phi); k++) {
1130 if (k == j) continue;
1131 Phi.setValue(phi, m, Phi.getValue(tmpPhi, k));
1132 Phi.setPred(phi, m, Phi.getPred(tmpPhi, k));
1133 m++;
1134 }
1135 }
1136 }
1137 }
1138 }
1139 }
1140
1141 /**
1142 * Return the meet of the types on the rhs of a phi instruction
1143 *
1144 * @param s phi instruction
1145 *
1146 * SIDE EFFECT: bashes the Instruction scratch field.
1147 */
1148 private static TypeReference meetPhiType(Instruction s) {
1149
1150 TypeReference result = null;
1151 for (int i = 0; i < Phi.getNumberOfValues(s); i++) {
1152 Operand val = Phi.getValue(s, i);
1153 if (val instanceof UnreachableOperand) continue;
1154 TypeReference t = val.getType();
1155 if (t == null) {
1156 s.scratch = FOUND_NULL_TYPE;
1157 } else if (result == null) {
1158 result = t;
1159 } else {
1160 TypeReference meet = ClassLoaderProxy.findCommonSuperclass(result, t);
1161 if (meet == null) {
1162 // TODO: This horrific kludge should go away once we get rid of Address.toInt()
1163 if ((result.isIntLikeType() && (t.isReferenceType() || t.isWordLikeType())) ||
1164 ((result.isReferenceType() || result.isWordLikeType()) && t.isIntLikeType())) {
1165 meet = TypeReference.Int;
1166 } else if (result.isReferenceType() && t.isWordLikeType()) {
1167 meet = t;
1168 } else if (result.isWordLikeType() && t.isReferenceType()) {
1169 meet = result;
1170 }
1171 }
1172 if (VM.VerifyAssertions && meet == null) {
1173 VM._assert(false, result + " and " + t + " meet to null");
1174 }
1175 result = meet;
1176 }
1177 }
1178 return result;
1179 }
1180
1181 /**
1182 * Find a parameter type.
1183 *
1184 * <p> Given a register that holds a parameter, look at the register's
1185 * use chain to find the type of the parameter
1186 */
1187 @SuppressWarnings("unused")
1188 private TypeReference findParameterType(Register p) {
1189 RegisterOperand firstUse = p.useList;
1190 if (firstUse == null) {
1191 return null; // parameter has no uses
1192 }
1193 return firstUse.getType();
1194 }
1195 }
1196
1197
1198