Don't modify LibFuncs in DeadArgumentElimination or ArgumentPromotion

[jgravelle-google]

Summary

When performing IPO, it's possible to modify function signatures to simplify things. There are also passes that make assumptions about LibFunc signatures, notably DeadStoreElimination, which crashes when strcpy, strncpy, strcat, or strncat have their arugments removed.
When including libc function definitions and running IPO, LibFunc signatures can be simplified, which can invalidate those assumptions. This patch adds checks to passes that modify signatures to exclude LibFuncs.

[dschuff]

A nit about the commit message: it's not just LTO passes that make assumptions about known library functions, lots of passes do. Also I might be just a little bit more explicit than "when statically linking libc" and make it "when including libc in LTO"
Otherwise LGTM

lib/Transforms/IPO/DeadArgumentElimination.cpp

83

I guess this isn't really a DummyMAM anymore if we are registering analyses on it?

[tejohnson]

In D48404#1138623, @dschuff wrote:

A nit about the commit message: it's not just LTO passes that make assumptions about known library functions, lots of passes do. Also I might be just a little bit more explicit than "when statically linking libc" and make it "when including libc in LTO"
Otherwise LGTM

Is this an issue with LTO specifically (link time optimization) or just IPO passes in general? The test case doesn't seem to involve LTO.

[jgravelle-google]

Probably just IPO then. It's still not WebAssembly specific.

Is there a good place to put the testcase? I guess test/Other?

lib/Transforms/IPO/DeadArgumentElimination.cpp

83

Not sure. I can't find any non-PassManager, non-test uses of registerPass other than things like https://github.com/llvm-mirror/llvm/blob/baa9ccee6421c045f639b492189da86b7e2a32dd/lib/Transforms/IPO/GlobalDCE.cpp#L58 , which every callsite I can find calls FunctionAnalysisManagerModuleProxy(DummyFAM), which probably still counts as being a Dummy.
Ideally here I'd like to register this pass as requiring TargetLibraryInfo and reusing a possibly-existing analysis, but I couldn't get that to work.

[jgravelle-google]

• Move test, remove triple

[tejohnson]

In D48404#1139705, @jgravelle-google wrote:

Probably just IPO then. It's still not WebAssembly specific.

Please update the patch description.

Is there a good place to put the testcase? I guess test/Other?

Better would be the appropriate subdirectory of test/Transforms. Although you should split your test - one for dead arg elim and one for arg promotion.

What happens without this patch - incorrect behavior or other missed optimization opportunities? Are we losing anything important by preventing the optimizations?

[jgravelle-google]

Better would be the appropriate subdirectory of test/Transforms.

In theory because the actual crash is in DeadStoreElimination I could put it there?

Although you should split your test - one for dead arg elim and one for arg promotion.

I figured because it was the same input bitcode that causes issues it made sense to keep it as one file. Although it might make more sense to have it be two separate calls to opt to make it clearer.
The other thought was I don't want *any* passes in -std-link-opts to cause this issue, so this test should catch new passes that overlook the same weird edge case.
The minimal subset of reproducing passes for the first case is -internalize -ipsccp -deadargelim -dse

What happens without this patch - incorrect behavior or other missed optimization opportunities? Are we losing anything important by preventing the optimizations?

