Raspberry Pi Compiler

Chapter 2a: Tinsel Enhancements – Part 1

Introduction

It is now time to do something specific to the Raspberry Pi and this will be to talk to its GPIO unit and, through this, read the state of a button and turn a LED on and off. But to achieve this, we will need to develop some extensions to Tinsel first.

We will introduce libraries, hex and binary constants, shift, modulo and bit-wise operations and finally pointers. These are significant changes, so I will dedicate this and the next chapter to them. Let’s get to work.

Libraries

Going forward, we will be writing code (i.e. functions) that can be used and reused by many different programs. Obviously we don’t want to include this code in every single program again and again – that would be very messy. We would want to put that foundation code in libraries, from which any Tinsel program would be able to use it. This will be done by linking the compiled library code with the compiled program (same as in every other language).

Our Tinsel libraries will not be very different to a Tinsel program. There will be only two main differences:

  • a library will have no main block (this is more or less obvious, as a library is not a stand-alone executable program, it just contains functions that another program can call)
  • the functions declared in a library that are needed to be called by other programs must be declared as global symbols so that the linker can do what it has to do

Given that the _main_ section is mandatory in every Tinsel program, we need to tell our compiler that a library is not a program but a library. And we will do this using the obvious keywords _library_ and _endlibrary_ in the beginning and at the end of the library module:

// a Tinsel library
library gpiolib
...
endlibrary

Please note, going forward there will be more and more Tinsel code extracts in these blogs, as we will be developing more code that does actually something. These will appear in different background, as above, to avoid confusion with the compiler code.

Our top level parser will recognise either _program_ or _library_ at the start of the module:

fun parseProgHeader() {
    when (inp.lookahead().encToken) {
        Kwd.startOfProgram -> isLibrary = false
        Kwd.startOfLibrary -> isLibrary = true
        else -> inp.expected("program or library")
    }
    ...
}

The _library_ keyword will tell the compiler not to expect a _main_ section:

fun parseMainBlock() {
    if (isLibrary) return   // no main block for libraries
    // else process main block
    ...
}

Those library functions that must be available to other modules will be declared using the _@global_ keyword:

// a Tinsel library function
fun gpio_init() @global:int {
    var fd :int
    ...
}

The function declaration parser will check for the global keyword and if the function is declared global, it will execute the _globalSymbol_ function in the code module to declare this symbol (the function name) as global symbol:

fun parseFunDecl() {
    while (inp.lookahead().encToken == Kwd.funDecl) {
        var isPackageGlobal = false
        ...
        when (inp.lookahead().encToken) {     // check for "package-global" or "external" function
            Kwd.global -> { inp.match(); isPackageGlobal = true }
            else -> {}
        }
        inp.match(Kwd.colonToken)
        ...
        declareFun(functionName, isPackageGlobal)
        ...
    }
}

and

fun declareFun(name: String, isPackageGlobal: Boolean) {
    code.outputCodeNl()
    if (isPackageGlobal)
        code.globalSymbol(name)
    code.declareAsmFun(name)
}

and finally in the code module:

    override fun globalSymbol(name: String) {
        outputCodeNl(".global $name")
    }

Needless to say, a library function may also be declared in the normal way, without the global keyword. This will make it visible only within the library module and not to other programs.

And that was it (or almost…) – these @global functions can now be called from another module that is compiled separately but linked with the library. There is one more thing missing though. When we want to call a library function from a program, the declaration and the body for that function will not be in that program module, but somehow we need to let the compiler know the signature of that function so that it knows what parameters it needs and what it returns. We will do this using the _@external_ keyword in the program that wants to use a library function. 

// a Tinsel program calling a library function
program blinkled

fun gpio_init() @external:int

main {
    if (gpio_init() < 0) {
        println "could not initialise GPIO - exiting"
        exit
    }
    // do something ...
}
endprogram

The external keyword will tell the function parser not to look for the body of the function. The function name will still be stored in the symbols table though and the list of its parameters will still be created. So, here’s the final version of the function declaration parser:

fun parseFunDecl() {
    while (inp.lookahead().encToken == Kwd.funDecl) {
        var isExternal = false
        var isPackageGlobal = false
        inp.match()
        val functionName = inp.match(Kwd.identifier).valuec
        ...
        inp.match(Kwd.leftParen)
        parseFunParams(functionName)
        inp.match(Kwd.rightParen)
        when (inp.lookahead().encToken) {     // check for "package-global" or "external" function
            Kwd.global -> { inp.match(); isPackageGlobal = true }
            Kwd.external -> { inp.match(); isExternal = true }
            else -> {}
        }
        inp.match(Kwd.colonToken)
        var funType: DataType = DataType.void
        when (inp.lookahead().encToken) {
            Kwd.intType -> ...
        }
        inp.match()
        if (identifiersMap[functionName] != null)
            abort ("line ${inp.currentLineNumber}: identifier $functionName already declared")
        identifiersMap[functionName] = IdentifierDecl(TokType.function, funType)
        if (!isExternal) {    // external functions do not have body
            declareFun(functionName, isPackageGlobal)
            storeParamsToStack(functionName)
            parseFunctionBlock()
        }
    }
}

