| /* |
| * Copyright (c) 2009, 2011, Oracle and/or its affiliates. All rights reserved. |
| * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
| * |
| * This code is free software; you can redistribute it and/or modify it |
| * under the terms of the GNU General Public License version 2 only, as |
| * published by the Free Software Foundation. |
| * |
| * This code is distributed in the hope that it will be useful, but WITHOUT |
| * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
| * version 2 for more details (a copy is included in the LICENSE file that |
| * accompanied this code). |
| * |
| * You should have received a copy of the GNU General Public License version |
| * 2 along with this work; if not, write to the Free Software Foundation, |
| * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
| * |
| * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
| * or visit www.oracle.com if you need additional information or have any |
| * questions. |
| */ |
| package org.graalvm.compiler.phases.util; |
| |
| import org.graalvm.compiler.nodes.AbstractMergeNode; |
| |
| /** |
| * This class implements a worklist for dealing with blocks. The worklist can operate either as a |
| * stack (i.e. first-in / last-out), or as a sorted list, where blocks can be sorted by a supplied |
| * number. The latter usage lends itself naturally to iterative dataflow analysis problems. |
| */ |
| public class BlockWorkList { |
| |
| AbstractMergeNode[] workList; |
| int[] workListNumbers; |
| int workListIndex; |
| |
| /** |
| * Adds a block to this list in an unsorted fashion, like a stack. |
| * |
| * @param block the block to add |
| */ |
| public void add(AbstractMergeNode block) { |
| if (workList == null) { |
| // worklist not allocated yet |
| allocate(); |
| } else if (workListIndex == workList.length) { |
| // need to grow the worklist |
| grow(); |
| } |
| // put the block at the end of the array |
| workList[workListIndex++] = block; |
| } |
| |
| /** |
| * Adds a block to this list, sorted by the supplied number. The block with the lowest number is |
| * returned upon subsequent removes. |
| * |
| * @param block the block to add |
| * @param number the number used to sort the block |
| */ |
| public void addSorted(AbstractMergeNode block, int number) { |
| if (workList == null) { |
| // worklist not allocated yet |
| allocate(); |
| } else if (workListIndex == workList.length) { |
| // need to grow the worklist |
| grow(); |
| } |
| // put the block at the end of the array |
| workList[workListIndex] = block; |
| workListNumbers[workListIndex] = number; |
| workListIndex++; |
| int i = workListIndex - 2; |
| // push block towards the beginning of the array |
| for (; i >= 0; i--) { |
| int n = workListNumbers[i]; |
| if (n >= number) { |
| break; // already in the right position |
| } |
| workList[i + 1] = workList[i]; // bubble b down by one |
| workList[i] = block; // and overwrite its place with block |
| workListNumbers[i + 1] = n; // bubble n down by one |
| workListNumbers[i] = number; // and overwrite its place with number |
| } |
| } |
| |
| /** |
| * Removes the next block from this work list. If the blocks have been added in a sorted order, |
| * then the block with the lowest number is returned. Otherwise, the last block added is |
| * returned. |
| * |
| * @return the next block in the list |
| */ |
| public AbstractMergeNode removeFromWorkList() { |
| if (workListIndex != 0) { |
| return workList[--workListIndex]; |
| } |
| return null; |
| } |
| |
| /** |
| * Checks whether the list is empty. |
| * |
| * @return {@code true} if this list is empty |
| */ |
| public boolean isEmpty() { |
| return workListIndex == 0; |
| } |
| |
| private void allocate() { |
| workList = new AbstractMergeNode[5]; |
| workListNumbers = new int[5]; |
| } |
| |
| private void grow() { |
| int prevLength = workList.length; |
| AbstractMergeNode[] nworkList = new AbstractMergeNode[prevLength * 3]; |
| System.arraycopy(workList, 0, nworkList, 0, prevLength); |
| workList = nworkList; |
| |
| int[] nworkListNumbers = new int[prevLength * 3]; |
| System.arraycopy(workListNumbers, 0, nworkListNumbers, 0, prevLength); |
| workListNumbers = nworkListNumbers; |
| } |
| } |