[CFLAA] Recognize builtin allocation functions.

This patch extends CFLAA to recognize allocation functions such as
malloc, free, etc, so we can treat them more aggressively.

Patch by Jia Chen.

Differential Revision: http://reviews.llvm.org/D20776

llvm-svn: 271421

3 files changed, 92 insertions, 34 deletions

diff --git a/llvm/include/llvm/Analysis/CFLAliasAnalysis.h b/llvm/include/llvm/Analysis/CFLAliasAnalysis.h
index 5ee4dddb94e..9940b0be5eb 100644
--- a/llvm/include/llvm/Analysis/CFLAliasAnalysis.h
+++ b/llvm/include/llvm/Analysis/CFLAliasAnalysis.h
@@ -14,10 +14,10 @@
 #ifndef LLVM_ANALYSIS_CFLALIASANALYSIS_H
 #define LLVM_ANALYSIS_CFLALIASANALYSIS_H
 
-#include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/None.h"
 #include "llvm/ADT/Optional.h"
+#include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/ValueHandle.h"
@@ -26,13 +26,15 @@
 
 namespace llvm {
 
+class TargetLibraryInfo;
+
 class CFLAAResult : public AAResultBase<CFLAAResult> {
   friend AAResultBase<CFLAAResult>;
 
   struct FunctionInfo;
 
 public:
-  explicit CFLAAResult();
+  explicit CFLAAResult(const TargetLibraryInfo &);
   CFLAAResult(CFLAAResult &&Arg);
   ~CFLAAResult();
 
@@ -94,6 +96,8 @@ private:
     }
   };
 
+  const TargetLibraryInfo &TLI;
+
   /// \brief Cached mapping of Functions to their StratifiedSets.
   /// If a function's sets are currently being built, it is marked
   /// in the cache as an Optional without a value. This way, if we
@@ -131,8 +135,7 @@ public:
   CFLAAResult &getResult() { return *Result; }
   const CFLAAResult &getResult() const { return *Result; }
 
-  bool doInitialization(Module &M) override;
-  bool doFinalization(Module &M) override;
+  void initializePass() override;
   void getAnalysisUsage(AnalysisUsage &AU) const override;
 };
 
diff --git a/llvm/lib/Analysis/CFLAliasAnalysis.cpp b/llvm/lib/Analysis/CFLAliasAnalysis.cpp
index 57c3f317c11..5b3e363ca35 100644
--- a/llvm/lib/Analysis/CFLAliasAnalysis.cpp
+++ b/llvm/lib/Analysis/CFLAliasAnalysis.cpp
@@ -38,6 +38,8 @@
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/None.h"
 #include "llvm/ADT/Optional.h"
+#include "llvm/Analysis/MemoryBuiltins.h"
+#include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/InstVisitor.h"
@@ -56,8 +58,10 @@ using namespace llvm;
 
 #define DEBUG_TYPE "cfl-aa"
 
-CFLAAResult::CFLAAResult() : AAResultBase() {}
-CFLAAResult::CFLAAResult(CFLAAResult &&Arg) : AAResultBase(std::move(Arg)) {}
+CFLAAResult::CFLAAResult(const TargetLibraryInfo &TLI)
+    : AAResultBase(), TLI(TLI) {}
+CFLAAResult::CFLAAResult(CFLAAResult &&Arg)
+    : AAResultBase(std::move(Arg)), TLI(Arg.TLI) {}
 CFLAAResult::~CFLAAResult() {}
 
 /// Information we have about a function and would like to keep around.
