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 package com.android.tools.r8.ir.conversion; 5 6 import com.android.tools.r8.code.FillArrayData; 7 import com.android.tools.r8.code.FillArrayDataPayload; 8 import com.android.tools.r8.code.Format31t; 9 import com.android.tools.r8.code.Goto; 10 import com.android.tools.r8.code.Goto16; 11 import com.android.tools.r8.code.Goto32; 12 import com.android.tools.r8.code.IfEq; 13 import com.android.tools.r8.code.IfEqz; 14 import com.android.tools.r8.code.IfGe; 15 import com.android.tools.r8.code.IfGez; 16 import com.android.tools.r8.code.IfGt; 17 import com.android.tools.r8.code.IfGtz; 18 import com.android.tools.r8.code.IfLe; 19 import com.android.tools.r8.code.IfLez; 20 import com.android.tools.r8.code.IfLt; 21 import com.android.tools.r8.code.IfLtz; 22 import com.android.tools.r8.code.IfNe; 23 import com.android.tools.r8.code.IfNez; 24 import com.android.tools.r8.code.Instruction; 25 import com.android.tools.r8.code.Move16; 26 import com.android.tools.r8.code.MoveFrom16; 27 import com.android.tools.r8.code.MoveObject; 28 import com.android.tools.r8.code.MoveObject16; 29 import com.android.tools.r8.code.MoveObjectFrom16; 30 import com.android.tools.r8.code.MoveWide; 31 import com.android.tools.r8.code.MoveWide16; 32 import com.android.tools.r8.code.MoveWideFrom16; 33 import com.android.tools.r8.code.Nop; 34 import com.android.tools.r8.dex.Constants; 35 import com.android.tools.r8.errors.Unreachable; 36 import com.android.tools.r8.graph.DexCode; 37 import com.android.tools.r8.graph.DexCode.Try; 38 import com.android.tools.r8.graph.DexCode.TryHandler; 39 import com.android.tools.r8.graph.DexCode.TryHandler.TypeAddrPair; 40 import com.android.tools.r8.graph.DexDebugEventBuilder; 41 import com.android.tools.r8.graph.DexItemFactory; 42 import com.android.tools.r8.graph.DexString; 43 import com.android.tools.r8.graph.DexType; 44 import com.android.tools.r8.ir.code.Argument; 45 import com.android.tools.r8.ir.code.BasicBlock; 46 import com.android.tools.r8.ir.code.CatchHandlers; 47 import com.android.tools.r8.ir.code.DebugPosition; 48 import com.android.tools.r8.ir.code.IRCode; 49 import com.android.tools.r8.ir.code.If; 50 import com.android.tools.r8.ir.code.InstructionIterator; 51 import com.android.tools.r8.ir.code.Move; 52 import com.android.tools.r8.ir.code.NewArrayFilledData; 53 import com.android.tools.r8.ir.code.Switch; 54 import com.android.tools.r8.ir.code.Value; 55 import com.android.tools.r8.ir.regalloc.LinearScanRegisterAllocator; 56 import com.android.tools.r8.ir.regalloc.RegisterAllocator; 57 import com.google.common.collect.BiMap; 58 import com.google.common.collect.HashBiMap; 59 import com.google.common.collect.Lists; 60 import com.google.common.collect.Sets; 61 import java.util.ArrayList; 62 import java.util.Iterator; 63 import java.util.List; 64 import java.util.ListIterator; 65 import java.util.Map; 66 import java.util.Set; 67 68 /** 69 * Builder object for constructing dex bytecode from the high-level IR. 70 */ 71 public 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 DexBuilder(IRCode ir, RegisterAllocator registerAllocator, DexItemFactory dexItemFactory)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 DexBuilder(IRCode ir, RegisterAllocator registerAllocator, DexItemFactory dexItemFactory, DexString firstJumboString)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 reset()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 isJumboString(DexString string)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 */ build(int numberOfArguments)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: ... rewriteIfs()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 needsIfRewriting(BasicBlock block)291 private void needsIfRewriting(BasicBlock block) { 292 ifsNeedingRewrite.add(block); 293 } 294 registerStringReference(DexString string)295 public void registerStringReference(DexString string) { 296 if (highestSortingReferencedString == null 297 || string.slowCompareTo(highestSortingReferencedString) > 0) { 298 highestSortingReferencedString = string; 299 } 300 } 301 requestOutgoingRegisters(int requiredRegisterCount)302 public void requestOutgoingRegisters(int requiredRegisterCount) { 303 if (requiredRegisterCount > outRegisterCount) { 304 outRegisterCount = requiredRegisterCount; 305 } 306 } 307 allocatedRegister(Value value, int instructionNumber)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. argumentOrAllocateRegister(Value value, int instructionNumber)314 public int argumentOrAllocateRegister(Value value, int instructionNumber) { 315 return registerAllocator.getArgumentOrAllocateRegisterForValue(value, instructionNumber); 316 } 317 argumentValueUsesHighRegister(Value value, int instructionNumber)318 public boolean argumentValueUsesHighRegister(Value value, int instructionNumber) { 319 return registerAllocator.argumentValueUsesHighRegister(value, instructionNumber); 320 } 321 addGoto(com.android.tools.r8.ir.code.Goto jump)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 addIf(If branch)330 public void addIf(If branch) { 331 assert nextBlock == branch.fallthroughBlock(); 332 add(branch, new IfInfo(branch)); 333 } 334 addMove(Move move)335 public void addMove(Move move) { 336 add(move, new MoveInfo(move)); 337 } 338 addNop(com.android.tools.r8.ir.code.Instruction instruction)339 public void addNop(com.android.tools.r8.ir.code.Instruction instruction) { 340 add(instruction, new FallThroughInfo(instruction)); 341 } 342 isNopInstruction(com.android.tools.r8.ir.code.Instruction instruction)343 private boolean isNopInstruction(com.android.tools.r8.ir.code.Instruction instruction) { 344 return instruction.isDebugLocalsChange() 345 || (instruction.isConstNumber() && !instruction.outValue().needsRegister()); 346 } 347 addDebugPosition(DebugPosition position)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 = block.listIterator(position); 352 353 com.android.tools.r8.ir.code.Instruction next = null; 354 while (next == null) { 355 next = iterator.next(); 356 while (isNopInstruction(next)) { 357 next = iterator.next(); 358 } 359 if (next.isGoto()) { 360 ++blockIndex; 361 BasicBlock nextBlock = blockIndex < ir.blocks.size() ? ir.blocks.get(blockIndex) : null; 362 if (next.asGoto().getTarget() == nextBlock) { 363 iterator = nextBlock.iterator(); 364 next = null; 365 } 366 } 367 } 368 if (next.isDebugPosition()) { 369 add(position, new FixedSizeInfo(position, new Nop())); 370 } else { 371 addNop(position); 372 } 373 } 374 375 public void add(com.android.tools.r8.ir.code.Instruction ir, Instruction dex) { 376 assert !ir.isGoto(); 377 add(ir, new FixedSizeInfo(ir, dex)); 378 } 379 380 public void add(com.android.tools.r8.ir.code.Instruction ir, Instruction[] dex) { 381 assert !ir.isGoto(); 382 add(ir, new MultiFixedSizeInfo(ir, dex)); 383 } 384 385 public void addSwitch(Switch s, Format31t dex) { 386 assert nextBlock == s.fallthroughBlock(); 387 switchPayloadInfos.add(new SwitchPayloadInfo(s, dex)); 388 add(s, dex); 389 } 390 391 public void addFillArrayData(NewArrayFilledData nafd, FillArrayData dex) { 392 fillArrayDataInfos.add(new FillArrayDataInfo(nafd, dex)); 393 add(nafd, dex); 394 } 395 396 public void addArgument(Argument argument) { 397 inRegisterCount += argument.outValue().requiredRegisters(); 398 add(argument, new FallThroughInfo(argument)); 399 } 400 401 private void add(com.android.tools.r8.ir.code.Instruction ir, Info info) { 402 assert ir != null; 403 assert info != null; 404 assert getInfo(ir) == null; 405 info.setMinOffset(minOffset); 406 info.setMaxOffset(maxOffset); 407 minOffset += info.minSize(); 408 maxOffset += info.maxSize(); 409 setInfo(ir, info); 410 } 411 412 private static int instructionNumberToIndex(int instructionNumber) { 413 return instructionNumber / LinearScanRegisterAllocator.INSTRUCTION_NUMBER_DELTA; 414 } 415 416 // Helper used by the info objects. 417 private Info getInfo(com.android.tools.r8.ir.code.Instruction instruction) { 418 return instructionToInfo[instructionNumberToIndex(instruction.getNumber())]; 419 } 420 421 private void setInfo(com.android.tools.r8.ir.code.Instruction instruction, Info info) { 422 instructionToInfo[instructionNumberToIndex(instruction.getNumber())] = info; 423 } 424 425 private Info getTargetInfo(BasicBlock block) { 426 InstructionIterator iterator = block.iterator(); 427 com.android.tools.r8.ir.code.Instruction instruction = null; 428 while (iterator.hasNext()) { 429 instruction = iterator.next(); 430 Info info = getInfo(instruction); 431 if (!(info instanceof FallThroughInfo)) { 432 return info; 433 } 434 } 435 assert instruction != null && instruction.isGoto(); 436 return getTargetInfo(instruction.asGoto().getTarget()); 437 } 438 439 // Helper for computing switch payloads. 440 private Nop createSwitchPayload(SwitchPayloadInfo info, int offset) { 441 Switch ir = info.ir; 442 // Patch the payload offset in the generated switch instruction now 443 // that the location is known. 444 info.dex.setPayloadOffset(offset - getInfo(ir).getOffset()); 445 // Compute target offset for each of the keys based on the offset of the 446 // first instruction in the block that the switch goes to for that key. 447 int[] targetBlockIndices = ir.targetBlockIndices(); 448 int[] targets = new int[targetBlockIndices.length]; 449 for (int i = 0; i < targetBlockIndices.length; i++) { 450 BasicBlock targetBlock = ir.targetBlock(i); 451 com.android.tools.r8.ir.code.Instruction targetInstruction = targetBlock.entry(); 452 targets[i] = getInfo(targetInstruction).getOffset() - getInfo(ir).getOffset(); 453 } 454 BasicBlock fallthroughBlock = ir.fallthroughBlock(); 455 com.android.tools.r8.ir.code.Instruction fallthroughTargetInstruction = 456 fallthroughBlock.entry(); 457 int fallthroughTarget = 458 getInfo(fallthroughTargetInstruction).getOffset() - getInfo(ir).getOffset(); 459 460 return ir.buildPayload(targets, fallthroughTarget); 461 } 462 463 // Helpers for computing the try items and handlers. 464 465 private TryInfo computeTryInfo() { 466 // Canonical map of handlers. 467 BiMap<CatchHandlers<BasicBlock>, Integer> canonicalHandlers = HashBiMap.create(); 468 // Compute the list of try items and their handlers. 469 List<TryItem> tryItems = computeTryItems(canonicalHandlers); 470 // Compute handler sets before dex items which depend on the handler index. 471 Try[] tries = getDexTryItems(tryItems, canonicalHandlers); 472 TryHandler[] handlers = getDexTryHandlers(canonicalHandlers.inverse()); 473 return new TryInfo(tries, handlers); 474 } 475 476 private List<TryItem> computeTryItems( 477 BiMap<CatchHandlers<BasicBlock>, Integer> handlerToIndex) { 478 BiMap<Integer, CatchHandlers<BasicBlock>> indexToHandler = handlerToIndex.inverse(); 479 List<TryItem> tryItems = new ArrayList<>(); 480 List<BasicBlock> blocksWithHandlers = new ArrayList<>(); 481 TryItem currentTryItem = null; 482 // Create try items with maximal ranges to get as much coalescing as possible. After coalescing 483 // the try ranges are trimmed. 484 for (BasicBlock block : ir.blocks) { 485 CatchHandlers<BasicBlock> handlers = block.getCatchHandlers(); 486 // If this assert is hit, then the block contains no instruction that can throw. This is most 487 // likely due to dead-code elimination or other optimizations that might now work on a refined 488 // notion of what can throw. If so, the trivial blocks should either be removed or their catch 489 // handlers deleted to reflect the simpler graph prior to building the dex code. 490 assert handlers.isEmpty() || block.canThrow(); 491 if (!handlers.isEmpty()) { 492 if (handlerToIndex.containsKey(handlers)) { 493 handlers = indexToHandler.get(handlerToIndex.get(handlers)); 494 } else { 495 handlerToIndex.put(handlers, handlerToIndex.size()); 496 } 497 Info startInfo = getInfo(block.entry()); 498 Info endInfo = getInfo(block.exit()); 499 int start = startInfo.getOffset(); 500 int end = endInfo.getOffset() + endInfo.getSize(); 501 currentTryItem = new TryItem(handlers, start, end); 502 tryItems.add(currentTryItem); 503 blocksWithHandlers.add(block); 504 } else if (currentTryItem != null && !block.canThrow()) { 505 Info endInfo = getInfo(block.exit()); 506 // If the block only contains a goto there might not be an info for the exit instruction. 507 if (endInfo != null) { 508 currentTryItem.end = endInfo.getOffset() + endInfo.getSize(); 509 } 510 } else { 511 currentTryItem = null; 512 } 513 } 514 515 // If there are no try items it is trivially coalesced. 516 if (tryItems.isEmpty()) { 517 return tryItems; 518 } 519 520 // Coalesce try blocks. 521 tryItems.sort(TryItem::compareTo); 522 List<TryItem> coalescedTryItems = new ArrayList<>(tryItems.size()); 523 for (int i = 0; i < tryItems.size(); ) { 524 TryItem item = tryItems.get(i); 525 coalescedTryItems.add(item); 526 // Trim the range start for non-throwing instructions when starting a new range. 527 List<com.android.tools.r8.ir.code.Instruction> instructions = blocksWithHandlers.get(i).getInstructions(); 528 for (com.android.tools.r8.ir.code.Instruction insn : instructions) { 529 if (insn.instructionTypeCanThrow()) { 530 item.start = getInfo(insn).getOffset(); 531 break; 532 } 533 } 534 // Append all consecutive ranges that define the same handlers. 535 ++i; 536 while (i < tryItems.size()) { 537 TryItem next = tryItems.get(i); 538 if (item.end != next.start || !item.handlers.equals(next.handlers)) { 539 item.end = trimEnd(blocksWithHandlers.get(i - 1)); 540 break; 541 } 542 item.end = next.end; 543 ++i; 544 } 545 } 546 // Trim the last try range. 547 int lastIndex = tryItems.size() - 1; 548 TryItem lastItem = tryItems.get(lastIndex); 549 lastItem.end = trimEnd(blocksWithHandlers.get(lastIndex)); 550 return coalescedTryItems; 551 } 552 553 private int trimEnd(BasicBlock block) { 554 // Trim the range end for non-throwing instructions when end has been computed. 555 List<com.android.tools.r8.ir.code.Instruction> instructions = block.getInstructions(); 556 for (com.android.tools.r8.ir.code.Instruction insn : Lists.reverse(instructions)) { 557 if (insn.instructionTypeCanThrow()) { 558 Info info = getInfo(insn); 559 return info.getOffset() + info.getSize(); 560 } 561 } 562 throw new Unreachable("Expected to find a possibly throwing instruction"); 563 } 564 565 private static Try[] getDexTryItems(List<TryItem> tryItems, 566 Map<CatchHandlers<BasicBlock>, Integer> catchHandlers) { 567 Try[] tries = new Try[tryItems.size()]; 568 for (int i = 0; i < tries.length; ++i) { 569 TryItem item = tryItems.get(i); 570 Try dexTry = new Try(item.start, item.end - item.start, -1); 571 dexTry.handlerIndex = catchHandlers.get(item.handlers); 572 tries[i] = dexTry; 573 } 574 return tries; 575 } 576 577 private TryHandler[] getDexTryHandlers(Map<Integer, CatchHandlers<BasicBlock>> catchHandlers) { 578 TryHandler[] handlers = new TryHandler[catchHandlers.size()]; 579 for (int j = 0; j < catchHandlers.size(); j++) { 580 CatchHandlers<BasicBlock> handlerGroup = catchHandlers.get(j); 581 int catchAllOffset = TryHandler.NO_HANDLER; 582 List<TypeAddrPair> pairs = new ArrayList<>(); 583 for (int i = 0; i < handlerGroup.getGuards().size(); i++) { 584 DexType type = handlerGroup.getGuards().get(i); 585 BasicBlock target = handlerGroup.getAllTargets().get(i); 586 int targetOffset = getInfo(target.entry()).getOffset(); 587 if (type == DexItemFactory.catchAllType) { 588 assert i == handlerGroup.getGuards().size() - 1; 589 catchAllOffset = targetOffset; 590 } else { 591 pairs.add(new TypeAddrPair(type, targetOffset, -1)); 592 } 593 } 594 TypeAddrPair[] pairsArray = pairs.toArray(new TypeAddrPair[pairs.size()]); 595 handlers[j] = new TryHandler(pairsArray, catchAllOffset); 596 } 597 return handlers; 598 } 599 600 // Dex instruction wrapper with information to compute instruction sizes and offsets for jumps. 601 private static abstract class Info { 602 603 private final com.android.tools.r8.ir.code.Instruction ir; 604 // Concrete final offset of the instruction. 605 private int offset = -1; 606 // Lower and upper bound of the final offset. 607 private int minOffset = -1; 608 private int maxOffset = -1; 609 610 public Info(com.android.tools.r8.ir.code.Instruction ir) { 611 assert ir != null; 612 this.ir = ir; 613 } 614 615 // Computes the final size of the instruction. 616 // All instruction offsets up-to and including this instruction will be defined at this point. 617 public abstract int computeSize(DexBuilder builder); 618 619 // Materialize the actual construction. 620 // All instruction offsets are known at this point. 621 public abstract void addInstructions(DexBuilder builder, List<Instruction> instructions); 622 623 // Lower bound on the size of the instruction. 624 public abstract int minSize(); 625 626 // Upper bound on the size of the instruction. 627 public abstract int maxSize(); 628 629 public abstract int getSize(); 630 631 public int getOffset() { 632 assert offset >= 0 : this; 633 return offset; 634 } 635 636 public void setOffset(int offset) { 637 assert offset >= 0; 638 this.offset = offset; 639 } 640 641 public int getMinOffset() { 642 assert minOffset >= 0; 643 return minOffset; 644 } 645 646 public void setMinOffset(int minOffset) { 647 assert minOffset >= 0; 648 this.minOffset = minOffset; 649 } 650 651 public int getMaxOffset() { 652 assert maxOffset >= 0; 653 return maxOffset; 654 } 655 656 public void setMaxOffset(int maxOffset) { 657 assert maxOffset >= 0; 658 this.maxOffset = maxOffset; 659 } 660 661 public com.android.tools.r8.ir.code.Instruction getIR() { 662 return ir; 663 } 664 } 665 666 private static class FixedSizeInfo extends Info { 667 668 private Instruction instruction; 669 670 public FixedSizeInfo(com.android.tools.r8.ir.code.Instruction ir, Instruction instruction) { 671 super(ir); 672 this.instruction = instruction; 673 } 674 675 @Override 676 public int getSize() { 677 return instruction.getSize(); 678 } 679 680 @Override 681 public int minSize() { 682 return instruction.getSize(); 683 } 684 685 @Override 686 public int maxSize() { 687 return instruction.getSize(); 688 } 689 690 @Override 691 public int computeSize(DexBuilder builder) { 692 instruction.setOffset(getOffset()); // for better printing of the dex code. 693 return instruction.getSize(); 694 } 695 696 @Override 697 public void addInstructions(DexBuilder builder, List<Instruction> instructions) { 698 instructions.add(instruction); 699 } 700 } 701 702 private static class MultiFixedSizeInfo extends Info { 703 704 private Instruction[] instructions; 705 private final int size; 706 707 public MultiFixedSizeInfo(com.android.tools.r8.ir.code.Instruction ir, Instruction[] instructions) { 708 super(ir); 709 this.instructions = instructions; 710 int size = 0; 711 for (Instruction instruction : instructions) { 712 size += instruction.getSize(); 713 } 714 this.size = size; 715 } 716 717 @Override 718 public int computeSize(DexBuilder builder) { 719 return size; 720 } 721 722 @Override 723 public void addInstructions(DexBuilder builder, List<Instruction> instructions) { 724 int offset = getOffset(); 725 for (Instruction instruction : this.instructions) { 726 instructions.add(instruction); 727 instruction.setOffset(offset); 728 offset += instruction.getSize(); 729 } 730 } 731 732 @Override 733 public int minSize() { 734 return size; 735 } 736 737 @Override 738 public int maxSize() { 739 return size; 740 } 741 742 @Override 743 public int getSize() { 744 return size; 745 } 746 } 747 748 private static class FallThroughInfo extends Info { 749 750 public FallThroughInfo(com.android.tools.r8.ir.code.Instruction ir) { 751 super(ir); 752 } 753 754 @Override 755 public int getSize() { 756 return 0; 757 } 758 759 @Override 760 public int computeSize(DexBuilder builder) { 761 return 0; 762 } 763 764 @Override 765 public void addInstructions(DexBuilder builder, List<Instruction> instructions) { 766 } 767 768 @Override 769 public int minSize() { 770 return 0; 771 } 772 773 @Override 774 public int maxSize() { 775 return 0; 776 } 777 } 778 779 private static class GotoInfo extends Info { 780 781 private int size = -1; 782 783 public GotoInfo(com.android.tools.r8.ir.code.Goto jump) { 784 super(jump); 785 } 786 787 private com.android.tools.r8.ir.code.Goto getJump() { 788 return (com.android.tools.r8.ir.code.Goto) getIR(); 789 } 790 791 @Override 792 public int getSize() { 793 assert size > 0; 794 return size; 795 } 796 797 @Override minSize()798 public int minSize() { 799 assert new Goto(42).getSize() == 1; 800 return 1; 801 } 802 803 @Override maxSize()804 public int maxSize() { 805 assert new Goto32(0).getSize() == 3; 806 return 3; 807 } 808 809 @Override computeSize(DexBuilder builder)810 public int computeSize(DexBuilder builder) { 811 assert size < 0; 812 com.android.tools.r8.ir.code.Goto jump = getJump(); 813 Info targetInfo = builder.getTargetInfo(jump.getTarget()); 814 // Trivial loop will be emitted as: nop & goto -1 815 if (jump == targetInfo.getIR()) { 816 size = 2; 817 return size; 818 } 819 int maxOffset = getMaxOffset(); 820 int maxTargetOffset = targetInfo.getMaxOffset(); 821 int delta; 822 if (maxTargetOffset < maxOffset) { 823 // Backward branch: compute exact size (the target offset is set). 824 delta = getOffset() - targetInfo.getOffset(); 825 } else { 826 // Forward branch: over estimate the distance, but take into account the sizes 827 // of instructions generated so far. That way the over estimation is only for the 828 // instructions between this one and the target. 829 int maxOverEstimation = maxOffset - getOffset(); 830 delta = (maxTargetOffset - maxOverEstimation) - getOffset(); 831 } 832 if (delta <= Byte.MAX_VALUE) { 833 size = 1; 834 } else if (delta <= Short.MAX_VALUE) { 835 size = 2; 836 } else { 837 size = 3; 838 } 839 if (targetInfo.getIR().isReturn()) { 840 // Set the size to the min of the size of the return and the size of the goto. When 841 // adding instructions, we use the return if the computed size matches the size of the 842 // return. 843 size = Math.min(targetInfo.getSize(), size); 844 } 845 return size; 846 } 847 848 @Override 849 public void addInstructions(DexBuilder builder, List<Instruction> instructions) { 850 com.android.tools.r8.ir.code.Goto jump = getJump(); 851 int source = builder.getInfo(jump).getOffset(); 852 Info targetInfo = builder.getTargetInfo(jump.getTarget()); 853 int relativeOffset = targetInfo.getOffset() - source; 854 // We should never generate a goto to the following instruction or two consecutive returns. 855 // TODO(b/34726595): We might have a goto to the following instruction if we fail to DCE. 856 // assert relativeOffset != size; 857 Instruction dex; 858 // Emit a return if the target is a return and the size of the return is the computed 859 // size of this instruction. 860 if (targetInfo.getIR().isReturn() && size == targetInfo.getSize()) { 861 dex = targetInfo.getIR().asReturn().createDexInstruction(builder); 862 } else { 863 switch (size) { 864 case 1: 865 assert relativeOffset != 0; 866 dex = new Goto(relativeOffset); 867 break; 868 case 2: 869 if (relativeOffset == 0) { 870 Nop nop = new Nop(); 871 instructions.add(nop); 872 dex = new Goto(-nop.getSize()); 873 } else { 874 dex = new Goto16(relativeOffset); 875 } 876 break; 877 case 3: 878 dex = new Goto32(relativeOffset); 879 break; 880 default: 881 throw new Unreachable("Unexpected size for goto instruction: " + size); 882 } 883 } 884 dex.setOffset(getOffset()); // for better printing of the dex code. 885 instructions.add(dex); 886 } 887 } 888 889 public static class IfInfo extends Info { 890 891 private int size = -1; 892 893 public IfInfo(If branch) { 894 super(branch); 895 } 896 897 private If getBranch() { 898 return (If) getIR(); 899 } 900 901 private boolean branchesToSelf(DexBuilder builder) { 902 If branch = getBranch(); 903 Info trueTargetInfo = builder.getTargetInfo(branch.getTrueTarget()); 904 return branch == trueTargetInfo.getIR(); 905 } 906 907 private boolean offsetOutOfRange(DexBuilder builder) { 908 Info targetInfo = builder.getTargetInfo(getBranch().getTrueTarget()); 909 int maxOffset = getMaxOffset(); 910 int maxTargetOffset = targetInfo.getMaxOffset(); 911 if (maxTargetOffset < maxOffset) { 912 return getOffset() - targetInfo.getOffset() < Short.MIN_VALUE; 913 } 914 // Forward branch: over estimate the distance, but take into account the sizes 915 // of instructions generated so far. That way the over estimation is only for the 916 // instructions between this one and the target. 917 int maxOverEstimation = maxOffset - getOffset(); 918 return (maxTargetOffset - maxOverEstimation) - getOffset() > Short.MAX_VALUE; 919 } 920 921 @Override 922 public void addInstructions(DexBuilder builder, List<Instruction> instructions) { 923 If branch = getBranch(); 924 int source = builder.getInfo(branch).getOffset(); 925 int target = builder.getInfo(branch.getTrueTarget().entry()).getOffset(); 926 int relativeOffset = target - source; 927 int register1 = builder.allocatedRegister(branch.inValues().get(0), branch.getNumber()); 928 if (size == 3) { 929 assert branchesToSelf(builder); 930 Nop nop = new Nop(); 931 relativeOffset -= nop.getSize(); 932 instructions.add(nop); 933 } 934 assert relativeOffset != 0; 935 Instruction instruction = null; 936 if (branch.isZeroTest()) { 937 switch (getBranch().getType()) { 938 case EQ: 939 instruction = new IfEqz(register1, relativeOffset); 940 break; 941 case GE: 942 instruction = new IfGez(register1, relativeOffset); 943 break; 944 case GT: 945 instruction = new IfGtz(register1, relativeOffset); 946 break; 947 case LE: 948 instruction = new IfLez(register1, relativeOffset); 949 break; 950 case LT: 951 instruction = new IfLtz(register1, relativeOffset); 952 break; 953 case NE: 954 instruction = new IfNez(register1, relativeOffset); 955 break; 956 } 957 } else { 958 int register2 = builder.allocatedRegister(branch.inValues().get(1), branch.getNumber()); 959 switch (getBranch().getType()) { 960 case EQ: 961 instruction = new IfEq(register1, register2, relativeOffset); 962 break; 963 case GE: 964 instruction = new IfGe(register1, register2, relativeOffset); 965 break; 966 case GT: 967 instruction = new IfGt(register1, register2, relativeOffset); 968 break; 969 case LE: 970 instruction = new IfLe(register1, register2, relativeOffset); 971 break; 972 case LT: 973 instruction = new IfLt(register1, register2, relativeOffset); 974 break; 975 case NE: 976 instruction = new IfNe(register1, register2, relativeOffset); 977 break; 978 } 979 } 980 instruction.setOffset(getOffset()); 981 instructions.add(instruction); 982 } 983 984 @Override 985 public int computeSize(DexBuilder builder) { 986 if (offsetOutOfRange(builder)) { 987 builder.needsIfRewriting(getBranch().getBlock()); 988 } 989 size = branchesToSelf(builder) ? 3 : 2; 990 return size; 991 } 992 993 @Override 994 public int minSize() { 995 return 2; 996 } 997 998 @Override 999 public int maxSize() { 1000 return 3; 1001 } 1002 1003 @Override 1004 public int getSize() { 1005 return size; 1006 } 1007 } 1008 1009 public static class MoveInfo extends Info { 1010 1011 private int size = -1; 1012 1013 public MoveInfo(Move move) { 1014 super(move); 1015 } 1016 1017 private Move getMove() { 1018 return (Move) getIR(); 1019 } 1020 1021 @Override 1022 public int computeSize(DexBuilder builder) { 1023 Move move = getMove(); 1024 int srcRegister = builder.allocatedRegister(move.src(), move.getNumber()); 1025 int destRegister = builder.allocatedRegister(move.dest(), move.getNumber()); 1026 if (srcRegister == destRegister) { 1027 size = 1; 1028 } else if (srcRegister <= Constants.U4BIT_MAX && destRegister <= Constants.U4BIT_MAX) { 1029 size = 1; 1030 } else if (destRegister <= Constants.U8BIT_MAX) { 1031 size = 2; 1032 } else { 1033 size = 3; 1034 } 1035 return size; 1036 } 1037 1038 @Override 1039 public void addInstructions(DexBuilder builder, List<Instruction> instructions) { 1040 Move move = getMove(); 1041 int dest = builder.allocatedRegister(move.dest(), move.getNumber()); 1042 int src = builder.allocatedRegister(move.src(), move.getNumber()); 1043 Instruction instruction = null; 1044 switch (size) { 1045 case 1: 1046 if (src == dest) { 1047 instruction = new Nop(); 1048 break; 1049 } 1050 switch (move.outType()) { 1051 case SINGLE: 1052 instruction = new com.android.tools.r8.code.Move(dest, src); 1053 break; 1054 case WIDE: 1055 instruction = new MoveWide(dest, src); 1056 break; 1057 case OBJECT: 1058 instruction = new MoveObject(dest, src); 1059 break; 1060 default: 1061 throw new Unreachable("Unexpected type: " + move.outType()); 1062 } 1063 break; 1064 case 2: 1065 switch (move.outType()) { 1066 case SINGLE: 1067 instruction = new MoveFrom16(dest, src); 1068 break; 1069 case WIDE: 1070 instruction = new MoveWideFrom16(dest, src); 1071 break; 1072 case OBJECT: 1073 instruction = new MoveObjectFrom16(dest, src); 1074 break; 1075 default: 1076 throw new Unreachable("Unexpected type: " + move.outType()); 1077 } 1078 break; 1079 case 3: 1080 switch (move.outType()) { 1081 case SINGLE: 1082 instruction = new Move16(dest, src); 1083 break; 1084 case WIDE: 1085 instruction = new MoveWide16(dest, src); 1086 break; 1087 case OBJECT: 1088 instruction = new MoveObject16(dest, src); 1089 break; 1090 default: 1091 throw new Unreachable("Unexpected type: " + move.outType()); 1092 } 1093 break; 1094 } 1095 instruction.setOffset(getOffset()); 1096 instructions.add(instruction); 1097 } 1098 1099 @Override 1100 public int minSize() { 1101 assert new Nop().getSize() == 1 && new com.android.tools.r8.code.Move(0, 0).getSize() == 1; 1102 return 1; 1103 } 1104 1105 @Override 1106 public int maxSize() { 1107 assert new Move16(0, 0).getSize() == 3; 1108 return 3; 1109 } 1110 1111 @Override 1112 public int getSize() { 1113 assert size > 0; 1114 return size; 1115 } 1116 } 1117 1118 // Return-type wrapper for try-related data. 1119 private static class TryInfo { 1120 1121 public final Try[] tries; 1122 public final TryHandler[] handlers; 1123 1124 public TryInfo(Try[] tries, TryHandler[] handlers) { 1125 this.tries = tries; 1126 this.handlers = handlers; 1127 } 1128 } 1129 1130 // Helper class for coalescing ranges for try blocks. 1131 private static class TryItem implements Comparable<TryItem> { 1132 1133 public final CatchHandlers<BasicBlock> handlers; 1134 public int start; 1135 public int end; 1136 1137 public TryItem(CatchHandlers<BasicBlock> handlers, int start, int end) { 1138 this.handlers = handlers; 1139 this.start = start; 1140 this.end = end; 1141 } 1142 1143 @Override 1144 public int compareTo(TryItem other) { 1145 return Integer.compare(start, other.start); 1146 } 1147 } 1148 1149 private static class SwitchPayloadInfo { 1150 1151 public final Switch ir; 1152 public final Format31t dex; 1153 1154 public SwitchPayloadInfo(Switch ir, Format31t dex) { 1155 this.ir = ir; 1156 this.dex = dex; 1157 } 1158 } 1159 1160 private static class FillArrayDataInfo { 1161 1162 public final NewArrayFilledData ir; 1163 public final FillArrayData dex; 1164 1165 public FillArrayDataInfo(NewArrayFilledData ir, FillArrayData dex) { 1166 this.ir = ir; 1167 this.dex = dex; 1168 } 1169 } 1170 } 1171