phanerozoic's picture
Replace the two-bank machine with a K-bank ring, prove its reproduction in Rocq, and revise the paper
a9ea017
Raw History Blame Contribute Delete
9.29 kB
(* Cells a pass writes before it reads them carry nothing from one pass to the next. *)
From Stdlib Require Import List Bool Arith ZArith Lia.
Import ListNotations.
From TH Require Import TwoHead Abstract.
Definition ao_of (r : rec) : nat := match r with Rec _ _ _ _ _ ao => ao end.
Definition reads_ok (istmp : nat -> bool) (written : list nat) (a : nat) (w : Z) : bool :=
Z.eqb w 0 || Nat.leb a CPY || negb (istmp a) || existsb (Nat.eqb a) written.
Fixpoint wbr_from (rs : list rec) (istmp : nat -> bool) (written : list nat) : bool :=
match rs with
| [] => true
| Rec a0 w0 a1 w1 _ ao :: t =>
reads_ok istmp written a0 w0 && reads_ok istmp written a1 w1
&& wbr_from t istmp (written ++ [ao])
end.
(* two windows agree on the cells from 4 on that are not temporaries or that the pass has written *)
Definition wagree (istmp : nat -> bool) (written : list nat) (w1 w2 : list bool) : Prop :=
forall x, 4 <= x -> (istmp x = false \/ In x written) -> wget w1 x = wget w2 x.
Lemma acell_agree : forall istmp written t1 t2 a w,
aR t1 = aR t2 -> aA t1 = aA t2 -> aK t1 = aK t2 ->
wagree istmp written (aw t1) (aw t2) ->
reads_ok istmp written a w = true ->
(w * b2z (acell t1 a) = w * b2z (acell t2 a))%Z.
Proof.
intros istmp written t1 t2 a w HR HA HK Hw Hok. unfold reads_ok in Hok. unfold acell.
rewrite HR, HA, HK.
destruct (Z.eqb w 0) eqn:Ew; [apply Z.eqb_eq in Ew; rewrite Ew; reflexivity|].
destruct (Nat.eqb a SINK) eqn:E0; [reflexivity|].
destruct (Nat.eqb a RD) eqn:E1; [reflexivity|].
destruct (Nat.eqb a ARM) eqn:E2; [reflexivity|].
destruct (Nat.eqb a CPY) eqn:E3; [reflexivity|].
apply Nat.eqb_neq in E0, E1, E2, E3.
cbn [orb] in Hok. destruct (Nat.leb_spec a CPY) as [Hc|Hc]; [unfold SINK, RD, ARM, CPY in *; lia|].
cbn [orb] in Hok. rewrite Hw; [reflexivity | unfold CPY in Hc; lia |].
destruct (istmp a) eqn:Et; [right | left; reflexivity].
cbn [negb orb] in Hok. apply existsb_exists in Hok as (y & Hy & Hey).
apply Nat.eqb_eq in Hey. subst. exact Hy.
Qed.
Lemma opok_heads : forall t1 t2 a w,
aR t1 = aR t2 -> aA t1 = aA t2 -> aK t1 = aK t2 -> opok t1 a w = opok t2 a w.
Proof. intros t1 t2 a w HR HA HK. unfold opok. rewrite HR, HA, HK. reflexivity. Qed.
Lemma wagree_step : forall istmp written w1 w2 ao v,
wagree istmp written w1 w2 -> length w1 = length w2 ->
(forall c, AR <= c <= HO -> istmp c = false) ->
wagree istmp (written ++ [ao]) (clearq (wnext w1 ao v)) (clearq (wnext w2 ao v)).
Proof.
intros istmp written w1 w2 ao v H Hl Hreq x H4 Hx.
assert (Hc : forall w, wget (clearq w) x = if (AR <=? x) && (x <=? HO) && (x <? length w) then false else wget w x).
{ intro w. unfold clearq. rewrite !wget_upd, !upd_length.
unfold AR, AA, AC, RR, RA, RC, CB, CT, HO.
destruct (Nat.eqb_spec x 12); [subst; destruct (12 <? length w); reflexivity|].
destruct (Nat.eqb_spec x 11); [subst; destruct (11 <? length w); reflexivity|].
destruct (Nat.eqb_spec x 10); [subst; destruct (10 <? length w); reflexivity|].
destruct (Nat.eqb_spec x 9); [subst; destruct (9 <? length w); reflexivity|].
destruct (Nat.eqb_spec x 8); [subst; destruct (8 <? length w); reflexivity|].
destruct (Nat.eqb_spec x 7); [subst; destruct (7 <? length w); reflexivity|].
destruct (Nat.eqb_spec x 6); [subst; destruct (6 <? length w); reflexivity|].
destruct (Nat.eqb_spec x 5); [subst; destruct (5 <? length w); reflexivity|].
destruct (Nat.eqb_spec x 4); [subst; destruct (4 <? length w); reflexivity|].
destruct (Nat.leb_spec 4 x), (Nat.leb_spec x 12); cbn [andb]; try reflexivity; lia. }
rewrite !Hc, !length_wnext, Hl.
destruct ((AR <=? x) && (x <=? HO) && (x <? length w2)); [reflexivity|].
unfold wnext. destruct (Nat.leb_spec ao CPY) as [E|E].
- apply H; [exact H4|]. destruct Hx as [Hx|Hx]; [left; exact Hx|].
apply in_app_or in Hx as [Hx|Hx]; [right; exact Hx|].
destruct Hx as [Hx|[]]. subst x. unfold CPY in E. lia.
- rewrite !wget_upd, Hl.
destruct (Nat.eqb x ao && Nat.ltb ao (length w2)) eqn:Ex; [reflexivity|].
destruct Hx as [Hx|Hx]; [apply H; auto|].
apply in_app_or in Hx as [Hx|Hx]; [apply H; auto|].
destruct Hx as [Hx|[]]. subst x.
rewrite Nat.eqb_refl in Ex. cbn [andb] in Ex. apply Nat.ltb_ge in Ex.
unfold wget. rewrite !nth_overflow by lia. reflexivity.
Qed.
Lemma firstn_S_nth : forall (rs : list rec) j r, nth_error rs j = Some r ->
firstn (S j) rs = firstn j rs ++ [r].
Proof.
induction rs as [|y rs IH]; intros [|j] r H; cbn in *; try discriminate.
- injection H as ->. reflexivity.
- rewrite (IH j r H). reflexivity.
Qed.
Lemma skipn_nth : forall (rs : list rec) j r, nth_error rs j = Some r ->
skipn j rs = r :: skipn (S j) rs.
Proof.
induction rs as [|y rs IH]; intros [|j] r H; cbn in *; try discriminate.
- injection H as ->. reflexivity.
- apply IH. exact H.
Qed.
(* two abstract runs that start from states agreeing away from the temporaries agree there at the end *)
Lemma aiter_indep : forall n rs istmp t1 t2,
(forall c, AR <= c <= HO -> istmp c = false) ->
wbr_from (skipn (ai t1) rs) istmp (map ao_of (firstn (ai t1) rs)) = true ->
ai t1 = ai t2 -> aR t1 = aR t2 -> aA t1 = aA t2 -> aK t1 = aK t2 -> aho t1 = aho t2 -> bad t1 = bad t2 ->
length (aw t1) = length (aw t2) ->
wagree istmp (map ao_of (firstn (ai t1) rs)) (aw t1) (aw t2) ->
ai (aiter n rs t1) = ai (aiter n rs t2)
/\ aR (aiter n rs t1) = aR (aiter n rs t2)
/\ aA (aiter n rs t1) = aA (aiter n rs t2)
/\ aK (aiter n rs t1) = aK (aiter n rs t2)
/\ aho (aiter n rs t1) = aho (aiter n rs t2)
/\ bad (aiter n rs t1) = bad (aiter n rs t2)
/\ (forall x, 4 <= x -> istmp x = false -> wget (aw (aiter n rs t1)) x = wget (aw (aiter n rs t2)) x)
/\ wagree istmp (map ao_of (firstn (ai (aiter n rs t1)) rs)) (aw (aiter n rs t1)) (aw (aiter n rs t2)).
Proof.
induction n as [|n IH]; intros rs istmp t1 t2 Hreq Hwbr Hi HR HA HK Hho Hb Hl Hw.
- cbn [aiter]. refine (conj Hi (conj HR (conj HA (conj HK (conj Hho (conj Hb (conj _ Hw))))))).
intros x H4 Hx. apply Hw; auto.
- cbn [aiter].
destruct (nth_error rs (ai t1)) as [r|] eqn:Er.
+ assert (Er2 : nth_error rs (ai t2) = Some r) by (rewrite <- Hi; exact Er).
rewrite (skipn_nth rs _ r Er) in Hwbr.
destruct r as [a0 w0 a1 w1 beta ao]. cbn [wbr_from] in Hwbr.
apply andb_prop in Hwbr as [Hrd Hwbr]. apply andb_prop in Hrd as [Hr0 Hr1].
unfold astep. rewrite Er, Er2.
rewrite (acell_agree istmp _ t1 t2 a0 w0 HR HA HK Hw Hr0), (acell_agree istmp _ t1 t2 a1 w1 HR HA HK Hw Hr1).
set (v := Z.leb 0 (w0 * b2z (acell t2 a0) + w1 * b2z (acell t2 a1) + beta)%Z).
assert (Hq : forall c, AR <= c <= HO -> wget (wnext (aw t1) ao v) c = wget (wnext (aw t2) ao v) c).
{ intros c Hc. unfold wnext. destruct (Nat.leb ao CPY).
- apply Hw; [unfold AR in Hc; lia | left; apply Hreq; exact Hc].
- rewrite !wget_upd, Hl. destruct (_ && _); [reflexivity|].
apply Hw; [unfold AR in Hc; lia | left; apply Hreq; exact Hc]. }
apply IH; auto; unfold astepres; cbv zeta; cbn [ai aR aA aK aho bad aw].
* rewrite (firstn_S_nth rs _ _ Er), map_app. exact Hwbr.
* rewrite Hi; reflexivity.
* rewrite !Hq by (unfold AR, RR, HO; lia). rewrite HR. reflexivity.
* rewrite !Hq by (unfold AR, RA, AA, CB, HO; lia). rewrite HA. reflexivity.
* rewrite !Hq by (unfold AR, RC, AC, CT, HO; lia). rewrite HK. reflexivity.
* rewrite !Hq by (unfold AR, HO; lia). rewrite Hho. reflexivity.
* rewrite Hb, Hho, (opok_heads t1 t2 a0 w0 HR HA HK), (opok_heads t1 t2 a1 w1 HR HA HK), HA, HK, Hi,
!Hq by (unfold AR, HO; lia). reflexivity.
* rewrite !length_clearq, !length_wnext. exact Hl.
* rewrite (firstn_S_nth rs _ _ Er), map_app. apply wagree_step; auto.
+ assert (Er2 : nth_error rs (ai t2) = None) by (rewrite <- Hi; exact Er).
unfold astep. rewrite Er, Er2.
apply IH; cbn [ai aR aA aK aho bad aw]; auto.
Qed.
(* the cells outside the requests that no record writes keep their values *)
Lemma wget_clearq_out : forall w x, x < AR \/ HO < x -> wget (clearq w) x = wget w x.
Proof.
intros w x Hx. unfold clearq. rewrite !wget_upd.
unfold AR, AA, AC, RR, RA, RC, CB, CT, HO in *.
repeat match goal with |- context [Nat.eqb x ?c] =>
replace (Nat.eqb x c) with false by (symmetry; apply Nat.eqb_neq; lia) end.
reflexivity.
Qed.
Lemma wget_wnext_other : forall w ao v x, ao <> x -> wget (wnext w ao v) x = wget w x.
Proof.
intros w ao v x H. unfold wnext. destruct (Nat.leb ao CPY); [reflexivity|].
rewrite wget_upd. replace (Nat.eqb x ao) with false by (symmetry; apply Nat.eqb_neq; lia). reflexivity.
Qed.
Lemma aiter_unwritten : forall n rs t x, HO < x -> ~ In x (map ao_of rs) ->
wget (aw (aiter n rs t)) x = wget (aw t) x.
Proof.
induction n as [|n IH]; intros rs t x Hx Hn; [reflexivity|].
cbn [aiter]. rewrite IH by assumption. unfold astep.
destruct (nth_error rs (ai t)) as [r|] eqn:Er; [|reflexivity].
destruct r as [a0 w0 a1 w1 beta ao]. unfold astepres. cbv zeta. cbn [aw].
rewrite wget_clearq_out by (right; exact Hx).
apply wget_wnext_other. intro E. subst ao. apply Hn. apply in_map_iff.
exists (Rec a0 w0 a1 w1 beta x). split; [reflexivity|]. eapply nth_error_In. exact Er.
Qed.