Mercurial > hg > graal-jvmci-8
comparison graal/Compiler/src/com/sun/c1x/util/BlockWorkList.java @ 2507:9ec15d6914ca
Pull over of compiler from maxine repository.
author | Thomas Wuerthinger <thomas@wuerthinger.net> |
---|---|
date | Wed, 27 Apr 2011 11:43:22 +0200 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
2506:4a3bf8a5bf41 | 2507:9ec15d6914ca |
---|---|
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 BlockBegin[] 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(BlockBegin 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(BlockBegin 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 BlockBegin 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 BlockBegin[5]; | |
116 workListNumbers = new int[5]; | |
117 } | |
118 | |
119 private void grow() { | |
120 int prevLength = workList.length; | |
121 BlockBegin[] nworkList = new BlockBegin[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 } |