Direct recursion detection possible?

[Cecil Ward]

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

Understood, quite so. Indeed that’s why I kept it to ‘direct’. Is 
anyone up for helping me deal with that one limited case of 
direct straight loops ?

This one case could even be detected in a backend, for want of a 
better solution. Just one limited common pattern, when spotted in 
the machine code generation, on seeing the "l1: jmp l1" pattern, 
which is without content from any basic block in the body, when 
an unconditional jump target is put to the output, that match 
then spots the pattern and triggers the output of an error level 
message for the user in the error listing and prevents object 
file output. Of course a check at a much higher level for this 
one specific pattern would be far better.

It’s only my own opinion, but it does seem a worthwhile specific 
error checking case to me, having been bitten by it for the first 
time, because I get any message at all. Spotting "l1: jmp l1" 
could be almost like a regex but I wouldn’t think that’s how 
things work. Nor I wouldn’t think that that’s necessarily the 
right place for such detection. There’s perhaps a ‘right’ place 
higher up. But I’m out of my depth with compiler innards here.

Would other users also like the safety of direct loop detection? 
Whether or not it comes from recursion, that is. A bad loop 
condition test too would be another case, where the compiler has 
worked out that the condition has a known boolean value.