Mercurial > hg > graal-jvmci-8

comparison graal/Compiler/src/com/sun/c1x/opt/ValueMap.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
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 }