lustrec / src / normalization.ml @ fc886259
History  View  Annotate  Download (16.8 KB)
1 
(********************************************************************) 

2 
(* *) 
3 
(* The LustreC compiler toolset / The LustreC Development Team *) 
4 
(* Copyright 2012   ONERA  CNRS  INPT *) 
5 
(* *) 
6 
(* LustreC is free software, distributed WITHOUT ANY WARRANTY *) 
7 
(* under the terms of the GNU Lesser General Public License *) 
8 
(* version 2.1. *) 
9 
(* *) 
10 
(********************************************************************) 
11  
12 
open Utils 
13 
open LustreSpec 
14 
open Corelang 
15 
open Format 
16  
17 
let expr_true loc ck = 
18 
{ expr_tag = Utils.new_tag (); 
19 
expr_desc = Expr_const (Const_tag tag_true); 
20 
expr_type = Type_predef.type_bool; 
21 
expr_clock = ck; 
22 
expr_delay = Delay.new_var (); 
23 
expr_annot = None; 
24 
expr_loc = loc } 
25  
26 
let expr_false loc ck = 
27 
{ expr_tag = Utils.new_tag (); 
28 
expr_desc = Expr_const (Const_tag tag_false); 
29 
expr_type = Type_predef.type_bool; 
30 
expr_clock = ck; 
31 
expr_delay = Delay.new_var (); 
32 
expr_annot = None; 
33 
expr_loc = loc } 
34  
35 
let expr_once loc ck = 
36 
{ expr_tag = Utils.new_tag (); 
37 
expr_desc = Expr_arrow (expr_true loc ck, expr_false loc ck); 
38 
expr_type = Type_predef.type_bool; 
39 
expr_clock = ck; 
40 
expr_delay = Delay.new_var (); 
41 
expr_annot = None; 
42 
expr_loc = loc } 
43  
44 
let is_expr_once = 
45 
let dummy_expr_once = expr_once Location.dummy_loc (Clocks.new_var true) in 
46 
fun expr > Corelang.is_eq_expr expr dummy_expr_once 
47  
48 
let unfold_arrow expr = 
49 
match expr.expr_desc with 
50 
 Expr_arrow (e1, e2) > 
51 
let loc = expr.expr_loc in 
52 
let ck = List.hd (Clocks.clock_list_of_clock expr.expr_clock) in 
53 
{ expr with expr_desc = Expr_ite (expr_once loc ck, e1, e2) } 
54 
 _ > assert false 
55  
56 
let unfold_arrow_active = ref true 
57 
let cpt_fresh = ref 0 
58  
59 
(* Generate a new local [node] variable *) 
60 
let mk_fresh_var node loc ty ck = 
61 
let vars = get_node_vars node in 
62 
let rec aux () = 
63 
incr cpt_fresh; 
64 
let s = Printf.sprintf "__%s_%d" node.node_id !cpt_fresh in 
65 
if List.exists (fun v > v.var_id = s) vars then aux () else 
66 
{ 
67 
var_id = s; 
68 
var_orig = false; 
69 
var_dec_type = dummy_type_dec; 
70 
var_dec_clock = dummy_clock_dec; 
71 
var_dec_const = false; 
72 
var_type = ty; 
73 
var_clock = ck; 
74 
var_loc = loc 
75 
} 
76 
in aux () 
77  
78 
(* Get the equation in [defs] with [expr] as rhs, if any *) 
79 
let get_expr_alias defs expr = 
80 
try Some (List.find (fun eq > is_eq_expr eq.eq_rhs expr) defs) 
81 
with 
82 
Not_found > None 
83  
84 
(* Replace [expr] with (tuple of) [locals] *) 
85 
let replace_expr locals expr = 
86 
match locals with 
87 
 [] > assert false 
