[CFLAA] Teach cfl-aa to understand heap memory allocation

[grievejia]

Summary

Cfl-aa used to bail out and make the most conservative assumption on any external library functions (any input or output parameter may alias just about anything). This patch tries to make it less conservative when seeing an external function that allocate/deallocate heap memory, e.g. malloc(), calloc(), and free().

[george.burgess.iv]

Tests would be appreciated here, too, please. :)

lib/Analysis/CFLAliasAnalysis.cpp

387

This looks a bit sketchy, because isAllocLikeFn returns true for strdup/strndup, both of which copy arbitrary bits from a source to a destination. It also looks like BasicAA (line 766) opts to be conservative with strdup/strndup.

That said, given how we currently handle external function calls + conversions of pointers to ints (and back), I'm not sure if allowing strdup here can break anything that has a reasonable chance of success in the first place.

...So, I'm really tempted to say "please do the same thing as BasicAA here and add a TODO that we'll address when external values/other CFLAA features are in, so this doesn't come back to subtly bite us in the future."

[• dberlin]

Unless i'm missing something, this is not the correct handling. Happy to be
convinced.

The normal behavior (and that specified in the papers) is to treat malloc
as if it output the address of a unique variable.

This is because while it introduces no aliases itself, it does introduce a
variable that can be aliased.
If that variable is reached through other mechanisms, it may be an alias :)

If you say they do *nothing*, as you've done here, nothing will ever alias
the result of malloc, even something that *should*.

Am i missing something?

[grievejia]

In D20776#443674, @dberlin wrote:

This is because while it introduces no aliases itself, it does introduce a
variable that can be aliased.
If that variable is reached through other mechanisms, it may be an alias :)

I agree.

If you say they do *nothing*, as you've done here, nothing will ever alias
the result of malloc, even something that *should*.

Am i missing something?

"Nothing" is currently what happens to AllocaInsts. I just tried to be consistent with how AllocaInst is treated.

Also, "nothing" only applies to the malloc() inst/AllocaInst itself. If any other instructions use it, the allocated value should get linked to other part of the function.

[grievejia]

Replaced isAllocLikeFn() with isMallocLikeFn() || isCallocLikeFn(), just to be consistent with BasicAA.

Also, added a test case.

[george.burgess.iv]

Danny - ...Good point. I forgot that we were super conservative when something isn't in the sets.

Jia - Can we please change this to just add an edge from the malloc/calloc result (and free argument) to itself with zero stratified attributes, so that we have the relevant pointer in our sets? :)

We need to do this because, if the result of the malloc is otherwise unused, we'll not see it in the stratified sets. If something's not in the stratified sets, we'll assume it was added after we ran on the function, so we're conservative and always just say MayAlias. If we're not doing the same thing with otherwise-unused allocas, we probably should be.

[grievejia]

Added additional edges in case the return value of malloc() is not used.

I'm not sure about free(), though. How could an actual argument becomes "unused"? Isn't the argument itself a use?

[grievejia]

In D20776#443765, @george.burgess.iv wrote:

We need to do this because, if the result of the malloc is otherwise unused, we'll not see it in the stratified sets. If something's not in the stratified sets, we'll assume it was added after we ran on the function, so we're conservative and always just say MayAlias. If we're not doing the same thing with otherwise-unused allocas, we probably should be.

You are right. I think we are doing this for unused allocas, outside GetEdgeVisitor.

Any reason for (1) not adding unused value to StratifiedSets, and (2) treating values not in StratifiedSets conservatively?

[george.burgess.iv]

We treat values that don't exist in StratifiedSets conservatively because the IR can be modified after we run CFLAA on it. Imagine that we started with:

define void @foo() {
  %1 = alloca [2 x i32], align 8
  ; some code here
  ret void
}

CFLAA ran, etc. and a later pass introduced a GEP of %1, like so:

define void @foo() {
  %1 = alloca [2 x i32], align 8
  %2 = GEP %1, i32 0, i32 0
  ; some code here
  ret void
}

...And a later pass queries CFLAA for whether %1 and %2 alias for whatever reason. Because %2 wasn't there at build-time, we can't offer an accurate answer without doing extra work, so we always answer conservatively.

As for why we don't add unused pointers, probably bugs. If you can find a case where we're not adding pointers, please say so. :)

lib/Analysis/CFLAliasAnalysis.cpp

392

I think we need to do the same edge hack with free calls, as well :)

Consider:

@g = ; some global ptr
define void @foo() {
  %a = alloca i32
  ; code that only uses %a
  call void @free(i8* @g)
}

