30749432829

Committed 02 Aug 2026 01:12PM UTC coverage: 36.382% (+0.2%) from 36.169%

Build # 30749432829

Build Type

push

github

Committed by

SamboyCoding

Commit Message

Decompiler: Stop having operands be raw `object`-typed

Coverage Stats

2857 of 8963 branches covered (31.88%)

Branch coverage included in aggregate %.

78 of 217 new or added lines in 31 files covered. (35.94%)

7 existing lines in 3 files now uncovered.

5293 of 13438 relevant lines covered (39.39%)

164513.36 hits per line

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

69.06

/Cpp2IL.Core/Analysis/SsaForm.cs

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

namespace Cpp2IL.Core.Analysis;

/// <summary>
/// Converts the control flow graph into and out of minimal SSA form, following the standard
/// Cytron et al. algorithm: phi functions are inserted at the iterated dominance frontiers of
/// each variable's definition sites, and the registers are then renamed (versioned) via a
/// pre-order walk of the dominator tree.
///
/// Variables are <see cref="Register"/>s, identified by <see cref="Register.Number"/>. Version
/// -1 represents the value on entry to the method (parameters / live-in values); real
/// definitions are numbered from 1 upwards.
/// </summary>
public class SsaForm
{
    // Per-register version stack (top = current version in the current dominator-tree path).
    private readonly Dictionary<int, Stack<Register>> _stacks = new();
    // Per-register last-assigned version number.
    private readonly Dictionary<int, int> _counter = new();
    // An unversioned representative register per number, used to build phi nodes and the entry value.
    private readonly Dictionary<int, Register> _repr = new();

    public static void Build(MethodAnalysisContext method)
        => Build(method.ControlFlowGraph!, method.DominatorInfo!);

    public static void Build(ISILControlFlowGraph graph, DominatorInfo dominatorInfo)
    {
        graph.BuildUseDefLists();

        var ssa = new SsaForm();
        ssa.CollectRegisters(graph);
        ssa.InsertPhiFunctions(graph, dominatorInfo);
        ssa.Rename(graph.EntryBlock, dominatorInfo);
    }

    private void CollectRegisters(ISILControlFlowGraph graph)
    {
        foreach (var instruction in graph.Instructions)
            foreach (var register in EnumerateRegisters(instruction))
                if (!_repr.ContainsKey(register.Number))
                    _repr[register.Number] = register.Copy();
    }

    private static IEnumerable<Register> EnumerateRegisters(Instruction instruction)
    {
        foreach (var operand in instruction.Operands)
        {
            if (operand is Register register)
                yield return register;
            else if (operand is MemoryOperand memory)
            {
                if (memory.Base is Register baseRegister)
                    yield return baseRegister;
                if (memory.Index is Register indexRegister)
                    yield return indexRegister;
            }
        }
    }

    private void InsertPhiFunctions(ISILControlFlowGraph graph, DominatorInfo dominance)
    {
        var defSites = GetDefinitionSites(graph);

        foreach (var entry in defSites)
        {
            var regNumber = entry.Key;
            var sites = entry.Value;

            var workList = new Queue<Block>(sites);
            var onWorkList = new HashSet<Block>(sites);
            var hasPhi = new HashSet<Block>();

            while (workList.Count > 0)
            {
                var block = workList.Dequeue();

                if (!dominance.DominanceFrontier.TryGetValue(block, out var frontier))
                    continue;

                foreach (var frontierBlock in frontier)
                {
                    // Only one phi per (block, register).
                    if (!hasPhi.Add(frontierBlock))
                        continue;

                    InsertPhiSkeleton(frontierBlock, regNumber);

                    // Inserting a phi is itself a definition, so propagate to its frontier too.
                    if (onWorkList.Add(frontierBlock))
                        workList.Enqueue(frontierBlock);
                }
            }
        }
    }

    private static Dictionary<int, HashSet<Block>> GetDefinitionSites(ISILControlFlowGraph graph)
    {
        var defSites = new Dictionary<int, HashSet<Block>>();

        foreach (var block in graph.Blocks)
        {
            foreach (var operand in block.Def)
            {
                if (operand is not Register register)
                    continue;

                if (!defSites.TryGetValue(register.Number, out var sites))
                    defSites[register.Number] = sites = [];

                sites.Add(block);
            }
        }

        return defSites;
    }

