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