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 */ 23package org.graalvm.compiler.phases.util; 24 25import 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 */ 32public 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} 127