Project

General

Profile

Statistics
| Branch: | Tag: | Revision:

lustrec / src / normalization.ml @ 54d032f5

History | View | Annotate | Download (16.4 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
(* Generate a new ident expression from a declared variable *)
79
let mk_ident_expr v =
80
  { expr_tag = new_tag ();
81
    expr_desc = Expr_ident v.var_id;
82
    expr_type = v.var_type;
83
    expr_clock = v.var_clock;
84
    expr_delay = Delay.new_var ();
85
    expr_annot = None;
86
    expr_loc = v.var_loc }
87

    
88
(* Get the equation in [defs] with [expr] as rhs, if any *)
89
let get_expr_alias defs expr =
90
 try Some (List.find (fun eq -> is_eq_expr eq.eq_rhs expr) defs)
91
 with
92
   Not_found -> None
93

    
94
(* Replace [expr] with (tuple of) [locals] *)
95
let replace_expr locals expr =
96
 match locals with
97
 | []  -> assert false
98
 | [v] -> { expr with
99
   expr_tag = Utils.new_tag ();
100
   expr_desc = Expr_ident v.var_id }
101
 | _   -> { expr with
102
   expr_tag = Utils.new_tag ();
103
   expr_desc = Expr_tuple (List.map mk_ident_expr locals) }
104

    
105
let unfold_offsets e offsets =
106
  let add_offset e d =
107
(*Format.eprintf "add_offset %a %a@." Dimension.pp_dimension (Types.array_type_dimension e.expr_type) Dimension.pp_dimension d;*)
108
    { e with
109
      expr_tag = Utils.new_tag ();
110
      expr_loc = d.Dimension.dim_loc;
111
      expr_type = Types.array_element_type e.expr_type;
112
      expr_desc = Expr_access (e, d) } in
113
 List.fold_left add_offset e offsets
114

    
115
(* Create an alias for [expr], if none exists yet *)
116
let mk_expr_alias node (defs, vars) expr =
117
(*Format.eprintf "mk_expr_alias %a %a %a@." Printers.pp_expr expr Types.print_ty expr.expr_type Clocks.print_ck expr.expr_clock;*)
118
  match get_expr_alias defs expr with
119
  | Some eq ->
120
    let aliases = List.map (fun id -> List.find (fun v -> v.var_id = id) vars) eq.eq_lhs in
121
    (defs, vars), replace_expr aliases expr
122
  | None    ->
123
    let new_aliases =
124
      List.map2
125
	(mk_fresh_var node expr.expr_loc)
126
	(Types.type_list_of_type expr.expr_type)
127
	(Clocks.clock_list_of_clock expr.expr_clock) in
128
    let new_def =
129
      mkeq expr.expr_loc (List.map (fun v -> v.var_id) new_aliases, expr)
130
    in (new_def::defs, new_aliases@vars), replace_expr new_aliases expr
131

    
132
(* Create an alias for [expr], if [expr] is not already an alias (i.e. an ident)
133
   and [opt] is true *)
134
let mk_expr_alias_opt opt node defvars expr =
135
  match expr.expr_desc with
136
  | Expr_ident alias ->
137
    defvars, expr
138
  | _                -> 
139
    if opt
140
    then
141
      mk_expr_alias node defvars expr
142
    else
143
      defvars, expr
144

    
145
(* Create a (normalized) expression from [ref_e], 
146
   replacing description with [norm_d],
147
   taking propagated [offsets] into account 
148
   in order to change expression type *)
149
let mk_norm_expr offsets ref_e norm_d =
150
  let drop_array_type ty =
151
    Types.map_tuple_type Types.array_element_type ty in
152
  { ref_e with
153
    expr_desc = norm_d;
154
    expr_type = Utils.repeat (List.length offsets) drop_array_type ref_e.expr_type }
155

    
156
(* normalize_<foo> : defs * used vars -> <foo> -> (updated defs * updated vars) * normalized <foo> *)
157
let rec normalize_list alias node offsets norm_element defvars elist =
158
  List.fold_right
159
    (fun t (defvars, qlist) ->
160
      let defvars, norm_t = norm_element alias node offsets defvars t in
161
      (defvars, norm_t :: qlist)
162
    ) elist (defvars, [])
163

    
164
let rec normalize_expr ?(alias=true) node offsets defvars expr =
165
(*  Format.eprintf "normalize %B %a [%a]@." alias Printers.pp_expr expr (Utils.fprintf_list ~sep:"," Dimension.pp_dimension) offsets;*)
166
  match expr.expr_desc with
167
  | Expr_const _ 
168
  | Expr_ident _ -> defvars, unfold_offsets expr offsets
169
  | Expr_array elist ->
170
    let defvars, norm_elist = normalize_list alias node offsets (fun _ -> normalize_array_expr ~alias:true) defvars elist in
171
    let norm_expr = mk_norm_expr offsets expr (Expr_array norm_elist) in
172
    mk_expr_alias_opt alias node defvars norm_expr
173
  | Expr_power (e1, d) when offsets = [] ->
174
    let defvars, norm_e1 = normalize_expr node offsets defvars e1 in
175
    let norm_expr = mk_norm_expr offsets expr (Expr_power (norm_e1, d)) in
176
    mk_expr_alias_opt alias node defvars norm_expr
177
  | Expr_power (e1, d) ->
178
    normalize_expr ~alias:alias node (List.tl offsets) defvars e1
179
  | Expr_access (e1, d) ->
180
    normalize_expr ~alias:alias node (d::offsets) defvars e1
181
  | Expr_tuple elist -> 
182
    let defvars, norm_elist =
183
      normalize_list alias node offsets (fun alias -> normalize_expr ~alias:alias) defvars elist in
184
    defvars, mk_norm_expr offsets expr (Expr_tuple norm_elist)
185
  | Expr_appl (id, args, None) 
186
      when Basic_library.is_internal_fun id 
187
	&& Types.is_array_type expr.expr_type ->
188
    let defvars, norm_args = 
189
      normalize_list 
190
	alias
191
	node
192
	offsets 
193
	(fun _ -> normalize_array_expr ~alias:true) 
194
	defvars 
195
	(expr_list_of_expr args) 
196
    in
197
    defvars, mk_norm_expr offsets expr (Expr_appl (id, expr_of_expr_list args.expr_loc norm_args, None))
198
  | Expr_appl (id, args, None) when Basic_library.is_internal_fun id ->
199
    let defvars, norm_args = normalize_expr ~alias:true node offsets defvars args in
200
    defvars, mk_norm_expr offsets expr (Expr_appl (id, norm_args, None))
201
  | Expr_appl (id, args, r) ->
202
    let defvars, norm_args = normalize_expr node [] defvars args in
203
    let norm_expr = mk_norm_expr [] expr (Expr_appl (id, norm_args, r)) in
204
    if offsets <> []
205
    then
206
      let defvars, norm_expr = normalize_expr node [] defvars norm_expr in
207
      normalize_expr ~alias:alias node offsets defvars norm_expr
208
    else
209
      mk_expr_alias_opt (alias && not (Basic_library.is_internal_fun id)) node defvars norm_expr
210
  | 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 *)
