Hi All, I am planning to re-implement PassManager in llvm 2.0. The goal is to address http://nondot.org/sabre/LLVMNotes/Inliner-PassManager.txt and http://nondot.org/sabre/LLVMNotes/LoopOptimizerNotes.txt and other crazy ideas Chris has. Current implementation of PassManager is very complex. Initially I attempted to update it to address above notes but realized that redoing PassManager in simple way makes more sense, and Chris agreed. Instead of replacing current PassManager with new PassManager in one big scoop I'm going to follow these steps: 1) Rename existing Managers using _X suffix. 2) Introduce new PassManager skeleton 3) Add functionality in new Pass Manager 4) Start Using new Pass Manager 5) Remove existing Pass Manager 6) Implement LoopPassManager 7) Update existing Loop transformations to conform LoopPassManager - Devang
Hi Devang, On Tue, 2006-11-07 at 09:32 -0800, Devang Patel wrote:> Hi All, > > I am planning to re-implement PassManager in llvm 2.0. The goal is to > address > > http://nondot.org/sabre/LLVMNotes/Inliner-PassManager.txt and > http://nondot.org/sabre/LLVMNotes/LoopOptimizerNotes.txt > > and other crazy ideas Chris has. Current implementation of PassManager > is very complex. Initially I attempted to update it to address above > notes but realized that redoing PassManager in simple way makes more > sense, and Chris agreed. Instead of replacing current PassManager with > new PassManager in one big scoop I'm going to follow these steps: > > 1) Rename existing Managers using _X suffix. > 2) Introduce new PassManager skeleton > 3) Add functionality in new Pass Manager > 4) Start Using new Pass Manager > 5) Remove existing Pass Manager > 6) Implement LoopPassManager > 7) Update existing Loop transformations to conform LoopPassManagerNice! What a welcome addition. It would be nice to have a PassManager that I can actually understand :) Reid.
Chris and Devang, Before you implement the LoopPassManager class, I'd like to discuss this a little bit. I have a suggestion and a question; we can discuss this now or later, as you wish: 1. The LoopPassManager might become much simpler if the more complex loop passes are given control over how they iterate over the loops, rather always rely on the manager to enumerate the loops in some fixed order. Then the pass could be responsible for making sure that it handles issues like loops that are deleted during the pass. For example, some algorithms make internal decisions about which loops to handle together and also what order to visit them. For example, the LoopFusion class may need to inspect loop headers to decide which subsets of loops to fuse and then fuse them as it goes. I think you could do this just by adding an iterator method somewhere that enumerates sets of loops (i.e,. returns a vector of Loop objects). The bottom-up iterator could just be a default choice. 2. The question is how you plan to handle unimodular transformations. I think it's a very nice abstraction and a number of loop transforms should be implemented using that rather than more ad hoc code, e.g., interchange, reversal, skewing. But that requires implementing support for unimodular transforms before those passes are implemented. --Vikram http://www.cs.uiuc.edu/~vadve http://llvm.cs.uiuc.edu/ On Nov 7, 2006, at 11:32 AM, Devang Patel wrote:> Hi All, > > I am planning to re-implement PassManager in llvm 2.0. The goal is to > address > > http://nondot.org/sabre/LLVMNotes/Inliner-PassManager.txt and > http://nondot.org/sabre/LLVMNotes/LoopOptimizerNotes.txt > > and other crazy ideas Chris has. Current implementation of PassManager > is very complex. Initially I attempted to update it to address above > notes but realized that redoing PassManager in simple way makes more > sense, and Chris agreed. Instead of replacing current PassManager with > new PassManager in one big scoop I'm going to follow these steps: > > 1) Rename existing Managers using _X suffix. > 2) Introduce new PassManager skeleton > 3) Add functionality in new Pass Manager > 4) Start Using new Pass Manager > 5) Remove existing Pass Manager > 6) Implement LoopPassManager > 7) Update existing Loop transformations to conform LoopPassManager > > - > Devang > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Hi Vikram, On Nov 7, 2006, at 10:19 AM, Vikram Adve wrote:> Chris and Devang, > > Before you implement the LoopPassManager class, I'd like to discuss > this a little bit. I have a suggestion and a question; we can > discuss this now or later, as you wish: > > 1. The LoopPassManager might become much simpler if the more complex > loop passes are given control over how they iterate over the loops, > rather always rely on the manager to enumerate the loops in some > fixed order. Then the pass could be responsible for making sure that > it handles issues like loops that are deleted during the pass.LoopPassManager will manage the LoopInfo. It will maintain loop priority queue and expose APIs to add/remove loops that transformations can use.> For > example, some algorithms make internal decisions about which loops to > handle together and also what order to visit them. For example, the > LoopFusion class may need to inspect loop headers to decide which > subsets of loops to fuse and then fuse them as it goes.LoopPassManager will expose two virtual methods. 1) runOnLoop(Loop &L, LoopPassManger &LPM) Loop transformation can override to process this particular loop. 2) runOnFunctionBody(Function &F, Loop&L, LoopPassManager &LPM) LoopFusion and others can override this to to analyze and process multiple loops.> > I think you could do this just by adding an iterator method somewhere > that enumerates sets of loops (i.e,. returns a vector of Loop > objects). The bottom-up iterator could just be a default choice. > > 2. The question is how you plan to handle unimodular > transformations. I think it's a very nice abstraction and a number > of loop transforms should be implemented using that rather than more > ad hoc code, e.g., interchange, reversal, skewing. But that requires > implementing support for unimodular transforms before those passes > are implemented.I have not yet spent enough time to think about unimodular transformation framework implementation. - Devang
On Tue, 7 Nov 2006, Vikram Adve wrote:> 1. The LoopPassManager might become much simpler if the more complex > loop passes are given control over how they iterate over the loops, > rather always rely on the manager to enumerate the loops in some > fixed order. Then the pass could be responsible for making sure that > it handles issues like loops that are deleted during the pass. For > example, some algorithms make internal decisions about which loops to > handle together and also what order to visit them. For example, the > LoopFusion class may need to inspect loop headers to decide which > subsets of loops to fuse and then fuse them as it goes.I think I see the issue here. The point of the pass manager (in general) is for passes to *give up control* over iteration order in order for obtain something else. For example, function passes give up control over which order functions are processed in. This allows pipelining of a function through multiple function passes before the next function is processed. If each functionpass could define its own iteration order, this wouldn't work. Note that no generality is lost here: passes that don't fit the FunctionPass mold can be made into ModulePasses. The LoopPassManager is the same thing. The idea is that the LPM provides structured iteration among loop pass classes. I believe that most loop transformations will fit into the framework, and will thus enjoy the benefits of it. Those that don't can alway be FunctionPasses. -Chris -- http://nondot.org/sabre/ http://llvm.org/