summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--include/llvm/Analysis/LazyCallGraph.h9
-rw-r--r--lib/Analysis/LazyCallGraph.cpp72
-rw-r--r--unittests/Analysis/LazyCallGraphTest.cpp98
3 files changed, 86 insertions, 93 deletions
diff --git a/include/llvm/Analysis/LazyCallGraph.h b/include/llvm/Analysis/LazyCallGraph.h
index 1b0e1dbf27..6aa0b8e0a2 100644
--- a/include/llvm/Analysis/LazyCallGraph.h
+++ b/include/llvm/Analysis/LazyCallGraph.h
@@ -112,8 +112,7 @@ public:
/// be scanned for "calls" or uses of functions and its child information
/// will be constructed. All of these results are accumulated and cached in
/// the graph.
- class iterator : public std::iterator<std::bidirectional_iterator_tag, Node *,
- ptrdiff_t, Node *, Node *> {
+ class iterator : public std::iterator<std::bidirectional_iterator_tag, Node> {
friend class LazyCallGraph;
friend class LazyCallGraph::Node;
typedef std::iterator<std::bidirectional_iterator_tag, Node *, ptrdiff_t,
@@ -139,14 +138,14 @@ public:
reference operator*() const {
if (NI->is<Node *>())
- return NI->get<Node *>();
+ return *NI->get<Node *>();
Function *F = NI->get<Function *>();
Node &ChildN = G->get(*F);
*NI = &ChildN;
- return &ChildN;
+ return ChildN;
}
- pointer operator->() const { return operator*(); }
+ pointer operator->() const { return &operator*(); }
iterator &operator++() {
++NI;
diff --git a/lib/Analysis/LazyCallGraph.cpp b/lib/Analysis/LazyCallGraph.cpp
index 128448e4c9..2da67227c3 100644
--- a/lib/Analysis/LazyCallGraph.cpp
+++ b/lib/Analysis/LazyCallGraph.cpp
@@ -140,13 +140,13 @@ void LazyCallGraph::SCC::removeEdge(LazyCallGraph &G, Function &Caller,
bool HasOtherCallToCalleeC = false;
bool HasOtherCallOutsideSCC = false;
for (Node *N : *this) {
- for (Node *Callee : *N) {
- SCC *OtherCalleeC = G.SCCMap.lookup(Callee);
- if (OtherCalleeC == &CalleeC) {
+ for (Node &Callee : *N) {
+ SCC &OtherCalleeC = *G.SCCMap.lookup(&Callee);
+ if (&OtherCalleeC == &CalleeC) {
HasOtherCallToCalleeC = true;
break;
}
- if (OtherCalleeC != this)
+ if (&OtherCalleeC != this)
HasOtherCallOutsideSCC = true;
}
if (HasOtherCallToCalleeC)
@@ -234,35 +234,33 @@ LazyCallGraph::SCC::removeInternalEdge(LazyCallGraph &G, Node &Caller,
do {
N = SI->first;
for (auto I = SI->second, E = N->end(); I != E; ++I) {
- Node *ChildN = *I;
+ Node &ChildN = *I;
// If this child isn't currently in this SCC, no need to process it.
// However, we do need to remove this SCC from its SCC's parent set.
- SCC *ChildSCC = G.SCCMap.lookup(ChildN);
- assert(ChildSCC &&
- "Everything reachable must already be in *some* SCC");
- if (ChildSCC != this) {
- ChildSCC->ParentSCCs.remove(this);
+ SCC &ChildSCC = *G.SCCMap.lookup(&ChildN);
+ if (&ChildSCC != this) {
+ ChildSCC.ParentSCCs.remove(this);
continue;
}
- if (ChildN->DFSNumber == 0) {
+ if (ChildN.DFSNumber == 0) {
// Mark that we should start at this child when next this node is the
// top of the stack. We don't start at the next child to ensure this
// child's lowlink is reflected.
SI->second = I;
// Recurse onto this node via a tail call.
- DFSStack.push_back(std::make_pair(ChildN, ChildN->begin()));
+ DFSStack.push_back(std::make_pair(&ChildN, ChildN.begin()));
PushedChildNode = true;
break;
}
// Track the lowest link of the childen, if any are still in the stack.
// Any child not on the stack will have a LowLink of -1.
- assert(ChildN->LowLink != 0 &&
+ assert(ChildN.LowLink != 0 &&
"Low-link must not be zero with a non-zero DFS number.");
- if (ChildN->LowLink >= 0 && ChildN->LowLink < N->LowLink)
- N->LowLink = ChildN->LowLink;
+ if (ChildN.LowLink >= 0 && ChildN.LowLink < N->LowLink)
+ N->LowLink = ChildN.LowLink;
}
if (!PushedChildNode)
// No more children to process for this stack entry.
@@ -293,13 +291,11 @@ LazyCallGraph::SCC::removeInternalEdge(LazyCallGraph &G, Node &Caller,
N->LowLink = -1;
Nodes.push_back(N);
NodeSet.insert(&N->getFunction());
- for (Node *ChildN : *N) {
- if (NewNodes.count(ChildN))
+ for (Node &ChildN : *N) {
+ if (NewNodes.count(&ChildN))
continue;
- SCC *ChildSCC = G.SCCMap.lookup(ChildN);
- assert(ChildSCC &&
- "Must have all child SCCs processed when building a new SCC!");
- ChildSCC->ParentSCCs.insert(this);
+ SCC &ChildSCC = *G.SCCMap.lookup(&ChildN);
+ ChildSCC.ParentSCCs.insert(this);
IsLeafSCC = false;
}
}
@@ -409,13 +405,11 @@ LazyCallGraph::SCC *LazyCallGraph::formSCCFromDFSStack(
// its children.
bool IsLeafSCC = true;
for (Node *SCCN : NewSCC->Nodes)
- for (Node *SCCChildN : *SCCN) {
- if (NewSCC->NodeSet.count(&SCCChildN->getFunction()))
+ for (Node &SCCChildN : *SCCN) {
+ if (NewSCC->NodeSet.count(&SCCChildN.getFunction()))
continue;
- SCC *ChildSCC = SCCMap.lookup(SCCChildN);
- assert(ChildSCC &&
- "Must have all child SCCs processed when building a new SCC!");
- ChildSCC->ParentSCCs.insert(NewSCC);
+ SCC &ChildSCC = *SCCMap.lookup(&SCCChildN);
+ ChildSCC.ParentSCCs.insert(NewSCC);
IsLeafSCC = false;
}
@@ -452,23 +446,23 @@ LazyCallGraph::SCC *LazyCallGraph::getNextSCCInPostOrder() {
do {
Node *N = SI->first;
for (auto I = SI->second, E = N->end(); I != E; ++I) {
- Node *ChildN = *I;
- if (ChildN->DFSNumber == 0) {
+ Node &ChildN = *I;
+ if (ChildN.DFSNumber == 0) {
// Mark that we should start at this child when next this node is the
// top of the stack. We don't start at the next child to ensure this
// child's lowlink is reflected.
SI->second = I;
// Recurse onto this node via a tail call.
- DFSStack.push_back(std::make_pair(ChildN, ChildN->begin()));
+ DFSStack.push_back(std::make_pair(&ChildN, ChildN.begin()));
return LazyCallGraph::getNextSCCInPostOrder();
}
// Track the lowest link of the childen, if any are still in the stack.
- assert(ChildN->LowLink != 0 &&
+ assert(ChildN.LowLink != 0 &&
"Low-link must not be zero with a non-zero DFS number.");
- if (ChildN->LowLink >= 0 && ChildN->LowLink < N->LowLink)
- N->LowLink = ChildN->LowLink;
+ if (ChildN.LowLink >= 0 && ChildN.LowLink < N->LowLink)
+ N->LowLink = ChildN.LowLink;
}
// No more children to process for this stack entry.
SI->second = N->end();
@@ -491,9 +485,9 @@ LazyCallGraphPrinterPass::LazyCallGraphPrinterPass(raw_ostream &OS) : OS(OS) {}
static void printNodes(raw_ostream &OS, LazyCallGraph::Node &N,
SmallPtrSetImpl<LazyCallGraph::Node *> &Printed) {
// Recurse depth first through the nodes.
- for (LazyCallGraph::Node *ChildN : N)
- if (Printed.insert(ChildN))
- printNodes(OS, *ChildN, Printed);
+ for (LazyCallGraph::Node &ChildN : N)
+ if (Printed.insert(&ChildN))
+ printNodes(OS, ChildN, Printed);
OS << " Call edges in function: " << N.getFunction().getName() << "\n";
for (LazyCallGraph::iterator I = N.begin(), E = N.end(); I != E; ++I)
@@ -520,9 +514,9 @@ PreservedAnalyses LazyCallGraphPrinterPass::run(Module *M,
<< "\n\n";
SmallPtrSet<LazyCallGraph::Node *, 16> Printed;
- for (LazyCallGraph::Node *N : G)
- if (Printed.insert(N))
- printNodes(OS, *N, Printed);
+ for (LazyCallGraph::Node &N : G)
+ if (Printed.insert(&N))
+ printNodes(OS, N, Printed);
for (LazyCallGraph::SCC *SCC : G.postorder_sccs())
printSCC(OS, *SCC);
diff --git a/unittests/Analysis/LazyCallGraphTest.cpp b/unittests/Analysis/LazyCallGraphTest.cpp
index a880c64d50..ff6919091c 100644
--- a/unittests/Analysis/LazyCallGraphTest.cpp
+++ b/unittests/Analysis/LazyCallGraphTest.cpp
@@ -128,79 +128,79 @@ TEST(LazyCallGraphTest, BasicGraphFormation) {
// the IR, and everything in our module is an entry node, so just directly
// build variables for each node.
auto I = CG.begin();
- LazyCallGraph::Node *A1 = *I++;
- EXPECT_EQ("a1", A1->getFunction().getName());
- LazyCallGraph::Node *A2 = *I++;
- EXPECT_EQ("a2", A2->getFunction().getName());
- LazyCallGraph::Node *A3 = *I++;
- EXPECT_EQ("a3", A3->getFunction().getName());
- LazyCallGraph::Node *B1 = *I++;
- EXPECT_EQ("b1", B1->getFunction().getName());
- LazyCallGraph::Node *B2 = *I++;
- EXPECT_EQ("b2", B2->getFunction().getName());
- LazyCallGraph::Node *B3 = *I++;
- EXPECT_EQ("b3", B3->getFunction().getName());
- LazyCallGraph::Node *C1 = *I++;
- EXPECT_EQ("c1", C1->getFunction().getName());
- LazyCallGraph::Node *C2 = *I++;
- EXPECT_EQ("c2", C2->getFunction().getName());
- LazyCallGraph::Node *C3 = *I++;
- EXPECT_EQ("c3", C3->getFunction().getName());
- LazyCallGraph::Node *D1 = *I++;
- EXPECT_EQ("d1", D1->getFunction().getName());
- LazyCallGraph::Node *D2 = *I++;
- EXPECT_EQ("d2", D2->getFunction().getName());
- LazyCallGraph::Node *D3 = *I++;
- EXPECT_EQ("d3", D3->getFunction().getName());
+ LazyCallGraph::Node &A1 = *I++;
+ EXPECT_EQ("a1", A1.getFunction().getName());
+ LazyCallGraph::Node &A2 = *I++;
+ EXPECT_EQ("a2", A2.getFunction().getName());
+ LazyCallGraph::Node &A3 = *I++;
+ EXPECT_EQ("a3", A3.getFunction().getName());
+ LazyCallGraph::Node &B1 = *I++;
+ EXPECT_EQ("b1", B1.getFunction().getName());
+ LazyCallGraph::Node &B2 = *I++;
+ EXPECT_EQ("b2", B2.getFunction().getName());
+ LazyCallGraph::Node &B3 = *I++;
+ EXPECT_EQ("b3", B3.getFunction().getName());
+ LazyCallGraph::Node &C1 = *I++;
+ EXPECT_EQ("c1", C1.getFunction().getName());
+ LazyCallGraph::Node &C2 = *I++;
+ EXPECT_EQ("c2", C2.getFunction().getName());
+ LazyCallGraph::Node &C3 = *I++;
+ EXPECT_EQ("c3", C3.getFunction().getName());
+ LazyCallGraph::Node &D1 = *I++;
+ EXPECT_EQ("d1", D1.getFunction().getName());
+ LazyCallGraph::Node &D2 = *I++;
+ EXPECT_EQ("d2", D2.getFunction().getName());
+ LazyCallGraph::Node &D3 = *I++;
+ EXPECT_EQ("d3", D3.getFunction().getName());
EXPECT_EQ(CG.end(), I);
// Build vectors and sort them for the rest of the assertions to make them
// independent of order.
std::vector<std::string> Nodes;
- for (LazyCallGraph::Node *N : *A1)
- Nodes.push_back(N->getFunction().getName());
+ for (LazyCallGraph::Node &N : A1)
+ Nodes.push_back(N.getFunction().getName());
std::sort(Nodes.begin(), Nodes.end());
EXPECT_EQ("a2", Nodes[0]);
EXPECT_EQ("b2", Nodes[1]);
EXPECT_EQ("c3", Nodes[2]);
Nodes.clear();
- EXPECT_EQ(A2->end(), std::next(A2->begin()));
- EXPECT_EQ("a3", A2->begin()->getFunction().getName());
- EXPECT_EQ(A3->end(), std::next(A3->begin()));
- EXPECT_EQ("a1", A3->begin()->getFunction().getName());
+ EXPECT_EQ(A2.end(), std::next(A2.begin()));
+ EXPECT_EQ("a3", A2.begin()->getFunction().getName());
+ EXPECT_EQ(A3.end(), std::next(A3.begin()));
+ EXPECT_EQ("a1", A3.begin()->getFunction().getName());
- for (LazyCallGraph::Node *N : *B1)
- Nodes.push_back(N->getFunction().getName());
+ for (LazyCallGraph::Node &N : B1)
+ Nodes.push_back(N.getFunction().getName());
std::sort(Nodes.begin(), Nodes.end());
EXPECT_EQ("b2", Nodes[0]);
EXPECT_EQ("d3", Nodes[1]);
Nodes.clear();
- EXPECT_EQ(B2->end(), std::next(B2->begin()));
- EXPECT_EQ("b3", B2->begin()->getFunction().getName());
- EXPECT_EQ(B3->end(), std::next(B3->begin()));
- EXPECT_EQ("b1", B3->begin()->getFunction().getName());
+ EXPECT_EQ(B2.end(), std::next(B2.begin()));
+ EXPECT_EQ("b3", B2.begin()->getFunction().getName());
+ EXPECT_EQ(B3.end(), std::next(B3.begin()));
+ EXPECT_EQ("b1", B3.begin()->getFunction().getName());
- for (LazyCallGraph::Node *N : *C1)
- Nodes.push_back(N->getFunction().getName());
+ for (LazyCallGraph::Node &N : C1)
+ Nodes.push_back(N.getFunction().getName());
std::sort(Nodes.begin(), Nodes.end());
EXPECT_EQ("c2", Nodes[0]);
EXPECT_EQ("d2", Nodes[1]);
Nodes.clear();
- EXPECT_EQ(C2->end(), std::next(C2->begin()));
- EXPECT_EQ("c3", C2->begin()->getFunction().getName());
- EXPECT_EQ(C3->end(), std::next(C3->begin()));
- EXPECT_EQ("c1", C3->begin()->getFunction().getName());
-
- EXPECT_EQ(D1->end(), std::next(D1->begin()));
- EXPECT_EQ("d2", D1->begin()->getFunction().getName());
- EXPECT_EQ(D2->end(), std::next(D2->begin()));
- EXPECT_EQ("d3", D2->begin()->getFunction().getName());
- EXPECT_EQ(D3->end(), std::next(D3->begin()));
- EXPECT_EQ("d1", D3->begin()->getFunction().getName());
+ EXPECT_EQ(C2.end(), std::next(C2.begin()));
+ EXPECT_EQ("c3", C2.begin()->getFunction().getName());
+ EXPECT_EQ(C3.end(), std::next(C3.begin()));
+ EXPECT_EQ("c1", C3.begin()->getFunction().getName());
+
+ EXPECT_EQ(D1.end(), std::next(D1.begin()));
+ EXPECT_EQ("d2", D1.begin()->getFunction().getName());
+ EXPECT_EQ(D2.end(), std::next(D2.begin()));
+ EXPECT_EQ("d3", D2.begin()->getFunction().getName());
+ EXPECT_EQ(D3.end(), std::next(D3.begin()));
+ EXPECT_EQ("d1", D3.begin()->getFunction().getName());
// Now lets look at the SCCs.
auto SCCI = CG.postorder_scc_begin();
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-15 16:19:50 +0000