[LLVMdev] readonly and infinite loops

[Hal Finkel]

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

That's right. I think we'll end up doing this to some extent or another.

 -Hal

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