David Greene wrote:> On Saturday 01 May 2010 08:34:50 Josef Eisl wrote: >> Hello, >> >> I want learn more about register allocation and do some analysis for a >> current research project. After reading some papers (eg. Chaitin, >> Briggs) I think its time to get my hands dirty :). > > Welcome! > >> First I plan to (re)implement some of the classic approaches to get >> familiar with the framework. > > Before doing that, can you describe your research a bit? A number of > people (include me!) have done graph-coloring style register allocators > for LLVM/x86 and not found much benefit over the existing "linear scan" > scheme (in quotes because it's not actually linear scan anymore :)).Maybe 'research' was not the appropriate term :). I am currently working on an assignment for the undergraduate course 'algorithms and data-structures' at our university and I want our attendee to see some real world examples. The topic of the assignment is graph coloring and I thought I can use LLVM to throw out some example input data. Maybe I'll port some of the submissions to LLVM and see what happens... Besides that, I am generally interested in all topics around compilation techniques/code generation especially using LLVM. I've been working on a back-end and recently implemented a tblgen pass to generate some hardware description files out of .td files. I am not planning to develop a highly efficient regalloc to compete with 'linear scan' ;). Just digging a little bit deeper into the topic.> > It might be better to use your time to investigate other algorithms. > If all you want to do right now is get familiar with the framework, there > are simpler algorithms than graph coloring. > >> At the beginning the following questions came up: >> >> - Is there some documentation about register allocation in LLVM? > > http://llvm.org/docs/CodeGenerator.html > http://llvm.org/docs/CodeGenerator.html#regalloc > > These are essential to read. A lot of details are missing which requires > one to just get down into the code and start hacking but this document helps > with understanding the broad picture.Thanks, I read these some time ago when I was starting the back-end implementation. I'll see if there are some new infos in it.> >> - As far as I understand it, register allocators are implemented as >> MachineFunctionPasses. Does a MachineFunction object contain all >> information needed for a (classic) allocator? > > It has the instructions, operands and dependencies among them. There's > a LiveInvervalAnalysis pass which you'll probably also need. That should > be enough to get going.I was able to set up my own allocator that uses LiveIntervals and it is currently printing out something that might become a conflict graph ;). Would be nice if there was some documentation about how to get all these objects out of the MachineFunction &MF parameter. Maybe I'll summarize how I did it and write something up...> >> - Is there already a pass that prints interference graph (Chaitin et al. >> 1981) or something similar like opt -view-cfg prints a CFG? If not, is >> it even possible with the current LLVM infrastructure? > > There's not one in trunk. When I did this I used Boost.Graph as the > representation and relied on its ability to dump GraphViz files for > visualization. You can also specialize LLVM's GraphTraits for your > particular graph representation and get much the same thing. You'll > need to add your own command-line options to display pretty pictures, > of course.I didn't know Boost.Graph. Seems pretty cool, thank for the hint. There is another questions that came up: Can I somehow get the PassManager to execute my MachineFunctionPass (loaded with llc -load) before the RegAlloc? As I am currently only printing out some LiveInterval infos so I don't need/want to implement a complete allocator. But if there is no pass that depends on my analysis the pass manager doesn't schedule my pass at all. I understand that that makes sense but it would be nice to 'force' the pass manager the execute my stuff before the allocator without changing the framework and only using llc -load (and maybe some custom cmd switches). Something similar is possible with opt but I can't figure it out with llc.> >> - Is there an LLVM register allocator that uses graph coloring or >> something similar? > > Not in trunk. Here's a message I looked at when I did mine: > > http://www.mail-archive.com/llvm-commits at cs.uiuc.edu/msg10962.html > > It's pretty stale at this point. It won't apply to trunk. Just > use it as a guide to get started.Hm, first class definition 'Interference graph node'. This looks very promising :).> >> - Which LLVM allocator would you recommend to look into to get the basic >> ideas how to use the framework? > > LinearScan is the only one widely used, AFAIK. There are some simpler > allocators as well (local, simple). PBQP is cool but I don't know much > about it. > > -Dave > >Many thanks your reply. I Really appreciate your help. Josef
On Tuesday 04 May 2010 05:45:36 Josef Eisl wrote:> >> - As far as I understand it, register allocators are implemented as > >> MachineFunctionPasses. Does a MachineFunction object contain all > >> information needed for a (classic) allocator? > > > > It has the instructions, operands and dependencies among them. There's > > a LiveInvervalAnalysis pass which you'll probably also need. That should > > be enough to get going. > > I was able to set up my own allocator that uses LiveIntervals and it is > currently printing out something that might become a conflict graph ;). > Would be nice if there was some documentation about how to get all these > objects out of the MachineFunction &MF parameter. > Maybe I'll summarize how I did it and write something up...Which objects? Iterating over blocks and instructions from MachineFunction is pretty straightforward and getAnalysis<> is what you want for LiveIntervals. I presume you know all this since you have LiveIntervals dumping something. What else do you need to get at?> I didn't know Boost.Graph. Seems pretty cool, thank for the hint.It's a bit unwieldy at times. The interface is much more complex than it needs to be, but people are working on that. Slowly. :(> There is another questions that came up: Can I somehow get the > PassManager to execute my MachineFunctionPass (loaded with llc -load) > before the RegAlloc? As I am currently only printing out some > LiveInterval infos so I don't need/want to implement a complete > allocator. But if there is no pass that depends on my analysis the pass > manager doesn't schedule my pass at all. I understand that that makes > sense but it would be nice to 'force' the pass manager the execute my > stuff before the allocator without changing the framework and only using > llc -load (and maybe some custom cmd switches). Something similar is > possible with opt but I can't figure it out with llc.Passes in llc are hard-coded in LLVMTargetMachine.cpp. Does your pass actually do register allocation, or will it? If so, you want to use the RegisterRegAlloc object. Here is how linear scan uses it: static RegisterRegAlloc linearscanRegAlloc("linearscan", "linear scan register allocator", createLinearScanRegisterAllocator); Then createRegisterAllocator in CodeGen/Passes.cpp will pick up your allocator and list it as an option under -regalloc=<allocator>. If you pass is just doing some analysis and dumps you can either add a invocation of it to LLVMTargetMachine.cpp or make some other pass dependent on it. -Dave
David Greene wrote:> On Tuesday 04 May 2010 05:45:36 Josef Eisl wrote: > > >>>> - As far as I understand it, register allocators are implemented as >>>> MachineFunctionPasses. Does a MachineFunction object contain all >>>> information needed for a (classic) allocator? >>> It has the instructions, operands and dependencies among them. There's >>> a LiveInvervalAnalysis pass which you'll probably also need. That should >>> be enough to get going. >> I was able to set up my own allocator that uses LiveIntervals and it is >> currently printing out something that might become a conflict graph ;). >> Would be nice if there was some documentation about how to get all these >> objects out of the MachineFunction &MF parameter. >> Maybe I'll summarize how I did it and write something up... > > Which objects? Iterating over blocks and instructions from MachineFunction > is pretty straightforward and getAnalysis<> is what you want for > LiveIntervals. I presume you know all this since you have LiveIntervals > dumping something.After I've taken a second look at my code, I must admit, it is really straight forward. Don't know why I didn't got it the first time.> > What else do you need to get at? > >> I didn't know Boost.Graph. Seems pretty cool, thank for the hint. > > It's a bit unwieldy at times. The interface is much more complex > than it needs to be, but people are working on that. Slowly. :( > >> There is another questions that came up: Can I somehow get the >> PassManager to execute my MachineFunctionPass (loaded with llc -load) >> before the RegAlloc? As I am currently only printing out some >> LiveInterval infos so I don't need/want to implement a complete >> allocator. But if there is no pass that depends on my analysis the pass >> manager doesn't schedule my pass at all. I understand that that makes >> sense but it would be nice to 'force' the pass manager the execute my >> stuff before the allocator without changing the framework and only using >> llc -load (and maybe some custom cmd switches). Something similar is >> possible with opt but I can't figure it out with llc. > > Passes in llc are hard-coded in LLVMTargetMachine.cpp. Does your > pass actually do register allocation, or will it? If so, you want > to use the RegisterRegAlloc object. Here is how linear scan uses it: > > static RegisterRegAlloc > linearscanRegAlloc("linearscan", "linear scan register allocator", > createLinearScanRegisterAllocator); > > Then createRegisterAllocator in CodeGen/Passes.cpp will pick up > your allocator and list it as an option under -regalloc=<allocator>.Yes, I've done so. After my pass is finished with the 'dumping' it calls runOnMachineFunction from another implemented RegAlloc until I implement my own.> > If you pass is just doing some analysis and dumps you can either > add a invocation of it to LLVMTargetMachine.cpp or make some > other pass dependent on it.Ok, thats what I expected. Would be nice to hook in a pass without changing llc but I guess it wouldn't make any sense for 'real' passes. Thanks again for your help! Josef
Abhishek Rhisheekesan
2012-Apr-21 17:06 UTC
[LLVMdev] Register Allocation: Interference graph
I am working on a similar project on register allocation using graph coloring and as part of it, I need to generate the register interference graph. The interference graph will be an input to my analysis program in another programming language, so a generic graph representation is required (nodes and edges). I see that you have come up with some conflict graph output and I assume this is the register interference graph. Can you please post your pass code?
Abhishek Rhisheekesan
2012-Apr-21 17:14 UTC
[LLVMdev] Re gister Allocation: Interference graph
I am working on a similar project on register allocation using graph coloring and as part of it, I need to generate the register interference graph. The interference graph will be an input to my analysis program in another programming language, so a generic graph representation is required (nodes and edges). I see that you have come up with some conflict graph output and I assume this is the register interference graph. Can you please post your pass code? Josef Eisl wrote:> > David Greene wrote: >> On Saturday 01 May 2010 08:34:50 Josef Eisl wrote: >>> Hello, >>> >>> I want learn more about register allocation and do some analysis for a >>> current research project. After reading some papers (eg. Chaitin, >>> Briggs) I think its time to get my hands dirty :). >> >> Welcome! >> >>> First I plan to (re)implement some of the classic approaches to get >>> familiar with the framework. >> >> Before doing that, can you describe your research a bit? A number of >> people (include me!) have done graph-coloring style register allocators >> for LLVM/x86 and not found much benefit over the existing "linear scan" >> scheme (in quotes because it's not actually linear scan anymore :)). > > Maybe 'research' was not the appropriate term :). I am currently working > on an assignment for the undergraduate course 'algorithms and > data-structures' at our university and I want our attendee to see some > real world examples. The topic of the assignment is graph coloring and I > thought I can use LLVM to throw out some example input data. Maybe I'll > port some of the submissions to LLVM and see what happens... > > Besides that, I am generally interested in all topics around compilation > techniques/code generation especially using LLVM. I've been working on a > back-end and recently implemented a tblgen pass to generate some > hardware description files out of .td files. > > I am not planning to develop a highly efficient regalloc to compete with > 'linear scan' ;). Just digging a little bit deeper into the topic. > >> >> It might be better to use your time to investigate other algorithms. >> If all you want to do right now is get familiar with the framework, there >> are simpler algorithms than graph coloring. >> >>> At the beginning the following questions came up: >>> >>> - Is there some documentation about register allocation in LLVM? >> >> http://llvm.org/docs/CodeGenerator.html >> http://llvm.org/docs/CodeGenerator.html#regalloc >> >> These are essential to read. A lot of details are missing which requires >> one to just get down into the code and start hacking but this document >> helps >> with understanding the broad picture. > > Thanks, I read these some time ago when I was starting the back-end > implementation. I'll see if there are some new infos in it. > >> >>> - As far as I understand it, register allocators are implemented as >>> MachineFunctionPasses. Does a MachineFunction object contain all >>> information needed for a (classic) allocator? >> >> It has the instructions, operands and dependencies among them. There's >> a LiveInvervalAnalysis pass which you'll probably also need. That should >> be enough to get going. > > I was able to set up my own allocator that uses LiveIntervals and it is > currently printing out something that might become a conflict graph ;). > Would be nice if there was some documentation about how to get all these > objects out of the MachineFunction &MF parameter. > Maybe I'll summarize how I did it and write something up... > >> >>> - Is there already a pass that prints interference graph (Chaitin et al. >>> 1981) or something similar like opt -view-cfg prints a CFG? If not, is >>> it even possible with the current LLVM infrastructure? >> >> There's not one in trunk. When I did this I used Boost.Graph as the >> representation and relied on its ability to dump GraphViz files for >> visualization. You can also specialize LLVM's GraphTraits for your >> particular graph representation and get much the same thing. You'll >> need to add your own command-line options to display pretty pictures, >> of course. > > I didn't know Boost.Graph. Seems pretty cool, thank for the hint. > > There is another questions that came up: Can I somehow get the > PassManager to execute my MachineFunctionPass (loaded with llc -load) > before the RegAlloc? As I am currently only printing out some > LiveInterval infos so I don't need/want to implement a complete > allocator. But if there is no pass that depends on my analysis the pass > manager doesn't schedule my pass at all. I understand that that makes > sense but it would be nice to 'force' the pass manager the execute my > stuff before the allocator without changing the framework and only using > llc -load (and maybe some custom cmd switches). Something similar is > possible with opt but I can't figure it out with llc. > >> >>> - Is there an LLVM register allocator that uses graph coloring or >>> something similar? >> >> Not in trunk. Here's a message I looked at when I did mine: >> >> http://www.mail-archive.com/llvm-commits at cs.uiuc.edu/msg10962.html >> >> It's pretty stale at this point. It won't apply to trunk. Just >> use it as a guide to get started. > > Hm, first class definition 'Interference graph node'. This looks very > promising :). > >> >>> - Which LLVM allocator would you recommend to look into to get the basic >>> ideas how to use the framework? >> >> LinearScan is the only one widely used, AFAIK. There are some simpler >> allocators as well (local, simple). PBQP is cool but I don't know much >> about it. >> >> -Dave >> >> > > Many thanks your reply. I Really appreciate your help. > > Josef > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > >-- View this message in context: http://old.nabble.com/Register-Allocation%3A-Interference-graph-tp28420851p33726089.html Sent from the LLVM - Dev mailing list archive at Nabble.com.