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. --- common/Globalenvs.v | 9 --------- common/Memory.v | 11 +---------- 2 files changed, 1 insertion(+), 19 deletions(-) (limited to 'common') diff --git a/common/Globalenvs.v b/common/Globalenvs.v index 4c9e7889..f424a69d 100644 --- a/common/Globalenvs.v +++ b/common/Globalenvs.v @@ -265,15 +265,6 @@ Qed. Program Definition empty_genv (pub: list ident): t := @mkgenv pub (PTree.empty _) (PTree.empty _) 1%positive _ _ _. -Next Obligation. - rewrite PTree.gempty in H. discriminate. -Qed. -Next Obligation. - rewrite PTree.gempty in H. discriminate. -Qed. -Next Obligation. - rewrite PTree.gempty in H. discriminate. -Qed. Definition globalenv (p: program F V) := add_globals (empty_genv p.(prog_public)) p.(prog_defs). diff --git a/common/Memory.v b/common/Memory.v index fa60455b..03a6572e 100644 --- a/common/Memory.v +++ b/common/Memory.v @@ -346,15 +346,6 @@ Program Definition empty: mem := mkmem (PMap.init (ZMap.init Undef)) (PMap.init (fun ofs k => None)) 1%positive _ _ _. -Next Obligation. - repeat rewrite PMap.gi. red; auto. -Qed. -Next Obligation. - rewrite PMap.gi. auto. -Qed. -Next Obligation. - rewrite PMap.gi. auto. -Qed. (** Allocation of a fresh block with the given bounds. Return an updated memory state and the address of the fresh block, which initially contains @@ -631,7 +622,7 @@ Proof. reflexivity. Qed. Theorem perm_empty: forall b ofs k p, ~perm empty b ofs k p. Proof. - intros. unfold perm, empty; simpl. rewrite PMap.gi. simpl. tauto. + intros. unfold perm, empty; simpl. tauto. Qed. Theorem valid_access_empty: forall chunk b ofs p, ~valid_access empty chunk b ofs p. -- cgit