// Copyright 2015 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package ssa

import (
	"cmd/compile/internal/types"
	"cmd/internal/src"
	"fmt"
	"sort"
	"testing"
)

func TestDeadStore(t *testing.T) {
	c := testConfig(t)
	ptrType := c.config.Types.BytePtr
	t.Logf("PTRTYPE %v", ptrType)
	fun := c.Fun("entry",
		Bloc("entry",
			Valu("start", OpInitMem, types.TypeMem, 0, nil),
			Valu("sb", OpSB, c.config.Types.Uintptr, 0, nil),
			Valu("v", OpConstBool, c.config.Types.Bool, 1, nil),
			Valu("addr1", OpAddr, ptrType, 0, nil, "sb"),
			Valu("addr2", OpAddr, ptrType, 0, nil, "sb"),
			Valu("addr3", OpAddr, ptrType, 0, nil, "sb"),
			Valu("zero1", OpZero, types.TypeMem, 1, c.config.Types.Bool, "addr3", "start"),
			Valu("store1", OpStore, types.TypeMem, 0, c.config.Types.Bool, "addr1", "v", "zero1"),
			Valu("store2", OpStore, types.TypeMem, 0, c.config.Types.Bool, "addr2", "v", "store1"),
			Valu("store3", OpStore, types.TypeMem, 0, c.config.Types.Bool, "addr1", "v", "store2"),
			Valu("store4", OpStore, types.TypeMem, 0, c.config.Types.Bool, "addr3", "v", "store3"),
			Goto("exit")),
		Bloc("exit",
			Exit("store3")))

	CheckFunc(fun.f)
	dse(fun.f)
	CheckFunc(fun.f)

	v1 := fun.values["store1"]
	if v1.Op != OpCopy {
		t.Errorf("dead store not removed")
	}

	v2 := fun.values["zero1"]
	if v2.Op != OpCopy {
		t.Errorf("dead store (zero) not removed")
	}
}

func TestDeadStorePhi(t *testing.T) {
	// make sure we don't get into an infinite loop with phi values.
	c := testConfig(t)
	ptrType := c.config.Types.BytePtr
	fun := c.Fun("entry",
		Bloc("entry",
			Valu("start", OpInitMem, types.TypeMem, 0, nil),
			Valu("sb", OpSB, c.config.Types.Uintptr, 0, nil),
			Valu("v", OpConstBool, c.config.Types.Bool, 1, nil),
			Valu("addr", OpAddr, ptrType, 0, nil, "sb"),
			Goto("loop")),
		Bloc("loop",
			Valu("phi", OpPhi, types.TypeMem, 0, nil, "start", "store"),
			Valu("store", OpStore, types.TypeMem, 0, c.config.Types.Bool, "addr", "v", "phi"),
			If("v", "loop", "exit")),
		Bloc("exit",
			Exit("store")))

	CheckFunc(fun.f)
	dse(fun.f)
	CheckFunc(fun.f)
}

func TestDeadStoreTypes(t *testing.T) {
	// Make sure a narrow store can't shadow a wider one. We test an even
	// stronger restriction, that one store can't shadow another unless the
	// types of the address fields are identical (where identicalness is
	// decided by the CSE pass).
	c := testConfig(t)
	t1 := c.config.Types.UInt64.PtrTo()
	t2 := c.config.Types.UInt32.PtrTo()
	fun := c.Fun("entry",
		Bloc("entry",
			Valu("start", OpInitMem, types.TypeMem, 0, nil),
			Valu("sb", OpSB, c.config.Types.Uintptr, 0, nil),
			Valu("v", OpConstBool, c.config.Types.Bool, 1, nil),
			Valu("addr1", OpAddr, t1, 0, nil, "sb"),
			Valu("addr2", OpAddr, t2, 0, nil, "sb"),
			Valu("store1", OpStore, types.TypeMem, 0, c.config.Types.Bool, "addr1", "v", "start"),
			Valu("store2", OpStore, types.TypeMem, 0, c.config.Types.Bool, "addr2", "v", "store1"),
			Goto("exit")),
		Bloc("exit",
			Exit("store2")))

	CheckFunc(fun.f)
	cse(fun.f)
	dse(fun.f)
	CheckFunc(fun.f)

	v := fun.values["store1"]
	if v.Op == OpCopy {
		t.Errorf("store %s incorrectly removed", v)
	}
}

