Greetings folks!<div><br></div><div>In working on a new optimization pass (splitting cold regions into separate functions based on branch probabilities) I've run into some limitations of the current pass manager infrastructure. After chatting about this with Nick, it seems that there are some pretty systematic weaknesses of the current design and implementation (but not with the fundamental concepts or behavior).</div>
<div><br></div><div>Current issues:</div><div><br></div><div>- Arbitrary limitations on how passes can depend on an analysis: module passes have a gross hack to depend on function pass analyses, and CGSCC passes are just out of luck.</div>
<div><br></div><div>- Poor caching of analysis runs across pass manager boundaries. Consider the N iterations on the SCC and the function passes run by the CGSCC pass manager. Even if every CG and function pass in the manager preserves a function pass analysis X, that pass will be re-run on each iteration of the SCC because it is scheduled in the function pass manager, not the CG pass manager. If we solve the previous item, that will make this one a *serious* problem suddenly.</div>
<div><br></div><div>- The structure of the pass management tree is very non-obvious from code. The pass manager builder simply adds a linear sequence of passes that happens to build the appropriate stacks of passes at the appropriate times.</div>
<div><br></div><div>- Currently the interfaces and implementation of passes and pass managers is overly complex: multiple inheritance, lots of virtual dispatch etc. Doesn't use the canonical LLVM 'isa' and 'dyn_cast' techniques.</div>
<div><br></div><div><br></div><div>I'd like to fix these issues and build a new pass manager implementation designed around the following core concepts:</div><div><br></div><div>- We should have clear tracking and statistics for pass run count, analysis invalidation, etc.</div>
<div><br></div><div>- Analysis scheduling and re-use is fundamentally a *caching* and dependency problem, and we should structure it as such.</div><div>  - Non-preserving passes should invalidate the cache</div><div>  - The cache should be capable of spanning any particular pass management boundary when needed.</div>
<div>  - We should be able to trade memory for speed and cache more analyses when beneficial.</div><div>  - The infrastructure should at least *support* a lazier approach to analyses, so that we can do more to avoid computing them at all.</div>
<div><br></div><div>- PassManagerBuilder should use an explicit nested syntax for building up the structure of the passes so it is clear when a pass is part of a CGSCC pass manager, or when it is a normal function pass.</div>
<div><br></div><div>- Clear hierarchy of "Pass" interfaces. Every pass should be capable of acting-as-if it is a higher level pass. That is, a function pass should be capable of acting-as-if it is a module pass just by running over all functions in the module. That doesn't mean this should regularly be *used*, but it makes conceptual reasoning about passes and testing of passes much more clear.</div>
<div><br></div><div>- PassManagers should *be* passes, and serve as pass-aggregation strategies and analysis caching strategies. Where a function pass *can* act as a module pass, you usually instead want a function pass manager, which will collect a sequence of function passes and run all of them over each function all at once. This aggregation strategy increases locality. Similarly, a CGSCC pass manager aggregates the pass runs over an SCC of the call graph. Each pass manager could influence the caching strategy as well, for example the CGSCC pass manager might cache a function analysis pass over an entire SCC, rather than just over one function.</div>
<div><br></div><div>- Single, LLVM-style inheritance model for the whole thing.</div><div><br></div><div>- Users should be able to add new pass managers, and compose them cleanly with the LLVM-provided pass managers. Currently, many implementation details are burried that makes this hard.</div>
<div><br></div><div>- What else did I miss?</div><div><br></div><div><br></div><div>Things that are totally out of scope: pass registration, the current pass order and structure, the fundamental interface of mapping from a pass to an analysis, etc. This is really about pass management and scheduling.</div>
<div><br></div><div><br></div><div>If folks generally like where this is going, I'll get to work writing up initial code. The first thing I would do is provide an example collection of interfaces for the passes and pass managers to make sure we're all on the same page. By then I should have a decent idea about the best strategy for cutting this into the actual codebase.</div>
<div><br></div><div><br></div><div><br></div>