1 /*
   2  * Copyright (c) 2016, 2018, 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 }