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.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(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();
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 (prob: %f)", block, block.probability());
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.probability() > next.probability())) {
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.probability() > next.probability())) {
164 next = succ;
165 }
166 }
167 return next;
168 }
169 }
|
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();
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 }
|