Skip to content

Commit 49d728a

Browse files
chandlercchandlerc
committedSep 16, 2016
[LCG] Redesign the lazy post-order iteration mechanism for the
LazyCallGraph to support repeated, stable iterations, even in the face of graph updates. This is particularly important to allow the CGSCC pass manager to walk the RefSCCs (and thus everything else) in a module more than once. Lots of unittests and other tests were hard or impossible to write because repeated CGSCC pass managers which didn't invalidate the LazyCallGraph would conclude the module was empty after the first one. =[ Really, really bad. The interesting thing is that in many ways this simplifies the code. We can now re-use the same code for handling reference edge insertion updates of the RefSCC graph as we use for handling call edge insertion updates of the SCC graph. Outside of adapting to the shared logic for this (which isn't trivial, but is *much* simpler than the DFS it replaces!), the new code involves putting newly created RefSCCs when deleting a reference edge into the cached list in the correct way, and to re-formulate the iterator to be stable and effective even in the face of these kinds of updates. I've updated the unittests for the LazyCallGraph to re-iterate the postorder sequence and verify that this all works. We even check for using alternating iterators to trigger the lazy formation of RefSCCs after mutation has occured. It's worth noting that there are a reasonable number of likely simplifications we can make past this. It isn't clear that we need to keep the "LeafRefSCCs" around any more. But I've not removed that mostly because I want this to be a more isolated change. Differential Revision: https://reviews.llvm.org/D24219 llvm-svn: 281716
1 parent 0dc4708 commit 49d728a

File tree

3 files changed

+560
-127
lines changed

3 files changed

+560
-127
lines changed
 

‎llvm/include/llvm/Analysis/LazyCallGraph.h

+49-12
Original file line numberDiff line numberDiff line change
@@ -730,27 +730,39 @@ class LazyCallGraph {
730730
struct IsAtEndT {};
731731

732732
LazyCallGraph *G;
733-
RefSCC *C;
733+
RefSCC *RC;
734734

735-
// Build the begin iterator for a node.
736-
postorder_ref_scc_iterator(LazyCallGraph &G) : G(&G) {
737-
C = G.getNextRefSCCInPostOrder();
738-
}
735+
/// Build the begin iterator for a node.
736+
postorder_ref_scc_iterator(LazyCallGraph &G) : G(&G), RC(getRC(G, 0)) {}
739737

740-
// Build the end iterator for a node. This is selected purely by overload.
738+
/// Build the end iterator for a node. This is selected purely by overload.
741739
postorder_ref_scc_iterator(LazyCallGraph &G, IsAtEndT /*Nonce*/)
742-
: G(&G), C(nullptr) {}
740+
: G(&G), RC(nullptr) {}
741+
742+
/// Get the post-order RefSCC at the given index of the postorder walk,
743+
/// populating it if necessary.
744+
static RefSCC *getRC(LazyCallGraph &G, int Index) {
745+
if (Index == (int)G.PostOrderRefSCCs.size())
746+
if (!G.buildNextRefSCCInPostOrder())
747+
// We're at the end.
748+
return nullptr;
749+
750+
assert(Index < (int)G.PostOrderRefSCCs.size() &&
751+
"Built the next post-order RefSCC without growing list!");
752+
return G.PostOrderRefSCCs[Index];
753+
}
743754

744755
public:
745756
bool operator==(const postorder_ref_scc_iterator &Arg) const {
746-
return G == Arg.G && C == Arg.C;
757+
return G == Arg.G && RC == Arg.RC;
747758
}
748759

749-
reference operator*() const { return *C; }
760+
reference operator*() const { return *RC; }
750761

751762
using iterator_facade_base::operator++;
752763
postorder_ref_scc_iterator &operator++() {
753-
C = G->getNextRefSCCInPostOrder();
764+
assert(RC && "Cannot increment the end iterator!");
765+
RC = getRC(*G, G->RefSCCIndices.find(RC)->second + 1);
754766
return *this;
755767
}
756768
};
@@ -897,6 +909,15 @@ class LazyCallGraph {
897909
/// Allocator that holds all the call graph RefSCCs.
898910
SpecificBumpPtrAllocator<RefSCC> RefSCCBPA;
899911

912+
/// The post-order sequence of RefSCCs.
913+
///
914+
/// This list is lazily formed the first time we walk the graph.
915+
SmallVector<RefSCC *, 16> PostOrderRefSCCs;
916+
917+
/// A map from RefSCC to the index for it in the postorder sequence of
918+
/// RefSCCs.
919+
DenseMap<RefSCC *, int> RefSCCIndices;
920+
900921
/// The leaf RefSCCs of the graph.
901922
///
902923
/// These are all of the RefSCCs which have no children.
@@ -944,8 +965,24 @@ class LazyCallGraph {
944965
/// and updates the root leaf list.
945966
void connectRefSCC(RefSCC &RC);
946967

947-
/// Retrieve the next node in the post-order RefSCC walk of the call graph.
948-
RefSCC *getNextRefSCCInPostOrder();
968+
/// Get the index of a RefSCC within the postorder traversal.
969+
///
970+
/// Requires that this RefSCC is a valid one in the (perhaps partial)
971+
/// postorder traversed part of the graph.
972+
int getRefSCCIndex(RefSCC &RC) {
973+
auto IndexIt = RefSCCIndices.find(&RC);
974+
assert(IndexIt != RefSCCIndices.end() && "RefSCC doesn't have an index!");
975+
assert(PostOrderRefSCCs[IndexIt->second] == &RC &&
976+
"Index does not point back at RC!");
977+
return IndexIt->second;
978+
}
979+
980+
/// Builds the next node in the post-order RefSCC walk of the call graph and
981+
/// appends it to the \c PostOrderRefSCCs vector.
982+
///
983+
/// Returns true if a new RefSCC was successfully constructed, and false if
984+
/// there are no more RefSCCs to build in the graph.
985+
bool buildNextRefSCCInPostOrder();
949986
};
950987

951988
inline LazyCallGraph::Edge::Edge() : Value() {}

0 commit comments

Comments
 (0)