Move TailRecursionElimination to new OptimizationRemarkEmitter API

[lenary]

Summary

This changes the TailRecursionElimination pass to use
the new OptimizationRemarkEmitter API available during
function passes.

[lenary]

This closes https://bugs.llvm.org/show_bug.cgi?id=33788

This commit almost certainly needs work, I'm new to the llvm codebase. I also don't fully understand arc, I think I have the right lists subscribed and have asked for reviews from the right people, but I'm not sure.

[anemet]

Bummer, looks like you and @davide both worked on the same pass: D35570 and came up with very similar patches. @davide did you make progress since the last rev?

[davide]

In D35606#814077, @lenary wrote:

This closes https://bugs.llvm.org/show_bug.cgi?id=33788

This commit almost certainly needs work, I'm new to the llvm codebase. I also don't fully understand arc, I think I have the right lists subscribed and have asked for reviews from the right people, but I'm not sure.

This seems to be a duplicate of https://reviews.llvm.org/D35570

[davide]

In D35606#814083, @anemet wrote:

Bummer, looks like you and @davide both worked on the same pass: D35570 and came up with very similar patches. @davide did you make progress since the last rev?

I have a new version of the patch with tests on my work machine. @lenary, if you want to work on this, I'm fine with it.

[lenary]

I have just discovered that I have a failing test, in test/Other/new-pm-thinlto-defaults.ll Yours will probably fail there too.

@davide I'll defer to you and your patch on this, given you have comments etc. No worries from me about my duplicated effort.

[davide]

In D35606#814098, @lenary wrote:

I have just discovered that I have a failing test, in test/Other/new-pm-thinlto-defaults.ll Yours will probably fail there too.

@davide I'll defer to you and your patch on this, given you have comments etc. No worries from me about my duplicated effort.

OK. FWIW, if you want to work on any other pass conversion you may want to assign the PR to you to avoid duplication (I was sloppy in this regard, but hey, I didn't think somebody else was interested otherwise I wouldn't have started :)
Also, you may want to subscribe to the llvm-commits mailing list because phabricator reviews mail are sent there.

lib/Transforms/Scalar/TailRecursionElimination.cpp

 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/CaptureTracking.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/InlineCost.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/Loads.h"
+#include "llvm/Analysis/OptimizationDiagnosticInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DerivedTypes.h"
-#include "llvm/IR/DiagnosticInfo.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/InstIterator.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/ValueHandle.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Debug.h"
if (!CS.onlyReadsMemory())
       EscapePoints.insert(CS.getInstruction());
   }
 
   SmallPtrSet<Instruction *, 32> AllocaUsers;
   SmallPtrSet<Instruction *, 32> EscapePoints;
 };
 }
 
