1 /*
2 * Copyright (c) 2024, 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.dialect.core;
27
28 import jdk.incubator.code.*;
29 import jdk.incubator.code.dialect.java.JavaOp;
30 import jdk.incubator.code.dialect.java.JavaType;
31
32 import java.util.*;
33
34 /**
35 * A code model transformer that normalizes blocks.
36 * <p>
37 * Merges redundant blocks with their predecessors, those which are unconditionally
38 * branched to and have only one predecessor.
39 * <p>
40 * Removes unused block parameters.
41 * <p>
42 * Skips intermediate conditional branches that use a single constant boolean argument,
43 * directly redirecting to the target true or false branch based on the constant's value.
44 */
45 public final class NormalizeBlocksTransformer implements CodeTransformer {
46 final Set<Block> mergedBlocks = new HashSet<>();
47 final Map<Block, BitSet> adjustedBlocks = new HashMap<>();
48
49 private NormalizeBlocksTransformer() {
50 }
51
52 /**
53 * Transforms an operation, merging redundant blocks.
54 *
55 * @param op the operation to transform
56 * @param <O> the type of operation
57 * @return the transformed operation
58 */
59 @SuppressWarnings("unchecked")
60 public static <O extends Op> O transform(O op) {
61 return (O) op.transform(CodeContext.create(), new NormalizeBlocksTransformer());
62 }
63
64 ;
65
66 @Override
67 public void acceptBlock(Block.Builder block, Block b) {
68 // Ignore merged block
69 if (!mergedBlocks.contains(b)) {
70 CodeTransformer.super.acceptBlock(block, b);
71 }
72 }
73
74 @Override
75 public Block.Builder acceptOp(Block.Builder b, Op op) {
76 switch (op) {
77 case CoreOp.BranchOp bop when bop.branch().targetBlock().predecessors().size() == 1 -> {
78 // Merge the successor's target block with this block, and so on
79 // The terminal branch operation is replaced with the operations in the
80 // successor's target block
81 mergeBlock(b, bop);
82 }
83 case CoreOp.BranchOp bop when isPureConditionalDispatchingBlock(bop.branch().targetBlock())
84 && bop.branch().arguments().getFirst() instanceof Op.Result or
85 && or.op() instanceof CoreOp.ConstantOp cop -> {
86 // Skip intermediate conditional branch with constant boolean argument and re-target
87 // directly to the true or false branch, based on the constant value.
88 CoreOp.ConditionalBranchOp cbo = (CoreOp.ConditionalBranchOp)bop.branch().targetBlock().terminatingOp();
89 Block.Reference br = (Boolean)cop.value() ? cbo.trueBranch() : cbo.falseBranch();
90 if (br.targetBlock().predecessors().size() == 1) {
91 // Merge the successor's target block with this block
92 mergeBlock(b, br.targetBlock());
93 } else {
94 b.add(CoreOp.branch(b.context().getReferenceOrCreate(br)));
95 }
96
97 // Remove the conditional dispatching block if all predecessor reference args are constants
98 if (bop.branch().targetBlock().predecessorReferences().stream()
99 .allMatch(r -> r.arguments().getFirst() instanceof Op.Result orr && orr.op() instanceof CoreOp.ConstantOp)) {
100 mergedBlocks.add(bop.branch().targetBlock());
101 }
102 }
103 case CoreOp.ConstantOp cop when cop.resultType().equals(JavaType.BOOLEAN)
104 && cop.result().uses().stream().allMatch(cr -> cr.op() instanceof CoreOp.BranchOp bop
105 && isPureConditionalDispatchingBlock(bop.branch().targetBlock())) -> {
106 // Remove boolean ConstantOp used purelly as BranchOp successor arguments to a conditional dispatching block
107 }
108 case JavaOp.ExceptionRegionEnter ere -> {
109 // Cannot remove block parameters from exception handlers
110 removeUnusedBlockParameters(b, ere.startReference());
111 b.add(op);
112 }
113 case JavaOp.ExceptionRegionExit ere -> {
114 // Cannot remove block parameters from exception handlers
115 removeUnusedBlockParameters(b, ere.endReference());
116 b.add(op);
117 }
118 case Op.BlockTerminating _ -> {
119 for (Block.Reference successor : op.successors()) {
120 removeUnusedBlockParameters(b, successor);
121 }
122 b.add(op);
123 }
124 default -> {
125 b.add(op);
126 }
127 }
128 return b;
129 }
130
131 private static boolean isPureConditionalDispatchingBlock(Block b) {
132 return b.parameters().size() == 1
133 && b.parameters().getFirst().type().equals(JavaType.BOOLEAN)
134 && b.ops().size() == 1
135 && b.terminatingOp() instanceof CoreOp.ConditionalBranchOp cbo
136 && cbo.operands().getFirst() == b.parameters().getFirst()
137 && cbo.trueBranch().arguments().isEmpty()
138 && cbo.falseBranch().arguments().isEmpty();
139 }
140
141 // Remove any unused block parameters and successor arguments
142 private void removeUnusedBlockParameters(Block.Builder b, Block.Reference successor) {
143 Block target = successor.targetBlock();
144 BitSet unusedParameterIndexes = adjustedBlocks.computeIfAbsent(target,
145 k -> adjustBlock(b, k));
146 if (!unusedParameterIndexes.isEmpty()) {
147 adjustSuccessor(unusedParameterIndexes, b, successor);
148 }
149
150 }
151
152 // Remove any unused block parameters
153 BitSet adjustBlock(Block.Builder b, Block target) {
154 // Determine the indexes of unused block parameters
155 List<Block.Parameter> parameters = target.parameters();
156 BitSet unusedParameterIndexes = parameters.stream()
157 .filter(p -> p.uses().isEmpty())
158 .mapToInt(Block.Parameter::index)
159 .collect(BitSet::new, BitSet::set, BitSet::or);
160
161 if (!unusedParameterIndexes.isEmpty()) {
162 // Create a new output block and remap it to the target block,
163 // overriding any previous mapping
164 Block.Builder adjustedBlock = b.block();
165 b.context().mapBlock(target, adjustedBlock);
166
167 // Update and remap the output block parameters
168 for (int i = 0; i < parameters.size(); i++) {
169 if (!unusedParameterIndexes.get(i)) {
170 Block.Parameter parameter = parameters.get(i);
171 b.context().mapValue(
172 parameter,
173 adjustedBlock.parameter(parameter.type()));
174 }
175 }
176 }
177
178 return unusedParameterIndexes;
179 }
180
181 // Remove any unused successor arguments
182 void adjustSuccessor(BitSet unusedParameterIndexes, Block.Builder b, Block.Reference successor) {
183 // Create a new output successor and remap it
184 List<Value> arguments = new ArrayList<>();
185 for (int i = 0; i < successor.arguments().size(); i++) {
186 if (!unusedParameterIndexes.get(i)) {
187 arguments.add(b.context().getValue(successor.arguments().get(i)));
188 }
189 }
190 Block.Reference adjustedSuccessor = b.context().getBlock(successor.targetBlock())
191 .reference(arguments);
192 b.context().mapReference(successor, adjustedSuccessor);
193 }
194
195 void mergeBlock(Block.Builder b, CoreOp.BranchOp bop) {
196 Block.Reference reference = bop.branch();
197 Block successor = reference.targetBlock();
198 // Replace use of the successor's parameters with the reference's arguments
199 b.context().mapValues(successor.parameters(),
200 b.context().getValues(reference.arguments()));
201 mergeBlock(b, successor);
202 }
203
204 void mergeBlock(Block.Builder b, Block successor) {
205 mergedBlocks.add(successor);
206
207 // Merge non-terminal operations
208 for (int i = 0; i < successor.ops().size() - 1; i++) {
209 acceptOp(b, successor.ops().get(i));
210 }
211
212 // Check if subsequent successor block can be normalized
213 acceptOp(b, successor.terminatingOp());
214 }
215 }