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 package org.graalvm.compiler.phases.util;
  24 
  25 import org.graalvm.compiler.nodes.AbstractMergeNode;
  26 
  27 /**
  28  * This class implements a worklist for dealing with blocks. The worklist can operate either as a
  29  * stack (i.e. first-in / last-out), or as a sorted list, where blocks can be sorted by a supplied
  30  * number. The latter usage lends itself naturally to iterative dataflow analysis problems.
  31  */
  32 public class BlockWorkList {
  33 
  34     AbstractMergeNode[] workList;
  35     int[] workListNumbers;
  36     int workListIndex;
  37 
  38     /**
  39      * Adds a block to this list in an unsorted fashion, like a stack.
  40      *
  41      * @param block the block to add
  42      */
  43     public void add(AbstractMergeNode block) {
  44         if (workList == null) {
  45             // worklist not allocated yet
  46             allocate();
  47         } else if (workListIndex == workList.length) {
  48             // need to grow the worklist
  49             grow();
  50         }
  51         // put the block at the end of the array
  52         workList[workListIndex++] = block;
  53     }
  54 
  55     /**
  56      * Adds a block to this list, sorted by the supplied number. The block with the lowest number is
  57      * returned upon subsequent removes.
  58      *
  59      * @param block the block to add
  60      * @param number the number used to sort the block
  61      */
  62     public void addSorted(AbstractMergeNode block, int number) {
  63         if (workList == null) {
  64             // worklist not allocated yet
  65             allocate();
  66         } else if (workListIndex == workList.length) {
  67             // need to grow the worklist
  68             grow();
  69         }
  70         // put the block at the end of the array
  71         workList[workListIndex] = block;
  72         workListNumbers[workListIndex] = number;
  73         workListIndex++;
  74         int i = workListIndex - 2;
  75         // push block towards the beginning of the array
  76         for (; i >= 0; i--) {
  77             int n = workListNumbers[i];
  78             if (n >= number) {
  79                 break; // already in the right position
  80             }
  81             workList[i + 1] = workList[i]; // bubble b down by one
  82             workList[i] = block;           // and overwrite its place with block
  83             workListNumbers[i + 1] = n;    // bubble n down by one
  84             workListNumbers[i] = number;   // and overwrite its place with number
  85         }
  86     }
  87 
  88     /**
  89      * Removes the next block from this work list. If the blocks have been added in a sorted order,
  90      * then the block with the lowest number is returned. Otherwise, the last block added is
  91      * returned.
  92      *
  93      * @return the next block in the list
  94      */
  95     public AbstractMergeNode removeFromWorkList() {
  96         if (workListIndex != 0) {
  97             return workList[--workListIndex];
  98         }
  99         return null;
 100     }
 101 
 102     /**
 103      * Checks whether the list is empty.
 104      *
 105      * @return {@code true} if this list is empty
 106      */
 107     public boolean isEmpty() {
 108         return workListIndex == 0;
 109     }
 110 
 111     private void allocate() {
 112         workList = new AbstractMergeNode[5];
 113         workListNumbers = new int[5];
 114     }
 115 
 116     private void grow() {
 117         int prevLength = workList.length;
 118         AbstractMergeNode[] nworkList = new AbstractMergeNode[prevLength * 3];
 119         System.arraycopy(workList, 0, nworkList, 0, prevLength);
 120         workList = nworkList;
 121 
 122         int[] nworkListNumbers = new int[prevLength * 3];
 123         System.arraycopy(workListNumbers, 0, nworkListNumbers, 0, prevLength);
 124         workListNumbers = nworkListNumbers;
 125     }
 126 }