source: src/ASM/CostsProof.ma @ 1579

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

Finished proof with simpler statement, making everything a lot nicer

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