91 }
92
93 //------------------------------hash_find--------------------------------------
94 // Find in hash table
95 Node *NodeHash::hash_find( const Node *n ) {
96 // ((Node*)n)->set_hash( n->hash() );
97 uint hash = n->hash();
98 if (hash == Node::NO_HASH) {
99 NOT_PRODUCT( _lookup_misses++ );
100 return NULL;
101 }
102 uint key = hash & (_max-1);
103 uint stride = key | 0x01;
104 NOT_PRODUCT( _look_probes++ );
105 Node *k = _table[key]; // Get hashed value
106 if( !k ) { // ?Miss?
107 NOT_PRODUCT( _lookup_misses++ );
108 return NULL; // Miss!
109 }
110
111 int op = n->Opcode();
112 uint req = n->req();
113 while( 1 ) { // While probing hash table
114 if( k->req() == req && // Same count of inputs
115 k->Opcode() == op ) { // Same Opcode
116 for( uint i=0; i<req; i++ )
117 if( n->in(i)!=k->in(i)) // Different inputs?
118 goto collision; // "goto" is a speed hack...
119 if( n->cmp(*k) ) { // Check for any special bits
120 NOT_PRODUCT( _lookup_hits++ );
121 return k; // Hit!
122 }
123 }
124 collision:
125 NOT_PRODUCT( _look_probes++ );
126 key = (key + stride/*7*/) & (_max-1); // Stride through table with relative prime
127 k = _table[key]; // Get hashed value
128 if( !k ) { // ?Miss?
129 NOT_PRODUCT( _lookup_misses++ );
130 return NULL; // Miss!
131 }
143 if (hash == Node::NO_HASH) {
144 NOT_PRODUCT( _lookup_misses++ );
145 return NULL;
146 }
147 uint key = hash & (_max-1);
148 uint stride = key | 0x01; // stride must be relatively prime to table siz
149 uint first_sentinel = 0; // replace a sentinel if seen.
150 NOT_PRODUCT( _look_probes++ );
151 Node *k = _table[key]; // Get hashed value
152 if( !k ) { // ?Miss?
153 NOT_PRODUCT( _lookup_misses++ );
154 _table[key] = n; // Insert into table!
155 debug_only(n->enter_hash_lock()); // Lock down the node while in the table.
156 check_grow(); // Grow table if insert hit limit
157 return NULL; // Miss!
158 }
159 else if( k == _sentinel ) {
160 first_sentinel = key; // Can insert here
161 }
162
163 int op = n->Opcode();
164 uint req = n->req();
165 while( 1 ) { // While probing hash table
166 if( k->req() == req && // Same count of inputs
167 k->Opcode() == op ) { // Same Opcode
168 for( uint i=0; i<req; i++ )
169 if( n->in(i)!=k->in(i)) // Different inputs?
170 goto collision; // "goto" is a speed hack...
171 if( n->cmp(*k) ) { // Check for any special bits
172 NOT_PRODUCT( _lookup_hits++ );
173 return k; // Hit!
174 }
175 }
176 collision:
177 NOT_PRODUCT( _look_probes++ );
178 key = (key + stride) & (_max-1); // Stride through table w/ relative prime
179 k = _table[key]; // Get hashed value
180 if( !k ) { // ?Miss?
181 NOT_PRODUCT( _lookup_misses++ );
182 key = (first_sentinel == 0) ? key : first_sentinel; // ?saw sentinel?
183 _table[key] = n; // Insert into table!
|
91 }
92
93 //------------------------------hash_find--------------------------------------
94 // Find in hash table
95 Node *NodeHash::hash_find( const Node *n ) {
96 // ((Node*)n)->set_hash( n->hash() );
97 uint hash = n->hash();
98 if (hash == Node::NO_HASH) {
99 NOT_PRODUCT( _lookup_misses++ );
100 return NULL;
101 }
102 uint key = hash & (_max-1);
103 uint stride = key | 0x01;
104 NOT_PRODUCT( _look_probes++ );
105 Node *k = _table[key]; // Get hashed value
106 if( !k ) { // ?Miss?
107 NOT_PRODUCT( _lookup_misses++ );
108 return NULL; // Miss!
109 }
110
111 uint op = n->Opcode();
112 uint req = n->req();
113 while( 1 ) { // While probing hash table
114 if( k->req() == req && // Same count of inputs
115 k->Opcode() == op ) { // Same Opcode
116 for( uint i=0; i<req; i++ )
117 if( n->in(i)!=k->in(i)) // Different inputs?
118 goto collision; // "goto" is a speed hack...
119 if( n->cmp(*k) ) { // Check for any special bits
120 NOT_PRODUCT( _lookup_hits++ );
121 return k; // Hit!
122 }
123 }
124 collision:
125 NOT_PRODUCT( _look_probes++ );
126 key = (key + stride/*7*/) & (_max-1); // Stride through table with relative prime
127 k = _table[key]; // Get hashed value
128 if( !k ) { // ?Miss?
129 NOT_PRODUCT( _lookup_misses++ );
130 return NULL; // Miss!
131 }
143 if (hash == Node::NO_HASH) {
144 NOT_PRODUCT( _lookup_misses++ );
145 return NULL;
146 }
147 uint key = hash & (_max-1);
148 uint stride = key | 0x01; // stride must be relatively prime to table siz
149 uint first_sentinel = 0; // replace a sentinel if seen.
150 NOT_PRODUCT( _look_probes++ );
151 Node *k = _table[key]; // Get hashed value
152 if( !k ) { // ?Miss?
153 NOT_PRODUCT( _lookup_misses++ );
154 _table[key] = n; // Insert into table!
155 debug_only(n->enter_hash_lock()); // Lock down the node while in the table.
156 check_grow(); // Grow table if insert hit limit
157 return NULL; // Miss!
158 }
159 else if( k == _sentinel ) {
160 first_sentinel = key; // Can insert here
161 }
162
163 uint op = n->Opcode();
164 uint req = n->req();
165 while( 1 ) { // While probing hash table
166 if( k->req() == req && // Same count of inputs
167 k->Opcode() == op ) { // Same Opcode
168 for( uint i=0; i<req; i++ )
169 if( n->in(i)!=k->in(i)) // Different inputs?
170 goto collision; // "goto" is a speed hack...
171 if( n->cmp(*k) ) { // Check for any special bits
172 NOT_PRODUCT( _lookup_hits++ );
173 return k; // Hit!
174 }
175 }
176 collision:
177 NOT_PRODUCT( _look_probes++ );
178 key = (key + stride) & (_max-1); // Stride through table w/ relative prime
179 k = _table[key]; // Get hashed value
180 if( !k ) { // ?Miss?
181 NOT_PRODUCT( _lookup_misses++ );
182 key = (first_sentinel == 0) ? key : first_sentinel; // ?saw sentinel?
183 _table[key] = n; // Insert into table!
|