    /// <summary>
    /// Inserts an unresolved phi node at the top of <paramref name="block"/> with one source slot
    /// per predecessor (positionally aligned to <see cref="Block.Predecessors"/>). The destination
    /// and source placeholders are versioned later during renaming.
    /// </summary>
    private void InsertPhiSkeleton(Block block, int regNumber)
    {
        var register = _repr[regNumber];

        var operands = new List<IOperand>(1 + block.Predecessors.Count) { register }; // destination first
        for (var i = 0; i < block.Predecessors.Count; i++)
            operands.Add(register); // one source per predecessor, filled in during renaming

        block.Instructions.Insert(0, new Instruction(-1, OpCode.Phi, operands));
    }

    private void Rename(Block block, DominatorInfo dominance)
    {
        // Register numbers newly defined in this block, so we can pop their versions on the way out.
        var definedHere = new List<int>();

        foreach (var instruction in block.Instructions)
        {
            // A phi's operands belong to the incoming edges, so they are filled by predecessors;
            // only its destination is renamed here.
            if (instruction.OpCode != OpCode.Phi)
                RewriteUses(instruction);

            if (instruction.Destination is Register definition)
                instruction.Destination = NewName(definition, definedHere);
        }

        // Resolve the phi operands of successors that correspond to this block's outgoing edge.
        foreach (var successor in block.Successors)
        {
            var predIndex = successor.Predecessors.IndexOf(block);
            if (predIndex < 0)
                continue;

            foreach (var phi in successor.Instructions)
            {
                if (phi.OpCode != OpCode.Phi)
                    continue;

                var regNumber = ((Register)phi.Operands[0]).Number;
                phi.SetOperand(1 + predIndex, CurrentVersion(regNumber));
            }
        }

        // Recurse over the dominator tree.
        if (dominance.DominanceTree.TryGetValue(block, out var children))
            foreach (var child in children)
                Rename(child, dominance);

        // Leaving the block: pop the versions it defined.
        foreach (var regNumber in definedHere)
            _stacks[regNumber].Pop();
    }

    private void RewriteUses(Instruction instruction)
    {
        for (var i = 0; i < instruction.Operands.Count; i++)
        {
            var operand = instruction.Operands[i];

            if (operand is Register register)
            {
                instruction.SetOperand(i, CurrentVersion(register.Number));
            }
            else if (operand is MemoryOperand memory)
            {
                if (memory.Base is Register baseRegister)
                    memory.Base = CurrentVersion(baseRegister.Number);
                if (memory.Index is Register indexRegister)
                    memory.Index = CurrentVersion(indexRegister.Number);

                instruction.SetOperand(i, memory); // MemoryOperand is a struct, write the copy back
            }
        }
    }

    /// <summary>
    /// The version of <paramref name="regNumber"/> currently in scope, or the entry value
    /// (version -1) if it has not been defined on the current path.
    /// </summary>
    private Register CurrentVersion(int regNumber)
    {
        if (_stacks.TryGetValue(regNumber, out var stack) && stack.Count > 0)
            return stack.Peek();

        return _repr.TryGetValue(regNumber, out var register) ? register : new Register(regNumber, null);
    }

    private Register NewName(Register register, List<int> definedHere)
    {
        var regNumber = register.Number;

        var version = _counter.TryGetValue(regNumber, out var current) ? current + 1 : 1;
        _counter[regNumber] = version;

        var versioned = register.Copy(version);

        if (!_stacks.TryGetValue(regNumber, out var stack))
            _stacks[regNumber] = stack = new Stack<Register>();

        stack.Push(versioned);
        definedHere.Add(regNumber);

        return versioned;
    }

