gc: drop support for 'precise' globals

Precise globals require a whole program optimization pass that is hard
to support when building packages separately. This patch removes support
for these globals by converting the last use (Linux) to use
linker-defined symbols instead.

For details, see: https://github.com/tinygo-org/tinygo/issues/2870

5 files changed, 1 insertions, 207 deletions

diff --git a/transform/gc.go b/transform/gc.go
index c8326f699..ab0809806 100644
--- a/transform/gc.go
+++ b/transform/gc.go
@@ -1,8 +1,6 @@
 package transform
 
 import (
-	"math/big"
-
 	"tinygo.org/x/go-llvm"
 )
 
@@ -311,138 +309,6 @@ func MakeGCStackSlots(mod llvm.Module) bool {
 	return true
 }
 
-// AddGlobalsBitmap performs a few related functions. It is needed for scanning
-// globals on platforms where the .data/.bss section is not easily accessible by
-// the GC, and thus all globals that contain pointers must be made reachable by
-// the GC in some other way.
-//
-// First, it scans all globals, and bundles all globals that contain a pointer
-// into one large global (updating all uses in the process). Then it creates a
-// bitmap (bit vector) to locate all the pointers in this large global. This
-// bitmap allows the GC to know in advance where exactly all the pointers live
-// in the large globals bundle, to avoid false positives.
-func AddGlobalsBitmap(mod llvm.Module) bool {
-	if mod.NamedGlobal("runtime.trackedGlobalsStart").IsNil() {
-		return false // nothing to do: no GC in use
-	}
-
-	ctx := mod.Context()
-	targetData := llvm.NewTargetData(mod.DataLayout())
-	defer targetData.Dispose()
-	uintptrType := ctx.IntType(targetData.PointerSize() * 8)
-
-	// Collect all globals that contain pointers (and thus must be scanned by
-	// the GC).
-	var trackedGlobals []llvm.Value
-	var trackedGlobalTypes []llvm.Type
-	for global := mod.FirstGlobal(); !global.IsNil(); global = llvm.NextGlobal(global) {
-		if global.IsDeclaration() || global.IsGlobalConstant() {
-			continue
-		}
-		typ := global.Type().ElementType()
-		ptrs := getPointerBitmap(targetData, typ, global.Name())
-		if ptrs.BitLen() == 0 {
-			continue
-		}
-		trackedGlobals = append(trackedGlobals, global)
-		trackedGlobalTypes = append(trackedGlobalTypes, typ)
-	}
-
-	// Make a new global that bundles all existing globals, and remove the
-	// existing globals. All uses of the previous independent globals are
-	// replaced with a GEP into the new globals bundle.
-	globalsBundleType := ctx.StructType(trackedGlobalTypes, false)
-	globalsBundle := llvm.AddGlobal(mod, globalsBundleType, "tinygo.trackedGlobals")
-	globalsBundle.SetLinkage(llvm.InternalLinkage)
-	globalsBundle.SetUnnamedAddr(true)
-	initializer := llvm.Undef(globalsBundleType)
-	for i, global := range trackedGlobals {
-		initializer = llvm.ConstInsertValue(initializer, global.Initializer(), []uint32{uint32(i)})
-		gep := llvm.ConstGEP(globalsBundle, []llvm.Value{
-			llvm.ConstInt(ctx.Int32Type(), 0, false),
-			llvm.ConstInt(ctx.Int32Type(), uint64(i), false),
-		})
-		global.ReplaceAllUsesWith(gep)
-		global.EraseFromParentAsGlobal()
-	}
-	globalsBundle.SetInitializer(initializer)
-
-	// Update trackedGlobalsStart, which points to the globals bundle.
-	trackedGlobalsStart := llvm.ConstPtrToInt(globalsBundle, uintptrType)
-	mod.NamedGlobal("runtime.trackedGlobalsStart").SetInitializer(trackedGlobalsStart)
-	mod.NamedGlobal("runtime.trackedGlobalsStart").SetLinkage(llvm.InternalLinkage)
-
-	// Update trackedGlobalsLength, which contains the length (in words) of the
-	// globals bundle.
-	alignment := targetData.PrefTypeAlignment(llvm.PointerType(ctx.Int8Type(), 0))
-	trackedGlobalsLength := llvm.ConstInt(uintptrType, targetData.TypeAllocSize(globalsBundleType)/uint64(alignment), false)
-	mod.NamedGlobal("runtime.trackedGlobalsLength").SetLinkage(llvm.InternalLinkage)
-	mod.NamedGlobal("runtime.trackedGlobalsLength").SetInitializer(trackedGlobalsLength)
-
-	// Create a bitmap (a new global) that stores for each word in the globals
-	// bundle whether it contains a pointer. This allows globals to be scanned
-	// precisely: no non-pointers will be considered pointers if the bit pattern
-	// looks like one.
-	// This code assumes that pointers are self-aligned. For example, that a
-	// 32-bit (4-byte) pointer is also aligned to 4 bytes.
-	bitmapBytes := getPointerBitmap(targetData, globalsBundleType, "globals bundle").Bytes()
-	bitmapValues := make([]llvm.Value, len(bitmapBytes))
-	for i, b := range bitmapBytes {
-		bitmapValues[len(bitmapBytes)-i-1] = llvm.ConstInt(ctx.Int8Type(), uint64(b), false)
-	}
-	bitmapArray := llvm.ConstArray(ctx.Int8Type(), bitmapValues)
-	bitmapNew := llvm.AddGlobal(mod, bitmapArray.Type(), "runtime.trackedGlobalsBitmap.tmp")
-	bitmapOld := mod.NamedGlobal("runtime.trackedGlobalsBitmap")
-	bitmapOld.ReplaceAllUsesWith(llvm.ConstBitCast(bitmapNew, bitmapOld.Type()))
-	bitmapNew.SetInitializer(bitmapArray)
-	bitmapNew.SetName("runtime.trackedGlobalsBitmap")
-	bitmapNew.SetLinkage(llvm.InternalLinkage)
-
-	return true // the IR was changed
-}
-
-// getPointerBitmap scans the given LLVM type for pointers and sets bits in a
-// bigint at the word offset that contains a pointer. This scan is recursive.
-func getPointerBitmap(targetData llvm.TargetData, typ llvm.Type, name string) *big.Int {
-	alignment := targetData.PrefTypeAlignment(llvm.PointerType(typ.Context().Int8Type(), 0))
-	switch typ.TypeKind() {
-	case llvm.IntegerTypeKind, llvm.FloatTypeKind, llvm.DoubleTypeKind:
-		return big.NewInt(0)
-	case llvm.PointerTypeKind:
-		return big.NewInt(1)
-	case llvm.StructTypeKind:
-		ptrs := big.NewInt(0)
-		for i, subtyp := range typ.StructElementTypes() {
-			subptrs := getPointerBitmap(targetData, subtyp, name)
-			if subptrs.BitLen() == 0 {
-				continue
-			}
-			offset := targetData.ElementOffset(typ, i)
-			if offset%uint64(alignment) != 0 {
-				panic("precise GC: global contains unaligned pointer: " + name)
-			}
-			subptrs.Lsh(subptrs, uint(offset)/uint(alignment))
-			ptrs.Or(ptrs, subptrs)
-		}
-		return ptrs
-	case llvm.ArrayTypeKind:
-		subtyp := typ.ElementType()
-		subptrs := getPointerBitmap(targetData, subtyp, name)
-		ptrs := big.NewInt(0)
-		if subptrs.BitLen() == 0 {
-			return ptrs
-		}
-		elementSize := targetData.TypeAllocSize(subtyp)
-		for i := 0; i < typ.ArrayLength(); i++ {
-			ptrs.Lsh(ptrs, uint(elementSize)/uint(alignment))
-			ptrs.Or(ptrs, subptrs)
-		}
-		return ptrs
-	default:
-		panic("unknown type kind of global: " + name)
-	}
-}
-
 // markParentFunctions traverses all parent function calls (recursively) and
 // adds them to the set of marked functions. It only considers function calls:
 // any other uses of such a function is ignored.
