Members/tobaru/cbc/CbC_llvm: lib/Transforms/Scalar/TailRecursionElimination.cpp comparison

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

-:f3e34b893a5f
+:afa8332a0e37
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/GlobalsModRef.h"
+#include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/CaptureTracking.h"
-#include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/InlineCost.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/Loads.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/IR/CFG.h"
 STATISTIC(NumAccumAdded, "Number of accumulators introduced");
 namespace {
 struct TailCallElim : public FunctionPass {
 const TargetTransformInfo *TTI;
-const DataLayout *DL;
 static char ID; // Pass identification, replacement for typeid
 TailCallElim() : FunctionPass(ID) {
 initializeTailCallElimPass(*PassRegistry::getPassRegistry());
 }
 return new TailCallElim();
 }
 void TailCallElim::getAnalysisUsage(AnalysisUsage &AU) const {
 AU.addRequired<TargetTransformInfoWrapperPass>();
+AU.addPreserved<GlobalsAAWrapperPass>();
 }
 /// \brief Scan the specified function for alloca instructions.
 /// If it contains any dynamic allocas, returns false.
 static bool CanTRE(Function &F) {
 bool TailCallElim::runOnFunction(Function &F) {
 if (skipOptnoneFunction(F))
 return false;
-DL = F.getParent()->getDataLayout();
+if (F.getFnAttribute("disable-tail-calls").getValueAsString() == "true")
+return false;
 bool AllCallsAreTailCalls = false;
 bool Modified = markTails(F, AllCallsAreTailCalls);
 if (AllCallsAreTailCalls)
 Modified |= runTRE(F);
 BasicBlock *OldEntry = nullptr;
 bool TailCallsAreMarkedTail = false;
 SmallVector<PHINode*, 8> ArgumentPHIs;
 bool MadeChange = false;
-// CanTRETailMarkedCall - If false, we cannot perform TRE on tail calls
+// If false, we cannot perform TRE on tail calls marked with the 'tail'
-// marked with the 'tail' attribute, because doing so would cause the stack
+// attribute, because doing so would cause the stack size to increase (real
-// size to increase (real TRE would deallocate variable sized allocas, TRE
+// TRE would deallocate variable sized allocas, TRE doesn't).
-// doesn't).
 bool CanTRETailMarkedCall = CanTRE(F);
 // Change any tail recursive calls to loops.
 //
 // FIXME: The code generator produces really bad code when an 'escaping
 // alloca' is changed from being a static alloca to being a dynamic alloca.
 // Until this is resolved, disable this transformation if that would ever
 // happen.  This bug is PR962.
-SmallVector<BasicBlock*, 8> BBToErase;
+for (Function::iterator BBI = F.begin(), E = F.end(); BBI != E; /*in loop*/) {
-for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
+BasicBlock *BB = BBI++; // FoldReturnAndProcessPred may delete BB.
 if (ReturnInst *Ret = dyn_cast<ReturnInst>(BB->getTerminator())) {
 bool Change = ProcessReturningBlock(Ret, OldEntry, TailCallsAreMarkedTail,
 ArgumentPHIs, !CanTRETailMarkedCall);
-if (!Change && BB->getFirstNonPHIOrDbg() == Ret) {
+if (!Change && BB->getFirstNonPHIOrDbg() == Ret)
 Change = FoldReturnAndProcessPred(BB, Ret, OldEntry,
 TailCallsAreMarkedTail, ArgumentPHIs,
 !CanTRETailMarkedCall);
-// FoldReturnAndProcessPred may have emptied some BB. Remember to
-// erase them.
-if (Change && BB->empty())
-BBToErase.push_back(BB);
-}
 MadeChange |= Change;
 }
 }
-for (auto BB: BBToErase)
-BB->eraseFromParent();
 // If we eliminated any tail recursions, it's possible that we inserted some
 // silly PHI nodes which just merge an initial value (the incoming operand)
 // with themselves.  Check to see if we did and clean up our mess if so.  This
 // occurs when a function passes an argument straight through to its tail
 // call.
 for (unsigned i = 0, e = ArgumentPHIs.size(); i != e; ++i) {
 PHINode *PN = ArgumentPHIs[i];
 // If the PHI Node is a dynamic constant, replace it with the value it is.
-if (Value *PNV = SimplifyInstruction(PN)) {
+if (Value *PNV = SimplifyInstruction(PN, F.getParent()->getDataLayout())) {
 PN->replaceAllUsesWith(PNV);
 PN->eraseFromParent();
 }
 }
 return MadeChange;
 }
-/// CanMoveAboveCall - Return true if it is safe to move the specified
+/// Return true if it is safe to move the specified
 /// instruction from after the call to before the call, assuming that all
 /// instructions between the call and this instruction are movable.
 ///
 bool TailCallElim::CanMoveAboveCall(Instruction *I, CallInst *CI) {
 // FIXME: We can move load/store/call/free instructions above the call if the
 // does not write to memory and the load provably won't trap.
 // FIXME: Writes to memory only matter if they may alias the pointer
 // being loaded from.
 if (CI->mayWriteToMemory() ||
 !isSafeToLoadUnconditionally(L->getPointerOperand(), L,
-L->getAlignment(), DL))
+L->getAlignment()))
 return false;
 }
 }
 // Otherwise, if this is a side-effect free instruction, check to make sure
 if (I->getOperand(i) == CI)
 return false;
 return true;
 }
