Require Import Coq.Sorting.Permutation.
Require Import Coq.Sorting.Sorting.
Require Import Coq.Structures.Orders.
Require Import VST.veric.base.
Require Import compcert.cfrontend.Ctypes. (*Require Import VST.veric.Clight_lemmas.*)
Require Import VST.veric.type_induction.
Require Import VST.veric.composite_compute.

(* This file contains three computational align criteria.
   1: the hardware alignof is not larger than alignof (and additional criterion for array).
   2: all fields are aligned as hardware requires. size as a multiple of hardware alignof.
   3: all value is well-aligned stored.
   The third one is the final specification we want. *)

Section align_compatible_rec.

Context (cenv: composite_env).

Inductive align_compatible_rec: type -> Z -> Prop :=
| align_compatible_rec_by_value: forall t ch z, access_mode t = By_value ch -> (Memdata.align_chunk ch | z) -> align_compatible_rec t z
| align_compatible_rec_Tarray: forall t n a z, (forall i, 0 <= i < n -> align_compatible_rec t (z + sizeof cenv t * i)) -> align_compatible_rec (Tarray t n a) z
| align_compatible_rec_Tstruct: forall i a co z, cenv ! i = Some co -> (forall i0 t0 z0, field_type i0 (co_members co) = Errors.OK t0 -> field_offset cenv i0 (co_members co) = Errors.OK z0 -> align_compatible_rec t0 (z + z0)) -> align_compatible_rec (Tstruct i a) z
| align_compatible_rec_Tunion: forall i a co z, cenv ! i = Some co -> (forall i0 t0, field_type i0 (co_members co) = Errors.OK t0 -> align_compatible_rec t0 z) -> align_compatible_rec (Tunion i a) z.

Lemma align_compatible_rec_by_value_inv : forall t ch z,
  access_mode t = By_value ch ->
  align_compatible_rec t z -> (Memdata.align_chunk ch | z).
Proof.
(* Goal: forall (t : type) (ofs : Z) (_ : @eq bool (is_aligned cenv ha_env la_env t ofs) true) (_ : @ex memory_chunk (fun ch : memory_chunk => @eq mode (access_mode t) (By_value ch))), align_compatible_rec cenv t ofs *)
  intros.
(* Goal: align_compatible_rec cenv (Tpointer t a) z *)
  inv H0.
  + rewrite H in H1; inv H1; auto.
  + inv H.
  + inv H.
  + inv H.
Qed.

Lemma align_compatible_rec_Tarray_inv: forall t n a z,
  align_compatible_rec (Tarray t n a) z ->
  (forall i : Z, 0 <= i < n -> align_compatible_rec t (z + sizeof cenv t * i)).
Proof.
(* Goal: forall (t : type) (ofs : Z) (_ : @eq bool (is_aligned cenv ha_env la_env t ofs) true) (_ : @ex memory_chunk (fun ch : memory_chunk => @eq mode (access_mode t) (By_value ch))), align_compatible_rec cenv t ofs *)
  intros.
(* Goal: align_compatible_rec cenv t0 z *)
  inv H.
  + inv H1.
  + auto.
Qed.

Lemma align_compatible_rec_Tstruct_inv: forall i a co z,
  cenv ! i = Some co ->
  align_compatible_rec (Tstruct i a) z ->
  (forall i0 t0 z0, field_type i0 (co_members co) = Errors.OK t0 -> field_offset cenv i0 (co_members co) = Errors.OK z0 -> align_compatible_rec t0 (z + z0)).
Proof.
(* Goal: forall (t : type) (ofs : Z) (_ : @eq bool (is_aligned cenv ha_env la_env t ofs) true) (_ : @ex memory_chunk (fun ch : memory_chunk => @eq mode (access_mode t) (By_value ch))), align_compatible_rec cenv t ofs *)
  intros.
(* Goal: align_compatible_rec cenv (Tpointer t a) z *)
  inv H0.
  + inv H3.
  + rewrite H in H5; inv H5.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
    eauto.
Qed.
  
Lemma align_compatible_rec_Tunion_inv: forall i a co z,
  cenv ! i = Some co ->
  align_compatible_rec (Tunion i a) z ->
  (forall i0 t0, field_type i0 (co_members co) = Errors.OK t0 -> align_compatible_rec t0 z).
Proof.
(* Goal: forall (t : type) (ofs : Z) (_ : @eq bool (is_aligned cenv ha_env la_env t ofs) true) (_ : @ex memory_chunk (fun ch : memory_chunk => @eq mode (access_mode t) (By_value ch))), align_compatible_rec cenv t ofs *)
  intros.
(* Goal: align_compatible_rec cenv (Tpointer t a) z *)
  inv H0.
  + inv H2.
  + rewrite H in H4; inv H4.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
    eauto.
Qed.

End align_compatible_rec.

Lemma align_chunk_1248: forall ch, align_chunk ch = 1 \/ align_chunk ch = 2 \/ align_chunk ch = 4 \/ align_chunk ch = 8.
Proof.
(* Goal: forall (t : type) (ofs : Z) (_ : @eq bool (is_aligned cenv ha_env la_env t ofs) true) (_ : @ex memory_chunk (fun ch : memory_chunk => @eq mode (access_mode t) (By_value ch))), align_compatible_rec cenv t ofs *)
  intros.
  destruct ch; simpl;
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
  auto.
Qed.

Lemma align_chunk_two_p:
  forall ch, exists n, align_chunk ch = two_power_nat n.
Proof.
(* Goal: forall (t : type) (ofs : Z) (_ : @eq bool (is_aligned cenv ha_env la_env t ofs) true) (_ : @ex memory_chunk (fun ch : memory_chunk => @eq mode (access_mode t) (By_value ch))), align_compatible_rec cenv t ofs *)
  intros.
(* Goal: @ex nat (fun n : nat => @eq Z (align_chunk ch) (two_power_nat n)) *)
  pose proof align_chunk_1248 ch as [| [| [|]]]; rewrite H.
  + exists 0%nat; auto.
  + exists 1%nat; auto.
  + exists 2%nat; auto.
  + exists 3%nat; auto.
Qed.

Fixpoint hardware_alignof (ha_env: PTree.t Z) t: Z :=
  match t with
  | Tarray t' _ _ => hardware_alignof ha_env t'
  | Tstruct id _ =>
      match ha_env ! id with
      | Some ha => ha
      | None => 1
      end
  | Tunion id _ =>
      match ha_env ! id with
      | Some ha => ha
      | None => 1
      end
  | _ => match access_mode t with
         | By_value ch => Memdata.align_chunk ch
         | _ => 1
         end
  end.

Fixpoint hardware_alignof_composite (ha_env: PTree.t Z) (m: members): Z :=
  match m with
  | nil => 1
  | (_, t) :: m' => Z.max (hardware_alignof ha_env t) (hardware_alignof_composite ha_env m')
  end.

Definition hardware_alignof_env (cenv: composite_env): PTree.t Z :=
  let l := composite_reorder.rebuild_composite_elements cenv in
  fold_right (fun (ic: positive * composite) (T0: PTree.t Z) => let (i, co) := ic in let T := T0 in PTree.set i (hardware_alignof_composite T (co_members co)) T) (PTree.empty _) l.

Definition hardware_alignof_env_consistent (cenv: composite_env) (ha_env: PTree.t Z): Prop :=
  forall i co ha,
    cenv ! i = Some co ->
    ha_env ! i = Some ha ->
    ha = hardware_alignof_composite ha_env (co_members co).

Definition hardware_alignof_env_complete (cenv: composite_env) (ha_env: PTree.t Z): Prop :=
  forall i,
    (exists co, cenv ! i = Some co) <->
    (exists ha, ha_env ! i = Some ha).

Module Type HARDWARE_ALIGNOF_FACTS.

  Axiom hardware_alignof_consistency:
    forall (cenv: composite_env) (ha_env: PTree.t Z),
      composite_env_consistent cenv ->
      ha_env = hardware_alignof_env cenv ->
      hardware_alignof_env_consistent cenv ha_env.

  Axiom hardware_alignof_completeness:
    forall (cenv: composite_env) (ha_env: PTree.t Z),
      ha_env = hardware_alignof_env cenv ->
      hardware_alignof_env_complete cenv ha_env.

End HARDWARE_ALIGNOF_FACTS.

Module hardware_alignof_facts: HARDWARE_ALIGNOF_FACTS.

Lemma aux1: forall T co,
  (fix fm (l : list (ident * type * Z)) : Z :=
     match l with
     | nil => 1
     | (_, _, ha) :: l' => Z.max ha (fm l')
     end)
    (map
       (fun it0 : positive * type =>
        let (i0, t0) := it0 in
        (i0, t0,
        type_func.F
          (fun t : type =>
           match access_mode t with
           | By_value ch => align_chunk ch
           | By_reference => 1
           | By_copy => 1
           | By_nothing => 1
           end) (fun (ha : Z) (_ : type) (_: Z) (_ : attr) => ha)
          (fun (ha : Z) (_ : ident) (_ : attr) => ha)
          (fun (ha : Z) (_ : ident) (_ : attr) => ha) T t0)) (co_members co)) =
                    hardware_alignof_composite T (co_members co).
Proof.
(* Goal: forall (T : PTree.t Z) (co : composite), @eq Z ((fix fm (l : list (prod (prod ident type) Z)) : Z := match l with | nil => Zpos xH | cons (pair (pair i t as p0) ha as p) l' => Z.max ha (fm l') end) (@map (prod positive type) (prod (prod positive type) Z) (fun it0 : prod positive type => let (i0, t0) := it0 in @pair (prod positive type) Z (@pair positive type i0 t0) (@type_func.F Z (fun t : type => match access_mode t with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end) (fun (ha : Z) (_ : type) (_ : Z) (_ : attr) => ha) (fun (ha : Z) (_ : ident) (_ : attr) => ha) (fun (ha : Z) (_ : ident) (_ : attr) => ha) T t0)) (co_members co))) (hardware_alignof_composite T (co_members co)) *)
  intros; unfold hardware_alignof_composite, hardware_alignof.
(* Goal: @eq Z ((fix fm (l : list (prod (prod ident type) Z)) : Z := match l with | nil => Zpos xH | cons (pair (pair i t as p0) ha as p) l' => Z.max ha (fm l') end) (@map (prod positive type) (prod (prod positive type) Z) (fun it0 : prod positive type => let (i0, t0) := it0 in @pair (prod positive type) Z (@pair positive type i0 t0) (@type_func.F Z (fun t : type => match access_mode t with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end) (fun (ha : Z) (_ : type) (_ : Z) (_ : attr) => ha) (fun (ha : Z) (_ : ident) (_ : attr) => ha) (fun (ha : Z) (_ : ident) (_ : attr) => ha) T t0)) (co_members co))) ((fix hardware_alignof_composite (ha_env : PTree.t Z) (m : members) {struct m} : Z := match m with | nil => Zpos xH | cons (pair i t as p) m' => Z.max ((fix hardware_alignof (ha_env0 : PTree.t Z) (t0 : type) {struct t0} : Z := match t0 with | Tvoid => match access_mode t0 with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end | Tint i0 s a => match access_mode t0 with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end | Tlong s a => match access_mode t0 with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end | Tfloat f a => match access_mode t0 with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end | Tpointer t1 a => match access_mode t0 with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end | Tarray t' z a => hardware_alignof ha_env0 t' | Tfunction t1 t2 c => match access_mode t0 with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end | Tstruct id a => match @PTree.get Z id ha_env0 with | Some ha => ha | None => Zpos xH end | Tunion id a => match @PTree.get Z id ha_env0 with | Some ha => ha | None => Zpos xH end end) ha_env t) (hardware_alignof_composite ha_env m') end) T (co_members co)) *)
  induction (co_members co) as [| [i t] ?].
  + auto.
  + simpl.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
    f_equal; auto.
(* Goal: @eq Z (@type_func.F Z (fun t : type => match access_mode t with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end) (fun (ha : Z) (_ : type) (_ : Z) (_ : attr) => ha) (fun (ha : Z) (_ : ident) (_ : attr) => ha) (fun (ha : Z) (_ : ident) (_ : attr) => ha) T t) ((fix hardware_alignof (ha_env : PTree.t Z) (t : type) {struct t} : Z := match t with | Tvoid => match access_mode t with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end | Tint i s a => match access_mode t with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end | Tlong s a => match access_mode t with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end | Tfloat f a => match access_mode t with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end | Tpointer t0 a => match access_mode t with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end | Tarray t' z a => hardware_alignof ha_env t' | Tfunction t0 t1 c => match access_mode t with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end | Tstruct id a => match @PTree.get Z id ha_env with | Some ha => ha | None => Zpos xH end | Tunion id a => match @PTree.get Z id ha_env with | Some ha => ha | None => Zpos xH end end) T t) *)
    clear.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
    induction t; auto.
Qed.

Lemma aux2: forall (cenv: composite_env),
  type_func.Env
          (fun t : type =>
           match access_mode t with
           | By_value ch => align_chunk ch
           | By_reference => 1
           | By_copy => 1
           | By_nothing => 1
           end) (fun (ha : Z) (_ : type) (_: Z) (_ : attr) => ha)
          (fun (ha : Z) (_ : ident) (_ : attr) => ha)
          (fun (ha : Z) (_ : ident) (_ : attr) => ha)
          (fun _ : struct_or_union =>
           fix fm (l : list (ident * type * Z)) : Z :=
             match l with
             | nil => 1
             | (_, _, ha) :: l' => Z.max ha (fm l')
             end) (composite_reorder.rebuild_composite_elements cenv) =
  hardware_alignof_env cenv.
