1 /*
2 * Copyright (c) 2026, 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.internal;
27
28 import java.util.ArrayDeque;
29 import java.util.ArrayList;
30 import java.util.Deque;
31 import java.util.BitSet;
32 import java.util.HashMap;
33 import java.util.List;
34 import java.util.Map;
35 import java.util.Objects;
36 import java.util.Optional;
37
38 import jdk.incubator.code.Block;
39 import jdk.incubator.code.Body;
40 import jdk.incubator.code.CodeContext;
41 import jdk.incubator.code.CodeTransformer;
42 import jdk.incubator.code.Op;
43 import jdk.incubator.code.Value;
44 import jdk.incubator.code.dialect.core.CoreOp;
45 import jdk.incubator.code.dialect.java.JavaOp;
46 import jdk.incubator.code.dialect.java.JavaType;
47
48 /**
49 * Prepares a fixed point control-flow and builds the model once
50 */
51 public final class ControlFlowPreparation implements CodeTransformer {
52
53 @SuppressWarnings("unchecked")
54 public static <O extends Op> O transform(O operation) {
55 Objects.requireNonNull(operation);
56 List<Op> branches = operation.elements().filter(e -> e instanceof CoreOp.BranchOp
57 || e instanceof CoreOp.ConditionalBranchOp).map(Op.class::cast).toList();
58 if (branches.stream().noneMatch(CoreOp.ConditionalBranchOp.class::isInstance)) {
59 return operation;
60 }
61 ControlFlowPreparation cfp = new ControlFlowPreparation(operation, branches);
62 cfp.prepare();
63 return cfp.rewrites.isEmpty() ? operation : (O) operation.transform(CodeContext.create(), cfp);
64 }
65
66 private record Target(Block block, List<Value> arguments) {
67 Target(Block.Reference reference) {
68 this(reference.targetBlock(), reference.arguments());
69 }
70
71 Block.Reference map(CodeContext context) {
72 return context.getBlock(block).reference(context.getValues(arguments));
73 }
74 }
75
76 final Op root;
77 final List<Op> branches;
78 final Map<Op, List<Target>> rewrites = new HashMap<>();
79 final Map<Op, List<Target>> originalTargets = new HashMap<>();
80 final Map<Body, BitSet> reachable = new HashMap<>();
81 final BitSet routeVisited = new BitSet();
82 final Map<Block, Boolean> routable = new HashMap<>();
83 final Map<Block, List<List<Value>>> incoming = new HashMap<>();
84 final ConstantValueAnalysis constants = new ConstantValueAnalysis(block -> incoming.getOrDefault(block, List.of()));
85
86 private ControlFlowPreparation(Op root, List<Op> branches) {
87 this.root = root;
88 this.branches = branches;
89 }
90
91 private void prepare() {
92 boolean changed;
93 do {
94 reachable.values().forEach(BitSet::clear);
95 incoming.values().forEach(List::clear);
96 Deque<Block> work = new ArrayDeque<>();
97 for (var body : root.bodies()) work.add(body.entryBlock());
98 while (!work.isEmpty()) {
99 Block block = work.removeFirst();
100 BitSet live = reachable.computeIfAbsent(block.parent(), _ -> new BitSet());
101 if (live.get(block.index())) continue;
102 live.set(block.index());
103 for (Op operation : block.ops())
104 for (var body : operation.bodies()) work.add(body.entryBlock());
105 for (Target target : targets(block.terminatingOp())) {
106 incoming.computeIfAbsent(target.block, _ -> new ArrayList<>()).add(target.arguments);
107 work.add(target.block);
108 }
109 }
110 // stop when every reachable conditional is resolved
111 if (branches.stream().noneMatch(op -> op instanceof CoreOp.ConditionalBranchOp
112 && isReachable(op.parent()) && targets(op).size() == 2)) return;
113 // known constants remain valid
114 constants.clearUnknowns();
115 changed = false;
116 for (Op branch : branches) {
117 if (isReachable(branch.parent())) changed |= discover(branch);
118 }
119 } while (changed);
120 }
121
122 private List<Target> targets(Op operation) {
123 List<Target> changed = rewrites.get(operation);
124 return changed != null ? changed : originalTargets.computeIfAbsent(operation,
125 op -> op.successors().stream().map(Target::new).toList());
126 }
127
128 private boolean isReachable(Block block) {
129 BitSet live = reachable.get(block.parent());
130 return live != null && live.get(block.index());
131 }
132
133 private boolean discover(Op operation) {
134 List<Target> before = targets(operation);
135 List<Target> after;
136 if (operation instanceof CoreOp.ConditionalBranchOp branch && before.size() == 2
137 && constants.booleanValue(branch.predicateOperand()) instanceof Boolean value) {
138 after = List.of(route(before.get(value ? 0 : 1)));
139 } else {
140 // allocate replacement successors when routing changes
141 after = null;
142 for (int i = 0; i < before.size(); i++) {
143 Target next = route(before.get(i));
144 if (!next.equals(before.get(i))) {
145 if (after == null) after = new ArrayList<>(before);
146 after.set(i, next);
147 }
148 }
149 if (after == null) return false;
150 }
151 if (before.equals(after)) return false;
152 rewrites.put(operation, after);
153 return true;
154 }
155
156 private boolean canRoute(Block block) {
157 return routable.computeIfAbsent(block, b ->
158 (b.terminatingOp() instanceof CoreOp.BranchOp
159 || b.terminatingOp() instanceof CoreOp.ConditionalBranchOp)
160 && (b.ops().size() == 1 || b.parameters().size() == 1
161 && b.parameters().getFirst().type().equals(JavaType.BOOLEAN)
162 && b.ops().stream().limit(b.ops().size() - 1)
163 .allMatch(JavaOp.NotOp.class::isInstance)));
164 }
165
166 private Target route(Target start) {
167 if (!canRoute(start.block)) return start;
168 Target current = start, selected = start;
169 Boolean argument = booleanArgument(current);
170 // routing stays within one immutable body
171 routeVisited.clear();
172 while (!current.block.isEntryBlock() && !routeVisited.get(current.block.index())) {
173 Block block = current.block;
174 routeVisited.set(block.index());
175 Op terminator = block.terminatingOp();
176 List<Op> operations = block.ops().subList(0, block.ops().size() - 1);
177 List<Target> outgoing = targets(terminator);
178 // empty forwarding block with no side-used parameters
179 if (operations.isEmpty() && outgoing.size() == 1
180 && (terminator instanceof CoreOp.BranchOp || terminator instanceof CoreOp.ConditionalBranchOp)
181 && block.parameters().stream().allMatch(p -> onlyUsedBy(p, terminator))) {
182 // compose edge arguments through empty forwarding blocks without merging blocks or deleting parameters
183 if (!canRoute(outgoing.getFirst().block)) break;
184 List<Value> arguments = current.arguments;
185 Boolean previous = argument;
186 List<Value> forwarded = outgoing.getFirst().arguments.stream()
187 .map(v -> v instanceof Block.Parameter p && p.declaringBlock() == block
188 ? arguments.get(p.index()) : v).toList();
189 argument = outgoing.getFirst().arguments.size() == 1
190 && block.parameters().size() == 1
191 && outgoing.getFirst().arguments.getFirst() == block.parameters().getFirst()
192 ? previous : booleanArgument(new Target(outgoing.getFirst().block, forwarded));
193 current = new Target(outgoing.getFirst().block, forwarded);
194 continue;
195 }
196 // remaining blocks with single boolean
197 if (argument == null || block.parameters().size() != 1
198 || !block.parameters().getFirst().type().equals(JavaType.BOOLEAN)) break;
199 Value value = block.parameters().getFirst();
200 boolean valid = true;
201 // successive negations with no side uses
202 for (Op operation : operations) {
203 if (!(operation instanceof JavaOp.NotOp not)
204 || not.operand() != value || !onlyUsedBy(value, operation)) {
205 valid = false;
206 break;
207 }
208 value = operation.result();
209 argument = !argument;
210 }
211 if (!valid || !onlyUsedBy(value, terminator)) break;
212 // shortcut for boolean dispatch with no-args exits
213 if (terminator instanceof CoreOp.ConditionalBranchOp branch
214 && branch.predicateOperand() == value
215 && outgoing.stream().allMatch(target -> target.arguments.isEmpty())) {
216 current = outgoing.get(outgoing.size() == 1 ? 0 : argument ? 0 : 1);
217 selected = current;
218 argument = booleanArgument(current);
219 } else if (terminator instanceof CoreOp.BranchOp
220 && outgoing.getFirst().arguments.size() == 1
221 && outgoing.getFirst().arguments.getFirst() == value) {
222 // carry boolean through a chain, no synthetic literal
223 current = new Target(outgoing.getFirst().block, current.arguments);
224 } else {
225 break;
226 }
227 }
228 // retain the last target
229 return selected;
230 }
231
232 private Boolean booleanArgument(Target target) {
233 return target.arguments.size() == 1
234 ? constants.booleanValue(target.arguments.getFirst()) : null;
235 }
236
237 private boolean onlyUsedBy(Value value, Op selected) {
238 // routing commits only zero-argument dispatch exits
239 // conditional selection only removes edges
240 for (Op.Result use : value.uses()) {
241 Op operation = use.op();
242 if (operation == selected || !isReachable(operation.parent())) continue;
243 boolean collapsed = operation instanceof CoreOp.ConditionalBranchOp
244 && targets(operation).size() == 1;
245 if (!collapsed && operation.operands().contains(value)
246 || targets(operation).stream().anyMatch(t -> t.arguments.contains(value))) return false;
247 }
248 return true;
249 }
250
251 @Override
252 public void acceptBlock(Block.Builder builder, Block block) {
253 if (isReachable(block)) CodeTransformer.super.acceptBlock(builder, block);
254 }
255
256 @Override
257 public Block.Builder acceptOp(Block.Builder builder, Op operation) {
258 List<Target> targets = rewrites.get(operation);
259 CodeContext context = builder.context();
260 Op replacement;
261 if (targets == null) {
262 Optional<Object> constant;
263 if (!operation.bodies().isEmpty()
264 || (constant = constants.evaluate(operation.result())).isEmpty()) {
265 builder.add(operation);
266 return builder;
267 }
268 // drop constant expressions consumed only by folded expressions
269 if (onlyUsedBy(operation.result(), null)) {
270 return builder;
271 }
272 replacement = CoreOp.constant(operation.resultType(), constant.orElseThrow());
273 } else {
274 replacement = targets.size() == 1
275 ? CoreOp.branch(targets.getFirst().map(context))
276 : CoreOp.conditionalBranch(context.getValue(operation.operands().getFirst()),
277 targets.get(0).map(context), targets.get(1).map(context));
278 }
279 Op.Result result = builder.add(replacement);
280 result.op().setLocation(operation.location());
281 context.mapValue(operation.result(), result);
282 return builder;
283 }
284 }