func TestDeadStoreUnsafe(t *testing.T) {
	// Make sure a narrow store can't shadow a wider one. The test above
	// covers the case of two different types, but unsafe pointer casting
	// can get to a point where the size is changed but type unchanged.
	c := testConfig(t)
	ptrType := c.config.Types.UInt64.PtrTo()
	fun := c.Fun("entry",
		Bloc("entry",
			Valu("start", OpInitMem, types.TypeMem, 0, nil),
			Valu("sb", OpSB, c.config.Types.Uintptr, 0, nil),
			Valu("v", OpConstBool, c.config.Types.Bool, 1, nil),
			Valu("addr1", OpAddr, ptrType, 0, nil, "sb"),
			Valu("store1", OpStore, types.TypeMem, 0, c.config.Types.Int64, "addr1", "v", "start"), // store 8 bytes
			Valu("store2", OpStore, types.TypeMem, 0, c.config.Types.Bool, "addr1", "v", "store1"), // store 1 byte
			Goto("exit")),
		Bloc("exit",
			Exit("store2")))

	CheckFunc(fun.f)
	cse(fun.f)
	dse(fun.f)
	CheckFunc(fun.f)

	v := fun.values["store1"]
	if v.Op == OpCopy {
		t.Errorf("store %s incorrectly removed", v)
	}
}

func TestDeadStoreSmallStructInit(t *testing.T) {
	c := testConfig(t)
	ptrType := c.config.Types.BytePtr
	typ := types.NewStruct([]*types.Field{
		types.NewField(src.NoXPos, &types.Sym{Name: "A"}, c.config.Types.Int),
		types.NewField(src.NoXPos, &types.Sym{Name: "B"}, c.config.Types.Int),
	})
	name := c.Temp(typ)
	fun := c.Fun("entry",
		Bloc("entry",
			Valu("start", OpInitMem, types.TypeMem, 0, nil),
			Valu("sp", OpSP, c.config.Types.Uintptr, 0, nil),
			Valu("zero", OpConst64, c.config.Types.Int, 0, nil),
			Valu("v6", OpLocalAddr, ptrType, 0, name, "sp", "start"),
			Valu("v3", OpOffPtr, ptrType, 8, nil, "v6"),
			Valu("v22", OpOffPtr, ptrType, 0, nil, "v6"),
			Valu("zerostore1", OpStore, types.TypeMem, 0, c.config.Types.Int, "v22", "zero", "start"),
			Valu("zerostore2", OpStore, types.TypeMem, 0, c.config.Types.Int, "v3", "zero", "zerostore1"),
			Valu("v8", OpLocalAddr, ptrType, 0, name, "sp", "zerostore2"),
			Valu("v23", OpOffPtr, ptrType, 8, nil, "v8"),
			Valu("v25", OpOffPtr, ptrType, 0, nil, "v8"),
			Valu("zerostore3", OpStore, types.TypeMem, 0, c.config.Types.Int, "v25", "zero", "zerostore2"),
			Valu("zerostore4", OpStore, types.TypeMem, 0, c.config.Types.Int, "v23", "zero", "zerostore3"),
			Goto("exit")),
		Bloc("exit",
			Exit("zerostore4")))

	fun.f.Name = "smallstructinit"
	CheckFunc(fun.f)
	cse(fun.f)
	dse(fun.f)
	CheckFunc(fun.f)

	v1 := fun.values["zerostore1"]
	if v1.Op != OpCopy {
		t.Errorf("dead store not removed")
	}
	v2 := fun.values["zerostore2"]
	if v2.Op != OpCopy {
		t.Errorf("dead store not removed")
	}
}

