1 /*
2 * Copyright (c) 2015, 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 */
23
24
25 package org.graalvm.compiler.core.common.alloc;
26
27 import java.util.ArrayList;
28 import java.util.BitSet;
29 import java.util.List;
30 import java.util.PriorityQueue;
31
32 import org.graalvm.compiler.core.common.alloc.TraceBuilderResult.TrivialTracePredicate;
33 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
34 import org.graalvm.compiler.debug.DebugContext;
35 import org.graalvm.compiler.debug.Indent;
36
37 /**
38 * Computes traces by starting at a trace head and keep adding successors as long as possible.
39 */
40 public final class UniDirectionalTraceBuilder {
41
42 public static TraceBuilderResult computeTraces(DebugContext debug, AbstractBlockBase<?> startBlock, AbstractBlockBase<?>[] blocks, TrivialTracePredicate pred) {
43 return new UniDirectionalTraceBuilder(blocks).build(debug, startBlock, blocks, pred);
44 }
45
46 private final PriorityQueue<AbstractBlockBase<?>> worklist;
47 private final BitSet processed;
48 /**
49 * Contains the number of unprocessed predecessors for every {@link AbstractBlockBase#getId()
50 * block}.
51 */
52 private final int[] blocked;
53 private final Trace[] blockToTrace;
54
55 private UniDirectionalTraceBuilder(AbstractBlockBase<?>[] blocks) {
56 processed = new BitSet(blocks.length);
57 worklist = new PriorityQueue<>(UniDirectionalTraceBuilder::compare);
58 assert (worklist != null);
59
60 blocked = new int[blocks.length];
61 blockToTrace = new Trace[blocks.length];
62 for (AbstractBlockBase<?> block : blocks) {
63 blocked[block.getId()] = block.getPredecessorCount();
64 }
65 }
66
67 private static int compare(AbstractBlockBase<?> a, AbstractBlockBase<?> b) {
68 return Double.compare(b.getRelativeFrequency(), a.getRelativeFrequency());
69 }
70
71 private boolean processed(AbstractBlockBase<?> b) {
72 return processed.get(b.getId());
73 }
74
75 @SuppressWarnings("try")
76 private TraceBuilderResult build(DebugContext debug, AbstractBlockBase<?> startBlock, AbstractBlockBase<?>[] blocks, TrivialTracePredicate pred) {
77 try (Indent indent = debug.logAndIndent("UniDirectionalTraceBuilder: start trace building: %s", startBlock)) {
78 ArrayList<Trace> traces = buildTraces(debug, startBlock);
79 return TraceBuilderResult.create(debug, blocks, traces, blockToTrace, pred);
80 }
81 }
82
83 protected ArrayList<Trace> buildTraces(DebugContext debug, AbstractBlockBase<?> startBlock) {
84 ArrayList<Trace> traces = new ArrayList<>();
85 // add start block
86 worklist.add(startBlock);
87 // process worklist
88 while (!worklist.isEmpty()) {
89 AbstractBlockBase<?> block = worklist.poll();
90 assert block != null;
91 if (!processed(block)) {
92 Trace trace = new Trace(findTrace(debug, block));
93 for (AbstractBlockBase<?> traceBlock : trace.getBlocks()) {
94 blockToTrace[traceBlock.getId()] = trace;
95 }
96 trace.setId(traces.size());
97 traces.add(trace);
98 }
99 }
100 return traces;
101 }
102
103 /**
104 * Build a new trace starting at {@code block}.
105 */
106 @SuppressWarnings("try")
107 private List<AbstractBlockBase<?>> findTrace(DebugContext debug, AbstractBlockBase<?> traceStart) {
108 assert checkPredecessorsProcessed(traceStart);
109 ArrayList<AbstractBlockBase<?>> trace = new ArrayList<>();
110 int blockNumber = 0;
111 try (Indent i = debug.logAndIndent("StartTrace: %s", traceStart)) {
112 for (AbstractBlockBase<?> block = traceStart; block != null; block = selectNext(block)) {
113 debug.log("add %s (freq: %f)", block, block.getRelativeFrequency());
114 processed.set(block.getId());
115 trace.add(block);
116 unblock(block);
117 block.setLinearScanNumber(blockNumber++);
118 }
119 }
120 return trace;
121 }
122
123 private boolean checkPredecessorsProcessed(AbstractBlockBase<?> block) {
124 for (AbstractBlockBase<?> pred : block.getPredecessors()) {
125 assert processed(pred) : "Predecessor unscheduled: " + pred;
126 }
127 return true;
128 }
129
130 /**
131 * Decrease the {@link #blocked} count for all predecessors and add them to the worklist once
132 * the count reaches 0.
133 */
134 private void unblock(AbstractBlockBase<?> block) {
135 for (AbstractBlockBase<?> successor : block.getSuccessors()) {
136 if (!processed(successor)) {
137 int blockCount = --blocked[successor.getId()];
138 assert blockCount >= 0;
139 if (blockCount == 0) {
140 worklist.add(successor);
141 }
142 }
143 }
144 }
145
146 /**
147 * @return The unprocessed predecessor with the highest probability, or {@code null}.
148 */
149 private AbstractBlockBase<?> selectNext(AbstractBlockBase<?> block) {
150 AbstractBlockBase<?> next = null;
151 for (AbstractBlockBase<?> successor : block.getSuccessors()) {
152 if (!processed(successor) && (next == null || successor.getRelativeFrequency() > next.getRelativeFrequency())) {
153 next = successor;
154 }
155 }
156 return next;
157 }
158 }