Correctness of instruction selection for operators
Require Import Coqlib.
Require Import AST.
Require Import Integers.
Require Import Floats.
Require Import Values.
Require Import Globalenvs.
Require Import Cminor.
Require Import Op.
Require Import CminorSel.
Require Import SelectOp.
Require Import Values_symbolictype.
Require Import Values_symbolic.
Open Local Scope cminorsel_scope.
Require Import NormaliseSpec.
Require Import ExprEval.
Require Import Memory.
Useful lemmas and tactics
The following are trivial lemmas and custom tactics that help
perform backward (inversion) and forward reasoning over the evaluation
of operator applications.
Ltac EvalOp :=
eapply eval_Eop;
eauto with evalexpr.
Ltac InvEval1 :=
match goal with
| [
H: (
eval_expr _ _ _ _ _ (
Eop _ Enil)
_) |-
_ ] =>
inv H;
InvEval1
| [
H: (
eval_expr _ _ _ _ _ (
Eop _ (
_ :::
Enil))
_) |-
_ ] =>
inv H;
InvEval1
| [
H: (
eval_expr _ _ _ _ _ (
Eop _ (
_ :::
_ :::
Enil))
_) |-
_ ] =>
inv H;
InvEval1
| [
H: (
eval_exprlist _ _ _ _ _ Enil _) |-
_ ] =>
inv H;
InvEval1
| [
H: (
eval_exprlist _ _ _ _ _ (
_ :::
_)
_) |-
_ ] =>
inv H;
InvEval1
|
_ =>
idtac
end.
Ltac InvEval2 :=
match goal with
| [
H: (
eval_operation _ _ _ nil =
Some _) |-
_ ] =>
simpl in H;
inv H
| [
H: (
eval_operation _ _ _ (
_ ::
nil) =
Some _) |-
_ ] =>
simpl in H;
FuncInv
| [
H: (
eval_operation _ _ _ (
_ ::
_ ::
nil) =
Some _) |-
_ ] =>
simpl in H;
FuncInv
| [
H: (
eval_operation _ _ _ (
_ ::
_ ::
_ ::
nil) =
Some _) |-
_ ] =>
simpl in H;
FuncInv
|
_ =>
idtac
end.
Ltac InvEval :=
InvEval1;
InvEval2;
InvEval2.
Correctness of the smart constructors
Section CMCONSTR.
Variable ge:
genv.
Variable sp:
expr_sym.
Variable e:
env.
Variable m:
mem.
We now show that the code generated by "smart constructor" functions
such as
SelectOp.notint behaves as expected. Continuing the
notint example, we show that if the expression
e
evaluates to some integer value
Vint n, then
SelectOp.notint e
evaluates to a value
Vint (Int.not n) which is indeed the integer
negation of the value of
e.
All proofs follow a common pattern:
-
Reasoning by case over the result of the classification functions
(such as add_match for integer addition), gathering additional
information on the shape of the argument expressions in the non-default
cases.
-
Inversion of the evaluations of the arguments, exploiting the additional
information thus gathered.
-
Equational reasoning over the arithmetic operations performed,
using the lemmas from the Int and Float modules.
-
Construction of an evaluation derivation for the expression returned
by the smart constructor.
Definition unary_constructor_sound (
cstr:
expr ->
expr) (
sem:
expr_sym ->
expr_sym) :
Prop :=
forall le a x
(
EXPR:
eval_expr ge sp e m le a x)
,
exists v,
eval_expr ge sp e m le (
cstr a)
v
/\
Val.lessdef (
sem x)
v.
Definition binary_constructor_sound (
cstr:
expr ->
expr ->
expr) (
sem:
expr_sym ->
expr_sym ->
expr_sym) :
Prop :=
forall le a x b y
(
EXPR1:
eval_expr ge sp e m le a x)
(
EXPR2:
eval_expr ge sp e m le b y),
exists v,
eval_expr ge sp e m le (
cstr a b)
v
/\
Val.lessdef (
sem x y)
v.
Ltac TrivialExists :=
eexists;
split; [
repeat (
econstructor;
simpl;
eauto)|
eauto;
try solve[
constructor;
simpl;
auto]].
Theorem eval_addrsymbol:
forall le id ofs b'
o',
Genv.symbol_address'
ge id ofs =
Some (
Eval (
Vptr b'
o')) ->
exists v,
eval_expr ge sp e m le (
addrsymbol id ofs)
v/\
same_eval v (
Eval (
Vptr b'
o')).
Proof.
intros.
unfold addrsymbol.
destr_cond_match.
destr_cond_match.
-
apply Cop.int_eq_true in Heqb0 .
subst;
auto.
eexists;
split.
econstructor;
eauto.
econstructor;
eauto.
simpl.
unfold Genv.symbol_address'
in *.
des (
Genv.find_symbol ge id).
inv H.
eauto.
unfold Genv.symbol_address'
in *.
des (
Genv.find_symbol ge id).
-
eexists;
split.
repeat (
econstructor;
simpl;
eauto);
simpl.
unfold Genv.symbol_address'
in *.
des (
Genv.find_symbol ge id).
inv H.
eauto.
unfold Genv.symbol_address'
in *.
des (
Genv.find_symbol ge id).
inv H.
red;
intros;
simpl.
rewrite Int.add_zero;
auto.
-
eexists;
split.
repeat (
econstructor;
simpl;
eauto);
simpl.
rewrite H.
eauto.
reflexivity.
Qed.
Theorem eval_addrstack:
forall le ofs,
exists v,
eval_expr ge sp e m le (
addrstack ofs)
v /\
same_eval (
Val.add sp (
Eval (
Vint ofs)))
v.
Proof.
intros.
unfold addrstack.
econstructor;
split.
EvalOp.
simpl;
eauto.
reflexivity.
Qed.
Theorem eval_notint:
unary_constructor_sound notint Val.notint.
Proof.
unfold notint;
red;
intros until x.
destr;
InvEval.
-
TrivialExists.
-
TrivialExists.
ld.
unfold Int.not.
subst.
rewrite <-
Int.xor_assoc;
auto.
-
TrivialExists.
Qed.
Theorem eval_addimm:
forall n,
unary_constructor_sound (
addimm n) (
fun x =>
Val.add x (
Eval (
Vint n))).
Proof.
red;
unfold addimm;
intros until x.
intros.
destr;
InvEval;
ld.
-
eexists;
split;
eauto.
apply Cop.int_eq_true in Heqb.
subst.
ld;
rewrite Int.add_zero;
auto.
-
destr.
+ (
eexists;
split; [
repeat econstructor;
simpl;
eauto|]).
inv EXPR.
simpl in *.
des vl.
inv H4.
ld.
rewrite Int.add_commut;
auto.
+
inv EXPR.
eapply eval_offset_addressing_total in H4;
eauto.
destruct H4 as [
e0 [
A B]].
intros.
TrivialExists.
red;
intros.
rewrite B.
constructor.
+
TrivialExists.
Qed.
Theorem eval_add:
binary_constructor_sound add Val.add.
Proof.
red;
intros until y.
unfold add;
case (
add_match a b);
intros;
InvEval.
-
generalize (
eval_addimm n1 le t2 y EXPR2).
intros [
v [
A B]].
eexists;
split;
eauto.
red;
intros;
specialize (
B alloc em);
inv B;
simpl;
seval;
try constructor.
rewrite Int.add_commut.
auto.
-
generalize (
eval_addimm n2 le t1 x EXPR1).
intros [
v [
A B]].
eexists;
split;
eauto.
-
eexists;
split; [
repeat (
econstructor;
simpl;
eauto)|].
subst.
red;
intros;
simpl;
seval;
try constructor;
apply Val.lessdef_same;
sint;
rewrite Int.add_commut;
sint.
-
eexists;
split; [
repeat (
econstructor;
simpl;
eauto)|].
subst.
red;
intros;
simpl;
seval;
try constructor;
apply Val.lessdef_same;
sint;
rewrite Int.add_commut;
sint.
-
eexists;
split; [
repeat (
econstructor;
simpl;
eauto)|].
subst.
red;
intros;
simpl;
seval;
try constructor;
apply Val.lessdef_same;
sint;
repeat (
rewrite Int.add_commut;
sint).
-
unfold Genv.symbol_address'
in *.
des (
Genv.find_symbol ge id).
inv H0.
eexists;
split; [
repeat (
econstructor;
simpl;
eauto)|];
simpl.
unfold Genv.symbol_address'.
rewrite Heqo.
simpl.
eauto.
red;
intros;
simpl;
seval;
try constructor;
apply Val.lessdef_same;
sint;
repeat (
rewrite Int.add_commut;
sint).
-
unfold Genv.symbol_address'
in *.
des (
Genv.find_symbol ge id).
inv H0.
eexists;
split; [
repeat (
econstructor;
simpl;
eauto)|];
simpl.
unfold Genv.symbol_address'.
rewrite Heqo.
simpl;
eauto.
red;
intros;
simpl;
seval;
try constructor;
apply Val.lessdef_same;
sint;
repeat (
rewrite Int.add_commut;
sint).
-
unfold Genv.symbol_address'
in *.
des (
Genv.find_symbol ge id).
inv H0.
eexists;
split; [
repeat (
econstructor;
simpl;
eauto)|];
simpl.
unfold Genv.symbol_address'.
rewrite Heqo.
simpl;
eauto.
red;
intros;
simpl;
seval;
try constructor;
apply Val.lessdef_same;
sint;
repeat (
rewrite Int.add_commut;
sint).
-
unfold Genv.symbol_address'
in *.
des (
Genv.find_symbol ge id).
inv H0.
eexists;
split; [
repeat (
econstructor;
simpl;
eauto)|];
simpl.
unfold Genv.symbol_address'.
rewrite Heqo.
simpl;
eauto.
red;
intros;
simpl;
seval;
try constructor;
apply Val.lessdef_same;
sint;
repeat (
rewrite Int.add_commut;
sint).
-
subst.
eexists;
split; [
repeat (
econstructor;
simpl;
eauto)|];
simpl.
red;
intros;
simpl;
seval;
try constructor;
apply Val.lessdef_same;
sint;
repeat (
rewrite Int.add_commut;
sint).
-
subst.
eexists;
split; [
repeat (
econstructor;
simpl;
eauto)|];
simpl.
constructor;
simpl;
eauto.
-
subst.
eexists;
split; [
repeat (
econstructor;
simpl;
eauto)|];
simpl.
red;
intros;
simpl;
seval;
try constructor;
apply Val.lessdef_same;
sint;
repeat (
rewrite Int.add_commut;
sint).
-
subst.
eexists;
split; [
repeat (
econstructor;
simpl;
eauto)|];
simpl.
red;
intros;
simpl;
seval;
try constructor;
apply Val.lessdef_same;
sint;
repeat (
rewrite Int.add_commut;
sint).
-
eexists;
split; [
repeat (
econstructor;
simpl;
eauto)|];
simpl.
red;
intros;
simpl;
seval;
try constructor;
rewrite Int.add_zero;
constructor.
Qed.
Theorem eval_sub:
binary_constructor_sound sub Val.sub.
Proof.
Theorem eval_negint:
unary_constructor_sound negint Val.negint.
Proof.
red;
intros until x.
unfold negint.
case (
negint_match a);
intros;
InvEval.
-
eexists;
split; [
repeat (
econstructor;
simpl;
eauto)|
eauto].
constructor;
simpl;
auto.
-
eexists;
split; [
repeat (
econstructor;
simpl;
eauto)|
eauto].
Qed.
Theorem eval_shlimm:
forall n,
unary_constructor_sound (
fun a =>
shlimm a n)
(
fun x =>
Val.shl x (
Eval (
Vint n))).
Proof.
Theorem eval_shruimm:
forall n,
unary_constructor_sound (
fun a =>
shruimm a n)
(
fun x =>
Val.shru x (
Eval (
Vint n))).
Proof.
Theorem eval_shrimm:
forall n,
unary_constructor_sound (
fun a =>
shrimm a n)
(
fun x =>
Val.shr x (
Eval (
Vint n))).
Proof.
Lemma eval_mulimm_base:
forall n,
unary_constructor_sound (
mulimm_base n) (
fun x =>
Val.mul x (
Eval (
Vint n))).
Proof.
Theorem eval_mulimm:
forall n,
unary_constructor_sound (
mulimm n) (
fun x =>
Val.mul x (
Eval (
Vint n))).
Proof.
Theorem eval_mul:
binary_constructor_sound mul Val.mul.
Proof.
Theorem eval_andimm:
forall n,
unary_constructor_sound (
andimm n) (
fun x =>
Val.and x (
Eval (
Vint n))).
Proof.
Theorem eval_and:
binary_constructor_sound and Val.and.
Proof.
Theorem eval_orimm:
forall n,
unary_constructor_sound (
orimm n) (
fun x =>
Val.or x (
Eval (
Vint n))).
Proof.
Remark eval_same_expr:
forall a1 a2 le v1 v2,
same_expr_pure a1 a2 =
true ->
eval_expr ge sp e m le a1 v1 ->
eval_expr ge sp e m le a2 v2 ->
a1 =
a2 /\
v1 =
v2.
Proof.
intros until v2.
destruct a1;
simpl;
try (
intros;
discriminate).
destruct a2;
simpl;
try (
intros;
discriminate).
case (
ident_eq i i0);
intros.
subst i0.
inversion H0.
inversion H1.
split.
auto.
congruence.
discriminate.
Qed.
Remark int_add_sub_eq:
forall x y z,
Int.add x y =
z ->
Int.sub z x =
y.
Proof.
Lemma eval_or:
binary_constructor_sound or Val.or.
Proof.
Theorem eval_xorimm:
forall n,
unary_constructor_sound (
xorimm n) (
fun x =>
Val.xor x (
Eval (
Vint n))).
Proof.
Theorem eval_xor:
binary_constructor_sound xor Val.xor.
Proof.
Theorem eval_divs_base:
binary_constructor_sound divs_base Val.divs.
Proof.
red;
intros.
unfold divs_base.
eexists;
split.
repeat (
econstructor;
simpl;
eauto).
auto.
Qed.
Theorem eval_divu_base:
binary_constructor_sound divu_base Val.divu.
Proof.
red;
intros.
unfold divu_base.
eexists;
split.
repeat (
econstructor;
simpl;
eauto).
auto.
Qed.
Theorem eval_mods_base:
binary_constructor_sound mods_base Val.mods.
Proof.
red;
intros.
unfold mods_base.
eexists;
split.
repeat (
econstructor;
simpl;
eauto).
auto.
Qed.
Theorem eval_modu_base:
binary_constructor_sound modu_base Val.modu.
Proof.
red;
intros.
unfold modu_base.
eexists;
split.
repeat (
econstructor;
simpl;
eauto).
auto.
Qed.
Theorem eval_shrximm:
forall n,
unary_constructor_sound (
fun x =>
shrximm x n) (
fun x =>
Val.shrx x (
Eval (
Vint n))) .
Proof.
Theorem eval_shl:
binary_constructor_sound shl Val.shl.
Proof.
red;
intros until y;
unfold shl;
case (
shl_match b);
intros.
-
InvEval.
apply eval_shlimm;
auto.
-
TrivialExists.
Qed.
Theorem eval_shr:
binary_constructor_sound shr Val.shr.
Proof.
red;
intros until y;
unfold shr;
case (
shr_match b);
intros.
-
InvEval.
apply eval_shrimm;
auto.
-
TrivialExists.
Qed.
Theorem eval_shru:
binary_constructor_sound shru Val.shru.
Proof.
Theorem eval_negf:
unary_constructor_sound negf Val.negf.
Proof.
red; intros. TrivialExists.
Qed.
Theorem eval_absf:
unary_constructor_sound absf Val.absf.
Proof.
red; intros. TrivialExists.
Qed.
Theorem eval_addf:
binary_constructor_sound addf Val.addf.
Proof.
red; intros; TrivialExists.
Qed.
Theorem eval_subf:
binary_constructor_sound subf Val.subf.
Proof.
red; intros; TrivialExists.
Qed.
Theorem eval_mulf:
binary_constructor_sound mulf Val.mulf.
Proof.
red; intros; TrivialExists.
Qed.
Theorem eval_negfs:
unary_constructor_sound negfs Val.negfs.
Proof.
red; intros. TrivialExists.
Qed.
Theorem eval_absfs:
unary_constructor_sound absfs Val.absfs.
Proof.
red; intros. TrivialExists.
Qed.
Theorem eval_addfs:
binary_constructor_sound addfs Val.addfs.
Proof.
red; intros; TrivialExists.
Qed.
Theorem eval_subfs:
binary_constructor_sound subfs Val.subfs.
Proof.
red; intros; TrivialExists.
Qed.
Theorem eval_mulfs:
binary_constructor_sound mulfs Val.mulfs.
Proof.
red; intros; TrivialExists.
Qed.
Section COMP_IMM.
Variable sg:
se_signedness.
Variable default:
comparison ->
int ->
condition.
Variable intsem:
comparison ->
int ->
int ->
bool.
Variable sem:
comparison ->
expr_sym ->
expr_sym ->
expr_sym.
Hypothesis sem_int:
forall x y c,
same_eval (
sem c (
Eval (
Vint x)) (
Eval (
Vint y)))
(
Val.of_bool (
intsem c x y)).
Hypothesis sem_default:
forall c x y ,
same_eval (
sem c x y) (
Ebinop (
OpCmp sg c)
Tint Tint x y).
Hypothesis default_eq:
default =
match sg with
SESigned =>
Ccompimm
|
SEUnsigned =>
Ccompuimm
end.
Lemma se_ld:
forall v1 v2,
same_eval v1 v2 ->
Val.lessdef v1 v2.
Proof.
intros v1 v2 A; red; intros.
rewrite A; auto.
Qed.
Lemma eval_compimm:
forall le c a n2 x,
eval_expr ge sp e m le a x ->
exists v,
eval_expr ge sp e m le (
compimm default intsem c a n2)
v
/\
Val.lessdef (
sem c x (
Eval (
Vint n2)))
v.
Proof.
Hypothesis sem_swap:
forall c x y,
same_eval (
sem (
swap_comparison c)
x y) (
sem c y x).
Lemma eval_compimm_swap:
forall le c a n2 x,
eval_expr ge sp e m le a x ->
exists v,
eval_expr ge sp e m le (
compimm default intsem (
swap_comparison c)
a n2)
v
/\
Val.lessdef (
sem c (
Eval (
Vint n2))
x)
v.
Proof.
intros.
exploit eval_compimm.
eauto.
intros [
v [
A B]].
eexists;
split.
eauto.
ldt.
red;
intros.
rewrite (
sem_swap c x (
Eval (
Vint n2))).
auto.
Qed.
End COMP_IMM.
Theorem eval_comp:
forall c,
binary_constructor_sound (
comp c) (
Val.cmp c).
Proof.
intros;
red;
intros until y.
unfold comp;
case (
comp_match a b);
intros;
InvEval.
-
eapply eval_compimm_swap with (
sg:=
SESigned);
eauto.
+
intros;
red;
simpl;
auto.
des (
Int.cmp c0 x y0).
+
intros;
red;
simpl;
intros;
seval.
+
intros;
red;
simpl;
intros;
seval.
rewrite Int.swap_cmp.
auto.
-
eapply eval_compimm with (
sg:=
SESigned);
eauto.
+
intros;
red;
simpl;
auto.
des (
Int.cmp c0 x0 y).
+
intros;
red;
simpl;
intros;
seval.
-
TrivialExists.
Qed.
Theorem eval_compu:
forall c,
binary_constructor_sound (
compu c) (
Val.cmpu c).
Proof.
Theorem eval_compf:
forall c,
binary_constructor_sound (
compf c) (
Val.cmpf c).
Proof.
intros;
red;
intros.
unfold compf.
TrivialExists.
Qed.
Theorem eval_compfs:
forall c,
binary_constructor_sound (
compfs c) (
Val.cmpfs c).
Proof.
intros;
red;
intros.
unfold compfs.
TrivialExists.
Qed.
Theorem eval_cast8signed:
unary_constructor_sound cast8signed (
Val.sign_ext 8).
Proof.
Theorem eval_cast8unsigned:
unary_constructor_sound cast8unsigned (
Val.zero_ext 8).
Proof.
Theorem eval_cast16signed:
unary_constructor_sound cast16signed (
Val.sign_ext 16).
Proof.
Theorem eval_cast16unsigned:
unary_constructor_sound cast16unsigned (
Val.zero_ext 16).
Proof.
Theorem eval_singleoffloat:
unary_constructor_sound singleoffloat Val.singleoffloat.
Proof.
Theorem eval_floatofsingle:
unary_constructor_sound floatofsingle Val.floatofsingle.
Proof.
Theorem eval_intoffloat:
unary_constructor_sound intoffloat Val.intoffloat.
Proof.
red;
intros;
unfold intoffloat.
TrivialExists.
Qed.
Theorem eval_floatofint:
unary_constructor_sound floatofint Val.floatofint.
Proof.
Theorem eval_intofsingle:
unary_constructor_sound intofsingle Val.intofsingle.
Proof.
Theorem eval_singleofint:
unary_constructor_sound singleofint Val.singleofint.
Proof.
Theorem eval_addressing:
forall ge le chunk a v ,
eval_expr ge sp e m le a v ->
wt_expr v Tint ->
match addressing chunk a with (
mode,
args) =>
exists vl v',
eval_exprlist ge sp e m le args vl /\
Op.eval_addressing ge sp mode vl =
Some v' /\
Val.lessdef v v'
end.
Proof.
intros until v.
unfold addressing;
case (
addressing_match a);
intros;
InvEval.
-
inv H.
exists vl;
exists v;
repeat split;
auto.
-
eexists;
eexists;
split.
+
constructor;
eauto.
econstructor.
+
subst;
simpl.
split;
eauto.
apply se_ld.
red;
simpl;
intros.
generalize (
expr_type _ _ H0 cm em).
seval.
rewrite Int.add_zero;
auto.
Qed.
End CMCONSTR.