Why is dynamic link required in function activation record? (in static scoped language)

Question

I read that the dynamic link points to the previous activation record ( aka a "stack frame"), so it makes sense in dynamic scoped programming language. But in static scoped programming language, why the access link (which points to activation record of function in one lower nesting level) isn't enough? And specifically in C - why access link is not needed? And why dynamic link is needed?

Answer 1

I will use this nomenclature which is more familiar to me:

Activation record: Stack frame

Dynamic link: [saved] frame pointer

So, I interpret your question as: Why are frame pointers needed?^[1]

A frame pointer is not required.

Some compilers (e.g. Green Hills C++, GCC with -O2) don’t usually generate one or can be asked not to generate it (MSVC, GCC).

That said, it does of course have its benefits:

• Easy traversing of the call stack: generating a stack trace is as easy as traversing a linked list where the frame pointer forms the head. Makes implementing stack traces and debuggers much easier.

• Easier code generation: stack variables can be referenced by indexing the frame pointer instead of the all-the-time-changing stack pointer. The stack pointer changes with each push/pop, the frame pointer stays constant within a function (between the prologue/epilogue)

• Should things go awry, stack unwinding can be done using the frame pointer. This is how Borland’s structured exception handling (SEH) works.

• Streamlines stack management: Particularly implementations of setjmp(3), alloca(3) and C99-VLA may (and usually do) depend on it.

Drawbacks:

• Register usage: a x86 got only 8 general purpose registers. one of these would need to be dedicated fully for holding the frame pointer.
• Overhead: the prologue/epilogue is generated for every function.

But as you noticed, a compiler can generate perfectly fine code without having to maintain a frame pointer.

---

[1] If that's not what's meant, please elaborate.

Answer 2

Your question might be related to the -fomit-frame-pointer optimizing option of GCC, then see this.

BTW, many people are naming call frames (in the call stack) what you name activation record. The notion of continuation, and also of continuation passing style and A-normal forms are closely related.

A dynamic link is really only useful for nested functions (and perhaps closures), and standard C does not have them. Some people speak of display links. Standard C don't have nested functions, so don't need any related trick (display link, trampoline, ...).

The GCC compiler provides nested functions as a C language extension, and implement them with dynamic links on activation records, very closely to what you are thinking about. Read also the wikipages on man or boy test and on trampoline.