source: src/ASM/CostsProof.ma @ 1648

Last change on this file since 1648 was 1648, checked in by mulligan, 7 years ago

new version of utilities/monad.ma with typecheck command comented out

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