30815301374

Committed 03 Aug 2026 12:51PM UTC coverage: 34.341% (+0.001%) from 34.34%

Build # 30815301374

Build Type

push

github

Committed by

SamboyCoding

Commit Message

Decompiler: Fix incorrect handling of `jmp <reg>` causing stack to never settle

Coverage Stats

2923 of 9954 branches covered (29.37%)

Branch coverage included in aggregate %.

1 of 8 new or added lines in 4 files covered. (12.5%)

5355 of 14151 relevant lines covered (37.84%)

156224.46 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

0.0

/Cpp2IL.Core/Analysis/StackAnalyzer.cs

using System.Collections.Generic;
using System.Diagnostics;
using Cpp2IL.Core.Graphs;
using Cpp2IL.Core.ISIL;
using Cpp2IL.Core.Model.Contexts;

namespace Cpp2IL.Core.Analysis;

public class StackAnalyzer
{
    [DebuggerDisplay("Size = {Size}")]
    private class StackState
    {
        public int Size;
        public StackState Copy() => new() { Size = this.Size };
    }

    private Dictionary<Block, StackState> _inComingState = [];
    private Dictionary<Block, StackState> _outGoingState = [];
    private Dictionary<Instruction, StackState> _instructionState = [];

    /// <summary>
    /// Max allowed count of blocks to visit (-1 for no limit).
    /// </summary>
    public static int MaxBlockVisitCount = 500000; //High enough to not be legitimately hit, but still give up if something loops infinitely.

    public static void Analyze(MethodAnalysisContext method)
    {
        var analyzer = new StackAnalyzer();

        var graph = method.ControlFlowGraph!;
        graph.RemoveUnreachableBlocks(); // Without this indirect jumps (in try catch i think) cause some weird stuff

        analyzer._inComingState = new Dictionary<Block, StackState> { { graph.EntryBlock, new StackState() } };

        analyzer.TraverseGraph(graph.EntryBlock);

        // The exit block has no outgoing state if it was never reached (e.g. every path loops or
        // throws). That's fine - just skip the end-of-method stack balance check in that case.
        if (analyzer._outGoingState.TryGetValue(graph.ExitBlock, out var outDelta) && outDelta.Size != 0)
        {
            var outText = outDelta.Size < 0 ? "-" + (-outDelta.Size).ToString("X") : outDelta.Size.ToString("X");
            method.AddWarning($"Method ends with non empty stack ({outText}), the output could be wrong!");
        }

        analyzer.CorrectOffsets(graph);
        ReplaceStackWithRegisters(method);

        graph.RemoveNops();
        graph.RemoveEmptyBlocks();
    }

    private void CorrectOffsets(ISILControlFlowGraph graph)
    {
        foreach (var block in graph.Blocks)
        {
            foreach (var instruction in block.Instructions)
            {
                if (instruction is { OpCode: OpCode.ShiftStack })
                {
                    // Nop the shift stack instruction
                    instruction.OpCode = OpCode.Nop;
                    instruction.SetOperands();
                    continue;
                }

                int? state = null;

                // Correct offset for stack operands.
                for (var i = 0; i < instruction.Operands.Count; i++)
                {
                    var op = instruction.Operands[i];

                    var slot = op switch
                    {
                        StackOffset direct => direct,
                        AddressOf { Target: StackOffset addressed } => addressed,
                        _ => (StackOffset?)null
                    };

                    if (slot is { } offset)
                    {
                        // This can only be done before modifying any of the instruction operands,
                        // as doing so will make the dictionary lookup impossible.
                        state ??= _instructionState[instruction].Size;

                        var actual = new StackOffset(state.Value + offset.Offset);
                        instruction.SetOperand(i, op is AddressOf ? new AddressOf(actual) : actual);
                    }
                }
            }
        }
    }

