source: src/joint/Joint_paolo.ma @ 2162

Last change on this file since 2162 was 2162, checked in by tranquil, 8 years ago
  • yet another correction to joint
  • added functions adding prologues and epilogues in TranslateUtils?. Adding a prologue will preserve the invariant of having a cost label at the start of the function, without needing transformations later
  • redefined ERTL and rewritten RTLToERTL (with suffix "_paolo")
File size: 19.4 KB
Line 
1include "ASM/I8051.ma".
2include "common/CostLabel.ma".
3include "common/AST.ma".
4include "common/Registers.ma".
5include "common/Graphs.ma".
6include "utilities/lists.ma".
7include "common/LabelledObjects.ma".
8include "ASM/Util.ma".
9include "common/StructuredTraces.ma".
10
11(* Here is the structure of parameter records (downward edges are coercions,
12   the ↓ edges are the only explicitly defined coercions). lin_params and
13   graph_params are simple wrappers of unserialized_params, and the coercions
14   from them to params instantiate the missing bits with values for linarized
15   programs and graph programs respectively.
16
17        lin_params      graph_params
18              |   \_____ /____   |
19              |         /     \  |
20              |        /      ↓  ↓
21              |       |      params
22              |       |        |
23              |       |   stmt_params
24              |       |    /   
25          unserialized_params             
26            |            \       
27            |             \     
28            |         local_params
29            |              |   
30    step_params       funct_params
31
32step_params : types needed to define steps (stmts with a default fallthrough)
33stmt_params : adds successor type needed to define statements
34funct_params : types of result register and parameters of function
35local_params : adds types of local registers
36params : adds type of code and related properties *)
37
38inductive possible_flows : Type[0] ≝
39| Labels : list label → possible_flows
40| Call : possible_flows.
41
42record step_params : Type[1] ≝
43 { acc_a_reg: Type[0] (* registers that will eventually need to be A *)
44 ; acc_b_reg: Type[0] (* registers that will eventually need to be B *)
45 ; acc_a_arg: Type[0] (* arguments that will eventually need to be A *)
46 ; acc_b_arg: Type[0] (* arguments that will eventually need to be B *)
47 ; dpl_reg: Type[0]   (* low address registers *)
48 ; dph_reg: Type[0]   (* high address registers *)
49 ; dpl_arg: Type[0]   (* low address registers *)
50 ; dph_arg: Type[0]   (* high address registers *)
51 ; snd_arg : Type[0]  (* second argument of binary op *)
52 ; pair_move: Type[0] (* argument of move instructions *)
53 ; call_args: Type[0] (* arguments of function calls *)
54 ; call_dest: Type[0] (* possible destination of function computation *)
55 (* other instructions not fitting in the general framework *)
56 ; ext_seq : Type[0]
57(* ; ext_branch : Type[0]
58 ; ext_branch_labels : ext_branch → list label*)
59 ; ext_call : Type[0]
60 ; ext_tailcall : Type[0]
61 (* if needed: ; ext_fin_branch : Type[0] ; ext_fin_branch_labels : ext_fin_branch → list label *)
62 }.
63
64inductive joint_seq (p:step_params) (globals: list ident): Type[0] ≝
65  | COMMENT: String → joint_seq p globals
66  | COST_LABEL: costlabel → joint_seq p globals
67  | MOVE: pair_move p → joint_seq p globals
68  | POP: acc_a_reg p → joint_seq p globals
69  | PUSH: acc_a_arg p → joint_seq p globals
70  | ADDRESS: ∀i: ident. (member i (eq_identifier ?) globals) → dpl_reg p → dph_reg p → joint_seq p globals
71  | OPACCS: OpAccs → acc_a_reg p → acc_b_reg p → acc_a_arg p → acc_b_arg p → joint_seq p globals
72  | OP1: Op1 → acc_a_reg p → acc_a_reg p → joint_seq p globals
73  | OP2: Op2 → acc_a_reg p → acc_a_arg p → snd_arg p → joint_seq p globals
74  (* int done with generic move *)
75(*| INT: generic_reg p → Byte → joint_seq p globals *)
76  | CLEAR_CARRY: joint_seq p globals
77  | SET_CARRY: joint_seq p globals
78  | LOAD: acc_a_reg p → dpl_arg p → dph_arg p → joint_seq p globals
79  | STORE: dpl_arg p → dph_arg p → acc_a_arg p → joint_seq p globals
80  | CALL_ID: ident → call_args p → call_dest p → joint_seq p globals
81  | extension_seq : ext_seq p → joint_seq p globals
82  | extension_call : ext_call p → joint_seq p globals.
83
84axiom EmptyString : String.
85definition NOOP ≝ λp,globals.COMMENT p globals EmptyString.
86
87notation "r ← a1 .op. a2" with precedence 60 for
88  @{'op2 $op $r $a1 $a2}.
89notation "r ← . op . a" with precedence 60 for
90  @{'op1 $op $r $a}.
91notation "r ← a" with precedence 60 for
92  @{'mov $r $a}. (* to be set in individual languages *)
93notation "❮r, s❯ ← a1 . op . a2" with precedence 55 for
94  @{'opaccs $op $r $s $a1 $a2}.
95
96interpretation "op2" 'op2 op r a1 a2 = (OP2 ? ? op r a1 a2).
97interpretation "op1" 'op1 op r a = (OP1 ? ? op r a).
98interpretation "opaccs" 'opaccs op r s a1 a2 = (OPACCS ? ? op r s a1 a2).
99
100coercion extension_seq_to_seq : ∀p,globals.∀s : ext_seq p.joint_seq p globals ≝
101  extension_seq on _s : ext_seq ? to joint_seq ??.
102coercion extension_call_to_seq : ∀p,globals.∀s : ext_call p.joint_seq p globals ≝
103  extension_call on _s : ext_call ? to joint_seq ??.
104 
105(* inductive joint_branch (p : step_params) : Type[0] ≝
106  | COND: acc_a_reg p → label → joint_branch p
107  | extension_branch : ext_branch p → joint_branch p.*)
108
109(*coercion extension_to_branch : ∀p.∀s : ext_branch p.joint_branch p ≝
110  extension_branch on _s : ext_branch ? to joint_branch ?.*)
111
112inductive joint_step (p : step_params) (globals : list ident) : Type[0] ≝
113  | step_seq : joint_seq p globals → joint_step p globals
114  | COND: acc_a_reg p → label → joint_step p globals.
115
116coercion seq_to_step : ∀p,globals.∀s : joint_seq p globals.joint_step p globals ≝
117  step_seq on _s : joint_seq ?? to joint_step ??.
118
119definition step_flows ≝ λp,globals.λs : joint_step p globals.
120  match s with
121  [ step_seq s ⇒
122    match s with
123    [ CALL_ID _ _ _ ⇒ Call
124    | extension_call _ ⇒ Call
125    | _ ⇒ Labels … [ ]
126    ]
127  | COND _ l ⇒ Labels … [l]
128  ].
129
130definition step_labels ≝
131  λp, globals.λs : joint_step p globals.
132    match step_flows … s with
133    [ Labels lbls ⇒ lbls
134    | Call ⇒ [ ]
135    ].
136
137definition step_forall_labels : ∀p : step_params.∀globals.
138    (label → Prop) → joint_step p globals → Prop ≝
139λp,g,P,inst. All … P (step_labels … inst).
140
141definition step_classifier :
142  ∀p : step_params.∀globals.
143    joint_step p globals → status_class ≝ λp,g,s.
144  match s with
145  [ step_seq s ⇒
146    match s with
147    [ CALL_ID _ _ _ ⇒ cl_call
148    | extension_call _ ⇒ cl_call
149    | _ ⇒ cl_other
150    ]
151  | COND _ _ ⇒ cl_jump
152  ].
153
154record funct_params : Type[1] ≝
155  { resultT : Type[0]
156  ; paramsT : Type[0]
157  }.
158 
159record local_params : Type[1] ≝
160 { funct_pars :> funct_params
161 ; localsT: Type[0]
162 }.
163
164record unserialized_params : Type[1] ≝
165 { u_inst_pars :> step_params
166 ; u_local_pars :> local_params
167 }.
168
169record stmt_params : Type[1] ≝
170  { uns_pars :> unserialized_params
171  ; succ : Type[0]
172  ; succ_label : succ → option label
173  }.
174
175inductive joint_fin_step (p: step_params): Type[0] ≝
176  | GOTO: label → joint_fin_step p
177  | RETURN: joint_fin_step p
178  | tailcall : ext_tailcall p → joint_fin_step p.
179
180definition fin_step_flows ≝ λp.λs : joint_fin_step p.
181  match s with
182  [ GOTO l ⇒ Labels … [l]
183  | _ ⇒ Labels … [ ] (* tailcalls will need to be integrated in structured traces *)
184  ].
185
186definition fin_step_labels ≝
187  λp.λs : joint_fin_step p.
188    match fin_step_flows … s with
189    [ Labels lbls ⇒ lbls
190    | Call ⇒ [ ]
191    ].
192
193definition fin_step_classifier :
194  ∀p : stmt_params.
195    joint_fin_step p → status_class
196  ≝ λp,s.
197  match s with
198  [ GOTO _ ⇒ cl_other
199  | _ ⇒ cl_return
200  ].
201
202inductive joint_statement (p: stmt_params) (globals: list ident): Type[0] ≝
203  | sequential: joint_step p globals → succ p → joint_statement p globals
204  | final: joint_fin_step p → joint_statement p globals.
205
206definition stmt_classifier :
207  ∀p : stmt_params.∀globals.
208    joint_statement p globals → status_class
209  ≝ λp,g,s.
210  match s with
211  [ sequential stp _ ⇒ step_classifier p g stp
212  | final stp ⇒ fin_step_classifier p stp
213  ].
214
215coercion extension_fin_to_fin_step : ∀p : stmt_params.
216  ∀s : ext_tailcall p.joint_fin_step p ≝
217  tailcall on _s : ext_tailcall ? to joint_fin_step ?.
218
219coercion fin_step_to_stmt : ∀p : stmt_params.∀globals.
220  ∀s : joint_fin_step p.joint_statement p globals ≝
221  final on _s : joint_fin_step ? to joint_statement ??.
222
223record params : Type[1] ≝
224 { stmt_pars :> stmt_params
225 ; codeT: list ident → Type[0]
226 ; code_point : Type[0]
227 ; stmt_at : ∀globals.codeT globals → code_point → option (joint_statement stmt_pars globals)
228 ; point_of_label : ∀globals.codeT globals → label → option code_point
229 ; point_of_succ : code_point → succ stmt_pars → code_point
230 }.
231
232definition code_has_point ≝
233  λp,globals,c,pt.match stmt_at p globals c pt with [Some _ ⇒ true | None ⇒ false].
234
235interpretation "code membership" 'mem p c = (code_has_point ?? c p).
236
237definition point_in_code ≝ λp,globals,code.Σpt.bool_to_Prop (code_has_point p globals code pt).
238unification hint 0 ≔ p, globals, code ⊢ point_in_code p globals code ≡ Sig (code_point p) (λpt.bool_to_Prop (code_has_point p globals code pt)).
239
240definition stmt_at_safe ≝ λp,globals,code.λpt : point_in_code p globals code.
241  match pt with
242  [ mk_Sig pt' pt_prf ⇒
243    match stmt_at … code pt' return λx.stmt_at … code pt' = x → ? with
244    [ Some x ⇒ λ_.x
245    | None ⇒ λabs.⊥
246    ] (refl …)
247  ]. normalize in pt_prf;
248    >abs in pt_prf; // qed.
249
250definition forall_statements : ∀p : params.∀globals.pred_transformer (joint_statement p globals) (codeT p globals)  ≝
251  λp,globals,P,c. ∀pt,s.stmt_at ?? c pt = Some ? s → P s.
252
253definition forall_statements_i :
254  ∀p : params.∀globals.(code_point p → joint_statement p globals → Prop) →
255    codeT p globals → Prop  ≝
256  λp,globals,P,c. ∀pt,s.stmt_at ?? c pt = Some ? s → P pt s.
257
258lemma forall_statements_mp : ∀p,globals.modus_ponens ?? (forall_statements p globals).
259#p #globals #P #Q #H #y #G #pnt #s #EQ @H @(G … EQ) qed.
260
261lemma forall_statements_i_mp : ∀p,globals.∀P,Q.(∀pt,s.P pt s → Q pt s) →
262  ∀c.forall_statements_i p globals P c → forall_statements_i p globals Q c.
263#p #globals #P #Q #H #y #G #pnt #s #EQ @H @(G … EQ) qed.
264
265definition code_has_label ≝ λp,globals,c,l.
266  match point_of_label p globals c l with
267  [ Some pt ⇒ code_has_point … c pt
268  | None ⇒ false
269  ].
270
271definition stmt_explicit_labels :
272  ∀p,globals.
273  joint_statement p globals → list label ≝
274  λp,globals,stmt. match stmt with
275  [ sequential c _ ⇒ step_labels … c
276  | final c ⇒ fin_step_labels … c
277  ].
278
279definition stmt_implicit_label : ∀p,globals.joint_statement p globals →
280  option label ≝
281 λp,globals,s.match s with [ sequential _ s ⇒ succ_label … s | _ ⇒ None ?].
282 
283definition stmt_labels : ∀p : stmt_params.∀globals.
284    joint_statement p globals → list label ≝
285  λp,g,stmt.
286  (match stmt_implicit_label … stmt with
287     [ Some l ⇒ [l]
288     | None ⇒ [ ]
289     ]) @ stmt_explicit_labels … stmt.
290
291definition stmt_forall_labels ≝
292  λp, globals.λ P : label → Prop.λs : joint_statement p globals.
293  All … P (stmt_labels … s).
294
295lemma stmt_forall_labels_explicit : ∀p,globals,P.∀s : joint_statement p globals.
296  stmt_forall_labels … P s → All … P (stmt_explicit_labels … s).
297#p#globals#P #s
298whd in ⊢ (% → ?);
299whd in ⊢ (???% → ?);
300elim (stmt_implicit_label ???) [2: #next * #_] //
301qed.
302
303lemma stmt_forall_labels_implicit : ∀p,globals,P.∀s : joint_statement p globals.
304  stmt_forall_labels … P s →
305    opt_All … P (stmt_implicit_label … s).
306#p#globals#P#s
307whd in ⊢ (% → ?);
308whd in ⊢ (???% → ?);
309elim (stmt_implicit_label ???)
310[ //
311| #next * #Pnext #_ @Pnext
312]
313qed.
314
315definition code_forall_labels ≝
316  λp,globals,P,c.forall_statements p globals (stmt_forall_labels … P) c.
317
318lemma code_forall_labels_mp : ∀p,globals,P,Q.(∀l.P l → Q l) →
319  ∀c.code_forall_labels p globals P c → code_forall_labels … Q c ≝
320  λp,globals,P,Q,H.forall_statements_mp … (λs. All_mp … H ?).
321
322record lin_params : Type[1] ≝
323  { l_u_pars : unserialized_params }.
324 
325lemma index_of_label_length : ∀tag,A,lbl,l.occurs_exactly_once ?? lbl l → lt (index_of_label tag A lbl l) (|l|).
326#tag #A #lbl #l elim l [*]
327** [2: #id] #a #tl #IH
328[ change with (if (eq_identifier ???) then ? else ?) in match (occurs_exactly_once ????);
329  change with (if (eq_identifier ???) then ? else ?) in match (index_of_label ????);
330  @eq_identifier_elim #Heq normalize nodelta
331  [ #_ normalize / by /]
332| whd in ⊢ (?%→?%?);
333]
334#H >(index_of_label_from_internal … H)
335@le_S_S @(IH H)
336qed.
337
338(* mv *)
339lemma nth_opt_hit_length : ∀A,l,n,x.nth_opt A n l = Some ? x → n < |l|.
340#A #l elim l normalize [ #n #x #ABS destruct(ABS)]
341#hd #tl #IH * [2:#n] #x normalize [#H @le_S_S @(IH … H)] /2 by /
342qed.
343
344lemma nth_opt_miss_length : ∀A,l,n.nth_opt A n l = None ? → n ≥ |l|.
345#A #l elim l [//] #hd #tl #IH * normalize [#ABS destruct(ABS)]
346#n' #H @le_S_S @(IH … H)
347qed.
348
349lemma nth_opt_safe : ∀A,l,n,prf.nth_opt A n l = Some ? (nth_safe A n l prf).
350#A #l elim l
351[ #n #ABS @⊥ /2 by absurd/
352| #hd #tl #IH * normalize //
353]
354qed.
355
356definition lin_params_to_params ≝
357  λlp : lin_params.
358     mk_params
359      (mk_stmt_params (l_u_pars lp) unit (λ_.None ?))
360    (* codeT ≝ *)(λglobals.list ((option label) × (joint_statement ? globals)))
361    (* code_point ≝ *)ℕ
362    (* stmt_at ≝ *)(λglobals,code,point.! ls ← nth_opt ? point code ; return \snd ls)
363    (* point_of_label ≝ *)(λglobals,c,lbl.
364      If occurs_exactly_once ?? lbl c then with prf do
365        return index_of_label ?? lbl c
366      else
367        None ?)
368    (* point_of_succ ≝ *)(λcurrent.λ_.S (current)).
369
370coercion lp_to_p : ∀lp : lin_params.params ≝ lin_params_to_params
371  on _lp : lin_params to params.
372 
373lemma lin_code_has_point : ∀lp : lin_params.∀globals.∀code:codeT lp globals.
374  ∀pt.pt ∈ code = leb (S pt) (|code|).
375#lp #globals #code elim code
376[ #pt %
377| #hd #tl #IH * [%]
378  #n @IH
379]qed.
380
381lemma lin_code_has_label : ∀lp : lin_params.∀globals.∀code:codeT lp globals.
382  ∀lbl.code_has_label … code lbl = occurs_exactly_once ?? lbl code.
383#lp #globals #code #lbl
384whd in match (code_has_label ????);
385whd in match (point_of_label ????);
386elim (true_or_false_Prop (occurs_exactly_once ?? lbl code))
387#Heq >Heq normalize nodelta
388[ >lin_code_has_point @(leb_elim (S ?)) [#_ |
389  #ABS elim(absurd ?? ABS) -ABS
390  @index_of_label_length assumption ]] %
391qed.
392
393record graph_params : Type[1] ≝
394  { g_u_pars : unserialized_params }.
395
396(* One common instantiation of params via Graphs of joint_statements
397   (all languages but LIN) *)
398definition graph_params_to_params ≝
399  λgp : graph_params.
400     mk_params
401      (mk_stmt_params (g_u_pars gp) label (Some ?))
402    (* codeT ≝ *)(λglobals.graph (joint_statement ? globals))
403    (* code_point ≝ *)label
404    (* stmt_at ≝ *)(λglobals,code.lookup LabelTag ? code)
405    (* point_of_label ≝ *)(λ_.λ_.λlbl.return lbl)
406    (* point_of_succ ≝ *)(λ_.λlbl.lbl).
407
408coercion gp_to_p : ∀gp:graph_params.params ≝ graph_params_to_params
409on _gp : graph_params to params.
410
411lemma graph_code_has_point : ∀gp : graph_params.∀globals.∀code:codeT gp globals.
412  ∀pt.code_has_point … code pt = mem_set … code pt.
413#gp#globals*#m*#i % qed.
414
415lemma graph_code_has_label : ∀gp : graph_params.∀globals.∀code:codeT gp globals.
416  ∀lbl.code_has_label … code lbl = mem_set … code lbl.
417#gp #globals * #m * #i % qed.
418
419definition stmt_forall_succ ≝ λp,globals.λP : succ p → Prop.
420  λs : joint_statement p globals.
421  match s with
422  [ sequential _ n ⇒ P n
423  | _ ⇒ True
424  ].
425
426definition statement_closed : ∀globals.∀p : params.
427  codeT p globals → code_point p → (joint_statement p globals) → Prop ≝
428λglobals,p,code,pt,s.
429  All ? (λl.bool_to_Prop (code_has_label ?? code l)) (stmt_explicit_labels … s) ∧
430  stmt_forall_succ … (λn.bool_to_Prop (point_of_succ ? pt n ∈ code)) s.
431
432definition code_closed : ∀p : params.∀globals.
433  codeT p globals → Prop ≝ λp,globals,code.
434    forall_statements_i … (statement_closed … code) code.
435
436(* CSC: special case where localsT is a list of registers (RTL and ERTL) *)
437definition rtl_ertl_params : ?→?→params ≝ λinst_pars,funct_pars.
438  (mk_graph_params (mk_unserialized_params inst_pars (mk_local_params funct_pars register))).
439
440record joint_internal_function (globals: list ident) (p:params) : Type[0] ≝
441{ joint_if_luniverse: universe LabelTag;    (*CSC: used only for compilation*)
442  joint_if_runiverse: universe RegisterTag; (*CSC: used only for compilation*)
443  (* Paolo: if we want this machinery to work for RTLabs too, we will need the
444     following, right? *)
445(*  joint_if_sig: signature;  -- dropped in front end *)
446  joint_if_result   : resultT p;
447  joint_if_params   : paramsT p;
448  joint_if_locals   : list (localsT p); (* use void where no locals are present *)
449(*CSC: XXXXX stacksize unused for LTL-...*)
450  joint_if_stacksize: nat;
451  joint_if_code     : codeT p globals ;
452  joint_if_entry : point_in_code … joint_if_code ;
453  joint_if_exit : point_in_code … joint_if_code
454}.
455
456definition joint_closed_internal_function ≝
457  λglobals,p.
458    Σdef : joint_internal_function globals p. code_closed … (joint_if_code … def).
459
460definition set_joint_code ≝
461  λglobals: list ident.
462  λpars: params.
463  λint_fun: joint_internal_function globals pars.
464  λgraph: codeT pars globals.
465  λentry.
466  λexit.
467    mk_joint_internal_function globals pars
468      (joint_if_luniverse … int_fun) (joint_if_runiverse … int_fun) (joint_if_result … int_fun)
469      (joint_if_params … int_fun) (joint_if_locals … int_fun) (joint_if_stacksize … int_fun)
470      graph entry exit.
471
472definition set_joint_if_graph ≝
473  λglobals.λpars : graph_params.
474  λgraph.
475  λp:joint_internal_function globals pars.
476  λentry_prf.
477  λexit_prf.
478    set_joint_code globals pars p
479      graph
480      (mk_Sig ?? (joint_if_entry ?? p) entry_prf)
481      (mk_Sig … (joint_if_exit ?? p) exit_prf).
482
483definition set_luniverse ≝
484  λglobals,pars.
485  λp : joint_internal_function globals pars.
486  λluniverse: universe LabelTag.
487   mk_joint_internal_function globals pars
488    luniverse (joint_if_runiverse … p) (joint_if_result … p)
489    (joint_if_params … p) (joint_if_locals … p) (joint_if_stacksize … p)
490    (joint_if_code … p) (joint_if_entry … p) (joint_if_exit … p).
491
492definition set_runiverse ≝
493  λglobals,pars.
494  λp : joint_internal_function globals pars.
495  λruniverse: universe RegisterTag.
496   mk_joint_internal_function globals pars
497    (joint_if_luniverse … p) runiverse (joint_if_result … p)
498    (joint_if_params … p) (joint_if_locals … p) (joint_if_stacksize … p)
499    (joint_if_code … p) (joint_if_entry … p) (joint_if_exit … p).
500   
501(* Specialized for graph_params *)
502definition add_graph ≝
503  λg_pars : graph_params.λglobals.λl:label.λstmt.
504    λp:joint_internal_function globals g_pars.
505   let code ≝ add … (joint_if_code … p) l stmt in
506    mk_joint_internal_function ? g_pars
507     (joint_if_luniverse … p) (joint_if_runiverse … p) (joint_if_result … p)
508     (joint_if_params … p) (joint_if_locals … p) (joint_if_stacksize … p)
509     code
510     (pi1 … (joint_if_entry … p))
511     (pi1 … (joint_if_exit … p)).
512>graph_code_has_point whd in match code; >mem_set_add
513@orb_Prop_r [elim (joint_if_entry ???) | elim (joint_if_exit ???) ]
514#x #H <graph_code_has_point @H
515qed.
516
517definition set_locals ≝
518  λglobals,pars.
519  λp : joint_internal_function globals pars.
520  λlocals.
521   mk_joint_internal_function globals pars
522    (joint_if_luniverse … p) (joint_if_runiverse … p) (joint_if_result … p)
523    (joint_if_params … p) locals (joint_if_stacksize … p)
524    (joint_if_code … p) (joint_if_entry … p) (joint_if_exit … p).
525
526definition joint_function ≝ λp,globals. fundef (joint_internal_function p globals).
527
528definition joint_program ≝
529 λp:params. program (λglobals. joint_function globals p) nat.
Note: See TracBrowser for help on using the repository browser.