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 >
Hi, Well, here is an example: preheader: %skip = icmp slt i64 0, %n br i1 %skip, label %exit, label %body body: %i = phi i64 [ 0, %preheader ], [ %i.inc, %body ] %n.int = trunc nsw i64 %n to i32 %i.int = trunc nsw i64 %i to i32 %test = icmp slt i32 %i.int, %n.int %i.inc = add nsw i64 %i, 1 br i1 %test, label %body, label %exit exit: ... The original loop induction variable (%i) was 32 bit, as well as the loop boundary (%n). A pass decided to "upgrade" the induction variable arithmetic to 64 bits, and because the original increment was "add nsw" it is safe to do so. However, the loop exit condition is still a 32 bits comparison. A later pass could upgrade the loop exit condition to 64 bits if it can prove that: « int64_t(i) < int64_t(n) ⇒ int32_t(i) < int32_t(n) » Which is false in general, but true in this case, as the truncation is nsw. That being said, maybe the pass that upgraded the induction variable arithmetic should have finished the job and upgraded the loop condition. But that does provide some additional flexibility. Hopefully, I didn't mess up the example [I just made this up]. :-) On Fri, Jul 7, 2017 at 8:55 AM, Sanjoy Das <sanjoy at playingwithpointers.com> 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 > > >-- *Alexandre Isoard* -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170707/5349d17c/attachment-0001.html>
On 07/07/2017 04:31 AM, Alexandre Isoard wrote:> Hi, > > Well, here is an example: > > preheader: > %skip = icmp slt i64 0, %n > br i1 %skip, label %exit, label %body > > body: > %i = phi i64 [ 0, %preheader ], [ %i.inc, %body ] > %n.int <http://n.int> = trunc nsw i64 %n to i32 > %i.int <http://i.int> = trunc nsw i64 %i to i32 > %test = icmp slt i32 %i.int <http://i.int>, %n.int <http://n.int> > %i.inc = add nsw i64 %i, 1 > br i1 %test, label %body, label %exit > > exit: > ... > > The original loop induction variable (%i) was 32 bit, as well as the > loop boundary (%n). > A pass decided to "upgrade" the induction variable arithmetic to 64 > bits, and because the original increment was "add nsw" it is safe to > do so. However, the loop exit condition is still a 32 bits comparison.This is a good point. Especially right now, we widen induction variables early in the pipeline, and so we lose information (in practice at least) as a result. I'd prefer that we move widening to later in the pipeline, but perhaps it is still valuable regardless (because there are backend passes that depend on SCEV, etc.). -Hal> > A later pass could upgrade the loop exit condition to 64 bits if it > can prove that: « int64_t(i) < int64_t(n) ⇒ int32_t(i) < int32_t(n) » > Which is false in general, but true in this case, as the truncation is > nsw. > > That being said, maybe the pass that upgraded the induction variable > arithmetic should have finished the job and upgraded the loop > condition. But that does provide some additional flexibility. > > Hopefully, I didn't mess up the example [I just made this up]. :-) > > On Fri, Jul 7, 2017 at 8:55 AM, Sanjoy Das > <sanjoy at playingwithpointers.com > <mailto:sanjoy at playingwithpointers.com>> 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 <mailto:llvm-dev at lists.llvm.org>> wrote: > > > > On 07/06/2017 10:41 AM, Bruce Hoult wrote: > > > > According to 6.3.1.3/3 <http://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 <mailto: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 > <mailto: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 > <mailto: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 <mailto: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 > <http://llvm.org/docs/LangRef.html#trunc-to-instruction> > >>>>>>> > >>>>>>> > >>>>>>> -- > >>>>>>> > >>>>>>> Alexandre Isoard > >>>>>>> > >>>>>>> _______________________________________________ > >>>>>>> LLVM Developers mailing list > >>>>>>> llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org> > >>>>>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev > <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 <mailto:llvm-dev at lists.llvm.org> > >>>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev > <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 <mailto:llvm-dev at lists.llvm.org> > >> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev > <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 <mailto:llvm-dev at lists.llvm.org> > > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev > <http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev> > > > > > > > -- > *Alexandre Isoard*-- Hal Finkel Lead, Compiler Technology and Programming Languages Leadership Computing Facility Argonne National Laboratory -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170707/ba15ead4/attachment.html>
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 >