function_analysis_test.go

package ember

import (
	"testing"
)

func TestFunctionIRCachesAnalysisUntilInstructionsChange(t *testing.T) {
	ir := []bytecodeIRInstruction{
		lowerInstructionToBytecodeIR(instruction{op: opLoadConst, a: 0, b: 0}, sourceRange{}),
		lowerInstructionToBytecodeIR(instruction{op: opReturnOne, a: 0}, sourceRange{}),
	}
	function := newFunctionIR(ir)
	first := function.currentAnalysis()
	if first == nil {
		t.Fatal("currentAnalysis returned nil")
	}
	if got := function.currentAnalysis(); got != first {
		t.Fatal("unchanged function rebuilt analysis")
	}

	same := append([]bytecodeIRInstruction(nil), ir...)
	function.replace(same)
	if function.revision != 0 {
		t.Fatalf("identical replacement advanced revision to %d, want 0", function.revision)
	}
	if got := function.currentAnalysis(); got != first {
		t.Fatal("identical replacement rebuilt analysis")
	}

	changed := append([]bytecodeIRInstruction(nil), ir...)
	if !changed[0].setOperandValue(bytecodeIROperandSlotA, 1) {
		t.Fatal("set IR operand failed")
	}
	function.replace(changed)
	if function.revision != 1 {
		t.Fatalf("changed replacement advanced revision to %d, want 1", function.revision)
	}
	second := function.currentAnalysis()
	if second == first {
		t.Fatal("changed function reused stale analysis")
	}
	if second.revision != function.revision {
		t.Fatalf("analysis revision is %d, want %d", second.revision, function.revision)
	}
}

func TestFunctionIRCachesBytecodeFeaturesUntilInstructionsChange(t *testing.T) {
	ir := []bytecodeIRInstruction{
		lowerInstructionToBytecodeIR(instruction{op: opLoadConst, a: 0, b: 0}, sourceRange{}),
		lowerInstructionToBytecodeIR(instruction{op: opReturnOne, a: 0}, sourceRange{}),
	}
	function := newFunctionIR(ir)
	first := function.currentFeatures()
	if first.hasMove || first.hasControlFlow || first.hasBackedge || first.hasCall {
		t.Fatalf("return-only features = %#v, want all false", first)
	}
	if !function.featuresValid {
		t.Fatal("initial bytecode features were not marked valid")
	}
	function.replace(append([]bytecodeIRInstruction(nil), ir...))
	if !function.featuresValid {
		t.Fatal("identical replacement invalidated bytecode features")
	}
	changed := append([]bytecodeIRInstruction(nil), ir...)
	changed[0] = lowerInstructionToBytecodeIR(instruction{op: opMove, a: 1, b: 0}, sourceRange{})
	function.replace(changed)
	if function.featuresValid {
		t.Fatal("changed replacement retained stale bytecode features")
	}
	updated := function.currentFeatures()
	if !updated.hasMove || updated.hasControlFlow || updated.hasBackedge || updated.hasCall {
		t.Fatalf("changed features = %#v, want move only", updated)
	}
}

func TestFunctionIRReusesAnalysisForValueOnlyChanges(t *testing.T) {
	base := []bytecodeIRInstruction{
		lowerInstructionToBytecodeIR(instruction{op: opLoadConst, a: 0, b: 0}, sourceRange{}),
		lowerInstructionToBytecodeIR(instruction{op: opReturnOne, a: 0}, sourceRange{}),
	}
	function := newFunctionIR(base)
	analysis := function.currentAnalysis()
	raw := function.currentCode()
	if got := function.currentCode(); len(got) == 0 || &got[0] != &raw[0] {
		t.Fatal("unchanged function rebuilt assembled view")
	}

	constantOnly := append([]bytecodeIRInstruction(nil), base...)
	constantOnly[0] = lowerInstructionToBytecodeIR(instruction{op: opLoadConst, a: 0, b: 1}, sourceRange{})
	function.replace(constantOnly)
	if got := function.currentAnalysis(); got != analysis {
		t.Fatal("constant-only replacement rebuilt CFG/liveness analysis")
	}
	rawAfterConstant := function.currentCode()
	if &rawAfterConstant[0] == &raw[0] {
		t.Fatal("constant-only replacement reused stale assembled view")
	}

	sourceOnly := append([]bytecodeIRInstruction(nil), constantOnly...)
	sourceOnly[0].sourceStart = 12
	sourceOnly[0].sourceEnd = 18
	function.replace(sourceOnly)
	if got := function.currentAnalysis(); got != analysis {
		t.Fatal("source-only replacement rebuilt CFG/liveness analysis")
	}
	if got := function.currentCode(); len(got) == 0 || &got[0] != &rawAfterConstant[0] {
		t.Fatal("source-only replacement rebuilt unchanged assembled view")
	}
}

