Sent from my Verizon Wireless 4G LTE DROID
From: “Sean Silva via llvm-dev” <llvm-dev@lists.llvm.org>
To: “llvm-dev” <llvm-dev@lists.llvm.org>
Sent: Wednesday, June 8, 2016 6:19:03 AM
Subject: [llvm-dev] Intended behavior of CGSCC pass manager.Hi Chandler, Philip, Mehdi, (and llvm-dev,)
(this is partially a summary of some discussions that happened at the last LLVM bay area social, and partially a discussion about the direction of the CGSCC pass manager)
A the last LLVM social we discussed the progress on the CGSCC pass manager. It seems like Chandler has a CGSCC pass manager working, but it is still unresolved exactly which semantics we want (more about this below) that are reasonably implementable.
AFAICT, there has been no public discussion about what exact semantics we ultimately want to have. We should figure that out.
The main difficulty which Chandler described is the apparently quite complex logic surrounding needing to run function passes nested within an SCC pass manager, while providing some guarantees about exactly what order the function passes are run. The existing CGSCC pass manager just punts on some of the problems that arise (look in CGPassManager::runOnModule, CGPassManager::RunAllPassesOnSCC, and CGPassManager::RunPassOnSCC in llvm/lib/Analysis/CallGraphSCCPass.cpp), and these are the problems that Chandler has been trying to solve.
(
Why is this “function passes inside CGSCC passes” stuff interesting? Because LLVM can do inlining on an SCC (often just a single function) and then run function passes to simplify the function(s) in the SCC before it tries to inline into a parent SCC. (the SCC visitation order is post-order)
For example, we may inline a bunch of code, but after inlining we can tremendously simplify the function, and we want to do so before considering this function for inlining into its callers so that we get an accurate evaluation of the inline cost.
Based on what Chandler said, it seems that LLVM is fairly unique in this regard and other compilers don’t do this (which is why we can’t just look at how other compilers solve this problem; they don’t have this problem (maybe they should? or maybe we shouldn’t?)). For example, he described that GCC uses different inlining “phases”; e.g. it does early inlining on the entire module, then does simplifications on the entire module, then does late inlining on the entire module; so it is not able to incrementally simplify as it inlines like LLVM does.This incremental simplification is an important feature of our inliner, and one we should endeavor to keep. We might also want different phases at some point (e.g. a top-down and a bottom-up phase), but that’s another story.
)
As background for what is below, the LazyCallGraph tracks two graphs: the “call graph” and the “ref graph”.
Conceptually, the call graph is the graph of direct calls, where indirect calls and calls to external functions do not appear (or are connected to dummy nodes). The ref graph is basically the graph of all functions transitively accessible based on the globals/constants/etc. referenced by a function (e.g. if a functionfoo
references a vtable that is defined in the module, there is an edge in the ref graph fromfoo
to every function in the vtable).
The call graph is a strict subset of the ref graph.Chandler described that he had a major breakthrough in that the CGSCC pass manager only had to deal with 3 classes of modifications that can occur:
- a pass may e.g. propagate a load of a function pointer into an indirect call, turning it into an direct call. This requires adding an edge in the CG but not in the ref graph.
- a pass may take a direct call and turn it into an indirect call. This requires removing an edge from the CG, but not in the ref graph.
- a pass may delete a direct call. This removes an edge in the CG and also in the ref graph.
From the perspective of the CGSCC pass manager, these operations can affect the SCC structure. Adding an edge might merge SCC’s and deleting an edge might split SCC’s. Chandler mentioned that apparently the issues of splitting and merging SCC’s within the current infrastructure are actually quite challenging and lead to e.g. iterator invalidation issues, and that is what he is working on.
(
The ref graph is important to guide the overall SCC visitation order because it basically represents “the largest graph that the CG may turn into due to our static analysis of this module”. I.e. no transformation we can statically make in the CGSCC passes can ever cause us to need to merge SCC’s in the ref graph.
)I have a couple overall questions/concerns:
- The ref graph can easily go quadratic. E.g.
typedef void (*fp)();
fp funcs = {
&foo1,
&foo2,
…
&fooN
}
void foo1() { funcssomething; }
void foo2() { funcssomething; }
…
void fooN() { funcssomething; }One real-world case where this might come about is in the presence of vtables.
The existing CGSCC pass manager does not have this issue AFAIK because it does not consider the ref graph.
Does anybody have any info/experience about how densely connected the ref graph can get in programs that might reasonably be fed to the compiler?
I just did a quick sanity check with LLD/ELF using--lto-newpm-passes=cgscc(no-op-cgscc)
and it at least seemed to terminate / not run out of memory. Based on some rough calculations looking at the profile, it seem like the entire run of the inliner in the old LTO pipeline (which is about 5% of total LTO time on this particular example I looked at) is only 2-3x as expensive as just--lto-newpm-passes=cgscc(no-op-cgscc)
, so the LazyCallGraph construction is certainly not free.
- What is the intended behavior of CGSCC passes when SCC’s are split or merged? E.g. a CGSCC pass runs on an SCC (e.g. the inliner). Now we run some function passes nested inside the CGSCC pass manager (e.g. to simplify things after inlining). Consider:
This is not how I thought the current scheme worked – I was under the impression that we had a call graph with conservatively-connected dummy nodes for external/indirect functions.
The fact that we have a separate nodes for calling into an external function and “being called” from an external function, these don’t form SCC. So it means we can end up merging SCC IIUC.
Yes, although I thought there was only one dummy node for those things.
-Hal