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.ArrayDeque; 28 import java.util.ArrayList; 29 import java.util.Arrays; 30 import java.util.BitSet; 31 import java.util.Collection; 32 import java.util.Deque; 33 34 import org.graalvm.compiler.core.common.alloc.TraceBuilderResult.TrivialTracePredicate; 35 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase; 36 import org.graalvm.compiler.debug.DebugContext; 37 import org.graalvm.compiler.debug.Indent; 38 39 /** 40 * Computes traces by selecting the unhandled block with the highest execution frequency and going 41 * in both directions, up and down, as long as possible. 42 */ 43 public final class BiDirectionalTraceBuilder { 44 45 public static TraceBuilderResult computeTraces(DebugContext debug, AbstractBlockBase<?> startBlock, AbstractBlockBase<?>[] blocks, TrivialTracePredicate pred) { 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(); 87 assert block != null; 88 if (!processed(block)) { 89 Trace trace = new Trace(findTrace(debug, block)); 90 for (AbstractBlockBase<?> traceBlock : trace.getBlocks()) { 91 blockToTrace[traceBlock.getId()] = trace; 92 } 93 trace.setId(traces.size()); 94 traces.add(trace); 95 } 96 } 97 return traces; 98 } 99 100 /** 101 * Build a new trace starting at {@code block}. 102 * 103 * @param debug 104 */ 105 @SuppressWarnings("try") 106 private Collection<AbstractBlockBase<?>> findTrace(DebugContext debug, AbstractBlockBase<?> initBlock) { 107 ArrayDeque<AbstractBlockBase<?>> trace = new ArrayDeque<>(); 108 try (Indent i = debug.logAndIndent("StartTrace: %s", initBlock)) { 109 try (Indent indentFront = debug.logAndIndent("Head:")) { 110 for (AbstractBlockBase<?> block = initBlock; block != null; block = selectPredecessor(block)) { 111 addBlockToTrace(debug, block); 112 trace.addFirst(block); 113 } 114 } 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 }