Explanation for Matrix Multiplication Conversion from MiniC to Cmd

Question

In the slides for compiler backend (RoSy) there are examples for converting MiniC-programs to Cmd. The last example is a matrix multiplication (if images are not fully visible, please open image in new tab, I did not find an option to attach files to the question; the example is from slides 21+43):

How exactly does the middle column work? So why are we creating index variables i*10 ? My understanding is that the matrix is automatically "flattened", meaning a 10x10 matrix is automatically converted to an array with 100 entries and then we need i*10 to access the former rows/columns of the matrix, since a[i][j] is not allowed in Cmd. Is this correct? 

edit: added note about images

Answer 1

You are absolutely right: A matrix as used in the example must be mapped to the linear memory, and also all array are mapped to the linearly addressed memory. If you try the above example that I copy here so that you can also copy it to the teaching tool compiler, you will see also the memory mapping as explained below:

thread MatrixMult {
    [10][10]nat a,b,c;
    nat i,j,k,n;
    while(i<n) {
        j = 0;
        while(j<n) {
         k = 0;
            while(k<n) {
                c[i][j] = c[i][j] + a[i][k]*b[k][j];
                k = k + 1;
            }
            j = j + 1 ;
        }
        i = i + 1 ;
    }
}

If you compile this program to Abacus assembler, the compiler shows you in the comments of the Abacus program the memory mapping: 

//    Mem[0300] : _t5
//    Mem[0000] : a
//    Mem[0100] : b
//    Mem[0200] : c
//    Mem[0300] : last allocated address

This means that matrix a is put into memory locations mem[0..99], matrix b is in mem[100..199], and matrix c is in mem[200..299], moreover, the temporary variable _t5 is put in memory address mem[300] since it could not be mapped to a register.

An element c[i][j] is then mapped to mem[i*10+j+200], so that you see the code 

0008 : _t3 := i * 10
0009 : _t4 := _t3 + j
0010 : _t5 := c[_t4]

The mapping to Abacus assembler is again more troublesome since we have to generate the constant 200 which is not that simple: We cannot simply write mov $7,200 since the direct operands are not allowed in that size. Hence, we need to generate some code that will compute that constant, and thus you will see the following code: 

    mov $7,0            // _t5 := c[_t4]
    mov $0,6            // 
    sft $7,$7,$0        // 
    mov $0,12           // 
    or $7,$7,$0         // 
    mov $0,4            // 
    sft $7,$7,$0        // 
    addiu $7,$7,8       // 

After this code, you find constant C8, i.e., 200 in decimal in register $7. You may think about a minimal code sequence to produce a desired constant like 200 in a specified register like $7. Such a function is implemented in the MiniC compiler for the above purpose.

Bytheway, as you can also see with the generated code, the MiniC compiler is quite bad in generating the index expressions in the sense that it computes many subexpressions like i*10 that are already available in a register again. A dataflow analysis to determine the available expressions in registers at some program line could be used to improve this. 

Comments

Thank you for the detailed answer, this makes it clear to me.