Mercurial > hg > graal-jvmci-8
comparison graal/Compiler/src/com/sun/c1x/opt/ValueMap.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, 2010, 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.opt; | |
24 | |
25 import com.sun.c1x.*; | |
26 import com.sun.c1x.ir.*; | |
27 | |
28 /** | |
29 * The {@code ValueMap} class implements a nested hashtable data structure | |
30 * for use in local and global value numbering. | |
31 * | |
32 * @author Ben L. Titzer | |
33 */ | |
34 public class ValueMap { | |
35 /** | |
36 * The class that forms hash chains. | |
37 */ | |
38 private static class Link { | |
39 final ValueMap map; | |
40 final int valueNumber; | |
41 final Instruction value; | |
42 final Link next; | |
43 | |
44 Link(ValueMap map, int valueNumber, Instruction value, Link next) { | |
45 this.map = map; | |
46 this.valueNumber = valueNumber; | |
47 this.value = value; | |
48 this.next = next; | |
49 } | |
50 } | |
51 | |
52 private final ValueMap parent; | |
53 | |
54 /** | |
55 * The table of links, indexed by hashing using the {@link Instruction#valueNumber() method}. | |
56 * The hash chains themselves may share parts of the parents' hash chains at the end. | |
57 */ | |
58 private Link[] table; | |
59 | |
60 /** | |
61 * Total number of entries in this map and the parent, used to compute unique ids. | |
62 */ | |
63 private int count; | |
64 | |
65 /** | |
66 * The maximum size allowed before triggering resizing. | |
67 */ | |
68 private int max; | |
69 | |
70 /** | |
71 * Creates a new value map. | |
72 */ | |
73 public ValueMap() { | |
74 parent = null; | |
75 table = new Link[19]; | |
76 } | |
77 | |
78 /** | |
79 * Creates a new value map with the specified parent value map. | |
80 * @param parent the parent value map | |
81 */ | |
82 public ValueMap(ValueMap parent) { | |
83 this.parent = parent; | |
84 this.table = parent.table.clone(); | |
85 this.count = parent.count; | |
86 this.max = table.length + table.length / 2; | |
87 } | |
88 | |
89 /** | |
90 * Inserts a value into the value map and looks up any previously available value. | |
91 * @param x the instruction to insert into the value map | |
92 * @return the value with which to replace the specified instruction, or the specified | |
93 * instruction if there is no replacement | |
94 */ | |
95 public Instruction findInsert(Instruction x) { | |
96 int valueNumber = x.valueNumber(); | |
97 if (valueNumber != 0) { | |
98 // value number != 0 means the instruction can be value numbered | |
99 int index = indexOf(valueNumber, table); | |
100 Link l = table[index]; | |
101 // hash and linear search | |
102 while (l != null) { | |
103 if (l.valueNumber == valueNumber && l.value.valueEqual(x)) { | |
104 return l.value; | |
105 } | |
106 l = l.next; | |
107 } | |
108 // not found; insert | |
109 table[index] = new Link(this, valueNumber, x, table[index]); | |
110 if (count > max) { | |
111 resize(); | |
112 } | |
113 } | |
114 return x; | |
115 } | |
116 | |
117 /** | |
118 * Kills all values in this local value map. | |
119 */ | |
120 public void killAll() { | |
121 assert parent == null : "should only be used for local value numbering"; | |
122 for (int i = 0; i < table.length; i++) { | |
123 table[i] = null; | |
124 } | |
125 count = 0; | |
126 } | |
127 | |
128 private void resize() { | |
129 C1XMetrics.ValueMapResizes++; | |
130 Link[] ntable = new Link[table.length * 3 + 4]; | |
131 if (parent != null) { | |
132 // first add all the parent's entries by cloning them | |
133 for (int i = 0; i < table.length; i++) { | |
134 Link l = table[i]; | |
135 while (l != null && l.map == this) { | |
136 l = l.next; // skip entries in this map | |
137 } | |
138 while (l != null) { | |
139 // copy entries from parent | |
140 int index = indexOf(l.valueNumber, ntable); | |
141 ntable[index] = new Link(l.map, l.valueNumber, l.value, ntable[index]); | |
142 l = l.next; | |
143 } | |
144 } | |
145 } | |
146 | |
147 for (int i = 0; i < table.length; i++) { | |
148 Link l = table[i]; | |
149 // now add all the entries from this map | |
150 while (l != null && l.map == this) { | |
151 int index = indexOf(l.valueNumber, ntable); | |
152 ntable[index] = new Link(l.map, l.valueNumber, l.value, ntable[index]); | |
153 l = l.next; | |
154 } | |
155 } | |
156 table = ntable; | |
157 max = table.length + table.length / 2; | |
158 } | |
159 | |
160 private int indexOf(int valueNumber, Link[] t) { | |
161 return (valueNumber & 0x7fffffff) % t.length; | |
162 } | |
163 } |