llvm dev - Mar 2016 - [RFC] lifetime.end metadata

I'd like to get a quick feedback on the lifetime.end metadata kind I'm
considering using. I'm planning to use it in cases where lifetime.end
intrinsics do not give lifetime bounds that are tight enough.

As an example of when lifetime.end cannot provide a tight lifetime bound,
consider the following program:

void test111(int n) {
  if (n < 10) {
    string    str = "One";
    cout << str;
  } else if (n < 100) {
    string    str = "Two";
    cout << str;
  } else if (n < 1000) {
    string    str = "Three";
    cout << str;
  }
}

In the program, the three local variables "str" have lifetimes that do
not
overlap with each other, so it should be possible to use the same stack
slot for all of them to save stack space. However, clang/llvm currently
allocates separate slots for each of the three variables because clang
doesn't insert lifetime.end markers after the objects are destructed (for
example, the destructor of the first string is called in block "lpad"
in
line 71 of the attached bitcode f1.ll, but there is no lifetime.end marker
inserted).

If we want to insert the missing lifetime.end markers for the strings,
we'll have to insert them at the beginning of lpad's successors,
%eh.resume
and %terminate.lpad, because the destructor call in lpad is an invoke
instruction. However, if we insert the lifetime.end markers for all of
them, the lifetimes of the strings will overlap clang generates only one
resume block and one terminate block per function.

To get tighter bounds for the strings' lifetimes, I'm considering
attaching
lifetime.end metadata to the destructor calls in clang:

invoke void @foo("basic_string"* %str) to label %eh.resume unwind
label
%terminate.lpad, !lifetime_end !10

!10 = !{i32 0}

SelectionDAGBuilder will then insert a lifetime.end node if there is a
lifetime.end attached to an invoke instruction.

Does this sound like a reasonable approach? Or are there better ways to
tell the backend that the lifetimes do not overlap?
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160301/27ef494d/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: test3.cpp
Type: text/x-c++src
Size: 267 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160301/27ef494d/attachment.cpp>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: f1.ll
Type: application/octet-stream
Size: 32762 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160301/27ef494d/attachment.obj>

On Tue, Mar 1, 2016 at 1:39 PM, Akira Hatanaka <ahatanak at gmail.com>
wrote:
> I'd like to get a quick feedback on the lifetime.end metadata kind
I'm
> considering using. I'm planning to use it in cases where lifetime.end
> intrinsics do not give lifetime bounds that are tight enough.
>
> As an example of when lifetime.end cannot provide a tight lifetime bound,
> consider the following program:
>
> void test111(int n) {
>   if (n < 10) {
>     string    str = "One";
>     cout << str;
>   } else if (n < 100) {
>     string    str = "Two";
>     cout << str;
>   } else if (n < 1000) {
>     string    str = "Three";
>     cout << str;
>   }
> }
>
> In the program, the three local variables "str" have lifetimes
that do not
> overlap with each other, so it should be possible to use the same stack
> slot for all of them to save stack space. However, clang/llvm currently
> allocates separate slots for each of the three variables because clang
> doesn't insert lifetime.end markers after the objects are destructed
(for
> example, the destructor of the first string is called in block
"lpad" in
> line 71 of the attached bitcode f1.ll, but there is no lifetime.end marker
> inserted).
>
> If we want to insert the missing lifetime.end markers for the strings,
> we'll have to insert them at the beginning of lpad's successors,
%eh.resume
> and %terminate.lpad, because the destructor call in lpad is an invoke
> instruction. However, if we insert the lifetime.end markers for all of
> them, the lifetimes of the strings will overlap clang generates only one
> resume block and one terminate block per function.
>
>
This is what I was trying to say:

"However, if we insert the lifetime.end markers for all of them, the
lifetimes of the strings will overlap since clang generates only one resume
block and one terminate block per function."

