1use crate::c_backend::{self, CEmitConfig, COutput};
6use crate::closure_convert::{ClosureConvertConfig, ClosureConverter};
7use crate::lcnf::*;
8use crate::native_backend::{self, NativeEmitConfig, NativeModule};
9use crate::opt_dce::{self, DceConfig};
10use crate::to_lcnf::{self, ToLcnfConfig};
11use crate::CodegenTarget;
12use oxilean_kernel::expr::Expr;
13use oxilean_kernel::Name;
14
15use super::super::functions::LcnfDeclInput;
16use super::impls1::*;
17use super::impls2::*;
18
19use super::super::functions::*;
20use super::impls1::*;
21use super::impls2::*;
22use std::collections::{HashMap, HashSet, VecDeque};
23
24#[allow(dead_code)]
25#[derive(Debug, Clone)]
26pub struct PipeDominatorTree {
27 pub idom: Vec<Option<u32>>,
28 pub dom_children: Vec<Vec<u32>>,
29 pub dom_depth: Vec<u32>,
30}
31impl PipeDominatorTree {
32 #[allow(dead_code)]
33 pub fn new(size: usize) -> Self {
34 PipeDominatorTree {
35 idom: vec![None; size],
36 dom_children: vec![Vec::new(); size],
37 dom_depth: vec![0; size],
38 }
39 }
40 #[allow(dead_code)]
41 pub fn set_idom(&mut self, node: usize, idom: u32) {
42 self.idom[node] = Some(idom);
43 }
44 #[allow(dead_code)]
45 pub fn dominates(&self, a: usize, b: usize) -> bool {
46 if a == b {
47 return true;
48 }
49 let mut cur = b;
50 loop {
51 match self.idom[cur] {
52 Some(parent) if parent as usize == a => return true,
53 Some(parent) if parent as usize == cur => return false,
54 Some(parent) => cur = parent as usize,
55 None => return false,
56 }
57 }
58 }
59 #[allow(dead_code)]
60 pub fn depth(&self, node: usize) -> u32 {
61 self.dom_depth.get(node).copied().unwrap_or(0)
62 }
63}
64#[allow(dead_code)]
66#[derive(Debug, Clone, Default)]
67pub struct PipeX2Liveness {
68 pub live_in: Vec<Vec<usize>>,
69 pub live_out: Vec<Vec<usize>>,
70 pub defs: Vec<Vec<usize>>,
71 pub uses: Vec<Vec<usize>>,
72}
73impl PipeX2Liveness {
74 #[allow(dead_code)]
75 pub fn new(n: usize) -> Self {
76 Self {
77 live_in: vec![Vec::new(); n],
78 live_out: vec![Vec::new(); n],
79 defs: vec![Vec::new(); n],
80 uses: vec![Vec::new(); n],
81 }
82 }
83 #[allow(dead_code)]
84 pub fn live_in(&self, b: usize, v: usize) -> bool {
85 self.live_in.get(b).map(|s| s.contains(&v)).unwrap_or(false)
86 }
87 #[allow(dead_code)]
88 pub fn live_out(&self, b: usize, v: usize) -> bool {
89 self.live_out
90 .get(b)
91 .map(|s| s.contains(&v))
92 .unwrap_or(false)
93 }
94 #[allow(dead_code)]
95 pub fn add_def(&mut self, b: usize, v: usize) {
96 if let Some(s) = self.defs.get_mut(b) {
97 if !s.contains(&v) {
98 s.push(v);
99 }
100 }
101 }
102 #[allow(dead_code)]
103 pub fn add_use(&mut self, b: usize, v: usize) {
104 if let Some(s) = self.uses.get_mut(b) {
105 if !s.contains(&v) {
106 s.push(v);
107 }
108 }
109 }
110 #[allow(dead_code)]
111 pub fn var_is_used_in_block(&self, b: usize, v: usize) -> bool {
112 self.uses.get(b).map(|s| s.contains(&v)).unwrap_or(false)
113 }
114 #[allow(dead_code)]
115 pub fn var_is_def_in_block(&self, b: usize, v: usize) -> bool {
116 self.defs.get(b).map(|s| s.contains(&v)).unwrap_or(false)
117 }
118}
119#[allow(dead_code)]
121#[derive(Debug, Clone, Default)]
122pub struct PipeX2ConstFolder {
123 pub(crate) folds: usize,
124 pub(crate) failures: usize,
125 pub(crate) enabled: bool,
126}
127impl PipeX2ConstFolder {
128 #[allow(dead_code)]
129 pub fn new() -> Self {
130 Self {
131 folds: 0,
132 failures: 0,
133 enabled: true,
134 }
135 }
136 #[allow(dead_code)]
137 pub fn add_i64(&mut self, a: i64, b: i64) -> Option<i64> {
138 self.folds += 1;
139 a.checked_add(b)
140 }
141 #[allow(dead_code)]
142 pub fn sub_i64(&mut self, a: i64, b: i64) -> Option<i64> {
143 self.folds += 1;
144 a.checked_sub(b)
145 }
146 #[allow(dead_code)]
147 pub fn mul_i64(&mut self, a: i64, b: i64) -> Option<i64> {
148 self.folds += 1;
149 a.checked_mul(b)
150 }
151 #[allow(dead_code)]
152 pub fn div_i64(&mut self, a: i64, b: i64) -> Option<i64> {
153 if b == 0 {
154 self.failures += 1;
155 None
156 } else {
157 self.folds += 1;
158 a.checked_div(b)
159 }
160 }
161 #[allow(dead_code)]
162 pub fn rem_i64(&mut self, a: i64, b: i64) -> Option<i64> {
163 if b == 0 {
164 self.failures += 1;
165 None
166 } else {
167 self.folds += 1;
168 a.checked_rem(b)
169 }
170 }
171 #[allow(dead_code)]
172 pub fn neg_i64(&mut self, a: i64) -> Option<i64> {
173 self.folds += 1;
174 a.checked_neg()
175 }
176 #[allow(dead_code)]
177 pub fn shl_i64(&mut self, a: i64, s: u32) -> Option<i64> {
178 if s >= 64 {
179 self.failures += 1;
180 None
181 } else {
182 self.folds += 1;
183 a.checked_shl(s)
184 }
185 }
186 #[allow(dead_code)]
187 pub fn shr_i64(&mut self, a: i64, s: u32) -> Option<i64> {
188 if s >= 64 {
189 self.failures += 1;
190 None
191 } else {
192 self.folds += 1;
193 a.checked_shr(s)
194 }
195 }
196 #[allow(dead_code)]
197 pub fn and_i64(&mut self, a: i64, b: i64) -> i64 {
198 self.folds += 1;
199 a & b
200 }
201 #[allow(dead_code)]
202 pub fn or_i64(&mut self, a: i64, b: i64) -> i64 {
203 self.folds += 1;
204 a | b
205 }
206 #[allow(dead_code)]
207 pub fn xor_i64(&mut self, a: i64, b: i64) -> i64 {
208 self.folds += 1;
209 a ^ b
210 }
211 #[allow(dead_code)]
212 pub fn not_i64(&mut self, a: i64) -> i64 {
213 self.folds += 1;
214 !a
215 }
216 #[allow(dead_code)]
217 pub fn fold_count(&self) -> usize {
218 self.folds
219 }
220 #[allow(dead_code)]
221 pub fn failure_count(&self) -> usize {
222 self.failures
223 }
224 #[allow(dead_code)]
225 pub fn enable(&mut self) {
226 self.enabled = true;
227 }
228 #[allow(dead_code)]
229 pub fn disable(&mut self) {
230 self.enabled = false;
231 }
232 #[allow(dead_code)]
233 pub fn is_enabled(&self) -> bool {
234 self.enabled
235 }
236}
237#[allow(dead_code)]
239#[derive(Debug, Clone)]
240pub struct PipeX2DepGraph {
241 pub(crate) n: usize,
242 pub(crate) adj: Vec<Vec<usize>>,
243 pub(crate) rev: Vec<Vec<usize>>,
244 pub(crate) edge_count: usize,
245}
246impl PipeX2DepGraph {
247 #[allow(dead_code)]
248 pub fn new(n: usize) -> Self {
249 Self {
250 n,
251 adj: vec![Vec::new(); n],
252 rev: vec![Vec::new(); n],
253 edge_count: 0,
254 }
255 }
256 #[allow(dead_code)]
257 pub fn add_edge(&mut self, from: usize, to: usize) {
258 if from < self.n && to < self.n {
259 if !self.adj[from].contains(&to) {
260 self.adj[from].push(to);
261 self.rev[to].push(from);
262 self.edge_count += 1;
263 }
264 }
265 }
266 #[allow(dead_code)]
267 pub fn succs(&self, n: usize) -> &[usize] {
268 self.adj.get(n).map(|v| v.as_slice()).unwrap_or(&[])
269 }
270 #[allow(dead_code)]
271 pub fn preds(&self, n: usize) -> &[usize] {
272 self.rev.get(n).map(|v| v.as_slice()).unwrap_or(&[])
273 }
274 #[allow(dead_code)]
275 pub fn topo_sort(&self) -> Option<Vec<usize>> {
276 let mut deg: Vec<usize> = (0..self.n).map(|i| self.rev[i].len()).collect();
277 let mut q: std::collections::VecDeque<usize> =
278 (0..self.n).filter(|&i| deg[i] == 0).collect();
279 let mut out = Vec::with_capacity(self.n);
280 while let Some(u) = q.pop_front() {
281 out.push(u);
282 for &v in &self.adj[u] {
283 deg[v] -= 1;
284 if deg[v] == 0 {
285 q.push_back(v);
286 }
287 }
288 }
289 if out.len() == self.n {
290 Some(out)
291 } else {
292 None
293 }
294 }
295 #[allow(dead_code)]
296 pub fn has_cycle(&self) -> bool {
297 self.topo_sort().is_none()
298 }
299 #[allow(dead_code)]
300 pub fn reachable(&self, start: usize) -> Vec<usize> {
301 let mut vis = vec![false; self.n];
302 let mut stk = vec![start];
303 let mut out = Vec::new();
304 while let Some(u) = stk.pop() {
305 if u < self.n && !vis[u] {
306 vis[u] = true;
307 out.push(u);
308 for &v in &self.adj[u] {
309 if !vis[v] {
310 stk.push(v);
311 }
312 }
313 }
314 }
315 out
316 }
317 #[allow(dead_code)]
318 pub fn scc(&self) -> Vec<Vec<usize>> {
319 let mut visited = vec![false; self.n];
320 let mut order = Vec::new();
321 for i in 0..self.n {
322 if !visited[i] {
323 let mut stk = vec![(i, 0usize)];
324 while let Some((u, idx)) = stk.last_mut() {
325 if !visited[*u] {
326 visited[*u] = true;
327 }
328 if *idx < self.adj[*u].len() {
329 let v = self.adj[*u][*idx];
330 *idx += 1;
331 if !visited[v] {
332 stk.push((v, 0));
333 }
334 } else {
335 order.push(*u);
336 stk.pop();
337 }
338 }
339 }
340 }
341 let mut comp = vec![usize::MAX; self.n];
342 let mut components: Vec<Vec<usize>> = Vec::new();
343 for &start in order.iter().rev() {
344 if comp[start] == usize::MAX {
345 let cid = components.len();
346 let mut component = Vec::new();
347 let mut stk = vec![start];
348 while let Some(u) = stk.pop() {
349 if comp[u] == usize::MAX {
350 comp[u] = cid;
351 component.push(u);
352 for &v in &self.rev[u] {
353 if comp[v] == usize::MAX {
354 stk.push(v);
355 }
356 }
357 }
358 }
359 components.push(component);
360 }
361 }
362 components
363 }
364 #[allow(dead_code)]
365 pub fn node_count(&self) -> usize {
366 self.n
367 }
368 #[allow(dead_code)]
369 pub fn edge_count(&self) -> usize {
370 self.edge_count
371 }
372}
373#[allow(dead_code)]
374#[derive(Debug, Clone)]
375pub struct PipeAnalysisCache {
376 pub(crate) entries: std::collections::HashMap<String, PipeCacheEntry>,
377 pub(crate) max_size: usize,
378 pub(crate) hits: u64,
379 pub(crate) misses: u64,
380}
381impl PipeAnalysisCache {
382 #[allow(dead_code)]
383 pub fn new(max_size: usize) -> Self {
384 PipeAnalysisCache {
385 entries: std::collections::HashMap::new(),
386 max_size,
387 hits: 0,
388 misses: 0,
389 }
390 }
391 #[allow(dead_code)]
392 pub fn get(&mut self, key: &str) -> Option<&PipeCacheEntry> {
393 if self.entries.contains_key(key) {
394 self.hits += 1;
395 self.entries.get(key)
396 } else {
397 self.misses += 1;
398 None
399 }
400 }
401 #[allow(dead_code)]
402 pub fn insert(&mut self, key: String, data: Vec<u8>) {
403 if self.entries.len() >= self.max_size {
404 if let Some(oldest) = self.entries.keys().next().cloned() {
405 self.entries.remove(&oldest);
406 }
407 }
408 self.entries.insert(
409 key.clone(),
410 PipeCacheEntry {
411 key,
412 data,
413 timestamp: 0,
414 valid: true,
415 },
416 );
417 }
418 #[allow(dead_code)]
419 pub fn invalidate(&mut self, key: &str) {
420 if let Some(entry) = self.entries.get_mut(key) {
421 entry.valid = false;
422 }
423 }
424 #[allow(dead_code)]
425 pub fn clear(&mut self) {
426 self.entries.clear();
427 }
428 #[allow(dead_code)]
429 pub fn hit_rate(&self) -> f64 {
430 let total = self.hits + self.misses;
431 if total == 0 {
432 return 0.0;
433 }
434 self.hits as f64 / total as f64
435 }
436 #[allow(dead_code)]
437 pub fn size(&self) -> usize {
438 self.entries.len()
439 }
440}
441pub struct PipelineBuilder {
443 pub(crate) config: PipelineConfig,
444}
445impl PipelineBuilder {
446 pub fn new() -> Self {
448 Self {
449 config: PipelineConfig::default(),
450 }
451 }
452 pub fn opt_level(mut self, level: OptLevel) -> Self {
454 self.config.opt_level = level;
455 self
456 }
457 pub fn target(mut self, target: CodegenTarget) -> Self {
459 self.config.target = target;
460 self
461 }
462 pub fn debug(mut self) -> Self {
464 self.config.debug = true;
465 self
466 }
467 pub fn emit_ir(mut self) -> Self {
469 self.config.emit_ir = true;
470 self
471 }
472 pub fn with_passes(mut self, passes: Vec<PassId>) -> Self {
474 self.config.passes = passes;
475 self
476 }
477 pub fn max_iterations(mut self, n: usize) -> Self {
479 self.config.max_iterations = n;
480 self
481 }
482 pub fn build(self) -> PipelineConfig {
484 self.config
485 }
486}
487#[allow(dead_code)]
489#[derive(Debug, Clone, Default)]
490pub struct PipeExtConstFolder {
491 pub(crate) folds: usize,
492 pub(crate) failures: usize,
493 pub(crate) enabled: bool,
494}
495impl PipeExtConstFolder {
496 #[allow(dead_code)]
497 pub fn new() -> Self {
498 Self {
499 folds: 0,
500 failures: 0,
501 enabled: true,
502 }
503 }
504 #[allow(dead_code)]
505 pub fn add_i64(&mut self, a: i64, b: i64) -> Option<i64> {
506 self.folds += 1;
507 a.checked_add(b)
508 }
509 #[allow(dead_code)]
510 pub fn sub_i64(&mut self, a: i64, b: i64) -> Option<i64> {
511 self.folds += 1;
512 a.checked_sub(b)
513 }
514 #[allow(dead_code)]
515 pub fn mul_i64(&mut self, a: i64, b: i64) -> Option<i64> {
516 self.folds += 1;
517 a.checked_mul(b)
518 }
519 #[allow(dead_code)]
520 pub fn div_i64(&mut self, a: i64, b: i64) -> Option<i64> {
521 if b == 0 {
522 self.failures += 1;
523 None
524 } else {
525 self.folds += 1;
526 a.checked_div(b)
527 }
528 }
529 #[allow(dead_code)]
530 pub fn rem_i64(&mut self, a: i64, b: i64) -> Option<i64> {
531 if b == 0 {
532 self.failures += 1;
533 None
534 } else {
535 self.folds += 1;
536 a.checked_rem(b)
537 }
538 }
539 #[allow(dead_code)]
540 pub fn neg_i64(&mut self, a: i64) -> Option<i64> {
541 self.folds += 1;
542 a.checked_neg()
543 }
544 #[allow(dead_code)]
545 pub fn shl_i64(&mut self, a: i64, s: u32) -> Option<i64> {
546 if s >= 64 {
547 self.failures += 1;
548 None
549 } else {
550 self.folds += 1;
551 a.checked_shl(s)
552 }
553 }
554 #[allow(dead_code)]
555 pub fn shr_i64(&mut self, a: i64, s: u32) -> Option<i64> {
556 if s >= 64 {
557 self.failures += 1;
558 None
559 } else {
560 self.folds += 1;
561 a.checked_shr(s)
562 }
563 }
564 #[allow(dead_code)]
565 pub fn and_i64(&mut self, a: i64, b: i64) -> i64 {
566 self.folds += 1;
567 a & b
568 }
569 #[allow(dead_code)]
570 pub fn or_i64(&mut self, a: i64, b: i64) -> i64 {
571 self.folds += 1;
572 a | b
573 }
574 #[allow(dead_code)]
575 pub fn xor_i64(&mut self, a: i64, b: i64) -> i64 {
576 self.folds += 1;
577 a ^ b
578 }
579 #[allow(dead_code)]
580 pub fn not_i64(&mut self, a: i64) -> i64 {
581 self.folds += 1;
582 !a
583 }
584 #[allow(dead_code)]
585 pub fn fold_count(&self) -> usize {
586 self.folds
587 }
588 #[allow(dead_code)]
589 pub fn failure_count(&self) -> usize {
590 self.failures
591 }
592 #[allow(dead_code)]
593 pub fn enable(&mut self) {
594 self.enabled = true;
595 }
596 #[allow(dead_code)]
597 pub fn disable(&mut self) {
598 self.enabled = false;
599 }
600 #[allow(dead_code)]
601 pub fn is_enabled(&self) -> bool {
602 self.enabled
603 }
604}
605#[allow(dead_code)]
606#[derive(Debug, Clone)]
607pub struct PipePassConfig {
608 pub phase: PipePassPhase,
609 pub enabled: bool,
610 pub max_iterations: u32,
611 pub debug_output: bool,
612 pub pass_name: String,
613}
614impl PipePassConfig {
615 #[allow(dead_code)]
616 pub fn new(name: impl Into<String>, phase: PipePassPhase) -> Self {
617 PipePassConfig {
618 phase,
619 enabled: true,
620 max_iterations: 10,
621 debug_output: false,
622 pass_name: name.into(),
623 }
624 }
625 #[allow(dead_code)]
626 pub fn disabled(mut self) -> Self {
627 self.enabled = false;
628 self
629 }
630 #[allow(dead_code)]
631 pub fn with_debug(mut self) -> Self {
632 self.debug_output = true;
633 self
634 }
635 #[allow(dead_code)]
636 pub fn max_iter(mut self, n: u32) -> Self {
637 self.max_iterations = n;
638 self
639 }
640}
641#[allow(dead_code)]
642#[derive(Debug, Clone)]
643pub struct PipeCacheEntry {
644 pub key: String,
645 pub data: Vec<u8>,
646 pub timestamp: u64,
647 pub valid: bool,
648}
649#[derive(Debug, Clone)]
651pub struct PassResult {
652 pub module: LcnfModule,
654 pub stats: PassStats,
656 pub changed: bool,
658}
659#[allow(dead_code)]
661#[derive(Debug, Clone)]
662pub struct PipeExtDomTree {
663 pub(crate) idom: Vec<Option<usize>>,
664 pub(crate) children: Vec<Vec<usize>>,
665 pub(crate) depth: Vec<usize>,
666}
667impl PipeExtDomTree {
668 #[allow(dead_code)]
669 pub fn new(n: usize) -> Self {
670 Self {
671 idom: vec![None; n],
672 children: vec![Vec::new(); n],
673 depth: vec![0; n],
674 }
675 }
676 #[allow(dead_code)]
677 pub fn set_idom(&mut self, node: usize, dom: usize) {
678 if node < self.idom.len() {
679 self.idom[node] = Some(dom);
680 if dom < self.children.len() {
681 self.children[dom].push(node);
682 }
683 self.depth[node] = if dom < self.depth.len() {
684 self.depth[dom] + 1
685 } else {
686 1
687 };
688 }
689 }
690 #[allow(dead_code)]
691 pub fn dominates(&self, a: usize, mut b: usize) -> bool {
692 if a == b {
693 return true;
694 }
695 let n = self.idom.len();
696 for _ in 0..n {
697 match self.idom.get(b).copied().flatten() {
698 None => return false,
699 Some(p) if p == a => return true,
700 Some(p) if p == b => return false,
701 Some(p) => b = p,
702 }
703 }
704 false
705 }
706 #[allow(dead_code)]
707 pub fn children_of(&self, n: usize) -> &[usize] {
708 self.children.get(n).map(|v| v.as_slice()).unwrap_or(&[])
709 }
710 #[allow(dead_code)]
711 pub fn depth_of(&self, n: usize) -> usize {
712 self.depth.get(n).copied().unwrap_or(0)
713 }
714 #[allow(dead_code)]
715 pub fn lca(&self, mut a: usize, mut b: usize) -> usize {
716 let n = self.idom.len();
717 for _ in 0..(2 * n) {
718 if a == b {
719 return a;
720 }
721 if self.depth_of(a) > self.depth_of(b) {
722 a = self.idom.get(a).and_then(|x| *x).unwrap_or(a);
723 } else {
724 b = self.idom.get(b).and_then(|x| *x).unwrap_or(b);
725 }
726 }
727 0
728 }
729}
730#[allow(dead_code)]
732#[derive(Debug, Clone)]
733pub struct PipeX2DomTree {
734 pub(crate) idom: Vec<Option<usize>>,
735 pub(crate) children: Vec<Vec<usize>>,
736 pub(crate) depth: Vec<usize>,
737}
738impl PipeX2DomTree {
739 #[allow(dead_code)]
740 pub fn new(n: usize) -> Self {
741 Self {
742 idom: vec![None; n],
743 children: vec![Vec::new(); n],
744 depth: vec![0; n],
745 }
746 }
747 #[allow(dead_code)]
748 pub fn set_idom(&mut self, node: usize, dom: usize) {
749 if node < self.idom.len() {
750 self.idom[node] = Some(dom);
751 if dom < self.children.len() {
752 self.children[dom].push(node);
753 }
754 self.depth[node] = if dom < self.depth.len() {
755 self.depth[dom] + 1
756 } else {
757 1
758 };
759 }
760 }
761 #[allow(dead_code)]
762 pub fn dominates(&self, a: usize, mut b: usize) -> bool {
763 if a == b {
764 return true;
765 }
766 let n = self.idom.len();
767 for _ in 0..n {
768 match self.idom.get(b).copied().flatten() {
769 None => return false,
770 Some(p) if p == a => return true,
771 Some(p) if p == b => return false,
772 Some(p) => b = p,
773 }
774 }
775 false
776 }
777 #[allow(dead_code)]
778 pub fn children_of(&self, n: usize) -> &[usize] {
779 self.children.get(n).map(|v| v.as_slice()).unwrap_or(&[])
780 }
781 #[allow(dead_code)]
782 pub fn depth_of(&self, n: usize) -> usize {
783 self.depth.get(n).copied().unwrap_or(0)
784 }
785 #[allow(dead_code)]
786 pub fn lca(&self, mut a: usize, mut b: usize) -> usize {
787 let n = self.idom.len();
788 for _ in 0..(2 * n) {
789 if a == b {
790 return a;
791 }
792 if self.depth_of(a) > self.depth_of(b) {
793 a = self.idom.get(a).and_then(|x| *x).unwrap_or(a);
794 } else {
795 b = self.idom.get(b).and_then(|x| *x).unwrap_or(b);
796 }
797 }
798 0
799 }
800}