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 26 package jdk.incubator.code.bytecode; 27 28 import java.lang.classfile.TypeKind; 29 import jdk.incubator.code.Block; 30 import jdk.incubator.code.Body; 31 import jdk.incubator.code.CodeElement; 32 import jdk.incubator.code.CopyContext; 33 import jdk.incubator.code.Op; 34 import jdk.incubator.code.TypeElement; 35 import jdk.incubator.code.Value; 36 import jdk.incubator.code.dialect.core.CoreOp; 37 import jdk.incubator.code.dialect.java.JavaOp; 38 import jdk.incubator.code.dialect.java.JavaType; 39 import java.util.ArrayDeque; 40 import java.util.ArrayList; 41 import java.util.BitSet; 42 import java.util.Deque; 43 import java.util.HashSet; 44 import java.util.IdentityHashMap; 45 import java.util.Iterator; 46 import java.util.List; 47 import java.util.Map; 48 import java.util.NoSuchElementException; 49 import java.util.Set; 50 import java.util.function.Consumer; 51 import java.util.function.Function; 52 53 /** 54 * 55 */ 56 final class SlotToVarTransformer { 57 58 static final class Var { 59 boolean single; 60 TypeKind typeKind; 61 Value value; 62 Body parentBody; 63 } 64 65 record ExcStackMap(List<Block> catchBlocks, Map<Block, BitSet> map) implements Function<Block, ExcStackMap> { 66 @Override 67 public ExcStackMap apply(Block b) { 68 BitSet excStack = map.computeIfAbsent(b, _ -> new BitSet()); 69 switch (b.terminatingOp()) { 70 case JavaOp.ExceptionRegionEnter ere -> { 71 BitSet entries = new BitSet(); 72 for (Block.Reference cbr : ere.catchBlocks()) { 73 Block cb = cbr.targetBlock(); 74 int i = catchBlocks.indexOf(cb); 75 if (i < 0) { 76 i = catchBlocks.size(); 77 catchBlocks.add(cb); 78 map.put(cb, excStack); 79 } 80 entries.set(i); 81 } 82 entries.or(excStack); 83 map.put(ere.start().targetBlock(), entries); 84 } 85 case JavaOp.ExceptionRegionExit ere -> { 86 excStack = (BitSet) excStack.clone(); 87 for (Block.Reference cbr : ere.catchBlocks()) { 88 excStack.clear(catchBlocks.indexOf(cbr.targetBlock())); 89 } 90 map.put(ere.end().targetBlock(), excStack); 91 } 92 case Op op -> { 93 for (Block.Reference tbr : op.successors()) { 94 map.put(tbr.targetBlock(), excStack); 95 } 96 } 97 } 98 return this; 99 } 100 101 void forEachHandler(Block b, Consumer<Block> hbc) { 102 map.get(b).stream().mapToObj(catchBlocks::get).forEach(hbc); 103 } 104 105 void forEachTryBlock(Block hb, Consumer<Block> bc) { 106 int i = catchBlocks.indexOf(hb); 107 if (i >= 0) { 108 for (var me : map.entrySet()) { 109 if (me.getValue().get(i)) bc.accept(me.getKey()); 110 } 111 } 112 } 113 } 114 115 static CoreOp.FuncOp transform(CoreOp.FuncOp func) { 116 try { 117 return new SlotToVarTransformer().convert(func); 118 } catch (Throwable t) { 119 System.out.println(func.toText()); 120 throw t; 121 } 122 } 123 124 private final Map<SlotOp, Var> varMap; 125 126 private SlotToVarTransformer() { 127 varMap = new IdentityHashMap<>(); 128 } 129 130 private CoreOp.FuncOp convert(CoreOp.FuncOp func) { 131 // Composing exception stack map to be able to follow slot ops from try to the handler 132 ExcStackMap excMap = func.traverse(new ExcStackMap(new ArrayList<>(), new IdentityHashMap<>()), 133 CodeElement.blockVisitor((map, b) -> map.apply(b))); 134 135 List<Var> toInitialize = func.body().traverse(new ArrayList<>(), CodeElement.opVisitor((toInit, op) -> { 136 if (op instanceof SlotOp slotOp && !varMap.containsKey(slotOp)) { 137 138 // Assign variable to segments, calculate var slotType 139 Var var = new Var(); // New variable 140 var.parentBody = slotOp.ancestorBody(); 141 var q = new ArrayDeque<SlotOp>(); 142 var stores = new ArrayList<SlotOp.SlotStoreOp>(); 143 q.add(slotOp); 144 while (!q.isEmpty()) { 145 SlotOp se = q.pop(); 146 if (!varMap.containsKey(se)) { 147 varMap.put(se, var); // Assign variable to the segment 148 if (var.typeKind == null) var.typeKind = se.typeKind(); // TypeKind is identical for all SlotOps of the same variable 149 for (SlotOp to : slotImmediateSuccessors(se, excMap)) { 150 // All following SlotLoadOp belong to the same variable 151 if (to instanceof SlotOp.SlotLoadOp) { 152 if (!varMap.containsKey(to)) { 153 q.add(to); 154 } 155 } 156 } 157 if (se instanceof SlotOp.SlotLoadOp) { 158 // Segments preceeding SlotLoadOp also belong to the same variable 159 for (SlotOp from : slotImmediatePredecessors(se, excMap)) { 160 if (!varMap.containsKey(from)) { 161 q.add(from); 162 } 163 } 164 } else if (se instanceof SlotOp.SlotStoreOp store) { 165 stores.add(store); // Collection of all SlotStoreOps of the variable 166 } 167 } 168 } 169 170 // Single-assigned variable has only one SlotStoreOp 171 var.single = stores.size() < 2; 172 173 // Identification of initial SlotStoreOp 174 for (var it = stores.iterator(); it.hasNext();) { 175 SlotOp s = it.next(); 176 if (isDominatedByTheSameVar(s, excMap)) { 177 // A store preceeding dominantly with segments of the same variable is not initial 178 it.remove(); 179 } 180 } 181 182 // Remaining stores are all initial. 183 if (stores.size() > 1) { 184 // A synthetic default-initialized dominant segment must be inserted to the variable, if there is more than one initial store segment. 185 // It is not necessary to link it with other variable segments, the analysys ends here. 186 toInit.add(varMap.get(stores.getFirst())); 187 } 188 189 190 } 191 return toInit; 192 })); 193 194 return func.transform((block, op) -> { 195 if (!toInitialize.isEmpty()) { 196 for (var it = toInitialize.iterator(); it.hasNext();) { 197 Var var = it.next(); 198 if (var.parentBody == op.ancestorBody()) { 199 var.value = block.op(CoreOp.var(toTypeElement(var.typeKind))); 200 it.remove(); 201 } 202 } 203 } 204 CopyContext cc = block.context(); 205 switch (op) { 206 case SlotOp.SlotLoadOp slo -> { 207 Var var = varMap.get(slo); 208 if (var.value == null) { 209 System.out.println(slo); 210 throw new AssertionError(); 211 } 212 cc.mapValue(op.result(), var.single ? var.value : block.op(CoreOp.varLoad(var.value))); 213 } 214 case SlotOp.SlotStoreOp sso -> { 215 Var var = varMap.get(sso); 216 Value val = sso.operands().getFirst(); 217 val = cc.getValueOrDefault(val, val); 218 if (var.single) { 219 var.value = val; 220 } else if (var.value == null) { 221 TypeElement varType = switch (val.type()) { 222 case UnresolvedType.Ref _ -> UnresolvedType.unresolvedRef(); 223 case UnresolvedType.Int _ -> UnresolvedType.unresolvedInt(); 224 default -> val.type(); 225 }; 226 var.value = block.op(CoreOp.var(null, varType, val)); 227 } else { 228 block.op(CoreOp.varStore(var.value, val)); 229 } 230 } 231 default -> 232 block.op(op); 233 } 234 return block; 235 }); 236 } 237 238 private static TypeElement toTypeElement(TypeKind tk) { 239 return switch (tk) { 240 case INT -> UnresolvedType.unresolvedInt(); 241 case REFERENCE -> UnresolvedType.unresolvedRef(); 242 case LONG -> JavaType.LONG; 243 case DOUBLE -> JavaType.DOUBLE; 244 case FLOAT -> JavaType.FLOAT; 245 case BOOLEAN -> JavaType.BOOLEAN; 246 case BYTE -> JavaType.BYTE; 247 case SHORT -> JavaType.SHORT; 248 case CHAR -> JavaType.CHAR; 249 case VOID -> throw new IllegalStateException("Unexpected void type."); 250 }; 251 } 252 253 // Traverse immediate same-slot successors of a SlotOp 254 private static Iterable<SlotOp> slotImmediateSuccessors(SlotOp slotOp, ExcStackMap excMap) { 255 return () -> new SlotOpIterator(slotOp, excMap, true); 256 } 257 258 // Traverse immediate same-slot predecessors of a SlotOp 259 private static Iterable<SlotOp> slotImmediatePredecessors(SlotOp slotOp, ExcStackMap excMap) { 260 return () -> new SlotOpIterator(slotOp, excMap, false); 261 } 262 263 private boolean isDominatedByTheSameVar(SlotOp slotOp, ExcStackMap excMap) { 264 Var var = varMap.get(slotOp); 265 Set<Op.Result> predecessors = new HashSet<>(); 266 for (SlotOp pred : slotImmediatePredecessors(slotOp, excMap)) { 267 if (varMap.get(pred) != var) { 268 return false; 269 } 270 if (pred != slotOp) predecessors.add(pred.result()); 271 } 272 return isDominatedBy(slotOp.result(), predecessors); 273 } 274 275 /** 276 * Returns {@code true} if this value is dominated by the given set of values {@code doms}. 277 * <p> 278 * The set dominates if every path from the entry node go through any member of the set. 279 * <p> 280 * First part checks individual dominance of every member of the set. 281 * <p> 282 * If no member of the set is individually dominant, the second part tries to find path 283 * to the entry block bypassing all blocks from the tested set. 284 * <p> 285 * Implementation searches for the paths by traversing the value declaring block predecessors, 286 * stopping at blocks where values from the tested set are declared or at blocks already processed. 287 * Negative test result is returned when the entry block is reached. 288 * Positive test result is returned when no path to the entry block is found. 289 * 290 * @param value the value 291 * @param doms the dominating set of values 292 * @return {@code true} if this value is dominated by the given set of values {@code dom}. 293 * @throws IllegalStateException if the declaring block is partially built 294 */ 295 public static boolean isDominatedBy(Value value, Set<? extends Value> doms) { 296 if (doms.isEmpty()) { 297 return false; 298 } 299 300 for (Value dom : doms) { 301 if (value.isDominatedBy(dom)) { 302 return true; 303 } 304 } 305 306 Set<Block> stopBlocks = new HashSet<>(); 307 for (Value dom : doms) { 308 stopBlocks.add(dom.declaringBlock()); 309 } 310 311 Deque<Block> toProcess = new ArrayDeque<>(); 312 toProcess.add(value.declaringBlock()); 313 stopBlocks.add(value.declaringBlock()); 314 while (!toProcess.isEmpty()) { 315 for (Block b : toProcess.pop().predecessors()) { 316 if (b.isEntryBlock()) { 317 return false; 318 } 319 if (stopBlocks.add(b)) { 320 toProcess.add(b); 321 } 322 } 323 } 324 return true; 325 } 326 327 static final class SlotOpIterator implements Iterator<SlotOp> { 328 329 SlotOp op; 330 final int slot; 331 final ExcStackMap map; 332 final TypeKind tk; 333 final boolean fwd; 334 Block b; 335 List<Op> ops; 336 int i; 337 BitSet visited; 338 ArrayDeque<Block> toVisit; 339 340 341 public SlotOpIterator(SlotOp slotOp, ExcStackMap excMap, boolean forward) { 342 slot = slotOp.slot; 343 tk = slotOp.typeKind(); 344 map = excMap; 345 fwd = forward; 346 b = slotOp.parentBlock(); 347 ops = fwd ? b.ops() : b.ops().reversed(); 348 i = ops.indexOf(slotOp) + 1; 349 } 350 351 @Override 352 public boolean hasNext() { 353 while (hasNextSlot()) { 354 // filter loads and stores of the same TypeKind (if known) 355 if (op.typeKind() == tk || op.typeKind() == null || tk == null) { 356 return true; 357 } 358 op = null; 359 } 360 return false; 361 } 362 363 private boolean hasNextSlot() { 364 if (op != null) { 365 return true; 366 } else { 367 while (b != null || toVisit != null && !toVisit.isEmpty()) { 368 if (b == null) { 369 b = toVisit.pop(); 370 ops = fwd ? b.ops() : b.ops().reversed(); 371 i = 0; 372 } 373 while (i < ops.size()) { 374 if (ops.get(i++) instanceof SlotOp sop && sop.slot == slot) { 375 op = sop; 376 b = null; 377 return true; 378 } 379 } 380 if (toVisit == null) { 381 toVisit = new ArrayDeque<>(); 382 visited = new BitSet(); 383 } 384 if (fwd) { 385 for (Block.Reference sr : b.successors()) { 386 Block sb = sr.targetBlock(); 387 if (!visited.get(sb.index())) { 388 toVisit.add(sb); 389 visited.set(sb.index()); 390 } 391 } 392 // Visit also relevant exception handlers 393 map.forEachHandler(b, sb -> { 394 if (!visited.get(sb.index())) { 395 toVisit.add(sb); 396 visited.set(sb.index()); 397 } 398 }); 399 } else { 400 for (Block pb : b.predecessors()) { 401 if (!visited.get(pb.index())) { 402 toVisit.add(pb); 403 visited.set(pb.index()); 404 } 405 } 406 // Visit also relevant try blocks from handler 407 map.forEachTryBlock(b, sb -> { 408 if (!visited.get(sb.index())) { 409 toVisit.add(sb); 410 visited.set(sb.index()); 411 } 412 }); 413 } 414 b = null; 415 } 416 return false; 417 } 418 } 419 420 @Override 421 public SlotOp next() { 422 if (!hasNext()) throw new NoSuchElementException(); 423 SlotOp ret = op; 424 op = null; 425 return ret; 426 } 427 } 428 }