The following are my notes on PassManager V2. Note that the sum effect of these improvements is basically a complete rewrite of the pass manager. 1. There should be an explicit ModulePass class. The "Pass" class should be abstract. 2. The pass manager should be extended to support callgraph SCC passes and Loop passes. The structural hierarchy of passes should be: ModulePass CallGraphSCCPass FunctionPass LoopPass BasicBlockPass 3. Instead of the structural hierarchy being reflected directly in the C++ class hierarchy, the various Pass subclasses should be derived like this: Pass ModulePass CallGraphSCCPass FunctionPass LoopPass BasicBlockPass 4. The current implementation of the PassManager in PassManagerT.h is really ugly and should be rewritten. 5. There needs to be a way to indicate that a pass needs to extend the lifetime of a pass it uses. For example, the alias analyses all chain to simpler implementation of alias analysis. For this reason, the simpler alias analyses should not be destroyed until the more complex ones are. 6. Implement support for ModulePasses that require FunctionPasses.
With the above in place, we should also be able to have a "MTModulePass" class, used for implementing thread-aware module passes. It should have the following interface: 1. MTModulePass derives from ModulePass 2. The "run" method should (on a thread enabled platform) spawn some number of threads (probably equal to the number of processors), each of which invoke the "runThread" abstract method. 3. Thread aware classes thus implement the runThread method, and use synchronization primitives to avoid having the threads step on each other's toes. This is what makes the pass "thread aware". Note that function passes are already implicitly threaded, multiple function passes can be run in parallel on different functions at the same time.
Note that for any of the multithreading improvements to happen, the LLVM VMCore needs to have locks put into certain places. For example, updating use_list's must be atomic, because multiple functions can add/remove uses to global objects. There needs to be a clear separation between what a thread (and implicitly a function pass) is allowed to do to global objects, and what they are not. In order to be useful, these rules must be extremely simple.
*** Bug 252 has been marked as a duplicate of this bug. ***
Changing all of these bugs who do not have people looking at them to be assigned to "unassignedbugs", indicating that if someone is feeling ambitious, they can take ownership of the bug. If I stole your bug, and you still want it, feel free to take ownership back. -Chris
Another serious problem with the current pass manager: it implicitly assumes that all FunctionPass's preserve all "ModulePass"'s. This is a big problem if your module pass is something like an alias analysis, which is very easy to invalidate. Consider three passes A, B, C, where A is a analysis ModulePass and B/C are FunctionPass's. Currently the pass manager batches these up like this (pipelining B and C together to be run on each function): A B C Causing it to run ABCBCBCBC. Instead it should batch them like this: A B . C Causing it to run ABBBBCCCC. -Chris
> 1. There should be an explicit ModulePass class. The "Pass" class should > be abstract. This has now been implemented. -Chris
Comment #5 doesn't make sense. This is what I was trying to get at: Another serious problem with the current pass manager: it implicitly assumes that all FunctionPass's preserve all "ModulePass"'s. This is a big problem if your module pass is something like an alias analysis, which is very easy to invalidate. Consider three passes A, B, C, where A is an analysis ModulePass and B/C are FunctionPass's. Currently the pass manager batches these up like this (pipelining B and C together to be run on each function): A B C Causing it to run ABCBCBCBC. If B invalidates A, the pass manager doesn't know this (it assumes that functionpasses always preserve module passes), C will use the invalidated version of A. Instead it should batch them like this: . B A C Causing it to run BBBBACCCC. Note that the pass manager currently generates the ordering above regardless of whether the passes are added as "ABC" "BAC" or "BC" where C requires A. -Chris
Would it be too complex to have each pass declare what kinds of things they invalidate and have the PassManager find the optimal execution order based on that information? That way the PassManager doesn't have to make assumptions. It just looks at each pass and orders them according to the kinds of things they invalidate. I haven't thought much about this, just asking a question. Seems it could lead to conflicting or cyclical dependencies.
The pass manager has that info. It 'making assumptions' is a bug. -Chris
some thoughts: http://lists.cs.uiuc.edu/pipermail/llvmdev/2006-January/005137.html
>> 4. The current implementation of the PassManager in PassManagerT.h is really >> ugly and should be rewritten. Done!
>>. Instead of the structural hierarchy being reflected directly in >> the C++ class hierarchy, the various Pass subclasses should be >> derived like this: >> >> Pass >> ModulePass >> CallGraphSCCPass >> FunctionPass >> LoopPass >> BasicBlockPass Done!
Is this done? If not, can someone summarize what is left to do? It is hard to reconstruct the remaining work from all the comment entries. Thanks.
Item #6 is not yet done.
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20070416/047854.html http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20070416/047859.html implements item #6.
Anything left? :)
item #5 ?
Isn't #5 "transitively requiring passes"?
it is.