382 // Like Find above, but no path compress, so bad asymptotic behavior
383 uint find_const(uint lrg) const;
384
385 // Like Find above, but no path compress, so bad asymptotic behavior
386 uint find_const(const Node *node) const {
387 if(node->_idx >= (uint)_names.length()) {
388 return 0; // not mapped, usual for debug dump
389 }
390 return find_const(_names.at(node->_idx));
391 }
392 };
393
394 //------------------------------Chaitin----------------------------------------
395 // Briggs-Chaitin style allocation, mostly.
396 class PhaseChaitin : public PhaseRegAlloc {
397 friend class VMStructs;
398
399 int _trip_cnt;
400 int _alternate;
401
402 LRG &lrgs(uint idx) const { return _ifg->lrgs(idx); }
403 PhaseLive *_live; // Liveness, used in the interference graph
404 PhaseIFG *_ifg; // Interference graph (for original chunk)
405 Node_List **_lrg_nodes; // Array of node; lists for lrgs which spill
406 VectorSet _spilled_once; // Nodes that have been spilled
407 VectorSet _spilled_twice; // Nodes that have been spilled twice
408
409 // Combine the Live Range Indices for these 2 Nodes into a single live
410 // range. Future requests for any Node in either live range will
411 // return the live range index for the combined live range.
412 void Union( const Node *src, const Node *dst );
413
414 void new_lrg( const Node *x, uint lrg );
415
416 // Compact live ranges, removing unused ones. Return new maxlrg.
417 void compact();
418
419 uint _lo_degree; // Head of lo-degree LRGs list
420 uint _lo_stk_degree; // Head of lo-stk-degree LRGs list
421 uint _hi_degree; // Head of hi-degree LRGs list
422 uint _simplified; // Linked list head of simplified LRGs
447 bool prompt_use( Block *b, uint lidx );
448 Node *get_spillcopy_wide(MachSpillCopyNode::SpillType spill_type, Node *def, Node *use, uint uidx );
449 // Insert the spill at chosen location. Skip over any intervening Proj's or
450 // Phis. Skip over a CatchNode and projs, inserting in the fall-through block
451 // instead. Update high-pressure indices. Create a new live range.
452 void insert_proj( Block *b, uint i, Node *spill, uint maxlrg );
453
454 bool is_high_pressure( Block *b, LRG *lrg, uint insidx );
455
456 uint _oldphi; // Node index which separates pre-allocation nodes
457
458 Block **_blks; // Array of blocks sorted by frequency for coalescing
459
460 float _high_frequency_lrg; // Frequency at which LRG will be spilled for debug info
461
462 #ifndef PRODUCT
463 bool _trace_spilling;
464 #endif
465
466 public:
467 PhaseChaitin( uint unique, PhaseCFG &cfg, Matcher &matcher );
468 ~PhaseChaitin() {}
469
470 LiveRangeMap _lrg_map;
471
472 // Do all the real work of allocate
473 void Register_Allocate();
474
475 float high_frequency_lrg() const { return _high_frequency_lrg; }
476
477 #ifndef PRODUCT
478 bool trace_spilling() const { return _trace_spilling; }
479 #endif
480
481 private:
482 // De-SSA the world. Assign registers to Nodes. Use the same register for
483 // all inputs to a PhiNode, effectively coalescing live ranges. Insert
484 // copies as needed.
485 void de_ssa();
486
487 // Add edge between reg and everything in the vector.
488 // Same as _ifg->add_vector(reg,live) EXCEPT use the RegMask
489 // information to trim the set of interferences. Return the
490 // count of edges added.
491 void interfere_with_live(uint lid, IndexSet* liveout);
492 #ifdef ASSERT
493 // Count register pressure for asserts
494 uint count_int_pressure(IndexSet* liveout);
495 uint count_float_pressure(IndexSet* liveout);
496 #endif
499 // Used for aggressive coalescing.
500 void build_ifg_virtual( );
501
502 // used when computing the register pressure for each block in the CFG. This
503 // is done during IFG creation.
504 class Pressure {
505 // keeps track of the register pressure at the current
506 // instruction (used when stepping backwards in the block)
507 uint _current_pressure;
508
509 // keeps track of the instruction index of the first low to high register pressure
510 // transition (starting from the top) in the block
511 // if high_pressure_index == 0 then the whole block is high pressure
512 // if high_pressure_index = b.end_idx() + 1 then the whole block is low pressure
513 uint _high_pressure_index;
514
515 // stores the highest pressure we find
516 uint _final_pressure;
517
518 // number of live ranges that constitute high register pressure
519 const uint _high_pressure_limit;
520 public:
521
522 // lower the register pressure and look for a low to high pressure
523 // transition
524 void lower(LRG& lrg, uint& location) {
525 _current_pressure -= lrg.reg_pressure();
526 if (_current_pressure == _high_pressure_limit) {
527 _high_pressure_index = location;
528 }
529 }
530
531 // raise the pressure and store the pressure if it's the biggest
532 // pressure so far
533 void raise(LRG &lrg) {
534 _current_pressure += lrg.reg_pressure();
535 if (_current_pressure > _final_pressure) {
536 _final_pressure = _current_pressure;
537 }
538 }
539
540 uint high_pressure_index() const {
541 return _high_pressure_index;
542 }
543
544 uint final_pressure() const {
545 return _final_pressure;
546 }
547
548 uint current_pressure() const {
549 return _current_pressure;
550 }
551
552 uint high_pressure_limit() const {
553 return _high_pressure_limit;
554 }
555
556 void lower_high_pressure_index() {
557 _high_pressure_index--;
558 }
559
560 void set_high_pressure_index_to_block_start() {
561 _high_pressure_index = 0;
562 }
563
564 void check_pressure_at_fatproj(uint fatproj_location, RegMask& fatproj_mask) {
565 // this pressure is only valid at this instruction, i.e. we don't need to lower
566 // the register pressure since the fat proj was never live before (going backwards)
567 uint new_pressure = current_pressure() + fatproj_mask.Size();
568 if (new_pressure > final_pressure()) {
569 _final_pressure = new_pressure;
570 }
571
572 // if we were at a low pressure and now and the fat proj is at high pressure, record the fat proj location
573 // as coming from a low to high (to low again)
574 if (current_pressure() <= high_pressure_limit() && new_pressure > high_pressure_limit()) {
575 _high_pressure_index = fatproj_location;
576 }
577 }
578
579 Pressure(uint high_pressure_index, uint high_pressure_limit)
580 : _current_pressure(0)
581 , _high_pressure_index(high_pressure_index)
582 , _high_pressure_limit(high_pressure_limit)
583 , _final_pressure(0) {}
584 };
585
586 void lower_pressure(Block* b, uint location, LRG& lrg, IndexSet* liveout, Pressure& int_pressure, Pressure& float_pressure);
587 void raise_pressure(Block* b, LRG& lrg, Pressure& int_pressure, Pressure& float_pressure);
588 void check_for_high_pressure_transition_at_fatproj(uint& block_reg_pressure, uint location, LRG& lrg, Pressure& pressure, const int op_regtype);
589 void add_input_to_liveout(Block* b, Node* n, IndexSet* liveout, double cost, Pressure& int_pressure, Pressure& float_pressure);
590 void compute_initial_block_pressure(Block* b, IndexSet* liveout, Pressure& int_pressure, Pressure& float_pressure, double cost);
591 bool remove_node_if_not_used(Block* b, uint location, Node* n, uint lid, IndexSet* liveout);
592 void assign_high_score_to_immediate_copies(Block* b, Node* n, LRG& lrg, uint next_inst, uint last_inst);
593 void remove_interference_from_copy(Block* b, uint location, uint lid_copy, IndexSet* liveout, double cost, Pressure& int_pressure, Pressure& float_pressure);
594 void remove_bound_register_from_interfering_live_ranges(LRG& lrg, IndexSet* liveout, uint& must_spill);
595 void check_for_high_pressure_block(Pressure& pressure);
596 void adjust_high_pressure_index(Block* b, uint& hrp_index, Pressure& pressure);
597
598 // Build the interference graph using physical registers when available.
599 // That is, if 2 live ranges are simultaneously alive but in their
600 // acceptable register sets do not overlap, then they do not interfere.
601 uint build_ifg_physical( ResourceArea *a );
602
603 // Gather LiveRanGe information, including register masks and base pointer/
604 // derived pointer relationships.
605 void gather_lrg_masks( bool mod_cisc_masks );
606
607 // Force the bases of derived pointers to be alive at GC points.
608 bool stretch_base_pointer_live_ranges( ResourceArea *a );
609 // Helper to stretch above; recursively discover the base Node for
610 // a given derived Node. Easy for AddP-related machine nodes, but
611 // needs to be recursive for derived Phis.
612 Node *find_base_for_derived( Node **derived_base_map, Node *derived, uint &maxlrg );
613
614 // Set the was-lo-degree bit. Conservative coalescing should not change the
615 // colorability of the graph. If any live range was of low-degree before
616 // coalescing, it should Simplify. This call sets the was-lo-degree bit.
617 void set_was_low();
618
619 // Split live-ranges that must spill due to register conflicts (as opposed
620 // to capacity spills). Typically these are things def'd in a register
621 // and used on the stack or vice-versa.
622 void pre_spill();
623
624 // Init LRG caching of degree, numregs. Init lo_degree list.
625 void cache_lrg_info( );
626
|
382 // Like Find above, but no path compress, so bad asymptotic behavior
383 uint find_const(uint lrg) const;
384
385 // Like Find above, but no path compress, so bad asymptotic behavior
386 uint find_const(const Node *node) const {
387 if(node->_idx >= (uint)_names.length()) {
388 return 0; // not mapped, usual for debug dump
389 }
390 return find_const(_names.at(node->_idx));
391 }
392 };
393
394 //------------------------------Chaitin----------------------------------------
395 // Briggs-Chaitin style allocation, mostly.
396 class PhaseChaitin : public PhaseRegAlloc {
397 friend class VMStructs;
398
399 int _trip_cnt;
400 int _alternate;
401
402 PhaseLive *_live; // Liveness, used in the interference graph
403 PhaseIFG *_ifg; // Interference graph (for original chunk)
404 Node_List **_lrg_nodes; // Array of node; lists for lrgs which spill
405 VectorSet _spilled_once; // Nodes that have been spilled
406 VectorSet _spilled_twice; // Nodes that have been spilled twice
407
408 // Combine the Live Range Indices for these 2 Nodes into a single live
409 // range. Future requests for any Node in either live range will
410 // return the live range index for the combined live range.
411 void Union( const Node *src, const Node *dst );
412
413 void new_lrg( const Node *x, uint lrg );
414
415 // Compact live ranges, removing unused ones. Return new maxlrg.
416 void compact();
417
418 uint _lo_degree; // Head of lo-degree LRGs list
419 uint _lo_stk_degree; // Head of lo-stk-degree LRGs list
420 uint _hi_degree; // Head of hi-degree LRGs list
421 uint _simplified; // Linked list head of simplified LRGs
446 bool prompt_use( Block *b, uint lidx );
447 Node *get_spillcopy_wide(MachSpillCopyNode::SpillType spill_type, Node *def, Node *use, uint uidx );
448 // Insert the spill at chosen location. Skip over any intervening Proj's or
449 // Phis. Skip over a CatchNode and projs, inserting in the fall-through block
450 // instead. Update high-pressure indices. Create a new live range.
451 void insert_proj( Block *b, uint i, Node *spill, uint maxlrg );
452
453 bool is_high_pressure( Block *b, LRG *lrg, uint insidx );
454
455 uint _oldphi; // Node index which separates pre-allocation nodes
456
457 Block **_blks; // Array of blocks sorted by frequency for coalescing
458
459 float _high_frequency_lrg; // Frequency at which LRG will be spilled for debug info
460
461 #ifndef PRODUCT
462 bool _trace_spilling;
463 #endif
464
465 public:
466 PhaseChaitin(uint unique, PhaseCFG &cfg, Matcher &matcher, bool track_liveout_pressure);
467 ~PhaseChaitin() {}
468
469 LiveRangeMap _lrg_map;
470
471 LRG &lrgs(uint idx) const { return _ifg->lrgs(idx); }
472
473 // Do all the real work of allocate
474 void Register_Allocate();
475
476 float high_frequency_lrg() const { return _high_frequency_lrg; }
477
478 // Used when scheduling info generated, not in general register allocation
479 bool _scheduling_info_generated;
480
481 void set_ifg(PhaseIFG &ifg) { _ifg = &ifg; }
482 void set_live(PhaseLive &live) { _live = &live; }
483 PhaseLive* get_live() { return _live; }
484
485 // Populate the live range maps with ssa info for scheduling
486 void mark_ssa();
487
488 #ifndef PRODUCT
489 bool trace_spilling() const { return _trace_spilling; }
490 #endif
491
492 private:
493 // De-SSA the world. Assign registers to Nodes. Use the same register for
494 // all inputs to a PhiNode, effectively coalescing live ranges. Insert
495 // copies as needed.
496 void de_ssa();
497
498 // Add edge between reg and everything in the vector.
499 // Same as _ifg->add_vector(reg,live) EXCEPT use the RegMask
500 // information to trim the set of interferences. Return the
501 // count of edges added.
502 void interfere_with_live(uint lid, IndexSet* liveout);
503 #ifdef ASSERT
504 // Count register pressure for asserts
505 uint count_int_pressure(IndexSet* liveout);
506 uint count_float_pressure(IndexSet* liveout);
507 #endif
510 // Used for aggressive coalescing.
511 void build_ifg_virtual( );
512
513 // used when computing the register pressure for each block in the CFG. This
514 // is done during IFG creation.
515 class Pressure {
516 // keeps track of the register pressure at the current
517 // instruction (used when stepping backwards in the block)
518 uint _current_pressure;
519
520 // keeps track of the instruction index of the first low to high register pressure
521 // transition (starting from the top) in the block
522 // if high_pressure_index == 0 then the whole block is high pressure
523 // if high_pressure_index = b.end_idx() + 1 then the whole block is low pressure
524 uint _high_pressure_index;
525
526 // stores the highest pressure we find
527 uint _final_pressure;
528
529 // number of live ranges that constitute high register pressure
530 uint _high_pressure_limit;
531
532 // initial pressure observed
533 uint _start_pressure;
534
535 public:
536
537 // lower the register pressure and look for a low to high pressure
538 // transition
539 void lower(LRG& lrg, uint& location) {
540 _current_pressure -= lrg.reg_pressure();
541 if (_current_pressure == _high_pressure_limit) {
542 _high_pressure_index = location;
543 }
544 }
545
546 // raise the pressure and store the pressure if it's the biggest
547 // pressure so far
548 void raise(LRG &lrg) {
549 _current_pressure += lrg.reg_pressure();
550 if (_current_pressure > _final_pressure) {
551 _final_pressure = _current_pressure;
552 }
553 }
554
555 void init(int limit) {
556 _current_pressure = 0;
557 _high_pressure_index = 0;
558 _final_pressure = 0;
559 _high_pressure_limit = limit;
560 _start_pressure = 0;
561 }
562
563 uint high_pressure_index() const {
564 return _high_pressure_index;
565 }
566
567 uint final_pressure() const {
568 return _final_pressure;
569 }
570
571 uint start_pressure() const {
572 return _start_pressure;
573 }
574
575 uint current_pressure() const {
576 return _current_pressure;
577 }
578
579 uint high_pressure_limit() const {
580 return _high_pressure_limit;
581 }
582
583 void lower_high_pressure_index() {
584 _high_pressure_index--;
585 }
586
587 void set_high_pressure_index_to_block_start() {
588 _high_pressure_index = 0;
589 }
590
591 void set_start_pressure(int value) {
592 _start_pressure = value;
593 _final_pressure = value;
594 }
595
596 void set_current_pressure(int value) {
597 _current_pressure = value;
598 }
599
600 void check_pressure_at_fatproj(uint fatproj_location, RegMask& fatproj_mask) {
601 // this pressure is only valid at this instruction, i.e. we don't need to lower
602 // the register pressure since the fat proj was never live before (going backwards)
603 uint new_pressure = current_pressure() + fatproj_mask.Size();
604 if (new_pressure > final_pressure()) {
605 _final_pressure = new_pressure;
606 }
607
608 // if we were at a low pressure and now and the fat proj is at high pressure, record the fat proj location
609 // as coming from a low to high (to low again)
610 if (current_pressure() <= high_pressure_limit() && new_pressure > high_pressure_limit()) {
611 _high_pressure_index = fatproj_location;
612 }
613 }
614
615 Pressure(uint high_pressure_index, uint high_pressure_limit)
616 : _current_pressure(0)
617 , _high_pressure_index(high_pressure_index)
618 , _final_pressure(0)
619 , _high_pressure_limit(high_pressure_limit)
620 , _start_pressure(0) {}
621 };
622
623 void check_for_high_pressure_transition_at_fatproj(uint& block_reg_pressure, uint location, LRG& lrg, Pressure& pressure, const int op_regtype);
624 void add_input_to_liveout(Block* b, Node* n, IndexSet* liveout, double cost, Pressure& int_pressure, Pressure& float_pressure);
625 void compute_initial_block_pressure(Block* b, IndexSet* liveout, Pressure& int_pressure, Pressure& float_pressure, double cost);
626 bool remove_node_if_not_used(Block* b, uint location, Node* n, uint lid, IndexSet* liveout);
627 void assign_high_score_to_immediate_copies(Block* b, Node* n, LRG& lrg, uint next_inst, uint last_inst);
628 void remove_interference_from_copy(Block* b, uint location, uint lid_copy, IndexSet* liveout, double cost, Pressure& int_pressure, Pressure& float_pressure);
629 void remove_bound_register_from_interfering_live_ranges(LRG& lrg, IndexSet* liveout, uint& must_spill);
630 void check_for_high_pressure_block(Pressure& pressure);
631 void adjust_high_pressure_index(Block* b, uint& hrp_index, Pressure& pressure);
632
633 // Build the interference graph using physical registers when available.
634 // That is, if 2 live ranges are simultaneously alive but in their
635 // acceptable register sets do not overlap, then they do not interfere.
636 uint build_ifg_physical( ResourceArea *a );
637
638 public:
639 // Gather LiveRanGe information, including register masks and base pointer/
640 // derived pointer relationships.
641 void gather_lrg_masks( bool mod_cisc_masks );
642
643 // user visible pressure variables for scheduling
644 Pressure _sched_int_pressure;
645 Pressure _sched_float_pressure;
646 Pressure _scratch_int_pressure;
647 Pressure _scratch_float_pressure;
648
649 // Pressure functions for user context
650 void lower_pressure(Block* b, uint location, LRG& lrg, IndexSet* liveout, Pressure& int_pressure, Pressure& float_pressure);
651 void raise_pressure(Block* b, LRG& lrg, Pressure& int_pressure, Pressure& float_pressure);
652 void compute_entry_block_pressure(Block* b);
653 void compute_exit_block_pressure(Block* b);
654 void print_pressure_info(Pressure& pressure, const char *str);
655
656 private:
657 // Force the bases of derived pointers to be alive at GC points.
658 bool stretch_base_pointer_live_ranges( ResourceArea *a );
659 // Helper to stretch above; recursively discover the base Node for
660 // a given derived Node. Easy for AddP-related machine nodes, but
661 // needs to be recursive for derived Phis.
662 Node *find_base_for_derived( Node **derived_base_map, Node *derived, uint &maxlrg );
663
664 // Set the was-lo-degree bit. Conservative coalescing should not change the
665 // colorability of the graph. If any live range was of low-degree before
666 // coalescing, it should Simplify. This call sets the was-lo-degree bit.
667 void set_was_low();
668
669 // Split live-ranges that must spill due to register conflicts (as opposed
670 // to capacity spills). Typically these are things def'd in a register
671 // and used on the stack or vice-versa.
672 void pre_spill();
673
674 // Init LRG caching of degree, numregs. Init lo_degree list.
675 void cache_lrg_info( );
676
|