1 /* 2 * Copyright (c) 2024, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 package java.lang.reflect.code.bytecode; 26 27 import java.lang.classfile.CodeElement; 28 import java.lang.classfile.Instruction; 29 import java.lang.classfile.Label; 30 import java.lang.classfile.Opcode; 31 import java.lang.classfile.TypeKind; 32 import java.lang.classfile.attribute.StackMapFrameInfo; 33 import java.lang.classfile.attribute.StackMapFrameInfo.*; 34 import java.lang.classfile.attribute.StackMapTableAttribute; 35 import java.lang.classfile.instruction.*; 36 import java.lang.constant.ClassDesc; 37 import java.lang.constant.ConstantDescs; 38 import java.lang.constant.DirectMethodHandleDesc; 39 import java.lang.constant.DynamicConstantDesc; 40 import java.lang.constant.MethodTypeDesc; 41 42 import java.util.ArrayList; 43 import java.util.HashMap; 44 import java.util.List; 45 import java.util.Map; 46 import java.util.Optional; 47 import java.util.stream.Collectors; 48 49 import static java.lang.classfile.attribute.StackMapFrameInfo.SimpleVerificationTypeInfo.*; 50 import static java.lang.constant.ConstantDescs.*; 51 import java.lang.reflect.code.Value; 52 import java.lang.reflect.code.type.JavaType; 53 import java.util.ArrayDeque; 54 import java.util.HashSet; 55 import java.util.LinkedHashSet; 56 import java.util.Set; 57 58 final class LocalsTypeMapper { 59 60 static class Variable { 61 private ClassDesc type; 62 boolean isSingleValue; 63 Value value; 64 65 JavaType type() { 66 return JavaType.type(type); 67 } 68 69 Object defaultValue() { 70 return switch (TypeKind.from(type)) { 71 case BooleanType -> false; 72 case ByteType -> (byte)0; 73 case CharType -> (char)0; 74 case DoubleType -> 0d; 75 case FloatType -> 0f; 76 case IntType -> 0; 77 case LongType -> 0l; 78 case ReferenceType -> null; 79 case ShortType -> (short)0; 80 default -> throw new IllegalStateException("Invalid type " + type.displayName()); 81 }; 82 } 83 } 84 85 static class Slot { 86 87 record Link(Slot slot, Link other) {} 88 89 ClassDesc type; 90 Link up, down; 91 Variable var; 92 boolean newValue; 93 Slot previous; // Previous Slot, not necessary of the same variable 94 95 void link(Slot target) { 96 if (this != target) { 97 target.up = new Link(this, target.up); 98 this.down = new Link(target, this.down); 99 } 100 } 101 } 102 103 record Frame(List<ClassDesc> stack, List<Slot> locals) {} 104 105 private static final ClassDesc NULL_TYPE = ClassDesc.ofDescriptor(CD_Object.descriptorString()); 106 private final Map<Integer, Slot> insMap; 107 private final LinkedHashSet<Slot> allSlots; 108 private final ClassDesc thisClass; 109 private final List<ExceptionCatch> exceptionHandlers; 110 private final List<ClassDesc> stack; 111 private final List<Slot> locals; 112 private final Map<Label, Frame> stackMap; 113 private final Map<Label, ClassDesc> newMap; 114 private boolean frameDirty; 115 final List<Slot> slotsToInitialize; 116 117 LocalsTypeMapper(ClassDesc thisClass, 118 List<ClassDesc> initFrameLocals, 119 List<ExceptionCatch> exceptionHandlers, 120 Optional<StackMapTableAttribute> stackMapTableAttribute, 121 List<CodeElement> codeElements) { 122 this.insMap = new HashMap<>(); 123 this.thisClass = thisClass; 124 this.exceptionHandlers = exceptionHandlers; 125 this.stack = new ArrayList<>(); 126 this.locals = new ArrayList<>(); 127 this.allSlots = new LinkedHashSet<>(); 128 this.newMap = computeNewMap(codeElements); 129 this.slotsToInitialize = new ArrayList<>(); 130 this.stackMap = stackMapTableAttribute.map(a -> a.entries().stream().collect(Collectors.toMap( 131 StackMapFrameInfo::target, 132 this::toFrame))).orElse(Map.of()); 133 for (ClassDesc cd : initFrameLocals) { 134 slotsToInitialize.add(cd == null ? null : newSlot(cd, true)); 135 } 136 int initSize = allSlots.size(); 137 do { 138 // Slot states reset if running additional rounds with adjusted frames 139 if (allSlots.size() > initSize) { 140 while (allSlots.size() > initSize) allSlots.removeLast(); 141 allSlots.forEach(sl -> { 142 sl.up = null; 143 sl.down = null; 144 sl.previous = null; 145 sl.var = null; 146 }); 147 } 148 for (int i = 0; i < initFrameLocals.size(); i++) { 149 store(i, slotsToInitialize.get(i), locals); 150 } 151 this.frameDirty = false; 152 for (int i = 0; i < codeElements.size(); i++) { 153 accept(i, codeElements.get(i)); 154 } 155 endOfFlow(); 156 } while (this.frameDirty); 157 158 // Assign variable to slots, calculate var type, detect single value variables and dominant slot 159 ArrayDeque<Slot> q = new ArrayDeque<>(); 160 Set<Slot> initialSlots = new HashSet<>(); 161 for (Slot slot : allSlots) { 162 if (slot.var == null) { 163 Variable var = new Variable(); 164 q.add(slot); 165 int sources = 0; 166 var.type = slot.type; 167 while (!q.isEmpty()) { 168 Slot sl = q.pop(); 169 if (sl.var == null) { 170 if (sl.newValue) { 171 sources++; 172 if (sl.up == null) { 173 initialSlots.add(sl); 174 } 175 } 176 sl.var = var; 177 Slot.Link l = sl.up; 178 while (l != null) { 179 if (var.type == NULL_TYPE) var.type = l.slot.type; 180 if (l.slot.var == null) q.add(l.slot); 181 l = l.other; 182 } 183 l = sl.down; 184 while (l != null) { 185 if (var.type == NULL_TYPE) var.type = l.slot.type; 186 if (l.slot.var == null) q.add(l.slot); 187 l = l.other; 188 } 189 } 190 } 191 var.isSingleValue = sources < 2; 192 193 // Filter out slots, which are not initial (store into the same variable) 194 for (var tsit = initialSlots.iterator(); tsit.hasNext();) { 195 Slot sl = tsit.next(); 196 if (sl.previous != null && sl.previous.var == sl.var) { 197 tsit.remove(); 198 } 199 } 200 if (initialSlots.size() > 1) { 201 // Add synthetic dominant slot, which needs to be initialized with a default value 202 Slot initialSlot = new Slot(); 203 initialSlot.var = var; 204 slotsToInitialize.add(initialSlot); 205 if (var.type == CD_long || var.type == CD_double) { 206 slotsToInitialize.add(null); 207 } 208 } 209 initialSlots.clear(); 210 } 211 } 212 } 213 214 private Frame toFrame(StackMapFrameInfo smfi) { 215 List<ClassDesc> fstack = new ArrayList<>(smfi.stack().size()); 216 List<Slot> flocals = new ArrayList<>(smfi.locals().size() * 2); 217 for (var vti : smfi.stack()) { 218 fstack.add(vtiToStackType(vti)); 219 } 220 int i = 0; 221 for (var vti : smfi.locals()) { 222 store(i, vtiToStackType(vti), flocals, false); 223 i += vti == ITEM_DOUBLE || vti == ITEM_LONG ? 2 : 1; 224 } 225 return new Frame(fstack, flocals); 226 } 227 228 private static Map<Label, ClassDesc> computeNewMap(List<CodeElement> codeElements) { 229 Map<Label, ClassDesc> newMap = new HashMap<>(); 230 Label lastLabel = null; 231 for (int i = 0; i < codeElements.size(); i++) { 232 switch (codeElements.get(i)) { 233 case LabelTarget lt -> lastLabel = lt.label(); 234 case NewObjectInstruction newI -> { 235 if (lastLabel != null) { 236 newMap.put(lastLabel, newI.className().asSymbol()); 237 } 238 } 239 case Instruction _ -> lastLabel = null; //invalidate label 240 default -> {} //skip 241 } 242 } 243 return newMap; 244 } 245 246 Variable getVarOf(int li) { 247 return insMap.get(li).var; 248 } 249 250 private Slot newSlot(ClassDesc type, boolean newValue) { 251 Slot s = new Slot(); 252 s.type = type; 253 s.newValue = newValue; 254 allSlots.add(s); 255 return s; 256 } 257 258 private ClassDesc vtiToStackType(StackMapFrameInfo.VerificationTypeInfo vti) { 259 return switch (vti) { 260 case ITEM_INTEGER -> CD_int; 261 case ITEM_FLOAT -> CD_float; 262 case ITEM_DOUBLE -> CD_double; 263 case ITEM_LONG -> CD_long; 264 case ITEM_UNINITIALIZED_THIS -> thisClass; 265 case ITEM_NULL -> NULL_TYPE; 266 case ObjectVerificationTypeInfo ovti -> ovti.classSymbol(); 267 case UninitializedVerificationTypeInfo uvti -> 268 newMap.computeIfAbsent(uvti.newTarget(), l -> { 269 throw new IllegalArgumentException("Unitialized type does not point to a new instruction"); 270 }); 271 case ITEM_TOP -> null; 272 }; 273 } 274 275 private void push(ClassDesc type) { 276 if (!ConstantDescs.CD_void.equals(type)) stack.add(type); 277 } 278 279 private void pushAt(int pos, ClassDesc... types) { 280 for (var t : types) 281 if (!ConstantDescs.CD_void.equals(t)) 282 stack.add(stack.size() + pos, t); 283 } 284 285 private boolean doubleAt(int pos) { 286 var t = stack.get(stack.size() + pos); 287 return t.equals(CD_long) || t.equals(CD_double); 288 } 289 290 private ClassDesc pop() { 291 return stack.removeLast(); 292 } 293 294 private ClassDesc get(int pos) { 295 return stack.get(stack.size() + pos); 296 } 297 298 private ClassDesc top() { 299 return stack.getLast(); 300 } 301 302 private ClassDesc[] top2() { 303 return new ClassDesc[] {stack.get(stack.size() - 2), stack.getLast()}; 304 } 305 306 private LocalsTypeMapper pop(int i) { 307 while (i-- > 0) pop(); 308 return this; 309 } 310 311 private void store(int slot, ClassDesc type) { 312 store(slot, type, locals, true); 313 } 314 315 private void store(int slot, ClassDesc type, List<Slot> where, boolean newValue) { 316 store(slot, type == null ? null : newSlot(type, newValue), where); 317 } 318 319 private void store(int slot, Slot s, List<Slot> where) { 320 if (s != null) { 321 for (int i = where.size(); i <= slot; i++) where.add(null); 322 s.previous = where.set(slot, s); 323 } 324 } 325 326 private ClassDesc load(int slot) { 327 return locals.get(slot).type; 328 } 329 330 private void accept(int elIndex, CodeElement el) { 331 switch (el) { 332 case ArrayLoadInstruction _ -> 333 pop(1).push(pop().componentType()); 334 case ArrayStoreInstruction _ -> 335 pop(3); 336 case BranchInstruction i -> { 337 switch (i.opcode()) { 338 case IFEQ, IFGE, IFGT, IFLE, IFLT, IFNE, IFNONNULL, IFNULL -> { 339 pop(); 340 mergeToTargetFrame(i.target()); 341 } 342 case IF_ACMPEQ, IF_ACMPNE, IF_ICMPEQ, IF_ICMPGE, IF_ICMPGT, IF_ICMPLE, IF_ICMPLT, IF_ICMPNE -> { 343 pop(2); 344 mergeToTargetFrame(i.target()); 345 } 346 case GOTO, GOTO_W -> { 347 mergeToTargetFrame(i.target()); 348 endOfFlow(); 349 } 350 } 351 } 352 case ConstantInstruction i -> 353 push(switch (i.constantValue()) { 354 case null -> NULL_TYPE; 355 case ClassDesc _ -> CD_Class; 356 case Double _ -> CD_double; 357 case Float _ -> CD_float; 358 case Integer _ -> CD_int; 359 case Long _ -> CD_long; 360 case String _ -> CD_String; 361 case DynamicConstantDesc<?> cd when cd.equals(NULL) -> NULL_TYPE; 362 case DynamicConstantDesc<?> cd -> cd.constantType(); 363 case DirectMethodHandleDesc _ -> CD_MethodHandle; 364 case MethodTypeDesc _ -> CD_MethodType; 365 }); 366 case ConvertInstruction i -> 367 pop(1).push(ClassDesc.ofDescriptor(i.toType().descriptor())); 368 case FieldInstruction i -> { 369 switch (i.opcode()) { 370 case GETSTATIC -> 371 push(i.typeSymbol()); 372 case GETFIELD -> 373 pop(1).push(i.typeSymbol()); 374 case PUTSTATIC -> 375 pop(1); 376 case PUTFIELD -> 377 pop(2); 378 } 379 } 380 case IncrementInstruction i -> { 381 Slot v = locals.get(i.slot()); 382 store(i.slot(), load(i.slot())); 383 v.link(locals.get(i.slot())); 384 insMap.put(elIndex, v); 385 } 386 case InvokeDynamicInstruction i -> 387 pop(i.typeSymbol().parameterCount()).push(i.typeSymbol().returnType()); 388 case InvokeInstruction i -> 389 pop(i.typeSymbol().parameterCount() + (i.opcode() == Opcode.INVOKESTATIC ? 0 : 1)) 390 .push(i.typeSymbol().returnType()); 391 case LoadInstruction i -> { 392 push(load(i.slot())); 393 insMap.put(elIndex, locals.get(i.slot())); 394 } 395 case StoreInstruction i -> { 396 store(i.slot(), pop()); 397 insMap.put(elIndex, locals.get(i.slot())); 398 } 399 case MonitorInstruction _ -> 400 pop(1); 401 case NewMultiArrayInstruction i -> 402 pop(i.dimensions()).push(i.arrayType().asSymbol()); 403 case NewObjectInstruction i -> 404 push(i.className().asSymbol()); 405 case NewPrimitiveArrayInstruction i -> 406 pop(1).push(ClassDesc.ofDescriptor(i.typeKind().descriptor()).arrayType()); 407 case NewReferenceArrayInstruction i -> 408 pop(1).push(i.componentType().asSymbol().arrayType()); 409 case OperatorInstruction i -> 410 pop(switch (i.opcode()) { 411 case ARRAYLENGTH, INEG, LNEG, FNEG, DNEG -> 1; 412 default -> 2; 413 }).push(ClassDesc.ofDescriptor(i.typeKind().descriptor())); 414 case StackInstruction i -> { 415 switch (i.opcode()) { 416 case POP -> pop(1); 417 case POP2 -> pop(doubleAt(-1) ? 1 : 2); 418 case DUP -> push(top()); 419 case DUP2 -> { 420 if (doubleAt(-1)) { 421 push(top()); 422 } else { 423 pushAt(-2, top2()); 424 } 425 } 426 case DUP_X1 -> pushAt(-2, top()); 427 case DUP_X2 -> pushAt(doubleAt(-2) ? -2 : -3, top()); 428 case DUP2_X1 -> { 429 if (doubleAt(-1)) { 430 pushAt(-2, top()); 431 } else { 432 pushAt(-3, top2()); 433 } 434 } 435 case DUP2_X2 -> { 436 if (doubleAt(-1)) { 437 pushAt(doubleAt(-2) ? -2 : -3, top()); 438 } else { 439 pushAt(doubleAt(-3) ? -3 : -4, top2()); 440 } 441 } 442 case SWAP -> pushAt(-1, pop()); 443 } 444 } 445 case TypeCheckInstruction i -> 446 pop(1).push(i.opcode() == Opcode.CHECKCAST ? i.type().asSymbol() : ConstantDescs.CD_int); 447 case LabelTarget lt -> { 448 var frame = stackMap.get(lt.label()); 449 if (frame != null) { 450 if (!stack.isEmpty() || !locals.isEmpty()) { 451 mergeToTargetFrame(lt.label()); 452 endOfFlow(); 453 } 454 stack.addAll(frame.stack()); 455 locals.addAll(frame.locals()); 456 } 457 for (ExceptionCatch ec : exceptionHandlers) { 458 if (lt.label() == ec.tryStart()) { 459 mergeLocalsToTargetFrame(stackMap.get(ec.handler())); 460 } 461 } 462 } 463 case ReturnInstruction _ , ThrowInstruction _ -> { 464 endOfFlow(); 465 } 466 case TableSwitchInstruction tsi -> { 467 pop(); 468 mergeToTargetFrame(tsi.defaultTarget()); 469 for (var c : tsi.cases()) { 470 mergeToTargetFrame(c.target()); 471 } 472 endOfFlow(); 473 } 474 case LookupSwitchInstruction lsi -> { 475 pop(); 476 mergeToTargetFrame(lsi.defaultTarget()); 477 for (var c : lsi.cases()) { 478 mergeToTargetFrame(c.target()); 479 } 480 endOfFlow(); 481 } 482 default -> {} 483 } 484 } 485 486 private void endOfFlow() { 487 stack.clear(); 488 locals.clear(); 489 } 490 491 private void mergeToTargetFrame(Label target) { 492 Frame targetFrame = stackMap.get(target); 493 // Merge stack 494 assert stack.size() == targetFrame.stack.size(); 495 for (int i = 0; i < targetFrame.stack.size(); i++) { 496 ClassDesc se = stack.get(i); 497 ClassDesc fe = targetFrame.stack.get(i); 498 if (!se.equals(fe)) { 499 if (se.isPrimitive() && CD_int.equals(fe)) { 500 targetFrame.stack.set(i, se); // Override int target frame type with more specific int sub-type 501 this.frameDirty = true; 502 } else { 503 stack.set(i, fe); // Override stack type with target frame type 504 } 505 } 506 } 507 mergeLocalsToTargetFrame(targetFrame); 508 } 509 510 private void mergeLocalsToTargetFrame(Frame targetFrame) { 511 // Merge locals 512 int lSize = Math.min(locals.size(), targetFrame.locals.size()); 513 for (int i = 0; i < lSize; i++) { 514 Slot le = locals.get(i); 515 Slot fe = targetFrame.locals.get(i); 516 if (le != null && fe != null) { 517 le.link(fe); // Link target frame var with its source 518 if (!le.type.equals(fe.type)) { 519 if (le.type.isPrimitive() && CD_int.equals(fe.type) ) { 520 fe.type = le.type; // Override int target frame type with more specific int sub-type 521 this.frameDirty = true; 522 } else { 523 le.type = fe.type; // Override var type with target frame type 524 } 525 } 526 } 527 } 528 } 529 }