Index: llvm/include/llvm/Transforms/IPO/Attributor.h
===================================================================
--- llvm/include/llvm/Transforms/IPO/Attributor.h
+++ llvm/include/llvm/Transforms/IPO/Attributor.h
@@ -97,8 +97,10 @@
 #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"
@@ -115,15 +117,21 @@
 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/Support/Allocator.h"
+#include "llvm/Support/DOTGraphTraits.h"
+#include "llvm/Support/GraphWriter.h"
 #include "llvm/Transforms/Utils/CallGraphUpdater.h"
 
+#include <vector>
+
 namespace llvm {
 
+struct AADepGraphNode;
 struct Attributor;
 struct AbstractAttribute;
 struct InformationCache;
 struct AAIsDead;
 
+class AADepGraph;
 class Function;
 
 /// Simple enum classes that forces properties to be spelled out explicitly.
@@ -143,6 +151,113 @@
 };
 ///}
 
+/// A node in the Abstract Attribute dependency graph.
+///
+/// Typically represents an abstract attribute in the dependency graph.
+struct AADepGraphNode {
+public:
+  // A pair of the class type and the node that this node depends on
+  using DepRecord = std::pair<DepClassTy, AADepGraphNode *>;
+
+public:
+  using DepAAVector = std::vector<DepRecord>;
+
+  using iterator = std::vector<DepRecord>::iterator;
+
+  inline iterator begin() { return DepAAs.begin(); }
+  inline iterator end() { return DepAAs.end(); }
+
+  AbstractAttribute *NodeAA;
+
+  std::vector<DepRecord> DepAAs;
+
+  friend AADepGraph;
+};
+
+/// The data structure for the dependency graph
+class AADepGraph {
+  using DepMapTy = std::map<AbstractAttribute *, AADepGraphNode *>;
+
+  /// A map from \c AbstractAttribute* to \c AADepGraphNode
+  DepMapTy DepMap;
+
+  // There is no root node for the dependence graph, so we create a root node
+  // that uses every node.
+  AADepGraphNode SyntheticRoot;
+
+public:
+  AADepGraph() { SyntheticRoot.NodeAA = nullptr; }
+
+  using iterator = DepMapTy::iterator;
+
+  iterator begin() { return DepMap.begin(); }
+  iterator end() { return DepMap.end(); }
+  AADepGraphNode *getEntryNode() { return &SyntheticRoot; }
+
+  void viewGraph();
+
+  AADepGraphNode *operator[](AbstractAttribute *AA) {
+    AADepGraphNode *Node = DepMap[AA];
+    // If such node does not already exist in the graph,
+    // we need to add it first
+    if (Node == nullptr) {
+      Node = new AADepGraphNode;
+      Node->NodeAA = AA;
+      DepMap[AA] = Node;
+    }
+
+    SyntheticRoot.DepAAs.push_back(std::make_pair(DepClassTy::OPTIONAL, Node));
+    return Node;
+  }
+};
+
+template <> struct GraphTraits<AADepGraphNode *> {
+  using NodeRef = AADepGraphNode *;
+  using DGNPairTy = AADepGraphNode::DepRecord;
+  using EdgeRef = AADepGraphNode::DepRecord &;
+
+  static NodeRef getEntryNode(AADepGraphNode *DGN) { return DGN; }
+  static AADepGraphNode *DGNGetValue(DGNPairTy P) { return P.second; }
+
+  using ChildIteratorType =
+      mapped_iterator<AADepGraphNode::iterator, decltype(&DGNGetValue)>;
+  using ChildEdgeIteratorType = AADepGraphNode::iterator;
+
+  static ChildIteratorType child_begin(NodeRef N) {
+    return ChildIteratorType(N->begin(), &DGNGetValue);
+  }
+
+  static ChildIteratorType child_end(NodeRef N) {
+    return ChildIteratorType(N->end(), &DGNGetValue);
+  }
+
+  static ChildEdgeIteratorType child_edge_begin(NodeRef N) {
+    return N->begin();
+  }
+
+  static ChildEdgeIteratorType child_edge_end(NodeRef N) { return N->end(); }
+};
+
+template <>
+struct GraphTraits<AADepGraph *> : public GraphTraits<AADepGraphNode *> {
+  using PairTy = std::pair<AbstractAttribute *, AADepGraphNode *>;
+
+  static AADepGraphNode *DGGetValuePtr(const PairTy &P) { return P.second; };
+
+  static NodeRef getEntryNode(AADepGraph *DG) { return DG->getEntryNode(); }
+
+  using nodes_iterator =
+      mapped_iterator<AADepGraph::iterator, decltype(&DGGetValuePtr)>;
+
+  static nodes_iterator nodes_begin(AADepGraph *DG) {
+    return nodes_iterator(DG->begin(), &DGGetValuePtr);
+  }
+
+  static nodes_iterator nodes_end(AADepGraph *DG) {
+    return nodes_iterator(DG->end(), &DGGetValuePtr);
+  }
+};
+
 /// 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
@@ -1245,6 +1360,8 @@
   QueryMapTy QueryMap;
   ///}
 
+  AADepGraph DG;
+
   /// Map to remember all requested signature changes (= argument replacements).
   DenseMap<Function *, SmallVector<ArgumentReplacementInfo *, 8>>
       ArgumentReplacementMap;
Index: llvm/lib/Transforms/IPO/Attributor.cpp
===================================================================
--- llvm/lib/Transforms/IPO/Attributor.cpp
+++ llvm/lib/Transforms/IPO/Attributor.cpp
@@ -15,6 +15,7 @@
 
 #include "llvm/Transforms/IPO/Attributor.h"
 
+#include "llvm/ADT/GraphTraits.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/LazyValueInfo.h"
 #include "llvm/Analysis/MustExecute.h"
@@ -23,10 +24,15 @@
 #include "llvm/IR/NoFolder.h"
 #include "llvm/IR/Verifier.h"
 #include "llvm/InitializePasses.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;
 
@@ -1691,6 +1697,10 @@
   else
     DepAAs->OptionalAAs.insert(const_cast<AbstractAttribute *>(&ToAA));
   QueriedNonFixAA = true;
+
+  // record dependence in dep graph
+  DG[const_cast<AbstractAttribute *>(&FromAA)]->DepAAs.push_back(
+      std::make_pair(DepClass, DG[const_cast<AbstractAttribute *>(&ToAA)]));
 }
 
 void Attributor::identifyDefaultAbstractAttributes(Function &F) {
@@ -1997,8 +2007,8 @@
       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());
@@ -2019,6 +2029,20 @@
   return Changed == ChangeStatus::CHANGED;
 }
 
+void AADepGraph::viewGraph() { llvm::ViewGraph(this, "CallGraph"); }
+
+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->NodeAA->print(O);
+    return AAString;
+  }
+};
+
 PreservedAnalyses AttributorPass::run(Module &M, ModuleAnalysisManager &AM) {
   FunctionAnalysisManager &FAM =
       AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();