[LLVMdev] readonly and infinite loops

[Daniel Berlin]

This is going to be pretty annoying.
At the *LLVM IR* level, i'm not aware of us having guarantees that
match the C/C++ standard rules.
If we do, i don't see them documented :)

Unless someone shows me different, this looks legal at the LLVM IR,
and thus, a but in clang for generating LLVM ir that doesn't represent
the semantics of hte language properly :)

(I'm half-joking)

Note at the LLVM IR level, t he only way to deal with this in general
would be to mark every loop that has a non-computable set of bounds as
maybe infinite.
Then, using metadata that contains the set of rules or something, mark
as finite those that meet those rules (ie it contains no volatile
loads, and ... and ... etc).

Note that execution and termination are, as sanjoy demonstrates, two
separate issues completely.

Given a program that says:

while (a)
   volatile load

while (b)
   nothing special



The second loop is guaranteed to terminate in C++, but not guaranteed
to *execute*.

Unless the standard believes that termination implies execution as
well ( (i can't find it anwhere) )





On Thu, Jul 9, 2015 at 12:29 PM, Sanjoy Das
<sanjoy at playingwithpointers.com> wrote:
> 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.
>
> -- Sanjoy
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev