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