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/SimplLocalsproof.v | |
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/SimplLocalsproof.v')
-rw-r--r-- | cfrontend/SimplLocalsproof.v | 1 |
1 files changed, 0 insertions, 1 deletions
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. |