1 /*
2 * Copyright (c) 2024, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25 package java.lang.reflect.code.bytecode;
26
27 import java.lang.classfile.CodeElement;
28 import java.lang.classfile.Instruction;
29 import java.lang.classfile.Label;
30 import java.lang.classfile.Opcode;
31 import java.lang.classfile.attribute.StackMapFrameInfo;
32 import java.lang.classfile.attribute.StackMapFrameInfo.*;
33 import java.lang.classfile.attribute.StackMapTableAttribute;
34 import java.lang.classfile.instruction.*;
35 import java.lang.constant.ClassDesc;
36 import java.lang.constant.ConstantDescs;
37 import java.lang.constant.DirectMethodHandleDesc;
38 import java.lang.constant.DynamicConstantDesc;
39 import java.lang.constant.MethodTypeDesc;
40 import java.util.ArrayDeque;
41 import java.util.ArrayList;
42 import java.util.HashMap;
43 import java.util.Iterator;
44 import java.util.LinkedHashSet;
45 import java.util.List;
46 import java.util.Map;
47 import java.util.NoSuchElementException;
48 import java.util.Set;
49 import java.util.Optional;
50 import java.util.stream.Collectors;
51
52 import static java.lang.classfile.attribute.StackMapFrameInfo.SimpleVerificationTypeInfo.*;
53 import static java.lang.classfile.attribute.StackMapFrameInfo.SimpleVerificationTypeInfo.NULL;
54 import static java.lang.constant.ConstantDescs.*;
55
56 /**
57 * LocalsToVarMapper scans bytecode for slot operations, forms oriented flow graphs of the slot operation segments,
58 * analyzes the graphs and maps the segments to distinct variables, calculates each variable type and identifies
59 * single-assigned variables and variables requiring initialization in the entry block.
60 */
61 final class LocalsToVarMapper {
62
63 /**
64 * Variable identity object result of the LocalsToVarMapper analysis.
65 */
66 public static final class Variable {
67 private ClassDesc type;
68 private boolean single;
69
70 /**
71 * {@return Variable type}
72 */
73 ClassDesc type() {
74 return type;
75 }
76
77 /**
78 * {@return whether the variable has only single assignement}
79 */
80 boolean hasSingleAssignment() {
81 return single;
82 }
83 }
84
85 /**
86 * Segment of bytecode related to one local slot, it represents a node in the segment graph.
87 */
88 private static final class Segment {
89
90 /**
91 * Categorization of the segment graph nodes.
92 */
93 enum Kind {
94
95 /**
96 * Segment storing a value into the local slot.
97 */
98 STORE,
99
100 /**
101 * Segment requesting to load value from the local slot.
102 */
103 LOAD,
104
105 /**
106 * Segment forming a frame of connection to other segments.
107 * This kind of segment is later either resolved as LOAD or it identifies false connection.
108 */
109 FRAME;
110 }
111
112 /**
113 * Link between segments.
114 */
115 record Link(Segment segment, Link other) {}
116
117 /**
118 * Kind of segment.
119 * The value is not final, {@link Kind.FRAME} segments may be later resolved to {@link Kind.LOAD}.
120 */
121 Kind kind;
122
123 /**
124 * Segment type.
125 * The value is not final, int type may be later changed to {@code boolean}, {@code byte}, {@code short} or {@code char}.
126 */
127 ClassDesc type;
128
129 /**
130 * Variable this segment belongs to.
131 * The value is calculated later in the process.
132 */
133 Variable var;
134
135
136 /**
137 * Incoming segments in the flow graph.
138 */
139 Link from;
140
141 /**
142 * Outgoing segments in the flow graph.
143 */
144 Link to;
145
146 /**
147 * Links this segment to an outgoing segment.
148 * @param toSegment outgoing segment
149 */
150 void link(Segment toSegment) {
151 if (this != toSegment) {
152 toSegment.from = new Link(this, toSegment.from);
153 this.to = new Link(toSegment, this.to);
154 }
155 }
156
157 /**
158 * {@return Iterable over incomming segments.}
159 */
160 Iterable<Segment> fromSegments() {
161 return () -> new LinkIterator(from);
162 }
163
164 /**
165 * {@return Iterable over outgoing segments.}
166 */
167 Iterable<Segment> toSegments() {
168 return () -> new LinkIterator(to);
169 }
170
171 private static final class LinkIterator implements Iterator<Segment> {
172 Link l;
173 public LinkIterator(Link l) {
174 this.l = l;
175 }
176
177 @Override
178 public boolean hasNext() {
179 return l != null;
180 }
181
182 @Override
183 public Segment next() {
184 if (l == null) throw new NoSuchElementException();
185 Segment s = l.segment();
186 l = l.other();
187 return s;
188 }
189 }
190 }
191
192 /**
193 * Stack map frame
194 */
195 private record Frame(List<ClassDesc> stack, List<Segment> locals) {}
196
197 /**
198 * Specific instance of CD_Object identifying null initialized objects.
199 */
200 private static final ClassDesc NULL_TYPE = ClassDesc.ofDescriptor(CD_Object.descriptorString());
201
202 /**
203 * Map from instruction index to a segment.
204 */
205 private final Map<Integer, Segment> insMap;
206
207 /**
208 * Set of all involved segments.
209 */
210 private final LinkedHashSet<Segment> allSegments;
211
212 /**
213 * This class descriptor.
214 */
215 private final ClassDesc thisClass;
216
217 /**
218 * All exception handlers.
219 */
220 private final List<ExceptionCatch> exceptionHandlers;
221
222 /**
223 * Actual exception handlers stack.
224 */
225 private final Set<ExceptionCatch> handlersStack;
226
227 /**
228 * Actual stack.
229 */
230 private final List<ClassDesc> stack;
231
232 /**
233 * Actual locals.
234 */
235 private final List<Segment> locals;
236
237 /**
238 * Stack map.
239 */
240 private final Map<Label, Frame> stackMap;
241
242 /**
243 * Map of new object types (to resolve unitialized verification types in the stack map).
244 */
245 private final Map<Label, ClassDesc> newMap;
246
247 /**
248 * Dirty flag indicates modified stack map frame (sub-int adjustments), so the scanning process must restart
249 */
250 private boolean frameDirty;
251
252 /**
253 * Initial set of slots. Static part comes from method arguments.
254 * Later phase of the analysis adds synthetic slots (declarations of multiple-assigned variables)
255 * with mandatory initialization in the entry block.
256 */
257 private final List<Segment> initSlots;
258
259 /**
260 * Constructor and executor of the LocalsToVarMapper.
261 * @param thisClass This class descriptor.
262 * @param initFrameLocals Entry frame locals, expanded form of the method receiver and arguments. Second positions of double slots are null.
263 * @param exceptionHandlers Exception handlers.
264 * @param stackMapTableAttribute Stack map table attribute.
265 * @param codeElements Code elements list. Indexes of this list are keys to the {@link #instructionVar(int) } method.
266 */
267 public LocalsToVarMapper(ClassDesc thisClass,
268 List<ClassDesc> initFrameLocals,
269 List<ExceptionCatch> exceptionHandlers,
270 Optional<StackMapTableAttribute> stackMapTableAttribute,
271 List<CodeElement> codeElements) {
272 this.insMap = new HashMap<>();
273 this.thisClass = thisClass;
274 this.exceptionHandlers = exceptionHandlers;
275 this.handlersStack = new LinkedHashSet<>();
276 this.stack = new ArrayList<>();
277 this.locals = new ArrayList<>();
278 this.allSegments = new LinkedHashSet<>();
279 this.newMap = computeNewMap(codeElements);
280 this.initSlots = new ArrayList<>();
281 this.stackMap = stackMapTableAttribute.map(a -> a.entries().stream().collect(Collectors.toMap(
282 StackMapFrameInfo::target,
283 this::toFrame))).orElse(Map.of());
284 for (ClassDesc cd : initFrameLocals) {
285 initSlots.add(cd == null ? null : newSegment(cd, Segment.Kind.STORE));
286 }
287 int initSize = allSegments.size();
288
289 // Main loop of the scan phase
290 do {
291 // Reset of the exception handler stack
292 handlersStack.clear();
293 // Slot states reset if running additional rounds (changed stack map frames)
294 if (allSegments.size() > initSize) {
295 while (allSegments.size() > initSize) allSegments.removeLast();
296 allSegments.forEach(sl -> {
297 sl.from = null;
298 sl.to = null;
299 sl.var = null;
300 });
301 }
302 // Initial frame store
303 for (int i = 0; i < initFrameLocals.size(); i++) {
304 storeLocal(i, initSlots.get(i), locals);
305 }
306 this.frameDirty = false;
307 // Iteration over all code elements
308 for (int i = 0; i < codeElements.size(); i++) {
309 var ce = codeElements.get(i);
310 scan(i, ce);
311 }
312 endOfFlow();
313 } while (this.frameDirty);
314
315 // Segment graph analysis phase
316 // First resolve FRAME segments to LOAD segments if directly followed by a LOAD segment
317 // Remaining FRAME segments do not form connection with segments of the same variable and will be ignored.
318 boolean changed = true;
319 while (changed) {
320 changed = false;
321 for (Segment segment : allSegments) {
322 if (segment.kind == Segment.Kind.FRAME) {
323 for (Segment to : segment.toSegments()) {
324 if (to.kind == Segment.Kind.LOAD) {
325 changed = true;
326 segment.kind = Segment.Kind.LOAD;
327 break;
328 }
329 }
330 }
331 }
332 }
333
334 // Assign variable to segments, calculate var type
335 Set<Segment> stores = new LinkedHashSet<>(); // Helper set to collect all STORE segments of a variable
336 ArrayDeque<Segment> q = new ArrayDeque<>(); // Working queue
337 Set<Segment> visited = new LinkedHashSet<>(); // Helper set to traverse segment graph to filter initial stores
338 for (Segment segment : allSegments) {
339 // Only STORE and LOAD segments without assigned var are computed
340 if (segment.var == null && segment.kind != Segment.Kind.FRAME) {
341 Variable var = new Variable(); // New variable
342 q.add(segment);
343 var.type = segment.type; // Initial variable type
344 while (!q.isEmpty()) {
345 Segment se = q.pop();
346 if (se.var == null) {
347 se.var = var; // Assign variable to the segment
348 for (Segment to : se.toSegments()) {
349 // All following LOAD segments belong to the same variable
350 if (to.kind == Segment.Kind.LOAD) {
351 if (var.type == NULL_TYPE) {
352 var.type = to.type; // Initially null type re-assignemnt
353 }
354 if (to.var == null) {
355 q.add(to);
356 }
357 }
358 }
359 if (se.kind == Segment.Kind.LOAD) {
360 // Segments preceeding LOAD segment also belong to the same variable
361 for (Segment from : se.fromSegments()) {
362 if (from.kind != Segment.Kind.FRAME) { // FRAME segments are ignored
363 if (var.type == NULL_TYPE) {
364 var.type = from.type; // Initially null type re-assignemnt
365 }
366 if (from.var == null) {
367 q.add(from);
368 }
369 }
370 }
371 }
372 }
373 if (se.var == var && se.kind == Segment.Kind.STORE) {
374 stores.add(se); // Collection of all STORE segments of the variable
375 }
376 }
377
378 // Single-assigned variable has only one STORE segment
379 var.single = stores.size() < 2;
380
381 // Identification of initial STORE segments
382 for (var it = stores.iterator(); it.hasNext();) {
383 visited.clear();
384 Segment s = it.next();
385 if (s.from != null && varDominatesOverSegmentPredecessors(s, var, visited)) {
386 // A store preceeding dominantly with segments of the same variable is not initial
387 it.remove();
388 }
389 }
390
391 // Remaining stores are all initial.
392 if (stores.size() > 1) {
393 // A synthetic default-initialized dominant segment must be inserted to the variable, if there is more than one initial store segment.
394 // It is not necessary to link it with other variable segments, the analysys ends here.
395 Segment initialSegment = new Segment();
396 initialSegment.var = var;
397 initSlots.add(initialSegment);
398 if (var.type == CD_long || var.type == CD_double) {
399 initSlots.add(null); // Do not forget to alocate second slot for double slots.
400 }
401 }
402 stores.clear();
403 }
404 }
405 }
406
407 /**
408 * {@return Number of slots to initialize at entry block (method receiver + arguments + synthetic variable initialization segments).}
409 */
410 public int slotsToInit() {
411 return initSlots.size();
412 }
413
414 /**
415 * {@return Variable related to the given initial slot or null}
416 * @param initSlot initial slot index
417 */
418 public Variable initSlotVar(int initSlot) {
419 Segment s = initSlots.get(initSlot);
420 return s == null ? null : s.var;
421 }
422
423 /**
424 * Method returns relevant {@link Variable} for instructions operating with local slots,
425 * such as {@link LoadInstruction}, {@link StoreInstruction} and {@link IncrementInstruction}.
426 * For all other elements it returns {@code null}.
427 *
428 * Instructions are identified by index into the {@code codeElements} list used in the {@link LocalsToVarMapper} initializer.
429 *
430 * {@link IncrementInstruction} relates to two potentially distinct variables, one variable to load the value from
431 * and one variable to store the incremented value into (see: {@link BytecodeLift#liftBody() }).
432 *
433 * @param codeElementIndex code element index
434 * @return Variable related to the given code element index or null
435 */
436 public Variable instructionVar(int codeElementIndex) {
437 return insMap.get(codeElementIndex).var;
438 }
439
440 /**
441 * Tests if variable dominates over the segment predecessors.
442 * All incoming paths to the segment must lead from segments of the given variable and not of any other variable.
443 * The paths may pass through {@code FRAME} segments, which do not belong to any variable and their dominance must be computed.
444 * Implementation relies on loops-avoiding breadth-first negative search.
445 */
446 private static boolean varDominatesOverSegmentPredecessors(Segment segment, Variable var, Set<Segment> visited) {
447 if (visited.add(segment)) {
448 for (Segment pred : segment.fromSegments()) {
449 // Breadth-first
450 if (pred.kind != Segment.Kind.FRAME && pred.var != var) {
451 return false;
452 }
453 }
454 for (Segment pred : segment.fromSegments()) {
455 // Preceeding FRAME segment implies there is no directly preceeding variable and the dominance test must go deeper
456 if (pred.kind == Segment.Kind.FRAME && !varDominatesOverSegmentPredecessors(pred, var, visited)) {
457 return false;
458 }
459 }
460 }
461 return true;
462 }
463
464 /**
465 * Cconverts {@link StackMapFrameInfo} to {@code Frame}, where locals are expanded form ({@code null}-filled second slots for double-slots)
466 * of {@code FRAME} segments.
467 * @param smfi StackMapFrameInfo
468 * @return Frame
469 */
470 private Frame toFrame(StackMapFrameInfo smfi) {
471 List<ClassDesc> fstack = new ArrayList<>(smfi.stack().size());
472 List<Segment> flocals = new ArrayList<>(smfi.locals().size() * 2);
473 for (var vti : smfi.stack()) {
474 fstack.add(vtiToStackType(vti));
475 }
476 int i = 0;
477 for (var vti : smfi.locals()) {
478 storeLocal(i, vtiToStackType(vti), flocals, Segment.Kind.FRAME);
479 i += vti == DOUBLE || vti == LONG ? 2 : 1;
480 }
481 return new Frame(fstack, flocals);
482 }
483
484 /**
485 * {@return map of labels immediately preceding {@link NewObjectInstruction} to the object types}
486 * The map is important to resolve unitialized verification types in the stack map.
487 * @param codeElements List of code elements to scan
488 */
489 private static Map<Label, ClassDesc> computeNewMap(List<CodeElement> codeElements) {
490 Map<Label, ClassDesc> newMap = new HashMap<>();
491 Label lastLabel = null;
492 for (int i = 0; i < codeElements.size(); i++) {
493 switch (codeElements.get(i)) {
494 case LabelTarget lt -> lastLabel = lt.label();
495 case NewObjectInstruction newI -> {
496 if (lastLabel != null) {
497 newMap.put(lastLabel, newI.className().asSymbol());
498 }
499 }
500 case Instruction _ -> lastLabel = null; //invalidate label
501 default -> {} //skip
502 }
503 }
504 return newMap;
505 }
506
507 /**
508 * {@return new segment and registers it in {@code allSegments} list}
509 * @param type class descriptor of segment type
510 * @param kind one of the segment kinds: {@code STORE}, {@code LOAD} or {@code FRAME}
511 */
512 private Segment newSegment(ClassDesc type, Segment.Kind kind) {
513 Segment s = new Segment();
514 s.kind = kind;
515 s.type = type;
516 allSegments.add(s);
517 return s;
518 }
519
520 /**
521 * {@return resolved class descriptor of the stack map frame verification type, custom {@code NULL_TYPE} for {@code ITEM_NULL}
522 * or {@code null} for {@code ITEM_TOP}}
523 * @param vti stack map frame verification type
524 */
525 private ClassDesc vtiToStackType(StackMapFrameInfo.VerificationTypeInfo vti) {
526 return switch (vti) {
527 case INTEGER -> CD_int;
528 case FLOAT -> CD_float;
529 case DOUBLE -> CD_double;
530 case LONG -> CD_long;
531 case UNINITIALIZED_THIS -> thisClass;
532 case NULL -> NULL_TYPE;
533 case ObjectVerificationTypeInfo ovti -> ovti.classSymbol();
534 case UninitializedVerificationTypeInfo uvti ->
535 newMap.computeIfAbsent(uvti.newTarget(), l -> {
536 throw new IllegalArgumentException("Unitialized type does not point to a new instruction");
537 });
538 case TOP -> null;
539 };
540 }
541
542 /**
543 * Pushes the class descriptor on {@link #stack}, except for {@code void}.
544 * @param type class descriptor
545 */
546 private void push(ClassDesc type) {
547 if (!ConstantDescs.CD_void.equals(type)) stack.add(type);
548 }
549
550 /**
551 * Pushes the class descriptors on the {@link #stack} at the relative position, except for {@code void}.
552 * @param pos position relative to the stack tip
553 * @param types class descriptors
554 */
555 private void pushAt(int pos, ClassDesc... types) {
556 for (var t : types)
557 if (!ConstantDescs.CD_void.equals(t))
558 stack.add(stack.size() + pos, t);
559 }
560
561 /**
562 * {@return if class descriptor on the {@link #stack} at the relative position is {@code long} or {@code double}}
563 * @param pos position relative to the stack tip
564 */
565 private boolean doubleAt(int pos) {
566 var t = stack.get(stack.size() + pos);
567 return t.equals(CD_long) || t.equals(CD_double);
568 }
569
570 /**
571 * {@return class descriptor poped from the {@link #stack}}
572 */
573 private ClassDesc pop() {
574 return stack.removeLast();
575 }
576
577 /**
578 * {@return class descriptor from the relative position of the {@link #stack}}
579 * @param pos position relative to the stack tip
580 */
581 private ClassDesc get(int pos) {
582 return stack.get(stack.size() + pos);
583 }
584
585 /**
586 * {@return class descriptor from the tip of the {@link #stack}}
587 */
588 private ClassDesc top() {
589 return stack.getLast();
590 }
591
592 /**
593 * {@return two class descriptors from the tip of the {@link #stack}}
594 */
595 private ClassDesc[] top2() {
596 return new ClassDesc[] {stack.get(stack.size() - 2), stack.getLast()};
597 }
598
599 /**
600 * Pops given number of class descriptors from the {@link #stack}.
601 * @param i number of class descriptors to pop
602 * @return this LocalsToVarMapper
603 */
604 private LocalsToVarMapper pop(int i) {
605 while (i-- > 0) pop();
606 return this;
607 }
608
609 /**
610 * Stores class descriptor as a new {@code STORE} {@link Segment} to the {@link #locals}.
611 * The new segment is linked with the previous segment on the same slot position (if any).
612 * @param slot locals slot number
613 * @param type new segment class descriptor
614 */
615 private void storeLocal(int slot, ClassDesc type) {
616 storeLocal(slot, type, locals, Segment.Kind.STORE);
617 }
618
619 /**
620 * Stores class descriptor as a new {@link Segment} of given kind to the given list .
621 * The new segment is linked with the previous segment on the same slot position (if any).
622 * @param slot locals slot number
623 * @param type new segment class descriptor
624 * @param where target list of segments
625 * @param kind new segment kind
626 */
627 private void storeLocal(int slot, ClassDesc type, List<Segment> where, Segment.Kind kind) {
628 storeLocal(slot, type == null ? null : newSegment(type, kind), where);
629 }
630
631 /**
632 * Stores the {@link Segment} to the given list.
633 * The new segment is linked with the previous segment on the same slot position (if any).
634 * @param slot locals slot number
635 * @param segment the segment to store
636 * @param where target list of segments
637 */
638 private void storeLocal(int slot, Segment segment, List<Segment> where) {
639 if (segment != null) {
640 for (int i = where.size(); i <= slot; i++) where.add(null);
641 Segment prev = where.set(slot, segment);
642 if (prev != null) {
643 prev.link(segment);
644 }
645 }
646 }
647
648 /**
649 * Links existing {@link Segment} of the {@link #locals} with a new {@code LOAD} {@link Segment} with inherited type.
650 * @param slot slot number to load
651 * @return type of the local
652 */
653 private ClassDesc loadLocal(int slot) {
654 Segment segment = locals.get(slot);
655 Segment newSegment = newSegment(segment.type, Segment.Kind.LOAD);
656 segment.link(newSegment);
657 return segment.type;
658 }
659
660 /**
661 * Main code element scanning method of the scan loop.
662 * @param elementIndex element index
663 * @param el code element
664 */
665 private void scan(int elementIndex, CodeElement el) {
666 switch (el) {
667 case ArrayLoadInstruction _ ->
668 pop(1).push(pop().componentType());
669 case ArrayStoreInstruction _ ->
670 pop(3);
671 case BranchInstruction i -> {
672 switch (i.opcode()) {
673 case IFEQ, IFGE, IFGT, IFLE, IFLT, IFNE, IFNONNULL, IFNULL -> {
674 pop();
675 mergeToTargetFrame(i.target());
676 }
677 case IF_ACMPEQ, IF_ACMPNE, IF_ICMPEQ, IF_ICMPGE, IF_ICMPGT, IF_ICMPLE, IF_ICMPLT, IF_ICMPNE -> {
678 pop(2);
679 mergeToTargetFrame(i.target());
680 }
681 case GOTO, GOTO_W -> {
682 mergeToTargetFrame(i.target());
683 endOfFlow();
684 }
685 }
686 }
687 case ConstantInstruction i ->
688 push(switch (i.constantValue()) {
689 case null -> NULL_TYPE;
690 case ClassDesc _ -> CD_Class;
691 case Double _ -> CD_double;
692 case Float _ -> CD_float;
693 case Integer _ -> CD_int;
694 case Long _ -> CD_long;
695 case String _ -> CD_String;
696 case DynamicConstantDesc<?> cd when cd.equals(NULL) -> NULL_TYPE;
697 case DynamicConstantDesc<?> cd -> cd.constantType();
698 case DirectMethodHandleDesc _ -> CD_MethodHandle;
699 case MethodTypeDesc _ -> CD_MethodType;
700 });
701 case ConvertInstruction i ->
702 pop(1).push(i.toType().upperBound());
703 case FieldInstruction i -> {
704 switch (i.opcode()) {
705 case GETSTATIC ->
706 push(i.typeSymbol());
707 case GETFIELD ->
708 pop(1).push(i.typeSymbol());
709 case PUTSTATIC ->
710 pop(1);
711 case PUTFIELD ->
712 pop(2);
713 }
714 }
715 case IncrementInstruction i -> { // Increment instruction maps to two segments
716 loadLocal(i.slot());
717 insMap.put(-elementIndex - 1, locals.get(i.slot())); // source segment is mapped with -elementIndex - 1 key
718 storeLocal(i.slot(), CD_int);
719 insMap.put(elementIndex, locals.get(i.slot())); // target segment is mapped with elementIndex key
720 for (var ec : handlersStack) {
721 mergeLocalsToTargetFrame(stackMap.get(ec.handler()));
722 }
723 }
724 case InvokeDynamicInstruction i ->
725 pop(i.typeSymbol().parameterCount()).push(i.typeSymbol().returnType());
726 case InvokeInstruction i ->
727 pop(i.typeSymbol().parameterCount() + (i.opcode() == Opcode.INVOKESTATIC ? 0 : 1))
728 .push(i.typeSymbol().returnType());
729 case LoadInstruction i -> {
730 push(loadLocal(i.slot())); // Load instruction segment is mapped with elementIndex key
731 insMap.put(elementIndex, locals.get(i.slot()));
732 }
733 case StoreInstruction i -> {
734 storeLocal(i.slot(), pop());
735 insMap.put(elementIndex, locals.get(i.slot())); // Store instruction segment is mapped with elementIndex key
736 for (var ec : handlersStack) {
737 mergeLocalsToTargetFrame(stackMap.get(ec.handler()));
738 }
739 }
740 case MonitorInstruction _ ->
741 pop(1);
742 case NewMultiArrayInstruction i ->
743 pop(i.dimensions()).push(i.arrayType().asSymbol());
744 case NewObjectInstruction i ->
745 push(i.className().asSymbol());
746 case NewPrimitiveArrayInstruction i ->
747 pop(1).push(i.typeKind().upperBound().arrayType());
748 case NewReferenceArrayInstruction i ->
749 pop(1).push(i.componentType().asSymbol().arrayType());
750 case OperatorInstruction i ->
751 pop(switch (i.opcode()) {
752 case ARRAYLENGTH, INEG, LNEG, FNEG, DNEG -> 1;
753 default -> 2;
754 }).push(i.typeKind().upperBound());
755 case StackInstruction i -> {
756 switch (i.opcode()) {
757 case POP -> pop(1);
758 case POP2 -> pop(doubleAt(-1) ? 1 : 2);
759 case DUP -> push(top());
760 case DUP2 -> {
761 if (doubleAt(-1)) {
762 push(top());
763 } else {
764 pushAt(-2, top2());
765 }
766 }
767 case DUP_X1 -> pushAt(-2, top());
768 case DUP_X2 -> pushAt(doubleAt(-2) ? -2 : -3, top());
769 case DUP2_X1 -> {
770 if (doubleAt(-1)) {
771 pushAt(-2, top());
772 } else {
773 pushAt(-3, top2());
774 }
775 }
776 case DUP2_X2 -> {
777 if (doubleAt(-1)) {
778 pushAt(doubleAt(-2) ? -2 : -3, top());
779 } else {
780 pushAt(doubleAt(-3) ? -3 : -4, top2());
781 }
782 }
783 case SWAP -> pushAt(-1, pop());
784 }
785 }
786 case TypeCheckInstruction i ->
787 pop(1).push(i.opcode() == Opcode.CHECKCAST ? i.type().asSymbol() : ConstantDescs.CD_int);
788 case LabelTarget lt -> {
789 var frame = stackMap.get(lt.label());
790 if (frame != null) { // Here we reached a stack map frame, so we merge actual stack and locals into the frame
791 if (!stack.isEmpty() || !locals.isEmpty()) {
792 mergeToTargetFrame(lt.label());
793 endOfFlow();
794 }
795 // Stack and locals are then taken from the frame
796 stack.addAll(frame.stack());
797 locals.addAll(frame.locals());
798 }
799 for (ExceptionCatch ec : exceptionHandlers) {
800 if (lt.label() == ec.tryStart()) { // Entering a try block
801 handlersStack.add(ec);
802 mergeLocalsToTargetFrame(stackMap.get(ec.handler()));
803 }
804 if (lt.label() == ec.tryEnd()) { // Leaving a try block
805 handlersStack.remove(ec);
806 }
807 }
808 }
809 case ReturnInstruction _ , ThrowInstruction _ -> {
810 endOfFlow();
811 }
812 case TableSwitchInstruction tsi -> {
813 pop();
814 mergeToTargetFrame(tsi.defaultTarget());
815 for (var c : tsi.cases()) {
816 mergeToTargetFrame(c.target());
817 }
818 endOfFlow();
819 }
820 case LookupSwitchInstruction lsi -> {
821 pop();
822 mergeToTargetFrame(lsi.defaultTarget());
823 for (var c : lsi.cases()) {
824 mergeToTargetFrame(c.target());
825 }
826 endOfFlow();
827 }
828 default -> {}
829 }
830 }
831
832 private void endOfFlow() {
833 stack.clear();
834 locals.clear();
835 }
836
837 /**
838 * Merge of the actual {@link #stack} and {@link #locals} to the target stack map frame
839 * @param target label of the target stack map frame
840 */
841 private void mergeToTargetFrame(Label target) {
842 Frame targetFrame = stackMap.get(target);
843 // Merge stack
844 assert stack.size() == targetFrame.stack.size();
845 for (int i = 0; i < targetFrame.stack.size(); i++) {
846 ClassDesc se = stack.get(i);
847 ClassDesc fe = targetFrame.stack.get(i);
848 if (!se.equals(fe)) {
849 if (se.isPrimitive() && CD_int.equals(fe)) {
850 targetFrame.stack.set(i, se); // Override int target frame type with more specific int sub-type
851 this.frameDirty = true; // This triggers scan loop to run again, as the stack map frame has been adjusted
852 } else {
853 stack.set(i, fe); // Override stack type with target frame type
854 }
855 }
856 }
857 mergeLocalsToTargetFrame(targetFrame);
858 }
859
860
861 /**
862 * Merge of the actual {@link #locals} to the target stack map frame
863 * @param targetFrame target stack map frame
864 */
865 private void mergeLocalsToTargetFrame(Frame targetFrame) {
866 // Merge locals
867 int lSize = Math.min(locals.size(), targetFrame.locals.size());
868 for (int i = 0; i < lSize; i++) {
869 Segment le = locals.get(i);
870 Segment fe = targetFrame.locals.get(i);
871 if (le != null && fe != null) {
872 le.link(fe); // Link target frame var with its source
873 if (!le.type.equals(fe.type)) {
874 if (le.type.isPrimitive() && CD_int.equals(fe.type) ) {
875 fe.type = le.type; // Override int target frame type with more specific int sub-type
876 this.frameDirty = true; // This triggers scan loop to run again, as the stack map frame has been adjusted
877 }
878 }
879 }
880 }
881 }
882 }