Mercurial > hg > truffle
comparison src/share/vm/opto/chaitin.hpp @ 10408:836a62f43af9
Merge with http://hg.openjdk.java.net/hsx/hsx25/hotspot/
author | Doug Simon <doug.simon@oracle.com> |
---|---|
date | Wed, 19 Jun 2013 10:45:56 +0200 |
parents | 8373c19be854 |
children | 4b2838704fd5 |
comparison
equal
deleted
inserted
replaced
10086:e0fb8a213650 | 10408:836a62f43af9 |
---|---|
263 | 263 |
264 // Compute effective degree as the sum of neighbors' _sizes. | 264 // Compute effective degree as the sum of neighbors' _sizes. |
265 int effective_degree( uint lidx ) const; | 265 int effective_degree( uint lidx ) const; |
266 }; | 266 }; |
267 | 267 |
268 // TEMPORARILY REPLACED WITH COMMAND LINE FLAG | 268 // The LiveRangeMap class is responsible for storing node to live range id mapping. |
269 | 269 // Each node is mapped to a live range id (a virtual register). Nodes that are |
270 //// !!!!! Magic Constants need to move into ad file | 270 // not considered for register allocation are given live range id 0. |
271 #ifdef SPARC | 271 class LiveRangeMap VALUE_OBJ_CLASS_SPEC { |
272 //#define FLOAT_PRESSURE 30 /* SFLT_REG_mask.Size() - 1 */ | 272 |
273 //#define INT_PRESSURE 23 /* NOTEMP_I_REG_mask.Size() - 1 */ | 273 private: |
274 #define FLOAT_INCREMENT(regs) regs | 274 |
275 #else | 275 uint _max_lrg_id; |
276 //#define FLOAT_PRESSURE 6 | 276 |
277 //#define INT_PRESSURE 6 | 277 // Union-find map. Declared as a short for speed. |
278 #define FLOAT_INCREMENT(regs) 1 | 278 // Indexed by live-range number, it returns the compacted live-range number |
279 #endif | 279 LRG_List _uf_map; |
280 | |
281 // Map from Nodes to live ranges | |
282 LRG_List _names; | |
283 | |
284 // Straight out of Tarjan's union-find algorithm | |
285 uint find_compress(const Node *node) { | |
286 uint lrg_id = find_compress(_names[node->_idx]); | |
287 _names.map(node->_idx, lrg_id); | |
288 return lrg_id; | |
289 } | |
290 | |
291 uint find_compress(uint lrg); | |
292 | |
293 public: | |
294 | |
295 const LRG_List& names() { | |
296 return _names; | |
297 } | |
298 | |
299 uint max_lrg_id() const { | |
300 return _max_lrg_id; | |
301 } | |
302 | |
303 void set_max_lrg_id(uint max_lrg_id) { | |
304 _max_lrg_id = max_lrg_id; | |
305 } | |
306 | |
307 uint size() const { | |
308 return _names.Size(); | |
309 } | |
310 | |
311 uint live_range_id(uint idx) const { | |
312 return _names[idx]; | |
313 } | |
314 | |
315 uint live_range_id(const Node *node) const { | |
316 return _names[node->_idx]; | |
317 } | |
318 | |
319 uint uf_live_range_id(uint lrg_id) const { | |
320 return _uf_map[lrg_id]; | |
321 } | |
322 | |
323 void map(uint idx, uint lrg_id) { | |
324 _names.map(idx, lrg_id); | |
325 } | |
326 | |
327 void uf_map(uint dst_lrg_id, uint src_lrg_id) { | |
328 _uf_map.map(dst_lrg_id, src_lrg_id); | |
329 } | |
330 | |
331 void extend(uint idx, uint lrg_id) { | |
332 _names.extend(idx, lrg_id); | |
333 } | |
334 | |
335 void uf_extend(uint dst_lrg_id, uint src_lrg_id) { | |
336 _uf_map.extend(dst_lrg_id, src_lrg_id); | |
337 } | |
338 | |
339 LiveRangeMap(uint unique) | |
340 : _names(unique) | |
341 , _uf_map(unique) | |
342 , _max_lrg_id(0) {} | |
343 | |
344 uint find_id( const Node *n ) { | |
345 uint retval = live_range_id(n); | |
346 assert(retval == find(n),"Invalid node to lidx mapping"); | |
347 return retval; | |
348 } | |
349 | |
350 // Reset the Union-Find map to identity | |
351 void reset_uf_map(uint max_lrg_id); | |
352 | |
353 // Make all Nodes map directly to their final live range; no need for | |
354 // the Union-Find mapping after this call. | |
355 void compress_uf_map_for_nodes(); | |
356 | |
357 uint find(uint lidx) { | |
358 uint uf_lidx = _uf_map[lidx]; | |
359 return (uf_lidx == lidx) ? uf_lidx : find_compress(lidx); | |
360 } | |
361 | |
362 // Convert a Node into a Live Range Index - a lidx | |
363 uint find(const Node *node) { | |
364 uint lidx = live_range_id(node); | |
365 uint uf_lidx = _uf_map[lidx]; | |
366 return (uf_lidx == lidx) ? uf_lidx : find_compress(node); | |
367 } | |
368 | |
369 // Like Find above, but no path compress, so bad asymptotic behavior | |
370 uint find_const(uint lrg) const; | |
371 | |
372 // Like Find above, but no path compress, so bad asymptotic behavior | |
373 uint find_const(const Node *node) const { | |
374 if(node->_idx >= _names.Size()) { | |
375 return 0; // not mapped, usual for debug dump | |
376 } | |
377 return find_const(_names[node->_idx]); | |
378 } | |
379 }; | |
280 | 380 |
281 //------------------------------Chaitin---------------------------------------- | 381 //------------------------------Chaitin---------------------------------------- |
282 // Briggs-Chaitin style allocation, mostly. | 382 // Briggs-Chaitin style allocation, mostly. |
283 class PhaseChaitin : public PhaseRegAlloc { | 383 class PhaseChaitin : public PhaseRegAlloc { |
284 friend class VMStructs; | 384 friend class VMStructs; |
285 | 385 |
286 int _trip_cnt; | 386 int _trip_cnt; |
287 int _alternate; | 387 int _alternate; |
288 | 388 |
289 uint _maxlrg; // Max live range number | |
290 LRG &lrgs(uint idx) const { return _ifg->lrgs(idx); } | 389 LRG &lrgs(uint idx) const { return _ifg->lrgs(idx); } |
291 PhaseLive *_live; // Liveness, used in the interference graph | 390 PhaseLive *_live; // Liveness, used in the interference graph |
292 PhaseIFG *_ifg; // Interference graph (for original chunk) | 391 PhaseIFG *_ifg; // Interference graph (for original chunk) |
293 Node_List **_lrg_nodes; // Array of node; lists for lrgs which spill | 392 Node_List **_lrg_nodes; // Array of node; lists for lrgs which spill |
294 VectorSet _spilled_once; // Nodes that have been spilled | 393 VectorSet _spilled_once; // Nodes that have been spilled |
295 VectorSet _spilled_twice; // Nodes that have been spilled twice | 394 VectorSet _spilled_twice; // Nodes that have been spilled twice |
296 | 395 |
297 LRG_List _names; // Map from Nodes to Live RanGes | |
298 | |
299 // Union-find map. Declared as a short for speed. | |
300 // Indexed by live-range number, it returns the compacted live-range number | |
301 LRG_List _uf_map; | |
302 // Reset the Union-Find map to identity | |
303 void reset_uf_map( uint maxlrg ); | |
304 // Remove the need for the Union-Find mapping | |
305 void compress_uf_map_for_nodes( ); | |
306 | |
307 // Combine the Live Range Indices for these 2 Nodes into a single live | 396 // Combine the Live Range Indices for these 2 Nodes into a single live |
308 // range. Future requests for any Node in either live range will | 397 // range. Future requests for any Node in either live range will |
309 // return the live range index for the combined live range. | 398 // return the live range index for the combined live range. |
310 void Union( const Node *src, const Node *dst ); | 399 void Union( const Node *src, const Node *dst ); |
311 | 400 |
320 uint _simplified; // Linked list head of simplified LRGs | 409 uint _simplified; // Linked list head of simplified LRGs |
321 | 410 |
322 // Helper functions for Split() | 411 // Helper functions for Split() |
323 uint split_DEF( Node *def, Block *b, int loc, uint max, Node **Reachblock, Node **debug_defs, GrowableArray<uint> splits, int slidx ); | 412 uint split_DEF( Node *def, Block *b, int loc, uint max, Node **Reachblock, Node **debug_defs, GrowableArray<uint> splits, int slidx ); |
324 uint split_USE( Node *def, Block *b, Node *use, uint useidx, uint max, bool def_down, bool cisc_sp, GrowableArray<uint> splits, int slidx ); | 413 uint split_USE( Node *def, Block *b, Node *use, uint useidx, uint max, bool def_down, bool cisc_sp, GrowableArray<uint> splits, int slidx ); |
325 int clone_projs( Block *b, uint idx, Node *con, Node *copy, uint &maxlrg ); | 414 |
415 bool clone_projs(Block *b, uint idx, Node *con, Node *copy, LiveRangeMap &lrg_map) { | |
416 bool found_projs = clone_projs_shared(b, idx, con, copy, lrg_map.max_lrg_id()); | |
417 | |
418 if(found_projs) { | |
419 uint max_lrg_id = lrg_map.max_lrg_id(); | |
420 lrg_map.set_max_lrg_id(max_lrg_id + 1); | |
421 } | |
422 | |
423 return found_projs; | |
424 } | |
425 | |
426 //------------------------------clone_projs------------------------------------ | |
427 // After cloning some rematerialized instruction, clone any MachProj's that | |
428 // follow it. Example: Intel zero is XOR, kills flags. Sparc FP constants | |
429 // use G3 as an address temp. | |
430 bool clone_projs(Block *b, uint idx, Node *con, Node *copy, uint &max_lrg_id) { | |
431 bool found_projs = clone_projs_shared(b, idx, con, copy, max_lrg_id); | |
432 | |
433 if(found_projs) { | |
434 max_lrg_id++; | |
435 } | |
436 | |
437 return found_projs; | |
438 } | |
439 | |
440 bool clone_projs_shared(Block *b, uint idx, Node *con, Node *copy, uint max_lrg_id); | |
441 | |
326 Node *split_Rematerialize(Node *def, Block *b, uint insidx, uint &maxlrg, GrowableArray<uint> splits, | 442 Node *split_Rematerialize(Node *def, Block *b, uint insidx, uint &maxlrg, GrowableArray<uint> splits, |
327 int slidx, uint *lrg2reach, Node **Reachblock, bool walkThru); | 443 int slidx, uint *lrg2reach, Node **Reachblock, bool walkThru); |
328 // True if lidx is used before any real register is def'd in the block | 444 // True if lidx is used before any real register is def'd in the block |
329 bool prompt_use( Block *b, uint lidx ); | 445 bool prompt_use( Block *b, uint lidx ); |
330 Node *get_spillcopy_wide( Node *def, Node *use, uint uidx ); | 446 Node *get_spillcopy_wide( Node *def, Node *use, uint uidx ); |
347 | 463 |
348 public: | 464 public: |
349 PhaseChaitin( uint unique, PhaseCFG &cfg, Matcher &matcher ); | 465 PhaseChaitin( uint unique, PhaseCFG &cfg, Matcher &matcher ); |
350 ~PhaseChaitin() {} | 466 ~PhaseChaitin() {} |
351 | 467 |
352 // Convert a Node into a Live Range Index - a lidx | 468 LiveRangeMap _lrg_map; |
353 uint Find( const Node *n ) { | |
354 uint lidx = n2lidx(n); | |
355 uint uf_lidx = _uf_map[lidx]; | |
356 return (uf_lidx == lidx) ? uf_lidx : Find_compress(n); | |
357 } | |
358 uint Find_const( uint lrg ) const; | |
359 uint Find_const( const Node *n ) const; | |
360 | 469 |
361 // Do all the real work of allocate | 470 // Do all the real work of allocate |
362 void Register_Allocate(); | 471 void Register_Allocate(); |
363 | |
364 uint n2lidx( const Node *n ) const { return _names[n->_idx]; } | |
365 | 472 |
366 float high_frequency_lrg() const { return _high_frequency_lrg; } | 473 float high_frequency_lrg() const { return _high_frequency_lrg; } |
367 | 474 |
368 #ifndef PRODUCT | 475 #ifndef PRODUCT |
369 bool trace_spilling() const { return _trace_spilling; } | 476 bool trace_spilling() const { return _trace_spilling; } |
372 private: | 479 private: |
373 // De-SSA the world. Assign registers to Nodes. Use the same register for | 480 // De-SSA the world. Assign registers to Nodes. Use the same register for |
374 // all inputs to a PhiNode, effectively coalescing live ranges. Insert | 481 // all inputs to a PhiNode, effectively coalescing live ranges. Insert |
375 // copies as needed. | 482 // copies as needed. |
376 void de_ssa(); | 483 void de_ssa(); |
377 uint Find_compress( const Node *n ); | |
378 uint Find( uint lidx ) { | |
379 uint uf_lidx = _uf_map[lidx]; | |
380 return (uf_lidx == lidx) ? uf_lidx : Find_compress(lidx); | |
381 } | |
382 uint Find_compress( uint lidx ); | |
383 | |
384 uint Find_id( const Node *n ) { | |
385 uint retval = n2lidx(n); | |
386 assert(retval == Find(n),"Invalid node to lidx mapping"); | |
387 return retval; | |
388 } | |
389 | 484 |
390 // Add edge between reg and everything in the vector. | 485 // Add edge between reg and everything in the vector. |
391 // Same as _ifg->add_vector(reg,live) EXCEPT use the RegMask | 486 // Same as _ifg->add_vector(reg,live) EXCEPT use the RegMask |
392 // information to trim the set of interferences. Return the | 487 // information to trim the set of interferences. Return the |
393 // count of edges added. | 488 // count of edges added. |