1/*
2 * Copyright (c) 2015, 2016, 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 */
23package org.graalvm.compiler.lir.alloc.trace.lsra;
24
25import static jdk.vm.ci.code.ValueUtil.isRegister;
26import static org.graalvm.compiler.lir.LIRValueUtil.asConstant;
27import static org.graalvm.compiler.lir.LIRValueUtil.asVariable;
28import static org.graalvm.compiler.lir.LIRValueUtil.isConstantValue;
29import static org.graalvm.compiler.lir.LIRValueUtil.isStackSlotValue;
30import static org.graalvm.compiler.lir.LIRValueUtil.isVirtualStackSlot;
31
32import java.util.ArrayList;
33
34import org.graalvm.compiler.core.common.alloc.RegisterAllocationConfig;
35import org.graalvm.compiler.core.common.alloc.Trace;
36import org.graalvm.compiler.core.common.alloc.TraceBuilderResult;
37import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
38import org.graalvm.compiler.debug.Assertions;
39import org.graalvm.compiler.debug.CounterKey;
40import org.graalvm.compiler.debug.DebugContext;
41import org.graalvm.compiler.debug.Indent;
42import org.graalvm.compiler.lir.LIR;
43import org.graalvm.compiler.lir.LIRInstruction;
44import org.graalvm.compiler.lir.StandardOp;
45import org.graalvm.compiler.lir.StandardOp.JumpOp;
46import org.graalvm.compiler.lir.StandardOp.LabelOp;
47import org.graalvm.compiler.lir.alloc.trace.GlobalLivenessInfo;
48import org.graalvm.compiler.lir.alloc.trace.lsra.TraceLinearScanPhase.TraceLinearScan;
49import org.graalvm.compiler.lir.gen.LIRGenerationResult;
50import org.graalvm.compiler.lir.gen.LIRGeneratorTool.MoveFactory;
51import org.graalvm.compiler.lir.ssa.SSAUtil;
52
53import jdk.vm.ci.code.TargetDescription;
54import jdk.vm.ci.meta.Value;
55
56/**
57 * Phase 6: resolve data flow
58 *
59 * Insert moves at edges between blocks if intervals have been split.
60 */
61final class TraceLinearScanResolveDataFlowPhase extends TraceLinearScanAllocationPhase {
62
63    @Override
64    protected void run(TargetDescription target, LIRGenerationResult lirGenRes, Trace trace, MoveFactory spillMoveFactory, RegisterAllocationConfig registerAllocationConfig,
65                    TraceBuilderResult traceBuilderResult, TraceLinearScan allocator) {
66        new Resolver(allocator, traceBuilderResult).resolveDataFlow(trace, allocator.sortedBlocks());
67    }
68
69    private static final class Resolver {
70        private final TraceLinearScan allocator;
71        private final TraceBuilderResult traceBuilderResult;
72        private final DebugContext debug;
73
74        private Resolver(TraceLinearScan allocator, TraceBuilderResult traceBuilderResult) {
75            this.allocator = allocator;
76            this.traceBuilderResult = traceBuilderResult;
77            this.debug = allocator.getDebug();
78        }
79
80        private void resolveFindInsertPos(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, TraceLocalMoveResolver moveResolver) {
81            if (fromBlock.getSuccessorCount() <= 1) {
82                if (debug.isLogEnabled()) {
83                    debug.log("inserting moves at end of fromBlock B%d", fromBlock.getId());
84                }
85
86                ArrayList<LIRInstruction> instructions = allocator.getLIR().getLIRforBlock(fromBlock);
87                LIRInstruction instr = instructions.get(instructions.size() - 1);
88                if (instr instanceof StandardOp.JumpOp) {
89                    // insert moves before branch
90                    moveResolver.setInsertPosition(instructions, instructions.size() - 1);
91                } else {
92                    moveResolver.setInsertPosition(instructions, instructions.size());
93                }
94
95            } else {
96                if (debug.isLogEnabled()) {
97                    debug.log("inserting moves at beginning of toBlock B%d", toBlock.getId());
98                }
99
100                if (Assertions.detailedAssertionsEnabled(allocator.getOptions())) {
101                    assert allocator.getLIR().getLIRforBlock(fromBlock).get(0) instanceof StandardOp.LabelOp : "block does not start with a label";
102
103                    /*
104                     * Because the number of predecessor edges matches the number of successor
105                     * edges, blocks which are reached by switch statements may have be more than
106                     * one predecessor but it will be guaranteed that all predecessors will be the
107                     * same.
108                     */
109                    for (AbstractBlockBase<?> predecessor : toBlock.getPredecessors()) {
110                        assert fromBlock == predecessor : "all critical edges must be broken";
111                    }
112                }
113
114                moveResolver.setInsertPosition(allocator.getLIR().getLIRforBlock(toBlock), 1);
115            }
116        }
117
118        /**
119         * Inserts necessary moves (spilling or reloading) at edges between blocks for intervals
120         * that have been split.
121         */
122        @SuppressWarnings("try")
123        private void resolveDataFlow(Trace currentTrace, AbstractBlockBase<?>[] blocks) {
124            if (blocks.length < 2) {
125                // no resolution necessary
126                return;
127            }
128            try (Indent indent = debug.logAndIndent("resolve data flow")) {
129
130                TraceLocalMoveResolver moveResolver = allocator.createMoveResolver();
131                AbstractBlockBase<?> toBlock = null;
132                for (int i = 0; i < blocks.length - 1; i++) {
133                    AbstractBlockBase<?> fromBlock = blocks[i];
134                    toBlock = blocks[i + 1];
135                    assert containedInTrace(currentTrace, fromBlock) : "Not in Trace: " + fromBlock;
136                    assert containedInTrace(currentTrace, toBlock) : "Not in Trace: " + toBlock;
137                    resolveCollectMappings(fromBlock, toBlock, moveResolver);
138                }
139                assert blocks[blocks.length - 1].equals(toBlock);
140                if (toBlock.isLoopEnd()) {
141                    assert toBlock.getSuccessorCount() == 1;
142                    AbstractBlockBase<?> loopHeader = toBlock.getSuccessors()[0];
143                    if (containedInTrace(currentTrace, loopHeader)) {
144                        resolveCollectMappings(toBlock, loopHeader, moveResolver);
145                    }
146                }
147
148            }
149        }
150
151        @SuppressWarnings("try")
152        private void resolveCollectMappings(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, TraceLocalMoveResolver moveResolver) {
153            try (Indent indent0 = debug.logAndIndent("Edge %s -> %s", fromBlock, toBlock)) {
154                // collect all intervals that have been split between
155                // fromBlock and toBlock
156                int toId = allocator.getFirstLirInstructionId(toBlock);
157                int fromId = allocator.getLastLirInstructionId(fromBlock);
158                assert fromId >= 0;
159                LIR lir = allocator.getLIR();
160                if (SSAUtil.isMerge(toBlock)) {
161                    JumpOp blockEnd = SSAUtil.phiOut(lir, fromBlock);
162                    LabelOp label = SSAUtil.phiIn(lir, toBlock);
163                    for (int i = 0; i < label.getPhiSize(); i++) {
164                        addMapping(blockEnd.getOutgoingValue(i), label.getIncomingValue(i), fromId, toId, moveResolver);
165                    }
166                }
167                GlobalLivenessInfo livenessInfo = allocator.getGlobalLivenessInfo();
168                int[] locTo = livenessInfo.getBlockIn(toBlock);
169                for (int i = 0; i < locTo.length; i++) {
170                    TraceInterval interval = allocator.intervalFor(locTo[i]);
171                    addMapping(interval, interval, fromId, toId, moveResolver);
172                }
173
174                if (moveResolver.hasMappings()) {
175                    resolveFindInsertPos(fromBlock, toBlock, moveResolver);
176                    moveResolver.resolveAndAppendMoves();
177                }
178            }
179        }
180
181        private boolean containedInTrace(Trace currentTrace, AbstractBlockBase<?> block) {
182            return currentTrace.getId() == traceBuilderResult.getTraceForBlock(block).getId();
183        }
184
185        private static final CounterKey numResolutionMoves = DebugContext.counter("TraceRA[numTraceLSRAResolutionMoves]");
186        private static final CounterKey numStackToStackMoves = DebugContext.counter("TraceRA[numTraceLSRAStackToStackMoves]");
187
188        private void addMapping(Value phiFrom, Value phiTo, int fromId, int toId, TraceLocalMoveResolver moveResolver) {
189            assert !isRegister(phiFrom) : "Out is a register: " + phiFrom;
190            assert !isRegister(phiTo) : "In is a register: " + phiTo;
191            assert !Value.ILLEGAL.equals(phiTo) : "The value not needed in this branch? " + phiFrom;
192            if (isVirtualStackSlot(phiTo) && isVirtualStackSlot(phiFrom) && phiTo.equals(phiFrom)) {
193                // no need to handle virtual stack slots
194                return;
195            }
196            TraceInterval toParent = allocator.intervalFor(asVariable(phiTo));
197            if (isConstantValue(phiFrom)) {
198                numResolutionMoves.increment(debug);
199                TraceInterval toInterval = allocator.splitChildAtOpId(toParent, toId, LIRInstruction.OperandMode.DEF);
200                moveResolver.addMapping(asConstant(phiFrom), toInterval);
201            } else {
202                addMapping(allocator.intervalFor(asVariable(phiFrom)), toParent, fromId, toId, moveResolver);
203            }
204        }
205
206        private void addMapping(TraceInterval fromParent, TraceInterval toParent, int fromId, int toId, TraceLocalMoveResolver moveResolver) {
207            TraceInterval fromInterval = allocator.splitChildAtOpId(fromParent, fromId, LIRInstruction.OperandMode.USE);
208            TraceInterval toInterval = toParent.getSplitChildAtOpIdOrNull(toId, LIRInstruction.OperandMode.DEF);
209            if (toInterval == null) {
210                // not alive
211                return;
212            }
213            if (fromInterval != toInterval) {
214                numResolutionMoves.increment(debug);
215                if (isStackSlotValue(toInterval.location()) && isStackSlotValue(fromInterval.location())) {
216                    numStackToStackMoves.increment(debug);
217                }
218                moveResolver.addMapping(fromInterval, toInterval);
219            }
220        }
221    }
222
223}
224