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 }