211
    normalize_expr ~alias:alias node offsets defvars (unfold_arrow expr)
212
  | Expr_arrow (e1,e2) ->
213
    let defvars, norm_e1 = normalize_expr node offsets defvars e1 in
214
    let defvars, norm_e2 = normalize_expr node offsets defvars e2 in
215
    let norm_expr = mk_norm_expr offsets expr (Expr_arrow (norm_e1, norm_e2)) in
216
    mk_expr_alias_opt alias node defvars norm_expr
217
  | Expr_pre e ->
218
    let defvars, norm_e = normalize_expr node offsets defvars e in
219
    let norm_expr = mk_norm_expr offsets expr (Expr_pre norm_e) in
220
    mk_expr_alias_opt alias node defvars norm_expr
221
  | Expr_fby (e1, e2) ->
222
    let defvars, norm_e1 = normalize_expr node offsets defvars e1 in
223
    let defvars, norm_e2 = normalize_expr node offsets defvars e2 in
224
    let norm_expr = mk_norm_expr offsets expr (Expr_fby (norm_e1, norm_e2)) in
225
    mk_expr_alias_opt alias node defvars norm_expr
226
  | Expr_when (e, c, l) ->
227
    let defvars, norm_e = normalize_expr node offsets defvars e in
228
    defvars, mk_norm_expr offsets expr (Expr_when (norm_e, c, l))
229
  | Expr_ite (c, t, e) ->
230
    let defvars, norm_c = normalize_guard node defvars c in
231
    let defvars, norm_t = normalize_cond_expr  node offsets defvars t in
232
    let defvars, norm_e = normalize_cond_expr  node offsets defvars e in
233
    let norm_expr = mk_norm_expr offsets expr (Expr_ite (norm_c, norm_t, norm_e)) in
234
    mk_expr_alias_opt alias node defvars norm_expr
