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