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.ArrayDeque;
  26 import java.util.ArrayList;
  27 import java.util.Arrays;
  28 import java.util.BitSet;
  29 import java.util.Collection;
  30 import java.util.Deque;
  31 
  32 import org.graalvm.compiler.core.common.alloc.TraceBuilderResult.TrivialTracePredicate;
  33 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
  34 import org.graalvm.compiler.debug.Debug;
  35 import 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  */
  41 public final class BiDirectionalTraceBuilder {
  42 
  43     public static TraceBuilderResult computeTraces(AbstractBlockBase<?> startBlock, AbstractBlockBase<?>[] blocks, TrivialTracePredicate pred) {
  44         return new BiDirectionalTraceBuilder(blocks).build(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(AbstractBlockBase<?> startBlock, AbstractBlockBase<?>[] blocks, TrivialTracePredicate pred) {
  73         try (Indent indent = Debug.logAndIndent("BiDirectionalTraceBuilder: start trace building")) {
  74             ArrayList<Trace> traces = buildTraces();
  75             assert traces.get(0).getBlocks()[0].equals(startBlock) : "The first traces always contains the start block";
  76             return TraceBuilderResult.create(blocks, traces, blockToTrace, pred);
  77         }
  78     }
  79 
  80     protected ArrayList<Trace> buildTraces() {
  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(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     @SuppressWarnings("try")
 102     private Collection<AbstractBlockBase<?>> startTrace(AbstractBlockBase<?> block) {
 103         ArrayDeque<AbstractBlockBase<?>> trace = new ArrayDeque<>();
 104         try (Indent i = Debug.logAndIndent("StartTrace: %s", block)) {
 105             try (Indent indentFront = Debug.logAndIndent("Head:")) {
 106                 for (AbstractBlockBase<?> currentBlock = block; currentBlock != null; currentBlock = selectPredecessor(currentBlock)) {
 107                     addBlockToTrace(currentBlock);
 108                     trace.addFirst(currentBlock);
 109                 }
 110             }
 111             /* Number head blocks. Can not do this in the loop as we go backwards. */
 112             int blockNr = 0;
 113             for (AbstractBlockBase<?> b : trace) {
 114                 b.setLinearScanNumber(blockNr++);
 115             }
 116 
 117             try (Indent indentBack = Debug.logAndIndent("Tail:")) {
 118                 for (AbstractBlockBase<?> currentBlock = selectSuccessor(block); currentBlock != null; currentBlock = selectSuccessor(currentBlock)) {
 119                     addBlockToTrace(currentBlock);
 120                     trace.addLast(currentBlock);
 121                     /* This time we can number the blocks immediately as we go forwards. */
 122                     currentBlock.setLinearScanNumber(blockNr++);
 123                 }
 124             }
 125         }
 126         Debug.log("Trace: %s", trace);
 127         return trace;
 128     }
 129 
 130     private void addBlockToTrace(AbstractBlockBase<?> currentBlock) {
 131         Debug.log("add %s (prob: %f)", currentBlock, currentBlock.probability());
 132         processed.set(currentBlock.getId());
 133     }
 134 
 135     /**
 136      * @return The unprocessed predecessor with the highest probability, or {@code null}.
 137      */
 138     private AbstractBlockBase<?> selectPredecessor(AbstractBlockBase<?> currentBlock) {
 139         AbstractBlockBase<?> next = null;
 140         for (AbstractBlockBase<?> pred : currentBlock.getPredecessors()) {
 141             if (!processed(pred) && !isBackEdge(pred, currentBlock) && (next == null || pred.probability() > next.probability())) {
 142                 next = pred;
 143             }
 144         }
 145         return next;
 146     }
 147 
 148     private static boolean isBackEdge(AbstractBlockBase<?> from, AbstractBlockBase<?> to) {
 149         assert Arrays.asList(from.getSuccessors()).contains(to) : "No edge from " + from + " to " + to;
 150         return from.isLoopEnd() && to.isLoopHeader() && from.getLoop().equals(to.getLoop());
 151     }

  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.ArrayDeque;
  26 import java.util.ArrayList;
  27 import java.util.Arrays;
  28 import java.util.BitSet;
  29 import java.util.Collection;
  30 import java.util.Deque;
  31 
  32 import org.graalvm.compiler.core.common.alloc.TraceBuilderResult.TrivialTracePredicate;
  33 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
  34 import org.graalvm.compiler.debug.DebugContext;
  35 import 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  */
  41 public 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     }