all: add compiler support for interrupts

This commit lets the compiler know about interrupts and allows
optimizations to be performed based on that: interrupts are eliminated
when they appear to be unused in a program. This is done with a new
pseudo-call (runtime/interrupt.New) that is treated specially by the
compiler.

7 files changed, 435 insertions, 0 deletions

diff --git a/transform/errors.go b/transform/errors.go
new file mode 100644
index 000000000..226ead28c
--- /dev/null
+++ b/transform/errors.go
@@ -0,0 +1,48 @@
+package transform
+
+import (
+	"go/scanner"
+	"go/token"
+	"path/filepath"
+
+	"tinygo.org/x/go-llvm"
+)
+
+// errorAt returns an error value at the location of the value.
+// The location information may not be complete as it depends on debug
+// information in the IR.
+func errorAt(val llvm.Value, msg string) scanner.Error {
+	return scanner.Error{
+		Pos: getPosition(val),
+		Msg: msg,
+	}
+}
+
+// getPosition returns the position information for the given value, as far as
+// it is available.
+func getPosition(val llvm.Value) token.Position {
+	if !val.IsAInstruction().IsNil() {
+		loc := val.InstructionDebugLoc()
+		if loc.IsNil() {
+			return token.Position{}
+		}
+		file := loc.LocationScope().ScopeFile()
+		return token.Position{
+			Filename: filepath.Join(file.FileDirectory(), file.FileFilename()),
+			Line:     int(loc.LocationLine()),
+			Column:   int(loc.LocationColumn()),
+		}
+	} else if !val.IsAFunction().IsNil() {
+		loc := val.Subprogram()
+		if loc.IsNil() {
+			return token.Position{}
+		}
+		file := loc.ScopeFile()
+		return token.Position{
+			Filename: filepath.Join(file.FileDirectory(), file.FileFilename()),
+			Line:     int(loc.SubprogramLine()),
+		}
+	} else {
+		return token.Position{}
+	}
+}
diff --git a/transform/interrupt.go b/transform/interrupt.go
new file mode 100644
index 000000000..2a0dbe02e
--- /dev/null
+++ b/transform/interrupt.go
@@ -0,0 +1,218 @@
+package transform
+
+import (
+	"fmt"
+	"strings"
+
+	"tinygo.org/x/go-llvm"
+)
+
+// LowerInterrupts creates interrupt handlers for the interrupts created by
+// runtime/interrupt.New.
+//
+// The operation is as follows. The compiler creates the following during IR
+// generation:
+//     * calls to runtime/interrupt.Register that map interrupt IDs to ISR names.
+//     * runtime/interrupt.handle objects that store the (constant) interrupt ID and
+//       interrupt handler func value.
+//
+// This pass then creates the specially named interrupt handler names that
+// simply call the registered handlers. This might seem like it causes extra
+// overhead, but in fact inlining and const propagation will eliminate most if
+// not all of that.
+func LowerInterrupts(mod llvm.Module) []error {
+	var errs []error
+
+	// Discover interrupts. The runtime/interrupt.Register call is a compiler
+	// intrinsic that maps interrupt numbers to handler names.
+	handlerNames := map[int64]string{}
+	for _, call := range getUses(mod.NamedFunction("runtime/interrupt.Register")) {
+		if call.IsACallInst().IsNil() {
+			errs = append(errs, errorAt(call, "expected a call to runtime/interrupt.Register?"))
+			continue
+		}
+
+		num := call.Operand(0)
+		if num.IsAConstant().IsNil() {
+			errs = append(errs, errorAt(call, "non-constant interrupt number?"))
+			continue
+		}
+
+		// extract the interrupt name
+		nameStrGEP := call.Operand(1)
+		if nameStrGEP.IsAConstantExpr().IsNil() || nameStrGEP.Opcode() != llvm.GetElementPtr {
+			errs = append(errs, errorAt(call, "expected a string operand?"))
+			continue
+		}
+		nameStrPtr := nameStrGEP.Operand(0) // note: assuming it's a GEP to the first byte
+		nameStrLen := call.Operand(2)
+		if nameStrPtr.IsAGlobalValue().IsNil() || !nameStrPtr.IsGlobalConstant() || nameStrLen.IsAConstant().IsNil() {
+			errs = append(errs, errorAt(call, "non-constant interrupt name?"))
+			continue
+		}
+
+		// keep track of this name
+		name := string(getGlobalBytes(nameStrPtr)[:nameStrLen.SExtValue()])
+		handlerNames[num.SExtValue()] = name
+
+		// remove this pseudo-call
+		call.ReplaceAllUsesWith(llvm.ConstNull(call.Type()))
+		call.EraseFromParentAsInstruction()
+	}
+
+	ctx := mod.Context()
+	nullptr := llvm.ConstNull(llvm.PointerType(ctx.Int8Type(), 0))
+	builder := ctx.NewBuilder()
+	defer builder.Dispose()
+
+	// Create a function type with the signature of an interrupt handler.
+	fnType := llvm.FunctionType(ctx.VoidType(), nil, false)
+
+	// Collect a slice of interrupt handle objects. The fact that they still
+	// exist in the IR indicates that they could not be optimized away,
+	// therefore we need to make real interrupt handlers for them.
+	var handlers []llvm.Value
+	handleType := mod.GetTypeByName("runtime/interrupt.handle")
+	if !handleType.IsNil() {
+		handlePtrType := llvm.PointerType(handleType, 0)
+		for global := mod.FirstGlobal(); !global.IsNil(); global = llvm.NextGlobal(global) {
+			if global.Type() != handlePtrType {
+				continue
+			}
+			handlers = append(handlers, global)
+		}
+	}
+
+	// Iterate over all handler objects, replacing their ptrtoint uses with a
+	// real interrupt ID and creating an interrupt handler for them.
+	for _, global := range handlers {
+		initializer := global.Initializer()
+		num := llvm.ConstExtractValue(initializer, []uint32{1, 0})
+		name := handlerNames[num.SExtValue()]
+
+		if name == "" {
+			errs = append(errs, errorAt(global, fmt.Sprintf("cannot find interrupt name for number %d", num.SExtValue())))
+			continue
+		}
+
+		// Extract the func value.
+		handlerContext := llvm.ConstExtractValue(initializer, []uint32{0, 0})
+		handlerFuncPtr := llvm.ConstExtractValue(initializer, []uint32{0, 1})
+		if !handlerContext.IsConstant() || !handlerFuncPtr.IsConstant() {
+			// This should have been checked already in the compiler.
+			errs = append(errs, errorAt(global, "func value must be constant"))
+			continue
+		}
+		if !handlerFuncPtr.IsAConstantExpr().IsNil() && handlerFuncPtr.Opcode() == llvm.PtrToInt {
+			// This is a ptrtoint: the IR was created for func lowering using a
+			// switch statement.
+			global := handlerFuncPtr.Operand(0)
+			if global.IsAGlobalValue().IsNil() {
+				errs = append(errs, errorAt(global, "internal error: expected a global for func lowering"))
+				continue
+			}
+			initializer := global.Initializer()
+			if initializer.Type() != mod.GetTypeByName("runtime.funcValueWithSignature") {
+				errs = append(errs, errorAt(global, "internal error: func lowering global has unexpected type"))
+				continue
+			}
+			ptrtoint := llvm.ConstExtractValue(initializer, []uint32{0})
+			if ptrtoint.IsAConstantExpr().IsNil() || ptrtoint.Opcode() != llvm.PtrToInt {
+				errs = append(errs, errorAt(global, "internal error: func lowering global has unexpected func ptr type"))
+				continue
+			}
+			handlerFuncPtr = ptrtoint.Operand(0)
+		}
+		if handlerFuncPtr.Type().TypeKind() != llvm.PointerTypeKind || handlerFuncPtr.Type().ElementType().TypeKind() != llvm.FunctionTypeKind {
+			errs = append(errs, errorAt(global, "internal error: unexpected LLVM types in func value"))
+			continue
+		}
+
+		// Check for an existing interrupt handler, and report it as an error if
+		// there is one.
+		fn := mod.NamedFunction(name)
+		if fn.IsNil() {
+			fn = llvm.AddFunction(mod, name, fnType)
+		} else if fn.Type().ElementType() != fnType {
+			// Don't bother with a precise error message (listing the previsous
+			// location) because this should not normally happen anyway.
+			errs = append(errs, errorAt(global, name+" redeclared with a different signature"))
+			continue
+		} else if !fn.IsDeclaration() {
+			// Interrupt handler was already defined. Check the first
+			// instruction (which should be a call) whether this handler would
+			// be identical anyway.
+			firstInst := fn.FirstBasicBlock().FirstInstruction()
+			if !firstInst.IsACallInst().IsNil() && firstInst.OperandsCount() == 4 && firstInst.CalledValue() == handlerFuncPtr && firstInst.Operand(0) == num && firstInst.Operand(1) == handlerContext {
+				// Already defined and apparently identical, so assume this is
+				// fine.
+				continue
+			}
+
+			errValue := name + " redeclared in this program"
+			fnPos := getPosition(fn)
+			if fnPos.IsValid() {
+				errValue += "\n\tprevious declaration at " + fnPos.String()
+			}
+			errs = append(errs, errorAt(global, errValue))
+			continue
+		}
+
+		// Create the wrapper function which is the actual interrupt handler
+		// that is inserted in the interrupt vector.
+		fn.SetUnnamedAddr(true)
+		fn.SetSection(".text." + name)
+		entryBlock := ctx.AddBasicBlock(fn, "entry")
+		builder.SetInsertPointAtEnd(entryBlock)
+
+		// Set the 'interrupt' flag if needed on this platform.
+		if strings.HasPrefix(mod.Target(), "avr") {
+			// This special calling convention is needed on AVR to save and
+			// restore all clobbered registers, instead of just the ones that
+			// would need to be saved/restored in a normal function call.
+			// Note that the AVR_INTERRUPT calling convention would enable
+			// interrupts right at the beginning of the handler, potentially
+			// leading to lots of nested interrupts and a stack overflow.
+			fn.SetFunctionCallConv(85) // CallingConv::AVR_SIGNAL
+		}
+
+		// Fill the function declaration with the forwarding call.
+		// In practice, the called function will often be inlined which avoids
+		// the extra indirection.
+		builder.CreateCall(handlerFuncPtr, []llvm.Value{num, handlerContext, nullptr}, "")
+		builder.CreateRetVoid()
+
+		// Replace all ptrtoint uses of the global with the interrupt constant.
+		// That can only now be safely done after the interrupt handler has been
+		// created, doing it before the interrupt handler is created might
+		// result in this interrupt handler being optimized away entirely.
+		for _, user := range getUses(global) {
+			if user.IsAConstantExpr().IsNil() || user.Opcode() != llvm.PtrToInt {
+				errs = append(errs, errorAt(global, "internal error: expected a ptrtoint"))
+				continue
+			}
+			user.ReplaceAllUsesWith(num)
+		}
+
+		// The runtime/interrput.handle struct can finally be removed.
+		// It would probably be eliminated anyway by a globaldce pass but it's
+		// better to do it now to be sure.
+		global.EraseFromParentAsGlobal()
+	}
+
+	// Remove now-useless runtime/interrupt.use calls. These are used for some
+	// platforms like AVR that do not need to enable interrupts to use them, so
+	// need another way to keep them alive.
+	// After interrupts have been lowered, this call is useless and would cause
+	// a linker error so must be removed.
+	for _, call := range getUses(mod.NamedFunction("runtime/interrupt.use")) {
+		if call.IsACallInst().IsNil() {
+			errs = append(errs, errorAt(call, "internal error: expected call to runtime/interrupt.use"))
+			continue
+		}
+
+		call.EraseFromParentAsInstruction()
+	}
+
+	return errs
+}
diff --git a/transform/interrupt_test.go b/transform/interrupt_test.go
new file mode 100644
index 000000000..00a199063
--- /dev/null
+++ b/transform/interrupt_test.go
@@ -0,0 +1,24 @@
+package transform
+
+import (
+	"testing"
+
+	"tinygo.org/x/go-llvm"
+)
+
+func TestInterruptLowering(t *testing.T) {
+	t.Parallel()
+	for _, subtest := range []string{"avr", "cortexm"} {
+		t.Run(subtest, func(t *testing.T) {
+			testTransform(t, "testdata/interrupt-"+subtest, func(mod llvm.Module) {
+				errs := LowerInterrupts(mod)
+				if len(errs) != 0 {
+					t.Fail()
+					for _, err := range errs {
+						t.Error(err)
+					}
+				}
+			})
+		})
+	}
+}
diff --git a/transform/testdata/interrupt-avr.ll b/transform/testdata/interrupt-avr.ll
new file mode 100644
index 000000000..1c195634b
--- /dev/null
+++ b/transform/testdata/interrupt-avr.ll
@@ -0,0 +1,33 @@
+target datalayout = "e-P1-p:16:8-i8:8-i16:8-i32:8-i64:8-f32:8-f64:8-n8-a:8"
+target triple = "avr-atmel-none"
+
+%"runtime/interrupt.handle" = type { %runtime.funcValue, %"runtime/interrupt.Interrupt" } %runtime.funcValue = type { i8*, i16 }
+%runtime.typecodeID = type { %runtime.typecodeID*, i16 }
+%runtime.funcValueWithSignature = type { i16, %runtime.typecodeID* }
+%machine.UART = type { %machine.RingBuffer* }
+%machine.RingBuffer = type { [128 x %"runtime/volatile.Register8"], %"runtime/volatile.Register8", %"runtime/volatile.Register8" }
+%"runtime/volatile.Register8" = type { i8 }
+%"runtime/interrupt.Interrupt" = type { i32 }
+
+@"reflect/types.type:func:{named:runtime/interrupt.Interrupt}{}" = external constant %runtime.typecodeID
+@"(machine.UART).Configure$1$withSignature" = internal constant %runtime.funcValueWithSignature { i16 ptrtoint (void (i32, i8*, i8*) addrspace(1)* @"(machine.UART).Configure$1" to i16), %runtime.typecodeID* @"reflect/types.type:func:{named:runtime/interrupt.Interrupt}{}" }
+@"runtime/interrupt.$interrupt18" = private unnamed_addr constant %"runtime/interrupt.handle" { %runtime.funcValue { i8* undef, i16 ptrtoint (%runtime.funcValueWithSignature* @"(machine.UART).Configure$1$withSignature" to i16) }, %"runtime/interrupt.Interrupt" { i32 18 } }
[email protected] = internal global %machine.UART zeroinitializer
+@"device/avr.init$string.18" = internal unnamed_addr constant [17 x i8] c"__vector_USART_RX"
+
+declare void @"(machine.UART).Configure$1"(i32, i8*, i8*) unnamed_addr addrspace(1)
+
+declare i32 @"runtime/interrupt.Register"(i32, i8*, i16, i8*, i8*) addrspace(1)
+
+declare void @"runtime/interrupt.use"(%"runtime/interrupt.Interrupt") addrspace(1)
+
+define void @"(machine.UART).Configure"(%machine.RingBuffer*, i32, i8, i8, i8* %context, i8* %parentHandle) unnamed_addr addrspace(1) {
+  call addrspace(1) void @"runtime/interrupt.use"(%"runtime/interrupt.Interrupt" { i32 ptrtoint (%"runtime/interrupt.handle"* @"runtime/interrupt.$interrupt18" to i32) })
+  ret void
+}
+
+define void @"device/avr.init"(i8* %context, i8* %parentHandle) unnamed_addr addrspace(1) {
+entry:
+  %0 = call addrspace(1) i32 @"runtime/interrupt.Register"(i32 18, i8* getelementptr inbounds ([17 x i8], [17 x i8]* @"device/avr.init$string.18", i32 0, i32 0), i16 17, i8* undef, i8* undef)
+  ret void
+}
diff --git a/transform/testdata/interrupt-avr.out.ll b/transform/testdata/interrupt-avr.out.ll
new file mode 100644
index 000000000..b71c43998
--- /dev/null
+++ b/transform/testdata/interrupt-avr.out.ll
@@ -0,0 +1,35 @@
+target datalayout = "e-P1-p:16:8-i8:8-i16:8-i32:8-i64:8-f32:8-f64:8-n8-a:8"
+target triple = "avr-atmel-none"
+
+%runtime.typecodeID = type { %runtime.typecodeID*, i16 }
+%runtime.funcValueWithSignature = type { i16, %runtime.typecodeID* }
+%machine.UART = type { %machine.RingBuffer* }
+%machine.RingBuffer = type { [128 x %"runtime/volatile.Register8"], %"runtime/volatile.Register8", %"runtime/volatile.Register8" }
+%"runtime/volatile.Register8" = type { i8 }
+%"runtime/interrupt.Interrupt" = type { i32 }
+
+@"reflect/types.type:func:{named:runtime/interrupt.Interrupt}{}" = external constant %runtime.typecodeID
+@"(machine.UART).Configure$1$withSignature" = internal constant %runtime.funcValueWithSignature { i16 ptrtoint (void (i32, i8*, i8*) addrspace(1)* @"(machine.UART).Configure$1" to i16), %runtime.typecodeID* @"reflect/types.type:func:{named:runtime/interrupt.Interrupt}{}" }
[email protected] = internal global %machine.UART zeroinitializer
+@"device/avr.init$string.18" = internal unnamed_addr constant [17 x i8] c"__vector_USART_RX"
+
+declare void @"(machine.UART).Configure$1"(i32, i8*, i8*) unnamed_addr addrspace(1)
+
+declare i32 @"runtime/interrupt.Register"(i32, i8*, i16, i8*, i8*) addrspace(1)
+
+declare void @"runtime/interrupt.use"(%"runtime/interrupt.Interrupt") addrspace(1)
+
+define void @"(machine.UART).Configure"(%machine.RingBuffer*, i32, i8, i8, i8* %context, i8* %parentHandle) unnamed_addr addrspace(1) {
+  ret void
+}
+
+define void @"device/avr.init"(i8* %context, i8* %parentHandle) unnamed_addr addrspace(1) {
+entry:
+  ret void
+}
+
+define avr_signalcc  void @__vector_USART_RX() unnamed_addr addrspace(1) section ".text.__vector_USART_RX" {
+entry:
+  call addrspace(1) void @"(machine.UART).Configure$1"(i32 18, i8* undef, i8* null)
+  ret void
+}
diff --git a/transform/testdata/interrupt-cortexm.ll b/transform/testdata/interrupt-cortexm.ll
new file mode 100644
index 000000000..2c156b5b6
--- /dev/null
+++ b/transform/testdata/interrupt-cortexm.ll
@@ -0,0 +1,38 @@
+target datalayout = "e-m:e-p:32:32-Fi8-i64:64-v128:64:128-a:0:32-n32-S64"
+target triple = "armv7em-none-eabi"
+
+%machine.UART = type { %machine.RingBuffer* }
+%machine.RingBuffer = type { [128 x %"runtime/volatile.Register8"], %"runtime/volatile.Register8", %"runtime/volatile.Register8" }
+%"runtime/volatile.Register8" = type { i8 }
+%"runtime/interrupt.handle" = type { { i8*, void (i32, i8*, i8*)* }, %"runtime/interrupt.Interrupt" }
+%"runtime/interrupt.Interrupt" = type { i32 }
+
+@"runtime/interrupt.$interrupt2" = private unnamed_addr constant %"runtime/interrupt.handle" { { i8*, void (i32, i8*, i8*)* } { i8* bitcast (%machine.UART* @machine.UART0 to i8*), void (i32, i8*, i8*)* @"(*machine.UART).handleInterrupt$bound" }, %"runtime/interrupt.Interrupt" { i32 2 } }
[email protected] = internal global %machine.UART { %machine.RingBuffer* @"machine$alloc.335" }
+@"machine$alloc.335" = internal global %machine.RingBuffer zeroinitializer
+@"device/nrf.init$string.2" = internal unnamed_addr constant [23 x i8] c"UARTE0_UART0_IRQHandler"
+@"device/nrf.init$string.3" = internal unnamed_addr constant [44 x i8] c"SPIM0_SPIS0_TWIM0_TWIS0_SPI0_TWI0_IRQHandler"
+
+declare i32 @"runtime/interrupt.Register"(i32, i8*, i32, i8*, i8*) local_unnamed_addr
+
+declare void @"device/arm.EnableIRQ"(i32, i8* nocapture readnone, i8* nocapture readnone)
+
+declare void @"device/arm.SetPriority"(i32, i32, i8* nocapture readnone, i8* nocapture readnone)
+
+define void @runtime.initAll(i8* nocapture readnone, i8* nocapture readnone) unnamed_addr {
+entry:
+  %2 = call i32 @"runtime/interrupt.Register"(i32 2, i8* getelementptr inbounds ([23 x i8], [23 x i8]* @"device/nrf.init$string.2", i32 0, i32 0), i32 23, i8* undef, i8* undef)
+  %3 = call i32 @"runtime/interrupt.Register"(i32 3, i8* getelementptr inbounds ([44 x i8], [44 x i8]* @"device/nrf.init$string.3", i32 0, i32 0), i32 44, i8* undef, i8* undef)
+  call void @"device/arm.SetPriority"(i32 ptrtoint (%"runtime/interrupt.handle"* @"runtime/interrupt.$interrupt2" to i32), i32 192, i8* undef, i8* undef)
+  call void @"device/arm.EnableIRQ"(i32 ptrtoint (%"runtime/interrupt.handle"* @"runtime/interrupt.$interrupt2" to i32), i8* undef, i8* undef)
+  ret void
+}
+
+define internal void @"(*machine.UART).handleInterrupt$bound"(i32, i8* nocapture %context, i8* nocapture readnone %parentHandle) {
+entry:
+  %unpack.ptr = bitcast i8* %context to %machine.UART*
+  call void @"(*machine.UART).handleInterrupt"(%machine.UART* %unpack.ptr, i32 %0, i8* undef, i8* undef)
+  ret void
+}
+
+declare void @"(*machine.UART).handleInterrupt"(%machine.UART* nocapture, i32, i8* nocapture readnone, i8* nocapture readnone)
diff --git a/transform/testdata/interrupt-cortexm.out.ll b/transform/testdata/interrupt-cortexm.out.ll
new file mode 100644
index 000000000..41fa9a776
--- /dev/null
+++ b/transform/testdata/interrupt-cortexm.out.ll
@@ -0,0 +1,39 @@
+target datalayout = "e-m:e-p:32:32-Fi8-i64:64-v128:64:128-a:0:32-n32-S64"
+target triple = "armv7em-none-eabi"
+
+%machine.UART = type { %machine.RingBuffer* }
+%machine.RingBuffer = type { [128 x %"runtime/volatile.Register8"], %"runtime/volatile.Register8", %"runtime/volatile.Register8" }
+%"runtime/volatile.Register8" = type { i8 }
+
[email protected] = internal global %machine.UART { %machine.RingBuffer* @"machine$alloc.335" }
+@"machine$alloc.335" = internal global %machine.RingBuffer zeroinitializer
+@"device/nrf.init$string.2" = internal unnamed_addr constant [23 x i8] c"UARTE0_UART0_IRQHandler"
+@"device/nrf.init$string.3" = internal unnamed_addr constant [44 x i8] c"SPIM0_SPIS0_TWIM0_TWIS0_SPI0_TWI0_IRQHandler"
+
+declare i32 @"runtime/interrupt.Register"(i32, i8*, i32, i8*, i8*) local_unnamed_addr
+
+declare void @"device/arm.EnableIRQ"(i32, i8* nocapture readnone, i8* nocapture readnone)
+
+declare void @"device/arm.SetPriority"(i32, i32, i8* nocapture readnone, i8* nocapture readnone)
+
+define void @runtime.initAll(i8* nocapture readnone, i8* nocapture readnone) unnamed_addr {
+entry:
+  call void @"device/arm.SetPriority"(i32 2, i32 192, i8* undef, i8* undef)
+  call void @"device/arm.EnableIRQ"(i32 2, i8* undef, i8* undef)
+  ret void
+}
+
+define internal void @"(*machine.UART).handleInterrupt$bound"(i32, i8* nocapture %context, i8* nocapture readnone %parentHandle) {
+entry:
+  %unpack.ptr = bitcast i8* %context to %machine.UART*
+  call void @"(*machine.UART).handleInterrupt"(%machine.UART* %unpack.ptr, i32 %0, i8* undef, i8* undef)
+  ret void
+}
+
+declare void @"(*machine.UART).handleInterrupt"(%machine.UART* nocapture, i32, i8* nocapture readnone, i8* nocapture readnone)
+
+define void @UARTE0_UART0_IRQHandler() unnamed_addr section ".text.UARTE0_UART0_IRQHandler" {
+entry:
+  call void @"(*machine.UART).handleInterrupt$bound"(i32 2, i8* bitcast (%machine.UART* @machine.UART0 to i8*), i8* null)
+  ret void
+}