The LRM (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: <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 (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 llvm.cs.uiuc.edu > 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 > > (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 llvm.cs.uiuc.edu > > lists.cs.uiuc.edu/mailman/listinfo/llvmdev > > > > _______________________________________________ > cfe-dev mailing list > cfe-dev at cs.uiuc.edu > 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 > (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 llvm.cs.uiuc.edu > 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 > (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 llvm.cs.uiuc.edu > 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 > > (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 llvm.cs.uiuc.edu > > 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 (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 llvm.cs.uiuc.edu > lists.cs.uiuc.edu/mailman/listinfo/llvmdev > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <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 (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 llvm.cs.uiuc.edu lists.cs.uiuc.edu/mailman/listinfo/llvmdev -------------- next part -------------- An HTML attachment was scrubbed... URL: <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 > (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: <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: <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 (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: <lists.llvm.org/pipermail/llvm-dev/attachments/20141105/3d4720dd/attachment.html>