Proof.
(* Goal: forall (t : type) (ofs : Z) (_ : @eq bool (is_aligned cenv ha_env la_env t ofs) true) (_ : @ex memory_chunk (fun ch : memory_chunk => @eq mode (access_mode t) (By_value ch))), align_compatible_rec cenv t ofs *)
  intros.
(* Goal: @eq (PTree.t Z) (@type_func.Env Z (fun t : type => match access_mode t with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end) (fun (ha : Z) (_ : type) (_ : Z) (_ : attr) => ha) (fun (ha : Z) (_ : ident) (_ : attr) => ha) (fun (ha : Z) (_ : ident) (_ : attr) => ha) (fun _ : struct_or_union => fix fm (l : list (prod (prod ident type) Z)) : Z := match l with | nil => Zpos xH | cons (pair (pair i t as p0) ha as p) l' => Z.max ha (fm l') end) (composite_reorder.rebuild_composite_elements cenv)) (hardware_alignof_env cenv) *)
  unfold type_func.Env, type_func.env_rec, hardware_alignof_env.
(* Goal: @eq (PTree.t Z) (@PTree.set Z i ((fix fm (l : list (prod (prod ident type) Z)) : Z := match l with | nil => Zpos xH | cons (pair (pair i t as p0) ha as p) l' => Z.max ha (fm l') end) (@map (prod positive type) (prod (prod positive type) Z) (fun it0 : prod positive type => let (i0, t0) := it0 in @pair (prod positive type) Z (@pair positive type i0 t0) (@type_func.F Z (fun t : type => match access_mode t with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end) (fun (ha : Z) (_ : type) (_ : Z) (_ : attr) => ha) (fun (ha : Z) (_ : ident) (_ : attr) => ha) (fun (ha : Z) (_ : ident) (_ : attr) => ha) T t0)) (co_members co))) T) (@PTree.set Z i (hardware_alignof_composite T (co_members co)) T) *)
  f_equal.
(* Goal: @eq (forall (_ : prod positive composite) (_ : PTree.t Z), PTree.t Z) (fun ic : prod positive composite => let (i, co) := ic in fun env : PTree.t Z => @PTree.set Z i ((fix fm (l : list (prod (prod ident type) Z)) : Z := match l with | nil => Zpos xH | cons (pair (pair i0 t as p0) ha as p) l' => Z.max ha (fm l') end) (@map (prod positive type) (prod (prod positive type) Z) (fun it0 : prod positive type => let (i0, t0) := it0 in @pair (prod positive type) Z (@pair positive type i0 t0) (@type_func.F Z (fun t : type => match access_mode t with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end) (fun (ha : Z) (_ : type) (_ : Z) (_ : attr) => ha) (fun (ha : Z) (_ : ident) (_ : attr) => ha) (fun (ha : Z) (_ : ident) (_ : attr) => ha) env t0)) (co_members co))) env) (fun (ic : prod positive composite) (T0 : PTree.t Z) => let (i, co) := ic in @PTree.set Z i (hardware_alignof_composite T0 (co_members co)) T0) *)
  extensionality ic.
(* Goal: @eq (forall _ : PTree.t Z, PTree.t Z) (let (i, co) := ic in fun env : PTree.t Z => @PTree.set Z i ((fix fm (l : list (prod (prod ident type) Z)) : Z := match l with | nil => Zpos xH | cons (pair (pair i0 t as p0) ha as p) l' => Z.max ha (fm l') end) (@map (prod positive type) (prod (prod positive type) Z) (fun it0 : prod positive type => let (i0, t0) := it0 in @pair (prod positive type) Z (@pair positive type i0 t0) (@type_func.F Z (fun t : type => match access_mode t with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end) (fun (ha : Z) (_ : type) (_ : Z) (_ : attr) => ha) (fun (ha : Z) (_ : ident) (_ : attr) => ha) (fun (ha : Z) (_ : ident) (_ : attr) => ha) env t0)) (co_members co))) env) (fun T0 : PTree.t Z => let (i, co) := ic in @PTree.set Z i (hardware_alignof_composite T0 (co_members co)) T0) *)
  destruct ic as [i co].
(* Goal: @eq (forall _ : PTree.t Z, PTree.t Z) (fun env : PTree.t Z => @PTree.set Z i ((fix fm (l : list (prod (prod ident type) Z)) : Z := match l with | nil => Zpos xH | cons (pair (pair i t as p0) ha as p) l' => Z.max ha (fm l') end) (@map (prod positive type) (prod (prod positive type) Z) (fun it0 : prod positive type => let (i0, t0) := it0 in @pair (prod positive type) Z (@pair positive type i0 t0) (@type_func.F Z (fun t : type => match access_mode t with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end) (fun (ha : Z) (_ : type) (_ : Z) (_ : attr) => ha) (fun (ha : Z) (_ : ident) (_ : attr) => ha) (fun (ha : Z) (_ : ident) (_ : attr) => ha) env t0)) (co_members co))) env) (fun T0 : PTree.t Z => @PTree.set Z i (hardware_alignof_composite T0 (co_members co)) T0) *)
  extensionality T.
(* Goal: @eq (PTree.t Z) (@PTree.set Z i ((fix fm (l : list (prod (prod ident type) Z)) : Z := match l with | nil => Zpos xH | cons (pair (pair i t as p0) ha as p) l' => Z.max ha (fm l') end) (@map (prod positive type) (prod (prod positive type) Z) (fun it0 : prod positive type => let (i0, t0) := it0 in @pair (prod positive type) Z (@pair positive type i0 t0) (@type_func.F Z (fun t : type => match access_mode t with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end) (fun (ha : Z) (_ : type) (_ : Z) (_ : attr) => ha) (fun (ha : Z) (_ : ident) (_ : attr) => ha) (fun (ha : Z) (_ : ident) (_ : attr) => ha) T t0)) (co_members co))) T) (@PTree.set Z i (hardware_alignof_composite T (co_members co)) T) *)
  f_equal.
(* Goal: @eq Z ((fix fm (l : list (prod (prod ident type) Z)) : Z := match l with | nil => Zpos xH | cons (pair (pair i t as p0) ha as p) l' => Z.max ha (fm l') end) (@map (prod positive type) (prod (prod positive type) Z) (fun it0 : prod positive type => let (i0, t0) := it0 in @pair (prod positive type) Z (@pair positive type i0 t0) (@type_func.F Z (fun t : type => match access_mode t with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end) (fun (ha : Z) (_ : type) (_ : Z) (_ : attr) => ha) (fun (ha : Z) (_ : ident) (_ : attr) => ha) (fun (ha : Z) (_ : ident) (_ : attr) => ha) T t0)) (co_members co))) (hardware_alignof_composite T (co_members co)) *)
  apply aux1.
Qed.

Lemma hardware_alignof_consistency (cenv: composite_env) (ha_env: PTree.t Z):
  composite_env_consistent cenv ->
  ha_env = hardware_alignof_env cenv ->
  forall i co ha,
    cenv ! i = Some co ->
    ha_env ! i = Some ha ->
    ha = hardware_alignof_composite ha_env (co_members co).
Proof.
(* Goal: forall (t : type) (ofs : Z) (_ : @eq bool (is_aligned cenv ha_env la_env t ofs) true) (_ : @ex memory_chunk (fun ch : memory_chunk => @eq mode (access_mode t) (By_value ch))), align_compatible_rec cenv t ofs *)
  intros.
  pose proof @composite_reorder_consistent Z cenv
             (fun t =>
                match access_mode t with
                | By_value ch => Memdata.align_chunk ch
                | _ => 1
                end)
             (fun ha _ _ _ => ha)
             (fun ha _ _ => ha)
             (fun ha _ _ => ha)
             (fun _ =>
                fix fm (l: list (ident * type * Z)): Z :=
                match l with
                | nil => 1
                | (_, _, ha) :: l' => Z.max ha (fm l')
                end)
             H
    as HH.
(* Goal: legal_alignas_env_complete cenv (legal_alignas_env cenv ha_env) *)
  hnf in HH.
(* Goal: @eq Z ha (hardware_alignof_composite ha_env (co_members co)) *)
  subst ha_env.
(* Goal: legal_alignas_env_complete cenv (legal_alignas_env cenv ha_env) *)
  rewrite aux2 in HH.
(* Goal: @eq Z ha (hardware_alignof_composite (hardware_alignof_env cenv) (co_members co)) *)
  specialize (HH _ _ ha H1 H2).
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
  rewrite HH, aux1; auto.
Qed.

Lemma hardware_alignof_completeness (cenv: composite_env) (ha_env: PTree.t Z):
  ha_env = hardware_alignof_env cenv ->
  forall i,
    (exists co, cenv ! i = Some co) <->
    (exists ha, ha_env ! i = Some ha).
Proof.
(* Goal: forall (t : type) (ofs : Z) (_ : @eq bool (is_aligned cenv ha_env la_env t ofs) true) (_ : @ex memory_chunk (fun ch : memory_chunk => @eq mode (access_mode t) (By_value ch))), align_compatible_rec cenv t ofs *)
  intros.
  pose proof @composite_reorder_complete Z cenv
             (fun t =>
                match access_mode t with
                | By_value ch => Memdata.align_chunk ch
                | _ => 1
                end)
             (fun ha _ _ _ => ha)
             (fun ha _ _ => ha)
             (fun ha _ _ => ha)
             (fun _ =>
                fix fm (l: list (ident * type * Z)): Z :=
                match l with
                | nil => 1
                | (_, _, ha) :: l' => Z.max ha (fm l')
                end)
    as HH.
(* Goal: legal_alignas_env_complete cenv (legal_alignas_env cenv ha_env) *)
  hnf in HH.
(* Goal: iff (@ex composite (fun co : composite => @eq (option composite) (@PTree.get composite i cenv) (@Some composite co))) (@ex Z (fun ha : Z => @eq (option Z) (@PTree.get Z i ha_env) (@Some Z ha))) *)
  subst.
(* Goal: legal_alignas_env_complete cenv (legal_alignas_env cenv ha_env) *)
  rewrite aux2 in HH.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
  auto.
Qed.

End hardware_alignof_facts.

Export hardware_alignof_facts.

Lemma hardware_alignof_two_p: forall (cenv: composite_env) (ha_env: PTree.t Z),
  composite_env_consistent cenv ->
  hardware_alignof_env_consistent cenv ha_env ->
  hardware_alignof_env_complete cenv ha_env ->
  forall t, exists n,
  hardware_alignof ha_env t = two_power_nat n.
Proof.
  intros ? ? CENV_CONS HA_ENV_CONS HA_ENV_COMPL ?.
  type_induction t cenv CENV_CONS.
  + exists 0%nat; reflexivity.
  + destruct s, i; try solve [exists 0%nat; reflexivity | exists 1%nat; reflexivity | exists 2%nat; reflexivity | exists 3%nat; reflexivity].
  + destruct s; try solve [exists 0%nat; reflexivity | exists 1%nat; reflexivity | exists 2%nat; reflexivity | exists 3%nat; reflexivity].
  + destruct f; try solve [exists 0%nat; reflexivity | exists 1%nat; reflexivity | exists 2%nat; reflexivity | exists 3%nat; reflexivity].
  + simpl. unfold Mptr.
      destruct Archi.ptr64; [exists 3%nat | exists 2%nat]; reflexivity.
  + simpl.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
    auto.
  + exists 0%nat; reflexivity.
  + simpl.
    pose proof HA_ENV_CONS id; pose proof HA_ENV_COMPL id.
    destruct (cenv ! id) as [co |] eqn:?H, (ha_env ! id) eqn:?H.
    2: { pose proof proj1 H0 (ex_intro _ _ eq_refl) as [? ?]; congruence. }
    2: { pose proof proj2 H0 (ex_intro _ _ eq_refl) as [? ?]; congruence. }
    - specialize (H _ _ eq_refl eq_refl).
      subst z.
      clear - IH.
      induction IH.
      * exists 0%nat; reflexivity.
      * destruct x as [i t], H as [n1 ?], IHIH as [n2 ?].
        simpl in H |- *.
        rewrite H, H0.
(* Goal: @ex nat (fun n : nat => @eq Z (Z.max (two_power_nat n2) (two_power_nat n1)) (two_power_nat n)) *)
        rewrite max_two_power_nat.
(* Goal: @ex memory_chunk (fun ch : memory_chunk => @eq mode (access_mode (Tpointer t0 a)) (By_value ch)) *)
        eexists; reflexivity.
    - exists 0%nat; reflexivity.
  + simpl.
    pose proof HA_ENV_CONS id; pose proof HA_ENV_COMPL id.
    destruct (cenv ! id) as [co |] eqn:?H, (ha_env ! id) eqn:?H.
    2: { pose proof proj1 H0 (ex_intro _ _ eq_refl) as [? ?]; congruence. }
    2: { pose proof proj2 H0 (ex_intro _ _ eq_refl) as [? ?]; congruence. }
    - specialize (H _ _ eq_refl eq_refl).
      subst z.
      clear - IH.
      induction IH.
      * exists 0%nat; reflexivity.
      * destruct x as [i t], H as [n1 ?], IHIH as [n2 ?].
        simpl in H |- *.
        rewrite H, H0.