func TestFunctionIRInvalidatesOnlyAffectedAnalysis(t *testing.T) {
	base := []bytecodeIRInstruction{
		lowerInstructionToBytecodeIR(instruction{op: opMove, a: 0, b: 1}, sourceRange{}),
		lowerInstructionToBytecodeIR(instruction{op: opReturnOne, a: 0}, sourceRange{}),
	}
	function := newFunctionIR(base)
	analysis := function.currentAnalysis()
	if len(analysis.blocks) == 0 || len(analysis.liveness) == 0 {
		t.Fatal("baseline analysis is empty")
	}
	blocks := &analysis.blocks[0]
	liveness := &analysis.liveness[0]

	registerOnly := append([]bytecodeIRInstruction(nil), base...)
	registerOnly[0] = lowerInstructionToBytecodeIR(instruction{op: opMove, a: 1, b: 2}, sourceRange{})
	function.replace(registerOnly)
	updated := function.currentAnalysis()
	if len(updated.blocks) == 0 || &updated.blocks[0] != blocks {
		t.Fatal("register-only replacement rebuilt CFG blocks")
	}
	if len(updated.liveness) == 0 || &updated.liveness[0] == liveness {
		t.Fatal("register-only replacement reused stale liveness")
	}

	jumpBase := []bytecodeIRInstruction{
		lowerInstructionToBytecodeIR(instruction{op: opJump, b: 2}, sourceRange{}),
		lowerInstructionToBytecodeIR(instruction{op: opReturnOne, a: 0}, sourceRange{}),
		lowerInstructionToBytecodeIR(instruction{op: opReturnOne, a: 0}, sourceRange{}),
	}
	function = newFunctionIR(jumpBase)
	jumpAnalysis := function.currentAnalysis()
	jumpBlocks := &jumpAnalysis.blocks[0]
	jumpChanged := append([]bytecodeIRInstruction(nil), jumpBase...)
	jumpChanged[0] = lowerInstructionToBytecodeIR(instruction{op: opJump, b: 1}, sourceRange{})
	function.replace(jumpChanged)
	if got := function.currentAnalysis(); len(got.blocks) == 0 || &got.blocks[0] == jumpBlocks {
		t.Fatal("jump-target replacement reused stale CFG")
	}
}

func TestFunctionIRCountAndOpcodeChangesInvalidateExpectedLayers(t *testing.T) {
	callBase := []bytecodeIRInstruction{
		lowerInstructionToBytecodeIR(instruction{op: opCall, a: 0, b: 1, c: 1, d: 1}, sourceRange{}),
		lowerInstructionToBytecodeIR(instruction{op: opReturnOne, a: 0}, sourceRange{}),
	}
	function := newFunctionIR(callBase)
	analysis := function.currentAnalysis()
	blocks := &analysis.blocks[0]
	countChanged := append([]bytecodeIRInstruction(nil), callBase...)
	countChanged[0] = lowerInstructionToBytecodeIR(instruction{op: opCall, a: 0, b: 1, c: 2, d: 1}, sourceRange{})
	function.replace(countChanged)
	updated := function.currentAnalysis()
	if len(updated.blocks) == 0 || &updated.blocks[0] != blocks {
		t.Fatal("count-only replacement rebuilt CFG")
	}
	if len(updated.liveness) == 0 || &updated.liveness[0] == &analysis.liveness[0] {
		t.Fatal("count-only replacement reused stale liveness")
	}

	opcodeChanged := append([]bytecodeIRInstruction(nil), countChanged...)
	opcodeChanged[0] = lowerInstructionToBytecodeIR(instruction{op: opLoadConst, a: 0, b: 0}, sourceRange{})
	function.replace(opcodeChanged)
	if got := function.currentAnalysis(); got == updated || len(got.effects) == 0 || got.effects[0] == updated.effects[0] {
		t.Fatal("opcode-only replacement reused stale full analysis")
	}

	rawBefore := function.currentCode()
	unusedRaw := append([]bytecodeIRInstruction(nil), opcodeChanged...)
	unusedRaw[0].d = 77
	function.replace(unusedRaw)
	before := function.currentCode()
	if &before[0] == &rawBefore[0] {
		t.Fatal("unused raw operand change reused stale assembled view")
	}
	if before[0].d != 77 {
		t.Fatalf("unused raw operand=%d, want 77", before[0].d)
	}
}

