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