Correctness of instruction selection for operators
Require Import Coqlib Zbits.
Require Import AST Integers Floats.
Require Import Values Memory Builtins Globalenvs.
Require Import Cminor Op CminorSel.
Require Import SelectOp.
Require Import OpHelpers.
Require Import OpHelpersproof.
Require Import Lia.
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;
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 prog:
program.
Variable hf:
helper_functions.
Hypothesis HELPERS:
helper_functions_declared prog hf.
Let ge :=
Genv.globalenv prog.
Variable sp:
val.
Variable e:
env.
Variable m:
mem.
We now show that the code generated by "smart constructor" functions
such as
Selection.notint behaves as expected. Continuing the
notint example, we show that if the expression
e
evaluates to some integer value
Vint n, then
Selection.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 (
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_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 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_mulhs:
binary_constructor_sound mulhs Val.mulhs.
Proof.
Theorem eval_mulhu:
binary_constructor_sound mulhu Val.mulhu.
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.
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_notint:
unary_constructor_sound notint Val.notint.
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.
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.
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_sqrtf:
forall expr expr' le x
(
EVAL :
sqrtf expr =
Some expr')
(
EXPR :
eval_expr ge sp e m le expr x),
exists v,
eval_expr ge sp e m le expr' v /\
Val.lessdef (
Val.sqrtf x)
v.
Proof.
unfold sqrtf in *.
intros.
inv EVAL.
eexists.
split.
repeat econstructor.
exact EXPR.
constructor.
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_sqrtfs:
forall expr expr' le x
(
EVAL :
sqrtfs expr =
Some expr')
(
EXPR :
eval_expr ge sp e m le expr x),
exists v,
eval_expr ge sp e m le expr' v /\
Val.lessdef (
Val.sqrtfs x)
v.
Proof.
unfold sqrtfs in *.
intros.
inv EVAL.
eexists.
split.
repeat econstructor.
exact EXPR.
constructor.
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.
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_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.
cbn.
rewrite H0.
reflexivity.
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.
intros;
unfold intuoffloat.
TrivialExists.
cbn.
rewrite H0.
reflexivity.
Qed.
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.
intros until y;
unfold floatofintu.
case (
floatofintu_match a);
intros.
InvEval.
simpl in H0.
TrivialExists.
TrivialExists.
cbn.
rewrite H0.
reflexivity.
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 until y;
unfold floatofint.
case (
floatofint_match a);
intros.
InvEval.
simpl in H0.
TrivialExists.
TrivialExists.
cbn.
rewrite H0.
reflexivity.
Qed.
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.
intros;
unfold intofsingle.
TrivialExists.
cbn.
rewrite H0.
reflexivity.
Qed.
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.
intros;
unfold singleofint;
TrivialExists.
cbn.
rewrite H0.
reflexivity.
Qed.
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.
intros;
unfold intuofsingle.
TrivialExists.
cbn.
rewrite H0.
reflexivity.
Qed.
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.
intros;
unfold intuofsingle.
TrivialExists.
cbn.
rewrite H0.
reflexivity.
Qed.
Theorem eval_singleoffloat:
unary_constructor_sound singleoffloat Val.singleoffloat.
Proof.
Theorem eval_floatofsingle:
unary_constructor_sound floatofsingle Val.floatofsingle.
Proof.
Lemma mod_small_negative:
forall a modulus,
modulus > 0 -> -
modulus <
a < 0 ->
a mod modulus =
a +
modulus.
Proof.
Remark normalize_low_long:
forall
(
PTR64 :
Archi.ptr64 =
true)
v1,
Val.loword (
Val.normalize (
Val.longofint v1)
Tlong) =
Val.normalize v1 Tint.
Proof.
Lemma same_expr_pure_correct:
forall le a1 a2 v1 v2
(
PURE :
same_expr_pure a1 a2 =
true)
(
EVAL1 :
eval_expr ge sp e m le a1 v1)
(
EVAL2 :
eval_expr ge sp e m le a2 v2),
v1 =
v2.
Proof.
intros.
destruct a1;
destruct a2;
cbn in *;
try discriminate.
inv EVAL1.
inv EVAL2.
destruct (
ident_eq i i0);
congruence.
Qed.
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.normalize (
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.
-
destruct (
Archi.pic_code tt).
+
exists (
Vptr b ofs0 ::
nil);
split.
constructor.
EvalOp.
simpl.
congruence.
constructor.
simpl.
rewrite Ptrofs.add_zero.
congruence.
+
exists (@
nil val);
split.
constructor.
simpl;
auto.
-
exists (
v1 ::
nil);
split.
eauto with evalexpr.
simpl.
destruct v1;
simpl in H;
try discriminate.
destruct Archi.ptr64 eqn:
SF;
inv H.
simpl.
auto.
-
exists (
v1 ::
nil);
split.
eauto with evalexpr.
simpl.
destruct v1;
simpl in H;
try discriminate.
destruct Archi.ptr64 eqn:
SF;
inv H.
simpl.
auto.
-
exists (
v ::
nil);
split.
eauto with evalexpr.
subst.
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.
-
InvEval.
constructor.
-
InvEval.
constructor.
-
InvEval.
simpl in H5.
inv H5.
constructor.
-
InvEval.
subst v.
constructor;
auto.
-
inv H.
InvEval.
simpl in H6;
inv H6.
constructor;
auto.
-
destruct Archi.ptr64 eqn:
SF.
+
constructor;
auto.
+
InvEval.
replace v with (
if Archi.ptr64 then Val.addl v1 (
Vint n)
else Val.add v1 (
Vint n)).
repeat constructor;
auto.
rewrite SF;
auto.
-
destruct Archi.ptr64 eqn:
SF.
+
InvEval.
replace v with (
if Archi.ptr64 then Val.addl v1 (
Vlong n)
else Val.add v1 (
Vlong n)).
repeat constructor;
auto.
rewrite SF;
auto.
+
constructor;
auto.
-
constructor;
auto.
Qed.
Theorem eval_divf_base:
forall le a b x 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 (
divf_base a b)
v /\
Val.lessdef (
Val.divf x y)
v.
Proof.
intros;
unfold divf_base.
TrivialExists.
Qed.
Theorem eval_divfs_base:
forall le a b x 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 (
divfs_base a b)
v /\
Val.lessdef (
Val.divfs x y)
v.
Proof.
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.
destruct bf; intros until le; intro Heval.
all: try (inversion Heval; subst a; clear Heval;
exists v; split; trivial;
repeat (try econstructor; try eassumption)).
Qed.
End CMCONSTR.