[fwd] Re: LLVM Compiler Infrastructure

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

[fwd] Re: LLVM Compiler Infrastructure

Misha Brukman-2
Hi, Yiping!

I am not sure of the answer to your question, but I am forwarding it to
the LLVMdev list where I am sure someone will be able to answer you.

Please send development questions directly to LLVMdev and you will get a
response quicker, as it is read by many LLVM developers.

----- Forwarded message from Yiping Fan <[hidden email]> -----

Date: Mon, 31 Oct 2005 17:20:24 -0800
From: "Yiping Fan" <[hidden email]>
To: "Misha Brukman" <[hidden email]>, "guoling han" <[hidden email]>,
        <[hidden email]>, "'Zhiru Zhang'" <[hidden email]>
Cc: "Brian Gaeke" <[hidden email]>
Subject: Re: LLVM Compiler Infrastructure

Hi Misha,
    How are you doing recently? It has been long time since the last email we exchanged.
We used your LLVM compiler in our xPilot behavioral synthesis system, and made great
progress, thanks to your great job.
   Now we got a small but annoying problem. When we get the following C code to llvm-gcc,

short test(int x) {
        return (short) (x >> 10);
}

   It will generate the following LLVM code:

; ModuleID = 'test.bc'
target endian = little
target pointersize = 32
target triple = "i686-pc-linux-gnu"
deplibs = [ "c", "crtend" ]

implementation   ; Functions:

