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 { range: ri, from: b.id, to: h });
116 }
117 }
118 }
119 }
120 for b in blocks.iter_mut() {
121 b.pred.sort_unstable();
122 b.pred.dedup();
123 b.handlers.sort_unstable();
124 b.handlers.dedup();
125 }
126 let mut starts: Vec<u32> = blocks.iter().map(|b| b.start).collect();
127 starts.sort_unstable();
128 if crate::dbg_flag!("JCDC_DBG_CORE_CFG") {
129 for b in &blocks {
130 eprintln!(
131 "CORE_CFG b={} start={} end={} ins_len={} succ={:?} pred={:?} handlers={:?}",
132 b.id, b.start, b.end, b.ins_len, b.succ, b.pred, b.handlers
133 );
134 }
135 for (i, r) in exc_ranges.iter().enumerate() {
136 eprintln!("CORE_EXC r={} {}..{} -> {} type={:?}", i, r.start, r.end, r.handler, r.catch_type);
137 }
138 for e in &exc_edges {
139 eprintln!("CORE_EDGE r={} from={} to={}", e.range, e.from, e.to);
140 }
141 }
142 Cfg { blocks, entry, exc_edges, exc_ranges, starts }
143 }
144
145 /// Assemble a CFG from blocks the caller has **already filled in**:
146 /// `pred` and `handlers` are taken as given and `exc_edges` is supplied,
147 /// so no derivation runs.
148 ///
149 /// This is the constructor for a front-end that is mirroring a graph it
150 /// already maintains (jcdc's `Cfg::to_core`): the derivation above would
151 /// only be thrown away, and at four to five snapshots per method that
152 /// waste — plus the allocate-then-replace churn of the derived lists —
153 /// is measurable.
154 pub fn from_parts(
155 blocks: Vec<Block>,
156 entry: usize,
157 exc_ranges: Vec<ExcRange>,
158 exc_edges: Vec<ExcEdge>,
159 ) -> Cfg {
160 let mut starts: Vec<u32> = blocks.iter().map(|b| b.start).collect();
161 starts.sort_unstable();
162 Cfg { blocks, entry, exc_edges, exc_ranges, starts }
163 }
164
165 /// Block containing machine offset `p`.
166 pub fn block_at(&self, p: u32) -> Option<usize> {
167 let i = self.starts.partition_point(|&l| l <= p);
168 if i == 0 {
169 None
170 } else {
171 Some(i - 1)
172 }
173 }
174
175 /// Number of blocks.
176 pub fn len(&self) -> usize {
177 self.blocks.len()
178 }
179
180 pub fn is_empty(&self) -> bool {
181 self.blocks.is_empty()
182 }
183
184 /// Index of the first block whose start >= `p` (starts are sorted).
185 pub fn starts_partition(&self, p: u32) -> usize {
186 self.starts.partition_point(|&l| l < p)
187 }
188
189 /// True if `p` starts a block.
190 pub fn is_block_start(&self, p: u32) -> bool {
191 self.starts.binary_search(&p).is_ok()
192 }
193}
194
195#[cfg(test)]
196mod tests {
197 use super::*;
198
199 fn blk(id: usize, start: u32, len: u32, succ: Vec<usize>) -> Block {
200 Block {
201 id,
202 start,
203 end: start + len,
204 ins_len: len,
205 succ,
206 pred: Vec::new(),
207 handlers: Vec::new(),
208 }
209 }
210
211 #[test]
212 fn preds_and_handlers_are_derived() {
213 // 0 → 1 → 2, with 2 throwing into 3.
214 let cfg = Cfg::from_blocks(
215 vec![blk(0, 0, 2, vec![1]), blk(1, 2, 2, vec![2]), blk(2, 4, 2, vec![]), blk(3, 6, 1, vec![])],
216 0,
217 vec![ExcRange { start: 0, end: 6, handler: 6, catch_type: Some("java/lang/Throwable".into()) }],
218 );
219 assert_eq!(cfg.blocks[1].pred, vec![0]);
220 assert_eq!(cfg.blocks[2].pred, vec![1]);
221 assert_eq!(cfg.blocks[3].pred, Vec::<usize>::new());
222 // `handlers` holds the exception-RANGE indices this block handles;
223 // the protected side is `exc_edges[..].from`.
224 assert_eq!(cfg.blocks[3].handlers, vec![0]);
225 assert_eq!(cfg.exc_edges.len(), 3);
226 assert!(cfg.exc_edges.iter().all(|e| e.range == 0 && e.to == 3));
227 assert!(cfg.block_at(3) == Some(1));
228 assert!(cfg.block_at(6) == Some(3));
229 assert!(cfg.is_block_start(4) && !cfg.is_block_start(5));
230 }
231}