[LLVMdev] Deriving undefined behavior from nsw/inbounds/poison for scalar evolution

[Hal Finkel]

----- Original Message -----
> From: "Bjarke Roune" <broune at google.com>
> To: "Jingyue Wu" <jingyue at google.com>
> Cc: llvmdev at cs.uiuc.edu
> Sent: Tuesday, June 30, 2015 8:16:13 PM
> Subject: Re: [LLVMdev] Deriving undefined behavior from nsw/inbounds/poison for scalar evolution
> 
> Hi Adam,
> 
> Jingyue is right. We need to keep things in 32 bits because 64 bit
> arithmetic is more expensive and because one 64 bit register
> consumes two 32 bit registers.
> 

What benefit to you get from listing i64 as a legal integer width in the DataLayout for NVPTX?

 -Hal

> 
> 
> To add a bit more background: we would often emit worse code if we
> widened in indvars and then narrowed in the NVPTX backend later
> because we often would not be able to narrow AFAICT. Consider this
> general pattern where everything is 32 bit:
> 
> 
> for (int i = a; i < b; i += s) {
> // ...
> }
> 
> 
> Suppose we widen i to be 64 bit:
> 
> 
> 
> for (int64 i = a; i < b; i += s) {
> // ...
> }
> 
> 
> As an example, suppose a = 0, b = INT_MAX, s = 2. The final value of
> i that makes the loop terminate would then be INT_MAX+1, so we
> cannot narrow i to 32 bits. To narrow in general, we have to prove
> that a, b and s take on only values where narrowing is sound. That's
> often not possible. I suppose an alternative would be to issue an
> assume intrinsic restricting the range of i, though I prefer making
> scalar evolution more powerful since that should be more generally
> useful.
> 
> 
> Bjarke
> 
> 
> 
> 
> 
> On Mon, Jun 29, 2015 at 8:57 PM, Jingyue Wu < jingyue at google.com >
> wrote:
> 
> 
> 
> Hi Adam,
> 
> 
> Indvar widening can sometimes be harmful for architectures (e.g.
> NVPTX and AMDGPU) where wider integer operations are more expensive
> ( https://llvm.org/bugs/show_bug.cgi?id=21148 ). For this reason, we
> disabled indvar widening in NVPTX in http://reviews.llvm.org/D6196 .
> 
> 
> Hope it helps.
> 
> 
> Jingyue
> 
> 
> 
> 
> On Mon, Jun 29, 2015 at 11:59 AM Adam Nemet < anemet at apple.com >
> wrote:
> 
> 
> 
> > On Jun 26, 2015, at 4:01 PM, Bjarke Roune < broune at google.com >
> > wrote:
> > 
> > *** Summary
> > I'd like to propose (and implement) functionality in LLVM to
> > determine when a poison value from an instruction is guaranteed to
> > produce undefined behavior. I want to use that to improve handling
> > of nsw, inbounds etc. flags in scalar evolution and LSR. I imagine
> > that there would be other uses for it. I'd like feedback on this
> > idea before I proceed with it.
> > 
> > 
> > *** Details
> > Poison values do produce undefined behavior if the poison becomes
> > externally observable. A load or store to a poison address value
> > is externally observable and I'd like to use that in a simple
> > analysis pass to derive guarantees that certain overflows would
> > produce undefined behavior, not just poison.
> > 
> > Scalar evolution (and hence LSR) cannot currently make much use of
> > the nsw and similar flags on instructions. That is because two
> > instructions can map to the same scev even if one instruction has
> > the nsw flag and the other one does not. If we applied the nsw
> > flag to the scev, the scev for the instruction without the nsw
> > flag would then incorrectly have the nsw flag.
> > 
> > Scalar evolution would be able to use the nsw flag from an
> > instruction for recurrences when the loop header dominates the
> > entire loop, the instruction with nsw post-dominates the loop
> > header and undefined behavior is guaranteed on wrap via the poison
> > value analysis pass that I'd like to write.
> > 
> > What do you think? Do we already have something similar to this?
> > 
> > Bjarke
> > 
> > 
> > 
> > *** PS: What got me thinking about this:
> > My immediate motivation is that I'd like LSR to be able to create
> > induction variables for expressions like &ptr[i + offset] where i
> > and offset are 32 bit integers, ptr is a loop-invariant 64 bit
> > pointer, i is an induction variable and offset is loop-invariant.
> > For that to happen, scalar evolution needs to propagate the nsw
> > flag from i + offset to the scev so that it can transform
> > 
> > ((4 * (sext i32 {%offset,+,1}<nw><%loop> to i64))<nsw> + %ptr)<nsw>
> > 
> > to
> > 
> > {((4 * (sext i32 %offset to i64)) + %ptr),+,4}<nsw><%loop>
> 
> I guess what I am missing here why indvars does not create an i64
> induction variable for this?
> 
> Adam
> 
> 
> > 
> > Currently the inner <nsw> is actually <nw>, which blocks the
> > transformation (the outer two nsw's shouldn't currently be there
> > either, as it's the same issue for inbounds on GEP: see llvm bug
> > 23527)
> > _______________________________________________
> > LLVM Developers mailing list
> > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu
> > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> 
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> 
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> 

-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory