From b9dfe18fb99d9fd0e8918c160ee297755c5fca59 Mon Sep 17 00:00:00 2001 From: Xavier Leroy Date: Tue, 16 Nov 2021 09:38:54 +0100 Subject: An improved PTree data structure (#420) This PR replaces the "PTree" data structure used in lib/Maps.v by the canonical binary tries data structure proposed by A. W. Appel and described in the paper "Efficient Extensional Binary Tries", https://arxiv.org/abs/2110.05063 The new implementation is more memory-efficient and a bit faster, resulting in reduced compilation times (-5% on typical C programs, up to -10% on very large C functions). It also enjoys the extensionality property (two tries mapping equal keys to equal data are equal), which simplifies some proofs. --- cfrontend/Cminorgenproof.v | 1 - cfrontend/SimplExprproof.v | 8 ++------ cfrontend/SimplLocalsproof.v | 1 - 3 files changed, 2 insertions(+), 8 deletions(-) (limited to 'cfrontend') diff --git a/cfrontend/Cminorgenproof.v b/cfrontend/Cminorgenproof.v index bc1c92ca..ed45ac23 100644 --- a/cfrontend/Cminorgenproof.v +++ b/cfrontend/Cminorgenproof.v @@ -875,7 +875,6 @@ Proof. intros. apply Mem.perm_implies with Freeable; auto with mem. eapply Mem.perm_alloc_2; eauto. instantiate (1 := f1). red; intros. eelim Mem.fresh_block_alloc; eauto. eapply Mem.valid_block_inject_2; eauto. - intros. apply PTree.gempty. eapply match_callstack_alloc_right; eauto. intros. destruct (In_dec peq id (map fst vars)). apply cenv_remove_gss; auto. diff --git a/cfrontend/SimplExprproof.v b/cfrontend/SimplExprproof.v index 507e2128..ea89a8ba 100644 --- a/cfrontend/SimplExprproof.v +++ b/cfrontend/SimplExprproof.v @@ -893,13 +893,9 @@ Qed. Lemma static_bool_val_sound: forall v t m b, bool_val v t Mem.empty = Some b -> bool_val v t m = Some b. Proof. - assert (A: forall b ofs, Mem.weak_valid_pointer Mem.empty b ofs = false). - { unfold Mem.weak_valid_pointer, Mem.valid_pointer, proj_sumbool; intros. - rewrite ! pred_dec_false by (apply Mem.perm_empty). auto. } intros until b; unfold bool_val. - destruct (classify_bool t); destruct v; destruct Archi.ptr64 eqn:SF; auto. -- rewrite A; congruence. -- simpl; rewrite A; congruence. + destruct (classify_bool t); destruct v; destruct Archi.ptr64 eqn:SF; auto; + simpl; congruence. Qed. Lemma step_makeif: diff --git a/cfrontend/SimplLocalsproof.v b/cfrontend/SimplLocalsproof.v index c133d8ea..d2943f64 100644 --- a/cfrontend/SimplLocalsproof.v +++ b/cfrontend/SimplLocalsproof.v @@ -935,7 +935,6 @@ Proof. (* local var, lifted *) destruct R as [U V]. exploit H2; eauto. intros [chunk X]. eapply match_var_lifted with (v := Vundef) (tv := Vundef); eauto. - rewrite U; apply PTree.gempty. eapply alloc_variables_initial_value; eauto. red. unfold empty_env; intros. rewrite PTree.gempty in H4; congruence. apply create_undef_temps_charact with ty. -- cgit