A set of benchmarks to compare a new prototype MiniZinc implementation
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2
3/*
4 * Main authors:
5 * Graeme Gange <graeme.gange@monash.edu>
6 */
7
8/* This Source Code Form is subject to the terms of the Mozilla Public
9 * License, v. 2.0. If a copy of the MPL was not distributed with this
10 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
11
12#ifndef __MINIZINC_CODEGEN_HH__
13#define __MINIZINC_CODEGEN_HH__
14
15// Simple single-pass bytecode compiler for MiniZinc.
16
17#include <minizinc/codegen_support.hh>
18#include <minizinc/flatten_internal.hh>
19#include <minizinc/interpreter.hh>
20
21#include <iostream>
22#include <set>
23#include <vector>
24
25namespace MiniZinc {
26
27struct CodeGen;
28
29// Location is either a register or global.
30class Loc {
31private:
32 Loc(int _x) : x(_x) {}
33
34public:
35 static Loc reg(int r) { return r << 1; }
36 static Loc global(int g) { return (g << 1) | 1; }
37
38 inline bool is_reg(void) const { return !(x & 1); }
39 inline bool is_global(void) const { return x & 1; }
40 inline int index(void) const { return x >> 1; }
41
42 int x;
43};
44
45// Code generators for structures.
46// Expressions can be executed in three modes:
47// - If Boolean, it is always just executed.
48// - If non-Boolean but total, it is similarly just executed.
49// - If non-Boolean and partial, we first evaluate its partiality
50// constraints in the enclosing Boolean expression, _then_
51// evaluate its numeric component.
52// For any function that is not total, we generate two procedures:
53// one which is
54// A slightly more structured representation for code generation.
55class CG_Value {
56public:
57 enum CG_ValueKind { V_Immi, V_Global, V_Reg, V_Proc, V_Label };
58
59protected:
60 CG_Value(CG_ValueKind _kind, int _value) : kind(_kind), value(_value) {}
61
62public:
63 CG_Value(void) : kind(V_Immi), value(0) {}
64 static CG_Value reg(int r) { return CG_Value(V_Reg, r); }
65 static CG_Value global(int r) { return CG_Value(V_Global, r); }
66 static CG_Value immi(long long int r) { return CG_Value(V_Immi, r); }
67 static CG_Value proc(int p) { return CG_Value(V_Proc, p); }
68 static CG_Value label(int l) { return CG_Value(V_Label, l); }
69
70 CG_ValueKind kind;
71 long long int value;
72};
73
74struct CG_Instr {
75protected:
76 CG_Instr(unsigned int _tag) : tag(_tag) {}
77
78public:
79 static CG_Instr instr(BytecodeStream::Instr i) { return static_cast<unsigned int>(i) << 1; }
80 static CG_Instr label(unsigned int l) { return (l << 1) + 1; }
81
82 unsigned int tag;
83 std::vector<CG_Value> params;
84};
85
86struct CG_ProcID {
87protected:
88 CG_ProcID(int _p) : p(_p) {}
89
90public:
91 static CG_ProcID builtin(int b) { return CG_ProcID((b << 1) | 1); }
92 static CG_ProcID proc(int p) { return CG_ProcID(p << 1); }
93 bool is_builtin(void) const { return p & 1; }
94 unsigned int id(void) const { return p >> 1; }
95
96 static CG_ProcID of_val(CG_Value v) {
97 assert(v.kind == CG_Value::V_Proc);
98 return CG_ProcID(v.value);
99 }
100
101 unsigned int p;
102};
103
104struct CG_Builder {
105 std::vector<CG_Instr> instrs;
106
107 void append(CG_Builder& o) {
108 instrs.insert(instrs.end(), o.instrs.begin(), o.instrs.end());
109 o.instrs.clear();
110 }
111 void clear(void) { instrs.clear(); }
112};
113
114// When we bind a non-Boolean expression, we also construct
115// a set of conditions we need to insert into any use-contexts.
116
117// We use CG_Cond to track the conditionality of values.
118struct CG_Cond {
119 // FIXME: Currently not GC'd, so this will leak a bunch of memory.
120 enum Kind { CC_Reg, CC_Call, CC_And };
121 class C_Reg;
122 class C_Call;
123 class C_And;
124
125 struct cond_reg {
126 cond_reg(void) : is_root(0), is_seen(0), is_par(0), reg(-1) {}
127 cond_reg(int _reg, bool _par) : is_root(0), is_seen(0), is_par(_par), reg(_reg) {}
128
129 int operator*(void) const {
130 assert(reg >= 0);
131 return reg;
132 }
133 bool has_reg(void) const { return reg >= 0; }
134
135 int is_root : 1;
136 int is_seen : 1;
137 int is_par : 1;
138 int reg : 29;
139 };
140
141 class _T {
142 public:
143 cond_reg reg[2];
144
145 _T(void) {}
146 _T(int r, bool is_par) {
147 reg[0].reg = r;
148 reg[0].is_par = is_par;
149 }
150
151 virtual Kind kind(void) const = 0;
152 };
153
154 class T {
155 T(uintptr_t _p) : p(_p) {}
156
157 public:
158 T(void) : p(0) {}
159
160 static T ttt(void) { return T(0); }
161 static T fff(void) { return T(1); }
162 static T of_ptr(_T* p) { return T(reinterpret_cast<uintptr_t>(p)); }
163
164 T operator~(void) const { return T(p ^ 1); }
165 T operator^(bool b) const { return T(p ^ b); }
166
167 bool sign(void) const { return p & 1; }
168 _T* get(void) const { return reinterpret_cast<_T*>(p & ~((uintptr_t)1)); }
169
170 uintptr_t p;
171 };
172
173 static T ttt(void) { return T::ttt(); }
174 static T fff(void) { return T::fff(); }
175
176 class C_Reg : public _T {
177 public:
178 static const Kind _kind = CC_Reg;
179 Kind kind(void) const { return _kind; }
180 C_Reg(int reg, bool is_par) : _T(reg, is_par) {}
181 };
182 class C_Call : public _T {
183 public:
184 static const Kind _kind = CC_Call;
185 Kind kind(void) const { return _kind; }
186
187 C_Call(ASTString _ident, BytecodeProc::Mode _m, bool _cse, const std::vector<Type>& _ty,
188 const std::vector<CG_Value>& _params)
189 : ident(_ident), m(std::move(_m)), ty(_ty), cse(_cse), params(_params) {}
190
191 ASTString ident;
192 // Return Types + argument types
193 BytecodeProc::Mode m;
194 bool cse;
195 std::vector<Type> ty;
196 std::vector<CG_Value> params;
197 };
198 class C_And : public _T {
199 public:
200 static const Kind _kind = CC_And;
201 Kind kind(void) const { return _kind; }
202
203 C_And(BytecodeProc::Mode _m, std::vector<T>& _children) : m(_m), children(_children) {
204 assert(children.size() > 1);
205 }
206
207 BytecodeProc::Mode m;
208 std::vector<T> children;
209 };
210
211 static T reg(int r, bool is_par) { return T::of_ptr(new C_Reg(r, is_par)); }
212
213 static T call(ASTString ident, BytecodeProc::Mode m, bool cse, const std::vector<Type>& ty,
214 const std::vector<CG_Value>& params) {
215 return _call(ident, m, cse, ty, params);
216 }
217
218 static T _call(ASTString ident, BytecodeProc::Mode m, bool cse, const std::vector<Type>& ty,
219 const std::vector<CG_Value>& params) {
220 return T::of_ptr(new C_Call(ident, m, cse, ty, params));
221 }
222
223 template <typename... Args>
224 static T _forall(BytecodeProc::Mode m, std::vector<T>& args, T next, Args... rest) {
225 args.push_back(next);
226 return _forall(m, args, rest...);
227 }
228 template <class It>
229 static void clear_seen(It b, It e) {
230 for (; b != e; ++b) {
231 if (!b->get()) continue;
232 b->get()->reg[b->sign()].is_seen = false;
233 }
234 }
235 static T _forall(BytecodeProc::Mode m, std::vector<T>& args) {
236 size_t count = 0;
237 for (T x : args) {
238 _T* p(x.get());
239 if (!p) {
240 // Either true or false.
241 if (x.sign()) {
242 clear_seen(args.begin(), args.end());
243 return T::fff();
244 }
245 continue;
246 }
247 // Otherwise, check if we've already seen this or its negation.
248 if (p->reg[1 - x.sign()].is_seen || p->reg[1 - x.sign()].is_root) {
249 clear_seen(args.begin(), args.end());
250 return T::fff();
251 }
252 if (p->reg[x.sign()].is_seen || p->reg[x.sign()].is_root) continue;
253 // Haven't seen this yet, so save and mark it.
254 p->reg[x.sign()].is_seen = true;
255 args[count] = x;
256 count++;
257 }
258 clear_seen(args.begin(), args.end());
259 args.resize(count);
260 if (count == 0) {
261 return T::ttt();
262 }
263 if (count == 1) {
264 return args[0];
265 }
266 return T::of_ptr(new C_And(m, args));
267 }
268
269 template <typename... Args>
270 static T forall(BytecodeProc::Mode m, Args... args) {
271 std::vector<CG_Cond::T> vec;
272 return _forall(m, vec, args...);
273 }
274 static T forall(BytecodeProc::Mode m, std::vector<T>& args) { return _forall(m, args); }
275
276 template <typename... Args>
277 static T _exists(BytecodeProc::Mode m, std::vector<T>& args, T next, Args... rest) {
278 args.push_back(next);
279 return _exists(m, args, rest...);
280 }
281 static T _exists(BytecodeProc::Mode m, std::vector<T>& args);
282
283 template <typename... Args>
284 static T exists(BytecodeProc::Mode m, Args... args) {
285 std::vector<T> vec;
286 return _exists(m, vec, args...);
287 }
288 static T exists(BytecodeProc::Mode m, std::vector<T>& args) { return _exists(m, args); }
289};
290
291// An environment should never outlive its parent.
292template <class T>
293class CG_Env {
294private:
295 CG_Env(CG_Env<T>* _p) : p(_p), sz(p ? p->sz : 0) {}
296
297 // Forbid copy and assignment operators.
298 CG_Env(const CG_Env& _o) = delete;
299 CG_Env& operator=(const CG_Env& o) = delete;
300
301public:
302 CG_Env(void) : p(nullptr), sz(0) {}
303 CG_Env(CG_Env&& o)
304 : bindings(std::move(o.bindings)),
305 available(std::move(o.available)),
306 available_csts(std::move(o.available_csts)),
307 available_ranges(std::move(o.available_ranges)),
308 cached_conds(std::move(o.cached_conds)),
309 occurs(std::move(o.occurs)),
310 p(o.p),
311 sz(o.sz) {}
312
313 void clear_cached_conds() {
314 for (CG_Cond::T c : cached_conds) {
315 CG_Cond::_T* p(c.get());
316 bool sign(c.sign());
317 p->reg[sign].reg = -1;
318 }
319 cached_conds.clear();
320 }
321 void record_cached_cond(CG_Cond::T c) { cached_conds.push_back(c); }
322
323 class NotFound : public std::exception {
324 public:
325 NotFound(void) {}
326 };
327
328 T lookup(const ASTString& s) const {
329 auto it(bindings.find(s));
330 if (it != bindings.end()) return (*it).second;
331 if (!p) throw NotFound();
332
333 return p->lookup(s);
334 }
335
336 void bind(const ASTString& s, T val) {
337 auto it(bindings.find(s));
338 if (it != bindings.end())
339 bindings.erase(it);
340 else
341 sz++;
342 bindings.insert(std::make_pair(s, val));
343
344 // Invalidate any cached values mentioning s.
345 auto o_it(occurs.find(s));
346 if (o_it != occurs.end()) {
347 // We're lazy here, in that we don't remove e from
348 // other occurs lists.
349 for (Expression* e : (*o_it).second) available.erase(e);
350 occurs.erase(o_it);
351 }
352 }
353
354 // Check whether e is already available in an enclosing environment.
355 T cache_lookup(Expression* e, ASTStSet e_scope) {
356 auto it(available.find(e));
357 // Anything in the current table is hasn't been invalidated.
358 if (it != available.end()) {
359 return (*it).second;
360 }
361 if (!p) throw NotFound();
362
363 // If there's a parent table, check whether we've re-bound
364 // something in its scope.
365 for (auto p : bindings) {
366 if (e_scope.find(p.first) != e_scope.end()) throw NotFound();
367 }
368 // If the scope hasn't been invalidated, check the parent.
369 return p->cache_lookup(e, e_scope);
370 }
371
372 void cache_store(Expression* e, ASTStSet e_scope, T val) {
373 available.insert(std::make_pair(e, val));
374 // Add e to the occurs lists for variables in its scope.
375 for (ASTString s : e_scope) occurs[s].push_back(e);
376 }
377
378 bool cache_lookup_cst(int x, T& ret) {
379 auto it(available_csts.find(x));
380 // Anything in the current table is hasn't been invalidated.
381 if (it != available_csts.end()) {
382 ret = (*it).second;
383 return true;
384 }
385 if (!p) return false;
386 return p->cache_lookup_cst(x, ret);
387 }
388 void cache_store_cst(int x, T val) { available_csts.insert(std::make_pair(x, val)); }
389
390 static uint64_t range_key(int l, int u) { return (((uint64_t)u) << 32ull | (uint64_t)l); }
391 bool cache_lookup_range(int l, int u, T& ret) {
392 auto it(available_ranges.find(range_key(l, u)));
393 // Anything in the current table is hasn't been invalidated.
394 if (it != available_ranges.end()) {
395 ret = (*it).second;
396 return true;
397 }
398 if (!p) return false;
399 return p->cache_lookup_range(l, u, ret);
400 }
401 void cache_store_range(int l, int u, T val) {
402 available_ranges.insert(std::make_pair(range_key(l, u), val));
403 }
404
405 static CG_Env* spawn(CG_Env* p) { return new CG_Env<T>(p); }
406
407 unsigned int size(void) const { return sz; }
408
409 typename ASTStringMap<T>::t bindings;
410
411 typename ExprMap<T>::t available;
412 std::unordered_map<int, T> available_csts;
413 std::unordered_map<uint64_t, T> available_ranges;
414 // std::unordered_map<std::pair<int, int>, T> available_ranges;
415 typename ASTStringMap<std::vector<Expression*>>::t occurs;
416
417 std::vector<CG_Cond::T> cached_conds;
418
419 // Parent environment.
420 CG_Env<T>* p;
421 unsigned int sz;
422};
423
424struct CG {
425 typedef std::pair<int, CG_Cond::T> Binding;
426
427 // This is currently (probably) sound, but unnecessarily weak. If an expression ever appears in
428 // root context, the root appearance should dominate.
429 struct Mode {
430 enum Strength { Root = 0, Imp = 1, Fun = 2 };
431 Mode(BytecodeProc::Mode _m) : m(_m) {}
432 Mode(Strength s, bool is_neg) {
433 switch (s) {
434 case Root:
435 m = is_neg ? BytecodeProc::ROOT_NEG : BytecodeProc::ROOT;
436 break;
437 case Imp:
438 m = is_neg ? BytecodeProc::IMP_NEG : BytecodeProc::IMP;
439 break;
440 case Fun:
441 m = is_neg ? BytecodeProc::FUN_NEG : BytecodeProc::FUN;
442 break;
443 }
444 }
445
446 bool is_neg(void) const {
447 switch (m) {
448 case BytecodeProc::ROOT_NEG:
449 case BytecodeProc::IMP_NEG:
450 case BytecodeProc::FUN_NEG:
451 return true;
452 default:
453 return false;
454 }
455 }
456
457 Strength strength(void) const {
458 switch (m) {
459 case BytecodeProc::ROOT:
460 case BytecodeProc::ROOT_NEG:
461 return Root;
462 case BytecodeProc::IMP:
463 case BytecodeProc::IMP_NEG:
464 return Imp;
465 case BytecodeProc::FUN:
466 case BytecodeProc::FUN_NEG:
467 return Fun;
468 default:
469 throw InternalError("Unexpected mode.");
470 }
471 }
472 bool is_root(void) const { return strength() == Root; }
473
474 Mode join(Mode o) {
475 if (is_neg() != o.is_neg()) return BytecodeProc::FUN;
476 return Mode(std::max(strength(), o.strength()), is_neg());
477 }
478 bool is_submode(Mode o) { return is_neg() == o.is_neg() && strength() <= o.strength(); }
479
480 // Half
481 Mode operator+(void) const { return Mode(strength() == Root ? Imp : strength(), is_neg()); }
482 Mode operator-(void) const { return Mode(strength(), !is_neg()); }
483
484 // Switch the current mode to functional.
485 Mode operator*(void) const { return Mode(Fun, is_neg()); }
486
487 operator BytecodeProc::Mode() const { return m; }
488
489 BytecodeProc::Mode m;
490 };
491
492 inline static CG_Value g(int g) { return CG_Value::global(g); }
493 inline static CG_Value r(int r) { return CG_Value::reg(r); }
494 inline static CG_Value i(int i) { return CG_Value::immi(i); }
495 inline static CG_Value l(int l) { return CG_Value::label(l); }
496
497 // Place a non-Boolean value in a register, and collect its partiality.
498 static Binding bind(Expression* e, CodeGen& cg, CG_Builder& frag);
499 // Compile a Boolean expression into a condition.
500 static CG_Cond::T compile(Expression* e, CodeGen& cg, CG_Builder& frag);
501 // Reify a condion, putting it in a register.
502 static int force(CG_Cond::T cond, Mode ctx, CodeGen& cg, CG_Builder& frag);
503 // Force compiled expression or Bind value depending on type
504 static Binding force_or_bind(Expression* e, Mode ctx, CodeGen& cg, CG_Builder& frag);
505 static int force_or_bind(Expression* e, Mode ctx, std::vector<CG_Cond::T>& cond, CodeGen& cg,
506 CG_Builder& frag);
507
508 static void run(CodeGen& cg, Model* m);
509
510 static int locate_immi(int x, CodeGen& cg, CG_Builder& frag);
511
512 static int vec2array(std::vector<int> vec, CodeGen& cg, CG_Builder& frag);
513
514 static Binding bind(Id* x, Mode ctx, CodeGen& cg, CG_Builder& frag);
515 static Binding bind(SetLit* l, Mode ctx, CodeGen& cg, CG_Builder& frag);
516 static Binding bind(ArrayLit* a, Mode ctx, CodeGen& cg, CG_Builder& frag);
517 static Binding bind(ArrayAccess* a, Mode ctx, CodeGen& cg, CG_Builder& frag);
518 static Binding bind(ITE* ite, Mode ctx, CodeGen& cg, CG_Builder& frag);
519 static Binding bind(BinOp* op, Mode ctx, CodeGen& cg, CG_Builder& frag);
520 static Binding bind(UnOp* op, Mode ctx, CodeGen& cg, CG_Builder& frag);
521 static Binding bind(Call* call, Mode ctx, CodeGen& cg, CG_Builder& frag);
522 static Binding bind(Let* let, Mode ctx, CodeGen& cg, CG_Builder& frag);
523 static Binding bind(Comprehension* let, Mode ctx, CodeGen& cg, CG_Builder& frag);
524
525 static CG_Cond::T compile(Id* x, Mode ctx, CodeGen& cg, CG_Builder& frag);
526 static CG_Cond::T compile(ArrayAccess* a, Mode ctx, CodeGen& cg, CG_Builder& frag);
527 static CG_Cond::T compile(ITE* ite, Mode ctx, CodeGen& cg, CG_Builder& frag);
528 static CG_Cond::T compile(BinOp* op, Mode ctx, CodeGen& cg, CG_Builder& frag);
529 static CG_Cond::T compile(UnOp* op, Mode ctx, CodeGen& cg, CG_Builder& frag);
530 static CG_Cond::T compile(Call* call, Mode ctx, CodeGen& cg, CG_Builder& frag);
531 static CG_Cond::T compile(Let* let, Mode ctx, CodeGen& cg, CG_Builder& frag);
532 static CG_Cond::T compile(Comprehension* let, Mode ctx, CodeGen& cg, CG_Builder& frag);
533};
534
535inline CG_Cond::T CG_Cond::_exists(BytecodeProc::Mode m, std::vector<T>& args) {
536 size_t count = 0;
537 for (T x : args) {
538 _T* p(x.get());
539 if (!p) {
540 // Either true or false.
541 if (!x.sign()) {
542 clear_seen(args.begin(), args.end());
543 return T::ttt();
544 }
545 continue;
546 }
547 // Otherwise, check if we've already seen this or its negation.
548 if (p->reg[1 - x.sign()].is_seen || p->reg[x.sign()].is_root) {
549 clear_seen(args.begin(), args.end());
550 return T::ttt();
551 }
552 if (p->reg[x.sign()].is_seen || p->reg[1 - x.sign()].is_root) {
553 continue;
554 }
555 // Haven't seen this yet, so save and mark it.
556 p->reg[x.sign()].is_seen = true;
557 args[count] = x;
558 count++;
559 }
560 clear_seen(args.begin(), args.end());
561 args.resize(count);
562 if (count == 0) {
563 return T::fff();
564 }
565 if (count == 1) {
566 return args[0];
567 }
568 return ~T::of_ptr(new C_And(-CG::Mode(m), args));
569}
570
571// Partially compiled bytecode.
572struct CG_Proc {
573 typedef std::vector<CG_Instr> body_t;
574
575 static unsigned char mode_mask(BytecodeProc::Mode m) {
576 return 1 << (static_cast<unsigned char>(m));
577 }
578 struct mode_iterator {
579 mode_iterator(unsigned int _x) : x(_x) {}
580 bool operator!=(const mode_iterator& o) const { return x != o.x; }
581 BytecodeProc::Mode operator*(void) const {
582 assert(x);
583 return static_cast<BytecodeProc::Mode>(find_lsb(x));
584 }
585 mode_iterator& operator++(void) {
586 x &= (x - 1);
587 return *this;
588 }
589
590 unsigned int x;
591 };
592 mode_iterator begin(void) { return mode_iterator(available_modes); }
593 mode_iterator end(void) { return mode_iterator(0); }
594
595 CG_Proc(std::string _ident, int _arity) : ident(_ident), arity(_arity), available_modes(0) {}
596
597 CG_Proc(CG_Proc&& o) : ident(o.ident), arity(o.arity), available_modes(o.available_modes) {
598 unsigned char rm(available_modes);
599 while (rm) {
600 unsigned char m(find_lsb(rm));
601 rm &= (rm - 1);
602 new (_body + m) body_t(std::move(o._body[m]));
603 o._body[m].~body_t();
604 }
605 o.available_modes = 0;
606 }
607
608 std::string ident;
609 unsigned int arity;
610
611 bool is_available(BytecodeProc::Mode m) const { return available_modes & mode_mask(m); }
612
613 std::vector<CG_Instr>& body(BytecodeProc::Mode m) {
614 static_assert(BytecodeProc::MAX_MODE < 8 * sizeof(unsigned char),
615 "Too many modes to to represent as unsigned char.");
616
617 if (!(available_modes & mode_mask(m))) {
618 available_modes |= mode_mask(m);
619 new (_body + m) body_t();
620 }
621 return _body[m];
622 }
623
624 unsigned char available_modes;
625 std::vector<CG_Instr> _body[BytecodeProc::MAX_MODE + 1];
626};
627
628// For identifying a call...
629struct CallSig {
630 ASTString id;
631 std::vector<Type> params;
632
633 CallSig(ASTString _id, std::vector<Type> _params) : id(_id) {
634 // Normalize the call types to par.
635 for (Type p : _params) {
636 p.ti(Type::TI_PAR);
637 params.push_back(p);
638 }
639 }
640
641 struct HashSig {
642 size_t operator()(const CallSig& c) const { return c.hash(); }
643 };
644 struct EqSig {
645 bool operator()(const CallSig& x, const CallSig& y) const { return x == y; }
646 };
647
648 bool operator==(const CallSig& o) const {
649 if (id != o.id || params.size() != o.params.size()) return false;
650 for (int ii = 0; ii < params.size(); ++ii) {
651 if (params[ii] != o.params[ii]) return false;
652 }
653 return true;
654 }
655
656 size_t hash(void) const {
657 size_t h(id.hash());
658 for (int ii = 0; ii < params.size(); ++ii)
659 h ^= params[ii].toInt() + 0x9e3779b9 + (h << 6) + (h >> 2);
660 return h;
661 }
662};
663
664template <class T>
665struct SigMap {
666 typedef std::unordered_map<CallSig, T, CallSig::HashSig, CallSig::EqSig> t;
667};
668
669struct CG_FunMap {
670 struct CG_FunDefn {
671 CG_FunDefn(ASTString _id) : id(_id) {}
672
673 ASTString id;
674 std::vector<FunctionI*> bodies;
675 };
676
677 ASTStringMap<unsigned int>::t id_map;
678 std::vector<CG_FunDefn> functions;
679
680 void add_body(FunctionI* f) {
681 // FIXME: Currently discarding anything with var-set.
682 ASTExprVec<VarDecl> params(f->params());
683 for (int ii = 0; ii < params.size(); ++ii) {
684 if (params[ii]->type().is_set() && !params[ii]->type().ispar()) return;
685 }
686
687 unsigned int fun_id;
688 ASTString id(f->id());
689 auto it(id_map.find(id));
690 if (it != id_map.end()) {
691 fun_id = (*it).second;
692 } else {
693 fun_id = functions.size();
694 id_map.insert(std::make_pair(id, fun_id));
695 functions.push_back(CG_FunDefn(id));
696 }
697 functions[fun_id].bodies.push_back(f);
698 }
699
700 bool dominates(FunctionI* f, FunctionI* g) {
701 auto f_params(f->params());
702 auto g_params(g->params());
703 assert(f_params.size() == g_params.size());
704 int sz(f_params.size());
705 for (int ii = 0; ii < sz; ++ii) {
706 if (!Type::bt_subtype(f_params[ii]->type(), g_params[ii]->type(), false)) return false;
707 }
708 return true;
709 }
710 void filter_bodies(std::vector<FunctionI*>::iterator& dest, std::vector<FunctionI*>::iterator b,
711 std::vector<FunctionI*>::iterator e, int arg, int sz) {
712 if (!(b != e)) // Empty partition
713 return;
714 if (arg == sz) {
715 // Find the best candidate between b and e, add it to the output.
716 // FIXME
717 auto best(b);
718 for (++b; b != e; ++b) {
719 if (dominates(*b, *best)) best = b;
720 }
721 (*dest) = (*best);
722 ++dest;
723 return;
724 }
725 // Otherwise, partition the arguments and recurse.
726 std::vector<FunctionI*>::iterator mid =
727 std::partition(b, e, [arg](FunctionI* b) { return b->params()[arg]->type().ispar(); });
728 filter_bodies(dest, b, mid, arg + 1, sz);
729 filter_bodies(dest, mid, e, arg + 1, sz);
730 }
731
732 std::vector<FunctionI*> get_bodies(unsigned int fun_id, const std::vector<Type>& args) {
733 CG_FunDefn& defn(functions[fun_id]);
734
735 // First, restrict consideration to feasible specialisations.
736 std::vector<FunctionI*> candidates;
737 int sz = args.size();
738 for (FunctionI* b : defn.bodies) {
739 ASTExprVec<VarDecl> b_params(b->params());
740 if (b_params.size() == sz) {
741 for (int pi = 0; pi < sz; ++pi) {
742 if (!args[pi].isSubtypeOf(b_params[pi]->type(), false)) goto get_bodies_continue;
743 }
744 // Can coerce args to b_params.
745 candidates.push_back(b);
746 }
747 get_bodies_continue:
748 continue;
749 }
750 // Now collect the relevant par-based refinements.
751 std::vector<FunctionI*>::iterator dest(candidates.begin());
752 filter_bodies(dest, candidates.begin(), candidates.end(), 0, sz);
753 candidates.erase(dest, candidates.end());
754 return candidates;
755 }
756
757 std::vector<FunctionI*> get_bodies(const ASTString& ident, const std::vector<Type>& args) {
758 auto it(id_map.find(ident));
759 if (it == id_map.end()) return {};
760 unsigned int fun_id((*it).second);
761 return get_bodies(fun_id, args);
762 }
763
764 std::vector<FunctionI*> get_bodies(Call* call) {
765 // Normalize all types to par, so isSubtype does what we want.
766 std::vector<Type> args;
767 int sz(call->n_args());
768 for (int ii = 0; ii < sz; ++ii) {
769 Type arg(call->arg(ii)->type());
770 arg.ti(Type::TI_PAR);
771 args.push_back(arg);
772 }
773 return get_bodies(call->id(), args);
774 }
775
776 std::pair<bool, ASTString> defines_mode(const ASTString& ident, const std::vector<Type>& args,
777 BytecodeProc::Mode mode) {
778 GCLock lock;
779 ASTString nident;
780 switch (mode) {
781 case BytecodeProc::ROOT_NEG:
782 nident = ident.str() + "_neg";
783 break;
784 case BytecodeProc::FUN:
785 nident = ident.str() + "_reif";
786 break;
787 case BytecodeProc::FUN_NEG:
788 nident = ident.str() + "_neg_reif";
789 break;
790 case BytecodeProc::IMP:
791 nident = ident.str() + "_imp";
792 break;
793 case BytecodeProc::IMP_NEG:
794 nident = ident.str() + "_neg_imp";
795 break;
796 default:
797 return {false, ASTString("")};
798 }
799 auto it(id_map.find(nident));
800 if (it == id_map.end()) {
801 return {false, nident};
802 }
803 unsigned int fun_id((*it).second);
804 std::vector<Type> reif_args;
805 reif_args.reserve(args.size() + 1);
806 for (int ii = 0; ii < args.size(); ++ii) {
807 Type arg(args[ii]);
808 arg.ti(Type::TI_PAR);
809 reif_args.push_back(arg);
810 }
811 if (mode != BytecodeProc::ROOT && mode != BytecodeProc::ROOT_NEG) {
812 reif_args.push_back(Type::parbool());
813 }
814 return {!get_bodies(fun_id, reif_args).empty(), nident};
815 }
816};
817
818struct CodeGen {
819 typedef unsigned int proc_id;
820 typedef unsigned int reg_id;
821 typedef std::pair<int, CG_Cond::T> Binding;
822 CodeGen(void)
823 : /*entry_proc(0)
824 ,*/
825 current_env(new CG_Env<Binding>()),
826 num_globals(0),
827 current_reg_count(0),
828 current_label_count(0) {
829 register_builtins();
830 }
831
832 void append(int proc, BytecodeProc::Mode m, CG_Builder& b) {
833 std::vector<CG_Instr>& body(bytecode[proc].body(m));
834
835 body.insert(body.end(), b.instrs.begin(), b.instrs.end());
836 b.clear();
837 }
838
839 void env_push(void) { current_env = CG_Env<Binding>::spawn(current_env); }
840 void env_pop(void) {
841 assert(current_env);
842 CG_Env<Binding>* c(current_env);
843 c->clear_cached_conds();
844 current_env = current_env->p;
845 delete c;
846 }
847
848 // Consult/update the available expressions in the current environment.
849 Binding cache_lookup(Expression* e);
850 void cache_store(Expression* e, Binding l);
851
852 // Function resolution
853 void register_function(FunctionI* f) { fun_map.add_body(f); }
854
855 CG_ProcID resolve_fun(FunctionI* f, bool reserved_name = false);
856 // CG_ProcID resolve_fun_pred(FunctionI* f);
857 // CG_ProcID resolve_pred_def(FunctionI* f, BytecodeProc::Mode m);
858
859 std::vector<CG_Proc> bytecode; // Bytecode we've built
860
861 inline CG_Env<Binding>& env(void) { return *current_env; }
862
863 CG_Env<Binding>* current_env; // Where are things in scope?
864 // Id -> <Register, input?>
865 std::unordered_map<VarDecl*, std::pair<int, bool>> globals_env;
866 int num_globals;
867 std::vector<FunctionI*> req_solver_predicates;
868
869 int add_global(VarDecl* vd, bool input = false) {
870 globals_env.insert(std::make_pair(vd, std::make_pair(num_globals, input)));
871 return num_globals++;
872 }
873
874 int find_global(VarDecl* str) {
875 auto pair = globals_env.at(str);
876 return pair.first;
877 }
878
879 std::vector<unsigned int> reg_trail;
880 unsigned int current_reg_count; // How many registers have been used?
881 unsigned int current_label_count;
882
883 // Helper information. For an expression, which variables does it refer to?
884 ASTStSet scope(Expression* e);
885 ExprMap<ASTStSet>::t _exp_scope;
886
887 ExprMap<CG::Mode>::t mode_map;
888
889 // Procedure information
890 void register_builtins(void);
891 CG_ProcID register_builtin(std::string s, unsigned int p);
892 CG_ProcID find_builtin(std::string s);
893 std::vector<std::pair<std::string, unsigned int>> _builtins;
894 std::unordered_map<std::string, CG_ProcID> _proc_map;
895
896 // Procedures yet to be emitted.
897 CG_FunMap fun_map;
898
899 SigMap<std::pair<CG_ProcID, bool>>::t dispatch;
900
901 std::unordered_map<FunctionI*, CG_ProcID> fun_bodies;
902 std::vector<std::pair<FunctionI*, std::pair<BytecodeProc::Mode, BytecodeProc::Mode>>>
903 pending_bodies;
904};
905
906const char* instr_name(BytecodeStream::Instr i);
907const char* agg_name(AggregationCtx::Symbol s);
908const char* mode_name(BytecodeProc::Mode m);
909
910std::tuple<CG_ProcID, BytecodeProc::Mode, bool> find_call_fun(CodeGen& cg, const ASTString& ident,
911 const Type& ret_type,
912 std::vector<Type> arg_types,
913 BytecodeProc::Mode m,
914 bool reserved_name = false);
915std::tuple<CG_ProcID, BytecodeProc::Mode, bool> find_call_fun(CodeGen& cg, Call* call,
916 BytecodeProc::Mode m,
917 bool reserved_name = false);
918
919void eval_let_body(Let* let, BytecodeProc::Mode ctx, CodeGen& cg, CG_Builder& frag,
920 std::vector<CG_Cond::T>& conj);
921
922}; // namespace MiniZinc
923
924#endif