(* Goal: @ex nat (fun n : nat => @eq Z (Z.max (two_power_nat n2) (two_power_nat n1)) (two_power_nat n)) *)
        rewrite max_two_power_nat.
(* Goal: @ex memory_chunk (fun ch : memory_chunk => @eq mode (access_mode (Tpointer t0 a)) (By_value ch)) *)
        eexists; reflexivity.
    - exists 0%nat; reflexivity.
Qed.

Lemma hardware_alignof_pos: forall (cenv: composite_env) (ha_env: PTree.t Z),
  composite_env_consistent cenv ->
  hardware_alignof_env_consistent cenv ha_env ->
  hardware_alignof_env_complete cenv ha_env ->
  forall t,
  hardware_alignof ha_env t > 0.
Proof.
(* Goal: forall (t : type) (ofs : Z) (_ : @eq bool (is_aligned cenv ha_env la_env t ofs) true) (_ : @ex memory_chunk (fun ch : memory_chunk => @eq mode (access_mode t) (By_value ch))), align_compatible_rec cenv t ofs *)
  intros.
(* Goal: Z.gt (hardware_alignof ha_env t) Z0 *)
  pose proof hardware_alignof_two_p _ _ H H0 H1 t as [n ?].
(* Goal: Z.gt (hardware_alignof ha_env t) Z0 *)
  rewrite H2.
(* Goal: Z.gt (two_power_nat n) Z0 *)
  apply two_power_nat_pos.
Qed.

Lemma hardware_alignof_composite_two_p: forall (cenv: composite_env) (ha_env: PTree.t Z),
  composite_env_consistent cenv ->
  hardware_alignof_env_consistent cenv ha_env ->
  hardware_alignof_env_complete cenv ha_env ->
  forall m, exists n,
    hardware_alignof_composite ha_env m = two_power_nat n.
Proof.
(* Goal: forall (t : type) (ofs : Z) (_ : @eq bool (is_aligned cenv ha_env la_env t ofs) true) (_ : @ex memory_chunk (fun ch : memory_chunk => @eq mode (access_mode t) (By_value ch))), align_compatible_rec cenv t ofs *)
  intros.
(* Goal: @ex nat (fun n : nat => @eq Z (hardware_alignof_composite ha_env m) (two_power_nat n)) *)
  induction m as [| [i t] ?].
  + exists 0%nat.
(* Goal: @eq Z (hardware_alignof_composite ha_env (@nil (prod ident type))) (two_power_nat O) *)
    reflexivity.
  + destruct IHm as [n1 ?], (hardware_alignof_two_p _ _ H H0 H1 t) as [n2 ?].
(* Goal: @ex nat (fun n : nat => @eq Z (hardware_alignof_composite ha_env (@cons (prod ident type) (@pair ident type i t) m)) (two_power_nat n)) *)
    simpl.
(* Goal: @ex nat (fun n : nat => @eq Z (Z.max (hardware_alignof ha_env t) (hardware_alignof_composite ha_env m)) (two_power_nat n)) *)
    rewrite H2, H3.
(* Goal: @ex nat (fun n : nat => @eq Z (Z.max (two_power_nat n2) (two_power_nat n1)) (two_power_nat n)) *)
    rewrite max_two_power_nat.
(* Goal: @ex memory_chunk (fun ch : memory_chunk => @eq mode (access_mode (Tpointer t0 a)) (By_value ch)) *)
    eexists; reflexivity.
Qed.

Hint Resolve alignof_two_p: align.
Hint Resolve align_chunk_two_p: align.
Hint Extern 10 (exists n: nat, hardware_alignof _ _ = two_power_nat n) => (eapply hardware_alignof_two_p; eassumption): align.
Hint Extern 10 (exists n: nat, hardware_alignof_composite _ _ = two_power_nat n) => (eapply hardware_alignof_composite_two_p; eassumption): align.

Lemma hardware_alignof_by_value: forall ha_env t ch,
  access_mode t = By_value ch ->
  hardware_alignof ha_env t = align_chunk ch.
Proof.
(* Goal: forall (t : type) (ofs : Z) (_ : @eq bool (is_aligned cenv ha_env la_env t ofs) true) (_ : @ex memory_chunk (fun ch : memory_chunk => @eq mode (access_mode t) (By_value ch))), align_compatible_rec cenv t ofs *)
  intros.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
  destruct t as [| [| | |] [|] | [|] | [|] | | | | |]; inv H; auto.
Qed.

Lemma align_compatible_rec_hardware_alignof_divide: forall cenv ha_env t z1 z2,
  composite_env_consistent cenv ->
  composite_env_complete_legal_cosu_type cenv ->
  hardware_alignof_env_consistent cenv ha_env ->
  hardware_alignof_env_complete cenv ha_env ->
  complete_legal_cosu_type cenv t = true ->
  (hardware_alignof ha_env t | z1 - z2) ->
  (align_compatible_rec cenv t z1 <-> align_compatible_rec cenv t z2).
Proof.
(* Goal: forall (cenv : composite_env) (ha_env : PTree.t Z) (t : type) (z1 z2 : Z) (_ : composite_env_consistent cenv) (_ : composite_env_complete_legal_cosu_type cenv) (_ : hardware_alignof_env_consistent cenv ha_env) (_ : hardware_alignof_env_complete cenv ha_env) (_ : @eq bool (complete_legal_cosu_type cenv t) true) (_ : Z.divide (hardware_alignof ha_env t) (Z.sub z1 z2)), iff (align_compatible_rec cenv t z1) (align_compatible_rec cenv t z2) *)
  intros ? ? ? ? ? CENV_CONS CENV_COSU HA_ENV_CONS HA_ENV_COMPL.
(* Goal: forall (_ : @eq bool (complete_legal_cosu_type cenv t) true) (_ : Z.divide (hardware_alignof ha_env t) (Z.sub z1 z2)), iff (align_compatible_rec cenv t z1) (align_compatible_rec cenv t z2) *)
  revert t z1 z2.
  assert (BY_VALUE: forall t z1 z2, (exists ch, access_mode t = By_value ch) -> (hardware_alignof ha_env t | z1 - z2) -> align_compatible_rec cenv t z1 <-> align_compatible_rec cenv t z2).
(* Goal: @eq bool (Z.leb (hardware_alignof ha_env t) (alignof cenv t)) true *)
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
  {
(* Goal: forall (t : type) (z1 z2 : Z) (_ : @ex memory_chunk (fun ch : memory_chunk => @eq mode (access_mode t) (By_value ch))) (_ : Z.divide (hardware_alignof ha_env t) (Z.sub z1 z2)), iff (align_compatible_rec cenv t z1) (align_compatible_rec cenv t z2) *)
    intros ? ? ? [? ?] ?.
(* Goal: forall (t : type) (ofs : Z) (_ : @eq bool (is_aligned cenv ha_env la_env t ofs) true) (_ : @ex memory_chunk (fun ch : memory_chunk => @eq mode (access_mode t) (By_value ch))), align_compatible_rec cenv t ofs *)
    split; intros.
    + eapply align_compatible_rec_by_value_inv in H1; eauto.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
      eapply align_compatible_rec_by_value; eauto.
      replace z2 with (z1 - (z1 - z2)) by omega.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
      erewrite hardware_alignof_by_value in H0 by eauto.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
      apply Z.divide_sub_r; auto.
    + eapply align_compatible_rec_by_value_inv in H1; eauto.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
      eapply align_compatible_rec_by_value; eauto.
      replace z1 with (z2 + (z1 - z2)) by omega.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
      erewrite hardware_alignof_by_value in H0 by eauto.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
      apply Z.divide_add_r; auto.
  } 
(* Goal: forall (t : type) (ofs : Z) (_ : @eq bool (is_aligned cenv ha_env la_env t ofs) true) (_ : @ex memory_chunk (fun ch : memory_chunk => @eq mode (access_mode t) (By_value ch))), align_compatible_rec cenv t ofs *)
  intro t; type_induction t cenv CENV_CONS; intros.
  + split; intros; inv H1; inv H2.
  + eapply BY_VALUE; auto.
(* Goal: @ex memory_chunk (fun ch : memory_chunk => @eq mode (access_mode (Tpointer t0 a)) (By_value ch)) *)
    destruct s, i; eexists; reflexivity.
  + eapply BY_VALUE; auto.
(* Goal: @ex memory_chunk (fun ch : memory_chunk => @eq mode (access_mode (Tpointer t0 a)) (By_value ch)) *)
    destruct s; eexists; reflexivity.
  + eapply BY_VALUE; auto.
(* Goal: @ex memory_chunk (fun ch : memory_chunk => @eq mode (access_mode (Tpointer t0 a)) (By_value ch)) *)
    destruct f; eexists; reflexivity.
  + eapply BY_VALUE; auto.
(* Goal: @ex memory_chunk (fun ch : memory_chunk => @eq mode (access_mode (Tpointer t0 a)) (By_value ch)) *)
    eexists; reflexivity.
  + simpl in H0.
    split; intros; apply align_compatible_rec_Tarray; intros;
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
    eapply align_compatible_rec_Tarray_inv in H1; eauto.
    - specialize (IH (z1 + sizeof cenv t0 * i) (z2 + sizeof cenv t0 * i)).
      replace (z1 + sizeof cenv t0 * i - (z2 + sizeof cenv t0 * i)) with (z1 - z2) in IH by omega.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
      tauto.
    - specialize (IH (z1 + sizeof cenv t0 * i) (z2 + sizeof cenv t0 * i)).
      replace (z1 + sizeof cenv t0 * i - (z2 + sizeof cenv t0 * i)) with (z1 - z2) in IH by omega.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
      tauto.
  + split; intros; inv H1; inv H2; econstructor.
  + simpl in H, H0.
(* Goal: align_compatible_rec cenv (Tunion id a) z *)
    destruct (cenv ! id) as [co |] eqn:?H; [| inv H].
(* Goal: align_compatible_rec cenv t0 z *)
    destruct (co_su co) eqn:?H; inv H.
    assert (forall i0 t0 ofs0,
              field_type i0 (co_members co) = Errors.OK t0 ->
              field_offset cenv i0 (co_members co) = Errors.OK ofs0 ->
              (align_compatible_rec cenv t0 (z1 + ofs0) <->
               align_compatible_rec cenv t0 (z2 + ofs0))) as HH;
    [ | split; intros; eapply align_compatible_rec_Tstruct; eauto;
        intros; eapply align_compatible_rec_Tstruct_inv in H; eauto;
        eapply HH; eauto].
(* Goal: align_compatible_rec cenv (Tunion id a) z *)
    pose proof proj1 (HA_ENV_COMPL id) (ex_intro _ co H1) as [ha ?].
(* Goal: align_compatible_rec cenv (Tunion id a) z *)
    rewrite H in H0.
(* Goal: align_compatible_rec cenv (Tunion id a) z *)
    pose proof HA_ENV_CONS _ _ _ H1 H.
(* Goal: align_compatible_rec cenv (Tunion id a) z *)
    rewrite H3 in H0.
(* Goal: align_compatible_rec cenv (Tunion id a) z *)
    pose proof CENV_COSU _ _ H1.
(* Goal: forall (i0 : ident) (t0 : type) (_ : @eq (Errors.res type) (field_type i0 (co_members co)) (@Errors.OK type t0)), align_compatible_rec cenv t0 z *)
    clear H H1 H2 H3 ha.
(* Goal: forall (t : type) (ofs : Z) (_ : @eq bool (is_aligned cenv ha_env la_env t ofs) true) (_ : @ex memory_chunk (fun ch : memory_chunk => @eq mode (access_mode t) (By_value ch))), align_compatible_rec cenv t ofs *)
    intros. clear H1.
(* Goal: align_compatible_rec cenv t0 z *)
    induction IH as [| [i t] ?].
(* Goal: align_compatible_rec cenv t0 z *)
    - inv H.
    - simpl in H, H0, H4.
(* Goal: align_compatible_rec cenv t0 z *)
      autorewrite with align in H0, H4.
(* Goal: align_compatible_rec cenv t0 z *)
      if_tac in H.
(* Goal: align_compatible_rec cenv t0 z *)
      * subst i; inv H.
(* Goal: iff (align_compatible_rec cenv t0 (Z.add z1 ofs0)) (align_compatible_rec cenv t0 (Z.add z2 ofs0)) *)
        apply H1; [simpl; tauto |].
        replace (z1 + ofs0 - (z2 + ofs0)) with (z1 - z2) by omega; tauto.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
      * apply IHIH; tauto.
  + simpl in H, H0.
(* Goal: align_compatible_rec cenv (Tunion id a) z *)
    destruct (cenv ! id) as [co |] eqn:?H; [| inv H].
