Merge remote-tracking branch 'origin/kvx-work' into kvx-work-dirty

9 files changed, 149 insertions, 79 deletions

diff --git a/.gitignore b/.gitignore
index 771654d7..1d6cad94 100644
--- a/.gitignore
+++ b/.gitignore
@@ -21,6 +21,7 @@
 # Emacs saves
 *~
 # Executables and configuration
+/tools/compiler_expand
 /ccomp
 /ccomp.byte
 /ccomp.prof
diff --git a/.gitlab-ci.yml b/.gitlab-ci.yml
index 88cc9fd4..7f992502 100644
--- a/.gitlab-ci.yml
+++ b/.gitlab-ci.yml
@@ -3,7 +3,7 @@ stages:
 
 check-admitted:
   stage: build
-  image: coqorg/coq:8.11.2-ocaml-4.11.1-flambda
+  image: coqorg/coq:8.12.2-ocaml-4.11.1-flambda
   before_script:
     - eval `opam config env`
     - opam update
@@ -22,7 +22,7 @@ check-admitted:
     
 build_x86_64:
   stage: build
-  image: coqorg/coq:8.12-ocaml-4.11-flambda
+  image: coqorg/coq:8.12.2-ocaml-4.11.1-flambda
   before_script:
     - eval `opam config env`
     - opam update
@@ -43,7 +43,7 @@ build_x86_64:
 
 build_ia32:
   stage: build
-  image: coqorg/coq:8.11.2-ocaml-4.11.1-flambda
+  image: coqorg/coq:8.12.2-ocaml-4.11.1-flambda
   before_script:
     - sudo apt-get -o Acquire::Check-Valid-Until=false -o Acquire::Check-Date=false update
     - sudo apt-get -y install gcc-multilib
@@ -66,7 +66,7 @@ build_ia32:
 
 build_aarch64:
   stage: build
-  image: coqorg/coq:8.11.2-ocaml-4.11.1-flambda
+  image: coqorg/coq:8.12.2-ocaml-4.11.1-flambda
   before_script:
     - sudo apt-get -o Acquire::Check-Valid-Until=false -o Acquire::Check-Date=false update
     - sudo apt-get -y install gcc-aarch64-linux-gnu qemu-user
@@ -89,7 +89,7 @@ build_aarch64:
 
 build_arm:
   stage: build
-  image: coqorg/coq:8.11.2-ocaml-4.11.1-flambda
+  image: coqorg/coq:8.12.2-ocaml-4.11.1-flambda
   before_script:
     - sudo apt-get -o Acquire::Check-Valid-Until=false -o Acquire::Check-Date=false update
     - sudo apt-get -y install gcc-arm-linux-gnueabi qemu-user
@@ -113,7 +113,7 @@ build_arm:
 
 build_armhf:
   stage: build
-  image: coqorg/coq:8.11.2-ocaml-4.11.1-flambda
+  image: coqorg/coq:8.12.2-ocaml-4.11.1-flambda
   before_script:
     - sudo apt-get -o Acquire::Check-Valid-Until=false -o Acquire::Check-Date=false update
     - sudo apt-get -y install gcc-arm-linux-gnueabihf qemu-user
@@ -136,7 +136,7 @@ build_armhf:
 
 build_ppc:
   stage: build
-  image: coqorg/coq:8.11.2-ocaml-4.11.1-flambda
+  image: coqorg/coq:8.12.2-ocaml-4.11.1-flambda
   before_script:
     - sudo apt-get -o Acquire::Check-Valid-Until=false -o Acquire::Check-Date=false update
     - sudo apt-get -y install gcc-powerpc-linux-gnu qemu-user
@@ -157,7 +157,7 @@ build_ppc:
 
 build_ppc64:
   stage: build
-  image: coqorg/coq:8.11.2-ocaml-4.11.1-flambda
+  image: coqorg/coq:8.12.2-ocaml-4.11.1-flambda
   before_script:
     - sudo apt-get -o Acquire::Check-Valid-Until=false -o Acquire::Check-Date=false update
     - sudo apt-get -y install gcc-powerpc64-linux-gnu
@@ -178,7 +178,7 @@ build_ppc64:
 
 build_rv64:
   stage: build
-  image: coqorg/coq:8.11.2-ocaml-4.11.1-flambda
+  image: coqorg/coq:8.12.2-ocaml-4.11.1-flambda
   before_script:
     - sudo apt-get -o Acquire::Check-Valid-Until=false -o Acquire::Check-Date=false update
     - sudo apt-get -y install gcc-riscv64-linux-gnu qemu-user
