source: src/ASM/CostsProof.ma @ 3056

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

code_memory added to labelled_object_code to avoid recomputing it every time.
This gives a major speed up in the semantics of the extracted code.

File size: 31.2 KB
RevLine 
[1898]1include "ASM/ASMCostsSplit.ma".
[1499]2include "ASM/WellLabeled.ma".
3include "ASM/Status.ma".
[1544]4include "common/StructuredTraces.ma".
[1619]5include "arithmetics/bigops.ma".
[1898]6
[1619]7include alias "arithmetics/nat.ma".
8include alias "basics/logic.ma".
[1498]9
[1506]10let rec compute_max_trace_label_label_cost
[2907]11  (prog: labelled_object_code)
[1544]12   (trace_ends_flag: trace_ends_with_ret)
[2999]13    (start_status: Status (cm prog))
14    (final_status: Status (cm prog))
[2907]15      (the_trace: trace_label_label (OC_abstract_status prog) trace_ends_flag
[1544]16        start_status final_status) on the_trace: nat ≝
[1506]17  match the_trace with
18  [ tll_base ends_flag initial final given_trace labelled_proof ⇒
[1544]19      compute_max_trace_any_label_cost … given_trace
[1506]20  ]
[1544]21and compute_max_trace_any_label_cost
[2907]22  (prog: labelled_object_code)
[1544]23  (trace_ends_flag: trace_ends_with_ret)
[2999]24   (start_status: Status (cm prog))
25   (final_status: Status (cm prog))
[2907]26     (the_trace: trace_any_label (OC_abstract_status prog) trace_ends_flag start_status final_status)
[1544]27       on the_trace: nat ≝
[1506]28  match the_trace with
[2907]29  [ tal_base_not_return the_status _ _ _ _ ⇒ current_instruction_cost … the_status
30  | tal_base_return the_status _ _ _ ⇒ current_instruction_cost … the_status
[1692]31  | tal_base_call pre_fun_call start_fun_call final _ _ _ call_trace _ ⇒
[2907]32      let current_instruction_cost ≝ current_instruction_cost … pre_fun_call in
[1692]33      let call_trace_cost ≝ compute_max_trace_label_return_cost … call_trace in
34        call_trace_cost + current_instruction_cost
[2656]35  | tal_base_tailcall pre_fun_call start_fun_call final _ _ call_trace ⇒
[2907]36      let current_instruction_cost ≝ current_instruction_cost … pre_fun_call in
[2656]37      let call_trace_cost ≝ compute_max_trace_label_return_cost … call_trace in
38        call_trace_cost + current_instruction_cost
[1544]39  | tal_step_call end_flag pre_fun_call start_fun_call after_fun_call final
[1692]40     _ _ _ call_trace _ final_trace ⇒
[2907]41      let current_instruction_cost ≝ current_instruction_cost … pre_fun_call in
[1544]42      let call_trace_cost ≝ compute_max_trace_label_return_cost … call_trace in
[2907]43      let final_trace_cost ≝ compute_max_trace_any_label_cost prog end_flag … final_trace in
[1506]44        call_trace_cost + current_instruction_cost + final_trace_cost
[1544]45  | tal_step_default end_flag status_pre status_init status_end _ tail_trace _ _ ⇒
[2907]46      let current_instruction_cost ≝ current_instruction_cost … status_pre in
[1544]47      let tail_trace_cost ≝
[2907]48       compute_max_trace_any_label_cost prog end_flag
[1544]49        status_init status_end tail_trace
50      in
[1506]51        current_instruction_cost + tail_trace_cost
52  ]
53and compute_max_trace_label_return_cost
[2907]54  (prog: labelled_object_code)
[2999]55  (start_status: Status (cm prog))
56  (final_status: Status (cm prog))
[2907]57    (the_trace: trace_label_return (OC_abstract_status prog) start_status final_status)
[1506]58      on the_trace: nat ≝
59  match the_trace with
60  [ tlr_base before after trace_to_lift ⇒ compute_max_trace_label_label_cost … trace_to_lift
61  | tlr_step initial labelled final labelled_trace ret_trace ⇒
62      let labelled_cost ≝ compute_max_trace_label_label_cost … labelled_trace in
63      let return_cost ≝ compute_max_trace_label_return_cost … ret_trace in
64        labelled_cost + return_cost
65  ].
[1500]66
[1544]67include alias "arithmetics/nat.ma".
68
[1579]69let rec compute_max_trace_label_label_cost_is_ok
[2907]70  (prog: labelled_object_code)
[1579]71   (trace_ends_flag: trace_ends_with_ret)
[2999]72    (start_status: Status (cm prog))
73    (final_status: Status (cm prog))
[2907]74      (the_trace: trace_label_label (OC_abstract_status prog) trace_ends_flag
[1579]75        start_status final_status) on the_trace:
[2999]76          clock … (cm prog) … final_status = (compute_max_trace_label_label_cost prog trace_ends_flag start_status final_status the_trace) + (clock … (cm prog) … start_status) ≝ ?
[1579]77and compute_max_trace_any_label_cost_is_ok
[2907]78  (prog: labelled_object_code)
[1579]79  (trace_ends_flag: trace_ends_with_ret)
[2999]80    (start_status: Status (cm prog))
81    (final_status: Status (cm prog))
[2907]82     (the_trace: trace_any_label (OC_abstract_status prog) trace_ends_flag start_status final_status)
[1579]83       on the_trace:
[2999]84         clock … (cm prog) … final_status = (compute_max_trace_any_label_cost prog trace_ends_flag start_status final_status the_trace) + (clock … (cm prog) … start_status) ≝ ?
[1579]85and compute_max_trace_label_return_cost_is_ok
[2907]86  (prog: labelled_object_code)
[2999]87    (start_status: Status (cm prog))
88    (final_status: Status (cm prog))
[2907]89    (the_trace: trace_label_return (OC_abstract_status prog) start_status final_status)
[1579]90      on the_trace:
[2999]91        clock … (cm prog) … final_status = (compute_max_trace_label_return_cost prog start_status final_status the_trace) + clock … (cm prog) … start_status ≝ ?.
[1579]92  [1:
93    cases the_trace
94    #ends_flag #start_status #end_status #any_label_trace #is_costed
[2907]95    @compute_max_trace_any_label_cost_is_ok
[1579]96  |2:
97    cases the_trace
98    [1,2:
99      #start_status #final_status #is_next #is_not_return try (#is_costed)
[2907]100      change with (current_instruction_cost … start_status) in ⊢ (???(?%?));
[1898]101      cases(is_next) @execute_1_ok_clock
[1579]102    |3:
[1693]103      #status_pre_fun_call #status_start_fun_call #status_final #is_next
104      #classifier_assm #after_return_assm #call_trace #costed_assm
105      whd in match (compute_max_trace_any_label_cost … (tal_base_call …));
[2907]106      >(compute_max_trace_label_return_cost_is_ok prog … call_trace)
[1693]107      >associative_plus @eq_f cases(is_next)
[1898]108      @execute_1_ok_clock
[1693]109    |4:
[2656]110      #status_pre_fun_call #status_start_fun_call #status_final #is_next
111      #classifier_assm #call_trace
112      whd in match (compute_max_trace_any_label_cost … (tal_base_tailcall …));
113      >(compute_max_trace_label_return_cost_is_ok … call_trace)
114      >associative_plus @eq_f cases(is_next)
115      @execute_1_ok_clock
116    |5:
[1579]117      #end_flag #status_pre_fun_call #status_start_fun_call #status_after_fun_call
[1693]118      #status_final #is_next #is_call #is_after_return #call_trace #not_costed #final_trace
[1579]119      change with (
[2907]120      let current_instruction_cost ≝ current_instruction_cost … status_pre_fun_call in
121      let call_trace_cost ≝ compute_max_trace_label_return_cost … … call_trace in
122      let final_trace_cost ≝ compute_max_trace_any_label_cost prog end_flag … final_trace in
[1579]123        call_trace_cost + current_instruction_cost + final_trace_cost) in ⊢ (???(?%?));
124      normalize nodelta;
[2907]125      >(compute_max_trace_any_label_cost_is_ok prog end_flag status_after_fun_call
[1579]126          status_final final_trace)
[2907]127      >(compute_max_trace_label_return_cost_is_ok prog status_start_fun_call
[1579]128        status_after_fun_call call_trace)
[2999]129      cases(is_next) in match (clock … (cm prog) status_start_fun_call);
[2907]130      >(execute_1_ok_clock … status_pre_fun_call)
[1579]131      <associative_plus in ⊢ (??%?);
132      <commutative_plus in match (
[2907]133        compute_max_trace_any_label_cost prog end_flag status_after_fun_call status_final final_trace
134          + compute_max_trace_label_return_cost prog status_start_fun_call status_after_fun_call call_trace);
[1693]135      >associative_plus in ⊢ (??%?); >associative_plus in ⊢ (???%); >associative_plus in ⊢ (???%);
136      @eq_f >commutative_plus in ⊢ (??%?); >associative_plus in ⊢ (??%?);
[2907]137      @eq_f @commutative_plus
[2656]138    |6:
[1579]139      #end_flag #status_pre #status_init #status_end #is_next
140      #trace_any_label #is_other #is_not_costed
141      change with (
[2907]142      let current_instruction_cost ≝ current_instruction_cost … status_pre in
[1579]143      let tail_trace_cost ≝
[2907]144       compute_max_trace_any_label_cost prog end_flag
[1579]145        status_init status_end trace_any_label
146      in
147        current_instruction_cost + tail_trace_cost) in ⊢ (???(?%?));
148      normalize nodelta;
[2907]149      >(compute_max_trace_any_label_cost_is_ok prog end_flag
[1579]150         status_init status_end trace_any_label)
[2999]151      cases(is_next) in match (clock … (cm prog) status_init);
[1898]152      >(execute_1_ok_clock … status_pre)
[1619]153      >commutative_plus >associative_plus >associative_plus @eq_f
154      @commutative_plus
[1579]155    ]
156  |3:
157    cases the_trace
158    [1:
159      #status_before #status_after #trace_to_lift
[2907]160      @compute_max_trace_label_label_cost_is_ok
[1579]161    |2:
162      #status_initial #status_labelled #status_final #labelled_trace #ret_trace
[2907]163      >(compute_max_trace_label_return_cost_is_ok prog status_labelled status_final ret_trace);
164      >(compute_max_trace_label_label_cost_is_ok prog doesnt_end_with_ret status_initial status_labelled labelled_trace);
[1579]165      <associative_plus in ⊢ (??%?);
166      >commutative_plus in match (
[2907]167        compute_max_trace_label_return_cost prog status_labelled status_final ret_trace
168          + compute_max_trace_label_label_cost prog doesnt_end_with_ret status_initial status_labelled labelled_trace);
[1579]169      %
170    ]
[1693]171  ]
[1579]172qed.
[1549]173
[1554]174let rec compute_trace_label_label_cost_using_paid
[2907]175  (prog:labelled_object_code)
[1554]176   (trace_ends_flag: trace_ends_with_ret)
[2999]177    (start_status: Status (cm prog))
178    (final_status: Status (cm prog))
[2907]179      (the_trace: trace_label_label (OC_abstract_status prog) trace_ends_flag
[1554]180        start_status final_status) on the_trace: nat ≝
181  match the_trace with
182  [ tll_base ends_flag initial final given_trace labelled_proof ⇒
[2907]183      compute_paid_trace_label_label prog … the_trace +
[1554]184      compute_trace_any_label_cost_using_paid … given_trace
185  ]
186and compute_trace_any_label_cost_using_paid
[2907]187  (prog:labelled_object_code)
[1554]188  (trace_ends_flag: trace_ends_with_ret)
[2999]189    (start_status: Status (cm prog))
190    (final_status: Status (cm prog))
[2907]191     (the_trace: trace_any_label (OC_abstract_status prog) trace_ends_flag start_status final_status)
[1554]192       on the_trace: nat ≝
193  match the_trace with
194  [ tal_base_not_return the_status _ _ _ _ ⇒ 0
195  | tal_base_return the_status _ _ _ ⇒ 0
[1693]196  | tal_base_call pre_fun_call start_fun_call final _ _ _ call_trace _ ⇒
197      compute_trace_label_return_cost_using_paid … call_trace
[2656]198  | tal_base_tailcall pre_fun_call start_fun_call final _ _ call_trace ⇒
199      compute_trace_label_return_cost_using_paid … call_trace
[1554]200  | tal_step_call end_flag pre_fun_call start_fun_call after_fun_call final
[1693]201     _ _ _ call_trace _ final_trace ⇒
[1554]202      let call_trace_cost ≝ compute_trace_label_return_cost_using_paid … call_trace in
[2907]203      let final_trace_cost ≝ compute_trace_any_label_cost_using_paid prog end_flag … final_trace in
[1554]204        call_trace_cost + final_trace_cost
205  | tal_step_default end_flag status_pre status_init status_end _ tail_trace _ _ ⇒
[2907]206     compute_trace_any_label_cost_using_paid prog end_flag
[1554]207      status_init status_end tail_trace
208  ]
209and compute_trace_label_return_cost_using_paid
[2907]210  (prog:labelled_object_code)
[2999]211    (start_status: Status (cm prog))
212    (final_status: Status (cm prog))
[2907]213    (the_trace: trace_label_return (OC_abstract_status prog) start_status final_status)
[1554]214      on the_trace: nat ≝
215  match the_trace with
216  [ tlr_base before after trace_to_lift ⇒ compute_trace_label_label_cost_using_paid … trace_to_lift
217  | tlr_step initial labelled final labelled_trace ret_trace ⇒
218      let labelled_cost ≝ compute_trace_label_label_cost_using_paid … labelled_trace in
219      let return_cost ≝ compute_trace_label_return_cost_using_paid … ret_trace in
220        labelled_cost + return_cost
221  ].
222
223let rec compute_trace_label_label_cost_using_paid_ok
[2907]224  (prog:labelled_object_code)
[1554]225   (trace_ends_flag: trace_ends_with_ret)
[2999]226    (start_status: Status (cm prog))
227    (final_status: Status (cm prog))
[2907]228      (the_trace: trace_label_label (OC_abstract_status prog) trace_ends_flag
[1554]229        start_status final_status) on the_trace:
[2907]230 compute_trace_label_label_cost_using_paid prog … the_trace =
[1554]231 compute_max_trace_label_label_cost … the_trace ≝ ?
232and compute_trace_any_label_cost_using_paid_ok
[2907]233  (prog:labelled_object_code)
[1554]234  (trace_ends_flag: trace_ends_with_ret)
[2999]235    (start_status: Status (cm prog))
236    (final_status: Status (cm prog))
[2907]237     (the_trace: trace_any_label (OC_abstract_status prog)
[1554]238      trace_ends_flag start_status final_status) on the_trace:     
[2907]239  compute_paid_trace_any_label prog trace_ends_flag … the_trace
240  +compute_trace_any_label_cost_using_paid prog trace_ends_flag … the_trace
241  =compute_max_trace_any_label_cost prog trace_ends_flag … the_trace ≝ ?
[1554]242and compute_trace_label_return_cost_using_paid_ok
[2907]243  (prog:labelled_object_code)
[2999]244    (start_status: Status (cm prog))
245    (final_status: Status (cm prog))
[2907]246    (the_trace: trace_label_return (OC_abstract_status prog)
[1554]247     start_status final_status) on the_trace:
[2907]248 compute_trace_label_return_cost_using_paid prog … the_trace =
249 compute_max_trace_label_return_cost prog … the_trace ≝ ?.
[1554]250[ cases the_trace #endsf #ss #es #tr #H normalize
251  @compute_trace_any_label_cost_using_paid_ok
252| cases the_trace
253  [ #ss #fs #H1 #H2 #H3 whd in ⊢ (??(?%%)%); <plus_n_O %
254  | #ss #fs #H1 #H2 whd in ⊢ (??(?%%)%); <plus_n_O %
[2656]255  | #sp #ss #sf #H1 #H2 #tr1 #tr2 #H3
[1693]256    whd in ⊢ (???%); whd in ⊢ (??(??%)?); whd in ⊢ (??(?%?)?);
257    >compute_trace_label_return_cost_using_paid_ok in ⊢ (??%?);
258    >commutative_plus in ⊢ (??%?); @eq_f %
[2656]259  | #sp #ss #sf #H1 #H2 #tr1
260    whd in ⊢ (???%); whd in ⊢ (??(??%)?); whd in ⊢ (??(?%?)?);
261    >compute_trace_label_return_cost_using_paid_ok in ⊢ (??%?);
262    >commutative_plus in ⊢ (??%?); @eq_f %
[1693]263  | #ef #spfc #ssfc #safc #sf #H1 #H2 #H3 #tr1 #H4 #tr2 whd in ⊢ (??(?%%)%);
[1554]264    <compute_trace_any_label_cost_using_paid_ok
265    <compute_trace_label_return_cost_using_paid_ok
266    -compute_trace_label_label_cost_using_paid_ok
267    -compute_trace_label_return_cost_using_paid_ok
268    -compute_trace_any_label_cost_using_paid_ok
269    >commutative_plus in ⊢ (???(?%?));
270    >commutative_plus in ⊢ (??(??%)?);
271    >associative_plus >associative_plus in ⊢ (???%); @eq_f2 try %
272    <associative_plus <commutative_plus %
273  | #ef #sp #si #se #H1 #tr #H2 #H3 whd in ⊢ (??(?%%)%); >associative_plus @eq_f2
274    [ % | @compute_trace_any_label_cost_using_paid_ok ]
[1506]275  ]
[1554]276| cases the_trace
277  [ #sb #sa #tr normalize @compute_trace_label_label_cost_using_paid_ok
278  | #si #sl #sf #tr1 #tr2 normalize @eq_f2
279    [ @compute_trace_label_label_cost_using_paid_ok
280    | @compute_trace_label_return_cost_using_paid_ok ]]]
281qed.
[1506]282
[1693]283include alias "ASM/BitVectorTrie.ma".
[1650]284include alias "arithmetics/nat.ma".
285include alias "basics/logic.ma".
[1693]286include alias "arithmetics/bigops.ma".
287
[1570]288(* This shoudl go in bigops! *)
289theorem bigop_sum_rev: ∀k1,k2,p,B,nil.∀op:Aop B nil.∀f:nat→B.
290 \big[op,nil]_{i<k1+k2|p i} (f i) =
291 op \big[op,nil]_{i<k2|p (i+k1)} (f (i+k1)) \big[op,nil]_{i<k1|p i} (f i).
[1693]292 #k1 #k2 #p #B #nil #op #f >bigop_sum
293 >commutative_plus @same_bigop #i @leb_elim normalize
[1570]294 [2,4: //
295 | #H1 #H2 <plus_minus_m_m //
296 | #H1 #H2 #H3 <plus_minus_m_m //]
[1561]297qed.
298
[1570]299(* This is taken by sigma_pi.ma that does not compile now *)
300definition natAop ≝ mk_Aop nat 0 plus (λa.refl ? a) (λn.sym_eq ??? (plus_n_O n))
301   (λa,b,c.sym_eq ??? (associative_plus a b c)).
302
303definition natACop ≝ mk_ACop nat 0 natAop commutative_plus.
304
305definition natDop ≝ mk_Dop nat 0 natACop times (λn.(sym_eq ??? (times_n_O n)))
306   distributive_times_plus.
307
308unification hint  0 ≔ ;
309   S ≟ mk_Aop nat 0 plus (λa.refl ? a) (λn.sym_eq ??? (plus_n_O n))
310   (λa,b,c.sym_eq ??? (associative_plus a b c))
311(* ---------------------------------------- *) ⊢
312   plus ≡ op ? ? S.
313
314unification hint  0 ≔ ;
315   S ≟ mk_ACop nat 0 (mk_Aop nat 0 plus (λa.refl ? a) (λn.sym_eq ??? (plus_n_O n))
316   (λa,b,c.sym_eq ??? (associative_plus a b c))) commutative_plus
317(* ---------------------------------------- *) ⊢
318   plus ≡ op ? ? S.
319   
320unification hint  0 ≔ ;
321   S ≟ natDop
322(* ---------------------------------------- *) ⊢
323   plus ≡ sum ? ? S.
324
325unification hint  0 ≔ ;
326   S ≟ natDop
327(* ---------------------------------------- *) ⊢
328   times ≡ prod ? ? S.
329
[1619]330notation > "Σ_{ ident i < n } f"
[1570]331  with precedence 20
332for @{'bigop $n plus 0 (λ${ident i}.true) (λ${ident i}. $f)}.
333
[1619]334notation < "Σ_{ ident i < n } f"
335  with precedence 20
336for @{'bigop $n plus 0 (λ${ident i}:$X.true) (λ${ident i}:$Y. $f)}.
337
[1570]338definition tech_cost_of_label0:
[2516]339 ∀cost_labels: BitVectorTrie costlabel 16.
[1570]340 ∀cost_map: identifier_map CostTag nat.
341 ∀codom_dom: (∀pc,k. lookup_opt … pc cost_labels = Some … k → present … cost_map k).
[1964]342 ∀ctrace:list (Σk:costlabel.∃b.lookup_opt … b cost_labels = Some ? k).
[1570]343 ∀i,p. present … cost_map (nth_safe ? i ctrace p).
[1964]344 #cost_labels #cost_map #codom_dom #ctrace #i #p
[1570]345 cases (nth_safe … i ctrace ?) normalize #id * #id_pc #K
346 lapply (codom_dom … K) #k_pres >(lookup_lookup_present … k_pres)
347 % #abs destruct (abs)
[1564]348qed.
349
[1619]350include alias "arithmetics/nat.ma".
351include alias "basics/logic.ma".
352
[1570]353lemma ltb_rect:
354 ∀P:Type[0].∀n,m. (n < m → P) → (¬ n < m → P) → P.
355 #P #n #m lapply (refl … (ltb n m)) cases (ltb n m) in ⊢ (???% → %); #E #H1 #H2
356 [ @H1 @leb_true_to_le @E | @H2 @leb_false_to_not_le @E ]
[1564]357qed.
358
[1570]359lemma same_ltb_rect:
360 ∀P,n,m,H1,H2,n',m',H1',H2'.
361  ltb n m = ltb n' m' → (∀x,y. H1 x = H1' y) → (∀x,y. H2 x = H2' y) →
362   ltb_rect P n m H1 H2 =
363   ltb_rect P n' m' H1' H2'.
364 #P #n #m #H1 #H2 #n' #m' #H1' #H2' #E #K1 #K2 whd in ⊢ (??%?);
365 cut (∀xxx,yyy,xxx',yyy'.
366   match ltb n m
367   return λx:bool.
368           eq bool (ltb n m) x
369            → (lt n m → P) → (Not (lt n m) → P) → P
370    with
371    [ true ⇒
372        λE0:eq bool (ltb n m) true.
373         λH10:lt n m → P.
374          λH20:Not (lt n m) → P. H10 (xxx E0)
375    | false ⇒
376        λE0:eq bool (ltb n m) false.
377         λH10:lt n m → P.
378          λH20:Not (lt n m) → P. H20 (yyy E0)]
379    (refl … (ltb n m)) H1 H2 =
380   match ltb n' m'
381   return λx:bool.
382           eq bool (ltb n' m') x
383            → (lt n' m' → P) → (Not (lt n' m') → P) → P
384    with
385    [ true ⇒
386        λE0:eq bool (ltb n' m') true.
387         λH10:lt n' m' → P.
388          λH20:Not (lt n' m') → P. H10 (xxx' E0)
389    | false ⇒
390        λE0:eq bool (ltb n' m') false.
391         λH10:lt n' m' → P.
392          λH20:Not (lt n' m') → P. H20 (yyy' E0)]
393    (refl … (ltb n' m')) H1' H2'
394  ) [2: #X @X]
395 >E cases (ltb n' m') #xxx #yyy #xxx' #yyy' normalize
396 [ @K1 | @K2 ]
[1564]397qed.
398
[1570]399definition tech_cost_of_label:
[2516]400 ∀cost_labels: BitVectorTrie costlabel 16.
[1570]401 ∀cost_map: identifier_map CostTag nat.
402 ∀codom_dom: (∀pc,k. lookup_opt … pc cost_labels = Some … k → present … cost_map k).
[1964]403 list (Σk:costlabel.∃b.lookup_opt … b cost_labels = Some ? k) →
[1570]404 nat → nat
[1964]405≝ λcost_labels,cost_map,codom_dom,ctrace,i.
[1570]406 ltb_rect ? i (|ctrace|)
407 (λH. lookup_present ?? cost_map (nth_safe ? i ctrace H) ?)
408 (λ_.0).
409 @tech_cost_of_label0 @codom_dom
[1564]410qed.
411
[1570]412lemma tech_cost_of_label_shift:
[1964]413 ∀cost_labels,cost_map,codom_dom,l1,l2,i.
[1620]414  i < |l2| →
[1964]415   tech_cost_of_label cost_labels cost_map codom_dom l2 i =
416   tech_cost_of_label cost_labels cost_map codom_dom (l1@l2) (i+|l1|).
417 #cost_labels #cost_Map #codom_dom #l1 #l2 #i #H
[1619]418 whd in match tech_cost_of_label; normalize nodelta @same_ltb_rect
419 [ @(ltb_rect ? i (|l2|)) @(ltb_rect ? (i+|l1|) (|l1@l2|)) #K1 #K2
420   whd in match ltb; normalize nodelta
[1964]421   [1: >le_to_leb_true try assumption applyS le_to_leb_true / by /
[1619]422   |4: >not_le_to_leb_false try assumption applyS not_le_to_leb_false
423       change with (¬ ? ≤ ?) in K1; applyS K1
[1964]424   |2: @⊥ @(absurd (i+|l1| < |l1@l2|)) / by / >length_append
425       applyS (monotonic_lt_plus_r … (|l1|)) / by /
[1619]426   |3: @⊥ @(absurd ?? K2) >length_append in K1; #K1 /2 by lt_plus_to_lt_l/ ]
427 | #H1 #H2
[1964]428   generalize in match (tech_cost_of_label0 ??? (l1@l2) ??);
[1619]429   <(shift_nth_safe … H1) #p %
[1964]430 | / by / ]
[1619]431qed.
[1570]432
[1695]433lemma tech_cost_of_label_prefix:
[1964]434 ∀cost_labels,cost_map,codom_dom,l1,l2,i.
[1695]435  i < |l1| →
[1964]436   tech_cost_of_label cost_labels cost_map codom_dom l1 i =
437   tech_cost_of_label cost_labels cost_map codom_dom (l1@l2) i.
438 #cost_labels #cost_map #codom_dom #l1 #l2 #i #H
[1695]439 whd in match tech_cost_of_label; normalize nodelta @same_ltb_rect
440 [1:
441   whd in match ltb; normalize nodelta
442   >(le_to_leb_true … H) applyS le_to_leb_true
443   >length_append whd in H; >commutative_plus @le_plus_a assumption
444 |2:
445   #K1 #K2
[1964]446   generalize in match (tech_cost_of_label0 ??? (l1@l2) ??);
[1695]447   <(shift_nth_prefix … l1 i l2 K1 K2) //
448 |3:
449   #_ #_ %
450 ]
451qed.
[2760]452
[1695]453let rec compute_trace_label_return_using_paid_ok_with_trace
[2907]454 (prog: labelled_object_code)
[1570]455 (cost_map: identifier_map CostTag nat)
[2999]456 (initial: Status (cm prog))
457 (final: Status (cm prog))
[2907]458 (trace: trace_label_return (OC_abstract_status prog) initial final)
459 (codom_dom: (∀pc,k. lookup_opt … pc (costlabels prog) = Some … k → present … cost_map k))
[1570]460 on trace:
[1921]461 ∀unrepeating_witness: tlr_unrepeating … trace.
[2907]462 ∀dom_codom:(∀k. ∀k_pres:present … cost_map k. ∀pc. lookup_opt … pc (costlabels prog) = Some … k →
463   pi1 … (block_cost prog pc) = lookup_present … k_pres).
464  let ctrace ≝ flatten_trace_label_return (OC_abstract_status prog) … trace in
465  compute_trace_label_return_cost_using_paid prog … trace =
466   (Σ_{i < |ctrace|} (tech_cost_of_label (costlabels prog) cost_map codom_dom ctrace i))
[1620]467    ≝ ?
[1695]468and compute_trace_any_label_using_paid_ok_with_trace
[2907]469 (prog: labelled_object_code)
[1620]470 (trace_ends_flag: trace_ends_with_ret)
471 (cost_map: identifier_map CostTag nat)
[2999]472 (initial: Status (cm prog))
473 (final: Status (cm prog))
[2907]474 (trace: trace_any_label (OC_abstract_status prog) trace_ends_flag initial final)
475 (codom_dom: (∀pc,k. lookup_opt … pc (costlabels prog) = Some … k → present … cost_map k))
476 (dom_codom:(∀k. ∀k_pres:present … cost_map k. ∀pc. lookup_opt … pc (costlabels prog) = Some … k →
477   pi1 … (block_cost prog pc) = lookup_present … k_pres))
[1695]478 on trace:
[1921]479  ∀unrepeating_witness: tal_unrepeating … trace.
[2907]480  let ctrace ≝ flatten_trace_any_label (OC_abstract_status prog) … trace_ends_flag … trace in
[1695]481  compute_trace_any_label_cost_using_paid … trace =
[2907]482   (Σ_{i < |ctrace|} (tech_cost_of_label (costlabels prog) cost_map codom_dom ctrace i))
[1695]483    ≝ ?
484and compute_trace_label_label_using_paid_ok_with_trace
[2907]485 (prog: labelled_object_code)
[1695]486 (trace_ends_flag: trace_ends_with_ret)
487 (cost_map: identifier_map CostTag nat)
[2999]488 (initial: Status (cm prog))
489 (final: Status (cm prog))
[2907]490 (trace: trace_label_label (OC_abstract_status prog) trace_ends_flag initial final)
[1921]491 (unrepeating_witness: tll_unrepeating … trace)
[2907]492 (codom_dom: (∀pc,k. lookup_opt … pc (costlabels prog) = Some … k → present … cost_map k))
493 (dom_codom:(∀k. ∀k_pres:present … cost_map k. ∀pc. lookup_opt … pc (costlabels prog) = Some … k →
494   pi1 … (block_cost prog pc) = lookup_present … k_pres))
[1620]495 on trace:
[1921]496 ∀unrepeating_witness: tll_unrepeating … trace.
[2907]497  let ctrace ≝ flatten_trace_label_label (OC_abstract_status prog) … trace in
[1695]498  compute_trace_label_label_cost_using_paid … trace =
[2907]499   (Σ_{i < |ctrace|} (tech_cost_of_label (costlabels prog) cost_map codom_dom ctrace i))
[1570]500    ≝ ?.
[1695]501  cases trace normalize nodelta
[1921]502  [ #sb #sa #tr #unrepeating_witness #dom_codom whd in ⊢ (??%?);
[1964]503    whd in match (flatten_trace_label_return ????);
[1929]504    @compute_trace_label_label_using_paid_ok_with_trace
[1921]505    assumption
506  | #si #sl #sf #tr1 #tr2 #unrepeating_witness #dom_codom
[1695]507    whd in ⊢ (??%?);
[2760]508    whd in match flatten_trace_label_return; normalize nodelta
509    whd in match (observables_trace_label_return ?????);
510    >costlabels_of_observables_append
[1695]511    >append_length >bigop_sum_rev >commutative_plus @eq_f2
[1929]512    [ >(compute_trace_label_return_using_paid_ok_with_trace … cost_map … codom_dom ? dom_codom)
[1695]513      -compute_trace_label_return_using_paid_ok_with_trace
[1921]514      [1:
515        @same_bigop [//] #i #H #_ -dom_codom @tech_cost_of_label_shift //
516      |2:
517        inversion unrepeating_witness
518        #tll_unrepeating #tlr_unrepeating #_ assumption
519      ]
[1929]520    | >(compute_trace_label_label_using_paid_ok_with_trace … cost_map … codom_dom … dom_codom)
[1695]521      -compute_trace_label_label_using_paid_ok_with_trace
[1921]522      [1:
523        @same_bigop [//] #i #H #_ @(tech_cost_of_label_prefix … H)
524      |2,3:
525        inversion unrepeating_witness
526        #tll_unrepeating #tlr_unrepeating #_ assumption
527      ]
[1695]528    ]
[2656]529  |9:
[1695]530    #end_flag #start_status #end_status #trace_any_label #costed_assm
[1923]531    #unrepeating_witness'
[1695]532    whd in ⊢ (??%?); whd in ⊢ (??(?%?)?);
[1929]533    >(compute_trace_any_label_using_paid_ok_with_trace … cost_map … codom_dom … dom_codom)
[1695]534    [1:
[1964]535      whd in match (flatten_trace_label_label ?????);
[1921]536      >bigop_0 in ⊢ (???%); >commutative_plus @eq_f2
[1900]537      [1:
[1921]538        @same_bigop [//] #i #H #_ -dom_codom >(plus_n_O i) >plus_n_Sm
[1964]539        <(tech_cost_of_label_shift ??? [?] ? i) try assumption <(plus_n_O i) %
[1900]540      |2:
[1921]541        change with (? = lookup_present ? ? ? ? ?)
[1964]542        generalize in match (tech_cost_of_label0 ? ? ? ? ? ?);
[2656]543        whd in ⊢ (∀p:????%.???(????%?));
[1927]544        whd in costed_assm; lapply costed_assm whd in match (as_label ??);
[2907]545        inversion (lookup_opt ? ? (program_counter … start_status) (costlabels prog))
[1921]546        [1:
[1927]547          #_ #absurd @⊥ cases absurd #absurd @absurd %
[1921]548        |2:
549          normalize nodelta #cost_label #Some_assm #_ #p
550          cases (dom_codom ? p ? Some_assm)
[2907]551          cases (block_cost ??)
[1929]552          #cost #block_cost_assm
553          cases (block_cost_assm ??? trace_any_label ??)
[1923]554          try @refl assumption
[1921]555        ]
[1900]556      ]
[1921]557    |2:
558      assumption
[1695]559    ]
560  |3:
561    #start_status #final_status #execute_assm #classifier_assm #costed_assm
[1921]562    #unrepeating_witness
[1695]563    %
564  |4:
[1921]565    #start_status #final_status #execute_assm #classifier_assm #unrepeating_witness
566    %
[1695]567  |5:
568    #status_pre_fun_call #status_start_fun_call #status_final #execute_assm
[1921]569    #classifier_assm #after_return_assm #trace_label_return #costed_assm #unrepeating_witness
[1695]570    whd in ⊢ (??%?);
[2760]571    >(compute_trace_label_return_using_paid_ok_with_trace … cost_map … codom_dom ? dom_codom)
572    //
573    whd in match flatten_trace_any_label; normalize nodelta
574    whd in match (observables_trace_any_label ??????);
575    >(costlabels_of_observables_append … [?]) [2: normalize /2/]
576    >length_append whd in match (? + ?);
577    whd in match flatten_trace_label_return; normalize nodelta
578    >costlabels_of_observables_trace_label_return_id_irrelevant //
[1695]579  |6:
[2656]580    #status_pre_fun_call #status_start_fun_call #status_final #execute_assm
581    #classifier_assm #trace_label_return #unrepeating_witness
582    whd in ⊢ (??%?);
[2760]583    >(compute_trace_label_return_using_paid_ok_with_trace … cost_map … codom_dom ? dom_codom)
584    //
585    whd in match flatten_trace_any_label; normalize nodelta
586    whd in match (observables_trace_any_label ??????);
587    >(costlabels_of_observables_append … [?]) [2: normalize /2/]
588    >length_append whd in match (? + ?);
589    whd in match flatten_trace_label_return; normalize nodelta
590    >costlabels_of_observables_trace_label_return_id_irrelevant //
[2656]591  |7:
[1695]592    #end_flag #status_pre_fun_call #status_start_fun_call #status_after_fun_call
593    #status_final #execute_assm #classifier_assm #after_return_assm #trace_label_return
[1921]594    #costed_assm #trace_any_label #unrepeating_witness
[1695]595    whd in ⊢ (??%?);
[1929]596    >(compute_trace_label_return_using_paid_ok_with_trace … cost_map … codom_dom ? dom_codom)
[1921]597    [1:
[1929]598      >(compute_trace_any_label_using_paid_ok_with_trace … cost_map … codom_dom … dom_codom)
[1921]599      [1:
[2760]600        whd in match flatten_trace_any_label in ⊢ (???%); normalize nodelta
601        whd in match (observables_trace_any_label ??????);
602        >costlabels_of_observables_append
603        >(costlabels_of_observables_append … [?]) [2: normalize /2/]
[1921]604        >length_append >bigop_sum_rev >commutative_plus @eq_f2
605        [ @same_bigop [2: #i #H #_ -dom_codom @tech_cost_of_label_shift assumption
606                      |1: #i #H % ]
[2760]607        | >length_append whd in match (|?|+?);
608          >costlabels_of_observables_trace_label_return_id_irrelevant
609          [@same_bigop [#i #H %] #i #H #_ @(tech_cost_of_label_prefix … H) | skip]
[1921]610        ]
611      |2:
612        inversion unrepeating_witness
613        * #memb_1 #tal_unrepeating #tlr_unrepeating #_ assumption
614      ]
615    |2:
616      inversion unrepeating_witness
617      * #memb_1 #tal_unrepeating #tlr_unrepeating #_ assumption
[1695]618    ]
[2656]619  |8:
[1695]620    #end_flag #status_pre_fun_call #status_start_fun_call #status_final
[1921]621    #execute_assm #trace_any_label #classifier_assm #costed_assm #unrepeating_witness
[1695]622    whd in ⊢ (??%?);
[1929]623    @(compute_trace_any_label_using_paid_ok_with_trace … cost_map … codom_dom … dom_codom)
[1921]624    inversion unrepeating_witness
625    #memb_1 #tal_unrepeating #_ assumption
[1554]626  ]
[1695]627qed.
628 
[1898]629lemma compute_max_trace_label_return_cost_ok_with_trace_aux:
[2907]630  ∀prog: labelled_object_code.
[1695]631  ∀cost_map: identifier_map CostTag nat.
[2999]632  ∀initial: Status (cm prog).
633  ∀final: Status (cm prog).
[2907]634  ∀trace: trace_label_return (OC_abstract_status prog) initial final.
[1921]635  ∀unrepeating_witness: tlr_unrepeating … trace.
[2907]636  ∀codom_dom: (∀pc,k. lookup_opt … pc (costlabels prog) = Some … k → present … cost_map k).
637  ∀dom_codom: (∀k. ∀k_pres:present … cost_map k. ∀pc. lookup_opt … pc (costlabels prog) = Some … k →
638      pi1 … (block_cost prog pc) = lookup_present … k_pres).
[1964]639        let ctrace ≝ flatten_trace_label_return … trace in
[2999]640          clock … (cm prog) … final =
641            clock … (cm prog) … initial + (Σ_{i < |ctrace|} (tech_cost_of_label (costlabels prog) cost_map codom_dom ctrace i)).
[2907]642  #prog #cost_map
[1921]643  #initial #final #trace #unrepeating_witness #codom_dom #dom_codom normalize nodelta
[1695]644  <compute_trace_label_return_using_paid_ok_with_trace try assumption
645  >commutative_plus >compute_trace_label_return_cost_using_paid_ok //
[1898]646qed.
647
648theorem compute_max_trace_label_return_cost_ok_with_trace:
[2907]649  ∀prog: labelled_object_code.
[2999]650  ∀initial: Status (cm prog).
651  ∀final: Status (cm prog).
[2907]652  ∀trace: trace_label_return (OC_abstract_status prog) initial final.
[1921]653  ∀unrepeating_witness: tlr_unrepeating … trace.
[2907]654    let cost_map ≝ traverse_code prog in
[1964]655    let ctrace ≝ flatten_trace_label_return … trace in
[2999]656      clock … (cm prog) … final = clock … (cm prog) … initial + (Σ_{i < |ctrace|} (tech_cost_of_label (costlabels prog) cost_map ? ctrace i)).
[1898]657  [1:
[2907]658    #prog #initial #final #trace #unrepeating_witness
[1898]659    @compute_max_trace_label_return_cost_ok_with_trace_aux try assumption
660  |2:
661    skip
662  ]
663  normalize nodelta
[2907]664  cases (traverse_code ?)
[1898]665  #cost_map * #dom_codom #codom_dom try assumption
666  #pc #k #lookup_opt_assm @(dom_codom … lookup_opt_assm)
667  lapply (sym_eq ? ? ? lookup_opt_assm)
668  -lookup_opt_assm #lookup_opt_assm
[1929]669  @nat_of_bitvector_lt_bound
[1976]670qed.
671 
672include "utilities/permutations.ma".
[2516]673
[2657]674definition map_of_sigma_map:
675 ∀P.
676  (Σmap:identifier_map CostTag ℕ.P map) → identifier_map CostTag ℕ
677 ≝ λP,x.x.
678
679lemma costlabel_map_of_as_cost_labels_map_ok:
[2907]680 ∀prog,tl,Htl,PRF,PRF2.
681  lookup_present CostTag ℕ (compute_costs prog) tl
[2657]682  PRF
683  =
[2907]684   lookup_present CostTag ℕ (compute_costs prog)
685   (as_cost_get_label (OC_abstract_status prog)
[2657]686    «tl,Htl») PRF2.
687//
688qed.
689
[1976]690lemma tech_cost_sum_eq_as_cost :
[2754]691  ∀compiled_code: labelled_object_code.
[2760]692  let cost_labels ≝ costlabels compiled_code in
[2907]693  let cost_map ≝ compute_costs compiled_code in
[2657]694  ∀codom_dom: (∀pc,k. lookup_opt … pc cost_labels = Some … k → present … k).
[1976]695  ∀trace.
[2671]696  (Σ_{i < |trace|}(tech_cost_of_label cost_labels (map_of_sigma_map … cost_map) codom_dom trace i)) =
[2760]697  (Σ_{l ∈ trace}(ASM_cost_map compiled_code l)).
698#ccode #codom_dom #trace
[1976]699@(list_elim_left … trace)
700[ %
701| #tl #hd #IH >append_length >commutative_plus
702  >(fold_permute … (hd@[tl]) (tl::hd)) [2: @perm_swap_append ]
[2671]703  whd in ⊢ (??%%); <IH
704  <tech_cost_of_label_shift [2: //]
[1976]705  cut (∀x,y,z,w.x = y → z = w → x + z = y + w) [ // ] #APP @APP -APP
[2760]706  [ cases tl -tl #tl #Htl @costlabel_map_of_as_cost_labels_map_ok
[1976]707  | @sym_eq @same_bigop /2 by tech_cost_of_label_prefix/
708  ]
709]
[2999]710qed.
Note: See TracBrowser for help on using the repository browser.