1

(* 

2

* SchedMCore  A MultiCore Scheduling Framework

3

* Copyright (C) 20092013, ONERA, Toulouse, FRANCE  LIFL, Lille, FRANCE

4

* Copyright (C) 20122013, 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 021111307

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 = expr.expr_clock in

69

{ expr with expr_desc = Expr_ite (expr_once loc ck, e1, e2) }

70

 _ > assert false

71


72

let cpt_fresh = ref 0

73


74

(* Generate a new local [node] variable *)

75

let mk_fresh_var node loc ty ck =

76

let vars = node_vars node in

77

let rec aux () =

78

incr cpt_fresh;

79

let s = Printf.sprintf "__%s_%d" node.node_id !cpt_fresh in

80

if List.exists (fun v > v.var_id = s) vars then aux () else

81

{

82

var_id = s;

83

var_dec_type = dummy_type_dec;

84

var_dec_clock = dummy_clock_dec;

85

var_dec_const = false;

86

var_type = ty;

87

var_clock = ck;

88

var_loc = loc

89

}

90

in aux ()

91


92

(* Generate a new ident expression from a declared variable *)

93

let mk_ident_expr v =

94

{ expr_tag = new_tag ();

95

expr_desc = Expr_ident v.var_id;

96

expr_type = v.var_type;

97

expr_clock = v.var_clock;

98

expr_delay = Delay.new_var ();

99

expr_annot = None;

100

expr_loc = v.var_loc }

101


102

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

103

let get_expr_alias defs expr =

104

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

105

with

106

Not_found > None

107


108

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

109

let replace_expr locals expr =

110

match locals with

111

 [] > assert false

112

 [v] > { expr with

113

expr_tag = Utils.new_tag ();

114

expr_desc = Expr_ident v.var_id }

115

 _ > { expr with

116

expr_tag = Utils.new_tag ();

117

expr_desc = Expr_tuple (List.map mk_ident_expr locals) }

118


119

let unfold_offsets e offsets =

120

let add_offset e d =

121

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

122

{ e with

123

expr_tag = Utils.new_tag ();

124

expr_loc = d.Dimension.dim_loc;

125

expr_type = Types.array_element_type e.expr_type;

126

expr_desc = Expr_access (e, d) } in

127

List.fold_left add_offset e offsets

128


129

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

130

let mk_expr_alias node (defs, vars) expr =

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

let new_aliases =

137

List.map2

138

(mk_fresh_var node expr.expr_loc)

139

(Types.type_list_of_type expr.expr_type)

140

(Clocks.clock_list_of_clock expr.expr_clock) in

141

let new_def =

142

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

143

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

144


145

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

146

and [opt] is true *)

147

let mk_expr_alias_opt opt node defvars expr =

148

match expr.expr_desc with

149

 Expr_ident alias >

150

defvars, expr

151

 _ >

152

if opt

153

then

154

mk_expr_alias node defvars expr

155

else

156

defvars, expr

157


158

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

159

replacing description with [norm_d],

160

taking propagated [offsets] into account

161

in order to change expression type *)

162

let mk_norm_expr offsets ref_e norm_d =

163

let drop_array_type ty =

164

Types.map_tuple_type Types.array_element_type ty in

165