@@ -158,10 +162,12 @@ struct Edge {
 class GetEdgesVisitor : public InstVisitor<GetEdgesVisitor, void> {
   CFLAAResult &AA;
   SmallVectorImpl<Edge> &Output;
+  const TargetLibraryInfo &TLI;
 
 public:
-  GetEdgesVisitor(CFLAAResult &AA, SmallVectorImpl<Edge> &Output)
-      : AA(AA), Output(Output) {}
+  GetEdgesVisitor(CFLAAResult &AA, SmallVectorImpl<Edge> &Output,
+                  const TargetLibraryInfo &TLI)
+      : AA(AA), Output(Output), TLI(TLI) {}
 
   void visitInstruction(Instruction &) {
     llvm_unreachable("Unsupported instruction encountered");
@@ -374,6 +380,20 @@ public:
   }
 
   template <typename InstT> void visitCallLikeInst(InstT &Inst) {
+    // Check if Inst is a call to a library function that allocates/deallocates
+    // on the heap. Those kinds of functions do not introduce any aliases.
+    // TODO: address other common library functions such as realloc(), strdup(),
+    // etc.
+    if (isMallocLikeFn(&Inst, &TLI) || isCallocLikeFn(&Inst, &TLI)) {
+      Output.push_back(Edge(&Inst, &Inst, EdgeType::Assign, AttrNone));
+      return;
+    } else if (isFreeCall(&Inst, &TLI)) {
+      assert(Inst.getNumArgOperands() == 1);
+      auto argVal = Inst.arg_begin()->get();
+      Output.push_back(Edge(argVal, argVal, EdgeType::Assign, AttrNone));
+      return;
+    }
+
     // TODO: Add support for noalias args/all the other fun function attributes
     // that we can tack on.
     SmallVector<Function *, 4> Targets;
@@ -642,10 +662,12 @@ static Optional<StratifiedAttr> valueToAttrIndex(Value *Val);
 static EdgeType flipWeight(EdgeType Initial);
 
 /// Gets edges of the given Instruction*, writing them to the SmallVector*.
-static void argsToEdges(CFLAAResult &, Instruction *, SmallVectorImpl<Edge> &);
+static void argsToEdges(CFLAAResult &, Instruction *, SmallVectorImpl<Edge> &,
+                        const TargetLibraryInfo &);
 
 /// Gets edges of the given ConstantExpr*, writing them to the SmallVector*.
-static void argsToEdges(CFLAAResult &, ConstantExpr *, SmallVectorImpl<Edge> &);
+static void argsToEdges(CFLAAResult &, ConstantExpr *, SmallVectorImpl<Edge> &,
+                        const TargetLibraryInfo &);
 
 /// Gets the "Level" that one should travel in StratifiedSets
 /// given an EdgeType.
@@ -654,13 +676,15 @@ static Level directionOfEdgeType(EdgeType);
 /// Builds the graph needed for constructing the StratifiedSets for the
 /// given function
 static void buildGraphFrom(CFLAAResult &, Function *,
-                           SmallVectorImpl<Value *> &, NodeMapT &, GraphT &);
+                           SmallVectorImpl<Value *> &, NodeMapT &, GraphT &,
+                           const TargetLibraryInfo &);
 
 /// Gets the edges of a ConstantExpr as if it was an Instruction. This function
 /// also acts on any nested ConstantExprs, adding the edges of those to the
 /// given SmallVector as well.
 static void constexprToEdges(CFLAAResult &, ConstantExpr &,
-                             SmallVectorImpl<Edge> &);
+                             SmallVectorImpl<Edge> &,
+                             const TargetLibraryInfo &);
 
 /// Given an Instruction, this will add it to the graph, along with any
 /// Instructions that are potentially only available from said Instruction
@@ -670,7 +694,7 @@ static void constexprToEdges(CFLAAResult &, ConstantExpr &,
 /// instructions to the graph appropriately.
 static void addInstructionToGraph(CFLAAResult &, Instruction &,
                                   SmallVectorImpl<Value *> &, NodeMapT &,
-                                  GraphT &);
+                                  GraphT &, const TargetLibraryInfo &);
 
 /// Determines whether it would be pointless to add the given Value to our sets.
 static bool canSkipAddingToSets(Value *Val);
@@ -749,17 +773,19 @@ static EdgeType flipWeight(EdgeType Initial) {
 }
 
 static void argsToEdges(CFLAAResult &Analysis, Instruction *Inst,
-                        SmallVectorImpl<Edge> &Output) {
+                        SmallVectorImpl<Edge> &Output,
+                        const TargetLibraryInfo &TLI) {
   assert(hasUsefulEdges(Inst) &&
          "Expected instructions to have 'useful' edges");
-  GetEdgesVisitor v(Analysis, Output);
+  GetEdgesVisitor v(Analysis, Output, TLI);
   v.visit(Inst);
 }
 
 static void argsToEdges(CFLAAResult &Analysis, ConstantExpr *CE,
-                        SmallVectorImpl<Edge> &Output) {
+                        SmallVectorImpl<Edge> &Output,
+                        const TargetLibraryInfo &TLI) {
   assert(hasUsefulEdges(CE) && "Expected constant expr to have 'useful' edges");
-  GetEdgesVisitor v(Analysis, Output);
+  GetEdgesVisitor v(Analysis, Output, TLI);
   v.visitConstantExpr(CE);
 }
 
@@ -777,7 +803,8 @@ static Level directionOfEdgeType(EdgeType Weight) {
 
 static void constexprToEdges(CFLAAResult &Analysis,
                              ConstantExpr &CExprToCollapse,
-                             SmallVectorImpl<Edge> &Results) {
+                             SmallVectorImpl<Edge> &Results,
+                             const TargetLibraryInfo &TLI) {
   SmallVector<ConstantExpr *, 4> Worklist;
   Worklist.push_back(&CExprToCollapse);
 
@@ -790,7 +817,7 @@ static void constexprToEdges(CFLAAResult &Analysis,
       continue;
 
     ConstexprEdges.clear();
-    argsToEdges(Analysis, CExpr, ConstexprEdges);
+    argsToEdges(Analysis, CExpr, ConstexprEdges, TLI);
     for (auto &Edge : ConstexprEdges) {
       if (auto *Nested = dyn_cast<ConstantExpr>(Edge.From))
         if (Visited.insert(Nested).second)
@@ -807,7 +834,8 @@ static void constexprToEdges(CFLAAResult &Analysis,
 
 static void addInstructionToGraph(CFLAAResult &Analysis, Instruction &Inst,
                                   SmallVectorImpl<Value *> &ReturnedValues,
-                                  NodeMapT &Map, GraphT &Graph) {
+                                  NodeMapT &Map, GraphT &Graph,
+                                  const TargetLibraryInfo &TLI) {
   const auto findOrInsertNode = [&Map, &Graph](Value *Val) {
     auto Pair = Map.insert(std::make_pair(Val, GraphT::Node()));
     auto &Iter = Pair.first;
@@ -827,7 +855,7 @@ static void addInstructionToGraph(CFLAAResult &Analysis, Instruction &Inst,
     return;
 
   SmallVector<Edge, 8> Edges;
-  argsToEdges(Analysis, &Inst, Edges);
+  argsToEdges(Analysis, &Inst, Edges, TLI);
 
   // In the case of an unused alloca (or similar), edges may be empty. Note
   // that it exists so we can potentially answer NoAlias.
@@ -859,19 +887,20 @@ static void addInstructionToGraph(CFLAAResult &Analysis, Instruction &Inst,
 
   for (ConstantExpr *CE : ConstantExprs) {
     Edges.clear();
-    constexprToEdges(Analysis, *CE, Edges);
+    constexprToEdges(Analysis, *CE, Edges, TLI);
     std::for_each(Edges.begin(), Edges.end(), addEdgeToGraph);
   }
 }
 
 static void buildGraphFrom(CFLAAResult &Analysis, Function *Fn,
                            SmallVectorImpl<Value *> &ReturnedValues,
-                           NodeMapT &Map, GraphT &Graph) {
+                           NodeMapT &Map, GraphT &Graph,
+                           const TargetLibraryInfo &TLI) {
   // (N.B. We may remove graph construction entirely, because it doesn't really
   // buy us much.)
   for (auto &Bb : Fn->getBasicBlockList())
     for (auto &Inst : Bb.getInstList())
-      addInstructionToGraph(Analysis, Inst, ReturnedValues, Map, Graph);
+      addInstructionToGraph(Analysis, Inst, ReturnedValues, Map, Graph, TLI);
 }
 
 static bool canSkipAddingToSets(Value *Val) {
@@ -901,7 +930,7 @@ CFLAAResult::FunctionInfo CFLAAResult::buildSetsFrom(Function *Fn) {
   GraphT Graph;
   SmallVector<Value *, 4> ReturnedValues;
 
-  buildGraphFrom(*this, Fn, ReturnedValues, Map, Graph);
+  buildGraphFrom(*this, Fn, ReturnedValues, Map, Graph, TLI);
 
   DenseMap<GraphT::Node, Value *> NodeValueMap;
   NodeValueMap.reserve(Map.size());
@@ -1082,7 +1111,7 @@ AliasResult CFLAAResult::query(const MemoryLocation &LocA,
 char CFLAA::PassID;
 
 CFLAAResult CFLAA::run(Function &F, AnalysisManager<Function> &AM) {
-  return CFLAAResult();
+  return CFLAAResult(AM.getResult<TargetLibraryAnalysis>(F));
 }
 
 char CFLAAWrapperPass::ID = 0;
@@ -1095,16 +1124,12 @@ CFLAAWrapperPass::CFLAAWrapperPass() : ImmutablePass(ID) {
   initializeCFLAAWrapperPassPass(*PassRegistry::getPassRegistry());
 }
 
-bool CFLAAWrapperPass::doInitialization(Module &M) {
-  Result.reset(new CFLAAResult());
-  return false;
-}
-
-bool CFLAAWrapperPass::doFinalization(Module &M) {
-  Result.reset();
-  return false;
+void CFLAAWrapperPass::initializePass() {
+  auto &TLIWP = getAnalysis<TargetLibraryInfoWrapperPass>();
+  Result.reset(new CFLAAResult(TLIWP.getTLI()));
 }
 
 void CFLAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesAll();
+  AU.addRequired<TargetLibraryInfoWrapperPass>();
 }
diff --git a/llvm/test/Analysis/CFLAliasAnalysis/malloc-and-free.ll b/llvm/test/Analysis/CFLAliasAnalysis/malloc-and-free.ll
new file mode 100644
index 00000000000..8b8ee4a5e4a
--- /dev/null
+++ b/llvm/test/Analysis/CFLAliasAnalysis/malloc-and-free.ll
@@ -0,0 +1,30 @@
+; This testcase ensures that CFL AA handles malloc and free in a sound and precise manner
+
+; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-no-aliases -disable-output 2>&1 | FileCheck %s
+; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-no-aliases -disable-output 2>&1 | FileCheck %s
+
+declare noalias i8* @malloc(i64)
+declare noalias i8* @calloc(i64, i64)
+declare void @free(i8* nocapture)
+
+; CHECK: Function: test_malloc
+; CHECK: NoAlias: i8* %p, i8* %q
+define void @test_malloc(i8* %p) {
+	%q = call i8* @malloc(i64 4)
+	ret void
+}
+
+; CHECK: Function: test_calloc
+; CHECK: NoAlias: i8* %p, i8* %q
+define void @test_calloc(i8* %p) {
+	%q = call i8* @calloc(i64 2, i64 4)
+	ret void
+}
+
+; CHECK: Function: test_free
+; CHECK: NoAlias: i8* %p, i8* %q
+define void @test_free(i8* %p) {
+	%q = alloca i8, align 4
+	call void @free(i8* %q)
+	ret void
+}