Revert "[Attributor] [WIP] Track AA dependency using dependency graph"

This reverts commit 6b78ed60708b56d85c6d028e9a06ce24ec3c1ae5.

4 files changed, 37 insertions, 418 deletions

diff --git a/llvm/include/llvm/Transforms/IPO/Attributor.h b/llvm/include/llvm/Transforms/IPO/Attributor.h
index 3378b19..bed180e 100644
--- a/llvm/include/llvm/Transforms/IPO/Attributor.h
+++ b/llvm/include/llvm/Transforms/IPO/Attributor.h
@@ -97,10 +97,8 @@
 #ifndef LLVM_TRANSFORMS_IPO_ATTRIBUTOR_H
 #define LLVM_TRANSFORMS_IPO_ATTRIBUTOR_H
 
-#include "llvm/ADT/GraphTraits.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/SCCIterator.h"
-#include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AssumeBundleQueries.h"
@@ -118,15 +116,10 @@
 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/Support/Allocator.h"
-#include "llvm/Support/Casting.h"
-#include "llvm/Support/DOTGraphTraits.h"
-#include "llvm/Support/GraphWriter.h"
 #include "llvm/Transforms/Utils/CallGraphUpdater.h"
 
 namespace llvm {
 
-struct AADepGraphNode;
-struct AADepGraph;
 struct Attributor;
 struct AbstractAttribute;
 struct InformationCache;
@@ -151,70 +144,6 @@ enum class DepClassTy {
 };
 ///}
 
-/// The data structure for the nodes of a dependency graph
-struct AADepGraphNode {
-public:
-  virtual ~AADepGraphNode(){};
-  using DepTy = PointerIntPair<AADepGraphNode *, 1>;
-
-protected:
-  /// Set of dependency graph nodes which this one depends on.
-  /// The bit encodes if it is optional.
-  TinyPtrVector<DepTy> Deps;
-
-  static AADepGraphNode *DepGetVal(DepTy &DT) { return DT.getPointer(); }
-  static AbstractAttribute *DepGetValAA(DepTy &DT) {
-    return cast<AbstractAttribute>(DT.getPointer());
-  }
-
-  operator AbstractAttribute *() { return cast<AbstractAttribute>(this); }
-
-public:
-  using iterator =
-      mapped_iterator<TinyPtrVector<DepTy>::iterator, decltype(&DepGetVal)>;
-  using aaiterator =
-      mapped_iterator<TinyPtrVector<DepTy>::iterator, decltype(&DepGetValAA)>;
-
-  aaiterator begin() { return aaiterator(Deps.begin(), &DepGetValAA); }
-  aaiterator end() { return aaiterator(Deps.end(), &DepGetValAA); }
-  iterator child_begin() { return iterator(Deps.begin(), &DepGetVal); }
-  iterator child_end() { return iterator(Deps.end(), &DepGetVal); }
-
-  virtual void print(raw_ostream &OS) const { OS << "AADepNode Impl\n"; }
-  TinyPtrVector<DepTy> &getDeps() { return Deps; }
-
-  friend struct Attributor;
-  friend struct AADepGraph;
-};
-
-struct AADepGraph {
-  AADepGraph() {}
-  ~AADepGraph() {}
-
-  using DepTy = AADepGraphNode::DepTy;
-  static AADepGraphNode *DepGetVal(DepTy &DT) { return DT.getPointer(); }
-  using iterator =
-      mapped_iterator<TinyPtrVector<DepTy>::iterator, decltype(&DepGetVal)>;
-
-  /// There is no root node for the dependency graph. But the SCCIterator
-  /// requires a single entry point, so we maintain a fake("synthetic") root
-  /// node that depends on every node.
-  AADepGraphNode SyntheticRoot;
-
-  AADepGraphNode *GetEntryNode() { return &SyntheticRoot; }
-
-  iterator begin() { return SyntheticRoot.child_begin(); }
-  iterator end() { return SyntheticRoot.child_end(); }
-
-  void viewGraph();
-
-  /// Dump graph to file
-  void dumpGraph();
-
-  /// Print dependency graph
-  void print();
-};
-
 /// Helper to describe and deal with positions in the LLVM-IR.
 ///
 /// A position in the IR is described by an anchor value and an "offset" that
@@ -1072,9 +1001,7 @@ struct Attributor {
     assert(!AAPtr && "Attribute already in map!");
     AAPtr = &AA;
 
-    DG.SyntheticRoot.Deps.push_back(
-        AADepGraphNode::DepTy(&AA, unsigned(DepClassTy::REQUIRED)));
-
+    AllAbstractAttributes.push_back(&AA);
     return AA;
   }
 
@@ -1436,6 +1363,12 @@ private:
   /// See getOrCreateAAFor.
   bool shouldSeedAttribute(AbstractAttribute &AA);
 
+  /// The set of all abstract attributes.
+  ///{
+  using AAVector = SmallVector<AbstractAttribute *, 64>;
+  AAVector AllAbstractAttributes;
+  ///}
+
   /// A nested map to lookup abstract attributes based on the argument position
   /// on the outer level, and the addresses of the static member (AAType::ID) on
   /// the inner level.
@@ -1457,9 +1390,6 @@ private:
   /// Helper to update an underlying call graph.
   CallGraphUpdater &CGUpdater;
 
-  /// Abstract Attribute dependency graph
-  AADepGraph DG;
-
   /// Set of functions for which we modified the content such that it might
   /// impact the call graph.
   SmallPtrSet<Function *, 8> CGModifiedFunctions;
@@ -1509,8 +1439,6 @@ private:
   SmallPtrSet<BasicBlock *, 8> ToBeDeletedBlocks;
   SmallDenseSet<WeakVH, 8> ToBeDeletedInsts;
   ///}
-
-  friend AADepGraph;
 };
 
 /// An interface to query the internal state of an abstract attribute.
