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
32 import java.util.*;
33
34 /**
35 * A 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 */
42 public final class NormalizeBlocksTransformer implements OpTransformer {
43 final Set<Block> mergedBlocks = new HashSet<>();
44 final Map<Block, BitSet> adjustedBlocks = new HashMap<>();
45
46 private NormalizeBlocksTransformer() {
47 }
48
49 /**
50 * Transforms an operation, merging redundant blocks.
51 *
52 * @param op the operation to transform
53 * @param <O> the type of operation
54 * @return the transformed operation
55 */
56 @SuppressWarnings("unchecked")
57 public static <O extends Op> O transform(O op) {
58 return (O) op.transform(CopyContext.create(), new NormalizeBlocksTransformer());
59 }
60
61 ;
62
63 @Override
64 public void apply(Block.Builder block, Block b) {
65 // Ignore merged block
66 if (!mergedBlocks.contains(b)) {
67 OpTransformer.super.apply(block, b);
68 }
69 }
70
71 @Override
72 public Block.Builder apply(Block.Builder b, Op op) {
73 if (op instanceof CoreOp.BranchOp bop &&
74 bop.branch().targetBlock().predecessors().size() == 1) {
75 // Merge the successor's target block with this block, and so on
76 // The terminal branch operation is replaced with the operations in the
77 // successor's target block
78 mergeBlock(b, bop);
79 return b;
80 } else if (op instanceof JavaOp.ExceptionRegionEnter ere) {
81 // Cannot remove block parameters from exception handlers
82 removeUnusedBlockParameters(b, ere.start());
83 } else if (op instanceof JavaOp.ExceptionRegionExit ere) {
84 // Cannot remove block parameters from exception handlers
85 removeUnusedBlockParameters(b, ere.end());
86 } else if (op instanceof Op.BlockTerminating) {
87 for (Block.Reference successor : op.successors()) {
88 removeUnusedBlockParameters(b, successor);
89 }
90 }
91 b.op(op);
92 return b;
93 }
94
95 // Remove any unused block parameters and successor arguments
96 private void removeUnusedBlockParameters(Block.Builder b, Block.Reference successor) {
97 Block target = successor.targetBlock();
98 BitSet unusedParameterIndexes = adjustedBlocks.computeIfAbsent(target,
99 k -> adjustBlock(b, k));
100 if (!unusedParameterIndexes.isEmpty()) {
101 adjustSuccessor(unusedParameterIndexes, b, successor);
102 }
103
104 }
105
106 // Remove any unused block parameters
107 BitSet adjustBlock(Block.Builder b, Block target) {
108 // Determine the indexes of unused block parameters
109 List<Block.Parameter> parameters = target.parameters();
110 BitSet unusedParameterIndexes = parameters.stream()
111 .filter(p -> p.uses().isEmpty())
112 .mapToInt(Block.Parameter::index)
113 .collect(BitSet::new, BitSet::set, BitSet::or);
114
115 if (!unusedParameterIndexes.isEmpty()) {
116 // Create a new output block and remap it to the target block,
117 // overriding any previous mapping
118 Block.Builder adjustedBlock = b.block();
119 b.context().mapBlock(target, adjustedBlock);
120
121 // Update and remap the output block parameters
122 for (int i = 0; i < parameters.size(); i++) {
123 if (!unusedParameterIndexes.get(i)) {
124 Block.Parameter parameter = parameters.get(i);
125 b.context().mapValue(
126 parameter,
127 adjustedBlock.parameter(parameter.type()));
128 }
129 }
130 }
131
132 return unusedParameterIndexes;
133 }
134
135 // Remove any unused successor arguments
136 void adjustSuccessor(BitSet unusedParameterIndexes, Block.Builder b, Block.Reference successor) {
137 // Create a new output successor and remap it
138 List<Value> arguments = new ArrayList<>();
139 for (int i = 0; i < successor.arguments().size(); i++) {
140 if (!unusedParameterIndexes.get(i)) {
141 arguments.add(b.context().getValue(successor.arguments().get(i)));
142 }
143 }
144 Block.Reference adjustedSuccessor = b.context().getBlock(successor.targetBlock())
145 .successor(arguments);
146 b.context().mapSuccessor(successor, adjustedSuccessor);
147 }
148
149 void mergeBlock(Block.Builder b, CoreOp.BranchOp bop) {
150 Block.Reference reference = bop.branch();
151 Block successor = reference.targetBlock();
152 // Replace use of the successor's parameters with the reference's arguments
153 b.context().mapValues(successor.parameters(),
154 b.context().getValues(reference.arguments()));
155 mergeBlock(b, successor);
156 }
157
158 void mergeBlock(Block.Builder b, Block successor) {
159 mergedBlocks.add(successor);
160
161 // Merge non-terminal operations
162 for (int i = 0; i < successor.ops().size() - 1; i++) {
163 b.op(successor.ops().get(i));
164 }
165
166 // Check if subsequent successor block can be normalized
167 apply(b, successor.terminatingOp());
168 }
169 }