Correctness of instruction selection for operators
Require Import Coqlib.
Require Import AST Integers Floats.
Require Import Values Memory Builtins Globalenvs.
Require Import Cminor Op CminorSel.
Require Import Compopts.
Require Import SelectOp.
Local Open Scope cminorsel_scope.
Local Transparent Archi.ptr64.
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
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 value
v, then
SelectOp.notint e
evaluates to a value
v' which is either
Val.notint v or more defined
than
Val.notint v.
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, Float and Value 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 (
Genv.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.offset_ptr sp ofs)
v.
Proof.
intros.
unfold addrstack.
econstructor;
split.
EvalOp.
simpl;
eauto.
auto.
Qed.
Theorem eval_notint:
unary_constructor_sound notint Val.notint.
Proof.
Remark shift_symbol_address:
forall id ofs delta,
Genv.symbol_address ge id (
Ptrofs.add ofs (
Ptrofs.of_int delta)) =
Val.add (
Genv.symbol_address ge id ofs) (
Vint delta).
Proof.
Theorem eval_addimm:
forall n,
unary_constructor_sound (
addimm n) (
fun x =>
Val.add x (
Vint n)).
Proof.
Theorem eval_addsymbol:
forall s ofs,
unary_constructor_sound (
addsymbol s ofs) (
Val.add (
Genv.symbol_address ge s ofs)).
Proof.
Theorem eval_add:
binary_constructor_sound add Val.add.
Proof.
Theorem eval_subimm:
forall n,
unary_constructor_sound (
subimm n) (
fun v =>
Val.sub (
Vint n)
v).
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.
Lemma eval_rolm:
forall amount mask,
unary_constructor_sound (
fun a =>
rolm a amount mask)
(
fun x =>
Val.rolm x amount mask).
Proof.
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_mulhs:
binary_constructor_sound mulhs Val.mulhs.
Proof.
unfold mulhs;
red;
intros;
TrivialExists.
Qed.
Theorem eval_mulhu:
binary_constructor_sound mulhu Val.mulhu.
Proof.
unfold mulhu;
red;
intros;
TrivialExists.
Qed.
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.
Theorem 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.
Lemma eval_mod_aux:
forall divop semdivop,
(
forall sp x y m,
eval_operation ge sp divop (
x ::
y ::
nil)
m =
semdivop x y) ->
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 ->
semdivop x y =
Some z ->
eval_expr ge sp e m le (
mod_aux divop a b) (
Val.sub x (
Val.mul z y)).
Proof.
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.
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_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.
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.
Theorem eval_shr:
binary_constructor_sound shr Val.shr.
Proof.
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 default:
comparison ->
int ->
condition.
Variable intsem:
comparison ->
int ->
int ->
bool.
Variable sem:
comparison ->
val ->
val ->
val.
Hypothesis sem_int:
forall c x y,
sem c (
Vint x) (
Vint y) =
Val.of_bool (
intsem c x y).
Hypothesis sem_undef:
forall c v,
sem c Vundef v =
Vundef.
Hypothesis sem_eq:
forall x y,
sem Ceq (
Vint x) (
Vint y) =
Val.of_bool (
Int.eq x y).
Hypothesis sem_ne:
forall x y,
sem Cne (
Vint x) (
Vint y) =
Val.of_bool (
negb (
Int.eq x y)).
Hypothesis sem_default:
forall c v n,
sem c v (
Vint n) =
Val.of_optbool (
eval_condition (
default c n) (
v ::
nil)
m).
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 (
Vint n2))
v.
Proof.
Hypothesis sem_swap:
forall c x y,
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 (
Vint n2)
x)
v.
Proof.
End COMP_IMM.
Theorem eval_comp:
forall c,
binary_constructor_sound (
comp c) (
Val.cmp c).
Proof.
Theorem eval_compu:
forall c,
binary_constructor_sound (
compu c) (
Val.cmpu (
Mem.valid_pointer m)
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.
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_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_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_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_select:
forall le ty cond al vl a1 v1 a2 v2 a b,
select ty cond al a1 a2 =
Some a ->
eval_exprlist ge sp e m le al vl ->
eval_expr ge sp e m le a1 v1 ->
eval_expr ge sp e m le a2 v2 ->
eval_condition cond vl m =
Some b ->
exists v,
eval_expr ge sp e m le a v
/\
Val.lessdef (
Val.select (
Some b)
v1 v2 ty)
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.
exists (@
nil val).
split.
eauto with evalexpr.
simpl.
auto.
exists (@
nil val).
split.
eauto with evalexpr.
simpl.
auto.
exists (
v1 ::
nil).
split.
eauto with evalexpr.
simpl.
congruence.
exists (
v1 ::
nil).
split.
eauto with evalexpr.
simpl.
congruence.
destruct (
can_use_Aindexed2 chunk).
exists (
v1 ::
v0 ::
nil).
split.
eauto with evalexpr.
simpl.
congruence.
exists (
Vptr b ofs ::
nil).
split.
constructor.
EvalOp.
simpl;
congruence.
constructor.
simpl.
rewrite Ptrofs.add_zero.
auto.
exists (
v ::
nil).
split.
eauto with evalexpr.
subst v.
simpl.
rewrite Ptrofs.add_zero.
auto.
Qed.
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.
-
simpl in H5.
inv H5.
constructor.
-
subst v.
constructor;
auto.
-
inv H.
InvEval.
simpl in H6;
inv H6.
constructor;
auto.
-
inv H.
InvEval.
simpl in H6.
inv H6.
constructor;
auto.
-
inv H.
repeat constructor;
auto.
-
inv H.
repeat constructor;
auto.
-
inv H.
repeat constructor;
auto.
-
constructor;
auto.
Qed.
Platform-specific known builtins
Theorem eval_platform_builtin:
forall bf al a vl v le,
platform_builtin bf al =
Some a ->
eval_exprlist ge sp e m le al vl ->
platform_builtin_sem bf vl =
Some v ->
exists v',
eval_expr ge sp e m le a v' /\
Val.lessdef v v'.
Proof.
intros. discriminate.
Qed.
End CMCONSTR.