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/SimplExprproof.v | 8 ++------ 1 file changed, 2 insertions(+), 6 deletions(-) (limited to 'cfrontend/SimplExprproof.v') 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: -- cgit