30161747008

Committed 25 Jul 2026 02:30PM UTC coverage: 37.69% (-0.02%) from 37.713%

Build # 30161747008

Build Type

Pull #588

github

Committed by

web-flow

Commit Message

Merge 95b161421 into d1cd6d97e

Pull Request Pull Request #588: StackAnalyzer fixes

Coverage Stats

2907 of 8656 branches covered (33.58%)

Branch coverage included in aggregate %.

0 of 33 new or added lines in 2 files covered. (0.0%)

2 existing lines in 1 file now uncovered.

5311 of 13148 relevant lines covered (40.39%)

175388.88 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 = 2000;

    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.Operands = [];
                    continue;
                }

                int? state = null;

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

                    if (op is StackOffset 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 = state.Value + offset.Offset;
                        instruction.Operands[i] = new StackOffset(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)instruction.Operands[0];
                    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! ({MaxBlockVisitCount} 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)
                {
                    var name = offset.Offset < 0 ? $"stack_-{-offset.Offset:X}" : $"stack_{offset.Offset:X}";
                    instruction.Operands[i] = new Register(null, name);
                }
            }
        }

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

            if (parameter is StackOffset offset)
            {
                var name = offset.Offset < 0 ? $"stack_-{-offset.Offset:X}" : $"stack_{offset.Offset:X}";
                method.ParameterOperands[i] = new Register(null, name);
            }
        }
    }
}

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>
25	public static int MaxBlockVisitCount = 2000;	×
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.Operands = [];	×
NEW 64	continue;	×
65	}
66
NEW 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	if (op is StackOffset offset)	×
75	{
76	// This can only be done before modifying any of the instruction operands,
77	// as doing so will make the dictionary lookup impossible.
NEW 78	state ??= _instructionState[instruction].Size;	×
79
NEW 80	var actual = state.Value + offset.Offset;	×
UNCOV 81	instruction.Operands[i] = new StackOffset(actual);	×
82	}
83	}
84	}
85	}
86	}	×
87
88	// Traverse the graph and calculate the stack state for each block and instruction
89	private void TraverseGraph(Block initialBlock, int initialVisitedBlockCount = 0)
90	{
NEW 91	var blockLevelState = new Stack<(Block, int)>();	×
NEW 92	blockLevelState.Push((initialBlock, initialVisitedBlockCount));	×
93
NEW 94	while (blockLevelState.Count > 0)	×
95	{
NEW 96	var (block, visitedBlockCount) = blockLevelState.Pop();	×
97
98	// Copy current state
NEW 99	var incomingState = _inComingState[block];	×
NEW 100	var currentState = incomingState.Copy();	×
101
102	// Process instructions
NEW 103	foreach (var instruction in block.Instructions)	×
104	{
NEW 105	_instructionState[instruction] = currentState;	×
106
NEW 107	if (instruction.OpCode == OpCode.ShiftStack)	×
108	{
NEW 109	var offset = (int)instruction.Operands[0];	×
NEW 110	currentState = currentState.Copy();	×
NEW 111	currentState.Size += offset;	×
112	}
NEW 113	else if (block.Instructions[^1] == instruction && block.BlockType == BlockType.TailCall)	×
114	{
115	// Tail calls clear stack
NEW 116	currentState = currentState.Copy();	×
NEW 117	currentState.Size = 0;	×
118	}
119	}
120
121	// Tail calls clear stack
NEW 122	if (block.BlockType == BlockType.TailCall)	×
NEW 123	currentState.Size = 0;	×
124
NEW 125	_outGoingState[block] = currentState;	×
126
NEW 127	visitedBlockCount++;	×
128
NEW 129	if (MaxBlockVisitCount != -1 && visitedBlockCount > MaxBlockVisitCount)	×
NEW 130	throw new DecompilerException($"Stack state not settling! ({MaxBlockVisitCount} blocks already visited)");	×
131
132	// Visit successors
NEW 133	foreach (var successor in block.Successors)	×
134	{
135	// Already visited
NEW 136	if (_inComingState.TryGetValue(successor, out var existingState))	×
137	{
NEW 138	if (existingState.Size != currentState.Size)	×
139	{
NEW 140	_inComingState[successor] = currentState.Copy();	×
NEW 141	blockLevelState.Push((successor, visitedBlockCount + 1));	×
142	}
143	}
144	else
145	{
146	// Set incoming delta and add to queue
147	_inComingState[successor] = currentState.Copy();	×
NEW 148	blockLevelState.Push((successor, visitedBlockCount + 1));	×
149	}
150	}
151	}
UNCOV 152	}	×
153
154	private static void ReplaceStackWithRegisters(MethodAnalysisContext method)
155	{
156	var instructions = method.ControlFlowGraph!.Instructions;	×
157
158	// Replace stack offset operands
159	foreach (var instruction in instructions)	×
160	{
161	for (var i = 0; i < instruction.Operands.Count; i++)	×
162	{
163	var operand = instruction.Operands[i];	×
164
165	if (operand is StackOffset offset)	×
166	{
167	var name = offset.Offset < 0 ? $"stack_-{-offset.Offset:X}" : $"stack_{offset.Offset:X}";	×
168	instruction.Operands[i] = new Register(null, name);	×
169	}
170	}
171	}
172
173	// Replace params
174	for (var i = 0; i < method.ParameterOperands.Count; i++)	×
175	{
176	var parameter = method.ParameterOperands[i];	×
177
178	if (parameter is StackOffset offset)	×
179	{
180	var name = offset.Offset < 0 ? $"stack_-{-offset.Offset:X}" : $"stack_{offset.Offset:X}";	×
181	method.ParameterOperands[i] = new Register(null, name);	×
182	}
183	}
184	}	×
185	}

SamboyCoding / Cpp2IL / 30161747008

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