(* Operations common to the Cminor and RTLabs front end stages. *)

(* Adapted from CompCert's Cminor.ma: *)

(* *********************************************************************)
(*                                                                     *)
(*              The Compcert verified compiler                         *)
(*                                                                     *)
(*          Xavier Leroy, INRIA Paris-Rocquencourt                     *)
(*                                                                     *)
(*  Copyright Institut National de Recherche en Informatique et en     *)
(*  Automatique.  All rights reserved.  This file is distributed       *)
(*  under the terms of the GNU General Public License as published by  *)
(*  the Free Software Foundation, either version 2 of the License, or  *)
(*  (at your option) any later version.  This file is also distributed *)
(*  under the terms of the INRIA Non-Commercial License Agreement.     *)
(*                                                                     *)
(* *********************************************************************)

include "common/Values.ma".

inductive constant : Type[0] ≝
  | Ointconst: ∀sz. bvint sz → constant    (**r integer constant *)
  | Ofloatconst: float → constant          (**r floating-point constant *)
  | Oaddrsymbol: ident → nat → constant    (**r address of the symbol plus the offset *)
  | Oaddrstack: nat → constant.            (**r stack pointer plus the given offset *)

definition boolsrc : typ → Prop ≝ λt. match t with [ ASTint _ _ ⇒ True | ASTptr _ ⇒ True | _ ⇒ False ].

inductive unary_operation : typ → typ → Type[0] ≝
  | Ocastint: ∀sz,sg,sz',sg'. unary_operation (ASTint sz sg) (ASTint sz' sg')  (**r integer casts *)
  | Onegint:  ∀sz,sg. unary_operation (ASTint sz sg) (ASTint sz sg)            (**r integer opposite *)
  | Onotbool: ∀t,sz,sg. boolsrc t → unary_operation t (ASTint sz sg)           (**r boolean negation  *)
  | Onotint:  ∀sz,sg. unary_operation (ASTint sz sg) (ASTint sz sg)            (**r bitwise complement  *)
  | Onegf: ∀sz. unary_operation (ASTfloat sz) (ASTfloat sz)                    (**r float opposite *)
  | Oabsf: ∀sz. unary_operation (ASTfloat sz) (ASTfloat sz)                    (**r float absolute value *)
  | Osingleoffloat: unary_operation (ASTfloat F64) (ASTfloat F32)              (**r float truncation *)
  | Ointoffloat:  ∀fsz,sz. unary_operation (ASTfloat fsz) (ASTint sz Signed)   (**r signed integer to float *)
  | Ointuoffloat: ∀fsz,sz. unary_operation (ASTfloat fsz) (ASTint sz Unsigned) (**r unsigned integer to float *)
  | Ofloatofint:  ∀fsz,sz. unary_operation (ASTint sz Signed) (ASTfloat fsz)   (**r float to signed integer *)
  | Ofloatofintu: ∀fsz,sz. unary_operation (ASTint sz Unsigned) (ASTfloat fsz) (**r float to unsigned integer *)
  | Oid: ∀t. unary_operation t t                                               (**r identity (used to move between registers *)
  | Optrofint: ∀sz,sg,r. unary_operation (ASTint sz sg) (ASTptr r)             (**r int to pointer with given representation *)
  | Ointofptr: ∀sz,sg,r. unary_operation (ASTptr r) (ASTint sz sg).            (**r pointer to int *)

inductive binary_operation : Type[0] ≝
  | Oadd: binary_operation                 (**r integer addition *)
  | Osub: binary_operation                 (**r integer subtraction *)
  | Omul: binary_operation                 (**r integer multiplication *)
  | Odiv: binary_operation                 (**r integer signed division *)
  | Odivu: binary_operation                (**r integer unsigned division *)
  | Omod: binary_operation                 (**r integer signed modulus *)
  | Omodu: binary_operation                (**r integer unsigned modulus *)
  | Oand: binary_operation                 (**r bitwise ``and'' *)
  | Oor: binary_operation                  (**r bitwise ``or'' *)
  | Oxor: binary_operation                 (**r bitwise ``xor'' *)
  | Oshl: binary_operation                 (**r left shift *)
  | Oshr: binary_operation                 (**r right signed shift *)
  | Oshru: binary_operation                (**r right unsigned shift *)
  | Oaddf: binary_operation                (**r float addition *)
  | Osubf: binary_operation                (**r float subtraction *)
  | Omulf: binary_operation                (**r float multiplication *)
  | Odivf: binary_operation                (**r float division *)
  | Ocmp: comparison -> binary_operation   (**r integer signed comparison *)
  | Ocmpu: comparison -> binary_operation  (**r integer unsigned comparison *)
  | Ocmpf: comparison -> binary_operation  (**r float comparison *)
  | Oaddp: binary_operation                (**r add an integer to a pointer *)
  | Osubpi: binary_operation               (**r subtract int from a pointers *)
  | Osubpp: intsize → binary_operation     (**r subtract two pointers *)
  | Ocmpp: comparison → binary_operation.  (**r compare pointers *)


(* * Evaluation of constants and operator applications.
    [None] is returned when the computation is undefined, e.g.
    if arguments are of the wrong types, or in case of an integer division
    by zero. *)

definition eval_constant : (ident → option block) → block → constant → option val ≝
λfind_symbol,sp,cst.
  match cst with
  [ Ointconst sz n ⇒ Some ? (Vint sz n)
  | Ofloatconst n ⇒ Some ? (Vfloat n)
  | Oaddrsymbol s ofs ⇒
      match find_symbol s with
      [ None ⇒ None ?
      | Some b ⇒ Some ? (Vptr Any b (match b with [ mk_block r id ⇒ universal_compat r id ]) (shift_offset ? zero_offset (repr I16 ofs)))
      ]
  | Oaddrstack ofs ⇒
      Some ? (Vptr Any sp ? (shift_offset ? zero_offset (repr I16 ofs)))
  ]. cases sp // qed.

definition eval_unop : ∀t,t'. unary_operation t t' → val → option val ≝
λt,t',op,arg.
  match op with
  [ Ocastint sz sg sz' sg' ⇒
      match sg with
      [ Unsigned ⇒ Some ? (zero_ext sz' arg)
      |   Signed ⇒ Some ? (sign_ext sz' arg)
      ]
  | Onegint sz sg ⇒ match arg with [ Vint sz1 n1 ⇒ Some ? (Vint sz1 (two_complement_negation ? n1)) | _ ⇒ None ? ]
  | Onotbool t sz sg _ ⇒
      match arg with
      [ Vint sz1 n1 ⇒ Some ? (Vint sz (if (eq_bv ? n1 (zero ?)) then (repr ? 1) else (zero ?)))
      | Vptr _ _ _ _ ⇒ Some ? (Vint sz (zero ?))
      | Vnull _ ⇒ Some ? (Vint sz (repr ? 1))
      | _ ⇒ None ?
      ]
  | Onotint sz sg ⇒ match arg with [ Vint sz1 n1 ⇒ Some ? (Vint sz1 (exclusive_disjunction_bv ? n1 (mone ?))) | _ ⇒ None ? ]
  | Onegf _ ⇒ match arg with [ Vfloat f1 ⇒ Some ? (Vfloat (Fneg f1)) | _ ⇒ None ? ]
  | Oabsf _ ⇒ match arg with [ Vfloat f1 ⇒ Some ? (Vfloat (Fabs f1)) | _ ⇒ None ? ]
  | Osingleoffloat ⇒ Some ? (singleoffloat arg)
  | Ointoffloat _ sz ⇒ match arg with [ Vfloat f1 ⇒ Some ? (Vint sz (intoffloat ? f1)) | _ ⇒ None ? ]
  | Ointuoffloat _ sz ⇒ match arg with [ Vfloat f1 ⇒ Some ? (Vint sz (intuoffloat ? f1)) | _ ⇒ None ? ]
  | Ofloatofint _ _ ⇒ match arg with [ Vint sz1 n1 ⇒ Some ? (Vfloat (floatofint ? n1)) | _ ⇒ None ? ]
  | Ofloatofintu _ _ ⇒ match arg with [ Vint sz1 n1 ⇒ Some ? (Vfloat (floatofintu ? n1)) | _ ⇒ None ? ]
  | Oid t ⇒ Some ? arg (* XXX should we restricted the values allowed? *)
  (* Only conversion of null pointers is specified. *)
  | Optrofint sz sg r ⇒ match arg with [ Vint sz1 n1 ⇒ if eq_bv ? n1 (zero ?) then Some ? (Vnull r) else None ? | _ ⇒ None ? ]
  | Ointofptr sz sg r ⇒ match arg with [ Vnull _ ⇒ Some ? (Vint sz (zero ?)) | _ ⇒ None ? ]
  ].

lemma elim_val_typ : ∀v,t. ∀P:val → Prop.
val_typ v t →
match t with
[ ASTint sz sg ⇒ ∀i.P (Vint sz i)
| ASTfloat sz ⇒ ∀f.P (Vfloat f)
| ASTptr r ⇒ P (Vnull r) ∧ ∀b,c,o. P (Vptr r b c o)
] →
P v.
#v #t #P *
[ 1,2: //
| #r * //
| #r #b #c #o * //
] qed.

lemma eval_unop_typ_correct : ∀t,t',op,v,v'.
  val_typ v t →
  eval_unop t t' op v = Some ? v' →
  val_typ v' t'.
#t #t' #op elim op
[ #sz #sg #sz' #sg' #v #v' #H @(elim_val_typ … H) #i whd in ⊢ (??%? → ?)
  cases sg whd in ⊢ (??%? → ?) #E' destruct %
| #sz #sg #v #v' #H @(elim_val_typ … H) #i whd in ⊢ (??%? → ?) #E' destruct %
| #t'' #sz #sg cases t''
  [ #sz' #sg' #H #v #v' #H1 @(elim_val_typ … H1) #i whd in ⊢ (??%? → ?) #E' destruct cases (eq_bv ???) whd in ⊢ (?%?) %
  | #r #H #v #v' #H1 @(elim_val_typ … H1) whd %
    [ whd in ⊢ (??%? → ?) #E' destruct; %
    | #b #c #o whd in ⊢ (??%? → ?) #E' destruct %
    ]
  | #f *
  ]
| #sz #sg #v #v' #H @(elim_val_typ … H) #i whd in ⊢ (??%? → ?) #E destruct %
| #sz #v #v' #H @(elim_val_typ … H) #f whd in ⊢ (??%? → ?) #E destruct %2
| #sz #v #v' #H @(elim_val_typ … H) #f whd in ⊢ (??%? → ?) #E destruct %2
| #v #v' #H @(elim_val_typ … H) #f whd in ⊢ (??%? → ?) #E destruct %2
| #fsz #sz #v #v' #H @(elim_val_typ … H) #f whd in ⊢ (??%? → ?) #E destruct %
| #fsz #sz #v #v' #H @(elim_val_typ … H) #f whd in ⊢ (??%? → ?) #E destruct %
| #fsz #sz #v #v' #H @(elim_val_typ … H) #i whd in ⊢ (??%? → ?) #E destruct %2
| #fsz #sz #v #v' #H @(elim_val_typ … H) #i whd in ⊢ (??%? → ?) #E destruct %2
| #t'' #v #v' #H whd in ⊢ (??%? → ?) #E destruct @H
| #sz #sg #r #v #v' #H @(elim_val_typ … H) #i whd in ⊢ (??%? → ?) cases (eq_bv ???)
  whd in ⊢ (??%? → ?) #E destruct //
| #sz #sg #r #v #v' #H @(elim_val_typ … H) %
  [ whd in ⊢ (??%? → ?) #E destruct %
  | #b #c #o whd in ⊢ (??%? → ?) #E destruct
  ]
] qed.
  
(* I think this is duplicated somewhere else *)
definition eval_compare_mismatch : comparison → option val ≝
λc. match c with [ Ceq ⇒ Some ? Vfalse | Cne ⇒ Some ? Vtrue | _ ⇒ None ? ].

(* Individual operations, adapted from Values.  These differ in that they
   implement the plain Cminor/RTLabs operations (e.g., with separate addition
   for ints,floats and pointers) and use option rather than Vundef.  The ones
   in Value are probably not needed. *)

definition ev_add ≝ λv1,v2: val.
  match v1 with
  [ Vint sz1 n1 ⇒ match v2 with
    [ Vint sz2 n2 ⇒ intsize_eq_elim ? sz1 sz2 ? n1
                    (λn1. Some ? (Vint ? (addition_n ? n1 n2)))
                    (None ?)
    | _ ⇒ None ? ]
  | _ ⇒ None ? ].

definition ev_sub ≝ λv1,v2: val.
  match v1 with
  [ Vint sz1 n1 ⇒ match v2 with
    [ Vint sz2 n2 ⇒ intsize_eq_elim ? sz1 sz2 ? n1
                    (λn1. Some ? (Vint ? (subtraction ? n1 n2)))
                    (None ?)
    | _ ⇒ None ? ]
  | _ ⇒ None ? ].

(* NB: requires arguments to be presented pointer first. *)
definition ev_addp ≝ λv1,v2: val.
  match v1 with
  [ Vptr r b1 p ofs1 ⇒ match v2 with
    [ Vint sz2 n2 ⇒ Some ? (Vptr r b1 p (shift_offset ? ofs1 n2))
    | _ ⇒ None ? ]
  | Vnull r ⇒ match v2 with
    [ Vint sz2 n2 ⇒ if eq_bv ? n2 (zero ?) then Some ? (Vnull r) else None ?
    | _ ⇒ None ?
    ]
  | _ ⇒ None ? ].

definition ev_subpi ≝ λv1,v2: val.
  match v1 with
  [ Vptr r1 b1 p1 ofs1 ⇒ match v2 with
    [ Vint sz2 n2 ⇒ Some ? (Vptr r1 b1 p1 (neg_shift_offset ? ofs1 n2))
    | _ ⇒ None ? ]
  | Vnull r ⇒ match v2 with [ Vint sz2 n2 ⇒ if eq_bv ? n2 (zero ?) then Some ? (Vnull r) else None ? | _ ⇒ None ? ]
  | _ ⇒ None ? ].

definition ev_subpp ≝ λsz. λv1,v2: val.
  match v1 with
  [ Vptr r1 b1 p1 ofs1 ⇒ match v2 with
    [ Vptr r2 b2 p2 ofs2 ⇒
        if eq_block b1 b2 then Some ? (Vint sz (sub_offset ? ofs1 ofs2)) else None ?
    | _ ⇒ None ? ]
  | Vnull r ⇒ match v2 with [ Vnull r' ⇒ Some ? (Vint sz (zero ?)) | _ ⇒ None ? ]
  | _ ⇒ None ? ].

definition ev_mul ≝ λv1, v2: val.
  match v1 with
  [ Vint sz1 n1 ⇒ match v2 with
    [ Vint sz2 n2 ⇒ intsize_eq_elim ? sz1 sz2 ? n1
                    (λn1. Some ? (Vint ? (\snd (split … (multiplication ? n1 n2)))))
                    (None ?)
    | _ ⇒ None ? ]
  | _ ⇒ None ? ].

definition ev_divs ≝ λv1, v2: val.
  match v1 with
  [ Vint sz1 n1 ⇒ match v2 with
    [ Vint sz2 n2 ⇒ intsize_eq_elim ? sz1 sz2 ? n1
                    (λn1. option_map ?? (Vint ?) (division_s ? n1 n2))
                    (None ?)
    | _ ⇒ None ? ]
  | _ ⇒ None ? ].

definition ev_mods ≝ λv1, v2: val.
  match v1 with
  [ Vint sz1 n1 ⇒ match v2 with
    [ Vint sz2 n2 ⇒ intsize_eq_elim ? sz1 sz2 ? n1
                    (λn1. option_map ?? (Vint ?) (modulus_s ? n1 n2))
                    (None ?)
    | _ ⇒ None ?
    ]
  | _ ⇒ None ?
  ].

definition ev_divu ≝ λv1, v2: val.
  match v1 with
  [ Vint sz1 n1 ⇒ match v2 with
    [ Vint sz2 n2 ⇒ intsize_eq_elim ? sz1 sz2 ? n1
                    (λn1. option_map ?? (Vint ?) (division_u ? n1 n2))
                    (None ?)
    | _ ⇒ None ?
    ]
  | _ ⇒ None ?
  ].

definition ev_modu ≝ λv1, v2: val.
  match v1 with
  [ Vint sz1 n1 ⇒ match v2 with
    [ Vint sz2 n2 ⇒ intsize_eq_elim ? sz1 sz2 ? n1
                    (λn1. option_map ?? (Vint ?) (modulus_u ? n1 n2))
                    (None ?)
    | _ ⇒ None ?
    ]
  | _ ⇒ None ?
  ].

definition ev_and ≝ λv1, v2: val.
  match v1 with
  [ Vint sz1 n1 ⇒ match v2 with
    [ Vint sz2 n2 ⇒ intsize_eq_elim ? sz1 sz2 ? n1
                    (λn1. Some ? (Vint ? (conjunction_bv ? n1 n2)))
                    (None ?)
    | _ ⇒ None ? ]
  | _ ⇒ None ? ].

definition ev_or ≝ λv1, v2: val.
  match v1 with
  [ Vint sz1 n1 ⇒ match v2 with
    [ Vint sz2 n2 ⇒ intsize_eq_elim ? sz1 sz2 ? n1
                    (λn1. Some ? (Vint ? (inclusive_disjunction_bv ? n1 n2)))
                    (None ?)
    | _ ⇒ None ? ]
  | _ ⇒ None ? ].

definition ev_xor ≝ λv1, v2: val.
  match v1 with
  [ Vint sz1 n1 ⇒ match v2 with
    [ Vint sz2 n2 ⇒ intsize_eq_elim ? sz1 sz2 ? n1
                    (λn1. Some ? (Vint ? (exclusive_disjunction_bv ? n1 n2)))
                    (None ?)
    | _ ⇒ None ? ]
  | _ ⇒ None ? ].

definition ev_shl ≝ λv1, v2: val.
  match v1 with
  [ Vint sz1 n1 ⇒ match v2 with 
    [ Vint sz2 n2 ⇒
       if lt_u ? n2 (bitvector_of_nat … (bitsize_of_intsize sz1))
       then Some ? (Vint sz1 (shift_left ?? (nat_of_bitvector … n2) n1 false))
       else None ?
    | _ ⇒ None ? ]
  | _ ⇒ None ? ].

definition ev_shr ≝ λv1, v2: val.
  match v1 with
  [ Vint sz1 n1 ⇒ match v2 with 
    [ Vint sz2 n2 ⇒
       if lt_u ? n2 (bitvector_of_nat … (bitsize_of_intsize sz1))
       then Some ? (Vint sz1 (shift_right ?? (nat_of_bitvector … n2) n1 (head' … n1)))
       else None ?
    | _ ⇒ None ? ]
  | _ ⇒ None ? ].

definition ev_shru ≝ λv1, v2: val.
  match v1 with
  [ Vint sz1 n1 ⇒ match v2 with 
    [ Vint sz2 n2 ⇒
       if lt_u ? n2 (bitvector_of_nat … (bitsize_of_intsize sz1))
       then Some ? (Vint sz1 (shift_right ?? (nat_of_bitvector … n2) n1 false))
       else None ?
    | _ ⇒ None ? ]
  | _ ⇒ None ? ].

definition ev_addf ≝ λv1,v2: val.
  match v1 with
  [ Vfloat f1 ⇒ match v2 with
    [ Vfloat f2 ⇒ Some ? (Vfloat (Fadd f1 f2))
    | _ ⇒ None ? ]
  | _ ⇒ None ? ].

definition ev_subf ≝ λv1,v2: val.
  match v1 with
  [ Vfloat f1 ⇒ match v2 with
    [ Vfloat f2 ⇒ Some ? (Vfloat (Fsub f1 f2))
    | _ ⇒ None ? ]
  | _ ⇒ None ? ].

definition ev_mulf ≝ λv1,v2: val.
  match v1 with
  [ Vfloat f1 ⇒ match v2 with
    [ Vfloat f2 ⇒ Some ? (Vfloat (Fmul f1 f2))
    | _ ⇒ None ? ]
  | _ ⇒ None ? ].

definition ev_divf ≝ λv1,v2: val.
  match v1 with
  [ Vfloat f1 ⇒ match v2 with
    [ Vfloat f2 ⇒ Some ? (Vfloat (Fdiv f1 f2))
    | _ ⇒ None ? ]
  | _ ⇒ None ? ].

definition ev_cmp_match : comparison → option val ≝ λc.
  match c with
  [ Ceq ⇒ Some ? Vtrue
  | Cne ⇒ Some ? Vfalse
  | _   ⇒ None ?
  ].

definition ev_cmp_mismatch : comparison → option val ≝ λc.
  match c with
  [ Ceq ⇒ Some ? Vfalse
  | Cne ⇒ Some ? Vtrue
  | _   ⇒ None ?
  ].

definition ev_cmp ≝ λc: comparison. λv1,v2: val.
  match v1 with
  [ Vint sz1 n1 ⇒ match v2 with
    [ Vint sz2 n2 ⇒ intsize_eq_elim ? sz1 sz2 ? n1
                    (λn1. Some ? (of_bool (cmp_int ? c n1 n2)))
                    (None ?)
    | _ ⇒ None ? ]
  | _ ⇒ None ? ].

definition ev_cmpp ≝ λc: comparison. λv1,v2: val.
  match v1 with
  [ Vptr r1 b1 p1 ofs1 ⇒ match v2 with
    [ Vptr r2 b2 p2 ofs2 ⇒
        if eq_block b1 b2
        then Some ? (of_bool (cmp_offset c ofs1 ofs2))
        else ev_cmp_mismatch c
    | Vnull r2 ⇒ ev_cmp_mismatch c
    | _ ⇒ None ? ]
  | Vnull r1 ⇒ match v2 with
    [ Vptr _ _ _ _ ⇒ ev_cmp_mismatch c
    | Vnull r2 ⇒ ev_cmp_match c
    | _ ⇒ None ?
    ]
  | _ ⇒ None ? ].

(* TODO: check this, it isn't the cmpu used elsewhere *)
definition ev_cmpu ≝ λc: comparison. λv1,v2: val.
  match v1 with
  [ Vint sz1 n1 ⇒ match v2 with
    [ Vint sz2 n2 ⇒ intsize_eq_elim ? sz1 sz2 ? n1
                    (λn1. Some ? (of_bool (cmpu_int ? c n1 n2)))
                    (None ?)
    | _ ⇒ None ? ]
  | _ ⇒ None ? ].

definition ev_cmpf ≝ λc: comparison. λv1,v2: val.
  match v1 with
  [ Vfloat f1 ⇒ match v2 with
    [ Vfloat f2 ⇒ Some ? (of_bool (Fcmp c f1 f2))
    | _ ⇒ None ? ]
  | _ ⇒ None ? ].

definition eval_binop : binary_operation → val → val → option val ≝
λop.
  match op with
  [ Oadd ⇒ ev_add
  | Osub ⇒ ev_sub
  | Omul ⇒ ev_mul
  | Odiv ⇒ ev_divs
  | Odivu ⇒ ev_divu
  | Omod ⇒ ev_mods
  | Omodu ⇒ ev_modu
  | Oand ⇒ ev_and
  | Oor ⇒ ev_or
  | Oxor ⇒ ev_xor
  | Oshl ⇒ ev_shl
  | Oshr ⇒ ev_shr
  | Oshru ⇒ ev_shru
  | Oaddf ⇒ ev_addf
  | Osubf ⇒ ev_subf
  | Omulf ⇒ ev_mulf
  | Odivf ⇒ ev_divf
  | Ocmp c ⇒ ev_cmp c
  | Ocmpu c ⇒ ev_cmpu c
  | Ocmpf c ⇒ ev_cmpf c
  | Oaddp ⇒ ev_addp
  | Osubpi ⇒ ev_subpi
  | Osubpp sz ⇒ ev_subpp sz
  | Ocmpp c ⇒ ev_cmpp c
  ].