jdc_core/cfg.rs
1//! Machine-neutral control-flow graph.
2//!
3//! A front-end builds one [`Cfg`] per method body: basic blocks with machine
4//! offsets (`u32` — JVM bytecode pcs, DEX code units, ...), successor and
5//! predecessor edges, handler edges, and the exception ranges that connect
6//! them. Nothing here knows how instructions are encoded; the front-end keeps
7//! its own instruction storage alongside (it needs it to build expressions).
8//!
9//! Conventions the structurer relies on (see `docs/CONTRACT.md`):
10//! * `succ[0]` is the fall-through successor of a conditional terminator,
11//! `succ[1]` the taken one.
12//! * `BlockResult`s are indexed by block id.
13//! * `exc_ranges[i]` pairs with the exception edges carrying `range == i`.
14
15#[derive(Debug, Clone)]
16pub struct Block {
17 pub id: usize,
18 /// First machine offset covered by this block (inclusive).
19 pub start: u32,
20 /// End offset (exclusive).
21 pub end: u32,
22 /// Number of machine instructions (or code units) in this block. `0`
23 /// marks a block with no code of its own — a structural stub the CFG
24 /// split produced (handler entries, empty ranges).
25 pub ins_len: u32,
26 /// Successor block ids. For a conditional branch: `[fallthrough, taken]`
27 /// (the structurer may reorder branches based on condition polarity).
28 pub succ: Vec<usize>,
29 pub pred: Vec<usize>,
30 /// Exception-range indices this block is the HANDLER of (index into
31 /// `Cfg::exc_ranges`) — the structurer's try reconstruction reads those,
32 /// not source blocks.
33 pub handlers: Vec<u32>,
34}
35
36impl Block {
37 /// True if the block ends with a conditional branch (two successors).
38 pub fn ends_cond(&self) -> bool {
39 matches!(self.succ.len(), 2)
40 }
41
42 /// True if the block cannot fall through anywhere (a return/throw/
43 /// goto-only ending as far as the graph is concerned).
44 pub fn is_exit(&self) -> bool {
45 self.succ.is_empty()
46 }
47}
48
49/// One exception-table entry: `[start, end)` is protected, `handler` catches.
50#[derive(Debug, Clone)]
51pub struct ExcRange {
52 pub start: u32,
53 pub end: u32,
54 pub handler: u32,
55 /// `None` = catch-all (the source form is usually `finally`).
56 pub catch_type: Option<String>,
57}
58
59/// An edge from a protected region to its handler.
60#[derive(Debug, Clone)]
61pub struct ExcEdge {
62 /// Index into [`Cfg::exc_ranges`].
63 pub range: usize,
64 pub from: usize,
65 pub to: usize,
66}
67
68pub struct Cfg {
69 pub blocks: Vec<Block>,
70 pub entry: usize,
71 pub exc_edges: Vec<ExcEdge>,
72 pub exc_ranges: Vec<ExcRange>,
73 /// Sorted block start offsets, for `block_at`.
74 starts: Vec<u32>,
75}
76
77impl Cfg {
78 /// Assemble a CFG from front-end-built blocks. Predecessor lists, handler
79 /// lists and exception edges are derived here so a front-end only has to
80 /// state successors and exception ranges.
81 pub fn from_blocks(blocks: Vec<Block>, entry: usize, exc_ranges: Vec<ExcRange>) -> Cfg {
82 let mut blocks = blocks;
83 // Predecessors.
84 for b in blocks.iter_mut() {
85 b.pred.clear();
86 b.handlers.clear();
87 }
88 for i in 0..blocks.len() {
89 let succ = blocks[i].succ.clone();
90 for s in succ {
91 if s < blocks.len() {
92 blocks[s].pred.push(i);
93 }
94 }
95 }
96 // Handler back-references, with jcdc's exact semantics:
97 // * `Block.handlers` lists the exception-RANGE indices this block is
98 // the handler of (the structurer's try reconstruction reads range
99 // indices, not source blocks);
100 // * a block is protected by a range when its FIRST offset lies inside
101 // `[start, end)` — using `start < end` (not `end <= end`) keeps
102 // blocks whose trailing return/throw sits exactly on the boundary
103 // (`try { return f(); } catch ..` — the call is protected, the
104 // areturn lands on `end` and can still reach the loop header
105 // through the handler, which loop membership must see).
106 let mut exc_edges = Vec::new();
107 for (ri, r) in exc_ranges.iter().enumerate() {
108 let handler = blocks.iter().position(|b| b.start == r.handler);
109 if let Some(h) = handler {
110 blocks[h].handlers.push(ri as u32);
111 }
112 for b in blocks.iter() {
113 if b.start >= r.start && b.start < r.end && b.ins_len != 0 {
114 if let Some(h) = handler {
115 exc_edges.push(ExcEdge {
116 range: ri,
117 from: b.id,
118 to: h,
119 });
120 }
121 }
122 }
123 }
124 for b in blocks.iter_mut() {
125 b.pred.sort_unstable();
126 b.pred.dedup();
127 b.handlers.sort_unstable();
128 b.handlers.dedup();
129 }
130 let mut starts: Vec<u32> = blocks.iter().map(|b| b.start).collect();
131 starts.sort_unstable();
132 if crate::dbg_flag!("JCDC_DBG_CORE_CFG") {
133 for b in &blocks {
134 eprintln!(
135 "CORE_CFG b={} start={} end={} ins_len={} succ={:?} pred={:?} handlers={:?}",
136 b.id, b.start, b.end, b.ins_len, b.succ, b.pred, b.handlers
137 );
138 }
139 for (i, r) in exc_ranges.iter().enumerate() {
140 eprintln!(
141 "CORE_EXC r={} {}..{} -> {} type={:?}",
142 i, r.start, r.end, r.handler, r.catch_type
143 );
144 }
145 for e in &exc_edges {
146 eprintln!("CORE_EDGE r={} from={} to={}", e.range, e.from, e.to);
147 }
148 }
149 Cfg {
150 blocks,
151 entry,
152 exc_edges,
153 exc_ranges,
154 starts,
155 }
156 }
157
158 /// Assemble a CFG from blocks the caller has **already filled in**:
159 /// `pred` and `handlers` are taken as given and `exc_edges` is supplied,
160 /// so no derivation runs.
161 ///
162 /// This is the constructor for a front-end that is mirroring a graph it
163 /// already maintains (jcdc's `Cfg::to_core`): the derivation above would
164 /// only be thrown away, and at four to five snapshots per method that
165 /// waste — plus the allocate-then-replace churn of the derived lists —
166 /// is measurable.
167 pub fn from_parts(
168 blocks: Vec<Block>,
169 entry: usize,
170 exc_ranges: Vec<ExcRange>,
171 exc_edges: Vec<ExcEdge>,
172 ) -> Cfg {
173 let mut starts: Vec<u32> = blocks.iter().map(|b| b.start).collect();
174 starts.sort_unstable();
175 Cfg {
176 blocks,
177 entry,
178 exc_edges,
179 exc_ranges,
180 starts,
181 }
182 }
183
184 /// Block containing machine offset `p`.
185 pub fn block_at(&self, p: u32) -> Option<usize> {
186 let i = self.starts.partition_point(|&l| l <= p);
187 if i == 0 {
188 None
189 } else {
190 Some(i - 1)
191 }
192 }
193
194 /// Number of blocks.
195 pub fn len(&self) -> usize {
196 self.blocks.len()
197 }
198
199 pub fn is_empty(&self) -> bool {
200 self.blocks.is_empty()
201 }
202
203 /// Index of the first block whose start >= `p` (starts are sorted).
204 pub fn starts_partition(&self, p: u32) -> usize {
205 self.starts.partition_point(|&l| l < p)
206 }
207
208 /// True if `p` starts a block.
209 pub fn is_block_start(&self, p: u32) -> bool {
210 self.starts.binary_search(&p).is_ok()
211 }
212}
213
214#[cfg(test)]
215mod tests {
216 use super::*;
217
218 fn blk(id: usize, start: u32, len: u32, succ: Vec<usize>) -> Block {
219 Block {
220 id,
221 start,
222 end: start + len,
223 ins_len: len,
224 succ,
225 pred: Vec::new(),
226 handlers: Vec::new(),
227 }
228 }
229
230 #[test]
231 fn preds_and_handlers_are_derived() {
232 // 0 → 1 → 2, with 2 throwing into 3.
233 let cfg = Cfg::from_blocks(
234 vec![
235 blk(0, 0, 2, vec![1]),
236 blk(1, 2, 2, vec![2]),
237 blk(2, 4, 2, vec![]),
238 blk(3, 6, 1, vec![]),
239 ],
240 0,
241 vec![ExcRange {
242 start: 0,
243 end: 6,
244 handler: 6,
245 catch_type: Some("java/lang/Throwable".into()),
246 }],
247 );
248 assert_eq!(cfg.blocks[1].pred, vec![0]);
249 assert_eq!(cfg.blocks[2].pred, vec![1]);
250 assert_eq!(cfg.blocks[3].pred, Vec::<usize>::new());
251 // `handlers` holds the exception-RANGE indices this block handles;
252 // the protected side is `exc_edges[..].from`.
253 assert_eq!(cfg.blocks[3].handlers, vec![0]);
254 assert_eq!(cfg.exc_edges.len(), 3);
255 assert!(cfg.exc_edges.iter().all(|e| e.range == 0 && e.to == 3));
256 assert!(cfg.block_at(3) == Some(1));
257 assert!(cfg.block_at(6) == Some(3));
258 assert!(cfg.is_block_start(4) && !cfg.is_block_start(5));
259 }
260}