    /// <summary>
    /// Destroys SSA form by replacing each phi with copies on the incoming edges. For a phi
    /// <c>dest = phi(s0, s1, ...)</c> a <c>Move dest, s[i]</c> is appended (before the terminator)
    /// to the i-th predecessor. Phi operands are positionally aligned to the predecessor list, so
    /// the i-th source belongs to the i-th predecessor.
    /// </summary>
    public static void Remove(MethodAnalysisContext method)
    {
        var cfg = method.ControlFlowGraph!;

        foreach (var block in cfg.Blocks)
        {
            var phiInstructions = block.Instructions
                .Where(i => i.OpCode == OpCode.Phi)
                .ToList();

            if (phiInstructions.Count == 0)
                continue;

            for (var predIndex = 0; predIndex < block.Predecessors.Count; predIndex++)
            {
                var predecessor = block.Predecessors[predIndex];
                var moves = new List<Instruction>();

                foreach (var phi in phiInstructions)
                {
                    if (1 + predIndex >= phi.Operands.Count)
                        continue;

                    var destination = phi.Operands[0];
                    var source = phi.Operands[1 + predIndex];

                    // Skip redundant self-copies.
                    if (Equals(destination, source))
                        continue;

                    moves.Add(new Instruction(-1, OpCode.Move, destination, source));
                }

                InsertBeforeTerminator(predecessor, moves);
            }

            foreach (var phi in phiInstructions)
            {
                phi.OpCode = OpCode.Nop;
                phi.SetOperands();
            }
        }

        cfg.RemoveNops();
        cfg.RemoveEmptyBlocks();
    }

    /// <summary>
    /// Inserts <paramref name="moves"/> at the end of <paramref name="block"/>, but before any
    /// trailing control-flow instruction, so the copies execute on the outgoing edge.
    /// </summary>
    private static void InsertBeforeTerminator(Block block, List<Instruction> moves)
    {
        if (moves.Count == 0)
            return;

        var insertAt = block.Instructions.Count;

        if (insertAt > 0 && !block.Instructions[insertAt - 1].IsFallThrough)
            insertAt--;

        block.Instructions.InsertRange(insertAt, moves);
    }
}

