CODEWITHSUNDEEP
coptimizationassemblydlx
Dor
Dor

Reputation: 7494

ASM - Optimized `for` loop

In homework I received a task to change a C code to ASM of simplified DLX:

a = 0;
for (i = 1; i < 14; i++)
    a = a + c;
A[0] = a;

My solution:

Assuming:

Then:

addi R1 R0 0    // init a = 0
addi R3 R0 1    // init i = 1
slti R5 R3 14   // test (i < 14) ; R5 = 1 if i < 14
beqz R5 3       // branch 3 lines of R5 == 0
add R1 R1 R2    // a = a + c
addi R3 R3 1    // i++
beqz R0 -5      // return up to the condition of the for loop
sw R1 R4 0      // A[0] = 0

Their solution:

Assuming:

Then:

addi R1 R0 0    // a = 0
addi R2 R0 1    // i = 1
add R1 R1 R3    // a = a+c
addi R2 R2 1    // i++
slti R5 R2 14   // R5=1 iff i<14
bnez R5 -4      // jump 4 lines up from the next line if
                // R5!=0, that is if i<14
sw R1 R4 0      // store the new value of A[0]=a (R1)

Difference:

Their solution is obviously better because that there's 1 less command - my code has an additional conditional branching. Their code is exactly what I wanted to do in the first place, but then I recalled of the for loop algorithm:

  1. Initialize a variable
  2. Check if condition is True.
    If True: Apply commands within the loop,
    Otherwise: exit the loop.
  3. Increment variable
  4. return to #2

So their code differs from the for loop algorithm, because that it doesn't check the condition (#2) after the initialization (#1)...
I thought to myself - is this the result of an optimization? What level of optimization is this? (IIRC there are 4 levels: O0, O1, O2, O3)
Is it expected to optimize code by default when interpreting a C code?

Upvotes: 1

Views: 308

Answers (1)

Aracthor
Aracthor

Reputation: 5907

When an optimization is activated, your compiler review its assembly code in order to see if there is anything to improve, in particular avoid useless instructions or check.

For instance, in your code, the for loop is an initialization, then a classic while loop. A classic optimization is to check if a while condition can be false at the first entry, and if not, transform it in a do while loop.
This is precisely your case. i < 14 cannot be false if you check it just after an instruction meaning i = 1. So it is faster to run:

a = 0;
i = 1;
do
{
    a = a + c;
    i++;
} while (i < 14);
A[0] = a;

So yes, it is a form of optimization. But when you code directly in assembly language, you are usually expected to do this kind of tricks, because the goal of assembly programming (and mainly learn it) is to make your code as fast as possible, using any possibilities to reduce instruction calls.

This is a result of level O1 optimization on GCC.

Upvotes: 2

Related Questions