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