1 /*
2 * Copyright (c) 2016, 2018, 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.ArrayDeque;
28 import java.util.ArrayList;
29 import java.util.Arrays;
30 import java.util.BitSet;
31 import java.util.Collection;
32 import java.util.Deque;
33
34 import org.graalvm.compiler.core.common.alloc.TraceBuilderResult.TrivialTracePredicate;
35 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
36 import org.graalvm.compiler.debug.DebugContext;
37 import org.graalvm.compiler.debug.Indent;
38
39 /**
40 * Computes traces by selecting the unhandled block with the highest execution frequency and going
41 * in both directions, up and down, as long as possible.
42 */
43 public final class BiDirectionalTraceBuilder {
44
45 public static TraceBuilderResult computeTraces(DebugContext debug, AbstractBlockBase<?> startBlock, AbstractBlockBase<?>[] blocks, TrivialTracePredicate pred) {
46 return new BiDirectionalTraceBuilder(blocks).build(debug, startBlock, blocks, pred);
47 }
48
49 private final Deque<AbstractBlockBase<?>> worklist;
50 private final BitSet processed;
51 private final Trace[] blockToTrace;
52
53 private BiDirectionalTraceBuilder(AbstractBlockBase<?>[] blocks) {
54 processed = new BitSet(blocks.length);
55 worklist = createQueue(blocks);
56 blockToTrace = new Trace[blocks.length];
57 }
58
59 private static Deque<AbstractBlockBase<?>> createQueue(AbstractBlockBase<?>[] blocks) {
60 ArrayList<AbstractBlockBase<?>> queue = new ArrayList<>(Arrays.asList(blocks));
61 queue.sort(BiDirectionalTraceBuilder::compare);
62 return new ArrayDeque<>(queue);
63 }
64
65 private static int compare(AbstractBlockBase<?> a, AbstractBlockBase<?> b) {
66 return Double.compare(b.getRelativeFrequency(), a.getRelativeFrequency());
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("BiDirectionalTraceBuilder: start trace building")) {
76 ArrayList<Trace> traces = buildTraces(debug);
77 assert traces.get(0).getBlocks()[0].equals(startBlock) : "The first traces always contains the start block";
78 return TraceBuilderResult.create(debug, blocks, traces, blockToTrace, pred);
79 }
80 }
81
82 protected ArrayList<Trace> buildTraces(DebugContext debug) {
83 ArrayList<Trace> traces = new ArrayList<>();
84 // process worklist
85 while (!worklist.isEmpty()) {
86 AbstractBlockBase<?> block = worklist.pollFirst();
87 assert block != null;
88 if (!processed(block)) {
89 Trace trace = new Trace(findTrace(debug, block));
90 for (AbstractBlockBase<?> traceBlock : trace.getBlocks()) {
91 blockToTrace[traceBlock.getId()] = trace;
92 }
93 trace.setId(traces.size());
94 traces.add(trace);
95 }
96 }
97 return traces;
98 }
99
100 /**
101 * Build a new trace starting at {@code block}.
102 *
103 * @param debug
104 */
105 @SuppressWarnings("try")
106 private Collection<AbstractBlockBase<?>> findTrace(DebugContext debug, AbstractBlockBase<?> initBlock) {
107 ArrayDeque<AbstractBlockBase<?>> trace = new ArrayDeque<>();
108 try (Indent i = debug.logAndIndent("StartTrace: %s", initBlock)) {
109 try (Indent indentFront = debug.logAndIndent("Head:")) {
110 for (AbstractBlockBase<?> block = initBlock; block != null; block = selectPredecessor(block)) {
111 addBlockToTrace(debug, block);
112 trace.addFirst(block);
113 }
114 }
115 /* Number head blocks. Can not do this in the loop as we go backwards. */
116 int blockNr = 0;
117 for (AbstractBlockBase<?> b : trace) {
118 b.setLinearScanNumber(blockNr++);
119 }
120
121 try (Indent indentBack = debug.logAndIndent("Tail:")) {
122 for (AbstractBlockBase<?> block = selectSuccessor(initBlock); block != null; block = selectSuccessor(block)) {
123 addBlockToTrace(debug, block);
124 trace.addLast(block);
125 /* This time we can number the blocks immediately as we go forwards. */
126 block.setLinearScanNumber(blockNr++);
127 }
128 }
129 }
130 debug.log("Trace: %s", trace);
131 return trace;
132 }
133
134 private void addBlockToTrace(DebugContext debug, AbstractBlockBase<?> block) {
135 debug.log("add %s (freq: %f)", block, block.getRelativeFrequency());
136 processed.set(block.getId());
137 }
138
139 /**
140 * @return The unprocessed predecessor with the highest probability, or {@code null}.
141 */
142 private AbstractBlockBase<?> selectPredecessor(AbstractBlockBase<?> block) {
143 AbstractBlockBase<?> next = null;
144 for (AbstractBlockBase<?> pred : block.getPredecessors()) {
145 if (!processed(pred) && !isBackEdge(pred, block) && (next == null || pred.getRelativeFrequency() > next.getRelativeFrequency())) {
146 next = pred;
147 }
148 }
149 return next;
150 }
151
152 private static boolean isBackEdge(AbstractBlockBase<?> from, AbstractBlockBase<?> to) {
153 assert Arrays.asList(from.getSuccessors()).contains(to) : "No edge from " + from + " to " + to;
154 return from.isLoopEnd() && to.isLoopHeader() && from.getLoop().equals(to.getLoop());
155 }
156
157 /**
158 * @return The unprocessed successor with the highest probability, or {@code null}.
159 */
160 private AbstractBlockBase<?> selectSuccessor(AbstractBlockBase<?> block) {
161 AbstractBlockBase<?> next = null;
162 for (AbstractBlockBase<?> succ : block.getSuccessors()) {
163 if (!processed(succ) && (next == null || succ.getRelativeFrequency() > next.getRelativeFrequency())) {
164 next = succ;
165 }
166 }
167 return next;
168 }
169 }