source: src/ASM/AssemblyProofSplitSplit.ma @ 2122

Last change on this file since 2122 was 2122, checked in by sacerdot, 7 years ago

More stuff moved around in proper places

File size: 12.3 KB
Line 
1include "ASM/AssemblyProofSplit.ma".
2include "common/LabelledObjects.ma".
3
4definition instruction_has_label ≝
5  λid: Identifier.
6  λi.
7  match i with
8  [ Jmp j ⇒ j = id
9  | Call j ⇒ j = id
10  | Instruction instr ⇒
11    match instr with
12    [ JC j ⇒ j = id
13    | JNC j ⇒ j = id
14    | JZ j ⇒ j = id
15    | JNZ j ⇒ j = id
16    | JB _ j ⇒ j = id
17    | JBC _ j ⇒ j = id
18    | DJNZ _ j ⇒ j = id
19    | CJNE _ j ⇒ j = id
20    | _ ⇒ False
21    ]
22  | _ ⇒ False
23  ].
24 
25
26definition is_well_labelled_p ≝
27  λinstr_list.
28  ∀id: Identifier.
29  ∀ppc. ∀ppc_ok.
30  ∀i.
31    fetch_pseudo_instruction instr_list ppc ppc_ok = i →
32      instruction_has_label id (\fst i) →
33        occurs_exactly_once ASMTag pseudo_instruction id instr_list.
34
35lemma short_jump_cond_ok:
36  ∀v1, v2: Word.
37  ∀is_possible, offset.
38    〈is_possible, offset〉 = short_jump_cond v1 v2 →
39      is_possible → v2 = add 16 v1 (sign_extension offset).
40  #v1 #v2 #is_possible #offset
41  whd in match short_jump_cond; normalize nodelta
42  @pair_elim #result #flags #sub16_refl
43  @pair_elim #upper #lower #vsplit_refl
44  inversion (get_index' bool ???) #get_index_refl normalize nodelta
45  #relevant destruct(relevant) #relevant
46  [1:
47    @(sub_16_to_add_16_8_1 … flags)
48  |2:
49    @(sub_16_to_add_16_8_0 … flags)
50  ]
51  try assumption >sub16_refl
52  <(eq_bv_eq … relevant)
53  >(vsplit_ok … (sym_eq … vsplit_refl)) %
54qed.
55
56lemma absolute_jump_cond_ok:
57  ∀v1, v2: Word.
58  ∀is_possible, offset, v1_upper, v1_lower.
59    〈is_possible, offset〉 = absolute_jump_cond v1 v2 →
60      〈v1_upper, v1_lower〉 = vsplit ? 5 11 v1 →
61        is_possible → v2 = v1_upper @@ offset.
62  #v1 #v2 #is_possible #offset #v1_upper #v1_lower
63  whd in match absolute_jump_cond; normalize nodelta
64  @pair_elim #fst_5_addr #rest_addr #vsplit_v2_refl
65  @pair_elim #fst_5_pc #rest_pc #vsplit_v1_refl
66  #relevant destruct(relevant) normalize nodelta #relevant
67  destruct(relevant) #relevant
68  <(vsplit_ok … (sym_eq … vsplit_v2_refl))
69  >(eq_bv_eq … relevant) %
70qed.
71       
72theorem main_thm:
73  ∀M, M': internal_pseudo_address_map.
74  ∀program: pseudo_assembly_program.
75  ∀is_well_labelled: is_well_labelled_p (\snd program).
76  ∀sigma: Word → Word.
77  ∀policy: Word → bool.
78  ∀sigma_policy_specification_witness: sigma_policy_specification program sigma policy.
79  ∀ps: PseudoStatus program.
80  ∀program_counter_in_bounds: nat_of_bitvector 16 (program_counter … ps) < |\snd program|.
81    next_internal_pseudo_address_map M program ps program_counter_in_bounds = Some … M' →
82      ∃n. execute n … (status_of_pseudo_status M … ps sigma policy) =
83        status_of_pseudo_status M' …
84          (execute_1_pseudo_instruction program (ticks_of program sigma policy) ps program_counter_in_bounds) sigma policy.
85  #M #M' * #preamble #instr_list #is_well_labelled_witness #sigma #policy #sigma_policy_witness #ps
86  letin ppc ≝ (program_counter pseudo_assembly_program ? ps) #ppc_in_bounds
87  change with (next_internal_pseudo_address_map0 ????? = ? → ?)
88  generalize in match (fetch_assembly_pseudo2 〈preamble,instr_list〉 sigma policy sigma_policy_witness ppc ppc_in_bounds) in ⊢ ?;
89  @pair_elim #labels #costs #create_label_cost_refl normalize nodelta
90  @pair_elim #assembled #costs' #assembly_refl normalize nodelta
91  lapply (pair_destruct_1 ????? (sym_eq ??? assembly_refl)) #EQassembled
92  @pair_elim #pi #newppc #fetch_pseudo_refl normalize nodelta
93  @(pose … (λx. address_of_word_labels_code_mem instr_list x)) #lookup_labels #EQlookup_labels
94  @(pose … (λx. lookup_def … (construct_datalabels preamble) x (zero 16))) #lookup_datalabels #EQlookup_datalabels
95  whd in match execute_1_pseudo_instruction; normalize nodelta
96  whd in match ticks_of; normalize nodelta >fetch_pseudo_refl normalize nodelta
97  lapply (snd_fetch_pseudo_instruction instr_list ppc ppc_in_bounds) >fetch_pseudo_refl #EQnewppc >EQnewppc
98  lapply (snd_assembly_1_pseudoinstruction_ok 〈preamble,instr_list〉 … sigma policy sigma_policy_witness … ppc ? pi … EQlookup_labels EQlookup_datalabels ?)
99  [1: >fetch_pseudo_refl % |2: skip ]
100  #assm1 #assm2 #assm3 generalize in match assm2; generalize in match assm3;
101  generalize in match assm1; -assm1 -assm2 -assm3
102  normalize nodelta
103  inversion pi
104  [2,3:
105    #arg #_
106    (* XXX: we first work on sigma_increment_commutation *)
107    #sigma_increment_commutation
108    normalize in match (assembly_1_pseudoinstruction ??????) in sigma_increment_commutation;
109    (* XXX: we work on the maps *)
110    whd in ⊢ (??%? → ?); @Some_Some_elim #map_refl_assm <map_refl_assm
111    (* XXX: we assume the fetch_many hypothesis *)
112    #fetch_many_assm
113    (* XXX: we give the existential *)
114    %{0}
115    whd in match (execute_1_pseudo_instruction0 ?????);
116    (* XXX: work on the left hand side of the equality *)
117    whd in ⊢ (??%?);
118    @split_eq_status try %
119    /demod/ >add_commutative <add_zero % (*CSC: auto not working, why? *)
120  |6: (* Mov *)
121    #arg1 #arg2 #_
122    (* XXX: we first work on sigma_increment_commutation *)
123    #sigma_increment_commutation
124    normalize in match (assembly_1_pseudoinstruction ??????) in sigma_increment_commutation;
125    (* XXX: we work on the maps *)
126    whd in ⊢ (??%? → ?); @Some_Some_elim #map_refl_assm <map_refl_assm
127    (* XXX: we assume the fetch_many hypothesis *)
128    #fetch_many_assm
129    (* XXX: we give the existential *)
130    %{1}
131    whd in match (execute_1_pseudo_instruction0 ?????);
132    (* XXX: work on the left hand side of the equality *)
133    whd in ⊢ (??%?); whd in match (program_counter ???);
134    (* XXX: execute fetches some more *)
135    whd in match code_memory_of_pseudo_assembly_program; normalize nodelta
136    whd in fetch_many_assm;
137    >EQassembled in fetch_many_assm;
138    cases (fetch ??) * #instr #newpc #ticks normalize nodelta *
139    #eq_instr
140    #fetch_many_assm whd in fetch_many_assm;
141    lapply (eq_bv_eq … fetch_many_assm) -fetch_many_assm #EQnewpc
142    destruct whd in ⊢ (??%?);
143    (* XXX: now we start to work on the mk_PreStatus equality *)
144    (* XXX: lhs *)
145    change with (set_arg_16 ????? = ?)
146    >set_program_counter_mk_Status_commutation
147    >set_clock_mk_Status_commutation
148    >set_arg_16_mk_Status_commutation
149    (* XXX: rhs *)
150    change with (status_of_pseudo_status ?? (set_arg_16 pseudo_assembly_program 〈preamble, instr_list〉 ?? arg1) ??) in ⊢ (???%);
151    >set_program_counter_mk_Status_commutation
152    >set_clock_mk_Status_commutation
153    >set_arg_16_mk_Status_commutation in ⊢ (???%);
154    (* here we are *)
155    @split_eq_status try %
156    [1:
157      assumption
158    |2:
159      @special_function_registers_8051_set_arg_16 %
160    ]
161  |1: (* Instruction *)
162    #instr #_ #EQP #EQnext #fetch_many_assm
163    @(main_lemma_preinstruction M M' preamble instr_list 〈preamble, instr_list〉 (refl …) sigma policy sigma_policy_witness
164      ps ppc ? labels costs create_label_cost_refl newppc lookup_labels EQlookup_labels lookup_datalabels EQlookup_datalabels
165      EQnewppc instr (ticks_of0 〈preamble, instr_list〉 sigma policy ppc (Instruction instr)) (refl …)
166      (λx:Identifier. λy:PreStatus pseudo_assembly_program 〈preamble, instr_list〉. address_of_word_labels 〈preamble, instr_list〉 x) (refl …) (set_program_counter pseudo_assembly_program 〈preamble, instr_list〉 ps (add 16 ppc (bitvector_of_nat 16 1)))
167      (refl …) ? (refl …))
168    try assumption try % >assembly_refl assumption
169  |4: (* Jmp *)
170    #arg1 #pi_refl
171    (* XXX: we first work on sigma_increment_commutation *)
172    whd in match (assembly_1_pseudoinstruction ??????) in ⊢ (% → ?);
173    whd in match (expand_pseudo_instruction ??????);
174    inversion (short_jump_cond ??) #sj_possible #offset #sjc_refl normalize nodelta
175    inversion (sj_possible ∧ ¬ policy ?) #sj_possible_refl normalize nodelta
176    [2:
177      inversion (absolute_jump_cond ??) #mj_possible #address #mjc_refl normalize nodelta
178      inversion (mj_possible ∧ ¬ policy ?) #mj_possible_refl normalize nodelta
179    ]
180    #sigma_increment_commutation
181    normalize in sigma_increment_commutation:(???(???(??%)));
182    (* XXX: we work on the maps *)
183    whd in ⊢ (??%? → ?); @Some_Some_elim #map_refl_assm <map_refl_assm
184    (* XXX: we assume the fetch_many hypothesis *)
185    * #fetch_refl #fetch_many_assm
186    (* XXX: we give the existential *)
187    %{1}
188    (* XXX: work on the left hand side of the equality *)
189    whd in ⊢ (??%?); whd in match (program_counter ???);
190    (* XXX: execute fetches some more *)
191    whd in match code_memory_of_pseudo_assembly_program; normalize nodelta
192    whd in fetch_many_assm;
193    >EQassembled in fetch_refl; #fetch_refl <fetch_refl
194    lapply (eq_bv_eq … fetch_many_assm) -fetch_many_assm #EQnewpc
195    whd in ⊢ (??%%);
196    (* XXX: now we start to work on the mk_PreStatus equality *)
197    (* XXX: lhs *)
198    (* XXX: rhs *)
199    (* here we are *)
200    @split_eq_status try % /demod nohyps/
201    [1,3,4:
202      change with (add ???) in match (\snd (half_add ???));
203      whd in match execute_1_pseudo_instruction0; normalize nodelta
204      /demod nohyps/ >set_clock_set_program_counter
205      >program_counter_set_program_counter
206      whd in ⊢ (??%?); normalize nodelta whd in match address_of_word_labels; normalize nodelta
207      lapply (create_label_cost_map_ok 〈preamble, instr_list〉) >create_label_cost_refl
208      normalize nodelta #address_of_word_labels_assm <address_of_word_labels_assm
209      [1:
210        >EQnewpc
211        inversion (vsplit bool ???) #pc_bu #pc_bl #vsplit_refl normalize nodelta
212        @sym_eq >address_of_word_labels_assm
213        [1:
214          >EQlookup_labels in mjc_refl; #mjc_refl
215          @(absolute_jump_cond_ok ?????? (sym_eq … mjc_refl) (sym_eq … vsplit_refl))
216          >(andb_true_l … mj_possible_refl) @I
217        ]
218      |3:
219        >EQlookup_labels normalize nodelta
220        >address_of_word_labels_assm try %
221      |5:
222        >EQnewpc
223        inversion (half_add ???) #carry #new_pc #half_add_refl normalize nodelta
224        @sym_eq >address_of_word_labels_assm
225        [1:
226          >EQlookup_labels in sjc_refl; #sjc_refl
227          >(pair_destruct_2 ????? (sym_eq … half_add_refl))
228          @(short_jump_cond_ok ???? (sym_eq … sjc_refl))
229          >(andb_true_l … sj_possible_refl) @I
230        ]
231      ]
232      @(is_well_labelled_witness … fetch_pseudo_refl)
233      >pi_refl %
234    |2:
235      whd in ⊢ (??(?%%)%);
236      cut (∃b1,b2,b3,b4,b5,b6,b7,b8,b9,b10,b11. address = [[b1;b2;b3;b4;b5;b6;b7;b8;b9;b10;b11]])
237      [1:
238        cases daemon (* XXX: easy but massive proof, move into separate lemma *)
239      |2:
240        * * * * * * * #b4 * #b5
241        * #b6 * #b7 * #b8 * #b9 * #b10 * #b11 #address_refl >address_refl
242        normalize in match (fetch ??); <plus_n_Sm @eq_f
243        @commutative_plus
244      ]
245    ]
246  |5: (* Call *)
247    #arg1 #_
248    (* XXX: we first work on sigma_increment_commutation *)
249    #sigma_increment_commutation
250    normalize in match (assembly_1_pseudoinstruction ??????) in sigma_increment_commutation;
251    (* XXX: we work on the maps *)
252    whd in ⊢ (??%? → ?); @Some_Some_elim #map_refl_assm <map_refl_assm
253    (* XXX: we assume the fetch_many hypothesis *)
254    #fetch_many_assm
255    (* XXX: we give the existential *)
256    %{1}
257    whd in match (execute_1_pseudo_instruction0 ?????);
258    (* XXX: work on the left hand side of the equality *)
259    whd in ⊢ (??%?); whd in match (program_counter ???); <EQppc
260    (* XXX: execute fetches some more *)
261    whd in match code_memory_of_pseudo_assembly_program; normalize nodelta
262    whd in fetch_many_assm;
263    >EQassembled in fetch_many_assm;
264    cases (fetch ??) * #instr #newpc #?ticks normalize nodelta *
265    #eq_instr
266    #fetch_many_assm whd in fetch_many_assm;
267    lapply (eq_bv_eq … fetch_many_assm) -fetch_many_assm #EQnewpc
268    destruct whd in ⊢ (??%?);
269    (* XXX: now we start to work on the mk_PreStatus equality *)
270    (* XXX: lhs *)
271    change with (set_arg_16 ????? = ?)
272    >set_program_counter_mk_Status_commutation
273    >set_clock_mk_Status_commutation
274    >set_arg_16_mk_Status_commutation
275    (* XXX: rhs *)
276    change with (status_of_pseudo_status ?? (set_arg_16 pseudo_assembly_program 〈preamble, instr_list〉 ?? arg1) ??) in ⊢ (???%);
277    >set_program_counter_mk_Status_commutation
278    >set_clock_mk_Status_commutation
279    >set_arg_16_mk_Status_commutation in ⊢ (???%);
280    (* here we are *)
281    @split_eq_status //
282    [1:
283      assumption
284    |2:
285      @special_function_registers_8051_set_arg_16
286      [2: %
287      |1: //
288      ]
289    ]
290  ]
291qed.
Note: See TracBrowser for help on using the repository browser.