llvm dev - May 2008 - [LLVMdev] Troubling promotion of return value to Integer ...

Chris,

I did not quite understand the "The bad thing about ..." part of your
argument. I'm not sure which of the two scenarios are you comparing
(promoting in FrontEnd vs BackEnd) or (promotion to int vs i32)

 

Regardless, I agree with you and shap that promotions should take place
in the FrontEnd and this is my reason:

The standard allows calling a function without prototype and assumes
"int" return value; and I realize that this is the primary reason why
the return value is being promoted. This ties this promotion to int type
and not the size of any register in target, which in turn makes it a
language issue rather than code generation issue; hence FrontEnd must
take care of it.

 

Now for our port, things are different. In most (sane) ports, the target
provides an integer class for int... however, things are different in
our (insane) port. We only have an 8-bit data bus but we also want
16-bit int type. So this promotion will make char return values (which
are used heavily in many application in 8-bit environment) quite
inefficient. So we need a way to turn off this promotion all together
and deal with default function prototype in a different way (perhaps
issue a diagnostic ...)

 

Cheers

Ali

 

 
>The bad thing about doing this is that, on the caller side, we lose
information.  With the current approach, the caller knows that the value
is (for example) 8 >bits but sign or zero extended as appropriate.  This
allows the caller side to do optimizations based on this fact.  If all
return values were i32, we wouldn't >know that the top 24 bits were
sign/zero extended.  I think we can handle this by adding some new
attributes, but this is marginally ugly.
> 
>What do you think?
> 
>-Chris
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20080516/6df42317/attachment.html>

On May 16, 2008, at 11:12 AM, <Alireza.Moshtaghi at microchip.com>
<Alireza.Moshtaghi at microchip.com
 > wrote:
>
> Chris,
> I did not quite understand the “The bad thing about …” part of your  
> argument. I’m not sure which of the two scenarios are you comparing  
> (promoting in FrontEnd vs BackEnd) or (promotion to int vs i32)
Assume we make the change I suggested.  This means that this C  
function (on x86-32):

char foo() {
   char c = ...
   return c;
}

would compile to something like:

define i32 @foo() {
    ...
    %tmp = sext i8 ... to i32
    ret i32 %tmp
}

Since "char" is sign extend to 32 bits on this target, there would be
an explicit sign extension.  This is goodness.  The problem is that  
now you have a caller:

  ...
char bar() {
   char x = foo()
   return char;
}

This would get compiled (by the front-end to something like this:

define i32 @bar() {
   ; call
   %tmp = call i32 @foo()
   %x = trunc i32 %tmp to i8

   ; return
   %tmp2 = sext i8 to i32
   ret i32 %tmp2
}

The problem with this is that we now have a trunc+sext instruction  
that cannot be eliminated.  The loss here is that while foo returns an  
i32 value, we lost the fact that the top 25 bits all have the same  
value (i.e. that it is a sign extended 8-bit value).  Because of this,  
we can't eliminate the trunc+sext pair in bar, pessimizing code (and  
in a very common case!).  I am just saying that we should have some  
attribute (or something) on foo that indicates its result is actually  
sign extended, allowing the optimizer to zap the trunc+sext in bar.

> The standard allows calling a function without prototype and assumes  
> “int” return value; and I realize that this is the primary reason  
> why the return value is being promoted. This ties this promotion to  
> int type and not the size of any register in target, which in turn  
> makes it a language issue rather than code generation issue; hence  
> FrontEnd must take care of it.
Right, I agree this should be fixed.
>
> Now for our port, things are different. In most (sane) ports, the  
> target provides an integer class for int… however, things are  
> different in our (insane) port. We only have an 8-bit data bus but  
> we also want 16-bit int type. So this promotion will make char  
> return values (which are used heavily in many application in 8-bit  
> environment) quite inefficient. So we need a way to turn off this  
> promotion all together and deal with default function prototype in a  
> different way (perhaps issue a diagnostic …)
Sure.  The other good thing about exposing this extensions in the IR  
is that interprocedural optimizations can eliminate them.  This gives  
the optimizer the ability to actually eliminate the extensions and  
truncations completely.

-Chris
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20080516/a6dc03f5/attachment.html>

