1 /*
2 * Copyright (c) 2022, 2025, Oracle and/or its affiliates. All rights reserved.
3 * Copyright (c) 2024, Alibaba Group Holding Limited. All Rights Reserved.
4 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
5 *
6 * This code is free software; you can redistribute it and/or modify it
7 * under the terms of the GNU General Public License version 2 only, as
8 * published by the Free Software Foundation. Oracle designates this
9 * particular file as subject to the "Classpath" exception as provided
10 * by Oracle in the LICENSE file that accompanied this code.
11 *
12 * This code is distributed in the hope that it will be useful, but WITHOUT
13 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 * version 2 for more details (a copy is included in the LICENSE file that
16 * accompanied this code).
17 *
18 * You should have received a copy of the GNU General Public License version
19 * 2 along with this work; if not, write to the Free Software Foundation,
20 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
21 *
22 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
23 * or visit www.oracle.com if you need additional information or have any
24 * questions.
25 *
26 */
27 package jdk.internal.classfile.impl;
28
29 import java.lang.classfile.Attribute;
30 import java.lang.classfile.Attributes;
31 import java.lang.classfile.Label;
32 import java.lang.classfile.attribute.StackMapTableAttribute;
33 import java.lang.classfile.constantpool.ClassEntry;
34 import java.lang.classfile.constantpool.ConstantDynamicEntry;
35 import java.lang.classfile.constantpool.ConstantPoolBuilder;
36 import java.lang.classfile.constantpool.InvokeDynamicEntry;
37 import java.lang.classfile.constantpool.MemberRefEntry;
38 import java.lang.classfile.constantpool.Utf8Entry;
39 import java.lang.constant.ClassDesc;
40 import java.lang.constant.MethodTypeDesc;
41 import java.util.ArrayList;
42 import java.util.Arrays;
43 import java.util.List;
44 import java.util.Objects;
45 import java.util.stream.Collectors;
46
47 import jdk.internal.constant.ClassOrInterfaceDescImpl;
48 import jdk.internal.util.Preconditions;
49
50 import static java.lang.classfile.ClassFile.*;
51 import static java.lang.classfile.constantpool.PoolEntry.*;
52 import static java.lang.constant.ConstantDescs.*;
53 import static jdk.internal.classfile.impl.RawBytecodeHelper.*;
54
55 /**
56 * StackMapGenerator is responsible for stack map frames generation.
57 * <p>
58 * Stack map frames are computed from serialized bytecode similar way they are verified during class loading process.
59 * <p>
60 * The {@linkplain #generate() frames computation} consists of following steps:
61 * <ol>
62 * <li>{@linkplain #detectFrames() Detection} of mandatory stack map frames:<ul>
63 * <li>Mandatory stack map frame include all jump and switch instructions targets,
64 * offsets immediately following {@linkplain #noControlFlow(int) "no control flow"}
65 * and all exception table handlers.
66 * <li>Detection is performed in a single fast pass through the bytecode,
67 * with no auxiliary structures construction nor further instructions processing.
68 * </ul>
69 * <li>Generator loop {@linkplain #processMethod() processing bytecode instructions}:<ul>
70 * <li>Generator loop simulates sequence instructions {@linkplain #processBlock(RawBytecodeHelper) processing effect on the actual stack and locals}.
71 * <li>All mandatory {@linkplain Frame frames} detected in the step #1 are {@linkplain Frame#checkAssignableTo(Frame) retro-filled}
72 * (or {@linkplain Frame#merge(Type, Type[], int, Frame) reverse-merged} in subsequent processing)
73 * with the actual stack and locals for all matching jump, switch and exception handler targets.
74 * <li>All frames modified by reverse merges are marked as {@linkplain Frame#dirty dirty} for further processing.
75 * <li>Code blocks with not yet known entry frame content are skipped and related frames are also marked as dirty.
76 * <li>Generator loop process is repeated until all mandatory frames are cleared or until an error state is reached.
77 * <li>Generator loop always passes all instructions at least once to calculate {@linkplain #maxStack max stack}
78 * and {@linkplain #maxLocals max locals} code attributes.
79 * <li>More than one pass is usually not necessary, except for more complex bytecode sequences.<br>
80 * <i>(Note: experimental measurements showed that more than 99% of the cases required only single pass to clear all frames,
81 * less than 1% of the cases required second pass and remaining 0,01% of the cases required third pass to clear all frames.)</i>.
82 * </ul>
83 * <li>Dead code patching to pass class loading verification:<ul>
84 * <li>Dead code blocks are indicated by frames remaining without content after leaving the Generator loop.
85 * <li>Each dead code block is filled with <code>NOP</code> instructions, terminated with
86 * <code>ATHROW</code> instruction, and removed from exception handlers table.
87 * <li>Dead code block entry frame is set to <code>java.lang.Throwable</code> single stack item and no locals.
88 * </ul>
89 * </ol>
90 * <p>
91 * {@linkplain Frame#merge(Type, Type[], int, Frame) Reverse-merge} of the stack map frames
92 * may in some situations require to determine {@linkplain ClassHierarchyImpl class hierarchy} relations.
93 * <p>
94 * Reverse-merge of individual {@linkplain Type types} is performed when a target frame has already been retro-filled
95 * and it is necessary to adjust its existing stack entries and locals to also match actual stack map frame conditions.
96 * Following tables describe how new target stack entry or local type is calculated, based on the actual frame stack entry or local ("from")
97 * and actual value of the target stack entry or local ("to").
98 *
99 * <table border="1">
100 * <caption>Reverse-merge of general type categories</caption>
101 * <tr><th>to \ from<th>TOP<th>PRIMITIVE<th>UNINITIALIZED<th>REFERENCE
102 * <tr><th>TOP<td>TOP<td>TOP<td>TOP<td>TOP
103 * <tr><th>PRIMITIVE<td>TOP<td><a href="#primitives">Reverse-merge of primitive types</a><td>TOP<td>TOP
104 * <tr><th>UNINITIALIZED<td>TOP<td>TOP<td>Is NEW offset matching ? UNINITIALIZED : TOP<td>TOP
105 * <tr><th>REFERENCE<td>TOP<td>TOP<td>TOP<td><a href="#references">Reverse-merge of reference types</a>
106 * </table>
107 * <p>
108 * <table id="primitives" border="1">
109 * <caption>Reverse-merge of primitive types</caption>
110 * <tr><th>to \ from<th>SHORT<th>BYTE<th>BOOLEAN<th>LONG<th>DOUBLE<th>FLOAT<th>INTEGER
111 * <tr><th>SHORT<td>SHORT<td>TOP<td>TOP<td>TOP<td>TOP<td>TOP<td>SHORT
112 * <tr><th>BYTE<td>TOP<td>BYTE<td>TOP<td>TOP<td>TOP<td>TOP<td>BYTE
113 * <tr><th>BOOLEAN<td>TOP<td>TOP<td>BOOLEAN<td>TOP<td>TOP<td>TOP<td>BOOLEAN
114 * <tr><th>LONG<td>TOP<td>TOP<td>TOP<td>LONG<td>TOP<td>TOP<td>TOP
115 * <tr><th>DOUBLE<td>TOP<td>TOP<td>TOP<td>TOP<td>DOUBLE<td>TOP<td>TOP
116 * <tr><th>FLOAT<td>TOP<td>TOP<td>TOP<td>TOP<td>TOP<td>FLOAT<td>TOP
117 * <tr><th>INTEGER<td>TOP<td>TOP<td>TOP<td>TOP<td>TOP<td>TOP<td>INTEGER
118 * </table>
119 * <p>
120 * <table id="references" border="1">
121 * <caption>Reverse merge of reference types</caption>
122 * <tr><th>to \ from<th>NULL<th>j.l.Object<th>j.l.Cloneable<th>j.i.Serializable<th>ARRAY<th>INTERFACE*<th>OBJECT**
123 * <tr><th>NULL<td>NULL<td>j.l.Object<td>j.l.Cloneable<td>j.i.Serializable<td>ARRAY<td>INTERFACE<td>OBJECT
124 * <tr><th>j.l.Object<td>j.l.Object<td>j.l.Object<td>j.l.Object<td>j.l.Object<td>j.l.Object<td>j.l.Object<td>j.l.Object
125 * <tr><th>j.l.Cloneable<td>j.l.Cloneable<td>j.l.Cloneable<td>j.l.Cloneable<td>j.l.Cloneable<td>j.l.Object<td>j.l.Cloneable<td>j.l.Cloneable
126 * <tr><th>j.i.Serializable<td>j.i.Serializable<td>j.i.Serializable<td>j.i.Serializable<td>j.i.Serializable<td>j.l.Object<td>j.i.Serializable<td>j.i.Serializable
127 * <tr><th>ARRAY<td>ARRAY<td>j.l.Object<td>j.l.Object<td>j.l.Object<td><a href="#arrays">Reverse merge of arrays</a><td>j.l.Object<td>j.l.Object
128 * <tr><th>INTERFACE*<td>INTERFACE<td>j.l.Object<td>j.l.Object<td>j.l.Object<td>j.l.Object<td>j.l.Object<td>j.l.Object
129 * <tr><th>OBJECT**<td>OBJECT<td>j.l.Object<td>j.l.Object<td>j.l.Object<td>j.l.Object<td>j.l.Object<td>Resolved common ancestor
130 * <tr><td colspan="8">*any interface reference except for j.l.Cloneable and j.i.Serializable<br>**any object reference except for j.l.Object
131 * </table>
132 * <p id="arrays">
133 * Array types are reverse-merged as reference to array type constructed from reverse-merged components.
134 * Reference to j.l.Object is an alternate result when construction of the array type is not possible (when reverse-merge of components returned TOP or other non-reference and non-primitive type).
135 * <p>
136 * Custom class hierarchy resolver has been implemented as a part of the library to avoid heavy class loading
137 * and to allow stack maps generation even for code with incomplete dependency classpath.
138 * However stack maps generated with {@linkplain ClassHierarchyImpl#resolve(java.lang.constant.ClassDesc) warnings of unresolved dependencies} may later fail to verify during class loading process.
139 * <p>
140 * Focus of the whole algorithm is on high performance and low memory footprint:<ul>
141 * <li>It does not produce, collect nor visit any complex intermediate structures
142 * <i>(beside {@linkplain RawBytecodeHelper traversing} the {@linkplain #bytecode bytecode in binary form}).</i>
143 * <li>It works with only minimal mandatory stack map frames.
144 * <li>It does not spend time on any non-essential verifications.
145 * </ul>
146 */
147
148 public final class StackMapGenerator {
149
150 static StackMapGenerator of(DirectCodeBuilder dcb, BufWriterImpl buf) {
151 return new StackMapGenerator(
152 dcb,
153 buf.thisClass().asSymbol(),
154 dcb.methodInfo.methodName().stringValue(),
155 dcb.methodInfo.methodTypeSymbol(),
156 (dcb.methodInfo.methodFlags() & ACC_STATIC) != 0,
157 dcb.bytecodesBufWriter.bytecodeView(),
158 dcb.constantPool,
159 dcb.context,
160 dcb.handlers);
161 }
162
163 private static final String OBJECT_INITIALIZER_NAME = "<init>";
164 private static final int FLAG_THIS_UNINIT = 0x01;
165 private static final int FRAME_DEFAULT_CAPACITY = 10;
166 private static final int T_BOOLEAN = 4, T_LONG = 11;
167 private static final Frame[] EMPTY_FRAME_ARRAY = {};
168
169 public static final int
170 ITEM_TOP = 0,
171 ITEM_INTEGER = 1,
172 ITEM_FLOAT = 2,
173 ITEM_DOUBLE = 3,
174 ITEM_LONG = 4,
175 ITEM_NULL = 5,
176 ITEM_UNINITIALIZED_THIS = 6,
177 ITEM_OBJECT = 7,
178 ITEM_UNINITIALIZED = 8,
179 ITEM_BOOLEAN = 9,
180 ITEM_BYTE = 10,
181 ITEM_SHORT = 11,
182 ITEM_CHAR = 12,
183 ITEM_LONG_2ND = 13,
184 ITEM_DOUBLE_2ND = 14,
185 ITEM_BOGUS = -1;
186
187 // Ranges represented by these constants are inclusive on both ends
188 public static final int
189 SAME_FRAME_END = 63,
190 SAME_LOCALS_1_STACK_ITEM_FRAME_START = 64,
191 SAME_LOCALS_1_STACK_ITEM_FRAME_END = 127,
192 RESERVED_END = 246,
193 SAME_LOCALS_1_STACK_ITEM_EXTENDED = 247,
194 CHOP_FRAME_START = 248,
195 CHOP_FRAME_END = 250,
196 SAME_FRAME_EXTENDED = 251,
197 APPEND_FRAME_START = 252,
198 APPEND_FRAME_END = 254,
199 FULL_FRAME = 255;
200
201 private static final Type[] ARRAY_FROM_BASIC_TYPE = {null, null, null, null,
202 Type.BOOLEAN_ARRAY_TYPE, Type.CHAR_ARRAY_TYPE, Type.FLOAT_ARRAY_TYPE, Type.DOUBLE_ARRAY_TYPE,
203 Type.BYTE_ARRAY_TYPE, Type.SHORT_ARRAY_TYPE, Type.INT_ARRAY_TYPE, Type.LONG_ARRAY_TYPE};
204
205 static record RawExceptionCatch(int start, int end, int handler, Type catchType) {}
206
207 private final Type thisType;
208 private final String methodName;
209 private final MethodTypeDesc methodDesc;
210 private final RawBytecodeHelper.CodeRange bytecode;
211 private final SplitConstantPool cp;
212 private final boolean isStatic;
213 private final LabelContext labelContext;
214 private final List<AbstractPseudoInstruction.ExceptionCatchImpl> handlers;
215 private final List<RawExceptionCatch> rawHandlers;
216 private final ClassHierarchyImpl classHierarchy;
217 private final boolean patchDeadCode;
218 private final boolean filterDeadLabels;
219 private Frame[] frames = EMPTY_FRAME_ARRAY;
220 private int framesCount = 0;
221 private final Frame currentFrame;
222 private int maxStack, maxLocals;
223
224 /**
225 * Primary constructor of the <code>Generator</code> class.
226 * New <code>Generator</code> instance must be created for each individual class/method.
227 * Instance contains only immutable results, all the calculations are processed during instance construction.
228 *
229 * @param labelContext <code>LabelContext</code> instance used to resolve or patch <code>ExceptionHandler</code>
230 * labels to bytecode offsets (or vice versa)
231 * @param thisClass class to generate stack maps for
232 * @param methodName method name to generate stack maps for
233 * @param methodDesc method descriptor to generate stack maps for
234 * @param isStatic information whether the method is static
235 * @param bytecode R/W <code>ByteBuffer</code> wrapping method bytecode, the content is altered in case <code>Generator</code> detects and patches dead code
236 * @param cp R/W <code>ConstantPoolBuilder</code> instance used to resolve all involved CP entries and also generate new entries referenced from the generated stack maps
237 * @param handlers R/W <code>ExceptionHandler</code> list used to detect mandatory frame offsets as well as to determine stack maps in exception handlers
238 * and also to be altered when dead code is detected and must be excluded from exception handlers
239 */
240 public StackMapGenerator(LabelContext labelContext,
241 ClassDesc thisClass,
242 String methodName,
243 MethodTypeDesc methodDesc,
244 boolean isStatic,
245 RawBytecodeHelper.CodeRange bytecode,
246 SplitConstantPool cp,
247 ClassFileImpl context,
248 List<AbstractPseudoInstruction.ExceptionCatchImpl> handlers) {
249 this.thisType = Type.referenceType(thisClass);
250 this.methodName = methodName;
251 this.methodDesc = methodDesc;
252 this.isStatic = isStatic;
253 this.bytecode = bytecode;
254 this.cp = cp;
255 this.labelContext = labelContext;
256 this.handlers = handlers;
257 this.rawHandlers = new ArrayList<>(handlers.size());
258 this.classHierarchy = new ClassHierarchyImpl(context.classHierarchyResolver());
259 this.patchDeadCode = context.patchDeadCode();
260 this.filterDeadLabels = context.dropDeadLabels();
261 this.currentFrame = new Frame(classHierarchy);
262 generate();
263 }
264
265 /**
266 * Calculated maximum number of the locals required
267 * @return maximum number of the locals required
268 */
269 public int maxLocals() {
270 return maxLocals;
271 }
272
273 /**
274 * Calculated maximum stack size required
275 * @return maximum stack size required
276 */
277 public int maxStack() {
278 return maxStack;
279 }
280
281 private Frame getFrame(int offset) {
282 //binary search over frames ordered by offset
283 int low = 0;
284 int high = framesCount - 1;
285 while (low <= high) {
286 int mid = (low + high) >>> 1;
287 var f = frames[mid];
288 if (f.offset < offset)
289 low = mid + 1;
290 else if (f.offset > offset)
291 high = mid - 1;
292 else
293 return f;
294 }
295 return null;
296 }
297
298 private void checkJumpTarget(Frame frame, int target) {
299 frame.checkAssignableTo(getFrame(target));
300 }
301
302 private int exMin, exMax;
303
304 private boolean isAnyFrameDirty() {
305 for (int i = 0; i < framesCount; i++) {
306 if (frames[i].dirty) return true;
307 }
308 return false;
309 }
310
311 private void generate() {
312 exMin = bytecode.length();
313 exMax = -1;
314 if (!handlers.isEmpty()) {
315 generateHandlers();
316 }
317 detectFrames();
318 do {
319 processMethod();
320 } while (isAnyFrameDirty());
321 maxLocals = currentFrame.frameMaxLocals;
322 maxStack = currentFrame.frameMaxStack;
323
324 //dead code patching
325 for (int i = 0; i < framesCount; i++) {
326 var frame = frames[i];
327 if (frame.flags == -1) {
328 deadCodePatching(frame, i);
329 }
330 }
331 }
332
333 private void generateHandlers() {
334 var labelContext = this.labelContext;
335 for (int i = 0; i < handlers.size(); i++) {
336 var exhandler = handlers.get(i);
337 int start_pc = labelContext.labelToBci(exhandler.tryStart());
338 int end_pc = labelContext.labelToBci(exhandler.tryEnd());
339 int handler_pc = labelContext.labelToBci(exhandler.handler());
340 if (start_pc >= 0 && end_pc >= 0 && end_pc > start_pc && handler_pc >= 0) {
341 if (start_pc < exMin) exMin = start_pc;
342 if (end_pc > exMax) exMax = end_pc;
343 var catchType = exhandler.catchType();
344 rawHandlers.add(new RawExceptionCatch(start_pc, end_pc, handler_pc,
345 catchType.isPresent() ? cpIndexToType(catchType.get().index(), cp)
346 : Type.THROWABLE_TYPE));
347 }
348 }
349 }
350
351 private void deadCodePatching(Frame frame, int i) {
352 if (!patchDeadCode) throw generatorError("Unable to generate stack map frame for dead code", frame.offset);
353 //patch frame
354 frame.pushStack(Type.THROWABLE_TYPE);
355 if (maxStack < 1) maxStack = 1;
356 int end = (i < framesCount - 1 ? frames[i + 1].offset : bytecode.length()) - 1;
357 //patch bytecode
358 var arr = bytecode.array();
359 Arrays.fill(arr, frame.offset, end, (byte) NOP);
360 arr[end] = (byte) ATHROW;
361 //patch handlers
362 removeRangeFromExcTable(frame.offset, end + 1);
363 }
364
365 private void removeRangeFromExcTable(int rangeStart, int rangeEnd) {
366 var it = handlers.listIterator();
367 while (it.hasNext()) {
368 var e = it.next();
369 int handlerStart = labelContext.labelToBci(e.tryStart());
370 int handlerEnd = labelContext.labelToBci(e.tryEnd());
371 if (rangeStart >= handlerEnd || rangeEnd <= handlerStart) {
372 //out of range
373 continue;
374 }
375 if (rangeStart <= handlerStart) {
376 if (rangeEnd >= handlerEnd) {
377 //complete removal
378 it.remove();
379 } else {
380 //cut from left
381 Label newStart = labelContext.newLabel();
382 labelContext.setLabelTarget(newStart, rangeEnd);
383 it.set(new AbstractPseudoInstruction.ExceptionCatchImpl(e.handler(), newStart, e.tryEnd(), e.catchType()));
384 }
385 } else if (rangeEnd >= handlerEnd) {
386 //cut from right
387 Label newEnd = labelContext.newLabel();
388 labelContext.setLabelTarget(newEnd, rangeStart);
389 it.set(new AbstractPseudoInstruction.ExceptionCatchImpl(e.handler(), e.tryStart(), newEnd, e.catchType()));
390 } else {
391 //split
392 Label newStart = labelContext.newLabel();
393 labelContext.setLabelTarget(newStart, rangeEnd);
394 Label newEnd = labelContext.newLabel();
395 labelContext.setLabelTarget(newEnd, rangeStart);
396 it.set(new AbstractPseudoInstruction.ExceptionCatchImpl(e.handler(), e.tryStart(), newEnd, e.catchType()));
397 it.add(new AbstractPseudoInstruction.ExceptionCatchImpl(e.handler(), newStart, e.tryEnd(), e.catchType()));
398 }
399 }
400 }
401
402 /**
403 * Getter of the generated <code>StackMapTableAttribute</code> or null if stack map is empty
404 * @return <code>StackMapTableAttribute</code> or null if stack map is empty
405 */
406 public Attribute<? extends StackMapTableAttribute> stackMapTableAttribute() {
407 return framesCount == 0 ? null : new UnboundAttribute.AdHocAttribute<>(Attributes.stackMapTable()) {
408 @Override
409 public void writeBody(BufWriterImpl b) {
410 b.writeU2(framesCount);
411 Frame prevFrame = new Frame(classHierarchy);
412 prevFrame.setLocalsFromArg(methodName, methodDesc, isStatic, thisType);
413 prevFrame.trimAndCompress();
414 for (int i = 0; i < framesCount; i++) {
415 var fr = frames[i];
416 fr.trimAndCompress();
417 fr.writeTo(b, prevFrame, cp);
418 prevFrame = fr;
419 }
420 }
421
422 @Override
423 public Utf8Entry attributeName() {
424 return cp.utf8Entry(Attributes.NAME_STACK_MAP_TABLE);
425 }
426 };
427 }
428
429 private static Type cpIndexToType(int index, ConstantPoolBuilder cp) {
430 return Type.referenceType(cp.entryByIndex(index, ClassEntry.class).asSymbol());
431 }
432
433 private void processMethod() {
434 var frames = this.frames;
435 var currentFrame = this.currentFrame;
436 currentFrame.setLocalsFromArg(methodName, methodDesc, isStatic, thisType);
437 currentFrame.stackSize = 0;
438 currentFrame.flags = 0;
439 currentFrame.offset = -1;
440 int stackmapIndex = 0;
441 var bcs = bytecode.start();
442 boolean ncf = false;
443 while (bcs.next()) {
444 currentFrame.offset = bcs.bci();
445 if (stackmapIndex < framesCount) {
446 int thisOffset = frames[stackmapIndex].offset;
447 if (ncf && thisOffset > bcs.bci()) {
448 throw generatorError("Expecting a stack map frame");
449 }
450 if (thisOffset == bcs.bci()) {
451 Frame nextFrame = frames[stackmapIndex++];
452 if (!ncf) {
453 currentFrame.checkAssignableTo(nextFrame);
454 }
455 while (!nextFrame.dirty) { //skip unmatched frames
456 if (stackmapIndex == framesCount) return; //skip the rest of this round
457 nextFrame = frames[stackmapIndex++];
458 }
459 bcs.reset(nextFrame.offset); //skip code up-to the next frame
460 bcs.next();
461 currentFrame.offset = bcs.bci();
462 currentFrame.copyFrom(nextFrame);
463 nextFrame.dirty = false;
464 } else if (thisOffset < bcs.bci()) {
465 throw generatorError("Bad stack map offset");
466 }
467 } else if (ncf) {
468 throw generatorError("Expecting a stack map frame");
469 }
470 ncf = processBlock(bcs);
471 }
472 }
473
474 private boolean processBlock(RawBytecodeHelper bcs) {
475 int opcode = bcs.opcode();
476 boolean ncf = false;
477 boolean this_uninit = false;
478 boolean verified_exc_handlers = false;
479 int bci = bcs.bci();
480 Type type1, type2, type3, type4;
481 if (RawBytecodeHelper.isStoreIntoLocal(opcode) && bci >= exMin && bci < exMax) {
482 processExceptionHandlerTargets(bci, this_uninit);
483 verified_exc_handlers = true;
484 }
485 switch (opcode) {
486 case NOP -> {}
487 case RETURN -> {
488 ncf = true;
489 }
490 case ACONST_NULL ->
491 currentFrame.pushStack(Type.NULL_TYPE);
492 case ICONST_M1, ICONST_0, ICONST_1, ICONST_2, ICONST_3, ICONST_4, ICONST_5, SIPUSH, BIPUSH ->
493 currentFrame.pushStack(Type.INTEGER_TYPE);
494 case LCONST_0, LCONST_1 ->
495 currentFrame.pushStack(Type.LONG_TYPE, Type.LONG2_TYPE);
496 case FCONST_0, FCONST_1, FCONST_2 ->
497 currentFrame.pushStack(Type.FLOAT_TYPE);
498 case DCONST_0, DCONST_1 ->
499 currentFrame.pushStack(Type.DOUBLE_TYPE, Type.DOUBLE2_TYPE);
500 case LDC ->
501 processLdc(bcs.getIndexU1());
502 case LDC_W, LDC2_W ->
503 processLdc(bcs.getIndexU2());
504 case ILOAD ->
505 currentFrame.checkLocal(bcs.getIndex()).pushStack(Type.INTEGER_TYPE);
506 case ILOAD_0, ILOAD_1, ILOAD_2, ILOAD_3 ->
507 currentFrame.checkLocal(opcode - ILOAD_0).pushStack(Type.INTEGER_TYPE);
508 case LLOAD ->
509 currentFrame.checkLocal(bcs.getIndex() + 1).pushStack(Type.LONG_TYPE, Type.LONG2_TYPE);
510 case LLOAD_0, LLOAD_1, LLOAD_2, LLOAD_3 ->
511 currentFrame.checkLocal(opcode - LLOAD_0 + 1).pushStack(Type.LONG_TYPE, Type.LONG2_TYPE);
512 case FLOAD ->
513 currentFrame.checkLocal(bcs.getIndex()).pushStack(Type.FLOAT_TYPE);
514 case FLOAD_0, FLOAD_1, FLOAD_2, FLOAD_3 ->
515 currentFrame.checkLocal(opcode - FLOAD_0).pushStack(Type.FLOAT_TYPE);
516 case DLOAD ->
517 currentFrame.checkLocal(bcs.getIndex() + 1).pushStack(Type.DOUBLE_TYPE, Type.DOUBLE2_TYPE);
518 case DLOAD_0, DLOAD_1, DLOAD_2, DLOAD_3 ->
519 currentFrame.checkLocal(opcode - DLOAD_0 + 1).pushStack(Type.DOUBLE_TYPE, Type.DOUBLE2_TYPE);
520 case ALOAD ->
521 currentFrame.pushStack(currentFrame.getLocal(bcs.getIndex()));
522 case ALOAD_0, ALOAD_1, ALOAD_2, ALOAD_3 ->
523 currentFrame.pushStack(currentFrame.getLocal(opcode - ALOAD_0));
524 case IALOAD, BALOAD, CALOAD, SALOAD ->
525 currentFrame.decStack(2).pushStack(Type.INTEGER_TYPE);
526 case LALOAD ->
527 currentFrame.decStack(2).pushStack(Type.LONG_TYPE, Type.LONG2_TYPE);
528 case FALOAD ->
529 currentFrame.decStack(2).pushStack(Type.FLOAT_TYPE);
530 case DALOAD ->
531 currentFrame.decStack(2).pushStack(Type.DOUBLE_TYPE, Type.DOUBLE2_TYPE);
532 case AALOAD ->
533 currentFrame.pushStack((type1 = currentFrame.decStack(1).popStack()) == Type.NULL_TYPE ? Type.NULL_TYPE : type1.getComponent());
534 case ISTORE ->
535 currentFrame.decStack(1).setLocal(bcs.getIndex(), Type.INTEGER_TYPE);
536 case ISTORE_0, ISTORE_1, ISTORE_2, ISTORE_3 ->
537 currentFrame.decStack(1).setLocal(opcode - ISTORE_0, Type.INTEGER_TYPE);
538 case LSTORE ->
539 currentFrame.decStack(2).setLocal2(bcs.getIndex(), Type.LONG_TYPE, Type.LONG2_TYPE);
540 case LSTORE_0, LSTORE_1, LSTORE_2, LSTORE_3 ->
541 currentFrame.decStack(2).setLocal2(opcode - LSTORE_0, Type.LONG_TYPE, Type.LONG2_TYPE);
542 case FSTORE ->
543 currentFrame.decStack(1).setLocal(bcs.getIndex(), Type.FLOAT_TYPE);
544 case FSTORE_0, FSTORE_1, FSTORE_2, FSTORE_3 ->
545 currentFrame.decStack(1).setLocal(opcode - FSTORE_0, Type.FLOAT_TYPE);
546 case DSTORE ->
547 currentFrame.decStack(2).setLocal2(bcs.getIndex(), Type.DOUBLE_TYPE, Type.DOUBLE2_TYPE);
548 case DSTORE_0, DSTORE_1, DSTORE_2, DSTORE_3 ->
549 currentFrame.decStack(2).setLocal2(opcode - DSTORE_0, Type.DOUBLE_TYPE, Type.DOUBLE2_TYPE);
550 case ASTORE ->
551 currentFrame.setLocal(bcs.getIndex(), currentFrame.popStack());
552 case ASTORE_0, ASTORE_1, ASTORE_2, ASTORE_3 ->
553 currentFrame.setLocal(opcode - ASTORE_0, currentFrame.popStack());
554 case LASTORE, DASTORE ->
555 currentFrame.decStack(4);
556 case IASTORE, BASTORE, CASTORE, SASTORE, FASTORE, AASTORE ->
557 currentFrame.decStack(3);
558 case POP, MONITORENTER, MONITOREXIT ->
559 currentFrame.decStack(1);
560 case POP2 ->
561 currentFrame.decStack(2);
562 case DUP ->
563 currentFrame.pushStack(type1 = currentFrame.popStack()).pushStack(type1);
564 case DUP_X1 -> {
565 type1 = currentFrame.popStack();
566 type2 = currentFrame.popStack();
567 currentFrame.pushStack(type1).pushStack(type2).pushStack(type1);
568 }
569 case DUP_X2 -> {
570 type1 = currentFrame.popStack();
571 type2 = currentFrame.popStack();
572 type3 = currentFrame.popStack();
573 currentFrame.pushStack(type1).pushStack(type3).pushStack(type2).pushStack(type1);
574 }
575 case DUP2 -> {
576 type1 = currentFrame.popStack();
577 type2 = currentFrame.popStack();
578 currentFrame.pushStack(type2).pushStack(type1).pushStack(type2).pushStack(type1);
579 }
580 case DUP2_X1 -> {
581 type1 = currentFrame.popStack();
582 type2 = currentFrame.popStack();
583 type3 = currentFrame.popStack();
584 currentFrame.pushStack(type2).pushStack(type1).pushStack(type3).pushStack(type2).pushStack(type1);
585 }
586 case DUP2_X2 -> {
587 type1 = currentFrame.popStack();
588 type2 = currentFrame.popStack();
589 type3 = currentFrame.popStack();
590 type4 = currentFrame.popStack();
591 currentFrame.pushStack(type2).pushStack(type1).pushStack(type4).pushStack(type3).pushStack(type2).pushStack(type1);
592 }
593 case SWAP -> {
594 type1 = currentFrame.popStack();
595 type2 = currentFrame.popStack();
596 currentFrame.pushStack(type1);
597 currentFrame.pushStack(type2);
598 }
599 case IADD, ISUB, IMUL, IDIV, IREM, ISHL, ISHR, IUSHR, IOR, IXOR, IAND ->
600 currentFrame.decStack(2).pushStack(Type.INTEGER_TYPE);
601 case INEG, ARRAYLENGTH, INSTANCEOF ->
602 currentFrame.decStack(1).pushStack(Type.INTEGER_TYPE);
603 case LADD, LSUB, LMUL, LDIV, LREM, LAND, LOR, LXOR ->
604 currentFrame.decStack(4).pushStack(Type.LONG_TYPE, Type.LONG2_TYPE);
605 case LNEG ->
606 currentFrame.decStack(2).pushStack(Type.LONG_TYPE, Type.LONG2_TYPE);
607 case LSHL, LSHR, LUSHR ->
608 currentFrame.decStack(3).pushStack(Type.LONG_TYPE, Type.LONG2_TYPE);
609 case FADD, FSUB, FMUL, FDIV, FREM ->
610 currentFrame.decStack(2).pushStack(Type.FLOAT_TYPE);
611 case FNEG ->
612 currentFrame.decStack(1).pushStack(Type.FLOAT_TYPE);
613 case DADD, DSUB, DMUL, DDIV, DREM ->
614 currentFrame.decStack(4).pushStack(Type.DOUBLE_TYPE, Type.DOUBLE2_TYPE);
615 case DNEG ->
616 currentFrame.decStack(2).pushStack(Type.DOUBLE_TYPE, Type.DOUBLE2_TYPE);
617 case IINC ->
618 currentFrame.checkLocal(bcs.getIndex());
619 case I2L ->
620 currentFrame.decStack(1).pushStack(Type.LONG_TYPE, Type.LONG2_TYPE);
621 case L2I ->
622 currentFrame.decStack(2).pushStack(Type.INTEGER_TYPE);
623 case I2F ->
624 currentFrame.decStack(1).pushStack(Type.FLOAT_TYPE);
625 case I2D ->
626 currentFrame.decStack(1).pushStack(Type.DOUBLE_TYPE, Type.DOUBLE2_TYPE);
627 case L2F ->
628 currentFrame.decStack(2).pushStack(Type.FLOAT_TYPE);
629 case L2D ->
630 currentFrame.decStack(2).pushStack(Type.DOUBLE_TYPE, Type.DOUBLE2_TYPE);
631 case F2I ->
632 currentFrame.decStack(1).pushStack(Type.INTEGER_TYPE);
633 case F2L ->
634 currentFrame.decStack(1).pushStack(Type.LONG_TYPE, Type.LONG2_TYPE);
635 case F2D ->
636 currentFrame.decStack(1).pushStack(Type.DOUBLE_TYPE, Type.DOUBLE2_TYPE);
637 case D2L ->
638 currentFrame.decStack(2).pushStack(Type.LONG_TYPE, Type.LONG2_TYPE);
639 case D2F ->
640 currentFrame.decStack(2).pushStack(Type.FLOAT_TYPE);
641 case I2B, I2C, I2S ->
642 currentFrame.decStack(1).pushStack(Type.INTEGER_TYPE);
643 case LCMP, DCMPL, DCMPG ->
644 currentFrame.decStack(4).pushStack(Type.INTEGER_TYPE);
645 case FCMPL, FCMPG, D2I ->
646 currentFrame.decStack(2).pushStack(Type.INTEGER_TYPE);
647 case IF_ICMPEQ, IF_ICMPNE, IF_ICMPLT, IF_ICMPGE, IF_ICMPGT, IF_ICMPLE, IF_ACMPEQ, IF_ACMPNE ->
648 checkJumpTarget(currentFrame.decStack(2), bcs.dest());
649 case IFEQ, IFNE, IFLT, IFGE, IFGT, IFLE, IFNULL, IFNONNULL ->
650 checkJumpTarget(currentFrame.decStack(1), bcs.dest());
651 case GOTO -> {
652 checkJumpTarget(currentFrame, bcs.dest());
653 ncf = true;
654 }
655 case GOTO_W -> {
656 checkJumpTarget(currentFrame, bcs.destW());
657 ncf = true;
658 }
659 case TABLESWITCH, LOOKUPSWITCH -> {
660 processSwitch(bcs);
661 ncf = true;
662 }
663 case LRETURN, DRETURN -> {
664 currentFrame.decStack(2);
665 ncf = true;
666 }
667 case IRETURN, FRETURN, ARETURN, ATHROW -> {
668 currentFrame.decStack(1);
669 ncf = true;
670 }
671 case GETSTATIC, PUTSTATIC, GETFIELD, PUTFIELD ->
672 processFieldInstructions(bcs);
673 case INVOKEVIRTUAL, INVOKESPECIAL, INVOKESTATIC, INVOKEINTERFACE, INVOKEDYNAMIC ->
674 this_uninit = processInvokeInstructions(bcs, (bci >= exMin && bci < exMax), this_uninit);
675 case NEW ->
676 currentFrame.pushStack(Type.uninitializedType(bci));
677 case NEWARRAY ->
678 currentFrame.decStack(1).pushStack(getNewarrayType(bcs.getIndex()));
679 case ANEWARRAY ->
680 processAnewarray(bcs.getIndexU2());
681 case CHECKCAST ->
682 currentFrame.decStack(1).pushStack(cpIndexToType(bcs.getIndexU2(), cp));
683 case MULTIANEWARRAY -> {
684 type1 = cpIndexToType(bcs.getIndexU2(), cp);
685 int dim = bcs.getU1Unchecked(bcs.bci() + 3);
686 for (int i = 0; i < dim; i++) {
687 currentFrame.popStack();
688 }
689 currentFrame.pushStack(type1);
690 }
691 case JSR, JSR_W, RET ->
692 throw generatorError("Instructions jsr, jsr_w, or ret must not appear in the class file version >= 51.0");
693 default ->
694 throw generatorError(String.format("Bad instruction: %02x", opcode));
695 }
696 if (!verified_exc_handlers && bci >= exMin && bci < exMax) {
697 processExceptionHandlerTargets(bci, this_uninit);
698 }
699 return ncf;
700 }
701
702 private void processExceptionHandlerTargets(int bci, boolean this_uninit) {
703 for (var ex : rawHandlers) {
704 if (bci == ex.start || (currentFrame.localsChanged && bci > ex.start && bci < ex.end)) {
705 int flags = currentFrame.flags;
706 if (this_uninit) flags |= FLAG_THIS_UNINIT;
707 Frame newFrame = currentFrame.frameInExceptionHandler(flags, ex.catchType);
708 checkJumpTarget(newFrame, ex.handler);
709 }
710 }
711 currentFrame.localsChanged = false;
712 }
713
714 private void processLdc(int index) {
715 switch (cp.entryByIndex(index).tag()) {
716 case TAG_UTF8 ->
717 currentFrame.pushStack(Type.OBJECT_TYPE);
718 case TAG_STRING ->
719 currentFrame.pushStack(Type.STRING_TYPE);
720 case TAG_CLASS ->
721 currentFrame.pushStack(Type.CLASS_TYPE);
722 case TAG_INTEGER ->
723 currentFrame.pushStack(Type.INTEGER_TYPE);
724 case TAG_FLOAT ->
725 currentFrame.pushStack(Type.FLOAT_TYPE);
726 case TAG_DOUBLE ->
727 currentFrame.pushStack(Type.DOUBLE_TYPE, Type.DOUBLE2_TYPE);
728 case TAG_LONG ->
729 currentFrame.pushStack(Type.LONG_TYPE, Type.LONG2_TYPE);
730 case TAG_METHOD_HANDLE ->
731 currentFrame.pushStack(Type.METHOD_HANDLE_TYPE);
732 case TAG_METHOD_TYPE ->
733 currentFrame.pushStack(Type.METHOD_TYPE);
734 case TAG_DYNAMIC ->
735 currentFrame.pushStack(cp.entryByIndex(index, ConstantDynamicEntry.class).typeSymbol());
736 default ->
737 throw generatorError("CP entry #%d %s is not loadable constant".formatted(index, cp.entryByIndex(index).tag()));
738 }
739 }
740
741 private void processSwitch(RawBytecodeHelper bcs) {
742 int bci = bcs.bci();
743 int alignedBci = RawBytecodeHelper.align(bci + 1);
744 int defaultOffset = bcs.getIntUnchecked(alignedBci);
745 int keys, delta;
746 currentFrame.popStack();
747 if (bcs.opcode() == TABLESWITCH) {
748 int low = bcs.getIntUnchecked(alignedBci + 4);
749 int high = bcs.getIntUnchecked(alignedBci + 2 * 4);
750 if (low > high) {
751 throw generatorError("low must be less than or equal to high in tableswitch");
752 }
753 keys = high - low + 1;
754 if (keys < 0) {
755 throw generatorError("too many keys in tableswitch");
756 }
757 delta = 1;
758 } else {
759 keys = bcs.getIntUnchecked(alignedBci + 4);
760 if (keys < 0) {
761 throw generatorError("number of keys in lookupswitch less than 0");
762 }
763 delta = 2;
764 for (int i = 0; i < (keys - 1); i++) {
765 int this_key = bcs.getIntUnchecked(alignedBci + (2 + 2 * i) * 4);
766 int next_key = bcs.getIntUnchecked(alignedBci + (2 + 2 * i + 2) * 4);
767 if (this_key >= next_key) {
768 throw generatorError("Bad lookupswitch instruction");
769 }
770 }
771 }
772 int target = bci + defaultOffset;
773 checkJumpTarget(currentFrame, target);
774 for (int i = 0; i < keys; i++) {
775 target = bci + bcs.getIntUnchecked(alignedBci + (3 + i * delta) * 4);
776 checkJumpTarget(currentFrame, target);
777 }
778 }
779
780 private void processFieldInstructions(RawBytecodeHelper bcs) {
781 var desc = Util.fieldTypeSymbol(cp.entryByIndex(bcs.getIndexU2(), MemberRefEntry.class).type());
782 var currentFrame = this.currentFrame;
783 switch (bcs.opcode()) {
784 case GETSTATIC ->
785 currentFrame.pushStack(desc);
786 case PUTSTATIC -> {
787 currentFrame.decStack(Util.isDoubleSlot(desc) ? 2 : 1);
788 }
789 case GETFIELD -> {
790 currentFrame.decStack(1);
791 currentFrame.pushStack(desc);
792 }
793 case PUTFIELD -> {
794 currentFrame.decStack(Util.isDoubleSlot(desc) ? 3 : 2);
795 }
796 default -> throw new AssertionError("Should not reach here");
797 }
798 }
799
800 private boolean processInvokeInstructions(RawBytecodeHelper bcs, boolean inTryBlock, boolean thisUninit) {
801 int index = bcs.getIndexU2();
802 int opcode = bcs.opcode();
803 var nameAndType = opcode == INVOKEDYNAMIC
804 ? cp.entryByIndex(index, InvokeDynamicEntry.class).nameAndType()
805 : cp.entryByIndex(index, MemberRefEntry.class).nameAndType();
806 var mDesc = Util.methodTypeSymbol(nameAndType.type());
807 int bci = bcs.bci();
808 var currentFrame = this.currentFrame;
809 currentFrame.decStack(Util.parameterSlots(mDesc));
810 if (opcode != INVOKESTATIC && opcode != INVOKEDYNAMIC) {
811 if (nameAndType.name().equalsString(OBJECT_INITIALIZER_NAME)) {
812 Type type = currentFrame.popStack();
813 if (type == Type.UNITIALIZED_THIS_TYPE) {
814 if (inTryBlock) {
815 processExceptionHandlerTargets(bci, true);
816 }
817 currentFrame.initializeObject(type, thisType);
818 thisUninit = true;
819 } else if (type.tag == ITEM_UNINITIALIZED) {
820 Type new_class_type = cpIndexToType(bcs.getU2(type.bci + 1), cp);
821 if (inTryBlock) {
822 processExceptionHandlerTargets(bci, thisUninit);
823 }
824 currentFrame.initializeObject(type, new_class_type);
825 } else {
826 throw generatorError("Bad operand type when invoking <init>");
827 }
828 } else {
829 currentFrame.decStack(1);
830 }
831 }
832 currentFrame.pushStack(mDesc.returnType());
833 return thisUninit;
834 }
835
836 private Type getNewarrayType(int index) {
837 if (index < T_BOOLEAN || index > T_LONG) throw generatorError("Illegal newarray instruction type %d".formatted(index));
838 return ARRAY_FROM_BASIC_TYPE[index];
839 }
840
841 private void processAnewarray(int index) {
842 currentFrame.popStack();
843 currentFrame.pushStack(cpIndexToType(index, cp).toArray());
844 }
845
846 /**
847 * {@return the generator error with attached details}
848 * @param msg error message
849 */
850 private IllegalArgumentException generatorError(String msg) {
851 return generatorError(msg, currentFrame.offset);
852 }
853
854 /**
855 * {@return the generator error with attached details}
856 * @param msg error message
857 * @param offset bytecode offset where the error occurred
858 */
859 private IllegalArgumentException generatorError(String msg, int offset) {
860 var sb = new StringBuilder("%s at bytecode offset %d of method %s(%s)".formatted(
861 msg,
862 offset,
863 methodName,
864 methodDesc.parameterList().stream().map(ClassDesc::displayName).collect(Collectors.joining(","))));
865 Util.dumpMethod(cp, thisType.sym(), methodName, methodDesc, isStatic ? ACC_STATIC : 0, bytecode, sb::append);
866 return new IllegalArgumentException(sb.toString());
867 }
868
869 /**
870 * Performs detection of mandatory stack map frames in a single bytecode traversing pass
871 * @return detected frames
872 */
873 private void detectFrames() {
874 var bcs = bytecode.start();
875 boolean no_control_flow = false;
876 int opcode, bci = 0;
877 while (bcs.next()) try {
878 opcode = bcs.opcode();
879 bci = bcs.bci();
880 if (no_control_flow) {
881 addFrame(bci);
882 }
883 no_control_flow = switch (opcode) {
884 case GOTO -> {
885 addFrame(bcs.dest());
886 yield true;
887 }
888 case GOTO_W -> {
889 addFrame(bcs.destW());
890 yield true;
891 }
892 case IF_ICMPEQ, IF_ICMPNE, IF_ICMPLT, IF_ICMPGE,
893 IF_ICMPGT, IF_ICMPLE, IFEQ, IFNE,
894 IFLT, IFGE, IFGT, IFLE, IF_ACMPEQ,
895 IF_ACMPNE , IFNULL , IFNONNULL -> {
896 addFrame(bcs.dest());
897 yield false;
898 }
899 case TABLESWITCH, LOOKUPSWITCH -> {
900 int aligned_bci = RawBytecodeHelper.align(bci + 1);
901 int default_ofset = bcs.getIntUnchecked(aligned_bci);
902 int keys, delta;
903 if (bcs.opcode() == TABLESWITCH) {
904 int low = bcs.getIntUnchecked(aligned_bci + 4);
905 int high = bcs.getIntUnchecked(aligned_bci + 2 * 4);
906 keys = high - low + 1;
907 delta = 1;
908 } else {
909 keys = bcs.getIntUnchecked(aligned_bci + 4);
910 delta = 2;
911 }
912 addFrame(bci + default_ofset);
913 for (int i = 0; i < keys; i++) {
914 addFrame(bci + bcs.getIntUnchecked(aligned_bci + (3 + i * delta) * 4));
915 }
916 yield true;
917 }
918 case IRETURN, LRETURN, FRETURN, DRETURN,
919 ARETURN, RETURN, ATHROW -> true;
920 default -> false;
921 };
922 } catch (IllegalArgumentException iae) {
923 throw generatorError("Detected branch target out of bytecode range", bci);
924 }
925 for (int i = 0; i < rawHandlers.size(); i++) try {
926 addFrame(rawHandlers.get(i).handler());
927 } catch (IllegalArgumentException iae) {
928 if (!filterDeadLabels)
929 throw generatorError("Detected exception handler out of bytecode range");
930 }
931 }
932
933 private void addFrame(int offset) {
934 Preconditions.checkIndex(offset, bytecode.length(), RawBytecodeHelper.IAE_FORMATTER);
935 var frames = this.frames;
936 int i = 0, framesCount = this.framesCount;
937 for (; i < framesCount; i++) {
938 var frameOffset = frames[i].offset;
939 if (frameOffset == offset) {
940 return;
941 }
942 if (frameOffset > offset) {
943 break;
944 }
945 }
946 if (framesCount >= frames.length) {
947 int newCapacity = framesCount + 8;
948 this.frames = frames = framesCount == 0 ? new Frame[newCapacity] : Arrays.copyOf(frames, newCapacity);
949 }
950 if (i != framesCount) {
951 System.arraycopy(frames, i, frames, i + 1, framesCount - i);
952 }
953 frames[i] = new Frame(offset, classHierarchy);
954 this.framesCount = framesCount + 1;
955 }
956
957 private final class Frame {
958
959 int offset;
960 int localsSize, stackSize;
961 int flags;
962 int frameMaxStack = 0, frameMaxLocals = 0;
963 boolean dirty = false;
964 boolean localsChanged = false;
965
966 private final ClassHierarchyImpl classHierarchy;
967
968 private Type[] locals, stack;
969
970 Frame(ClassHierarchyImpl classHierarchy) {
971 this(-1, 0, 0, 0, null, null, classHierarchy);
972 }
973
974 Frame(int offset, ClassHierarchyImpl classHierarchy) {
975 this(offset, -1, 0, 0, null, null, classHierarchy);
976 }
977
978 Frame(int offset, int flags, int locals_size, int stack_size, Type[] locals, Type[] stack, ClassHierarchyImpl classHierarchy) {
979 this.offset = offset;
980 this.localsSize = locals_size;
981 this.stackSize = stack_size;
982 this.flags = flags;
983 this.locals = locals;
984 this.stack = stack;
985 this.classHierarchy = classHierarchy;
986 }
987
988 @Override
989 public String toString() {
990 return (dirty ? "frame* @" : "frame @") + offset + " with locals " + (locals == null ? "[]" : Arrays.asList(locals).subList(0, localsSize)) + " and stack " + (stack == null ? "[]" : Arrays.asList(stack).subList(0, stackSize));
991 }
992
993 Frame pushStack(ClassDesc desc) {
994 if (desc == CD_long) return pushStack(Type.LONG_TYPE, Type.LONG2_TYPE);
995 if (desc == CD_double) return pushStack(Type.DOUBLE_TYPE, Type.DOUBLE2_TYPE);
996 return desc == CD_void ? this
997 : pushStack(
998 desc.isPrimitive()
999 ? (desc == CD_float ? Type.FLOAT_TYPE : Type.INTEGER_TYPE)
1000 : Type.referenceType(desc));
1001 }
1002
1003 Frame pushStack(Type type) {
1004 checkStack(stackSize);
1005 stack[stackSize++] = type;
1006 return this;
1007 }
1008
1009 Frame pushStack(Type type1, Type type2) {
1010 checkStack(stackSize + 1);
1011 stack[stackSize++] = type1;
1012 stack[stackSize++] = type2;
1013 return this;
1014 }
1015
1016 Type popStack() {
1017 if (stackSize < 1) throw generatorError("Operand stack underflow");
1018 return stack[--stackSize];
1019 }
1020
1021 Frame decStack(int size) {
1022 stackSize -= size;
1023 if (stackSize < 0) throw generatorError("Operand stack underflow");
1024 return this;
1025 }
1026
1027 Frame frameInExceptionHandler(int flags, Type excType) {
1028 return new Frame(offset, flags, localsSize, 1, locals, new Type[] {excType}, classHierarchy);
1029 }
1030
1031 void initializeObject(Type old_object, Type new_object) {
1032 int i;
1033 for (i = 0; i < localsSize; i++) {
1034 if (locals[i].equals(old_object)) {
1035 locals[i] = new_object;
1036 localsChanged = true;
1037 }
1038 }
1039 for (i = 0; i < stackSize; i++) {
1040 if (stack[i].equals(old_object)) {
1041 stack[i] = new_object;
1042 }
1043 }
1044 if (old_object == Type.UNITIALIZED_THIS_TYPE) {
1045 flags = 0;
1046 }
1047 }
1048
1049 Frame checkLocal(int index) {
1050 if (index >= frameMaxLocals) frameMaxLocals = index + 1;
1051 if (locals == null) {
1052 locals = new Type[index + FRAME_DEFAULT_CAPACITY];
1053 Arrays.fill(locals, Type.TOP_TYPE);
1054 } else if (index >= locals.length) {
1055 int current = locals.length;
1056 locals = Arrays.copyOf(locals, index + FRAME_DEFAULT_CAPACITY);
1057 Arrays.fill(locals, current, locals.length, Type.TOP_TYPE);
1058 }
1059 return this;
1060 }
1061
1062 private void checkStack(int index) {
1063 if (index >= frameMaxStack) frameMaxStack = index + 1;
1064 if (stack == null) {
1065 stack = new Type[index + FRAME_DEFAULT_CAPACITY];
1066 Arrays.fill(stack, Type.TOP_TYPE);
1067 } else if (index >= stack.length) {
1068 int current = stack.length;
1069 stack = Arrays.copyOf(stack, index + FRAME_DEFAULT_CAPACITY);
1070 Arrays.fill(stack, current, stack.length, Type.TOP_TYPE);
1071 }
1072 }
1073
1074 private void setLocalRawInternal(int index, Type type) {
1075 checkLocal(index);
1076 localsChanged |= !type.equals(locals[index]);
1077 locals[index] = type;
1078 }
1079
1080 void setLocalsFromArg(String name, MethodTypeDesc methodDesc, boolean isStatic, Type thisKlass) {
1081 int localsSize = 0;
1082 // Pre-emptively create a locals array that encompass all parameter slots
1083 checkLocal(Util.parameterSlots(methodDesc) + (isStatic ? -1 : 0));
1084 Type type;
1085 Type[] locals = this.locals;
1086 if (!isStatic) {
1087 if (OBJECT_INITIALIZER_NAME.equals(name) && !CD_Object.equals(thisKlass.sym)) {
1088 type = Type.UNITIALIZED_THIS_TYPE;
1089 flags |= FLAG_THIS_UNINIT;
1090 } else {
1091 type = thisKlass;
1092 }
1093 locals[localsSize++] = type;
1094 }
1095 for (int i = 0; i < methodDesc.parameterCount(); i++) {
1096 var desc = methodDesc.parameterType(i);
1097 if (desc == CD_long) {
1098 locals[localsSize ] = Type.LONG_TYPE;
1099 locals[localsSize + 1] = Type.LONG2_TYPE;
1100 localsSize += 2;
1101 } else if (desc == CD_double) {
1102 locals[localsSize ] = Type.DOUBLE_TYPE;
1103 locals[localsSize + 1] = Type.DOUBLE2_TYPE;
1104 localsSize += 2;
1105 } else {
1106 if (!desc.isPrimitive()) {
1107 type = Type.referenceType(desc);
1108 } else if (desc == CD_float) {
1109 type = Type.FLOAT_TYPE;
1110 } else {
1111 type = Type.INTEGER_TYPE;
1112 }
1113 locals[localsSize++] = type;
1114 }
1115 }
1116 this.localsSize = localsSize;
1117 }
1118
1119 void copyFrom(Frame src) {
1120 if (locals != null && src.localsSize < locals.length) Arrays.fill(locals, src.localsSize, locals.length, Type.TOP_TYPE);
1121 localsSize = src.localsSize;
1122 checkLocal(src.localsSize - 1);
1123 if (src.localsSize > 0) System.arraycopy(src.locals, 0, locals, 0, src.localsSize);
1124 if (stack != null && src.stackSize < stack.length) Arrays.fill(stack, src.stackSize, stack.length, Type.TOP_TYPE);
1125 stackSize = src.stackSize;
1126 checkStack(src.stackSize - 1);
1127 if (src.stackSize > 0) System.arraycopy(src.stack, 0, stack, 0, src.stackSize);
1128 flags = src.flags;
1129 localsChanged = true;
1130 }
1131
1132 void checkAssignableTo(Frame target) {
1133 int localsSize = this.localsSize;
1134 int stackSize = this.stackSize;
1135 if (target.flags == -1) {
1136 target.locals = locals == null ? null : locals.clone();
1137 target.localsSize = localsSize;
1138 if (stackSize > 0) {
1139 target.stack = stack.clone();
1140 target.stackSize = stackSize;
1141 }
1142 target.flags = flags;
1143 target.dirty = true;
1144 } else {
1145 if (target.localsSize > localsSize) {
1146 target.localsSize = localsSize;
1147 target.dirty = true;
1148 }
1149 for (int i = 0; i < target.localsSize; i++) {
1150 merge(locals[i], target.locals, i, target);
1151 }
1152 if (stackSize != target.stackSize) {
1153 throw generatorError("Stack size mismatch");
1154 }
1155 for (int i = 0; i < target.stackSize; i++) {
1156 if (merge(stack[i], target.stack, i, target) == Type.TOP_TYPE) {
1157 throw generatorError("Stack content mismatch");
1158 }
1159 }
1160 }
1161 }
1162
1163 private Type getLocalRawInternal(int index) {
1164 checkLocal(index);
1165 return locals[index];
1166 }
1167
1168 Type getLocal(int index) {
1169 Type ret = getLocalRawInternal(index);
1170 if (index >= localsSize) {
1171 localsSize = index + 1;
1172 }
1173 return ret;
1174 }
1175
1176 void setLocal(int index, Type type) {
1177 Type old = getLocalRawInternal(index);
1178 if (old == Type.DOUBLE_TYPE || old == Type.LONG_TYPE) {
1179 setLocalRawInternal(index + 1, Type.TOP_TYPE);
1180 }
1181 if (old == Type.DOUBLE2_TYPE || old == Type.LONG2_TYPE) {
1182 setLocalRawInternal(index - 1, Type.TOP_TYPE);
1183 }
1184 setLocalRawInternal(index, type);
1185 if (index >= localsSize) {
1186 localsSize = index + 1;
1187 }
1188 }
1189
1190 void setLocal2(int index, Type type1, Type type2) {
1191 Type old = getLocalRawInternal(index + 1);
1192 if (old == Type.DOUBLE_TYPE || old == Type.LONG_TYPE) {
1193 setLocalRawInternal(index + 2, Type.TOP_TYPE);
1194 }
1195 old = getLocalRawInternal(index);
1196 if (old == Type.DOUBLE2_TYPE || old == Type.LONG2_TYPE) {
1197 setLocalRawInternal(index - 1, Type.TOP_TYPE);
1198 }
1199 setLocalRawInternal(index, type1);
1200 setLocalRawInternal(index + 1, type2);
1201 if (index >= localsSize - 1) {
1202 localsSize = index + 2;
1203 }
1204 }
1205
1206 private Type merge(Type me, Type[] toTypes, int i, Frame target) {
1207 var to = toTypes[i];
1208 var newTo = to.mergeFrom(me, classHierarchy);
1209 if (to != newTo && !to.equals(newTo)) {
1210 toTypes[i] = newTo;
1211 target.dirty = true;
1212 }
1213 return newTo;
1214 }
1215
1216 private static int trimAndCompress(Type[] types, int count) {
1217 while (count > 0 && types[count - 1] == Type.TOP_TYPE) count--;
1218 int compressed = 0;
1219 for (int i = 0; i < count; i++) {
1220 if (!types[i].isCategory2_2nd()) {
1221 if (compressed != i) {
1222 types[compressed] = types[i];
1223 }
1224 compressed++;
1225 }
1226 }
1227 return compressed;
1228 }
1229
1230 void trimAndCompress() {
1231 localsSize = trimAndCompress(locals, localsSize);
1232 stackSize = trimAndCompress(stack, stackSize);
1233 }
1234
1235 private static boolean equals(Type[] l1, Type[] l2, int commonSize) {
1236 if (l1 == null || l2 == null) return commonSize == 0;
1237 return Arrays.equals(l1, 0, commonSize, l2, 0, commonSize);
1238 }
1239
1240 void writeTo(BufWriterImpl out, Frame prevFrame, ConstantPoolBuilder cp) {
1241 int localsSize = this.localsSize;
1242 int stackSize = this.stackSize;
1243 int offsetDelta = offset - prevFrame.offset - 1;
1244 if (stackSize == 0) {
1245 int commonLocalsSize = localsSize > prevFrame.localsSize ? prevFrame.localsSize : localsSize;
1246 int diffLocalsSize = localsSize - prevFrame.localsSize;
1247 if (-3 <= diffLocalsSize && diffLocalsSize <= 3 && equals(locals, prevFrame.locals, commonLocalsSize)) {
1248 if (diffLocalsSize == 0 && offsetDelta <= SAME_FRAME_END) { //same frame
1249 out.writeU1(offsetDelta);
1250 } else { //chop, same extended or append frame
1251 out.writeU1U2(SAME_FRAME_EXTENDED + diffLocalsSize, offsetDelta);
1252 for (int i=commonLocalsSize; i<localsSize; i++) locals[i].writeTo(out, cp);
1253 }
1254 return;
1255 }
1256 } else if (stackSize == 1 && localsSize == prevFrame.localsSize && equals(locals, prevFrame.locals, localsSize)) {
1257 if (offsetDelta <= SAME_LOCALS_1_STACK_ITEM_FRAME_END - SAME_LOCALS_1_STACK_ITEM_FRAME_START) { //same locals 1 stack item frame
1258 out.writeU1(SAME_LOCALS_1_STACK_ITEM_FRAME_START + offsetDelta);
1259 } else { //same locals 1 stack item extended frame
1260 out.writeU1U2(SAME_LOCALS_1_STACK_ITEM_EXTENDED, offsetDelta);
1261 }
1262 stack[0].writeTo(out, cp);
1263 return;
1264 }
1265 //full frame
1266 out.writeU1U2U2(FULL_FRAME, offsetDelta, localsSize);
1267 for (int i=0; i<localsSize; i++) locals[i].writeTo(out, cp);
1268 out.writeU2(stackSize);
1269 for (int i=0; i<stackSize; i++) stack[i].writeTo(out, cp);
1270 }
1271 }
1272
1273 private static record Type(int tag, ClassDesc sym, int bci) {
1274
1275 //singleton types
1276 static final Type TOP_TYPE = simpleType(ITEM_TOP),
1277 NULL_TYPE = simpleType(ITEM_NULL),
1278 INTEGER_TYPE = simpleType(ITEM_INTEGER),
1279 FLOAT_TYPE = simpleType(ITEM_FLOAT),
1280 LONG_TYPE = simpleType(ITEM_LONG),
1281 LONG2_TYPE = simpleType(ITEM_LONG_2ND),
1282 DOUBLE_TYPE = simpleType(ITEM_DOUBLE),
1283 BOOLEAN_TYPE = simpleType(ITEM_BOOLEAN),
1284 BYTE_TYPE = simpleType(ITEM_BYTE),
1285 CHAR_TYPE = simpleType(ITEM_CHAR),
1286 SHORT_TYPE = simpleType(ITEM_SHORT),
1287 DOUBLE2_TYPE = simpleType(ITEM_DOUBLE_2ND),
1288 UNITIALIZED_THIS_TYPE = simpleType(ITEM_UNINITIALIZED_THIS);
1289
1290 //frequently used types to reduce footprint
1291 static final Type OBJECT_TYPE = referenceType(CD_Object),
1292 THROWABLE_TYPE = referenceType(CD_Throwable),
1293 INT_ARRAY_TYPE = referenceType(CD_int.arrayType()),
1294 BOOLEAN_ARRAY_TYPE = referenceType(CD_boolean.arrayType()),
1295 BYTE_ARRAY_TYPE = referenceType(CD_byte.arrayType()),
1296 CHAR_ARRAY_TYPE = referenceType(CD_char.arrayType()),
1297 SHORT_ARRAY_TYPE = referenceType(CD_short.arrayType()),
1298 LONG_ARRAY_TYPE = referenceType(CD_long.arrayType()),
1299 DOUBLE_ARRAY_TYPE = referenceType(CD_double.arrayType()),
1300 FLOAT_ARRAY_TYPE = referenceType(CD_float.arrayType()),
1301 STRING_TYPE = referenceType(CD_String),
1302 CLASS_TYPE = referenceType(CD_Class),
1303 METHOD_HANDLE_TYPE = referenceType(CD_MethodHandle),
1304 METHOD_TYPE = referenceType(CD_MethodType);
1305
1306 private static Type simpleType(int tag) {
1307 return new Type(tag, null, 0);
1308 }
1309
1310 static Type referenceType(ClassDesc desc) {
1311 return new Type(ITEM_OBJECT, desc, 0);
1312 }
1313
1314 static Type uninitializedType(int bci) {
1315 return new Type(ITEM_UNINITIALIZED, null, bci);
1316 }
1317
1318 @Override //mandatory override to avoid use of method reference during JDK bootstrap
1319 public boolean equals(Object o) {
1320 return (o instanceof Type t) && t.tag == tag && t.bci == bci && Objects.equals(sym, t.sym);
1321 }
1322
1323 boolean isCategory2_2nd() {
1324 return this == DOUBLE2_TYPE || this == LONG2_TYPE;
1325 }
1326
1327 boolean isReference() {
1328 return tag == ITEM_OBJECT || this == NULL_TYPE;
1329 }
1330
1331 boolean isObject() {
1332 return tag == ITEM_OBJECT && sym.isClassOrInterface();
1333 }
1334
1335 boolean isArray() {
1336 return tag == ITEM_OBJECT && sym.isArray();
1337 }
1338
1339 Type mergeFrom(Type from, ClassHierarchyImpl context) {
1340 if (this == TOP_TYPE || this == from || equals(from)) {
1341 return this;
1342 } else {
1343 return switch (tag) {
1344 case ITEM_BOOLEAN, ITEM_BYTE, ITEM_CHAR, ITEM_SHORT ->
1345 from == INTEGER_TYPE ? this : TOP_TYPE;
1346 default ->
1347 isReference() && from.isReference() ? mergeReferenceFrom(from, context) : TOP_TYPE;
1348 };
1349 }
1350 }
1351
1352 Type mergeComponentFrom(Type from, ClassHierarchyImpl context) {
1353 if (this == TOP_TYPE || this == from || equals(from)) {
1354 return this;
1355 } else {
1356 return switch (tag) {
1357 case ITEM_BOOLEAN, ITEM_BYTE, ITEM_CHAR, ITEM_SHORT ->
1358 TOP_TYPE;
1359 default ->
1360 isReference() && from.isReference() ? mergeReferenceFrom(from, context) : TOP_TYPE;
1361 };
1362 }
1363 }
1364
1365 private static final ClassDesc CD_Cloneable = ClassOrInterfaceDescImpl.ofValidated("Ljava/lang/Cloneable;");
1366 private static final ClassDesc CD_Serializable = ClassOrInterfaceDescImpl.ofValidated("Ljava/io/Serializable;");
1367
1368 private Type mergeReferenceFrom(Type from, ClassHierarchyImpl context) {
1369 if (from == NULL_TYPE) {
1370 return this;
1371 } else if (this == NULL_TYPE) {
1372 return from;
1373 } else if (sym.equals(from.sym)) {
1374 return this;
1375 } else if (isObject()) {
1376 if (CD_Object.equals(sym)) {
1377 return this;
1378 }
1379 if (context.isInterface(sym)) {
1380 if (!from.isArray() || CD_Cloneable.equals(sym) || CD_Serializable.equals(sym)) {
1381 return this;
1382 }
1383 } else if (from.isObject()) {
1384 var anc = context.commonAncestor(sym, from.sym);
1385 return anc == null ? this : Type.referenceType(anc);
1386 }
1387 } else if (isArray() && from.isArray()) {
1388 Type compThis = getComponent();
1389 Type compFrom = from.getComponent();
1390 if (compThis != TOP_TYPE && compFrom != TOP_TYPE) {
1391 return compThis.mergeComponentFrom(compFrom, context).toArray();
1392 }
1393 }
1394 return OBJECT_TYPE;
1395 }
1396
1397 Type toArray() {
1398 return switch (tag) {
1399 case ITEM_BOOLEAN -> BOOLEAN_ARRAY_TYPE;
1400 case ITEM_BYTE -> BYTE_ARRAY_TYPE;
1401 case ITEM_CHAR -> CHAR_ARRAY_TYPE;
1402 case ITEM_SHORT -> SHORT_ARRAY_TYPE;
1403 case ITEM_INTEGER -> INT_ARRAY_TYPE;
1404 case ITEM_LONG -> LONG_ARRAY_TYPE;
1405 case ITEM_FLOAT -> FLOAT_ARRAY_TYPE;
1406 case ITEM_DOUBLE -> DOUBLE_ARRAY_TYPE;
1407 case ITEM_OBJECT -> Type.referenceType(sym.arrayType());
1408 default -> OBJECT_TYPE;
1409 };
1410 }
1411
1412 Type getComponent() {
1413 if (isArray()) {
1414 var comp = sym.componentType();
1415 if (comp.isPrimitive()) {
1416 return switch (comp.descriptorString().charAt(0)) {
1417 case 'Z' -> Type.BOOLEAN_TYPE;
1418 case 'B' -> Type.BYTE_TYPE;
1419 case 'C' -> Type.CHAR_TYPE;
1420 case 'S' -> Type.SHORT_TYPE;
1421 case 'I' -> Type.INTEGER_TYPE;
1422 case 'J' -> Type.LONG_TYPE;
1423 case 'F' -> Type.FLOAT_TYPE;
1424 case 'D' -> Type.DOUBLE_TYPE;
1425 default -> Type.TOP_TYPE;
1426 };
1427 }
1428 return Type.referenceType(comp);
1429 }
1430 return Type.TOP_TYPE;
1431 }
1432
1433 void writeTo(BufWriterImpl bw, ConstantPoolBuilder cp) {
1434 switch (tag) {
1435 case ITEM_OBJECT ->
1436 bw.writeU1U2(tag, cp.classEntry(sym).index());
1437 case ITEM_UNINITIALIZED ->
1438 bw.writeU1U2(tag, bci);
1439 default ->
1440 bw.writeU1(tag);
1441 }
1442 }
1443 }
1444 }