30815175474

Committed 03 Aug 2026 12:49PM UTC coverage: 34.34% (+0.05%) from 34.288%

Build # 30815175474

Build Type

push

github

Committed by

web-flow

Commit Message

More analysis performance improvements (#595)

* make ThrowHelperNamesByAddress thread safe

* check if we actually have to reset sources in ResetSources

* SsaForm: make Rename iterative

* CopyCoalescer: only process potentially changed blocks in ComputeBlockLiveOut

Coverage Stats

2921 of 9952 branches covered (29.35%)

Branch coverage included in aggregate %.

29 of 50 new or added lines in 4 files covered. (58.0%)

5355 of 14148 relevant lines covered (37.85%)

156257.58 hits per line

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

54.18

/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)
    {
        var ssa = new SsaForm();
        ssa.FindClobberingAddressTakes(graph);

        graph.BuildUseDefLists(ssa._clobbering);

        ssa.CollectRegisters(graph);
        ssa.InsertPhiFunctions(graph, dominatorInfo);
        ssa.Rename(graph.EntryBlock, dominatorInfo);
    }

    // The address-takes whose slot is read again afterwards, and so have to be treated as definitions.
    private readonly HashSet<Instruction> _clobbering = [];

    private void FindClobberingAddressTakes(ISILControlFlowGraph graph)
    {
        foreach (var block in graph.Blocks)
        {
            for (var i = 0; i < block.Instructions.Count; i++)
            {
                var instruction = block.Instructions[i];

                foreach (var operand in instruction.Operands)
                {
                    if (operand is AddressOf { Target: Register addressed } && IsReadAfter(block, i, addressed))
                        _clobbering.Add(instruction);
                }
            }
        }
    }

    private static bool IsReadAfter(Block block, int index, Register register)
    {
        if (ScanForRead(block, index + 1, register, out var continuePastBlock))
            return true;

        if (!continuePastBlock)
            return false;

        var visited = new HashSet<Block>();
        var queue = new Queue<Block>(block.Successors);

        while (queue.Count > 0)
        {
            var reachable = queue.Dequeue();

            if (!visited.Add(reachable))
                continue;

            if (ScanForRead(reachable, 0, register, out var keepGoing))
                return true;

            if (!keepGoing)
                continue;

            foreach (var successor in reachable.Successors)
                queue.Enqueue(successor);
        }

        return false;
    }

    // Scans a block from an index. Reports whether the register is read, and whether the paths beyond
    // this block are still worth following (they aren't once something has reassigned it).
    private static bool ScanForRead(Block block, int from, Register register, out bool continuePastBlock)
    {
        continuePastBlock = true;

        for (var i = from; i < block.Instructions.Count; i++)
        {
            var instruction = block.Instructions[i];

            if (Reads(instruction, register))
                return true;

            if (instruction.Destination is Register defined && defined.Number == register.Number)
            {
                continuePastBlock = false;
                return false;
            }
        }

        return false;
    }

    // A plain read of the register's value. The address-takes themselves don't count.
    private static bool Reads(Instruction instruction, Register register)
    {
        for (var i = 0; i < instruction.Operands.Count; i++)
        {
            if (i == 0 && instruction.Destination is Register)
                continue;

            var reads = instruction.Operands[i] switch
            {
                Register other => other.Number == register.Number,
                MemoryOperand memory => (memory.Base as Register?)?.Number == register.Number
                    || (memory.Index as Register?)?.Number == register.Number,
                _ => false
            };

            if (reads)
                return true;
        }

        return false;
    }

    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 AddressOf { Target: Register addressed })
                yield return addressed;
            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 initialBlock, DominatorInfo dominance)
    {
        var remaining = new Stack<(Stack<Block>, List<int>)>();
        remaining.Push((new Stack<Block>([initialBlock]), []));

        while (remaining.Count > 0)
        {
            var (blocks, parentDefinedRegisters) = remaining.Pop();
            if (blocks.Count == 0)
            {
                // Leaving the block: pop the versions it defined.
                foreach (var regNumber in parentDefinedRegisters)
                    _stacks[regNumber].Pop();

                continue;
            }

            var block = blocks.Pop();
            remaining.Push((blocks, parentDefinedRegisters));

            // 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);

                for (var i = 0; i < instruction.Operands.Count; i++)
                {
                    // Taking a slot's address lets the callee assign it, so the slot stops holding anything that reached this point, UNLESS
                    // nothing reads it afterwards, in which case any write is unobservable and the callee is only reading the value it has now
                    if (instruction.Operands[i] is AddressOf { Target: Register addressed })
                        instruction.SetOperand(i, new AddressOf(_clobbering.Contains(instruction)
                            ? NewName(addressed, definedHere)
                            : CurrentVersion(addressed.Number)));
                }
            }

            // 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))
            {
                remaining.Push((new Stack<Block>(children), definedHere));
            }
        }
    }

    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	var ssa = new SsaForm();	2✔
