Direct recursion detection possible?

[Timon Gehr]

On 5/25/23 09:30, Cecil Ward wrote:
> On Thursday, 25 May 2023 at 02:30:35 UTC, Steven Schveighoffer wrote:
>> On 5/24/23 7:04 PM, Cecil Ward wrote:
>>
>>> Is it possible for our compilers to detect direct infinite recursion 
>>> ? I’m ignoring the indirect call case, and I’m also ignoring anything 
>>> involving function pointers, so given those restrictions, we will be 
>>> able to see that the generated code of a routine is calling its own 
>>> address, because that address is a literal and we know what the 
>>> current function is that we’re currently in.
>>
>> Not in the general case. Direct recursion is a common pattern (direct 
>> inifite recursion obviously is not desired, but detecting that is the 
>> halting problem).
>>
>> -Steve
> 
> Could that one limited case of direct straight loops be detected in the 
> backend, just as one limited common pattern, then sending a message 
> upwards to throw out an error message for the user in the error listing 
> and stop object code generation? It seems worthwhile to me having been 
> bitten by it for the first time. Spotting "l1: jmp l1" could be almost 
> like a regex but I wouldn’t think that’s how it works.

I guess one challenge is you don't really know if the code is reachable. 
In principle it might even happen that the optimizer introduces new 
unreachable code that happens to have an infinite loop in it, then fails 
to detect it's not reachable.