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