1 | include "Clight/label.ma". |
---|
2 | include "Clight/SimplifyCasts.ma". |
---|
3 | include "Clight/switchRemoval.ma". |
---|
4 | include "Clight/toCminor.ma". |
---|
5 | include "Cminor/initialisation.ma". |
---|
6 | include "Cminor/toRTLabs.ma". |
---|
7 | include "RTLabs/CostCheck.ma". |
---|
8 | include "RTLabs/CostInj.ma". |
---|
9 | |
---|
10 | definition front_end : clight_program → res (costlabel × clight_program × RTLabs_program) ≝ |
---|
11 | λp. |
---|
12 | let p ≝ program_switch_removal p in |
---|
13 | let 〈p',init_cost〉 ≝ clight_label p in |
---|
14 | let p ≝ simplify_program p' in |
---|
15 | ! p ← clight_to_cminor p; |
---|
16 | let p ≝ cminor_to_rtlabs init_cost p in |
---|
17 | if check_cost_program p then |
---|
18 | if check_program_cost_injectivity p then |
---|
19 | (return 〈init_cost,p',p〉) |
---|
20 | else |
---|
21 | (Error ? (msg RepeatedCostLabel)) |
---|
22 | else |
---|
23 | (Error ? (msg BadCostLabelling)). |
---|
24 | |
---|
25 | include "RTLabs/RTLabsToRTL.ma". |
---|
26 | include "RTL/RTLToERTL.ma". |
---|
27 | include "ERTL/ERTLToERTLptr.ma". |
---|
28 | include "ERTLptr/ERTLptrToLTL.ma". |
---|
29 | include "LTL/LTLToLIN.ma". |
---|
30 | include "LIN/LINToASM.ma". |
---|
31 | |
---|
32 | axiom compute_fixpoint : fixpoint_computer. |
---|
33 | axiom colour_graph : coloured_graph_computer. |
---|
34 | |
---|
35 | definition back_end : RTLabs_program → pseudo_assembly_program ≝ |
---|
36 | λp. |
---|
37 | let p ≝ rtlabs_to_rtl p in |
---|
38 | let p ≝ rtl_to_ertl p in |
---|
39 | let p ≝ ertl_to_ertlptr p in |
---|
40 | let p ≝ ertlptr_to_ltl compute_fixpoint colour_graph p in (* TODO: abstract over colouring *) |
---|
41 | let p ≝ ltl_to_lin p in |
---|
42 | lin_to_asm p. |
---|
43 | |
---|
44 | (* JHM: minimum needed for assembler to typecheck *) |
---|
45 | (* JHM: moved from ASMCostsSplit.ma *) |
---|
46 | (* JHM: should move elsewhere in ASM/ *) |
---|
47 | definition object_code ≝ list Byte. |
---|
48 | definition costlabel_map ≝ BitVectorTrie costlabel 16. |
---|
49 | |
---|
50 | include "ASM/Policy.ma". |
---|
51 | (* Equivalent to the inclusion of ASM/Policy.ma, waiting for that slow |
---|
52 | file to compile |
---|
53 | include "ASM/PolicyStep.ma". |
---|
54 | axiom jump_expansion': ∀program:preamble × (Σl:list labelled_instruction.lt (S (|l|)) 2^16 ∧ is_well_labelled_p l). |
---|
55 | option (Σsigma_policy:(Word → Word) × (Word → bool). |
---|
56 | let 〈sigma,policy〉≝ sigma_policy in |
---|
57 | sigma_policy_specification 〈\fst program,\snd program〉 sigma policy). *) |
---|
58 | |
---|
59 | definition assembler : pseudo_assembly_program → res (object_code × costlabel_map) ≝ |
---|
60 | λp. |
---|
61 | let 〈preamble, list_instr〉 ≝ p in |
---|
62 | (* TODO: fail if p is too large. *) |
---|
63 | let p' ≝ 〈preamble, list_instr〉 in |
---|
64 | ! sigma_pol ← opt_to_res ? (msg Jump_expansion_failed) (jump_expansion' p'); |
---|
65 | let sigma ≝ λppc. \fst sigma_pol ppc in |
---|
66 | let pol ≝ λppc. \snd sigma_pol ppc in |
---|
67 | OK ? (assembly p sigma pol). |
---|
68 | cases daemon |
---|
69 | qed. |
---|
70 | |
---|
71 | include "ASM/ASMCosts.ma". |
---|
72 | |
---|
73 | definition lift_cost_map_back_to_front : |
---|
74 | ∀clight, code_memory, lbls. |
---|
75 | let abstat ≝ ASM_abstract_status code_memory lbls in |
---|
76 | (∀l. (as_cost_labelled abstat l) + ¬(as_cost_labelled abstat l)) → |
---|
77 | as_cost_map abstat → clight_cost_map clight ≝ |
---|
78 | λclight,code_memory,lbls,dec,k,asm_cost_map. |
---|
79 | lift_sigma_map_id … 0 (* labels not present in out code get 0 *) |
---|
80 | dec k asm_cost_map. |
---|
81 | |
---|
82 | include "ASM/ASMCostsSplit.ma". |
---|
83 | |
---|
84 | (*CSC: move the next definitions, e.g. in BitVectorTrie *) |
---|
85 | definition in_codomain: ∀A:Type[0].∀n:nat. BitVectorTrie A n → A → Prop ≝ |
---|
86 | λA,n,m,a. ∃k:BitVector n. lookup_opt … k m = Some … a. |
---|
87 | |
---|
88 | definition strong_decidable: Prop → Type[0] ≝ |
---|
89 | λP:Prop. P + ¬ P. |
---|
90 | |
---|
91 | lemma strong_decidable_in_codomain: |
---|
92 | ∀A:DeqSet.∀n:nat.∀m: BitVectorTrie A n.∀a:A. |
---|
93 | strong_decidable (in_codomain A n m a). |
---|
94 | #A #n #m elim m |
---|
95 | [ normalize #a' #a inversion (a' == a) #H |
---|
96 | [ %1 %{(VEmpty …)} >(\P H) % |
---|
97 | | %2 % * #_ #EQ destruct lapply (\Pf H) /2/ ] |
---|
98 | | -n #n #L #R #Hl #Hr #a |
---|
99 | cases (Hl a) -Hl [#K %1 cases K #k #H %{(false:::k)} <H % ] #Hl |
---|
100 | cases (Hr a) -Hr [#K %1 cases K #k #H %{(true:::k)} <H % ] #Hr |
---|
101 | %2 % * #k cases (BitVector_Sn … k) ** #tl #EQ >EQ whd in ⊢ (??%? → ?); |
---|
102 | normalize nodelta whd in match (tail ???); #abs [ cases Hr | cases Hl ] /3/ |
---|
103 | | #n #A %2 % * #x normalize #abs destruct ] |
---|
104 | qed. |
---|
105 | |
---|
106 | definition compile : clight_program → |
---|
107 | res (object_code × costlabel_map × (𝚺labelled:clight_program. clight_cost_map labelled)) ≝ |
---|
108 | λp. |
---|
109 | ! 〈init_cost,p',p〉 ← front_end p; |
---|
110 | let p ≝ back_end p in |
---|
111 | ! p ← assembler p; |
---|
112 | let k ≝ ASM_cost_map p ? in |
---|
113 | let k' ≝ lift_cost_map_back_to_front |
---|
114 | p' |
---|
115 | (load_code_memory (\fst p)) |
---|
116 | (\snd p) |
---|
117 | ? k |
---|
118 | in |
---|
119 | return 〈p, ❬p', k'❭〉. |
---|
120 | [ @strong_decidable_in_codomain |
---|
121 | | cases daemon ] |
---|
122 | qed. |
---|