source: src/ASM/CostsProof.ma @ 1564

include "ASM/ASMCosts.ma".
include "ASM/WellLabeled.ma".
include "ASM/Status.ma".
include "common/StructuredTraces.ma".

(*
definition next_instruction_is_labelled ≝
  λcost_labels: BitVectorTrie Byte 16.
  λs: Status.
  let pc ≝ program_counter … (execute_1 s) in
    match lookup_opt … pc cost_labels with
    [ None ⇒ False
    | _    ⇒ True
    ].

definition current_instruction_cost ≝
  λs: Status. \snd (fetch (code_memory … s) (program_counter … s)).

definition is_call_p ≝
  λs.
  match s with
  [ ACALL _ ⇒ True
  | LCALL _ ⇒ True
  | JMP ⇒ True (* XXX: is function pointer call *)
  | _ ⇒ False
  ].

definition next_instruction ≝
  λs: Status.
  let 〈instruction, ignore, ignore〉 ≝ fetch (code_memory … s) (program_counter … s) in
    instruction.

inductive trace_ends_with_ret: Type[0] ≝
  | ends_with_ret: trace_ends_with_ret
  | doesnt_end_with_ret: trace_ends_with_ret.

definition next_instruction_is_labelled ≝
  λcost_labels: BitVectorTrie Byte 16.
  λs: Status.
  let pc ≝ program_counter … (execute 1 s) in
    match lookup_opt … pc cost_labels with
    [ None ⇒ False
    | _    ⇒ True
    ].

definition next_instruction_properly_relates_program_counters ≝
  λbefore: Status.
  λafter : Status.
  let size ≝ current_instruction_cost before in
  let pc_before ≝ program_counter … before in
  let pc_after ≝ program_counter … after in
  let sum ≝ \snd (half_add … pc_before (bitvector_of_nat … size)) in
    sum = pc_after.

definition current_instruction ≝
  λs: Status.
  let pc ≝ program_counter … s in
  \fst (\fst (fetch … (code_memory … s) pc)).

definition current_instruction_is_labelled ≝
  λcost_labels: BitVectorTrie Byte 16.
  λs: Status.
  let pc ≝ program_counter … s in
    match lookup_opt … pc cost_labels with
    [ None ⇒ False
    | _    ⇒ True
    ].

inductive trace_label_return (cost_labels: BitVectorTrie Byte 16): Status → Status → Type[0] ≝
  | tlr_base:
      ∀status_before: Status.
      ∀status_after: Status.
        trace_label_label cost_labels ends_with_ret status_before status_after →
        trace_label_return cost_labels status_before status_after
  | tlr_step:
      ∀status_initial: Status.
      ∀status_labelled: Status.
      ∀status_final: Status.
          trace_label_label cost_labels doesnt_end_with_ret status_initial status_labelled →
            trace_label_return cost_labels status_labelled status_final →
              trace_label_return cost_labels status_initial status_final
with trace_label_label: trace_ends_with_ret → Status → Status → Type[0] ≝
  | tll_base:
      ∀ends_flag: trace_ends_with_ret.
      ∀start_status: Status.
      ∀end_status: Status.
        trace_label_label_pre cost_labels ends_flag start_status end_status →
        current_instruction_is_labelled cost_labels start_status →
        trace_label_label cost_labels ends_flag start_status end_status
with trace_label_label_pre: trace_ends_with_ret → Status → Status → Type[0] ≝
  | tllp_base_not_return:
      ∀start_status: Status.
        let final_status ≝ execute 1 start_status in
        current_instruction start_status ≠ (RealInstruction … (RET [[relative]])) →
        ¬ (is_jump_p (current_instruction start_status)) →
        current_instruction_is_labelled cost_labels final_status →
          trace_label_label_pre cost_labels doesnt_end_with_ret start_status final_status
  | tllp_base_return:
      ∀start_status: Status.
        let final_status ≝ execute 1 start_status in
          current_instruction start_status = (RealInstruction … (RET [[relative]])) →
            trace_label_label_pre cost_labels ends_with_ret start_status final_status
  | tllp_base_jump:
      ∀start_status: Status.
        let final_status ≝ execute 1 start_status in
          is_jump_p (current_instruction start_status) →
            current_instruction_is_labelled cost_labels final_status →
              trace_label_label_pre cost_labels doesnt_end_with_ret start_status final_status
  | tllp_step_call:
      ∀end_flag: trace_ends_with_ret.
      ∀status_pre_fun_call: Status.
      ∀status_after_fun_call: Status.
      ∀status_final: Status.
        let status_start_fun_call ≝ execute 1 status_pre_fun_call in
          is_call_p (current_instruction status_pre_fun_call) →
          next_instruction_properly_relates_program_counters status_pre_fun_call status_after_fun_call →
          trace_label_return cost_labels status_start_fun_call status_after_fun_call →
          trace_label_label_pre cost_labels end_flag status_after_fun_call status_final →
            trace_label_label_pre cost_labels end_flag status_pre_fun_call status_final
  | tllp_step_default:
      ∀end_flag: trace_ends_with_ret.
      ∀status_pre: Status.
      ∀status_end: Status.
        let status_init ≝ execute 1 status_pre in
          trace_label_label_pre cost_labels end_flag status_init status_end →
          ¬ (is_call_p (current_instruction status_pre)) →
          ¬ (is_jump_p (current_instruction status_pre)) →
          (current_instruction status_pre) ≠ (RealInstruction … (RET [[relative]])) →
          ¬ (current_instruction_is_labelled cost_labels status_init) →
            trace_label_label_pre cost_labels end_flag status_pre status_end.
*)

(* XXX: not us
definition compute_simple_path0 (s:Status) (is_labelled s) (well_balanced s) (labelled_p p): trace_lab_ret ≝ ….

lemma simple_path_ok:
 ∀st: Status.∀H.
 let p ≝ compute_simple_path0 st H in
   ∀n.
    nth_path n p = execute n st ∧
     (execute' (path_length p) st = 〈st',τ〉 →
      τ = cost_trace p)
  ].
*)

let rec compute_max_trace_label_label_cost
  (cost_labels: BitVectorTrie costlabel 16)
   (trace_ends_flag: trace_ends_with_ret)
    (start_status: Status) (final_status: Status)
      (the_trace: trace_label_label (ASM_abstract_status cost_labels) trace_ends_flag
        start_status final_status) on the_trace: nat ≝
  match the_trace with
  [ tll_base ends_flag initial final given_trace labelled_proof ⇒
      compute_max_trace_any_label_cost … given_trace
  ]
and compute_max_trace_any_label_cost
  (cost_labels: BitVectorTrie costlabel 16)
  (trace_ends_flag: trace_ends_with_ret)
   (start_status: Status) (final_status: Status)
     (the_trace: trace_any_label (ASM_abstract_status cost_labels) trace_ends_flag start_status final_status)
       on the_trace: nat ≝
  match the_trace with
  [ tal_base_not_return the_status _ _ _ _ ⇒ current_instruction_cost the_status
  | tal_base_return the_status _ _ _ ⇒ current_instruction_cost the_status
  | tal_step_call end_flag pre_fun_call start_fun_call after_fun_call final
     _ _ _ call_trace final_trace ⇒
      let current_instruction_cost ≝ current_instruction_cost pre_fun_call in
      let call_trace_cost ≝ compute_max_trace_label_return_cost … call_trace in
      let final_trace_cost ≝ compute_max_trace_any_label_cost cost_labels end_flag … final_trace in
        call_trace_cost + current_instruction_cost + final_trace_cost
  | tal_step_default end_flag status_pre status_init status_end _ tail_trace _ _ ⇒
      let current_instruction_cost ≝ current_instruction_cost status_pre in
      let tail_trace_cost ≝
       compute_max_trace_any_label_cost cost_labels end_flag
        status_init status_end tail_trace
      in
        current_instruction_cost + tail_trace_cost
  ]
and compute_max_trace_label_return_cost
  (cost_labels: BitVectorTrie costlabel 16)
  (start_status: Status) (final_status: Status)
    (the_trace: trace_label_return (ASM_abstract_status cost_labels) start_status final_status)
      on the_trace: nat ≝
  match the_trace with
  [ tlr_base before after trace_to_lift ⇒ compute_max_trace_label_label_cost … trace_to_lift
  | tlr_step initial labelled final labelled_trace ret_trace ⇒
      let labelled_cost ≝ compute_max_trace_label_label_cost … labelled_trace in
      let return_cost ≝ compute_max_trace_label_return_cost … ret_trace in
        labelled_cost + return_cost
  ].

(*Useless now?
(* To be moved *)
lemma pred_minus_1:
  ∀m, n: nat.
  ∀proof: n < m.
    pred (m - n) = m - n - 1.
  #m #n
  cases m
  [ #proof
    cases(lt_to_not_zero … proof)
  | #m' #proof
    normalize in ⊢ (???%);
    cases n
    [ normalize //
    | #n' normalize
      cases(m' - n')
      [ %
      | #Sm_n'
        normalize //
      ]
    ]
  ]
qed.

lemma succ_m_plus_one:
  ∀m: nat.
    S m = m + 1.
 //
qed.*)

include alias "arithmetics/nat.ma".

(*Useless now?
lemma minus_m_n_minus_minus_plus_1:
  ∀m, n: nat.
  ∀proof: n < m.
    m - n = (m - n - 1) + 1.
 /3 by lt_plus_to_minus_r, plus_minus/
qed.

lemma plus_minus_rearrangement_1:
  ∀m, n, o: nat.
  ∀proof_n_m: n ≤ m.
  ∀proof_m_o: m ≤ o.
    (m - n) + (o - m) = o - n.
  #m #n #o #H1 #H2
  lapply (minus_to_plus … H1 (refl …)) #K1 >K1
  lapply (minus_to_plus … H2 (refl …)) #K2 >K2
  /2 by plus_minus/
qed.

lemma plus_minus_rearrangement_2:
  ∀m, n, o: nat. n ≤ m → o ≤ n →
    (m - n) + (n - o) = m - o.
 /2 by plus_minus_rearrangement_1/
qed.*)

(*
let rec compute_max_trace_label_label_cost_is_ok
  (cost_labels: BitVectorTrie Byte 16)
   (trace_ends_flag: trace_ends_with_ret)
    (start_status: Status) (final_status: Status)
      (the_trace: trace_label_label (ASM_abstract_status cost_labels) trace_ends_flag
        start_status final_status) on the_trace:
          compute_max_trace_label_label_cost cost_labels trace_ends_flag start_status final_status the_trace =
            (clock … final_status) - (clock … start_status) ≝ ?
and compute_max_trace_any_label_cost_is_ok
  (cost_labels: BitVectorTrie Byte 16)
  (trace_ends_flag: trace_ends_with_ret)
   (start_status: Status) (final_status: Status)
     (the_trace: trace_any_label (ASM_abstract_status cost_labels) trace_ends_flag start_status final_status)
       on the_trace:
         compute_max_trace_any_label_cost cost_labels trace_ends_flag start_status final_status the_trace =
           (clock … final_status) - (clock … start_status) ≝ ?
and compute_max_trace_label_return_cost_is_ok
  (cost_labels: BitVectorTrie Byte 16)
  (start_status: Status) (final_status: Status)
    (the_trace: trace_label_return (ASM_abstract_status cost_labels) start_status final_status)
      on the_trace:
        compute_max_trace_label_return_cost cost_labels start_status final_status the_trace =
          (clock … final_status) - (clock … start_status) ≝ ?.
  [1:
    cases the_trace
    #ends_flag #start_status #end_status #any_label_trace #is_costed
    normalize @compute_max_trace_any_label_cost_is_ok
  |2:
  |3:
    cases the_trace
    [1:
      #status_before #status_after #trace_to_lift
      normalize @compute_max_trace_label_label_cost_is_ok
    |2:
      #status_initial #status_labelled #status_final #labelled_trace #ret_trace
      normalize >compute_max_trace_label_label_cost_is_ok
      >compute_max_trace_label_return_cost_is_ok
    ]
  ].
*)

(* XXX: work below here: *)

let rec compute_paid_trace_any_label
  (cost_labels: BitVectorTrie costlabel 16)
  (trace_ends_flag: trace_ends_with_ret)
   (start_status: Status) (final_status: Status)
     (the_trace: trace_any_label (ASM_abstract_status cost_labels) trace_ends_flag start_status final_status)
       on the_trace: nat ≝
  match the_trace with
  [ tal_base_not_return the_status _ _ _ _ ⇒ current_instruction_cost the_status
  | tal_base_return the_status _ _ _ ⇒ current_instruction_cost the_status
  | tal_step_call end_flag pre_fun_call start_fun_call after_fun_call final
     _ _ _ call_trace final_trace ⇒
      let current_instruction_cost ≝ current_instruction_cost pre_fun_call in
      let final_trace_cost ≝ compute_paid_trace_any_label cost_labels end_flag … final_trace in
        current_instruction_cost + final_trace_cost
  | tal_step_default end_flag status_pre status_init status_end _ tail_trace _ _ ⇒
      let current_instruction_cost ≝ current_instruction_cost status_pre in
      let tail_trace_cost ≝
       compute_paid_trace_any_label cost_labels end_flag
        status_init status_end tail_trace
      in
        current_instruction_cost + tail_trace_cost
  ].

definition compute_paid_trace_label_label ≝
 λcost_labels: BitVectorTrie costlabel 16.
  λtrace_ends_flag: trace_ends_with_ret.
   λstart_status: Status.
    λfinal_status: Status.
     λthe_trace: trace_label_label (ASM_abstract_status cost_labels) trace_ends_flag
      start_status final_status.
  match the_trace with
  [ tll_base ends_flag initial final given_trace labelled_proof ⇒
      compute_paid_trace_any_label … given_trace
  ].

let rec compute_trace_label_label_cost_using_paid
  (cost_labels: BitVectorTrie costlabel 16)
   (trace_ends_flag: trace_ends_with_ret)
    (start_status: Status) (final_status: Status)
      (the_trace: trace_label_label (ASM_abstract_status cost_labels) trace_ends_flag
        start_status final_status) on the_trace: nat ≝
  match the_trace with
  [ tll_base ends_flag initial final given_trace labelled_proof ⇒
      compute_paid_trace_label_label cost_labels … the_trace +
      compute_trace_any_label_cost_using_paid … given_trace
  ]
and compute_trace_any_label_cost_using_paid
  (cost_labels: BitVectorTrie costlabel 16)
  (trace_ends_flag: trace_ends_with_ret)
   (start_status: Status) (final_status: Status)
     (the_trace: trace_any_label (ASM_abstract_status cost_labels) trace_ends_flag start_status final_status)
       on the_trace: nat ≝
  match the_trace with
  [ tal_base_not_return the_status _ _ _ _ ⇒ 0
  | tal_base_return the_status _ _ _ ⇒ 0
  | tal_step_call end_flag pre_fun_call start_fun_call after_fun_call final
     _ _ _ call_trace final_trace ⇒
      let call_trace_cost ≝ compute_trace_label_return_cost_using_paid … call_trace in
      let final_trace_cost ≝ compute_trace_any_label_cost_using_paid cost_labels end_flag … final_trace in
        call_trace_cost + final_trace_cost
  | tal_step_default end_flag status_pre status_init status_end _ tail_trace _ _ ⇒
     compute_trace_any_label_cost_using_paid cost_labels end_flag
      status_init status_end tail_trace
  ]
and compute_trace_label_return_cost_using_paid
  (cost_labels: BitVectorTrie costlabel 16)
  (start_status: Status) (final_status: Status)
    (the_trace: trace_label_return (ASM_abstract_status cost_labels) start_status final_status)
      on the_trace: nat ≝
  match the_trace with
  [ tlr_base before after trace_to_lift ⇒ compute_trace_label_label_cost_using_paid … trace_to_lift
  | tlr_step initial labelled final labelled_trace ret_trace ⇒
      let labelled_cost ≝ compute_trace_label_label_cost_using_paid … labelled_trace in
      let return_cost ≝ compute_trace_label_return_cost_using_paid … ret_trace in
        labelled_cost + return_cost
  ].

let rec compute_trace_label_label_cost_using_paid_ok
  (cost_labels: BitVectorTrie costlabel 16)
   (trace_ends_flag: trace_ends_with_ret)
    (start_status: Status) (final_status: Status)
      (the_trace: trace_label_label (ASM_abstract_status cost_labels) trace_ends_flag
        start_status final_status) on the_trace:
 compute_trace_label_label_cost_using_paid cost_labels … the_trace =
 compute_max_trace_label_label_cost … the_trace ≝ ?
and compute_trace_any_label_cost_using_paid_ok
  (cost_labels: BitVectorTrie costlabel 16)
  (trace_ends_flag: trace_ends_with_ret)
   (start_status: Status) (final_status: Status)
     (the_trace: trace_any_label (ASM_abstract_status cost_labels)
      trace_ends_flag start_status final_status) on the_trace:      
  compute_paid_trace_any_label cost_labels trace_ends_flag … the_trace
  +compute_trace_any_label_cost_using_paid cost_labels trace_ends_flag … the_trace
  =compute_max_trace_any_label_cost cost_labels trace_ends_flag … the_trace ≝ ?
and compute_trace_label_return_cost_using_paid_ok
  (cost_labels: BitVectorTrie costlabel 16)
  (start_status: Status) (final_status: Status)
    (the_trace: trace_label_return (ASM_abstract_status cost_labels)
     start_status final_status) on the_trace:
 compute_trace_label_return_cost_using_paid cost_labels … the_trace =
 compute_max_trace_label_return_cost cost_labels … the_trace ≝ ?.
[ cases the_trace #endsf #ss #es #tr #H normalize
  @compute_trace_any_label_cost_using_paid_ok
| cases the_trace
  [ #ss #fs #H1 #H2 #H3 whd in ⊢ (??(?%%)%); <plus_n_O %
  | #ss #fs #H1 #H2 whd in ⊢ (??(?%%)%); <plus_n_O %
  | #ef #spfc #ssfc #safc #sf #H1 #H2 #H3 #tr1 #tr2 whd in ⊢ (??(?%%)%);
    <compute_trace_any_label_cost_using_paid_ok
    <compute_trace_label_return_cost_using_paid_ok
    -compute_trace_label_label_cost_using_paid_ok
    -compute_trace_label_return_cost_using_paid_ok
    -compute_trace_any_label_cost_using_paid_ok
    >commutative_plus in ⊢ (???(?%?));
    >commutative_plus in ⊢ (??(??%)?);
    >associative_plus >associative_plus in ⊢ (???%); @eq_f2 try %
    <associative_plus <commutative_plus %
  | #ef #sp #si #se #H1 #tr #H2 #H3 whd in ⊢ (??(?%%)%); >associative_plus @eq_f2
    [ % | @compute_trace_any_label_cost_using_paid_ok ]
  ]
| cases the_trace
  [ #sb #sa #tr normalize @compute_trace_label_label_cost_using_paid_ok
  | #si #sl #sf #tr1 #tr2 normalize @eq_f2
    [ @compute_trace_label_label_cost_using_paid_ok
    | @compute_trace_label_return_cost_using_paid_ok ]]]
qed.

(*
let rec compute_paid_trace_label_return
  (cost_labels: BitVectorTrie costlabel 16)
  (start_status: Status) (final_status: Status)
    (the_trace: trace_label_return (ASM_abstract_status cost_labels) start_status final_status)
      on the_trace: nat ≝
 match the_trace with
  [ tlr_base before after trace_to_lift ⇒ compute_paid_trace_label_label … trace_to_lift
  | tlr_step initial labelled final labelled_trace ret_trace ⇒
      let labelled_cost ≝ compute_paid_trace_label_label … labelled_trace in
      let return_cost ≝ compute_paid_trace_label_return … ret_trace in
        labelled_cost + return_cost
  ].
*)

let rec compute_cost_trace_label_label
  (cost_labels: BitVectorTrie costlabel 16)
   (trace_ends_flag: trace_ends_with_ret)
    (start_status: Status) (final_status: Status)
      (the_trace: trace_label_label (ASM_abstract_status cost_labels) trace_ends_flag
        start_status final_status) on the_trace:
         list (Σk:costlabel. ∃pc. lookup_opt … pc cost_labels = Some … k) ≝
  match the_trace with
  [ tll_base ends_flag initial final given_trace labelled_proof ⇒
     let pc ≝ program_counter … initial in
     let label ≝
      match lookup_opt … pc cost_labels return λx. match x with [None ⇒ False | Some _ ⇒ True] → costlabel with
      [ None ⇒ λabs. ⊥
      | Some l ⇒ λ_. l ] labelled_proof in
     (dp … label ?)::compute_cost_trace_any_label … given_trace
  ]
and compute_cost_trace_any_label
  (cost_labels: BitVectorTrie costlabel 16)
  (trace_ends_flag: trace_ends_with_ret)
   (start_status: Status) (final_status: Status)
     (the_trace: trace_any_label (ASM_abstract_status cost_labels) trace_ends_flag start_status final_status)
       on the_trace: list (Σk:costlabel. ∃pc. lookup_opt … pc cost_labels = Some … k) ≝
  match the_trace with
  [ tal_base_not_return the_status _ _ _ _ ⇒ []
  | tal_base_return the_status _ _ _ ⇒ []
  | tal_step_call end_flag pre_fun_call start_fun_call after_fun_call final
     _ _ _ call_trace final_trace ⇒
      let call_cost_trace ≝ compute_cost_trace_label_return … call_trace in
      let final_cost_trace ≝ compute_cost_trace_any_label cost_labels end_flag … final_trace in
        call_cost_trace @ final_cost_trace
  | tal_step_default end_flag status_pre status_init status_end _ tail_trace _ _ ⇒
       compute_cost_trace_any_label cost_labels end_flag
        status_init status_end tail_trace
  ]
and compute_cost_trace_label_return
  (cost_labels: BitVectorTrie costlabel 16)
  (start_status: Status) (final_status: Status)
    (the_trace: trace_label_return (ASM_abstract_status cost_labels) start_status final_status)
      on the_trace: list (Σk:costlabel. ∃pc. lookup_opt … pc cost_labels = Some … k) ≝
  match the_trace with
  [ tlr_base before after trace_to_lift ⇒ compute_cost_trace_label_label … trace_to_lift
  | tlr_step initial labelled final labelled_trace ret_trace ⇒
      let labelled_cost ≝ compute_cost_trace_label_label … labelled_trace in
      let return_cost ≝ compute_cost_trace_label_return … ret_trace in
        labelled_cost @ return_cost
  ].
 [ %{pc} whd in match label;  generalize in match labelled_proof; whd in ⊢ (% → ?);
  cases (lookup_opt costlabel … pc cost_labels) normalize
  [ #abs cases abs | // ]
 | // ]
qed.

(* ??????????????????????? *)
axiom block_cost_static_dynamic_ok:
 ∀cost_labels: BitVectorTrie costlabel 16.
 ∀trace_ends_flag.
 ∀start_status: Status.
 ∀final_status: Status.
 ∀the_trace:
  trace_label_label (ASM_abstract_status cost_labels) trace_ends_flag
   start_status final_status.
 let mem ≝ code_memory … start_status in
 let pc ≝ program_counter … start_status in
 let program_size ≝ 2^16 in
  block_cost mem cost_labels pc program_size =
  compute_paid_trace_label_label cost_labels trace_ends_flag
   start_status final_status the_trace.

(* To be moved elsewhere*)
lemma le_S_n_m_to_le_n_m: ∀n,m. S n ≤ m → n ≤ m.
 #n #m #H change with (pred (S n) ≤ m) @(transitive_le ? (S n)) //
qed.

(* Here I would like to use arithmetics/bigops.ma, but it requires the
   function f to be total on nat, which is not the case here *)
let rec bigplus0 (b:nat) (f: ∀n:nat. n < b → nat) (n:nat) on n ≝
  match n return λn.n < b → nat with
   [ O ⇒ λ_. 0
   | S k ⇒ λH. f k ? + bigplus0 b f k ?
   ].
 @(le_S_n_m_to_le_n_m … H)
qed.

definition bigplus ≝
 λn,f.
 match n return λx. x = n → nat with
 [ O ⇒ λ_. 0
 | S m ⇒ λH. bigplus0 n f m ? ] (refl … n).
 <H % (* Automation works, but finds an ugly proof that goes in the contexts
         of later theorems *)
qed.

lemma bigplus_0: ∀n. n=0 → ∀f. bigplus n f = 0.
 #n #E >E //
qed.

lemma bigplus0_extensional:
 ∀b,f1,f2,n,K. (∀n,H. f1 n H = f2 n H) → bigplus0 b f1 n K = bigplus0 b f2 n K.
 #b #f1 #f2 #n elim n //
 #m #IH #K #ext normalize @eq_f2 [ @ext | @IH @ext ]
qed.

lemma bigplus_extensional:
 ∀b,f1,f2. (∀n,H. f1 n H = f2 n H) → bigplus b f1 = bigplus b f2.
 #b cases b // #n #f1 #f2 @bigplus0_extensional
qed.

(*CSC: !!!!!!!!!!!!!!!!!!!!!!! *)
axiom pi_f: ∀b. ∀f: ∀n. n < b → nat. ∀n. ∀p1,p2: n < b. f n p1 = f n p2.

axiom bigplus0_sum:
 ∀b1,b2. ∀f:(∀n. n < b1+b2 → nat). ∀n,K.
  bigplus0 (b1+b2) f n K =
  if ltb n b1 then
   bigplus0 b1 (λn,H. f n ?) n ?
  else
   bigplus b1 (λn,H. f n ?)  + bigplus0 b2 (λn,H. f (b1+n) ?) (n-b1) ?.
 cases daemon
qed.

lemma bigplus_sum:
 ∀b1,b2. ∀f:(∀n. n < b1+b2 → nat).
  bigplus (b1+b2) f =
  bigplus b1 (λn,H. f n ?) + bigplus b2 (λn,H. f (b1+n) ?).
 [2: normalize in H ⊢ %; >plus_n_Sm @le_plus // (*CSC: Automation is lost here*)
 |3: normalize in H ⊢ %; @(transitive_le ? b1) // (*CSC: here too*)
 | #b1 #b2 lapply (refl … (b1+b2)) cases (b1+b2) in ⊢ (??%? → ?);
   [ #E #f cut (b1=0) [//] #E1 >bigplus_0 [2://] >bigplus_0 [2://]
     cut (b2=0) // #E2 >bigplus_0 //
   | #n #E #f whd in ⊢ (??%?); >bigplus0_sum
 
  #f cases b1
   cases (b1+b2)
 ]
qed.

lemma compute_max_trace_label_return_cost_ok_with_trace:
 ∀cost_labels: BitVectorTrie costlabel 16.
 ∀cost_map: identifier_map CostTag nat.
 ∀initial,final.
 ∀trace: trace_label_return (ASM_abstract_status cost_labels) initial final.
 ∀codom_dom: (∀pc,k. lookup_opt … pc cost_labels = Some … k → present … cost_map k).
 ∀dom_codom:(∀k. ∀k_pres:present … cost_map k. ∃pc. lookup_opt … pc cost_labels = Some … k →
   block_cost (code_memory … initial) cost_labels pc 2^16 = lookup_present … k_pres).
  let ctrace ≝ compute_cost_trace_label_return … trace in
  compute_max_trace_label_return_cost … trace =
   bigplus (|ctrace|) (λi,H.lookup_present … cost_map (nth_safe ? i ctrace H) ?).
 [2: cases (nth_safe … i ctrace H) normalize #id * #id_pc #K
   lapply (codom_dom … K) #k_pres //
 | #cost_labels #costmap #initial #final #trace #codom_dom #dom_codom
   cases trace
   [ #sb #sa #tr whd in ⊢ (let ctrace ≝ % in ??%?);
   | #si #sl #sf #tr1 #tr2 whd in ⊢ (let ctrace ≝ % in ??%?);
   ]

lemma
 compute_max_trace_any_label_cost cost_label trace_ends_flag start_status
  final_status the_trace =
 

let rec compute_paid_trace_label_label_cost
  (cost_labels: BitVectorTrie Byte 16)
   (trace_ends_flag: trace_ends_with_ret)
    (start_status: Status) (final_status: Status)
      (the_trace: trace_label_label (ASM_abstract_status cost_labels) trace_ends_flag
        start_status final_status) on the_trace: nat ≝
  match the_trace with
  [ tll_base _ _ _ given_trace _ ⇒
      compute_paid_trace_any_label_cost … given_trace
  ]
and compute_paid_trace_any_label_cost
  (cost_labels: BitVectorTrie Byte 16)
  (trace_ends_flag: trace_ends_with_ret)
   (start_status: Status) (final_status: Status)
     (the_trace: trace_any_label (ASM_abstract_status cost_labels) trace_ends_flag start_status final_status)
       on the_trace: nat ≝
  match the_trace with
  [ tal_base_not_return the_status _ _ _ _ ⇒ current_instruction_cost the_status
  | tal_base_return the_status _ _ _ ⇒ current_instruction_cost the_status
  | tal_step_call end_flag pre_fun_call start_fun_call after_fun_call final
     _ _ _ call_trace final_trace ⇒
      let current_instruction_cost ≝ current_instruction_cost pre_fun_call in
      let final_trace_cost ≝ compute_paid_trace_any_label_cost cost_labels end_flag … final_trace in
        current_instruction_cost + final_trace_cost
  | tal_step_default end_flag status_pre status_init status_end _ tail_trace _ _ ⇒
      let current_instruction_cost ≝ current_instruction_cost status_pre in
      let tail_trace_cost ≝
       compute_paid_trace_any_label_cost cost_labels end_flag
        status_init status_end tail_trace
      in
        current_instruction_cost + tail_trace_cost
  ]
and compute_paid_trace_label_return_cost
  (cost_labels: BitVectorTrie Byte 16)
  (start_status: Status) (final_status: Status)
    (the_trace: trace_label_return (ASM_abstract_status cost_labels) start_status final_status)
      on the_trace: nat ≝
  match the_trace with
  [ tlr_base before after trace_to_lift ⇒ compute_paid_trace_label_label_cost … trace_to_lift
  | tlr_step initial labelled final labelled_trace ret_trace ⇒
      let labelled_cost ≝ compute_paid_trace_label_label_cost … labelled_trace in
      let return_cost ≝ compute_paid_trace_label_return_cost … ret_trace in
        labelled_cost + return_cost
  ].

let rec trace_lab_rec_cost' (p: trace_lab_ret) : nat.
 | (call b bf tr af tl) as self ⇒
    trace_lab_lab_cost_nocall self + trace_lab_ret_cost' tr +
    trace_lab_rec_cost' tl

theorem main_lemma:
 ∀p. trace_lab_rec_cost p = trace_lab_rec_cost' p.

axiom lemma1:
 ∀p: simple_path.
  traverse_cost_internal (pc (hd p)) … = trace_lab_lab_cost_nocall p.

axiom lemma2:
 ∀s,l,cost_map.
  is_labelled l s →
   traverse_cost_internal s = cost_map l. 

axiom main_statement:
 ∀s.
 ∀cost_map.
 let p ≝ compute_simple_path0 s in
 ∑ (cost_trace p) cost_map = trace_lab_rec_cost' p.

axiom main_statement:
 ∀s.
 ∀cost_map.
 let p ≝ compute_simple_path0 s in
  execute' (path_length p) s = 〈s',τ〉 →
   Timer s' - Timer s = ∑ τ cost_map.