Require Import Coqlib.
Require Import AST.
Require Import Integers.
Require Import Floats.
Require Import Values.
Require Import NormaliseSpec.
Require Import ExprEval.
Require Import Memory.
Require Import Globalenvs.
Require Import Events.
Require Import Values_symbolic.
Require Import Values_symbolictype.
Require Import Setoid.
Require Import MemRel.

Set Implicit Arguments.


Inductive condition : Type :=
  | Ccomp: comparison -> condition (* signed integer comparison *)
  | Ccompu: comparison -> condition (* unsigned integer comparison *)
  | Ccompimm: comparison -> int -> condition (* signed integer comparison with a constant *)
  | Ccompuimm: comparison -> int -> condition (* unsigned integer comparison with a constant *)
  | Ccompf: comparison -> condition (* 64-bit floating-point comparison *)
  | Cnotcompf: comparison -> condition (* negation of a floating-point comparison *)
  | Ccompfs: comparison -> condition (* 32-bit floating-point comparison *)
  | Cnotcompfs: comparison -> condition (* negation of a floating-point comparison *)
  | Cmaskzero: int -> condition (* test (arg & constant) == 0 *)
  | Cmasknotzero: int -> condition. (* test (arg & constant) != 0 *)


Inductive addressing: Type :=
  | Aindexed: int -> addressing (* Address is r1 + offset *)
  | Aindexed2: int -> addressing (* Address is r1 + r2 + offset *)
  | Ascaled: int -> int -> addressing (* Address is r1 * scale + offset *)
  | Aindexed2scaled: int -> int -> addressing
  | Aglobal: ident -> int -> addressing (* Address is symbol + offset *)
  | Abased: ident -> int -> addressing (* Address is symbol + offset + r1 *)
  | Abasedscaled: int -> ident -> int -> addressing (* Address is symbol + offset + r1 * scale *)
  | Ainstack: int -> addressing. (* Address is stack_pointer + offset *)


Inductive operation : Type :=
  | Omove: operation (* rd = r1 *)
  | Ointconst: int -> operation (* rd is set to the given integer constant *)
  | Ofloatconst: float -> operation (* rd is set to the given float constant *)
  | Osingleconst: float32 -> operation (* rd is set to the given float constant *)
  | Oindirectsymbol: ident -> operation (* rd is set to the address of the symbol *)
  | Ocast8signed: operation (* rd is 8-bit sign extension of r1 *)
  | Ocast8unsigned: operation (* rd is 8-bit zero extension of r1 *)
  | Ocast16signed: operation (* rd is 16-bit sign extension of r1 *)
  | Ocast16unsigned: operation (* rd is 16-bit zero extension of r1 *)
  | Oneg: operation (* rd = - r1 *)
  | Osub: operation (* rd = r1 - r2 *)
  | Omul: operation (* rd = r1 * r2 *)
  | Omulimm: int -> operation (* rd = r1 * n *)
  | Omulhs: operation (* rd = high part of r1 * r2, signed *)
  | Omulhu: operation (* rd = high part of r1 * r2, unsigned *)
  | Odiv: operation (* rd = r1 / r2 (signed) *)
  | Odivu: operation (* rd = r1 / r2 (unsigned) *)
  | Omod: operation (* rd = r1 % r2 (signed) *)
  | Omodu: operation (* rd = r1 % r2 (unsigned) *)
  | Oand: operation (* rd = r1 & r2 *)
  | Oandimm: int -> operation (* rd = r1 & n *)
  | Oor: operation (* rd = r1 | r2 *)
  | Oorimm: int -> operation (* rd = r1 | n *)
  | Oxor: operation (* rd = r1 ^ r2 *)
  | Oxorimm: int -> operation (* rd = r1 ^ n *)
  | Onot: operation (* rd = ~r1 *)
  | Oshl: operation (* rd = r1 << r2 *)
  | Oshlimm: int -> operation (* rd = r1 << n *)
  | Oshr: operation (* rd = r1 >> r2 (signed) *)
  | Oshrimm: int -> operation (* rd = r1 >> n (signed) *)
  | Oshrximm: int -> operation (* rd = r1 / 2^n (signed) *)
  | Oshru: operation (* rd = r1 >> r2 (unsigned) *)
  | Oshruimm: int -> operation (* rd = r1 >> n (unsigned) *)
  | Ororimm: int -> operation (* rotate right immediate *)
  | Oshldimm: int -> operation (* rd = r1 << n | r2 >> (32-n) *)
  | Olea: addressing -> operation (* effective address *)
  | Onegf: operation (* rd = - r1 *)
  | Oabsf: operation (* rd = abs(r1) *)
  | Oaddf: operation (* rd = r1 + r2 *)
  | Osubf: operation (* rd = r1 - r2 *)
  | Omulf: operation (* rd = r1 * r2 *)
  | Odivf: operation (* rd = r1 / r2 *)
  | Onegfs: operation (* rd = - r1 *)
  | Oabsfs: operation (* rd = abs(r1) *)
  | Oaddfs: operation (* rd = r1 + r2 *)
  | Osubfs: operation (* rd = r1 - r2 *)
  | Omulfs: operation (* rd = r1 * r2 *)
  | Odivfs: operation (* rd = r1 / r2 *)
  | Osingleoffloat: operation (* rd is r1 truncated to single-precision float *)
  | Ofloatofsingle: operation (* rd is r1 extended to double-precision float *)
  | Ointoffloat: operation (* rd = signed_int_of_float64(r1) *)
  | Ofloatofint: operation (* rd = float64_of_signed_int(r1) *)
  | Ointofsingle: operation (* rd = signed_int_of_float32(r1) *)
  | Osingleofint: operation (* rd = float32_of_signed_int(r1) *)
  | Omakelong: operation (* rd = r1 << 32 | r2 *)
  | Olowlong: operation (* rd = low-word(r1) *)
  | Ohighlong: operation (* rd = high-word(r1) *)
  | Ocmp: condition -> operation. (* rd = 1 if condition holds, rd = 0 otherwise. *)


