Mercurial > hg > graal-compiler
comparison src/share/vm/opto/chaitin.cpp @ 12254:8c83625e3a53
8024646: Remove LRG_List container, replace it with GrowableArray
Summary: We already have GrowableArray, use it instead of LRG_List
Reviewed-by: kvn
author | adlertz |
---|---|
date | Thu, 12 Sep 2013 23:13:45 +0200 |
parents | 650868c062a9 |
children | 303c352ba1a8 15120a36272d |
comparison
equal
deleted
inserted
replaced
12192:34bd5e86aadb | 12254:8c83625e3a53 |
---|---|
120 return score + 1e10; // Likely no progress to spill | 120 return score + 1e10; // Likely no progress to spill |
121 | 121 |
122 return score; | 122 return score; |
123 } | 123 } |
124 | 124 |
125 LRG_List::LRG_List( uint max ) : _cnt(max), _max(max), _lidxs(NEW_RESOURCE_ARRAY(uint,max)) { | |
126 memset( _lidxs, 0, sizeof(uint)*max ); | |
127 } | |
128 | |
129 void LRG_List::extend( uint nidx, uint lidx ) { | |
130 _nesting.check(); | |
131 if( nidx >= _max ) { | |
132 uint size = 16; | |
133 while( size <= nidx ) size <<=1; | |
134 _lidxs = REALLOC_RESOURCE_ARRAY( uint, _lidxs, _max, size ); | |
135 _max = size; | |
136 } | |
137 while( _cnt <= nidx ) | |
138 _lidxs[_cnt++] = 0; | |
139 _lidxs[nidx] = lidx; | |
140 } | |
141 | |
142 #define NUMBUCKS 3 | 125 #define NUMBUCKS 3 |
143 | 126 |
144 // Straight out of Tarjan's union-find algorithm | 127 // Straight out of Tarjan's union-find algorithm |
145 uint LiveRangeMap::find_compress(uint lrg) { | 128 uint LiveRangeMap::find_compress(uint lrg) { |
146 uint cur = lrg; | 129 uint cur = lrg; |
147 uint next = _uf_map[cur]; | 130 uint next = _uf_map.at(cur); |
148 while (next != cur) { // Scan chain of equivalences | 131 while (next != cur) { // Scan chain of equivalences |
149 assert( next < cur, "always union smaller"); | 132 assert( next < cur, "always union smaller"); |
150 cur = next; // until find a fixed-point | 133 cur = next; // until find a fixed-point |
151 next = _uf_map[cur]; | 134 next = _uf_map.at(cur); |
152 } | 135 } |
153 | 136 |
154 // Core of union-find algorithm: update chain of | 137 // Core of union-find algorithm: update chain of |
155 // equivalences to be equal to the root. | 138 // equivalences to be equal to the root. |
156 while (lrg != next) { | 139 while (lrg != next) { |
157 uint tmp = _uf_map[lrg]; | 140 uint tmp = _uf_map.at(lrg); |
158 _uf_map.map(lrg, next); | 141 _uf_map.at_put(lrg, next); |
159 lrg = tmp; | 142 lrg = tmp; |
160 } | 143 } |
161 return lrg; | 144 return lrg; |
162 } | 145 } |
163 | 146 |
164 // Reset the Union-Find map to identity | 147 // Reset the Union-Find map to identity |
165 void LiveRangeMap::reset_uf_map(uint max_lrg_id) { | 148 void LiveRangeMap::reset_uf_map(uint max_lrg_id) { |
166 _max_lrg_id= max_lrg_id; | 149 _max_lrg_id= max_lrg_id; |
167 // Force the Union-Find mapping to be at least this large | 150 // Force the Union-Find mapping to be at least this large |
168 _uf_map.extend(_max_lrg_id, 0); | 151 _uf_map.at_put_grow(_max_lrg_id, 0); |
169 // Initialize it to be the ID mapping. | 152 // Initialize it to be the ID mapping. |
170 for (uint i = 0; i < _max_lrg_id; ++i) { | 153 for (uint i = 0; i < _max_lrg_id; ++i) { |
171 _uf_map.map(i, i); | 154 _uf_map.at_put(i, i); |
172 } | 155 } |
173 } | 156 } |
174 | 157 |
175 // Make all Nodes map directly to their final live range; no need for | 158 // Make all Nodes map directly to their final live range; no need for |
176 // the Union-Find mapping after this call. | 159 // the Union-Find mapping after this call. |
177 void LiveRangeMap::compress_uf_map_for_nodes() { | 160 void LiveRangeMap::compress_uf_map_for_nodes() { |
178 // For all Nodes, compress mapping | 161 // For all Nodes, compress mapping |
179 uint unique = _names.Size(); | 162 uint unique = _names.length(); |
180 for (uint i = 0; i < unique; ++i) { | 163 for (uint i = 0; i < unique; ++i) { |
181 uint lrg = _names[i]; | 164 uint lrg = _names.at(i); |
182 uint compressed_lrg = find(lrg); | 165 uint compressed_lrg = find(lrg); |
183 if (lrg != compressed_lrg) { | 166 if (lrg != compressed_lrg) { |
184 _names.map(i, compressed_lrg); | 167 _names.at_put(i, compressed_lrg); |
185 } | 168 } |
186 } | 169 } |
187 } | 170 } |
188 | 171 |
189 // Like Find above, but no path compress, so bad asymptotic behavior | 172 // Like Find above, but no path compress, so bad asymptotic behavior |
196 // brand new live ranges but have not told the allocator yet. | 179 // brand new live ranges but have not told the allocator yet. |
197 if (lrg >= _max_lrg_id) { | 180 if (lrg >= _max_lrg_id) { |
198 return lrg; | 181 return lrg; |
199 } | 182 } |
200 | 183 |
201 uint next = _uf_map[lrg]; | 184 uint next = _uf_map.at(lrg); |
202 while (next != lrg) { // Scan chain of equivalences | 185 while (next != lrg) { // Scan chain of equivalences |
203 assert(next < lrg, "always union smaller"); | 186 assert(next < lrg, "always union smaller"); |
204 lrg = next; // until find a fixed-point | 187 lrg = next; // until find a fixed-point |
205 next = _uf_map[lrg]; | 188 next = _uf_map.at(lrg); |
206 } | 189 } |
207 return next; | 190 return next; |
208 } | 191 } |
209 | 192 |
210 PhaseChaitin::PhaseChaitin(uint unique, PhaseCFG &cfg, Matcher &matcher) | 193 PhaseChaitin::PhaseChaitin(uint unique, PhaseCFG &cfg, Matcher &matcher) |
213 print_chaitin_statistics | 196 print_chaitin_statistics |
214 #else | 197 #else |
215 NULL | 198 NULL |
216 #endif | 199 #endif |
217 ) | 200 ) |
218 , _lrg_map(unique) | 201 , _lrg_map(Thread::current()->resource_area(), unique) |
219 , _live(0) | 202 , _live(0) |
220 , _spilled_once(Thread::current()->resource_area()) | 203 , _spilled_once(Thread::current()->resource_area()) |
221 , _spilled_twice(Thread::current()->resource_area()) | 204 , _spilled_twice(Thread::current()->resource_area()) |
222 , _lo_degree(0), _lo_stk_degree(0), _hi_degree(0), _simplified(0) | 205 , _lo_degree(0), _lo_stk_degree(0), _hi_degree(0), _simplified(0) |
223 , _oldphi(unique) | 206 , _oldphi(unique) |
690 // Pre-color to the zero live range, or pick virtual register | 673 // Pre-color to the zero live range, or pick virtual register |
691 const RegMask &rm = n->out_RegMask(); | 674 const RegMask &rm = n->out_RegMask(); |
692 _lrg_map.map(n->_idx, rm.is_NotEmpty() ? lr_counter++ : 0); | 675 _lrg_map.map(n->_idx, rm.is_NotEmpty() ? lr_counter++ : 0); |
693 } | 676 } |
694 } | 677 } |
678 | |
695 // Reset the Union-Find mapping to be identity | 679 // Reset the Union-Find mapping to be identity |
696 _lrg_map.reset_uf_map(lr_counter); | 680 _lrg_map.reset_uf_map(lr_counter); |
697 } | 681 } |
698 | 682 |
699 | 683 |