harborc/
mir.rs

1use alloc::collections::BTreeMap;
2use core::fmt;
3use super::{error, lir::Program};
4
5use lalrpop_util::lalrpop_mod;
6lalrpop_mod!(pub mir_parser);
7
8
9#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
10pub struct Address(pub u32);
11
12impl fmt::Display for Address {
13    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
14        write!(f, "{}", self.0)
15    }
16}
17
18#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
19pub struct Literal(pub u32);
20
21impl fmt::Display for Literal {
22    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
23        write!(f, "{}", self.0)
24    }
25}
26
27#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
28pub enum Location {
29    Address(Address),
30    Deref(Box<Self>),
31    Offset(Box<Self>, i32),
32}
33
34#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
35pub enum Error {
36    MacroNotDefined(String),
37    CannotGetRuntimeAddress(Location),
38    
39    ParseError(String),
40}
41
42impl fmt::Display for Error {
43    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
44        write!(f, "\x1b[91merror: \x1b[m\x1b[0m")?;
45        match self {
46            Error::MacroNotDefined(name) => write!(f, "macro '{}' not defined", name),
47            Error::CannotGetRuntimeAddress(location) => write!(f, "cannot get runtime address of {}", location),
48            Error::ParseError(msg) => write!(f, "\n{}", msg),
49        }
50    }
51}
52
53pub fn parse(code: impl ToString) -> Result<Op, Error> {
54    let code = code.to_string();
55    match mir_parser::MIRParser::new().parse(&code) {
56        Ok(parsed) => {
57            Ok(parsed)
58        },
59        Err(e) => {
60            Err(Error::ParseError(error::format_error(&code, e)))
61        }
62    }
63}
64
65
66pub fn function(mut args: Vec<(String, u32)>, ret_size: u32, code: Vec<Op>) -> Op {
67    let mut offset = 0;
68    let mut args_size = 0;
69    let mut result = Op::Do(code);
70    for (_, size) in &args {
71        args_size += size;
72    }
73    
74    while let Some((name, size)) = args.pop() {
75        offset += size;
76        result = Op::Let(name, vec![
77            Op::LoadFrom(FP, 1),
78            Op::Increment(SP.deref(), args_size - offset),
79        ], vec![result]);
80    }
81    
82    Op::Frame(args_size, ret_size, vec![result])
83}
84
85impl Location {
86    pub fn get_address(&self) -> Result<Address, Error> {
87        match self {
88            Self::Address(address) => Ok(*address),
89            Self::Offset(inner, offset) => {
90                match inner.get_address() {
91                    Ok(address) => Ok(Address((address.0 as i32 + offset) as u32)),
92                    Err(error) => Err(error),
93                }
94            }
95            Self::Deref(_) => Err(Error::CannotGetRuntimeAddress(self.clone())),
96        }
97    }
98
99    pub fn deref(&self) -> Self {
100        Self::Deref(Box::new(self.clone()))
101    }
102
103    pub fn offset(&self, count: i32) -> Self {
104        Self::Offset(Box::new(self.clone()), count)
105    }
106
107    pub fn to(&self, program: &mut Program) {
108        match self {
109            Self::Deref(value) => {
110                value.to(program);
111                program.deref();
112            },
113
114            Self::Address(Address(address)) => {
115                program.right(*address);
116            }
117
118            Self::Offset(value, count) => {
119                value.to(program);
120                program.shift(*count);
121            }
122        }
123    }
124
125    pub fn from(&self, program: &mut Program) {
126        match self {
127            Self::Deref(value) => {
128                program.refer();
129                value.from(program);
130            },
131
132            Self::Address(Address(address)) => {
133                program.left(*address);
134            }
135
136            Self::Offset(value, count) => {
137                program.shift(-*count);
138                value.from(program);
139            }
140        }
141    }
142
143    pub fn zero(&self, program: &mut Program) {
144        self.to(program);
145        program.begin_loop();
146        program.minus(1);
147        program.end_loop();
148        self.from(program);
149    }
150
151    pub fn plus(&self, n: u32, program: &mut Program) {
152        self.to(program);
153        program.plus(n);
154        self.from(program);
155    }
156
157    pub fn inc(&self, program: &mut Program) {
158        self.to(program);
159        program.plus(1);
160        self.from(program);
161    }
162
163    pub fn minus(&self, n: u32, program: &mut Program) {
164        self.to(program);
165        program.minus(n);
166        self.from(program);
167    }
168
169    pub fn dec(&self, program: &mut Program) {
170        self.to(program);
171        program.minus(1);
172        self.from(program);
173    }
174
175    pub fn set(&self, value: u32, program: &mut Program) {
176        self.zero(program);
177        self.plus(value, program);
178    }
179
180    pub fn alloc(&self, program: &mut Program) {
181        self.to(program);
182        program.alloc();
183        self.from(program);
184    }
185
186    pub fn free(&self, program: &mut Program) {
187        self.to(program);
188        program.free();
189        program.zero();
190        self.from(program);
191    }
192
193    pub fn put(&self, program: &mut Program) {
194        self.to(program);
195        program.put();
196        self.from(program);
197    }
198
199    pub fn get(&self, program: &mut Program) {
200        self.to(program);
201        program.get();
202        self.from(program);
203    }
204
205    pub fn putnum(&self, program: &mut Program) {
206        self.to(program);
207        program.putnum();
208        self.from(program);
209    }
210
211    pub fn getnum(&self, program: &mut Program) {
212        self.to(program);
213        program.getnum();
214        self.from(program);
215    }
216
217
218    pub fn begin_loop(&self, program: &mut Program) {
219        self.to(program);
220        program.begin_loop();
221        self.from(program);
222    }
223    
224    pub fn end_loop(&self, program: &mut Program) {
225        self.to(program);
226        program.end_loop();
227        self.from(program);
228    }
229
230    pub fn push(&self, program: &mut Program) {
231        SP.inc(program);
232        copy_cell(
233            SP.deref(),
234            self.clone(),
235            program
236        );
237    }
238
239    pub fn pop_into(&self, program: &mut Program) {
240        copy_cell(
241            self.clone(),
242            SP.deref(),
243            program
244        );
245        // SP.deref().zero(program);
246        SP.dec(program);
247    }
248
249    pub fn load_ptr(&self, size: u32, program: &mut Program) {
250        for i in 0..size {
251            self.offset(i as i32).push(program);
252        }
253    }
254
255    pub fn store_ptr(&self, size: u32, program: &mut Program) {
256        for i in 0..size {
257            self.offset((size - i - 1) as i32).pop_into(program);
258        }
259    }
260}
261
262impl fmt::Display for Location {
263    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
264        match self {
265            Self::Address(loc) => if self == &SP {
266                write!(f, "SP")
267            } else if self == &FP {
268                write!(f, "FP")
269
270            } else if self == &TMP0 {
271                write!(f, "TMP0")
272            } else if self == &TMP1 {
273                write!(f, "TMP1")
274            } else if self == &TMP2 {
275                write!(f, "TMP2")
276            } else if self == &TMP3 {
277                write!(f, "TMP3")
278            } else if self == &TMP4 {
279                write!(f, "TMP4")
280            } else if self == &TMP5 {
281                write!(f, "TMP5")
282                
283            } else if self == &R0 {
284                write!(f, "R0")
285            } else if self == &R1 {
286                write!(f, "R1")
287            } else if self == &R2 {
288                write!(f, "R2")
289            } else if self == &R3 {
290                write!(f, "R3")
291            } else if self == &R4 {
292                write!(f, "R4")
293            } else if self == &R5 {
294                write!(f, "R5")
295
296            } else {
297                write!(f, "{}", loc.0)
298            },
299            Self::Offset(inner, offset) => write!(f, "{} {} +", inner, offset),
300            Self::Deref(inner) => write!(f, "{}@", inner),
301        }
302    }
303}
304
305pub const TOTAL_REGISTERS: u32 = 14;
306
307
308/// Stack pointer
309pub const SP: Location = Location::Address(Address(0));
310
311// Frame pointer
312pub const FP: Location = Location::Address(Address(3));
313
314/// Builtin registers for assembler use only
315pub const TMP0: Location = Location::Address(Address(1));
316pub const TMP1: Location = Location::Address(Address(2));
317pub const TMP2: Location = Location::Address(Address(4));
318pub const TMP3: Location = Location::Address(Address(5));
319pub const TMP4: Location = Location::Address(Address(6));
320pub const TMP5: Location = Location::Address(Address(7));
321
322/// General purpose registers
323pub const R0: Location = Location::Address(Address(8));
324pub const R1: Location = Location::Address(Address(9));
325pub const R2: Location = Location::Address(Address(10));
326pub const R3: Location = Location::Address(Address(11));
327pub const R4: Location = Location::Address(Address(12));
328pub const R5: Location = Location::Address(Address(13));
329
330#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
331pub enum Op {
332    Let(String, Vec<Self>, Vec<Self>),
333    Macro(String),
334
335    Frame(u32, u32, Vec<Self>),
336    Do(Vec<Self>),
337
338
339    /// Pop an address and store a value at that address
340    Set(Literal),
341
342    /// Store a number of cells at an address
343    StoreAt(Location, u32),
344    
345    /// Load a number of cells from an address
346    LoadFrom(Location, u32),
347
348    /// Pop an address and store a number of cells at that address
349    Store(u32),
350    /// Pop an address and load cells at that address
351    Load(u32),
352
353    /// Pop a size off the stack, and allocate that number of cells
354    Alloc,
355    /// Pop an address off the stack, and free that number of cells
356    Free,
357    /// Duplicate the top cell on the stack
358    Duplicate,
359
360    /// Pop a cell and print it
361    Putchar,
362
363    /// Get a character from STDIN and push it
364    Getchar,
365
366    /// Pop a cell and print it as a number
367    Putnum,
368    
369    /// Get a number from STDIN and push it
370    Getnum,
371
372    /// While loop
373    While(Vec<Self>, Vec<Self>),
374
375    /// If statement
376    If(Vec<Self>, Vec<Self>),
377
378    Increment(Location, u32),
379    Decrement(Location, u32),
380
381    /// Pop a value and push its logical not
382    Not,
383
384    /// Pop two cells and push their logical or
385    Or,
386
387    /// Pop two cells and push their logical and
388    And,
389
390    /// Pop two cells and push their sum
391    Add,
392
393    /// Pop two cells and push their difference
394    Sub,
395
396    /// Pop two cells and push their product
397    Mul,
398
399    /// Pop two cells and push their quotient
400    Div,
401
402    /// Pop two cells and push their equality
403    Eq,
404
405    /// Pop two cells and push their inequality
406    Neq,
407
408    /// Pop a value from the stack into an address
409    Pop(Location),
410
411    /// Push a literal onto the stack
412    PushLiteral(Literal),
413    /// Push an address onto the stack
414    PushAddress(Address),
415    /// Push a value onto the stack
416    Push(Location),
417
418    /// Allocate a number of cells on the stack
419    Stalloc(u32),
420    /// Pop a number of cells off the stack
421    Stfree(u32),
422}
423
424pub fn copy_cell(x: Location, y: Location, program: &mut Program) {
425    TMP0.zero(program);
426    x.zero(program);
427    
428    y.begin_loop(program);
429    x.inc(program);
430    TMP0.inc(program);
431    y.dec(program);
432    y.end_loop(program);
433    
434    TMP0.begin_loop(program);    
435    y.inc(program);
436    TMP0.dec(program);
437    TMP0.end_loop(program);
438}
439
440impl Op {
441    pub fn assemble(&self, program: &mut Program) -> Result<(), Error> {
442        self.assemble_with_scope(&BTreeMap::new(), program)
443    }
444
445    pub fn assemble_with_scope(&self, scope: &BTreeMap<String, Vec<Self>>, program: &mut Program) -> Result<(), Error> {
446        match self {
447            Self::Do(code) => {
448                for op in code {
449                    op.assemble_with_scope(&scope, program)?;
450                }
451            }
452            Self::Let(name, val, ret) => {
453                let mut new_scope = scope.clone();
454                new_scope.insert(name.clone(), val.clone());
455                
456                for op in ret {
457                    op.assemble_with_scope(&new_scope, program)?;
458                }
459            }
460
461            Self::Macro(name) => {
462                if let Some(code) = scope.get(name) {
463                    let mut new_scope = scope.clone();
464                    new_scope.remove(name);
465                    for op in code {
466                        op.assemble_with_scope(&new_scope, program)?;
467                    }
468                } else {
469                    return Err(Error::MacroNotDefined(name.clone()));
470                }
471            }
472
473            Self::Frame(args_size, ret_size, code) => {
474                // Allocate some space on the heap and temporarily spill the arguments there
475
476                if *args_size > 0 {
477                    Self::PushLiteral(Literal(*args_size)).assemble_with_scope(scope, program)?;
478                    Self::Alloc.assemble_with_scope(scope, program)?;
479                    Self::Duplicate.assemble_with_scope(scope, program)?;
480                    TMP5.pop_into(program);
481                    Self::Store(*args_size).assemble_with_scope(scope, program)?;
482                }
483
484
485                // push old frame pointer
486                FP.push(program);
487                copy_cell(
488                    FP,
489                    SP,
490                    program
491                );
492                // Increment it so it points to the first argument
493                FP.inc(program);
494
495                if *args_size > 0 {
496                    // Load the arguments from the heap
497                    TMP5.push(program);
498                    Self::Load(*args_size).assemble_with_scope(scope, program)?;
499                    // Free the memory we allocated to store them temporarily
500                    TMP5.push(program);
501                    Self::Free.assemble_with_scope(scope, program)?;
502                }
503                // Run the code in the new frame
504                for op in code {
505                    op.assemble_with_scope(scope, program)?;
506                }
507
508                if *ret_size > 0 {
509                    // Spill the return value to some memory on the heap
510                    Self::PushLiteral(Literal(*ret_size)).assemble_with_scope(scope, program)?;
511                    Self::Alloc.assemble_with_scope(scope, program)?;
512                    Self::Duplicate.assemble_with_scope(scope, program)?;
513                    TMP5.pop_into(program);
514                    Self::Store(*ret_size).assemble_with_scope(scope, program)?;
515                }
516                if *args_size > 0 {
517                    // Remove the arguments from the stack
518                    Self::Stfree(*args_size).assemble_with_scope(scope, program)?;
519                }
520                // Restore the frame pointer
521                FP.pop_into(program);
522
523                if *ret_size > 0 {
524                    // Load the return value from the heap, and free the memory
525                    TMP5.push(program);
526                    Self::Load(*ret_size).assemble_with_scope(scope, program)?;
527                    TMP5.push(program);
528                    Self::Free.assemble_with_scope(scope, program)?;
529                }
530                TMP5.zero(program);
531            }
532
533            Self::Pop(loc) => {
534                loc.pop_into(program);
535            },
536
537            Self::PushLiteral(Literal(n)) | Self::PushAddress(Address(n)) => {
538                SP.inc(program);
539                SP.deref().set(*n, program);
540            },
541
542            Self::Push(loc) => {
543                loc.push(program);
544            },
545
546            Self::Load(size) => {
547                TMP2.pop_into(program);
548                TMP2.deref().load_ptr(*size, program);
549            },
550
551            Self::Store(size) => {
552                // TMP2.pop_into(program);
553                // TMP2.deref().store_ptr(*size, program);
554                SP.dec(program);
555                for i in 1..*size+1 {
556                    SP.deref()
557                      .offset(i as i32)
558                      .deref()
559                      .offset((*size - i) as i32)
560                      .pop_into(program);
561                }
562            },
563
564            Self::LoadFrom(loc, size) => {
565                loc.load_ptr(*size, program);
566            },
567
568            Self::StoreAt(loc, size) => {
569                loc.store_ptr(*size, program);
570            },
571
572            Self::Stalloc(size) => {
573                if *size > 0 {
574                    SP.plus(*size, program);
575                }
576            }
577
578            Self::Stfree(size) => {
579                if *size > 0 {
580                    SP.minus(*size, program);
581                }
582            }
583
584            Self::Alloc => {
585                SP.deref().alloc(program);
586            }
587
588            Self::Free => {
589                SP.deref().free(program);
590                SP.dec(program);
591            }
592
593            Self::Duplicate => {
594                copy_cell(SP.deref().offset(1), SP.deref(), program);
595                SP.inc(program);
596            }
597
598            Self::Decrement(loc, n) => {
599                loc.minus(*n, program)
600            }
601
602            Self::Increment(loc, n) => {
603                loc.plus(*n, program)
604            }
605
606            Self::Not => {
607                let x = SP.deref();
608
609                TMP0.zero(program);
610                x.begin_loop(program);
611                TMP0.inc(program);
612                x.zero(program);
613                x.end_loop(program);
614                x.inc(program);
615
616                TMP0.begin_loop(program);
617                x.dec(program);
618                TMP0.dec(program);
619                TMP0.end_loop(program);
620            }
621
622            Self::Add | Self::Or => {
623                let x = SP.deref().offset(-1);
624                let y = SP.deref();
625                
626                // do addition
627                TMP0.zero(program);
628                y.begin_loop(program);
629                x.inc(program);
630                TMP0.inc(program);
631                y.dec(program);
632                y.end_loop(program);
633
634                TMP0.begin_loop(program);
635                y.inc(program);
636                TMP0.dec(program);
637                TMP0.end_loop(program);
638
639                SP.dec(program);
640            }
641
642            Self::Sub => {
643                let x = SP.deref().offset(-1);
644                let y = SP.deref();
645                
646                // do subtraction
647                TMP0.zero(program);
648                y.begin_loop(program);
649                x.dec(program);
650                TMP0.inc(program);
651                y.dec(program);
652                y.end_loop(program);
653
654                TMP0.begin_loop(program);
655                y.inc(program);
656                TMP0.dec(program);
657                TMP0.end_loop(program);
658
659                SP.dec(program);
660            }
661
662            Self::Mul | Self::And => {
663                let x = SP.deref().offset(-1);
664                let y = SP.deref();
665                
666                // do multiplication
667                TMP0.zero(program);
668                TMP1.zero(program);
669                
670                x.begin_loop(program);
671                TMP1.inc(program);
672                x.dec(program);
673                x.end_loop(program);
674
675                TMP1.begin_loop(program);
676                y.begin_loop(program);
677                x.inc(program);
678                TMP0.inc(program);
679                y.dec(program);
680                y.end_loop(program);
681
682                TMP0.begin_loop(program);
683                y.inc(program);
684                TMP0.dec(program);
685                TMP0.end_loop(program);
686
687                TMP1.dec(program);
688                TMP1.end_loop(program);
689
690                SP.dec(program);
691            }
692
693            Self::Div => {
694                let x = SP.deref().offset(-1);
695                let y = SP.deref();
696
697                // do division
698                TMP0.zero(program);
699                TMP1.zero(program);
700                TMP2.zero(program);
701                TMP3.zero(program);
702
703                x.begin_loop(program);
704                TMP0.inc(program);
705                x.dec(program);
706                x.end_loop(program);
707
708                TMP0.begin_loop(program);
709
710                y.begin_loop(program);
711                TMP1.inc(program);
712                TMP2.inc(program);
713                y.dec(program);
714                y.end_loop(program);
715
716                TMP2.begin_loop(program);
717                y.inc(program);
718                TMP2.dec(program);
719                TMP2.end_loop(program);
720
721                TMP1.begin_loop(program);
722
723                TMP2.inc(program);
724                TMP0.dec(program);
725                TMP0.begin_loop(program);
726                TMP2.zero(program);
727                TMP3.inc(program);
728                TMP0.dec(program);
729                TMP0.end_loop(program);
730                
731                TMP3.begin_loop(program);
732                TMP0.inc(program);
733                TMP3.dec(program);
734                TMP3.end_loop(program);
735
736                TMP2.begin_loop(program);
737                TMP1.dec(program);
738                TMP1.begin_loop(program);
739                x.dec(program);
740                TMP1.zero(program);
741                TMP1.end_loop(program);
742                TMP1.inc(program);
743
744                TMP2.dec(program);
745                TMP2.end_loop(program);
746                TMP1.dec(program);
747
748                TMP1.end_loop(program);
749                x.inc(program);
750                TMP0.end_loop(program);
751
752                SP.dec(program);
753            }
754
755            Self::If(cond, body) => {
756                let x = TMP2;
757                for op in cond {
758                    op.assemble_with_scope(scope, program)?;
759                }
760                x.pop_into(program);
761                x.begin_loop(program);
762                for op in body {
763                    op.assemble_with_scope(scope, program)?;
764                }
765                x.zero(program);
766                x.end_loop(program);
767            }
768
769            Self::While(cond, body) => {
770                for op in cond {
771                    op.assemble_with_scope(scope, program)?;
772                }
773                SP.deref().begin_loop(program);
774                SP.dec(program);
775                for op in body {
776                    op.assemble_with_scope(scope, program)?;
777                }
778                for op in cond {
779                    op.assemble_with_scope(scope, program)?;
780                }
781                SP.deref().end_loop(program);
782                SP.dec(program);
783            }
784
785            Self::Eq => {
786                let x = SP.deref().offset(-1);
787                let y = SP.deref();
788                // let x = TMP2;
789                // let y = TMP3;
790                // y.pop_into(program);
791                // x.pop_into(program);
792
793                TMP0.zero(program);
794                TMP1.zero(program);
795
796                x.begin_loop(program);
797                TMP1.inc(program);
798                x.dec(program);
799                x.end_loop(program);
800                x.inc(program);
801
802                y.begin_loop(program);
803                TMP1.dec(program);
804                TMP0.inc(program);
805                y.dec(program);
806                y.end_loop(program);
807
808                TMP0.begin_loop(program);
809                y.inc(program);
810                TMP0.dec(program);
811                TMP0.end_loop(program);
812
813                TMP1.begin_loop(program);
814                x.dec(program);
815                TMP1.zero(program);
816                TMP1.end_loop(program);
817
818                SP.dec(program);
819                // x.push(program);
820            }
821            
822            Self::Neq => {
823                Self::Eq.assemble_with_scope(scope, program)?;
824                Self::Not.assemble_with_scope(scope, program)?;
825                // Self::Sub.assemble_with_scope(scope, program)?;
826            }
827
828            Self::Putnum => {
829                SP.deref().putnum(program);
830                // SP.deref().zero(program);
831                SP.dec(program);
832            }
833            Self::Getnum => {
834                // TMP2.getnum(program);
835                // TMP2.push(program);
836                SP.inc(program);
837                SP.deref().getnum(program);
838            }
839
840            Self::Putchar => {
841                // SP.deref().zero(program);
842                SP.deref().put(program);
843                SP.dec(program);
844            }
845            Self::Getchar => {
846                // TMP2.get(program);
847                // TMP2.push(program);
848                SP.inc(program);
849                SP.deref().get(program);
850            }
851
852            _ => unimplemented!()
853        }
854        Ok(())
855    }
856}
harborc/mir.rs

harborc/
mir.rs
