Raspberry Pi Compiler

Introduction

As mentioned at the end of the previous part, in this second part of this chapter we will complete the Tinsel extensions by implementing bit-wise operations and pointers.

Bit-wise Operations

I will implement bit-wise And, Or, Xor and Not operations. And will be at the same level of priority as multiply, divide, shift and modulo, so it will be another one of mullOps. Or and Xor will be at the same level of priority as add and subtract so it will be another one of addOps. Not will be implemented at the same part of the code code where the unary minus is processed.

Let’s add the respective Tinsel operators to our tokens list first: & | ^ and ~

    languageTokens.add(
        Token("&",     Kwd.andOp,      TokType.mulOps)
    )    
    languageTokens.add(
        Token("|",     Kwd.orOp,       TokType.addOps)
    )
    languageTokens.add(
        Token("^",     Kwd.xorOp,      TokType.addOps)
    )
    languageTokens.add(
        Token("~",      Kwd.notOp,      TokType.none)
    )

And will be parsed in parseTerm:

fun parseTerm(): DataType {
    val typeF1 = parseSignedFactor()
    while (inp.lookahead().type == TokType.mulOps) {
        ...
        when (inp.lookahead().encToken) {
            ...
            Kwd.andOp -> bitwiseAnd(typeF1)
            ...
        }
    }
    return typeF1
}

Or and Xor will be parsed in parseExpression:

fun parseExpression(): DataType {
    val typeT1 = parseTerm()
    while (inp.lookahead().type == TokType.addOps) {
        ...
        when (inp.lookahead().encToken) {
            ...
            Kwd.orOp -> bitwiseOr(typeT1)
            Kwd.xorOp -> bitwiseXor(typeT1)
            ...
        }
    }
    return typeT1
}

Not will be parsed in parseSignedFactor:

fun parseSignedFactor(): DataType {
    val factType: DataType
    if (inp.lookahead().encToken == Kwd.addOp)
        inp.match()
    if (inp.lookahead().encToken == Kwd.subOp) {
        inp.match()
        ...
    }
    else if (inp.lookahead().encToken == Kwd.notOp) {
            inp.match()
            factType = parseFactor()
            checkOperandTypeCompatibility(factType, DataType.none, NOT)
            code.notAccumulator()
        }
    else
        factType = parseFactor()
    return factType
}

The implementation of these operations is done with functions like the one below (for and) that parse the second operand, check the types and then call the corresponding function in the numeric module (same as all the other operations)

fun bitwiseAnd(typeF1: DataType) {
    inp.match()
    val typeF2 = parseFactor()
    checkOperandTypeCompatibility(typeF1, typeF2, AND)
    when (typeF1) {
        DataType.int -> andNumber()
        else -> {}
    }
}

fun bitwiseOr...

fun bitwiseXor...

The corresponding functions in OpsNumeric that implement these operations are all effectively one-liners:

/** process bitwise and */
fun andNumber() {
    code.andAccumulator()
}

/** process bitwise or */
fun orNumber() {
    code.orAccumulator()
}

/** process bitwise xor */
fun xorNumber() {
    code.xorAccumulator()
}

In the code module, bit-wise and, or and xor are quite straightforward (pop from the top of the stack and apply the operation with the accumulator)

    /** and top of stack with accumulator */
    override fun andAccumulator() {
        outputCodeTabNl("ldr\tr2, [sp], #4")
        outputCodeTabNl("ands\tr3, r2, r3")
    }    

    /** or top of stack with accumulator */
    override fun orAccumulator() {
        outputCodeTabNl("ldr\tr2, [sp], #4")
        outputCodeTabNl("orrs\tr3, r2, r3")
    }

    /** exclusive or top of stack with accumulator */
    override fun xorAccumulator() {
        outputCodeTabNl("ldr\tr2, [sp], #4")
        outputCodeTabNl("eors\tr3, r2, r3")
    }

While bit-wise Not is slightly more complicated in the ARM case as the constant 0xFFFFFFFF that we need to xor with the accumulator must be stored in memory (as mentioned in Chapter 1 – Integer Constants):

    override fun notAccumulator() {
        outputCodeTabNl("ldr\tr2, ${CONST_ALL_1S}${GLOBAL_VARS_ADDR_SUFFIX}")
        outputCodeTabNl("ldr\tr2, [r2]")
        outputCodeTabNl("eors\tr3, r3, r2")
    }

