• Home
  • Features
  • Pricing
  • Docs
  • Announcements
  • Sign In

SamboyCoding / Cpp2IL / 30771032007

02 Aug 2026 10:51PM UTC coverage: 34.288% (+0.1%) from 34.169%
30771032007

push

github

web-flow
optimize performance of simplifier and dominator calculation (#594)

2911 of 9942 branches covered (29.28%)

Branch coverage included in aggregate %.

141 of 155 new or added lines in 3 files covered. (90.97%)

1 existing line in 1 file now uncovered.

5347 of 14142 relevant lines covered (37.81%)

156323.88 hits per line

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

82.46
/Cpp2IL.Core/Analysis/Simplifier.cs
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
/// Post-SSA copy/constant cleanup. The bulk of copy and constant propagation is done earlier, in SSA,
11
/// by <see cref="SsaSimplifier"/>; this pass mops up the copies that <em>destroying</em> SSA leaves
12
/// behind - each phi is lowered to a <c>Move</c> on every incoming edge, so the phi's result becomes a
13
/// single local with one definition per predecessor.
14
///
15
/// Those multiple definitions mean a value is no longer single-assignment: at the join the definitions
16
/// merge, and which one reaches a use is path-dependent. So unlike <see cref="SsaSimplifier"/>, this
17
/// pass cannot blindly forward a definition - it walks the CFG and refuses to carry a multiply-defined
18
/// local's value across the join its other definitions merge at (where the phi used to be).
19
/// </summary>
20
public static class Simplifier
21
{
22
    public static void Simplify(MethodAnalysisContext method)
23
    {
24
        new SimplifierContext(method).Process();
3✔
25
    }
3✔
26

27
    private readonly ref struct SimplifierContext(MethodAnalysisContext method)
28
    {
29
        private readonly Dictionary<Block, Dictionary<Instruction, OperandList>> _sourceCache = [];
3✔
30
        private readonly MethodAnalysisContext _method = method;
3✔
31
        private readonly ISILControlFlowGraph _graph = method.ControlFlowGraph!;
3✔
32

33
        public void Process()
34
        {
35
            PopulateSourceCache();
3✔
36

37
            InlineLocals();
3✔
38

39
            // Repeat until no change
40
            while (InlineConstantsSinglePass()) ;
6✔
41

42
            // More locals can now be inlined
43
            InlineLocals();
3✔
44

45
            _graph.RemoveNops();
3✔
46
            _graph.RemoveEmptyBlocks();
3✔
47
        }
3✔
48

49
        private void PopulateSourceCache()
50
        {
51
            #if NET5_0_OR_GREATER
52
            _sourceCache.EnsureCapacity(_graph.Blocks.Count);
3✔
53
            #endif
54

55
            foreach (var block in _graph.Blocks)
38✔
56
            {
57
                var sourceCache = new Dictionary<Instruction, OperandList>(block.Instructions.Count);
16✔
58
                foreach (var instruction in block.Instructions)
70✔
59
                {
60
                    sourceCache[instruction] = instruction.Sources;
19✔
61
                }
62

63
                _sourceCache[block] = sourceCache;
16✔
64
            }
65
        }
3✔
66

67
        private void UpdateSourceCache(Block block, Instruction instruction)
68
        {
69
            _sourceCache[block][instruction] = instruction.Operands;
12✔
70
        }
12✔
71

72
        private bool InlineConstantsSinglePass()
73
        {
74
            var changed = false;
6✔
75
            var definitionCounts = CountDefinitions();
6✔
76

77
            var visited = new HashSet<Block>();
6✔
78
            var queue = new Queue<Block>(_graph.Blocks.Count);
6✔
79

80
#if NET5_0_OR_GREATER
81
            visited.EnsureCapacity(_graph.Blocks.Count);
6✔
82
#endif
83

84
            queue.Enqueue(_graph.EntryBlock);
6✔
85
            visited.Add(_graph.EntryBlock);
6✔
86

87
            while (queue.Count > 0)
38✔
88
            {
89
                var block = queue.Dequeue();
32✔
90

91
                for (var i = 0; i < block.Instructions.Count; i++)
140✔
92
                {
93
                    var instruction = block.Instructions[i];
38✔
94

95
                    // If it's move and it moves something to local, replace and remove it
96
                    if (instruction.OpCode == OpCode.Move && instruction.Operands[0] is LocalVariable local)
38!
97
                    {
98
                        if (IsLocalUsedAfterInstruction(block, i + 1, local, out var usedByMemory))
9!
99
                        {
100
                            // This can't be inlined into memory operand
101
                            if (usedByMemory) continue;
9!
102

103
                            // A local with several definitions is not in SSA form, so its value at a join
104
                            // depends on the path taken; don't carry this definition across that join.
105
                            var stopAtJoins = definitionCounts.TryGetValue(local, out var defs) && defs > 1;
9!
106

107
                            // Replace local
108
                            ReplaceLocalsUntilReassignment(block, i + 1, local, instruction.Operands[1], stopAtJoins);
9✔
109

110
                            // Only drop the defining move once the local has no remaining uses; if the
111
                            // replacement stopped at a join, the local is still live past it so the move stays.
112
                            if (IsLocalUsedAfterInstruction(block, i + 1, local, out _))
9✔
113
                                continue;
114

115
                            // Change that move to nop
116
                            instruction.OpCode = OpCode.Nop;
5✔
117
                            instruction.SetOperands();
5✔
118
                            UpdateSourceCache(block, instruction);
5✔
119

120
                            changed = true;
5✔
121
                        }
122
                    }
123
                }
124

125
                foreach (var successor in block.Successors)
120✔
126
                {
127
                    if (visited.Add(successor))
28✔
128
                        queue.Enqueue(successor);
26✔
129
                }
130
            }
131

132
            return changed;
6✔
133
        }
134

135
        private void InlineLocals()
136
        {
137
            var definitionCounts = CountDefinitions();
6✔
138

139
            var visited = new HashSet<Block>();
6✔
140
            var queue = new Queue<Block>(_method.ControlFlowGraph!.Blocks.Count);
6✔
141

142
#if NET5_0_OR_GREATER
143
            visited.EnsureCapacity(_graph.Blocks.Count);
6✔
144
#endif
145

146
            queue.Enqueue(_graph.EntryBlock);
6✔
147
            visited.Add(_graph.EntryBlock);
6✔
148

149
            while (queue.Count > 0)
38✔
150
            {
151
                var block = queue.Dequeue();
32✔
152

153
                for (var i = 0; i < block.Instructions.Count; i++)
140✔
154
                {
155
                    var instruction = block.Instructions[i];
38✔
156

157
                    // If it's move and it moves local to local, replace and remove it
158
                    if (instruction is { OpCode: OpCode.Move, Operands: [LocalVariable local, LocalVariable source] })
38!
159
                    {
160
                        // A local with several definitions is not in SSA form, so its value at a join
161
                        // depends on the path taken; don't carry this definition across that join.
162
                        var stopAtJoins = definitionCounts.TryGetValue(local, out var defs) && defs > 1;
3!
163

164
                        // Replace local with source
165
                        ReplaceLocalsUntilReassignment(block, i + 1, local, source, stopAtJoins);
3✔
166

167
                        // If the replacement stopped at a join merging another definition, the local is
168
                        // still live there - keep its defining move rather than dropping the value on this path.
169
                        if (IsLocalUsedAfterInstruction(block, i + 1, local, out _))
3✔
170
                            continue;
171

172
                        if (!_method.ParameterLocals.Contains(local))
1!
173
                            _method.Locals.Remove(local);
1✔
174

175
                        // Change that move to nop
176
                        instruction.OpCode = OpCode.Nop;
1✔
177
                        instruction.SetOperands();
1✔
178
                        UpdateSourceCache(block, instruction);
1✔
179
                    }
180
                }
181

182
                foreach (var successor in block.Successors)
120✔
183
                {
184
                    if (visited.Add(successor))
28✔
185
                        queue.Enqueue(successor);
26✔
186
                }
187
            }
188
        }
6✔
189

190
        // Counts how many instructions define each local. A local with more than one definition is not in
191
        // SSA form: at a control-flow join its value depends on which predecessor was taken, so none of its
192
        // definitions may be propagated across that join - a phi would be needed there instead.
193
        private Dictionary<LocalVariable, int> CountDefinitions()
194
        {
195
            var counts = new Dictionary<LocalVariable, int>();
12✔
196

197
            foreach (var instruction in _graph.Blocks.SelectMany(block => block.Instructions))
240✔
198
            {
199
                if (instruction.Destination is LocalVariable local)
76✔
200
                    counts[local] = counts.TryGetValue(local, out var count) ? count + 1 : 1;
23✔
201
            }
202

203
            return counts;
12✔
204
        }
205

206
        private void ReplaceLocalsUntilReassignment(Block startBlock, int startIndex, LocalVariable local,
207
            IOperand replacement, bool stopAtJoins)
208
        {
209
            var visited = new HashSet<Block>();
12✔
210
            var remaining = new Stack<(Block, int)>(_graph.Blocks.Count);
12✔
211

212
#if NET5_0_OR_GREATER
213
            visited.EnsureCapacity(_graph.Blocks.Count);
12✔
214
#endif
215

216
            visited.Add(startBlock);
12✔
217
            remaining.Push((startBlock, startIndex));
12✔
218

219
            while (remaining.Count > 0)
39✔
220
            {
221
                var (currentBlock, index) = remaining.Pop();
27✔
222

223
                // Process instructions starting at the given index
224
                for (var i = index; i < currentBlock.Instructions.Count; i++)
104✔
225
                {
226
                    var instruction = currentBlock.Instructions[i];
25✔
227

228
                    // Stop on this branch when reassigned
229
                    if (instruction.Destination is LocalVariable destLocal && destLocal == local)
25!
NEW
230
                        return;
×
231

232
                    // Replace operands
233
                    for (var j = 0; j < instruction.Operands.Count; j++)
124✔
234
                    {
235
                        var operand = instruction.Operands[j];
37✔
236

237
                        if (operand is LocalVariable usedLocal && usedLocal == local)
37✔
238
                        {
239
                            instruction.SetOperand(j, replacement);
5✔
240
                            UpdateSourceCache(currentBlock, instruction);
5✔
241
                        }
242

243
                        // A memory operand's base/index holds an address, so only a local replacement may
244
                        // be substituted there (copy propagation). A constant/value replacement is left in
245
                        // place - the caller sees the local is still used and keeps its defining move.
246
                        else if (operand is MemoryOperand memory && replacement is LocalVariable)
32✔
247
                        {
248
                            if (memory.Base is LocalVariable baseLocal && baseLocal == local)
1!
249
                                memory.Base = replacement;
1✔
250

251
                            if (memory.Index is LocalVariable indexLocal && indexLocal == local)
1!
NEW
252
                                memory.Index = replacement;
×
253

254
                            instruction.SetOperand(j, memory);
1✔
255
                            UpdateSourceCache(currentBlock, instruction);
1✔
256
                        }
257

258
                        // The object a field is accessed on is an address just like a memory base.
259
                        else if (operand is FieldReference field && replacement is LocalVariable fieldReplacement &&
31!
260
                                 field.Local == local)
31✔
261
                        {
NEW
262
                            field.Local = fieldReplacement;
×
263
                        }
264
                    }
265
                }
266

267
                // Process successors
268
                foreach (var successor in currentBlock.Successors)
96✔
269
                {
270
                    // A join merges this local's other definitions, so for a non-SSA (multiply-defined)
271
                    // local the replacement must not flow past it - the value there is path-dependent.
272
                    if (stopAtJoins && successor.Predecessors.Count > 1)
21✔
273
                        continue;
274

275
                    if (visited.Add(successor))
15✔
276
                        remaining.Push((successor, 0));
15✔
277
                }
278
            }
279
        }
12✔
280

281
        private bool IsLocalUsedAfterInstruction(Block startBlock, int startIndex, LocalVariable local, out bool usedByMemory)
282
        {
283
            var visited = new HashSet<Block>();
21✔
284
            var remaining = new Stack<(Block, int)>(_graph.Blocks.Count);
21✔
285

286
#if NET5_0_OR_GREATER
287
            visited.EnsureCapacity(_graph.Blocks.Count);
21✔
288
#endif
289

290
            visited.Add(startBlock);
21✔
291
            remaining.Push((startBlock, startIndex));
21✔
292

293
            usedByMemory = false;
21✔
294

295
            while (remaining.Count > 0)
52✔
296
            {
297
                var (currentBlock, index) = remaining.Pop();
46✔
298

299
                var blockSources = _sourceCache[currentBlock];
46✔
300

301
                // Process instructions
302
                for (var i = index; i < currentBlock.Instructions.Count; i++)
150✔
303
                {
304
                    var instruction = currentBlock.Instructions[i];
44✔
305
                    var sources = blockSources[instruction];
44✔
306

307
                    // Direct usage check
308
                    if (sources.Contains(local))
44✔
309
                        return true;
15✔
310

311
                    // A field access reads the object it is on, whether the field is being read or written,
312
                    // so the destination has to be considered too - a store is not in Sources.
313
                    foreach (var operand in instruction.Operands)
140✔
314
                    {
315
                        if (operand is FieldReference field && field.Local == local)
41!
316
                        {
NEW
317
                            usedByMemory = true;
×
NEW
318
                            return true;
×
319
                        }
320

321
                        // Likewise, an array element or length reads the array, and taking a slot's address reads it
322
                        // however the callee uses it - none of which are in Sources when they sit in a destination position.
323
                        if (operand is ArrayAccess array && (array.Array == local || array.Index == local as IOperand))
41!
324
                        {
NEW
325
                            usedByMemory = true;
×
NEW
326
                            return true;
×
327
                        }
328

329
                        if (operand is ArrayLength length && length.Array == local)
41!
330
                        {
NEW
331
                            usedByMemory = true;
×
332
                            return true;
×
333
                        }
334

335
                        if (operand is AddressOf { Target: LocalVariable addressed } && addressed == local)
41!
336
                        {
NEW
337
                            usedByMemory = true;
×
338
                            return true;
×
339
                        }
340
                    }
341

342
                    // Used in memory operand
343
                    foreach (var source in sources)
96✔
344
                    {
345
                        if (source is MemoryOperand memory)
19✔
346
                        {
347
                            if (memory.Base is LocalVariable memLocal && memLocal == local)
4!
348
                            {
NEW
349
                                usedByMemory = true;
×
NEW
350
                                return true;
×
351
                            }
352

353
                            if (memory.Index is LocalVariable memLocal2 && memLocal2 == local)
4!
354
                            {
NEW
355
                                usedByMemory = true;
×
NEW
356
                                return true;
×
357
                            }
358
                        }
359
                    }
360
                }
361

362
                // Process successors
363
                foreach (var successor in currentBlock.Successors)
112✔
364
                {
365
                    if (visited.Add(successor))
25✔
366
                        remaining.Push((successor, 0));
25✔
367
                }
368
            }
369

370
            return false;
6✔
UNCOV
371
        }
×
372
    }
373
}
STATUS · Troubleshooting · Open an Issue · Sales · Support · CAREERS · ENTERPRISE · START FREE TRIAL · SCHEDULE DEMO
ANNOUNCEMENTS · TWITTER · TOS & SLA · Supported CI Services · What's a CI service? · Automated Testing

© 2026 Coveralls, Inc