Definition Oaddrsymbol (id: ident) (ofs: int) : operation := Olea (Aglobal id ofs).
Definition Oaddrstack (ofs: int) : operation := Olea (Ainstack ofs).
Definition Oaddimm (n: int) : operation := Olea (Aindexed n).


Definition eq_condition (x y: condition) : {x=y} + {x<>y}.

Definition eq_addressing (x y: addressing) : {x=y} + {x<>y}.

Definition eq_operation (x y: operation): {x=y} + {x<>y}.

Global Opaque eq_condition eq_addressing eq_operation.

Evaluation functions

Definition eval_condition (cond: condition) (vl: list expr_sym) : option expr_sym :=
  match cond, vl with
  | Ccomp c, v1 :: v2 :: nil => Some (Val.cmp_bool c v1 v2)
  | Ccompu c, v1 :: v2 :: nil => Some (Val.cmpu_bool c v1 v2)
  | Ccompimm c n, v1 :: nil => Some (Val.cmp_bool c v1 (Eval (Vint n)))
  | Ccompuimm c n, v1 :: nil => Some (Val.cmpu_bool c v1 (Eval (Vint n)))
  | Ccompf c, v1 :: v2 :: nil => Some (Val.cmpf_bool c v1 v2)
  | Cnotcompf c, v1 :: v2 :: nil => Some (Eunop OpNotbool Tint (Val.cmpf_bool c v1 v2))
  | Ccompfs c, v1 :: v2 :: nil => Some (Val.cmpfs_bool c v1 v2)
  | Cnotcompfs c, v1 :: v2 :: nil => Some (Eunop OpNotbool Tint (Val.cmpfs_bool c v1 v2))
  | Cmaskzero n, v1 :: nil => Some (Val.maskzero_bool v1 n)
  | Cmasknotzero n, v1 :: nil => Some (Eunop OpNotbool Tint (Val.maskzero_bool v1 n))
  | _, _ => None
  end.

Ltac easy_inv :=
  repeat match goal with
           H: match ?vl : list expr_sym with _ => _ end = _ |- _ =>
           destruct vl; try discriminate
         | H: Some _ = Some _ |- _ => inv H
         end.
  
Lemma eval_condition_cmp_one:
  forall c vl x sg,
    eval_condition c vl = Some x ->
    same_eval (Ebinop (OpCmp sg Ceq) Tint Tint x (Eval (Vint Int.one))) x.

Lemma eval_condition_zero_one:
  forall c vl x alloc em i,
    eval_condition c vl = Some x ->
    eSexpr alloc em x = Vint i ->
    i = Int.one \/ i = Int.zero.

Lemma eval_condition_boolval:
  forall c vl v,
    eval_condition c vl = Some v ->
    same_eval (Val.boolval v) v.
Ltac FuncInv :=
  match goal with
  | H: (match ?x with nil => _ | _ :: _ => _ end = Some _) |- _ =>
      destruct x; simpl in H; try discriminate; FuncInv
  | H: (match ?v with Vundef => _ | Vint _ => _ | Vfloat _ => _ | Vptr _ _ => _ end = Some _) |- _ =>
      destruct v; simpl in H; try discriminate; FuncInv
  | H: (Some _ = Some _) |- _ =>
      injection H; intros; clear H; FuncInv
  | _ =>
      idtac
  end.

Lemma eval_condition_type:
  forall c vl v t,
    eval_condition c vl = Some v ->
    wt_expr v t -> t = Tint.

Lemma eval_cond_norm_0_1:
  forall cond args b i
         (EC: eval_condition cond args = Some b)
         m (N : Mem.mem_norm m b = Vint i),
    i = Int.one \/ i = Int.zero.


