Revert "Data Dependence Graph Basics"

This reverts commit c98ec60993a7aa65073692b62f6d728b36e68ccd, which broke the sphinx-docs build.

llvm-svn: 372168

3 files changed, 0 insertions, 383 deletions

diff --git a/llvm/lib/Analysis/CMakeLists.txt b/llvm/lib/Analysis/CMakeLists.txt
index 3d4920e5ead..1dc9544120e 100644
--- a/llvm/lib/Analysis/CMakeLists.txt
+++ b/llvm/lib/Analysis/CMakeLists.txt
@@ -22,11 +22,9 @@ add_llvm_library(LLVMAnalysis
   CostModel.cpp
   CodeMetrics.cpp
   ConstantFolding.cpp
-  DDG.cpp
   Delinearization.cpp
   DemandedBits.cpp
   DependenceAnalysis.cpp
-  DependenceGraphBuilder.cpp
   DivergenceAnalysis.cpp
   DomPrinter.cpp
   DomTreeUpdater.cpp
diff --git a/llvm/lib/Analysis/DDG.cpp b/llvm/lib/Analysis/DDG.cpp
deleted file mode 100644
index 29778b3e0d6..00000000000
--- a/llvm/lib/Analysis/DDG.cpp
+++ /dev/null
@@ -1,181 +0,0 @@
-//===- DDG.cpp - Data Dependence Graph -------------------------------------==//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-//
-// The implementation for the data dependence graph.
-//===----------------------------------------------------------------------===//
-#include "llvm/Analysis/DDG.h"
-#include "llvm/Analysis/LoopInfo.h"
-
-using namespace llvm;
-
-#define DEBUG_TYPE "ddg"
-
-template class llvm::DGEdge<DDGNode, DDGEdge>;
-template class llvm::DGNode<DDGNode, DDGEdge>;
-template class llvm::DirectedGraph<DDGNode, DDGEdge>;
-
-//===--------------------------------------------------------------------===//
-// DDGNode implementation
-//===--------------------------------------------------------------------===//
-DDGNode::~DDGNode() {}
-
-bool DDGNode::collectInstructions(
-    llvm::function_ref<bool(Instruction *)> const &Pred,
-    InstructionListType &IList) const {
-  assert(IList.empty() && "Expected the IList to be empty on entry.");
-  if (isa<SimpleDDGNode>(this)) {
-    for (auto *I : cast<const SimpleDDGNode>(this)->getInstructions())
-      if (Pred(I))
-        IList.push_back(I);
-  } else
-    llvm_unreachable("unimplemented type of node");
-  return !IList.empty();
-}
-
-raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGNode::NodeKind K) {
-  const char *Out;
-  switch (K) {
-  case DDGNode::NodeKind::SingleInstruction:
-    Out = "single-instruction";
-    break;
-  case DDGNode::NodeKind::MultiInstruction:
-    Out = "multi-instruction";
-    break;
-  case DDGNode::NodeKind::Unknown:
-    Out = "??";
-    break;
-  }
-  OS << Out;
-  return OS;
-}
-
-raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGNode &N) {
-  OS << "Node Address:" << &N << ":" << N.getKind() << "\n";
-  if (isa<SimpleDDGNode>(N)) {
-    OS << " Instructions:\n";
-    for (auto *I : cast<const SimpleDDGNode>(N).getInstructions())
-      OS.indent(2) << *I << "\n";
-  } else
-    llvm_unreachable("unimplemented type of node");
-
-  OS << (N.getEdges().empty() ? " Edges:none!\n" : " Edges:\n");
-  for (auto &E : N.getEdges())
-    OS.indent(2) << *E;
-  return OS;
-}
-
-//===--------------------------------------------------------------------===//
-// SimpleDDGNode implementation
-//===--------------------------------------------------------------------===//
-
-SimpleDDGNode::SimpleDDGNode(Instruction &I)
-  : DDGNode(NodeKind::SingleInstruction), InstList() {
-  assert(InstList.empty() && "Expected empty list.");
-  InstList.push_back(&I);
-}
-
-SimpleDDGNode::SimpleDDGNode(const SimpleDDGNode &N)
-    : DDGNode(N), InstList(N.InstList) {
-  assert(((getKind() == NodeKind::SingleInstruction && InstList.size() == 1) ||
-          (getKind() == NodeKind::MultiInstruction && InstList.size() > 1)) &&
-         "constructing from invalid simple node.");
-}
-
-SimpleDDGNode::SimpleDDGNode(SimpleDDGNode &&N)
-    : DDGNode(std::move(N)), InstList(std::move(N.InstList)) {
-  assert(((getKind() == NodeKind::SingleInstruction && InstList.size() == 1) ||
-          (getKind() == NodeKind::MultiInstruction && InstList.size() > 1)) &&
-         "constructing from invalid simple node.");
-}
-
-SimpleDDGNode::~SimpleDDGNode() { InstList.clear(); }
-
-//===--------------------------------------------------------------------===//
-// DDGEdge implementation
-//===--------------------------------------------------------------------===//
-
-raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGEdge::EdgeKind K) {
-  const char *Out;
-  switch (K) {
-  case DDGEdge::EdgeKind::RegisterDefUse:
-    Out = "def-use";
-    break;
-  case DDGEdge::EdgeKind::MemoryDependence:
-    Out = "memory";
-    break;
-  case DDGEdge::EdgeKind::Unknown:
-    Out = "??";
-    break;
-  }
-  OS << Out;
-  return OS;
-}
-
-raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGEdge &E) {
-  OS << "[" << E.getKind() << "] to " << &E.getTargetNode() << "\n";
-  return OS;
-}
-
-//===--------------------------------------------------------------------===//
-// DataDependenceGraph implementation
-//===--------------------------------------------------------------------===//
-using BasicBlockListType = SmallVector<BasicBlock *, 8>;
-
-DataDependenceGraph::DataDependenceGraph(Function &F, DependenceInfo &D)
-    : DependenceGraphInfo(F.getName().str(), D) {
-  BasicBlockListType BBList;
-  for (auto &BB : F.getBasicBlockList())
-    BBList.push_back(&BB);
-  DDGBuilder(*this, D, BBList).populate();
-}
-
-DataDependenceGraph::DataDependenceGraph(const Loop &L, DependenceInfo &D)
-    : DependenceGraphInfo(Twine(L.getHeader()->getParent()->getName() + "." +
-                                L.getHeader()->getName())
-                              .str(),
-                          D) {
-  BasicBlockListType BBList;
-  for (BasicBlock *BB : L.blocks())
-    BBList.push_back(BB);
-  DDGBuilder(*this, D, BBList).populate();
-}
-
-DataDependenceGraph::~DataDependenceGraph() {
-  for (auto *N : Nodes) {
-    for (auto *E : *N)
-      delete E;
-    delete N;
-  }
-}
-
-raw_ostream &llvm::operator<<(raw_ostream &OS, const DataDependenceGraph &G) {
-  for (auto *Node : G)
-    OS << *Node << "\n";
-  return OS;
-}
-
-//===--------------------------------------------------------------------===//
-// DDG Analysis Passes
-//===--------------------------------------------------------------------===//
-
-/// DDG as a loop pass.
-DDGAnalysis::Result DDGAnalysis::run(Loop &L, LoopAnalysisManager &AM,
-                                     LoopStandardAnalysisResults &AR) {
-  Function *F = L.getHeader()->getParent();
-  DependenceInfo DI(F, &AR.AA, &AR.SE, &AR.LI);
-  return std::make_unique<DataDependenceGraph>(L, DI);
-}
-AnalysisKey DDGAnalysis::Key;
-
-PreservedAnalyses DDGAnalysisPrinterPass::run(Loop &L, LoopAnalysisManager &AM,
-                                              LoopStandardAnalysisResults &AR,
-                                              LPMUpdater &U) {
-  OS << "'DDG' for loop '" << L.getHeader()->getName() << "':\n";
-  OS << *AM.getResult<DDGAnalysis>(L, AR);
-  return PreservedAnalyses::all();
-}
diff --git a/llvm/lib/Analysis/DependenceGraphBuilder.cpp b/llvm/lib/Analysis/DependenceGraphBuilder.cpp
deleted file mode 100644
index ed21cc7134f..00000000000
--- a/llvm/lib/Analysis/DependenceGraphBuilder.cpp
+++ /dev/null
@@ -1,200 +0,0 @@
-//===- DependenceGraphBuilder.cpp ------------------------------------------==//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-// This file implements common steps of the build algorithm for construction
-// of dependence graphs such as DDG and PDG.
-//===----------------------------------------------------------------------===//
-
-#include "llvm/Analysis/DependenceGraphBuilder.h"
-#include "llvm/ADT/SCCIterator.h"
-#include "llvm/ADT/Statistic.h"
-#include "llvm/Analysis/DDG.h"
-
-using namespace llvm;
-
-#define DEBUG_TYPE "dgb"
-
-STATISTIC(TotalGraphs, "Number of dependence graphs created.");
-STATISTIC(TotalDefUseEdges, "Number of def-use edges created.");
-STATISTIC(TotalMemoryEdges, "Number of memory dependence edges created.");
-STATISTIC(TotalFineGrainedNodes, "Number of fine-grained nodes created.");
-STATISTIC(TotalConfusedEdges,
-          "Number of confused memory dependencies between two nodes.");
-STATISTIC(TotalEdgeReversals,
-          "Number of times the source and sink of dependence was reversed to "
-          "expose cycles in the graph.");
-
-using InstructionListType = SmallVector<Instruction *, 2>;
-
-//===--------------------------------------------------------------------===//
-// AbstractDependenceGraphBuilder implementation
-//===--------------------------------------------------------------------===//
-
-template <class G>
-void AbstractDependenceGraphBuilder<G>::createFineGrainedNodes() {
-  ++TotalGraphs;
-  assert(IMap.empty() && "Expected empty instruction map at start");
-  for (BasicBlock *BB : BBList)
-    for (Instruction &I : *BB) {
-      auto &NewNode = createFineGrainedNode(I);
-      IMap.insert(std::make_pair(&I, &NewNode));
-      ++TotalFineGrainedNodes;
-    }
-}
-
-template <class G> void AbstractDependenceGraphBuilder<G>::createDefUseEdges() {
-  for (NodeType *N : Graph) {
-    InstructionListType SrcIList;
-    N->collectInstructions([](const Instruction *I) { return true; }, SrcIList);
-
-    // Use a set to mark the targets that we link to N, so we don't add
-    // duplicate def-use edges when more than one instruction in a target node
-    // use results of instructions that are contained in N.
-    SmallPtrSet<NodeType *, 4> VisitedTargets;
-
-    for (Instruction *II : SrcIList) {
-      for (User *U : II->users()) {
-        Instruction *UI = dyn_cast<Instruction>(U);
-        if (!UI)
-          continue;
-        NodeType *DstNode = nullptr;
-        if (IMap.find(UI) != IMap.end())
-          DstNode = IMap.find(UI)->second;
-
-        // In the case of loops, the scope of the subgraph is all the
-        // basic blocks (and instructions within them) belonging to the loop. We
-        // simply ignore all the edges coming from (or going into) instructions
-        // or basic blocks outside of this range.
-        if (!DstNode) {
-          LLVM_DEBUG(
-              dbgs()
-              << "skipped def-use edge since the sink" << *UI
-              << " is outside the range of instructions being considered.\n");
-          continue;
-        }
-
-        // Self dependencies are ignored because they are redundant and
-        // uninteresting.
-        if (DstNode == N) {
-          LLVM_DEBUG(dbgs()
-                     << "skipped def-use edge since the sink and the source ("
-                     << N << ") are the same.\n");
-          continue;
-        }
-
-        if (VisitedTargets.insert(DstNode).second) {
-          createDefUseEdge(*N, *DstNode);
-          ++TotalDefUseEdges;
-        }
-      }
-    }
-  }
-}
-
-template <class G>
-void AbstractDependenceGraphBuilder<G>::createMemoryDependencyEdges() {
-  using DGIterator = typename G::iterator;
-  auto isMemoryAccess = [](const Instruction *I) {
-    return I->mayReadOrWriteMemory();
-  };
-  for (DGIterator SrcIt = Graph.begin(), E = Graph.end(); SrcIt != E; ++SrcIt) {
-    InstructionListType SrcIList;
-    (*SrcIt)->collectInstructions(isMemoryAccess, SrcIList);
-    if (SrcIList.empty())
-      continue;
-
-    for (DGIterator DstIt = SrcIt; DstIt != E; ++DstIt) {
-      if (**SrcIt == **DstIt)
-        continue;
-      InstructionListType DstIList;
-      (*DstIt)->collectInstructions(isMemoryAccess, DstIList);
-      if (DstIList.empty())
-        continue;
-      bool ForwardEdgeCreated = false;
-      bool BackwardEdgeCreated = false;
-      for (Instruction *ISrc : SrcIList) {
-        for (Instruction *IDst : DstIList) {
-          auto D = DI.depends(ISrc, IDst, true);
-          if (!D)
-            continue;
-
-          // If we have a dependence with its left-most non-'=' direction
-          // being '>' we need to reverse the direction of the edge, because
-          // the source of the dependence cannot occur after the sink. For
-          // confused dependencies, we will create edges in both directions to
-          // represent the possibility of a cycle.
-
-          auto createConfusedEdges = [&](NodeType &Src, NodeType &Dst) {
-            if (!ForwardEdgeCreated) {
-              createMemoryEdge(Src, Dst);
-              ++TotalMemoryEdges;
-            }
-            if (!BackwardEdgeCreated) {
-              createMemoryEdge(Dst, Src);
-              ++TotalMemoryEdges;
-            }
-            ForwardEdgeCreated = BackwardEdgeCreated = true;
-            ++TotalConfusedEdges;
-          };
-
-          auto createForwardEdge = [&](NodeType &Src, NodeType &Dst) {
-            if (!ForwardEdgeCreated) {
-              createMemoryEdge(Src, Dst);
-              ++TotalMemoryEdges;
-            }
-            ForwardEdgeCreated = true;
-          };
-
-          auto createBackwardEdge = [&](NodeType &Src, NodeType &Dst) {
-            if (!BackwardEdgeCreated) {
-              createMemoryEdge(Dst, Src);
-              ++TotalMemoryEdges;
-            }
-            BackwardEdgeCreated = true;
-          };
-
-          if (D->isConfused())
-            createConfusedEdges(**SrcIt, **DstIt);
-          else if (D->isOrdered() && !D->isLoopIndependent()) {
-            bool ReversedEdge = false;
-            for (unsigned Level = 1; Level <= D->getLevels(); ++Level) {
-              if (D->getDirection(Level) == Dependence::DVEntry::EQ)
-                continue;
-              else if (D->getDirection(Level) == Dependence::DVEntry::GT) {
-                createBackwardEdge(**SrcIt, **DstIt);
-                ReversedEdge = true;
-                ++TotalEdgeReversals;
-                break;
-              } else if (D->getDirection(Level) == Dependence::DVEntry::LT)
-                break;
-              else {
-                createConfusedEdges(**SrcIt, **DstIt);
-                break;
-              }
-            }
-            if (!ReversedEdge)
-              createForwardEdge(**SrcIt, **DstIt);
-          } else
-            createForwardEdge(**SrcIt, **DstIt);
-
-          // Avoid creating duplicate edges.
-          if (ForwardEdgeCreated && BackwardEdgeCreated)
-            break;
-        }
-
-        // If we've created edges in both directions, there is no more
-        // unique edge that we can create between these two nodes, so we
-        // can exit early.
-        if (ForwardEdgeCreated && BackwardEdgeCreated)
-          break;
-      }
-    }
-  }
-}
-
-template class llvm::AbstractDependenceGraphBuilder<DataDependenceGraph>;
-template class llvm::DependenceGraphInfo<DDGNode>;