[LLVMdev] readonly and infinite loops

[Hal Finkel]

----- Original Message -----
> From: "Nuno Lopes" <nunoplopes at sapo.pt>
> To: "Hal Finkel" <hfinkel at anl.gov>
> Cc: "LLVM Developers Mailing List" <llvmdev at cs.uiuc.edu>, "Sanjoy Das" <sanjoy at playingwithpointers.com>, "Jeremy
> Lakeman" <Jeremy.Lakeman at gmail.com>, nlewycky at google.com
> Sent: Sunday, June 28, 2015 4:39:44 PM
> 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.
> 
> Interesting.  Could you give an example why knowing a function will
> halt is
> essential for the heap-to-stack conversion?

The key situation you need to establish in order to do heap-to-stack conversion, is that you can see the calls to free (or realloc, etc.) along all control-flow paths. If you can, then you can perform the conversion (because any additional calls to free that you can't observe would lead to a double free, and thus undefined behavior). Thus, if we have this situation:

void bar(int *a);
void foo() {
  int *a = (int*) malloc(sizeof(int)*40);
  bar(a);
  free(a);
}

we can perform heap-to-stack conversion iff we know that bar(int *) always returns normally. If it never returns (perhaps by looping indefinitely) then it might capture the pointer, pass it off to some other thread, and that other thread might call free() (or it might just call free() itself before looping indefinitely). In short, we need to know whether the call to free() after the call to bar() is dead. If we know that it is reached, then we can perform heap-to-stack conversion. Also worth noting is that because we unconditionally free(a) after the call to bar(a), it would not be legal for bar(a) to call realloc on a (because if realloc did reallocate the buffer we'd end up freeing it twice when bar(a) did eventually return).

>  It's definitely an
> optimization
> we should be doing (although, correct me if I'm wrong, LLVM already
> has some
> form of this for very small mallocs, no?)

Not that I recall, although we will remove unused mallocs (those that are immediately freed).

Thanks again,
Hal

> 
> Thanks,
> Nuno
> 
> 

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