diff options
| author | Xavier Leroy <xavierleroy@users.noreply.github.com> | 2021-11-16 09:38:54 +0100 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2021-11-16 09:38:54 +0100 |
| commit | b9dfe18fb99d9fd0e8918c160ee297755c5fca59 (patch) | |
| tree | c7613e597e7f13156b57cdaf97c0ec89a4b7f655 /cfrontend | |
| parent | 168495d726e623e0b4bd6364f949ae577fa8b52e (diff) | |
| download | compcert-kvx-b9dfe18fb99d9fd0e8918c160ee297755c5fca59.tar.gz compcert-kvx-b9dfe18fb99d9fd0e8918c160ee297755c5fca59.zip | |
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.
Diffstat (limited to 'cfrontend')
| -rw-r--r-- | cfrontend/Cminorgenproof.v | 1 | ||||
| -rw-r--r-- | cfrontend/SimplExprproof.v | 8 | ||||
| -rw-r--r-- | cfrontend/SimplLocalsproof.v | 1 |
3 files changed, 2 insertions, 8 deletions
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. |