34	ssa.FindClobberingAddressTakes(graph);	2✔
35
36	graph.BuildUseDefLists(ssa._clobbering);	2✔
37
38	ssa.CollectRegisters(graph);	2✔
39	ssa.InsertPhiFunctions(graph, dominatorInfo);	2✔
40	ssa.Rename(graph.EntryBlock, dominatorInfo);	2✔
41	}	2✔
42
43	// The address-takes whose slot is read again afterwards, and so have to be treated as definitions.
44	private readonly HashSet<Instruction> _clobbering = [];	2✔
45
46	private void FindClobberingAddressTakes(ISILControlFlowGraph graph)
47	{
48	foreach (var block in graph.Blocks)	30✔
49	{
50	for (var i = 0; i < block.Instructions.Count; i++)	56✔
51	{
52	var instruction = block.Instructions[i];	15✔
53
54	foreach (var operand in instruction.Operands)	82✔
55	{
56	if (operand is AddressOf { Target: Register addressed } && IsReadAfter(block, i, addressed))	26!
57	_clobbering.Add(instruction);	×
58	}
59	}
60	}
61	}	2✔
62
63	private static bool IsReadAfter(Block block, int index, Register register)
64	{
65	if (ScanForRead(block, index + 1, register, out var continuePastBlock))	×
66	return true;	×
67
68	if (!continuePastBlock)	×
69	return false;	×
70
71	var visited = new HashSet<Block>();	×
72	var queue = new Queue<Block>(block.Successors);	×
73
74	while (queue.Count > 0)	×
75	{
76	var reachable = queue.Dequeue();	×
77
78	if (!visited.Add(reachable))	×
79	continue;
80
81	if (ScanForRead(reachable, 0, register, out var keepGoing))	×
82	return true;	×
83
84	if (!keepGoing)	×
85	continue;
86
87	foreach (var successor in reachable.Successors)	×
88	queue.Enqueue(successor);	×
89	}
90
91	return false;	×
92	}
93
94	// Scans a block from an index. Reports whether the register is read, and whether the paths beyond
95	// this block are still worth following (they aren't once something has reassigned it).
96	private static bool ScanForRead(Block block, int from, Register register, out bool continuePastBlock)
97	{
98	continuePastBlock = true;	×
99
100	for (var i = from; i < block.Instructions.Count; i++)	×
101	{
102	var instruction = block.Instructions[i];	×
103
104	if (Reads(instruction, register))	×
105	return true;	×
106
107	if (instruction.Destination is Register defined && defined.Number == register.Number)	×
108	{
109	continuePastBlock = false;	×
110	return false;	×
111	}
112	}
113
114	return false;	×
115	}
116
117	// A plain read of the register's value. The address-takes themselves don't count.
118	private static bool Reads(Instruction instruction, Register register)
119	{
120	for (var i = 0; i < instruction.Operands.Count; i++)	×
121	{
122	if (i == 0 && instruction.Destination is Register)	×
123	continue;
124
125	var reads = instruction.Operands[i] switch	×
126	{	×
127	Register other => other.Number == register.Number,	×
128	MemoryOperand memory => (memory.Base as Register?)?.Number == register.Number	×
129	\|\| (memory.Index as Register?)?.Number == register.Number,	×
130	_ => false	×
131	};	×
132
133	if (reads)	×
134	return true;	×
135	}
136
137	return false;	×
138	}
139
140	private void CollectRegisters(ISILControlFlowGraph graph)
141	{
142	foreach (var instruction in graph.Instructions)	34✔
143	foreach (var register in EnumerateRegisters(instruction))	60✔
144	if (!_repr.ContainsKey(register.Number))	15✔
145	_repr[register.Number] = register.Copy();	5✔
146	}	2✔
147
148	private static IEnumerable<Register> EnumerateRegisters(Instruction instruction)
149	{
150	foreach (var operand in instruction.Operands)	82✔
151	{
152	if (operand is Register register)	26✔
153	yield return register;	15✔
154	else if (operand is AddressOf { Target: Register addressed })	11!
155	yield return addressed;	×
156	else if (operand is MemoryOperand memory)	11!
157	{
158	if (memory.Base is Register baseRegister)	×
159	yield return baseRegister;	×
160	if (memory.Index is Register indexRegister)	×
161	yield return indexRegister;	×
162	}
163	}
164	}	15✔
165
166	private void InsertPhiFunctions(ISILControlFlowGraph graph, DominatorInfo dominance)
167	{
168	var defSites = GetDefinitionSites(graph);	2✔
169
170	foreach (var entry in defSites)	12✔
171	{
172	var regNumber = entry.Key;	4✔
173	var sites = entry.Value;	4✔
174
175	var workList = new Queue<Block>(sites);	4✔
176	var onWorkList = new HashSet<Block>(sites);	4✔
177	var hasPhi = new HashSet<Block>();	4✔
178
179	while (workList.Count > 0)	13✔
180	{
181	var block = workList.Dequeue();	9✔
182
183	if (!dominance.DominanceFrontier.TryGetValue(block, out var frontier))	9✔
184	continue;
185
186	foreach (var frontierBlock in frontier)	28✔
187	{
188	// Only one phi per (block, register).
189	if (!hasPhi.Add(frontierBlock))	5✔
190	continue;
191
192	InsertPhiSkeleton(frontierBlock, regNumber);	3✔
193
194	// Inserting a phi is itself a definition, so propagate to its frontier too.
195	if (onWorkList.Add(frontierBlock))	3✔
196	workList.Enqueue(frontierBlock);	2✔
197	}
198	}
199	}
200	}	2✔
201
202	private static Dictionary<int, HashSet<Block>> GetDefinitionSites(ISILControlFlowGraph graph)
203	{
204	var defSites = new Dictionary<int, HashSet<Block>>();	2✔
205
206	foreach (var block in graph.Blocks)	30✔
207	{
208	foreach (var operand in block.Def)	40✔
209	{
210	if (operand is not Register register)	7✔
211	continue;
212
213	if (!defSites.TryGetValue(register.Number, out var sites))	7✔
214	defSites[register.Number] = sites = [];	4✔
215
216	sites.Add(block);	7✔
217	}
218	}
219
220	return defSites;	2✔
221	}
222
223	/// <summary>
224	/// Inserts an unresolved phi node at the top of <paramref name="block"/> with one source slot
225	/// per predecessor (positionally aligned to <see cref="Block.Predecessors"/>). The destination
226	/// and source placeholders are versioned later during renaming.
227	/// </summary>
228	private void InsertPhiSkeleton(Block block, int regNumber)
229	{
230	var register = _repr[regNumber];	3✔
231
232	var operands = new List<IOperand>(1 + block.Predecessors.Count) { register }; // destination first	3✔
233	for (var i = 0; i < block.Predecessors.Count; i++)	18✔
234	operands.Add(register); // one source per predecessor, filled in during renaming	6✔
235
236	block.Instructions.Insert(0, new Instruction(-1, OpCode.Phi, operands));	3✔
237	}	3✔
238
239	private void Rename(Block initialBlock, DominatorInfo dominance)
240	{
241	var remaining = new Stack<(Stack<Block>, List<int>)>();	2✔
242	remaining.Push((new Stack<Block>([initialBlock]), []));	2✔
243
244	while (remaining.Count > 0)	25✔
245	{
246	var (blocks, parentDefinedRegisters) = remaining.Pop();	23✔
247	if (blocks.Count == 0)	23✔
248	{
249	// Leaving the block: pop the versions it defined.
250	foreach (var regNumber in parentDefinedRegisters)	38✔
251	_stacks[regNumber].Pop();	9✔
252
253	continue;
254	}
255
256	var block = blocks.Pop();	13✔
257	remaining.Push((blocks, parentDefinedRegisters));	13✔
258
259	// Register numbers newly defined in this block, so we can pop their versions on the way out.
260	var definedHere = new List<int>();	13✔
261
262	foreach (var instruction in block.Instructions)	62✔
263	{
264	// A phi's operands belong to the incoming edges, so they are filled by predecessors;
265	// only its destination is renamed here.
266	if (instruction.OpCode != OpCode.Phi)	18✔
267	RewriteUses(instruction);	15✔
268
269	if (instruction.Destination is Register definition)	18✔
270	instruction.Destination = NewName(definition, definedHere);	11✔
271
272	for (var i = 0; i < instruction.Operands.Count; i++)	106✔
273	{
274	// Taking a slot's address lets the callee assign it, so the slot stops holding anything that reached this point, UNLESS
275	// nothing reads it afterwards, in which case any write is unobservable and the callee is only reading the value it has now
276	if (instruction.Operands[i] is AddressOf { Target: Register addressed })	35!
NEW 277	instruction.SetOperand(i, new AddressOf(_clobbering.Contains(instruction)	×
NEW 278	? NewName(addressed, definedHere)	×
NEW 279	: CurrentVersion(addressed.Number)));	×
280	}
281	}
282
283	// Resolve the phi operands of successors that correspond to this block's outgoing edge.
284	foreach (var successor in block.Successors)	52✔
285	{
286	var predIndex = successor.Predecessors.IndexOf(block);	13✔
287	if (predIndex < 0)	13✔
288	continue;
289
290	foreach (var phi in successor.Instructions)	78✔
291	{
292	if (phi.OpCode != OpCode.Phi)	26✔
293	continue;
294
295	var regNumber = ((Register)phi.Operands[0]).Number;	6✔
296	phi.SetOperand(1 + predIndex, CurrentVersion(regNumber));	6✔
297	}
298	}
299
300	// Recurse over the dominator tree.
301	if (dominance.DominanceTree.TryGetValue(block, out var children))	13✔
302	{
303	remaining.Push((new Stack<Block>(children), definedHere));	8✔
304	}
305	}
306	}	2✔
307
308	private void RewriteUses(Instruction instruction)
309	{
310	for (var i = 0; i < instruction.Operands.Count; i++)	82✔
311	{
312	var operand = instruction.Operands[i];	26✔
313
314	if (operand is Register register)	26✔
315	{
316	instruction.SetOperand(i, CurrentVersion(register.Number));	15✔
317	}
318	else if (operand is MemoryOperand memory)	11!
319	{
320	if (memory.Base is Register baseRegister)	×
321	memory.Base = CurrentVersion(baseRegister.Number);	×
322	if (memory.Index is Register indexRegister)	×
323	memory.Index = CurrentVersion(indexRegister.Number);	×
324
325	instruction.SetOperand(i, memory); // MemoryOperand is a struct, write the copy back	×
326	}
327	}
328	}	15✔
329
330	/// <summary>
331	/// The version of <paramref name="regNumber"/> currently in scope, or the entry value
332	/// (version -1) if it has not been defined on the current path.
333	/// </summary>
334	private Register CurrentVersion(int regNumber)
335	{
336	if (_stacks.TryGetValue(regNumber, out var stack) && stack.Count > 0)	21✔
337	return stack.Peek();	16✔
338
339	return _repr.TryGetValue(regNumber, out var register) ? register : new Register(regNumber, null);	5!
340	}
341
342	private Register NewName(Register register, List<int> definedHere)
343	{
344	var regNumber = register.Number;	11✔
345
346	var version = _counter.TryGetValue(regNumber, out var current) ? current + 1 : 1;	11✔
347	_counter[regNumber] = version;	11✔
348
349	var versioned = register.Copy(version);	11✔
350
351	if (!_stacks.TryGetValue(regNumber, out var stack))	11✔
352	_stacks[regNumber] = stack = new Stack<Register>();	4✔
353
354	stack.Push(versioned);	11✔
355	definedHere.Add(regNumber);	11✔
356
357	return versioned;	11✔
358	}
359
360	/// <summary>
361	/// Destroys SSA form by replacing each phi with copies on the incoming edges. For a phi
362	/// <c>dest = phi(s0, s1, ...)</c> a <c>Move dest, s[i]</c> is appended (before the terminator)
363	/// to the i-th predecessor. Phi operands are positionally aligned to the predecessor list, so
364	/// the i-th source belongs to the i-th predecessor.
365	/// </summary>
366	public static void Remove(MethodAnalysisContext method)
367	{
368	var cfg = method.ControlFlowGraph!;	×
369
370	foreach (var block in cfg.Blocks)	×
371	{
372	var phiInstructions = block.Instructions	×
373	.Where(i => i.OpCode == OpCode.Phi)	×
374	.ToList();	×
375
376	if (phiInstructions.Count == 0)	×
377	continue;
378
379	for (var predIndex = 0; predIndex < block.Predecessors.Count; predIndex++)	×
380	{
381	var predecessor = block.Predecessors[predIndex];	×
382	var moves = new List<Instruction>();	×
383
384	foreach (var phi in phiInstructions)	×
385	{
386	if (1 + predIndex >= phi.Operands.Count)	×
387	continue;
388
389	var destination = phi.Operands[0];	×
390	var source = phi.Operands[1 + predIndex];	×
391
392	// Skip redundant self-copies.
393	if (Equals(destination, source))	×
394	continue;
395
396	moves.Add(new Instruction(-1, OpCode.Move, destination, source));	×
397	}
398
399	InsertBeforeTerminator(predecessor, moves);	×
400	}
401
402	foreach (var phi in phiInstructions)	×
403	{
404	phi.OpCode = OpCode.Nop;	×
405	phi.SetOperands();	×
406	}
407	}
408
409	cfg.RemoveNops();	×
410	cfg.RemoveEmptyBlocks();	×
411	}	×
412
413	/// <summary>
414	/// Inserts <paramref name="moves"/> at the end of <paramref name="block"/>, but before any
415	/// trailing control-flow instruction, so the copies execute on the outgoing edge.
416	/// </summary>
417	private static void InsertBeforeTerminator(Block block, List<Instruction> moves)
418	{
419	if (moves.Count == 0)	×
420	return;	×
421
422	var insertAt = block.Instructions.Count;	×
423
424	if (insertAt > 0 && !block.Instructions[insertAt - 1].IsFallThrough)	×
425	insertAt--;	×
426
427	block.Instructions.InsertRange(insertAt, moves);	×
428	}	×
429	}

SamboyCoding / Cpp2IL / 30815175474

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