(* 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 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.