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 package org.graalvm.compiler.core.common.alloc;
24
25 import java.util.ArrayList;
26 import java.util.BitSet;
27 import java.util.List;
28 import java.util.PriorityQueue;
29
30 import org.graalvm.compiler.core.common.alloc.TraceBuilderResult.TrivialTracePredicate;
31 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
32 import org.graalvm.compiler.debug.Debug;
33 import 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 */
38 public final class UniDirectionalTraceBuilder {
39
40 public static TraceBuilderResult computeTraces(AbstractBlockBase<?> startBlock, AbstractBlockBase<?>[] blocks, TrivialTracePredicate pred) {
41 return new UniDirectionalTraceBuilder(blocks).build(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(AbstractBlockBase<?> startBlock, AbstractBlockBase<?>[] blocks, TrivialTracePredicate pred) {
75 try (Indent indent = Debug.logAndIndent("UniDirectionalTraceBuilder: start trace building: %s", startBlock)) {
76 ArrayList<Trace> traces = buildTraces(startBlock);
77 return TraceBuilderResult.create(blocks, traces, blockToTrace, pred);
78 }
79 }
80
81 protected ArrayList<Trace> buildTraces(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(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(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 }