ir: Define the data types used to represent LLVM IR

[mewmew]

To identify a relevant subset of LLVM IR capable of representing the actions of the uC test case source files, Clang has been used with the -emit-llvm flag to convert the uC test case source files to LLVM IR (e.g. quiet/semantic/s02.ll).

A grammar for the identified subset of LLVM IR has been expressed in BNF with Gocc syntax at https://github.com/llir/spec/blob/master/gocc/ll.bnf

This issue tracks the work to define the data types required to represent the relevant parts of the identified subset of LLVM IR, which should include:

• [x] Global variables
• [x] Constants
• [x] Functions
• [x] Basic blocks
• [x] Instructions

The high-level representation of a function is as follows: A function consists of one or more basic blocks. A basic block is a sequence of zero or more non-terminating instructions followed by a terminating instruction. The intuition behind basic blocks is that if one of the instructions within the basic block is executed, then all instructions within the basic block are executed. An instruction may be non-terminating (e.g. xor, add) or terminating (e.g. ret, br).

Feel free to discuss how we may wish to represent these concepts. We may explore the benefits and drawbacks of different data type representations (e.g. hash map (from basic block name to basic block) vs. slice (of basic blocks) for keeping track of the basic blocks within a function).

[mewmew]

Preliminary proposal, just to get the ball rolling, and to give us a starting point to evaluate the pros and cons of other data type representations against.

type Global struct {
   Name string
   Val Value
}

type Function struct {
   Name string
   Blocks []*BasicBlock
}

type BasicBlock struct {
   Name string
   Insts []Instruction
   Term Terminator
}

type Instruction interface {
   isInst()
}

type Terminator interface {
   isTerm()
}

type Value interface {
   isVal()
}

Pros:

• Very straight forward representation
• Maps almost one-to-one to the assembler representation in LLVM IR source files

Cons:

• Using a slice rather than a map to keep track of basic blocks may make control flow graph generation less trivial
• Unclear interfaces, basically a hack to provide union types in Go (see Sum Types in Go). Would be better to define interfaces which indeed provide an interface to the least common denominator of a given concept (see the types.Type interface for a good example).

@sangisos, what do you think?

[sangisos]

The use of a slice should be fine if we change the implementation of the IR code generation to be recursive, which I agree we should.

[mewmew]

The use of a slice should be fine if we change the implementation of the IR code generation to be recursive, which I agree we should.

Sounds like a plan. We can always evaluate the implementation against other designs later and redefine it if we happen to discover a better™ representation.

[sangisos]

I have already started making the little code I had naïvely recursive. Do we have any way to translate uc types to ir types?

[mewmew]

Do we have any way to translate uc types to ir types?

They should map pretty straight forward to llvm/ir/types. During the translation, we may use something along the lines of map[uctypes.Type]irtypes.Type?, which we populate by the corresponding types required for translation of a given unit. E.g. something along the lines of.

typeMap := make(map[uctypes.Type]irtypes.Type)
...
switch n := node.(type) {
case *ast.Expr:
   ucType := n.Type()
   irType, ok := typeMap[ucType]
   if !ok {
      irType, err := translateType(ucType)
      if err != nil {
         return errutil.Err(err)
      }
   }
}

func translateType(ucType uctypes.Type) (irtypes.Type, error) {
    switch ucType := ucType.(type) {
    case *uctypes.Basic
        switch ucType.Kind {
        case uctypes.Char:
            return irtypes.NewInt(8)
        case uctypes.Int:
            // TODO: Assmue 32-bit platform?
            return irtypes.NewInt(32)
        default:
            panic(fmt.Sprintf("support for translating basic type kind %v not yet implemented.", ucType.Kind))
        }
    case *uctypes.Array:
        elem, err := translateType(ucType.Elem())
        if err != nil {
            return nil, errutil.Err(err)
        }
        return irtypes.NewArray(elem, ucType.Len())
    default:
        panic(fmt.Sprintf("support for translating type %T not yet implemented.", ucType))
    }
}

[mewmew]

The LLVM IR library is feature complete with regards to the requirements of the uC compiler as of llir/llvm@9af80ed60e023b18309c4c67033119932519adbe. Closing this issue.