cmd/compile: type-based alias resolving has problems

[randall77]

There's something not quite right about how we detect when loads are stores are not to the same address, using type information.

I don't think this is currently a bug, but it is pretty precarious and probably needs to be reorganized to be more sound.

This comes up when we see a load and try to figure out what store it comes from. Consider this program:

package main

import "unsafe"

//go:noinline
func f(p, q *uintptr) uintptr {
	*p = 0
	*(**byte)(unsafe.Pointer(q)) = &g
	return *p
}

var g byte

func main() {
	var u uintptr
	println(f(&u, &u))
}

It currently prints the address of g when run with -N and prints 0 when run without -N.
That's fine. Using unsafe here is writing a pointer to a non-pointer location, which is not allowed. The compiler optimizes by realizing the intermediate write at line 8 can't affect the value of *p because it is writing a pointer, and forwards the 0 stored at line 7 to the load at line 9.

The trouble comes when different parts of our system disagree about the type of certain fields. In particular, this comes up with the type field of interfaces. Some parts of our system treat that field as a uintptr, others treat it as an unsafe.Pointer.

The compiler uses uintptrs to load/store the type field of interfaces. We can, and want, to do that because:

1. The object pointed to by the type field is either something static (type descriptor, interface table) or something allocated by runtime or reflect and kept alive permanently in a side table.
2. It avoids write barriers on the store side.

Unfortunately, other parts of the system use a pointer as the type field of an interface. For example, internal/abi.EmptyInterface or sync/atomic.efaceWords.

This can lead to issues where parts of our system are reading/writing as uintptrs and parts are reading/writing as unsafe.Pointers. Our type-based alias checking, in cmd/compile/internal/ssa/rewrite.go:disjointTypes will treat the two as distinct, meaning it might redirect some load to the wrong store.

I have not figured out how to trigger such a bug at tip currently. But something about this is very fragile. The following patch, which shouldn't really do anything, causes problems:

diff --git a/src/cmd/compile/internal/ssa/_gen/dec.rules b/src/cmd/compile/internal/ssa/_gen/dec.rules
index 97bc2a5978..3ccda284c2 100644
--- a/src/cmd/compile/internal/ssa/_gen/dec.rules
+++ b/src/cmd/compile/internal/ssa/_gen/dec.rules
@@ -86,7 +86,9 @@
 
 (Load <t> ptr mem) && t.IsInterface() =>
   (IMake
-    (Load <typ.Uintptr> ptr mem)
+    (Load <typ.Uintptr>
+      (OffPtr <typ.UintptrPtr> [0] ptr)
+      mem)
     (Load <typ.BytePtr>
       (OffPtr <typ.BytePtrPtr> [config.PtrSize] ptr)
       mem))
@@ -94,7 +96,10 @@
   (Store {typ.BytePtr}
     (OffPtr <typ.BytePtrPtr> [config.PtrSize] dst)
     data
-    (Store {typ.Uintptr} dst itab mem))
+    (Store {typ.Uintptr}
+      (OffPtr <typ.UintptrPtr> [0] dst)
+      itab
+      mem))

It is just enough to get the right types to the type-based alias analysis to cause problems. In particular, it changes the pointer type of the load and store from *any to *uintptr (which is, if anything, more correct).

With that patch, tests fail. For instance

> ../bin/go test sync/atomic -test.run=Value_CompareAndSwap/6
--- FAIL: TestValue_CompareAndSwap (0.00s)
    --- FAIL: TestValue_CompareAndSwap/6 (0.00s)
        value_test.go:242: got false, want true
FAIL
FAIL	sync/atomic	0.006s
FAIL

This is the kind of thing happening in that test:

package main

import "unsafe"

type iface struct {
	typ  *byte
	data *byte
}

//go:noinline
func f(old any) bool {
	i := old
	e := (*iface)(unsafe.Pointer(&i))
	e.typ = &myType
	return i == old
}

var myType byte

func main() {
	println(f(nil))
}

This should print false, but with the patch it prints true.

I'm not sure exactly what to do here. It would be nice if we could have the whole system agree about the type of the type word of interfaces. It would take some work, but maybe we could make that happen for the stdlib. It would be somewhat risky though, as I'm sure there's code outside the stdlib that pokes into interfaces and anything we do might interact with that code badly.

We could just accept that uintptr and pointers might be aliased. This would be the most conservative route, but may end up disabling most type-based alias info.

Other ideas?

@cuonglm @andreybokhanko

[gabyhelp]

Related Issues

• cmd/compile: implement type-based alias analysis #70488 (closed)
• cmd/compile, runtime, reflect: pointers to go:notinheap types must be stored indirectly in interfaces #42076 (closed)
• cmd/gc: make interface updates atomic wrt garbage collector #8405 (closed)
• cmd/compile: pointer shaped type with more than one field causes allocation when cast to interface #74092 (closed)

Related Code Changes

• cmd/compile: add type-based alias analysis

_{(Emoji vote if this was helpful or unhelpful; more detailed feedback welcome in this discussion.)}

[ianlancetaylor]

Type Based Alias Analysis is the kind of compiler optimizations that baffles non-compiler-writers, as it takes code that appears straightforward and compiles into something unexpected. Pedantically, it's not clear to me that the Go memory model permits TBAA at all. It's true that the Go garbage collector generally doesn't permit storing a non-pointer in a variable of pointer type. And it's true that if you store a pointer in a variable of non-pointer type the Go garbage collector doesn't promise that converting the variable to a pointer type will yield a valid pointer. But those are perhaps implementation restrictions.

I think it's worth asking whether the benefit of TBAA is worth the cost in potential confusion.

[andreybokhanko]

Sorry for a late reply. TBH, I moved out of actively working on Go compiler in my daily job.

We could just accept that uintptr and pointers might be aliased. This would be the most conservative route, but may end up disabling most type-based alias info.

Personally, I don't mind going this conservative route -- or removing type-based alias analysis all together. As I wrote in my ticket (#70488) "this doesn't bring any tangible benefits to sweet benchmark". My hope was that my patch would serve as "type-based alias analysis v1.0", with people running it in the wild, reporting bugs / issues (I remember there was just one issue, proven to be an incorrect Go program problem, not Go compiler problem) and then someone (me or someone else) build on top of this, adding more rules and hopefully getting some real perf benefits. However, with cases reported here, this seems to be an unreachable hope. So, for now type-based analysis exists here, doesn't bring any perf benefits (to the best of my knowledge -- Google might test their internal benchmarks to see if they are affected at all), yet brings confusion => better to be removed.

Andrey

[amusman]

I tried to measure the code-size effect (as the most reliable metric to collect) of losing TBAA only for uintptr, and completely disabling disjointTypes:

	base .text	no uintptr TBAA	no TBAA
link	2865860	+0.01%	+0.09%
compile	11320212	+0.00%	+0.01%
cmd/go	6588244	+0.00%	+0.01%
etcd	10136468	+0.00%	+0.01%
6 more tools		+0.01..0.02%	+0.02..0.05%
total	44.3 MB	+2224 B	+8112 B

Disabling TBAA completely costs up to +0.09% of .text, and only for uintptr the effect is smaller. CL 813180 relies on it too, and with it the no-TBAA numbers grow up to about +0.12% (on the link binary). But the current use is still very narrow: disjoint is consulted only by CSE and a few generic rewrite rules, all before lower. Nothing queries it after lowering now; I think there is quite a bit of headroom.

So I'd rather keep TBAA. Currently the issue seems to be from compiler-generated accesses: what if we added a compiler-internal "aliasing" uintptr type variant — used only for the *uintptr views the compiler itself manufactures of pointer-valued words. disjointTypes would treat it as aliasing both pointer-shaped and non-pointer memory. This way no user-visible changes are needed; the trade-off is that we'd need to remember to use the new type in every such compiler-generated view. Happy to prepare CL if this direction makes sense.