llvm dev - Oct 2015 - [RFC] Clean up the way we store optional Function data

Here is a WIP patch as promised:

    http://reviews.llvm.org/D13829

It uses a hungoff uselist to store optional data as needed.

Some early objections from Duncan:

    - An extra one-time malloc() is required to set personality functions.
    - We get and set personality functions frequently. This patch introduces a
level of indirection which slows the common case down.

Is this overhead acceptable?

If not, maybe we could leave personality function handling untouched and add a
"Constant **OptionalData" array to Function.

vedant

> On Oct 14, 2015, at 3:12 PM, Vedant Kumar <vsk at apple.com> wrote:
> 
> I like the idea of using hung off uses.
> 
> We can keep using SubclassData to indicate whether or not some optional
data is present.
> 
> Benefits: zero space overhead until some optional data is set, we can get
rid of the DenseMaps in LLVMContextImpl, and RAUW just works (so no clang
changes are needed).
> 
> I'll have a patch up before the end of the week.
> 
> thanks
> vedant
> 
> 
>> On Oct 12, 2015, at 12:15 PM, Sanjoy Das via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
>> 
>> 
>> 
>> David Majnemer wrote:
>>> 
>>> 
>>> On Mon, Oct 12, 2015 at 11:00 AM, Duncan P. N. Exon Smith via
llvm-dev
>>> <llvm-dev at lists.llvm.org <mailto:llvm-dev at
lists.llvm.org>> wrote:
>>> 
>>> 
>>>> On 2015-Oct-12, at 10:41, Sanjoy Das
>>>   <sanjoy at playingwithpointers.com
>>>   <mailto:sanjoy at playingwithpointers.com>> wrote:
>>>> 
>>>> 
>>>> 
>>>> Vedant Kumar wrote:
>>>>>>> That's a neat idea. To summarize: make Function
have 3 optional
>>>   operands. (For context -- Function currently has 1 optional
operand,
>>>   and my proposal is to move to 0.)
>>>>>>> 
>>>>>>> Could someone else chime in on what they'd like
to see?
>>>>>> Sanjoy's idea makes sense to me, but only if we
never need to add
>>>>>> prefix/prologue data after functions are created.  Are
there any
>>>   places
>>>>>> where we need/want to add them after the fact?
>>>>> 
>>>>> I think so. I see:
>>>>> 
>>>>> LinkModules.cpp:
>>>   Dst.setPrefixData(MapValue(Src.getPrefixData(), ValueMap,
>>>>> BitcodeReader.cpp:
>>>   FunctionPrologueWorklist.back().first->setPrologueData(C);
>>>>> InlineFunction.cpp:
Caller->setPersonalityFn(CalledPersonality);
>>>>> 
>>>>> Some of these sites could be refactored so that the
Functions are
>>>   created with the prefix/prologue data they need. I don't
think
>>>   that's possible for personality functions (see my third
example).
>>>>> 
>>>>> Would we inhibit any future patches which add
prefix/prologue
>>>   data to Functions on the fly by taking this approach?
>>>> 
>>>> You should always be able to create a new `llvm::Function`
>>>   instance (and RAUW it in) if you want to add prefix/prologue data
to
>>>   functions after they've been created; just like you have to
do today
>>>   for any other `llvm::User`s that do not have hung off uses.
>>> 
>>>   It's possible, but a lot more involved with `Function`s. 
Besides
>>>   RAUW, you need to transfer over all the basic blocks.
>>> 
>>>   This seems kind of wrong to me, if we expect it to happen.
>>> 
>>>>  Which brings me to -- can you use hung off uses for this? 
These
>>>   use lists can be resized on the fly, so you should be able to add
>>>   and remove prologue data on the fly.  If you're using hung
off uses,
>>>   you'll probably still need a descriptor to remember whether /
which
>>>   operands are prologue data etc.
>>> 
>>>   Sure, this is another option.  It might be simplest.  I'd be
>>>   tempted to start with a 0/3 choice (if we allocate any hung-off
>>>   uses, allocate enough for all three operands) to simplify the
>>>   logic.  Although I can't remember right now whether
that's
>>>   legal (having nullptr operands followed by real ones)...
>>> 
>>>>>>>>> Personalities are stored as ``optional``
Function operands.
>>>   We actually always
>>>>>>>>> allocate the space for this ``optional``
operand: there's a
>>>   FIXME in the
>>>>>>>>> destructor for Function about this.
>>> 
>>>   Makes me wonder, why didn't we use hung off uses to begin
with?
>>>   Do functions "usually" have personality functions, for
some
>>>   definition of?
>>> 
>>> 
>>> Depends. In C++? It's pretty common to have objects which have
>>> non-trivial destructors on the stack which means calling a function
will
>>> be an invoke which will require the function to have a personality.
In
>>> C? It's pretty rare. You'd need something like
__attribute__((cleanup))
>>> to do it, the most common source of this will be something
>>> like pthread_cleanup_push. If I recall correctly, Julia sets the
>>> personality on functions regardless of whether or not there are any
>>> invokes, they need the AsmPrinter to scribble something down.  I
can't
>>> say for other languages (Rust, etc.).  From what I understand,
Swift
>>> doesn't use landingpad for EH so they wouldn't need the
personality set.
>> 
>> Most functions we emit from our Java frontend have personalities.
>> 
>> -- Sanjoy
>> 
>>> 
>>>   _______________________________________________
>>>   LLVM Developers mailing list
>>>   llvm-dev at lists.llvm.org <mailto:llvm-dev at
lists.llvm.org>
>>>   http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>> 
>>> 
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>

> On 2015-Oct-16, at 13:54, Vedant Kumar <vsk at apple.com> wrote:
> 
> Here is a WIP patch as promised:
> 
>    http://reviews.llvm.org/D13829
> 
> It uses a hungoff uselist to store optional data as needed.
> 
> Some early objections from Duncan:
> 
>    - An extra one-time malloc() is required to set personality functions.
>    - We get and set personality functions frequently. This patch introduces
a level of indirection which slows the common case down.
> 
> Is this overhead acceptable?
If the overhead isn't bad, then this SGTM.  (I haven't looked at the
patch.)

