Does this criteria prove that Y calls X in infinite recursion?

[polcott]

#include <stdint.h>
typedef int(*ptr)();

int X(ptr P, ptr I)
{
  P(I);
  return 0;
}

int Y(ptr P)
{
  X(P, P);
  return 1;
}

int main()
{
  X(Y, Y);
}

Does this criteria prove that Y calls X in infinite recursion?
An examination its x86 machine language proves that Y calls X with its same parameters and there are no conditional branch instructions between the invocation of Y and its call to X.

_X()
[00001cf3] 55         push ebp
[00001cf4] 8bec       mov ebp,esp
[00001cf6] 8b450c     mov eax,[ebp+0c]
[00001cf9] 50         push eax            ; push Y
[00001cfa] ff5508     call dword [ebp+08] ; call Y
[00001cfd] 83c404     add esp,+04
[00001d00] 33c0       xor eax,eax
[00001d02] 5d         pop ebp
[00001d03] c3         ret
Size in bytes:(0017) [00001d03]
                       
_Y()                
[00001d13] 55         push ebp
[00001d14] 8bec       mov ebp,esp
[00001d16] 8b4508     mov eax,[ebp+08]
[00001d19] 50         push eax            ; push Y
[00001d1a] 8b4d08     mov ecx,[ebp+08]
[00001d1d] 51         push ecx            ; push Y
[00001d1e] e8d0ffffff call 00001cf3       ; call X
[00001d23] 83c408     add esp,+08
[00001d26] b801000000 mov eax,00000001
[00001d2b] 5d         pop ebp
[00001d2c] c3         ret
Size in bytes:(0026) [00001d2c]

 

[Antero360]

#include <stdint.h>
typedef int(*ptr)();

int X(ptr P, ptr I)
{
  P(I);
  return 0;
}

int Y(ptr P)
{
  X(P, P);
  return 1;
}

int main()
{
  X(Y, Y);
}

Does this criteria prove that Y calls X in infinite recursion?
An examination its x86 machine language proves that Y calls X with its same parameters and there are no conditional branch instructions between the invocation of Y and its call to X.

_X()
[00001cf3] 55         push ebp
[00001cf4] 8bec       mov ebp,esp
[00001cf6] 8b450c     mov eax,[ebp+0c]
[00001cf9] 50         push eax            ; push Y
[00001cfa] ff5508     call dword [ebp+08] ; call Y
[00001cfd] 83c404     add esp,+04
[00001d00] 33c0       xor eax,eax
[00001d02] 5d         pop ebp
[00001d03] c3         ret
Size in bytes:(0017) [00001d03]
                      
_Y()               
[00001d13] 55         push ebp
[00001d14] 8bec       mov ebp,esp
[00001d16] 8b4508     mov eax,[ebp+08]
[00001d19] 50         push eax            ; push Y
[00001d1a] 8b4d08     mov ecx,[ebp+08]
[00001d1d] 51         push ecx            ; push Y
[00001d1e] e8d0ffffff call 00001cf3       ; call X
[00001d23] 83c408     add esp,+08
[00001d26] b801000000 mov eax,00000001
[00001d2b] 5d         pop ebp
[00001d2c] c3         ret
Size in bytes:(0026) [00001d2c]

Hi there,

Can you provide a bit more context for your analysis? What is the end goal? What was the origin for making such analysis?

 

[polcott]

Hi there,

Can you provide a bit more context for your analysis? What is the end goal? What was the origin for making such analysis?

I am validating the criteria for a termination analyzer to correctly determine the halt status of Y.

 

[JavaJames]

Isn't it the case that if there are no conditionals in the executed code then the code will either be executed exactly once, or loop forever?

 

[polcott]

Isn't it the case that if there are no conditionals in the executed code then the code will either be executed exactly once, or loop forever?

In the above case stack overflow would seem to eventually occur, so not always.

 

[JavaJames]

In the above case stack overflow would seem to eventually occur, so not always.

Yes, sure. But you know what I meant…. “Loop until the computer runs out of some limited resource or the sun goes nova and destroys it. 😉

More seriously: that looks like tail recursion, so a decent compiler could optimise it to avoid growing the stack.