diff options
-rw-r--r-- | mppa_k1c/Asmblock.v | 5 | ||||
-rw-r--r-- | mppa_k1c/Asmblockdeps.v | 8 | ||||
-rw-r--r-- | mppa_k1c/Asmvliw.v | 80 | ||||
-rw-r--r-- | mppa_k1c/PostpassSchedulingproof.v | 22 |
4 files changed, 73 insertions, 42 deletions
diff --git a/mppa_k1c/Asmblock.v b/mppa_k1c/Asmblock.v index b4cf57ae..f3f59f7d 100644 --- a/mppa_k1c/Asmblock.v +++ b/mppa_k1c/Asmblock.v @@ -1636,6 +1636,8 @@ Inductive final_state: state -> int -> Prop := Definition semantics (p: program) := Semantics step (initial_state p) final_state (Genv.globalenv p). +(* Useless + Remark extcall_arguments_determ: forall rs m sg args1 args2, extcall_arguments rs m sg args1 -> extcall_arguments rs m sg args2 -> args1 = args2. @@ -1695,6 +1697,7 @@ Ltac Equalities := - (* final states *) inv H; inv H0. congruence. Qed. +*) Definition data_preg (r: preg) : bool := match r with @@ -1707,7 +1710,7 @@ Definition data_preg (r: preg) : bool := (** Determinacy of the [Asm] semantics. *) -(* TODO. +(* Useless. Remark extcall_arguments_determ: forall rs m sg args1 args2, diff --git a/mppa_k1c/Asmblockdeps.v b/mppa_k1c/Asmblockdeps.v index dd876485..6d98ab9b 100644 --- a/mppa_k1c/Asmblockdeps.v +++ b/mppa_k1c/Asmblockdeps.v @@ -2158,15 +2158,13 @@ Proof. constructor; auto. Qed. -Lemma bblock_para_check_correct: - forall ge fn bb rs m rs' m' o, +Lemma bblock_para_check_correct ge fn bb rs m rs' m': Ge = Genv ge fn -> exec_bblock ge fn bb rs m = Next rs' m' -> bblock_para_check bb = true -> - parexec_bblock ge fn bb rs m o -> - o = Next rs' m'. + det_parexec ge fn bb rs m rs' m'. Proof. - intros. unfold bblock_para_check in H1. + intros H H0 H1 o H2. unfold bblock_para_check in H1. exploit forward_simu; eauto. eapply trans_state_match. intros (s2' & EXEC & MS). exploit forward_simu_par_alt. 2: apply (trans_state_match (State rs m)). all: eauto. diff --git a/mppa_k1c/Asmvliw.v b/mppa_k1c/Asmvliw.v index d553c612..1b3e0897 100644 --- a/mppa_k1c/Asmvliw.v +++ b/mppa_k1c/Asmvliw.v @@ -256,12 +256,14 @@ Definition parexec_wio_bblock_aux (f: function) bdy ext size_b (rsr rsw: regset) | Stuck => Stuck end. +(** parallel in-order writes execution of bundles *) Definition parexec_wio_bblock (f: function) (b: bblock) (rs: regset) (m: mem): outcome := parexec_wio_bblock_aux f (body b) (exit b) (Ptrofs.repr (size b)) rs rs m m. -Definition parexec_bblock (f: function) (b: bblock) (rs: regset) (m: mem) (o: outcome): Prop := - exists bdy1 bdy2, Permutation (bdy1++bdy2) (body b) /\ - o=match parexec_wio_bblock_aux f bdy1 (exit b) (Ptrofs.repr (size b)) rs rs m m with +(** non-deterministic (out-of-order writes) parallel execution of bundles *) +Definition parexec_bblock (f: function) (bundle: bblock) (rs: regset) (m: mem) (o: outcome): Prop := + exists bdy1 bdy2, Permutation (bdy1++bdy2) (body bundle) /\ + o=match parexec_wio_bblock_aux f bdy1 (exit bundle) (Ptrofs.repr (size bundle)) rs rs m m with | Next rsw mw => parexec_wio_body bdy2 rs rsw m mw | Stuck => Stuck end. @@ -276,14 +278,26 @@ Proof. destruct (parexec_wio_bblock_aux f _ _ _ _ _); simpl; auto. Qed. +(** deterministic parallel (out-of-order writes) execution of bundles *) +Definition det_parexec (f: function) (bundle: bblock) (rs: regset) (m: mem) rs' m': Prop := + forall o, parexec_bblock f bundle rs m o -> o = Next rs' m'. + + +Local Hint Resolve parexec_bblock_write_in_order. + +Lemma det_parexec_write_in_order f b rs m rs' m': + det_parexec f b rs m rs' m' -> parexec_wio_bblock f b rs m = Next rs' m'. +Proof. + unfold det_parexec; auto. +Qed. + Inductive step: state -> trace -> state -> Prop := | exec_step_internal: - forall b ofs f bi rs m rs' m', + forall b ofs f bundle rs m rs' m', rs PC = Vptr b ofs -> Genv.find_funct_ptr ge b = Some (Internal f) -> - find_bblock (Ptrofs.unsigned ofs) (fn_blocks f) = Some bi -> - parexec_wio_bblock f bi rs m = Next rs' m' -> - (forall o, parexec_bblock f bi rs m o -> o=(Next rs' m')) -> + find_bblock (Ptrofs.unsigned ofs) (fn_blocks f) = Some bundle -> + det_parexec f bundle rs m rs' m' -> step (State rs m) E0 (State rs' m') | exec_step_builtin: forall b ofs f ef args res rs m vargs t vres rs' m' bi, @@ -315,7 +329,29 @@ End RELSEM. Definition semantics (p: program) := Semantics step (initial_state p) final_state (Genv.globalenv p). -Lemma semantics_determinate: forall p, determinate (semantics p). +Remark extcall_arguments_determ: + forall rs m sg args1 args2, + extcall_arguments rs m sg args1 -> extcall_arguments rs m sg args2 -> args1 = args2. +Proof. + intros until m. + assert (A: forall l v1 v2, + extcall_arg rs m l v1 -> extcall_arg rs m l v2 -> v1 = v2). + { intros. inv H; inv H0; congruence. } + assert (B: forall p v1 v2, + extcall_arg_pair rs m p v1 -> extcall_arg_pair rs m p v2 -> v1 = v2). + { intros. inv H; inv H0. + eapply A; eauto. + f_equal; eapply A; eauto. } + assert (C: forall ll vl1, list_forall2 (extcall_arg_pair rs m) ll vl1 -> + forall vl2, list_forall2 (extcall_arg_pair rs m) ll vl2 -> vl1 = vl2). + { + induction 1; intros vl2 EA; inv EA. + auto. + f_equal; eauto. } + intros. eapply C; eauto. +Qed. + +Lemma semantics_determinate p: determinate (semantics p). Proof. Ltac Equalities := match goal with @@ -323,14 +359,20 @@ Ltac Equalities := rewrite H1 in H2; inv H2; Equalities | _ => idtac end. - intros; constructor; simpl; intros. -- (* determ *) - inv H; inv H0; Equalities. +Ltac Det_WIO X := + match goal with + | [ H: det_parexec _ _ _ _ _ _ _ |- _ ] => + exploit det_parexec_write_in_order; [ eapply H | idtac]; clear H; intro X + | _ => idtac + end. + intros; constructor; simpl. +- (* determ *) intros s t1 s1 t2 s2 H H0. inv H; Det_WIO X1; + inv H0; Det_WIO X2; Equalities. + split. constructor. auto. - + unfold parexec_wio_bblock, parexec_wio_bblock_aux in H4. destruct (parexec_wio_body _ _ _ _ _ _); try discriminate. - rewrite H10 in H4. discriminate. - + unfold parexec_wio_bblock, parexec_wio_bblock_aux in H11. destruct (parexec_wio_body _ _ _ _ _ _); try discriminate. - rewrite H4 in H11. discriminate. + + unfold parexec_wio_bblock, parexec_wio_bblock_aux in X1. destruct (parexec_wio_body _ _ _ _ _ _); try discriminate. + rewrite H8 in X1. discriminate. + + unfold parexec_wio_bblock, parexec_wio_bblock_aux in X2. destruct (parexec_wio_body _ _ _ _ _ _); try discriminate. + rewrite H4 in X2. discriminate. + assert (vargs0 = vargs) by (eapply eval_builtin_args_determ; eauto). subst vargs0. exploit external_call_determ. eexact H6. eexact H13. intros [A B]. split. auto. intros. destruct B; auto. subst. auto. @@ -343,12 +385,12 @@ Ltac Equalities := eapply external_call_trace_length; eauto. eapply external_call_trace_length; eauto. - (* initial states *) - inv H; inv H0. f_equal. congruence. + intros s1 s2 H H0; inv H; inv H0; f_equal; congruence. - (* final no step *) - assert (NOTNULL: forall b ofs, Vnullptr <> Vptr b ofs). + intros s r H; assert (NOTNULL: forall b ofs, Vnullptr <> Vptr b ofs). { intros; unfold Vnullptr; destruct Archi.ptr64; congruence. } - inv H. unfold Vzero in H0. red; intros; red; intros. + inv H. red; intros; red; intros. inv H; rewrite H0 in *; eelim NOTNULL; eauto. - (* final states *) - inv H; inv H0. congruence. + intros s r1 r2 H H0; inv H; inv H0. congruence. Qed.
\ No newline at end of file diff --git a/mppa_k1c/PostpassSchedulingproof.v b/mppa_k1c/PostpassSchedulingproof.v index 4e33fc90..4433bb1d 100644 --- a/mppa_k1c/PostpassSchedulingproof.v +++ b/mppa_k1c/PostpassSchedulingproof.v @@ -776,37 +776,26 @@ Proof. intros; eapply find_bblock_Some_in; eauto. Qed. -Lemma checked_bundles_are_parexec_equiv f bundle rs rs' m m' o: +Lemma checked_bundles_are_parexec_equiv f bundle rs rs' m m': exec_bblock (globalenv (Asmblock.semantics tprog)) f bundle rs m = Next rs' m' -> verify_par_bblock bundle = OK tt -> - parexec_bblock (globalenv (semantics tprog)) f bundle rs m o -> o = Next rs' m'. + det_parexec (globalenv (semantics tprog)) f bundle rs m rs' m'. Proof. intros. unfold verify_par_bblock in H0. destruct (Asmblockdeps.bblock_para_check _) eqn:BPC; try discriminate. clear H0. - simpl in H. simpl in H1. + simpl in H. eapply Asmblockdeps.bblock_para_check_correct; eauto. Qed. -Lemma seqexec_parexec_equiv b ofs f bundle rs rs' m m' o: +Lemma seqexec_parexec_equiv b ofs f bundle rs rs' m m': Genv.find_funct_ptr (globalenv (Asmblock.semantics tprog)) b = Some (Internal f) -> find_bblock (Ptrofs.unsigned ofs) (fn_blocks f) = Some bundle -> exec_bblock (globalenv (Asmblock.semantics tprog)) f bundle rs m = Next rs' m' -> - parexec_bblock (globalenv (semantics tprog)) f bundle rs m o -> o = Next rs' m'. + det_parexec (globalenv (semantics tprog)) f bundle rs m rs' m'. Proof. intros; eapply checked_bundles_are_parexec_equiv; eauto. eapply all_bundles_are_checked; eauto. Qed. -Lemma seqexec_parexec_wio b ofs f bundle rs rs' m m': - Genv.find_funct_ptr (globalenv (Asmblock.semantics tprog)) b = Some (Internal f) -> - find_bblock (Ptrofs.unsigned ofs) (fn_blocks f) = Some bundle -> - exec_bblock (globalenv (Asmblock.semantics tprog)) f bundle rs m = Next rs' m' -> - parexec_wio_bblock (globalenv (semantics tprog)) f bundle rs m = Next rs' m'. -Proof. - intros; erewrite <- seqexec_parexec_equiv; eauto. - eapply parexec_bblock_write_in_order. -Qed. - - Theorem transf_program_correct_Asmvliw: forward_simulation (Asmblock.semantics tprog) (Asmvliw.semantics tprog). Proof. @@ -814,7 +803,6 @@ Proof. - intros; subst; auto. - intros s1 t s1' H s2 H0; subst; inversion H; clear H; subst; eexists; split; eauto. + eapply exec_step_internal; eauto. - eapply seqexec_parexec_wio; eauto. intros; eapply seqexec_parexec_equiv; eauto. + eapply exec_step_builtin; eauto. + eapply exec_step_external; eauto. |