I guess I was thinking about large applications that use C++ exceptions
and build with LTO, but even there it's a per-function overhead.  I
doubt it really matters.  
> If not, maybe we could leave personality function handling untouched and
add a "Constant **OptionalData" array to Function.
The `IndirectUser` approach you outlined initially might be better
than this?
> vedant
> 
> 
>> On Oct 14, 2015, at 3:12 PM, Vedant Kumar <vsk at apple.com>
wrote:
>> 
>> I like the idea of using hung off uses.
>> 
>> We can keep using SubclassData to indicate whether or not some optional
data is present.
>> 
>> Benefits: zero space overhead until some optional data is set, we can
get rid of the DenseMaps in LLVMContextImpl, and RAUW just works (so no clang
changes are needed).
>> 
>> I'll have a patch up before the end of the week.
>> 
>> thanks
>> vedant
>> 
>> 
>>> On Oct 12, 2015, at 12:15 PM, Sanjoy Das via llvm-dev <llvm-dev
at lists.llvm.org> wrote:
>>> 
>>> 
>>> 
>>> David Majnemer wrote:
>>>> 
>>>> 
>>>> On Mon, Oct 12, 2015 at 11:00 AM, Duncan P. N. Exon Smith via
llvm-dev
>>>> <llvm-dev at lists.llvm.org <mailto:llvm-dev at
lists.llvm.org>> wrote:
>>>> 
>>>> 
>>>>> On 2015-Oct-12, at 10:41, Sanjoy Das
>>>>  <sanjoy at playingwithpointers.com
>>>>  <mailto:sanjoy at playingwithpointers.com>> wrote:
>>>>> 
>>>>> 
>>>>> 
>>>>> Vedant Kumar wrote:
>>>>>>>> That's a neat idea. To summarize: make
Function have 3 optional
>>>>  operands. (For context -- Function currently has 1 optional
operand,
>>>>  and my proposal is to move to 0.)
>>>>>>>> 
>>>>>>>> Could someone else chime in on what they'd
like to see?
>>>>>>> Sanjoy's idea makes sense to me, but only if we
never need to add
>>>>>>> prefix/prologue data after functions are created. 
Are there any
>>>>  places
>>>>>>> where we need/want to add them after the fact?
>>>>>> 
>>>>>> I think so. I see:
>>>>>> 
>>>>>> LinkModules.cpp:
>>>>  Dst.setPrefixData(MapValue(Src.getPrefixData(), ValueMap,
>>>>>> BitcodeReader.cpp:
>>>>  FunctionPrologueWorklist.back().first->setPrologueData(C);
>>>>>> InlineFunction.cpp:
Caller->setPersonalityFn(CalledPersonality);
>>>>>> 
>>>>>> Some of these sites could be refactored so that the
Functions are
>>>>  created with the prefix/prologue data they need. I don't
think
>>>>  that's possible for personality functions (see my third
example).
>>>>>> 
>>>>>> Would we inhibit any future patches which add
prefix/prologue
>>>>  data to Functions on the fly by taking this approach?
>>>>> 
>>>>> You should always be able to create a new `llvm::Function`
>>>>  instance (and RAUW it in) if you want to add prefix/prologue
data to
>>>>  functions after they've been created; just like you have
to do today
>>>>  for any other `llvm::User`s that do not have hung off uses.
>>>> 
>>>>  It's possible, but a lot more involved with `Function`s. 
Besides
>>>>  RAUW, you need to transfer over all the basic blocks.
>>>> 
>>>>  This seems kind of wrong to me, if we expect it to happen.
>>>> 
>>>>> Which brings me to -- can you use hung off uses for this? 
These
>>>>  use lists can be resized on the fly, so you should be able to
add
>>>>  and remove prologue data on the fly.  If you're using hung
off uses,
>>>>  you'll probably still need a descriptor to remember
whether / which
>>>>  operands are prologue data etc.
>>>> 
>>>>  Sure, this is another option.  It might be simplest.  I'd
be
>>>>  tempted to start with a 0/3 choice (if we allocate any
hung-off
>>>>  uses, allocate enough for all three operands) to simplify the
>>>>  logic.  Although I can't remember right now whether
that's
>>>>  legal (having nullptr operands followed by real ones)...
>>>> 
>>>>>>>>>> Personalities are stored as
``optional`` Function operands.
>>>>  We actually always
>>>>>>>>>> allocate the space for this
``optional`` operand: there's a
>>>>  FIXME in the
>>>>>>>>>> destructor for Function about this.
>>>> 
>>>>  Makes me wonder, why didn't we use hung off uses to begin
with?
>>>>  Do functions "usually" have personality functions,
for some
>>>>  definition of?
>>>> 
>>>> 
>>>> Depends. In C++? It's pretty common to have objects which
have
>>>> non-trivial destructors on the stack which means calling a
function will
>>>> be an invoke which will require the function to have a
personality. In
>>>> C? It's pretty rare. You'd need something like
__attribute__((cleanup))
>>>> to do it, the most common source of this will be something
>>>> like pthread_cleanup_push. If I recall correctly, Julia sets
the
>>>> personality on functions regardless of whether or not there are
any
>>>> invokes, they need the AsmPrinter to scribble something down. 
I can't
>>>> say for other languages (Rust, etc.).  From what I understand,
Swift
>>>> doesn't use landingpad for EH so they wouldn't need the
personality set.
>>> 
>>> Most functions we emit from our Java frontend have personalities.
>>> 
>>> -- Sanjoy
>>> 
>>>> 
>>>>  _______________________________________________
>>>>  LLVM Developers mailing list
>>>>  llvm-dev at lists.llvm.org <mailto:llvm-dev at
lists.llvm.org>
>>>>  http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>>> 
>>>> 
>>> _______________________________________________
>>> LLVM Developers mailing list
>>> llvm-dev at lists.llvm.org
>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>> 
>

I've done some measurements on this.

The test program I have just calls Function::Create(), F->setPersonalityFn(),
and then F->eraseFromParent() in a loop 2^20 times.

Results:

    pre-patch  --- min: 1.10s    max: 1.13s    avg: 1.11s
    post-patch --- min: 1.26s    max: 1.35s    avg: 1.29s

So we expect to lose 0.2 seconds per 1 million functions (with personality
functions) in a project. I've only tested on my machine, and I haven't
accounted for performance variations in other parts of the codebase where code
was removed.

I'm happy enough with the patch and think that this is a reasonable
tradeoff. Should we go with this?

http://reviews.llvm.org/D13829

vedant

> On Oct 16, 2015, at 5:56 PM, Duncan P. N. Exon Smith <dexonsmith at
apple.com> wrote:
> 
> 
>> On 2015-Oct-16, at 13:54, Vedant Kumar <vsk at apple.com> wrote:
>> 
>> Here is a WIP patch as promised:
>> 
>>   http://reviews.llvm.org/D13829
>> 
>> It uses a hungoff uselist to store optional data as needed.
>> 
>> Some early objections from Duncan:
>> 
>>   - An extra one-time malloc() is required to set personality
functions.
>>   - We get and set personality functions frequently. This patch
introduces a level of indirection which slows the common case down.
>> 
>> Is this overhead acceptable?
> 
> If the overhead isn't bad, then this SGTM.  (I haven't looked at
the
> patch.)
> 
> I guess I was thinking about large applications that use C++ exceptions
> and build with LTO, but even there it's a per-function overhead.  I
> doubt it really matters.  
> 
>> If not, maybe we could leave personality function handling untouched
and add a "Constant **OptionalData" array to Function.
> 
> The `IndirectUser` approach you outlined initially might be better
> than this?
> 
>> vedant
>> 
>> 
>>> On Oct 14, 2015, at 3:12 PM, Vedant Kumar <vsk at apple.com>
wrote:
>>> 
>>> I like the idea of using hung off uses.
>>> 
>>> We can keep using SubclassData to indicate whether or not some
optional data is present.
>>> 
>>> Benefits: zero space overhead until some optional data is set, we
can get rid of the DenseMaps in LLVMContextImpl, and RAUW just works (so no
clang changes are needed).
>>> 
>>> I'll have a patch up before the end of the week.
>>> 
>>> thanks
>>> vedant
>>> 
>>> 
>>>> On Oct 12, 2015, at 12:15 PM, Sanjoy Das via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
>>>> 
>>>> 
>>>> 
>>>> David Majnemer wrote:
>>>>> 
>>>>> 
>>>>> On Mon, Oct 12, 2015 at 11:00 AM, Duncan P. N. Exon Smith
via llvm-dev
>>>>> <llvm-dev at lists.llvm.org <mailto:llvm-dev at
lists.llvm.org>> wrote:
>>>>> 
>>>>> 
>>>>>> On 2015-Oct-12, at 10:41, Sanjoy Das
>>>>> <sanjoy at playingwithpointers.com
>>>>> <mailto:sanjoy at playingwithpointers.com>> wrote:
>>>>>> 
>>>>>> 
>>>>>> 
>>>>>> Vedant Kumar wrote:
>>>>>>>>> That's a neat idea. To summarize: make
Function have 3 optional
>>>>> operands. (For context -- Function currently has 1 optional
operand,
>>>>> and my proposal is to move to 0.)
>>>>>>>>> 
>>>>>>>>> Could someone else chime in on what
they'd like to see?
>>>>>>>> Sanjoy's idea makes sense to me, but only
if we never need to add
>>>>>>>> prefix/prologue data after functions are
created.  Are there any
>>>>> places
>>>>>>>> where we need/want to add them after the fact?
>>>>>>> 
>>>>>>> I think so. I see:
>>>>>>> 
>>>>>>> LinkModules.cpp:
>>>>> Dst.setPrefixData(MapValue(Src.getPrefixData(), ValueMap,
>>>>>>> BitcodeReader.cpp:
>>>>>
FunctionPrologueWorklist.back().first->setPrologueData(C);
>>>>>>> InlineFunction.cpp:
Caller->setPersonalityFn(CalledPersonality);
>>>>>>> 
>>>>>>> Some of these sites could be refactored so that the
Functions are
>>>>> created with the prefix/prologue data they need. I
don't think
>>>>> that's possible for personality functions (see my third
example).
>>>>>>> 
>>>>>>> Would we inhibit any future patches which add
prefix/prologue
>>>>> data to Functions on the fly by taking this approach?
>>>>>> 
>>>>>> You should always be able to create a new
`llvm::Function`
>>>>> instance (and RAUW it in) if you want to add
prefix/prologue data to
>>>>> functions after they've been created; just like you
have to do today
>>>>> for any other `llvm::User`s that do not have hung off uses.
>>>>> 
>>>>> It's possible, but a lot more involved with
`Function`s.  Besides
>>>>> RAUW, you need to transfer over all the basic blocks.
>>>>> 
>>>>> This seems kind of wrong to me, if we expect it to happen.
>>>>> 
>>>>>> Which brings me to -- can you use hung off uses for
this?  These
>>>>> use lists can be resized on the fly, so you should be able
to add
>>>>> and remove prologue data on the fly.  If you're using
hung off uses,
>>>>> you'll probably still need a descriptor to remember
whether / which
>>>>> operands are prologue data etc.
>>>>> 
>>>>> Sure, this is another option.  It might be simplest. 
I'd be
>>>>> tempted to start with a 0/3 choice (if we allocate any
hung-off
>>>>> uses, allocate enough for all three operands) to simplify
the
>>>>> logic.  Although I can't remember right now whether
that's
>>>>> legal (having nullptr operands followed by real ones)...
>>>>> 
>>>>>>>>>>> Personalities are stored as
``optional`` Function operands.
>>>>> We actually always
>>>>>>>>>>> allocate the space for this
``optional`` operand: there's a
>>>>> FIXME in the
>>>>>>>>>>> destructor for Function about this.
>>>>> 
>>>>> Makes me wonder, why didn't we use hung off uses to
begin with?
>>>>> Do functions "usually" have personality
functions, for some
>>>>> definition of?
>>>>> 
>>>>> 
>>>>> Depends. In C++? It's pretty common to have objects
which have
>>>>> non-trivial destructors on the stack which means calling a
function will
>>>>> be an invoke which will require the function to have a
personality. In
>>>>> C? It's pretty rare. You'd need something like
__attribute__((cleanup))
>>>>> to do it, the most common source of this will be something
>>>>> like pthread_cleanup_push. If I recall correctly, Julia
sets the
>>>>> personality on functions regardless of whether or not there
are any
>>>>> invokes, they need the AsmPrinter to scribble something
down.  I can't
>>>>> say for other languages (Rust, etc.).  From what I
understand, Swift
>>>>> doesn't use landingpad for EH so they wouldn't need
the personality set.
>>>> 
>>>> Most functions we emit from our Java frontend have
personalities.
>>>> 
>>>> -- Sanjoy
>>>> 
>>>>> 
>>>>> _______________________________________________
>>>>> LLVM Developers mailing list
>>>>> llvm-dev at lists.llvm.org <mailto:llvm-dev at
lists.llvm.org>
>>>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>>>> 
>>>>> 
>>>> _______________________________________________
>>>> LLVM Developers mailing list
>>>> llvm-dev at lists.llvm.org
>>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>> 
>> 
>