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 */ 013package org.jikesrvm.compilers.opt.ssa; 014 015import java.util.Enumeration; 016import org.jikesrvm.VM; 017import org.jikesrvm.classloader.TypeReference; 018import org.jikesrvm.compilers.opt.ir.BBend; 019import org.jikesrvm.compilers.opt.ir.Move; 020import org.jikesrvm.compilers.opt.ir.BasicBlock; 021import org.jikesrvm.compilers.opt.ir.IR; 022import org.jikesrvm.compilers.opt.ir.IRTools; 023import org.jikesrvm.compilers.opt.ir.Instruction; 024import org.jikesrvm.compilers.opt.ir.Operator; 025 026import static org.jikesrvm.compilers.opt.driver.OptConstants.SSA_SYNTH_BCI; 027import static org.jikesrvm.compilers.opt.ir.Operators.PHI; 028import org.jikesrvm.compilers.opt.ir.Register; 029import org.jikesrvm.compilers.opt.ir.Phi; 030import org.jikesrvm.compilers.opt.ir.operand.BasicBlockOperand; 031import org.jikesrvm.compilers.opt.ir.operand.ConstantOperand; 032import org.jikesrvm.compilers.opt.ir.operand.HeapOperand; 033import org.jikesrvm.compilers.opt.ir.operand.Operand; 034import 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 org.jikesrvm.compilers.opt.ir.HIRInfo#dictionary} which 053 * is reachable via the IR object. 054 * 055 * dphi functions do <em> not </em> 056 * explicitly appear in the IR. 057 * <p> 058 * For example, consider the code: 059 * <pre> 060 * a.x = z; 061 * b[100] = 5; 062 * y = a.x; 063 * </pre> 064 * 065 * <p>Logically, we translate to Array SSA form (before renumbering) as: 066 * <pre> 067 * HEAP_x[a] = z 068 * HEAP_x = dphi(HEAP_x,HEAP_x) 069 * HEAP_I[] = { < b,100,5 > } 070 * HEAP_I[] = dphi(HEAP_I[], HEAP_I[]) 071 * y = HEAP_x[a] 072 * </pre> 073 * 074 * <p> However, the implementation does not actually modify the instruction 075 * stream. Instead, we keep track of the following information with 076 * <code> ir.HIRInfo.dictionary </code>: 077 * <pre> 078 * a.x = z (implicit: reads HEAP_x, writes HEAP_x) 079 * b[100] =5 (implicit: reads HEAP_I[], writes HEAP_I[]) 080 * y = a.x (implicit: reads HEAP_x) 081 * </pre> 082 * 083 * <p>Similarly, phi functions for the implicit heap 084 * variables <em> will not </em> 085 * appear explicitly in the instruction stream. Instead, the 086 * SSADictionary data structure keeps the heap control phi 087 * functions for each basic block in a lookaside table. 088 * </ul> 089 * 090 * @see EnterSSA 091 * @see LeaveSSA 092 * @see SSADictionary 093 * @see org.jikesrvm.compilers.opt.ir.HIRInfo 094 */ 095class SSA { 096 097 /** 098 * Add a move instruction at the end of a basic block, renaming 099 * with a temporary register if needed to protect conditional branches 100 * at the end of the block. 101 * 102 * @param ir governing IR 103 * @param bb the basic block 104 * @param c the move instruction to insert 105 * @param exp whether or not to respect exception control flow at the 106 * end of the block 107 */ 108 static void addAtEnd(IR ir, BasicBlock bb, Instruction c, boolean exp) { 109 if (exp) { 110 bb.appendInstructionRespectingTerminalBranchOrPEI(c); 111 } else { 112 bb.appendInstructionRespectingTerminalBranch(c); 113 } 114 RegisterOperand aux = null; 115 if (VM.VerifyAssertions) { 116 VM._assert(Move.conforms(c)); 117 } 118 RegisterOperand lhs = Move.getResult(c); 119 Instruction i = c.nextInstructionInCodeOrder(); 120 while (!BBend.conforms(i)) { 121 Enumeration<Operand> os = i.getUses(); 122 while (os.hasMoreElements()) { 123 Operand op = os.nextElement(); 124 if (lhs.similar(op)) { 125 if (aux == null) { 126 aux = ir.regpool.makeTemp(lhs); 127 c.insertBefore(makeMoveInstruction(ir, aux.getRegister(), lhs.getRegister(), lhs.getType())); 128 } 129 op.asRegister().setRegister(aux.getRegister()); 130 } 131 } 132 i = i.nextInstructionInCodeOrder(); 133 } 134 } 135 136 /** 137 * Print the instructions in SSA form. 138 * 139 * @param ir the IR, assumed to be in SSA form 140 */ 141 public static void printInstructions(IR ir) { 142 SSADictionary dictionary = ir.HIRInfo.dictionary; 143 System.out.println("********* START OF IR DUMP in SSA FOR " + ir.method); 144 for (Enumeration<BasicBlock> be = ir.forwardBlockEnumerator(); be.hasMoreElements();) { 145 BasicBlock bb = be.nextElement(); 146 // print the explicit instructions for basic block bb 147 for (Enumeration<Instruction> e = dictionary.getAllInstructions(bb); e.hasMoreElements();) { 148 Instruction s = e.nextElement(); 149 System.out.print(s.bcIndex + "\t" + s); 150 if (dictionary.defsHeapVariable(s) && s.operator() != PHI) { 151 System.out.print(" (Implicit Defs: "); 152 HeapOperand<?>[] defs = dictionary.getHeapDefs(s); 153 if (defs != null) { 154 for (HeapOperand<?> def : defs) System.out.print(def + " "); 155 } 156 System.out.print(" )"); 157 } 158 if (dictionary.usesHeapVariable(s) && s.operator() != PHI) { 159 System.out.print(" (Implicit Uses: "); 160 HeapOperand<?>[] uses = dictionary.getHeapUses(s); 161 if (uses != null) { 162 for (HeapOperand<?> use : uses) System.out.print(use + " "); 163 } 164 System.out.print(" )"); 165 } 166 System.out.print('\n'); 167 } 168 } 169 System.out.println("********* END OF IR DUMP in SSA FOR " + ir.method); 170 } 171 172 /** 173 * Create a move instruction r1 := r2.<p> 174 * 175 * TODO: This utility function should be moved elsewhere. 176 * 177 * @param ir the governing ir 178 * @param r1 the destination 179 * @param r2 the source 180 * @param t the type of r1 and r2. 181 * @return the created move instruction 182 */ 183 static Instruction makeMoveInstruction(IR ir, Register r1, Register r2, TypeReference t) { 184 Operator mv = IRTools.getMoveOp(t); 185 RegisterOperand o1 = new RegisterOperand(r1, t); 186 RegisterOperand o2 = new RegisterOperand(r2, t); 187 Instruction s = Move.create(mv, o1, o2); 188 s.position = ir.gc.getInlineSequence(); 189 s.bcIndex = SSA_SYNTH_BCI; 190 return s; 191 } 192 193 /** 194 * Create a move instruction r1 := c.<p> 195 * 196 * !!TODO: put this functionality elsewhere. 197 * 198 * @param ir the governing ir 199 * @param r1 the destination 200 * @param c the source 201 * @return the created move instruction 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.getInlineSequence(); 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 (Enumeration<Instruction> e = target.forwardRealInstrEnumerator(); e.hasMoreElements();) { 224 Instruction s = e.nextElement(); 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 (Enumeration<Instruction> e = target.forwardRealInstrEnumerator(); e.hasMoreElements();) { 258 Instruction s = e.nextElement(); 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}