DexBuilder.java revision fc475d644e6da9968673a7509085a7e9a3b0c531
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. 4package com.android.tools.r8.ir.conversion; 5 6import com.android.tools.r8.code.FillArrayData; 7import com.android.tools.r8.code.FillArrayDataPayload; 8import com.android.tools.r8.code.Format31t; 9import com.android.tools.r8.code.Goto; 10import com.android.tools.r8.code.Goto16; 11import com.android.tools.r8.code.Goto32; 12import com.android.tools.r8.code.IfEq; 13import com.android.tools.r8.code.IfEqz; 14import com.android.tools.r8.code.IfGe; 15import com.android.tools.r8.code.IfGez; 16import com.android.tools.r8.code.IfGt; 17import com.android.tools.r8.code.IfGtz; 18import com.android.tools.r8.code.IfLe; 19import com.android.tools.r8.code.IfLez; 20import com.android.tools.r8.code.IfLt; 21import com.android.tools.r8.code.IfLtz; 22import com.android.tools.r8.code.IfNe; 23import com.android.tools.r8.code.IfNez; 24import com.android.tools.r8.code.Instruction; 25import com.android.tools.r8.code.Move16; 26import com.android.tools.r8.code.MoveFrom16; 27import com.android.tools.r8.code.MoveObject; 28import com.android.tools.r8.code.MoveObject16; 29import com.android.tools.r8.code.MoveObjectFrom16; 30import com.android.tools.r8.code.MoveWide; 31import com.android.tools.r8.code.MoveWide16; 32import com.android.tools.r8.code.MoveWideFrom16; 33import com.android.tools.r8.code.Nop; 34import com.android.tools.r8.dex.Constants; 35import com.android.tools.r8.errors.Unreachable; 36import com.android.tools.r8.graph.DexCode; 37import com.android.tools.r8.graph.DexCode.Try; 38import com.android.tools.r8.graph.DexCode.TryHandler; 39import com.android.tools.r8.graph.DexCode.TryHandler.TypeAddrPair; 40import com.android.tools.r8.graph.DexDebugEventBuilder; 41import com.android.tools.r8.graph.DexItemFactory; 42import com.android.tools.r8.graph.DexString; 43import com.android.tools.r8.graph.DexType; 44import com.android.tools.r8.ir.code.Argument; 45import com.android.tools.r8.ir.code.BasicBlock; 46import com.android.tools.r8.ir.code.CatchHandlers; 47import com.android.tools.r8.ir.code.IRCode; 48import com.android.tools.r8.ir.code.If; 49import com.android.tools.r8.ir.code.InstructionIterator; 50import com.android.tools.r8.ir.code.Move; 51import com.android.tools.r8.ir.code.NewArrayFilledData; 52import com.android.tools.r8.ir.code.Switch; 53import com.android.tools.r8.ir.code.Value; 54import com.android.tools.r8.ir.regalloc.LinearScanRegisterAllocator; 55import com.android.tools.r8.ir.regalloc.RegisterAllocator; 56import com.google.common.collect.BiMap; 57import com.google.common.collect.HashBiMap; 58import com.google.common.collect.Lists; 59import com.google.common.collect.Sets; 60import java.util.ArrayList; 61import java.util.List; 62import java.util.ListIterator; 63import java.util.Map; 64import java.util.Set; 65 66/** 67 * Builder object for constructing dex bytecode from the high-level IR. 68 */ 69public class DexBuilder { 70 71 // The IR representation of the code to build. 72 private final IRCode ir; 73 74 // The register allocator providing register assignments for the code to build. 75 private final RegisterAllocator registerAllocator; 76 77 private final DexItemFactory dexItemFactory; 78 79 // List of information about switch payloads that have to be created at the end of the 80 // dex code. 81 private final List<SwitchPayloadInfo> switchPayloadInfos = new ArrayList<>(); 82 83 // List of generated FillArrayData dex instructions. 84 private final List<FillArrayDataInfo> fillArrayDataInfos = new ArrayList<>(); 85 86 // First jumbo string if known. 87 private final DexString firstJumboString; 88 89 // Set of if instructions that have offsets that are so large that they cannot be encoded in 90 // the if instruction format. 91 private Set<BasicBlock> ifsNeedingRewrite = Sets.newIdentityHashSet(); 92 93 // Running bounds on offsets. 94 private int maxOffset = 0; 95 private int minOffset = 0; 96 97 // Mapping from IR instructions to info for computing the dex translation. Use the 98 // getInfo/setInfo methods to access the mapping. 99 private Info[] instructionToInfo; 100 101 // The number of ingoing and outgoing argument registers for the code. 102 private int inRegisterCount = 0; 103 private int outRegisterCount = 0; 104 105 // The string reference in the code with the highest index. 106 private DexString highestSortingReferencedString = null; 107 108 BasicBlock nextBlock; 109 110 public DexBuilder(IRCode ir, RegisterAllocator registerAllocator, DexItemFactory dexItemFactory) { 111 assert ir != null; 112 assert registerAllocator != null; 113 assert dexItemFactory != null; 114 this.ir = ir; 115 this.registerAllocator = registerAllocator; 116 this.dexItemFactory = dexItemFactory; 117 this.firstJumboString = null; 118 } 119 120 public DexBuilder(IRCode ir, RegisterAllocator registerAllocator, 121 DexItemFactory dexItemFactory, DexString firstJumboString) { 122 assert ir != null; 123 assert registerAllocator != null; 124 assert dexItemFactory != null; 125 this.ir = ir; 126 this.registerAllocator = registerAllocator; 127 this.dexItemFactory = dexItemFactory; 128 this.firstJumboString = firstJumboString; 129 } 130 131 private void reset() { 132 switchPayloadInfos.clear(); 133 fillArrayDataInfos.clear(); 134 ifsNeedingRewrite.clear(); 135 maxOffset = 0; 136 minOffset = 0; 137 instructionToInfo = new Info[instructionNumberToIndex(ir.numberRemainingInstructions())]; 138 inRegisterCount = 0; 139 outRegisterCount = 0; 140 highestSortingReferencedString = null; 141 nextBlock = null; 142 } 143 144 public boolean isJumboString(DexString string) { 145 if (firstJumboString == null) { 146 return false; 147 } 148 // We have to use compareTo here, as slowCompareTo will return the wrong order when minification 149 // is used. 150 return firstJumboString.compareTo(string) <= 0; 151 } 152 153 /** 154 * Build the dex instructions added to this builder. 155 * 156 * This is a two pass construction that will first compute concrete offsets and then construct 157 * the concrete instructions. 158 */ 159 public DexCode build(int numberOfArguments) { 160 int numberOfInstructions; 161 int offset; 162 163 do { 164 // Rewrite ifs that are know from the previous iteration to have offsets that are too 165 // large for the if encoding. 166 rewriteIfs(); 167 168 // Reset the state of the builder to start from scratch. 169 reset(); 170 171 // Populate the builder info objects. 172 numberOfInstructions = 0; 173 ListIterator<BasicBlock> iterator = ir.listIterator(); 174 assert iterator.hasNext(); 175 BasicBlock block = iterator.next(); 176 do { 177 nextBlock = iterator.hasNext() ? iterator.next() : null; 178 block.buildDex(this); 179 block = nextBlock; 180 } while (block != null); 181 182 // Compute offsets. 183 offset = 0; 184 InstructionIterator it = ir.instructionIterator(); 185 while (it.hasNext()) { 186 Info info = getInfo(it.next()); 187 info.setOffset(offset); 188 offset += info.computeSize(this); 189 ++numberOfInstructions; 190 } 191 } while (!ifsNeedingRewrite.isEmpty()); 192 193 // Build instructions. 194 DexDebugEventBuilder debugEventBuilder = 195 new DexDebugEventBuilder(ir.method.method, dexItemFactory); 196 List<Instruction> dexInstructions = new ArrayList<>(numberOfInstructions); 197 int instructionOffset = 0; 198 InstructionIterator instructionIterator = ir.instructionIterator(); 199 int lastMoveExceptionOffset = -1; 200 while (instructionIterator.hasNext()) { 201 com.android.tools.r8.ir.code.Instruction ir = instructionIterator.next(); 202 Info info = getInfo(ir); 203 int previousInstructionCount = dexInstructions.size(); 204 info.addInstructions(this, dexInstructions); 205 206 if (ir.isArgument()) { 207 int register = registerAllocator.getRegisterForValue(ir.outValue(), ir.getNumber()); 208 debugEventBuilder.startArgument(register, ir.getLocalInfo(), ir.outValue().isThis()); 209 } else if (ir.isDebugPosition()) { 210 int pc = lastMoveExceptionOffset >= 0 ? lastMoveExceptionOffset : instructionOffset; 211 debugEventBuilder.setPosition(pc, ir.asDebugPosition()); 212 } 213 lastMoveExceptionOffset = ir.isMoveException() ? instructionOffset : -1; 214 215 if (previousInstructionCount < dexInstructions.size()) { 216 while (previousInstructionCount < dexInstructions.size()) { 217 Instruction instruction = dexInstructions.get(previousInstructionCount++); 218 instruction.setOffset(instructionOffset); 219 instructionOffset += instruction.getSize(); 220 } 221 } 222 } 223 224 // Compute switch payloads. 225 for (SwitchPayloadInfo switchPayloadInfo : switchPayloadInfos) { 226 // Align payloads at even addresses. 227 if (offset % 2 != 0) { 228 Nop nop = new Nop(); 229 nop.setOffset(offset++); 230 dexInstructions.add(nop); 231 } 232 // Create payload and add it to the instruction stream. 233 Nop payload = createSwitchPayload(switchPayloadInfo, offset); 234 payload.setOffset(offset); 235 offset += payload.getSize(); 236 dexInstructions.add(payload); 237 } 238 239 // Compute fill array data payloads. 240 for (FillArrayDataInfo info : fillArrayDataInfos) { 241 // Align payloads at even addresses. 242 if (offset % 2 != 0) { 243 Nop nop = new Nop(); 244 nop.setOffset(offset++); 245 dexInstructions.add(nop); 246 } 247 // Create payload and add it to the instruction stream. 248 FillArrayDataPayload payload = info.ir.createPayload(); 249 payload.setOffset(offset); 250 info.dex.setPayloadOffset(offset - info.dex.getOffset()); 251 offset += payload.getSize(); 252 dexInstructions.add(payload); 253 } 254 255 // Construct try-catch info. 256 TryInfo tryInfo = computeTryInfo(); 257 258 // Return the dex code. 259 DexCode code = new DexCode( 260 registerAllocator.registersUsed(), 261 inRegisterCount, 262 outRegisterCount, 263 dexInstructions.toArray(new Instruction[dexInstructions.size()]), tryInfo.tries, 264 tryInfo.handlers, 265 debugEventBuilder.build(), 266 highestSortingReferencedString); 267 268 return code; 269 } 270 271 // Rewrite ifs with offsets that are too large for the if encoding. The rewriting transforms: 272 // 273 // 274 // BB0: if condition goto BB_FAR_AWAY 275 // BB1: ... 276 // 277 // to: 278 // 279 // BB0: if !condition goto BB1 280 // BB2: goto BB_FAR_AWAY 281 // BB1: ... 282 private void rewriteIfs() { 283 if (ifsNeedingRewrite.isEmpty()) { 284 return; 285 } 286 ListIterator<BasicBlock> it = ir.blocks.listIterator(); 287 while (it.hasNext()) { 288 BasicBlock block = it.next(); 289 if (ifsNeedingRewrite.contains(block)) { 290 If theIf = block.exit().asIf(); 291 BasicBlock trueTarget = theIf.getTrueTarget(); 292 BasicBlock newBlock = BasicBlock.createGotoBlock(trueTarget, ir.blocks.size()); 293 theIf.setTrueTarget(newBlock); 294 theIf.invert(); 295 it.add(newBlock); 296 } 297 } 298 } 299 300 private void needsIfRewriting(BasicBlock block) { 301 ifsNeedingRewrite.add(block); 302 } 303 304 public void registerStringReference(DexString string) { 305 if (highestSortingReferencedString == null 306 || string.slowCompareTo(highestSortingReferencedString) > 0) { 307 highestSortingReferencedString = string; 308 } 309 } 310 311 public void requestOutgoingRegisters(int requiredRegisterCount) { 312 if (requiredRegisterCount > outRegisterCount) { 313 outRegisterCount = requiredRegisterCount; 314 } 315 } 316 317 public int allocatedRegister(Value value, int instructionNumber) { 318 return registerAllocator.getRegisterForValue(value, instructionNumber); 319 } 320 321 public int allocatedRegisterForRangedArgument(Value value, int instructionNumber) { 322 return registerAllocator.getRegisterForRangedArgument(value, instructionNumber); 323 } 324 325 public boolean argumentValueUsesHighRegister(Value value, int instructionNumber) { 326 return registerAllocator.argumentValueUsesHighRegister(value, instructionNumber); 327 } 328 329 public void addGoto(com.android.tools.r8.ir.code.Goto jump) { 330 if (jump.getTarget() != nextBlock) { 331 add(jump, new GotoInfo(jump)); 332 } else { 333 addNop(jump); 334 } 335 } 336 337 public void addIf(If branch) { 338 assert nextBlock == branch.fallthroughBlock(); 339 add(branch, new IfInfo(branch)); 340 } 341 342 public void addMove(Move move) { 343 add(move, new MoveInfo(move)); 344 } 345 346 public void addNop(com.android.tools.r8.ir.code.Instruction instruction) { 347 add(instruction, new FallThroughInfo(instruction)); 348 } 349 350 public void add(com.android.tools.r8.ir.code.Instruction ir, Instruction dex) { 351 assert !ir.isGoto(); 352 add(ir, new FixedSizeInfo(ir, dex)); 353 } 354 355 public void add(com.android.tools.r8.ir.code.Instruction ir, Instruction[] dex) { 356 assert !ir.isGoto(); 357 add(ir, new MultiFixedSizeInfo(ir, dex)); 358 } 359 360 public void addSwitch(Switch s, Format31t dex) { 361 assert nextBlock == s.fallthroughBlock(); 362 switchPayloadInfos.add(new SwitchPayloadInfo(s, dex)); 363 add(s, dex); 364 } 365 366 public void addFillArrayData(NewArrayFilledData nafd, FillArrayData dex) { 367 fillArrayDataInfos.add(new FillArrayDataInfo(nafd, dex)); 368 add(nafd, dex); 369 } 370 371 public void addArgument(Argument argument) { 372 inRegisterCount += argument.outValue().requiredRegisters(); 373 add(argument, new FallThroughInfo(argument)); 374 } 375 376 private void add(com.android.tools.r8.ir.code.Instruction ir, Info info) { 377 assert ir != null; 378 assert info != null; 379 assert getInfo(ir) == null; 380 info.setMinOffset(minOffset); 381 info.setMaxOffset(maxOffset); 382 minOffset += info.minSize(); 383 maxOffset += info.maxSize(); 384 setInfo(ir, info); 385 } 386 387 private static int instructionNumberToIndex(int instructionNumber) { 388 return instructionNumber / LinearScanRegisterAllocator.INSTRUCTION_NUMBER_DELTA; 389 } 390 391 // Helper used by the info objects. 392 private Info getInfo(com.android.tools.r8.ir.code.Instruction instruction) { 393 return instructionToInfo[instructionNumberToIndex(instruction.getNumber())]; 394 } 395 396 private void setInfo(com.android.tools.r8.ir.code.Instruction instruction, Info info) { 397 instructionToInfo[instructionNumberToIndex(instruction.getNumber())] = info; 398 } 399 400 private Info getTargetInfo(BasicBlock block) { 401 InstructionIterator iterator = block.iterator(); 402 com.android.tools.r8.ir.code.Instruction instruction = null; 403 while (iterator.hasNext()) { 404 instruction = iterator.next(); 405 Info info = getInfo(instruction); 406 if (!(info instanceof FallThroughInfo)) { 407 return info; 408 } 409 } 410 assert instruction != null && instruction.isGoto(); 411 return getTargetInfo(instruction.asGoto().getTarget()); 412 } 413 414 // Helper for computing switch payloads. 415 private Nop createSwitchPayload(SwitchPayloadInfo info, int offset) { 416 Switch ir = info.ir; 417 // Patch the payload offset in the generated switch instruction now 418 // that the location is known. 419 info.dex.setPayloadOffset(offset - getInfo(ir).getOffset()); 420 // Compute target offset for each of the keys based on the offset of the 421 // first instruction in the block that the switch goes to for that key. 422 int[] targetBlockIndices = ir.targetBlockIndices(); 423 int[] targets = new int[targetBlockIndices.length]; 424 for (int i = 0; i < targetBlockIndices.length; i++) { 425 BasicBlock targetBlock = ir.targetBlock(i); 426 com.android.tools.r8.ir.code.Instruction targetInstruction = targetBlock.entry(); 427 targets[i] = getInfo(targetInstruction).getOffset() - getInfo(ir).getOffset(); 428 } 429 return ir.buildPayload(targets); 430 } 431 432 // Helpers for computing the try items and handlers. 433 434 private TryInfo computeTryInfo() { 435 // Canonical map of handlers. 436 BiMap<CatchHandlers<BasicBlock>, Integer> canonicalHandlers = HashBiMap.create(); 437 // Compute the list of try items and their handlers. 438 List<TryItem> tryItems = computeTryItems(canonicalHandlers); 439 // Compute handler sets before dex items which depend on the handler index. 440 Try[] tries = getDexTryItems(tryItems, canonicalHandlers); 441 TryHandler[] handlers = getDexTryHandlers(canonicalHandlers.inverse()); 442 return new TryInfo(tries, handlers); 443 } 444 445 private List<TryItem> computeTryItems( 446 BiMap<CatchHandlers<BasicBlock>, Integer> handlerToIndex) { 447 BiMap<Integer, CatchHandlers<BasicBlock>> indexToHandler = handlerToIndex.inverse(); 448 List<TryItem> tryItems = new ArrayList<>(); 449 List<BasicBlock> blocksWithHandlers = new ArrayList<>(); 450 TryItem currentTryItem = null; 451 // Create try items with maximal ranges to get as much coalescing as possible. After coalescing 452 // the try ranges are trimmed. 453 for (BasicBlock block : ir.blocks) { 454 CatchHandlers<BasicBlock> handlers = block.getCatchHandlers(); 455 // If this assert is hit, then the block contains no instruction that can throw. This is most 456 // likely due to dead-code elimination or other optimizations that might now work on a refined 457 // notion of what can throw. If so, the trivial blocks should either be removed or their catch 458 // handlers deleted to reflect the simpler graph prior to building the dex code. 459 assert handlers.isEmpty() || block.canThrow(); 460 if (!handlers.isEmpty()) { 461 if (handlerToIndex.containsKey(handlers)) { 462 handlers = indexToHandler.get(handlerToIndex.get(handlers)); 463 } else { 464 handlerToIndex.put(handlers, handlerToIndex.size()); 465 } 466 Info startInfo = getInfo(block.entry()); 467 Info endInfo = getInfo(block.exit()); 468 int start = startInfo.getOffset(); 469 int end = endInfo.getOffset() + endInfo.getSize(); 470 currentTryItem = new TryItem(handlers, start, end); 471 tryItems.add(currentTryItem); 472 blocksWithHandlers.add(block); 473 } else if (currentTryItem != null && !block.canThrow()) { 474 Info endInfo = getInfo(block.exit()); 475 // If the block only contains a goto there might not be an info for the exit instruction. 476 if (endInfo != null) { 477 currentTryItem.end = endInfo.getOffset() + endInfo.getSize(); 478 } 479 } else { 480 currentTryItem = null; 481 } 482 } 483 484 // If there are no try items it is trivially coalesced. 485 if (tryItems.isEmpty()) { 486 return tryItems; 487 } 488 489 // Coalesce try blocks. 490 tryItems.sort(TryItem::compareTo); 491 List<TryItem> coalescedTryItems = new ArrayList<>(tryItems.size()); 492 for (int i = 0; i < tryItems.size(); ) { 493 TryItem item = tryItems.get(i); 494 coalescedTryItems.add(item); 495 // Trim the range start for non-throwing instructions when starting a new range. 496 List<com.android.tools.r8.ir.code.Instruction> instructions = blocksWithHandlers.get(i).getInstructions(); 497 for (com.android.tools.r8.ir.code.Instruction insn : instructions) { 498 if (insn.instructionTypeCanThrow()) { 499 item.start = getInfo(insn).getOffset(); 500 break; 501 } 502 } 503 // Append all consecutive ranges that define the same handlers. 504 ++i; 505 while (i < tryItems.size()) { 506 TryItem next = tryItems.get(i); 507 if (item.end != next.start || !item.handlers.equals(next.handlers)) { 508 item.end = trimEnd(blocksWithHandlers.get(i - 1)); 509 break; 510 } 511 item.end = next.end; 512 ++i; 513 } 514 } 515 // Trim the last try range. 516 int lastIndex = tryItems.size() - 1; 517 TryItem lastItem = tryItems.get(lastIndex); 518 lastItem.end = trimEnd(blocksWithHandlers.get(lastIndex)); 519 return coalescedTryItems; 520 } 521 522 private int trimEnd(BasicBlock block) { 523 // Trim the range end for non-throwing instructions when end has been computed. 524 List<com.android.tools.r8.ir.code.Instruction> instructions = block.getInstructions(); 525 for (com.android.tools.r8.ir.code.Instruction insn : Lists.reverse(instructions)) { 526 if (insn.instructionTypeCanThrow()) { 527 Info info = getInfo(insn); 528 return info.getOffset() + info.getSize(); 529 } 530 } 531 throw new Unreachable("Expected to find a possibly throwing instruction"); 532 } 533 534 private static Try[] getDexTryItems(List<TryItem> tryItems, 535 Map<CatchHandlers<BasicBlock>, Integer> catchHandlers) { 536 Try[] tries = new Try[tryItems.size()]; 537 for (int i = 0; i < tries.length; ++i) { 538 TryItem item = tryItems.get(i); 539 Try dexTry = new Try(item.start, item.end - item.start, -1); 540 dexTry.handlerIndex = catchHandlers.get(item.handlers); 541 tries[i] = dexTry; 542 } 543 return tries; 544 } 545 546 private TryHandler[] getDexTryHandlers(Map<Integer, CatchHandlers<BasicBlock>> catchHandlers) { 547 TryHandler[] handlers = new TryHandler[catchHandlers.size()]; 548 for (int j = 0; j < catchHandlers.size(); j++) { 549 CatchHandlers<BasicBlock> handlerGroup = catchHandlers.get(j); 550 int catchAllOffset = TryHandler.NO_HANDLER; 551 List<TypeAddrPair> pairs = new ArrayList<>(); 552 for (int i = 0; i < handlerGroup.getGuards().size(); i++) { 553 DexType type = handlerGroup.getGuards().get(i); 554 BasicBlock target = handlerGroup.getAllTargets().get(i); 555 int targetOffset = getInfo(target.entry()).getOffset(); 556 if (type == DexItemFactory.catchAllType) { 557 assert i == handlerGroup.getGuards().size() - 1; 558 catchAllOffset = targetOffset; 559 } else { 560 pairs.add(new TypeAddrPair(type, targetOffset, -1)); 561 } 562 } 563 TypeAddrPair[] pairsArray = pairs.toArray(new TypeAddrPair[pairs.size()]); 564 handlers[j] = new TryHandler(pairsArray, catchAllOffset); 565 } 566 return handlers; 567 } 568 569 // Dex instruction wrapper with information to compute instruction sizes and offsets for jumps. 570 private static abstract class Info { 571 572 private final com.android.tools.r8.ir.code.Instruction ir; 573 // Concrete final offset of the instruction. 574 private int offset = -1; 575 // Lower and upper bound of the final offset. 576 private int minOffset = -1; 577 private int maxOffset = -1; 578 579 public Info(com.android.tools.r8.ir.code.Instruction ir) { 580 assert ir != null; 581 this.ir = ir; 582 } 583 584 // Computes the final size of the instruction. 585 // All instruction offsets up-to and including this instruction will be defined at this point. 586 public abstract int computeSize(DexBuilder builder); 587 588 // Materialize the actual construction. 589 // All instruction offsets are known at this point. 590 public abstract void addInstructions(DexBuilder builder, List<Instruction> instructions); 591 592 // Lower bound on the size of the instruction. 593 public abstract int minSize(); 594 595 // Upper bound on the size of the instruction. 596 public abstract int maxSize(); 597 598 public abstract int getSize(); 599 600 public int getOffset() { 601 assert offset >= 0 : this; 602 return offset; 603 } 604 605 public void setOffset(int offset) { 606 assert offset >= 0; 607 this.offset = offset; 608 } 609 610 public int getMinOffset() { 611 assert minOffset >= 0; 612 return minOffset; 613 } 614 615 public void setMinOffset(int minOffset) { 616 assert minOffset >= 0; 617 this.minOffset = minOffset; 618 } 619 620 public int getMaxOffset() { 621 assert maxOffset >= 0; 622 return maxOffset; 623 } 624 625 public void setMaxOffset(int maxOffset) { 626 assert maxOffset >= 0; 627 this.maxOffset = maxOffset; 628 } 629 630 public com.android.tools.r8.ir.code.Instruction getIR() { 631 return ir; 632 } 633 } 634 635 private static class FixedSizeInfo extends Info { 636 637 private Instruction instruction; 638 639 public FixedSizeInfo(com.android.tools.r8.ir.code.Instruction ir, Instruction instruction) { 640 super(ir); 641 this.instruction = instruction; 642 } 643 644 @Override 645 public int getSize() { 646 return instruction.getSize(); 647 } 648 649 @Override 650 public int minSize() { 651 return instruction.getSize(); 652 } 653 654 @Override 655 public int maxSize() { 656 return instruction.getSize(); 657 } 658 659 @Override 660 public int computeSize(DexBuilder builder) { 661 instruction.setOffset(getOffset()); // for better printing of the dex code. 662 return instruction.getSize(); 663 } 664 665 @Override 666 public void addInstructions(DexBuilder builder, List<Instruction> instructions) { 667 instructions.add(instruction); 668 } 669 } 670 671 private static class MultiFixedSizeInfo extends Info { 672 673 private Instruction[] instructions; 674 private final int size; 675 676 public MultiFixedSizeInfo(com.android.tools.r8.ir.code.Instruction ir, Instruction[] instructions) { 677 super(ir); 678 this.instructions = instructions; 679 int size = 0; 680 for (Instruction instruction : instructions) { 681 size += instruction.getSize(); 682 } 683 this.size = size; 684 } 685 686 @Override 687 public int computeSize(DexBuilder builder) { 688 return size; 689 } 690 691 @Override 692 public void addInstructions(DexBuilder builder, List<Instruction> instructions) { 693 int offset = getOffset(); 694 for (Instruction instruction : this.instructions) { 695 instructions.add(instruction); 696 instruction.setOffset(offset); 697 offset += instruction.getSize(); 698 } 699 } 700 701 @Override 702 public int minSize() { 703 return size; 704 } 705 706 @Override 707 public int maxSize() { 708 return size; 709 } 710 711 @Override 712 public int getSize() { 713 return size; 714 } 715 } 716 717 private static class FallThroughInfo extends Info { 718 719 public FallThroughInfo(com.android.tools.r8.ir.code.Instruction ir) { 720 super(ir); 721 } 722 723 @Override 724 public int getSize() { 725 return 0; 726 } 727 728 @Override 729 public int computeSize(DexBuilder builder) { 730 return 0; 731 } 732 733 @Override 734 public void addInstructions(DexBuilder builder, List<Instruction> instructions) { 735 } 736 737 @Override 738 public int minSize() { 739 return 0; 740 } 741 742 @Override 743 public int maxSize() { 744 return 0; 745 } 746 } 747 748 private static class GotoInfo extends Info { 749 750 private int size = -1; 751 752 public GotoInfo(com.android.tools.r8.ir.code.Goto jump) { 753 super(jump); 754 } 755 756 private com.android.tools.r8.ir.code.Goto getJump() { 757 return (com.android.tools.r8.ir.code.Goto) getIR(); 758 } 759 760 @Override 761 public int getSize() { 762 assert size > 0; 763 return size; 764 } 765 766 @Override 767 public int minSize() { 768 assert new Goto(42).getSize() == 1; 769 return 1; 770 } 771 772 @Override 773 public int maxSize() { 774 assert new Goto32(0).getSize() == 3; 775 return 3; 776 } 777 778 @Override 779 public int computeSize(DexBuilder builder) { 780 assert size < 0; 781 com.android.tools.r8.ir.code.Goto jump = getJump(); 782 Info targetInfo = builder.getTargetInfo(jump.getTarget()); 783 // Trivial loop will be emitted as: nop & goto -1 784 if (jump == targetInfo.getIR()) { 785 size = 2; 786 return size; 787 } 788 int maxOffset = getMaxOffset(); 789 int maxTargetOffset = targetInfo.getMaxOffset(); 790 int delta; 791 if (maxTargetOffset < maxOffset) { 792 // Backward branch: compute exact size (the target offset is set). 793 delta = getOffset() - targetInfo.getOffset(); 794 } else { 795 // Forward branch: over estimate the distance, but take into account the sizes 796 // of instructions generated so far. That way the over estimation is only for the 797 // instructions between this one and the target. 798 int maxOverEstimation = maxOffset - getOffset(); 799 delta = (maxTargetOffset - maxOverEstimation) - getOffset(); 800 } 801 if (delta <= Byte.MAX_VALUE) { 802 size = 1; 803 } else if (delta <= Short.MAX_VALUE) { 804 size = 2; 805 } else { 806 size = 3; 807 } 808 if (targetInfo.getIR().isReturn()) { 809 // Set the size to the min of the size of the return and the size of the goto. When 810 // adding instructions, we use the return if the computed size matches the size of the 811 // return. 812 size = Math.min(targetInfo.getSize(), size); 813 } 814 return size; 815 } 816 817 @Override 818 public void addInstructions(DexBuilder builder, List<Instruction> instructions) { 819 com.android.tools.r8.ir.code.Goto jump = getJump(); 820 int source = builder.getInfo(jump).getOffset(); 821 Info targetInfo = builder.getTargetInfo(jump.getTarget()); 822 int relativeOffset = targetInfo.getOffset() - source; 823 // We should never generate a goto to the following instruction or two consecutive returns. 824 // TODO(b/34726595): We might have a goto to the following instruction if we fail to DCE. 825 // assert relativeOffset != size; 826 Instruction dex; 827 // Emit a return if the target is a return and the size of the return is the computed 828 // size of this instruction. 829 if (targetInfo.getIR().isReturn() && size == targetInfo.getSize()) { 830 dex = targetInfo.getIR().asReturn().createDexInstruction(builder); 831 } else { 832 switch (size) { 833 case 1: 834 assert relativeOffset != 0; 835 dex = new Goto(relativeOffset); 836 break; 837 case 2: 838 if (relativeOffset == 0) { 839 Nop nop = new Nop(); 840 instructions.add(nop); 841 dex = new Goto(-nop.getSize()); 842 } else { 843 dex = new Goto16(relativeOffset); 844 } 845 break; 846 case 3: 847 dex = new Goto32(relativeOffset); 848 break; 849 default: 850 throw new Unreachable("Unexpected size for goto instruction: " + size); 851 } 852 } 853 dex.setOffset(getOffset()); // for better printing of the dex code. 854 instructions.add(dex); 855 } 856 } 857 858 public static class IfInfo extends Info { 859 860 private int size = -1; 861 862 public IfInfo(If branch) { 863 super(branch); 864 } 865 866 private If getBranch() { 867 return (If) getIR(); 868 } 869 870 private boolean branchesToSelf(DexBuilder builder) { 871 If branch = getBranch(); 872 Info trueTargetInfo = builder.getTargetInfo(branch.getTrueTarget()); 873 return branch == trueTargetInfo.getIR(); 874 } 875 876 private boolean offsetOutOfRange(DexBuilder builder) { 877 Info targetInfo = builder.getTargetInfo(getBranch().getTrueTarget()); 878 int maxOffset = getMaxOffset(); 879 int maxTargetOffset = targetInfo.getMaxOffset(); 880 if (maxTargetOffset < maxOffset) { 881 return getOffset() - targetInfo.getOffset() < Short.MIN_VALUE; 882 } 883 // Forward branch: over estimate the distance, but take into account the sizes 884 // of instructions generated so far. That way the over estimation is only for the 885 // instructions between this one and the target. 886 int maxOverEstimation = maxOffset - getOffset(); 887 return (maxTargetOffset - maxOverEstimation) - getOffset() > Short.MAX_VALUE; 888 } 889 890 @Override 891 public void addInstructions(DexBuilder builder, List<Instruction> instructions) { 892 If branch = getBranch(); 893 int source = builder.getInfo(branch).getOffset(); 894 int target = builder.getInfo(branch.getTrueTarget().entry()).getOffset(); 895 int relativeOffset = target - source; 896 int register1 = builder.allocatedRegister(branch.inValues().get(0), branch.getNumber()); 897 if (size == 3) { 898 assert branchesToSelf(builder); 899 Nop nop = new Nop(); 900 relativeOffset -= nop.getSize(); 901 instructions.add(nop); 902 } 903 assert relativeOffset != 0; 904 Instruction instruction = null; 905 if (branch.isZeroTest()) { 906 switch (getBranch().getType()) { 907 case EQ: 908 instruction = new IfEqz(register1, relativeOffset); 909 break; 910 case GE: 911 instruction = new IfGez(register1, relativeOffset); 912 break; 913 case GT: 914 instruction = new IfGtz(register1, relativeOffset); 915 break; 916 case LE: 917 instruction = new IfLez(register1, relativeOffset); 918 break; 919 case LT: 920 instruction = new IfLtz(register1, relativeOffset); 921 break; 922 case NE: 923 instruction = new IfNez(register1, relativeOffset); 924 break; 925 } 926 } else { 927 int register2 = builder.allocatedRegister(branch.inValues().get(1), branch.getNumber()); 928 switch (getBranch().getType()) { 929 case EQ: 930 instruction = new IfEq(register1, register2, relativeOffset); 931 break; 932 case GE: 933 instruction = new IfGe(register1, register2, relativeOffset); 934 break; 935 case GT: 936 instruction = new IfGt(register1, register2, relativeOffset); 937 break; 938 case LE: 939 instruction = new IfLe(register1, register2, relativeOffset); 940 break; 941 case LT: 942 instruction = new IfLt(register1, register2, relativeOffset); 943 break; 944 case NE: 945 instruction = new IfNe(register1, register2, relativeOffset); 946 break; 947 } 948 } 949 instruction.setOffset(getOffset()); 950 instructions.add(instruction); 951 } 952 953 @Override 954 public int computeSize(DexBuilder builder) { 955 if (offsetOutOfRange(builder)) { 956 builder.needsIfRewriting(getBranch().getBlock()); 957 } 958 size = branchesToSelf(builder) ? 3 : 2; 959 return size; 960 } 961 962 @Override 963 public int minSize() { 964 return 2; 965 } 966 967 @Override 968 public int maxSize() { 969 return 3; 970 } 971 972 @Override 973 public int getSize() { 974 return size; 975 } 976 } 977 978 public static class MoveInfo extends Info { 979 980 private int size = -1; 981 982 public MoveInfo(Move move) { 983 super(move); 984 } 985 986 private Move getMove() { 987 return (Move) getIR(); 988 } 989 990 @Override 991 public int computeSize(DexBuilder builder) { 992 Move move = getMove(); 993 int srcRegister = builder.allocatedRegister(move.src(), move.getNumber()); 994 int destRegister = builder.allocatedRegister(move.dest(), move.getNumber()); 995 if (srcRegister == destRegister) { 996 size = 1; 997 } else if (srcRegister <= Constants.U4BIT_MAX && destRegister <= Constants.U4BIT_MAX) { 998 size = 1; 999 } else if (destRegister <= Constants.U8BIT_MAX) { 1000 size = 2; 1001 } else { 1002 size = 3; 1003 } 1004 return size; 1005 } 1006 1007 @Override 1008 public void addInstructions(DexBuilder builder, List<Instruction> instructions) { 1009 Move move = getMove(); 1010 int dest = builder.allocatedRegister(move.dest(), move.getNumber()); 1011 int src = builder.allocatedRegister(move.src(), move.getNumber()); 1012 Instruction instruction = null; 1013 switch (size) { 1014 case 1: 1015 if (src == dest) { 1016 instruction = new Nop(); 1017 break; 1018 } 1019 switch (move.outType()) { 1020 case SINGLE: 1021 instruction = new com.android.tools.r8.code.Move(dest, src); 1022 break; 1023 case WIDE: 1024 instruction = new MoveWide(dest, src); 1025 break; 1026 case OBJECT: 1027 instruction = new MoveObject(dest, src); 1028 break; 1029 default: 1030 throw new Unreachable("Unexpected type: " + move.outType()); 1031 } 1032 break; 1033 case 2: 1034 switch (move.outType()) { 1035 case SINGLE: 1036 instruction = new MoveFrom16(dest, src); 1037 break; 1038 case WIDE: 1039 instruction = new MoveWideFrom16(dest, src); 1040 break; 1041 case OBJECT: 1042 instruction = new MoveObjectFrom16(dest, src); 1043 break; 1044 default: 1045 throw new Unreachable("Unexpected type: " + move.outType()); 1046 } 1047 break; 1048 case 3: 1049 switch (move.outType()) { 1050 case SINGLE: 1051 instruction = new Move16(dest, src); 1052 break; 1053 case WIDE: 1054 instruction = new MoveWide16(dest, src); 1055 break; 1056 case OBJECT: 1057 instruction = new MoveObject16(dest, src); 1058 break; 1059 default: 1060 throw new Unreachable("Unexpected type: " + move.outType()); 1061 } 1062 break; 1063 } 1064 instruction.setOffset(getOffset()); 1065 instructions.add(instruction); 1066 } 1067 1068 @Override 1069 public int minSize() { 1070 assert new Nop().getSize() == 1 && new com.android.tools.r8.code.Move(0, 0).getSize() == 1; 1071 return 1; 1072 } 1073 1074 @Override 1075 public int maxSize() { 1076 assert new Move16(0, 0).getSize() == 3; 1077 return 3; 1078 } 1079 1080 @Override 1081 public int getSize() { 1082 assert size > 0; 1083 return size; 1084 } 1085 } 1086 1087 // Return-type wrapper for try-related data. 1088 private static class TryInfo { 1089 1090 public final Try[] tries; 1091 public final TryHandler[] handlers; 1092 1093 public TryInfo(Try[] tries, TryHandler[] handlers) { 1094 this.tries = tries; 1095 this.handlers = handlers; 1096 } 1097 } 1098 1099 // Helper class for coalescing ranges for try blocks. 1100 private static class TryItem implements Comparable<TryItem> { 1101 1102 public final CatchHandlers<BasicBlock> handlers; 1103 public int start; 1104 public int end; 1105 1106 public TryItem(CatchHandlers<BasicBlock> handlers, int start, int end) { 1107 this.handlers = handlers; 1108 this.start = start; 1109 this.end = end; 1110 } 1111 1112 @Override 1113 public int compareTo(TryItem other) { 1114 return Integer.compare(start, other.start); 1115 } 1116 } 1117 1118 private static class SwitchPayloadInfo { 1119 1120 public final Switch ir; 1121 public final Format31t dex; 1122 1123 public SwitchPayloadInfo(Switch ir, Format31t dex) { 1124 this.ir = ir; 1125 this.dex = dex; 1126 } 1127 } 1128 1129 private static class FillArrayDataInfo { 1130 1131 public final NewArrayFilledData ir; 1132 public final FillArrayData dex; 1133 1134 public FillArrayDataInfo(NewArrayFilledData ir, FillArrayData dex) { 1135 this.ir = ir; 1136 this.dex = dex; 1137 } 1138 } 1139} 1140