If we don't, @g won't be in the sets, so we'll consider it to alias anything, which is too conservative.

[grievejia]

Addressed free() argument.

[grievejia]

In D20776#443810, @george.burgess.iv wrote:

We treat values that don't exist in StratifiedSets conservatively because the IR can be modified after we run CFLAA on it.

Hmm, this is strange. To me the one and only right thing to do after IR changes is to invalidate the cfl-aa pass and re-run the analysis. In general it is not safe to persist alias analysis result across IR modifications. In your example, what if, instead of someone adding a new value to the IR, a new store instruction is added and the points-to set of some existing value gets altered? The analysis result can't be used anyway.

[grievejia]

Updated test case.

The previous test case makes alias queries on poisoned pointers and alloca-ed pointers. We'll always get back NoAlias result for those queries even before applying the patch. The updated version tests for the right thing.

[george.burgess.iv]

LGTM'ed this over email. Doing so here, too, to make life easier for code historians.

include/llvm/Analysis/CFLAliasAnalysis.h

 //===- CFLAliasAnalysis.h - CFL-Based Alias Analysis Interface ---*- C++ -*-==//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 /// \file
 /// This is the interface for LLVM's primary stateless and local alias analysis.
 ///
 //===----------------------------------------------------------------------===//
 
 #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"
 #include "llvm/Pass.h"
 #include <forward_list>
 
 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();
 
   /// Handle invalidation events from the new pass manager.
   ///
   /// By definition, this result is stateless and so remains valid.
   bool invalidate(Function &, const PreservedAnalyses &) { return false; }
 
private:
     void removeSelfFromCache() {
       assert(Result != nullptr);
       auto *Val = getValPtr();
       Result->evict(cast<Function>(Val));
       setValPtr(nullptr);
     }
   };
 
+  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
   /// have any kind of recursion, it is discernable from a function
   /// that simply has empty sets.
   DenseMap<Function *, Optional<FunctionInfo>> Cache;
   std::forward_list<FunctionHandle> Handles;
 

 public:
   static char ID;
 
   CFLAAWrapperPass();
 
   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;
 };
 
 //===--------------------------------------------------------------------===//
 //
 // createCFLAAWrapperPass - This pass implements a set-based approach to
 // alias analysis.
 //
 ImmutablePass *createCFLAAWrapperPass();
 }
 
 #endif

lib/Analysis/CFLAliasAnalysis.cpp

 // run on. Realistically, this likely isn't a problem until we allow
 // FunctionPasses to run concurrently.
 
 #include "llvm/Analysis/CFLAliasAnalysis.h"
 #include "StratifiedSets.h"
 #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"
 #include "llvm/IR/Instructions.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 #include <cassert>
 #include <memory>
 #include <tuple>
 
 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.
 struct CFLAAResult::FunctionInfo {
   StratifiedSets<Value *> Sets;
   // Lots of functions have < 4 returns. Adjust as necessary.
   SmallVector<Value *, 4> ReturnedValues;
 
struct Edge {
   Edge(Value *From, Value *To, EdgeType W, StratifiedAttrs A)
       : From(From), To(To), Weight(W), AdditionalAttrs(A) {}
 };
 
 /// Gets the edges our graph should have, based on an Instruction*
 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");
   }
 
   void visitPtrToIntInst(PtrToIntInst &Inst) {
     auto *Ptr = Inst.getOperand(0);
     Output.push_back(Edge(Ptr, Ptr, EdgeType::Assign, AttrUnknown));
for (auto *Fn : Fns) {
           Output.push_back(Edge(MainVal, SubVal, EdgeType::Assign, NewAttrs));
         }
       }
     }
     return true;
   }
 
   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.
