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.GUARD_MOVE;
017 import static org.jikesrvm.compilers.opt.ir.Operators.PHI;
018
019 import java.lang.reflect.Constructor;
020 import java.util.Enumeration;
021 import java.util.HashMap;
022 import java.util.HashSet;
023 import java.util.Iterator;
024 import java.util.LinkedList;
025 import java.util.Stack;
026
027 import org.jikesrvm.VM;
028 import org.jikesrvm.classloader.TypeReference;
029 import org.jikesrvm.compilers.opt.DefUse;
030 import org.jikesrvm.compilers.opt.OptOptions;
031 import org.jikesrvm.compilers.opt.OptimizingCompilerException;
032 import org.jikesrvm.compilers.opt.controlflow.BranchOptimizations;
033 import org.jikesrvm.compilers.opt.controlflow.DominatorTree;
034 import org.jikesrvm.compilers.opt.controlflow.DominatorTreeNode;
035 import org.jikesrvm.compilers.opt.controlflow.LTDominators;
036 import org.jikesrvm.compilers.opt.driver.CompilerPhase;
037 import org.jikesrvm.compilers.opt.ir.BasicBlock;
038 import org.jikesrvm.compilers.opt.ir.IR;
039 import org.jikesrvm.compilers.opt.ir.IRTools;
040 import org.jikesrvm.compilers.opt.ir.Instruction;
041 import org.jikesrvm.compilers.opt.ir.Move;
042 import org.jikesrvm.compilers.opt.ir.Phi;
043 import org.jikesrvm.compilers.opt.ir.Register;
044 import org.jikesrvm.compilers.opt.ir.operand.ConstantOperand;
045 import org.jikesrvm.compilers.opt.ir.operand.Operand;
046 import org.jikesrvm.compilers.opt.ir.operand.RegisterOperand;
047 import org.jikesrvm.compilers.opt.ir.operand.TrueGuardOperand;
048 import org.jikesrvm.compilers.opt.ir.operand.UnreachableOperand;
049 import org.jikesrvm.compilers.opt.liveness.LiveAnalysis;
050 import org.jikesrvm.compilers.opt.liveness.LiveSet;
051 import org.jikesrvm.compilers.opt.util.TreeNode;
052
053 /**
054 * This compiler phase translates out of SSA form.
055 *
056 * @see SSA
057 * @see SSAOptions
058 * @see LTDominators
059 */
060 public class LeaveSSA extends CompilerPhase {
061
062 /**
063 * verbose debugging flag
064 */
065 static final boolean DEBUG = false;
066
067 /**
068 * The IR to manipulate
069 */
070 private IR ir;
071
072 private final BranchOptimizations branchOpts = new BranchOptimizations(-1, true, true);
073
074 private boolean splitSomeBlock = false;
075
076 private final HashSet<Instruction> globalRenameTable = new HashSet<Instruction>();
077
078 private final HashSet<Register> globalRenamePhis = new HashSet<Register>();
079
080 /**
081 * Is SSA form enabled for the HIR?
082 */
083 @Override
084 public final boolean shouldPerform(OptOptions options) {
085 return options.SSA;
086 }
087
088 /**
089 * Constructor for this compiler phase
090 */
091 private static final Constructor<CompilerPhase> constructor = getCompilerPhaseConstructor(LeaveSSA.class);
092
093 /**
094 * Get a constructor object for this compiler phase
095 * @return compiler phase constructor
096 */
097 @Override
098 public Constructor<CompilerPhase> getClassConstructor() {
099 return constructor;
100 }
101
102 /**
103 * Return a string name for this phase.
104 * @return "Leave SSA"
105 */
106 @Override
107 public final String getName() {
108 return "Leave SSA";
109 }
110
111 /**
112 * perform the main out-of-ssa transformation
113 */
114 @Override
115 public final void perform(IR ir) {
116 this.ir = ir;
117 translateFromSSA(ir);
118
119 // reset ir.SSADictionary
120 ir.HIRInfo.dictionary = null;
121 // reset ssa options
122 ir.actualSSAOptions = null;
123
124 branchOpts.perform(ir, true);
125
126 ir.HIRInfo.dominatorsAreComputed = false;
127 }
128
129 /**
130 * This class provides an abstraction over stacks of names
131 * for registers.
132 */
133 static final class VariableStacks extends HashMap<Register, Stack<Operand>> {
134 /** Support for map serialization */
135 static final long serialVersionUID = -5664504465082745314L;
136
137 /**
138 * Get the name at the top of the stack for a particular register
139 * @param s the register in question
140 * @return the name at the top of the stack for the register
141 */
142 Operand peek(Register s) {
143 Stack<Operand> stack = get(s);
144 if (stack == null || stack.isEmpty()) {
145 return null;
146 } else {
147 return stack.peek();
148 }
149 }
150
151 /**
152 * Pop the name at the top of the stack for a particular register
153 * @param s the register in question
154 * @return the name at the top of the stack for the register
155 */
156 Operand pop(Register s) {
157 Stack<Operand> stack = get(s);
158 if (stack == null) {
159 throw new OptimizingCompilerException(
160 "Failure in translating out of SSA form: trying to pop operand from non-existant stack");
161 } else {
162 return stack.pop();
163 }
164 }
165
166 /**
167 * Push a name at the top of the stack for a particular register
168 * @param s the register in question
169 * @param name the name to push on the stack
170 */
171 void push(Register s, Operand name) {
172 Stack<Operand> stack = get(s);
173 if (stack == null) {
174 stack = new Stack<Operand>();
175 put(s, stack);
176 }
177 stack.push(name);
178 }
179 }
180
181 /**
182 * An instance of this class represents a pending copy instruction
183 * to be inserted.
184 */
185 static final class Copy {
186 /**
187 * The right-hand side of the copy instruction
188 */
189 final Operand source;
190 /**
191 * The left-hand side of the copy instruction
192 */
193 final RegisterOperand destination;
194 /**
195 * The phi instruction which generated this copy instruction
196 */
197 final Instruction phi;
198
199 /**
200 * Create a pending copy operation for an operand of a phi instruction
201 * @param phi the phi instruction
202 * @param index which operand of the instruction to copy
203 */
204 Copy(Instruction phi, int index) {
205 this.phi = phi;
206 destination = Phi.getResult(phi).asRegister();
207 source = Phi.getValue(phi, index);
208 }
209 }
210
211 /**
212 * substitute variables renamed in control parents
213 */
214 private void performRename(BasicBlock bb, DominatorTree dom, VariableStacks s) {
215 if (DEBUG) VM.sysWriteln("performRename: " + bb);
216
217 Enumeration<Instruction> e = bb.forwardRealInstrEnumerator();
218 while (e.hasMoreElements()) {
219 Instruction i = e.nextElement();
220 Enumeration<Operand> ee = i.getUses();
221 while (ee.hasMoreElements()) {
222 Operand o = ee.nextElement();
223 if (o instanceof RegisterOperand) {
224 Register r1 = ((RegisterOperand) o).getRegister();
225 if (r1.isValidation()) continue;
226 Operand r2 = s.peek(r1);
227 if (r2 != null) {
228 if (DEBUG) {
229 VM.sysWriteln("replace operand in " + i + "(" + r2 + " for " + o);
230 }
231 i.replaceOperand(o, r2.copy());
232 }
233 }
234 }
235 }
236
237 // record renamings required in children
238 e = bb.forwardRealInstrEnumerator();
239 while (e.hasMoreElements()) {
240 Instruction i = e.nextElement();
241 if (globalRenameTable.contains(i)) {
242 Register original = Move.getVal(i).asRegister().getRegister();
243 RegisterOperand rename = Move.getResult(i);
244 if (DEBUG) VM.sysWriteln("record rename " + rename + " for " + original);
245 s.push(original, rename);
246 }
247 }
248
249 // insert copies in control children
250 Enumeration<TreeNode> children = dom.getChildren(bb);
251 while (children.hasMoreElements()) {
252 BasicBlock c = ((DominatorTreeNode) children.nextElement()).getBlock();
253 performRename(c, dom, s);
254 }
255
256 // pop renamings from this block off stack
257 e = bb.forwardRealInstrEnumerator();
258 while (e.hasMoreElements()) {
259 Instruction i = e.nextElement();
260 if (globalRenameTable.contains(i)) {
261 Register original = Move.getVal(i).asRegister().getRegister();
262 s.pop(original);
263 }
264 }
265 }
266
267 private boolean usedBelowCopy(BasicBlock bb, Register r) {
268 Enumeration<Instruction> ie = bb.reverseRealInstrEnumerator();
269 while (ie.hasMoreElements()) {
270 Instruction inst = ie.nextElement();
271 if (inst.isBranch()) {
272 Enumeration<Operand> oe = inst.getUses();
273 while (oe.hasMoreElements()) {
274 Operand op = oe.nextElement();
275 if (op.isRegister() && op.asRegister().getRegister() == r) {
276 return true;
277 }
278 }
279 } else {
280 break;
281 }
282 }
283
284 return false;
285 }
286
287 /**
288 * Record pending copy operations needed to insert at the end of a basic
289 * block.<p>
290 *
291 * TODO: this procedure is getting long and ugly. Rewrite or refactor
292 * it.
293 * @param bb the basic block to process
294 * @param live valid liveness information for the IR
295 */
296 private void scheduleCopies(BasicBlock bb, LiveAnalysis live) {
297
298 if (DEBUG) VM.sysWrite("scheduleCopies: " + bb + "\n");
299
300 // compute out liveness from information in LiveAnalysis
301 LiveSet out = new LiveSet();
302 for (Enumeration<BasicBlock> outBlocks = bb.getOut(); outBlocks.hasMoreElements();) {
303 BasicBlock ob = outBlocks.nextElement();
304 LiveAnalysis.BBLiveElement le = live.getLiveInfo(ob);
305 out.add(le.getIn());
306 }
307
308 // usedByAnother represents the set of registers that appear on the
309 // left-hand side of subsequent phi nodes. This is important, since
310 // we be careful to order copies if the same register appears as the
311 // source and dest of copies in the same basic block.
312 HashSet<Register> usedByAnother = new HashSet<Register>(4);
313
314 // for each basic block successor b of bb, if we make a block on the
315 // critical edge bb->b, then store this critical block.
316 HashMap<BasicBlock, BasicBlock> criticalBlocks = new HashMap<BasicBlock, BasicBlock>(4);
317
318 // For each critical basic block b in which we are inserting copies: return the
319 // mapping of registers to names implied by the copies that have
320 // already been inserted into b.
321 HashMap<BasicBlock, HashMap<Register, Register>> currentNames =
322 new HashMap<BasicBlock, HashMap<Register, Register>>(4);
323
324 // Additionally store the current names for the current basic block bb.
325 HashMap<Register, Register> bbNames = new HashMap<Register, Register>(4);
326
327 // copySet is a linked-list of copies we need to insert in this block.
328 final LinkedList<Copy> copySet = new LinkedList<Copy>();
329
330 /* Worklist is actually used like a stack - should we make this an Stack ?? */
331 final LinkedList<Copy> workList = new LinkedList<Copy>();
332
333 // collect copies required in this block. These copies move
334 // the appropriate rval into the lval of each phi node in
335 // control children of the current block.
336 Enumeration<BasicBlock> e = bb.getOut();
337 while (e.hasMoreElements()) {
338 BasicBlock bbs = e.nextElement();
339 if (bbs.isExit()) continue;
340 for (Instruction phi = bbs.firstInstruction(); phi != bbs.lastInstruction(); phi =
341 phi.nextInstructionInCodeOrder()) {
342 if (phi.operator() != PHI) continue;
343 for (int index = 0; index < Phi.getNumberOfPreds(phi); index++) {
344 if (Phi.getPred(phi, index).block != bb) continue;
345 Operand rval = Phi.getValue(phi, index);
346 if (rval.isRegister() && Phi.getResult(phi).asRegister().getRegister() == rval.asRegister().getRegister()) {
347 continue;
348 }
349 Copy c = new Copy(phi, index);
350 copySet.add(0, c);
351 if (c.source instanceof RegisterOperand) {
352 Register r = c.source.asRegister().getRegister();
353 usedByAnother.add(r);
354 }
355 }
356 }
357 }
358 // the copies that need to be added to this block are processed
359 // in a worklist that ensures that copies are inserted only
360 // after the destination register has been read by any other copy
361 // that needs it.
362 //
363 // initialize work list with all copies whose destination is not
364 // the source for any other copy, and delete such copies from
365 // the set of needed copies.
366 for (Iterator<Copy> copySetIter = copySet.iterator(); copySetIter.hasNext();) {
367 Copy c = copySetIter.next();
368 if (!usedByAnother.contains(c.destination.getRegister())) {
369 workList.add(0, c);
370 copySetIter.remove();
371 }
372 }
373 // while there is any more work to do.
374 while (!workList.isEmpty() || !copySet.isEmpty()) {
375 // while there are copies that can be correctly inserted.
376 while (!workList.isEmpty()) {
377 Copy c = workList.remove(0);
378 Register r = c.destination.getRegister();
379 TypeReference tt = c.destination.getType();
380 if (VM.VerifyAssertions && tt == null) {
381 tt = TypeReference.Int;
382 VM.sysWrite("SSA, warning: null type in " + c.destination + "\n");
383 }
384
385 Register rr = null;
386 if (c.source.isRegister()) rr = c.source.asRegister().getRegister();
387 boolean shouldSplitBlock =
388 !c.phi.getBasicBlock().isExceptionHandlerBasicBlock() &&
389 ((ir.options.SSA_SPLITBLOCK_TO_AVOID_RENAME && out.contains(r)) ||
390 (rr != null && ir.options.SSA_SPLITBLOCK_FOR_LOCAL_LIVE && usedBelowCopy(bb, rr)));
391
392 if (ir.options.SSA_SPLITBLOCK_INTO_INFREQUENT) {
393 if (!bb.getInfrequent() &&
394 c.phi.getBasicBlock().getInfrequent() &&
395 !c.phi.getBasicBlock().isExceptionHandlerBasicBlock()) {
396 shouldSplitBlock = true;
397 }
398 }
399
400 // this check captures cases when the result of a phi
401 // in a control successor is live on exit of the current
402 // block. this means it is incorrect to simply insert
403 // a copy of the destination in the current block. so
404 // we rename the destination to a new temporary, and
405 // record the renaming so that dominator blocks get the
406 // new name.
407 if (out.contains(r) && !shouldSplitBlock) {
408 if (!globalRenamePhis.contains(r)) {
409 Register t = ir.regpool.getReg(r);
410 Instruction save = SSA.makeMoveInstruction(ir, t, r, tt);
411 if (DEBUG) {
412 VM.sysWriteln("Inserting " + save + " before " + c.phi + " in " + c.phi.getBasicBlock());
413 }
414 c.phi.insertAfter(save);
415 globalRenamePhis.add(r);
416 globalRenameTable.add(save);
417 }
418 }
419 Instruction ci = null;
420
421 // insert copy operation required to remove phi
422 if (c.source instanceof ConstantOperand) {
423 if (c.source instanceof UnreachableOperand) {
424 ci = null;
425 } else {
426 ci = SSA.makeMoveInstruction(ir, r, (ConstantOperand) c.source);
427 }
428 } else if (c.source instanceof RegisterOperand) {
429 if (shouldSplitBlock) {
430 if (DEBUG) VM.sysWriteln("splitting edge: " + bb + "->" + c.phi.getBasicBlock());
431 BasicBlock criticalBlock = criticalBlocks.get(c.phi.getBasicBlock());
432 if (criticalBlock == null) {
433 criticalBlock = IRTools.makeBlockOnEdge(bb, c.phi.getBasicBlock(), ir);
434 if (c.phi.getBasicBlock().getInfrequent()) {
435 criticalBlock.setInfrequent();
436 }
437 splitSomeBlock = true;
438 criticalBlocks.put(c.phi.getBasicBlock(), criticalBlock);
439 HashMap<Register, Register> newNames = new HashMap<Register, Register>(4);
440 currentNames.put(criticalBlock, newNames);
441 }
442 Register sr = c.source.asRegister().getRegister();
443 HashMap<Register, Register> criticalBlockNames = currentNames.get(criticalBlock);
444 Register nameForSR = criticalBlockNames.get(sr);
445 if (nameForSR == null) {
446 nameForSR = bbNames.get(sr);
447 if (nameForSR == null) nameForSR = sr;
448 }
449 if (DEBUG) VM.sysWriteln("dest(r): " + r);
450 if (DEBUG) VM.sysWriteln("sr: " + sr + ", nameForSR: " + nameForSR);
451 ci = SSA.makeMoveInstruction(ir, r, nameForSR, tt);
452 criticalBlockNames.put(sr, r);
453 criticalBlock.appendInstructionRespectingTerminalBranch(ci);
454 } else {
455 Register sr = c.source.asRegister().getRegister();
456 Register nameForSR = bbNames.get(sr);
457 if (nameForSR == null) nameForSR = sr;
458 if (DEBUG) VM.sysWriteln("not splitting edge: " + bb + "->" + c.phi.getBasicBlock());
459 if (DEBUG) VM.sysWriteln("dest(r): " + r);
460 if (DEBUG) VM.sysWriteln("sr: " + sr + ", nameForSR: " + nameForSR);
461 ci = SSA.makeMoveInstruction(ir, r, nameForSR, tt);
462 bbNames.put(sr, r);
463 SSA.addAtEnd(ir, bb, ci, c.phi.getBasicBlock().isExceptionHandlerBasicBlock());
464 }
465 // ugly hack: having already added ci; set ci to null to skip remaining code;
466 ci = null;
467 } else {
468 throw new OptimizingCompilerException("Unexpected phi operand " +
469 c
470 .source +
471 " encountered during SSA teardown", true);
472 }
473 if (ci != null) {
474 if (shouldSplitBlock) {
475 if (DEBUG) VM.sysWriteln("splitting edge: " + bb + "->" + c.phi.getBasicBlock());
476 BasicBlock criticalBlock = criticalBlocks.get(c.phi.getBasicBlock());
477 if (criticalBlock == null) {
478 criticalBlock = IRTools.makeBlockOnEdge(bb, c.phi.getBasicBlock(), ir);
479 if (c.phi.getBasicBlock().getInfrequent()) {
480 criticalBlock.setInfrequent();
481 }
482 splitSomeBlock = true;
483 criticalBlocks.put(c.phi.getBasicBlock(), criticalBlock);
484 HashMap<Register, Register> newNames = new HashMap<Register, Register>(4);
485 currentNames.put(criticalBlock, newNames);
486 }
487 criticalBlock.appendInstructionRespectingTerminalBranch(ci);
488 } else {
489 SSA.addAtEnd(ir, bb, ci, c.phi.getBasicBlock().isExceptionHandlerBasicBlock());
490 }
491 }
492
493 // source has been copied and so can now be overwritten
494 // safely. so now add any copies _to_ the source of the
495 // current copy to the work list.
496 if (c.source instanceof RegisterOperand) {
497 Register saved = c.source.asRegister().getRegister();
498 Iterator<Copy> copySetIter = copySet.iterator();
499 while (copySetIter.hasNext()) {
500 Copy cc = copySetIter.next();
501 if (cc.destination.asRegister().getRegister() == saved) {
502 workList.add(0, cc);
503 copySetIter.remove();
504 }
505 }
506 }
507 }
508 // an empty work list with work remaining in the copy set
509 // implies a cycle in the dependencies amongst copies. deal
510 // with this: break the cycle by copying the destination
511 // of an arbitrary member of the copy set into a temporary.
512 // this destination has thus been saved, and can now be
513 // safely overwritten. so, add that copy to the work list.
514 if (!copySet.isEmpty()) {
515 Copy c = copySet.remove(0);
516 Register tt = ir.regpool.getReg(c.destination.getRegister());
517 SSA.addAtEnd(ir,
518 bb,
519 SSA.makeMoveInstruction(ir, tt, c.destination.getRegister(), c.destination.getType()),
520 c.phi.getBasicBlock().isExceptionHandlerBasicBlock());
521 bbNames.put(c.destination.getRegister(), tt);
522 workList.add(0, c);
523 }
524 }
525 }
526
527 /**
528 * Insert copy instructions into a basic block to safely translate out
529 * of SSA form.
530 *
531 * @param bb the basic block
532 * @param dom a valid dominator tree for the IR
533 * @param live valid liveness information for the IR
534 */
535 private void insertCopies(BasicBlock bb, DominatorTree dom, LiveAnalysis live) {
536 // add copies required in this block to remove phis.
537 // (record renaming required by simultaneous liveness in global tables)
538 scheduleCopies(bb, live);
539
540 // insert copies in control children
541 Enumeration<TreeNode> children = dom.getChildren(bb);
542 while (children.hasMoreElements()) {
543 BasicBlock c = ((DominatorTreeNode) children.nextElement()).getBlock();
544 insertCopies(c, dom, live);
545 }
546 }
547
548 /**
549 * Main driver to translate an IR out of SSA form.
550 *
551 * @param ir the IR in SSA form
552 */
553 public void translateFromSSA(IR ir) {
554 // 0. Deal with guards (validation registers)
555 unSSAGuards(ir);
556
557 // 1. re-compute dominator tree in case of control flow changes
558 LTDominators.perform(ir, true, true);
559 DominatorTree dom = new DominatorTree(ir, true);
560
561 // 1.5 Perform Sreedhar's naive translation from TSSA to CSSA
562 //if (ir.options.UNROLL_LOG == 0) normalizeSSA(ir);
563
564 // 2. compute liveness
565 LiveAnalysis live = new LiveAnalysis(false, // don't create GC maps
566 true, // skip (final) local propagation step
567 // of live analysis
568 false, // don't store information at handlers
569 false); // don't skip guards
570
571 live.perform(ir);
572 // 3. initialization
573 VariableStacks s = new VariableStacks();
574 // 4. convert phi nodes into copies
575 BasicBlock b = ((DominatorTreeNode) dom.getRoot()).getBlock();
576 insertCopies(b, dom, live);
577 // 5. If necessary, recompute dominators to account for new control flow.
578 if (splitSomeBlock) {
579 LTDominators.perform(ir, true, true);
580 dom = new DominatorTree(ir, true);
581 }
582 // 6. compensate for copies required by simultaneous liveness
583 performRename(b, dom, s);
584 // 7. phis are now redundant
585 removeAllPhis(ir);
586 }
587
588 /**
589 * Remove all phi instructions from the IR.
590 *
591 * @param ir the governing IR
592 */
593 static void removeAllPhis(IR ir) {
594 for (Instruction s = ir.firstInstructionInCodeOrder(),
595 sentinel = ir.lastInstructionInCodeOrder(),
596 nextInstr = null; s != sentinel; s = nextInstr) {
597 // cache because remove nulls next/prev fields
598 nextInstr = s.nextInstructionInCodeOrder();
599 if (Phi.conforms(s)) s.remove();
600 }
601 }
602
603 /**
604 * Special treatment for guard registers:
605 * Remove guard-phis by evaluating operands into same register.
606 * If this target register is not unique, unite the alternatives.
607 */
608 private void unSSAGuards(IR ir) {
609 // 0. initialization
610 unSSAGuardsInit(ir);
611 // 1. Determine target registers
612 unSSAGuardsDetermineReg(ir);
613 // 2. Rename targets and remove Phis
614 unSSAGuardsFinalize(ir);
615 }
616
617 Instruction guardPhis = null;
618
619 /**
620 * Initialization for removal of guard phis.
621 */
622 private void unSSAGuardsInit(IR ir) {
623 guardPhis = null;
624 Enumeration<Instruction> e = ir.forwardInstrEnumerator();
625
626 // visit all instructions, looking for guard phis
627
628 while (e.hasMoreElements()) {
629 Instruction inst = e.nextElement();
630 if (!Phi.conforms(inst)) continue;
631 Operand res = Phi.getResult(inst);
632 if (!(res instanceof RegisterOperand)) continue;
633 Register r = res.asRegister().getRegister();
634 if (!r.isValidation()) continue;
635
636 // force all operands of Phis into registers.
637
638 inst.scratchObject = guardPhis;
639 guardPhis = inst;
640
641 int values = Phi.getNumberOfValues(inst);
642 for (int i = 0; i < values; ++i) {
643 Operand op = Phi.getValue(inst, i);
644 if (!(op instanceof RegisterOperand)) {
645 if (op instanceof TrueGuardOperand) {
646 BasicBlock bb = Phi.getPred(inst, i).block;
647 Instruction move = Move.create(GUARD_MOVE, res.asRegister().copyD2D(), new TrueGuardOperand());
648 move.position = ir.gc.inlineSequence;
649 move.bcIndex = SSA_SYNTH_BCI;
650 bb.appendInstructionRespectingTerminalBranchOrPEI(move);
651 } else if (op instanceof UnreachableOperand) {
652 // do nothing
653 } else {
654 if (VM.VerifyAssertions) VM._assert(VM.NOT_REACHED);
655 }
656 }
657 }
658 }
659
660 // visit all guard registers, init union/find
661 for (Register r = ir.regpool.getFirstSymbolicRegister(); r != null; r = r.getNext()) {
662 if (!r.isValidation()) continue;
663 r.scratch = 1;
664 r.scratchObject = r;
665 }
666 }
667
668 /**
669 * Determine target register for guard phi operands
670 */
671 private void unSSAGuardsDetermineReg(IR ir) {
672 Instruction inst = guardPhis;
673 while (inst != null) {
674 Register r = Phi.getResult(inst).asRegister().getRegister();
675 int values = Phi.getNumberOfValues(inst);
676 for (int i = 0; i < values; ++i) {
677 Operand op = Phi.getValue(inst, i);
678 if (op instanceof RegisterOperand) {
679 guardUnion(op.asRegister().getRegister(), r);
680 } else {
681 if (VM.VerifyAssertions) {
682 VM._assert(op instanceof TrueGuardOperand || op instanceof UnreachableOperand);
683 }
684 }
685 }
686 inst = (Instruction) inst.scratchObject;
687 }
688 }
689
690 /**
691 * Rename registers and delete Phis.
692 */
693 private void unSSAGuardsFinalize(IR ir) {
694 DefUse.computeDU(ir);
695 for (Register r = ir.regpool.getFirstSymbolicRegister(); r != null; r = r.getNext()) {
696 if (!r.isValidation()) continue;
697 Register nreg = guardFind(r);
698 Enumeration<RegisterOperand> uses = DefUse.uses(r);
699 while (uses.hasMoreElements()) {
700 RegisterOperand use = uses.nextElement();
701 use.setRegister(nreg);
702 }
703 Enumeration<RegisterOperand> defs = DefUse.defs(r);
704 while (defs.hasMoreElements()) {
705 RegisterOperand def = defs.nextElement();
706 def.setRegister(nreg);
707 }
708 }
709 Instruction inst = guardPhis;
710 while (inst != null) {
711 inst.remove();
712 inst = (Instruction) inst.scratchObject;
713 }
714 }
715
716 /**
717 * union step of union/find for guard registers during unSSA
718 */
719 private Register guardUnion(Register from, Register to) {
720 Register a = guardFind(from);
721 Register b = guardFind(to);
722 if (a == b) return a;
723 if (a.scratch == b.scratch) {
724 a.scratch++;
725 b.scratchObject = a;
726 return a;
727 }
728 if (a.scratch > b.scratch) {
729 b.scratchObject = a;
730 return a;
731 }
732 a.scratchObject = b;
733 return b;
734 }
735
736 /**
737 * find step of union/find for guard registers during unSSA
738 */
739 private Register guardFind(Register r) {
740 Register start = r;
741 if (VM.VerifyAssertions) VM._assert(r.scratchObject != null);
742 while (r.scratchObject != r) r = (Register) r.scratchObject;
743 while (start.scratchObject != r) {
744 start.scratchObject = r;
745 start = (Register) start.scratchObject;
746 }
747 return r;
748 }
749
750 /**
751 * Avoid potential lost copy and other associated problems by
752 * Sreedhar's naive translation from TSSA to CSSA. Guards are rather
753 * trivial to un-SSA so they have already been removed from the IR.
754 * This algorithm is very wasteful of registers so needs good
755 * coalescing.
756 * @param ir the IR to work upon
757 */
758 @SuppressWarnings("unused") // NB this was an aborted attempt to fix a bug in leave SSA
759 private static void normalizeSSA(IR ir) {
760 for (Instruction s = ir.firstInstructionInCodeOrder(),
761 sentinel = ir.lastInstructionInCodeOrder(),
762 nextInstr = null; s != sentinel; s = nextInstr) {
763 // cache so we don't process inserted instructions
764 nextInstr = s.nextInstructionInCodeOrder();
765 if (Phi.conforms(s) && !s.getBasicBlock().isExceptionHandlerBasicBlock()) {
766 // We ignore exception handler BBs as they cause problems when inserting copies
767 if (DEBUG) VM.sysWriteln("Processing " + s + " of basic block " + s.getBasicBlock());
768 // Does the phi instruction have an unreachable operand?
769 boolean hasUnreachable = false;
770 // 1. Naively copy source operands into predecessor blocks
771 for (int index = 0; index < Phi.getNumberOfPreds(s); index++) {
772 Operand op = Phi.getValue(s, index);
773 if (op.isRegister()) {
774 // Get rval
775 Register rval = op.asRegister().getRegister();
776 if (rval.isValidation()) {
777 continue; // ignore guards
778 } else {
779 // Make rval'
780 Register rvalPrime = ir.regpool.getReg(rval);
781 // Make copy instruction
782 Instruction copy = SSA.makeMoveInstruction(ir, rvalPrime, rval, op.getType());
783 // Insert a copy of rval to rval' in predBlock
784 BasicBlock pred = Phi.getPred(s, index).block;
785 pred.appendInstructionRespectingTerminalBranch(copy);
786 if (DEBUG) VM.sysWriteln("Inserted rval copy of " + copy + " into basic block " + pred);
787 // Rename rval to rval' in phi instruction
788 op.asRegister().setRegister(rvalPrime);
789 }
790 } else if (op instanceof UnreachableOperand) {
791 hasUnreachable = true;
792 }
793 }
794 // 2. Naively copy the result if there were no unreachable operands
795 if (!hasUnreachable) {
796 Operand op = Phi.getResult(s);
797 if (!op.isRegister()) {
798 // ignore heap operands
799 } else {
800 // Get lval
801 Register lval = op.asRegister().getRegister();
802 // Make lval'
803 Register lvalPrime = ir.regpool.getReg(lval);
804 // Make copy instruction
805 Instruction copy = SSA.makeMoveInstruction(ir, lval, lvalPrime, op.getType());
806 // Insert a copy of lval' to lval after phi instruction
807 s.insertAfter(copy);
808 // Rename lval to lval' in phi instruction
809 op.asRegister().setRegister(lvalPrime);
810 if (DEBUG) VM.sysWriteln("Inserted lval copy of " + copy + " after " + s);
811 }
812 }
813 }
814 }
815 }
816 }