UniDirectionalTraceBuilder.java revision 13264:48566d838608 
1207753Smm/*
2207753Smm * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved.
3207753Smm * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4207753Smm *
5207753Smm * This code is free software; you can redistribute it and/or modify it
6207753Smm * under the terms of the GNU General Public License version 2 only, as
7207753Smm * published by the Free Software Foundation.
8207753Smm *
9207753Smm * This code is distributed in the hope that it will be useful, but WITHOUT
10207753Smm * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11207753Smm * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
12207753Smm * version 2 for more details (a copy is included in the LICENSE file that
13207753Smm * accompanied this code).
14207753Smm *
15207753Smm * You should have received a copy of the GNU General Public License version
16207753Smm * 2 along with this work; if not, write to the Free Software Foundation,
17207753Smm * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18207753Smm *
19207753Smm * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20207753Smm * or visit www.oracle.com if you need additional information or have any
21207753Smm * questions.
22207753Smm */
23207753Smmpackage org.graalvm.compiler.core.common.alloc;
24207753Smm
25207753Smmimport java.util.ArrayList;
26207753Smmimport java.util.BitSet;
27207753Smmimport java.util.List;
28207753Smmimport java.util.PriorityQueue;
29
30import org.graalvm.compiler.core.common.alloc.TraceBuilderResult.TrivialTracePredicate;
31import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
32import org.graalvm.compiler.debug.DebugContext;
33import org.graalvm.compiler.debug.Indent;
34
35/**
36 * Computes traces by starting at a trace head and keep adding predecessors as long as possible.
37 */
38public final class UniDirectionalTraceBuilder {
39
40    public static TraceBuilderResult computeTraces(DebugContext debug, AbstractBlockBase<?> startBlock, AbstractBlockBase<?>[] blocks, TrivialTracePredicate pred) {
41        return new UniDirectionalTraceBuilder(blocks).build(debug, startBlock, blocks, pred);
42    }
43
44    private final PriorityQueue<AbstractBlockBase<?>> worklist;
45    private final BitSet processed;
46    /**
47     * Contains the number of unprocessed predecessors for every {@link AbstractBlockBase#getId()
48     * block}.
49     */
50    private final int[] blocked;
51    private final Trace[] blockToTrace;
52
53    private UniDirectionalTraceBuilder(AbstractBlockBase<?>[] blocks) {
54        processed = new BitSet(blocks.length);
55        worklist = new PriorityQueue<>(UniDirectionalTraceBuilder::compare);
56        assert (worklist != null);
57
58        blocked = new int[blocks.length];
59        blockToTrace = new Trace[blocks.length];
60        for (AbstractBlockBase<?> block : blocks) {
61            blocked[block.getId()] = block.getPredecessorCount();
62        }
63    }
64
65    private static int compare(AbstractBlockBase<?> a, AbstractBlockBase<?> b) {
66        return Double.compare(b.probability(), a.probability());
67    }
68
69    private boolean processed(AbstractBlockBase<?> b) {
70        return processed.get(b.getId());
71    }
72
73    @SuppressWarnings("try")
74    private TraceBuilderResult build(DebugContext debug, AbstractBlockBase<?> startBlock, AbstractBlockBase<?>[] blocks, TrivialTracePredicate pred) {
75        try (Indent indent = debug.logAndIndent("UniDirectionalTraceBuilder: start trace building: %s", startBlock)) {
76            ArrayList<Trace> traces = buildTraces(debug, startBlock);
77            return TraceBuilderResult.create(debug, blocks, traces, blockToTrace, pred);
78        }
79    }
80
81    protected ArrayList<Trace> buildTraces(DebugContext debug, AbstractBlockBase<?> startBlock) {
82        ArrayList<Trace> traces = new ArrayList<>();
83        // add start block
84        worklist.add(startBlock);
85        // process worklist
86        while (!worklist.isEmpty()) {
87            AbstractBlockBase<?> block = worklist.poll();
88            assert block != null;
89            if (!processed(block)) {
90                Trace trace = new Trace(startTrace(debug, block));
91                for (AbstractBlockBase<?> traceBlock : trace.getBlocks()) {
92                    blockToTrace[traceBlock.getId()] = trace;
93                }
94                trace.setId(traces.size());
95                traces.add(trace);
96            }
97        }
98        return traces;
99    }
100
101    /**
102     * Build a new trace starting at {@code block}.
103     */
104    @SuppressWarnings("try")
105    private List<AbstractBlockBase<?>> startTrace(DebugContext debug, AbstractBlockBase<?> block) {
106        assert checkPredecessorsProcessed(block);
107        ArrayList<AbstractBlockBase<?>> trace = new ArrayList<>();
108        int blockNumber = 0;
109        try (Indent i = debug.logAndIndent("StartTrace: %s", block)) {
110            for (AbstractBlockBase<?> currentBlock = block; currentBlock != null; currentBlock = selectNext(currentBlock)) {
111                debug.log("add %s (prob: %f)", currentBlock, currentBlock.probability());
112                processed.set(currentBlock.getId());
113                trace.add(currentBlock);
114                unblock(currentBlock);
115                currentBlock.setLinearScanNumber(blockNumber++);
116            }
117        }
118        return trace;
119    }
120
121    private boolean checkPredecessorsProcessed(AbstractBlockBase<?> block) {
122        for (AbstractBlockBase<?> pred : block.getPredecessors()) {
123            if (!processed(pred)) {
124                assert false : "Predecessor unscheduled: " + pred;
125                return false;
126            }
127
128        }
129        return true;
130    }
131
132    /**
133     * Decrease the {@link #blocked} count for all predecessors and add them to the worklist once
134     * the count reaches 0.
135     */
136    private void unblock(AbstractBlockBase<?> currentBlock) {
137        for (AbstractBlockBase<?> successor : currentBlock.getSuccessors()) {
138            if (!processed(successor)) {
139                int blockCount = --blocked[successor.getId()];
140                assert blockCount >= 0;
141                if (blockCount == 0) {
142                    worklist.add(successor);
143                }
144            }
145        }
146    }
147
148    /**
149     * @return The unprocessed predecessor with the highest probability, or {@code null}.
150     */
151    private AbstractBlockBase<?> selectNext(AbstractBlockBase<?> currentBlock) {
152        AbstractBlockBase<?> next = null;
153        for (AbstractBlockBase<?> succ : currentBlock.getSuccessors()) {
154            if (!processed(succ) && (next == null || succ.probability() > next.probability())) {
155                next = succ;
156            }
157        }
158        return next;
159    }
160}
161