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