[LLVMdev] readonly and infinite loops

[Hal Finkel]

----- Original Message -----
> From: "Daniel Berlin" <dberlin at dberlin.org>
> To: "Sanjoy Das" <sanjoy at playingwithpointers.com>
> Cc: "Hal Finkel" <hfinkel at anl.gov>, "LLVM Developers Mailing List" <llvmdev at cs.uiuc.edu>
> Sent: Thursday, July 9, 2015 3:26:32 PM
> Subject: Re: [LLVMdev] readonly and infinite loops
> 
> 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) )
> 

I don't believe that it does.

 -Hal

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

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