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