Mercurial > hg > Members > tobaru > cbc > CbC_llvm
comparison lib/Transforms/Scalar/TailRecursionElimination.cpp @ 95:afa8332a0e37
LLVM 3.8
author | Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> |
---|---|
date | Tue, 13 Oct 2015 17:48:58 +0900 |
parents | 60c9769439b8 |
children | b0dd3743370f 7d135dc70f03 |
comparison
equal
deleted
inserted
replaced
84:f3e34b893a5f | 95:afa8332a0e37 |
---|---|
52 | 52 |
53 #include "llvm/Transforms/Scalar.h" | 53 #include "llvm/Transforms/Scalar.h" |
54 #include "llvm/ADT/STLExtras.h" | 54 #include "llvm/ADT/STLExtras.h" |
55 #include "llvm/ADT/SmallPtrSet.h" | 55 #include "llvm/ADT/SmallPtrSet.h" |
56 #include "llvm/ADT/Statistic.h" | 56 #include "llvm/ADT/Statistic.h" |
57 #include "llvm/Analysis/GlobalsModRef.h" | |
58 #include "llvm/Analysis/CFG.h" | |
57 #include "llvm/Analysis/CaptureTracking.h" | 59 #include "llvm/Analysis/CaptureTracking.h" |
58 #include "llvm/Analysis/CFG.h" | |
59 #include "llvm/Analysis/InlineCost.h" | 60 #include "llvm/Analysis/InlineCost.h" |
60 #include "llvm/Analysis/InstructionSimplify.h" | 61 #include "llvm/Analysis/InstructionSimplify.h" |
61 #include "llvm/Analysis/Loads.h" | 62 #include "llvm/Analysis/Loads.h" |
62 #include "llvm/Analysis/TargetTransformInfo.h" | 63 #include "llvm/Analysis/TargetTransformInfo.h" |
63 #include "llvm/IR/CFG.h" | 64 #include "llvm/IR/CFG.h" |
85 STATISTIC(NumAccumAdded, "Number of accumulators introduced"); | 86 STATISTIC(NumAccumAdded, "Number of accumulators introduced"); |
86 | 87 |
87 namespace { | 88 namespace { |
88 struct TailCallElim : public FunctionPass { | 89 struct TailCallElim : public FunctionPass { |
89 const TargetTransformInfo *TTI; | 90 const TargetTransformInfo *TTI; |
90 const DataLayout *DL; | |
91 | 91 |
92 static char ID; // Pass identification, replacement for typeid | 92 static char ID; // Pass identification, replacement for typeid |
93 TailCallElim() : FunctionPass(ID) { | 93 TailCallElim() : FunctionPass(ID) { |
94 initializeTailCallElimPass(*PassRegistry::getPassRegistry()); | 94 initializeTailCallElimPass(*PassRegistry::getPassRegistry()); |
95 } | 95 } |
135 return new TailCallElim(); | 135 return new TailCallElim(); |
136 } | 136 } |
137 | 137 |
138 void TailCallElim::getAnalysisUsage(AnalysisUsage &AU) const { | 138 void TailCallElim::getAnalysisUsage(AnalysisUsage &AU) const { |
139 AU.addRequired<TargetTransformInfoWrapperPass>(); | 139 AU.addRequired<TargetTransformInfoWrapperPass>(); |
140 AU.addPreserved<GlobalsAAWrapperPass>(); | |
140 } | 141 } |
141 | 142 |
142 /// \brief Scan the specified function for alloca instructions. | 143 /// \brief Scan the specified function for alloca instructions. |
143 /// If it contains any dynamic allocas, returns false. | 144 /// If it contains any dynamic allocas, returns false. |
144 static bool CanTRE(Function &F) { | 145 static bool CanTRE(Function &F) { |
157 | 158 |
158 bool TailCallElim::runOnFunction(Function &F) { | 159 bool TailCallElim::runOnFunction(Function &F) { |
159 if (skipOptnoneFunction(F)) | 160 if (skipOptnoneFunction(F)) |
160 return false; | 161 return false; |
161 | 162 |
162 DL = F.getParent()->getDataLayout(); | 163 if (F.getFnAttribute("disable-tail-calls").getValueAsString() == "true") |
164 return false; | |
163 | 165 |
164 bool AllCallsAreTailCalls = false; | 166 bool AllCallsAreTailCalls = false; |
165 bool Modified = markTails(F, AllCallsAreTailCalls); | 167 bool Modified = markTails(F, AllCallsAreTailCalls); |
166 if (AllCallsAreTailCalls) | 168 if (AllCallsAreTailCalls) |
167 Modified |= runTRE(F); | 169 Modified |= runTRE(F); |
390 BasicBlock *OldEntry = nullptr; | 392 BasicBlock *OldEntry = nullptr; |
391 bool TailCallsAreMarkedTail = false; | 393 bool TailCallsAreMarkedTail = false; |
392 SmallVector<PHINode*, 8> ArgumentPHIs; | 394 SmallVector<PHINode*, 8> ArgumentPHIs; |
393 bool MadeChange = false; | 395 bool MadeChange = false; |
394 | 396 |
395 // CanTRETailMarkedCall - If false, we cannot perform TRE on tail calls | 397 // If false, we cannot perform TRE on tail calls marked with the 'tail' |
396 // marked with the 'tail' attribute, because doing so would cause the stack | 398 // attribute, because doing so would cause the stack size to increase (real |
397 // size to increase (real TRE would deallocate variable sized allocas, TRE | 399 // TRE would deallocate variable sized allocas, TRE doesn't). |
398 // doesn't). | |
399 bool CanTRETailMarkedCall = CanTRE(F); | 400 bool CanTRETailMarkedCall = CanTRE(F); |
400 | 401 |
401 // Change any tail recursive calls to loops. | 402 // Change any tail recursive calls to loops. |
402 // | 403 // |
403 // FIXME: The code generator produces really bad code when an 'escaping | 404 // FIXME: The code generator produces really bad code when an 'escaping |
404 // alloca' is changed from being a static alloca to being a dynamic alloca. | 405 // alloca' is changed from being a static alloca to being a dynamic alloca. |
405 // Until this is resolved, disable this transformation if that would ever | 406 // Until this is resolved, disable this transformation if that would ever |
406 // happen. This bug is PR962. | 407 // happen. This bug is PR962. |
407 SmallVector<BasicBlock*, 8> BBToErase; | 408 for (Function::iterator BBI = F.begin(), E = F.end(); BBI != E; /*in loop*/) { |
408 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { | 409 BasicBlock *BB = BBI++; // FoldReturnAndProcessPred may delete BB. |
409 if (ReturnInst *Ret = dyn_cast<ReturnInst>(BB->getTerminator())) { | 410 if (ReturnInst *Ret = dyn_cast<ReturnInst>(BB->getTerminator())) { |
410 bool Change = ProcessReturningBlock(Ret, OldEntry, TailCallsAreMarkedTail, | 411 bool Change = ProcessReturningBlock(Ret, OldEntry, TailCallsAreMarkedTail, |
411 ArgumentPHIs, !CanTRETailMarkedCall); | 412 ArgumentPHIs, !CanTRETailMarkedCall); |
412 if (!Change && BB->getFirstNonPHIOrDbg() == Ret) { | 413 if (!Change && BB->getFirstNonPHIOrDbg() == Ret) |
413 Change = FoldReturnAndProcessPred(BB, Ret, OldEntry, | 414 Change = FoldReturnAndProcessPred(BB, Ret, OldEntry, |
414 TailCallsAreMarkedTail, ArgumentPHIs, | 415 TailCallsAreMarkedTail, ArgumentPHIs, |
415 !CanTRETailMarkedCall); | 416 !CanTRETailMarkedCall); |
416 // FoldReturnAndProcessPred may have emptied some BB. Remember to | |
417 // erase them. | |
418 if (Change && BB->empty()) | |
419 BBToErase.push_back(BB); | |
420 | |
421 } | |
422 MadeChange |= Change; | 417 MadeChange |= Change; |
423 } | 418 } |
424 } | 419 } |
425 | |
426 for (auto BB: BBToErase) | |
427 BB->eraseFromParent(); | |
428 | 420 |
429 // If we eliminated any tail recursions, it's possible that we inserted some | 421 // If we eliminated any tail recursions, it's possible that we inserted some |
430 // silly PHI nodes which just merge an initial value (the incoming operand) | 422 // silly PHI nodes which just merge an initial value (the incoming operand) |
431 // with themselves. Check to see if we did and clean up our mess if so. This | 423 // with themselves. Check to see if we did and clean up our mess if so. This |
432 // occurs when a function passes an argument straight through to its tail | 424 // occurs when a function passes an argument straight through to its tail |
433 // call. | 425 // call. |
434 for (unsigned i = 0, e = ArgumentPHIs.size(); i != e; ++i) { | 426 for (unsigned i = 0, e = ArgumentPHIs.size(); i != e; ++i) { |
435 PHINode *PN = ArgumentPHIs[i]; | 427 PHINode *PN = ArgumentPHIs[i]; |
436 | 428 |
437 // If the PHI Node is a dynamic constant, replace it with the value it is. | 429 // If the PHI Node is a dynamic constant, replace it with the value it is. |
438 if (Value *PNV = SimplifyInstruction(PN)) { | 430 if (Value *PNV = SimplifyInstruction(PN, F.getParent()->getDataLayout())) { |
439 PN->replaceAllUsesWith(PNV); | 431 PN->replaceAllUsesWith(PNV); |
440 PN->eraseFromParent(); | 432 PN->eraseFromParent(); |
441 } | 433 } |
442 } | 434 } |
443 | 435 |
444 return MadeChange; | 436 return MadeChange; |
445 } | 437 } |
446 | 438 |
447 | 439 |
448 /// CanMoveAboveCall - Return true if it is safe to move the specified | 440 /// Return true if it is safe to move the specified |
449 /// instruction from after the call to before the call, assuming that all | 441 /// instruction from after the call to before the call, assuming that all |
450 /// instructions between the call and this instruction are movable. | 442 /// instructions between the call and this instruction are movable. |
451 /// | 443 /// |
452 bool TailCallElim::CanMoveAboveCall(Instruction *I, CallInst *CI) { | 444 bool TailCallElim::CanMoveAboveCall(Instruction *I, CallInst *CI) { |
453 // FIXME: We can move load/store/call/free instructions above the call if the | 445 // FIXME: We can move load/store/call/free instructions above the call if the |
462 // does not write to memory and the load provably won't trap. | 454 // does not write to memory and the load provably won't trap. |
463 // FIXME: Writes to memory only matter if they may alias the pointer | 455 // FIXME: Writes to memory only matter if they may alias the pointer |
464 // being loaded from. | 456 // being loaded from. |
465 if (CI->mayWriteToMemory() || | 457 if (CI->mayWriteToMemory() || |
466 !isSafeToLoadUnconditionally(L->getPointerOperand(), L, | 458 !isSafeToLoadUnconditionally(L->getPointerOperand(), L, |
467 L->getAlignment(), DL)) | 459 L->getAlignment())) |
468 return false; | 460 return false; |
469 } | 461 } |
470 } | 462 } |
471 | 463 |
472 // Otherwise, if this is a side-effect free instruction, check to make sure | 464 // Otherwise, if this is a side-effect free instruction, check to make sure |
478 if (I->getOperand(i) == CI) | 470 if (I->getOperand(i) == CI) |
479 return false; | 471 return false; |
480 return true; | 472 return true; |
481 } | 473 } |
482 | 474 |
483 // isDynamicConstant - Return true if the specified value is the same when the | 475 /// Return true if the specified value is the same when the return would exit |
484 // return would exit as it was when the initial iteration of the recursive | 476 /// as it was when the initial iteration of the recursive function was executed. |
485 // function was executed. | 477 /// |
486 // | 478 /// We currently handle static constants and arguments that are not modified as |
487 // We currently handle static constants and arguments that are not modified as | 479 /// part of the recursion. |
488 // part of the recursion. | |
489 // | |
490 static bool isDynamicConstant(Value *V, CallInst *CI, ReturnInst *RI) { | 480 static bool isDynamicConstant(Value *V, CallInst *CI, ReturnInst *RI) { |
491 if (isa<Constant>(V)) return true; // Static constants are always dyn consts | 481 if (isa<Constant>(V)) return true; // Static constants are always dyn consts |
492 | 482 |
493 // Check to see if this is an immutable argument, if so, the value | 483 // Check to see if this is an immutable argument, if so, the value |
494 // will be available to initialize the accumulator. | 484 // will be available to initialize the accumulator. |
516 | 506 |
517 // Not a constant or immutable argument, we can't safely transform. | 507 // Not a constant or immutable argument, we can't safely transform. |
518 return false; | 508 return false; |
519 } | 509 } |
520 | 510 |
521 // getCommonReturnValue - Check to see if the function containing the specified | 511 /// Check to see if the function containing the specified tail call consistently |
522 // tail call consistently returns the same runtime-constant value at all exit | 512 /// returns the same runtime-constant value at all exit points except for |
523 // points except for IgnoreRI. If so, return the returned value. | 513 /// IgnoreRI. If so, return the returned value. |
524 // | |
525 static Value *getCommonReturnValue(ReturnInst *IgnoreRI, CallInst *CI) { | 514 static Value *getCommonReturnValue(ReturnInst *IgnoreRI, CallInst *CI) { |
526 Function *F = CI->getParent()->getParent(); | 515 Function *F = CI->getParent()->getParent(); |
527 Value *ReturnedValue = nullptr; | 516 Value *ReturnedValue = nullptr; |
528 | 517 |
529 for (Function::iterator BBI = F->begin(), E = F->end(); BBI != E; ++BBI) { | 518 for (Function::iterator BBI = F->begin(), E = F->end(); BBI != E; ++BBI) { |
543 ReturnedValue = RetOp; | 532 ReturnedValue = RetOp; |
544 } | 533 } |
545 return ReturnedValue; | 534 return ReturnedValue; |
546 } | 535 } |
547 | 536 |
548 /// CanTransformAccumulatorRecursion - If the specified instruction can be | 537 /// If the specified instruction can be transformed using accumulator recursion |
549 /// transformed using accumulator recursion elimination, return the constant | 538 /// elimination, return the constant which is the start of the accumulator |
550 /// which is the start of the accumulator value. Otherwise return null. | 539 /// value. Otherwise return null. |
551 /// | |
552 Value *TailCallElim::CanTransformAccumulatorRecursion(Instruction *I, | 540 Value *TailCallElim::CanTransformAccumulatorRecursion(Instruction *I, |
553 CallInst *CI) { | 541 CallInst *CI) { |
554 if (!I->isAssociative() || !I->isCommutative()) return nullptr; | 542 if (!I->isAssociative() || !I->isCommutative()) return nullptr; |
555 assert(I->getNumOperands() == 2 && | 543 assert(I->getNumOperands() == 2 && |
556 "Associative/commutative operations should have 2 args!"); | 544 "Associative/commutative operations should have 2 args!"); |
834 DEBUG(dbgs() << "FOLDING: " << *BB | 822 DEBUG(dbgs() << "FOLDING: " << *BB |
835 << "INTO UNCOND BRANCH PRED: " << *Pred); | 823 << "INTO UNCOND BRANCH PRED: " << *Pred); |
836 ReturnInst *RI = FoldReturnIntoUncondBranch(Ret, BB, Pred); | 824 ReturnInst *RI = FoldReturnIntoUncondBranch(Ret, BB, Pred); |
837 | 825 |
838 // Cleanup: if all predecessors of BB have been eliminated by | 826 // Cleanup: if all predecessors of BB have been eliminated by |
839 // FoldReturnIntoUncondBranch, we would like to delete it, but we | 827 // FoldReturnIntoUncondBranch, delete it. It is important to empty it, |
840 // can not just nuke it as it is being used as an iterator by our caller. | 828 // because the ret instruction in there is still using a value which |
841 // Just empty it, and the caller will erase it when it is safe to do so. | 829 // EliminateRecursiveTailCall will attempt to remove. |
842 // It is important to empty it, because the ret instruction in there is | |
843 // still using a value which EliminateRecursiveTailCall will attempt | |
844 // to remove. | |
845 if (!BB->hasAddressTaken() && pred_begin(BB) == pred_end(BB)) | 830 if (!BB->hasAddressTaken() && pred_begin(BB) == pred_end(BB)) |
846 BB->getInstList().clear(); | 831 BB->eraseFromParent(); |
847 | 832 |
848 EliminateRecursiveTailCall(CI, RI, OldEntry, TailCallsAreMarkedTail, | 833 EliminateRecursiveTailCall(CI, RI, OldEntry, TailCallsAreMarkedTail, |
849 ArgumentPHIs, | 834 ArgumentPHIs, |
850 CannotTailCallElimCallsMarkedTail); | 835 CannotTailCallElimCallsMarkedTail); |
851 ++NumRetDuped; | 836 ++NumRetDuped; |