## lustrec / src / normalization.ml @ 53206908

History | View | Annotate | Download (17.3 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_dec_value = None; |

73 |
var_type = ty; |

74 |
var_clock = ck; |

75 |
var_loc = loc |

76 |
} |

77 |
in aux () |

78 | |

79 |
(* Get the equation in [defs] with [expr] as rhs, if any *) |

80 |
let get_expr_alias defs expr = |

81 |
try Some (List.find (fun eq -> is_eq_expr eq.eq_rhs expr) defs) |

82 |
with |

83 |
Not_found -> None |

84 | |

85 |
(* Replace [expr] with (tuple of) [locals] *) |

86 |
let replace_expr locals expr = |

87 |
match locals with |

88 |
| [] -> assert false |

89 |
| [v] -> { expr with |

90 |
expr_tag = Utils.new_tag (); |

91 |
expr_desc = Expr_ident v.var_id } |

92 |
| _ -> { expr with |

93 |
expr_tag = Utils.new_tag (); |

94 |
expr_desc = Expr_tuple (List.map expr_of_vdecl locals) } |

95 | |

96 |
let unfold_offsets e offsets = |

97 |
let add_offset e d = |

98 |
(*Format.eprintf "add_offset %a %a@." Dimension.pp_dimension (Types.array_type_dimension e.expr_type) Dimension.pp_dimension d;*) |

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) } in |

104 |
List.fold_left add_offset e offsets |

105 | |

106 |
(* Create an alias for [expr], if none exists yet *) |

107 |
let mk_expr_alias node (defs, vars) expr = |

108 |
(*Format.eprintf "mk_expr_alias %a %a %a@." Printers.pp_expr expr Types.print_ty expr.expr_type Clocks.print_ck expr.expr_clock;*) |

109 |
match get_expr_alias defs expr with |

110 |
| Some eq -> |

111 |
let aliases = List.map (fun id -> List.find (fun v -> v.var_id = id) vars) eq.eq_lhs in |

112 |
(defs, vars), replace_expr aliases expr |

113 |
| None -> |

114 |
let new_aliases = |

115 |
List.map2 |

116 |
(mk_fresh_var node expr.expr_loc) |

117 |
(Types.type_list_of_type expr.expr_type) |

118 |
(Clocks.clock_list_of_clock expr.expr_clock) in |

119 |
let new_def = |

120 |
mkeq expr.expr_loc (List.map (fun v -> v.var_id) new_aliases, expr) |

121 |
in (new_def::defs, new_aliases@vars), replace_expr new_aliases expr |

122 | |

123 |
(* Create an alias for [expr], if [expr] is not already an alias (i.e. an ident) |

124 |
and [opt] is true *) |

125 |
let mk_expr_alias_opt opt node (defs, vars) expr = |

126 |
(*Format.eprintf "mk_expr_alias_opt %B %a %a %a@." opt Printers.pp_expr expr Types.print_ty expr.expr_type Clocks.print_ck expr.expr_clock;*) |

127 |
match expr.expr_desc with |

128 |
| Expr_ident alias -> |

129 |
(defs, vars), expr |

130 |
| _ -> |

131 |
match get_expr_alias defs expr with |

132 |
| Some eq -> |

133 |
let aliases = List.map (fun id -> List.find (fun v -> v.var_id = id) vars) eq.eq_lhs in |

134 |
(defs, vars), replace_expr aliases expr |

135 |
| None -> |

136 |
if opt |

137 |
then |

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 |
else |

147 |
(defs, vars), expr |

148 | |

149 |
(* Create a (normalized) expression from [ref_e], |

150 |
replacing description with [norm_d], |

151 |
taking propagated [offsets] into account |

152 |
in order to change expression type *) |

153 |
let mk_norm_expr offsets ref_e norm_d = |

154 |
(*Format.eprintf "mk_norm_expr %a %a @." Printers.pp_expr ref_e Printers.pp_expr { ref_e with expr_desc = norm_d};*) |

155 |
let drop_array_type ty = |

156 |
Types.map_tuple_type Types.array_element_type ty in |

157 |
{ ref_e with |

158 |
expr_desc = norm_d; |

159 |
expr_type = Utils.repeat (List.length offsets) drop_array_type ref_e.expr_type } |

