Mercurial > hg > graal-compiler
view graal/GraalCompiler/src/com/sun/c1x/util/BlockWorkList.java @ 2581:4a36a0bd6d18
added GraalGraph to classpath, Node as superclass of Value
author | Lukas Stadler <lukas.stadler@jku.at> |
---|---|
date | Thu, 05 May 2011 13:27:48 +0200 |
parents | 16b9a8b5ad39 |
children | d3fc4fe063bf |
line wrap: on
line source
/* * Copyright (c) 2009, 2009, 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 com.sun.c1x.util; import com.sun.c1x.ir.*; /** * 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. * * This implementation is not able to tell if a block is in the worklist already. * Note that this implementation is slightly less efficient than the dedicated * work list in {@link com.sun.c1x.graph.ScopeData}, because this worklist uses * an externally supplied number. * * @author Ben L. Titzer */ public class BlockWorkList { BlockBegin[] 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(BlockBegin 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(BlockBegin 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 BlockBegin 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 BlockBegin[5]; workListNumbers = new int[5]; } private void grow() { int prevLength = workList.length; BlockBegin[] nworkList = new BlockBegin[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; } }