1	using System.Collections.Generic;
2	using System.Linq;
3	using Cpp2IL.Core.Graphs;
4	using Cpp2IL.Core.ISIL;
5	using Cpp2IL.Core.Model.Contexts;
6
7	namespace Cpp2IL.Core.Analysis;
8
9	/// <summary>
10	/// Converts the control flow graph into and out of minimal SSA form, following the standard
11	/// Cytron et al. algorithm: phi functions are inserted at the iterated dominance frontiers of
12	/// each variable's definition sites, and the registers are then renamed (versioned) via a
13	/// pre-order walk of the dominator tree.
14	///
15	/// Variables are <see cref="Register"/>s, identified by <see cref="Register.Number"/>. Version
16	/// -1 represents the value on entry to the method (parameters / live-in values); real
17	/// definitions are numbered from 1 upwards.
18	/// </summary>
19	public class SsaForm
20	{
21	// Per-register version stack (top = current version in the current dominator-tree path).
22	private readonly Dictionary<int, Stack<Register>> _stacks = new();	2✔
23	// Per-register last-assigned version number.
24	private readonly Dictionary<int, int> _counter = new();	2✔
25	// An unversioned representative register per number, used to build phi nodes and the entry value.
26	private readonly Dictionary<int, Register> _repr = new();	2✔
27
28	public static void Build(MethodAnalysisContext method)
29	=> Build(method.ControlFlowGraph!, method.DominatorInfo!);	×
30
31	public static void Build(ISILControlFlowGraph graph, DominatorInfo dominatorInfo)
32	{
33	graph.BuildUseDefLists();	2✔
34
35	var ssa = new SsaForm();	2✔
36	ssa.CollectRegisters(graph);	2✔
37	ssa.InsertPhiFunctions(graph, dominatorInfo);	2✔
38	ssa.Rename(graph.EntryBlock, dominatorInfo);	2✔
39	}	2✔
40
41	private void CollectRegisters(ISILControlFlowGraph graph)
42	{
43	foreach (var instruction in graph.Instructions)	34✔
44	foreach (var register in EnumerateRegisters(instruction))	60✔
45	if (!_repr.ContainsKey(register.Number))	15✔
46	_repr[register.Number] = register.Copy();	5✔
47	}	2✔
48
49	private static IEnumerable<Register> EnumerateRegisters(Instruction instruction)
50	{
51	foreach (var operand in instruction.Operands)	82✔
52	{
53	if (operand is Register register)	26✔
54	yield return register;	15✔
55	else if (operand is MemoryOperand memory)	11!
56	{
57	if (memory.Base is Register baseRegister)	×
58	yield return baseRegister;	×
59	if (memory.Index is Register indexRegister)	×
60	yield return indexRegister;	×
61	}
62	}
63	}	15✔
64
65	private void InsertPhiFunctions(ISILControlFlowGraph graph, DominatorInfo dominance)
66	{
67	var defSites = GetDefinitionSites(graph);	2✔
68
69	foreach (var entry in defSites)	12✔
70	{
71	var regNumber = entry.Key;	4✔
72	var sites = entry.Value;	4✔
73
74	var workList = new Queue<Block>(sites);	4✔
75	var onWorkList = new HashSet<Block>(sites);	4✔
76	var hasPhi = new HashSet<Block>();	4✔
77
78	while (workList.Count > 0)	13✔
79	{
80	var block = workList.Dequeue();	9✔
81
82	if (!dominance.DominanceFrontier.TryGetValue(block, out var frontier))	9✔
83	continue;
84
85	foreach (var frontierBlock in frontier)	28✔
86	{
87	// Only one phi per (block, register).
88	if (!hasPhi.Add(frontierBlock))	5✔
89	continue;
90
91	InsertPhiSkeleton(frontierBlock, regNumber);	3✔
92
93	// Inserting a phi is itself a definition, so propagate to its frontier too.
94	if (onWorkList.Add(frontierBlock))	3✔
95	workList.Enqueue(frontierBlock);	2✔
96	}
97	}
98	}
99	}	2✔
100
101	private static Dictionary<int, HashSet<Block>> GetDefinitionSites(ISILControlFlowGraph graph)
102	{
103	var defSites = new Dictionary<int, HashSet<Block>>();	2✔
104
105	foreach (var block in graph.Blocks)	30✔
106	{
107	foreach (var operand in block.Def)	40✔
108	{
109	if (operand is not Register register)	7✔
110	continue;
111
112	if (!defSites.TryGetValue(register.Number, out var sites))	7✔
113	defSites[register.Number] = sites = [];	4✔
114
115	sites.Add(block);	7✔
116	}
117	}
118
119	return defSites;	2✔
120	}
121
122	/// <summary>
123	/// Inserts an unresolved phi node at the top of <paramref name="block"/> with one source slot
124	/// per predecessor (positionally aligned to <see cref="Block.Predecessors"/>). The destination
125	/// and source placeholders are versioned later during renaming.
126	/// </summary>
127	private void InsertPhiSkeleton(Block block, int regNumber)
128	{
129	var register = _repr[regNumber];	3✔
130
131	var operands = new List<IOperand>(1 + block.Predecessors.Count) { register }; // destination first	3✔
132	for (var i = 0; i < block.Predecessors.Count; i++)	18✔
133	operands.Add(register); // one source per predecessor, filled in during renaming	6✔
134
135	block.Instructions.Insert(0, new Instruction(-1, OpCode.Phi, operands));	3✔
136	}	3✔
137
138	private void Rename(Block block, DominatorInfo dominance)
139	{
140	// Register numbers newly defined in this block, so we can pop their versions on the way out.
141	var definedHere = new List<int>();	13✔
142
143	foreach (var instruction in block.Instructions)	62✔
144	{
145	// A phi's operands belong to the incoming edges, so they are filled by predecessors;
146	// only its destination is renamed here.
147	if (instruction.OpCode != OpCode.Phi)	18✔
148	RewriteUses(instruction);	15✔
149
150	if (instruction.Destination is Register definition)	18✔
151	instruction.Destination = NewName(definition, definedHere);	11✔
152	}
153
154	// Resolve the phi operands of successors that correspond to this block's outgoing edge.
155	foreach (var successor in block.Successors)	52✔
156	{
157	var predIndex = successor.Predecessors.IndexOf(block);	13✔
158	if (predIndex < 0)	13✔
159	continue;
160
161	foreach (var phi in successor.Instructions)	78✔
162	{
163	if (phi.OpCode != OpCode.Phi)	26✔
164	continue;
165
166	var regNumber = ((Register)phi.Operands[0]).Number;	6✔
167	phi.SetOperand(1 + predIndex, CurrentVersion(regNumber));	6✔
168	}
169	}
170
171	// Recurse over the dominator tree.
172	if (dominance.DominanceTree.TryGetValue(block, out var children))	13✔
173	foreach (var child in children)	38✔
174	Rename(child, dominance);	11✔
175
176	// Leaving the block: pop the versions it defined.
177	foreach (var regNumber in definedHere)	48✔
178	_stacks[regNumber].Pop();	11✔
179	}	13✔
180
181	private void RewriteUses(Instruction instruction)
182	{
183	for (var i = 0; i < instruction.Operands.Count; i++)	82✔
184	{
185	var operand = instruction.Operands[i];	26✔
186
187	if (operand is Register register)	26✔
188	{
189	instruction.SetOperand(i, CurrentVersion(register.Number));	15✔
190	}
191	else if (operand is MemoryOperand memory)	11!
192	{
193	if (memory.Base is Register baseRegister)	×
194	memory.Base = CurrentVersion(baseRegister.Number);	×
195	if (memory.Index is Register indexRegister)	×
196	memory.Index = CurrentVersion(indexRegister.Number);	×
197
198	instruction.SetOperand(i, memory); // MemoryOperand is a struct, write the copy back	×
199	}
200	}
201	}	15✔
202
203	/// <summary>
204	/// The version of <paramref name="regNumber"/> currently in scope, or the entry value
205	/// (version -1) if it has not been defined on the current path.
206	/// </summary>
207	private Register CurrentVersion(int regNumber)
208	{
209	if (_stacks.TryGetValue(regNumber, out var stack) && stack.Count > 0)	21✔
210	return stack.Peek();	16✔
211
212	return _repr.TryGetValue(regNumber, out var register) ? register : new Register(regNumber, null);	5!
213	}
214
215	private Register NewName(Register register, List<int> definedHere)
216	{
217	var regNumber = register.Number;	11✔
218
219	var version = _counter.TryGetValue(regNumber, out var current) ? current + 1 : 1;	11✔
220	_counter[regNumber] = version;	11✔
221
222	var versioned = register.Copy(version);	11✔
223
224	if (!_stacks.TryGetValue(regNumber, out var stack))	11✔
225	_stacks[regNumber] = stack = new Stack<Register>();	4✔
226
227	stack.Push(versioned);	11✔
228	definedHere.Add(regNumber);	11✔
229
230	return versioned;	11✔
231	}
232
233	/// <summary>
234	/// Destroys SSA form by replacing each phi with copies on the incoming edges. For a phi
235	/// <c>dest = phi(s0, s1, ...)</c> a <c>Move dest, s[i]</c> is appended (before the terminator)
236	/// to the i-th predecessor. Phi operands are positionally aligned to the predecessor list, so
237	/// the i-th source belongs to the i-th predecessor.
238	/// </summary>
239	public static void Remove(MethodAnalysisContext method)
240	{
241	var cfg = method.ControlFlowGraph!;	×
242
243	foreach (var block in cfg.Blocks)	×
244	{
245	var phiInstructions = block.Instructions	×
246	.Where(i => i.OpCode == OpCode.Phi)	×
247	.ToList();	×
248
249	if (phiInstructions.Count == 0)	×
250	continue;
251
252	for (var predIndex = 0; predIndex < block.Predecessors.Count; predIndex++)	×
253	{
254	var predecessor = block.Predecessors[predIndex];	×
255	var moves = new List<Instruction>();	×
256
257	foreach (var phi in phiInstructions)	×
258	{
259	if (1 + predIndex >= phi.Operands.Count)	×
260	continue;
261
262	var destination = phi.Operands[0];	×
263	var source = phi.Operands[1 + predIndex];	×
264
265	// Skip redundant self-copies.
266	if (Equals(destination, source))	×
267	continue;
268
269	moves.Add(new Instruction(-1, OpCode.Move, destination, source));	×
270	}
271
272	InsertBeforeTerminator(predecessor, moves);	×
273	}
274
275	foreach (var phi in phiInstructions)	×
276	{
277	phi.OpCode = OpCode.Nop;	×
NEW 278	phi.SetOperands();	×
279	}
280	}
281
282	cfg.RemoveNops();	×
283	cfg.RemoveEmptyBlocks();	×
284	}	×
285
286	/// <summary>
287	/// Inserts <paramref name="moves"/> at the end of <paramref name="block"/>, but before any
288	/// trailing control-flow instruction, so the copies execute on the outgoing edge.
289	/// </summary>
290	private static void InsertBeforeTerminator(Block block, List<Instruction> moves)
291	{
292	if (moves.Count == 0)	×
293	return;	×
294
295	var insertAt = block.Instructions.Count;	×
296
297	if (insertAt > 0 && !block.Instructions[insertAt - 1].IsFallThrough)	×
298	insertAt--;	×
299
300	block.Instructions.InsertRange(insertAt, moves);	×
301	}	×
302	}

SamboyCoding / Cpp2IL / 30749432829

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