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 5 package com.android.tools.r8.ir.conversion; 6 7 import com.android.tools.r8.dex.Constants; 8 import com.android.tools.r8.errors.CompilationError; 9 import com.android.tools.r8.errors.InternalCompilerError; 10 import com.android.tools.r8.graph.DebugLocalInfo; 11 import com.android.tools.r8.graph.DexCallSite; 12 import com.android.tools.r8.graph.DexEncodedMethod; 13 import com.android.tools.r8.graph.DexField; 14 import com.android.tools.r8.graph.DexItem; 15 import com.android.tools.r8.graph.DexMethod; 16 import com.android.tools.r8.graph.DexMethodHandle; 17 import com.android.tools.r8.graph.DexProto; 18 import com.android.tools.r8.graph.DexString; 19 import com.android.tools.r8.graph.DexType; 20 import com.android.tools.r8.ir.code.Add; 21 import com.android.tools.r8.ir.code.And; 22 import com.android.tools.r8.ir.code.Argument; 23 import com.android.tools.r8.ir.code.ArrayGet; 24 import com.android.tools.r8.ir.code.ArrayLength; 25 import com.android.tools.r8.ir.code.ArrayPut; 26 import com.android.tools.r8.ir.code.BasicBlock; 27 import com.android.tools.r8.ir.code.BasicBlock.EdgeType; 28 import com.android.tools.r8.ir.code.BasicBlock.ThrowingInfo; 29 import com.android.tools.r8.ir.code.CatchHandlers; 30 import com.android.tools.r8.ir.code.CheckCast; 31 import com.android.tools.r8.ir.code.Cmp; 32 import com.android.tools.r8.ir.code.Cmp.Bias; 33 import com.android.tools.r8.ir.code.ConstClass; 34 import com.android.tools.r8.ir.code.ConstNumber; 35 import com.android.tools.r8.ir.code.ConstString; 36 import com.android.tools.r8.ir.code.ConstType; 37 import com.android.tools.r8.ir.code.DebugLocalUninitialized; 38 import com.android.tools.r8.ir.code.DebugLocalWrite; 39 import com.android.tools.r8.ir.code.DebugPosition; 40 import com.android.tools.r8.ir.code.Div; 41 import com.android.tools.r8.ir.code.Goto; 42 import com.android.tools.r8.ir.code.IRCode; 43 import com.android.tools.r8.ir.code.If; 44 import com.android.tools.r8.ir.code.InstanceGet; 45 import com.android.tools.r8.ir.code.InstanceOf; 46 import com.android.tools.r8.ir.code.InstancePut; 47 import com.android.tools.r8.ir.code.Instruction; 48 import com.android.tools.r8.ir.code.InstructionListIterator; 49 import com.android.tools.r8.ir.code.Invoke; 50 import com.android.tools.r8.ir.code.Invoke.Type; 51 import com.android.tools.r8.ir.code.InvokeCustom; 52 import com.android.tools.r8.ir.code.MemberType; 53 import com.android.tools.r8.ir.code.Monitor; 54 import com.android.tools.r8.ir.code.MoveException; 55 import com.android.tools.r8.ir.code.MoveType; 56 import com.android.tools.r8.ir.code.Mul; 57 import com.android.tools.r8.ir.code.Neg; 58 import com.android.tools.r8.ir.code.NewArrayEmpty; 59 import com.android.tools.r8.ir.code.NewArrayFilledData; 60 import com.android.tools.r8.ir.code.NewInstance; 61 import com.android.tools.r8.ir.code.Not; 62 import com.android.tools.r8.ir.code.NumberConversion; 63 import com.android.tools.r8.ir.code.NumericType; 64 import com.android.tools.r8.ir.code.Or; 65 import com.android.tools.r8.ir.code.Phi; 66 import com.android.tools.r8.ir.code.Rem; 67 import com.android.tools.r8.ir.code.Return; 68 import com.android.tools.r8.ir.code.Shl; 69 import com.android.tools.r8.ir.code.Shr; 70 import com.android.tools.r8.ir.code.StaticGet; 71 import com.android.tools.r8.ir.code.StaticPut; 72 import com.android.tools.r8.ir.code.Sub; 73 import com.android.tools.r8.ir.code.Switch; 74 import com.android.tools.r8.ir.code.Throw; 75 import com.android.tools.r8.ir.code.Ushr; 76 import com.android.tools.r8.ir.code.Value; 77 import com.android.tools.r8.ir.code.Value.DebugInfo; 78 import com.android.tools.r8.ir.code.ValueNumberGenerator; 79 import com.android.tools.r8.ir.code.Xor; 80 import com.android.tools.r8.utils.InternalOptions; 81 import it.unimi.dsi.fastutil.ints.Int2ReferenceAVLTreeMap; 82 import it.unimi.dsi.fastutil.ints.Int2ReferenceMap; 83 import it.unimi.dsi.fastutil.ints.Int2ReferenceSortedMap; 84 import it.unimi.dsi.fastutil.ints.IntArrayList; 85 import it.unimi.dsi.fastutil.ints.IntArraySet; 86 import it.unimi.dsi.fastutil.ints.IntIterator; 87 import it.unimi.dsi.fastutil.ints.IntList; 88 import it.unimi.dsi.fastutil.ints.IntSet; 89 import java.util.ArrayList; 90 import java.util.Collections; 91 import java.util.HashMap; 92 import java.util.HashSet; 93 import java.util.LinkedList; 94 import java.util.List; 95 import java.util.Map; 96 import java.util.Queue; 97 import java.util.Set; 98 99 /** 100 * Builder object for constructing high-level IR from dex bytecode. 101 * 102 * <p>The generated IR is in SSA form. The SSA construction is based on the paper 103 * "Simple and Efficient Construction of Static Single Assignment Form" available at 104 * http://compilers.cs.uni-saarland.de/papers/bbhlmz13cc.pdf 105 */ 106 public class IRBuilder { 107 108 public static final int INITIAL_BLOCK_OFFSET = -1; 109 110 // SSA construction uses a worklist of basic blocks reachable from the entry and their 111 // instruction offsets. 112 private static class WorklistItem { 113 114 private final BasicBlock block; 115 private final int firstInstructionIndex; 116 WorklistItem(BasicBlock block, int firstInstructionIndex)117 private WorklistItem(BasicBlock block, int firstInstructionIndex) { 118 assert block != null; 119 this.block = block; 120 this.firstInstructionIndex = firstInstructionIndex; 121 } 122 } 123 124 /** 125 * Representation of lists of values that can be used as keys in maps. A list of 126 * values is equal to another list of values if it contains exactly the same values 127 * in the same order. 128 */ 129 private static class ValueList { 130 131 private List<Value> values = new ArrayList<>(); 132 133 /** 134 * Creates a ValueList of all the operands at the given index in the list of phis. 135 */ fromPhis(List<Phi> phis, int index)136 public static ValueList fromPhis(List<Phi> phis, int index) { 137 ValueList result = new ValueList(); 138 for (Phi phi : phis) { 139 result.values.add(phi.getOperand(index)); 140 } 141 return result; 142 } 143 144 @Override hashCode()145 public int hashCode() { 146 return values.hashCode(); 147 } 148 149 @Override equals(Object other)150 public boolean equals(Object other) { 151 if (!(other instanceof ValueList)) { 152 return false; 153 } 154 ValueList o = (ValueList) other; 155 if (o.values.size() != values.size()) { 156 return false; 157 } 158 for (int i = 0; i < values.size(); i++) { 159 if (values.get(i) != o.values.get(i)) { 160 return false; 161 } 162 } 163 return true; 164 } 165 } 166 167 public static class BlockInfo { 168 BasicBlock block = new BasicBlock(); 169 IntSet normalPredecessors = new IntArraySet(); 170 IntSet normalSuccessors = new IntArraySet(); 171 IntSet exceptionalPredecessors = new IntArraySet(); 172 IntSet exceptionalSuccessors = new IntArraySet(); 173 addNormalPredecessor(int offset)174 void addNormalPredecessor(int offset) { 175 normalPredecessors.add(offset); 176 } 177 addNormalSuccessor(int offset)178 void addNormalSuccessor(int offset) { 179 normalSuccessors.add(offset); 180 } 181 replaceNormalPredecessor(int existing, int replacement)182 void replaceNormalPredecessor(int existing, int replacement) { 183 normalPredecessors.remove(existing); 184 normalPredecessors.add(replacement); 185 } 186 addExceptionalPredecessor(int offset)187 void addExceptionalPredecessor(int offset) { 188 exceptionalPredecessors.add(offset); 189 } 190 addExceptionalSuccessor(int offset)191 void addExceptionalSuccessor(int offset) { 192 exceptionalSuccessors.add(offset); 193 } 194 predecessorCount()195 int predecessorCount() { 196 return normalPredecessors.size() + exceptionalPredecessors.size(); 197 } 198 split( int blockStartOffset, int fallthroughOffset, Int2ReferenceMap<BlockInfo> targets)199 BlockInfo split( 200 int blockStartOffset, int fallthroughOffset, Int2ReferenceMap<BlockInfo> targets) { 201 BlockInfo fallthroughInfo = new BlockInfo(); 202 fallthroughInfo.normalPredecessors = new IntArraySet(Collections.singleton(blockStartOffset)); 203 fallthroughInfo.block.incrementUnfilledPredecessorCount(); 204 // Move all normal successors to the fallthrough block. 205 IntIterator normalSuccessorIterator = normalSuccessors.iterator(); 206 while (normalSuccessorIterator.hasNext()) { 207 BlockInfo normalSuccessor = targets.get(normalSuccessorIterator.nextInt()); 208 normalSuccessor.replaceNormalPredecessor(blockStartOffset, fallthroughOffset); 209 } 210 fallthroughInfo.normalSuccessors = normalSuccessors; 211 normalSuccessors = new IntArraySet(Collections.singleton(fallthroughOffset)); 212 // Copy all exceptional successors to the fallthrough block. 213 IntIterator exceptionalSuccessorIterator = fallthroughInfo.exceptionalSuccessors.iterator(); 214 while (exceptionalSuccessorIterator.hasNext()) { 215 BlockInfo exceptionalSuccessor = targets.get(exceptionalSuccessorIterator.nextInt()); 216 exceptionalSuccessor.addExceptionalPredecessor(fallthroughOffset); 217 } 218 fallthroughInfo.exceptionalSuccessors = new IntArraySet(this.exceptionalSuccessors); 219 return fallthroughInfo; 220 } 221 } 222 223 // Mapping from instruction offsets to basic-block targets. 224 private final Int2ReferenceSortedMap<BlockInfo> targets = new Int2ReferenceAVLTreeMap<>(); 225 226 // Worklist of reachable blocks. 227 private final Queue<Integer> traceBlocksWorklist = new LinkedList<>(); 228 229 // Bitmap to ensure we don't process an instruction more than once. 230 private boolean[] processedInstructions = null; 231 232 // Bitmap of processed subroutine instructions. Lazily allocated off the fast-path. 233 private Set<Integer> processedSubroutineInstructions = null; 234 235 // Worklist for SSA construction. 236 private final Queue<WorklistItem> ssaWorklist = new LinkedList<>(); 237 238 // Basic blocks. Added after processing from the worklist. 239 private LinkedList<BasicBlock> blocks = new LinkedList<>(); 240 241 private BasicBlock currentBlock = null; 242 243 // Mappings for canonicalizing constants of a given type at IR construction time. 244 private Map<Long, ConstNumber> intConstants = new HashMap<>(); 245 private Map<Long, ConstNumber> longConstants = new HashMap<>(); 246 private Map<Long, ConstNumber> floatConstants = new HashMap<>(); 247 private Map<Long, ConstNumber> doubleConstants = new HashMap<>(); 248 private Map<Long, ConstNumber> nullConstants = new HashMap<>(); 249 250 private List<BasicBlock> exitBlocks = new ArrayList<>(); 251 private BasicBlock normalExitBlock; 252 253 private List<BasicBlock.Pair> needGotoToCatchBlocks = new ArrayList<>(); 254 255 final private ValueNumberGenerator valueNumberGenerator; 256 257 private DebugPosition currentDebugPosition = null; 258 259 private DexEncodedMethod method; 260 261 // Source code to build IR from. Null if already built. 262 private SourceCode source; 263 264 boolean throwingInstructionInCurrentBlock = false; 265 266 private final InternalOptions options; 267 268 // Pending local changes. 269 private List<Value> debugLocalStarts = new ArrayList<>(); 270 private List<Value> debugLocalReads = new ArrayList<>(); 271 private List<Value> debugLocalEnds = new ArrayList<>(); 272 273 private int nextBlockNumber = 0; 274 IRBuilder(DexEncodedMethod method, SourceCode source, InternalOptions options)275 public IRBuilder(DexEncodedMethod method, SourceCode source, InternalOptions options) { 276 this(method, source, new ValueNumberGenerator(), options); 277 } 278 IRBuilder( DexEncodedMethod method, SourceCode source, ValueNumberGenerator valueNumberGenerator, InternalOptions options)279 public IRBuilder( 280 DexEncodedMethod method, 281 SourceCode source, 282 ValueNumberGenerator valueNumberGenerator, 283 InternalOptions options) { 284 assert source != null; 285 this.method = method; 286 this.source = source; 287 this.valueNumberGenerator = valueNumberGenerator; 288 this.options = options; 289 } 290 getCFG()291 public Int2ReferenceSortedMap<BlockInfo> getCFG() { 292 return targets; 293 } 294 addToWorklist(BasicBlock block, int firstInstructionIndex)295 private void addToWorklist(BasicBlock block, int firstInstructionIndex) { 296 // TODO(ager): Filter out the ones that are already in the worklist, mark bit in block? 297 if (!block.isFilled()) { 298 ssaWorklist.add(new WorklistItem(block, firstInstructionIndex)); 299 } 300 } 301 setCurrentBlock(BasicBlock block)302 private void setCurrentBlock(BasicBlock block) { 303 currentBlock = block; 304 } 305 306 /** 307 * Build the high-level IR in SSA form. 308 * 309 * @return The list of basic blocks. First block is the main entry. 310 */ build()311 public IRCode build() { 312 assert source != null; 313 source.setUp(); 314 315 // Create entry block (at a non-targetable address). 316 targets.put(INITIAL_BLOCK_OFFSET, new BlockInfo()); 317 318 // Process reachable code paths starting from instruction 0. 319 processedInstructions = new boolean[source.instructionCount()]; 320 traceBlocksWorklist.add(0); 321 while (!traceBlocksWorklist.isEmpty()) { 322 int startOfBlockOffset = traceBlocksWorklist.remove(); 323 int startOfBlockIndex = source.instructionIndex(startOfBlockOffset); 324 // Check that the block has not been processed after being added. 325 if (isIndexProcessed(startOfBlockIndex)) { 326 continue; 327 } 328 // Process each instruction until the block is closed. 329 for (int index = startOfBlockIndex; index < source.instructionCount(); ++index) { 330 markIndexProcessed(index); 331 int closedAt = source.traceInstruction(index, this); 332 if (closedAt != -1) { 333 if (closedAt + 1 < source.instructionCount()) { 334 ensureBlockWithoutEnqueuing(source.instructionOffset(closedAt + 1)); 335 } 336 break; 337 } 338 // If the next instruction starts a block, fall through to it. 339 if (index + 1 < source.instructionCount()) { 340 int nextOffset = source.instructionOffset(index + 1); 341 if (targets.get(nextOffset) != null) { 342 ensureNormalSuccessorBlock(startOfBlockOffset, nextOffset); 343 break; 344 } 345 } 346 } 347 } 348 processedInstructions = null; 349 350 setCurrentBlock(targets.get(INITIAL_BLOCK_OFFSET).block); 351 source.buildPrelude(this); 352 353 // Process normal blocks reachable from the entry block using a worklist of reachable 354 // blocks. 355 addToWorklist(currentBlock, 0); 356 processWorklist(); 357 358 // Check that the last block is closed and does not fall off the end. 359 assert currentBlock == null; 360 361 // Handle where a catch handler hits the same block as the fallthrough. 362 handleFallthroughToCatchBlock(); 363 364 // Verify that we have properly filled all blocks 365 // Must be after handle-catch (which has delayed edges), 366 // but before handle-exit (which does not maintain predecessor counts). 367 assert verifyFilledPredecessors(); 368 369 // If there are multiple returns create an exit block. 370 handleExitBlock(); 371 372 // Clear all reaching definitions to free up memory (and avoid invalid use). 373 for (BasicBlock block : blocks) { 374 block.clearCurrentDefinitions(); 375 } 376 377 // Join predecessors for which all phis have the same inputs. This avoids generating the 378 // same phi moves in multiple blocks. 379 joinPredecessorsWithIdenticalPhis(); 380 381 // Split critical edges to make sure that we have a place to insert phi moves if 382 // necessary. 383 splitCriticalEdges(); 384 385 // Package up the IR code. 386 IRCode ir = new IRCode(method, blocks, normalExitBlock, valueNumberGenerator); 387 388 // Create block order and make sure that all blocks are immediately followed by their 389 // fallthrough block if any. 390 traceBlocks(ir); 391 392 // Clear the code so we don't build multiple times. 393 source.clear(); 394 clearCanonicalizationMaps(); 395 source = null; 396 397 assert ir.isConsistentSSA(); 398 return ir; 399 } 400 clearCanonicalizationMaps()401 private void clearCanonicalizationMaps() { 402 intConstants = null; 403 longConstants = null; 404 floatConstants = null; 405 doubleConstants = null; 406 nullConstants = null; 407 } 408 verifyFilledPredecessors()409 private boolean verifyFilledPredecessors() { 410 for (BasicBlock block : blocks) { 411 assert verifyFilledPredecessors(block); 412 } 413 return true; 414 } 415 verifyFilledPredecessors(BasicBlock block)416 private boolean verifyFilledPredecessors(BasicBlock block) { 417 assert block.verifyFilledPredecessors(); 418 // TODO(zerny): Consider moving the validation of the initial control-flow graph to after its 419 // construction and prior to building the IR. 420 for (BlockInfo info : targets.values()) { 421 if (info != null && info.block == block) { 422 assert info.predecessorCount() == block.getPredecessors().size(); 423 assert info.normalSuccessors.size() == block.getNormalSucessors().size(); 424 if (block.hasCatchHandlers()) { 425 assert info.exceptionalSuccessors.size() 426 == block.getCatchHandlers().getUniqueTargets().size(); 427 } else { 428 assert !block.canThrow() 429 || info.exceptionalSuccessors.isEmpty() 430 || (info.exceptionalSuccessors.size() == 1 431 && info.exceptionalSuccessors.iterator().nextInt() < 0); 432 } 433 return true; 434 } 435 } 436 // There are places where we add in new blocks that we do not represent in the initial CFG. 437 // TODO(zerny): Should we maintain the initial CFG after instruction building? 438 return true; 439 } 440 441 private void processWorklist() { 442 for (WorklistItem item = ssaWorklist.poll(); item != null; item = ssaWorklist.poll()) { 443 if (item.block.isFilled()) { 444 continue; 445 } 446 setCurrentBlock(item.block); 447 blocks.add(currentBlock); 448 currentBlock.setNumber(nextBlockNumber++); 449 // Build IR for each dex instruction in the block. 450 for (int i = item.firstInstructionIndex; i < source.instructionCount(); ++i) { 451 if (currentBlock == null) { 452 source.closedCurrentBlock(); 453 break; 454 } 455 BlockInfo info = targets.get(source.instructionOffset(i)); 456 if (info != null && info.block != currentBlock) { 457 closeCurrentBlockWithFallThrough(info.block); 458 source.closedCurrentBlockWithFallthrough(i); 459 addToWorklist(info.block, i); 460 break; 461 } 462 source.buildInstruction(this, i); 463 } 464 } 465 } 466 467 // Helper to resolve switch payloads and build switch instructions (dex code only). 468 public void resolveAndBuildSwitch(int value, int fallthroughOffset, int payloadOffset) { 469 source.resolveAndBuildSwitch(value, fallthroughOffset, payloadOffset, this); 470 } 471 472 // Helper to resolve fill-array data and build new-array instructions (dex code only). 473 public void resolveAndBuildNewArrayFilledData(int arrayRef, int payloadOffset) { 474 source.resolveAndBuildNewArrayFilledData(arrayRef, payloadOffset, this); 475 } 476 477 /** 478 * Add an (non-jump) instruction to the builder. 479 * 480 * @param ir IR instruction to add as the next instruction. 481 */ 482 public void add(Instruction ir) { 483 assert !ir.isJumpInstruction(); 484 addInstruction(ir); 485 } 486 487 public void addThisArgument(int register) { 488 DebugLocalInfo local = getCurrentLocal(register); 489 DebugInfo info = local == null ? null : new DebugInfo(local, null); 490 Value value = writeRegister(register, MoveType.OBJECT, ThrowingInfo.NO_THROW, info); 491 addInstruction(new Argument(value)); 492 value.markAsThis(); 493 } 494 495 public void addNonThisArgument(int register, MoveType moveType) { 496 DebugLocalInfo local = getCurrentLocal(register); 497 DebugInfo info = local == null ? null : new DebugInfo(local, null); 498 Value value = writeRegister(register, moveType, ThrowingInfo.NO_THROW, info); 499 addInstruction(new Argument(value)); 500 } 501 502 public void addDebugUninitialized(int register, ConstType type) { 503 if (!options.debug) { 504 return; 505 } 506 Value value = writeRegister(register, MoveType.fromConstType(type), ThrowingInfo.NO_THROW, 507 null); 508 assert value.getLocalInfo() == null; 509 addInstruction(new DebugLocalUninitialized(type, value)); 510 } 511 512 public void addDebugLocalStart(int register, DebugLocalInfo local) { 513 if (!options.debug) { 514 return; 515 } 516 assert local != null; 517 assert local == getCurrentLocal(register); 518 MoveType moveType = MoveType.fromDexType(local.type); 519 Value in = readRegisterIgnoreLocal(register, moveType); 520 if (in.isPhi() || in.getLocalInfo() != local) { 521 // We cannot shortcut if the local is defined by a phi as it could end up being trivial. 522 addDebugLocalWrite(moveType, register, in); 523 } else { 524 Value value = getLocalValue(register, local); 525 if (value != null) { 526 debugLocalStarts.add(value); 527 } 528 } 529 } 530 531 private void addDebugLocalWrite(MoveType type, int dest, Value in) { 532 Value out = writeRegister(dest, type, ThrowingInfo.NO_THROW); 533 DebugLocalWrite write = new DebugLocalWrite(out, in); 534 assert !write.instructionTypeCanThrow(); 535 addInstruction(write); 536 } 537 538 private Value getLocalValue(int register, DebugLocalInfo local) { 539 assert local != null; 540 assert local == getCurrentLocal(register); 541 MoveType moveType = MoveType.fromDexType(local.type); 542 // Invalid debug-info may cause attempt to read a local that is not actually alive. 543 // See b/37722432 and regression test {@code jasmin.InvalidDebugInfoTests::testInvalidInfoThrow} 544 Value in = readRegisterIgnoreLocal(register, moveType); 545 if (in.isUninitializedLocal() || in.getLocalInfo() != local) { 546 return null; 547 } 548 assert in.getLocalInfo() == local; 549 return in; 550 } 551 552 public void addDebugLocalRead(int register, DebugLocalInfo local) { 553 if (!options.debug) { 554 return; 555 } 556 Value value = getLocalValue(register, local); 557 if (value != null) { 558 debugLocalReads.add(value); 559 } 560 } 561 562 public void addDebugLocalEnd(int register, DebugLocalInfo local) { 563 if (!options.debug) { 564 return; 565 } 566 Value value = getLocalValue(register, local); 567 if (value != null) { 568 debugLocalEnds.add(value); 569 } 570 } 571 572 public void addAdd(NumericType type, int dest, int left, int right) { 573 Value in1 = readNumericRegister(left, type); 574 Value in2 = readNumericRegister(right, type); 575 Value out = writeNumericRegister(dest, type, ThrowingInfo.NO_THROW); 576 Add instruction = new Add(type, out, in1, in2); 577 assert !instruction.instructionTypeCanThrow(); 578 addInstruction(instruction); 579 } 580 581 public void addAddLiteral(NumericType type, int dest, int value, int constant) { 582 assert isNonLongIntegerType(type); 583 Value in1 = readNumericRegister(value, type); 584 Value in2 = readLiteral(type, constant); 585 Value out = writeNumericRegister(dest, type, ThrowingInfo.NO_THROW); 586 Add instruction = new Add(type, out, in1, in2); 587 assert !instruction.instructionTypeCanThrow(); 588 addInstruction(instruction); 589 } 590 591 public void addAnd(NumericType type, int dest, int left, int right) { 592 assert isIntegerType(type); 593 Value in1 = readNumericRegister(left, type); 594 Value in2 = readNumericRegister(right, type); 595 Value out = writeNumericRegister(dest, type, ThrowingInfo.NO_THROW); 596 And instruction = new And(type, out, in1, in2); 597 assert !instruction.instructionTypeCanThrow(); 598 addInstruction(instruction); 599 } 600 601 public void addAndLiteral(NumericType type, int dest, int value, int constant) { 602 assert isNonLongIntegerType(type); 603 Value in1 = readNumericRegister(value, type); 604 Value in2 = readLiteral(type, constant); 605 Value out = writeNumericRegister(dest, type, ThrowingInfo.NO_THROW); 606 And instruction = new And(type, out, in1, in2); 607 assert !instruction.instructionTypeCanThrow(); 608 addInstruction(instruction); 609 } 610 611 public void addArrayGet(MemberType type, int dest, int array, int index) { 612 Value in1 = readRegister(array, MoveType.OBJECT); 613 Value in2 = readRegister(index, MoveType.SINGLE); 614 Value out = writeRegister(dest, MoveType.fromMemberType(type), ThrowingInfo.CAN_THROW); 615 ArrayGet instruction = new ArrayGet(type, out, in1, in2); 616 assert instruction.instructionTypeCanThrow(); 617 add(instruction); 618 } 619 620 public void addArrayLength(int dest, int array) { 621 Value in = readRegister(array, MoveType.OBJECT); 622 Value out = writeRegister(dest, MoveType.SINGLE, ThrowingInfo.CAN_THROW); 623 ArrayLength instruction = new ArrayLength(out, in); 624 assert instruction.instructionTypeCanThrow(); 625 add(instruction); 626 } 627 628 public void addArrayPut(MemberType type, int value, int array, int index) { 629 List<Value> ins = new ArrayList<>(3); 630 ins.add(readRegister(value, MoveType.fromMemberType(type))); 631 ins.add(readRegister(array, MoveType.OBJECT)); 632 ins.add(readRegister(index, MoveType.SINGLE)); 633 ArrayPut instruction = new ArrayPut(type, ins); 634 add(instruction); 635 } 636 637 public void addCheckCast(int value, DexType type) { 638 Value in = readRegister(value, MoveType.OBJECT); 639 Value out = writeRegister(value, MoveType.OBJECT, ThrowingInfo.CAN_THROW); 640 CheckCast instruction = new CheckCast(out, in, type); 641 assert instruction.instructionTypeCanThrow(); 642 add(instruction); 643 } 644 645 public void addCmp(NumericType type, Bias bias, int dest, int left, int right) { 646 Value in1 = readNumericRegister(left, type); 647 Value in2 = readNumericRegister(right, type); 648 Value out = writeRegister(dest, MoveType.SINGLE, ThrowingInfo.NO_THROW); 649 Cmp instruction = new Cmp(type, bias, out, in1, in2); 650 assert !instruction.instructionTypeCanThrow(); 651 add(instruction); 652 } 653 654 public void addConst(MoveType type, int dest, long value) { 655 ConstNumber instruction; 656 if (type == MoveType.SINGLE) { 657 Value out = writeRegister(dest, type, ThrowingInfo.NO_THROW); 658 instruction = new ConstNumber(ConstType.INT_OR_FLOAT, out, value); 659 } else { 660 assert type == MoveType.WIDE; 661 Value out = writeRegister(dest, type, ThrowingInfo.NO_THROW); 662 instruction = new ConstNumber(ConstType.LONG_OR_DOUBLE, out, value); 663 } 664 assert !instruction.instructionTypeCanThrow(); 665 add(instruction); 666 } 667 668 // TODO(ager): Does art support changing the value of locals during debugging? If so, we need 669 // to disable constant canonicalization in debug builds to make sure we have separate values 670 // for separate locals. 671 private void canonicalizeAndAddConst( 672 ConstType type, int dest, long value, Map<Long, ConstNumber> table) { 673 ConstNumber existing = table.get(value); 674 if (existing != null) { 675 currentBlock.writeCurrentDefinition(dest, existing.outValue(), ThrowingInfo.NO_THROW); 676 } else { 677 Value out = writeRegister(dest, MoveType.fromConstType(type), ThrowingInfo.NO_THROW); 678 ConstNumber instruction = new ConstNumber(type, out, value); 679 BasicBlock entryBlock = blocks.get(0); 680 if (currentBlock != entryBlock) { 681 // Insert the constant instruction at the start of the block right after the argument 682 // instructions. It is important that the const instruction is put before any instruction 683 // that can throw exceptions (since the value could be used on the exceptional edge). 684 InstructionListIterator it = entryBlock.listIterator(); 685 while (it.hasNext()) { 686 if (!it.next().isArgument()) { 687 it.previous(); 688 break; 689 } 690 } 691 it.add(instruction); 692 } else { 693 add(instruction); 694 } 695 table.put(value, instruction); 696 } 697 } 698 699 public void addLongConst(int dest, long value) { 700 canonicalizeAndAddConst(ConstType.LONG, dest, value, longConstants); 701 } 702 703 public void addDoubleConst(int dest, long value) { 704 canonicalizeAndAddConst(ConstType.DOUBLE, dest, value, doubleConstants); 705 } 706 707 public void addIntConst(int dest, long value) { 708 canonicalizeAndAddConst(ConstType.INT, dest, value, intConstants); 709 } 710 711 public void addFloatConst(int dest, long value) { 712 canonicalizeAndAddConst(ConstType.FLOAT, dest, value, floatConstants); 713 } 714 715 public void addNullConst(int dest, long value) { 716 canonicalizeAndAddConst(ConstType.INT, dest, value, nullConstants); 717 } 718 719 public void addConstClass(int dest, DexType type) { 720 Value out = writeRegister(dest, MoveType.OBJECT, ThrowingInfo.CAN_THROW); 721 ConstClass instruction = new ConstClass(out, type); 722 assert instruction.instructionTypeCanThrow(); 723 add(instruction); 724 } 725 726 public void addConstString(int dest, DexString string) { 727 Value out = writeRegister(dest, MoveType.OBJECT, ThrowingInfo.CAN_THROW); 728 ConstString instruction = new ConstString(out, string); 729 add(instruction); 730 } 731 732 public void addDiv(NumericType type, int dest, int left, int right) { 733 boolean canThrow = type != NumericType.DOUBLE && type != NumericType.FLOAT; 734 Value in1 = readNumericRegister(left, type); 735 Value in2 = readNumericRegister(right, type); 736 Value out = writeNumericRegister(dest, type, 737 canThrow ? ThrowingInfo.CAN_THROW : ThrowingInfo.NO_THROW); 738 Div instruction = new Div(type, out, in1, in2); 739 assert instruction.instructionTypeCanThrow() == canThrow; 740 add(instruction); 741 } 742 743 public void addDivLiteral(NumericType type, int dest, int value, int constant) { 744 assert isNonLongIntegerType(type); 745 boolean canThrow = type != NumericType.DOUBLE && type != NumericType.FLOAT; 746 Value in1 = readNumericRegister(value, type); 747 Value in2 = readLiteral(type, constant); 748 Value out = writeNumericRegister(dest, type, 749 canThrow ? ThrowingInfo.CAN_THROW : ThrowingInfo.NO_THROW); 750 Div instruction = new Div(type, out, in1, in2); 751 assert instruction.instructionTypeCanThrow() == canThrow; 752 add(instruction); 753 } 754 755 public Monitor addMonitor(Monitor.Type type, int monitor) { 756 Value in = readRegister(monitor, MoveType.OBJECT); 757 Monitor monitorEnter = new Monitor(type, in); 758 add(monitorEnter); 759 return monitorEnter; 760 } 761 762 public void addMove(MoveType type, int dest, int src) { 763 Value in = readRegister(src, type); 764 if (options.debug) { 765 // If the move is writing to a different local we must construct a new value. 766 DebugLocalInfo destLocal = getCurrentLocal(dest); 767 if (destLocal != null && destLocal != in.getLocalInfo()) { 768 addDebugLocalWrite(type, dest, in); 769 return; 770 } 771 } 772 currentBlock.writeCurrentDefinition(dest, in, ThrowingInfo.NO_THROW); 773 } 774 775 public void addMul(NumericType type, int dest, int left, int right) { 776 Value in1 = readNumericRegister(left, type); 777 Value in2 = readNumericRegister(right, type); 778 Value out = writeNumericRegister(dest, type, ThrowingInfo.NO_THROW); 779 Mul instruction = new Mul(type, out, in1, in2); 780 assert !instruction.instructionTypeCanThrow(); 781 addInstruction(instruction); 782 } 783 784 public void addMulLiteral(NumericType type, int dest, int value, int constant) { 785 assert isNonLongIntegerType(type); 786 Value in1 = readNumericRegister(value, type); 787 Value in2 = readLiteral(type, constant); 788 Value out = writeNumericRegister(dest, type, ThrowingInfo.NO_THROW); 789 Mul instruction = new Mul(type, out, in1, in2); 790 assert !instruction.instructionTypeCanThrow(); 791 addInstruction(instruction); 792 } 793 794 public void addRem(NumericType type, int dest, int left, int right) { 795 boolean canThrow = type != NumericType.DOUBLE && type != NumericType.FLOAT; 796 Value in1 = readNumericRegister(left, type); 797 Value in2 = readNumericRegister(right, type); 798 Value out = writeNumericRegister(dest, type, 799 canThrow ? ThrowingInfo.CAN_THROW : ThrowingInfo.NO_THROW); 800 Rem instruction = new Rem(type, out, in1, in2); 801 assert instruction.instructionTypeCanThrow() == canThrow; 802 addInstruction(instruction); 803 } 804 805 public void addRemLiteral(NumericType type, int dest, int value, int constant) { 806 assert isNonLongIntegerType(type); 807 boolean canThrow = type != NumericType.DOUBLE && type != NumericType.FLOAT; 808 Value in1 = readNumericRegister(value, type); 809 Value in2 = readLiteral(type, constant); 810 Value out = writeNumericRegister(dest, type, 811 canThrow ? ThrowingInfo.CAN_THROW : ThrowingInfo.NO_THROW); 812 Rem instruction = new Rem(type, out, in1, in2); 813 assert instruction.instructionTypeCanThrow() == canThrow; 814 addInstruction(instruction); 815 } 816 817 public void addGoto(int targetOffset) { 818 addInstruction(new Goto()); 819 BasicBlock targetBlock = getTarget(targetOffset); 820 if (currentBlock.hasCatchSuccessor(targetBlock)) { 821 needGotoToCatchBlocks.add(new BasicBlock.Pair(currentBlock, targetBlock)); 822 } else { 823 currentBlock.link(targetBlock); 824 } 825 addToWorklist(targetBlock, source.instructionIndex(targetOffset)); 826 closeCurrentBlock(); 827 } 828 829 private void addTrivialIf(int trueTargetOffset, int falseTargetOffset) { 830 assert trueTargetOffset == falseTargetOffset; 831 // Conditional instructions with the same true and false targets are noops. They will 832 // always go to the next instruction. We end this basic block with a goto instead of 833 // a conditional. 834 BasicBlock target = getTarget(trueTargetOffset); 835 // We expected an if here and therefore we incremented the expected predecessor count 836 // twice for the following block. 837 target.decrementUnfilledPredecessorCount(); 838 addInstruction(new Goto()); 839 currentBlock.link(target); 840 addToWorklist(target, source.instructionIndex(trueTargetOffset)); 841 closeCurrentBlock(); 842 } 843 844 private void addNonTrivialIf(If instruction, int trueTargetOffset, int falseTargetOffset) { 845 addInstruction(instruction); 846 BasicBlock trueTarget = getTarget(trueTargetOffset); 847 BasicBlock falseTarget = getTarget(falseTargetOffset); 848 currentBlock.link(trueTarget); 849 currentBlock.link(falseTarget); 850 // Generate fall-through before the block that is branched to. 851 addToWorklist(falseTarget, source.instructionIndex(falseTargetOffset)); 852 addToWorklist(trueTarget, source.instructionIndex(trueTargetOffset)); 853 closeCurrentBlock(); 854 } 855 856 public void addIf(If.Type type, int value1, int value2, 857 int trueTargetOffset, int falseTargetOffset) { 858 if (trueTargetOffset == falseTargetOffset) { 859 addTrivialIf(trueTargetOffset, falseTargetOffset); 860 } else { 861 List<Value> values = new ArrayList<>(2); 862 values.add(readRegister(value1, MoveType.SINGLE)); 863 values.add(readRegister(value2, MoveType.SINGLE)); 864 If instruction = new If(type, values); 865 addNonTrivialIf(instruction, trueTargetOffset, falseTargetOffset); 866 } 867 } 868 869 public void addIfZero(If.Type type, int value, int trueTargetOffset, int falseTargetOffset) { 870 if (trueTargetOffset == falseTargetOffset) { 871 addTrivialIf(trueTargetOffset, falseTargetOffset); 872 } else { 873 If instruction = new If(type, readRegister(value, MoveType.SINGLE)); 874 addNonTrivialIf(instruction, trueTargetOffset, falseTargetOffset); 875 } 876 } 877 878 public void addInstanceGet( 879 MemberType type, 880 int dest, 881 int object, 882 DexField field) { 883 Value in = readRegister(object, MoveType.OBJECT); 884 Value out = writeRegister(dest, MoveType.fromMemberType(type), ThrowingInfo.CAN_THROW); 885 InstanceGet instruction = new InstanceGet(type, out, in, field); 886 assert instruction.instructionTypeCanThrow(); 887 addInstruction(instruction); 888 } 889 890 public void addInstanceOf(int dest, int value, DexType type) { 891 Value in = readRegister(value, MoveType.OBJECT); 892 Value out = writeRegister(dest, MoveType.SINGLE, ThrowingInfo.CAN_THROW); 893 InstanceOf instruction = new InstanceOf(out, in, type); 894 assert instruction.instructionTypeCanThrow(); 895 addInstruction(instruction); 896 } 897 898 public void addInstancePut( 899 MemberType type, 900 int value, 901 int object, 902 DexField field) { 903 List<Value> values = new ArrayList<>(2); 904 values.add(readRegister(value, MoveType.fromMemberType(type))); 905 values.add(readRegister(object, MoveType.OBJECT)); 906 InstancePut instruction = new InstancePut(type, values, field); 907 add(instruction); 908 } 909 910 public void addInvoke( 911 Type type, DexItem item, DexProto callSiteProto, List<Value> arguments) { 912 if (type == Invoke.Type.POLYMORPHIC && !options.canUseInvokePolymorphic()) { 913 throw new CompilationError( 914 "MethodHandle.invoke and MethodHandle.invokeExact is unsupported before " 915 + "Android O (--min-api " + Constants.ANDROID_O_API + ")"); 916 } 917 add(Invoke.create(type, item, callSiteProto, null, arguments)); 918 } 919 920 public void addInvoke( 921 Invoke.Type type, 922 DexItem item, 923 DexProto callSiteProto, 924 List<MoveType> types, 925 List<Integer> registers) { 926 assert types.size() == registers.size(); 927 List<Value> arguments = new ArrayList<>(types.size()); 928 for (int i = 0; i < types.size(); i++) { 929 arguments.add(readRegister(registers.get(i), types.get(i))); 930 } 931 addInvoke(type, item, callSiteProto, arguments); 932 } 933 934 public void addInvokeCustomRegisters( 935 DexCallSite callSite, int argumentRegisterCount, int[] argumentRegisters) { 936 int registerIndex = 0; 937 DexMethodHandle bootstrapMethod = callSite.bootstrapMethod; 938 List<Value> arguments = new ArrayList<>(argumentRegisterCount); 939 940 if (!bootstrapMethod.isStaticHandle()) { 941 arguments.add(readRegister(argumentRegisters[registerIndex], MoveType.OBJECT)); 942 registerIndex += MoveType.OBJECT.requiredRegisters(); 943 } 944 945 String shorty = callSite.methodProto.shorty.toString(); 946 947 for (int i = 1; i < shorty.length(); i++) { 948 MoveType moveType = MoveType.fromTypeDescriptorChar(shorty.charAt(i)); 949 arguments.add(readRegister(argumentRegisters[registerIndex], moveType)); 950 registerIndex += moveType.requiredRegisters(); 951 } 952 953 add(new InvokeCustom(callSite, null, arguments)); 954 } 955 956 public void addInvokeCustomRange( 957 DexCallSite callSite, int argumentCount, int firstArgumentRegister) { 958 DexMethodHandle bootstrapMethod = callSite.bootstrapMethod; 959 List<Value> arguments = new ArrayList<>(argumentCount); 960 961 int register = firstArgumentRegister; 962 if (!bootstrapMethod.isStaticHandle()) { 963 arguments.add(readRegister(register, MoveType.OBJECT)); 964 register += MoveType.OBJECT.requiredRegisters(); 965 } 966 967 String shorty = callSite.methodProto.shorty.toString(); 968 969 for (int i = 1; i < shorty.length(); i++) { 970 MoveType moveType = MoveType.fromTypeDescriptorChar(shorty.charAt(i)); 971 arguments.add(readRegister(register, moveType)); 972 register += moveType.requiredRegisters(); 973 } 974 checkInvokeArgumentRegisters(register, firstArgumentRegister + argumentCount); 975 add(new InvokeCustom(callSite, null, arguments)); 976 } 977 978 public void addInvokeCustom( 979 DexCallSite callSite, List<MoveType> types, List<Integer> registers) { 980 assert types.size() == registers.size(); 981 List<Value> arguments = new ArrayList<>(types.size()); 982 for (int i = 0; i < types.size(); i++) { 983 arguments.add(readRegister(registers.get(i), types.get(i))); 984 } 985 add(new InvokeCustom(callSite, null, arguments)); 986 } 987 988 public void addInvokeRegisters( 989 Invoke.Type type, 990 DexMethod method, 991 DexProto callSiteProto, 992 int argumentRegisterCount, 993 int[] argumentRegisters) { 994 // The value of argumentRegisterCount is the number of registers - not the number of values, 995 // but it is an upper bound on the number of arguments. 996 List<Value> arguments = new ArrayList<>(argumentRegisterCount); 997 int registerIndex = 0; 998 if (type != Invoke.Type.STATIC) { 999 arguments.add(readRegister(argumentRegisters[registerIndex], MoveType.OBJECT)); 1000 registerIndex += MoveType.OBJECT.requiredRegisters(); 1001 } 1002 DexString methodShorty; 1003 if (type == Invoke.Type.POLYMORPHIC) { 1004 // The call site signature for invoke polymorphic must be take from call site and not from 1005 // the called method. 1006 methodShorty = callSiteProto.shorty; 1007 } else { 1008 methodShorty = method.proto.shorty; 1009 } 1010 String shorty = methodShorty.toString(); 1011 for (int i = 1; i < methodShorty.size; i++) { 1012 MoveType moveType = MoveType.fromTypeDescriptorChar(shorty.charAt(i)); 1013 arguments.add(readRegister(argumentRegisters[registerIndex], moveType)); 1014 registerIndex += moveType.requiredRegisters(); 1015 } 1016 checkInvokeArgumentRegisters(registerIndex, argumentRegisterCount); 1017 addInvoke(type, method, callSiteProto, arguments); 1018 } 1019 1020 public void addInvokeNewArray(DexType type, int argumentCount, int[] argumentRegisters) { 1021 String descriptor = type.descriptor.toString(); 1022 assert descriptor.charAt(0) == '['; 1023 assert descriptor.length() >= 2; 1024 MoveType moveType = MoveType.fromTypeDescriptorChar(descriptor.charAt(1)); 1025 List<Value> arguments = new ArrayList<>(argumentCount / moveType.requiredRegisters()); 1026 int registerIndex = 0; 1027 while (registerIndex < argumentCount) { 1028 arguments.add(readRegister(argumentRegisters[registerIndex], moveType)); 1029 if (moveType == MoveType.WIDE) { 1030 assert registerIndex < argumentCount - 1; 1031 assert argumentRegisters[registerIndex] == argumentRegisters[registerIndex + 1] + 1; 1032 } 1033 registerIndex += moveType.requiredRegisters(); 1034 } 1035 checkInvokeArgumentRegisters(registerIndex, argumentCount); 1036 addInvoke(Invoke.Type.NEW_ARRAY, type, null, arguments); 1037 } 1038 1039 public void addInvokeRange( 1040 Invoke.Type type, 1041 DexMethod method, 1042 DexProto callSiteProto, 1043 int argumentCount, 1044 int firstArgumentRegister) { 1045 // The value of argumentCount is the number of registers - not the number of values, but it 1046 // is an upper bound on the number of arguments. 1047 List<Value> arguments = new ArrayList<>(argumentCount); 1048 int register = firstArgumentRegister; 1049 if (type != Invoke.Type.STATIC) { 1050 arguments.add(readRegister(register, MoveType.OBJECT)); 1051 register += MoveType.OBJECT.requiredRegisters(); 1052 } 1053 DexString methodShorty; 1054 if (type == Invoke.Type.POLYMORPHIC) { 1055 // The call site signature for invoke polymorphic must be take from call site and not from 1056 // the called method. 1057 methodShorty = callSiteProto.shorty; 1058 } else { 1059 methodShorty = method.proto.shorty; 1060 } 1061 String shorty = methodShorty.toString(); 1062 for (int i = 1; i < methodShorty.size; i++) { 1063 MoveType moveType = MoveType.fromTypeDescriptorChar(shorty.charAt(i)); 1064 arguments.add(readRegister(register, moveType)); 1065 register += moveType.requiredRegisters(); 1066 } 1067 checkInvokeArgumentRegisters(register, firstArgumentRegister + argumentCount); 1068 addInvoke(type, method, callSiteProto, arguments); 1069 } 1070 1071 public void addInvokeRangeNewArray(DexType type, int argumentCount, int firstArgumentRegister) { 1072 String descriptor = type.descriptor.toString(); 1073 assert descriptor.charAt(0) == '['; 1074 assert descriptor.length() >= 2; 1075 MoveType moveType = MoveType.fromTypeDescriptorChar(descriptor.charAt(1)); 1076 List<Value> arguments = new ArrayList<>(argumentCount / moveType.requiredRegisters()); 1077 int register = firstArgumentRegister; 1078 while (register < firstArgumentRegister + argumentCount) { 1079 arguments.add(readRegister(register, moveType)); 1080 register += moveType.requiredRegisters(); 1081 } 1082 checkInvokeArgumentRegisters(register, firstArgumentRegister + argumentCount); 1083 addInvoke(Invoke.Type.NEW_ARRAY, type, null, arguments); 1084 } 1085 1086 private void checkInvokeArgumentRegisters(int expected, int actual) { 1087 if (expected != actual) { 1088 throw new CompilationError("Invalid invoke instruction. " 1089 + "Expected use of " + expected + " argument registers, " 1090 + "found actual use of " + actual); 1091 } 1092 } 1093 1094 public void addMoveException(int dest) { 1095 Value out = writeRegister(dest, MoveType.OBJECT, ThrowingInfo.NO_THROW); 1096 assert out.getDebugInfo() == null; 1097 MoveException instruction = new MoveException(out); 1098 assert !instruction.instructionTypeCanThrow(); 1099 if (!currentBlock.getInstructions().isEmpty()) { 1100 throw new CompilationError("Invalid MoveException instruction encountered. " 1101 + "The MoveException instruction is not the first instruction in the block in " 1102 + method.qualifiedName() 1103 + "."); 1104 } 1105 addInstruction(instruction); 1106 } 1107 1108 public void addMoveResult(MoveType type, int dest) { 1109 List<Instruction> instructions = currentBlock.getInstructions(); 1110 Invoke invoke = instructions.get(instructions.size() - 1).asInvoke(); 1111 assert invoke.outValue() == null; 1112 assert invoke.instructionTypeCanThrow(); 1113 invoke.setOutValue(writeRegister(dest, type, ThrowingInfo.CAN_THROW)); 1114 } 1115 1116 public void addNeg(NumericType type, int dest, int value) { 1117 Value in = readNumericRegister(value, type); 1118 Value out = writeNumericRegister(dest, type, ThrowingInfo.NO_THROW); 1119 Neg instruction = new Neg(type, out, in); 1120 assert !instruction.instructionTypeCanThrow(); 1121 addInstruction(instruction); 1122 } 1123 1124 public void addNot(NumericType type, int dest, int value) { 1125 Value in = readNumericRegister(value, type); 1126 Value out = writeNumericRegister(dest, type, ThrowingInfo.NO_THROW); 1127 Not instruction = new Not(type, out, in); 1128 assert !instruction.instructionTypeCanThrow(); 1129 addInstruction(instruction); 1130 } 1131 1132 public void addNewArrayEmpty(int dest, int size, DexType type) { 1133 assert type.isArrayType(); 1134 Value in = readRegister(size, MoveType.SINGLE); 1135 Value out = writeRegister(dest, MoveType.OBJECT, ThrowingInfo.CAN_THROW); 1136 NewArrayEmpty instruction = new NewArrayEmpty(out, in, type); 1137 assert instruction.instructionTypeCanThrow(); 1138 addInstruction(instruction); 1139 } 1140 1141 public void addNewArrayFilledData(int arrayRef, int elementWidth, long size, short[] data) { 1142 add(new NewArrayFilledData(readRegister(arrayRef, MoveType.OBJECT), elementWidth, size, data)); 1143 } 1144 1145 public void addNewInstance(int dest, DexType type) { 1146 Value out = writeRegister(dest, MoveType.OBJECT, ThrowingInfo.CAN_THROW); 1147 NewInstance instruction = new NewInstance(type, out); 1148 assert instruction.instructionTypeCanThrow(); 1149 addInstruction(instruction); 1150 } 1151 1152 public void addReturn(MoveType type, int value) { 1153 Value in = readRegister(value, type); 1154 addInstruction(new Return(in, type)); 1155 exitBlocks.add(currentBlock); 1156 closeCurrentBlock(); 1157 } 1158 1159 public void addReturn() { 1160 addInstruction(new Return()); 1161 exitBlocks.add(currentBlock); 1162 closeCurrentBlock(); 1163 } 1164 1165 public void addStaticGet(MemberType type, int dest, DexField field) { 1166 Value out = writeRegister(dest, MoveType.fromMemberType(type), ThrowingInfo.CAN_THROW); 1167 StaticGet instruction = new StaticGet(type, out, field); 1168 assert instruction.instructionTypeCanThrow(); 1169 addInstruction(instruction); 1170 } 1171 1172 public void addStaticPut(MemberType type, int value, DexField field) { 1173 Value in = readRegister(value, MoveType.fromMemberType(type)); 1174 add(new StaticPut(type, in, field)); 1175 } 1176 1177 public void addSub(NumericType type, int dest, int left, int right) { 1178 Value in1 = readNumericRegister(left, type); 1179 Value in2 = readNumericRegister(right, type); 1180 Value out = writeNumericRegister(dest, type, ThrowingInfo.NO_THROW); 1181 Sub instruction = new Sub(type, out, in1, in2); 1182 assert !instruction.instructionTypeCanThrow(); 1183 addInstruction(instruction); 1184 } 1185 1186 public void addRsubLiteral(NumericType type, int dest, int value, int constant) { 1187 assert type != NumericType.DOUBLE; 1188 Value in1 = readNumericRegister(value, type); 1189 Value in2 = readLiteral(type, constant); 1190 Value out = writeNumericRegister(dest, type, ThrowingInfo.NO_THROW); 1191 // Add this as a sub instruction - sub instructions with literals need to have the constant 1192 // on the left side (rsub). 1193 Sub instruction = new Sub(type, out, in2, in1); 1194 assert !instruction.instructionTypeCanThrow(); 1195 addInstruction(instruction); 1196 } 1197 1198 private void addSwitchIf(int key, int value, int caseOffset, int fallthroughOffset) { 1199 if (key == 0) { 1200 addIfZero(If.Type.EQ, value, caseOffset, fallthroughOffset); 1201 } else { 1202 if (caseOffset == fallthroughOffset) { 1203 addTrivialIf(caseOffset, fallthroughOffset); 1204 } else { 1205 List<Value> values = new ArrayList<>(2); 1206 values.add(readRegister(value, MoveType.SINGLE)); 1207 values.add(readLiteral(NumericType.INT, key)); 1208 If instruction = new If(If.Type.EQ, values); 1209 addNonTrivialIf(instruction, caseOffset, fallthroughOffset); 1210 } 1211 } 1212 } 1213 1214 public void addSwitch(int value, int[] keys, int fallthroughOffset, int[] labelOffsets) { 1215 int numberOfTargets = labelOffsets.length; 1216 assert (keys.length == 1) || (keys.length == numberOfTargets); 1217 1218 // If the switch has no targets simply add a goto to the fallthrough. 1219 if (numberOfTargets == 0) { 1220 addGoto(fallthroughOffset); 1221 return; 1222 } 1223 1224 Value switchValue = readRegister(value, MoveType.SINGLE); 1225 1226 // Find the keys not targeting the fallthrough. 1227 IntList nonFallthroughKeys = new IntArrayList(numberOfTargets); 1228 IntList nonFallthroughOffsets = new IntArrayList(numberOfTargets); 1229 int numberOfFallthroughs = 0; 1230 if (keys.length == 1) { 1231 int key = keys[0]; 1232 for (int i = 0; i < numberOfTargets; i++) { 1233 if (labelOffsets[i] != fallthroughOffset) { 1234 nonFallthroughKeys.add(key); 1235 nonFallthroughOffsets.add(labelOffsets[i]); 1236 } else { 1237 numberOfFallthroughs++; 1238 } 1239 key++; 1240 } 1241 } else { 1242 assert keys.length == numberOfTargets; 1243 for (int i = 0; i < numberOfTargets; i++) { 1244 if (labelOffsets[i] != fallthroughOffset) { 1245 nonFallthroughKeys.add(keys[i]); 1246 nonFallthroughOffsets.add(labelOffsets[i]); 1247 } else { 1248 numberOfFallthroughs++; 1249 } 1250 } 1251 } 1252 targets.get(fallthroughOffset).block.decrementUnfilledPredecessorCount(numberOfFallthroughs); 1253 1254 // If this was switch with only fallthrough cases we can make it a goto. 1255 // Oddly, this does happen. 1256 if (numberOfFallthroughs == numberOfTargets) { 1257 assert nonFallthroughKeys.size() == 0; 1258 addGoto(fallthroughOffset); 1259 return; 1260 } 1261 1262 // Create a switch with only the non-fallthrough targets. 1263 keys = nonFallthroughKeys.toIntArray(); 1264 labelOffsets = nonFallthroughOffsets.toIntArray(); 1265 addInstruction(createSwitch(switchValue, keys, fallthroughOffset, labelOffsets)); 1266 closeCurrentBlock(); 1267 } 1268 1269 private Switch createSwitch(Value value, int[] keys, int fallthroughOffset, int[] targetOffsets) { 1270 assert keys.length == targetOffsets.length; 1271 // Compute target blocks for all keys. Only add a successor block once even 1272 // if it is hit by more of the keys. 1273 int[] targetBlockIndices = new int[targetOffsets.length]; 1274 Map<Integer, Integer> offsetToBlockIndex = new HashMap<>(); 1275 // Start with fall-through block. 1276 BasicBlock fallthroughBlock = getTarget(fallthroughOffset); 1277 currentBlock.link(fallthroughBlock); 1278 addToWorklist(fallthroughBlock, source.instructionIndex(fallthroughOffset)); 1279 int fallthroughBlockIndex = currentBlock.getSuccessors().size() - 1; 1280 offsetToBlockIndex.put(fallthroughOffset, fallthroughBlockIndex); 1281 // Then all the switch target blocks. 1282 for (int i = 0; i < targetOffsets.length; i++) { 1283 int targetOffset = targetOffsets[i]; 1284 BasicBlock targetBlock = getTarget(targetOffset); 1285 Integer targetBlockIndex = offsetToBlockIndex.get(targetOffset); 1286 if (targetBlockIndex == null) { 1287 // Target block not added as successor. Add it now. 1288 currentBlock.link(targetBlock); 1289 addToWorklist(targetBlock, source.instructionIndex(targetOffset)); 1290 int successorIndex = currentBlock.getSuccessors().size() - 1; 1291 offsetToBlockIndex.put(targetOffset, successorIndex); 1292 targetBlockIndices[i] = successorIndex; 1293 } else { 1294 // Target block already added as successor. The target block therefore 1295 // has one less predecessor than precomputed. 1296 targetBlock.decrementUnfilledPredecessorCount(); 1297 targetBlockIndices[i] = targetBlockIndex; 1298 } 1299 } 1300 return new Switch(value, keys, targetBlockIndices, fallthroughBlockIndex); 1301 } 1302 1303 public void addThrow(int value) { 1304 Value in = readRegister(value, MoveType.OBJECT); 1305 addInstruction(new Throw(in)); 1306 closeCurrentBlock(); 1307 } 1308 1309 public void addOr(NumericType type, int dest, int left, int right) { 1310 assert isIntegerType(type); 1311 Value in1 = readNumericRegister(left, type); 1312 Value in2 = readNumericRegister(right, type); 1313 Value out = writeNumericRegister(dest, type, ThrowingInfo.NO_THROW); 1314 Or instruction = new Or(type, out, in1, in2); 1315 assert !instruction.instructionTypeCanThrow(); 1316 addInstruction(instruction); 1317 } 1318 1319 public void addOrLiteral(NumericType type, int dest, int value, int constant) { 1320 assert isNonLongIntegerType(type); 1321 Value in1 = readNumericRegister(value, type); 1322 Value in2 = readLiteral(type, constant); 1323 Value out = writeNumericRegister(dest, type, ThrowingInfo.NO_THROW); 1324 Or instruction = new Or(type, out, in1, in2); 1325 assert !instruction.instructionTypeCanThrow(); 1326 addInstruction(instruction); 1327 } 1328 1329 public void addShl(NumericType type, int dest, int left, int right) { 1330 assert isIntegerType(type); 1331 Value in1 = readNumericRegister(left, type); 1332 Value in2 = readRegister(right, MoveType.SINGLE); 1333 Value out = writeNumericRegister(dest, type, ThrowingInfo.NO_THROW); 1334 Shl instruction = new Shl(type, out, in1, in2); 1335 assert !instruction.instructionTypeCanThrow(); 1336 addInstruction(instruction); 1337 } 1338 1339 public void addShlLiteral(NumericType type, int dest, int value, int constant) { 1340 assert isNonLongIntegerType(type); 1341 Value in1 = readNumericRegister(value, type); 1342 Value in2 = readLiteral(type, constant); 1343 Value out = writeNumericRegister(dest, type, ThrowingInfo.NO_THROW); 1344 Shl instruction = new Shl(type, out, in1, in2); 1345 assert !instruction.instructionTypeCanThrow(); 1346 addInstruction(instruction); 1347 } 1348 1349 public void addShr(NumericType type, int dest, int left, int right) { 1350 assert isIntegerType(type); 1351 Value in1 = readNumericRegister(left, type); 1352 Value in2 = readRegister(right, MoveType.SINGLE); 1353 Value out = writeNumericRegister(dest, type, ThrowingInfo.NO_THROW); 1354 Shr instruction = new Shr(type, out, in1, in2); 1355 assert !instruction.instructionTypeCanThrow(); 1356 addInstruction(instruction); 1357 } 1358 1359 public void addShrLiteral(NumericType type, int dest, int value, int constant) { 1360 assert isNonLongIntegerType(type); 1361 Value in1 = readNumericRegister(value, type); 1362 Value in2 = readLiteral(type, constant); 1363 Value out = writeNumericRegister(dest, type, ThrowingInfo.NO_THROW); 1364 Shr instruction = new Shr(type, out, in1, in2); 1365 assert !instruction.instructionTypeCanThrow(); 1366 addInstruction(instruction); 1367 } 1368 1369 public void addUshr(NumericType type, int dest, int left, int right) { 1370 assert isIntegerType(type); 1371 Value in1 = readNumericRegister(left, type); 1372 Value in2 = readRegister(right, MoveType.SINGLE); 1373 Value out = writeNumericRegister(dest, type, ThrowingInfo.NO_THROW); 1374 Ushr instruction = new Ushr(type, out, in1, in2); 1375 assert !instruction.instructionTypeCanThrow(); 1376 addInstruction(instruction); 1377 } 1378 1379 public void addUshrLiteral(NumericType type, int dest, int value, int constant) { 1380 assert isNonLongIntegerType(type); 1381 Value in1 = readNumericRegister(value, type); 1382 Value in2 = readLiteral(type, constant); 1383 Value out = writeNumericRegister(dest, type, ThrowingInfo.NO_THROW); 1384 Ushr instruction = new Ushr(type, out, in1, in2); 1385 assert !instruction.instructionTypeCanThrow(); 1386 addInstruction(instruction); 1387 } 1388 1389 public void addXor(NumericType type, int dest, int left, int right) { 1390 assert isIntegerType(type); 1391 Value in1 = readNumericRegister(left, type); 1392 Value in2 = readNumericRegister(right, type); 1393 Value out = writeNumericRegister(dest, type, ThrowingInfo.NO_THROW); 1394 Instruction instruction; 1395 if (in2.isConstant() && in2.getConstInstruction().asConstNumber().isIntegerNegativeOne(type)) { 1396 instruction = new Not(type, out, in1); 1397 } else { 1398 instruction = new Xor(type, out, in1, in2); 1399 } 1400 assert !instruction.instructionTypeCanThrow(); 1401 addInstruction(instruction); 1402 } 1403 1404 public void addXorLiteral(NumericType type, int dest, int value, int constant) { 1405 assert isNonLongIntegerType(type); 1406 Value in1 = readNumericRegister(value, type); 1407 Instruction instruction; 1408 if (constant == -1) { 1409 Value out = writeNumericRegister(dest, type, ThrowingInfo.NO_THROW); 1410 instruction = new Not(type, out, in1); 1411 } else { 1412 Value in2 = readLiteral(type, constant); 1413 Value out = writeNumericRegister(dest, type, ThrowingInfo.NO_THROW); 1414 instruction = new Xor(type, out, in1, in2); 1415 } 1416 assert !instruction.instructionTypeCanThrow(); 1417 addInstruction(instruction); 1418 } 1419 1420 public void addConversion(NumericType to, NumericType from, int dest, int source) { 1421 Value in = readNumericRegister(source, from); 1422 Value out = writeNumericRegister(dest, to, ThrowingInfo.NO_THROW); 1423 NumberConversion instruction = new NumberConversion(from, to, out, in); 1424 assert !instruction.instructionTypeCanThrow(); 1425 addInstruction(instruction); 1426 } 1427 1428 // Value abstraction methods. 1429 1430 public Value readRegister(int register, MoveType type) { 1431 DebugLocalInfo local = getCurrentLocal(register); 1432 Value value = readRegister(register, currentBlock, EdgeType.NON_EDGE, type, local); 1433 // Check that any information about a current-local is consistent with the read. 1434 assert local == null || value.getLocalInfo() == local || value.isUninitializedLocal(); 1435 // Check that any local information on the value is actually visible. 1436 // If this assert triggers, the probable cause is that we end up reading an SSA value 1437 // after it should have been ended on a fallthrough from a conditional jump or a trivial-phi 1438 // removal resurrected the local. 1439 assert value.getLocalInfo() == null 1440 || value.getDebugLocalEnds() != null 1441 || source.verifyLocalInScope(value.getLocalInfo()); 1442 return value; 1443 } 1444 1445 public Value readRegisterIgnoreLocal(int register, MoveType type) { 1446 DebugLocalInfo local = getCurrentLocal(register); 1447 return readRegister(register, currentBlock, EdgeType.NON_EDGE, type, local); 1448 } 1449 1450 public Value readRegister(int register, BasicBlock block, EdgeType readingEdge, MoveType type, 1451 DebugLocalInfo local) { 1452 checkRegister(register); 1453 Value value = block.readCurrentDefinition(register, readingEdge); 1454 return value != null ? value : readRegisterRecursive(register, block, readingEdge, type, local); 1455 } 1456 1457 private Value readRegisterRecursive( 1458 int register, BasicBlock block, EdgeType readingEdge, MoveType type, DebugLocalInfo local) { 1459 Value value; 1460 if (!block.isSealed()) { 1461 assert !blocks.isEmpty() : "No write to " + register; 1462 Phi phi = new Phi(valueNumberGenerator.next(), block, type, local); 1463 block.addIncompletePhi(register, phi, readingEdge); 1464 value = phi; 1465 } else if (block.getPredecessors().size() == 1) { 1466 assert block.verifyFilledPredecessors(); 1467 BasicBlock pred = block.getPredecessors().get(0); 1468 EdgeType edgeType = pred.getEdgeType(block); 1469 value = readRegister(register, pred, edgeType, type, local); 1470 } else { 1471 Phi phi = new Phi(valueNumberGenerator.next(), block, type, local); 1472 // We need to write the phi before adding operands to break cycles. If the phi is trivial 1473 // and is removed by addOperands, the definition is overwritten and looked up again below. 1474 block.updateCurrentDefinition(register, phi, readingEdge); 1475 phi.addOperands(this, register); 1476 // Lookup the value for the register again at this point. Recursive trivial 1477 // phi removal could have simplified what we wanted to return here. 1478 value = block.readCurrentDefinition(register, readingEdge); 1479 } 1480 block.updateCurrentDefinition(register, value, readingEdge); 1481 return value; 1482 } 1483 1484 public Value readNumericRegister(int register, NumericType type) { 1485 return readRegister(register, type.moveTypeFor()); 1486 } 1487 1488 public Value readLiteral(NumericType type, long constant) { 1489 Value value = new Value(valueNumberGenerator.next(), MoveType.fromNumericType(type), null); 1490 add(new ConstNumber(ConstType.fromNumericType(type), value, constant)); 1491 return value; 1492 } 1493 1494 // This special write register is needed when changing the scoping of a local variable. 1495 // See addDebugLocalStart and addDebugLocalEnd. 1496 private Value writeRegister(int register, MoveType type, ThrowingInfo throwing, DebugInfo info) { 1497 checkRegister(register); 1498 Value value = new Value(valueNumberGenerator.next(), type, info); 1499 currentBlock.writeCurrentDefinition(register, value, throwing); 1500 return value; 1501 } 1502 1503 public Value writeRegister(int register, MoveType type, ThrowingInfo throwing) { 1504 DebugLocalInfo local = getCurrentLocal(register); 1505 DebugInfo info = null; 1506 if (local != null) { 1507 Value previousLocal = readRegisterIgnoreLocal(register, type); 1508 info = new DebugInfo(local, previousLocal.getLocalInfo() != local ? null : previousLocal); 1509 } 1510 return writeRegister(register, type, throwing, info); 1511 } 1512 1513 public Value writeNumericRegister(int register, NumericType type, ThrowingInfo throwing) { 1514 return writeRegister(register, type.moveTypeFor(), throwing); 1515 } 1516 1517 private DebugLocalInfo getCurrentLocal(int register) { 1518 return options.debug ? source.getCurrentLocal(register) : null; 1519 } 1520 1521 private void checkRegister(int register) { 1522 if (register < 0) { 1523 throw new InternalCompilerError("Invalid register"); 1524 } 1525 if (!source.verifyRegister(register)) { 1526 throw new CompilationError("Invalid use of register " + register); 1527 } 1528 } 1529 1530 /** 1531 * Ensure that the current block can hold a throwing instruction. This will create a new current 1532 * block if the current block has handlers and already has one throwing instruction. 1533 */ 1534 void ensureBlockForThrowingInstruction() { 1535 if (!throwingInstructionInCurrentBlock) { 1536 return; 1537 } 1538 BasicBlock block = new BasicBlock(); 1539 block.setNumber(nextBlockNumber++); 1540 blocks.add(block); 1541 block.incrementUnfilledPredecessorCount(); 1542 int freshOffset = INITIAL_BLOCK_OFFSET - 1; 1543 while (targets.containsKey(freshOffset)) { 1544 freshOffset--; 1545 } 1546 targets.put(freshOffset, null); 1547 for (int offset : source.getCurrentCatchHandlers().getUniqueTargets()) { 1548 BlockInfo target = targets.get(offset); 1549 assert !target.block.isSealed(); 1550 target.block.incrementUnfilledPredecessorCount(); 1551 target.addExceptionalPredecessor(freshOffset); 1552 } 1553 addInstruction(new Goto()); 1554 currentBlock.link(block); 1555 closeCurrentBlock(); 1556 setCurrentBlock(block); 1557 } 1558 1559 // Private instruction helpers. 1560 private void addInstruction(Instruction ir) { 1561 attachLocalChanges(ir); 1562 if (currentDebugPosition != null && !ir.isMoveException()) { 1563 flushCurrentDebugPosition(); 1564 } 1565 currentBlock.add(ir); 1566 if (ir.instructionTypeCanThrow()) { 1567 assert source.verifyCurrentInstructionCanThrow(); 1568 CatchHandlers<Integer> catchHandlers = source.getCurrentCatchHandlers(); 1569 if (catchHandlers != null) { 1570 assert !throwingInstructionInCurrentBlock; 1571 throwingInstructionInCurrentBlock = true; 1572 List<BasicBlock> targets = new ArrayList<>(catchHandlers.getAllTargets().size()); 1573 for (int targetOffset : catchHandlers.getAllTargets()) { 1574 BasicBlock target = getTarget(targetOffset); 1575 addToWorklist(target, source.instructionIndex(targetOffset)); 1576 targets.add(target); 1577 } 1578 currentBlock.linkCatchSuccessors(catchHandlers.getGuards(), targets); 1579 } 1580 } 1581 if (currentDebugPosition != null) { 1582 assert ir.isMoveException(); 1583 flushCurrentDebugPosition(); 1584 } 1585 } 1586 1587 private void attachLocalChanges(Instruction ir) { 1588 if (!options.debug) { 1589 return; 1590 } 1591 if (debugLocalStarts.isEmpty() && debugLocalReads.isEmpty() && debugLocalEnds.isEmpty()) { 1592 return; 1593 } 1594 for (Value debugLocalStart : debugLocalStarts) { 1595 ir.addDebugValue(debugLocalStart); 1596 debugLocalStart.addDebugLocalStart(ir); 1597 } 1598 for (Value debugLocalRead : debugLocalReads) { 1599 ir.addDebugValue(debugLocalRead); 1600 } 1601 for (Value debugLocalEnd : debugLocalEnds) { 1602 ir.addDebugValue(debugLocalEnd); 1603 debugLocalEnd.addDebugLocalEnd(ir); 1604 } 1605 debugLocalStarts.clear(); 1606 debugLocalReads.clear(); 1607 debugLocalEnds.clear(); 1608 } 1609 1610 // Package (ie, SourceCode accessed) helpers. 1611 1612 // Ensure there is a block starting at offset. 1613 BlockInfo ensureBlockWithoutEnqueuing(int offset) { 1614 assert offset != INITIAL_BLOCK_OFFSET; 1615 BlockInfo info = targets.get(offset); 1616 if (info == null) { 1617 // If this is a processed instruction, the block split and it has a fall-through predecessor. 1618 if (offset >= 0 && isOffsetProcessed(offset)) { 1619 int blockStartOffset = getBlockStartOffset(offset); 1620 BlockInfo existing = targets.get(blockStartOffset); 1621 info = existing.split(blockStartOffset, offset, targets); 1622 } else { 1623 info = new BlockInfo(); 1624 } 1625 targets.put(offset, info); 1626 } 1627 return info; 1628 } 1629 1630 private int getBlockStartOffset(int offset) { 1631 if (targets.containsKey(offset)) { 1632 return offset; 1633 } 1634 return targets.headMap(offset).lastIntKey(); 1635 } 1636 1637 // Ensure there is a block starting at offset and add it to the work-list if it needs processing. 1638 private BlockInfo ensureBlock(int offset) { 1639 // We don't enqueue negative targets (these are special blocks, eg, an argument prelude). 1640 if (offset >= 0 && !isOffsetProcessed(offset)) { 1641 traceBlocksWorklist.add(offset); 1642 } 1643 return ensureBlockWithoutEnqueuing(offset); 1644 } 1645 1646 private boolean isOffsetProcessed(int offset) { 1647 return isIndexProcessed(source.instructionIndex(offset)); 1648 } 1649 1650 private boolean isIndexProcessed(int index) { 1651 if (index < processedInstructions.length) { 1652 return processedInstructions[index]; 1653 } 1654 ensureSubroutineProcessedInstructions(); 1655 return processedSubroutineInstructions.contains(index); 1656 } 1657 1658 private void markIndexProcessed(int index) { 1659 assert !isIndexProcessed(index); 1660 if (index < processedInstructions.length) { 1661 processedInstructions[index] = true; 1662 return; 1663 } 1664 ensureSubroutineProcessedInstructions(); 1665 processedSubroutineInstructions.add(index); 1666 } 1667 1668 private void ensureSubroutineProcessedInstructions() { 1669 if (processedSubroutineInstructions == null) { 1670 processedSubroutineInstructions = new HashSet<>(); 1671 } 1672 } 1673 1674 // Ensure there is a block at offset and add a predecessor to it. 1675 private void ensureSuccessorBlock(int sourceOffset, int targetOffset, boolean normal) { 1676 BlockInfo targetInfo = ensureBlock(targetOffset); 1677 int sourceStartOffset = getBlockStartOffset(sourceOffset); 1678 BlockInfo sourceInfo = targets.get(sourceStartOffset); 1679 if (normal) { 1680 sourceInfo.addNormalSuccessor(targetOffset); 1681 targetInfo.addNormalPredecessor(sourceStartOffset); 1682 } else { 1683 sourceInfo.addExceptionalSuccessor(targetOffset); 1684 targetInfo.addExceptionalPredecessor(sourceStartOffset); 1685 } 1686 targetInfo.block.incrementUnfilledPredecessorCount(); 1687 } 1688 1689 void ensureNormalSuccessorBlock(int sourceOffset, int targetOffset) { 1690 ensureSuccessorBlock(sourceOffset, targetOffset, true); 1691 } 1692 1693 void ensureExceptionalSuccessorBlock(int sourceOffset, int targetOffset) { 1694 ensureSuccessorBlock(sourceOffset, targetOffset, false); 1695 } 1696 1697 // Private block helpers. 1698 1699 private BasicBlock getTarget(int offset) { 1700 return targets.get(offset).block; 1701 } 1702 1703 private void closeCurrentBlock() { 1704 // TODO(zerny): To ensure liveness of locals throughout the entire block, we might want to 1705 // insert reads before closing the block. It is unclear if we can rely on a local-end to ensure 1706 // liveness in all blocks where the local should be live. 1707 assert currentBlock != null; 1708 assert currentDebugPosition == null; 1709 currentBlock.close(this); 1710 setCurrentBlock(null); 1711 throwingInstructionInCurrentBlock = false; 1712 } 1713 1714 private void closeCurrentBlockWithFallThrough(BasicBlock nextBlock) { 1715 assert currentBlock != null; 1716 addInstruction(new Goto()); 1717 if (currentBlock.hasCatchSuccessor(nextBlock)) { 1718 needGotoToCatchBlocks.add(new BasicBlock.Pair(currentBlock, nextBlock)); 1719 } else { 1720 currentBlock.link(nextBlock); 1721 } 1722 closeCurrentBlock(); 1723 } 1724 1725 void handleExitBlock() { 1726 if (exitBlocks.size() > 0) { 1727 // Create and populate the exit block if needed (eg, synchronized support for jar). 1728 setCurrentBlock(new BasicBlock()); 1729 source.buildPostlude(this); 1730 // If the new exit block is empty and we only have one exit, abort building a new exit block. 1731 if (currentBlock.getInstructions().isEmpty() && exitBlocks.size() == 1) { 1732 normalExitBlock = exitBlocks.get(0); 1733 setCurrentBlock(null); 1734 return; 1735 } 1736 // Commit to creating the new exit block. 1737 normalExitBlock = currentBlock; 1738 normalExitBlock.setNumber(nextBlockNumber++); 1739 blocks.add(normalExitBlock); 1740 // Add the return instruction possibly creating a phi of return values. 1741 Return origReturn = exitBlocks.get(0).exit().asReturn(); 1742 Phi phi = null; 1743 if (origReturn.isReturnVoid()) { 1744 normalExitBlock.add(new Return()); 1745 } else { 1746 Value returnValue = origReturn.returnValue(); 1747 MoveType returnType = origReturn.getReturnType(); 1748 assert origReturn.getLocalInfo() == null; 1749 phi = new Phi( 1750 valueNumberGenerator.next(), normalExitBlock, returnValue.outType(), null); 1751 normalExitBlock.add(new Return(phi, returnType)); 1752 assert returnType == MoveType.fromDexType(method.method.proto.returnType); 1753 } 1754 closeCurrentBlock(); 1755 // Replace each return instruction with a goto to the new exit block. 1756 List<Value> operands = new ArrayList<>(); 1757 for (BasicBlock block : exitBlocks) { 1758 List<Instruction> instructions = block.getInstructions(); 1759 Return ret = block.exit().asReturn(); 1760 if (!ret.isReturnVoid()) { 1761 operands.add(ret.returnValue()); 1762 ret.returnValue().removeUser(ret); 1763 } 1764 Goto gotoExit = new Goto(); 1765 gotoExit.setBlock(block); 1766 if (options.debug) { 1767 for (Value value : ret.getDebugValues()) { 1768 gotoExit.addDebugValue(value); 1769 value.removeDebugUser(ret); 1770 } 1771 } 1772 instructions.set(instructions.size() - 1, gotoExit); 1773 block.link(normalExitBlock); 1774 gotoExit.setTarget(normalExitBlock); 1775 } 1776 if (phi != null) { 1777 phi.addOperands(operands); 1778 } 1779 } 1780 } 1781 1782 private void handleFallthroughToCatchBlock() { 1783 // When a catch handler for a block goes to the same block as the fallthrough for that 1784 // block the graph only has one edge there. In these cases we add an additional block so the 1785 // catch edge goes through that and then make the fallthrough go through a new direct edge. 1786 for (BasicBlock.Pair pair : needGotoToCatchBlocks) { 1787 BasicBlock source = pair.first; 1788 BasicBlock target = pair.second; 1789 1790 // New block with one unfilled predecessor. 1791 BasicBlock newBlock = BasicBlock.createGotoBlock(target, nextBlockNumber++); 1792 blocks.add(newBlock); 1793 newBlock.incrementUnfilledPredecessorCount(); 1794 1795 // Link blocks. 1796 source.replaceSuccessor(target, newBlock); 1797 newBlock.getPredecessors().add(source); 1798 source.getSuccessors().add(target); 1799 target.getPredecessors().add(newBlock); 1800 1801 // Check that the successor indexes are correct. 1802 assert source.hasCatchSuccessor(newBlock); 1803 assert !source.hasCatchSuccessor(target); 1804 1805 // Mark the filled predecessors to the blocks. 1806 if (source.isFilled()) { 1807 newBlock.filledPredecessor(this); 1808 } 1809 target.filledPredecessor(this); 1810 } 1811 } 1812 1813 /** 1814 * Change to control-flow graph to avoid repeated phi operands when all the same values 1815 * flow in from multiple predecessors. 1816 * 1817 * <p> As an example: 1818 * 1819 * <pre> 1820 * 1821 * b1 b2 b3 1822 * | | 1823 * ----------\ | /---------- 1824 * 1825 * b4 1826 * v3 = phi(v1, v1, v2) 1827 * </pre> 1828 * 1829 * <p> Is rewritten to: 1830 * 1831 * <pre> 1832 * b1 b2 b3 1833 * \ / / 1834 * b5 ------- 1835 * \ / 1836 * b4 1837 * v3 = phi(v1, v2) 1838 * 1839 * </pre> 1840 */ 1841 public void joinPredecessorsWithIdenticalPhis() { 1842 List<BasicBlock> blocksToAdd = new ArrayList<>(); 1843 for (BasicBlock block : blocks) { 1844 // Consistency check. At this point there should be no incomplete phis. 1845 // If there are, the input is typically dex code that uses a register 1846 // that is not defined on all control-flow paths. 1847 if (block.hasIncompletePhis()) { 1848 throw new CompilationError( 1849 "Undefined value encountered during compilation. " 1850 + "This is typically caused by invalid dex input that uses a register " 1851 + "that is not define on all control-flow paths leading to the use."); 1852 } 1853 if (block.entry() instanceof MoveException) { 1854 // TODO: Should we support joining in the presence of move-exception instructions? 1855 continue; 1856 } 1857 List<Integer> operandsToRemove = new ArrayList<>(); 1858 Map<ValueList, Integer> values = new HashMap<>(); 1859 Map<Integer, BasicBlock> joinBlocks = new HashMap<>(); 1860 if (block.getPhis().size() > 0) { 1861 Phi phi = block.getPhis().get(0); 1862 for (int operandIndex = 0; operandIndex < phi.getOperands().size(); operandIndex++) { 1863 ValueList v = ValueList.fromPhis(block.getPhis(), operandIndex); 1864 BasicBlock predecessor = block.getPredecessors().get(operandIndex); 1865 if (values.containsKey(v)) { 1866 // Seen before, create a join block (or reuse an existing join block) to join through. 1867 int otherPredecessorIndex = values.get(v); 1868 BasicBlock joinBlock = joinBlocks.get(otherPredecessorIndex); 1869 if (joinBlock == null) { 1870 joinBlock = BasicBlock.createGotoBlock(block, blocks.size() + blocksToAdd.size()); 1871 joinBlocks.put(otherPredecessorIndex, joinBlock); 1872 blocksToAdd.add(joinBlock); 1873 BasicBlock otherPredecessor = block.getPredecessors().get(otherPredecessorIndex); 1874 joinBlock.getPredecessors().add(otherPredecessor); 1875 otherPredecessor.replaceSuccessor(block, joinBlock); 1876 block.getPredecessors().set(otherPredecessorIndex, joinBlock); 1877 } 1878 joinBlock.getPredecessors().add(predecessor); 1879 predecessor.replaceSuccessor(block, joinBlock); 1880 operandsToRemove.add(operandIndex); 1881 } else { 1882 // Record the value and its predecessor index. 1883 values.put(v, operandIndex); 1884 } 1885 } 1886 } 1887 block.removePredecessorsByIndex(operandsToRemove); 1888 block.removePhisByIndex(operandsToRemove); 1889 } 1890 blocks.addAll(blocksToAdd); 1891 } 1892 1893 private void splitCriticalEdges() { 1894 List<BasicBlock> newBlocks = new ArrayList<>(); 1895 for (BasicBlock block : blocks) { 1896 // We are using a spilling register allocator that might need to insert moves at 1897 // all critical edges, so we always split them all. 1898 List<BasicBlock> predecessors = block.getPredecessors(); 1899 if (predecessors.size() <= 1) { 1900 continue; 1901 } 1902 // If any of the edges to the block are critical, we need to insert new blocks on each 1903 // containing the move-exception instruction which must remain the first instruction. 1904 if (block.entry() instanceof MoveException) { 1905 block.splitCriticalExceptionEdges(valueNumberGenerator, 1906 newBlock -> { 1907 newBlock.setNumber(blocks.size() + newBlocks.size()); 1908 newBlocks.add(newBlock); 1909 }); 1910 continue; 1911 } 1912 for (int predIndex = 0; predIndex < predecessors.size(); predIndex++) { 1913 BasicBlock pred = predecessors.get(predIndex); 1914 if (!pred.hasOneNormalExit()) { 1915 // Critical edge: split it and inject a new block into which the 1916 // phi moves can be inserted. The new block is created with the 1917 // correct predecessor and successor structure. It is inserted 1918 // at the end of the list of blocks disregarding branching 1919 // structure. 1920 int blockNumber = blocks.size() + newBlocks.size(); 1921 BasicBlock newBlock = BasicBlock.createGotoBlock(block, blockNumber); 1922 newBlocks.add(newBlock); 1923 pred.replaceSuccessor(block, newBlock); 1924 newBlock.getPredecessors().add(pred); 1925 predecessors.set(predIndex, newBlock); 1926 } 1927 } 1928 } 1929 blocks.addAll(newBlocks); 1930 } 1931 1932 /** 1933 * Trace blocks and attempt to put fallthrough blocks immediately after the block that 1934 * falls through. When we fail to do that we create a new fallthrough block with an explicit 1935 * goto to the actual fallthrough block. 1936 */ 1937 private void traceBlocks(IRCode code) { 1938 BasicBlock[] sorted = code.topologicallySortedBlocks(); 1939 code.clearMarks(); 1940 int nextBlockNumber = blocks.size(); 1941 LinkedList<BasicBlock> tracedBlocks = new LinkedList<>(); 1942 for (BasicBlock block : sorted) { 1943 if (!block.isMarked()) { 1944 block.mark(); 1945 tracedBlocks.add(block); 1946 BasicBlock current = block; 1947 BasicBlock fallthrough = block.exit().fallthroughBlock(); 1948 while (fallthrough != null && !fallthrough.isMarked()) { 1949 fallthrough.mark(); 1950 tracedBlocks.add(fallthrough); 1951 current = fallthrough; 1952 fallthrough = fallthrough.exit().fallthroughBlock(); 1953 } 1954 if (fallthrough != null) { 1955 BasicBlock newFallthrough = BasicBlock.createGotoBlock(fallthrough, nextBlockNumber++); 1956 current.exit().setFallthroughBlock(newFallthrough); 1957 newFallthrough.getPredecessors().add(current); 1958 fallthrough.replacePredecessor(current, newFallthrough); 1959 newFallthrough.mark(); 1960 tracedBlocks.add(newFallthrough); 1961 } 1962 } 1963 } 1964 code.blocks = tracedBlocks; 1965 } 1966 1967 // Debug info helpers. 1968 1969 public void updateCurrentDebugPosition(int line, DexString file) { 1970 // Stack-trace support requires position information in both debug and release mode. 1971 flushCurrentDebugPosition(); 1972 currentDebugPosition = new DebugPosition(line, file); 1973 attachLocalChanges(currentDebugPosition); 1974 } 1975 1976 private void flushCurrentDebugPosition() { 1977 if (currentDebugPosition != null) { 1978 DebugPosition position = currentDebugPosition; 1979 currentDebugPosition = null; 1980 addInstruction(position); 1981 } 1982 } 1983 1984 // Other stuff. 1985 1986 boolean isIntegerType(NumericType type) { 1987 return type != NumericType.FLOAT && type != NumericType.DOUBLE; 1988 } 1989 1990 boolean isNonLongIntegerType(NumericType type) { 1991 return type != NumericType.FLOAT && type != NumericType.DOUBLE && type != NumericType.LONG; 1992 } 1993 1994 @Override 1995 public String toString() { 1996 StringBuilder builder = new StringBuilder(); 1997 builder.append(("blocks:\n")); 1998 for (BasicBlock block : blocks) { 1999 builder.append(block.toDetailedString()); 2000 builder.append("\n"); 2001 } 2002 return builder.toString(); 2003 } 2004 } 2005