[llvm-dev] Design issues in LLVM IR

[Chris Lattner via llvm-dev]

Nikita Popov wrote a great block post last week: “Design issues in LLVM IR” that I just found.  It is well framed and nicely written, it seems like a good idea to discuss this on llvm-dev.  :-)

Here are my 2c for what it is worth:

a) I completely agree we should continue to invest in fixing the core of LLVM.  There are long standing issues that we should fix, and not doing so slows things down, leads to worse quality of results, etc.

b) I completely agree with his framing on canonicalization and its value.  I think that LLVM has historically taken this a bit too far (e.g. loop transformations, the old IndVar/LSR dichotomy among others) but many of those have already been walked back.

c) I completely agree we need to continue to march towards opaque pointers, I’m a fan of this work.

d) I’m less enthused about eliminating type based GEP.  The post is right that indexing computations are expensive, but that is largely due to the algorithms used, not the IR structure.  If this was the thing to fix, then we should fix other aspects of the design.  The thing that I’m particularly concerned about is array indexes: I think we need to preserve the ability to do simple dependence analysis and other array subscript indexing analyses in the middle end.  I think the sweet spot is to drop types from pointers, but keep them on GEPs.  Alternatively, finish the typeless pointer migration and then evaluate what to do with GEPs only when that completes.

e) Constant Expressions are a disaster.  In addition to the problem identified, there are also many annoying cases to deal with, eg. When constexprs exist in phi nodes, trapping constexprs, etc.  In my opinion, the fix is to eliminate them entirely, in a few steps:

    1) Introduce a new “RelocatableConstant” object which is *not* a mirror of all the IR operations in LLVM, but is instead designed to be used in global variables and allows the standard “globalpointer+offset” pattern that object files support, and we should add a new MachoRelocatableConstant class to represent the “(gv1-gv2+offset)” relocations macho supports.  The presence of this would make codegen and frontends easier to write, and get rid of all the fiddly pattern matching stuff.  I think we need to talk about whether “offset” is a byte offset, or whether it is a series of (constant integer) field indexes in a GEP like operation.  I would argue for the later to make inter procedural optimizations easier to write, but it is debatable.

    2) Move the general constant folding API off of ConstantExpr to somewhere else, it never should have been there for reasons pointed out in the blog.

    3) Eliminate ConstExpr: after #1, we don’t need a mirror of the LLVM IR in constant nodes.  Constant folding should be a failable operation and would return the primitive nodes like ConstantInt.  The asmparser / byte code parser could auto upgrade general unfolded constexprs to instructions when in a function and to [Macho]RelocatableConstant

In any case, I’d love to see progress on any of these.  I’d personally love to see the typeless pointers land because we’re in an unfortunate in-between state, and we should close off partial transitions.

-Chris

[Nicolai Hähnle via llvm-dev]

a) I completely agree we should continue to invest in fixing the core of LLVM.  There are long standing issues that we should fix, and not doing so slows things down, leads to worse quality of results, etc.

Absolutely!

 

b) I completely agree with his framing on canonicalization and its value.  I think that LLVM has historically taken this a bit too far (e.g. loop transformations, the old IndVar/LSR dichotomy among others) but many of those have already been walked back.

c) I completely agree we need to continue to march towards opaque pointers, I’m a fan of this work.

+1. Also +1 on the point that partial transitions are the worst :)

 

d) I’m less enthused about eliminating type based GEP.  The post is right that indexing computations are expensive, but that is largely due to the algorithms used, not the IR structure.  If this was the thing to fix, then we should fix other aspects of the design.  The thing that I’m particularly concerned about is array indexes: I think we need to preserve the ability to do simple dependence analysis and other array subscript indexing analyses in the middle end.  I think the sweet spot is to drop types from pointers, but keep them on GEPs.  Alternatively, finish the typeless pointer migration and then evaluate what to do with GEPs only when that completes.

Yeah. I've been thinking it would be interesting to be able to do more backend-ish work in LLVM IR, in which case the _ability_ to do raw pointer arithmetic without bitcast hell would be nice. But I think typeless pointers already give us that anyway: adding a pointer and an offset is just a GEP of i8 type.

 

