// Copyright 2016 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"
	"fmt"
	"strconv"
	"testing"
)

func TestFuseEliminatesOneBranch(t *testing.T) {
	c := testConfig(t)
	ptrType := c.config.Types.BytePtr
	fun := c.Fun("entry",
		Bloc("entry",
			Valu("mem", OpInitMem, types.TypeMem, 0, nil),
			Valu("sb", OpSB, c.config.Types.Uintptr, 0, nil),
			Goto("checkPtr")),
		Bloc("checkPtr",
			Valu("ptr1", OpLoad, ptrType, 0, nil, "sb", "mem"),
			Valu("nilptr", OpConstNil, ptrType, 0, nil),
			Valu("bool1", OpNeqPtr, c.config.Types.Bool, 0, nil, "ptr1", "nilptr"),
			If("bool1", "then", "exit")),
		Bloc("then",
			Goto("exit")),
		Bloc("exit",
			Exit("mem")))

	CheckFunc(fun.f)
	fuseLate(fun.f)

	for _, b := range fun.f.Blocks {
		if b == fun.blocks["then"] && b.Kind != BlockInvalid {
			t.Errorf("then was not eliminated, but should have")
		}
	}
}

func TestFuseEliminatesBothBranches(t *testing.T) {
	c := testConfig(t)
	ptrType := c.config.Types.BytePtr
	fun := c.Fun("entry",
		Bloc("entry",
			Valu("mem", OpInitMem, types.TypeMem, 0, nil),
			Valu("sb", OpSB, c.config.Types.Uintptr, 0, nil),
			Goto("checkPtr")),
		Bloc("checkPtr",
			Valu("ptr1", OpLoad, ptrType, 0, nil, "sb", "mem"),
			Valu("nilptr", OpConstNil, ptrType, 0, nil),
			Valu("bool1", OpNeqPtr, c.config.Types.Bool, 0, nil, "ptr1", "nilptr"),
			If("bool1", "then", "else")),
		Bloc("then",
			Goto("exit")),
		Bloc("else",
			Goto("exit")),
		Bloc("exit",
			Exit("mem")))

	CheckFunc(fun.f)
	fuseLate(fun.f)

	for _, b := range fun.f.Blocks {
		if b == fun.blocks["then"] && b.Kind != BlockInvalid {
			t.Errorf("then was not eliminated, but should have")
		}
		if b == fun.blocks["else"] && b.Kind != BlockInvalid {
			t.Errorf("else was not eliminated, but should have")
		}
	}
}

func TestFuseHandlesPhis(t *testing.T) {
	c := testConfig(t)
	ptrType := c.config.Types.BytePtr
	fun := c.Fun("entry",
		Bloc("entry",
			Valu("mem", OpInitMem, types.TypeMem, 0, nil),
			Valu("sb", OpSB, c.config.Types.Uintptr, 0, nil),
			Goto("checkPtr")),
		Bloc("checkPtr",
			Valu("ptr1", OpLoad, ptrType, 0, nil, "sb", "mem"),
			Valu("nilptr", OpConstNil, ptrType, 0, nil),
			Valu("bool1", OpNeqPtr, c.config.Types.Bool, 0, nil, "ptr1", "nilptr"),
			If("bool1", "then", "else")),
		Bloc("then",
			Goto("exit")),
		Bloc("else",
			Goto("exit")),
		Bloc("exit",
			Valu("phi", OpPhi, ptrType, 0, nil, "ptr1", "ptr1"),
			Exit("mem")))

	CheckFunc(fun.f)
	fuseLate(fun.f)

	for _, b := range fun.f.Blocks {
		if b == fun.blocks["then"] && b.Kind != BlockInvalid {
			t.Errorf("then was not eliminated, but should have")
		}
		if b == fun.blocks["else"] && b.Kind != BlockInvalid {
			t.Errorf("else was not eliminated, but should have")
		}
	}
}

