[CFLAA] Simplify CFLGraphBuilder by removing the escaped value set and external value set

[grievejia]

Summary

This is a code cleanup patch. No functionality change is introduced.

Previously, CFLGraphBuilder maintained 5 auxiliary structures in addition to the CFLGraph under construction. Among those five structures, the escaped value set and the external value set were irreplaceable when they were first introduced, but now their use cases can be completely covered by InstantiatedAttrs. We could simplify CFLGraphBuilder (as well as its clients) by removing those two sets.

[grievejia]

Rebased on master

[george.burgess.iv]

Sorry for the latency on these reviews: LGTM. Will commit later today.

lib/Analysis/CFLSteensAliasAnalysis.cpp

 
 /// Gets the edges our graph should have, based on an Instruction*
 class GetEdgesVisitor : public InstVisitor<GetEdgesVisitor, void> {
   CFLSteensAAResult &AA;
   const TargetLibraryInfo &TLI;
 
   CFLGraph &Graph;
   SmallVectorImpl<Value *> &ReturnValues;
-  SmallPtrSetImpl<Value *> &Externals;
-  SmallPtrSetImpl<Value *> &Escapes;
   SmallVectorImpl<InstantiatedRelation> &InstantiatedRelations;
   SmallVectorImpl<InstantiatedAttr> &InstantiatedAttrs;
 
   static bool hasUsefulEdges(ConstantExpr *CE) {
     // ConstantExpr doesn't have terminators, invokes, or fences, so only needs
     // to check for compares.
     return CE->getOpcode() != Instruction::ICmp &&
            CE->getOpcode() != Instruction::FCmp;
   }
 
   void addNode(Value *Val) {
+    assert(Val != nullptr);
     if (!Graph.addNode(Val))
       return;
 
-    if (isa<GlobalValue>(Val))
-      Externals.insert(Val);
-    else if (auto CExpr = dyn_cast<ConstantExpr>(Val))
+    if (isa<GlobalValue>(Val)) {
+      Graph.addAttr(Val, getGlobalOrArgAttrFromValue(*Val));
+      // Currently we do not attempt to be smart on globals
+      InstantiatedAttrs.push_back(
+          InstantiatedAttr{InstantiatedValue{Val, 1}, getAttrUnknown()});
+    } else if (auto CExpr = dyn_cast<ConstantExpr>(Val))
       if (hasUsefulEdges(CExpr))
         visitConstantExpr(CExpr);
   }
 
   void addNodeWithAttr(Value *Val, AliasAttrs Attr) {
     addNode(Val);
     Graph.addAttr(Val, Attr);
   }
 
   void addEdge(Value *From, Value *To, EdgeType Type) {
+    assert(From != nullptr && To != nullptr);
     if (!From->getType()->isPointerTy() || !To->getType()->isPointerTy())
       return;
     addNode(From);
     if (To != From)
       addNode(To);
     Graph.addEdge(From, To, Type);
   }
 
 public:
   GetEdgesVisitor(CFLSteensAAResult &AA, const TargetLibraryInfo &TLI,
                   CFLGraph &Graph, SmallVectorImpl<Value *> &ReturnValues,
-                  SmallPtrSetImpl<Value *> &Externals,
-                  SmallPtrSetImpl<Value *> &Escapes,
                   SmallVectorImpl<InstantiatedRelation> &InstantiatedRelations,
                   SmallVectorImpl<InstantiatedAttr> &InstantiatedAttrs)
       : AA(AA), TLI(TLI), Graph(Graph), ReturnValues(ReturnValues),
-        Externals(Externals), Escapes(Escapes),
         InstantiatedRelations(InstantiatedRelations),
         InstantiatedAttrs(InstantiatedAttrs) {}
 
   void visitInstruction(Instruction &) {
     llvm_unreachable("Unsupported instruction encountered");
   }
 
   void visitReturnInst(ReturnInst &Inst) {
if (getPossibleTargets(CS, Targets))
         return;
 
     // Because the function is opaque, we need to note that anything
     // could have happened to the arguments (unless the function is marked
     // readonly or readnone), and that the result could alias just about
     // anything, too (unless the result is marked noalias).
     if (!CS.onlyReadsMemory())
       for (Value *V : CS.args()) {
-        if (V->getType()->isPointerTy())
-          Escapes.insert(V);
+        if (V->getType()->isPointerTy()) {
+          // The argument itself escapes.
+          addNodeWithAttr(V, getAttrEscaped());
+          // The fate of argument memory is unknown. Note that since AliasAttrs
+          // is transitive with respect to dereference, we only need to specify
+          // it for the first-level memory.
+          InstantiatedAttrs.push_back(
+              InstantiatedAttr{InstantiatedValue{V, 1}, getAttrUnknown()});
+        }
       }
 
     if (Inst->getType()->isPointerTy()) {
       auto *Fn = CS.getCalledFunction();
       if (Fn == nullptr || !Fn->doesNotAlias(0))
+        // No need to call addNodeWithAttr() since we've added Inst at the
+        // beginning of this function and we know it is not a global.
         Graph.addAttr(Inst, getAttrUnknown());
     }
   }
 
   /// Because vectors/aggregates are immutable and unaddressable, there's
   /// nothing we can do to coax a value out of them, other than calling
   /// Extract{Element,Value}. We can effectively treat them as pointers to
   /// arbitrary memory locations we can store in and load from.
class CFLGraphBuilder {
   CFLSteensAAResult &Analysis;
   const TargetLibraryInfo &TLI;
 
   // Output of the builder
   CFLGraph Graph;
   SmallVector<Value *, 4> ReturnedValues;
 
   // Auxiliary structures used by the builder
-  SmallPtrSet<Value *, 8> ExternalValues;
-  SmallPtrSet<Value *, 8> EscapedValues;
   SmallVector<InstantiatedRelation, 8> InstantiatedRelations;
   SmallVector<InstantiatedAttr, 8> InstantiatedAttrs;
 
   // Helper functions
 
   // Determines whether or not we an instruction is useless to us (e.g.
   // FenceInst)
   static bool hasUsefulEdges(Instruction *Inst) {
     bool IsNonInvokeRetTerminator = isa<TerminatorInst>(Inst) &&
                                     !isa<InvokeInst>(Inst) &&
                                     !isa<ReturnInst>(Inst);
     return !isa<CmpInst>(Inst) && !isa<FenceInst>(Inst) &&
            !IsNonInvokeRetTerminator;
   }
 
   void addArgumentToGraph(Argument &Arg) {
     if (Arg.getType()->isPointerTy()) {
       Graph.addNode(&Arg);
-      ExternalValues.insert(&Arg);
+      Graph.addAttr(&Arg, getGlobalOrArgAttrFromValue(Arg));
+      // Pointees of a formal parameter is known to the caller
+      InstantiatedAttrs.push_back(
+          InstantiatedAttr{InstantiatedValue{&Arg, 1}, getAttrCaller()});
     }
   }
 
   // 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.
   void addInstructionToGraph(Instruction &Inst) {
     if (!hasUsefulEdges(&Inst))
       return;
 
-    GetEdgesVisitor(Analysis, TLI, Graph, ReturnedValues, ExternalValues,
-                    EscapedValues, InstantiatedRelations, InstantiatedAttrs)
+    GetEdgesVisitor(Analysis, TLI, Graph, ReturnedValues, InstantiatedRelations,
+                    InstantiatedAttrs)
         .visit(Inst);
   }
 
   // Builds the graph needed for constructing the StratifiedSets for the given
   // function
   void buildGraphFrom(Function &Fn) {
     for (auto &Bb : Fn.getBasicBlockList())
       for (auto &Inst : Bb.getInstList())
CFLGraphBuilder(CFLSteensAAResult &Analysis, const TargetLibraryInfo &TLI,
       : Analysis(Analysis), TLI(TLI) {
     buildGraphFrom(Fn);
   }
 
   const CFLGraph &getCFLGraph() const { return Graph; }
   const SmallVector<Value *, 4> &getReturnValues() const {
     return ReturnedValues;
   }
-  const SmallPtrSet<Value *, 8> &getExternalValues() const {
-    return ExternalValues;
-  }
-  const SmallPtrSet<Value *, 8> &getEscapedValues() const {
-    return EscapedValues;
-  }
   const SmallVector<InstantiatedRelation, 8> &getInstantiatedRelations() const {
     return InstantiatedRelations;
   }
   const SmallVector<InstantiatedAttr, 8> &getInstantiatedAttrs() const {
     return InstantiatedAttrs;
   }
 };
 }
for (const auto &Edge : Graph.edgesFor(CurValue)) {
         break;
       }
 
       if (Added)
         Worklist.push_back(OtherValue);
     }
   }
 
