1// Copyright (c) 2016, the R8 project authors. Please see the AUTHORS file 2// for details. All rights reserved. Use of this source code is governed by a 3// BSD-style license that can be found in the LICENSE file. 4 5package com.android.tools.r8.ir.optimize; 6 7import com.android.tools.r8.dex.Constants; 8import com.android.tools.r8.errors.CompilationError; 9import com.android.tools.r8.graph.AppInfo; 10import com.android.tools.r8.graph.DexClass; 11import com.android.tools.r8.graph.DexEncodedMethod; 12import com.android.tools.r8.graph.DexField; 13import com.android.tools.r8.graph.DexItemFactory; 14import com.android.tools.r8.graph.DexMethod; 15import com.android.tools.r8.graph.DexProto; 16import com.android.tools.r8.graph.DexType; 17import com.android.tools.r8.ir.code.ArrayGet; 18import com.android.tools.r8.ir.code.ArrayPut; 19import com.android.tools.r8.ir.code.BasicBlock; 20import com.android.tools.r8.ir.code.Binop; 21import com.android.tools.r8.ir.code.CatchHandlers; 22import com.android.tools.r8.ir.code.Cmp; 23import com.android.tools.r8.ir.code.Cmp.Bias; 24import com.android.tools.r8.ir.code.ConstNumber; 25import com.android.tools.r8.ir.code.ConstString; 26import com.android.tools.r8.ir.code.DominatorTree; 27import com.android.tools.r8.ir.code.Goto; 28import com.android.tools.r8.ir.code.IRCode; 29import com.android.tools.r8.ir.code.If; 30import com.android.tools.r8.ir.code.If.Type; 31import com.android.tools.r8.ir.code.Instruction; 32import com.android.tools.r8.ir.code.InstructionIterator; 33import com.android.tools.r8.ir.code.InstructionListIterator; 34import com.android.tools.r8.ir.code.Invoke; 35import com.android.tools.r8.ir.code.InvokeDirect; 36import com.android.tools.r8.ir.code.InvokeMethod; 37import com.android.tools.r8.ir.code.InvokeVirtual; 38import com.android.tools.r8.ir.code.MemberType; 39import com.android.tools.r8.ir.code.MoveType; 40import com.android.tools.r8.ir.code.NewArrayEmpty; 41import com.android.tools.r8.ir.code.NewArrayFilledData; 42import com.android.tools.r8.ir.code.NumericType; 43import com.android.tools.r8.ir.code.Phi; 44import com.android.tools.r8.ir.code.Return; 45import com.android.tools.r8.ir.code.StaticGet; 46import com.android.tools.r8.ir.code.StaticPut; 47import com.android.tools.r8.ir.code.Switch; 48import com.android.tools.r8.ir.code.Value; 49import com.android.tools.r8.ir.conversion.OptimizationFeedback; 50import com.android.tools.r8.utils.InternalOptions; 51import com.android.tools.r8.utils.LongInterval; 52import com.google.common.base.Equivalence; 53import com.google.common.base.Equivalence.Wrapper; 54import com.google.common.collect.ArrayListMultimap; 55import com.google.common.collect.ImmutableList; 56import com.google.common.collect.ListMultimap; 57import it.unimi.dsi.fastutil.ints.Int2IntArrayMap; 58import it.unimi.dsi.fastutil.ints.Int2IntMap; 59import it.unimi.dsi.fastutil.ints.Int2ReferenceArrayMap; 60import it.unimi.dsi.fastutil.ints.Int2ReferenceMap; 61import it.unimi.dsi.fastutil.ints.IntArrayList; 62import it.unimi.dsi.fastutil.ints.IntList; 63import it.unimi.dsi.fastutil.objects.Reference2IntArrayMap; 64import it.unimi.dsi.fastutil.objects.Reference2IntMap; 65import java.util.ArrayList; 66import java.util.Comparator; 67import java.util.HashMap; 68import java.util.HashSet; 69import java.util.IdentityHashMap; 70import java.util.Iterator; 71import java.util.LinkedList; 72import java.util.List; 73import java.util.ListIterator; 74import java.util.Map; 75import java.util.Queue; 76import java.util.Set; 77 78public class CodeRewriter { 79 80 private static final int UNKNOWN_CAN_THROW = 0; 81 private static final int CAN_THROW = 1; 82 private static final int CANNOT_THROW = 2; 83 private static final int MAX_FILL_ARRAY_SIZE = 8 * Constants.KILOBYTE; 84 // This constant was determined by experimentation. 85 private static final int STOP_SHARED_CONSTANT_THRESHOLD = 50; 86 87 private final AppInfo appInfo; 88 private final DexItemFactory dexItemFactory; 89 private final Set<DexType> libraryClassesWithOptimizationInfo; 90 91 public CodeRewriter(AppInfo appInfo, Set<DexType> libraryClassesWithOptimizationInfo) { 92 this.appInfo = appInfo; 93 this.dexItemFactory = appInfo.dexItemFactory; 94 this.libraryClassesWithOptimizationInfo = libraryClassesWithOptimizationInfo; 95 } 96 97 /** 98 * Removes all debug positions that are not needed to maintain proper stack trace information. 99 * If a debug position is followed by another debug position and no instructions between the two 100 * can throw then it is unneeded (in a release build). 101 * If a block with a position has (normal) outgoing edges, this property depends on the 102 * possibility of the successors throwing before the next debug position is hit. 103 */ 104 public static boolean removedUnneededDebugPositions(IRCode code) { 105 computeThrowsColorForAllBlocks(code); 106 for (BasicBlock block : code.blocks) { 107 InstructionListIterator iterator = block.listIterator(); 108 while (iterator.hasNext()) { 109 Instruction instruction = iterator.next(); 110 if (instruction.isDebugPosition() 111 && getThrowsColorForBlock(block, iterator.nextIndex()) == CANNOT_THROW) { 112 iterator.remove(); 113 } 114 } 115 } 116 return true; 117 } 118 119 private static void computeThrowsColorForAllBlocks(IRCode code) { 120 // First pass colors blocks in reverse topological order, based on the instructions. 121 code.clearMarks(); 122 List<BasicBlock> blocks = code.blocks; 123 ArrayList<BasicBlock> worklist = new ArrayList<>(); 124 for (int i = blocks.size() - 1; i >= 0; i--) { 125 BasicBlock block = blocks.get(i); 126 // Mark the block as not-throwing if no successor implies otherwise. 127 // This ensures that a loop back to this block will be seen as non-throwing. 128 block.setColor(CANNOT_THROW); 129 int color = getThrowsColorForBlock(block, 0); 130 block.setColor(color); 131 if (color == UNKNOWN_CAN_THROW) { 132 worklist.add(block); 133 } 134 } 135 // A fixed point then ensures that we propagate the color backwards over normal edges. 136 ArrayList<BasicBlock> remaining = new ArrayList<>(worklist.size()); 137 while (!worklist.isEmpty()) { 138 ImmutableList<BasicBlock> work = new ImmutableList.Builder<BasicBlock>() 139 .addAll(worklist) 140 .addAll(remaining) 141 .build(); 142 worklist.clear(); 143 remaining.clear(); 144 for (BasicBlock block : work) { 145 if (!block.hasColor(UNKNOWN_CAN_THROW)) { 146 continue; 147 } 148 block.setColor(CANNOT_THROW); 149 int color = getThrowsColorForSuccessors(block); 150 block.setColor(color); 151 if (color == UNKNOWN_CAN_THROW) { 152 remaining.add(block); 153 } else { 154 for (BasicBlock predecessor : block.getNormalPredecessors()) { 155 if (predecessor.hasColor(UNKNOWN_CAN_THROW)) { 156 worklist.add(predecessor); 157 } 158 } 159 } 160 } 161 } 162 // Any remaining set of blocks represents a cycle of blocks containing no throwing instructions. 163 for (BasicBlock block : remaining) { 164 assert !block.canThrow(); 165 block.setColor(CANNOT_THROW); 166 } 167 } 168 169 private static int getThrowsColorForBlock(BasicBlock block, int index) { 170 InstructionListIterator iterator = block.listIterator(index); 171 while (iterator.hasNext()) { 172 Instruction instruction = iterator.next(); 173 if (instruction.isDebugPosition()) { 174 return CANNOT_THROW; 175 } 176 if (instruction.instructionTypeCanThrow()) { 177 return CAN_THROW; 178 } 179 } 180 return getThrowsColorForSuccessors(block); 181 } 182 183 private static int getThrowsColorForSuccessors(BasicBlock block) { 184 int color = CANNOT_THROW; 185 for (BasicBlock successor : block.getNormalSucessors()) { 186 if (successor.hasColor(CAN_THROW)) { 187 return CAN_THROW; 188 } 189 if (successor.hasColor(UNKNOWN_CAN_THROW)) { 190 color = UNKNOWN_CAN_THROW; 191 } 192 } 193 return color; 194 } 195 196 private static boolean removedTrivialGotos(IRCode code) { 197 ListIterator<BasicBlock> iterator = code.listIterator(); 198 assert iterator.hasNext(); 199 BasicBlock block = iterator.next(); 200 BasicBlock nextBlock; 201 do { 202 nextBlock = iterator.hasNext() ? iterator.next() : null; 203 // Trivial goto block are only kept if they are self-targeting or are targeted by 204 // fallthroughs. 205 BasicBlock blk = block; // Additional local for lambda below. 206 assert !block.isTrivialGoto() 207 || block.exit().asGoto().getTarget() == block 208 || block.getPredecessors().stream().anyMatch((b) -> b.exit().fallthroughBlock() == blk); 209 // Trivial goto blocks never target the next block (in that case there should just be a 210 // fallthrough). 211 assert !block.isTrivialGoto() || block.exit().asGoto().getTarget() != nextBlock; 212 block = nextBlock; 213 } while (block != null); 214 return true; 215 } 216 217 private static BasicBlock endOfGotoChain(BasicBlock block) { 218 block.mark(); 219 BasicBlock target = block; 220 while (target.isTrivialGoto()) { 221 BasicBlock nextTarget = target.exit().asGoto().getTarget(); 222 if (nextTarget.isMarked()) { 223 clearTrivialGotoMarks(block); 224 return nextTarget; 225 } 226 nextTarget.mark(); 227 target = nextTarget; 228 } 229 clearTrivialGotoMarks(block); 230 return target; 231 } 232 233 private static void clearTrivialGotoMarks(BasicBlock block) { 234 while (block.isMarked()) { 235 block.clearMark(); 236 if (block.isTrivialGoto()) { 237 block = block.exit().asGoto().getTarget(); 238 } 239 } 240 } 241 242 private static void collapsTrivialGoto( 243 BasicBlock block, BasicBlock nextBlock, List<BasicBlock> blocksToRemove) { 244 245 // This is the base case for GOTO loops. 246 if (block.exit().asGoto().getTarget() == block) { 247 return; 248 } 249 250 BasicBlock target = endOfGotoChain(block); 251 252 boolean needed = false; 253 if (target != nextBlock) { 254 for (BasicBlock pred : block.getPredecessors()) { 255 if (pred.exit().fallthroughBlock() == block) { 256 needed = true; 257 break; 258 } 259 } 260 } 261 262 // This implies we are in a loop of GOTOs. In that case, we will iteratively remove each trival 263 // GOTO one-by-one until the above base case (one block targeting itself) is left. 264 if (target == block) { 265 target = block.exit().asGoto().getTarget(); 266 } 267 268 if (!needed) { 269 blocksToRemove.add(block); 270 for (BasicBlock pred : block.getPredecessors()) { 271 pred.replaceSuccessor(block, target); 272 } 273 for (BasicBlock succ : block.getSuccessors()) { 274 succ.getPredecessors().remove(block); 275 } 276 for (BasicBlock pred : block.getPredecessors()) { 277 if (!target.getPredecessors().contains(pred)) { 278 target.getPredecessors().add(pred); 279 } 280 } 281 } 282 } 283 284 private static void collapsIfTrueTarget(BasicBlock block) { 285 If insn = block.exit().asIf(); 286 BasicBlock target = insn.getTrueTarget(); 287 BasicBlock newTarget = endOfGotoChain(target); 288 BasicBlock fallthrough = insn.fallthroughBlock(); 289 BasicBlock newFallthrough = endOfGotoChain(fallthrough); 290 if (target != newTarget) { 291 insn.getBlock().replaceSuccessor(target, newTarget); 292 target.getPredecessors().remove(block); 293 if (!newTarget.getPredecessors().contains(block)) { 294 newTarget.getPredecessors().add(block); 295 } 296 } 297 if (block.exit().isIf()) { 298 insn = block.exit().asIf(); 299 if (insn.getTrueTarget() == newFallthrough) { 300 // Replace if with the same true and fallthrough target with a goto to the fallthrough. 301 block.replaceSuccessor(insn.getTrueTarget(), fallthrough); 302 assert block.exit().isGoto(); 303 assert block.exit().asGoto().getTarget() == fallthrough; 304 } 305 } 306 } 307 308 private static void collapsNonFallthroughSwitchTargets(BasicBlock block) { 309 Switch insn = block.exit().asSwitch(); 310 BasicBlock fallthroughBlock = insn.fallthroughBlock(); 311 Set<BasicBlock> replacedBlocks = new HashSet<>(); 312 for (int j = 0; j < insn.targetBlockIndices().length; j++) { 313 BasicBlock target = insn.targetBlock(j); 314 if (target != fallthroughBlock) { 315 BasicBlock newTarget = endOfGotoChain(target); 316 if (target != newTarget && !replacedBlocks.contains(target)) { 317 insn.getBlock().replaceSuccessor(target, newTarget); 318 target.getPredecessors().remove(block); 319 if (!newTarget.getPredecessors().contains(block)) { 320 newTarget.getPredecessors().add(block); 321 } 322 replacedBlocks.add(target); 323 } 324 } 325 } 326 } 327 328 public void rewriteSwitch(IRCode code) { 329 for (BasicBlock block : code.blocks) { 330 InstructionListIterator iterator = block.listIterator(); 331 while (iterator.hasNext()) { 332 Instruction instruction = iterator.next(); 333 if (instruction.isSwitch()) { 334 Switch theSwitch = instruction.asSwitch(); 335 if (theSwitch.numberOfKeys() == 1) { 336 // Rewrite the switch to an if. 337 int fallthroughBlockIndex = theSwitch.getFallthroughBlockIndex(); 338 int caseBlockIndex = theSwitch.targetBlockIndices()[0]; 339 if (fallthroughBlockIndex < caseBlockIndex) { 340 block.swapSuccessorsByIndex(fallthroughBlockIndex, caseBlockIndex); 341 } 342 if (theSwitch.getFirstKey() == 0) { 343 iterator.replaceCurrentInstruction(new If(Type.EQ, theSwitch.value())); 344 } else { 345 ConstNumber labelConst = code.createIntConstant(theSwitch.getFirstKey()); 346 iterator.previous(); 347 iterator.add(labelConst); 348 Instruction dummy = iterator.next(); 349 assert dummy == theSwitch; 350 If theIf = new If(Type.EQ, ImmutableList.of(theSwitch.value(), labelConst.dest())); 351 iterator.replaceCurrentInstruction(theIf); 352 } 353 } 354 } 355 } 356 } 357 } 358 359 /** 360 * Inline the indirection of switch maps into the switch statement. 361 * <p> 362 * To ensure binary compatibility, javac generated code does not use ordinal values of enums 363 * directly in switch statements but instead generates a companion class that computes a mapping 364 * from switch branches to ordinals at runtime. As we have whole-program knowledge, we can 365 * analyze these maps and inline the indirection into the switch map again. 366 * <p> 367 * In particular, we look for code of the form 368 * 369 * <blockquote><pre> 370 * switch(CompanionClass.$switchmap$field[enumValue.ordinal()]) { 371 * ... 372 * } 373 * </pre></blockquote> 374 * See {@link #extractIndexMapFrom} and {@link #extractOrdinalsMapFor} for 375 * details of the companion class and ordinals computation. 376 */ 377 public void removeSwitchMaps(IRCode code) { 378 for (BasicBlock block : code.blocks) { 379 InstructionListIterator it = block.listIterator(); 380 while (it.hasNext()) { 381 Instruction insn = it.next(); 382 // Pattern match a switch on a switch map as input. 383 if (insn.isSwitch()) { 384 Switch switchInsn = insn.asSwitch(); 385 Instruction input = switchInsn.inValues().get(0).definition; 386 if (input == null || !input.isArrayGet()) { 387 continue; 388 } 389 ArrayGet arrayGet = input.asArrayGet(); 390 Instruction index = arrayGet.index().definition; 391 if (index == null || !index.isInvokeVirtual()) { 392 continue; 393 } 394 InvokeVirtual ordinalInvoke = index.asInvokeVirtual(); 395 DexMethod ordinalMethod = ordinalInvoke.getInvokedMethod(); 396 DexClass enumClass = appInfo.definitionFor(ordinalMethod.holder); 397 if (enumClass == null 398 || (!enumClass.accessFlags.isEnum() && enumClass.type != dexItemFactory.enumType) 399 || ordinalMethod.name != dexItemFactory.ordinalMethodName 400 || ordinalMethod.proto.returnType != dexItemFactory.intType 401 || !ordinalMethod.proto.parameters.isEmpty()) { 402 continue; 403 } 404 Instruction array = arrayGet.array().definition; 405 if (array == null || !array.isStaticGet()) { 406 continue; 407 } 408 StaticGet staticGet = array.asStaticGet(); 409 if (staticGet.getField().name.toSourceString().startsWith("$SwitchMap$")) { 410 Int2ReferenceMap<DexField> indexMap = extractIndexMapFrom(staticGet.getField()); 411 if (indexMap == null || indexMap.isEmpty()) { 412 continue; 413 } 414 // Due to member rebinding, only the fields are certain to provide the actual enums 415 // class. 416 DexType switchMapHolder = indexMap.values().iterator().next().getHolder(); 417 Reference2IntMap ordinalsMap = extractOrdinalsMapFor(switchMapHolder); 418 if (ordinalsMap != null) { 419 Int2IntMap targetMap = new Int2IntArrayMap(); 420 IntList keys = new IntArrayList(switchInsn.numberOfKeys()); 421 for (int i = 0; i < switchInsn.numberOfKeys(); i++) { 422 assert switchInsn.targetBlockIndices()[i] != switchInsn.getFallthroughBlockIndex(); 423 int key = ordinalsMap.getInt(indexMap.get(switchInsn.getKey(i))); 424 keys.add(key); 425 targetMap.put(key, switchInsn.targetBlockIndices()[i]); 426 } 427 keys.sort(Comparator.naturalOrder()); 428 int[] targets = new int[keys.size()]; 429 for (int i = 0; i < keys.size(); i++) { 430 targets[i] = targetMap.get(keys.getInt(i)); 431 } 432 433 Switch newSwitch = new Switch(ordinalInvoke.outValue(), keys.toIntArray(), 434 targets, switchInsn.getFallthroughBlockIndex()); 435 // Replace the switch itself. 436 it.replaceCurrentInstruction(newSwitch); 437 // If the original input to the switch is now unused, remove it too. It is not dead 438 // as it might have side-effects but we ignore these here. 439 if (arrayGet.outValue().numberOfUsers() == 0) { 440 arrayGet.inValues().forEach(v -> v.removeUser(arrayGet)); 441 arrayGet.getBlock().removeInstruction(arrayGet); 442 } 443 if (staticGet.outValue().numberOfUsers() == 0) { 444 assert staticGet.inValues().isEmpty(); 445 staticGet.getBlock().removeInstruction(staticGet); 446 } 447 } 448 } 449 } 450 } 451 } 452 } 453 454 455 /** 456 * Extracts the mapping from ordinal values to switch case constants. 457 * <p> 458 * This is done by pattern-matching on the class initializer of the synthetic switch map class. 459 * For a switch 460 * 461 * <blockquote><pre> 462 * switch (day) { 463 * case WEDNESDAY: 464 * case FRIDAY: 465 * System.out.println("3 or 5"); 466 * break; 467 * case SUNDAY: 468 * System.out.println("7"); 469 * break; 470 * default: 471 * System.out.println("other"); 472 * } 473 * </pre></blockquote> 474 * 475 * the generated companing class initializer will have the form 476 * 477 * <blockquote><pre> 478 * class Switches$1 { 479 * static { 480 * $SwitchMap$switchmaps$Days[Days.WEDNESDAY.ordinal()] = 1; 481 * $SwitchMap$switchmaps$Days[Days.FRIDAY.ordinal()] = 2; 482 * $SwitchMap$switchmaps$Days[Days.SUNDAY.ordinal()] = 3; 483 * } 484 * </pre></blockquote> 485 * 486 * Note that one map per class is generated, so the map might contain additional entries as used 487 * by other switches in the class. 488 */ 489 private Int2ReferenceMap<DexField> extractIndexMapFrom(DexField field) { 490 DexClass clazz = appInfo.definitionFor(field.getHolder()); 491 if (!clazz.accessFlags.isSynthetic()) { 492 return null; 493 } 494 DexEncodedMethod initializer = clazz.getClassInitializer(); 495 if (initializer == null || initializer.getCode() == null) { 496 return null; 497 } 498 IRCode code = initializer.getCode().buildIR(initializer, new InternalOptions()); 499 Int2ReferenceMap<DexField> switchMap = new Int2ReferenceArrayMap<>(); 500 for (BasicBlock block : code.blocks) { 501 InstructionListIterator it = block.listIterator(); 502 Instruction insn = it.nextUntil(i -> i.isStaticGet() && i.asStaticGet().getField() == field); 503 if (insn == null) { 504 continue; 505 } 506 for (Instruction use : insn.outValue().uniqueUsers()) { 507 if (use.isArrayPut()) { 508 Instruction index = use.asArrayPut().source().definition; 509 if (index == null || !index.isConstNumber()) { 510 return null; 511 } 512 int integerIndex = index.asConstNumber().getIntValue(); 513 Instruction value = use.asArrayPut().index().definition; 514 if (value == null || !value.isInvokeVirtual()) { 515 return null; 516 } 517 InvokeVirtual invoke = value.asInvokeVirtual(); 518 DexClass holder = appInfo.definitionFor(invoke.getInvokedMethod().holder); 519 if (holder == null || 520 (!holder.accessFlags.isEnum() && holder.type != dexItemFactory.enumType)) { 521 return null; 522 } 523 Instruction enumGet = invoke.arguments().get(0).definition; 524 if (enumGet == null || !enumGet.isStaticGet()) { 525 return null; 526 } 527 DexField enumField = enumGet.asStaticGet().getField(); 528 if (!appInfo.definitionFor(enumField.getHolder()).accessFlags.isEnum()) { 529 return null; 530 } 531 if (switchMap.put(integerIndex, enumField) != null) { 532 return null; 533 } 534 } else { 535 return null; 536 } 537 } 538 } 539 return switchMap; 540 } 541 542 /** 543 * Extracts the ordinal values for an Enum class from the classes static initializer. 544 * <p> 545 * An Enum class has a field for each value. In the class initializer, each field is initialized 546 * to a singleton object that represents the value. This code matches on the corresponding call 547 * to the constructor (instance initializer) and extracts the value of the second argument, which 548 * is the ordinal. 549 */ 550 private Reference2IntMap<DexField> extractOrdinalsMapFor(DexType enumClass) { 551 DexClass clazz = appInfo.definitionFor(enumClass); 552 if (clazz == null || clazz.isLibraryClass()) { 553 // We have to keep binary compatibility in tact for libraries. 554 return null; 555 } 556 DexEncodedMethod initializer = clazz.getClassInitializer(); 557 if (!clazz.accessFlags.isEnum() || initializer == null || initializer.getCode() == null) { 558 return null; 559 } 560 IRCode code = initializer.getCode().buildIR(initializer, new InternalOptions()); 561 Reference2IntMap<DexField> ordinalsMap = new Reference2IntArrayMap<>(); 562 ordinalsMap.defaultReturnValue(-1); 563 InstructionIterator it = code.instructionIterator(); 564 while (it.hasNext()) { 565 Instruction insn = it.next(); 566 if (!insn.isStaticPut()) { 567 continue; 568 } 569 StaticPut staticPut = insn.asStaticPut(); 570 if (staticPut.getField().type != enumClass) { 571 continue; 572 } 573 Instruction newInstance = staticPut.inValue().definition; 574 if (newInstance == null || !newInstance.isNewInstance()) { 575 continue; 576 } 577 Instruction ordinal = null; 578 for (Instruction ctorCall : newInstance.outValue().uniqueUsers()) { 579 if (!ctorCall.isInvokeDirect()) { 580 continue; 581 } 582 InvokeDirect invoke = ctorCall.asInvokeDirect(); 583 if (!dexItemFactory.isConstructor(invoke.getInvokedMethod()) 584 || invoke.arguments().size() < 3) { 585 continue; 586 } 587 ordinal = invoke.arguments().get(2).definition; 588 break; 589 } 590 if (ordinal == null || !ordinal.isConstNumber()) { 591 return null; 592 } 593 if (ordinalsMap.put(staticPut.getField(), ordinal.asConstNumber().getIntValue()) != -1) { 594 return null; 595 } 596 } 597 return ordinalsMap; 598 } 599 600 /** 601 * Rewrite all branch targets to the destination of trivial goto chains when possible. 602 * Does not rewrite fallthrough targets as that would require block reordering and the 603 * transformation only makes sense after SSA destruction where there are no phis. 604 */ 605 public static void collapsTrivialGotos(DexEncodedMethod method, IRCode code) { 606 assert code.isConsistentGraph(); 607 List<BasicBlock> blocksToRemove = new ArrayList<>(); 608 // Rewrite all non-fallthrough targets to the end of trivial goto chains and remove 609 // first round of trivial goto blocks. 610 ListIterator<BasicBlock> iterator = code.listIterator(); 611 assert iterator.hasNext(); 612 BasicBlock block = iterator.next(); 613 BasicBlock nextBlock; 614 615 // The marks will be used for cycle detection. 616 code.clearMarks(); 617 do { 618 nextBlock = iterator.hasNext() ? iterator.next() : null; 619 if (block.isTrivialGoto()) { 620 collapsTrivialGoto(block, nextBlock, blocksToRemove); 621 } 622 if (block.exit().isIf()) { 623 collapsIfTrueTarget(block); 624 } 625 if (block.exit().isSwitch()) { 626 collapsNonFallthroughSwitchTargets(block); 627 } 628 block = nextBlock; 629 } while (nextBlock != null); 630 code.removeBlocks(blocksToRemove); 631 // Get rid of gotos to the next block. 632 while (!blocksToRemove.isEmpty()) { 633 blocksToRemove = new ArrayList<>(); 634 iterator = code.listIterator(); 635 block = iterator.next(); 636 do { 637 nextBlock = iterator.hasNext() ? iterator.next() : null; 638 if (block.isTrivialGoto()) { 639 collapsTrivialGoto(block, nextBlock, blocksToRemove); 640 } 641 block = nextBlock; 642 } while (block != null); 643 code.removeBlocks(blocksToRemove); 644 } 645 assert removedTrivialGotos(code); 646 assert code.isConsistentGraph(); 647 } 648 649 public void identifyReturnsArgument( 650 DexEncodedMethod method, IRCode code, OptimizationFeedback feedback) { 651 if (code.getNormalExitBlock() != null) { 652 Return ret = code.getNormalExitBlock().exit().asReturn(); 653 if (!ret.isReturnVoid()) { 654 Value returnValue = ret.returnValue(); 655 if (returnValue.isArgument()) { 656 // Find the argument number. 657 int index = code.collectArguments().indexOf(returnValue); 658 assert index != -1; 659 feedback.methodReturnsArgument(method, index); 660 } 661 if (returnValue.isConstant() && returnValue.definition.isConstNumber()) { 662 long value = returnValue.definition.asConstNumber().getRawValue(); 663 feedback.methodReturnsConstant(method, value); 664 } 665 if (returnValue.isNeverNull()) { 666 feedback.methodNeverReturnsNull(method); 667 } 668 } 669 } 670 } 671 672 private boolean checkArgumentType(InvokeMethod invoke, DexMethod target, int argumentIndex) { 673 DexType returnType = invoke.getInvokedMethod().proto.returnType; 674 // TODO(sgjesse): Insert cast if required. 675 if (invoke.isInvokeStatic()) { 676 return invoke.getInvokedMethod().proto.parameters.values[argumentIndex] == returnType; 677 } else { 678 if (argumentIndex == 0) { 679 return invoke.getInvokedMethod().getHolder() == returnType; 680 } else { 681 return invoke.getInvokedMethod().proto.parameters.values[argumentIndex - 1] == returnType; 682 } 683 } 684 } 685 686 // Replace result uses for methods where something is known about what is returned. 687 public void rewriteMoveResult(IRCode code) { 688 if (!appInfo.hasSubtyping()) { 689 return; 690 } 691 InstructionIterator iterator = code.instructionIterator(); 692 while (iterator.hasNext()) { 693 Instruction current = iterator.next(); 694 if (current.isInvokeMethod()) { 695 InvokeMethod invoke = current.asInvokeMethod(); 696 if (invoke.outValue() != null) { 697 DexEncodedMethod target = invoke.computeSingleTarget(appInfo.withSubtyping()); 698 // We have a set of library classes with optimization information - consider those 699 // as well. 700 if ((target == null) && 701 libraryClassesWithOptimizationInfo.contains(invoke.getInvokedMethod().getHolder())) { 702 target = appInfo.definitionFor(invoke.getInvokedMethod()); 703 } 704 if (target != null) { 705 DexMethod invokedMethod = target.method; 706 // Check if the invoked method is known to return one of its arguments. 707 DexEncodedMethod definition = appInfo.definitionFor(invokedMethod); 708 if (definition != null && definition.getOptimizationInfo().returnsArgument()) { 709 int argumentIndex = definition.getOptimizationInfo().getReturnedArgument(); 710 // Replace the out value of the invoke with the argument and ignore the out value. 711 if (argumentIndex != -1 && checkArgumentType(invoke, target.method, argumentIndex)) { 712 Value argument = invoke.arguments().get(argumentIndex); 713 assert (invoke.outType() == argument.outType()) || 714 (invoke.outType() == MoveType.OBJECT 715 && argument.outType() == MoveType.SINGLE 716 && argument.getConstInstruction().asConstNumber().isZero()); 717 invoke.outValue().replaceUsers(argument); 718 invoke.setOutValue(null); 719 } 720 } 721 } 722 } 723 } 724 } 725 assert code.isConsistentGraph(); 726 } 727 728 // For supporting assert javac adds the static field $assertionsDisabled to all classes which 729 // have methods with assertions. This is used to support the Java VM -ea flag. 730 // 731 // The class: 732 // 733 // class A { 734 // void m() { 735 // assert xxx; 736 // } 737 // } 738 // 739 // Is compiled into: 740 // 741 // class A { 742 // static boolean $assertionsDisabled; 743 // static { 744 // $assertionsDisabled = A.class.desiredAssertionStatus(); 745 // } 746 // 747 // // method with "assert xxx"; 748 // void m() { 749 // if (!$assertionsDisabled) { 750 // if (xxx) { 751 // throw new AssertionError(...); 752 // } 753 // } 754 // } 755 // } 756 // 757 // With the rewriting below (and other rewritings) the resulting code is: 758 // 759 // class A { 760 // void m() { 761 // } 762 // } 763 // 764 public void disableAssertions(IRCode code) { 765 InstructionIterator iterator = code.instructionIterator(); 766 while (iterator.hasNext()) { 767 Instruction current = iterator.next(); 768 if (current.isInvokeMethod()) { 769 InvokeMethod invoke = current.asInvokeMethod(); 770 if (invoke.getInvokedMethod() == dexItemFactory.classMethods.desiredAssertionStatus) { 771 iterator.replaceCurrentInstruction(code.createFalse()); 772 } 773 } else if (current.isStaticPut()) { 774 StaticPut staticPut = current.asStaticPut(); 775 if (staticPut.getField().name == dexItemFactory.assertionsDisabled) { 776 iterator.remove(); 777 } 778 } else if (current.isStaticGet()) { 779 StaticGet staticGet = current.asStaticGet(); 780 if (staticGet.getField().name == dexItemFactory.assertionsDisabled) { 781 iterator.replaceCurrentInstruction(code.createTrue()); 782 } 783 } 784 } 785 } 786 787 private boolean canBeFolded(Instruction instruction) { 788 return (instruction.isBinop() && instruction.asBinop().canBeFolded()) || 789 (instruction.isUnop() && instruction.asUnop().canBeFolded()); 790 } 791 792 public void foldConstants(IRCode code) { 793 Queue<BasicBlock> worklist = new LinkedList<>(); 794 worklist.addAll(code.blocks); 795 for (BasicBlock block = worklist.poll(); block != null; block = worklist.poll()) { 796 InstructionIterator iterator = block.iterator(); 797 while (iterator.hasNext()) { 798 Instruction current = iterator.next(); 799 Instruction folded; 800 if (canBeFolded(current)) { 801 folded = current.fold(code); 802 iterator.replaceCurrentInstruction(folded); 803 folded.outValue().uniqueUsers() 804 .forEach(instruction -> worklist.add(instruction.getBlock())); 805 } 806 } 807 } 808 assert code.isConsistentSSA(); 809 } 810 811 // Constants are canonicalized in the entry block. We split some of them when it is likely 812 // that having them canonicalized in the entry block will lead to poor code quality. 813 public void splitConstants(IRCode code) { 814 for (BasicBlock block : code.blocks) { 815 // Split constants that flow into phis. It is likely that these constants will have moves 816 // generated for them anyway and we might as well insert a const instruction in the right 817 // predecessor block. 818 splitPhiConstants(code, block); 819 // Split constants that flow into ranged invokes. This gives the register allocator more 820 // freedom in assigning register to ranged invokes which can greatly reduce the number 821 // of register needed (and thereby code size as well). 822 splitRangedInvokeConstants(code, block); 823 } 824 } 825 826 private void splitRangedInvokeConstants(IRCode code, BasicBlock block) { 827 InstructionListIterator it = block.listIterator(); 828 while (it.hasNext()) { 829 Instruction current = it.next(); 830 if (current.isInvoke() && current.asInvoke().requiredArgumentRegisters() > 5) { 831 Invoke invoke = current.asInvoke(); 832 it.previous(); 833 Map<ConstNumber, ConstNumber> oldToNew = new HashMap<>(); 834 for (int i = 0; i < invoke.inValues().size(); i++) { 835 Value value = invoke.inValues().get(i); 836 if (value.isConstant() && value.numberOfUsers() > 1) { 837 ConstNumber definition = value.getConstInstruction().asConstNumber(); 838 Value originalValue = definition.outValue(); 839 ConstNumber newNumber = oldToNew.get(definition); 840 if (newNumber == null) { 841 newNumber = ConstNumber.copyOf(code, definition); 842 it.add(newNumber); 843 oldToNew.put(definition, newNumber); 844 } 845 invoke.inValues().set(i, newNumber.outValue()); 846 originalValue.removeUser(invoke); 847 newNumber.outValue().addUser(invoke); 848 } 849 } 850 it.next(); 851 } 852 } 853 } 854 855 private void splitPhiConstants(IRCode code, BasicBlock block) { 856 for (int i = 0; i < block.getPredecessors().size(); i++) { 857 Map<ConstNumber, ConstNumber> oldToNew = new IdentityHashMap<>(); 858 BasicBlock predecessor = block.getPredecessors().get(i); 859 for (Phi phi : block.getPhis()) { 860 Value operand = phi.getOperand(i); 861 if (!operand.isPhi() && operand.isConstant()) { 862 ConstNumber definition = operand.getConstInstruction().asConstNumber(); 863 ConstNumber newNumber = oldToNew.get(definition); 864 Value originalValue = definition.outValue(); 865 if (newNumber == null) { 866 newNumber = ConstNumber.copyOf(code, definition); 867 oldToNew.put(definition, newNumber); 868 insertConstantInBlock(newNumber, predecessor); 869 } 870 phi.getOperands().set(i, newNumber.outValue()); 871 originalValue.removePhiUser(phi); 872 newNumber.outValue().addPhiUser(phi); 873 } 874 } 875 } 876 } 877 878 public void shortenLiveRanges(IRCode code) { 879 // Currently, we are only shortening the live range of constants in the entry block. 880 // TODO(ager): Generalize this to shorten live ranges for more instructions? Currently 881 // doing so seems to make things worse. 882 Map<BasicBlock, List<Instruction>> addConstantInBlock = new HashMap<>(); 883 DominatorTree dominatorTree = new DominatorTree(code); 884 BasicBlock block = code.blocks.get(0); 885 InstructionListIterator it = block.listIterator(); 886 List<Instruction> toInsertInThisBlock = new ArrayList<>(); 887 while (it.hasNext()) { 888 Instruction instruction = it.next(); 889 if (instruction.isConstNumber()) { 890 // Collect the blocks for all users of the constant. 891 List<BasicBlock> userBlocks = new LinkedList<>(); 892 for (Instruction user : instruction.outValue().uniqueUsers()) { 893 userBlocks.add(user.getBlock()); 894 } 895 for (Phi phi : instruction.outValue().uniquePhiUsers()) { 896 userBlocks.add(phi.getBlock()); 897 } 898 // Locate the closest dominator block for all user blocks. 899 BasicBlock dominator = dominatorTree.closestDominator(userBlocks); 900 // If the closest dominator block is a block that uses the constant for a phi the constant 901 // needs to go in the immediate dominator block so that it is available for phi moves. 902 for (Phi phi : instruction.outValue().uniquePhiUsers()) { 903 if (phi.getBlock() == dominator) { 904 dominator = dominatorTree.immediateDominator(dominator); 905 break; 906 } 907 } 908 // Move the const instruction as close to its uses as possible. 909 it.detach(); 910 if (dominator != block) { 911 // Post-pone constant insertion in order to use a global heuristics. 912 List<Instruction> csts = addConstantInBlock.get(dominator); 913 if (csts == null) { 914 csts = new ArrayList<>(); 915 addConstantInBlock.put(dominator, csts); 916 } 917 csts.add(instruction); 918 } else { 919 toInsertInThisBlock.add(instruction); 920 } 921 } 922 } 923 924 // Heuristic to decide if constant instructions are shared in dominator block of usages or move 925 // to the usages. 926 for (Map.Entry<BasicBlock, List<Instruction>> entry : addConstantInBlock.entrySet()) { 927 if (entry.getValue().size() > STOP_SHARED_CONSTANT_THRESHOLD) { 928 // Too much constants in the same block, do not longer shared them except if they are used 929 // by phi instructions. 930 for (Instruction instruction : entry.getValue()) { 931 if (instruction.outValue().numberOfPhiUsers() != 0) { 932 // Add constant into the dominator block of usages. 933 insertConstantInBlock(instruction, entry.getKey()); 934 } else { 935 assert instruction.outValue().numberOfUsers() != 0; 936 ConstNumber constNumber = instruction.asConstNumber(); 937 Value constantValue = instruction.outValue(); 938 for (Instruction user : constantValue.uniqueUsers()) { 939 ConstNumber newCstNum = ConstNumber.copyOf(code, constNumber); 940 InstructionListIterator iterator = user.getBlock().listIterator(user); 941 iterator.previous(); 942 iterator.add(newCstNum); 943 user.replaceValue(constantValue, newCstNum.outValue()); 944 } 945 } 946 } 947 } else { 948 // Add constant into the dominator block of usages. 949 for (Instruction inst : entry.getValue()) { 950 insertConstantInBlock(inst, entry.getKey()); 951 } 952 } 953 } 954 955 for (Instruction toInsert : toInsertInThisBlock) { 956 insertConstantInBlock(toInsert, block); 957 } 958 assert code.isConsistentSSA(); 959 } 960 961 private void insertConstantInBlock(Instruction instruction, BasicBlock block) { 962 boolean hasCatchHandlers = block.hasCatchHandlers(); 963 InstructionListIterator insertAt = block.listIterator(); 964 // Place the instruction as late in the block as we can. It needs to go before users 965 // and if we have catch handlers it needs to be placed before the throwing instruction. 966 insertAt.nextUntil(i -> { 967 return i.inValues().contains(instruction.outValue()) 968 || i.isJumpInstruction() 969 || (hasCatchHandlers && i.instructionInstanceCanThrow()); 970 }); 971 insertAt.previous(); 972 insertAt.add(instruction); 973 } 974 975 private short[] computeArrayFilledData( 976 NewArrayEmpty newArray, int size, BasicBlock block, int elementSize) { 977 ConstNumber[] values = computeConstantArrayValues(newArray, block, size); 978 if (values == null) { 979 return null; 980 } 981 if (elementSize == 1) { 982 short[] result = new short[(size + 1) / 2]; 983 for (int i = 0; i < size; i += 2) { 984 short value = (short) (values[i].getIntValue() & 0xFF); 985 if (i + 1 < size) { 986 value |= (short) ((values[i + 1].getIntValue() & 0xFF) << 8); 987 } 988 result[i / 2] = value; 989 } 990 return result; 991 } 992 assert elementSize == 2 || elementSize == 4 || elementSize == 8; 993 int shortsPerConstant = elementSize / 2; 994 short[] result = new short[size * shortsPerConstant]; 995 for (int i = 0; i < size; i++) { 996 long value = values[i].getRawValue(); 997 for (int part = 0; part < shortsPerConstant; part++) { 998 result[i * shortsPerConstant + part] = (short) ((value >> (16 * part)) & 0xFFFFL); 999 } 1000 } 1001 return result; 1002 } 1003 1004 private ConstNumber[] computeConstantArrayValues( 1005 NewArrayEmpty newArray, BasicBlock block, int size) { 1006 if (size > MAX_FILL_ARRAY_SIZE) { 1007 return null; 1008 } 1009 ConstNumber[] values = new ConstNumber[size]; 1010 int remaining = size; 1011 Set<Instruction> users = newArray.outValue().uniqueUsers(); 1012 // We allow the array instantiations to cross block boundaries as long as it hasn't encountered 1013 // an instruction instance that can throw an exception. 1014 InstructionListIterator it = block.listIterator(); 1015 it.nextUntil(i -> i == newArray); 1016 do { 1017 while (it.hasNext()) { 1018 Instruction instruction = it.next(); 1019 // If we encounter an instruction that can throw an exception we need to bail out of the 1020 // optimization so that we do not transform half-initialized arrays into fully initialized 1021 // arrays on exceptional edges. 1022 if (instruction.instructionInstanceCanThrow()) { 1023 return null; 1024 } 1025 if (!users.contains(instruction)) { 1026 continue; 1027 } 1028 // If the initialization sequence is broken by another use we cannot use a 1029 // fill-array-data instruction. 1030 if (!instruction.isArrayPut()) { 1031 return null; 1032 } 1033 ArrayPut arrayPut = instruction.asArrayPut(); 1034 if (!arrayPut.source().isConstant()) { 1035 return null; 1036 } 1037 assert arrayPut.index().isConstant(); 1038 int index = arrayPut.index().getConstInstruction().asConstNumber().getIntValue(); 1039 assert index >= 0 && index < values.length; 1040 if (values[index] != null) { 1041 return null; 1042 } 1043 ConstNumber value = arrayPut.source().getConstInstruction().asConstNumber(); 1044 values[index] = value; 1045 --remaining; 1046 if (remaining == 0) { 1047 return values; 1048 } 1049 } 1050 block = block.exit().isGoto() ? block.exit().asGoto().getTarget() : null; 1051 it = block != null ? block.listIterator() : null; 1052 } while (it != null); 1053 return null; 1054 } 1055 1056 private boolean isPrimitiveNewArrayWithConstantPositiveSize(Instruction instruction) { 1057 if (!(instruction instanceof NewArrayEmpty)) { 1058 return false; 1059 } 1060 NewArrayEmpty newArray = instruction.asNewArrayEmpty(); 1061 if (!newArray.size().isConstant()) { 1062 return false; 1063 } 1064 int size = newArray.size().getConstInstruction().asConstNumber().getIntValue(); 1065 if (size < 1) { 1066 return false; 1067 } 1068 if (!newArray.type.isPrimitiveArrayType()) { 1069 return false; 1070 } 1071 return true; 1072 } 1073 1074 /** 1075 * Replace NewArrayEmpty followed by stores of constants to all entries with NewArrayEmpty 1076 * and FillArrayData. 1077 */ 1078 public void simplifyArrayConstruction(IRCode code) { 1079 for (BasicBlock block : code.blocks) { 1080 // Map from the array value to the number of array put instruction to remove for that value. 1081 Map<Value, Integer> storesToRemoveForArray = new HashMap<>(); 1082 // First pass: identify candidates and insert fill array data instruction. 1083 InstructionListIterator it = block.listIterator(); 1084 while (it.hasNext()) { 1085 Instruction instruction = it.next(); 1086 if (!isPrimitiveNewArrayWithConstantPositiveSize(instruction)) { 1087 continue; 1088 } 1089 NewArrayEmpty newArray = instruction.asNewArrayEmpty(); 1090 int size = newArray.size().getConstInstruction().asConstNumber().getIntValue(); 1091 // If there is only one element it is typically smaller to generate the array put 1092 // instruction instead of fill array data. 1093 if (size == 1) { 1094 continue; 1095 } 1096 int elementSize = newArray.type.elementSizeForPrimitiveArrayType(); 1097 short[] contents = computeArrayFilledData(newArray, size, block, elementSize); 1098 if (contents == null) { 1099 continue; 1100 } 1101 storesToRemoveForArray.put(newArray.outValue(), size); 1102 int arraySize = newArray.size().getConstInstruction().asConstNumber().getIntValue(); 1103 NewArrayFilledData fillArray = new NewArrayFilledData( 1104 newArray.outValue(), elementSize, arraySize, contents); 1105 it.add(fillArray); 1106 } 1107 // Second pass: remove all the array put instructions for the array for which we have 1108 // inserted a fill array data instruction instead. 1109 if (!storesToRemoveForArray.isEmpty()) { 1110 do { 1111 it = block.listIterator(); 1112 while (it.hasNext()) { 1113 Instruction instruction = it.next(); 1114 if (instruction.isArrayPut()) { 1115 Value array = instruction.asArrayPut().array(); 1116 Integer toRemoveCount = storesToRemoveForArray.get(array); 1117 if (toRemoveCount != null && toRemoveCount > 0) { 1118 storesToRemoveForArray.put(array, toRemoveCount - 1); 1119 it.remove(); 1120 } 1121 } 1122 } 1123 block = block.exit().isGoto() ? block.exit().asGoto().getTarget() : null; 1124 } while (block != null); 1125 } 1126 } 1127 } 1128 1129 private class ExpressionEquivalence extends Equivalence<Instruction> { 1130 1131 @Override 1132 protected boolean doEquivalent(Instruction a, Instruction b) { 1133 if (a.getClass() != b.getClass() || !a.identicalNonValueParts(b)) { 1134 return false; 1135 } 1136 // For commutative binary operations any order of in-values are equal. 1137 if (a.isBinop() && a.asBinop().isCommutative()) { 1138 Value a0 = a.inValues().get(0); 1139 Value a1 = a.inValues().get(1); 1140 Value b0 = b.inValues().get(0); 1141 Value b1 = b.inValues().get(1); 1142 return (a0.equals(b0) && a1.equals(b1)) || (a0.equals(b1) && a1.equals(b0)); 1143 } else { 1144 // Compare all in-values. 1145 assert a.inValues().size() == b.inValues().size(); 1146 for (int i = 0; i < a.inValues().size(); i++) { 1147 if (!a.inValues().get(i).equals(b.inValues().get(i))) { 1148 return false; 1149 } 1150 } 1151 return true; 1152 } 1153 } 1154 1155 @Override 1156 protected int doHash(Instruction instruction) { 1157 final int prime = 29; 1158 int hash = instruction.getClass().hashCode(); 1159 if (instruction.isBinop()) { 1160 Binop binop = instruction.asBinop(); 1161 Value in0 = instruction.inValues().get(0); 1162 Value in1 = instruction.inValues().get(1); 1163 if (binop.isCommutative()) { 1164 hash += hash * prime + in0.hashCode() * in1.hashCode(); 1165 } else { 1166 hash += hash * prime + in0.hashCode(); 1167 hash += hash * prime + in1.hashCode(); 1168 } 1169 return hash; 1170 } else { 1171 for (Value value : instruction.inValues()) { 1172 hash += hash * prime + value.hashCode(); 1173 } 1174 } 1175 return hash; 1176 } 1177 } 1178 1179 private boolean shareCatchHandlers(Instruction i0, Instruction i1) { 1180 if (!i0.instructionTypeCanThrow()) { 1181 assert !i1.instructionTypeCanThrow(); 1182 return true; 1183 } 1184 assert i1.instructionTypeCanThrow(); 1185 // TODO(sgjesse): This could be even better by checking for the exceptions thrown, e.g. div 1186 // and rem only ever throw ArithmeticException. 1187 CatchHandlers<BasicBlock> ch0 = i0.getBlock().getCatchHandlers(); 1188 CatchHandlers<BasicBlock> ch1 = i1.getBlock().getCatchHandlers(); 1189 return ch0.equals(ch1); 1190 } 1191 1192 public void commonSubexpressionElimination(IRCode code) { 1193 final ListMultimap<Wrapper<Instruction>, Value> instructionToValue = ArrayListMultimap.create(); 1194 final DominatorTree dominatorTree = new DominatorTree(code); 1195 final ExpressionEquivalence equivalence = new ExpressionEquivalence(); 1196 1197 for (int i = 0; i < dominatorTree.getSortedBlocks().length; i++) { 1198 BasicBlock block = dominatorTree.getSortedBlocks()[i]; 1199 Iterator<Instruction> iterator = block.iterator(); 1200 while (iterator.hasNext()) { 1201 Instruction instruction = iterator.next(); 1202 if (instruction.isBinop() 1203 || instruction.isUnop() 1204 || instruction.isInstanceOf() 1205 || instruction.isCheckCast()) { 1206 List<Value> candidates = instructionToValue.get(equivalence.wrap(instruction)); 1207 boolean eliminated = false; 1208 if (candidates.size() > 0) { 1209 for (Value candidate : candidates) { 1210 if (dominatorTree.dominatedBy(block, candidate.definition.getBlock()) && 1211 shareCatchHandlers(instruction, candidate.definition)) { 1212 instruction.outValue().replaceUsers(candidate); 1213 eliminated = true; 1214 iterator.remove(); 1215 break; // Don't try any more candidates. 1216 } 1217 } 1218 } 1219 if (!eliminated) { 1220 instructionToValue.put(equivalence.wrap(instruction), instruction.outValue()); 1221 } 1222 } 1223 } 1224 } 1225 assert code.isConsistentSSA(); 1226 } 1227 1228 public void simplifyIf(IRCode code) { 1229 DominatorTree dominator = new DominatorTree(code); 1230 code.clearMarks(); 1231 for (BasicBlock block : code.blocks) { 1232 if (block.isMarked()) { 1233 continue; 1234 } 1235 if (block.exit().isIf()) { 1236 // First rewrite zero comparison. 1237 rewriteIfWithConstZero(block); 1238 1239 // Simplify if conditions when possible. 1240 If theIf = block.exit().asIf(); 1241 List<Value> inValues = theIf.inValues(); 1242 int cond; 1243 if (inValues.get(0).isConstant() 1244 && (theIf.isZeroTest() || inValues.get(1).isConstant())) { 1245 // Zero test with a constant of comparison between between two constants. 1246 if (theIf.isZeroTest()) { 1247 cond = inValues.get(0).getConstInstruction().asConstNumber().getIntValue(); 1248 } else { 1249 int left = inValues.get(0).getConstInstruction().asConstNumber().getIntValue(); 1250 int right = inValues.get(1).getConstInstruction().asConstNumber().getIntValue(); 1251 cond = left - right; 1252 } 1253 } else if (inValues.get(0).hasValueRange() 1254 && (theIf.isZeroTest() || inValues.get(1).hasValueRange())) { 1255 // Zero test with a value range, or comparison between between two values, 1256 // each with a value ranges. 1257 if (theIf.isZeroTest()) { 1258 if (inValues.get(0).isValueInRange(0)) { 1259 // Zero in in the range - can't determine the comparison. 1260 continue; 1261 } 1262 cond = Long.signum(inValues.get(0).getValueRange().getMin()); 1263 } else { 1264 LongInterval leftRange = inValues.get(0).getValueRange(); 1265 LongInterval rightRange = inValues.get(1).getValueRange(); 1266 if (leftRange.overlapsWith(rightRange)) { 1267 // Ranges overlap - can't determine the comparison. 1268 continue; 1269 } 1270 // There is no overlap. 1271 cond = Long.signum(leftRange.getMin() - rightRange.getMin()); 1272 } 1273 } else { 1274 continue; 1275 } 1276 BasicBlock target = theIf.targetFromCondition(cond); 1277 BasicBlock deadTarget = 1278 target == theIf.getTrueTarget() ? theIf.fallthroughBlock() : theIf.getTrueTarget(); 1279 List<BasicBlock> removedBlocks = block.unlink(deadTarget, dominator); 1280 for (BasicBlock removedBlock : removedBlocks) { 1281 if (!removedBlock.isMarked()) { 1282 removedBlock.mark(); 1283 } 1284 } 1285 assert theIf == block.exit(); 1286 replaceLastInstruction(block, new Goto()); 1287 assert block.exit().isGoto(); 1288 assert block.exit().asGoto().getTarget() == target; 1289 } 1290 } 1291 code.removeMarkedBlocks(); 1292 assert code.isConsistentSSA(); 1293 } 1294 1295 private void rewriteIfWithConstZero(BasicBlock block) { 1296 If theIf = block.exit().asIf(); 1297 if (theIf.isZeroTest()) { 1298 return; 1299 } 1300 1301 List<Value> inValues = theIf.inValues(); 1302 Value leftValue = inValues.get(0); 1303 Value rightValue = inValues.get(1); 1304 if (leftValue.isConstant() || rightValue.isConstant()) { 1305 if (leftValue.isConstant()) { 1306 int left = leftValue.getConstInstruction().asConstNumber().getIntValue(); 1307 if (left == 0) { 1308 If ifz = new If(theIf.getType().forSwappedOperands(), rightValue); 1309 replaceLastInstruction(block, ifz); 1310 assert block.exit() == ifz; 1311 } 1312 } else { 1313 assert rightValue.isConstant(); 1314 int right = rightValue.getConstInstruction().asConstNumber().getIntValue(); 1315 if (right == 0) { 1316 If ifz = new If(theIf.getType(), leftValue); 1317 replaceLastInstruction(block, ifz); 1318 assert block.exit() == ifz; 1319 } 1320 } 1321 } 1322 } 1323 1324 private void replaceLastInstruction(BasicBlock block, Instruction instruction) { 1325 InstructionListIterator iterator = block.listIterator(block.getInstructions().size()); 1326 iterator.previous(); 1327 iterator.replaceCurrentInstruction(instruction); 1328 } 1329 1330 public void rewriteLongCompareAndRequireNonNull(IRCode code, InternalOptions options) { 1331 if (options.canUseLongCompareAndObjectsNonNull()) { 1332 return; 1333 } 1334 1335 InstructionIterator iterator = code.instructionIterator(); 1336 while (iterator.hasNext()) { 1337 Instruction current = iterator.next(); 1338 if (current.isInvokeMethod()) { 1339 DexMethod invokedMethod = current.asInvokeMethod().getInvokedMethod(); 1340 if (invokedMethod == dexItemFactory.longMethods.compare) { 1341 // Rewrite calls to Long.compare for sdk versions that do not have that method. 1342 List<Value> inValues = current.inValues(); 1343 assert inValues.size() == 2; 1344 iterator.replaceCurrentInstruction( 1345 new Cmp(NumericType.LONG, Bias.NONE, current.outValue(), inValues.get(0), 1346 inValues.get(1))); 1347 } else if (invokedMethod == dexItemFactory.objectsMethods.requireNonNull) { 1348 // Rewrite calls to Objects.requireNonNull(Object) because Javac 9 start to use it for 1349 // synthesized null checks. 1350 InvokeVirtual callToGetClass = new InvokeVirtual(dexItemFactory.objectMethods.getClass, 1351 null, current.inValues()); 1352 if (current.outValue() != null) { 1353 current.outValue().replaceUsers(current.inValues().get(0)); 1354 current.setOutValue(null); 1355 } 1356 iterator.replaceCurrentInstruction(callToGetClass); 1357 } 1358 } 1359 } 1360 assert code.isConsistentSSA(); 1361 } 1362 1363 // Removes calls to Throwable.addSuppressed(Throwable) and rewrites 1364 // Throwable.getSuppressed() into new Throwable[0]. 1365 // 1366 // Note that addSuppressed() and getSuppressed() methods are final in 1367 // Throwable, so these changes don't have to worry about overrides. 1368 public void rewriteThrowableAddAndGetSuppressed(IRCode code) { 1369 DexItemFactory.ThrowableMethods throwableMethods = dexItemFactory.throwableMethods; 1370 1371 for (BasicBlock block : code.blocks) { 1372 InstructionListIterator iterator = block.listIterator(); 1373 while (iterator.hasNext()) { 1374 Instruction current = iterator.next(); 1375 if (current.isInvokeMethod()) { 1376 DexMethod invokedMethod = current.asInvokeMethod().getInvokedMethod(); 1377 1378 if (matchesMethodOfThrowable(invokedMethod, throwableMethods.addSuppressed)) { 1379 // Remove Throwable::addSuppressed(Throwable) call. 1380 iterator.remove(); 1381 } else if (matchesMethodOfThrowable(invokedMethod, throwableMethods.getSuppressed)) { 1382 Value destValue = current.outValue(); 1383 if (destValue == null) { 1384 // If the result of the call was not used we don't create 1385 // an empty array and just remove the call. 1386 iterator.remove(); 1387 continue; 1388 } 1389 1390 // Replace call to Throwable::getSuppressed() with new Throwable[0]. 1391 1392 // First insert the constant value *before* the current instruction. 1393 ConstNumber zero = code.createIntConstant(0); 1394 assert iterator.hasPrevious(); 1395 iterator.previous(); 1396 iterator.add(zero); 1397 1398 // Then replace the invoke instruction with NewArrayEmpty instruction. 1399 Instruction next = iterator.next(); 1400 assert current == next; 1401 NewArrayEmpty newArray = new NewArrayEmpty(destValue, zero.outValue(), 1402 dexItemFactory.createType(dexItemFactory.throwableArrayDescriptor)); 1403 iterator.replaceCurrentInstruction(newArray); 1404 } 1405 } 1406 } 1407 } 1408 assert code.isConsistentSSA(); 1409 } 1410 1411 private boolean matchesMethodOfThrowable(DexMethod invoked, DexMethod expected) { 1412 return invoked.name == expected.name 1413 && invoked.proto == expected.proto 1414 && isSubtypeOfThrowable(invoked.holder); 1415 } 1416 1417 private boolean isSubtypeOfThrowable(DexType type) { 1418 while (type != null && type != dexItemFactory.objectType) { 1419 if (type == dexItemFactory.throwableType) { 1420 return true; 1421 } 1422 DexClass dexClass = appInfo.definitionFor(type); 1423 if (dexClass == null) { 1424 throw new CompilationError("Class or interface " + type.toSourceString() + 1425 " required for desugaring of try-with-resources is not found."); 1426 } 1427 type = dexClass.superType; 1428 } 1429 return false; 1430 } 1431 1432 private Value addConstString(IRCode code, InstructionListIterator iterator, String s) { 1433 Value value = code.createValue(MoveType.OBJECT);; 1434 iterator.add(new ConstString(value, dexItemFactory.createString(s))); 1435 return value; 1436 } 1437 1438 /** 1439 * Insert code into <code>method</code> to log the argument types to System.out. 1440 * 1441 * The type is determined by calling getClass() on the argument. 1442 */ 1443 public void logArgumentTypes(DexEncodedMethod method, IRCode code) { 1444 List<Value> arguments = code.collectArguments(); 1445 BasicBlock block = code.blocks.getFirst(); 1446 InstructionListIterator iterator = block.listIterator(); 1447 1448 // Split arguments into their own block. 1449 iterator.nextUntil(instruction -> !instruction.isArgument()); 1450 iterator.previous(); 1451 iterator.split(code); 1452 iterator.previous(); 1453 1454 // Now that the block is split there should not be any catch handlers in the block. 1455 assert !block.hasCatchHandlers(); 1456 Value out = code.createValue(MoveType.OBJECT); 1457 DexType javaLangSystemType = dexItemFactory.createType("Ljava/lang/System;"); 1458 DexType javaIoPrintStreamType = dexItemFactory.createType("Ljava/io/PrintStream;"); 1459 1460 DexProto proto = dexItemFactory.createProto( 1461 dexItemFactory.voidType, new DexType[]{dexItemFactory.objectType}); 1462 DexMethod print = dexItemFactory.createMethod(javaIoPrintStreamType, proto, "print"); 1463 DexMethod printLn = dexItemFactory.createMethod(javaIoPrintStreamType, proto, "println"); 1464 1465 iterator.add( 1466 new StaticGet(MemberType.OBJECT, out, 1467 dexItemFactory.createField(javaLangSystemType, javaIoPrintStreamType, "out"))); 1468 1469 Value value = code.createValue(MoveType.OBJECT); 1470 iterator.add(new ConstString(value, dexItemFactory.createString("INVOKE "))); 1471 iterator.add(new InvokeVirtual(print, null, ImmutableList.of(out, value))); 1472 1473 value = code.createValue(MoveType.OBJECT);; 1474 iterator.add( 1475 new ConstString(value, dexItemFactory.createString(method.method.qualifiedName()))); 1476 iterator.add(new InvokeVirtual(print, null, ImmutableList.of(out, value))); 1477 1478 Value openParenthesis = addConstString(code, iterator, "("); 1479 Value comma = addConstString(code, iterator, ","); 1480 Value closeParenthesis = addConstString(code, iterator, ")"); 1481 Value indent = addConstString(code, iterator, " "); 1482 Value nul = addConstString(code, iterator, "(null)"); 1483 Value primitive = addConstString(code, iterator, "(primitive)"); 1484 Value empty = addConstString(code, iterator, ""); 1485 1486 iterator.add(new InvokeVirtual(printLn, null, ImmutableList.of(out, openParenthesis))); 1487 for (int i = 0; i < arguments.size(); i++) { 1488 iterator.add(new InvokeVirtual(print, null, ImmutableList.of(out, indent))); 1489 1490 // Add a block for end-of-line printing. 1491 BasicBlock eol = BasicBlock.createGotoBlock(code.blocks.size()); 1492 code.blocks.add(eol); 1493 1494 BasicBlock successor = block.unlinkSingleSuccessor(); 1495 block.link(eol); 1496 eol.link(successor); 1497 1498 Value argument = arguments.get(i); 1499 if (argument.outType() != MoveType.OBJECT) { 1500 iterator.add(new InvokeVirtual(print, null, ImmutableList.of(out, primitive))); 1501 } else { 1502 // Insert "if (argument != null) ...". 1503 successor = block.unlinkSingleSuccessor(); 1504 If theIf = new If(If.Type.NE, argument); 1505 BasicBlock ifBlock = BasicBlock.createIfBlock(code.blocks.size(), theIf); 1506 code.blocks.add(ifBlock); 1507 // Fallthrough block must be added right after the if. 1508 BasicBlock isNullBlock = BasicBlock.createGotoBlock(code.blocks.size()); 1509 code.blocks.add(isNullBlock); 1510 BasicBlock isNotNullBlock = BasicBlock.createGotoBlock(code.blocks.size()); 1511 code.blocks.add(isNotNullBlock); 1512 1513 // Link the added blocks together. 1514 block.link(ifBlock); 1515 ifBlock.link(isNotNullBlock); 1516 ifBlock.link(isNullBlock); 1517 isNotNullBlock.link(successor); 1518 isNullBlock.link(successor); 1519 1520 // Fill code into the blocks. 1521 iterator = isNullBlock.listIterator(); 1522 iterator.add(new InvokeVirtual(print, null, ImmutableList.of(out, nul))); 1523 iterator = isNotNullBlock.listIterator(); 1524 value = code.createValue(MoveType.OBJECT); 1525 iterator.add(new InvokeVirtual(dexItemFactory.objectMethods.getClass, value, 1526 ImmutableList.of(arguments.get(i)))); 1527 iterator.add(new InvokeVirtual(print, null, ImmutableList.of(out, value))); 1528 } 1529 1530 iterator = eol.listIterator(); 1531 if (i == arguments.size() - 1) { 1532 iterator.add(new InvokeVirtual(printLn, null, ImmutableList.of(out, closeParenthesis))); 1533 } else { 1534 iterator.add(new InvokeVirtual(printLn, null, ImmutableList.of(out, comma))); 1535 } 1536 block = eol; 1537 } 1538 // When we fall out of the loop the iterator is in the last eol block. 1539 iterator.add(new InvokeVirtual(printLn, null, ImmutableList.of(out, empty))); 1540 } 1541} 1542