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