SsaToRop.java revision 579d7739c53a2707ad711a2d2cae46d7d782f061
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.back; 18 19import com.android.dx.rop.code.BasicBlock; 20import com.android.dx.rop.code.BasicBlockList; 21import com.android.dx.rop.code.InsnList; 22import com.android.dx.rop.code.RegisterSpec; 23import com.android.dx.rop.code.RegisterSpecList; 24import com.android.dx.rop.code.Rop; 25import com.android.dx.rop.code.RopMethod; 26import com.android.dx.rop.code.Rops; 27import com.android.dx.ssa.BasicRegisterMapper; 28import com.android.dx.ssa.PhiInsn; 29import com.android.dx.ssa.RegisterMapper; 30import com.android.dx.ssa.SsaBasicBlock; 31import com.android.dx.ssa.SsaInsn; 32import com.android.dx.ssa.SsaMethod; 33import com.android.dx.util.Hex; 34import com.android.dx.util.IntList; 35 36import java.util.ArrayList; 37import java.util.Arrays; 38import java.util.BitSet; 39import java.util.Comparator; 40 41/** 42 * Converts a method in SSA form to ROP form. 43 */ 44public class SsaToRop { 45 /** local debug flag */ 46 private static final boolean DEBUG = false; 47 48 /** {@code non-null;} method to process */ 49 private final SsaMethod ssaMeth; 50 51 /** 52 * {@code true} if the converter should attempt to minimize 53 * the rop-form register count 54 */ 55 private final boolean minimizeRegisters; 56 57 /** {@code non-null;} interference graph */ 58 private final InterferenceGraph interference; 59 60 /** 61 * Converts a method in SSA form to ROP form. 62 * 63 * @param ssaMeth {@code non-null;} method to process 64 * @param minimizeRegisters {@code true} if the converter should 65 * attempt to minimize the rop-form register count 66 * @return {@code non-null;} rop-form output 67 */ 68 public static RopMethod convertToRopMethod(SsaMethod ssaMeth, 69 boolean minimizeRegisters) { 70 return new SsaToRop(ssaMeth, minimizeRegisters).convert(); 71 } 72 73 /** 74 * Constructs an instance. 75 * 76 * @param ssaMeth {@code non-null;} method to process 77 * @param minimizeRegisters {@code true} if the converter should 78 * attempt to minimize the rop-form register count 79 */ 80 private SsaToRop(SsaMethod ssaMethod, boolean minimizeRegisters) { 81 this.minimizeRegisters = minimizeRegisters; 82 this.ssaMeth = ssaMethod; 83 this.interference = 84 LivenessAnalyzer.constructInterferenceGraph(ssaMethod); 85 } 86 87 /** 88 * Performs the conversion. 89 * 90 * @return {@code non-null;} rop-form output 91 */ 92 private RopMethod convert() { 93 if (DEBUG) { 94 interference.dumpToStdout(); 95 } 96 97 // These are other allocators for debugging or historical comparison: 98 // allocator = new NullRegisterAllocator(ssaMeth, interference); 99 // allocator = new FirstFitAllocator(ssaMeth, interference); 100 101 RegisterAllocator allocator = 102 new FirstFitLocalCombiningAllocator(ssaMeth, interference, 103 minimizeRegisters); 104 105 RegisterMapper mapper = allocator.allocateRegisters(); 106 107 if (DEBUG) { 108 System.out.println("Printing reg map"); 109 System.out.println(((BasicRegisterMapper)mapper).toHuman()); 110 } 111 112 ssaMeth.setBackMode(); 113 114 ssaMeth.mapRegisters(mapper); 115 116 removePhiFunctions(); 117 118 if (allocator.wantsParamsMovedHigh()) { 119 moveParametersToHighRegisters(); 120 } 121 122 removeEmptyGotos(); 123 124 RopMethod ropMethod = new RopMethod(convertBasicBlocks(), 125 ssaMeth.blockIndexToRopLabel(ssaMeth.getEntryBlockIndex())); 126 ropMethod = new IdenticalBlockCombiner(ropMethod).process(); 127 128 return ropMethod; 129 } 130 131 /** 132 * Removes all blocks containing only GOTOs from the control flow. 133 * Although much of this work will be done later when converting 134 * from rop to dex, not all simplification cases can be handled 135 * there. Furthermore, any no-op block between the exit block and 136 * blocks containing the real return or throw statements must be 137 * removed. 138 */ 139 private void removeEmptyGotos() { 140 final ArrayList<SsaBasicBlock> blocks = ssaMeth.getBlocks(); 141 142 ssaMeth.forEachBlockDepthFirst(false, new SsaBasicBlock.Visitor() { 143 public void visitBlock(SsaBasicBlock b, SsaBasicBlock parent) { 144 ArrayList<SsaInsn> insns = b.getInsns(); 145 146 if ((insns.size() == 1) 147 && (insns.get(0).getOpcode() == Rops.GOTO)) { 148 BitSet preds = (BitSet) b.getPredecessors().clone(); 149 150 for (int i = preds.nextSetBit(0); i >= 0; 151 i = preds.nextSetBit(i + 1)) { 152 SsaBasicBlock pb = blocks.get(i); 153 pb.replaceSuccessor(b.getIndex(), 154 b.getPrimarySuccessorIndex()); 155 } 156 } 157 } 158 }); 159 } 160 161 /** 162 * See Appel 19.6. To remove the phi instructions in an edge-split 163 * SSA representation we know we can always insert a move in a 164 * predecessor block. 165 */ 166 private void removePhiFunctions() { 167 ArrayList<SsaBasicBlock> blocks = ssaMeth.getBlocks(); 168 169 for (SsaBasicBlock block : blocks) { 170 // Add moves in all the pred blocks for each phi insn. 171 block.forEachPhiInsn(new PhiVisitor(blocks)); 172 173 // Delete the phi insns. 174 block.removeAllPhiInsns(); 175 } 176 177 /* 178 * After all move insns have been added, sort them so they don't 179 * destructively interfere. 180 */ 181 for (SsaBasicBlock block : blocks) { 182 block.scheduleMovesFromPhis(); 183 } 184 } 185 186 /** 187 * Helper for {@link #removePhiFunctions}: PhiSuccessorUpdater for 188 * adding move instructions to predecessors based on phi insns. 189 */ 190 private static class PhiVisitor implements PhiInsn.Visitor { 191 private final ArrayList<SsaBasicBlock> blocks; 192 193 public PhiVisitor(ArrayList<SsaBasicBlock> blocks) { 194 this.blocks = blocks; 195 } 196 197 public void visitPhiInsn(PhiInsn insn) { 198 RegisterSpecList sources = insn.getSources(); 199 RegisterSpec result = insn.getResult(); 200 int sz = sources.size(); 201 202 for (int i = 0; i < sz; i++) { 203 RegisterSpec source = sources.get(i); 204 SsaBasicBlock predBlock = blocks.get( 205 insn.predBlockIndexForSourcesIndex(i)); 206 207 predBlock.addMoveToEnd(result, source); 208 } 209 } 210 } 211 212 /** 213 * Moves the parameter registers, which allocateRegisters() places 214 * at the bottom of the frame, up to the top of the frame to match 215 * Dalvik calling convention. 216 */ 217 private void moveParametersToHighRegisters() { 218 int paramWidth = ssaMeth.getParamWidth(); 219 BasicRegisterMapper mapper 220 = new BasicRegisterMapper(ssaMeth.getRegCount()); 221 int regCount = ssaMeth.getRegCount(); 222 223 for (int i = 0; i < regCount; i++) { 224 if (i < paramWidth) { 225 mapper.addMapping(i, regCount - paramWidth + i, 1); 226 } else { 227 mapper.addMapping(i, i - paramWidth, 1); 228 } 229 } 230 231 if (DEBUG) { 232 System.out.printf("Moving %d registers from 0 to %d\n", 233 paramWidth, regCount - paramWidth); 234 } 235 236 ssaMeth.mapRegisters(mapper); 237 } 238 239 /** 240 * @return rop-form basic block list 241 */ 242 private BasicBlockList convertBasicBlocks() { 243 ArrayList<SsaBasicBlock> blocks = ssaMeth.getBlocks(); 244 245 // Exit block may be null. 246 SsaBasicBlock exitBlock = ssaMeth.getExitBlock(); 247 248 ssaMeth.computeReachability(); 249 int ropBlockCount = ssaMeth.getCountReachableBlocks(); 250 251 // Don't count the exit block, if it exists and is reachable. 252 ropBlockCount -= (exitBlock != null && exitBlock.isReachable()) ? 1 : 0; 253 254 BasicBlockList result = new BasicBlockList(ropBlockCount); 255 256 // Convert all the reachable blocks except the exit block. 257 int ropBlockIndex = 0; 258 for (SsaBasicBlock b : blocks) { 259 if (b.isReachable() && b != exitBlock) { 260 result.set(ropBlockIndex++, convertBasicBlock(b)); 261 } 262 } 263 264 // The exit block, which is discarded, must do nothing. 265 if (exitBlock != null && exitBlock.getInsns().size() != 0) { 266 throw new RuntimeException( 267 "Exit block must have no insns when leaving SSA form"); 268 } 269 270 return result; 271 } 272 273 /** 274 * Validates that a basic block is a valid end predecessor. It must 275 * end in a RETURN or a THROW. Throws a runtime exception on error. 276 * 277 * @param b {@code non-null;} block to validate 278 * @throws RuntimeException on error 279 */ 280 private void verifyValidExitPredecessor(SsaBasicBlock b) { 281 ArrayList<SsaInsn> insns = b.getInsns(); 282 SsaInsn lastInsn = insns.get(insns.size() - 1); 283 Rop opcode = lastInsn.getOpcode(); 284 285 if (opcode.getBranchingness() != Rop.BRANCH_RETURN 286 && opcode != Rops.THROW) { 287 throw new RuntimeException("Exit predecessor must end" 288 + " in valid exit statement."); 289 } 290 } 291 292 /** 293 * Converts a single basic block to rop form. 294 * 295 * @param block SSA block to process 296 * @return {@code non-null;} ROP block 297 */ 298 private BasicBlock convertBasicBlock(SsaBasicBlock block) { 299 IntList successorList = block.getRopLabelSuccessorList(); 300 int primarySuccessorLabel = block.getPrimarySuccessorRopLabel(); 301 302 // Filter out any reference to the SSA form's exit block. 303 304 // Exit block may be null. 305 SsaBasicBlock exitBlock = ssaMeth.getExitBlock(); 306 int exitRopLabel = (exitBlock == null) ? -1 : exitBlock.getRopLabel(); 307 308 if (successorList.contains(exitRopLabel)) { 309 if (successorList.size() > 1) { 310 throw new RuntimeException( 311 "Exit predecessor must have no other successors" 312 + Hex.u2(block.getRopLabel())); 313 } else { 314 successorList = IntList.EMPTY; 315 primarySuccessorLabel = -1; 316 317 verifyValidExitPredecessor(block); 318 } 319 } 320 321 successorList.setImmutable(); 322 323 BasicBlock result = new BasicBlock( 324 block.getRopLabel(), convertInsns(block.getInsns()), 325 successorList, 326 primarySuccessorLabel); 327 328 return result; 329 } 330 331 /** 332 * Converts an insn list to rop form. 333 * 334 * @param ssaInsns {@code non-null;} old instructions 335 * @return {@code non-null;} immutable instruction list 336 */ 337 private InsnList convertInsns(ArrayList<SsaInsn> ssaInsns) { 338 int insnCount = ssaInsns.size(); 339 InsnList result = new InsnList(insnCount); 340 341 for (int i = 0; i < insnCount; i++) { 342 result.set(i, ssaInsns.get(i).toRopInsn()); 343 } 344 345 result.setImmutable(); 346 347 return result; 348 } 349 350 /** 351 * <b>Note:</b> This method is not presently used. 352 * 353 * @return a list of registers ordered by most-frequently-used to 354 * least-frequently-used. Each register is listed once and only 355 * once. 356 */ 357 public int[] getRegistersByFrequency() { 358 int regCount = ssaMeth.getRegCount(); 359 Integer[] ret = new Integer[regCount]; 360 361 for (int i = 0; i < regCount; i++) { 362 ret[i] = i; 363 } 364 365 Arrays.sort(ret, new Comparator<Integer>() { 366 public int compare(Integer o1, Integer o2) { 367 return ssaMeth.getUseListForRegister(o2).size() 368 - ssaMeth.getUseListForRegister(o1).size(); 369 } 370 }); 371 372 int result[] = new int[regCount]; 373 374 for (int i = 0; i < regCount; i++) { 375 result[i] = ret[i]; 376 } 377 378 return result; 379 } 380} 381