Here is a proposal that I mentioned sometime ago. Any
thoughts,comments or
suggestions on this proposal would be appreciated.
-
Devang
//
=
=
=----------------------------------------------------------------------
===//
// Function Notes (or Traits)
//
=
=
=----------------------------------------------------------------------
===//
This document describes the motivation and semantics of encoding
function Notes
in the LLVM IR.
//
=
=
=----------------------------------------------------------------------
===//
// The problem
//
Link Time Optimization
The llvm-gcc supports Link Time Optimization (LTO) at optimization
level -O4 on
platforms where the linker support is available. This optimization
level also
enables -O3 level optimization passes at the compile time. The -O3
optimization
level enables aggressive inlining which may sacrifice code size for
the code
performance. Now, the llvm-gcc also supports optimize for size, -Os.
However,
right now there is not any way today to select optimize for size
during link
time optimizations. At link time, the optimizer (LTO) may receive
input LLVM
IR files that are compiled and optimized using various optimization
choices.
Today, there is not any way to communicate these optimization choices
to LTO,
which is a limitation.
Code Generation
The LLVM code generator supports various target specific choices, for
example
optimizer for size, enable exception handling, eliminate frame pointer
etc..
The llvm-gcc selects these choices based on the command line arguments
and
default settings for the target. However, this information is not
preserved in
llvm IR. This means, the llvm IR generated by llvm-gcc does not
contain enough
information to independently reproduce llvm code generator behaviors
using stand
alone tools like llc.
The Inliner
The GCC compiler supports inliner specific attributes, e.g. noinline,
always_inline. These attributes instruct the inliner to take special
actions for
the function that specifies them. This information is not properly
encoded in
LLVM IR, which means the llvm inliner is not informed about such special
requests, for example always_inline. Today, llvm-gcc respects GCC’s
noinline
attribute but the current solution is not ideal.
//
=
=
=----------------------------------------------------------------------
===//
// Proposed solution
//
The proposed solution to this problem to encode Function Notes in the
IR.
define void @f() notes("opt-size,pic,noinline") { ... }
Here, the notes include a comma separated list of strings. Note, the
notes are
only attached to functions definitions. They are not attached to call
or invoke
instructions. All supported notes must be documented in LLVM language
reference.
The LLVM passes are responsible to take appropriate actions based on
Function
Notes associated with function definition. For example,
define void @fn1() notes("opt-size=1") { ... }
The function fn1() is being optimized for size without losing
significant
performance. The inliner will update inlining threshold for fn1() such
that the
functions called by fn1() are checked for size threshold for fn1()
while being
inlined inside fn1(). If the function fn1() is itself inlined
somewhere, for
example bar(), then the inlining threshold for bar() will be the
deciding factor.
define void @fn2() notes("opt-size=2") { ... }
The function fn2() is aggressively optimized for size. The code
generator may
sacrifice performance while selecting instructions. The inliner will
aggressively
reduce inlining threshold.
define void @fn3() notes("noinline") { ... }
define void @fn4() notes("always_inline") { ... }
define void @fn5() notes("noinline,always_inline") { ... }
Here the inliner is instructed to not inline function fn3() anywhere
and inline
function fn4() everywhere. The function fn5() is malformed and it
should be
rejected by the verifier.
define void @fn6() notes("opt-size=1,noinline") { ... }
This is valid. The inliner is instructed to not inline fn6() here.
The target CPU specific features can be encoded as function notes.
define void @fn7() notes("x86.sse3") { ... }
define void @fn8() notes("x86.no-sse") { ... }
define void @fn9() notes("arm.no-thumb") { ... }
define void @fn10() notes("arm.force-thumb") { ... }
The fn7() note "sse3" instructs the x86 code generator to use SSE3
instructions
in fn7() whereas the code generator should not use SSE instructions
for function
fn8().
The Function Notes are not a place for all the llvm-gcc command line
options.
Each note should represent function specific choice or an option for
LLVM
passes. For example, optimize for size is appropriate because it
instructions
the LLVM passes to make appropriate choices and update their
thresholds. It is
appropriate to encode -ffast-math related choices here. It is not
appropriate
to include -O4 as a function note.
//
=
=
=----------------------------------------------------------------------
===//
// Implementation Overview
//
[0] Implement llvm::Function Note store and access interface.
[1] Update LLVM Asm Parser to recognize Function Notes.
[2] Update LLVM Printer to print Function Notes.
[3] Update LLVM BitCode Reader and Writer to handle Function Notes.
[4] Update optimization passes to recognize "opt-size" property
Update the inliner to recognize "noinline" and
"always_inline"
Notes.
[5] Many code generation choices are encoded as global variables in
TargetOptions.h. Update code generation passes to read these
choices from
function notes and eliminate these global variables.
[6] Update LTO to merge function Notes from various IR files
appropriately.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20080822/8aa9d2bf/attachment.html>
On Fri, Aug 22, 2008 at 6:40 PM, Devang Patel <dpatel at apple.com> wrote:> Here is a proposal that I mentioned sometime ago. Any thoughts,comments or > suggestions on this proposal would be appreciated.> The proposed solution to this problem to encode Function Notes in the IR. > define void @f() notes("opt-size,pic,noinline") { ... } > Here, the notes include a comma separated list of strings. Note, the notes > are > only attached to functions definitions. They are not attached to call or > invoke > instructions. All supported notes must be documented in LLVM language > reference.Would this subsume calling convention and linkage and const/pure specification? (as well as "used" (or more appropriately "do-not-internalize")). It seems that it covers those too if it applied to function definitions and declarations and thus reduce all the extra function meta-data to one format. Andrew
Hi Devang,> All supported notes must be documented in LLVM language reference.Does this also mean that undocumented / unsupported notes are invalid? In particular, when I have a custom frontend and backend, using custom notes could be a great way to communicate between those, if the LLVM IR would allow unknown notes. Other than that, this seems like a decent approach. As Andrew pointed out, I do think that perhaps calling conventions and function attributes could be included as notes, though I think most (if not all) of them are conceptually different (but perhaps a few could be moved?). Gr. Matthijs -------------- next part -------------- A non-text attachment was scrubbed... Name: signature.asc Type: application/pgp-signature Size: 189 bytes Desc: Digital signature URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20080823/d529cee8/attachment.sig>
On Aug 22, 2008, at 8:30 PM, Andrew Lenharth wrote:> On Fri, Aug 22, 2008 at 6:40 PM, Devang Patel <dpatel at apple.com> > wrote: >> Here is a proposal that I mentioned sometime ago. Any >> thoughts,comments or >> suggestions on this proposal would be appreciated. > >> The proposed solution to this problem to encode Function Notes in >> the IR. >> define void @f() notes("opt-size,pic,noinline") { ... } >> Here, the notes include a comma separated list of strings. Note, >> the notes >> are >> only attached to functions definitions. They are not attached to >> call or >> invoke >> instructions. All supported notes must be documented in LLVM language >> reference. > > Would this subsume calling convention and linkage and const/pure > specification?No, that is not the goal.> (as well as "used" (or more appropriately > "do-not-internalize")).yes, "used" could be handled by notes. I am not so sure about "do-not- internalize". - Devang
On Aug 23, 2008, at 6:58 AM, Matthijs Kooijman wrote:> Hi Devang, > >> All supported notes must be documented in LLVM language reference. > Does this also mean that undocumented / unsupported notes are invalid?Yes. This is not a replacement for existing annotation instructions.> In > particular, when I have a custom frontend and backend, using custom > notes > could be a great way to communicate between those, if the LLVM IR > would allow > unknown notes. > > Other than that, this seems like a decent approach. As Andrew > pointed out, I > do think that perhaps calling conventions and function attributes > could be > included as notes, though I think most (if not all) of them are > conceptually > different (but perhaps a few could be moved?).The goal here is to provide optimizer and code generator hints about choices made by the user on the command line. Typically, these choices are specific and the optimizer and code generation passes are "advised" to act on these notes if possible, for example, optimize for size. It is not a good idea to encode, optimization level 3 in notes. The linkage information is not an advise that the respective pass can ignore without causing disaster. So is true for calling convention. One good example to clarify role played by notes is : Notes are not designed to specify target architecture or target machine, however it may be used to restrict/enable use of certain instruction subset per function by a code generation pass. The notes themselves do not influence selection of a pass. The notes guide pass when there are alternative choices a pass can made, which are typically exposed by a command line argument. - Devang
Hi Devang, I have a few questions below. On Aug 22, 2008, at 4:40 PM, Devang Patel wrote:> Here is a proposal that I mentioned sometime ago. Any > thoughts,comments or > suggestions on this proposal would be appreciated. > - > Devang > > // > = > = > = > ----------------------------------------------------------------------= > ==// > // Function Notes (or Traits) > // > = > = > = > ----------------------------------------------------------------------= > ==// > > This document describes the motivation and semantics of encoding > function Notes > in the LLVM IR. > > // > = > = > = > ----------------------------------------------------------------------= > ==// > // The problem > // > > Link Time Optimization > > The llvm-gcc supports Link Time Optimization (LTO) at optimization > level -O4 on > platforms where the linker support is available. This optimization > level also > enables -O3 level optimization passes at the compile time. The -O3 > optimization > level enables aggressive inlining which may sacrifice code size for > the code > performance. Now, the llvm-gcc also supports optimize for size, -Os. > However, > right now there is not any way today to select optimize for size > during link > time optimizations. At link time, the optimizer (LTO) may receive > input LLVM > IR files that are compiled and optimized using various optimization > choices. > Today, there is not any way to communicate these optimization > choices to LTO, > which is a limitation. > > Code Generation > > The LLVM code generator supports various target specific choices, > for example > optimizer for size, enable exception handling, eliminate frame > pointer etc.. > The llvm-gcc selects these choices based on the command line > arguments and > default settings for the target. However, this information is not > preserved in > llvm IR. This means, the llvm IR generated by llvm-gcc does not > contain enough > information to independently reproduce llvm code generator behaviors > using stand > alone tools like llc.From this description, it sounds like this particular problem is that users just aren't accustomed to passing their "optimization" options to the compiler during the "link" phase. Is there more to it than that? Otherwise, this sounds like a problem best solved in documentation and IDEs.> > The Inliner > > The GCC compiler supports inliner specific attributes, e.g. noinline, > always_inline. These attributes instruct the inliner to take special > actions for > the function that specifies them. This information is not properly > encoded in > LLVM IR, which means the llvm inliner is not informed about such > special > requests, for example always_inline. Today, llvm-gcc respects GCC’s > noinline > attribute but the current solution is not ideal.We already have attributes like "noreturn". Can you discuss what the main advantages are of using this new notes mechanism instead of just adding more function attributes like the ones we already have?> > > // > = > = > = > ----------------------------------------------------------------------= > ==// > // Proposed solution > // > > The proposed solution to this problem to encode Function Notes in > the IR. > > define void @f() notes("opt-size,pic,noinline") { ... } > > Here, the notes include a comma separated list of strings. Note, the > notes are > only attached to functions definitions. They are not attached to > call or invoke > instructions. All supported notes must be documented in LLVM > language reference.Would unsupported notes be rejected in the Verifier?> > The LLVM passes are responsible to take appropriate actions based on > Function > Notes associated with function definition. For example, > > define void @fn1() notes("opt-size=1") { ... } > > The function fn1() is being optimized for size without losing > significant > performance. The inliner will update inlining threshold for fn1() > such that the > functions called by fn1() are checked for size threshold for fn1() > while being > inlined inside fn1(). If the function fn1() is itself inlined > somewhere, for > example bar(), then the inlining threshold for bar() will be the > deciding factor. > > define void @fn2() notes("opt-size=2") { ... } > > The function fn2() is aggressively optimized for size. The code > generator may > sacrifice performance while selecting instructions. The inliner will > aggressively > reduce inlining threshold. > > define void @fn3() notes("noinline") { ... } > define void @fn4() notes("always_inline") { ... } > define void @fn5() notes("noinline,always_inline") { ... } > > Here the inliner is instructed to not inline function fn3() anywhere > and inline > function fn4() everywhere. The function fn5() is malformed and it > should be > rejected by the verifier. > > define void @fn6() notes("opt-size=1,noinline") { ... } > > This is valid. The inliner is instructed to not inline fn6() here. > > The target CPU specific features can be encoded as function notes. > > define void @fn7() notes("x86.sse3") { ... } > define void @fn8() notes("x86.no-sse") { ... } > define void @fn9() notes("arm.no-thumb") { ... } > define void @fn10() notes("arm.force-thumb") { ... } > > The fn7() note "sse3" instructs the x86 code generator to use SSE3 > instructions > in fn7() whereas the code generator should not use SSE instructions > for function > fn8().Can the names directly correspond with the current -mattr names somehow? It'd be good to avoid inventing yet another subtarget minilanguage :-).> > The Function Notes are not a place for all the llvm-gcc command line > options. > Each note should represent function specific choice or an option for > LLVM > passes. For example, optimize for size is appropriate because it > instructions > the LLVM passes to make appropriate choices and update their > thresholds. It is > appropriate to encode -ffast-math related choices here. It is not > appropriate > to include -O4 as a function note.What's the fundamental difference between -Os and -O4 here? Why is one appropriate for a note and the other not? Also, if you're going to put -ffast-math in a note, please include in this proposal a description of what happens when a -ffast-math function is inlined into a -fno-fast-math function, or a -fno-fast-math function is inlined into an -ffast-math one. Also, how about all the various individual options that -ffast-math is an umbrella for? Thanks, Dan
On Aug 25, 2008, at 1:12 PM, Dan Gohman wrote:> From this description, it sounds like this particular problem is that > users just aren't accustomed to passing their "optimization" options > to the compiler during the "link" phase. Is there more to it than > that?Yes. The issue is that optimization/code generation choices for various input IRs at link time may not match.> Otherwise, this sounds like a problem best solved in documentation > and IDEs. > >> >> The Inliner >> >> The GCC compiler supports inliner specific attributes, e.g. noinline, >> always_inline. These attributes instruct the inliner to take special >> actions for >> the function that specifies them. This information is not properly >> encoded in >> LLVM IR, which means the llvm inliner is not informed about such >> special >> requests, for example always_inline. Today, llvm-gcc respects GCC’s >> noinline >> attribute but the current solution is not ideal. > > We already have attributes like "noreturn". Can you discuss what the > main advantages are of using this new notes mechanism instead of just > adding more function attributes like the ones we already have?Right now we have parameter attributes. NoReturn is implemented as a special case parameter attribute, which is not idea. Initially we named this proposal as function attributes then later on we realized that this is not specific to GCC's function attributes.> Would unsupported notes be rejected in the Verifier?yes.> Can the names directly correspond with the current -mattr names > somehow? It'd be good to avoid inventing yet another subtarget > minilanguage :-).Fine with me :)>> The Function Notes are not a place for all the llvm-gcc command line >> options. >> Each note should represent function specific choice or an option for >> LLVM >> passes. For example, optimize for size is appropriate because it >> instructions >> the LLVM passes to make appropriate choices and update their >> thresholds. It is >> appropriate to encode -ffast-math related choices here. It is not >> appropriate >> to include -O4 as a function note. > > What's the fundamental difference between -Os and -O4 here? Why is one > appropriate for a note and the other not?-Os is specific - Optimize for size. The llvm pass can make appropriate decision, e.g. update their thresholds, based on this note. -O4 is useful for the tool that is arranging pass sequence. Optimization level 4 is defined and documented at llvm-gcc level, it has no meaning at llvm IR level.> Also, if you're going to put -ffast-math in a note, please include in > this proposal a description of what happens when a -ffast-math > function > is inlined into a -fno-fast-math function, or a -fno-fast-math > function > is inlined into an -ffast-math one.We are in unchartered territory thanks to LTO! What happens today, without Function Notes, when user does following ? $ llvm-gcc -c -ffast-math foo.c -O3 --emit-llvm -o foo.o $ llvm-gcc -c -fno-fast-math bar.c -O3 --emit-llvm -o bar.o $ llvm-gcc foo.o bar.o -o foobar -O4 We will have to make appropriate decisions when the LTO merges notes from different compilation units and document them properly. - Devang> Also, how about all the various > individual options that -ffast-math is an umbrella for?
On Aug 22, 2008, at 4:40 PM, Devang Patel wrote:> The LLVM passes are responsible to take appropriate actions based on > Function > Notes associated with function definition. For example, > > define void @fn1() notes("opt-size=1") { ... } > > The function fn1() is being optimized for size without losing > significant > performance. The inliner will update inlining threshold for fn1() > such that the > functions called by fn1() are checked for size threshold for fn1() > while being > inlined inside fn1(). If the function fn1() is itself inlined > somewhere, for > example bar(), then the inlining threshold for bar() will be the > deciding factor. > > define void @fn2() notes("opt-size=2") { ... } > > The function fn2() is aggressively optimized for size. The code > generator may > sacrifice performance while selecting instructions. The inliner will > aggressively > reduce inlining threshold. > > define void @fn3() notes("noinline") { ... } > define void @fn4() notes("always_inline") { ... } > define void @fn5() notes("noinline,always_inline") { ... } > > Here the inliner is instructed to not inline function fn3() anywhere > and inline > function fn4() everywhere. The function fn5() is malformed and it > should be > rejected by the verifier.Since you opened the door with values for opt-size, couldn't we do the same for inlining. That is: define void @fn3() notes("inline=never") { ... } define void @fn4() notes("inline=always") { ... } Then the general rule is that there can be only one "foo=" in the set of notes. I know this won't make the __attribute__ keywords, but it would make the function notes cleaner. Also, could there be a name for 1 and 2 on opt-size? What happens when we find a need for a third kind of opt-size... These seem like great default parameters for code-gen, but looking forward, if we also allowed some optimization flags to be specified at LTO time, how would they interact? -Nick -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20080825/43f83586/attachment.html>
On Aug 25, 2008, at 3:24 PM, Nick Kledzik wrote:> > On Aug 22, 2008, at 4:40 PM, Devang Patel wrote: > >> The LLVM passes are responsible to take appropriate actions based >> on Function >> Notes associated with function definition. For example, >> >> define void @fn1() notes("opt-size=1") { ... } >> >> The function fn1() is being optimized for size without losing >> significant >> performance. The inliner will update inlining threshold for fn1() >> such that the >> functions called by fn1() are checked for size threshold for fn1() >> while being >> inlined inside fn1(). If the function fn1() is itself inlined >> somewhere, for >> example bar(), then the inlining threshold for bar() will be the >> deciding factor. >> >> define void @fn2() notes("opt-size=2") { ... } >> >> The function fn2() is aggressively optimized for size. The code >> generator may >> sacrifice performance while selecting instructions. The inliner >> will aggressively >> reduce inlining threshold. >> >> define void @fn3() notes("noinline") { ... } >> define void @fn4() notes("always_inline") { ... } >> define void @fn5() notes("noinline,always_inline") { ... } >> >> Here the inliner is instructed to not inline function fn3() >> anywhere and inline >> function fn4() everywhere. The function fn5() is malformed and it >> should be >> rejected by the verifier. > > Since you opened the door with values for opt-size, couldn't we do > the same for inlining. That is: > > define void @fn3() notes("inline=never") { ... } > define void @fn4() notes("inline=always") { ... } > > Then the general rule is that there can be only one "foo=" in the > set of notes.yes! I did not think about this. This is a good idea.> I know this won't make the __attribute__ keywords, but it would > make the function notes cleaner. > > Also, could there be a name for 1 and 2 on opt-size? What happens > when we find a need for a third kind of opt-size... > > > These seem like great default parameters for code-gen, but looking > forward, if we also allowed some optimization flags to be specified > at LTO time, how would they interact?The flags specified on the linker command line during LTO are not encoded into llvm IR. However, IMO, these linker command line flags should override notes encoded in llvm IR. We may have to handle special cases, but we should document linker's decision choices properly. - Devang -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20080825/4f23b1ed/attachment.html>
On Aug 22, 2008, at 4:40 PM, Devang Patel wrote: I like it. It's simple enough to understand. We can implement the easy (and most frequently used) stuff first and go from there.> > > // > = > = > = > ----------------------------------------------------------------------= > ==// > // Implementation Overview > // > > [0] Implement llvm::Function Note store and access interface. > [1] Update LLVM Asm Parser to recognize Function Notes. > [2] Update LLVM Printer to print Function Notes. > [3] Update LLVM BitCode Reader and Writer to handle Function Notes. > [4] Update optimization passes to recognize "opt-size" property > Update the inliner to recognize "noinline" and "always_inline" > Notes.Some naming inconsistency here. opt-size vs. always_inline. If there isn't a win to use the same name as gcc attribute, always-inline might be better.> [5] Many code generation choices are encoded as global variables in > TargetOptions.h. Update code generation passes to read these > choices from > function notes and eliminate these global variables. > [6] Update LTO to merge function Notes from various IR files > appropriately.One issue I can think of. Options change. Their names can change, some can go away, etc. Do we have AutoUpgrade to upgrade them? Is there a better solution? Evan> > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20080825/1cafb7fc/attachment.html>
On Aug 23, 2008, at 6:58 AM, Matthijs Kooijman wrote:> Hi Devang, > >> All supported notes must be documented in LLVM language reference. > Does this also mean that undocumented / unsupported notes are > invalid? In > particular, when I have a custom frontend and backend, using custom > notes > could be a great way to communicate between those, if the LLVM IR > would allow > unknown notes.As mentioned before Devang's proposal is not really suited for that. The notes should be considered to be part of the LLVM IR, and documented in langref (Devang, did you do this?). The metadata proposal I sent out would be a more appropriate way of handling cases where front-ends want to propagate arbitrary information. http://nondot.org/sabre/LLVMNotes/EmbeddedMetadata.txt -Chris
Possibly Parallel Threads
- [LLVMdev] Proposal : Function Notes
- [LLVMdev] Proposal : Function Notes
- Behavior or as.environment in function arguments/call (and force() behaviors...)
- [RFC][InlineCost] Modeling JumpThreading (or similar) in inline cost model
- [RFC][InlineCost] Modeling JumpThreading (or similar) in inline cost model