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 java.lang.reflect.code.analysis;
27
28 import java.lang.reflect.code.*;
29 import java.lang.reflect.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 Op.BlockTerminating) {
82 for (Block.Reference successor : op.successors()) {
83 removeUnusedBlockParameters(b, successor);
84 }
85 }
86 b.op(op);
87 return b;
88 }
89
90 // Remove any unused block parameters and successor arguments
91 private void removeUnusedBlockParameters(Block.Builder b, Block.Reference successor) {
92 Block target = successor.targetBlock();
93 BitSet unusedParameterIndexes = adjustedBlocks.computeIfAbsent(target,
94 k -> adjustBlock(b, k));
95 if (!unusedParameterIndexes.isEmpty()) {
96 adjustSuccessor(unusedParameterIndexes, b, successor);
97 }
98
99 }
100
101 // Remove any unused block parameters
102 BitSet adjustBlock(Block.Builder b, Block target) {
103 // Determine the indexes of unused block parameters
104 List<Block.Parameter> parameters = target.parameters();
105 BitSet unusedParameterIndexes = parameters.stream()
106 .filter(p -> p.uses().isEmpty())
107 .mapToInt(Block.Parameter::index)
108 .collect(BitSet::new, BitSet::set, BitSet::or);
109
110 if (!unusedParameterIndexes.isEmpty()) {
111 // Create a new output block and remap it to the target block,
112 // overriding any previous mapping
113 Block.Builder adjustedBlock = b.block();
114 b.context().mapBlock(target, adjustedBlock);
115
116 // Update and remap the output block parameters
117 for (int i = 0; i < parameters.size(); i++) {
118 if (!unusedParameterIndexes.get(i)) {
119 Block.Parameter parameter = parameters.get(i);
120 b.context().mapValue(
121 parameter,
122 adjustedBlock.parameter(parameter.type()));
123 }
124 }
125 }
126
127 return unusedParameterIndexes;
128 }
129
130 // Remove any unused successor arguments
131 void adjustSuccessor(BitSet unusedParameterIndexes, Block.Builder b, Block.Reference successor) {
132 // Create a new output successor and remap it
133 List<Value> arguments = new ArrayList<>();
134 for (int i = 0; i < successor.arguments().size(); i++) {
135 if (!unusedParameterIndexes.get(i)) {
136 arguments.add(b.context().getValue(successor.arguments().get(i)));
137 }
138 }
139 Block.Reference adjustedSuccessor = b.context().getBlock(successor.targetBlock())
140 .successor(arguments);
141 b.context().mapSuccessor(successor, adjustedSuccessor);
142 }
143
144 void mergeBlock(Block.Builder b, CoreOp.BranchOp bop) {
145 Block.Reference reference = bop.branch();
146 Block successor = reference.targetBlock();
147 // Replace use of the successor's parameters with the reference's arguments
148 b.context().mapValues(successor.parameters(),
149 b.context().getValues(reference.arguments()));
150 mergeBlock(b, successor);
151 }
152
153 void mergeBlock(Block.Builder b, Block successor) {
154 mergedBlocks.add(successor);
155
156 // Merge non-terminal operations
157 for (int i = 0; i < successor.ops().size() - 1; i++) {
158 b.op(successor.ops().get(i));
159 }
160
161 // Check if subsequent successor block can be normalized
162 apply(b, successor.terminatingOp());
163 }
164 }