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 package jdk.incubator.code.dialect.java;
26
27 import jdk.incubator.code.*;
28 import jdk.incubator.code.dialect.core.CoreOp;
29
30 import java.util.*;
31 import java.util.function.BiFunction;
32
33 import static jdk.incubator.code.Op.Lowerable.loweringTransformer;
34
35 /**
36 * An operation characteristic indicating that an operation can model a boolean expression whose evaluation contains
37 * control flow. Such operations can lower themselves using a supplied continuation for its boolean result to produce
38 * simpler control flow graphs.
39 * <p>
40 * For example, consider the following code, in which a boolean expression is used by a {@code while} statement:
41 * {@snippet lang = java:
42 * while (a && (b || c)) {
43 * ...
44 * }
45 * }
46 * The result of the {@code while} loop's boolean expression determines whether the loop body is executed or the loop
47 * finishes. If {@code a} is {@code true} and {@code b} or {@code c} is {@code true} then the loop body is executed.
48 * Conversely, if {@code a} is {@code false} or {@code b} and {@code c} is {@code false} then the loop finishes.
49 * <p>
50 * The code model for this code contains a while operation, modeling the {@code while} statement. When the while
51 * operation lowers itself it creates a boolean result continuation containing block references to the blocks associated
52 * with start of executing the loop body and the loop finishing, referred to respectively as true and false branch
53 * references.
54 * That boolean result continuation is used when lowering operation's predicate body, which models the boolean
55 * expression, the conditional-and operation modeling the conditional-and expression. The continuation is passed along
56 * when lowering the sub-expressions, and when needed the continuation is operated on to continue with a boolean result
57 * or to obtain block references for a statically known boolean result. Consequently, the lowering of the boolean
58 * expression will directly branch to the while operation's continuation's true and false branch references. This is far
59 * more preferable than creating localized control flow behavior that joins to blocks whose boolean block parameter
60 * represents an intermediate boolean result; a result that is then used by a conditional branch operations to continue
61 * towards the blocks of the lowered while operation.
62 */
63 interface ControlFlowBooleanExpressionOp extends Op.Lowerable {
64
65 ContextStackArg<BooleanResultContinuation> BOOLEAN_CONTINUATION_ARG = new ContextStackArg<>();
66
67 static void lowerBooleanBody(
68 Block.Builder startBlock,
69 Body body,
70 List<? extends Value> entryValues,
71 BooleanResultContinuation continuation,
72 BiFunction<Block.Builder, Op, Block.Builder> inherited) {
73 BooleanExpressionSuffix suffix = findBooleanExpressionSuffix(body);
74 CodeTransformer codeTransformer;
75 if (suffix != null) {
76 boolean[] isSuffixProcessed = new boolean[1];
77 codeTransformer = loweringTransformer(inherited, (block, op) -> {
78 if (op == suffix.expression) {
79 // Process the boolean expression
80 isSuffixProcessed[0] = true;
81
82 ConditionalBranchContinuation expressionContinuation =
83 continuation.forExpression(block, suffix.negatesExpression);
84 // Pass expression continuation as additional implicit argument
85 BOOLEAN_CONTINUATION_ARG.push(block.context(), expressionContinuation);
86 return suffix.expression.lower(block, inherited);
87 } else if (!isSuffixProcessed[0]) {
88 // Process any operation in the prefix
89 return null;
90 } else {
91 // Ignore any operation in the suffix after ControlFlowBooleanExpressionOp
92 return block;
93 }
94 });
95 } else {
96 codeTransformer = loweringTransformer(inherited, (block, op) -> {
97 if (op instanceof CoreOp.YieldOp yield) {
98 Value booleanResult = block.context().getValue(yield.yieldValue());
99 continuation.continueWith(block, booleanResult);
100 return block;
101 } else {
102 return null;
103 }
104 });
105 }
106 startBlock.transformBody(body, entryValues, codeTransformer);
107 }
108
109 /**
110 * Represents the continuation of a boolean result.
111 * <p>
112 * If the lowering of a boolean expression operation needs to continue with expression's boolean result value,
113 * then it can invoke {@link #continueWith(Block.Builder, Value) continueWith}. Otherwise, if lowering statically
114 * knows the value of the expression and requires a block reference targeting a continuing block corresponding to
115 * that known value , then it can invoke {@link #referenceFor(Block.Builder, boolean) referenceFor}.
116 */
117 sealed interface BooleanResultContinuation
118 permits ConditionalBranchContinuation, BranchWithArgumentContinuation {
119 /**
120 * Continues with the result of a boolean expression.
121 *
122 * @param block the block to add a block terminating operation
123 * @param result the boolean result.
124 */
125 void continueWith(Block.Builder block, Value result);
126
127 /**
128 * Creates a block reference to branch to continue the result of the boolean expression when the result is
129 * statically known.
130 *
131 * @param block the block to add any necessary operations
132 * @param result the static boolean result
133 * @return the block reference to continue the result
134 */
135 Block.Reference referenceFor(Block.Builder block, boolean result);
136
137 /**
138 * Creates a conditional branch continuation from this continuation to be used as the continuation of a boolean
139 * expression.
140 *
141 * @param negatesExpression true if the result of the expression is negated
142 * @return the conditional branch continuation
143 */
144 default ConditionalBranchContinuation forExpression(Block.Builder block, boolean negatesExpression) {
145 Block.Reference trueRef = referenceFor(block, !negatesExpression);
146 Block.Reference falseRef = referenceFor(block, negatesExpression);
147 return new ConditionalBranchContinuation(trueRef, falseRef);
148 }
149 }
150
151 /**
152 * Represents a boolean result continuation as block references to blocks corresponding to continuing the
153 * {@code true} result and the {@code false} result.
154 *
155 * @param trueRef the block reference to a block corresponding to continuing the {@code true} result
156 * @param falseRef the block reference to a block corresponding to continuing the {@code false} result
157 */
158 record ConditionalBranchContinuation(
159 Block.Reference trueRef,
160 Block.Reference falseRef) implements BooleanResultContinuation {
161 @Override
162 public void continueWith(Block.Builder block, Value result) {
163 // result will be present in a model being built, so only its operation structure can be queried
164 if (result instanceof Op.Result opResult
165 && opResult.op() instanceof CoreOp.ConstantOp constant
166 && constant.value() instanceof Boolean booleanValue) {
167 block.add(CoreOp.branch(
168 booleanValue ? trueRef : falseRef));
169 } else {
170 block.add(CoreOp.conditionalBranch(result, trueRef, falseRef));
171 }
172 }
173
174 @Override
175 public Block.Reference referenceFor(Block.Builder block, boolean result) {
176 return result ? trueRef : falseRef;
177 }
178
179 @Override
180 public ConditionalBranchContinuation forExpression(Block.Builder block, boolean negatesExpression) {
181 return !negatesExpression
182 ? this
183 : new ConditionalBranchContinuation(falseRef, trueRef);
184 }
185 }
186
187 /**
188 * Represents a boolean result continuation as a result block with a boolean parameter, whose value corresponds to
189 * continuing the {@code true} result and the {@code false} result.
190 *
191 * @param resultBlock the result block with a boolean parameter corresponding to continuing the {@code true}
192 * and {@code false} result
193 */
194 record BranchWithArgumentContinuation(Block.Builder resultBlock) implements BooleanResultContinuation {
195 @Override
196 public void continueWith(Block.Builder block, Value result) {
197 block.add(CoreOp.branch(resultBlock.reference(result)));
198 }
199
200 @Override
201 public Block.Reference referenceFor(Block.Builder block, boolean result) {
202 return resultBlock.reference(block.add(CoreOp.constant(JavaType.BOOLEAN, result)));
203 }
204 }
205
206 record BooleanExpressionSuffix(ControlFlowBooleanExpressionOp expression, boolean negatesExpression) {
207 }
208
209 private static BooleanExpressionSuffix findBooleanExpressionSuffix(Body body) {
210 if (body.blocks().size() != 1) {
211 return null;
212 }
213
214 Block block = body.entryBlock();
215
216 // Find suffix of
217 // ControlFlowBooleanExpressionOp
218 // NotOp *
219 // CoreOp.YieldOp
220
221 Op.Terminating yop = block.terminatingOp();
222 if (!(yop instanceof CoreOp.YieldOp)) {
223 return null;
224 }
225
226 boolean negatesExpression = false;
227 Op next = yop;
228 Op expression = null;
229 List<Op> ops = block.ops();
230 for (int i = ops.size() - 2; i >= 0; i--) {
231 Op op = ops.get(i);
232
233 if (next.operands().isEmpty() || next.operands().getFirst() != op.result()) {
234 return null;
235 } else if (op instanceof JavaOp.NotOp) {
236 negatesExpression = !negatesExpression;
237 } else if (isSupportedBooleanExpressionOp(op)) {
238 expression = op;
239 break;
240 } else {
241 break;
242 }
243
244 next = op;
245 }
246
247 return expression != null
248 ? new BooleanExpressionSuffix((ControlFlowBooleanExpressionOp) expression, negatesExpression)
249 : null;
250 }
251
252 private static boolean isSupportedBooleanExpressionOp(Op op) {
253 return op instanceof ControlFlowBooleanExpressionOp && op.resultType().equals(JavaType.BOOLEAN);
254 }
255 }