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 #include "precompiled.hpp"
  26 #include "libadt/vectset.hpp"
  27 #include "memory/allocation.inline.hpp"
  28 #include "opto/block.hpp"
  29 #include "opto/c2compiler.hpp"
  30 #include "opto/callnode.hpp"
  31 #include "opto/cfgnode.hpp"
  32 #include "opto/machnode.hpp"
  33 #include "opto/opcodes.hpp"
  34 #include "opto/phaseX.hpp"
  35 #include "opto/rootnode.hpp"
  36 #include "opto/runtime.hpp"
  37 #include "runtime/deoptimization.hpp"
  38 #if defined AD_MD_HPP
  39 # include AD_MD_HPP
  40 #elif defined TARGET_ARCH_MODEL_x86_32
  41 # include "adfiles/ad_x86_32.hpp"
  42 #elif defined TARGET_ARCH_MODEL_x86_64
  43 # include "adfiles/ad_x86_64.hpp"
  44 #elif defined TARGET_ARCH_MODEL_sparc
  45 # include "adfiles/ad_sparc.hpp"
  46 #elif defined TARGET_ARCH_MODEL_zero
  47 # include "adfiles/ad_zero.hpp"
  48 #elif defined TARGET_ARCH_MODEL_ppc_64
  49 # include "adfiles/ad_ppc_64.hpp"
  50 #elif defined TARGET_ARCH_MODEL_aarch32
  51 # include "adfiles/ad_aarch32.hpp"
  52 #endif
  53 
  54 
  55 // Portions of code courtesy of Clifford Click
  56 
  57 // Optimization - Graph Style
  58 
  59 // To avoid float value underflow
  60 #define MIN_BLOCK_FREQUENCY 1.e-35f
  61 
  62 //----------------------------schedule_node_into_block-------------------------
  63 // Insert node n into block b. Look for projections of n and make sure they
  64 // are in b also.
  65 void PhaseCFG::schedule_node_into_block( Node *n, Block *b ) {
  66   // Set basic block of n, Add n to b,
  67   map_node_to_block(n, b);
  68   b->add_inst(n);
  69 
  70   // After Matching, nearly any old Node may have projections trailing it.
  71   // These are usually machine-dependent flags.  In any case, they might
  72   // float to another block below this one.  Move them up.
  73   for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
  74     Node*  use  = n->fast_out(i);
  75     if (use->is_Proj()) {
  76       Block* buse = get_block_for_node(use);
  77       if (buse != b) {              // In wrong block?
  78         if (buse != NULL) {
  79           buse->find_remove(use);   // Remove from wrong block
  80         }
  81         map_node_to_block(use, b);
  82         b->add_inst(use);
  83       }
  84     }
  85   }
  86 }
  87 
  88 //----------------------------replace_block_proj_ctrl-------------------------
  89 // Nodes that have is_block_proj() nodes as their control need to use
  90 // the appropriate Region for their actual block as their control since
  91 // the projection will be in a predecessor block.
  92 void PhaseCFG::replace_block_proj_ctrl( Node *n ) {
  93   const Node *in0 = n->in(0);
  94   assert(in0 != NULL, "Only control-dependent");
  95   const Node *p = in0->is_block_proj();
  96   if (p != NULL && p != n) {    // Control from a block projection?
  97     assert(!n->pinned() || n->is_MachConstantBase(), "only pinned MachConstantBase node is expected here");
  98     // Find trailing Region
  99     Block *pb = get_block_for_node(in0); // Block-projection already has basic block
 100     uint j = 0;
 101     if (pb->_num_succs != 1) {  // More then 1 successor?
 102       // Search for successor
 103       uint max = pb->number_of_nodes();
 104       assert( max > 1, "" );
 105       uint start = max - pb->_num_succs;
 106       // Find which output path belongs to projection
 107       for (j = start; j < max; j++) {
 108         if( pb->get_node(j) == in0 )
 109           break;
 110       }
 111       assert( j < max, "must find" );
 112       // Change control to match head of successor basic block
 113       j -= start;
 114     }
 115     n->set_req(0, pb->_succs[j]->head());
 116   }
 117 }
 118 
 119 
 120 //------------------------------schedule_pinned_nodes--------------------------
 121 // Set the basic block for Nodes pinned into blocks
 122 void PhaseCFG::schedule_pinned_nodes(VectorSet &visited) {
 123   // Allocate node stack of size C->live_nodes()+8 to avoid frequent realloc
 124   GrowableArray <Node *> spstack(C->live_nodes() + 8);
 125   spstack.push(_root);
 126   while (spstack.is_nonempty()) {
 127     Node* node = spstack.pop();
 128     if (!visited.test_set(node->_idx)) { // Test node and flag it as visited
 129       if (node->pinned() && !has_block(node)) {  // Pinned?  Nail it down!
 130         assert(node->in(0), "pinned Node must have Control");
 131         // Before setting block replace block_proj control edge
 132         replace_block_proj_ctrl(node);
 133         Node* input = node->in(0);
 134         while (!input->is_block_start()) {
 135           input = input->in(0);
 136         }
 137         Block* block = get_block_for_node(input); // Basic block of controlling input
 138         schedule_node_into_block(node, block);
 139       }
 140 
 141       // process all inputs that are non NULL
 142       for (int i = node->req() - 1; i >= 0; --i) {
 143         if (node->in(i) != NULL) {
 144           spstack.push(node->in(i));
 145         }
 146       }
 147     }
 148   }
 149 }
 150 
 151 #ifdef ASSERT
 152 // Assert that new input b2 is dominated by all previous inputs.
 153 // Check this by by seeing that it is dominated by b1, the deepest
 154 // input observed until b2.
 155 static void assert_dom(Block* b1, Block* b2, Node* n, const PhaseCFG* cfg) {
 156   if (b1 == NULL)  return;
 157   assert(b1->_dom_depth < b2->_dom_depth, "sanity");
 158   Block* tmp = b2;
 159   while (tmp != b1 && tmp != NULL) {
 160     tmp = tmp->_idom;
 161   }
 162   if (tmp != b1) {
 163     // Detected an unschedulable graph.  Print some nice stuff and die.
 164     tty->print_cr("!!! Unschedulable graph !!!");
 165     for (uint j=0; j<n->len(); j++) { // For all inputs
 166       Node* inn = n->in(j); // Get input
 167       if (inn == NULL)  continue;  // Ignore NULL, missing inputs
 168       Block* inb = cfg->get_block_for_node(inn);
 169       tty->print("B%d idom=B%d depth=%2d ",inb->_pre_order,
 170                  inb->_idom ? inb->_idom->_pre_order : 0, inb->_dom_depth);
 171       inn->dump();
 172     }
 173     tty->print("Failing node: ");
 174     n->dump();
 175     assert(false, "unscheduable graph");
 176   }
 177 }
 178 #endif
 179 
 180 static Block* find_deepest_input(Node* n, const PhaseCFG* cfg) {
 181   // Find the last input dominated by all other inputs.
 182   Block* deepb           = NULL;        // Deepest block so far
 183   int    deepb_dom_depth = 0;
 184   for (uint k = 0; k < n->len(); k++) { // For all inputs
 185     Node* inn = n->in(k);               // Get input
 186     if (inn == NULL)  continue;         // Ignore NULL, missing inputs
 187     Block* inb = cfg->get_block_for_node(inn);
 188     assert(inb != NULL, "must already have scheduled this input");
 189     if (deepb_dom_depth < (int) inb->_dom_depth) {
 190       // The new inb must be dominated by the previous deepb.
 191       // The various inputs must be linearly ordered in the dom
 192       // tree, or else there will not be a unique deepest block.
 193       DEBUG_ONLY(assert_dom(deepb, inb, n, cfg));
 194       deepb = inb;                      // Save deepest block
 195       deepb_dom_depth = deepb->_dom_depth;
 196     }
 197   }
 198   assert(deepb != NULL, "must be at least one input to n");
 199   return deepb;
 200 }
 201 
 202 
 203 //------------------------------schedule_early---------------------------------
 204 // Find the earliest Block any instruction can be placed in.  Some instructions
 205 // are pinned into Blocks.  Unpinned instructions can appear in last block in
 206 // which all their inputs occur.
 207 bool PhaseCFG::schedule_early(VectorSet &visited, Node_List &roots) {
 208   // Allocate stack with enough space to avoid frequent realloc
 209   Node_Stack nstack(roots.Size() + 8);
 210   // _root will be processed among C->top() inputs
 211   roots.push(C->top());
 212   visited.set(C->top()->_idx);
 213 
 214   while (roots.size() != 0) {
 215     // Use local variables nstack_top_n & nstack_top_i to cache values
 216     // on stack's top.
 217     Node* parent_node = roots.pop();
 218     uint  input_index = 0;
 219 
 220     while (true) {
 221       if (input_index == 0) {
 222         // Fixup some control.  Constants without control get attached
 223         // to root and nodes that use is_block_proj() nodes should be attached
 224         // to the region that starts their block.
 225         const Node* control_input = parent_node->in(0);
 226         if (control_input != NULL) {
 227           replace_block_proj_ctrl(parent_node);
 228         } else {
 229           // Is a constant with NO inputs?
 230           if (parent_node->req() == 1) {
 231             parent_node->set_req(0, _root);
 232           }
 233         }
 234       }
 235 
 236       // First, visit all inputs and force them to get a block.  If an
 237       // input is already in a block we quit following inputs (to avoid
 238       // cycles). Instead we put that Node on a worklist to be handled
 239       // later (since IT'S inputs may not have a block yet).
 240 
 241       // Assume all n's inputs will be processed
 242       bool done = true;
 243 
 244       while (input_index < parent_node->len()) {
 245         Node* in = parent_node->in(input_index++);
 246         if (in == NULL) {
 247           continue;
 248         }
 249 
 250         int is_visited = visited.test_set(in->_idx);
 251         if (!has_block(in)) {
 252           if (is_visited) {
 253             return false;
 254           }
 255           // Save parent node and next input's index.
 256           nstack.push(parent_node, input_index);
 257           // Process current input now.
 258           parent_node = in;
 259           input_index = 0;
 260           // Not all n's inputs processed.
 261           done = false;
 262           break;
 263         } else if (!is_visited) {
 264           // Visit this guy later, using worklist
 265           roots.push(in);
 266         }
 267       }
 268 
 269       if (done) {
 270         // All of n's inputs have been processed, complete post-processing.
 271 
 272         // Some instructions are pinned into a block.  These include Region,
 273         // Phi, Start, Return, and other control-dependent instructions and
 274         // any projections which depend on them.
 275         if (!parent_node->pinned()) {
 276           // Set earliest legal block.
 277           Block* earliest_block = find_deepest_input(parent_node, this);
 278           map_node_to_block(parent_node, earliest_block);
 279         } else {
 280           assert(get_block_for_node(parent_node) == get_block_for_node(parent_node->in(0)), "Pinned Node should be at the same block as its control edge");
 281         }
 282 
 283         if (nstack.is_empty()) {
 284           // Finished all nodes on stack.
 285           // Process next node on the worklist 'roots'.
 286           break;
 287         }
 288         // Get saved parent node and next input's index.
 289         parent_node = nstack.node();
 290         input_index = nstack.index();
 291         nstack.pop();
 292       }
 293     }
 294   }
 295   return true;
 296 }
 297 
 298 //------------------------------dom_lca----------------------------------------
 299 // Find least common ancestor in dominator tree
 300 // LCA is a current notion of LCA, to be raised above 'this'.
 301 // As a convenient boundary condition, return 'this' if LCA is NULL.
 302 // Find the LCA of those two nodes.
 303 Block* Block::dom_lca(Block* LCA) {
 304   if (LCA == NULL || LCA == this)  return this;
 305 
 306   Block* anc = this;
 307   while (anc->_dom_depth > LCA->_dom_depth)
 308     anc = anc->_idom;           // Walk up till anc is as high as LCA
 309 
 310   while (LCA->_dom_depth > anc->_dom_depth)
 311     LCA = LCA->_idom;           // Walk up till LCA is as high as anc
 312 
 313   while (LCA != anc) {          // Walk both up till they are the same
 314     LCA = LCA->_idom;
 315     anc = anc->_idom;
 316   }
 317 
 318   return LCA;
 319 }
 320 
 321 //--------------------------raise_LCA_above_use--------------------------------
 322 // We are placing a definition, and have been given a def->use edge.
 323 // The definition must dominate the use, so move the LCA upward in the
 324 // dominator tree to dominate the use.  If the use is a phi, adjust
 325 // the LCA only with the phi input paths which actually use this def.
 326 static Block* raise_LCA_above_use(Block* LCA, Node* use, Node* def, const PhaseCFG* cfg) {
 327   Block* buse = cfg->get_block_for_node(use);
 328   if (buse == NULL)    return LCA;   // Unused killing Projs have no use block
 329   if (!use->is_Phi())  return buse->dom_lca(LCA);
 330   uint pmax = use->req();       // Number of Phi inputs
 331   // Why does not this loop just break after finding the matching input to
 332   // the Phi?  Well...it's like this.  I do not have true def-use/use-def
 333   // chains.  Means I cannot distinguish, from the def-use direction, which
 334   // of many use-defs lead from the same use to the same def.  That is, this
 335   // Phi might have several uses of the same def.  Each use appears in a
 336   // different predecessor block.  But when I enter here, I cannot distinguish
 337   // which use-def edge I should find the predecessor block for.  So I find
 338   // them all.  Means I do a little extra work if a Phi uses the same value
 339   // more than once.
 340   for (uint j=1; j<pmax; j++) { // For all inputs
 341     if (use->in(j) == def) {    // Found matching input?
 342       Block* pred = cfg->get_block_for_node(buse->pred(j));
 343       LCA = pred->dom_lca(LCA);
 344     }
 345   }
 346   return LCA;
 347 }
 348 
 349 //----------------------------raise_LCA_above_marks----------------------------
 350 // Return a new LCA that dominates LCA and any of its marked predecessors.
 351 // Search all my parents up to 'early' (exclusive), looking for predecessors
 352 // which are marked with the given index.  Return the LCA (in the dom tree)
 353 // of all marked blocks.  If there are none marked, return the original
 354 // LCA.
 355 static Block* raise_LCA_above_marks(Block* LCA, node_idx_t mark, Block* early, const PhaseCFG* cfg) {
 356   Block_List worklist;
 357   worklist.push(LCA);
 358   while (worklist.size() > 0) {
 359     Block* mid = worklist.pop();
 360     if (mid == early)  continue;  // stop searching here
 361 
 362     // Test and set the visited bit.
 363     if (mid->raise_LCA_visited() == mark)  continue;  // already visited
 364 
 365     // Don't process the current LCA, otherwise the search may terminate early
 366     if (mid != LCA && mid->raise_LCA_mark() == mark) {
 367       // Raise the LCA.
 368       LCA = mid->dom_lca(LCA);
 369       if (LCA == early)  break;   // stop searching everywhere
 370       assert(early->dominates(LCA), "early is high enough");
 371       // Resume searching at that point, skipping intermediate levels.
 372       worklist.push(LCA);
 373       if (LCA == mid)
 374         continue; // Don't mark as visited to avoid early termination.
 375     } else {
 376       // Keep searching through this block's predecessors.
 377       for (uint j = 1, jmax = mid->num_preds(); j < jmax; j++) {
 378         Block* mid_parent = cfg->get_block_for_node(mid->pred(j));
 379         worklist.push(mid_parent);
 380       }
 381     }
 382     mid->set_raise_LCA_visited(mark);
 383   }
 384   return LCA;
 385 }
 386 
 387 //--------------------------memory_early_block--------------------------------
 388 // This is a variation of find_deepest_input, the heart of schedule_early.
 389 // Find the "early" block for a load, if we considered only memory and
 390 // address inputs, that is, if other data inputs were ignored.
 391 //
 392 // Because a subset of edges are considered, the resulting block will
 393 // be earlier (at a shallower dom_depth) than the true schedule_early
 394 // point of the node. We compute this earlier block as a more permissive
 395 // site for anti-dependency insertion, but only if subsume_loads is enabled.
 396 static Block* memory_early_block(Node* load, Block* early, const PhaseCFG* cfg) {
 397   Node* base;
 398   Node* index;
 399   Node* store = load->in(MemNode::Memory);
 400   load->as_Mach()->memory_inputs(base, index);
 401 
 402   assert(base != NodeSentinel && index != NodeSentinel,
 403          "unexpected base/index inputs");
 404 
 405   Node* mem_inputs[4];
 406   int mem_inputs_length = 0;
 407   if (base != NULL)  mem_inputs[mem_inputs_length++] = base;
 408   if (index != NULL) mem_inputs[mem_inputs_length++] = index;
 409   if (store != NULL) mem_inputs[mem_inputs_length++] = store;
 410 
 411   // In the comparision below, add one to account for the control input,
 412   // which may be null, but always takes up a spot in the in array.
 413   if (mem_inputs_length + 1 < (int) load->req()) {
 414     // This "load" has more inputs than just the memory, base and index inputs.
 415     // For purposes of checking anti-dependences, we need to start
 416     // from the early block of only the address portion of the instruction,
 417     // and ignore other blocks that may have factored into the wider
 418     // schedule_early calculation.
 419     if (load->in(0) != NULL) mem_inputs[mem_inputs_length++] = load->in(0);
 420 
 421     Block* deepb           = NULL;        // Deepest block so far
 422     int    deepb_dom_depth = 0;
 423     for (int i = 0; i < mem_inputs_length; i++) {
 424       Block* inb = cfg->get_block_for_node(mem_inputs[i]);
 425       if (deepb_dom_depth < (int) inb->_dom_depth) {
 426         // The new inb must be dominated by the previous deepb.
 427         // The various inputs must be linearly ordered in the dom
 428         // tree, or else there will not be a unique deepest block.
 429         DEBUG_ONLY(assert_dom(deepb, inb, load, cfg));
 430         deepb = inb;                      // Save deepest block
 431         deepb_dom_depth = deepb->_dom_depth;
 432       }
 433     }
 434     early = deepb;
 435   }
 436 
 437   return early;
 438 }
 439 
 440 //--------------------------insert_anti_dependences---------------------------
 441 // A load may need to witness memory that nearby stores can overwrite.
 442 // For each nearby store, either insert an "anti-dependence" edge
 443 // from the load to the store, or else move LCA upward to force the
 444 // load to (eventually) be scheduled in a block above the store.
 445 //
 446 // Do not add edges to stores on distinct control-flow paths;
 447 // only add edges to stores which might interfere.
 448 //
 449 // Return the (updated) LCA.  There will not be any possibly interfering
 450 // store between the load's "early block" and the updated LCA.
 451 // Any stores in the updated LCA will have new precedence edges
 452 // back to the load.  The caller is expected to schedule the load
 453 // in the LCA, in which case the precedence edges will make LCM
 454 // preserve anti-dependences.  The caller may also hoist the load
 455 // above the LCA, if it is not the early block.
 456 Block* PhaseCFG::insert_anti_dependences(Block* LCA, Node* load, bool verify) {
 457   assert(load->needs_anti_dependence_check(), "must be a load of some sort");
 458   assert(LCA != NULL, "");
 459   DEBUG_ONLY(Block* LCA_orig = LCA);
 460 
 461   // Compute the alias index.  Loads and stores with different alias indices
 462   // do not need anti-dependence edges.
 463   uint load_alias_idx = C->get_alias_index(load->adr_type());
 464 #ifdef ASSERT
 465   if (load_alias_idx == Compile::AliasIdxBot && C->AliasLevel() > 0 &&
 466       (PrintOpto || VerifyAliases ||
 467        PrintMiscellaneous && (WizardMode || Verbose))) {
 468     // Load nodes should not consume all of memory.
 469     // Reporting a bottom type indicates a bug in adlc.
 470     // If some particular type of node validly consumes all of memory,
 471     // sharpen the preceding "if" to exclude it, so we can catch bugs here.
 472     tty->print_cr("*** Possible Anti-Dependence Bug:  Load consumes all of memory.");
 473     load->dump(2);
 474     if (VerifyAliases)  assert(load_alias_idx != Compile::AliasIdxBot, "");
 475   }
 476 #endif
 477   assert(load_alias_idx || (load->is_Mach() && load->as_Mach()->ideal_Opcode() == Op_StrComp),
 478          "String compare is only known 'load' that does not conflict with any stores");
 479   assert(load_alias_idx || (load->is_Mach() && load->as_Mach()->ideal_Opcode() == Op_StrEquals),
 480          "String equals is a 'load' that does not conflict with any stores");
 481   assert(load_alias_idx || (load->is_Mach() && load->as_Mach()->ideal_Opcode() == Op_StrIndexOf),
 482          "String indexOf is a 'load' that does not conflict with any stores");
 483   assert(load_alias_idx || (load->is_Mach() && load->as_Mach()->ideal_Opcode() == Op_AryEq),
 484          "Arrays equals is a 'load' that do not conflict with any stores");
 485 
 486   if (!C->alias_type(load_alias_idx)->is_rewritable()) {
 487     // It is impossible to spoil this load by putting stores before it,
 488     // because we know that the stores will never update the value
 489     // which 'load' must witness.
 490     return LCA;
 491   }
 492 
 493   node_idx_t load_index = load->_idx;
 494 
 495   // Note the earliest legal placement of 'load', as determined by
 496   // by the unique point in the dom tree where all memory effects
 497   // and other inputs are first available.  (Computed by schedule_early.)
 498   // For normal loads, 'early' is the shallowest place (dom graph wise)
 499   // to look for anti-deps between this load and any store.
 500   Block* early = get_block_for_node(load);
 501 
 502   // If we are subsuming loads, compute an "early" block that only considers
 503   // memory or address inputs. This block may be different than the
 504   // schedule_early block in that it could be at an even shallower depth in the
 505   // dominator tree, and allow for a broader discovery of anti-dependences.
 506   if (C->subsume_loads()) {
 507     early = memory_early_block(load, early, this);
 508   }
 509 
 510   ResourceArea *area = Thread::current()->resource_area();
 511   Node_List worklist_mem(area);     // prior memory state to store
 512   Node_List worklist_store(area);   // possible-def to explore
 513   Node_List worklist_visited(area); // visited mergemem nodes
 514   Node_List non_early_stores(area); // all relevant stores outside of early
 515   bool must_raise_LCA = false;
 516 
 517 #ifdef TRACK_PHI_INPUTS
 518   // %%% This extra checking fails because MergeMem nodes are not GVNed.
 519   // Provide "phi_inputs" to check if every input to a PhiNode is from the
 520   // original memory state.  This indicates a PhiNode for which should not
 521   // prevent the load from sinking.  For such a block, set_raise_LCA_mark
 522   // may be overly conservative.
 523   // Mechanism: count inputs seen for each Phi encountered in worklist_store.
 524   DEBUG_ONLY(GrowableArray<uint> phi_inputs(area, C->unique(),0,0));
 525 #endif
 526 
 527   // 'load' uses some memory state; look for users of the same state.
 528   // Recurse through MergeMem nodes to the stores that use them.
 529 
 530   // Each of these stores is a possible definition of memory
 531   // that 'load' needs to use.  We need to force 'load'
 532   // to occur before each such store.  When the store is in
 533   // the same block as 'load', we insert an anti-dependence
 534   // edge load->store.
 535 
 536   // The relevant stores "nearby" the load consist of a tree rooted
 537   // at initial_mem, with internal nodes of type MergeMem.
 538   // Therefore, the branches visited by the worklist are of this form:
 539   //    initial_mem -> (MergeMem ->)* store
 540   // The anti-dependence constraints apply only to the fringe of this tree.
 541 
 542   Node* initial_mem = load->in(MemNode::Memory);
 543   worklist_store.push(initial_mem);
 544   worklist_visited.push(initial_mem);
 545   worklist_mem.push(NULL);
 546   while (worklist_store.size() > 0) {
 547     // Examine a nearby store to see if it might interfere with our load.
 548     Node* mem   = worklist_mem.pop();
 549     Node* store = worklist_store.pop();
 550     uint op = store->Opcode();
 551 
 552     // MergeMems do not directly have anti-deps.
 553     // Treat them as internal nodes in a forward tree of memory states,
 554     // the leaves of which are each a 'possible-def'.
 555     if (store == initial_mem    // root (exclusive) of tree we are searching
 556         || op == Op_MergeMem    // internal node of tree we are searching
 557         ) {
 558       mem = store;   // It's not a possibly interfering store.
 559       if (store == initial_mem)
 560         initial_mem = NULL;  // only process initial memory once
 561 
 562       for (DUIterator_Fast imax, i = mem->fast_outs(imax); i < imax; i++) {
 563         store = mem->fast_out(i);
 564         if (store->is_MergeMem()) {
 565           // Be sure we don't get into combinatorial problems.
 566           // (Allow phis to be repeated; they can merge two relevant states.)
 567           uint j = worklist_visited.size();
 568           for (; j > 0; j--) {
 569             if (worklist_visited.at(j-1) == store)  break;
 570           }
 571           if (j > 0)  continue; // already on work list; do not repeat
 572           worklist_visited.push(store);
 573         }
 574         worklist_mem.push(mem);
 575         worklist_store.push(store);
 576       }
 577       continue;
 578     }
 579 
 580     if (op == Op_MachProj || op == Op_Catch)   continue;
 581     if (store->needs_anti_dependence_check())  continue;  // not really a store
 582 
 583     // Compute the alias index.  Loads and stores with different alias
 584     // indices do not need anti-dependence edges.  Wide MemBar's are
 585     // anti-dependent on everything (except immutable memories).
 586     const TypePtr* adr_type = store->adr_type();
 587     if (!C->can_alias(adr_type, load_alias_idx))  continue;
 588 
 589     // Most slow-path runtime calls do NOT modify Java memory, but
 590     // they can block and so write Raw memory.
 591     if (store->is_Mach()) {
 592       MachNode* mstore = store->as_Mach();
 593       if (load_alias_idx != Compile::AliasIdxRaw) {
 594         // Check for call into the runtime using the Java calling
 595         // convention (and from there into a wrapper); it has no
 596         // _method.  Can't do this optimization for Native calls because
 597         // they CAN write to Java memory.
 598         if (mstore->ideal_Opcode() == Op_CallStaticJava) {
 599           assert(mstore->is_MachSafePoint(), "");
 600           MachSafePointNode* ms = (MachSafePointNode*) mstore;
 601           assert(ms->is_MachCallJava(), "");
 602           MachCallJavaNode* mcj = (MachCallJavaNode*) ms;
 603           if (mcj->_method == NULL) {
 604             // These runtime calls do not write to Java visible memory
 605             // (other than Raw) and so do not require anti-dependence edges.
 606             continue;
 607           }
 608         }
 609         // Same for SafePoints: they read/write Raw but only read otherwise.
 610         // This is basically a workaround for SafePoints only defining control
 611         // instead of control + memory.
 612         if (mstore->ideal_Opcode() == Op_SafePoint)
 613           continue;
 614       } else {
 615         // Some raw memory, such as the load of "top" at an allocation,
 616         // can be control dependent on the previous safepoint. See
 617         // comments in GraphKit::allocate_heap() about control input.
 618         // Inserting an anti-dep between such a safepoint and a use
 619         // creates a cycle, and will cause a subsequent failure in
 620         // local scheduling.  (BugId 4919904)
 621         // (%%% How can a control input be a safepoint and not a projection??)
 622         if (mstore->ideal_Opcode() == Op_SafePoint && load->in(0) == mstore)
 623           continue;
 624       }
 625     }
 626 
 627     // Identify a block that the current load must be above,
 628     // or else observe that 'store' is all the way up in the
 629     // earliest legal block for 'load'.  In the latter case,
 630     // immediately insert an anti-dependence edge.
 631     Block* store_block = get_block_for_node(store);
 632     assert(store_block != NULL, "unused killing projections skipped above");
 633 
 634     if (store->is_Phi()) {
 635       // 'load' uses memory which is one (or more) of the Phi's inputs.
 636       // It must be scheduled not before the Phi, but rather before
 637       // each of the relevant Phi inputs.
 638       //
 639       // Instead of finding the LCA of all inputs to a Phi that match 'mem',
 640       // we mark each corresponding predecessor block and do a combined
 641       // hoisting operation later (raise_LCA_above_marks).
 642       //
 643       // Do not assert(store_block != early, "Phi merging memory after access")
 644       // PhiNode may be at start of block 'early' with backedge to 'early'
 645       DEBUG_ONLY(bool found_match = false);
 646       for (uint j = PhiNode::Input, jmax = store->req(); j < jmax; j++) {
 647         if (store->in(j) == mem) {   // Found matching input?
 648           DEBUG_ONLY(found_match = true);
 649           Block* pred_block = get_block_for_node(store_block->pred(j));
 650           if (pred_block != early) {
 651             // If any predecessor of the Phi matches the load's "early block",
 652             // we do not need a precedence edge between the Phi and 'load'
 653             // since the load will be forced into a block preceding the Phi.
 654             pred_block->set_raise_LCA_mark(load_index);
 655             assert(!LCA_orig->dominates(pred_block) ||
 656                    early->dominates(pred_block), "early is high enough");
 657             must_raise_LCA = true;
 658           } else {
 659             // anti-dependent upon PHI pinned below 'early', no edge needed
 660             LCA = early;             // but can not schedule below 'early'
 661           }
 662         }
 663       }
 664       assert(found_match, "no worklist bug");
 665 #ifdef TRACK_PHI_INPUTS
 666 #ifdef ASSERT
 667       // This assert asks about correct handling of PhiNodes, which may not
 668       // have all input edges directly from 'mem'. See BugId 4621264
 669       int num_mem_inputs = phi_inputs.at_grow(store->_idx,0) + 1;
 670       // Increment by exactly one even if there are multiple copies of 'mem'
 671       // coming into the phi, because we will run this block several times
 672       // if there are several copies of 'mem'.  (That's how DU iterators work.)
 673       phi_inputs.at_put(store->_idx, num_mem_inputs);
 674       assert(PhiNode::Input + num_mem_inputs < store->req(),
 675              "Expect at least one phi input will not be from original memory state");
 676 #endif //ASSERT
 677 #endif //TRACK_PHI_INPUTS
 678     } else if (store_block != early) {
 679       // 'store' is between the current LCA and earliest possible block.
 680       // Label its block, and decide later on how to raise the LCA
 681       // to include the effect on LCA of this store.
 682       // If this store's block gets chosen as the raised LCA, we
 683       // will find him on the non_early_stores list and stick him
 684       // with a precedence edge.
 685       // (But, don't bother if LCA is already raised all the way.)
 686       if (LCA != early) {
 687         store_block->set_raise_LCA_mark(load_index);
 688         must_raise_LCA = true;
 689         non_early_stores.push(store);
 690       }
 691     } else {
 692       // Found a possibly-interfering store in the load's 'early' block.
 693       // This means 'load' cannot sink at all in the dominator tree.
 694       // Add an anti-dep edge, and squeeze 'load' into the highest block.
 695       assert(store != load->in(0), "dependence cycle found");
 696       if (verify) {
 697         assert(store->find_edge(load) != -1, "missing precedence edge");
 698       } else {
 699         store->add_prec(load);
 700       }
 701       LCA = early;
 702       // This turns off the process of gathering non_early_stores.
 703     }
 704   }
 705   // (Worklist is now empty; all nearby stores have been visited.)
 706 
 707   // Finished if 'load' must be scheduled in its 'early' block.
 708   // If we found any stores there, they have already been given
 709   // precedence edges.
 710   if (LCA == early)  return LCA;
 711 
 712   // We get here only if there are no possibly-interfering stores
 713   // in the load's 'early' block.  Move LCA up above all predecessors
 714   // which contain stores we have noted.
 715   //
 716   // The raised LCA block can be a home to such interfering stores,
 717   // but its predecessors must not contain any such stores.
 718   //
 719   // The raised LCA will be a lower bound for placing the load,
 720   // preventing the load from sinking past any block containing
 721   // a store that may invalidate the memory state required by 'load'.
 722   if (must_raise_LCA)
 723     LCA = raise_LCA_above_marks(LCA, load->_idx, early, this);
 724   if (LCA == early)  return LCA;
 725 
 726   // Insert anti-dependence edges from 'load' to each store
 727   // in the non-early LCA block.
 728   // Mine the non_early_stores list for such stores.
 729   if (LCA->raise_LCA_mark() == load_index) {
 730     while (non_early_stores.size() > 0) {
 731       Node* store = non_early_stores.pop();
 732       Block* store_block = get_block_for_node(store);
 733       if (store_block == LCA) {
 734         // add anti_dependence from store to load in its own block
 735         assert(store != load->in(0), "dependence cycle found");
 736         if (verify) {
 737           assert(store->find_edge(load) != -1, "missing precedence edge");
 738         } else {
 739           store->add_prec(load);
 740         }
 741       } else {
 742         assert(store_block->raise_LCA_mark() == load_index, "block was marked");
 743         // Any other stores we found must be either inside the new LCA
 744         // or else outside the original LCA.  In the latter case, they
 745         // did not interfere with any use of 'load'.
 746         assert(LCA->dominates(store_block)
 747                || !LCA_orig->dominates(store_block), "no stray stores");
 748       }
 749     }
 750   }
 751 
 752   // Return the highest block containing stores; any stores
 753   // within that block have been given anti-dependence edges.
 754   return LCA;
 755 }
 756 
 757 // This class is used to iterate backwards over the nodes in the graph.
 758 
 759 class Node_Backward_Iterator {
 760 
 761 private:
 762   Node_Backward_Iterator();
 763 
 764 public:
 765   // Constructor for the iterator
 766   Node_Backward_Iterator(Node *root, VectorSet &visited, Node_List &stack, PhaseCFG &cfg);
 767 
 768   // Postincrement operator to iterate over the nodes
 769   Node *next();
 770 
 771 private:
 772   VectorSet   &_visited;
 773   Node_List   &_stack;
 774   PhaseCFG &_cfg;
 775 };
 776 
 777 // Constructor for the Node_Backward_Iterator
 778 Node_Backward_Iterator::Node_Backward_Iterator( Node *root, VectorSet &visited, Node_List &stack, PhaseCFG &cfg)
 779   : _visited(visited), _stack(stack), _cfg(cfg) {
 780   // The stack should contain exactly the root
 781   stack.clear();
 782   stack.push(root);
 783 
 784   // Clear the visited bits
 785   visited.Clear();
 786 }
 787 
 788 // Iterator for the Node_Backward_Iterator
 789 Node *Node_Backward_Iterator::next() {
 790 
 791   // If the _stack is empty, then just return NULL: finished.
 792   if ( !_stack.size() )
 793     return NULL;
 794 
 795   // '_stack' is emulating a real _stack.  The 'visit-all-users' loop has been
 796   // made stateless, so I do not need to record the index 'i' on my _stack.
 797   // Instead I visit all users each time, scanning for unvisited users.
 798   // I visit unvisited not-anti-dependence users first, then anti-dependent
 799   // children next.
 800   Node *self = _stack.pop();
 801 
 802   // I cycle here when I am entering a deeper level of recursion.
 803   // The key variable 'self' was set prior to jumping here.
 804   while( 1 ) {
 805 
 806     _visited.set(self->_idx);
 807 
 808     // Now schedule all uses as late as possible.
 809     const Node* src = self->is_Proj() ? self->in(0) : self;
 810     uint src_rpo = _cfg.get_block_for_node(src)->_rpo;
 811 
 812     // Schedule all nodes in a post-order visit
 813     Node *unvisited = NULL;  // Unvisited anti-dependent Node, if any
 814 
 815     // Scan for unvisited nodes
 816     for (DUIterator_Fast imax, i = self->fast_outs(imax); i < imax; i++) {
 817       // For all uses, schedule late
 818       Node* n = self->fast_out(i); // Use
 819 
 820       // Skip already visited children
 821       if ( _visited.test(n->_idx) )
 822         continue;
 823 
 824       // do not traverse backward control edges
 825       Node *use = n->is_Proj() ? n->in(0) : n;
 826       uint use_rpo = _cfg.get_block_for_node(use)->_rpo;
 827 
 828       if ( use_rpo < src_rpo )
 829         continue;
 830 
 831       // Phi nodes always precede uses in a basic block
 832       if ( use_rpo == src_rpo && use->is_Phi() )
 833         continue;
 834 
 835       unvisited = n;      // Found unvisited
 836 
 837       // Check for possible-anti-dependent
 838       if( !n->needs_anti_dependence_check() )
 839         break;            // Not visited, not anti-dep; schedule it NOW
 840     }
 841 
 842     // Did I find an unvisited not-anti-dependent Node?
 843     if ( !unvisited )
 844       break;                  // All done with children; post-visit 'self'
 845 
 846     // Visit the unvisited Node.  Contains the obvious push to
 847     // indicate I'm entering a deeper level of recursion.  I push the
 848     // old state onto the _stack and set a new state and loop (recurse).
 849     _stack.push(self);
 850     self = unvisited;
 851   } // End recursion loop
 852 
 853   return self;
 854 }
 855 
 856 //------------------------------ComputeLatenciesBackwards----------------------
 857 // Compute the latency of all the instructions.
 858 void PhaseCFG::compute_latencies_backwards(VectorSet &visited, Node_List &stack) {
 859 #ifndef PRODUCT
 860   if (trace_opto_pipelining())
 861     tty->print("\n#---- ComputeLatenciesBackwards ----\n");
 862 #endif
 863 
 864   Node_Backward_Iterator iter((Node *)_root, visited, stack, *this);
 865   Node *n;
 866 
 867   // Walk over all the nodes from last to first
 868   while (n = iter.next()) {
 869     // Set the latency for the definitions of this instruction
 870     partial_latency_of_defs(n);
 871   }
 872 } // end ComputeLatenciesBackwards
 873 
 874 //------------------------------partial_latency_of_defs------------------------
 875 // Compute the latency impact of this node on all defs.  This computes
 876 // a number that increases as we approach the beginning of the routine.
 877 void PhaseCFG::partial_latency_of_defs(Node *n) {
 878   // Set the latency for this instruction
 879 #ifndef PRODUCT
 880   if (trace_opto_pipelining()) {
 881     tty->print("# latency_to_inputs: node_latency[%d] = %d for node", n->_idx, get_latency_for_node(n));
 882     dump();
 883   }
 884 #endif
 885 
 886   if (n->is_Proj()) {
 887     n = n->in(0);
 888   }
 889 
 890   if (n->is_Root()) {
 891     return;
 892   }
 893 
 894   uint nlen = n->len();
 895   uint use_latency = get_latency_for_node(n);
 896   uint use_pre_order = get_block_for_node(n)->_pre_order;
 897 
 898   for (uint j = 0; j < nlen; j++) {
 899     Node *def = n->in(j);
 900 
 901     if (!def || def == n) {
 902       continue;
 903     }
 904 
 905     // Walk backwards thru projections
 906     if (def->is_Proj()) {
 907       def = def->in(0);
 908     }
 909 
 910 #ifndef PRODUCT
 911     if (trace_opto_pipelining()) {
 912       tty->print("#    in(%2d): ", j);
 913       def->dump();
 914     }
 915 #endif
 916 
 917     // If the defining block is not known, assume it is ok
 918     Block *def_block = get_block_for_node(def);
 919     uint def_pre_order = def_block ? def_block->_pre_order : 0;
 920 
 921     if ((use_pre_order <  def_pre_order) || (use_pre_order == def_pre_order && n->is_Phi())) {
 922       continue;
 923     }
 924 
 925     uint delta_latency = n->latency(j);
 926     uint current_latency = delta_latency + use_latency;
 927 
 928     if (get_latency_for_node(def) < current_latency) {
 929       set_latency_for_node(def, current_latency);
 930     }
 931 
 932 #ifndef PRODUCT
 933     if (trace_opto_pipelining()) {
 934       tty->print_cr("#      %d + edge_latency(%d) == %d -> %d, node_latency[%d] = %d", use_latency, j, delta_latency, current_latency, def->_idx, get_latency_for_node(def));
 935     }
 936 #endif
 937   }
 938 }
 939 
 940 //------------------------------latency_from_use-------------------------------
 941 // Compute the latency of a specific use
 942 int PhaseCFG::latency_from_use(Node *n, const Node *def, Node *use) {
 943   // If self-reference, return no latency
 944   if (use == n || use->is_Root()) {
 945     return 0;
 946   }
 947 
 948   uint def_pre_order = get_block_for_node(def)->_pre_order;
 949   uint latency = 0;
 950 
 951   // If the use is not a projection, then it is simple...
 952   if (!use->is_Proj()) {
 953 #ifndef PRODUCT
 954     if (trace_opto_pipelining()) {
 955       tty->print("#    out(): ");
 956       use->dump();
 957     }
 958 #endif
 959 
 960     uint use_pre_order = get_block_for_node(use)->_pre_order;
 961 
 962     if (use_pre_order < def_pre_order)
 963       return 0;
 964 
 965     if (use_pre_order == def_pre_order && use->is_Phi())
 966       return 0;
 967 
 968     uint nlen = use->len();
 969     uint nl = get_latency_for_node(use);
 970 
 971     for ( uint j=0; j<nlen; j++ ) {
 972       if (use->in(j) == n) {
 973         // Change this if we want local latencies
 974         uint ul = use->latency(j);
 975         uint  l = ul + nl;
 976         if (latency < l) latency = l;
 977 #ifndef PRODUCT
 978         if (trace_opto_pipelining()) {
 979           tty->print_cr("#      %d + edge_latency(%d) == %d -> %d, latency = %d",
 980                         nl, j, ul, l, latency);
 981         }
 982 #endif
 983       }
 984     }
 985   } else {
 986     // This is a projection, just grab the latency of the use(s)
 987     for (DUIterator_Fast jmax, j = use->fast_outs(jmax); j < jmax; j++) {
 988       uint l = latency_from_use(use, def, use->fast_out(j));
 989       if (latency < l) latency = l;
 990     }
 991   }
 992 
 993   return latency;
 994 }
 995 
 996 //------------------------------latency_from_uses------------------------------
 997 // Compute the latency of this instruction relative to all of it's uses.
 998 // This computes a number that increases as we approach the beginning of the
 999 // routine.
