1. Write a procedure that reverses order of a 1-D array using the stack. The arr
ID: 3690898 • Letter: 1
Question
1. Write a procedure that reverses order of a 1-D array using the stack. The array is a string array, and the address along with the number of elements are passed though the stack. Then write a complete program to test your procedure. USING MIPS
EXAMLE
2. MIPS REGISTER USE:
A convention regarding the use of registers is necessary when software is a team effort. In this case each member must know how registers are supposed to be used such that her piece of software does not conflict with others’.
Since almost nobody does assembly programming anymore, you may ask why such a convention is still necessary. Well, it’s the compiler who needs to know about it. It is mostly because an executable can be created from pieces that are compiled separately: the compiler then makes the assumption that they all have been compiled using the same convention.
To compile a procedure, the compiler must know which registers need to be preserved and which can be modified without worry. These rules for register-use are also called procedure call conventions.
There is nothing to prevent you from ignoring these rules. After all they are not enforced by hardware mechanisms. But, if you choose to not follow the rules, then you call for trouble in the form of software bugs. And some of these bugs may be very vicious.
The following table presents the MIPS register usage convention.
Register Number
Register Name
Usage
0
zero
Always zero
1
$at
Reserved for the assembler
2-3
$v0-$v01
Expression evaluation and procedure return results
4 - 7
$a0 - $a3
The first four parameters passed to a procedure. Not pre-
served across procedure calls
8 - 15
$t0 - $t7
Temporary registers. Not preserved across procedure calls
16 - 23
$s0 - $s7
Saved values. Preserved across procedure calls
24 - 25
$t8 - $t9
Temporary registers. Not preserved across procedure calls
26 - 27
$k0 - $k1
Reserved for kernel usage.
28
$gp
Global pointer (pointer to global area)
29
$sp
Stack pointer
30
$fp
Frame pointera
31
$ra
Return address
$f0 - $f2
Floating point procedure results
$f4 - $f10
Temporary registers. Not preserved across procedure calls
$f12 - $f14
The first two floating point parameters. Not preserved
across procedure calls
$f16 - $f18
Temporary floating point registers. Not preserved across
procedure calls
$f20 - $f30
Saved floating point values. Preserved across procedure
calls
aThe MIPS compiler does not use a frame pointer (as gcc does). In this case register 30 is called $s8 and is used like any of the registers $s0 to $s7.
“Not preserved across procedure calls” means that the register may change value if a procedure is called. If some value is stored in that register before the procedure is called, then you may not make the assumption that the same value will be in the register at the return from the procedure.
“Preserved across procedure calls” means that the value stored in the register will not be changed by a procedure. It is safe to assume that the value in the register after the procedure call is the same as the value in the register before the call.
3. HOW PROCEDURES WORK
There are six steps that need to be accomplished in order to call and return from a procedure:
Place parameters in a place where the procedure can access them.
Transfer control to the procedure
Acquire the storage resources needed for the procedure.
Execute the procedure
Place the result value in a place where the calling program can access it.
Return control to the point of origin.
MIPS software follows the following convention in allocating its 32 registers for procedure calling:
$a0 – $a3: four argument registers in which to pass parameters
$v0 – $v1: two value registers in which to return values
$ra: one return address register to return to the point of origin
The code that calls the procedure executes a jal instruction, which saves the address of the following instruction (PC+4) in register $ra and then loads PC with the address of the desired subroutine, thereby branching to the subroutine. The subroutine then executes just as any other code would. Procedures can – and often do – contain calls to other procedures; in fact, properly designed subroutines can even call themselves, a practice known as recursion.
When the subroutine has finished its task, it executes a jr $ra instruction, which jumps to the address stored in register $ra. This causes execution of the calling routine to resume at the instruction following the jal X instruction.
However, since the procedure may utilize any registers needed by the caller, those registers must be preserved before the procedure called and then be restored back after the procedure completed the tasks.
The ideal data structure for spilling registers is a stack. MIPS software allocates $sp to track as the top of stack (TOS). The stack grows from higher address to lower address.
4. STACK MANIPULATION
The MIPS architecture does not explicitly support stack operations. In MIPS, we have to manipulate the stack pointer register to implement the stack.
4.1 PUSH operation
We have to decrement $sp to make room for the value being pushed onto the stack. For example, if we want to push the contents of $a0, we have to reserve four bytes of stack space and use the sw instruction to push the value as shown below:
addiu
$sp,$sp,-4
# reserve 4 bytes of stack
sw
$a0,0($sp)
# save the register
4.2 POP operation
The operation can be implemented by using the load and add instructions. For example, to restore the value of $a0 from the stack, we use the lw instruction to copy the value and increment $sp by 4 as shown below:
lw
$a0,0($sp)
# restore the two registers
addiu
$sp,$sp,-4
# clear 4 bytes of stack
5. PRESERVING REGISTERS
To preserve registers efficiently, MIPS software separates 18 of the registers into two groups:
$t0 – $t9: 10 temporary registers that are NOT preserved by the called procedure on a procedure call. It is the caller's responsibility to preserve any of them.
$s0 – $s7: 8 saved registers that must be preserved on a procedure call (if used, the called procedure saves and restores them).
6. NESTED PROCEDURES
Procedures that do not call others are called leaf procedures. Non-leaf procedures must push all necessary registers before calling other procedures.
EXAMPLE
The following is a complete program consisting of a main program and a procedure.
.data
array: .word -4, 5, 8, -1
msg1: .asciiz " The sum of positive values= "
msg2: .asciiz " The sum of negative values= "
.globl main
.text
main:
li $v0, 4
la $a0, msg1
syscall
la $a0, array # Initialize address parameter
li $a1, 4 # Initialize length parameter
jal Sum # Call sum function
addu $a0, $v0, $0 # sum of positive returned in $v0
li $v0, 1
syscall
li $v0, 4
la $a0, msg2
syscall
addu $a0, $v1, $0 #sum of negative returned in $v1
li $v0, 1
syscall
li $v0, 10
syscall
Sum: addu $v0, $0, $0
addu $v0, $0, $0
Loop: blez $a1, Return
addi $a1, $a1, -1
lw $t0, 0($a0)
addiu $a0, $a0, 4
blez $t0, neg
addu $v0, $v0, $t0
j Loop
neg: add $v1, $v1, $t0
j Loop
Return: jr $raBottom of Form
Register Number
Register Name
Usage
0
zero
Always zero
1
$at
Reserved for the assembler
2-3
$v0-$v01
Expression evaluation and procedure return results
4 - 7
$a0 - $a3
The first four parameters passed to a procedure. Not pre-
served across procedure calls
8 - 15
$t0 - $t7
Temporary registers. Not preserved across procedure calls
16 - 23
$s0 - $s7
Saved values. Preserved across procedure calls
24 - 25
$t8 - $t9
Temporary registers. Not preserved across procedure calls
26 - 27
$k0 - $k1
Reserved for kernel usage.
28
$gp
Global pointer (pointer to global area)
29
$sp
Stack pointer
30
$fp
Frame pointera
31
$ra
Return address
$f0 - $f2
Floating point procedure results
$f4 - $f10
Temporary registers. Not preserved across procedure calls
$f12 - $f14
The first two floating point parameters. Not preserved
across procedure calls
$f16 - $f18
Temporary floating point registers. Not preserved across
procedure calls
$f20 - $f30
Saved floating point values. Preserved across procedure
calls
Explanation / Answer
include<stdio.h>
#include<stdlib.h>
#define bool int
struct sNode //here is a stack node structure
{
char data;//initialization
struct sNode *next;
};
void push(struct sNode** top_ref, int new_data);
int pop(struct sNode** top_ref);//method used to pop
bool isEmpty(struct sNode* top);//which used to find empty stack
void print(struct sNode* top);//used to print node
//This is driver program
int main()
{
struct sNode *s = NULL; //here the node declared as null
push(&s, 4);//push 4 to stack
push(&s, 3);//push 3 to stack
push(&s, 2);//push 2 to stack
push(&s, 1);//push 1 to stack
printf(" Original Stack ");// display original Stack
print(s);
reverse(&s);
printf(" Reversed Stack ");// display Reversed Stack
print(s);
getchar();
}
// here is a bool function to check whether the stack is empty
bool isEmpty(struct sNode* top)
{
return (top == NULL)? 1 : 0;//here top return null value
}
// this void method used to push the item to stack
void push(struct sNode** top_ref, int new_data)
{
//here new node can be allocated
struct sNode* new_node =
(struct sNode*) malloc(sizeof(struct sNode));
if(new_node == NULL)
{
printf("Stack overflow ");//display Stack overflow
getchar();
exit(0);
}
//here the new node tends to data
new_node->data = new_data;
// here put link new node
new_node->next = (*top_ref);
// move to new node
(*top_ref) = new_node;
}
//this function is used to pop item from stack
int pop(struct sNode** top_ref)
{
char res;
struct sNode *top;//structure node top
//this is show error if stack is empty
if(*top_ref == NULL)
{
printf("Stack overflow ");//display Stack overflow
getchar();
exit(0);
}
else
{
top = *top_ref;
res = top->data;
*top_ref = top->next;
free(top);
return res;
}
}
//this method is used to pront the linked list
void print(struct sNode* top)
{
printf(" ");
while(top != NULL)
{
printf(" %d ", top->data);
top = top->next;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.