1use super::defs::*;
6use super::impls2::*;
7use crate::c_backend::{self, CEmitConfig, COutput};
8use crate::closure_convert::{ClosureConvertConfig, ClosureConverter};
9use crate::lcnf::*;
10use crate::native_backend::{self, NativeEmitConfig, NativeModule};
11use crate::opt_dce::{self, DceConfig};
12use crate::to_lcnf::{self, ToLcnfConfig};
13use crate::CodegenTarget;
14use oxilean_kernel::expr::Expr;
15use oxilean_kernel::Name;
16
17use super::super::functions::LcnfDeclInput;
18
19use super::super::functions::*;
20use std::collections::{HashMap, HashSet, VecDeque};
21
22#[allow(dead_code)]
23#[derive(Debug, Clone, Default)]
24pub struct PipePassStats {
25 pub total_runs: u32,
26 pub successful_runs: u32,
27 pub total_changes: u64,
28 pub time_ms: u64,
29 pub iterations_used: u32,
30}
31impl PipePassStats {
32 #[allow(dead_code)]
33 pub fn new() -> Self {
34 Self::default()
35 }
36 #[allow(dead_code)]
37 pub fn record_run(&mut self, changes: u64, time_ms: u64, iterations: u32) {
38 self.total_runs += 1;
39 self.successful_runs += 1;
40 self.total_changes += changes;
41 self.time_ms += time_ms;
42 self.iterations_used = iterations;
43 }
44 #[allow(dead_code)]
45 pub fn average_changes_per_run(&self) -> f64 {
46 if self.total_runs == 0 {
47 return 0.0;
48 }
49 self.total_changes as f64 / self.total_runs as f64
50 }
51 #[allow(dead_code)]
52 pub fn success_rate(&self) -> f64 {
53 if self.total_runs == 0 {
54 return 0.0;
55 }
56 self.successful_runs as f64 / self.total_runs as f64
57 }
58 #[allow(dead_code)]
59 pub fn format_summary(&self) -> String {
60 format!(
61 "Runs: {}/{}, Changes: {}, Time: {}ms",
62 self.successful_runs, self.total_runs, self.total_changes, self.time_ms
63 )
64 }
65}
66#[allow(dead_code)]
68#[derive(Debug, Default)]
69pub struct PipeExtPassRegistry {
70 pub(crate) configs: Vec<PipeExtPassConfig>,
71 pub(crate) stats: Vec<PipeExtPassStats>,
72}
73impl PipeExtPassRegistry {
74 #[allow(dead_code)]
75 pub fn new() -> Self {
76 Self::default()
77 }
78 #[allow(dead_code)]
79 pub fn register(&mut self, c: PipeExtPassConfig) {
80 self.stats.push(PipeExtPassStats::new());
81 self.configs.push(c);
82 }
83 #[allow(dead_code)]
84 pub fn len(&self) -> usize {
85 self.configs.len()
86 }
87 #[allow(dead_code)]
88 pub fn is_empty(&self) -> bool {
89 self.configs.is_empty()
90 }
91 #[allow(dead_code)]
92 pub fn get(&self, i: usize) -> Option<&PipeExtPassConfig> {
93 self.configs.get(i)
94 }
95 #[allow(dead_code)]
96 pub fn get_stats(&self, i: usize) -> Option<&PipeExtPassStats> {
97 self.stats.get(i)
98 }
99 #[allow(dead_code)]
100 pub fn enabled_passes(&self) -> Vec<&PipeExtPassConfig> {
101 self.configs.iter().filter(|c| c.enabled).collect()
102 }
103 #[allow(dead_code)]
104 pub fn passes_in_phase(&self, ph: &PipeExtPassPhase) -> Vec<&PipeExtPassConfig> {
105 self.configs
106 .iter()
107 .filter(|c| c.enabled && &c.phase == ph)
108 .collect()
109 }
110 #[allow(dead_code)]
111 pub fn total_nodes_visited(&self) -> usize {
112 self.stats.iter().map(|s| s.nodes_visited).sum()
113 }
114 #[allow(dead_code)]
115 pub fn any_changed(&self) -> bool {
116 self.stats.iter().any(|s| s.changed)
117 }
118}
119#[allow(dead_code)]
121#[derive(Debug, Clone, PartialEq, Eq, Hash)]
122pub enum PipeX2PassPhase {
123 Early,
124 Middle,
125 Late,
126 Finalize,
127}
128impl PipeX2PassPhase {
129 #[allow(dead_code)]
130 pub fn is_early(&self) -> bool {
131 matches!(self, Self::Early)
132 }
133 #[allow(dead_code)]
134 pub fn is_middle(&self) -> bool {
135 matches!(self, Self::Middle)
136 }
137 #[allow(dead_code)]
138 pub fn is_late(&self) -> bool {
139 matches!(self, Self::Late)
140 }
141 #[allow(dead_code)]
142 pub fn is_finalize(&self) -> bool {
143 matches!(self, Self::Finalize)
144 }
145 #[allow(dead_code)]
146 pub fn order(&self) -> u32 {
147 match self {
148 Self::Early => 0,
149 Self::Middle => 1,
150 Self::Late => 2,
151 Self::Finalize => 3,
152 }
153 }
154 #[allow(dead_code)]
155 pub fn from_order(n: u32) -> Option<Self> {
156 match n {
157 0 => Some(Self::Early),
158 1 => Some(Self::Middle),
159 2 => Some(Self::Late),
160 3 => Some(Self::Finalize),
161 _ => None,
162 }
163 }
164}
165#[allow(dead_code)]
166#[derive(Debug, Clone)]
167pub struct PipeWorklist {
168 pub(crate) items: std::collections::VecDeque<u32>,
169 pub(crate) in_worklist: std::collections::HashSet<u32>,
170}
171impl PipeWorklist {
172 #[allow(dead_code)]
173 pub fn new() -> Self {
174 PipeWorklist {
175 items: std::collections::VecDeque::new(),
176 in_worklist: std::collections::HashSet::new(),
177 }
178 }
179 #[allow(dead_code)]
180 pub fn push(&mut self, item: u32) -> bool {
181 if self.in_worklist.insert(item) {
182 self.items.push_back(item);
183 true
184 } else {
185 false
186 }
187 }
188 #[allow(dead_code)]
189 pub fn pop(&mut self) -> Option<u32> {
190 let item = self.items.pop_front()?;
191 self.in_worklist.remove(&item);
192 Some(item)
193 }
194 #[allow(dead_code)]
195 pub fn is_empty(&self) -> bool {
196 self.items.is_empty()
197 }
198 #[allow(dead_code)]
199 pub fn len(&self) -> usize {
200 self.items.len()
201 }
202 #[allow(dead_code)]
203 pub fn contains(&self, item: u32) -> bool {
204 self.in_worklist.contains(&item)
205 }
206}
207#[allow(dead_code)]
208pub struct PipeConstantFoldingHelper;
209impl PipeConstantFoldingHelper {
210 #[allow(dead_code)]
211 pub fn fold_add_i64(a: i64, b: i64) -> Option<i64> {
212 a.checked_add(b)
213 }
214 #[allow(dead_code)]
215 pub fn fold_sub_i64(a: i64, b: i64) -> Option<i64> {
216 a.checked_sub(b)
217 }
218 #[allow(dead_code)]
219 pub fn fold_mul_i64(a: i64, b: i64) -> Option<i64> {
220 a.checked_mul(b)
221 }
222 #[allow(dead_code)]
223 pub fn fold_div_i64(a: i64, b: i64) -> Option<i64> {
224 if b == 0 {
225 None
226 } else {
227 a.checked_div(b)
228 }
229 }
230 #[allow(dead_code)]
231 pub fn fold_add_f64(a: f64, b: f64) -> f64 {
232 a + b
233 }
234 #[allow(dead_code)]
235 pub fn fold_mul_f64(a: f64, b: f64) -> f64 {
236 a * b
237 }
238 #[allow(dead_code)]
239 pub fn fold_neg_i64(a: i64) -> Option<i64> {
240 a.checked_neg()
241 }
242 #[allow(dead_code)]
243 pub fn fold_not_bool(a: bool) -> bool {
244 !a
245 }
246 #[allow(dead_code)]
247 pub fn fold_and_bool(a: bool, b: bool) -> bool {
248 a && b
249 }
250 #[allow(dead_code)]
251 pub fn fold_or_bool(a: bool, b: bool) -> bool {
252 a || b
253 }
254 #[allow(dead_code)]
255 pub fn fold_shl_i64(a: i64, b: u32) -> Option<i64> {
256 a.checked_shl(b)
257 }
258 #[allow(dead_code)]
259 pub fn fold_shr_i64(a: i64, b: u32) -> Option<i64> {
260 a.checked_shr(b)
261 }
262 #[allow(dead_code)]
263 pub fn fold_rem_i64(a: i64, b: i64) -> Option<i64> {
264 if b == 0 {
265 None
266 } else {
267 Some(a % b)
268 }
269 }
270 #[allow(dead_code)]
271 pub fn fold_bitand_i64(a: i64, b: i64) -> i64 {
272 a & b
273 }
274 #[allow(dead_code)]
275 pub fn fold_bitor_i64(a: i64, b: i64) -> i64 {
276 a | b
277 }
278 #[allow(dead_code)]
279 pub fn fold_bitxor_i64(a: i64, b: i64) -> i64 {
280 a ^ b
281 }
282 #[allow(dead_code)]
283 pub fn fold_bitnot_i64(a: i64) -> i64 {
284 !a
285 }
286}
287pub struct CompilerPipeline {
292 pub(crate) config: PipelineConfig,
293}
294impl CompilerPipeline {
295 pub fn new(config: PipelineConfig) -> Self {
297 CompilerPipeline { config }
298 }
299 pub fn default_pipeline() -> Self {
301 Self::new(PipelineConfig::default())
302 }
303 pub fn run_pipeline(
308 &self,
309 input: Vec<(Name, Expr, Expr)>,
310 config: &PipelineConfig,
311 ) -> PipelineResult {
312 let start_time = std::time::Instant::now();
313 let mut stats = PipelineStats::default();
314 let mut module = self.exprs_to_lcnf(&input);
315 stats.input_decls = module.fun_decls.len();
316 let passes = config.effective_passes();
317 let max_iter = config.effective_max_iterations();
318 if !passes.is_empty() {
319 module = self.iterate_to_fixpoint(module, &passes, max_iter, &mut stats);
320 }
321 stats.output_decls = module.fun_decls.len();
322 let mut result = PipelineResult {
323 c_output: None,
324 native_output: None,
325 lcnf_module: module.clone(),
326 stats: stats.clone(),
327 };
328 match config.target {
329 CodegenTarget::C => {
330 let c_config = CEmitConfig {
331 emit_comments: config.emit_comments,
332 ..CEmitConfig::default()
333 };
334 let c_output = c_backend::compile_to_c(&module, c_config);
335 result.c_output = Some(c_output);
336 }
337 CodegenTarget::LlvmIr | CodegenTarget::Rust => {
338 let native_config = NativeEmitConfig {
339 opt_level: config.opt_level.to_u8(),
340 debug_info: config.debug,
341 emit_comments: config.emit_comments,
342 ..NativeEmitConfig::default()
343 };
344 let mut backend = native_backend::NativeBackend::new(native_config);
345 let native_module = backend.compile_module(&module);
346 result.native_output = Some(native_module);
347 }
348 CodegenTarget::Interpreter => {}
349 }
350 result.stats.total_time_us = start_time.elapsed().as_micros() as u64;
351 result
352 }
353 pub(crate) fn exprs_to_lcnf(&self, input: &[(Name, Expr, Expr)]) -> LcnfModule {
359 if input.is_empty() {
360 return LcnfModule {
361 fun_decls: Vec::new(),
362 extern_decls: Vec::new(),
363 name: "compiled_module".to_string(),
364 metadata: LcnfModuleMetadata::default(),
365 };
366 }
367 let config = ToLcnfConfig::default();
368 let decls: Vec<LcnfDeclInput> = input
369 .iter()
370 .map(|(name, _ty, value)| {
371 let (params, body) = peel_lam_params(value);
372 (name.clone(), params, body)
373 })
374 .collect();
375 match to_lcnf::module_to_lcnf(&decls, &config) {
376 Ok(mut module) => {
377 module.name = "compiled_module".to_string();
378 module
379 }
380 Err(_err) => LcnfModule {
381 fun_decls: Vec::new(),
382 extern_decls: Vec::new(),
383 name: "compiled_module".to_string(),
384 metadata: LcnfModuleMetadata::default(),
385 },
386 }
387 }
388 pub fn iterate_to_fixpoint(
390 &self,
391 mut module: LcnfModule,
392 passes: &[PassId],
393 max_iters: usize,
394 stats: &mut PipelineStats,
395 ) -> LcnfModule {
396 for _iteration in 0..max_iters {
397 stats.iterations += 1;
398 let mut any_changed = false;
399 for pass_id in passes {
400 let result = self.run_pass(&module, pass_id);
401 stats.per_pass.push((pass_id.clone(), result.stats));
402 if result.changed {
403 any_changed = true;
404 }
405 module = result.module;
406 }
407 if !any_changed {
408 break;
409 }
410 }
411 module
412 }
413 pub fn run_pass(&self, module: &LcnfModule, pass_id: &PassId) -> PassResult {
415 let start = std::time::Instant::now();
416 let before_count = count_module_lets(module);
417 let (new_module, transformations) = match pass_id {
418 PassId::Dce => {
419 let dce_config = DceConfig {
420 max_iterations: 3,
421 ..DceConfig::default()
422 };
423 let (result, dce_stats) = opt_dce::optimize_dce(module, &dce_config);
424 (result, dce_stats.total_changes())
425 }
426 PassId::JoinPoints => {
427 let result = run_join_point_pass(module);
428 let after_count = count_module_lets(&result);
429 let changes = before_count.abs_diff(after_count);
430 (result, changes)
431 }
432 PassId::Specialize => {
433 let result = run_specialize_pass(module);
434 let after_count = count_module_lets(&result);
435 let changes = before_count.abs_diff(after_count);
436 (result, changes)
437 }
438 PassId::Reuse => {
439 let result = run_reuse_pass(module);
440 let after_count = count_module_lets(&result);
441 let changes = before_count.abs_diff(after_count);
442 (result, changes)
443 }
444 PassId::ClosureConvert => {
445 let mut result = module.clone();
446 let cc_config = ClosureConvertConfig::default();
447 let mut converter = ClosureConverter::new(cc_config);
448 converter.convert_module(&mut result);
449 let cc_stats = converter.stats();
450 (result, cc_stats.closures_converted)
451 }
452 PassId::Custom(_name) => (module.clone(), 0),
453 };
454 let elapsed = start.elapsed().as_micros() as u64;
455 let changed = transformations > 0;
456 PassResult {
457 module: new_module,
458 stats: PassStats {
459 decls_processed: module.fun_decls.len(),
460 transformations,
461 time_us: elapsed,
462 },
463 changed,
464 }
465 }
466}
467#[allow(dead_code)]
469#[derive(Debug, Clone, Default)]
470pub struct PipeExtPassStats {
471 pub iterations: usize,
472 pub changed: bool,
473 pub nodes_visited: usize,
474 pub nodes_modified: usize,
475 pub time_ms: u64,
476 pub memory_bytes: usize,
477 pub errors: usize,
478}
479impl PipeExtPassStats {
480 #[allow(dead_code)]
481 pub fn new() -> Self {
482 Self::default()
483 }
484 #[allow(dead_code)]
485 pub fn visit(&mut self) {
486 self.nodes_visited += 1;
487 }
488 #[allow(dead_code)]
489 pub fn modify(&mut self) {
490 self.nodes_modified += 1;
491 self.changed = true;
492 }
493 #[allow(dead_code)]
494 pub fn iterate(&mut self) {
495 self.iterations += 1;
496 }
497 #[allow(dead_code)]
498 pub fn error(&mut self) {
499 self.errors += 1;
500 }
501 #[allow(dead_code)]
502 pub fn efficiency(&self) -> f64 {
503 if self.nodes_visited == 0 {
504 0.0
505 } else {
506 self.nodes_modified as f64 / self.nodes_visited as f64
507 }
508 }
509 #[allow(dead_code)]
510 pub fn merge(&mut self, o: &PipeExtPassStats) {
511 self.iterations += o.iterations;
512 self.changed |= o.changed;
513 self.nodes_visited += o.nodes_visited;
514 self.nodes_modified += o.nodes_modified;
515 self.time_ms += o.time_ms;
516 self.memory_bytes = self.memory_bytes.max(o.memory_bytes);
517 self.errors += o.errors;
518 }
519}
520#[allow(dead_code)]
522#[derive(Debug)]
523pub struct PipeExtCache {
524 pub(crate) entries: Vec<(u64, Vec<u8>, bool, u32)>,
525 pub(crate) cap: usize,
526 pub(crate) total_hits: u64,
527 pub(crate) total_misses: u64,
528}
529impl PipeExtCache {
530 #[allow(dead_code)]
531 pub fn new(cap: usize) -> Self {
532 Self {
533 entries: Vec::new(),
534 cap,
535 total_hits: 0,
536 total_misses: 0,
537 }
538 }
539 #[allow(dead_code)]
540 pub fn get(&mut self, key: u64) -> Option<&[u8]> {
541 for e in self.entries.iter_mut() {
542 if e.0 == key && e.2 {
543 e.3 += 1;
544 self.total_hits += 1;
545 return Some(&e.1);
546 }
547 }
548 self.total_misses += 1;
549 None
550 }
551 #[allow(dead_code)]
552 pub fn put(&mut self, key: u64, data: Vec<u8>) {
553 if self.entries.len() >= self.cap {
554 self.entries.retain(|e| e.2);
555 if self.entries.len() >= self.cap {
556 self.entries.remove(0);
557 }
558 }
559 self.entries.push((key, data, true, 0));
560 }
561 #[allow(dead_code)]
562 pub fn invalidate(&mut self) {
563 for e in self.entries.iter_mut() {
564 e.2 = false;
565 }
566 }
567 #[allow(dead_code)]
568 pub fn hit_rate(&self) -> f64 {
569 let t = self.total_hits + self.total_misses;
570 if t == 0 {
571 0.0
572 } else {
573 self.total_hits as f64 / t as f64
574 }
575 }
576 #[allow(dead_code)]
577 pub fn live_count(&self) -> usize {
578 self.entries.iter().filter(|e| e.2).count()
579 }
580}
581#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
583pub enum OptLevel {
584 O0,
586 O1,
588 O2,
590 O3,
592}
593impl OptLevel {
594 pub fn to_u8(self) -> u8 {
596 match self {
597 OptLevel::O0 => 0,
598 OptLevel::O1 => 1,
599 OptLevel::O2 => 2,
600 OptLevel::O3 => 3,
601 }
602 }
603 pub fn default_passes(self) -> Vec<PassId> {
605 match self {
606 OptLevel::O0 => vec![],
607 OptLevel::O1 => vec![PassId::Dce],
608 OptLevel::O2 => {
609 vec![
610 PassId::Dce,
611 PassId::JoinPoints,
612 PassId::Specialize,
613 PassId::ClosureConvert,
614 PassId::Dce,
615 ]
616 }
617 OptLevel::O3 => {
618 vec![
619 PassId::Dce,
620 PassId::JoinPoints,
621 PassId::Specialize,
622 PassId::Reuse,
623 PassId::ClosureConvert,
624 PassId::Dce,
625 PassId::JoinPoints,
626 PassId::Dce,
627 ]
628 }
629 }
630 }
631 pub fn max_iterations(self) -> usize {
633 match self {
634 OptLevel::O0 => 0,
635 OptLevel::O1 => 3,
636 OptLevel::O2 => 5,
637 OptLevel::O3 => 10,
638 }
639 }
640}
641#[allow(dead_code)]
642#[derive(Debug, Clone)]
643pub struct PipeDepGraph {
644 pub(crate) nodes: Vec<u32>,
645 pub(crate) edges: Vec<(u32, u32)>,
646}
647impl PipeDepGraph {
648 #[allow(dead_code)]
649 pub fn new() -> Self {
650 PipeDepGraph {
651 nodes: Vec::new(),
652 edges: Vec::new(),
653 }
654 }
655 #[allow(dead_code)]
656 pub fn add_node(&mut self, id: u32) {
657 if !self.nodes.contains(&id) {
658 self.nodes.push(id);
659 }
660 }
661 #[allow(dead_code)]
662 pub fn add_dep(&mut self, dep: u32, dependent: u32) {
663 self.add_node(dep);
664 self.add_node(dependent);
665 self.edges.push((dep, dependent));
666 }
667 #[allow(dead_code)]
668 pub fn dependents_of(&self, node: u32) -> Vec<u32> {
669 self.edges
670 .iter()
671 .filter(|(d, _)| *d == node)
672 .map(|(_, dep)| *dep)
673 .collect()
674 }
675 #[allow(dead_code)]
676 pub fn dependencies_of(&self, node: u32) -> Vec<u32> {
677 self.edges
678 .iter()
679 .filter(|(_, dep)| *dep == node)
680 .map(|(d, _)| *d)
681 .collect()
682 }
683 #[allow(dead_code)]
684 pub fn topological_sort(&self) -> Vec<u32> {
685 let mut in_degree: std::collections::HashMap<u32, u32> = std::collections::HashMap::new();
686 for &n in &self.nodes {
687 in_degree.insert(n, 0);
688 }
689 for (_, dep) in &self.edges {
690 *in_degree.entry(*dep).or_insert(0) += 1;
691 }
692 let mut queue: std::collections::VecDeque<u32> = self
693 .nodes
694 .iter()
695 .filter(|&&n| in_degree[&n] == 0)
696 .copied()
697 .collect();
698 let mut result = Vec::new();
699 while let Some(node) = queue.pop_front() {
700 result.push(node);
701 for dep in self.dependents_of(node) {
702 let cnt = in_degree.entry(dep).or_insert(0);
703 *cnt = cnt.saturating_sub(1);
704 if *cnt == 0 {
705 queue.push_back(dep);
706 }
707 }
708 }
709 result
710 }
711 #[allow(dead_code)]
712 pub fn has_cycle(&self) -> bool {
713 self.topological_sort().len() < self.nodes.len()
714 }
715}
716#[derive(Debug, Clone, Default)]
718pub struct PipelineChangeSummary {
719 pub active_passes: Vec<String>,
721 pub converged_passes: Vec<String>,
723 pub lets_eliminated: usize,
725}
726impl PipelineChangeSummary {
727 pub fn new() -> Self {
729 Self::default()
730 }
731 pub fn mark_active(&mut self, pass: &str) {
733 self.active_passes.push(pass.to_string());
734 }
735 pub fn mark_converged(&mut self, pass: &str) {
737 self.converged_passes.push(pass.to_string());
738 }
739 pub fn any_changed(&self) -> bool {
741 !self.active_passes.is_empty()
742 }
743}
744#[allow(dead_code)]
746#[derive(Debug, Clone)]
747pub struct PipeExtPassConfig {
748 pub name: String,
749 pub phase: PipeExtPassPhase,
750 pub enabled: bool,
751 pub max_iterations: usize,
752 pub debug: u32,
753 pub timeout_ms: Option<u64>,
754}
755impl PipeExtPassConfig {
756 #[allow(dead_code)]
757 pub fn new(name: impl Into<String>) -> Self {
758 Self {
759 name: name.into(),
760 phase: PipeExtPassPhase::Middle,
761 enabled: true,
762 max_iterations: 100,
763 debug: 0,
764 timeout_ms: None,
765 }
766 }
767 #[allow(dead_code)]
768 pub fn with_phase(mut self, phase: PipeExtPassPhase) -> Self {
769 self.phase = phase;
770 self
771 }
772 #[allow(dead_code)]
773 pub fn with_max_iter(mut self, n: usize) -> Self {
774 self.max_iterations = n;
775 self
776 }
777 #[allow(dead_code)]
778 pub fn with_debug(mut self, d: u32) -> Self {
779 self.debug = d;
780 self
781 }
782 #[allow(dead_code)]
783 pub fn disabled(mut self) -> Self {
784 self.enabled = false;
785 self
786 }
787 #[allow(dead_code)]
788 pub fn with_timeout(mut self, ms: u64) -> Self {
789 self.timeout_ms = Some(ms);
790 self
791 }
792 #[allow(dead_code)]
793 pub fn is_debug_enabled(&self) -> bool {
794 self.debug > 0
795 }
796}