160 | |

161 |
(* normalize_<foo> : defs * used vars -> <foo> -> (updated defs * updated vars) * normalized <foo> *) |

162 |
let rec normalize_list alias node offsets norm_element defvars elist = |

163 |
List.fold_right |

164 |
(fun t (defvars, qlist) -> |

165 |
let defvars, norm_t = norm_element alias node offsets defvars t in |

166 |
(defvars, norm_t :: qlist) |

167 |
) elist (defvars, []) |

168 | |

169 |
let rec normalize_expr ?(alias=true) node offsets defvars expr = |

170 |
(*Format.eprintf "normalize %B %a:%a [%a]@." alias Printers.pp_expr expr Types.print_ty expr.expr_type (Utils.fprintf_list ~sep:"," Dimension.pp_dimension) offsets;*) |

171 |
match expr.expr_desc with |

172 |
| Expr_const _ |

173 |
| Expr_ident _ -> defvars, unfold_offsets expr offsets |

174 |
| Expr_array elist -> |

175 |
let defvars, norm_elist = normalize_list alias node offsets (fun _ -> normalize_array_expr ~alias:true) defvars elist in |

176 |
let norm_expr = mk_norm_expr offsets expr (Expr_array norm_elist) in |

177 |
mk_expr_alias_opt alias node defvars norm_expr |

178 |
| Expr_power (e1, d) when offsets = [] -> |

179 |
let defvars, norm_e1 = normalize_expr node offsets defvars e1 in |

180 |
let norm_expr = mk_norm_expr offsets expr (Expr_power (norm_e1, d)) in |

181 |
mk_expr_alias_opt alias node defvars norm_expr |

182 |
| Expr_power (e1, d) -> |

183 |
normalize_expr ~alias:alias node (List.tl offsets) defvars e1 |

184 |
| Expr_access (e1, d) -> |

185 |
normalize_expr ~alias:alias node (d::offsets) defvars e1 |

186 |
| Expr_tuple elist -> |

187 |
let defvars, norm_elist = |

188 |
normalize_list alias node offsets (fun alias -> normalize_expr ~alias:alias) defvars elist in |

189 |
defvars, mk_norm_expr offsets expr (Expr_tuple norm_elist) |

190 |
| Expr_appl (id, args, None) |

191 |
when Basic_library.is_homomorphic_fun id |

192 |
&& Types.is_array_type expr.expr_type -> |

193 |
let defvars, norm_args = |

194 |
normalize_list |

195 |
alias |

196 |
node |

197 |
offsets |

198 |
(fun _ -> normalize_array_expr ~alias:true) |

199 |
defvars |

200 |
(expr_list_of_expr args) |

201 |
in |

202 |
defvars, mk_norm_expr offsets expr (Expr_appl (id, expr_of_expr_list args.expr_loc norm_args, None)) |

203 |
| Expr_appl (id, args, None) when Basic_library.is_expr_internal_fun expr -> |

204 |
let defvars, norm_args = normalize_expr ~alias:true node offsets defvars args in |

205 |
defvars, mk_norm_expr offsets expr (Expr_appl (id, norm_args, None)) |

206 |
| Expr_appl (id, args, r) -> |

207 |
let defvars, norm_args = normalize_expr node [] defvars args in |

208 |
let norm_expr = mk_norm_expr [] expr (Expr_appl (id, norm_args, r)) in |

209 |
if offsets <> [] |

210 |
then |

211 |
let defvars, norm_expr = normalize_expr node [] defvars norm_expr in |

212 |
normalize_expr ~alias:alias node offsets defvars norm_expr |

213 |
else |

214 |
mk_expr_alias_opt (alias && not (Basic_library.is_expr_internal_fun expr)) node defvars norm_expr |

215 |
| 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 *) |

216 |
normalize_expr ~alias:alias node offsets defvars (unfold_arrow expr) |

217 |
| Expr_arrow (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_arrow (norm_e1, norm_e2)) in |

221 |
mk_expr_alias_opt alias node defvars norm_expr |

222 |
| Expr_pre e -> |

223 |
let defvars, norm_e = normalize_expr node offsets defvars e in |

224 |
let norm_expr = mk_norm_expr offsets expr (Expr_pre norm_e) in |

225 |
mk_expr_alias_opt alias node defvars norm_expr |

226 |
| Expr_fby (e1, e2) -> |

227 |
let defvars, norm_e1 = normalize_expr node offsets defvars e1 in |

228 |
let defvars, norm_e2 = normalize_expr node offsets defvars e2 in |

229 |
let norm_expr = mk_norm_expr offsets expr (Expr_fby (norm_e1, norm_e2)) in |

230 |
mk_expr_alias_opt alias node defvars norm_expr |

231 |
| Expr_when (e, c, l) -> |

232 |
let defvars, norm_e = normalize_expr node offsets defvars e in |

233 |
defvars, mk_norm_expr offsets expr (Expr_when (norm_e, c, l)) |

234 |
| Expr_ite (c, t, e) -> |

235 |
let defvars, norm_c = normalize_guard node defvars c in |

236 |
let defvars, norm_t = normalize_cond_expr node offsets defvars t in |

237 |
let defvars, norm_e = normalize_cond_expr node offsets defvars e in |

238 |
let norm_expr = mk_norm_expr offsets expr (Expr_ite (norm_c, norm_t, norm_e)) in |

239 |
mk_expr_alias_opt alias node defvars norm_expr |

240 |
| Expr_merge (c, hl) -> |

241 |
let defvars, norm_hl = normalize_branches node offsets defvars hl in |

242 |
let norm_expr = mk_norm_expr offsets expr (Expr_merge (c, norm_hl)) in |

243 |
mk_expr_alias_opt alias node defvars norm_expr |

244 | |

245 |
(* Creates a conditional with a merge construct, which is more lazy *) |

246 |
(* |

247 |
let norm_conditional_as_merge alias node norm_expr offsets defvars expr = |

248 |
match expr.expr_desc with |

249 |
| Expr_ite (c, t, e) -> |

250 |
let defvars, norm_t = norm_expr (alias node offsets defvars t in |

251 |
| _ -> assert false |

252 |
*) |

253 |
and normalize_branches node offsets defvars hl = |

254 |
List.fold_right |

255 |
(fun (t, h) (defvars, norm_q) -> |

256 |
let (defvars, norm_h) = normalize_cond_expr node offsets defvars h in |

257 |
defvars, (t, norm_h) :: norm_q |

258 |
) |

259 |
hl (defvars, []) |

260 | |

261 |
and normalize_array_expr ?(alias=true) node offsets defvars expr = |

262 |
(*Format.eprintf "normalize_array %B %a [%a]@." alias Printers.pp_expr expr (Utils.fprintf_list ~sep:"," Dimension.pp_dimension) offsets;*) |

263 |
match expr.expr_desc with |

264 |
| Expr_power (e1, d) when offsets = [] -> |

265 |
let defvars, norm_e1 = normalize_expr node offsets defvars e1 in |

266 |
defvars, mk_norm_expr offsets expr (Expr_power (norm_e1, d)) |

267 |
| Expr_power (e1, d) -> |

268 |
normalize_array_expr ~alias:alias node (List.tl offsets) defvars e1 |

269 |
| Expr_access (e1, d) -> normalize_array_expr ~alias:alias node (d::offsets) defvars e1 |

270 |
| Expr_array elist when offsets = [] -> |

271 |
let defvars, norm_elist = normalize_list alias node offsets (fun _ -> normalize_array_expr ~alias:true) defvars elist in |

272 |
defvars, mk_norm_expr offsets expr (Expr_array norm_elist) |

273 |
| Expr_appl (id, args, None) when Basic_library.is_expr_internal_fun expr -> |

274 |
let defvars, norm_args = normalize_list alias node offsets (fun _ -> normalize_array_expr ~alias:true) defvars (expr_list_of_expr args) in |

275 |
defvars, mk_norm_expr offsets expr (Expr_appl (id, expr_of_expr_list args.expr_loc norm_args, None)) |

276 |
| _ -> normalize_expr ~alias:alias node offsets defvars expr |

277 | |

278 |
and normalize_cond_expr ?(alias=true) node offsets defvars expr = |

279 |
(*Format.eprintf "normalize_cond %B %a [%a]@." alias Printers.pp_expr expr (Utils.fprintf_list ~sep:"," Dimension.pp_dimension) offsets;*) |

280 |
match expr.expr_desc with |

281 |
| Expr_access (e1, d) -> |

282 |
normalize_cond_expr ~alias:alias node (d::offsets) defvars e1 |

283 |
| Expr_ite (c, t, e) -> |

284 |
let defvars, norm_c = normalize_guard node defvars c in |

285 |
let defvars, norm_t = normalize_cond_expr node offsets defvars t in |

286 |
let defvars, norm_e = normalize_cond_expr node offsets defvars e in |

287 |
defvars, mk_norm_expr offsets expr (Expr_ite (norm_c, norm_t, norm_e)) |

288 |
| Expr_merge (c, hl) -> |

289 |
let defvars, norm_hl = normalize_branches node offsets defvars hl in |

290 |
defvars, mk_norm_expr offsets expr (Expr_merge (c, norm_hl)) |

291 |
| _ -> normalize_expr ~alias:alias node offsets defvars expr |

292 | |

293 |
and normalize_guard node defvars expr = |

294 |
let defvars, norm_expr = normalize_expr node [] defvars expr in |

295 |
mk_expr_alias_opt true node defvars norm_expr |

296 | |

297 |
(* outputs cannot be memories as well. If so, introduce new local variable. |

298 |
*) |

299 |
let decouple_outputs node defvars eq = |

300 |
let rec fold_lhs defvars lhs tys cks = |

301 |
match lhs, tys, cks with |

302 |
| [], [], [] -> defvars, [] |

303 |
| v::qv, t::qt, c::qc -> let (defs_q, vars_q), lhs_q = fold_lhs defvars qv qt qc in |

304 |
if List.exists (fun o -> o.var_id = v) node.node_outputs |

305 |
then |

306 |
let newvar = mk_fresh_var node eq.eq_loc t c in |

307 |
let neweq = mkeq eq.eq_loc ([v], expr_of_vdecl newvar) in |

308 |
(neweq :: defs_q, newvar :: vars_q), newvar.var_id :: lhs_q |

309 |
else |

310 |
(defs_q, vars_q), v::lhs_q |

311 |
| _ -> assert false in |

312 |
let defvars', lhs' = |

313 |
fold_lhs |

314 |
defvars |

315 |
eq.eq_lhs |

316 |
(Types.type_list_of_type eq.eq_rhs.expr_type) |

317 |
(Clocks.clock_list_of_clock eq.eq_rhs.expr_clock) in |

318 |
defvars', {eq with eq_lhs = lhs' } |

