Mercurial > hg > truffle

comparison graal/com.oracle.max.graal.compiler/src/com/sun/c1x/util/BlockWorkList.java @ 2872:0341b6424579

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Project renaming.
author Thomas Wuerthinger <thomas@wuerthinger.net>
date Wed, 08 Jun 2011 08:42:25 +0200
parents graal/GraalCompiler/src/com/sun/c1x/util/BlockWorkList.java@d3fc4fe063bf
children
comparison
equal deleted inserted replaced
2871:d704eb526603 2872:0341b6424579
1 /*
2 * Copyright (c) 2009, 2009, 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 com.sun.c1x.util;
24
25 import com.sun.c1x.ir.*;
26
27 /**
28 * This class implements a worklist for dealing with blocks. The worklist can
29 * operate either as a stack (i.e. first-in / last-out), or as a sorted list,
30 * where blocks can be sorted by a supplied number. The latter usage lends itself
31 * naturally to iterative dataflow analysis problems.
32 *
33 * This implementation is not able to tell if a block is in the worklist already.
34 * Note that this implementation is slightly less efficient than the dedicated
35 * work list in {@link com.sun.c1x.graph.ScopeData}, because this worklist uses
36 * an externally supplied number.
37 *
38 * @author Ben L. Titzer
39 */
40 public class BlockWorkList {
41 Merge[] workList;
42 int[] workListNumbers;
43 int workListIndex;
44
45 /**
46 * Adds a block to this list in an unsorted fashion, like a stack.
47 * @param block the block to add
48 */
49 public void add(Merge block) {
50 if (workList == null) {
51 // worklist not allocated yet
52 allocate();
53 } else if (workListIndex == workList.length) {
54 // need to grow the worklist
55 grow();
56 }
57 // put the block at the end of the array
58 workList[workListIndex++] = block;
59 }
60
61 /**
62 * Adds a block to this list, sorted by the supplied number. The block
63 * with the lowest number is returned upon subsequent removes.
64 * @param block the block to add
65 * @param number the number used to sort the block
66 */
67 public void addSorted(Merge block, int number) {
68 if (workList == null) {
69 // worklist not allocated yet
70 allocate();
71 } else if (workListIndex == workList.length) {
72 // need to grow the worklist
73 grow();
74 }
75 // put the block at the end of the array
76 workList[workListIndex] = block;
77 workListNumbers[workListIndex] = number;
78 workListIndex++;
79 int i = workListIndex - 2;
80 // push block towards the beginning of the array
81 for (; i >= 0; i--) {
82 int n = workListNumbers[i];
83 if (n >= number) {
84 break; // already in the right position
85 }
86 workList[i + 1] = workList[i]; // bubble b down by one
87 workList[i] = block; // and overwrite its place with block
88 workListNumbers[i + 1] = n; // bubble n down by one
89 workListNumbers[i] = number; // and overwrite its place with number
90 }
91 }
92
93 /**
94 * Removes the next block from this work list. If the blocks have been added
95 * in a sorted order, then the block with the lowest number is returned. Otherwise,
96 * the last block added is returned.
97 * @return the next block in the list
98 */
99 public Merge removeFromWorkList() {
100 if (workListIndex != 0) {
101 return workList[--workListIndex];
102 }
103 return null;
104 }
105
106 /**
107 * Checks whether the list is empty.
108 * @return {@code true} if this list is empty
109 */
110 public boolean isEmpty() {
111 return workListIndex == 0;
112 }
113
114 private void allocate() {
115 workList = new Merge[5];
116 workListNumbers = new int[5];
117 }
118
119 private void grow() {
120 int prevLength = workList.length;
121 Merge[] nworkList = new Merge[prevLength * 3];
122 System.arraycopy(workList, 0, nworkList, 0, prevLength);
123 workList = nworkList;
124
125 int[] nworkListNumbers = new int[prevLength * 3];
126 System.arraycopy(workListNumbers, 0, nworkListNumbers, 0, prevLength);
127 workListNumbers = nworkListNumbers;
128 }
129 }