@@ -2083,7 +2011,7 @@ struct IRAttribute : public BaseType {
 ///       both directions will be added in the future.
 /// NOTE: The mechanics of adding a new "concrete" abstract attribute are
 ///       described in the file comment.
-struct AbstractAttribute : public IRPosition, public AADepGraphNode {
+struct AbstractAttribute : public IRPosition {
   using StateType = AbstractState;
 
   AbstractAttribute(const IRPosition &IRP) : IRPosition(IRP) {}
@@ -2091,14 +2019,6 @@ struct AbstractAttribute : public IRPosition, public AADepGraphNode {
   /// Virtual destructor.
   virtual ~AbstractAttribute() {}
 
-  /// This function is used to identify if an \p DGN is of type
-  /// AbstractAttribute so that the dyn_cast and cast can use such information
-  /// to cast an AADepGraphNode to an AbstractAttribute.
-  ///
-  /// We eagerly return true here because all AADepGraphNodes except for the
-  /// Synthethis Node are of type AbstractAttribute
-  static bool classof(const AADepGraphNode *DGN) { return true; }
-
   /// Initialize the state with the information in the Attributor \p A.
   ///
   /// This function is called by the Attributor once all abstract attributes
@@ -2120,7 +2040,6 @@ struct AbstractAttribute : public IRPosition, public AADepGraphNode {
   /// Helper functions, for debug purposes only.
   ///{
   virtual void print(raw_ostream &OS) const;
-  virtual void printWithDeps(raw_ostream &OS) const;
   void dump() const { print(dbgs()); }
 
   /// This function should return the "summarized" assumed state as string.
@@ -2168,6 +2087,12 @@ protected:
   ///
   /// \Return CHANGED if the internal state changed, otherwise UNCHANGED.
   virtual ChangeStatus updateImpl(Attributor &A) = 0;
+
+private:
+  /// Set of abstract attributes which were queried by this one. The bit encodes
+  /// if there is an optional of required dependence.
+  using DepTy = PointerIntPair<AbstractAttribute *, 1>;
+  TinyPtrVector<DepTy> Deps;
 };
 
 /// Forward declarations of output streams for debug purposes.
diff --git a/llvm/lib/Transforms/IPO/Attributor.cpp b/llvm/lib/Transforms/IPO/Attributor.cpp
index f021582..f96dac5 100644
--- a/llvm/lib/Transforms/IPO/Attributor.cpp
+++ b/llvm/lib/Transforms/IPO/Attributor.cpp
@@ -15,10 +15,7 @@
 
 #include "llvm/Transforms/IPO/Attributor.h"
 
-#include "llvm/ADT/GraphTraits.h"
-#include "llvm/ADT/PointerIntPair.h"
 #include "llvm/ADT/Statistic.h"
-#include "llvm/ADT/TinyPtrVector.h"
 #include "llvm/Analysis/LazyValueInfo.h"
 #include "llvm/Analysis/MustExecute.h"
 #include "llvm/Analysis/ValueTracking.h"
@@ -28,15 +25,10 @@
 #include "llvm/InitializePasses.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/CommandLine.h"
-#include "llvm/Support/Debug.h"
-#include "llvm/Support/FileSystem.h"
-#include "llvm/Support/GraphWriter.h"
-#include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/Local.h"
 
 #include <cassert>
-#include <string>
 
 using namespace llvm;
 
@@ -93,23 +85,6 @@ static cl::list<std::string>
                            "allowed to be seeded."),
                   cl::ZeroOrMore, cl::CommaSeparated);
 
-static cl::opt<bool>
-    DumpDepGraph("attributor-dump-dep-graph", cl::Hidden,
-                 cl::desc("Dump the dependency graph to dot files."),
-                 cl::init(false));
-
-static cl::opt<std::string> DepGraphDotFileNamePrefix(
-    "attributor-depgraph-dot-filename-prefix", cl::Hidden,
-    cl::desc("The prefix used for the CallGraph dot file names."));
-
-static cl::opt<bool> ViewDepGraph("attributor-view-dep-graph", cl::Hidden,
-                                  cl::desc("View the dependency graph."),
-                                  cl::init(false));
-
-static cl::opt<bool> PrintDependencies("attributor-print-dep", cl::Hidden,
-                                       cl::desc("Print attribute dependencies"),
-                                       cl::init(false));
-
 /// Logic operators for the change status enum class.
 ///
 ///{
@@ -523,10 +498,8 @@ Attributor::getAssumedConstant(const Value &V, const AbstractAttribute &AA,
 Attributor::~Attributor() {
   // The abstract attributes are allocated via the BumpPtrAllocator Allocator,
   // thus we cannot delete them. We can, and want to, destruct them though.
-  for (auto &DepAA : DG.SyntheticRoot.Deps) {
-    AbstractAttribute *AA = cast<AbstractAttribute>(DepAA.getPointer());
+  for (AbstractAttribute *AA : AllAbstractAttributes)
     AA->~AbstractAttribute();
-  }
 }
 
 bool Attributor::isAssumedDead(const AbstractAttribute &AA,
@@ -931,7 +904,7 @@ bool Attributor::checkForAllReadWriteInstructions(
 
 void Attributor::runTillFixpoint() {
   LLVM_DEBUG(dbgs() << "[Attributor] Identified and initialized "
-                    << DG.SyntheticRoot.Deps.size()
+                    << AllAbstractAttributes.size()
                     << " abstract attributes.\n");
 
   // Now that all abstract attributes are collected and initialized we start
@@ -941,11 +914,11 @@ void Attributor::runTillFixpoint() {
 
   SmallVector<AbstractAttribute *, 32> ChangedAAs;
   SetVector<AbstractAttribute *> Worklist, InvalidAAs;
-  Worklist.insert(DG.SyntheticRoot.begin(), DG.SyntheticRoot.end());
+  Worklist.insert(AllAbstractAttributes.begin(), AllAbstractAttributes.end());
 
   do {
     // Remember the size to determine new attributes.
-    size_t NumAAs = DG.SyntheticRoot.Deps.size();
+    size_t NumAAs = AllAbstractAttributes.size();
     LLVM_DEBUG(dbgs() << "\n\n[Attributor] #Iteration: " << IterationCounter
                       << ", Worklist size: " << Worklist.size() << "\n");
 
@@ -962,7 +935,7 @@ void Attributor::runTillFixpoint() {
       while (!InvalidAA->Deps.empty()) {
         const auto &Dep = InvalidAA->Deps.back();
         InvalidAA->Deps.pop_back();
-        AbstractAttribute *DepAA = cast<AbstractAttribute>(Dep.getPointer());
+        AbstractAttribute *DepAA = Dep.getPointer();
         if (Dep.getInt() == unsigned(DepClassTy::OPTIONAL)) {
           Worklist.insert(DepAA);
           continue;
@@ -980,8 +953,7 @@ void Attributor::runTillFixpoint() {
     // changed to the work list.
     for (AbstractAttribute *ChangedAA : ChangedAAs)
       while (!ChangedAA->Deps.empty()) {
-        Worklist.insert(
-            cast<AbstractAttribute>(ChangedAA->Deps.back().getPointer()));
+        Worklist.insert(ChangedAA->Deps.back().getPointer());
         ChangedAA->Deps.pop_back();
       }
 
@@ -1009,8 +981,8 @@ void Attributor::runTillFixpoint() {
 
     // Add attributes to the changed set if they have been created in the last
     // iteration.
-    ChangedAAs.append(DG.SyntheticRoot.begin() + NumAAs,
-                      DG.SyntheticRoot.end());
+    ChangedAAs.append(AllAbstractAttributes.begin() + NumAAs,
+                      AllAbstractAttributes.end());
 
     // Reset the work list and repopulate with the changed abstract attributes.
     // Note that dependent ones are added above.
@@ -1043,8 +1015,7 @@ void Attributor::runTillFixpoint() {
     }
 
     while (!ChangedAA->Deps.empty()) {
-      ChangedAAs.push_back(
-          cast<AbstractAttribute>(ChangedAA->Deps.back().getPointer()));
+      ChangedAAs.push_back(ChangedAA->Deps.back().getPointer());
       ChangedAA->Deps.pop_back();
     }
   }
@@ -1066,13 +1037,12 @@ void Attributor::runTillFixpoint() {
 }
 
 ChangeStatus Attributor::manifestAttributes() {
-  size_t NumFinalAAs = DG.SyntheticRoot.Deps.size();
+  size_t NumFinalAAs = AllAbstractAttributes.size();
 
   unsigned NumManifested = 0;
   unsigned NumAtFixpoint = 0;
   ChangeStatus ManifestChange = ChangeStatus::UNCHANGED;
-  for (auto &DepAA : DG.SyntheticRoot.Deps) {
-    AbstractAttribute *AA = cast<AbstractAttribute>(DepAA.getPointer());
+  for (AbstractAttribute *AA : AllAbstractAttributes) {
     AbstractState &State = AA->getState();
 
     // If there is not already a fixpoint reached, we can now take the
@@ -1112,14 +1082,11 @@ ChangeStatus Attributor::manifestAttributes() {
   NumAttributesValidFixpoint += NumAtFixpoint;
 
   (void)NumFinalAAs;
-  if (NumFinalAAs != DG.SyntheticRoot.Deps.size()) {
-    for (unsigned u = NumFinalAAs; u < DG.SyntheticRoot.Deps.size(); ++u)
-      errs() << "Unexpected abstract attribute: "
-             << cast<AbstractAttribute>(DG.SyntheticRoot.Deps[u].getPointer())
+  if (NumFinalAAs != AllAbstractAttributes.size()) {
+    for (unsigned u = NumFinalAAs; u < AllAbstractAttributes.size(); ++u)
+      errs() << "Unexpected abstract attribute: " << *AllAbstractAttributes[u]
              << " :: "
-             << cast<AbstractAttribute>(DG.SyntheticRoot.Deps[u].getPointer())
-                    ->getIRPosition()
-                    .getAssociatedValue()
+             << AllAbstractAttributes[u]->getIRPosition().getAssociatedValue()
              << "\n";
     llvm_unreachable("Expected the final number of abstract attributes to "
                      "remain unchanged!");
@@ -1298,17 +1265,6 @@ ChangeStatus Attributor::cleanupIR() {
 ChangeStatus Attributor::run() {
   SeedingPeriod = false;
   runTillFixpoint();
-
-  // dump graphs on demand
-  if (DumpDepGraph)
-    DG.dumpGraph();
-
-  if (ViewDepGraph)
-    DG.viewGraph();
-
-  if (PrintDependencies)
-    DG.print();
-
   ChangeStatus ManifestChange = manifestAttributes();
   ChangeStatus CleanupChange = cleanupIR();
   return ManifestChange | CleanupChange;
@@ -2072,31 +2028,8 @@ raw_ostream &llvm::operator<<(raw_ostream &OS, const AbstractAttribute &AA) {
 }
 
 void AbstractAttribute::print(raw_ostream &OS) const {
-  OS << "[";
-  OS << getName();
-  OS << "] for CtxI ";
-
-  if (auto *I = getCtxI()) {
-    OS << "'";
-    I->print(OS);
-    OS << "'";
-  } else
-    OS << "<<null inst>>";
-
-  OS << " at position " << getIRPosition() << " with state " << getAsStr()
-     << '\n';
-}
-
-void AbstractAttribute::printWithDeps(raw_ostream &OS) const {
-  print(OS);
-
-  for (const auto &DepAA : Deps) {
-    auto *AA = DepAA.getPointer();
-    OS << "  updates ";
-    AA->print(OS);
-  }
-
-  OS << '\n';
+  OS << "[P: " << getIRPosition() << "][" << getAsStr() << "][S: " << getState()
+     << "]";
 }
 ///}
 
@@ -2131,8 +2064,8 @@ static bool runAttributorOnFunctions(InformationCache &InfoCache,
       NumFnWithoutExactDefinition++;
 
     // We look at internal functions only on-demand but if any use is not a
-    // direct call or outside the current set of analyzed functions, we have
-    // to do it eagerly.
+    // direct call or outside the current set of analyzed functions, we have to
+    // do it eagerly.
     if (F->hasLocalLinkage()) {
       if (llvm::all_of(F->uses(), [&Functions](const Use &U) {
             const auto *CB = dyn_cast<CallBase>(U.getUser());
@@ -2148,53 +2081,11 @@ static bool runAttributorOnFunctions(InformationCache &InfoCache,
   }
 
   ChangeStatus Changed = A.run();
-
   LLVM_DEBUG(dbgs() << "[Attributor] Done with " << Functions.size()
                     << " functions, result: " << Changed << ".\n");
   return Changed == ChangeStatus::CHANGED;
 }
 
-void AADepGraph::viewGraph() { llvm::ViewGraph(this, "Dependency Graph"); }
-
-void AADepGraph::dumpGraph() {
-  static std::atomic<int> CallTimes;
-  std::string Prefix;
-
-  if (!DepGraphDotFileNamePrefix.empty())
-    Prefix = DepGraphDotFileNamePrefix;
-  else
-    Prefix = "dep_graph";
-  std::string Filename =
-      Prefix + "_" + std::to_string(CallTimes.load()) + ".dot";
-
-  outs() << "Dependency graph dump to " << Filename << ".\n";
-
-  std::error_code EC;
-
-  raw_fd_ostream File(Filename, EC, sys::fs::OF_Text);
-  if (!EC)
-    llvm::WriteGraph(File, this);
-
-  CallTimes++;
-}
-
-void AADepGraph::print() {
-  SmallVector<AbstractAttribute *, 16> AAs;
-  AAs.reserve(SyntheticRoot.Deps.size());
-
-  for (auto tAA : SyntheticRoot.Deps)
-    AAs.push_back(cast<AbstractAttribute>(tAA.getPointer()));
-
-  llvm::sort(AAs, [](AbstractAttribute *LHS, AbstractAttribute *RHS) {
-    if (LHS->getIdAddr() == RHS->getIdAddr())
-      return LHS < RHS;
-    return LHS->getIdAddr() < RHS->getIdAddr();
-  });
-
-  for (AbstractAttribute *AA : AAs)
-    AA->printWithDeps(outs());
-}
-
 PreservedAnalyses AttributorPass::run(Module &M, ModuleAnalysisManager &AM) {
   FunctionAnalysisManager &FAM =
       AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
@@ -2241,51 +2132,6 @@ PreservedAnalyses AttributorCGSCCPass::run(LazyCallGraph::SCC &C,
   return PreservedAnalyses::all();
 }
 
-namespace llvm {
-
-template <> struct GraphTraits<AADepGraphNode *> {
-  using NodeRef = AADepGraphNode *;
-  using DepTy = PointerIntPair<AADepGraphNode *, 1>;
-  using EdgeRef = PointerIntPair<AADepGraphNode *, 1>;
-
-  static NodeRef getEntryNode(AADepGraphNode *DGN) { return DGN; }
-  static NodeRef DepGetVal(DepTy &DT) { return DT.getPointer(); }
-
-  using ChildIteratorType =
-      mapped_iterator<TinyPtrVector<DepTy>::iterator, decltype(&DepGetVal)>;
-  using ChildEdgeIteratorType = TinyPtrVector<DepTy>::iterator;
-
-  static ChildIteratorType child_begin(NodeRef N) { return N->child_begin(); }
-
-  static ChildIteratorType child_end(NodeRef N) { return N->child_end(); }
-};
-
-template <>
-struct GraphTraits<AADepGraph *> : public GraphTraits<AADepGraphNode *> {
-  static NodeRef getEntryNode(AADepGraph *DG) { return DG->GetEntryNode(); }
-
-  using nodes_iterator =
-      mapped_iterator<TinyPtrVector<DepTy>::iterator, decltype(&DepGetVal)>;
-
-  static nodes_iterator nodes_begin(AADepGraph *DG) { return DG->begin(); }
-
-  static nodes_iterator nodes_end(AADepGraph *DG) { return DG->end(); }
-};
-
-template <> struct DOTGraphTraits<AADepGraph *> : public DefaultDOTGraphTraits {
-  DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}
-
-  static std::string getNodeLabel(const AADepGraphNode *Node,
-                                  const AADepGraph *DG) {
-    std::string AAString = "";
-    raw_string_ostream O(AAString);
-    Node->print(O);
-    return AAString;
-  }
-};
-
-} // end namespace llvm
-
 namespace {
 
 struct AttributorLegacyPass : public ModulePass {
diff --git a/llvm/lib/Transforms/IPO/AttributorAttributes.cpp b/llvm/lib/Transforms/IPO/AttributorAttributes.cpp
index 510ddf8a..7e9fd61 100644
--- a/llvm/lib/Transforms/IPO/AttributorAttributes.cpp
+++ b/llvm/lib/Transforms/IPO/AttributorAttributes.cpp
@@ -1052,10 +1052,9 @@ ChangeStatus AAReturnedValuesImpl::updateImpl(Attributor &A) {
   // map, NewRVsMap.
   decltype(ReturnedValues) NewRVsMap;
 
-  auto HandleReturnValue = [&](Value *RV,
-                               SmallSetVector<ReturnInst *, 4> &RIs) {
-    LLVM_DEBUG(dbgs() << "[AAReturnedValues] Returned value: " << *RV << " by #"
-                      << RIs.size() << " RIs\n");
+  auto HandleReturnValue = [&](Value *RV, SmallSetVector<ReturnInst *, 4> &RIs) {
+    LLVM_DEBUG(dbgs() << "[AAReturnedValues] Returned value: " << *RV
+                      << " by #" << RIs.size() << " RIs\n");
     CallBase *CB = dyn_cast<CallBase>(RV);
     if (!CB || UnresolvedCalls.count(CB))
       return;
@@ -3426,6 +3425,7 @@ struct AADereferenceableFloating : AADereferenceableImpl {
         T.GlobalState &= DS.GlobalState;
       }
 
+
       // For now we do not try to "increase" dereferenceability due to negative
       // indices as we first have to come up with code to deal with loops and
       // for overflows of the dereferenceable bytes.
diff --git a/llvm/test/Transforms/Attributor/depgraph.ll b/llvm/test/Transforms/Attributor/depgraph.ll
deleted file mode 100644
index 70597c8..0000000
--- a/llvm/test/Transforms/Attributor/depgraph.ll
+++ /dev/null
@@ -1,152 +0,0 @@
-; RUN: opt -passes=attributor-cgscc -disable-output -attributor-print-dep < %s 2>&1 | FileCheck %s --check-prefixes=GRAPH
-; RUN: opt -passes=attributor-cgscc -disable-output -attributor-dump-dep-graph -attributor-depgraph-dot-filename-prefix=%t < %s 2>/dev/null
-; RUN: FileCheck %s -input-file=%t_0.dot --check-prefix=DOT
-
-; Test 0
-;
-; test copied from the attributor introduction video: checkAndAdvance(), and the C code is:
-; int *checkAndAdvance(int * __attribute__((aligned(16))) p) {
-;   if (*p == 0)
-;     return checkAndAdvance(p + 4);
-;   return p;
-; }
-;
-define i32* @checkAndAdvance(i32* align 16 %0) {
-  %2 = load i32, i32* %0, align 4
-  %3 = icmp eq i32 %2, 0
-  br i1 %3, label %4, label %7
-
-4:                                                ; preds = %1
-  %5 = getelementptr inbounds i32, i32* %0, i64 4
-  %6 = call i32* @checkAndAdvance(i32* %5)
-  br label %8
-
-7:                                                ; preds = %1
-  br label %8
-
-8:                                                ; preds = %7, %4
-  %.0 = phi i32* [ %6, %4 ], [ %0, %7 ]
-  ret i32* %.0
-}
-
-;
-; Check for graph
-;
-
-; GRAPH: [AANoUnwind] for CtxI '  %2 = load i32, i32* %0, align 4' at position {fn:checkAndAdvance [checkAndAdvance@-1]}
-; GRAPH:  updates [AANoCapture] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
-; GRAPH:  updates [AANoUnwind] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs: [@-1]}
-; GRAPH:  updates [AANoCapture] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
-
-; GRAPH: [AANoUnwind] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs: [@-1]}
-; GRAPH:  updates [AAIsDead] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs_ret: [@-1]}
-; GRAPH:  updates [AANoUnwind] for CtxI '  %2 = load i32, i32* %0, align 4' at position {fn:checkAndAdvance [checkAndAdvance@-1]}
-
-; GRAPH: [AANoSync] for CtxI '  %2 = load i32, i32* %0, align 4' at position {fn:checkAndAdvance [checkAndAdvance@-1]} 
-; GRAPH:  updates [AANoSync] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs: [@-1]}
-
-; GRAPH: [AANoSync] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs: [@-1]}
-; GRAPH:  updates [AANoSync] for CtxI '  %2 = load i32, i32* %0, align 4' at position {fn:checkAndAdvance [checkAndAdvance@-1]}
-
-; GRAPH: [AANoFree] for CtxI '  %2 = load i32, i32* %0, align 4' at position {fn:checkAndAdvance [checkAndAdvance@-1]}
-; GRAPH:  updates [AANoFree] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
-; GRAPH:  updates [AANoFree] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs: [@-1]}
-
-; GRAPH: [AANoFree] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
-; GRAPH:  updates [AANoFree] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs_arg: [@0]}
-
-; GRAPH: [AANoFree] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs: [@-1]}
-; GRAPH:  updates [AANoFree] for CtxI '  %2 = load i32, i32* %0, align 4' at position {fn:checkAndAdvance [checkAndAdvance@-1]}
-
-; GRAPH: [AANonNull] for CtxI '  %2 = load i32, i32* %0, align 4' at position {fn_ret:checkAndAdvance [checkAndAdvance@-1]}
-; GRAPH:  updates [AANonNull] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs_ret: [@-1]}
-
-; GRAPH: [AANonNull] for CtxI '  %5 = getelementptr inbounds i32, i32* %0, i64 4' at position {flt: [@-1]}
-; GRAPH:  updates [AANonNull] for CtxI '  %2 = load i32, i32* %0, align 4' at position {fn_ret:checkAndAdvance [checkAndAdvance@-1]}
-
-; GRAPH: [AAAlign] for CtxI '  %2 = load i32, i32* %0, align 4' at position {fn_ret:checkAndAdvance [checkAndAdvance@-1]}
-; GRAPH:  updates [AAAlign] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs_ret: [@-1]}
-
-; GRAPH: [AANoCapture] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
-; GRAPH:  updates [AANoCapture] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs_arg: [@0]}
-
-; GRAPH: [AANoCapture] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs_arg: [@0]}
-; GRAPH:  updates [AANoCapture] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
-
-; GRAPH: [AAMemoryBehavior] for CtxI '  %2 = load i32, i32* %0, align 4' at position {fn:checkAndAdvance [checkAndAdvance@-1]}
-; GRAPH:  updates [AANoCapture] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
-; GRAPH:  updates [AAMemoryBehavior] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
-; GRAPH:  updates [AAMemoryBehavior] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs: [@-1]}
-
-; GRAPH: [AAMemoryBehavior] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
-; GRAPH:  updates [AAMemoryBehavior] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs_arg: [@0]}
-
-; GRAPH: [AAMemoryBehavior] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs: [@-1]}
-; GRAPH:  updates [AAIsDead] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs_ret: [@-1]}
-; GRAPH:  updates [AAMemoryBehavior] for CtxI '  %2 = load i32, i32* %0, align 4' at position {fn:checkAndAdvance [checkAndAdvance@-1]}
-
-; GRAPH: [AAMemoryBehavior] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs_arg: [@0]} with state readonly
-; GRAPH:  updates [AAMemoryLocation] for CtxI '  %2 = load i32, i32* %0, align 4' at position {fn:checkAndAdvance [checkAndAdvance@-1]} with state memory:argument
-
-; GRAPH: [AAMemoryLocation] for CtxI '  %2 = load i32, i32* %0, align 4' at position {fn:checkAndAdvance [checkAndAdvance@-1]} with state memory:argument
-; GRAPH:  updates [AAMemoryLocation] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs: [@-1]} with state memory:argument
-
-; GRAPH: [AAMemoryLocation] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs: [@-1]} with state memory:argument
-; GRAPH:  updates [AAMemoryLocation] for CtxI '  %2 = load i32, i32* %0, align 4' at position {fn:checkAndAdvance [checkAndAdvance@-1]} with state memory:argument
-
-;
-; Check for .dot file
-;
-
-; DOT-DAG: Node[[Node6:0x[a-z0-9]+]] [shape=record,label="{[AANoUnwind] for CtxI '  %2 = load i32, i32* %0, align 4' at position \{fn:checkAndAdvance [checkAndAdvance@-1]\}
-; DOT-DAG: Node[[Node34:0x[a-z0-9]+]] [shape=record,label="{[AANoCapture] for CtxI '  %2 = load i32, i32* %0, align 4' at position \{arg: [@0]\}
-; DOT-DAG: Node[[Node39:0x[a-z0-9]+]] [shape=record,label="{[AANoUnwind] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position \{cs: [@-1]\}
-; DOT-DAG: Node[[Node7:0x[a-z0-9]+]] [shape=record,label="{[AANoSync] for CtxI '  %2 = load i32, i32* %0, align 4' at position \{fn:checkAndAdvance [checkAndAdvance@-1]\}
-; DOT-DAG: Node[[Node61:0x[a-z0-9]+]] [shape=record,label="{[AANoSync] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position \{cs: [@-1]\}
-; DOT-DAG: Node[[Node13:0x[a-z0-9]+]] [shape=record,label="{[AANoFree] for CtxI '  %2 = load i32, i32* %0, align 4' at position \{fn:checkAndAdvance [checkAndAdvance@-1]\}
-; DOT-DAG: Node[[Node36:0x[a-z0-9]+]] [shape=record,label="{[AANoFree] for CtxI '  %2 = load i32, i32* %0, align 4' at position \{arg: [@0]\}
-; DOT-DAG: Node[[Node62:0x[a-z0-9]+]] [shape=record,label="{[AANoFree] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position \{cs: [@-1]\}
-; DOT-DAG: Node[[Node16:0x[a-z0-9]+]] [shape=record,label="{[AAMemoryBehavior] for CtxI '  %2 = load i32, i32* %0, align 4' at position \{fn:checkAndAdvance [checkAndAdvance@-1]\}
-; DOT-DAG: Node[[Node35:0x[a-z0-9]+]] [shape=record,label="{[AAMemoryBehavior] for CtxI '  %2 = load i32, i32* %0, align 4' at position \{arg: [@0]\}
-; DOT-DAG: Node[[Node40:0x[a-z0-9]+]] [shape=record,label="{[AAMemoryBehavior] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position \{cs: [@-1]\}
-; DOT-DAG: Node[[Node17:0x[a-z0-9]+]] [shape=record,label="{[AAMemoryLocation] for CtxI '  %2 = load i32, i32* %0, align 4' at position \{fn:checkAndAdvance [checkAndAdvance@-1]\}
-; DOT-DAG: Node[[Node63:0x[a-z0-9]+]] [shape=record,label="{[AAMemoryLocation] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position \{cs: [@-1]\}
-; DOT-DAG: Node[[Node22:0x[a-z0-9]+]] [shape=record,label="{[AAAlign] for CtxI '  %2 = load i32, i32* %0, align 4' at position \{fn_ret:checkAndAdvance [checkAndAdvance@-1]\}
-; DOT-DAG: Node[[Node65:0x[a-z0-9]+]] [shape=record,label="{[AAAlign] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position \{cs_ret: [@-1]\}
-; DOT-DAG: Node[[Node23:0x[a-z0-9]+]] [shape=record,label="{[AANonNull] for CtxI '  %2 = load i32, i32* %0, align 4' at position \{fn_ret:checkAndAdvance [checkAndAdvance@-1]\}
-; DOT-DAG: Node[[Node67:0x[a-z0-9]+]] [shape=record,label="{[AANonNull] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position \{cs_ret: [@-1]\}
-; DOT-DAG: Node[[Node43:0x[a-z0-9]+]] [shape=record,label="{[AANoCapture] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position \{cs_arg: [@0]\}
-; DOT-DAG: Node[[Node45:0x[a-z0-9]+]] [shape=record,label="{[AAMemoryBehavior] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position \{cs_arg: [@0]\}
-; DOT-DAG: Node[[Node46:0x[a-z0-9]+]] [shape=record,label="{[AANoFree] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position \{cs_arg: [@0]\}
-; DOT-DAG: Node[[Node38:0x[a-z0-9]+]] [shape=record,label="{[AAIsDead] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position \{cs_ret: [@-1]\}
-; DOT-DAG: Node[[Node55:0x[a-z0-9]+]] [shape=record,label="{[AANonNull] for CtxI '  %5 = getelementptr inbounds i32, i32* %0, i64 4' at position \{flt: [@-1]\}
-; DOT-DAG: Node[[Node31:0x[a-x0-9]+]] [shape=record,label="{[AANonNull] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position \{cs_arg: [@0]\}
-
-; DOT-DAG: Node[[Node6]] -> Node[[Node34]]
-; DOT-DAG: Node[[Node6]] -> Node[[Node39]]
-; DOT-DAG: Node[[Node7]] -> Node[[Node61]]
-; DOT-DAG: Node[[Node13]] -> Node[[Node36]]
-; DOT-DAG: Node[[Node13]] -> Node[[Node62]]
-; DOT-DAG: Node[[Node16]] -> Node[[Node34]]
-; DOT-DAG: Node[[Node16]] -> Node[[Node35]]
-; DOT-DAG: Node[[Node16]] -> Node[[Node40]]
-; DOT-DAG: Node[[Node17]] -> Node[[Node63]]
-; DOT-DAG: Node[[Node22]] -> Node[[Node65]]
-; DOT-DAG: Node[[Node23]] -> Node[[Node67]]
-; DOT-DAG: Node[[Node34]] -> Node[[Node43]]
-; DOT-DAG: Node[[Node35]] -> Node[[Node45]]
-; DOT-DAG: Node[[Node36]] -> Node[[Node46]]
-; DOT-DAG: Node[[Node39]] -> Node[[Node38]]
-; DOT-DAG: Node[[Node39]] -> Node[[Node6]]
-; DOT-DAG: Node[[Node40]] -> Node[[Node38]]
-; DOT-DAG: Node[[Node40]] -> Node[[Node16]]
-; DOT-DAG: Node[[Node43]] -> Node[[Node34]]
-; DOT-DAG: Node[[Node45]] -> Node[[Node17]]
-; DOT-DAG: Node[[Node55]] -> Node[[Node55]]
-; DOT-DAG: Node[[Node55]] -> Node[[Node31]]
-; DOT-DAG: Node[[Node55]] -> Node[[Node23]]
-; DOT-DAG: Node[[Node61]] -> Node[[Node7]]
-; DOT-DAG: Node[[Node62]] -> Node[[Node13]]
-; DOT-DAG: Node[[Node63]] -> Node[[Node17]]
-; DOT-DAG: Node[[Node65]] -> Node[[Node22]]
-; DOT-DAG: Node[[Node67]] -> Node[[Node23]]
\ No newline at end of file