Procedural abstraction refers to the idea that you can write a piece of code once and then use it multiple times, This piece of code becomes a fundamental operation, much like a basic math operation or a simple command, and you can use it easily and conveniently .

In this example, there's a main program that includes two procedures, P and Q. The program calls procedure P, performs some computations, and then encounters a return statement. At another point, procedure Q is called, some operations are carried out, and then there's a return statement.

The execution of a procedure, the program must follow these six steps:

1. Transfer control to the procedure: The control flow is managed in a way that when a procedure completes, it goes back to the exact point where it was called. This requires a linkage process, Knowing the origin point is crucial, as calls can happen from various places, and the return must be directed accordingly. This linkage is a critical aspect of the process.
2. Parameters passing in procedure: Procedures have a set of parameters. When a procedure is called, data is sent into these parameters for the computation. Once the computation is complete, the results flow back to the calling program. So, some parameters bring values in, while others carry values back out to the caller.
3. Acquire storage resources for procedure: If you repeatedly call a function, each call is treated as a new allocation of storage. Managing this involves handling the storage allocation for each instance separately. Additionally, a procedure might need to access data that is defined both globally and locally. This means the procedure should be able to reach both global and local data for effective functionality.
4. Perform the desired task: Executing a specific task by using a pre-set set of instructions simplifies the overall design.
5. Return appropriate result: We need to know where you came from so that return can be appropriately made because call may occur from several different points and return has to be made accordingly.

Registers in procedure abstraction

Registers are the fastest place to hold data in a computer because they are physically located on the CPU chip, reducing access time. Their design prioritizes speed and low latency, making them ideal for temporarily holding small amounts of data that the CPU is actively processing,so we want to use them as much as possible . RISC-V software follows the following convention for procedure calling in allocating its 32 registers:

1. Register x10–x17: Eight parameter registers which is to pass parameters or return values.
2. Register x1: one return address register to return to the point of origin.

RISC-V assembly language includes an instruction just for the procedures:_*jump -and-link *_instruction. jump-and-link instruction :A command that jumps to a specific location in the program while also remembering where to go next by saving that address in a register.

Example:

jal x1, ProcedureAddress    // jump to Procedure Address and write return address to x1

ProcedureAddress: This is the destination address to which the program will jump. The control flow is transferred to this address.

x1: The address of the next instruction after the jump, will be stored in register x1

The "link" part of the name indicates that an address or link is created, pointing back to the place where the procedure was called, ensuring the procedure can return to the correct location. This "link," saved in register x1 and known as the return address,it is essential because the procedure might be called from different parts of the program.

we have jump-and-link register instruction :

Jump and link register: This instruction is used to jump to an address specified by a register and simultaneously save the address of the next instruction in the register specified.

Example:

jalr x0, 0(x1)

x0: the address of the next instruction after the jump, will be stored in register x0.

0(x1): This is the offset addressing mode. It means the address to jump to is calculated by adding the value stored in register x1 to the offset of 0. In other words, it's a direct jump to the address contained in x1.

Return address:

In a RISC architecture, the term "return address" is typically associated with subroutine or function calls. When a function is called, the address of the instruction following the function call (i.e., the return address) needs to be stored so that when the function completes, the program knows where to resume execution.

The return address is typically stored in a special-purpose register called the link register or return address register. In RISC-V we use x1 register for this purpose. Different RISC architectures may use different names for this register. To support the return from a procedure, RISC-V use an indirect jump, like the jump-and-link instruction (jalr).

Note: Before returning, we must restore the old values of the registers by “popping” them from the stack.

Different architecture may use different registers for storing return address. Some of them are:

ARM Architecture:

In ARM, the return address is stored in the link register (lr).

MIPS Architecture:

In MIPS, the return address is stored in the return address register ($ra).

Caller

The program that initiate a procedure and provides the necessary parameter values.

Callee

A procedure that executes a series of stored instructions based on parameters provided by the caller and then returns control to the caller.

---

Registers in MIPS