-  // Special handling for globals and arguments
-  for (auto *External : GraphBuilder.getExternalValues()) {
-    SetBuilder.add(External);
-    auto Attr = getGlobalOrArgAttrFromValue(*External);
-    if (Attr.any()) {
-      SetBuilder.noteAttributes(External, Attr);
-      if (isa<GlobalValue>(External))
-        SetBuilder.addAttributesBelow(External, 1, getAttrUnknown());
-      else
-        SetBuilder.addAttributesBelow(External, 1, getAttrCaller());
-    }
-  }
-
   // Special handling for interprocedural aliases
   for (auto &Edge : GraphBuilder.getInstantiatedRelations()) {
     auto FromVal = Edge.From.Val;
     auto ToVal = Edge.To.Val;
     SetBuilder.add(FromVal);
     SetBuilder.add(ToVal);
     SetBuilder.addBelowWith(FromVal, Edge.From.DerefLevel, ToVal,
                             Edge.To.DerefLevel);
   }
 
   // Special handling for interprocedural attributes
   for (auto &IPAttr : GraphBuilder.getInstantiatedAttrs()) {
     auto Val = IPAttr.IValue.Val;
     SetBuilder.add(Val);
     SetBuilder.addAttributesBelow(Val, IPAttr.IValue.DerefLevel, IPAttr.Attr);
   }
 
-  // Special handling for opaque external functions
-  for (auto *Escape : GraphBuilder.getEscapedValues()) {
-    SetBuilder.add(Escape);
-    SetBuilder.noteAttributes(Escape, getAttrEscaped());
-    SetBuilder.addAttributesBelow(Escape, 1, getAttrUnknown());
-  }
-
   return FunctionInfo(*Fn, GraphBuilder.getReturnValues(), SetBuilder.build());
 }
 
 void CFLSteensAAResult::scan(Function *Fn) {
   auto InsertPair = Cache.insert(std::make_pair(Fn, Optional<FunctionInfo>()));
   (void)InsertPair;
   assert(InsertPair.second &&
          "Trying to scan a function that has already been cached");