[2828] | 1 | (* Front-end related includes *) |
---|
[1991] | 2 | include "Clight/label.ma". |
---|
[2019] | 3 | include "Clight/SimplifyCasts.ma". |
---|
[2475] | 4 | include "Clight/switchRemoval.ma". |
---|
[1991] | 5 | include "Clight/toCminor.ma". |
---|
| 6 | include "Cminor/toRTLabs.ma". |
---|
[2724] | 7 | include "RTLabs/CostCheck.ma". |
---|
| 8 | include "RTLabs/CostInj.ma". |
---|
[1991] | 9 | |
---|
[2828] | 10 | (* Back-end related includes *) |
---|
| 11 | include "RTLabs/RTLabsToRTL.ma". |
---|
| 12 | include "RTL/RTLToERTL.ma". |
---|
| 13 | include "ERTL/ERTLToERTLptr.ma". |
---|
| 14 | include "ERTLptr/ERTLptrToLTL.ma". |
---|
| 15 | include "LTL/LTLToLIN.ma". |
---|
| 16 | include "LIN/LINToASM.ma". |
---|
| 17 | |
---|
| 18 | (* List of all passes whose outputs can be observed *) |
---|
| 19 | inductive pass : Type[0] ≝ |
---|
| 20 | clight_pass: pass |
---|
| 21 | | clight_switch_removed_pass: pass |
---|
| 22 | | clight_label_pass: pass |
---|
| 23 | | clight_simplified_pass: pass |
---|
| 24 | | cminor_pass: pass |
---|
| 25 | | rtlabs_pass: pass |
---|
| 26 | | rtl_separate_pass: pass |
---|
| 27 | | rtl_uniq_pass: pass |
---|
| 28 | | ertl_pass: pass |
---|
| 29 | | ertlptr_pass: pass |
---|
| 30 | | ltl_pass: pass |
---|
| 31 | | lin_pass: pass. |
---|
| 32 | |
---|
[2841] | 33 | definition with_stack_model : Type[0] → Type[0] ≝ |
---|
| 34 | λA:Type[0].A × (ident → option ℕ). |
---|
| 35 | |
---|
[2828] | 36 | definition syntax_of_pass : pass → Type[0] ≝ |
---|
| 37 | λpass. |
---|
| 38 | match pass with |
---|
| 39 | [ clight_pass ⇒ clight_program |
---|
| 40 | | clight_switch_removed_pass ⇒ clight_program |
---|
| 41 | | clight_label_pass ⇒ clight_program |
---|
| 42 | | clight_simplified_pass ⇒ clight_program |
---|
| 43 | | cminor_pass ⇒ Cminor_program |
---|
| 44 | | rtlabs_pass ⇒ RTLabs_program |
---|
[2841] | 45 | | rtl_separate_pass ⇒ with_stack_model rtl_program |
---|
| 46 | | rtl_uniq_pass ⇒ with_stack_model rtl_program |
---|
| 47 | | ertl_pass ⇒ with_stack_model ertl_program |
---|
| 48 | | ertlptr_pass ⇒ with_stack_model ertlptr_program |
---|
| 49 | | ltl_pass ⇒ with_stack_model ltl_program |
---|
| 50 | | lin_pass ⇒ with_stack_model lin_program ]. |
---|
[2828] | 51 | |
---|
| 52 | definition observe_pass ≝ ∀pass. syntax_of_pass pass → unit. |
---|
| 53 | |
---|
| 54 | (* The compiler front-end *) |
---|
| 55 | definition front_end : |
---|
| 56 | observe_pass → clight_program → res (costlabel × clight_program × RTLabs_program) ≝ |
---|
| 57 | λobserve,p. |
---|
| 58 | let i ≝ observe clight_pass p in |
---|
[2475] | 59 | let p ≝ program_switch_removal p in |
---|
[2828] | 60 | let i ≝ observe clight_switch_removed_pass p in |
---|
[2319] | 61 | let 〈p',init_cost〉 ≝ clight_label p in |
---|
[2828] | 62 | let i ≝ observe clight_label_pass p' in |
---|
[2001] | 63 | let p ≝ simplify_program p' in |
---|
[2828] | 64 | let i ≝ observe clight_simplified_pass p in |
---|
[1991] | 65 | ! p ← clight_to_cminor p; |
---|
[2828] | 66 | let i ≝ observe cminor_pass p in |
---|
[2319] | 67 | let p ≝ cminor_to_rtlabs init_cost p in |
---|
[2828] | 68 | let i ≝ observe rtlabs_pass p in |
---|
[2724] | 69 | if check_cost_program p then |
---|
| 70 | if check_program_cost_injectivity p then |
---|
| 71 | (return 〈init_cost,p',p〉) |
---|
| 72 | else |
---|
| 73 | (Error ? (msg RepeatedCostLabel)) |
---|
| 74 | else |
---|
| 75 | (Error ? (msg BadCostLabelling)). |
---|
[1995] | 76 | |
---|
[2828] | 77 | (* The compiler back-end *) |
---|
[2841] | 78 | include "ERTLptr/uses.ma". (* Included by the untrusted code *) |
---|
[2700] | 79 | axiom compute_fixpoint : fixpoint_computer. |
---|
| 80 | axiom colour_graph : coloured_graph_computer. |
---|
[2505] | 81 | |
---|
[2841] | 82 | include "common/AssocList.ma". |
---|
| 83 | |
---|
| 84 | (* Inefficient, replace with Trie lookup *) |
---|
| 85 | definition lookup_stack_cost ≝ |
---|
| 86 | λP,p,id. |
---|
| 87 | assoc_list_lookup ?? id (eq_identifier …) (stack_cost P p). |
---|
| 88 | |
---|
[2774] | 89 | definition back_end : |
---|
[2828] | 90 | observe_pass → RTLabs_program → |
---|
[2774] | 91 | res (pseudo_assembly_program × stack_cost_model × nat) ≝ |
---|
[2828] | 92 | λobserve,p. |
---|
[1995] | 93 | let p ≝ rtlabs_to_rtl p in |
---|
[2841] | 94 | let st ≝ lookup_stack_cost … p in |
---|
| 95 | let i ≝ observe rtl_separate_pass 〈p,st〉 in |
---|
| 96 | let i ≝ observe rtl_uniq_pass 〈p,st〉 in |
---|
[1995] | 97 | let p ≝ rtl_to_ertl p in |
---|
[2841] | 98 | let st ≝ lookup_stack_cost … p in |
---|
| 99 | let i ≝ observe ertl_pass 〈p,st〉 in |
---|
[2697] | 100 | let p ≝ ertl_to_ertlptr p in |
---|
[2841] | 101 | let st ≝ lookup_stack_cost … p in |
---|
| 102 | let i ≝ observe ertlptr_pass 〈p,st〉 in |
---|
| 103 | let 〈p,stack_cost,max_stack〉 ≝ ertlptr_to_ltl compute_fixpoint colour_graph p in |
---|
| 104 | (* The two stack models are the same *) |
---|
| 105 | let st ≝ lookup_stack_cost … p in |
---|
| 106 | let i ≝ observe ltl_pass 〈p,st〉 in |
---|
| 107 | let st ≝ lookup_stack_cost … p in |
---|
[1995] | 108 | let p ≝ ltl_to_lin p in |
---|
[2841] | 109 | let st ≝ lookup_stack_cost … p in |
---|
| 110 | let i ≝ observe lin_pass 〈p,st〉 in |
---|
[2794] | 111 | ! p ← opt_to_res ? (msg AssemblyTooLarge) (lin_to_asm p) ; |
---|
| 112 | return 〈p,stack_cost,max_stack〉. |
---|
[1995] | 113 | |
---|
[2828] | 114 | (* The assembler *) |
---|
[2702] | 115 | include "ASM/Policy.ma". |
---|
[2794] | 116 | |
---|
[2754] | 117 | definition assembler : pseudo_assembly_program → res labelled_object_code ≝ |
---|
[1995] | 118 | λp. |
---|
[2762] | 119 | ! sigma_pol ← opt_to_res ? (msg Jump_expansion_failed) (jump_expansion' p); |
---|
[2702] | 120 | let sigma ≝ λppc. \fst sigma_pol ppc in |
---|
| 121 | let pol ≝ λppc. \snd sigma_pol ppc in |
---|
[1995] | 122 | OK ? (assembly p sigma pol). |
---|
| 123 | |
---|
[2828] | 124 | (* Cost lifting *) |
---|
[2505] | 125 | include "ASM/ASMCosts.ma". |
---|
| 126 | |
---|
[2753] | 127 | definition lift_cost_map_back_to_front : |
---|
| 128 | ∀clight, code_memory, lbls. |
---|
| 129 | let abstat ≝ ASM_abstract_status code_memory lbls in |
---|
| 130 | as_cost_map abstat → clight_cost_map clight ≝ |
---|
[2762] | 131 | λclight,code_memory,lbls,k,asm_cost_map. |
---|
[2753] | 132 | lift_sigma_map_id … 0 (* labels not present in out code get 0 *) |
---|
[2762] | 133 | (strong_decidable_in_codomain …) k asm_cost_map. |
---|
[2753] | 134 | |
---|
[2828] | 135 | (* Cost model computation *) |
---|
| 136 | include "ASM/ASMCostsSplit.ma". |
---|
[2753] | 137 | |
---|
[2774] | 138 | record compiler_output : Type[0] ≝ |
---|
| 139 | { c_labelled_object_code: labelled_object_code |
---|
| 140 | ; c_stack_cost: stack_cost_model |
---|
| 141 | ; c_max_stack: nat |
---|
| 142 | ; c_labelled_clight: clight_program |
---|
| 143 | ; c_clight_cost_map: clight_cost_map c_labelled_clight |
---|
| 144 | }. |
---|
| 145 | |
---|
[2828] | 146 | definition compile : observe_pass → clight_program → res compiler_output ≝ |
---|
| 147 | λobserve,p. |
---|
| 148 | ! 〈init_cost,p',p〉 ← front_end observe p; |
---|
| 149 | ! 〈p,stack_cost,max_stack〉 ← back_end observe p; |
---|
[2767] | 150 | ! p ← assembler p; |
---|
[2762] | 151 | let k ≝ ASM_cost_map p in |
---|
| 152 | let k' ≝ |
---|
| 153 | lift_cost_map_back_to_front p' (load_code_memory (oc p)) (costlabels p) k in |
---|
[2835] | 154 | return mk_compiler_output p stack_cost max_stack p' k'. |
---|