1. Register $a0-$a3: These are the registers that work as inputs to procedure during parameter passing in MIPS.
2. Register $v0, $v1: These are the registers that work as outputs of procedure.
3. Register $ra: It is the return address register.

---

PROGRAM COUNTER

The stored-program idea is a fundamental concept in computer architecture. It suggests that both program instructions and data can be stored in the computer's memory. To do this, there must be a way to keep track of the memory address of the current instruction being executed.

This is accomplished by the program counter (PC), a register—a compact, quick storage area inside the CPU It holds the memory address of the next instruction to be fetched and executed.

After an instruction is fetched, the program counter is typically incremented to point to the next memory address. Different architectures may use slightly different terms, such as "instruction pointer" or "instruction address register," but the core functionality remains the same.

The program counter is not explicitly one of the registers (x0 to x31) in RISC-V. Instead, the program counter is managed by the control logic of the processor.

STACK POINTER (x2)

A procedure in RISC-V has a fixed number of registers (eight argument registers x10-x17). When a function requires more registers than are available, certain registers may be temporarily "spilled" onto the stack to make room for further computations. The stack is used to allocate space for local variables, creating a "stack frame" for each function. This allows functions to have private, temporary storage without interfering with others.

stack—a last-in-first-out (LIFO) queue.

A stack needs a pointer to show where the next procedure should place the registers to be placed or where old register values are found. In RISC-V, the stack pointer is registered *x2, also known by the name *sp. Adjusting the stack pointer facilitates the allocation and deallocation of space for registers during function calls. The stack pointer is adjusted by one doubleword (typically 8 bytes in RISC-V) for each register that is saved or restored.

Placing data onto the stack is referred to as a "push" operation. This involves storing data, such as register values, at the memory location pointed to by the stack pointer. Decrements the current stack pointer and stores data to the stack.

Removing data from the stack is referred to as a "pop" operation. This involves retrieving data from the memory location pointed to by the stack pointer and adjusting the stack pointer accordingly. Reads the data from the stack and increments the current stack pointer.

Simple procedure without including nested or recursive procedures:

In simple procedures we make a call to a function and return to the origin point after execution of that function. The function body doesn't include any further function calls. Let us consider an example for better understanding of how compilation of a simple procedure works in RISC-V architecture.

The original C code procedure is given below:

long long int simple_procedure (long long int a, long long int b, long long int c)
{
long long int f;
f = (a + b) −(c * 8);
return f;
}

Above code represents a function definition in C with return type long long int which is a signed datatype of 64 bit(8 bytes) wide. It performs arithmetic operation on 4 variables which are all of long long int too.

Compiled RISC-V assembly code:

simple_procedure:
addi sp, sp, -24  //-----> provide 3 stack rooms 
sd x5, 16(sp)     //-----> store value of x5 at (stack pointer + 16)th location
sd x6, 8(sp)      //-----> store value of x6 at (stack pointer + 8)th location
sd x20, 0(sp)     //-----> store value of x20 at (stack pointer + 0)th location
add x5, x10, x11  //-----> register x5 contains a + b
slli x6, x12, 3  //-----> register x6 contains c * 8
sub x20, x5, x6   //-----> f = x5 − x6, which is (a + b)−(c * d)
addi x10, x20, 0  //-----> returns f (x10 = x20 + 0)
ld x20, 0(sp)     //-----> restore register x20 for caller
ld x6, 8(sp)      //-----> restore register x6 for caller
ld x5, 16(sp)     //-----> restore register x5 for caller
addi sp, sp, 24   //-----> adjust stack to delete 3 items
jalr x0, 0(x1)    //-----> branch back to calling routine

Initially the procedure is called by the caller by jump and link instruction to "simple_procedure". i.e.,

jal simple_procedure

On doing so the PC jumps to callee after storing PC + 4 in return address register x1.
Next step is to store/push the old values of x5, x6 and x20 registers into stack. The stack pointer register(sp) contains the highest location preset. Subtracting value from the stack pointer results in expansion of stack and adding value shrinks the stack. For pushing values to stack we need to follow below steps:

