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 java.lang.reflect.code.analysis;
27
28 import java.lang.reflect.code.*;
29 import java.lang.reflect.code.op.CoreOp;
30 import java.util.ArrayDeque;
31 import java.util.ArrayList;
32 import java.util.Deque;
33 import java.util.HashMap;
34 import java.util.HashSet;
35 import java.util.LinkedHashMap;
36 import java.util.LinkedHashSet;
37 import java.util.List;
38 import java.util.Map;
39 import java.util.Set;
40 import java.util.stream.Collectors;
41
42 /**
43 * Functionality to transform a code model into pure SSA form, replacing operations that declare variables and
44 * access them with the use of values they depend on or additional block parameters.
45 */
46 public final class SSA {
47 private SSA() {
48 }
49
50 /**
51 * Applies an SSA transformation to an invokable operation, replacing operations that declare variables and
52 * access them with the use of values they depend on or additional block parameters.
53 * <p>
54 * The operation should first be in lowered form before applying this transformation.
55 * <p>
56 * Note: this implementation does not currently work correctly when a variable is stored to within an exception
57 * region and read from outside as a result of catching an exception. In such cases a complete transformation may be
58 * not possible and such variables will need to be retained.
59 *
60 * @param iop the invokable operation
61 * @return the transformed operation
62 * @param <T> the invokable type
63 */
64 public static <T extends Op & Op.Invokable> T transform(T iop) {
65 Map<Block, Set<CoreOp.VarOp>> joinPoints = new HashMap<>();
66 Map<CoreOp.VarAccessOp.VarLoadOp, Object> loadValues = new HashMap<>();
67 Map<Block.Reference, List<Object>> joinSuccessorValues = new HashMap<>();
68
69 Map<Body, Boolean> visited = new HashMap<>();
70 Map<Block, Map<CoreOp.VarOp, Block.Parameter>> joinBlockArguments = new HashMap<>();
71 @SuppressWarnings("unchecked")
72 T liop = (T) iop.transform(CopyContext.create(), (block, op) -> {
73 // Compute join points and value mappings for body
74 visited.computeIfAbsent(op.ancestorBody(), b -> {
75 findJoinPoints(b, joinPoints);
76 variableToValue(b, joinPoints, loadValues, joinSuccessorValues);
77 return true;
78 });
79
80 if (op instanceof CoreOp.VarOp || op instanceof CoreOp.VarAccessOp) {
81 // Drop var operations
82 if (op instanceof CoreOp.VarAccessOp.VarLoadOp vl) {
83 // Replace result of load
84 Object loadValue = loadValues.get(vl);
85 CopyContext cc = block.context();
86 Value v = loadValue instanceof VarOpBlockArgument vba
87 ? joinBlockArguments.get(vba.b()).get(vba.vop())
88 : cc.getValue((Value) loadValue);
89 cc.mapValue(op.result(), v);
90 }
91 } else if (op instanceof Op.Terminating) {
92 for (Block.Reference s : op.successors()) {
93 List<Object> joinValues = joinSuccessorValues.get(s);
94 // Successor has join values
95 if (joinValues != null) {
96 CopyContext cc = block.context();
97
98 // Lazily append target block arguments
99 joinBlockArguments.computeIfAbsent(s.targetBlock(), b -> {
100 Block.Builder bb = cc.getBlock(b);
101 return joinPoints.get(b).stream().collect(Collectors.toMap(
102 varOp -> varOp,
103 varOp -> bb.parameter(varOp.varType())));
104 });
105
106 // Append successor arguments
107 List<Value> values = new ArrayList<>();
108 for (Object o : joinValues) {
109 Value v = o instanceof VarOpBlockArgument vba
110 ? joinBlockArguments.get(vba.b()).get(vba.vop())
111 : cc.getValue((Value) o);
112 values.add(v);
113 }
114
115 // Map successor with append arguments
116 List<Value> toArgs = cc.getValues(s.arguments());
117 toArgs.addAll(values);
118 Block.Reference toS = cc.getBlock(s.targetBlock()).successor(toArgs);
119 cc.mapSuccessor(s, toS);
120 }
121 }
122
123 block.apply(op);
124 } else {
125 block.apply(op);
126 }
127
128 return block;
129 });
130 return liop;
131 }
132
133 record VarOpBlockArgument(Block b, CoreOp.VarOp vop) {
134 }
135
136 // @@@ Check for var uses in exception regions
137 // A variable cannot be converted to SAA form if the variable is stored
138 // to in an exception region and accessed from an associated catch region
139
140 static void variableToValue(Body body,
141 Map<Block, Set<CoreOp.VarOp>> joinPoints,
142 Map<CoreOp.VarAccessOp.VarLoadOp, Object> loadValues,
143 Map<Block.Reference, List<Object>> joinSuccessorValues) {
144 Map<CoreOp.VarOp, Deque<Object>> variableStack = new HashMap<>();
145 Node top = buildDomTree(body.entryBlock(), body.immediateDominators());
146 variableToValue(top, variableStack, joinPoints, loadValues, joinSuccessorValues);
147 }
148
149 /**
150 * Replaces usages of a variable with the corresponding value, from a given block node in the dominator tree.
151 * <p>
152 * The result of a {@code VarLoadOp} for variable, {@code V} say the result of a {@code VarOp} operation,
153 * is replaced with the value passed as an operand to the immediately dominating {@code VarStoreOp} that operates
154 * on {@code V}, or a block argument representing the equivalent of a phi-value of {@code V}.
155 * After which, any related {@code VarOp}, {@code VarLoadOp}, or {@code VarStoreOp} operations are removed.
156 *
157 * @param n the node in the dominator tree
158 * @param variableStack the variable stack
159 * @param joinPoints the join points
160 * @implNote See "Efficiently Computing Static Single Assignment Form and the Control Dependence Graph" by Ron Cytron et. al.
161 * Section 5.2 and Figure 12.
162 */
163 static void variableToValue(Node n,
164 Map<CoreOp.VarOp, Deque<Object>> variableStack,
165 Map<Block, Set<CoreOp.VarOp>> joinPoints,
166 Map<CoreOp.VarAccessOp.VarLoadOp, Object> loadValues,
167 Map<Block.Reference, List<Object>> joinSuccessorValues) {
168 int size = n.b().ops().size();
169
170 // Check if V is associated with block argument (phi)
171 // Push argument onto V's stack
172 {
173 Set<CoreOp.VarOp> varOps = joinPoints.get(n.b());
174 if (varOps != null) {
175 varOps.forEach(v -> {
176 assert variableStack.get(v) != null;
177 variableStack.get(v).push(new VarOpBlockArgument(n.b(), v));
178 });
179 }
180 }
181
182 {
183 for (int i = 0; i < size - 1; i++) {
184 Op op = n.b().ops().get(i);
185
186 if (op instanceof CoreOp.VarOp varOp) {
187 // Initial value assigned to variable
188 Value current = op.operands().get(0);
189 variableStack.computeIfAbsent(varOp, _k -> new ArrayDeque<>())
190 .push(current);
191 } else if (op instanceof CoreOp.VarAccessOp.VarStoreOp storeOp) {
192 // Value assigned to variable
193 Value current = op.operands().get(1);
194 variableStack.computeIfAbsent(storeOp.varOp(), _k -> new ArrayDeque<>())
195 .push(current);
196 } else if (op instanceof CoreOp.VarAccessOp.VarLoadOp loadOp) {
197 Object to = variableStack.get(loadOp.varOp()).peek();
198 loadValues.put(loadOp, to);
199 } else if (op instanceof Op.Nested) {
200 // Traverse descendant variable loads for variables
201 // declared in the block's parent body
202 op.traverse(null, (o, codeElement) -> {
203 if (o instanceof CoreOp.VarAccessOp.VarLoadOp loadOp &&
204 loadOp.varOp().ancestorBody() == op.ancestorBody()) {
205 Object to = variableStack.get(loadOp.varOp()).peek();
206 loadValues.put(loadOp, to);
207 }
208 return null;
209 });
210 }
211 }
212
213 // Add successor args for joint points
214 for (Block.Reference succ : n.b().successors()) {
215 Set<CoreOp.VarOp> varOps = joinPoints.get(succ.targetBlock());
216 if (varOps != null) {
217 List<Object> joinValues = varOps.stream()
218 .map(vop -> variableStack.get(vop).peek()).toList();
219 joinSuccessorValues.put(succ, joinValues);
220 }
221 }
222
223 // The result of a VarOp, a variable value, can only be used in VarStoreOp and VarLoadOp
224 // therefore there is no need to check existing successor arguments
225 }
226
227 // Traverse children of dom tree
228 for (Node y : n.children()) {
229 variableToValue(y, variableStack, joinPoints, loadValues, joinSuccessorValues);
230 }
231
232 // Pop off values for variables
233 {
234 Set<CoreOp.VarOp> varOps = joinPoints.get(n.b());
235 if (varOps != null) {
236 varOps.forEach(v -> {
237 variableStack.get(v).pop();
238 });
239 }
240
241 for (int i = 0; i < size - 1; i++) {
242 Op op = n.b().ops().get(i);
243
244 if (op instanceof CoreOp.VarOp varOp) {
245 variableStack.get(varOp).pop();
246 } else if (op instanceof CoreOp.VarAccessOp.VarStoreOp storeOp) {
247 variableStack.get(storeOp.varOp()).pop();
248 }
249 }
250 }
251 }
252
253 /**
254 * Finds the join points of a body.
255 * <p>
256 * A join point is a block that is in the dominance frontier of one or more predecessors, that make one or more
257 * stores to variables (using the {@code VarStoreOp} operation on the result of a {@code VarOp} operation).
258 * The join point contains the set variables ({@code VarOp} operations) that are stored to.
259 * <p>
260 * A variable of a joint point indicates that a block argument may need to be added to the join point's block
261 * when converting variables to SSA form. Different values of a variable may occur at different control flow
262 * paths at the join point. The block argument represents the convergence of multiple values for the same
263 * variable, where a predecessor assigns to the block argument.
264 * (Block arguments are equivalent to phi-values, or phi-nodes, used in other representations.)
265 *
266 * @param body the body.
267 * @param joinPoints the returned join points.
268 * @implNote See "Efficiently Computing Static Single Assignment Form and the Control Dependence Graph" by Ron Cytron et. al.
269 * Section 5.1 and Figure 11.
270 */
271 public static void findJoinPoints(Body body, Map<Block, Set<CoreOp.VarOp>> joinPoints) {
272 Map<Block, Set<Block>> df = body.dominanceFrontier();
273 Map<CoreOp.VarOp, Set<Block>> a = findVarStores(body);
274
275 int iterCount = 0;
276 int[] hasAlready = new int[body.blocks().size()];
277 int[] work = new int[body.blocks().size()];
278
279 Deque<Block> w = new ArrayDeque<>();
280
281 for (CoreOp.VarOp v : a.keySet()) {
282 iterCount++;
283
284 for (Block x : a.get(v)) {
285 work[x.index()] = iterCount;
286 w.push(x);
287 }
288
289 while (!w.isEmpty()) {
290 Block x = w.pop();
291
292 for (Block y : df.getOrDefault(x, Set.of())) {
293 if (hasAlready[y.index()] < iterCount) {
294 // Only add to the join points if y is dominated by the var's block
295 if (y.isDominatedBy(v.parentBlock())) {
296 joinPoints.computeIfAbsent(y, _k -> new LinkedHashSet<>()).add(v);
297 }
298 hasAlready[y.index()] = iterCount;
299
300 if (work[y.index()] < iterCount) {
301 work[y.index()] = iterCount;
302 w.push(y);
303 }
304 }
305 }
306 }
307 }
308 }
309
310 // Returns map of variable to blocks that contain stores to the variables declared in the body
311 // Throws ISE if a descendant store operation is encountered
312 // @@@ Compute map for whole tree, then traverse keys with filter
313 static Map<CoreOp.VarOp, Set<Block>> findVarStores(Body r) {
314 return r.traverse(new LinkedHashMap<>(), CodeElement.opVisitor((stores, op) -> {
315 if (op instanceof CoreOp.VarAccessOp.VarStoreOp storeOp) {
316 if (storeOp.varOp().ancestorBody() != storeOp.ancestorBody()) {
317 throw new IllegalStateException("Descendant variable store operation");
318 }
319 if (storeOp.varOp().ancestorBody() == r) {
320 stores.computeIfAbsent(storeOp.varOp(), _v -> new LinkedHashSet<>()).add(storeOp.parentBlock());
321 }
322 }
323 return stores;
324 }));
325 }
326
327 record Node(Block b, Set<Node> children) {
328 }
329
330 static Node buildDomTree(Block entryBlock, Map<Block, Block> idoms) {
331 Map<Block, Node> tree = new HashMap<>();
332 for (Map.Entry<Block, Block> e : idoms.entrySet()) {
333 Block id = e.getValue();
334 Block b = e.getKey();
335
336 Node parent = tree.computeIfAbsent(id, _k -> new Node(_k, new HashSet<>()));
337 if (b == entryBlock) {
338 continue;
339 }
340
341 Node child = tree.computeIfAbsent(b, _k -> new Node(_k, new HashSet<>()));
342 parent.children.add(child);
343 }
344 return tree.get(entryBlock);
345 }
346 }