Hi Chris, One remaining question here is, if the GHC team tries some of these alternative schemes and finds them unsatisfactory what is the LLVM communities feeling in regards to extending LLVM IR to support directly implementing TNTC? How do you envision this would look at the IR level, how much work do you think it would be and most importantly do you feel LLVM would be willing to accept patches for it? We simply post process the assembly right now to get the desired code and it works very well but it means we can't use the integrated assembler which annoys me. Cheers, David. On 14 February 2012 02:59, Chris Lattner <clattner at apple.com> wrote:> On Feb 13, 2012, at 6:49 AM, Sergiu Ivanov wrote: >> On behalf of GHC hackers, I would like to discuss the possibility of >> having a proper implementation of the tables-next-to-code optimisation >> in LLVM. > > It would be great to have this. However, the design will be tricky. Is there anything that spells out how the TNTC optimization works at the actual machine instruction level? It seems that there should be a blog post somewhere that shows the code with and without the optimization, but I can't find it offhand. > >> This, obviously, requires certain >> ordering of data and text in the object code. Since LLVM does not >> make it possible to explicitly control the placement of data and code, >> the necessary ordering is currently achieved by injecting GNU >> Assembler subsections on platforms supported by GNU Assembler. Mac >> assembler, however, does not support this feature, so the resulting >> object code is post-processed directly. > > It's interesting that you bring this up. It turns out that on the mac toolchain (unless you disable subsectionsviasymbol, a gross hack) does not give you the ability to control the ordering of blobs of code separated by global labels (aka 'atoms' in the linker's terminology). This is important because it enables link-time dead code elimination, profile based code reordering etc. My understanding is that ELF toolchains don't have something like this, but it would be unfortunate if TNTC fundamentally prevents something like this from working. > > Beyond this, the proposed model has some other issues: code ordering only makes sense within a linker section, but modeling "the table" and "the code" as two different LLVM values (a global value and a function) would mean that the optimizer will be tempted to put them into different sections, do dead code elimination, etc. > >> He proposes adding a "placebefore" >> attribute to global variables (or, similarly, a "placeafter" attribute >> for functions). The corresponding example is: > > This is a non-starter for a few reasons, but that doesn't mean that there aren't other reasonable options. I'd really like to see the codegen that you guys are after to try to help come up with another suggestion that isn't a complete one-off hack for GHC. :) > > One random question: have you considered placing the table *inside* of the function? If the prologue for the closure was effectively: > > Closure: > jmp .LAfterTable > .word ... > .word ... > .LAfterTable: > push $rbp > ... > > then you can avoid a lot of problems. I realize that this is not going to be absolutely as fast as your current TNTC implementation, but processors are *really really* good at predicting unconditional branches, so the cost is probably minimal, and it is likely to be much much faster than not having TNTC at all. > > Getting even this to work will not be fully straight-forward, but again I'd like to understand more of what you're looking for from codegen to understand what the constraints are. > > -Chris > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
On Mar 13, 2012, at 4:36 PM, David Terei wrote:> Hi Chris, > > One remaining question here is, if the GHC team tries some of these > alternative schemes and finds them unsatisfactory what is the LLVM > communities feeling in regards to extending LLVM IR to support > directly implementing TNTC?I'm strongly in favor of getting proper support for TNTC, because your workarounds (while very pragmatic!) give me the shivers :). I'd much rather have a proper solution that works well with the rest of the llvm toolchain. That said, the design and implementation needs to fit in well with the rest of llvm. I'm not willing to add a crazy completely-special purpose bolt-on extension just to support this, which means that we need to find a way to design it that makes sense in the larger context of llvm.> How do you envision this would look at the > IR level, how much work do you think it would be and most importantly > do you feel LLVM would be willing to accept patches for it?I really like the idea of adding this as an inline asm blob at the start of a function, and biasing the actual address of the closure based on the size of the table. I'm not 100% confident that it will work (not being very familiar with TNTC) but it seems quite plausible and the impact on LLVM would be quite reasonable (some new calling convention work?) -Chris
Chris said:> I really like the idea of adding this as an inline asm blob at the start of a function, and biasing the actual address of the closure based on the size of the table. I'm not 100% confident that it will work (not being very familiar with TNTC) but it seems quite plausible and the impact on LLVM would be quite reasonable (some new calling convention work?)While reading this I had the idea that the LLVM code generator could watch out for the specific combination of inline asm and calling convention and strip off the fat. This way the code increase could be dealt with. OTOH the inline asm would still need to be target specific, which is very ugly. What about a new intrinsic which holds a reference to the global and creates the right assembly in the backend? Since the reference to the global (which is the table) would not be used otherwise, the linker could drop it, thus no code increase and no redundant global. Does this make sense? Cheers, Gabor
On 15 March 2012 01:58, Chris Lattner <clattner at apple.com> wrote:> > On Mar 13, 2012, at 4:36 PM, David Terei wrote: > >> Hi Chris, >> >> One remaining question here is, if the GHC team tries some of these >> alternative schemes and finds them unsatisfactory what is the LLVM >> communities feeling in regards to extending LLVM IR to support >> directly implementing TNTC? > > I'm strongly in favor of getting proper support for TNTC, because your workarounds (while very pragmatic!) give me the shivers :). I'd much rather have a proper solution that works well with the rest of the llvm toolchain. > > That said, the design and implementation needs to fit in well with the rest of llvm. I'm not willing to add a crazy completely-special purpose bolt-on extension just to support this, which means that we need to find a way to design it that makes sense in the larger context of llvm.OK great! I have no idea when we on the GHC side (me) will get time to tackle this so don't hold your breath. Good to know where you guys stand though. We began this conversation as a GSoC student is interested in tackling it so we may progress down that path.> >> How do you envision this would look at the >> IR level, how much work do you think it would be and most importantly >> do you feel LLVM would be willing to accept patches for it? > > I really like the idea of adding this as an inline asm blob at the start of a function, and biasing the actual address of the closure based on the size of the table. I'm not 100% confident that it will work (not being very familiar with TNTC) but it seems quite plausible and the impact on LLVM would be quite reasonable (some new calling convention work?) > > -ChrisI personally would prefer something like Gabor suggests that is platform agnostic but am not fussed on the issue, whatever works (and isn't a hack) is my goal. Cheers, David