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