func TestDeadStoreArrayGap(t *testing.T) {
	c := testConfig(t)
	ptr := c.config.Types.BytePtr
	i64 := c.config.Types.Int64

	typ := types.NewArray(i64, 5)
	tmp := c.Temp(typ)

	fun := c.Fun("entry",
		Bloc("entry",
			Valu("start", OpInitMem, types.TypeMem, 0, nil),
			Valu("sp", OpSP, c.config.Types.Uintptr, 0, nil),

			Valu("base", OpLocalAddr, ptr, 0, tmp, "sp", "start"),

			Valu("p0", OpOffPtr, ptr, 0, nil, "base"),
			Valu("p1", OpOffPtr, ptr, 8, nil, "base"),
			Valu("p2", OpOffPtr, ptr, 16, nil, "base"),
			Valu("p3", OpOffPtr, ptr, 24, nil, "base"),
			Valu("p4", OpOffPtr, ptr, 32, nil, "base"),

			Valu("one", OpConst64, i64, 1, nil),
			Valu("seven", OpConst64, i64, 7, nil),
			Valu("zero", OpConst64, i64, 0, nil),

			Valu("mem0", OpZero, types.TypeMem, 40, typ, "base", "start"),

			Valu("s0", OpStore, types.TypeMem, 0, i64, "p0", "one", "mem0"),
			Valu("s1", OpStore, types.TypeMem, 0, i64, "p1", "seven", "s0"),
			Valu("s2", OpStore, types.TypeMem, 0, i64, "p3", "one", "s1"),
			Valu("s3", OpStore, types.TypeMem, 0, i64, "p4", "one", "s2"),
			Valu("s4", OpStore, types.TypeMem, 0, i64, "p2", "zero", "s3"),

			Goto("exit")),
		Bloc("exit",
			Exit("s4")))

	CheckFunc(fun.f)
	dse(fun.f)
	CheckFunc(fun.f)

	if op := fun.values["mem0"].Op; op != OpCopy {
		t.Fatalf("dead Zero not removed: got %s, want OpCopy", op)
	}
}

func TestShadowRanges(t *testing.T) {
	t.Run("simple insert & contains", func(t *testing.T) {
		var sr shadowRanges
		sr.add(10, 20)

		wantRanges(t, sr.ranges, [][2]uint16{{10, 20}})
		if !sr.contains(12, 18) || !sr.contains(10, 20) {
			t.Fatalf("contains failed after simple add")
		}
		if sr.contains(9, 11) || sr.contains(11, 21) {
			t.Fatalf("contains erroneously true for non-contained range")
		}
	})

	t.Run("merge overlapping", func(t *testing.T) {
		var sr shadowRanges
		sr.add(10, 20)
		sr.add(15, 25)

		wantRanges(t, sr.ranges, [][2]uint16{{10, 25}})
		if !sr.contains(13, 24) {
			t.Fatalf("contains should be true after merge")
		}
	})

	t.Run("merge touching boundary", func(t *testing.T) {
		var sr shadowRanges
		sr.add(100, 150)
		// touches at 150 - should coalesce
		sr.add(150, 180)

		wantRanges(t, sr.ranges, [][2]uint16{{100, 180}})
	})

	t.Run("union across several ranges", func(t *testing.T) {
		var sr shadowRanges
		sr.add(10, 20)
		sr.add(30, 40)
		// bridges second, not first
		sr.add(25, 35)

		wantRanges(t, sr.ranges, [][2]uint16{{10, 20}, {25, 40}})

		// envelops everything
		sr.add(5, 50)
		wantRanges(t, sr.ranges, [][2]uint16{{5, 50}})
	})

	t.Run("disjoint intervals stay separate", func(t *testing.T) {
		var sr shadowRanges
		sr.add(10, 20)
		sr.add(22, 30)

		wantRanges(t, sr.ranges, [][2]uint16{{10, 20}, {22, 30}})
		// spans both
		if sr.contains(15, 25) {
			t.Fatalf("contains across two disjoint ranges should be false")
		}
	})

	t.Run("large uint16 offsets still work", func(t *testing.T) {
		var sr shadowRanges
		sr.add(40000, 45000)

		if !sr.contains(42000, 43000) {
			t.Fatalf("contains failed for large uint16 values")
		}
	})

	t.Run("out-of-bounds inserts ignored", func(t *testing.T) {
		var sr shadowRanges
		sr.add(10, 20)
		sr.add(-5, 5)
		sr.add(70000, 70010)

		wantRanges(t, sr.ranges, [][2]uint16{{10, 20}})
	})
}

// canonicalise order for comparisons
func sortRanges(r []shadowRange) {
	sort.Slice(r, func(i, j int) bool { return r[i].lo < r[j].lo })
}

