Abstract Syntax of atomic conditions (e.g. arithmetic comparisons).
At, the end of the module, some functors are provided to lift domains
with a "assume" on Cstr into "assume" on these conditions.
=> This is the place of Linearisation...
Require Import Bool.
Require Import ZArith.
Require Export ASTerm.
Require Import LinTerm.
Require Import CstrC.
Require Import OptionMonad.
Require Import PredTrans.
Require Export DomainInterfaces.
Require Import DomainGCL.
Require Import LinearizeBackend.
Module AtomicCond (
N:
NumSig) (
Import Term:
ASTermSig(
N)) <:
CondSig N.
Record atomicCond :
Type := {
cmpOp:
cmpG;
right:
Term.t }.
Definition t :=
atomicCond.
Definition sat (
c:
t) (
m:
Mem.t N.t):
Prop :=
N.cmpDenote (
cmpOp c)
N.z (
eval (
right c)
m).
Definition make (
t1:
term) (
cmp:
cmpG) (
t2:
term) :
t :=
{|
cmpOp:=
cmp;
right:=
smartAdd t2 (
smartOpp t1) |}.
Lemma make_correct t1 cmp t2 m:
sat (
make t1 cmp t2)
m <->
N.cmpDenote cmp (
Term.eval t1 m) (
Term.eval t2 m).
Proof.
unfold sat,
make;
simpl.
autorewrite with linterm num.
intuition;
N.cmp_simplify.
Qed.
End AtomicCond.
Module Type AtomicCondSig (
N:
NumSig) (
Import Term:
ASTermSig(
N)).
Include AtomicCond N Term.
End AtomicCondSig.
Module ZAtomicCond <:
AtomicCondSig ZNum ZTerm.
Import ZAffTerm.
Import ZTerm.
Include AtomicCond ZNum ZTerm.
Translations from ZAtomicCond.t into Cstr.t
Add Ring QRing:
QNum.Ring.
Lemma switch_sides:
forall (
cmp:
cmpT) (
n1 n2:
QNum.t),
QNum.cmpDenote cmp QNum.z (
QNum.add n1 n2) <->
QNum.cmpDenote cmp (
QNum.opp n1)
n2.
Proof.
intuition; QNum.cmp_simplify.
Qed.
Definition toCstr (
cmp:
cmpT) (
aft:
ZAffTerm.t) :
Cstr.t :=
{|
Cstr.coefs:=
LinQ.lift (
LinZ.opp (
lin aft)) ;
Cstr.typ:=
cmp;
Cstr.cst:=
ZtoQ.ofZ (
cte aft) |}.
Lemma toCstr_correct cmp aft m:
Cstr.sat (
toCstr cmp aft) (
Mem.lift ZtoQ.ofZ m) <->
ZNum.cmpDenote cmp ZNum.z (
ZAffTerm.eval aft m).
Proof.
Global Opaque toCstr.
End ZAtomicCond.
Module ZtoQCstr <:
CondSig ZNum.
Definition t :=
Cstr.t.
Definition sat c m :=
Cstr.sat c (
Mem.lift ZtoQ.ofZ m).
End ZtoQCstr.
Require Import ZNone.
Require Import ZNoneItv.
Import String.
Open Scope impure.
Module ZAtomicCondAssume (
D:
BasicDomain ZNum)
(
CstrD:
HasAssume ZNum ZtoQCstr D)
(
ItvD:
HasGetItvMode ZNum ZTerm ZNItv D)
<:
HasAssume ZNum ZAtomicCond D.
Import ZAffTerm.
Import ZAtomicCond.
Import D.
Add Ring ZRing:
ZNum.Ring.
Assume of affine terms (on Z)
0 < x is written 0 <= x-1
0 <> x is written 0 <= x-1 \/ 0 <= -1-x
Definition affAssumeLe aft a :=
CstrD.assume (
toCstr LeT aft)
a.
Lemma affAssumeLe_correct aft a:
WHEN p <-
affAssumeLe aft a THEN
forall m, 0 <=
ZAffTerm.eval aft m ->
gamma a m ->
gamma p m.
Proof.
Local Hint Resolve affAssumeLe_correct:
vpl.
Extraction Inline affAssumeLe.
Local Opaque affAssumeLe.
Definition affAssumeLt aft a :=
affAssumeLe (
ZAffTerm.addc (-1)%
Z aft)
a.
Lemma affAssumeLt_correct aft a:
WHEN p <-
affAssumeLt aft a THEN
forall m, 0 <
ZAffTerm.eval aft m ->
gamma a m ->
gamma p m.
Proof.
unfold affAssumeLt;
VPLAsimplify.
intros X;
intros;
apply X;
auto.
autorewrite with linterm;
ZNum.simplify.
Qed.
Local Hint Resolve affAssumeLt_correct:
vpl.
Extraction Inline affAssumeLt.
Local Opaque affAssumeLt.
Definition affAssumeGt aft a :=
affAssumeLt (
ZAffTerm.opp aft)
a.
Lemma affAssumeGt_correct aft a:
WHEN p <-
affAssumeGt aft a THEN
forall m, ~0 <= (
ZAffTerm.eval aft m) ->
gamma a m ->
gamma p m.
Proof.
unfold affAssumeGt;
VPLAsimplify.
simpl in * |- *.
intros X;
intros;
apply X;
clear X;
auto.
autorewrite with linterm.
ZNum.simplify.
Qed.
Local Hint Resolve affAssumeGt_correct:
vpl.
Extraction Inline affAssumeGt.
Opaque affAssumeGt.
Lemma neq_join n1 n2:
n1 <>
n2 ->
n1 <
n2 \/
n2 <
n1.
Proof.
intro H ;
destruct (
Ztrichotomy_inf n1 n2)
as [
H0|
H0];
auto with zarith.
destruct H0;
auto with zarith.
Qed.
Definition affAssume cmp aft a :=
match cmp with
|
Eq =>
CstrD.assume (
toCstr EqT aft)
a
|
Le =>
affAssumeLe aft a
|
Lt =>
affAssumeLt aft a
|
Neq =>
BIND a1 <-
affAssumeLt aft a -;
BIND a2 <-
affAssumeGt aft a -;
D.join a1
a2
end.
Local Arguments ZNum.add x y:
simpl never.
Lemma affAssume_correct cmp aft a:
WHEN p <-
affAssume cmp aft a THEN
forall m,
ZNum.cmpDenote cmp ZNum.z (
ZAffTerm.eval aft m) ->
gamma a m ->
gamma p m.
Proof.
unfold affAssume;
destruct cmp;
simpl;
VPLAsimplify;
intros X;
intros;
apply X;
auto.
eq case *)
unfold ZtoQCstr.sat;
rewrite toCstr_correct;
autorewrite with linterm;
simpl;
ZNum.simplify.
neq case *)
simpl in * |- *;
case (
neq_join _ _ H1);
[
constructor 1;
apply H |
constructor 2;
apply H0];
ZNum.simplify.
Qed.
Local Hint Resolve affAssume_correct:
vpl.
Opaque affAssume.
Early Computation of the interval of all variables
Section EarlyVariableIntervals.
Require Import FMapPositive.
Definition add_variable (
a:
D.t) (
x:
PVar.t) (
mitv:
PositiveMap.t ZNItv.t):
imp (
PositiveMap.t ZNItv.t) :=
match PositiveMap.find x mitv with
|
Some _ =>
pure mitv
|
None =>
BIND itv <-
ItvD.getItvMode BOTH (
ZTerm.Var x)
a -;
pure (
PositiveMap.add x itv mitv)
end.
Definition get_variables (
a:
D.t)
te:
imp (
PositiveMap.t ZNItv.t) :=
ZTerm.fold_variables te (
fun x i =>
BIND mitv <-
i -;
add_variable a x mitv) (
pure (
PositiveMap.Leaf)).
Lemma PositiveMap_find_None {
A}
x:
FAILS PositiveMap.find x (
PositiveMap.Leaf (
A:=
A)).
Proof.
Local Hint Resolve PositiveMap_find_None.
Lemma get_variables_correct a te:
WHEN mitv <-
get_variables a te THEN
forall x m,
gamma a m ->
(
WHEN itv <-
PositiveMap.find x mitv THEN ZNItv.sat itv (
m x))%
option.
Proof.
Definition mitv_find (
mitv:
PositiveMap.t ZNItv.t)
x:
ZNItv.t :=
match PositiveMap.find x mitv with
|
Some itv =>
itv
|
None =>
ZNItv.top
end.
Local Hint Resolve get_variables_correct.
Definition isItvEnv (
env:
PVar.t ->
ZNItv.t) (
m:
Mem.t ZNum.t):
Prop :=
forall x,
ZNItv.sat (
env x) (
m x).
Lemma isItvEnv_unfold env m:
isItvEnv env m ->
forall x,
ZNItv.sat (
env x) (
m x).
Proof.
auto.
Qed.
Hint Resolve isItvEnv_unfold:
zn.
Theorem mitv_find_get_variables a te:
WHEN mitv <-
get_variables a te THEN
forall m,
gamma a m ->
isItvEnv (
mitv_find mitv)
m.
Proof.
End EarlyVariableIntervals.
Extraction Inline ZTerm.fold_variables.
Local Hint Resolve mitv_find_get_variables:
vpl.
Dealing with non-affine terms.
- We treat equality as a conjunct of two inequalities
(rem: this may be not the better choice ! See below...)
- Strict inequalities are not supported (they should be eliminated through nnfForAssume)
Import ZTerm.
Section Intervalization.
Variable env:
PVar.t ->
ZNItv.t.
Fixpoint intervalize (
sic:
bool)
mo (
te:
term) (
a:
D.t):
imp ZNItv.t
:=
match te with
|
Var x =>
if sic then pure (
env x)
else ItvD.getItvMode mo (
Var x)
a
|
Cte c =>
pure (
ZNItv.single c)
|
Add tl tr =>
BIND i1 <-
intervalize sic mo tl a -;
BIND i2 <-
intervalize sic mo tr a -;
pure (
ZNItv.add mo i1 i2)
|
Opp te =>
BIND i <-
intervalize sic (
ZNItv.oppMode mo)
te a -;
pure (
ZNItv.opp i)
|
Mul tl tr =>
match (
matchCte tr)
with
|
Some c =>
BIND i <-
intervalize sic (
if Z_isNat c then mo else ZNItv.oppMode mo)
tl a -;
pure (
ZNItv.mulZ mo c i)
|
_ =>
BIND i1 <-
intervalize sic BOTH tl a -;
BIND i2 <-
intervalize sic BOTH tr a -;
pure (
ZNItv.mul mo i1 i2)
end
|
Annot AFFINE te =>
if sic then intervalize sic mo te a
else ItvD.getItvMode mo te a
|
Annot STATIC te =>
let te:=
trace DEBUG "!
INTERV STATIC!"
te in
intervalize true mo te a
|
Annot _ te =>
intervalize sic mo te a
end.
Theorem intervalize_correct te a:
forall sic mo,
WHEN itv <-
intervalize sic mo te a THEN forall m,
isItvEnv env m ->
gamma a m ->
ZNItv.sat itv (
eval te m).
Proof.
induction te;
simpl;
try (
xasimplify ltac:(
eauto with zn vpl);
fail).
mul *) +
xasimplify ltac:(
eauto with zn vpl).
cte case *)
intros;
simpl in * |- *;
rewrite H.
unfold ZNum.mul.
rewrite Z.mul_comm;
eauto with zn.
annot *) +
destruct a0;
simpl;
xasimplify ltac:(
eauto with zn pedraQ vpl).
Qed.
End Intervalization.
Local Hint Resolve intervalize_correct:
vpl.
Module G :=
BasicGCL ZNum D.
Import G.
Program Definition gAffAssumeLe aft :
cdac
:=
build_cdac
(
affAssumeLe aft)
(°-| (
fun m => 0 <=
ZAffTerm.eval aft m))%
MPP
.
Obligation 1.
VPLAsimplify.
Qed.
Proof.
Proof.
Proof.
Proof.