As you can see above, the function _parseFunParams_ is always called and creates the parameters list for this function. Also, the _identifiersMap_ is always updated with the function name and return type. However the declaration of the function name in the code and the parsing of the function body will happen only if the function is not external.

And with that, we have completed the changes required to support library modules in Tinsel. As you can guess from the Tinsel code extracts above, our first library will be the gpiolib module that will let Tinsel programs talk to the Raspberry Pi GPIO. And we will build this in the next chapter.

Hex and Binary Constants

Given that we will be talking to the GPIO chip, where each pin is accessed by reading or setting specific bits in a register, it would be really useful if TINSEL could handle binary and hex numbers. So, let’s do this.

The changes required for this are very localised in the InputProgramScanner module and in particular in the function _getNumber_. This function will have to check whether it has a binary, hex or decimal number and read that number from the input in the appropriate manner.

For this, we will first create two new functions that will recognise a binary number (starting with a 0b) and a hex number (starting with a 0x) respectively.

    /** check for a binary number - starting with 0b */   
    fun isBinaryNumber(): Boolean {
        if (nextChar != '0')
            return false
        getNextChar()
        if (nextChar != 'b') {
            pushChar()
            return false
        }
        getNextChar()
        return true
    }

    /** check for a hex number - starting with 0x */
    fun isHexNumber(): Boolean {
        if (nextChar != '0')
            return false
        getNextChar()
        if (nextChar != 'x') {
            pushChar()
            return false
        }
        getNextChar()
        return true
    }

Here you can see I have introduced the _pushChar_ function that “pushes” a character back to the input stream if it is not the one we expected (the 'b' in case of binary or the 'x' in case of hex). 

    private fun pushChar() {
        if (cursor > 0)
            nextChar = inputProgram[--cursor]
    }

You can also see that both functions isBinaryNumber and isHexNumber call _getNextChar()_ at the end as they have to get rid of the 'b' or the 'x' which is not needed anymore.

So, with these changes, _getNumber_ now looks like this:

    private fun getNumber(): String {
        if (isBinaryNumber())
            return getBinaryNumber()
        if (isHexNumber())
            return getHexNumber()
        return getDecimalNumber()
    }

and the two new functions _getBinaryNumber_ and _getHexNumber_ look like this:

    /** get a binary number */
    private fun getBinaryNumber(): String {
        var value = "0b"
        while (isBinaryDigit(nextChar)) {
            value += nextChar.toString()
            getNextChar()
        }
        return value
    }

    /** get a hex number */
    private fun getHexNumber(): String {
        var value = "0x"
        while (isHexDigit(nextChar)) {
            value += nextChar.toString()
            getNextChar()
        }
        return value
    }

while _getDecimalNumber_ is the old getNumber function.

And, as you can see above, we need two more new functions to recognise the binary and hex digits respectively:

    /** check for a binary numeric digit */
    private fun isBinaryDigit(c: Char): Boolean = c in '0'..'1'

    /** check for a hex numeric digit */
    private fun isHexDigit(c: Char): Boolean = c in '0'..'9' || c in 'a'..'f' || c in 'A'..'F'

Actually, there is one more change required to properly support binary and hex constants. This is in the ARM code module in two places, (a) where we set the accumulator to a constant value (this happens every time a number appears in an expression) and (b) where we initialise a stack variable. These changes are required in order to check the value of the given number and put it either directly in the MOV instruction or in memory (see Chapter 1 – Integer Constants).

    /** set accumulator to a value */
    override fun setAccumulator(value: String) {
        val intValue: Int
        if (value.startsWith("0x"))
            intValue = value.substring(2).toInt(16)
        else if (value.startsWith("0b"))
            intValue = value.substring(2).toInt(2)
        else
            intValue = value.toInt()
        if (intValue in 0..255)
            ...
    }

and

    /** initialise an int stack var */
    override fun initStackVarInt(stackOffset : Int, initValue: String) {
        val value: Int
        if (initValue.startsWith("0x"))
            value = initValue.substring(2).toInt(16)
        else if (initValue.startsWith("0b"))
            value = initValue.substring(2).toInt(2)
        else
            value = initValue.toInt()
        if (value in 0..255)
            ...
    }

