[LLVMdev] Adding a halting function attribute?

[Chris Lattner]

On May 1, 2010, at 11:19 AM, Chris Lattner wrote:

> 
> On May 1, 2010, at 11:07 AM, Owen Anderson wrote:
> 
>> Hey folks,
>> 
>> In a recent blog post, John Regehr pointed out that LLVM is currently optimizing away read-only functions containing infinite loops whose return values are never used.  The culprit for the moment is the inliner, but the more insidious problem is that isTriviallyDeletable currently returns true for any read-only function whose value is not used.
>> 
>> In order to prevent this from happening while avoiding pessimizing the common case, I'm proposing adding a "halting" function attribute which is a hint to the optimizers that a function is guaranteed to halt.  A pretty simple conservative implementation would be as a "contains no loops" analysis.  Obviously fancier implementations are possible, but we'd like to avoid having the FunctionAttrs depend on LoopInfo or SCEV which would be needed for loop finiteness analysis.  Additionally, we already have the LoopDeletion pass interleaved, which should handle exactly those cases anyways.
> 
> Two (more) problems:
> 
> 1) You have to prove that infinite recursion (which might be tail calls) doesn't happen.  This means that anything that does an indirect call has to be assumed to not be halting.
> 
> 2) You'd have to update all the builtins to say they are halting, because they are external functions.
> 
> 3) This adds (even more) clutter to the IR. :(

On reflection, perhaps this isn't so bad.  This really only matters when the compiler is able to infer readnone/readonly, which typically doesn't include cases with indirect calls.  Per #2, I think it could be handled by making the GCC-style pure/const attributes imply both readonly/readnone *and* halting.

-Chris