001/*
002 * Copyright (c) 2009, 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 com.oracle.graal.compiler.common.GraalOptions.*;
026import static com.oracle.graal.lir.LIRValueUtil.*;
027import static com.oracle.graal.lir.phases.LIRPhase.Options.*;
028import static jdk.internal.jvmci.code.CodeUtil.*;
029import static jdk.internal.jvmci.code.ValueUtil.*;
030
031import java.util.*;
032
033import jdk.internal.jvmci.code.*;
034import jdk.internal.jvmci.common.*;
035import jdk.internal.jvmci.meta.*;
036import jdk.internal.jvmci.options.*;
037
038import com.oracle.graal.compiler.common.alloc.*;
039import com.oracle.graal.compiler.common.cfg.*;
040import com.oracle.graal.debug.*;
041import com.oracle.graal.debug.Debug.Scope;
042import com.oracle.graal.lir.*;
043import com.oracle.graal.lir.LIRInstruction.OperandFlag;
044import com.oracle.graal.lir.LIRInstruction.OperandMode;
045import com.oracle.graal.lir.alloc.lsra.Interval.RegisterBinding;
046import com.oracle.graal.lir.framemap.*;
047import com.oracle.graal.lir.gen.*;
048import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory;
049import com.oracle.graal.lir.phases.AllocationPhase.AllocationContext;
050
051/**
052 * An implementation of the linear scan register allocator algorithm described in <a
053 * href="http://doi.acm.org/10.1145/1064979.1064998"
054 * >"Optimized Interval Splitting in a Linear Scan Register Allocator"</a> by Christian Wimmer and
055 * Hanspeter Moessenboeck.
056 */
057public class LinearScan {
058
059    public static class Options {
060        // @formatter:off
061        @Option(help = "Enable spill position optimization", type = OptionType.Debug)
062        public static final OptionValue<Boolean> LIROptLSRAOptimizeSpillPosition = new NestedBooleanOptionValue(LIROptimization, true);
063        // @formatter:on
064    }
065
066    public static class BlockData {
067
068        /**
069         * Bit map specifying which operands are live upon entry to this block. These are values
070         * used in this block or any of its successors where such value are not defined in this
071         * block. The bit index of an operand is its {@linkplain LinearScan#operandNumber(Value)
072         * operand number}.
073         */
074        public BitSet liveIn;
075
076        /**
077         * Bit map specifying which operands are live upon exit from this block. These are values
078         * used in a successor block that are either defined in this block or were live upon entry
079         * to this block. The bit index of an operand is its
080         * {@linkplain LinearScan#operandNumber(Value) operand number}.
081         */
082        public BitSet liveOut;
083
084        /**
085         * Bit map specifying which operands are used (before being defined) in this block. That is,
086         * these are the values that are live upon entry to the block. The bit index of an operand
087         * is its {@linkplain LinearScan#operandNumber(Value) operand number}.
088         */
089        public BitSet liveGen;
090
091        /**
092         * Bit map specifying which operands are defined/overwritten in this block. The bit index of
093         * an operand is its {@linkplain LinearScan#operandNumber(Value) operand number}.
094         */
095        public BitSet liveKill;
096    }
097
098    public static final int DOMINATOR_SPILL_MOVE_ID = -2;
099    private static final int SPLIT_INTERVALS_CAPACITY_RIGHT_SHIFT = 1;
100
101    private final LIR ir;
102    private final FrameMapBuilder frameMapBuilder;
103    private final RegisterAttributes[] registerAttributes;
104    private final Register[] registers;
105    private final RegisterAllocationConfig regAllocConfig;
106    private final SpillMoveFactory moveFactory;
107
108    private final BlockMap<BlockData> blockData;
109
110    /**
111     * List of blocks in linear-scan order. This is only correct as long as the CFG does not change.
112     */
113    private final List<? extends AbstractBlockBase<?>> sortedBlocks;
114
115    /** @see #intervals() */
116    private Interval[] intervals;
117
118    /**
119     * The number of valid entries in {@link #intervals}.
120     */
121    private int intervalsSize;
122
123    /**
124     * The index of the first entry in {@link #intervals} for a
125     * {@linkplain #createDerivedInterval(Interval) derived interval}.
126     */
127    private int firstDerivedIntervalIndex = -1;
128
129    /**
130     * Intervals sorted by {@link Interval#from()}.
131     */
132    private Interval[] sortedIntervals;
133
134    /**
135     * Map from an instruction {@linkplain LIRInstruction#id id} to the instruction. Entries should
136     * be retrieved with {@link #instructionForId(int)} as the id is not simply an index into this
137     * array.
138     */
139    private LIRInstruction[] opIdToInstructionMap;
140
141    /**
142     * Map from an instruction {@linkplain LIRInstruction#id id} to the
143     * {@linkplain AbstractBlockBase block} containing the instruction. Entries should be retrieved
144     * with {@link #blockForId(int)} as the id is not simply an index into this array.
145     */
146    private AbstractBlockBase<?>[] opIdToBlockMap;
147
148    /**
149     * The {@linkplain #operandNumber(Value) number} of the first variable operand allocated.
150     */
151    private final int firstVariableNumber;
152
153    protected LinearScan(TargetDescription target, LIRGenerationResult res, SpillMoveFactory spillMoveFactory, RegisterAllocationConfig regAllocConfig,
154                    List<? extends AbstractBlockBase<?>> sortedBlocks) {
155        this.ir = res.getLIR();
156        this.moveFactory = spillMoveFactory;
157        this.frameMapBuilder = res.getFrameMapBuilder();
158        this.sortedBlocks = sortedBlocks;
159        this.registerAttributes = regAllocConfig.getRegisterConfig().getAttributesMap();
160        this.regAllocConfig = regAllocConfig;
161
162        this.registers = target.arch.getRegisters();
163        this.firstVariableNumber = getRegisters().length;
164        this.blockData = new BlockMap<>(ir.getControlFlowGraph());
165    }
166
167    public int getFirstLirInstructionId(AbstractBlockBase<?> block) {
168        int result = ir.getLIRforBlock(block).get(0).id();
169        assert result >= 0;
170        return result;
171    }
172
173    public int getLastLirInstructionId(AbstractBlockBase<?> block) {
174        List<LIRInstruction> instructions = ir.getLIRforBlock(block);
175        int result = instructions.get(instructions.size() - 1).id();
176        assert result >= 0;
177        return result;
178    }
179
180    public SpillMoveFactory getSpillMoveFactory() {
181        return moveFactory;
182    }
183
184    protected MoveResolver createMoveResolver() {
185        MoveResolver moveResolver = new MoveResolver(this);
186        assert moveResolver.checkEmpty();
187        return moveResolver;
188    }
189
190    public static boolean isVariableOrRegister(Value value) {
191        return isVariable(value) || isRegister(value);
192    }
193
194    /**
195     * Converts an operand (variable or register) to an index in a flat address space covering all
196     * the {@linkplain Variable variables} and {@linkplain RegisterValue registers} being processed
197     * by this allocator.
198     */
199    int operandNumber(Value operand) {
200        if (isRegister(operand)) {
201            int number = asRegister(operand).number;
202            assert number < firstVariableNumber;
203            return number;
204        }
205        assert isVariable(operand) : operand;
206        return firstVariableNumber + ((Variable) operand).index;
207    }
208
209    /**
210     * Gets the number of operands. This value will increase by 1 for new variable.
211     */
212    int operandSize() {
213        return firstVariableNumber + ir.numVariables();
214    }
215
216    /**
217     * Gets the highest operand number for a register operand. This value will never change.
218     */
219    int maxRegisterNumber() {
220        return firstVariableNumber - 1;
221    }
222
223    public BlockData getBlockData(AbstractBlockBase<?> block) {
224        return blockData.get(block);
225    }
226
227    void initBlockData(AbstractBlockBase<?> block) {
228        blockData.put(block, new BlockData());
229    }
230
231    static final IntervalPredicate IS_PRECOLORED_INTERVAL = new IntervalPredicate() {
232
233        @Override
234        public boolean apply(Interval i) {
235            return isRegister(i.operand);
236        }
237    };
238
239    static final IntervalPredicate IS_VARIABLE_INTERVAL = new IntervalPredicate() {
240
241        @Override
242        public boolean apply(Interval i) {
243            return isVariable(i.operand);
244        }
245    };
246
247    static final IntervalPredicate IS_STACK_INTERVAL = new IntervalPredicate() {
248
249        @Override
250        public boolean apply(Interval i) {
251            return !isRegister(i.operand);
252        }
253    };
254
255    /**
256     * Gets an object describing the attributes of a given register according to this register
257     * configuration.
258     */
259    public RegisterAttributes attributes(Register reg) {
260        return registerAttributes[reg.number];
261    }
262
263    void assignSpillSlot(Interval interval) {
264        /*
265         * Assign the canonical spill slot of the parent (if a part of the interval is already
266         * spilled) or allocate a new spill slot.
267         */
268        if (interval.canMaterialize()) {
269            interval.assignLocation(Value.ILLEGAL);
270        } else if (interval.spillSlot() != null) {
271            interval.assignLocation(interval.spillSlot());
272        } else {
273            VirtualStackSlot slot = frameMapBuilder.allocateSpillSlot(interval.kind());
274            interval.setSpillSlot(slot);
275            interval.assignLocation(slot);
276        }
277    }
278
279    /**
280     * Map from {@linkplain #operandNumber(Value) operand numbers} to intervals.
281     */
282    public Interval[] intervals() {
283        return intervals;
284    }
285
286    void initIntervals() {
287        intervalsSize = operandSize();
288        intervals = new Interval[intervalsSize + (intervalsSize >> SPLIT_INTERVALS_CAPACITY_RIGHT_SHIFT)];
289    }
290
291    /**
292     * Creates a new interval.
293     *
294     * @param operand the operand for the interval
295     * @return the created interval
296     */
297    Interval createInterval(AllocatableValue operand) {
298        assert isLegal(operand);
299        int operandNumber = operandNumber(operand);
300        Interval interval = new Interval(operand, operandNumber);
301        assert operandNumber < intervalsSize;
302        assert intervals[operandNumber] == null;
303        intervals[operandNumber] = interval;
304        return interval;
305    }
306
307    /**
308     * Creates an interval as a result of splitting or spilling another interval.
309     *
310     * @param source an interval being split of spilled
311     * @return a new interval derived from {@code source}
312     */
313    Interval createDerivedInterval(Interval source) {
314        if (firstDerivedIntervalIndex == -1) {
315            firstDerivedIntervalIndex = intervalsSize;
316        }
317        if (intervalsSize == intervals.length) {
318            intervals = Arrays.copyOf(intervals, intervals.length + (intervals.length >> SPLIT_INTERVALS_CAPACITY_RIGHT_SHIFT));
319        }
320        intervalsSize++;
321        Variable variable = new Variable(source.kind(), ir.nextVariable());
322
323        Interval interval = createInterval(variable);
324        assert intervals[intervalsSize - 1] == interval;
325        return interval;
326    }
327
328    // access to block list (sorted in linear scan order)
329    public int blockCount() {
330        return sortedBlocks.size();
331    }
332
333    public AbstractBlockBase<?> blockAt(int index) {
334        return sortedBlocks.get(index);
335    }
336
337    /**
338     * Gets the size of the {@link BlockData#liveIn} and {@link BlockData#liveOut} sets for a basic
339     * block. These sets do not include any operands allocated as a result of creating
340     * {@linkplain #createDerivedInterval(Interval) derived intervals}.
341     */
342    public int liveSetSize() {
343        return firstDerivedIntervalIndex == -1 ? operandSize() : firstDerivedIntervalIndex;
344    }
345
346    int numLoops() {
347        return ir.getControlFlowGraph().getLoops().size();
348    }
349
350    Interval intervalFor(int operandNumber) {
351        return intervals[operandNumber];
352    }
353
354    public Interval intervalFor(Value operand) {
355        int operandNumber = operandNumber(operand);
356        assert operandNumber < intervalsSize;
357        return intervals[operandNumber];
358    }
359
360    public Interval getOrCreateInterval(AllocatableValue operand) {
361        Interval ret = intervalFor(operand);
362        if (ret == null) {
363            return createInterval(operand);
364        } else {
365            return ret;
366        }
367    }
368
369    void initOpIdMaps(int numInstructions) {
370        opIdToInstructionMap = new LIRInstruction[numInstructions];
371        opIdToBlockMap = new AbstractBlockBase<?>[numInstructions];
372    }
373
374    void putOpIdMaps(int index, LIRInstruction op, AbstractBlockBase<?> block) {
375        opIdToInstructionMap[index] = op;
376        opIdToBlockMap[index] = block;
377    }
378
379    /**
380     * Gets the highest instruction id allocated by this object.
381     */
382    int maxOpId() {
383        assert opIdToInstructionMap.length > 0 : "no operations";
384        return (opIdToInstructionMap.length - 1) << 1;
385    }
386
387    /**
388     * Converts an {@linkplain LIRInstruction#id instruction id} to an instruction index. All LIR
389     * instructions in a method have an index one greater than their linear-scan order predecessor
390     * with the first instruction having an index of 0.
391     */
392    private static int opIdToIndex(int opId) {
393        return opId >> 1;
394    }
395
396    /**
397     * Retrieves the {@link LIRInstruction} based on its {@linkplain LIRInstruction#id id}.
398     *
399     * @param opId an instruction {@linkplain LIRInstruction#id id}
400     * @return the instruction whose {@linkplain LIRInstruction#id} {@code == id}
401     */
402    public LIRInstruction instructionForId(int opId) {
403        assert isEven(opId) : "opId not even";
404        LIRInstruction instr = opIdToInstructionMap[opIdToIndex(opId)];
405        assert instr.id() == opId;
406        return instr;
407    }
408
409    /**
410     * Gets the block containing a given instruction.
411     *
412     * @param opId an instruction {@linkplain LIRInstruction#id id}
413     * @return the block containing the instruction denoted by {@code opId}
414     */
415    public AbstractBlockBase<?> blockForId(int opId) {
416        assert opIdToBlockMap.length > 0 && opId >= 0 && opId <= maxOpId() + 1 : "opId out of range";
417        return opIdToBlockMap[opIdToIndex(opId)];
418    }
419
420    boolean isBlockBegin(int opId) {
421        return opId == 0 || blockForId(opId) != blockForId(opId - 1);
422    }
423
424    boolean coversBlockBegin(int opId1, int opId2) {
425        return blockForId(opId1) != blockForId(opId2);
426    }
427
428    /**
429     * Determines if an {@link LIRInstruction} destroys all caller saved registers.
430     *
431     * @param opId an instruction {@linkplain LIRInstruction#id id}
432     * @return {@code true} if the instruction denoted by {@code id} destroys all caller saved
433     *         registers.
434     */
435    boolean hasCall(int opId) {
436        assert isEven(opId) : "opId not even";
437        return instructionForId(opId).destroysCallerSavedRegisters();
438    }
439
440    abstract static class IntervalPredicate {
441
442        abstract boolean apply(Interval i);
443    }
444
445    public boolean isProcessed(Value operand) {
446        return !isRegister(operand) || attributes(asRegister(operand)).isAllocatable();
447    }
448
449    // * Phase 5: actual register allocation
450
451    private static boolean isSorted(Interval[] intervals) {
452        int from = -1;
453        for (Interval interval : intervals) {
454            assert interval != null;
455            assert from <= interval.from();
456            from = interval.from();
457        }
458        return true;
459    }
460
461    static Interval addToList(Interval first, Interval prev, Interval interval) {
462        Interval newFirst = first;
463        if (prev != null) {
464            prev.next = interval;
465        } else {
466            newFirst = interval;
467        }
468        return newFirst;
469    }
470
471    Interval.Pair createUnhandledLists(IntervalPredicate isList1, IntervalPredicate isList2) {
472        assert isSorted(sortedIntervals) : "interval list is not sorted";
473
474        Interval list1 = Interval.EndMarker;
475        Interval list2 = Interval.EndMarker;
476
477        Interval list1Prev = null;
478        Interval list2Prev = null;
479        Interval v;
480
481        int n = sortedIntervals.length;
482        for (int i = 0; i < n; i++) {
483            v = sortedIntervals[i];
484            if (v == null) {
485                continue;
486            }
487
488            if (isList1.apply(v)) {
489                list1 = addToList(list1, list1Prev, v);
490                list1Prev = v;
491            } else if (isList2 == null || isList2.apply(v)) {
492                list2 = addToList(list2, list2Prev, v);
493                list2Prev = v;
494            }
495        }
496
497        if (list1Prev != null) {
498            list1Prev.next = Interval.EndMarker;
499        }
500        if (list2Prev != null) {
501            list2Prev.next = Interval.EndMarker;
502        }
503
504        assert list1Prev == null || list1Prev.next == Interval.EndMarker : "linear list ends not with sentinel";
505        assert list2Prev == null || list2Prev.next == Interval.EndMarker : "linear list ends not with sentinel";
506
507        return new Interval.Pair(list1, list2);
508    }
509
510    protected void sortIntervalsBeforeAllocation() {
511        int sortedLen = 0;
512        for (Interval interval : intervals) {
513            if (interval != null) {
514                sortedLen++;
515            }
516        }
517
518        Interval[] sortedList = new Interval[sortedLen];
519        int sortedIdx = 0;
520        int sortedFromMax = -1;
521
522        // special sorting algorithm: the original interval-list is almost sorted,
523        // only some intervals are swapped. So this is much faster than a complete QuickSort
524        for (Interval interval : intervals) {
525            if (interval != null) {
526                int from = interval.from();
527
528                if (sortedFromMax <= from) {
529                    sortedList[sortedIdx++] = interval;
530                    sortedFromMax = interval.from();
531                } else {
532                    // the assumption that the intervals are already sorted failed,
533                    // so this interval must be sorted in manually
534                    int j;
535                    for (j = sortedIdx - 1; j >= 0 && from < sortedList[j].from(); j--) {
536                        sortedList[j + 1] = sortedList[j];
537                    }
538                    sortedList[j + 1] = interval;
539                    sortedIdx++;
540                }
541            }
542        }
543        sortedIntervals = sortedList;
544    }
545
546    void sortIntervalsAfterAllocation() {
547        if (firstDerivedIntervalIndex == -1) {
548            // no intervals have been added during allocation, so sorted list is already up to date
549            return;
550        }
551
552        Interval[] oldList = sortedIntervals;
553        Interval[] newList = Arrays.copyOfRange(intervals, firstDerivedIntervalIndex, intervalsSize);
554        int oldLen = oldList.length;
555        int newLen = newList.length;
556
557        // conventional sort-algorithm for new intervals
558        Arrays.sort(newList, (Interval a, Interval b) -> a.from() - b.from());
559
560        // merge old and new list (both already sorted) into one combined list
561        Interval[] combinedList = new Interval[oldLen + newLen];
562        int oldIdx = 0;
563        int newIdx = 0;
564
565        while (oldIdx + newIdx < combinedList.length) {
566            if (newIdx >= newLen || (oldIdx < oldLen && oldList[oldIdx].from() <= newList[newIdx].from())) {
567                combinedList[oldIdx + newIdx] = oldList[oldIdx];
568                oldIdx++;
569            } else {
570                combinedList[oldIdx + newIdx] = newList[newIdx];
571                newIdx++;
572            }
573        }
574
575        sortedIntervals = combinedList;
576    }
577
578    // wrapper for Interval.splitChildAtOpId that performs a bailout in product mode
579    // instead of returning null
580    public Interval splitChildAtOpId(Interval interval, int opId, LIRInstruction.OperandMode mode) {
581        Interval result = interval.getSplitChildAtOpId(opId, mode, this);
582
583        if (result != null) {
584            if (Debug.isLogEnabled()) {
585                Debug.log("Split child at pos %d of interval %s is %s", opId, interval, result);
586            }
587            return result;
588        }
589
590        throw new BailoutException("LinearScan: interval is null");
591    }
592
593    static StackSlotValue canonicalSpillOpr(Interval interval) {
594        assert interval.spillSlot() != null : "canonical spill slot not set";
595        return interval.spillSlot();
596    }
597
598    boolean isMaterialized(AllocatableValue operand, int opId, OperandMode mode) {
599        Interval interval = intervalFor(operand);
600        assert interval != null : "interval must exist";
601
602        if (opId != -1) {
603            /*
604             * Operands are not changed when an interval is split during allocation, so search the
605             * right interval here.
606             */
607            interval = splitChildAtOpId(interval, opId, mode);
608        }
609
610        return isIllegal(interval.location()) && interval.canMaterialize();
611    }
612
613    boolean isCallerSave(Value operand) {
614        return attributes(asRegister(operand)).isCallerSave();
615    }
616
617    protected <B extends AbstractBlockBase<B>> void allocate(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder,
618                    SpillMoveFactory spillMoveFactory, RegisterAllocationConfig registerAllocationConfig) {
619
620        /*
621         * This is the point to enable debug logging for the whole register allocation.
622         */
623        try (Indent indent = Debug.logAndIndent("LinearScan allocate")) {
624            AllocationContext context = new AllocationContext(spillMoveFactory, registerAllocationConfig);
625
626            createLifetimeAnalysisPhase().apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context, false);
627
628            try (Scope s = Debug.scope("AfterLifetimeAnalysis", (Object) intervals)) {
629                sortIntervalsBeforeAllocation();
630
631                createRegisterAllocationPhase().apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context, false);
632
633                if (LinearScan.Options.LIROptLSRAOptimizeSpillPosition.getValue()) {
634                    createOptimizeSpillPositionPhase().apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context, false);
635                }
636                createResolveDataFlowPhase().apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context);
637
638                sortIntervalsAfterAllocation();
639
640                if (DetailedAsserts.getValue()) {
641                    verify();
642                }
643                beforeSpillMoveElimination();
644                createSpillMoveEliminationPhase().apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context);
645                createAssignLocationsPhase().apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context);
646
647                if (DetailedAsserts.getValue()) {
648                    verifyIntervals();
649                }
650            } catch (Throwable e) {
651                throw Debug.handle(e);
652            }
653        }
654    }
655
656    protected void beforeSpillMoveElimination() {
657    }
658
659    protected LinearScanLifetimeAnalysisPhase createLifetimeAnalysisPhase() {
660        return new LinearScanLifetimeAnalysisPhase(this);
661    }
662
663    protected LinearScanRegisterAllocationPhase createRegisterAllocationPhase() {
664        return new LinearScanRegisterAllocationPhase(this);
665    }
666
667    protected LinearScanOptimizeSpillPositionPhase createOptimizeSpillPositionPhase() {
668        return new LinearScanOptimizeSpillPositionPhase(this);
669    }
670
671    protected LinearScanResolveDataFlowPhase createResolveDataFlowPhase() {
672        return new LinearScanResolveDataFlowPhase(this);
673    }
674
675    protected LinearScanEliminateSpillMovePhase createSpillMoveEliminationPhase() {
676        return new LinearScanEliminateSpillMovePhase(this);
677    }
678
679    protected LinearScanAssignLocationsPhase createAssignLocationsPhase() {
680        return new LinearScanAssignLocationsPhase(this);
681    }
682
683    public void printIntervals(String label) {
684        if (Debug.isLogEnabled()) {
685            try (Indent indent = Debug.logAndIndent("intervals %s", label)) {
686                for (Interval interval : intervals) {
687                    if (interval != null) {
688                        Debug.log("%s", interval.logString(this));
689                    }
690                }
691
692                try (Indent indent2 = Debug.logAndIndent("Basic Blocks")) {
693                    for (int i = 0; i < blockCount(); i++) {
694                        AbstractBlockBase<?> block = blockAt(i);
695                        Debug.log("B%d [%d, %d, %s] ", block.getId(), getFirstLirInstructionId(block), getLastLirInstructionId(block), block.getLoop());
696                    }
697                }
698            }
699        }
700        Debug.dump(Arrays.copyOf(intervals, intervalsSize), label);
701    }
702
703    public void printLir(String label, @SuppressWarnings("unused") boolean hirValid) {
704        Debug.dump(ir, label);
705    }
706
707    boolean verify() {
708        // (check that all intervals have a correct register and that no registers are overwritten)
709        verifyIntervals();
710
711        verifyRegisters();
712
713        Debug.log("no errors found");
714
715        return true;
716    }
717
718    private void verifyRegisters() {
719        // Enable this logging to get output for the verification process.
720        try (Indent indent = Debug.logAndIndent("verifying register allocation")) {
721            RegisterVerifier verifier = new RegisterVerifier(this);
722            verifier.verify(blockAt(0));
723        }
724    }
725
726    protected void verifyIntervals() {
727        try (Indent indent = Debug.logAndIndent("verifying intervals")) {
728            int len = intervalsSize;
729
730            for (int i = 0; i < len; i++) {
731                Interval i1 = intervals[i];
732                if (i1 == null) {
733                    continue;
734                }
735
736                i1.checkSplitChildren();
737
738                if (i1.operandNumber != i) {
739                    Debug.log("Interval %d is on position %d in list", i1.operandNumber, i);
740                    Debug.log(i1.logString(this));
741                    throw new JVMCIError("");
742                }
743
744                if (isVariable(i1.operand) && i1.kind().equals(LIRKind.Illegal)) {
745                    Debug.log("Interval %d has no type assigned", i1.operandNumber);
746                    Debug.log(i1.logString(this));
747                    throw new JVMCIError("");
748                }
749
750                if (i1.location() == null) {
751                    Debug.log("Interval %d has no register assigned", i1.operandNumber);
752                    Debug.log(i1.logString(this));
753                    throw new JVMCIError("");
754                }
755
756                if (i1.first() == Range.EndMarker) {
757                    Debug.log("Interval %d has no Range", i1.operandNumber);
758                    Debug.log(i1.logString(this));
759                    throw new JVMCIError("");
760                }
761
762                for (Range r = i1.first(); r != Range.EndMarker; r = r.next) {
763                    if (r.from >= r.to) {
764                        Debug.log("Interval %d has zero length range", i1.operandNumber);
765                        Debug.log(i1.logString(this));
766                        throw new JVMCIError("");
767                    }
768                }
769
770                for (int j = i + 1; j < len; j++) {
771                    Interval i2 = intervals[j];
772                    if (i2 == null) {
773                        continue;
774                    }
775
776                    // special intervals that are created in MoveResolver
777                    // . ignore them because the range information has no meaning there
778                    if (i1.from() == 1 && i1.to() == 2) {
779                        continue;
780                    }
781                    if (i2.from() == 1 && i2.to() == 2) {
782                        continue;
783                    }
784                    Value l1 = i1.location();
785                    Value l2 = i2.location();
786                    if (i1.intersects(i2) && !isIllegal(l1) && (l1.equals(l2))) {
787                        if (DetailedAsserts.getValue()) {
788                            Debug.log("Intervals %d and %d overlap and have the same register assigned", i1.operandNumber, i2.operandNumber);
789                            Debug.log(i1.logString(this));
790                            Debug.log(i2.logString(this));
791                        }
792                        throw new BailoutException("");
793                    }
794                }
795            }
796        }
797    }
798
799    class CheckConsumer implements ValueConsumer {
800
801        boolean ok;
802        Interval curInterval;
803
804        @Override
805        public void visitValue(Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
806            if (isRegister(operand)) {
807                if (intervalFor(operand) == curInterval) {
808                    ok = true;
809                }
810            }
811        }
812    }
813
814    void verifyNoOopsInFixedIntervals() {
815        try (Indent indent = Debug.logAndIndent("verifying that no oops are in fixed intervals *")) {
816            CheckConsumer checkConsumer = new CheckConsumer();
817
818            Interval fixedIntervals;
819            Interval otherIntervals;
820            fixedIntervals = createUnhandledLists(IS_PRECOLORED_INTERVAL, null).first;
821            // to ensure a walking until the last instruction id, add a dummy interval
822            // with a high operation id
823            otherIntervals = new Interval(Value.ILLEGAL, -1);
824            otherIntervals.addRange(Integer.MAX_VALUE - 2, Integer.MAX_VALUE - 1);
825            IntervalWalker iw = new IntervalWalker(this, fixedIntervals, otherIntervals);
826
827            for (AbstractBlockBase<?> block : sortedBlocks) {
828                List<LIRInstruction> instructions = ir.getLIRforBlock(block);
829
830                for (int j = 0; j < instructions.size(); j++) {
831                    LIRInstruction op = instructions.get(j);
832
833                    if (op.hasState()) {
834                        iw.walkBefore(op.id());
835                        boolean checkLive = true;
836
837                        /*
838                         * Make sure none of the fixed registers is live across an oopmap since we
839                         * can't handle that correctly.
840                         */
841                        if (checkLive) {
842                            for (Interval interval = iw.activeLists.get(RegisterBinding.Fixed); interval != Interval.EndMarker; interval = interval.next) {
843                                if (interval.currentTo() > op.id() + 1) {
844                                    /*
845                                     * This interval is live out of this op so make sure that this
846                                     * interval represents some value that's referenced by this op
847                                     * either as an input or output.
848                                     */
849                                    checkConsumer.curInterval = interval;
850                                    checkConsumer.ok = false;
851
852                                    op.visitEachInput(checkConsumer);
853                                    op.visitEachAlive(checkConsumer);
854                                    op.visitEachTemp(checkConsumer);
855                                    op.visitEachOutput(checkConsumer);
856
857                                    assert checkConsumer.ok : "fixed intervals should never be live across an oopmap point";
858                                }
859                            }
860                        }
861                    }
862                }
863            }
864        }
865    }
866
867    public LIR getLIR() {
868        return ir;
869    }
870
871    public FrameMapBuilder getFrameMapBuilder() {
872        return frameMapBuilder;
873    }
874
875    public List<? extends AbstractBlockBase<?>> sortedBlocks() {
876        return sortedBlocks;
877    }
878
879    public Register[] getRegisters() {
880        return registers;
881    }
882
883    public RegisterAllocationConfig getRegisterAllocationConfig() {
884        return regAllocConfig;
885    }
886
887    public boolean callKillsRegisters() {
888        return regAllocConfig.getRegisterConfig().areAllAllocatableRegistersCallerSaved();
889    }
890
891}