From d75f2e734f38dfc522dca72ce94b0477e029db28 Mon Sep 17 00:00:00 2001 From: Léo Gourdin Date: Mon, 25 Jan 2021 11:35:29 +0100 Subject: Hashmap in peephole --- aarch64/PeepholeOracle.ml | 260 ++++++++++++++++++++-------------------------- 1 file changed, 110 insertions(+), 150 deletions(-) (limited to 'aarch64') diff --git a/aarch64/PeepholeOracle.ml b/aarch64/PeepholeOracle.ml index 83e454e7..18f41fed 100644 --- a/aarch64/PeepholeOracle.ml +++ b/aarch64/PeepholeOracle.ml @@ -64,6 +64,7 @@ let is_valid_str64 b1 b2 n1 n2 = else false let dreg_of_ireg r = IR (RR1 r) + let dreg_of_freg r = FR r (* Return true if an intermediate @@ -76,8 +77,7 @@ let verify_load_affect reg rd b rev = (* Return true if an intermediate * read eliminates the potential * candidate *) -let verify_load_read reg rd b rev = - dreg_eq reg rd +let verify_load_read reg rd b rev = dreg_eq reg rd (* Return true if an intermediate * affectation eliminates the potential @@ -86,15 +86,9 @@ let verify_store_affect reg rs b rev = let b = IR b in dreg_eq reg b || dreg_eq reg rs -type ph_type = - | P32 - | P32f - | P64 - | P64f +type ph_type = P32 | P32f | P64 | P64f -type inst_type = - | Ldr of ph_type - | Str of ph_type +type inst_type = Ldr of ph_type | Str of ph_type let ph_ty_to_string = function | Ldr P32 -> "ldr32" @@ -108,6 +102,8 @@ let ph_ty_to_string = function let print_ph_ty chan v = output_string chan (ph_ty_to_string v) +let symb_mem = Hashtbl.create 9 + (* Affect a symbolic memory list of potential replacements * for a given write in reg *) let rec affect_symb_mem reg insta pot_rep stype rev = @@ -166,8 +162,9 @@ let update_pot_rep_addressing a insta pot_rep stype rev = (* Update a symbolic memory list of potential replacements * for any basic instruction *) -let update_pot_rep_basic inst insta pot_rep stype rev = - match inst with +let update_pot_rep_basic inst insta stype rev = + let pot_rep = Hashtbl.find symb_mem stype in + (match inst with | PArith i -> ( match i with | PArithP (_, rd) -> @@ -218,7 +215,7 @@ let update_pot_rep_basic inst insta pot_rep stype rev = | Pcset (rd, _) -> pot_rep := affect_symb_mem (dreg_of_ireg rd) insta !pot_rep stype rev | Pfmovi (_, rd, rs) -> ( - pot_rep := affect_symb_mem (dreg_of_freg rd) insta !pot_rep stype rev; + pot_rep := affect_symb_mem (dreg_of_freg rd) insta !pot_rep stype rev; match rs with | RR0 rs -> pot_rep := @@ -228,7 +225,7 @@ let update_pot_rep_basic inst insta pot_rep stype rev = pot_rep := affect_symb_mem rd insta !pot_rep stype rev; pot_rep := read_symb_mem rs1 insta !pot_rep stype rev; pot_rep := read_symb_mem rs2 insta !pot_rep stype rev - | Pfnmul (_, rd, rs1, rs2) -> + | Pfnmul (_, rd, rs1, rs2) -> pot_rep := affect_symb_mem (dreg_of_freg rd) insta !pot_rep stype rev; pot_rep := read_symb_mem (dreg_of_freg rs1) insta !pot_rep stype rev; pot_rep := read_symb_mem (dreg_of_freg rs2) insta !pot_rep stype rev) @@ -242,10 +239,8 @@ let update_pot_rep_basic inst insta pot_rep stype rev = pot_rep := affect_symb_mem rd insta !pot_rep stype rev; update_pot_rep_addressing a insta pot_rep stype rev | Pldp (_, rd1, rd2, _, _, a) -> - pot_rep := - affect_symb_mem rd1 insta !pot_rep stype rev; - pot_rep := - affect_symb_mem rd2 insta !pot_rep stype rev; + pot_rep := affect_symb_mem rd1 insta !pot_rep stype rev; + pot_rep := affect_symb_mem rd2 insta !pot_rep stype rev; update_pot_rep_addressing a insta pot_rep stype rev) | _ -> pot_rep := []) | PStore _ -> ( @@ -266,7 +261,8 @@ let update_pot_rep_basic inst insta pot_rep stype rev = | Pcvtx2w rd -> pot_rep := affect_symb_mem (dreg_of_ireg rd) insta !pot_rep stype rev; pot_rep := read_symb_mem (dreg_of_ireg rd) insta !pot_rep stype rev - | Pnop -> () + | Pnop -> ()); + Hashtbl.replace symb_mem stype pot_rep (* This is useful to manage the case were the immofs * of the first ldr/str is greater than the second one *) @@ -294,24 +290,28 @@ let trans_sti (sti : store_rs_a) : store_rs1_rs2_a = | _ -> failwith "trans_sti: Found a non compatible store to translate" let is_compat_load (ldi : load_rd_a) = - match ldi with Pldrw | Pldrw_a | Pldrx | Pldrx_a | Pldrs | Pldrd | Pldrd_a-> true | _ -> false + match ldi with + | Pldrw | Pldrw_a | Pldrx | Pldrx_a | Pldrs | Pldrd | Pldrd_a -> true + | _ -> false let are_compat_load (ldi1 : load_rd_a) (ldi2 : load_rd_a) = match ldi1 with | Pldrw | Pldrw_a -> ( match ldi2 with Pldrw | Pldrw_a -> true | _ -> false) | Pldrx | Pldrx_a -> ( match ldi2 with Pldrx | Pldrx_a -> true | _ -> false) - | Pldrs -> (match ldi2 with Pldrs -> true | _ -> false) + | Pldrs -> ( match ldi2 with Pldrs -> true | _ -> false) | Pldrd | Pldrd_a -> ( match ldi2 with Pldrd | Pldrd_a -> true | _ -> false) | _ -> false let is_compat_store (sti : store_rs_a) = - match sti with Pstrw | Pstrw_a | Pstrx | Pstrx_a | Pstrs | Pstrd | Pstrd_a -> true | _ -> false + match sti with + | Pstrw | Pstrw_a | Pstrx | Pstrx_a | Pstrs | Pstrd | Pstrd_a -> true + | _ -> false let are_compat_store (sti1 : store_rs_a) (sti2 : store_rs_a) = match sti1 with | Pstrw | Pstrw_a -> ( match sti2 with Pstrw | Pstrw_a -> true | _ -> false) | Pstrx | Pstrx_a -> ( match sti2 with Pstrx | Pstrx_a -> true | _ -> false) - | Pstrs -> (match sti2 with Pstrs -> true | _ -> false) + | Pstrs -> ( match sti2 with Pstrs -> true | _ -> false) | Pstrd | Pstrd_a -> ( match sti2 with Pstrd | Pstrd_a -> true | _ -> false) | _ -> false @@ -356,8 +356,8 @@ let rec search_compat_rep r2 b2 n2 insta pot_rep stype = if is_valid_str b1 b2 n1 n2 stype then Some (h0, chunk_store st1, rs1, b1, n1) else search_compat_rep r2 b2 n2 insta t0 stype - | _ -> - failwith "search_compat_rep: Found an inconsistent inst in pot_rep") + | _ -> failwith "search_compat_rep: Found an inconsistent inst in pot_rep" + ) (* Try to find the index of the first previous compatible * replacement in a given symbolic memory (when iterating in the reversed list) *) @@ -376,49 +376,51 @@ let rec search_compat_rep_inv r2 b2 n2 insta pot_rep stype = else search_compat_rep_inv r2 b2 n2 insta t0 stype | _ -> failwith - "search_compat_rep_inv: Found an inconsistent inst in pot_rep") + "search_compat_rep_ldst_inv: Found an inconsistent inst in pot_rep") + +let init_symb_mem () = + Hashtbl.clear symb_mem; + Hashtbl.add symb_mem (Ldr P32) (ref []); + Hashtbl.add symb_mem (Ldr P64) (ref []); + Hashtbl.add symb_mem (Ldr P32f) (ref []); + Hashtbl.add symb_mem (Ldr P64f) (ref []); + Hashtbl.add symb_mem (Str P32) (ref []); + Hashtbl.add symb_mem (Str P64) (ref []); + Hashtbl.add symb_mem (Str P32f) (ref []); + Hashtbl.add symb_mem (Str P64f) (ref []) + +let reset_str_symb_mem () = + Hashtbl.replace symb_mem (Str P32) (ref []); + Hashtbl.replace symb_mem (Str P64) (ref []); + Hashtbl.replace symb_mem (Str P32f) (ref []); + Hashtbl.replace symb_mem (Str P64f) (ref []) (* Main peephole function in backward style *) let pair_rep_inv insta = (* Each list below is a symbolic mem representation * for one type of inst. Lists contains integers which * are the indices of insts in the main array "insta". *) - let pot_ldrw_rep = ref [] in - let pot_ldrx_rep = ref [] in - let pot_ldrs_rep = ref [] in - let pot_ldrd_rep = ref [] in - let pot_strw_rep = ref [] in - let pot_strx_rep = ref [] in - let pot_strs_rep = ref [] in - let pot_strd_rep = ref [] in + init_symb_mem (); for i = Array.length insta - 1 downto 1 do let h0 = insta.(i) in let h1 = insta.(i - 1) in (* Here we need to update every symbolic memory according to the matched inst *) - update_pot_rep_basic h0 insta pot_ldrw_rep (Ldr P32) true; - update_pot_rep_basic h0 insta pot_ldrx_rep (Ldr P64) true; - update_pot_rep_basic h0 insta pot_ldrs_rep (Ldr P32f) true; - update_pot_rep_basic h0 insta pot_ldrd_rep (Ldr P64f) true; - update_pot_rep_basic h0 insta pot_strw_rep (Str P32) true; - update_pot_rep_basic h0 insta pot_strx_rep (Str P64) true; - update_pot_rep_basic h0 insta pot_strs_rep (Str P32f) true; - update_pot_rep_basic h0 insta pot_strd_rep (Str P64f) true; + update_pot_rep_basic h0 insta (Ldr P32) true; + update_pot_rep_basic h0 insta (Ldr P64) true; + update_pot_rep_basic h0 insta (Ldr P32f) true; + update_pot_rep_basic h0 insta (Ldr P64f) true; + update_pot_rep_basic h0 insta (Str P32) true; + update_pot_rep_basic h0 insta (Str P64) true; + update_pot_rep_basic h0 insta (Str P32f) true; + update_pot_rep_basic h0 insta (Str P64f) true; match (h0, h1) with (* Non-consecutive ldr *) - | PLoad (PLd_rd_a (ldi, rd1, ADimm (b1, n1))), _ -> ( - if is_compat_load ldi then - let pot_rep = - match ldi with - | Pldrw | Pldrw_a -> pot_ldrw_rep - | Pldrx | Pldrx_a -> pot_ldrx_rep - | Pldrs -> pot_ldrs_rep - | _ -> pot_ldrd_rep - in + | PLoad (PLd_rd_a (ldi, rd1, ADimm (b1, n1))), _ -> + if is_compat_load ldi then ( (* Search a previous compatible load *) let ld_t = get_load_pht ldi in - match - search_compat_rep_inv rd1 b1 n1 insta !pot_rep ld_t - with + let pot_rep = Hashtbl.find symb_mem ld_t in + (match search_compat_rep_inv rd1 b1 n1 insta !pot_rep ld_t with (* If we can't find a candidate, add the current load as a potential future one *) | None -> pot_rep := i :: !pot_rep (* Else, perform the peephole *) @@ -428,61 +430,48 @@ let pair_rep_inv insta = pot_rep := List.filter filt !pot_rep; insta.(rep) <- Pnop; if min_is_rev n n1 then ( - if debug then eprintf "LDP_BACK_SPACED_PEEP_IMM_INC_%a\n" print_ph_ty ld_t; + if debug then + eprintf "LDP_BACK_SPACED_PEEP_IMM_INC_%a\n" print_ph_ty ld_t; insta.(i) <- PLoad (Pldp (trans_ldi ldi, r, rd1, c, chunk_load ldi, ADimm (b, n)))) else ( - if debug then eprintf "LDP_BACK_SPACED_PEEP_IMM_DEC_%a\n" print_ph_ty ld_t; + if debug then + eprintf "LDP_BACK_SPACED_PEEP_IMM_DEC_%a\n" print_ph_ty ld_t; insta.(i) <- PLoad (Pldp - (trans_ldi ldi, rd1, r, chunk_load ldi, c, ADimm (b, n1)))) - ) + (trans_ldi ldi, rd1, r, chunk_load ldi, c, ADimm (b, n1))))); + Hashtbl.replace symb_mem ld_t pot_rep) (* Non-consecutive str *) - | PStore (PSt_rs_a (sti, rd1, ADimm (b1, n1))), _ -> ( - if is_compat_store sti then - let pot_rep = - match sti with - | Pstrw | Pstrw_a -> pot_strw_rep - | Pstrx | Pstrx_a -> pot_strx_rep - | Pstrs -> pot_strs_rep - | _ -> pot_strd_rep - in + | PStore (PSt_rs_a (sti, rd1, ADimm (b1, n1))), _ -> + if is_compat_store sti then ( (* Search a previous compatible store *) let st_t = get_store_pht sti in - match - search_compat_rep_inv rd1 b1 n1 insta !pot_rep st_t - with + let pot_rep = Hashtbl.find symb_mem st_t in + (match search_compat_rep_inv rd1 b1 n1 insta !pot_rep st_t with (* If we can't find a candidate, clean and add the current store as a potential future one *) | None -> - pot_strw_rep := []; - pot_strx_rep := []; - pot_strs_rep := []; - pot_strd_rep := []; - pot_rep := i :: !pot_rep + reset_str_symb_mem (); + pot_rep := [ i ] (* Else, perform the peephole *) | Some (rep, c, r, b, n) -> (* The two lines below are used to filter the elected candidate *) let filt x = x != rep in pot_rep := List.filter filt !pot_rep; insta.(rep) <- Pnop; - if debug then eprintf "STP_BACK_SPACED_PEEP_IMM_INC_%a\n" print_ph_ty st_t; + if debug then + eprintf "STP_BACK_SPACED_PEEP_IMM_INC_%a\n" print_ph_ty st_t; insta.(i) <- PStore (Pstp - (trans_sti sti, rd1, r, chunk_store sti, c, ADimm (b, n1))) + (trans_sti sti, rd1, r, chunk_store sti, c, ADimm (b, n1)))); + Hashtbl.replace symb_mem st_t pot_rep (* Any other inst *)) | i, _ -> ( (* Clear list of candidates if there is a non supported store *) - match i with - | PStore _ -> - pot_strw_rep := []; - pot_strx_rep := []; - pot_strs_rep := []; - pot_strd_rep := [] - | _ -> ()) + match i with PStore _ -> reset_str_symb_mem () | _ -> ()) done (* Main peephole function in forward style *) @@ -490,26 +479,19 @@ let pair_rep insta = (* Each list below is a symbolic mem representation * for one type of inst. Lists contains integers which * are the indices of insts in the main array "insta". *) - let pot_ldrw_rep = ref [] in - let pot_ldrx_rep = ref [] in - let pot_ldrs_rep = ref [] in - let pot_ldrd_rep = ref [] in - let pot_strw_rep = ref [] in - let pot_strx_rep = ref [] in - let pot_strs_rep = ref [] in - let pot_strd_rep = ref [] in + init_symb_mem (); for i = 0 to Array.length insta - 2 do let h0 = insta.(i) in let h1 = insta.(i + 1) in (* Here we need to update every symbolic memory according to the matched inst *) - update_pot_rep_basic h0 insta pot_ldrw_rep (Ldr P32) true; - update_pot_rep_basic h0 insta pot_ldrx_rep (Ldr P64) true; - update_pot_rep_basic h0 insta pot_ldrs_rep (Ldr P32f) true; - update_pot_rep_basic h0 insta pot_ldrd_rep (Ldr P64f) true; - update_pot_rep_basic h0 insta pot_strw_rep (Str P32) true; - update_pot_rep_basic h0 insta pot_strx_rep (Str P64) true; - update_pot_rep_basic h0 insta pot_strs_rep (Str P32f) true; - update_pot_rep_basic h0 insta pot_strd_rep (Str P64f) true; + update_pot_rep_basic h0 insta (Ldr P32) false; + update_pot_rep_basic h0 insta (Ldr P64) false; + update_pot_rep_basic h0 insta (Ldr P32f) false; + update_pot_rep_basic h0 insta (Ldr P64f) false; + update_pot_rep_basic h0 insta (Str P32) false; + update_pot_rep_basic h0 insta (Str P64) false; + update_pot_rep_basic h0 insta (Str P32f) false; + update_pot_rep_basic h0 insta (Str P64f) false; match (h0, h1) with (* Consecutive ldr *) | ( PLoad (PLd_rd_a (ldi1, rd1, ADimm (b1, n1))), @@ -518,7 +500,8 @@ let pair_rep insta = let ld_t = get_load_pht ldi1 in if is_valid_ldr rd1 rd2 b1 b2 n1 n2 ld_t then ( if min_is_rev n1 n2 then ( - if debug then eprintf "LDP_CONSEC_PEEP_IMM_INC_%a\n" print_ph_ty ld_t; + if debug then + eprintf "LDP_CONSEC_PEEP_IMM_INC_%a\n" print_ph_ty ld_t; insta.(i) <- PLoad (Pldp @@ -529,7 +512,8 @@ let pair_rep insta = chunk_load ldi2, ADimm (b1, n1) ))) else ( - if debug then eprintf "LDP_CONSEC_PEEP_IMM_DEC_%a\n" print_ph_ty ld_t; + if debug then + eprintf "LDP_CONSEC_PEEP_IMM_DEC_%a\n" print_ph_ty ld_t; insta.(i) <- PLoad (Pldp @@ -541,20 +525,12 @@ let pair_rep insta = ADimm (b1, n2) ))); insta.(i + 1) <- Pnop) (* Non-consecutive ldr *) - | PLoad (PLd_rd_a (ldi, rd1, ADimm (b1, n1))), _ -> ( - if is_compat_load ldi then - let pot_rep = - match ldi with - | Pldrw | Pldrw_a -> pot_ldrw_rep - | Pldrx | Pldrx_a -> pot_ldrx_rep - | Pldrs -> pot_ldrs_rep - | _ -> pot_ldrd_rep - in + | PLoad (PLd_rd_a (ldi, rd1, ADimm (b1, n1))), _ -> + if is_compat_load ldi then ( (* Search a previous compatible load *) let ld_t = get_load_pht ldi in - match - search_compat_rep rd1 b1 n1 insta !pot_rep ld_t - with + let pot_rep = Hashtbl.find symb_mem ld_t in + (match search_compat_rep rd1 b1 n1 insta !pot_rep ld_t with (* If we can't find a candidate, add the current load as a potential future one *) | None -> pot_rep := i :: !pot_rep (* Else, perform the peephole *) @@ -564,32 +540,32 @@ let pair_rep insta = pot_rep := List.filter filt !pot_rep; insta.(rep) <- Pnop; if min_is_rev n n1 then ( - if debug then eprintf "LDP_FORW_SPACED_PEEP_IMM_INC_%a\n" print_ph_ty ld_t; + if debug then + eprintf "LDP_FORW_SPACED_PEEP_IMM_INC_%a\n" print_ph_ty ld_t; insta.(i) <- PLoad (Pldp (trans_ldi ldi, r, rd1, c, chunk_load ldi, ADimm (b, n)))) else ( - if debug then eprintf "LDP_FORW_SPACED_PEEP_IMM_DEC_%a\n" print_ph_ty ld_t; + if debug then + eprintf "LDP_FORW_SPACED_PEEP_IMM_DEC_%a\n" print_ph_ty ld_t; insta.(i) <- PLoad (Pldp - (trans_ldi ldi, rd1, r, chunk_load ldi, c, ADimm (b, n1)))) - ) + (trans_ldi ldi, rd1, r, chunk_load ldi, c, ADimm (b, n1))))); + Hashtbl.replace symb_mem ld_t pot_rep) (* Consecutive str *) | ( PStore (PSt_rs_a (sti1, rd1, ADimm (b1, n1))), PStore (PSt_rs_a (sti2, rd2, ADimm (b2, n2))) ) -> (* Regardless of whether we can perform the peephole or not, * we have to clean the potential candidates for stp now as we are * looking at two new store instructions. *) - pot_strw_rep := []; - pot_strx_rep := []; - pot_strs_rep := []; - pot_strd_rep := []; + reset_str_symb_mem (); if are_compat_store sti1 sti2 then let st_t = get_store_pht sti1 in if is_valid_str b1 b2 n1 n2 st_t then ( - if debug then eprintf "STP_CONSEC_PEEP_IMM_INC_%a\n" print_ph_ty st_t; + if debug then + eprintf "STP_CONSEC_PEEP_IMM_INC_%a\n" print_ph_ty st_t; insta.(i) <- PStore (Pstp @@ -601,48 +577,32 @@ let pair_rep insta = ADimm (b1, n1) )); insta.(i + 1) <- Pnop) (* Non-consecutive str *) - | PStore (PSt_rs_a (sti, rd1, ADimm (b1, n1))), _ -> ( - if is_compat_store sti then - let pot_rep = - match sti with - | Pstrw | Pstrw_a -> pot_strw_rep - | Pstrx | Pstrx_a -> pot_strx_rep - | Pstrs -> pot_strs_rep - | _ -> pot_strd_rep - in + | PStore (PSt_rs_a (sti, rd1, ADimm (b1, n1))), _ -> + if is_compat_store sti then ( (* Search a previous compatible store *) let st_t = get_store_pht sti in - match - search_compat_rep rd1 b1 n1 insta !pot_rep st_t - with + let pot_rep = Hashtbl.find symb_mem st_t in + (match search_compat_rep rd1 b1 n1 insta !pot_rep st_t with (* If we can't find a candidate, clean and add the current store as a potential future one *) | None -> - pot_strw_rep := []; - pot_strx_rep := []; - pot_strs_rep := []; - pot_strd_rep := []; - pot_rep := i :: !pot_rep + reset_str_symb_mem (); + pot_rep := [ i ] (* Else, perform the peephole *) | Some (rep, c, r, b, n) -> (* The two lines below are used to filter the elected candidate *) let filt x = x != rep in pot_rep := List.filter filt !pot_rep; insta.(rep) <- Pnop; - if debug then eprintf "STP_FORW_SPACED_PEEP_IMM_INC_%a\n" print_ph_ty st_t; + if debug then + eprintf "STP_FORW_SPACED_PEEP_IMM_INC_%a\n" print_ph_ty st_t; insta.(i) <- PStore - (Pstp (trans_sti sti, r, rd1, c, chunk_store sti, ADimm (b, n))) - ) + (Pstp (trans_sti sti, r, rd1, c, chunk_store sti, ADimm (b, n)))); + Hashtbl.replace symb_mem st_t pot_rep) (* Any other inst *) | i, _ -> ( (* Clear list of candidates if there is a non supported store *) - match i with - | PStore _ -> - pot_strw_rep := []; - pot_strx_rep := []; - pot_strs_rep := []; - pot_strd_rep := [] - | _ -> ()) + match i with PStore _ -> reset_str_symb_mem () | _ -> ()) done (* Calling peephole if flag is set *) -- cgit