llvm dev - Jun 2008 - [LLVMdev] optimization assumes malloc return is non-null

On Wednesday 30 April 2008 21:21, Chris Lattner wrote:
> If LLVM is able to eliminate all users of the malloc assuming the
> malloc succeeded (as in this case), then it is safe to assume the malloc
> returned success.
Ah, I missed this bit.  I didn't see that the result of malloc was not used
outside the if test.

But is the if test considered a "use?"  If so, it's a use in the
context of
success or failure, so how can LLVM assume success?

Your argument seems circular:

1. LLVM can't assume malloc success

2. If, assuming malloc success, LLVM can eliminate all uses, the malloc
   becomes dead.

3. LLVM can eliminate the dead malloc.

4. Since the malloc was eliminated under assumption of success, the if test 
   becomes dead code and we can assume the malloc succeeded.

Perhaps the trouble is that your statement, "If LLVM is able to eliminate
all
users of the malloc assuming the malloc succeeded," is ambiguous.  Do
you mean that LLVM assumes the malloc succeeded and then tries to eliminate 
all users by making use of that assumption or that it tries to eliminate all 
users that are in a context where malloc is assumed to have succeeded (for 
example the "else" of a check for malloc failure)?  

If the former, it's a circular argument, if the latter, then what about the 
use in the if test, which is in a context where we don't know whether the 
malloc succeeded or not?

Just trying to get some clarity.

                                                  -Dave

On Thu, 2008-05-01 at 12:00 -0500, David Greene wrote:
> On Wednesday 30 April 2008 21:21, Chris Lattner wrote:
> 
> > If LLVM is able to eliminate all users of the malloc assuming the
> > malloc succeeded (as in this case), then it is safe to assume the
malloc
> > returned success.
> 
> Ah, I missed this bit.  I didn't see that the result of malloc was not
used
> outside the if test.
> 
> But is the if test considered a "use?"  If so, it's a use in
the context of
> success or failure, so how can LLVM assume success?
Small correction. The pivotal issue isn't "use", it is
"capture". In
this case, the value returned by malloc is not bound to any variable
that survives, so there is no capture of the return value.
> 1. LLVM can't assume malloc success
I was confused about this too. LLVM actually *can* assume malloc success
in this case, using any of several arguments that came up in my exchange
with Daveed.

What I do not know is *which* of these justifications (or some variant)
the optimizer is presently exploiting. Perhaps Chris can clarify that
for both of us.


shap

On Thu, May 1, 2008 at 12:14 PM, Jonathan S. Shapiro <shap at eros-os.com>
wrote:
>  > 1. LLVM can't assume malloc success
>
>  I was confused about this too. LLVM actually *can* assume malloc success
>  in this case, using any of several arguments that came up in my exchange
>  with Daveed.
>
>  What I do not know is *which* of these justifications (or some variant)
>  the optimizer is presently exploiting. Perhaps Chris can clarify that
>  for both of us.
So a small nit-pick here, if the transformation is unsafe, the step
that is unsafe is
call malloc -> malloc instruction.

The malloc instruction doesn't have to have a 1:1 mapping to c malloc
semantics and in fact this is not claimed in the language reference.
So if llvm wants to eliminate malloc in this instance that is
permissable under it's (under-specified) semantics.  If the malloc
instruction doesn't actually follow exactly the C standard, then it is
the lowering of malloc calls, when compiling C, to malloc instructions
that is at fault, not the subsequent removal of it.

Andrew

On Thursday 01 May 2008 19:14, Jonathan S. Shapiro
wrote:
> On Thu, 2008-05-01 at 12:00 -0500, David Greene wrote:
> > On Wednesday 30 April 2008 21:21, Chris Lattner wrote:
> > 
> > > If LLVM is able to eliminate all users of the malloc assuming the
> > > malloc succeeded (as in this case), then it is safe to assume the
malloc
> > > returned success.
> > 
> > Ah, I missed this bit.  I didn't see that the result of malloc was
not used
> > outside the if test.
> > 
> > But is the if test considered a "use?"  If so, it's a
use in the context of
> > success or failure, so how can LLVM assume success?
> 
> Small correction. The pivotal issue isn't "use", it is
"capture". In
> this case, the value returned by malloc is not bound to any variable
> that survives, so there is no capture of the return value.
> 
> > 1. LLVM can't assume malloc success
> 
> I was confused about this too. LLVM actually *can* assume malloc success
> in this case, using any of several arguments that came up in my exchange
> with Daveed.
Under this reasoning, it can equally assume malloc *failure*.

Under this assumption, it can eliminate malloc exactly as in
your arguments and then

int main(int argc, char** argv){
   if(malloc(sizeof(int)) == NULL){ return 0; }
   else{ return 1; }
}

is optimized to returning 0.

Which leads us to the same programs being validly optimized to returning 0
and to returning 1. Which is an observable (and nonsensical) behavior.
--
vda