Mercurial > hg > graal-compiler

annotate graal/Compiler/src/com/sun/c1x/util/BlockWorkList.java @ 2507:9ec15d6914ca

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Pull over of compiler from maxine repository.
author Thomas Wuerthinger <thomas@wuerthinger.net>
date Wed, 27 Apr 2011 11:43:22 +0200
parents
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
2507
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
1 /*
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
2 * Copyright (c) 2009, 2009, Oracle and/or its affiliates. All rights reserved.
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
4 *
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
5 * This code is free software; you can redistribute it and/or modify it
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
6 * under the terms of the GNU General Public License version 2 only, as
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
7 * published by the Free Software Foundation.
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
8 *
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
9 * This code is distributed in the hope that it will be useful, but WITHOUT
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
12 * version 2 for more details (a copy is included in the LICENSE file that
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
13 * accompanied this code).
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
14 *
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
15 * You should have received a copy of the GNU General Public License version
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
16 * 2 along with this work; if not, write to the Free Software Foundation,
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
18 *
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
20 * or visit www.oracle.com if you need additional information or have any
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
21 * questions.
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
22 */
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
23 package com.sun.c1x.util;
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
24
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
25 import com.sun.c1x.ir.*;
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
26
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
27 /**
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
28 * This class implements a worklist for dealing with blocks. The worklist can
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
29 * operate either as a stack (i.e. first-in / last-out), or as a sorted list,
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
30 * where blocks can be sorted by a supplied number. The latter usage lends itself
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
31 * naturally to iterative dataflow analysis problems.
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
32 *
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
33 * This implementation is not able to tell if a block is in the worklist already.
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
34 * Note that this implementation is slightly less efficient than the dedicated
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
35 * work list in {@link com.sun.c1x.graph.ScopeData}, because this worklist uses
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
36 * an externally supplied number.
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
37 *
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
38 * @author Ben L. Titzer
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
39 */
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
40 public class BlockWorkList {
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
41 BlockBegin[] workList;
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
42 int[] workListNumbers;
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
43 int workListIndex;
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
44
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
45 /**
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
46 * Adds a block to this list in an unsorted fashion, like a stack.
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
47 * @param block the block to add
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
48 */
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
49 public void add(BlockBegin block) {
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
50 if (workList == null) {
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
51 // worklist not allocated yet
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
52 allocate();
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
53 } else if (workListIndex == workList.length) {
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
54 // need to grow the worklist
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
55 grow();
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
56 }
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
57 // put the block at the end of the array
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
58 workList[workListIndex++] = block;
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
59 }
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
60
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
61 /**
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
62 * Adds a block to this list, sorted by the supplied number. The block
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
63 * with the lowest number is returned upon subsequent removes.
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
64 * @param block the block to add
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
65 * @param number the number used to sort the block
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
66 */
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
67 public void addSorted(BlockBegin block, int number) {
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
68 if (workList == null) {
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
69 // worklist not allocated yet
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
70 allocate();
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
71 } else if (workListIndex == workList.length) {
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
72 // need to grow the worklist
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
73 grow();
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
74 }
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
75 // put the block at the end of the array
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
76 workList[workListIndex] = block;
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
77 workListNumbers[workListIndex] = number;
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
78 workListIndex++;
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
79 int i = workListIndex - 2;
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
80 // push block towards the beginning of the array
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
81 for (; i >= 0; i--) {
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
82 int n = workListNumbers[i];
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
83 if (n >= number) {
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
84 break; // already in the right position
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
85 }
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
86 workList[i + 1] = workList[i]; // bubble b down by one
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
87 workList[i] = block; // and overwrite its place with block
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
88 workListNumbers[i + 1] = n; // bubble n down by one
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
89 workListNumbers[i] = number; // and overwrite its place with number
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
90 }
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
91 }
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
92
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
93 /**
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
94 * Removes the next block from this work list. If the blocks have been added
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
95 * in a sorted order, then the block with the lowest number is returned. Otherwise,
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
96 * the last block added is returned.
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
97 * @return the next block in the list
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
98 */
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
99 public BlockBegin removeFromWorkList() {
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
100 if (workListIndex != 0) {
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
101 return workList[--workListIndex];
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
102 }
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
103 return null;
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
104 }
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
105
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
106 /**
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
107 * Checks whether the list is empty.
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
108 * @return {@code true} if this list is empty
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
109 */
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
110 public boolean isEmpty() {
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
111 return workListIndex == 0;
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
112 }
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
113
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
114 private void allocate() {
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
115 workList = new BlockBegin[5];
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
116 workListNumbers = new int[5];
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
117 }
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
118
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
119 private void grow() {
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
120 int prevLength = workList.length;
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
121 BlockBegin[] nworkList = new BlockBegin[prevLength * 3];
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
122 System.arraycopy(workList, 0, nworkList, 0, prevLength);
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
123 workList = nworkList;
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
124
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
125 int[] nworkListNumbers = new int[prevLength * 3];
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
126 System.arraycopy(workListNumbers, 0, nworkListNumbers, 0, prevLength);
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
127 workListNumbers = nworkListNumbers;
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
128 }
9ec15d6914ca Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
129 }