    // Traverse the graph and calculate the stack state for each block and instruction
    private void TraverseGraph(Block initialBlock, int initialVisitedBlockCount = 0)
    {
        var blockLevelState = new Stack<(Block, int)>();
        blockLevelState.Push((initialBlock, initialVisitedBlockCount));

        while (blockLevelState.Count > 0)
        {
            var (block, visitedBlockCount) = blockLevelState.Pop();

            // Copy current state
            var incomingState = _inComingState[block];
            var currentState = incomingState.Copy();

            // Process instructions
            foreach (var instruction in block.Instructions)
            {
                _instructionState[instruction] = currentState;

                if (instruction.OpCode == OpCode.ShiftStack)
                {
                    var offset = (int)((Immediate)instruction.Operands[0]).Value;
                    currentState = currentState.Copy();
                    currentState.Size += offset;
                }
                else if (block.Instructions[^1] == instruction && block.BlockType == BlockType.TailCall)
                {
                    // Tail calls clear stack
                    currentState = currentState.Copy();
                    currentState.Size = 0;
                }
            }

            // Tail calls clear stack
            if (block.BlockType == BlockType.TailCall)
                currentState.Size = 0;

            _outGoingState[block] = currentState;

            visitedBlockCount++;

            if (MaxBlockVisitCount != -1 && visitedBlockCount > MaxBlockVisitCount)
                throw new DecompilerException($"Stack state not settling! ({visitedBlockCount} blocks already visited)");

            // Visit successors
            foreach (var successor in block.Successors)
            {
                // Already visited
                if (_inComingState.TryGetValue(successor, out var existingState))
                {
                    if (existingState.Size != currentState.Size)
                    {
                        _inComingState[successor] = currentState.Copy();
                        blockLevelState.Push((successor, visitedBlockCount + 1));
                    }
                }
                else
                {
                    // Set incoming delta and add to queue
                    _inComingState[successor] = currentState.Copy();
                    blockLevelState.Push((successor, visitedBlockCount + 1));
                }
            }
        }
    }

    private static void ReplaceStackWithRegisters(MethodAnalysisContext method)
    {
        var instructions = method.ControlFlowGraph!.Instructions;

        // Replace stack offset operands
        foreach (var instruction in instructions)
        {
            for (var i = 0; i < instruction.Operands.Count; i++)
            {
                var operand = instruction.Operands[i];

                if (operand is StackOffset offset)
                    instruction.SetOperand(i, new Register(null, NameForSlot(offset)));

                if (operand is AddressOf { Target: StackOffset addressed })
                    instruction.SetOperand(i, new AddressOf(new Register(null, NameForSlot(addressed))));
            }
        }

        // Replace params
        for (var i = 0; i < method.ParameterOperands.Count; i++)
        {
            var parameter = method.ParameterOperands[i];

            if (parameter is StackOffset offset)
                method.ParameterOperands[i] = new Register(null, NameForSlot(offset));
        }
    }

    private static string NameForSlot(StackOffset offset) => offset.Offset < 0 ? $"stack_-{-offset.Offset:X}" : $"stack_{offset.Offset:X}";
}

