1use crate::vm::{CompiledProgram, Op, Reg};
25
26#[derive(Clone, Copy, PartialEq, Eq, Debug)]
28pub enum SiteKind {
29 NoMem,
31 Alloc,
33 StaticStream,
35 StaticField,
37 IndexedBy(Reg),
40 DynamicHash,
42 Coprocessor,
44}
45
46pub fn site_kind(op: &Op) -> SiteKind {
48 use SiteKind::*;
49 match op {
50 Op::LoadConst { .. }
52 | Op::Move { .. }
53 | Op::RevSwap { .. }
54 | Op::RevXor { .. }
55 | Op::RevNeg { .. }
56 | Op::RevAdd { .. }
57 | Op::RevSub { .. }
58 | Op::Add { .. }
59 | Op::BigIntWide { .. }
60 | Op::AddAssign { .. }
61 | Op::Sub { .. }
62 | Op::Mul { .. }
63 | Op::Div { .. }
64 | Op::ExactDiv { .. }
65 | Op::FloorDiv { .. }
66 | Op::Mod { .. }
67 | Op::DivPow2 { .. }
68 | Op::MagicDivU { .. }
69 | Op::Lt { .. }
70 | Op::Gt { .. }
71 | Op::LtEq { .. }
72 | Op::GtEq { .. }
73 | Op::Eq { .. }
74 | Op::ApproxEq { .. }
75 | Op::NotEq { .. }
76 | Op::Not { .. }
77 | Op::Pow { .. }
78 | Op::BitXor { .. }
79 | Op::BitAnd { .. }
80 | Op::BitOr { .. }
81 | Op::Shl { .. }
82 | Op::Shr { .. }
83 | Op::Jump { .. }
84 | Op::JumpIfFalse { .. }
85 | Op::JumpIfTrue { .. }
86 | Op::Call { .. }
87 | Op::CallValue { .. }
88 | Op::Return { .. }
89 | Op::ReturnNothing
90 | Op::RegionBoundsGuard { .. }
91 | Op::IterPop
92 | Op::Halt => NoMem,
93
94 Op::NewList { .. }
96 | Op::NewEmptyList { .. }
97 | Op::NewEmptyListWithCapacity { .. }
98 | Op::NewEmptyListFixed { .. }
99 | Op::NewEmptyListI32 { .. }
100 | Op::NewEmptySet { .. }
101 | Op::NewEmptyMap { .. }
102 | Op::NewEmptyMapWithCapacity { .. }
103 | Op::NewRange { .. }
104 | Op::NewTuple { .. }
105 | Op::NewStruct { .. }
106 | Op::NewInductive { .. }
107 | Op::NewCrdt { .. }
108 | Op::Args { .. } => Alloc,
109
110 Op::ListPush { .. }
112 | Op::ListPop { .. }
113 | Op::ListPushField { .. }
114 | Op::Concat { .. }
115 | Op::SeqConcat { .. }
116 | Op::SliceOp { .. }
117 | Op::DeepClone { .. }
118 | Op::EnsureOwned { .. }
119 | Op::MakeClosure { .. }
120 | Op::FormatValue { .. }
121 | Op::DestructureTuple { .. }
122 | Op::IterPrepare { .. }
123 | Op::IterNext { .. }
124 | Op::CrdtAppend { .. }
125 | Op::CrdtMerge { .. }
126 | Op::CrdtJoin { .. } => StaticStream,
127
128 Op::GlobalGet { .. }
130 | Op::GlobalSet { .. }
131 | Op::GetField { .. }
132 | Op::StructInsert { .. }
133 | Op::TestArm { .. }
134 | Op::BindArm { .. }
135 | Op::Length { .. }
136 | Op::CrdtBump { .. }
137 | Op::CrdtResolve { .. } => StaticField,
138
139 Op::Index { index, .. }
141 | Op::IndexUnchecked { index, .. }
142 | Op::SetIndex { index, .. }
143 | Op::SetIndexUnchecked { index, .. } => IndexedBy(*index),
144
145 Op::SetAdd { .. }
147 | Op::RemoveFrom { .. }
148 | Op::Contains { .. }
149 | Op::UnionOp { .. }
150 | Op::IntersectOp { .. } => DynamicHash,
151
152 Op::CallBuiltin { .. }
154 | Op::CheckPolicy { .. }
155 | Op::LoadToday { .. }
156 | Op::LoadNow { .. }
157 | Op::Sleep { .. }
158 | Op::Show { .. }
159 | Op::Obs { .. }
160 | Op::FailWith { .. }
161 | Op::ChanNew { .. }
162 | Op::ChanSend { .. }
163 | Op::ChanRecv { .. }
164 | Op::ChanTrySend { .. }
165 | Op::ChanTryRecv { .. }
166 | Op::ChanClose { .. }
167 | Op::Spawn { .. }
168 | Op::SpawnHandle { .. }
169 | Op::TaskAwait { .. }
170 | Op::TaskAbort { .. }
171 | Op::SelectArmRecv { .. }
172 | Op::SelectArmTimeout { .. }
173 | Op::SelectWait { .. }
174 | Op::NetConnect { .. }
175 | Op::NetListen { .. }
176 | Op::NetSend { .. }
177 | Op::NetStream { .. }
178 | Op::NetAwait { .. }
179 | Op::NetMakePeer { .. }
180 | Op::NetSync { .. }
181 | Op::Tcp { .. }
182 | Op::Serve { .. } => Coprocessor,
183 }
184}
185
186#[derive(Clone, Copy, PartialEq, Eq, Debug)]
194pub enum RegClass {
195 StaticAddr,
198 Opaque,
200}
201
202fn segments(prog: &CompiledProgram) -> Vec<(usize, usize)> {
204 let mut entries: Vec<usize> = prog.functions.iter().map(|c| c.entry_pc).collect();
205 entries.sort_unstable();
206 entries.dedup();
207 let mut segs = Vec::new();
208 let first = entries.first().copied().unwrap_or(prog.code.len());
209 segs.push((0, first)); for (i, &e) in entries.iter().enumerate() {
211 let end = entries.get(i + 1).copied().unwrap_or(prog.code.len());
212 segs.push((e, end));
213 }
214 segs
215}
216
217fn alu_reads(op: &Op) -> Option<(Reg, Vec<Reg>)> {
220 let two = |dst: &Reg, lhs: &Reg, rhs: &Reg| Some((*dst, vec![*lhs, *rhs]));
221 match op {
222 Op::LoadConst { dst, .. } => Some((*dst, vec![])),
223 Op::Move { dst, src } => Some((*dst, vec![*src])),
224 Op::Length { dst, .. } => Some((*dst, vec![])),
226 Op::Add { dst, lhs, rhs }
227 | Op::Sub { dst, lhs, rhs }
228 | Op::Mul { dst, lhs, rhs }
229 | Op::Div { dst, lhs, rhs }
230 | Op::ExactDiv { dst, lhs, rhs }
231 | Op::FloorDiv { dst, lhs, rhs }
232 | Op::Mod { dst, lhs, rhs }
233 | Op::Pow { dst, lhs, rhs }
234 | Op::BitXor { dst, lhs, rhs }
235 | Op::BitAnd { dst, lhs, rhs }
236 | Op::BitOr { dst, lhs, rhs }
237 | Op::Shl { dst, lhs, rhs }
238 | Op::Shr { dst, lhs, rhs }
239 | Op::Lt { dst, lhs, rhs }
240 | Op::Gt { dst, lhs, rhs }
241 | Op::LtEq { dst, lhs, rhs }
242 | Op::GtEq { dst, lhs, rhs }
243 | Op::Eq { dst, lhs, rhs }
244 | Op::NotEq { dst, lhs, rhs } => two(dst, lhs, rhs),
245 Op::AddAssign { dst, src } => Some((*dst, vec![*src])),
246 Op::Not { dst, src } => Some((*dst, vec![*src])),
247 Op::DivPow2 { dst, lhs, .. } => Some((*dst, vec![*lhs])),
248 Op::MagicDivU { dst, lhs, .. } => Some((*dst, vec![*lhs])),
249 Op::RevAdd { place, delta } | Op::RevSub { place, delta } | Op::RevXor { place, delta } => {
250 Some((*place, vec![*delta]))
251 }
252 Op::RevNeg { place } => Some((*place, vec![])),
253 _ => None,
254 }
255}
256
257fn successors(code: &[Op], lo: usize, hi: usize, pc: usize) -> Vec<usize> {
259 let in_seg = |t: usize| if t >= lo && t < hi { Some(t) } else { None };
260 match &code[pc] {
261 Op::Jump { target } => in_seg(*target).into_iter().collect(),
262 Op::JumpIfFalse { target, .. } | Op::JumpIfTrue { target, .. } => {
263 let mut s: Vec<usize> = in_seg(*target).into_iter().collect();
264 if pc + 1 < hi {
265 s.push(pc + 1);
266 }
267 s
268 }
269 Op::IterNext { exit, .. } => {
270 let mut s: Vec<usize> = in_seg(*exit).into_iter().collect();
271 if pc + 1 < hi {
272 s.push(pc + 1);
273 }
274 s
275 }
276 Op::Return { .. } | Op::ReturnNothing | Op::Halt | Op::FailWith { .. } => Vec::new(),
277 _ => {
278 if pc + 1 < hi {
279 vec![pc + 1]
280 } else {
281 Vec::new()
282 }
283 }
284 }
285}
286
287struct SegmentFlow {
296 def_static: Vec<bool>,
298 reaching_in: Vec<Vec<u64>>,
300 defs_of_reg: Vec<Vec<u32>>, lo: usize,
302}
303
304impl SegmentFlow {
305 fn build(code: &[Op], lo: usize, hi: usize) -> SegmentFlow {
306 let mut def_at: Vec<(usize, Reg)> = Vec::new();
308 let mut def_reads: Vec<Option<Vec<Reg>>> = Vec::new(); let mut max_reg = 0usize;
310 for pc in lo..hi {
311 let op = &code[pc];
312 match (alu_reads(op), op) {
313 (_, Op::RevSwap { a, b }) => {
314 for r in [*a, *b] {
315 def_at.push((pc, r));
316 def_reads.push(None);
317 max_reg = max_reg.max(r as usize + 1);
318 }
319 }
320 (Some((dst, reads)), _) => {
321 for &r in &reads {
322 max_reg = max_reg.max(r as usize + 1);
323 }
324 max_reg = max_reg.max(dst as usize + 1);
325 def_at.push((pc, dst));
326 def_reads.push(Some(reads));
327 }
328 (None, other) => {
329 other.for_each_written_reg(|r| {
330 def_at.push((pc, r));
331 def_reads.push(None);
332 max_reg = max_reg.max(r as usize + 1);
333 });
334 }
335 }
336 if let SiteKind::IndexedBy(r) = site_kind(op) {
337 max_reg = max_reg.max(r as usize + 1);
338 }
339 }
340 let ndefs = def_at.len();
341 let words = ndefs.div_ceil(64).max(1);
342 let mut defs_of_reg: Vec<Vec<u32>> = vec![Vec::new(); max_reg];
343 for (id, &(_, r)) in def_at.iter().enumerate() {
344 defs_of_reg[r as usize].push(id as u32);
345 }
346
347 let n = hi - lo;
349 let mut r_in: Vec<Vec<u64>> = vec![vec![0; words]; n];
350 let mut r_out: Vec<Vec<u64>> = vec![vec![0; words]; n];
351 let mut gen: Vec<Vec<u32>> = vec![Vec::new(); n];
353 for (id, &(pc, _)) in def_at.iter().enumerate() {
354 gen[pc - lo].push(id as u32);
355 }
356 let mut preds: Vec<Vec<usize>> = vec![Vec::new(); n];
358 for p in lo..hi {
359 for s in successors(code, lo, hi, p) {
360 preds[s - lo].push(p);
361 }
362 }
363 let mut changed = true;
364 while changed {
365 changed = false;
366 for pc in lo..hi {
367 let i = pc - lo;
368 let mut newin = vec![0u64; words];
369 for &p in &preds[i] {
370 for w in 0..words {
371 newin[w] |= r_out[p - lo][w];
372 }
373 }
374 if newin != r_in[i] {
375 r_in[i] = newin;
376 changed = true;
377 }
378 let mut newout = r_in[i].clone();
380 for &id in &gen[i] {
381 let (_, reg) = def_at[id as usize];
382 for &k in &defs_of_reg[reg as usize] {
383 newout[(k / 64) as usize] &= !(1u64 << (k % 64));
384 }
385 }
386 for &id in &gen[i] {
387 newout[(id / 64) as usize] |= 1u64 << (id % 64);
388 }
389 if newout != r_out[i] {
390 r_out[i] = newout;
391 changed = true;
392 }
393 }
394 }
395
396 let mut def_static: Vec<bool> = def_reads.iter().map(|d| d.is_some()).collect();
398 let reach = |r_in: &Vec<Vec<u64>>, pc: usize, reg: Reg| -> Vec<u32> {
399 defs_of_reg
400 .get(reg as usize)
401 .map(|ids| {
402 ids.iter()
403 .copied()
404 .filter(|&id| r_in[pc - lo][(id / 64) as usize] & (1u64 << (id % 64)) != 0)
405 .collect()
406 })
407 .unwrap_or_default()
408 };
409 let mut demoted = true;
410 while demoted {
411 demoted = false;
412 for id in 0..ndefs {
413 if !def_static[id] {
414 continue;
415 }
416 let (pc, _) = def_at[id];
417 let Some(reads) = &def_reads[id] else {
418 unreachable!()
419 };
420 let ok = reads.iter().all(|&o| {
421 let rd = reach(&r_in, pc, o);
422 !rd.is_empty() && rd.iter().all(|&d| def_static[d as usize])
423 });
424 if !ok {
425 def_static[id] = false;
426 demoted = true;
427 }
428 }
429 }
430
431 SegmentFlow {
432 def_static,
433 reaching_in: r_in,
434 defs_of_reg,
435 lo,
436 }
437 }
438
439 fn static_at(&self, pc: usize, r: Reg) -> bool {
441 let Some(ids) = self.defs_of_reg.get(r as usize) else {
442 return false;
443 };
444 let row = &self.reaching_in[pc - self.lo];
445 let mut any = false;
446 for &id in ids {
447 if row[(id / 64) as usize] & (1u64 << (id % 64)) != 0 {
448 any = true;
449 if !self.def_static[id as usize] {
450 return false;
451 }
452 }
453 }
454 any
455 }
456}
457
458#[derive(Clone, Debug, Default)]
460pub struct MemSchedReport {
461 pub static_sites: usize,
463 pub dynamic_sites: usize,
465 pub coprocessor_sites: usize,
467 pub nomem_sites: usize,
469}
470
471impl MemSchedReport {
472 pub fn datapath_sites(&self) -> usize {
473 self.static_sites + self.dynamic_sites
474 }
475 pub fn static_fraction(&self) -> f64 {
478 let d = self.datapath_sites();
479 if d == 0 {
480 1.0
481 } else {
482 self.static_sites as f64 / d as f64
483 }
484 }
485}
486
487pub fn analyze(prog: &CompiledProgram) -> MemSchedReport {
490 let mut report = MemSchedReport::default();
491 for (lo, hi) in segments(prog) {
492 if lo >= hi {
493 continue;
494 }
495 let flow = SegmentFlow::build(&prog.code, lo, hi);
496 for (i, op) in prog.code[lo..hi].iter().enumerate() {
497 match site_kind(op) {
498 SiteKind::NoMem => report.nomem_sites += 1,
499 SiteKind::Alloc | SiteKind::StaticStream | SiteKind::StaticField => {
500 report.static_sites += 1
501 }
502 SiteKind::DynamicHash => report.dynamic_sites += 1,
503 SiteKind::Coprocessor => report.coprocessor_sites += 1,
504 SiteKind::IndexedBy(r) => {
505 if flow.static_at(lo + i, r) {
506 report.static_sites += 1
507 } else {
508 report.dynamic_sites += 1
509 }
510 }
511 }
512 }
513 }
514 report
515}
516
517#[derive(Clone, Debug, Default)]
523pub struct CachePlan {
524 pub prefetch: Vec<usize>,
525 pub probe: Vec<usize>,
526}
527
528impl CachePlan {
529 pub fn is_total_over(&self, report: &MemSchedReport) -> bool {
531 self.prefetch.len() == report.static_sites
532 && self.probe.len() == report.dynamic_sites
533 && self.prefetch.len() + self.probe.len() == report.datapath_sites()
534 }
535}
536
537pub fn cache_plan(prog: &CompiledProgram) -> CachePlan {
542 let mut plan = CachePlan::default();
543 for (lo, hi) in segments(prog) {
544 if lo >= hi {
545 continue;
546 }
547 let flow = SegmentFlow::build(&prog.code, lo, hi);
548 for (i, op) in prog.code[lo..hi].iter().enumerate() {
549 let pc = lo + i;
550 match site_kind(op) {
551 SiteKind::Alloc | SiteKind::StaticStream | SiteKind::StaticField => {
552 plan.prefetch.push(pc)
553 }
554 SiteKind::DynamicHash => plan.probe.push(pc),
555 SiteKind::IndexedBy(r) => {
556 if flow.static_at(pc, r) {
557 plan.prefetch.push(pc)
558 } else {
559 plan.probe.push(pc)
560 }
561 }
562 SiteKind::NoMem | SiteKind::Coprocessor => {}
563 }
564 }
565 }
566 plan
567}
568
569pub fn explain_dynamic_sites(prog: &CompiledProgram, limit: usize) -> String {
573 let mut out = String::new();
574 for (lo, hi) in segments(prog) {
575 if lo >= hi {
576 continue;
577 }
578 let flow = SegmentFlow::build(&prog.code, lo, hi);
579 for (pc, op) in prog.code[lo..hi].iter().enumerate() {
580 let dynamic = match site_kind(op) {
581 SiteKind::DynamicHash => Some(None),
582 SiteKind::IndexedBy(r) if !flow.static_at(lo + pc, r) => Some(Some(r)),
583 _ => None,
584 };
585 let Some(index_reg) = dynamic else { continue };
586 out.push_str(&format!("pc {} {}", lo + pc, op.name()));
587 if let Some(r) = index_reg {
588 out.push_str(&format!(" index=r{r} writes=["));
589 for (wpc, wop) in prog.code[lo..hi].iter().enumerate() {
590 let mut hits = false;
591 wop.for_each_written_reg(|w| hits |= w == r);
592 if hits {
593 out.push_str(&format!("{}@{} ", wop.name(), lo + wpc));
594 }
595 }
596 out.push(']');
597 }
598 out.push('\n');
599 if out.lines().count() >= limit {
600 return out;
601 }
602 }
603 }
604 out
605}
606
607#[cfg(test)]
608#[path = "../../../logicaffeine_tests/unit/logicaffeine_compile/codegen_sva/memsched/tests.rs"]
609mod tests;