From bb624cc971e02913c039b60a0e16cbf4d06694c7 Mon Sep 17 00:00:00 2001 From: Mark Thom Date: Sun, 8 Jan 2023 12:10:38 -0700 Subject: [PATCH] use free lists to allow register re-use (#1612) --- src/codegen.rs | 76 ++++++++++++++++++++++++++++++----------- src/debray_allocator.rs | 24 +++++++++++-- 2 files changed, 79 insertions(+), 21 deletions(-) diff --git a/src/codegen.rs b/src/codegen.rs index 6f722336..dc03a19a 100644 --- a/src/codegen.rs +++ b/src/codegen.rs @@ -242,6 +242,41 @@ fn trim_structure_by_last_arg(instr: &mut Instruction, last_arg: &Term) { } } +trait AddToFreeList<'a, Target: CompilationTarget<'a>> { + fn add_term_to_free_list(&mut self, r: RegType); + fn add_subterm_to_free_list(&mut self, term: &Term); +} + +impl<'a, 'b> AddToFreeList<'a, FactInstruction> for CodeGenerator<'b> { + #[inline(always)] + fn add_term_to_free_list(&mut self, r: RegType) { + self.marker.add_to_free_list(r); + } + + fn add_subterm_to_free_list(&mut self, _term: &Term) {} +} + +impl<'a, 'b> AddToFreeList<'a, QueryInstruction> for CodeGenerator<'b> { + fn add_term_to_free_list(&mut self, _r: RegType) {} + + #[inline(always)] + fn add_subterm_to_free_list(&mut self, term: &Term) { + if let Some(cell) = structure_cell(term) { + self.marker.add_to_free_list(cell.get()); + } + } +} + +fn structure_cell(term: &Term) -> Option<&Cell> { + match term { + &Term::Cons(ref cell, ..) | + &Term::Clause(ref cell, ..) | + Term::PartialString(ref cell, ..) | + Term::CompleteString(ref cell, ..) => Some(cell), + _ => None, + } +} + impl<'b> CodeGenerator<'b> { pub(crate) fn new(atom_tbl: &'b mut AtomTable, settings: CodeGenSettings) -> Self { CodeGenerator { @@ -287,10 +322,9 @@ impl<'b> CodeGenerator<'b> { cell: &'a Cell, var: &Rc, term_loc: GenContext, - is_exposed: bool, target: &mut Code, ) { - if is_exposed || self.get_var_count(var.as_ref()) > 1 { + if self.get_var_count(var.as_ref()) > 1 { self.marker.mark_var::(var.clone(), Level::Deep, cell, term_loc, target); } else { Self::add_or_increment_void_instr::(target); @@ -301,13 +335,9 @@ impl<'b> CodeGenerator<'b> { &mut self, subterm: &'a Term, term_loc: GenContext, - is_exposed: bool, target: &mut Code, ) { match subterm { - &Term::AnonVar if is_exposed => { - self.marker.mark_anon_var::(Level::Deep, term_loc, target); - } &Term::AnonVar => { Self::add_or_increment_void_instr::(target); } @@ -322,7 +352,7 @@ impl<'b> CodeGenerator<'b> { target.push(Target::constant_subterm(constant.clone())); } &Term::Var(ref cell, ref var) => { - self.deep_var_instr::(cell, var, term_loc, is_exposed, target); + self.deep_var_instr::(cell, var, term_loc, target); } }; } @@ -331,11 +361,11 @@ impl<'b> CodeGenerator<'b> { &mut self, iter: Iter, term_loc: GenContext, - is_exposed: bool, ) -> Code where Target: crate::targets::CompilationTarget<'a>, Iter: Iterator>, + CodeGenerator<'b>: AddToFreeList<'a, Target> { let mut target: Code = Vec::new(); @@ -352,6 +382,8 @@ impl<'b> CodeGenerator<'b> { self.marker.mark_non_var::(lvl, term_loc, cell, &mut target); target.push(Target::to_structure(name, terms.len(), cell.get())); + as AddToFreeList<'a, Target>>::add_term_to_free_list(self, cell.get()); + if let Some(instr) = target.last_mut() { if let Some(term) = terms.last() { trim_structure_by_last_arg(instr, term); @@ -359,15 +391,24 @@ impl<'b> CodeGenerator<'b> { } for subterm in terms { - self.subterm_to_instr::(subterm, term_loc, is_exposed, &mut target); + self.subterm_to_instr::(subterm, term_loc, &mut target); + } + + for subterm in terms { + as AddToFreeList<'a, Target>>::add_subterm_to_free_list(self, subterm); } } TermRef::Cons(lvl, cell, head, tail) => { self.marker.mark_non_var::(lvl, term_loc, cell, &mut target); target.push(Target::to_list(lvl, cell.get())); - self.subterm_to_instr::(head, term_loc, is_exposed, &mut target); - self.subterm_to_instr::(tail, term_loc, is_exposed, &mut target); + as AddToFreeList<'a, Target>>::add_term_to_free_list(self, cell.get()); + + self.subterm_to_instr::(head, term_loc, &mut target); + self.subterm_to_instr::(tail, term_loc, &mut target); + + as AddToFreeList<'a, Target>>::add_subterm_to_free_list(self, head); + as AddToFreeList<'a, Target>>::add_subterm_to_free_list(self, tail); } TermRef::Literal(lvl @ Level::Shallow, cell, Literal::String(ref string)) => { self.marker.mark_non_var::(lvl, term_loc, cell, &mut target); @@ -382,7 +423,7 @@ impl<'b> CodeGenerator<'b> { let atom = self.atom_tbl.build_with(&string); target.push(Target::to_pstr(lvl, atom, cell.get(), true)); - self.subterm_to_instr::(tail, term_loc, is_exposed, &mut target); + self.subterm_to_instr::(tail, term_loc, &mut target); } TermRef::CompleteString(lvl, cell, atom) => { self.marker.mark_non_var::(lvl, term_loc, cell, &mut target); @@ -823,7 +864,6 @@ impl<'b> CodeGenerator<'b> { iter: ChunkedIterator<'a>, conjunct_info: &ConjunctInfo<'a>, code: &mut Code, - is_exposed: bool, ) -> Result<(), CompilationError> { for (chunk_num, _, terms) in iter.rule_body_iter() { for (i, term) in terms.iter().enumerate() { @@ -859,7 +899,7 @@ impl<'b> CodeGenerator<'b> { conjunct_info.perm_vs.vars_above_threshold(i + 1) }; - self.compile_query_line(term, term_loc, code, num_perm_vars, is_exposed); + self.compile_query_line(term, term_loc, code, num_perm_vars); if self.marker.max_reg_allocated() > MAX_ARITY { return Err(CompilationError::ExceededMaxArity); @@ -931,7 +971,7 @@ impl<'b> CodeGenerator<'b> { self.compile_seq_prelude(&conjunct_info, &mut code); let iter = FactIterator::from_rule_head_clause(args); - let mut fact = self.compile_target::(iter, GenContext::Head, false); + let mut fact = self.compile_target::(iter, GenContext::Head); if self.marker.max_reg_allocated() > MAX_ARITY { return Err(CompilationError::ExceededMaxArity); @@ -945,7 +985,7 @@ impl<'b> CodeGenerator<'b> { } let iter = ChunkedIterator::from_rule_body(p1, clauses); - self.compile_seq(iter, &conjunct_info, &mut code, false)?; + self.compile_seq(iter, &conjunct_info, &mut code)?; unsafe_var_marker.mark_unsafe_instrs(&mut code); @@ -994,7 +1034,6 @@ impl<'b> CodeGenerator<'b> { let mut compiled_fact = self.compile_target::( iter, GenContext::Head, - false, ); if self.marker.max_reg_allocated() > MAX_ARITY { @@ -1018,12 +1057,11 @@ impl<'b> CodeGenerator<'b> { term_loc: GenContext, code: &mut Code, num_perm_vars_left: usize, - is_exposed: bool, ) { self.marker.reset_arg(term.arity()); let iter = query_term_post_order_iter(term); - let query = self.compile_target::(iter, term_loc, is_exposed); + let query = self.compile_target::(iter, term_loc); code.extend(query.into_iter()); self.add_conditional_call(code, term, num_perm_vars_left); diff --git a/src/debray_allocator.rs b/src/debray_allocator.rs index 1c81fcdd..98c1bd6e 100644 --- a/src/debray_allocator.rs +++ b/src/debray_allocator.rs @@ -6,7 +6,7 @@ use crate::forms::Level; use crate::instructions::*; use crate::machine::machine_indices::*; use crate::parser::ast::*; -use crate::targets::CompilationTarget; +use crate::targets::*; use crate::temp_v; @@ -24,6 +24,7 @@ pub(crate) struct DebrayAllocator { arity: usize, // 0 if not at head. contents: IndexMap, FxBuildHasher>, in_use: BTreeSet, + free_list: Vec, } impl DebrayAllocator { @@ -182,14 +183,21 @@ impl DebrayAllocator { fn alloc_reg_to_non_var(&mut self) -> usize { let mut final_index = 0; + while let Some(r) = self.free_list.pop() { + if !self.in_use.contains(&r) { + self.in_use.insert(r); + return r; + } + } + for index in self.temp_lb.. { if !self.in_use.contains(&index) { final_index = index; + self.in_use.insert(final_index); break; } } - self.in_use.insert(final_index); self.temp_lb = final_index + 1; final_index } @@ -203,6 +211,15 @@ impl DebrayAllocator { }, } } + + pub fn add_to_free_list(&mut self, r: RegType) { + if let RegType::Temp(r) = r { + if r > self.arity { + self.in_use.remove(&r); + self.free_list.push(r); + } + } + } } impl Allocator for DebrayAllocator { @@ -214,6 +231,7 @@ impl Allocator for DebrayAllocator { bindings: IndexMap::with_hasher(FxBuildHasher::default()), contents: IndexMap::with_hasher(FxBuildHasher::default()), in_use: BTreeSet::new(), + free_list: vec![], } } @@ -356,11 +374,13 @@ impl Allocator for DebrayAllocator { self.bindings.clear(); self.contents.clear(); self.in_use.clear(); + self.free_list.clear(); } fn reset_contents(&mut self) { self.contents.clear(); self.in_use.clear(); + self.free_list.clear(); } fn advance_arg(&mut self) { -- 2.54.0