Definition eval_addressing
    (F V: Type) (genv: Genv.t F V) (sp: expr_sym)
    (addr: addressing) (vl: list expr_sym) : option expr_sym :=
  match addr, vl with
  | Aindexed n, v1::nil =>
      Some (Val.add v1 (Eval (Vint n)))
  | Aindexed2 n, v1::v2::nil =>
      Some (Val.add (Val.add v1 v2) (Eval (Vint n)))
  | Ascaled sc ofs, v1::nil =>
      Some (Val.add (Val.mul v1 (Eval (Vint sc))) (Eval (Vint ofs)))
  | Aindexed2scaled sc ofs, v1::v2::nil =>
      Some(Val.add v1 (Val.add (Val.mul v2 (Eval (Vint sc))) (Eval (Vint ofs))))
  | Aglobal s ofs, nil => Genv.symbol_address' genv s ofs
  | Abased s ofs, v1::nil =>
    option_map (Val.add v1) (Genv.symbol_address' genv s ofs)
  | Abasedscaled sc s ofs, v1::nil =>
    option_map (Val.add (Val.mul v1 (Eval (Vint sc)))) (Genv.symbol_address' genv s ofs)
  | Ainstack ofs, nil =>
      Some(Val.add sp (Eval (Vint ofs)))
  | _, _ => None
  end.

Definition eval_operation
    (F V: Type) (genv: Genv.t F V) (sp: expr_sym)
    (op: operation) (vl: list expr_sym) : option expr_sym :=
  match op, vl with
  | Omove, v1::nil => Some v1
  | Ointconst n, nil => Some (Eval (Vint n))
  | Ofloatconst n, nil => Some (Eval (Vfloat n))
  | Osingleconst n, nil => Some (Eval (Vsingle n))
  | Oindirectsymbol id, nil => Genv.symbol_address' genv id Int.zero
  | Ocast8signed, v1 :: nil => Some (Val.sign_ext 8 v1)
  | Ocast8unsigned, v1 :: nil => Some (Val.zero_ext 8 v1)
  | Ocast16signed, v1 :: nil => Some (Val.sign_ext 16 v1)
  | Ocast16unsigned, v1 :: nil => Some (Val.zero_ext 16 v1)
  | Oneg, v1::nil => Some (Val.neg v1)
  | Osub, v1::v2::nil => Some (Val.sub v1 v2)
  | Omul, v1::v2::nil => Some (Val.mul v1 v2)
  | Omulimm n, v1::nil => Some (Val.mul v1 (Eval (Vint n)))
  | Omulhs, v1::v2::nil => Some (Val.mulhs v1 v2)
  | Omulhu, v1::v2::nil => Some (Val.mulhu v1 v2)
  | Odiv, v1::v2::nil => Some (Val.divs v1 v2)
  | Odivu, v1::v2::nil => Some (Val.divu v1 v2)
  | Omod, v1::v2::nil => Some (Val.mods v1 v2)
  | Omodu, v1::v2::nil => Some (Val.modu v1 v2)
  | Oand, v1::v2::nil => Some(Val.and v1 v2)
  | Oandimm n, v1::nil => Some (Val.and v1 (Eval (Vint n)))
  | Oor, v1::v2::nil => Some(Val.or v1 v2)
  | Oorimm n, v1::nil => Some (Val.or v1 (Eval (Vint n)))
  | Oxor, v1::v2::nil => Some(Val.xor v1 v2)
  | Oxorimm n, v1::nil => Some (Val.xor v1 (Eval (Vint n)))
  | Onot, v1::nil => Some(Val.notint v1)
  | Oshl, v1::v2::nil => Some (Val.shl v1 v2)
  | Oshlimm n, v1::nil => Some (Val.shl v1 (Eval (Vint n)))
  | Oshr, v1::v2::nil => Some (Val.shr v1 v2)
  | Oshrimm n, v1::nil => Some (Val.shr v1 (Eval (Vint n)))
  | Oshrximm n, v1::nil => Some (Val.shrx v1 (Eval (Vint n)))
  | Oshru, v1::v2::nil => Some (Val.shru v1 v2)
  | Oshruimm n, v1::nil => Some (Val.shru v1 (Eval (Vint n)))
  | Ororimm n, v1::nil => Some (Val.ror v1 (Eval (Vint n)))
  | Oshldimm n, v1::v2::nil => Some (Val.or (Val.shl v1 (Eval (Vint n)))
                                            (Val.shru v2 (Eval (Vint (Int.sub Int.iwordsize n)))))
  | Olea addr, _ => eval_addressing genv sp addr vl
  | Onegf, v1::nil => Some(Val.negf v1)
  | Oabsf, v1::nil => Some(Val.absf v1)
  | Oaddf, v1::v2::nil => Some(Val.addf v1 v2)
  | Osubf, v1::v2::nil => Some(Val.subf v1 v2)
  | Omulf, v1::v2::nil => Some(Val.mulf v1 v2)
  | Odivf, v1::v2::nil => Some(Val.divf v1 v2)
  | Onegfs, v1::nil => Some(Val.negfs v1)
  | Oabsfs, v1::nil => Some(Val.absfs v1)
  | Oaddfs, v1::v2::nil => Some(Val.addfs v1 v2)
  | Osubfs, v1::v2::nil => Some(Val.subfs v1 v2)
  | Omulfs, v1::v2::nil => Some(Val.mulfs v1 v2)
  | Odivfs, v1::v2::nil => Some(Val.divfs v1 v2)
  | Osingleoffloat, v1::nil => Some(Val.singleoffloat v1)
  | Ofloatofsingle, v1::nil => Some(Val.floatofsingle v1)
  | Ointoffloat, v1::nil => Some (Val.intoffloat v1)
  | Ofloatofint, v1::nil => Some (Val.floatofint v1)
  | Ointofsingle, v1::nil => Some (Val.intofsingle v1)
  | Osingleofint, v1::nil => Some (Val.singleofint v1)
  | Omakelong, v1::v2::nil => Some(Val.longofwords v1 v2)
  | Olowlong, v1::nil => Some(Val.loword v1)
  | Ohighlong, v1::nil => Some(Val.hiword v1)
  | Ocmp c, _ => (eval_condition c vl)
  | _, _ => None
  end.

Static typing of conditions, operators and addressing modes.

Definition type_of_condition (c: condition) : list typ :=
  match c with
  | Ccomp _ => AST.Tint :: AST.Tint :: nil
  | Ccompu _ => AST.Tint :: AST.Tint :: nil
  | Ccompimm _ _ => AST.Tint :: nil
  | Ccompuimm _ _ => AST.Tint :: nil
  | Ccompf _ => AST.Tfloat :: AST.Tfloat :: nil
  | Cnotcompf _ => AST.Tfloat :: AST.Tfloat :: nil
  | Ccompfs _ => AST.Tsingle :: AST.Tsingle :: nil
  | Cnotcompfs _ => AST.Tsingle :: AST.Tsingle :: nil
  | Cmaskzero _ => AST.Tint :: nil
  | Cmasknotzero _ => AST.Tint :: nil
  end.

Definition type_of_addressing (addr: addressing) : list typ :=
  match addr with
  | Aindexed _ => AST.Tint :: nil
  | Aindexed2 _ => AST.Tint :: AST.Tint :: nil
  | Ascaled _ _ => AST.Tint :: nil
  | Aindexed2scaled _ _ => AST.Tint :: AST.Tint :: nil
  | Aglobal _ _ => nil
  | Abased _ _ => AST.Tint :: nil
  | Abasedscaled _ _ _ => AST.Tint :: nil
  | Ainstack _ => nil
  end.

Definition type_of_operation (op: operation) : list typ * typ :=
  match op with
  | Omove => (nil, AST.Tint)
  | Ointconst _ => (nil, AST.Tint)
  | Ofloatconst f => (nil, AST.Tfloat)
  | Osingleconst f => (nil, AST.Tsingle)
  | Oindirectsymbol _ => (nil, AST.Tint)
  | Ocast8signed => (AST.Tint :: nil, AST.Tint)
  | Ocast8unsigned => (AST.Tint :: nil, AST.Tint)
  | Ocast16signed => (AST.Tint :: nil, AST.Tint)
  | Ocast16unsigned => (AST.Tint :: nil, AST.Tint)
  | Oneg => (AST.Tint :: nil, AST.Tint)
  | Osub => (AST.Tint :: AST.Tint :: nil, AST.Tint)
  | Omul => (AST.Tint :: AST.Tint :: nil, AST.Tint)
  | Omulimm _ => (AST.Tint :: nil, AST.Tint)
  | Omulhs => (AST.Tint :: AST.Tint :: nil, AST.Tint)
  | Omulhu => (AST.Tint :: AST.Tint :: nil, AST.Tint)
  | Odiv => (AST.Tint :: AST.Tint :: nil, AST.Tint)
  | Odivu => (AST.Tint :: AST.Tint :: nil, AST.Tint)
  | Omod => (AST.Tint :: AST.Tint :: nil, AST.Tint)
  | Omodu => (AST.Tint :: AST.Tint :: nil, AST.Tint)
  | Oand => (AST.Tint :: AST.Tint :: nil, AST.Tint)
  | Oandimm _ => (AST.Tint :: nil, AST.Tint)
  | Oor => (AST.Tint :: AST.Tint :: nil, AST.Tint)
  | Oorimm _ => (AST.Tint :: nil, AST.Tint)
  | Oxor => (AST.Tint :: AST.Tint :: nil, AST.Tint)
  | Oxorimm _ => (AST.Tint :: nil, AST.Tint)
  | Onot => (AST.Tint :: nil, AST.Tint)
  | Oshl => (AST.Tint :: AST.Tint :: nil, AST.Tint)
  | Oshlimm _ => (AST.Tint :: nil, AST.Tint)
  | Oshr => (AST.Tint :: AST.Tint :: nil, AST.Tint)
  | Oshrimm _ => (AST.Tint :: nil, AST.Tint)
  | Oshrximm _ => (AST.Tint :: nil, AST.Tint)
  | Oshru => (AST.Tint :: AST.Tint :: nil, AST.Tint)
  | Oshruimm _ => (AST.Tint :: nil, AST.Tint)
  | Ororimm _ => (AST.Tint :: nil, AST.Tint)
  | Oshldimm _ => (AST.Tint :: AST.Tint :: nil, AST.Tint)
  | Olea addr => (type_of_addressing addr, AST.Tint)
  | Onegf => (AST.Tfloat :: nil, AST.Tfloat)
  | Oabsf => (AST.Tfloat :: nil, AST.Tfloat)
  | Oaddf => (AST.Tfloat :: AST.Tfloat :: nil, AST.Tfloat)
  | Osubf => (AST.Tfloat :: AST.Tfloat :: nil, AST.Tfloat)
  | Omulf => (AST.Tfloat :: AST.Tfloat :: nil, AST.Tfloat)
  | Odivf => (AST.Tfloat :: AST.Tfloat :: nil, AST.Tfloat)
  | Onegfs => (AST.Tsingle :: nil, AST.Tsingle)
  | Oabsfs => (AST.Tsingle :: nil, AST.Tsingle)
  | Oaddfs => (AST.Tsingle :: AST.Tsingle :: nil, AST.Tsingle)
  | Osubfs => (AST.Tsingle :: AST.Tsingle :: nil, AST.Tsingle)
  | Omulfs => (AST.Tsingle :: AST.Tsingle :: nil, AST.Tsingle)
  | Odivfs => (AST.Tsingle :: AST.Tsingle :: nil, AST.Tsingle)
  | Osingleoffloat => (AST.Tfloat :: nil, AST.Tsingle)
  | Ofloatofsingle => (AST.Tsingle :: nil, AST.Tfloat)
  | Ointoffloat => (AST.Tfloat :: nil, AST.Tint)
  | Ofloatofint => (AST.Tint :: nil, AST.Tfloat)
  | Ointofsingle => (AST.Tsingle :: nil, AST.Tint)
  | Osingleofint => (AST.Tint :: nil, AST.Tsingle)
  | Omakelong => (AST.Tint :: AST.Tint :: nil, AST.Tlong)
  | Olowlong => (AST.Tlong :: nil, AST.Tint)
  | Ohighlong => (AST.Tlong :: nil, AST.Tint)
  | Ocmp c => (type_of_condition c, AST.Tint)
  end.




Lemma eval_condition_cmp_zero:
  forall c vl x sg,
    eval_condition c vl = Some x ->
    same_eval (Ebinop (OpCmp sg Cne) Tint Tint x (Eval (Vint Int.zero))) x.


Ltac TrivialExists :=
  repeat match goal with
  | [ |- exists v2, Some ?v1 = Some v2 /\ _ ] =>
    exists v1; split; auto
  | H: Some _ = Some _ |- _ => inv H
  | H : ?X = Some ?v |- exists v2, ?X = Some v2 /\ _ =>
    exists v ; split;[exact H | auto]
  | _ => idtac
  end.



Section SOUNDNESS.

Variable A V: Type.
Variable genv: Genv.t A V.


Lemma symbol_address'_has_type : forall (A V : Type) (genv:Genv.t A V) i i0 v,
    Genv.symbol_address' genv i i0 = Some v ->
   Val.has_type v Tint.

Lemma option_map_symbol_address'_some :
  forall (A V : Type) (genv:Genv.t A V) i ofs v (F: expr_sym -> expr_sym),
    option_map F (Genv.symbol_address' genv i ofs) = Some v ->
    exists b, (Genv.symbol_address' genv i ofs = Some (Eval (Vptr b ofs)) /\
               v = F (Eval (Vptr b ofs))).
  
Lemma symbol_address'_option_map_has_type :
forall (A V : Type) (genv:Genv.t A V) i i0 v F
  (FTYPE : forall e, Val.has_type e Tint -> Val.has_type (F e) Tint),
  option_map F (Genv.symbol_address' genv i i0) = Some v ->
   Val.has_type v Tint.


Lemma type_of_operation_sound:
  forall op vl sp v,
  op <> Omove ->
  Val.has_type_list vl (map styp_of_ast (fst (type_of_operation op))) ->
  Val.has_type sp Tint ->
  eval_operation genv sp op vl = Some v ->
  Val.has_type v (styp_of_ast (snd (type_of_operation op))).

End SOUNDNESS.

Manipulating and transforming operations

Definition is_move_operation
    (A: Type) (op: operation) (args: list A) : option A :=
  match op, args with
  | Omove, arg :: nil => Some arg
  | _, _ => None
  end.

Lemma is_move_operation_correct:
  forall (A: Type) (op: operation) (args: list A) (a: A),
  is_move_operation op args = Some a ->
  op = Omove /\ args = a :: nil.


Definition negate_condition (cond: condition): condition :=
  match cond with
  | Ccomp c => Ccomp(negate_comparison c)
  | Ccompu c => Ccompu(negate_comparison c)
  | Ccompimm c n => Ccompimm (negate_comparison c) n
  | Ccompuimm c n => Ccompuimm (negate_comparison c) n
  | Ccompf c => Cnotcompf c
  | Cnotcompf c => Ccompf c
  | Ccompfs c => Cnotcompfs c
  | Cnotcompfs c => Ccompfs c
  | Cmaskzero n => Cmasknotzero n
  | Cmasknotzero n => Cmaskzero n
  end.



Lemma negate_cmp_eqm:
  forall c e e0,
    same_eval (Val.cmp_bool (negate_comparison c) e e0)
                                  (Eunop OpNotbool Tint (Val.cmp_bool c e e0)).

Lemma negate_cmpu_eqm:
  forall c e e0,
    same_eval (Val.cmpu_bool (negate_comparison c) e e0)
              (Eunop OpNotbool Tint (Val.cmpu_bool c e e0)).


Lemma dbl_negate_cmpf:
  forall c e e0,
    same_eval (Val.cmpf_bool c e e0)
              (Eunop OpNotbool Tint (Eunop OpNotbool Tint (Val.cmpf_bool c e e0))).

Lemma dbl_negate_cmpfs:
  forall c e e0,
    same_eval (Val.cmpfs_bool c e e0) (Eunop OpNotbool Tint (Eunop OpNotbool Tint (Val.cmpfs_bool c e e0))).


Lemma dbl_negate_mskzero:
  forall e i,
    same_eval (Val.maskzero_bool e i)
              (Eunop OpNotbool Tint (Eunop OpNotbool Tint (Val.maskzero_bool e i))).

Lemma eval_negate_condition:
  forall cond vl,
    match eval_condition (negate_condition cond) vl,
          option_map (Eunop OpNotbool Tint) (eval_condition cond vl) with
        Some e, Some f => same_eval e f
      | None, None => True
      | _, _ => False
    end.


Definition shift_stack_addressing (delta: int) (addr: addressing) :=
  match addr with
  | Ainstack ofs => Ainstack (Int.add delta ofs)
  | _ => addr
  end.

Definition shift_stack_operation (delta: int) (op: operation) :=
  match op with
  | Olea addr => Olea (shift_stack_addressing delta addr)
  | _ => op
  end.

Lemma type_shift_stack_addressing:
  forall delta addr, type_of_addressing (shift_stack_addressing delta addr) = type_of_addressing addr.

Lemma type_shift_stack_operation:
  forall delta op, type_of_operation (shift_stack_operation delta op) = type_of_operation op.

Lemma eval_shift_stack_addressing:
  forall F V (ge: Genv.t F V) sp addr vl delta,
    match eval_addressing ge sp (shift_stack_addressing delta addr) vl,
          eval_addressing ge (Val.add sp (Eval (Vint delta))) addr vl with
        Some e, Some f => same_eval e f
      | None, None => True
      | _, _ => False
    end.

Lemma eval_shift_stack_operation:
  forall F V (ge: Genv.t F V) sp op vl delta,
    match eval_operation ge sp (shift_stack_operation delta op) vl,
          eval_operation ge (Val.add sp (Eval (Vint delta))) op vl with
        Some e, Some f => same_eval e f
      | None, None => True
      | _, _ => False
    end.


Definition offset_addressing_total (addr: addressing) (delta: int) : addressing :=
  match addr with
  | Aindexed n => Aindexed (Int.add n delta)
  | Aindexed2 n => Aindexed2 (Int.add n delta)
  | Ascaled sc n => Ascaled sc (Int.add n delta)
  | Aindexed2scaled sc n => Aindexed2scaled sc (Int.add n delta)
  | Aglobal s n => Aglobal s (Int.add n delta)
  | Abased s n => Abased s (Int.add n delta)
  | Abasedscaled sc s n => Abasedscaled sc s (Int.add n delta)
  | Ainstack n => Ainstack (Int.add n delta)
  end.

Definition offset_addressing (addr: addressing) (delta: int) : option addressing :=
  Some(offset_addressing_total addr delta).

Lemma eval_offset_addressing_total:
  forall (F V: Type) (ge: Genv.t F V) sp addr args delta v,
  eval_addressing ge sp addr args = Some v ->
  exists e,
    eval_addressing ge sp (offset_addressing_total addr delta) args = Some e /\
    same_eval e (Val.add v (Eval (Vint delta))).

Lemma eval_offset_addressing:
  forall (F V: Type) (ge: Genv.t F V) sp addr args delta addr' v,
  offset_addressing addr delta = Some addr' ->
  eval_addressing ge sp addr args = Some v ->
  exists e,
    eval_addressing ge sp addr' args = Some e /\
    same_eval e (Val.add v (Eval (Vint delta))).


Definition is_trivial_op (op: operation) : bool :=
  match op with
  | Omove => true
  | Ointconst _ => true
  | Olea (Aglobal _ _) => true
  | Olea (Ainstack _) => true
  | _ => false
  end.


Definition op_depends_on_memory (op: operation) : bool :=
  match op with
  | Ocmp (Ccompu _) => true
  | _ => false
  end.

Lemma op_depends_on_memory_correct:
  forall (F V: Type) (ge: Genv.t F V) sp op args,
  op_depends_on_memory op = false ->
  eval_operation ge sp op args = eval_operation ge sp op args.

Invariance and compatibility properties.

Section GENV_TRANSF.

Variable F1 F2 V1 V2: Type.
Variable ge1: Genv.t F1 V1.
Variable ge2: Genv.t F2 V2.
Hypothesis agree_on_symbols:
  forall (s: ident), Genv.find_symbol ge2 s = Genv.find_symbol ge1 s.

Lemma eval_addressing_preserved:
  forall sp addr vl,
  eval_addressing ge2 sp addr vl = eval_addressing ge1 sp addr vl.

Lemma eval_operation_preserved:
  forall sp op vl,
  eval_operation ge2 sp op vl = eval_operation ge1 sp op vl.

End GENV_TRANSF.


Section EVAL_COMPAT.

Variable F V: Type.
Variable genv: Genv.t F V.
Variable f: meminj.
Variable ei: meminj -> expr_sym -> expr_sym -> Prop.
Hypothesis wf: wf_inj ei.

Hypothesis symbol_address_inj:
  forall id ofs b ofs',
    Genv.symbol_address' genv id ofs = Some (Eval (Vptr b ofs')) ->
    f b = Some (b,0).

Variable m1: mem.
Variable m2: mem.

Hypothesis valid_pointer_inj:
  forall b1 ofs b2 delta,
  f b1 = Some(b2, delta) ->
  Mem.valid_pointer m1 b1 (Int.unsigned ofs) = true ->
  Mem.valid_pointer m2 b2 (Int.unsigned (Int.add ofs (Int.repr delta))) = true.

Hypothesis weak_valid_pointer_inj:
  forall b1 ofs b2 delta,
  f b1 = Some(b2, delta) ->
  Mem.weak_valid_pointer m1 b1 (Int.unsigned ofs) = true ->
  Mem.weak_valid_pointer m2 b2 (Int.unsigned (Int.add ofs (Int.repr delta))) = true.

Hypothesis weak_valid_pointer_no_overflow:
  forall b1 ofs b2 delta,
  f b1 = Some(b2, delta) ->
  Mem.weak_valid_pointer m1 b1 (Int.unsigned ofs) = true ->
  0 <= Int.unsigned ofs + Int.unsigned (Int.repr delta) <= Int.max_unsigned.

Hypothesis valid_different_pointers_inj:
  forall b1 ofs1 b2 ofs2 b1' delta1 b2' delta2,
  b1 <> b2 ->
  Mem.valid_pointer m1 b1 (Int.unsigned ofs1) = true ->
  Mem.valid_pointer m1 b2 (Int.unsigned ofs2) = true ->
  f b1 = Some (b1', delta1) ->
  f b2 = Some (b2', delta2) ->
  b1' <> b2' \/
  Int.unsigned (Int.add ofs1 (Int.repr delta1)) <> Int.unsigned (Int.add ofs2 (Int.repr delta2)).

Ltac InvInject :=
  match goal with
  | [ H: val_inject _ (Vint _) _ |- _ ] =>
      inv H; InvInject
  | [ H: val_inject _ (Vfloat _) _ |- _ ] =>
      inv H; InvInject
  | [ H: val_inject _ (Vptr _ _) _ |- _ ] =>
      inv H; InvInject
  | [ H: val_list_inject _ nil _ |- _ ] =>
      inv H; InvInject
  | [ H: val_list_inject _ (_ :: _) _ |- _ ] =>
      inv H; InvInject
  | _ => idtac
  end.


Ltac invInj :=
  repeat match goal with
             H: list_ei ?ei ?f (_::_) _ |- _ => inv H
           | H: list_ei ?ei ?f nil _ |- _ => inv H
         end.




Lemma eval_condition_inj:
  forall cond vl1 vl2 b,
    list_ei ei f vl1 vl2 ->
    eval_condition cond vl1 = Some b ->
    exists b1,
      eval_condition cond vl2 = Some b1 /\ ei f b b1.

Lemma eval_addressing_inj:
  forall addr sp1 vl1 sp2 vl2 v1,
    ei f sp1 sp2 ->
    list_ei ei f vl1 vl2 ->
    eval_addressing genv sp1 addr vl1 = Some v1 ->
    exists v2, eval_addressing genv sp2 addr vl2 = Some v2 /\ ei f v1 v2.

Ltac inv_expr_inject:= invInj.

Lemma eval_operation_inj:
  forall op sp1 vl1 sp2 vl2 v1,
    ei f sp1 sp2 ->
    list_ei ei f vl1 vl2 ->
    eval_operation genv sp1 op vl1 = Some v1 ->
    exists v2, eval_operation genv sp2 op vl2 = Some v2 /\ ei f v1 v2.

End EVAL_COMPAT.


Ltac myinv :=
  repeat match goal with
           | H : list_forall2 _ (_::_) _ |- _ => inv H
           | H : list_forall2 _ nil _ |- _ => inv H
           | H : context [match ?v with _ => _ end] |- _ => des v
           | |- exists v, Some ?V = Some v /\ _ => exists V; split; auto
           | H : Some _ = Some _ |- _ => inv H
           | H : None = Some _ |- _ => inv H
           | H : Some _ = None |- _ => inv H
         end.


Ltac ld' H :=
  repeat
    ((apply (mr_unop _ H); auto)
       ||
       (apply (mr_binop _ H); auto)
       || (apply (mr_refl _ H))).

Ltac ld :=
  match goal with
      H: wf_mr ?mr |- _ => ld' H
  end.
  

Section EVAL_LESSDEF.

Variable F V: Type.
Variable genv: Genv.t F V.


Variable mr : expr_sym -> expr_sym -> Prop.
Hypothesis wf: wf_mr mr.
                                        

Lemma eval_condition_rel:
  forall cond vl1 vl2 b,
    list_forall2 mr vl1 vl2 ->
    eval_condition cond vl1 = Some b ->
    exists b1,
      eval_condition cond vl2 = Some b1 /\
      mr b b1.


Lemma eval_addressing_rel:
  forall sp addr vl1 vl2 v1,
    list_forall2 mr vl1 vl2 ->
    eval_addressing genv sp addr vl1 = Some v1 ->
    exists v2, eval_addressing genv sp addr vl2 = Some v2 /\ mr v1 v2.
  
  
Lemma eval_operation_rel:
  forall sp op vl1 vl2 v1 ,
    list_forall2 mr vl1 vl2 ->
    eval_operation genv sp op vl1 = Some v1 ->
    exists v2, eval_operation genv sp op vl2 = Some v2 /\ mr v1 v2.

End EVAL_LESSDEF.


Section EVAL_INJECT.

Variable F V: Type.
Variable genv: Genv.t F V.
Variable f: meminj.
Variable ei : meminj -> expr_sym -> expr_sym -> Prop.
Hypothesis wf: wf_inj ei.
Hypothesis globals: meminj_preserves_globals genv f.
Variable sp1: block.
Variable sp2: block.
Variable delta: Z.
Hypothesis sp_inj: f sp1 = Some(sp2, delta).

Remark symbol_address_inject:
  forall id ofs, val_inject f (Genv.symbol_address genv id ofs) (Genv.symbol_address genv id ofs).

Lemma sp_inject:
  forall b1 ofs b2 delta0,
    f b1 = Some (b2, delta0) ->
    ei f (Eval (Vptr b1 ofs))
       (Eval (Vptr b2 (Int.add ofs (Int.repr delta0)))).

Lemma eval_condition_inject:
  forall cond vl1 vl2 b,
    list_ei ei f vl1 vl2 ->
    eval_condition cond vl1 = Some b ->
    exists b1, eval_condition cond vl2 = Some b1 /\ ei f b b1.

Inductive opt_same_eval : option expr_sym -> option expr_sym -> Prop :=
| opt_same_eval_None : opt_same_eval None None
| opt_same_eval_Some : forall e e' (OPTSAME : same_eval e e'), opt_same_eval (Some e) (Some e').


Instance EquiOptSameEval : Equivalence opt_same_eval.

Lemma eval_addressing_mod_norm:
  forall addr vl a b
         (EQM: same_eval a b),
    opt_same_eval (eval_addressing genv a addr vl) (eval_addressing genv b addr vl).

Add Parametric Morphism
  : (eval_addressing genv) with
    signature same_eval ==> @eq addressing ==> (@eq (list expr_sym)) ==> opt_same_eval as eval_addressing_same_eval.

Lemma eval_addressing_inject:
  forall addr vl1 vl2 v1,
    list_ei ei f vl1 vl2 ->
    eval_addressing genv (Eval (Vptr sp1 Int.zero)) addr vl1 = Some v1 ->
    exists v2 e,
      eval_addressing genv (Eval (Vptr sp2 Int.zero)) (shift_stack_addressing (Int.repr delta) addr) vl2 = Some v2
      /\ same_eval v2 e
      /\ ei f v1 e.


Lemma eval_operation_mod_norm:
  forall vl a b op
         (EQM: same_eval a b), opt_same_eval (eval_operation genv a op vl) (eval_operation genv b op vl).

Add Parametric Morphism
  : (eval_operation genv) with
    signature same_eval ==> @eq operation ==> (@eq (list expr_sym)) ==> opt_same_eval as eval_operation_same_eval.
  
  
Lemma eval_operation_inject:
  forall op vl1 vl2 v1,
    list_ei ei f vl1 vl2 ->
    eval_operation genv (Eval (Vptr sp1 Int.zero)) op vl1 = Some v1 ->
    exists v2 e,
      eval_operation genv (Eval (Vptr sp2 Int.zero))
                     (shift_stack_operation (Int.repr delta) op) vl2 = Some e
      /\ same_eval v2 e
     /\ ei f v1 v2.

End EVAL_INJECT.



Ltac Inv := repeat match goal with
           | H : match ?vl with _ => _ end = Some _ |- _ =>
             destruct vl; try discriminate
           | H: Some _ = Some _ |- _ => inv H
           | H: list_forall2 _ (_ :: _) _ |- _ => inv H
           | H: list_forall2 _ nil _ |- _ => inv H
           | H: Val.lessdef_list (_::_) _ |- _ => inv H
           | H: Val.lessdef_list nil _ |- _ => inv H
     
         end.


Lemma eval_addressing_se:
  forall F V (genv: Genv.t F V) sp a vl1 vl2 v1
         (LF: Val.lessdef_list vl1 vl2)
         (EOP : eval_addressing genv sp a vl1 = Some v1),
  exists v2,
    eval_addressing genv sp a vl2 = Some v2 /\ Val.lessdef v1 v2.

Lemma eval_condition_se:
  forall F V (genv: Genv.t F V) c vl1 vl2 v1
         (LF: Val.lessdef_list vl1 vl2)
         (EOP : eval_condition c vl1 = Some v1),
  exists v2,
    eval_condition c vl2 = Some v2 /\
    Val.lessdef v1 v2.

Lemma eval_operation_se:
  forall F V (genv: Genv.t F V) sp op vl1 vl2 v1
         (LF: Val.lessdef_list vl1 vl2)
         (EOP: eval_operation genv sp op vl1 = Some v1),
  exists v2,
    eval_operation genv sp op vl2 = Some v2 /\
    Val.lessdef v1 v2.

Lemma eval_operation_inject' :
forall (F V : Type) (genv : Genv.t F V) (f : meminj),
  meminj_preserves_globals genv f ->
  forall (sp1 sp2 : block) (delta : Z),
    f sp1 = Some (sp2, delta) ->
    forall (op : operation) (vl1 vl2 : list expr_sym)
      (v1 : expr_sym) (m1 m2 : mem),
      expr_list_inject f vl1 vl2 ->
       eval_operation genv (Eval (Vptr sp1 Int.zero)) op vl1 = Some v1 ->
       exists v2 : expr_sym,
         eval_operation genv (Eval (Vptr sp2 Int.zero))
           (shift_stack_operation (Int.repr delta) op) vl2 =
         Some v2 /\ expr_inj_se f v1 v2.


Lemma eval_addressing_inject':
  forall (F V : Type) (genv : Genv.t F V) (f : meminj),
       meminj_preserves_globals genv f ->
       forall (sp1 sp2 : block) (delta : Z),
       f sp1 = Some (sp2, delta) ->
       forall (addr : addressing) (vl1 vl2 : list expr_sym)
         (v1 : expr_sym),
         expr_list_inject f vl1 vl2 ->
         eval_addressing genv (Eval (Vptr sp1 Int.zero)) addr vl1 = Some v1 ->
       exists v2 : expr_sym,
         eval_addressing genv (Eval (Vptr sp2 Int.zero))
           (shift_stack_addressing (Int.repr delta) addr) vl2 =
         Some v2 /\ expr_inj_se f v1 v2.


Ltac inv_se :=
  repeat match goal with
           | H: match ?vl with _ => _ end = Some _ |- _ => des vl
           | H: Some _ = Some _ |- _ => inv H
           | H: None = Some _ |- _ => inv H
           | H : list_forall2 _ (_ :: _) _ |- _=> inv H
           | H : list_forall2 _ nil _ |- _ => inv H
           | |- exists _, _ = _ /\ _ =>
             eexists; split; eauto;
             repeat match goal with
                      | |- same_eval ?a ?a => reflexivity
                      | |- same_eval _ _ => apply unop_same_eval; auto
                      | |- same_eval _ _ => apply binop_same_eval; auto
                    end; fail
         end.

Lemma eval_addressing_se':
  forall F V (ge: Genv.t F V) sp addr vl v,
    eval_addressing ge sp addr vl = Some v ->
    forall vl',
      list_forall2 same_eval vl vl' ->
      exists v',
        eval_addressing ge sp addr vl' = Some v' /\
        same_eval v v'.

Lemma eval_condition_se':
  forall c vl v,
    eval_condition c vl = Some v ->
    forall vl',
      list_forall2 same_eval vl vl' ->
      exists v',
        eval_condition c vl' = Some v' /\
        same_eval v v'.

Lemma eval_operation_se':
  forall F V (ge: Genv.t F V) sp o vl v,
    eval_operation ge sp o vl = Some v ->
    forall vl' ,
      list_forall2 same_eval vl vl' ->
      exists v',
        eval_operation ge sp o vl' = Some v' /\
        same_eval v v'.