pub use crate::runtime::{*};
use crossbeam::utils::{Backoff};
use std::collections::HashSet;
use std::sync::atomic::{AtomicBool, AtomicUsize, AtomicU64, Ordering};
pub struct ReduceCtx<'a> {
pub heap : &'a Heap,
pub prog : &'a Program,
pub tid : usize,
pub hold : bool,
pub term : Ptr,
pub visit : &'a VisitQueue,
pub redex : &'a RedexBag,
pub cont : &'a mut u64,
pub host : &'a mut u64,
}
pub fn is_whnf(term: Ptr) -> bool {
match get_tag(term) {
ERA => true,
LAM => true,
SUP => true,
CTR => true,
U60 => true,
F60 => true,
_ => false,
}
}
pub fn reduce(heap: &Heap, prog: &Program, tids: &[usize], root: u64, full: bool, debug: bool) -> Ptr {
let stop = &AtomicUsize::new(1);
let barr = &Barrier::new(tids.len());
let locs = &tids.iter().map(|x| AtomicU64::new(u64::MAX)).collect::<Vec<AtomicU64>>();
std::thread::scope(|s| {
for tid in tids {
s.spawn(move || {
reducer(heap, prog, tids, stop, barr, locs, root, *tid, full, debug);
});
}
});
return load_ptr(heap, root);
}
pub fn reducer(
heap: &Heap,
prog: &Program,
tids: &[usize],
stop: &AtomicUsize,
barr: &Barrier,
locs: &[AtomicU64],
root: u64,
tid: usize,
full: bool,
debug: bool,
) {
let redex = &heap.rbag;
let visit = &heap.vstk[tid];
let bkoff = &Backoff::new();
let hold = tids.len() <= 1;
let seen = &mut HashSet::new();
let (mut cont, mut host) = if tid == tids[0] {
(REDEX_CONT_RET, root)
} else {
(0, u64::MAX)
};
let print = |tid: usize, host: u64| {
barr.wait(stop);
locs[tid].store(host, Ordering::SeqCst);
barr.wait(stop);
if tid == tids[0] {
println!("{}\n----------------", show_at(heap, prog, root, locs));
}
barr.wait(stop);
};
'main: loop {
'init: {
if host == u64::MAX {
break 'init;
}
'work: loop {
'visit: loop {
let term = load_ptr(heap, host);
if debug {
print(tid, host);
}
match get_tag(term) {
APP => {
if app::visit(ReduceCtx { heap, prog, tid, hold, term, visit, redex, cont: &mut cont, host: &mut host }) {
continue 'visit;
} else {
break 'work;
}
}
DP0 | DP1 => {
match acquire_lock(heap, tid, term) {
Err(locker_tid) => {
continue 'work;
}
Ok(_) => {
if term != load_ptr(heap, host) {
release_lock(heap, tid, term);
continue 'visit;
} else {
if dup::visit(ReduceCtx { heap, prog, tid, hold, term, visit, redex, cont: &mut cont, host: &mut host }) {
continue 'visit;
} else {
break 'work;
}
}
}
}
}
OP2 => {
if op2::visit(ReduceCtx { heap, prog, tid, hold, term, visit, redex, cont: &mut cont, host: &mut host }) {
continue 'visit;
} else {
break 'work;
}
}
FUN | CTR => {
let fid = get_ext(term);
match &prog.funs.get(&fid) {
Some(Function::Interpreted { smap: fn_smap, visit: fn_visit, apply: fn_apply }) => {
if fun::visit(ReduceCtx { heap, prog, tid, hold, term, visit, redex, cont: &mut cont, host: &mut host }, &fn_visit.strict_idx) {
continue 'visit;
} else {
break 'visit;
}
}
Some(Function::Compiled { smap: fn_smap, visit: fn_visit, apply: fn_apply }) => {
if fn_visit(ReduceCtx { heap, prog, tid, hold, term, visit, redex, cont: &mut cont, host: &mut host }) {
continue 'visit;
} else {
break 'visit;
}
}
None => {
break 'visit;
}
}
}
_ => {
break 'visit;
}
}
}
'call: loop {
'apply: loop {
let term = load_ptr(heap, host);
if debug {
print(tid, host);
}
match get_tag(term) {
APP => {
if app::apply(ReduceCtx { heap, prog, tid, hold, term, visit, redex, cont: &mut cont, host: &mut host }) {
continue 'work;
} else {
break 'apply;
}
}
DP0 | DP1 => {
if dup::apply(ReduceCtx { heap, prog, tid, hold, term, visit, redex, cont: &mut cont, host: &mut host }) {
release_lock(heap, tid, term);
continue 'work;
} else {
release_lock(heap, tid, term);
break 'apply;
}
}
OP2 => {
if op2::apply(ReduceCtx { heap, prog, tid, hold, term, visit, redex, cont: &mut cont, host: &mut host }) {
continue 'work;
} else {
break 'apply;
}
}
FUN | CTR => {
let fid = get_ext(term);
match &prog.funs.get(&fid) {
Some(Function::Interpreted { smap: fn_smap, visit: fn_visit, apply: fn_apply }) => {
if fun::apply(ReduceCtx { heap, prog, tid, hold, term, visit, redex, cont: &mut cont, host: &mut host }, fid, fn_visit, fn_apply) {
continue 'work;
} else {
break 'apply;
}
}
Some(Function::Compiled { smap: fn_smap, visit: fn_visit, apply: fn_apply }) => {
if fn_apply(ReduceCtx { heap, prog, tid, hold, term, visit, redex, cont: &mut cont, host: &mut host }) {
continue 'work;
} else {
break 'apply;
}
}
None => {
break 'apply;
}
}
}
_ => {
break 'apply;
}
}
}
if cont == REDEX_CONT_RET {
stop.fetch_sub(1, Ordering::Relaxed);
if full && !seen.contains(&host) {
seen.insert(host);
let term = load_ptr(heap, host);
match get_tag(term) {
LAM => {
stop.fetch_add(1, Ordering::Relaxed);
visit.push(new_visit(get_loc(term, 1), hold, cont));
}
APP => {
stop.fetch_add(2, Ordering::Relaxed);
visit.push(new_visit(get_loc(term, 0), hold, cont));
visit.push(new_visit(get_loc(term, 1), hold, cont));
}
SUP => {
stop.fetch_add(2, Ordering::Relaxed);
visit.push(new_visit(get_loc(term, 0), hold, cont));
visit.push(new_visit(get_loc(term, 1), hold, cont));
}
DP0 => {
stop.fetch_add(1, Ordering::Relaxed);
visit.push(new_visit(get_loc(term, 2), hold, cont));
}
DP1 => {
stop.fetch_add(1, Ordering::Relaxed);
visit.push(new_visit(get_loc(term, 2), hold, cont));
}
CTR | FUN => {
let arit = arity_of(&prog.aris, term);
if arit > 0 {
stop.fetch_add(arit as usize, Ordering::Relaxed);
for i in 0 .. arit {
visit.push(new_visit(get_loc(term, i), hold, cont));
}
}
}
_ => {}
}
}
break 'work;
}
if let Some((new_cont, new_host)) = redex.complete(cont) {
cont = new_cont;
host = new_host;
continue 'call;
}
break 'work;
}
}
'blink: loop {
if let Some((new_cont, new_host)) = visit.pop() {
cont = new_cont;
host = new_host;
continue 'main;
}
else {
break 'blink;
}
}
}
'steal: loop {
if debug {
print(tid, u64::MAX);
}
if stop.load(Ordering::Relaxed) == 0 {
break 'main;
} else {
for victim_tid in tids {
if *victim_tid != tid {
if let Some((new_cont, new_host)) = heap.vstk[*victim_tid].steal() {
cont = new_cont;
host = new_host;
continue 'main;
}
}
}
bkoff.snooze();
continue 'steal;
}
}
}
}
pub fn normalize(heap: &Heap, prog: &Program, tids: &[usize], host: u64, debug: bool) -> Ptr {
let mut cost = get_cost(heap);
loop {
reduce(heap, prog, tids, host, true, debug);
let new_cost = get_cost(heap);
if new_cost != cost {
cost = new_cost;
} else {
break;
}
}
load_ptr(heap, host)
}