17216182984

Committed 25 Aug 2025 05:35PM UTC coverage: 30.38% (-4.0%) from 34.352%

Build # 17216182984

Build Type

Pull #481

github

Committed by

web-flow

Commit Message

Merge b82763a24 into d5260685f

Pull Request Pull Request #481: Decompiler

Run Details

1804 of 7561 branches covered (23.86%)

Branch coverage included in aggregate %.

100 of 1839 new or added lines in 29 files covered. (5.44%)

41 existing lines in 6 files now uncovered.

4093 of 11850 relevant lines covered (34.54%)

165575.01 hits per line

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

0.0

/Cpp2IL.Core/Analysis/SsaForm.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	public class SsaForm
10	{
NEW 11	private Dictionary<int, Stack<Register>> _versions = new();	×
NEW 12	private Dictionary<int, int> _versionCount = new();	×
NEW 13	private Dictionary<Block, Dictionary<int, Register>> _blockOutVersions = new();	×
14
15	public static void Build(MethodAnalysisContext method)
16	{
NEW 17	var ssa = new SsaForm();	×
18
NEW 19	method.ControlFlowGraph!.BuildUseDefLists();	×
20
NEW 21	ssa._versions.Clear();	×
NEW 22	ssa._versionCount.Clear();	×
NEW 23	ssa._blockOutVersions.Clear();	×
24
NEW 25	var graph = method.ControlFlowGraph!;	×
NEW 26	var dominatorInfo = method.DominatorInfo!;	×
27
NEW 28	ssa.ProcessBlock(graph.EntryBlock, dominatorInfo.DominanceTree);	×
NEW 29	ssa.InsertAllPhiFunctions(graph, dominatorInfo, method.ParameterOperands);	×
NEW 30	}	×
31
32	private void InsertAllPhiFunctions(ISILControlFlowGraph graph, DominatorInfo dominance, List<object> parameters)
33	{
34	// Check where registers are defined
NEW 35	var defSites = GetDefinitionSites(graph);	×
36
37	// For each register
NEW 38	foreach (var entry in defSites)	×
39	{
NEW 40	var regNumber = entry.Key;	×
41
NEW 42	var workList = new Queue<Block>(entry.Value);	×
NEW 43	var phiInserted = new HashSet<Block>();	×
44
NEW 45	while (workList.Count > 0)	×
46	{
NEW 47	var block = workList.Dequeue();	×
48
49	// For each dominance frontier block of the current block
NEW 50	if (!dominance.DominanceFrontier.TryGetValue(block, out var dfBlocks))	×
51	continue;
52
NEW 53	foreach (var dfBlock in dfBlocks)	×
54	{
55	// Already visited
NEW 56	if (phiInserted.Contains(dfBlock)) continue;	×
57
58	// For each predecessor, get it's last register version
NEW 59	var sources = new List<Register>();	×
NEW 60	foreach (var pred in dfBlock.Predecessors)	×
61	{
NEW 62	if (_blockOutVersions.TryGetValue(pred, out var mapping)	×
NEW 63	&& mapping.TryGetValue(regNumber, out var versionedReg))	×
64	{
NEW 65	sources.Add(versionedReg);	×
66	}
67	else
68	{
69	// It's not in predecessors so it's probably a parameter
NEW 70	var param = parameters.OfType<Register>().FirstOrDefault(p => p.Number == regNumber);	×
NEW 71	sources.Add(param);	×
72	}
73	}
74
75	// Insert phi into the frontier block
NEW 76	InsertPhiFunction(sources, dfBlock);	×
NEW 77	phiInserted.Add(dfBlock);	×
78
79	// If dfBlock doesn't define this register, add it to queue
NEW 80	var defines = dfBlock.Def.Any(operand => operand is Register r && r.Number == regNumber);	×
NEW 81	if (!defines)	×
NEW 82	workList.Enqueue(dfBlock);	×
83	}
84	}
85	}
NEW 86	}	×
87
88	private static Dictionary<int, HashSet<Block>> GetDefinitionSites(ISILControlFlowGraph graph)
89	{
90	// Check what registers are defined and where
NEW 91	var defSites = new Dictionary<int, HashSet<Block>>();	×
92
NEW 93	foreach (var block in graph.Blocks)	×
94	{
NEW 95	for (var i = 0; i < block.Def.Count; i++)	×
96	{
NEW 97	var operand = block.Def[i];	×
98
NEW 99	if (operand is Register register)	×
100	{
NEW 101	if (!defSites.ContainsKey(register.Number))	×
NEW 102	defSites[register.Number] = [];	×
NEW 103	defSites[register.Number].Add(block);	×
104	}
105	}
106	}
107
NEW 108	return defSites;	×
109	}
110
111	private void InsertPhiFunction(List<Register> sources, Block block)
112	{
113	// Create phi dest, src1, src2, etc.
NEW 114	var destination = GetNewVersion(sources[0]);	×
NEW 115	var phi = new Instruction(-1, OpCode.Phi, destination);	×
116
NEW 117	foreach (var source in sources.Distinct())	×
NEW 118	phi.Operands.Add(source);	×
119
120	// Add it
NEW 121	block.Instructions.Insert(0, phi);	×
122	// Replace uses
NEW 123	ReplaceRegistersUntilReassignment(block, 1, destination);	×
NEW 124	}	×
125
126	private static void ReplaceRegistersUntilReassignment(Block block, int startIndex, Register register)
127	{
NEW 128	for (var i = startIndex; i < block.Instructions.Count; i++)	×
129	{
NEW 130	var instruction = block.Instructions[i];	×
131
132	// Reassignment?
NEW 133	if (instruction.Destination is Register destination)	×
134	{
NEW 135	if (destination.Number == register.Number)	×
NEW 136	return;	×
137	}
138
139	// Replace it
NEW 140	for (var j = 0; j < instruction.Operands.Count; j++)	×
141	{
NEW 142	var operand = instruction.Operands[j];	×
143
NEW 144	if (operand is Register register2)	×
145	{
NEW 146	if (register2.Number == register.Number)	×
NEW 147	instruction.Operands[j] = register;	×
148	}
149
NEW 150	if (operand is MemoryOperand memory)	×
151	{
NEW 152	if (memory.Base != null)	×
153	{
NEW 154	var baseRegister = (Register)memory.Base;	×
155
NEW 156	if (baseRegister.Number == register.Number)	×
NEW 157	memory.Base = register;	×
158	}
159
NEW 160	if (memory.Index != null)	×
161	{
NEW 162	var index = (Register)memory.Index;	×
163
NEW 164	if (index.Number == register.Number)	×
NEW 165	memory.Index = register;	×
166	}
167
NEW 168	instruction.Operands[j] = memory;	×
169	}
170	}
171	}
NEW 172	}	×
173
174	private Register GetNewVersion(Register old)
175	{
NEW 176	if (!_versionCount.ContainsKey(old.Number))	×
177	{
178	// Params are version 0
NEW 179	_versionCount.Add(old.Number, 0);	×
NEW 180	_versions.Add(old.Number, new Stack<Register>());	×
NEW 181	_versions[old.Number].Push(old.Copy(0));	×
182	}
183
NEW 184	_versionCount[old.Number]++;	×
NEW 185	var newRegister = old.Copy(_versionCount[old.Number]);	×
NEW 186	_versions[old.Number].Push(newRegister);	×
NEW 187	return newRegister;	×
188	}
189
190	private void ProcessBlock(Block block, Dictionary<Block, List<Block>> dominanceTree)
191	{
NEW 192	foreach (var instruction in block.Instructions)	×
193	{
194	// Replace registers with SSA versions
NEW 195	for (var i = 0; i < instruction.Operands.Count; i++)	×
196	{
NEW 197	if (instruction.Operands[i] is Register register)	×
198	{
NEW 199	if (_versions.TryGetValue(register.Number, out var versions))	×
NEW 200	instruction.Operands[i] = register.Copy(versions.Peek().Version);	×
201	}
202
NEW 203	if (instruction.Operands[i] is MemoryOperand memory)	×
204	{
NEW 205	if (memory.Base != null)	×
206	{
NEW 207	var baseRegister = (Register)memory.Base;	×
208
NEW 209	if (_versions.TryGetValue(baseRegister.Number, out var versions))	×
NEW 210	memory.Base = baseRegister.Copy(versions.Peek().Version);	×
211	}
212
NEW 213	if (memory.Index != null)	×
214	{
NEW 215	var indexRegister = (Register)memory.Index;	×
216
NEW 217	if (_versions.TryGetValue(indexRegister.Number, out var versions))	×
NEW 218	memory.Index = indexRegister.Copy(versions.Peek().Version);	×
219	}
220
NEW 221	instruction.Operands[i] = memory;	×
222	}
223	}
224
225	// Create new version
NEW 226	if (instruction.Destination is Register destination)	×
NEW 227	instruction.Destination = GetNewVersion(destination);	×
228	}
229
230	// Record last register version
NEW 231	var outMapping = new Dictionary<int, Register>();	×
NEW 232	foreach (var kvp in _versions)	×
233	{
NEW 234	if (kvp.Value.Count > 0)	×
NEW 235	outMapping[kvp.Key] = kvp.Value.Peek();	×
236	}
237
NEW 238	_blockOutVersions[block] = outMapping;	×
239
240	// Process children in the tree
NEW 241	if (dominanceTree.TryGetValue(block, out var children))	×
242	{
NEW 243	foreach (var child in children)	×
NEW 244	ProcessBlock(child, dominanceTree);	×
245	}
246
247	// Remove registers from versions but not from count
NEW 248	foreach (var instruction in block.Instructions.Where(i => i.Destination is Register))	×
249	{
NEW 250	var register = (Register)instruction.Destination!;	×
NEW 251	_versions.FirstOrDefault(kv => kv.Key == register.Number).Value.Pop();	×
252	}
NEW 253	}	×
254
255	public static void Remove(MethodAnalysisContext method)
256	{
NEW 257	var cfg = method.ControlFlowGraph!;	×
258
NEW 259	foreach (var block in cfg.Blocks)	×
260	{
261	// Get all phis
NEW 262	var phiInstructions = block.Instructions	×
NEW 263	.Where(i => i.OpCode == OpCode.Phi)	×
NEW 264	.ToList();	×
265
NEW 266	if (phiInstructions.Count == 0) continue;	×
267
NEW 268	foreach (var predecessor in block.Predecessors)	×
269	{
NEW 270	if (predecessor.Instructions.Count == 0)	×
271	continue;
272
NEW 273	predecessor.Instructions.RemoveAt(0);	×
NEW 274	var moves = new List<Instruction>();	×
275
NEW 276	foreach (var phi in phiInstructions)	×
277	{
NEW 278	var result = (LocalVariable)phi.Operands[0]!;	×
NEW 279	var sources = phi.Operands.Skip(1).Cast<LocalVariable>().ToList();	×
280
NEW 281	var predIndex = block.Predecessors.IndexOf(predecessor);	×
282
NEW 283	if (predIndex < 0 \|\| predIndex >= sources.Count)	×
284	continue;
285
NEW 286	var source = sources[predIndex];	×
287
288	// Add move for it
NEW 289	moves.Add(new Instruction(-1, OpCode.Move, result, source));	×
290	}
291
292	// Add all of those moves
NEW 293	if (predecessor.Instructions.Count == 0)	×
NEW 294	predecessor.Instructions = moves;	×
295	else
NEW 296	predecessor.Instructions.InsertRange(predecessor.Instructions.Count - (predecessor.Instructions.Count == 1 ? 1 : 2), moves);	×
297	}
298
299	// Remove all phis
NEW 300	foreach (var instruction in block.Instructions)	×
301	{
NEW 302	if (instruction.OpCode == OpCode.Phi)	×
303	{
NEW 304	instruction.OpCode = OpCode.Nop;	×
NEW 305	instruction.Operands = [];	×
306	}
307	}
308	}
309
NEW 310	cfg.RemoveNops();	×
NEW 311	cfg.RemoveEmptyBlocks();	×
NEW 312	}	×
313	}

SamboyCoding / Cpp2IL / 17216182984

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