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