git.seregonwar.com

core/decompiler/analysis/DominatorAnalysis.h

ShadPKG / core / decompiler / analysis / DominatorAnalysis.h

1	#pragma once
2
3	#include "../ir/IR.h"
4	#include <algorithm>
5	#include <cstdint>
6	#include <map>
7	#include <memory>
8	#include <set>
9	#include <vector>
10
11	namespace ShadPKG::Decompiler::Analysis {
12
13	// ╔═══════════════════════════════════════════════════════════════════════════╗
14	// ║ DOMINATOR ANALYSIS ║
15	// ║ ║
16	// ║ Computes dominator tree and identifies natural loops via back-edges. ║
17	// ║ Uses Cooper-Harvey-Kennedy algorithm (efficient iterative approach). ║
18	// ╚═══════════════════════════════════════════════════════════════════════════╝
19
20	// ─────────────────────────────────────────────────────────────────────────────
21	// LoopInfo: Represents a detected natural loop
22	// ─────────────────────────────────────────────────────────────────────────────
23
24	struct LoopInfo {
25	uint64_t headerBlock; // Loop header (back-edge target)
26	uint64_t latchBlock; // Back-edge source
27	std::set<uint64_t> bodyBlocks; // All blocks in loop body
28	std::vector<uint64_t> exitBlocks; // Blocks that exit the loop
29	bool isDoWhile = false; // true if condition at end
30
31	bool contains(uint64_t blockId) const {
32	return bodyBlocks.find(blockId) != bodyBlocks.end();
33	}
34	};
35
36	// ─────────────────────────────────────────────────────────────────────────────
37	// DominatorAnalysis: Main analysis class
38	// ─────────────────────────────────────────────────────────────────────────────
39
40	class DominatorAnalysis {
41	public:
42	DominatorAnalysis() = default;
43
44	// ═══════════════════════════════════════════════════════════════════════
45	// Main Analysis Entry Point
46	// ═══════════════════════════════════════════════════════════════════════
47
48	void analyze(const std::shared_ptr<IR::Function> &func);
49
50	// ═══════════════════════════════════════════════════════════════════════
51	// Dominator Queries
52	// ═══════════════════════════════════════════════════════════════════════
53
54	// Get immediate dominator of a block
55	uint64_t getImmediateDominator(uint64_t blockId) const;
56
57	// Check if A dominates B (A is on every path from entry to B)
58	bool dominates(uint64_t dominator, uint64_t dominated) const;
59
60	// Check if A strictly dominates B (A dom B and A != B)
61	bool strictlyDominates(uint64_t dominator, uint64_t dominated) const;
62
63	// Get all dominators of a block
64	const std::set<uint64_t> &getDominators(uint64_t blockId) const;
65
66	// ═══════════════════════════════════════════════════════════════════════
67	// Post-Dominator Queries (for if-then-else detection)
68	// ═══════════════════════════════════════════════════════════════════════
69
70	uint64_t getImmediatePostDominator(uint64_t blockId) const;
71	bool postDominates(uint64_t postDom, uint64_t dominated) const;
72
73	// ═══════════════════════════════════════════════════════════════════════
74	// Loop Detection
75	// ═══════════════════════════════════════════════════════════════════════
76
77	const std::vector<LoopInfo> &getLoops() const { return loops_; }
78
79	// Check if block is a loop header
80	bool isLoopHeader(uint64_t blockId) const;
81
82	// Get the loop containing a block (nullptr if none)
83	const LoopInfo *getLoopFor(uint64_t blockId) const;
84
85	// ═══════════════════════════════════════════════════════════════════════
86	// Utility
87	// ═══════════════════════════════════════════════════════════════════════
88
89	// Get blocks in reverse post-order (for iteration)
90	const std::vector<uint64_t> &getReversePostOrder() const { return rpo_; }
91
92	// Get entry block ID
93	uint64_t getEntryBlock() const { return entryBlock_; }
94
95	private:
96	// ═══════════════════════════════════════════════════════════════════════
97	// Internal Algorithms
98	// ═══════════════════════════════════════════════════════════════════════
99
100	void computeReversePostOrder(const std::shared_ptr<IR::Function> &func);
101	void computeDominators();
102	void computePostDominators();
103	void detectBackEdges();
104	void buildLoops();
105
106	// Intersect helper for iterative dominator computation
107	uint64_t intersect(uint64_t b1, uint64_t b2) const;
108
109	// Collect loop body blocks using reverse DFS from latch
110	void collectLoopBody(uint64_t header, uint64_t latch,
111	std::set<uint64_t> &body);
112
113	// ═══════════════════════════════════════════════════════════════════════
114	// Data
115	// ═══════════════════════════════════════════════════════════════════════
116
117	// Block adjacency
118	std::map<uint64_t, std::vector<uint64_t>> successors_;
119	std::map<uint64_t, std::vector<uint64_t>> predecessors_;
120
121	// RPO numbering
122	std::vector<uint64_t> rpo_; // Blocks in reverse post-order
123	std::map<uint64_t, int> rpoNumber_; // Block ID → RPO index
124
125	// Dominators
126	std::map<uint64_t, uint64_t> idom_; // Immediate dominator
127	std::map<uint64_t, std::set<uint64_t>> doms_; // All dominators
128
129	// Post-dominators
130	std::map<uint64_t, uint64_t> ipdom_; // Immediate post-dominator
131	std::map<uint64_t, std::set<uint64_t>> pdoms_; // All post-dominators
132
133	// Back-edges & loops
134	std::vector<std::pair<uint64_t, uint64_t>> backEdges_; // (source, target)
135	std::vector<LoopInfo> loops_;
136	std::map<uint64_t, size_t> blockToLoop_; // Block → loop index
137
138	uint64_t entryBlock_ = 0;
139	uint64_t exitBlock_ = 0; // Virtual exit for post-dom
140
141	static const std::set<uint64_t> emptySet_;
142	};
143
144	} // namespace ShadPKG::Decompiler::Analysis
145

Seregon/ShadPKG