diff --git a/transform/gc_test.go b/transform/gc_test.go
index 70412d6b6..c071c5f4d 100644
--- a/transform/gc_test.go
+++ b/transform/gc_test.go
@@ -7,13 +7,6 @@ import (
 	"tinygo.org/x/go-llvm"
 )
 
-func TestAddGlobalsBitmap(t *testing.T) {
-	t.Parallel()
-	testTransform(t, "testdata/gc-globals", func(mod llvm.Module) {
-		transform.AddGlobalsBitmap(mod)
-	})
-}
-
 func TestMakeGCStackSlots(t *testing.T) {
 	t.Parallel()
 	testTransform(t, "testdata/gc-stackslots", func(mod llvm.Module) {
diff --git a/transform/optimizer.go b/transform/optimizer.go
index e688a5394..80be63191 100644
--- a/transform/optimizer.go
+++ b/transform/optimizer.go
@@ -189,8 +189,7 @@ func Optimize(mod llvm.Module, config *compileopts.Config, optLevel, sizeLevel i
 	builder.Populate(modPasses)
 	modPasses.Run(mod)
 
-	hasGCPass := AddGlobalsBitmap(mod)
-	hasGCPass = MakeGCStackSlots(mod) || hasGCPass
+	hasGCPass := MakeGCStackSlots(mod)
 	if hasGCPass {
 		if err := llvm.VerifyModule(mod, llvm.PrintMessageAction); err != nil {
 			return []error{errors.New("GC pass caused a verification failure")}
diff --git a/transform/testdata/gc-globals.ll b/transform/testdata/gc-globals.ll
deleted file mode 100644
index afcaa32a2..000000000
--- a/transform/testdata/gc-globals.ll
+++ /dev/null
@@ -1,33 +0,0 @@
-target datalayout = "e-m:e-p:32:32-i64:64-n32:64-S128"
-target triple = "wasm32-unknown-unknown-wasm"
-
-%runtime._string = type { i8*, i32 }
-%runtime._interface = type { i32, i8* }
-
-@globalInt = global i32 5
-@globalString = global %runtime._string zeroinitializer
-@globalInterface = global %runtime._interface zeroinitializer
-@constString = constant %runtime._string zeroinitializer
-@constInterface = constant %runtime._interface zeroinitializer
[email protected] = external global i32
[email protected] = external global [0 x i8]
[email protected] = external global i32
-
-define void @main() {
-  %1 = load i32, i32* @globalInt
-  %2 = load %runtime._string, %runtime._string* @globalString
-  %3 = load %runtime._interface, %runtime._interface* @globalInterface
-  %4 = load %runtime._string, %runtime._string* @constString
-  %5 = load %runtime._interface, %runtime._interface* @constInterface
-  ret void
-}
-
-define void @runtime.markGlobals() {
-  ; Very small subset of what runtime.markGlobals would really do.
-  ; Just enough to make sure the transformation is correct.
-  %1 = load i32, i32* @runtime.trackedGlobalsStart
-  %2 = load i32, i32* @runtime.trackedGlobalsLength
-  %3 = getelementptr inbounds [0 x i8], [0 x i8]* @runtime.trackedGlobalsBitmap, i32 0, i32 0
-  %4 = load i8, i8* %3
-  ret void
-}
diff --git a/transform/testdata/gc-globals.out.ll b/transform/testdata/gc-globals.out.ll
deleted file mode 100644
index 78b182fbd..000000000
--- a/transform/testdata/gc-globals.out.ll
+++ /dev/null
@@ -1,31 +0,0 @@
-target datalayout = "e-m:e-p:32:32-i64:64-n32:64-S128"
-target triple = "wasm32-unknown-unknown-wasm"
-
-%runtime._string = type { i8*, i32 }
-%runtime._interface = type { i32, i8* }
-
-@globalInt = global i32 5
-@constString = constant %runtime._string zeroinitializer
-@constInterface = constant %runtime._interface zeroinitializer
[email protected] = internal global i32 4
[email protected] = external global [0 x i8]
[email protected] = internal global i32 ptrtoint ({ %runtime._string, %runtime._interface }* @tinygo.trackedGlobals to i32)
[email protected] = internal unnamed_addr global { %runtime._string, %runtime._interface } zeroinitializer
[email protected] = internal global [1 x i8] c"\09"
-
-define void @main() {
-  %1 = load i32, i32* @globalInt, align 4
-  %2 = load %runtime._string, %runtime._string* getelementptr inbounds ({ %runtime._string, %runtime._interface }, { %runtime._string, %runtime._interface }* @tinygo.trackedGlobals, i32 0, i32 0), align 4
-  %3 = load %runtime._interface, %runtime._interface* getelementptr inbounds ({ %runtime._string, %runtime._interface }, { %runtime._string, %runtime._interface }* @tinygo.trackedGlobals, i32 0, i32 1), align 4
-  %4 = load %runtime._string, %runtime._string* @constString, align 4
-  %5 = load %runtime._interface, %runtime._interface* @constInterface, align 4
-  ret void
-}
-
-define void @runtime.markGlobals() {
-  %1 = load i32, i32* @runtime.trackedGlobalsStart, align 4
-  %2 = load i32, i32* @runtime.trackedGlobalsLength, align 4
-  %3 = getelementptr inbounds [0 x i8], [0 x i8]* bitcast ([1 x i8]* @runtime.trackedGlobalsBitmap.1 to [0 x i8]*), i32 0, i32 0
-  %4 = load i8, i8* %3, align 1
-  ret void
-}