24
25 #include "precompiled.hpp"
26 #include "memory/allocation.inline.hpp"
27 #include "opto/callnode.hpp"
28 #include "opto/chaitin.hpp"
29 #include "opto/live.hpp"
30 #include "opto/machnode.hpp"
31
32
33 // Compute live-in/live-out. We use a totally incremental algorithm. The LIVE
34 // problem is monotonic. The steady-state solution looks like this: pull a
35 // block from the worklist. It has a set of delta's - values which are newly
36 // live-in from the block. Push these to the live-out sets of all predecessor
37 // blocks. At each predecessor, the new live-out values are ANDed with what is
38 // already live-out (extra stuff is added to the live-out sets). Then the
39 // remaining new live-out values are ANDed with what is locally defined.
40 // Leftover bits become the new live-in for the predecessor block, and the pred
41 // block is put on the worklist.
42 // The locally live-in stuff is computed once and added to predecessor
43 // live-out sets. This separate compilation is done in the outer loop below.
44 PhaseLive::PhaseLive( const PhaseCFG &cfg, const LRG_List &names, Arena *arena ) : Phase(LIVE), _cfg(cfg), _names(names), _arena(arena), _live(0) {
45 }
46
47 void PhaseLive::compute(uint maxlrg) {
48 _maxlrg = maxlrg;
49 _worklist = new (_arena) Block_List();
50
51 // Init the sparse live arrays. This data is live on exit from here!
52 // The _live info is the live-out info.
53 _live = (IndexSet*)_arena->Amalloc(sizeof(IndexSet) * _cfg.number_of_blocks());
54 uint i;
55 for (i = 0; i < _cfg.number_of_blocks(); i++) {
56 _live[i].initialize(_maxlrg);
57 }
58
59 // Init the sparse arrays for delta-sets.
60 ResourceMark rm; // Nuke temp storage on exit
61
62 // Does the memory used by _defs and _deltas get reclaimed? Does it matter? TT
63
64 // Array of values defined locally in blocks
65 _defs = NEW_RESOURCE_ARRAY(IndexSet,_cfg.number_of_blocks());
66 for (i = 0; i < _cfg.number_of_blocks(); i++) {
67 _defs[i].initialize(_maxlrg);
68 }
69
70 // Array of delta-set pointers, indexed by block pre_order-1.
71 _deltas = NEW_RESOURCE_ARRAY(IndexSet*,_cfg.number_of_blocks());
72 memset( _deltas, 0, sizeof(IndexSet*)* _cfg.number_of_blocks());
73
74 _free_IndexSet = NULL;
75
76 // Blocks having done pass-1
77 VectorSet first_pass(Thread::current()->resource_area());
78
107 }
108 }
109 #ifdef ASSERT
110 def_outside->set_next(_free_IndexSet);
111 _free_IndexSet = def_outside; // Drop onto free list
112 #endif
113 // Remove anything defined by Phis and the block start instruction
114 for (uint k = i; k > 0; k--) {
115 uint r = _names.at(block->get_node(k - 1)->_idx);
116 def->insert(r);
117 use->remove(r);
118 }
119
120 // Push these live-in things to predecessors
121 for (uint l = 1; l < block->num_preds(); l++) {
122 Block* p = _cfg.get_block_for_node(block->pred(l));
123 add_liveout(p, use, first_pass);
124
125 // PhiNode uses go in the live-out set of prior blocks.
126 for (uint k = i; k > 0; k--) {
127 add_liveout(p, _names.at(block->get_node(k-1)->in(l)->_idx), first_pass);
128 }
129 }
130 freeset(block);
131 first_pass.set(block->_pre_order);
132
133 // Inner loop: blocks that picked up new live-out values to be propagated
134 while (_worklist->size()) {
135 Block* block = _worklist->pop();
136 IndexSet *delta = getset(block);
137 assert( delta->count(), "missing delta set" );
138
139 // Add new-live-in to predecessors live-out sets
140 for (uint l = 1; l < block->num_preds(); l++) {
141 Block* predecessor = _cfg.get_block_for_node(block->pred(l));
142 add_liveout(predecessor, delta, first_pass);
143 }
144
145 freeset(block);
146 } // End of while-worklist-not-empty
147
183
184 // Pull from free list, or allocate. Internal allocation on the returned set
185 // is always from thread local storage.
186 IndexSet *PhaseLive::getfreeset( ) {
187 IndexSet *f = _free_IndexSet;
188 if( !f ) {
189 f = new IndexSet;
190 // f->set_arena(Thread::current()->resource_area());
191 f->initialize(_maxlrg, Thread::current()->resource_area());
192 } else {
193 // Pull from free list
194 _free_IndexSet = f->next();
195 //f->_cnt = 0; // Reset to empty
196 // f->set_arena(Thread::current()->resource_area());
197 f->initialize(_maxlrg, Thread::current()->resource_area());
198 }
199 return f;
200 }
201
202 // Free an IndexSet from a block.
203 void PhaseLive::freeset( const Block *p ) {
204 IndexSet *f = _deltas[p->_pre_order-1];
205 f->set_next(_free_IndexSet);
206 _free_IndexSet = f; // Drop onto free list
207 _deltas[p->_pre_order-1] = NULL;
208 }
209
210 // Add a live-out value to a given blocks live-out set. If it is new, then
211 // also add it to the delta set and stick the block on the worklist.
212 void PhaseLive::add_liveout( Block *p, uint r, VectorSet &first_pass ) {
213 IndexSet *live = &_live[p->_pre_order-1];
214 if( live->insert(r) ) { // If actually inserted...
215 // We extended the live-out set. See if the value is generated locally.
216 // If it is not, then we must extend the live-in set.
217 if( !_defs[p->_pre_order-1].member( r ) ) {
218 if( !_deltas[p->_pre_order-1] && // Not on worklist?
219 first_pass.test(p->_pre_order) )
220 _worklist->push(p); // Actually go on worklist if already 1st pass
221 getset(p)->insert(r);
222 }
223 }
224 }
232
233 IndexSetIterator elements(lo);
234 uint r;
235 while ((r = elements.next()) != 0) {
236 if( live->insert(r) && // If actually inserted...
237 !defs->member( r ) ) // and not defined locally
238 delta->insert(r); // Then add to live-in set
239 }
240
241 if( delta->count() ) { // If actually added things
242 _deltas[p->_pre_order-1] = delta; // Flag as on worklist now
243 if( !on_worklist && // Not on worklist?
244 first_pass.test(p->_pre_order) )
245 _worklist->push(p); // Actually go on worklist if already 1st pass
246 } else { // Nothing there; just free it
247 delta->set_next(_free_IndexSet);
248 _free_IndexSet = delta; // Drop onto free list
249 }
250 }
251
252 #ifndef PRODUCT
253 // Dump the live-out set for a block
254 void PhaseLive::dump( const Block *b ) const {
255 tty->print("Block %d: ",b->_pre_order);
256 tty->print("LiveOut: "); _live[b->_pre_order-1].dump();
257 uint cnt = b->number_of_nodes();
258 for( uint i=0; i<cnt; i++ ) {
259 tty->print("L%d/", _names.at(b->get_node(i)->_idx));
260 b->get_node(i)->dump();
261 }
262 tty->print("\n");
263 }
264
265 // Verify that base pointers and derived pointers are still sane.
266 void PhaseChaitin::verify_base_ptrs( ResourceArea *a ) const {
267 #ifdef ASSERT
268 Unique_Node_List worklist(a);
269 for (uint i = 0; i < _cfg.number_of_blocks(); i++) {
270 Block* block = _cfg.get_block(i);
271 for (uint j = block->end_idx() + 1; j > 1; j--) {
272 Node* n = block->get_node(j-1);
273 if (n->is_Phi()) {
274 break;
275 }
|
24
25 #include "precompiled.hpp"
26 #include "memory/allocation.inline.hpp"
27 #include "opto/callnode.hpp"
28 #include "opto/chaitin.hpp"
29 #include "opto/live.hpp"
30 #include "opto/machnode.hpp"
31
32
33 // Compute live-in/live-out. We use a totally incremental algorithm. The LIVE
34 // problem is monotonic. The steady-state solution looks like this: pull a
35 // block from the worklist. It has a set of delta's - values which are newly
36 // live-in from the block. Push these to the live-out sets of all predecessor
37 // blocks. At each predecessor, the new live-out values are ANDed with what is
38 // already live-out (extra stuff is added to the live-out sets). Then the
39 // remaining new live-out values are ANDed with what is locally defined.
40 // Leftover bits become the new live-in for the predecessor block, and the pred
41 // block is put on the worklist.
42 // The locally live-in stuff is computed once and added to predecessor
43 // live-out sets. This separate compilation is done in the outer loop below.
44 PhaseLive::PhaseLive(const PhaseCFG &cfg, const LRG_List &names, Arena *arena, bool keep_deltas)
45 : Phase(LIVE),
46 _cfg(cfg),
47 _names(names),
48 _arena(arena),
49 _live(0),
50 _livein(0),
51 _keep_deltas(keep_deltas) {
52 }
53
54 void PhaseLive::compute(uint maxlrg) {
55 _maxlrg = maxlrg;
56 _worklist = new (_arena) Block_List();
57
58 // Init the sparse live arrays. This data is live on exit from here!
59 // The _live info is the live-out info.
60 _live = (IndexSet*)_arena->Amalloc(sizeof(IndexSet) * _cfg.number_of_blocks());
61 uint i;
62 for (i = 0; i < _cfg.number_of_blocks(); i++) {
63 _live[i].initialize(_maxlrg);
64 }
65
66 if (_keep_deltas) {
67 _livein = (IndexSet*)_arena->Amalloc(sizeof(IndexSet) * _cfg.number_of_blocks());
68 for (i = 0; i < _cfg.number_of_blocks(); i++) {
69 _livein[i].initialize(_maxlrg);
70 }
71 }
72
73 // Init the sparse arrays for delta-sets.
74 ResourceMark rm; // Nuke temp storage on exit
75
76 // Does the memory used by _defs and _deltas get reclaimed? Does it matter? TT
77
78 // Array of values defined locally in blocks
79 _defs = NEW_RESOURCE_ARRAY(IndexSet,_cfg.number_of_blocks());
80 for (i = 0; i < _cfg.number_of_blocks(); i++) {
81 _defs[i].initialize(_maxlrg);
82 }
83
84 // Array of delta-set pointers, indexed by block pre_order-1.
85 _deltas = NEW_RESOURCE_ARRAY(IndexSet*,_cfg.number_of_blocks());
86 memset( _deltas, 0, sizeof(IndexSet*)* _cfg.number_of_blocks());
87
88 _free_IndexSet = NULL;
89
90 // Blocks having done pass-1
91 VectorSet first_pass(Thread::current()->resource_area());
92
121 }
122 }
123 #ifdef ASSERT
124 def_outside->set_next(_free_IndexSet);
125 _free_IndexSet = def_outside; // Drop onto free list
126 #endif
127 // Remove anything defined by Phis and the block start instruction
128 for (uint k = i; k > 0; k--) {
129 uint r = _names.at(block->get_node(k - 1)->_idx);
130 def->insert(r);
131 use->remove(r);
132 }
133
134 // Push these live-in things to predecessors
135 for (uint l = 1; l < block->num_preds(); l++) {
136 Block* p = _cfg.get_block_for_node(block->pred(l));
137 add_liveout(p, use, first_pass);
138
139 // PhiNode uses go in the live-out set of prior blocks.
140 for (uint k = i; k > 0; k--) {
141 Node *phi = block->get_node(k - 1);
142 if (l < phi->req()) {
143 add_liveout(p, _names.at(phi->in(l)->_idx), first_pass);
144 }
145 }
146 }
147 freeset(block);
148 first_pass.set(block->_pre_order);
149
150 // Inner loop: blocks that picked up new live-out values to be propagated
151 while (_worklist->size()) {
152 Block* block = _worklist->pop();
153 IndexSet *delta = getset(block);
154 assert( delta->count(), "missing delta set" );
155
156 // Add new-live-in to predecessors live-out sets
157 for (uint l = 1; l < block->num_preds(); l++) {
158 Block* predecessor = _cfg.get_block_for_node(block->pred(l));
159 add_liveout(predecessor, delta, first_pass);
160 }
161
162 freeset(block);
163 } // End of while-worklist-not-empty
164
200
201 // Pull from free list, or allocate. Internal allocation on the returned set
202 // is always from thread local storage.
203 IndexSet *PhaseLive::getfreeset( ) {
204 IndexSet *f = _free_IndexSet;
205 if( !f ) {
206 f = new IndexSet;
207 // f->set_arena(Thread::current()->resource_area());
208 f->initialize(_maxlrg, Thread::current()->resource_area());
209 } else {
210 // Pull from free list
211 _free_IndexSet = f->next();
212 //f->_cnt = 0; // Reset to empty
213 // f->set_arena(Thread::current()->resource_area());
214 f->initialize(_maxlrg, Thread::current()->resource_area());
215 }
216 return f;
217 }
218
219 // Free an IndexSet from a block.
220 void PhaseLive::freeset( Block *p ) {
221 IndexSet *f = _deltas[p->_pre_order-1];
222 if ( _keep_deltas ) {
223 add_livein(p, f);
224 }
225 f->set_next(_free_IndexSet);
226 _free_IndexSet = f; // Drop onto free list
227 _deltas[p->_pre_order-1] = NULL;
228 }
229
230 // Add a live-out value to a given blocks live-out set. If it is new, then
231 // also add it to the delta set and stick the block on the worklist.
232 void PhaseLive::add_liveout( Block *p, uint r, VectorSet &first_pass ) {
233 IndexSet *live = &_live[p->_pre_order-1];
234 if( live->insert(r) ) { // If actually inserted...
235 // We extended the live-out set. See if the value is generated locally.
236 // If it is not, then we must extend the live-in set.
237 if( !_defs[p->_pre_order-1].member( r ) ) {
238 if( !_deltas[p->_pre_order-1] && // Not on worklist?
239 first_pass.test(p->_pre_order) )
240 _worklist->push(p); // Actually go on worklist if already 1st pass
241 getset(p)->insert(r);
242 }
243 }
244 }
252
253 IndexSetIterator elements(lo);
254 uint r;
255 while ((r = elements.next()) != 0) {
256 if( live->insert(r) && // If actually inserted...
257 !defs->member( r ) ) // and not defined locally
258 delta->insert(r); // Then add to live-in set
259 }
260
261 if( delta->count() ) { // If actually added things
262 _deltas[p->_pre_order-1] = delta; // Flag as on worklist now
263 if( !on_worklist && // Not on worklist?
264 first_pass.test(p->_pre_order) )
265 _worklist->push(p); // Actually go on worklist if already 1st pass
266 } else { // Nothing there; just free it
267 delta->set_next(_free_IndexSet);
268 _free_IndexSet = delta; // Drop onto free list
269 }
270 }
271
272 // Add a vector of live-in values to a given blocks live-in set.
273 void PhaseLive::add_livein(Block *p, IndexSet *lo) {
274 IndexSet *livein = &_livein[p->_pre_order-1];
275 IndexSetIterator elements(lo);
276 uint r;
277 while ((r = elements.next()) != 0) {
278 livein->insert(r); // Then add to live-in set
279 }
280 }
281
282 #ifndef PRODUCT
283 // Dump the live-out set for a block
284 void PhaseLive::dump( const Block *b ) const {
285 tty->print("Block %d: ",b->_pre_order);
286 if ( _keep_deltas ) {
287 tty->print("LiveIn: "); _livein[b->_pre_order-1].dump();
288 }
289 tty->print("LiveOut: "); _live[b->_pre_order-1].dump();
290 uint cnt = b->number_of_nodes();
291 for( uint i=0; i<cnt; i++ ) {
292 tty->print("L%d/", _names.at(b->get_node(i)->_idx));
293 b->get_node(i)->dump();
294 }
295 tty->print("\n");
296 }
297
298 // Verify that base pointers and derived pointers are still sane.
299 void PhaseChaitin::verify_base_ptrs( ResourceArea *a ) const {
300 #ifdef ASSERT
301 Unique_Node_List worklist(a);
302 for (uint i = 0; i < _cfg.number_of_blocks(); i++) {
303 Block* block = _cfg.get_block(i);
304 for (uint j = block->end_idx() + 1; j > 1; j--) {
305 Node* n = block->get_node(j-1);
306 if (n->is_Phi()) {
307 break;
308 }
|