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) %a @." Printers.pp_expr e Types.print_ty e.expr_type Dimension.pp_dimension d;

99

let res = *)

100

{ e with

101

expr_tag = Utils.new_tag ();

102

expr_loc = d.Dimension.dim_loc;

103

expr_type = Types.array_element_type e.expr_type;

104

expr_desc = Expr_access (e, d) }

105

(*in (Format.eprintf "= %a @." Printers.pp_expr res; res) *)

106

in

107

List.fold_left add_offset e offsets

108


109

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

110

let mk_expr_alias node (defs, vars) expr =

111

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

112

match get_expr_alias defs expr with

113

 Some eq >

114

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

115

(defs, vars), replace_expr aliases expr

116

 None >

117

let new_aliases =

118

List.map2

119

(mk_fresh_var node expr.expr_loc)

120

(Types.type_list_of_type expr.expr_type)

121

(Clocks.clock_list_of_clock expr.expr_clock) in

122

let new_def =

123

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

124

in

125

(* 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; *)

126

(new_def::defs, new_aliases@vars), replace_expr new_aliases expr

127


128

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

129

and [opt] is true *)

130

let mk_expr_alias_opt opt node (defs, vars) expr =

131

(*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;*)

132

match expr.expr_desc with

133

 Expr_ident alias >

134

(defs, vars), expr

135

 _ >

136

match get_expr_alias defs expr with

137

 Some eq >

138

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

139

(defs, vars), replace_expr aliases expr

140

 None >

141

if opt

142

then

143

let new_aliases =

144

List.map2

145

(mk_fresh_var node expr.expr_loc)

146

(Types.type_list_of_type expr.expr_type)

147

(Clocks.clock_list_of_clock expr.expr_clock) in

148

let new_def =

149

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

150

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

151

else

152

(defs, vars), expr

153


154

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

155

replacing description with [norm_d],

156

taking propagated [offsets] into account

157

in order to change expression type *)

158

let mk_norm_expr offsets ref_e norm_d =

159

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

160

let drop_array_type ty =

161

Types.map_tuple_type Types.array_element_type ty in

162

{ ref_e with

163

expr_desc = norm_d;

164

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

165


166

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

167

let rec normalize_list alias node offsets norm_element defvars elist =

168

List.fold_right

169

(fun t (defvars, qlist) >

170

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

171

(defvars, norm_t :: qlist)

172

) elist (defvars, [])

173


174

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

175

(*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;*)

176

match expr.expr_desc with

177

 Expr_const _

178

 Expr_ident _ > defvars, unfold_offsets expr offsets

179

 Expr_array elist >

180

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

181

let norm_expr = mk_norm_expr offsets expr (Expr_array norm_elist) in

182

mk_expr_alias_opt alias node defvars norm_expr

183

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

184

let defvars, norm_e1 = normalize_expr node offsets defvars e1 in

185

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

186

mk_expr_alias_opt alias node defvars norm_expr

187

 Expr_power (e1, d) >

188

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

189

 Expr_access (e1, d) >

190

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

191

 Expr_tuple elist >

192

let defvars, norm_elist =

193

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

194

defvars, mk_norm_expr offsets expr (Expr_tuple norm_elist)

195

 Expr_appl (id, args, None)

196

when Basic_library.is_homomorphic_fun id

197

&& Types.is_array_type expr.expr_type >

198

let defvars, norm_args =

199

normalize_list

200

alias

201

node

202

offsets

203

(fun _ > normalize_array_expr ~alias:true)

204

defvars

205

(expr_list_of_expr args)

206

in

207

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

208

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

209

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

210

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

211

 Expr_appl (id, args, r) >

212

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

213

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

214

if offsets <> []

215

then

216

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

217

normalize_expr ~alias:alias node offsets defvars norm_expr

218

else

219

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

220

 Expr_arrow (e1,e2) when !unfold_arrow_active && not (is_expr_once expr) >

221

(* Here we differ from Colaco paper: arrows are pushed to the top *)

222

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

223

 Expr_arrow (e1,e2) >

224

let defvars, norm_e1 = normalize_expr node offsets defvars e1 in

225

let defvars, norm_e2 = normalize_expr node offsets defvars e2 in

226

let norm_expr = mk_norm_expr offsets expr (Expr_arrow (norm_e1, norm_e2)) in

227

mk_expr_alias_opt alias node defvars norm_expr

228

 Expr_pre e >

229

let defvars, norm_e = normalize_expr node offsets defvars e in

230

let norm_expr = mk_norm_expr offsets expr (Expr_pre norm_e) in

231

mk_expr_alias_opt alias node defvars norm_expr

232

 Expr_fby (e1, e2) >

233

let defvars, norm_e1 = normalize_expr node offsets defvars e1 in

234

let defvars, norm_e2 = normalize_expr node offsets defvars e2 in

235

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

236

mk_expr_alias_opt alias node defvars norm_expr

237

 Expr_when (e, c, l) >

238

let defvars, norm_e = normalize_expr node offsets defvars e in

239

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

240

 Expr_ite (c, t, e) >

241

let defvars, norm_c = normalize_guard node defvars c in

242

let defvars, norm_t = normalize_cond_expr node offsets defvars t in

243

let defvars, norm_e = normalize_cond_expr node offsets defvars e in

244

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

245

mk_expr_alias_opt alias node defvars norm_expr

246

 Expr_merge (c, hl) >

247

let defvars, norm_hl = normalize_branches node offsets defvars hl in

248

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

249

mk_expr_alias_opt alias node defvars norm_expr

250


251

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

252

(*

253

let norm_conditional_as_merge alias node norm_expr offsets defvars expr =

254

match expr.expr_desc with

255

 Expr_ite (c, t, e) >

256

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

257

 _ > assert false

258

*)

259

and normalize_branches node offsets defvars hl =

260

List.fold_right

261

(fun (t, h) (defvars, norm_q) >

262

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

263

defvars, (t, norm_h) :: norm_q

264

)

265

hl (defvars, [])

266


267

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

268

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

269

match expr.expr_desc with

270

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

271

let defvars, norm_e1 = normalize_expr node offsets defvars e1 in

272

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

273

 Expr_power (e1, d) >

274

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

275

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

276

 Expr_array elist when offsets = [] >

277

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

278

defvars, mk_norm_expr offsets expr (Expr_array norm_elist)

279

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

280

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

281

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

282

 _ > normalize_expr ~alias:alias node offsets defvars expr

283


284

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

285

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

286

match expr.expr_desc with

287

 Expr_access (e1, d) >

288

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

289

 Expr_ite (c, t, e) >

290

let defvars, norm_c = normalize_guard node defvars c in

291

let defvars, norm_t = normalize_cond_expr node offsets defvars t in

292

let defvars, norm_e = normalize_cond_expr node offsets defvars e in

293

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

294

 Expr_merge (c, hl) >

295

let defvars, norm_hl = normalize_branches node offsets defvars hl in

296

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

297

 _ > normalize_expr ~alias:alias node offsets defvars expr

298


299

and normalize_guard node defvars expr =

300

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

301

mk_expr_alias_opt true node defvars norm_expr

302


303

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

304

*)

305

let decouple_outputs node defvars eq =

306

let rec fold_lhs defvars lhs tys cks =

307

match lhs, tys, cks with

308

 [], [], [] > defvars, []

309

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

310

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

311

then

312

let newvar = mk_fresh_var node eq.eq_loc t c in

313

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

314

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

315

else

316

(defs_q, vars_q), v::lhs_q

317

 _ > assert false in

318

let defvars', lhs' =

319

fold_lhs

320

defvars

321

eq.eq_lhs

322

(Types.type_list_of_type eq.eq_rhs.expr_type)

323

(Clocks.clock_list_of_clock eq.eq_rhs.expr_clock) in

324

defvars', {eq with eq_lhs = lhs' }

325


326

let rec normalize_eq node defvars eq =

327

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

328

match eq.eq_rhs.expr_desc with

329

 Expr_pre _

330

 Expr_fby _ >

331

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

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

 Expr_array _ >

336

let (defs', vars'), norm_rhs = normalize_array_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

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

340

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

341

let norm_eq = { eq with eq_rhs = norm_rhs } in

342

(norm_eq::defs', vars')

343

 Expr_appl _ >

344

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

345

let norm_eq = { eq with eq_rhs = norm_rhs } in

346

(norm_eq::defs', vars')

347

 _ >

348

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

349

let norm_eq = { eq with eq_rhs = norm_rhs } in

350

norm_eq::defs', vars'

351


352

(** normalize_node node returns a normalized node,

353

ie.

354

 updated locals

355

 new equations

356



357

*)

358

let normalize_node node =

359

cpt_fresh := 0;

360

let inputs_outputs = node.node_inputs@node.node_outputs in

361

let is_local v =

362

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

363

let orig_vars = inputs_outputs@node.node_locals in

364

let defs, vars =

365

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

366

(* Normalize the asserts *)

367

let vars, assert_defs, asserts =

368

List.fold_left (

369

fun (vars, def_accu, assert_accu) assert_ >

370

let assert_expr = assert_.assert_expr in

371

let (defs, vars'), expr =

372

normalize_expr

373

~alias:false

374

node

375

[] (* empty offset for arrays *)

376

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

377

assert_expr

378

in

379

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

380

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

381

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

382

let new_locals = List.filter is_local vars in

383

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

384


385

let new_annots =

386

if !Options.traces then

387

begin

388

(* Compute traceability info:

389

 gather newly bound variables

390

 compute the associated expression without aliases

391

*)

392

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

393

let norm_traceability = {

394

annots = List.map (fun v >

395

let eq =

396

try

397

List.find (fun eq > List.exists (fun v' > v' = v.var_id ) eq.eq_lhs) (defs@assert_defs)

398

with Not_found >

399

(

400

Format.eprintf "Traceability annotation generation: var %s not found@." v.var_id;

401

assert false

402

)

403

in

404

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

405

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

406

(["traceability"], pair)

407

) diff_vars;

408

annot_loc = Location.dummy_loc

409

}

410

in

411

norm_traceability::node.node_annot

412

end

413

else

414

node.node_annot

415

in

416


417

let node =

418

{ node with

419

node_locals = new_locals;

420

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

421

node_asserts = asserts;

422

node_annot = new_annots;

423

}

424

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

425

node

426

)

427


428


429

let normalize_decl decl =

430

match decl.top_decl_desc with

431

 Node nd >

432

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

433

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

434

decl'

435

 Open _  ImportedNode _  Const _  TypeDef _ > decl

436


437

let normalize_prog decls =

438

List.map normalize_decl decls

439


440

(* Local Variables: *)

441

(* compilecommand:"make C .." *)

442

(* End: *)
