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 }