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

38.29

/Cpp2IL.Core/Graphs/ISILControlFlowGraph.cs

1	using System;
2	using System.Collections.Generic;
3	using System.Linq;
4	using Cpp2IL.Core.ISIL;
5
6	namespace Cpp2IL.Core.Graphs;
7
8	public class ISILControlFlowGraph
9	{
10	public Block EntryBlock;
11	public Block ExitBlock;
NEW 12	public int Count => Blocks.Count;	×
13	public List<Block> Blocks;
14
15	public List<Instruction> Instructions
16	{
17	get
18	{
19	// BFS search
NEW 20	var visited = new HashSet<Block>();	×
NEW 21	var queue = new Queue<Block>();	×
NEW 22	var result = new List<Instruction>();	×
23
NEW 24	queue.Enqueue(EntryBlock);	×
25
NEW 26	while (queue.Count > 0)	×
27	{
NEW 28	var current = queue.Dequeue();	×
29
NEW 30	if (!visited.Add(current))	×
31	continue;
32
NEW 33	result.AddRange(current.Instructions);	×
34
NEW 35	foreach (var successor in current.Successors)	×
36	{
NEW 37	if (!visited.Contains(successor))	×
NEW 38	queue.Enqueue(successor);	×
39	}
40	}
41
NEW 42	return result; // Should this be cached?	×
43	}
44	}
45
46	private int idCounter;
47
48	public ISILControlFlowGraph(List<Instruction> instructions)	4✔
49	{
50	EntryBlock = new Block	4✔
51	{	4✔
52	ID = idCounter++,	4✔
53	BlockType = BlockType.Entry	4✔
54	};	4✔
55
56	ExitBlock = new Block	4✔
57	{	4✔
58	ID = idCounter++,	4✔
59	BlockType = BlockType.Exit	4✔
60	};	4✔
61
62	Blocks =	4✔
63	[	4✔
64	EntryBlock,	4✔
65	ExitBlock	4✔
66	];	4✔
67
68	Build(instructions);	4✔
69	}	4✔
70
71	private bool TryGetTargetJumpInstructionIndex(Instruction instruction, out int jumpInstructionIndex)
72	{
73	jumpInstructionIndex = 0;	×
74	try
75	{
NEW 76	jumpInstructionIndex = ((Instruction)instruction.Operands[0]).Index;	×
77	return true;	×
78	}
79	catch	×
80	{
81	// ignore
82	}	×
83
84	return false;	×
85	}	×
86
87	public void RemoveUnreachableBlocks()
88	{
NEW 89	if (Blocks.Count == 0)	×
NEW 90	return;	×
91
92	// Get blocks reachable from entry
NEW 93	var reachable = new List<Block>();	×
NEW 94	var visited = new List<Block> { EntryBlock };	×
NEW 95	reachable.Add(EntryBlock);	×
96
NEW 97	var total = 0;	×
NEW 98	while (total < reachable.Count)	×
99	{
NEW 100	var block = reachable[total];	×
NEW 101	total++;	×
102
NEW 103	foreach (var successor in block.Successors)	×
104	{
NEW 105	if (visited.Contains(successor))	×
106	continue;
NEW 107	visited.Add(successor);	×
NEW 108	reachable.Add(successor);	×
109	}
110	}
111
112	// Get unreachable blocks
NEW 113	var unreachable = Blocks.Where(block => !visited.Remove(block)).ToList();	×
114
115	// Remove those
NEW 116	foreach (var block in unreachable)	×
117	{
118	// Don't remove entry or exit
NEW 119	if (block == EntryBlock \|\| block == ExitBlock)	×
120	continue;
121
NEW 122	block.Successors.Clear();	×
NEW 123	Blocks.Remove(block);	×
124	}
NEW 125	}	×
126
127	public void RemoveNops()
128	{
NEW 129	var usedAsTarget = new HashSet<Instruction>();	×
130
131	// Get all instructions used as branch targets
NEW 132	foreach (var block in Blocks)	×
133	{
NEW 134	foreach (var instr in block.Instructions)	×
135	{
NEW 136	foreach (var operand in instr.Operands)	×
137	{
NEW 138	if (operand is Instruction target)	×
NEW 139	usedAsTarget.Add(target);	×
140	}
141	}
142	}
143
144	// Build replacement map for NOPs that are safe to replace
NEW 145	var instructionReplacement = new Dictionary<Instruction, Instruction>();	×
NEW 146	foreach (var block in Blocks)	×
147	{
NEW 148	Instruction? replacement = null;	×
NEW 149	for (var i = block.Instructions.Count - 1; i >= 0; i--)	×
150	{
NEW 151	var instr = block.Instructions[i];	×
NEW 152	if (instr.OpCode == OpCode.Nop)	×
153	{
NEW 154	if (replacement != null && !usedAsTarget.Contains(instr))	×
NEW 155	instructionReplacement[instr] = replacement;	×
156	}
157	else
158	{
NEW 159	replacement = instr;	×
160	}
161	}
162	}
163
164	// Update operands
NEW 165	foreach (var block in Blocks)	×
166	{
NEW 167	foreach (var instr in block.Instructions)	×
168	{
NEW 169	for (var i = 0; i < instr.Operands.Count; i++)	×
170	{
NEW 171	if (instr.Operands[i] is Instruction target && instructionReplacement.TryGetValue(target, out var newTarget))	×
NEW 172	instr.Operands[i] = newTarget;	×
173	}
174	}
175	}
176
177	// Remove NOPs
NEW 178	foreach (var block in Blocks)	×
179	{
NEW 180	block.Instructions.RemoveAll(i => i.OpCode == OpCode.Nop && !usedAsTarget.Contains(i));	×
181	}
NEW 182	}	×
183
184	public void RemoveEmptyBlocks()
185	{
NEW 186	var toRemove = new List<Block>();	×
187
NEW 188	foreach (var block in Blocks)	×
189	{
NEW 190	if (block == EntryBlock \|\| block == ExitBlock)	×
191	continue;
192
NEW 193	if (block.Instructions.Count == 0)	×
194	{
195	// Redirect predecessors to successors
NEW 196	foreach (var pred in block.Predecessors)	×
197	{
NEW 198	pred.Successors.Remove(block);	×
NEW 199	foreach (var succ in block.Successors)	×
200	{
NEW 201	if (!pred.Successors.Contains(succ))	×
NEW 202	pred.Successors.Add(succ);	×
203	}
204	}
205
206	// Redirect successors to predecessors
NEW 207	foreach (var succ in block.Successors)	×
208	{
NEW 209	succ.Predecessors.Remove(block);	×
NEW 210	foreach (var pred in block.Predecessors)	×
211	{
NEW 212	if (!succ.Predecessors.Contains(pred))	×
NEW 213	succ.Predecessors.Add(pred);	×
214	}
215	}
216
NEW 217	toRemove.Add(block);	×
218	}
219	}
220
NEW 221	foreach (var block in toRemove)	×
NEW 222	Blocks.Remove(block);	×
NEW 223	}	×
224
225	public void BuildUseDefLists()
226	{
NEW 227	foreach (var block in Blocks)	×
228	{
NEW 229	var use = new List<object>();	×
NEW 230	var def = new List<object>();	×
231
NEW 232	foreach (var instruction in block.Instructions)	×
233	{
NEW 234	foreach (var operand in instruction.Sources.Where(operand => !use.Contains(operand)))	×
NEW 235	use.Add(operand);	×
236
NEW 237	if (instruction.Destination != null && !def.Contains(instruction.Destination))	×
NEW 238	def.Add(instruction.Destination);	×
239	}
240
NEW 241	block.Use = use;	×
NEW 242	block.Def = def;	×
243	}
NEW 244	}	×
245
246	public void MergeCallBlocks()
247	{
NEW 248	var toRemove = new List<Block>();	×
249
NEW 250	for (var i = 0; i < Blocks.Count; i++)	×
251	{
NEW 252	var block = Blocks[i];	×
NEW 253	if (block.BlockType != BlockType.Call) continue;	×
254
NEW 255	if (block.Successors.Count != 1)	×
256	continue;
257
NEW 258	var nextBlock = block.Successors[0];	×
259
260	// make sure that the next block only has one predecessor (this)
NEW 261	if (nextBlock.Predecessors.Count != 1 \|\| nextBlock.Predecessors[0] != block)	×
262	continue;
263
264	// merge instructions
NEW 265	block.Instructions.AddRange(nextBlock.Instructions);	×
NEW 266	block.Successors = nextBlock.Successors;	×
267
268	// fix up successors predecessors
NEW 269	foreach (var successor in nextBlock.Successors)	×
270	{
NEW 271	for (var j = 0; j < successor.Predecessors.Count; j++)	×
272	{
NEW 273	if (successor.Predecessors[j] == nextBlock)	×
NEW 274	successor.Predecessors[j] = block;	×
275	}
276	}
277
NEW 278	toRemove.Add(nextBlock);	×
279	}
280
281	// Remove all merged blocks
NEW 282	foreach (var removed in toRemove)	×
NEW 283	Blocks.Remove(removed);	×
284
NEW 285	foreach (var block in Blocks)	×
NEW 286	block.CalculateBlockType();	×
NEW 287	}	×
288
289	private void Build(List<Instruction> instructions)
290	{
291	if (instructions == null)	4!
292	throw new ArgumentNullException(nameof(instructions));	×
293
294	var currentBlock = new Block() { ID = idCounter++ };	4✔
295	AddBlock(currentBlock);	4✔
296	AddDirectedEdge(EntryBlock, currentBlock);	4✔
297
298	for (var i = 0; i < instructions.Count; i++)	300✔
299	{
300	var isLast = i == instructions.Count - 1;	146✔
301	Block newBlock;
302
303	switch (instructions[i].OpCode)	146✔
304	{
305	case OpCode.Jump:
306	case OpCode.ConditionalJump:
307	currentBlock.AddInstruction(instructions[i]);	16✔
308
309	if (!isLast)	16!
310	{
311	newBlock = new Block() { ID = idCounter++ };	16✔
312	AddBlock(newBlock);	16✔
313
314	if (instructions[i].OpCode == OpCode.Jump)	16!
315	{
NEW 316	if (TryGetTargetJumpInstructionIndex(instructions[i], out int jumpTargetIndex))	×
NEW 317	currentBlock.Dirty = true;	×
318	else
NEW 319	AddDirectedEdge(currentBlock, ExitBlock);	×
320	}
321	else
322	{
323	AddDirectedEdge(currentBlock, newBlock);	16✔
324	currentBlock.Dirty = true;	16✔
325	}
326
327	currentBlock.CalculateBlockType();	16✔
328	currentBlock = newBlock;	16✔
329	}
330	else
331	{
NEW 332	AddDirectedEdge(currentBlock, ExitBlock);	×
333
NEW 334	if (instructions[i].OpCode == OpCode.Jump)	×
NEW 335	currentBlock.Dirty = true;	×
336	}
337
UNCOV 338	break;	×
339
340	case OpCode.Call:
341	case OpCode.CallVoid:
342	case OpCode.Return:
343	var isReturn = instructions[i].OpCode == OpCode.Return;	24✔
344
345	currentBlock.AddInstruction(instructions[i]);	24✔
346
347	if (!isLast)	24✔
348	{
349	newBlock = new Block() { ID = idCounter++ };	20✔
350	AddBlock(newBlock);	20✔
351	AddDirectedEdge(currentBlock, isReturn ? ExitBlock : newBlock);	20✔
352	currentBlock.CalculateBlockType();	20✔
353	currentBlock = newBlock;	20✔
354	}
355	else
356	{
357	AddDirectedEdge(currentBlock, ExitBlock);	4✔
358	currentBlock.CalculateBlockType();	4✔
359	}
360
361	break;	4✔
362
363	default:
364	currentBlock.AddInstruction(instructions[i]);	106✔
365	if (isLast)	106!
366	{
NEW 367	AddDirectedEdge(currentBlock, ExitBlock);	×
NEW 368	currentBlock.CalculateBlockType();	×
369	}
370	break;
371	}
372	}
373
374	for (var index = 0; index < Blocks.Count; index++)	120✔
375	{
376	var node = Blocks[index];	56✔
377	if (node.Dirty)	56✔
378	FixBlock(node);	16✔
379	}
380
381	// Connect blocks without successors to exit
382	foreach (var block in Blocks)	120✔
383	{
384	if (block.Successors.Count == 0 && block != EntryBlock && block != ExitBlock)	56!
NEW 385	AddDirectedEdge(block, ExitBlock);	×
386	}
387
388	// Change branch targets to blocks
389	foreach (var instruction in Blocks.SelectMany(block => block.Instructions))	356✔
390	{
391	if (instruction.Operands.Count > 0 && instruction.Operands[0] is Instruction target)	146✔
392	instruction.Operands[0] = FindBlockByInstruction(target)!;	16✔
393	}
394	}	4✔
395
396	private void FixBlock(Block block, bool removeJmp = false)
397	{
398	if (block.BlockType is BlockType.Fall)	16!
399	return;	×
400
401	var jump = block.Instructions.Last();	16✔
402
403	var targetInstruction = jump.Operands[0] as Instruction;	16✔
404
405	var destination = FindBlockByInstruction(targetInstruction);	16✔
406
407	if (destination == null)	16!
408	{
409	//We assume that we're tail calling another method somewhere. Need to verify if this breaks anywhere but it shouldn't in general
NEW 410	block.BlockType = BlockType.TailCall;	×
411	return;	×
412	}
413
414
415	int index = destination.Instructions.FindIndex(instruction => instruction == targetInstruction);	44✔
416
417	var targetNode = SplitAndCreate(destination, index);	16✔
418
419	AddDirectedEdge(block, targetNode);	16✔
420	block.Dirty = false;	16✔
421
422	if (removeJmp)	16!
NEW 423	block.Instructions.Remove(jump);	×
424	}	16✔
425
426	public Block? FindBlockByInstruction(Instruction? instruction)
427	{
428	if (instruction == null)	32!
429	return null;	×
430
431	for (var i = 0; i < Blocks.Count; i++)	756!
432	{
433	var block = Blocks[i];	378✔
434	for (var j = 0; j < block.Instructions.Count; j++)	2,644✔
435	{
436	var instr = block.Instructions[j];	976✔
437	if (instr == instruction)	976✔
438	{
439	return block;	32✔
440	}
441	}
442	}
443
444	return null;	×
445	}
446
447	private Block SplitAndCreate(Block target, int index)
448	{
449	if (index < 0 \|\| index >= target.Instructions.Count)	16!
450	throw new ArgumentOutOfRangeException(nameof(index));	×
451
452	// Don't need to split...
453	if (index == 0)	16✔
454	return target;	8✔
455
456	var newBlock = new Block() { ID = idCounter++ };	8✔
457
458	// target split in two
459	// targetFirstPart -> targetSecondPart aka newNode
460
461	// Take the instructions for the secondPart
462	var instructions = target.Instructions.GetRange(index, target.Instructions.Count - index);	8✔
463	target.Instructions.RemoveRange(index, target.Instructions.Count - index);	8✔
464
465	// Add those to the newNode
466	newBlock.Instructions.AddRange(instructions);	8✔
467	// Transfer control flow
468	newBlock.BlockType = target.BlockType;	8✔
469	target.BlockType = BlockType.Fall;	8✔
470
471	// Transfer successors
472	newBlock.Successors = target.Successors;	8✔
473	if (target.Dirty)	8✔
474	newBlock.Dirty = true;	4✔
475	target.Dirty = false;	8✔
476	target.Successors = [];	8✔
477
478	// Correct the predecessors for all the successors
479	foreach (var successor in newBlock.Successors)	32✔
480	{
481	for (int i = 0; i < successor.Predecessors.Count; i++)	32✔
482	{
483	if (successor.Predecessors[i].ID == target.ID)	8✔
484	successor.Predecessors[i] = newBlock;	8✔
485	}
486	}
487
488	// Add newNode and connect it
489	AddBlock(newBlock);	8✔
490	AddDirectedEdge(target, newBlock);	8✔
491
492	return newBlock;	8✔
493	}
494
495	private void AddDirectedEdge(Block from, Block to)
496	{
497	from.Successors.Add(to);	68✔
498	to.Predecessors.Add(from);	68✔
499	}	68✔
500
501	protected void AddBlock(Block block) => Blocks.Add(block);	48✔
502	}

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