calyx_opt/passes_experimental/sync/
compile_sync_without_sync_reg.rs

1use crate::traversal::{Action, Named, VisResult, Visitor};
2use calyx_ir::Guard;
3use calyx_ir::Nothing;
4use calyx_ir::{self as ir, GetAttributes, RRC};
5use calyx_ir::{build_assignments, guard, structure};
6use calyx_utils::{CalyxResult, Error};
7use std::collections::HashMap;
8
9#[derive(Default)]
10/// Compiles @sync without use of std_sync_reg
11/// Upon encountering @sync, it first instantiates a std_reg(1) for each thread(`bar`)
12/// and a std_wire(1) for each barrier (`s`)
13/// It then continuously assigns the value of (`s.in`) to 1'd1 guarded by the
14/// expression that all values of `bar` for threads under the barrier are
15/// set to 1'd1
16/// Then it replaces the @sync control operator with
17/// seq {
18///     barrier;
19///     clear;
20/// }
21/// `barrier` simply sets the value of `bar` to 1'd1 and then waits
22/// for `s.out` to be up
23/// `clear` resets the value of `bar` to 1'd0 for reuse of barrier
24/// Using this method, each thread only incurs 3 cycles of latency overhead for
25/// the barrier, and we theoretically won't have a limit for number of threads
26/// under one barrier
27pub struct CompileSyncWithoutSyncReg;
28
29impl Named for CompileSyncWithoutSyncReg {
30    fn name() -> &'static str {
31        "compile-sync-without-sync-reg"
32    }
33
34    fn description() -> &'static str {
35        "Implement barriers for statements marked with @sync attribute without std_sync_reg"
36    }
37}
38
39// Data structure storing the shared `s` register and the guard accumulator
40// for guarding `s.in`
41#[derive(Default)]
42struct BarrierMap(HashMap<u64, (RRC<ir::Cell>, Box<ir::Guard<ir::Nothing>>)>);
43
44impl BarrierMap {
45    fn get_mut(
46        &mut self,
47        idx: &u64,
48    ) -> Option<&mut (RRC<calyx_ir::Cell>, Box<Guard<Nothing>>)> {
49        self.0.get_mut(idx)
50    }
51
52    fn new() -> Self {
53        BarrierMap(HashMap::new())
54    }
55
56    fn get_reg(&mut self, idx: &u64) -> &mut RRC<ir::Cell> {
57        let (cell, _) = self.get_mut(idx).unwrap();
58        cell
59    }
60
61    fn get_guard(&mut self, idx: &u64) -> &mut Box<ir::Guard<ir::Nothing>> {
62        let (_, gd) = self.get_mut(idx).unwrap();
63        gd
64    }
65
66    fn insert_shared_wire(&mut self, builder: &mut ir::Builder, idx: &u64) {
67        if !self.0.contains_key(idx) {
68            structure!(builder;
69                let s = prim std_wire(1);
70            );
71            let gd = ir::Guard::True;
72            self.0.insert(*idx, (s, Box::new(gd)));
73        }
74    }
75}
76
77// instantiates the hardware and the two groups: `bar` and `clear` for each
78// barrier
79fn build_barrier_group(
80    builder: &mut ir::Builder,
81    barrier_idx: &u64,
82    barrier_reg: &mut BarrierMap,
83) -> ir::Control {
84    let group = builder.add_group("barrier");
85    structure!(
86        builder;
87        let bar = prim std_reg(1);
88        let z = constant(0, 1);
89        let constant = constant(1, 1);
90    );
91
92    barrier_reg
93        .get_guard(barrier_idx)
94        .update(|g| g.and(guard!(bar["out"])));
95
96    let s = barrier_reg.get_reg(barrier_idx);
97
98    let assigns = build_assignments!(builder;
99        bar["in"] = ? constant["out"];
100        bar["write_en"] = ? constant["out"];
101        group["done"] = ? s["out"];
102    );
103    group.borrow_mut().assignments.extend(assigns);
104
105    let clear = builder.add_group("clear");
106    let clear_assigns = build_assignments!(builder;
107        bar["in"] = ? z["out"];
108        bar["write_en"] = ? constant["out"];
109        clear["done"] = ? bar["done"];);
110    clear.borrow_mut().assignments.extend(clear_assigns);
111
112    let stmts = vec![ir::Control::enable(group), ir::Control::enable(clear)];
113
114    ir::Control::seq(stmts)
115}
116
117// produces error if `invoke` or `enable` are marked with @sync
118fn produce_err(con: &ir::Control) -> CalyxResult<()> {
119    match con {
120        ir::Control::Enable(e) => {
121            if con.get_attributes().get(ir::NumAttr::Sync).is_some() {
122                return Err(Error::malformed_control(
123                    "Enable or Invoke controls cannot be marked with @sync"
124                        .to_string(),
125                )
126                .with_pos(e.get_attributes()));
127            }
128            Ok(())
129        }
130        ir::Control::Invoke(i) => {
131            if con.get_attributes().get(ir::NumAttr::Sync).is_some() {
132                return Err(Error::malformed_control(
133                    "Enable or Invoke controls cannot be marked with @sync"
134                        .to_string(),
135                )
136                .with_pos(&i.attributes));
137            }
138            Ok(())
139        }
140        _ => Ok(()),
141    }
142}
143
144// recursively looks for the `@sync` control operator and then replaces them with
145// the corresponding `seq` block
146fn insert_barrier(
147    builder: &mut ir::Builder,
148    con: &mut ir::Control,
149    barrier_reg: &mut BarrierMap,
150    barrier_con: &mut HashMap<u64, ir::Control>,
151) -> CalyxResult<()> {
152    match con {
153        ir::Control::Empty(_) => {
154            if let Some(ref n) = con.get_attributes().get(ir::NumAttr::Sync) {
155                barrier_reg.insert_shared_wire(builder, n);
156                let con_ref = barrier_con.entry(*n).or_insert_with(|| {
157                    build_barrier_group(builder, n, barrier_reg)
158                });
159                *con = ir::Cloner::control(con_ref);
160            }
161            Ok(())
162        }
163        ir::Control::Seq(seq) => {
164            for s in seq.stmts.iter_mut() {
165                insert_barrier(builder, s, barrier_reg, barrier_con)?;
166            }
167            Ok(())
168        }
169        ir::Control::If(i) => {
170            insert_barrier(builder, &mut i.tbranch, barrier_reg, barrier_con)?;
171            insert_barrier(builder, &mut i.fbranch, barrier_reg, barrier_con)?;
172            Ok(())
173        }
174        ir::Control::While(w) => {
175            insert_barrier(builder, &mut w.body, barrier_reg, barrier_con)?;
176            Ok(())
177        }
178        ir::Control::Enable(_) | ir::Control::Invoke(_) => {
179            produce_err(con)?;
180            Ok(())
181        }
182        _ => Ok(()),
183    }
184}
185impl Visitor for CompileSyncWithoutSyncReg {
186    fn finish_par(
187        &mut self,
188        s: &mut ir::Par,
189        comp: &mut ir::Component,
190        sigs: &ir::LibrarySignatures,
191        _comps: &[ir::Component],
192    ) -> VisResult {
193        let mut builder = ir::Builder::new(comp, sigs);
194        let mut barrier_reg: BarrierMap = BarrierMap::new();
195        for stmt in s.stmts.iter_mut() {
196            let mut barrier_con: HashMap<u64, ir::Control> = HashMap::new();
197            insert_barrier(
198                &mut builder,
199                stmt,
200                &mut barrier_reg,
201                &mut barrier_con,
202            )?;
203        }
204
205        // add continuous assignments for value of `s`
206        for (_, (wire, g_box)) in barrier_reg.0 {
207            structure!( builder;
208                let constant = constant(1,1);
209            );
210            let g = *g_box;
211            let cont_assigns = build_assignments!(builder;
212                wire["in"] = g ? constant["out"];
213            );
214            builder
215                .component
216                .continuous_assignments
217                .extend(cont_assigns);
218        }
219        Ok(Action::Continue)
220    }
221}
calyx_opt/passes_experimental/sync/compile_sync_without_sync_reg.rs

calyx_opt/passes_experimental/sync/
compile_sync_without_sync_reg.rs
