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

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

410

(* End: *)
