1 /*
   2  * Copyright (c) 1998, 2016, 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 #include "precompiled.hpp"
  26 #include "compiler/oopMap.hpp"
  27 #include "memory/allocation.inline.hpp"
  28 #include "memory/resourceArea.hpp"
  29 #include "opto/addnode.hpp"
  30 #include "opto/block.hpp"
  31 #include "opto/callnode.hpp"
  32 #include "opto/cfgnode.hpp"
  33 #include "opto/chaitin.hpp"
  34 #include "opto/coalesce.hpp"
  35 #include "opto/indexSet.hpp"
  36 #include "opto/machnode.hpp"
  37 #include "opto/memnode.hpp"
  38 #include "opto/opcodes.hpp"
  39 
  40 PhaseIFG::PhaseIFG( Arena *arena ) : Phase(Interference_Graph), _arena(arena) {
  41 }
  42 
  43 void PhaseIFG::init( uint maxlrg ) {
  44   _maxlrg = maxlrg;
  45   _yanked = new (_arena) VectorSet(_arena);
  46   _is_square = false;
  47   // Make uninitialized adjacency lists
  48   _adjs = (IndexSet*)_arena->Amalloc(sizeof(IndexSet)*maxlrg);
  49   // Also make empty live range structures
  50   _lrgs = (LRG *)_arena->Amalloc( maxlrg * sizeof(LRG) );
  51   memset(_lrgs,0,sizeof(LRG)*maxlrg);
  52   // Init all to empty
  53   for( uint i = 0; i < maxlrg; i++ ) {
  54     _adjs[i].initialize(maxlrg);
  55     _lrgs[i].Set_All();
  56   }
  57 }
  58 
  59 // Add edge between vertices a & b.  These are sorted (triangular matrix),
  60 // then the smaller number is inserted in the larger numbered array.
  61 int PhaseIFG::add_edge( uint a, uint b ) {
  62   lrgs(a).invalid_degree();
  63   lrgs(b).invalid_degree();
  64   // Sort a and b, so that a is bigger
  65   assert( !_is_square, "only on triangular" );
  66   if( a < b ) { uint tmp = a; a = b; b = tmp; }
  67   return _adjs[a].insert( b );
  68 }
  69 
  70 // Add an edge between 'a' and everything in the vector.
  71 void PhaseIFG::add_vector( uint a, IndexSet *vec ) {
  72   // IFG is triangular, so do the inserts where 'a' < 'b'.
  73   assert( !_is_square, "only on triangular" );
  74   IndexSet *adjs_a = &_adjs[a];
  75   if( !vec->count() ) return;
  76 
  77   IndexSetIterator elements(vec);
  78   uint neighbor;
  79   while ((neighbor = elements.next()) != 0) {
  80     add_edge( a, neighbor );
  81   }
  82 }
  83 
  84 // Is there an edge between a and b?
  85 int PhaseIFG::test_edge( uint a, uint b ) const {
  86   // Sort a and b, so that a is larger
  87   assert( !_is_square, "only on triangular" );
  88   if( a < b ) { uint tmp = a; a = b; b = tmp; }
  89   return _adjs[a].member(b);
  90 }
  91 
  92 // Convert triangular matrix to square matrix
  93 void PhaseIFG::SquareUp() {
  94   assert( !_is_square, "only on triangular" );
  95 
  96   // Simple transpose
  97   for( uint i = 0; i < _maxlrg; i++ ) {
  98     IndexSetIterator elements(&_adjs[i]);
  99     uint datum;
 100     while ((datum = elements.next()) != 0) {
 101       _adjs[datum].insert( i );
 102     }
 103   }
 104   _is_square = true;
 105 }
 106 
 107 // Compute effective degree in bulk
 108 void PhaseIFG::Compute_Effective_Degree() {
 109   assert( _is_square, "only on square" );
 110 
 111   for( uint i = 0; i < _maxlrg; i++ )
 112     lrgs(i).set_degree(effective_degree(i));
 113 }
 114 
 115 int PhaseIFG::test_edge_sq( uint a, uint b ) const {
 116   assert( _is_square, "only on square" );
 117   // Swap, so that 'a' has the lesser count.  Then binary search is on
 118   // the smaller of a's list and b's list.
 119   if( neighbor_cnt(a) > neighbor_cnt(b) ) { uint tmp = a; a = b; b = tmp; }
 120   //return _adjs[a].unordered_member(b);
 121   return _adjs[a].member(b);
 122 }
 123 
 124 // Union edges of B into A
 125 void PhaseIFG::Union( uint a, uint b ) {
 126   assert( _is_square, "only on square" );
 127   IndexSet *A = &_adjs[a];
 128   IndexSetIterator b_elements(&_adjs[b]);
 129   uint datum;
 130   while ((datum = b_elements.next()) != 0) {
 131     if(A->insert(datum)) {
 132       _adjs[datum].insert(a);
 133       lrgs(a).invalid_degree();
 134       lrgs(datum).invalid_degree();
 135     }
 136   }
 137 }
 138 
 139 // Yank a Node and all connected edges from the IFG.  Return a
 140 // list of neighbors (edges) yanked.
 141 IndexSet *PhaseIFG::remove_node( uint a ) {
 142   assert( _is_square, "only on square" );
 143   assert( !_yanked->test(a), "" );
 144   _yanked->set(a);
 145 
 146   // I remove the LRG from all neighbors.
 147   IndexSetIterator elements(&_adjs[a]);
 148   LRG &lrg_a = lrgs(a);
 149   uint datum;
 150   while ((datum = elements.next()) != 0) {
 151     _adjs[datum].remove(a);
 152     lrgs(datum).inc_degree( -lrg_a.compute_degree(lrgs(datum)) );
 153   }
 154   return neighbors(a);
 155 }
 156 
 157 // Re-insert a yanked Node.
 158 void PhaseIFG::re_insert( uint a ) {
 159   assert( _is_square, "only on square" );
 160   assert( _yanked->test(a), "" );
 161   (*_yanked) >>= a;
 162 
 163   IndexSetIterator elements(&_adjs[a]);
 164   uint datum;
 165   while ((datum = elements.next()) != 0) {
 166     _adjs[datum].insert(a);
 167     lrgs(datum).invalid_degree();
 168   }
 169 }
 170 
 171 // Compute the degree between 2 live ranges.  If both live ranges are
 172 // aligned-adjacent powers-of-2 then we use the MAX size.  If either is
 173 // mis-aligned (or for Fat-Projections, not-adjacent) then we have to
 174 // MULTIPLY the sizes.  Inspect Brigg's thesis on register pairs to see why
 175 // this is so.
 176 int LRG::compute_degree( LRG &l ) const {
 177   int tmp;
 178   int num_regs = _num_regs;
 179   int nregs = l.num_regs();
 180   tmp =  (_fat_proj || l._fat_proj)     // either is a fat-proj?
 181     ? (num_regs * nregs)                // then use product
 182     : MAX2(num_regs,nregs);             // else use max
 183   return tmp;
 184 }
 185 
 186 // Compute effective degree for this live range.  If both live ranges are
 187 // aligned-adjacent powers-of-2 then we use the MAX size.  If either is
 188 // mis-aligned (or for Fat-Projections, not-adjacent) then we have to
 189 // MULTIPLY the sizes.  Inspect Brigg's thesis on register pairs to see why
 190 // this is so.
 191 int PhaseIFG::effective_degree( uint lidx ) const {
 192   int eff = 0;
 193   int num_regs = lrgs(lidx).num_regs();
 194   int fat_proj = lrgs(lidx)._fat_proj;
 195   IndexSet *s = neighbors(lidx);
 196   IndexSetIterator elements(s);
 197   uint nidx;
 198   while((nidx = elements.next()) != 0) {
 199     LRG &lrgn = lrgs(nidx);
 200     int nregs = lrgn.num_regs();
 201     eff += (fat_proj || lrgn._fat_proj) // either is a fat-proj?
 202       ? (num_regs * nregs)              // then use product
 203       : MAX2(num_regs,nregs);           // else use max
 204   }
 205   return eff;
 206 }
 207 
 208 
 209 #ifndef PRODUCT
 210 void PhaseIFG::dump() const {
 211   tty->print_cr("-- Interference Graph --%s--",
 212                 _is_square ? "square" : "triangular" );
 213   if( _is_square ) {
 214     for( uint i = 0; i < _maxlrg; i++ ) {
 215       tty->print( (*_yanked)[i] ? "XX " : "  ");
 216       tty->print("L%d: { ",i);
 217       IndexSetIterator elements(&_adjs[i]);
 218       uint datum;
 219       while ((datum = elements.next()) != 0) {
 220         tty->print("L%d ", datum);
 221       }
 222       tty->print_cr("}");
 223 
 224     }
 225     return;
 226   }
 227 
 228   // Triangular
 229   for( uint i = 0; i < _maxlrg; i++ ) {
 230     uint j;
 231     tty->print( (*_yanked)[i] ? "XX " : "  ");
 232     tty->print("L%d: { ",i);
 233     for( j = _maxlrg; j > i; j-- )
 234       if( test_edge(j - 1,i) ) {
 235         tty->print("L%d ",j - 1);
 236       }
 237     tty->print("| ");
 238     IndexSetIterator elements(&_adjs[i]);
 239     uint datum;
 240     while ((datum = elements.next()) != 0) {
 241       tty->print("L%d ", datum);
 242     }
 243     tty->print("}\n");
 244   }
 245   tty->print("\n");
 246 }
 247 
 248 void PhaseIFG::stats() const {
 249   ResourceMark rm;
 250   int *h_cnt = NEW_RESOURCE_ARRAY(int,_maxlrg*2);
 251   memset( h_cnt, 0, sizeof(int)*_maxlrg*2 );
 252   uint i;
 253   for( i = 0; i < _maxlrg; i++ ) {
 254     h_cnt[neighbor_cnt(i)]++;
 255   }
 256   tty->print_cr("--Histogram of counts--");
 257   for( i = 0; i < _maxlrg*2; i++ )
 258     if( h_cnt[i] )
 259       tty->print("%d/%d ",i,h_cnt[i]);
 260   tty->cr();
 261 }
 262 
 263 void PhaseIFG::verify( const PhaseChaitin *pc ) const {
 264   // IFG is square, sorted and no need for Find
 265   for( uint i = 0; i < _maxlrg; i++ ) {
 266     assert(!((*_yanked)[i]) || !neighbor_cnt(i), "Is removed completely" );
 267     IndexSet *set = &_adjs[i];
 268     IndexSetIterator elements(set);
 269     uint idx;
 270     uint last = 0;
 271     while ((idx = elements.next()) != 0) {
 272       assert(idx != i, "Must have empty diagonal");
 273       assert(pc->_lrg_map.find_const(idx) == idx, "Must not need Find");
 274       assert(_adjs[idx].member(i), "IFG not square");
 275       assert(!(*_yanked)[idx], "No yanked neighbors");
 276       assert(last < idx, "not sorted increasing");
 277       last = idx;
 278     }
 279     assert(!lrgs(i)._degree_valid || effective_degree(i) == lrgs(i).degree(), "degree is valid but wrong");
 280   }
 281 }
 282 #endif
 283 
 284 /*
 285  * Interfere this register with everything currently live.
 286  * Check for interference by checking overlap of regmasks.
 287  * Only interfere if acceptable register masks overlap.
 288  */
 289 void PhaseChaitin::interfere_with_live(uint lid, IndexSet* liveout) {
 290   LRG& lrg = lrgs(lid);
 291   const RegMask& rm = lrg.mask();
 292   IndexSetIterator elements(liveout);
 293   uint interfering_lid = elements.next();
 294   while (interfering_lid != 0) {
 295     LRG& interfering_lrg = lrgs(interfering_lid);
 296     if (rm.overlap(interfering_lrg.mask())) {
 297       _ifg->add_edge(lid, interfering_lid);
 298     }
 299     interfering_lid = elements.next();
 300   }
 301 }
 302 
 303 // Actually build the interference graph.  Uses virtual registers only, no
 304 // physical register masks.  This allows me to be very aggressive when
 305 // coalescing copies.  Some of this aggressiveness will have to be undone
 306 // later, but I'd rather get all the copies I can now (since unremoved copies
 307 // at this point can end up in bad places).  Copies I re-insert later I have
 308 // more opportunity to insert them in low-frequency locations.
 309 void PhaseChaitin::build_ifg_virtual( ) {
 310   Compile::TracePhase tp("buildIFG_virt", &timers[_t_buildIFGvirtual]);
 311 
 312   // For all blocks (in any order) do...
 313   for (uint i = 0; i < _cfg.number_of_blocks(); i++) {
 314     Block* block = _cfg.get_block(i);
 315     IndexSet* liveout = _live->live(block);
 316 
 317     // The IFG is built by a single reverse pass over each basic block.
 318     // Starting with the known live-out set, we remove things that get
 319     // defined and add things that become live (essentially executing one
 320     // pass of a standard LIVE analysis). Just before a Node defines a value
 321     // (and removes it from the live-ness set) that value is certainly live.
 322     // The defined value interferes with everything currently live.  The
 323     // value is then removed from the live-ness set and it's inputs are
 324     // added to the live-ness set.
 325     for (uint j = block->end_idx() + 1; j > 1; j--) {
 326       Node* n = block->get_node(j - 1);
 327 
 328       // Get value being defined
 329       uint r = _lrg_map.live_range_id(n);
 330 
 331       // Some special values do not allocate
 332       if (r) {
 333 
 334         // Remove from live-out set
 335         liveout->remove(r);
 336 
 337         // Copies do not define a new value and so do not interfere.
 338         // Remove the copies source from the liveout set before interfering.
 339         uint idx = n->is_Copy();
 340         if (idx != 0) {
 341           liveout->remove(_lrg_map.live_range_id(n->in(idx)));
 342         }
 343 
 344         // Interfere with everything live
 345         interfere_with_live(r, liveout);
 346       }
 347 
 348       // Make all inputs live
 349       if (!n->is_Phi()) {      // Phi function uses come from prior block
 350         for(uint k = 1; k < n->req(); k++) {
 351           liveout->insert(_lrg_map.live_range_id(n->in(k)));
 352         }
 353       }
 354 
 355       // 2-address instructions always have the defined value live
 356       // on entry to the instruction, even though it is being defined
 357       // by the instruction.  We pretend a virtual copy sits just prior
 358       // to the instruction and kills the src-def'd register.
 359       // In other words, for 2-address instructions the defined value
 360       // interferes with all inputs.
 361       uint idx;
 362       if( n->is_Mach() && (idx = n->as_Mach()->two_adr()) ) {
 363         const MachNode *mach = n->as_Mach();
 364         // Sometimes my 2-address ADDs are commuted in a bad way.
 365         // We generally want the USE-DEF register to refer to the
 366         // loop-varying quantity, to avoid a copy.
 367         Opcodes op = mach->ideal_Opcode();
 368         // Check that mach->num_opnds() == 3 to ensure instruction is
 369         // not subsuming constants, effectively excludes addI_cin_imm
 370         // Can NOT swap for instructions like addI_cin_imm since it
 371         // is adding zero to yhi + carry and the second ideal-input
 372         // points to the result of adding low-halves.
 373         // Checking req() and num_opnds() does NOT distinguish addI_cout from addI_cout_imm
 374         if( (op == Opcodes::Op_AddI && mach->req() == 3 && mach->num_opnds() == 3) &&
 375             n->in(1)->bottom_type()->base() == Type::Int &&
 376             // See if the ADD is involved in a tight data loop the wrong way
 377             n->in(2)->is_Phi() &&
 378             n->in(2)->in(2) == n ) {
 379           Node *tmp = n->in(1);
 380           n->set_req( 1, n->in(2) );
 381           n->set_req( 2, tmp );
 382         }
 383         // Defined value interferes with all inputs
 384         uint lidx = _lrg_map.live_range_id(n->in(idx));
 385         for (uint k = 1; k < n->req(); k++) {
 386           uint kidx = _lrg_map.live_range_id(n->in(k));
 387           if (kidx != lidx) {
 388             _ifg->add_edge(r, kidx);
 389           }
 390         }
 391       }
 392     } // End of forall instructions in block
 393   } // End of forall blocks
 394 }
 395 
 396 #ifdef ASSERT
 397 uint PhaseChaitin::count_int_pressure(IndexSet* liveout) {
 398   IndexSetIterator elements(liveout);
 399   uint lidx = elements.next();
 400   uint cnt = 0;
 401   while (lidx != 0) {
 402     LRG& lrg = lrgs(lidx);
 403     if (lrg.mask_is_nonempty_and_up() &&
 404         !lrg.is_float_or_vector() &&
 405         lrg.mask().overlap(*Matcher::idealreg2regmask[static_cast<uint>(Opcodes::Op_RegI)])) {
 406       cnt += lrg.reg_pressure();
 407     }
 408     lidx = elements.next();
 409   }
 410   return cnt;
 411 }
 412 
 413 uint PhaseChaitin::count_float_pressure(IndexSet* liveout) {
 414   IndexSetIterator elements(liveout);
 415   uint lidx = elements.next();
 416   uint cnt = 0;
 417   while (lidx != 0) {
 418     LRG& lrg = lrgs(lidx);
 419     if (lrg.mask_is_nonempty_and_up() && lrg.is_float_or_vector()) {
 420       cnt += lrg.reg_pressure();
 421     }
 422     lidx = elements.next();
 423   }
 424   return cnt;
 425 }
 426 #endif
 427 
 428 /*
 429  * Adjust register pressure down by 1.  Capture last hi-to-low transition,
 430  */
 431 void PhaseChaitin::lower_pressure(Block* b, uint location, LRG& lrg, IndexSet* liveout, Pressure& int_pressure, Pressure& float_pressure) {
 432   if (lrg.mask_is_nonempty_and_up()) {
 433     if (lrg.is_float_or_vector()) {
 434       float_pressure.lower(lrg, location);
 435     } else {
 436       // Do not count the SP and flag registers
 437       const RegMask& r = lrg.mask();
 438       if (r.overlap(*Matcher::idealreg2regmask[static_cast<uint>(Opcodes::Op_RegI)])) {
 439         int_pressure.lower(lrg, location);
 440       }
 441     }
 442   }
 443   if (_scheduling_info_generated == false) {
 444     assert(int_pressure.current_pressure() == count_int_pressure(liveout), "the int pressure is incorrect");
 445     assert(float_pressure.current_pressure() == count_float_pressure(liveout), "the float pressure is incorrect");
 446   }
 447 }
 448 
 449 /* Go to the first non-phi index in a block */
 450 static uint first_nonphi_index(Block* b) {
 451   uint i;
 452   uint end_idx = b->end_idx();
 453   for (i = 1; i < end_idx; i++) {
 454     Node* n = b->get_node(i);
 455     if (!n->is_Phi()) {
 456       break;
 457     }
 458   }
 459   return i;
 460 }
 461 
 462 /*
 463  * Spills could be inserted before a CreateEx node which should be the first
 464  * instruction in a block after Phi nodes. If so, move the CreateEx node up.
 465  */
 466 static void move_exception_node_up(Block* b, uint first_inst, uint last_inst) {
 467   for (uint i = first_inst; i < last_inst; i++) {
 468     Node* ex = b->get_node(i);
 469     if (ex->is_SpillCopy()) {
 470       continue;
 471     }
 472 
 473     if (i > first_inst &&
 474         ex->is_Mach() && ex->as_Mach()->ideal_Opcode() == Opcodes::Op_CreateEx) {
 475       b->remove_node(i);
 476       b->insert_node(ex, first_inst);
 477     }
 478     // Stop once a CreateEx or any other node is found
 479     break;
 480   }
 481 }
 482 
 483 /*
 484  * When new live ranges are live, we raise the register pressure
 485  */
 486 void PhaseChaitin::raise_pressure(Block* b, LRG& lrg, Pressure& int_pressure, Pressure& float_pressure) {
 487   if (lrg.mask_is_nonempty_and_up()) {
 488     if (lrg.is_float_or_vector()) {
 489       float_pressure.raise(lrg);
 490     } else {
 491       // Do not count the SP and flag registers
 492       const RegMask& rm = lrg.mask();
 493       if (rm.overlap(*Matcher::idealreg2regmask[static_cast<uint>(Opcodes::Op_RegI)])) {
 494         int_pressure.raise(lrg);
 495       }
 496     }
 497   }
 498 }
 499 
 500 
 501 /*
 502  * Computes the initial register pressure of a block, looking at all live
 503  * ranges in the liveout. The register pressure is computed for both float
 504  * and int/pointer registers.
 505  * Live ranges in the liveout are presumed live for the whole block.
 506  * We add the cost for the whole block to the area of the live ranges initially.
 507  * If a live range gets killed in the block, we'll subtract the unused part of
 508  * the block from the area.
 509  */
 510 void PhaseChaitin::compute_initial_block_pressure(Block* b, IndexSet* liveout, Pressure& int_pressure, Pressure& float_pressure, double cost) {
 511   IndexSetIterator elements(liveout);
 512   uint lid = elements.next();
 513   while (lid != 0) {
 514     LRG& lrg = lrgs(lid);
 515     lrg._area += cost;
 516     raise_pressure(b, lrg, int_pressure, float_pressure);
 517     lid = elements.next();
 518   }
 519   assert(int_pressure.current_pressure() == count_int_pressure(liveout), "the int pressure is incorrect");
 520   assert(float_pressure.current_pressure() == count_float_pressure(liveout), "the float pressure is incorrect");
 521 }
 522 
 523 /*
 524 * Computes the entry register pressure of a block, looking at all live
 525 * ranges in the livein. The register pressure is computed for both float
 526 * and int/pointer registers.
 527 */
 528 void PhaseChaitin::compute_entry_block_pressure(Block* b) {
 529   IndexSet* livein = _live->livein(b);
 530   IndexSetIterator elements(livein);
 531   uint lid = elements.next();
 532   while (lid != 0) {
 533     LRG& lrg = lrgs(lid);
 534     raise_pressure(b, lrg, _sched_int_pressure, _sched_float_pressure);
 535     lid = elements.next();
 536   }
 537   // Now check phis for locally defined inputs
 538   for (uint j = 0; j < b->number_of_nodes(); j++) {
 539     Node* n = b->get_node(j);
 540     if (n->is_Phi()) {
 541       for (uint k = 1; k < n->req(); k++) {
 542         Node* phi_in = n->in(k);
 543         // Because we are talking about phis, raise register pressure once for each
 544         // instance of a phi to account for a single value
 545         if (_cfg.get_block_for_node(phi_in) == b) {
 546           LRG& lrg = lrgs(phi_in->_idx);
 547           raise_pressure(b, lrg, _sched_int_pressure, _sched_float_pressure);
 548           break;
 549         }
 550       }
 551     }
 552   }
 553   _sched_int_pressure.set_start_pressure(_sched_int_pressure.current_pressure());
 554   _sched_float_pressure.set_start_pressure(_sched_float_pressure.current_pressure());
 555 }
 556 
 557 /*
 558 * Computes the exit register pressure of a block, looking at all live
 559 * ranges in the liveout. The register pressure is computed for both float
 560 * and int/pointer registers.
 561 */
 562 void PhaseChaitin::compute_exit_block_pressure(Block* b) {
 563   IndexSet* livein = _live->live(b);
 564   IndexSetIterator elements(livein);
 565   _sched_int_pressure.set_current_pressure(0);
 566   _sched_float_pressure.set_current_pressure(0);
 567   uint lid = elements.next();
 568   while (lid != 0) {
 569     LRG& lrg = lrgs(lid);
 570     raise_pressure(b, lrg, _sched_int_pressure, _sched_float_pressure);
 571     lid = elements.next();
 572   }
 573 }
 574 
 575 /*
 576  * Remove dead node if it's not used.
 577  * We only remove projection nodes if the node "defining" the projection is
 578  * dead, for example on x86, if we have a dead Add node we remove its
 579  * RFLAGS node.
 580  */
 581 bool PhaseChaitin::remove_node_if_not_used(Block* b, uint location, Node* n, uint lid, IndexSet* liveout) {
 582   Node* def = n->in(0);
 583   if (!n->is_Proj() ||
 584       (_lrg_map.live_range_id(def) && !liveout->member(_lrg_map.live_range_id(def)))) {
 585     if (n->is_MachProj()) {
 586       // Don't remove KILL projections if their "defining" nodes have
 587       // memory effects (have SCMemProj projection node) -
 588       // they are not dead even when their result is not used.
 589       // For example, compareAndSwapL (and other CAS) and EncodeISOArray nodes.
 590       // The method add_input_to_liveout() keeps such nodes alive (put them on liveout list)
 591       // when it sees SCMemProj node in a block. Unfortunately SCMemProj node could be placed
 592       // in block in such order that KILL MachProj nodes are processed first.
 593       if (def->has_out_with(Opcodes::Op_SCMemProj)) {
 594         return false;
 595       }
 596     }
 597     b->remove_node(location);
 598     LRG& lrg = lrgs(lid);
 599     if (lrg._def == n) {
 600       lrg._def = 0;
 601     }
 602     n->disconnect_inputs(NULL, C);
 603     _cfg.unmap_node_from_block(n);
 604     n->replace_by(C->top());
 605     return true;
 606   }
 607   return false;
 608 }
 609 
 610 /*
 611  * When encountering a fat projection, we might go from a low to high to low
 612  * (since the fat proj only lives at this instruction) going backwards in the
 613  * block. If we find a low to high transition, we record it.
 614  */
 615 void PhaseChaitin::check_for_high_pressure_transition_at_fatproj(uint& block_reg_pressure, uint location, LRG& lrg, Pressure& pressure, const Opcodes op_regtype) {
 616   RegMask mask_tmp = lrg.mask();
 617   mask_tmp.AND(*Matcher::idealreg2regmask[static_cast<uint>(op_regtype)]);
 618   pressure.check_pressure_at_fatproj(location, mask_tmp);
 619 }
 620 
 621 /*
 622  * Insure high score for immediate-use spill copies so they get a color.
 623  * All single-use MachSpillCopy(s) that immediately precede their
 624  * use must color early.  If a longer live range steals their
 625  * color, the spill copy will split and may push another spill copy
 626  * further away resulting in an infinite spill-split-retry cycle.
 627  * Assigning a zero area results in a high score() and a good
 628  * location in the simplify list.
 629  */
 630 void PhaseChaitin::assign_high_score_to_immediate_copies(Block* b, Node* n, LRG& lrg, uint next_inst, uint last_inst) {
 631   if (n->is_SpillCopy() &&
 632       lrg.is_singledef() && // A multi defined live range can still split
 633       n->outcnt() == 1 &&   // and use must be in this block
 634       _cfg.get_block_for_node(n->unique_out()) == b) {
 635 
 636     Node* single_use = n->unique_out();
 637     assert(b->find_node(single_use) >= next_inst, "Use must be later in block");
 638     // Use can be earlier in block if it is a Phi, but then I should be a MultiDef
 639 
 640     // Find first non SpillCopy 'm' that follows the current instruction
 641     // (current_inst - 1) is index for current instruction 'n'
 642     Node* m = n;
 643     for (uint i = next_inst; i <= last_inst && m->is_SpillCopy(); ++i) {
 644       m = b->get_node(i);
 645     }
 646     if (m == single_use) {
 647       lrg._area = 0.0;
 648     }
 649   }
 650 }
 651 
 652 /*
 653  * Copies do not define a new value and so do not interfere.
 654  * Remove the copies source from the liveout set before interfering.
 655  */
 656 void PhaseChaitin::remove_interference_from_copy(Block* b, uint location, uint lid_copy, IndexSet* liveout, double cost, Pressure& int_pressure, Pressure& float_pressure) {
 657   if (liveout->remove(lid_copy)) {
 658     LRG& lrg_copy = lrgs(lid_copy);
 659     lrg_copy._area -= cost;
 660 
 661     // Lower register pressure since copy and definition can share the same register
 662     lower_pressure(b, location, lrg_copy, liveout, int_pressure, float_pressure);
 663   }
 664 }
 665 
 666 /*
 667  * The defined value must go in a particular register. Remove that register from
 668  * all conflicting parties and avoid the interference.
 669  */
 670 void PhaseChaitin::remove_bound_register_from_interfering_live_ranges(LRG& lrg, IndexSet* liveout, uint& must_spill) {
 671   // Check for common case
 672   const RegMask& rm = lrg.mask();
 673   int r_size = lrg.num_regs();
 674   // Smear odd bits
 675   IndexSetIterator elements(liveout);
 676   uint l = elements.next();
 677   while (l != 0) {
 678     LRG& interfering_lrg = lrgs(l);
 679     // If 'l' must spill already, do not further hack his bits.
 680     // He'll get some interferences and be forced to spill later.
 681     if (interfering_lrg._must_spill) {
 682       l = elements.next();
 683       continue;
 684     }
 685 
 686     // Remove bound register(s) from 'l's choices
 687     RegMask old = interfering_lrg.mask();
 688     uint old_size = interfering_lrg.mask_size();
 689 
 690     // Remove the bits from LRG 'rm' from LRG 'l' so 'l' no
 691     // longer interferes with 'rm'.  If 'l' requires aligned
 692     // adjacent pairs, subtract out bit pairs.
 693     assert(!interfering_lrg._is_vector || !interfering_lrg._fat_proj, "sanity");
 694 
 695     if (interfering_lrg.num_regs() > 1 && !interfering_lrg._fat_proj) {
 696       RegMask r2mask = rm;
 697       // Leave only aligned set of bits.
 698       r2mask.smear_to_sets(interfering_lrg.num_regs());
 699       // It includes vector case.
 700       interfering_lrg.SUBTRACT(r2mask);
 701       interfering_lrg.compute_set_mask_size();
 702     } else if (r_size != 1) {
 703       // fat proj
 704       interfering_lrg.SUBTRACT(rm);
 705       interfering_lrg.compute_set_mask_size();
 706     } else {
 707       // Common case: size 1 bound removal
 708       OptoReg::Name r_reg = rm.find_first_elem();
 709       if (interfering_lrg.mask().Member(r_reg)) {
 710         interfering_lrg.Remove(r_reg);
 711         interfering_lrg.set_mask_size(interfering_lrg.mask().is_AllStack() ? LRG::AllStack_size : old_size - 1);
 712       }
 713     }
 714 
 715     // If 'l' goes completely dry, it must spill.
 716     if (interfering_lrg.not_free()) {
 717       // Give 'l' some kind of reasonable mask, so it picks up
 718       // interferences (and will spill later).
 719       interfering_lrg.set_mask(old);
 720       interfering_lrg.set_mask_size(old_size);
 721       must_spill++;
 722       interfering_lrg._must_spill = 1;
 723       interfering_lrg.set_reg(OptoReg::Name(LRG::SPILL_REG));
 724     }
 725     l = elements.next();
 726   }
 727 }
 728 
 729 /*
 730  * Start loop at 1 (skip control edge) for most Nodes. SCMemProj's might be the
 731  * sole use of a StoreLConditional. While StoreLConditionals set memory (the
 732  * SCMemProj use) they also def flags; if that flag def is unused the allocator
 733  * sees a flag-setting instruction with no use of the flags and assumes it's
 734  * dead.  This keeps the (useless) flag-setting behavior alive while also
 735  * keeping the (useful) memory update effect.
 736  */
 737 void PhaseChaitin::add_input_to_liveout(Block* b, Node* n, IndexSet* liveout, double cost, Pressure& int_pressure, Pressure& float_pressure) {
 738   JVMState* jvms = n->jvms();
 739   uint debug_start = jvms ? jvms->debug_start() : 999999;
 740 
 741   for (uint k = ((n->Opcode() == Opcodes::Op_SCMemProj) ? 0:1); k < n->req(); k++) {
 742     Node* def = n->in(k);
 743     uint lid = _lrg_map.live_range_id(def);
 744     if (!lid) {
 745       continue;
 746     }
 747     LRG& lrg = lrgs(lid);
 748 
 749     // No use-side cost for spilling debug info
 750     if (k < debug_start) {
 751       // A USE costs twice block frequency (once for the Load, once
 752       // for a Load-delay).  Rematerialized uses only cost once.
 753       lrg._cost += (def->rematerialize() ? b->_freq : (b->_freq * 2));
 754     }
 755 
 756     if (liveout->insert(lid)) {
 757       // Newly live things assumed live from here to top of block
 758       lrg._area += cost;
 759       raise_pressure(b, lrg, int_pressure, float_pressure);
 760       assert(int_pressure.current_pressure() == count_int_pressure(liveout), "the int pressure is incorrect");
 761       assert(float_pressure.current_pressure() == count_float_pressure(liveout), "the float pressure is incorrect");
 762     }
 763     assert(lrg._area >= 0.0, "negative spill area" );
 764   }
 765 }
 766 
 767 /*
 768  * If we run off the top of the block with high pressure just record that the
 769  * whole block is high pressure. (Even though we might have a transition
 770  * later down in the block)
 771  */
 772 void PhaseChaitin::check_for_high_pressure_block(Pressure& pressure) {
 773   // current pressure now means the pressure before the first instruction in the block
 774   // (since we have stepped through all instructions backwards)
 775   if (pressure.current_pressure() > pressure.high_pressure_limit()) {
 776     pressure.set_high_pressure_index_to_block_start();
 777   }
 778 }
 779 
 780 /*
 781  * Compute high pressure indice; avoid landing in the middle of projnodes
 782  * and set the high pressure index for the block
 783  */
 784 void PhaseChaitin::adjust_high_pressure_index(Block* b, uint& block_hrp_index, Pressure& pressure) {
 785   uint i = pressure.high_pressure_index();
 786   if (i < b->number_of_nodes() && i < b->end_idx() + 1) {
 787     Node* cur = b->get_node(i);
 788     while (cur->is_Proj() || (cur->is_MachNullCheck()) || cur->is_Catch()) {
 789       cur = b->get_node(--i);
 790     }
 791   }
 792   block_hrp_index = i;
 793 }
 794 
 795 void PhaseChaitin::print_pressure_info(Pressure& pressure, const char *str) {
 796   if (str != NULL) {
 797     tty->print_cr("#  *** %s ***", str);
 798   }
 799   tty->print_cr("#     start pressure is = %d", pressure.start_pressure());
 800   tty->print_cr("#     max pressure is = %d", pressure.final_pressure());
 801   tty->print_cr("#     end pressure is = %d", pressure.current_pressure());
 802   tty->print_cr("#");
 803 }
 804 
 805 /* Build an interference graph:
 806  *   That is, if 2 live ranges are simultaneously alive but in their acceptable
 807  *   register sets do not overlap, then they do not interfere. The IFG is built
 808  *   by a single reverse pass over each basic block. Starting with the known
 809  *   live-out set, we remove things that get defined and add things that become
 810  *   live (essentially executing one pass of a standard LIVE analysis). Just
 811  *   before a Node defines a value (and removes it from the live-ness set) that
 812  *   value is certainly live. The defined value interferes with everything
 813  *   currently live. The value is then removed from the live-ness set and it's
 814  *   inputs are added to the live-ness set.
 815  * Compute register pressure for each block:
 816  *   We store the biggest register pressure for each block and also the first
 817  *   low to high register pressure transition within the block (if any).
 818  */
 819 uint PhaseChaitin::build_ifg_physical( ResourceArea *a ) {
 820   Compile::TracePhase tp("buildIFG", &timers[_t_buildIFGphysical]);
 821 
 822   uint must_spill = 0;
 823   for (uint i = 0; i < _cfg.number_of_blocks(); i++) {
 824     Block* block = _cfg.get_block(i);
 825 
 826     // Clone (rather than smash in place) the liveout info, so it is alive
 827     // for the "collect_gc_info" phase later.
 828     IndexSet liveout(_live->live(block));
 829 
 830     uint first_inst = first_nonphi_index(block);
 831     uint last_inst = block->end_idx();
 832 
 833     move_exception_node_up(block, first_inst, last_inst);
 834 
 835     Pressure int_pressure(last_inst + 1, INTPRESSURE);
 836     Pressure float_pressure(last_inst + 1, FLOATPRESSURE);
 837     block->_reg_pressure = 0;
 838     block->_freg_pressure = 0;
 839 
 840     int inst_count = last_inst - first_inst;
 841     double cost = (inst_count <= 0) ? 0.0 : block->_freq * double(inst_count);
 842     assert(cost >= 0.0, "negative spill cost" );
 843 
 844     compute_initial_block_pressure(block, &liveout, int_pressure, float_pressure, cost);
 845 
 846     for (uint location = last_inst; location > 0; location--) {
 847       Node* n = block->get_node(location);
 848       uint lid = _lrg_map.live_range_id(n);
 849 
 850       if(lid) {
 851         LRG& lrg = lrgs(lid);
 852 
 853         // A DEF normally costs block frequency; rematerialized values are
 854         // removed from the DEF sight, so LOWER costs here.
 855         lrg._cost += n->rematerialize() ? 0 : block->_freq;
 856 
 857         if (!liveout.member(lid) && n->Opcode() != Opcodes::Op_SafePoint) {
 858           if (remove_node_if_not_used(block, location, n, lid, &liveout)) {
 859             float_pressure.lower_high_pressure_index();
 860             int_pressure.lower_high_pressure_index();
 861             continue;
 862           }
 863           if (lrg._fat_proj) {
 864             check_for_high_pressure_transition_at_fatproj(block->_reg_pressure, location, lrg, int_pressure, Opcodes::Op_RegI);
 865             check_for_high_pressure_transition_at_fatproj(block->_freg_pressure, location, lrg, float_pressure, Opcodes::Op_RegD);
 866           }
 867         } else {
 868           // A live range ends at its definition, remove the remaining area.
 869           // If the cost is +Inf (which might happen in extreme cases), the lrg area will also be +Inf,
 870           // and +Inf - +Inf = NaN. So let's not do that subtraction.
 871           if (g_isfinite(cost)) {
 872             lrg._area -= cost;
 873           }
 874           assert(lrg._area >= 0.0, "negative spill area" );
 875 
 876           assign_high_score_to_immediate_copies(block, n, lrg, location + 1, last_inst);
 877 
 878           if (liveout.remove(lid)) {
 879             lower_pressure(block, location, lrg, &liveout, int_pressure, float_pressure);
 880           }
 881           uint copy_idx = n->is_Copy();
 882           if (copy_idx) {
 883             uint lid_copy = _lrg_map.live_range_id(n->in(copy_idx));
 884             remove_interference_from_copy(block, location, lid_copy, &liveout, cost, int_pressure, float_pressure);
 885           }
 886         }
 887 
 888         // Since rematerializable DEFs are not bound but the live range is,
 889         // some uses must be bound. If we spill live range 'r', it can
 890         // rematerialize at each use site according to its bindings.
 891         if (lrg.is_bound() && !n->rematerialize() && lrg.mask().is_NotEmpty()) {
 892           remove_bound_register_from_interfering_live_ranges(lrg, &liveout, must_spill);
 893         }
 894         interfere_with_live(lid, &liveout);
 895       }
 896 
 897       // Area remaining in the block
 898       inst_count--;
 899       cost = (inst_count <= 0) ? 0.0 : block->_freq * double(inst_count);
 900 
 901       if (!n->is_Phi()) {
 902         add_input_to_liveout(block, n, &liveout, cost, int_pressure, float_pressure);
 903       }
 904     }
 905 
 906     check_for_high_pressure_block(int_pressure);
 907     check_for_high_pressure_block(float_pressure);
 908     adjust_high_pressure_index(block, block->_ihrp_index, int_pressure);
 909     adjust_high_pressure_index(block, block->_fhrp_index, float_pressure);
 910     // set the final_pressure as the register pressure for the block
 911     block->_reg_pressure = int_pressure.final_pressure();
 912     block->_freg_pressure = float_pressure.final_pressure();
 913 
 914 #ifndef PRODUCT
 915     // Gather Register Pressure Statistics
 916     if (PrintOptoStatistics) {
 917       if (block->_reg_pressure > int_pressure.high_pressure_limit() || block->_freg_pressure > float_pressure.high_pressure_limit()) {
 918         _high_pressure++;
 919       } else {
 920         _low_pressure++;
 921       }
 922     }
 923 #endif
 924   }
 925 
 926   return must_spill;
 927 }
--- EOF ---