[llvm-dev] trunc nsw/nuw?

Fri Jul 7 14:40:53 PDT 2017

This is the kind of thing where (at least in an ideal world where I can 
find the free time) Souper can easily help -- we teach it about trunc 
nsw (should only take a couple of minutes) and then run it over a lot of 
code and see if anything good comes out.

John

On 7/7/17 2:55 AM, Sanjoy Das via llvm-dev wrote:
> Hi,
>
> Even if there are no ways in which a *frontend* can produce nsw
> truncs, it may still be useful to have if optimization passes can
> usefully attach nsw to truncates (after proving the truncates don't
> "overflow").  For instance in
>
>   %a = ashr i64 %v, i32 33
>   %t = trunc %a to i32
>
> the trunc can be marked nsw.
>
> However, the burden of proof here is to show that we can do some
> useful optimization with nsw truncs that we can't do (unless we move
> mountains) without them.
>
> Thanks!
> -- Sanjoy
>
>
> On Thu, Jul 6, 2017 at 5:46 PM, Hal Finkel via llvm-dev
> <llvm-dev at lists.llvm.org> wrote:
>>
>> On 07/06/2017 10:41 AM, Bruce Hoult wrote:
>>
>> According to 6.3.1.3/3 of the C standard (I didn't check C++):
>>
>> "3   Otherwise, the new type is signed and the value cannot be represented
>> in it; either the result is implementation-defined or an
>> implementation-defined signal is raised."
>>
>> I *think* that means that IF a signal is raised then the signal raised could
>> be one that you can't guarantee to be able to return from ("SIGFPE, SIGILL,
>> SIGSEGV, or any other implementation-defined value corresponding to a
>> computational exception") and thus it is implementation defined whether the
>> program will terminate.
>>
>> That provides pretty big scope to optimize around :-)
>>
>>
>> That might be true, but C++ does not have the implementation-defined signal
>> part. So whatever we did would need to be C specific at this point.
>>
>>  -Hal
>>
>>
>>
>> Note also that while unsigned variables require the implementation to act AS
>> IF running on a binary machine, signed variables have no such requirement.
>> Most implementations do in fact truncate by taking the remainder modulus the
>> number of values that can be represented in the destination type, but that
>> might not be a power of two.
>>
>> I would guess there is very little code in the wild that conforms to a
>> strict interpretation of all this.
>>
>> On Thu, Jul 6, 2017 at 5:24 PM, Alexandre Isoard via llvm-dev
>> <llvm-dev at lists.llvm.org> wrote:
>>>
>>> Hi Hal,
>>>
>>> I just want to check I understand correctly the subtlety, in C++ an
>>> overflowing signed addition is an undefined behavior (so Clang adds the nsw
>>> keyword to the sign add), while a signed cast that overflow is "only"
>>> implementation defined (so Clang cant risk to produce poison on trunc). Is
>>> that right?
>>>
>>> If trunc produced undef instead of poison, clang could use it, but then it
>>> is less useful and/or unwanted?
>>>
>>> On Wed, Jul 5, 2017 at 10:30 PM, Hal Finkel <hfinkel at anl.gov> wrote:
>>>>
>>>>
>>>> On 07/05/2017 03:10 PM, Alexandre Isoard wrote:
>>>>
>>>> Ah, ok. I read it wrong. In *neither* case it is UB.
>>>>
>>>> Hum, can an implementation define it as UB? :-)
>>>>
>>>>
>>>> Nope :-)
>>>>
>>>> The only case I've thought of where we could add these for C++ would be
>>>> on conversions to (most) enums (because they used signed underlying types
>>>> and the out-of-bounds mapping won't generally be one of the allowed values
>>>> (or maybe we can define this to be the case?)).
>>>>
>>>>  -Hal
>>>>
>>>>
>>>>
>>>> On Wed, Jul 5, 2017 at 9:09 PM, Alexandre Isoard
>>>> <alexandre.isoard at gmail.com> wrote:
>>>>>
>>>>>
>>>>>
>>>>> On Wed, Jul 5, 2017 at 3:59 PM, Hal Finkel via llvm-dev
>>>>> <llvm-dev at lists.llvm.org> wrote:
>>>>>>
>>>>>>
>>>>>> On 07/04/2017 01:41 AM, Dr.-Ing. Christoph Cullmann via llvm-dev wrote:
>>>>>>>
>>>>>>> Hi,
>>>>>>>
>>>>>>>> Hi Alexandre,
>>>>>>>>
>>>>>>>> LLVM currently doesn't have trunc nsw/nuw, no.
>>>>>>>> Which frontend would emit such instructions? Any application in mind?
>>>>>>>> Just asking because if no frontend could emit those, then the
>>>>>>>> motivation to
>>>>>>>> add nsw/nuw support to trunc would be very low I guess.
>>>>>>>
>>>>>>> I think the clang frontend could use that to allow better static
>>>>>>> analysis of integer overflows
>>>>>>> on the LLVM IR.
>>>>>>>
>>>>>>> It might be interesting for static analysis tools that want to know if
>>>>>>> you truncate something
>>>>>>> that is too large for the target range but you need the sign to
>>>>>>> determine, e.g. the C/C++ frontend
>>>>>>> could use that flag for trunc of signed/unsigned integers, then you
>>>>>>> could e.g. check if
>>>>>>>
>>>>>>> (uint8_t)x
>>>>>>>
>>>>>>> changes the values if x has stuff out of the 0..255 range.
>>>>>>>
>>>>>>> e.g. x as int with -100 => trunc nuw to 8 => bad
>>>>>>>
>>>>>>> (int8_t)x
>>>>>>>
>>>>>>>    => trunc nsw to 8 => ok
>>>>>>
>>>>>>
>>>>>> I'm not sure that a C/C++ frontend could add this flag. In C++, the
>>>>>> conversion for unsigned types is specified and for signed types, it's
>>>>>> implementation defined, but in neither case is it UB.
>>>>>
>>>>>
>>>>> Hmm, I don't get it.
>>>>>
>>>>> Two questions:
>>>>> - if the conversion for unsigned types is specified, how is it undefined
>>>>> behavior?
>>>>> - if the conversion for signed types is UB, then this is a direct
>>>>> application of those flags, isn't it?
>>>>>
>>>>>>  -Hal
>>>>>>
>>>>>>
>>>>>>>
>>>>>>> Greetings
>>>>>>> Christoph
>>>>>>>
>>>>>>>> Thanks,
>>>>>>>> Nuno
>>>>>>>>
>>>>>>>> -----Original Message-----
>>>>>>>> From: Alexandre Isoard via llvm-dev
>>>>>>>> Sent: Monday, July 3, 2017 8:38 PM
>>>>>>>> To: llvm-dev
>>>>>>>> Subject: [llvm-dev] trunc nsw/nuw?
>>>>>>>>
>>>>>>>>
>>>>>>>> Hello,
>>>>>>>>
>>>>>>>>  From [1], trunc does not seems to have a nsw/nuw attribute.
>>>>>>>> Is it possible to have that? Or do we have that and it is not
>>>>>>>> up-to-date?
>>>>>>>>
>>>>>>>> The definition would be:
>>>>>>>>
>>>>>>>> If the nuw keyword is present, the result value of the trunc is a
>>>>>>>> poison
>>>>>>>> value if the truncated high order bits are non-zero. If the nsw
>>>>>>>> keyword is
>>>>>>>> present, the result value of the trunc is a poison value if the
>>>>>>>> truncated
>>>>>>>> high order bits are not all equal to the non-truncated bit of the
>>>>>>>> highest
>>>>>>>> order.
>>>>>>>>
>>>>>>>> This allow to cancel out:
>>>>>>>> - sext with trunc nsw
>>>>>>>> - zext with trunc nuw
>>>>>>>>
>>>>>>>> And probably to commute with add/sub/mul/lshr/ashr/shl/urem/udiv/udiv
>>>>>>>> (with
>>>>>>>> the correct flags).
>>>>>>>>
>>>>>>>> [1]: http://llvm.org/docs/LangRef.html#trunc-to-instruction
>>>>>>>>
>>>>>>>>
>>>>>>>> --
>>>>>>>>
>>>>>>>> Alexandre Isoard
>>>>>>>>
>>>>>>>> _______________________________________________
>>>>>>>> LLVM Developers mailing list
>>>>>>>> llvm-dev at lists.llvm.org
>>>>>>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>>>>>
>>>>>>
>>>>>> --
>>>>>> Hal Finkel
>>>>>> Lead, Compiler Technology and Programming Languages
>>>>>> Leadership Computing Facility
>>>>>> Argonne National Laboratory
>>>>>>
>>>>>>
>>>>>> _______________________________________________
>>>>>> LLVM Developers mailing list
>>>>>> llvm-dev at lists.llvm.org
>>>>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>>>>
>>>>>
>>>>>
>>>>>
>>>>> --
>>>>> Alexandre Isoard
>>>>
>>>>
>>>>
>>>>
>>>> --
>>>> Alexandre Isoard
>>>>
>>>>
>>>> --
>>>> Hal Finkel
>>>> Lead, Compiler Technology and Programming Languages
>>>> Leadership Computing Facility
>>>> Argonne National Laboratory
>>>
>>>
>>>
>>>
>>> --
>>> Alexandre Isoard
>>>
>>> _______________________________________________
>>> LLVM Developers mailing list
>>> llvm-dev at lists.llvm.org
>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>>
>>
>>
>> --
>> Hal Finkel
>> Lead, Compiler Technology and Programming Languages
>> Leadership Computing Facility
>> Argonne National Laboratory
>>
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>