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 java.util.Enumeration;
016 import org.jikesrvm.VM;
017 import org.jikesrvm.classloader.TypeReference;
018 import org.jikesrvm.compilers.opt.ir.BBend;
019 import org.jikesrvm.compilers.opt.ir.Move;
020 import org.jikesrvm.compilers.opt.ir.BasicBlock;
021 import org.jikesrvm.compilers.opt.ir.BasicBlockEnumeration;
022 import org.jikesrvm.compilers.opt.ir.IR;
023 import org.jikesrvm.compilers.opt.ir.IRTools;
024 import org.jikesrvm.compilers.opt.ir.Instruction;
025 import org.jikesrvm.compilers.opt.ir.InstructionEnumeration;
026 import org.jikesrvm.compilers.opt.ir.OperandEnumeration;
027 import org.jikesrvm.compilers.opt.ir.Operator;
028
029 import static org.jikesrvm.compilers.opt.driver.OptConstants.SSA_SYNTH_BCI;
030 import static org.jikesrvm.compilers.opt.ir.Operators.PHI;
031 import org.jikesrvm.compilers.opt.ir.Register;
032 import org.jikesrvm.compilers.opt.ir.Phi;
033 import org.jikesrvm.compilers.opt.ir.operand.BasicBlockOperand;
034 import org.jikesrvm.compilers.opt.ir.operand.ConstantOperand;
035 import org.jikesrvm.compilers.opt.ir.operand.HeapOperand;
036 import org.jikesrvm.compilers.opt.ir.operand.Operand;
037 import org.jikesrvm.compilers.opt.ir.operand.RegisterOperand;
038
039 /**
040 * This module holds utility functions for SSA form.
041 *
042 * Our SSA form is <em> Heap Array SSA Form </em>, an extension of
043 * SSA that allows analysis of scalars, arrays, and object fields
044 * in a unified framework. See our SAS 2000 paper
045 * <a href="http://www.research.ibm.com/jalapeno/publication.html#sas00">
046 * Unified Analysis of Arrays and Object References in Strongly Typed
047 * Languages </a>
048 * <p> Details about our current implementation include:
049 * <ul>
050 * <li> We explicitly place phi-functions as instructions in the IR.
051 * <li> Scalar registers are explicitly renamed in the IR.
052 * <li> Heap variables are represented implicitly. Each instruction
053 * that reads or writes from the heap implicitly uses a Heap variable.
054 * The particular heap variable for each instruction is cached
055 * in {@link SSADictionary <code> ir.HIRInfo.dictionary </code>}.
056 * dphi functions do <em> not </em>
057 * explicitly appear in the IR.
058 * <p>
059 * For example, consider the code:
060 * <p>
061 * <pre>
062 * a.x = z;
063 * b[100] = 5;
064 * y = a.x;
065 * </pre>
066 *
067 * <p>Logically, we translate to Array SSA form (before renumbering) as:
068 * <pre>
069 * HEAP_x[a] = z
070 * HEAP_x = dphi(HEAP_x,HEAP_x)
071 * HEAP_I[] = { < b,100,5 > }
072 * HEAP_I[] = dphi(HEAP_I[], HEAP_I[])
073 * y = HEAP_x[a]
074 * </pre>
075 *
076 * <p> However, the implementation does not actually modify the instruction
077 * stream. Instead, we keep track of the following information with
078 * <code> ir.HIRInfo.dictionary </code>:
079 * <pre>
080 * a.x = z (implicit: reads HEAP_x, writes HEAP_x)
081 * b[100] =5 (implicit: reads HEAP_I[], writes HEAP_I[])
082 * y = a.x (implicit: reads HEAP_x)
083 * </pre>
084 *
085 * <p>Similarly, phi functions for the implicit heap
086 * variables <em> will not </em>
087 * appear explicitly in the instruction stream. Instead, the
088 * SSADictionary data structure keeps the heap control phi
089 * functions for each basic block in a lookaside table.
090 * </ul>
091 *
092 * @see EnterSSA
093 * @see LeaveSSA
094 * @see SSADictionary
095 * @see org.jikesrvm.compilers.opt.ir.HIRInfo
096 */
097 class SSA {
098
099 /**
100 * Add a move instruction at the end of a basic block, renaming
101 * with a temporary register if needed to protect conditional branches
102 * at the end of the block.
103 *
104 * @param ir governing IR
105 * @param bb the basic block
106 * @param c the move instruction to insert
107 * @param exp whether or not to respect exception control flow at the
108 * end of the block
109 */
110 static void addAtEnd(IR ir, BasicBlock bb, Instruction c, boolean exp) {
111 if (exp) {
112 bb.appendInstructionRespectingTerminalBranchOrPEI(c);
113 } else {
114 bb.appendInstructionRespectingTerminalBranch(c);
115 }
116 RegisterOperand aux = null;
117 if (VM.VerifyAssertions) {
118 VM._assert(Move.conforms(c));
119 }
120 RegisterOperand lhs = Move.getResult(c);
121 Instruction i = c.nextInstructionInCodeOrder();
122 while (!BBend.conforms(i)) {
123 OperandEnumeration os = i.getUses();
124 while (os.hasMoreElements()) {
125 Operand op = os.next();
126 if (lhs.similar(op)) {
127 if (aux == null) {
128 aux = ir.regpool.makeTemp(lhs);
129 c.insertBefore(makeMoveInstruction(ir, aux.getRegister(), lhs.getRegister(), lhs.getType()));
130 }
131 op.asRegister().setRegister(aux.getRegister());
132 }
133 }
134 i = i.nextInstructionInCodeOrder();
135 }
136 }
137
138 /**
139 * Print the instructions in SSA form.
140 *
141 * @param ir the IR, assumed to be in SSA form
142 */
143 public static void printInstructions(IR ir) {
144 SSADictionary dictionary = ir.HIRInfo.dictionary;
145 System.out.println("********* START OF IR DUMP in SSA FOR " + ir.method);
146 for (BasicBlockEnumeration be = ir.forwardBlockEnumerator(); be.hasMoreElements();) {
147 BasicBlock bb = be.next();
148 // print the explicit instructions for basic block bb
149 for (Enumeration<Instruction> e = dictionary.getAllInstructions(bb); e.hasMoreElements();) {
150 Instruction s = e.nextElement();
151 System.out.print(s.bcIndex + "\t" + s);
152 if (dictionary.defsHeapVariable(s) && s.operator != PHI) {
153 System.out.print(" (Implicit Defs: ");
154 HeapOperand<?>[] defs = dictionary.getHeapDefs(s);
155 if (defs != null) {
156 for (HeapOperand<?> def : defs) System.out.print(def + " ");
157 }
158 System.out.print(" )");
159 }
160 if (dictionary.usesHeapVariable(s) && s.operator != PHI) {
161 System.out.print(" (Implicit Uses: ");
162 HeapOperand<?>[] uses = dictionary.getHeapUses(s);
163 if (uses != null) {
164 for (HeapOperand<?> use : uses) System.out.print(use + " ");
165 }
166 System.out.print(" )");
167 }
168 System.out.print("\n");
169 }
170 }
171 System.out.println("********* END OF IR DUMP in SSA FOR " + ir.method);
172 }
173
174 /**
175 * Create a move instruction r1 := r2.
176 *
177 * TODO: This utility function should be moved elsewhere.
178 *
179 * @param ir the governing ir
180 * @param r1 the destination
181 * @param r2 the source
182 * @param t the type of r1 and r2.
183 */
184 static Instruction makeMoveInstruction(IR ir, Register r1, Register r2, TypeReference t) {
185 Operator mv = IRTools.getMoveOp(t);
186 RegisterOperand o1 = new RegisterOperand(r1, t);
187 RegisterOperand o2 = new RegisterOperand(r2, t);
188 Instruction s = Move.create(mv, o1, o2);
189 s.position = ir.gc.inlineSequence;
190 s.bcIndex = SSA_SYNTH_BCI;
191 return s;
192 }
193
194 /**
195 * Create a move instruction r1 := c.
196 *
197 * !!TODO: put this functionality elsewhere.
198 *
199 * @param ir the governing ir
200 * @param r1 the destination
201 * @param c the source
202 */
203 static Instruction makeMoveInstruction(IR ir, Register r1, ConstantOperand c) {
204 Operator mv = IRTools.getMoveOp(c.getType());
205 RegisterOperand o1 = new RegisterOperand(r1, c.getType());
206 Operand o2 = c.copy();
207 Instruction s = Move.create(mv, o1, o2);
208 s.position = ir.gc.inlineSequence;
209 s.bcIndex = SSA_SYNTH_BCI;
210 return s;
211 }
212
213 /**
214 * Fix up any PHI instructions in the given target block to reflect that
215 * the given source block is no longer a predecessor of target.
216 * The basic algorithm is to erase the PHI operands related to the edge
217 * from source to target by sliding the other PHI operands down as required.
218 *
219 * @param source the source block to remove from PHIs in target
220 * @param target the target block that may contain PHIs to update.
221 */
222 static void purgeBlockFromPHIs(BasicBlock source, BasicBlock target) {
223 for (InstructionEnumeration e = target.forwardRealInstrEnumerator(); e.hasMoreElements();) {
224 Instruction s = e.next();
225 if (s.operator() != PHI) return; // all done (assume PHIs are first!)
226 int numPairs = Phi.getNumberOfPreds(s);
227 int dst = 0;
228 for (int src = 0; src < numPairs; src++) {
229 BasicBlockOperand bbop = Phi.getPred(s, src);
230 if (bbop.block == source) {
231 Phi.setValue(s, src, null);
232 Phi.setPred(s, src, null);
233 } else {
234 if (src != dst) {
235 Phi.setValue(s, dst, Phi.getClearValue(s, src));
236 Phi.setPred(s, dst, Phi.getClearPred(s, src));
237 }
238 dst++;
239 }
240 }
241 for (int i = dst; i < numPairs; i++) {
242 Phi.setValue(s, i, null);
243 Phi.setPred(s, i, null);
244 }
245 }
246 }
247
248 /**
249 * Update PHI instructions in the target block so that any PHIs that
250 * come from basic block B1, now come from basic block B2.
251 *
252 * @param target the target block that may contain PHIs to update.
253 * @param B1 the block to replace in the phi instructions
254 * @param B2 the replacement block for B1
255 */
256 static void replaceBlockInPhis(BasicBlock target, BasicBlock B1, BasicBlock B2) {
257 for (InstructionEnumeration e = target.forwardRealInstrEnumerator(); e.hasMoreElements();) {
258 Instruction s = e.next();
259 if (s.operator() != PHI) return; // all done (assume PHIs are first!)
260 int numPairs = Phi.getNumberOfPreds(s);
261 for (int src = 0; src < numPairs; src++) {
262 BasicBlockOperand bbop = Phi.getPred(s, src);
263 if (bbop.block == B1) {
264 Phi.setPred(s, src, new BasicBlockOperand(B2));
265 }
266 }
267 }
268 }
269 }