[LLVMdev] Deriving undefined behavior from nsw/inbounds/poison for scalar evolution (original) (raw)

Jingyue Wu jingyue at google.com
Wed Jul 1 11:13:23 PDT 2015

On Tue, Jun 30, 2015 at 6:24 PM, Hal Finkel <hfinkel at anl.gov> wrote:

----- 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

That's a good call. I used to misunderstand what DataLayout::isLegalInteger means; I thought that would prevent codegen from emitting i64 at all. We will look at how things go with i64 removed from the datalayout string.

> > > 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 = INTMAX, s = 2. The final value of > i that makes the loop terminate would then be INTMAX+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/showbug.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}<%loop> to i64)) + %ptr) > > > > to > > > > {((4 * (sext i32 %offset to i64)) + %ptr),+,4}<%loop> > > I guess what I am missing here why indvars does not create an i64 > induction variable for this? > > Adam > > > > > > Currently the inner is actually , 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 -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150701/9d680158/attachment.html>

More information about the llvm-dev mailing list