88 
 [v] > { expr with 
89 
expr_tag = Utils.new_tag (); 
90 
expr_desc = Expr_ident v.var_id } 
91 
 _ > { expr with 
92 
expr_tag = Utils.new_tag (); 
93 
expr_desc = Expr_tuple (List.map expr_of_vdecl locals) } 
94  
95 
let unfold_offsets e offsets = 
96 
let add_offset e d = 
97 
(*Format.eprintf "add_offset %a(%a) %a @." Printers.pp_expr e Types.print_ty e.expr_type Dimension.pp_dimension d; 
98 
let res = *) 
99 
{ e with 
100 
expr_tag = Utils.new_tag (); 
101 
expr_loc = d.Dimension.dim_loc; 
102 
expr_type = Types.array_element_type e.expr_type; 
103 
expr_desc = Expr_access (e, d) } 
104 
(*in (Format.eprintf "= %a @." Printers.pp_expr res; res) *) 
105 
in 
106 
List.fold_left add_offset e offsets 
107  
108 
(* Create an alias for [expr], if none exists yet *) 
109 
let mk_expr_alias node (defs, vars) expr = 
110 
(*Format.eprintf "mk_expr_alias %a %a %a@." Printers.pp_expr expr Types.print_ty expr.expr_type Clocks.print_ck expr.expr_clock;*) 
111 
match get_expr_alias defs expr with 
112 
 Some eq > 
113 
let aliases = List.map (fun id > List.find (fun v > v.var_id = id) vars) eq.eq_lhs in 
114 
(defs, vars), replace_expr aliases expr 
115 
 None > 
116 
let new_aliases = 
117 
List.map2 
118 
(mk_fresh_var node expr.expr_loc) 
119 
(Types.type_list_of_type expr.expr_type) 
120 
(Clocks.clock_list_of_clock expr.expr_clock) in 
121 
let new_def = 
122 
mkeq expr.expr_loc (List.map (fun v > v.var_id) new_aliases, expr) 
123 
in 
124 
(* Format.eprintf "Checking def of alias: %a > %a@." (fprintf_list ~sep:", " (fun fmt v > Format.pp_print_string fmt v.var_id)) new_aliases Printers.pp_expr expr; *) 
125 
(new_def::defs, new_aliases@vars), replace_expr new_aliases expr 
126  
127 
(* Create an alias for [expr], if [expr] is not already an alias (i.e. an ident) 
128 
and [opt] is true *) 
129 
let mk_expr_alias_opt opt node defvars expr = 
130 
match expr.expr_desc with 
131 
 Expr_ident alias > 
132 
defvars, expr 
133 
 _ > 
134 
if opt 
135 
then 
136 
mk_expr_alias node defvars expr 
137 
else 
138 
defvars, expr 
139  
140 
(* Create a (normalized) expression from [ref_e], 
141 
replacing description with [norm_d], 
142 
taking propagated [offsets] into account 
143 
in order to change expression type *) 
144 
let mk_norm_expr offsets ref_e norm_d = 
145 
(*Format.eprintf "mk_norm_expr %a %a @." Printers.pp_expr ref_e Printers.pp_expr { ref_e with expr_desc = norm_d};*) 
146 
let drop_array_type ty = 
147 
Types.map_tuple_type Types.array_element_type ty in 
148 
{ ref_e with 
149 
expr_desc = norm_d; 
150 
expr_type = Utils.repeat (List.length offsets) drop_array_type ref_e.expr_type } 
151  
152 
(* normalize_<foo> : defs * used vars > <foo> > (updated defs * updated vars) * normalized <foo> *) 
153 
let rec normalize_list alias node offsets norm_element defvars elist = 
154 
List.fold_right 
155 
(fun t (defvars, qlist) > 
156 
let defvars, norm_t = norm_element alias node offsets defvars t in 
157 
(defvars, norm_t :: qlist) 
158 
) elist (defvars, []) 
159  
160 
let rec normalize_expr ?(alias=true) node offsets defvars expr = 
161 
(* Format.eprintf "normalize %B %a [%a]@." alias Printers.pp_expr expr (Utils.fprintf_list ~sep:"," Dimension.pp_dimension) offsets;*) 
162 
match expr.expr_desc with 
163 
 Expr_const _ 
