[LLVMdev] readonly and infinite loops

[Hal Finkel]

----- Original Message -----
> From: "Nuno Lopes" <nunoplopes at sapo.pt>
> To: "Sanjoy Das" <sanjoy at playingwithpointers.com>, "Jeremy Lakeman" <Jeremy.Lakeman at gmail.com>, nlewycky at google.com
> Cc: "LLVM Developers Mailing List" <llvmdev at cs.uiuc.edu>
> Sent: Sunday, June 28, 2015 6:08:52 AM
> Subject: Re: [LLVMdev] readonly and infinite loops
> 
> 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.

I can't comment about the rationale in 2010, but this came up again when I was originally working on heap-to-stack conversion. Being able to mark functions as halting is essential for doing heap-to-stack conversion. This was put on hold, however, essentially awaiting the new pass manager. The issue is that you'd like to be able to use SCEV in a module/CGSCC-level pass to infer the attribute on functions with loops, and this cannot be done directly until we have the new pass manager.

On the other hand, maybe we don't need to wait for that now. We now also have a scheme for tagging loops with metadata, and we could use that to add metadata to loops known to have a finite trip count, and then use that metadata in a pass that infers the attribute (FunctionAttrs presumably).

 -Hal

> 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.
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> 

-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory