[LLVMdev] readonly and infinite loops

[Daniel Berlin]

I guess it's also worth pointing out that 9 years ago in GCC, starting
to do this instead of treating all infinite loops as "always exiting"
cost 3% geomean on SPEC.

(How useful this is as a measure for LLVM, no idea :P)




On Thu, Jul 9, 2015 at 1:26 PM, Daniel Berlin <dberlin at dberlin.org> wrote:
> 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