+    if (isAllocLikeFn(&Inst, &TLI) || isFreeCall(&Inst, &TLI))
+      return;
+
     // TODO: Add support for noalias args/all the other fun function attributes
     // that we can tack on.
     SmallVector<Function *, 4> Targets;
     if (getPossibleTargets(&Inst, Targets)) {
       if (tryInterproceduralAnalysis(Targets, &Inst, Inst.arg_operands()))
         return;
       // Cleanup from interprocedural analysis
       Output.clear();
     }
 
     // Because the function is opaque, we need to note that anything

 
 /// Given a Value, potentially return which AttrIndex it maps to.
 static Optional<StratifiedAttr> valueToAttrIndex(Value *Val);
 
 /// Gets the inverse of a given EdgeType.
 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.
 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
 /// For example, given the following line:
 ///   %0 = load i16* getelementptr ([1 x i16]* @a, 0, 0), align 2
 /// addInstructionToGraph would add both the `load` and `getelementptr`
 /// 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);
 
 static Optional<Function *> parentFunctionOfValue(Value *Val) {
   if (auto *Inst = dyn_cast<Instruction>(Val)) {
     auto *Bb = Inst->getParent();
     return Bb->getParent();
case EdgeType::Dereference:
     return EdgeType::Reference;
   case EdgeType::Reference:
     return EdgeType::Dereference;
   }
   llvm_unreachable("Incomplete coverage of EdgeType enum");
 }
 
 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);
 }
 
 static Level directionOfEdgeType(EdgeType Weight) {
   switch (Weight) {
   case EdgeType::Reference:
     return Level::Above;
   case EdgeType::Dereference:
     return Level::Below;
   case EdgeType::Assign:
     return Level::Same;
   }
   llvm_unreachable("Incomplete switch coverage");
 }
 
 static void constexprToEdges(CFLAAResult &Analysis,
                              ConstantExpr &CExprToCollapse,
-                             SmallVectorImpl<Edge> &Results) {
+                             SmallVectorImpl<Edge> &Results,
+                             const TargetLibraryInfo &TLI) {
   SmallVector<ConstantExpr *, 4> Worklist;
   Worklist.push_back(&CExprToCollapse);
 
   SmallVector<Edge, 8> ConstexprEdges;
   SmallPtrSet<ConstantExpr *, 4> Visited;
   while (!Worklist.empty()) {
     auto *CExpr = Worklist.pop_back_val();
 
     if (!hasUsefulEdges(CExpr))
       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)
           Worklist.push_back(Nested);
 
       if (auto *Nested = dyn_cast<ConstantExpr>(Edge.To))
         if (Visited.insert(Nested).second)
           Worklist.push_back(Nested);
     }
 
     Results.append(ConstexprEdges.begin(), ConstexprEdges.end());
   }
 }
 
 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;
     if (Pair.second) {
       auto NewNode = Graph.addNode();
       Iter->second = NewNode;
     }
     return Iter->second;
   };
 
   // We don't want the edges of most "return" instructions, but we *do* want
   // to know what can be returned.
   if (isa<ReturnInst>(&Inst))
     ReturnedValues.push_back(&Inst);
 
   if (!hasUsefulEdges(&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.
   if (Edges.empty()) {
     auto MaybeVal = getTargetValue(&Inst);
     assert(MaybeVal.hasValue());
     auto *Target = *MaybeVal;
     findOrInsertNode(Target);
for (const Edge &E : Edges) {
     if (auto *Constexpr = dyn_cast<ConstantExpr>(E.To))
       ConstantExprs.push_back(Constexpr);
     if (auto *Constexpr = dyn_cast<ConstantExpr>(E.From))
       ConstantExprs.push_back(Constexpr);
   }
 
   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) {
   // Constants can share instances, which may falsely unify multiple
   // sets, e.g. in
   // store i32* null, i32** %ptr1
   // store i32* null, i32** %ptr2
   // clearly ptr1 and ptr2 should not be unified into the same set, so

 }
 
 // Builds the graph + StratifiedSets for a function.
 CFLAAResult::FunctionInfo CFLAAResult::buildSetsFrom(Function *Fn) {
   NodeMapT Map;
   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());
   for (const auto &Pair : Map)
     NodeValueMap.insert(std::make_pair(Pair.second, Pair.first));
 
   const auto findValueOrDie = [&NodeValueMap](GraphT::Node Node) {
     auto ValIter = NodeValueMap.find(Node);
AliasResult CFLAAResult::query(const MemoryLocation &LocA,
   // two. We can't return partial alias for this case. Since we do not currently
   // track enough information to differentiate.
   return SetA.Index == SetB.Index ? MayAlias : NoAlias;
 }
 
 char CFLAA::PassID;
 
 CFLAAResult CFLAA::run(Function &F, AnalysisManager<Function> &AM) {
-  return CFLAAResult();
+  return CFLAAResult(AM.getResult<TargetLibraryAnalysis>(F));
 }
 
 char CFLAAWrapperPass::ID = 0;
 INITIALIZE_PASS(CFLAAWrapperPass, "cfl-aa", "CFL-Based Alias Analysis", false,
                 true)
 
 ImmutablePass *llvm::createCFLAAWrapperPass() { return new CFLAAWrapperPass(); }
 
 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>();
 }