The LRM (http://llvm.org/docs/LangRef.html#llvm-lifetime-start-intrinsic)
essentially states that:
- ptr is dead before a call to "lifetime.start size, ptr"
- ptr is dead after a call to "lifetime.end size, ptr"
This is all good and fine, and the expected use case is that all
"lifetime.end size, ptr" markers are matched with a preceding
"lifetime.start size, ptr" in the CFG.
What is supposed to happen when a "lifetime.end size, ptr" is not
matched
with a "lifetime.start size, ptr" ? I think there are a few possible
answers:
- the memory area pointed to by ptr is assumed to be alive since function
entry
- the memory area pointed to by ptr is assumed to be dead since function
entry, as it has not been marked alive
- this is an unexpected situation
I think this ambiguity should be cleared in the LRM, because today's
implicit assumption may be broken at any time.
This is not a theoretical question: clang can generate such cases. For
example, the following testcase:
struct X {
void doSomething();
char b[33];
};
void bar(X &);
void baz();
void test(int i) {
if (i==9) {
X x;
x.doSomething();
label:
bar(x);
} else {
baz();
if (i==0)
goto label;
}
}
Produces:
%struct.X = type { [33 x i8] }
define void @_Z4testi(i32 %i) {
entry:
%x = alloca %struct.X, align 1
%cmp = icmp eq i32 %i, 9
br i1 %cmp, label %if.then, label %if.else
if.then: ; preds = %entry
%0 = getelementptr inbounds %struct.X* %x, i64 0, i32 0, i64 0
call void @llvm.lifetime.start(i64 33, i8* %0)
call void @_ZN1X11doSomethingEv(%struct.X* %x)
br label %label
label: ; preds
%if.else.label_crit_edge, %if.then
%.pre-phi = phi i8* [ %.pre, %if.else.label_crit_edge ], [ %0, %if.then ]
call void @_Z3barR1X(%struct.X* dereferenceable(33) %x)
call void @llvm.lifetime.end(i64 33, i8* %.pre-phi)
br label %if.end3
if.else: ; preds = %entry
tail call void @_Z3bazv()
%cmp1 = icmp eq i32 %i, 0
br i1 %cmp1, label %if.else.label_crit_edge, label %if.end3
if.else.label_crit_edge: ; preds = %if.else
%.pre = getelementptr inbounds %struct.X* %x, i64 0, i32 0, i64 0
br label %label
if.end3: ; preds = %if.else, %label
ret void
}
Note that the path thru if.else.label_crit_edge has no lifetime start.
Cheers,
--
Arnaud
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20141104/64e2f5f7/attachment.html>
Hi Arnaud. In that path, X x seems to be undefined, so the behaviour is anyone's guess. If I'm not mistaken, the standard says that kind of code is ill-formed (6.7-p3). Clang folks might know better. cheers, --renato On 4 November 2014 11:59, Arnaud A. de Grandmaison <arnaud.degrandmaison at arm.com> wrote:> The LRM (http://llvm.org/docs/LangRef.html#llvm-lifetime-start-intrinsic) > essentially states that: > > - ptr is dead before a call to “lifetime.start size, ptr” > > - ptr is dead after a call to “lifetime.end size, ptr” > > > > This is all good and fine, and the expected use case is that all > “lifetime.end size, ptr” markers are matched with a preceding > “lifetime.start size, ptr” in the CFG. > > > > What is supposed to happen when a “lifetime.end size, ptr” is not matched > with a “lifetime.start size, ptr” ? I think there are a few possible > answers: > > - the memory area pointed to by ptr is assumed to be alive since function > entry > > - the memory area pointed to by ptr is assumed to be dead since function > entry, as it has not been marked alive > > - this is an unexpected situation > > > > I think this ambiguity should be cleared in the LRM, because today’s > implicit assumption may be broken at any time. > > > > This is not a theoretical question: clang can generate such cases. For > example, the following testcase: > > struct X { > > void doSomething(); > > char b[33]; > > }; > > > > void bar(X &); > > void baz(); > > > > void test(int i) { > > if (i==9) { > > X x; > > x.doSomething(); > > label: > > bar(x); > > } else { > > baz(); > > if (i==0) > > goto label; > > } > > } > > > > Produces: > > > > %struct.X = type { [33 x i8] } > > > > define void @_Z4testi(i32 %i) { > > entry: > > %x = alloca %struct.X, align 1 > > %cmp = icmp eq i32 %i, 9 > > br i1 %cmp, label %if.then, label %if.else > > > > if.then: ; preds = %entry > > %0 = getelementptr inbounds %struct.X* %x, i64 0, i32 0, i64 0 > > call void @llvm.lifetime.start(i64 33, i8* %0) > > call void @_ZN1X11doSomethingEv(%struct.X* %x) > > br label %label > > > > label: ; preds > %if.else.label_crit_edge, %if.then > > %.pre-phi = phi i8* [ %.pre, %if.else.label_crit_edge ], [ %0, %if.then ] > > call void @_Z3barR1X(%struct.X* dereferenceable(33) %x) > > call void @llvm.lifetime.end(i64 33, i8* %.pre-phi) > > br label %if.end3 > > > > if.else: ; preds = %entry > > tail call void @_Z3bazv() > > %cmp1 = icmp eq i32 %i, 0 > > br i1 %cmp1, label %if.else.label_crit_edge, label %if.end3 > > > > if.else.label_crit_edge: ; preds = %if.else > > %.pre = getelementptr inbounds %struct.X* %x, i64 0, i32 0, i64 0 > > br label %label > > > > if.end3: ; preds = %if.else, %label > > ret void > > } > > > > Note that the path thru if.else.label_crit_edge has no lifetime start. > > > > Cheers, > > -- > > Arnaud > > > > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >
Hi Renato, Just so this conversation does not get too side-tracked, from what Arnaud told me at the developers' meeting, this general issue breaks self-hosting of Clang/LLVM if we enable lifetime intrinsics for smaller objects. So even if the specific example is not really a well-defined program, the general problem still needs to be resolved for well-defined programs. -Hal ----- Original Message -----> From: "Renato Golin" <renato.golin at linaro.org> > To: "Arnaud A. de Grandmaison" <arnaud.degrandmaison at arm.com> > Cc: "Clang Dev" <cfe-dev at cs.uiuc.edu>, "LLVM Developers Mailing List" <llvmdev at cs.uiuc.edu> > Sent: Tuesday, November 4, 2014 7:19:03 AM > Subject: Re: [cfe-dev] [LLVMdev] lifetime.start/end clarification > > Hi Arnaud. > > In that path, X x seems to be undefined, so the behaviour is anyone's > guess. If I'm not mistaken, the standard says that kind of code is > ill-formed (6.7-p3). > > Clang folks might know better. > > cheers, > --renato > > On 4 November 2014 11:59, Arnaud A. de Grandmaison > <arnaud.degrandmaison at arm.com> wrote: > > The LRM > > (http://llvm.org/docs/LangRef.html#llvm-lifetime-start-intrinsic) > > essentially states that: > > > > - ptr is dead before a call to “lifetime.start size, ptr” > > > > - ptr is dead after a call to “lifetime.end size, ptr” > > > > > > > > This is all good and fine, and the expected use case is that all > > “lifetime.end size, ptr” markers are matched with a preceding > > “lifetime.start size, ptr” in the CFG. > > > > > > > > What is supposed to happen when a “lifetime.end size, ptr” is not > > matched > > with a “lifetime.start size, ptr” ? I think there are a few > > possible > > answers: > > > > - the memory area pointed to by ptr is assumed to be alive since > > function > > entry > > > > - the memory area pointed to by ptr is assumed to be dead since > > function > > entry, as it has not been marked alive > > > > - this is an unexpected situation > > > > > > > > I think this ambiguity should be cleared in the LRM, because > > today’s > > implicit assumption may be broken at any time. > > > > > > > > This is not a theoretical question: clang can generate such cases. > > For > > example, the following testcase: > > > > struct X { > > > > void doSomething(); > > > > char b[33]; > > > > }; > > > > > > > > void bar(X &); > > > > void baz(); > > > > > > > > void test(int i) { > > > > if (i==9) { > > > > X x; > > > > x.doSomething(); > > > > label: > > > > bar(x); > > > > } else { > > > > baz(); > > > > if (i==0) > > > > goto label; > > > > } > > > > } > > > > > > > > Produces: > > > > > > > > %struct.X = type { [33 x i8] } > > > > > > > > define void @_Z4testi(i32 %i) { > > > > entry: > > > > %x = alloca %struct.X, align 1 > > > > %cmp = icmp eq i32 %i, 9 > > > > br i1 %cmp, label %if.then, label %if.else > > > > > > > > if.then: ; preds = %entry > > > > %0 = getelementptr inbounds %struct.X* %x, i64 0, i32 0, i64 0 > > > > call void @llvm.lifetime.start(i64 33, i8* %0) > > > > call void @_ZN1X11doSomethingEv(%struct.X* %x) > > > > br label %label > > > > > > > > label: ; preds > > %if.else.label_crit_edge, %if.then > > > > %.pre-phi = phi i8* [ %.pre, %if.else.label_crit_edge ], [ %0, > > %if.then ] > > > > call void @_Z3barR1X(%struct.X* dereferenceable(33) %x) > > > > call void @llvm.lifetime.end(i64 33, i8* %.pre-phi) > > > > br label %if.end3 > > > > > > > > if.else: ; preds = %entry > > > > tail call void @_Z3bazv() > > > > %cmp1 = icmp eq i32 %i, 0 > > > > br i1 %cmp1, label %if.else.label_crit_edge, label %if.end3 > > > > > > > > if.else.label_crit_edge: ; preds > > %if.else > > > > %.pre = getelementptr inbounds %struct.X* %x, i64 0, i32 0, i64 0 > > > > br label %label > > > > > > > > if.end3: ; preds > > %if.else, %label > > > > ret void > > > > } > > > > > > > > Note that the path thru if.else.label_crit_edge has no lifetime > > start. > > > > > > > > Cheers, > > > > -- > > > > Arnaud > > > > > > > > > > _______________________________________________ > > LLVM Developers mailing list > > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > > > > _______________________________________________ > cfe-dev mailing list > cfe-dev at cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev >-- Hal Finkel Assistant Computational Scientist Leadership Computing Facility Argonne National Laboratory
Hey Renato, As a reduced testcase, I agree this looks weird, but I do not think this is undefined behaviour: this is allowed iff x have trivial ctors and dtors (and clang enforces it). Bar(X &) may be able to (and even designed to) handle the uninitialized object. Cheers, Arnaud -----Original Message----- From: Renato Golin [mailto:renato.golin at linaro.org] Sent: 04 November 2014 14:19 To: Arnaud De Grandmaison Cc: LLVM Developers Mailing List; Clang Dev Subject: Re: [LLVMdev] lifetime.start/end clarification Hi Arnaud. In that path, X x seems to be undefined, so the behaviour is anyone's guess. If I'm not mistaken, the standard says that kind of code is ill-formed (6.7-p3). Clang folks might know better. cheers, --renato On 4 November 2014 11:59, Arnaud A. de Grandmaison <arnaud.degrandmaison at arm.com> wrote:> The LRM > (http://llvm.org/docs/LangRef.html#llvm-lifetime-start-intrinsic) > essentially states that: > > - ptr is dead before a call to “lifetime.start size, ptr” > > - ptr is dead after a call to “lifetime.end size, ptr” > > > > This is all good and fine, and the expected use case is that all > “lifetime.end size, ptr” markers are matched with a preceding > “lifetime.start size, ptr” in the CFG. > > > > What is supposed to happen when a “lifetime.end size, ptr” is not > matched with a “lifetime.start size, ptr” ? I think there are a few > possible > answers: > > - the memory area pointed to by ptr is assumed to be alive since > function entry > > - the memory area pointed to by ptr is assumed to be dead since > function entry, as it has not been marked alive > > - this is an unexpected situation > > > > I think this ambiguity should be cleared in the LRM, because today’s > implicit assumption may be broken at any time. > > > > This is not a theoretical question: clang can generate such cases. For > example, the following testcase: > > struct X { > > void doSomething(); > > char b[33]; > > }; > > > > void bar(X &); > > void baz(); > > > > void test(int i) { > > if (i==9) { > > X x; > > x.doSomething(); > > label: > > bar(x); > > } else { > > baz(); > > if (i==0) > > goto label; > > } > > } > > > > Produces: > > > > %struct.X = type { [33 x i8] } > > > > define void @_Z4testi(i32 %i) { > > entry: > > %x = alloca %struct.X, align 1 > > %cmp = icmp eq i32 %i, 9 > > br i1 %cmp, label %if.then, label %if.else > > > > if.then: ; preds = %entry > > %0 = getelementptr inbounds %struct.X* %x, i64 0, i32 0, i64 0 > > call void @llvm.lifetime.start(i64 33, i8* %0) > > call void @_ZN1X11doSomethingEv(%struct.X* %x) > > br label %label > > > > label: ; preds > %if.else.label_crit_edge, %if.then > > %.pre-phi = phi i8* [ %.pre, %if.else.label_crit_edge ], [ %0, > %if.then ] > > call void @_Z3barR1X(%struct.X* dereferenceable(33) %x) > > call void @llvm.lifetime.end(i64 33, i8* %.pre-phi) > > br label %if.end3 > > > > if.else: ; preds = %entry > > tail call void @_Z3bazv() > > %cmp1 = icmp eq i32 %i, 0 > > br i1 %cmp1, label %if.else.label_crit_edge, label %if.end3 > > > > if.else.label_crit_edge: ; preds = %if.else > > %.pre = getelementptr inbounds %struct.X* %x, i64 0, i32 0, i64 0 > > br label %label > > > > if.end3: ; preds = %if.else, %label > > ret void > > } > > > > Note that the path thru if.else.label_crit_edge has no lifetime start. > > > > Cheers, > > -- > > Arnaud > > > > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >-- IMPORTANT NOTICE: The contents of this email and any attachments are confidential and may also be privileged. If you are not the intended recipient, please notify the sender immediately and do not disclose the contents to any other person, use it for any purpose, or store or copy the information in any medium. Thank you. ARM Limited, Registered office 110 Fulbourn Road, Cambridge CB1 9NJ, Registered in England & Wales, Company No: 2557590 ARM Holdings plc, Registered office 110 Fulbourn Road, Cambridge CB1 9NJ, Registered in England & Wales, Company No: 2548782
----- Original Message -----> From: "Arnaud A. de Grandmaison" <arnaud.degrandmaison at arm.com> > To: "LLVM Developers Mailing List" <llvmdev at cs.uiuc.edu> > Sent: Tuesday, November 4, 2014 5:59:28 AM > Subject: [LLVMdev] lifetime.start/end clarification > > The LRM > (http://llvm.org/docs/LangRef.html#llvm-lifetime-start-intrinsic) > essentially states that: > > - ptr is dead before a call to “lifetime.start size, ptr” > > - ptr is dead after a call to “lifetime.end size, ptr” > > > > This is all good and fine, and the expected use case is that all > “lifetime.end size, ptr” markers are matched with a preceding > “lifetime.start size, ptr” in the CFG. > > > > What is supposed to happen when a “lifetime.end size, ptr” is not > matched with a “lifetime.start size, ptr” ? I think there are a few > possible answers: > > - the memory area pointed to by ptr is assumed to be alive since > function entry > > - the memory area pointed to by ptr is assumed to be dead since > function entry, as it has not been marked alive > > - this is an unexpected situation >When you say "unmatched", do you mean not visible in any dominating block? Assuming we realize that the lifetime begin could also be inside a function called by any of these dominating blocks (assuming the pointer is an argument or is captured prior to the call), it seems most logical to say that the ptr is alive (and invariant) from the function entry.> > > I think this ambiguity should be cleared in the LRM, because today’s > implicit assumptionWhat is today's implicit assumption? Thanks again, Hal> may be broken at any time. > > > > This is not a theoretical question: clang can generate such cases. > For example, the following testcase: > > struct X { > > void doSomething(); > > char b[33]; > > }; > > > > void bar(X &); > > void baz(); > > > > void test(int i) { > > if (i==9) { > > X x; > > x.doSomething(); > > label: > > bar(x); > > } else { > > baz(); > > if (i==0) > > goto label; > > } > > } > > > > Produces: > > > > %struct.X = type { [33 x i8] } > > > > define void @_Z4testi(i32 %i) { > > entry: > > %x = alloca %struct.X, align 1 > > %cmp = icmp eq i32 %i, 9 > > br i1 %cmp, label %if.then, label %if.else > > > > if.then: ; preds = %entry > > %0 = getelementptr inbounds %struct.X* %x, i64 0, i32 0, i64 0 > > call void @llvm.lifetime.start(i64 33, i8* %0) > > call void @_ZN1X11doSomethingEv(%struct.X* %x) > > br label %label > > > > label: ; preds = %if.else.label_crit_edge, %if.then > > %.pre-phi = phi i8* [ %.pre, %if.else.label_crit_edge ], [ %0, > %if.then ] > > call void @_Z3barR1X(%struct.X* dereferenceable(33) %x) > > call void @llvm.lifetime.end(i64 33, i8* %.pre-phi) > > br label %if.end3 > > > > if.else: ; preds = %entry > > tail call void @_Z3bazv() > > %cmp1 = icmp eq i32 %i, 0 > > br i1 %cmp1, label %if.else.label_crit_edge, label %if.end3 > > > > if.else.label_crit_edge: ; preds = %if.else > > %.pre = getelementptr inbounds %struct.X* %x, i64 0, i32 0, i64 0 > > br label %label > > > > if.end3: ; preds = %if.else, %label > > ret void > > } > > > > Note that the path thru if.else.label_crit_edge has no lifetime > start. > > > > Cheers, > > -- > > Arnaud > > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >-- Hal Finkel Assistant Computational Scientist Leadership Computing Facility Argonne National Laboratory
> -----Original Message----- > From: Hal Finkel [mailto:hfinkel at anl.gov] > Sent: 04 November 2014 17:16 > To: Arnaud De Grandmaison > Cc: LLVM Developers Mailing List > Subject: Re: [LLVMdev] lifetime.start/end clarification > > ----- Original Message ----- > > From: "Arnaud A. de Grandmaison" <arnaud.degrandmaison at arm.com> > > To: "LLVM Developers Mailing List" <llvmdev at cs.uiuc.edu> > > Sent: Tuesday, November 4, 2014 5:59:28 AM > > Subject: [LLVMdev] lifetime.start/end clarification > > > > The LRM > > (http://llvm.org/docs/LangRef.html#llvm-lifetime-start-intrinsic) > > essentially states that: > > > > - ptr is dead before a call to “lifetime.start size, ptr” > > > > - ptr is dead after a call to “lifetime.end size, ptr” > > > > > > > > This is all good and fine, and the expected use case is that all > > “lifetime.end size, ptr” markers are matched with a preceding > > “lifetime.start size, ptr” in the CFG. > > > > > > > > What is supposed to happen when a “lifetime.end size, ptr” is not > > matched with a “lifetime.start size, ptr” ? I think there are a few > > possible answers: > > > > - the memory area pointed to by ptr is assumed to be alive since > > function entry > > > > - the memory area pointed to by ptr is assumed to be dead since > > function entry, as it has not been marked alive > > > > - this is an unexpected situation > > > > When you say "unmatched", do you mean not visible in any dominating > block? Assuming we realize that the lifetime begin could also be inside a > function called by any of these dominating blocks (assuming the pointer is an > argument or is captured prior to the call), it seems most logical to say that the > ptr is alive (and invariant) from the function entry.Yes, I meant not visible in any dominating block. I believe assuming the ptr is alive from the function entry is conservatively correct, but not optimal. In my testcase, a lifetime.start could be inserted in the crit_edge bb. Do we really want to handle cross-function stack lifetime analysis ? That's an interesting point. Until now, I supposed this all stayed inside the same function.> > > > > > > I think this ambiguity should be cleared in the LRM, because today’s > > implicit assumption > > What is today's implicit assumption?To be honest: I don't know. I have to dig it out of the stack coloring pass, which I think (but I may be wrong) is the only user of the lifetime markers.> > Thanks again, > Hal > > > may be broken at any time. > > > > > > > > This is not a theoretical question: clang can generate such cases. > > For example, the following testcase: > > > > struct X { > > > > void doSomething(); > > > > char b[33]; > > > > }; > > > > > > > > void bar(X &); > > > > void baz(); > > > > > > > > void test(int i) { > > > > if (i==9) { > > > > X x; > > > > x.doSomething(); > > > > label: > > > > bar(x); > > > > } else { > > > > baz(); > > > > if (i==0) > > > > goto label; > > > > } > > > > } > > > > > > > > Produces: > > > > > > > > %struct.X = type { [33 x i8] } > > > > > > > > define void @_Z4testi(i32 %i) { > > > > entry: > > > > %x = alloca %struct.X, align 1 > > > > %cmp = icmp eq i32 %i, 9 > > > > br i1 %cmp, label %if.then, label %if.else > > > > > > > > if.then: ; preds = %entry > > > > %0 = getelementptr inbounds %struct.X* %x, i64 0, i32 0, i64 0 > > > > call void @llvm.lifetime.start(i64 33, i8* %0) > > > > call void @_ZN1X11doSomethingEv(%struct.X* %x) > > > > br label %label > > > > > > > > label: ; preds = %if.else.label_crit_edge, %if.then > > > > %.pre-phi = phi i8* [ %.pre, %if.else.label_crit_edge ], [ %0, > > %if.then ] > > > > call void @_Z3barR1X(%struct.X* dereferenceable(33) %x) > > > > call void @llvm.lifetime.end(i64 33, i8* %.pre-phi) > > > > br label %if.end3 > > > > > > > > if.else: ; preds = %entry > > > > tail call void @_Z3bazv() > > > > %cmp1 = icmp eq i32 %i, 0 > > > > br i1 %cmp1, label %if.else.label_crit_edge, label %if.end3 > > > > > > > > if.else.label_crit_edge: ; preds = %if.else > > > > %.pre = getelementptr inbounds %struct.X* %x, i64 0, i32 0, i64 0 > > > > br label %label > > > > > > > > if.end3: ; preds = %if.else, %label > > > > ret void > > > > } > > > > > > > > Note that the path thru if.else.label_crit_edge has no lifetime start. > > > > > > > > Cheers, > > > > -- > > > > Arnaud > > > > > > _______________________________________________ > > LLVM Developers mailing list > > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > > > > -- > Hal Finkel > Assistant Computational Scientist > Leadership Computing Facility > Argonne National Laboratory
Short version: I think Clang needs some analysis capabilities to widen the
lifetime.
---
I think we need a new approach. These intrinsics were designed to be
general between heap and stack, and we don't need that extra generality for
the simple problem of stack coloring that we're trying to solve here. See
for example the size parameter, which I bet stack coloring doesn't need. If
we have a bitcast alloca, we already know the size.
Rafael had an idea at the dev meeting that maybe the IR needs a stack
deallocation instruction to pair with alloca. Then we could teach LLVM to
consider allocas that are post-dominated by a deallocation instruction to
be static, and fold them into the entry block. He pointed out that the
Swift IL actually has such a construct.
It would be the responsibility of the frontend to ensure that each alloca
is post-dominated by its "dealloca", so in this example with labels,
we'd
just have to hoist the allocation to the nearest dominating block, or just
give up and go to the function entry block. Similarly the deallocation has
to be moved to post-dominate the allocation, to handle cases like:
void foo(int x) {
if (x > 10) {
// alloca y
goto lbl;
while (x) {
int y;
lbl:
y = bar();
x -= y;
}
// dealloca y
}
}
This representation would support more aggressive stack coloring.
Furthermore, it supports a much more efficient lowering for inalloca, which
is why I'm somewhat interested in it.
If we don't want to do this, we can do something less drastic and either
add new intrinsics or modify the current ones with the same rules proposed
above. We'd have the alloca in the entry block, the lifetime start at the
first block that dominates all uses, and the deallocation at the first
block that post-dominates all that stuff.
One other thing to think about is EH. We can often get into a situation
where uses of y are statically reachable from cleanup code while being
dynamically unreachable. This can happen when cleanups are not simply
ordered in a stack-like manner. I think if we can teach clang to do this
kind of domination analysis, then we can probably detect this case and give
up on it by allocating in the entry block.
On Tue, Nov 4, 2014 at 3:59 AM, Arnaud A. de Grandmaison <
arnaud.degrandmaison at arm.com> wrote:
> The LRM (http://llvm.org/docs/LangRef.html#llvm-lifetime-start-intrinsic)
> essentially states that:
>
> - ptr is dead before a call to “lifetime.start size, ptr”
>
> - ptr is dead after a call to “lifetime.end size, ptr”
>
>
>
> This is all good and fine, and the expected use case is that all
> “lifetime.end size, ptr” markers are matched with a preceding
> “lifetime.start size, ptr” in the CFG.
>
>
>
> What is supposed to happen when a “lifetime.end size, ptr” is not matched
> with a “lifetime.start size, ptr” ? I think there are a few possible
> answers:
>
> - the memory area pointed to by ptr is assumed to be alive since function
> entry
>
> - the memory area pointed to by ptr is assumed to be dead since function
> entry, as it has not been marked alive
>
> - this is an unexpected situation
>
>
>
> I think this ambiguity should be cleared in the LRM, because today’s
> implicit assumption may be broken at any time.
>
>
>
> This is not a theoretical question: clang can generate such cases. For
> example, the following testcase:
>
> struct X {
>
> void doSomething();
>
> char b[33];
>
> };
>
>
>
> void bar(X &);
>
> void baz();
>
>
>
> void test(int i) {
>
> if (i==9) {
>
> X x;
>
> x.doSomething();
>
> label:
>
> bar(x);
>
> } else {
>
> baz();
>
> if (i==0)
>
> goto label;
>
> }
>
> }
>
>
>
> Produces:
>
>
>
> %struct.X = type { [33 x i8] }
>
>
>
> define void @_Z4testi(i32 %i) {
>
> entry:
>
> %x = alloca %struct.X, align 1
>
> %cmp = icmp eq i32 %i, 9
>
> br i1 %cmp, label %if.then, label %if.else
>
>
>
> if.then: ; preds = %entry
>
> %0 = getelementptr inbounds %struct.X* %x, i64 0, i32 0, i64 0
>
> call void @llvm.lifetime.start(i64 33, i8* %0)
>
> call void @_ZN1X11doSomethingEv(%struct.X* %x)
>
> br label %label
>
>
>
> label: ; preds >
%if.else.label_crit_edge, %if.then
>
> %.pre-phi = phi i8* [ %.pre, %if.else.label_crit_edge ], [ %0, %if.then ]
>
> call void @_Z3barR1X(%struct.X* dereferenceable(33) %x)
>
> call void @llvm.lifetime.end(i64 33, i8* %.pre-phi)
>
> br label %if.end3
>
>
>
> if.else: ; preds = %entry
>
> tail call void @_Z3bazv()
>
> %cmp1 = icmp eq i32 %i, 0
>
> br i1 %cmp1, label %if.else.label_crit_edge, label %if.end3
>
>
>
> if.else.label_crit_edge: ; preds = %if.else
>
> %.pre = getelementptr inbounds %struct.X* %x, i64 0, i32 0, i64 0
>
> br label %label
>
>
>
> if.end3: ; preds = %if.else,
> %label
>
> ret void
>
> }
>
>
>
> Note that the path thru if.else.label_crit_edge has no lifetime start.
>
>
>
> Cheers,
>
> --
>
> Arnaud
>
>
>
> _______________________________________________
> 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/20141104/c72d7846/attachment.html>
Here are some comments.
It seems to me there are 2 (mostly separate) aspects:
1. Teaching clang how to do domination / post-domination analysis, so that the
lifetime information (alloca/dealloca, or lifetime markers) can be set in the
right locations in the IR. Such an analysis should be able to understand the
language scopes, as well as labels / gotos and EH. The results of this analysis
would be used at IR codegen.
Caveat: I have no expertise in this area of Clang, so take everything with a
grain of salt and please feel free to correct me.
Where should this analysis be run ? Presumably at the beginning of each
function’s codegen’s time.
This analysis looks a bit special (at least to me), as it will work over the
AST, but it also requires a pretty good understanding of LLVM’s IR, which sets
it apart from other clang analyses.
Maybe another option (some may call it a poor’s man option) would be to enforce
at IR codegen time the dominators / post-dominators on the multiple paths
(normal & EH control flows) by inserting basic blocks around each statement
which is codegened. Those would be fall-thru most of the time, the llvm
optimizers can remove them easily. The obvious drawback is that it will insert
lots of small or fall-thru BBs.
2. How liveranges are represented in LLVM’s IR.
I like the idea of pairing alloca / dealloca (and removing the lifetime markers,
at least for stack coloring) and I think it could even ease / improve some
analysis.
Currently, allocas have to be located in the entry BB in order to get a chance
to be promoted to registers by the Mem2Reg pass. Allocas in other BBs are
considered to be dynamic. I have no idea how difficult it would be to teach
Mem2Reg to consider alloca/dealloca in other basic blocks.
With the alloca / dealloca solution, in order to do stack colouring, the alloca
must _not_ be in the entry block, because all allocas defined there are alive at
the same time and cannot be merged. All LLVM passes would need to be teached
that those alloca / dealloca pairs correspond to stack slots --- as the alloca
in the entry. The pairing would also have to be preserved across transformations
(same as lifetime.start/end).
Cheers,
Arnaud
From: Reid Kleckner [mailto:rnk at google.com]
Sent: 04 November 2014 19:35
To: Arnaud De Grandmaison; Nick Lewycky; Rafael Ávila de Espíndola
Cc: LLVM Developers Mailing List
Subject: Re: [LLVMdev] lifetime.start/end clarification
Short version: I think Clang needs some analysis capabilities to widen the
lifetime.
---
I think we need a new approach. These intrinsics were designed to be general
between heap and stack, and we don't need that extra generality for the
simple problem of stack coloring that we're trying to solve here. See for
example the size parameter, which I bet stack coloring doesn't need. If we
have a bitcast alloca, we already know the size.
Rafael had an idea at the dev meeting that maybe the IR needs a stack
deallocation instruction to pair with alloca. Then we could teach LLVM to
consider allocas that are post-dominated by a deallocation instruction to be
static, and fold them into the entry block. He pointed out that the Swift IL
actually has such a construct.
It would be the responsibility of the frontend to ensure that each alloca is
post-dominated by its "dealloca", so in this example with labels,
we'd just have to hoist the allocation to the nearest dominating block, or
just give up and go to the function entry block. Similarly the deallocation has
to be moved to post-dominate the allocation, to handle cases like:
void foo(int x) {
if (x > 10) {
// alloca y
goto lbl;
while (x) {
int y;
lbl:
y = bar();
x -= y;
}
// dealloca y
}
}
This representation would support more aggressive stack coloring. Furthermore,
it supports a much more efficient lowering for inalloca, which is why I'm
somewhat interested in it.
If we don't want to do this, we can do something less drastic and either add
new intrinsics or modify the current ones with the same rules proposed above.
We'd have the alloca in the entry block, the lifetime start at the first
block that dominates all uses, and the deallocation at the first block that
post-dominates all that stuff.
One other thing to think about is EH. We can often get into a situation where
uses of y are statically reachable from cleanup code while being dynamically
unreachable. This can happen when cleanups are not simply ordered in a
stack-like manner. I think if we can teach clang to do this kind of domination
analysis, then we can probably detect this case and give up on it by allocating
in the entry block.
On Tue, Nov 4, 2014 at 3:59 AM, Arnaud A. de Grandmaison
<arnaud.degrandmaison at arm.com> wrote:
The LRM (http://llvm.org/docs/LangRef.html#llvm-lifetime-start-intrinsic)
essentially states that:
- ptr is dead before a call to “lifetime.start size, ptr”
- ptr is dead after a call to “lifetime.end size, ptr”
This is all good and fine, and the expected use case is that all “lifetime.end
size, ptr” markers are matched with a preceding “lifetime.start size, ptr” in
the CFG.
What is supposed to happen when a “lifetime.end size, ptr” is not matched with a
“lifetime.start size, ptr” ? I think there are a few possible answers:
- the memory area pointed to by ptr is assumed to be alive since function entry
- the memory area pointed to by ptr is assumed to be dead since function entry,
as it has not been marked alive
- this is an unexpected situation
I think this ambiguity should be cleared in the LRM, because today’s implicit
assumption may be broken at any time.
This is not a theoretical question: clang can generate such cases. For example,
the following testcase:
struct X {
void doSomething();
char b[33];
};
void bar(X &);
void baz();
void test(int i) {
if (i==9) {
X x;
x.doSomething();
label:
bar(x);
} else {
baz();
if (i==0)
goto label;
}
}
Produces:
%struct.X = type { [33 x i8] }
define void @_Z4testi(i32 %i) {
entry:
%x = alloca %struct.X, align 1
%cmp = icmp eq i32 %i, 9
br i1 %cmp, label %if.then, label %if.else
if.then: ; preds = %entry
%0 = getelementptr inbounds %struct.X* %x, i64 0, i32 0, i64 0
call void @llvm.lifetime.start(i64 33, i8* %0)
call void @_ZN1X11doSomethingEv(%struct.X* %x)
br label %label
label: ; preds =
%if.else.label_crit_edge, %if.then
%.pre-phi = phi i8* [ %.pre, %if.else.label_crit_edge ], [ %0, %if.then ]
call void @_Z3barR1X(%struct.X* dereferenceable(33) %x)
call void @llvm.lifetime.end(i64 33, i8* %.pre-phi)
br label %if.end3
if.else: ; preds = %entry
tail call void @_Z3bazv()
%cmp1 = icmp eq i32 %i, 0
br i1 %cmp1, label %if.else.label_crit_edge, label %if.end3
if.else.label_crit_edge: ; preds = %if.else
%.pre = getelementptr inbounds %struct.X* %x, i64 0, i32 0, i64 0
br label %label
if.end3: ; preds = %if.else, %label
ret void
}
Note that the path thru if.else.label_crit_edge has no lifetime start.
Cheers,
--
Arnaud
_______________________________________________
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/20141105/a943b444/attachment.html>
On 11/04/2014 03:59 AM, Arnaud A. de Grandmaison wrote:> > The LRM > (http://llvm.org/docs/LangRef.html#llvm-lifetime-start-intrinsic) > essentially states that: > > - ptr is dead before a call to “lifetime.start size, ptr” > > - ptr is dead after a call to “lifetime.end size, ptr” > > This is all good and fine, and the expected use case is that all > “lifetime.end size, ptr” markers are matched with a preceding > “lifetime.start size, ptr” in the CFG. > > What is supposed to happen when a “lifetime.end size, ptr” is not > matched with a “lifetime.start size, ptr” ? I think there are a few > possible answers: > > - the memory area pointed to by ptr is assumed to be alive since > function entry > > - the memory area pointed to by ptr is assumed to be dead since > function entry, as it has not been marked alive > > - this is an unexpected situation >My reading of the current spec is that your first option is the only valid interpretation. My interpretation of the spec wording would be that each path in the program may contain either a lifetime.start, a lifetime.end, or both. If the path contains no marker, the location is assumed live (unless proven otherwise). The lifetime markers segment the path into live, and dead regions, but only on that specific path. To reason about global properties, the optimizer must form "for-all-paths" facts. (Dominance being the easiest form of this generally.) Just to note, this is rather different than the "invariant.*" family. In particular, the invariant family requires the "start" as an argument to the "end" intrinsic.> I think this ambiguity should be cleared in the LRM, because today’s > implicit assumption may be broken at any time. >I believe the existing implementation matches the semantics I specified above. If you find a case where it doesn't, that's a bug.> > This is not a theoretical question: clang can generate such cases. For > example, the following testcase: > > struct X { > > void doSomething(); > > char b[33]; > > }; > > void bar(X &); > > void baz(); > > void test(int i) { > > if (i==9) { > > X x; > > x.doSomething(); > > label: > > bar(x); > > } else { > > baz(); > > if (i==0) > > goto label; > > } > > } > > Produces: > > %struct.X = type { [33 x i8] } > > define void @_Z4testi(i32 %i) { > > entry: > > %x = alloca %struct.X, align 1 > > %cmp = icmp eq i32 %i, 9 > > br i1 %cmp, label %if.then, label %if.else > > if.then: ; preds = %entry > > %0 = getelementptr inbounds %struct.X* %x, i64 0, i32 0, i64 0 > > call void @llvm.lifetime.start(i64 33, i8* %0) > > call void @_ZN1X11doSomethingEv(%struct.X* %x) > > br label %label > > label: ; preds = %if.else.label_crit_edge, %if.then > > %.pre-phi = phi i8* [ %.pre, %if.else.label_crit_edge ], [ %0, > %if.then ] > > call void @_Z3barR1X(%struct.X* dereferenceable(33) %x) > > call void @llvm.lifetime.end(i64 33, i8* %.pre-phi) > > br label %if.end3 > > if.else: ; preds = %entry > > tail call void @_Z3bazv() > > %cmp1 = icmp eq i32 %i, 0 > > br i1 %cmp1, label %if.else.label_crit_edge, label %if.end3 > > if.else.label_crit_edge: ; preds = %if.else > > %.pre = getelementptr inbounds %struct.X* %x, i64 0, i32 0, i64 0 > > br label %label > > if.end3: ; preds = %if.else, %label > > ret void > > } > > Note that the path thru if.else.label_crit_edge has no lifetime start. >This seems fine to me. The optimizer can (soundly) conclude that %p is dead after the "lifetime.end" (for the two instructions), and dead before the "lifetime.start" (for the *single* instruction in that basic block, *not* for the previous BB). This seems like the proper result for this example, am I missing something? Philip -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20141105/7cf63cb2/attachment.html>
> > This seems fine to me. The optimizer can (soundly) conclude that %p is > dead after the "lifetime.end" (for the two instructions), and dead before > the "lifetime.start" (for the *single* instruction in that basic block, > *not* for the previous BB). This seems like the proper result for this > example, am I missing something? >What if I put that in a loop, unroll it once, and prove that the lifetime.start is unreachable? We would end up with IR like: loop: ... use %p call void @lifetime.end( %p ) ... use %p call void @lifetime.end( %p ) br i1 %c, label %loop, label %exit Are the second uses of %p uses of dead memory? We have similar issues if the optimizer somehow removes the lifetime end and keeps the start: loop: call void @lifetime.start( %p ) ... use %p call void @lifetime.start( %p ) ... use %p br i1 %c, label %loop, label %exit For this reason, it has been suggested that these intrinsics are horribly broken, and both should be remodeled to just mean "store of undef bytes to this memory". If "use %p" is a load, for example, in both cases we can safely say it returns undef, because it's a use-after-scope. I think coming up with a new representation with simpler semantics is the way to go. One allocation or lifetime start, and one deallocation and end. Implementing this in Clang will be tricky, though. Clang's IRGen is supposed to be a dumb AST walk, but it has already strayed from that path. Needs more thought... -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20141105/e7736105/attachment.html>
From: Philip Reames [mailto:listmail at philipreames.com]
Sent: 05 November 2014 19:21
To: Arnaud De Grandmaison; LLVM Developers Mailing List
Subject: Re: [LLVMdev] lifetime.start/end clarification
On 11/04/2014 03:59 AM, Arnaud A. de Grandmaison wrote:
The LRM (http://llvm.org/docs/LangRef.html#llvm-lifetime-start-intrinsic)
essentially states that:
- ptr is dead before a call to "lifetime.start size, ptr"
- ptr is dead after a call to "lifetime.end size, ptr"
This is all good and fine, and the expected use case is that all
"lifetime.end size, ptr" markers are matched with a preceding
"lifetime.start size, ptr" in the CFG.
What is supposed to happen when a "lifetime.end size, ptr" is not
matched
with a "lifetime.start size, ptr" ? I think there are a few possible
answers:
- the memory area pointed to by ptr is assumed to be alive since function
entry
- the memory area pointed to by ptr is assumed to be dead since function
entry, as it has not been marked alive
- this is an unexpected situation
My reading of the current spec is that your first option is the only valid
interpretation.
My interpretation of the spec wording would be that each path in the program
may contain either a lifetime.start, a lifetime.end, or both. If the path
contains no marker, the location is assumed live (unless proven otherwise).
The lifetime markers segment the path into live, and dead regions, but only
on that specific path. To reason about global properties, the optimizer
must form "for-all-paths" facts. (Dominance being the easiest form of
this
generally.)
You worded the above as your interpretation of the spec. I agree your
interpretation is the sanest one.
Just to note, this is rather different than the "invariant.*" family.
In
particular, the invariant family requires the "start" as an argument
to the
"end" intrinsic.
I think this ambiguity should be cleared in the LRM, because today's
implicit assumption may be broken at any time.
I believe the existing implementation matches the semantics I specified
above. If you find a case where it doesn't, that's a bug.
I checked the stack coloring (the only real user of the lifetime markers),
and it seems to match this semantics.
This is not a theoretical question: clang can generate such cases. For
example, the following testcase:
struct X {
void doSomething();
char b[33];
};
void bar(X &);
void baz();
void test(int i) {
if (i==9) {
X x;
x.doSomething();
label:
bar(x);
} else {
baz();
if (i==0)
goto label;
}
}
Produces:
%struct.X = type { [33 x i8] }
define void @_Z4testi(i32 %i) {
entry:
%x = alloca %struct.X, align 1
%cmp = icmp eq i32 %i, 9
br i1 %cmp, label %if.then, label %if.else
if.then: ; preds = %entry
%0 = getelementptr inbounds %struct.X* %x, i64 0, i32 0, i64 0
call void @llvm.lifetime.start(i64 33, i8* %0)
call void @_ZN1X11doSomethingEv(%struct.X* %x)
br label %label
label: ; preds
%if.else.label_crit_edge, %if.then
%.pre-phi = phi i8* [ %.pre, %if.else.label_crit_edge ], [ %0, %if.then ]
call void @_Z3barR1X(%struct.X* dereferenceable(33) %x)
call void @llvm.lifetime.end(i64 33, i8* %.pre-phi)
br label %if.end3
if.else: ; preds = %entry
tail call void @_Z3bazv()
%cmp1 = icmp eq i32 %i, 0
br i1 %cmp1, label %if.else.label_crit_edge, label %if.end3
if.else.label_crit_edge: ; preds = %if.else
%.pre = getelementptr inbounds %struct.X* %x, i64 0, i32 0, i64 0
br label %label
if.end3: ; preds = %if.else, %label
ret void
}
Note that the path thru if.else.label_crit_edge has no lifetime start.
This seems fine to me. The optimizer can (soundly) conclude that %p is dead
after the "lifetime.end" (for the two instructions), and dead before
the
"lifetime.start" (for the *single* instruction in that basic block,
*not*
for the previous BB). This seems like the proper result for this example,
am I missing something?
With the clarification you made on the semantics, the above IR is correct,
but could be improved when clang generates it: the label_crit_edge block
should contain a lifetime.start for the alloca.
Philip
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20141105/3d4720dd/attachment.html>
Reasonably Related Threads
- [LLVMdev] lifetime.start/end clarification
- [LLVMdev] lifetime.start/end clarification
- [LLVMdev] Curiosity about transform changes under Sanitizers (Was: [PATCH] Disable branch folding with MemorySanitizer)
- [LLVMdev] Curiosity about transform changes under Sanitizers (Was: [PATCH] Disable branch folding with MemorySanitizer)
- [LLVMdev] Curiosity about transform changes under Sanitizers (Was: [PATCH] Disable branch folding with MemorySanitizer)