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