1 /*
2 * Copyright (c) 2022, 2024, 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 private static final int ITEM_TOP = 0,
170 ITEM_INTEGER = 1,
171 ITEM_FLOAT = 2,
172 ITEM_DOUBLE = 3,
173 ITEM_LONG = 4,
174 ITEM_NULL = 5,
175 ITEM_UNINITIALIZED_THIS = 6,
176 ITEM_OBJECT = 7,
177 ITEM_UNINITIALIZED = 8,
178 ITEM_BOOLEAN = 9,
179 ITEM_BYTE = 10,
180 ITEM_SHORT = 11,
181 ITEM_CHAR = 12,
182 ITEM_LONG_2ND = 13,
183 ITEM_DOUBLE_2ND = 14;
184
185 private static final Type[] ARRAY_FROM_BASIC_TYPE = {null, null, null, null,
186 Type.BOOLEAN_ARRAY_TYPE, Type.CHAR_ARRAY_TYPE, Type.FLOAT_ARRAY_TYPE, Type.DOUBLE_ARRAY_TYPE,
187 Type.BYTE_ARRAY_TYPE, Type.SHORT_ARRAY_TYPE, Type.INT_ARRAY_TYPE, Type.LONG_ARRAY_TYPE};
188
189 static record RawExceptionCatch(int start, int end, int handler, Type catchType) {}
190
191 private final Type thisType;
192 private final String methodName;
193 private final MethodTypeDesc methodDesc;
194 private final RawBytecodeHelper.CodeRange bytecode;
195 private final SplitConstantPool cp;
196 private final boolean isStatic;
197 private final LabelContext labelContext;
198 private final List<AbstractPseudoInstruction.ExceptionCatchImpl> handlers;
199 private final List<RawExceptionCatch> rawHandlers;
200 private final ClassHierarchyImpl classHierarchy;
201 private final boolean patchDeadCode;
202 private final boolean filterDeadLabels;
203 private Frame[] frames = EMPTY_FRAME_ARRAY;
204 private int framesCount = 0;
205 private final Frame currentFrame;
206 private int maxStack, maxLocals;
207
208 /**
209 * Primary constructor of the <code>Generator</code> class.
210 * New <code>Generator</code> instance must be created for each individual class/method.
211 * Instance contains only immutable results, all the calculations are processed during instance construction.
212 *
213 * @param labelContext <code>LabelContext</code> instance used to resolve or patch <code>ExceptionHandler</code>
214 * labels to bytecode offsets (or vice versa)
215 * @param thisClass class to generate stack maps for
216 * @param methodName method name to generate stack maps for
217 * @param methodDesc method descriptor to generate stack maps for
218 * @param isStatic information whether the method is static
219 * @param bytecode R/W <code>ByteBuffer</code> wrapping method bytecode, the content is altered in case <code>Generator</code> detects and patches dead code
220 * @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
221 * @param handlers R/W <code>ExceptionHandler</code> list used to detect mandatory frame offsets as well as to determine stack maps in exception handlers
222 * and also to be altered when dead code is detected and must be excluded from exception handlers
223 */
224 public StackMapGenerator(LabelContext labelContext,
225 ClassDesc thisClass,
226 String methodName,
227 MethodTypeDesc methodDesc,
228 boolean isStatic,
229 RawBytecodeHelper.CodeRange bytecode,
230 SplitConstantPool cp,
231 ClassFileImpl context,
232 List<AbstractPseudoInstruction.ExceptionCatchImpl> handlers) {
233 this.thisType = Type.referenceType(thisClass);
234 this.methodName = methodName;
235 this.methodDesc = methodDesc;
236 this.isStatic = isStatic;
237 this.bytecode = bytecode;
238 this.cp = cp;
239 this.labelContext = labelContext;
240 this.handlers = handlers;
241 this.rawHandlers = new ArrayList<>(handlers.size());
242 this.classHierarchy = new ClassHierarchyImpl(context.classHierarchyResolver());
243 this.patchDeadCode = context.patchDeadCode();
244 this.filterDeadLabels = context.dropDeadLabels();
245 this.currentFrame = new Frame(classHierarchy);
246 generate();
247 }
248
249 /**
250 * Calculated maximum number of the locals required
251 * @return maximum number of the locals required
252 */
253 public int maxLocals() {
254 return maxLocals;
255 }
256
257 /**
258 * Calculated maximum stack size required
259 * @return maximum stack size required
260 */
261 public int maxStack() {
262 return maxStack;
263 }
264
265 private Frame getFrame(int offset) {
266 //binary search over frames ordered by offset
267 int low = 0;
268 int high = framesCount - 1;
269 while (low <= high) {
270 int mid = (low + high) >>> 1;
271 var f = frames[mid];
272 if (f.offset < offset)
273 low = mid + 1;
274 else if (f.offset > offset)
275 high = mid - 1;
276 else
277 return f;
278 }
279 return null;
280 }
281
282 private void checkJumpTarget(Frame frame, int target) {
283 frame.checkAssignableTo(getFrame(target));
284 }
285
286 private int exMin, exMax;
287
288 private boolean isAnyFrameDirty() {
289 for (int i = 0; i < framesCount; i++) {
290 if (frames[i].dirty) return true;
291 }
292 return false;
293 }
294
295 private void generate() {
296 exMin = bytecode.length();
297 exMax = -1;
298 if (!handlers.isEmpty()) {
299 generateHandlers();
300 }
301 detectFrames();
302 do {
303 processMethod();
304 } while (isAnyFrameDirty());
305 maxLocals = currentFrame.frameMaxLocals;
306 maxStack = currentFrame.frameMaxStack;
307
308 //dead code patching
309 for (int i = 0; i < framesCount; i++) {
310 var frame = frames[i];
311 if (frame.flags == -1) {
312 deadCodePatching(frame, i);
313 }
314 }
315 }
316
317 private void generateHandlers() {
318 var labelContext = this.labelContext;
319 for (int i = 0; i < handlers.size(); i++) {
320 var exhandler = handlers.get(i);
321 int start_pc = labelContext.labelToBci(exhandler.tryStart());
322 int end_pc = labelContext.labelToBci(exhandler.tryEnd());
323 int handler_pc = labelContext.labelToBci(exhandler.handler());
324 if (start_pc >= 0 && end_pc >= 0 && end_pc > start_pc && handler_pc >= 0) {
325 if (start_pc < exMin) exMin = start_pc;
326 if (end_pc > exMax) exMax = end_pc;
327 var catchType = exhandler.catchType();
328 rawHandlers.add(new RawExceptionCatch(start_pc, end_pc, handler_pc,
329 catchType.isPresent() ? cpIndexToType(catchType.get().index(), cp)
330 : Type.THROWABLE_TYPE));
331 }
332 }
333 }
334
335 private void deadCodePatching(Frame frame, int i) {
336 if (!patchDeadCode) throw generatorError("Unable to generate stack map frame for dead code", frame.offset);
337 //patch frame
338 frame.pushStack(Type.THROWABLE_TYPE);
339 if (maxStack < 1) maxStack = 1;
340 int end = (i < framesCount - 1 ? frames[i + 1].offset : bytecode.length()) - 1;
341 //patch bytecode
342 var arr = bytecode.array();
343 Arrays.fill(arr, frame.offset, end, (byte) NOP);
344 arr[end] = (byte) ATHROW;
345 //patch handlers
346 removeRangeFromExcTable(frame.offset, end + 1);
347 }
348
349 private void removeRangeFromExcTable(int rangeStart, int rangeEnd) {
350 var it = handlers.listIterator();
351 while (it.hasNext()) {
352 var e = it.next();
353 int handlerStart = labelContext.labelToBci(e.tryStart());
354 int handlerEnd = labelContext.labelToBci(e.tryEnd());
355 if (rangeStart >= handlerEnd || rangeEnd <= handlerStart) {
356 //out of range
357 continue;
358 }
359 if (rangeStart <= handlerStart) {
360 if (rangeEnd >= handlerEnd) {
361 //complete removal
362 it.remove();
363 } else {
364 //cut from left
365 Label newStart = labelContext.newLabel();
366 labelContext.setLabelTarget(newStart, rangeEnd);
367 it.set(new AbstractPseudoInstruction.ExceptionCatchImpl(e.handler(), newStart, e.tryEnd(), e.catchType()));
368 }
369 } else if (rangeEnd >= handlerEnd) {
370 //cut from right
371 Label newEnd = labelContext.newLabel();
372 labelContext.setLabelTarget(newEnd, rangeStart);
373 it.set(new AbstractPseudoInstruction.ExceptionCatchImpl(e.handler(), e.tryStart(), newEnd, e.catchType()));
374 } else {
375 //split
376 Label newStart = labelContext.newLabel();
377 labelContext.setLabelTarget(newStart, rangeEnd);
378 Label newEnd = labelContext.newLabel();
379 labelContext.setLabelTarget(newEnd, rangeStart);
380 it.set(new AbstractPseudoInstruction.ExceptionCatchImpl(e.handler(), e.tryStart(), newEnd, e.catchType()));
381 it.add(new AbstractPseudoInstruction.ExceptionCatchImpl(e.handler(), newStart, e.tryEnd(), e.catchType()));
382 }
383 }
384 }
385
386 /**
387 * Getter of the generated <code>StackMapTableAttribute</code> or null if stack map is empty
388 * @return <code>StackMapTableAttribute</code> or null if stack map is empty
389 */
390 public Attribute<? extends StackMapTableAttribute> stackMapTableAttribute() {
391 return framesCount == 0 ? null : new UnboundAttribute.AdHocAttribute<>(Attributes.stackMapTable()) {
392 @Override
393 public void writeBody(BufWriterImpl b) {
394 b.writeU2(framesCount);
395 Frame prevFrame = new Frame(classHierarchy);
396 prevFrame.setLocalsFromArg(methodName, methodDesc, isStatic, thisType);
397 prevFrame.trimAndCompress();
398 for (int i = 0; i < framesCount; i++) {
399 var fr = frames[i];
400 fr.trimAndCompress();
401 fr.writeTo(b, prevFrame, cp);
402 prevFrame = fr;
403 }
404 }
405
406 @Override
407 public Utf8Entry attributeName() {
408 return cp.utf8Entry(Attributes.NAME_STACK_MAP_TABLE);
409 }
410 };
411 }
412
413 private static Type cpIndexToType(int index, ConstantPoolBuilder cp) {
414 return Type.referenceType(cp.entryByIndex(index, ClassEntry.class).asSymbol());
415 }
416
417 private void processMethod() {
418 var frames = this.frames;
419 var currentFrame = this.currentFrame;
420 currentFrame.setLocalsFromArg(methodName, methodDesc, isStatic, thisType);
421 currentFrame.stackSize = 0;
422 currentFrame.flags = 0;
423 currentFrame.offset = -1;
424 int stackmapIndex = 0;
425 var bcs = bytecode.start();
426 boolean ncf = false;
427 while (bcs.next()) {
428 currentFrame.offset = bcs.bci();
429 if (stackmapIndex < framesCount) {
430 int thisOffset = frames[stackmapIndex].offset;
431 if (ncf && thisOffset > bcs.bci()) {
432 throw generatorError("Expecting a stack map frame");
433 }
434 if (thisOffset == bcs.bci()) {
435 Frame nextFrame = frames[stackmapIndex++];
436 if (!ncf) {
437 currentFrame.checkAssignableTo(nextFrame);
438 }
439 while (!nextFrame.dirty) { //skip unmatched frames
440 if (stackmapIndex == framesCount) return; //skip the rest of this round
441 nextFrame = frames[stackmapIndex++];
442 }
443 bcs.reset(nextFrame.offset); //skip code up-to the next frame
444 bcs.next();
445 currentFrame.offset = bcs.bci();
446 currentFrame.copyFrom(nextFrame);
447 nextFrame.dirty = false;
448 } else if (thisOffset < bcs.bci()) {
449 throw generatorError("Bad stack map offset");
450 }
451 } else if (ncf) {
452 throw generatorError("Expecting a stack map frame");
453 }
454 ncf = processBlock(bcs);
455 }
456 }
457
458 private boolean processBlock(RawBytecodeHelper bcs) {
459 int opcode = bcs.opcode();
460 boolean ncf = false;
461 boolean this_uninit = false;
462 boolean verified_exc_handlers = false;
463 int bci = bcs.bci();
464 Type type1, type2, type3, type4;
465 if (RawBytecodeHelper.isStoreIntoLocal(opcode) && bci >= exMin && bci < exMax) {
466 processExceptionHandlerTargets(bci, this_uninit);
467 verified_exc_handlers = true;
468 }
469 switch (opcode) {
470 case NOP -> {}
471 case RETURN -> {
472 ncf = true;
473 }
474 case ACONST_NULL ->
475 currentFrame.pushStack(Type.NULL_TYPE);
476 case ICONST_M1, ICONST_0, ICONST_1, ICONST_2, ICONST_3, ICONST_4, ICONST_5, SIPUSH, BIPUSH ->
477 currentFrame.pushStack(Type.INTEGER_TYPE);
478 case LCONST_0, LCONST_1 ->
479 currentFrame.pushStack(Type.LONG_TYPE, Type.LONG2_TYPE);
480 case FCONST_0, FCONST_1, FCONST_2 ->
481 currentFrame.pushStack(Type.FLOAT_TYPE);
482 case DCONST_0, DCONST_1 ->
483 currentFrame.pushStack(Type.DOUBLE_TYPE, Type.DOUBLE2_TYPE);
484 case LDC ->
485 processLdc(bcs.getIndexU1());
486 case LDC_W, LDC2_W ->
487 processLdc(bcs.getIndexU2());
488 case ILOAD ->
489 currentFrame.checkLocal(bcs.getIndex()).pushStack(Type.INTEGER_TYPE);
490 case ILOAD_0, ILOAD_1, ILOAD_2, ILOAD_3 ->
491 currentFrame.checkLocal(opcode - ILOAD_0).pushStack(Type.INTEGER_TYPE);
492 case LLOAD ->
493 currentFrame.checkLocal(bcs.getIndex() + 1).pushStack(Type.LONG_TYPE, Type.LONG2_TYPE);
494 case LLOAD_0, LLOAD_1, LLOAD_2, LLOAD_3 ->
495 currentFrame.checkLocal(opcode - LLOAD_0 + 1).pushStack(Type.LONG_TYPE, Type.LONG2_TYPE);
496 case FLOAD ->
497 currentFrame.checkLocal(bcs.getIndex()).pushStack(Type.FLOAT_TYPE);
498 case FLOAD_0, FLOAD_1, FLOAD_2, FLOAD_3 ->
499 currentFrame.checkLocal(opcode - FLOAD_0).pushStack(Type.FLOAT_TYPE);
500 case DLOAD ->
501 currentFrame.checkLocal(bcs.getIndex() + 1).pushStack(Type.DOUBLE_TYPE, Type.DOUBLE2_TYPE);
502 case DLOAD_0, DLOAD_1, DLOAD_2, DLOAD_3 ->
503 currentFrame.checkLocal(opcode - DLOAD_0 + 1).pushStack(Type.DOUBLE_TYPE, Type.DOUBLE2_TYPE);
504 case ALOAD ->
505 currentFrame.pushStack(currentFrame.getLocal(bcs.getIndex()));
506 case ALOAD_0, ALOAD_1, ALOAD_2, ALOAD_3 ->
507 currentFrame.pushStack(currentFrame.getLocal(opcode - ALOAD_0));
508 case IALOAD, BALOAD, CALOAD, SALOAD ->
509 currentFrame.decStack(2).pushStack(Type.INTEGER_TYPE);
510 case LALOAD ->
511 currentFrame.decStack(2).pushStack(Type.LONG_TYPE, Type.LONG2_TYPE);
512 case FALOAD ->
513 currentFrame.decStack(2).pushStack(Type.FLOAT_TYPE);
514 case DALOAD ->
515 currentFrame.decStack(2).pushStack(Type.DOUBLE_TYPE, Type.DOUBLE2_TYPE);
516 case AALOAD ->
517 currentFrame.pushStack((type1 = currentFrame.decStack(1).popStack()) == Type.NULL_TYPE ? Type.NULL_TYPE : type1.getComponent());
518 case ISTORE ->
519 currentFrame.decStack(1).setLocal(bcs.getIndex(), Type.INTEGER_TYPE);
520 case ISTORE_0, ISTORE_1, ISTORE_2, ISTORE_3 ->
521 currentFrame.decStack(1).setLocal(opcode - ISTORE_0, Type.INTEGER_TYPE);
522 case LSTORE ->
523 currentFrame.decStack(2).setLocal2(bcs.getIndex(), Type.LONG_TYPE, Type.LONG2_TYPE);
524 case LSTORE_0, LSTORE_1, LSTORE_2, LSTORE_3 ->
525 currentFrame.decStack(2).setLocal2(opcode - LSTORE_0, Type.LONG_TYPE, Type.LONG2_TYPE);
526 case FSTORE ->
527 currentFrame.decStack(1).setLocal(bcs.getIndex(), Type.FLOAT_TYPE);
528 case FSTORE_0, FSTORE_1, FSTORE_2, FSTORE_3 ->
529 currentFrame.decStack(1).setLocal(opcode - FSTORE_0, Type.FLOAT_TYPE);
530 case DSTORE ->
531 currentFrame.decStack(2).setLocal2(bcs.getIndex(), Type.DOUBLE_TYPE, Type.DOUBLE2_TYPE);
532 case DSTORE_0, DSTORE_1, DSTORE_2, DSTORE_3 ->
533 currentFrame.decStack(2).setLocal2(opcode - DSTORE_0, Type.DOUBLE_TYPE, Type.DOUBLE2_TYPE);
534 case ASTORE ->
535 currentFrame.setLocal(bcs.getIndex(), currentFrame.popStack());
536 case ASTORE_0, ASTORE_1, ASTORE_2, ASTORE_3 ->
537 currentFrame.setLocal(opcode - ASTORE_0, currentFrame.popStack());
538 case LASTORE, DASTORE ->
539 currentFrame.decStack(4);
540 case IASTORE, BASTORE, CASTORE, SASTORE, FASTORE, AASTORE ->
541 currentFrame.decStack(3);
542 case POP, MONITORENTER, MONITOREXIT ->
543 currentFrame.decStack(1);
544 case POP2 ->
545 currentFrame.decStack(2);
546 case DUP ->
547 currentFrame.pushStack(type1 = currentFrame.popStack()).pushStack(type1);
548 case DUP_X1 -> {
549 type1 = currentFrame.popStack();
550 type2 = currentFrame.popStack();
551 currentFrame.pushStack(type1).pushStack(type2).pushStack(type1);
552 }
553 case DUP_X2 -> {
554 type1 = currentFrame.popStack();
555 type2 = currentFrame.popStack();
556 type3 = currentFrame.popStack();
557 currentFrame.pushStack(type1).pushStack(type3).pushStack(type2).pushStack(type1);
558 }
559 case DUP2 -> {
560 type1 = currentFrame.popStack();
561 type2 = currentFrame.popStack();
562 currentFrame.pushStack(type2).pushStack(type1).pushStack(type2).pushStack(type1);
563 }
564 case DUP2_X1 -> {
565 type1 = currentFrame.popStack();
566 type2 = currentFrame.popStack();
567 type3 = currentFrame.popStack();
568 currentFrame.pushStack(type2).pushStack(type1).pushStack(type3).pushStack(type2).pushStack(type1);
569 }
570 case DUP2_X2 -> {
571 type1 = currentFrame.popStack();
572 type2 = currentFrame.popStack();
573 type3 = currentFrame.popStack();
574 type4 = currentFrame.popStack();
575 currentFrame.pushStack(type2).pushStack(type1).pushStack(type4).pushStack(type3).pushStack(type2).pushStack(type1);
576 }
577 case SWAP -> {
578 type1 = currentFrame.popStack();
579 type2 = currentFrame.popStack();
580 currentFrame.pushStack(type1);
581 currentFrame.pushStack(type2);
582 }
583 case IADD, ISUB, IMUL, IDIV, IREM, ISHL, ISHR, IUSHR, IOR, IXOR, IAND ->
584 currentFrame.decStack(2).pushStack(Type.INTEGER_TYPE);
585 case INEG, ARRAYLENGTH, INSTANCEOF ->
586 currentFrame.decStack(1).pushStack(Type.INTEGER_TYPE);
587 case LADD, LSUB, LMUL, LDIV, LREM, LAND, LOR, LXOR ->
588 currentFrame.decStack(4).pushStack(Type.LONG_TYPE, Type.LONG2_TYPE);
589 case LNEG ->
590 currentFrame.decStack(2).pushStack(Type.LONG_TYPE, Type.LONG2_TYPE);
591 case LSHL, LSHR, LUSHR ->
592 currentFrame.decStack(3).pushStack(Type.LONG_TYPE, Type.LONG2_TYPE);
593 case FADD, FSUB, FMUL, FDIV, FREM ->
594 currentFrame.decStack(2).pushStack(Type.FLOAT_TYPE);
595 case FNEG ->
596 currentFrame.decStack(1).pushStack(Type.FLOAT_TYPE);
597 case DADD, DSUB, DMUL, DDIV, DREM ->
598 currentFrame.decStack(4).pushStack(Type.DOUBLE_TYPE, Type.DOUBLE2_TYPE);
599 case DNEG ->
600 currentFrame.decStack(2).pushStack(Type.DOUBLE_TYPE, Type.DOUBLE2_TYPE);
601 case IINC ->
602 currentFrame.checkLocal(bcs.getIndex());
603 case I2L ->
604 currentFrame.decStack(1).pushStack(Type.LONG_TYPE, Type.LONG2_TYPE);
605 case L2I ->
606 currentFrame.decStack(2).pushStack(Type.INTEGER_TYPE);
607 case I2F ->
608 currentFrame.decStack(1).pushStack(Type.FLOAT_TYPE);
609 case I2D ->
610 currentFrame.decStack(1).pushStack(Type.DOUBLE_TYPE, Type.DOUBLE2_TYPE);
611 case L2F ->
612 currentFrame.decStack(2).pushStack(Type.FLOAT_TYPE);
613 case L2D ->
614 currentFrame.decStack(2).pushStack(Type.DOUBLE_TYPE, Type.DOUBLE2_TYPE);
615 case F2I ->
616 currentFrame.decStack(1).pushStack(Type.INTEGER_TYPE);
617 case F2L ->
618 currentFrame.decStack(1).pushStack(Type.LONG_TYPE, Type.LONG2_TYPE);
619 case F2D ->
620 currentFrame.decStack(1).pushStack(Type.DOUBLE_TYPE, Type.DOUBLE2_TYPE);
621 case D2L ->
622 currentFrame.decStack(2).pushStack(Type.LONG_TYPE, Type.LONG2_TYPE);
623 case D2F ->
624 currentFrame.decStack(2).pushStack(Type.FLOAT_TYPE);
625 case I2B, I2C, I2S ->
626 currentFrame.decStack(1).pushStack(Type.INTEGER_TYPE);
627 case LCMP, DCMPL, DCMPG ->
628 currentFrame.decStack(4).pushStack(Type.INTEGER_TYPE);
629 case FCMPL, FCMPG, D2I ->
630 currentFrame.decStack(2).pushStack(Type.INTEGER_TYPE);
631 case IF_ICMPEQ, IF_ICMPNE, IF_ICMPLT, IF_ICMPGE, IF_ICMPGT, IF_ICMPLE, IF_ACMPEQ, IF_ACMPNE ->
632 checkJumpTarget(currentFrame.decStack(2), bcs.dest());
633 case IFEQ, IFNE, IFLT, IFGE, IFGT, IFLE, IFNULL, IFNONNULL ->
634 checkJumpTarget(currentFrame.decStack(1), bcs.dest());
635 case GOTO -> {
636 checkJumpTarget(currentFrame, bcs.dest());
637 ncf = true;
638 }
639 case GOTO_W -> {
640 checkJumpTarget(currentFrame, bcs.destW());
641 ncf = true;
642 }
643 case TABLESWITCH, LOOKUPSWITCH -> {
644 processSwitch(bcs);
645 ncf = true;
646 }
647 case LRETURN, DRETURN -> {
648 currentFrame.decStack(2);
649 ncf = true;
650 }
651 case IRETURN, FRETURN, ARETURN, ATHROW -> {
652 currentFrame.decStack(1);
653 ncf = true;
654 }
655 case GETSTATIC, PUTSTATIC, GETFIELD, PUTFIELD ->
656 processFieldInstructions(bcs);
657 case INVOKEVIRTUAL, INVOKESPECIAL, INVOKESTATIC, INVOKEINTERFACE, INVOKEDYNAMIC ->
658 this_uninit = processInvokeInstructions(bcs, (bci >= exMin && bci < exMax), this_uninit);
659 case NEW ->
660 currentFrame.pushStack(Type.uninitializedType(bci));
661 case NEWARRAY ->
662 currentFrame.decStack(1).pushStack(getNewarrayType(bcs.getIndex()));
663 case ANEWARRAY ->
664 processAnewarray(bcs.getIndexU2());
665 case CHECKCAST ->
666 currentFrame.decStack(1).pushStack(cpIndexToType(bcs.getIndexU2(), cp));
667 case MULTIANEWARRAY -> {
668 type1 = cpIndexToType(bcs.getIndexU2(), cp);
669 int dim = bcs.getU1Unchecked(bcs.bci() + 3);
670 for (int i = 0; i < dim; i++) {
671 currentFrame.popStack();
672 }
673 currentFrame.pushStack(type1);
674 }
675 case JSR, JSR_W, RET ->
676 throw generatorError("Instructions jsr, jsr_w, or ret must not appear in the class file version >= 51.0");
677 default ->
678 throw generatorError(String.format("Bad instruction: %02x", opcode));
679 }
680 if (!verified_exc_handlers && bci >= exMin && bci < exMax) {
681 processExceptionHandlerTargets(bci, this_uninit);
682 }
683 return ncf;
684 }
685
686 private void processExceptionHandlerTargets(int bci, boolean this_uninit) {
687 for (var ex : rawHandlers) {
688 if (bci == ex.start || (currentFrame.localsChanged && bci > ex.start && bci < ex.end)) {
689 int flags = currentFrame.flags;
690 if (this_uninit) flags |= FLAG_THIS_UNINIT;
691 Frame newFrame = currentFrame.frameInExceptionHandler(flags, ex.catchType);
692 checkJumpTarget(newFrame, ex.handler);
693 }
694 }
695 currentFrame.localsChanged = false;
696 }
697
698 private void processLdc(int index) {
699 switch (cp.entryByIndex(index).tag()) {
700 case TAG_UTF8 ->
701 currentFrame.pushStack(Type.OBJECT_TYPE);
702 case TAG_STRING ->
703 currentFrame.pushStack(Type.STRING_TYPE);
704 case TAG_CLASS ->
705 currentFrame.pushStack(Type.CLASS_TYPE);
706 case TAG_INTEGER ->
707 currentFrame.pushStack(Type.INTEGER_TYPE);
708 case TAG_FLOAT ->
709 currentFrame.pushStack(Type.FLOAT_TYPE);
710 case TAG_DOUBLE ->
711 currentFrame.pushStack(Type.DOUBLE_TYPE, Type.DOUBLE2_TYPE);
712 case TAG_LONG ->
713 currentFrame.pushStack(Type.LONG_TYPE, Type.LONG2_TYPE);
714 case TAG_METHOD_HANDLE ->
715 currentFrame.pushStack(Type.METHOD_HANDLE_TYPE);
716 case TAG_METHOD_TYPE ->
717 currentFrame.pushStack(Type.METHOD_TYPE);
718 case TAG_DYNAMIC ->
719 currentFrame.pushStack(cp.entryByIndex(index, ConstantDynamicEntry.class).asSymbol().constantType());
720 default ->
721 throw generatorError("CP entry #%d %s is not loadable constant".formatted(index, cp.entryByIndex(index).tag()));
722 }
723 }
724
725 private void processSwitch(RawBytecodeHelper bcs) {
726 int bci = bcs.bci();
727 int alignedBci = RawBytecodeHelper.align(bci + 1);
728 int defaultOffset = bcs.getIntUnchecked(alignedBci);
729 int keys, delta;
730 currentFrame.popStack();
731 if (bcs.opcode() == TABLESWITCH) {
732 int low = bcs.getIntUnchecked(alignedBci + 4);
733 int high = bcs.getIntUnchecked(alignedBci + 2 * 4);
734 if (low > high) {
735 throw generatorError("low must be less than or equal to high in tableswitch");
736 }
737 keys = high - low + 1;
738 if (keys < 0) {
739 throw generatorError("too many keys in tableswitch");
740 }
741 delta = 1;
742 } else {
743 keys = bcs.getIntUnchecked(alignedBci + 4);
744 if (keys < 0) {
745 throw generatorError("number of keys in lookupswitch less than 0");
746 }
747 delta = 2;
748 for (int i = 0; i < (keys - 1); i++) {
749 int this_key = bcs.getIntUnchecked(alignedBci + (2 + 2 * i) * 4);
750 int next_key = bcs.getIntUnchecked(alignedBci + (2 + 2 * i + 2) * 4);
751 if (this_key >= next_key) {
752 throw generatorError("Bad lookupswitch instruction");
753 }
754 }
755 }
756 int target = bci + defaultOffset;
757 checkJumpTarget(currentFrame, target);
758 for (int i = 0; i < keys; i++) {
759 target = bci + bcs.getIntUnchecked(alignedBci + (3 + i * delta) * 4);
760 checkJumpTarget(currentFrame, target);
761 }
762 }
763
764 private void processFieldInstructions(RawBytecodeHelper bcs) {
765 var desc = Util.fieldTypeSymbol(cp.entryByIndex(bcs.getIndexU2(), MemberRefEntry.class).type());
766 var currentFrame = this.currentFrame;
767 switch (bcs.opcode()) {
768 case GETSTATIC ->
769 currentFrame.pushStack(desc);
770 case PUTSTATIC -> {
771 currentFrame.decStack(Util.isDoubleSlot(desc) ? 2 : 1);
772 }
773 case GETFIELD -> {
774 currentFrame.decStack(1);
775 currentFrame.pushStack(desc);
776 }
777 case PUTFIELD -> {
778 currentFrame.decStack(Util.isDoubleSlot(desc) ? 3 : 2);
779 }
780 default -> throw new AssertionError("Should not reach here");
781 }
782 }
783
784 private boolean processInvokeInstructions(RawBytecodeHelper bcs, boolean inTryBlock, boolean thisUninit) {
785 int index = bcs.getIndexU2();
786 int opcode = bcs.opcode();
787 var nameAndType = opcode == INVOKEDYNAMIC
788 ? cp.entryByIndex(index, InvokeDynamicEntry.class).nameAndType()
789 : cp.entryByIndex(index, MemberRefEntry.class).nameAndType();
790 var mDesc = Util.methodTypeSymbol(nameAndType.type());
791 int bci = bcs.bci();
792 var currentFrame = this.currentFrame;
793 currentFrame.decStack(Util.parameterSlots(mDesc));
794 if (opcode != INVOKESTATIC && opcode != INVOKEDYNAMIC) {
795 if (nameAndType.name().equalsString(OBJECT_INITIALIZER_NAME)) {
796 Type type = currentFrame.popStack();
797 if (type == Type.UNITIALIZED_THIS_TYPE) {
798 if (inTryBlock) {
799 processExceptionHandlerTargets(bci, true);
800 }
801 currentFrame.initializeObject(type, thisType);
802 thisUninit = true;
803 } else if (type.tag == ITEM_UNINITIALIZED) {
804 Type new_class_type = cpIndexToType(bcs.getU2(type.bci + 1), cp);
805 if (inTryBlock) {
806 processExceptionHandlerTargets(bci, thisUninit);
807 }
808 currentFrame.initializeObject(type, new_class_type);
809 } else {
810 throw generatorError("Bad operand type when invoking <init>");
811 }
812 } else {
813 currentFrame.decStack(1);
814 }
815 }
816 currentFrame.pushStack(mDesc.returnType());
817 return thisUninit;
818 }
819
820 private Type getNewarrayType(int index) {
821 if (index < T_BOOLEAN || index > T_LONG) throw generatorError("Illegal newarray instruction type %d".formatted(index));
822 return ARRAY_FROM_BASIC_TYPE[index];
823 }
824
825 private void processAnewarray(int index) {
826 currentFrame.popStack();
827 currentFrame.pushStack(cpIndexToType(index, cp).toArray());
828 }
829
830 /**
831 * {@return the generator error with attached details}
832 * @param msg error message
833 */
834 private IllegalArgumentException generatorError(String msg) {
835 return generatorError(msg, currentFrame.offset);
836 }
837
838 /**
839 * {@return the generator error with attached details}
840 * @param msg error message
841 * @param offset bytecode offset where the error occurred
842 */
843 private IllegalArgumentException generatorError(String msg, int offset) {
844 var sb = new StringBuilder("%s at bytecode offset %d of method %s(%s)".formatted(
845 msg,
846 offset,
847 methodName,
848 methodDesc.parameterList().stream().map(ClassDesc::displayName).collect(Collectors.joining(","))));
849 Util.dumpMethod(cp, thisType.sym(), methodName, methodDesc, isStatic ? ACC_STATIC : 0, bytecode, sb::append);
850 return new IllegalArgumentException(sb.toString());
851 }
852
853 /**
854 * Performs detection of mandatory stack map frames in a single bytecode traversing pass
855 * @return detected frames
856 */
857 private void detectFrames() {
858 var bcs = bytecode.start();
859 boolean no_control_flow = false;
860 int opcode, bci = 0;
861 while (bcs.next()) try {
862 opcode = bcs.opcode();
863 bci = bcs.bci();
864 if (no_control_flow) {
865 addFrame(bci);
866 }
867 no_control_flow = switch (opcode) {
868 case GOTO -> {
869 addFrame(bcs.dest());
870 yield true;
871 }
872 case GOTO_W -> {
873 addFrame(bcs.destW());
874 yield true;
875 }
876 case IF_ICMPEQ, IF_ICMPNE, IF_ICMPLT, IF_ICMPGE,
877 IF_ICMPGT, IF_ICMPLE, IFEQ, IFNE,
878 IFLT, IFGE, IFGT, IFLE, IF_ACMPEQ,
879 IF_ACMPNE , IFNULL , IFNONNULL -> {
880 addFrame(bcs.dest());
881 yield false;
882 }
883 case TABLESWITCH, LOOKUPSWITCH -> {
884 int aligned_bci = RawBytecodeHelper.align(bci + 1);
885 int default_ofset = bcs.getIntUnchecked(aligned_bci);
886 int keys, delta;
887 if (bcs.opcode() == TABLESWITCH) {
888 int low = bcs.getIntUnchecked(aligned_bci + 4);
889 int high = bcs.getIntUnchecked(aligned_bci + 2 * 4);
890 keys = high - low + 1;
891 delta = 1;
892 } else {
893 keys = bcs.getIntUnchecked(aligned_bci + 4);
894 delta = 2;
895 }
896 addFrame(bci + default_ofset);
897 for (int i = 0; i < keys; i++) {
898 addFrame(bci + bcs.getIntUnchecked(aligned_bci + (3 + i * delta) * 4));
899 }
900 yield true;
901 }
902 case IRETURN, LRETURN, FRETURN, DRETURN,
903 ARETURN, RETURN, ATHROW -> true;
904 default -> false;
905 };
906 } catch (IllegalArgumentException iae) {
907 throw generatorError("Detected branch target out of bytecode range", bci);
908 }
909 for (int i = 0; i < rawHandlers.size(); i++) try {
910 addFrame(rawHandlers.get(i).handler());
911 } catch (IllegalArgumentException iae) {
912 if (!filterDeadLabels)
913 throw generatorError("Detected exception handler out of bytecode range");
914 }
915 }
916
917 private void addFrame(int offset) {
918 Preconditions.checkIndex(offset, bytecode.length(), RawBytecodeHelper.IAE_FORMATTER);
919 var frames = this.frames;
920 int i = 0, framesCount = this.framesCount;
921 for (; i < framesCount; i++) {
922 var frameOffset = frames[i].offset;
923 if (frameOffset == offset) {
924 return;
925 }
926 if (frameOffset > offset) {
927 break;
928 }
929 }
930 if (framesCount >= frames.length) {
931 int newCapacity = framesCount + 8;
932 this.frames = frames = framesCount == 0 ? new Frame[newCapacity] : Arrays.copyOf(frames, newCapacity);
933 }
934 if (i != framesCount) {
935 System.arraycopy(frames, i, frames, i + 1, framesCount - i);
936 }
937 frames[i] = new Frame(offset, classHierarchy);
938 this.framesCount = framesCount + 1;
939 }
940
941 private final class Frame {
942
943 int offset;
944 int localsSize, stackSize;
945 int flags;
946 int frameMaxStack = 0, frameMaxLocals = 0;
947 boolean dirty = false;
948 boolean localsChanged = false;
949
950 private final ClassHierarchyImpl classHierarchy;
951
952 private Type[] locals, stack;
953
954 Frame(ClassHierarchyImpl classHierarchy) {
955 this(-1, 0, 0, 0, null, null, classHierarchy);
956 }
957
958 Frame(int offset, ClassHierarchyImpl classHierarchy) {
959 this(offset, -1, 0, 0, null, null, classHierarchy);
960 }
961
962 Frame(int offset, int flags, int locals_size, int stack_size, Type[] locals, Type[] stack, ClassHierarchyImpl classHierarchy) {
963 this.offset = offset;
964 this.localsSize = locals_size;
965 this.stackSize = stack_size;
966 this.flags = flags;
967 this.locals = locals;
968 this.stack = stack;
969 this.classHierarchy = classHierarchy;
970 }
971
972 @Override
973 public String toString() {
974 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));
975 }
976
977 Frame pushStack(ClassDesc desc) {
978 if (desc == CD_long) return pushStack(Type.LONG_TYPE, Type.LONG2_TYPE);
979 if (desc == CD_double) return pushStack(Type.DOUBLE_TYPE, Type.DOUBLE2_TYPE);
980 return desc == CD_void ? this
981 : pushStack(
982 desc.isPrimitive()
983 ? (desc == CD_float ? Type.FLOAT_TYPE : Type.INTEGER_TYPE)
984 : Type.referenceType(desc));
985 }
986
987 Frame pushStack(Type type) {
988 checkStack(stackSize);
989 stack[stackSize++] = type;
990 return this;
991 }
992
993 Frame pushStack(Type type1, Type type2) {
994 checkStack(stackSize + 1);
995 stack[stackSize++] = type1;
996 stack[stackSize++] = type2;
997 return this;
998 }
999
1000 Type popStack() {
1001 if (stackSize < 1) throw generatorError("Operand stack underflow");
1002 return stack[--stackSize];
1003 }
1004
1005 Frame decStack(int size) {
1006 stackSize -= size;
1007 if (stackSize < 0) throw generatorError("Operand stack underflow");
1008 return this;
1009 }
1010
1011 Frame frameInExceptionHandler(int flags, Type excType) {
1012 return new Frame(offset, flags, localsSize, 1, locals, new Type[] {excType}, classHierarchy);
1013 }
1014
1015 void initializeObject(Type old_object, Type new_object) {
1016 int i;
1017 for (i = 0; i < localsSize; i++) {
1018 if (locals[i].equals(old_object)) {
1019 locals[i] = new_object;
1020 localsChanged = true;
1021 }
1022 }
1023 for (i = 0; i < stackSize; i++) {
1024 if (stack[i].equals(old_object)) {
1025 stack[i] = new_object;
1026 }
1027 }
1028 if (old_object == Type.UNITIALIZED_THIS_TYPE) {
1029 flags = 0;
1030 }
1031 }
1032
1033 Frame checkLocal(int index) {
1034 if (index >= frameMaxLocals) frameMaxLocals = index + 1;
1035 if (locals == null) {
1036 locals = new Type[index + FRAME_DEFAULT_CAPACITY];
1037 Arrays.fill(locals, Type.TOP_TYPE);
1038 } else if (index >= locals.length) {
1039 int current = locals.length;
1040 locals = Arrays.copyOf(locals, index + FRAME_DEFAULT_CAPACITY);
1041 Arrays.fill(locals, current, locals.length, Type.TOP_TYPE);
1042 }
1043 return this;
1044 }
1045
1046 private void checkStack(int index) {
1047 if (index >= frameMaxStack) frameMaxStack = index + 1;
1048 if (stack == null) {
1049 stack = new Type[index + FRAME_DEFAULT_CAPACITY];
1050 Arrays.fill(stack, Type.TOP_TYPE);
1051 } else if (index >= stack.length) {
1052 int current = stack.length;
1053 stack = Arrays.copyOf(stack, index + FRAME_DEFAULT_CAPACITY);
1054 Arrays.fill(stack, current, stack.length, Type.TOP_TYPE);
1055 }
1056 }
1057
1058 private void setLocalRawInternal(int index, Type type) {
1059 checkLocal(index);
1060 localsChanged |= !type.equals(locals[index]);
1061 locals[index] = type;
1062 }
1063
1064 void setLocalsFromArg(String name, MethodTypeDesc methodDesc, boolean isStatic, Type thisKlass) {
1065 int localsSize = 0;
1066 // Pre-emptively create a locals array that encompass all parameter slots
1067 checkLocal(Util.parameterSlots(methodDesc) + (isStatic ? -1 : 0));
1068 Type type;
1069 Type[] locals = this.locals;
1070 if (!isStatic) {
1071 if (OBJECT_INITIALIZER_NAME.equals(name) && !CD_Object.equals(thisKlass.sym)) {
1072 type = Type.UNITIALIZED_THIS_TYPE;
1073 flags |= FLAG_THIS_UNINIT;
1074 } else {
1075 type = thisKlass;
1076 }
1077 locals[localsSize++] = type;
1078 }
1079 for (int i = 0; i < methodDesc.parameterCount(); i++) {
1080 var desc = methodDesc.parameterType(i);
1081 if (desc == CD_long) {
1082 locals[localsSize ] = Type.LONG_TYPE;
1083 locals[localsSize + 1] = Type.LONG2_TYPE;
1084 localsSize += 2;
1085 } else if (desc == CD_double) {
1086 locals[localsSize ] = Type.DOUBLE_TYPE;
1087 locals[localsSize + 1] = Type.DOUBLE2_TYPE;
1088 localsSize += 2;
1089 } else {
1090 if (!desc.isPrimitive()) {
1091 type = Type.referenceType(desc);
1092 } else if (desc == CD_float) {
1093 type = Type.FLOAT_TYPE;
1094 } else {
1095 type = Type.INTEGER_TYPE;
1096 }
1097 locals[localsSize++] = type;
1098 }
1099 }
1100 this.localsSize = localsSize;
1101 }
1102
1103 void copyFrom(Frame src) {
1104 if (locals != null && src.localsSize < locals.length) Arrays.fill(locals, src.localsSize, locals.length, Type.TOP_TYPE);
1105 localsSize = src.localsSize;
1106 checkLocal(src.localsSize - 1);
1107 if (src.localsSize > 0) System.arraycopy(src.locals, 0, locals, 0, src.localsSize);
1108 if (stack != null && src.stackSize < stack.length) Arrays.fill(stack, src.stackSize, stack.length, Type.TOP_TYPE);
1109 stackSize = src.stackSize;
1110 checkStack(src.stackSize - 1);
1111 if (src.stackSize > 0) System.arraycopy(src.stack, 0, stack, 0, src.stackSize);
1112 flags = src.flags;
1113 localsChanged = true;
1114 }
1115
1116 void checkAssignableTo(Frame target) {
1117 int localsSize = this.localsSize;
1118 int stackSize = this.stackSize;
1119 if (target.flags == -1) {
1120 target.locals = locals == null ? null : locals.clone();
1121 target.localsSize = localsSize;
1122 if (stackSize > 0) {
1123 target.stack = stack.clone();
1124 target.stackSize = stackSize;
1125 }
1126 target.flags = flags;
1127 target.dirty = true;
1128 } else {
1129 if (target.localsSize > localsSize) {
1130 target.localsSize = localsSize;
1131 target.dirty = true;
1132 }
1133 for (int i = 0; i < target.localsSize; i++) {
1134 merge(locals[i], target.locals, i, target);
1135 }
1136 if (stackSize != target.stackSize) {
1137 throw generatorError("Stack size mismatch");
1138 }
1139 for (int i = 0; i < target.stackSize; i++) {
1140 if (merge(stack[i], target.stack, i, target) == Type.TOP_TYPE) {
1141 throw generatorError("Stack content mismatch");
1142 }
1143 }
1144 }
1145 }
1146
1147 private Type getLocalRawInternal(int index) {
1148 checkLocal(index);
1149 return locals[index];
1150 }
1151
1152 Type getLocal(int index) {
1153 Type ret = getLocalRawInternal(index);
1154 if (index >= localsSize) {
1155 localsSize = index + 1;
1156 }
1157 return ret;
1158 }
1159
1160 void setLocal(int index, Type type) {
1161 Type old = getLocalRawInternal(index);
1162 if (old == Type.DOUBLE_TYPE || old == Type.LONG_TYPE) {
1163 setLocalRawInternal(index + 1, Type.TOP_TYPE);
1164 }
1165 if (old == Type.DOUBLE2_TYPE || old == Type.LONG2_TYPE) {
1166 setLocalRawInternal(index - 1, Type.TOP_TYPE);
1167 }
1168 setLocalRawInternal(index, type);
1169 if (index >= localsSize) {
1170 localsSize = index + 1;
1171 }
1172 }
1173
1174 void setLocal2(int index, Type type1, Type type2) {
1175 Type old = getLocalRawInternal(index + 1);
1176 if (old == Type.DOUBLE_TYPE || old == Type.LONG_TYPE) {
1177 setLocalRawInternal(index + 2, Type.TOP_TYPE);
1178 }
1179 old = getLocalRawInternal(index);
1180 if (old == Type.DOUBLE2_TYPE || old == Type.LONG2_TYPE) {
1181 setLocalRawInternal(index - 1, Type.TOP_TYPE);
1182 }
1183 setLocalRawInternal(index, type1);
1184 setLocalRawInternal(index + 1, type2);
1185 if (index >= localsSize - 1) {
1186 localsSize = index + 2;
1187 }
1188 }
1189
1190 private Type merge(Type me, Type[] toTypes, int i, Frame target) {
1191 var to = toTypes[i];
1192 var newTo = to.mergeFrom(me, classHierarchy);
1193 if (to != newTo && !to.equals(newTo)) {
1194 toTypes[i] = newTo;
1195 target.dirty = true;
1196 }
1197 return newTo;
1198 }
1199
1200 private static int trimAndCompress(Type[] types, int count) {
1201 while (count > 0 && types[count - 1] == Type.TOP_TYPE) count--;
1202 int compressed = 0;
1203 for (int i = 0; i < count; i++) {
1204 if (!types[i].isCategory2_2nd()) {
1205 if (compressed != i) {
1206 types[compressed] = types[i];
1207 }
1208 compressed++;
1209 }
1210 }
1211 return compressed;
1212 }
1213
1214 void trimAndCompress() {
1215 localsSize = trimAndCompress(locals, localsSize);
1216 stackSize = trimAndCompress(stack, stackSize);
1217 }
1218
1219 private static boolean equals(Type[] l1, Type[] l2, int commonSize) {
1220 if (l1 == null || l2 == null) return commonSize == 0;
1221 return Arrays.equals(l1, 0, commonSize, l2, 0, commonSize);
1222 }
1223
1224 void writeTo(BufWriterImpl out, Frame prevFrame, ConstantPoolBuilder cp) {
1225 int localsSize = this.localsSize;
1226 int stackSize = this.stackSize;
1227 int offsetDelta = offset - prevFrame.offset - 1;
1228 if (stackSize == 0) {
1229 int commonLocalsSize = localsSize > prevFrame.localsSize ? prevFrame.localsSize : localsSize;
1230 int diffLocalsSize = localsSize - prevFrame.localsSize;
1231 if (-3 <= diffLocalsSize && diffLocalsSize <= 3 && equals(locals, prevFrame.locals, commonLocalsSize)) {
1232 if (diffLocalsSize == 0 && offsetDelta < 64) { //same frame
1233 out.writeU1(offsetDelta);
1234 } else { //chop, same extended or append frame
1235 out.writeU1U2(251 + diffLocalsSize, offsetDelta);
1236 for (int i=commonLocalsSize; i<localsSize; i++) locals[i].writeTo(out, cp);
1237 }
1238 return;
1239 }
1240 } else if (stackSize == 1 && localsSize == prevFrame.localsSize && equals(locals, prevFrame.locals, localsSize)) {
1241 if (offsetDelta < 64) { //same locals 1 stack item frame
1242 out.writeU1(64 + offsetDelta);
1243 } else { //same locals 1 stack item extended frame
1244 out.writeU1U2(247, offsetDelta);
1245 }
1246 stack[0].writeTo(out, cp);
1247 return;
1248 }
1249 //full frame
1250 out.writeU1U2U2(255, offsetDelta, localsSize);
1251 for (int i=0; i<localsSize; i++) locals[i].writeTo(out, cp);
1252 out.writeU2(stackSize);
1253 for (int i=0; i<stackSize; i++) stack[i].writeTo(out, cp);
1254 }
1255 }
1256
1257 private static record Type(int tag, ClassDesc sym, int bci) {
1258
1259 //singleton types
1260 static final Type TOP_TYPE = simpleType(ITEM_TOP),
1261 NULL_TYPE = simpleType(ITEM_NULL),
1262 INTEGER_TYPE = simpleType(ITEM_INTEGER),
1263 FLOAT_TYPE = simpleType(ITEM_FLOAT),
1264 LONG_TYPE = simpleType(ITEM_LONG),
1265 LONG2_TYPE = simpleType(ITEM_LONG_2ND),
1266 DOUBLE_TYPE = simpleType(ITEM_DOUBLE),
1267 BOOLEAN_TYPE = simpleType(ITEM_BOOLEAN),
1268 BYTE_TYPE = simpleType(ITEM_BYTE),
1269 CHAR_TYPE = simpleType(ITEM_CHAR),
1270 SHORT_TYPE = simpleType(ITEM_SHORT),
1271 DOUBLE2_TYPE = simpleType(ITEM_DOUBLE_2ND),
1272 UNITIALIZED_THIS_TYPE = simpleType(ITEM_UNINITIALIZED_THIS);
1273
1274 //frequently used types to reduce footprint
1275 static final Type OBJECT_TYPE = referenceType(CD_Object),
1276 THROWABLE_TYPE = referenceType(CD_Throwable),
1277 INT_ARRAY_TYPE = referenceType(CD_int.arrayType()),
1278 BOOLEAN_ARRAY_TYPE = referenceType(CD_boolean.arrayType()),
1279 BYTE_ARRAY_TYPE = referenceType(CD_byte.arrayType()),
1280 CHAR_ARRAY_TYPE = referenceType(CD_char.arrayType()),
1281 SHORT_ARRAY_TYPE = referenceType(CD_short.arrayType()),
1282 LONG_ARRAY_TYPE = referenceType(CD_long.arrayType()),
1283 DOUBLE_ARRAY_TYPE = referenceType(CD_double.arrayType()),
1284 FLOAT_ARRAY_TYPE = referenceType(CD_float.arrayType()),
1285 STRING_TYPE = referenceType(CD_String),
1286 CLASS_TYPE = referenceType(CD_Class),
1287 METHOD_HANDLE_TYPE = referenceType(CD_MethodHandle),
1288 METHOD_TYPE = referenceType(CD_MethodType);
1289
1290 private static Type simpleType(int tag) {
1291 return new Type(tag, null, 0);
1292 }
1293
1294 static Type referenceType(ClassDesc desc) {
1295 return new Type(ITEM_OBJECT, desc, 0);
1296 }
1297
1298 static Type uninitializedType(int bci) {
1299 return new Type(ITEM_UNINITIALIZED, null, bci);
1300 }
1301
1302 @Override //mandatory override to avoid use of method reference during JDK bootstrap
1303 public boolean equals(Object o) {
1304 return (o instanceof Type t) && t.tag == tag && t.bci == bci && Objects.equals(sym, t.sym);
1305 }
1306
1307 boolean isCategory2_2nd() {
1308 return this == DOUBLE2_TYPE || this == LONG2_TYPE;
1309 }
1310
1311 boolean isReference() {
1312 return tag == ITEM_OBJECT || this == NULL_TYPE;
1313 }
1314
1315 boolean isObject() {
1316 return tag == ITEM_OBJECT && sym.isClassOrInterface();
1317 }
1318
1319 boolean isArray() {
1320 return tag == ITEM_OBJECT && sym.isArray();
1321 }
1322
1323 Type mergeFrom(Type from, ClassHierarchyImpl context) {
1324 if (this == TOP_TYPE || this == from || equals(from)) {
1325 return this;
1326 } else {
1327 return switch (tag) {
1328 case ITEM_BOOLEAN, ITEM_BYTE, ITEM_CHAR, ITEM_SHORT ->
1329 from == INTEGER_TYPE ? this : TOP_TYPE;
1330 default ->
1331 isReference() && from.isReference() ? mergeReferenceFrom(from, context) : TOP_TYPE;
1332 };
1333 }
1334 }
1335
1336 Type mergeComponentFrom(Type from, ClassHierarchyImpl context) {
1337 if (this == TOP_TYPE || this == from || equals(from)) {
1338 return this;
1339 } else {
1340 return switch (tag) {
1341 case ITEM_BOOLEAN, ITEM_BYTE, ITEM_CHAR, ITEM_SHORT ->
1342 TOP_TYPE;
1343 default ->
1344 isReference() && from.isReference() ? mergeReferenceFrom(from, context) : TOP_TYPE;
1345 };
1346 }
1347 }
1348
1349 private static final ClassDesc CD_Cloneable = ClassOrInterfaceDescImpl.ofValidated("Ljava/lang/Cloneable;");
1350 private static final ClassDesc CD_Serializable = ClassOrInterfaceDescImpl.ofValidated("Ljava/io/Serializable;");
1351
1352 private Type mergeReferenceFrom(Type from, ClassHierarchyImpl context) {
1353 if (from == NULL_TYPE) {
1354 return this;
1355 } else if (this == NULL_TYPE) {
1356 return from;
1357 } else if (sym.equals(from.sym)) {
1358 return this;
1359 } else if (isObject()) {
1360 if (CD_Object.equals(sym)) {
1361 return this;
1362 }
1363 if (context.isInterface(sym)) {
1364 if (!from.isArray() || CD_Cloneable.equals(sym) || CD_Serializable.equals(sym)) {
1365 return this;
1366 }
1367 } else if (from.isObject()) {
1368 var anc = context.commonAncestor(sym, from.sym);
1369 return anc == null ? this : Type.referenceType(anc);
1370 }
1371 } else if (isArray() && from.isArray()) {
1372 Type compThis = getComponent();
1373 Type compFrom = from.getComponent();
1374 if (compThis != TOP_TYPE && compFrom != TOP_TYPE) {
1375 return compThis.mergeComponentFrom(compFrom, context).toArray();
1376 }
1377 }
1378 return OBJECT_TYPE;
1379 }
1380
1381 Type toArray() {
1382 return switch (tag) {
1383 case ITEM_BOOLEAN -> BOOLEAN_ARRAY_TYPE;
1384 case ITEM_BYTE -> BYTE_ARRAY_TYPE;
1385 case ITEM_CHAR -> CHAR_ARRAY_TYPE;
1386 case ITEM_SHORT -> SHORT_ARRAY_TYPE;
1387 case ITEM_INTEGER -> INT_ARRAY_TYPE;
1388 case ITEM_LONG -> LONG_ARRAY_TYPE;
1389 case ITEM_FLOAT -> FLOAT_ARRAY_TYPE;
1390 case ITEM_DOUBLE -> DOUBLE_ARRAY_TYPE;
1391 case ITEM_OBJECT -> Type.referenceType(sym.arrayType());
1392 default -> OBJECT_TYPE;
1393 };
1394 }
1395
1396 Type getComponent() {
1397 if (isArray()) {
1398 var comp = sym.componentType();
1399 if (comp.isPrimitive()) {
1400 return switch (comp.descriptorString().charAt(0)) {
1401 case 'Z' -> Type.BOOLEAN_TYPE;
1402 case 'B' -> Type.BYTE_TYPE;
1403 case 'C' -> Type.CHAR_TYPE;
1404 case 'S' -> Type.SHORT_TYPE;
1405 case 'I' -> Type.INTEGER_TYPE;
1406 case 'J' -> Type.LONG_TYPE;
1407 case 'F' -> Type.FLOAT_TYPE;
1408 case 'D' -> Type.DOUBLE_TYPE;
1409 default -> Type.TOP_TYPE;
1410 };
1411 }
1412 return Type.referenceType(comp);
1413 }
1414 return Type.TOP_TYPE;
1415 }
1416
1417 void writeTo(BufWriterImpl bw, ConstantPoolBuilder cp) {
1418 switch (tag) {
1419 case ITEM_OBJECT ->
1420 bw.writeU1U2(tag, cp.classEntry(sym).index());
1421 case ITEM_UNINITIALIZED ->
1422 bw.writeU1U2(tag, bci);
1423 default ->
1424 bw.writeU1(tag);
1425 }
1426 }
1427 }
1428 }