Project

General

Profile

Statistics
| Branch: | Tag: | Revision:

lustrec / src / normalization.ml @ a38c681e

History | View | Annotate | Download (16.8 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
(* This module is used for the lustre to C compiler *)
25

    
26

    
27
open Utils
28
open LustreSpec
29
open Corelang
30
(* open Clocks *)
31
open Format
32

    
33
let expr_true loc ck =
34
{ expr_tag = Utils.new_tag ();
35
  expr_desc = Expr_const (Const_tag tag_true);
36
  expr_type = Type_predef.type_bool;
37
  expr_clock = ck;
38
  expr_delay = Delay.new_var ();
39
  expr_annot = None;
40
  expr_loc = loc }
41

    
42
let expr_false loc ck =
43
{ expr_tag = Utils.new_tag ();
44
  expr_desc = Expr_const (Const_tag tag_false);
45
  expr_type = Type_predef.type_bool;
46
  expr_clock = ck;
47
  expr_delay = Delay.new_var ();
48
  expr_annot = None;
49
  expr_loc = loc }
50

    
51
let expr_once loc ck =
52
 { expr_tag = Utils.new_tag ();
53
  expr_desc = Expr_arrow (expr_true loc ck, expr_false loc ck);
54
  expr_type = Type_predef.type_bool;
55
  expr_clock = ck;
56
  expr_delay = Delay.new_var ();
57
  expr_annot = None;
58
  expr_loc = loc }
59

    
60
let is_expr_once =
61
  let dummy_expr_once = expr_once Location.dummy_loc (Clocks.new_var true) in
62
  fun expr -> Corelang.is_eq_expr expr dummy_expr_once
63

    
64
let unfold_arrow expr =
65
 match expr.expr_desc with
66
 | Expr_arrow (e1, e2) ->
67
    let loc = expr.expr_loc in
68
    let ck = List.hd (Clocks.clock_list_of_clock expr.expr_clock) in
69
    { expr with expr_desc = Expr_ite (expr_once loc ck, e1, e2) }
70
 | _                   -> assert false
71

    
72
let unfold_arrow_active = ref true 
73
let cpt_fresh = ref 0
74

    
75
(* Generate a new local [node] variable *)
76
let mk_fresh_var node loc ty ck =
77
  let vars = get_node_vars node in
78
  let rec aux () =
79
  incr cpt_fresh;
80
  let s = Printf.sprintf "__%s_%d" node.node_id !cpt_fresh in
81
  if List.exists (fun v -> v.var_id = s) vars then aux () else
82
  {
83
    var_id = s;
84
    var_dec_type = dummy_type_dec;
85
    var_dec_clock = dummy_clock_dec;
86
    var_dec_const = false;
87
    var_type = ty;
88
    var_clock = ck;
89
    var_loc = loc
90
  }
91
  in aux ()
92

    
93
(* Generate a new ident expression from a declared variable *)
94
let mk_ident_expr v =
95
  { expr_tag = new_tag ();
96
    expr_desc = Expr_ident v.var_id;
97
    expr_type = v.var_type;
98
    expr_clock = v.var_clock;
99
    expr_delay = Delay.new_var ();
100
    expr_annot = None;
101
    expr_loc = v.var_loc }
102

    
103
(* Get the equation in [defs] with [expr] as rhs, if any *)
104
let get_expr_alias defs expr =
105
 try Some (List.find (fun eq -> is_eq_expr eq.eq_rhs expr) defs)
106
 with
107
   Not_found -> None
108

    
109
(* Replace [expr] with (tuple of) [locals] *)
110
let replace_expr locals expr =
111
 match locals with
112
 | []  -> assert false
113
 | [v] -> { expr with
114
   expr_tag = Utils.new_tag ();
115
   expr_desc = Expr_ident v.var_id }
116
 | _   -> { expr with
117
   expr_tag = Utils.new_tag ();
118
   expr_desc = Expr_tuple (List.map mk_ident_expr locals) }
119

    
120
let unfold_offsets e offsets =
121
  let add_offset e d =
122
(*Format.eprintf "add_offset %a %a@." Dimension.pp_dimension (Types.array_type_dimension e.expr_type) Dimension.pp_dimension d;*)
123
    { e with
124
      expr_tag = Utils.new_tag ();
125
      expr_loc = d.Dimension.dim_loc;
126
      expr_type = Types.array_element_type e.expr_type;
127
      expr_desc = Expr_access (e, d) } in
128
 List.fold_left add_offset e offsets
129

    
130
(* Create an alias for [expr], if none exists yet *)
131
let mk_expr_alias node (defs, vars) expr =
132
(*Format.eprintf "mk_expr_alias %a %a %a@." Printers.pp_expr expr Types.print_ty expr.expr_type Clocks.print_ck expr.expr_clock;*)
133
  match get_expr_alias defs expr with
134
  | Some eq ->
135
    let aliases = List.map (fun id -> List.find (fun v -> v.var_id = id) vars) eq.eq_lhs in
136
    (defs, vars), replace_expr aliases expr
137
  | None    ->
138
    let new_aliases =
139
      List.map2
140
	(mk_fresh_var node expr.expr_loc)
141
	(Types.type_list_of_type expr.expr_type)
142
	(Clocks.clock_list_of_clock expr.expr_clock) in
143
    let new_def =
144
      mkeq expr.expr_loc (List.map (fun v -> v.var_id) new_aliases, expr)
145
    in (new_def::defs, new_aliases@vars), replace_expr new_aliases expr
146

    
147
(* Create an alias for [expr], if [expr] is not already an alias (i.e. an ident)
148
   and [opt] is true *)
149
let mk_expr_alias_opt opt node defvars expr =
150
  match expr.expr_desc with
151
  | Expr_ident alias ->
152
    defvars, expr
153
  | _                -> 
154
    if opt
155
    then
156
      mk_expr_alias node defvars expr
157
    else
158
      defvars, expr
159

    
160
(* Create a (normalized) expression from [ref_e], 
161
   replacing description with [norm_d],
162
   taking propagated [offsets] into account 
163
   in order to change expression type *)
164
let mk_norm_expr offsets ref_e norm_d =
165
  let drop_array_type ty =
166
    Types.map_tuple_type Types.array_element_type ty in
167
  { ref_e with
168
    expr_desc = norm_d;
169
    expr_type = Utils.repeat (List.length offsets) drop_array_type ref_e.expr_type }
170

    
171
(* normalize_<foo> : defs * used vars -> <foo> -> (updated defs * updated vars) * normalized <foo> *)
172
let rec normalize_list alias node offsets norm_element defvars elist =
173
  List.fold_right
174
    (fun t (defvars, qlist) ->
175
      let defvars, norm_t = norm_element alias node offsets defvars t in
176
      (defvars, norm_t :: qlist)
177
    ) elist (defvars, [])
178

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

    
271
and normalize_array_expr ?(alias=true) node offsets defvars expr =
272
(*  Format.eprintf "normalize_array %B %a [%a]@." alias Printers.pp_expr expr (Utils.fprintf_list ~sep:"," Dimension.pp_dimension) offsets;*)
273
  match expr.expr_desc with
274
  | Expr_power (e1, d) when offsets = [] ->
275
    let defvars, norm_e1 = normalize_expr node offsets defvars e1 in
276
    defvars, mk_norm_expr offsets expr (Expr_power (norm_e1, d))
277
  | Expr_power (e1, d) ->
278
    normalize_array_expr ~alias:alias node (List.tl offsets) defvars e1
279
  | Expr_access (e1, d) -> normalize_array_expr ~alias:alias node (d::offsets) defvars e1
280
  | Expr_array elist when offsets = [] ->
281
    let defvars, norm_elist = normalize_list alias node offsets (fun _ -> normalize_array_expr ~alias:true) defvars elist in
282
    defvars, mk_norm_expr offsets expr (Expr_array norm_elist)
283
  | Expr_appl (id, args, None) when Basic_library.is_internal_fun id ->
284
    let defvars, norm_args = normalize_list alias node offsets (fun _ -> normalize_array_expr ~alias:true) defvars (expr_list_of_expr args) in
285
    defvars, mk_norm_expr offsets expr (Expr_appl (id, expr_of_expr_list args.expr_loc norm_args, None))
286
  |  _ -> normalize_expr ~alias:alias node offsets defvars expr
287

    
288
and normalize_cond_expr ?(alias=true) node offsets defvars expr =
289
  (*Format.eprintf "normalize_cond %B %a [%a]@." alias Printers.pp_expr expr (Utils.fprintf_list ~sep:"," Dimension.pp_dimension) offsets;*)
290
  match expr.expr_desc with
291
  | Expr_access (e1, d) ->
292
    normalize_cond_expr ~alias:alias node (d::offsets) defvars e1
293
  | Expr_ite (c, t, e) ->
294
    let defvars, norm_c = normalize_guard node defvars c in
295
    let defvars, norm_t = normalize_cond_expr node offsets defvars t in
296
    let defvars, norm_e = normalize_cond_expr node offsets defvars e in
297
    defvars, mk_norm_expr offsets expr (Expr_ite (norm_c, norm_t, norm_e))
298
  | Expr_merge (c, hl) ->
299
    let defvars, norm_hl = normalize_branches node offsets defvars hl in
300
    defvars, mk_norm_expr offsets expr (Expr_merge (c, norm_hl))
301
  | _ -> normalize_expr ~alias:alias node offsets defvars expr
302

    
303
and normalize_guard node defvars expr =
304
  let defvars, norm_expr = normalize_expr node [] defvars expr in
305
  mk_expr_alias_opt true node defvars norm_expr
306

    
307
(* outputs cannot be memories as well. If so, introduce new local variable.
308
*)
309
let decouple_outputs node defvars eq =
310
  let rec fold_lhs defvars lhs tys cks =
311
   match lhs, tys, cks with
312
   | [], [], []          -> defvars, []
313
   | v::qv, t::qt, c::qc -> let (defs_q, vars_q), lhs_q = fold_lhs defvars qv qt qc in
314
			    if List.exists (fun o -> o.var_id = v) node.node_outputs
315
			    then
316
			      let newvar = mk_fresh_var node eq.eq_loc t c in
317
			      let neweq  = mkeq eq.eq_loc ([v], mk_ident_expr newvar) in
318
			      (neweq :: defs_q, newvar :: vars_q), newvar.var_id :: lhs_q
319
			    else
320
			      (defs_q, vars_q), v::lhs_q
321
   | _                   -> assert false in
322
  let defvars', lhs' =
323
    fold_lhs
324
      defvars
325
      eq.eq_lhs
326
      (Types.type_list_of_type eq.eq_rhs.expr_type)
327
      (Clocks.clock_list_of_clock eq.eq_rhs.expr_clock) in
328
  defvars', {eq with eq_lhs = lhs' }
