为什么函数调用(Procedure Call)是通过栈调用(Call Stack)的方式来实现?

1. Intro

1RednaxelaFX的回答说到了关键,因为栈是最自然的模拟函数调用的方式。考察一段最简单的函数调用1:main()–>a(), a()–>b()

main() { a(); ... }

a() { b(); ... }

各函数的liveness分析如下:

Fig.1 liveness of functions
Fig.1 liveness of functions

可以看到,进入函数的顺序是main()–>a()–>b(),而退出函数的顺序却是b()–>a()–>main(),这是一个典型的先进后出(FILO)的场景,所以使用栈(Stack)来实现函数调用是再自然不过了。

这里简单用三个函数来解释,实际程序函数成千上万,但是实质是不变的。从这里也看出,不管程序再复杂,入口函数(main)的liveness总是最久的。

考虑一个实际的例子:

int 
compare(int a, int b)
{
  return (a >= b) ? 1 : 0;
}

int 
max_num(int a, int b, int c)
{
  int max;
  if(compare(a,b) ) 
  {
    if(compare(a,c) )
      max = a;
    else
      max = c;
  } 
  else 
  {
    if(compare(b, c) )
      max = b;
    else
      max = c;
  }

  return max;
}


int 
main(void)
{
  int n;

  n = max_num(1,3,5);
  return 0;
}

当程序执行compare()函数的时候:

(gdb) s
compare (a=1, b=3) at stack_frame.c:6
6 return (a >= b) ? 1 : 0;

此时的Call Stack:

(gdb) bt
#0 compare (a=1, b=3) at stack_frame.c:7
#1 0x56555523 in max_num (a=1, b=3, c=5) at stack_frame.c:13
#2 0x5655558c in main () at stack_frame.c:37

可以看出,main()–>max_num()–>compare()三个函数依次调用,在Call Stack上正是按照FILO的顺序存储,每一个函数对应一个栈帧(Stack Frame)。