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. --- backend/CSEdomain.v | 2 +- backend/ValueDomain.v | 4 ++-- 2 files changed, 3 insertions(+), 3 deletions(-) (limited to 'backend') diff --git a/backend/CSEdomain.v b/backend/CSEdomain.v index e96c4cd4..8809094e 100644 --- a/backend/CSEdomain.v +++ b/backend/CSEdomain.v @@ -140,7 +140,7 @@ Proof. - split; simpl; intros. + contradiction. + rewrite PTree.gempty in H; discriminate. - + rewrite PMap.gi in H; contradiction. + + contradiction. - contradiction. - rewrite PTree.gempty in H; discriminate. Qed. diff --git a/backend/ValueDomain.v b/backend/ValueDomain.v index 01f080ff..9bb99eaa 100644 --- a/backend/ValueDomain.v +++ b/backend/ValueDomain.v @@ -3438,7 +3438,7 @@ Lemma ablock_init_sound: forall m b p, smatch m b p -> bmatch m b (ablock_init p). Proof. intros; split; auto; intros. - unfold ablock_load, ablock_init; simpl. rewrite ZTree.gempty. + unfold ablock_load, ablock_init; simpl. eapply vnormalize_cast; eauto. eapply H; eauto. Qed. @@ -4558,7 +4558,7 @@ Lemma ematch_init: ematch (init_regs vl rl) (einit_regs rl). Proof. induction rl; simpl; intros. -- red; intros. rewrite Regmap.gi. simpl AE.get. rewrite PTree.gempty. +- red; intros. rewrite Regmap.gi. simpl. constructor. - destruct vl as [ | v1 vs ]. + assert (ematch (init_regs nil rl) (einit_regs rl)). -- cgit