source: src/ASM/CostsProof.ma @ 1576

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

big changes to proofs, just two small cases remain and a few (dubious?) axioms

File size: 37.6 KB
Line 
1
2include "ASM/ASMCosts.ma".
3include "ASM/WellLabeled.ma".
4include "ASM/Status.ma".
5include "common/StructuredTraces.ma".
6
7(*
8definition next_instruction_is_labelled ≝
9  λcost_labels: BitVectorTrie Byte 16.
10  λs: Status.
11  let pc ≝ program_counter … (execute_1 s) in
12    match lookup_opt … pc cost_labels with
13    [ None ⇒ False
14    | _    ⇒ True
15    ].
16
17definition current_instruction_cost ≝
18  λs: Status. \snd (fetch (code_memory … s) (program_counter … s)).
19
20definition is_call_p ≝
21  λs.
22  match s with
23  [ ACALL _ ⇒ True
24  | LCALL _ ⇒ True
25  | JMP ⇒ True (* XXX: is function pointer call *)
26  | _ ⇒ False
27  ].
28
29definition next_instruction ≝
30  λs: Status.
31  let 〈instruction, ignore, ignore〉 ≝ fetch (code_memory … s) (program_counter … s) in
32    instruction.
33
34inductive trace_ends_with_ret: Type[0] ≝
35  | ends_with_ret: trace_ends_with_ret
36  | doesnt_end_with_ret: trace_ends_with_ret.
37
38definition next_instruction_is_labelled ≝
39  λcost_labels: BitVectorTrie Byte 16.
40  λs: Status.
41  let pc ≝ program_counter … (execute 1 s) in
42    match lookup_opt … pc cost_labels with
43    [ None ⇒ False
44    | _    ⇒ True
45    ].
46
47definition next_instruction_properly_relates_program_counters ≝
48  λbefore: Status.
49  λafter : Status.
50  let size ≝ current_instruction_cost before in
51  let pc_before ≝ program_counter … before in
52  let pc_after ≝ program_counter … after in
53  let sum ≝ \snd (half_add … pc_before (bitvector_of_nat … size)) in
54    sum = pc_after.
55
56definition current_instruction ≝
57  λs: Status.
58  let pc ≝ program_counter … s in
59  \fst (\fst (fetch … (code_memory … s) pc)).
60
61definition current_instruction_is_labelled ≝
62  λcost_labels: BitVectorTrie Byte 16.
63  λs: Status.
64  let pc ≝ program_counter … s in
65    match lookup_opt … pc cost_labels with
66    [ None ⇒ False
67    | _    ⇒ True
68    ].
69
70inductive trace_label_return (cost_labels: BitVectorTrie Byte 16): Status → Status → Type[0] ≝
71  | tlr_base:
72      ∀status_before: Status.
73      ∀status_after: Status.
74        trace_label_label cost_labels ends_with_ret status_before status_after →
75        trace_label_return cost_labels status_before status_after
76  | tlr_step:
77      ∀status_initial: Status.
78      ∀status_labelled: Status.
79      ∀status_final: Status.
80          trace_label_label cost_labels doesnt_end_with_ret status_initial status_labelled →
81            trace_label_return cost_labels status_labelled status_final →
82              trace_label_return cost_labels status_initial status_final
83with trace_label_label: trace_ends_with_ret → Status → Status → Type[0] ≝
84  | tll_base:
85      ∀ends_flag: trace_ends_with_ret.
86      ∀start_status: Status.
87      ∀end_status: Status.
88        trace_label_label_pre cost_labels ends_flag start_status end_status →
89        current_instruction_is_labelled cost_labels start_status →
90        trace_label_label cost_labels ends_flag start_status end_status
91with trace_label_label_pre: trace_ends_with_ret → Status → Status → Type[0] ≝
92  | tllp_base_not_return:
93      ∀start_status: Status.
94        let final_status ≝ execute 1 start_status in
95        current_instruction start_status ≠ (RealInstruction … (RET [[relative]])) →
96        ¬ (is_jump_p (current_instruction start_status)) →
97        current_instruction_is_labelled cost_labels final_status →
98          trace_label_label_pre cost_labels doesnt_end_with_ret start_status final_status
99  | tllp_base_return:
100      ∀start_status: Status.
101        let final_status ≝ execute 1 start_status in
102          current_instruction start_status = (RealInstruction … (RET [[relative]])) →
103            trace_label_label_pre cost_labels ends_with_ret start_status final_status
104  | tllp_base_jump:
105      ∀start_status: Status.
106        let final_status ≝ execute 1 start_status in
107          is_jump_p (current_instruction start_status) →
108            current_instruction_is_labelled cost_labels final_status →
109              trace_label_label_pre cost_labels doesnt_end_with_ret start_status final_status
110  | tllp_step_call:
111      ∀end_flag: trace_ends_with_ret.
112      ∀status_pre_fun_call: Status.
113      ∀status_after_fun_call: Status.
114      ∀status_final: Status.
115        let status_start_fun_call ≝ execute 1 status_pre_fun_call in
116          is_call_p (current_instruction status_pre_fun_call) →
117          next_instruction_properly_relates_program_counters status_pre_fun_call status_after_fun_call →
118          trace_label_return cost_labels status_start_fun_call status_after_fun_call →
119          trace_label_label_pre cost_labels end_flag status_after_fun_call status_final →
120            trace_label_label_pre cost_labels end_flag status_pre_fun_call status_final
121  | tllp_step_default:
122      ∀end_flag: trace_ends_with_ret.
123      ∀status_pre: Status.
124      ∀status_end: Status.
125        let status_init ≝ execute 1 status_pre in
126          trace_label_label_pre cost_labels end_flag status_init status_end →
127          ¬ (is_call_p (current_instruction status_pre)) →
128          ¬ (is_jump_p (current_instruction status_pre)) →
129          (current_instruction status_pre) ≠ (RealInstruction … (RET [[relative]])) →
130          ¬ (current_instruction_is_labelled cost_labels status_init) →
131            trace_label_label_pre cost_labels end_flag status_pre status_end.
132*)
133
134(* XXX: not us
135definition compute_simple_path0 (s:Status) (is_labelled s) (well_balanced s) (labelled_p p): trace_lab_ret ≝ ….
136
137lemma simple_path_ok:
138 ∀st: Status.∀H.
139 let p ≝ compute_simple_path0 st H in
140   ∀n.
141    nth_path n p = execute n st ∧
142     (execute' (path_length p) st = 〈st',τ〉 →
143      τ = cost_trace p)
144  ].
145*)
146
147let rec compute_max_trace_label_label_cost
148  (cost_labels: BitVectorTrie costlabel 16)
149   (trace_ends_flag: trace_ends_with_ret)
150    (start_status: Status) (final_status: Status)
151      (the_trace: trace_label_label (ASM_abstract_status cost_labels) trace_ends_flag
152        start_status final_status) on the_trace: nat ≝
153  match the_trace with
154  [ tll_base ends_flag initial final given_trace labelled_proof ⇒
155      compute_max_trace_any_label_cost … given_trace
156  ]
157and compute_max_trace_any_label_cost
158  (cost_labels: BitVectorTrie costlabel 16)
159  (trace_ends_flag: trace_ends_with_ret)
160   (start_status: Status) (final_status: Status)
161     (the_trace: trace_any_label (ASM_abstract_status cost_labels) trace_ends_flag start_status final_status)
162       on the_trace: nat ≝
163  match the_trace with
164  [ tal_base_not_return the_status _ _ _ _ ⇒ current_instruction_cost the_status
165  | tal_base_return the_status _ _ _ ⇒ current_instruction_cost the_status
166  | tal_step_call end_flag pre_fun_call start_fun_call after_fun_call final
167     _ _ _ call_trace final_trace ⇒
168      let current_instruction_cost ≝ current_instruction_cost pre_fun_call in
169      let call_trace_cost ≝ compute_max_trace_label_return_cost … call_trace in
170      let final_trace_cost ≝ compute_max_trace_any_label_cost cost_labels end_flag … final_trace in
171        call_trace_cost + current_instruction_cost + final_trace_cost
172  | tal_step_default end_flag status_pre status_init status_end _ tail_trace _ _ ⇒
173      let current_instruction_cost ≝ current_instruction_cost status_pre in
174      let tail_trace_cost ≝
175       compute_max_trace_any_label_cost cost_labels end_flag
176        status_init status_end tail_trace
177      in
178        current_instruction_cost + tail_trace_cost
179  ]
180and compute_max_trace_label_return_cost
181  (cost_labels: BitVectorTrie costlabel 16)
182  (start_status: Status) (final_status: Status)
183    (the_trace: trace_label_return (ASM_abstract_status cost_labels) start_status final_status)
184      on the_trace: nat ≝
185  match the_trace with
186  [ tlr_base before after trace_to_lift ⇒ compute_max_trace_label_label_cost … trace_to_lift
187  | tlr_step initial labelled final labelled_trace ret_trace ⇒
188      let labelled_cost ≝ compute_max_trace_label_label_cost … labelled_trace in
189      let return_cost ≝ compute_max_trace_label_return_cost … ret_trace in
190        labelled_cost + return_cost
191  ].
192
193(*Useless now?
194(* To be moved *)
195lemma pred_minus_1:
196  ∀m, n: nat.
197  ∀proof: n < m.
198    pred (m - n) = m - n - 1.
199  #m #n
200  cases m
201  [ #proof
202    cases(lt_to_not_zero … proof)
203  | #m' #proof
204    normalize in ⊢ (???%);
205    cases n
206    [ normalize //
207    | #n' normalize
208      cases(m' - n')
209      [ %
210      | #Sm_n'
211        normalize //
212      ]
213    ]
214  ]
215qed.
216
217lemma succ_m_plus_one:
218  ∀m: nat.
219    S m = m + 1.
220 //
221qed.*)
222
223include alias "arithmetics/nat.ma".
224
225(*
226lemma minus_m_n_minus_minus_plus_1:
227  ∀m, n: nat.
228  ∀proof: n < m.
229    m - n = (m - n - 1) + 1.
230 /3 by lt_plus_to_minus_r, plus_minus/
231qed.
232*)
233
234lemma plus_minus_rearrangement_1:
235  ∀m, n, o: nat.
236  ∀proof_n_m: n ≤ m.
237  ∀proof_m_o: m ≤ o.
238    (m - n) + (o - m) = o - n.
239  #m #n #o #H1 #H2
240  lapply (minus_to_plus … H1 (refl …)) #K1 >K1
241  lapply (minus_to_plus … H2 (refl …)) #K2 >K2
242  /2 by plus_minus/
243qed.
244
245lemma plus_minus_rearrangement_2:
246  ∀m, n, o: nat. n ≤ m → o ≤ n →
247    (m - n) + (n - o) = m - o.
248 /2 by plus_minus_rearrangement_1/
249qed.
250
251axiom clock_execute_1:
252  ∀s: Status.
253    clock … (execute_1 s) = current_instruction_cost s + clock … s.
254
255axiom plus_minus_minus:
256  ∀m, n, o: nat.
257    m - (n + o) = (m - n) - o.
258
259axiom plus_le_le:
260  ∀m, n, o: nat.
261    m + n ≤ o → n ≤ o.
262   
263let rec compute_max_trace_label_label_cost_is_ok
264  (cost_labels: BitVectorTrie costlabel 16)
265   (trace_ends_flag: trace_ends_with_ret)
266    (start_status: Status) (final_status: Status)
267      (the_trace: trace_label_label (ASM_abstract_status cost_labels) trace_ends_flag
268        start_status final_status) on the_trace:
269          And (compute_max_trace_label_label_cost cost_labels trace_ends_flag start_status final_status the_trace =
270            (clock … final_status) - (clock … start_status)) (clock … start_status ≤ clock … final_status) ≝ ?
271and compute_max_trace_any_label_cost_is_ok
272  (cost_labels: BitVectorTrie costlabel 16)
273  (trace_ends_flag: trace_ends_with_ret)
274   (start_status: Status) (final_status: Status)
275     (the_trace: trace_any_label (ASM_abstract_status cost_labels) trace_ends_flag start_status final_status)
276       on the_trace:
277         (compute_max_trace_any_label_cost cost_labels trace_ends_flag start_status final_status the_trace =
278           (clock … final_status) - (clock … start_status)) ∧ (clock … start_status ≤ clock … final_status) ≝ ?
279and compute_max_trace_label_return_cost_is_ok
280  (cost_labels: BitVectorTrie costlabel 16)
281  (start_status: Status) (final_status: Status)
282    (the_trace: trace_label_return (ASM_abstract_status cost_labels) start_status final_status)
283      on the_trace:
284        (compute_max_trace_label_return_cost cost_labels start_status final_status the_trace =
285          (clock … final_status) - (clock … start_status)) ∧ (clock … start_status ≤ clock … final_status) ≝ ?.
286  [1:
287    cases the_trace
288    #ends_flag #start_status #end_status #any_label_trace #is_costed
289    normalize @compute_max_trace_any_label_cost_is_ok
290  |2:
291    cases the_trace
292    [1:
293      #start_status #final_status #is_next #is_not_return #is_costed
294      change with (current_instruction_cost start_status) in ⊢ (?(??%?)?);
295      cases(is_next)
296      @conj
297      [1:
298        cases(execute_1 start_status)
299        #the_status #assm
300        whd in match eject; normalize nodelta
301        cases(assm)
302        #eq_hyp #le_hyp
303        >eq_hyp %
304      |2:
305        cases(execute_1 start_status)
306        #the_status #assm
307        whd in match eject; normalize nodelta
308        cases(assm)
309        #eq_hyp #le_hyp
310        assumption
311      ]
312    |2:
313      #start_status #final_status #is_next #is_return
314      change with (current_instruction_cost start_status) in ⊢ (?(??%?)?);
315      cases(is_next)
316      @conj
317      [1:
318        cases(execute_1 start_status)
319        #the_status #assm
320        whd in match eject; normalize nodelta
321        cases(assm)
322        #eq_hyp #le_hyp
323        >eq_hyp %
324      |2:
325        cases(execute_1 start_status)
326        #the_status #assm
327        whd in match eject; normalize nodelta
328        cases(assm)
329        #eq_hyp #le_hyp
330        assumption
331      ]
332    |3:
333      #end_flag #status_pre_fun_call #status_start_fun_call #status_after_fun_call
334      #status_final #is_next #is_call #is_after_return #call_trace #final_trace
335      change with (
336      let current_instruction_cost ≝ current_instruction_cost status_pre_fun_call in
337      let call_trace_cost ≝ compute_max_trace_label_return_cost … call_trace in
338      let final_trace_cost ≝ compute_max_trace_any_label_cost cost_labels end_flag … final_trace in
339        call_trace_cost + current_instruction_cost + final_trace_cost) in ⊢ (?(??%?)?);
340      normalize nodelta;
341      @conj
342      [1:
343        cases(compute_max_trace_label_return_cost_is_ok cost_labels status_start_fun_call
344          status_after_fun_call call_trace)
345        #trace_label_return_eq #trace_label_return_le
346        cases(compute_max_trace_any_label_cost_is_ok cost_labels end_flag status_after_fun_call
347          status_final final_trace)
348        #trace_any_label_eq #trace_any_label_le
349        >trace_label_return_eq >trace_any_label_eq
350        cases(is_next)
351        >(clock_execute_1 status_pre_fun_call) in match (clock … (execute_1 status_pre_fun_call));
352        >commutative_plus in match (
353          (current_instruction_cost status_pre_fun_call
354            + clock (BitVectorTrie Byte 16) status_pre_fun_call));
355        >plus_minus_minus
356        <(plus_minus_m_m (clock (BitVectorTrie Byte 16) status_after_fun_call
357  -clock (BitVectorTrie Byte 16) status_pre_fun_call) (current_instruction_cost status_pre_fun_call))
358        [1:
359          >plus_minus_rearrangement_1
360          [1:
361            %
362          |2:
363            assumption
364          |3:
365            generalize in match trace_label_return_le;
366            cases(is_next)
367            >(clock_execute_1 status_pre_fun_call)
368            @plus_le_le
369          ]
370        |2:
371          cases daemon (* XXX: todo *)
372        ]
373      |2:
374        cases(compute_max_trace_label_return_cost_is_ok cost_labels status_start_fun_call
375          status_after_fun_call call_trace)
376        #trace_label_return_eq cases(is_next)
377        >clock_execute_1
378        #trace_label_return_le
379        lapply (plus_le_le … trace_label_return_le)
380        #trace_label_return_le'
381        cases(compute_max_trace_any_label_cost_is_ok cost_labels end_flag status_after_fun_call
382          status_final final_trace)
383        #trace_any_label_eq #trace_any_label_le
384        @(transitive_le (clock … status_pre_fun_call) (clock … status_after_fun_call) (clock … status_final))
385        assumption
386      ]
387    |4:
388      #end_flag #status_pre #status_init #status_end #is_next
389      #trace_any_label #is_other #is_not_costed
390      change with (
391      let current_instruction_cost ≝ current_instruction_cost status_pre in
392      let tail_trace_cost ≝
393       compute_max_trace_any_label_cost cost_labels end_flag
394        status_init status_end trace_any_label
395      in
396        current_instruction_cost + tail_trace_cost) in ⊢ (?(??%?)?);
397      normalize nodelta;
398      @conj
399      [1:
400        cases(compute_max_trace_any_label_cost_is_ok cost_labels end_flag
401        status_init status_end trace_any_label)
402        #trace_any_label_eq #trace_any_label_le
403        >trace_any_label_eq
404        cases(is_next)
405        >commutative_plus
406        >clock_execute_1
407        >commutative_plus in match ((current_instruction_cost status_pre+clock (BitVectorTrie Byte 16) status_pre));
408        >plus_minus_minus
409        <plus_minus_m_m
410        [1: %
411        |2: cases daemon (* XXX: todo *)
412        ]
413      |2:
414        cases(compute_max_trace_any_label_cost_is_ok cost_labels end_flag
415        status_init status_end trace_any_label)
416        #trace_any_label_eq
417        cases(is_next)
418        >clock_execute_1
419        @plus_le_le
420      ]
421    ]
422  |3:
423    cases the_trace
424    [1:
425      #status_before #status_after #trace_to_lift
426      normalize @compute_max_trace_label_label_cost_is_ok
427    |2:
428      #status_initial #status_labelled #status_final #labelled_trace #ret_trace
429      normalize
430      cases(compute_max_trace_label_label_cost_is_ok cost_labels doesnt_end_with_ret status_initial status_labelled labelled_trace);
431      #label_label_trace_equality #label_label_trace_leq
432      cases(compute_max_trace_label_return_cost_is_ok cost_labels status_labelled status_final ret_trace);
433      #label_return_trace_equality #label_return_trace_leq
434      >label_label_trace_equality >label_return_trace_equality
435      @conj
436      [2: @(transitive_le (clock (BitVectorTrie (Vector bool 8) 16) status_initial)
437            (clock (BitVectorTrie Byte 16) status_labelled)
438            (clock (BitVectorTrie (Vector bool 8) 16) status_final))
439      |1: @plus_minus_rearrangement_1
440      ]
441      assumption
442    ]
443  ]
444qed.
445
446(* XXX: work below here: *)
447
448let rec compute_paid_trace_any_label
449  (cost_labels: BitVectorTrie costlabel 16)
450  (trace_ends_flag: trace_ends_with_ret)
451   (start_status: Status) (final_status: Status)
452     (the_trace: trace_any_label (ASM_abstract_status cost_labels) trace_ends_flag start_status final_status)
453       on the_trace: nat ≝
454  match the_trace with
455  [ tal_base_not_return the_status _ _ _ _ ⇒ current_instruction_cost the_status
456  | tal_base_return the_status _ _ _ ⇒ current_instruction_cost the_status
457  | tal_step_call end_flag pre_fun_call start_fun_call after_fun_call final
458     _ _ _ call_trace final_trace ⇒
459      let current_instruction_cost ≝ current_instruction_cost pre_fun_call in
460      let final_trace_cost ≝ compute_paid_trace_any_label cost_labels end_flag … final_trace in
461        current_instruction_cost + final_trace_cost
462  | tal_step_default end_flag status_pre status_init status_end _ tail_trace _ _ ⇒
463      let current_instruction_cost ≝ current_instruction_cost status_pre in
464      let tail_trace_cost ≝
465       compute_paid_trace_any_label cost_labels end_flag
466        status_init status_end tail_trace
467      in
468        current_instruction_cost + tail_trace_cost
469  ].
470
471definition compute_paid_trace_label_label ≝
472 λcost_labels: BitVectorTrie costlabel 16.
473  λtrace_ends_flag: trace_ends_with_ret.
474   λstart_status: Status.
475    λfinal_status: Status.
476     λthe_trace: trace_label_label (ASM_abstract_status cost_labels) trace_ends_flag
477      start_status final_status.
478  match the_trace with
479  [ tll_base ends_flag initial final given_trace labelled_proof ⇒
480      compute_paid_trace_any_label … given_trace
481  ].
482
483let rec compute_trace_label_label_cost_using_paid
484  (cost_labels: BitVectorTrie costlabel 16)
485   (trace_ends_flag: trace_ends_with_ret)
486    (start_status: Status) (final_status: Status)
487      (the_trace: trace_label_label (ASM_abstract_status cost_labels) trace_ends_flag
488        start_status final_status) on the_trace: nat ≝
489  match the_trace with
490  [ tll_base ends_flag initial final given_trace labelled_proof ⇒
491      compute_paid_trace_label_label cost_labels … the_trace +
492      compute_trace_any_label_cost_using_paid … given_trace
493  ]
494and compute_trace_any_label_cost_using_paid
495  (cost_labels: BitVectorTrie costlabel 16)
496  (trace_ends_flag: trace_ends_with_ret)
497   (start_status: Status) (final_status: Status)
498     (the_trace: trace_any_label (ASM_abstract_status cost_labels) trace_ends_flag start_status final_status)
499       on the_trace: nat ≝
500  match the_trace with
501  [ tal_base_not_return the_status _ _ _ _ ⇒ 0
502  | tal_base_return the_status _ _ _ ⇒ 0
503  | tal_step_call end_flag pre_fun_call start_fun_call after_fun_call final
504     _ _ _ call_trace final_trace ⇒
505      let call_trace_cost ≝ compute_trace_label_return_cost_using_paid … call_trace in
506      let final_trace_cost ≝ compute_trace_any_label_cost_using_paid cost_labels end_flag … final_trace in
507        call_trace_cost + final_trace_cost
508  | tal_step_default end_flag status_pre status_init status_end _ tail_trace _ _ ⇒
509     compute_trace_any_label_cost_using_paid cost_labels end_flag
510      status_init status_end tail_trace
511  ]
512and compute_trace_label_return_cost_using_paid
513  (cost_labels: BitVectorTrie costlabel 16)
514  (start_status: Status) (final_status: Status)
515    (the_trace: trace_label_return (ASM_abstract_status cost_labels) start_status final_status)
516      on the_trace: nat ≝
517  match the_trace with
518  [ tlr_base before after trace_to_lift ⇒ compute_trace_label_label_cost_using_paid … trace_to_lift
519  | tlr_step initial labelled final labelled_trace ret_trace ⇒
520      let labelled_cost ≝ compute_trace_label_label_cost_using_paid … labelled_trace in
521      let return_cost ≝ compute_trace_label_return_cost_using_paid … ret_trace in
522        labelled_cost + return_cost
523  ].
524
525let rec compute_trace_label_label_cost_using_paid_ok
526  (cost_labels: BitVectorTrie costlabel 16)
527   (trace_ends_flag: trace_ends_with_ret)
528    (start_status: Status) (final_status: Status)
529      (the_trace: trace_label_label (ASM_abstract_status cost_labels) trace_ends_flag
530        start_status final_status) on the_trace:
531 compute_trace_label_label_cost_using_paid cost_labels … the_trace =
532 compute_max_trace_label_label_cost … the_trace ≝ ?
533and compute_trace_any_label_cost_using_paid_ok
534  (cost_labels: BitVectorTrie costlabel 16)
535  (trace_ends_flag: trace_ends_with_ret)
536   (start_status: Status) (final_status: Status)
537     (the_trace: trace_any_label (ASM_abstract_status cost_labels)
538      trace_ends_flag start_status final_status) on the_trace:     
539  compute_paid_trace_any_label cost_labels trace_ends_flag … the_trace
540  +compute_trace_any_label_cost_using_paid cost_labels trace_ends_flag … the_trace
541  =compute_max_trace_any_label_cost cost_labels trace_ends_flag … the_trace ≝ ?
542and compute_trace_label_return_cost_using_paid_ok
543  (cost_labels: BitVectorTrie costlabel 16)
544  (start_status: Status) (final_status: Status)
545    (the_trace: trace_label_return (ASM_abstract_status cost_labels)
546     start_status final_status) on the_trace:
547 compute_trace_label_return_cost_using_paid cost_labels … the_trace =
548 compute_max_trace_label_return_cost cost_labels … the_trace ≝ ?.
549[ cases the_trace #endsf #ss #es #tr #H normalize
550  @compute_trace_any_label_cost_using_paid_ok
551| cases the_trace
552  [ #ss #fs #H1 #H2 #H3 whd in ⊢ (??(?%%)%); <plus_n_O %
553  | #ss #fs #H1 #H2 whd in ⊢ (??(?%%)%); <plus_n_O %
554  | #ef #spfc #ssfc #safc #sf #H1 #H2 #H3 #tr1 #tr2 whd in ⊢ (??(?%%)%);
555    <compute_trace_any_label_cost_using_paid_ok
556    <compute_trace_label_return_cost_using_paid_ok
557    -compute_trace_label_label_cost_using_paid_ok
558    -compute_trace_label_return_cost_using_paid_ok
559    -compute_trace_any_label_cost_using_paid_ok
560    >commutative_plus in ⊢ (???(?%?));
561    >commutative_plus in ⊢ (??(??%)?);
562    >associative_plus >associative_plus in ⊢ (???%); @eq_f2 try %
563    <associative_plus <commutative_plus %
564  | #ef #sp #si #se #H1 #tr #H2 #H3 whd in ⊢ (??(?%%)%); >associative_plus @eq_f2
565    [ % | @compute_trace_any_label_cost_using_paid_ok ]
566  ]
567| cases the_trace
568  [ #sb #sa #tr normalize @compute_trace_label_label_cost_using_paid_ok
569  | #si #sl #sf #tr1 #tr2 normalize @eq_f2
570    [ @compute_trace_label_label_cost_using_paid_ok
571    | @compute_trace_label_return_cost_using_paid_ok ]]]
572qed.
573
574(*
575let rec compute_paid_trace_label_return
576  (cost_labels: BitVectorTrie costlabel 16)
577  (start_status: Status) (final_status: Status)
578    (the_trace: trace_label_return (ASM_abstract_status cost_labels) start_status final_status)
579      on the_trace: nat ≝
580 match the_trace with
581  [ tlr_base before after trace_to_lift ⇒ compute_paid_trace_label_label … trace_to_lift
582  | tlr_step initial labelled final labelled_trace ret_trace ⇒
583      let labelled_cost ≝ compute_paid_trace_label_label … labelled_trace in
584      let return_cost ≝ compute_paid_trace_label_return … ret_trace in
585        labelled_cost + return_cost
586  ].
587*)
588
589let rec compute_cost_trace_label_label
590  (cost_labels: BitVectorTrie costlabel 16)
591   (trace_ends_flag: trace_ends_with_ret)
592    (start_status: Status) (final_status: Status)
593      (the_trace: trace_label_label (ASM_abstract_status cost_labels) trace_ends_flag
594        start_status final_status) on the_trace:
595         list (Σk:costlabel. ∃pc. lookup_opt … pc cost_labels = Some … k) ≝
596  match the_trace with
597  [ tll_base ends_flag initial final given_trace labelled_proof ⇒
598     let pc ≝ program_counter … initial in
599     let label ≝
600      match lookup_opt … pc cost_labels return λx. match x with [None ⇒ False | Some _ ⇒ True] → costlabel with
601      [ None ⇒ λabs. ⊥
602      | Some l ⇒ λ_. l ] labelled_proof in
603     (dp … label ?)::compute_cost_trace_any_label … given_trace
604  ]
605and compute_cost_trace_any_label
606  (cost_labels: BitVectorTrie costlabel 16)
607  (trace_ends_flag: trace_ends_with_ret)
608   (start_status: Status) (final_status: Status)
609     (the_trace: trace_any_label (ASM_abstract_status cost_labels) trace_ends_flag start_status final_status)
610       on the_trace: list (Σk:costlabel. ∃pc. lookup_opt … pc cost_labels = Some … k) ≝
611  match the_trace with
612  [ tal_base_not_return the_status _ _ _ _ ⇒ []
613  | tal_base_return the_status _ _ _ ⇒ []
614  | tal_step_call end_flag pre_fun_call start_fun_call after_fun_call final
615     _ _ _ call_trace final_trace ⇒
616      let call_cost_trace ≝ compute_cost_trace_label_return … call_trace in
617      let final_cost_trace ≝ compute_cost_trace_any_label cost_labels end_flag … final_trace in
618        call_cost_trace @ final_cost_trace
619  | tal_step_default end_flag status_pre status_init status_end _ tail_trace _ _ ⇒
620       compute_cost_trace_any_label cost_labels end_flag
621        status_init status_end tail_trace
622  ]
623and compute_cost_trace_label_return
624  (cost_labels: BitVectorTrie costlabel 16)
625  (start_status: Status) (final_status: Status)
626    (the_trace: trace_label_return (ASM_abstract_status cost_labels) start_status final_status)
627      on the_trace: list (Σk:costlabel. ∃pc. lookup_opt … pc cost_labels = Some … k) ≝
628  match the_trace with
629  [ tlr_base before after trace_to_lift ⇒ compute_cost_trace_label_label … trace_to_lift
630  | tlr_step initial labelled final labelled_trace ret_trace ⇒
631      let labelled_cost ≝ compute_cost_trace_label_label … labelled_trace in
632      let return_cost ≝ compute_cost_trace_label_return … ret_trace in
633        labelled_cost @ return_cost
634  ].
635 [ %{pc} whd in match label;  generalize in match labelled_proof; whd in ⊢ (% → ?);
636  cases (lookup_opt costlabel … pc cost_labels) normalize
637  [ #abs cases abs | // ]
638 | // ]
639qed.
640
641(* ??????????????????????? *)
642axiom block_cost_static_dynamic_ok:
643 ∀cost_labels: BitVectorTrie costlabel 16.
644 ∀trace_ends_flag.
645 ∀start_status: Status.
646 ∀final_status: Status.
647 ∀the_trace:
648  trace_label_label (ASM_abstract_status cost_labels) trace_ends_flag
649   start_status final_status.
650 let mem ≝ code_memory … start_status in
651 let pc ≝ program_counter … start_status in
652 let program_size ≝ 2^16 in
653  block_cost mem cost_labels pc program_size =
654  compute_paid_trace_label_label cost_labels trace_ends_flag
655   start_status final_status the_trace.
656
657(*
658(* To be moved elsewhere*)
659lemma le_S_n_m_to_le_n_m: ∀n,m. S n ≤ m → n ≤ m.
660 #n #m #H change with (pred (S n) ≤ m) @(transitive_le ? (S n)) //
661qed.
662*)
663
664include "arithmetics/bigops.ma".
665
666(* This shoudl go in bigops! *)
667theorem bigop_sum_rev: ∀k1,k2,p,B,nil.∀op:Aop B nil.∀f:nat→B.
668 \big[op,nil]_{i<k1+k2|p i} (f i) =
669 op \big[op,nil]_{i<k2|p (i+k1)} (f (i+k1)) \big[op,nil]_{i<k1|p i} (f i).
670 #k1 #k2 #p #B #nil #op #f >bigop_sum >commutative_plus @same_bigop #i @leb_elim normalize
671 [2,4: //
672 | #H1 #H2 <plus_minus_m_m //
673 | #H1 #H2 #H3 <plus_minus_m_m //]
674qed.
675
676(* This is taken by sigma_pi.ma that does not compile now *)
677definition natAop ≝ mk_Aop nat 0 plus (λa.refl ? a) (λn.sym_eq ??? (plus_n_O n))
678   (λa,b,c.sym_eq ??? (associative_plus a b c)).
679
680definition natACop ≝ mk_ACop nat 0 natAop commutative_plus.
681
682definition natDop ≝ mk_Dop nat 0 natACop times (λn.(sym_eq ??? (times_n_O n)))
683   distributive_times_plus.
684
685unification hint  0 ≔ ;
686   S ≟ mk_Aop nat 0 plus (λa.refl ? a) (λn.sym_eq ??? (plus_n_O n))
687   (λa,b,c.sym_eq ??? (associative_plus a b c))
688(* ---------------------------------------- *) ⊢
689   plus ≡ op ? ? S.
690
691unification hint  0 ≔ ;
692   S ≟ mk_ACop nat 0 (mk_Aop nat 0 plus (λa.refl ? a) (λn.sym_eq ??? (plus_n_O n))
693   (λa,b,c.sym_eq ??? (associative_plus a b c))) commutative_plus
694(* ---------------------------------------- *) ⊢
695   plus ≡ op ? ? S.
696   
697unification hint  0 ≔ ;
698   S ≟ natDop
699(* ---------------------------------------- *) ⊢
700   plus ≡ sum ? ? S.
701
702unification hint  0 ≔ ;
703   S ≟ natDop
704(* ---------------------------------------- *) ⊢
705   times ≡ prod ? ? S.
706
707notation "Σ_{ ident i < n } f"
708  with precedence 20
709for @{'bigop $n plus 0 (λ${ident i}.true) (λ${ident i}. $f)}.
710
711axiom code_memory_ro_label_label:
712 ∀cost_labels. ∀ends_flag.
713 ∀initial,final. trace_label_label (ASM_abstract_status cost_labels) ends_flag initial final →
714  code_memory … initial = code_memory … final.
715
716(*
717axiom code_memory_ro_label_return:
718 ∀cost_labels.
719 ∀initial,final. trace_label_return (ASM_abstract_status cost_labels) initial final →
720  code_memory … initial = code_memory … final.
721*)
722
723definition tech_cost_of_label0:
724 ∀cost_labels: BitVectorTrie costlabel 16.
725 ∀cost_map: identifier_map CostTag nat.
726 ∀codom_dom: (∀pc,k. lookup_opt … pc cost_labels = Some … k → present … cost_map k).
727 ∀ctrace:list (Σk:costlabel.∃pc. lookup_opt costlabel 16 pc cost_labels = Some ? k).
728 ∀i,p. present … cost_map (nth_safe ? i ctrace p).
729 #cost_labels #cost_map #codom_dom #ctrace #i #p
730 cases (nth_safe … i ctrace ?) normalize #id * #id_pc #K
731 lapply (codom_dom … K) #k_pres >(lookup_lookup_present … k_pres)
732 % #abs destruct (abs)
733qed.
734
735lemma ltb_rect:
736 ∀P:Type[0].∀n,m. (n < m → P) → (¬ n < m → P) → P.
737 #P #n #m lapply (refl … (ltb n m)) cases (ltb n m) in ⊢ (???% → %); #E #H1 #H2
738 [ @H1 @leb_true_to_le @E | @H2 @leb_false_to_not_le @E ]
739qed.
740
741lemma same_ltb_rect:
742 ∀P,n,m,H1,H2,n',m',H1',H2'.
743  ltb n m = ltb n' m' → (∀x,y. H1 x = H1' y) → (∀x,y. H2 x = H2' y) →
744   ltb_rect P n m H1 H2 =
745   ltb_rect P n' m' H1' H2'.
746 #P #n #m #H1 #H2 #n' #m' #H1' #H2' #E #K1 #K2 whd in ⊢ (??%?);
747 cut (∀xxx,yyy,xxx',yyy'.
748   match ltb n m
749   return λx:bool.
750           eq bool (ltb n m) x
751            → (lt n m → P) → (Not (lt n m) → P) → P
752    with
753    [ true ⇒
754        λE0:eq bool (ltb n m) true.
755         λH10:lt n m → P.
756          λH20:Not (lt n m) → P. H10 (xxx E0)
757    | false ⇒
758        λE0:eq bool (ltb n m) false.
759         λH10:lt n m → P.
760          λH20:Not (lt n m) → P. H20 (yyy E0)]
761    (refl … (ltb n m)) H1 H2 =
762   match ltb n' m'
763   return λx:bool.
764           eq bool (ltb n' m') x
765            → (lt n' m' → P) → (Not (lt n' m') → P) → P
766    with
767    [ true ⇒
768        λE0:eq bool (ltb n' m') true.
769         λH10:lt n' m' → P.
770          λH20:Not (lt n' m') → P. H10 (xxx' E0)
771    | false ⇒
772        λE0:eq bool (ltb n' m') false.
773         λH10:lt n' m' → P.
774          λH20:Not (lt n' m') → P. H20 (yyy' E0)]
775    (refl … (ltb n' m')) H1' H2'
776  ) [2: #X @X]
777 >E cases (ltb n' m') #xxx #yyy #xxx' #yyy' normalize
778 [ @K1 | @K2 ]
779qed.
780
781
782definition tech_cost_of_label:
783 ∀cost_labels: BitVectorTrie costlabel 16.
784 ∀cost_map: identifier_map CostTag nat.
785 ∀codom_dom: (∀pc,k. lookup_opt … pc cost_labels = Some … k → present … cost_map k).
786 list (Σk:costlabel.∃pc. lookup_opt costlabel 16 pc cost_labels = Some ? k) →
787 nat → nat
788≝ λcost_labels,cost_map,codom_dom,ctrace,i.
789 ltb_rect ? i (|ctrace|)
790 (λH. lookup_present ?? cost_map (nth_safe ? i ctrace H) ?)
791 (λ_.0).
792 @tech_cost_of_label0 @codom_dom
793qed.
794
795lemma shift_nth_safe:
796 ∀T,i,l2,l1,K1,K2.
797  nth_safe T i l1 K1 = nth_safe T (i+|l2|) (l2@l1) K2.
798 #T #i #l2 elim l2 normalize
799  [ #l1 #K1 <plus_n_O #K2 %
800  | #hd #tl #IH #l1 #K1 <plus_n_Sm #K2 change with (? < ?) in K1; change with (? < ?) in K2;
801    whd in ⊢ (???%); @IH ]
802qed.
803
804lemma tech_cost_of_label_shift:
805 ∀cost_labels,cost_map,codom_dom,l1,l2,i.
806  i < |l1| →
807   tech_cost_of_label cost_labels cost_map codom_dom l2 i =
808   tech_cost_of_label cost_labels cost_map codom_dom (l1@l2) (i+|l1|).
809 #cost_labels #cost_Map #codom_dom #l1 #l2 #i #H
810 cut (ltb i (|l2|) = ltb (i+|l1|) (|l1@l2|))
811 [ change with (leb ?? = leb ??); @leb_elim
812   [ #H1 change with (i < ?) in H1; >le_to_leb_true [//] change with (? < ?)
813     >append_length >commutative_plus @monotonic_lt_plus_r //
814   | #H1 change with (¬ i < ?) in H1; >not_le_to_leb_false [//]
815     >append_length >commutative_plus % #H2
816     change with (? < ?) in H2; @(absurd ?? H1) @(lt_plus_to_lt_r … H2) ]
817 | #E whd in match tech_cost_of_label; normalize nodelta
818 @same_ltb_rect [@E]
819 [ #K1 #K2 lapply (shift_nth_safe ? i l1 l2 K1 K2) #H check eq_f
820   lapply (eq_f ?? (lookup_present CostTag nat cost_Map) ?? H)
821
822   
823 
824  cut (decide_bool (ltb i (|l2|)) = decide_bool (ltb (i+(|l1|)) (|l1@l2|)))
825  whd in match tech_cost_of_label; normalize nodelta
826   
827
828let rec compute_max_trace_label_return_cost_ok_with_trace
829 (cost_labels: BitVectorTrie costlabel 16)
830 (cost_map: identifier_map CostTag nat)
831 (initial: Status) (final: Status)
832 (trace: trace_label_return (ASM_abstract_status cost_labels) initial final)
833 (codom_dom: (∀pc,k. lookup_opt … pc cost_labels = Some … k → present … cost_map k))
834 (dom_codom:(∀k. ∀k_pres:present … cost_map k. ∃pc. lookup_opt … pc cost_labels = Some … k →
835   block_cost (code_memory … initial) cost_labels pc 2^16 = lookup_present … k_pres))
836 on trace:
837  let ctrace ≝ compute_cost_trace_label_return … trace in
838  compute_max_trace_label_return_cost … trace =
839   Σ_{i < |ctrace|} (tech_cost_of_label cost_labels cost_map codom_dom ctrace i)
840    ≝ ?.
841lapply (refl … initial) cases trace in ⊢ (??%? → %);
842[ #sb #sa #tr #_ whd in ⊢ (let ctrace ≝ % in ??%?);
843| #si #sl #sf #tr1 #tr2 #E whd in ⊢ (let ctrace ≝ % in ??%?);
844  change with (let ctrace ≝ ? in ? = bigop (|? @ ?|) ?????)
845  >append_length in ⊢ (let ctrace ≝ ? in ???(?%?????));
846  change with (?=?) >bigop_sum_rev >commutative_plus @eq_f2
847  [ >compute_max_trace_label_return_cost_ok_with_trace
848    -compute_max_trace_label_return_cost_ok_with_trace     
849    [3: @cost_map
850    |2: @codom_dom
851    |4:lapply (code_memory_ro_label_label … tr1) >E #E2 <E2 @dom_codom]
852    @same_bigop [//] #i #H #_ -dom_codom
853    generalize in match (compute_cost_trace_label_return cost_labels sl sf tr2); #l1
854    generalize in match (compute_cost_trace_label_label cost_labels doesnt_end_with_ret si sl tr1);
855
856i < |l1| →
857tech_cost_of_label cost_labels cost_map codom_dom l1 i =
858tech_cost_of_label cost_labels cost_map codom_dom (l2@l1) (i+|l1|)
859
860
861     whd in ⊢ (??%%);
862  |
863  ]
864]
865
866lemma
867 compute_max_trace_any_label_cost cost_label trace_ends_flag start_status
868  final_status the_trace =
869 
870
871let rec compute_paid_trace_label_label_cost
872  (cost_labels: BitVectorTrie Byte 16)
873   (trace_ends_flag: trace_ends_with_ret)
874    (start_status: Status) (final_status: Status)
875      (the_trace: trace_label_label (ASM_abstract_status cost_labels) trace_ends_flag
876        start_status final_status) on the_trace: nat ≝
877  match the_trace with
878  [ tll_base _ _ _ given_trace _ ⇒
879      compute_paid_trace_any_label_cost … given_trace
880  ]
881and compute_paid_trace_any_label_cost
882  (cost_labels: BitVectorTrie Byte 16)
883  (trace_ends_flag: trace_ends_with_ret)
884   (start_status: Status) (final_status: Status)
885     (the_trace: trace_any_label (ASM_abstract_status cost_labels) trace_ends_flag start_status final_status)
886       on the_trace: nat ≝
887  match the_trace with
888  [ tal_base_not_return the_status _ _ _ _ ⇒ current_instruction_cost the_status
889  | tal_base_return the_status _ _ _ ⇒ current_instruction_cost the_status
890  | tal_step_call end_flag pre_fun_call start_fun_call after_fun_call final
891     _ _ _ call_trace final_trace ⇒
892      let current_instruction_cost ≝ current_instruction_cost pre_fun_call in
893      let final_trace_cost ≝ compute_paid_trace_any_label_cost cost_labels end_flag … final_trace in
894        current_instruction_cost + final_trace_cost
895  | tal_step_default end_flag status_pre status_init status_end _ tail_trace _ _ ⇒
896      let current_instruction_cost ≝ current_instruction_cost status_pre in
897      let tail_trace_cost ≝
898       compute_paid_trace_any_label_cost cost_labels end_flag
899        status_init status_end tail_trace
900      in
901        current_instruction_cost + tail_trace_cost
902  ]
903and compute_paid_trace_label_return_cost
904  (cost_labels: BitVectorTrie Byte 16)
905  (start_status: Status) (final_status: Status)
906    (the_trace: trace_label_return (ASM_abstract_status cost_labels) start_status final_status)
907      on the_trace: nat ≝
908  match the_trace with
909  [ tlr_base before after trace_to_lift ⇒ compute_paid_trace_label_label_cost … trace_to_lift
910  | tlr_step initial labelled final labelled_trace ret_trace ⇒
911      let labelled_cost ≝ compute_paid_trace_label_label_cost … labelled_trace in
912      let return_cost ≝ compute_paid_trace_label_return_cost … ret_trace in
913        labelled_cost + return_cost
914  ].
915
916let rec trace_lab_rec_cost' (p: trace_lab_ret) : nat.
917 | (call b bf tr af tl) as self ⇒
918    trace_lab_lab_cost_nocall self + trace_lab_ret_cost' tr +
919    trace_lab_rec_cost' tl
920
921theorem main_lemma:
922 ∀p. trace_lab_rec_cost p = trace_lab_rec_cost' p.
923
924axiom lemma1:
925 ∀p: simple_path.
926  traverse_cost_internal (pc (hd p)) … = trace_lab_lab_cost_nocall p.
927
928axiom lemma2:
929 ∀s,l,cost_map.
930  is_labelled l s →
931   traverse_cost_internal s = cost_map l.
932
933axiom main_statement:
934 ∀s.
935 ∀cost_map.
936 let p ≝ compute_simple_path0 s in
937 ∑ (cost_trace p) cost_map = trace_lab_rec_cost' p.
938
939axiom main_statement:
940 ∀s.
941 ∀cost_map.
942 let p ≝ compute_simple_path0 s in
943  execute' (path_length p) s = 〈s',τ〉 →
944   Timer s' - Timer s = ∑ τ cost_map.
Note: See TracBrowser for help on using the repository browser.