Changeset 1241


Ignore:
Timestamp:
Sep 21, 2011, 5:28:06 PM (8 years ago)
Author:
mulligan
Message:

changes for claudio

Location:
src/ERTL
Files:
5 edited

Legend:

Unmodified
Added
Removed
  • src/ERTL/ERTL.ma

    r1223 r1241  
    1313  | ertl_st_ext_frame_size: register → label → ertl_statement_extension.
    1414
     15definition ertl_params_: params_ ≝
     16  mk_params_ register register register register
     17    (move_registers × move_registers) register
     18      ertl_statement_extension unit (list register) nat.
     19
    1520definition ertl_params: params ≝
    16  mk_params
    17    register register register register
    18      (move_registers × move_registers) register
    19        ertl_statement_extension unit (list register) nat.
     21  mk_params ertl_params_ label.
    2022
    2123definition ertl_statement ≝ joint_statement ertl_params.
    2224
     25(*
    2326definition ertl_sem_params_ : ∀globals. sem_params_ ertl_params globals ≝
    2427 λglobals.
    2528  mk_sem_params_ ertl_params globals (graph (ertl_statement globals)) (lookup …).
     29*)
    2630
    2731definition ertl_internal_function ≝
    28   λglobals. joint_internal_function globals … (ertl_sem_params_ globals).
     32  joint_internal_function ertl_params.
    2933
    30 definition ertl_program ≝ λglobals. joint_program globals … (ertl_sem_params_ globals).
     34definition ertl_program ≝ joint_program ertl_params.
  • src/ERTL/ERTLToLTL.ma

    r1232 r1241  
    33include "ERTL/spill.ma".
    44include "ERTL/build.ma".
     5include "ERTL/uses.ma".
    56include "ERTL/Interference.ma".
    67include "ASM/Arithmetic.ma".
     
    7879  λglobals.
    7980  λint_fun.
    80     colour_locals + (joint_if_stacksize globals ertl_params (ertl_sem_params_ globals) int_fun).
     81    colour_locals + (joint_if_stacksize ertl_params globals int_fun).
    8182
    8283definition stacksize ≝
    8384  λglobals.
    8485  λint_fun.
    85     colour_locals + (joint_if_stacksize globals ertl_params (ertl_sem_params_ globals) int_fun).
     86    colour_locals + (joint_if_stacksize ertl_params globals int_fun).
    8687
    8788definition adjust_off ≝
     
    103104  λl.
    104105    let off ≝ adjust_off globals int_fun off in
    105     let luniv ≝ joint_if_luniverse globals … int_fun in
     106    let luniv ≝ joint_if_luniverse ertl_params globals int_fun in
    106107    let 〈l, graph, luniv〉 ≝ generate globals luniv graph (joint_st_sequential … globals (joint_instr_move … globals (from_acc r)) l) in
    107108    let 〈l, graph, luniv〉 ≝ generate globals luniv graph (joint_st_sequential … globals (joint_instr_load … globals it it it) l) in
     
    123124  λl.
    124125  let off ≝ adjust_off globals int_fun off in
    125   let luniv ≝ joint_if_luniverse globals … int_fun in
     126  let luniv ≝ joint_if_luniverse ertl_params globals int_fun in
    126127  let 〈l, graph, luniv〉 ≝ generate globals luniv graph (joint_st_sequential … globals (joint_instr_store ltl_params … globals it it it) l) in
    127128  let 〈l, graph, luniv〉 ≝ generate globals luniv graph (joint_st_sequential … globals (joint_instr_move … globals (to_acc r)) l) in
     
    147148      〈RegisterSST, l, graph, luniv〉
    148149  | decision_colour hwr ⇒
    149     let luniv ≝ joint_if_luniverse globals ertl_params (ertl_sem_params_ globals) int_fun in
     150    let luniv ≝ joint_if_luniverse ertl_params globals int_fun in
    150151      〈hwr, l, graph, luniv〉
    151152  ].
     
    160161  λstmt.
    161162  match lookup valuation coloured_graph (inl … r) with
    162   [ decision_colour hwr ⇒ generate globals (joint_if_luniverse globals ertl_params (ertl_sem_params_ globals) int_fun) graph (stmt hwr)
     163  [ decision_colour hwr ⇒ generate globals (joint_if_luniverse ertl_params globals int_fun) graph (stmt hwr)
    163164  | decision_spill off ⇒
    164165    let temphwr ≝ RegisterSST in
    165     let 〈l, graph, luniv〉 ≝ generate globals (joint_if_luniverse globals … int_fun) graph (stmt temphwr) in
     166    let 〈l, graph, luniv〉 ≝ generate globals (joint_if_luniverse ertl_params globals int_fun) graph (stmt temphwr) in
    166167    let 〈stmt, graph, luniv〉 ≝ get_stack globals int_fun graph temphwr (bitvector_of_nat … off) l in
    167168      generate globals luniv graph stmt
     
    179180    match src with
    180181    [ decision_colour src_hwr ⇒
    181       let luniv ≝ joint_if_luniverse globals ertl_params (ertl_sem_params_ globals) int_fun in
     182      let luniv ≝ joint_if_luniverse ertl_params globals int_fun in
    182183      if eq_Register dest_hwr src_hwr then
    183184        〈joint_st_goto … globals l, graph, luniv〉
     
    191192    [ decision_colour src_hwr ⇒ set_stack globals int_fun graph (bitvector_of_nat … dest_off) src_hwr l
    192193    | decision_spill src_off ⇒
    193       let luniv ≝ joint_if_luniverse globals … int_fun in
     194      let luniv ≝ joint_if_luniverse ertl_params globals int_fun in
    194195      if eq_nat dest_off src_off then
    195196        〈joint_st_goto … globals l, graph, luniv〉
     
    208209  λl: label.
    209210  if eq_nat (stacksize globals int_fun) 0 then
    210     〈joint_st_goto ltl_params globals l, graph, (joint_if_luniverse globals ertl_params (ertl_sem_params_ globals) int_fun)〉
     211    〈joint_st_goto ltl_params globals l, graph, (joint_if_luniverse ertl_params globals int_fun)〉
    211212  else
    212     let luniv ≝ joint_if_luniverse globals … int_fun in
     213    let luniv ≝ joint_if_luniverse ertl_params globals int_fun in
    213214    let 〈l, graph, luniv〉 ≝ generate globals luniv graph (joint_st_sequential ltl_params globals (joint_instr_move … globals (from_acc RegisterSPH)) l) in
    214215    let 〈l, graph, luniv〉 ≝ generate globals luniv graph (joint_st_sequential ltl_params globals (joint_instr_op2 … globals Sub it RegisterDPH) l) in
     
    227228  λl.
    228229  if eq_nat (stacksize globals int_fun) 0 then
    229     〈joint_st_goto ltl_params globals l, graph, joint_if_luniverse globals ertl_params (ertl_sem_params_ globals) int_fun〉
     230    〈joint_st_goto ltl_params globals l, graph, joint_if_luniverse ertl_params globals int_fun〉
    230231  else
    231     let luniv ≝ joint_if_luniverse globals … int_fun in
     232    let luniv ≝ joint_if_luniverse ertl_params globals int_fun in
    232233    let 〈l, graph, luniv〉 ≝ generate globals luniv graph (joint_st_sequential ltl_params globals (joint_instr_move … globals (from_acc RegisterSPH)) l) in
    233234    let 〈l, graph, luniv〉 ≝ generate globals luniv graph (joint_st_sequential ltl_params globals (joint_instr_op2 … globals Addc it RegisterSPH) l) in
     
    246247  match stmt with
    247248  [ joint_st_sequential seq l ⇒
    248     let luniv ≝ joint_if_luniverse globals ertl_params (ertl_sem_params_ globals) int_fun in
     249    let luniv ≝ joint_if_luniverse ertl_params globals int_fun in
    249250    match seq with
    250251    [ joint_instr_comment c ⇒
     
    258259    | joint_instr_push r ⇒
    259260      let 〈l, graph, luniv〉 ≝ generate globals luniv graph (joint_st_sequential … globals (joint_instr_push … globals it) l) in
    260       let int_fun ≝ set_luniverse globals ertl_params (ertl_sem_params_ globals) int_fun luniv in
     261      let int_fun ≝ set_luniverse ertl_params globals int_fun luniv in
    261262      let 〈l, graph, luniv〉 ≝ read globals int_fun valuation coloured_graph graph r (λhdw. joint_st_sequential … globals (joint_instr_move … globals (to_acc hdw)) l) in
    262263        〈joint_st_goto ltl_params globals l, graph, luniv〉
    263264    | joint_instr_cond srcr lbl_true ⇒
    264265      let 〈l, graph, luniv〉 ≝ generate globals luniv graph (joint_st_sequential … globals (joint_instr_cond … globals it lbl_true) l) in
    265       let int_fun ≝ set_luniverse globals ertl_params (ertl_sem_params_ globals) int_fun luniv in
     266      let int_fun ≝ set_luniverse ertl_params globals int_fun luniv in
    266267      let 〈l, graph, luniv〉 ≝ read globals int_fun valuation coloured_graph graph srcr (λhdw. joint_st_sequential … globals (joint_instr_move … globals (to_acc hdw)) l) in
    267268        〈joint_st_goto ltl_params globals l, graph, luniv〉
     
    273274      let 〈l, graph, luniv〉 ≝ generate globals luniv graph (joint_st_sequential … globals (joint_instr_move … globals (to_acc RegisterST0)) l) in
    274275      let 〈l, graph, luniv〉 ≝ generate globals luniv graph (joint_st_sequential … globals (joint_instr_move … globals (from_acc RegisterDPL)) l) in
    275       let int_fun ≝ set_luniverse globals ertl_params (ertl_sem_params_ globals) int_fun luniv in
     276      let int_fun ≝ set_luniverse ertl_params globals int_fun luniv in
    276277      let 〈l, graph, luniv〉 ≝ read globals int_fun valuation coloured_graph graph addr1 (λhdw. joint_st_sequential … globals (joint_instr_move … globals (to_acc hdw)) l) in
    277278      let 〈l, graph, luniv〉 ≝ generate globals luniv graph (joint_st_sequential … globals (joint_instr_move … globals (from_acc RegisterST0)) l) in
    278       let int_fun ≝ set_luniverse globals ertl_params (ertl_sem_params_ globals) int_fun luniv in
     279      let int_fun ≝ set_luniverse ertl_params globals int_fun luniv in
    279280      let 〈l, graph, luniv〉 ≝ read globals int_fun valuation coloured_graph graph addr2 (λhdw. joint_st_sequential … globals (joint_instr_move … globals (to_acc hdw)) l) in
    280281      let 〈l, graph, luniv〉 ≝ generate globals luniv graph (joint_st_sequential … globals (joint_instr_move … globals (from_acc RegisterST1)) l) in
     
    288289      let 〈l, graph, luniv〉 ≝ generate globals luniv graph (joint_st_sequential … globals (joint_instr_move … globals (to_acc RegisterST0)) l) in
    289290      let 〈l, graph, luniv〉 ≝ generate globals luniv graph (joint_st_sequential … globals (joint_instr_move … globals (from_acc RegisterDPL)) l) in
    290       let int_fun ≝ set_luniverse globals ertl_params (ertl_sem_params_ globals) int_fun luniv in
     291      let int_fun ≝ set_luniverse ertl_params globals int_fun luniv in
    291292      let 〈l, graph, luniv〉 ≝ read globals int_fun valuation coloured_graph graph addr1 (λhdw. joint_st_sequential … globals (joint_instr_move … globals (to_acc hdw)) l) in
    292293      let 〈l, graph, luniv〉 ≝ generate globals luniv graph (joint_st_sequential … globals (joint_instr_move … globals (from_acc RegisterST0)) l) in
    293       let int_fun ≝ set_luniverse globals ertl_params (ertl_sem_params_ globals) int_fun luniv in
     294      let int_fun ≝ set_luniverse ertl_params globals int_fun luniv in
    294295      let 〈l, graph, luniv〉 ≝ read globals int_fun valuation coloured_graph graph addr2 (λhdw. joint_st_sequential … globals (joint_instr_move … globals (to_acc hdw)) l) in
    295296        〈joint_st_goto ltl_params globals l, graph, luniv〉
     
    300301      let 〈l, graph, luniv〉 ≝ generate globals luniv graph (joint_st_sequential … globals (joint_instr_move … globals (from_acc hdw)) l) in
    301302      let 〈l, graph, luniv〉 ≝ generate globals luniv graph (joint_st_sequential … globals (joint_instr_op2 … globals op2 it RegisterB) l) in
    302       let luniv ≝ set_luniverse globals ertl_params (ertl_sem_params_ globals) int_fun luniv in
     303      let luniv ≝ set_luniverse ertl_params globals int_fun luniv in
    303304      let 〈l, graph, luniv〉 ≝ read globals int_fun valuation coloured_graph graph destr (λhdw. joint_st_sequential … globals (joint_instr_move … globals (to_acc hdw)) l) in
    304305      let 〈l, graph, luniv〉 ≝ generate globals luniv graph (joint_st_sequential … globals (joint_instr_move … globals (from_acc RegisterB)) l) in
    305       let luniv ≝ set_luniverse globals ertl_params (ertl_sem_params_ globals) int_fun luniv in
     306      let luniv ≝ set_luniverse ertl_params globals int_fun luniv in
    306307      let 〈l, graph, luniv〉 ≝ read globals int_fun valuation coloured_graph graph srcr (λhdw. joint_st_sequential … globals (joint_instr_move … globals (to_acc hdw)) l) in
    307308        〈joint_st_goto ltl_params globals l, graph, luniv〉
     
    310311      let 〈l, graph, luniv〉 ≝ generate globals luniv graph (joint_st_sequential … globals (joint_instr_move … globals (from_acc hdw)) l) in
    311312      let 〈l, graph, luniv〉 ≝ generate globals luniv graph (joint_st_sequential … globals (joint_instr_op1 … globals op1 it) l) in
    312       let int_fun ≝ set_luniverse globals ertl_params (ertl_sem_params_ globals) int_fun luniv in
     313      let int_fun ≝ set_luniverse ertl_params globals int_fun luniv in
    313314      let 〈l, graph, luniv〉 ≝ read globals int_fun valuation coloured_graph graph acc_a (λhdw. joint_st_sequential … globals (joint_instr_move … globals (to_acc hdw)) l) in
    314315        〈joint_st_goto ltl_params globals l, graph, luniv〉
     
    320321      let 〈l, graph, luniv〉 ≝ generate globals luniv graph (joint_st_sequential … globals (joint_instr_move … globals (from_acc hdw)) l) in
    321322      let 〈l, graph, luniv〉 ≝ generate globals luniv graph (joint_st_sequential … globals (joint_instr_opaccs … globals opaccs it it) l) in
    322       let luniv ≝ set_luniverse globals ertl_params (ertl_sem_params_ globals) int_fun luniv in
     323      let luniv ≝ set_luniverse ertl_params globals int_fun luniv in
    323324      let 〈l, graph, luniv〉 ≝ read globals int_fun valuation coloured_graph graph acc_a_reg (λhdw. joint_st_sequential … globals (joint_instr_move … globals (to_acc hdw)) l) in
    324325      let 〈l, graph, luniv〉 ≝ generate globals luniv graph (joint_st_sequential … globals (joint_instr_move … globals (from_acc RegisterB)) l) in
    325       let luniv ≝ set_luniverse globals ertl_params (ertl_sem_params_ globals) int_fun luniv in
     326      let luniv ≝ set_luniverse ertl_params globals int_fun luniv in
    326327      let 〈l, graph, luniv〉 ≝ read globals int_fun valuation coloured_graph graph acc_b_reg (λhdw. joint_st_sequential … globals (joint_instr_move … globals (to_acc hdw)) l) in
    327328      let 〈l, graph, luniv〉 ≝ generate globals luniv graph (joint_st_goto … globals l) in
    328       let luniv ≝ set_luniverse globals ertl_params (ertl_sem_params_ globals) int_fun luniv in
     329      let luniv ≝ set_luniverse ertl_params globals int_fun luniv in
    329330      let 〈hdw, l, graph, luniv〉 ≝ write globals int_fun valuation coloured_graph graph acc_b_reg l in
    330331      let 〈l, graph, luniv〉 ≝ generate globals luniv graph (joint_st_sequential … globals (joint_instr_move … globals (from_acc hdw)) l) in
    331332      let 〈l, graph, luniv〉 ≝ generate globals luniv graph (joint_st_sequential … globals (joint_instr_move … globals (to_acc RegisterB)) l) in
    332333      let 〈l, graph, luniv〉 ≝ generate globals luniv graph (joint_st_sequential … globals (joint_instr_opaccs … globals opaccs it it) l) in
    333       let luniv ≝ set_luniverse globals ertl_params (ertl_sem_params_ globals) int_fun luniv in
     334      let luniv ≝ set_luniverse ertl_params globals int_fun luniv in
    334335      let 〈l, graph, luniv〉 ≝ read globals int_fun valuation coloured_graph graph acc_a_reg (λhdw. joint_st_sequential … globals (joint_instr_move … globals (to_acc hdw)) l) in
    335336      let 〈l, graph, luniv〉 ≝ generate globals luniv graph (joint_st_sequential … globals (joint_instr_move … globals (from_acc RegisterB)) l) in
    336       let luniv ≝ set_luniverse globals ertl_params (ertl_sem_params_ globals) int_fun luniv in
     337      let luniv ≝ set_luniverse ertl_params globals int_fun luniv in
    337338      let 〈l, graph, luniv〉 ≝ read globals int_fun valuation coloured_graph graph acc_b_reg (λhdw. joint_st_sequential … globals (joint_instr_move … globals (to_acc hdw)) l) in
    338339        〈joint_st_goto ltl_params globals l, graph, luniv〉
     
    359360      let 〈l, graph, luniv〉 ≝ generate globals luniv graph (joint_st_sequential … globals (joint_instr_move … globals (to_acc RegisterDPH)) l) in
    360361      let 〈l, graph, luniv〉 ≝ generate globals luniv graph (joint_st_sequential … globals (joint_instr_address … globals lbl prf it it) l) in
    361       let int_fun ≝ set_luniverse globals ertl_params (ertl_sem_params_ globals) int_fun luniv in
     362      let int_fun ≝ set_luniverse ertl_params globals int_fun luniv in
    362363      let 〈hdw2, l, graph, luniv〉 ≝ write globals int_fun valuation coloured_graph graph dpl l in
    363364      let 〈l, graph, luniv〉 ≝ generate globals luniv graph (joint_st_sequential … globals (joint_instr_move … globals (from_acc hdw2)) l) in
     
    365366        〈joint_st_sequential ltl_params globals (joint_instr_address … globals lbl prf it it) l, graph, luniv〉
    366367    ]
    367   | joint_st_return ⇒ 〈joint_st_return … globals, graph, joint_if_luniverse globals … int_fun〉
    368   | joint_st_goto l ⇒ 〈joint_st_goto … globals l, graph, joint_if_luniverse globals … int_fun〉
     368  | joint_st_return ⇒ 〈joint_st_return … globals, graph, joint_if_luniverse ertl_params globals int_fun〉
     369  | joint_st_goto l ⇒ 〈joint_st_goto … globals l, graph, joint_if_luniverse ertl_params globals int_fun〉
    369370  | joint_st_extension ext ⇒
    370371    match ext with
     
    380381  λglobals.
    381382  λint_fun.
    382     ?.
     383  let uses ≝ examine_internal globals int_fun in ?.
    383384
    384385definition translate_funct ≝
  • src/ERTL/Interference.ma

    r1232 r1241  
    1 include "basics/types.ma".
    2 include "basics/list.ma".
    3 include "common/Graphs.ma".
    4 include "common/Order.ma".
    5 include "common/Registers.ma".
    61include "ERTL/ERTL.ma".
    72include "ERTL/liveness.ma".
    8 
    9 include "utilities/adt/table_adt.ma".
    10 include "utilities/adt/priority_set_adt.ma".
    11 include "utilities/adt/set_adt.ma".
    12 include "utilities/adt/set_table_adt.ma".
    13 include "utilities/adt/register_table.ma".
    143
    154definition vertex ≝ register ⊎ Register.
     
    3726axiom build: ∀valuation. coloured_graph valuation.
    3827
     28(*
    3929(* definition vertex_set ≝ set vertex. *)
    4030definition vertex_priority_set ≝ priority_set vertex.
     
    4333definition Register_set_table ≝ set_table vertex (set Register).
    4434definition Register_set ≝ set Register.
     35*)
    4536
    4637(*
  • src/ERTL/liveness.ma

    r1223 r1241  
    283283  λlabel.
    284284  λliveafter: valuation.
    285   match lookup ? ? (joint_if_graph … int_fun) label with
     285  match joint_if_lookup … int_fun label with
    286286  [ None      ⇒ ?
    287287  | Some stmt ⇒ statement_semantics globals stmt (liveafter label)
     
    296296  λlabel.
    297297  λliveafter: valuation.
    298   match lookup … (joint_if_graph … int_fun) label with
     298  match joint_if_lookup … int_fun label with
    299299  [ None      ⇒ ?
    300300  | Some stmt ⇒ set_fold ? ? (λsuccessor. λaccu: register_lattice.
  • src/ERTL/uses.ma

    r1188 r1241  
    11include "ERTL/ERTL.ma".
    22
    3 let rec assoc_list_find
    4   (A: Type[0]) (B: Type[0]) (eq_a: A → A → bool) (to_find: A)
    5   (def: B) (l: list (A × B))
    6     on l ≝
    7   match l with
    8   [ nil ⇒ def
    9   | cons hd tl ⇒
    10     if eq_a (\fst hd) to_find then
    11       \snd hd
    12     else
    13       assoc_list_find A B eq_a to_find def tl
     3include "utilities/adt/table_adt.ma".
     4
     5definition lookup: table register nat → register → nat ≝
     6  λuses.
     7  λr: register.
     8  match tbl_find … r uses with
     9  [ None      ⇒ 0
     10  | Some uses ⇒ uses
    1411  ].
    15      
    16 definition lookup ≝
    17   λuses.
    18   λr.
    19     assoc_list_find register nat (eq_identifier ?) uses 0 r.
     12
     13definition count: register → table register nat → ? ≝
     14  λr: register.
     15  λuses: table register nat.
     16    tbl_insert … r ((lookup uses r) + 1) uses.
     17 
     18definition examine_statement ≝
     19  λglobals: list ident.
     20  λstmt: ertl_statement globals.
     21  λuses: table register nat.
     22  match stmt with
     23  [ joint_st_sequential seq l ⇒
     24    match seq with
     25    [ joint_instr_comment c ⇒ uses
     26    | joint_instr_cost_label c ⇒ uses
     27    | joint_instr_move pair_regs ⇒
     28      let reg1 ≝ \fst pair_regs in
     29      let reg2 ≝ \snd pair_regs in
     30      match reg1 with
     31      [ pseudo p ⇒ count p uses
     32      | hardware h1 ⇒
     33        match reg2 with
     34        [ pseudo p ⇒ count p uses
     35        | hardware h2 ⇒ uses
     36        ]
     37      ]
     38    | joint_instr_clear_carry ⇒ uses
     39    | joint_instr_set_carry ⇒ uses
     40    | joint_instr_call_id _ _ ⇒ uses
     41    | joint_instr_pop r ⇒ count r uses
     42    | joint_instr_push r ⇒ count r uses
     43    | joint_instr_int r _ ⇒ count r uses
     44    | joint_instr_address lbl prf r1 r2 ⇒ count r1 (count r2 uses)
     45    | joint_instr_opaccs opaccs acc_a acc_b ⇒ count acc_a (count acc_b uses)
     46    | joint_instr_op1 op1 r1 ⇒ count r1 uses
     47    | joint_instr_op2 op2 r1 r2 ⇒ count r1 (count r2 uses)
     48    | joint_instr_load destr r1 r2 ⇒ count r1 (count r2 (count destr uses))
     49    | joint_instr_store srcr r1 r2 ⇒ count r1 (count r2 (count srcr uses))
     50    | joint_instr_cond srcr l2 ⇒ count srcr uses
     51    ]
     52  | joint_st_return ⇒ uses
     53  | joint_st_goto l ⇒ uses
     54  | joint_st_extension ext ⇒
     55    match ext with
     56    [ ertl_st_ext_new_frame l ⇒ uses
     57    | ertl_st_ext_del_frame l ⇒ uses
     58    | ertl_st_ext_frame_size r l ⇒ count r uses
     59    ]
     60  ].
     61
     62definition examine_internal ≝
     63  λglobals: list ident.
     64  λint_fun: ertl_internal_function globals.
     65    let uses ≝ tbl_fold ?? (examine_statement globals) (joint_if_graph … int_fun) (tbl_empty …) in
     66      lookup uses.
Note: See TracChangeset for help on using the changeset viewer.