329

    
330
let rec normalize_eq node defvars eq = 
331
  match eq.eq_rhs.expr_desc with
332
  | Expr_pre _
333
  | Expr_fby _  ->
334
    let (defvars', eq') = decouple_outputs node defvars eq in
335
    let (defs', vars'), norm_rhs = normalize_expr ~alias:false node [] defvars' eq'.eq_rhs in
336
    let norm_eq = { eq' with eq_rhs = norm_rhs } in
337
    (norm_eq::defs', vars')
338
  | Expr_array _ ->
339
    let (defs', vars'), norm_rhs = normalize_array_expr ~alias:false node [] defvars eq.eq_rhs in
340
    let norm_eq = { eq with eq_rhs = norm_rhs } in
341
    (norm_eq::defs', vars')
342
  | Expr_appl (id, _, None) when Basic_library.is_internal_fun id && Types.is_array_type eq.eq_rhs.expr_type ->
343
    let (defs', vars'), norm_rhs = normalize_array_expr ~alias:false node [] defvars eq.eq_rhs in
344
    let norm_eq = { eq with eq_rhs = norm_rhs } in
345
    (norm_eq::defs', vars')
346
  | Expr_appl _ ->
347
    let (defs', vars'), norm_rhs = normalize_expr ~alias:false node [] defvars eq.eq_rhs in
348
    let norm_eq = { eq with eq_rhs = norm_rhs } in
349
    (norm_eq::defs', vars')
350
  | _ ->
351
    let (defs', vars'), norm_rhs = normalize_cond_expr ~alias:false node [] defvars eq.eq_rhs in
352
    let norm_eq = { eq with eq_rhs = norm_rhs } in
353
    norm_eq::defs', vars'
354

    
355
(** normalize_node node returns a normalized node, 
356
    ie. 
357
    - updated locals
358
    - new equations
359
    - 
360
*)
361
let normalize_node node = 
362
  cpt_fresh := 0;
363
  let inputs_outputs = node.node_inputs@node.node_outputs in
364
  let is_local v =
365
    List.for_all ((!=) v) inputs_outputs in
366
  let orig_vars = inputs_outputs@node.node_locals in
367
  let defs, vars = 
368
    List.fold_left (normalize_eq node) ([], orig_vars) node.node_eqs in
369
  (* Normalize the asserts *)
370
  let vars, assert_defs, asserts = 
371
    List.fold_left (
372
    fun (vars, def_accu, assert_accu) assert_ ->
373
      let assert_expr = assert_.assert_expr in
374
      let (defs, vars'), expr = 
375
	normalize_expr 
376
	  ~alias:false 
377
	  node 
378
	  [] (* empty offset for arrays *)
379
	  ([], vars) (* defvar only contains vars *)
380
	  assert_expr
381
      in
382
      vars', defs@def_accu, {assert_ with assert_expr = expr}::assert_accu
383
    ) (vars, [], []) node.node_asserts in
384
  let new_locals = List.filter is_local vars in
385
  (* Compute tracebaility info: 
386
     - gather newly bound variables
387
     - compute the associated expression without aliases     
388
  *)
389
  let diff_vars = List.filter (fun v -> not (List.mem v node.node_locals) ) new_locals in
390
  let norm_traceability = {
391
    annots =
392
      List.map 
393
	(fun v -> 
394
	  let expr = substitute_expr diff_vars defs (
395
	    let eq = try
396
		       List.find (fun eq -> eq.eq_lhs = [v.var_id]) defs 
397
	      with Not_found -> (Format.eprintf "var not found %s@." v.var_id; assert false) in
398
	    eq.eq_rhs) in 
399
	  let pair = mkeexpr expr.expr_loc (mkexpr expr.expr_loc (Expr_tuple [expr_of_ident v.var_id expr.expr_loc; expr])) in 
400
	  ["horn_backend";"trace"], pair 
401
	)
402
    diff_vars ;
403
    annot_loc = Location.dummy_loc
404
  }
405

    
406
  in
407
  let node =
408
  { node with 
409
    node_locals = new_locals; 
410
    node_eqs = defs @ assert_defs;
411
    node_asserts = asserts;
412
    node_annot = norm_traceability::node.node_annot;
413
  }
414
  in ((*Printers.pp_node Format.err_formatter node;*) node)
415

    
416
let normalize_decl decl =
417
  match decl.top_decl_desc with
418
  | Node nd ->
419
    {decl with top_decl_desc = Node (normalize_node nd)}
420
  | Open _ | ImportedNode _ | Consts _ -> decl
421
  
422
let normalize_prog decls = 
423
  List.map normalize_decl decls
424

    
425
(* Local Variables: *)
426
(* compile-command:"make -C .." *)
427
(* End: *)