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 17 package com.android.dx.cf.code; 18 19 import com.android.dx.rop.cst.Constant; 20 import com.android.dx.rop.cst.CstMemberRef; 21 import com.android.dx.rop.cst.CstString; 22 import com.android.dx.rop.cst.CstType; 23 import com.android.dx.rop.type.Type; 24 import com.android.dx.util.Bits; 25 import com.android.dx.util.IntList; 26 import java.util.ArrayList; 27 28 /** 29 * Utility that identifies basic blocks in bytecode. 30 */ 31 public final class BasicBlocker implements BytecodeArray.Visitor { 32 /** {@code non-null;} method being converted */ 33 private final ConcreteMethod method; 34 35 /** 36 * {@code non-null;} work set; bits indicate offsets in need of 37 * examination 38 */ 39 private final int[] workSet; 40 41 /** 42 * {@code non-null;} live set; bits indicate potentially-live 43 * opcodes; contrawise, a bit that isn't on is either in the 44 * middle of an instruction or is a definitely-dead opcode 45 */ 46 private final int[] liveSet; 47 48 /** 49 * {@code non-null;} block start set; bits indicate the starts of 50 * basic blocks, including the opcodes that start blocks of 51 * definitely-dead code 52 */ 53 private final int[] blockSet; 54 55 /** 56 * {@code non-null, sparse;} for each instruction offset to a branch of 57 * some sort, the list of targets for that instruction 58 */ 59 private final IntList[] targetLists; 60 61 /** 62 * {@code non-null, sparse;} for each instruction offset to a throwing 63 * instruction, the list of exception handlers for that instruction 64 */ 65 private final ByteCatchList[] catchLists; 66 67 /** offset of the previously parsed bytecode */ 68 private int previousOffset; 69 70 /** 71 * Identifies and enumerates the basic blocks in the given method, 72 * returning a list of them. The returned list notably omits any 73 * definitely-dead code that is identified in the process. 74 * 75 * @param method {@code non-null;} method to convert 76 * @return {@code non-null;} list of basic blocks 77 */ identifyBlocks(ConcreteMethod method)78 public static ByteBlockList identifyBlocks(ConcreteMethod method) { 79 BasicBlocker bb = new BasicBlocker(method); 80 81 bb.doit(); 82 return bb.getBlockList(); 83 } 84 85 /** 86 * Constructs an instance. This class is not publicly instantiable; use 87 * {@link #identifyBlocks}. 88 * 89 * @param method {@code non-null;} method to convert 90 */ BasicBlocker(ConcreteMethod method)91 private BasicBlocker(ConcreteMethod method) { 92 if (method == null) { 93 throw new NullPointerException("method == null"); 94 } 95 96 this.method = method; 97 98 /* 99 * The "+1" below is so the idx-past-end is also valid, 100 * avoiding a special case, but without preventing 101 * flow-of-control falling past the end of the method from 102 * getting properly reported. 103 */ 104 int sz = method.getCode().size() + 1; 105 106 workSet = Bits.makeBitSet(sz); 107 liveSet = Bits.makeBitSet(sz); 108 blockSet = Bits.makeBitSet(sz); 109 targetLists = new IntList[sz]; 110 catchLists = new ByteCatchList[sz]; 111 previousOffset = -1; 112 } 113 114 /* 115 * Note: These methods are defined implementation of the interface 116 * BytecodeArray.Visitor; since the class isn't publicly 117 * instantiable, no external code ever gets a chance to actually 118 * call these methods. 119 */ 120 121 /** {@inheritDoc} */ visitInvalid(int opcode, int offset, int length)122 public void visitInvalid(int opcode, int offset, int length) { 123 visitCommon(offset, length, true); 124 } 125 126 /** {@inheritDoc} */ visitNoArgs(int opcode, int offset, int length, Type type)127 public void visitNoArgs(int opcode, int offset, int length, Type type) { 128 switch (opcode) { 129 case ByteOps.IRETURN: 130 case ByteOps.RETURN: { 131 visitCommon(offset, length, false); 132 targetLists[offset] = IntList.EMPTY; 133 break; 134 } 135 case ByteOps.ATHROW: { 136 visitCommon(offset, length, false); 137 visitThrowing(offset, length, false); 138 break; 139 } 140 case ByteOps.IALOAD: 141 case ByteOps.LALOAD: 142 case ByteOps.FALOAD: 143 case ByteOps.DALOAD: 144 case ByteOps.AALOAD: 145 case ByteOps.BALOAD: 146 case ByteOps.CALOAD: 147 case ByteOps.SALOAD: 148 case ByteOps.IASTORE: 149 case ByteOps.LASTORE: 150 case ByteOps.FASTORE: 151 case ByteOps.DASTORE: 152 case ByteOps.AASTORE: 153 case ByteOps.BASTORE: 154 case ByteOps.CASTORE: 155 case ByteOps.SASTORE: 156 case ByteOps.ARRAYLENGTH: 157 case ByteOps.MONITORENTER: 158 case ByteOps.MONITOREXIT: { 159 /* 160 * These instructions can all throw, so they have to end 161 * the block they appear in (since throws are branches). 162 */ 163 visitCommon(offset, length, true); 164 visitThrowing(offset, length, true); 165 break; 166 } 167 case ByteOps.IDIV: 168 case ByteOps.IREM: { 169 /* 170 * The int and long versions of division and remainder may 171 * throw, but not the other types. 172 */ 173 visitCommon(offset, length, true); 174 if ((type == Type.INT) || (type == Type.LONG)) { 175 visitThrowing(offset, length, true); 176 } 177 break; 178 } 179 default: { 180 visitCommon(offset, length, true); 181 break; 182 } 183 } 184 } 185 186 /** {@inheritDoc} */ visitLocal(int opcode, int offset, int length, int idx, Type type, int value)187 public void visitLocal(int opcode, int offset, int length, 188 int idx, Type type, int value) { 189 if (opcode == ByteOps.RET) { 190 visitCommon(offset, length, false); 191 targetLists[offset] = IntList.EMPTY; 192 } else { 193 visitCommon(offset, length, true); 194 } 195 } 196 197 /** {@inheritDoc} */ visitConstant(int opcode, int offset, int length, Constant cst, int value)198 public void visitConstant(int opcode, int offset, int length, 199 Constant cst, int value) { 200 visitCommon(offset, length, true); 201 202 if ((cst instanceof CstMemberRef) || (cst instanceof CstType) || 203 (cst instanceof CstString)) { 204 /* 205 * Instructions with these sorts of constants have the 206 * possibility of throwing, so this instruction needs to 207 * end its block (since it can throw, and possible-throws 208 * are branch points). 209 */ 210 visitThrowing(offset, length, true); 211 } 212 } 213 214 /** {@inheritDoc} */ visitBranch(int opcode, int offset, int length, int target)215 public void visitBranch(int opcode, int offset, int length, 216 int target) { 217 switch (opcode) { 218 case ByteOps.GOTO: { 219 visitCommon(offset, length, false); 220 targetLists[offset] = IntList.makeImmutable(target); 221 break; 222 } 223 case ByteOps.JSR: { 224 /* 225 * Each jsr is quarantined into a separate block (containing 226 * only the jsr instruction) but is otherwise treated 227 * as a conditional branch. (That is to say, both its 228 * target and next instruction begin new blocks.) 229 */ 230 addWorkIfNecessary(offset, true); 231 // Fall through to next case... 232 } 233 default: { 234 int next = offset + length; 235 visitCommon(offset, length, true); 236 addWorkIfNecessary(next, true); 237 targetLists[offset] = IntList.makeImmutable(next, target); 238 break; 239 } 240 } 241 242 addWorkIfNecessary(target, true); 243 } 244 245 /** {@inheritDoc} */ visitSwitch(int opcode, int offset, int length, SwitchList cases, int padding)246 public void visitSwitch(int opcode, int offset, int length, 247 SwitchList cases, int padding) { 248 visitCommon(offset, length, false); 249 addWorkIfNecessary(cases.getDefaultTarget(), true); 250 251 int sz = cases.size(); 252 for (int i = 0; i < sz; i++) { 253 addWorkIfNecessary(cases.getTarget(i), true); 254 } 255 256 targetLists[offset] = cases.getTargets(); 257 } 258 259 /** {@inheritDoc} */ visitNewarray(int offset, int length, CstType type, ArrayList<Constant> intVals)260 public void visitNewarray(int offset, int length, CstType type, 261 ArrayList<Constant> intVals) { 262 visitCommon(offset, length, true); 263 visitThrowing(offset, length, true); 264 } 265 266 /** 267 * Extracts the list of basic blocks from the bit sets. 268 * 269 * @return {@code non-null;} the list of basic blocks 270 */ getBlockList()271 private ByteBlockList getBlockList() { 272 BytecodeArray bytes = method.getCode(); 273 ByteBlock[] bbs = new ByteBlock[bytes.size()]; 274 int count = 0; 275 276 for (int at = 0, next; /*at*/; at = next) { 277 next = Bits.findFirst(blockSet, at + 1); 278 if (next < 0) { 279 break; 280 } 281 282 if (Bits.get(liveSet, at)) { 283 /* 284 * Search backward for the branch or throwing 285 * instruction at the end of this block, if any. If 286 * there isn't any, then "next" is the sole target. 287 */ 288 IntList targets = null; 289 int targetsAt = -1; 290 ByteCatchList blockCatches; 291 292 for (int i = next - 1; i >= at; i--) { 293 targets = targetLists[i]; 294 if (targets != null) { 295 targetsAt = i; 296 break; 297 } 298 } 299 300 if (targets == null) { 301 targets = IntList.makeImmutable(next); 302 blockCatches = ByteCatchList.EMPTY; 303 } else { 304 blockCatches = catchLists[targetsAt]; 305 if (blockCatches == null) { 306 blockCatches = ByteCatchList.EMPTY; 307 } 308 } 309 310 bbs[count] = 311 new ByteBlock(at, at, next, targets, blockCatches); 312 count++; 313 } 314 } 315 316 ByteBlockList result = new ByteBlockList(count); 317 for (int i = 0; i < count; i++) { 318 result.set(i, bbs[i]); 319 } 320 321 return result; 322 } 323 324 /** 325 * Does basic block identification. 326 */ doit()327 private void doit() { 328 BytecodeArray bytes = method.getCode(); 329 ByteCatchList catches = method.getCatches(); 330 int catchSz = catches.size(); 331 332 /* 333 * Start by setting offset 0 as the start of a block and in need 334 * of work... 335 */ 336 Bits.set(workSet, 0); 337 Bits.set(blockSet, 0); 338 339 /* 340 * And then process the work set, add new work based on 341 * exception ranges that are active, and iterate until there's 342 * nothing left to work on. 343 */ 344 while (!Bits.isEmpty(workSet)) { 345 try { 346 bytes.processWorkSet(workSet, this); 347 } catch (IllegalArgumentException ex) { 348 // Translate the exception. 349 throw new SimException("flow of control falls off " + 350 "end of method", 351 ex); 352 } 353 354 for (int i = 0; i < catchSz; i++) { 355 ByteCatchList.Item item = catches.get(i); 356 int start = item.getStartPc(); 357 int end = item.getEndPc(); 358 if (Bits.anyInRange(liveSet, start, end)) { 359 Bits.set(blockSet, start); 360 Bits.set(blockSet, end); 361 addWorkIfNecessary(item.getHandlerPc(), true); 362 } 363 } 364 } 365 } 366 367 /** 368 * Sets a bit in the work set, but only if the instruction in question 369 * isn't yet known to be possibly-live. 370 * 371 * @param offset offset to the instruction in question 372 * @param blockStart {@code true} iff this instruction starts a 373 * basic block 374 */ addWorkIfNecessary(int offset, boolean blockStart)375 private void addWorkIfNecessary(int offset, boolean blockStart) { 376 if (!Bits.get(liveSet, offset)) { 377 Bits.set(workSet, offset); 378 } 379 380 if (blockStart) { 381 Bits.set(blockSet, offset); 382 } 383 } 384 385 /** 386 * Helper method used by all the visitor methods. 387 * 388 * @param offset offset to the instruction 389 * @param length length of the instruction, in bytes 390 * @param nextIsLive {@code true} iff the instruction after 391 * the indicated one is possibly-live (because this one isn't an 392 * unconditional branch, a return, or a switch) 393 */ visitCommon(int offset, int length, boolean nextIsLive)394 private void visitCommon(int offset, int length, boolean nextIsLive) { 395 Bits.set(liveSet, offset); 396 397 if (nextIsLive) { 398 /* 399 * If the next instruction is flowed to by this one, just 400 * add it to the work set, and then a subsequent visit*() 401 * will deal with it as appropriate. 402 */ 403 addWorkIfNecessary(offset + length, false); 404 } else { 405 /* 406 * If the next instruction isn't flowed to by this one, 407 * then mark it as a start of a block but *don't* add it 408 * to the work set, so that in the final phase we can know 409 * dead code blocks as those marked as blocks but not also marked 410 * live. 411 */ 412 Bits.set(blockSet, offset + length); 413 } 414 } 415 416 /** 417 * Helper method used by all the visitor methods that deal with 418 * opcodes that possibly throw. This method should be called after calling 419 * {@link #visitCommon}. 420 * 421 * @param offset offset to the instruction 422 * @param length length of the instruction, in bytes 423 * @param nextIsLive {@code true} iff the instruction after 424 * the indicated one is possibly-live (because this one isn't an 425 * unconditional throw) 426 */ visitThrowing(int offset, int length, boolean nextIsLive)427 private void visitThrowing(int offset, int length, boolean nextIsLive) { 428 int next = offset + length; 429 430 if (nextIsLive) { 431 addWorkIfNecessary(next, true); 432 } 433 434 ByteCatchList catches = method.getCatches().listFor(offset); 435 catchLists[offset] = catches; 436 targetLists[offset] = catches.toTargetList(nextIsLive ? next : -1); 437 } 438 439 /** 440 * {@inheritDoc} 441 */ setPreviousOffset(int offset)442 public void setPreviousOffset(int offset) { 443 previousOffset = offset; 444 } 445 446 /** 447 * {@inheritDoc} 448 */ getPreviousOffset()449 public int getPreviousOffset() { 450 return previousOffset; 451 } 452 } 453