[LLVMdev] readonly and infinite loops

Sanjoy Das sanjoy at playingwithpointers.com
Sun Jun 28 12:20:52 PDT 2015


> Sanjoy: do you have a practical concern about this issue?  I mean, of course

I don't have any immediate practical concerns and I've not actually
seen miscompiles resulting from this.  But fixing this is certainly
more important than a "nice to have" -- we cannot miscompile "while
(true) ;" loops.

-- Sanjoy

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



More information about the llvm-dev mailing list