1 /*
   2  * Copyright (c) 2015, 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.BitSet;
  29 import java.util.List;
  30 import java.util.PriorityQueue;
  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 starting at a trace head and keep adding successors as long as possible.
  39  */
  40 public final class UniDirectionalTraceBuilder {
  41 
  42     public static TraceBuilderResult computeTraces(DebugContext debug, AbstractBlockBase<?> startBlock, AbstractBlockBase<?>[] blocks, TrivialTracePredicate pred) {
  43         return new UniDirectionalTraceBuilder(blocks).build(debug, startBlock, blocks, pred);
  44     }
  45 
  46     private final PriorityQueue<AbstractBlockBase<?>> worklist;
  47     private final BitSet processed;
  48     /**
  49      * Contains the number of unprocessed predecessors for every {@link AbstractBlockBase#getId()
  50      * block}.
  51      */
  52     private final int[] blocked;
  53     private final Trace[] blockToTrace;
  54 
  55     private UniDirectionalTraceBuilder(AbstractBlockBase<?>[] blocks) {
  56         processed = new BitSet(blocks.length);
  57         worklist = new PriorityQueue<>(UniDirectionalTraceBuilder::compare);
  58         assert (worklist != null);
  59 
  60         blocked = new int[blocks.length];
  61         blockToTrace = new Trace[blocks.length];
  62         for (AbstractBlockBase<?> block : blocks) {
  63             blocked[block.getId()] = block.getPredecessorCount();
  64         }
  65     }
  66 
  67     private static int compare(AbstractBlockBase<?> a, AbstractBlockBase<?> b) {
  68         return Double.compare(b.getRelativeFrequency(), a.getRelativeFrequency());
  69     }
  70 
  71     private boolean processed(AbstractBlockBase<?> b) {
  72         return processed.get(b.getId());
  73     }
  74 
  75     @SuppressWarnings("try")
  76     private TraceBuilderResult build(DebugContext debug, AbstractBlockBase<?> startBlock, AbstractBlockBase<?>[] blocks, TrivialTracePredicate pred) {
  77         try (Indent indent = debug.logAndIndent("UniDirectionalTraceBuilder: start trace building: %s", startBlock)) {
  78             ArrayList<Trace> traces = buildTraces(debug, startBlock);
  79             return TraceBuilderResult.create(debug, blocks, traces, blockToTrace, pred);
  80         }
  81     }
  82 
  83     protected ArrayList<Trace> buildTraces(DebugContext debug, AbstractBlockBase<?> startBlock) {
  84         ArrayList<Trace> traces = new ArrayList<>();
  85         // add start block
  86         worklist.add(startBlock);
  87         // process worklist
  88         while (!worklist.isEmpty()) {
  89             AbstractBlockBase<?> block = worklist.poll();
  90             assert block != null;
  91             if (!processed(block)) {
  92                 Trace trace = new Trace(findTrace(debug, block));
  93                 for (AbstractBlockBase<?> traceBlock : trace.getBlocks()) {
  94                     blockToTrace[traceBlock.getId()] = trace;
  95                 }
  96                 trace.setId(traces.size());
  97                 traces.add(trace);
  98             }
  99         }
 100         return traces;
 101     }
 102 
 103     /**
 104      * Build a new trace starting at {@code block}.
 105      */
 106     @SuppressWarnings("try")
 107     private List<AbstractBlockBase<?>> findTrace(DebugContext debug, AbstractBlockBase<?> traceStart) {
 108         assert checkPredecessorsProcessed(traceStart);
 109         ArrayList<AbstractBlockBase<?>> trace = new ArrayList<>();
 110         int blockNumber = 0;
 111         try (Indent i = debug.logAndIndent("StartTrace: %s", traceStart)) {
 112             for (AbstractBlockBase<?> block = traceStart; block != null; block = selectNext(block)) {
 113                 debug.log("add %s (freq: %f)", block, block.getRelativeFrequency());
 114                 processed.set(block.getId());
 115                 trace.add(block);
 116                 unblock(block);
 117                 block.setLinearScanNumber(blockNumber++);
 118             }
 119         }
 120         return trace;
 121     }
 122 
 123     private boolean checkPredecessorsProcessed(AbstractBlockBase<?> block) {
 124         for (AbstractBlockBase<?> pred : block.getPredecessors()) {
 125             assert processed(pred) : "Predecessor unscheduled: " + pred;
 126         }
 127         return true;
 128     }
 129 
 130     /**
 131      * Decrease the {@link #blocked} count for all predecessors and add them to the worklist once
 132      * the count reaches 0.
 133      */
 134     private void unblock(AbstractBlockBase<?> block) {
 135         for (AbstractBlockBase<?> successor : block.getSuccessors()) {
 136             if (!processed(successor)) {
 137                 int blockCount = --blocked[successor.getId()];
 138                 assert blockCount >= 0;
 139                 if (blockCount == 0) {
 140                     worklist.add(successor);
 141                 }
 142             }
 143         }
 144     }
 145 
 146     /**
 147      * @return The unprocessed predecessor with the highest probability, or {@code null}.
 148      */
 149     private AbstractBlockBase<?> selectNext(AbstractBlockBase<?> block) {
 150         AbstractBlockBase<?> next = null;
 151         for (AbstractBlockBase<?> successor : block.getSuccessors()) {
 152             if (!processed(successor) && (next == null || successor.getRelativeFrequency() > next.getRelativeFrequency())) {
 153                 next = successor;
 154             }
 155         }
 156         return next;
 157     }
 158 }