summaryrefslogtreecommitdiff
path: root/llvm/lib/Analysis/DDG.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib/Analysis/DDG.cpp')
-rw-r--r--llvm/lib/Analysis/DDG.cpp112
1 files changed, 96 insertions, 16 deletions
diff --git a/llvm/lib/Analysis/DDG.cpp b/llvm/lib/Analysis/DDG.cpp
index b5c3c761ad98f..90ce13e6f6503 100644
--- a/llvm/lib/Analysis/DDG.cpp
+++ b/llvm/lib/Analysis/DDG.cpp
@@ -9,10 +9,17 @@
// The implementation for the data dependence graph.
//===----------------------------------------------------------------------===//
#include "llvm/Analysis/DDG.h"
+#include "llvm/ADT/SCCIterator.h"
#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/LoopIterator.h"
+#include "llvm/Support/CommandLine.h"
using namespace llvm;
+static cl::opt<bool>
+ CreatePiBlocks("ddg-pi-blocks", cl::init(true), cl::Hidden, cl::ZeroOrMore,
+ cl::desc("Create pi-block nodes."));
+
#define DEBUG_TYPE "ddg"
template class llvm::DGEdge<DDGNode, DDGEdge>;
@@ -29,9 +36,16 @@ bool DDGNode::collectInstructions(
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())
+ for (Instruction *I : cast<const SimpleDDGNode>(this)->getInstructions())
if (Pred(I))
IList.push_back(I);
+ } else if (isa<PiBlockDDGNode>(this)) {
+ for (const DDGNode *PN : cast<const PiBlockDDGNode>(this)->getNodes()) {
+ assert(!isa<PiBlockDDGNode>(PN) && "Nested PiBlocks are not supported.");
+ SmallVector<Instruction *, 8> TmpIList;
+ PN->collectInstructions(Pred, TmpIList);
+ IList.insert(IList.end(), TmpIList.begin(), TmpIList.end());
+ }
} else
llvm_unreachable("unimplemented type of node");
return !IList.empty();
@@ -46,11 +60,14 @@ raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGNode::NodeKind K) {
case DDGNode::NodeKind::MultiInstruction:
Out = "multi-instruction";
break;
+ case DDGNode::NodeKind::PiBlock:
+ Out = "pi-block";
+ break;
case DDGNode::NodeKind::Root:
Out = "root";
break;
case DDGNode::NodeKind::Unknown:
- Out = "??";
+ Out = "?? (error)";
break;
}
OS << Out;
@@ -61,8 +78,15 @@ 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())
+ for (const Instruction *I : cast<const SimpleDDGNode>(N).getInstructions())
OS.indent(2) << *I << "\n";
+ } else if (isa<PiBlockDDGNode>(&N)) {
+ OS << "--- start of nodes in pi-block ---\n";
+ auto &Nodes = cast<const PiBlockDDGNode>(&N)->getNodes();
+ unsigned Count = 0;
+ for (const DDGNode *N : Nodes)
+ OS << *N << (++Count == Nodes.size() ? "" : "\n");
+ OS << "--- end of nodes in pi-block ---\n";
} else if (!isa<RootDDGNode>(N))
llvm_unreachable("unimplemented type of node");
@@ -99,6 +123,29 @@ SimpleDDGNode::SimpleDDGNode(SimpleDDGNode &&N)
SimpleDDGNode::~SimpleDDGNode() { InstList.clear(); }
//===--------------------------------------------------------------------===//
+// PiBlockDDGNode implementation
+//===--------------------------------------------------------------------===//
+
+PiBlockDDGNode::PiBlockDDGNode(const PiNodeList &List)
+ : DDGNode(NodeKind::PiBlock), NodeList(List) {
+ assert(!NodeList.empty() && "pi-block node constructed with an empty list.");
+}
+
+PiBlockDDGNode::PiBlockDDGNode(const PiBlockDDGNode &N)
+ : DDGNode(N), NodeList(N.NodeList) {
+ assert(getKind() == NodeKind::PiBlock && !NodeList.empty() &&
+ "constructing from invalid pi-block node.");
+}
+
+PiBlockDDGNode::PiBlockDDGNode(PiBlockDDGNode &&N)
+ : DDGNode(std::move(N)), NodeList(std::move(N.NodeList)) {
+ assert(getKind() == NodeKind::PiBlock && !NodeList.empty() &&
+ "constructing from invalid pi-block node.");
+}
+
+PiBlockDDGNode::~PiBlockDDGNode() { NodeList.clear(); }
+
+//===--------------------------------------------------------------------===//
// DDGEdge implementation
//===--------------------------------------------------------------------===//
@@ -115,7 +162,7 @@ raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGEdge::EdgeKind K) {
Out = "rooted";
break;
case DDGEdge::EdgeKind::Unknown:
- Out = "??";
+ Out = "?? (error)";
break;
}
OS << Out;
@@ -134,19 +181,28 @@ using BasicBlockListType = SmallVector<BasicBlock *, 8>;
DataDependenceGraph::DataDependenceGraph(Function &F, DependenceInfo &D)
: DependenceGraphInfo(F.getName().str(), D) {
+ // Put the basic blocks in program order for correct dependence
+ // directions.
BasicBlockListType BBList;
- for (auto &BB : F.getBasicBlockList())
- BBList.push_back(&BB);
+ for (auto &SCC : make_range(scc_begin(&F), scc_end(&F)))
+ for (BasicBlock * BB : SCC)
+ BBList.push_back(BB);
+ std::reverse(BBList.begin(), BBList.end());
DDGBuilder(*this, D, BBList).populate();
}
-DataDependenceGraph::DataDependenceGraph(const Loop &L, DependenceInfo &D)
+DataDependenceGraph::DataDependenceGraph(Loop &L, LoopInfo &LI,
+ DependenceInfo &D)
: DependenceGraphInfo(Twine(L.getHeader()->getParent()->getName() + "." +
L.getHeader()->getName())
.str(),
D) {
+ // Put the basic blocks in program order for correct dependence
+ // directions.
+ LoopBlocksDFS DFS(&L);
+ DFS.perform(&LI);
BasicBlockListType BBList;
- for (BasicBlock *BB : L.blocks())
+ for (BasicBlock *BB : make_range(DFS.beginRPO(), DFS.endRPO()))
BBList.push_back(BB);
DDGBuilder(*this, D, BBList).populate();
}
@@ -164,23 +220,47 @@ bool DataDependenceGraph::addNode(DDGNode &N) {
return false;
// In general, if the root node is already created and linked, it is not safe
- // to add new nodes since they may be unreachable by the root.
- // TODO: Allow adding Pi-block nodes after root is created. Pi-blocks are an
- // exception because they represent components that are already reachable by
- // root.
- assert(!Root && "Root node is already added. No more nodes can be added.");
+ // to add new nodes since they may be unreachable by the root. However,
+ // pi-block nodes need to be added after the root node is linked, and they are
+ // always reachable by the root, because they represent components that are
+ // already reachable by root.
+ auto *Pi = dyn_cast<PiBlockDDGNode>(&N);
+ assert((!Root || Pi) &&
+ "Root node is already added. No more nodes can be added.");
+
if (isa<RootDDGNode>(N))
Root = &N;
+ if (Pi)
+ for (DDGNode *NI : Pi->getNodes())
+ PiBlockMap.insert(std::make_pair(NI, Pi));
+
return true;
}
+const PiBlockDDGNode *DataDependenceGraph::getPiBlock(const NodeType &N) const {
+ if (PiBlockMap.find(&N) == PiBlockMap.end())
+ return nullptr;
+ auto *Pi = PiBlockMap.find(&N)->second;
+ assert(PiBlockMap.find(Pi) == PiBlockMap.end() &&
+ "Nested pi-blocks detected.");
+ return Pi;
+}
+
raw_ostream &llvm::operator<<(raw_ostream &OS, const DataDependenceGraph &G) {
- for (auto *Node : G)
- OS << *Node << "\n";
+ for (DDGNode *Node : G)
+ // Avoid printing nodes that are part of a pi-block twice. They will get
+ // printed when the pi-block is printed.
+ if (!G.getPiBlock(*Node))
+ OS << *Node << "\n";
+ OS << "\n";
return OS;
}
+bool DDGBuilder::shouldCreatePiBlocks() const {
+ return CreatePiBlocks;
+}
+
//===--------------------------------------------------------------------===//
// DDG Analysis Passes
//===--------------------------------------------------------------------===//
@@ -190,7 +270,7 @@ 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);
+ return std::make_unique<DataDependenceGraph>(L, AR.LI, DI);
}
AnalysisKey DDGAnalysis::Key;
generated by cgit v1.2.3 (git 2.25.1) at 2025-07-17 02:39:57 +0000