1 /*
2 * Copyright (c) 2014, 2015, 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.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
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;
61 import jdk.vm.ci.meta.Constant;
62 import jdk.vm.ci.meta.Value;
63 import jdk.vm.ci.meta.ValueKind;
64
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)) {
166 // set instruction id to the index in the lir instruction list
167 inst.visitEachState(stateConsumer);
168 }
169 }
170 }
171
172 private static boolean isConstantLoad(LIRInstruction inst) {
173 if (!LoadConstantOp.isLoadConstantOp(inst)) {
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 }