In X86, bit-wise not is much more straightforward:

    override fun notAccumulator() {
        outputCodeTabNl("xorq\t%rax, -1")
    }

Now that I have implemented the bit-wise operations I have taken the opportunity to clean up the boolean And, Or and Not operations. To avoid confusion with the bit-wise operators, I have used the operators _and_, _or_ and _not_ respectively in Tinsel.

If you remember boolean variables or expressions are actually integers where 0 means false and anything else means true. This means that before we perform the operation we have to convert the integer value (0 or not 0) to boolean (0 or 1). Then the boolean operation is simple:

   /** boolean not accumulator */
    override fun booleanNotAccumulator() {
        outputCodeTabNl("mov\tr3, #0")       // zero accumulator but keep flags
        outputCodeTabNl("moveq\tr3, #1")     // set r3 to 1 if zero flag is set
        outputCodeTabNl("ands\tr3, r3, #1")   // zero the rest of r3 and set flags - Z flag set = FALSE
    }

    override fun booleanOrAccumulator() {
        outputCodeTabNl("mov\tr3, #0")       // convert accumulator to 0-1
        outputCodeTabNl("movne\tr3, #1")     // set r3 to 1 if initially not 0
        outputCodeTabNl("ldr\tr2, [sp], #4") // get op2 in r2 and convert to 0-1
        outputCodeTabNl("orrs\tr2, r2, #0")   // set flags - Z flag set = FALSE
        outputCodeTabNl("mov\tr2, #0")
        outputCodeTabNl("movne\tr2, #1")     // set r2 to 1 if initially not 0
        outputCodeTabNl("orrs\tr3, r3, r2")
    }

    override fun booleanAndAccumulator() {
        outputCodeTabNl("mov\tr3, #0")       // convert accumulator to 0-1
        outputCodeTabNl("movne\tr3, #1")     // set r3 to 1 if initially not 0
        outputCodeTabNl("ldr\tr2, [sp], #4") // get op2 in r2 and convert to 0-1
        outputCodeTabNl("orrs\tr2, r2, #0")   // set flags - Z flag set = FALSE
        outputCodeTabNl("mov\tr2, #0")
        outputCodeTabNl("movne\tr2, #1")     // set r2 to 1 if initially not 0
        outputCodeTabNl("ands\tr3, r3, r2")
    }

Pointers

We will need pointers in Tinsel, as many C library functions take pointers as parameters or return a pointer. We will use pointers both as parameters and as return values in the Tinsel GPIO and Time libraries in the next chapter.

We will have to first add the pointer type to the list of Tinsel supported types. Given that the only numeric type supported at the moment is integer, we will only support integer pointers for now (string is already a pointer actually).

enum class DataType { int, string, intptr, void, none }

intptr is also added to our list of tokens:

    languageTokens.add(
        Token("intptr",     Kwd.intPtrType,       TokType.varType)
    )

We then need to define what operations we will allow between pointers and integers. This is done by adding the appropriate lines in the typesCompatibility map. You can see in the below listing what operations are allowed between pointer and integer or pointer and pointer:

val typesCompatibility = mapOf(
    // pointer with int allowed only for assign add, subtract and comparisons
    TypesAndOpsCombi(DataType.intptr, DataType.int, ADD) to true,
    TypesAndOpsCombi(DataType.intptr, DataType.int, SUBTRACT) to true,
    TypesAndOpsCombi(DataType.intptr, DataType.int, ASSIGN) to true,
    TypesAndOpsCombi(DataType.intptr, DataType.string, ASSIGN) to true,
    TypesAndOpsCombi(DataType.int, DataType.intptr, ASSIGN) to true,
    TypesAndOpsCombi(DataType.intptr, DataType.int, COMPARE_EQ) to true,
    TypesAndOpsCombi(DataType.int, DataType.intptr, COMPARE_EQ) to true,
    ...
    // pointer with pointer allowed only for subtract, assign and compare
    TypesAndOpsCombi(DataType.intptr, DataType.intptr, SUBTRACT) to true,
    TypesAndOpsCombi(DataType.intptr, DataType.intptr, ASSIGN) to true,
    TypesAndOpsCombi(DataType.intptr, DataType.intptr, COMPARE_EQ) to true,
    ...
    TypesAndOpsCombi(DataType.intptr, DataType.none, PRINT) to true,
    // all other combinations forbidden unless set here
)