The X86 code module does not require such changes as the integer constants go directly into the MOV instruction regardless of value.

Shift Operations

Shift is a very useful operation when you have to deal with bits, and even though shift left is equivalent to multiplying by powers of 2, and shift right is equivalent to dividing by powers of 2, in many cases the shift instruction is much clearer than the equivalent multiply or divide instruction even if they both result in the same outcome. Consider the following example where we want to create a mask that will set bit 5 of a variable by doing a bit-wise or of the variable with the mask. The shift instruction that creates this mask pattern in the below pseudo-code is much easier to understand

mask = 0b01 shl 5
var = var or mask

than the multiply one

mask = 1 * 32
var = var or mask

…not to mention that shift is much faster than multiply and, actually, many compilers translate multiply to a series of shift and add instructions.

I will implement shift left and shift right using the operators _<<_ and _>>_ respectively. The shift instruction that will be generated will be logical shift, so in case of shift right, it will ignore the sign flag and will fill the left-most bit(s) with 0.

Shift will be at the same level of priority in the hierarchy of operators as multiply or divide, so it will be another mullop. Actually, very few changes are needed to implement the shift operations.

First, we need to add the two Tinsel shift operators to our list of tokens:

    ...
    languageTokens.add(
        Token("<<",      Kwd.shlOp,      TokType.mulOps)
    )
    languageTokens.add(
        Token(">>",      Kwd.shrOp,      TokType.mulOps)
    )
    ...

Then, in parseTerm:

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

fun shiftLeft(typeF1: DataType) {
    inp.match()
    val typeF2 = parseFactor()
    checkOperandTypeCompatibility(typeF1, typeF2, SHIFT_LEFT)
    when (typeF1) {
        DataType.int -> shiftLeftNumber()
        else -> {}
    }
}

fun shiftRight(typeF1: DataType) {
    ...

and in OpsNumeric.kt:

fun shiftLeftNumber() {
    code.shiftAccumulatorLeft()
}

and, finally, in the code block:

override fun shiftAccumulatorLeft() {
    outputCodeTabNl("ldr\tr2, [sp], #4")
    outputCodeTabNl("lsl\tr3, r2, r3")
    outputCodeTabNl("tst\tr3, r3")
}

That was not so hard.

Modulo Operation

Another useful one that until now was missing in Tinsel. As we all know, the modulo operation gives us the remainder of the division between two integers. I will use the % operator and, obviously, the priority of modulo will be the same as multiply and divide. So we need to add the code for modulo exactly in the places where we added the code for shift:

    languageTokens.add(
        Token("%",      Kwd.modOp,      TokType.mulOps)
    )
fun parseTerm(): DataType {
    val typeF1 = parseSignedFactor()
    while (inp.lookahead().type == TokType.mulOps) {
        ...
        when (inp.lookahead().encToken) {
            ...
            Kwd.modOp -> modulo(typeF1)
            ...
        }
    }
    return typeF1
}
fun modulo(typeF1: DataType) {
    inp.match()
    val typeF2 = parseFactor()
    checkOperandTypeCompatibility(typeF1, typeF2, MODULO)
    when (typeF1) {
        DataType.int -> moduloNumber()
        else -> {}
    }
}
fun moduloNumber() {
    code.moduloAccumulator()
}

A little complication arises when it comes to writing the assembly code for modulo. In X86 assembly there is no issue as the division operation 

    idivq %rbx, %rax

divides the value in %rdx:%rax by the value in %rbx and leaves the quotient in %rax and the remainder (modulo) in %rdx.

In ARM there is no such functionality though, so we will calculate the modulo by using the formula:

    a mod b = a - ( a / b) * b

or in ARM assembly

    override fun moduloAccumulator() {
        outputCodeTabNl("ldr\tr2, [sp], #4")
        outputCodeTabNl("sdiv\tr0, r2, r3")
        outputCodeTabNl("mul\tr0, r0, r3")
        outputCodeTabNl("sub\tr3, r2, r0")
        outputCodeTabNl("tst\tr3, r3")    // also set flags - Z flag set = FALSE
    }

I will stop this chapter here, as I have done quite a few changes so far, not complicated ones, but many small changes in many places. In the second part of this chapter I will complete the Tinsel extensions needed to access the GPIO unit of the Raspberry Pi by implementing Bit-wise And/Or/Xor and Not operations and also by introducing Pointers.

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

Coming up next: Tinsel Enhancements – Part2

Leave a Reply

Fill in your details below or click an icon to log in:

Gravatar
WordPress.com Logo

You are commenting using your WordPress.com account. ( Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. ( Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. ( Log Out /  Change )

Cancel

Connecting to %s

%d bloggers like this: