From bec37c3fc766a7b97f8c52c181c325fd47b75259 Mon Sep 17 00:00:00 2001 From: bmahjour Date: Mon, 25 Nov 2019 11:12:37 -0500 Subject: [DDG] Data Dependence Graph - Topological Sort Summary: In this patch the DDG DAG is sorted topologically to put the nodes in the graph in the order that would satisfy all dependencies. This helps transformations that would like to generate code based on the DDG. Since the DDG is a DAG a reverse-post-order traversal would give us the topological ordering. This patch also sorts the basic blocks passed to the builder based on program order to ensure that the dependencies are computed in the correct direction. Authored By: bmahjour Reviewer: Meinersbur, fhahn, myhsu, xtian, dmgreen, kbarton, jdoerfert Reviewed By: Meinersbur Subscribers: ychen, arphaman, simoll, a.elovikov, mgorny, hiraditya, jfb, wuzish, llvm-commits, jsji, Whitney, etiotto, ppc-slack Tags: #llvm Differential Revision: https://reviews.llvm.org/D70609 --- llvm/lib/Analysis/DependenceGraphBuilder.cpp | 16 ++++++++++++++++ 1 file changed, 16 insertions(+) (limited to 'llvm/lib/Analysis/DependenceGraphBuilder.cpp') diff --git a/llvm/lib/Analysis/DependenceGraphBuilder.cpp b/llvm/lib/Analysis/DependenceGraphBuilder.cpp index 115f5d6e814..a1ebe38b578 100644 --- a/llvm/lib/Analysis/DependenceGraphBuilder.cpp +++ b/llvm/lib/Analysis/DependenceGraphBuilder.cpp @@ -353,5 +353,21 @@ void AbstractDependenceGraphBuilder::createMemoryDependencyEdges() { } } +template +void AbstractDependenceGraphBuilder::sortNodesTopologically() { + + // If we don't create pi-blocks, then we may not have a DAG. + if (!shouldCreatePiBlocks()) + return; + + SmallVector NodesInPO; + for (NodeType *N : post_order(&Graph)) + NodesInPO.push_back(N); + + Graph.Nodes.clear(); + for (auto &N : make_range(NodesInPO.rbegin(), NodesInPO.rend())) + Graph.Nodes.push_back(N); +} + template class llvm::AbstractDependenceGraphBuilder; template class llvm::DependenceGraphInfo; -- cgit v1.2.3