[LLVMdev] readonly and infinite loops

[Kuperstein, Michael M]

What's really I missing, I believe, is the equivalent of the GCC "pure" attribute - which explicitly forbids infinite loops. I think readnone + halting (like in the proposed 2010 patch) is good enough, though. Then every function emitted by a C/C++ FE could be marked as halting, and we could then fix bug [2] by requiring "readnone halting". 
One potential issue with this is that "readnone halting" isn't strong enough to allow speculative execution of functions (because they may have other UB), but I'm not entirely sure GCC "pure" allows that either.

Regarding Java - what are the expected semantics of infinite loops without side-effects, per spec? 
It seems that for "trivial" infinite loops (while(1);) the FE should actually generate a compile-time error, per JLS 14.21: 
https://docs.oracle.com/javase/specs/jls/se8/html/jls-14.html#jls-14.21

The JLS does, however, explicitly claim that this is legal code:
{
    int n = 5;
    while (n > 7) k = 2;
}

But I don't see what the semantics of this are. Does it actually mandate non-termination?

Michael

-----Original Message-----
From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at cs.uiuc.edu] On Behalf Of Sanjoy Das
Sent: Sunday, June 28, 2015 09:50
To: Jeremy Lakeman
Cc: LLVM Developers Mailing List
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.
_______________________________________________
LLVM Developers mailing list
LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
---------------------------------------------------------------------
Intel Israel (74) Limited

This e-mail and any attachments may contain confidential material for
the sole use of the intended recipient(s). Any review or distribution
by others is strictly prohibited. If you are not the intended
recipient, please contact the sender and delete all copies.