18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23 package org.graalvm.compiler.lir.constopt;
24
25 import static org.graalvm.compiler.lir.LIRValueUtil.isVariable;
26 import static org.graalvm.compiler.lir.phases.LIRPhase.Options.LIROptimization;
27
28 import java.util.ArrayDeque;
29 import java.util.ArrayList;
30 import java.util.BitSet;
31 import java.util.Collections;
32 import java.util.Deque;
33 import java.util.EnumSet;
34 import java.util.List;
35
36 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
37 import org.graalvm.compiler.core.common.cfg.BlockMap;
38 import org.graalvm.compiler.debug.Debug;
39 import org.graalvm.compiler.debug.Debug.Scope;
40 import org.graalvm.compiler.debug.DebugCounter;
41 import org.graalvm.compiler.debug.Indent;
42 import org.graalvm.compiler.lir.InstructionValueConsumer;
43 import org.graalvm.compiler.lir.LIR;
44 import org.graalvm.compiler.lir.LIRInsertionBuffer;
45 import org.graalvm.compiler.lir.LIRInstruction;
46 import org.graalvm.compiler.lir.LIRInstruction.OperandFlag;
47 import org.graalvm.compiler.lir.LIRInstruction.OperandMode;
48 import org.graalvm.compiler.lir.StandardOp.LoadConstantOp;
49 import org.graalvm.compiler.lir.ValueConsumer;
50 import org.graalvm.compiler.lir.Variable;
51 import org.graalvm.compiler.lir.constopt.ConstantTree.Flags;
52 import org.graalvm.compiler.lir.constopt.ConstantTree.NodeCost;
53 import org.graalvm.compiler.lir.gen.LIRGenerationResult;
54 import org.graalvm.compiler.lir.gen.LIRGeneratorTool;
55 import org.graalvm.compiler.lir.phases.PreAllocationOptimizationPhase;
56 import org.graalvm.compiler.options.NestedBooleanOptionKey;
57 import org.graalvm.compiler.options.Option;
58 import org.graalvm.compiler.options.OptionType;
59
60 import jdk.vm.ci.code.TargetDescription;
65 /**
66 * This optimization tries to improve the handling of constants by replacing a single definition of
67 * a constant, which is potentially scheduled into a block with high probability, with one or more
68 * definitions in blocks with a lower probability.
69 */
70 public final class ConstantLoadOptimization extends PreAllocationOptimizationPhase {
71
72 public static class Options {
73 // @formatter:off
74 @Option(help = "Enable constant load optimization.", type = OptionType.Debug)
75 public static final NestedBooleanOptionKey LIROptConstantLoadOptimization = new NestedBooleanOptionKey(LIROptimization, true);
76 // @formatter:on
77 }
78
79 @Override
80 protected void run(TargetDescription target, LIRGenerationResult lirGenRes, PreAllocationOptimizationContext context) {
81 LIRGeneratorTool lirGen = context.lirGen;
82 new Optimization(lirGenRes.getLIR(), lirGen).apply();
83 }
84
85 private static final DebugCounter constantsTotal = Debug.counter("ConstantLoadOptimization[total]");
86 private static final DebugCounter phiConstantsSkipped = Debug.counter("ConstantLoadOptimization[PhisSkipped]");
87 private static final DebugCounter singleUsageConstantsSkipped = Debug.counter("ConstantLoadOptimization[SingleUsageSkipped]");
88 private static final DebugCounter usageAtDefinitionSkipped = Debug.counter("ConstantLoadOptimization[UsageAtDefinitionSkipped]");
89 private static final DebugCounter materializeAtDefinitionSkipped = Debug.counter("ConstantLoadOptimization[MaterializeAtDefinitionSkipped]");
90 private static final DebugCounter constantsOptimized = Debug.counter("ConstantLoadOptimization[optimized]");
91
92 private static final class Optimization {
93 private final LIR lir;
94 private final LIRGeneratorTool lirGen;
95 private final VariableMap<DefUseTree> map;
96 private final BitSet phiConstants;
97 private final BitSet defined;
98 private final BlockMap<List<UseEntry>> blockMap;
99 private final BlockMap<LIRInsertionBuffer> insertionBuffers;
100
101 private Optimization(LIR lir, LIRGeneratorTool lirGen) {
102 this.lir = lir;
103 this.lirGen = lirGen;
104 this.map = new VariableMap<>();
105 this.phiConstants = new BitSet();
106 this.defined = new BitSet();
107 this.insertionBuffers = new BlockMap<>(lir.getControlFlowGraph());
108 this.blockMap = new BlockMap<>(lir.getControlFlowGraph());
109 }
110
111 @SuppressWarnings("try")
112 private void apply() {
113 try (Indent indent = Debug.logAndIndent("ConstantLoadOptimization")) {
114 try (Scope s = Debug.scope("BuildDefUseTree")) {
115 // build DefUseTree
116 for (AbstractBlockBase<?> b : lir.getControlFlowGraph().getBlocks()) {
117 this.analyzeBlock(b);
118 }
119 // remove all with only one use
120 map.filter(t -> {
121 if (t.usageCount() > 1) {
122 return true;
123 } else {
124 singleUsageConstantsSkipped.increment();
125 return false;
126 }
127 });
128 // collect block map
129 map.forEach(tree -> tree.forEach(this::addUsageToBlockMap));
130 } catch (Throwable e) {
131 throw Debug.handle(e);
132 }
133
134 try (Scope s = Debug.scope("BuildConstantTree")) {
135 // create ConstantTree
136 map.forEach(this::createConstantTree);
137
138 // insert moves, delete null instructions and reset instruction ids
139 for (AbstractBlockBase<?> b : lir.getControlFlowGraph().getBlocks()) {
140 this.rewriteBlock(b);
141 }
142
143 assert verifyStates();
144 } catch (Throwable e) {
145 throw Debug.handle(e);
146 }
147 }
148 }
149
150 private boolean verifyStates() {
151 map.forEach(this::verifyStateUsage);
152 return true;
153 }
154
155 private void verifyStateUsage(DefUseTree tree) {
156 Variable var = tree.getVariable();
157 ValueConsumer stateConsumer = new ValueConsumer() {
158
159 @Override
160 public void visitValue(Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
161 assert !operand.equals(var) : "constant usage through variable in frame state " + var;
162 }
163 };
164 for (AbstractBlockBase<?> block : lir.getControlFlowGraph().getBlocks()) {
165 for (LIRInstruction inst : lir.getLIRforBlock(block)) {
174 return false;
175 }
176 return isVariable(LoadConstantOp.asLoadConstantOp(inst).getResult());
177 }
178
179 private void addUsageToBlockMap(UseEntry entry) {
180 AbstractBlockBase<?> block = entry.getBlock();
181 List<UseEntry> list = blockMap.get(block);
182 if (list == null) {
183 list = new ArrayList<>();
184 blockMap.put(block, list);
185 }
186 list.add(entry);
187 }
188
189 /**
190 * Collects def-use information for a {@code block}.
191 */
192 @SuppressWarnings("try")
193 private void analyzeBlock(AbstractBlockBase<?> block) {
194 try (Indent indent = Debug.logAndIndent("Block: %s", block)) {
195
196 InstructionValueConsumer loadConsumer = (instruction, value, mode, flags) -> {
197 if (isVariable(value)) {
198 Variable var = (Variable) value;
199
200 if (!phiConstants.get(var.index)) {
201 if (!defined.get(var.index)) {
202 defined.set(var.index);
203 if (isConstantLoad(instruction)) {
204 Debug.log("constant load: %s", instruction);
205 map.put(var, new DefUseTree(instruction, block));
206 constantsTotal.increment();
207 }
208 } else {
209 // Variable is redefined, this only happens for constant loads
210 // introduced by phi resolution -> ignore.
211 DefUseTree removed = map.remove(var);
212 if (removed != null) {
213 phiConstantsSkipped.increment();
214 }
215 phiConstants.set(var.index);
216 Debug.log(Debug.VERBOSE_LEVEL, "Removing phi variable: %s", var);
217 }
218 } else {
219 assert defined.get(var.index) : "phi but not defined? " + var;
220 }
221 }
222 };
223
224 InstructionValueConsumer useConsumer = (instruction, value, mode, flags) -> {
225 if (isVariable(value)) {
226 Variable var = (Variable) value;
227 if (!phiConstants.get(var.index)) {
228 DefUseTree tree = map.get(var);
229 if (tree != null) {
230 tree.addUsage(block, instruction, value);
231 Debug.log("usage of %s : %s", var, instruction);
232 }
233 }
234 }
235 };
236
237 int opId = 0;
238 for (LIRInstruction inst : lir.getLIRforBlock(block)) {
239 // set instruction id to the index in the lir instruction list
240 inst.setId(opId++);
241 inst.visitEachOutput(loadConsumer);
242 inst.visitEachInput(useConsumer);
243 inst.visitEachAlive(useConsumer);
244
245 }
246 }
247 }
248
249 /**
250 * Creates the dominator tree and searches for an solution.
251 */
252 @SuppressWarnings("try")
253 private void createConstantTree(DefUseTree tree) {
254 ConstantTree constTree = new ConstantTree(lir.getControlFlowGraph(), tree);
255 constTree.set(Flags.SUBTREE, tree.getBlock());
256 tree.forEach(u -> constTree.set(Flags.USAGE, u.getBlock()));
257
258 if (constTree.get(Flags.USAGE, tree.getBlock())) {
259 // usage in the definition block -> no optimization
260 usageAtDefinitionSkipped.increment();
261 return;
262 }
263
264 constTree.markBlocks();
265
266 NodeCost cost = ConstantTreeAnalyzer.analyze(constTree, tree.getBlock());
267 int usageCount = cost.getUsages().size();
268 assert usageCount == tree.usageCount() : "Usage count differs: " + usageCount + " vs. " + tree.usageCount();
269
270 if (Debug.isLogEnabled()) {
271 try (Indent i = Debug.logAndIndent("Variable: %s, Block: %s, prob.: %f", tree.getVariable(), tree.getBlock(), tree.getBlock().probability())) {
272 Debug.log("Usages result: %s", cost);
273 }
274
275 }
276
277 if (cost.getNumMaterializations() > 1 || cost.getBestCost() < tree.getBlock().probability()) {
278 try (Scope s = Debug.scope("CLOmodify", constTree); Indent i = Debug.logAndIndent("Replacing %s = %s", tree.getVariable(), tree.getConstant().toValueString())) {
279 // mark original load for removal
280 deleteInstruction(tree);
281 constantsOptimized.increment();
282
283 // collect result
284 createLoads(tree, constTree, tree.getBlock());
285
286 } catch (Throwable e) {
287 throw Debug.handle(e);
288 }
289 } else {
290 // no better solution found
291 materializeAtDefinitionSkipped.increment();
292 }
293 Debug.dump(Debug.DETAILED_LEVEL, constTree, "ConstantTree for %s", tree.getVariable());
294 }
295
296 private void createLoads(DefUseTree tree, ConstantTree constTree, AbstractBlockBase<?> startBlock) {
297 Deque<AbstractBlockBase<?>> worklist = new ArrayDeque<>();
298 worklist.add(startBlock);
299 while (!worklist.isEmpty()) {
300 AbstractBlockBase<?> block = worklist.pollLast();
301 if (constTree.get(Flags.CANDIDATE, block)) {
302 constTree.set(Flags.MATERIALIZE, block);
303 // create and insert load
304 insertLoad(tree.getConstant(), tree.getVariable().getValueKind(), block, constTree.getCost(block).getUsages());
305 } else {
306 AbstractBlockBase<?> dominated = block.getFirstDominated();
307 while (dominated != null) {
308 if (constTree.isMarked(dominated)) {
309 worklist.addLast(dominated);
310 }
311 dominated = dominated.getDominatedSibling();
312 }
313 }
314 }
315 }
316
317 private void insertLoad(Constant constant, ValueKind<?> kind, AbstractBlockBase<?> block, List<UseEntry> usages) {
318 assert usages != null && usages.size() > 0 : String.format("No usages %s %s %s", constant, block, usages);
319 // create variable
320 Variable variable = lirGen.newVariable(kind);
321 // create move
322 LIRInstruction move = lirGen.getSpillMoveFactory().createLoad(variable, constant);
323 // insert instruction
324 getInsertionBuffer(block).append(1, move);
325 Debug.log("new move (%s) and inserted in block %s", move, block);
326 // update usages
327 for (UseEntry u : usages) {
328 u.setValue(variable);
329 Debug.log("patched instruction %s", u.getInstruction());
330 }
331 }
332
333 /**
334 * Inserts the constant loads created in {@link #createConstantTree} and deletes the
335 * original definition.
336 */
337 private void rewriteBlock(AbstractBlockBase<?> block) {
338 // insert moves
339 LIRInsertionBuffer buffer = insertionBuffers.get(block);
340 if (buffer != null) {
341 assert buffer.initialized() : "not initialized?";
342 buffer.finish();
343 }
344
345 // delete instructions
346 ArrayList<LIRInstruction> instructions = lir.getLIRforBlock(block);
347 boolean hasDead = false;
348 for (LIRInstruction inst : instructions) {
349 if (inst == null) {
350 hasDead = true;
351 } else {
352 inst.setId(-1);
353 }
354 }
355 if (hasDead) {
356 // Remove null values from the list.
357 instructions.removeAll(Collections.singleton(null));
358 }
359 }
360
361 private void deleteInstruction(DefUseTree tree) {
362 AbstractBlockBase<?> block = tree.getBlock();
363 LIRInstruction instruction = tree.getInstruction();
364 Debug.log("deleting instruction %s from block %s", instruction, block);
365 lir.getLIRforBlock(block).set(instruction.id(), null);
366 }
367
368 private LIRInsertionBuffer getInsertionBuffer(AbstractBlockBase<?> block) {
369 LIRInsertionBuffer insertionBuffer = insertionBuffers.get(block);
370 if (insertionBuffer == null) {
371 insertionBuffer = new LIRInsertionBuffer();
372 insertionBuffers.put(block, insertionBuffer);
373 assert !insertionBuffer.initialized() : "already initialized?";
374 ArrayList<LIRInstruction> instructions = lir.getLIRforBlock(block);
375 insertionBuffer.init(instructions);
376 }
377 return insertionBuffer;
378 }
379 }
380 }
|
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23 package org.graalvm.compiler.lir.constopt;
24
25 import static org.graalvm.compiler.lir.LIRValueUtil.isVariable;
26 import static org.graalvm.compiler.lir.phases.LIRPhase.Options.LIROptimization;
27
28 import java.util.ArrayDeque;
29 import java.util.ArrayList;
30 import java.util.BitSet;
31 import java.util.Collections;
32 import java.util.Deque;
33 import java.util.EnumSet;
34 import java.util.List;
35
36 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
37 import org.graalvm.compiler.core.common.cfg.BlockMap;
38 import org.graalvm.compiler.debug.CounterKey;
39 import org.graalvm.compiler.debug.DebugContext;
40 import org.graalvm.compiler.debug.Indent;
41 import org.graalvm.compiler.lir.InstructionValueConsumer;
42 import org.graalvm.compiler.lir.LIR;
43 import org.graalvm.compiler.lir.LIRInsertionBuffer;
44 import org.graalvm.compiler.lir.LIRInstruction;
45 import org.graalvm.compiler.lir.LIRInstruction.OperandFlag;
46 import org.graalvm.compiler.lir.LIRInstruction.OperandMode;
47 import org.graalvm.compiler.lir.StandardOp.LoadConstantOp;
48 import org.graalvm.compiler.lir.ValueConsumer;
49 import org.graalvm.compiler.lir.Variable;
50 import org.graalvm.compiler.lir.constopt.ConstantTree.Flags;
51 import org.graalvm.compiler.lir.constopt.ConstantTree.NodeCost;
52 import org.graalvm.compiler.lir.gen.LIRGenerationResult;
53 import org.graalvm.compiler.lir.gen.LIRGeneratorTool;
54 import org.graalvm.compiler.lir.phases.PreAllocationOptimizationPhase;
55 import org.graalvm.compiler.options.NestedBooleanOptionKey;
56 import org.graalvm.compiler.options.Option;
57 import org.graalvm.compiler.options.OptionType;
58
59 import jdk.vm.ci.code.TargetDescription;
64 /**
65 * This optimization tries to improve the handling of constants by replacing a single definition of
66 * a constant, which is potentially scheduled into a block with high probability, with one or more
67 * definitions in blocks with a lower probability.
68 */
69 public final class ConstantLoadOptimization extends PreAllocationOptimizationPhase {
70
71 public static class Options {
72 // @formatter:off
73 @Option(help = "Enable constant load optimization.", type = OptionType.Debug)
74 public static final NestedBooleanOptionKey LIROptConstantLoadOptimization = new NestedBooleanOptionKey(LIROptimization, true);
75 // @formatter:on
76 }
77
78 @Override
79 protected void run(TargetDescription target, LIRGenerationResult lirGenRes, PreAllocationOptimizationContext context) {
80 LIRGeneratorTool lirGen = context.lirGen;
81 new Optimization(lirGenRes.getLIR(), lirGen).apply();
82 }
83
84 private static final CounterKey constantsTotal = DebugContext.counter("ConstantLoadOptimization[total]");
85 private static final CounterKey phiConstantsSkipped = DebugContext.counter("ConstantLoadOptimization[PhisSkipped]");
86 private static final CounterKey singleUsageConstantsSkipped = DebugContext.counter("ConstantLoadOptimization[SingleUsageSkipped]");
87 private static final CounterKey usageAtDefinitionSkipped = DebugContext.counter("ConstantLoadOptimization[UsageAtDefinitionSkipped]");
88 private static final CounterKey materializeAtDefinitionSkipped = DebugContext.counter("ConstantLoadOptimization[MaterializeAtDefinitionSkipped]");
89 private static final CounterKey constantsOptimized = DebugContext.counter("ConstantLoadOptimization[optimized]");
90
91 private static final class Optimization {
92 private final LIR lir;
93 private final LIRGeneratorTool lirGen;
94 private final VariableMap<DefUseTree> map;
95 private final BitSet phiConstants;
96 private final BitSet defined;
97 private final BlockMap<List<UseEntry>> blockMap;
98 private final BlockMap<LIRInsertionBuffer> insertionBuffers;
99 private final DebugContext debug;
100
101 private Optimization(LIR lir, LIRGeneratorTool lirGen) {
102 this.lir = lir;
103 this.debug = lir.getDebug();
104 this.lirGen = lirGen;
105 this.map = new VariableMap<>();
106 this.phiConstants = new BitSet();
107 this.defined = new BitSet();
108 this.insertionBuffers = new BlockMap<>(lir.getControlFlowGraph());
109 this.blockMap = new BlockMap<>(lir.getControlFlowGraph());
110 }
111
112 @SuppressWarnings("try")
113 private void apply() {
114 try (Indent indent = debug.logAndIndent("ConstantLoadOptimization")) {
115 try (DebugContext.Scope s = debug.scope("BuildDefUseTree")) {
116 // build DefUseTree
117 for (AbstractBlockBase<?> b : lir.getControlFlowGraph().getBlocks()) {
118 this.analyzeBlock(b);
119 }
120 // remove all with only one use
121 map.filter(t -> {
122 if (t.usageCount() > 1) {
123 return true;
124 } else {
125 singleUsageConstantsSkipped.increment(debug);
126 return false;
127 }
128 });
129 // collect block map
130 map.forEach(tree -> tree.forEach(this::addUsageToBlockMap));
131 } catch (Throwable e) {
132 throw debug.handle(e);
133 }
134
135 try (DebugContext.Scope s = debug.scope("BuildConstantTree")) {
136 // create ConstantTree
137 map.forEach(this::createConstantTree);
138
139 // insert moves, delete null instructions and reset instruction ids
140 for (AbstractBlockBase<?> b : lir.getControlFlowGraph().getBlocks()) {
141 this.rewriteBlock(b);
142 }
143
144 assert verifyStates();
145 } catch (Throwable e) {
146 throw debug.handle(e);
147 }
148 }
149 }
150
151 private boolean verifyStates() {
152 map.forEach(this::verifyStateUsage);
153 return true;
154 }
155
156 private void verifyStateUsage(DefUseTree tree) {
157 Variable var = tree.getVariable();
158 ValueConsumer stateConsumer = new ValueConsumer() {
159
160 @Override
161 public void visitValue(Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
162 assert !operand.equals(var) : "constant usage through variable in frame state " + var;
163 }
164 };
165 for (AbstractBlockBase<?> block : lir.getControlFlowGraph().getBlocks()) {
166 for (LIRInstruction inst : lir.getLIRforBlock(block)) {
175 return false;
176 }
177 return isVariable(LoadConstantOp.asLoadConstantOp(inst).getResult());
178 }
179
180 private void addUsageToBlockMap(UseEntry entry) {
181 AbstractBlockBase<?> block = entry.getBlock();
182 List<UseEntry> list = blockMap.get(block);
183 if (list == null) {
184 list = new ArrayList<>();
185 blockMap.put(block, list);
186 }
187 list.add(entry);
188 }
189
190 /**
191 * Collects def-use information for a {@code block}.
192 */
193 @SuppressWarnings("try")
194 private void analyzeBlock(AbstractBlockBase<?> block) {
195 try (Indent indent = debug.logAndIndent("Block: %s", block)) {
196
197 InstructionValueConsumer loadConsumer = (instruction, value, mode, flags) -> {
198 if (isVariable(value)) {
199 Variable var = (Variable) value;
200
201 if (!phiConstants.get(var.index)) {
202 if (!defined.get(var.index)) {
203 defined.set(var.index);
204 if (isConstantLoad(instruction)) {
205 debug.log("constant load: %s", instruction);
206 map.put(var, new DefUseTree(instruction, block));
207 constantsTotal.increment(debug);
208 }
209 } else {
210 // Variable is redefined, this only happens for constant loads
211 // introduced by phi resolution -> ignore.
212 DefUseTree removed = map.remove(var);
213 if (removed != null) {
214 phiConstantsSkipped.increment(debug);
215 }
216 phiConstants.set(var.index);
217 debug.log(DebugContext.VERBOSE_LEVEL, "Removing phi variable: %s", var);
218 }
219 } else {
220 assert defined.get(var.index) : "phi but not defined? " + var;
221 }
222 }
223 };
224
225 InstructionValueConsumer useConsumer = (instruction, value, mode, flags) -> {
226 if (isVariable(value)) {
227 Variable var = (Variable) value;
228 if (!phiConstants.get(var.index)) {
229 DefUseTree tree = map.get(var);
230 if (tree != null) {
231 tree.addUsage(block, instruction, value);
232 debug.log("usage of %s : %s", var, instruction);
233 }
234 }
235 }
236 };
237
238 int opId = 0;
239 for (LIRInstruction inst : lir.getLIRforBlock(block)) {
240 // set instruction id to the index in the lir instruction list
241 inst.setId(opId++);
242 inst.visitEachOutput(loadConsumer);
243 inst.visitEachInput(useConsumer);
244 inst.visitEachAlive(useConsumer);
245
246 }
247 }
248 }
249
250 /**
251 * Creates the dominator tree and searches for an solution.
252 */
253 @SuppressWarnings("try")
254 private void createConstantTree(DefUseTree tree) {
255 ConstantTree constTree = new ConstantTree(lir.getControlFlowGraph(), tree);
256 constTree.set(Flags.SUBTREE, tree.getBlock());
257 tree.forEach(u -> constTree.set(Flags.USAGE, u.getBlock()));
258
259 if (constTree.get(Flags.USAGE, tree.getBlock())) {
260 // usage in the definition block -> no optimization
261 usageAtDefinitionSkipped.increment(debug);
262 return;
263 }
264
265 constTree.markBlocks();
266
267 NodeCost cost = ConstantTreeAnalyzer.analyze(debug, constTree, tree.getBlock());
268 int usageCount = cost.getUsages().size();
269 assert usageCount == tree.usageCount() : "Usage count differs: " + usageCount + " vs. " + tree.usageCount();
270
271 if (debug.isLogEnabled()) {
272 try (Indent i = debug.logAndIndent("Variable: %s, Block: %s, prob.: %f", tree.getVariable(), tree.getBlock(), tree.getBlock().probability())) {
273 debug.log("Usages result: %s", cost);
274 }
275
276 }
277
278 if (cost.getNumMaterializations() > 1 || cost.getBestCost() < tree.getBlock().probability()) {
279 try (DebugContext.Scope s = debug.scope("CLOmodify", constTree); Indent i = debug.logAndIndent("Replacing %s = %s", tree.getVariable(), tree.getConstant().toValueString())) {
280 // mark original load for removal
281 deleteInstruction(tree);
282 constantsOptimized.increment(debug);
283
284 // collect result
285 createLoads(tree, constTree, tree.getBlock());
286
287 } catch (Throwable e) {
288 throw debug.handle(e);
289 }
290 } else {
291 // no better solution found
292 materializeAtDefinitionSkipped.increment(debug);
293 }
294 debug.dump(DebugContext.DETAILED_LEVEL, constTree, "ConstantTree for %s", tree.getVariable());
295 }
296
297 private void createLoads(DefUseTree tree, ConstantTree constTree, AbstractBlockBase<?> startBlock) {
298 Deque<AbstractBlockBase<?>> worklist = new ArrayDeque<>();
299 worklist.add(startBlock);
300 while (!worklist.isEmpty()) {
301 AbstractBlockBase<?> block = worklist.pollLast();
302 if (constTree.get(Flags.CANDIDATE, block)) {
303 constTree.set(Flags.MATERIALIZE, block);
304 // create and insert load
305 insertLoad(tree.getConstant(), tree.getVariable().getValueKind(), block, constTree.getCost(block).getUsages());
306 } else {
307 AbstractBlockBase<?> dominated = block.getFirstDominated();
308 while (dominated != null) {
309 if (constTree.isMarked(dominated)) {
310 worklist.addLast(dominated);
311 }
312 dominated = dominated.getDominatedSibling();
313 }
314 }
315 }
316 }
317
318 private void insertLoad(Constant constant, ValueKind<?> kind, AbstractBlockBase<?> block, List<UseEntry> usages) {
319 assert usages != null && usages.size() > 0 : String.format("No usages %s %s %s", constant, block, usages);
320 // create variable
321 Variable variable = lirGen.newVariable(kind);
322 // create move
323 LIRInstruction move = lirGen.getSpillMoveFactory().createLoad(variable, constant);
324 // insert instruction
325 getInsertionBuffer(block).append(1, move);
326 debug.log("new move (%s) and inserted in block %s", move, block);
327 // update usages
328 for (UseEntry u : usages) {
329 u.setValue(variable);
330 debug.log("patched instruction %s", u.getInstruction());
331 }
332 }
333
334 /**
335 * Inserts the constant loads created in {@link #createConstantTree} and deletes the
336 * original definition.
337 */
338 private void rewriteBlock(AbstractBlockBase<?> block) {
339 // insert moves
340 LIRInsertionBuffer buffer = insertionBuffers.get(block);
341 if (buffer != null) {
342 assert buffer.initialized() : "not initialized?";
343 buffer.finish();
344 }
345
346 // delete instructions
347 ArrayList<LIRInstruction> instructions = lir.getLIRforBlock(block);
348 boolean hasDead = false;
349 for (LIRInstruction inst : instructions) {
350 if (inst == null) {
351 hasDead = true;
352 } else {
353 inst.setId(-1);
354 }
355 }
356 if (hasDead) {
357 // Remove null values from the list.
358 instructions.removeAll(Collections.singleton(null));
359 }
360 }
361
362 private void deleteInstruction(DefUseTree tree) {
363 AbstractBlockBase<?> block = tree.getBlock();
364 LIRInstruction instruction = tree.getInstruction();
365 debug.log("deleting instruction %s from block %s", instruction, block);
366 lir.getLIRforBlock(block).set(instruction.id(), null);
367 }
368
369 private LIRInsertionBuffer getInsertionBuffer(AbstractBlockBase<?> block) {
370 LIRInsertionBuffer insertionBuffer = insertionBuffers.get(block);
371 if (insertionBuffer == null) {
372 insertionBuffer = new LIRInsertionBuffer();
373 insertionBuffers.put(block, insertionBuffer);
374 assert !insertionBuffer.initialized() : "already initialized?";
375 ArrayList<LIRInstruction> instructions = lir.getLIRforBlock(block);
376 insertionBuffer.init(instructions);
377 }
378 return insertionBuffer;
379 }
380 }
381 }
|