Nested subroutine calls in ARM Architecture - Deep Dive

Overview - Nested subroutine calls

What is it?

Nested subroutine calls happen when one subroutine (a small program or function) calls another subroutine inside it. This can happen multiple times, creating layers of calls. Each call pauses the current subroutine and jumps to the next one, then returns back when done. This helps organize complex tasks into smaller, manageable pieces.

Why it matters

Without nested subroutine calls, programs would be long and hard to manage because every task would have to be written in one place. Nested calls allow reuse of code and clearer structure. In ARM architecture, managing these calls correctly is crucial for the processor to keep track of where to return after each subroutine finishes, ensuring the program runs smoothly.

Where it fits

Before learning nested subroutine calls, you should understand basic subroutines and how the ARM processor handles function calls and returns. After this, you can learn about stack management, calling conventions, and interrupt handling, which build on nested calls to manage complex program flows.

Mental Model

Core Idea

Nested subroutine calls are like stacking tasks where each new task pauses the current one and resumes it only after finishing the new task.

Think of it like...

Imagine you are reading a book and find a footnote that refers you to another book. You put a bookmark in your current book, read the footnote's book, and when done, return to your original book exactly where you left off.

Main Program
   │
   ▼
Subroutine A (calls Subroutine B)
   │
   ▼
Subroutine B (calls Subroutine C)
   │
   ▼
Subroutine C
   │
   ▲
Return to Subroutine B
   │
   ▲
Return to Subroutine A
   │
   ▲
Return to Main Program

Build-Up - 7 Steps

1

Foundation

Understanding Basic Subroutine Calls

Concept: Learn what a subroutine is and how a single call and return works in ARM.

A subroutine is a set of instructions that performs a specific task. In ARM, calling a subroutine uses the BL (Branch with Link) instruction, which saves the return address in the link register (LR). When the subroutine finishes, it uses the BX LR instruction to return to the caller.

Result

The program jumps to the subroutine, executes its instructions, then returns to the point after the call.

Understanding how a single call and return works is essential before adding layers of nested calls.

2

Foundation

Role of the Stack in Subroutine Calls

Concept: Introduce the stack as a memory area to save return addresses and local data during calls.

The stack is a special memory area that grows and shrinks as subroutines are called and return. When a subroutine calls another, it saves the current return address and important registers on the stack to avoid losing them. This way, each subroutine can return correctly even when calls are nested.

Result

Return addresses and data are safely stored, allowing multiple nested calls without confusion.

Knowing the stack's role prevents errors in nested calls and helps understand how the processor keeps track of multiple return points.

3

Intermediate

How Nested Calls Use the Link Register and Stack

🤔Before reading on: do you think the link register alone can handle multiple nested calls correctly? Commit to yes or no.

Concept: Explain why the link register (LR) must be saved on the stack during nested calls.

The link register holds the return address for the current subroutine. When a subroutine calls another, the LR is overwritten with the new return address. To avoid losing the previous return address, the current LR is pushed onto the stack before the new call. This preserves the chain of return addresses for nested calls.

Result

Each nested call has its own saved return address, ensuring correct returns in reverse order.

Understanding LR saving is key to grasping how nested calls maintain correct return flow.

4

Intermediate

Stack Frame Creation in Nested Calls

🤔Before reading on: do you think all nested subroutines share the same stack frame or have separate ones? Commit to your answer.

Concept: Introduce the concept of stack frames as separate blocks of stack memory for each subroutine call.

Each subroutine creates a stack frame by saving registers and local variables on the stack. Nested calls create new stack frames on top of previous ones. This separation keeps data organized and prevents interference between subroutines.

Result

Multiple stack frames exist simultaneously, each corresponding to a nested call level.

Knowing about stack frames helps understand how nested calls manage local data safely.

5

Intermediate

Calling Conventions and Nested Calls

Concept: Explain how ARM calling conventions define rules for passing parameters and saving registers in nested calls.

ARM calling conventions specify which registers must be saved by the caller or callee. In nested calls, these rules ensure that important data is preserved across calls. For example, some registers are saved on the stack before calling another subroutine, so they can be restored after return.

Result

Consistent behavior in nested calls, avoiding data corruption and crashes.

Understanding calling conventions is crucial for writing reliable nested subroutine code.

6

Advanced

Handling Deep Nesting and Stack Overflow Risks

🤔Before reading on: do you think the stack size is unlimited for nested calls? Commit to yes or no.

Concept: Discuss the limits of stack size and risks of too many nested calls causing stack overflow.

Each nested call uses stack space for return addresses and local data. If calls nest too deeply without returning, the stack can run out of space, causing overflow and program crashes. ARM systems often have fixed stack sizes, so programmers must avoid excessive nesting or use techniques like tail calls to reduce stack use.

Result

Awareness of stack limits helps prevent crashes and design safer programs.

Knowing stack overflow risks guides better program structure and debugging.

7

Expert

Optimizations and Tail Call Behavior in ARM

🤔Before reading on: do you think all subroutine calls always add a new stack frame? Commit to yes or no.

Concept: Explain tail call optimization where the last action of a subroutine is calling another, allowing reuse of the current stack frame.

In some cases, when a subroutine calls another as its final action, the ARM compiler or programmer can optimize by replacing the call with a jump. This avoids adding a new stack frame, saving stack space and improving performance. This is called tail call optimization and is important in recursive or deeply nested calls.

Result

Programs run more efficiently and use less stack memory in certain nested call patterns.

Understanding tail call optimization reveals how ARM systems can handle deep recursion without stack overflow.

Under the Hood

