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