How do I do dIvision and modulo with powers of 2 in MiniC/Abacus?

Question

I tried the following good-for-nothing MiniC-Code in the MiniC-Compiler-Webtool:

procedure Initialize([]nat x,nat xlen) {
    nat i;
    for(i=0..xlen-1)
        x[i] = i / 2;
        //x[i] = i % 2;
     return;
}

thread t {
    [10]nat x;
    nat xlen;
    xlen = 10;
    Initialize(x,xlen);
}

The first thing that I noticed was that I may not place the array allocation [10nat x; in between the variable assignment xlen = 10; and the function call Initialize(x,xlen);. The compiler tells me that [ was unexpected. What am I doing wrong here?

Also, I noticed a slight difference in division and modulo with powers of two. The division turns out as

    diviu $3,$1,2       // _t2 := xlen / 2

while the modulo is compiled to

    mov $3,2            // _t3 := 2
    divu $3,$1,$3       // _t2 := xlen % _t3
    ovf $3              //

The division is straight forward. It just does a constant division of $1 by 2 and stores it in $3. The modulo uses the overflow register to overwrite $3 with the result remainder of the division. But in contrast to the division, it does not use the constant division but the operation with two register operands. Why this distinction?

Then there are a few things in the Abacus code that I'd do differently if I'd handwrite it. I'd do the constant division with 2ⁿ as an n-bit right shift and the modulo by 2ⁿ either as an AND with 2ⁿ-1 or with a (registerwidth - n)-bit left-and-then-right shift. How would I write my MiniC-Code in order to obtain the said Abacus Code?

Answer 1

Type definitions in MiniC and C are different, and in my opinion cleaner in MiniC than in C. Types are types, and names are names, and in MiniC a declaration has the form <type> <name> to declare a variable with a name and a type. In C, it depends what kind of type it is, for arrays the dimensions are added to the name while the rest of the type is written in front of it. So, it was intentionally defined differently in MiniC to clearly distinguish between types and names (also when implementing the language, you will have a data type for its types where arrays will be one of the possible types).

About div and mod: Essentially all algorithms to compute one of the two will also compute the other one. Hence, having computed (x div y), we also have somewhere (x mod y), and if we need both, there would be no need to recompute what we already have. The problem was just that RISC instructions do not provide more than one target register. So, the solution was to use the overflow register in this case for (x mod y) which is used for addition and multiplication to compute the upper half of a double-precision result. Indeed, to compute (x mod y), it is therefore correct in the assembly code to have computed (x div y) to get (x mod y) from the overflow register.

Simplification of div and mod as well as multiplication with powers of 2 can be done by a code optimizer, but that does not generalize easily to other operands.

Comments

Well. I still don't really understand why a) compiles correctly, and b) doesn't.

a)
    [10]nat x;
    nat xlen;
    xlen = 10;
    Initialize(x,xlen);

b)
    nat xlen;
    xlen = 10;
    [10]nat x;
    Initialize(x,xlen);

About implementing modulo mod as a by-product of div: Thank you for clarifying this. But I'm still haven't understood why one piece of code compiles to diviu while the other one compiles to divu with a register that constantly contains value 2.

About the simplification by shift: So the right solution would running an optimizer on the Abacus-Code? Is there any way to directly trigger use shift operations from MiniC?

---

The reason why a) compiles while b) does not is as follows: The MiniC syntax expects as body statements of threads, functions and procedures a local declaration followed by a statement. This is the case for a), but not for b), since after the declaration nat xlen, there is an assignment, so no further declarations are expected. To make b) work, you have to use braces (which defines a local declaration with a scope), i.e.,

    nat xlen;
    xlen = 10;
    {
      [10]nat x;
      Initialize(x,xlen);
    }

You next question why mod did not make use of a diviu while the corresponding division operations does: This was a bug (or better a missing opportunity for code optimization). It is fixed now, please try.

The final question about using shift instead of arithmetic operators: There is no possibility yet since MiniC does not offer shift operations at the moment, so that you cannot implement it in the source code. And there are not yet code optimizers that take care of this optimization. That has to be added later.

---

The tested case works perfectly now! Thank you for changing it!