On 30 June 2015 at 14:30, Nuno Lopes <nunoplopes at sapo.pt> wrote:> Interesting. Could you give an example why knowing a function will >>> halt is >>> essential for the heap-to-stack conversion? >>> >> >> The key situation you need to establish in order to do heap-to-stack >> conversion, is that you can see the calls to free (or realloc, etc.) along >> all control-flow paths. If you can, then you can perform the conversion >> (because any additional calls to free that you can't observe would lead to >> a double free, and thus undefined behavior). Thus, if we have this >> situation: >> >> void bar(int *a); >> void foo() { >> int *a = (int*) malloc(sizeof(int)*40); >> bar(a); >> free(a); >> } >> >> we can perform heap-to-stack conversion iff we know that bar(int *) >> always returns normally. If it never returns (perhaps by looping >> indefinitely) then it might capture the pointer, pass it off to some other >> thread, and that other thread might call free() (or it might just call >> free() itself before looping indefinitely). In short, we need to know >> whether the call to free() after the call to bar() is dead. If we know that >> it is reached, then we can perform heap-to-stack conversion. Also worth >> noting is that because we unconditionally free(a) after the call to bar(a), >> it would not be legal for bar(a) to call realloc on a (because if realloc >> did reallocate the buffer we'd end up freeing it twice when bar(a) did >> eventually return). >> > > I see, thanks! > Your argument is that knowing that bar returns implies that 'a' cannot be > captured or reallocated, otherwise it would be UB. Makes sense, yes. >I'm afraid it's worse than that. void caller() { int *ptr = malloc(sizeof(int)); callee(ptr); free(ptr); } void callee(int *ptr) { if (...) { free(ptr); log("get critical log message out to the humans, maybe my final message will be the last hint they need to finally resolve the bugs inside myself"); } } C and C++ do permit undefined behaviour to have interactions backwards in time. In essence, knowing that UB must happen later can cause impossible things to happen now. However, LLVM offers an implementation-defined guarantee that no UB occurs until the earliest instruction where it occurs. Your reasoning that we can't have a free in the callee because we'd hit a double-free (and hence UB) in the caller is not sufficient to perform heap-to-stack transform with that guarantee, because it will move the UB sooner to the free() in the callee. That violates our implementation guarantee that the log message will be emitted (because we'll have already entered UB-land). The alternatives are to define double-free as not entering full UB (similar to poison, but we also have problems to solve with load, store, call, branch on value computed through signed overflow, etc.), or to remove the guarantee that the log message will be emitted. Nick -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150701/c376590e/attachment.html>
----- Original Message -----> From: "Nick Lewycky" <nlewycky at google.com> > To: "Nuno Lopes" <nunoplopes at sapo.pt> > Cc: "Hal Finkel" <hfinkel at anl.gov>, "LLVM Developers Mailing List" <llvmdev at cs.uiuc.edu>, "Sanjoy Das" > <sanjoy at playingwithpointers.com>, "Jeremy Lakeman" <Jeremy.Lakeman at gmail.com> > Sent: Wednesday, July 1, 2015 5:15:31 PM > Subject: Re: [LLVMdev] readonly and infinite loops > > > > > On 30 June 2015 at 14:30, Nuno Lopes < nunoplopes at sapo.pt > wrote: > > > > > > > Interesting. Could you give an example why knowing a function will > halt is > essential for the heap-to-stack conversion? > > The key situation you need to establish in order to do heap-to-stack > conversion, is that you can see the calls to free (or realloc, etc.) > along all control-flow paths. If you can, then you can perform the > conversion (because any additional calls to free that you can't > observe would lead to a double free, and thus undefined behavior). > Thus, if we have this situation: > > void bar(int *a); > void foo() { > int *a = (int*) malloc(sizeof(int)*40); > bar(a); > free(a); > } > > we can perform heap-to-stack conversion iff we know that bar(int *) > always returns normally. If it never returns (perhaps by looping > indefinitely) then it might capture the pointer, pass it off to some > other thread, and that other thread might call free() (or it might > just call free() itself before looping indefinitely). In short, we > need to know whether the call to free() after the call to bar() is > dead. If we know that it is reached, then we can perform > heap-to-stack conversion. Also worth noting is that because we > unconditionally free(a) after the call to bar(a), it would not be > legal for bar(a) to call realloc on a (because if realloc did > reallocate the buffer we'd end up freeing it twice when bar(a) did > eventually return). > > I see, thanks! > Your argument is that knowing that bar returns implies that 'a' > cannot be captured or reallocated, otherwise it would be UB. Makes > sense, yes. > > > > I'm afraid it's worse than that. > > > void caller() { > int *ptr = malloc(sizeof(int)); > callee(ptr); > free(ptr); > } > > > void callee(int *ptr) { > if (...) { > free(ptr); > log("get critical log message out to the humans, maybe my final > message will be the last hint they need to finally resolve the bugs > inside myself"); > } > } > > > > C and C++ do permit undefined behaviour to have interactions > backwards in time. In essence, knowing that UB must happen later can > cause impossible things to happen now. However, LLVM offers an > implementation-defined guarantee that no UB occurs until the > earliest instruction where it occurs. > > Your reasoning that we can't have a free in the callee because we'd > hit a double-free (and hence UB) in the caller is not sufficient to > perform heap-to-stack transform with that guarantee, because it will > move the UB sooner to the free() in the callee. That violates our > implementation guarantee that the log message will be emitted > (because we'll have already entered UB-land). > > The alternatives are to define double-free as not entering full UB > (similar to poison, but we also have problems to solve with load, > store, call, branch on value computed through signed overflow, > etc.), or to remove the guarantee that the log message will be > emitted.We'll need to loosen that guarantee. However, for the case you've highlighted, the fact that the routine performs I/O is sufficient to conclude that it might not always return normally in some finite period of time. The C++ specification guarantees only that the function will eventually return (terminate), or perform I/O, or access a volatile variable, or perform some synchronization/atomic operation. Since your function might perform I/O, it cannot be marked as always returning normally, and so we can't perform the conversion. The critical case here is really a constructor that fills in some structure members and then returns (although some loop may be involved if there is some array to be initialized). -Hal> > > Nick >-- Hal Finkel Assistant Computational Scientist Leadership Computing Facility Argonne National Laboratory
Here's a fun spin on this same topic (I can't file a bug at this
moment since llvm.org is down).
Consider:
define i32 @x(i32* %x, i1* %y) {
entry:
br label %loop
loop:
%v = phi i32 [ 0 , %entry ], [ %v.inc, %exit.inner ], [ %v, %loop ]
%c = load volatile i1, i1* %y
br i1 %c, label %exit.inner, label %loop
exit.inner:
%c1 = load volatile i1, i1* %y
%x.val = load i32, i32* %x
%v.inc = add i32 %v, %x.val
br i1 %c1, label %exit.real, label %loop
exit.real:
ret i32 %v
}
Now if %c is false every time, %x is never dereferenced. Since this
is an infinitely looping program that does a volatile load in every
iteration, it is well defined (going by what Hal said).
However, opt -licm transforms this to
; ModuleID = '/Users/sanjoy/tmp/inf.ll'
define i32 @x(i32* %x, i1* %y) {
entry:
%x.val = load i32, i32* %x
br label %loop.outer
loop.outer: ; preds = %exit.inner, %entry
%v.ph = phi i32 [ %v.inc, %exit.inner ], [ 0, %entry ]
br label %loop
loop: ; preds = %loop.outer, %loop
%c = load volatile i1, i1* %y
br i1 %c, label %exit.inner, label %loop
exit.inner: ; preds = %loop
%c1 = load volatile i1, i1* %y
%v.inc = add i32 %v.ph, %x.val
br i1 %c1, label %exit.real, label %loop.outer
exit.real: ; preds = %exit.inner
%v.ph.lcssa = phi i32 [ %v.ph, %exit.inner ]
ret i32 %v.ph.lcssa
}
where it unconditionally dereferences %x, effectively introducing UB
if %x is not dereferenceable.
The bug is in isGuaranteedToExecute. It assumes that if an
instruction dominates all the loop exits then it will always be
executed by the loop "on its way out". But there may never be a way
out of the loop.
-- Sanjoy