164 
 Expr_ident _ > defvars, unfold_offsets expr offsets 
165 
 Expr_array elist > 
166 
let defvars, norm_elist = normalize_list alias node offsets (fun _ > normalize_array_expr ~alias:true) defvars elist in 
167 
let norm_expr = mk_norm_expr offsets expr (Expr_array norm_elist) in 
168 
mk_expr_alias_opt alias node defvars norm_expr 
169 
 Expr_power (e1, d) when offsets = [] > 
170 
let defvars, norm_e1 = normalize_expr node offsets defvars e1 in 
171 
let norm_expr = mk_norm_expr offsets expr (Expr_power (norm_e1, d)) in 
172 
mk_expr_alias_opt alias node defvars norm_expr 
173 
 Expr_power (e1, d) > 
174 
normalize_expr ~alias:alias node (List.tl offsets) defvars e1 
175 
 Expr_access (e1, d) > 
176 
normalize_expr ~alias:alias node (d::offsets) defvars e1 
177 
 Expr_tuple elist > 
178 
let defvars, norm_elist = 
179 
normalize_list alias node offsets (fun alias > normalize_expr ~alias:alias) defvars elist in 
180 
defvars, mk_norm_expr offsets expr (Expr_tuple norm_elist) 
181 
 Expr_appl (id, args, None) 
182 
when Basic_library.is_internal_fun id 
183 
&& Types.is_array_type expr.expr_type > 
184 
let defvars, norm_args = 
185 
normalize_list 
186 
alias 
187 
node 
188 
offsets 
189 
(fun _ > normalize_array_expr ~alias:true) 
190 
defvars 
191 
(expr_list_of_expr args) 
192 
in 
193 
defvars, mk_norm_expr offsets expr (Expr_appl (id, expr_of_expr_list args.expr_loc norm_args, None)) 
194 
 Expr_appl (id, args, None) when Basic_library.is_internal_fun id > 
195 
let defvars, norm_args = normalize_expr ~alias:true node offsets defvars args in 
196 
defvars, mk_norm_expr offsets expr (Expr_appl (id, norm_args, None)) 
197 
 Expr_appl (id, args, r) > 
198 
let defvars, norm_args = normalize_expr node [] defvars args in 
199 
let norm_expr = mk_norm_expr [] expr (Expr_appl (id, norm_args, r)) in 
200 
if offsets <> [] 
201 
then 
202 
let defvars, norm_expr = normalize_expr node [] defvars norm_expr in 
203 
normalize_expr ~alias:alias node offsets defvars norm_expr 
204 
else 
205 
mk_expr_alias_opt (alias && not (Basic_library.is_internal_fun id)) node defvars norm_expr 
206 
 Expr_arrow (e1,e2) when !unfold_arrow_active && not (is_expr_once expr) > (* Here we differ from Colaco paper: arrows are pushed to the top *) 
207 
normalize_expr ~alias:alias node offsets defvars (unfold_arrow expr) 
208 
 Expr_arrow (e1,e2) > 
209 
let defvars, norm_e1 = normalize_expr node offsets defvars e1 in 
210 
let defvars, norm_e2 = normalize_expr node offsets defvars e2 in 
211 
let norm_expr = mk_norm_expr offsets expr (Expr_arrow (norm_e1, norm_e2)) in 
212 
mk_expr_alias_opt alias node defvars norm_expr 
213 
 Expr_pre e > 
214 
let defvars, norm_e = normalize_expr node offsets defvars e in 
215 
let norm_expr = mk_norm_expr offsets expr (Expr_pre norm_e) in 
216 
mk_expr_alias_opt alias node defvars norm_expr 
217 
 Expr_fby (e1, e2) > 