-static bool markTails(Function &F, bool &AllCallsAreTailCalls) {
+static bool markTails(Function &F, bool &AllCallsAreTailCalls,
+                      OptimizationRemarkEmitter *ORE) {
   if (F.callsFunctionThatReturnsTwice())
     return false;
   AllCallsAreTailCalls = true;
 
   // The local stack holds all alloca instructions and all byval arguments.
   AllocaDerivedValueTracker Tracker;
   for (Argument &Arg : F.args()) {
     if (Arg.hasByValAttr())
for (auto &I : *BB) {
             continue;
           if (Argument *A = dyn_cast<Argument>(Arg.getUser()))
             if (!A->hasByValAttr())
               continue;
           SafeToTail = false;
           break;
         }
         if (SafeToTail) {
-          emitOptimizationRemark(
-              F.getContext(), "tailcallelim", F, CI->getDebugLoc(),
-              "marked this readnone call a tail call candidate");
+          ORE->emit(OptimizationRemark(DEBUG_TYPE, "tailcallelim", CI)
+                    << "marked this readnone call a tail call candidate");
           CI->setTailCall();
           Modified = true;
           continue;
         }
       }
 
       if (!IsNoTail && Escaped == UNESCAPED && !Tracker.AllocaUsers.count(CI)) {
         DeferredTails.push_back(CI);
if (!WorklistEscaped.empty()) {
       }
     }
   } while (BB);
 
   for (CallInst *CI : DeferredTails) {
     if (Visited[CI->getParent()] != ESCAPED) {
       // If the escape point was part way through the block, calls after the
       // escape point wouldn't have been put into DeferredTails.
-      emitOptimizationRemark(F.getContext(), "tailcallelim", F,
-                             CI->getDebugLoc(),
-                             "marked this call a tail call candidate");
+      ORE->emit(OptimizationRemark(DEBUG_TYPE, "tailcallelim", CI)
+                << "marked this call a tail call candidate");
       CI->setTailCall();
       Modified = true;
     } else {
       AllCallsAreTailCalls = false;
     }
   }
 
   return Modified;
static CallInst *findTRECandidate(Instruction *TI,
 
   return CI;
 }
 
 static bool eliminateRecursiveTailCall(CallInst *CI, ReturnInst *Ret,
                                        BasicBlock *&OldEntry,
                                        bool &TailCallsAreMarkedTail,
                                        SmallVectorImpl<PHINode *> &ArgumentPHIs,
-                                       AliasAnalysis *AA) {
+                                       AliasAnalysis *AA,
+                                       OptimizationRemarkEmitter *ORE) {
   // If we are introducing accumulator recursion to eliminate operations after
   // the call instruction that are both associative and commutative, the initial
   // value for the accumulator is placed in this variable.  If this value is set
   // then we actually perform accumulator recursion elimination instead of
   // simple tail recursion elimination.  If the operation is an LLVM instruction
   // (eg: "add") then it is recorded in AccumulatorRecursionInstr.  If not, then
   // we are handling the case when the return instruction returns a constant C
   // which is different to the constant returned by other return instructions
if (Ret->getNumOperands() == 1 && Ret->getReturnValue() != CI &&
     AccumulatorRecursionEliminationInitVal = getCommonReturnValue(Ret, CI);
     if (!AccumulatorRecursionEliminationInitVal)
       return false;
   }
 
   BasicBlock *BB = Ret->getParent();
   Function *F = BB->getParent();
 
-  emitOptimizationRemark(F->getContext(), "tailcallelim", *F, CI->getDebugLoc(),
-                         "transforming tail recursion to loop");
+  ORE->emit(OptimizationRemark(DEBUG_TYPE, "tailcallelim", CI)
+            << "transforming tail recursion to loop");
 
   // OK! We can transform this tail call.  If this is the first one found,
   // create the new entry block, allowing us to branch back to the old entry.
   if (!OldEntry) {
     OldEntry = &F->getEntryBlock();
     BasicBlock *NewEntry = BasicBlock::Create(F->getContext(), "", F, OldEntry);
     NewEntry->takeName(OldEntry);
     OldEntry->setName("tailrecurse");

 }
 
 static bool foldReturnAndProcessPred(BasicBlock *BB, ReturnInst *Ret,
                                      BasicBlock *&OldEntry,
                                      bool &TailCallsAreMarkedTail,
                                      SmallVectorImpl<PHINode *> &ArgumentPHIs,
                                      bool CannotTailCallElimCallsMarkedTail,
                                      const TargetTransformInfo *TTI,
-                                     AliasAnalysis *AA) {
+                                     AliasAnalysis *AA,
+                                     OptimizationRemarkEmitter *ORE) {
   bool Change = false;
 
   // Make sure this block is a trivial return block.
   assert(BB->getFirstNonPHIOrDbg() == Ret &&
          "Trying to fold non-trivial return block");
 
   // If the return block contains nothing but the return and PHI's,
   // there might be an opportunity to duplicate the return in its
if (CallInst *CI = findTRECandidate(BI, CannotTailCallElimCallsMarkedTail, TTI)){
       // Cleanup: if all predecessors of BB have been eliminated by
       // FoldReturnIntoUncondBranch, delete it.  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->eraseFromParent();
 
       eliminateRecursiveTailCall(CI, RI, OldEntry, TailCallsAreMarkedTail,
-                                 ArgumentPHIs, AA);
+                                 ArgumentPHIs, AA, ORE);
       ++NumRetDuped;
       Change = true;
     }
   }
 
   return Change;
 }
 
 static bool processReturningBlock(ReturnInst *Ret, BasicBlock *&OldEntry,
                                   bool &TailCallsAreMarkedTail,
                                   SmallVectorImpl<PHINode *> &ArgumentPHIs,
                                   bool CannotTailCallElimCallsMarkedTail,
                                   const TargetTransformInfo *TTI,
-                                  AliasAnalysis *AA) {
+                                  AliasAnalysis *AA,
+                                  OptimizationRemarkEmitter *ORE) {
   CallInst *CI = findTRECandidate(Ret, CannotTailCallElimCallsMarkedTail, TTI);
   if (!CI)
     return false;
 
   return eliminateRecursiveTailCall(CI, Ret, OldEntry, TailCallsAreMarkedTail,
-                                    ArgumentPHIs, AA);
+                                    ArgumentPHIs, AA, ORE);
 }
 
 static bool eliminateTailRecursion(Function &F, const TargetTransformInfo *TTI,
-                                   AliasAnalysis *AA) {
+                                   AliasAnalysis *AA, OptimizationRemarkEmitter *ORE) {
   if (F.getFnAttribute("disable-tail-calls").getValueAsString() == "true")
     return false;
 
   bool MadeChange = false;
   bool AllCallsAreTailCalls = false;
-  MadeChange |= markTails(F, AllCallsAreTailCalls);
+  MadeChange |= markTails(F, AllCallsAreTailCalls, ORE);
   if (!AllCallsAreTailCalls)
     return MadeChange;
 
   // If this function is a varargs function, we won't be able to PHI the args
   // right, so don't even try to convert it...
   if (F.getFunctionType()->isVarArg())
     return false;
 
static bool eliminateTailRecursion(Function &F, const TargetTransformInfo *TTI,
   // 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.
   for (Function::iterator BBI = F.begin(), E = F.end(); BBI != E; /*in loop*/) {
     BasicBlock *BB = &*BBI++; // foldReturnAndProcessPred may delete BB.
     if (ReturnInst *Ret = dyn_cast<ReturnInst>(BB->getTerminator())) {
       bool Change =
           processReturningBlock(Ret, OldEntry, TailCallsAreMarkedTail,
-                                ArgumentPHIs, !CanTRETailMarkedCall, TTI, AA);
+                                ArgumentPHIs, !CanTRETailMarkedCall, TTI, AA, ORE);
       if (!Change && BB->getFirstNonPHIOrDbg() == Ret)
         Change = foldReturnAndProcessPred(BB, Ret, OldEntry,
                                           TailCallsAreMarkedTail, ArgumentPHIs,
-                                          !CanTRETailMarkedCall, TTI, AA);
+                                          !CanTRETailMarkedCall, TTI, AA, ORE);
       MadeChange |= Change;
     }
   }
 
   // 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
