001/*
002 * Copyright (c) 2009, 2011, Oracle and/or its affiliates. All rights reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation.
008 *
009 * This code is distributed in the hope that it will be useful, but WITHOUT
010 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
011 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
012 * version 2 for more details (a copy is included in the LICENSE file that
013 * accompanied this code).
014 *
015 * You should have received a copy of the GNU General Public License version
016 * 2 along with this work; if not, write to the Free Software Foundation,
017 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
018 *
019 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
020 * or visit www.oracle.com if you need additional information or have any
021 * questions.
022 */
023package com.oracle.graal.phases.util;
024
025import com.oracle.graal.nodes.*;
026
027/**
028 * This class implements a worklist for dealing with blocks. The worklist can operate either as a
029 * stack (i.e. first-in / last-out), or as a sorted list, where blocks can be sorted by a supplied
030 * number. The latter usage lends itself naturally to iterative dataflow analysis problems.
031 */
032public class BlockWorkList {
033
034    AbstractMergeNode[] workList;
035    int[] workListNumbers;
036    int workListIndex;
037
038    /**
039     * Adds a block to this list in an unsorted fashion, like a stack.
040     *
041     * @param block the block to add
042     */
043    public void add(AbstractMergeNode block) {
044        if (workList == null) {
045            // worklist not allocated yet
046            allocate();
047        } else if (workListIndex == workList.length) {
048            // need to grow the worklist
049            grow();
050        }
051        // put the block at the end of the array
052        workList[workListIndex++] = block;
053    }
054
055    /**
056     * Adds a block to this list, sorted by the supplied number. The block with the lowest number is
057     * returned upon subsequent removes.
058     *
059     * @param block the block to add
060     * @param number the number used to sort the block
061     */
062    public void addSorted(AbstractMergeNode block, int number) {
063        if (workList == null) {
064            // worklist not allocated yet
065            allocate();
066        } else if (workListIndex == workList.length) {
067            // need to grow the worklist
068            grow();
069        }
070        // put the block at the end of the array
071        workList[workListIndex] = block;
072        workListNumbers[workListIndex] = number;
073        workListIndex++;
074        int i = workListIndex - 2;
075        // push block towards the beginning of the array
076        for (; i >= 0; i--) {
077            int n = workListNumbers[i];
078            if (n >= number) {
079                break; // already in the right position
080            }
081            workList[i + 1] = workList[i]; // bubble b down by one
082            workList[i] = block;           // and overwrite its place with block
083            workListNumbers[i + 1] = n;    // bubble n down by one
084            workListNumbers[i] = number;   // and overwrite its place with number
085        }
086    }
087
088    /**
089     * Removes the next block from this work list. If the blocks have been added in a sorted order,
090     * then the block with the lowest number is returned. Otherwise, the last block added is
091     * returned.
092     *
093     * @return the next block in the list
094     */
095    public AbstractMergeNode removeFromWorkList() {
096        if (workListIndex != 0) {
097            return workList[--workListIndex];
098        }
099        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}