Mercurial > hg > truffle
comparison src/share/vm/opto/chaitin.hpp @ 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 | 4b2838704fd5 |
| children | d8a449d2f5b2 |
comparison
equal
deleted
inserted
replaced
| 12192:34bd5e86aadb | 12254:8c83625e3a53 |
|---|---|
| 281 // Map from Nodes to live ranges | 281 // Map from Nodes to live ranges |
| 282 LRG_List _names; | 282 LRG_List _names; |
| 283 | 283 |
| 284 // Straight out of Tarjan's union-find algorithm | 284 // Straight out of Tarjan's union-find algorithm |
| 285 uint find_compress(const Node *node) { | 285 uint find_compress(const Node *node) { |
| 286 uint lrg_id = find_compress(_names[node->_idx]); | 286 uint lrg_id = find_compress(_names.at(node->_idx)); |
| 287 _names.map(node->_idx, lrg_id); | 287 _names.at_put(node->_idx, lrg_id); |
| 288 return lrg_id; | 288 return lrg_id; |
| 289 } | 289 } |
| 290 | 290 |
| 291 uint find_compress(uint lrg); | 291 uint find_compress(uint lrg); |
| 292 | 292 |
| 303 void set_max_lrg_id(uint max_lrg_id) { | 303 void set_max_lrg_id(uint max_lrg_id) { |
| 304 _max_lrg_id = max_lrg_id; | 304 _max_lrg_id = max_lrg_id; |
| 305 } | 305 } |
| 306 | 306 |
| 307 uint size() const { | 307 uint size() const { |
| 308 return _names.Size(); | 308 return _names.length(); |
| 309 } | 309 } |
| 310 | 310 |
| 311 uint live_range_id(uint idx) const { | 311 uint live_range_id(uint idx) const { |
| 312 return _names[idx]; | 312 return _names.at(idx); |
| 313 } | 313 } |
| 314 | 314 |
| 315 uint live_range_id(const Node *node) const { | 315 uint live_range_id(const Node *node) const { |
| 316 return _names[node->_idx]; | 316 return _names.at(node->_idx); |
| 317 } | 317 } |
| 318 | 318 |
| 319 uint uf_live_range_id(uint lrg_id) const { | 319 uint uf_live_range_id(uint lrg_id) const { |
| 320 return _uf_map[lrg_id]; | 320 return _uf_map.at(lrg_id); |
| 321 } | 321 } |
| 322 | 322 |
| 323 void map(uint idx, uint lrg_id) { | 323 void map(uint idx, uint lrg_id) { |
| 324 _names.map(idx, lrg_id); | 324 _names.at_put(idx, lrg_id); |
| 325 } | 325 } |
| 326 | 326 |
| 327 void uf_map(uint dst_lrg_id, uint src_lrg_id) { | 327 void uf_map(uint dst_lrg_id, uint src_lrg_id) { |
| 328 _uf_map.map(dst_lrg_id, src_lrg_id); | 328 _uf_map.at_put(dst_lrg_id, src_lrg_id); |
| 329 } | 329 } |
| 330 | 330 |
| 331 void extend(uint idx, uint lrg_id) { | 331 void extend(uint idx, uint lrg_id) { |
| 332 _names.extend(idx, lrg_id); | 332 _names.at_put_grow(idx, lrg_id); |
| 333 } | 333 } |
| 334 | 334 |
| 335 void uf_extend(uint dst_lrg_id, uint src_lrg_id) { | 335 void uf_extend(uint dst_lrg_id, uint src_lrg_id) { |
| 336 _uf_map.extend(dst_lrg_id, src_lrg_id); | 336 _uf_map.at_put_grow(dst_lrg_id, src_lrg_id); |
| 337 } | 337 } |
| 338 | 338 |
| 339 LiveRangeMap(uint unique) | 339 LiveRangeMap(Arena* arena, uint unique) |
| 340 : _names(unique) | 340 : _names(arena, unique, unique, 0) |
| 341 , _uf_map(unique) | 341 , _uf_map(arena, unique, unique, 0) |
| 342 , _max_lrg_id(0) {} | 342 , _max_lrg_id(0) {} |
| 343 | 343 |
| 344 uint find_id( const Node *n ) { | 344 uint find_id( const Node *n ) { |
| 345 uint retval = live_range_id(n); | 345 uint retval = live_range_id(n); |
| 346 assert(retval == find(n),"Invalid node to lidx mapping"); | 346 assert(retval == find(n),"Invalid node to lidx mapping"); |
| 353 // Make all Nodes map directly to their final live range; no need for | 353 // Make all Nodes map directly to their final live range; no need for |
| 354 // the Union-Find mapping after this call. | 354 // the Union-Find mapping after this call. |
| 355 void compress_uf_map_for_nodes(); | 355 void compress_uf_map_for_nodes(); |
| 356 | 356 |
| 357 uint find(uint lidx) { | 357 uint find(uint lidx) { |
| 358 uint uf_lidx = _uf_map[lidx]; | 358 uint uf_lidx = _uf_map.at(lidx); |
| 359 return (uf_lidx == lidx) ? uf_lidx : find_compress(lidx); | 359 return (uf_lidx == lidx) ? uf_lidx : find_compress(lidx); |
| 360 } | 360 } |
| 361 | 361 |
| 362 // Convert a Node into a Live Range Index - a lidx | 362 // Convert a Node into a Live Range Index - a lidx |
| 363 uint find(const Node *node) { | 363 uint find(const Node *node) { |
| 364 uint lidx = live_range_id(node); | 364 uint lidx = live_range_id(node); |
| 365 uint uf_lidx = _uf_map[lidx]; | 365 uint uf_lidx = _uf_map.at(lidx); |
| 366 return (uf_lidx == lidx) ? uf_lidx : find_compress(node); | 366 return (uf_lidx == lidx) ? uf_lidx : find_compress(node); |
| 367 } | 367 } |
| 368 | 368 |
| 369 // Like Find above, but no path compress, so bad asymptotic behavior | 369 // Like Find above, but no path compress, so bad asymptotic behavior |
| 370 uint find_const(uint lrg) const; | 370 uint find_const(uint lrg) const; |
| 371 | 371 |
| 372 // Like Find above, but no path compress, so bad asymptotic behavior | 372 // Like Find above, but no path compress, so bad asymptotic behavior |
| 373 uint find_const(const Node *node) const { | 373 uint find_const(const Node *node) const { |
| 374 if(node->_idx >= _names.Size()) { | 374 if(node->_idx >= (uint)_names.length()) { |
| 375 return 0; // not mapped, usual for debug dump | 375 return 0; // not mapped, usual for debug dump |
| 376 } | 376 } |
| 377 return find_const(_names[node->_idx]); | 377 return find_const(_names.at(node->_idx)); |
| 378 } | 378 } |
| 379 }; | 379 }; |
| 380 | 380 |
| 381 //------------------------------Chaitin---------------------------------------- | 381 //------------------------------Chaitin---------------------------------------- |
| 382 // Briggs-Chaitin style allocation, mostly. | 382 // Briggs-Chaitin style allocation, mostly. |