func TestFunctionIROwnsInstructionSlicesAcrossAliases(t *testing.T) {
	input := []bytecodeIRInstruction{lowerInstructionToBytecodeIR(instruction{op: opReturnOne, a: 0}, sourceRange{})}
	function := newFunctionIR(input)
	input[0] = lowerInstructionToBytecodeIR(instruction{op: opJump, b: 0}, sourceRange{})
	if got := function.currentFeatures(); got.hasControlFlow {
		t.Fatal("mutating constructor input changed owned function IR")
	}

	replacement := []bytecodeIRInstruction{lowerInstructionToBytecodeIR(instruction{op: opMove, a: 0, b: 1}, sourceRange{})}
	function.replace(replacement)
	replacement[0] = lowerInstructionToBytecodeIR(instruction{op: opJump, b: 0}, sourceRange{})
	if got := function.currentFeatures(); got.hasControlFlow {
		t.Fatal("mutating replacement input changed owned function IR")
	}
}

func TestOptimizerPlanGatesOpcodeFamilies(t *testing.T) {
	toIR := func(code ...instruction) []bytecodeIRInstruction {
		ir := make([]bytecodeIRInstruction, len(code))
		for index, instruction := range code {
			ir[index] = lowerInstructionToBytecodeIR(instruction, sourceRange{})
		}
		return ir
	}
	if plan := optimizerPlanForIR(toIR(instruction{op: opReturnOne, a: 0})); plan.runControlFlow || plan.runMoves || plan.runLoop {
		t.Fatalf("return-only optimizer plan = %#v, want no optional passes", plan)
	}
	returnWithDeadTail := optimizerPlanForIR(toIR(
		instruction{op: opReturnOne, a: 0},
		instruction{op: opLoadConst, a: 0, b: 0},
	))
	if !returnWithDeadTail.runControlFlow || returnWithDeadTail.runMoves || returnWithDeadTail.runLoop {
		t.Fatalf("return-with-tail optimizer plan = %#v, want control-flow only", returnWithDeadTail)
	}
	branch := optimizerPlanForIR(toIR(
		instruction{op: opJumpIfFalse, a: 0, b: 2},
		instruction{op: opReturnOne, a: 0},
		instruction{op: opReturnOne, a: 0},
	))
	if !branch.runControlFlow || branch.runMoves || branch.runLoop {
		t.Fatalf("branch optimizer plan = %#v, want control-flow only", branch)
	}
	backedge := optimizerPlanForIR(toIR(
		instruction{op: opJump, b: 0},
		instruction{op: opReturnOne, a: 0},
	))
	if !backedge.runControlFlow || !backedge.runLoop {
		t.Fatalf("backedge optimizer plan = %#v, want control-flow and loop work", backedge)
	}
	moves := optimizerPlanForIR(toIR(
		instruction{op: opMove, a: 1, b: 0},
		instruction{op: opReturnOne, a: 1},
	))
	if !moves.runMoves || moves.runControlFlow || moves.runLoop {
		t.Fatalf("move optimizer plan = %#v, want move work only", moves)
	}
	for _, op := range []opcode{opCall, opCallOne, opCallLocalOne, opCallUpvalueOne} {
		features := newFunctionIR(toIR(instruction{op: op})).currentFeatures()
		if !features.hasCall {
			t.Fatalf("call opcode %v did not set hasCall", op)
		}
	}
	for raw := 0; raw < int(opcodeLimit); raw++ {
		op := opcode(raw)
		features := newFunctionIR(toIR(instruction{op: op})).currentFeatures()
		if opcodeMayCall(op) != features.hasCall {
			t.Fatalf("opcode %d call feature = %t, opcodeMayCall = %t", raw, features.hasCall, opcodeMayCall(op))
		}
	}
	for _, target := range []int{-1, 2} {
		ir := toIR(instruction{op: opJump, b: target}, instruction{op: opReturnOne, a: 0})
		features := newFunctionIR(ir).currentFeatures()
		if !features.hasControlFlow || features.hasBackedge {
			t.Fatalf("malformed jump target %d features = %#v, want control-flow only", target, features)
		}
	}
}