319 | |

320 |
let rec normalize_eq node defvars eq = |

321 |
(*Format.eprintf "normalize_eq %a@." Types.print_ty eq.eq_rhs.expr_type;*) |

322 |
match eq.eq_rhs.expr_desc with |

323 |
| Expr_pre _ |

324 |
| Expr_fby _ -> |

325 |
let (defvars', eq') = decouple_outputs node defvars eq in |

326 |
let (defs', vars'), norm_rhs = normalize_expr ~alias:false node [] defvars' eq'.eq_rhs in |

327 |
let norm_eq = { eq' with eq_rhs = norm_rhs } in |

328 |
(norm_eq::defs', vars') |

329 |
| Expr_array _ -> |

330 |
let (defs', vars'), norm_rhs = normalize_array_expr ~alias:false node [] defvars eq.eq_rhs in |

331 |
let norm_eq = { eq with eq_rhs = norm_rhs } in |

332 |
(norm_eq::defs', vars') |

333 |
| Expr_appl (id, _, None) when Basic_library.is_homomorphic_fun id && Types.is_array_type eq.eq_rhs.expr_type -> |

334 |
let (defs', vars'), norm_rhs = normalize_array_expr ~alias:false node [] defvars eq.eq_rhs in |

335 |
let norm_eq = { eq with eq_rhs = norm_rhs } in |

336 |
(norm_eq::defs', vars') |

337 |
| Expr_appl _ -> |

338 |
let (defs', vars'), norm_rhs = normalize_expr ~alias:false node [] defvars eq.eq_rhs in |

339 |
let norm_eq = { eq with eq_rhs = norm_rhs } in |

340 |
(norm_eq::defs', vars') |

341 |
| _ -> |

342 |
let (defs', vars'), norm_rhs = normalize_cond_expr ~alias:false node [] defvars eq.eq_rhs in |

343 |
let norm_eq = { eq with eq_rhs = norm_rhs } in |

344 |
norm_eq::defs', vars' |

345 | |

346 |
(** normalize_node node returns a normalized node, |

347 |
ie. |

348 |
- updated locals |

349 |
- new equations |

350 |
- |

351 |
*) |

352 |
let normalize_node node = |

353 |
cpt_fresh := 0; |

354 |
let inputs_outputs = node.node_inputs@node.node_outputs in |

355 |
let is_local v = |

356 |
List.for_all ((!=) v) inputs_outputs in |

357 |
let orig_vars = inputs_outputs@node.node_locals in |

358 |
let defs, vars = |

359 |
List.fold_left (normalize_eq node) ([], orig_vars) (get_node_eqs node) in |

360 |
(* Normalize the asserts *) |

361 |
let vars, assert_defs, asserts = |

362 |
List.fold_left ( |

363 |
fun (vars, def_accu, assert_accu) assert_ -> |

364 |
let assert_expr = assert_.assert_expr in |

365 |
let (defs, vars'), expr = |

366 |
normalize_expr |

367 |
~alias:false |

368 |
node |

369 |
[] (* empty offset for arrays *) |

370 |
([], vars) (* defvar only contains vars *) |

371 |
assert_expr |

372 |
in |

373 |
(*Format.eprintf "New assert vars: %a@.@?" (fprintf_list ~sep:", " Printers.pp_var) vars';*) |

374 |
vars', defs@def_accu, {assert_ with assert_expr = expr}::assert_accu |

375 |
) (vars, [], []) node.node_asserts in |

376 |
let new_locals = List.filter is_local vars in |

377 |
(*Format.eprintf "New locals: %a@.@?" (fprintf_list ~sep:", " Printers.pp_var) new_locals;*) |

378 | |

379 |
let new_annots = |

380 |
if !Options.horntraces then |

381 |
begin |

382 |
(* Compute traceability info: |

383 |
- gather newly bound variables |

384 |
- compute the associated expression without aliases |

385 |
*) |

386 |
let diff_vars = List.filter (fun v -> not (List.mem v node.node_locals) ) new_locals in |

387 |
let norm_traceability = { |

388 |
annots = List.map (fun v -> |

389 |
let eq = |

390 |
try |

391 |
List.find (fun eq -> eq.eq_lhs = [v.var_id]) (defs@assert_defs) |

392 |
with Not_found -> (Format.eprintf "var not found %s@." v.var_id; assert false) in |

393 |
let expr = substitute_expr diff_vars (defs@assert_defs) eq.eq_rhs in |

394 |
let pair = mkeexpr expr.expr_loc (mkexpr expr.expr_loc (Expr_tuple [expr_of_ident v.var_id expr.expr_loc; expr])) in |

395 |
(["traceability"], pair) |

396 |
) diff_vars; |

397 |
annot_loc = Location.dummy_loc |

398 |
} |

399 |
in |

400 |
norm_traceability::node.node_annot |

401 |
end |

402 |
else |

403 |
node.node_annot |

404 |
in |

405 | |

406 |
let node = |

407 |
{ node with |

408 |
node_locals = new_locals; |

409 |
node_stmts = List.map (fun eq -> Eq eq) (defs @ assert_defs); |

410 |
node_asserts = asserts; |

411 |
node_annot = new_annots; |

412 |
} |

413 |
in ((*Printers.pp_node Format.err_formatter node;*) node) |

414 | |

415 |
let normalize_decl decl = |

416 |
match decl.top_decl_desc with |

417 |
| Node nd -> |

418 |
let decl' = {decl with top_decl_desc = Node (normalize_node nd)} in |

419 |
Hashtbl.replace Corelang.node_table nd.node_id decl'; |

420 |
decl' |

421 |
| Open _ | ImportedNode _ | Const _ | TypeDef _ -> decl |

422 | |

423 |
let normalize_prog decls = |

424 |
List.map normalize_decl decls |

425 | |

426 |
(* Local Variables: *) |

427 |
(* compile-command:"make -C .." *) |

428 |
(* End: *) |