Mercurial > hg > graal-compiler

comparison src/share/vm/opto/chaitin.hpp @ 12355:cefad50507d8

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Merge with hs25-b53
author Gilles Duboscq <duboscq@ssw.jku.at>
date Fri, 11 Oct 2013 10:38:03 +0200
parents 8c83625e3a53
children d8a449d2f5b2
comparison
equal deleted inserted replaced
12058:ccb4f2af2319 12355:cefad50507d8
281 // Map from Nodes to live ranges 281 // Map from Nodes to live ranges
282 LRG_List _names; 282 LRG_List _names;
283 283
284 // Straight out of Tarjan's union-find algorithm 284 // Straight out of Tarjan's union-find algorithm
285 uint find_compress(const Node *node) { 285 uint find_compress(const Node *node) {
286 uint lrg_id = find_compress(_names[node->_idx]); 286 uint lrg_id = find_compress(_names.at(node->_idx));
287 _names.map(node->_idx, lrg_id); 287 _names.at_put(node->_idx, lrg_id);
288 return lrg_id; 288 return lrg_id;
289 } 289 }
290 290
291 uint find_compress(uint lrg); 291 uint find_compress(uint lrg);
292 292
303 void set_max_lrg_id(uint max_lrg_id) { 303 void set_max_lrg_id(uint max_lrg_id) {
304 _max_lrg_id = max_lrg_id; 304 _max_lrg_id = max_lrg_id;
305 } 305 }
306 306
307 uint size() const { 307 uint size() const {
308 return _names.Size(); 308 return _names.length();
309 } 309 }
310 310
311 uint live_range_id(uint idx) const { 311 uint live_range_id(uint idx) const {
312 return _names[idx]; 312 return _names.at(idx);
313 } 313 }
314 314
315 uint live_range_id(const Node *node) const { 315 uint live_range_id(const Node *node) const {
316 return _names[node->_idx]; 316 return _names.at(node->_idx);
317 } 317 }
318 318
319 uint uf_live_range_id(uint lrg_id) const { 319 uint uf_live_range_id(uint lrg_id) const {
320 return _uf_map[lrg_id]; 320 return _uf_map.at(lrg_id);
321 } 321 }
322 322
323 void map(uint idx, uint lrg_id) { 323 void map(uint idx, uint lrg_id) {
324 _names.map(idx, lrg_id); 324 _names.at_put(idx, lrg_id);
325 } 325 }
326 326
327 void uf_map(uint dst_lrg_id, uint src_lrg_id) { 327 void uf_map(uint dst_lrg_id, uint src_lrg_id) {
328 _uf_map.map(dst_lrg_id, src_lrg_id); 328 _uf_map.at_put(dst_lrg_id, src_lrg_id);
329 } 329 }
330 330
331 void extend(uint idx, uint lrg_id) { 331 void extend(uint idx, uint lrg_id) {
332 _names.extend(idx, lrg_id); 332 _names.at_put_grow(idx, lrg_id);
333 } 333 }
334 334
335 void uf_extend(uint dst_lrg_id, uint src_lrg_id) { 335 void uf_extend(uint dst_lrg_id, uint src_lrg_id) {
336 _uf_map.extend(dst_lrg_id, src_lrg_id); 336 _uf_map.at_put_grow(dst_lrg_id, src_lrg_id);
337 } 337 }
338 338
339 LiveRangeMap(uint unique) 339 LiveRangeMap(Arena* arena, uint unique)
340 : _names(unique) 340 : _names(arena, unique, unique, 0)
341 , _uf_map(unique) 341 , _uf_map(arena, unique, unique, 0)
342 , _max_lrg_id(0) {} 342 , _max_lrg_id(0) {}
343 343
344 uint find_id( const Node *n ) { 344 uint find_id( const Node *n ) {
345 uint retval = live_range_id(n); 345 uint retval = live_range_id(n);
346 assert(retval == find(n),"Invalid node to lidx mapping"); 346 assert(retval == find(n),"Invalid node to lidx mapping");
353 // Make all Nodes map directly to their final live range; no need for 353 // Make all Nodes map directly to their final live range; no need for
354 // the Union-Find mapping after this call. 354 // the Union-Find mapping after this call.
355 void compress_uf_map_for_nodes(); 355 void compress_uf_map_for_nodes();
356 356
357 uint find(uint lidx) { 357 uint find(uint lidx) {
358 uint uf_lidx = _uf_map[lidx]; 358 uint uf_lidx = _uf_map.at(lidx);
359 return (uf_lidx == lidx) ? uf_lidx : find_compress(lidx); 359 return (uf_lidx == lidx) ? uf_lidx : find_compress(lidx);
360 } 360 }
361 361
362 // Convert a Node into a Live Range Index - a lidx 362 // Convert a Node into a Live Range Index - a lidx
363 uint find(const Node *node) { 363 uint find(const Node *node) {
364 uint lidx = live_range_id(node); 364 uint lidx = live_range_id(node);
365 uint uf_lidx = _uf_map[lidx]; 365 uint uf_lidx = _uf_map.at(lidx);
366 return (uf_lidx == lidx) ? uf_lidx : find_compress(node); 366 return (uf_lidx == lidx) ? uf_lidx : find_compress(node);
367 } 367 }
368 368
369 // Like Find above, but no path compress, so bad asymptotic behavior 369 // Like Find above, but no path compress, so bad asymptotic behavior
370 uint find_const(uint lrg) const; 370 uint find_const(uint lrg) const;
371 371
372 // Like Find above, but no path compress, so bad asymptotic behavior 372 // Like Find above, but no path compress, so bad asymptotic behavior
373 uint find_const(const Node *node) const { 373 uint find_const(const Node *node) const {
374 if(node->_idx >= _names.Size()) { 374 if(node->_idx >= (uint)_names.length()) {
375 return 0; // not mapped, usual for debug dump 375 return 0; // not mapped, usual for debug dump
376 } 376 }
377 return find_const(_names[node->_idx]); 377 return find_const(_names.at(node->_idx));
378 } 378 }
379 }; 379 };
380 380
381 //------------------------------Chaitin---------------------------------------- 381 //------------------------------Chaitin----------------------------------------
382 // Briggs-Chaitin style allocation, mostly. 382 // Briggs-Chaitin style allocation, mostly.
410 410
411 // Helper functions for Split() 411 // Helper functions for Split()
412 uint split_DEF( Node *def, Block *b, int loc, uint max, Node **Reachblock, Node **debug_defs, GrowableArray<uint> splits, int slidx ); 412 uint split_DEF( Node *def, Block *b, int loc, uint max, Node **Reachblock, Node **debug_defs, GrowableArray<uint> splits, int slidx );
413 uint split_USE( Node *def, Block *b, Node *use, uint useidx, uint max, bool def_down, bool cisc_sp, GrowableArray<uint> splits, int slidx ); 413 uint split_USE( Node *def, Block *b, Node *use, uint useidx, uint max, bool def_down, bool cisc_sp, GrowableArray<uint> splits, int slidx );
414 414
415 bool clone_projs(Block *b, uint idx, Node *con, Node *copy, LiveRangeMap &lrg_map) {
416 bool found_projs = clone_projs_shared(b, idx, con, copy, lrg_map.max_lrg_id());
417
418 if(found_projs) {
419 uint max_lrg_id = lrg_map.max_lrg_id();
420 lrg_map.set_max_lrg_id(max_lrg_id + 1);
421 }
422
423 return found_projs;
424 }
425
426 //------------------------------clone_projs------------------------------------ 415 //------------------------------clone_projs------------------------------------
427 // After cloning some rematerialized instruction, clone any MachProj's that 416 // After cloning some rematerialized instruction, clone any MachProj's that
428 // follow it. Example: Intel zero is XOR, kills flags. Sparc FP constants 417 // follow it. Example: Intel zero is XOR, kills flags. Sparc FP constants
429 // use G3 as an address temp. 418 // use G3 as an address temp.
430 bool clone_projs(Block *b, uint idx, Node *con, Node *copy, uint &max_lrg_id) { 419 int clone_projs(Block* b, uint idx, Node* orig, Node* copy, uint& max_lrg_id);
431 bool found_projs = clone_projs_shared(b, idx, con, copy, max_lrg_id); 420
432 421 int clone_projs(Block* b, uint idx, Node* orig, Node* copy, LiveRangeMap& lrg_map) {
433 if(found_projs) { 422 uint max_lrg_id = lrg_map.max_lrg_id();
434 max_lrg_id++; 423 int found_projs = clone_projs(b, idx, orig, copy, max_lrg_id);
424 if (found_projs > 0) {
425 // max_lrg_id is updated during call above
426 lrg_map.set_max_lrg_id(max_lrg_id);
435 } 427 }
436
437 return found_projs; 428 return found_projs;
438 } 429 }
439
440 bool clone_projs_shared(Block *b, uint idx, Node *con, Node *copy, uint max_lrg_id);
441 430
442 Node *split_Rematerialize(Node *def, Block *b, uint insidx, uint &maxlrg, GrowableArray<uint> splits, 431 Node *split_Rematerialize(Node *def, Block *b, uint insidx, uint &maxlrg, GrowableArray<uint> splits,
443 int slidx, uint *lrg2reach, Node **Reachblock, bool walkThru); 432 int slidx, uint *lrg2reach, Node **Reachblock, bool walkThru);
444 // True if lidx is used before any real register is def'd in the block 433 // True if lidx is used before any real register is def'd in the block
445 bool prompt_use( Block *b, uint lidx ); 434 bool prompt_use( Block *b, uint lidx );