On Fri, 2008-05-16 at 11:42 -0700, Chris Lattner wrote:
> This would get compiled (by the front-end to something like this:
> 
> 
> define i32 @bar() {
>   ; call
>   %tmp = call i32 @foo()
>   %x = trunc i32 %tmp to i8
> 
> 
>   ; return
>   %tmp2 = sext i8 to i32
>   ret i32 %tmp2
> }
> 
> 
> The problem with this is that we now have a trunc+sext instruction
> that cannot be eliminated...
Chris:

In an attempt to avoid adding distraction, I withheld the following
thought earlier. It may be equivalent to your annotation idea, but I
want to throw it out in case it provokes something useful.

Extension and promotion is a peculiar case. If an

   %x = sext i8 %y to i32

has already been performed, then there is no harm (in the sense that no
value is changed) by executing it redundantly on the low field of the
result register, as in:

   %z = sext i8 %x to i32

I'm giving an input %x that is known to be an i32 here intentionally.

This prompts me to the following thought, which may not be helpful.
Perhaps we might introduce something like the following two
pseudo-instructions in the IR:

   resext   sign extend on a quantity that the front end asserts has
            already been sign extended.

   rezext   zero extend on a quantity that the front end asserts has
            already been zero extended.

These instructions serve to advise the caller-side optimizer that the
required extend has been done, which tells us what we need to know for
optimizations. If they inadvertently make it to the back end, they
peephole away as a NO-OP.

Since we are already trusting the front end to introduce the correct
extension in the callee, I don't see any harm in trusting it to advise
us that it did so at the caller return site. The outcome is certainly no
worse than a front end that simply generates IR that is wrong, and
omission of the advisory instruction merely results in loss of an
optimization opportunity rather than any error of computational
semantics.

Like I say, not sure if this is helpful.


shap

To me, this "optimization" problem doesn't seem to be a
consequence of
doing the promotion differently than what is currently being done in
llvm. 

Anyways, I don't agree that the information is completely lost.
Shouldn't an llvm pass be able to figure out if the truncated value is
coming from a function call, and since it is aware of calling
convention, it should be able to deduce that tmp2 can really take its
value from function call?

 

So the pass will modify 

 

define i32 @bar() {

  ; call

  %tmp = call i32 @foo()

  %x = trunc i32 %tmp to i8

 

  ; return

  %tmp2 = sext i8 to i32

  ret i32 %tmp2

}

 

To

 

define i32 @bar() {

  ; call

  %tmp = call i32 @foo()

  %tmp2 = %tmp

  %x = trunc i32 %tmp to i8

 

  ; return

  ret i32 %tmp2

}

 

Meanwhile, the FrontEnd is consistent with the calling convention and
produce the correct IR with necessary promotions.

 

Ali

 

 

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20080516/0c14573c/attachment.html>

Chris,

Regardless of the optimization problem that we had discussions before, I
think we all agreed that promotion of return value should take place in
the front-end...

Now I have a suggestion:

In the message below you laid out the suggested IR for "char foo()"
when
its return value is promoted to i32 in front-end.

You have applied the promotion both at the definition of function and
its return statement. This leaves no way for backend to differentiate
"char foo()" from "int foo()". 

Currently in llvm, promotion affects only the return value but function
definition is not promoted, and that is helpful because in LowerRET() I
can look at the return size from the function definition and
differentiate a promoted return statement from a non-promoted one and
accordingly do the desired lowering for my port.

I would like to suggest that when the promotion is done in the
Front-end, we do the same and only promote the return value and the
function definition does not get promoted:

So for:

 

char foo() {

  char c = ...

  return c;

} 

 

We will have:

 

define i8 @foo() {

   ...

   %tmp = sext i8 ... to i32

   ret i32 %tmp

} 

 

And for 

 

int foo() {

  char c = ...

  return c;

} 

 

We will have:

 

define i32 @foo() {

   ...

   %tmp = sext i8 ... to i32

   ret i32 %tmp

} 

 

Is this acceptable?

 

Cheers

Ali

________________________________

From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at cs.uiuc.edu]
On Behalf Of Chris Lattner
Sent: Friday, May 16, 2008 11:43 AM
To: LLVM Developers Mailing List
Subject: Re: [LLVMdev] Troubling promotion of return value to Integer
...

 

 

Assume we make the change I suggested.  This means that this C function
(on x86-32):

 

char foo() { 

  char c = ...

  return c;

}

 

would compile to something like:

 

define i32 @foo() {

   ...

   %tmp = sext i8 ... to i32

   ret i32 %tmp

} 

 

Since "char" is sign extend to 32 bits on this target, there would be
an
explicit sign extension.  This is goodness.  The problem is that now you
have a caller:

 

 ...

char bar() {

  char x = foo()

  return char;

}

 

This would get compiled (by the front-end to something like this:

 

define i32 @bar() {

  ; call

  %tmp = call i32 @foo()

  %x = trunc i32 %tmp to i8

 

  ; return

  %tmp2 = sext i8 to i32

  ret i32 %tmp2

}

 

The problem with this is that we now have a trunc+sext instruction that
cannot be eliminated.  The loss here is that while foo returns an i32
value, we lost the fact that the top 25 bits all have the same value
(i.e. that it is a sign extended 8-bit value).  Because of this, we
can't eliminate the trunc+sext pair in bar, pessimizing code (and in a
very common case!).  I am just saying that we should have some attribute
(or something) on foo that indicates its result is actually sign
extended, allowing the optimizer to zap the trunc+sext in bar.

 





The standard allows calling a function without prototype and assumes
"int" return value; and I realize that this is the primary reason why
the return value is being promoted. This ties this promotion to int type
and not the size of any register in target, which in turn makes it a
language issue rather than code generation issue; hence FrontEnd must
take care of it.

 

Right, I agree this should be fixed.





 

Now for our port, things are different. In most (sane) ports, the target
provides an integer class for int... however, things are different in
our (insane) port. We only have an 8-bit data bus but we also want
16-bit int type. So this promotion will make char return values (which
are used heavily in many application in 8-bit environment) quite
inefficient. So we need a way to turn off this promotion all together
and deal with default function prototype in a different way (perhaps
issue a diagnostic ...)

 

Sure.  The other good thing about exposing this extensions in the IR is
that interprocedural optimizations can eliminate them.  This gives the
optimizer the ability to actually eliminate the extensions and
truncations completely.

 

-Chris

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20080523/d9c741ba/attachment.html>