1 /*
2 * Copyright (c) 2016, 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.Arrays;
27 import java.util.BitSet;
28
29 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
30 import org.graalvm.compiler.debug.Debug;
31 import org.graalvm.compiler.debug.Indent;
32
33 public final class TraceBuilderResult {
34
35 public abstract static class TrivialTracePredicate {
36 public abstract boolean isTrivialTrace(Trace trace);
37 }
38
39 private final ArrayList<Trace> traces;
40 private final Trace[] blockToTrace;
41
42 static TraceBuilderResult create(AbstractBlockBase<?>[] blocks, ArrayList<Trace> traces, Trace[] blockToTrace, TrivialTracePredicate pred) {
43 connect(traces, blockToTrace);
44 ArrayList<Trace> newTraces = reorderTraces(traces, pred);
45 TraceBuilderResult traceBuilderResult = new TraceBuilderResult(newTraces, blockToTrace);
46 traceBuilderResult.numberTraces();
47 assert verify(traceBuilderResult, blocks.length);
48 return traceBuilderResult;
49 }
50
51 private TraceBuilderResult(ArrayList<Trace> traces, Trace[] blockToTrace) {
52 this.traces = traces;
53 this.blockToTrace = blockToTrace;
54 }
55
56 public Trace getTraceForBlock(AbstractBlockBase<?> block) {
57 return blockToTrace[block.getId()];
58 }
59
60 public ArrayList<Trace> getTraces() {
61 return traces;
62 }
63
64 public boolean incomingEdges(Trace trace) {
65 return incomingEdges(trace.getId(), trace.getBlocks(), 0);
66 }
67
68 public boolean incomingSideEdges(Trace trace) {
69 AbstractBlockBase<?>[] traceArr = trace.getBlocks();
70 if (traceArr.length <= 0) {
71 return false;
72 }
73 return incomingEdges(trace.getId(), traceArr, 1);
74 }
75
76 private boolean incomingEdges(int traceNr, AbstractBlockBase<?>[] trace, int index) {
77 /* TODO (je): not efficient. find better solution. */
78 for (int i = index; i < trace.length; i++) {
79 AbstractBlockBase<?> block = trace[1];
80 for (AbstractBlockBase<?> pred : block.getPredecessors()) {
81 if (getTraceForBlock(pred).getId() != traceNr) {
82 return true;
83 }
84 }
85 }
86 return false;
87 }
88
89 public static boolean verify(TraceBuilderResult traceBuilderResult, int expectedLength) {
90 ArrayList<Trace> traces = traceBuilderResult.getTraces();
91 assert verifyAllBlocksScheduled(traceBuilderResult, expectedLength) : "Not all blocks assigned to traces!";
92 for (int i = 0; i < traces.size(); i++) {
93 Trace trace = traces.get(i);
94 assert trace.getId() == i : "Trace number mismatch: " + trace.getId() + " vs. " + i;
95
96 BitSet suxTraces = new BitSet(traces.size());
97 for (Trace suxTrace : trace.getSuccessors()) {
98 assert !suxTraces.get(suxTrace.getId()) : "Trace twice successors " + suxTrace;
99 suxTraces.set(suxTrace.getId());
100 }
101
102 AbstractBlockBase<?> last = null;
103 int blockNumber = 0;
104 for (AbstractBlockBase<?> current : trace.getBlocks()) {
105 AbstractBlockBase<?> block = current;
106 assert traceBuilderResult.getTraceForBlock(block).getId() == i : "Trace number mismatch for block " + block + ": " + traceBuilderResult.getTraceForBlock(block) + " vs. " + i;
107 assert last == null || Arrays.asList(current.getPredecessors()).contains(last) : "Last block (" + last + ") not a predecessor of " + current;
108 assert current.getLinearScanNumber() == blockNumber : "Blocks not numbered correctly: " + current.getLinearScanNumber() + " vs. " + blockNumber;
109 last = current;
110 blockNumber++;
111 for (AbstractBlockBase<?> sux : block.getSuccessors()) {
112 Trace suxTrace = traceBuilderResult.getTraceForBlock(sux);
113 assert suxTraces.get(suxTrace.getId()) : "Successor Trace " + suxTrace + " for block " + sux + " not in successor traces of " + trace;
114 }
115 }
116 }
117 return true;
118 }
119
120 private static boolean verifyAllBlocksScheduled(TraceBuilderResult traceBuilderResult, int expectedLength) {
121 ArrayList<Trace> traces = traceBuilderResult.getTraces();
122 BitSet handled = new BitSet(expectedLength);
123 for (Trace trace : traces) {
124 for (AbstractBlockBase<?> block : trace.getBlocks()) {
125 assert !handled.get(block.getId()) : "Block added twice: " + block;
126 handled.set(block.getId());
127 }
128 }
129 return handled.cardinality() == expectedLength;
130 }
131
132 private void numberTraces() {
133 for (int i = 0; i < traces.size(); i++) {
134 Trace trace = traces.get(i);
135 trace.setId(i);
136 }
137 }
138
139 private static void connect(ArrayList<Trace> traces, Trace[] blockToTrace) {
140 int numTraces = traces.size();
141 for (Trace trace : traces) {
142 BitSet added = new BitSet(numTraces);
143 ArrayList<Trace> successors = trace.getSuccessors();
144 assert successors.size() == 0 : "Can only connect traces once!";
145
146 for (AbstractBlockBase<?> block : trace.getBlocks()) {
147 for (AbstractBlockBase<?> succ : block.getSuccessors()) {
148 Trace succTrace = blockToTrace[succ.getId()];
149 int succId = succTrace.getId();
150 if (!added.get(succId)) {
151 added.set(succId);
152 successors.add(succTrace);
153 }
154 }
155 }
156 }
157 }
158
159 @SuppressWarnings("try")
160 private static ArrayList<Trace> reorderTraces(ArrayList<Trace> oldTraces, TrivialTracePredicate pred) {
161 if (pred == null) {
162 return oldTraces;
163 }
164 try (Indent indent = Debug.logAndIndent("ReorderTrace")) {
165 ArrayList<Trace> newTraces = new ArrayList<>(oldTraces.size());
166 for (int oldTraceIdx = 0; oldTraceIdx < oldTraces.size(); oldTraceIdx++) {
167 Trace currentTrace = oldTraces.get(oldTraceIdx);
168 if (!alreadyProcessed(newTraces, currentTrace)) {
169 assert currentTrace.getId() == oldTraceIdx : "Index mismatch";
170 // add current trace
171 addTrace(newTraces, currentTrace);
172 for (Trace succTrace : currentTrace.getSuccessors()) {
173 if (pred.isTrivialTrace(succTrace) && !alreadyProcessed(newTraces, succTrace)) {
174 Debug.log("Moving trivial trace from %d to %d", succTrace.getId(), newTraces.size());
175 // add trivial successor trace
176 addTrace(newTraces, succTrace);
177 }
178 }
179 }
180 }
181 assert newTraces.size() == oldTraces.size() : "Lost traces? " + oldTraces.size() + " vs. " + newTraces.size();
182 return newTraces;
183 }
184 }
185
186 private static boolean alreadyProcessed(ArrayList<Trace> newTraces, Trace currentTrace) {
187 int currentTraceId = currentTrace.getId();
188 return currentTraceId < newTraces.size() && currentTrace == newTraces.get(currentTraceId);
189 }
190
191 private static void addTrace(ArrayList<Trace> newTraces, Trace currentTrace) {
192 currentTrace.setId(newTraces.size());
193 newTraces.add(currentTrace);
194 }
195
196 }