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 }