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

Sorry, clicked send by accident. It seems there's some background I'm
missing though. Can I read up on this "as-if" rule anywhere?

I was just saying this translation seems safe for word-sized or
smaller objects, since those could end up being allocated to registers
and such. My confusion is over larger object sizes. At what point
would the translation not be done, or would it always be done, even
when an object exceeds the addressable size on the target machine?

On a real machine, calling malloc with a large value will cause a real
program to fail. This translation would seem to make potentially
failing programs succeed. Seems counter-intuitive to me, but as I
said, perhaps I just need to read up on this "as-if" rule.

Sandro

On Fri, May 2, 2008 at 1:55 PM, Sandro Magi <naasking at gmail.com>
wrote:
>
> On Thu, May 1, 2008 at 6:54 PM, Chris Lattner <sabre at nondot.org>
wrote:
>  >
>  >  > I don't see how this could be true in general, without
either
>  >  > knowledge of the malloc implementation, which would be fine, or
>  >  > presuming knowledge of the target, which would not be fine. If
>  >  > "malloc(sizeof(int))" were changed to
"malloc(3245677423)", would it
>  >  > still be eliminated?
>  >
>  >  Would it cause your head to explode if you knew that llvm optimizes
this:
>  >
>  >  static char* G;
>  >  void foo() {
>  >    G = malloc(sizeof(char));
>  >  }
>  >  char get() { return *G; }
>  >  void set(char x) { *G = x; }
>  >
>  >  into this (note the lack of malloc):
>  >
>  >  @G.body = internal global i8 undef              ; <i8*>
[#uses=2]
>  >  define i8 @get() signext nounwind  {
>  >  entry:
>  >         %tmp2 = load i8* @G.body, align 1               ; <i8>
[#uses=1]
>  >         ret i8 %tmp2
>  >  }
>  >  define void @set(i8 signext  %x) nounwind  {
>  >  entry:
>  >         store i8 %x, i8* @G.body, align 1
>  >         ret void
>  >  }
>  >  define void @foo() nounwind  {
>  >  entry:
>  >         ret void
>  >  }
>  >
>  >  ?
>  >
>  >  This is safe even without "whole program" information.  I
love the as-if
>  >  rule ;-)
>
>  No, that seems perfectly reasonable (assuming I understand the
>  translation), but only because char is so small. This optimization
>  seems reasonable when the object is of word size or smaller, as this
>  may simply
>
>  Sandro
>

On Fri, May 2, 2008 at 2:07 PM, Sandro Magi <naasking at gmail.com>
wrote:
> Sorry, clicked send by accident. It seems there's some background
I'm
>  missing though. Can I read up on this "as-if" rule anywhere?
>
>From the latest C++0x draft (n2588), 1.9/1 [intro.execution]:
"The semantic descriptions in this International Standard define a
parameterized nondeterministic abstract machine. This International
Standard places no requirement on the structure of conforming
implementations. In particular, they need not copy or emulate the
structure of the abstract machine. Rather, conforming implementations
are required to emulate (only) the observable behavior of the abstract
machine as explained below.*"
"* This provision is sometimes called the "as-if" rule, because
an
implementation is free to disregard any requirement of this
International Standard as long as the result is as if the requirement
had been obeyed, as far as can be determined from the observable
behavior of the program. For instance, an actual implementation need
not evaluate part of an expression if it can deduce that its value is
not used and that no side effects affecting the observable behavior of
the program are produced."
(C++03 contains the same text)

I suppose the most important issue is what constitutes "observable
behavior".

On May 2, 2008, at 2:23 PM, me22 wrote:
[...]
> I suppose the most important issue is what constitutes "observable  
> behavior".
1.9/6:
«The observable behavior of the abstract machine is its sequence of  
reads and writes to volatile data and calls to library
I/O functions. [ Footnote 6: An implementation can offer additional  
library I/O functions as an extension. Implementations that do so  
should treat calls to those functions as “observable behavior” as  
well. ]»

(I wish the C standard were as clear on this topic.)

	Daveed

On Fri, 2 May 2008, Sandro Magi wrote:
> I was just saying this translation seems safe for word-sized or
> smaller objects, since those could end up being allocated to registers
> and such. My confusion is over larger object sizes. At what point
> would the translation not be done, or would it always be done, even
> when an object exceeds the addressable size on the target machine?
>
> On a real machine, calling malloc with a large value will cause a real
> program to fail. This translation would seem to make potentially
> failing programs succeed. Seems counter-intuitive to me, but as I
> said, perhaps I just need to read up on this "as-if" rule.
In practice, calling malloc of any size could fail.  We do this up to 2K 
allocations, on the idea that we don't want to bloat global data in the 
case when the code is not actually reachable.  This transformation is safe 
because the compiler can assume the malloc is successful.

-Chris

> Sandro
>
> On Fri, May 2, 2008 at 1:55 PM, Sandro Magi <naasking at gmail.com>
wrote:
>>
>> On Thu, May 1, 2008 at 6:54 PM, Chris Lattner <sabre at
nondot.org> wrote:
>> >
>> > > I don't see how this could be true in general, without
either
>> > > knowledge of the malloc implementation, which would be fine,
or
>> > > presuming knowledge of the target, which would not be fine.
If
>> > > "malloc(sizeof(int))" were changed to
"malloc(3245677423)", would it
>> > > still be eliminated?
>> >
>> >  Would it cause your head to explode if you knew that llvm
optimizes this:
>> >
>> >  static char* G;
>> >  void foo() {
>> >    G = malloc(sizeof(char));
>> >  }
>> >  char get() { return *G; }
>> >  void set(char x) { *G = x; }
>> >
>> >  into this (note the lack of malloc):
>> >
>> >  @G.body = internal global i8 undef              ; <i8*>
[#uses=2]
>> >  define i8 @get() signext nounwind  {
>> >  entry:
>> >         %tmp2 = load i8* @G.body, align 1               ;
<i8> [#uses=1]
>> >         ret i8 %tmp2
>> >  }
>> >  define void @set(i8 signext  %x) nounwind  {
>> >  entry:
>> >         store i8 %x, i8* @G.body, align 1
>> >         ret void
>> >  }
>> >  define void @foo() nounwind  {
>> >  entry:
>> >         ret void
>> >  }
>> >
>> >  ?
>> >
>> >  This is safe even without "whole program" information. 
I love the as-if
>> >  rule ;-)
>>
>>  No, that seems perfectly reasonable (assuming I understand the
>>  translation), but only because char is so small. This optimization
>>  seems reasonable when the object is of word size or smaller, as this
>>  may simply
>>
>>  Sandro
>>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
-Chris

-- 
http://nondot.org/sabre/
http://llvm.org/