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.ancestorBlock();
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 }