// compare actual slice with expected pairs
func wantRanges(t *testing.T, got []shadowRange, want [][2]uint16) {
	t.Helper()
	sortRanges(got)

	if len(got) != len(want) {
		t.Fatalf("len(ranges)=%d, want %d (got=%v)", len(got), len(want), got)
	}

	for i, w := range want {
		if got[i].lo != w[0] || got[i].hi != w[1] {
			t.Fatalf("range %d = [%d,%d], want [%d,%d] (full=%v)",
				i, got[i].lo, got[i].hi, w[0], w[1], got)
		}
	}
}

func BenchmarkDeadStore(b *testing.B) {
	cfg := testConfig(b)
	ptr := cfg.config.Types.BytePtr

	f := cfg.Fun("entry",
		Bloc("entry",
			Valu("start", OpInitMem, types.TypeMem, 0, nil),
			Valu("sb", OpSB, cfg.config.Types.Uintptr, 0, nil),
			Valu("v", OpConstBool, cfg.config.Types.Bool, 1, nil),
			Valu("a1", OpAddr, ptr, 0, nil, "sb"),
			Valu("a2", OpAddr, ptr, 0, nil, "sb"),
			Valu("a3", OpAddr, ptr, 0, nil, "sb"),
			Valu("z1", OpZero, types.TypeMem, 1, cfg.config.Types.Bool, "a3", "start"),
			Valu("s1", OpStore, types.TypeMem, 0, cfg.config.Types.Bool, "a1", "v", "z1"),
			Valu("s2", OpStore, types.TypeMem, 0, cfg.config.Types.Bool, "a2", "v", "s1"),
			Valu("s3", OpStore, types.TypeMem, 0, cfg.config.Types.Bool, "a1", "v", "s2"),
			Valu("s4", OpStore, types.TypeMem, 0, cfg.config.Types.Bool, "a3", "v", "s3"),
			Goto("exit")),
		Bloc("exit",
			Exit("s3")))

	runBench(b, func() {
		dse(f.f)
	})
}

func BenchmarkDeadStorePhi(b *testing.B) {
	cfg := testConfig(b)
	ptr := cfg.config.Types.BytePtr

	f := cfg.Fun("entry",
		Bloc("entry",
			Valu("start", OpInitMem, types.TypeMem, 0, nil),
			Valu("sb", OpSB, cfg.config.Types.Uintptr, 0, nil),
			Valu("v", OpConstBool, cfg.config.Types.Bool, 1, nil),
			Valu("addr", OpAddr, ptr, 0, nil, "sb"),
			Goto("loop")),
		Bloc("loop",
			Valu("phi", OpPhi, types.TypeMem, 0, nil, "start", "store"),
			Valu("store", OpStore, types.TypeMem, 0, cfg.config.Types.Bool, "addr", "v", "phi"),
			If("v", "loop", "exit")),
		Bloc("exit",
			Exit("store")))

	runBench(b, func() {
		dse(f.f)
	})
}

func BenchmarkDeadStoreTypes(b *testing.B) {
	cfg := testConfig(b)

	t1 := cfg.config.Types.UInt64.PtrTo()
	t2 := cfg.config.Types.UInt32.PtrTo()

	f := cfg.Fun("entry",
		Bloc("entry",
			Valu("start", OpInitMem, types.TypeMem, 0, nil),
			Valu("sb", OpSB, cfg.config.Types.Uintptr, 0, nil),
			Valu("v", OpConstBool, cfg.config.Types.Bool, 1, nil),
			Valu("a1", OpAddr, t1, 0, nil, "sb"),
			Valu("a2", OpAddr, t2, 0, nil, "sb"),
			Valu("s1", OpStore, types.TypeMem, 0, cfg.config.Types.Bool, "a1", "v", "start"),
			Valu("s2", OpStore, types.TypeMem, 0, cfg.config.Types.Bool, "a2", "v", "s1"),
			Goto("exit")),
		Bloc("exit",
			Exit("s2")))
	cse(f.f)

	runBench(b, func() {
		dse(f.f)
	})
}

