compiler: support recursive types

Previously, the cycle was broken by inserting an unsafe.Pointer type in
some places. This is of course incorrect, and makes debugging harder.
However, LLVM provides a way to make temporary nodes that are later
replaced, exactly for this purpose.

This commit uses those temporary metadata nodes to allow such recursive
types.

3 files changed, 37 insertions, 5 deletions

diff --git a/compiler/compiler.go b/compiler/compiler.go
index cba701355..10d39ddbc 100644
--- a/compiler/compiler.go
+++ b/compiler/compiler.go
@@ -1,6 +1,7 @@
 package compiler
 
 import (
+	"debug/dwarf"
 	"errors"
 	"fmt"
 	"go/ast"
@@ -91,6 +92,7 @@ type Compiler struct {
 	dibuilder               *llvm.DIBuilder
 	cu                      llvm.Metadata
 	difiles                 map[string]llvm.Metadata
+	ditypes                 map[types.Type]llvm.Metadata
 	machine                 llvm.TargetMachine
 	targetData              llvm.TargetData
 	intType                 llvm.Type
@@ -136,6 +138,7 @@ func NewCompiler(pkgName string, config Config) (*Compiler, error) {
 	c := &Compiler{
 		Config:  config,
 		difiles: make(map[string]llvm.Metadata),
+		ditypes: make(map[types.Type]llvm.Metadata),
 	}
 
 	target, err := llvm.GetTargetFromTriple(config.Triple)
@@ -596,6 +599,17 @@ func isPointer(typ types.Type) bool {
 
 // Get the DWARF type for this Go type.
 func (c *Compiler) getDIType(typ types.Type) llvm.Metadata {
+	if md, ok := c.ditypes[typ]; ok {
+		return md
+	}
+	md := c.createDIType(typ)
+	c.ditypes[typ] = md
+	return md
+}
+
+// createDIType creates a new DWARF type. Don't call this function directly,
+// call getDIType instead.
+func (c *Compiler) createDIType(typ types.Type) llvm.Metadata {
 	llvmType := c.getLLVMType(typ)
 	sizeInBytes := c.targetData.TypeAllocSize(llvmType)
 	switch typ := typ.(type) {
@@ -732,14 +746,17 @@ func (c *Compiler) getDIType(typ types.Type) llvm.Metadata {
 			},
 		})
 	case *types.Struct:
+		// Placeholder metadata node, to be replaced afterwards.
+		temporaryMDNode := c.dibuilder.CreateReplaceableCompositeType(llvm.Metadata{}, llvm.DIReplaceableCompositeType{
+			Tag:         dwarf.TagStructType,
+			SizeInBits:  sizeInBytes * 8,
+			AlignInBits: uint32(c.targetData.ABITypeAlignment(llvmType)) * 8,
+		})
+		c.ditypes[typ] = temporaryMDNode
 		elements := make([]llvm.Metadata, typ.NumFields())
 		for i := range elements {
 			field := typ.Field(i)
 			fieldType := field.Type()
-			if _, ok := fieldType.Underlying().(*types.Pointer); ok {
-				// XXX hack to avoid recursive types
-				fieldType = types.Typ[types.UnsafePointer]
-			}
 			llvmField := c.getLLVMType(fieldType)
 			elements[i] = c.dibuilder.CreateMemberType(llvm.Metadata{}, llvm.DIMemberType{
 				Name:         field.Name(),
@@ -749,11 +766,13 @@ func (c *Compiler) getDIType(typ types.Type) llvm.Metadata {
 				Type:         c.getDIType(fieldType),
 			})
 		}
-		return c.dibuilder.CreateStructType(llvm.Metadata{}, llvm.DIStructType{
+		md := c.dibuilder.CreateStructType(llvm.Metadata{}, llvm.DIStructType{
 			SizeInBits:  sizeInBytes * 8,
 			AlignInBits: uint32(c.targetData.ABITypeAlignment(llvmType)) * 8,
 			Elements:    elements,
 		})
+		temporaryMDNode.ReplaceAllUsesWith(md)
+		return md
 	default:
 		panic("unknown type while generating DWARF debug type: " + typ.String())
 	}
diff --git a/testdata/structs.go b/testdata/structs.go
index 4ff5068d5..c4ba5d29d 100644
--- a/testdata/structs.go
+++ b/testdata/structs.go
@@ -60,6 +60,13 @@ type s8 struct {
 	b byte   // 1 element
 }
 
+// linked list (recursive type)
+type s9 struct {
+	n    int
+	next *s9
+	s    []*s9
+}
+
 func test0(s s0) {
 	println("test0")
 }
@@ -106,6 +113,10 @@ func test8(s s8) {
 	println("test8", len(s.a), cap(s.a), s.a[0], s.a[1], s.b)
 }
 
+func test9(s s9) {
+	println("test9", s.next.next)
+}
+
 func main() {
 	test0(s0{})
 	test1(s1{1})
@@ -119,4 +130,5 @@ func main() {
 	test6(s6{"foo", 5})
 	test7(s7{a: nil, b: 8})
 	test8(s8{[]byte{12, 13, 14}[:2], 6})
+	test9(s9{next: &s9{}})
 }
diff --git a/testdata/structs.txt b/testdata/structs.txt
index b94ce0344..e0a997d94 100644
--- a/testdata/structs.txt
+++ b/testdata/structs.txt
@@ -9,3 +9,4 @@ test5 1 2 3
 test6 foo 3 5
 test7 (0:nil) 8
 test8 2 3 12 13 6
+test9 nil