When a subroutine is called in ARM, the processor saves the return address in the link register (LR). If the subroutine calls another, it must save LR on the stack to preserve the return address chain. Each nested call pushes a new return address and possibly registers onto the stack, creating a stack frame. The processor uses the stack pointer (SP) to track the top of the stack. Returning from a subroutine involves restoring LR and other saved registers from the stack and branching back to the saved return address.

Why designed this way?

ARM architecture uses the link register for efficient single calls to avoid unnecessary memory access. However, nested calls require saving LR on the stack to maintain correct return addresses. This design balances speed for simple calls and flexibility for nested calls. Using the stack for saving context allows unlimited nesting depth limited only by stack size, a common and proven approach in many CPU architectures.

┌───────────────┐
│ Main Program  │
└──────┬────────┘
       │ BL (call)
       ▼
┌───────────────┐
│ Subroutine A  │
│ Save LR to SP │
│ BL (call)     │
└──────┬────────┘
       ▼
┌───────────────┐
│ Subroutine B  │
│ Save LR to SP │
│ BL (call)     │
└──────┬────────┘
       ▼
┌───────────────┐
│ Subroutine C  │
│ Return using  │
│ BX LR         │
└──────┬────────┘
       ▲
Restore LR from SP
       ▲
Return to B
       ▲
Restore LR from SP
       ▲
Return to A
       ▲
Return to Main

Myth Busters - 4 Common Misconceptions

Quick: Does the link register (LR) automatically save all return addresses in nested calls? Commit to yes or no.

Common Belief: The link register always holds all return addresses, so no extra saving is needed.

Reality: The link register holds only the return address of the current call. Nested calls overwrite LR, so it must be saved on the stack to preserve previous return addresses.

Why it matters: Failing to save LR leads to incorrect returns, causing program crashes or unexpected behavior.

Quick: Can nested subroutine calls use unlimited stack space without problems? Commit to yes or no.

Common Belief: The stack is large enough to handle any number of nested calls without issues.

Reality: The stack size is limited. Excessive nesting can cause stack overflow, crashing the program or corrupting data.

Why it matters: Ignoring stack limits can cause hard-to-debug crashes in deeply nested or recursive programs.

Quick: Do all nested calls create new stack frames even if the call is the last action? Commit to yes or no.

Common Belief: Every subroutine call always creates a new stack frame regardless of context.

Reality: Tail call optimization can reuse the current stack frame if the call is the last action, saving stack space.

Why it matters: Not understanding tail calls can lead to inefficient code and unnecessary stack growth.

Quick: Is the stack only used for saving return addresses in nested calls? Commit to yes or no.

Common Belief: The stack only stores return addresses during nested subroutine calls.

Reality: The stack also stores local variables, saved registers, and sometimes parameters, not just return addresses.

Why it matters: Misunderstanding stack usage can cause bugs when local data is overwritten or corrupted.

Expert Zone

1

Some ARM processors have a dedicated link register but also support a frame pointer register to help manage complex stack frames in nested calls.

2

Compiler-generated prologues and epilogues automate saving and restoring registers, but manual assembly requires careful management to avoid subtle bugs.

3

Tail call optimization is not guaranteed; it depends on compiler settings and code structure, so programmers must understand when it applies.

When NOT to use

Nested subroutine calls are not ideal in real-time or deeply recursive systems with limited stack space; iterative solutions or explicit state machines are better alternatives to avoid stack overflow.

Production Patterns

In embedded ARM systems, nested calls are carefully managed with fixed stack sizes and watchdog timers. Critical functions often avoid deep nesting or use inline functions to reduce call overhead. Tail call optimization is used in recursive algorithms like parsing or state transitions to improve performance.

Connections

Call Stack in High-Level Languages

Nested subroutine calls in ARM correspond directly to call stacks in languages like C or Java.

Understanding ARM nested calls deepens comprehension of how high-level languages manage function calls and recursion at the machine level.

Recursion in Mathematics

Nested calls implement recursion by repeatedly calling subroutines with new parameters.

Knowing how nested calls work helps understand recursion's practical execution and limitations like stack overflow.

Task Switching in Operating Systems

Both nested calls and OS task switching save and restore execution context using stacks.

Recognizing this similarity clarifies how processors manage multiple tasks and function calls using similar mechanisms.

Common Pitfalls

#1 Not saving the link register before a nested call.

Wrong approach:

BL SubroutineB
; no push of LR before call

Correct approach:

PUSH {LR}
BL SubroutineB
POP {LR}

Root cause:

Assuming the link register preserves all return addresses automatically.

#2 Ignoring stack overflow risk in deep recursion.

Wrong approach:

void recursive() { recursive(); } // no stack limit check

Correct approach:

void recursive(int depth) { if(depth == 0) return; recursive(depth - 1); }

Root cause:

Not considering limited stack size and infinite recursion consequences.

#3 Creating unnecessary stack frames for tail calls.

Wrong approach:

SubroutineA:
PUSH {LR}
BL SubroutineB
POP {LR}
BX LR

Correct approach:

SubroutineA:
BX SubroutineB ; tail call optimization

Root cause:

Not recognizing when tail call optimization can be applied.

Key Takeaways

Nested subroutine calls allow programs to break tasks into smaller parts by calling subroutines within subroutines.

The ARM link register holds the return address for the current call but must be saved on the stack for nested calls to preserve return order.

Each nested call creates a stack frame to save return addresses, registers, and local data, enabling safe and organized execution.

Stack size is limited, so deep nesting risks overflow; understanding this helps design safer programs.

Tail call optimization can reduce stack usage by reusing stack frames when a call is the last action in a subroutine.