1. We first need to subtract the value from sp register to create rooms in stack(stack expansion). In the above example we need to create 3 rooms for 3 doublewords, this value is computed as (16 x 3) i.e., (doubleword x 3) = 24
2. We then store values at stack locations in the order of higher memory location to lower memory location. This is done by providing right offset values in store doubleword instruction.

In the above diagram we have considered an example where sp register has value preset to 64'h28 and thus it points to corresponding memory address 64'h28.

In the above diagram we have allocate 3 doubleword room stack by subtarcting 24. Thus now sp points to 64'h10 and the values from x5, x6 and x20 are pushed to 64'h10, 64'h18 and 64'h20.

This procedure is done due to the concept of saving and restoring old values of registers. As per the register convention:

• x5−x7 and x28−x31: temporary registers that are not preserved by the callee (called procedure) on a procedure call
• x8−x9 and x18−x27: saved registers that must be preserved on a procedure call (if used, the callee saves and restores them) In the above example we use register x5, x6 and x20. x5 and x6 are temporary registers and need not be preserved. Hence we can drop the 2 store and 2 load instructions corresponding to x5 and x6. However storing and loading x20 is necessary.

Thus above code can be rewritten as:

simple_procedure:
addi sp, sp, -24  //-----> provide 3 stack rooms 
sd x20, 0(sp)     //-----> store value of x20 at (stack pointer + 0)th location
add x5, x10, x11  //-----> register x5 contains a + b
slli x6, x12, 3  //-----> register x6 contains c * 8
sub x20, x5, x6   //-----> f = x5 − x6, which is (a + b)−(c * d)
addi x10, x20, 0  //-----> returns f (x10 = x20 + 0)
ld x20, 0(sp)     //-----> restore register x20 for caller
addi sp, sp, 24   //-----> adjust stack to delete 3 items
jalr x0, 0(x1)    //-----> branch back to calling routine

---

Stack in MIPS

In MIPS ISA, the procedure abstraction for a simple procedure is same as that of RISC-V, however we can notice certain changes interms of stack push and pop. In MIPS, we do not initially allocate stack rooms by subtracting stack pointer, instead we move the stack pointer one location above as we push value to the stack by subtracting 4(for storing word) from stack pointer. The push and pop operations in MIPS is given as:

Push : addi $sp, $sp, -4
       sw $ra, 0($sp)
Pop  : lw $ra, 0($sp)
       addi $sp, $sp, 4

---

After storing x20 in stack, we need to perform (a + b). a and b are parameters to the procedure and they must be passed through parameter registers ranging from x10 to x17. Here we have considered a to be present in x10 and b to be present in x11. The result of addition is stored in x5. We need to then perform (c x 8). c is represented by x12. To multipy by 8 we can perform shift left by 3 times and store the result in x6. Finally we perform addition of the 2 results and store final result in x20. After computation is done, we move the value of x20 to x10. x10 represents return value register. We then restore the value of x20 register using load/pop from stack instruction. Finally we jump back to the origin point using return address register, x1.

Non-Leaf Procedure

Procedures that call other procedures

• For nested call, caller needs to save on the stack:

  – Its return address

  – Any arguments and temporaries needed after the call

• Restore from the stack after the call

Let's take an example:

       long long int fact (long long int n)

       {

           if (n < 1) return n;

           else return n * fact(n - 1);

       }

– Argument n in x10

– Result in x10

• It is a recursive function

RISC-V code:

    jalr x1, fact         //call the fact and x1 will have the address of the next instruction  
    j Exit
    fact:
         addi sp,sp,-16      //Adjust stack for two items
         sd x1,8(sp)        //Save return address and n on stack
         sd x10,0(sp)      //Save the argument n
         addi x5,x10,-1    //x5 = n - 1
         bge x5,x0,L1      //if n >= 1, go to L1
         addi x10,x0,1     //Else, set return value to 1
         addi sp,sp,16     //Pop stack, don’t bother restoring values
         jalr x0,0(x1)     //Return
     L1: 
         addi x10,x10,-1   //n = n - 1
         jal x1,fact       //call fact(n-1)
         addi x6,x10,0     //move result of fact(n - 1) to x6
         ld x10,0(sp)      //Restore caller’s n
         ld x1,8(sp)       //Restore caller’s return address
         addi sp,sp,16    //Pop stack
         mul x10,x10,x6   //return n * fact(n-1)
         jalr x0,0(x1)    //return
    Exit:

