[LLVMdev] readonly and infinite loops

[Nuno Lopes]

People have been aware of this issue for a long time (as you can see by 
Nick's 2010 patch).  I guess it was not pushed further because of lack of 
practical interest.
Maybe Nick remembers more about the issue and why the patch was dropped.

Sanjoy: do you have a practical concern about this issue?  I mean, of course 
this can be "fixed", but it will require some work, and even a termination 
checker for -functionattrs for the non-C/C++ frontends.

Nuno

-----Original Message----- 
From: Sanjoy Das
Sent: Sunday, June 28, 2015 7:50 AM
Subject: Re: [LLVMdev] readonly and infinite loops

> You dropped some context...

> A daemon program wouldn't be readonly. An infinite loop can be.

Right.

To prevent miscommunication, here is a quick analysis of a problematic
(IMO) example:

We start with

```
define void @infloop(i1 %c) {
entry:
  br i1 %c,  label %l, label %e

l:
  br label %l

e:
  ret void
}

define void @main_func() {
entry:
  call void @infloop(i1 1)
  ret void
}
```

In this program `@main_func`, when called, will loop infinitely.

If we run this program through `opt -functionattrs -prune-eh
-early-cse`, we get

```
; Function Attrs: nounwind readnone
define void @infloop(i1 %c) #0 {
entry:
  br i1 %c, label %l, label %e

l:                                                ; preds = %l, %entry
  br label %l

e:                                                ; preds = %entry
  ret void
}

; Function Attrs: nounwind
define void @main_func() #1 {
entry:
  ret void
}

attributes #0 = { nounwind readnone }
attributes #1 = { nounwind }
```

LLVM has optimized `@main_func` to return immediately.
`-functionattrs` and `-prune-eh` infer `nounwind readnone` for
`@infloop` and `-early-cse` delets such calls that are dead.

There are three ways to justify what happened:

1. The optimization was correct.  Infinite loops [1] in LLVM IR are
    UB and since the original program had UB, it can be optimized to
    anything.  This is problematic since if this were true, we would
    have trouble writing frontends for programming languages that
    actually have a well defined `while(1);`.

2. The bug is in `-early-cse`: a `readnone nounwind` function can
    loop infinitely, so it is not correct to remove a dead call to
    such a function.

3. The bug is in `-functionattrs`: a function cannot be marked as
    `readonly` if it may loop infinitely.


Needless to say, both (2) and (3) are "easy to fix"; the question is
really about the deeper semantic issue about how LLVM treats
`while(1);`.

There are interesting related questions on the semantics of the
equivalent C/C++ programs, but I personally am interested
only in "pure" LLVM IR semantics.

-- Sanjoy

[1]: We could make the distinction between infinite loops that are
empty vs. infinite loops that are non-empty but that's tricky -- if
only empty infinite loops were UB then e.g. LICM gets harder, since
sinking the store out of loops like `while(1) *addr = 42;` now
introduces UB.