On Aug 14, 2007, at 4:35 AM, Gordon Henriksen wrote:> On Aug 14, 2007, at 06:24, Gordon Henriksen wrote: > >> The two major problems I had really boil down to identifying GC >> points in machine code and statically identifying live roots at >> those GC points, both problems common to many collection >> techniques. Looking at the problem from that perspective makes the >> problem much more tractable, actually… > > Chris, > > This is much more generic than what I was originally thinking, but > what do you think of providing a facility like this? > That could enable several kinds of conservative collectors.I'm not sure I follow what you mean.> The code generator would need to cooperate by: > > 1. Inserting nodes for GC points if required, recording the > corresponding original Instruction*. > 2. Recording the physical location of each llvm.gcroot'd alloca.This is somewhat implicit in the design we want. The only question is how to identify these at runtime. In theory, the code generator already knows what the gc points are and where the pointers on the stack are located. For a "cooperative" code generator, the codegen should emit tables (similar to EH tables) that describe this, and the llvm code generator callback should enumerate these.> Later, a MachineFunctionPass could walk the MachineFunction to > lower these nodes. Live roots can be identified using domination > information.These are optimizations that can be implemented in the code generator, there are many others as well. For the time being, we don't even have real dominator info in the code generator though.. -Chris
On Aug 19, 2007, at 20:43, Chris Lattner wrote:> On Aug 14, 2007, at 4:35 AM, Gordon Henriksen wrote: > >> On Aug 14, 2007, at 06:24, Gordon Henriksen wrote: >> >>> The two major problems I had really boil down to identifying GC >>> points in machine code and statically identifying live roots at >>> those GC points, both problems common to many collection >>> techniques. Looking at the problem from that perspective makes >>> the problem much more tractable, actually… >> >> Chris, >> >> This is much more generic than what I was originally thinking, but >> what do you think of providing a facility like this? That could >> enable several kinds of conservative collectors.A thinko; I meant accurate, not conservative.> I'm not sure I follow what you mean.My initial thought was more akin to getting the labels I needed and representing the frametable at the source level. That's a terrible idea. :) It makes much more sense for the code generator to cooperate with GC.>> The code generator would need to cooperate by: >> >> 1. Inserting nodes for GC points if required, recording the >> corresponding original Instruction*. >> 2. Recording the physical location of each llvm.gcroot'd alloca. > > This is somewhat implicit in the design we want. The only question > is how to identify these at runtime. In theory, the code generator > already knows what the gc points are and where the pointers on the > stack are located. For a "cooperative" code generator, the codegen > should emit tables (similar to EH tables) that describe this, and > the llvm code generator callback should enumerate these.Yes, that's what I'm working on. Currently I have: - Suppressed llvm.gcroot lowering in the LowerGC pass [may wish to remove the pass from the default pipeline entirely] - Added a GCInfo analysis - Recorded in GCInfo the stack object indices for roots Presumably, then, another pass can come along and use the analysis to emit GC tables. I'm still rummaging around the code generators trying to determine an approach to identifying GC points in machine code which enables liveness analysis. Perhaps I should punt on that for the moment in the interests of getting something dumb working (sans liveness analysis), though.>> Later, a MachineFunctionPass could walk the MachineFunction to >> lower these nodes. Live roots can be identified using domination >> information. > > These are optimizations that can be implemented in the code > generator, there are many others as well. For the time being, we > don't even have real dominator info in the code generator though..Would it be sufficient to use domination information from the LLVM representation for liveness analysis? — Gordon -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20070820/1a970e4b/attachment.html>
On Mon, 20 Aug 2007, Gordon Henriksen wrote:>> I'm not sure I follow what you mean. > > My initial thought was more akin to getting the labels I needed and > representing the frametable at the source level. That's a terrible idea. :) > It makes much more sense for the code generator to cooperate with GC.All the GC needs is information about what pointers are live in each stack trace, right? This is all details of implementation of how it extracts that. The GC should not be tied to the implementation of the code generator.>> This is somewhat implicit in the design we want. The only question is how >> to identify these at runtime. In theory, the code generator already knows >> what the gc points are and where the pointers on the stack are located. >> For a "cooperative" code generator, the codegen should emit tables >> (similar to EH tables) that describe this, and the llvm code generator >> callback should enumerate these. > > Yes, that's what I'm working on. Currently I have: > > - Suppressed llvm.gcroot lowering in the LowerGC pass [may wish to remove the > pass from the default pipeline entirely]Right.> - Added a GCInfo analysis > - Recorded in GCInfo the stack object indices for roots > > Presumably, then, another pass can come along and use the analysis to emit GC > tables.Makes sense!> I'm still rummaging around the code generators trying to determine an > approach to identifying GC points in machine code which enables liveness > analysis. Perhaps I should punt on that for the moment in the interests of > getting something dumb working (sans liveness analysis), though.Please start with something simple: we can work up optimizations once the simple stuff is really solid.>> > Later, a MachineFunctionPass could walk the MachineFunction to lower >> > these nodes. Live roots can be identified using domination information. >> >> These are optimizations that can be implemented in the code generator, >> there are many others as well. For the time being, we don't even have >> real dominator info in the code generator though.. > > Would it be sufficient to use domination information from the LLVM > representation for liveness analysis?No, because the machine code cfg can be significantly different. We really do need dom info on machine code. -Chris -- http://nondot.org/sabre/ http://llvm.org/