[llvm-dev] trunc nsw/nuw?
Hal Finkel via llvm-dev
llvm-dev at lists.llvm.org
Fri Jul 7 04:03:04 PDT 2017
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>
More information about the llvm-dev
mailing list