{ ref_e with

166

expr_desc = norm_d;

167

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

168


169

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

170

let rec normalize_list alias node offsets norm_element defvars elist =

171

List.fold_right

172

(fun t (defvars, qlist) >

173

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

174

(defvars, norm_t :: qlist)

175

) elist (defvars, [])

176


177

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

178

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

179

match expr.expr_desc with

180

 Expr_const _

181

 Expr_ident _ > defvars, unfold_offsets expr offsets

182

 Expr_array elist >

183

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

184

let norm_expr = mk_norm_expr offsets expr (Expr_array norm_elist) in

185

mk_expr_alias_opt alias node defvars norm_expr

186

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

187

let defvars, norm_e1 = normalize_expr node offsets defvars e1 in

188

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

189

mk_expr_alias_opt alias node defvars norm_expr

190

 Expr_power (e1, d) >

191

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

192

 Expr_access (e1, d) >

193

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

194

 Expr_tuple elist >

195

let defvars, norm_elist =

196

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

197

defvars, mk_norm_expr offsets expr (Expr_tuple norm_elist)

198

 Expr_appl (id, args, None) when Basic_library.is_internal_fun id && Types.is_array_type expr.expr_type >

199

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

200

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

201

 Expr_appl (id, args, None) when Basic_library.is_internal_fun id >

202

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

203

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

204

 Expr_appl (id, args, r) >

205

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

206

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

207

if offsets <> []

208

then

209

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

210

normalize_expr ~alias:alias node offsets defvars norm_expr

211

else

212

mk_expr_alias_opt (alias && not (Basic_library.is_internal_fun id)) node defvars norm_expr

213

 Expr_arrow (e1,e2) when not (is_expr_once expr) > (* Here we differ from Colaco paper: arrows are pushed to the top *)

214

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

215

 Expr_arrow (e1,e2) >

216

let defvars, norm_e1 = normalize_expr node offsets defvars e1 in

217

let defvars, norm_e2 = normalize_expr node offsets defvars e2 in

218

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

219

mk_expr_alias_opt alias node defvars norm_expr

220

 Expr_pre e >

221

let defvars, norm_e = normalize_expr node offsets defvars e in

222

let norm_expr = mk_norm_expr offsets expr (Expr_pre norm_e) in

223

mk_expr_alias_opt alias node defvars norm_expr

224

 Expr_fby (e1, e2) >

225

let defvars, norm_e1 = normalize_expr node offsets defvars e1 in

226

let defvars, norm_e2 = normalize_expr node offsets defvars e2 in

227

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

228

mk_expr_alias_opt alias node defvars norm_expr

229

 Expr_when (e, c, l) >

230

let defvars, norm_e = normalize_expr node offsets defvars e in

231

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

232

 Expr_ite (c, t, e) >

233

let defvars, norm_c = normalize_guard node defvars c in

234

let defvars, norm_t = normalize_cond_expr node offsets defvars t in

235

let defvars, norm_e = normalize_cond_expr node offsets defvars e in

236

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

237

mk_expr_alias_opt alias node defvars norm_expr

238

 Expr_merge (c, hl) >

239

let defvars, norm_hl = normalize_branches node offsets defvars hl in

240

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

241

mk_expr_alias_opt alias node defvars norm_expr

242

 Expr_uclock _

243

 Expr_dclock _

244

 Expr_phclock _ > assert false (* Not handled yet *)

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_internal_fun id >

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], mk_ident_expr 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

match eq.eq_rhs.expr_desc with

322

 Expr_pre _

323

 Expr_fby _ >

324

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

325

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

326

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

327

(norm_eq::defs', vars')

328

 Expr_array _ >

329

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

330

let norm_eq = { eq with eq_rhs = norm_rhs } in

331

(norm_eq::defs', vars')

332

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

333

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

334

let norm_eq = { eq with eq_rhs = norm_rhs } in

335

(norm_eq::defs', vars')

336

 Expr_appl _ >

337

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

338

let norm_eq = { eq with eq_rhs = norm_rhs } in

339

(norm_eq::defs', vars')

340

 _ >

341

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

342

let norm_eq = { eq with eq_rhs = norm_rhs } in

343

norm_eq::defs', vars'

344


345

let normalize_node node =

346

cpt_fresh := 0;

347

let inputs_outputs = node.node_inputs@node.node_outputs in

348

let is_local v =

349

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

350

let defs, vars =

351

List.fold_left (normalize_eq node) ([], inputs_outputs@node.node_locals) node.node_eqs in

352

let new_locals = List.filter is_local vars in

353

let node =

354

{ node with node_locals = new_locals; node_eqs = defs }

355

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

356


357

let normalize_decl decl =

358

match decl.top_decl_desc with

359

 Node nd >

360

{decl with top_decl_desc = Node (normalize_node nd)}

361

 Open _  ImportedNode _  Consts _ > decl

362


363

let normalize_prog decls =

364

List.map normalize_decl decls

365


366

(* Local Variables: *)

367

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

368

(* End: *)
