Correctness of instruction selection for operators
Require Import Coqlib.
Require Import Maps.
Require Import AST.
Require Import Integers.
Require Import Floats.
Require Import Values.
Require Import Memory.
Require Import Events.
Require Import Globalenvs.
Require Import Smallstep.
Require Import Cminor.
Require Import Op.
Require Import CminorSel.
Require Import SelectOp.
Open Local Scope cminorsel_scope.
Section CMCONSTR.
Variable ge:
genv.
Variable sp:
val.
Variable e:
env.
Variable m:
mem.
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.
Ltac TrivialExists :=
match goal with
| [ |-
exists v,
_ /\
Val.lessdef ?
a v ] =>
exists a;
split; [
EvalOp |
auto]
end.
Correctness of the smart constructors
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.
(
cstr:
expr ->
expr) (
sem:
val ->
val) :
Prop :=
forall le a x,
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:
val ->
val ->
val) :
Prop :=
forall le a x b y,
eval_expr ge sp e m le a x ->
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.
Theorem eval_addrsymbol:
forall le id ofs,
exists v,
eval_expr ge sp e m le (
addrsymbol id ofs)
v /\
Val.lessdef (
symbol_address ge id ofs)
v.
Proof.
intros. unfold addrsymbol. econstructor; split.
EvalOp. simpl; eauto.
auto.
Qed.
Theorem eval_addrstack:
forall le ofs,
exists v,
eval_expr ge sp e m le (
addrstack ofs)
v /\
Val.lessdef (
Val.add sp (
Vint ofs))
v.
Proof.
intros. unfold addrstack. econstructor; split.
EvalOp. simpl; eauto.
auto.
Qed.
Theorem eval_notint:
unary_constructor_sound notint Val.notint.
Proof.
unfold notint; red; intros. TrivialExists.
Qed.
Theorem eval_boolval:
unary_constructor_sound boolval Val.boolval.
Proof.
assert (
DFL:
forall le a x,
eval_expr ge sp e m le a x ->
exists v,
eval_expr ge sp e m le (
Eop (
Ocmp (
Ccompuimm Cne Int.zero)) (
a :::
Enil))
v
/\
Val.lessdef (
Val.boolval x)
v).
intros.
TrivialExists.
simpl.
destruct x;
simpl;
auto.
red.
induction a;
simpl;
intros;
eauto.
destruct o;
eauto.
destruct e0;
eauto.
InvEval.
TrivialExists.
simpl.
destruct (
Int.eq i Int.zero);
auto.
inv H.
simpl in H5.
destruct (
eval_condition c vl m)
as []
_eqn.
TrivialExists.
simpl.
inv H5.
rewrite Heqo.
destruct b;
auto.
simpl in H5.
inv H5.
exists Vundef;
split;
auto.
EvalOp;
simpl.
rewrite Heqo;
auto.
inv H.
destruct v1.
exploit IHa1;
eauto.
intros [
v [
A B]].
exists v;
split;
auto.
eapply eval_Econdition;
eauto.
exploit IHa2;
eauto.
intros [
v [
A B]].
exists v;
split;
auto.
eapply eval_Econdition;
eauto.
Qed.
Theorem eval_notbool:
unary_constructor_sound notbool Val.notbool.
Proof.
Lemma shift_symbol_address:
forall id ofs n,
symbol_address ge id (
Int.add ofs n) =
Val.add (
symbol_address ge id ofs) (
Vint n).
Proof.
Lemma eval_offset_addressing:
forall addr n args v,
eval_addressing ge sp addr args =
Some v ->
eval_addressing ge sp (
offset_addressing addr n)
args =
Some (
Val.add v (
Vint n)).
Proof.
Theorem eval_addimm:
forall n,
unary_constructor_sound (
addimm n) (
fun x =>
Val.add x (
Vint n)).
Proof.
Theorem eval_add:
binary_constructor_sound add Val.add.
Proof.
Theorem eval_sub:
binary_constructor_sound sub Val.sub.
Proof.
Theorem eval_negint:
unary_constructor_sound negint (
fun v =>
Val.sub Vzero v).
Proof.
red; intros. unfold negint. TrivialExists.
Qed.
Theorem eval_shlimm:
forall n,
unary_constructor_sound (
fun a =>
shlimm a n)
(
fun x =>
Val.shl x (
Vint n)).
Proof.
Theorem eval_shruimm:
forall n,
unary_constructor_sound (
fun a =>
shruimm a n)
(
fun x =>
Val.shru x (
Vint n)).
Proof.
Theorem eval_shrimm:
forall n,
unary_constructor_sound (
fun a =>
shrimm a n)
(
fun x =>
Val.shr x (
Vint n)).
Proof.
Lemma eval_mulimm_base:
forall n,
unary_constructor_sound (
mulimm_base n) (
fun x =>
Val.mul x (
Vint n)).
Proof.
Theorem eval_mulimm:
forall n,
unary_constructor_sound (
mulimm n) (
fun x =>
Val.mul x (
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 (
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 (
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.
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 (
Vint n)).
Proof.
Theorem eval_xor:
binary_constructor_sound xor Val.xor.
Proof.
Theorem eval_divs:
forall le a b x y z,
eval_expr ge sp e m le a x ->
eval_expr ge sp e m le b y ->
Val.divs x y =
Some z ->
exists v,
eval_expr ge sp e m le (
divs a b)
v /\
Val.lessdef z v.
Proof.
intros. unfold divs. exists z; split. EvalOp. auto.
Qed.
Theorem eval_divu:
forall le a b x y z,
eval_expr ge sp e m le a x ->
eval_expr ge sp e m le b y ->
Val.divu x y =
Some z ->
exists v,
eval_expr ge sp e m le (
divu a b)
v /\
Val.lessdef z v.
Proof.
intros. unfold divu. exists z; split. EvalOp. auto.
Qed.
Theorem eval_mods:
forall le a b x y z,
eval_expr ge sp e m le a x ->
eval_expr ge sp e m le b y ->
Val.mods x y =
Some z ->
exists v,
eval_expr ge sp e m le (
mods a b)
v /\
Val.lessdef z v.
Proof.
intros. unfold mods. exists z; split. EvalOp. auto.
Qed.
Theorem eval_modu:
forall le a b x y z,
eval_expr ge sp e m le a x ->
eval_expr ge sp e m le b y ->
Val.modu x y =
Some z ->
exists v,
eval_expr ge sp e m le (
modu a b)
v /\
Val.lessdef z v.
Proof.
intros. unfold modu. exists z; split. EvalOp. auto.
Qed.
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.
red;
intros until y;
unfold shru;
case (
shru_match b);
intros.
InvEval.
apply eval_shruimm;
auto.
TrivialExists.
Qed.
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_divf:
binary_constructor_sound divf Val.divf.
Proof.
red; intros; TrivialExists.
Qed.
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.
TrivialExists.
simpl.
rewrite Val.swap_cmp_bool.
auto.
TrivialExists.
TrivialExists.
Qed.
Theorem eval_compu:
forall c,
binary_constructor_sound (
compu c) (
Val.cmpu (
Mem.valid_pointer m)
c).
Proof.
intros;
red;
intros until y.
unfold compu;
case (
compu_match a b);
intros;
InvEval.
TrivialExists.
simpl.
rewrite Val.swap_cmpu_bool.
auto.
TrivialExists.
TrivialExists.
Qed.
Theorem eval_compf:
forall c,
binary_constructor_sound (
compf c) (
Val.cmpf c).
Proof.
intros; red; intros. unfold compf. TrivialExists.
Qed.
Theorem eval_cast8signed:
unary_constructor_sound cast8signed (
Val.sign_ext 8).
Proof.
red; intros. unfold cast8signed. TrivialExists.
Qed.
Theorem eval_cast8unsigned:
unary_constructor_sound cast8unsigned (
Val.zero_ext 8).
Proof.
Theorem eval_cast16signed:
unary_constructor_sound cast16signed (
Val.sign_ext 16).
Proof.
red; intros. unfold cast16signed. TrivialExists.
Qed.
Theorem eval_cast16unsigned:
unary_constructor_sound cast16unsigned (
Val.zero_ext 16).
Proof.
Theorem eval_singleoffloat:
unary_constructor_sound singleoffloat Val.singleoffloat.
Proof.
red; intros. unfold singleoffloat. TrivialExists.
Qed.
Theorem eval_intoffloat:
forall le a x y,
eval_expr ge sp e m le a x ->
Val.intoffloat x =
Some y ->
exists v,
eval_expr ge sp e m le (
intoffloat a)
v /\
Val.lessdef y v.
Proof.
intros; unfold intoffloat. TrivialExists.
Qed.
Theorem eval_floatofint:
forall le a x y,
eval_expr ge sp e m le a x ->
Val.floatofint x =
Some y ->
exists v,
eval_expr ge sp e m le (
floatofint a)
v /\
Val.lessdef y v.
Proof.
intros; unfold floatofint. TrivialExists.
Qed.
Theorem eval_intuoffloat:
forall le a x y,
eval_expr ge sp e m le a x ->
Val.intuoffloat x =
Some y ->
exists v,
eval_expr ge sp e m le (
intuoffloat a)
v /\
Val.lessdef y v.
Proof.
Theorem eval_floatofintu:
forall le a x y,
eval_expr ge sp e m le a x ->
Val.floatofintu x =
Some y ->
exists v,
eval_expr ge sp e m le (
floatofintu a)
v /\
Val.lessdef y v.
Proof.
Theorem eval_addressing:
forall le chunk a v b ofs,
eval_expr ge sp e m le a v ->
v =
Vptr b ofs ->
match addressing chunk a with (
mode,
args) =>
exists vl,
eval_exprlist ge sp e m le args vl /\
eval_addressing ge sp mode vl =
Some v
end.
Proof.
intros until v.
unfold addressing;
case (
addressing_match a);
intros;
InvEval.
inv H.
exists vl;
auto.
exists (
v ::
nil);
split.
constructor;
auto.
constructor.
subst;
simpl.
rewrite Int.add_zero;
auto.
Qed.
Theorem eval_cond_of_expr:
forall le a v b,
eval_expr ge sp e m le a v ->
Val.bool_of_val v b ->
match cond_of_expr a with (
cond,
args) =>
exists vl,
eval_exprlist ge sp e m le args vl /\
eval_condition cond vl m =
Some b
end.
Proof.
intros until v.
unfold cond_of_expr;
case (
cond_of_expr_match a);
intros;
InvEval.
subst v.
exists (
v1 ::
nil);
split;
auto with evalexpr.
simpl.
destruct b.
generalize (
Val.bool_of_true_val2 _ H0);
clear H0;
intro ISTRUE.
destruct v1;
simpl in ISTRUE;
try contradiction.
rewrite Int.eq_false;
auto.
generalize (
Val.bool_of_false_val2 _ H0);
clear H0;
intro ISFALSE.
destruct v1;
simpl in ISFALSE;
try contradiction.
rewrite ISFALSE.
rewrite Int.eq_true;
auto.
exists (
v ::
nil);
split;
auto with evalexpr.
simpl.
inversion H0;
simpl.
rewrite Int.eq_false;
auto.
auto.
auto.
Qed.
End CMCONSTR.