To refer to the value stored in the address where a pointer is pointing to, I will use the [...] symbols

a = [ptr_var] + 5

The above will take the value of ptr_var, will retrieve the value stored in that memory address, will add 5 to it and will store the result to variable a. This means that we will have to introduce a new function that will parse a pointer expression like the above (i.e. the sequence [...]). As you can see below it is quite simple:

fun parsePtrExpression(): DataType {
    inp.match()
    val expType = parseExpression()
    if (expType != DataType.intptr)
        abort("line ${inp.currentLineNumber}: expected pointer expression, found ${expType}")
    code.savePtrValue()
    inp.match(Kwd.ptrClose)
    return if (expType == DataType.intptr) DataType.int else DataType.none
}

It is called when an opening [ is found in parseFactor (when the factor contains a pointer pointing to a variable):

fun parseFactor(): DataType {
    when (inp.lookahead().encToken) {
        ...
        Kwd.ptrOpen -> return parsePointer()
        ...
    }
    return DataType.void    // dummy instruction
}

fun parsePointer(): DataType {
    val expType = parsePtrExpression()
    code.setAccumulatorToPointerVar()
    return expType
}

or in parseStatement (when we assign a value to a variable pointed to by a pointer):

fun parseStatement(breakLabel: String, continueLabel: String, blockName: String) {
    when (inp.lookahead().encToken) {
        ...
        Kwd.ptrOpen -> parsePtrAssignment()
        ...
    }
}

fun parsePtrAssignment() {
    var ptrType = parsePtrExpression()
    inp.match(Kwd.equalsOp)
    val typeExp = parseBooleanExpression()
    checkOperandTypeCompatibility(ptrType, typeExp, ASSIGN)
    code.pointerAssignment()
}

We also need to be able to set a pointer to an address. For this I’m introducing the keyword addr(variable) which will return the address of the variable mentioned between the (), like in the example below.

ptr_var = addr(a)

As with every token, this new keyword has to be added to our tokens list:

    languageTokens.add(
        Token("addr",  Kwd.addressOfVar,   TokType.none)
    )

This new token will be parsed and processed in (where else?) parseFactor:

fun parseFactor(): DataType {
    when (inp.lookahead().encToken) {
        ...
        Kwd.addressOfVar -> return parseAddressOfVar()
        ...
    }
    return DataType.void    // dummy instruction
}

fun parseAddressOfVar(): DataType {
    inp.match()
    inp.match(Kwd.leftParen)
    val nextToken = inp.match(Kwd.identifier)
    val varName = nextToken.value
    if (nextToken.type != TokType.variable)
        abort("line ${inp.currentLineNumber}: expected variable name, found ${varName}")
    if (identifiersMap[varName]?.isStackVar == true)
        identifiersMap[varName]?.stackOffset?.let { code.setAccumulatorToLocalVarAddress(it) }
    else
        code.setAccumulatorToVarAddress(varName)
    inp.match(Kwd.rightParen)
    return DataType.intptr
}

This function is quite simple, first checks the syntax and then checks whether the variable between the (...) is a stack variable or a static variable and calls the respective function in the code module.

Finally, we have a new function in OpsNumeric.kt (parsePtrVariable) which is exactly the same as parseNumericVariable, with the only difference that it returns type intptr instead.

fun parsePtrVariable(): DataType {
    val varName = inp.match(Kwd.identifier).value
    if (identifiersMap[varName]?.isStackVar == true)
        identifiersMap[varName]?.stackOffset?.let { code.setAccumulatorToLocalVar(it) }
    else
        code.setAccumulatorToVar(varName)
    return DataType.intptr
}

You can see above a number of new functions in the code module that are called when a pointer is processed. These result in very similar code as when the equivalent functions are called when an integer variable is processed. There is just an extra step added in the case of pointers, which is to save the value of the pointer in a separate register so that we can store or retrieve the value in/from the address pointed to by the pointer.

Consider the example below where a static variable is set to the value in the accumulator by loading the variable address to r2 and then storing the contents of r3 to the address r2 is pointing to.

a = 5 * b

The expression 5 * b is first calculated and stored in the accumulator. Then the following code is called, which simply gets the address of the variable into r2 and then stores the contents of the accumulator to the address where r2 is pointing (i.e. the variable).

    /** set variable to accumulator */
    override fun assignment(identifier: String) {
        outputCodeTabNl("ldr\tr2, ${identifier}${GLOBAL_VARS_ADDR_SUFFIX}")
        outputCodeTabNl("str\tr3, [r2]")
    }

Let’s see what happens when we want to set the location a pointer points to a value:

[ptr_var] = 5 * b

Here’s the sequence of events:

The [ will trigger parsePtrAssignment which in turn will call parsePtrExpression. This function will create the code to calculate the address the pointer is pointing to and will save that address in r1 by calling code.savePtrValue.

Then the code to calculate the expression on the right hand side of the = will be produced and the value of that expression will be left in the accumulator.

Finally, pointerAssignment will be called, which will save the accumulator value to the address r1 is pointing to (i.e. the address we wanted).

Here are these code module functions for your quick reference:

     /** save address a pointer is pointing to for later use */
    override fun savePtrValue() {
        // the address the pointer points to is saved in r1
        outputCodeTabNl("mov\tr1, r3")
    }

    /** save accumulator to the previously saved address the pointer is pointing to */
    override fun pointerAssignment() {
        // the pointer address was previously saved in r1
        outputCodeTabNl("str\tr3, [r1]")
    }

Needless to say that (same as in C) one has to be very careful when using pointers as uninitialised pointers or pointers pointing to the wrong address (both of which are every easy to happen) will lead to Segmentation Faults and program crashes.

Print Formats

Given that we now support binary and hex constants it might be useful to support binary and hex format when we print an integer. I will introduce the print format as a sequence _:nc_ where n is the length and c is the format to be used same as in printf in C. The format will optionally follow the expression to be printed as below:

print a+1 :05x

The above will result in the value a+1 to be printed using the "%05x" format in printf. In the absence of format, the call to printf will use the default decimal format "%d". Please note, print format is only supported for integers.

The parsing of the format is done in printExpressions when it detects a colon after the expression to be printed:

   fun printExpressions() {
    do {
        var decFmt = code.DEF_INT_FMT
        if (inp.lookahead().encToken == Kwd.commaToken)
            inp.match() // skip the comma
        val exprType = parseBooleanExpression()
        checkOperandTypeCompatibility(exprType, DataType.none, PRINT)
        if (inp.lookahead().encToken == Kwd.colonToken) {
            inp.match()
            decFmt = getPrintFormat()
        }
        when (exprType) {
            DataType.int, DataType.intptr -> code.printInt(decFmt)
            DataType.string -> code.printStr()
            else -> {}
        }
    } while (inp.lookahead().encToken == Kwd.commaToken)
}      

When a print format is found the below function is called:

  fun getPrintFormat(): String {
    var fmt = ""
    var fmtLen = ""
    var fmtType = ""
    if (inp.lookahead().encToken == Kwd.number) {
        fmtLen = inp.lookahead().value
        inp.match()
    }
    if (inp.lookahead().encToken == Kwd.identifier) {
        fmtType = inp.lookahead().value
        inp.match()
    }
    fmt = "%$fmtLen$fmtType"
    // fmt must be added to the map of constant strings
    var fmtStringName = ""
    stringConstants.forEach { (k, v) -> if (v == fmt) fmtStringName = k }
    if (fmtStringName == "") {  // if not found
        // save the string in the map of constant strings
        fmtStringName = "${code.INT_FMT}_${fmt.substring(1)}"
        stringConstants[fmtStringName] = fmt
    }
    return fmtStringName
}

This function first gets the numeric part and the alphabetic part of the format. It then does two things: (a) it creates the C-like format that will be passed to the call to printf (in the variable fmt) and (b) it creates a string name for this format, which is added to the map of constant strings that the compiler maintains. The new format is added to the map of strings only if the same format does not exist in the map already. If you remember, this map of constant strings will be included in the output code at the end. Finally, the resulting format is passed to the code module function printInt which passes it on to printf.

As you can see above, the print format is always parsed (if it is there, that is) but in the case of string, it is simply ignored.

And with that we have completed this round of Tinsel enhancements and are ready to build the libraries that we need in order to talk to the GPIO Unit of the Raspberry Pi and blink the LED.

As usual, all the sources are in my GitHub repository.

Coming up next: Communicate with the Raspberry Pi GPIO – LED Blink