40 _bbs.map(n->_idx, b);
41 b->add_inst(n);
42
43 // After Matching, nearly any old Node may have projections trailing it.
44 // These are usually machine-dependent flags. In any case, they might
45 // float to another block below this one. Move them up.
46 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
47 Node* use = n->fast_out(i);
48 if (use->is_Proj()) {
49 Block* buse = _bbs[use->_idx];
50 if (buse != b) { // In wrong block?
51 if (buse != NULL)
52 buse->find_remove(use); // Remove from wrong block
53 _bbs.map(use->_idx, b); // Re-insert in this block
54 b->add_inst(use);
55 }
56 }
57 }
58 }
59
60
61 //------------------------------schedule_pinned_nodes--------------------------
62 // Set the basic block for Nodes pinned into blocks
63 void PhaseCFG::schedule_pinned_nodes( VectorSet &visited ) {
64 // Allocate node stack of size C->unique()+8 to avoid frequent realloc
65 GrowableArray <Node *> spstack(C->unique()+8);
66 spstack.push(_root);
67 while ( spstack.is_nonempty() ) {
68 Node *n = spstack.pop();
69 if( !visited.test_set(n->_idx) ) { // Test node and flag it as visited
70 if( n->pinned() && !_bbs.lookup(n->_idx) ) { // Pinned? Nail it down!
71 Node *input = n->in(0);
72 assert( input, "pinned Node must have Control" );
73 while( !input->is_block_start() )
74 input = input->in(0);
75 Block *b = _bbs[input->_idx]; // Basic block of controlling input
76 schedule_node_into_block(n, b);
77 }
78 for( int i = n->req() - 1; i >= 0; --i ) { // For all inputs
79 if( n->in(i) != NULL )
80 spstack.push(n->in(i));
81 }
82 }
83 }
84 }
85
86 #ifdef ASSERT
87 // Assert that new input b2 is dominated by all previous inputs.
88 // Check this by by seeing that it is dominated by b1, the deepest
89 // input observed until b2.
90 static void assert_dom(Block* b1, Block* b2, Node* n, Block_Array &bbs) {
91 if (b1 == NULL) return;
92 assert(b1->_dom_depth < b2->_dom_depth, "sanity");
141 // which all their inputs occur.
142 bool PhaseCFG::schedule_early(VectorSet &visited, Node_List &roots) {
143 // Allocate stack with enough space to avoid frequent realloc
144 Node_Stack nstack(roots.Size() + 8); // (unique >> 1) + 24 from Java2D stats
145 // roots.push(_root); _root will be processed among C->top() inputs
146 roots.push(C->top());
147 visited.set(C->top()->_idx);
148
149 while (roots.size() != 0) {
150 // Use local variables nstack_top_n & nstack_top_i to cache values
151 // on stack's top.
152 Node *nstack_top_n = roots.pop();
153 uint nstack_top_i = 0;
154 //while_nstack_nonempty:
155 while (true) {
156 // Get parent node and next input's index from stack's top.
157 Node *n = nstack_top_n;
158 uint i = nstack_top_i;
159
160 if (i == 0) {
161 // Special control input processing.
162 // While I am here, go ahead and look for Nodes which are taking control
163 // from a is_block_proj Node. After I inserted RegionNodes to make proper
164 // blocks, the control at a is_block_proj more properly comes from the
165 // Region being controlled by the block_proj Node.
166 const Node *in0 = n->in(0);
167 if (in0 != NULL) { // Control-dependent?
168 const Node *p = in0->is_block_proj();
169 if (p != NULL && p != n) { // Control from a block projection?
170 // Find trailing Region
171 Block *pb = _bbs[in0->_idx]; // Block-projection already has basic block
172 uint j = 0;
173 if (pb->_num_succs != 1) { // More then 1 successor?
174 // Search for successor
175 uint max = pb->_nodes.size();
176 assert( max > 1, "" );
177 uint start = max - pb->_num_succs;
178 // Find which output path belongs to projection
179 for (j = start; j < max; j++) {
180 if( pb->_nodes[j] == in0 )
181 break;
182 }
183 assert( j < max, "must find" );
184 // Change control to match head of successor basic block
185 j -= start;
186 }
187 n->set_req(0, pb->_succs[j]->head());
188 }
189 } else { // n->in(0) == NULL
190 if (n->req() == 1) { // This guy is a constant with NO inputs?
191 n->set_req(0, _root);
192 }
193 }
194 }
195
196 // First, visit all inputs and force them to get a block. If an
197 // input is already in a block we quit following inputs (to avoid
198 // cycles). Instead we put that Node on a worklist to be handled
199 // later (since IT'S inputs may not have a block yet).
200 bool done = true; // Assume all n's inputs will be processed
201 while (i < n->len()) { // For all inputs
202 Node *in = n->in(i); // Get input
203 ++i;
204 if (in == NULL) continue; // Ignore NULL, missing inputs
205 int is_visited = visited.test_set(in->_idx);
206 if (!_bbs.lookup(in->_idx)) { // Missing block selection?
207 if (is_visited) {
208 // assert( !visited.test(in->_idx), "did not schedule early" );
209 return false;
210 }
211 nstack.push(n, i); // Save parent node and next input's index.
212 nstack_top_n = in; // Process current input now.
213 nstack_top_i = 0;
214 done = false; // Not all n's inputs processed.
215 break; // continue while_nstack_nonempty;
216 } else if (!is_visited) { // Input not yet visited?
217 roots.push(in); // Visit this guy later, using worklist
218 }
219 }
220 if (done) {
221 // All of n's inputs have been processed, complete post-processing.
222
223 // Some instructions are pinned into a block. These include Region,
224 // Phi, Start, Return, and other control-dependent instructions and
225 // any projections which depend on them.
226 if (!n->pinned()) {
227 // Set earliest legal block.
228 _bbs.map(n->_idx, find_deepest_input(n, _bbs));
229 }
230
231 if (nstack.is_empty()) {
232 // Finished all nodes on stack.
233 // Process next node on the worklist 'roots'.
234 break;
235 }
236 // Get saved parent node and next input's index.
237 nstack_top_n = nstack.node();
238 nstack_top_i = nstack.index();
239 nstack.pop();
240 } // if (done)
241 } // while (true)
242 } // while (roots.size() != 0)
243 return true;
244 }
245
246 //------------------------------dom_lca----------------------------------------
247 // Find least common ancestor in dominator tree
248 // LCA is a current notion of LCA, to be raised above 'this'.
|
40 _bbs.map(n->_idx, b);
41 b->add_inst(n);
42
43 // After Matching, nearly any old Node may have projections trailing it.
44 // These are usually machine-dependent flags. In any case, they might
45 // float to another block below this one. Move them up.
46 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
47 Node* use = n->fast_out(i);
48 if (use->is_Proj()) {
49 Block* buse = _bbs[use->_idx];
50 if (buse != b) { // In wrong block?
51 if (buse != NULL)
52 buse->find_remove(use); // Remove from wrong block
53 _bbs.map(use->_idx, b); // Re-insert in this block
54 b->add_inst(use);
55 }
56 }
57 }
58 }
59
60 //----------------------------replace_block_proj_ctrl-------------------------
61 // Nodes that have is_block_proj() nodes as their control need to use
62 // the appropriate Region for their actual block as their control since
63 // the projection will be in a predecessor block.
64 void PhaseCFG::replace_block_proj_ctrl( Node *n ) {
65 const Node *in0 = n->in(0);
66 assert(in0 != NULL, "Only control-dependent");
67 const Node *p = in0->is_block_proj();
68 if (p != NULL && p != n) { // Control from a block projection?
69 assert(!n->pinned() || n->is_SafePointScalarObject(), "only SafePointScalarObject pinned node is expected here");
70 // Find trailing Region
71 Block *pb = _bbs[in0->_idx]; // Block-projection already has basic block
72 uint j = 0;
73 if (pb->_num_succs != 1) { // More then 1 successor?
74 // Search for successor
75 uint max = pb->_nodes.size();
76 assert( max > 1, "" );
77 uint start = max - pb->_num_succs;
78 // Find which output path belongs to projection
79 for (j = start; j < max; j++) {
80 if( pb->_nodes[j] == in0 )
81 break;
82 }
83 assert( j < max, "must find" );
84 // Change control to match head of successor basic block
85 j -= start;
86 }
87 n->set_req(0, pb->_succs[j]->head());
88 }
89 }
90
91
92 //------------------------------schedule_pinned_nodes--------------------------
93 // Set the basic block for Nodes pinned into blocks
94 void PhaseCFG::schedule_pinned_nodes( VectorSet &visited ) {
95 // Allocate node stack of size C->unique()+8 to avoid frequent realloc
96 GrowableArray <Node *> spstack(C->unique()+8);
97 spstack.push(_root);
98 while ( spstack.is_nonempty() ) {
99 Node *n = spstack.pop();
100 if( !visited.test_set(n->_idx) ) { // Test node and flag it as visited
101 if( n->pinned() && !_bbs.lookup(n->_idx) ) { // Pinned? Nail it down!
102 assert( n->in(0), "pinned Node must have Control" );
103 // Before setting block replace block_proj control edge
104 replace_block_proj_ctrl(n);
105 Node *input = n->in(0);
106 while( !input->is_block_start() )
107 input = input->in(0);
108 Block *b = _bbs[input->_idx]; // Basic block of controlling input
109 schedule_node_into_block(n, b);
110 }
111 for( int i = n->req() - 1; i >= 0; --i ) { // For all inputs
112 if( n->in(i) != NULL )
113 spstack.push(n->in(i));
114 }
115 }
116 }
117 }
118
119 #ifdef ASSERT
120 // Assert that new input b2 is dominated by all previous inputs.
121 // Check this by by seeing that it is dominated by b1, the deepest
122 // input observed until b2.
123 static void assert_dom(Block* b1, Block* b2, Node* n, Block_Array &bbs) {
124 if (b1 == NULL) return;
125 assert(b1->_dom_depth < b2->_dom_depth, "sanity");
174 // which all their inputs occur.
175 bool PhaseCFG::schedule_early(VectorSet &visited, Node_List &roots) {
176 // Allocate stack with enough space to avoid frequent realloc
177 Node_Stack nstack(roots.Size() + 8); // (unique >> 1) + 24 from Java2D stats
178 // roots.push(_root); _root will be processed among C->top() inputs
179 roots.push(C->top());
180 visited.set(C->top()->_idx);
181
182 while (roots.size() != 0) {
183 // Use local variables nstack_top_n & nstack_top_i to cache values
184 // on stack's top.
185 Node *nstack_top_n = roots.pop();
186 uint nstack_top_i = 0;
187 //while_nstack_nonempty:
188 while (true) {
189 // Get parent node and next input's index from stack's top.
190 Node *n = nstack_top_n;
191 uint i = nstack_top_i;
192
193 if (i == 0) {
194 // Fixup some control. Constants without control get attached
195 // to root and nodes that use is_block_proj() nodes should be attached
196 // to the region that starts their block.
197 const Node *in0 = n->in(0);
198 if (in0 != NULL) { // Control-dependent?
199 replace_block_proj_ctrl(n);
200 } else { // n->in(0) == NULL
201 if (n->req() == 1) { // This guy is a constant with NO inputs?
202 n->set_req(0, _root);
203 }
204 }
205 }
206
207 // First, visit all inputs and force them to get a block. If an
208 // input is already in a block we quit following inputs (to avoid
209 // cycles). Instead we put that Node on a worklist to be handled
210 // later (since IT'S inputs may not have a block yet).
211 bool done = true; // Assume all n's inputs will be processed
212 while (i < n->len()) { // For all inputs
213 Node *in = n->in(i); // Get input
214 ++i;
215 if (in == NULL) continue; // Ignore NULL, missing inputs
216 int is_visited = visited.test_set(in->_idx);
217 if (!_bbs.lookup(in->_idx)) { // Missing block selection?
218 if (is_visited) {
219 // assert( !visited.test(in->_idx), "did not schedule early" );
220 return false;
221 }
222 nstack.push(n, i); // Save parent node and next input's index.
223 nstack_top_n = in; // Process current input now.
224 nstack_top_i = 0;
225 done = false; // Not all n's inputs processed.
226 break; // continue while_nstack_nonempty;
227 } else if (!is_visited) { // Input not yet visited?
228 roots.push(in); // Visit this guy later, using worklist
229 }
230 }
231 if (done) {
232 // All of n's inputs have been processed, complete post-processing.
233
234 // Some instructions are pinned into a block. These include Region,
235 // Phi, Start, Return, and other control-dependent instructions and
236 // any projections which depend on them.
237 if (!n->pinned()) {
238 // Set earliest legal block.
239 _bbs.map(n->_idx, find_deepest_input(n, _bbs));
240 } else {
241 assert(_bbs[n->_idx] == _bbs[n->in(0)->_idx], "Pinned Node should be at the same block as its control edge");
242 }
243
244 if (nstack.is_empty()) {
245 // Finished all nodes on stack.
246 // Process next node on the worklist 'roots'.
247 break;
248 }
249 // Get saved parent node and next input's index.
250 nstack_top_n = nstack.node();
251 nstack_top_i = nstack.index();
252 nstack.pop();
253 } // if (done)
254 } // while (true)
255 } // while (roots.size() != 0)
256 return true;
257 }
258
259 //------------------------------dom_lca----------------------------------------
260 // Find least common ancestor in dominator tree
261 // LCA is a current notion of LCA, to be raised above 'this'.
|