func TestFunctionAnalysisOwnsCFGDataflowAndEffects(t *testing.T) {
	ir := []bytecodeIRInstruction{
		lowerInstructionToBytecodeIR(instruction{op: opJumpIfFalse, a: 0, b: 2}, sourceRange{}),
		lowerInstructionToBytecodeIR(instruction{op: opReturnOne, a: 1}, sourceRange{}),
		lowerInstructionToBytecodeIR(instruction{op: opLoadConst, a: 1, b: 0}, sourceRange{}),
		lowerInstructionToBytecodeIR(instruction{op: opReturnOne, a: 1}, sourceRange{}),
	}
	function := newFunctionIR(ir)
	analysis := function.currentAnalysis()

	if len(analysis.blocks) != 3 || len(analysis.successors) != 3 || len(analysis.predecessors) != 3 {
		t.Fatalf("analysis CFG sizes are blocks=%d successors=%d predecessors=%d, want 3 each", len(analysis.blocks), len(analysis.successors), len(analysis.predecessors))
	}
	if len(analysis.reachable) != 3 || !analysis.reachable[0] || !analysis.reachable[1] || !analysis.reachable[2] {
		t.Fatalf("analysis reachability is %#v, want all three blocks reachable", analysis.reachable)
	}
	if len(analysis.use) != 3 || len(analysis.def) != 3 || len(analysis.liveness) != 3 {
		t.Fatalf("analysis dataflow sizes are use=%d def=%d liveness=%d, want 3 each", len(analysis.use), len(analysis.def), len(analysis.liveness))
	}
	if !analysis.use[0].contains(0) {
		t.Fatal("entry block use set does not contain branch register 0")
	}
	if len(analysis.effects) != len(ir) || analysis.effects[0] != opcodeEffect(opJumpIfFalse) || analysis.effects[2] != opcodeEffect(opLoadConst) {
		t.Fatalf("analysis effects are %#v, want per-instruction opcode effects", analysis.effects)
	}
}

func TestFunctionAnalysisComputesEphemeralLiveAfter(t *testing.T) {
	ir := []bytecodeIRInstruction{
		lowerInstructionToBytecodeIR(instruction{op: opLoadConst, a: 0, b: 0}, sourceRange{}),
		lowerInstructionToBytecodeIR(instruction{op: opMove, a: 1, b: 0}, sourceRange{}),
		lowerInstructionToBytecodeIR(instruction{op: opReturnOne, a: 1}, sourceRange{}),
	}
	analysis := newFunctionIR(ir).currentAnalysis()
	if len(analysis.liveAfter) != len(ir) {
		t.Fatalf("live-after length = %d, want %d", len(analysis.liveAfter), len(ir))
	}
	if !analysis.liveAfter[0].contains(0) {
		t.Fatal("load's result was not live after the load")
	}
	if !analysis.liveAfter[1].contains(1) || analysis.liveAfter[1].contains(0) {
		t.Fatalf("move live-after set = %#v, want only r1", analysis.liveAfter[1].values())
	}
	if len(analysis.liveAfter[2].values()) != 0 {
		t.Fatalf("return live-after set = %#v, want empty", analysis.liveAfter[2].values())
	}
}

func TestFixedCallBorrowFactsRejectUnsafeSuffixes(t *testing.T) {
	base := []instruction{
		{op: opCallLocalOne, a: 0, b: 3, c: 1, d: 2},
		{op: opReturnOne, a: 0},
	}
	facts := analyzeFixedCallBorrowFacts(base, 5, nil)
	if len(facts) != 1 || !facts[0].eligible {
		t.Fatalf("safe fixed-call fact = %#v, want eligible", facts)
	}

	liveSuffix := append([]instruction(nil), base...)
	liveSuffix[1] = instruction{op: opReturnOne, a: 4}
	if fact := analyzeFixedCallBorrowFacts(liveSuffix, 5, nil)[0]; fact.eligible || fact.reason == "" {
		t.Fatalf("live suffix fact = %#v, want rejection reason", fact)
	}

	captured := analyzeFixedCallBorrowFacts(base, 5, []bool{false, true, false, false, false})[0]
	if captured.eligible || captured.reason == "" {
		t.Fatalf("captured suffix fact = %#v, want rejection reason", captured)
	}

	destinationOverlap := []instruction{
		{op: opCallLocalOne, a: 3, b: 0, c: 1, d: 1},
		{op: opReturnOne, a: 3},
	}
	overlap := analyzeFixedCallBorrowFacts(destinationOverlap, 5, nil)[0]
	if overlap.eligible || overlap.reason == "" {
		t.Fatalf("destination-overlap fact = %#v, want rejection reason", overlap)
	}
}

