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

On May 20, 2008, at 2:16 PM, <Alireza.Moshtaghi at microchip.com>
<Alireza.Moshtaghi at microchip.com
 > wrote:
>
>> Ok, I'm not sure what issue you mean.  Can you restate?
>
> I'm referring to your statement (below) where you say "there needs
> to be
> some attribute (or something) on foo".
Ok.
> What I don't understand is I
> don't know who would be setting this attribute?
The front-end should set this.  Further, as an optimization, the  
optimizer could also infer cases where it is safe to set this.  For  
example, if the C programmer defined a function to return int, and  
always return a value whose top 24 bits are sign extended, the  
optimizer could apply the attribute if it were smart enough.
> Whatever you do, if you
> consider caller and callee are in different translation units, then  
> all
> that we can know in the caller is whether the return value has been
> extended or not. But we don't know if it is sign extended or zero
> extended.
I think this is where the confusion is.  The ABI of many (all?)  
platforms specifies that the return value is *required* to be properly  
sign/zero extended based on the C type.  For example, if you have:

extern signed char X();
int Y() { return X(); }

The ABI *guarantees* that the implementation of "X" returns a value  
properly sign extended from i8.  If there abi specifies that the  
result comes back in an i32 register, then this means that the top 25  
bits are known to match.  Capturing this information in the IR is  
important, because it otherwise unsafe to assume that this is the case.

The optimizer and code generator has logic (see  
SelectionDAG::ComputeNumSignBits) that propagates around the number of  
sign bits that a computation is known to have.  This allows it to  
eliminate redundant sign extension instructions, and this is very  
important for common RISCy systems.

Since the C ABI guarantees that "X" returns a sign extended value  
here, it is safe to assume it in callers, even if you can't see the  
implementation of the callee.
> 	"
> 	define i32 @bar() {
>  	; call
>  	%tmp = call i32 @foo()
>  	%x = trunc i32 %tmp to i8
>
>
>  	; return
>  	%tmp2 = sext i8 to i32
>  	ret i32 %tmp2
> 	}
>
What I'm getting at with this, is that if we compiled foo to include  
an attribute "sign_ext_from_i8" or something, then we could capture  
this information.  It would be ugly, but acceptable to define:

   sign_ext_from_i8, sign_ext_from_i16
   zero_ext_from_i8, zero_ext_from_i16

And have the C front-end generate these.  Given this, the optimizer  
and codegen can continue doing their optimizations, and we can  
eventually eliminate the existing sext/zext attributes.

Does this make sense?

-Chris

Chris,
I see, so in deed the front-end sets the attributes on the declaration
of the called function; which in theory is also available to the caller
through the CALL node. Now here is what I think:
I agree that 4 attributes are a bit ugly. I think we can only get away
with 2 attributes to signify sign extension or zero extension. 
Currently the front end does not promote the function declaration; I
hope we don't change this...
The length of extension can be inferred from the CALL SDNode by
following the links all the way to the definition of callee in Function
class.
All that is needed is to add some kind of sign attribute to the
definition of callee function which will be set by the front-end and
eventually saved in Function class. Two llvm methods (probably in
SelectionDAG class) would be responsible for retrieving this
information. We pass to them the SDNode of CALL to callee. Knowing the
ABI/ calling convention, these two methods can infer the size and sign
extension information from function definition information.
So:

signed char g(...);
void foo(){
	x = g(...);
}

Would translate to:

define void @foo(){
Entry:
	%call = call i32 @g(...)
	...
}
declare signed i8 @g(...)

Alternatively (and this may be quite a change) to identify sign
information, we can add new SimpleValueTypes (u1, u8, u16, ...) to
signify unsigned values in addition to (i1, i8, i16, ...) which are
signed values. 
Then the front-end can define 

unsigned char ug(...); 
as:  declare u8 @ug(...)
where DAG.isReturnValueSignExtended(...) returns false

and 

signed char sg(...); 
as:   declare i8 @sg(...)
where DAG.isReturnValueSignExtended(...) returns true

In both cases DAG.getReturnValueRegisterSizeInBits(...) returns 32 (on a
32 bit architecture)

The caveat here is when we don't have a prototype for callee in which
case "int ()" is considered, hence known values are returned and no
optimization will take effect.

Regards.
Ali.