218 
let defvars, norm_e1 = normalize_expr node offsets defvars e1 in 
219 
let defvars, norm_e2 = normalize_expr node offsets defvars e2 in 
220 
let norm_expr = mk_norm_expr offsets expr (Expr_fby (norm_e1, norm_e2)) in 
221 
mk_expr_alias_opt alias node defvars norm_expr 
222 
 Expr_when (e, c, l) > 
223 
let defvars, norm_e = normalize_expr node offsets defvars e in 
224 
defvars, mk_norm_expr offsets expr (Expr_when (norm_e, c, l)) 
225 
 Expr_ite (c, t, e) > 
226 
let defvars, norm_c = normalize_guard node defvars c in 
227 
let defvars, norm_t = normalize_cond_expr node offsets defvars t in 
228 
let defvars, norm_e = normalize_cond_expr node offsets defvars e in 
229 
let norm_expr = mk_norm_expr offsets expr (Expr_ite (norm_c, norm_t, norm_e)) in 
230 
mk_expr_alias_opt alias node defvars norm_expr 
231 
 Expr_merge (c, hl) > 
232 
let defvars, norm_hl = normalize_branches node offsets defvars hl in 
233 
let norm_expr = mk_norm_expr offsets expr (Expr_merge (c, norm_hl)) in 
234 
mk_expr_alias_opt alias node defvars norm_expr 
235 

236 
(* Creates a conditional with a merge construct, which is more lazy *) 
237 
(* 
238 
let norm_conditional_as_merge alias node norm_expr offsets defvars expr = 
239 
match expr.expr_desc with 
240 
 Expr_ite (c, t, e) > 
241 
let defvars, norm_t = norm_expr (alias node offsets defvars t in 
242 
 _ > assert false 
243 
*) 
244 
and normalize_branches node offsets defvars hl = 
245 
List.fold_right 
246 
(fun (t, h) (defvars, norm_q) > 
247 
let (defvars, norm_h) = normalize_cond_expr node offsets defvars h in 
248 
defvars, (t, norm_h) :: norm_q 
249 
) 
250 
hl (defvars, []) 
251  
252 
and normalize_array_expr ?(alias=true) node offsets defvars expr = 
253 
(* Format.eprintf "normalize_array %B %a [%a]@." alias Printers.pp_expr expr (Utils.fprintf_list ~sep:"," Dimension.pp_dimension) offsets;*) 
254 
match expr.expr_desc with 
255 
 Expr_power (e1, d) when offsets = [] > 
256 
let defvars, norm_e1 = normalize_expr node offsets defvars e1 in 
257 
defvars, mk_norm_expr offsets expr (Expr_power (norm_e1, d)) 
258 
 Expr_power (e1, d) > 
259 
normalize_array_expr ~alias:alias node (List.tl offsets) defvars e1 
260 
 Expr_access (e1, d) > normalize_array_expr ~alias:alias node (d::offsets) defvars e1 
261 
 Expr_array elist when offsets = [] > 
262 
let defvars, norm_elist = normalize_list alias node offsets (fun _ > normalize_array_expr ~alias:true) defvars elist in 
263 
defvars, mk_norm_expr offsets expr (Expr_array norm_elist) 
264 
 Expr_appl (id, args, None) when Basic_library.is_internal_fun id > 
265 
let defvars, norm_args = normalize_list alias node offsets (fun _ > normalize_array_expr ~alias:true) defvars (expr_list_of_expr args) in 
266 
defvars, mk_norm_expr offsets expr (Expr_appl (id, expr_of_expr_list args.expr_loc norm_args, None)) 
267 
 _ > normalize_expr ~alias:alias node offsets defvars expr 
268  
269 
and normalize_cond_expr ?(alias=true) node offsets defvars expr = 
270 
(*Format.eprintf "normalize_cond %B %a [%a]@." alias Printers.pp_expr expr (Utils.fprintf_list ~sep:"," Dimension.pp_dimension) offsets;*) 
271 
match expr.expr_desc with 
272 
 Expr_access (e1, d) > 
273 
normalize_cond_expr ~alias:alias node (d::offsets) defvars e1 
274 
 Expr_ite (c, t, e) > 
275 
let defvars, norm_c = normalize_guard node defvars c in 
276 
let defvars, norm_t = normalize_cond_expr node offsets defvars t in 
277 
let defvars, norm_e = normalize_cond_expr node offsets defvars e in 
278 
defvars, mk_norm_expr offsets expr (Expr_ite (norm_c, norm_t, norm_e)) 
279 
 Expr_merge (c, hl) > 
280 
let defvars, norm_hl = normalize_branches node offsets defvars hl in 
281 
defvars, mk_norm_expr offsets expr (Expr_merge (c, norm_hl)) 
282 
 _ > normalize_expr ~alias:alias node offsets defvars expr 
283  
284 
and normalize_guard node defvars expr = 
285 
let defvars, norm_expr = normalize_expr node [] defvars expr in 
286 
mk_expr_alias_opt true node defvars norm_expr 
287  
288 
(* outputs cannot be memories as well. If so, introduce new local variable. 
289 
*) 
290 
let decouple_outputs node defvars eq = 
291 
let rec fold_lhs defvars lhs tys cks = 
292 
match lhs, tys, cks with 
293 
 [], [], [] > defvars, [] 
294 
 v::qv, t::qt, c::qc > let (defs_q, vars_q), lhs_q = fold_lhs defvars qv qt qc in 
295 
if List.exists (fun o > o.var_id = v) node.node_outputs 
296 
then 
297 
let newvar = mk_fresh_var node eq.eq_loc t c in 
298 
let neweq = mkeq eq.eq_loc ([v], expr_of_vdecl newvar) in 
299 
(neweq :: defs_q, newvar :: vars_q), newvar.var_id :: lhs_q 
300 
else 
301 
(defs_q, vars_q), v::lhs_q 
302 
 _ > assert false in 
303 
let defvars', lhs' = 
304 
fold_lhs 
305 
defvars 
306 
eq.eq_lhs 
307 
(Types.type_list_of_type eq.eq_rhs.expr_type) 
308 
(Clocks.clock_list_of_clock eq.eq_rhs.expr_clock) in 
309 
defvars', {eq with eq_lhs = lhs' } 
310  
311 
let rec normalize_eq node defvars eq = 
312 
match eq.eq_rhs.expr_desc with 
313 
 Expr_pre _ 
