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