1 /*
   2  * Copyright (c) 2009, 2011, 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 package org.graalvm.compiler.core.common.alloc;
  25 
  26 import java.util.ArrayList;
  27 import java.util.BitSet;
  28 import java.util.Comparator;
  29 import java.util.List;
  30 import java.util.PriorityQueue;
  31 
  32 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
  33 import org.graalvm.compiler.core.common.cfg.Loop;
  34 
  35 /**
  36  * Computes an ordering of the block that can be used by the linear scan register allocator and the
  37  * machine code generator. The machine code generation order will start with the first block and
  38  * produce a straight sequence always following the most likely successor. Then it will continue
  39  * with the most likely path that was left out during this process. The process iteratively
  40  * continues until all blocks are scheduled. Additionally, it is guaranteed that all blocks of a
  41  * loop are scheduled before any block following the loop is scheduled.
  42  *
  43  * The machine code generator order includes reordering of loop headers such that the backward jump
  44  * is a conditional jump if there is only one loop end block. Additionally, the target of loop
  45  * backward jumps are always marked as aligned. Aligning the target of conditional jumps does not
  46  * bring a measurable benefit and is therefore avoided to keep the code size small.
  47  *
  48  * The linear scan register allocator order has an additional mechanism that prevents merge nodes
  49  * from being scheduled if there is at least one highly likely predecessor still unscheduled. This
  50  * increases the probability that the merge node and the corresponding predecessor are more closely
  51  * together in the schedule thus decreasing the probability for inserted phi moves. Also, the
  52  * algorithm sets the linear scan order number of the block that corresponds to its index in the
  53  * linear scan order.
  54  */
  55 public final class ComputeBlockOrder {
  56 
  57     /**
  58      * The initial capacities of the worklists used for iteratively finding the block order.
  59      */
  60     private static final int INITIAL_WORKLIST_CAPACITY = 10;
  61 
  62     /**
  63      * Divisor used for degrading the probability of the current path versus unscheduled paths at a
  64      * merge node when calculating the linear scan order. A high value means that predecessors of
  65      * merge nodes are more likely to be scheduled before the merge node.
  66      */
  67     private static final int PENALTY_VERSUS_UNSCHEDULED = 10;
  68 
  69     /**
  70      * Computes the block order used for the linear scan register allocator.
  71      *
  72      * @return sorted list of blocks
  73      */
  74     public static <T extends AbstractBlockBase<T>> AbstractBlockBase<?>[] computeLinearScanOrder(int blockCount, T startBlock) {
  75         List<T> order = new ArrayList<>();
  76         BitSet visitedBlocks = new BitSet(blockCount);
  77         PriorityQueue<T> worklist = initializeWorklist(startBlock, visitedBlocks);
  78         computeLinearScanOrder(order, worklist, visitedBlocks);
  79         assert checkOrder(order, blockCount);
  80         return order.toArray(new AbstractBlockBase<?>[0]);
  81     }
  82 
  83     /**
  84      * Computes the block order used for code emission.
  85      *
  86      * @return sorted list of blocks
  87      */
  88     public static <T extends AbstractBlockBase<T>> AbstractBlockBase<?>[] computeCodeEmittingOrder(int blockCount, T startBlock) {
  89         List<T> order = new ArrayList<>();
  90         BitSet visitedBlocks = new BitSet(blockCount);
  91         PriorityQueue<T> worklist = initializeWorklist(startBlock, visitedBlocks);
  92         computeCodeEmittingOrder(order, worklist, visitedBlocks);
  93         assert checkOrder(order, blockCount);
  94         return order.toArray(new AbstractBlockBase<?>[0]);
  95     }
  96 
  97     /**
  98      * Iteratively adds paths to the code emission block order.
  99      */
 100     private static <T extends AbstractBlockBase<T>> void computeCodeEmittingOrder(List<T> order, PriorityQueue<T> worklist, BitSet visitedBlocks) {
 101         while (!worklist.isEmpty()) {
 102             T nextImportantPath = worklist.poll();
 103             addPathToCodeEmittingOrder(nextImportantPath, order, worklist, visitedBlocks);
 104         }
 105     }
 106 
 107     /**
 108      * Iteratively adds paths to the linear scan block order.
 109      */
 110     private static <T extends AbstractBlockBase<T>> void computeLinearScanOrder(List<T> order, PriorityQueue<T> worklist, BitSet visitedBlocks) {
 111         while (!worklist.isEmpty()) {
 112             T nextImportantPath = worklist.poll();
 113             do {
 114                 nextImportantPath = addPathToLinearScanOrder(nextImportantPath, order, worklist, visitedBlocks);
 115             } while (nextImportantPath != null);
 116         }
 117     }
 118 
 119     /**
 120      * Initializes the priority queue used for the work list of blocks and adds the start block.
 121      */
 122     private static <T extends AbstractBlockBase<T>> PriorityQueue<T> initializeWorklist(T startBlock, BitSet visitedBlocks) {
 123         PriorityQueue<T> result = new PriorityQueue<>(INITIAL_WORKLIST_CAPACITY, new BlockOrderComparator<>());
 124         result.add(startBlock);
 125         visitedBlocks.set(startBlock.getId());
 126         return result;
 127     }
 128 
 129     /**
 130      * Add a linear path to the linear scan order greedily following the most likely successor.
 131      */
 132     private static <T extends AbstractBlockBase<T>> T addPathToLinearScanOrder(T block, List<T> order, PriorityQueue<T> worklist, BitSet visitedBlocks) {
 133         block.setLinearScanNumber(order.size());
 134         order.add(block);
 135         T mostLikelySuccessor = findAndMarkMostLikelySuccessor(block, visitedBlocks);
 136         enqueueSuccessors(block, worklist, visitedBlocks);
 137         if (mostLikelySuccessor != null) {
 138             if (!mostLikelySuccessor.isLoopHeader() && mostLikelySuccessor.getPredecessorCount() > 1) {
 139                 // We are at a merge. Check probabilities of predecessors that are not yet
 140                 // scheduled.
 141                 double unscheduledSum = 0.0;
 142                 for (T pred : mostLikelySuccessor.getPredecessors()) {
 143                     if (pred.getLinearScanNumber() == -1) {
 144                         unscheduledSum += pred.probability();
 145                     }
 146                 }
 147 
 148                 if (unscheduledSum > block.probability() / PENALTY_VERSUS_UNSCHEDULED) {
 149                     // Add this merge only after at least one additional predecessor gets scheduled.
 150                     visitedBlocks.clear(mostLikelySuccessor.getId());
 151                     return null;
 152                 }
 153             }
 154             return mostLikelySuccessor;
 155         }
 156         return null;
 157     }
 158 
 159     /**
 160      * Add a linear path to the code emission order greedily following the most likely successor.
 161      */
 162     private static <T extends AbstractBlockBase<T>> void addPathToCodeEmittingOrder(T initialBlock, List<T> order, PriorityQueue<T> worklist, BitSet visitedBlocks) {
 163         T block = initialBlock;
 164         while (block != null) {
 165             // Skip loop headers if there is only a single loop end block to
 166             // make the backward jump be a conditional jump.
 167             if (!skipLoopHeader(block)) {
 168 
 169                 // Align unskipped loop headers as they are the target of the backward jump.
 170                 if (block.isLoopHeader()) {
 171                     block.setAlign(true);
 172                 }
 173                 addBlock(block, order);
 174             }
 175 
 176             Loop<T> loop = block.getLoop();
 177             if (block.isLoopEnd() && skipLoopHeader(loop.getHeader())) {
 178 
 179                 // This is the only loop end of a skipped loop header.
 180                 // Add the header immediately afterwards.
 181                 addBlock(loop.getHeader(), order);
 182 
 183                 // Make sure the loop successors of the loop header are aligned
 184                 // as they are the target
 185                 // of the backward jump.
 186                 for (T successor : loop.getHeader().getSuccessors()) {
 187                     if (successor.getLoopDepth() == block.getLoopDepth()) {
 188                         successor.setAlign(true);
 189                     }
 190                 }
 191             }
 192 
 193             T mostLikelySuccessor = findAndMarkMostLikelySuccessor(block, visitedBlocks);
 194             enqueueSuccessors(block, worklist, visitedBlocks);
 195             block = mostLikelySuccessor;
 196         }
 197     }
 198 
 199     /**
 200      * Adds a block to the ordering.
 201      */
 202     private static <T extends AbstractBlockBase<T>> void addBlock(T header, List<T> order) {
 203         assert !order.contains(header) : "Cannot insert block twice";
 204         order.add(header);
 205     }
 206 
 207     /**
 208      * Find the highest likely unvisited successor block of a given block.
 209      */
 210     private static <T extends AbstractBlockBase<T>> T findAndMarkMostLikelySuccessor(T block, BitSet visitedBlocks) {
 211         T result = null;
 212         for (T successor : block.getSuccessors()) {
 213             assert successor.probability() >= 0.0 : "Probabilities must be positive";
 214             if (!visitedBlocks.get(successor.getId()) && successor.getLoopDepth() >= block.getLoopDepth() && (result == null || successor.probability() >= result.probability())) {
 215                 result = successor;
 216             }
 217         }
 218         if (result != null) {
 219             visitedBlocks.set(result.getId());
 220         }
 221         return result;
 222     }
 223 
 224     /**
 225      * Add successor blocks into the given work list if they are not already marked as visited.
 226      */
 227     private static <T extends AbstractBlockBase<T>> void enqueueSuccessors(T block, PriorityQueue<T> worklist, BitSet visitedBlocks) {
 228         for (T successor : block.getSuccessors()) {
 229             if (!visitedBlocks.get(successor.getId())) {
 230                 visitedBlocks.set(successor.getId());
 231                 worklist.add(successor);
 232             }
 233         }
 234     }
 235 
 236     /**
 237      * Skip the loop header block if the loop consists of more than one block and it has only a
 238      * single loop end block.
 239      */
 240     private static <T extends AbstractBlockBase<T>> boolean skipLoopHeader(AbstractBlockBase<T> block) {
 241         return (block.isLoopHeader() && !block.isLoopEnd() && block.getLoop().numBackedges() == 1);
 242     }
 243 
 244     /**
 245      * Checks that the ordering contains the expected number of blocks.
 246      */
 247     private static boolean checkOrder(List<? extends AbstractBlockBase<?>> order, int expectedBlockCount) {
 248         assert order.size() == expectedBlockCount : String.format("Number of blocks in ordering (%d) does not match expected block count (%d)", order.size(), expectedBlockCount);
 249         return true;
 250     }
 251 
 252     /**
 253      * Comparator for sorting blocks based on loop depth and probability.
 254      */
 255     private static class BlockOrderComparator<T extends AbstractBlockBase<T>> implements Comparator<T> {
 256         private static final double EPSILON = 1E-6;
 257 
 258         @Override
 259         public int compare(T a, T b) {
 260             // Loop blocks before any loop exit block. The only exception are blocks that are
 261             // (almost) impossible to reach.
 262             if (a.probability() > EPSILON && b.probability() > EPSILON) {
 263                 int diff = b.getLoopDepth() - a.getLoopDepth();
 264                 if (diff != 0) {
 265                     return diff;
 266                 }
 267             }
 268 
 269             // Blocks with high probability before blocks with low probability.
 270             if (a.probability() > b.probability()) {
 271                 return -1;
 272             } else {
 273                 return 1;
 274             }
 275         }
 276     }
 277 }