235
  | Expr_merge (c, hl) ->
236
    let defvars, norm_hl = normalize_branches node offsets defvars hl in
237
    let norm_expr = mk_norm_expr offsets expr (Expr_merge (c, norm_hl)) in
238
    mk_expr_alias_opt alias node defvars norm_expr
239
  
240
(* Creates a conditional with a merge construct, which is more lazy *)
241
(*
242
let norm_conditional_as_merge alias node norm_expr offsets defvars expr =
243
 match expr.expr_desc with
244
 | Expr_ite (c, t, e) ->
245
   let defvars, norm_t = norm_expr (alias node offsets defvars t in
246
 | _ -> assert false
247
*)
248
and normalize_branches node offsets defvars hl =
249
 List.fold_right
250
   (fun (t, h) (defvars, norm_q) ->
251
     let (defvars, norm_h) = normalize_cond_expr node offsets defvars h in
252
     defvars, (t, norm_h) :: norm_q
253
   )
254
   hl (defvars, [])
255

    
256
and normalize_array_expr ?(alias=true) node offsets defvars expr =
257
(*  Format.eprintf "normalize_array %B %a [%a]@." alias Printers.pp_expr expr (Utils.fprintf_list ~sep:"," Dimension.pp_dimension) offsets;*)
258
  match expr.expr_desc with
259
  | Expr_power (e1, d) when offsets = [] ->
260
    let defvars, norm_e1 = normalize_expr node offsets defvars e1 in
261
    defvars, mk_norm_expr offsets expr (Expr_power (norm_e1, d))
262
  | Expr_power (e1, d) ->
263
    normalize_array_expr ~alias:alias node (List.tl offsets) defvars e1
264
  | Expr_access (e1, d) -> normalize_array_expr ~alias:alias node (d::offsets) defvars e1
265
  | Expr_array elist when offsets = [] ->
266
    let defvars, norm_elist = normalize_list alias node offsets (fun _ -> normalize_array_expr ~alias:true) defvars elist in
267
    defvars, mk_norm_expr offsets expr (Expr_array norm_elist)
268
  | Expr_appl (id, args, None) when Basic_library.is_internal_fun id ->
269
    let defvars, norm_args = normalize_list alias node offsets (fun _ -> normalize_array_expr ~alias:true) defvars (expr_list_of_expr args) in
270
    defvars, mk_norm_expr offsets expr (Expr_appl (id, expr_of_expr_list args.expr_loc norm_args, None))
271
  |  _ -> normalize_expr ~alias:alias node offsets defvars expr
272

    
273
and normalize_cond_expr ?(alias=true) node offsets defvars expr =
274
  (*Format.eprintf "normalize_cond %B %a [%a]@." alias Printers.pp_expr expr (Utils.fprintf_list ~sep:"," Dimension.pp_dimension) offsets;*)
275
  match expr.expr_desc with
276
  | Expr_access (e1, d) ->
277
    normalize_cond_expr ~alias:alias node (d::offsets) defvars e1
278
  | Expr_ite (c, t, e) ->
279
    let defvars, norm_c = normalize_guard node defvars c in
280
    let defvars, norm_t = normalize_cond_expr node offsets defvars t in
281
    let defvars, norm_e = normalize_cond_expr node offsets defvars e in
282
    defvars, mk_norm_expr offsets expr (Expr_ite (norm_c, norm_t, norm_e))
283
  | Expr_merge (c, hl) ->
284
    let defvars, norm_hl = normalize_branches node offsets defvars hl in
285
    defvars, mk_norm_expr offsets expr (Expr_merge (c, norm_hl))
286
  | _ -> normalize_expr ~alias:alias node offsets defvars expr
287

    
288
and normalize_guard node defvars expr =
289
  let defvars, norm_expr = normalize_expr node [] defvars expr in
290
  mk_expr_alias_opt true node defvars norm_expr
291

    
292
(* outputs cannot be memories as well. If so, introduce new local variable.
293
*)
294
let decouple_outputs node defvars eq =
295
  let rec fold_lhs defvars lhs tys cks =
296
   match lhs, tys, cks with
297
   | [], [], []          -> defvars, []
298
   | v::qv, t::qt, c::qc -> let (defs_q, vars_q), lhs_q = fold_lhs defvars qv qt qc in
299
			    if List.exists (fun o -> o.var_id = v) node.node_outputs
300
			    then
301
			      let newvar = mk_fresh_var node eq.eq_loc t c in
302
			      let neweq  = mkeq eq.eq_loc ([v], mk_ident_expr newvar) in
303
			      (neweq :: defs_q, newvar :: vars_q), newvar.var_id :: lhs_q
304
			    else
305
			      (defs_q, vars_q), v::lhs_q
306
   | _                   -> assert false in
307
  let defvars', lhs' =
308
    fold_lhs
309
      defvars
310
      eq.eq_lhs
311
      (Types.type_list_of_type eq.eq_rhs.expr_type)
312
      (Clocks.clock_list_of_clock eq.eq_rhs.expr_clock) in
313
  defvars', {eq with eq_lhs = lhs' }
