[LLVMdev] readonly and infinite loops

[Hal Finkel]

----- Original Message -----
> From: "Sanjoy Das" <sanjoy at playingwithpointers.com>
> To: "Hal Finkel" <hfinkel at anl.gov>
> Cc: "Nick Lewycky" <nlewycky at google.com>, "LLVM Developers Mailing List" <llvmdev at cs.uiuc.edu>, "Jeremy Lakeman"
> <Jeremy.Lakeman at gmail.com>, "Nuno Lopes" <nunoplopes at sapo.pt>
> Sent: Thursday, July 9, 2015 2:29:22 PM
> Subject: Re: [LLVMdev] readonly and infinite loops
> 
> Here's a fun spin on this same topic (I can't file a bug at this
> moment since llvm.org is down).
> 
> Consider:
> 
> define i32 @x(i32* %x, i1* %y) {
>  entry:
>   br label %loop
> 
>  loop:
>   %v = phi i32 [ 0 , %entry ], [ %v.inc, %exit.inner ], [ %v, %loop ]
>   %c = load volatile i1, i1* %y
>   br i1 %c, label %exit.inner, label %loop
> 
>  exit.inner:
>   %c1 = load volatile i1, i1* %y
>   %x.val = load i32, i32* %x
>   %v.inc = add i32 %v, %x.val
>   br i1 %c1, label %exit.real, label %loop
> 
>  exit.real:
>   ret i32 %v
> }
> 
> Now if %c is false every time, %x is never dereferenced.  Since this
> is an infinitely looping program that does a volatile load in every
> iteration, it is well defined (going by what Hal said).
> 
> However, opt -licm transforms this to
> 
> ; ModuleID = '/Users/sanjoy/tmp/inf.ll'
> 
> define i32 @x(i32* %x, i1* %y) {
> entry:
>   %x.val = load i32, i32* %x
>   br label %loop.outer
> 
> loop.outer:                                       ; preds =
> %exit.inner, %entry
>   %v.ph = phi i32 [ %v.inc, %exit.inner ], [ 0, %entry ]
>   br label %loop
> 
> loop:                                             ; preds =
> %loop.outer, %loop
>   %c = load volatile i1, i1* %y
>   br i1 %c, label %exit.inner, label %loop
> 
> exit.inner:                                       ; preds = %loop
>   %c1 = load volatile i1, i1* %y
>   %v.inc = add i32 %v.ph, %x.val
>   br i1 %c1, label %exit.real, label %loop.outer
> 
> exit.real:                                        ; preds =
> %exit.inner
>   %v.ph.lcssa = phi i32 [ %v.ph, %exit.inner ]
>   ret i32 %v.ph.lcssa
> }
> 
> where it unconditionally dereferences %x, effectively introducing UB
> if %x is not dereferenceable.
> 
> 
> The bug is in isGuaranteedToExecute.  It assumes that if an
> instruction dominates all the loop exits then it will always be
> executed by the loop "on its way out".  But there may never be a way
> out of the loop.

That's unfortunately correct. This is a bug.

 -Hal

> 
> -- Sanjoy
> 

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