001/*
002 * Copyright (c) 2015, 2015, 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.trace;
024
025import static com.oracle.graal.lir.alloc.trace.TraceRegisterAllocationPhase.Options.*;
026import static jdk.internal.jvmci.code.ValueUtil.*;
027
028import java.util.*;
029
030import jdk.internal.jvmci.code.*;
031import jdk.internal.jvmci.options.*;
032
033import com.oracle.graal.compiler.common.alloc.*;
034import com.oracle.graal.compiler.common.alloc.TraceBuilder.TraceBuilderResult;
035import com.oracle.graal.compiler.common.cfg.*;
036import com.oracle.graal.debug.*;
037import com.oracle.graal.debug.Debug.Scope;
038import com.oracle.graal.lir.*;
039import com.oracle.graal.lir.StandardOp.MoveOp;
040import com.oracle.graal.lir.gen.*;
041import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory;
042import com.oracle.graal.lir.phases.*;
043import com.oracle.graal.lir.ssi.*;
044
045public class TraceRegisterAllocationPhase extends AllocationPhase {
046    public static class Options {
047        // @formatter:off
048        @Option(help = "Use inter-trace register hints.", type = OptionType.Debug)
049        public static final OptionValue<Boolean> TraceRAuseInterTraceHints = new OptionValue<>(true);
050        @Option(help = "Use special allocator for trivial blocks.", type = OptionType.Debug)
051        public static final OptionValue<Boolean> TraceRAtrivialBlockAllocator = new OptionValue<>(true);
052        // @formatter:on
053    }
054
055    static final int TRACE_DUMP_LEVEL = 3;
056    private static final DebugMetric trivialTracesMetric = Debug.metric("TraceRA[trivialTraces]");
057    private static final DebugMetric tracesMetric = Debug.metric("TraceRA[traces]");
058
059    @Override
060    protected <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, SpillMoveFactory spillMoveFactory,
061                    RegisterAllocationConfig registerAllocationConfig) {
062        LIR lir = lirGenRes.getLIR();
063        assert SSIVerifier.verify(lir) : "LIR not in SSI form.";
064        B startBlock = linearScanOrder.get(0);
065        assert startBlock.equals(lir.getControlFlowGraph().getStartBlock());
066        TraceBuilderResult<B> resultTraces = TraceBuilder.computeTraces(startBlock, linearScanOrder);
067
068        Debug.dump(lir, "Before TraceRegisterAllocation");
069        int traceNumber = 0;
070        for (List<B> trace : resultTraces.getTraces()) {
071            try (Indent i = Debug.logAndIndent("Allocating Trace%d: %s", traceNumber, trace); Scope s = Debug.scope("AllocateTrace", trace)) {
072                tracesMetric.increment();
073                if (trivialTracesMetric.isEnabled() && isTrivialTrace(lir, trace)) {
074                    trivialTracesMetric.increment();
075                }
076                Debug.dump(TRACE_DUMP_LEVEL, trace, "Trace" + traceNumber + ": " + trace);
077                if (TraceRAtrivialBlockAllocator.getValue() && isTrivialTrace(lir, trace)) {
078                    new TraceTrivialAllocator(resultTraces).apply(target, lirGenRes, codeEmittingOrder, trace, new AllocationContext(spillMoveFactory, registerAllocationConfig), false);
079                } else {
080                    TraceLinearScan allocator = new TraceLinearScan(target, lirGenRes, spillMoveFactory, registerAllocationConfig, trace, resultTraces);
081                    allocator.allocate(target, lirGenRes, codeEmittingOrder, linearScanOrder, spillMoveFactory, registerAllocationConfig);
082                }
083                Debug.dump(TRACE_DUMP_LEVEL, trace, "After Trace" + traceNumber + ": " + trace);
084                traceNumber++;
085            } catch (Throwable e) {
086                throw Debug.handle(e);
087            }
088            unnumberInstructions(trace, lir);
089        }
090        Debug.dump(lir, "After trace allocation");
091
092        new TraceGlobalMoveResolutionPhase(resultTraces).apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, new AllocationContext(spillMoveFactory, registerAllocationConfig));
093
094        if (replaceStackToStackMoves(lir, spillMoveFactory)) {
095            Debug.dump(lir, "After fixing stack to stack moves");
096        }
097        /*
098         * Incoming Values are needed for the RegisterVerifier, otherwise SIGMAs/PHIs where the Out
099         * and In value matches (ie. there is no resolution move) are falsely detected as errors.
100         */
101        for (AbstractBlockBase<?> toBlock : lir.getControlFlowGraph().getBlocks()) {
102            if (toBlock.getPredecessorCount() != 0) {
103                SSIUtil.removeIncoming(lir, toBlock);
104            } else {
105                assert lir.getControlFlowGraph().getStartBlock().equals(toBlock);
106            }
107            SSIUtil.removeOutgoing(lir, toBlock);
108        }
109    }
110
111    static boolean isTrivialTrace(LIR lir, List<? extends AbstractBlockBase<?>> trace) {
112        return trace.size() == 1 && lir.getLIRforBlock(trace.iterator().next()).size() == 2;
113    }
114
115    /**
116     * Fixup stack to stack moves introduced by stack arguments.
117     *
118     * TODO (je) find a better solution.
119     */
120    private static boolean replaceStackToStackMoves(LIR lir, SpillMoveFactory spillMoveFactory) {
121        boolean changed = false;
122        for (AbstractBlockBase<?> block : lir.getControlFlowGraph().getBlocks()) {
123            List<LIRInstruction> instructions = lir.getLIRforBlock(block);
124            for (int i = 0; i < instructions.size(); i++) {
125                LIRInstruction inst = instructions.get(i);
126
127                if (inst instanceof MoveOp) {
128                    MoveOp move = (MoveOp) inst;
129                    if (isStackSlotValue(move.getInput()) && isStackSlotValue(move.getResult())) {
130                        instructions.set(i, spillMoveFactory.createStackMove(move.getResult(), move.getInput()));
131                        changed = true;
132                    }
133                }
134            }
135        }
136        return changed;
137    }
138
139    private static void unnumberInstructions(List<? extends AbstractBlockBase<?>> trace, LIR lir) {
140        trace.stream().flatMap(b -> lir.getLIRforBlock(b).stream()).forEach(op -> op.setId(-1));
141    }
142}