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 */
23package org.graalvm.compiler.lir.alloc.lsra;
24
25import static jdk.vm.ci.code.ValueUtil.asRegister;
26import static jdk.vm.ci.code.ValueUtil.isRegister;
27import static org.graalvm.compiler.lir.LIRValueUtil.isStackSlotValue;
28
29import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
30import org.graalvm.compiler.debug.DebugContext;
31import org.graalvm.compiler.debug.Indent;
32import org.graalvm.compiler.lir.alloc.lsra.Interval.RegisterBinding;
33import org.graalvm.compiler.lir.alloc.lsra.Interval.RegisterBindingLists;
34import org.graalvm.compiler.lir.alloc.lsra.Interval.RegisterPriority;
35import org.graalvm.compiler.lir.alloc.lsra.Interval.State;
36import org.graalvm.compiler.options.Option;
37import org.graalvm.compiler.options.OptionKey;
38import org.graalvm.compiler.options.OptionType;
39
40import jdk.vm.ci.code.Register;
41import jdk.vm.ci.meta.AllocatableValue;
42
43public class OptimizingLinearScanWalker extends LinearScanWalker {
44
45    public static class Options {
46        // @formatter:off
47        @Option(help = "Enable LSRA optimization", type = OptionType.Debug)
48        public static final OptionKey<Boolean> LSRAOptimization = new OptionKey<>(false);
49        @Option(help = "LSRA optimization: Only split but do not reassign", type = OptionType.Debug)
50        public static final OptionKey<Boolean> LSRAOptSplitOnly = new OptionKey<>(false);
51        // @formatter:on
52    }
53
54    OptimizingLinearScanWalker(LinearScan allocator, Interval unhandledFixedFirst, Interval unhandledAnyFirst) {
55        super(allocator, unhandledFixedFirst, unhandledAnyFirst);
56    }
57
58    @SuppressWarnings("try")
59    @Override
60    protected void handleSpillSlot(Interval interval) {
61        assert interval.location() != null : "interval  not assigned " + interval;
62        if (interval.canMaterialize()) {
63            assert !isStackSlotValue(interval.location()) : "interval can materialize but assigned to a stack slot " + interval;
64            return;
65        }
66        assert isStackSlotValue(interval.location()) : "interval not assigned to a stack slot " + interval;
67        DebugContext debug = allocator.getDebug();
68        try (DebugContext.Scope s1 = debug.scope("LSRAOptimization")) {
69            debug.log("adding stack to unhandled list %s", interval);
70            unhandledLists.addToListSortedByStartAndUsePositions(RegisterBinding.Stack, interval);
71        }
72    }
73
74    @SuppressWarnings("unused")
75    private static void printRegisterBindingList(DebugContext debug, RegisterBindingLists list, RegisterBinding binding) {
76        for (Interval interval = list.get(binding); !interval.isEndMarker(); interval = interval.next) {
77            debug.log("%s", interval);
78        }
79    }
80
81    @SuppressWarnings("try")
82    @Override
83    void walk() {
84        try (DebugContext.Scope s = allocator.getDebug().scope("OptimizingLinearScanWalker")) {
85            for (AbstractBlockBase<?> block : allocator.sortedBlocks()) {
86                optimizeBlock(block);
87            }
88        }
89        super.walk();
90    }
91
92    @SuppressWarnings("try")
93    private void optimizeBlock(AbstractBlockBase<?> block) {
94        if (block.getPredecessorCount() == 1) {
95            int nextBlock = allocator.getFirstLirInstructionId(block);
96            DebugContext debug = allocator.getDebug();
97            try (DebugContext.Scope s1 = debug.scope("LSRAOptimization")) {
98                debug.log("next block: %s (%d)", block, nextBlock);
99            }
100            try (Indent indent0 = debug.indent()) {
101                walkTo(nextBlock);
102
103                try (DebugContext.Scope s1 = debug.scope("LSRAOptimization")) {
104                    boolean changed = true;
105                    // we need to do this because the active lists might change
106                    loop: while (changed) {
107                        changed = false;
108                        try (Indent indent1 = debug.logAndIndent("Active intervals: (block %s [%d])", block, nextBlock)) {
109                            for (Interval active = activeLists.get(RegisterBinding.Any); !active.isEndMarker(); active = active.next) {
110                                debug.log("active   (any): %s", active);
111                                if (optimize(nextBlock, block, active, RegisterBinding.Any)) {
112                                    changed = true;
113                                    break loop;
114                                }
115                            }
116                            for (Interval active = activeLists.get(RegisterBinding.Stack); !active.isEndMarker(); active = active.next) {
117                                debug.log("active (stack): %s", active);
118                                if (optimize(nextBlock, block, active, RegisterBinding.Stack)) {
119                                    changed = true;
120                                    break loop;
121                                }
122                            }
123                        }
124                    }
125                }
126            }
127        }
128    }
129
130    @SuppressWarnings("try")
131    private boolean optimize(int currentPos, AbstractBlockBase<?> currentBlock, Interval currentInterval, RegisterBinding binding) {
132        // BEGIN initialize and sanity checks
133        assert currentBlock != null : "block must not be null";
134        assert currentInterval != null : "interval must not be null";
135
136        assert currentBlock.getPredecessorCount() == 1 : "more than one predecessors -> optimization not possible";
137
138        if (!currentInterval.isSplitChild()) {
139            // interval is not a split child -> no need for optimization
140            return false;
141        }
142
143        if (currentInterval.from() == currentPos) {
144            // the interval starts at the current position so no need for splitting
145            return false;
146        }
147
148        // get current location
149        AllocatableValue currentLocation = currentInterval.location();
150        assert currentLocation != null : "active intervals must have a location assigned!";
151
152        // get predecessor stuff
153        AbstractBlockBase<?> predecessorBlock = currentBlock.getPredecessors()[0];
154        int predEndId = allocator.getLastLirInstructionId(predecessorBlock);
155        Interval predecessorInterval = currentInterval.getIntervalCoveringOpId(predEndId);
156        assert predecessorInterval != null : "variable not live at the end of the only predecessor! " + predecessorBlock + " -> " + currentBlock + " interval: " + currentInterval;
157        AllocatableValue predecessorLocation = predecessorInterval.location();
158        assert predecessorLocation != null : "handled intervals must have a location assigned!";
159
160        // END initialize and sanity checks
161
162        if (currentLocation.equals(predecessorLocation)) {
163            // locations are already equal -> nothing to optimize
164            return false;
165        }
166
167        if (!isStackSlotValue(predecessorLocation) && !isRegister(predecessorLocation)) {
168            assert predecessorInterval.canMaterialize();
169            // value is materialized -> no need for optimization
170            return false;
171        }
172
173        assert isStackSlotValue(currentLocation) || isRegister(currentLocation) : "current location not a register or stack slot " + currentLocation;
174
175        DebugContext debug = allocator.getDebug();
176        try (Indent indent = debug.logAndIndent("location differs: %s vs. %s", predecessorLocation, currentLocation)) {
177            // split current interval at current position
178            debug.log("splitting at position %d", currentPos);
179
180            assert allocator.isBlockBegin(currentPos) && ((currentPos & 1) == 0) : "split pos must be even when on block boundary";
181
182            Interval splitPart = currentInterval.split(currentPos, allocator);
183            activeLists.remove(binding, currentInterval);
184
185            assert splitPart.from() >= currentPosition : "cannot append new interval before current walk position";
186
187            // the currentSplitChild is needed later when moves are inserted for reloading
188            assert splitPart.currentSplitChild() == currentInterval : "overwriting wrong currentSplitChild";
189            splitPart.makeCurrentSplitChild();
190
191            if (debug.isLogEnabled()) {
192                debug.log("left interval  : %s", currentInterval.logString(allocator));
193                debug.log("right interval : %s", splitPart.logString(allocator));
194            }
195
196            if (Options.LSRAOptSplitOnly.getValue(allocator.getOptions())) {
197                // just add the split interval to the unhandled list
198                unhandledLists.addToListSortedByStartAndUsePositions(RegisterBinding.Any, splitPart);
199            } else {
200                if (isRegister(predecessorLocation)) {
201                    splitRegisterInterval(splitPart, asRegister(predecessorLocation));
202                } else {
203                    assert isStackSlotValue(predecessorLocation);
204                    debug.log("assigning interval %s to %s", splitPart, predecessorLocation);
205                    splitPart.assignLocation(predecessorLocation);
206                    // activate interval
207                    activeLists.addToListSortedByCurrentFromPositions(RegisterBinding.Stack, splitPart);
208                    splitPart.state = State.Active;
209
210                    splitStackInterval(splitPart);
211                }
212            }
213        }
214        return true;
215    }
216
217    @SuppressWarnings("try")
218    private void splitRegisterInterval(Interval interval, Register reg) {
219        // collect current usage of registers
220        initVarsForAlloc(interval);
221        initUseLists(false);
222        spillExcludeActiveFixed();
223        // spillBlockUnhandledFixed(cur);
224        assert unhandledLists.get(RegisterBinding.Fixed).isEndMarker() : "must not have unhandled fixed intervals because all fixed intervals have a use at position 0";
225        spillBlockInactiveFixed(interval);
226        spillCollectActiveAny(RegisterPriority.LiveAtLoopEnd);
227        spillCollectInactiveAny(interval);
228
229        DebugContext debug = allocator.getDebug();
230        if (debug.isLogEnabled()) {
231            try (Indent indent2 = debug.logAndIndent("state of registers:")) {
232                for (Register register : availableRegs) {
233                    int i = register.number;
234                    try (Indent indent3 = debug.logAndIndent("reg %d: usePos: %d, blockPos: %d, intervals: ", i, usePos[i], blockPos[i])) {
235                        for (int j = 0; j < spillIntervals[i].size(); j++) {
236                            debug.log("%d ", spillIntervals[i].get(j).operandNumber);
237                        }
238                    }
239                }
240            }
241        }
242
243        // the register must be free at least until this position
244        boolean needSplit = blockPos[reg.number] <= interval.to();
245
246        int splitPos = blockPos[reg.number];
247
248        assert splitPos > 0 : "invalid splitPos";
249        assert needSplit || splitPos > interval.from() : "splitting interval at from";
250
251        debug.log("assigning interval %s to %s", interval, reg);
252        interval.assignLocation(reg.asValue(interval.kind()));
253        if (needSplit) {
254            // register not available for full interval : so split it
255            splitWhenPartialRegisterAvailable(interval, splitPos);
256        }
257
258        // perform splitting and spilling for all affected intervals
259        splitAndSpillIntersectingIntervals(reg);
260
261        // activate interval
262        activeLists.addToListSortedByCurrentFromPositions(RegisterBinding.Any, interval);
263        interval.state = State.Active;
264
265    }
266}
267