From ab520acd80f7d39aa14fdda6932accbb2a787ebf Mon Sep 17 00:00:00 2001 From: Léo Gourdin Date: Wed, 19 May 2021 12:47:22 +0200 Subject: Grouping common RTL functions, printer improvement --- backend/Duplicateaux.ml | 2 +- backend/LICMaux.ml | 5 +---- 2 files changed, 2 insertions(+), 5 deletions(-) (limited to 'backend') diff --git a/backend/Duplicateaux.ml b/backend/Duplicateaux.ml index d55da64a..e8e60a4f 100644 --- a/backend/Duplicateaux.ml +++ b/backend/Duplicateaux.ml @@ -23,6 +23,7 @@ open RTL open Maps open Camlcoq open DebugPrint +open AuxTools let stats_oc = ref None @@ -95,7 +96,6 @@ let write_stats_oc () = end let get_loop_headers = LICMaux.get_loop_headers -let get_some = LICMaux.get_some let rtl_successors = LICMaux.rtl_successors (* Get list of nodes following a BFS of the code *) diff --git a/backend/LICMaux.ml b/backend/LICMaux.ml index b88dbc2d..df609505 100644 --- a/backend/LICMaux.ml +++ b/backend/LICMaux.ml @@ -17,16 +17,13 @@ open Kildall;; open HashedSet;; open Inject;; open DebugPrint;; +open AuxTools;; type reg = P.t;; (** get_loop_headers moved from Duplicateaux.ml to LICMaux.ml to prevent cycle dependencies *) type vstate = Unvisited | Processed | Visited -let get_some = function -| None -> failwith "Did not get some" -| Some thing -> thing - let rtl_successors = function | Itailcall _ | Ireturn _ -> [] | Icall(_,_,_,_,n) | Ibuiltin(_,_,_,n) | Inop n | Iop (_,_,_,n) -- cgit From 2408dd1aecf8d8c3bfd3b24a65f7f57cf602cb10 Mon Sep 17 00:00:00 2001 From: Léo Gourdin Date: Thu, 20 May 2021 11:58:40 +0200 Subject: Changing to an opaq record in BTL info, this is a broken commit --- backend/AuxTools.ml | 52 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 52 insertions(+) create mode 100644 backend/AuxTools.ml (limited to 'backend') diff --git a/backend/AuxTools.ml b/backend/AuxTools.ml new file mode 100644 index 00000000..1e334524 --- /dev/null +++ b/backend/AuxTools.ml @@ -0,0 +1,52 @@ +open RTL +open Maps +open Camlcoq + +let p2i r = P.to_int r + +let get_some = function + | None -> failwith "Got None instead of Some _" + | Some thing -> thing + +let successors_inst = function + | Inop n + | Iop (_, _, _, n) + | Iload (_, _, _, _, _, n) + | Istore (_, _, _, _, n) + | Icall (_, _, _, _, n) + | Ibuiltin (_, _, _, n) -> + [ n ] + | Icond (_, _, n1, n2, _) -> [ n1; n2 ] + | Ijumptable (_, l) -> l + | Itailcall _ | Ireturn _ -> [] + +let predicted_successor = function + | Inop n | Iop (_, _, _, n) | Iload (_, _, _, _, _, n) | Istore (_, _, _, _, n) + -> + Some n + | Icall (_, _, _, _, n) | Ibuiltin (_, _, _, n) -> None + | Icond (_, _, n1, n2, p) -> ( + match p with Some true -> Some n1 | Some false -> Some n2 | None -> None) + | Ijumptable _ | Itailcall _ | Ireturn _ -> None + +let non_predicted_successors i = function + | None -> successors_inst i + | Some ps -> List.filter (fun s -> s != ps) (successors_inst i) + +(* adapted from Linearizeaux.get_join_points *) +let get_join_points code entry = + let reached = ref (PTree.map (fun n i -> false) code) in + let reached_twice = ref (PTree.map (fun n i -> false) code) in + let rec traverse pc = + if get_some @@ PTree.get pc !reached then begin + if not (get_some @@ PTree.get pc !reached_twice) then + reached_twice := PTree.set pc true !reached_twice + end else begin + reached := PTree.set pc true !reached; + traverse_succs (successors_inst @@ get_some @@ PTree.get pc code) + end + and traverse_succs = function + | [] -> () + | [pc] -> traverse pc + | pc :: l -> traverse pc; traverse_succs l + in traverse entry; !reached_twice -- cgit From 0efe7783c50d72858352fda93d30e0f52792d658 Mon Sep 17 00:00:00 2001 From: Léo Gourdin Date: Mon, 24 May 2021 10:07:52 +0200 Subject: Moving common tools, adding liveness input/output information to BTL generation oracle --- backend/AuxTools.ml | 52 ----------------------------- backend/Duplicateaux.ml | 2 +- backend/LICMaux.ml | 2 +- backend/RTLcommonaux.ml | 89 +++++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 91 insertions(+), 54 deletions(-) delete mode 100644 backend/AuxTools.ml create mode 100644 backend/RTLcommonaux.ml (limited to 'backend') diff --git a/backend/AuxTools.ml b/backend/AuxTools.ml deleted file mode 100644 index 1e334524..00000000 --- a/backend/AuxTools.ml +++ /dev/null @@ -1,52 +0,0 @@ -open RTL -open Maps -open Camlcoq - -let p2i r = P.to_int r - -let get_some = function - | None -> failwith "Got None instead of Some _" - | Some thing -> thing - -let successors_inst = function - | Inop n - | Iop (_, _, _, n) - | Iload (_, _, _, _, _, n) - | Istore (_, _, _, _, n) - | Icall (_, _, _, _, n) - | Ibuiltin (_, _, _, n) -> - [ n ] - | Icond (_, _, n1, n2, _) -> [ n1; n2 ] - | Ijumptable (_, l) -> l - | Itailcall _ | Ireturn _ -> [] - -let predicted_successor = function - | Inop n | Iop (_, _, _, n) | Iload (_, _, _, _, _, n) | Istore (_, _, _, _, n) - -> - Some n - | Icall (_, _, _, _, n) | Ibuiltin (_, _, _, n) -> None - | Icond (_, _, n1, n2, p) -> ( - match p with Some true -> Some n1 | Some false -> Some n2 | None -> None) - | Ijumptable _ | Itailcall _ | Ireturn _ -> None - -let non_predicted_successors i = function - | None -> successors_inst i - | Some ps -> List.filter (fun s -> s != ps) (successors_inst i) - -(* adapted from Linearizeaux.get_join_points *) -let get_join_points code entry = - let reached = ref (PTree.map (fun n i -> false) code) in - let reached_twice = ref (PTree.map (fun n i -> false) code) in - let rec traverse pc = - if get_some @@ PTree.get pc !reached then begin - if not (get_some @@ PTree.get pc !reached_twice) then - reached_twice := PTree.set pc true !reached_twice - end else begin - reached := PTree.set pc true !reached; - traverse_succs (successors_inst @@ get_some @@ PTree.get pc code) - end - and traverse_succs = function - | [] -> () - | [pc] -> traverse pc - | pc :: l -> traverse pc; traverse_succs l - in traverse entry; !reached_twice diff --git a/backend/Duplicateaux.ml b/backend/Duplicateaux.ml index e8e60a4f..8ca6c6ab 100644 --- a/backend/Duplicateaux.ml +++ b/backend/Duplicateaux.ml @@ -23,7 +23,7 @@ open RTL open Maps open Camlcoq open DebugPrint -open AuxTools +open RTLcommonaux let stats_oc = ref None diff --git a/backend/LICMaux.ml b/backend/LICMaux.ml index df609505..82e4629f 100644 --- a/backend/LICMaux.ml +++ b/backend/LICMaux.ml @@ -17,7 +17,7 @@ open Kildall;; open HashedSet;; open Inject;; open DebugPrint;; -open AuxTools;; +open RTLcommonaux;; type reg = P.t;; diff --git a/backend/RTLcommonaux.ml b/backend/RTLcommonaux.ml new file mode 100644 index 00000000..2334dfee --- /dev/null +++ b/backend/RTLcommonaux.ml @@ -0,0 +1,89 @@ +open RTL +open Maps +open Camlcoq +open Registers +open Kildall +open Lattice + +let p2i r = P.to_int r + +let get_some = function + | None -> failwith "Got None instead of Some _" + | Some thing -> thing + +let successors_inst = function + | Inop n + | Iop (_, _, _, n) + | Iload (_, _, _, _, _, n) + | Istore (_, _, _, _, n) + | Icall (_, _, _, _, n) + | Ibuiltin (_, _, _, n) -> + [ n ] + | Icond (_, _, n1, n2, _) -> [ n1; n2 ] + | Ijumptable (_, l) -> l + | Itailcall _ | Ireturn _ -> [] + +let predicted_successor = function + | Inop n | Iop (_, _, _, n) | Iload (_, _, _, _, _, n) | Istore (_, _, _, _, n) + -> + Some n + | Icall (_, _, _, _, n) | Ibuiltin (_, _, _, n) -> None + | Icond (_, _, n1, n2, p) -> ( + match p with Some true -> Some n1 | Some false -> Some n2 | None -> None) + | Ijumptable _ | Itailcall _ | Ireturn _ -> None + +let non_predicted_successors i = function + | None -> successors_inst i + | Some ps -> List.filter (fun s -> s != ps) (successors_inst i) + +(* adapted from Linearizeaux.get_join_points *) +let get_join_points code entry = + let reached = ref (PTree.map (fun n i -> false) code) in + let reached_twice = ref (PTree.map (fun n i -> false) code) in + let rec traverse pc = + if get_some @@ PTree.get pc !reached then begin + if not (get_some @@ PTree.get pc !reached_twice) then + reached_twice := PTree.set pc true !reached_twice + end else begin + reached := PTree.set pc true !reached; + traverse_succs (successors_inst @@ get_some @@ PTree.get pc code) + end + and traverse_succs = function + | [] -> () + | [pc] -> traverse pc + | pc :: l -> traverse pc; traverse_succs l + in traverse entry; !reached_twice + +let transfer f pc after = let open Liveness in + match PTree.get pc f.fn_code with + | Some i -> + (match i with + | Inop _ -> after + | Iop (_, args, res, _) -> + reg_list_live args (Regset.remove res after) + | Iload (_, _, _, args, dst, _) -> + reg_list_live args (Regset.remove dst after) + | Istore (_, _, args, src, _) -> + reg_list_live args (Regset.add src after) + | Icall (_, ros, args, res, _) -> + reg_list_live args (reg_sum_live ros (Regset.remove res after)) + | Itailcall (_, ros, args) -> + reg_list_live args (reg_sum_live ros Regset.empty) + | Ibuiltin (_, args, res, _) -> + reg_list_live (AST.params_of_builtin_args args) + (reg_list_dead (AST.params_of_builtin_res res) after) + | Icond (_, args, _, _, _) -> + reg_list_live args after + | Ijumptable (arg, _) -> + Regset.add arg after + | Ireturn optarg -> + reg_option_live optarg Regset.empty) + | None -> Regset.empty + +module RegsetLat = LFSet(Regset) + +module DS = Backward_Dataflow_Solver(RegsetLat)(NodeSetBackward) + +let analyze f = + let liveouts = get_some @@ DS.fixpoint f.fn_code successors_instr (transfer f) in + PTree.map (fun n _ -> let lo = PMap.get n liveouts in transfer f n lo) f.fn_code -- cgit From 1a78c940f46273b7146d2111b1e2da309434f021 Mon Sep 17 00:00:00 2001 From: Léo Gourdin Date: Thu, 27 May 2021 16:55:18 +0200 Subject: [disabled checker] BTL Scheduling and Renumbering OK! --- backend/RTLcommonaux.ml | 1 + 1 file changed, 1 insertion(+) (limited to 'backend') diff --git a/backend/RTLcommonaux.ml b/backend/RTLcommonaux.ml index 2334dfee..0e369d04 100644 --- a/backend/RTLcommonaux.ml +++ b/backend/RTLcommonaux.ml @@ -6,6 +6,7 @@ open Kildall open Lattice let p2i r = P.to_int r +let i2p i = P.of_int i let get_some = function | None -> failwith "Got None instead of Some _" -- cgit