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.rop.code; 18 19 import com.android.dx.rop.type.StdTypeList; 20 import com.android.dx.rop.type.TypeList; 21 import com.android.dx.util.Hex; 22 import com.android.dx.util.IntList; 23 import com.android.dx.util.LabeledList; 24 25 /** 26 * List of {@link BasicBlock} instances. 27 */ 28 public final class BasicBlockList extends LabeledList { 29 /** 30 * {@code >= -1;} the count of registers required by this method or 31 * {@code -1} if not yet calculated 32 */ 33 private int regCount; 34 35 /** 36 * Constructs an instance. All indices initially contain {@code null}, 37 * and the first-block label is initially {@code -1}. 38 * 39 * @param size the size of the list 40 */ 41 public BasicBlockList(int size) { 42 super(size); 43 44 regCount = -1; 45 } 46 47 /** 48 * Constructs a mutable copy for {@code getMutableCopy()}. 49 * 50 * @param old block to copy 51 */ 52 private BasicBlockList(BasicBlockList old) { 53 super(old); 54 regCount = old.regCount; 55 } 56 57 58 /** 59 * Gets the element at the given index. It is an error to call 60 * this with the index for an element which was never set; if you 61 * do that, this will throw {@code NullPointerException}. 62 * 63 * @param n {@code >= 0, < size();} which index 64 * @return {@code non-null;} element at that index 65 */ 66 public BasicBlock get(int n) { 67 return (BasicBlock) get0(n); 68 } 69 70 /** 71 * Sets the basic block at the given index. 72 * 73 * @param n {@code >= 0, < size();} which index 74 * @param bb {@code null-ok;} the element to set at {@code n} 75 */ 76 public void set(int n, BasicBlock bb) { 77 super.set(n, bb); 78 79 // Reset regCount, since it will need to be recalculated. 80 regCount = -1; 81 } 82 83 /** 84 * Returns how many registers this method requires. This is simply 85 * the maximum of register-number-plus-category referred to by this 86 * instance's instructions (indirectly through {@link BasicBlock} 87 * instances). 88 * 89 * @return {@code >= 0;} the register count 90 */ 91 public int getRegCount() { 92 if (regCount == -1) { 93 RegCountVisitor visitor = new RegCountVisitor(); 94 forEachInsn(visitor); 95 regCount = visitor.getRegCount(); 96 } 97 98 return regCount; 99 } 100 101 /** 102 * Gets the total instruction count for this instance. This is the 103 * sum of the instruction counts of each block. 104 * 105 * @return {@code >= 0;} the total instruction count 106 */ 107 public int getInstructionCount() { 108 int sz = size(); 109 int result = 0; 110 111 for (int i = 0; i < sz; i++) { 112 BasicBlock one = (BasicBlock) getOrNull0(i); 113 if (one != null) { 114 result += one.getInsns().size(); 115 } 116 } 117 118 return result; 119 } 120 121 /** 122 * Gets the total instruction count for this instance, ignoring 123 * mark-local instructions which are not actually emitted. 124 * 125 * @return {@code >= 0;} the total instruction count 126 */ 127 public int getEffectiveInstructionCount() { 128 int sz = size(); 129 int result = 0; 130 131 for (int i = 0; i < sz; i++) { 132 BasicBlock one = (BasicBlock) getOrNull0(i); 133 if (one != null) { 134 InsnList insns = one.getInsns(); 135 int insnsSz = insns.size(); 136 137 for (int j = 0; j < insnsSz; j++) { 138 Insn insn = insns.get(j); 139 140 if (insn.getOpcode().getOpcode() != RegOps.MARK_LOCAL) { 141 result++; 142 } 143 } 144 } 145 } 146 147 return result; 148 } 149 150 /** 151 * Gets the first block in the list with the given label, if any. 152 * 153 * @param label {@code >= 0;} the label to look for 154 * @return {@code non-null;} the so-labelled block 155 * @throws IllegalArgumentException thrown if the label isn't found 156 */ 157 public BasicBlock labelToBlock(int label) { 158 int idx = indexOfLabel(label); 159 160 if (idx < 0) { 161 throw new IllegalArgumentException("no such label: " 162 + Hex.u2(label)); 163 } 164 165 return get(idx); 166 } 167 168 /** 169 * Visits each instruction of each block in the list, in order. 170 * 171 * @param visitor {@code non-null;} visitor to use 172 */ 173 public void forEachInsn(Insn.Visitor visitor) { 174 int sz = size(); 175 176 for (int i = 0; i < sz; i++) { 177 BasicBlock one = get(i); 178 InsnList insns = one.getInsns(); 179 insns.forEach(visitor); 180 } 181 } 182 183 /** 184 * Returns an instance that is identical to this one, except that 185 * the registers in each instruction are offset by the given 186 * amount. Mutability of the result is inherited from the 187 * original. 188 * 189 * @param delta the amount to offset register numbers by 190 * @return {@code non-null;} an appropriately-constructed instance 191 */ 192 public BasicBlockList withRegisterOffset(int delta) { 193 int sz = size(); 194 BasicBlockList result = new BasicBlockList(sz); 195 196 for (int i = 0; i < sz; i++) { 197 BasicBlock one = (BasicBlock) get0(i); 198 if (one != null) { 199 result.set(i, one.withRegisterOffset(delta)); 200 } 201 } 202 203 if (isImmutable()) { 204 result.setImmutable(); 205 } 206 207 return result; 208 } 209 210 /** 211 * Returns a mutable copy of this list. 212 * 213 * @return {@code non-null;} an appropriately-constructed instance 214 */ 215 public BasicBlockList getMutableCopy() { 216 return new BasicBlockList(this); 217 } 218 219 /** 220 * Gets the preferred successor for the given block. If the block 221 * only has one successor, then that is the preferred successor. 222 * Otherwise, if the block has a primay successor, then that is 223 * the preferred successor. If the block has no successors, then 224 * this returns {@code null}. 225 * 226 * @param block {@code non-null;} the block in question 227 * @return {@code null-ok;} the preferred successor, if any 228 */ 229 public BasicBlock preferredSuccessorOf(BasicBlock block) { 230 int primarySuccessor = block.getPrimarySuccessor(); 231 IntList successors = block.getSuccessors(); 232 int succSize = successors.size(); 233 234 switch (succSize) { 235 case 0: { 236 return null; 237 } 238 case 1: { 239 return labelToBlock(successors.get(0)); 240 } 241 } 242 243 if (primarySuccessor != -1) { 244 return labelToBlock(primarySuccessor); 245 } else { 246 return labelToBlock(successors.get(0)); 247 } 248 } 249 250 /** 251 * Compares the catches of two blocks for equality. This includes 252 * both the catch types and target labels. 253 * 254 * @param block1 {@code non-null;} one block to compare 255 * @param block2 {@code non-null;} the other block to compare 256 * @return {@code true} if the two blocks' non-primary successors 257 * are identical 258 */ 259 public boolean catchesEqual(BasicBlock block1, BasicBlock block2) { 260 TypeList catches1 = block1.getExceptionHandlerTypes(); 261 TypeList catches2 = block2.getExceptionHandlerTypes(); 262 263 if (!StdTypeList.equalContents(catches1, catches2)) { 264 return false; 265 } 266 267 IntList succ1 = block1.getSuccessors(); 268 IntList succ2 = block2.getSuccessors(); 269 int size = succ1.size(); // Both are guaranteed to be the same size. 270 271 int primary1 = block1.getPrimarySuccessor(); 272 int primary2 = block2.getPrimarySuccessor(); 273 274 if (((primary1 == -1) || (primary2 == -1)) 275 && (primary1 != primary2)) { 276 /* 277 * For the current purpose, both blocks in question must 278 * either both have a primary or both not have a primary to 279 * be considered equal, and it turns out here that that's not 280 * the case. 281 */ 282 return false; 283 } 284 285 for (int i = 0; i < size; i++) { 286 int label1 = succ1.get(i); 287 int label2 = succ2.get(i); 288 289 if (label1 == primary1) { 290 /* 291 * It should be the case that block2's primary is at the 292 * same index. If not, we consider the blocks unequal for 293 * the current purpose. 294 */ 295 if (label2 != primary2) { 296 return false; 297 } 298 continue; 299 } 300 301 if (label1 != label2) { 302 return false; 303 } 304 } 305 306 return true; 307 } 308 309 /** 310 * Instruction visitor class for counting registers used. 311 */ 312 private static class RegCountVisitor 313 implements Insn.Visitor { 314 /** {@code >= 0;} register count in-progress */ 315 private int regCount; 316 317 /** 318 * Constructs an instance. 319 */ 320 public RegCountVisitor() { 321 regCount = 0; 322 } 323 324 /** 325 * Gets the register count. 326 * 327 * @return {@code >= 0;} the count 328 */ 329 public int getRegCount() { 330 return regCount; 331 } 332 333 /** {@inheritDoc} */ 334 public void visitPlainInsn(PlainInsn insn) { 335 visit(insn); 336 } 337 338 /** {@inheritDoc} */ 339 public void visitPlainCstInsn(PlainCstInsn insn) { 340 visit(insn); 341 } 342 343 /** {@inheritDoc} */ 344 public void visitSwitchInsn(SwitchInsn insn) { 345 visit(insn); 346 } 347 348 /** {@inheritDoc} */ 349 public void visitThrowingCstInsn(ThrowingCstInsn insn) { 350 visit(insn); 351 } 352 353 /** {@inheritDoc} */ 354 public void visitThrowingInsn(ThrowingInsn insn) { 355 visit(insn); 356 } 357 358 /** {@inheritDoc} */ 359 public void visitFillArrayDataInsn(FillArrayDataInsn insn) { 360 visit(insn); 361 } 362 363 /** 364 * Helper for all the {@code visit*} methods. 365 * 366 * @param insn {@code non-null;} instruction being visited 367 */ 368 private void visit(Insn insn) { 369 RegisterSpec result = insn.getResult(); 370 371 if (result != null) { 372 processReg(result); 373 } 374 375 RegisterSpecList sources = insn.getSources(); 376 int sz = sources.size(); 377 378 for (int i = 0; i < sz; i++) { 379 processReg(sources.get(i)); 380 } 381 } 382 383 /** 384 * Processes the given register spec. 385 * 386 * @param spec {@code non-null;} the register spec 387 */ 388 private void processReg(RegisterSpec spec) { 389 int reg = spec.getNextReg(); 390 391 if (reg > regCount) { 392 regCount = reg; 393 } 394 } 395 } 396 } 397