Project

General

Profile

Statistics
| Branch: | Tag: | Revision:

lustrec / src / liveness.ml @ a38c681e

History | View | Annotate | Download (9.84 KB)

1
(* ----------------------------------------------------------------------------
2
 * SchedMCore - A MultiCore Scheduling Framework
3
 * Copyright (C) 2009-2013, ONERA, Toulouse, FRANCE - LIFL, Lille, FRANCE
4
 * Copyright (C) 2012-2013, INPT, Toulouse, FRANCE
5
 *
6
 * This file is part of Prelude
7
 *
8
 * Prelude is free software; you can redistribute it and/or
9
 * modify it under the terms of the GNU Lesser General Public License
10
 * as published by the Free Software Foundation ; either version 2 of
11
 * the License, or (at your option) any later version.
12
 *
13
 * Prelude is distributed in the hope that it will be useful, but
14
 * WITHOUT ANY WARRANTY ; without even the implied warranty of
15
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16
 * Lesser General Public License for more details.
17
 *
18
 * You should have received a copy of the GNU Lesser General Public
19
 * License along with this program ; if not, write to the Free Software
20
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
21
 * USA
22
 *---------------------------------------------------------------------------- *)
23

    
24
open Utils
25
open LustreSpec
26
open Corelang
27
open Graph
28
open Causality
29

    
30
(* Computes the last dependency
31
*)
32

    
33
(* Computes the death table of [node] wrt dep graph [g] and topological [sort].
34
   The death table is a mapping: ident -> Set(ident) such that:
35
   death x is the set of local variables which get dead (i.e. unused) 
36
   after x is evaluated, but were until live.
37
let death_table node g sort =
38
  let death = Hashtbl.create 23 in
39
  let sort  = ref (List.rev sort) in
40
  let buried  = ref ISet.empty in
41
  begin
42
    buried := ExprDep.node_memory_variables node;
43
    buried := List.fold_left (fun dead (v : var_decl) -> ISet.add v.var_id dead) !buried node.node_outputs;
44
    (* We could also try to reuse input variables, due to C parameter copying semantics *)
45
    buried := List.fold_left (fun dead (v : var_decl) -> ISet.add v.var_id dead) !buried node.node_inputs;
46
    while (!sort <> [])
47
    do
48
      let head = List.hd !sort in
49
      let dead = IdentDepGraph.fold_succ
50
	(fun tgt dead -> if not (ExprDep.is_instance_var tgt || ISet.mem tgt !buried) then ISet.add tgt dead else dead)
51
	g head ISet.empty in
52
      buried := ISet.union !buried dead;
53
      Hashtbl.add death head dead;
54
      sort := List.tl !sort
55
    done;
56
    IdentDepGraph.clear g;
57
    death
58
  end
59
*)
60

    
61
(* computes the in-degree for each local variable of node [n], according to dep graph [g].
62
*)
63
let compute_fanin n g =
64
  let locals = ISet.diff (ExprDep.node_local_variables n) (ExprDep.node_memory_variables n) in
65
  let fanin = Hashtbl.create 23 in
66
  begin
67
    IdentDepGraph.iter_vertex (fun v -> if ISet.mem v locals then Hashtbl.add fanin v (IdentDepGraph.in_degree g v)) g;
68
    fanin
69
  end
70
 
71
let pp_fanin fmt fanin =
72
  begin
73
    Format.fprintf fmt "{ /* locals fanin: */@.";
74
    Hashtbl.iter (fun s t -> Format.fprintf fmt "%s -> %d@." s t) fanin;
75
    Format.fprintf fmt "}@."
76
  end
77

    
78
(* computes the cone of influence of a given [var] wrt a dependency graph [g].
79
*)
80
let cone_of_influence g var =
81
 (*Format.printf "coi: %s@." var;*)
82
 let frontier = ref (ISet.add var ISet.empty) in
83
 let coi = ref ISet.empty in
84
 while not (ISet.is_empty !frontier)
85
 do
86
   let head = ISet.min_elt !frontier in
87
   (*Format.printf "head: %s@." head;*)
