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