-// isDynamicConstant - Return true if the specified value is the same when the
+/// Return true if the specified value is the same when the return would exit
-// return would exit as it was when the initial iteration of the recursive
+/// as it was when the initial iteration of the recursive function was executed.
-// function was executed.
+///
-//
+/// We currently handle static constants and arguments that are not modified as
-// We currently handle static constants and arguments that are not modified as
+/// part of the recursion.
-// part of the recursion.
-//
 static bool isDynamicConstant(Value *V, CallInst *CI, ReturnInst *RI) {
 if (isa<Constant>(V)) return true; // Static constants are always dyn consts
 // Check to see if this is an immutable argument, if so, the value
 // will be available to initialize the accumulator.
 // Not a constant or immutable argument, we can't safely transform.
 return false;
 }
-// getCommonReturnValue - Check to see if the function containing the specified
+/// Check to see if the function containing the specified tail call consistently
-// tail call consistently returns the same runtime-constant value at all exit
+/// returns the same runtime-constant value at all exit points except for
-// points except for IgnoreRI.  If so, return the returned value.
+/// IgnoreRI. If so, return the returned value.
-//
 static Value *getCommonReturnValue(ReturnInst *IgnoreRI, CallInst *CI) {
 Function *F = CI->getParent()->getParent();
 Value *ReturnedValue = nullptr;
 for (Function::iterator BBI = F->begin(), E = F->end(); BBI != E; ++BBI) {
 ReturnedValue = RetOp;
 }
 return ReturnedValue;
 }
-/// CanTransformAccumulatorRecursion - If the specified instruction can be
+/// If the specified instruction can be transformed using accumulator recursion
-/// transformed using accumulator recursion elimination, return the constant
+/// elimination, return the constant which is the start of the accumulator
-/// which is the start of the accumulator value.  Otherwise return null.
+/// value.  Otherwise return null.
-///
 Value *TailCallElim::CanTransformAccumulatorRecursion(Instruction *I,
 CallInst *CI) {
 if (!I->isAssociative() || !I->isCommutative()) return nullptr;
 assert(I->getNumOperands() == 2 &&
 "Associative/commutative operations should have 2 args!");
 DEBUG(dbgs() << "FOLDING: " << *BB
 << "INTO UNCOND BRANCH PRED: " << *Pred);
 ReturnInst *RI = FoldReturnIntoUncondBranch(Ret, BB, Pred);
 // Cleanup: if all predecessors of BB have been eliminated by
-// FoldReturnIntoUncondBranch, we would like to delete it, but we
+// FoldReturnIntoUncondBranch, delete it.  It is important to empty it,
-// can not just nuke it as it is being used as an iterator by our caller.
+// because the ret instruction in there is still using a value which
-// Just empty it, and the caller will erase it when it is safe to do so.
+// EliminateRecursiveTailCall will attempt to remove.
-// It is important to empty it, because the ret instruction in there is
-// still using a value which EliminateRecursiveTailCall will attempt
-// to remove.
 if (!BB->hasAddressTaken() && pred_begin(BB) == pred_end(BB))
-BB->getInstList().clear();
+BB->eraseFromParent();
 EliminateRecursiveTailCall(CI, RI, OldEntry, TailCallsAreMarkedTail,
 ArgumentPHIs,
 CannotTailCallElimCallsMarkedTail);
 ++NumRetDuped;

Mercurial > hg > Members > tobaru > cbc > CbC_llvm

comparison lib/Transforms/Scalar/TailRecursionElimination.cpp @ 95:afa8332a0e37