* Make some methods more const correct.
* Change the FunctionCalls and AuxFunctionCalls vectors into std::lists.
This makes many operations on these lists much more natural, and avoids
*exteremely* expensive copying of DSCallSites (e.g. moving nodes around
between lists, erasing a node from not the end of the vector, etc).
With a profile build of analyze, this speeds up BU DS from 25.14s to
12.59s on 176.gcc. I expect that it would help TD even more, but I don't
have data for it.
This effectively eliminates removeIdenticalCalls and children from the
profile, going from 6.53 to 0.27s.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@19939 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Analysis/DataStructure/BottomUpClosure.cpp b/lib/Analysis/DataStructure/BottomUpClosure.cpp
index 5e6d5f3..0b4d5c1 100644
--- a/lib/Analysis/DataStructure/BottomUpClosure.cpp
+++ b/lib/Analysis/DataStructure/BottomUpClosure.cpp
@@ -247,23 +247,23 @@
void BUDataStructures::calculateGraph(DSGraph &Graph) {
// Move our call site list into TempFCs so that inline call sites go into the
// new call site list and doesn't invalidate our iterators!
- std::vector<DSCallSite> TempFCs;
- std::vector<DSCallSite> &AuxCallsList = Graph.getAuxFunctionCalls();
+ std::list<DSCallSite> TempFCs;
+ std::list<DSCallSite> &AuxCallsList = Graph.getAuxFunctionCalls();
TempFCs.swap(AuxCallsList);
DSGraph::ReturnNodesTy &ReturnNodes = Graph.getReturnNodes();
// Loop over all of the resolvable call sites
- unsigned LastCallSiteIdx = ~0U;
- for (DSCallSiteIterator I = DSCallSiteIterator::begin(TempFCs),
- E = DSCallSiteIterator::end(TempFCs); I != E; ++I) {
- // If we skipped over any call sites, they must be unresolvable, copy them
- // to the real call site list.
- LastCallSiteIdx++;
- for (; LastCallSiteIdx < I.getCallSiteIdx(); ++LastCallSiteIdx)
- AuxCallsList.push_back(TempFCs[LastCallSiteIdx]);
- LastCallSiteIdx = I.getCallSiteIdx();
+ DSCallSiteIterator I = DSCallSiteIterator::begin(TempFCs);
+ DSCallSiteIterator E = DSCallSiteIterator::end(TempFCs);
+
+ // If DSCallSiteIterator skipped over any call sites, they are unresolvable:
+ // move them back to the AuxCallsList.
+ std::list<DSCallSite>::iterator LastCallSiteIdx = TempFCs.begin();
+ while (LastCallSiteIdx != I.getCallSiteIdx())
+ AuxCallsList.splice(AuxCallsList.end(), TempFCs, LastCallSiteIdx++);
+ while (I != E) {
// Resolve the current call...
Function *Callee = *I;
DSCallSite CS = I.getCallSite();
@@ -301,11 +301,23 @@
Callee->getName());
#endif
}
- }
- // Make sure to catch any leftover unresolvable calls...
- for (++LastCallSiteIdx; LastCallSiteIdx < TempFCs.size(); ++LastCallSiteIdx)
- AuxCallsList.push_back(TempFCs[LastCallSiteIdx]);
+ LastCallSiteIdx = I.getCallSiteIdx();
+ ++I; // Move to the next call site.
+
+ if (I.getCallSiteIdx() != LastCallSiteIdx) {
+ ++LastCallSiteIdx; // Skip over the site we already processed.
+
+ // If there are call sites that get skipped over, move them to the aux
+ // calls list: they are not resolvable.
+ if (I != E)
+ while (LastCallSiteIdx != I.getCallSiteIdx())
+ AuxCallsList.splice(AuxCallsList.end(), TempFCs, LastCallSiteIdx++);
+ else
+ while (LastCallSiteIdx != TempFCs.end())
+ AuxCallsList.splice(AuxCallsList.end(), TempFCs, LastCallSiteIdx++);
+ }
+ }
TempFCs.clear();