SsaConverter.java revision 99409883d9c4c0ffb49b070ce307bb33a9dfe9f1
1/* 2 * Copyright (C) 2007 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17package com.android.dx.ssa; 18 19import com.android.dx.rop.code.RegisterSpec; 20import com.android.dx.rop.code.RopMethod; 21import com.android.dx.util.IntIterator; 22 23import java.util.ArrayList; 24import java.util.BitSet; 25 26/** 27 * Converts ROP methods to SSA Methods 28 */ 29public class SsaConverter { 30 public static boolean DEBUG = false; 31 32 /** 33 * returns an SSA representation, edge-split and with phi functions placed 34 * @param rmeth input 35 * @param paramWidth the total width, in register-units, of the method's 36 * parameters 37 * @param isStatic true if this method has no 'this' 38 * pointer argument 39 * @return output in SSA form 40 */ 41 public static SsaMethod convertToSsaMethod(RopMethod rmeth, 42 int paramWidth, boolean isStatic) { 43 SsaMethod result; 44 45 result = SsaMethod.newFromRopMethod(rmeth, paramWidth, isStatic); 46 47 edgeSplit(result); 48 49 LocalVariableInfo localInfo = LocalVariableExtractor.extract(result); 50 51 placePhiFunctions(result, localInfo); 52 new SsaRenamer(result).run(); 53 54 /* 55 * Exit block, added here, is not considered for edge splitting 56 * or phi placement since no actual control flows to it. 57 */ 58 result.makeExitBlock(); 59 60 return result; 61 } 62 63 /** 64 * Returns an SSA represention with only the edge-splitter run. 65 * @param rmeth method to process 66 * @param paramWidth width of all arguments in the method 67 * @param isStatic true if this method has no 'this' pointer argument 68 * @return an SSA represention with only the edge-splitter run. 69 */ 70 public static SsaMethod testEdgeSplit (RopMethod rmeth, int paramWidth, 71 boolean isStatic) { 72 SsaMethod result; 73 74 result = SsaMethod.newFromRopMethod(rmeth, paramWidth, isStatic); 75 76 edgeSplit(result); 77 return result; 78 } 79 80 /** 81 * Returns an SSA represention with only the steps through the 82 * phi placement run. 83 * @param rmeth method to process 84 * @param paramWidth width of all arguments in the method 85 * @param isStatic true if this method has no 'this' pointer argument 86 * @return an SSA represention with only the edge-splitter run. 87 */ 88 public static SsaMethod testPhiPlacement (RopMethod rmeth, int paramWidth, 89 boolean isStatic) { 90 SsaMethod result; 91 92 result = SsaMethod.newFromRopMethod(rmeth, paramWidth, isStatic); 93 94 edgeSplit(result); 95 96 LocalVariableInfo localInfo = LocalVariableExtractor.extract(result); 97 98 placePhiFunctions(result, localInfo); 99 return result; 100 } 101 102 /** 103 * See Appel section 19.1 104 * Converts CFG into "edge-split" form, such that each node either a 105 * unique successor or unique predecessor.<p> 106 * 107 * In addition, the SSA form we use enforces a further constraint, 108 * requiring each block with a final instruction that returns a 109 * value to have a primary successor that has no other 110 * predecessor. This ensures move statements can always be 111 * inserted correctly when phi statements are removed. 112 * 113 * @param result method to process 114 */ 115 private static void edgeSplit(SsaMethod result) { 116 117 edgeSplitPredecessors(result); 118 edgeSplitMoveExceptionsAndResults(result); 119 edgeSplitSuccessors(result); 120 } 121 122 /** 123 * Inserts Z nodes as new predecessors for every node that has multiple 124 * successors and multiple predecessors. 125 * @param result {@code non-null;} method to process 126 */ 127 private static void edgeSplitPredecessors(SsaMethod result) { 128 ArrayList<SsaBasicBlock> blocks = result.getBlocks(); 129 130 // New blocks are added to the end of the block list during 131 // this iteration 132 for (int i = blocks.size() - 1; i >= 0; i-- ) { 133 SsaBasicBlock block = blocks.get(i); 134 if (nodeNeedsUniquePredecessor(block)) { 135 block.insertNewPredecessor(); 136 } 137 } 138 } 139 140 /** 141 * @param block {@code non-null;} block in question 142 * @return true if this node needs to have a unique predecessor created for 143 * it. 144 */ 145 private static boolean nodeNeedsUniquePredecessor(SsaBasicBlock block) { 146 147 /* 148 * Any block with that has both multiple successors and multiple 149 * predecessors needs a new predecessor node. 150 */ 151 152 int countPredecessors = block.getPredecessors().cardinality(); 153 int countSuccessors = block.getSuccessors().cardinality(); 154 155 return (countPredecessors > 1 && countSuccessors > 1); 156 } 157 158 /** 159 * In ROP form, move-exception must occur as the first insn in a block 160 * immediately succeeding the insn that could thrown an exception. 161 * We may need room to insert move insns later, so make sure to split 162 * any block that starts with a move-exception such that there is a 163 * unique move-exception block for each predecessor. 164 * @param ssaMeth method to process 165 */ 166 private static void edgeSplitMoveExceptionsAndResults(SsaMethod ssaMeth) { 167 ArrayList<SsaBasicBlock> blocks = ssaMeth.getBlocks(); 168 169 // New blocks are added to the end of the block list during 170 // this iteration 171 for (int i = blocks.size() - 1; i >= 0; i-- ) { 172 SsaBasicBlock block = blocks.get(i); 173 174 // Any block that starts with a move-exception and has more than 175 // one predecessor... 176 if (!block.isExitBlock() 177 && block.getPredecessors().cardinality() > 1 178 && block.getInsns().get(0).isMoveException()) { 179 180 // block.getPredecessors() is changed in the loop below 181 BitSet preds = (BitSet)block.getPredecessors().clone(); 182 for (int j = preds.nextSetBit(0); j >= 0; 183 j = preds.nextSetBit(j + 1)) { 184 185 SsaBasicBlock predecessor = blocks.get(j); 186 187 SsaBasicBlock zNode = predecessor.insertNewSuccessor(block); 188 189 // Make sure to place the move-exception as the 190 // first insn... 191 zNode.getInsns().add(0, block.getInsns().get(0).clone()); 192 } 193 194 // remove the move-exception from the original block... 195 block.getInsns().remove(0); 196 } 197 } 198 } 199 200 /** 201 * Inserts Z nodes for every node that needs a new 202 * successor. 203 * @param result {@code non-null;} method to process 204 */ 205 private static void edgeSplitSuccessors(SsaMethod result) { 206 ArrayList<SsaBasicBlock> blocks = result.getBlocks(); 207 208 // New blocks are added to the end of the block list during 209 // this iteration 210 for (int i = blocks.size() - 1; i >= 0; i-- ) { 211 SsaBasicBlock block = blocks.get(i); 212 213 // successors list is modified in loop below 214 BitSet successors = (BitSet)block.getSuccessors().clone(); 215 for(int j = successors.nextSetBit(0); 216 j >= 0; j = successors.nextSetBit(j+1)) { 217 218 SsaBasicBlock succ = blocks.get(j); 219 220 if (needsNewSuccessor(block, succ)) { 221 block.insertNewSuccessor(succ); 222 } 223 } 224 } 225 } 226 227 /** 228 * Returns true if block and successor need a Z-node between them. 229 * Presently, this is true if the final instruction has any sources 230 * or results and the current successor block has more than one 231 * predecessor. 232 * @param block predecessor node 233 * @param succ successor node 234 * @return true if a Z node is needed 235 */ 236 private static boolean needsNewSuccessor(SsaBasicBlock block, 237 SsaBasicBlock succ) { 238 239 ArrayList<SsaInsn> insns = block.getInsns(); 240 SsaInsn lastInsn = insns.get(insns.size() - 1); 241 242 return ((lastInsn.getResult() != null) 243 || (lastInsn.getSources().size() > 0)) 244 && succ.getPredecessors().cardinality() > 1; 245 } 246 247 /** 248 * See Appel algorithm 19.6 249 * Place Phi functions in appropriate locations. 250 * 251 * @param ssaMeth {@code non-null;} method to process. Modifications made in-place 252 * @param localInfo {@code non-null;} Local variable info, used when placing phis 253 */ 254 private static void placePhiFunctions (SsaMethod ssaMeth, 255 LocalVariableInfo localInfo) { 256 ArrayList<SsaBasicBlock> ssaBlocks; 257 int regCount; 258 int blockCount; 259 260 ssaBlocks = ssaMeth.getBlocks(); 261 blockCount = ssaBlocks.size(); 262 regCount = ssaMeth.getRegCount(); 263 264 DomFront df = new DomFront(ssaMeth); 265 DomFront.DomInfo[] domInfos = df.run(); 266 267 // Bit set of registers vs block index "definition sites" 268 BitSet[] defsites = new BitSet[regCount]; 269 270 // Bit set of registers vs block index "phi placement sites" 271 BitSet[] phisites = new BitSet[regCount]; 272 273 for (int i = 0; i < regCount; i++) { 274 defsites[i] = new BitSet(blockCount); 275 phisites[i] = new BitSet(blockCount); 276 } 277 278 /* 279 * For each register, build a set of all basic blocks where 280 * containing an assignment to that register. 281 */ 282 for (int bi = 0, s = ssaBlocks.size(); bi < s; bi++) { 283 SsaBasicBlock b = ssaBlocks.get(bi); 284 285 for (SsaInsn insn: b.getInsns()) { 286 287 RegisterSpec rs = insn.getResult(); 288 289 if (rs != null) { 290 defsites[rs.getReg()].set(bi); 291 } 292 } 293 } 294 295 if (DEBUG) { 296 System.out.println("defsites"); 297 298 for (int i = 0; i < regCount; i++) { 299 StringBuilder sb = new StringBuilder(); 300 301 sb.append('v').append(i).append(": "); 302 303 sb.append(defsites[i].toString()); 304 305 System.out.println(sb); 306 } 307 } 308 309 BitSet worklist; 310 311 /* 312 * For each register, compute all locations for phi placement 313 * based on dominance-frontier algorithm. 314 */ 315 for (int reg = 0, s = ssaMeth.getRegCount() ; reg < s ; reg++ ) { 316 int workBlockIndex; 317 318 /* Worklist set starts out with each node where reg is assigned */ 319 320 worklist = (BitSet)(defsites[reg].clone()); 321 322 while (0 <= (workBlockIndex = worklist.nextSetBit(0))) { 323 worklist.clear(workBlockIndex); 324 IntIterator dfIterator 325 = domInfos[workBlockIndex] 326 .dominanceFrontiers.iterator(); 327 328 while (dfIterator.hasNext()) { 329 int dfBlockIndex = dfIterator.next(); 330 331 if (!phisites[reg].get(dfBlockIndex)) { 332 phisites[reg].set(dfBlockIndex); 333 334 RegisterSpec rs 335 = localInfo.getStarts(dfBlockIndex).get(reg); 336 337 if (rs == null) { 338 ssaBlocks.get(dfBlockIndex).addPhiInsnForReg(reg); 339 } else { 340 ssaBlocks.get(dfBlockIndex).addPhiInsnForReg(rs); 341 } 342 343 if (!defsites[reg].get(dfBlockIndex)) { 344 worklist.set(dfBlockIndex); 345 } 346 } 347 } 348 } 349 } 350 351 if (DEBUG) { 352 System.out.println("phisites"); 353 354 for (int i = 0; i < regCount; i++) { 355 StringBuilder sb = new StringBuilder(); 356 357 sb.append('v').append(i).append(": "); 358 359 sb.append(phisites[i].toString()); 360 361 System.out.println(sb); 362 } 363 } 364 } 365} 366