all: move OptimizeMaps to transforms and add tests

4 files changed, 158 insertions, 0 deletions

diff --git a/transform/maps.go b/transform/maps.go
new file mode 100644
index 000000000..359d9cc57
--- /dev/null
+++ b/transform/maps.go
@@ -0,0 +1,47 @@
+package transform
+
+import (
+	"tinygo.org/x/go-llvm"
+)
+
+// OptimizeMaps eliminates created but unused maps.
+//
+// In the future, this should statically allocate created but never modified
+// maps. This has not yet been implemented, however.
+func OptimizeMaps(mod llvm.Module) {
+	hashmapMake := mod.NamedFunction("runtime.hashmapMake")
+	if hashmapMake.IsNil() {
+		// nothing to optimize
+		return
+	}
+
+	hashmapBinarySet := mod.NamedFunction("runtime.hashmapBinarySet")
+	hashmapStringSet := mod.NamedFunction("runtime.hashmapStringSet")
+
+	for _, makeInst := range getUses(hashmapMake) {
+		updateInsts := []llvm.Value{}
+		unknownUses := false // are there any uses other than setting a value?
+
+		for _, use := range getUses(makeInst) {
+			if use := use.IsACallInst(); !use.IsNil() {
+				switch use.CalledValue() {
+				case hashmapBinarySet, hashmapStringSet:
+					updateInsts = append(updateInsts, use)
+				default:
+					unknownUses = true
+				}
+			} else {
+				unknownUses = true
+			}
+		}
+
+		if !unknownUses {
+			// This map can be entirely removed, as it is only created but never
+			// used.
+			for _, inst := range updateInsts {
+				inst.EraseFromParentAsInstruction()
+			}
+			makeInst.EraseFromParentAsInstruction()
+		}
+	}
+}
diff --git a/transform/maps_test.go b/transform/maps_test.go
new file mode 100644
index 000000000..2bfc7feff
--- /dev/null
+++ b/transform/maps_test.go
@@ -0,0 +1,22 @@
+package transform
+
+import (
+	"testing"
+
+	"tinygo.org/x/go-llvm"
+)
+
+func TestOptimizeMaps(t *testing.T) {
+	t.Parallel()
+	testTransform(t, "testdata/maps", func(mod llvm.Module) {
+		// Run optimization pass.
+		OptimizeMaps(mod)
+
+		// Run an optimization pass, to clean up the result.
+		// This shows that all code related to the map is really eliminated.
+		pm := llvm.NewPassManager()
+		defer pm.Dispose()
+		pm.AddDeadStoreEliminationPass()
+		pm.Run(mod)
+	})
+}
diff --git a/transform/testdata/maps.ll b/transform/testdata/maps.ll
new file mode 100644
index 000000000..0bf004246
--- /dev/null
+++ b/transform/testdata/maps.ll
@@ -0,0 +1,55 @@
+target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
+target triple = "armv7m-none-eabi"
+
+%runtime.hashmap = type { %runtime.hashmap*, i8*, i32, i8, i8, i8 }
+
+@answer = constant [6 x i8] c"answer"
+
+; func(keySize, valueSize uint8, sizeHint uintptr) *runtime.hashmap
+declare nonnull %runtime.hashmap* @runtime.hashmapMake(i8, i8, i32)
+
+; func(map[string]int, string, unsafe.Pointer)
+declare void @runtime.hashmapStringSet(%runtime.hashmap* nocapture, i8*, i32, i8* nocapture readonly)
+
+; func(map[string]int, string, unsafe.Pointer)
+declare i1 @runtime.hashmapStringGet(%runtime.hashmap* nocapture, i8*, i32, i8* nocapture)
+
+define void @testUnused() {
+    ; create the map
+    %map = call %runtime.hashmap* @runtime.hashmapMake(i8 4, i8 4, i32 0)
+    ; create the value to be stored
+    %hashmap.value = alloca i32
+    store i32 42, i32* %hashmap.value
+    ; store the value
+    %hashmap.value.bitcast = bitcast i32* %hashmap.value to i8*
+    call void @runtime.hashmapStringSet(%runtime.hashmap* %map, i8* getelementptr inbounds ([6 x i8], [6 x i8]* @answer, i32 0, i32 0), i32 6, i8* %hashmap.value.bitcast)
+    ret void
+}
+
+; Note that the following function should ideally be optimized (it could simply
+; return 42), but isn't at the moment.
+define i32 @testReadonly() {
+    ; create the map
+    %map = call %runtime.hashmap* @runtime.hashmapMake(i8 4, i8 4, i32 0)
+
+    ; create the value to be stored
+    %hashmap.value = alloca i32
+    store i32 42, i32* %hashmap.value
+
+    ; store the value
+    %hashmap.value.bitcast = bitcast i32* %hashmap.value to i8*
+    call void @runtime.hashmapStringSet(%runtime.hashmap* %map, i8* getelementptr inbounds ([6 x i8], [6 x i8]* @answer, i32 0, i32 0), i32 6, i8* %hashmap.value.bitcast)
+
+    ; load the value back
+    %hashmap.value2 = alloca i32
+    %hashmap.value2.bitcast = bitcast i32* %hashmap.value2 to i8*
+    %commaOk = call i1 @runtime.hashmapStringGet(%runtime.hashmap* %map, i8* getelementptr inbounds ([6 x i8], [6 x i8]* @answer, i32 0, i32 0), i32 6, i8* %hashmap.value2.bitcast)
+    %loadedValue = load i32, i32* %hashmap.value2
+
+    ret i32 %loadedValue
+}
+
+define %runtime.hashmap* @testUsed() {
+    %1 = call %runtime.hashmap* @runtime.hashmapMake(i8 4, i8 4, i32 0)
+    ret %runtime.hashmap* %1
+}
diff --git a/transform/testdata/maps.out.ll b/transform/testdata/maps.out.ll
new file mode 100644
index 000000000..925a61b00
--- /dev/null
+++ b/transform/testdata/maps.out.ll
@@ -0,0 +1,34 @@
+target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
+target triple = "armv7m-none-eabi"
+
+%runtime.hashmap = type { %runtime.hashmap*, i8*, i32, i8, i8, i8 }
+
+@answer = constant [6 x i8] c"answer"
+
+declare nonnull %runtime.hashmap* @runtime.hashmapMake(i8, i8, i32)
+
+declare void @runtime.hashmapStringSet(%runtime.hashmap* nocapture, i8*, i32, i8* nocapture readonly)
+
+declare i1 @runtime.hashmapStringGet(%runtime.hashmap* nocapture, i8*, i32, i8* nocapture)
+
+define void @testUnused() {
+  ret void
+}
+
+define i32 @testReadonly() {
+  %map = call %runtime.hashmap* @runtime.hashmapMake(i8 4, i8 4, i32 0)
+  %hashmap.value = alloca i32
+  store i32 42, i32* %hashmap.value
+  %hashmap.value.bitcast = bitcast i32* %hashmap.value to i8*
+  call void @runtime.hashmapStringSet(%runtime.hashmap* %map, i8* getelementptr inbounds ([6 x i8], [6 x i8]* @answer, i32 0, i32 0), i32 6, i8* %hashmap.value.bitcast)
+  %hashmap.value2 = alloca i32
+  %hashmap.value2.bitcast = bitcast i32* %hashmap.value2 to i8*
+  %commaOk = call i1 @runtime.hashmapStringGet(%runtime.hashmap* %map, i8* getelementptr inbounds ([6 x i8], [6 x i8]* @answer, i32 0, i32 0), i32 6, i8* %hashmap.value2.bitcast)
+  %loadedValue = load i32, i32* %hashmap.value2
+  ret i32 %loadedValue
+}
+
+define %runtime.hashmap* @testUsed() {
+  %1 = call %runtime.hashmap* @runtime.hashmapMake(i8 4, i8 4, i32 0)
+  ret %runtime.hashmap* %1
+}