From 993c6f0e7bc89af63f33d88ad3c71045a32a0a0f Mon Sep 17 00:00:00 2001 From: Mark Thom Date: Wed, 26 Feb 2020 21:57:57 -0700 Subject: [PATCH] actually do lco, and mark unsafe variables before the goals where they last occur, not just in the last goal --- src/prolog/codegen.rs | 94 ++++++++++-------------- src/prolog/fixtures.rs | 73 +++++++++--------- src/prolog/machine/machine_state.rs | 9 ++- src/prolog/machine/machine_state_impl.rs | 48 ++++++++---- 4 files changed, 112 insertions(+), 112 deletions(-) diff --git a/src/prolog/codegen.rs b/src/prolog/codegen.rs index eadbdded..13cb33f8 100644 --- a/src/prolog/codegen.rs +++ b/src/prolog/codegen.rs @@ -11,7 +11,7 @@ use crate::prolog::iterators::*; use crate::prolog::machine::machine_indices::*; use crate::prolog::targets::*; -use indexmap::IndexMap; +use indexmap::{IndexMap, IndexSet}; use std::cell::Cell; use std::rc::Rc; @@ -50,56 +50,45 @@ impl<'a> ConjunctInfo<'a> { self.has_deep_cut as usize } - fn mark_unsafe_vars>( + fn mark_unsafe_vars( &self, mut unsafe_var_marker: UnsafeVarMarker, - marker: &Alloc, - code: &mut Code + code: &mut Code, ) { - // target the last goal of the rule for handling unsafe variables. - // we use this weird logic to find the last goal. - let right_index = if let Some(Line::Control(_)) = code.last() { - if code.len() >= 2 { - code.len() - 2 - } else { - return; - } - } else { - if code.len() >= 1 { - code.len() - 1 - } else { - return; - } - }; + if code.is_empty() { + return; + } - let mut index = right_index; + let mut code_index = 0; - if let Line::Query(_) = &code[right_index] { - while let Line::Query(_) = &code[index] { - if index == 0 { - break; - } else { - index -= 1; + for phase in 0 .. { + while let Line::Query(ref query_instr) = &code[code_index] { + if !unsafe_var_marker.mark_safe_vars(query_instr) { + unsafe_var_marker.mark_phase(query_instr, phase); } + + code_index += 1; } - if let Line::Query(_) = &code[index] { + if code_index + 1 < code.len() { + code_index += 1; } else { - index += 1; + break; } + } - unsafe_var_marker.record_unsafe_vars(&self.perm_vs, marker); + code_index = 0; - for line in code.iter() { - if let Line::Query(ref query_instr) = line { - unsafe_var_marker.mark_safe_vars(query_instr); - } + for phase in 0 .. { + while let Line::Query(ref mut query_instr) = &mut code[code_index] { + unsafe_var_marker.mark_unsafe_vars(query_instr, phase); + code_index += 1; } - for index in index..right_index + 1 { - if let &mut Line::Query(ref mut query_instr) = &mut code[index] { - unsafe_var_marker.mark_unsafe_vars(query_instr); - } + if code_index + 1 < code.len() { + code_index += 1; + } else { + break; } } } @@ -684,6 +673,7 @@ impl<'a, TermMarker: Allocator<'a>> CodeGenerator { head: (_, ref args, ref p1), ref clauses, } = rule; + let mut code = Vec::new(); self.marker.reset_at_head(args); @@ -705,39 +695,31 @@ impl<'a, TermMarker: Allocator<'a>> CodeGenerator { let iter = ChunkedIterator::from_rule_body(p1, clauses); self.compile_seq(iter, &conjunct_info, &mut code, false)?; - conjunct_info.mark_unsafe_vars(unsafe_var_marker, &self.marker, &mut code); + conjunct_info.mark_unsafe_vars(unsafe_var_marker, &mut code); Self::compile_cleanup(&mut code, &conjunct_info, clauses.last().unwrap_or(p1)); Ok(code) } fn mark_unsafe_fact_vars(&self, fact: &mut CompiledFact) -> UnsafeVarMarker { - let mut unsafe_vars = IndexMap::new(); - - for var_status in self.marker.bindings().values() { - unsafe_vars.insert(var_status.as_reg_type(), false); - } + let mut safe_vars = IndexSet::new(); for fact_instr in fact.iter_mut() { match fact_instr { - &mut FactInstruction::UnifyValue(reg) => { - if let Some(found) = unsafe_vars.get_mut(®) { - if !*found { - *found = true; - *fact_instr = FactInstruction::UnifyLocalValue(reg); - } + &mut FactInstruction::UnifyValue(r) => { + if !safe_vars.contains(&r) { + *fact_instr = FactInstruction::UnifyLocalValue(r); + safe_vars.insert(r); } } - &mut FactInstruction::UnifyVariable(reg) => { - if let Some(found) = unsafe_vars.get_mut(®) { - *found = true; - } + &mut FactInstruction::UnifyVariable(r) => { + safe_vars.insert(r); } _ => {} - }; + } } - UnsafeVarMarker { unsafe_vars } + UnsafeVarMarker::from_safe_vars(safe_vars) } pub fn compile_fact<'b: 'a>(&mut self, term: &'b Term) -> Code { @@ -802,7 +784,7 @@ impl<'a, TermMarker: Allocator<'a>> CodeGenerator { let iter = ChunkedIterator::from_term_sequence(query); self.compile_seq(iter, &conjunct_info, &mut code, true)?; - conjunct_info.mark_unsafe_vars(UnsafeVarMarker::new(), &self.marker, &mut code); + conjunct_info.mark_unsafe_vars(UnsafeVarMarker::new(), &mut code); if let Some(query_term) = query.last() { Self::compile_cleanup(&mut code, &conjunct_info, query_term); diff --git a/src/prolog/fixtures.rs b/src/prolog/fixtures.rs index 5decc89c..6400bfec 100644 --- a/src/prolog/fixtures.rs +++ b/src/prolog/fixtures.rs @@ -1,6 +1,5 @@ use prolog_parser::ast::*; -use crate::prolog::allocator::*; use crate::prolog::forms::*; use crate::prolog::instructions::*; use crate::prolog::iterators::*; @@ -91,7 +90,7 @@ impl<'a> VariableFixtures<'a> { perm_vars: IndexMap::new(), last_chunk_temp_vars: IndexSet::new() } - + } pub fn insert(&mut self, var: Rc, vs: VariableFixture<'a>) { @@ -250,67 +249,67 @@ impl<'a> VariableFixtures<'a> { } pub struct UnsafeVarMarker { - pub unsafe_vars: IndexMap, + pub unsafe_vars: IndexMap, + pub safe_vars: IndexSet, } impl UnsafeVarMarker { pub fn new() -> Self { UnsafeVarMarker { unsafe_vars: IndexMap::new(), + safe_vars: IndexSet::new() } } - pub fn record_unsafe_vars<'a, Alloc: Allocator<'a>>( - &mut self, - fixtures: &VariableFixtures, - marker: &Alloc - ) { - for &(_, ref cb) in fixtures.values() { - if let Some(index) = cb.first() { - if !self.unsafe_vars.contains_key(&index.get().norm()) { - self.unsafe_vars.insert(index.get().norm(), false); - } - } + pub fn from_safe_vars(safe_vars: IndexSet) -> Self { + UnsafeVarMarker { + unsafe_vars: IndexMap::new(), + safe_vars } + } - for var in fixtures.last_chunk_temp_vars.iter().cloned() { - let r = marker.get(var); - self.unsafe_vars.insert(r, false); + pub fn mark_safe_vars(&mut self, query_instr: &QueryInstruction) -> bool { + match query_instr { + &QueryInstruction::PutVariable(r @ RegType::Temp(_), _) + | &QueryInstruction::SetVariable(r) => { + self.safe_vars.insert(r); + true + } + _ => { + false + } } } - pub fn mark_safe_vars(&mut self, query_instr: &QueryInstruction) { + pub fn mark_phase(&mut self, query_instr: &QueryInstruction, phase: usize) { match query_instr { - QueryInstruction::PutVariable(RegType::Temp(r), _) => { - if let Some(found) = self.unsafe_vars.get_mut(&RegType::Temp(*r)) { - *found = true; - } - } - QueryInstruction::SetVariable(reg) => { - if let Some(found) = self.unsafe_vars.get_mut(reg) { - *found = true; - } + &QueryInstruction::PutValue(r @ RegType::Perm(_), _) + | &QueryInstruction::SetValue(r) => { + let p = self.unsafe_vars.entry(r).or_insert(0); + *p = phase; } _ => {} } } - pub fn mark_unsafe_vars(&mut self, query_instr: &mut QueryInstruction) { + pub fn mark_unsafe_vars(&mut self, query_instr: &mut QueryInstruction, phase: usize) { match query_instr { &mut QueryInstruction::PutValue(RegType::Perm(i), arg) => { - if let Some(found) = self.unsafe_vars.get_mut(&RegType::Perm(i)) { - if !*found { - *found = true; + if let Some(p) = self.unsafe_vars.swap_remove(&RegType::Perm(i)) { + if p == phase { *query_instr = QueryInstruction::PutUnsafeValue(i, arg); + self.safe_vars.insert(RegType::Perm(i)); + } else { + self.unsafe_vars.insert(RegType::Perm(i), p); } } } - &mut QueryInstruction::SetValue(reg) => { - if let Some(found) = self.unsafe_vars.get_mut(®) { - if !*found { - *found = true; - *query_instr = QueryInstruction::SetLocalValue(reg); - } + &mut QueryInstruction::SetValue(r) => { + if !self.safe_vars.contains(&r) { + *query_instr = QueryInstruction::SetLocalValue(r); + + self.safe_vars.insert(r); + self.unsafe_vars.remove(&r); } } _ => {} diff --git a/src/prolog/machine/machine_state.rs b/src/prolog/machine/machine_state.rs index 3cca9363..bf4c5c5f 100644 --- a/src/prolog/machine/machine_state.rs +++ b/src/prolog/machine/machine_state.rs @@ -225,9 +225,12 @@ impl Index for MachineState { impl IndexMut for MachineState { fn index_mut(&mut self, reg: RegType) -> &mut Self::Output { match reg { - RegType::Temp(temp) => &mut self.registers[temp], + RegType::Temp(temp) => { + &mut self.registers[temp] + } RegType::Perm(perm) => { let e = self.e; + &mut self.stack.index_and_frame_mut(e)[perm] } } @@ -274,10 +277,10 @@ impl MachineState { fn try_char_list(&self, addrs: Vec) -> Result { let mut chars = String::new(); let mut iter = addrs.iter(); - + while let Some(addr) = iter.next() { let addr = self.store(self.deref(addr.clone())); - + match addr { Addr::Con(Constant::String(n, ref s)) if self.flags.double_quotes.is_chars() => { diff --git a/src/prolog/machine/machine_state_impl.rs b/src/prolog/machine/machine_state_impl.rs index fbc249cd..6b8849a5 100644 --- a/src/prolog/machine/machine_state_impl.rs +++ b/src/prolog/machine/machine_state_impl.rs @@ -49,7 +49,8 @@ macro_rules! try_or_fail { } impl MachineState { - pub(crate) fn new() -> Self { + pub(crate) + fn new() -> Self { MachineState { s: 0, p: CodePtr::default(), @@ -78,7 +79,8 @@ impl MachineState { } } - pub(crate) fn with_small_heap() -> Self { + pub(crate) + fn with_small_heap() -> Self { MachineState { s: 0, p: CodePtr::default(), @@ -441,6 +443,7 @@ impl MachineState { pub(super) fn unify(&mut self, a1: Addr, a2: Addr) { let mut pdl = vec![a1, a2]; + let mut tabu_list: IndexSet<(Addr, Addr)> = IndexSet::new(); self.fail = false; @@ -600,7 +603,8 @@ impl MachineState { } } - pub(super) fn trail(&mut self, r: TrailRef) { + pub(super) + fn trail(&mut self, r: TrailRef) { match r { TrailRef::Ref(Ref::HeapCell(h)) => { if h < self.hb { @@ -641,7 +645,8 @@ impl MachineState { } } - pub(super) fn unwind_trail(&mut self, a1: usize, a2: usize) { + pub(super) + fn unwind_trail(&mut self, a1: usize, a2: usize) { // the sequence is reversed to respect the chronology of trail // additions, now that deleted attributes can be undeleted by // backtracking. @@ -674,7 +679,8 @@ impl MachineState { } } - pub(super) fn tidy_trail(&mut self) { + pub(super) + fn tidy_trail(&mut self) { if self.b == 0 { return; } @@ -846,7 +852,9 @@ impl MachineState { { interms.push(Number::Float(OrderedFloat(f64::consts::PI))) } - _ => return Err(self.error_form(MachineError::instantiation_error(), caller)), + _ => { + return Err(self.error_form(MachineError::instantiation_error(), caller)); + } } } @@ -1284,7 +1292,8 @@ impl MachineState { } } - pub(super) fn execute_arith_instr(&mut self, instr: &ArithmeticInstruction) { + pub(super) + fn execute_arith_instr(&mut self, instr: &ArithmeticInstruction) { let stub = MachineError::functor_stub(clause_name!("(is)"), 2); match instr { @@ -1594,7 +1603,8 @@ impl MachineState { self.mode = MachineMode::Read; } - pub(super) fn execute_fact_instr(&mut self, instr: &FactInstruction) { + pub(super) + fn execute_fact_instr(&mut self, instr: &FactInstruction) { match instr { &FactInstruction::GetConstant(_, ref c, reg) => { let addr = self[reg].clone(); @@ -1759,7 +1769,8 @@ impl MachineState { }; } - pub(super) fn execute_indexing_instr(&mut self, instr: &IndexingInstruction) { + pub(super) + fn execute_indexing_instr(&mut self, instr: &IndexingInstruction) { match instr { &IndexingInstruction::SwitchOnTerm(v, c, l, s) => { let a1 = self.registers[1].clone(); @@ -1898,12 +1909,9 @@ impl MachineState { let addr = self.deref(self[reg].clone()); let h = self.heap.h(); - if let Addr::HeapCell(hc) = addr { - if hc < h { - let heap_val = self.heap[hc].clone(); - self.heap.push(heap_val); - return; - } + if addr < Ref::HeapCell(h) { + self.heap.push(HeapCellValue::Addr(addr)); + return; } self.heap.push(HeapCellValue::Addr(Addr::HeapCell(h))); @@ -1915,7 +1923,7 @@ impl MachineState { self[reg] = Addr::HeapCell(h); } &QueryInstruction::SetValue(reg) => { - let heap_val = self[reg].clone(); + let heap_val = self.store(self[reg].clone()); self.heap.push(HeapCellValue::Addr(heap_val)); } &QueryInstruction::SetVoid(n) => { @@ -3197,6 +3205,10 @@ impl MachineState { self.cp = frame.prelude.cp; self.e = frame.prelude.e; + if e > self.b { + self.stack.truncate(e); + } + self.p += 1; } @@ -3406,6 +3418,10 @@ impl MachineState { if b > b0 { self.b = b0; self.tidy_trail(); + + if b > self.e { + self.stack.truncate(b); + } } self.p += 1; -- 2.54.0