I’ve added a number of elements to the language and compiler:
-
comparison operators (<, <=, EQ, NE) yielding BOOL values. These work for any combinations of floating and integer types (including BOOL.)
-
integer bitwise operators (OR, AND, XOR). These only for for integer types (including BOOL.)
-
a NOT operator, yielding BOOL.
-
Array + string declaration and lowering support, including debug instrumentation, and print support for string variables.
This version also fixes a few specific issues:
- Fixed -g/-OX propagation to lowering. If -g not specified, now don’t generate the DI.
- Show the optimized .ll with –emit-llvm instead of the just-lowered .ll (unless not invoking the assembly printer, where the ll optimization passes are registered.)
- Reorganize the grammar so that all the simple lexer tokens are last. Rename a bunch of the tokens, introducing some consistency.
- calculator.td: introduce IntOrFloat constraint type, replacing AnyType usage; array decl support, and string support.
- driver: writeLL helper function, pass -g to lowering if set.
- parser: handle large integer constants properly, array decl support, and string support.
- simplest.cpp: This MWE is updated to include a global variable and global variable access.
- parser: implicit exit: use the last saved location, instead of the module start. This means the line numbers don’t jump around at the very end of the program anymore (i.e.: implicit return/exit)
I started with the comparison operators, thinking that I’d add if statement support, and loops, but got sidetracked. In particular, I generated a number of really large test programs, and without some way to print a string message, it was hard to figure out where an error was occuring. This led to implementing PRINT string-variable support as an interesting feature first.
As a side effect of adding STRING support, I’ve also got declaration support for arbitrary fixed size arrays for any type. I haven’t implemented array access yet, but that probably won’t be too hard.
Here’s an example of a program that uses STRING variables:
STRING t[2]; STRING u[3]; STRING s[2]; INT8 s2; s = "hi"; PRINT s; t = "hi"; PRINT t; u = "hi"; PRINT u; u = "bye"; PRINT u;
This is the MLIR for the program:
module { toy.program { "toy.declare"() <{name = "t", size = 2 : i64, type = i8}> : () -> () "toy.declare"() <{name = "u", size = 3 : i64, type = i8}> : () -> () "toy.declare"() <{name = "s", size = 2 : i64, type = i8}> : () -> () "toy.declare"() <{name = "s2", type = i8}> : () -> () toy.string_assign "s" = "hi" %0 = toy.load "s" : !llvm.ptr toy.print %0 : !llvm.ptr toy.string_assign "t" = "hi" %1 = toy.load "t" : !llvm.ptr toy.print %1 : !llvm.ptr toy.string_assign "u" = "hi" %2 = toy.load "u" : !llvm.ptr toy.print %2 : !llvm.ptr toy.string_assign "u" = "bye" %3 = toy.load "u" : !llvm.ptr toy.print %3 : !llvm.ptr toy.exit } }
It’s a bit clunky, because I cheated and didn’t try to implement PRINT support of string literals directly. I thought that since I had variable support already (which emits llvm.alloca), I could change that alloca trivially to an array from a scalar value.
I think that this did turn out to be a relatively easy way to do it, but this little item did take much more effort than I expected.
The DeclareOp builder is fairly straightforward:
builder.create<toy::DeclareOp>( loc, builder.getStringAttr( varName ), mlir::TypeAttr::get( ty ), nullptr ); // for scalars ... auto sizeAttr = builder.getI64IntegerAttr( arraySize ); builder.create<toy::DeclareOp>( loc, builder.getStringAttr( varName ), mlir::TypeAttr::get( ty ), sizeAttr ); // for arrays
This matches the Optional size now added to DeclareOp for arrays:
def Toy_DeclareOp : Op<Toy_Dialect, "declare"> { let summary = "Declare a variable or array, specifying its name, type (integer or float), and optional size."; let arguments = (ins StrAttr:$name, TypeAttr:$type, OptionalAttr:$size); let results = (outs);
There’s a new AssignStringOp complementing AssignOp:
def Toy_AssignOp : Op<Toy_Dialect, "assign"> { let summary = "Assign a (non-string) value to a variable associated with a declaration"; let arguments = (ins StrAttr:$name, AnyType:$value); let results = (outs); // toy.assign "x", %0 : i32 let assemblyFormat = "$name `,` $value `:` type($value) attr-dict"; } def Toy_AssignStringOp : Op<Toy_Dialect, "string_assign"> { let summary = "Assign a string literal to an i8 array variable"; let arguments = (ins StrAttr:$name, Builtin_StringAttr:$value); let results = (outs); let assemblyFormat = "$name `=` $value attr-dict"; }
I also feel this is a cludge. I probably really want a string literal type like flang’s. Here’s a fortran hello world:
and selected parts of the flang fir dialect MLIR for it:
%4 = fir.declare %3 typeparams %c13 {fortran_attrs = #fir.var_attrs, uniq_name = "_QQclX48656C6C6F2C20776F726C6421"} : (!fir.ref<!fir.char<1,13>>, index) -> !fir.ref<!fir.char<1,13>> %5 = fir.convert %4 : (!fir.ref<!fir.char<1,13>>) -> !fir.ref %6 = fir.convert %c13 : (index) -> i64 %7 = fir.call @_FortranAioOutputAscii(%2, %5, %6) fastmath : (!fir.ref, !fir.ref, i64) -> i1 ... fir.global linkonce @_QQclX48656C6C6F2C20776F726C6421 constant : !fir.char<1,13> { %0 = fir.string_lit "Hello, world!"(13) : !fir.char<1,13> fir.has_value %0 : !fir.char<1,13> }
I had to specialize the LoadOp builder too so that it didn’t create a scalar load. That code looks like:
mlir::Type varType; mlir::Type elemType = declareOp.getTypeAttr().getValue(); if ( declareOp.getSizeAttr() ) // Check if size attribute exists { // Array: load a generic pointer varType = mlir::LLVM::LLVMPointerType::get( builder.getContext(), /*addressSpace=*/0 ); } else { // Scalar: load the value varType = elemType; } auto value = builder.create<toy::LoadOp>( loc, varType, builder.getStringAttr( varName ) );
Lowering didn’t require too much. I needed a print function object:
auto ptrType = LLVM::LLVMPointerType::get( ctx ); auto printFuncStringType = LLVM::LLVMFunctionType::get( LLVM::LLVMVoidType::get( ctx ), { pr_builder.getI64Type(), ptrType }, false ); pr_printFuncString = pr_builder.create<LLVM::LLVMFuncOp>( pr_module.getLoc(), "__toy_print_string", printFuncStringType, LLVM::Linkage::External );
With LoadOp now possibly having pointer valued return
if ( loadOp.getResult().getType().isa<mlir::LLVM::LLVMPointerType>() ) { // Return the allocated pointer LLVM_DEBUG( llvm::dbgs() << "Loading array address: " << allocaOp.getResult() << '\n' ); rewriter.replaceOp( op, allocaOp.getResult() ); } else { // Scalar load auto load = rewriter.create<LLVM::LoadOp>( loc, elemType, allocaOp ); LLVM_DEBUG( llvm::dbgs() << "new load op: " << load << '\n' ); rewriter.replaceOp( op, load.getResult() ); }
assign-string lowering basically just generates a memcpy from a global:
Type elemType = allocaOp.getElemType(); int64_t numElems = 0; if ( auto constOp = allocaOp.getArraySize().getDefiningOp<LLVM::ConstantOp>() ) { auto intAttr = mlir::dyn_cast<IntegerAttr>( constOp.getValue() ); numElems = intAttr.getInt(); } LLVM_DEBUG( llvm::dbgs() << "numElems: " << numElems << '\n' ); LLVM_DEBUG( llvm::dbgs() << "elemType: " << elemType << '\n' ); if ( !mlir::isa<mlir::IntegerType>( elemType ) || elemType.getIntOrFloatBitWidth() != 8 ) { return rewriter.notifyMatchFailure( assignOp, "string assignment requires i8 array" ); } if ( numElems == 0 ) { return rewriter.notifyMatchFailure( assignOp, "invalid array size" ); } size_t strLen = value.size(); size_t copySize = std::min( strLen + 1, static_cast<size_t>( numElems ) ); if ( strLen > static_cast<size_t>( numElems ) ) { return rewriter.notifyMatchFailure( assignOp, "string too large for array" ); } mlir::LLVM::GlobalOp globalOp = lState.lookupOrInsertGlobalOp( rewriter, value, loc, copySize, strLen ); auto globalPtr = rewriter.create<LLVM::AddressOfOp>( loc, globalOp ); auto destPtr = allocaOp.getResult(); auto sizeConst = rewriter.create<LLVM::ConstantOp>( loc, rewriter.getI64Type(), rewriter.getI64IntegerAttr( copySize ) ); rewriter.create<LLVM::MemcpyOp>( loc, destPtr, globalPtr, sizeConst, rewriter.getBoolAttr( false ) ); rewriter.eraseOp( op );
I used global’s like what we’d find in clang LLVM-IR. For example, here’s a C hello world:
#include <string.h> int main() { const char* s = "hi there"; char buf[100]; memcpy( buf, s, strlen( s ) + 1 ); return strlen( buf ); }
where our LLVM-IR looks like:
@.str = private unnamed_addr constant [9 x i8] c"hi there\00", align 1 ; Function Attrs: noinline nounwind optnone uwtable define dso_local i32 @main() #0 { %1 = alloca i32, align 4 %2 = alloca ptr, align 8 %3 = alloca [100 x i8], align 16 store i32 0, ptr %1, align 4 store ptr @.str, ptr %2, align 8 %4 = getelementptr inbounds [100 x i8], ptr %3, i64 0, i64 0 %5 = load ptr, ptr %2, align 8 %6 = load ptr, ptr %2, align 8 %7 = call i64 @strlen(ptr noundef %6) #3 %8 = add i64 %7, 1 call void @llvm.memcpy.p0.p0.i64(ptr align 16 %4, ptr align 1 %5, i64 %8, i1 false) %9 = getelementptr inbounds [100 x i8], ptr %3, i64 0, i64 0 %10 = call i64 @strlen(ptr noundef %9) #3 %11 = trunc i64 %10 to i32 ret i32 %11 }
My lowered LLVM-IR for the program is similar:
@str_1 = private constant [3 x i8] c"bye" @str_0 = private constant [2 x i8] c"hi" declare void @__toy_print_f64(double) declare void @__toy_print_i64(i64) declare void @__toy_print_string(i64, ptr) define i32 @main() { %1 = alloca i8, i64 2, align 1 %2 = alloca i8, i64 3, align 1 %3 = alloca i8, i64 2, align 1 %4 = alloca i8, i64 1, align 1 call void @llvm.memcpy.p0.p0.i64(ptr align 1 %3, ptr align 1 @str_0, i64 2, i1 false) call void @__toy_print_string(i64 2, ptr %3) call void @llvm.memcpy.p0.p0.i64(ptr align 1 %1, ptr align 1 @str_0, i64 2, i1 false) call void @__toy_print_string(i64 2, ptr %1) call void @llvm.memcpy.p0.p0.i64(ptr align 1 %2, ptr align 1 @str_0, i64 3, i1 false) call void @__toy_print_string(i64 3, ptr %2) call void @llvm.memcpy.p0.p0.i64(ptr align 1 %2, ptr align 1 @str_1, i64 3, i1 false) call void @__toy_print_string(i64 3, ptr %2) ret i32 0 } ...
I managed my string literals with a simple hash, avoiding replication if repeated:
mlir::LLVM::GlobalOp lookupOrInsertGlobalOp( ConversionPatternRewriter& rewriter, mlir::StringAttr& stringLit, mlir::Location loc, size_t copySize, size_t strLen ) { mlir::LLVM::GlobalOp globalOp; auto it = pr_stringLiterals.find( stringLit.str() ); if ( it != pr_stringLiterals.end() ) { globalOp = it->second; LLVM_DEBUG( llvm::dbgs() << "Reusing global: " << globalOp.getSymName() << '\n' ); } else { auto savedIP = rewriter.saveInsertionPoint(); rewriter.setInsertionPointToStart( pr_module.getBody() ); auto i8Type = rewriter.getI8Type(); auto arrayType = mlir::LLVM::LLVMArrayType::get( i8Type, copySize ); SmallVector<char> stringData( stringLit.begin(), stringLit.end() ); if ( copySize > strLen ) { stringData.push_back( '\0' ); } auto denseAttr = DenseElementsAttr::get( RankedTensorType::get( { static_cast<int64_t>( copySize ) }, i8Type ), ArrayRef<char>( stringData ) ); std::string globalName = "str_" + std::to_string( pr_stringLiterals.size() ); globalOp = rewriter.create<LLVM::GlobalOp>( loc, arrayType, true, LLVM::Linkage::Private, globalName, denseAttr ); globalOp->setAttr( "unnamed_addr", rewriter.getUnitAttr() ); pr_stringLiterals[stringLit.str()] = globalOp; LLVM_DEBUG( llvm::dbgs() << "Created global: " << globalName << '\n' ); rewriter.restoreInsertionPoint( savedIP ); } return globalOp; }
Without the insertion point swaperoo, this GlobalOp creation doesn’t work, as we need to be in the ModuleOp level where the symbol table lives.
… anyways, it looks like I’m droning on. There’s been lots of stuff to get this far, but there are still many many things to do before what I’ve got even qualifies as a basic programming language (if statements, loops, functions, array assignments, types, …)