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

[Hal Finkel]

----- Original Message -----
> From: "Bjarke Roune" <broune at google.com>
> To: llvmdev at cs.uiuc.edu
> Sent: Friday, June 26, 2015 6:01:35 PM
> Subject: [LLVMdev] Deriving undefined behavior from nsw/inbounds/poison for	scalar evolution
> 
> 
> 
> 
> *** 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.
> 

My understanding is that SCEV currently only uses no-wrap flags that it can independently prove, in part, because SCEVExpander might be used to materialize the expressions outside of the loop body (in the pre-header, for example). Andy, can you comment on the constraints here?

 -Hal

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

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