1 /*

     2  * Copyright (c) 1997, 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 "libadt/vectset.hpp"

    27 #include "memory/allocation.inline.hpp"

    28 #include "memory/resourceArea.hpp"

    29 #include "compiler/compilerDirectives.hpp"

    30 #include "opto/block.hpp"

    31 #include "opto/cfgnode.hpp"

    32 #include "opto/chaitin.hpp"

    33 #include "opto/loopnode.hpp"

    34 #include "opto/machnode.hpp"

    35 #include "opto/matcher.hpp"

    36 #include "opto/opcodes.hpp"

    37 #include "opto/rootnode.hpp"

    38 #include "utilities/copy.hpp"

    39 

    40 void Block_Array::grow( uint i ) {

    41   assert(i >= Max(), "must be an overflow");

    42   debug_only(_limit = i+1);

    43   if( i < _size )  return;

    44   if( !_size ) {

    45     _size = 1;

    46     _blocks = (Block**)_arena->Amalloc( _size * sizeof(Block*) );

    47     _blocks[0] = NULL;

    48   }

    49   uint old = _size;

    50   while( i >= _size ) _size <<= 1;      // Double to fit

    51   _blocks = (Block**)_arena->Arealloc( _blocks, old*sizeof(Block*),_size*sizeof(Block*));

    52   Copy::zero_to_bytes( &_blocks[old], (_size-old)*sizeof(Block*) );

    53 }

    54 

    55 void Block_List::remove(uint i) {

    56   assert(i < _cnt, "index out of bounds");

    57   Copy::conjoint_words_to_lower((HeapWord*)&_blocks[i+1], (HeapWord*)&_blocks[i], ((_cnt-i-1)*sizeof(Block*)));

    58   pop(); // shrink list by one block

    59 }

    60 

    61 void Block_List::insert(uint i, Block *b) {

    62   push(b); // grow list by one block

    63   Copy::conjoint_words_to_higher((HeapWord*)&_blocks[i], (HeapWord*)&_blocks[i+1], ((_cnt-i-1)*sizeof(Block*)));

    64   _blocks[i] = b;

    65 }

    66 

    67 #ifndef PRODUCT

    68 void Block_List::print() {

    69   for (uint i=0; i < size(); i++) {

    70     tty->print("B%d ", _blocks[i]->_pre_order);

    71   }

    72   tty->print("size = %d\n", size());

    73 }

    74 #endif

    75 

    76 uint Block::code_alignment() const {

    77   // Check for Root block

    78   if (_pre_order == 0) return CodeEntryAlignment;

    79   // Check for Start block

    80   if (_pre_order == 1) return InteriorEntryAlignment;

    81   // Check for loop alignment

    82   if (has_loop_alignment()) return loop_alignment();

    83 

    84   return relocInfo::addr_unit(); // no particular alignment

    85 }

    86 

    87 uint Block::compute_loop_alignment() {

    88   Node *h = head();

    89   int unit_sz = relocInfo::addr_unit();

    90   if (h->is_Loop() && h->as_Loop()->is_inner_loop())  {

    91     // Pre- and post-loops have low trip count so do not bother with

    92     // NOPs for align loop head.  The constants are hidden from tuning

    93     // but only because my "divide by 4" heuristic surely gets nearly

    94     // all possible gain (a "do not align at all" heuristic has a

    95     // chance of getting a really tiny gain).

    96     if (h->is_CountedLoop() && (h->as_CountedLoop()->is_pre_loop() ||

    97                                 h->as_CountedLoop()->is_post_loop())) {

    98       return (OptoLoopAlignment > 4*unit_sz) ? (OptoLoopAlignment>>2) : unit_sz;

    99     }

   100     // Loops with low backedge frequency should not be aligned.

   101     Node *n = h->in(LoopNode::LoopBackControl)->in(0);

   102     if (n->is_MachIf() && n->as_MachIf()->_prob < 0.01) {

   103       return unit_sz; // Loop does not loop, more often than not!

   104     }

   105     return OptoLoopAlignment; // Otherwise align loop head

   106   }

   107 

   108   return unit_sz; // no particular alignment

   109 }

   110 

   111 // Compute the size of first 'inst_cnt' instructions in this block.

   112 // Return the number of instructions left to compute if the block has

   113 // less then 'inst_cnt' instructions. Stop, and return 0 if sum_size

   114 // exceeds OptoLoopAlignment.

   115 uint Block::compute_first_inst_size(uint& sum_size, uint inst_cnt,

   116                                     PhaseRegAlloc* ra) {

   117   uint last_inst = number_of_nodes();

   118   for( uint j = 0; j < last_inst && inst_cnt > 0; j++ ) {

   119     uint inst_size = get_node(j)->size(ra);

   120     if( inst_size > 0 ) {

   121       inst_cnt--;

   122       uint sz = sum_size + inst_size;

   123       if( sz <= (uint)OptoLoopAlignment ) {

   124         // Compute size of instructions which fit into fetch buffer only

   125         // since all inst_cnt instructions will not fit even if we align them.

   126         sum_size = sz;

   127       } else {

   128         return 0;

   129       }

   130     }

   131   }

   132   return inst_cnt;

   133 }

   134 

   135 uint Block::find_node( const Node *n ) const {

   136   for( uint i = 0; i < number_of_nodes(); i++ ) {

   137     if( get_node(i) == n )

   138       return i;

   139   }

   140   ShouldNotReachHere();

   141   return 0;

   142 }

   143 

   144 // Find and remove n from block list

   145 void Block::find_remove( const Node *n ) {

   146   remove_node(find_node(n));

   147 }

   148 

   149 bool Block::contains(const Node *n) const {

   150   return _nodes.contains(n);

   151 }

   152 

   153 // Return empty status of a block.  Empty blocks contain only the head, other

   154 // ideal nodes, and an optional trailing goto.

   155 int Block::is_Empty() const {

   156 

   157   // Root or start block is not considered empty

   158   if (head()->is_Root() || head()->is_Start()) {

   159     return not_empty;

   160   }

   161 

   162   int success_result = completely_empty;

   163   int end_idx = number_of_nodes() - 1;

   164 

   165   // Check for ending goto

   166   if ((end_idx > 0) && (get_node(end_idx)->is_MachGoto())) {

   167     success_result = empty_with_goto;

   168     end_idx--;

   169   }

   170 

   171   // Unreachable blocks are considered empty

   172   if (num_preds() <= 1) {

   173     return success_result;

   174   }

   175 

   176   // Ideal nodes are allowable in empty blocks: skip them  Only MachNodes

   177   // turn directly into code, because only MachNodes have non-trivial

   178   // emit() functions.

   179   while ((end_idx > 0) && !get_node(end_idx)->is_Mach()) {

   180     end_idx--;

   181   }

   182 

   183   // No room for any interesting instructions?

   184   if (end_idx == 0) {

   185     return success_result;

   186   }

   187 

   188   return not_empty;

   189 }

   190 

   191 // Return true if the block's code implies that it is likely to be

   192 // executed infrequently.  Check to see if the block ends in a Halt or

   193 // a low probability call.

   194 bool Block::has_uncommon_code() const {

   195   Node* en = end();

   196 

   197   if (en->is_MachGoto())

   198     en = en->in(0);

   199   if (en->is_Catch())

   200     en = en->in(0);

   201   if (en->is_MachProj() && en->in(0)->is_MachCall()) {

   202     MachCallNode* call = en->in(0)->as_MachCall();

   203     if (call->cnt() != COUNT_UNKNOWN && call->cnt() <= PROB_UNLIKELY_MAG(4)) {

   204       // This is true for slow-path stubs like new_{instance,array},

   205       // slow_arraycopy, complete_monitor_locking, uncommon_trap.

   206       // The magic number corresponds to the probability of an uncommon_trap,

   207       // even though it is a count not a probability.

   208       return true;

   209     }

   210   }

   211 

   212   int op = en->is_Mach() ? en->as_Mach()->ideal_Opcode() : en->Opcode();

   213   return op == Op_Halt;

   214 }

   215 

   216 // True if block is low enough frequency or guarded by a test which

   217 // mostly does not go here.

   218 bool PhaseCFG::is_uncommon(const Block* block) {

   219   // Initial blocks must never be moved, so are never uncommon.

   220   if (block->head()->is_Root() || block->head()->is_Start())  return false;

   221 

   222   // Check for way-low freq

   223   if(block->_freq < BLOCK_FREQUENCY(0.00001f) ) return true;

   224 

   225   // Look for code shape indicating uncommon_trap or slow path

   226   if (block->has_uncommon_code()) return true;

   227 

   228   const float epsilon = 0.05f;

   229   const float guard_factor = PROB_UNLIKELY_MAG(4) / (1.f - epsilon);

   230   uint uncommon_preds = 0;

   231   uint freq_preds = 0;

   232   uint uncommon_for_freq_preds = 0;

   233 

   234   for( uint i=1; i< block->num_preds(); i++ ) {

   235     Block* guard = get_block_for_node(block->pred(i));

   236     // Check to see if this block follows its guard 1 time out of 10000

   237     // or less.

   238     //

   239     // See list of magnitude-4 unlikely probabilities in cfgnode.hpp which

   240     // we intend to be "uncommon", such as slow-path TLE allocation,

   241     // predicted call failure, and uncommon trap triggers.

   242     //

   243     // Use an epsilon value of 5% to allow for variability in frequency

   244     // predictions and floating point calculations. The net effect is

   245     // that guard_factor is set to 9500.

   246     //

   247     // Ignore low-frequency blocks.

   248     // The next check is (guard->_freq < 1.e-5 * 9500.).

   249     if(guard->_freq*BLOCK_FREQUENCY(guard_factor) < BLOCK_FREQUENCY(0.00001f)) {

   250       uncommon_preds++;

   251     } else {

   252       freq_preds++;

   253       if(block->_freq < guard->_freq * guard_factor ) {

   254         uncommon_for_freq_preds++;

   255       }

   256     }

   257   }

   258   if( block->num_preds() > 1 &&

   259       // The block is uncommon if all preds are uncommon or

   260       (uncommon_preds == (block->num_preds()-1) ||

   261       // it is uncommon for all frequent preds.

   262        uncommon_for_freq_preds == freq_preds) ) {

   263     return true;

   264   }

   265   return false;

   266 }

   267 

   268 #ifndef PRODUCT

   269 void Block::dump_bidx(const Block* orig, outputStream* st) const {

   270   if (_pre_order) st->print("B%d",_pre_order);

   271   else st->print("N%d", head()->_idx);

   272 

   273   if (Verbose && orig != this) {

   274     // Dump the original block's idx

   275     st->print(" (");

   276     orig->dump_bidx(orig, st);

   277     st->print(")");

   278   }

   279 }

   280 

   281 void Block::dump_pred(const PhaseCFG* cfg, Block* orig, outputStream* st) const {

   282   if (is_connector()) {

   283     for (uint i=1; i<num_preds(); i++) {

   284       Block *p = cfg->get_block_for_node(pred(i));

   285       p->dump_pred(cfg, orig, st);

   286     }

   287   } else {

   288     dump_bidx(orig, st);

   289     st->print(" ");

   290   }

   291 }

   292 

   293 void Block::dump_head(const PhaseCFG* cfg, outputStream* st) const {

   294   // Print the basic block

   295   dump_bidx(this, st);

   296   st->print(": #\t");

   297 

   298   // Print the incoming CFG edges and the outgoing CFG edges

   299   for( uint i=0; i<_num_succs; i++ ) {

   300     non_connector_successor(i)->dump_bidx(_succs[i], st);

   301     st->print(" ");

   302   }

   303   st->print("<- ");

   304   if( head()->is_block_start() ) {

   305     for (uint i=1; i<num_preds(); i++) {

   306       Node *s = pred(i);

   307       if (cfg != NULL) {

   308         Block *p = cfg->get_block_for_node(s);

   309         p->dump_pred(cfg, p, st);

   310       } else {

   311         while (!s->is_block_start())

   312           s = s->in(0);

   313         st->print("N%d ", s->_idx );

   314       }

   315     }

   316   } else {

   317     st->print("BLOCK HEAD IS JUNK  ");

   318   }

   319 

   320   // Print loop, if any

   321   const Block *bhead = this;    // Head of self-loop

   322   Node *bh = bhead->head();

   323 

   324   if ((cfg != NULL) && bh->is_Loop() && !head()->is_Root()) {

   325     LoopNode *loop = bh->as_Loop();

   326     const Block *bx = cfg->get_block_for_node(loop->in(LoopNode::LoopBackControl));

   327     while (bx->is_connector()) {

   328       bx = cfg->get_block_for_node(bx->pred(1));

   329     }

   330     st->print("\tLoop: B%d-B%d ", bhead->_pre_order, bx->_pre_order);

   331     // Dump any loop-specific bits, especially for CountedLoops.

   332     loop->dump_spec(st);

   333   } else if (has_loop_alignment()) {

   334     st->print(" top-of-loop");

   335   }

   336   st->print(" Freq: %g",_freq);

   337   if( Verbose || WizardMode ) {

   338     st->print(" IDom: %d/#%d", _idom ? _idom->_pre_order : 0, _dom_depth);

   339     st->print(" RegPressure: %d",_reg_pressure);

   340     st->print(" IHRP Index: %d",_ihrp_index);

   341     st->print(" FRegPressure: %d",_freg_pressure);

   342     st->print(" FHRP Index: %d",_fhrp_index);

   343   }

   344   st->cr();

   345 }

   346 

   347 void Block::dump() const {

   348   dump(NULL);

   349 }

   350 

   351 void Block::dump(const PhaseCFG* cfg) const {

   352   dump_head(cfg);

   353   for (uint i=0; i< number_of_nodes(); i++) {

   354     get_node(i)->dump();

   355   }

   356   tty->print("\n");

   357 }

   358 #endif

   359 

   360 PhaseCFG::PhaseCFG(Arena* arena, RootNode* root, Matcher& matcher)

   361 : Phase(CFG)

   362 , _block_arena(arena)

   363 , _regalloc(NULL)

   364 , _scheduling_for_pressure(false)

   365 , _root(root)

   366 , _matcher(matcher)

   367 , _node_to_block_mapping(arena)

   368 , _node_latency(NULL)

   369 #ifndef PRODUCT

   370 , _trace_opto_pipelining(C->directive()->TraceOptoPipeliningOption)

   371 #endif

   372 #ifdef ASSERT

   373 , _raw_oops(arena)

   374 #endif

   375 {

   376   ResourceMark rm;

   377   // I'll need a few machine-specific GotoNodes.  Make an Ideal GotoNode,

   378   // then Match it into a machine-specific Node.  Then clone the machine

   379   // Node on demand.

   380   Node *x = new GotoNode(NULL);

   381   x->init_req(0, x);

   382   _goto = matcher.match_tree(x);

   383   assert(_goto != NULL, "");

   384   _goto->set_req(0,_goto);

   385 

   386   // Build the CFG in Reverse Post Order

   387   _number_of_blocks = build_cfg();

   388   _root_block = get_block_for_node(_root);

   389 }

   390 

   391 // Build a proper looking CFG.  Make every block begin with either a StartNode

   392 // or a RegionNode.  Make every block end with either a Goto, If or Return.

   393 // The RootNode both starts and ends it's own block.  Do this with a recursive

   394 // backwards walk over the control edges.

   395 uint PhaseCFG::build_cfg() {

   396   Arena *a = Thread::current()->resource_area();

   397   VectorSet visited(a);

   398 

   399   // Allocate stack with enough space to avoid frequent realloc

   400   Node_Stack nstack(a, C->live_nodes() >> 1);

   401   nstack.push(_root, 0);

   402   uint sum = 0;                 // Counter for blocks

   403 

   404   while (nstack.is_nonempty()) {

   405     // node and in's index from stack's top

   406     // 'np' is _root (see above) or RegionNode, StartNode: we push on stack

   407     // only nodes which point to the start of basic block (see below).

   408     Node *np = nstack.node();

   409     // idx > 0, except for the first node (_root) pushed on stack

   410     // at the beginning when idx == 0.

   411     // We will use the condition (idx == 0) later to end the build.

   412     uint idx = nstack.index();

   413     Node *proj = np->in(idx);

   414     const Node *x = proj->is_block_proj();

   415     // Does the block end with a proper block-ending Node?  One of Return,

   416     // If or Goto? (This check should be done for visited nodes also).

   417     if (x == NULL) {                    // Does not end right...

   418       Node *g = _goto->clone(); // Force it to end in a Goto

   419       g->set_req(0, proj);

   420       np->set_req(idx, g);

   421       x = proj = g;

   422     }

   423     if (!visited.test_set(x->_idx)) { // Visit this block once

   424       // Skip any control-pinned middle'in stuff

   425       Node *p = proj;

   426       do {

   427         proj = p;                   // Update pointer to last Control

   428         p = p->in(0);               // Move control forward

   429       } while( !p->is_block_proj() &&

   430                !p->is_block_start() );

   431       // Make the block begin with one of Region or StartNode.

   432       if( !p->is_block_start() ) {

   433         RegionNode *r = new RegionNode( 2 );

   434         r->init_req(1, p);         // Insert RegionNode in the way

   435         proj->set_req(0, r);        // Insert RegionNode in the way

   436         p = r;

   437       }

   438       // 'p' now points to the start of this basic block

   439 

   440       // Put self in array of basic blocks

   441       Block *bb = new (_block_arena) Block(_block_arena, p);

   442       map_node_to_block(p, bb);

   443       map_node_to_block(x, bb);

   444       if( x != p ) {                // Only for root is x == p

   445         bb->push_node((Node*)x);

   446       }

   447       // Now handle predecessors

   448       ++sum;                        // Count 1 for self block

   449       uint cnt = bb->num_preds();

   450       for (int i = (cnt - 1); i > 0; i-- ) { // For all predecessors

   451         Node *prevproj = p->in(i);  // Get prior input

   452         assert( !prevproj->is_Con(), "dead input not removed" );

   453         // Check to see if p->in(i) is a "control-dependent" CFG edge -

   454         // i.e., it splits at the source (via an IF or SWITCH) and merges

   455         // at the destination (via a many-input Region).

   456         // This breaks critical edges.  The RegionNode to start the block

   457         // will be added when <p,i> is pulled off the node stack

   458         if ( cnt > 2 ) {             // Merging many things?

   459           assert( prevproj== bb->pred(i),"");

   460           if(prevproj->is_block_proj() != prevproj) { // Control-dependent edge?

   461             // Force a block on the control-dependent edge

   462             Node *g = _goto->clone();       // Force it to end in a Goto

   463             g->set_req(0,prevproj);

   464             p->set_req(i,g);

   465           }

   466         }

   467         nstack.push(p, i);  // 'p' is RegionNode or StartNode

   468       }

   469     } else { // Post-processing visited nodes

   470       nstack.pop();                 // remove node from stack

   471       // Check if it the fist node pushed on stack at the beginning.

   472       if (idx == 0) break;          // end of the build

   473       // Find predecessor basic block

   474       Block *pb = get_block_for_node(x);

   475       // Insert into nodes array, if not already there

   476       if (!has_block(proj)) {

   477         assert( x != proj, "" );

   478         // Map basic block of projection

   479         map_node_to_block(proj, pb);

   480         pb->push_node(proj);

   481       }

   482       // Insert self as a child of my predecessor block

   483       pb->_succs.map(pb->_num_succs++, get_block_for_node(np));

   484       assert( pb->get_node(pb->number_of_nodes() - pb->_num_succs)->is_block_proj(),

   485               "too many control users, not a CFG?" );

   486     }

   487   }

   488   // Return number of basic blocks for all children and self

   489   return sum;

   490 }

   491 

   492 // Inserts a goto & corresponding basic block between

   493 // block[block_no] and its succ_no'th successor block

   494 void PhaseCFG::insert_goto_at(uint block_no, uint succ_no) {

   495   // get block with block_no

   496   assert(block_no < number_of_blocks(), "illegal block number");

   497   Block* in  = get_block(block_no);

   498   // get successor block succ_no

   499   assert(succ_no < in->_num_succs, "illegal successor number");

   500   Block* out = in->_succs[succ_no];

   501   // Compute frequency of the new block. Do this before inserting

   502   // new block in case succ_prob() needs to infer the probability from

   503   // surrounding blocks.

   504   float freq = in->_freq * in->succ_prob(succ_no);

   505   // get ProjNode corresponding to the succ_no'th successor of the in block

   506   ProjNode* proj = in->get_node(in->number_of_nodes() - in->_num_succs + succ_no)->as_Proj();

   507   // create region for basic block

   508   RegionNode* region = new RegionNode(2);

   509   region->init_req(1, proj);

   510   // setup corresponding basic block

   511   Block* block = new (_block_arena) Block(_block_arena, region);

   512   map_node_to_block(region, block);

   513   C->regalloc()->set_bad(region->_idx);

   514   // add a goto node

   515   Node* gto = _goto->clone(); // get a new goto node

   516   gto->set_req(0, region);

   517   // add it to the basic block

   518   block->push_node(gto);

   519   map_node_to_block(gto, block);

   520   C->regalloc()->set_bad(gto->_idx);

   521   // hook up successor block

   522   block->_succs.map(block->_num_succs++, out);

   523   // remap successor's predecessors if necessary

   524   for (uint i = 1; i < out->num_preds(); i++) {

   525     if (out->pred(i) == proj) out->head()->set_req(i, gto);

   526   }

   527   // remap predecessor's successor to new block

   528   in->_succs.map(succ_no, block);

   529   // Set the frequency of the new block

   530   block->_freq = freq;

   531   // add new basic block to basic block list

   532   add_block_at(block_no + 1, block);

   533 }

   534 

   535 // Does this block end in a multiway branch that cannot have the default case

   536 // flipped for another case?

   537 static bool no_flip_branch(Block *b) {

   538   int branch_idx = b->number_of_nodes() - b->_num_succs-1;

   539   if (branch_idx < 1) {

   540     return false;

   541   }

   542   Node *branch = b->get_node(branch_idx);

   543   if (branch->is_Catch()) {

   544     return true;

   545   }

   546   if (branch->is_Mach()) {

   547     if (branch->is_MachNullCheck()) {

   548       return true;

   549     }

   550     int iop = branch->as_Mach()->ideal_Opcode();

   551     if (iop == Op_FastLock || iop == Op_FastUnlock) {

   552       return true;

   553     }

   554     // Don't flip if branch has an implicit check.

   555     if (branch->as_Mach()->is_TrapBasedCheckNode()) {

   556       return true;

   557     }

   558   }

   559   return false;

   560 }

   561 

   562 // Check for NeverBranch at block end.  This needs to become a GOTO to the

   563 // true target.  NeverBranch are treated as a conditional branch that always

   564 // goes the same direction for most of the optimizer and are used to give a

   565 // fake exit path to infinite loops.  At this late stage they need to turn

   566 // into Goto's so that when you enter the infinite loop you indeed hang.

   567 void PhaseCFG::convert_NeverBranch_to_Goto(Block *b) {

   568   // Find true target

   569   int end_idx = b->end_idx();

   570   int idx = b->get_node(end_idx+1)->as_Proj()->_con;

   571   Block *succ = b->_succs[idx];

   572   Node* gto = _goto->clone(); // get a new goto node

   573   gto->set_req(0, b->head());

   574   Node *bp = b->get_node(end_idx);

   575   b->map_node(gto, end_idx); // Slam over NeverBranch

   576   map_node_to_block(gto, b);

   577   C->regalloc()->set_bad(gto->_idx);

   578   b->pop_node();              // Yank projections

   579   b->pop_node();              // Yank projections

   580   b->_succs.map(0,succ);        // Map only successor

   581   b->_num_succs = 1;

   582   // remap successor's predecessors if necessary

   583   uint j;

   584   for( j = 1; j < succ->num_preds(); j++)

   585     if( succ->pred(j)->in(0) == bp )

   586       succ->head()->set_req(j, gto);

   587   // Kill alternate exit path

   588   Block *dead = b->_succs[1-idx];

   589   for( j = 1; j < dead->num_preds(); j++)

   590     if( dead->pred(j)->in(0) == bp )

   591       break;

   592   // Scan through block, yanking dead path from

   593   // all regions and phis.

   594   dead->head()->del_req(j);

   595   for( int k = 1; dead->get_node(k)->is_Phi(); k++ )

   596     dead->get_node(k)->del_req(j);

   597 }

   598 

   599 // Helper function to move block bx to the slot following b_index. Return

   600 // true if the move is successful, otherwise false

   601 bool PhaseCFG::move_to_next(Block* bx, uint b_index) {

   602   if (bx == NULL) return false;

   603 

   604   // Return false if bx is already scheduled.

   605   uint bx_index = bx->_pre_order;

   606   if ((bx_index <= b_index) && (get_block(bx_index) == bx)) {

   607     return false;

   608   }

   609 

   610   // Find the current index of block bx on the block list

   611   bx_index = b_index + 1;

   612   while (bx_index < number_of_blocks() && get_block(bx_index) != bx) {

   613     bx_index++;

   614   }

   615   assert(get_block(bx_index) == bx, "block not found");

   616 

   617   // If the previous block conditionally falls into bx, return false,

   618   // because moving bx will create an extra jump.

   619   for(uint k = 1; k < bx->num_preds(); k++ ) {

   620     Block* pred = get_block_for_node(bx->pred(k));

   621     if (pred == get_block(bx_index - 1)) {

   622       if (pred->_num_succs != 1) {

   623         return false;

   624       }

   625     }

   626   }

   627 

   628   // Reinsert bx just past block 'b'

   629   _blocks.remove(bx_index);

   630   _blocks.insert(b_index + 1, bx);

   631   return true;

   632 }

   633 

   634 // Move empty and uncommon blocks to the end.

   635 void PhaseCFG::move_to_end(Block *b, uint i) {

   636   int e = b->is_Empty();

   637   if (e != Block::not_empty) {

   638     if (e == Block::empty_with_goto) {

   639       // Remove the goto, but leave the block.

   640       b->pop_node();

   641     }

   642     // Mark this block as a connector block, which will cause it to be

   643     // ignored in certain functions such as non_connector_successor().

   644     b->set_connector();

   645   }

   646   // Move the empty block to the end, and don't recheck.

   647   _blocks.remove(i);

   648   _blocks.push(b);

   649 }

   650 

   651 // Set loop alignment for every block

   652 void PhaseCFG::set_loop_alignment() {

   653   uint last = number_of_blocks();

   654   assert(get_block(0) == get_root_block(), "");

   655 

   656   for (uint i = 1; i < last; i++) {

   657     Block* block = get_block(i);

   658     if (block->head()->is_Loop()) {

   659       block->set_loop_alignment(block);

   660     }

   661   }

   662 }

   663 

   664 // Make empty basic blocks to be "connector" blocks, Move uncommon blocks

   665 // to the end.

   666 void PhaseCFG::remove_empty_blocks() {

   667   // Move uncommon blocks to the end

   668   uint last = number_of_blocks();

   669   assert(get_block(0) == get_root_block(), "");

   670 

   671   for (uint i = 1; i < last; i++) {

   672     Block* block = get_block(i);

   673     if (block->is_connector()) {

   674       break;

   675     }

   676 

   677     // Check for NeverBranch at block end.  This needs to become a GOTO to the

   678     // true target.  NeverBranch are treated as a conditional branch that

   679     // always goes the same direction for most of the optimizer and are used

   680     // to give a fake exit path to infinite loops.  At this late stage they

   681     // need to turn into Goto's so that when you enter the infinite loop you

   682     // indeed hang.

   683     if (block->get_node(block->end_idx())->Opcode() == Op_NeverBranch) {

   684       convert_NeverBranch_to_Goto(block);

   685     }

   686 

   687     // Look for uncommon blocks and move to end.

   688     if (!C->do_freq_based_layout()) {

   689       if (is_uncommon(block)) {

   690         move_to_end(block, i);

   691         last--;                   // No longer check for being uncommon!

   692         if (no_flip_branch(block)) { // Fall-thru case must follow?

   693           // Find the fall-thru block

   694           block = get_block(i);

   695           move_to_end(block, i);

   696           last--;

   697         }

   698         // backup block counter post-increment

   699         i--;

   700       }

   701     }

   702   }

   703 

   704   // Move empty blocks to the end

   705   last = number_of_blocks();

   706   for (uint i = 1; i < last; i++) {

   707     Block* block = get_block(i);

   708     if (block->is_Empty() != Block::not_empty) {

   709       move_to_end(block, i);

   710       last--;

   711       i--;

   712     }

   713   } // End of for all blocks

   714 }

   715 

   716 Block *PhaseCFG::fixup_trap_based_check(Node *branch, Block *block, int block_pos, Block *bnext) {

   717   // Trap based checks must fall through to the successor with

   718   // PROB_ALWAYS.

   719   // They should be an If with 2 successors.

   720   assert(branch->is_MachIf(),   "must be If");

   721   assert(block->_num_succs == 2, "must have 2 successors");

   722 

   723   // Get the If node and the projection for the first successor.

   724   MachIfNode *iff   = block->get_node(block->number_of_nodes()-3)->as_MachIf();

   725   ProjNode   *proj0 = block->get_node(block->number_of_nodes()-2)->as_Proj();

   726   ProjNode   *proj1 = block->get_node(block->number_of_nodes()-1)->as_Proj();

   727   ProjNode   *projt = (proj0->Opcode() == Op_IfTrue)  ? proj0 : proj1;

   728   ProjNode   *projf = (proj0->Opcode() == Op_IfFalse) ? proj0 : proj1;

   729 

   730   // Assert that proj0 and succs[0] match up. Similarly for proj1 and succs[1].

   731   assert(proj0->raw_out(0) == block->_succs[0]->head(), "Mismatch successor 0");

   732   assert(proj1->raw_out(0) == block->_succs[1]->head(), "Mismatch successor 1");

   733 

   734   ProjNode *proj_always;

   735   ProjNode *proj_never;

   736   // We must negate the branch if the implicit check doesn't follow

   737   // the branch's TRUE path. Then, the new TRUE branch target will

   738   // be the old FALSE branch target.

   739   if (iff->_prob <= 2*PROB_NEVER) {   // There are small rounding errors.

   740     proj_never  = projt;

   741     proj_always = projf;

   742   } else {

   743     // We must negate the branch if the trap doesn't follow the

   744     // branch's TRUE path. Then, the new TRUE branch target will

   745     // be the old FALSE branch target.

   746     proj_never  = projf;

   747     proj_always = projt;

   748     iff->negate();

   749   }

   750   assert(iff->_prob <= 2*PROB_NEVER, "Trap based checks are expected to trap never!");

   751   // Map the successors properly

   752   block->_succs.map(0, get_block_for_node(proj_never ->raw_out(0)));   // The target of the trap.

   753   block->_succs.map(1, get_block_for_node(proj_always->raw_out(0)));   // The fall through target.

   754 

   755   if (block->get_node(block->number_of_nodes() - block->_num_succs + 1) != proj_always) {

   756     block->map_node(proj_never,  block->number_of_nodes() - block->_num_succs + 0);

   757     block->map_node(proj_always, block->number_of_nodes() - block->_num_succs + 1);

   758   }

   759 

   760   // Place the fall through block after this block.

   761   Block *bs1 = block->non_connector_successor(1);

   762   if (bs1 != bnext && move_to_next(bs1, block_pos)) {

   763     bnext = bs1;

   764   }

   765   // If the fall through block still is not the next block, insert a goto.

   766   if (bs1 != bnext) {

   767     insert_goto_at(block_pos, 1);

   768   }

   769   return bnext;

   770 }

   771 

   772 // Fix up the final control flow for basic blocks.

   773 void PhaseCFG::fixup_flow() {

   774   // Fixup final control flow for the blocks.  Remove jump-to-next

   775   // block. If neither arm of an IF follows the conditional branch, we

   776   // have to add a second jump after the conditional.  We place the

   777   // TRUE branch target in succs[0] for both GOTOs and IFs.

   778   for (uint i = 0; i < number_of_blocks(); i++) {

   779     Block* block = get_block(i);

   780     block->_pre_order = i;          // turn pre-order into block-index

   781 

   782     // Connector blocks need no further processing.

   783     if (block->is_connector()) {

   784       assert((i+1) == number_of_blocks() || get_block(i + 1)->is_connector(), "All connector blocks should sink to the end");

   785       continue;

   786     }

   787     assert(block->is_Empty() != Block::completely_empty, "Empty blocks should be connectors");

   788 

   789     Block* bnext = (i < number_of_blocks() - 1) ? get_block(i + 1) : NULL;

   790     Block* bs0 = block->non_connector_successor(0);

   791 

   792     // Check for multi-way branches where I cannot negate the test to

   793     // exchange the true and false targets.

   794     if (no_flip_branch(block)) {

   795       // Find fall through case - if must fall into its target.

   796       // Get the index of the branch's first successor.

   797       int branch_idx = block->number_of_nodes() - block->_num_succs;

   798 

   799       // The branch is 1 before the branch's first successor.

   800       Node *branch = block->get_node(branch_idx-1);

   801 

   802       // Handle no-flip branches which have implicit checks and which require

   803       // special block ordering and individual semantics of the 'fall through

   804       // case'.

   805       if ((TrapBasedNullChecks || TrapBasedRangeChecks) &&

   806           branch->is_Mach() && branch->as_Mach()->is_TrapBasedCheckNode()) {

   807         bnext = fixup_trap_based_check(branch, block, i, bnext);

   808       } else {

   809         // Else, default handling for no-flip branches

   810         for (uint j2 = 0; j2 < block->_num_succs; j2++) {

   811           const ProjNode* p = block->get_node(branch_idx + j2)->as_Proj();

   812           if (p->_con == 0) {

   813             // successor j2 is fall through case

   814             if (block->non_connector_successor(j2) != bnext) {

   815               // but it is not the next block => insert a goto

   816               insert_goto_at(i, j2);

   817             }

   818             // Put taken branch in slot 0

   819             if (j2 == 0 && block->_num_succs == 2) {

   820               // Flip targets in succs map

   821               Block *tbs0 = block->_succs[0];

   822               Block *tbs1 = block->_succs[1];

   823               block->_succs.map(0, tbs1);

   824               block->_succs.map(1, tbs0);

   825             }

   826             break;

   827           }

   828         }

   829       }

   830 

   831       // Remove all CatchProjs

   832       for (uint j = 0; j < block->_num_succs; j++) {

   833         block->pop_node();

   834       }

   835 

   836     } else if (block->_num_succs == 1) {

   837       // Block ends in a Goto?

   838       if (bnext == bs0) {

   839         // We fall into next block; remove the Goto

   840         block->pop_node();

   841       }

   842 

   843     } else if(block->_num_succs == 2) { // Block ends in a If?

   844       // Get opcode of 1st projection (matches _succs[0])

   845       // Note: Since this basic block has 2 exits, the last 2 nodes must

   846       //       be projections (in any order), the 3rd last node must be

   847       //       the IfNode (we have excluded other 2-way exits such as

   848       //       CatchNodes already).

   849       MachNode* iff   = block->get_node(block->number_of_nodes() - 3)->as_Mach();

   850       ProjNode* proj0 = block->get_node(block->number_of_nodes() - 2)->as_Proj();

   851       ProjNode* proj1 = block->get_node(block->number_of_nodes() - 1)->as_Proj();

   852 

   853       // Assert that proj0 and succs[0] match up. Similarly for proj1 and succs[1].

   854       assert(proj0->raw_out(0) == block->_succs[0]->head(), "Mismatch successor 0");

   855       assert(proj1->raw_out(0) == block->_succs[1]->head(), "Mismatch successor 1");

   856 

   857       Block* bs1 = block->non_connector_successor(1);

   858 

   859       // Check for neither successor block following the current

   860       // block ending in a conditional. If so, move one of the

   861       // successors after the current one, provided that the

   862       // successor was previously unscheduled, but moveable

   863       // (i.e., all paths to it involve a branch).

   864       if (!C->do_freq_based_layout() && bnext != bs0 && bnext != bs1) {

   865         // Choose the more common successor based on the probability

   866         // of the conditional branch.

   867         Block* bx = bs0;

   868         Block* by = bs1;

   869 

   870         // _prob is the probability of taking the true path. Make

   871         // p the probability of taking successor #1.

   872         float p = iff->as_MachIf()->_prob;

   873         if (proj0->Opcode() == Op_IfTrue) {

   874           p = 1.0 - p;

   875         }

   876 

   877         // Prefer successor #1 if p > 0.5

   878         if (p > PROB_FAIR) {

   879           bx = bs1;

   880           by = bs0;

   881         }

   882 

   883         // Attempt the more common successor first

   884         if (move_to_next(bx, i)) {

   885           bnext = bx;

   886         } else if (move_to_next(by, i)) {

   887           bnext = by;

   888         }

   889       }

   890 

   891       // Check for conditional branching the wrong way.  Negate

   892       // conditional, if needed, so it falls into the following block

   893       // and branches to the not-following block.

   894 

   895       // Check for the next block being in succs[0].  We are going to branch

   896       // to succs[0], so we want the fall-thru case as the next block in

   897       // succs[1].

   898       if (bnext == bs0) {

   899         // Fall-thru case in succs[0], so flip targets in succs map

   900         Block* tbs0 = block->_succs[0];

   901         Block* tbs1 = block->_succs[1];

   902         block->_succs.map(0, tbs1);

   903         block->_succs.map(1, tbs0);

   904         // Flip projection for each target

   905         ProjNode* tmp = proj0;

   906         proj0 = proj1;

   907         proj1 = tmp;

   908 

   909       } else if(bnext != bs1) {

   910         // Need a double-branch

   911         // The existing conditional branch need not change.

   912         // Add a unconditional branch to the false target.

   913         // Alas, it must appear in its own block and adding a

   914         // block this late in the game is complicated.  Sigh.

   915         insert_goto_at(i, 1);

   916       }

   917 

   918       // Make sure we TRUE branch to the target

   919       if (proj0->Opcode() == Op_IfFalse) {

   920         iff->as_MachIf()->negate();

   921       }

   922 

   923       block->pop_node();          // Remove IfFalse & IfTrue projections

   924       block->pop_node();

   925 

   926     } else {

   927       // Multi-exit block, e.g. a switch statement

   928       // But we don't need to do anything here

   929     }

   930   } // End of for all blocks

   931 }

   932 

   933 

   934 // postalloc_expand: Expand nodes after register allocation.

   935 //

   936 // postalloc_expand has to be called after register allocation, just

   937 // before output (i.e. scheduling). It only gets called if

   938 // Matcher::require_postalloc_expand is true.

   939 //

   940 // Background:

   941 //

   942 // Nodes that are expandend (one compound node requiring several

   943 // assembler instructions to be implemented split into two or more

   944 // non-compound nodes) after register allocation are not as nice as

   945 // the ones expanded before register allocation - they don't

   946 // participate in optimizations as global code motion. But after

   947 // register allocation we can expand nodes that use registers which

   948 // are not spillable or registers that are not allocated, because the

   949 // old compound node is simply replaced (in its location in the basic

   950 // block) by a new subgraph which does not contain compound nodes any

   951 // more. The scheduler called during output can later on process these

   952 // non-compound nodes.

   953 //

   954 // Implementation:

   955 //

   956 // Nodes requiring postalloc expand are specified in the ad file by using

   957 // a postalloc_expand statement instead of ins_encode. A postalloc_expand

   958 // contains a single call to an encoding, as does an ins_encode

   959 // statement. Instead of an emit() function a postalloc_expand() function

   960 // is generated that doesn't emit assembler but creates a new

   961 // subgraph. The code below calls this postalloc_expand function for each

   962 // node with the appropriate attribute. This function returns the new

   963 // nodes generated in an array passed in the call. The old node,

   964 // potential MachTemps before and potential Projs after it then get

   965 // disconnected and replaced by the new nodes. The instruction

   966 // generating the result has to be the last one in the array. In

   967 // general it is assumed that Projs after the node expanded are

   968 // kills. These kills are not required any more after expanding as

   969 // there are now explicitly visible def-use chains and the Projs are

   970 // removed. This does not hold for calls: They do not only have

   971 // kill-Projs but also Projs defining values. Therefore Projs after

   972 // the node expanded are removed for all but for calls. If a node is

   973 // to be reused, it must be added to the nodes list returned, and it

   974 // will be added again.

   975 //

   976 // Implementing the postalloc_expand function for a node in an enc_class

   977 // is rather tedious. It requires knowledge about many node details, as

   978 // the nodes and the subgraph must be hand crafted. To simplify this,

   979 // adlc generates some utility variables into the postalloc_expand function,

   980 // e.g., holding the operands as specified by the postalloc_expand encoding

   981 // specification, e.g.:

   982 //  * unsigned idx_<par_name>  holding the index of the node in the ins

   983 //  * Node *n_<par_name>       holding the node loaded from the ins

   984 //  * MachOpnd *op_<par_name>  holding the corresponding operand

   985 //

   986 // The ordering of operands can not be determined by looking at a

   987 // rule. Especially if a match rule matches several different trees,

   988 // several nodes are generated from one instruct specification with

   989 // different operand orderings. In this case the adlc generated

   990 // variables are the only way to access the ins and operands

   991 // deterministically.

   992 //

   993 // If assigning a register to a node that contains an oop, don't

   994 // forget to call ra_->set_oop() for the node.

   995 void PhaseCFG::postalloc_expand(PhaseRegAlloc* _ra) {

   996   GrowableArray <Node *> new_nodes(32); // Array with new nodes filled by postalloc_expand function of node.

   997   GrowableArray <Node *> remove(32);

   998   GrowableArray <Node *> succs(32);

   999   unsigned int max_idx = C->unique();   // Remember to distinguish new from old nodes.

  1000   DEBUG_ONLY(bool foundNode = false);

  1001 

  1002   // for all blocks

  1003   for (uint i = 0; i < number_of_blocks(); i++) {

  1004     Block *b = _blocks[i];

  1005     // For all instructions in the current block.

  1006     for (uint j = 0; j < b->number_of_nodes(); j++) {

  1007       Node *n = b->get_node(j);

  1008       if (n->is_Mach() && n->as_Mach()->requires_postalloc_expand()) {

  1009 #ifdef ASSERT

  1010         if (TracePostallocExpand) {

  1011           if (!foundNode) {

  1012             foundNode = true;

  1013             tty->print("POSTALLOC EXPANDING %d %s\n", C->compile_id(),

  1014                        C->method() ? C->method()->name()->as_utf8() : C->stub_name());

  1015           }

  1016           tty->print("  postalloc expanding "); n->dump();

  1017           if (Verbose) {

  1018             tty->print("    with ins:\n");

  1019             for (uint k = 0; k < n->len(); ++k) {

  1020               if (n->in(k)) { tty->print("        "); n->in(k)->dump(); }

  1021             }

  1022           }

  1023         }

  1024 #endif

  1025         new_nodes.clear();

  1026         // Collect nodes that have to be removed from the block later on.

  1027         uint req = n->req();

  1028         remove.clear();

  1029         for (uint k = 0; k < req; ++k) {

  1030           if (n->in(k) && n->in(k)->is_MachTemp()) {

  1031             remove.push(n->in(k)); // MachTemps which are inputs to the old node have to be removed.

  1032             n->in(k)->del_req(0);

  1033             j--;

  1034           }

  1035         }

  1036 

  1037         // Check whether we can allocate enough nodes. We set a fix limit for

  1038         // the size of postalloc expands with this.

  1039         uint unique_limit = C->unique() + 40;

  1040         if (unique_limit >= _ra->node_regs_max_index()) {

  1041           Compile::current()->record_failure("out of nodes in postalloc expand");

  1042           return;

  1043         }

  1044 

  1045         // Emit (i.e. generate new nodes).

  1046         n->as_Mach()->postalloc_expand(&new_nodes, _ra);

  1047 

  1048         assert(C->unique() < unique_limit, "You allocated too many nodes in your postalloc expand.");

  1049 

  1050         // Disconnect the inputs of the old node.

  1051         //

  1052         // We reuse MachSpillCopy nodes. If we need to expand them, there

  1053         // are many, so reusing pays off. If reused, the node already

  1054         // has the new ins. n must be the last node on new_nodes list.

  1055         if (!n->is_MachSpillCopy()) {

  1056           for (int k = req - 1; k >= 0; --k) {

  1057             n->del_req(k);

  1058           }

  1059         }

  1060 

  1061 #ifdef ASSERT

  1062         // Check that all nodes have proper operands.

  1063         for (int k = 0; k < new_nodes.length(); ++k) {

  1064           if (new_nodes.at(k)->_idx < max_idx || !new_nodes.at(k)->is_Mach()) continue; // old node, Proj ...

  1065           MachNode *m = new_nodes.at(k)->as_Mach();

  1066           for (unsigned int l = 0; l < m->num_opnds(); ++l) {

  1067             if (MachOper::notAnOper(m->_opnds[l])) {

  1068               outputStream *os = tty;

  1069               os->print("Node %s ", m->Name());

  1070               os->print("has invalid opnd %d: %p\n", l, m->_opnds[l]);

  1071               assert(0, "Invalid operands, see inline trace in hs_err_pid file.");

  1072             }

  1073           }

  1074         }

  1075 #endif

  1076 

  1077         // Collect succs of old node in remove (for projections) and in succs (for

  1078         // all other nodes) do _not_ collect projections in remove (but in succs)

  1079         // in case the node is a call. We need the projections for calls as they are

  1080         // associated with registes (i.e. they are defs).

  1081         succs.clear();

  1082         for (DUIterator k = n->outs(); n->has_out(k); k++) {

  1083           if (n->out(k)->is_Proj() && !n->is_MachCall() && !n->is_MachBranch()) {

  1084             remove.push(n->out(k));

  1085           } else {

  1086             succs.push(n->out(k));

  1087           }

  1088         }

  1089         // Replace old node n as input of its succs by last of the new nodes.

  1090         for (int k = 0; k < succs.length(); ++k) {

  1091           Node *succ = succs.at(k);

  1092           for (uint l = 0; l < succ->req(); ++l) {

  1093             if (succ->in(l) == n) {

  1094               succ->set_req(l, new_nodes.at(new_nodes.length() - 1));

  1095             }

  1096           }

  1097           for (uint l = succ->req(); l < succ->len(); ++l) {

  1098             if (succ->in(l) == n) {

  1099               succ->set_prec(l, new_nodes.at(new_nodes.length() - 1));

  1100             }

  1101           }

  1102         }

  1103 

  1104         // Index of old node in block.

  1105         uint index = b->find_node(n);

  1106         // Insert new nodes into block and map them in nodes->blocks array

  1107         // and remember last node in n2.

  1108         Node *n2 = NULL;

  1109         for (int k = 0; k < new_nodes.length(); ++k) {

  1110           n2 = new_nodes.at(k);

  1111           b->insert_node(n2, ++index);

  1112           map_node_to_block(n2, b);

  1113         }

  1114 

  1115         // Add old node n to remove and remove them all from block.

  1116         remove.push(n);

  1117         j--;

  1118 #ifdef ASSERT

  1119         if (TracePostallocExpand && Verbose) {

  1120           tty->print("    removing:\n");

  1121           for (int k = 0; k < remove.length(); ++k) {

  1122             tty->print("        "); remove.at(k)->dump();

  1123           }

  1124           tty->print("    inserting:\n");

  1125           for (int k = 0; k < new_nodes.length(); ++k) {

  1126             tty->print("        "); new_nodes.at(k)->dump();

  1127           }

  1128         }

  1129 #endif

  1130         for (int k = 0; k < remove.length(); ++k) {

  1131           if (b->contains(remove.at(k))) {

  1132             b->find_remove(remove.at(k));

  1133           } else {

  1134             assert(remove.at(k)->is_Proj() && (remove.at(k)->in(0)->is_MachBranch()), "");