314 
 Expr_fby _ > 
315 
let (defvars', eq') = decouple_outputs node defvars eq in 
316 
let (defs', vars'), norm_rhs = normalize_expr ~alias:false node [] defvars' eq'.eq_rhs in 
317 
let norm_eq = { eq' with eq_rhs = norm_rhs } in 
318 
(norm_eq::defs', vars') 
319 
 Expr_array _ > 
320 
let (defs', vars'), norm_rhs = normalize_array_expr ~alias:false node [] defvars eq.eq_rhs in 
321 
let norm_eq = { eq with eq_rhs = norm_rhs } in 
322 
(norm_eq::defs', vars') 
323 
 Expr_appl (id, _, None) when Basic_library.is_internal_fun id && Types.is_array_type eq.eq_rhs.expr_type > 
324 
let (defs', vars'), norm_rhs = normalize_array_expr ~alias:false node [] defvars eq.eq_rhs in 
325 
let norm_eq = { eq with eq_rhs = norm_rhs } in 
326 
(norm_eq::defs', vars') 
327 
 Expr_appl _ > 
328 
let (defs', vars'), norm_rhs = normalize_expr ~alias:false node [] defvars eq.eq_rhs in 
329 
let norm_eq = { eq with eq_rhs = norm_rhs } in 
330 
(norm_eq::defs', vars') 
331 
 _ > 
332 
let (defs', vars'), norm_rhs = normalize_cond_expr ~alias:false node [] defvars eq.eq_rhs in 
333 
let norm_eq = { eq with eq_rhs = norm_rhs } in 
334 
norm_eq::defs', vars' 
335  
336 
(** normalize_node node returns a normalized node, 
337 
ie. 
338 
 updated locals 
339 
 new equations 
340 
 
341 
*) 
342 
let normalize_node node = 
343 
cpt_fresh := 0; 
344 
let inputs_outputs = node.node_inputs@node.node_outputs in 
345 
let is_local v = 
346 
List.for_all ((!=) v) inputs_outputs in 
347 
let orig_vars = inputs_outputs@node.node_locals in 
348 
let defs, vars = 
349 
List.fold_left (normalize_eq node) ([], orig_vars) (get_node_eqs node) in 
350 
(* Normalize the asserts *) 
351 
let vars, assert_defs, asserts = 
352 
List.fold_left ( 
353 
fun (vars, def_accu, assert_accu) assert_ > 
354 
let assert_expr = assert_.assert_expr in 
355 
let (defs, vars'), expr = 
356 
normalize_expr 
357 
~alias:true 
358 
node 
359 
[] (* empty offset for arrays *) 
360 
([], vars) (* defvar only contains vars *) 
361 
assert_expr 
362 
in 
363 
(* Format.eprintf "New assert vars: %a@.@?" (fprintf_list ~sep:", " Printers.pp_var) vars'; *) 
364 
vars', defs@def_accu, {assert_ with assert_expr = expr}::assert_accu 
365 
) (vars, [], []) node.node_asserts in 
366 
let new_locals = List.filter is_local vars in 
367 
(* Format.eprintf "New locals: %a@.@?" (fprintf_list ~sep:", " Printers.pp_var) new_locals; *) 
368  
369 
let new_annots = 
370 
if !Options.traces then 
371 
begin 
372 
(* Compute traceability info: 
373 
 gather newly bound variables 
374 
 compute the associated expression without aliases 
375 
*) 
376 
let diff_vars = List.filter (fun v > not (List.mem v node.node_locals) ) new_locals in 
377 
let norm_traceability = { 
378 
annots = List.map (fun v > 
379 
let eq = 
380 
try 
381 
List.find (fun eq > eq.eq_lhs = [v.var_id]) defs 
382 
with Not_found > (Format.eprintf "var not found %s@." v.var_id; assert false) in 
383 
let expr = substitute_expr diff_vars defs eq.eq_rhs in 
384 
let pair = mkeexpr expr.expr_loc (mkexpr expr.expr_loc (Expr_tuple [expr_of_ident v.var_id expr.expr_loc; expr])) in 
385 
(["traceability"], pair) 
386 
) diff_vars; 
387 
annot_loc = Location.dummy_loc 
388 
} 
389 
in 
390 
norm_traceability::node.node_annot 
391 
end 
392 
else 
393 
node.node_annot 
394 
in 
395  
396 
let node = 
397 
{ node with 
398 
node_locals = new_locals; 
399 
node_stmts = List.map (fun eq > Eq eq) (defs @ assert_defs); 
400 
node_asserts = asserts; 
401 
node_annot = new_annots; 
402 
} 
403 
in ((*Printers.pp_node Format.err_formatter node;*) 
404 
node 
405 
) 
406  
407  
408 
let normalize_decl decl = 
409 
match decl.top_decl_desc with 
410 
 Node nd > 
411 
let decl' = {decl with top_decl_desc = Node (normalize_node nd)} in 
412 
Hashtbl.replace Corelang.node_table nd.node_id decl'; 
413 
decl' 
414 
 Open _  ImportedNode _  Const _  TypeDef _ > decl 
415 

416 
let normalize_prog decls = 
417 
List.map normalize_decl decls 
418  
419 
(* Local Variables: *) 
420 
(* compilecommand:"make C .." *) 
421 
(* End: *) 