1000 void PhaseCFG::latency_from_uses(Node *n) {
1001   // Set the latency for this instruction
1002 #ifndef PRODUCT
1003   if (trace_opto_pipelining()) {
1004     tty->print("# latency_from_outputs: node_latency[%d] = %d for node", n->_idx, get_latency_for_node(n));
1005     dump();
1006   }
1007 #endif
1008   uint latency=0;
1009   const Node *def = n->is_Proj() ? n->in(0): n;
1010 
1011   for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
1012     uint l = latency_from_use(n, def, n->fast_out(i));
1013 
1014     if (latency < l) latency = l;
1015   }
1016 
1017   set_latency_for_node(n, latency);
1018 }
1019 
1020 //------------------------------hoist_to_cheaper_block-------------------------
1021 // Pick a block for node self, between early and LCA, that is a cheaper
1022 // alternative to LCA.
1023 Block* PhaseCFG::hoist_to_cheaper_block(Block* LCA, Block* early, Node* self) {
1024   const double delta = 1+PROB_UNLIKELY_MAG(4);
1025   Block* least       = LCA;
1026   double least_freq  = least->_freq;
1027   uint target        = get_latency_for_node(self);
1028   uint start_latency = get_latency_for_node(LCA->head());
1029   uint end_latency   = get_latency_for_node(LCA->get_node(LCA->end_idx()));
1030   bool in_latency    = (target <= start_latency);
1031   const Block* root_block = get_block_for_node(_root);
1032 
1033   // Turn off latency scheduling if scheduling is just plain off
1034   if (!C->do_scheduling())
1035     in_latency = true;
1036 
1037   // Do not hoist (to cover latency) instructions which target a
1038   // single register.  Hoisting stretches the live range of the
1039   // single register and may force spilling.
1040   MachNode* mach = self->is_Mach() ? self->as_Mach() : NULL;
1041   if (mach && mach->out_RegMask().is_bound1() && mach->out_RegMask().is_NotEmpty())
1042     in_latency = true;
1043 
1044 #ifndef PRODUCT
1045   if (trace_opto_pipelining()) {
1046     tty->print("# Find cheaper block for latency %d: ", get_latency_for_node(self));
1047     self->dump();
1048     tty->print_cr("#   B%d: start latency for [%4d]=%d, end latency for [%4d]=%d, freq=%g",
1049       LCA->_pre_order,
1050       LCA->head()->_idx,
1051       start_latency,
1052       LCA->get_node(LCA->end_idx())->_idx,
1053       end_latency,
1054       least_freq);
1055   }
1056 #endif
1057 
1058   int cand_cnt = 0;  // number of candidates tried
1059 
1060   // Walk up the dominator tree from LCA (Lowest common ancestor) to
1061   // the earliest legal location.  Capture the least execution frequency.
1062   while (LCA != early) {
1063     LCA = LCA->_idom;         // Follow up the dominator tree
1064 
1065     if (LCA == NULL) {
1066       // Bailout without retry
1067       C->record_method_not_compilable("late schedule failed: LCA == NULL");
1068       return least;
1069     }
1070 
1071     // Don't hoist machine instructions to the root basic block
1072     if (mach && LCA == root_block)
1073       break;
1074 
1075     uint start_lat = get_latency_for_node(LCA->head());
1076     uint end_idx   = LCA->end_idx();
1077     uint end_lat   = get_latency_for_node(LCA->get_node(end_idx));
1078     double LCA_freq = LCA->_freq;
1079 #ifndef PRODUCT
1080     if (trace_opto_pipelining()) {
1081       tty->print_cr("#   B%d: start latency for [%4d]=%d, end latency for [%4d]=%d, freq=%g",
1082         LCA->_pre_order, LCA->head()->_idx, start_lat, end_idx, end_lat, LCA_freq);
1083     }
1084 #endif
1085     cand_cnt++;
1086     if (LCA_freq < least_freq              || // Better Frequency
1087         (StressGCM && Compile::randomized_select(cand_cnt)) || // Should be randomly accepted in stress mode
1088          (!StressGCM                    &&    // Otherwise, choose with latency
1089           !in_latency                   &&    // No block containing latency
1090           LCA_freq < least_freq * delta &&    // No worse frequency
1091           target >= end_lat             &&    // within latency range
1092           !self->is_iteratively_computed() )  // But don't hoist IV increments
1093              // because they may end up above other uses of their phi forcing
1094              // their result register to be different from their input.
1095        ) {
1096       least = LCA;            // Found cheaper block
1097       least_freq = LCA_freq;
1098       start_latency = start_lat;
1099       end_latency = end_lat;
1100       if (target <= start_lat)
1101         in_latency = true;
1102     }
1103   }
1104 
1105 #ifndef PRODUCT
1106   if (trace_opto_pipelining()) {
1107     tty->print_cr("#  Choose block B%d with start latency=%d and freq=%g",
1108       least->_pre_order, start_latency, least_freq);
1109   }
1110 #endif
1111 
1112   // See if the latency needs to be updated
1113   if (target < end_latency) {
1114 #ifndef PRODUCT
1115     if (trace_opto_pipelining()) {
1116       tty->print_cr("#  Change latency for [%4d] from %d to %d", self->_idx, target, end_latency);
1117     }
1118 #endif
1119     set_latency_for_node(self, end_latency);
1120     partial_latency_of_defs(self);
1121   }
1122 
1123   return least;
1124 }
1125 
1126 
1127 //------------------------------schedule_late-----------------------------------
1128 // Now schedule all codes as LATE as possible.  This is the LCA in the
1129 // dominator tree of all USES of a value.  Pick the block with the least
1130 // loop nesting depth that is lowest in the dominator tree.
1131 extern const char must_clone[];
1132 void PhaseCFG::schedule_late(VectorSet &visited, Node_List &stack) {
1133 #ifndef PRODUCT
1134   if (trace_opto_pipelining())
1135     tty->print("\n#---- schedule_late ----\n");
1136 #endif
1137 
1138   Node_Backward_Iterator iter((Node *)_root, visited, stack, *this);
1139   Node *self;
1140 
1141   // Walk over all the nodes from last to first
1142   while (self = iter.next()) {
1143     Block* early = get_block_for_node(self); // Earliest legal placement
1144 
1145     if (self->is_top()) {
1146       // Top node goes in bb #2 with other constants.
1147       // It must be special-cased, because it has no out edges.
1148       early->add_inst(self);
1149       continue;
1150     }
1151 
1152     // No uses, just terminate
1153     if (self->outcnt() == 0) {
1154       assert(self->is_MachProj(), "sanity");
1155       continue;                   // Must be a dead machine projection
1156     }
1157 
1158     // If node is pinned in the block, then no scheduling can be done.
1159     if( self->pinned() )          // Pinned in block?
1160       continue;
1161 
1162     MachNode* mach = self->is_Mach() ? self->as_Mach() : NULL;
1163     if (mach) {
1164       switch (mach->ideal_Opcode()) {
1165       case Op_CreateEx:
1166         // Don't move exception creation
1167         early->add_inst(self);
1168         continue;
1169         break;
1170       case Op_CheckCastPP:
1171         // Don't move CheckCastPP nodes away from their input, if the input
1172         // is a rawptr (5071820).
1173         Node *def = self->in(1);
1174         if (def != NULL && def->bottom_type()->base() == Type::RawPtr) {
1175           early->add_inst(self);
1176 #ifdef ASSERT
1177           _raw_oops.push(def);
1178 #endif
1179           continue;
1180         }
1181         break;
1182       }
1183     }
1184 
1185     // Gather LCA of all uses
1186     Block *LCA = NULL;
1187     {
1188       for (DUIterator_Fast imax, i = self->fast_outs(imax); i < imax; i++) {
1189         // For all uses, find LCA
1190         Node* use = self->fast_out(i);
1191         LCA = raise_LCA_above_use(LCA, use, self, this);
1192       }
1193     }  // (Hide defs of imax, i from rest of block.)
1194 
1195     // Place temps in the block of their use.  This isn't a
1196     // requirement for correctness but it reduces useless
1197     // interference between temps and other nodes.
1198     if (mach != NULL && mach->is_MachTemp()) {
1199       map_node_to_block(self, LCA);
1200       LCA->add_inst(self);
1201       continue;
1202     }
1203 
1204     // Check if 'self' could be anti-dependent on memory
1205     if (self->needs_anti_dependence_check()) {
1206       // Hoist LCA above possible-defs and insert anti-dependences to
1207       // defs in new LCA block.
1208       LCA = insert_anti_dependences(LCA, self);
1209     }
1210 
1211     if (early->_dom_depth > LCA->_dom_depth) {
1212       // Somehow the LCA has moved above the earliest legal point.
1213       // (One way this can happen is via memory_early_block.)
1214       if (C->subsume_loads() == true && !C->failing()) {
1215         // Retry with subsume_loads == false
1216         // If this is the first failure, the sentinel string will "stick"
1217         // to the Compile object, and the C2Compiler will see it and retry.
1218         C->record_failure(C2Compiler::retry_no_subsuming_loads());
1219       } else {
1220         // Bailout without retry when (early->_dom_depth > LCA->_dom_depth)
1221         C->record_method_not_compilable("late schedule failed: incorrect graph");
1222       }
1223       return;
1224     }
1225 
1226     // If there is no opportunity to hoist, then we're done.
1227     // In stress mode, try to hoist even the single operations.
1228     bool try_to_hoist = StressGCM || (LCA != early);
1229 
1230     // Must clone guys stay next to use; no hoisting allowed.
1231     // Also cannot hoist guys that alter memory or are otherwise not
1232     // allocatable (hoisting can make a value live longer, leading to
1233     // anti and output dependency problems which are normally resolved
1234     // by the register allocator giving everyone a different register).
1235     if (mach != NULL && must_clone[mach->ideal_Opcode()])
1236       try_to_hoist = false;
1237 
1238     Block* late = NULL;
1239     if (try_to_hoist) {
1240       // Now find the block with the least execution frequency.
1241       // Start at the latest schedule and work up to the earliest schedule
1242       // in the dominator tree.  Thus the Node will dominate all its uses.
1243       late = hoist_to_cheaper_block(LCA, early, self);
1244     } else {
1245       // Just use the LCA of the uses.
1246       late = LCA;
1247     }
1248 
1249     // Put the node into target block
1250     schedule_node_into_block(self, late);
1251 
1252 #ifdef ASSERT
1253     if (self->needs_anti_dependence_check()) {
1254       // since precedence edges are only inserted when we're sure they
1255       // are needed make sure that after placement in a block we don't
1256       // need any new precedence edges.
1257       verify_anti_dependences(late, self);
1258     }
1259 #endif
1260   } // Loop until all nodes have been visited
1261 
1262 } // end ScheduleLate
1263 
1264 //------------------------------GlobalCodeMotion-------------------------------
1265 void PhaseCFG::global_code_motion() {
1266   ResourceMark rm;
1267 
1268 #ifndef PRODUCT
1269   if (trace_opto_pipelining()) {
1270     tty->print("\n---- Start GlobalCodeMotion ----\n");
1271   }
1272 #endif
1273 
1274   // Initialize the node to block mapping for things on the proj_list
1275   for (uint i = 0; i < _matcher.number_of_projections(); i++) {
1276     unmap_node_from_block(_matcher.get_projection(i));
1277   }
1278 
1279   // Set the basic block for Nodes pinned into blocks
1280   Arena* arena = Thread::current()->resource_area();
1281   VectorSet visited(arena);
1282   schedule_pinned_nodes(visited);
1283 
1284   // Find the earliest Block any instruction can be placed in.  Some
1285   // instructions are pinned into Blocks.  Unpinned instructions can
1286   // appear in last block in which all their inputs occur.
1287   visited.Clear();
1288   Node_List stack(arena);
1289   // Pre-grow the list
1290   stack.map((C->live_nodes() >> 1) + 16, NULL);
1291   if (!schedule_early(visited, stack)) {
1292     // Bailout without retry
1293     C->record_method_not_compilable("early schedule failed");
1294     return;
1295   }
1296 
1297   // Build Def-Use edges.
1298   // Compute the latency information (via backwards walk) for all the
1299   // instructions in the graph
1300   _node_latency = new GrowableArray<uint>(); // resource_area allocation
1301 
1302   if (C->do_scheduling()) {
1303     compute_latencies_backwards(visited, stack);
1304   }
1305 
1306   // Now schedule all codes as LATE as possible.  This is the LCA in the
1307   // dominator tree of all USES of a value.  Pick the block with the least
1308   // loop nesting depth that is lowest in the dominator tree.
1309   // ( visited.Clear() called in schedule_late()->Node_Backward_Iterator() )
1310   schedule_late(visited, stack);
1311   if (C->failing()) {
1312     // schedule_late fails only when graph is incorrect.
1313     assert(!VerifyGraphEdges, "verification should have failed");
1314     return;
1315   }
1316 
1317 #ifndef PRODUCT
1318   if (trace_opto_pipelining()) {
1319     tty->print("\n---- Detect implicit null checks ----\n");
1320   }
1321 #endif
1322 
1323   // Detect implicit-null-check opportunities.  Basically, find NULL checks
1324   // with suitable memory ops nearby.  Use the memory op to do the NULL check.
1325   // I can generate a memory op if there is not one nearby.
1326   if (C->is_method_compilation()) {
1327     // By reversing the loop direction we get a very minor gain on mpegaudio.
1328     // Feel free to revert to a forward loop for clarity.
1329     // for( int i=0; i < (int)matcher._null_check_tests.size(); i+=2 ) {
1330     for (int i = _matcher._null_check_tests.size() - 2; i >= 0; i -= 2) {
1331       Node* proj = _matcher._null_check_tests[i];
1332       Node* val  = _matcher._null_check_tests[i + 1];
1333       Block* block = get_block_for_node(proj);
1334       implicit_null_check(block, proj, val, C->allowed_deopt_reasons());
1335       // The implicit_null_check will only perform the transformation
1336       // if the null branch is truly uncommon, *and* it leads to an
1337       // uncommon trap.  Combined with the too_many_traps guards
1338       // above, this prevents SEGV storms reported in 6366351,
1339       // by recompiling offending methods without this optimization.
1340     }
1341   }
1342 
1343 #ifndef PRODUCT
1344   if (trace_opto_pipelining()) {
1345     tty->print("\n---- Start Local Scheduling ----\n");
1346   }
1347 #endif
1348 
1349   // Schedule locally.  Right now a simple topological sort.
1350   // Later, do a real latency aware scheduler.
1351   GrowableArray<int> ready_cnt(C->unique(), C->unique(), -1);
1352   visited.Clear();
1353   for (uint i = 0; i < number_of_blocks(); i++) {
1354     Block* block = get_block(i);
1355     if (!schedule_local(block, ready_cnt, visited)) {
1356       if (!C->failure_reason_is(C2Compiler::retry_no_subsuming_loads())) {
1357         C->record_method_not_compilable("local schedule failed");
1358       }
1359       return;
1360     }
1361   }
1362 
1363   // If we inserted any instructions between a Call and his CatchNode,
1364   // clone the instructions on all paths below the Catch.
1365   for (uint i = 0; i < number_of_blocks(); i++) {
1366     Block* block = get_block(i);
1367     call_catch_cleanup(block);
1368   }
1369 
1370 #ifndef PRODUCT
1371   if (trace_opto_pipelining()) {
1372     tty->print("\n---- After GlobalCodeMotion ----\n");
1373     for (uint i = 0; i < number_of_blocks(); i++) {
1374       Block* block = get_block(i);
1375       block->dump();
1376     }
1377   }
1378 #endif
1379   // Dead.
1380   _node_latency = (GrowableArray<uint> *)((intptr_t)0xdeadbeef);
1381 }
1382 
1383 bool PhaseCFG::do_global_code_motion() {
1384 
1385   build_dominator_tree();
1386   if (C->failing()) {
1387     return false;
1388   }
1389 
1390   NOT_PRODUCT( C->verify_graph_edges(); )
1391 
1392   estimate_block_frequency();
1393 
1394   global_code_motion();
1395 
1396   if (C->failing()) {
1397     return false;
1398   }
1399 
1400   return true;
1401 }
1402 
1403 //------------------------------Estimate_Block_Frequency-----------------------
1404 // Estimate block frequencies based on IfNode probabilities.
1405 void PhaseCFG::estimate_block_frequency() {
1406 
1407   // Force conditional branches leading to uncommon traps to be unlikely,
1408   // not because we get to the uncommon_trap with less relative frequency,
1409   // but because an uncommon_trap typically causes a deopt, so we only get
1410   // there once.
1411   if (C->do_freq_based_layout()) {
1412     Block_List worklist;
1413     Block* root_blk = get_block(0);
1414     for (uint i = 1; i < root_blk->num_preds(); i++) {
1415       Block *pb = get_block_for_node(root_blk->pred(i));
1416       if (pb->has_uncommon_code()) {
1417         worklist.push(pb);
1418       }
1419     }
1420     while (worklist.size() > 0) {
1421       Block* uct = worklist.pop();
1422       if (uct == get_root_block()) {
1423         continue;
1424       }
1425       for (uint i = 1; i < uct->num_preds(); i++) {
1426         Block *pb = get_block_for_node(uct->pred(i));
1427         if (pb->_num_succs == 1) {
1428           worklist.push(pb);
1429         } else if (pb->num_fall_throughs() == 2) {
1430           pb->update_uncommon_branch(uct);
1431         }
1432       }
1433     }
1434   }
1435 
1436   // Create the loop tree and calculate loop depth.
1437   _root_loop = create_loop_tree();
1438   _root_loop->compute_loop_depth(0);
1439 
1440   // Compute block frequency of each block, relative to a single loop entry.
1441   _root_loop->compute_freq();
1442 
1443   // Adjust all frequencies to be relative to a single method entry
1444   _root_loop->_freq = 1.0;
1445   _root_loop->scale_freq();
1446 
1447   // Save outmost loop frequency for LRG frequency threshold
1448   _outer_loop_frequency = _root_loop->outer_loop_freq();
1449 
1450   // force paths ending at uncommon traps to be infrequent
1451   if (!C->do_freq_based_layout()) {
1452     Block_List worklist;
1453     Block* root_blk = get_block(0);
1454     for (uint i = 1; i < root_blk->num_preds(); i++) {
1455       Block *pb = get_block_for_node(root_blk->pred(i));
1456       if (pb->has_uncommon_code()) {
1457         worklist.push(pb);
1458       }
1459     }
1460     while (worklist.size() > 0) {
1461       Block* uct = worklist.pop();
1462       uct->_freq = PROB_MIN;
1463       for (uint i = 1; i < uct->num_preds(); i++) {
1464         Block *pb = get_block_for_node(uct->pred(i));
1465         if (pb->_num_succs == 1 && pb->_freq > PROB_MIN) {
1466           worklist.push(pb);
1467         }
1468       }
1469     }
1470   }
1471 
1472 #ifdef ASSERT
1473   for (uint i = 0; i < number_of_blocks(); i++) {
1474     Block* b = get_block(i);
1475     assert(b->_freq >= MIN_BLOCK_FREQUENCY, "Register Allocator requires meaningful block frequency");
1476   }
1477 #endif
1478 
1479 #ifndef PRODUCT
1480   if (PrintCFGBlockFreq) {
1481     tty->print_cr("CFG Block Frequencies");
1482     _root_loop->dump_tree();
1483     if (Verbose) {
1484       tty->print_cr("PhaseCFG dump");
1485       dump();
1486       tty->print_cr("Node dump");
1487       _root->dump(99999);
1488     }
1489   }
1490 #endif
1491 }
1492 
1493 //----------------------------create_loop_tree--------------------------------
1494 // Create a loop tree from the CFG
1495 CFGLoop* PhaseCFG::create_loop_tree() {
1496 
1497 #ifdef ASSERT
1498   assert(get_block(0) == get_root_block(), "first block should be root block");
1499   for (uint i = 0; i < number_of_blocks(); i++) {
1500     Block* block = get_block(i);
1501     // Check that _loop field are clear...we could clear them if not.
1502     assert(block->_loop == NULL, "clear _loop expected");
1503     // Sanity check that the RPO numbering is reflected in the _blocks array.
1504     // It doesn't have to be for the loop tree to be built, but if it is not,
1505     // then the blocks have been reordered since dom graph building...which
1506     // may question the RPO numbering
1507     assert(block->_rpo == i, "unexpected reverse post order number");
1508   }
1509 #endif
1510 
1511   int idct = 0;
1512   CFGLoop* root_loop = new CFGLoop(idct++);
1513 
1514   Block_List worklist;
1515 
1516   // Assign blocks to loops
1517   for(uint i = number_of_blocks() - 1; i > 0; i-- ) { // skip Root block
1518     Block* block = get_block(i);
1519 
1520     if (block->head()->is_Loop()) {
1521       Block* loop_head = block;
1522       assert(loop_head->num_preds() - 1 == 2, "loop must have 2 predecessors");
1523       Node* tail_n = loop_head->pred(LoopNode::LoopBackControl);
1524       Block* tail = get_block_for_node(tail_n);
1525 
1526       // Defensively filter out Loop nodes for non-single-entry loops.
1527       // For all reasonable loops, the head occurs before the tail in RPO.
1528       if (i <= tail->_rpo) {
1529 
1530         // The tail and (recursive) predecessors of the tail
1531         // are made members of a new loop.
1532 
1533         assert(worklist.size() == 0, "nonempty worklist");
1534         CFGLoop* nloop = new CFGLoop(idct++);
1535         assert(loop_head->_loop == NULL, "just checking");
1536         loop_head->_loop = nloop;
1537         // Add to nloop so push_pred() will skip over inner loops
1538         nloop->add_member(loop_head);
1539         nloop->push_pred(loop_head, LoopNode::LoopBackControl, worklist, this);
1540 
1541         while (worklist.size() > 0) {
1542           Block* member = worklist.pop();
1543           if (member != loop_head) {
1544             for (uint j = 1; j < member->num_preds(); j++) {
1545               nloop->push_pred(member, j, worklist, this);
1546             }
1547           }
1548         }
1549       }
1550     }
1551   }
1552 
1553   // Create a member list for each loop consisting
1554   // of both blocks and (immediate child) loops.
1555   for (uint i = 0; i < number_of_blocks(); i++) {
1556     Block* block = get_block(i);
1557     CFGLoop* lp = block->_loop;
1558     if (lp == NULL) {
1559       // Not assigned to a loop. Add it to the method's pseudo loop.
1560       block->_loop = root_loop;
1561       lp = root_loop;
1562     }
1563     if (lp == root_loop || block != lp->head()) { // loop heads are already members
1564       lp->add_member(block);
1565     }
1566     if (lp != root_loop) {
1567       if (lp->parent() == NULL) {
1568         // Not a nested loop. Make it a child of the method's pseudo loop.
1569         root_loop->add_nested_loop(lp);
1570       }
1571       if (block == lp->head()) {
1572         // Add nested loop to member list of parent loop.
1573         lp->parent()->add_member(lp);
1574       }
1575     }
1576   }
1577 
1578   return root_loop;
1579 }
1580 
1581 //------------------------------push_pred--------------------------------------
1582 void CFGLoop::push_pred(Block* blk, int i, Block_List& worklist, PhaseCFG* cfg) {
1583   Node* pred_n = blk->pred(i);
1584   Block* pred = cfg->get_block_for_node(pred_n);
1585   CFGLoop *pred_loop = pred->_loop;
1586   if (pred_loop == NULL) {
1587     // Filter out blocks for non-single-entry loops.
1588     // For all reasonable loops, the head occurs before the tail in RPO.
1589     if (pred->_rpo > head()->_rpo) {
1590       pred->_loop = this;
1591       worklist.push(pred);
1592     }
1593   } else if (pred_loop != this) {
1594     // Nested loop.
1595     while (pred_loop->_parent != NULL && pred_loop->_parent != this) {
1596       pred_loop = pred_loop->_parent;
1597     }
1598     // Make pred's loop be a child
1599     if (pred_loop->_parent == NULL) {
1600       add_nested_loop(pred_loop);
1601       // Continue with loop entry predecessor.
1602       Block* pred_head = pred_loop->head();
1603       assert(pred_head->num_preds() - 1 == 2, "loop must have 2 predecessors");
1604       assert(pred_head != head(), "loop head in only one loop");
1605       push_pred(pred_head, LoopNode::EntryControl, worklist, cfg);
1606     } else {
1607       assert(pred_loop->_parent == this && _parent == NULL, "just checking");
1608     }
1609   }
1610 }
1611 
1612 //------------------------------add_nested_loop--------------------------------
1613 // Make cl a child of the current loop in the loop tree.
1614 void CFGLoop::add_nested_loop(CFGLoop* cl) {
1615   assert(_parent == NULL, "no parent yet");
1616   assert(cl != this, "not my own parent");
1617   cl->_parent = this;
1618   CFGLoop* ch = _child;
1619   if (ch == NULL) {
1620     _child = cl;
1621   } else {
1622     while (ch->_sibling != NULL) { ch = ch->_sibling; }
1623     ch->_sibling = cl;
1624   }
1625 }
1626 
1627 //------------------------------compute_loop_depth-----------------------------
1628 // Store the loop depth in each CFGLoop object.
1629 // Recursively walk the children to do the same for them.
1630 void CFGLoop::compute_loop_depth(int depth) {
1631   _depth = depth;
1632   CFGLoop* ch = _child;
1633   while (ch != NULL) {
1634     ch->compute_loop_depth(depth + 1);
1635     ch = ch->_sibling;
1636   }
1637 }
1638 
1639 //------------------------------compute_freq-----------------------------------
1640 // Compute the frequency of each block and loop, relative to a single entry
1641 // into the dominating loop head.
1642 void CFGLoop::compute_freq() {
1643   // Bottom up traversal of loop tree (visit inner loops first.)
1644   // Set loop head frequency to 1.0, then transitively
1645   // compute frequency for all successors in the loop,
1646   // as well as for each exit edge.  Inner loops are
1647   // treated as single blocks with loop exit targets
1648   // as the successor blocks.
1649 
1650   // Nested loops first
1651   CFGLoop* ch = _child;
1652   while (ch != NULL) {
1653     ch->compute_freq();
1654     ch = ch->_sibling;
1655   }
1656   assert (_members.length() > 0, "no empty loops");
1657   Block* hd = head();
1658   hd->_freq = 1.0f;
1659   for (int i = 0; i < _members.length(); i++) {
1660     CFGElement* s = _members.at(i);
1661     float freq = s->_freq;
1662     if (s->is_block()) {
1663       Block* b = s->as_Block();
1664       for (uint j = 0; j < b->_num_succs; j++) {
1665         Block* sb = b->_succs[j];
1666         update_succ_freq(sb, freq * b->succ_prob(j));
1667       }
1668     } else {
1669       CFGLoop* lp = s->as_CFGLoop();
1670       assert(lp->_parent == this, "immediate child");
1671       for (int k = 0; k < lp->_exits.length(); k++) {
1672         Block* eb = lp->_exits.at(k).get_target();
1673         float prob = lp->_exits.at(k).get_prob();
1674         update_succ_freq(eb, freq * prob);
1675       }
1676     }
1677   }
1678 
1679   // For all loops other than the outer, "method" loop,
1680   // sum and normalize the exit probability. The "method" loop
1681   // should keep the initial exit probability of 1, so that
1682   // inner blocks do not get erroneously scaled.
1683   if (_depth != 0) {
1684     // Total the exit probabilities for this loop.
1685     float exits_sum = 0.0f;
1686     for (int i = 0; i < _exits.length(); i++) {
1687       exits_sum += _exits.at(i).get_prob();
1688     }
1689 
1690     // Normalize the exit probabilities. Until now, the
1691     // probabilities estimate the possibility of exit per
1692     // a single loop iteration; afterward, they estimate
1693     // the probability of exit per loop entry.
1694     for (int i = 0; i < _exits.length(); i++) {
1695       Block* et = _exits.at(i).get_target();
1696       float new_prob = 0.0f;
1697       if (_exits.at(i).get_prob() > 0.0f) {
1698         new_prob = _exits.at(i).get_prob() / exits_sum;
1699       }
1700       BlockProbPair bpp(et, new_prob);
1701       _exits.at_put(i, bpp);
1702     }
1703 
1704     // Save the total, but guard against unreasonable probability,
1705     // as the value is used to estimate the loop trip count.
1706     // An infinite trip count would blur relative block
1707     // frequencies.
1708     if (exits_sum > 1.0f) exits_sum = 1.0;
1709     if (exits_sum < PROB_MIN) exits_sum = PROB_MIN;
1710     _exit_prob = exits_sum;
1711   }
1712 }
1713 
1714 //------------------------------succ_prob-------------------------------------
1715 // Determine the probability of reaching successor 'i' from the receiver block.
1716 float Block::succ_prob(uint i) {
1717   int eidx = end_idx();
1718   Node *n = get_node(eidx);  // Get ending Node
1719 
1720   int op = n->Opcode();
1721   if (n->is_Mach()) {
1722     if (n->is_MachNullCheck()) {
1723       // Can only reach here if called after lcm. The original Op_If is gone,
1724       // so we attempt to infer the probability from one or both of the
1725       // successor blocks.
1726       assert(_num_succs == 2, "expecting 2 successors of a null check");
1727       // If either successor has only one predecessor, then the
1728       // probability estimate can be derived using the
1729       // relative frequency of the successor and this block.
1730       if (_succs[i]->num_preds() == 2) {
1731         return _succs[i]->_freq / _freq;
1732       } else if (_succs[1-i]->num_preds() == 2) {
1733         return 1 - (_succs[1-i]->_freq / _freq);
1734       } else {
1735         // Estimate using both successor frequencies
1736         float freq = _succs[i]->_freq;
1737         return freq / (freq + _succs[1-i]->_freq);
1738       }
1739     }
1740     op = n->as_Mach()->ideal_Opcode();
1741   }
1742 
1743 
1744   // Switch on branch type
1745   switch( op ) {
1746   case Op_CountedLoopEnd:
1747   case Op_If: {
1748     assert (i < 2, "just checking");
1749     // Conditionals pass on only part of their frequency
1750     float prob  = n->as_MachIf()->_prob;
1751     assert(prob >= 0.0 && prob <= 1.0, "out of range probability");
1752     // If succ[i] is the FALSE branch, invert path info
1753     if( get_node(i + eidx + 1)->Opcode() == Op_IfFalse ) {
1754       return 1.0f - prob; // not taken
1755     } else {
1756       return prob; // taken
1757     }
1758   }
1759 
1760   case Op_Jump:
1761     // Divide the frequency between all successors evenly
1762     return 1.0f/_num_succs;
1763 
1764   case Op_Catch: {
1765     const CatchProjNode *ci = get_node(i + eidx + 1)->as_CatchProj();
1766     if (ci->_con == CatchProjNode::fall_through_index) {
1767       // Fall-thru path gets the lion's share.
1768       return 1.0f - PROB_UNLIKELY_MAG(5)*_num_succs;
1769     } else {
1770       // Presume exceptional paths are equally unlikely
1771       return PROB_UNLIKELY_MAG(5);
1772     }
1773   }
1774 
1775   case Op_Root:
1776   case Op_Goto:
1777     // Pass frequency straight thru to target
1778     return 1.0f;
1779 
1780   case Op_NeverBranch:
1781     return 0.0f;
1782 
1783   case Op_TailCall:
1784   case Op_TailJump:
1785   case Op_Return:
1786   case Op_Halt:
1787   case Op_Rethrow:
1788     // Do not push out freq to root block
1789     return 0.0f;
1790 
1791   default:
1792     ShouldNotReachHere();
1793   }
1794 
1795   return 0.0f;
1796 }
1797 
1798 //------------------------------num_fall_throughs-----------------------------
1799 // Return the number of fall-through candidates for a block
1800 int Block::num_fall_throughs() {
1801   int eidx = end_idx();
1802   Node *n = get_node(eidx);  // Get ending Node
1803 
1804   int op = n->Opcode();
1805   if (n->is_Mach()) {
1806     if (n->is_MachNullCheck()) {
1807       // In theory, either side can fall-thru, for simplicity sake,
1808       // let's say only the false branch can now.
1809       return 1;
1810     }
1811     op = n->as_Mach()->ideal_Opcode();
1812   }
1813 
1814   // Switch on branch type
1815   switch( op ) {
1816   case Op_CountedLoopEnd:
1817   case Op_If:
1818     return 2;
1819 
1820   case Op_Root:
1821   case Op_Goto:
1822     return 1;
1823 
1824   case Op_Catch: {
1825     for (uint i = 0; i < _num_succs; i++) {
1826       const CatchProjNode *ci = get_node(i + eidx + 1)->as_CatchProj();
1827       if (ci->_con == CatchProjNode::fall_through_index) {
1828         return 1;
1829       }
1830     }
1831     return 0;
1832   }
1833 
1834   case Op_Jump:
1835   case Op_NeverBranch:
1836   case Op_TailCall:
1837   case Op_TailJump:
1838   case Op_Return:
1839   case Op_Halt:
1840   case Op_Rethrow:
1841     return 0;
1842 
1843   default:
1844     ShouldNotReachHere();
1845   }
1846 
1847   return 0;
1848 }
1849 
1850 //------------------------------succ_fall_through-----------------------------
1851 // Return true if a specific successor could be fall-through target.
1852 bool Block::succ_fall_through(uint i) {
1853   int eidx = end_idx();
1854   Node *n = get_node(eidx);  // Get ending Node
1855 
1856   int op = n->Opcode();
1857   if (n->is_Mach()) {
1858     if (n->is_MachNullCheck()) {
1859       // In theory, either side can fall-thru, for simplicity sake,
1860       // let's say only the false branch can now.
1861       return get_node(i + eidx + 1)->Opcode() == Op_IfFalse;
1862     }
1863     op = n->as_Mach()->ideal_Opcode();
1864   }
1865 
1866   // Switch on branch type
1867   switch( op ) {
1868   case Op_CountedLoopEnd:
1869   case Op_If:
1870   case Op_Root:
1871   case Op_Goto:
1872     return true;
1873 
1874   case Op_Catch: {
1875     const CatchProjNode *ci = get_node(i + eidx + 1)->as_CatchProj();
1876     return ci->_con == CatchProjNode::fall_through_index;
1877   }
1878 
1879   case Op_Jump:
1880   case Op_NeverBranch:
1881   case Op_TailCall:
1882   case Op_TailJump:
1883   case Op_Return:
1884   case Op_Halt:
1885   case Op_Rethrow:
1886     return false;
1887 
1888   default:
1889     ShouldNotReachHere();
1890   }
1891 
1892   return false;
1893 }
1894 
1895 //------------------------------update_uncommon_branch------------------------
1896 // Update the probability of a two-branch to be uncommon
1897 void Block::update_uncommon_branch(Block* ub) {
1898   int eidx = end_idx();
1899   Node *n = get_node(eidx);  // Get ending Node
1900 
1901   int op = n->as_Mach()->ideal_Opcode();
1902 
1903   assert(op == Op_CountedLoopEnd || op == Op_If, "must be a If");
1904   assert(num_fall_throughs() == 2, "must be a two way branch block");
1905 
1906   // Which successor is ub?
1907   uint s;
1908   for (s = 0; s <_num_succs; s++) {
1909     if (_succs[s] == ub) break;
1910   }
1911   assert(s < 2, "uncommon successor must be found");
1912 
1913   // If ub is the true path, make the proability small, else
1914   // ub is the false path, and make the probability large
1915   bool invert = (get_node(s + eidx + 1)->Opcode() == Op_IfFalse);
1916 
1917   // Get existing probability
1918   float p = n->as_MachIf()->_prob;
1919 
1920   if (invert) p = 1.0 - p;
1921   if (p > PROB_MIN) {
1922     p = PROB_MIN;
1923   }
1924   if (invert) p = 1.0 - p;
1925 
1926   n->as_MachIf()->_prob = p;
1927 }
1928 
1929 //------------------------------update_succ_freq-------------------------------
1930 // Update the appropriate frequency associated with block 'b', a successor of
1931 // a block in this loop.
1932 void CFGLoop::update_succ_freq(Block* b, float freq) {
1933   if (b->_loop == this) {
1934     if (b == head()) {
1935       // back branch within the loop
1936       // Do nothing now, the loop carried frequency will be
1937       // adjust later in scale_freq().
1938     } else {
1939       // simple branch within the loop
1940       b->_freq += freq;
1941     }
1942   } else if (!in_loop_nest(b)) {
1943     // branch is exit from this loop
1944     BlockProbPair bpp(b, freq);
1945     _exits.append(bpp);
1946   } else {
1947     // branch into nested loop
1948     CFGLoop* ch = b->_loop;
1949     ch->_freq += freq;
1950   }
1951 }
1952 
1953 //------------------------------in_loop_nest-----------------------------------
1954 // Determine if block b is in the receiver's loop nest.
1955 bool CFGLoop::in_loop_nest(Block* b) {
1956   int depth = _depth;
1957   CFGLoop* b_loop = b->_loop;
1958   int b_depth = b_loop->_depth;
1959   if (depth == b_depth) {
1960     return true;
1961   }
1962   while (b_depth > depth) {
1963     b_loop = b_loop->_parent;
1964     b_depth = b_loop->_depth;
1965   }
1966   return b_loop == this;
1967 }
1968 
1969 //------------------------------scale_freq-------------------------------------
1970 // Scale frequency of loops and blocks by trip counts from outer loops
1971 // Do a top down traversal of loop tree (visit outer loops first.)
1972 void CFGLoop::scale_freq() {
1973   float loop_freq = _freq * trip_count();
1974   _freq = loop_freq;
1975   for (int i = 0; i < _members.length(); i++) {
1976     CFGElement* s = _members.at(i);
1977     float block_freq = s->_freq * loop_freq;
1978     if (g_isnan(block_freq) || block_freq < MIN_BLOCK_FREQUENCY)
1979       block_freq = MIN_BLOCK_FREQUENCY;
1980     s->_freq = block_freq;
1981   }
1982   CFGLoop* ch = _child;
1983   while (ch != NULL) {
1984     ch->scale_freq();
1985     ch = ch->_sibling;
1986   }
1987 }
1988 
1989 // Frequency of outer loop
1990 float CFGLoop::outer_loop_freq() const {
1991   if (_child != NULL) {
1992     return _child->_freq;
1993   }
1994   return _freq;
1995 }
1996 
1997 #ifndef PRODUCT
1998 //------------------------------dump_tree--------------------------------------
1999 void CFGLoop::dump_tree() const {
2000   dump();
2001   if (_child != NULL)   _child->dump_tree();
2002   if (_sibling != NULL) _sibling->dump_tree();
2003 }
2004 
2005 //------------------------------dump-------------------------------------------
2006 void CFGLoop::dump() const {
2007   for (int i = 0; i < _depth; i++) tty->print("   ");
2008   tty->print("%s: %d  trip_count: %6.0f freq: %6.0f\n",
2009              _depth == 0 ? "Method" : "Loop", _id, trip_count(), _freq);
2010   for (int i = 0; i < _depth; i++) tty->print("   ");
2011   tty->print("         members:");
2012   int k = 0;
2013   for (int i = 0; i < _members.length(); i++) {
2014     if (k++ >= 6) {
2015       tty->print("\n              ");
2016       for (int j = 0; j < _depth+1; j++) tty->print("   ");
2017       k = 0;
2018     }
2019     CFGElement *s = _members.at(i);
2020     if (s->is_block()) {
2021       Block *b = s->as_Block();
2022       tty->print(" B%d(%6.3f)", b->_pre_order, b->_freq);
2023     } else {
2024       CFGLoop* lp = s->as_CFGLoop();
2025       tty->print(" L%d(%6.3f)", lp->_id, lp->_freq);
2026     }
2027   }
2028   tty->print("\n");
2029   for (int i = 0; i < _depth; i++) tty->print("   ");
2030   tty->print("         exits:  ");
2031   k = 0;
2032   for (int i = 0; i < _exits.length(); i++) {
2033     if (k++ >= 7) {
2034       tty->print("\n              ");
2035       for (int j = 0; j < _depth+1; j++) tty->print("   ");
2036       k = 0;
2037     }
2038     Block *blk = _exits.at(i).get_target();
2039     float prob = _exits.at(i).get_prob();
2040     tty->print(" ->%d@%d%%", blk->_pre_order, (int)(prob*100));
2041   }
2042   tty->print("\n");
2043 }
2044 #endif