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