I'm looking at bug 3367. If I run: $ opt b.bc -inline -loop-rotate -loop-unswitch -debug-pass=Executions ... it eventually crashes in the inliner, because the call graph isn't up to date. (NB if you want to reproduce this you'll have to apply my patch from bug 3367 first.) The reason the call graph isn't up to date is that -loop-unswitch has changed a function and not updated the call graph. But that seems OK, because -loop-unswitch's getAnalysisUsage() method doesn't claim to preserve the call graph. So are loop passed *required* to preserved the call graph, in the same way that CallGraphSCC passes are? Or should the pass manager take care of rebuilding the call graph before calling the inliner on an SCC whose functions have been changed? I don't see any evidence of this happening. I've attached the full output from -debug-pass=Executions -debug-only=inline. You can see that the loop pass manager modifies function readClause(), and then the inliner decides to inline readClause() into parse_DIMACS_main(), but I don't think the call graph is being rebuilt in between those two points. Any ideas? Thanks, Jay. -------------- next part -------------- A non-text attachment was scrubbed... Name: executions Type: application/octet-stream Size: 34890 bytes Desc: not available URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20090213/785ae7f8/attachment.obj>
Hi,> I'm looking at bug 3367. > > If I run: > > $ opt b.bc -inline -loop-rotate -loop-unswitch -debug-pass=Executions > > ... it eventually crashes in the inliner, because the call graph isn't > up to date. (NB if you want to reproduce this you'll have to apply my > patch from bug 3367 first.) > > The reason the call graph isn't up to date is that -loop-unswitch has > changed a function and not updated the call graph. But that seems OK, > because -loop-unswitch's getAnalysisUsage() method doesn't claim to > preserve the call graph.given the callgraph F -> G, the pass manager currently does the following: run inliner on G, run loop passes on G, run inliner on F, run loop passes on F. Presumably what is happening is this: the loop passes change the functions that G calls (but don't update the callgraph). Now the inliner visits F and decides to inline G into F. When it does this, it presumably merges the callgraph info for G (i.e. what G calls) into that of F. But this info is wrong, so F ends up having invalid callgraph info which at some point causes trouble. I think what should happen is: if a SCC pass (eg: inline) is followed by function passes that preserve the callgraph, then it should schedule them together like above. However if the SCC pass is followed by a function pass that does not preserve the callgraph then it should be scheduled entirely after the SCC pass. For example, imagine -inline -fpass -loop-unswitch, where fpass is a function pass that preserves the callgraph. Then the pass manager should do: run -inline on G run -fpass on G run -inline on F run -fpass on F run -loop-unswitch on G run -loop-unswitch on F. Just my opinion of course. Ciao, Duncan.> So are loop passed *required* to preserved the call graph, in the same > way that CallGraphSCC passes are? > > Or should the pass manager take care of rebuilding the call graph > before calling the inliner on an SCC whose functions have been > changed? I don't see any evidence of this happening. > > > I've attached the full output from -debug-pass=Executions > -debug-only=inline. You can see that the loop pass manager modifies > function readClause(), and then the inliner decides to inline > readClause() into parse_DIMACS_main(), but I don't think the call > graph is being rebuilt in between those two points. > > Any ideas? > > Thanks, > Jay. >
> given the callgraph F -> G, the pass manager currently does the following: > run inliner on G, run loop passes on G, run inliner on F, run loop > passes on F. Presumably what is happening is this: the loop passes change > the functions that G calls (but don't update the callgraph). Now the > inliner visits F and decides to inline G into F. When it does this, it > presumably merges the callgraph info for G (i.e. what G calls) into that of > F. But this info is wrong, so F ends up having invalid callgraph info which > at some point causes trouble.Yes, exactly!> I think what should happen is: if a SCC pass (eg: inline) is followed > by function passes that preserve the callgraph, then it should schedule > them together like above. However if the SCC pass is followed by a > function pass that does not preserve the callgraph then it should be > scheduled entirely after the SCC pass.Sounds good, but it's a bit outside my area of expertise. I think it would be nice to have a call graph verifier, that checks that the call graph is complete and correct whenever the pass manager thinks it ought to be. Maybe it could be part of -verify - I'm not sure how these things work. Thanks, Jay.
On Feb 13, 2009, at 5:39 AM, Duncan Sands wrote:> Hi, > >> I'm looking at bug 3367. >> >> If I run: >> >> $ opt b.bc -inline -loop-rotate -loop-unswitch -debug-pass=Executions >> >> ... it eventually crashes in the inliner, because the call graph >> isn't >> up to date. (NB if you want to reproduce this you'll have to apply my >> patch from bug 3367 first.) >> >> The reason the call graph isn't up to date is that -loop-unswitch has >> changed a function and not updated the call graph. But that seems OK, >> because -loop-unswitch's getAnalysisUsage() method doesn't claim to >> preserve the call graph. > > given the callgraph F -> G, the pass manager currently does the > following: > run inliner on G, run loop passes on G, run inliner on F, run loop > passes on F. Presumably what is happening is this: the loop passes > change > the functions that G calls (but don't update the callgraph). Now the > inliner visits F and decides to inline G into F. When it does this, > it > presumably merges the callgraph info for G (i.e. what G calls) into > that of > F. But this info is wrong, so F ends up having invalid callgraph > info which > at some point causes trouble. > > I think what should happen is: if a SCC pass (eg: inline) is followed > by function passes that preserve the callgraph, then it should > schedule > them together like above. However if the SCC pass is followed by a > function pass that does not preserve the callgraph then it should be > scheduled entirely after the SCC pass. > > For example, imagine -inline -fpass -loop-unswitch, where fpass is a > function pass that preserves the callgraph. Then the pass manager > should do: > > run -inline on G > run -fpass on G > run -inline on F > run -fpass on F > run -loop-unswitch on G > run -loop-unswitch on F.This will defeat the goal of applying loop transformations before inlining leaf functions. Note, Loop transformations are not aware of call graph. They do not claim to preserve call graph. However, loop passes are run by a loop pass manager (LPPassManager) which is itself a function pass. The pass manager is not doing the right thing here because LPPassManager is incorrectly claiming to preserve call graph. The right approach is to teach LPPassManager to really preserve call graph. - Devang> > > Just my opinion of course. > > Ciao, > > Duncan. >