@@ -201,7 +201,7 @@ build_rv64:
 
 build_rv32:
   stage: build
-  image: coqorg/coq:8.11.2-ocaml-4.11.1-flambda
+  image: coqorg/coq:8.12.2-ocaml-4.11.1-flambda
   before_script:
     - sudo apt-get -o Acquire::Check-Valid-Until=false -o Acquire::Check-Date=false update
     - sudo apt-get -y install gcc-riscv64-linux-gnu qemu-user
@@ -222,7 +222,7 @@ build_rv32:
 
 build_kvx:
   stage: build
-  image: coqorg/coq:8.11.2-ocaml-4.11.1-flambda
+  image: coqorg/coq:8.12.2-ocaml-4.11.1-flambda
   before_script:
     - sudo apt-get -o Acquire::Check-Valid-Until=false -o Acquire::Check-Date=false update
     - sudo apt-get -y install sshpass openssh-client libzip4 lttng-tools liblttng-ctl-dev liblttng-ust-dev babeltrace
@@ -249,7 +249,7 @@ build_kvx:
 
 pages: # TODO: change to "deploy" when "build" succeeds (or integrate with "build_kvx" above ?)
   stage: build
-  image: coqorg/coq:8.11.2-ocaml-4.11.1-flambda
+  image: coqorg/coq:8.12.2-ocaml-4.11.1-flambda
   before_script:
     - sudo apt-get -o Acquire::Check-Valid-Until=false -o Acquire::Check-Date=false update
     - sudo apt-get -y install sshpass openssh-client libzip4 lttng-tools liblttng-ctl-dev liblttng-ust-dev babeltrace
diff --git a/configure b/configure
index 415dbb03..e63ff928 100755
--- a/configure
+++ b/configure
@@ -565,7 +565,7 @@ missingtools=false
 echo "Testing Coq... " | tr -d '\n'
 coq_ver=$(${COQBIN}coqc -v 2>/dev/null | sed -n -e 's/The Coq Proof Assistant, version \([^ ]*\).*$/\1/p')
 case "$coq_ver" in
-  8.8.0|8.8.1|8.8.2|8.9.0|8.9.1|8.10.0|8.10.1|8.10.2|8.11.0|8.11.1|8.11.2|8.12.0|8.12.1)
+  8.8.0|8.8.1|8.8.2|8.9.0|8.9.1|8.10.0|8.10.1|8.10.2|8.11.0|8.11.1|8.11.2|8.12.0|8.12.1|8.12.2)
         echo "version $coq_ver -- good!";;
   ?*)
         echo "version $coq_ver -- UNSUPPORTED"
diff --git a/doc/index-kvx.html b/doc/index-kvx.html
index b8850727..dc646a67 100644
--- a/doc/index-kvx.html
+++ b/doc/index-kvx.html
@@ -22,15 +22,17 @@ a:active {color : Red; text-decoration : underline; }
 </HEAD>
 <BODY>
 
-<font color=gray><H1 align="center">The CompCert verified compiler</H1>
+<font color=gray>
+<H1 align="center">The CompCert verified compiler</H1>
 <H2 align="center">Commented Coq development</H2>
-<H3 align="center">Version 3.7, 2020-03-31</H3></font>
+<H3 align="center">Version 3.8, 2020-11-16</H3>
+</font>
 <H3 align="center">PATCHED for the Kalray MPPA-KVX VLIW CORE<!--@DATE@--></H3>
 
 <H2>Introduction</H2>
 
-<p>This web page is a patched version of the table of contents of the official CompCert documentation,
-  as given on <A HREF="http://compcert.inria.fr/doc/index.html">the CompCert Web site</A>.
+<p>This web page is a patched version of the table of contents of the official CompCert sources documentation,
+  as given on <A HREF="http://compcert.org/doc/index.html">the CompCert Web site</A>.
   The unmodified parts of this table appear in <font color=gray>gray</font>.
   <br>
   <br>
@@ -40,7 +42,8 @@ a:active {color : Red; text-decoration : underline; }
   See also the <tt>README.md</tt> of our <a href=https://gricad-gitlab.univ-grenoble-alpes.fr/certicompil/compcert-kvx>GitLab public repository</a>.
 </p>
 