(* Goal: align_compatible_rec cenv t0 z *)
    destruct (co_su co) eqn:?H; inv H.
    assert (forall i0 t0,
              field_type i0 (co_members co) = Errors.OK t0 ->
              (align_compatible_rec cenv t0 z1 <->
               align_compatible_rec cenv t0 z2)) as HH;
    [ | split; intros; eapply align_compatible_rec_Tunion; eauto;
        intros; eapply align_compatible_rec_Tunion_inv in H; eauto;
        eapply HH; eauto].
(* Goal: align_compatible_rec cenv (Tunion id a) z *)
    pose proof proj1 (HA_ENV_COMPL id) (ex_intro _ co H1) as [ha ?].
(* Goal: align_compatible_rec cenv (Tunion id a) z *)
    rewrite H in H0.
(* Goal: align_compatible_rec cenv (Tunion id a) z *)
    pose proof HA_ENV_CONS _ _ _ H1 H.
(* Goal: align_compatible_rec cenv (Tunion id a) z *)
    rewrite H3 in H0.
(* Goal: align_compatible_rec cenv (Tunion id a) z *)
    pose proof CENV_COSU _ _ H1.
(* Goal: forall (i0 : ident) (t0 : type) (_ : @eq (Errors.res type) (field_type i0 (co_members co)) (@Errors.OK type t0)), align_compatible_rec cenv t0 z *)
    clear H H1 H2 H3 ha.
(* Goal: forall (t : type) (ofs : Z) (_ : @eq bool (is_aligned cenv ha_env la_env t ofs) true) (_ : @ex memory_chunk (fun ch : memory_chunk => @eq mode (access_mode t) (By_value ch))), align_compatible_rec cenv t ofs *)
    intros.
(* Goal: align_compatible_rec cenv t0 z *)
    induction IH as [| [i t] ?].
(* Goal: align_compatible_rec cenv t0 z *)
    - inv H.
    - simpl in H, H0, H4.
(* Goal: align_compatible_rec cenv t0 z *)
      autorewrite with align in H0, H4.
(* Goal: align_compatible_rec cenv t0 z *)
      if_tac in H.
(* Goal: align_compatible_rec cenv t0 z *)
      * subst i; inv H.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
        apply H1; simpl; tauto.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
      * apply IHIH; tauto.
Qed.

Lemma align_compatible_rec_hardware_1: forall cenv ha_env t z,
  composite_env_consistent cenv ->
  composite_env_complete_legal_cosu_type cenv ->
  hardware_alignof_env_consistent cenv ha_env ->
  hardware_alignof_env_complete cenv ha_env ->
  complete_legal_cosu_type cenv t = true ->
  hardware_alignof ha_env t = 1 ->
  align_compatible_rec cenv t z.
Proof.
(* Goal: forall (cenv : composite_env) (ha_env : PTree.t Z) (t : type) (z : Z) (_ : composite_env_consistent cenv) (_ : composite_env_complete_legal_cosu_type cenv) (_ : hardware_alignof_env_consistent cenv ha_env) (_ : hardware_alignof_env_complete cenv ha_env) (_ : @eq bool (complete_legal_cosu_type cenv t) true) (_ : @eq Z (hardware_alignof ha_env t) (Zpos xH)), align_compatible_rec cenv t z *)
  intros ? ? ? ? CENV_CONS CENV_COSU HA_ENV_CONS HA_ENV_COMPL.
(* Goal: forall (t : type) (ofs : Z) (_ : @eq bool (is_aligned cenv ha_env la_env t ofs) true) (_ : @ex memory_chunk (fun ch : memory_chunk => @eq mode (access_mode t) (By_value ch))), align_compatible_rec cenv t ofs *)
  revert z; type_induction t cenv CENV_CONS; intros.
  + inv H.
  + destruct s, i; inv H0;
    econstructor; try reflexivity; apply Z.divide_1_l.
(* Goal: align_compatible_rec cenv (Tpointer t a) z *)
  + destruct s; inv H0.
(* Goal: align_compatible_rec cenv (Tpointer t a) z *)
  + destruct f; inv H0.
(* Goal: align_compatible_rec cenv (Tpointer t a) z *)
  + inv H0.
  + apply align_compatible_rec_Tarray.
(* Goal: forall (t : type) (ofs : Z) (_ : @eq bool (is_aligned cenv ha_env la_env t ofs) true) (_ : @ex memory_chunk (fun ch : memory_chunk => @eq mode (access_mode t) (By_value ch))), align_compatible_rec cenv t ofs *)
    intros.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
    apply IH; auto.
  + inv H.
  + simpl in H, H0.
(* Goal: align_compatible_rec cenv (Tunion id a) z *)
    destruct (cenv ! id) as [co |] eqn:?H; [| inv H].
(* Goal: align_compatible_rec cenv t0 z *)
    destruct (co_su co) eqn:?H; inv H.
(* Goal: align_compatible_rec cenv (Tunion id a) z *)
    pose proof proj1 (HA_ENV_COMPL id) (ex_intro _ co H1) as [ha ?].
(* Goal: align_compatible_rec cenv (Tunion id a) z *)
    rewrite H in H0.
(* Goal: align_compatible_rec cenv (Tunion id a) z *)
    pose proof HA_ENV_CONS _ _ _ H1 H.
(* Goal: align_compatible_rec cenv (Tunion id a) z *)
    rewrite H3 in H0.
(* Goal: align_compatible_rec cenv (Tunion id a) z *)
    pose proof CENV_COSU _ _ H1.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
    eapply align_compatible_rec_Tstruct; eauto.
(* Goal: forall (i0 : ident) (t0 : type) (_ : @eq (Errors.res type) (field_type i0 (co_members co)) (@Errors.OK type t0)), align_compatible_rec cenv t0 z *)
    clear H H1 H2 H3 ha.
(* Goal: iff (align_compatible_rec cenv t0 (Z.add z1 ofs0)) (align_compatible_rec cenv t0 (Z.add z2 ofs0)) *)
    intros; clear H1.
(* Goal: align_compatible_rec cenv t0 z *)
    induction IH as [| [i t] ?].
(* Goal: align_compatible_rec cenv t0 z *)
    - inv H.
    - simpl in H, H0, H4.
(* Goal: align_compatible_rec cenv t0 z *)
      autorewrite with align in H0, H4.
(* Goal: align_compatible_rec cenv t0 z *)
      destruct H0, H4.
(* Goal: align_compatible_rec cenv t0 z *)
      if_tac in H.
(* Goal: align_compatible_rec cenv t0 z *)
      * subst i; inv H.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
        apply H1; auto.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
      * apply IHIH; auto.
  + simpl in H, H0.
(* Goal: align_compatible_rec cenv (Tunion id a) z *)
    destruct (cenv ! id) as [co |] eqn:?H; [| inv H].
(* Goal: align_compatible_rec cenv t0 z *)
    destruct (co_su co) eqn:?H; inv H.
(* Goal: align_compatible_rec cenv (Tunion id a) z *)
    pose proof proj1 (HA_ENV_COMPL id) (ex_intro _ co H1) as [ha ?].
(* Goal: align_compatible_rec cenv (Tunion id a) z *)
    rewrite H in H0.
(* Goal: align_compatible_rec cenv (Tunion id a) z *)
    pose proof HA_ENV_CONS _ _ _ H1 H.
(* Goal: align_compatible_rec cenv (Tunion id a) z *)
    rewrite H3 in H0.
(* Goal: align_compatible_rec cenv (Tunion id a) z *)
    pose proof CENV_COSU _ _ H1.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
    eapply align_compatible_rec_Tunion; eauto.
(* Goal: forall (i0 : ident) (t0 : type) (_ : @eq (Errors.res type) (field_type i0 (co_members co)) (@Errors.OK type t0)), align_compatible_rec cenv t0 z *)
    clear H H1 H2 H3 ha.
(* Goal: forall (t : type) (ofs : Z) (_ : @eq bool (is_aligned cenv ha_env la_env t ofs) true) (_ : @ex memory_chunk (fun ch : memory_chunk => @eq mode (access_mode t) (By_value ch))), align_compatible_rec cenv t ofs *)
    intros.
(* Goal: align_compatible_rec cenv t0 z *)
    induction IH as [| [i t] ?].
(* Goal: align_compatible_rec cenv t0 z *)
    - inv H.
    - simpl in H, H0, H4.
(* Goal: align_compatible_rec cenv t0 z *)
      autorewrite with align in H0, H4.
(* Goal: align_compatible_rec cenv t0 z *)
      destruct H0, H4.
(* Goal: align_compatible_rec cenv t0 z *)
      if_tac in H.
(* Goal: align_compatible_rec cenv t0 z *)
      * subst i; inv H.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
        apply H1; auto.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
      * apply IHIH; auto.
Qed.

Module Type LEGAL_ALIGNAS.

  Parameter legal_alignas_obs: Type.
  Parameter legal_alignas_type: composite_env -> PTree.t Z -> PTree.t legal_alignas_obs -> type -> legal_alignas_obs.
  Parameter legal_alignas_composite: composite_env -> PTree.t Z -> PTree.t legal_alignas_obs -> composite -> legal_alignas_obs.
  Parameter legal_alignas_env: composite_env -> PTree.t Z -> PTree.t legal_alignas_obs.
  Parameter is_aligned_aux: legal_alignas_obs -> Z -> Z -> bool.  

End LEGAL_ALIGNAS.

Module LegalAlignasDefsGen (LegalAlignas: LEGAL_ALIGNAS).

  Import LegalAlignas.

  Definition legal_alignas_env_consistent (cenv: composite_env) (ha_env: PTree.t Z) (la_env: PTree.t legal_alignas_obs): Prop :=
    forall i co la,
      cenv ! i = Some co ->
      la_env ! i = Some la ->
      la = legal_alignas_composite cenv ha_env la_env co.

  Definition legal_alignas_env_complete (cenv: composite_env) (la_env: PTree.t legal_alignas_obs): Prop :=
    forall i,
      (exists co, cenv ! i = Some co) <->
      (exists la, la_env ! i = Some la).

  Definition is_aligned cenv ha_env la_env (t: type) (ofs: Z): bool := is_aligned_aux (legal_alignas_type cenv ha_env la_env t) (hardware_alignof ha_env t) ofs.

  Definition legal_alignas_env_sound (cenv: composite_env) (ha_env: PTree.t Z) (la_env: PTree.t legal_alignas_obs): Prop :=
    forall ofs t,
      complete_legal_cosu_type cenv t = true ->
      is_aligned cenv ha_env la_env t ofs = true ->
      align_compatible_rec cenv t ofs.

End LegalAlignasDefsGen.

Module Type LEGAL_ALIGNAS_FACTS.

  Declare Module LegalAlignas: LEGAL_ALIGNAS.
  Module LegalAlignasDefs := LegalAlignasDefsGen (LegalAlignas).
  Export LegalAlignas LegalAlignasDefs.

  Axiom legal_alignas_env_consistency: forall cenv ha_env,
    composite_env_consistent cenv ->
    legal_alignas_env_consistent cenv ha_env (legal_alignas_env cenv ha_env).

  Axiom legal_alignas_env_completeness: forall cenv ha_env,
    legal_alignas_env_complete cenv (legal_alignas_env cenv ha_env).

  Axiom legal_alignas_soundness: forall cenv ha_env la_env,
    composite_env_consistent cenv ->
    composite_env_complete_legal_cosu_type cenv ->
    hardware_alignof_env_consistent cenv ha_env ->
    hardware_alignof_env_complete cenv ha_env ->
    legal_alignas_env_consistent cenv ha_env la_env ->
    legal_alignas_env_complete cenv la_env ->
    legal_alignas_env_sound cenv ha_env la_env.

End LEGAL_ALIGNAS_FACTS.

Module LegalAlignasStrict <: LEGAL_ALIGNAS.

Section legal_alignas.

Context (cenv: composite_env) (ha_env: PTree.t Z).

Definition legal_alignas_obs: Type := bool.

Fixpoint legal_alignas_type (la_env: PTree.t bool) t: bool :=
  (hardware_alignof ha_env t <=? alignof cenv t) &&
  match t with
  | Tarray t' _ _ => (sizeof cenv t' mod alignof cenv t' =? 0) && legal_alignas_type la_env t'
  | Tstruct id _ =>
      match la_env ! id with
      | Some la => la
      | None => false
      end
  | Tunion id _ =>
      match la_env ! id with
      | Some la => la
      | None => false
      end
  | _ => match access_mode t with
         | By_value ch => true
         | _ => false
         end
  end.

Fixpoint legal_alignas_members (la_env: PTree.t bool) (m: members): bool :=
  match m with
  | nil => true
  | (_, t) :: m' => (legal_alignas_type la_env t) && (legal_alignas_members la_env m')
  end.

Definition legal_alignas_composite (la_env: PTree.t bool) (co: composite): bool :=
  legal_alignas_members la_env (co_members co).

Definition legal_alignas_env: PTree.t bool :=
  let l := composite_reorder.rebuild_composite_elements cenv in
  fold_right (fun (ic: positive * composite) (T0: PTree.t bool) => let (i, co) := ic in let T := T0 in PTree.set i (legal_alignas_composite T co) T) (PTree.empty _) l.

Definition is_aligned_aux (b: bool) (ha: Z) (ofs: Z) := b && ((ofs mod ha) =? 0).

End legal_alignas.

End LegalAlignasStrict.

Module LegalAlignasStrictFacts: LEGAL_ALIGNAS_FACTS with Module LegalAlignas := LegalAlignasStrict.

Module LegalAlignas := LegalAlignasStrict.
Module LegalAlignasDefs := LegalAlignasDefsGen (LegalAlignas).
Export LegalAlignas LegalAlignasDefs.

Section legal_alignas.

Context (cenv: composite_env) (ha_env: PTree.t Z).

Lemma aux1: forall T co,
      (fix fm (l : list (ident * type * bool)) : bool :=
          match l with
          | nil => true
          | (_, _, la) :: l' => la && fm l'
          end)
         (map
            (fun it0 : positive * type =>
             let (i0, t0) := it0 in
             (i0, t0,
             type_func.F
               (fun t : type =>
                (hardware_alignof ha_env t <=? alignof cenv t) &&
                match access_mode t with
                | By_value _ => true
                | By_reference => false
                | By_copy => false
                | By_nothing => false
                end)
               (fun (la : bool) (t : type) (n : Z) (a0 : attr) =>
                (hardware_alignof ha_env (Tarray t n a0) <=? alignof cenv (Tarray t n a0)) && ((sizeof cenv t mod alignof cenv t =? 0) && la))
               (fun (la : bool) (id : ident) (a0 : attr) =>
                (hardware_alignof ha_env (Tstruct id a0) <=? alignof cenv (Tstruct id a0)) && la)
               (fun (la : bool) (id : ident) (a0 : attr) =>
                (hardware_alignof ha_env (Tunion id a0) <=? alignof cenv (Tunion id a0)) && la) T t0)) (co_members co)) =
      legal_alignas_composite cenv ha_env T co.
Proof.
  intros; unfold legal_alignas_composite, legal_alignas_members, legal_alignas_type.
(* Goal: @eq Z ((fix fm (l : list (prod (prod ident type) Z)) : Z := match l with | nil => Zpos xH | cons (pair (pair i t as p0) ha as p) l' => Z.max ha (fm l') end) (@map (prod positive type) (prod (prod positive type) Z) (fun it0 : prod positive type => let (i0, t0) := it0 in @pair (prod positive type) Z (@pair positive type i0 t0) (@type_func.F Z (fun t : type => match access_mode t with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end) (fun (ha : Z) (_ : type) (_ : Z) (_ : attr) => ha) (fun (ha : Z) (_ : ident) (_ : attr) => ha) (fun (ha : Z) (_ : ident) (_ : attr) => ha) T t0)) (co_members co))) ((fix hardware_alignof_composite (ha_env : PTree.t Z) (m : members) {struct m} : Z := match m with | nil => Zpos xH | cons (pair i t as p) m' => Z.max ((fix hardware_alignof (ha_env0 : PTree.t Z) (t0 : type) {struct t0} : Z := match t0 with | Tvoid => match access_mode t0 with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end | Tint i0 s a => match access_mode t0 with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end | Tlong s a => match access_mode t0 with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end | Tfloat f a => match access_mode t0 with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end | Tpointer t1 a => match access_mode t0 with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end | Tarray t' z a => hardware_alignof ha_env0 t' | Tfunction t1 t2 c => match access_mode t0 with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end | Tstruct id a => match @PTree.get Z id ha_env0 with | Some ha => ha | None => Zpos xH end | Tunion id a => match @PTree.get Z id ha_env0 with | Some ha => ha | None => Zpos xH end end) ha_env t) (hardware_alignof_composite ha_env m') end) T (co_members co)) *)
  induction (co_members co) as [| [i t] ?].
  + auto.
  + simpl.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
    f_equal; auto.
(* Goal: @eq Z (@type_func.F Z (fun t : type => match access_mode t with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end) (fun (ha : Z) (_ : type) (_ : Z) (_ : attr) => ha) (fun (ha : Z) (_ : ident) (_ : attr) => ha) (fun (ha : Z) (_ : ident) (_ : attr) => ha) T t) ((fix hardware_alignof (ha_env : PTree.t Z) (t : type) {struct t} : Z := match t with | Tvoid => match access_mode t with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end | Tint i s a => match access_mode t with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end | Tlong s a => match access_mode t with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end | Tfloat f a => match access_mode t with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end | Tpointer t0 a => match access_mode t with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end | Tarray t' z a => hardware_alignof ha_env t' | Tfunction t0 t1 c => match access_mode t with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end | Tstruct id a => match @PTree.get Z id ha_env with | Some ha => ha | None => Zpos xH end | Tunion id a => match @PTree.get Z id ha_env with | Some ha => ha | None => Zpos xH end end) T t) *)
    clear.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
    induction t; auto.
(* Goal: @ex nat (fun n : nat => @eq Z (hardware_alignof_composite ha_env (@cons (prod ident type) (@pair ident type i t) m)) (two_power_nat n)) *)
    - simpl.
      rewrite IHt.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
      auto.
(* Goal: @ex nat (fun n : nat => @eq Z (hardware_alignof_composite ha_env (@cons (prod ident type) (@pair ident type i t) m)) (two_power_nat n)) *)
    - simpl.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
      destruct (T ! i); auto.
(* Goal: @ex nat (fun n : nat => @eq Z (hardware_alignof_composite ha_env (@cons (prod ident type) (@pair ident type i t) m)) (two_power_nat n)) *)
    - simpl.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
      destruct (T ! i); auto.
Qed.

Lemma aux2:
    (type_func.Env
          (fun t : type =>
           (hardware_alignof ha_env t <=? alignof cenv t) &&
           match access_mode t with
           | By_value _ => true
           | By_reference => false
           | By_copy => false
           | By_nothing => false
           end)
          (fun (la : bool) (t : type) (n : Z) (a0 : attr) =>
           (hardware_alignof ha_env (Tarray t n a0) <=? alignof cenv (Tarray t n a0)) && ((sizeof cenv t mod alignof cenv t =? 0) && la))
          (fun (la : bool) (id : ident) (a0 : attr) =>
           (hardware_alignof ha_env (Tstruct id a0) <=? alignof cenv (Tstruct id a0)) && la)
          (fun (la : bool) (id : ident) (a0 : attr) =>
           (hardware_alignof ha_env (Tunion id a0) <=? alignof cenv (Tunion id a0)) && la)
          (fun _ : struct_or_union =>
           fix fm (l : list (ident * type * bool)) : bool :=
             match l with
             | nil => true
             | (_, _, la) :: l' => la && fm l'
             end) (composite_reorder.rebuild_composite_elements cenv)) =
    legal_alignas_env cenv ha_env.
Proof.
(* Goal: forall (t : type) (ofs : Z) (_ : @eq bool (is_aligned cenv ha_env la_env t ofs) true) (_ : @ex memory_chunk (fun ch : memory_chunk => @eq mode (access_mode t) (By_value ch))), align_compatible_rec cenv t ofs *)
  intros.
  unfold type_func.Env, type_func.env_rec, legal_alignas_env.
(* Goal: @eq (PTree.t Z) (@PTree.set Z i ((fix fm (l : list (prod (prod ident type) Z)) : Z := match l with | nil => Zpos xH | cons (pair (pair i t as p0) ha as p) l' => Z.max ha (fm l') end) (@map (prod positive type) (prod (prod positive type) Z) (fun it0 : prod positive type => let (i0, t0) := it0 in @pair (prod positive type) Z (@pair positive type i0 t0) (@type_func.F Z (fun t : type => match access_mode t with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end) (fun (ha : Z) (_ : type) (_ : Z) (_ : attr) => ha) (fun (ha : Z) (_ : ident) (_ : attr) => ha) (fun (ha : Z) (_ : ident) (_ : attr) => ha) T t0)) (co_members co))) T) (@PTree.set Z i (hardware_alignof_composite T (co_members co)) T) *)
  f_equal.
(* Goal: @eq (forall (_ : prod positive composite) (_ : PTree.t Z), PTree.t Z) (fun ic : prod positive composite => let (i, co) := ic in fun env : PTree.t Z => @PTree.set Z i ((fix fm (l : list (prod (prod ident type) Z)) : Z := match l with | nil => Zpos xH | cons (pair (pair i0 t as p0) ha as p) l' => Z.max ha (fm l') end) (@map (prod positive type) (prod (prod positive type) Z) (fun it0 : prod positive type => let (i0, t0) := it0 in @pair (prod positive type) Z (@pair positive type i0 t0) (@type_func.F Z (fun t : type => match access_mode t with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end) (fun (ha : Z) (_ : type) (_ : Z) (_ : attr) => ha) (fun (ha : Z) (_ : ident) (_ : attr) => ha) (fun (ha : Z) (_ : ident) (_ : attr) => ha) env t0)) (co_members co))) env) (fun (ic : prod positive composite) (T0 : PTree.t Z) => let (i, co) := ic in @PTree.set Z i (hardware_alignof_composite T0 (co_members co)) T0) *)
  extensionality ic.
(* Goal: @eq (forall _ : PTree.t Z, PTree.t Z) (let (i, co) := ic in fun env : PTree.t Z => @PTree.set Z i ((fix fm (l : list (prod (prod ident type) Z)) : Z := match l with | nil => Zpos xH | cons (pair (pair i0 t as p0) ha as p) l' => Z.max ha (fm l') end) (@map (prod positive type) (prod (prod positive type) Z) (fun it0 : prod positive type => let (i0, t0) := it0 in @pair (prod positive type) Z (@pair positive type i0 t0) (@type_func.F Z (fun t : type => match access_mode t with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end) (fun (ha : Z) (_ : type) (_ : Z) (_ : attr) => ha) (fun (ha : Z) (_ : ident) (_ : attr) => ha) (fun (ha : Z) (_ : ident) (_ : attr) => ha) env t0)) (co_members co))) env) (fun T0 : PTree.t Z => let (i, co) := ic in @PTree.set Z i (hardware_alignof_composite T0 (co_members co)) T0) *)
  destruct ic as [i co].
(* Goal: @eq (forall _ : PTree.t Z, PTree.t Z) (fun env : PTree.t Z => @PTree.set Z i ((fix fm (l : list (prod (prod ident type) Z)) : Z := match l with | nil => Zpos xH | cons (pair (pair i t as p0) ha as p) l' => Z.max ha (fm l') end) (@map (prod positive type) (prod (prod positive type) Z) (fun it0 : prod positive type => let (i0, t0) := it0 in @pair (prod positive type) Z (@pair positive type i0 t0) (@type_func.F Z (fun t : type => match access_mode t with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end) (fun (ha : Z) (_ : type) (_ : Z) (_ : attr) => ha) (fun (ha : Z) (_ : ident) (_ : attr) => ha) (fun (ha : Z) (_ : ident) (_ : attr) => ha) env t0)) (co_members co))) env) (fun T0 : PTree.t Z => @PTree.set Z i (hardware_alignof_composite T0 (co_members co)) T0) *)
  extensionality T.
(* Goal: @eq (PTree.t Z) (@PTree.set Z i ((fix fm (l : list (prod (prod ident type) Z)) : Z := match l with | nil => Zpos xH | cons (pair (pair i t as p0) ha as p) l' => Z.max ha (fm l') end) (@map (prod positive type) (prod (prod positive type) Z) (fun it0 : prod positive type => let (i0, t0) := it0 in @pair (prod positive type) Z (@pair positive type i0 t0) (@type_func.F Z (fun t : type => match access_mode t with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end) (fun (ha : Z) (_ : type) (_ : Z) (_ : attr) => ha) (fun (ha : Z) (_ : ident) (_ : attr) => ha) (fun (ha : Z) (_ : ident) (_ : attr) => ha) T t0)) (co_members co))) T) (@PTree.set Z i (hardware_alignof_composite T (co_members co)) T) *)
  f_equal.
(* Goal: @eq Z ((fix fm (l : list (prod (prod ident type) Z)) : Z := match l with | nil => Zpos xH | cons (pair (pair i t as p0) ha as p) l' => Z.max ha (fm l') end) (@map (prod positive type) (prod (prod positive type) Z) (fun it0 : prod positive type => let (i0, t0) := it0 in @pair (prod positive type) Z (@pair positive type i0 t0) (@type_func.F Z (fun t : type => match access_mode t with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end) (fun (ha : Z) (_ : type) (_ : Z) (_ : attr) => ha) (fun (ha : Z) (_ : ident) (_ : attr) => ha) (fun (ha : Z) (_ : ident) (_ : attr) => ha) T t0)) (co_members co))) (hardware_alignof_composite T (co_members co)) *)
  apply aux1.
Qed.

End legal_alignas.

Theorem legal_alignas_env_consistency:
  forall (cenv: composite_env) (ha_env: PTree.t Z),
    composite_env_consistent cenv ->
    legal_alignas_env_consistent cenv ha_env (legal_alignas_env cenv ha_env).
Proof.
(* Goal: forall (t : type) (ofs : Z) (_ : @eq bool (is_aligned cenv ha_env la_env t ofs) true) (_ : @ex memory_chunk (fun ch : memory_chunk => @eq mode (access_mode t) (By_value ch))), align_compatible_rec cenv t ofs *)
  intros.
  pose proof @composite_reorder_consistent bool cenv
             (fun t => (hardware_alignof ha_env t <=? alignof cenv t) &&
                match access_mode t with
                | By_value _ => true
                | _ => false
                end)
             (fun la t n a => (hardware_alignof ha_env (Tarray t n a) <=? alignof cenv (Tarray t n a)) && ((sizeof cenv t mod alignof cenv t =? 0) && la))
             (fun la id a => (hardware_alignof ha_env (Tstruct id a) <=? alignof cenv (Tstruct id a)) && la)
             (fun la id a => (hardware_alignof ha_env (Tunion id a) <=? alignof cenv (Tunion id a)) && la)
             (fun _ =>
                fix fm (l: list (ident * type * bool)): bool :=
                match l with
                | nil => true
                | (_, _, la) :: l' => la && (fm l')
                end)
             H
    as HH.
(* Goal: legal_alignas_env_complete cenv (legal_alignas_env cenv ha_env) *)
  hnf in HH.
(* Goal: legal_alignas_env_complete cenv (legal_alignas_env cenv ha_env) *)
  rewrite aux2 in HH.
(* Goal: forall (t : type) (ofs : Z) (_ : @eq bool (is_aligned cenv ha_env la_env t ofs) true) (_ : @ex memory_chunk (fun ch : memory_chunk => @eq mode (access_mode t) (By_value ch))), align_compatible_rec cenv t ofs *)
  hnf; intros.
(* Goal: @eq legal_alignas_obs la (legal_alignas_composite cenv ha_env (legal_alignas_env cenv ha_env) co) *)
  specialize (HH _ _ la H0 H1).
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
  rewrite HH, aux1; auto.
Qed.

Theorem legal_alignas_env_completeness:
  forall (cenv: composite_env) (ha_env: PTree.t Z),
    legal_alignas_env_complete cenv (legal_alignas_env cenv ha_env).
Proof.
(* Goal: forall (t : type) (ofs : Z) (_ : @eq bool (is_aligned cenv ha_env la_env t ofs) true) (_ : @ex memory_chunk (fun ch : memory_chunk => @eq mode (access_mode t) (By_value ch))), align_compatible_rec cenv t ofs *)
  intros.
  pose proof @composite_reorder_complete bool cenv
             (fun t => (hardware_alignof ha_env t <=? alignof cenv t) &&
                match access_mode t with
                | By_value _ => true
                | _ => false
                end)
             (fun la t n a => (hardware_alignof ha_env (Tarray t n a) <=? alignof cenv (Tarray t n a)) && ((sizeof cenv t mod alignof cenv t =? 0) && la))
             (fun la id a => (hardware_alignof ha_env (Tstruct id a) <=? alignof cenv (Tstruct id a)) && la)
             (fun la id a => (hardware_alignof ha_env (Tunion id a) <=? alignof cenv (Tunion id a)) && la)
             (fun _ =>
                fix fm (l: list (ident * type * bool)): bool :=
                match l with
                | nil => true
                | (_, _, la) :: l' => la && (fm l')
                end)
    as HH.
(* Goal: legal_alignas_env_complete cenv (legal_alignas_env cenv ha_env) *)
  hnf in HH.
(* Goal: legal_alignas_env_complete cenv (legal_alignas_env cenv ha_env) *)
  rewrite aux2 in HH.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
  auto.
Qed.

Section soundness.

Context (cenv: composite_env)
        (ha_env: PTree.t Z)
        (la_env: PTree.t bool)
        (CENV_CONSI: composite_env_consistent cenv)
        (CENV_COSU: composite_env_complete_legal_cosu_type cenv)
        (HA_ENV_CONSI: hardware_alignof_env_consistent cenv ha_env)
        (HA_ENV_COMPL: hardware_alignof_env_complete cenv ha_env)
        (LA_ENV_CONSI: legal_alignas_env_consistent cenv ha_env la_env)
        (LA_ENV_COMPL: legal_alignas_env_complete cenv la_env).

Lemma legal_alignas_type_divide: forall t,
  legal_alignas_type cenv ha_env la_env t = true ->
  (hardware_alignof ha_env t | alignof cenv t).
Proof.
(* Goal: forall (t : type) (ofs : Z) (_ : @eq bool (is_aligned cenv ha_env la_env t ofs) true) (_ : @ex memory_chunk (fun ch : memory_chunk => @eq mode (access_mode t) (By_value ch))), align_compatible_rec cenv t ofs *)
  intros.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
  assert (hardware_alignof ha_env t <=? alignof cenv t = true).
(* Goal: @eq bool (Z.leb (hardware_alignof ha_env t) (alignof cenv t)) true *)
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
  {
    destruct t; simpl in H |- *;
    solve [inv H | rewrite andb_true_iff in H; tauto].
  }
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
  autorewrite with align in H0.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
  auto.
Qed.

Lemma by_value_sound:
  forall t ofs,
    is_aligned cenv ha_env la_env t ofs = true ->
    (exists ch, access_mode t = By_value ch) ->
    align_compatible_rec cenv t ofs.
Proof.
(* Goal: forall (t : type) (ofs : Z) (_ : @eq bool (is_aligned cenv ha_env la_env t ofs) true) (_ : @ex memory_chunk (fun ch : memory_chunk => @eq mode (access_mode t) (By_value ch))), align_compatible_rec cenv t ofs *)
  intros.
(* Goal: align_compatible_rec cenv t ofs *)
  unfold is_aligned, is_aligned_aux, legal_alignas_type, hardware_alignof in H.
(* Goal: align_compatible_rec cenv t ofs *)
  destruct H0 as [ch ?].
  assert ((align_chunk ch <=? alignof cenv t) && true && (ofs mod align_chunk ch =? 0) = true) by
    (destruct t; try solve [inversion H0]; rewrite H0 in H; auto); clear H.
(* Goal: align_compatible_rec cenv t ofs *)
  autorewrite with align in H1.
(* Goal: align_compatible_rec cenv t ofs *)
  destruct H1 as [_ ?].
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
  eapply align_compatible_rec_by_value; eauto.
Qed.

Theorem legal_alignas_soundness:
  legal_alignas_env_sound cenv ha_env la_env.
Proof.
  pose proof CENV_COSU.
  clear CENV_COSU H.
(* Goal: forall (t : type) (ofs : Z) (_ : @eq bool (is_aligned cenv ha_env la_env t ofs) true) (_ : @ex memory_chunk (fun ch : memory_chunk => @eq mode (access_mode t) (By_value ch))), align_compatible_rec cenv t ofs *)
  intros.
  hnf; intros ? ? _ ?.
(* Goal: forall (t : type) (ofs : Z) (_ : @eq bool (is_aligned cenv ha_env la_env t ofs) true) (_ : @ex memory_chunk (fun ch : memory_chunk => @eq mode (access_mode t) (By_value ch))), align_compatible_rec cenv t ofs *)
  revert ofs H; type_induction t cenv CENV_CONSI; intros.
  + inversion H.
  + eapply by_value_sound; eauto.
(* Goal: @eq Z (hardware_alignof_composite ha_env (@nil (prod ident type))) (two_power_nat O) *)
    destruct i, s; eexists; try reflexivity.
  + eapply by_value_sound; eauto.
(* Goal: @eq Z (hardware_alignof_composite ha_env (@nil (prod ident type))) (two_power_nat O) *)
    destruct s; eexists; try reflexivity.
  + eapply by_value_sound; eauto.
(* Goal: @eq Z (hardware_alignof_composite ha_env (@nil (prod ident type))) (two_power_nat O) *)
    destruct f; eexists; try reflexivity.
  + eapply by_value_sound; eauto.
(* Goal: @eq Z (hardware_alignof_composite ha_env (@nil (prod ident type))) (two_power_nat O) *)
    eexists; try reflexivity.
(* Goal: forall (t : type) (ofs : Z) (_ : @eq bool (is_aligned cenv ha_env la_env t ofs) true) (_ : @ex memory_chunk (fun ch : memory_chunk => @eq mode (access_mode t) (By_value ch))), align_compatible_rec cenv t ofs *)
  + apply align_compatible_rec_Tarray; intros.
    apply IH; clear IH.
    unfold is_aligned, is_aligned_aux in H |- *.
    Opaque alignof. simpl in H |- *. Transparent alignof.
    autorewrite with align in H |- *.
    destruct H as [[? [? ?]] ?].
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
    split; auto.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
    apply Z.divide_add_r; auto.
    apply Z.divide_mul_l.
    clear H H3.
    apply legal_alignas_type_divide in H2.
    eapply Z.divide_trans; try eassumption.
  + inv H.
  + unfold is_aligned, is_aligned_aux in H, IH.
    Opaque alignof. simpl in H, IH. Transparent alignof.
    destruct (la_env ! id) as [la |] eqn:?H.
    2: {
      rewrite (andb_comm _ false) in H.
(* Goal: align_compatible_rec cenv t0 z *)
      inv H.
    }
    pose proof proj2 (LA_ENV_COMPL id) (ex_intro _ _ H0) as [co ?].
    pose proof proj1 (HA_ENV_COMPL id) (ex_intro _ _ H1) as [ha ?].
    rewrite H1 in IH; rewrite H2 in H.
    rewrite (HA_ENV_CONSI id _ _ H1 H2) in H.
    rewrite (LA_ENV_CONSI id _ _ H1 H0) in H.
    eapply align_compatible_rec_Tstruct; [eassumption | intros].
    pose proof field_offset_aligned _ _ _ _ _ H4 H3.
    unfold field_offset in H4.
    clear H0 H1 H2 H4.
    unfold legal_alignas_composite in *.
(* Goal: align_compatible_rec cenv t0 z *)
    induction IH as [| [i t] ?].
(* Goal: align_compatible_rec t0 (Z.add z z0) *)
    - inv H3.
    - Opaque alignof. simpl in H0, H3, H. Transparent alignof.
      if_tac in H3.
(* Goal: align_compatible_rec t0 (Z.add z z0) *)
      * subst i0; inv H3.
(* Goal: @ex nat (fun n : nat => @eq Z (hardware_alignof_composite ha_env (@cons (prod ident type) (@pair ident type i t) m)) (two_power_nat n)) *)
        apply H0; simpl.
        autorewrite with align in H |- *.
        destruct H as [[_ [? ?]] [? ?]].
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
        split; auto.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
        apply Z.divide_add_r; auto.
        apply legal_alignas_type_divide in H.
        apply Z.divide_trans with (alignof cenv t0); try eassumption.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
      * apply IHIH; auto.
        autorewrite with align in H |- *.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
        split; [split |]; tauto.
  + unfold is_aligned, is_aligned_aux in H, IH.
    Opaque alignof. simpl in H, IH. Transparent alignof.
    destruct (la_env ! id) as [la |] eqn:?H.
(* Goal: @eq bool (Z.leb (hardware_alignof ha_env t) (alignof cenv t)) true *)
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
    2:{
      rewrite (andb_comm _ false) in H.
(* Goal: align_compatible_rec cenv t0 z *)
      inv H.
    }
    pose proof proj2 (LA_ENV_COMPL id) (ex_intro _ _ H0) as [co ?].
    pose proof proj1 (HA_ENV_COMPL id) (ex_intro _ _ H1) as [ha ?].
    rewrite H1 in IH; rewrite H2 in H.
    rewrite (HA_ENV_CONSI id _ _ H1 H2) in H.
    rewrite (LA_ENV_CONSI id _ _ H1 H0) in H.
    eapply align_compatible_rec_Tunion; [eassumption | intros].
    clear H0 H1 H2.
    unfold legal_alignas_composite in *.
(* Goal: align_compatible_rec cenv t0 z *)
    induction IH as [| [i t] ?].
(* Goal: align_compatible_rec t0 (Z.add z z0) *)
    - inv H3.
    - Opaque alignof. simpl in H0, H3, H. Transparent alignof.
      if_tac in H3.
(* Goal: align_compatible_rec t0 (Z.add z z0) *)
      * subst i0; inv H3.
(* Goal: @ex nat (fun n : nat => @eq Z (hardware_alignof_composite ha_env (@cons (prod ident type) (@pair ident type i t) m)) (two_power_nat n)) *)
        apply H0; simpl.
        autorewrite with align in H |- *.
        destruct H as [[_ [? ?]] [? ?]].
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
        split; auto.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
      * apply IHIH; auto.
        autorewrite with align in H |- *.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
        split; [split |]; tauto.
Qed.

End soundness.

End LegalAlignasStrictFacts.

Module LegalAlignasStrong <: LEGAL_ALIGNAS.

Section legal_alignas.

Context (cenv: composite_env) (ha_env: PTree.t Z).

Definition legal_alignas_obs: Type := bool.

Fixpoint legal_alignas_type (la_env: PTree.t bool) t: bool :=
  match t with
  | Tarray t' _ _ => (sizeof cenv t' mod hardware_alignof ha_env t' =? 0) && legal_alignas_type la_env t'
  | Tstruct id _ =>
      match la_env ! id with
      | Some la => la
      | None => false
      end
  | Tunion id _ =>
      match la_env ! id with
      | Some la => la
      | None => false
      end
  | _ => match access_mode t with
         | By_value ch => true
         | _ => false
         end
  end.

Fixpoint legal_alignas_struct_members_rec (la_env: PTree.t bool) (m: members) (pos: Z): bool :=
  match m with
  | nil => true
  | (_, t) :: m' => (align pos (alignof cenv t) mod hardware_alignof ha_env t =? 0) && (legal_alignas_type la_env t) && (legal_alignas_struct_members_rec la_env m' (align pos (alignof cenv t) + sizeof cenv t))
  end.

Fixpoint legal_alignas_union_members_rec (la_env: PTree.t bool) (m: members): bool :=
  match m with
  | nil => true
  | (_, t) :: m' => (legal_alignas_type la_env t) && (legal_alignas_union_members_rec la_env m')
  end.

Definition legal_alignas_composite (la_env: PTree.t bool) (co: composite): bool :=
  match co_su co with
  | Struct => legal_alignas_struct_members_rec la_env (co_members co) 0
  | Union => legal_alignas_union_members_rec la_env (co_members co)
  end.

Definition legal_alignas_env: PTree.t bool :=
  let l := composite_reorder.rebuild_composite_elements cenv in
  fold_right (fun (ic: positive * composite) (T0: PTree.t bool) => let (i, co) := ic in let T := T0 in PTree.set i (legal_alignas_composite T co) T) (PTree.empty _) l.

Definition is_aligned_aux (b: bool) (ha: Z) (ofs: Z) := b && ((ofs mod ha) =? 0).

End legal_alignas.

End LegalAlignasStrong.

Module LegalAlignasStrongFacts: LEGAL_ALIGNAS_FACTS with Module LegalAlignas := LegalAlignasStrong.

Module LegalAlignas := LegalAlignasStrong.
Module LegalAlignasDefs := LegalAlignasDefsGen (LegalAlignas).
Export LegalAlignas LegalAlignasDefs.

Section legal_alignas.

Context (cenv: composite_env) (ha_env: PTree.t Z).

Lemma aux1: forall T co,
  match co_su co with
  | Struct =>
      (fix fm (pos : Z) (l : list (ident * type * bool)) {struct l} : bool :=
         match l with
         | nil => true
         | (_, t, la) :: l' =>
             (align pos (alignof cenv t) mod hardware_alignof ha_env t =? 0) &&
             la && fm (align pos (alignof cenv t) + sizeof cenv t) l'
         end) 0
  | Union =>
      fix fm (l : list (ident * type * bool)) : bool :=
        match l with
        | nil => true
        | (_, _, la) :: l' => la && fm l'
        end
  end
    (map
       (fun it0 : positive * type =>
        let (i0, t0) := it0 in
        (i0, t0,
        type_func.F
          (fun t : type =>
           match access_mode t with
           | By_value _ => true
           | By_reference => false
           | By_copy => false
           | By_nothing => false
           end)
          (fun (la : bool) (t : type) (_ : Z) (_ : attr) =>
           (sizeof cenv t mod hardware_alignof ha_env t =? 0) && la)
          (fun (la : bool) (_ : ident) (_ : attr) => la)
          (fun (la : bool) (_ : ident) (_ : attr) => la) T t0)) 
       (co_members co)) = legal_alignas_composite cenv ha_env T co.
Proof.
  intros; unfold legal_alignas_composite, legal_alignas_type.
  destruct (co_su co).
(* Goal: @eq bool (Z.leb (hardware_alignof ha_env t) (alignof cenv t)) true *)
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
  {
  generalize 0 at 2 4.
(* Goal: forall (t : type) (ofs : Z) (_ : @eq bool (is_aligned cenv ha_env la_env t ofs) true) (_ : @ex memory_chunk (fun ch : memory_chunk => @eq mode (access_mode t) (By_value ch))), align_compatible_rec cenv t ofs *)
  induction (co_members co) as [| [i t] ?]; intros.
  + auto.
  + simpl.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
    f_equal; [f_equal |]; auto.
(* Goal: @eq Z (@type_func.F Z (fun t : type => match access_mode t with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end) (fun (ha : Z) (_ : type) (_ : Z) (_ : attr) => ha) (fun (ha : Z) (_ : ident) (_ : attr) => ha) (fun (ha : Z) (_ : ident) (_ : attr) => ha) T t) ((fix hardware_alignof (ha_env : PTree.t Z) (t : type) {struct t} : Z := match t with | Tvoid => match access_mode t with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end | Tint i s a => match access_mode t with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end | Tlong s a => match access_mode t with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end | Tfloat f a => match access_mode t with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end | Tpointer t0 a => match access_mode t with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end | Tarray t' z a => hardware_alignof ha_env t' | Tfunction t0 t1 c => match access_mode t with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end | Tstruct id a => match @PTree.get Z id ha_env with | Some ha => ha | None => Zpos xH end | Tunion id a => match @PTree.get Z id ha_env with | Some ha => ha | None => Zpos xH end end) T t) *)
    clear.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
    induction t; auto.
(* Goal: @ex nat (fun n : nat => @eq Z (hardware_alignof_composite ha_env (@cons (prod ident type) (@pair ident type i t) m)) (two_power_nat n)) *)
    simpl.
    rewrite IHt.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
    auto.
  }
(* Goal: @eq bool (Z.leb (hardware_alignof ha_env t) (alignof cenv t)) true *)
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
  {
(* Goal: forall (t : type) (ofs : Z) (_ : @eq bool (is_aligned cenv ha_env la_env t ofs) true) (_ : @ex memory_chunk (fun ch : memory_chunk => @eq mode (access_mode t) (By_value ch))), align_compatible_rec cenv t ofs *)
  induction (co_members co) as [| [i t] ?]; intros.
  + auto.
  + simpl.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
    f_equal; [f_equal |]; auto.
(* Goal: @eq Z (@type_func.F Z (fun t : type => match access_mode t with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end) (fun (ha : Z) (_ : type) (_ : Z) (_ : attr) => ha) (fun (ha : Z) (_ : ident) (_ : attr) => ha) (fun (ha : Z) (_ : ident) (_ : attr) => ha) T t) ((fix hardware_alignof (ha_env : PTree.t Z) (t : type) {struct t} : Z := match t with | Tvoid => match access_mode t with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end | Tint i s a => match access_mode t with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end | Tlong s a => match access_mode t with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end | Tfloat f a => match access_mode t with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end | Tpointer t0 a => match access_mode t with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end | Tarray t' z a => hardware_alignof ha_env t' | Tfunction t0 t1 c => match access_mode t with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end | Tstruct id a => match @PTree.get Z id ha_env with | Some ha => ha | None => Zpos xH end | Tunion id a => match @PTree.get Z id ha_env with | Some ha => ha | None => Zpos xH end end) T t) *)
    clear.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
    induction t; auto.
(* Goal: @ex nat (fun n : nat => @eq Z (hardware_alignof_composite ha_env (@cons (prod ident type) (@pair ident type i t) m)) (two_power_nat n)) *)
    simpl.
    rewrite IHt.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
    auto.
  }
Qed.

Lemma aux2:
    (type_func.Env
                  (fun t : type =>
                   match access_mode t with
                   | By_value _ => true
                   | By_reference => false
                   | By_copy => false
                   | By_nothing => false
                   end)
                  (fun (la : bool) (t : type) (_ : Z) (_ : attr) =>
                   (sizeof cenv t mod hardware_alignof ha_env t =? 0) && la)
                  (fun (la : bool) (_ : ident) (_ : attr) => la)
                  (fun (la : bool) (_ : ident) (_ : attr) => la)
                  (fun su : struct_or_union =>
                   match su with
                   | Struct =>
                       (fix
                        fm (pos : Z) (l : list (ident * type * bool)) {struct l} :
                          bool :=
                          match l with
                          | nil => true
                          | (_, t, la) :: l' =>
                              (align pos (alignof cenv t)
                               mod hardware_alignof ha_env t =? 0) && la &&
                              fm (align pos (alignof cenv t) + sizeof cenv t) l'
                          end) 0
                   | Union =>
                       fix fm (l : list (ident * type * bool)) : bool :=
                         match l with
                         | nil => true
                         | (_, _, la) :: l' => la && fm l'
                         end
                   end) (composite_reorder.rebuild_composite_elements cenv)) =
    legal_alignas_env cenv ha_env.
Proof.
(* Goal: forall (t : type) (ofs : Z) (_ : @eq bool (is_aligned cenv ha_env la_env t ofs) true) (_ : @ex memory_chunk (fun ch : memory_chunk => @eq mode (access_mode t) (By_value ch))), align_compatible_rec cenv t ofs *)
  intros.
  unfold type_func.Env, type_func.env_rec, legal_alignas_env.
(* Goal: @eq (PTree.t Z) (@PTree.set Z i ((fix fm (l : list (prod (prod ident type) Z)) : Z := match l with | nil => Zpos xH | cons (pair (pair i t as p0) ha as p) l' => Z.max ha (fm l') end) (@map (prod positive type) (prod (prod positive type) Z) (fun it0 : prod positive type => let (i0, t0) := it0 in @pair (prod positive type) Z (@pair positive type i0 t0) (@type_func.F Z (fun t : type => match access_mode t with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end) (fun (ha : Z) (_ : type) (_ : Z) (_ : attr) => ha) (fun (ha : Z) (_ : ident) (_ : attr) => ha) (fun (ha : Z) (_ : ident) (_ : attr) => ha) T t0)) (co_members co))) T) (@PTree.set Z i (hardware_alignof_composite T (co_members co)) T) *)
  f_equal.
(* Goal: @eq (forall (_ : prod positive composite) (_ : PTree.t Z), PTree.t Z) (fun ic : prod positive composite => let (i, co) := ic in fun env : PTree.t Z => @PTree.set Z i ((fix fm (l : list (prod (prod ident type) Z)) : Z := match l with | nil => Zpos xH | cons (pair (pair i0 t as p0) ha as p) l' => Z.max ha (fm l') end) (@map (prod positive type) (prod (prod positive type) Z) (fun it0 : prod positive type => let (i0, t0) := it0 in @pair (prod positive type) Z (@pair positive type i0 t0) (@type_func.F Z (fun t : type => match access_mode t with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end) (fun (ha : Z) (_ : type) (_ : Z) (_ : attr) => ha) (fun (ha : Z) (_ : ident) (_ : attr) => ha) (fun (ha : Z) (_ : ident) (_ : attr) => ha) env t0)) (co_members co))) env) (fun (ic : prod positive composite) (T0 : PTree.t Z) => let (i, co) := ic in @PTree.set Z i (hardware_alignof_composite T0 (co_members co)) T0) *)
  extensionality ic.
(* Goal: @eq (forall _ : PTree.t Z, PTree.t Z) (let (i, co) := ic in fun env : PTree.t Z => @PTree.set Z i ((fix fm (l : list (prod (prod ident type) Z)) : Z := match l with | nil => Zpos xH | cons (pair (pair i0 t as p0) ha as p) l' => Z.max ha (fm l') end) (@map (prod positive type) (prod (prod positive type) Z) (fun it0 : prod positive type => let (i0, t0) := it0 in @pair (prod positive type) Z (@pair positive type i0 t0) (@type_func.F Z (fun t : type => match access_mode t with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end) (fun (ha : Z) (_ : type) (_ : Z) (_ : attr) => ha) (fun (ha : Z) (_ : ident) (_ : attr) => ha) (fun (ha : Z) (_ : ident) (_ : attr) => ha) env t0)) (co_members co))) env) (fun T0 : PTree.t Z => let (i, co) := ic in @PTree.set Z i (hardware_alignof_composite T0 (co_members co)) T0) *)
  destruct ic as [i co].
(* Goal: @eq (forall _ : PTree.t Z, PTree.t Z) (fun env : PTree.t Z => @PTree.set Z i ((fix fm (l : list (prod (prod ident type) Z)) : Z := match l with | nil => Zpos xH | cons (pair (pair i t as p0) ha as p) l' => Z.max ha (fm l') end) (@map (prod positive type) (prod (prod positive type) Z) (fun it0 : prod positive type => let (i0, t0) := it0 in @pair (prod positive type) Z (@pair positive type i0 t0) (@type_func.F Z (fun t : type => match access_mode t with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end) (fun (ha : Z) (_ : type) (_ : Z) (_ : attr) => ha) (fun (ha : Z) (_ : ident) (_ : attr) => ha) (fun (ha : Z) (_ : ident) (_ : attr) => ha) env t0)) (co_members co))) env) (fun T0 : PTree.t Z => @PTree.set Z i (hardware_alignof_composite T0 (co_members co)) T0) *)
  extensionality T.
(* Goal: @eq (PTree.t Z) (@PTree.set Z i ((fix fm (l : list (prod (prod ident type) Z)) : Z := match l with | nil => Zpos xH | cons (pair (pair i t as p0) ha as p) l' => Z.max ha (fm l') end) (@map (prod positive type) (prod (prod positive type) Z) (fun it0 : prod positive type => let (i0, t0) := it0 in @pair (prod positive type) Z (@pair positive type i0 t0) (@type_func.F Z (fun t : type => match access_mode t with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end) (fun (ha : Z) (_ : type) (_ : Z) (_ : attr) => ha) (fun (ha : Z) (_ : ident) (_ : attr) => ha) (fun (ha : Z) (_ : ident) (_ : attr) => ha) T t0)) (co_members co))) T) (@PTree.set Z i (hardware_alignof_composite T (co_members co)) T) *)
  f_equal.