func BenchmarkDeadStoreUnsafe(b *testing.B) {
	cfg := testConfig(b)
	ptr := cfg.config.Types.UInt64.PtrTo()
	f := cfg.Fun("entry",
		Bloc("entry",
			Valu("start", OpInitMem, types.TypeMem, 0, nil),
			Valu("sb", OpSB, cfg.config.Types.Uintptr, 0, nil),
			Valu("v", OpConstBool, cfg.config.Types.Bool, 1, nil),
			Valu("a1", OpAddr, ptr, 0, nil, "sb"),
			Valu("s1", OpStore, types.TypeMem, 0, cfg.config.Types.Int64, "a1", "v", "start"),
			Valu("s2", OpStore, types.TypeMem, 0, cfg.config.Types.Bool, "a1", "v", "s1"),
			Goto("exit")),
		Bloc("exit",
			Exit("s2")))
	cse(f.f)
	runBench(b, func() {
		dse(f.f)
	})
}

func BenchmarkDeadStoreSmallStructInit(b *testing.B) {
	cfg := testConfig(b)
	ptr := cfg.config.Types.BytePtr

	typ := types.NewStruct([]*types.Field{
		types.NewField(src.NoXPos, &types.Sym{Name: "A"}, cfg.config.Types.Int),
		types.NewField(src.NoXPos, &types.Sym{Name: "B"}, cfg.config.Types.Int),
	})
	tmp := cfg.Temp(typ)

	f := cfg.Fun("entry",
		Bloc("entry",
			Valu("start", OpInitMem, types.TypeMem, 0, nil),
			Valu("sp", OpSP, cfg.config.Types.Uintptr, 0, nil),
			Valu("zero", OpConst64, cfg.config.Types.Int, 0, nil),

			Valu("v6", OpLocalAddr, ptr, 0, tmp, "sp", "start"),
			Valu("v3", OpOffPtr, ptr, 8, nil, "v6"),
			Valu("v22", OpOffPtr, ptr, 0, nil, "v6"),
			Valu("s1", OpStore, types.TypeMem, 0, cfg.config.Types.Int, "v22", "zero", "start"),
			Valu("s2", OpStore, types.TypeMem, 0, cfg.config.Types.Int, "v3", "zero", "s1"),

			Valu("v8", OpLocalAddr, ptr, 0, tmp, "sp", "s2"),
			Valu("v23", OpOffPtr, ptr, 8, nil, "v8"),
			Valu("v25", OpOffPtr, ptr, 0, nil, "v8"),
			Valu("s3", OpStore, types.TypeMem, 0, cfg.config.Types.Int, "v25", "zero", "s2"),
			Valu("s4", OpStore, types.TypeMem, 0, cfg.config.Types.Int, "v23", "zero", "s3"),
			Goto("exit")),
		Bloc("exit",
			Exit("s4")))
	cse(f.f)

	runBench(b, func() {
		dse(f.f)
	})
}

func BenchmarkDeadStoreLargeBlock(b *testing.B) {
	// create a very large block with many shadowed stores
	const (
		addrCount = 128
		// first 7 are dead
		storesPerAddr = 8
	)
	cfg := testConfig(b)
	ptrType := cfg.config.Types.BytePtr
	boolType := cfg.config.Types.Bool

	items := []interface{}{
		Valu("start", OpInitMem, types.TypeMem, 0, nil),
		Valu("sb", OpSB, cfg.config.Types.Uintptr, 0, nil),
		Valu("v", OpConstBool, boolType, 1, nil),
	}

	for i := 0; i < addrCount; i++ {
		items = append(items,
			Valu(fmt.Sprintf("addr%d", i), OpAddr, ptrType, 0, nil, "sb"),
		)
	}

	prev := "start"
	for round := 0; round < storesPerAddr; round++ {
		for i := 0; i < addrCount; i++ {
			store := fmt.Sprintf("s_%03d_%d", i, round)
			addr := fmt.Sprintf("addr%d", i)
			items = append(items,
				Valu(store, OpStore, types.TypeMem, 0, boolType, addr, "v", prev),
			)
			prev = store
		}
	}

	items = append(items, Goto("exit"))
	entryBlk := Bloc("entry", items...)
	exitBlk := Bloc("exit", Exit(prev))

	f := cfg.Fun("stress", entryBlk, exitBlk)

	runBench(b, func() {
		dse(f.f)
	})
}

func runBench(b *testing.B, build func()) {
	b.ReportAllocs()
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		build()
	}
}