func TestFuseEliminatesEmptyBlocks(t *testing.T) {
	c := testConfig(t)
	// Case 1, plain type empty blocks z0 ~ z3 will be eliminated.
	//     entry
	//       |
	//      z0
	//       |
	//      z1
	//       |
	//      z2
	//       |
	//      z3
	//       |
	//     exit
	fun := c.Fun("entry",
		Bloc("entry",
			Valu("mem", OpInitMem, types.TypeMem, 0, nil),
			Valu("sb", OpSB, c.config.Types.Uintptr, 0, nil),
			Goto("z0")),
		Bloc("z1",
			Goto("z2")),
		Bloc("z3",
			Goto("exit")),
		Bloc("z2",
			Goto("z3")),
		Bloc("z0",
			Goto("z1")),
		Bloc("exit",
			Exit("mem"),
		))

	CheckFunc(fun.f)
	fuseLate(fun.f)

	for k, b := range fun.blocks {
		if k[:1] == "z" && b.Kind != BlockInvalid {
			t.Errorf("case1 %s was not eliminated, but should have", k)
		}
	}

	// Case 2, empty blocks with If branch, z0 and z1 will be eliminated.
	//     entry
	//     /  \
	//    z0  z1
	//     \  /
	//     exit
	fun = c.Fun("entry",
		Bloc("entry",
			Valu("mem", OpInitMem, types.TypeMem, 0, nil),
			Valu("c", OpArg, c.config.Types.Bool, 0, nil),
			If("c", "z0", "z1")),
		Bloc("z0",
			Goto("exit")),
		Bloc("z1",
			Goto("exit")),
		Bloc("exit",
			Exit("mem"),
		))

	CheckFunc(fun.f)
	fuseLate(fun.f)

	for k, b := range fun.blocks {
		if k[:1] == "z" && b.Kind != BlockInvalid {
			t.Errorf("case2 %s was not eliminated, but should have", k)
		}
	}

	// Case 3, empty blocks with multiple predecessors, z0 and z1 will be eliminated.
	//     entry
	//      |  \
	//      |  b0
	//      | /  \
	//      z0   z1
	//       \   /
	//       exit
	fun = c.Fun("entry",
		Bloc("entry",
			Valu("mem", OpInitMem, types.TypeMem, 0, nil),
			Valu("c1", OpArg, c.config.Types.Bool, 0, nil),
			If("c1", "b0", "z0")),
		Bloc("b0",
			Valu("c2", OpArg, c.config.Types.Bool, 0, nil),
			If("c2", "z1", "z0")),
		Bloc("z0",
			Goto("exit")),
		Bloc("z1",
			Goto("exit")),
		Bloc("exit",
			Exit("mem"),
		))

	CheckFunc(fun.f)
	fuseLate(fun.f)

	for k, b := range fun.blocks {
		if k[:1] == "z" && b.Kind != BlockInvalid {
			t.Errorf("case3 %s was not eliminated, but should have", k)
		}
	}
}

func TestFuseSideEffects(t *testing.T) {
	c := testConfig(t)
	// Case1, test that we don't fuse branches that have side effects but
	// have no use (e.g. followed by infinite loop).
	// See issue #36005.
	fun := c.Fun("entry",
		Bloc("entry",
			Valu("mem", OpInitMem, types.TypeMem, 0, nil),
			Valu("b", OpArg, c.config.Types.Bool, 0, nil),
			If("b", "then", "else")),
		Bloc("then",
			Valu("call1", OpStaticCall, types.TypeMem, 0, AuxCallLSym("_"), "mem"),
			Goto("empty")),
		Bloc("else",
			Valu("call2", OpStaticCall, types.TypeMem, 0, AuxCallLSym("_"), "mem"),
			Goto("empty")),
		Bloc("empty",
			Goto("loop")),
		Bloc("loop",
			Goto("loop")))

	CheckFunc(fun.f)
	fuseLate(fun.f)

	for _, b := range fun.f.Blocks {
		if b == fun.blocks["then"] && b.Kind == BlockInvalid {
			t.Errorf("then is eliminated, but should not")
		}
		if b == fun.blocks["else"] && b.Kind == BlockInvalid {
			t.Errorf("else is eliminated, but should not")
		}
	}

	// Case2, z0 contains a value that has side effect, z0 shouldn't be eliminated.
	//     entry
	//      | \
	//      |  z0
	//      | /
	//     exit
	fun = c.Fun("entry",
		Bloc("entry",
			Valu("mem", OpInitMem, types.TypeMem, 0, nil),
			Valu("c1", OpArg, c.config.Types.Bool, 0, nil),
			Valu("p", OpArg, c.config.Types.IntPtr, 0, nil),
			If("c1", "z0", "exit")),
		Bloc("z0",
			Valu("nilcheck", OpNilCheck, c.config.Types.IntPtr, 0, nil, "p", "mem"),
			Goto("exit")),
		Bloc("exit",
			Exit("mem"),
		))
	CheckFunc(fun.f)
	fuseLate(fun.f)
	z0, ok := fun.blocks["z0"]
	if !ok || z0.Kind == BlockInvalid {
		t.Errorf("case2 z0 is eliminated, but should not")
	}
}

func BenchmarkFuse(b *testing.B) {
	for _, n := range [...]int{1, 10, 100, 1000, 10000} {
		b.Run(strconv.Itoa(n), func(b *testing.B) {
			c := testConfig(b)

			blocks := make([]bloc, 0, 2*n+3)
			blocks = append(blocks,
				Bloc("entry",
					Valu("mem", OpInitMem, types.TypeMem, 0, nil),
					Valu("cond", OpArg, c.config.Types.Bool, 0, nil),
					Valu("x", OpArg, c.config.Types.Int64, 0, nil),
					Goto("exit")))

			phiArgs := make([]string, 0, 2*n)
			for i := 0; i < n; i++ {
				cname := fmt.Sprintf("c%d", i)
				blocks = append(blocks,
					Bloc(fmt.Sprintf("b%d", i), If("cond", cname, "merge")),
					Bloc(cname, Goto("merge")))
				phiArgs = append(phiArgs, "x", "x")
			}
			blocks = append(blocks,
				Bloc("merge",
					Valu("phi", OpPhi, types.TypeMem, 0, nil, phiArgs...),
					Goto("exit")),
				Bloc("exit",
					Exit("mem")))

			b.ResetTimer()
			for i := 0; i < b.N; i++ {
				fun := c.Fun("entry", blocks...)
				fuseLate(fun.f)
			}
		})
	}
}