> -----Original Message-----
> From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at
cs.uiuc.edu]
On
> Behalf Of Chris Lattner
> Sent: Friday, May 23, 2008 3:28 PM
> To: LLVM Developers Mailing List
> Subject: Re: [LLVMdev] Troubling promotion of return value to Integer
...
> 
> 
> On May 20, 2008, at 2:16 PM, <Alireza.Moshtaghi at microchip.com>
> <Alireza.Moshtaghi at microchip.com
>  > wrote:
> 
> >
> >> Ok, I'm not sure what issue you mean.  Can you restate?
> >
> > I'm referring to your statement (below) where you say "there
needs
> > to be
> > some attribute (or something) on foo".
> 
> Ok.
> 
> > What I don't understand is I
> > don't know who would be setting this attribute?
> 
> The front-end should set this.  Further, as an optimization, the
> optimizer could also infer cases where it is safe to set this.  For
> example, if the C programmer defined a function to return int, and
> always return a value whose top 24 bits are sign extended, the
> optimizer could apply the attribute if it were smart enough.
> 
> > Whatever you do, if you
> > consider caller and callee are in different translation units, then
> > all
> > that we can know in the caller is whether the return value has been
> > extended or not. But we don't know if it is sign extended or zero
> > extended.
> 
> I think this is where the confusion is.  The ABI of many (all?)
> platforms specifies that the return value is *required* to be properly
> sign/zero extended based on the C type.  For example, if you have:
> 
> extern signed char X();
> int Y() { return X(); }
> 
> The ABI *guarantees* that the implementation of "X" returns a
value
> properly sign extended from i8.  If there abi specifies that the
> result comes back in an i32 register, then this means that the top 25
> bits are known to match.  Capturing this information in the IR is
> important, because it otherwise unsafe to assume that this is the
case.
> 
> The optimizer and code generator has logic (see
> SelectionDAG::ComputeNumSignBits) that propagates around the number of
> sign bits that a computation is known to have.  This allows it to
> eliminate redundant sign extension instructions, and this is very
> important for common RISCy systems.
> 
> Since the C ABI guarantees that "X" returns a sign extended value
> here, it is safe to assume it in callers, even if you can't see the
> implementation of the callee.
> 
> > 	"
> > 	define i32 @bar() {
> >  	; call
> >  	%tmp = call i32 @foo()
> >  	%x = trunc i32 %tmp to i8
> >
> >
> >  	; return
> >  	%tmp2 = sext i8 to i32
> >  	ret i32 %tmp2
> > 	}
> >
> 
> What I'm getting at with this, is that if we compiled foo to include
> an attribute "sign_ext_from_i8" or something, then we could
capture
> this information.  It would be ugly, but acceptable to define:
> 
>    sign_ext_from_i8, sign_ext_from_i16
>    zero_ext_from_i8, zero_ext_from_i16
> 
> And have the C front-end generate these.  Given this, the optimizer
> and codegen can continue doing their optimizations, and we can
> eventually eliminate the existing sext/zext attributes.
> 
> Does this make sense?
> 
> -Chris
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

On May 27, 2008, at 3:33 PM, <Alireza.Moshtaghi at microchip.com>
<Alireza.Moshtaghi at microchip.com
 > wrote:
> Chris,
> I see, so in deed the front-end sets the attributes on the declaration
> of the called function; which in theory is also available to the  
> caller
> through the CALL node.
Right.
> Now here is what I think:
> I agree that 4 attributes are a bit ugly. I think we can only get away
> with 2 attributes to signify sign extension or zero extension.
> Currently the front end does not promote the function declaration; I
> hope we don't change this...
> The length of extension can be inferred from the CALL SDNode by
> following the links all the way to the definition of callee in  
> Function
> class.
In many cases that is true, but for indirect calls (calls through a  
function pointer) it isn't.
> All that is needed is to add some kind of sign attribute to the
> definition of callee function which will be set by the front-end and
> eventually saved in Function class.
Sure.  Adding an attribute is what we need to do.  To handle the  
indirect call case, llvm puts attributes both on the function  
definitions and on the calls to those functions.
> Two llvm methods (probably in
> SelectionDAG class) would be responsible for retrieving this
> information. We pass to them the SDNode of CALL to callee. Knowing the
> ABI/ calling convention, these two methods can infer the size and sign
> extension information from function definition information.
> So:
>
> signed char g(...);
> void foo(){
> 	x = g(...);
> }
>
> Would translate to:
>
> define void @foo(){
> Entry:
> 	%call = call i32 @g(...)
> 	...
> }
> declare signed i8 @g(...)
Ok.  We already have this, with the 'signext' attribute.  This code:

signed char g();
signed char foo(){
	return g();
}

compiles into:

define i8 @foo() signext nounwind  {
entry:
	%tmp1 = tail call i8 (...)* @g( ) signext nounwind 		; <i8> [#uses=1]
	ret i8 %tmp1
}

declare i8 @g(...) signext

Note that the 'signext' attribute is on all of foo, the call to G, and  
the G declaration itself.
> In both cases DAG.getReturnValueRegisterSizeInBits(...) returns 32  
> (on a
> 32 bit architecture)
>
> The caveat here is when we don't have a prototype for callee in which
> case "int ()" is considered, hence known values are returned and
no
> optimization will take effect.
The IR is already capturing this much information.  If you want to go  
this route, it seems simple to parameterize (in target data?) the size  
of int, and have the code generator extend to that size, instead of  
forcing extension to i32.

-Chris

On 2008-05-23, at 18:27, Chris Lattner wrote:
> What I'm getting at with this, is that if we compiled foo to include  
> an attribute "sign_ext_from_i8" or something, then we could
capture
> this information.  It would be ugly, but acceptable to define:
>
>   sign_ext_from_i8, sign_ext_from_i16
>   zero_ext_from_i8, zero_ext_from_i16
>
> And have the C front-end generate these.  Given this, the optimizer  
> and codegen can continue doing their optimizations, and we can  
> eventually eliminate the existing sext/zext attributes.

Although at some greater memory expense, maybe this could be  
generalized to a known bit mask and known bit values (for zext) and  
number of sign bits (for sext). Could probably be abbreviated fairly  
efficient in bitcode, though.

Seems to fall into a recurring pattern of memoizing analysis results  
as attributes on IR.

— Gordon