Edited the commit message to make it clearer what the problem was - we crash in DeadStoreElimination. (Specifically here: https://github.com/llvm-mirror/llvm/blob/5119d140c565456349a27c45b52be5a81b18ffe0/lib/Transforms/Scalar/DeadStoreElimination.cpp#L216)

[lebedev.ri]

lib/Transforms/IPO/ArgumentPromotion.cpp

831–832

This reads weird.
Are you sure you didn't mean:

// Don't promote arguments for library functions,
// because later passes may make assumptions about library function signatures.

[efriedma]

Maybe instead of trying to turn off optimizations on internal builtin functions, we should instead try to make optimizations not treat functions with local linkage as builtin? Not sure. This came up before on llvmdev, but we didn't really decide one way or the other.

If you're going to go with this approach, we probably also need to fix a bunch of other places that call hasLocalLinkage: llvm::canTrackArgumentsInterprocedurally is used by IPSCCP, GlobalOpt will change the calling convention of function definitions, etc.

Regardless of which approach we choose, DSE should be fixed to use getLibFunc() so it doesn't crash on invalid input.

[efriedma]

Also, LTO currently calls TargetLibraryInfo::disableAllFunctions to avoid this problem.

[dschuff]

Just ran across this again. @jgravelle-google is this still relevant?

lib/Transforms/IPO/ArgumentPromotion.cpp

831–832

+1, this is better wording (and is the intent for this change).

include/llvm/Transforms/IPO/DeadArgumentElimination.h

 #include <map>
 #include <set>
 #include <string>
 #include <tuple>
 
 namespace llvm {
 
 class Module;
+class TargetLibraryInfo;
 class Use;
 class Value;
 
 /// Eliminate dead arguments (and return values) from functions.
 class DeadArgumentEliminationPass
     : public PassInfoMixin<DeadArgumentEliminationPass> {
 public:
   /// Struct that represents (part of) either a return value or a function
public:
   bool ShouldHackArguments = false;
 
 private:
   Liveness MarkIfNotLive(RetOrArg Use, UseVector &MaybeLiveUses);
   Liveness SurveyUse(const Use *U, UseVector &MaybeLiveUses,
                      unsigned RetValNum = -1U);
   Liveness SurveyUses(const Value *V, UseVector &MaybeLiveUses);
 
-  void SurveyFunction(const Function &F);
+  void SurveyFunction(const Function &F, const TargetLibraryInfo &TLI);
   void MarkValue(const RetOrArg &RA, Liveness L,
                  const UseVector &MaybeLiveUses);
   void MarkLive(const RetOrArg &RA);
   void MarkLive(const Function &F);
   void PropagateLiveness(const RetOrArg &RA);
   bool RemoveDeadStuffFromFunction(Function *F);
   bool DeleteDeadVarargs(Function &Fn);
   bool RemoveDeadArgumentsFromCallers(Function &Fn);
 };
 
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_IPO_DEADARGUMENTELIMINATION_H

lib/Transforms/IPO/ArgumentPromotion.cpp

 /// PromoteArguments - This method checks the specified function to see if there
 /// are any promotable arguments and if it is safe to promote the function (for
 /// example, all callers are direct).  If safe to promote some arguments, it
 /// calls the DoPromotion method.
 static Function *
 promoteArguments(Function *F, function_ref<AAResults &(Function &F)> AARGetter,
                  unsigned MaxElements,
                  Optional<function_ref<void(CallSite OldCS, CallSite NewCS)>>
-                     ReplaceCallSite) {
+                     ReplaceCallSite,
+                 const TargetLibraryInfo &TLI) {
   // Don't perform argument promotion for naked functions; otherwise we can end
   // up removing parameters that are seemingly 'not used' as they are referred
   // to in the assembly.
   if(F->hasFnAttribute(Attribute::Naked))
     return nullptr;
 
   // Make sure that it is local to this module.
   if (!F->hasLocalLinkage())
     return nullptr;
 
+  // Don't promote arguments for library functions. We can make assumptions
+  // about library function signatures in later passes.
+  LibFunc LF;
+  if (TLI.getLibFunc(*F, LF))
+    return nullptr;
+
   // Don't promote arguments for variadic functions. Adding, removing, or
   // changing non-pack parameters can change the classification of pack
   // parameters. Frontends encode that classification at the call site in the
   // IR, while in the callee the classification is determined dynamically based
   // on the number of registers consumed so far.
   if (F->isVarArg())
     return nullptr;
 
for (LazyCallGraph::Node &N : C) {
       FunctionAnalysisManager &FAM =
           AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
       // FIXME: This lambda must only be used with this function. We should
       // skip the lambda and just get the AA results directly.
       auto AARGetter = [&](Function &F) -> AAResults & {
         assert(&F == &OldF && "Called with an unexpected function!");
         return FAM.getResult<AAManager>(F);
       };
+      const TargetLibraryInfo *TLI = &FAM.getResult<TargetLibraryAnalysis>(OldF);
 
-      Function *NewF = promoteArguments(&OldF, AARGetter, MaxElements, None);
+      Function *NewF = promoteArguments(&OldF, AARGetter, MaxElements, None,
+                                        *TLI);
       if (!NewF)
         continue;
       LocalChange = true;
 
       // Directly substitute the functions in the call graph. Note that this
       // requires the old function to be completely dead and completely
       // replaced by the new function. It does no call graph updates, it merely
       // swaps out the particular function mapped to a particular node in the

 
 bool ArgPromotion::runOnSCC(CallGraphSCC &SCC) {
   if (skipSCC(SCC))
     return false;
 
   // Get the callgraph information that we need to update to reflect our
   // changes.
   CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
+  TargetLibraryInfo const& TLI =
+    getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
 
   LegacyAARGetter AARGetter(*this);
 
   bool Changed = false, LocalChange;
 
   // Iterate until we stop promoting from this SCC.
   do {
     LocalChange = false;
     // Attempt to promote arguments from all functions in this SCC.
     for (CallGraphNode *OldNode : SCC) {
       Function *OldF = OldNode->getFunction();
       if (!OldF)
         continue;
 
       auto ReplaceCallSite = [&](CallSite OldCS, CallSite NewCS) {
         Function *Caller = OldCS.getInstruction()->getParent()->getParent();
         CallGraphNode *NewCalleeNode =
             CG.getOrInsertFunction(NewCS.getCalledFunction());
         CallGraphNode *CallerNode = CG[Caller];
         CallerNode->replaceCallEdge(OldCS, NewCS, NewCalleeNode);
       };
 
       if (Function *NewF = promoteArguments(OldF, AARGetter, MaxElements,
-                                            {ReplaceCallSite})) {
+                                            {ReplaceCallSite}, TLI)) {
         LocalChange = true;
 
         // Update the call graph for the newly promoted function.
         CallGraphNode *NewNode = CG.getOrInsertFunction(NewF);
         NewNode->stealCalledFunctionsFrom(OldNode);
         if (OldNode->getNumReferences() == 0)
           delete CG.removeFunctionFromModule(OldNode);
         else

lib/Transforms/IPO/DeadArgumentElimination.cpp

 // This pass is often useful as a cleanup pass to run after aggressive
 // interprocedural passes, which add possibly-dead arguments or return values.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/IPO/DeadArgumentElimination.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/IR/Argument.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Function.h"
DAE() : ModulePass(ID) {
       initializeDAEPass(*PassRegistry::getPassRegistry());
     }
 
     bool runOnModule(Module &M) override {
       if (skipModule(M))
         return false;
       DeadArgumentEliminationPass DAEP(ShouldHackArguments());
       ModuleAnalysisManager DummyMAM;
+      DummyMAM.registerPass([&] { return TargetLibraryAnalysis(); });
       PreservedAnalyses PA = DAEP.run(M, DummyMAM);
       return !PA.areAllPreserved();
     }
 
     virtual bool ShouldHackArguments() const { return false; }
   };
 
 } // end anonymous namespace

 
 // SurveyFunction - This performs the initial survey of the specified function,
 // checking out whether or not it uses any of its incoming arguments or whether
 // any callers use the return value.  This fills in the LiveValues set and Uses
 // map.
 //
 // We consider arguments of non-internal functions to be intrinsically alive as
 // well as arguments to functions which have their "address taken".
-void DeadArgumentEliminationPass::SurveyFunction(const Function &F) {
+void DeadArgumentEliminationPass::SurveyFunction(const Function &F,
+                                                 const TargetLibraryInfo &TLI) {
   // Functions with inalloca parameters are expecting args in a particular
   // register and memory layout.
   if (F.getAttributes().hasAttrSomewhere(Attribute::InAlloca)) {
     MarkLive(F);
     return;
   }
 
   // Don't touch naked functions. The assembly might be using an argument, or
if (BB->getTerminatingMustTailCall() != nullptr)
       HasMustTailCalls = true;
   }
 
   if (HasMustTailCalls) {
     LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - " << F.getName()
                       << " has musttail calls\n");
   }
 
-  if (!F.hasLocalLinkage() && (!ShouldHackArguments || F.isIntrinsic())) {
+  bool CanTouchArguments = ShouldHackArguments && !F.isIntrinsic();
+  LibFunc LF;
+  bool IsLibFunc = TLI.getLibFunc(F, LF);
+  if ((!F.hasLocalLinkage() && !CanTouchArguments) || IsLibFunc) {
     MarkLive(F);
     return;
   }
 
   LLVM_DEBUG(
       dbgs() << "DeadArgumentEliminationPass - Inspecting callers for fn: "
              << F.getName() << "\n");
   // Keep track of the number of live retvals, so we can skip checks once all
bool DeadArgumentEliminationPass::RemoveDeadStuffFromFunction(Function *F) {
 
   // Now that the old function is dead, delete it.
   F->eraseFromParent();
 
   return true;
 }
 
 PreservedAnalyses DeadArgumentEliminationPass::run(Module &M,
-                                                   ModuleAnalysisManager &) {
+                                                   ModuleAnalysisManager &AM) {
   bool Changed = false;
+  const TargetLibraryInfo *TLI = &AM.getResult<TargetLibraryAnalysis>(M);
 
   // First pass: Do a simple check to see if any functions can have their "..."
   // removed.  We can do this if they never call va_start.  This loop cannot be
   // fused with the next loop, because deleting a function invalidates
   // information computed while surveying other functions.
   LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Deleting dead varargs\n");
   for (Module::iterator I = M.begin(), E = M.end(); I != E; ) {
     Function &F = *I++;
     if (F.getFunctionType()->isVarArg())
       Changed |= DeleteDeadVarargs(F);
   }
 
   // Second phase:loop through the module, determining which arguments are live.
   // We assume all arguments are dead unless proven otherwise (allowing us to
   // determine that dead arguments passed into recursive functions are dead).
   //
   LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Determining liveness\n");
   for (auto &F : M)
-    SurveyFunction(F);
+    SurveyFunction(F, *TLI);
 
   // Now, remove all dead arguments and return values from each function in
   // turn.
   for (Module::iterator I = M.begin(), E = M.end(); I != E; ) {
     // Increment now, because the function will probably get removed (ie.
     // replaced by a new one).
     Function *F = &*I++;
     Changed |= RemoveDeadStuffFromFunction(F);

test/Other/ipo-libfunc-signature.ll

+; RUN: opt %s -S -internalize -internalize-public-api-list=main -std-link-opts | FileCheck %s
+
+@Msg = hidden global [32 x i8] zeroinitializer, align 16
[e-mail] = internal global [64 x i8] zeroinitializer, align 16
+
+; Function Attrs: nounwind
+define hidden void @main() local_unnamed_addr {
+entry:
+  %call150 = call i8* @strcat(
+    i8* getelementptr inbounds ([64 x i8], [64 x i8]* @main.Parms, i32 0, i32 0),
+    i8* getelementptr inbounds ([32 x i8], [32 x i8]* @Msg, i32 0, i32 0))
+  ret void
+}
+
+declare hidden i8* @strcpy(i8* noalias returned, i8* noalias) local_unnamed_addr
+declare hidden i32 @strlen(i8* %s) local_unnamed_addr
+
+
+; CHECK: define{{.*}}i8* @strcat(i8*{{.*}}%dest, i8*{{.*}}%src)
+; Function Attrs: noinline nounwind optsize
+define hidden i8* @strcat(i8* noalias returned %dest, i8* noalias %src) local_unnamed_addr #0 {
+entry:
+  %call = tail call i32 @strlen(i8* %dest)
+  %add.ptr = getelementptr inbounds i8, i8* %dest, i32 %call
+  %call1 = tail call i8* @strcpy(i8* %add.ptr, i8* %src)
+  ret i8* %dest
+}
+
+attributes #0 = { noinline nounwind optsize }