314

    
315
let rec normalize_eq node defvars eq = 
316
  match eq.eq_rhs.expr_desc with
317
  | Expr_pre _
318
  | Expr_fby _  ->
319
    let (defvars', eq') = decouple_outputs node defvars eq in
320
    let (defs', vars'), norm_rhs = normalize_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_array _ ->
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 (id, _, None) when Basic_library.is_internal_fun id && Types.is_array_type eq.eq_rhs.expr_type ->
328
    let (defs', vars'), norm_rhs = normalize_array_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
  | Expr_appl _ ->
332
    let (defs', vars'), norm_rhs = normalize_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
    let (defs', vars'), norm_rhs = normalize_cond_expr ~alias:false node [] defvars eq.eq_rhs in
337
    let norm_eq = { eq with eq_rhs = norm_rhs } in
338
    norm_eq::defs', vars'
339

    
340
(** normalize_node node returns a normalized node, 
341
    ie. 
342
    - updated locals
343
    - new equations
344
    - 
345
*)
346
let normalize_node node = 
347
  cpt_fresh := 0;
348
  let inputs_outputs = node.node_inputs@node.node_outputs in
349
  let is_local v =
350
    List.for_all ((!=) v) inputs_outputs in
351
  let orig_vars = inputs_outputs@node.node_locals in
352
  let defs, vars = 
353
    List.fold_left (normalize_eq node) ([], orig_vars) (get_node_eqs node) in
354
  (* Normalize the asserts *)
355
  let vars, assert_defs, asserts = 
356
    List.fold_left (
357
    fun (vars, def_accu, assert_accu) assert_ ->
358
      let assert_expr = assert_.assert_expr in
359
      let (defs, vars'), expr = 
360
	normalize_expr 
361
	  ~alias:false 
362
	  node 
363
	  [] (* empty offset for arrays *)
364
	  ([], vars) (* defvar only contains vars *)
365
	  assert_expr
366
      in
367
      vars', defs@def_accu, {assert_ with assert_expr = expr}::assert_accu
368
    ) (vars, [], []) node.node_asserts in
369
  let new_locals = List.filter is_local vars in
370
  (* Compute traceability info: 
371
     - gather newly bound variables
372
     - compute the associated expression without aliases     
373
  *)
374
  let diff_vars = List.filter (fun v -> not (List.mem v node.node_locals) ) new_locals in
375
  let split_defs = Splitting.tuple_split_eq_list defs in
376
  let norm_traceability = {
377
    annots = List.map (fun v ->
378
      let eq =
379
	try
380
	  List.find (fun eq -> eq.eq_lhs = [v.var_id]) split_defs 
381
	with Not_found -> (Format.eprintf "var not found %s@." v.var_id; assert false) in
382
      let expr = substitute_expr diff_vars split_defs eq.eq_rhs in
383
      let pair = mkeexpr expr.expr_loc (mkexpr expr.expr_loc (Expr_tuple [expr_of_ident v.var_id expr.expr_loc; expr])) in
384
      (["horn_backend";"trace"], pair)
385
    ) diff_vars;
386
    annot_loc = Location.dummy_loc
387
  }
388

    
389
  in
390
  let node =
391
  { node with 
392
    node_locals = new_locals; 
393
    node_stmts = List.map (fun eq -> Eq eq) (defs @ assert_defs);
394
    node_asserts = asserts;
395
    node_annot = norm_traceability::node.node_annot;
396
  }
397
  in ((*Printers.pp_node Format.err_formatter node;*) node)
398

    
399
let normalize_decl decl =
400
  match decl.top_decl_desc with
401
  | Node nd ->
402
    {decl with top_decl_desc = Node (normalize_node nd)}
403
  | Open _ | ImportedNode _ | Const _ | TypeDef _ -> decl
404
  
405
let normalize_prog decls = 
406
  List.map normalize_decl decls
407

    
408
(* Local Variables: *)
409
(* compile-command:"make -C .." *)
410
(* End: *)