1	using System.Collections.Generic;
2	using System.Diagnostics;
3	using Cpp2IL.Core.Graphs;
4	using Cpp2IL.Core.ISIL;
5	using Cpp2IL.Core.Model.Contexts;
6
7	namespace Cpp2IL.Core.Analysis;
8
9	public class StackAnalyzer
10	{
11	[DebuggerDisplay("Size = {Size}")]
12	private class StackState
13	{
14	public int Size;
15	public StackState Copy() => new() { Size = this.Size };	×
16	}
17
18	private Dictionary<Block, StackState> _inComingState = [];	×
19	private Dictionary<Block, StackState> _outGoingState = [];	×
20	private Dictionary<Instruction, StackState> _instructionState = [];	×
21
22	/// <summary>
23	/// Max allowed count of blocks to visit (-1 for no limit).
24	/// </summary>
NEW 25	public static int MaxBlockVisitCount = 500000; //High enough to not be legitimately hit, but still give up if something loops infinitely.	×
26
27	public static void Analyze(MethodAnalysisContext method)
28	{
29	var analyzer = new StackAnalyzer();	×
30
31	var graph = method.ControlFlowGraph!;	×
32	graph.RemoveUnreachableBlocks(); // Without this indirect jumps (in try catch i think) cause some weird stuff	×
33
34	analyzer._inComingState = new Dictionary<Block, StackState> { { graph.EntryBlock, new StackState() } };	×
35
36	analyzer.TraverseGraph(graph.EntryBlock);	×
37
38	// The exit block has no outgoing state if it was never reached (e.g. every path loops or
39	// throws). That's fine - just skip the end-of-method stack balance check in that case.
40	if (analyzer._outGoingState.TryGetValue(graph.ExitBlock, out var outDelta) && outDelta.Size != 0)	×
41	{
42	var outText = outDelta.Size < 0 ? "-" + (-outDelta.Size).ToString("X") : outDelta.Size.ToString("X");	×
43	method.AddWarning($"Method ends with non empty stack ({outText}), the output could be wrong!");	×
44	}
45
46	analyzer.CorrectOffsets(graph);	×
47	ReplaceStackWithRegisters(method);	×
48
49	graph.RemoveNops();	×
50	graph.RemoveEmptyBlocks();	×
51	}	×
52
53	private void CorrectOffsets(ISILControlFlowGraph graph)
54	{
55	foreach (var block in graph.Blocks)	×
56	{
57	foreach (var instruction in block.Instructions)	×
58	{
59	if (instruction is { OpCode: OpCode.ShiftStack })	×
60	{
61	// Nop the shift stack instruction
62	instruction.OpCode = OpCode.Nop;	×
63	instruction.SetOperands();	×
64	continue;	×
65	}
66
67	int? state = null;	×
68
69	// Correct offset for stack operands.
70	for (var i = 0; i < instruction.Operands.Count; i++)	×
71	{
72	var op = instruction.Operands[i];	×
73
74	var slot = op switch	×
75	{	×
76	StackOffset direct => direct,	×
77	AddressOf { Target: StackOffset addressed } => addressed,	×
78	_ => (StackOffset?)null	×
79	};	×
80
81	if (slot is { } offset)	×
82	{
83	// This can only be done before modifying any of the instruction operands,
84	// as doing so will make the dictionary lookup impossible.
85	state ??= _instructionState[instruction].Size;	×
86
87	var actual = new StackOffset(state.Value + offset.Offset);	×
88	instruction.SetOperand(i, op is AddressOf ? new AddressOf(actual) : actual);	×
89	}
90	}
91	}
92	}
93	}	×
94
95	// Traverse the graph and calculate the stack state for each block and instruction
96	private void TraverseGraph(Block initialBlock, int initialVisitedBlockCount = 0)
97	{
98	var blockLevelState = new Stack<(Block, int)>();	×
99	blockLevelState.Push((initialBlock, initialVisitedBlockCount));	×
100
101	while (blockLevelState.Count > 0)	×
102	{
103	var (block, visitedBlockCount) = blockLevelState.Pop();	×
104
105	// Copy current state
106	var incomingState = _inComingState[block];	×
107	var currentState = incomingState.Copy();	×
108
109	// Process instructions
110	foreach (var instruction in block.Instructions)	×
111	{
112	_instructionState[instruction] = currentState;	×
113
114	if (instruction.OpCode == OpCode.ShiftStack)	×
115	{
116	var offset = (int)((Immediate)instruction.Operands[0]).Value;	×
117	currentState = currentState.Copy();	×
118	currentState.Size += offset;	×
119	}
120	else if (block.Instructions[^1] == instruction && block.BlockType == BlockType.TailCall)	×
121	{
122	// Tail calls clear stack
123	currentState = currentState.Copy();	×
124	currentState.Size = 0;	×
125	}
126	}
127
128	// Tail calls clear stack
129	if (block.BlockType == BlockType.TailCall)	×
130	currentState.Size = 0;	×
131
132	_outGoingState[block] = currentState;	×
133
134	visitedBlockCount++;	×
135
136	if (MaxBlockVisitCount != -1 && visitedBlockCount > MaxBlockVisitCount)	×
NEW 137	throw new DecompilerException($"Stack state not settling! ({visitedBlockCount} blocks already visited)");	×
138
139	// Visit successors
140	foreach (var successor in block.Successors)	×
141	{
142	// Already visited
143	if (_inComingState.TryGetValue(successor, out var existingState))	×
144	{
145	if (existingState.Size != currentState.Size)	×
146	{
147	_inComingState[successor] = currentState.Copy();	×
148	blockLevelState.Push((successor, visitedBlockCount + 1));	×
149	}
150	}
151	else
152	{
153	// Set incoming delta and add to queue
154	_inComingState[successor] = currentState.Copy();	×
155	blockLevelState.Push((successor, visitedBlockCount + 1));	×
156	}
157	}
158	}
159	}	×
160
161	private static void ReplaceStackWithRegisters(MethodAnalysisContext method)
162	{
163	var instructions = method.ControlFlowGraph!.Instructions;	×
164
165	// Replace stack offset operands
166	foreach (var instruction in instructions)	×
167	{
168	for (var i = 0; i < instruction.Operands.Count; i++)	×
169	{
170	var operand = instruction.Operands[i];	×
171
172	if (operand is StackOffset offset)	×
173	instruction.SetOperand(i, new Register(null, NameForSlot(offset)));	×
174
175	if (operand is AddressOf { Target: StackOffset addressed })	×
176	instruction.SetOperand(i, new AddressOf(new Register(null, NameForSlot(addressed))));	×
177	}
178	}
179
180	// Replace params
181	for (var i = 0; i < method.ParameterOperands.Count; i++)	×
182	{
183	var parameter = method.ParameterOperands[i];	×
184
185	if (parameter is StackOffset offset)	×
186	method.ParameterOperands[i] = new Register(null, NameForSlot(offset));	×
187	}
188	}	×
189
190	private static string NameForSlot(StackOffset offset) => offset.Offset < 0 ? $"stack_-{-offset.Offset:X}" : $"stack_{offset.Offset:X}";	×
191	}

SamboyCoding / Cpp2IL / 30815301374

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous