1 /* 2 * Copyright (c) 1997, 2018, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. 8 * 9 * This code is distributed in the hope that it will be useful, but WITHOUT 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 12 * version 2 for more details (a copy is included in the LICENSE file that 13 * accompanied this code). 14 * 15 * You should have received a copy of the GNU General Public License version 16 * 2 along with this work; if not, write to the Free Software Foundation, 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 18 * 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 * 23 */ 24 25 #ifndef SHARE_VM_OPTO_CHAITIN_HPP 26 #define SHARE_VM_OPTO_CHAITIN_HPP 27 28 #include "code/vmreg.hpp" 29 #include "memory/resourceArea.hpp" 30 #include "opto/connode.hpp" 31 #include "opto/live.hpp" 32 #include "opto/matcher.hpp" 33 #include "opto/phase.hpp" 34 #include "opto/regalloc.hpp" 35 #include "opto/regmask.hpp" 36 #include "opto/machnode.hpp" 37 38 class LoopTree; 39 class Matcher; 40 class PhaseCFG; 41 class PhaseLive; 42 class PhaseRegAlloc; 43 class PhaseChaitin; 44 45 #define OPTO_DEBUG_SPLIT_FREQ BLOCK_FREQUENCY(0.001) 46 #define OPTO_LRG_HIGH_FREQ BLOCK_FREQUENCY(0.25) 47 48 //------------------------------LRG-------------------------------------------- 49 // Live-RanGe structure. 50 class LRG : public ResourceObj { 51 friend class VMStructs; 52 public: 53 static const uint AllStack_size = 0xFFFFF; // This mask size is used to tell that the mask of this LRG supports stack positions 54 enum { SPILL_REG=29999 }; // Register number of a spilled LRG 55 56 double _cost; // 2 for loads/1 for stores times block freq 57 double _area; // Sum of all simultaneously live values 58 double score() const; // Compute score from cost and area 59 double _maxfreq; // Maximum frequency of any def or use 60 61 Node *_def; // Check for multi-def live ranges 62 #ifndef PRODUCT 63 GrowableArray<Node*>* _defs; 64 #endif 65 66 uint _risk_bias; // Index of LRG which we want to avoid color 67 uint _copy_bias; // Index of LRG which we want to share color 68 69 uint _next; // Index of next LRG in linked list 70 uint _prev; // Index of prev LRG in linked list 71 private: 72 uint _reg; // Chosen register; undefined if mask is plural 73 public: 74 // Return chosen register for this LRG. Error if the LRG is not bound to 75 // a single register. reg() const76 OptoReg::Name reg() const { return OptoReg::Name(_reg); } set_reg(OptoReg::Name r)77 void set_reg( OptoReg::Name r ) { _reg = r; } 78 79 private: 80 uint _eff_degree; // Effective degree: Sum of neighbors _num_regs 81 public: degree() const82 int degree() const { assert( _degree_valid , "" ); return _eff_degree; } 83 // Degree starts not valid and any change to the IFG neighbor 84 // set makes it not valid. set_degree(uint degree)85 void set_degree( uint degree ) { 86 _eff_degree = degree; 87 debug_only(_degree_valid = 1;) 88 assert(!_mask.is_AllStack() || (_mask.is_AllStack() && lo_degree()), "_eff_degree can't be bigger than AllStack_size - _num_regs if the mask supports stack registers"); 89 } 90 // Made a change that hammered degree invalid_degree()91 void invalid_degree() { debug_only(_degree_valid=0;) } 92 // Incrementally modify degree. If it was correct, it should remain correct inc_degree(uint mod)93 void inc_degree( uint mod ) { 94 _eff_degree += mod; 95 assert(!_mask.is_AllStack() || (_mask.is_AllStack() && lo_degree()), "_eff_degree can't be bigger than AllStack_size - _num_regs if the mask supports stack registers"); 96 } 97 // Compute the degree between 2 live ranges 98 int compute_degree( LRG &l ) const; mask_is_nonempty_and_up() const99 bool mask_is_nonempty_and_up() const { 100 return mask().is_UP() && mask_size(); 101 } is_float_or_vector() const102 bool is_float_or_vector() const { 103 return _is_float || _is_vector; 104 } 105 106 private: 107 RegMask _mask; // Allowed registers for this LRG 108 uint _mask_size; // cache of _mask.Size(); 109 public: compute_mask_size() const110 int compute_mask_size() const { return _mask.is_AllStack() ? AllStack_size : _mask.Size(); } set_mask_size(int size)111 void set_mask_size( int size ) { 112 assert((size == (int)AllStack_size) || (size == (int)_mask.Size()), ""); 113 _mask_size = size; 114 #ifdef ASSERT 115 _msize_valid=1; 116 if (_is_vector) { 117 assert(!_fat_proj, "sanity"); 118 _mask.verify_sets(_num_regs); 119 } else if (_num_regs == 2 && !_fat_proj) { 120 _mask.verify_pairs(); 121 } 122 #endif 123 } compute_set_mask_size()124 void compute_set_mask_size() { set_mask_size(compute_mask_size()); } mask_size() const125 int mask_size() const { assert( _msize_valid, "mask size not valid" ); 126 return _mask_size; } 127 // Get the last mask size computed, even if it does not match the 128 // count of bits in the current mask. get_invalid_mask_size() const129 int get_invalid_mask_size() const { return _mask_size; } mask() const130 const RegMask &mask() const { return _mask; } set_mask(const RegMask & rm)131 void set_mask( const RegMask &rm ) { _mask = rm; debug_only(_msize_valid=0;)} AND(const RegMask & rm)132 void AND( const RegMask &rm ) { _mask.AND(rm); debug_only(_msize_valid=0;)} SUBTRACT(const RegMask & rm)133 void SUBTRACT( const RegMask &rm ) { _mask.SUBTRACT(rm); debug_only(_msize_valid=0;)} Clear()134 void Clear() { _mask.Clear() ; debug_only(_msize_valid=1); _mask_size = 0; } Set_All()135 void Set_All() { _mask.Set_All(); debug_only(_msize_valid=1); _mask_size = RegMask::CHUNK_SIZE; } 136 Insert(OptoReg::Name reg)137 void Insert( OptoReg::Name reg ) { _mask.Insert(reg); debug_only(_msize_valid=0;) } Remove(OptoReg::Name reg)138 void Remove( OptoReg::Name reg ) { _mask.Remove(reg); debug_only(_msize_valid=0;) } clear_to_pairs()139 void clear_to_pairs() { _mask.clear_to_pairs(); debug_only(_msize_valid=0;) } clear_to_sets()140 void clear_to_sets() { _mask.clear_to_sets(_num_regs); debug_only(_msize_valid=0;) } 141 142 // Number of registers this live range uses when it colors 143 private: 144 uint16_t _num_regs; // 2 for Longs and Doubles, 1 for all else 145 // except _num_regs is kill count for fat_proj 146 public: num_regs() const147 int num_regs() const { return _num_regs; } set_num_regs(int reg)148 void set_num_regs( int reg ) { assert( _num_regs == reg || !_num_regs, "" ); _num_regs = reg; } 149 150 private: 151 // Number of physical registers this live range uses when it colors 152 // Architecture and register-set dependent 153 uint16_t _reg_pressure; 154 public: set_reg_pressure(int i)155 void set_reg_pressure(int i) { _reg_pressure = i; } reg_pressure() const156 int reg_pressure() const { return _reg_pressure; } 157 158 // How much 'wiggle room' does this live range have? 159 // How many color choices can it make (scaled by _num_regs)? degrees_of_freedom() const160 int degrees_of_freedom() const { return mask_size() - _num_regs; } 161 // Bound LRGs have ZERO degrees of freedom. We also count 162 // must_spill as bound. is_bound() const163 bool is_bound () const { return _is_bound; } 164 // Negative degrees-of-freedom; even with no neighbors this 165 // live range must spill. not_free() const166 bool not_free() const { return degrees_of_freedom() < 0; } 167 // Is this live range of "low-degree"? Trivially colorable? lo_degree() const168 bool lo_degree () const { return degree() <= degrees_of_freedom(); } 169 // Is this live range just barely "low-degree"? Trivially colorable? just_lo_degree() const170 bool just_lo_degree () const { return degree() == degrees_of_freedom(); } 171 172 uint _is_oop:1, // Live-range holds an oop 173 _is_float:1, // True if in float registers 174 _is_vector:1, // True if in vector registers 175 _was_spilled1:1, // True if prior spilling on def 176 _was_spilled2:1, // True if twice prior spilling on def 177 _is_bound:1, // live range starts life with no 178 // degrees of freedom. 179 _direct_conflict:1, // True if def and use registers in conflict 180 _must_spill:1, // live range has lost all degrees of freedom 181 // If _fat_proj is set, live range does NOT require aligned, adjacent 182 // registers and has NO interferences. 183 // If _fat_proj is clear, live range requires num_regs() to be a power of 184 // 2, and it requires registers to form an aligned, adjacent set. 185 _fat_proj:1, // 186 _was_lo:1, // Was lo-degree prior to coalesce 187 _msize_valid:1, // _mask_size cache valid 188 _degree_valid:1, // _degree cache valid 189 _has_copy:1, // Adjacent to some copy instruction 190 _at_risk:1; // Simplify says this guy is at risk to spill 191 192 193 // Alive if non-zero, dead if zero alive() const194 bool alive() const { return _def != NULL; } is_multidef() const195 bool is_multidef() const { return _def == NodeSentinel; } is_singledef() const196 bool is_singledef() const { return _def != NodeSentinel; } 197 198 #ifndef PRODUCT 199 void dump( ) const; 200 #endif 201 }; 202 203 //------------------------------IFG-------------------------------------------- 204 // InterFerence Graph 205 // An undirected graph implementation. Created with a fixed number of 206 // vertices. Edges can be added & tested. Vertices can be removed, then 207 // added back later with all edges intact. Can add edges between one vertex 208 // and a list of other vertices. Can union vertices (and their edges) 209 // together. The IFG needs to be really really fast, and also fairly 210 // abstract! It needs abstraction so I can fiddle with the implementation to 211 // get even more speed. 212 class PhaseIFG : public Phase { 213 friend class VMStructs; 214 // Current implementation: a triangular adjacency list. 215 216 // Array of adjacency-lists, indexed by live-range number 217 IndexSet *_adjs; 218 219 // Assertion bit for proper use of Squaring 220 bool _is_square; 221 222 // Live range structure goes here 223 LRG *_lrgs; // Array of LRG structures 224 225 public: 226 // Largest live-range number 227 uint _maxlrg; 228 229 Arena *_arena; 230 231 // Keep track of inserted and deleted Nodes 232 VectorSet *_yanked; 233 234 PhaseIFG( Arena *arena ); 235 void init( uint maxlrg ); 236 237 // Add edge between a and b. Returns true if actually addded. 238 int add_edge( uint a, uint b ); 239 240 // Add edge between a and everything in the vector 241 void add_vector( uint a, IndexSet *vec ); 242 243 // Test for edge existance 244 int test_edge( uint a, uint b ) const; 245 246 // Square-up matrix for faster Union 247 void SquareUp(); 248 249 // Return number of LRG neighbors neighbor_cnt(uint a) const250 uint neighbor_cnt( uint a ) const { return _adjs[a].count(); } 251 // Union edges of b into a on Squared-up matrix 252 void Union( uint a, uint b ); 253 // Test for edge in Squared-up matrix 254 int test_edge_sq( uint a, uint b ) const; 255 // Yank a Node and all connected edges from the IFG. Be prepared to 256 // re-insert the yanked Node in reverse order of yanking. Return a 257 // list of neighbors (edges) yanked. 258 IndexSet *remove_node( uint a ); 259 // Reinsert a yanked Node 260 void re_insert( uint a ); 261 // Return set of neighbors neighbors(uint a) const262 IndexSet *neighbors( uint a ) const { return &_adjs[a]; } 263 264 #ifndef PRODUCT 265 // Dump the IFG 266 void dump() const; 267 void stats() const; 268 void verify( const PhaseChaitin * ) const; 269 #endif 270 271 //--------------- Live Range Accessors lrgs(uint idx) const272 LRG &lrgs(uint idx) const { assert(idx < _maxlrg, "oob"); return _lrgs[idx]; } 273 274 // Compute and set effective degree. Might be folded into SquareUp(). 275 void Compute_Effective_Degree(); 276 277 // Compute effective degree as the sum of neighbors' _sizes. 278 int effective_degree( uint lidx ) const; 279 }; 280 281 // The LiveRangeMap class is responsible for storing node to live range id mapping. 282 // Each node is mapped to a live range id (a virtual register). Nodes that are 283 // not considered for register allocation are given live range id 0. 284 class LiveRangeMap { 285 286 private: 287 288 uint _max_lrg_id; 289 290 // Union-find map. Declared as a short for speed. 291 // Indexed by live-range number, it returns the compacted live-range number 292 LRG_List _uf_map; 293 294 // Map from Nodes to live ranges 295 LRG_List _names; 296 297 // Straight out of Tarjan's union-find algorithm find_compress(const Node * node)298 uint find_compress(const Node *node) { 299 uint lrg_id = find_compress(_names.at(node->_idx)); 300 _names.at_put(node->_idx, lrg_id); 301 return lrg_id; 302 } 303 304 uint find_compress(uint lrg); 305 306 public: 307 names()308 const LRG_List& names() { 309 return _names; 310 } 311 max_lrg_id() const312 uint max_lrg_id() const { 313 return _max_lrg_id; 314 } 315 set_max_lrg_id(uint max_lrg_id)316 void set_max_lrg_id(uint max_lrg_id) { 317 _max_lrg_id = max_lrg_id; 318 } 319 size() const320 uint size() const { 321 return _names.length(); 322 } 323 live_range_id(uint idx) const324 uint live_range_id(uint idx) const { 325 return _names.at(idx); 326 } 327 live_range_id(const Node * node) const328 uint live_range_id(const Node *node) const { 329 return _names.at(node->_idx); 330 } 331 uf_live_range_id(uint lrg_id) const332 uint uf_live_range_id(uint lrg_id) const { 333 return _uf_map.at(lrg_id); 334 } 335 map(uint idx,uint lrg_id)336 void map(uint idx, uint lrg_id) { 337 _names.at_put(idx, lrg_id); 338 } 339 uf_map(uint dst_lrg_id,uint src_lrg_id)340 void uf_map(uint dst_lrg_id, uint src_lrg_id) { 341 _uf_map.at_put(dst_lrg_id, src_lrg_id); 342 } 343 extend(uint idx,uint lrg_id)344 void extend(uint idx, uint lrg_id) { 345 _names.at_put_grow(idx, lrg_id); 346 } 347 uf_extend(uint dst_lrg_id,uint src_lrg_id)348 void uf_extend(uint dst_lrg_id, uint src_lrg_id) { 349 _uf_map.at_put_grow(dst_lrg_id, src_lrg_id); 350 } 351 LiveRangeMap(Arena * arena,uint unique)352 LiveRangeMap(Arena* arena, uint unique) 353 : _max_lrg_id(0) 354 , _uf_map(arena, unique, unique, 0) 355 , _names(arena, unique, unique, 0) {} 356 find_id(const Node * n)357 uint find_id( const Node *n ) { 358 uint retval = live_range_id(n); 359 assert(retval == find(n),"Invalid node to lidx mapping"); 360 return retval; 361 } 362 363 // Reset the Union-Find map to identity 364 void reset_uf_map(uint max_lrg_id); 365 366 // Make all Nodes map directly to their final live range; no need for 367 // the Union-Find mapping after this call. 368 void compress_uf_map_for_nodes(); 369 find(uint lidx)370 uint find(uint lidx) { 371 uint uf_lidx = _uf_map.at(lidx); 372 return (uf_lidx == lidx) ? uf_lidx : find_compress(lidx); 373 } 374 375 // Convert a Node into a Live Range Index - a lidx find(const Node * node)376 uint find(const Node *node) { 377 uint lidx = live_range_id(node); 378 uint uf_lidx = _uf_map.at(lidx); 379 return (uf_lidx == lidx) ? uf_lidx : find_compress(node); 380 } 381 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 find_const(const Node * node) const386 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 422 423 // Helper functions for Split() 424 uint split_DEF(Node *def, Block *b, int loc, uint max, Node **Reachblock, Node **debug_defs, GrowableArray<uint> splits, int slidx ); 425 uint split_USE(MachSpillCopyNode::SpillType spill_type, Node *def, Block *b, Node *use, uint useidx, uint max, bool def_down, bool cisc_sp, GrowableArray<uint> splits, int slidx ); 426 427 //------------------------------clone_projs------------------------------------ 428 // After cloning some rematerialized instruction, clone any MachProj's that 429 // follow it. Example: Intel zero is XOR, kills flags. Sparc FP constants 430 // use G3 as an address temp. 431 int clone_projs(Block* b, uint idx, Node* orig, Node* copy, uint& max_lrg_id); 432 clone_projs(Block * b,uint idx,Node * orig,Node * copy,LiveRangeMap & lrg_map)433 int clone_projs(Block* b, uint idx, Node* orig, Node* copy, LiveRangeMap& lrg_map) { 434 uint max_lrg_id = lrg_map.max_lrg_id(); 435 int found_projs = clone_projs(b, idx, orig, copy, max_lrg_id); 436 if (found_projs > 0) { 437 // max_lrg_id is updated during call above 438 lrg_map.set_max_lrg_id(max_lrg_id); 439 } 440 return found_projs; 441 } 442 443 Node *split_Rematerialize(Node *def, Block *b, uint insidx, uint &maxlrg, GrowableArray<uint> splits, 444 int slidx, uint *lrg2reach, Node **Reachblock, bool walkThru); 445 // True if lidx is used before any real register is def'd in the block 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); ~PhaseChaitin()467 ~PhaseChaitin() {} 468 469 LiveRangeMap _lrg_map; 470 lrgs(uint idx) const471 LRG &lrgs(uint idx) const { return _ifg->lrgs(idx); } 472 473 // Do all the real work of allocate 474 void Register_Allocate(); 475 high_frequency_lrg() const476 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 set_ifg(PhaseIFG & ifg)481 void set_ifg(PhaseIFG &ifg) { _ifg = &ifg; } set_live(PhaseLive & live)482 void set_live(PhaseLive &live) { _live = &live; } get_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 trace_spilling() const489 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 508 509 // Build the interference graph using virtual registers only. 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 lower(LRG & lrg,uint & location)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 raise(LRG & lrg)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 init(int limit)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 high_pressure_index() const563 uint high_pressure_index() const { 564 return _high_pressure_index; 565 } 566 final_pressure() const567 uint final_pressure() const { 568 return _final_pressure; 569 } 570 start_pressure() const571 uint start_pressure() const { 572 return _start_pressure; 573 } 574 current_pressure() const575 uint current_pressure() const { 576 return _current_pressure; 577 } 578 high_pressure_limit() const579 uint high_pressure_limit() const { 580 return _high_pressure_limit; 581 } 582 lower_high_pressure_index()583 void lower_high_pressure_index() { 584 _high_pressure_index--; 585 } 586 set_high_pressure_index_to_block_start()587 void set_high_pressure_index_to_block_start() { 588 _high_pressure_index = 0; 589 } 590 set_start_pressure(int value)591 void set_start_pressure(int value) { 592 _start_pressure = value; 593 _final_pressure = value; 594 } 595 set_current_pressure(int value)596 void set_current_pressure(int value) { 597 _current_pressure = value; 598 } 599 check_pressure_at_fatproj(uint fatproj_location,RegMask & fatproj_mask)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 Pressure(uint high_pressure_index,uint high_pressure_limit)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 677 // Simplify the IFG by removing LRGs of low degree with no copies 678 void Pre_Simplify(); 679 680 // Simplify the IFG by removing LRGs of low degree 681 void Simplify(); 682 683 // Select colors by re-inserting edges into the IFG. 684 // Return TRUE if any spills occurred. 685 uint Select( ); 686 // Helper function for select which allows biased coloring 687 OptoReg::Name choose_color( LRG &lrg, int chunk ); 688 // Helper function which implements biasing heuristic 689 OptoReg::Name bias_color( LRG &lrg, int chunk ); 690 691 // Split uncolorable live ranges 692 // Return new number of live ranges 693 uint Split(uint maxlrg, ResourceArea* split_arena); 694 695 // Copy 'was_spilled'-edness from one Node to another. 696 void copy_was_spilled( Node *src, Node *dst ); 697 // Set the 'spilled_once' or 'spilled_twice' flag on a node. 698 void set_was_spilled( Node *n ); 699 700 // Convert ideal spill-nodes into machine loads & stores 701 // Set C->failing when fixup spills could not complete, node limit exceeded. 702 void fixup_spills(); 703 704 // Post-Allocation peephole copy removal 705 void post_allocate_copy_removal(); 706 Node *skip_copies( Node *c ); 707 // Replace the old node with the current live version of that value 708 // and yank the old value if it's dead. replace_and_yank_if_dead(Node * old,OptoReg::Name nreg,Block * current_block,Node_List & value,Node_List & regnd)709 int replace_and_yank_if_dead( Node *old, OptoReg::Name nreg, 710 Block *current_block, Node_List& value, Node_List& regnd ) { 711 Node* v = regnd[nreg]; 712 assert(v->outcnt() != 0, "no dead values"); 713 old->replace_by(v); 714 return yank_if_dead(old, current_block, &value, ®nd); 715 } 716 yank_if_dead(Node * old,Block * current_block,Node_List * value,Node_List * regnd)717 int yank_if_dead( Node *old, Block *current_block, Node_List *value, Node_List *regnd ) { 718 return yank_if_dead_recurse(old, old, current_block, value, regnd); 719 } 720 int yank_if_dead_recurse(Node *old, Node *orig_old, Block *current_block, 721 Node_List *value, Node_List *regnd); 722 int yank( Node *old, Block *current_block, Node_List *value, Node_List *regnd ); 723 int elide_copy( Node *n, int k, Block *current_block, Node_List &value, Node_List ®nd, bool can_change_regs ); 724 int use_prior_register( Node *copy, uint idx, Node *def, Block *current_block, Node_List &value, Node_List ®nd ); 725 bool may_be_copy_of_callee( Node *def ) const; 726 727 // If nreg already contains the same constant as val then eliminate it 728 bool eliminate_copy_of_constant(Node* val, Node* n, 729 Block *current_block, Node_List& value, Node_List ®nd, 730 OptoReg::Name nreg, OptoReg::Name nreg2); 731 // Extend the node to LRG mapping 732 void add_reference( const Node *node, const Node *old_node); 733 734 // Record the first use of a def in the block for a register. 735 class RegDefUse { 736 Node* _def; 737 Node* _first_use; 738 public: RegDefUse()739 RegDefUse() : _def(NULL), _first_use(NULL) { } def() const740 Node* def() const { return _def; } first_use() const741 Node* first_use() const { return _first_use; } 742 update(Node * def,Node * use)743 void update(Node* def, Node* use) { 744 if (_def != def) { 745 _def = def; 746 _first_use = use; 747 } 748 } clear()749 void clear() { 750 _def = NULL; 751 _first_use = NULL; 752 } 753 }; 754 typedef GrowableArray<RegDefUse> RegToDefUseMap; 755 int possibly_merge_multidef(Node *n, uint k, Block *block, RegToDefUseMap& reg2defuse); 756 757 // Merge nodes that are a part of a multidef lrg and produce the same value within a block. 758 void merge_multidefs(); 759 760 private: 761 762 static int _final_loads, _final_stores, _final_copies, _final_memoves; 763 static double _final_load_cost, _final_store_cost, _final_copy_cost, _final_memove_cost; 764 static int _conserv_coalesce, _conserv_coalesce_pair; 765 static int _conserv_coalesce_trie, _conserv_coalesce_quad; 766 static int _post_alloc; 767 static int _lost_opp_pp_coalesce, _lost_opp_cflow_coalesce; 768 static int _used_cisc_instructions, _unused_cisc_instructions; 769 static int _allocator_attempts, _allocator_successes; 770 771 #ifndef PRODUCT 772 static uint _high_pressure, _low_pressure; 773 774 void dump() const; 775 void dump( const Node *n ) const; 776 void dump( const Block * b ) const; 777 void dump_degree_lists() const; 778 void dump_simplified() const; 779 void dump_lrg( uint lidx, bool defs_only) const; dump_lrg(uint lidx) const780 void dump_lrg( uint lidx) const { 781 // dump defs and uses by default 782 dump_lrg(lidx, false); 783 } 784 void dump_bb( uint pre_order ) const; 785 786 // Verify that base pointers and derived pointers are still sane 787 void verify_base_ptrs( ResourceArea *a ) const; 788 789 void verify( ResourceArea *a, bool verify_ifg = false ) const; 790 791 void dump_for_spill_split_recycle() const; 792 793 public: 794 void dump_frame() const; 795 char *dump_register( const Node *n, char *buf ) const; 796 private: 797 static void print_chaitin_statistics(); 798 #endif 799 friend class PhaseCoalesce; 800 friend class PhaseAggressiveCoalesce; 801 friend class PhaseConservativeCoalesce; 802 }; 803 804 #endif // SHARE_VM_OPTO_CHAITIN_HPP 805