# Assignment1: RISC-V Assembly and Instruction Pipeline
###### tags: `Computer Architecture (Fall 2021)`

## Find the Highest Altitude ([1732. Find the Highest Altitude](https://leetcode.com/problems/find-the-highest-altitude/))

There is a biker going on a road trip. The road trip consists of ```n + 1``` points at different altitudes. The biker starts his trip on point ```0``` with altitude equal ```0```.

You are given an integer array ```gain``` of length ```n``` where ```gain[i]``` is the **net gain in altitude** between points ```i``` and ```i + 1``` for all ```(0 <= i < n```). Return the **highest altitude** of a point.

## Idea
When it read the ```gain``` by sequence, there is a variable ``altitude`` to update now altitude.Then there is the other variable ```highest``` to compare and record the altitude right now wether the hightest altitude. Finally print the ```highest```.

## C code

#include <stdio.h>
#define max(a, b) ((a > b) ? a : b)
int main()
{
    int gain[] = {-5,1,5,0,-7, -5, 10, 9, -4, 8, -4, 2, -4, 4, 3, -2}, len = 16;
    
    int altitude = 0, highest = 0;
    for(int i = 0; i < len; i++) {
        altitude += gain[i];
        highest = max(highest, altitude);
    }
    printf("%d", highest);

    return 0;
}

:::warning
Alternatively, you can rewrite as following:

int largestAltitude(int *gain, int gainSize)
{ 
    int r = 0, t = 0;
    for (int i = 0; i < gainSize; i++) {
        t += gain[i];
        if (t > r)
            r = t;
    }
    return r;
}     

:notes: jserv
:::

## Assembly Code

:::warning
TODO: Can you use fewer instructions?

:notes: jserv
:::

.data
gain:     .word -5,1,5,0,-7, -5, 10, 9, -4, 8, -4, 2, -4, 4, 3, -2
len:      .word 16

.text
main:
        la s0, gain         
        mv s1, zero # altitude = 0
        mv s2, zero # highest = 0
        lw s3, len
        mv t0, zero # i = 0
loop:
        lw t1, 0(s0)
        addi s0, s0, 4
        add s1, s1, t1 # altitude += gain[i];
        
        mv a2, s2 # max(highest, altitude);
        mv a3, s1
        jal max
        add s2, a0, zero
        
        addi t0, t0, 1 #i++
        blt t0, s3, loop
        
        mv a2, s2
        jal print
        
        li  a7, 10        # end program
        ecall
        
max:
        mv a0, a3
        blt a2, a3, maxReturn
        mv a0, a2
maxReturn:
        jr ra 
        
print:
        mv a0, a2
        li a7, 1
        ecall
        jr ra 

In this assembly code I try to use the function call ,so there have the ```max``` funtion to compare to number and the ```print``` function to print the result. Becuse of this I add the more jump instruction than optimal compilation.
I would want to use the sp pointer to push some register into the stack, but I think that may be to much redundancy in this code.

## Analysis

### Pseudo code

00000000 <main>:
	0:		10000417		auipc x8 0x10000
	4:		00040413		addi x8 x8 0
	8:		00000493		addi x9 x0 0
	c:		00000913		addi x18 x0 0
	10:		10000997		auipc x19 0x10000
	14:		0309a983		lw x19 48 x19
	18:		00000293		addi x5 x0 0

0000001c <loop>:
	1c:		00042303		lw x6 0 x8
	20:		00440413		addi x8 x8 4
	24:		006484b3		add x9 x9 x6
	28:		00090613		addi x12 x18 0
	2c:		00048693		addi x13 x9 0
	30:		020000ef		jal x1 32 <max>
	34:		00050933		add x18 x10 x0
	38:		00128293		addi x5 x5 1
	3c:		ff32c0e3		blt x5 x19 -32 <loop>
	40:		00090613		addi x12 x18 0
	44:		01c000ef		jal x1 28 <print>
	48:		00a00893		addi x17 x0 10
	4c:		00000073		ecall

00000050 <max>:
	50:		00068513		addi x10 x13 0
	54:		00d64463		blt x12 x13 8 <maxReturn>
	58:		00060513		addi x10 x12 0

0000005c <maxReturn>:
	5c:		00008067		jalr x0 x1 0

00000060 <print>:
	60:		00060513		addi x10 x12 0
	64:		00100893		addi x17 x0 1
	68:		00000073		ecall
	6c:		00008067		jalr x0 x1 0

There are some pseudo code have be transform, like the ``la`` ,``lw`` amd ``mv``.

In ``la`` and ``lw``, they will be split into two instruction.First is the ``auipc`` ,it can point to the head for the data block. In Second ``la`` and ``lw`` are a little different.
In ``la``, they will be transform to the ```addi```, it mean addi the interval from head to the space by value.Like 2th line, there add 0,Becuse gain is the frist vale in data block.
Then in ``lw`` ,they still be the ```lw```. but as stated above ,they will be add the interval. There are 16 word in ```gain``` , so add the 64. But result add 48, I think it maybe because of there is at 6th instrution. At 2th add 0 , so at 6th need subtract more 4 word. That equal 48.

In ``mv`` is simpler than above. They will be transform to the ``addi x8 x8 0``,becuse any number add 0 equal 0.

### System call
``ecall``makes me a little confused at first, so I search in the google. Then I find the graph below, it from a senior. This system services table tell as, which service and what it number.
Put the system call code into ``a7``,then call ``ecall``. PC will jump to system call and excute.
In this homework , I use the 1 to print integer and 10 to exit the program.