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. |