Could you give me some guidance on how to efficiently design an assembly language program?

Question

I'm a CS student at university, and I'm supposed to develop a MIPS assembly language program for an exam, but I do have a hard time designing it, especially when it comes to assigning registers, following calling conventions, saving registers on stack... It all seems to get pretty confusing and overwhelming rather fast, I lose track!

I don't have a problem figuring out, at least conceptually, an algorithm to solve a specific problem. It has more to do with the bigger picture, the overall structure and design of the project.

In light of this, could you point out a pattern, give tips or best practices to follow to sort everything out prior to actually writing code, so I don't lose myself in the process?

Answer 1

MIPS is a very unique language compared to other high level languages like Java OR Python, so it takes some time to get used to it. The way I would recommend about going with program development in MIPS is by doing the following:

1. Make sure you understand and memorize each MIPS instruction that your professor has informed you about or that you know you will be tested on. Understand that MIPS has no if statements so you must create them all from scratch.
2. Make sure you understand what data types each register can be loaded with, $t, $s etc.
3. If you cannot do the first 2 steps, it will be near impossible to create an effective program in MIPS. So the next step is getting some scrap paper or a part of the exam where you can write on and start jotting down what you want your program to do, consider all the MIPS instructions you have and attempt to realize which instruction suits best for each task. Consider if you need to create any if statements or loops and use the appropriate branch or jump instruction. I truly believe it comes down to memorizing and truly understanding what each instruction does and which registers to accompany it with to develop good MIPS code.

Answer 2

Generally speaking, what I recommend for the efficient design of assembly language code is the following steps:

Write out the algorithm in C and run it and test it to make sure it works.  Then translate that to assembly language rather mechanically and without gratuitous changes.

Developing an algorithm directly in assembly is hard, and, fixing algorithm bugs in assembly is not a lot of fun, in part because what might appear as a small change in the algorithm can have a dramatic effect on the assembly code.

Many have the urge to make improvements in a given algorithm for assembly — resist that — go back and make those same improvements in the C version, then test to make sure it still works.

Your C code may contain data structures, global data, and functions having statements and expressions.

For statements, convert control flow structures to if-goto-label form.  C supports if-goto-label.  You can substitute each structured statement (if,while,for) for something using if-goto-label.  You can do this in any order, too, one structured statement converted at a time to if-goto-label, and still test the resulting C code to make sure it continues working.

Also, simplify all if-goto statements, e.g. such that you have removed &&s and ||s.  This means splitting conjuctions and disjunctions into multiple if-goto statements.

Translate complex expressions into assignments connected by short-lived variables, so as to expose and make explicit these short-lived variables.  For example, in return fib(n-2) + fib(n-1), we can introduce temporary variables to hold the function call result: int t1 = fib(n-2); int t2 = fib(n-1); return t1+t2.  This makes clearer that we need some temporary variables, and that one of these, t1, is live across a function call so needs different physical storage (of call-surviving duration) than t2, which only needs short-term storge.

Once you have that, you can begin translation of the C to assembly.

During translation of C code to assembly, first translate data structures (if needed), then translate global data, then translate functions.

For functions, translate parameters & all local variables (assign variables to registers or memory).  Assigning storage for variables requires an analysis of how the variables are used by the function implementation.

Formal parameters are relatively easy, they follow the calling convention.  However, you need to perform an analysis on the usage of formal parameters and local variables within the function itself.  Any variable that is live across a function call will need some help from memory to survive those function calls.  If a formal parameter, that on function entry is in a parameter register and this variable is live across a function call, it will have to be moved to a safe place.  Any variables that are not live across a function call can be left in parameter and/or use temporary registers.

Then translate statements, then translate the expressions in those statements (e.g. assignments, conditional test, function calls).  Keep the order of the exiting C code and translate piece parts in the same orientation in assembly as they are in the C code.  Your code will already be in if-goto-label form so just take that rather directly to assembly language.

---

Each of these steps are, individually, fairly small, and can be mastered by following the proper rules and equivalence patterns.