• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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.dex.Constants;
7 import com.android.tools.r8.errors.Unreachable;
8 import com.android.tools.r8.graph.DebugLocalInfo;
9 import com.android.tools.r8.graph.Descriptor;
10 import com.android.tools.r8.graph.DexCallSite;
11 import com.android.tools.r8.graph.DexField;
12 import com.android.tools.r8.graph.DexItem;
13 import com.android.tools.r8.graph.DexItemFactory;
14 import com.android.tools.r8.graph.DexMethod;
15 import com.android.tools.r8.graph.DexMethodHandle;
16 import com.android.tools.r8.graph.DexMethodHandle.MethodHandleType;
17 import com.android.tools.r8.graph.DexProto;
18 import com.android.tools.r8.graph.DexType;
19 import com.android.tools.r8.graph.DexValue;
20 import com.android.tools.r8.graph.JarApplicationReader;
21 import com.android.tools.r8.ir.code.CatchHandlers;
22 import com.android.tools.r8.ir.code.Cmp.Bias;
23 import com.android.tools.r8.ir.code.ConstType;
24 import com.android.tools.r8.ir.code.If;
25 import com.android.tools.r8.ir.code.Invoke;
26 import com.android.tools.r8.ir.code.MemberType;
27 import com.android.tools.r8.ir.code.Monitor;
28 import com.android.tools.r8.ir.code.MoveType;
29 import com.android.tools.r8.ir.code.NumericType;
30 import com.android.tools.r8.ir.conversion.IRBuilder.BlockInfo;
31 import com.android.tools.r8.ir.conversion.JarState.Local;
32 import com.android.tools.r8.ir.conversion.JarState.Slot;
33 import com.android.tools.r8.logging.Log;
34 import it.unimi.dsi.fastutil.ints.Int2ReferenceSortedMap;
35 import java.io.PrintWriter;
36 import java.io.StringWriter;
37 import java.util.ArrayList;
38 import java.util.Arrays;
39 import java.util.HashMap;
40 import java.util.HashSet;
41 import java.util.LinkedList;
42 import java.util.List;
43 import java.util.Map;
44 import java.util.Queue;
45 import java.util.Set;
46 import java.util.function.BiConsumer;
47 import org.objectweb.asm.Handle;
48 import org.objectweb.asm.Opcodes;
49 import org.objectweb.asm.Type;
50 import org.objectweb.asm.tree.AbstractInsnNode;
51 import org.objectweb.asm.tree.FieldInsnNode;
52 import org.objectweb.asm.tree.IincInsnNode;
53 import org.objectweb.asm.tree.InsnNode;
54 import org.objectweb.asm.tree.IntInsnNode;
55 import org.objectweb.asm.tree.InvokeDynamicInsnNode;
56 import org.objectweb.asm.tree.JumpInsnNode;
57 import org.objectweb.asm.tree.LabelNode;
58 import org.objectweb.asm.tree.LdcInsnNode;
59 import org.objectweb.asm.tree.LineNumberNode;
60 import org.objectweb.asm.tree.LocalVariableNode;
61 import org.objectweb.asm.tree.LookupSwitchInsnNode;
62 import org.objectweb.asm.tree.MethodInsnNode;
63 import org.objectweb.asm.tree.MethodNode;
64 import org.objectweb.asm.tree.MultiANewArrayInsnNode;
65 import org.objectweb.asm.tree.TableSwitchInsnNode;
66 import org.objectweb.asm.tree.TryCatchBlockNode;
67 import org.objectweb.asm.tree.TypeInsnNode;
68 import org.objectweb.asm.tree.VarInsnNode;
69 import org.objectweb.asm.util.Textifier;
70 import org.objectweb.asm.util.TraceMethodVisitor;
71 
72 public class JarSourceCode implements SourceCode {
73 
74   // Try-catch block wrapper containing resolved offsets.
75   private static class TryCatchBlock {
76 
77     private final int handler;
78     private final int start;
79     private final int end;
80 
81     private final String type;
82 
TryCatchBlock(TryCatchBlockNode node, JarSourceCode code)83     public TryCatchBlock(TryCatchBlockNode node, JarSourceCode code) {
84       this(code.getOffset(node.handler),
85           code.getOffset(node.start),
86           code.getOffset(node.end),
87           node.type);
88     }
89 
TryCatchBlock(int handler, int start, int end, String type)90     private TryCatchBlock(int handler, int start, int end, String type) {
91       assert start < end;
92       this.handler = handler;
93       this.start = start;
94       this.end = end;
95       this.type = type;
96     }
97 
98     int getStart() {
99       return start;
100     }
101 
102     int getEnd() {
103       return end;
104     }
105 
106     int getHandler() {
107       return handler;
108     }
109 
110     String getType() {
111       return type;
112     }
113   }
114 
115   private static class JarStateWorklistItem {
116     BlockInfo blockInfo;
117     int instructionIndex;
118 
119     public JarStateWorklistItem(BlockInfo blockInfo, int instructionIndex) {
120       this.blockInfo = blockInfo;
121       this.instructionIndex = instructionIndex;
122     }
123   }
124 
125   // Various descriptors.
126   private static final String INT_ARRAY_DESC = "[I";
127   private static final String REFLECT_ARRAY_DESC = "Ljava/lang/reflect/Array;";
128   private static final String REFLECT_ARRAY_NEW_INSTANCE_NAME = "newInstance";
129   private static final String REFLECT_ARRAY_NEW_INSTANCE_DESC =
130       "(Ljava/lang/Class;[I)Ljava/lang/Object;";
131   private static final String METHODHANDLE_INVOKE_OR_INVOKEEXACT_DESC =
132       "([Ljava/lang/Object;)Ljava/lang/Object;";
133 
134   // Language types.
135   private static final Type CLASS_TYPE = Type.getObjectType("java/lang/Class");
136   private static final Type STRING_TYPE = Type.getObjectType("java/lang/String");
137   private static final Type INT_ARRAY_TYPE = Type.getObjectType(INT_ARRAY_DESC);
138   private static final Type THROWABLE_TYPE = Type.getObjectType("java/lang/Throwable");
139 
140   private static final int[] NO_TARGETS = {};
141 
142   private final JarApplicationReader application;
143   private final MethodNode node;
144   private final DexType clazz;
145   private final List<Type> parameterTypes;
146   private final LabelNode initialLabel;
147 
148   private TraceMethodVisitor printVisitor = null;
149 
150   private final JarState state;
151   private AbstractInsnNode currentInstruction = null;
152 
153   // Special try-catch block for synchronized methods.
154   // This block is given a negative instruction index as it is not part of the instruction stream.
155   // The start range of 0 ensures that a new block will start at the first real instruction and
156   // thus that the monitor-entry prelude (part of the argument block which must not have a try-catch
157   // successor) is not joined with the first instruction block (which likely will have a try-catch
158   // successor).
159   private static final int EXCEPTIONAL_SYNC_EXIT_OFFSET = -2;
160   private static final TryCatchBlock EXCEPTIONAL_SYNC_EXIT =
161       new TryCatchBlock(EXCEPTIONAL_SYNC_EXIT_OFFSET, 0, Integer.MAX_VALUE, null);
162 
163   // Instruction that enters the monitor. Null if the method is not synchronized.
164   private Monitor monitorEnter = null;
165 
166   // State to signal that the code currently being emitted is part of synchronization prelude/exits.
167   private boolean generatingMethodSynchronization = false;
168 
169   public JarSourceCode(DexType clazz, MethodNode node, JarApplicationReader application) {
170     assert node != null;
171     assert node.desc != null;
172     this.node = node;
173     this.application = application;
174     this.clazz = clazz;
175     parameterTypes = Arrays.asList(Type.getArgumentTypes(node.desc));
176     state = new JarState(node.maxLocals, computeLocals(node.localVariables, application));
177     AbstractInsnNode first = node.instructions.getFirst();
178     initialLabel = first instanceof LabelNode ? (LabelNode) first : null;
179   }
180 
181   private static Map<LocalVariableNode, DebugLocalInfo> computeLocals(
182       List localNodes, JarApplicationReader application) {
183     Map<DebugLocalInfo, DebugLocalInfo> canonical = new HashMap<>(localNodes.size());
184     Map<LocalVariableNode, DebugLocalInfo> localVariables = new HashMap<>(localNodes.size());
185     for (Object o : localNodes) {
186       LocalVariableNode node = (LocalVariableNode) o;
187       localVariables.computeIfAbsent(node, n -> canonicalizeLocal(n, canonical, application));
188     }
189     return localVariables;
190   }
191 
canonicalizeLocal( LocalVariableNode node, Map<DebugLocalInfo, DebugLocalInfo> canonicalLocalVariables, JarApplicationReader application)192   private static DebugLocalInfo canonicalizeLocal(
193       LocalVariableNode node,
194       Map<DebugLocalInfo, DebugLocalInfo> canonicalLocalVariables,
195       JarApplicationReader application) {
196     DebugLocalInfo info = new DebugLocalInfo(
197         application.getString(node.name),
198         application.getType(Type.getType(node.desc)),
199         node.signature == null ? null : application.getString(node.signature));
200     DebugLocalInfo canonical = canonicalLocalVariables.putIfAbsent(info, info);
201     return canonical != null ? canonical : info;
202   }
203 
isStatic()204   private boolean isStatic() {
205     return (node.access & Opcodes.ACC_STATIC) > 0;
206   }
207 
isSynchronized()208   private boolean isSynchronized() {
209     return (node.access & Opcodes.ACC_SYNCHRONIZED) > 0;
210   }
211 
formalParameterCount()212   private int formalParameterCount() {
213     return parameterTypes.size();
214   }
215 
actualArgumentCount()216   private int actualArgumentCount() {
217     return isStatic() ? formalParameterCount() : formalParameterCount() + 1;
218   }
219 
220   @Override
instructionCount()221   public int instructionCount() {
222     return node.instructions.size();
223   }
224 
225   @Override
instructionIndex(int instructionOffset)226   public int instructionIndex(int instructionOffset) {
227     return instructionOffset;
228   }
229 
230   @Override
instructionOffset(int instructionIndex)231   public int instructionOffset(int instructionIndex) {
232     return instructionIndex;
233   }
234 
235   @Override
verifyRegister(int register)236   public boolean verifyRegister(int register) {
237     // The register set is dynamically managed by the state so we assume all values valid here.
238     return true;
239   }
240 
241   @Override
setUp()242   public void setUp() {
243     if (Log.ENABLED) {
244       Log.debug(JarSourceCode.class, "Computing blocks for:\n" + toString());
245     }
246   }
247 
248   @Override
clear()249   public void clear() {
250 
251   }
252 
253   @Override
needsPrelude()254   public boolean needsPrelude() {
255     return isSynchronized() || actualArgumentCount() > 0 || !node.localVariables.isEmpty();
256   }
257 
258   @Override
buildPrelude(IRBuilder builder)259   public void buildPrelude(IRBuilder builder) {
260     Map<Integer, MoveType> initializedLocals = new HashMap<>(node.localVariables.size());
261     if (initialLabel != null) {
262       state.openLocals(initialLabel);
263     }
264     int argumentRegister = 0;
265     if (!isStatic()) {
266       Type thisType = Type.getType(clazz.descriptor.toString());
267       int register = state.writeLocal(argumentRegister++, thisType);
268       builder.addThisArgument(register);
269       initializedLocals.put(register, moveType(thisType));
270     }
271     for (Type type : parameterTypes) {
272       MoveType moveType = moveType(type);
273       int register = state.writeLocal(argumentRegister, type);
274       builder.addNonThisArgument(register, moveType);
275       argumentRegister += moveType.requiredRegisters();
276       initializedLocals.put(register, moveType);
277     }
278     if (isSynchronized()) {
279       generatingMethodSynchronization = true;
280       Type clazzType = Type.getType(clazz.toDescriptorString());
281       int monitorRegister;
282       if (isStatic()) {
283         // Load the class using a temporary on the stack.
284         monitorRegister = state.push(clazzType);
285         state.pop();
286         builder.addConstClass(monitorRegister, clazz);
287       } else {
288         assert actualArgumentCount() > 0;
289         // The object is stored in the first local.
290         monitorRegister = state.readLocal(0, clazzType).register;
291       }
292       // Build the monitor enter and save it for when generating exits later.
293       monitorEnter = builder.addMonitor(Monitor.Type.ENTER, monitorRegister);
294       generatingMethodSynchronization = false;
295     }
296     // Initialize all non-argument locals to ensure safe insertion of debug-local instructions.
297     for (Object o : node.localVariables) {
298       LocalVariableNode local = (LocalVariableNode) o;
299       Type localType = Type.getType(local.desc);
300       int localRegister = state.getLocalRegister(local.index, localType);
301       MoveType exitingLocalType = initializedLocals.get(localRegister);
302       assert exitingLocalType == null || exitingLocalType == moveType(localType);
303       if (exitingLocalType == null) {
304         int localRegister2 = state.writeLocal(local.index, localType);
305         assert localRegister == localRegister2;
306         initializedLocals.put(localRegister, moveType(localType));
307         builder.addDebugUninitialized(localRegister, constType(localType));
308       }
309     }
310     computeBlockEntryJarStates(builder);
311   }
312 
computeBlockEntryJarStates(IRBuilder builder)313   private void computeBlockEntryJarStates(IRBuilder builder) {
314     Int2ReferenceSortedMap<BlockInfo> CFG = builder.getCFG();
315     Queue<JarStateWorklistItem> worklist = new LinkedList<>();
316     BlockInfo entry = CFG.get(IRBuilder.INITIAL_BLOCK_OFFSET);
317     if (CFG.get(0) != null) {
318       entry = CFG.get(0);
319     }
320     worklist.add(new JarStateWorklistItem(entry, 0));
321     state.recordStateForTarget(0, this);
322     for (JarStateWorklistItem item = worklist.poll(); item != null; item = worklist.poll()) {
323       state.restoreState(item.instructionIndex);
324       // If the block being restored is a try-catch handler push the exception on the stack.
325       for (int i = 0; i < node.tryCatchBlocks.size(); i++) {
326         TryCatchBlockNode tryCatchBlockNode = (TryCatchBlockNode) node.tryCatchBlocks.get(i);
327         if (tryCatchBlockNode.handler == getInstruction(item.instructionIndex)) {
328           state.push(THROWABLE_TYPE);
329           break;
330         }
331       }
332       // Iterate each of the instructions in the block to compute the outgoing JarState.
333       for (int i = item.instructionIndex; i <= instructionCount(); ++i) {
334         // If we are at the end of the instruction stream or if we have reached the start
335         // of a new block, propagate the state to all successors and add the ones
336         // that changed to the worklist.
337         if (i == instructionCount() || (i != item.instructionIndex && CFG.containsKey(i))) {
338           item.blockInfo.normalSuccessors.iterator().forEachRemaining(offset -> {
339             if (state.recordStateForTarget(offset, this)) {
340               if (offset >= 0) {
341                 worklist.add(new JarStateWorklistItem(CFG.get(offset.intValue()), offset));
342               }
343             }
344           });
345           item.blockInfo.exceptionalSuccessors.iterator().forEachRemaining(offset -> {
346             if (state.recordStateForExceptionalTarget(offset, this)) {
347               if (offset >= 0) {
348                 worklist.add(new JarStateWorklistItem(CFG.get(offset.intValue()), offset));
349               }
350             }
351           });
352           break;
353         }
354 
355         AbstractInsnNode insn = getInstruction(i);
356         updateState(insn);
357 
358         if (!isControlFlowInstruction(insn)) {
359           updateStateForLocalVariableEnd(insn);
360         }
361       }
362     }
363   }
364 
updateStateForLocalVariableEnd(AbstractInsnNode insn)365   private void updateStateForLocalVariableEnd(AbstractInsnNode insn) {
366     assert !isControlFlowInstruction(insn);
367     if (!(insn.getNext() instanceof LabelNode)) {
368       return;
369     }
370     // If the label is the end of any local-variable scopes end the locals.
371     LabelNode label = (LabelNode) insn.getNext();
372     List<Local> locals = state.getLocalsToClose(label);
373     state.closeLocals(locals);
374   }
375 
376   @Override
buildPostlude(IRBuilder builder)377   public void buildPostlude(IRBuilder builder) {
378     if (isSynchronized()) {
379       generatingMethodSynchronization = true;
380       buildMonitorExit(builder);
381       generatingMethodSynchronization = false;
382     }
383   }
384 
buildExceptionalPostlude(IRBuilder builder)385   private void buildExceptionalPostlude(IRBuilder builder) {
386     assert isSynchronized();
387     generatingMethodSynchronization = true;
388     int exceptionRegister = 0; // We are exiting the method so we just overwrite register 0.
389     builder.addMoveException(exceptionRegister);
390     buildMonitorExit(builder);
391     builder.addThrow(exceptionRegister);
392     generatingMethodSynchronization = false;
393   }
394 
buildMonitorExit(IRBuilder builder)395   private void buildMonitorExit(IRBuilder builder) {
396     assert generatingMethodSynchronization;
397     builder.add(new Monitor(Monitor.Type.EXIT, monitorEnter.inValues().get(0)));
398   }
399 
400   @Override
closedCurrentBlockWithFallthrough(int fallthroughInstructionIndex)401   public void closedCurrentBlockWithFallthrough(int fallthroughInstructionIndex) {
402   }
403 
404   @Override
closedCurrentBlock()405   public void closedCurrentBlock() {
406   }
407 
408   @Override
buildInstruction(IRBuilder builder, int instructionIndex)409   public void buildInstruction(IRBuilder builder, int instructionIndex) {
410     if (instructionIndex == EXCEPTIONAL_SYNC_EXIT_OFFSET) {
411       buildExceptionalPostlude(builder);
412       return;
413     }
414     AbstractInsnNode insn = getInstruction(instructionIndex);
415     currentInstruction = insn;
416     assert verifyExceptionEdgesAreRecorded(insn);
417 
418     // If a new block is starting here, we restore the computed JarState.
419     if (builder.getCFG().containsKey(instructionIndex) || instructionIndex == 0) {
420       state.restoreState(instructionIndex);
421       // If the block being restored is a try-catch handler push the exception on the stack.
422       for (int i = 0; i < node.tryCatchBlocks.size(); i++) {
423         TryCatchBlockNode tryCatchBlockNode = (TryCatchBlockNode) node.tryCatchBlocks.get(i);
424         if (tryCatchBlockNode.handler == insn) {
425           builder.addMoveException(state.push(THROWABLE_TYPE));
426           break;
427         }
428       }
429     }
430 
431     String preInstructionState;
432     if (Log.ENABLED) {
433       preInstructionState = state.toString();
434     }
435 
436     // Process local-variable end scopes if this instruction is not a control-flow instruction.
437     // For control-flow instructions, processing takes place before closing their respective blocks.
438     if (!isControlFlowInstruction(insn)) {
439       processLocalVariableEnd(insn, builder);
440     }
441 
442     build(insn, builder);
443 
444     if (Log.ENABLED && !(insn instanceof LineNumberNode)) {
445       int offset = getOffset(insn);
446       if (insn instanceof LabelNode) {
447         Log.debug(getClass(), "\n%4d: %s",
448             offset, instructionToString(insn).replace('\n', ' '));
449       } else {
450         Log.debug(getClass(), "\n%4d: %s          pre:  %s\n          post: %s",
451             offset, instructionToString(insn), preInstructionState, state);
452       }
453     }
454   }
455 
verifyExceptionEdgesAreRecorded(AbstractInsnNode insn)456   private boolean verifyExceptionEdgesAreRecorded(AbstractInsnNode insn) {
457     if (canThrow(insn)) {
458       for (TryCatchBlock tryCatchBlock : getTryHandlers(insn)) {
459         assert tryCatchBlock.getHandler() == EXCEPTIONAL_SYNC_EXIT_OFFSET
460             || state.hasState(tryCatchBlock.getHandler());
461       }
462     }
463     return true;
464   }
465 
466   @Override
resolveAndBuildSwitch(int value, int fallthroughOffset, int payloadOffset, IRBuilder builder)467   public void resolveAndBuildSwitch(int value, int fallthroughOffset,
468       int payloadOffset, IRBuilder builder) {
469     throw new Unreachable();
470   }
471 
472   @Override
resolveAndBuildNewArrayFilledData(int arrayRef, int payloadOffset, IRBuilder builder)473   public void resolveAndBuildNewArrayFilledData(int arrayRef, int payloadOffset,
474       IRBuilder builder) {
475     throw new Unreachable();
476   }
477 
478   @Override
getCurrentLocal(int register)479   public DebugLocalInfo getCurrentLocal(int register) {
480     return generatingMethodSynchronization ? null : state.getLocalInfoForRegister(register);
481   }
482 
483   @Override
getCurrentCatchHandlers()484   public CatchHandlers<Integer> getCurrentCatchHandlers() {
485     if (generatingMethodSynchronization) {
486       return null;
487     }
488     List<TryCatchBlock> tryCatchBlocks = getTryHandlers(currentInstruction);
489     if (tryCatchBlocks.isEmpty()) {
490       return null;
491     }
492     // TODO(zerny): Compute this more efficiently.
493     return new CatchHandlers<>(
494         getTryHandlerGuards(tryCatchBlocks),
495         getTryHandlerOffsets(tryCatchBlocks));
496   }
497 
498   @Override
verifyCurrentInstructionCanThrow()499   public boolean verifyCurrentInstructionCanThrow() {
500     return generatingMethodSynchronization || canThrow(currentInstruction);
501   }
502 
503   @Override
verifyLocalInScope(DebugLocalInfo local)504   public boolean verifyLocalInScope(DebugLocalInfo local) {
505     for (Local open : state.getLocals()) {
506       if (open.info != null && open.info.name == local.name) {
507         return true;
508       }
509     }
510     return false;
511   }
512 
getInstruction(int index)513   private AbstractInsnNode getInstruction(int index) {
514     return node.instructions.get(index);
515   }
516 
isReturn(AbstractInsnNode insn)517   private static boolean isReturn(AbstractInsnNode insn) {
518     return Opcodes.IRETURN <= insn.getOpcode() && insn.getOpcode() <= Opcodes.RETURN;
519   }
520 
isSwitch(AbstractInsnNode insn)521   private static boolean isSwitch(AbstractInsnNode insn) {
522     return Opcodes.TABLESWITCH == insn.getOpcode() || insn.getOpcode() == Opcodes.LOOKUPSWITCH;
523   }
524 
isThrow(AbstractInsnNode insn)525   private static boolean isThrow(AbstractInsnNode insn) {
526     return Opcodes.ATHROW == insn.getOpcode();
527   }
528 
isControlFlowInstruction(AbstractInsnNode insn)529   private static boolean isControlFlowInstruction(AbstractInsnNode insn) {
530     return isReturn(insn) || isThrow(insn) || isSwitch(insn) || (insn instanceof JumpInsnNode)
531         || insn.getOpcode() == Opcodes.RET;
532   }
533 
canThrow(AbstractInsnNode insn)534   private boolean canThrow(AbstractInsnNode insn) {
535     switch (insn.getOpcode()) {
536       case Opcodes.AALOAD:
537       case Opcodes.AASTORE:
538       case Opcodes.ANEWARRAY:
539         // ARETURN does not throw in its dex image.
540       case Opcodes.ARRAYLENGTH:
541       case Opcodes.ATHROW:
542       case Opcodes.BALOAD:
543       case Opcodes.BASTORE:
544       case Opcodes.CALOAD:
545       case Opcodes.CASTORE:
546       case Opcodes.CHECKCAST:
547       case Opcodes.DALOAD:
548       case Opcodes.DASTORE:
549         // DRETURN does not throw in its dex image.
550       case Opcodes.FALOAD:
551       case Opcodes.FASTORE:
552         // FRETURN does not throw in its dex image.
553       case Opcodes.GETFIELD:
554       case Opcodes.GETSTATIC:
555       case Opcodes.IALOAD:
556       case Opcodes.IASTORE:
557       case Opcodes.IDIV:
558       case Opcodes.INSTANCEOF:
559       case Opcodes.INVOKEDYNAMIC:
560       case Opcodes.INVOKEINTERFACE:
561       case Opcodes.INVOKESPECIAL:
562       case Opcodes.INVOKESTATIC:
563       case Opcodes.INVOKEVIRTUAL:
564       case Opcodes.IREM:
565         // IRETURN does not throw in its dex image.
566       case Opcodes.LALOAD:
567       case Opcodes.LASTORE:
568       case Opcodes.LDIV:
569       case Opcodes.LREM:
570         // LRETURN does not throw in its dex image.
571       case Opcodes.MONITORENTER:
572       case Opcodes.MONITOREXIT:
573       case Opcodes.MULTIANEWARRAY:
574       case Opcodes.NEW:
575       case Opcodes.NEWARRAY:
576       case Opcodes.PUTFIELD:
577       case Opcodes.PUTSTATIC:
578         // RETURN does not throw in its dex image.
579       case Opcodes.SALOAD:
580       case Opcodes.SASTORE:
581         return true;
582       case Opcodes.LDC: {
583         // const-class and const-string* may throw in dex.
584         LdcInsnNode ldc = (LdcInsnNode) insn;
585         return ldc.cst instanceof String || ldc.cst instanceof Type;
586       }
587       default:
588         return false;
589     }
590   }
591 
592   @Override
traceInstruction(int index, IRBuilder builder)593   public int traceInstruction(int index, IRBuilder builder) {
594     AbstractInsnNode insn = getInstruction(index);
595     // Exit early on no-op instructions.
596     if (insn instanceof LabelNode || insn instanceof LineNumberNode) {
597       return -1;
598     }
599     // If this instruction exits, close this block.
600     if (isReturn(insn)) {
601       return index;
602     }
603     // For each target ensure a basic block and close this block.
604     int[] targets = getTargets(insn);
605     if (targets != NO_TARGETS) {
606       assert !canThrow(insn);
607       for (int target : targets) {
608         builder.ensureNormalSuccessorBlock(index, target);
609       }
610       return index;
611     }
612     if (canThrow(insn)) {
613       List<TryCatchBlock> tryCatchBlocks = getTryHandlers(insn);
614       if (!tryCatchBlocks.isEmpty()) {
615         Set<Integer> seenHandlerOffsets = new HashSet<>();
616         for (TryCatchBlock tryCatchBlock : tryCatchBlocks) {
617           // Ensure the block starts at the start of the try-range (don't enqueue, not a target).
618           builder.ensureBlockWithoutEnqueuing(tryCatchBlock.getStart());
619           // Add edge to exceptional successor (only one edge for each unique successor).
620           int handler = tryCatchBlock.getHandler();
621           if (!seenHandlerOffsets.contains(handler)) {
622             seenHandlerOffsets.add(handler);
623             builder.ensureExceptionalSuccessorBlock(index, handler);
624           }
625         }
626         // Edge to normal successor if any (fallthrough).
627         if (!isThrow(insn)) {
628           builder.ensureNormalSuccessorBlock(index, getOffset(insn.getNext()));
629         }
630         return index;
631       }
632       // If the throwable instruction is "throw" it closes the block.
633       return isThrow(insn) ? index : -1;
634     }
635     // This instruction does not close the block.
636     return -1;
637   }
638 
getPotentialTryHandlers(AbstractInsnNode insn)639   private List<TryCatchBlock> getPotentialTryHandlers(AbstractInsnNode insn) {
640     int offset = getOffset(insn);
641     return getPotentialTryHandlers(offset);
642   }
643 
tryBlockRelevant(TryCatchBlockNode tryHandler, int offset)644   private boolean tryBlockRelevant(TryCatchBlockNode tryHandler, int offset) {
645     int start = getOffset(tryHandler.start);
646     int end = getOffset(tryHandler.end);
647     return start <= offset && offset < end;
648   }
649 
getPotentialTryHandlers(int offset)650   private List<TryCatchBlock> getPotentialTryHandlers(int offset) {
651     List<TryCatchBlock> handlers = new ArrayList<>();
652     for (int i = 0; i < node.tryCatchBlocks.size(); i++) {
653       TryCatchBlockNode tryBlock = (TryCatchBlockNode) node.tryCatchBlocks.get(i);
654       if (tryBlockRelevant(tryBlock, offset)) {
655         handlers.add(new TryCatchBlock(tryBlock, this));
656       }
657     }
658     return handlers;
659   }
660 
getTryHandlers(AbstractInsnNode insn)661   private List<TryCatchBlock> getTryHandlers(AbstractInsnNode insn) {
662     List<TryCatchBlock> handlers = new ArrayList<>();
663     Set<String> seen = new HashSet<>();
664     // The try-catch blocks are ordered by precedence.
665     for (TryCatchBlock tryCatchBlock : getPotentialTryHandlers(insn)) {
666       if (tryCatchBlock.getType() == null) {
667         handlers.add(tryCatchBlock);
668         return handlers;
669       }
670       if (!seen.contains(tryCatchBlock.getType())) {
671         seen.add(tryCatchBlock.getType());
672         handlers.add(tryCatchBlock);
673       }
674     }
675     if (isSynchronized()) {
676       // Add synchronized exceptional exit for synchronized-method instructions without a default.
677       assert handlers.isEmpty() || handlers.get(handlers.size() - 1).getType() != null;
678       handlers.add(EXCEPTIONAL_SYNC_EXIT);
679     }
680     return handlers;
681   }
682 
getTryHandlerOffsets(List<TryCatchBlock> tryCatchBlocks)683   private List<Integer> getTryHandlerOffsets(List<TryCatchBlock> tryCatchBlocks) {
684     List<Integer> offsets = new ArrayList<>();
685     for (TryCatchBlock tryCatchBlock : tryCatchBlocks) {
686       offsets.add(tryCatchBlock.getHandler());
687     }
688     return offsets;
689   }
690 
getTryHandlerGuards(List<TryCatchBlock> tryCatchBlocks)691   private List<DexType> getTryHandlerGuards(List<TryCatchBlock> tryCatchBlocks) {
692     List<DexType> guards = new ArrayList<>();
693     for (TryCatchBlock tryCatchBlock : tryCatchBlocks) {
694       guards.add(tryCatchBlock.getType() == null
695           ? DexItemFactory.catchAllType
696           : application.getTypeFromName(tryCatchBlock.getType()));
697 
698     }
699     return guards;
700   }
701 
getOffset(AbstractInsnNode insn)702   int getOffset(AbstractInsnNode insn) {
703     return node.instructions.indexOf(insn);
704   }
705 
getTargets(AbstractInsnNode insn)706   private int[] getTargets(AbstractInsnNode insn) {
707     switch (insn.getType()) {
708       case AbstractInsnNode.TABLESWITCH_INSN: {
709         TableSwitchInsnNode switchInsn = (TableSwitchInsnNode) insn;
710         return getSwitchTargets(switchInsn.dflt, switchInsn.labels);
711       }
712       case AbstractInsnNode.LOOKUPSWITCH_INSN: {
713         LookupSwitchInsnNode switchInsn = (LookupSwitchInsnNode) insn;
714         return getSwitchTargets(switchInsn.dflt, switchInsn.labels);
715       }
716       case AbstractInsnNode.JUMP_INSN: {
717         return getJumpTargets((JumpInsnNode) insn);
718       }
719       case AbstractInsnNode.VAR_INSN: {
720         return getVarTargets((VarInsnNode) insn);
721       }
722       default:
723         return NO_TARGETS;
724     }
725   }
726 
getSwitchTargets(LabelNode dflt, List labels)727   private int[] getSwitchTargets(LabelNode dflt, List labels) {
728     int[] targets = new int[1 + labels.size()];
729     targets[0] = getOffset(dflt);
730     for (int i = 1; i < targets.length; i++) {
731       targets[i] = getOffset((LabelNode) labels.get(i - 1));
732     }
733     return targets;
734   }
735 
getJumpTargets(JumpInsnNode jump)736   private int[] getJumpTargets(JumpInsnNode jump) {
737     switch (jump.getOpcode()) {
738       case Opcodes.IFEQ:
739       case Opcodes.IFNE:
740       case Opcodes.IFLT:
741       case Opcodes.IFGE:
742       case Opcodes.IFGT:
743       case Opcodes.IFLE:
744       case Opcodes.IF_ICMPEQ:
745       case Opcodes.IF_ICMPNE:
746       case Opcodes.IF_ICMPLT:
747       case Opcodes.IF_ICMPGE:
748       case Opcodes.IF_ICMPGT:
749       case Opcodes.IF_ICMPLE:
750       case Opcodes.IF_ACMPEQ:
751       case Opcodes.IF_ACMPNE:
752       case Opcodes.IFNULL:
753       case Opcodes.IFNONNULL:
754         return new int[]{getOffset(jump.label), getOffset(jump.getNext())};
755       case Opcodes.GOTO:
756         return new int[]{getOffset(jump.label)};
757       case Opcodes.JSR: {
758         throw new Unreachable("JSR should be handled by the ASM jsr inliner");
759       }
760       default:
761         throw new Unreachable("Unexpected opcode in jump instruction: " + jump);
762     }
763   }
764 
getVarTargets(VarInsnNode insn)765   private int[] getVarTargets(VarInsnNode insn) {
766     if (insn.getOpcode() == Opcodes.RET) {
767       throw new Unreachable("RET should be handled by the ASM jsr inliner");
768     }
769     return NO_TARGETS;
770   }
771 
772   // Type conversion helpers.
773 
moveType(Type type)774   private static MoveType moveType(Type type) {
775     switch (type.getSort()) {
776       case Type.ARRAY:
777       case Type.OBJECT:
778         return MoveType.OBJECT;
779       case Type.BOOLEAN:
780       case Type.BYTE:
781       case Type.SHORT:
782       case Type.CHAR:
783       case Type.INT:
784       case Type.FLOAT:
785         return MoveType.SINGLE;
786       case Type.LONG:
787       case Type.DOUBLE:
788         return MoveType.WIDE;
789       case Type.VOID:
790         // Illegal. Throws in fallthrough.
791       default:
792         throw new Unreachable("Invalid type in moveType: " + type);
793     }
794   }
795 
constType(Type type)796   private static ConstType constType(Type type) {
797     switch (type.getSort()) {
798       case Type.ARRAY:
799       case Type.OBJECT:
800         return ConstType.OBJECT;
801       case Type.BOOLEAN:
802       case Type.BYTE:
803       case Type.SHORT:
804       case Type.CHAR:
805       case Type.INT:
806         return ConstType.INT;
807       case Type.FLOAT:
808         return ConstType.FLOAT;
809       case Type.LONG:
810         return ConstType.LONG;
811       case Type.DOUBLE:
812         return ConstType.DOUBLE;
813       case Type.VOID:
814         // Illegal. Throws in fallthrough.
815       default:
816         throw new Unreachable("Invalid type in constType: " + type);
817     }
818   }
819 
memberType(Type type)820   private static MemberType memberType(Type type) {
821     switch (type.getSort()) {
822       case Type.ARRAY:
823       case Type.OBJECT:
824         return MemberType.OBJECT;
825       case Type.BOOLEAN:
826         return MemberType.BOOLEAN;
827       case Type.BYTE:
828         return MemberType.BYTE;
829       case Type.SHORT:
830         return MemberType.SHORT;
831       case Type.CHAR:
832         return MemberType.CHAR;
833       case Type.INT:
834       case Type.FLOAT:
835         return MemberType.SINGLE;
836       case Type.LONG:
837       case Type.DOUBLE:
838         return MemberType.WIDE;
839       case Type.VOID:
840         // Illegal. Throws in fallthrough.
841       default:
842         throw new Unreachable("Invalid type in memberType: " + type);
843     }
844   }
845 
memberType(String fieldDesc)846   private static MemberType memberType(String fieldDesc) {
847     return memberType(Type.getType(fieldDesc));
848   }
849 
numericType(Type type)850   private static NumericType numericType(Type type) {
851     switch (type.getSort()) {
852       case Type.BYTE:
853         return NumericType.BYTE;
854       case Type.CHAR:
855         return NumericType.CHAR;
856       case Type.SHORT:
857         return NumericType.SHORT;
858       case Type.INT:
859         return NumericType.INT;
860       case Type.LONG:
861         return NumericType.LONG;
862       case Type.FLOAT:
863         return NumericType.FLOAT;
864       case Type.DOUBLE:
865         return NumericType.DOUBLE;
866       default:
867         throw new Unreachable("Invalid type in numericType: " + type);
868     }
869   }
870 
invokeType(MethodInsnNode method)871   private Invoke.Type invokeType(MethodInsnNode method) {
872     switch (method.getOpcode()) {
873       case Opcodes.INVOKEVIRTUAL:
874         if (isCallToPolymorphicSignatureMethod(method)) {
875           return Invoke.Type.POLYMORPHIC;
876         }
877         return Invoke.Type.VIRTUAL;
878       case Opcodes.INVOKESTATIC:
879         return Invoke.Type.STATIC;
880       case Opcodes.INVOKEINTERFACE:
881         return Invoke.Type.INTERFACE;
882       case Opcodes.INVOKESPECIAL: {
883         DexType owner = application.getTypeFromName(method.owner);
884         if (owner == clazz || method.name.equals(Constants.INSTANCE_INITIALIZER_NAME)) {
885           return Invoke.Type.DIRECT;
886         } else {
887           return Invoke.Type.SUPER;
888         }
889       }
890       default:
891         throw new Unreachable("Unexpected MethodInsnNode opcode: " + method.getOpcode());
892     }
893   }
894 
getArrayElementType(Type array)895   static Type getArrayElementType(Type array) {
896     if (array == JarState.NULL_TYPE) {
897       return null;
898     }
899     String desc = array.getDescriptor();
900     assert desc.charAt(0) == '[';
901     return Type.getType(desc.substring(1));
902   }
903 
makeArrayType(Type elementType)904   private static Type makeArrayType(Type elementType) {
905     return Type.getObjectType("[" + elementType.getDescriptor());
906   }
907 
arrayTypeDesc(int arrayTypeCode)908   private static String arrayTypeDesc(int arrayTypeCode) {
909     switch (arrayTypeCode) {
910       case Opcodes.T_BOOLEAN:
911         return "[Z";
912       case Opcodes.T_CHAR:
913         return "[C";
914       case Opcodes.T_FLOAT:
915         return "[F";
916       case Opcodes.T_DOUBLE:
917         return "[D";
918       case Opcodes.T_BYTE:
919         return "[B";
920       case Opcodes.T_SHORT:
921         return "[S";
922       case Opcodes.T_INT:
923         return "[I";
924       case Opcodes.T_LONG:
925         return "[J";
926       default:
927         throw new Unreachable("Unexpected array-type code " + arrayTypeCode);
928     }
929   }
930 
getArrayElementTypeForOpcode(int opcode)931   private static Type getArrayElementTypeForOpcode(int opcode) {
932     switch (opcode) {
933       case Opcodes.IALOAD:
934       case Opcodes.IASTORE:
935         return Type.INT_TYPE;
936       case Opcodes.FALOAD:
937       case Opcodes.FASTORE:
938         return Type.FLOAT_TYPE;
939       case Opcodes.LALOAD:
940       case Opcodes.LASTORE:
941         return Type.LONG_TYPE;
942       case Opcodes.DALOAD:
943       case Opcodes.DASTORE:
944         return Type.DOUBLE_TYPE;
945       case Opcodes.AALOAD:
946       case Opcodes.AASTORE:
947         return JarState.NULL_TYPE; // We might not know the type.
948       case Opcodes.BALOAD:
949       case Opcodes.BASTORE:
950         return Type.BYTE_TYPE; // We don't distinguish byte and boolean.
951       case Opcodes.CALOAD:
952       case Opcodes.CASTORE:
953         return Type.CHAR_TYPE;
954       case Opcodes.SALOAD:
955       case Opcodes.SASTORE:
956         return Type.SHORT_TYPE;
957       default:
958         throw new Unreachable("Unexpected array opcode " + opcode);
959     }
960   }
961 
isCompatibleArrayElementType(int opcode, Type type)962   private static boolean isCompatibleArrayElementType(int opcode, Type type) {
963     switch (opcode) {
964       case Opcodes.IALOAD:
965       case Opcodes.IASTORE:
966         return Slot.isCompatible(type, Type.INT_TYPE);
967       case Opcodes.FALOAD:
968       case Opcodes.FASTORE:
969         return Slot.isCompatible(type, Type.FLOAT_TYPE);
970       case Opcodes.LALOAD:
971       case Opcodes.LASTORE:
972         return Slot.isCompatible(type, Type.LONG_TYPE);
973       case Opcodes.DALOAD:
974       case Opcodes.DASTORE:
975         return Slot.isCompatible(type, Type.DOUBLE_TYPE);
976       case Opcodes.AALOAD:
977       case Opcodes.AASTORE:
978         return Slot.isCompatible(type, JarState.REFERENCE_TYPE);
979       case Opcodes.BALOAD:
980       case Opcodes.BASTORE:
981         return Slot.isCompatible(type, Type.BYTE_TYPE)
982             || Slot.isCompatible(type, Type.BOOLEAN_TYPE);
983       case Opcodes.CALOAD:
984       case Opcodes.CASTORE:
985         return Slot.isCompatible(type, Type.CHAR_TYPE);
986       case Opcodes.SALOAD:
987       case Opcodes.SASTORE:
988         return Slot.isCompatible(type, Type.SHORT_TYPE);
989       default:
990         throw new Unreachable("Unexpected array opcode " + opcode);
991     }
992   }
993 
ifType(int opcode)994   private static If.Type ifType(int opcode) {
995     switch (opcode) {
996       case Opcodes.IFEQ:
997       case Opcodes.IF_ICMPEQ:
998       case Opcodes.IF_ACMPEQ:
999         return If.Type.EQ;
1000       case Opcodes.IFNE:
1001       case Opcodes.IF_ICMPNE:
1002       case Opcodes.IF_ACMPNE:
1003         return If.Type.NE;
1004       case Opcodes.IFLT:
1005       case Opcodes.IF_ICMPLT:
1006         return If.Type.LT;
1007       case Opcodes.IFGE:
1008       case Opcodes.IF_ICMPGE:
1009         return If.Type.GE;
1010       case Opcodes.IFGT:
1011       case Opcodes.IF_ICMPGT:
1012         return If.Type.GT;
1013       case Opcodes.IFLE:
1014       case Opcodes.IF_ICMPLE:
1015         return If.Type.LE;
1016       default:
1017         throw new Unreachable("Unexpected If instruction opcode: " + opcode);
1018     }
1019   }
1020 
opType(int opcode)1021   private static Type opType(int opcode) {
1022     switch (opcode) {
1023       case Opcodes.IADD:
1024       case Opcodes.ISUB:
1025       case Opcodes.IMUL:
1026       case Opcodes.IDIV:
1027       case Opcodes.IREM:
1028       case Opcodes.INEG:
1029       case Opcodes.ISHL:
1030       case Opcodes.ISHR:
1031       case Opcodes.IUSHR:
1032         return Type.INT_TYPE;
1033       case Opcodes.LADD:
1034       case Opcodes.LSUB:
1035       case Opcodes.LMUL:
1036       case Opcodes.LDIV:
1037       case Opcodes.LREM:
1038       case Opcodes.LNEG:
1039       case Opcodes.LSHL:
1040       case Opcodes.LSHR:
1041       case Opcodes.LUSHR:
1042         return Type.LONG_TYPE;
1043       case Opcodes.FADD:
1044       case Opcodes.FSUB:
1045       case Opcodes.FMUL:
1046       case Opcodes.FDIV:
1047       case Opcodes.FREM:
1048       case Opcodes.FNEG:
1049         return Type.FLOAT_TYPE;
1050       case Opcodes.DADD:
1051       case Opcodes.DSUB:
1052       case Opcodes.DMUL:
1053       case Opcodes.DDIV:
1054       case Opcodes.DREM:
1055       case Opcodes.DNEG:
1056         return Type.DOUBLE_TYPE;
1057       default:
1058         throw new Unreachable("Unexpected opcode " + opcode);
1059     }
1060   }
1061 
1062   // State updating procedures.
1063 
updateState(AbstractInsnNode insn)1064   private void updateState(AbstractInsnNode insn) {
1065     switch (insn.getType()) {
1066       case AbstractInsnNode.INSN:
1067         updateState((InsnNode) insn);
1068         break;
1069       case AbstractInsnNode.INT_INSN:
1070         updateState((IntInsnNode) insn);
1071         break;
1072       case AbstractInsnNode.VAR_INSN:
1073         updateState((VarInsnNode) insn);
1074         break;
1075       case AbstractInsnNode.TYPE_INSN:
1076         updateState((TypeInsnNode) insn);
1077         break;
1078       case AbstractInsnNode.FIELD_INSN:
1079         updateState((FieldInsnNode) insn);
1080         break;
1081       case AbstractInsnNode.METHOD_INSN:
1082         updateState((MethodInsnNode) insn);
1083         break;
1084       case AbstractInsnNode.INVOKE_DYNAMIC_INSN:
1085         updateState((InvokeDynamicInsnNode) insn);
1086         break;
1087       case AbstractInsnNode.JUMP_INSN:
1088         updateState((JumpInsnNode) insn);
1089         break;
1090       case AbstractInsnNode.LABEL:
1091         updateState((LabelNode) insn);
1092         break;
1093       case AbstractInsnNode.LDC_INSN:
1094         updateState((LdcInsnNode) insn);
1095         break;
1096       case AbstractInsnNode.IINC_INSN:
1097         updateState((IincInsnNode) insn);
1098         break;
1099       case AbstractInsnNode.TABLESWITCH_INSN:
1100         updateState((TableSwitchInsnNode) insn);
1101         break;
1102       case AbstractInsnNode.LOOKUPSWITCH_INSN:
1103         updateState((LookupSwitchInsnNode) insn);
1104         break;
1105       case AbstractInsnNode.MULTIANEWARRAY_INSN:
1106         updateState((MultiANewArrayInsnNode) insn);
1107         break;
1108       case AbstractInsnNode.LINE:
1109         updateState((LineNumberNode) insn);
1110         break;
1111       default:
1112         throw new Unreachable("Unexpected instruction " + insn);
1113     }
1114   }
1115 
updateState(InsnNode insn)1116   private void updateState(InsnNode insn) {
1117     int opcode = insn.getOpcode();
1118     switch (opcode) {
1119       case Opcodes.NOP:
1120         // Intentionally left empty.
1121         break;
1122       case Opcodes.ACONST_NULL:
1123         state.push(JarState.NULL_TYPE);
1124         break;
1125       case Opcodes.ICONST_M1:
1126       case Opcodes.ICONST_0:
1127       case Opcodes.ICONST_1:
1128       case Opcodes.ICONST_2:
1129       case Opcodes.ICONST_3:
1130       case Opcodes.ICONST_4:
1131       case Opcodes.ICONST_5:
1132         state.push(Type.INT_TYPE);
1133         break;
1134       case Opcodes.LCONST_0:
1135       case Opcodes.LCONST_1:
1136         state.push(Type.LONG_TYPE);
1137         break;
1138       case Opcodes.FCONST_0:
1139       case Opcodes.FCONST_1:
1140       case Opcodes.FCONST_2:
1141         state.push(Type.FLOAT_TYPE);
1142         break;
1143       case Opcodes.DCONST_0:
1144       case Opcodes.DCONST_1:
1145         state.push(Type.DOUBLE_TYPE);
1146         break;
1147       case Opcodes.IALOAD:
1148       case Opcodes.LALOAD:
1149       case Opcodes.FALOAD:
1150       case Opcodes.DALOAD:
1151       case Opcodes.AALOAD:
1152       case Opcodes.BALOAD:
1153       case Opcodes.CALOAD:
1154       case Opcodes.SALOAD: {
1155         state.pop();
1156         Slot array = state.pop(JarState.ARRAY_TYPE);
1157         Type elementType = getArrayElementType(array.type);
1158         if (elementType == null) {
1159           // We propagate the null type, which will then get resolved to an
1160           // actual type if we have a non-null type on another flow edge.
1161           elementType = JarState.NULL_TYPE;
1162         }
1163         state.push(elementType);
1164         break;
1165       }
1166       case Opcodes.IASTORE:
1167       case Opcodes.LASTORE:
1168       case Opcodes.FASTORE:
1169       case Opcodes.DASTORE:
1170       case Opcodes.AASTORE:
1171       case Opcodes.BASTORE:
1172       case Opcodes.CASTORE:
1173       case Opcodes.SASTORE: {
1174         state.pop();
1175         state.pop();
1176         state.pop();
1177         break;
1178       }
1179       case Opcodes.POP: {
1180         Slot value = state.pop();
1181         assert value.isCategory1();
1182         break;
1183       }
1184       case Opcodes.POP2: {
1185         Slot value = state.pop();
1186         if (value.isCategory1()) {
1187           Slot value2 = state.pop();
1188           assert value2.isCategory1();
1189         }
1190         break;
1191       }
1192       case Opcodes.DUP: {
1193         Slot value = state.peek();
1194         assert value.isCategory1();
1195         state.push(value.type);
1196         break;
1197       }
1198       case Opcodes.DUP_X1: {
1199         // Stack transformation: ..., v2, v1 -> ..., v1, v2, v1
1200         Slot value1 = state.pop();
1201         Slot value2 = state.pop();
1202         assert value1.isCategory1() && value2.isCategory1();
1203         int stack2 = state.push(value1.type);
1204         int stack1 = state.push(value2.type);
1205         state.push(value1.type);
1206         assert value2.register == stack2;
1207         assert value1.register == stack1;
1208         break;
1209       }
1210       case Opcodes.DUP_X2: {
1211         Slot value1 = state.pop();
1212         Slot value2 = state.pop();
1213         assert value1.isCategory1();
1214         if (value2.isCategory1()) {
1215           Slot value3 = state.pop();
1216           assert value3.isCategory1();
1217           // Stack transformation: ..., v3, v2, v1 -> ..., v1, v3, v2, v1
1218           updateStateForDupOneBelowTwo(value3, value2, value1);
1219         } else {
1220           // Stack transformation: ..., w2, v1 -> ..., v1, w2, v1
1221           updateStateForDupOneBelowOne(value2, value1);
1222         }
1223         break;
1224       }
1225       case Opcodes.DUP2: {
1226         Slot value1 = state.pop();
1227         if (value1.isCategory1()) {
1228           Slot value2 = state.pop();
1229           // Stack transformation: ..., v2, v1 -> ..., v2, v1, v2, v1
1230           assert value2.isCategory1();
1231           state.push(value2.type);
1232           state.push(value1.type);
1233           state.push(value2.type);
1234           state.push(value1.type);
1235         } else {
1236           // Stack transformation: ..., w1 -> ..., w1, w1
1237           state.push(value1.type);
1238           state.push(value1.type);
1239         }
1240         break;
1241       }
1242       case Opcodes.DUP2_X1: {
1243         Slot value1 = state.pop();
1244         Slot value2 = state.pop();
1245         assert value2.isCategory1();
1246         if (value1.isCategory1()) {
1247           // Stack transformation: ..., v3, v2, v1 -> v2, v1, v3, v2, v1
1248           Slot value3 = state.pop();
1249           assert value3.isCategory1();
1250           updateStateForDupTwoBelowOne(value3, value2, value1);
1251         } else {
1252           // Stack transformation: ..., v2, w1 -> ..., w1, v2, w1
1253           updateStateForDupOneBelowOne(value2, value1);
1254         }
1255         break;
1256       }
1257       case Opcodes.DUP2_X2: {
1258         Slot value1 = state.pop();
1259         Slot value2 = state.pop();
1260         if (!value1.isCategory1() && !value2.isCategory1()) {
1261           // State transformation: ..., w2, w1 -> w1, w2, w1
1262           updateStateForDupOneBelowOne(value2, value1);
1263         } else {
1264           Slot value3 = state.pop();
1265           if (!value1.isCategory1()) {
1266             assert value2.isCategory1();
1267             assert value3.isCategory1();
1268             // State transformation: ..., v3, v2, w1 -> w1, v3, v2, w1
1269             updateStateForDupOneBelowTwo(value3, value2, value1);
1270           } else if (!value3.isCategory1()) {
1271             assert value1.isCategory1();
1272             assert value2.isCategory1();
1273             // State transformation: ..., w3, v2, v1 -> v2, v1, w3, v2, v1
1274             updateStateForDupTwoBelowOne(value3, value2, value1);
1275           } else {
1276             Slot value4 = state.pop();
1277             assert value1.isCategory1();
1278             assert value2.isCategory1();
1279             assert value3.isCategory1();
1280             assert value4.isCategory1();
1281             // State transformation: ..., v4, v3, v2, v1 -> v2, v1, v4, v3, v2, v1
1282             updateStateForDupTwoBelowTwo(value4, value3, value2, value1);
1283           }
1284         }
1285         break;
1286       }
1287       case Opcodes.SWAP: {
1288         Slot value1 = state.pop();
1289         Slot value2 = state.pop();
1290         assert value1.isCategory1() && value2.isCategory1();
1291         state.push(value1.type);
1292         state.push(value2.type);
1293         break;
1294       }
1295       case Opcodes.IADD:
1296       case Opcodes.LADD:
1297       case Opcodes.FADD:
1298       case Opcodes.DADD:
1299       case Opcodes.ISUB:
1300       case Opcodes.LSUB:
1301       case Opcodes.FSUB:
1302       case Opcodes.DSUB:
1303       case Opcodes.IMUL:
1304       case Opcodes.LMUL:
1305       case Opcodes.FMUL:
1306       case Opcodes.DMUL:
1307       case Opcodes.IDIV:
1308       case Opcodes.LDIV:
1309       case Opcodes.FDIV:
1310       case Opcodes.DDIV:
1311       case Opcodes.IREM:
1312       case Opcodes.LREM:
1313       case Opcodes.FREM:
1314       case Opcodes.DREM: {
1315         Type type = opType(opcode);
1316         state.pop();
1317         state.pop();
1318         state.push(type);
1319         break;
1320       }
1321       case Opcodes.INEG:
1322       case Opcodes.LNEG:
1323       case Opcodes.FNEG:
1324       case Opcodes.DNEG: {
1325         Type type = opType(opcode);
1326         state.pop();
1327         state.push(type);
1328         break;
1329       }
1330       case Opcodes.ISHL:
1331       case Opcodes.LSHL:
1332       case Opcodes.ISHR:
1333       case Opcodes.LSHR:
1334       case Opcodes.IUSHR:
1335       case Opcodes.LUSHR: {
1336         Type type = opType(opcode);
1337         state.pop();
1338         state.pop();
1339         state.push(type);
1340         break;
1341       }
1342       case Opcodes.IAND:
1343       case Opcodes.LAND: {
1344         Type type = opcode == Opcodes.IAND ? Type.INT_TYPE : Type.LONG_TYPE;
1345         state.pop();
1346         state.pop();
1347         state.push(type);
1348         break;
1349       }
1350       case Opcodes.IOR:
1351       case Opcodes.LOR: {
1352         Type type = opcode == Opcodes.IOR ? Type.INT_TYPE : Type.LONG_TYPE;
1353         state.pop();
1354         state.pop();
1355         state.push(type);
1356         break;
1357       }
1358       case Opcodes.IXOR:
1359       case Opcodes.LXOR: {
1360         Type type = opcode == Opcodes.IXOR ? Type.INT_TYPE : Type.LONG_TYPE;
1361         state.pop();
1362         state.pop();
1363         state.push(type);
1364         break;
1365       }
1366       case Opcodes.I2L:
1367         updateStateForConversion(Type.INT_TYPE, Type.LONG_TYPE);
1368         break;
1369       case Opcodes.I2F:
1370         updateStateForConversion(Type.INT_TYPE, Type.FLOAT_TYPE);
1371         break;
1372       case Opcodes.I2D:
1373         updateStateForConversion(Type.INT_TYPE, Type.DOUBLE_TYPE);
1374         break;
1375       case Opcodes.L2I:
1376         updateStateForConversion(Type.LONG_TYPE, Type.INT_TYPE);
1377         break;
1378       case Opcodes.L2F:
1379         updateStateForConversion(Type.LONG_TYPE, Type.FLOAT_TYPE);
1380         break;
1381       case Opcodes.L2D:
1382         updateStateForConversion(Type.LONG_TYPE, Type.DOUBLE_TYPE);
1383         break;
1384       case Opcodes.F2I:
1385         updateStateForConversion(Type.FLOAT_TYPE, Type.INT_TYPE);
1386         break;
1387       case Opcodes.F2L:
1388         updateStateForConversion(Type.FLOAT_TYPE, Type.LONG_TYPE);
1389         break;
1390       case Opcodes.F2D:
1391         updateStateForConversion(Type.FLOAT_TYPE, Type.DOUBLE_TYPE);
1392         break;
1393       case Opcodes.D2I:
1394         updateStateForConversion(Type.DOUBLE_TYPE, Type.INT_TYPE);
1395         break;
1396       case Opcodes.D2L:
1397         updateStateForConversion(Type.DOUBLE_TYPE, Type.LONG_TYPE);
1398         break;
1399       case Opcodes.D2F:
1400         updateStateForConversion(Type.DOUBLE_TYPE, Type.FLOAT_TYPE);
1401         break;
1402       case Opcodes.I2B:
1403         updateStateForConversion(Type.INT_TYPE, Type.BYTE_TYPE);
1404         break;
1405       case Opcodes.I2C:
1406         updateStateForConversion(Type.INT_TYPE, Type.CHAR_TYPE);
1407         break;
1408       case Opcodes.I2S:
1409         updateStateForConversion(Type.INT_TYPE, Type.SHORT_TYPE);
1410         break;
1411       case Opcodes.LCMP: {
1412         state.pop();
1413         state.pop();
1414         state.push(Type.INT_TYPE);
1415         break;
1416       }
1417       case Opcodes.FCMPL:
1418       case Opcodes.FCMPG: {
1419         state.pop();
1420         state.pop();
1421         state.push(Type.INT_TYPE);
1422         break;
1423       }
1424       case Opcodes.DCMPL:
1425       case Opcodes.DCMPG: {
1426         state.pop();
1427         state.pop();
1428         state.push(Type.INT_TYPE);
1429         break;
1430       }
1431       case Opcodes.IRETURN: {
1432         state.pop();
1433         break;
1434       }
1435       case Opcodes.LRETURN: {
1436         state.pop();
1437         break;
1438       }
1439       case Opcodes.FRETURN: {
1440         state.pop();
1441         break;
1442       }
1443       case Opcodes.DRETURN: {
1444         state.pop();
1445         break;
1446       }
1447       case Opcodes.ARETURN: {
1448         state.pop(JarState.REFERENCE_TYPE);
1449         break;
1450       }
1451       case Opcodes.RETURN: {
1452         break;
1453       }
1454       case Opcodes.ARRAYLENGTH: {
1455         state.pop(JarState.ARRAY_TYPE);
1456         state.push(Type.INT_TYPE);
1457         break;
1458       }
1459       case Opcodes.ATHROW: {
1460         state.pop(JarState.OBJECT_TYPE);
1461         break;
1462       }
1463       case Opcodes.MONITORENTER: {
1464         state.pop(JarState.REFERENCE_TYPE);
1465         break;
1466       }
1467       case Opcodes.MONITOREXIT: {
1468         state.pop(JarState.REFERENCE_TYPE);
1469         break;
1470       }
1471       default:
1472         throw new Unreachable("Unexpected Insn opcode: " + insn.getOpcode());
1473     }
1474   }
1475 
updateStateForDupOneBelowTwo(Slot value3, Slot value2, Slot value1)1476   private void updateStateForDupOneBelowTwo(Slot value3, Slot value2, Slot value1) {
1477     state.push(value1.type);
1478     state.push(value3.type);
1479     state.push(value2.type);
1480     state.push(value1.type);
1481   }
1482 
updateStateForDupOneBelowOne(Slot value2, Slot value1)1483   private void updateStateForDupOneBelowOne(Slot value2, Slot value1) {
1484     state.push(value1.type);
1485     state.push(value2.type);
1486     state.push(value1.type);
1487   }
1488 
updateStateForDupTwoBelowOne(Slot value3, Slot value2, Slot value1)1489   private void updateStateForDupTwoBelowOne(Slot value3, Slot value2, Slot value1) {
1490     state.push(value2.type);
1491     state.push(value1.type);
1492     state.push(value3.type);
1493     state.push(value2.type);
1494     state.push(value1.type);
1495   }
1496 
updateStateForDupTwoBelowTwo(Slot value4, Slot value3, Slot value2, Slot value1)1497   private void updateStateForDupTwoBelowTwo(Slot value4, Slot value3, Slot value2, Slot value1) {
1498     state.push(value2.type);
1499     state.push(value1.type);
1500     state.push(value4.type);
1501     state.push(value3.type);
1502     state.push(value2.type);
1503     state.push(value1.type);
1504   }
1505 
updateState(IntInsnNode insn)1506   private void updateState(IntInsnNode insn) {
1507     switch (insn.getOpcode()) {
1508       case Opcodes.BIPUSH:
1509       case Opcodes.SIPUSH: {
1510         state.push(Type.INT_TYPE);
1511         break;
1512       }
1513       case Opcodes.NEWARRAY: {
1514         String desc = arrayTypeDesc(insn.operand);
1515         Type type = Type.getType(desc);
1516         state.pop();
1517         state.push(type);
1518         break;
1519       }
1520       default:
1521         throw new Unreachable("Unexpected IntInsn opcode: " + insn.getOpcode());
1522     }
1523   }
1524 
updateState(VarInsnNode insn)1525   private void updateState(VarInsnNode insn) {
1526     int opcode = insn.getOpcode();
1527     Type expectedType;
1528     switch (opcode) {
1529       case Opcodes.ILOAD:
1530       case Opcodes.ISTORE:
1531         expectedType = Type.INT_TYPE;
1532         break;
1533       case Opcodes.FLOAD:
1534       case Opcodes.FSTORE:
1535         expectedType = Type.FLOAT_TYPE;
1536         break;
1537       case Opcodes.LLOAD:
1538       case Opcodes.LSTORE:
1539         expectedType = Type.LONG_TYPE;
1540         break;
1541       case Opcodes.DLOAD:
1542       case Opcodes.DSTORE:
1543         expectedType = Type.DOUBLE_TYPE;
1544         break;
1545       case Opcodes.ALOAD:
1546       case Opcodes.ASTORE:
1547         expectedType = JarState.REFERENCE_TYPE;
1548         break;
1549       case Opcodes.RET: {
1550         throw new Unreachable("RET should be handled by the ASM jsr inliner");
1551       }
1552       default:
1553         throw new Unreachable("Unexpected VarInsn opcode: " + insn.getOpcode());
1554     }
1555     if (Opcodes.ILOAD <= opcode && opcode <= Opcodes.ALOAD) {
1556       Slot src = state.readLocal(insn.var, expectedType);
1557       state.push(src.type);
1558     } else {
1559       assert Opcodes.ISTORE <= opcode && opcode <= Opcodes.ASTORE;
1560       Slot slot = state.pop();
1561       if (slot.type == JarState.NULL_TYPE && expectedType != JarState.REFERENCE_TYPE) {
1562         state.writeLocal(insn.var, expectedType);
1563       } else {
1564         state.writeLocal(insn.var, slot.type);
1565       }
1566     }
1567   }
1568 
updateState(TypeInsnNode insn)1569   private void updateState(TypeInsnNode insn) {
1570     Type type = Type.getObjectType(insn.desc);
1571     switch (insn.getOpcode()) {
1572       case Opcodes.NEW: {
1573         state.push(type);
1574         break;
1575       }
1576       case Opcodes.ANEWARRAY: {
1577         Type arrayType = makeArrayType(type);
1578         state.pop();
1579         state.push(arrayType);
1580         break;
1581       }
1582       case Opcodes.CHECKCAST: {
1583         // Pop the top value and push it back on with the checked type.
1584         state.pop(type);
1585         state.push(type);
1586         break;
1587       }
1588       case Opcodes.INSTANCEOF: {
1589         state.pop(JarState.REFERENCE_TYPE);
1590         state.push(Type.INT_TYPE);
1591         break;
1592       }
1593       default:
1594         throw new Unreachable("Unexpected TypeInsn opcode: " + insn.getOpcode());
1595     }
1596 
1597   }
1598 
updateState(FieldInsnNode insn)1599   private void updateState(FieldInsnNode insn) {
1600     Type type = Type.getType(insn.desc);
1601     switch (insn.getOpcode()) {
1602       case Opcodes.GETSTATIC:
1603         state.push(type);
1604         break;
1605       case Opcodes.PUTSTATIC:
1606         state.pop();
1607         break;
1608       case Opcodes.GETFIELD: {
1609         state.pop(JarState.OBJECT_TYPE);
1610         state.push(type);
1611         break;
1612       }
1613       case Opcodes.PUTFIELD: {
1614         state.pop();
1615         state.pop(JarState.OBJECT_TYPE);
1616         break;
1617       }
1618       default:
1619         throw new Unreachable("Unexpected FieldInsn opcode: " + insn.getOpcode());
1620     }
1621   }
1622 
updateState(MethodInsnNode insn)1623   private void updateState(MethodInsnNode insn) {
1624     updateStateForInvoke(insn.desc, insn.getOpcode() != Opcodes.INVOKESTATIC);
1625   }
1626 
updateState(InvokeDynamicInsnNode insn)1627   private void updateState(InvokeDynamicInsnNode insn) {
1628     updateStateForInvoke(insn.desc, false /* receiver passed explicitly */);
1629   }
1630 
updateStateForInvoke(String desc, boolean implicitReceiver)1631   private void updateStateForInvoke(String desc, boolean implicitReceiver) {
1632     // Pop arguments.
1633     Type[] parameterTypes = Type.getArgumentTypes(desc);
1634     state.popReverse(parameterTypes.length);
1635     // Pop implicit receiver if needed.
1636     if (implicitReceiver) {
1637       state.pop();
1638     }
1639     // Push return value if needed.
1640     Type returnType = Type.getReturnType(desc);
1641     if (returnType != Type.VOID_TYPE) {
1642       state.push(returnType);
1643     }
1644   }
1645 
updateState(JumpInsnNode insn)1646   private void updateState(JumpInsnNode insn) {
1647     int[] targets = getTargets(insn);
1648     int opcode = insn.getOpcode();
1649     if (Opcodes.IFEQ <= opcode && opcode <= Opcodes.IF_ACMPNE) {
1650       assert targets.length == 2;
1651       if (opcode <= Opcodes.IFLE) {
1652         state.pop();
1653       } else {
1654         state.pop();
1655         state.pop();
1656       }
1657     } else {
1658       switch (opcode) {
1659         case Opcodes.GOTO: {
1660           assert targets.length == 1;
1661           break;
1662         }
1663         case Opcodes.IFNULL:
1664         case Opcodes.IFNONNULL: {
1665           state.pop();
1666           break;
1667         }
1668         case Opcodes.JSR: {
1669           throw new Unreachable("JSR should be handled by the ASM jsr inliner");
1670         }
1671         default:
1672           throw new Unreachable("Unexpected JumpInsn opcode: " + insn.getOpcode());
1673       }
1674     }
1675   }
1676 
updateState(LabelNode insn)1677   private void updateState(LabelNode insn) {
1678     // Open the scope of locals starting at this point.
1679     if (insn != initialLabel) {
1680       state.openLocals(insn);
1681     }
1682   }
1683 
updateState(LdcInsnNode insn)1684   private void updateState(LdcInsnNode insn) {
1685     if (insn.cst instanceof Type) {
1686       Type type = (Type) insn.cst;
1687       state.push(type);
1688     } else if (insn.cst instanceof String) {
1689       state.push(STRING_TYPE);
1690     } else if (insn.cst instanceof Long) {
1691       state.push(Type.LONG_TYPE);
1692     } else if (insn.cst instanceof Double) {
1693       state.push(Type.DOUBLE_TYPE);
1694     } else if (insn.cst instanceof Integer) {
1695       state.push(Type.INT_TYPE);
1696     } else {
1697       assert insn.cst instanceof Float;
1698       state.push(Type.FLOAT_TYPE);
1699     }
1700   }
1701 
updateState(IincInsnNode insn)1702   private void updateState(IincInsnNode insn) {
1703     state.readLocal(insn.var, Type.INT_TYPE);
1704   }
1705 
updateState(TableSwitchInsnNode insn)1706   private void updateState(TableSwitchInsnNode insn) {
1707     state.pop();
1708   }
1709 
updateState(LookupSwitchInsnNode insn)1710   private void updateState(LookupSwitchInsnNode insn) {
1711     state.pop();
1712   }
1713 
updateState(MultiANewArrayInsnNode insn)1714   private void updateState(MultiANewArrayInsnNode insn) {
1715     // Type of the full array.
1716     Type arrayType = Type.getObjectType(insn.desc);
1717     state.popReverse(insn.dims, Type.INT_TYPE);
1718     state.push(arrayType);
1719   }
1720 
updateState(LineNumberNode insn)1721   private void updateState(LineNumberNode insn) {
1722     // Intentionally empty.
1723   }
1724 
updateStateForConversion(Type from, Type to)1725   private void updateStateForConversion(Type from, Type to) {
1726     state.pop();
1727     state.push(to);
1728   }
1729 
1730   // IR instruction building procedures.
1731 
build(AbstractInsnNode insn, IRBuilder builder)1732   private void build(AbstractInsnNode insn, IRBuilder builder) {
1733     switch (insn.getType()) {
1734       case AbstractInsnNode.INSN:
1735         build((InsnNode) insn, builder);
1736         break;
1737       case AbstractInsnNode.INT_INSN:
1738         build((IntInsnNode) insn, builder);
1739         break;
1740       case AbstractInsnNode.VAR_INSN:
1741         build((VarInsnNode) insn, builder);
1742         break;
1743       case AbstractInsnNode.TYPE_INSN:
1744         build((TypeInsnNode) insn, builder);
1745         break;
1746       case AbstractInsnNode.FIELD_INSN:
1747         build((FieldInsnNode) insn, builder);
1748         break;
1749       case AbstractInsnNode.METHOD_INSN:
1750         build((MethodInsnNode) insn, builder);
1751         break;
1752       case AbstractInsnNode.INVOKE_DYNAMIC_INSN:
1753         build((InvokeDynamicInsnNode) insn, builder);
1754         break;
1755       case AbstractInsnNode.JUMP_INSN:
1756         build((JumpInsnNode) insn, builder);
1757         break;
1758       case AbstractInsnNode.LABEL:
1759         build((LabelNode) insn, builder);
1760         break;
1761       case AbstractInsnNode.LDC_INSN:
1762         build((LdcInsnNode) insn, builder);
1763         break;
1764       case AbstractInsnNode.IINC_INSN:
1765         build((IincInsnNode) insn, builder);
1766         break;
1767       case AbstractInsnNode.TABLESWITCH_INSN:
1768         build((TableSwitchInsnNode) insn, builder);
1769         break;
1770       case AbstractInsnNode.LOOKUPSWITCH_INSN:
1771         build((LookupSwitchInsnNode) insn, builder);
1772         break;
1773       case AbstractInsnNode.MULTIANEWARRAY_INSN:
1774         build((MultiANewArrayInsnNode) insn, builder);
1775         break;
1776       case AbstractInsnNode.LINE:
1777         build((LineNumberNode) insn, builder);
1778         break;
1779       default:
1780         throw new Unreachable("Unexpected instruction " + insn);
1781     }
1782   }
1783 
processLocalVariableEnd(AbstractInsnNode insn, IRBuilder builder)1784   private void processLocalVariableEnd(AbstractInsnNode insn, IRBuilder builder) {
1785     assert !isControlFlowInstruction(insn);
1786     if (!(insn.getNext() instanceof LabelNode)) {
1787       return;
1788     }
1789     // If the label is the end of any local-variable scopes end the locals.
1790     LabelNode label = (LabelNode) insn.getNext();
1791     List<Local> locals = state.getLocalsToClose(label);
1792     for (Local local : locals) {
1793       builder.addDebugLocalEnd(local.slot.register, local.info);
1794     }
1795     state.closeLocals(locals);
1796   }
1797 
processLocalVariablesAtControlEdge(AbstractInsnNode insn, IRBuilder builder)1798   private void processLocalVariablesAtControlEdge(AbstractInsnNode insn, IRBuilder builder) {
1799     assert isControlFlowInstruction(insn) && !isReturn(insn);
1800     if (!(insn.getNext() instanceof LabelNode)) {
1801       return;
1802     }
1803     // If the label is the end of any local-variable scopes read the locals to ensure liveness.
1804     LabelNode label = (LabelNode) insn.getNext();
1805     for (Local local : state.getLocalsToClose(label)) {
1806       builder.addDebugLocalRead(local.slot.register, local.info);
1807     }
1808   }
1809 
processLocalVariablesAtExit(AbstractInsnNode insn, IRBuilder builder)1810   private void processLocalVariablesAtExit(AbstractInsnNode insn, IRBuilder builder) {
1811     assert isReturn(insn) || isThrow(insn);
1812     // Read all locals live at exit to ensure liveness.
1813     for (Local local : state.getLocals()) {
1814       if (local.info != null) {
1815         builder.addDebugLocalRead(local.slot.register, local.info);
1816       }
1817     }
1818   }
1819 
build(InsnNode insn, IRBuilder builder)1820   private void build(InsnNode insn, IRBuilder builder) {
1821     int opcode = insn.getOpcode();
1822     switch (opcode) {
1823       case Opcodes.NOP:
1824         // Intentionally left empty.
1825         break;
1826       case Opcodes.ACONST_NULL:
1827         builder.addNullConst(state.push(JarState.NULL_TYPE), 0);
1828         break;
1829       case Opcodes.ICONST_M1:
1830       case Opcodes.ICONST_0:
1831       case Opcodes.ICONST_1:
1832       case Opcodes.ICONST_2:
1833       case Opcodes.ICONST_3:
1834       case Opcodes.ICONST_4:
1835       case Opcodes.ICONST_5:
1836         builder.addIntConst(state.push(Type.INT_TYPE), opcode - Opcodes.ICONST_0);
1837         break;
1838       case Opcodes.LCONST_0:
1839       case Opcodes.LCONST_1:
1840         builder.addLongConst(state.push(Type.LONG_TYPE), opcode - Opcodes.LCONST_0);
1841         break;
1842       case Opcodes.FCONST_0:
1843       case Opcodes.FCONST_1:
1844       case Opcodes.FCONST_2:
1845         builder.addFloatConst(state.push(Type.FLOAT_TYPE),
1846             Float.floatToRawIntBits(opcode - Opcodes.FCONST_0));
1847         break;
1848       case Opcodes.DCONST_0:
1849       case Opcodes.DCONST_1:
1850         builder.addDoubleConst(state.push(Type.DOUBLE_TYPE),
1851             Double.doubleToRawLongBits(opcode - Opcodes.DCONST_0));
1852         break;
1853       case Opcodes.IALOAD:
1854       case Opcodes.LALOAD:
1855       case Opcodes.FALOAD:
1856       case Opcodes.DALOAD:
1857       case Opcodes.AALOAD:
1858       case Opcodes.BALOAD:
1859       case Opcodes.CALOAD:
1860       case Opcodes.SALOAD: {
1861         Slot index = state.pop(Type.INT_TYPE);
1862         Slot array = state.pop(JarState.ARRAY_TYPE);
1863         Type elementType = getArrayElementType(array.type);
1864         if (elementType == null) {
1865           elementType = getArrayElementTypeForOpcode(opcode);
1866         }
1867         int dest = state.push(elementType);
1868         assert isCompatibleArrayElementType(opcode, elementType);
1869         builder.addArrayGet(memberType(elementType), dest, array.register, index.register);
1870         break;
1871       }
1872       case Opcodes.IASTORE:
1873       case Opcodes.LASTORE:
1874       case Opcodes.FASTORE:
1875       case Opcodes.DASTORE:
1876       case Opcodes.AASTORE:
1877       case Opcodes.BASTORE:
1878       case Opcodes.CASTORE:
1879       case Opcodes.SASTORE: {
1880         Slot value = state.pop();
1881         Slot index = state.pop(Type.INT_TYPE);
1882         Slot array = state.pop(JarState.ARRAY_TYPE);
1883         Type elementType = getArrayElementType(array.type);
1884         if (elementType == null) {
1885           elementType = getArrayElementTypeForOpcode(opcode);
1886         }
1887         assert isCompatibleArrayElementType(opcode, elementType);
1888         assert isCompatibleArrayElementType(opcode, value.type);
1889         builder.addArrayPut(
1890             memberType(elementType), value.register, array.register, index.register);
1891         break;
1892       }
1893       case Opcodes.POP: {
1894         Slot value = state.pop();
1895         assert value.isCategory1();
1896         break;
1897       }
1898       case Opcodes.POP2: {
1899         Slot value = state.pop();
1900         if (value.isCategory1()) {
1901           Slot value2 = state.pop();
1902           assert value2.isCategory1();
1903         }
1904         break;
1905       }
1906       case Opcodes.DUP: {
1907         Slot value = state.peek();
1908         assert value.isCategory1();
1909         int copy = state.push(value.type);
1910         builder.addMove(moveType(value.type), copy, value.register);
1911         break;
1912       }
1913       case Opcodes.DUP_X1: {
1914         // Stack transformation: ..., v2, v1 -> ..., v1, v2, v1
1915         Slot value1 = state.pop();
1916         Slot value2 = state.pop();
1917         assert value1.isCategory1() && value2.isCategory1();
1918         int stack2 = state.push(value1.type);
1919         int stack1 = state.push(value2.type);
1920         int stack0 = state.push(value1.type);
1921         assert value2.register == stack2;
1922         assert value1.register == stack1;
1923         // stack0 is new top-of-stack.
1924         builder.addMove(moveType(value1.type), stack0, stack1);
1925         builder.addMove(moveType(value2.type), stack1, stack2);
1926         builder.addMove(moveType(value1.type), stack2, stack0);
1927         break;
1928       }
1929       case Opcodes.DUP_X2: {
1930         Slot value1 = state.pop();
1931         Slot value2 = state.pop();
1932         assert value1.isCategory1();
1933         if (value2.isCategory1()) {
1934           Slot value3 = state.pop();
1935           assert value3.isCategory1();
1936           // Stack transformation: ..., v3, v2, v1 -> ..., v1, v3, v2, v1
1937           dupOneBelowTwo(value3, value2, value1, builder);
1938         } else {
1939           // Stack transformation: ..., w2, v1 -> ..., v1, w2, v1
1940           dupOneBelowOne(value2, value1, builder);
1941         }
1942         break;
1943       }
1944       case Opcodes.DUP2: {
1945         Slot value1 = state.pop();
1946         if (value1.isCategory1()) {
1947           Slot value2 = state.pop();
1948           // Stack transformation: ..., v2, v1 -> ..., v2, v1, v2, v1
1949           assert value2.isCategory1();
1950           state.push(value2.type);
1951           state.push(value1.type);
1952           int copy2 = state.push(value2.type);
1953           int copy1 = state.push(value1.type);
1954           builder.addMove(moveType(value1.type), copy1, value1.register);
1955           builder.addMove(moveType(value2.type), copy2, value2.register);
1956         } else {
1957           // Stack transformation: ..., w1 -> ..., w1, w1
1958           state.push(value1.type);
1959           int copy1 = state.push(value1.type);
1960           builder.addMove(moveType(value1.type), copy1, value1.register);
1961         }
1962         break;
1963       }
1964       case Opcodes.DUP2_X1: {
1965         Slot value1 = state.pop();
1966         Slot value2 = state.pop();
1967         assert value2.isCategory1();
1968         if (value1.isCategory1()) {
1969           // Stack transformation: ..., v3, v2, v1 -> v2, v1, v3, v2, v1
1970           Slot value3 = state.pop();
1971           assert value3.isCategory1();
1972           dupTwoBelowOne(value3, value2, value1, builder);
1973         } else {
1974           // Stack transformation: ..., v2, w1 -> ..., w1, v2, w1
1975           dupOneBelowOne(value2, value1, builder);
1976         }
1977         break;
1978       }
1979       case Opcodes.DUP2_X2: {
1980         Slot value1 = state.pop();
1981         Slot value2 = state.pop();
1982         if (!value1.isCategory1() && !value2.isCategory1()) {
1983           // State transformation: ..., w2, w1 -> w1, w2, w1
1984           dupOneBelowOne(value2, value1, builder);
1985         } else {
1986           Slot value3 = state.pop();
1987           if (!value1.isCategory1()) {
1988             assert value2.isCategory1();
1989             assert value3.isCategory1();
1990             // State transformation: ..., v3, v2, w1 -> w1, v3, v2, w1
1991             dupOneBelowTwo(value3, value2, value1, builder);
1992           } else if (!value3.isCategory1()) {
1993             assert value1.isCategory1();
1994             assert value2.isCategory1();
1995             // State transformation: ..., w3, v2, v1 -> v2, v1, w3, v2, v1
1996             dupTwoBelowOne(value3, value2, value1, builder);
1997           } else {
1998             Slot value4 = state.pop();
1999             assert value1.isCategory1();
2000             assert value2.isCategory1();
2001             assert value3.isCategory1();
2002             assert value4.isCategory1();
2003             // State transformation: ..., v4, v3, v2, v1 -> v2, v1, v4, v3, v2, v1
2004             dupTwoBelowTwo(value4, value3, value2, value1, builder);
2005           }
2006         }
2007         break;
2008       }
2009       case Opcodes.SWAP: {
2010         Slot value1 = state.pop();
2011         Slot value2 = state.pop();
2012         assert value1.isCategory1() && value2.isCategory1();
2013         state.push(value1.type);
2014         state.push(value2.type);
2015         int tmp = state.push(value1.type);
2016         builder.addMove(moveType(value1.type), tmp, value1.register);
2017         builder.addMove(moveType(value2.type), value1.register, value2.register);
2018         builder.addMove(moveType(value1.type), value2.register, tmp);
2019         state.pop(); // Remove temp.
2020         break;
2021       }
2022       case Opcodes.IADD:
2023       case Opcodes.LADD:
2024       case Opcodes.FADD:
2025       case Opcodes.DADD:
2026       case Opcodes.ISUB:
2027       case Opcodes.LSUB:
2028       case Opcodes.FSUB:
2029       case Opcodes.DSUB:
2030       case Opcodes.IMUL:
2031       case Opcodes.LMUL:
2032       case Opcodes.FMUL:
2033       case Opcodes.DMUL:
2034       case Opcodes.IDIV:
2035       case Opcodes.LDIV:
2036       case Opcodes.FDIV:
2037       case Opcodes.DDIV:
2038       case Opcodes.IREM:
2039       case Opcodes.LREM:
2040       case Opcodes.FREM:
2041       case Opcodes.DREM: {
2042         Type type = opType(opcode);
2043         NumericType numericType = numericType(type);
2044         int right = state.pop(type).register;
2045         int left = state.pop(type).register;
2046         int dest = state.push(type);
2047         if (opcode <= Opcodes.DADD) {
2048           builder.addAdd(numericType, dest, left, right);
2049         } else if (opcode <= Opcodes.DSUB) {
2050           builder.addSub(numericType, dest, left, right);
2051         } else if (opcode <= Opcodes.DMUL) {
2052           builder.addMul(numericType, dest, left, right);
2053         } else if (opcode <= Opcodes.DDIV) {
2054           builder.addDiv(numericType, dest, left, right);
2055         } else {
2056           assert Opcodes.IREM <= opcode && opcode <= Opcodes.DREM;
2057           builder.addRem(numericType, dest, left, right);
2058         }
2059         break;
2060       }
2061       case Opcodes.INEG:
2062       case Opcodes.LNEG:
2063       case Opcodes.FNEG:
2064       case Opcodes.DNEG: {
2065         Type type = opType(opcode);
2066         NumericType numericType = numericType(type);
2067         int value = state.pop(type).register;
2068         int dest = state.push(type);
2069         builder.addNeg(numericType, dest, value);
2070         break;
2071       }
2072       case Opcodes.ISHL:
2073       case Opcodes.LSHL:
2074       case Opcodes.ISHR:
2075       case Opcodes.LSHR:
2076       case Opcodes.IUSHR:
2077       case Opcodes.LUSHR: {
2078         Type type = opType(opcode);
2079         NumericType numericType = numericType(type);
2080         int right = state.pop(Type.INT_TYPE).register;
2081         int left = state.pop(type).register;
2082         int dest = state.push(type);
2083         if (opcode <= Opcodes.LSHL) {
2084           builder.addShl(numericType, dest, left, right);
2085         } else if (opcode <= Opcodes.LSHR) {
2086           builder.addShr(numericType, dest, left, right);
2087         } else {
2088           assert opcode == Opcodes.IUSHR || opcode == Opcodes.LUSHR;
2089           builder.addUshr(numericType, dest, left, right);
2090         }
2091         break;
2092       }
2093       case Opcodes.IAND:
2094       case Opcodes.LAND: {
2095         Type type = opcode == Opcodes.IAND ? Type.INT_TYPE : Type.LONG_TYPE;
2096         int right = state.pop(type).register;
2097         int left = state.pop(type).register;
2098         int dest = state.push(type);
2099         builder.addAnd(numericType(type), dest, left, right);
2100         break;
2101       }
2102       case Opcodes.IOR:
2103       case Opcodes.LOR: {
2104         Type type = opcode == Opcodes.IOR ? Type.INT_TYPE : Type.LONG_TYPE;
2105         int right = state.pop(type).register;
2106         int left = state.pop(type).register;
2107         int dest = state.push(type);
2108         builder.addOr(numericType(type), dest, left, right);
2109         break;
2110       }
2111       case Opcodes.IXOR:
2112       case Opcodes.LXOR: {
2113         Type type = opcode == Opcodes.IXOR ? Type.INT_TYPE : Type.LONG_TYPE;
2114         int right = state.pop(type).register;
2115         int left = state.pop(type).register;
2116         int dest = state.push(type);
2117         builder.addXor(numericType(type), dest, left, right);
2118         break;
2119       }
2120       case Opcodes.I2L:
2121         buildConversion(Type.INT_TYPE, Type.LONG_TYPE, builder);
2122         break;
2123       case Opcodes.I2F:
2124         buildConversion(Type.INT_TYPE, Type.FLOAT_TYPE, builder);
2125         break;
2126       case Opcodes.I2D:
2127         buildConversion(Type.INT_TYPE, Type.DOUBLE_TYPE, builder);
2128         break;
2129       case Opcodes.L2I:
2130         buildConversion(Type.LONG_TYPE, Type.INT_TYPE, builder);
2131         break;
2132       case Opcodes.L2F:
2133         buildConversion(Type.LONG_TYPE, Type.FLOAT_TYPE, builder);
2134         break;
2135       case Opcodes.L2D:
2136         buildConversion(Type.LONG_TYPE, Type.DOUBLE_TYPE, builder);
2137         break;
2138       case Opcodes.F2I:
2139         buildConversion(Type.FLOAT_TYPE, Type.INT_TYPE, builder);
2140         break;
2141       case Opcodes.F2L:
2142         buildConversion(Type.FLOAT_TYPE, Type.LONG_TYPE, builder);
2143         break;
2144       case Opcodes.F2D:
2145         buildConversion(Type.FLOAT_TYPE, Type.DOUBLE_TYPE, builder);
2146         break;
2147       case Opcodes.D2I:
2148         buildConversion(Type.DOUBLE_TYPE, Type.INT_TYPE, builder);
2149         break;
2150       case Opcodes.D2L:
2151         buildConversion(Type.DOUBLE_TYPE, Type.LONG_TYPE, builder);
2152         break;
2153       case Opcodes.D2F:
2154         buildConversion(Type.DOUBLE_TYPE, Type.FLOAT_TYPE, builder);
2155         break;
2156       case Opcodes.I2B:
2157         buildConversion(Type.INT_TYPE, Type.BYTE_TYPE, builder);
2158         break;
2159       case Opcodes.I2C:
2160         buildConversion(Type.INT_TYPE, Type.CHAR_TYPE, builder);
2161         break;
2162       case Opcodes.I2S:
2163         buildConversion(Type.INT_TYPE, Type.SHORT_TYPE, builder);
2164         break;
2165       case Opcodes.LCMP: {
2166         Slot right = state.pop(Type.LONG_TYPE);
2167         Slot left = state.pop(Type.LONG_TYPE);
2168         int dest = state.push(Type.INT_TYPE);
2169         builder.addCmp(NumericType.LONG, Bias.NONE, dest, left.register, right.register);
2170         break;
2171       }
2172       case Opcodes.FCMPL:
2173       case Opcodes.FCMPG: {
2174         Slot right = state.pop(Type.FLOAT_TYPE);
2175         Slot left = state.pop(Type.FLOAT_TYPE);
2176         int dest = state.push(Type.INT_TYPE);
2177         Bias bias = opcode == Opcodes.FCMPL ? Bias.LT : Bias.GT;
2178         builder.addCmp(NumericType.FLOAT, bias, dest, left.register, right.register);
2179         break;
2180       }
2181       case Opcodes.DCMPL:
2182       case Opcodes.DCMPG: {
2183         Slot right = state.pop(Type.DOUBLE_TYPE);
2184         Slot left = state.pop(Type.DOUBLE_TYPE);
2185         int dest = state.push(Type.INT_TYPE);
2186         Bias bias = opcode == Opcodes.DCMPL ? Bias.LT : Bias.GT;
2187         builder.addCmp(NumericType.DOUBLE, bias, dest, left.register, right.register);
2188         break;
2189       }
2190       case Opcodes.IRETURN: {
2191         Slot value = state.pop(Type.INT_TYPE);
2192         addReturn(insn, MoveType.SINGLE, value.register, builder);
2193         break;
2194       }
2195       case Opcodes.LRETURN: {
2196         Slot value = state.pop(Type.LONG_TYPE);
2197         addReturn(insn, MoveType.WIDE, value.register, builder);
2198         break;
2199       }
2200       case Opcodes.FRETURN: {
2201         Slot value = state.pop(Type.FLOAT_TYPE);
2202         addReturn(insn, MoveType.SINGLE, value.register, builder);
2203         break;
2204       }
2205       case Opcodes.DRETURN: {
2206         Slot value = state.pop(Type.DOUBLE_TYPE);
2207         addReturn(insn, MoveType.WIDE, value.register, builder);
2208         break;
2209       }
2210       case Opcodes.ARETURN: {
2211         Slot obj = state.pop(JarState.REFERENCE_TYPE);
2212         addReturn(insn, MoveType.OBJECT, obj.register, builder);
2213         break;
2214       }
2215       case Opcodes.RETURN: {
2216         addReturn(insn, null, -1, builder);
2217         break;
2218       }
2219       case Opcodes.ARRAYLENGTH: {
2220         Slot array = state.pop(JarState.ARRAY_TYPE);
2221         int dest = state.push(Type.INT_TYPE);
2222         builder.addArrayLength(dest, array.register);
2223         break;
2224       }
2225       case Opcodes.ATHROW: {
2226         Slot object = state.pop(JarState.OBJECT_TYPE);
2227         addThrow(insn, object.register, builder);
2228         break;
2229       }
2230       case Opcodes.MONITORENTER: {
2231         Slot object = state.pop(JarState.REFERENCE_TYPE);
2232         builder.addMonitor(Monitor.Type.ENTER, object.register);
2233         break;
2234       }
2235       case Opcodes.MONITOREXIT: {
2236         Slot object = state.pop(JarState.REFERENCE_TYPE);
2237         builder.addMonitor(Monitor.Type.EXIT, object.register);
2238         break;
2239       }
2240       default:
2241         throw new Unreachable("Unexpected Insn opcode: " + insn.getOpcode());
2242     }
2243   }
2244 
addThrow(InsnNode insn, int register, IRBuilder builder)2245   private void addThrow(InsnNode insn, int register, IRBuilder builder) {
2246     if (getTryHandlers(insn).isEmpty()) {
2247       processLocalVariablesAtExit(insn, builder);
2248     } else {
2249       processLocalVariablesAtControlEdge(insn, builder);
2250     }
2251     builder.addThrow(register);
2252   }
2253 
addReturn(InsnNode insn, MoveType type, int register, IRBuilder builder)2254   private void addReturn(InsnNode insn, MoveType type, int register, IRBuilder builder) {
2255     processLocalVariablesAtExit(insn, builder);
2256     if (type == null) {
2257       assert register == -1;
2258       builder.addReturn();
2259     } else {
2260       builder.addReturn(type, register);
2261     }
2262   }
2263 
dupOneBelowTwo(Slot value3, Slot value2, Slot value1, IRBuilder builder)2264   private void dupOneBelowTwo(Slot value3, Slot value2, Slot value1, IRBuilder builder) {
2265     int stack3 = state.push(value1.type);
2266     int stack2 = state.push(value3.type);
2267     int stack1 = state.push(value2.type);
2268     int stack0 = state.push(value1.type);
2269     assert value3.register == stack3;
2270     assert value2.register == stack2;
2271     assert value1.register == stack1;
2272     builder.addMove(moveType(value1.type), stack0, stack1);
2273     builder.addMove(moveType(value2.type), stack1, stack2);
2274     builder.addMove(moveType(value3.type), stack2, stack3);
2275     builder.addMove(moveType(value1.type), stack3, stack0);
2276   }
2277 
dupOneBelowOne(Slot value2, Slot value1, IRBuilder builder)2278   private void dupOneBelowOne(Slot value2, Slot value1, IRBuilder builder) {
2279     int stack2 = state.push(value1.type);
2280     int stack1 = state.push(value2.type);
2281     int stack0 = state.push(value1.type);
2282     assert value2.register == stack2;
2283     assert value1.register == stack1;
2284     builder.addMove(moveType(value1.type), stack0, stack1);
2285     builder.addMove(moveType(value2.type), stack1, stack2);
2286     builder.addMove(moveType(value1.type), stack2, stack0);
2287   }
2288 
dupTwoBelowOne(Slot value3, Slot value2, Slot value1, IRBuilder builder)2289   private void dupTwoBelowOne(Slot value3, Slot value2, Slot value1, IRBuilder builder) {
2290     int stack4 = state.push(value2.type);
2291     int stack3 = state.push(value1.type);
2292     int stack2 = state.push(value3.type);
2293     int stack1 = state.push(value2.type);
2294     int stack0 = state.push(value1.type);
2295     assert value3.register == stack4;
2296     assert value2.register == stack3;
2297     assert value1.register == stack2;
2298     builder.addMove(moveType(value1.type), stack0, stack2);
2299     builder.addMove(moveType(value2.type), stack1, stack3);
2300     builder.addMove(moveType(value3.type), stack2, stack4);
2301     builder.addMove(moveType(value1.type), stack3, stack0);
2302     builder.addMove(moveType(value2.type), stack4, stack1);
2303   }
2304 
dupTwoBelowTwo(Slot value4, Slot value3, Slot value2, Slot value1, IRBuilder builder)2305   private void dupTwoBelowTwo(Slot value4, Slot value3, Slot value2, Slot value1,
2306       IRBuilder builder) {
2307     int stack5 = state.push(value2.type);
2308     int stack4 = state.push(value1.type);
2309     int stack3 = state.push(value4.type);
2310     int stack2 = state.push(value3.type);
2311     int stack1 = state.push(value2.type);
2312     int stack0 = state.push(value1.type);
2313     assert value4.register == stack5;
2314     assert value3.register == stack4;
2315     assert value2.register == stack3;
2316     assert value1.register == stack2;
2317     builder.addMove(moveType(value1.type), stack0, stack2);
2318     builder.addMove(moveType(value2.type), stack1, stack3);
2319     builder.addMove(moveType(value3.type), stack2, stack4);
2320     builder.addMove(moveType(value3.type), stack3, stack5);
2321     builder.addMove(moveType(value1.type), stack4, stack0);
2322     builder.addMove(moveType(value2.type), stack5, stack1);
2323   }
2324 
buildConversion(Type from, Type to, IRBuilder builder)2325   private void buildConversion(Type from, Type to, IRBuilder builder) {
2326     int source = state.pop(from).register;
2327     int dest = state.push(to);
2328     builder.addConversion(numericType(to), numericType(from), dest, source);
2329   }
2330 
build(IntInsnNode insn, IRBuilder builder)2331   private void build(IntInsnNode insn, IRBuilder builder) {
2332     switch (insn.getOpcode()) {
2333       case Opcodes.BIPUSH:
2334       case Opcodes.SIPUSH: {
2335         int dest = state.push(Type.INT_TYPE);
2336         builder.addIntConst(dest, insn.operand);
2337         break;
2338       }
2339       case Opcodes.NEWARRAY: {
2340         String desc = arrayTypeDesc(insn.operand);
2341         Type type = Type.getType(desc);
2342         DexType dexType = application.getTypeFromDescriptor(desc);
2343         int count = state.pop(Type.INT_TYPE).register;
2344         int array = state.push(type);
2345         builder.addNewArrayEmpty(array, count, dexType);
2346         break;
2347       }
2348       default:
2349         throw new Unreachable("Unexpected IntInsn opcode: " + insn.getOpcode());
2350     }
2351   }
2352 
build(VarInsnNode insn, IRBuilder builder)2353   private void build(VarInsnNode insn, IRBuilder builder) {
2354     int opcode = insn.getOpcode();
2355     Type expectedType;
2356     switch (opcode) {
2357       case Opcodes.ILOAD:
2358       case Opcodes.ISTORE:
2359         expectedType = Type.INT_TYPE;
2360         break;
2361       case Opcodes.FLOAD:
2362       case Opcodes.FSTORE:
2363         expectedType = Type.FLOAT_TYPE;
2364         break;
2365       case Opcodes.LLOAD:
2366       case Opcodes.LSTORE:
2367         expectedType = Type.LONG_TYPE;
2368         break;
2369       case Opcodes.DLOAD:
2370       case Opcodes.DSTORE:
2371         expectedType = Type.DOUBLE_TYPE;
2372         break;
2373       case Opcodes.ALOAD:
2374       case Opcodes.ASTORE:
2375         expectedType = JarState.REFERENCE_TYPE;
2376         break;
2377       case Opcodes.RET: {
2378         throw new Unreachable("RET should be handled by the ASM jsr inliner");
2379       }
2380       default:
2381         throw new Unreachable("Unexpected VarInsn opcode: " + insn.getOpcode());
2382     }
2383     if (Opcodes.ILOAD <= opcode && opcode <= Opcodes.ALOAD) {
2384       Slot src = state.readLocal(insn.var, expectedType);
2385       int dest = state.push(src.type);
2386       builder.addMove(moveType(src.type), dest, src.register);
2387     } else {
2388       assert Opcodes.ISTORE <= opcode && opcode <= Opcodes.ASTORE;
2389       Slot src = state.pop(expectedType);
2390       int dest = state.writeLocal(insn.var, src.type);
2391       builder.addMove(moveType(src.type), dest, src.register);
2392     }
2393   }
2394 
build(TypeInsnNode insn, IRBuilder builder)2395   private void build(TypeInsnNode insn, IRBuilder builder) {
2396     Type type = Type.getObjectType(insn.desc);
2397     switch (insn.getOpcode()) {
2398       case Opcodes.NEW: {
2399         DexType dexType = application.getTypeFromName(insn.desc);
2400         int dest = state.push(type);
2401         builder.addNewInstance(dest, dexType);
2402         break;
2403       }
2404       case Opcodes.ANEWARRAY: {
2405         Type arrayType = makeArrayType(type);
2406         DexType dexArrayType = application.getTypeFromDescriptor(arrayType.getDescriptor());
2407         int count = state.pop(Type.INT_TYPE).register;
2408         int dest = state.push(arrayType);
2409         builder.addNewArrayEmpty(dest, count, dexArrayType);
2410         break;
2411       }
2412       case Opcodes.CHECKCAST: {
2413         DexType dexType = application.getTypeFromDescriptor(type.getDescriptor());
2414         // Pop the top value and push it back on with the checked type.
2415         state.pop(type);
2416         int object = state.push(type);
2417         builder.addCheckCast(object, dexType);
2418         break;
2419       }
2420       case Opcodes.INSTANCEOF: {
2421         int obj = state.pop(JarState.REFERENCE_TYPE).register;
2422         int dest = state.push(Type.INT_TYPE);
2423         DexType dexType = application.getTypeFromDescriptor(type.getDescriptor());
2424         builder.addInstanceOf(dest, obj, dexType);
2425         break;
2426       }
2427       default:
2428         throw new Unreachable("Unexpected TypeInsn opcode: " + insn.getOpcode());
2429     }
2430   }
2431 
build(FieldInsnNode insn, IRBuilder builder)2432   private void build(FieldInsnNode insn, IRBuilder builder) {
2433     DexField field = application.getField(insn.owner, insn.name, insn.desc);
2434     Type type = Type.getType(insn.desc);
2435     MemberType fieldType = memberType(insn.desc);
2436     switch (insn.getOpcode()) {
2437       case Opcodes.GETSTATIC:
2438         builder.addStaticGet(fieldType, state.push(type), field);
2439         break;
2440       case Opcodes.PUTSTATIC:
2441         builder.addStaticPut(fieldType, state.pop(type).register, field);
2442         break;
2443       case Opcodes.GETFIELD: {
2444         Slot object = state.pop(JarState.OBJECT_TYPE);
2445         int dest = state.push(type);
2446         builder.addInstanceGet(fieldType, dest, object.register, field);
2447         break;
2448       }
2449       case Opcodes.PUTFIELD: {
2450         Slot value = state.pop(type);
2451         Slot object = state.pop(JarState.OBJECT_TYPE);
2452         builder.addInstancePut(fieldType, value.register, object.register, field);
2453         break;
2454       }
2455       default:
2456         throw new Unreachable("Unexpected FieldInsn opcode: " + insn.getOpcode());
2457     }
2458   }
2459 
build(MethodInsnNode insn, IRBuilder builder)2460   private void build(MethodInsnNode insn, IRBuilder builder) {
2461     // Resolve the target method of the invoke.
2462     DexMethod method = application.getMethod(insn.owner, insn.name, insn.desc);
2463 
2464     buildInvoke(
2465         insn.desc,
2466         Type.getObjectType(insn.owner),
2467         insn.getOpcode() != Opcodes.INVOKESTATIC,
2468         builder,
2469         (types, registers) -> {
2470           Invoke.Type invokeType = invokeType(insn);
2471           DexProto callSiteProto = null;
2472           DexMethod targetMethod = method;
2473           if (invokeType == Invoke.Type.POLYMORPHIC) {
2474             targetMethod = application.getMethod(
2475                 insn.owner, insn.name, METHODHANDLE_INVOKE_OR_INVOKEEXACT_DESC);
2476             callSiteProto = application.getProto(insn.desc);
2477           }
2478           builder.addInvoke(invokeType, targetMethod, callSiteProto, types, registers);
2479         });
2480   }
2481 
buildInvoke( String methodDesc, Type methodOwner, boolean addImplicitReceiver, IRBuilder builder, BiConsumer<List<MoveType>, List<Integer>> creator)2482   private void buildInvoke(
2483       String methodDesc, Type methodOwner, boolean addImplicitReceiver,
2484       IRBuilder builder, BiConsumer<List<MoveType>, List<Integer>> creator) {
2485 
2486     // Build the argument list of the form [owner, param1, ..., paramN].
2487     // The arguments are in reverse order on the stack, so we pop off the parameters here.
2488     Type[] parameterTypes = Type.getArgumentTypes(methodDesc);
2489     Slot[] parameterRegisters = state.popReverse(parameterTypes.length);
2490 
2491     List<MoveType> types = new ArrayList<>(parameterTypes.length + 1);
2492     List<Integer> registers = new ArrayList<>(parameterTypes.length + 1);
2493 
2494     // Add receiver argument for non-static calls.
2495     if (addImplicitReceiver) {
2496       addArgument(types, registers, methodOwner, state.pop());
2497     }
2498 
2499     // The remaining arguments are the parameters of the method.
2500     for (int i = 0; i < parameterTypes.length; i++) {
2501       addArgument(types, registers, parameterTypes[i], parameterRegisters[i]);
2502     }
2503 
2504     // Create the invoke.
2505     creator.accept(types, registers);
2506 
2507     // Move the result to the "top of stack".
2508     Type returnType = Type.getReturnType(methodDesc);
2509     if (returnType != Type.VOID_TYPE) {
2510       builder.addMoveResult(moveType(returnType), state.push(returnType));
2511     }
2512   }
2513 
addArgument(List<MoveType> types, List<Integer> registers, Type type, Slot slot)2514   private static void addArgument(List<MoveType> types, List<Integer> registers, Type type,
2515       Slot slot) {
2516     assert slot.isCompatibleWith(type);
2517     types.add(moveType(type));
2518     registers.add(slot.register);
2519   }
2520 
build(InvokeDynamicInsnNode insn, IRBuilder builder)2521   private void build(InvokeDynamicInsnNode insn, IRBuilder builder) {
2522     // Bootstrap method
2523     Handle bsmHandle = insn.bsm;
2524     if (bsmHandle.getTag() != Opcodes.H_INVOKESTATIC &&
2525         bsmHandle.getTag() != Opcodes.H_NEWINVOKESPECIAL) {
2526       throw new Unreachable(
2527           "Bootstrap handle is not yet supported: tag == " + bsmHandle.getTag());
2528     }
2529     // Resolve the bootstrap method.
2530     DexMethodHandle bootstrapMethod = getMethodHandle(application, bsmHandle);
2531 
2532     // Decode static bootstrap arguments
2533     List<DexValue> bootstrapArgs = new ArrayList<>();
2534     for (Object arg : insn.bsmArgs) {
2535       bootstrapArgs.add(decodeBootstrapArgument(arg));
2536     }
2537 
2538     // Construct call site
2539     DexCallSite callSite = application
2540         .getCallSite(insn.name, insn.desc, bootstrapMethod, bootstrapArgs);
2541 
2542     buildInvoke(insn.desc, null /* Not needed */,
2543         false /* Receiver is passed explicitly */, builder,
2544         (types, registers) -> builder.addInvokeCustom(callSite, types, registers));
2545   }
2546 
decodeBootstrapArgument(Object value)2547   private DexValue decodeBootstrapArgument(Object value) {
2548     if (value instanceof Integer) {
2549       return DexValue.DexValueInt.create((Integer) value);
2550     } else if (value instanceof Long) {
2551       return DexValue.DexValueLong.create((Long) value);
2552     } else if (value instanceof Float) {
2553       return DexValue.DexValueFloat.create((Float) value);
2554     } else if (value instanceof Double) {
2555       return DexValue.DexValueDouble.create((Double) value);
2556     } else if (value instanceof String) {
2557       return new DexValue.DexValueString(application.getString((String) value));
2558 
2559     } else if (value instanceof Type) {
2560       Type type = (Type) value;
2561       switch (type.getSort()) {
2562         case Type.OBJECT:
2563           return new DexValue.DexValueType(
2564               application.getTypeFromDescriptor(((Type) value).getDescriptor()));
2565         case Type.METHOD:
2566           return new DexValue.DexValueMethodType(
2567               application.getProto(((Type) value).getDescriptor()));
2568       }
2569       throw new Unreachable("Type sort is not supported: " + type.getSort());
2570 
2571     } else if (value instanceof Handle) {
2572       return new DexValue.DexValueMethodHandle(getMethodHandle(application, (Handle) value));
2573     } else {
2574       throw new Unreachable(
2575           "Unsupported bootstrap static argument of type " + value.getClass().getSimpleName());
2576     }
2577   }
2578 
getMethodHandle(JarApplicationReader application, Handle handle)2579   private DexMethodHandle getMethodHandle(JarApplicationReader application, Handle handle) {
2580     MethodHandleType methodHandleType = getMethodHandleType(handle);
2581     Descriptor<? extends DexItem, ? extends Descriptor> descriptor =
2582         methodHandleType.isFieldType()
2583             ? application.getField(handle.getOwner(), handle.getName(), handle.getDesc())
2584             : application.getMethod(handle.getOwner(), handle.getName(), handle.getDesc());
2585     return application.getMethodHandle(methodHandleType, descriptor);
2586   }
2587 
getMethodHandleType(Handle handle)2588   private MethodHandleType getMethodHandleType(Handle handle) {
2589     switch (handle.getTag()) {
2590       case Opcodes.H_GETFIELD:
2591         return MethodHandleType.INSTANCE_GET;
2592       case Opcodes.H_GETSTATIC:
2593         return MethodHandleType.STATIC_GET;
2594       case Opcodes.H_PUTFIELD:
2595         return MethodHandleType.INSTANCE_PUT;
2596       case Opcodes.H_PUTSTATIC:
2597         return MethodHandleType.STATIC_PUT;
2598       case Opcodes.H_INVOKESPECIAL:
2599         DexType owner = application.getTypeFromName(handle.getOwner());
2600         if (owner == clazz || handle.getName().equals(Constants.INSTANCE_INITIALIZER_NAME)) {
2601           return MethodHandleType.INVOKE_INSTANCE;
2602         } else {
2603           return MethodHandleType.INVOKE_SUPER;
2604         }
2605       case Opcodes.H_INVOKEVIRTUAL:
2606         return MethodHandleType.INVOKE_INSTANCE;
2607       case Opcodes.H_INVOKEINTERFACE:
2608         return MethodHandleType.INVOKE_INTERFACE;
2609       case Opcodes.H_INVOKESTATIC:
2610         return MethodHandleType.INVOKE_STATIC;
2611       case Opcodes.H_NEWINVOKESPECIAL:
2612         return MethodHandleType.INVOKE_CONSTRUCTOR;
2613       default:
2614         throw new Unreachable("MethodHandle tag is not supported: " + handle.getTag());
2615     }
2616   }
2617 
build(JumpInsnNode insn, IRBuilder builder)2618   private void build(JumpInsnNode insn, IRBuilder builder) {
2619     processLocalVariablesAtControlEdge(insn, builder);
2620     int[] targets = getTargets(insn);
2621     int opcode = insn.getOpcode();
2622     if (Opcodes.IFEQ <= opcode && opcode <= Opcodes.IF_ACMPNE) {
2623       assert targets.length == 2;
2624       if (opcode <= Opcodes.IFLE) {
2625         Slot value = state.pop(Type.INT_TYPE);
2626         builder.addIfZero(ifType(opcode), value.register, targets[0], targets[1]);
2627       } else {
2628         Type expectedType = opcode < Opcodes.IF_ACMPEQ ? Type.INT_TYPE : JarState.REFERENCE_TYPE;
2629         Slot value2 = state.pop(expectedType);
2630         Slot value1 = state.pop(expectedType);
2631         builder.addIf(ifType(opcode), value1.register, value2.register, targets[0], targets[1]);
2632       }
2633     } else {
2634       switch (opcode) {
2635         case Opcodes.GOTO: {
2636           assert targets.length == 1;
2637           builder.addGoto(targets[0]);
2638           break;
2639         }
2640         case Opcodes.IFNULL:
2641         case Opcodes.IFNONNULL: {
2642           Slot value = state.pop(JarState.REFERENCE_TYPE);
2643           If.Type type = opcode == Opcodes.IFNULL ? If.Type.EQ : If.Type.NE;
2644           builder.addIfZero(type, value.register, targets[0], targets[1]);
2645           break;
2646         }
2647         case Opcodes.JSR: {
2648           throw new Unreachable("JSR should be handled by the ASM jsr inliner");
2649         }
2650         default:
2651           throw new Unreachable("Unexpected JumpInsn opcode: " + insn.getOpcode());
2652       }
2653     }
2654   }
2655 
2656   private void build(LabelNode insn, IRBuilder builder) {
2657     // Open the scope of locals starting at this point.
2658     if (insn != initialLabel) {
2659       for (Local local : state.openLocals(insn)) {
2660         builder.addDebugLocalStart(local.slot.register, local.info);
2661       }
2662     }
2663   }
2664 
2665   private void build(LdcInsnNode insn, IRBuilder builder) {
2666     if (insn.cst instanceof Type) {
2667       Type type = (Type) insn.cst;
2668       int dest = state.push(type);
2669       builder.addConstClass(dest, application.getTypeFromDescriptor(type.getDescriptor()));
2670     } else if (insn.cst instanceof String) {
2671       int dest = state.push(STRING_TYPE);
2672       builder.addConstString(dest, application.getString((String) insn.cst));
2673     } else if (insn.cst instanceof Long) {
2674       int dest = state.push(Type.LONG_TYPE);
2675       builder.addLongConst(dest, (Long) insn.cst);
2676     } else if (insn.cst instanceof Double) {
2677       int dest = state.push(Type.DOUBLE_TYPE);
2678       builder.addDoubleConst(dest, Double.doubleToRawLongBits((Double) insn.cst));
2679     } else if (insn.cst instanceof Integer) {
2680       int dest = state.push(Type.INT_TYPE);
2681       builder.addIntConst(dest, (Integer) insn.cst);
2682     } else {
2683       assert insn.cst instanceof Float;
2684       int dest = state.push(Type.FLOAT_TYPE);
2685       builder.addFloatConst(dest, Float.floatToRawIntBits((Float) insn.cst));
2686     }
2687   }
2688 
2689   private void build(IincInsnNode insn, IRBuilder builder) {
2690     int local = state.readLocal(insn.var, Type.INT_TYPE).register;
2691     builder.addAddLiteral(NumericType.INT, local, local, insn.incr);
2692   }
2693 
2694   private void build(TableSwitchInsnNode insn, IRBuilder builder) {
2695     processLocalVariablesAtControlEdge(insn, builder);
2696     buildSwitch(insn.dflt, insn.labels, new int[]{insn.min}, builder);
2697   }
2698 
2699   private void build(LookupSwitchInsnNode insn, IRBuilder builder) {
2700     processLocalVariablesAtControlEdge(insn, builder);
2701     int[] keys = new int[insn.keys.size()];
2702     for (int i = 0; i < insn.keys.size(); i++) {
2703       keys[i] = (int) insn.keys.get(i);
2704     }
2705     buildSwitch(insn.dflt, insn.labels, keys, builder);
2706   }
2707 
2708   private void buildSwitch(LabelNode dflt, List labels, int[] keys,
2709       IRBuilder builder) {
2710     int index = state.pop(Type.INT_TYPE).register;
2711     int fallthroughOffset = getOffset(dflt);
2712     int[] labelOffsets = new int[labels.size()];
2713     for (int i = 0; i < labels.size(); i++) {
2714       int offset = getOffset((LabelNode) labels.get(i));
2715       labelOffsets[i] = offset;
2716     }
2717     builder.addSwitch(index, keys, fallthroughOffset, labelOffsets);
2718   }
2719 
2720   private void build(MultiANewArrayInsnNode insn, IRBuilder builder) {
2721     // Type of the full array.
2722     Type arrayType = Type.getObjectType(insn.desc);
2723     DexType dexArrayType = application.getType(arrayType);
2724     // Type of the members. Can itself be of array type, eg, 'int[]' for 'new int[x][y][]'
2725     DexType memberType = application.getTypeFromDescriptor(insn.desc.substring(insn.dims));
2726     // Push an array containing the dimensions of the desired multi-dimensional array.
2727     DexType dimArrayType = application.getTypeFromDescriptor(INT_ARRAY_DESC);
2728     Slot[] slots = state.popReverse(insn.dims, Type.INT_TYPE);
2729     int[] dimensions = new int[insn.dims];
2730     for (int i = 0; i < insn.dims; i++) {
2731       dimensions[i] = slots[i].register;
2732     }
2733     builder.addInvokeNewArray(dimArrayType, insn.dims, dimensions);
2734     int dimensionsDestTemp = state.push(INT_ARRAY_TYPE);
2735     builder.addMoveResult(MoveType.OBJECT, dimensionsDestTemp);
2736     // Push the class object for the member type of the array.
2737     int classDestTemp = state.push(CLASS_TYPE);
2738     builder.ensureBlockForThrowingInstruction();
2739     builder.addConstClass(classDestTemp, memberType);
2740     // Create the actual multi-dimensional array using java.lang.reflect.Array::newInstance
2741     DexType reflectArrayClass = application.getTypeFromDescriptor(REFLECT_ARRAY_DESC);
2742     DexMethod newInstance = application.getMethod(reflectArrayClass,
2743         REFLECT_ARRAY_NEW_INSTANCE_NAME, REFLECT_ARRAY_NEW_INSTANCE_DESC);
2744     List<MoveType> argumentTypes = Arrays.asList(moveType(CLASS_TYPE), moveType(INT_ARRAY_TYPE));
2745     List<Integer> argumentRegisters = Arrays.asList(classDestTemp, dimensionsDestTemp);
2746     builder.ensureBlockForThrowingInstruction();
2747     builder.addInvoke(Invoke.Type.STATIC, newInstance, null, argumentTypes, argumentRegisters);
2748     // Pop the temporaries and push the final result.
2749     state.pop(); // classDestTemp.
2750     state.pop(); // dimensionsDestTemp.
2751     int result = state.push(arrayType);
2752     builder.addMoveResult(moveType(arrayType), result);
2753     // Insert cast check to satisfy verification.
2754     builder.ensureBlockForThrowingInstruction();
2755     builder.addCheckCast(result, dexArrayType);
2756   }
2757 
2758   private void build(LineNumberNode insn, IRBuilder builder) {
2759     builder.updateCurrentDebugPosition(insn.line, null);
2760   }
2761 
2762   // Printing helpers.
2763 
2764   @Override
2765   public String toString() {
2766     StringBuilder builder = new StringBuilder();
2767     builder.append("node.name = [").append(node.name).append("]");
2768     builder.append("\n");
2769     builder.append("node.desc = ").append(node.desc);
2770     builder.append("\n");
2771     builder.append("node.maxStack = ").append(node.maxStack);
2772     builder.append("\n");
2773     builder.append("node.maxLocals = ").append(node.maxLocals);
2774     builder.append("\n");
2775     builder.append("node.locals.size = ").append(node.localVariables.size());
2776     builder.append("\n");
2777     builder.append("node.insns.size = ").append(node.instructions.size());
2778     builder.append("\n");
2779     for (int i = 0; i < parameterTypes.size(); i++) {
2780       builder.append("arg ").append(i).append(", type: ").append(parameterTypes.get(i))
2781           .append("\n");
2782     }
2783     for (int i = 0; i < node.localVariables.size(); i++) {
2784       LocalVariableNode local = (LocalVariableNode) node.localVariables.get(i);
2785       builder.append("local ").append(i)
2786           .append(", name: ").append(local.name)
2787           .append(", desc: ").append(local.desc)
2788           .append(", index: ").append(local.index)
2789           .append(", [").append(getOffset(local.start))
2790           .append("..").append(getOffset(local.end))
2791           .append("[\n");
2792     }
2793     for (int i = 0; i < node.tryCatchBlocks.size(); i++) {
2794       TryCatchBlockNode tryCatchBlockNode = (TryCatchBlockNode) node.tryCatchBlocks.get(i);
2795       builder.append("[").append(getOffset(tryCatchBlockNode.start))
2796           .append("..").append(getOffset(tryCatchBlockNode.end)).append("[ ")
2797           .append(tryCatchBlockNode.type).append(" -> ")
2798           .append(getOffset(tryCatchBlockNode.handler))
2799           .append("\n");
2800     }
2801     for (int i = 0; i < node.instructions.size(); i++) {
2802       AbstractInsnNode insn = node.instructions.get(i);
2803       builder.append(String.format("%4d: ", i)).append(instructionToString(insn));
2804     }
2805     return builder.toString();
2806   }
2807 
2808   private String instructionToString(AbstractInsnNode insn) {
2809     if (printVisitor == null) {
2810       printVisitor = new TraceMethodVisitor(new Textifier());
2811     }
2812     insn.accept(printVisitor);
2813     StringWriter writer = new StringWriter();
2814     printVisitor.p.print(new PrintWriter(writer));
2815     printVisitor.p.getText().clear();
2816     return writer.toString();
2817   }
2818 
2819   private boolean isCallToPolymorphicSignatureMethod(MethodInsnNode method) {
2820     return method.owner.equals("java/lang/invoke/MethodHandle")
2821         && (method.name.equals("invoke") || method.name.equals("invokeExact"));
2822   }
2823 }
2824