func TestFixedCallBorrowFactsHandleMissingExtraArgsAndRecursion(t *testing.T) {
	for _, count := range []int{0, 3} {
		code := []instruction{
			{op: opCallLocalOne, a: 0, b: 3, c: 1, d: count},
			{op: opReturnOne, a: 0},
		}
		facts := analyzeFixedCallBorrowFacts(code, 5, nil)
		if len(facts) != 1 || !facts[0].eligible {
			t.Fatalf("fixed-call count %d fact = %#v, want eligible", count, facts)
		}
	}

	recursive := []instruction{
		{op: opCallLocalOne, a: 0, b: 3, c: 1, d: 2},
		{op: opJumpIfFalse, a: 0, b: 0},
		{op: opReturnOne, a: 0},
	}
	facts := analyzeFixedCallBorrowFacts(recursive, 5, nil)
	if len(facts) != 1 || facts[0].eligible || facts[0].reason == "" {
		t.Fatalf("recursive fixed-call fact = %#v, want deterministic rejection", facts)
	}
}

func TestMarkBorrowableFixedCallWindowsEncodesEligibleCallShapes(t *testing.T) {
	callOne := markBorrowableFixedCallWindows([]instruction{
		{op: opCallOne, a: 0, b: 3, c: 2}, {op: opReturnOne, a: 0},
	}, 6, nil)
	if got, borrow := decodeFixedCallCount(callOne[0].c); got != 2 || !borrow {
		t.Fatalf("CALL_ONE count = (%d, %t), want (2, true)", got, borrow)
	}
	local := markBorrowableFixedCallWindows([]instruction{
		{op: opCallLocalOne, a: 0, b: 3, c: 1, d: 2}, {op: opReturnOne, a: 0},
	}, 6, nil)
	if got, borrow := decodeFixedCallCount(local[0].d); got != 2 || !borrow {
		t.Fatalf("CALL_LOCAL_ONE count = (%d, %t), want (2, true)", got, borrow)
	}
	upvalue := markBorrowableFixedCallWindows([]instruction{
		{op: opCallUpvalueOne, a: 0, b: 0, c: 1, d: 2}, {op: opReturnOne, a: 0},
	}, 6, nil)
	if got, borrow := decodeFixedCallCount(upvalue[0].d); got != 2 || !borrow {
		t.Fatalf("CALL_UPVALUE_ONE count = (%d, %t), want (2, true)", got, borrow)
	}
	method := markBorrowableFixedCallWindows([]instruction{
		{op: opCallMethodOne, a: 0, b: 3, c: 0, d: 1}, {op: opReturnOne, a: 0},
	}, 6, nil)
	if got, borrow := decodeFixedCallCount(method[0].d); got != 1 || !borrow {
		t.Fatalf("CALL_METHOD_ONE count = (%d, %t), want (1, true)", got, borrow)
	}
	methodFact := analyzeFixedCallBorrowFacts([]instruction{
		{op: opCallMethodOne, a: 0, b: 3, c: 0, d: 1}, {op: opReturnOne, a: 0},
	}, 6, nil)[0]
	if methodFact.argumentStart != 1 || methodFact.argumentCount != 2 || methodFact.result != 0 {
		t.Fatalf("method borrow shape = start %d count %d result %d, want 1, 2, 0", methodFact.argumentStart, methodFact.argumentCount, methodFact.result)
	}
	generic := []instruction{
		{op: opCall, a: 0, b: 3, c: -2, d: 1}, {op: opReturnOne, a: 0},
	}
	markedGeneric := markBorrowableFixedCallWindows(generic, 6, nil)
	if markedGeneric[0].c != generic[0].c {
		t.Fatalf("generic CALL count changed from %d to %d", generic[0].c, markedGeneric[0].c)
	}
	fixedMulti := []instruction{
		{op: opCall, a: 0, b: 2, c: 0, d: 2},
		{op: opReturn, a: 0, b: 2},
	}
	markedMulti := markBorrowableFixedCallWindows(fixedMulti, 4, nil)
	if got, borrow := decodeFixedMultiResultCount(markedMulti[0].d, 4); got != 2 || !borrow {
		t.Fatalf("fixed-multi CALL result count = (%d, %t), want (2, true)", got, borrow)
	}
	normalized := normalizeFixedMultiResultCounts(markedMulti, 4)
	if normalized[0].d != 2 {
		t.Fatalf("normalized fixed-multi result count = %d, want 2", normalized[0].d)
	}
	remarked := markBorrowableFixedCallWindows(normalized, 4, nil)
	if remarked[0].d != markedMulti[0].d {
		t.Fatalf("re-finalized marker = %d, want stable %d", remarked[0].d, markedMulti[0].d)
	}
	capturedDestination := analyzeFixedCallBorrowFacts(fixedMulti, 4, []bool{false, true})
	if len(capturedDestination) != 1 || capturedDestination[0].eligible || capturedDestination[0].reason != "result destination is captured" {
		t.Fatalf("captured multi-result fact = %#v, want rejection", capturedDestination)
	}
}