Let's consider sp is at 64'h50

Argument n in x10

Return address is x1

Pass argument as 3

Iterative implementation of Recursive Procedure:

• Iterative procedures offer performance advantages over recursive ones by eliminating the overhead associated with maintaining call stacks.
• This shift reduces memory consumption and enhances execution speed, critical for tasks in environments with limited stack space.
• However, while iteration boosts performance, it can sometimes sacrifice code readability.

Let's take an example:

 long long int sum (long long int n, long long int acc) {
 if (n > 0)
 return sum(n − 1, acc + n);
 else
 return acc;
       }

RISC-V code:

  // x10 has n value
  // x11 = acc
  // x12 holds result    
 sum: ble x10, x0, sum_exit // go to sum_exit if n <= 0
 add x11, x11, x10 // add n to acc
 addi x10, x10, -1 // subtract 1 from n
 jal x0, sum // jump to sum
 sum_exit:
  addi x12, x11, 0 // return value acc
  jalr x0, 0(x1) // return to caller

Recursive Method Example:

Sorting Example

 const m=20;
 void main(void) {
   int N,i;
   int X[m], y[m];
   // enter the N Value
   for (i=0; i<N; i++)
    //enter the Number of integers 
   
   sort ( X, Y, N) ;          //calling the sort function
  }

  void sort( int A[], int B[], int n) {
   int A1[m], A2[m];
   int n1, n2;
   if( n ==1) B[0] = A[0];
   else {
       n1 = n/2 ;
       n2 = n-n1;
       merge ( A1, A2, B, n1, n2);  //calling merge function
  }

  void merge ( int P[], int Q[], int R[], int p, int q) {
   int i,j,k;
   i = j = k = 0;
   while ( i<p && j<q)
     if( P[i] < Q[j]) R[k++] = P[i++];
     else R[k++] = Q[j++];
   while ( i<p) R[k++] = P[i++];
   while ( j<q) R[k++] = Q[j++];
}

RISC-V code:

# merge procedure

lw x13, 4(sp)        
L:bge x10, x13, X      
muli x14, x10, 4     
add x14, x14, x2     
lw x16, 0(x14)      
addi x10, x10, 1       
muli x15, x12, 4     
add x15, x15, x2      
sw x16, 0(x15)      
addi x12, x12, 1     

# calling merge(A1, A2, B, n1, n2) 
addi x10, sp, 0       
addi x11, sp, 80  
addi x12, sp, 176  
lw x24, 160(sp)        
sw x24, -8(sp)         
lw x24, 164(sp)        
sw x24, -4(sp)         
addi sp, sp, -12       
jal merge              

# calling sort(A, A1, n1)
sw x1, 168(sp)         
lw x24, 172(sp)        
sw x24, -12(sp)        
addi x24, sp, 0        
sw x24, -8(sp)         
lw x24, 160(sp)        
sw x24, -4(sp)         
addi sp, sp, -184      
jal sort               

# return from merge

lw x1, 168(sp)         
addi sp, sp, 184       
jr x1                  

Activation Record

Variables that are specific to the procedure but do not fit in registers, like local arrays or structures, are likewise kept on the stack. The section of the stack that holds the local variables and stored registers of a procedure is called a Procedure Frame or Activation Record.

Calling merge

When merge procedure is called activation record is created on the top of the sort activation record. When this call is executed, a new record is created on the top of the stack and the registers are filled with the appropriate values.

Returning from merge:

We have to dispose the activation record which is created. At the top there is activation record for merge; at the bottom there is record for sort and registers are containing parameters and temporary data. So, before you could return basically these three statements before returning you must bring the return address into ra(x1) register.

lw x1, 0(x2)         # lw $ra, 0($sp)                             
addi x2, x2,12       # addi $sp, $sp,12
jr x1                # jr $ra