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.alloc.lsra;
024
025import static jdk.internal.jvmci.code.ValueUtil.*;
026import jdk.internal.jvmci.code.*;
027import jdk.internal.jvmci.meta.*;
028import jdk.internal.jvmci.options.*;
029
030import com.oracle.graal.compiler.common.cfg.*;
031import com.oracle.graal.debug.*;
032import com.oracle.graal.debug.Debug.Scope;
033import com.oracle.graal.lir.alloc.lsra.Interval.RegisterBinding;
034import com.oracle.graal.lir.alloc.lsra.Interval.RegisterBindingLists;
035import com.oracle.graal.lir.alloc.lsra.Interval.RegisterPriority;
036import com.oracle.graal.lir.alloc.lsra.Interval.State;
037
038public class OptimizingLinearScanWalker extends LinearScanWalker {
039
040    public static class Options {
041        // @formatter:off
042        @Option(help = "Enable LSRA optimization", type = OptionType.Debug)
043        public static final OptionValue<Boolean> LSRAOptimization = new OptionValue<>(true);
044        @Option(help = "LSRA optimization: Only split but do not reassign", type = OptionType.Debug)
045        public static final OptionValue<Boolean> LSRAOptSplitOnly = new OptionValue<>(false);
046        // @formatter:on
047    }
048
049    OptimizingLinearScanWalker(LinearScan allocator, Interval unhandledFixedFirst, Interval unhandledAnyFirst) {
050        super(allocator, unhandledFixedFirst, unhandledAnyFirst);
051    }
052
053    @Override
054    protected void handleSpillSlot(Interval interval) {
055        assert interval.location() != null : "interval  not assigned " + interval;
056        if (interval.canMaterialize()) {
057            assert !isStackSlotValue(interval.location()) : "interval can materialize but assigned to a stack slot " + interval;
058            return;
059        }
060        assert isStackSlotValue(interval.location()) : "interval not assigned to a stack slot " + interval;
061        try (Scope s1 = Debug.scope("LSRAOptimization")) {
062            Debug.log("adding stack to unhandled list %s", interval);
063            unhandledLists.addToListSortedByStartAndUsePositions(RegisterBinding.Stack, interval);
064        }
065    }
066
067    @SuppressWarnings("unused")
068    private static void printRegisterBindingList(RegisterBindingLists list, RegisterBinding binding) {
069        for (Interval interval = list.get(binding); interval != Interval.EndMarker; interval = interval.next) {
070            Debug.log("%s", interval);
071        }
072    }
073
074    @Override
075    void walk() {
076        try (Scope s = Debug.scope("OptimizingLinearScanWalker")) {
077            for (AbstractBlockBase<?> block : allocator.sortedBlocks()) {
078                optimizeBlock(block);
079            }
080        }
081        super.walk();
082    }
083
084    private void optimizeBlock(AbstractBlockBase<?> block) {
085        if (block.getPredecessorCount() == 1) {
086            int nextBlock = allocator.getFirstLirInstructionId(block);
087            try (Scope s1 = Debug.scope("LSRAOptimization")) {
088                Debug.log("next block: %s (%d)", block, nextBlock);
089            }
090            try (Indent indent0 = Debug.indent()) {
091                walkTo(nextBlock);
092
093                try (Scope s1 = Debug.scope("LSRAOptimization")) {
094                    boolean changed = true;
095                    // we need to do this because the active lists might change
096                    loop: while (changed) {
097                        changed = false;
098                        try (Indent indent1 = Debug.logAndIndent("Active intervals: (block %s [%d])", block, nextBlock)) {
099                            for (Interval active = activeLists.get(RegisterBinding.Any); active != Interval.EndMarker; active = active.next) {
100                                Debug.log("active   (any): %s", active);
101                                if (optimize(nextBlock, block, active, RegisterBinding.Any)) {
102                                    changed = true;
103                                    break loop;
104                                }
105                            }
106                            for (Interval active = activeLists.get(RegisterBinding.Stack); active != Interval.EndMarker; active = active.next) {
107                                Debug.log("active (stack): %s", active);
108                                if (optimize(nextBlock, block, active, RegisterBinding.Stack)) {
109                                    changed = true;
110                                    break loop;
111                                }
112                            }
113                        }
114                    }
115                }
116            }
117        }
118    }
119
120    private boolean optimize(int currentPos, AbstractBlockBase<?> currentBlock, Interval currentInterval, RegisterBinding binding) {
121        // BEGIN initialize and sanity checks
122        assert currentBlock != null : "block must not be null";
123        assert currentInterval != null : "interval must not be null";
124
125        assert currentBlock.getPredecessorCount() == 1 : "more than one predecessors -> optimization not possible";
126
127        if (!currentInterval.isSplitChild()) {
128            // interval is not a split child -> no need for optimization
129            return false;
130        }
131
132        if (currentInterval.from() == currentPos) {
133            // the interval starts at the current position so no need for splitting
134            return false;
135        }
136
137        // get current location
138        AllocatableValue currentLocation = currentInterval.location();
139        assert currentLocation != null : "active intervals must have a location assigned!";
140
141        // get predecessor stuff
142        AbstractBlockBase<?> predecessorBlock = currentBlock.getPredecessors().get(0);
143        int predEndId = allocator.getLastLirInstructionId(predecessorBlock);
144        Interval predecessorInterval = currentInterval.getIntervalCoveringOpId(predEndId);
145        assert predecessorInterval != null : "variable not live at the end of the only predecessor! " + predecessorBlock + " -> " + currentBlock + " interval: " + currentInterval;
146        AllocatableValue predecessorLocation = predecessorInterval.location();
147        assert predecessorLocation != null : "handled intervals must have a location assigned!";
148
149        // END initialize and sanity checks
150
151        if (currentLocation.equals(predecessorLocation)) {
152            // locations are already equal -> nothing to optimize
153            return false;
154        }
155
156        if (!isStackSlotValue(predecessorLocation) && !isRegister(predecessorLocation)) {
157            assert predecessorInterval.canMaterialize();
158            // value is materialized -> no need for optimization
159            return false;
160        }
161
162        assert isStackSlotValue(currentLocation) || isRegister(currentLocation) : "current location not a register or stack slot " + currentLocation;
163
164        try (Indent indent = Debug.logAndIndent("location differs: %s vs. %s", predecessorLocation, currentLocation)) {
165            // split current interval at current position
166            Debug.log("splitting at position %d", currentPos);
167
168            assert allocator.isBlockBegin(currentPos) && ((currentPos & 1) == 0) : "split pos must be even when on block boundary";
169
170            Interval splitPart = currentInterval.split(currentPos, allocator);
171            activeLists.remove(binding, currentInterval);
172
173            assert splitPart.from() >= currentPosition : "cannot append new interval before current walk position";
174
175            // the currentSplitChild is needed later when moves are inserted for reloading
176            assert splitPart.currentSplitChild() == currentInterval : "overwriting wrong currentSplitChild";
177            splitPart.makeCurrentSplitChild();
178
179            if (Debug.isLogEnabled()) {
180                Debug.log("left interval  : %s", currentInterval.logString(allocator));
181                Debug.log("right interval : %s", splitPart.logString(allocator));
182            }
183
184            if (Options.LSRAOptSplitOnly.getValue()) {
185                // just add the split interval to the unhandled list
186                unhandledLists.addToListSortedByStartAndUsePositions(RegisterBinding.Any, splitPart);
187            } else {
188                if (isRegister(predecessorLocation)) {
189                    splitRegisterInterval(splitPart, asRegister(predecessorLocation));
190                } else {
191                    assert isStackSlotValue(predecessorLocation);
192                    Debug.log("assigning interval %s to %s", splitPart, predecessorLocation);
193                    splitPart.assignLocation(predecessorLocation);
194                    // activate interval
195                    activeLists.addToListSortedByCurrentFromPositions(RegisterBinding.Stack, splitPart);
196                    splitPart.state = State.Active;
197
198                    splitStackInterval(splitPart);
199                }
200            }
201        }
202        return true;
203    }
204
205    private void splitRegisterInterval(Interval interval, Register reg) {
206        // collect current usage of registers
207        initVarsForAlloc(interval);
208        initUseLists(false);
209        spillExcludeActiveFixed();
210        // spillBlockUnhandledFixed(cur);
211        assert unhandledLists.get(RegisterBinding.Fixed) == Interval.EndMarker : "must not have unhandled fixed intervals because all fixed intervals have a use at position 0";
212        spillBlockInactiveFixed(interval);
213        spillCollectActiveAny(RegisterPriority.LiveAtLoopEnd);
214        spillCollectInactiveAny(interval);
215
216        if (Debug.isLogEnabled()) {
217            try (Indent indent2 = Debug.logAndIndent("state of registers:")) {
218                for (Register register : availableRegs) {
219                    int i = register.number;
220                    try (Indent indent3 = Debug.logAndIndent("reg %d: usePos: %d, blockPos: %d, intervals: ", i, usePos[i], blockPos[i])) {
221                        for (int j = 0; j < spillIntervals[i].size(); j++) {
222                            Debug.log("%d ", spillIntervals[i].get(j).operandNumber);
223                        }
224                    }
225                }
226            }
227        }
228
229        // the register must be free at least until this position
230        boolean needSplit = blockPos[reg.number] <= interval.to();
231
232        int splitPos = blockPos[reg.number];
233
234        assert splitPos > 0 : "invalid splitPos";
235        assert needSplit || splitPos > interval.from() : "splitting interval at from";
236
237        Debug.log("assigning interval %s to %s", interval, reg);
238        interval.assignLocation(reg.asValue(interval.kind()));
239        if (needSplit) {
240            // register not available for full interval : so split it
241            splitWhenPartialRegisterAvailable(interval, splitPos);
242        }
243
244        // perform splitting and spilling for all affected intervals
245        splitAndSpillIntersectingIntervals(reg);
246
247        // activate interval
248        activeLists.addToListSortedByCurrentFromPositions(RegisterBinding.Any, interval);
249        interval.state = State.Active;
250
251    }
252}