88
   frontier := ISet.remove head !frontier;
89
   if ExprDep.is_read_var head then coi := ISet.add (ExprDep.undo_read_var head) !coi;
90
   List.iter (fun s -> frontier := ISet.add s !frontier) (IdentDepGraph.succ g head);
91
 done;
92
 !coi
93

    
94
let compute_unused_variables n g =
95
  let inputs = ExprDep.node_input_variables n in
96
  let mems = ExprDep.node_memory_variables n in
97
  let outputs = ExprDep.node_output_variables n in
98
  ISet.fold
99
    (fun var unused -> ISet.diff unused (cone_of_influence g var))
100
    (ISet.union outputs mems)
101
    (ISet.union inputs mems)
102

    
103
(* computes the set of potentially reusable variables.
104
   We don't reuse input variables, due to possible aliasing *)
105
let node_reusable_variables node =
106
  let mems = ExprDep.node_memory_variables node in
107
  List.fold_left
108
    (fun acc l ->
109
      if ISet.mem l.var_id mems then acc else Disjunction.CISet.add l acc)
110
    Disjunction.CISet.empty
111
    node.node_locals
112

    
113
(* Recursively removes useless variables,
114
   i.e. variables that are current roots of the dep graph [g]
115
   and returns [locals] and [evaluated] such roots *)
116
let remove_local_roots locals evaluated g =
117
  let rem = ref true in
118
  let roots = ref Disjunction.CISet.empty in
119
  while !rem
120
  do
121
    rem := false;
122
    let new_roots = graph_roots g in
123
    let reusable_roots = Disjunction.CISet.filter (fun v -> (List.mem v.var_id new_roots) && (Disjunction.CISet.mem v locals)) evaluated in
124
    if not (Disjunction.CISet.is_empty reusable_roots) then
125
      begin
126
	rem := true;
127
	Disjunction.CISet.iter (fun v -> IdentDepGraph.remove_vertex g v.var_id) reusable_roots;
128
	roots := Disjunction.CISet.union reusable_roots !roots
129
      end
130
  done;
131
  !roots
132

    
133
(* checks whether a variable is aliasable,
134
   depending on its (address) type *)
135
let is_aliasable var =
136
 Types.is_address_type var.var_type
137
 
138
(* checks whether a variable [v] is an input of the [var] equation, with an address type.
139
   if so, [var] could not safely reuse/alias [v], should [v] be dead in the caller node,
140
   because [v] may not be dead in the callee node when [var] is assigned *)
141
let is_aliasable_input node var =
142
  let eq_var = get_node_eq var node in
143
  let inputs_var =
144
    match NodeDep.get_callee eq_var.eq_rhs with
145
    | None           -> []
146
    | Some (_, args) -> List.fold_right (fun e r -> match e.expr_desc with Expr_ident id -> id::r | _ -> r) args [] in
147
  fun v -> Types.is_address_type v.var_type && List.mem v.var_id inputs_var
148

    
149
(* merges two variables [v] and [v'] of graph [g].
150
   [v] is replaced by [v']
151
*)
152
let merge_in_dep_graph v v' g =
153
  begin
154
    IdentDepGraph.add_vertex g v';
155
    IdentDepGraph.iter_succ (fun s -> IdentDepGraph.add_edge g v' s) g v;
156
    IdentDepGraph.iter_pred (fun p -> IdentDepGraph.add_edge g p v') g v;
157
    IdentDepGraph.remove_vertex g v
158
  end
159

    
160
(* computes the reusable dependencies of variable [var] in graph [g],
161
   once [var] has been evaluated
162
   [dead] is the set of evaluated and dead variables
163
   [eval] is the set of evaluated variables
164
*)
165
let compute_reusable_dependencies locals evaluated reusable var g =
166
  begin
167
    Log.report ~level:2 (fun fmt -> Format.fprintf fmt "compute_reusable_dependencies %a %a %a %a %a@." Disjunction.pp_ciset locals Disjunction.pp_ciset !evaluated Disjunction.pp_ciset !reusable Printers.pp_var_name var pp_dep_graph g);
168
    evaluated := Disjunction.CISet.add var !evaluated;
169
    IdentDepGraph.iter_succ (IdentDepGraph.remove_edge g var.var_id) g var.var_id;
170
    reusable := Disjunction.CISet.union (remove_local_roots locals !evaluated g) !reusable;
171
  end
172

    
173
let compute_reuse_policy node schedule disjoint g =
174
  let locals = node_reusable_variables node in
175
  let sort = ref schedule in
176
  let evaluated = ref Disjunction.CISet.empty in
177
  let reusable = ref Disjunction.CISet.empty in
178
  let policy = Hashtbl.create 23 in
179
  while !sort <> []
180
  do
181
    let head = get_node_var (List.hd !sort) node in
182
    compute_reusable_dependencies locals evaluated reusable head g;
183
    let aliasable = is_aliasable_input node head.var_id in
184
    let eligible v = Typing.eq_ground head.var_type v.var_type && not (aliasable v) in
185
    let reuse =
186
      try
187
	let disj = Hashtbl.find disjoint head.var_id in
188
	Disjunction.CISet.max_elt (Disjunction.CISet.filter (fun v -> (eligible v) && (Disjunction.CISet.mem v !evaluated) && not (Disjunction.CISet.mem v !reusable)) disj)
189
      with Not_found ->
190
      try
191
	Disjunction.CISet.choose (Disjunction.CISet.filter (fun v -> eligible v) !reusable)
192
      with Not_found -> head in
193
    reusable := Disjunction.CISet.remove reuse !reusable;
194
    Disjunction.replace_in_disjoint_map disjoint head reuse;
195
    merge_in_dep_graph head.var_id reuse.var_id g;
196
    Hashtbl.add policy head.var_id reuse;
197
    Log.report ~level:2 (fun fmt -> Format.fprintf fmt "reuse %s instead of %s@." reuse.var_id head.var_id);
198
    Log.report ~level:1 (fun fmt -> Format.fprintf fmt "new disjoint:%a@." Disjunction.pp_disjoint_map disjoint);
199
    Log.report ~level:2 
200
      (fun fmt -> Format.fprintf fmt "new dependency graph:%a@." pp_dep_graph g);
201
    sort := List.tl !sort;
202
  done;
203
  IdentDepGraph.clear g;
204
  policy
205

    
206
(* Reuse policy:
207
   - could reuse variables with the same type exactly only (simple).
208
   - reusing variables with different types would involve:
209
     - either dirty castings
210
     - or complex inclusion expression (for instance: array <-> array cell, struct <-> struct field) to be able to reuse only some parts of structured data.
211
     ... it seems too complex and potentially unsafe
212
   - for node instance calls: output variables could NOT reuse aliasable input variables, 
213
     even if inputs become dead, because the correctness would depend on the scheduling
214
     of the callee (so, the compiling strategy could NOT be modular anymore).
215
   - once a policy is set, we need to:
216
     - replace each variable by its reuse alias.
217
     - simplify resulting equations, as we may now have:
218
        x = x;                     --> ;           for scalar vars
219
       or:
220
        x = &{ f1 = x->f1; f2 = t; } --> x->f2 = t;   for struct vars
221
     - such simplifications are, until now, only expressible at the C source level...
222
 *)
223

    
224

    
225
(* the reuse policy seeks to use less local variables
226
   by replacing local variables, applying the rules
227
   in the following order:
228
    1) use another clock disjoint still live variable,
229
       with the greatest possible disjoint clock
230
    2) reuse a dead variable
231
   For the sake of safety, we replace variables by others:
232
    - with the same type
233
    - not aliasable (i.e. address type)
234
*)
235

    
236
let pp_reuse_policy fmt policy =
237
  begin
238
    Format.fprintf fmt "{ /* reuse policy */@.";
239
    Hashtbl.iter (fun s t -> Format.fprintf fmt "%s -> %s@." s t.var_id) policy;
240
    Format.fprintf fmt "}@."
241
  end
242
(* Local Variables: *)
243
(* compile-command:"make -C .." *)
244
(* End: *)