Correctness of instruction selection for operators
Require Import Coqlib.
Require Import AST.
Require Import Integers.
Require Import Floats.
Require Import Values.
Require Import Memory.
Require Import Globalenvs.
Require Import Cminor.
Require Import Op.
Require Import CminorSel.
Require Import SelectOp.
Local Open Scope cminorsel_scope.
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;
FuncInv
| [
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;
subst.
Ltac TrivialExists :=
match goal with
| [ |-
exists v,
_ /\
Val.lessdef ?
a v ] =>
exists a;
split; [
EvalOp |
auto]
end.
Correctness of the smart constructors
Section CMCONSTR.
Variable ge:
genv.
Variable sp:
val.
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.
(
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.
Lemma eval_Olea_ptr:
forall a el m,
eval_operation ge sp (
Olea_ptr a)
el m =
eval_addressing ge sp a el.
Proof.
Theorem eval_addrsymbol:
forall le id ofs,
exists v,
eval_expr ge sp e m le (
addrsymbol id ofs)
v /\
Val.lessdef (
Genv.symbol_address ge id ofs)
v.
Proof.
Theorem eval_addrstack:
forall le ofs,
exists v,
eval_expr ge sp e m le (
addrstack ofs)
v /\
Val.lessdef (
Val.offset_ptr sp ofs)
v.
Proof.
intros.
unfold addrstack.
TrivialExists.
Qed.
Theorem eval_notint:
unary_constructor_sound notint Val.notint.
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 Val.neg.
Proof.
red;
intros until x.
unfold negint.
case (
negint_match a);
intros;
InvEval.
-
TrivialExists.
-
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.
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 (
Vint n)).
Proof.
Theorem eval_xor:
binary_constructor_sound xor Val.xor.
Proof.
Theorem eval_divs_base:
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_base a b)
v /\
Val.lessdef z v.
Proof.
intros.
unfold divs_base.
exists z;
split.
EvalOp.
auto.
Qed.
Theorem eval_divu_base:
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_base a b)
v /\
Val.lessdef z v.
Proof.
intros.
unfold divu_base.
exists z;
split.
EvalOp.
auto.
Qed.
Theorem eval_mods_base:
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_base a b)
v /\
Val.lessdef z v.
Proof.
intros.
unfold mods_base.
exists z;
split.
EvalOp.
auto.
Qed.
Theorem eval_modu_base:
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_base a b)
v /\
Val.lessdef z v.
Proof.
intros.
unfold modu_base.
exists z;
split.
EvalOp.
auto.
Qed.
Theorem eval_shrximm:
forall le a n x z,
eval_expr ge sp e m le a x ->
Val.shrx x (
Vint n) =
Some z ->
exists v,
eval_expr ge sp e m le (
shrximm a n)
v /\
Val.lessdef z v.
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.
My Modification:
stop using Val.cmpu, use option_map Val.of_bool Val.cmpu_bool instead.
Section COMP_IMM_OPT.
Variable default:
comparison ->
int ->
condition.
Variable intsem:
comparison ->
int ->
int ->
bool.
Variable sem:
comparison ->
val ->
val ->
option val.
Hypothesis sem_int:
forall c x y,
sem c (
Vint x) (
Vint y) =
Some (
Val.of_bool (
intsem c x y)).
Hypothesis sem_eq:
forall x y,
sem Ceq (
Vint x) (
Vint y) =
Some (
Val.of_bool (
Int.eq x y)).
Hypothesis sem_ne:
forall x y,
sem Cne (
Vint x) (
Vint y) =
Some (
Val.of_bool (
negb (
Int.eq x y))).
Hypothesis sem_default:
forall c v n,
sem c v (
Vint n) =
option_map Val.of_bool (
eval_condition (
default c n) (
v ::
nil)
m).
Lemma eval_compimm_opt:
forall le c a n2 x y,
eval_expr ge sp e m le a x ->
sem c x (
Vint n2) =
Some y ->
exists v,
eval_expr ge sp e m le (
compimm default intsem c a n2)
v
/\
Val.lessdef y v.
Proof.
intros until x.
unfold compimm;
case (
compimm_match c a);
intros ? ?
y EVAL RES.
-
InvEval.
rewrite sem_int in RES.
TrivialExists.
simpl.
destruct (
intsem c0 n1 n2);
auto.
-
InvEval.
inv EVAL.
simpl in H4.
destruct (
Int.eq_dec n2 Int.zero).
subst n2.
TrivialExists.
simpl.
rewrite eval_negate_condition.
destruct (
eval_condition c0 vl m);
simpl in *; [|
discriminate].
destruct b;
inv H4;
simpl;
unfold Vtrue,
Vfalse in *;
rewrite sem_eq in RES;
auto.
destruct (
Int.eq_dec n2 Int.one).
subst n2.
TrivialExists.
simpl.
destruct (
eval_condition c0 vl m);
simpl.
unfold Val.of_bool,
Vtrue,
Vfalse in *.
destruct b;
inv H4;
simpl in *;
rewrite sem_eq in RES;
auto.
discriminate.
exists (
Vint Int.zero);
split.
EvalOp.
destruct (
eval_condition c0 vl m);
simpl.
unfold Val.of_bool,
Vtrue,
Vfalse in *.
destruct b;
inv H4;
rewrite sem_eq in RES;
rewrite Int.eq_false in RES;
inv RES;
auto.
discriminate.
-
InvEval.
inv EVAL.
simpl in H4.
destruct (
Int.eq_dec n2 Int.zero).
subst n2.
TrivialExists.
simpl.
unfold Val.of_bool,
Vtrue,
Vfalse in *.
destruct (
eval_condition c0 vl m);
simpl; [|
discriminate].
destruct b;
simpl;
inv H4;
rewrite sem_ne in RES;
auto.
destruct (
Int.eq_dec n2 Int.one).
subst n2.
TrivialExists.
simpl.
unfold Val.of_bool,
Vtrue,
Vfalse in *.
rewrite eval_negate_condition.
destruct (
eval_condition c0 vl m);
simpl.
destruct b;
simpl;
inv H4;
rewrite sem_ne in RES;
auto.
discriminate.
exists (
Vint Int.one);
split.
EvalOp.
destruct (
eval_condition c0 vl m);
simpl.
unfold Val.of_bool,
Vtrue,
Vfalse in *.
destruct b;
inv H4;
rewrite sem_ne,
Int.eq_false in RES;
inv RES;
auto.
discriminate.
-
destruct (
Int.eq_dec n2 Int.zero).
+
InvEval;
subst.
destruct v1;
simpl in *;
try (
rewrite sem_default in RES;
simpl in RES;
destruct default;
simpl in RES;
discriminate).
rewrite sem_eq in RES;
simpl in RES.
destruct (
Int.eq (
Int.and i n1)
Int.zero)
eqn:
RES';
inv RES; (
eexists;
split; [
EvalOp;
cbn;
rewrite RES'|];
eauto).
+
TrivialExists.
simpl in *.
rewrite sem_default in RES.
auto.
-
destruct (
Int.eq_dec n2 Int.zero).
InvEval;
subst.
destruct v1;
simpl in *;
try (
rewrite sem_default in RES;
simpl in RES;
destruct default;
simpl in RES;
discriminate;
fail).
econstructor;
split.
EvalOp.
simpl;
eauto.
rewrite sem_ne in RES;
inv RES.
auto.
TrivialExists.
simpl in *.
rewrite sem_default in RES.
auto.
-
TrivialExists.
simpl.
rewrite sem_default in RES.
auto.
Qed.
Hypothesis sem_swap:
forall c x y,
sem (
swap_comparison c)
x y =
sem c y x.
Lemma eval_compimm_swap_opt:
forall le c a n2 x y,
eval_expr ge sp e m le a x ->
sem c (
Vint n2)
x =
Some y ->
exists v,
eval_expr ge sp e m le (
compimm default intsem (
swap_comparison c)
a n2)
v
/\
Val.lessdef y v.
Proof.
End COMP_IMM_OPT.
Definition binary_constructor_sound_opt (
cstr:
expr ->
expr ->
expr) (
sem:
val ->
val ->
option val) :=
forall le a x b y z,
eval_expr ge sp e m le a x ->
eval_expr ge sp e m le b y ->
sem x y =
Some z ->
exists v,
eval_expr ge sp e m le (
cstr a b)
v /\
Val.lessdef z v.
Theorem eval_comp_opt:
forall c,
binary_constructor_sound_opt (
comp c) (
fun v1 v2 =>
option_map Val.of_bool (
Val.cmp_bool c v1 v2)).
Proof.
Theorem eval_compu_opt:
forall c,
binary_constructor_sound_opt (
compu c) (
fun v1 v2 =>
option_map Val.of_bool (
Val.cmpu_bool (
Mem.valid_pointer m)
c v1 v2)).
Proof.
Theorem eval_compf_opt:
forall c,
binary_constructor_sound_opt (
compf c) (
fun v1 v2 =>
option_map Val.of_bool (
Val.cmpf_bool c v1 v2)).
Proof.
intros;
red;
intros.
unfold compf.
TrivialExists.
Qed.
Theorem eval_compfs_opt:
forall c,
binary_constructor_sound_opt (
compfs c) (
fun v1 v2 =>
option_map Val.of_bool (
Val.cmpfs_bool c v1 v2)).
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:
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.
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.
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_intofsingle:
forall le a x y,
eval_expr ge sp e m le a x ->
Val.intofsingle x =
Some y ->
exists v,
eval_expr ge sp e m le (
intofsingle a)
v /\
Val.lessdef y v.
Proof.
Theorem eval_singleofint:
forall le a x y,
eval_expr ge sp e m le a x ->
Val.singleofint x =
Some y ->
exists v,
eval_expr ge sp e m le (
singleofint a)
v /\
Val.lessdef y v.
Proof.
Theorem eval_intuofsingle:
forall le a x y,
eval_expr ge sp e m le a x ->
Val.intuofsingle x =
Some y ->
exists v,
eval_expr ge sp e m le (
intuofsingle a)
v /\
Val.lessdef y v.
Proof.
Theorem eval_singleofintu:
forall le a x y,
eval_expr ge sp e m le a x ->
Val.singleofintu x =
Some y ->
exists v,
eval_expr ge sp e m le (
singleofintu 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.
Theorem eval_builtin_arg:
forall a v,
eval_expr ge sp e m nil a v ->
CminorSel.eval_builtin_arg ge sp e m (
builtin_arg a)
v.
Proof.
intros until v.
unfold builtin_arg;
case (
builtin_arg_match a);
intros;
InvEval.
-
constructor.
-
constructor.
-
constructor.
-
constructor.
-
constructor.
-
constructor.
-
simpl in H5.
inv H5.
constructor.
-
constructor;
auto.
-
inv H.
InvEval.
rewrite eval_addressing_Aglobal in H6.
inv H6.
constructor;
auto.
-
inv H.
InvEval.
rewrite eval_addressing_Ainstack in H6.
inv H6.
constructor;
auto.
-
constructor;
auto.
Qed.
End CMCONSTR.