-<font color=gray><H2>Table of contents</H2>
+<font color=gray>
+<H2>Table of contents</H2>
 
 <H3>General-purpose libraries, data structures and algorithms</H3>
 
@@ -85,6 +88,8 @@ See also: <A HREF="html/compcert.common.Memdata.html">Memdata</A> (in-memory rep
 <LI> <A HREF="html/compcert.common.Determinism.html">Determinism</A>: determinism properties of small-step semantics.
 <LI> <A HREF="html/compcert.kvx.Op.html"><I>Op</I></A>: operators, addressing modes and their
 semantics.
+<LI> <A HREF="html/compcert.common.Builtins.html">Builtins</A>: semantics of built-in functions. <BR>
+See also: <A HREF="html/compcert.common.Builtins0.html">Builtins0</A> (target-independent part), <A HREF="html/compcert.kvx.Builtins1.html"><I>Builtins1</I></A> (target-dependent part).
 <LI> <A HREF="html/compcert.common.Unityping.html">Unityping</A>: a solver for atomic unification constraints.
 </UL>
 
@@ -123,6 +128,8 @@ view of the activation record.
 </font>
 <H4>Languages introduced for KVX core</H4>
 <UL>
+  <LI> <A HREF="html/compcert.scheduling.RTLpath.html">RTLpath</A>: extends RTL with annotations for delimitating superblocks (with possible liveness information).
+    This IR is generic over the processor, and used for prepass scheduling.
 <LI> <A HREF="html/compcert.kvx.lib.Machblock.html">Machblock</A>: a variant of Mach, with a syntax for basic-blocks, and a block-step semantics (execute one basic-block in one step).
 This IR is generic over the processor, even if currently, only used for KVX.
 <LI> <A HREF="html/compcert.kvx.Asmvliw.html"><I>Asmvliw</I></A>: abstract syntax and semantics for KVX VLIW assembly: atomic instructions are grouped by "bundles". These bundles are executed sequentially, but execution is parallel within bundles.
@@ -131,14 +138,14 @@ This IR is generic over the processor, even if currently, only used for KVX.
 <LI> <A HREF="html/compcert.kvx.Asm.html"><I>Asm</I></A>: a variant of Asmvliw with a flat syntax for bundles, instead of a structured one (bundle termination is encoded as a pseudo-instruction). This IR is mainly a wrapper of <I>Asmvliw</I> for a smooth integration in CompCert (and an easier pretty-printing of the abstract syntax).
 </UL>
 
-<font color=gray><H3>Compiler passes</H3></font>
+<H3>Compiler passes</H3>
 
 <TABLE cellpadding="5%" style="color:#808080">
 <TR valign="top">
-  <TH>Pass</TH>
-  <TH>Source &amp; target</TH>
-  <TH>Compiler&nbsp;code</TH>
-  <TH>Correctness&nbsp;proof</TH>
+  <TH align=left>Pass</TH>
+  <TH align=left>Source &amp; target</TH>
+  <TH align=left>Compiler&nbsp;code</TH>
+  <TH align=left>Correctness&nbsp;proof</TH>
 </TR>
 
 <TR valign="top">
@@ -172,7 +179,8 @@ This IR is generic over the processor, even if currently, only used for KVX.
 </TR>
 
 <TR valign="top">
-  <TD>Recognition of operators<br>and addressing modes</TD>
+  <TD>Recognition of operators<br>and addressing modes;<br>
+      if-conversion</TD>
   <TD>Cminor to CminorSel</TD>
   <TD><A HREF="html/compcert.backend.Selection.html">Selection</A><br>
       <A HREF="html/compcert.kvx.SelectOp.html"><I>SelectOp</I></A><br>
@@ -215,16 +223,6 @@ This IR is generic over the processor, even if currently, only used for KVX.
   <TD><A HREF="html/compcert.backend.Renumber.html">Renumber</A></TD>
   <TD><A HREF="html/compcert.backend.Renumberproof.html">Renumberproof</A></TD>
 </TR>
-
-<TR valign="top">
-  <TD>Constant propagation</TD>
-  <TD>RTL to RTL</TD>
-  <TD><A HREF="html/compcert.backend.Constprop.html">Constprop</A><br>
-      <A HREF="html/compcert.kvx.ConstpropOp.html"><I>ConstpropOp</I></A></TD>
-  <TD><A HREF="html/compcert.backend.Constpropproof.html">Constpropproof</A><br>
-      <A HREF="html/compcert.kvx.ConstpropOpproof.html"><I>ConstproppOproof</I></A></TD>
-</TR>
-
 <TR valign="top">
   <TD>Common subexpression elimination</TD>
   <TD>RTL to RTL</TD>
@@ -235,12 +233,19 @@ This IR is generic over the processor, even if currently, only used for KVX.
 </TR>
 
 <TR valign="top">
+  <TD>Constant propagation</TD>
+  <TD>RTL to RTL</TD>
+  <TD><A HREF="html/compcert.backend.Constprop.html">Constprop</A><br>
+      <A HREF="html/compcert.kvx.ConstpropOp.html"><I>ConstpropOp</I></A></TD>
+  <TD><A HREF="html/compcert.backend.Constpropproof.html">Constpropproof</A><br>
+      <A HREF="html/compcert.kvx.ConstpropOpproof.html"><I>ConstproppOproof</I></A></TD>
+</TR>
+<TR valign="top">
   <TD>Redundancy elimination</TD>
   <TD>RTL to RTL</TD>
   <TD><A HREF="html/compcert.backend.Deadcode.html">Deadcode</A></TD>
   <TD><A HREF="html/compcert.backend.Deadcodeproof.html">Deadcodeproof</A></TD>
 </TR>
-
 <TR valign="top">
   <TD>Removal of unused static globals</TD>
   <TD>RTL to RTL</TD>
@@ -248,6 +253,60 @@ This IR is generic over the processor, even if currently, only used for KVX.
   <TD><A HREF="html/compcert.backend.Unusedglobproof.html">Unusedglobproof</A></TD>
 </TR>
 
+<TR valign="top" style="color:#000000">
+  <TD colspan="4"><b>Passes introduced for profiling (for later use in trace selection)</b></TD>
+</TR>
+<TR valign="top" style="color:#000000">
+  <TD>Insert profiling annotations (for recording experiments -- see PROFILE.md).
+  </TD>
+  <TD>RTL to RTL</TD>
+  <TD><A HREF="html/compcert.backend.Profiling.html">Profiling</A></TD>
+  <TD><A HREF="html/compcert.backend.Profilingproof.html">Profilingproof</A></TD>
+</TR>
+<TR valign="top" style="color:#000000">
+  <TD>Update ICond nodes (from recorded experiments -- see PROFILE.md).
+  </TD>
+  <TD>RTL to RTL</TD>
+  <TD><A HREF="html/compcert.backend.ProfilingExploit.html">ProfilingExploit</A></TD>
+  <TD><A HREF="html/compcert.backend.ProfilingExploitproof.html">ProfilingExploitproof</A></TD>
+</TR>
+<TR valign="top" style="color:#000000">
+  <TD colspan="4"><b>Passes introduced for superblock prepass scheduling</b></TD>
+</TR>
+<TR valign="top" style="color:#000000">
+  <TD>Code duplications (trace selection, loop unrollings, etc)
+  </TD>
+  <TD>RTL to RTL</TD>
+  <TD><A HREF="html/compcert.backend.Duplicate.html">Duplicate</A> (generic checker)</TD>
+  <TD><A HREF="html/compcert.scheduling.Duplicateproof.html">Duplicateproof</A> (generic proof)<BR>
+    <a href="html/compcert.backend.Duplicatepasses.html">Duplicatepasses</a> (several passes from several oracles)</TD>
+</TR>
+<TR valign="top" style="color:#000000">
+  <TD>Superblock selection (with Liveness information)</TD>
+  <TD>RTL to RTLPath</TD>
+  <TD><A HREF="html/compcert.scheduling.RTLpathLivegen.html">RTLpathLivegen</A></TD>
+  <TD><A HREF="html/compcert.scheduling.RTLpathLivegenproof.html">RTLpathLivegenproof</A></TD>
+</TR>
+<TR valign="top" style="color:#000000">
+  <TD>Superblock prepass scheduling</TD>
+  <TD>RTLPath to RTLPath</TD>
+  <TD><A HREF="html/compcert.scheduling.RTLpathScheduler.html">RTLpathScheduler</A></TD>
+  <TD><A HREF="html/compcert.scheduling.RTLpathSchedulerproof.html">RTLpathSchedulerproof</A><BR>
+    with <A HREF="html/compcert.scheduling.RTLpathSE_theory.html">RTLpathSE_theory</A> (the theory of symbolic execution on RTLpath)<BR>
+    and <A HREF="html/compcert.scheduling.RTLpathSE_simu_specs.html">RTLpathSE_simu_specs</A> (the low-level specifications of the simulation checker)<BR>
+    and <A HREF="html/compcert.scheduling.RTLpathSE_impl.html">RTLpathSE_impl</A> (the simulation checker with hash-consing)</TD>
+</TR>
+<TR valign="top" style="color:#000000">
+  <TD>Forgeting superblocks</TD>
+  <TD>RTLPath to RTL</TD>
+  <TD><A HREF="html/compcert.scheduling.RTLpath.html#transf_program">RTLpath.transf_program</A></TD>
+  <TD><A HREF="html/compcert.scheduling.RTLpathproof.html">RTLpathproof</A></TD>
+</TR>
+
+<TR valign="top">
+  <TD colspan="4"><b>Passes from register allocation</b></TD>
+</TR>
+
 <TR valign="top">
   <TD>Register allocation (validation a posteriori)</TD>
   <TD>RTL to LTL</TD>
@@ -292,11 +351,11 @@ This IR is generic over the processor, even if currently, only used for KVX.
   <TD><A HREF="html/compcert.backend.Stackingproof.html">Stackingproof</A><br>
       <A HREF="html/compcert.common.Separation.html">Separation</A></TD>
 </TR>
-</TABLE>
 
-<H4>Compilation passes introduced for KVX VLIW</H4>
-<TABLE cellpadding="5%">
-<TR valign="top">
+<TR valign="top" style="color:#000000">
+  <TD colspan="4"><b>Passes introduced for KVX VLIW</b></TD>
+</TR>
+<TR valign="top" style="color:#000000">
   <TD>Reconstruction of basic-blocks at Mach level</TD>
   <TD>Mach to Machblock</TD>
   <TD><A HREF="html/compcert.kvx.lib.Machblockgen.html">Machblockgen</A></TD>
@@ -304,7 +363,7 @@ This IR is generic over the processor, even if currently, only used for KVX.
       <A HREF="html/compcert.kvx.lib.Machblockgenproof.html">Machblockgenproof</A></TD>
 </TR>
 
-<TR valign="top">
+<TR valign="top" style="color:#000000">
   <TD>Emission of purely sequential assembly code</TD>
   <TD>Machblock to Asmblock</TD>
   <TD><A HREF="html/compcert.kvx.Asmblockgen.html"><I>Asmblockgen</I></A></TD>
@@ -313,15 +372,16 @@ This IR is generic over the processor, even if currently, only used for KVX.
       <A HREF="html/compcert.kvx.Asmblockgenproof.html"><I>Asmblockgenproof</I></A></TD>
 </TR>
 
-<TR valign="top">
+<TR valign="top" style="color:#000000">
   <TD>Bundling (and basic-block scheduling)</TD>
   <TD>Asmblock to Asmvliw</TD>
-  <TD><A HREF="html/compcert.kvx.PostpassScheduling.html"><I>PostpassScheduling</I></A> using<BR>
-      <A HREF="html/compcert.kvx.Asmblockdeps.html"><I>Asmblockdeps</I></A> and the <tt>abstractbb</tt> library</TD>
+  <TD><A HREF="html/compcert.kvx.PostpassScheduling.html"><I>PostpassScheduling</I></A><BR>
+    using <A HREF="html/compcert.kvx.Asmblockdeps.html"><I>Asmblockdeps</I></A><BR>
+    and the <tt>abstractbb</tt> library</TD>
   <TD><A HREF="html/compcert.kvx.PostpassSchedulingproof.html"><I>PostpassSchedulingproof</I></A></TD>
 </TR>
 
-<TR valign="top">
+<TR valign="top" style="color:#000000">
   <TD>Flattening bundles (only a bureaucratic operation)</TD>
   <TD>Asmvliw to Asm</TD>
   <TD><A HREF="html/compcert.kvx.Asmgen.html"><I>Asmgen</I></A></TD>
@@ -329,12 +389,13 @@ This IR is generic over the processor, even if currently, only used for KVX.
 </TR>
 </TABLE>
 
-<font color=gray>
-<H3>All together</H3>
+<H3>All together (there are many more RTL passes than on vanilla CompCert: their order is specified in Compiler)</H3>
 
 <UL>
+</font>
 <LI> <A HREF="html/compcert.driver.Compiler.html">Compiler</A>: composing the passes together;
 whole-compiler semantic preservation theorems.
+<font color=gray>
 <LI> <A HREF="html/compcert.driver.Complements.html">Complements</A>: interesting consequences of the semantic preservation theorems.
 </UL>
 
diff --git a/kvx/Asmblockdeps.v b/kvx/Asmblockdeps.v
index 3d981100..67430b54 100644
--- a/kvx/Asmblockdeps.v
+++ b/kvx/Asmblockdeps.v
@@ -40,6 +40,10 @@ Require Import Chunks.
 
 Require Import Lia.
 
+
+Import ListNotations.
+Local Open Scope list_scope.
+
 Open Scope impure.
 
 (** Definition of [L] *)
@@ -706,19 +710,20 @@ Proof.
   destruct r; destruct r'.
   all: try discriminate; try contradiction.
   - intros. apply not_eq_add. apply ireg_to_pos_discr. congruence.
-  - intros. unfold ppos. cutrewrite (3 + ireg_to_pos g = (1 + ireg_to_pos g) + 2). apply Pos.add_no_neutral.
-    apply eq_sym. rewrite Pos.add_comm. rewrite Pos.add_assoc. reflexivity.
+  - intros. unfold ppos. replace (3 + ireg_to_pos g) with ((1 + ireg_to_pos g) + 2).
+    apply Pos.add_no_neutral.
+    rewrite Pos.add_comm, Pos.add_assoc. reflexivity.
   - intros. unfold ppos. rewrite Pos.add_comm. apply Pos.add_no_neutral.
   - intros. unfold ppos. apply not_eq_sym.
-    cutrewrite (3 + ireg_to_pos g = (1 + ireg_to_pos g) + 2). apply Pos.add_no_neutral.
-    apply eq_sym. rewrite Pos.add_comm. rewrite Pos.add_assoc. reflexivity.
+    replace (3 + ireg_to_pos g) with ((1 + ireg_to_pos g) + 2). apply Pos.add_no_neutral.
+    rewrite Pos.add_comm, Pos.add_assoc. reflexivity.
   - intros. unfold ppos. apply not_eq_sym. rewrite Pos.add_comm. apply Pos.add_no_neutral.
 Qed.
 
 Lemma ppos_pmem_discr: forall r, pmem <> ppos r.
 Proof.
   intros. destruct r.
-  - unfold ppos. unfold pmem. apply not_eq_sym. rewrite Pos.add_comm. cutrewrite (3 = 2 + 1). rewrite Pos.add_assoc. apply Pos.add_no_neutral.
+  - unfold ppos. unfold pmem. apply not_eq_sym. rewrite Pos.add_comm. replace 3 with (2 + 1). rewrite Pos.add_assoc. apply Pos.add_no_neutral.
     reflexivity.
   - unfold ppos. unfold pmem. discriminate.
   - unfold ppos. unfold pmem. discriminate.
@@ -1250,7 +1255,7 @@ Theorem bisimu_par_exit ex sz ge fn rsr rsw mr mw sr sw:
 Proof.
   intros; unfold estep.
   exploit (bisimu_par_control ex sz rsw#PC ge fn rsr rsw mr mw sr sw); eauto.
-  cutrewrite (rsw # PC <- (rsw PC) = rsw); auto.
+  replace (rsw # PC <- (rsw PC)) with rsw; auto.
   apply extensionality. intros; destruct x; simpl; auto.
 Qed.
 
@@ -1461,8 +1466,8 @@ Proof.
   destruct H2 as (m2' & H2 & H4). discriminate. rewrite H2 in H3.
   destruct (exec_bblock ge fn p2 rs m); simpl in H3.
   * destruct H3 as (s' & H3 & H5 & H6). inv H3. inv MS'.
-    cutrewrite (rs0=rs1).
-    - cutrewrite (m0=m1); auto. congruence.
+    replace rs0 with rs1.
+    - replace m0 with m1; auto. congruence.
     - apply functional_extensionality. intros r.
       generalize (H0 r). intros Hr. congruence.
   * discriminate.
diff --git a/kvx/abstractbb/AbstractBasicBlocksDef.v b/kvx/abstractbb/AbstractBasicBlocksDef.v
index 6960f363..34d72de1 100644
--- a/kvx/abstractbb/AbstractBasicBlocksDef.v
+++ b/kvx/abstractbb/AbstractBasicBlocksDef.v
@@ -273,23 +273,26 @@ with list_term :=
 Scheme term_mut := Induction for term Sort Prop
 with list_term_mut := Induction for list_term Sort Prop.
 
+Declare Scope pattern_scope.
+Declare Scope term_scope.
 Bind Scope pattern_scope with term.
 Delimit Scope term_scope with term.
 Delimit Scope pattern_scope with pattern.
 
+Local Open Scope pattern_scope.
+
 Notation "[ ]" := (LTnil _) (format "[ ]"): pattern_scope.
-Notation "[ x ]" := (LTcons x [] _): pattern_scope.
+Notation "[ x ]" := (LTcons x [ ] _): pattern_scope.
 Notation "[ x ; y ; .. ; z ]" := (LTcons x (LTcons y .. (LTcons z (LTnil _) _) .. _) _): pattern_scope.
 Notation "o @ l" := (App o l _) (at level 50, no associativity): pattern_scope.
 
 Import HConsingDefs.
 
 Notation "[ ]" := (LTnil unknown_hid) (format "[ ]"): term_scope.
-Notation "[ x ]" := (LTcons x [] unknown_hid): term_scope.
+Notation "[ x ]" := (LTcons x []%term unknown_hid): term_scope.
 Notation "[ x ; y ; .. ; z ]" := (LTcons x (LTcons y .. (LTcons z (LTnil unknown_hid) unknown_hid) .. unknown_hid) unknown_hid): term_scope.
 Notation "o @ l" := (App o l unknown_hid) (at level 50, no associativity): term_scope.
 
-Local Open Scope pattern_scope.
 
 Fixpoint term_eval (ge: genv) (t: term) (m: mem): option value :=
   match t with
@@ -370,7 +373,7 @@ Qed.
 Hint Resolve intro_fail_correct: wlp.
 
 (** The default reduction of a term to a pseudo-term *) 
-Definition identity_fail (t: term):= intro_fail [t] t.
+Definition identity_fail (t: term):= intro_fail (t::nil) t.
 
 Lemma identity_fail_correct (t: term): match_pt t (identity_fail t).
 Proof.
@@ -382,8 +385,8 @@ Hint Resolve identity_fail_correct: wlp.
 (** The reduction for constant term *) 
 Definition nofail (is_constant: op -> bool) (t: term):=
     match t with
-    | Input x _ => intro_fail ([])%list t
-    | o @ [] => if is_constant o then (intro_fail ([])%list t) else (identity_fail t)
+    | Input x _ => intro_fail nil t
+    | o @ [] => if is_constant o then (intro_fail nil t) else (identity_fail t)
     | _ => identity_fail t
     end.
 
diff --git a/kvx/abstractbb/Parallelizability.v b/kvx/abstractbb/Parallelizability.v
index e5d21434..afa4b9fd 100644
--- a/kvx/abstractbb/Parallelizability.v
+++ b/kvx/abstractbb/Parallelizability.v
@@ -299,7 +299,7 @@ Proof.
   induction i as [|[y e] i']; cbn.
   - intros m tmp H x H0; inversion_clear H; auto.
   - intros m tmp H x (H1 & H2); destruct (exp_eval ge e tmp old); cbn; try congruence.
-    cutrewrite (m x = assign m y v x); eauto.
+    replace (m x) with (assign m y v x); eauto.
     rewrite assign_diff; auto.
 Qed.
 
@@ -514,13 +514,13 @@ Proof.
   induction i as [|[x e] i']; cbn; auto.
   intros m tmp1 tmp2; rewrite disjoint_cons_l, disjoint_app_l.
   intros (H1 & H2 & H3) H6 H7.
-  cutrewrite (exp_eval ge e tmp1 old1 = exp_eval ge e tmp2 old2).
+  replace (exp_eval ge e tmp1 old1) with (exp_eval ge e tmp2 old2).
   - destruct (exp_eval ge e tmp2 old2); auto.
     eapply IHi'; eauto. 
     cbn; intros x0 H0; unfold assign. destruct (R.eq_dec x x0); cbn; auto. 
   - unfold disjoint in H2; apply exp_frame_correct.
-    intros;apply H6; auto.
-    intros;apply H7; auto.
+    intros;rewrite H6; auto.
+    intros;rewrite H7; auto.
 Qed.
 
 (** * Parallelizability *)
diff --git a/kvx/lib/ForwardSimulationBlock.v b/kvx/lib/ForwardSimulationBlock.v
index 61466dad..cc6ecdd8 100644
--- a/kvx/lib/ForwardSimulationBlock.v
+++ b/kvx/lib/ForwardSimulationBlock.v
@@ -25,7 +25,7 @@ Require Import Coqlib.
 Require Import Events.
 Require Import Globalenvs.
 Require Import Smallstep.
-
+Require Import Lia.
 
 Local Open Scope nat_scope.
 
@@ -43,8 +43,8 @@ Lemma starN_split n s t s':
   exists (t1 t2:trace) s0, starN (step L) (globalenv L) m s t1 s0 /\ starN (step L) (globalenv L) k s0 t2 s' /\ t=t1**t2.
 Proof.
   induction 1; cbn.
-  + intros m k H; assert (X: m=0); try omega.
-    assert (X0: k=0); try omega.
+  + intros m k H; assert (X: m=0); try lia.
+    assert (X0: k=0); try lia.
     subst; repeat (eapply ex_intro); intuition eauto.
   + intros m; destruct m as [| m']; cbn.
     - intros k H2; subst; repeat (eapply ex_intro); intuition eauto.
@@ -119,10 +119,10 @@ Proof.
   intros t [H1 H2] H3 H4.
   destruct (simu_mid_block _ _ _ H3 H4) as [H5 H6]; subst. 
   constructor 1.
-  + omega.
-  + cutrewrite (dist_end_block head - dist_end_block next = S (dist_end_block head - dist_end_block previous)).
+  + lia.
+  + replace (dist_end_block head - dist_end_block next) with (S (dist_end_block head - dist_end_block previous)).
     - eapply starN_tailstep; eauto.
-    - omega.
+    - lia.
 Qed.
 
 Lemma follows_in_block_init (head current: state L1):
@@ -131,10 +131,10 @@ Proof.
   intros t H3 H4.
   destruct (simu_mid_block _ _ _ H3 H4) as [H5 H6]; subst. 
   constructor 1.
-  + omega.
-  + cutrewrite (dist_end_block head - dist_end_block current = 1).
+  + lia.
+  + replace (dist_end_block head - dist_end_block current) with 1.
     - eapply starN_tailstep; eauto.
-    - omega.
+    - lia.
 Qed.
 
 
@@ -156,10 +156,10 @@ Proof.
   destruct s as [rs ms Hs]. cbn.
   destruct ms as [ms|]; unfold head; cbn; auto.
   constructor 1.
-  omega.
-  cutrewrite ((dist_end_block rs - dist_end_block rs)%nat=O).
+  lia.
+  replace (dist_end_block rs - dist_end_block rs)%nat with O.
   + apply starN_refl; auto.
-  + omega.
+  + lia.
 Qed.
 
 Inductive is_well_memorized (s s': memostate): Prop :=
@@ -259,7 +259,7 @@ Proof.
       constructor 1.
       destruct (simu_end_block (head s1) t (real s1') s2) as (s2' & H3 & H4); auto.
       * destruct (head_followed s1) as [H4 H3].
-        cutrewrite (dist_end_block (head s1) - dist_end_block (real s1) = dist_end_block (head s1)) in H3; try omega.
+        replace (dist_end_block (head s1) - dist_end_block (real s1)) with (dist_end_block (head s1)) in H3; try lia.
         eapply starN_tailstep; eauto.
       * unfold head; rewrite H2; cbn. intuition eauto. 
 Qed.
diff --git a/kvx/lib/Machblockgen.v b/kvx/lib/Machblockgen.v
index 3d5d7b2c..5a2f2a61 100644
--- a/kvx/lib/Machblockgen.v
+++ b/kvx/lib/Machblockgen.v
@@ -155,11 +155,11 @@ Proof.
     + intros; eapply Tr_add_label; eauto. destruct i; cbn in * |- *; congruence.
     + intros. remember (header bh0) as hbh0. destruct hbh0 as [|b].
       * eapply Tr_add_basic; eauto.
-      * cutrewrite (add_basic bi empty_bblock = add_to_new_bblock (MB_basic bi)); auto.
+      * replace (add_basic bi empty_bblock) with (add_to_new_bblock (MB_basic bi)); auto.
         rewrite Heqti; eapply Tr_end_block; eauto.
         rewrite <- Heqti. eapply End_basic. congruence.
     + intros.
-      cutrewrite (cfi_bblock cfi = add_to_new_bblock (MB_cfi cfi)); auto.
+      replace (cfi_bblock cfi) with (add_to_new_bblock (MB_cfi cfi)); auto.
       rewrite Heqti. eapply Tr_end_block; eauto.
       rewrite <- Heqti. eapply End_cfi. congruence.
 Qed.