[LLVMdev] readonly and infinite loops

[Sanjoy Das]

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