Source code

001/*
002 * Copyright (c) 2014, 2014, Oracle and/or its affiliates. All rights reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation.
008 *
009 * This code is distributed in the hope that it will be useful, but WITHOUT
010 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
011 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
012 * version 2 for more details (a copy is included in the LICENSE file that
013 * accompanied this code).
014 *
015 * You should have received a copy of the GNU General Public License version
016 * 2 along with this work; if not, write to the Free Software Foundation,
017 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
018 *
019 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
020 * or visit www.oracle.com if you need additional information or have any
021 * questions.
022 */
023package com.oracle.graal.lir.constopt;
024
025import static com.oracle.graal.lir.LIRValueUtil.*;
026import static com.oracle.graal.lir.phases.LIRPhase.Options.*;
027import static jdk.internal.jvmci.code.ValueUtil.*;
028
029import java.util.*;
030
031import jdk.internal.jvmci.code.*;
032import com.oracle.graal.debug.*;
033import com.oracle.graal.debug.Debug.*;
034import jdk.internal.jvmci.meta.*;
035import jdk.internal.jvmci.options.*;
036
037import com.oracle.graal.compiler.common.cfg.*;
038import com.oracle.graal.lir.*;
039import com.oracle.graal.lir.LIRInstruction.OperandFlag;
040import com.oracle.graal.lir.LIRInstruction.OperandMode;
041import com.oracle.graal.lir.StandardOp.MoveOp;
042import com.oracle.graal.lir.constopt.ConstantTree.Flags;
043import com.oracle.graal.lir.constopt.ConstantTree.NodeCost;
044import com.oracle.graal.lir.gen.*;
045import com.oracle.graal.lir.phases.*;
046
047/**
048 * This optimization tries to improve the handling of constants by replacing a single definition of
049 * a constant, which is potentially scheduled into a block with high probability, with one or more
050 * definitions in blocks with a lower probability.
051 */
052public final class ConstantLoadOptimization extends PreAllocationOptimizationPhase {
053
054    public static class Options {
055        // @formatter:off
056        @Option(help = "Enable constant load optimization.", type = OptionType.Debug)
057        public static final NestedBooleanOptionValue LIROptConstantLoadOptimization = new NestedBooleanOptionValue(LIROptimization, true);
058        // @formatter:on
059    }
060
061    @Override
062    protected <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, LIRGeneratorTool lirGen) {
063        new Optimization(lirGenRes.getLIR(), lirGen).apply();
064    }
065
066    private static final DebugMetric constantsTotal = Debug.metric("ConstantLoadOptimization[total]");
067    private static final DebugMetric phiConstantsSkipped = Debug.metric("ConstantLoadOptimization[PhisSkipped]");
068    private static final DebugMetric singleUsageConstantsSkipped = Debug.metric("ConstantLoadOptimization[SingleUsageSkipped]");
069    private static final DebugMetric usageAtDefinitionSkipped = Debug.metric("ConstantLoadOptimization[UsageAtDefinitionSkipped]");
070    private static final DebugMetric materializeAtDefinitionSkipped = Debug.metric("ConstantLoadOptimization[MaterializeAtDefinitionSkipped]");
071    private static final DebugMetric constantsOptimized = Debug.metric("ConstantLoadOptimization[optimized]");
072
073    private static final class Optimization {
074        private final LIR lir;
075        private final LIRGeneratorTool lirGen;
076        private final VariableMap<DefUseTree> map;
077        private final BitSet phiConstants;
078        private final BitSet defined;
079        private final BlockMap<List<UseEntry>> blockMap;
080        private final BlockMap<LIRInsertionBuffer> insertionBuffers;
081
082        private Optimization(LIR lir, LIRGeneratorTool lirGen) {
083            this.lir = lir;
084            this.lirGen = lirGen;
085            this.map = new VariableMap<>();
086            this.phiConstants = new BitSet();
087            this.defined = new BitSet();
088            this.insertionBuffers = new BlockMap<>(lir.getControlFlowGraph());
089            this.blockMap = new BlockMap<>(lir.getControlFlowGraph());
090        }
091
092        private void apply() {
093            try (Indent indent = Debug.logAndIndent("ConstantLoadOptimization")) {
094                try (Scope s = Debug.scope("BuildDefUseTree")) {
095                    // build DefUseTree
096                    lir.getControlFlowGraph().getBlocks().forEach(this::analyzeBlock);
097                    // remove all with only one use
098                    map.filter(t -> {
099                        if (t.usageCount() > 1) {
100                            return true;
101                        } else {
102                            singleUsageConstantsSkipped.increment();
103                            return false;
104                        }
105                    });
106                    // collect block map
107                    map.forEach(tree -> tree.forEach(this::addUsageToBlockMap));
108                } catch (Throwable e) {
109                    throw Debug.handle(e);
110                }
111
112                try (Scope s = Debug.scope("BuildConstantTree")) {
113                    // create ConstantTree
114                    map.forEach(this::createConstantTree);
115
116                    // insert moves, delete null instructions and reset instruction ids
117                    lir.getControlFlowGraph().getBlocks().forEach(this::rewriteBlock);
118
119                    assert verifyStates();
120                } catch (Throwable e) {
121                    throw Debug.handle(e);
122                }
123            }
124        }
125
126        private boolean verifyStates() {
127            map.forEach(this::verifyStateUsage);
128            return true;
129        }
130
131        private void verifyStateUsage(DefUseTree tree) {
132            Variable var = tree.getVariable();
133            ValueConsumer stateConsumer = new ValueConsumer() {
134
135                @Override
136                public void visitValue(Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
137                    assert !operand.equals(var) : "constant usage through variable in frame state " + var;
138                }
139            };
140            for (AbstractBlockBase<?> block : lir.getControlFlowGraph().getBlocks()) {
141                for (LIRInstruction inst : lir.getLIRforBlock(block)) {
142                    // set instruction id to the index in the lir instruction list
143                    inst.visitEachState(stateConsumer);
144                }
145            }
146        }
147
148        private static boolean isConstantLoad(LIRInstruction inst) {
149            if (!(inst instanceof MoveOp)) {
150                return false;
151            }
152            MoveOp move = (MoveOp) inst;
153            return isConstant(move.getInput()) && isVariable(move.getResult());
154        }
155
156        private void addUsageToBlockMap(UseEntry entry) {
157            AbstractBlockBase<?> block = entry.getBlock();
158            List<UseEntry> list = blockMap.get(block);
159            if (list == null) {
160                list = new ArrayList<>();
161                blockMap.put(block, list);
162            }
163            list.add(entry);
164        }
165
166        /**
167         * Collects def-use information for a {@code block}.
168         */
169        private void analyzeBlock(AbstractBlockBase<?> block) {
170            try (Indent indent = Debug.logAndIndent("Block: %s", block)) {
171
172                InstructionValueConsumer loadConsumer = (instruction, value, mode, flags) -> {
173                    if (isVariable(value)) {
174                        Variable var = (Variable) value;
175
176                        if (!phiConstants.get(var.index)) {
177                            if (!defined.get(var.index)) {
178                                defined.set(var.index);
179                                if (isConstantLoad(instruction)) {
180                                    Debug.log("constant load: %s", instruction);
181                                    map.put(var, new DefUseTree(instruction, block));
182                                    constantsTotal.increment();
183                                }
184                            } else {
185                                // Variable is redefined, this only happens for constant loads
186                                // introduced by phi resolution -> ignore.
187                                DefUseTree removed = map.remove(var);
188                                if (removed != null) {
189                                    phiConstantsSkipped.increment();
190                                }
191                                phiConstants.set(var.index);
192                                Debug.log(3, "Removing phi variable: %s", var);
193                            }
194                        } else {
195                            assert defined.get(var.index) : "phi but not defined? " + var;
196                        }
197                    }
198                };
199
200                InstructionValueConsumer useConsumer = (instruction, value, mode, flags) -> {
201                    if (isVariable(value)) {
202                        Variable var = (Variable) value;
203                        if (!phiConstants.get(var.index)) {
204                            DefUseTree tree = map.get(var);
205                            if (tree != null) {
206                                tree.addUsage(block, instruction, value);
207                                Debug.log("usage of %s : %s", var, instruction);
208                            }
209                        }
210                    }
211                };
212
213                int opId = 0;
214                for (LIRInstruction inst : lir.getLIRforBlock(block)) {
215                    // set instruction id to the index in the lir instruction list
216                    inst.setId(opId++);
217                    inst.visitEachOutput(loadConsumer);
218                    inst.visitEachInput(useConsumer);
219                    inst.visitEachAlive(useConsumer);
220
221                }
222            }
223        }
224
225        /**
226         * Creates the dominator tree and searches for an solution.
227         */
228        private void createConstantTree(DefUseTree tree) {
229            ConstantTree constTree = new ConstantTree(lir.getControlFlowGraph(), tree);
230            constTree.set(Flags.SUBTREE, tree.getBlock());
231            tree.forEach(u -> constTree.set(Flags.USAGE, u.getBlock()));
232
233            if (constTree.get(Flags.USAGE, tree.getBlock())) {
234                // usage in the definition block -> no optimization
235                usageAtDefinitionSkipped.increment();
236                return;
237            }
238
239            constTree.markBlocks();
240
241            NodeCost cost = ConstantTreeAnalyzer.analyze(constTree, tree.getBlock());
242            int usageCount = cost.getUsages().size();
243            assert usageCount == tree.usageCount() : "Usage count differs: " + usageCount + " vs. " + tree.usageCount();
244
245            if (Debug.isLogEnabled()) {
246                try (Indent i = Debug.logAndIndent("Variable: %s, Block: %s, prob.: %f", tree.getVariable(), tree.getBlock(), tree.getBlock().probability())) {
247                    Debug.log("Usages result: %s", cost);
248                }
249
250            }
251
252            if (cost.getNumMaterializations() > 1 || cost.getBestCost() < tree.getBlock().probability()) {
253                try (Scope s = Debug.scope("CLOmodify", constTree); Indent i = Debug.logAndIndent("Replacing %s = %s", tree.getVariable(), tree.getConstant().toValueString())) {
254                    // mark original load for removal
255                    deleteInstruction(tree);
256                    constantsOptimized.increment();
257
258                    // collect result
259                    createLoads(tree, constTree, tree.getBlock());
260
261                } catch (Throwable e) {
262                    throw Debug.handle(e);
263                }
264            } else {
265                // no better solution found
266                materializeAtDefinitionSkipped.increment();
267            }
268            Debug.dump(constTree, "ConstantTree for " + tree.getVariable());
269        }
270
271        private void createLoads(DefUseTree tree, ConstantTree constTree, AbstractBlockBase<?> startBlock) {
272            Deque<AbstractBlockBase<?>> worklist = new ArrayDeque<>();
273            worklist.add(startBlock);
274            while (!worklist.isEmpty()) {
275                AbstractBlockBase<?> block = worklist.pollLast();
276                if (constTree.get(Flags.CANDIDATE, block)) {
277                    constTree.set(Flags.MATERIALIZE, block);
278                    // create and insert load
279                    insertLoad(tree.getConstant(), tree.getVariable().getLIRKind(), block, constTree.getCost(block).getUsages());
280                } else {
281                    for (AbstractBlockBase<?> dominated : block.getDominated()) {
282                        if (constTree.isMarked(dominated)) {
283                            worklist.addLast(dominated);
284                        }
285                    }
286                }
287            }
288        }
289
290        private void insertLoad(JavaConstant constant, LIRKind kind, AbstractBlockBase<?> block, List<UseEntry> usages) {
291            assert usages != null && usages.size() > 0 : String.format("No usages %s %s %s", constant, block, usages);
292            // create variable
293            Variable variable = lirGen.newVariable(kind);
294            // create move
295            LIRInstruction move = lirGen.getSpillMoveFactory().createMove(variable, constant);
296            // insert instruction
297            getInsertionBuffer(block).append(1, move);
298            Debug.log("new move (%s) and inserted in block %s", move, block);
299            // update usages
300            for (UseEntry u : usages) {
301                u.setValue(variable);
302                Debug.log("patched instruction %s", u.getInstruction());
303            }
304        }
305
306        /**
307         * Inserts the constant loads created in {@link #createConstantTree} and deletes the
308         * original definition.
309         */
310        private void rewriteBlock(AbstractBlockBase<?> block) {
311            // insert moves
312            LIRInsertionBuffer buffer = insertionBuffers.get(block);
313            if (buffer != null) {
314                assert buffer.initialized() : "not initialized?";
315                buffer.finish();
316            }
317
318            // delete instructions
319            List<LIRInstruction> instructions = lir.getLIRforBlock(block);
320            boolean hasDead = false;
321            for (LIRInstruction inst : instructions) {
322                if (inst == null) {
323                    hasDead = true;
324                } else {
325                    inst.setId(-1);
326                }
327            }
328            if (hasDead) {
329                // Remove null values from the list.
330                instructions.removeAll(Collections.singleton(null));
331            }
332        }
333
334        private void deleteInstruction(DefUseTree tree) {
335            AbstractBlockBase<?> block = tree.getBlock();
336            LIRInstruction instruction = tree.getInstruction();
337            Debug.log("deleting instruction %s from block %s", instruction, block);
338            lir.getLIRforBlock(block).set(instruction.id(), null);
339        }
340
341        private LIRInsertionBuffer getInsertionBuffer(AbstractBlockBase<?> block) {
342            LIRInsertionBuffer insertionBuffer = insertionBuffers.get(block);
343            if (insertionBuffer == null) {
344                insertionBuffer = new LIRInsertionBuffer();
345                insertionBuffers.put(block, insertionBuffer);
346                assert !insertionBuffer.initialized() : "already initialized?";
347                List<LIRInstruction> instructions = lir.getLIRforBlock(block);
348                insertionBuffer.init(instructions);
349            }
350            return insertionBuffer;
351        }
352    }
353}