e) Constant Expressions are a disaster.  In addition to the problem identified, there are also many annoying cases to deal with, eg. When constexprs exist in phi nodes, trapping constexprs, etc.  In my opinion, the fix is to eliminate them entirely, in a few steps:

    1) Introduce a new “RelocatableConstant” object which is *not* a mirror of all the IR operations in LLVM, but is instead designed to be used in global variables and allows the standard “globalpointer+offset” pattern that object files support, and we should add a new MachoRelocatableConstant class to represent the “(gv1-gv2+offset)” relocations macho supports.  The presence of this would make codegen and frontends easier to write, and get rid of all the fiddly pattern matching stuff.  I think we need to talk about whether “offset” is a byte offset, or whether it is a series of (constant integer) field indexes in a GEP like operation.  I would argue for the later to make inter procedural optimizations easier to write, but it is debatable.

    2) Move the general constant folding API off of ConstantExpr to somewhere else, it never should have been there for reasons pointed out in the blog.

    3) Eliminate ConstExpr: after #1, we don’t need a mirror of the LLVM IR in constant nodes.  Constant folding should be a failable operation and would return the primitive nodes like ConstantInt.  The asmparser / byte code parser could auto upgrade general unfolded constexprs to instructions when in a function and to [Macho]RelocatableConstant

Right. I'd like to see more of the learnings of MLIR make it into LLVM IR. It's quite unfortunate that the introduction of MLIR caused a sort of split in the community. I understand why it happened: MLIR is a radical departure that would never have made it through review as a modification of LLVM IR. However, now that MLIR exists and many of its ideas have been proven out, it may be time to go back and put (some of?) them into LLVM IR as a step towards re-unification.

There are many of those ideas to choose from. One that I'm partial to is the ability to have instructions with multiple result values. This would allow us to fix a number of low-key annoyances, like the integration of inline assembly with convergence analysis for GPU backends. Inline assembly can produce multiple results, and there's no reason why all of them should be divergent or all of them should be uniform; it could be a mix, and yet because the inline asm instruction returns a single (struct) value, we can't cleanly express this.

Cheers,

Nicolai

 

In any case, I’d love to see progress on any of these.  I’d personally love to see the typeless pointers land because we’re in an unfortunate in-between state, and we should close off partial transitions.

-Chris

_______________________________________________
LLVM Developers mailing list
llvm...@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

--

Lerne, wie die Welt wirklich ist,
aber vergiss niemals, wie sie sein sollte.

[David Blaikie via llvm-dev]

Re: Opaque pointers - yeah, sorry I've left that lingering for years. +Arthur Eubanks has picked that up recently (& credit to a few others too - +James Y Knight, +Tim Northover, +Matt Arsenault etc along the way) & seems to be making good progress.

(& agreed - it's crossed my mind that gep starts to look "strange" once pointers are typeless - but I wouldn't want to get ahead of ourselves and start removing gep in favor of more raw pointer arithmetic while we still haven't fully transitioned to opaque pointers)

[Madhur Amilkanthwar via llvm-dev]

Speaking of which, I think it would be useful if we can document the progress of migration to opaque pointers somewhere. Going one step ahead, if we have identified fine level items to do (than high level items on opaque poonters page), it would be easy for people to pick up. 

[Arthur Eubanks via llvm-dev]

Yes, I can write up some next steps that should be parallelizable.

[Nikita Popov via llvm-dev]

On Wed, Jun 9, 2021 at 6:19 PM Chris Lattner <clat...@nondot.org> wrote:

Nikita Popov wrote a great block post last week: “Design issues in LLVM IR” that I just found.  It is well framed and nicely written, it seems like a good idea to discuss this on llvm-dev.  :-)

Here are my 2c for what it is worth:

a) I completely agree we should continue to invest in fixing the core of LLVM.  There are long standing issues that we should fix, and not doing so slows things down, leads to worse quality of results, etc.

b) I completely agree with his framing on canonicalization and its value.  I think that LLVM has historically taken this a bit too far (e.g. loop transformations, the old IndVar/LSR dichotomy among others) but many of those have already been walked back.

c) I completely agree we need to continue to march towards opaque pointers, I’m a fan of this work.

d) I’m less enthused about eliminating type based GEP.  The post is right that indexing computations are expensive, but that is largely due to the algorithms used, not the IR structure.  If this was the thing to fix, then we should fix other aspects of the design.  The thing that I’m particularly concerned about is array indexes: I think we need to preserve the ability to do simple dependence analysis and other array subscript indexing analyses in the middle end.  I think the sweet spot is to drop types from pointers, but keep them on GEPs.  Alternatively, finish the typeless pointer migration and then evaluate what to do with GEPs only when that completes.

Right, I don't think it makes sense to address this while we still have pointer element types. That would require encoding an extra result pointer type argument for GEPs, which just makes things worse.

Once we have opaque pointers, I do think it's important to canonicalize GEPs in some way, as we do see optimization failures related to different GEP representations. Using raw offset arithmetic seems the easiest way to do that to me, as generating a canonical type is fairly awkward for more involved expressions like %p + 3 * %i1 + 4 * %i2 + 5, and also runs into DataLayout dependence issues (you can technically give i8 an alignment greater 1, in case there is no longer any convenient type for byte addressing).