short %test(int %x) {
entry:
        %x = cast int %x to uint                ; <uint> [#uses=1]
        %tmp.2 = shr uint %x, ubyte 10          ; <uint> [#uses=1]
        %tmp.3 = cast uint %tmp.2 to short              ; <short> [#uses=1]
        ret short %tmp.3
}

Basically, LLVM frontend will first convert an integer to unsigned integer, and then do shifting.
It seems that this conversion often occurs for SHIFTING operations. Although it is correct for 32-bit
general purpose processor, it does not fit well for hardware synthesis, since we need
to use wider components (up to 32-bit) to implement these operations, otherwise we may lose sign flag.
Our favorite LLVM code is that without (or with very few) CAST, and doing the SHR directly for the signed integers.

So our question is that do you know there is any option in LLVM to disable this kind of cast-to-unsigned
code generation?

Thank you very much.

-Yiping Fan
UCLA Computer Science Department
4651 Boelter Hall
503 Hilgard Ave, Los Angeles, CA 90095
Tel: 310-206-5449
Email: [hidden email]
WWW: http://ballade.cs.ucla.edu/~fanyp

----- End forwarded message -----

--
Misha Brukman :: http://misha.brukman.net :: http://llvm.cs.uiuc.edu

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: [fwd] Re: LLVM Compiler Infrastructure

Robert L. Bocchino Jr.
I would like to know the answer to this too.  One of the optimization passes does this, but I don't know which.  If you run gccas with -debug-pass=Arguments, it will spit out all the optimizations that it runs.  You can do a binary search on these optimizations to figure out which one causes this transformation.  Then you can try to disable it, but you may have to hack on the optimization pass itself.

If you figure out how to do this, please let me know!

Rob

On Nov 1, 2005, at 3:09 PM, Misha Brukman wrote:

Hi, Yiping!

I am not sure of the answer to your question, but I am forwarding it to
the LLVMdev list where I am sure someone will be able to answer you.

Please send development questions directly to LLVMdev and you will get a
response quicker, as it is read by many LLVM developers.

----- Forwarded message from Yiping Fan <[hidden email]> -----

Date: Mon, 31 Oct 2005 17:20:24 -0800
From: "Yiping Fan" <[hidden email]>
To: "Misha Brukman" <[hidden email]>, "guoling han" <[hidden email]>,
        <[hidden email]>, "'Zhiru Zhang'" <[hidden email]>
Cc: "Brian Gaeke" <[hidden email]>
Subject: Re: LLVM Compiler Infrastructure

Hi Misha, 
    How are you doing recently? It has been long time since the last email we exchanged.
We used your LLVM compiler in our xPilot behavioral synthesis system, and made great
progress, thanks to your great job. 
   Now we got a small but annoying problem. When we get the following C code to llvm-gcc,

short test(int x) {
        return (short) (x >> 10);
}

   It will generate the following LLVM code:

; ModuleID = 'test.bc'
target endian = little
target pointersize = 32
target triple = "i686-pc-linux-gnu"
deplibs = [ "c", "crtend" ]

implementation   ; Functions:

short %test(int %x) {
entry:
        %x = cast int %x to uint                ; <uint> [#uses=1]
        %tmp.2 = shr uint %x, ubyte 10          ; <uint> [#uses=1]
        %tmp.3 = cast uint %tmp.2 to short              ; <short> [#uses=1]
        ret short %tmp.3
}

Basically, LLVM frontend will first convert an integer to unsigned integer, and then do shifting. 
It seems that this conversion often occurs for SHIFTING operations. Although it is correct for 32-bit
general purpose processor, it does not fit well for hardware synthesis, since we need 
to use wider components (up to 32-bit) to implement these operations, otherwise we may lose sign flag. 
Our favorite LLVM code is that without (or with very few) CAST, and doing the SHR directly for the signed integers. 

So our question is that do you know there is any option in LLVM to disable this kind of cast-to-unsigned 
code generation?

Thank you very much.

-Yiping Fan
UCLA Computer Science Department 
4651 Boelter Hall 
503 Hilgard Ave, Los Angeles, CA 90095
Tel: 310-206-5449 

----- End forwarded message -----

-- 

_______________________________________________
LLVM Developers mailing list

Robert L. Bocchino Jr.

Ph.D. Student, Computer Science

University of Illinois, Urbana-Champaign



_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: [fwd] Re: LLVM Compiler Infrastructure

Chris Lattner
In reply to this post by Misha Brukman-2

>   Now we got a small but annoying problem. When we get the following C
> code to llvm-gcc,
>
> short test(int x) {
>        return (short) (x >> 10);
> }
>
>   It will generate the following LLVM code:
> short %test(int %x) {
>        %x = cast int %x to uint                ; <uint> [#uses=1]
>        %tmp.2 = shr uint %x, ubyte 10          ; <uint> [#uses=1]
>        %tmp.3 = cast uint %tmp.2 to short              ; <short> [#uses=1]
>        ret short %tmp.3
> }

ok.

> Basically, LLVM frontend will first convert an integer to unsigned
> integer, and then do shifting. It seems that this conversion often
> occurs for SHIFTING operations.

The cast from 'int' to 'uint' changes the semantics of the shift from
being an arithmetic shift to a logical shift.

> So our question is that do you know there is any option in LLVM to
> disable this kind of cast-to-unsigned code generation?

No.

I'm not sure exactly why you don't like the code above, but here's the
basic idea that we're following:

1. All code generators have to support all operations, no exceptions.  The
    above code should *work* for you, no matter what.
2. Performance, on the other hand, is different.  It is quite possible
    that some code will result in really lousy machine code or even a call
    to a library support routine if it doesn't map to the hardware well.
    Because of this, the optimizers are occasionally aware of things that
    are bad for targets.

In the case above, the cast from "int to uint" results in no code.  The
optimization being done is probably performed by the 'instcombine' pass,
as it is strength reducing an arithmetic shift right into a logical shift
right.  It currently assumes that a logical shift is always at least as
cheap as an arithmetic shift: this is true for all targets that I am aware
of, and certainly true for all that LLVM supports currently.

An important part of this discussion is that the sign flag in this
function does not matter, thus it is safe to convert one shift into the
other.

> Although it is correct for 32-bit general purpose processor, it does not
> fit well for hardware synthesis, since we need to use wider components
> (up to 32-bit) to implement these operations, otherwise we may lose sign
> flag. Our favorite LLVM code is that without (or with very few) CAST,
> and doing the SHR directly for the signed integers.

I'm not sure I understand what you are saying here.  Can you please
clarify whether:

1. signed shift is cheaper than logical/unsigned shift, or
2. the cast is causing the problem?

For example, is this code:

short %test(uint %x) {
        %tmp.2 = shr uint %x, ubyte 10          ; <uint> [#uses=1]
        %tmp.3 = cast uint %tmp.2 to short              ; <short> [#uses=1]
        ret short %tmp.3
}

okay for you?  It has no cast, but does the same operations as the above
code.

If so, I would argue strongly that this is a bug/missing-feature from your
code generator.  The two pieces of code should generate *exactly* the same
machine code (or circuits :) ).

-Chris

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

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: [fwd] Re: LLVM Compiler Infrastructure

Yiping Fan
Chris, thank you for your reply.

Our problem is that we don't assume an integer must have 32 bits.
In our code generation, we can define an integer to be less than 32 bits. For example, 24 bits.
In this case, by executing this LLVM code (my first example) on a 24-bit machine, let x = 0xFFFFFF,
then we will get %tmp.2 = 0x003FFF, and %tmp.3 = 0x3FFF, which is positive. That is not correct because
the sign flag is lost.

I know that this transformation is correct and may be efficient for a 32-bit machine of course.
But it introduces the problem above in our scenario, and we would like the LLVM code without this
cast-to-unsigned transformation.
For unsigned shifting, there is no such problem though.

So you suggested that maybe we can skip the 'instcombine' pass to disable this transformation?

Thanks.


On 11/1/05, Chris Lattner <[hidden email]> wrote:

>   Now we got a small but annoying problem. When we get the following C
> code to llvm-gcc,
>
> short test(int x) {
>        return (short) (x >> 10);
> }
>
>   It will generate the following LLVM code:
> short %test(int %x) {
>        %x = cast int %x to uint                ; <uint> [#uses=1]
>        %tmp.2 = shr uint %x, ubyte 10          ; <uint> [#uses=1]
>        %tmp.3 = cast uint %tmp.2 to short              ; <short> [#uses=1]
>        ret short %tmp.3
> }

ok.

> Basically, LLVM frontend will first convert an integer to unsigned
> integer, and then do shifting. It seems that this conversion often
> occurs for SHIFTING operations.

The cast from 'int' to 'uint' changes the semantics of the shift from
being an arithmetic shift to a logical shift.

> So our question is that do you know there is any option in LLVM to
> disable this kind of cast-to-unsigned code generation?

No.

I'm not sure exactly why you don't like the code above, but here's the
basic idea that we're following:

1. All code generators have to support all operations, no exceptions.  The
    above code should *work* for you, no matter what.
2. Performance, on the other hand, is different.  It is quite possible
    that some code will result in really lousy machine code or even a call
    to a library support routine if it doesn't map to the hardware well.
    Because of this, the optimizers are occasionally aware of things that
    are bad for targets.

In the case above, the cast from "int to uint" results in no code.  The
optimization being done is probably performed by the 'instcombine' pass,
as it is strength reducing an arithmetic shift right into a logical shift
right.  It currently assumes that a logical shift is always at least as
cheap as an arithmetic shift: this is true for all targets that I am aware
of, and certainly true for all that LLVM supports currently.

An important part of this discussion is that the sign flag in this
function does not matter, thus it is safe to convert one shift into the
other.

> Although it is correct for 32-bit general purpose processor, it does not
> fit well for hardware synthesis, since we need to use wider components
> (up to 32-bit) to implement these operations, otherwise we may lose sign
> flag. Our favorite LLVM code is that without (or with very few) CAST,
> and doing the SHR directly for the signed integers.

I'm not sure I understand what you are saying here.  Can you please
clarify whether:

1. signed shift is cheaper than logical/unsigned shift, or
2. the cast is causing the problem?

For example, is this code:

short %test(uint %x) {
        %tmp.2 = shr uint %x, ubyte 10          ; <uint> [#uses=1]
        %tmp.3 = cast uint %tmp.2 to short              ; <short> [#uses=1]
        ret short %tmp.3
}

okay for you?  It has no cast, but does the same operations as the above
code.

If so, I would argue strongly that this is a bug/missing-feature from your
code generator.  The two pieces of code should generate *exactly* the same
machine code (or circuits :) ).

-Chris

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



_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: [fwd] Re: LLVM Compiler Infrastructure

Chris Lattner
On Tue, 1 Nov 2005, Yiping Fan wrote:

> Chris, thank you for your reply.
>
> Our problem is that we don't assume an integer must have 32 bits.
> In our code generation, we can define an integer to be less than 32 bits.
> For example, 24 bits.
> In this case, by executing this LLVM code (my first example) on a 24-bit
> machine, let x = 0xFFFFFF,
> then we will get %tmp.2 = 0x003FFF, and %tmp.3 = 0x3FFF, which is positive.
> That is not correct because
> the sign flag is lost.

There is something wrong in your compiler then, because you are not
honoring the semantics of the LLVM code.  As long as LLVM thinks that
things are 32-bits and you're implementing them as 24-bits you will
continue to run into problems like this.  The correct, but invasive, thing
to do is to add a 24-bit type to LLVM.

> I know that this transformation is correct and may be efficient for a
> 32-bit machine of course. But it introduces the problem above in our
> scenario, and we would like the LLVM code without this cast-to-unsigned
> transformation. For unsigned shifting, there is no such problem though.
>
> So you suggested that maybe we can skip the 'instcombine' pass to disable
> this transformation?

To avoid this transformation, if it is sufficient for your purposes, yes,
disabling instcombine should do it.

-Chris

> On 11/1/05, Chris Lattner <[hidden email]> wrote:
>>
>>
>>> Now we got a small but annoying problem. When we get the following C
>>> code to llvm-gcc,
>>>
>>> short test(int x) {
>>> return (short) (x >> 10);
>>> }
>>>
>>> It will generate the following LLVM code:
>>> short %test(int %x) {
>>> %x = cast int %x to uint ; <uint> [#uses=1]
>>> %tmp.2 = shr uint %x, ubyte 10 ; <uint> [#uses=1]
>>> %tmp.3 = cast uint %tmp.2 to short ; <short> [#uses=1]
>>> ret short %tmp.3
>>> }
>>
>> ok.
>>
>>> Basically, LLVM frontend will first convert an integer to unsigned
>>> integer, and then do shifting. It seems that this conversion often
>>> occurs for SHIFTING operations.
>>
>> The cast from 'int' to 'uint' changes the semantics of the shift from
>> being an arithmetic shift to a logical shift.
>>
>>> So our question is that do you know there is any option in LLVM to
>>> disable this kind of cast-to-unsigned code generation?
>>
>> No.
>>
>> I'm not sure exactly why you don't like the code above, but here's the
>> basic idea that we're following:
>>
>> 1. All code generators have to support all operations, no exceptions. The
>> above code should *work* for you, no matter what.
>> 2. Performance, on the other hand, is different. It is quite possible
>> that some code will result in really lousy machine code or even a call
>> to a library support routine if it doesn't map to the hardware well.
>> Because of this, the optimizers are occasionally aware of things that
>> are bad for targets.
>>
>> In the case above, the cast from "int to uint" results in no code. The
>> optimization being done is probably performed by the 'instcombine' pass,
>> as it is strength reducing an arithmetic shift right into a logical shift
>> right. It currently assumes that a logical shift is always at least as
>> cheap as an arithmetic shift: this is true for all targets that I am aware
>> of, and certainly true for all that LLVM supports currently.
>>
>> An important part of this discussion is that the sign flag in this
>> function does not matter, thus it is safe to convert one shift into the
>> other.
>>
>>> Although it is correct for 32-bit general purpose processor, it does not
>>> fit well for hardware synthesis, since we need to use wider components
>>> (up to 32-bit) to implement these operations, otherwise we may lose sign
>>> flag. Our favorite LLVM code is that without (or with very few) CAST,
>>> and doing the SHR directly for the signed integers.
>>
>> I'm not sure I understand what you are saying here. Can you please
>> clarify whether:
>>
>> 1. signed shift is cheaper than logical/unsigned shift, or
>> 2. the cast is causing the problem?
>>
>> For example, is this code:
>>
>> short %test(uint %x) {
>> %tmp.2 = shr uint %x, ubyte 10 ; <uint> [#uses=1]
>> %tmp.3 = cast uint %tmp.2 to short ; <short> [#uses=1]
>> ret short %tmp.3
>> }
>>
>> okay for you? It has no cast, but does the same operations as the above
>> code.
>>
>> If so, I would argue strongly that this is a bug/missing-feature from your
>> code generator. The two pieces of code should generate *exactly* the same
>> machine code (or circuits :) ).
>>
>> -Chris
>>
>> --
>> http://nondot.org/sabre/
>> http://llvm.org/
>>
>>
>

-Chris

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

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev