source: src/ASM/CostsProof.ma @ 1561

Last change on this file since 1561 was 1561, checked in by sacerdot, 8 years ago

More dependent types to accomodate the statement.

File size: 25.7 KB
Line 
1include "ASM/ASMCosts.ma".
2include "ASM/WellLabeled.ma".
3include "ASM/Status.ma".
4include "common/StructuredTraces.ma".
5
6(*
7definition next_instruction_is_labelled ≝
8  λcost_labels: BitVectorTrie Byte 16.
9  λs: Status.
10  let pc ≝ program_counter … (execute_1 s) in
11    match lookup_opt … pc cost_labels with
12    [ None ⇒ False
13    | _    ⇒ True
14    ].
15
16definition current_instruction_cost ≝
17  λs: Status. \snd (fetch (code_memory … s) (program_counter … s)).
18
19definition is_call_p ≝
20  λs.
21  match s with
22  [ ACALL _ ⇒ True
23  | LCALL _ ⇒ True
24  | JMP ⇒ True (* XXX: is function pointer call *)
25  | _ ⇒ False
26  ].
27
28definition next_instruction ≝
29  λs: Status.
30  let 〈instruction, ignore, ignore〉 ≝ fetch (code_memory … s) (program_counter … s) in
31    instruction.
32
33inductive trace_ends_with_ret: Type[0] ≝
34  | ends_with_ret: trace_ends_with_ret
35  | doesnt_end_with_ret: trace_ends_with_ret.
36
37definition next_instruction_is_labelled ≝
38  λcost_labels: BitVectorTrie Byte 16.
39  λs: Status.
40  let pc ≝ program_counter … (execute 1 s) in
41    match lookup_opt … pc cost_labels with
42    [ None ⇒ False
43    | _    ⇒ True
44    ].
45
46definition next_instruction_properly_relates_program_counters ≝
47  λbefore: Status.
48  λafter : Status.
49  let size ≝ current_instruction_cost before in
50  let pc_before ≝ program_counter … before in
51  let pc_after ≝ program_counter … after in
52  let sum ≝ \snd (half_add … pc_before (bitvector_of_nat … size)) in
53    sum = pc_after.
54
55definition current_instruction ≝
56  λs: Status.
57  let pc ≝ program_counter … s in
58  \fst (\fst (fetch … (code_memory … s) pc)).
59
60definition current_instruction_is_labelled ≝
61  λcost_labels: BitVectorTrie Byte 16.
62  λs: Status.
63  let pc ≝ program_counter … s in
64    match lookup_opt … pc cost_labels with
65    [ None ⇒ False
66    | _    ⇒ True
67    ].
68
69inductive trace_label_return (cost_labels: BitVectorTrie Byte 16): Status → Status → Type[0] ≝
70  | tlr_base:
71      ∀status_before: Status.
72      ∀status_after: Status.
73        trace_label_label cost_labels ends_with_ret status_before status_after →
74        trace_label_return cost_labels status_before status_after
75  | tlr_step:
76      ∀status_initial: Status.
77      ∀status_labelled: Status.
78      ∀status_final: Status.
79          trace_label_label cost_labels doesnt_end_with_ret status_initial status_labelled →
80            trace_label_return cost_labels status_labelled status_final →
81              trace_label_return cost_labels status_initial status_final
82with trace_label_label: trace_ends_with_ret → Status → Status → Type[0] ≝
83  | tll_base:
84      ∀ends_flag: trace_ends_with_ret.
85      ∀start_status: Status.
86      ∀end_status: Status.
87        trace_label_label_pre cost_labels ends_flag start_status end_status →
88        current_instruction_is_labelled cost_labels start_status →
89        trace_label_label cost_labels ends_flag start_status end_status
90with trace_label_label_pre: trace_ends_with_ret → Status → Status → Type[0] ≝
91  | tllp_base_not_return:
92      ∀start_status: Status.
93        let final_status ≝ execute 1 start_status in
94        current_instruction start_status ≠ (RealInstruction … (RET [[relative]])) →
95        ¬ (is_jump_p (current_instruction start_status)) →
96        current_instruction_is_labelled cost_labels final_status →
97          trace_label_label_pre cost_labels doesnt_end_with_ret start_status final_status
98  | tllp_base_return:
99      ∀start_status: Status.
100        let final_status ≝ execute 1 start_status in
101          current_instruction start_status = (RealInstruction … (RET [[relative]])) →
102            trace_label_label_pre cost_labels ends_with_ret start_status final_status
103  | tllp_base_jump:
104      ∀start_status: Status.
105        let final_status ≝ execute 1 start_status in
106          is_jump_p (current_instruction start_status) →
107            current_instruction_is_labelled cost_labels final_status →
108              trace_label_label_pre cost_labels doesnt_end_with_ret start_status final_status
109  | tllp_step_call:
110      ∀end_flag: trace_ends_with_ret.
111      ∀status_pre_fun_call: Status.
112      ∀status_after_fun_call: Status.
113      ∀status_final: Status.
114        let status_start_fun_call ≝ execute 1 status_pre_fun_call in
115          is_call_p (current_instruction status_pre_fun_call) →
116          next_instruction_properly_relates_program_counters status_pre_fun_call status_after_fun_call →
117          trace_label_return cost_labels status_start_fun_call status_after_fun_call →
118          trace_label_label_pre cost_labels end_flag status_after_fun_call status_final →
119            trace_label_label_pre cost_labels end_flag status_pre_fun_call status_final
120  | tllp_step_default:
121      ∀end_flag: trace_ends_with_ret.
122      ∀status_pre: Status.
123      ∀status_end: Status.
124        let status_init ≝ execute 1 status_pre in
125          trace_label_label_pre cost_labels end_flag status_init status_end →
126          ¬ (is_call_p (current_instruction status_pre)) →
127          ¬ (is_jump_p (current_instruction status_pre)) →
128          (current_instruction status_pre) ≠ (RealInstruction … (RET [[relative]])) →
129          ¬ (current_instruction_is_labelled cost_labels status_init) →
130            trace_label_label_pre cost_labels end_flag status_pre status_end.
131*)
132
133(* XXX: not us
134definition compute_simple_path0 (s:Status) (is_labelled s) (well_balanced s) (labelled_p p): trace_lab_ret ≝ ….
135
136lemma simple_path_ok:
137 ∀st: Status.∀H.
138 let p ≝ compute_simple_path0 st H in
139   ∀n.
140    nth_path n p = execute n st ∧
141     (execute' (path_length p) st = 〈st',τ〉 →
142      τ = cost_trace p)
143  ].
144*)
145
146let rec compute_max_trace_label_label_cost
147  (cost_labels: BitVectorTrie costlabel 16)
148   (trace_ends_flag: trace_ends_with_ret)
149    (start_status: Status) (final_status: Status)
150      (the_trace: trace_label_label (ASM_abstract_status cost_labels) trace_ends_flag
151        start_status final_status) on the_trace: nat ≝
152  match the_trace with
153  [ tll_base ends_flag initial final given_trace labelled_proof ⇒
154      compute_max_trace_any_label_cost … given_trace
155  ]
156and compute_max_trace_any_label_cost
157  (cost_labels: BitVectorTrie costlabel 16)
158  (trace_ends_flag: trace_ends_with_ret)
159   (start_status: Status) (final_status: Status)
160     (the_trace: trace_any_label (ASM_abstract_status cost_labels) trace_ends_flag start_status final_status)
161       on the_trace: nat ≝
162  match the_trace with
163  [ tal_base_not_return the_status _ _ _ _ ⇒ current_instruction_cost the_status
164  | tal_base_return the_status _ _ _ ⇒ current_instruction_cost the_status
165  | tal_step_call end_flag pre_fun_call start_fun_call after_fun_call final
166     _ _ _ call_trace final_trace ⇒
167      let current_instruction_cost ≝ current_instruction_cost pre_fun_call in
168      let call_trace_cost ≝ compute_max_trace_label_return_cost … call_trace in
169      let final_trace_cost ≝ compute_max_trace_any_label_cost cost_labels end_flag … final_trace in
170        call_trace_cost + current_instruction_cost + final_trace_cost
171  | tal_step_default end_flag status_pre status_init status_end _ tail_trace _ _ ⇒
172      let current_instruction_cost ≝ current_instruction_cost status_pre in
173      let tail_trace_cost ≝
174       compute_max_trace_any_label_cost cost_labels end_flag
175        status_init status_end tail_trace
176      in
177        current_instruction_cost + tail_trace_cost
178  ]
179and compute_max_trace_label_return_cost
180  (cost_labels: BitVectorTrie costlabel 16)
181  (start_status: Status) (final_status: Status)
182    (the_trace: trace_label_return (ASM_abstract_status cost_labels) start_status final_status)
183      on the_trace: nat ≝
184  match the_trace with
185  [ tlr_base before after trace_to_lift ⇒ compute_max_trace_label_label_cost … trace_to_lift
186  | tlr_step initial labelled final labelled_trace ret_trace ⇒
187      let labelled_cost ≝ compute_max_trace_label_label_cost … labelled_trace in
188      let return_cost ≝ compute_max_trace_label_return_cost … ret_trace in
189        labelled_cost + return_cost
190  ].
191
192(*Useless now?
193(* To be moved *)
194lemma pred_minus_1:
195  ∀m, n: nat.
196  ∀proof: n < m.
197    pred (m - n) = m - n - 1.
198  #m #n
199  cases m
200  [ #proof
201    cases(lt_to_not_zero … proof)
202  | #m' #proof
203    normalize in ⊢ (???%);
204    cases n
205    [ normalize //
206    | #n' normalize
207      cases(m' - n')
208      [ %
209      | #Sm_n'
210        normalize //
211      ]
212    ]
213  ]
214qed.
215
216lemma succ_m_plus_one:
217  ∀m: nat.
218    S m = m + 1.
219 //
220qed.*)
221
222include alias "arithmetics/nat.ma".
223
224(*Useless now?
225lemma minus_m_n_minus_minus_plus_1:
226  ∀m, n: nat.
227  ∀proof: n < m.
228    m - n = (m - n - 1) + 1.
229 /3 by lt_plus_to_minus_r, plus_minus/
230qed.
231
232lemma plus_minus_rearrangement_1:
233  ∀m, n, o: nat.
234  ∀proof_n_m: n ≤ m.
235  ∀proof_m_o: m ≤ o.
236    (m - n) + (o - m) = o - n.
237  #m #n #o #H1 #H2
238  lapply (minus_to_plus … H1 (refl …)) #K1 >K1
239  lapply (minus_to_plus … H2 (refl …)) #K2 >K2
240  /2 by plus_minus/
241qed.
242
243lemma plus_minus_rearrangement_2:
244  ∀m, n, o: nat. n ≤ m → o ≤ n →
245    (m - n) + (n - o) = m - o.
246 /2 by plus_minus_rearrangement_1/
247qed.*)
248
249(*
250let rec compute_max_trace_label_label_cost_is_ok
251  (cost_labels: BitVectorTrie Byte 16)
252   (trace_ends_flag: trace_ends_with_ret)
253    (start_status: Status) (final_status: Status)
254      (the_trace: trace_label_label (ASM_abstract_status cost_labels) trace_ends_flag
255        start_status final_status) on the_trace:
256          compute_max_trace_label_label_cost cost_labels trace_ends_flag start_status final_status the_trace =
257            (clock … final_status) - (clock … start_status) ≝ ?
258and compute_max_trace_any_label_cost_is_ok
259  (cost_labels: BitVectorTrie Byte 16)
260  (trace_ends_flag: trace_ends_with_ret)
261   (start_status: Status) (final_status: Status)
262     (the_trace: trace_any_label (ASM_abstract_status cost_labels) trace_ends_flag start_status final_status)
263       on the_trace:
264         compute_max_trace_any_label_cost cost_labels trace_ends_flag start_status final_status the_trace =
265           (clock … final_status) - (clock … start_status) ≝ ?
266and compute_max_trace_label_return_cost_is_ok
267  (cost_labels: BitVectorTrie Byte 16)
268  (start_status: Status) (final_status: Status)
269    (the_trace: trace_label_return (ASM_abstract_status cost_labels) start_status final_status)
270      on the_trace:
271        compute_max_trace_label_return_cost cost_labels start_status final_status the_trace =
272          (clock … final_status) - (clock … start_status) ≝ ?.
273  [1:
274    cases the_trace
275    #ends_flag #start_status #end_status #any_label_trace #is_costed
276    normalize @compute_max_trace_any_label_cost_is_ok
277  |2:
278  |3:
279    cases the_trace
280    [1:
281      #status_before #status_after #trace_to_lift
282      normalize @compute_max_trace_label_label_cost_is_ok
283    |2:
284      #status_initial #status_labelled #status_final #labelled_trace #ret_trace
285      normalize >compute_max_trace_label_label_cost_is_ok
286      >compute_max_trace_label_return_cost_is_ok
287    ]
288  ].
289*)
290
291(* XXX: work below here: *)
292
293let rec compute_paid_trace_any_label
294  (cost_labels: BitVectorTrie costlabel 16)
295  (trace_ends_flag: trace_ends_with_ret)
296   (start_status: Status) (final_status: Status)
297     (the_trace: trace_any_label (ASM_abstract_status cost_labels) trace_ends_flag start_status final_status)
298       on the_trace: nat ≝
299  match the_trace with
300  [ tal_base_not_return the_status _ _ _ _ ⇒ current_instruction_cost the_status
301  | tal_base_return the_status _ _ _ ⇒ current_instruction_cost the_status
302  | tal_step_call end_flag pre_fun_call start_fun_call after_fun_call final
303     _ _ _ call_trace final_trace ⇒
304      let current_instruction_cost ≝ current_instruction_cost pre_fun_call in
305      let final_trace_cost ≝ compute_paid_trace_any_label cost_labels end_flag … final_trace in
306        current_instruction_cost + final_trace_cost
307  | tal_step_default end_flag status_pre status_init status_end _ tail_trace _ _ ⇒
308      let current_instruction_cost ≝ current_instruction_cost status_pre in
309      let tail_trace_cost ≝
310       compute_paid_trace_any_label cost_labels end_flag
311        status_init status_end tail_trace
312      in
313        current_instruction_cost + tail_trace_cost
314  ].
315
316definition compute_paid_trace_label_label ≝
317 λcost_labels: BitVectorTrie costlabel 16.
318  λtrace_ends_flag: trace_ends_with_ret.
319   λstart_status: Status.
320    λfinal_status: Status.
321     λthe_trace: trace_label_label (ASM_abstract_status cost_labels) trace_ends_flag
322      start_status final_status.
323  match the_trace with
324  [ tll_base ends_flag initial final given_trace labelled_proof ⇒
325      compute_paid_trace_any_label … given_trace
326  ].
327
328let rec compute_trace_label_label_cost_using_paid
329  (cost_labels: BitVectorTrie costlabel 16)
330   (trace_ends_flag: trace_ends_with_ret)
331    (start_status: Status) (final_status: Status)
332      (the_trace: trace_label_label (ASM_abstract_status cost_labels) trace_ends_flag
333        start_status final_status) on the_trace: nat ≝
334  match the_trace with
335  [ tll_base ends_flag initial final given_trace labelled_proof ⇒
336      compute_paid_trace_label_label cost_labels … the_trace +
337      compute_trace_any_label_cost_using_paid … given_trace
338  ]
339and compute_trace_any_label_cost_using_paid
340  (cost_labels: BitVectorTrie costlabel 16)
341  (trace_ends_flag: trace_ends_with_ret)
342   (start_status: Status) (final_status: Status)
343     (the_trace: trace_any_label (ASM_abstract_status cost_labels) trace_ends_flag start_status final_status)
344       on the_trace: nat ≝
345  match the_trace with
346  [ tal_base_not_return the_status _ _ _ _ ⇒ 0
347  | tal_base_return the_status _ _ _ ⇒ 0
348  | tal_step_call end_flag pre_fun_call start_fun_call after_fun_call final
349     _ _ _ call_trace final_trace ⇒
350      let call_trace_cost ≝ compute_trace_label_return_cost_using_paid … call_trace in
351      let final_trace_cost ≝ compute_trace_any_label_cost_using_paid cost_labels end_flag … final_trace in
352        call_trace_cost + final_trace_cost
353  | tal_step_default end_flag status_pre status_init status_end _ tail_trace _ _ ⇒
354     compute_trace_any_label_cost_using_paid cost_labels end_flag
355      status_init status_end tail_trace
356  ]
357and compute_trace_label_return_cost_using_paid
358  (cost_labels: BitVectorTrie costlabel 16)
359  (start_status: Status) (final_status: Status)
360    (the_trace: trace_label_return (ASM_abstract_status cost_labels) start_status final_status)
361      on the_trace: nat ≝
362  match the_trace with
363  [ tlr_base before after trace_to_lift ⇒ compute_trace_label_label_cost_using_paid … trace_to_lift
364  | tlr_step initial labelled final labelled_trace ret_trace ⇒
365      let labelled_cost ≝ compute_trace_label_label_cost_using_paid … labelled_trace in
366      let return_cost ≝ compute_trace_label_return_cost_using_paid … ret_trace in
367        labelled_cost + return_cost
368  ].
369
370let rec compute_trace_label_label_cost_using_paid_ok
371  (cost_labels: BitVectorTrie costlabel 16)
372   (trace_ends_flag: trace_ends_with_ret)
373    (start_status: Status) (final_status: Status)
374      (the_trace: trace_label_label (ASM_abstract_status cost_labels) trace_ends_flag
375        start_status final_status) on the_trace:
376 compute_trace_label_label_cost_using_paid cost_labels … the_trace =
377 compute_max_trace_label_label_cost … the_trace ≝ ?
378and compute_trace_any_label_cost_using_paid_ok
379  (cost_labels: BitVectorTrie costlabel 16)
380  (trace_ends_flag: trace_ends_with_ret)
381   (start_status: Status) (final_status: Status)
382     (the_trace: trace_any_label (ASM_abstract_status cost_labels)
383      trace_ends_flag start_status final_status) on the_trace:     
384  compute_paid_trace_any_label cost_labels trace_ends_flag … the_trace
385  +compute_trace_any_label_cost_using_paid cost_labels trace_ends_flag … the_trace
386  =compute_max_trace_any_label_cost cost_labels trace_ends_flag … the_trace ≝ ?
387and compute_trace_label_return_cost_using_paid_ok
388  (cost_labels: BitVectorTrie costlabel 16)
389  (start_status: Status) (final_status: Status)
390    (the_trace: trace_label_return (ASM_abstract_status cost_labels)
391     start_status final_status) on the_trace:
392 compute_trace_label_return_cost_using_paid cost_labels … the_trace =
393 compute_max_trace_label_return_cost cost_labels … the_trace ≝ ?.
394[ cases the_trace #endsf #ss #es #tr #H normalize
395  @compute_trace_any_label_cost_using_paid_ok
396| cases the_trace
397  [ #ss #fs #H1 #H2 #H3 whd in ⊢ (??(?%%)%); <plus_n_O %
398  | #ss #fs #H1 #H2 whd in ⊢ (??(?%%)%); <plus_n_O %
399  | #ef #spfc #ssfc #safc #sf #H1 #H2 #H3 #tr1 #tr2 whd in ⊢ (??(?%%)%);
400    <compute_trace_any_label_cost_using_paid_ok
401    <compute_trace_label_return_cost_using_paid_ok
402    -compute_trace_label_label_cost_using_paid_ok
403    -compute_trace_label_return_cost_using_paid_ok
404    -compute_trace_any_label_cost_using_paid_ok
405    >commutative_plus in ⊢ (???(?%?));
406    >commutative_plus in ⊢ (??(??%)?);
407    >associative_plus >associative_plus in ⊢ (???%); @eq_f2 try %
408    <associative_plus <commutative_plus %
409  | #ef #sp #si #se #H1 #tr #H2 #H3 whd in ⊢ (??(?%%)%); >associative_plus @eq_f2
410    [ % | @compute_trace_any_label_cost_using_paid_ok ]
411  ]
412| cases the_trace
413  [ #sb #sa #tr normalize @compute_trace_label_label_cost_using_paid_ok
414  | #si #sl #sf #tr1 #tr2 normalize @eq_f2
415    [ @compute_trace_label_label_cost_using_paid_ok
416    | @compute_trace_label_return_cost_using_paid_ok ]]]
417qed.
418
419(*
420let rec compute_paid_trace_label_return
421  (cost_labels: BitVectorTrie costlabel 16)
422  (start_status: Status) (final_status: Status)
423    (the_trace: trace_label_return (ASM_abstract_status cost_labels) start_status final_status)
424      on the_trace: nat ≝
425 match the_trace with
426  [ tlr_base before after trace_to_lift ⇒ compute_paid_trace_label_label … trace_to_lift
427  | tlr_step initial labelled final labelled_trace ret_trace ⇒
428      let labelled_cost ≝ compute_paid_trace_label_label … labelled_trace in
429      let return_cost ≝ compute_paid_trace_label_return … ret_trace in
430        labelled_cost + return_cost
431  ].
432*)
433
434let rec compute_cost_trace_label_label
435  (cost_labels: BitVectorTrie costlabel 16)
436   (trace_ends_flag: trace_ends_with_ret)
437    (start_status: Status) (final_status: Status)
438      (the_trace: trace_label_label (ASM_abstract_status cost_labels) trace_ends_flag
439        start_status final_status) on the_trace:
440         list (Σk:costlabel. ∃pc. lookup_opt … pc cost_labels = Some … k) ≝
441  match the_trace with
442  [ tll_base ends_flag initial final given_trace labelled_proof ⇒
443     let pc ≝ program_counter … initial in
444     let label ≝
445      match lookup_opt … pc cost_labels return λx. match x with [None ⇒ False | Some _ ⇒ True] → costlabel with
446      [ None ⇒ λabs. ⊥
447      | Some l ⇒ λ_. l ] labelled_proof in
448     (dp … label ?)::compute_cost_trace_any_label … given_trace
449  ]
450and compute_cost_trace_any_label
451  (cost_labels: BitVectorTrie costlabel 16)
452  (trace_ends_flag: trace_ends_with_ret)
453   (start_status: Status) (final_status: Status)
454     (the_trace: trace_any_label (ASM_abstract_status cost_labels) trace_ends_flag start_status final_status)
455       on the_trace: list (Σk:costlabel. ∃pc. lookup_opt … pc cost_labels = Some … k) ≝
456  match the_trace with
457  [ tal_base_not_return the_status _ _ _ _ ⇒ []
458  | tal_base_return the_status _ _ _ ⇒ []
459  | tal_step_call end_flag pre_fun_call start_fun_call after_fun_call final
460     _ _ _ call_trace final_trace ⇒
461      let call_cost_trace ≝ compute_cost_trace_label_return … call_trace in
462      let final_cost_trace ≝ compute_cost_trace_any_label cost_labels end_flag … final_trace in
463        call_cost_trace @ final_cost_trace
464  | tal_step_default end_flag status_pre status_init status_end _ tail_trace _ _ ⇒
465       compute_cost_trace_any_label cost_labels end_flag
466        status_init status_end tail_trace
467  ]
468and compute_cost_trace_label_return
469  (cost_labels: BitVectorTrie costlabel 16)
470  (start_status: Status) (final_status: Status)
471    (the_trace: trace_label_return (ASM_abstract_status cost_labels) start_status final_status)
472      on the_trace: list (Σk:costlabel. ∃pc. lookup_opt … pc cost_labels = Some … k) ≝
473  match the_trace with
474  [ tlr_base before after trace_to_lift ⇒ compute_cost_trace_label_label … trace_to_lift
475  | tlr_step initial labelled final labelled_trace ret_trace ⇒
476      let labelled_cost ≝ compute_cost_trace_label_label … labelled_trace in
477      let return_cost ≝ compute_cost_trace_label_return … ret_trace in
478        labelled_cost @ return_cost
479  ].
480 [ %{pc} whd in match label;  generalize in match labelled_proof; whd in ⊢ (% → ?);
481  cases (lookup_opt costlabel … pc cost_labels) normalize
482  [ #abs cases abs | // ]
483 | // ]
484qed.
485
486(* ??????????????????????? *)
487axiom block_cost_static_dynamic_ok:
488 ∀cost_labels: BitVectorTrie costlabel 16.
489 ∀trace_ends_flag.
490 ∀start_status: Status.
491 ∀final_status: Status.
492 ∀the_trace:
493  trace_label_label (ASM_abstract_status cost_labels) trace_ends_flag
494   start_status final_status.
495 let mem ≝ code_memory … start_status in
496 let pc ≝ program_counter … start_status in
497 let program_size ≝ 2^16 in
498  block_cost mem cost_labels pc program_size =
499  compute_paid_trace_label_label cost_labels trace_ends_flag
500   start_status final_status the_trace.
501
502(* To be moved elsewhere*)
503lemma le_S_n_m_to_le_n_m: ∀n,m. S n ≤ m → n ≤ m.
504 #n #m #H change with (pred (S n) ≤ m) @(transitive_le ? (S n)) //
505qed.
506
507(* Here I would like to use arithmetics/bigops.ma, but it requires the
508   function f to be total on nat, which is not the case here *)
509let rec bigplus0 (b:nat) (f: ∀n:nat. n < b → nat) (n:nat) on n ≝
510  match n return λn.n < b → nat with
511   [ O ⇒ λ_. 0
512   | S k ⇒ λH. f k ? + bigplus0 b f k ?
513   ].
514 @(le_S_n_m_to_le_n_m … H)
515qed.
516
517definition bigplus ≝
518 λn,f.
519 match n return λx. x = n → nat with
520 [ O ⇒ λ_. 0
521 | S m ⇒ λH. bigplus0 n f m ? ] (refl … n).
522 //
523qed.
524
525lemma compute_max_trace_label_return_cost_ok_with_trace:
526 ∀cost_labels: BitVectorTrie costlabel 16.
527 ∀cost_map: identifier_map CostTag nat.
528 ∀initial,final.
529 ∀trace: trace_label_return (ASM_abstract_status cost_labels) initial final.
530 ∀codom_dom: (∀pc,k. lookup_opt … pc cost_labels = Some … k → present … cost_map k).
531 ∀dom_codom:(∀k. ∀k_pres:present … cost_map k. ∃pc. lookup_opt … pc cost_labels = Some … k →
532   block_cost (code_memory … initial) cost_labels pc 2^16 =
533   lookup_present … k_pres).
534  let ctrace ≝ compute_cost_trace_label_return … trace in
535  compute_max_trace_label_return_cost … trace =
536   bigplus (|ctrace|) (λi,H.lookup_present … cost_map (nth_safe ? i ctrace H) ?).
537 [2: cases (nth_safe … i ctrace H) normalize #id * #id_pc #K
538   lapply (codom_dom … K) #k_pres //
539 | #cost_labels #costmap #initial #final #trace #codom_dom #dom_codom normalize nodelta
540   whd in match
541
542lemma
543 compute_max_trace_any_label_cost cost_label trace_ends_flag start_status
544  final_status the_trace =
545 
546
547let rec compute_paid_trace_label_label_cost
548  (cost_labels: BitVectorTrie Byte 16)
549   (trace_ends_flag: trace_ends_with_ret)
550    (start_status: Status) (final_status: Status)
551      (the_trace: trace_label_label (ASM_abstract_status cost_labels) trace_ends_flag
552        start_status final_status) on the_trace: nat ≝
553  match the_trace with
554  [ tll_base _ _ _ given_trace _ ⇒
555      compute_paid_trace_any_label_cost … given_trace
556  ]
557and compute_paid_trace_any_label_cost
558  (cost_labels: BitVectorTrie Byte 16)
559  (trace_ends_flag: trace_ends_with_ret)
560   (start_status: Status) (final_status: Status)
561     (the_trace: trace_any_label (ASM_abstract_status cost_labels) trace_ends_flag start_status final_status)
562       on the_trace: nat ≝
563  match the_trace with
564  [ tal_base_not_return the_status _ _ _ _ ⇒ current_instruction_cost the_status
565  | tal_base_return the_status _ _ _ ⇒ current_instruction_cost the_status
566  | tal_step_call end_flag pre_fun_call start_fun_call after_fun_call final
567     _ _ _ call_trace final_trace ⇒
568      let current_instruction_cost ≝ current_instruction_cost pre_fun_call in
569      let final_trace_cost ≝ compute_paid_trace_any_label_cost cost_labels end_flag … final_trace in
570        current_instruction_cost + final_trace_cost
571  | tal_step_default end_flag status_pre status_init status_end _ tail_trace _ _ ⇒
572      let current_instruction_cost ≝ current_instruction_cost status_pre in
573      let tail_trace_cost ≝
574       compute_paid_trace_any_label_cost cost_labels end_flag
575        status_init status_end tail_trace
576      in
577        current_instruction_cost + tail_trace_cost
578  ]
579and compute_paid_trace_label_return_cost
580  (cost_labels: BitVectorTrie Byte 16)
581  (start_status: Status) (final_status: Status)
582    (the_trace: trace_label_return (ASM_abstract_status cost_labels) start_status final_status)
583      on the_trace: nat ≝
584  match the_trace with
585  [ tlr_base before after trace_to_lift ⇒ compute_paid_trace_label_label_cost … trace_to_lift
586  | tlr_step initial labelled final labelled_trace ret_trace ⇒
587      let labelled_cost ≝ compute_paid_trace_label_label_cost … labelled_trace in
588      let return_cost ≝ compute_paid_trace_label_return_cost … ret_trace in
589        labelled_cost + return_cost
590  ].
591
592let rec trace_lab_rec_cost' (p: trace_lab_ret) : nat.
593 | (call b bf tr af tl) as self ⇒
594    trace_lab_lab_cost_nocall self + trace_lab_ret_cost' tr +
595    trace_lab_rec_cost' tl
596
597theorem main_lemma:
598 ∀p. trace_lab_rec_cost p = trace_lab_rec_cost' p.
599
600axiom lemma1:
601 ∀p: simple_path.
602  traverse_cost_internal (pc (hd p)) … = trace_lab_lab_cost_nocall p.
603
604axiom lemma2:
605 ∀s,l,cost_map.
606  is_labelled l s →
607   traverse_cost_internal s = cost_map l.
608
609axiom main_statement:
610 ∀s.
611 ∀cost_map.
612 let p ≝ compute_simple_path0 s in
613 ∑ (cost_trace p) cost_map = trace_lab_rec_cost' p.
614
615axiom main_statement:
616 ∀s.
617 ∀cost_map.
618 let p ≝ compute_simple_path0 s in
619  execute' (path_length p) s = 〈s',τ〉 →
620   Timer s' - Timer s = ∑ τ cost_map.
Note: See TracBrowser for help on using the repository browser.