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