Mercurial > projects > ldc

comparison gen/passes/GarbageCollect2Stack.cpp @ 1551:ed0feda76820

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
DOUT is deprecated, use DEBUG(errs()) instead
author Benjamin Kramer <benny.kra@gmail.com>
date Mon, 27 Jul 2009 11:44:01 +0200
parents a326f145a57b
children f55ca8a1598c
comparison
equal deleted inserted replaced
1550:c704fea92f80 1551:ed0feda76820
33 #include "llvm/ADT/SmallVector.h" 33 #include "llvm/ADT/SmallVector.h"
34 #include "llvm/ADT/StringMap.h" 34 #include "llvm/ADT/StringMap.h"
35 #include "llvm/ADT/Statistic.h" 35 #include "llvm/ADT/Statistic.h"
36 #include "llvm/Support/Compiler.h" 36 #include "llvm/Support/Compiler.h"
37 #include "llvm/Support/Debug.h" 37 #include "llvm/Support/Debug.h"
38 #include "llvm/Support/raw_ostream.h"
38 using namespace llvm; 39 using namespace llvm;
39 40
40 STATISTIC(NumGcToStack, "Number of calls promoted to constant-size allocas"); 41 STATISTIC(NumGcToStack, "Number of calls promoted to constant-size allocas");
41 STATISTIC(NumToDynSize, "Number of calls promoted to dynamically-sized allocas"); 42 STATISTIC(NumToDynSize, "Number of calls promoted to dynamically-sized allocas");
42 STATISTIC(NumDeleted, "Number of GC calls deleted because the return value was unused"); 43 STATISTIC(NumDeleted, "Number of GC calls deleted because the return value was unused");
316 static bool isSafeToStackAllocate(Instruction* Alloc, DominatorTree& DT); 317 static bool isSafeToStackAllocate(Instruction* Alloc, DominatorTree& DT);
317 318
318 /// runOnFunction - Top level algorithm. 319 /// runOnFunction - Top level algorithm.
319 /// 320 ///
320 bool GarbageCollect2Stack::runOnFunction(Function &F) { 321 bool GarbageCollect2Stack::runOnFunction(Function &F) {
321 DEBUG(DOUT << "\nRunning -dgc2stack on function " << F.getName() << '\n'); 322 DEBUG(errs() << "\nRunning -dgc2stack on function " << F.getName() << '\n');
322 323
323 TargetData& TD = getAnalysis<TargetData>(); 324 TargetData& TD = getAnalysis<TargetData>();
324 DominatorTree& DT = getAnalysis<DominatorTree>(); 325 DominatorTree& DT = getAnalysis<DominatorTree>();
325 CallGraph* CG = getAnalysisIfAvailable<CallGraph>(); 326 CallGraph* CG = getAnalysisIfAvailable<CallGraph>();
326 CallGraphNode* CGNode = CG ? (*CG)[&F] : NULL; 327 CallGraphNode* CGNode = CG ? (*CG)[&F] : NULL;
362 NumDeleted++; 363 NumDeleted++;
363 RemoveCall(*Context, CS, A); 364 RemoveCall(*Context, CS, A);
364 continue; 365 continue;
365 } 366 }
366 367
367 DEBUG(DOUT << "GarbageCollect2Stack inspecting: " << *Inst); 368 DEBUG(errs() << "GarbageCollect2Stack inspecting: " << *Inst);
368 369
369 if (!info->analyze(*Context, CS, A) || !isSafeToStackAllocate(Inst, DT)) 370 if (!info->analyze(*Context, CS, A) || !isSafeToStackAllocate(Inst, DT))
370 continue; 371 continue;
371 372
372 // Let's alloca this! 373 // Let's alloca this!
373 Changed = true; 374 Changed = true;
374 375
375 IRBuilder<> Builder(BB, Inst); 376 IRBuilder<> Builder(BB, Inst);
376 Value* newVal = info->promote(*Context, CS, Builder, A); 377 Value* newVal = info->promote(*Context, CS, Builder, A);
377 378
378 DEBUG(DOUT << "Promoted to: " << *newVal); 379 DEBUG(errs() << "Promoted to: " << *newVal);
379 380
380 // Make sure the type is the same as it was before, and replace all 381 // Make sure the type is the same as it was before, and replace all
381 // uses of the runtime call with the alloca. 382 // uses of the runtime call with the alloca.
382 if (newVal->getType() != Inst->getType()) 383 if (newVal->getType() != Inst->getType())
383 newVal = Builder.CreateBitCast(newVal, Inst->getType()); 384 newVal = Builder.CreateBitCast(newVal, Inst->getType());
416 } 417 }
417 418
418 /// Returns whether Def is used by any instruction that is reachable from Alloc 419 /// Returns whether Def is used by any instruction that is reachable from Alloc
419 /// (without executing Def again). 420 /// (without executing Def again).
420 static bool mayBeUsedAfterRealloc(Instruction* Def, Instruction* Alloc, DominatorTree& DT) { 421 static bool mayBeUsedAfterRealloc(Instruction* Def, Instruction* Alloc, DominatorTree& DT) {
421 DOUT << "### mayBeUsedAfterRealloc()\n" << *Def << *Alloc; 422 DEBUG(errs() << "### mayBeUsedAfterRealloc()\n" << *Def << *Alloc);
422 423
423 // If the definition isn't used it obviously won't be used after the 424 // If the definition isn't used it obviously won't be used after the
424 // allocation. 425 // allocation.
425 // If it does not dominate the allocation, there's no way for it to be used 426 // If it does not dominate the allocation, there's no way for it to be used
426 // without going through Def again first, since the definition couldn't 427 // without going through Def again first, since the definition couldn't
427 // dominate the user either. 428 // dominate the user either.
428 if (Def->use_empty() || !DT.dominates(Def, Alloc)) { 429 if (Def->use_empty() || !DT.dominates(Def, Alloc)) {
429 DOUT << "### No uses or does not dominate allocation\n"; 430 DEBUG(errs() << "### No uses or does not dominate allocation\n");
430 return false; 431 return false;
431 } 432 }
432 433
433 DOUT << "### Def dominates Alloc\n"; 434 DEBUG(errs() << "### Def dominates Alloc\n");
434 435
435 BasicBlock* DefBlock = Def->getParent(); 436 BasicBlock* DefBlock = Def->getParent();
436 BasicBlock* AllocBlock = Alloc->getParent(); 437 BasicBlock* AllocBlock = Alloc->getParent();
437 438
438 // Create a set of users and one of blocks containing users. 439 // Create a set of users and one of blocks containing users.
439 SmallSet<User*, 16> Users; 440 SmallSet<User*, 16> Users;
440 SmallSet<BasicBlock*, 16> UserBlocks; 441 SmallSet<BasicBlock*, 16> UserBlocks;
441 for (Instruction::use_iterator UI = Def->use_begin(), UE = Def->use_end(); 442 for (Instruction::use_iterator UI = Def->use_begin(), UE = Def->use_end();
442 UI != UE; ++UI) { 443 UI != UE; ++UI) {
443 Instruction* User = cast<Instruction>(*UI); 444 Instruction* User = cast<Instruction>(*UI);
444 DOUT << "USER: " << *User; 445 DEBUG(errs() << "USER: " << *User);
445 BasicBlock* UserBlock = User->getParent(); 446 BasicBlock* UserBlock = User->getParent();
446 447
447 // This dominance check is not performed if they're in the same block 448 // This dominance check is not performed if they're in the same block
448 // because it will just walk the instruction list to figure it out. 449 // because it will just walk the instruction list to figure it out.
449 // We will instead do that ourselves in the first iteration (for all 450 // We will instead do that ourselves in the first iteration (for all
450 // users at once). 451 // users at once).
451 if (AllocBlock != UserBlock && DT.dominates(AllocBlock, UserBlock)) { 452 if (AllocBlock != UserBlock && DT.dominates(AllocBlock, UserBlock)) {
452 // There's definitely a path from alloc to this user that does not 453 // There's definitely a path from alloc to this user that does not
453 // go through Def, namely any path that ends up in that user. 454 // go through Def, namely any path that ends up in that user.
454 DOUT << "### Alloc dominates user " << *User; 455 DEBUG(errs() << "### Alloc dominates user " << *User);
455 return true; 456 return true;
456 } 457 }
457 458
458 // Phi nodes are checked separately, so no need to enter them here. 459 // Phi nodes are checked separately, so no need to enter them here.
459 if (!isa<PHINode>(User)) { 460 if (!isa<PHINode>(User)) {
489 if (UserBlocks.count(B)) { 490 if (UserBlocks.count(B)) {
490 if (B != DefBlock && B != AllocBlock) { 491 if (B != DefBlock && B != AllocBlock) {
491 // This block does not contain the definition or the allocation, 492 // This block does not contain the definition or the allocation,
492 // so any user in this block is definitely reachable without 493 // so any user in this block is definitely reachable without
493 // finding either the definition or the allocation. 494 // finding either the definition or the allocation.
494 DOUT << "### Block " << B->getName() 495 DEBUG(errs() << "### Block " << B->getName()
495 << " contains a reachable user\n"; 496 << " contains a reachable user\n");
496 return true; 497 return true;
497 } 498 }
498 // We need to walk the instructions in the block to see whether we 499 // We need to walk the instructions in the block to see whether we
499 // reach a user before we reach the definition or the allocation. 500 // reach a user before we reach the definition or the allocation.
500 for (BasicBlock::iterator E = B->end(); BBI != E; ++BBI) { 501 for (BasicBlock::iterator E = B->end(); BBI != E; ++BBI) {
501 if (&*BBI == Alloc || &*BBI == Def) 502 if (&*BBI == Alloc || &*BBI == Def)
502 break; 503 break;
503 if (Users.count(BBI)) { 504 if (Users.count(BBI)) {
504 DOUT << "### Problematic user: " << *BBI; 505 DEBUG(errs() << "### Problematic user: " << *BBI);
505 return true; 506 return true;
506 } 507 }
507 } 508 }
508 } else if (B == DefBlock || (B == AllocBlock && BBI != Start)) { 509 } else if (B == DefBlock || (B == AllocBlock && BBI != Start)) {
509 // There are no users in the block so the def or the allocation 510 // There are no users in the block so the def or the allocation
525 // Check phi nodes here because we only care about the operand 526 // Check phi nodes here because we only care about the operand
526 // coming in from this block. 527 // coming in from this block.
527 bool SeenDef = false; 528 bool SeenDef = false;
528 while (isa<PHINode>(BBI)) { 529 while (isa<PHINode>(BBI)) {
529 if (Def == cast<PHINode>(BBI)->getIncomingValueForBlock(B)) { 530 if (Def == cast<PHINode>(BBI)->getIncomingValueForBlock(B)) {
530 DOUT << "### Problematic phi user: " << *BBI; 531 DEBUG(errs() << "### Problematic phi user: " << *BBI);
531 return true; 532 return true;
532 } 533 }
533 SeenDef |= (Def == &*BBI); 534 SeenDef |= (Def == &*BBI);
534 ++BBI; 535 ++BBI;
535 } 536 }