source: src/ASM/CostsProof.ma @ 1571

Last change on this file since 1571 was 1571, checked in by mulligan, 8 years ago

small changes

File size: 35.8 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(*
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*)
232
233lemma plus_minus_rearrangement_1:
234  ∀m, n, o: nat.
235  ∀proof_n_m: n ≤ m.
236  ∀proof_m_o: m ≤ o.
237    (m - n) + (o - m) = o - n.
238  #m #n #o #H1 #H2
239  lapply (minus_to_plus … H1 (refl …)) #K1 >K1
240  lapply (minus_to_plus … H2 (refl …)) #K2 >K2
241  /2 by plus_minus/
242qed.
243
244lemma plus_minus_rearrangement_2:
245  ∀m, n, o: nat. n ≤ m → o ≤ n →
246    (m - n) + (n - o) = m - o.
247 /2 by plus_minus_rearrangement_1/
248qed.
249
250lemma current_instruction_cost_non_zero:
251  ∀s: Status.
252    0 ≤ current_instruction_cost s.
253  //
254qed.
255
256lemma le_monotonic_plus:
257  ∀m, n, o: nat.
258    m ≤ n → m + o ≤ n + o.
259  #m #n #o #hyp
260  elim o
261  [ //
262  | #o' #ind_hyp
263    <plus_n_Sm <plus_n_Sm
264    @le_S_S
265    assumption
266  ]
267qed.
268
269lemma le_plus_to_minus_l:
270  ∀m, n, o: nat.
271    n ≤ o → m ≤ o - n → m + n ≤ o.
272  #m #n #o #le_hyp #hyp
273  generalize in match (le_monotonic_plus m (o - n) n hyp);
274  generalize in match (plus_minus_m_m o n le_hyp);
275  #assm <assm in ⊢ (% → ?); #finished assumption
276qed.
277   
278lemma minus_m_n_le_n_m:
279  ∀m, n, o.
280    m - n = o → o > 0 → n ≤ m.
281  #m #n #o #eq_hyp
282  cases o
283  [ #absrd normalize in absrd; @le
284  normalize in ⊢ (% → ?);
285  <eq_hyp in ⊢ (% → ?);
286  #lt_hyp
287  generalize in match (le_plus_to_minus_l 1 n m ? lt_hyp);
288  [1: /2/ |
289qed.
290 
291
292let rec compute_max_trace_label_label_cost_is_ok
293  (cost_labels: BitVectorTrie costlabel 16)
294   (trace_ends_flag: trace_ends_with_ret)
295    (start_status: Status) (final_status: Status)
296      (the_trace: trace_label_label (ASM_abstract_status cost_labels) trace_ends_flag
297        start_status final_status) on the_trace:
298          And (compute_max_trace_label_label_cost cost_labels trace_ends_flag start_status final_status the_trace =
299            (clock … final_status) - (clock … start_status)) (clock … start_status ≤ clock … final_status) ≝ ?
300and compute_max_trace_any_label_cost_is_ok
301  (cost_labels: BitVectorTrie costlabel 16)
302  (trace_ends_flag: trace_ends_with_ret)
303   (start_status: Status) (final_status: Status)
304     (the_trace: trace_any_label (ASM_abstract_status cost_labels) trace_ends_flag start_status final_status)
305       on the_trace:
306         (compute_max_trace_any_label_cost cost_labels trace_ends_flag start_status final_status the_trace =
307           (clock … final_status) - (clock … start_status)) ∧ (clock … start_status ≤ clock … final_status) ≝ ?
308and compute_max_trace_label_return_cost_is_ok
309  (cost_labels: BitVectorTrie costlabel 16)
310  (start_status: Status) (final_status: Status)
311    (the_trace: trace_label_return (ASM_abstract_status cost_labels) start_status final_status)
312      on the_trace:
313        (compute_max_trace_label_return_cost cost_labels start_status final_status the_trace =
314          (clock … final_status) - (clock … start_status)) ∧ (clock … start_status ≤ clock … final_status) ≝ ?.
315  [1:
316    cases the_trace
317    #ends_flag #start_status #end_status #any_label_trace #is_costed
318    normalize @compute_max_trace_any_label_cost_is_ok
319  |2:
320    cases the_trace
321    [1:
322      #start_status #final_status #is_next #is_not_return #is_costed
323      change with (current_instruction_cost start_status) in ⊢ (?(??%?)?);
324      cases(is_next)
325      @conj
326      [1:
327        cases(execute_1 start_status)
328        #the_status #assm
329        whd in match eject; normalize nodelta
330        >assm %
331      |2:
332        cases(execute_1 start_status)
333        #the_status #assm
334        whd in match eject; normalize nodelta
335        @(minus_m_n_gt_o_0_le_n_m ? ? (current_instruction_cost start_status))
336        [1: assumption
337        |2: @current_instruction_cost_non_zero
338        ]
339      ]
340    |2:
341      #start_status #final_status #is_next #is_return
342      change with (current_instruction_cost start_status) in ⊢ (?(??%?)?);
343      cases(is_next)
344      @conj
345      [1:
346        cases(execute_1 start_status)
347        #the_status #assm
348        whd in match eject; normalize nodelta
349        >assm %
350      |2:
351        cases(execute_1 start_status)
352        #the_status #assm
353        whd in match eject; normalize nodelta
354        @(minus_m_n_gt_o_0_le_n_m ? ? (current_instruction_cost start_status))
355        [1: assumption
356        |2: @current_instruction_cost_non_zero
357        ]
358      ]
359    |3:
360      #end_flag #status_pre_fun_call #status_start_fun_call #status_after_fun_call
361      #status_final #is_next #is_call #is_after_return #call_trace #final_trace
362      change with (
363      let current_instruction_cost ≝ current_instruction_cost status_pre_fun_call in
364      let call_trace_cost ≝ compute_max_trace_label_return_cost … call_trace in
365      let final_trace_cost ≝ compute_max_trace_any_label_cost cost_labels end_flag … final_trace in
366        call_trace_cost + current_instruction_cost + final_trace_cost) in ⊢ (?(??%?)?);
367      normalize nodelta;
368      @conj
369      [1:
370        cases(compute_max_trace_label_return_cost_is_ok cost_labels status_start_fun_call
371          status_after_fun_call call_trace)
372        #trace_label_return_eq #trace_label_return_le
373        cases(compute_max_trace_any_label_cost_is_ok cost_labels end_flag status_after_fun_call
374          status_final final_trace)
375        #trace_any_label_eq #trace_any_label_le
376        >trace_label_return_eq >trace_any_label_eq
377        cases daemon (* XXX: complete me *)
378      |2:
379        cases daemon (* XXX: complete me *)
380      ]
381    |4:
382      #end_flag #status_pre #status_init #status_end #is_next
383      #trace_any_label #is_other #is_not_costed
384      cases daemon (* XXX: complete me *)
385    ]
386  |3:
387    cases the_trace
388    [1:
389      #status_before #status_after #trace_to_lift
390      normalize @compute_max_trace_label_label_cost_is_ok
391    |2:
392      #status_initial #status_labelled #status_final #labelled_trace #ret_trace
393      normalize
394      cases(compute_max_trace_label_label_cost_is_ok cost_labels doesnt_end_with_ret status_initial status_labelled labelled_trace);
395      #label_label_trace_equality #label_label_trace_leq
396      cases(compute_max_trace_label_return_cost_is_ok cost_labels status_labelled status_final ret_trace);
397      #label_return_trace_equality #label_return_trace_leq
398      >label_label_trace_equality >label_return_trace_equality
399      @conj
400      [2: @(transitive_le (clock (BitVectorTrie (Vector bool 8) 16) status_initial)
401            (clock (BitVectorTrie Byte 16) status_labelled)
402            (clock (BitVectorTrie (Vector bool 8) 16) status_final))
403      |1: @plus_minus_rearrangement_1
404      ]
405      assumption
406    ]
407  ]
408qed.
409
410(* XXX: work below here: *)
411
412let rec compute_paid_trace_any_label
413  (cost_labels: BitVectorTrie costlabel 16)
414  (trace_ends_flag: trace_ends_with_ret)
415   (start_status: Status) (final_status: Status)
416     (the_trace: trace_any_label (ASM_abstract_status cost_labels) trace_ends_flag start_status final_status)
417       on the_trace: nat ≝
418  match the_trace with
419  [ tal_base_not_return the_status _ _ _ _ ⇒ current_instruction_cost the_status
420  | tal_base_return the_status _ _ _ ⇒ current_instruction_cost the_status
421  | tal_step_call end_flag pre_fun_call start_fun_call after_fun_call final
422     _ _ _ call_trace final_trace ⇒
423      let current_instruction_cost ≝ current_instruction_cost pre_fun_call in
424      let final_trace_cost ≝ compute_paid_trace_any_label cost_labels end_flag … final_trace in
425        current_instruction_cost + final_trace_cost
426  | tal_step_default end_flag status_pre status_init status_end _ tail_trace _ _ ⇒
427      let current_instruction_cost ≝ current_instruction_cost status_pre in
428      let tail_trace_cost ≝
429       compute_paid_trace_any_label cost_labels end_flag
430        status_init status_end tail_trace
431      in
432        current_instruction_cost + tail_trace_cost
433  ].
434
435definition compute_paid_trace_label_label ≝
436 λcost_labels: BitVectorTrie costlabel 16.
437  λtrace_ends_flag: trace_ends_with_ret.
438   λstart_status: Status.
439    λfinal_status: Status.
440     λthe_trace: trace_label_label (ASM_abstract_status cost_labels) trace_ends_flag
441      start_status final_status.
442  match the_trace with
443  [ tll_base ends_flag initial final given_trace labelled_proof ⇒
444      compute_paid_trace_any_label … given_trace
445  ].
446
447let rec compute_trace_label_label_cost_using_paid
448  (cost_labels: BitVectorTrie costlabel 16)
449   (trace_ends_flag: trace_ends_with_ret)
450    (start_status: Status) (final_status: Status)
451      (the_trace: trace_label_label (ASM_abstract_status cost_labels) trace_ends_flag
452        start_status final_status) on the_trace: nat ≝
453  match the_trace with
454  [ tll_base ends_flag initial final given_trace labelled_proof ⇒
455      compute_paid_trace_label_label cost_labels … the_trace +
456      compute_trace_any_label_cost_using_paid … given_trace
457  ]
458and compute_trace_any_label_cost_using_paid
459  (cost_labels: BitVectorTrie costlabel 16)
460  (trace_ends_flag: trace_ends_with_ret)
461   (start_status: Status) (final_status: Status)
462     (the_trace: trace_any_label (ASM_abstract_status cost_labels) trace_ends_flag start_status final_status)
463       on the_trace: nat ≝
464  match the_trace with
465  [ tal_base_not_return the_status _ _ _ _ ⇒ 0
466  | tal_base_return the_status _ _ _ ⇒ 0
467  | tal_step_call end_flag pre_fun_call start_fun_call after_fun_call final
468     _ _ _ call_trace final_trace ⇒
469      let call_trace_cost ≝ compute_trace_label_return_cost_using_paid … call_trace in
470      let final_trace_cost ≝ compute_trace_any_label_cost_using_paid cost_labels end_flag … final_trace in
471        call_trace_cost + final_trace_cost
472  | tal_step_default end_flag status_pre status_init status_end _ tail_trace _ _ ⇒
473     compute_trace_any_label_cost_using_paid cost_labels end_flag
474      status_init status_end tail_trace
475  ]
476and compute_trace_label_return_cost_using_paid
477  (cost_labels: BitVectorTrie costlabel 16)
478  (start_status: Status) (final_status: Status)
479    (the_trace: trace_label_return (ASM_abstract_status cost_labels) start_status final_status)
480      on the_trace: nat ≝
481  match the_trace with
482  [ tlr_base before after trace_to_lift ⇒ compute_trace_label_label_cost_using_paid … trace_to_lift
483  | tlr_step initial labelled final labelled_trace ret_trace ⇒
484      let labelled_cost ≝ compute_trace_label_label_cost_using_paid … labelled_trace in
485      let return_cost ≝ compute_trace_label_return_cost_using_paid … ret_trace in
486        labelled_cost + return_cost
487  ].
488
489let rec compute_trace_label_label_cost_using_paid_ok
490  (cost_labels: BitVectorTrie costlabel 16)
491   (trace_ends_flag: trace_ends_with_ret)
492    (start_status: Status) (final_status: Status)
493      (the_trace: trace_label_label (ASM_abstract_status cost_labels) trace_ends_flag
494        start_status final_status) on the_trace:
495 compute_trace_label_label_cost_using_paid cost_labels … the_trace =
496 compute_max_trace_label_label_cost … the_trace ≝ ?
497and compute_trace_any_label_cost_using_paid_ok
498  (cost_labels: BitVectorTrie costlabel 16)
499  (trace_ends_flag: trace_ends_with_ret)
500   (start_status: Status) (final_status: Status)
501     (the_trace: trace_any_label (ASM_abstract_status cost_labels)
502      trace_ends_flag start_status final_status) on the_trace:     
503  compute_paid_trace_any_label cost_labels trace_ends_flag … the_trace
504  +compute_trace_any_label_cost_using_paid cost_labels trace_ends_flag … the_trace
505  =compute_max_trace_any_label_cost cost_labels trace_ends_flag … the_trace ≝ ?
506and compute_trace_label_return_cost_using_paid_ok
507  (cost_labels: BitVectorTrie costlabel 16)
508  (start_status: Status) (final_status: Status)
509    (the_trace: trace_label_return (ASM_abstract_status cost_labels)
510     start_status final_status) on the_trace:
511 compute_trace_label_return_cost_using_paid cost_labels … the_trace =
512 compute_max_trace_label_return_cost cost_labels … the_trace ≝ ?.
513[ cases the_trace #endsf #ss #es #tr #H normalize
514  @compute_trace_any_label_cost_using_paid_ok
515| cases the_trace
516  [ #ss #fs #H1 #H2 #H3 whd in ⊢ (??(?%%)%); <plus_n_O %
517  | #ss #fs #H1 #H2 whd in ⊢ (??(?%%)%); <plus_n_O %
518  | #ef #spfc #ssfc #safc #sf #H1 #H2 #H3 #tr1 #tr2 whd in ⊢ (??(?%%)%);
519    <compute_trace_any_label_cost_using_paid_ok
520    <compute_trace_label_return_cost_using_paid_ok
521    -compute_trace_label_label_cost_using_paid_ok
522    -compute_trace_label_return_cost_using_paid_ok
523    -compute_trace_any_label_cost_using_paid_ok
524    >commutative_plus in ⊢ (???(?%?));
525    >commutative_plus in ⊢ (??(??%)?);
526    >associative_plus >associative_plus in ⊢ (???%); @eq_f2 try %
527    <associative_plus <commutative_plus %
528  | #ef #sp #si #se #H1 #tr #H2 #H3 whd in ⊢ (??(?%%)%); >associative_plus @eq_f2
529    [ % | @compute_trace_any_label_cost_using_paid_ok ]
530  ]
531| cases the_trace
532  [ #sb #sa #tr normalize @compute_trace_label_label_cost_using_paid_ok
533  | #si #sl #sf #tr1 #tr2 normalize @eq_f2
534    [ @compute_trace_label_label_cost_using_paid_ok
535    | @compute_trace_label_return_cost_using_paid_ok ]]]
536qed.
537
538(*
539let rec compute_paid_trace_label_return
540  (cost_labels: BitVectorTrie costlabel 16)
541  (start_status: Status) (final_status: Status)
542    (the_trace: trace_label_return (ASM_abstract_status cost_labels) start_status final_status)
543      on the_trace: nat ≝
544 match the_trace with
545  [ tlr_base before after trace_to_lift ⇒ compute_paid_trace_label_label … trace_to_lift
546  | tlr_step initial labelled final labelled_trace ret_trace ⇒
547      let labelled_cost ≝ compute_paid_trace_label_label … labelled_trace in
548      let return_cost ≝ compute_paid_trace_label_return … ret_trace in
549        labelled_cost + return_cost
550  ].
551*)
552
553let rec compute_cost_trace_label_label
554  (cost_labels: BitVectorTrie costlabel 16)
555   (trace_ends_flag: trace_ends_with_ret)
556    (start_status: Status) (final_status: Status)
557      (the_trace: trace_label_label (ASM_abstract_status cost_labels) trace_ends_flag
558        start_status final_status) on the_trace:
559         list (Σk:costlabel. ∃pc. lookup_opt … pc cost_labels = Some … k) ≝
560  match the_trace with
561  [ tll_base ends_flag initial final given_trace labelled_proof ⇒
562     let pc ≝ program_counter … initial in
563     let label ≝
564      match lookup_opt … pc cost_labels return λx. match x with [None ⇒ False | Some _ ⇒ True] → costlabel with
565      [ None ⇒ λabs. ⊥
566      | Some l ⇒ λ_. l ] labelled_proof in
567     (dp … label ?)::compute_cost_trace_any_label … given_trace
568  ]
569and compute_cost_trace_any_label
570  (cost_labels: BitVectorTrie costlabel 16)
571  (trace_ends_flag: trace_ends_with_ret)
572   (start_status: Status) (final_status: Status)
573     (the_trace: trace_any_label (ASM_abstract_status cost_labels) trace_ends_flag start_status final_status)
574       on the_trace: list (Σk:costlabel. ∃pc. lookup_opt … pc cost_labels = Some … k) ≝
575  match the_trace with
576  [ tal_base_not_return the_status _ _ _ _ ⇒ []
577  | tal_base_return the_status _ _ _ ⇒ []
578  | tal_step_call end_flag pre_fun_call start_fun_call after_fun_call final
579     _ _ _ call_trace final_trace ⇒
580      let call_cost_trace ≝ compute_cost_trace_label_return … call_trace in
581      let final_cost_trace ≝ compute_cost_trace_any_label cost_labels end_flag … final_trace in
582        call_cost_trace @ final_cost_trace
583  | tal_step_default end_flag status_pre status_init status_end _ tail_trace _ _ ⇒
584       compute_cost_trace_any_label cost_labels end_flag
585        status_init status_end tail_trace
586  ]
587and compute_cost_trace_label_return
588  (cost_labels: BitVectorTrie costlabel 16)
589  (start_status: Status) (final_status: Status)
590    (the_trace: trace_label_return (ASM_abstract_status cost_labels) start_status final_status)
591      on the_trace: list (Σk:costlabel. ∃pc. lookup_opt … pc cost_labels = Some … k) ≝
592  match the_trace with
593  [ tlr_base before after trace_to_lift ⇒ compute_cost_trace_label_label … trace_to_lift
594  | tlr_step initial labelled final labelled_trace ret_trace ⇒
595      let labelled_cost ≝ compute_cost_trace_label_label … labelled_trace in
596      let return_cost ≝ compute_cost_trace_label_return … ret_trace in
597        labelled_cost @ return_cost
598  ].
599 [ %{pc} whd in match label;  generalize in match labelled_proof; whd in ⊢ (% → ?);
600  cases (lookup_opt costlabel … pc cost_labels) normalize
601  [ #abs cases abs | // ]
602 | // ]
603qed.
604
605(* ??????????????????????? *)
606axiom block_cost_static_dynamic_ok:
607 ∀cost_labels: BitVectorTrie costlabel 16.
608 ∀trace_ends_flag.
609 ∀start_status: Status.
610 ∀final_status: Status.
611 ∀the_trace:
612  trace_label_label (ASM_abstract_status cost_labels) trace_ends_flag
613   start_status final_status.
614 let mem ≝ code_memory … start_status in
615 let pc ≝ program_counter … start_status in
616 let program_size ≝ 2^16 in
617  block_cost mem cost_labels pc program_size =
618  compute_paid_trace_label_label cost_labels trace_ends_flag
619   start_status final_status the_trace.
620
621(*
622(* To be moved elsewhere*)
623lemma le_S_n_m_to_le_n_m: ∀n,m. S n ≤ m → n ≤ m.
624 #n #m #H change with (pred (S n) ≤ m) @(transitive_le ? (S n)) //
625qed.
626*)
627
628include "arithmetics/bigops.ma".
629
630(* This shoudl go in bigops! *)
631theorem bigop_sum_rev: ∀k1,k2,p,B,nil.∀op:Aop B nil.∀f:nat→B.
632 \big[op,nil]_{i<k1+k2|p i} (f i) =
633 op \big[op,nil]_{i<k2|p (i+k1)} (f (i+k1)) \big[op,nil]_{i<k1|p i} (f i).
634 #k1 #k2 #p #B #nil #op #f >bigop_sum >commutative_plus @same_bigop #i @leb_elim normalize
635 [2,4: //
636 | #H1 #H2 <plus_minus_m_m //
637 | #H1 #H2 #H3 <plus_minus_m_m //]
638qed.
639
640(* This is taken by sigma_pi.ma that does not compile now *)
641definition natAop ≝ mk_Aop nat 0 plus (λa.refl ? a) (λn.sym_eq ??? (plus_n_O n))
642   (λa,b,c.sym_eq ??? (associative_plus a b c)).
643
644definition natACop ≝ mk_ACop nat 0 natAop commutative_plus.
645
646definition natDop ≝ mk_Dop nat 0 natACop times (λn.(sym_eq ??? (times_n_O n)))
647   distributive_times_plus.
648
649unification hint  0 ≔ ;
650   S ≟ mk_Aop nat 0 plus (λa.refl ? a) (λn.sym_eq ??? (plus_n_O n))
651   (λa,b,c.sym_eq ??? (associative_plus a b c))
652(* ---------------------------------------- *) ⊢
653   plus ≡ op ? ? S.
654
655unification hint  0 ≔ ;
656   S ≟ mk_ACop nat 0 (mk_Aop nat 0 plus (λa.refl ? a) (λn.sym_eq ??? (plus_n_O n))
657   (λa,b,c.sym_eq ??? (associative_plus a b c))) commutative_plus
658(* ---------------------------------------- *) ⊢
659   plus ≡ op ? ? S.
660   
661unification hint  0 ≔ ;
662   S ≟ natDop
663(* ---------------------------------------- *) ⊢
664   plus ≡ sum ? ? S.
665
666unification hint  0 ≔ ;
667   S ≟ natDop
668(* ---------------------------------------- *) ⊢
669   times ≡ prod ? ? S.
670
671notation "Σ_{ ident i < n } f"
672  with precedence 20
673for @{'bigop $n plus 0 (λ${ident i}.true) (λ${ident i}. $f)}.
674
675axiom code_memory_ro_label_label:
676 ∀cost_labels. ∀ends_flag.
677 ∀initial,final. trace_label_label (ASM_abstract_status cost_labels) ends_flag initial final →
678  code_memory … initial = code_memory … final.
679
680(*
681axiom code_memory_ro_label_return:
682 ∀cost_labels.
683 ∀initial,final. trace_label_return (ASM_abstract_status cost_labels) initial final →
684  code_memory … initial = code_memory … final.
685*)
686
687definition tech_cost_of_label0:
688 ∀cost_labels: BitVectorTrie costlabel 16.
689 ∀cost_map: identifier_map CostTag nat.
690 ∀codom_dom: (∀pc,k. lookup_opt … pc cost_labels = Some … k → present … cost_map k).
691 ∀ctrace:list (Σk:costlabel.∃pc. lookup_opt costlabel 16 pc cost_labels = Some ? k).
692 ∀i,p. present … cost_map (nth_safe ? i ctrace p).
693 #cost_labels #cost_map #codom_dom #ctrace #i #p
694 cases (nth_safe … i ctrace ?) normalize #id * #id_pc #K
695 lapply (codom_dom … K) #k_pres >(lookup_lookup_present … k_pres)
696 % #abs destruct (abs)
697qed.
698
699lemma ltb_rect:
700 ∀P:Type[0].∀n,m. (n < m → P) → (¬ n < m → P) → P.
701 #P #n #m lapply (refl … (ltb n m)) cases (ltb n m) in ⊢ (???% → %); #E #H1 #H2
702 [ @H1 @leb_true_to_le @E | @H2 @leb_false_to_not_le @E ]
703qed.
704
705lemma same_ltb_rect:
706 ∀P,n,m,H1,H2,n',m',H1',H2'.
707  ltb n m = ltb n' m' → (∀x,y. H1 x = H1' y) → (∀x,y. H2 x = H2' y) →
708   ltb_rect P n m H1 H2 =
709   ltb_rect P n' m' H1' H2'.
710 #P #n #m #H1 #H2 #n' #m' #H1' #H2' #E #K1 #K2 whd in ⊢ (??%?);
711 cut (∀xxx,yyy,xxx',yyy'.
712   match ltb n m
713   return λx:bool.
714           eq bool (ltb n m) x
715            → (lt n m → P) → (Not (lt n m) → P) → P
716    with
717    [ true ⇒
718        λE0:eq bool (ltb n m) true.
719         λH10:lt n m → P.
720          λH20:Not (lt n m) → P. H10 (xxx E0)
721    | false ⇒
722        λE0:eq bool (ltb n m) false.
723         λH10:lt n m → P.
724          λH20:Not (lt n m) → P. H20 (yyy E0)]
725    (refl … (ltb n m)) H1 H2 =
726   match ltb n' m'
727   return λx:bool.
728           eq bool (ltb n' m') x
729            → (lt n' m' → P) → (Not (lt n' m') → P) → P
730    with
731    [ true ⇒
732        λE0:eq bool (ltb n' m') true.
733         λH10:lt n' m' → P.
734          λH20:Not (lt n' m') → P. H10 (xxx' E0)
735    | false ⇒
736        λE0:eq bool (ltb n' m') false.
737         λH10:lt n' m' → P.
738          λH20:Not (lt n' m') → P. H20 (yyy' E0)]
739    (refl … (ltb n' m')) H1' H2'
740  ) [2: #X @X]
741 >E cases (ltb n' m') #xxx #yyy #xxx' #yyy' normalize
742 [ @K1 | @K2 ]
743qed.
744
745
746definition tech_cost_of_label:
747 ∀cost_labels: BitVectorTrie costlabel 16.
748 ∀cost_map: identifier_map CostTag nat.
749 ∀codom_dom: (∀pc,k. lookup_opt … pc cost_labels = Some … k → present … cost_map k).
750 list (Σk:costlabel.∃pc. lookup_opt costlabel 16 pc cost_labels = Some ? k) →
751 nat → nat
752≝ λcost_labels,cost_map,codom_dom,ctrace,i.
753 ltb_rect ? i (|ctrace|)
754 (λH. lookup_present ?? cost_map (nth_safe ? i ctrace H) ?)
755 (λ_.0).
756 @tech_cost_of_label0 @codom_dom
757qed.
758
759lemma shift_nth_safe:
760 ∀T,i,l2,l1,K1,K2.
761  nth_safe T i l1 K1 = nth_safe T (i+|l2|) (l2@l1) K2.
762 #T #i #l2 elim l2 normalize
763  [ #l1 #K1 <plus_n_O #K2 %
764  | #hd #tl #IH #l1 #K1 <plus_n_Sm #K2 change with (? < ?) in K1; change with (? < ?) in K2;
765    whd in ⊢ (???%); @IH ]
766qed.
767
768lemma tech_cost_of_label_shift:
769 ∀cost_labels,cost_map,codom_dom,l1,l2,i.
770  i < |l1| →
771   tech_cost_of_label cost_labels cost_map codom_dom l2 i =
772   tech_cost_of_label cost_labels cost_map codom_dom (l1@l2) (i+|l1|).
773 #cost_labels #cost_Map #codom_dom #l1 #l2 #i #H
774 cut (ltb i (|l2|) = ltb (i+|l1|) (|l1@l2|))
775 [ change with (leb ?? = leb ??); @leb_elim
776   [ #H1 change with (i < ?) in H1; >le_to_leb_true [//] change with (? < ?)
777     >append_length >commutative_plus @monotonic_lt_plus_r //
778   | #H1 change with (¬ i < ?) in H1; >not_le_to_leb_false [//]
779     >append_length >commutative_plus % #H2
780     change with (? < ?) in H2; @(absurd ?? H1) @(lt_plus_to_lt_r … H2) ]
781 | #E whd in match tech_cost_of_label; normalize nodelta
782 @same_ltb_rect [@E]
783 [ #K1 #K2 lapply (shift_nth_safe ? i l1 l2 K1 K2) #H check eq_f
784   lapply (eq_f ?? (lookup_present CostTag nat cost_Map) ?? H)
785
786   
787 
788  cut (decide_bool (ltb i (|l2|)) = decide_bool (ltb (i+(|l1|)) (|l1@l2|)))
789  whd in match tech_cost_of_label; normalize nodelta
790   
791
792let rec compute_max_trace_label_return_cost_ok_with_trace
793 (cost_labels: BitVectorTrie costlabel 16)
794 (cost_map: identifier_map CostTag nat)
795 (initial: Status) (final: Status)
796 (trace: trace_label_return (ASM_abstract_status cost_labels) initial final)
797 (codom_dom: (∀pc,k. lookup_opt … pc cost_labels = Some … k → present … cost_map k))
798 (dom_codom:(∀k. ∀k_pres:present … cost_map k. ∃pc. lookup_opt … pc cost_labels = Some … k →
799   block_cost (code_memory … initial) cost_labels pc 2^16 = lookup_present … k_pres))
800 on trace:
801  let ctrace ≝ compute_cost_trace_label_return … trace in
802  compute_max_trace_label_return_cost … trace =
803   Σ_{i < |ctrace|} (tech_cost_of_label cost_labels cost_map codom_dom ctrace i)
804    ≝ ?.
805lapply (refl … initial) cases trace in ⊢ (??%? → %);
806[ #sb #sa #tr #_ whd in ⊢ (let ctrace ≝ % in ??%?);
807| #si #sl #sf #tr1 #tr2 #E whd in ⊢ (let ctrace ≝ % in ??%?);
808  change with (let ctrace ≝ ? in ? = bigop (|? @ ?|) ?????)
809  >append_length in ⊢ (let ctrace ≝ ? in ???(?%?????));
810  change with (?=?) >bigop_sum_rev >commutative_plus @eq_f2
811  [ >compute_max_trace_label_return_cost_ok_with_trace
812    -compute_max_trace_label_return_cost_ok_with_trace     
813    [3: @cost_map
814    |2: @codom_dom
815    |4:lapply (code_memory_ro_label_label … tr1) >E #E2 <E2 @dom_codom]
816    @same_bigop [//] #i #H #_ -dom_codom
817    generalize in match (compute_cost_trace_label_return cost_labels sl sf tr2); #l1
818    generalize in match (compute_cost_trace_label_label cost_labels doesnt_end_with_ret si sl tr1);
819
820i < |l1| →
821tech_cost_of_label cost_labels cost_map codom_dom l1 i =
822tech_cost_of_label cost_labels cost_map codom_dom (l2@l1) (i+|l1|)
823
824
825     whd in ⊢ (??%%);
826  |
827  ]
828]
829
830lemma
831 compute_max_trace_any_label_cost cost_label trace_ends_flag start_status
832  final_status the_trace =
833 
834
835let rec compute_paid_trace_label_label_cost
836  (cost_labels: BitVectorTrie Byte 16)
837   (trace_ends_flag: trace_ends_with_ret)
838    (start_status: Status) (final_status: Status)
839      (the_trace: trace_label_label (ASM_abstract_status cost_labels) trace_ends_flag
840        start_status final_status) on the_trace: nat ≝
841  match the_trace with
842  [ tll_base _ _ _ given_trace _ ⇒
843      compute_paid_trace_any_label_cost … given_trace
844  ]
845and compute_paid_trace_any_label_cost
846  (cost_labels: BitVectorTrie Byte 16)
847  (trace_ends_flag: trace_ends_with_ret)
848   (start_status: Status) (final_status: Status)
849     (the_trace: trace_any_label (ASM_abstract_status cost_labels) trace_ends_flag start_status final_status)
850       on the_trace: nat ≝
851  match the_trace with
852  [ tal_base_not_return the_status _ _ _ _ ⇒ current_instruction_cost the_status
853  | tal_base_return the_status _ _ _ ⇒ current_instruction_cost the_status
854  | tal_step_call end_flag pre_fun_call start_fun_call after_fun_call final
855     _ _ _ call_trace final_trace ⇒
856      let current_instruction_cost ≝ current_instruction_cost pre_fun_call in
857      let final_trace_cost ≝ compute_paid_trace_any_label_cost cost_labels end_flag … final_trace in
858        current_instruction_cost + final_trace_cost
859  | tal_step_default end_flag status_pre status_init status_end _ tail_trace _ _ ⇒
860      let current_instruction_cost ≝ current_instruction_cost status_pre in
861      let tail_trace_cost ≝
862       compute_paid_trace_any_label_cost cost_labels end_flag
863        status_init status_end tail_trace
864      in
865        current_instruction_cost + tail_trace_cost
866  ]
867and compute_paid_trace_label_return_cost
868  (cost_labels: BitVectorTrie Byte 16)
869  (start_status: Status) (final_status: Status)
870    (the_trace: trace_label_return (ASM_abstract_status cost_labels) start_status final_status)
871      on the_trace: nat ≝
872  match the_trace with
873  [ tlr_base before after trace_to_lift ⇒ compute_paid_trace_label_label_cost … trace_to_lift
874  | tlr_step initial labelled final labelled_trace ret_trace ⇒
875      let labelled_cost ≝ compute_paid_trace_label_label_cost … labelled_trace in
876      let return_cost ≝ compute_paid_trace_label_return_cost … ret_trace in
877        labelled_cost + return_cost
878  ].
879
880let rec trace_lab_rec_cost' (p: trace_lab_ret) : nat.
881 | (call b bf tr af tl) as self ⇒
882    trace_lab_lab_cost_nocall self + trace_lab_ret_cost' tr +
883    trace_lab_rec_cost' tl
884
885theorem main_lemma:
886 ∀p. trace_lab_rec_cost p = trace_lab_rec_cost' p.
887
888axiom lemma1:
889 ∀p: simple_path.
890  traverse_cost_internal (pc (hd p)) … = trace_lab_lab_cost_nocall p.
891
892axiom lemma2:
893 ∀s,l,cost_map.
894  is_labelled l s →
895   traverse_cost_internal s = cost_map l.
896
897axiom main_statement:
898 ∀s.
899 ∀cost_map.
900 let p ≝ compute_simple_path0 s in
901 ∑ (cost_trace p) cost_map = trace_lab_rec_cost' p.
902
903axiom main_statement:
904 ∀s.
905 ∀cost_map.
906 let p ≝ compute_simple_path0 s in
907  execute' (path_length p) s = 〈s',τ〉 →
908   Timer s' - Timer s = ∑ τ cost_map.
Note: See TracBrowser for help on using the repository browser.