(* Goal: @eq Z ((fix fm (l : list (prod (prod ident type) Z)) : Z := match l with | nil => Zpos xH | cons (pair (pair i t as p0) ha as p) l' => Z.max ha (fm l') end) (@map (prod positive type) (prod (prod positive type) Z) (fun it0 : prod positive type => let (i0, t0) := it0 in @pair (prod positive type) Z (@pair positive type i0 t0) (@type_func.F Z (fun t : type => match access_mode t with | By_value ch => align_chunk ch | By_reference => Zpos xH | By_copy => Zpos xH | By_nothing => Zpos xH end) (fun (ha : Z) (_ : type) (_ : Z) (_ : attr) => ha) (fun (ha : Z) (_ : ident) (_ : attr) => ha) (fun (ha : Z) (_ : ident) (_ : attr) => ha) T t0)) (co_members co))) (hardware_alignof_composite T (co_members co)) *)
  apply aux1.
Qed.

End legal_alignas.

Theorem legal_alignas_env_consistency:
  forall (cenv: composite_env) (ha_env: PTree.t Z),
    composite_env_consistent cenv ->
    legal_alignas_env_consistent cenv ha_env (legal_alignas_env cenv ha_env).
Proof.
(* Goal: forall (t : type) (ofs : Z) (_ : @eq bool (is_aligned cenv ha_env la_env t ofs) true) (_ : @ex memory_chunk (fun ch : memory_chunk => @eq mode (access_mode t) (By_value ch))), align_compatible_rec cenv t ofs *)
  intros.
  pose proof @composite_reorder_consistent bool cenv
             (fun t =>
                match access_mode t with
                | By_value _ => true
                | _ => false
                end)
             (fun la t n a => ((sizeof cenv t mod hardware_alignof ha_env t =? 0) && la))
             (fun la id a => la)
             (fun la id a => la)
             (fun su =>
                match su with
                | Struct =>
                   (fix fm (pos: Z) (l: list (ident * type * bool)) : bool :=
                    match l with
                    | nil => true
                    | (_, t, la) :: l' => (align pos (alignof cenv t) mod hardware_alignof ha_env t =? 0) && la && (fm (align pos (alignof cenv t) + sizeof cenv t) l')
                    end) 0
                | Union =>
                   (fix fm (l: list (ident * type * bool)) : bool :=
                    match l with
                    | nil => true
                    | (_, t, la) :: l' => la && (fm l')
                    end)
                end)
             H
    as HH.
(* Goal: legal_alignas_env_complete cenv (legal_alignas_env cenv ha_env) *)
  hnf in HH.
(* Goal: legal_alignas_env_complete cenv (legal_alignas_env cenv ha_env) *)
  rewrite aux2 in HH.
(* Goal: forall (t : type) (ofs : Z) (_ : @eq bool (is_aligned cenv ha_env la_env t ofs) true) (_ : @ex memory_chunk (fun ch : memory_chunk => @eq mode (access_mode t) (By_value ch))), align_compatible_rec cenv t ofs *)
  hnf; intros.
(* Goal: @eq legal_alignas_obs la (legal_alignas_composite cenv ha_env (legal_alignas_env cenv ha_env) co) *)
  specialize (HH _ _ la H0 H1).
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
  rewrite HH, <- aux1; auto.
Qed.

Theorem legal_alignas_env_completeness:
  forall (cenv: composite_env) (ha_env: PTree.t Z),
    legal_alignas_env_complete cenv (legal_alignas_env cenv ha_env).
Proof.
(* Goal: forall (t : type) (ofs : Z) (_ : @eq bool (is_aligned cenv ha_env la_env t ofs) true) (_ : @ex memory_chunk (fun ch : memory_chunk => @eq mode (access_mode t) (By_value ch))), align_compatible_rec cenv t ofs *)
  intros.
  pose proof @composite_reorder_complete bool cenv
             (fun t =>
                match access_mode t with
                | By_value _ => true
                | _ => false
                end)
             (fun la t n a => ((sizeof cenv t mod hardware_alignof ha_env t =? 0) && la))
             (fun la id a => la)
             (fun la id a => la)
             (fun su =>
                match su with
                | Struct =>
                   (fix fm (pos: Z) (l: list (ident * type * bool)) : bool :=
                    match l with
                    | nil => true
                    | (_, t, la) :: l' => (align pos (alignof cenv t) mod hardware_alignof ha_env t =? 0) && la && (fm (align pos (alignof cenv t) + sizeof cenv t) l')
                    end) 0
                | Union =>
                   (fix fm (l: list (ident * type * bool)) : bool :=
                    match l with
                    | nil => true
                    | (_, t, la) :: l' => la && (fm l')
                    end)
                end)
    as HH.
(* Goal: legal_alignas_env_complete cenv (legal_alignas_env cenv ha_env) *)
  hnf in HH.
(* Goal: legal_alignas_env_complete cenv (legal_alignas_env cenv ha_env) *)
  rewrite aux2 in HH.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
  auto.
Qed.

Section soundness.

Context (cenv: composite_env)
        (ha_env: PTree.t Z)
        (la_env: PTree.t bool)
        (CENV_CONSI: composite_env_consistent cenv)
        (CENV_COSU: composite_env_complete_legal_cosu_type cenv)
        (HA_ENV_CONSI: hardware_alignof_env_consistent cenv ha_env)
        (HA_ENV_COMPL: hardware_alignof_env_complete cenv ha_env)
        (LA_ENV_CONSI: legal_alignas_env_consistent cenv ha_env la_env)
        (LA_ENV_COMPL: legal_alignas_env_complete cenv la_env).

Lemma by_value_sound:
  forall t ofs,
    is_aligned cenv ha_env la_env t ofs = true ->
    (exists ch, access_mode t = By_value ch) ->
    align_compatible_rec cenv t ofs.
Proof.
(* Goal: forall (t : type) (ofs : Z) (_ : @eq bool (is_aligned cenv ha_env la_env t ofs) true) (_ : @ex memory_chunk (fun ch : memory_chunk => @eq mode (access_mode t) (By_value ch))), align_compatible_rec cenv t ofs *)
  intros.
(* Goal: align_compatible_rec cenv t ofs *)
  unfold is_aligned, is_aligned_aux, legal_alignas_type, hardware_alignof in H.
(* Goal: align_compatible_rec cenv t ofs *)
  destruct H0 as [ch ?].
  assert ((ofs mod align_chunk ch =? 0) = true) by
    (destruct t; try solve [inversion H0]; rewrite H0 in H; auto); clear H.
(* Goal: align_compatible_rec cenv t ofs *)
  autorewrite with align in H1.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
  eapply align_compatible_rec_by_value; eauto.
Qed.

Theorem legal_alignas_soundness:
  legal_alignas_env_sound cenv ha_env la_env.
Proof.
(* Goal: forall (t : type) (ofs : Z) (_ : @eq bool (is_aligned cenv ha_env la_env t ofs) true) (_ : @ex memory_chunk (fun ch : memory_chunk => @eq mode (access_mode t) (By_value ch))), align_compatible_rec cenv t ofs *)
  intros.
(* Goal: forall (t : type) (ofs : Z) (_ : @eq bool (is_aligned cenv ha_env la_env t ofs) true) (_ : @ex memory_chunk (fun ch : memory_chunk => @eq mode (access_mode t) (By_value ch))), align_compatible_rec cenv t ofs *)
  hnf; intros.
(* Goal: forall (t : type) (ofs : Z) (_ : @eq bool (is_aligned cenv ha_env la_env t ofs) true) (_ : @ex memory_chunk (fun ch : memory_chunk => @eq mode (access_mode t) (By_value ch))), align_compatible_rec cenv t ofs *)
  revert ofs H H0; type_induction t cenv CENV_CONSI; intros.
  + inversion H0.
  + eapply by_value_sound; eauto.
(* Goal: @eq Z (hardware_alignof_composite ha_env (@nil (prod ident type))) (two_power_nat O) *)
    destruct i, s; eexists; try reflexivity.
  + eapply by_value_sound; eauto.
(* Goal: @eq Z (hardware_alignof_composite ha_env (@nil (prod ident type))) (two_power_nat O) *)
    destruct s; eexists; try reflexivity.
  + eapply by_value_sound; eauto.
(* Goal: @eq Z (hardware_alignof_composite ha_env (@nil (prod ident type))) (two_power_nat O) *)
    destruct f; eexists; try reflexivity.
  + eapply by_value_sound; eauto.
(* Goal: @eq Z (hardware_alignof_composite ha_env (@nil (prod ident type))) (two_power_nat O) *)
    eexists; try reflexivity.
(* Goal: forall (t : type) (ofs : Z) (_ : @eq bool (is_aligned cenv ha_env la_env t ofs) true) (_ : @ex memory_chunk (fun ch : memory_chunk => @eq mode (access_mode t) (By_value ch))), align_compatible_rec cenv t ofs *)
  + apply align_compatible_rec_Tarray; intros.
    apply IH; clear IH; [auto |].
    unfold is_aligned, is_aligned_aux in H0 |- *.
    simpl in H0 |- *.
    autorewrite with align in H0 |- *.
    destruct H0 as [[? ?] ?].
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
    split; auto.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
    apply Z.divide_add_r; auto.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
    apply Z.divide_mul_l; auto.
  + inv H.
  + unfold is_aligned, is_aligned_aux in H0, IH.
    simpl in H, H0, IH.
    destruct (la_env ! id) as [la |] eqn:?H; [| inv H0].
    pose proof proj2 (LA_ENV_COMPL id) (ex_intro _ _ H1) as [co ?].
    pose proof proj1 (HA_ENV_COMPL id) (ex_intro _ _ H2) as [ha ?].
    pose proof CENV_COSU _ _ H2.
(* Goal: align_compatible_rec cenv (Tunion id a) z *)
    rewrite H2 in IH, H; rewrite H3 in H0.
    rewrite (HA_ENV_CONSI id _ _ H2 H3) in H0.
    rewrite (LA_ENV_CONSI id _ _ H2 H1) in H0.
    autorewrite with align in H0 |- *.
    destruct H0.
    unfold legal_alignas_composite in H0.
    destruct (co_su co); [| inv H].
    eapply align_compatible_rec_Tstruct; [eassumption | intros].
    unfold field_offset in H7.
    clear H H1 H2 H3.
    revert H0 H4 H5 H6 H7; generalize 0;
(* Goal: forall (t : type) (ofs : Z) (_ : @eq bool (is_aligned cenv ha_env la_env t ofs) true) (_ : @ex memory_chunk (fun ch : memory_chunk => @eq mode (access_mode t) (By_value ch))), align_compatible_rec cenv t ofs *)
    induction IH as [| [i t] ?]; intros.
    - inv H6.
    - simpl in H, H0, H4, H5, H6, H7.
      if_tac in H6.
      * subst i0; inv H6; inv H7.
        autorewrite with align in H4, H5, H0 |- *.
        destruct H0 as [[? ?] ?], H4 as [? ?], H5 as [? ?].
        apply H; simpl; [tauto |].
        autorewrite with align.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
        split; auto.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
        apply Z.divide_add_r; auto.
      * autorewrite with align in H0, H4, H5.
        destruct H4, H5.
        apply (IHIH (align z (alignof cenv t) + sizeof cenv t)); auto.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
        tauto.
  + unfold is_aligned, is_aligned_aux in H0, IH.
    simpl in H, H0, IH.
    destruct (la_env ! id) as [la |] eqn:?H; [| inv H0].
    pose proof proj2 (LA_ENV_COMPL id) (ex_intro _ _ H1) as [co ?].
    pose proof proj1 (HA_ENV_COMPL id) (ex_intro _ _ H2) as [ha ?].
    pose proof CENV_COSU _ _ H2.
(* Goal: align_compatible_rec cenv (Tunion id a) z *)
    rewrite H2 in IH, H; rewrite H3 in H0.
    rewrite (HA_ENV_CONSI id _ _ H2 H3) in H0.
    rewrite (LA_ENV_CONSI id _ _ H2 H1) in H0.
    autorewrite with align in H0 |- *.
    destruct H0.
    unfold legal_alignas_composite in H0.
    destruct (co_su co); [inv H |].
    eapply align_compatible_rec_Tunion; [eassumption | intros].
    clear H H1 H2 H3.
    revert H0 H4 H5 H6;
(* Goal: forall (t : type) (ofs : Z) (_ : @eq bool (is_aligned cenv ha_env la_env t ofs) true) (_ : @ex memory_chunk (fun ch : memory_chunk => @eq mode (access_mode t) (By_value ch))), align_compatible_rec cenv t ofs *)
    induction IH as [| [i t] ?]; intros.
    - inv H6.
    - simpl in H, H0, H4, H5, H6.
      if_tac in H6.
      * subst i0; inv H6.
        autorewrite with align in H4, H5, H0 |- *.
        destruct H0 as [? ?], H4 as [? ?], H5 as [? ?].
        apply H; simpl; [tauto |].
        autorewrite with align.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
        split; auto.
      * autorewrite with align in H0, H4, H5.
        destruct H4, H5.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
        apply IHIH; auto.
(* Goal: Z.divide (hardware_alignof ha_env t) (alignof cenv t) *)
        tauto.
Qed.

End soundness.

End LegalAlignasStrongFacts.

Module Export LegalAlignasFacts := LegalAlignasStrongFacts.