I don't think removing GEP types would make much difference when it comes to analyzing arrays. As far as GEPs are concerned, types like [4 x i32] do not restrict valid indices (both -1 and 5 would be legal indices for that type, and possibly even inbounds), so in the end they only provide size information anyway. (The one exception here is the "inrange" attribute, which is only available for constant expression GEPs.)

 

e) Constant Expressions are a disaster.  In addition to the problem identified, there are also many annoying cases to deal with, eg. When constexprs exist in phi nodes, trapping constexprs, etc.  In my opinion, the fix is to eliminate them entirely, in a few steps:

    1) Introduce a new “RelocatableConstant” object which is *not* a mirror of all the IR operations in LLVM, but is instead designed to be used in global variables and allows the standard “globalpointer+offset” pattern that object files support, and we should add a new MachoRelocatableConstant class to represent the “(gv1-gv2+offset)” relocations macho supports.  The presence of this would make codegen and frontends easier to write, and get rid of all the fiddly pattern matching stuff.  I think we need to talk about whether “offset” is a byte offset, or whether it is a series of (constant integer) field indexes in a GEP like operation.  I would argue for the later to make inter procedural optimizations easier to write, but it is debatable.

Something that isn't entirely clear to me is whether these two types of constants cover everything that is supported. LLVM is happy to take something like this:

@a = global i64 0
@g = global i64 sdiv (i64 ptrtoint (i64* getelementptr (i64, i64* @a, i64 1) to i64), i64 3)

And produce this kind of assembly from it:

g:
.quad (a+8)/3

The code that decides what is accepted in initializers is https://github.com/llvm/llvm-project/blob/aaaeb4b160fe94e0ad3bcd6073eea4807f84a33a/llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp#L2445 and covers quite a few operations. Did this code just get over-generalized, or is there some reason for the set of operations it supports?

Regards,

Nikita

[Chris Lattner via llvm-dev]

Sorry for dropping off the face of the earth:

On Jun 10, 2021, at 3:01 AM, Nicolai Hähnle <nhae...@gmail.com> wrote:

Right. I'd like to see more of the learnings of MLIR make it into LLVM IR. It's quite unfortunate that the introduction of MLIR caused a sort of split in the community. 

I agree, but I was trying to focus this thread on specific problems in LLVM that aren’t really related to MLIR.  Replacing the whole mid-level optimizer with a bunch of MLIR passes would be one solution to this problem, but that isn’t what I’m proposing. :)

On Jun 10, 2021, at 1:44 PM, Nikita Popov <nikit...@gmail.com> wrote:

e) Constant Expressions are a disaster.  In addition to the problem identified, there are also many annoying cases to deal with, eg. When constexprs exist in phi nodes, trapping constexprs, etc.  In my opinion, the fix is to eliminate them entirely, in a few steps:

    1) Introduce a new “RelocatableConstant” object which is *not* a mirror of all the IR operations in LLVM, but is instead designed to be used in global variables and allows the standard “globalpointer+offset” pattern that object files support, and we should add a new MachoRelocatableConstant class to represent the “(gv1-gv2+offset)” relocations macho supports.  The presence of this would make codegen and frontends easier to write, and get rid of all the fiddly pattern matching stuff.  I think we need to talk about whether “offset” is a byte offset, or whether it is a series of (constant integer) field indexes in a GEP like operation.  I would argue for the later to make inter procedural optimizations easier to write, but it is debatable.

Something that isn't entirely clear to me is whether these two types of constants cover everything that is supported. LLVM is happy to take something like this:

@a = global i64 0 
@g = global i64 sdiv (i64 ptrtoint (i64* getelementptr (i64, i64* @a, i64 1) to i64), i64 3)

And produce this kind of assembly from it:

g:
.quad (a+8)/3

The code that decides what is accepted in initializers is https://github.com/llvm/llvm-project/blob/aaaeb4b160fe94e0ad3bcd6073eea4807f84a33a/llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp#L2445 and covers quite a few operations. Did this code just get over-generalized, or is there some reason for the set of operations it supports?

Sort of both, but also the problem is that AsmPrinter::lowerConstant was written before really understanding the problem (actually, it was written in the MC timeframe, but was refactored from existing logic that didn’t understand it).

Because it predated the MC layer, all of the different things going on with object files were confused, as was the fact that assemblers have constant folding (which is highly irrelevant to the LLVM code generator).

The three things that matter at this level (please correct me if I’m wrong!) are:

1) we need aggregate constants for structs, arrays etc.

2) We need simple integer/float/vector constants which are bitwise initialized.

3) We need relocatable constants.

For #3, we have a closed set of object files we support (ELF,COFF,MachO), so we have a specific set of things to support.

-Chris