To get tighter bounds for the strings' lifetimes, I'm considering
attaching
> lifetime.end metadata to the destructor calls in clang:
>
> invoke void @foo("basic_string"* %str) to label %eh.resume unwind
label
> %terminate.lpad, !lifetime_end !10
>
> !10 = !{i32 0}
>
> SelectionDAGBuilder will then insert a lifetime.end node if there is a
> lifetime.end attached to an invoke instruction.
>
> Does this sound like a reasonable approach? Or are there better ways to
> tell the backend that the lifetimes do not overlap?
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160301/3194c493/attachment-0001.html>

On Tue, Mar 1, 2016 at 1:39 PM, Akira Hatanaka via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
>
> If we want to insert the missing lifetime.end markers for the strings,
> we'll have to insert them at the beginning of lpad's successors,
%eh.resume
> and %terminate.lpad, because the destructor call in lpad is an invoke
> instruction. However, if we insert the lifetime.end markers for all of
> them, the lifetimes of the strings will overlap clang generates only one
> resume block and one terminate block per function.
>
In C++11, destructors are noexcept by default, so I'm not sure this really
matters that much going forward. You can still declare your destructor
noexcept(false), in which case, maybe we don't care as much about
optimizing your stack slot usage.

>
> To get tighter bounds for the strings' lifetimes, I'm considering
> attaching lifetime.end metadata to the destructor calls in clang:
>
> invoke void @foo("basic_string"* %str) to label %eh.resume unwind
label
> %terminate.lpad, !lifetime_end !10
>
> !10 = !{i32 0}
>
> SelectionDAGBuilder will then insert a lifetime.end node if there is a
> lifetime.end attached to an invoke instruction.
>
> Does this sound like a reasonable approach? Or are there better ways to
> tell the backend that the lifetimes do not overlap?
>
I think there are issues with this proposal. How does this approach
interact with IPO like inlining? Would we insert lifetime.end in the
inliner? What if we delete the dtor because it has no side effects, do we
lose the lifetime info?

LLVM CFG soup makes this stuff kind of awkward. :(
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160301/3fce6b2f/attachment.html>

On Tue, Mar 1, 2016 at 2:52 PM, Reid Kleckner <rnk at google.com> wrote:
> On Tue, Mar 1, 2016 at 1:39 PM, Akira Hatanaka via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>>
>> If we want to insert the missing lifetime.end markers for the strings,
>> we'll have to insert them at the beginning of lpad's
successors, %eh.resume
>> and %terminate.lpad, because the destructor call in lpad is an invoke
>> instruction. However, if we insert the lifetime.end markers for all of
>> them, the lifetimes of the strings will overlap clang generates only
one
>> resume block and one terminate block per function.
>>
>
> In C++11, destructors are noexcept by default, so I'm not sure this
really
> matters that much going forward. You can still declare your destructor
> noexcept(false), in which case, maybe we don't care as much about
> optimizing your stack slot usage.
>
>
Ah, that's a good point. I still have to investigate whether the code is or
can be compiled with -std=c++11, but if that is the case, lifetime.end
metadata won't be needed.

>
>> To get tighter bounds for the strings' lifetimes, I'm
considering
>> attaching lifetime.end metadata to the destructor calls in clang:
>>
>> invoke void @foo("basic_string"* %str) to label %eh.resume
unwind label
>> %terminate.lpad, !lifetime_end !10
>>
>> !10 = !{i32 0}
>>
>> SelectionDAGBuilder will then insert a lifetime.end node if there is a
>> lifetime.end attached to an invoke instruction.
>>
>> Does this sound like a reasonable approach? Or are there better ways to
>> tell the backend that the lifetimes do not overlap?
>>
>
> I think there are issues with this proposal. How does this approach
> interact with IPO like inlining? Would we insert lifetime.end in the
> inliner? What if we delete the dtor because it has no side effects, do we
> lose the lifetime info?
>
> LLVM CFG soup makes this stuff kind of awkward. :(
>
I think we would have to make changes to insert a lifetime.end marker when
the destructor function is inlined or is deleted. In the worst case, if the
call to the destructor is deleted and a marker isn't inserted, the
StackColoring will not be able to merge the stack slots but will still
generate functionally correct code.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160302/89159829/attachment.html>