struct TailCallElim : public FunctionPass {
   static char ID; // Pass identification, replacement for typeid
   TailCallElim() : FunctionPass(ID) {
     initializeTailCallElimPass(*PassRegistry::getPassRegistry());
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<TargetTransformInfoWrapperPass>();
     AU.addRequired<AAResultsWrapperPass>();
+    AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
     AU.addPreserved<GlobalsAAWrapperPass>();
   }
 
   bool runOnFunction(Function &F) override {
     if (skipFunction(F))
       return false;
 
     return eliminateTailRecursion(
         F, &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F),
-        &getAnalysis<AAResultsWrapperPass>().getAAResults());
+        &getAnalysis<AAResultsWrapperPass>().getAAResults(),
+        &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE());
   }
 };
 }
 
 char TailCallElim::ID = 0;
 INITIALIZE_PASS_BEGIN(TailCallElim, "tailcallelim", "Tail Call Elimination",
                       false, false)
 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass)
 INITIALIZE_PASS_END(TailCallElim, "tailcallelim", "Tail Call Elimination",
                     false, false)
 
 // Public interface to the TailCallElimination pass
 FunctionPass *llvm::createTailCallEliminationPass() {
   return new TailCallElim();
 }
 
 PreservedAnalyses TailCallElimPass::run(Function &F,
                                         FunctionAnalysisManager &AM) {
 
   TargetTransformInfo &TTI = AM.getResult<TargetIRAnalysis>(F);
   AliasAnalysis &AA = AM.getResult<AAManager>(F);
+  OptimizationRemarkEmitter &ORE = AM.getResult<OptimizationRemarkEmitterAnalysis>(F);
 
-  bool Changed = eliminateTailRecursion(F, &TTI, &AA);
+  bool Changed = eliminateTailRecursion(F, &TTI, &AA, &ORE);
 
   if (!Changed)
     return PreservedAnalyses::all();
   PreservedAnalyses PA;
   PA.preserve<GlobalsAA>();
   return PA;
 }