7.9.函数运行模拟

发表于 更新于 分类于 ， 阅读次数： 本文字数： 508 阅读时长 ≈ 2 分钟

\(7.9.\)Run-time Simulation

1.Run-time example

1
2
3
4
5
6
7
8
int main() {
	return factorial(3);
}

int factorial(int n) {
	if (n == 1) return 1;
	else return n * factorial(n - 1);
}

  • When compiling the main part, we:

    • push 3
    • call factorial
    • return
1
2
3
4
function main
	push 3
	call factorial
	return

  • Then we start to compile the function:

    • We declare the function.
    • We evaluate the condition n==1
    • If the conitional statement returns false, we push n, and compute factorial(n - 1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function factorial(n) 
	push n
	push 1
	eq 
	if-goto BASECASE
	
	push n
	push n
	pusn 1
	sub
	call factorial
	call mult
	return

label BASECASE
	push 1
	return

  The pseudo VM code can be translated into these VM codes: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function main 0
	push constant 3
	call factorial 1
	return

function factorial 0
	push argument 0
	push constant 1
	eq
	if-goto BASECASE

	push argument 0
	push argument 0
	push constant 1
	sub
	call factorial 1
	call mult 2
	return 

label BASECASE
	push constant 1
	return

  Then what happen during the runtime?

  1. main starts running, and informs that it has 0 local variable.
  2. main pushes, so it starts with an empty stack.
  3. push constant 3, then we get a 3 on the stack.

  1. call factorial 1, the 1 informs that 1 argument was pushed onto the stack. So we can refer to the topmost value in the stack as argument 0.

2.Callee process

  Then we begin to deal with the call command.

  1. We first save the frame of main onto the stack. Then we jump to execute factorial.

  • The blue dot shows the return address in the given code. And this is exactly where we want to return to after factorial finishes.
  1. The eq consumes argument 0 and constant 1, so the overall effect of the first 4 commands on the stack is nil.
  2. We push argument 0, push argument 0, push constant 1, sub, so we are going to get 3 and 2 on the stack.

  1. call factorial 1, we inform the implementation that 1 argument has been pushed onto the stack, we can refer to it as argument 0.
  2. We want to issue a call command, so the implementation is going to save the frame of the current function, and the return address is the green dot, we save it, too.

  1. After several calls, we turn to f(1), and the global stack now looks like this:

  1. This time 1 equals 1, we jump to BASECASE, push constant 1 and do a return.

  When the inplementation encounters the return command, it:

  1. Gets the return address off the stack.
  2. Copy the return value. In this case, it's argument 0, so we copy 1 on arg0.
  3. After return, we can recycle the current frame, which is no more relevant.

  And we do this step again and again:

  During the process, the caller is completely oblivious of all the drama, it takes part behind the scene.