this repo has no description
dekker.one
1#include <minizinc/astexception.hh>
2#include <minizinc/astiterator.hh>
3#include <minizinc/codegen.hh>
4#include <minizinc/copy.hh>
5#include <minizinc/eval_par.hh>
6#include <minizinc/flatten.hh>
7#include <minizinc/hash.hh>
8#include <minizinc/interpreter.hh>
9#include <minizinc/optimize.hh>
10#include <minizinc/output.hh>
11#include <minizinc/prettyprinter.hh>
12
13#include <../lib/codegen/analysis.hpp>
14#include <../lib/codegen/codegen_internal.hpp>
15#include <functional>
16#include <set>
17
18namespace MiniZinc {
19
20// Known limitations:
21// - Comprehensions and generator expressions are assumed to be total, so are evaluated in root
22// context. Expression evaluation currently runs in two modes:
23// - eval, which places the result onto the value stack on the enclosing context, or
24// - locate, which places the result into a register, and returns the register.
25// this is done to avoid a unnecessary push/pop sequences, when a result is already bound to
26// a register, and is needed for e.g. a call.
27
28#define ENABLE_PLUS 1
29// MZNC_COLLECT_LEAVES should generate fewer aggregation contexts for models with par-resolved
30// partiality (i.e. lots of array accesses)
31#define MZNC_COLLECT_LEAVES
32
33using Mode = CG::Mode;
34
35struct builtin_t {
36 std::function<CG_Cond::T(Call*, Mode, CodeGen&, CG_Builder&)> boolean;
37 std::function<CG::Binding(Call*, Mode, CodeGen&, CG_Builder&)> general;
38};
39
40typedef std::unordered_map<std::string, builtin_t> builtin_table;
41
42const char* instr_names[] = {
43 "ADDI",
44 "SUBI",
45 "MULI",
46 "DIVI",
47 "MODI",
48 "INCI",
49 "DECI",
50
51 "IMMI",
52 "CLEAR",
53 "LOAD_GLOBAL",
54 "STORE_GLOBAL",
55 "MOV",
56
57 "JMP",
58 "JMPIF",
59 "JMPIFNOT",
60
61 "EQI",
62 "LTI",
63 "LEI",
64
65 "AND",
66 "OR",
67 "NOT",
68 "XOR",
69
70 "ISPAR",
71 "ISEMPTY",
72 "LENGTH",
73 "GET_VEC",
74 "GET_ARRAY",
75
76 "LB",
77 "UB",
78 "DOM",
79
80 "MAKE_SET",
81 "INTERSECTION",
82 "UNION",
83 "DIFF",
84
85 "INTERSECT_DOMAIN",
86
87 "OPEN_AGGREGATION",
88 "CLOSE_AGGREGATION",
89 "SIMPLIFY_LIN",
90
91 "PUSH",
92 "POP",
93 "POST",
94
95 "RET",
96 "CALL",
97 "BUILTIN",
98 "TCALL",
99
100 "ITER_ARRAY",
101 "ITER_VEC",
102 "ITER_RANGE",
103 "ITER_NEXT",
104 "ITER_BREAK",
105
106 "TRACE",
107 "ABORT",
108};
109
110const char* mode_names[] = {
111 "ROOT", "ROOT_NEG", "FUN", "FUN_NEG", "IMP", "IMP_NEG", "MAX_MODE",
112};
113
114const char* agg_names[] = {"AND", "OR", "VEC", "OTHER"};
115const char* instr_name(BytecodeStream::Instr i) { return instr_names[i]; }
116
117const char* agg_name(AggregationCtx::Symbol s) { return agg_names[s]; }
118const char* mode_name(BytecodeProc::Mode m) { return mode_names[m]; }
119
120inline void TODO(void) { throw InternalError("Not yet implemented!"); }
121
122void CodeGen::register_builtins(void) {
123 // Solver Built-ins
124 register_builtin("mk_intvar", 1);
125
126 // Constants
127 register_builtin("absent", 1);
128 register_builtin("infinity", 1);
129 register_builtin("boolean_domain", 0);
130 register_builtin("infinite_domain", 0);
131
132 // Interpreter Built-ins
133 register_builtin("uniform", 2);
134 register_builtin("sol", 1);
135 register_builtin("sort_by", 2);
136 register_builtin("floor", 1);
137 register_builtin("ceil", 1);
138 register_builtin("slice_Xd", 3);
139 register_builtin("array_Xd", 2);
140 register_builtin("index_set", 2);
141 register_builtin("internal_sort", 1);
142}
143
144void OPEN_AGG(CodeGen& cg, CG_Builder& frag, AggregationCtx::Symbol ctx) {
145 cg.env_push();
146 cg.reg_trail.push_back(cg.current_reg_count);
147
148 PUSH_INSTR(frag, BytecodeStream::OPEN_AGGREGATION, ctx);
149}
150void CLOSE_AGG(CodeGen& cg, CG_Builder& frag) {
151 assert(cg.reg_trail.size() > 0);
152 int old_reg_count = cg.current_reg_count;
153 cg.current_reg_count = cg.reg_trail.back();
154 cg.reg_trail.pop_back();
155 if (cg.current_reg_count < old_reg_count) {
156 PUSH_INSTR(frag, BytecodeStream::CLEAR, CG::r(cg.current_reg_count), CG::r(old_reg_count - 1));
157 }
158 PUSH_INSTR(frag, BytecodeStream::CLOSE_AGGREGATION);
159 cg.env_pop();
160}
161
162void OPEN_AND(CodeGen& cg, CG_Builder& frag) { OPEN_AGG(cg, frag, AggregationCtx::VCTX_AND); }
163void OPEN_OR(CodeGen& cg, CG_Builder& frag) { OPEN_AGG(cg, frag, AggregationCtx::VCTX_OR); }
164void OPEN_OTHER(CodeGen& cg, CG_Builder& frag) { OPEN_AGG(cg, frag, AggregationCtx::VCTX_OTHER); }
165void OPEN_VEC(CodeGen& cg, CG_Builder& frag) { OPEN_AGG(cg, frag, AggregationCtx::VCTX_VEC); }
166
167CG_ProcID CodeGen::register_builtin(std::string s, unsigned int arity) {
168 auto it(_proc_map.find(s));
169 if (it != _proc_map.end()) {
170 // throw InternalError(std::string("Builtin already registered: ") + s);
171 std::cerr << "WARNING: Builtin " << s << " already registered." << std::endl;
172 return it->second;
173 }
174
175 CG_ProcID id(CG_ProcID::builtin(_builtins.size()));
176 _builtins.push_back(std::make_pair(s, arity));
177 _proc_map.insert(std::make_pair(s, id));
178 return id;
179}
180
181CG_ProcID CodeGen::find_builtin(std::string s) {
182 auto it(_proc_map.find(s));
183 assert(it != _proc_map.end());
184 return (*it).second;
185}
186
187int bind_cst(int x, CodeGen& cg, CG_Builder& frag);
188
189void bind_binop_var(CodeGen& cg, CG_Builder& frag, Mode ctx, BinOpType op, int r_lhs, int r_rhs) {
190 GCLock lock;
191 switch (op) {
192 // Actual builtins
193 case BOT_PLUS: {
194 auto fun =
195 find_call_fun(cg, {"op_plus"}, Type::varint(), {Type::varint(), Type::varint()}, ctx);
196 assert(BytecodeProc::is_neg(ctx) == BytecodeProc::is_neg(std::get<1>(fun)));
197 PUSH_INSTR(frag, BytecodeStream::CALL, std::get<1>(fun), std::get<0>(fun),
198 CG::i(!std::get<2>(fun)), CG::r(r_lhs), CG::r(r_rhs));
199 return;
200 }
201 case BOT_MINUS: {
202 auto fun =
203 find_call_fun(cg, {"op_minus"}, Type::varint(), {Type::varint(), Type::varint()}, ctx);
204 assert(BytecodeProc::is_neg(ctx) == BytecodeProc::is_neg(std::get<1>(fun)));
205 PUSH_INSTR(frag, BytecodeStream::CALL, std::get<1>(fun), std::get<0>(fun),
206 CG::i(!std::get<2>(fun)), CG::r(r_lhs), CG::r(r_rhs));
207 return;
208 }
209 case BOT_MULT: {
210 auto fun =
211 find_call_fun(cg, {"op_times"}, Type::varint(), {Type::varint(), Type::varint()}, ctx);
212 assert(BytecodeProc::is_neg(ctx) == BytecodeProc::is_neg(std::get<1>(fun)));
213 PUSH_INSTR(frag, BytecodeStream::CALL, std::get<1>(fun), std::get<0>(fun),
214 CG::i(!std::get<2>(fun)), CG::r(r_lhs), CG::r(r_rhs));
215 return;
216 }
217 case BOT_IDIV: {
218 auto fun = find_call_fun(cg, {"op_int_division"}, Type::varint(),
219 {Type::varint(), Type::varint()}, ctx);
220 assert(BytecodeProc::is_neg(ctx) == BytecodeProc::is_neg(std::get<1>(fun)));
221 PUSH_INSTR(frag, BytecodeStream::CALL, std::get<1>(fun), std::get<0>(fun),
222 CG::i(!std::get<2>(fun)), CG::r(r_lhs), CG::r(r_rhs));
223 return;
224 }
225 case BOT_DIV: {
226 auto fun = find_call_fun(cg, {"op_float_division"}, Type::varint(),
227 {Type::varint(), Type::varint()}, ctx);
228 assert(BytecodeProc::is_neg(ctx) == BytecodeProc::is_neg(std::get<1>(fun)));
229 PUSH_INSTR(frag, BytecodeStream::CALL, std::get<1>(fun), std::get<0>(fun),
230 CG::i(!std::get<2>(fun)), CG::r(r_lhs), CG::r(r_rhs));
231 return;
232 }
233 case BOT_MOD: {
234 auto fun =
235 find_call_fun(cg, {"op_modulus"}, Type::varint(), {Type::varint(), Type::varint()}, ctx);
236 assert(BytecodeProc::is_neg(ctx) == BytecodeProc::is_neg(std::get<1>(fun)));
237 PUSH_INSTR(frag, BytecodeStream::CALL, std::get<1>(fun), std::get<0>(fun),
238 CG::i(!std::get<2>(fun)), CG::r(r_lhs), CG::r(r_rhs));
239 return;
240 }
241 case BOT_DOTDOT: {
242 // The values in r_lhs and r_rhs had better be IMMIs.
243 OPEN_VEC(cg, frag);
244 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(r_lhs));
245 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(r_rhs));
246 CLOSE_AGG(cg, frag);
247 return;
248 }
249 case BOT_PLUSPLUS: {
250 OPEN_VEC(cg, frag);
251 Foreach iter_lhs(cg, r_lhs);
252 iter_lhs.emit_pre(frag);
253 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(iter_lhs.val()));
254 iter_lhs.emit_post(frag);
255
256 Foreach iter_rhs(cg, r_rhs);
257 iter_rhs.emit_pre(frag);
258 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(iter_rhs.val()));
259 iter_rhs.emit_post(frag);
260 CLOSE_AGG(cg, frag);
261 return;
262 }
263 default:
264 break;
265 }
266 throw InternalError("Unexpected fall-through in bind_binop_var.");
267}
268
269int bind_binop_par_int(CodeGen& cg, CG_Builder& frag, BinOpType op, int r_lhs, int r_rhs) {
270 int r;
271 switch (op) {
272 // Actual builtins
273 case BOT_EQ:
274 case BOT_EQUIV:
275 r = GET_REG(cg);
276 PUSH_INSTR(frag, BytecodeStream::EQI, CG::r(r_lhs), CG::r(r_rhs), CG::r(r));
277 return r;
278 case BOT_NQ:
279 r = GET_REG(cg);
280 PUSH_INSTR(frag, BytecodeStream::EQI, CG::r(r_lhs), CG::r(r_rhs), CG::r(r));
281 PUSH_INSTR(frag, BytecodeStream::NOT, CG::r(r), CG::r(r));
282 return r;
283 case BOT_LE:
284 r = GET_REG(cg);
285 PUSH_INSTR(frag, BytecodeStream::LTI, CG::r(r_lhs), CG::r(r_rhs), CG::r(r));
286 return r;
287 case BOT_LQ:
288 r = GET_REG(cg);
289 PUSH_INSTR(frag, BytecodeStream::LEI, CG::r(r_lhs), CG::r(r_rhs), CG::r(r));
290 return r;
291 case BOT_GR:
292 r = GET_REG(cg);
293 PUSH_INSTR(frag, BytecodeStream::LTI, CG::r(r_rhs), CG::r(r_lhs), CG::r(r));
294 return r;
295 case BOT_GQ:
296 r = GET_REG(cg);
297 PUSH_INSTR(frag, BytecodeStream::LEI, CG::r(r_rhs), CG::r(r_lhs), CG::r(r));
298 return r;
299 case BOT_XOR:
300 r = GET_REG(cg);
301 PUSH_INSTR(frag, BytecodeStream::XOR, CG::r(r_rhs), CG::r(r_lhs), CG::r(r));
302 return r;
303 case BOT_AND:
304 r = GET_REG(cg);
305 PUSH_INSTR(frag, BytecodeStream::AND, CG::r(r_lhs), CG::r(r_rhs), CG::r(r));
306 return r;
307 case BOT_OR:
308 r = GET_REG(cg);
309 PUSH_INSTR(frag, BytecodeStream::OR, CG::r(r_lhs), CG::r(r_rhs), CG::r(r));
310 return r;
311 case BOT_IMPL:
312 r = GET_REG(cg);
313 PUSH_INSTR(frag, BytecodeStream::NOT, CG::r(r_lhs), CG::r(r));
314 PUSH_INSTR(frag, BytecodeStream::OR, CG::r(r), CG::r(r_rhs), CG::r(r));
315 return r;
316 case BOT_RIMPL:
317 r = GET_REG(cg);
318 PUSH_INSTR(frag, BytecodeStream::NOT, CG::r(r_rhs), CG::r(r));
319 PUSH_INSTR(frag, BytecodeStream::XOR, CG::r(r_lhs), CG::r(r), CG::r(r));
320 return r;
321 case BOT_PLUS:
322 r = GET_REG(cg);
323 PUSH_INSTR(frag, BytecodeStream::ADDI, CG::r(r_lhs), CG::r(r_rhs), CG::r(r));
324 return r;
325 case BOT_MINUS:
326 r = GET_REG(cg);
327 PUSH_INSTR(frag, BytecodeStream::SUBI, CG::r(r_lhs), CG::r(r_rhs), CG::r(r));
328 return r;
329 case BOT_MULT:
330 r = GET_REG(cg);
331 PUSH_INSTR(frag, BytecodeStream::MULI, CG::r(r_lhs), CG::r(r_rhs), CG::r(r));
332 return r;
333 case BOT_IDIV:
334 r = GET_REG(cg);
335 PUSH_INSTR(frag, BytecodeStream::DIVI, CG::r(r_lhs), CG::r(r_rhs), CG::r(r));
336 return r;
337 case BOT_MOD:
338 r = GET_REG(cg);
339 PUSH_INSTR(frag, BytecodeStream::MODI, CG::r(r_lhs), CG::r(r_rhs), CG::r(r));
340 return r;
341 case BOT_DOTDOT:
342 // The values in r_lhs and r_rhs had better be IMMIs.
343 OPEN_VEC(cg, frag);
344 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(r_lhs));
345 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(r_rhs));
346 CLOSE_AGG(cg, frag);
347 r = GET_REG(cg);
348 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r));
349 return r;
350 case BOT_IN: {
351 int l_head(GET_LABEL(cg));
352 int l_stop(GET_LABEL(cg));
353 int l_exit(GET_LABEL(cg));
354 r = GET_REG(cg);
355 PUSH_INSTR(frag, BytecodeStream::ITER_VEC, CG::r(r_rhs), CG::l(l_exit));
356 PUSH_LABEL(frag, l_head);
357 PUSH_INSTR(frag, BytecodeStream::ITER_NEXT, CG::r(r));
358 // Start of interval.
359 PUSH_INSTR(frag, BytecodeStream::LEI, CG::r(r), CG::r(r_lhs), CG::r(r));
360 PUSH_INSTR(frag, BytecodeStream::JMPIFNOT, CG::r(r), CG::l(l_stop));
361 // End of interval
362 PUSH_INSTR(frag, BytecodeStream::ITER_NEXT, CG::r(r));
363 PUSH_INSTR(frag, BytecodeStream::LEI, CG::r(r_lhs), CG::r(r), CG::r(r));
364 PUSH_INSTR(frag, BytecodeStream::JMPIF, CG::r(r), CG::l(l_stop));
365 PUSH_INSTR(frag, BytecodeStream::JMP, CG::l(l_head));
366 PUSH_LABEL(frag, l_stop);
367 PUSH_INSTR(frag, BytecodeStream::ITER_BREAK, CG::i(1));
368 PUSH_LABEL(frag, l_exit);
369 return r;
370 }
371 case BOT_PLUSPLUS: {
372 r = GET_REG(cg);
373 OPEN_VEC(cg, frag);
374 Foreach iter_lhs(cg, r_lhs);
375 iter_lhs.emit_pre(frag);
376 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(iter_lhs.val()));
377 iter_lhs.emit_post(frag);
378
379 Foreach iter_rhs(cg, r_rhs);
380 iter_rhs.emit_pre(frag);
381 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(iter_rhs.val()));
382 iter_rhs.emit_post(frag);
383 CLOSE_AGG(cg, frag);
384 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r));
385 return r;
386 }
387 default:
388 break;
389 }
390 throw InternalError("Unexpected fall-through in bind_binop_par.");
391}
392
393int bind_binop_par_set(CodeGen& cg, CG_Builder& frag, BinOpType op, int r_lhs, int r_rhs) {
394 int r;
395 switch (op) {
396 // Actual builtins
397 case BOT_EQ:
398 case BOT_EQUIV: {
399 r = GET_REG(cg);
400 int r_tmp = GET_REG(cg);
401 PUSH_INSTR(frag, BytecodeStream::DIFF, CG::r(r_lhs), CG::r(r_rhs), CG::r(r));
402 PUSH_INSTR(frag, BytecodeStream::ISEMPTY, CG::r(r), CG::r(r));
403 PUSH_INSTR(frag, BytecodeStream::DIFF, CG::r(r_rhs), CG::r(r_lhs), CG::r(r_tmp));
404 PUSH_INSTR(frag, BytecodeStream::ISEMPTY, CG::r(r_tmp), CG::r(r_tmp));
405 PUSH_INSTR(frag, BytecodeStream::AND, CG::r(r), CG::r(r_tmp), CG::r(r));
406 return r;
407 }
408 case BOT_NQ: {
409 r = bind_binop_par_set(cg, frag, BOT_EQ, r_lhs, r_rhs);
410 PUSH_INSTR(frag, BytecodeStream::NOT, CG::r(r), CG::r(r));
411 return r;
412 }
413 case BOT_LE:
414 r = GET_REG(cg);
415 TODO();
416 return r;
417 case BOT_LQ:
418 r = GET_REG(cg);
419 TODO();
420 return r;
421 case BOT_GR:
422 r = GET_REG(cg);
423 TODO();
424 return r;
425 case BOT_GQ:
426 r = GET_REG(cg);
427 TODO();
428 return r;
429 case BOT_UNION:
430 r = GET_REG(cg);
431 PUSH_INSTR(frag, BytecodeStream::UNION, CG::r(r_lhs), CG::r(r_rhs), CG::r(r));
432 return r;
433 case BOT_INTERSECT:
434 r = GET_REG(cg);
435 PUSH_INSTR(frag, BytecodeStream::INTERSECTION, CG::r(r_lhs), CG::r(r_rhs), CG::r(r));
436 return r;
437 case BOT_SUBSET: {
438 // (L subset R) <-> ((L intersect R) == L)
439 r = GET_REG(cg);
440 int l_fin(GET_LABEL(cg));
441 int r_inter(GET_REG(cg));
442 PUSH_INSTR(frag, BytecodeStream::INTERSECTION, CG::r(r_lhs), CG::r(r_rhs), CG::r(r_inter));
443
444 int r_sz(GET_REG(cg));
445 int r_tmp(GET_REG(cg));
446 PUSH_INSTR(frag, BytecodeStream::LENGTH, CG::r(r_lhs), CG::r(r_tmp));
447 PUSH_INSTR(frag, BytecodeStream::LENGTH, CG::r(r_inter), CG::r(r_sz));
448 PUSH_INSTR(frag, BytecodeStream::EQI, CG::r(r_tmp), CG::r(r_sz), CG::r(r));
449 PUSH_INSTR(frag, BytecodeStream::JMPIFNOT, CG::r(r), CG::l(l_fin));
450
451 int r_idx(GET_REG(cg));
452 int l_loop(GET_LABEL(cg));
453 PUSH_INSTR(frag, BytecodeStream::IMMI, CG::i(1), CG::r(r_idx));
454 PUSH_LABEL(frag, l_loop);
455 PUSH_INSTR(frag, BytecodeStream::LEI, CG::r(r_idx), CG::r(r_sz), CG::r(r_tmp));
456 PUSH_INSTR(frag, BytecodeStream::JMPIFNOT, CG::r(r_tmp), CG::l(l_fin));
457
458 int r_tmp2(GET_REG(cg));
459 PUSH_INSTR(frag, BytecodeStream::GET_VEC, CG::r(r_lhs), CG::r(r_idx), CG::r(r_tmp));
460 PUSH_INSTR(frag, BytecodeStream::GET_VEC, CG::r(r_inter), CG::r(r_idx), CG::r(r_tmp2));
461 PUSH_INSTR(frag, BytecodeStream::EQI, CG::r(r_tmp), CG::r(r_tmp2), CG::r(r));
462 PUSH_INSTR(frag, BytecodeStream::JMPIFNOT, CG::r(r), CG::l(l_fin));
463
464 PUSH_INSTR(frag, BytecodeStream::INCI, CG::r(r_idx));
465 PUSH_INSTR(frag, BytecodeStream::JMP, CG::l(l_loop));
466
467 PUSH_LABEL(frag, l_fin);
468 return r;
469 }
470 case BOT_SUPERSET: {
471 return bind_binop_par_set(cg, frag, BOT_SUBSET, r_rhs, r_lhs);
472 }
473 case BOT_DIFF: {
474 int r(GET_REG(cg));
475 PUSH_INSTR(frag, BytecodeStream::DIFF, CG::r(r_lhs), CG::r(r_rhs), CG::r(r));
476 return r;
477 }
478 case BOT_SYMDIFF: {
479 int r(GET_REG(cg));
480 int r_tmp(GET_REG(cg));
481 PUSH_INSTR(frag, BytecodeStream::DIFF, CG::r(r_lhs), CG::r(r_rhs), CG::r(r));
482 PUSH_INSTR(frag, BytecodeStream::DIFF, CG::r(r_rhs), CG::r(r_lhs), CG::r(r_tmp));
483 PUSH_INSTR(frag, BytecodeStream::UNION, CG::r(r), CG::r(r_tmp), CG::r(r));
484 return r;
485 }
486 default:
487 break;
488 }
489 throw InternalError("Unexpected fall-through in bind_binop_par_set.");
490}
491
492CG_Cond::T linear_cond(CodeGen& cg, CG_Builder& frag, BinOpType op, Mode ctx, int r_lhs,
493 int r_rhs) {
494 GCLock lock;
495 switch (op) {
496 // Actual builtins
497 case BOT_LQ:
498 case BOT_LE: {
499 // Check bounds
500 int lb_lhs = GET_REG(cg);
501 int ub_rhs = GET_REG(cg);
502 PUSH_INSTR(frag, BytecodeStream::LB, CG::r(r_lhs), CG::r(lb_lhs));
503 PUSH_INSTR(frag, BytecodeStream::UB, CG::r(r_rhs), CG::r(ub_rhs));
504 PUSH_INSTR(frag, (op == BOT_LE ? BytecodeStream::LTI : BytecodeStream::LEI), CG::r(lb_lhs),
505 CG::r(ub_rhs), CG::r(lb_lhs));
506 int c = GET_REG(cg);
507 int x = GET_REG(cg);
508 int k = GET_REG(cg);
509 int z = (op == BOT_LE ? +1 : 0);
510 PUSH_INSTR(frag, BytecodeStream::SIMPLIFY_LIN, CG::r(r_lhs), CG::r(r_rhs), CG::i(z), CG::r(c),
511 CG::r(x), CG::r(k));
512 auto linear =
513 CG_Cond::call({"pre_int_lin_le"}, ctx, true,
514 {Type::varbool(), Type::parint(1), Type::varint(1), Type::parint()},
515 {CG::r(c), CG::r(x), CG::r(k)});
516 return CG_Cond::forall(ctx, CG_Cond::reg(lb_lhs, true), linear);
517 }
518 case BOT_EQUIV:
519 case BOT_EQ: {
520 // Check domain
521 int dom_lhs = GET_REG(cg);
522 int dom_rhs = GET_REG(cg);
523 PUSH_INSTR(frag, BytecodeStream::DOM, CG::r(r_lhs), CG::r(dom_lhs));
524 PUSH_INSTR(frag, BytecodeStream::DOM, CG::r(r_rhs), CG::r(dom_rhs));
525 PUSH_INSTR(frag, BytecodeStream::INTERSECTION, CG::r(dom_lhs), CG::r(dom_rhs),
526 CG::r(dom_lhs));
527 PUSH_INSTR(frag, BytecodeStream::ISEMPTY, CG::r(dom_lhs), CG::r(dom_rhs));
528 PUSH_INSTR(frag, BytecodeStream::NOT, CG::r(dom_rhs), CG::r(dom_rhs));
529 // Create linear equation
530 int k = GET_REG(cg);
531 int c = GET_REG(cg);
532 int x = GET_REG(cg);
533 PUSH_INSTR(frag, BytecodeStream::SIMPLIFY_LIN, CG::r(r_lhs), CG::r(r_rhs), CG::i(0), CG::r(c),
534 CG::r(x), CG::r(k));
535 auto linear =
536 CG_Cond::call({"pre_int_lin_eq"}, ctx, true,
537 {Type::varbool(), Type::parint(1), Type::varint(1), Type::parint()},
538 {CG::r(c), CG::r(x), CG::r(k)});
539 return CG_Cond::forall(ctx, CG_Cond::reg(dom_rhs, true), linear);
540 }
541 case BOT_NQ:
542 return ~linear_cond(cg, frag, BOT_EQ, -ctx, r_lhs, r_rhs);
543 case BOT_GR:
544 return linear_cond(cg, frag, BOT_LE, ctx, r_rhs, r_lhs);
545 case BOT_GQ:
546 return linear_cond(cg, frag, BOT_LQ, ctx, r_rhs, r_lhs);
547 default:
548 break;
549 }
550 throw InternalError("Unexpected fall-through in linear_cond.");
551}
552
553CG_ProcID CodeGen::resolve_fun(FunctionI* fun, bool reserved_name) {
554 auto it(fun_bodies.find(fun));
555 if (it != fun_bodies.end()) return it->second;
556
557 GCLock lock;
558
559 int p_idx = bytecode.size();
560 CG_ProcID p_id(CG_ProcID::proc(p_idx));
561 ASTExprVec<VarDecl> params(fun->params());
562
563 std::stringstream ss;
564 if (!reserved_name && fun->e()) {
565 ss << "f_" << fun->id().str();
566 for (auto& param : params) {
567 ss << "_";
568 if (param->type().dim() > 0) {
569 ss << "d" << param->type().dim();
570 } else if (param->type().dim() < 0) {
571 ss << "dT";
572 }
573 if (param->type().isvar()) {
574 ss << "v";
575 }
576 if (param->type().is_set()) {
577 ss << "s";
578 }
579 switch (param->type().bt()) {
580 case Type::BT_BOOL: {
581 ss << "b";
582 break;
583 }
584 case Type::BT_INT: {
585 ss << "i";
586 break;
587 }
588 case Type::BT_FLOAT: {
589 ss << "f";
590 break;
591 }
592 case Type::BT_STRING: {
593 ss << "s";
594 break;
595 }
596 case Type::BT_ANN: {
597 ss << "a";
598 break;
599 }
600 case Type::BT_TOP: {
601 ss << "t";
602 break;
603 }
604 default: {
605 assert(false);
606 break;
607 }
608 }
609 }
610 } else {
611 ss << fun->id().str();
612 }
613
614 bytecode.emplace_back(ss.str(), params.size());
615 fun_bodies.insert(std::make_pair(fun, p_id));
616 return p_id;
617}
618
619struct dispatch_node {
620 int label;
621 int level;
622 uint64_t sig;
623};
624
625std::tuple<CG_ProcID, BytecodeProc::Mode, bool> find_call_fun(CodeGen& cg, const ASTString& ident,
626 const Type& ret_type,
627 std::vector<Type> arg_types,
628 BytecodeProc::Mode m,
629 bool reserved_name) {
630 for (auto& arg_type : arg_types) {
631 arg_type.ti(Type::TI_PAR);
632 }
633 int sz = arg_types.size();
634 CallSig sig(ident, arg_types);
635 auto it(cg.dispatch.find(sig));
636
637 BytecodeProc::Mode call_mode(ret_type.isbool() ? m : BytecodeProc::FUN);
638 BytecodeProc::Mode def_mode(ret_type.isbool() ? m : BytecodeProc::ROOT);
639
640 if (it != cg.dispatch.end()) {
641 auto d_proc(it->second);
642 if (d_proc.first.is_builtin() || cg.bytecode[d_proc.first.id()].is_available(call_mode)) {
643 return {d_proc.first, call_mode, d_proc.second};
644 }
645 }
646
647 GCLock lock;
648 auto bodies = std::move(cg.fun_map.get_bodies(ident, arg_types));
649 assert(!bodies.empty());
650 auto neg_bodies = std::move(cg.fun_map.get_bodies(ASTString(ident.str() + "_neg"), arg_types));
651
652 if (ret_type.isbool() && call_mode != BytecodeProc::ROOT) {
653 bool valid = false;
654 if (cg.fun_map.defines_mode(ident, arg_types, call_mode).first) {
655 valid = true;
656 } else if (BytecodeProc::is_neg(m) && std::any_of(neg_bodies.begin(), neg_bodies.end(),
657 [](FunctionI* fi) { return fi->e(); })) {
658 valid = true;
659 } else {
660 valid = cg.fun_map.defines_mode(ident, arg_types, BytecodeProc::FUN).first;
661 if (valid) {
662 call_mode = BytecodeProc::FUN;
663 def_mode = BytecodeProc::FUN;
664 }
665 }
666 if (!valid &&
667 std::none_of(bodies.begin(), bodies.end(), [](FunctionI* fi) { return fi->e(); })) {
668 throw InternalError(ident.str() +
669 " is used in a reified context, but no reification is available.");
670 }
671 }
672
673 std::vector<CG_ProcID> procs;
674 for (FunctionI* b : bodies) {
675 CG_ProcID body(cg.resolve_fun(b, reserved_name && bodies.size() == 1));
676 // Force the body to be created
677 procs.push_back(body);
678 if (!cg.bytecode[body.id()].is_available(call_mode)) {
679 cg.bytecode[body.id()].body(call_mode);
680 cg.pending_bodies.emplace_back(b, std::make_pair(call_mode, def_mode));
681 }
682 }
683
684 // If there's a unique candidate, go for it.
685 if (procs.size() == 1) {
686 if (it == cg.dispatch.end()) {
687 cg.dispatch.insert(std::make_pair(sig, std::make_pair(procs[0], false)));
688 }
689 return {procs[0], call_mode, false};
690 }
691
692 CG_ProcID d_proc(CG_ProcID::builtin(0));
693 if (it != cg.dispatch.end()) {
694 d_proc = it->second.first;
695 } else {
696 // Otherwise, generate the dispatch function.
697 int p_idx = cg.bytecode.size();
698
699 std::stringstream ss;
700 if (reserved_name) {
701 ss << ident.str();
702 } else {
703 ss << "d_" << ident.str();
704 for (auto& type : arg_types) {
705 ss << "_";
706 if (type.dim() > 0) {
707 ss << "d" << type.dim();
708 } else if (type.dim() < 0) {
709 ss << "dT";
710 }
711 if (type.is_set()) {
712 ss << "s";
713 }
714 switch (type.bt()) {
715 case Type::BT_BOOL: {
716 ss << "b";
717 break;
718 }
719 case Type::BT_INT: {
720 ss << "i";
721 break;
722 }
723 case Type::BT_FLOAT: {
724 ss << "f";
725 break;
726 }
727 case Type::BT_STRING: {
728 ss << "s";
729 break;
730 }
731 case Type::BT_ANN: {
732 ss << "a";
733 break;
734 }
735 case Type::BT_TOP: {
736 ss << "t";
737 break;
738 }
739 default: {
740 assert(false);
741 break;
742 }
743 }
744 }
745 }
746
747 d_proc = CG_ProcID::proc(p_idx);
748 cg.bytecode.emplace_back(ss.str(), arg_types.size());
749 cg.dispatch.insert(std::make_pair(sig, std::make_pair(d_proc, true)));
750 }
751
752 // Now generate the dispatch body.
753 CG_Builder frag;
754 std::vector<uint64_t> var_sig(sz);
755 std::vector<uint64_t> def_sig(bodies.size());
756 for (int bi = 0; bi < bodies.size(); ++bi) {
757 ASTExprVec<VarDecl> params(bodies[bi]->params());
758 for (int ii = 0; ii < params.size(); ++ii) {
759 if (params[ii]->type().isvar()) {
760 var_sig[ii] |= 1ull << bi;
761 def_sig[bi] |= 1ull << ii;
762 }
763 }
764 }
765
766 std::vector<std::unordered_map<uint64_t, int>> sig_table(sz + 1);
767 std::vector<dispatch_node> nodes;
768
769 nodes.push_back(dispatch_node{-1, 0, (1ull << bodies.size()) - 1});
770
771 for (int ii = 0; ii < nodes.size(); ii++) {
772 dispatch_node d(nodes[ii]);
773 if (d.label != -1) PUSH_LABEL(frag, d.label);
774 if (!d.sig) {
775 PUSH_INSTR(frag, BytecodeStream::ABORT);
776 } else if (d.level == sz) {
777 // Find the best candidate, and emit a call.
778 uint64_t candidates(d.sig);
779 unsigned int best(find_lsb(candidates));
780 uint64_t best_sig(def_sig[best]);
781 candidates ^= 1ull << best;
782 while (candidates) {
783 unsigned int curr(find_lsb(candidates));
784 candidates ^= 1ull << curr;
785 uint64_t sig(def_sig[curr]);
786 if (!(sig & ~best_sig)) {
787 // At least as good as the incumbent
788 best = curr;
789 best_sig = sig;
790 }
791 }
792 CG_ProcID p_id(procs[best]);
793 PUSH_INSTR(frag, BytecodeStream::TCALL, call_mode, p_id,
794 CG::i(bodies[best]->ti()->type().isvar()));
795 } else {
796 int par_label;
797 auto p_it(sig_table[d.level + 1].find(d.sig));
798 if (p_it != sig_table[d.level + 1].end()) {
799 par_label = p_it->second;
800 } else {
801 par_label = GET_LABEL(cg);
802 // int idx = nodes.size();
803 sig_table[d.level + 1].insert(std::make_pair(d.sig, par_label));
804 nodes.push_back(dispatch_node{par_label, d.level + 1, d.sig});
805 }
806 uint64_t v_sig(d.sig & var_sig[d.level]);
807 if (v_sig == d.sig) {
808 PUSH_INSTR(frag, BytecodeStream::JMP, CG::l(par_label));
809 } else {
810 int var_label;
811 auto v_it(sig_table[d.level + 1].find(v_sig));
812 if (v_it != sig_table[d.level + 1].end()) {
813 var_label = v_it->second;
814 } else {
815 var_label = GET_LABEL(cg);
816 // int idx = nodes.size();
817 sig_table[d.level + 1].insert(std::make_pair(v_sig, var_label));
818 nodes.push_back(dispatch_node{var_label, d.level + 1, v_sig});
819 }
820
821 PUSH_INSTR(frag, BytecodeStream::ISPAR, CG::r(d.level), CG::r(sz));
822 PUSH_INSTR(frag, BytecodeStream::JMPIF, CG::r(sz), CG::l(par_label));
823 PUSH_INSTR(frag, BytecodeStream::JMP, CG::l(var_label));
824 }
825 }
826 }
827
828 cg.append(d_proc.id(), call_mode, frag);
829
830 return {d_proc, call_mode, false};
831}
832
833std::tuple<CG_ProcID, BytecodeProc::Mode, bool> find_call_fun(CodeGen& cg, Call* call,
834 BytecodeProc::Mode m,
835 bool reserved_name) {
836 std::vector<Type> arg_types;
837 int sz = call->n_args();
838 for (int ii = 0; ii < sz; ++ii) {
839 Type t(call->arg(ii)->type());
840 arg_types.push_back(t);
841 }
842 return find_call_fun(cg, call->id(), call->type(), arg_types, m, reserved_name);
843}
844/*
845CG_ProcID find_call_pred(CodeGen& cg, Call* c) {
846 return CG_ProcID::proc(0xbead);
847
848}
849*/
850
851// Analyse an expression (and sub-expressions) for partiality
852#if 0
853struct ClearFlags : public EVisitor {
854 bool enter(Expression* e) {
855 if(!e->isUnboxedVal() && e->user_flag0()) {
856 e->user_flag0(0);
857 e->user_flag1(0);
858 return true;
859 }
860 return false;
861 }
862 // FIXME: We need to identify call bodies.
863 void vCall(const Call&) {}
864
865 static void clear(Expression* e) {
866 ClearFlags cf;
867 TopDownIterator<ClearFlags> td(cf);
868 td.run(e);
869 }
870};
871
872struct Partiality {
873 Partiality(CodeGen& _cg) : cg(_cg) { }
874
875 // We use _flag_3 to track whether something is already on the
876 // stack, and _flag_4 to track whether it is eliminated as true.
877 bool is_partial(Expression* e) {
878 if(e->isUnboxedVal())
879 return false;
880 // Either on the call stack and still open, or completed.
881 // In either case, check whether the partiality-flag is set.
882 if(e->user_flag0())
883 return e->user_flag1();
884 // Otherwise, mark it as pending, and enter it.
885 e->user_flag0(1);
886 bool p = _is_partial(e);
887 // Record the result, and return.
888 e->user_flag1(p);
889 return p;
890 }
891
892 bool _is_partial(Expression* e) {
893 // First, Boolean expressions are always total.
894 if(e->type().isbool())
895 return false;
896 // Otherwise, look at the
897 switch(e->eid()) {
898 case Expression::E_INTLIT:
899 case Expression::E_FLOATLIT:
900 case Expression::E_SETLIT:
901 case Expression::E_BOOLLIT:
902 case Expression::E_STRINGLIT:
903 case Expression::E_ID:
904 return false;
905 case Expression::E_ARRAYLIT: {
906 ArrayLit* a(e->template cast<ArrayLit>());
907 int sz(a->size());
908 for(int ii = 0; ii < sz; ++ii) {
909 if(is_partial((*a)[ii]))
910 return true;
911 }
912 return true;
913 }
914 case Expression::E_ARRAYACCESS: {
915 /*
916 ArrayAccess* a(e->template cast<ArrayAccess>());
917 if(is_partial(a->v()))
918 return true;
919 ASTExprVec<Expression> idx(a->idx());
920 int sz(idx.size());
921 for(int ii = 0; ii < sz; ++ii) {
922 if(is_partial(idx[ii]))
923 return true;
924 }
925 break;
926 */
927 // FIXME: Needs an analysis to determine whether
928 // dom(a->v) subseteq index_set(A).
929 return true;
930 }
931 case Expression::E_COMP: {
932 // A comprehension is total if all its generators
933 // and its body are total.
934 // Don't need to look in the where clauses, because
935 // they're Boolean, and therefore total.
936 Comprehension* c(e->template cast<Comprehension>());
937 int sz = c->n_generators();
938 for(int g = 0; g < c->n_generators(); ++g) {
939 if(is_partial(c->in(g)))
940 return true;
941 }
942 return is_partial(c->e());
943 }
944 case Expression::E_ITE: {
945 // The conditions are Boolean, so must be total.
946 // Look at the values.
947 ITE* ite(e->template cast<ITE>());
948 int sz(ite->size());
949 if(is_partial(ite->e_else()))
950 return false;
951 for(int ii = 0; ii < sz; ++ii) {
952 if(is_partial(ite->e_then(ii)))
953 return false;
954 }
955 return true;
956 }
957 case Expression::E_BINOP: {
958 BinOp* b(e->template cast<BinOp>());
959 // First, check if the op is itself partial.
960 // TODO: (Eventually) add a pass to determine whether we can exclude
961 // 0 from the domain of b->rhs().
962 if(b->op() == BOT_DIV || b->op() == BOT_IDIV || b->op() == BOT_MOD)
963 return true;
964 return is_partial(b->lhs()) || is_partial(b->rhs());
965 }
966 case Expression::E_UNOP:
967 return is_partial(e->template cast<UnOp>()->e());
968
969 case Expression::E_CALL: {
970 Call* call(e->template cast<Call>());
971 int sz = call->n_args();
972 // Check if any of its arguments are partial.
973 for(int ii = 0; ii < sz; ++ii) {
974 if(is_partial(call->arg(ii)))
975 return true;
976 }
977 // FIXME: Identify the relevant call body, recursively
978 // check for partiality.
979 // return false;
980 for(FunctionI* b : cg.fun_map.get_bodies(call)) {
981 // Boolean-typed values are always total
982 if(b->ti()->type().isbool())
983 continue;
984 if(!b->e())
985 return true;
986 }
987 return false;
988 }
989 case Expression::E_LET: {
990 Let* let(e->template cast<Let>());
991
992 // Check if any of the expressions are partial.
993 ASTExprVec<Expression> bindings(let->let());
994 for(Expression* item : bindings) {
995 if (VarDecl* vd = e->dyn_cast<VarDecl>()) {
996 if(vd->e()) {
997 // If both a domain and a definition are given,
998 // the domain might be constraining.
999 if (vd->ti()->domain())
1000 return true;
1001 if(is_partial(vd->e()))
1002 return true;
1003 }
1004 } else {
1005 // If there's some item that isn't a binding, it must be a constriant
1006 return true;
1007 }
1008 }
1009 return is_partial(let->in());
1010 }
1011 case Expression::E_ANON:
1012 case Expression::E_VARDECL:
1013 case Expression::E_TI:
1014 case Expression::E_TIID:
1015 throw InternalError("Bytecode generator encountered unexpected expression type.");
1016 }
1017 }
1018
1019 void reset_flags(Expression* e) {
1020 /*
1021 if(!e->isUnboxedVal()) {
1022 if(e->_flag_3) {
1023 e->_flag_3 = e->_flag_4 = 0;
1024 }
1025 }
1026 */
1027 }
1028
1029 CodeGen& cg;
1030
1031};
1032#endif
1033
1034ASTStSet CodeGen::scope(Expression* e) {
1035 // Is it already cached?
1036 auto it(_exp_scope.find(e));
1037 if (it != _exp_scope.end()) return (*it).second;
1038
1039 // Otherwise, dispatch on the type.
1040 ASTStSet r;
1041 switch (e->eid()) {
1042 case Expression::E_INTLIT:
1043 case Expression::E_FLOATLIT:
1044 case Expression::E_SETLIT:
1045 case Expression::E_BOOLLIT:
1046 case Expression::E_STRINGLIT:
1047 break;
1048 case Expression::E_ID: {
1049 Id* id(e->template cast<Id>());
1050 r.insert(id->v());
1051 break;
1052 }
1053 case Expression::E_ARRAYLIT: {
1054 ArrayLit* a(e->template cast<ArrayLit>());
1055 int sz(a->size());
1056 for (int ii = 0; ii < sz; ++ii) {
1057 ASTStSet rr(scope((*a)[ii]));
1058 r.insert(rr.begin(), rr.end());
1059 }
1060 break;
1061 }
1062 case Expression::E_ARRAYACCESS: {
1063 ArrayAccess* a(e->template cast<ArrayAccess>());
1064 r = scope(a->v());
1065
1066 ASTExprVec<Expression> idx(a->idx());
1067 int sz(idx.size());
1068 for (int ii = 0; ii < sz; ++ii) {
1069 ASTStSet rr(scope(idx[ii]));
1070 r.insert(rr.begin(), rr.end());
1071 }
1072 break;
1073 }
1074 case Expression::E_COMP: {
1075 // Work from the inner expression out.
1076 Comprehension* c(e->template cast<Comprehension>());
1077 r = scope(c->e());
1078 int sz = c->n_generators();
1079 for (int g = sz - 1; g >= 0; --g) {
1080 ASTStSet r_in(scope(c->in(g)));
1081
1082 if (c->where(g)) {
1083 ASTStSet r_where(scope(c->where(g)));
1084 r.insert(r_where.begin(), r_where.end());
1085 r.insert(r_in.begin(), r_in.end());
1086 }
1087
1088 // Now remove the variables that were bound.
1089 for (int d = 0; d < c->n_decls(g); ++d) {
1090 VarDecl* vd(c->decl(g, d));
1091 r.erase(vd->id()->str());
1092 }
1093 }
1094 break;
1095 }
1096 case Expression::E_ITE: {
1097 ITE* ite(e->template cast<ITE>());
1098 int sz(ite->size());
1099 r = scope(ite->e_else());
1100 for (int ii = 0; ii < sz; ++ii) {
1101 ASTStSet rr(scope(ite->e_if(ii)));
1102 r.insert(rr.begin(), rr.end());
1103 rr = scope(ite->e_then(ii));
1104 r.insert(rr.begin(), rr.end());
1105 }
1106 break;
1107 }
1108 case Expression::E_BINOP: {
1109 BinOp* b(e->template cast<BinOp>());
1110 r = scope(b->lhs());
1111 ASTStSet rr(scope(b->rhs()));
1112 r.insert(rr.begin(), rr.end());
1113 break;
1114 }
1115 case Expression::E_UNOP:
1116 r = scope(e->template cast<UnOp>()->e());
1117 break;
1118 case Expression::E_CALL: {
1119 Call* call(e->template cast<Call>());
1120 int sz = call->n_args();
1121 for (int ii = 0; ii < sz; ++ii) {
1122 ASTStSet rr(scope(call->arg(ii)));
1123 r.insert(rr.begin(), rr.end());
1124 }
1125 break;
1126 }
1127 case Expression::E_LET: {
1128 Let* let(e->template cast<Let>());
1129 ASTExprVec<Expression> bindings(let->let());
1130 int sz(bindings.size());
1131 r = scope(let->in());
1132 for (int ii = sz - 1; ii >= 0; --ii) {
1133 if (VarDecl* vd = bindings[ii]->dyn_cast<VarDecl>()) {
1134 r.erase(vd->id()->str());
1135 if (vd->e()) {
1136 ASTStSet r_d(scope(vd->e()));
1137 r.insert(r_d.begin(), r_d.end());
1138 }
1139 } else {
1140 ASTStSet r_e(scope(bindings[ii]));
1141 r.insert(r_e.begin(), r_e.end());
1142 }
1143 }
1144 break;
1145 }
1146 case Expression::E_ANON:
1147 case Expression::E_VARDECL:
1148 case Expression::E_TI:
1149 case Expression::E_TIID:
1150 throw InternalError("Bytecode generator encountered unexpected expression type.");
1151 }
1152
1153 _exp_scope.insert(std::make_pair(e, r));
1154 return r;
1155}
1156
1157CodeGen::Binding CodeGen::cache_lookup(Expression* e) { return env().cache_lookup(e, scope(e)); }
1158void CodeGen::cache_store(Expression* e, CodeGen::Binding l) { env().cache_store(e, scope(e), l); }
1159
1160void _debugcond(CG_Cond::T c) {
1161 CG_Cond::_T* p(c.get());
1162 if (c.sign()) std::cerr << "~";
1163 if (!p) {
1164 std::cerr << "T";
1165 } else {
1166 switch (p->kind()) {
1167 case CG_Cond::CC_Reg:
1168 std::cerr << "R" << p->reg[0].reg;
1169 break;
1170 case CG_Cond::CC_Call:
1171 std::cerr << "<Call>";
1172 break;
1173 case CG_Cond::CC_And:
1174 std::cerr << "(and";
1175 for (CG_Cond::T child : static_cast<CG_Cond::C_And*>(p)->children) {
1176 std::cerr << " ";
1177 _debugcond(child);
1178 }
1179 break;
1180 }
1181 }
1182}
1183void debugcond(CG_Cond::T c) {
1184 _debugcond(c);
1185 std::cerr << std::endl;
1186}
1187
1188int bind_cst(int x, CodeGen& cg, CG_Builder& frag) {
1189 CG::Binding b;
1190 if (cg.env().cache_lookup_cst(x, b)) return b.first;
1191 int r = GET_REG(cg);
1192 PUSH_INSTR(frag, BytecodeStream::IMMI, CG::i(x), CG::r(r));
1193 cg.env().cache_store_cst(x, std::make_pair(r, CG_Cond::ttt()));
1194 return r;
1195}
1196
1197// WARNING ON THE USE OF CG_Conds: register caching assumes that CG_Conds dont escape an
1198// aggregation context, and will be available on all paths. If the cond is forced conditionally
1199// (e.g. shortcutting), cg.push_env() should be called before the force() call, and cg.pop_env()
1200// called where control flow rejoins.
1201
1202// Given CG_Cond cond, collect the disjuncts having positive or negative values.
1203// Returns false if the conjunction is a contradiction.
1204bool collect_prod(std::vector<int>& pos, std::vector<int>& neg,
1205 std::vector<CG_Cond::C_And*>& delayed, CG_Cond::T cond, CodeGen& cg,
1206 CG_Builder& frag) {
1207 assert(cond.get());
1208 CG_Cond::_T* p(cond.get());
1209 bool sign(cond.sign());
1210
1211 if (p->reg[1 - sign].is_seen || p->reg[1 - sign].is_root) return false;
1212 if (p->reg[sign].is_seen || p->reg[sign].is_root) return true;
1213 p->reg[sign].is_seen = true;
1214
1215 if (p->reg[sign].has_reg()) {
1216 pos.push_back(p->reg[sign].reg);
1217 } else if (p->reg[1 - sign].has_reg()) {
1218 neg.push_back(p->reg[1 - sign].reg);
1219 } else if (p->kind() == CG_Cond::CC_And && !sign) {
1220 // Recursively collect the children.
1221 std::vector<CG_Cond::T>& children(static_cast<CG_Cond::C_And*>(p)->children);
1222 for (CG_Cond::T c : children) {
1223 if (!collect_prod(pos, neg, delayed, c, cg, frag)) return false;
1224 }
1225 } else if (p->kind() == CG_Cond::CC_And) {
1226 // How do we decide which way to compile the remaining conditions?
1227 delayed.push_back(static_cast<CG_Cond::C_And*>(p));
1228 } else {
1229 assert(p->kind() == CG_Cond::CC_Call);
1230 CG_Cond::C_Call* call(static_cast<CG_Cond::C_Call*>(p));
1231 std::vector<Type> ty(call->ty.begin() + 1, call->ty.end());
1232 auto fun = find_call_fun(cg, call->ident, call->ty[0], ty, call->m);
1233 PUSH_INSTR(frag, BytecodeStream::CALL, std::get<1>(fun), std::get<0>(fun),
1234 CG::i((!std::get<2>(fun)) && call->cse), call->params);
1235 int r = GET_REG(cg);
1236 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r));
1237 if (BytecodeProc::is_neg(call->m) != BytecodeProc::is_neg(std::get<1>(fun))) {
1238 if (call->ty[0].ispar()) {
1239 PUSH_INSTR(frag, BytecodeStream::NOT, CG::r(r), CG::r(r));
1240 } else {
1241 auto fun =
1242 find_call_fun(cg, {"op_not"}, Type::varbool(), {Type::varbool()}, BytecodeProc::FUN);
1243 assert(std::get<1>(fun) == BytecodeProc::FUN);
1244 PUSH_INSTR(frag, BytecodeStream::CALL, BytecodeProc::FUN, std::get<0>(fun),
1245 CG::i(!std::get<2>(fun)), CG::r(r));
1246 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r));
1247 }
1248 }
1249 if (!sign)
1250 pos.push_back(r);
1251 else
1252 neg.push_back(r);
1253 }
1254 return true;
1255}
1256
1257// Given CG_Cond cond, collect the disjuncts having positive or negative values.
1258// Returns true if the disjunction is a tautology.
1259bool collect_disj(std::vector<int>& pos, std::vector<int>& neg,
1260 std::vector<CG_Cond::C_And*>& delayed, CG_Cond::T cond, CodeGen& cg,
1261 CG_Builder& frag) {
1262 assert(cond.get());
1263 CG_Cond::_T* p(cond.get());
1264 bool sign(cond.sign());
1265
1266 if (p->reg[1 - sign].is_seen || p->reg[sign].is_root) return true;
1267 if (p->reg[sign].is_seen || p->reg[1 - sign].is_root) return false;
1268 p->reg[sign].is_seen = true;
1269
1270 if (p->reg[sign].has_reg()) {
1271 pos.push_back(p->reg[sign].reg);
1272 } else if (p->reg[1 - sign].has_reg()) {
1273 neg.push_back(p->reg[1 - sign].reg);
1274 } else if (p->kind() == CG_Cond::CC_And && sign) {
1275 // Recursively collect the children.
1276 std::vector<CG_Cond::T>& children(static_cast<CG_Cond::C_And*>(p)->children);
1277 for (CG_Cond::T c : children) {
1278 if (collect_disj(pos, neg, delayed, ~c, cg, frag)) return true;
1279 }
1280 } else if (p->kind() == CG_Cond::CC_And) {
1281 delayed.push_back(static_cast<CG_Cond::C_And*>(p));
1282 } else {
1283 CG_Cond::C_Call* call(static_cast<CG_Cond::C_Call*>(p));
1284 std::vector<Type> ty(call->ty.begin() + 1, call->ty.end());
1285 auto fun = find_call_fun(cg, call->ident, call->ty[0], ty, call->m);
1286 PUSH_INSTR(frag, BytecodeStream::CALL, std::get<1>(fun), std::get<0>(fun),
1287 CG::i((!std::get<2>(fun)) && call->cse), call->params);
1288 int r = GET_REG(cg);
1289 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r));
1290 if (BytecodeProc::is_neg(call->m) != BytecodeProc::is_neg(std::get<1>(fun))) {
1291 if (call->ty[0].ispar()) {
1292 PUSH_INSTR(frag, BytecodeStream::NOT, CG::r(r), CG::r(r));
1293 } else {
1294 auto fun =
1295 find_call_fun(cg, {"op_not"}, Type::varbool(), {Type::varbool()}, BytecodeProc::FUN);
1296 assert(std::get<1>(fun) == BytecodeProc::FUN);
1297 PUSH_INSTR(frag, BytecodeStream::CALL, BytecodeProc::FUN, std::get<0>(fun),
1298 CG::i(!std::get<2>(fun)), CG::r(r));
1299 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r));
1300 }
1301 }
1302 if (!sign)
1303 pos.push_back(r);
1304 else
1305 neg.push_back(r);
1306 }
1307 return false;
1308}
1309
1310std::pair<int, bool> _force_cond(CG_Cond::T cond, CodeGen& cg, CG_Builder& frag);
1311
1312void collect_and_leaves(std::vector<CG_Cond::T>& par_leaves, std::vector<CG_Cond::T>& var_leaves,
1313 CG_Cond::T child, CodeGen& cg, CG_Builder& frag) {
1314 assert(child.get());
1315 CG_Cond::_T* p(child.get());
1316 bool sign(child.sign());
1317 auto push = [&](CG_Cond::T r, bool is_par) {
1318 if (is_par) {
1319 par_leaves.push_back(r);
1320 } else {
1321 var_leaves.push_back(r);
1322 }
1323 };
1324
1325 if (p->reg[sign].has_reg()) {
1326 push(child, p->reg[sign].is_par);
1327 return;
1328 }
1329 if (p->reg[1 - sign].has_reg()) {
1330 push(child, p->reg[1 - sign].is_par);
1331 } else if (p->kind() == CG_Cond::CC_And && !sign) {
1332 std::vector<CG_Cond::T>& children(static_cast<CG_Cond::C_And*>(p)->children);
1333 for (CG_Cond::T c : children) {
1334 collect_and_leaves(par_leaves, var_leaves, c, cg, frag);
1335 }
1336 } else {
1337 push(child, /* Check if this is par. */ false);
1338 }
1339}
1340void collect_or_leaves(std::vector<CG_Cond::T>& par_leaves, std::vector<CG_Cond::T>& var_leaves,
1341 CG_Cond::T child, CodeGen& cg, CG_Builder& frag) {
1342 assert(child.get());
1343 CG_Cond::_T* p(child.get());
1344 bool sign(child.sign());
1345 auto push = [&](CG_Cond::T r, bool is_par) {
1346 if (is_par) {
1347 par_leaves.push_back(r);
1348 } else {
1349 var_leaves.push_back(r);
1350 }
1351 };
1352
1353 if (p->reg[1 - sign].has_reg()) {
1354 push(~child, p->reg[1 - sign].is_par);
1355 return;
1356 }
1357 if (p->reg[sign].has_reg()) {
1358 push(~child, p->reg[sign].is_par);
1359 } else if (p->kind() == CG_Cond::CC_And && !sign) {
1360 std::vector<CG_Cond::T>& children(static_cast<CG_Cond::C_And*>(p)->children);
1361 for (CG_Cond::T c : children) {
1362 collect_or_leaves(par_leaves, var_leaves, c, cg, frag);
1363 }
1364 } else {
1365 push(~child, /* Check if this is par. */ false);
1366 }
1367}
1368
1369void force_and_leaves(std::vector<int>& var_leaves, std::vector<int>& par_leaves, CG_Cond::T child,
1370 CodeGen& cg, CG_Builder& frag) {
1371 assert(child.get());
1372 CG_Cond::_T* p(child.get());
1373 bool sign(child.sign());
1374 auto push = [&](int r, bool is_par) {
1375 if (is_par) {
1376 par_leaves.push_back(r);
1377 } else {
1378 var_leaves.push_back(r);
1379 }
1380 };
1381 if (p->reg[sign].has_reg()) {
1382 push(p->reg[sign].reg, p->reg[sign].is_par);
1383 return;
1384 }
1385 cg.env().record_cached_cond(child);
1386 if (p->reg[1 - sign].has_reg()) {
1387 // Create the negation
1388 int r(GET_REG(cg));
1389 if (p->reg[1 - sign].is_par) {
1390 PUSH_INSTR(frag, BytecodeStream::NOT, CG::r(p->reg[1 - sign].reg), CG::r(r));
1391 } else {
1392 GCLock lock;
1393 auto fun =
1394 find_call_fun(cg, {"op_not"}, Type::varbool(), {Type::varbool()}, BytecodeProc::FUN);
1395 assert(std::get<1>(fun) == BytecodeProc::FUN);
1396 PUSH_INSTR(frag, BytecodeStream::CALL, BytecodeProc::FUN, std::get<0>(fun),
1397 CG::i(!std::get<2>(fun)), CG::r(p->reg[1 - sign].reg));
1398 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r));
1399 }
1400 p->reg[sign] = CG_Cond::cond_reg(r, p->reg[1 - sign].is_par);
1401 push(p->reg[sign].reg, p->reg[sign].is_par);
1402 } else if (p->kind() == CG_Cond::CC_And && !sign) {
1403 std::vector<CG_Cond::T>& children(static_cast<CG_Cond::C_And*>(p)->children);
1404 for (CG_Cond::T c : children) {
1405 force_and_leaves(var_leaves, par_leaves, c, cg, frag);
1406 }
1407 } else {
1408 auto forced = _force_cond(child, cg, frag);
1409 push(forced.first, forced.second);
1410 }
1411}
1412
1413// Pushing the _negation_ of child.
1414void force_or_leaves(std::vector<int>& var_leaves, std::vector<int>& par_leaves, CG_Cond::T child,
1415 CodeGen& cg, CG_Builder& frag) {
1416 assert(child.get());
1417 CG_Cond::_T* p(child.get());
1418 bool sign(child.sign());
1419 auto push = [&](int r, bool is_par) {
1420 if (is_par) {
1421 par_leaves.push_back(r);
1422 } else {
1423 var_leaves.push_back(r);
1424 }
1425 };
1426 if (p->reg[1 - sign].has_reg()) {
1427 push(p->reg[1 - sign].reg, p->reg[1 - sign].is_par);
1428 return;
1429 }
1430 cg.env().record_cached_cond(~child);
1431 if (p->reg[sign].has_reg()) {
1432 // Create the negation
1433 int r(GET_REG(cg));
1434 if (p->reg[sign].is_par) {
1435 PUSH_INSTR(frag, BytecodeStream::NOT, CG::r(p->reg[sign].reg), CG::r(r));
1436 } else {
1437 GCLock lock;
1438 auto fun =
1439 find_call_fun(cg, {"op_not"}, Type::varbool(), {Type::varbool()}, BytecodeProc::FUN);
1440 assert(std::get<1>(fun) == BytecodeProc::FUN);
1441 PUSH_INSTR(frag, BytecodeStream::CALL, BytecodeProc::FUN, std::get<0>(fun),
1442 CG::i(!std::get<2>(fun)), CG::r(p->reg[sign].reg));
1443 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r));
1444 }
1445 p->reg[1 - sign] = CG_Cond::cond_reg(r, p->reg[sign].is_par);
1446 push(p->reg[1 - sign].reg, p->reg[1 - sign].is_par);
1447 } else if (p->kind() == CG_Cond::CC_And && !sign) {
1448 std::vector<CG_Cond::T>& children(static_cast<CG_Cond::C_And*>(p)->children);
1449 for (CG_Cond::T c : children) {
1450 force_or_leaves(var_leaves, par_leaves, c, cg, frag);
1451 }
1452 } else {
1453 auto forced = _force_cond(~child, cg, frag);
1454 push(forced.first, forced.second);
1455 }
1456}
1457
1458std::pair<int, bool> _force_cond(CG_Cond::T cond, CodeGen& cg, CG_Builder& frag) {
1459 CG_Cond::_T* p(cond.get());
1460 bool negated(cond.sign());
1461 if (!p) {
1462 // Either true or false.
1463 // return CG::locate_immi(1 - cond.sign(), cg, frag);
1464 return {bind_cst(1 - cond.sign(), cg, frag), true};
1465 }
1466 cg.env().record_cached_cond(cond);
1467 if (p->kind() == CG_Cond::CC_Reg) {
1468 throw InternalError("_force_cond called on value in register.");
1469 } else if (p->kind() == CG_Cond::CC_Call) {
1470 CG_Cond::C_Call* call(static_cast<CG_Cond::C_Call*>(p));
1471 std::vector<Type> ty(call->ty.begin() + 1, call->ty.end());
1472 int r;
1473 Mode m(call->m);
1474 if (m.strength() != CG::Mode::Root) {
1475 Mode call_m(m.strength(), negated);
1476 auto fun = find_call_fun(cg, call->ident, call->ty[0], ty, call->m);
1477 PUSH_INSTR(frag, BytecodeStream::CALL, std::get<1>(fun), std::get<0>(fun),
1478 CG::i((!std::get<2>(fun)) && call->cse), call->params);
1479 r = GET_REG(cg);
1480 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r));
1481 if (BytecodeProc::is_neg(call->m) != BytecodeProc::is_neg(std::get<1>(fun))) {
1482 if (call->ty[0].ispar()) {
1483 PUSH_INSTR(frag, BytecodeStream::NOT, CG::r(r), CG::r(r));
1484 } else {
1485 auto fun =
1486 find_call_fun(cg, {"op_not"}, Type::varbool(), {Type::varbool()}, BytecodeProc::FUN);
1487 assert(std::get<1>(fun) == BytecodeProc::FUN);
1488 PUSH_INSTR(frag, BytecodeStream::CALL, BytecodeProc::FUN, std::get<0>(fun),
1489 CG::i(!std::get<2>(fun)), CG::r(r));
1490 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r));
1491 }
1492 }
1493 return {r, call->ty[0].ispar()};
1494 }
1495 Mode call_m(m.strength(), negated);
1496 assert(m == call_m);
1497 auto fun = find_call_fun(cg, call->ident, call->ty[0], ty, call->m);
1498 if (call_m == std::get<1>(fun)) {
1499 PUSH_INSTR(frag, BytecodeStream::CALL, call_m, std::get<0>(fun),
1500 CG::i((!std::get<2>(fun)) && call->cse), call->params);
1501 } else {
1502 assert(std::get<1>(fun) == BytecodeProc::FUN);
1503 std::cerr << "Warning: emitting reification for " << call->ident
1504 << " because no ROOT_NEG version is available\n";
1505 PUSH_INSTR(frag, BytecodeStream::CALL, std::get<1>(fun), std::get<0>(fun),
1506 CG::i(!std::get<2>(fun)), call->params);
1507 r = GET_REG(cg);
1508 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r));
1509 if (BytecodeProc::is_neg(call->m) != BytecodeProc::is_neg(std::get<1>(fun))) {
1510 if (call->ty[0].ispar()) {
1511 PUSH_INSTR(frag, BytecodeStream::NOT, CG::r(r), CG::r(r));
1512 } else {
1513 auto fun =
1514 find_call_fun(cg, {"op_not"}, Type::varbool(), {Type::varbool()}, BytecodeProc::FUN);
1515 assert(std::get<1>(fun) == BytecodeProc::FUN);
1516 PUSH_INSTR(frag, BytecodeStream::CALL, BytecodeProc::FUN, std::get<0>(fun),
1517 CG::i(!std::get<2>(fun)), CG::r(r));
1518 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r));
1519 }
1520 }
1521 PUSH_INSTR(frag, BytecodeStream::POST, CG::r(r));
1522 }
1523 return {bind_cst(1, cg, frag), true};
1524 } else if (p->kind() == CG_Cond::CC_And && !cond.sign()) {
1525#ifndef MZNC_COLLECT_LEAVES
1526 std::vector<int> var_leaves;
1527 std::vector<int> par_leaves;
1528 int r = GET_REG(cg);
1529 // I don't think these are necessary
1530 force_and_leaves(var_leaves, par_leaves, cond, cg, frag);
1531 if (var_leaves.empty()) {
1532 PUSH_INSTR(frag, BytecodeStream::MOV, CG::r(par_leaves[0]), CG::r(r));
1533 for (int i = 1; i < par_leaves.size(); ++i) {
1534 PUSH_INSTR(frag, BytecodeStream::AND, CG::r(r), CG::r(par_leaves[i]), CG::r(r));
1535 }
1536 } else {
1537 OPEN_AND(cg, frag);
1538 for (int r_c : par_leaves) {
1539 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(r_c));
1540 }
1541 for (int r_c : var_leaves) {
1542 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(r_c));
1543 }
1544 CLOSE_AGG(cg, frag);
1545 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r));
1546 }
1547 return {r, var_leaves.empty()};
1548#else
1549 std::vector<CG_Cond::T> par_leaves;
1550 std::vector<CG_Cond::T> var_leaves;
1551 collect_and_leaves(par_leaves, var_leaves, cond, cg, frag);
1552
1553 // If we had a conjunction, there should be at least two leaves.
1554 assert(var_leaves.size() + par_leaves.size() > 1);
1555
1556 // If there is at least one par child, we're going to do shortcutting
1557 // -- so we need a jump, and to push a fresh env.
1558 int r = GET_REG(cg);
1559 int lblE = 0xdeadbeef;
1560 if (par_leaves.size() > 0) {
1561 lblE = GET_LABEL(cg);
1562 cg.env_push();
1563
1564 PUSH_INSTR(frag, BytecodeStream::IMMI, CG::i(0), CG::r(r));
1565 for (int ii = 0; ii < par_leaves.size() - 1; ii++) {
1566 CG_Cond::T c(par_leaves[ii]);
1567 int r_c = CG::force(c, BytecodeProc::FUN, cg, frag);
1568 PUSH_INSTR(frag, BytecodeStream::JMPIFNOT, CG::r(r_c), CG::l(lblE));
1569 }
1570 CG_Cond::T c(par_leaves.back());
1571 int r_c = CG::force(c, BytecodeProc::FUN, cg, frag);
1572 if (var_leaves.size() > 0) {
1573 PUSH_INSTR(frag, BytecodeStream::JMPIFNOT, CG::r(r_c), CG::l(lblE));
1574 } else {
1575 PUSH_INSTR(frag, BytecodeStream::MOV, CG::r(r_c), CG::r(r));
1576 }
1577 }
1578 // Excludes the 0 case, because it's just been handled.
1579 if (var_leaves.size() == 1) {
1580 // Exactly one var. Don't open a context;
1581 // we return either the result register
1582 // or the forced cond.
1583 int r_c = CG::force(var_leaves[0], BytecodeProc::FUN, cg, frag);
1584 PUSH_INSTR(frag, BytecodeStream::MOV, CG::r(r_c), CG::r(r));
1585 } else if (var_leaves.size() > 1) {
1586 // In this case, we need to open a context.
1587 OPEN_AND(cg, frag);
1588 for (CG_Cond::T c : var_leaves) {
1589 int r_c = CG::force(c, BytecodeProc::FUN, cg, frag);
1590 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(r_c));
1591 }
1592 CLOSE_AGG(cg, frag);
1593 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r));
1594 }
1595 if (par_leaves.size() > 0) { // We did some shortcutting.
1596 PUSH_LABEL(frag, lblE);
1597 cg.env_pop();
1598 }
1599 return {r, var_leaves.empty()};
1600#endif
1601 } else {
1602 assert(p->kind() == CG_Cond::CC_And && cond.sign());
1603#ifndef MZNC_COLLECT_LEAVES
1604 std::vector<int> var_leaves;
1605 std::vector<int> par_leaves;
1606 int r = GET_REG(cg);
1607 // I don't think these are necessary
1608 force_or_leaves(var_leaves, par_leaves, ~cond, cg, frag);
1609 if (var_leaves.empty()) {
1610 PUSH_INSTR(frag, BytecodeStream::MOV, CG::r(par_leaves[0]), CG::r(r));
1611 for (int i = 1; i < par_leaves.size(); ++i) {
1612 PUSH_INSTR(frag, BytecodeStream::OR, CG::r(r), CG::r(par_leaves[i]), CG::r(r));
1613 }
1614 } else {
1615 OPEN_OR(cg, frag);
1616 for (int r_c : par_leaves) {
1617 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(r_c));
1618 }
1619 for (int r_c : var_leaves) {
1620 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(r_c));
1621 }
1622 CLOSE_AGG(cg, frag);
1623 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r));
1624 }
1625 return {r, var_leaves.empty()};
1626#else
1627 std::vector<CG_Cond::T> par_leaves;
1628 std::vector<CG_Cond::T> var_leaves;
1629 collect_or_leaves(par_leaves, var_leaves, ~cond, cg, frag);
1630
1631 // If we had a conjunction, there should be at least two leaves.
1632 assert(var_leaves.size() + par_leaves.size() > 1);
1633
1634 // If there is at least one par child, we're going to do shortcutting
1635 // -- so we need a jump, and to push a fresh env.
1636 int r = GET_REG(cg);
1637 int lblE = 0xdeadbeef;
1638 if (par_leaves.size() > 0) {
1639 lblE = GET_LABEL(cg);
1640 cg.env_push();
1641 PUSH_INSTR(frag, BytecodeStream::IMMI, CG::i(1), CG::r(r));
1642
1643 for (int ii = 0; ii < par_leaves.size() - 1; ii++) {
1644 CG_Cond::T c(par_leaves[ii]);
1645 int r_c = CG::force(c, BytecodeProc::FUN, cg, frag);
1646 PUSH_INSTR(frag, BytecodeStream::JMPIF, CG::r(r_c), CG::l(lblE));
1647 }
1648 CG_Cond::T c(par_leaves.back());
1649 int r_c = CG::force(c, BytecodeProc::FUN, cg, frag);
1650 if (var_leaves.size() > 0) {
1651 PUSH_INSTR(frag, BytecodeStream::JMPIF, CG::r(r_c), CG::l(lblE));
1652 } else {
1653 PUSH_INSTR(frag, BytecodeStream::MOV, CG::r(r_c), CG::r(r));
1654 }
1655 }
1656 // Excludes the 0 case, because it's just been handled.
1657 if (var_leaves.size() == 1) {
1658 // Exactly one var. Don't open a context;
1659 // we return either the result register
1660 // or the forced cond.
1661 int r_c = CG::force(var_leaves[0], BytecodeProc::FUN, cg, frag);
1662 PUSH_INSTR(frag, BytecodeStream::MOV, CG::r(r_c), CG::r(r));
1663 } else if (var_leaves.size() > 1) {
1664 // In this case, we need to open a context.
1665 OPEN_OR(cg, frag);
1666 for (CG_Cond::T c : var_leaves) {
1667 int r_c = CG::force(c, BytecodeProc::FUN, cg, frag);
1668 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(r_c));
1669 }
1670 CLOSE_AGG(cg, frag);
1671 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r));
1672 }
1673 if (par_leaves.size() > 0) { // We did some shortcutting.
1674 PUSH_LABEL(frag, lblE);
1675 cg.env_pop();
1676 }
1677 return {r, var_leaves.empty()};
1678#endif
1679 }
1680}
1681int CG::force(CG_Cond::T _cond, Mode ctx, CodeGen& cg, CG_Builder& frag) {
1682 GCLock lock;
1683 // Negate condition if forced in negated context
1684 CG_Cond::T cond = ctx.is_neg() ? ~_cond : _cond;
1685 // Check if the condition is already forced.
1686 CG_Cond::_T* p(cond.get());
1687 bool sign(cond.sign());
1688 if (!p) {
1689 return bind_cst(!sign, cg, frag);
1690 }
1691 if (p->reg[sign].has_reg()) {
1692 return p->reg[sign].reg;
1693 }
1694 if (p->reg[1 - sign].has_reg()) {
1695 // Emit the negation
1696 int r(GET_REG(cg));
1697 if (p->reg[1 - sign].is_par) {
1698 PUSH_INSTR(frag, BytecodeStream::NOT, CG::r(p->reg[1 - sign].reg), CG::r(r));
1699 } else {
1700 auto fun =
1701 find_call_fun(cg, {"op_not"}, Type::varbool(), {Type::varbool()}, BytecodeProc::FUN);
1702 assert(std::get<1>(fun) == BytecodeProc::FUN);
1703 PUSH_INSTR(frag, BytecodeStream::CALL, BytecodeProc::FUN, std::get<0>(fun),
1704 CG::i(!std::get<2>(fun)), CG::r(p->reg[1 - sign].reg));
1705 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r));
1706 }
1707 p->reg[sign] = CG_Cond::cond_reg(r, p->reg[1 - sign].is_par);
1708 return r;
1709 }
1710 auto forced = _force_cond(cond, cg, frag);
1711 p->reg[sign] = CG_Cond::cond_reg(forced.first, forced.second);
1712 return forced.first;
1713}
1714
1715CG::Binding CG::force_or_bind(Expression* e, Mode ctx, CodeGen& cg, CG_Builder& frag) {
1716 if (e->type().isbool()) {
1717 return {CG::force(CG::compile(e, cg, frag), ctx, cg, frag), CG_Cond::ttt()};
1718 }
1719 return CG::bind(e, cg, frag);
1720}
1721
1722int CG::force_or_bind(Expression* e, Mode ctx, std::vector<CG_Cond::T>& cond, CodeGen& cg,
1723 CG_Builder& frag) {
1724 if (e->type().isbool()) {
1725 return CG::force(CG::compile(e, cg, frag), ctx, cg, frag);
1726 } else {
1727 CG::Binding b(CG::bind(e, cg, frag));
1728 if (b.second.get()) {
1729 cond.push_back(b.second);
1730 }
1731 return b.first;
1732 }
1733}
1734
1735class EnvInit : public ItemVisitor {
1736private:
1737 friend class ItemIter<EnvInit>;
1738
1739 EnvInit(CodeGen& _cg, Model& _m) : cg(_cg), m(_m) {}
1740
1741 /// Enter model
1742 bool enterModel(Model* m) { return true; }
1743 /// Enter item
1744 bool enter(Item* m) { return true; }
1745 /// Visit variable declaration
1746 void vVarDeclI(VarDeclI* vdi) {
1747 VarDecl* vd(vdi->e());
1748 if (!vd->type().isann()) {
1749 if (vd->type().ispar()) {
1750 if (!vd->e()) {
1751 // cg.env().bind(vd->id()->v(), Loc::global(cg.num_globals));
1752 int g = cg.add_global(vd, true);
1753 }
1754 } else {
1755 // If it's a var with a body, feed it into the mode analyser.
1756 // TODO: Because mode analysis is not interprocedural, we have to
1757 // assume global params may be used in any context.
1758 modes.def(vd, BytecodeProc::ROOT);
1759 modes.use(vd, BytecodeProc::FUN);
1760 }
1761 }
1762 }
1763 void vConstraintI(ConstraintI* c) { modes.use(c->e(), BytecodeProc::ROOT); }
1764 /// Visit assign item
1765 void vAssignI(AssignI* ass) {}
1766
1767 void vFunctionI(FunctionI* f) { cg.register_function(f); }
1768
1769 void vSolveI(SolveI* si) {
1770 GCLock lock;
1771 if (si->st() == SolveI::ST_SAT) {
1772 return;
1773 }
1774 ASTString ident("solve_this");
1775 int mode;
1776 Expression* objective;
1777 switch (si->st()) {
1778 case SolveI::ST_SAT:
1779 mode = 0;
1780 objective = IntLit::a(0);
1781 break;
1782 case SolveI::ST_MIN:
1783 mode = 1;
1784 objective = si->e();
1785 break;
1786 case SolveI::ST_MAX:
1787 mode = 2;
1788 objective = si->e();
1789 break;
1790 }
1791 Expression* search_a;
1792 int search_var = 0;
1793 int search_val = 0;
1794 Call* c;
1795 if (Call* ann = si->ann().getCall(ASTString("int_search"))) {
1796 search_a = ann->arg(0);
1797 Id* varsel = ann->arg(1)->cast<Id>();
1798 if (varsel->idn() == -1 && varsel->v() == ASTString("input_order")) {
1799 search_var = 1;
1800 } else if (varsel->idn() == -1 && varsel->v() == ASTString("first_fail")) {
1801 search_var = 2;
1802 }
1803 Id* valsel = ann->arg(2)->cast<Id>();
1804 if (valsel->idn() == -1 && valsel->v() == ASTString("indomain_min")) {
1805 search_val = 1;
1806 } else if (valsel->idn() == -1 && valsel->v() == ASTString("indomain_max")) {
1807 search_val = 2;
1808 }
1809 c = new Call(
1810 si->loc(), ident,
1811 {IntLit::a(mode), objective, search_a, IntLit::a(search_var), IntLit::a(search_val)});
1812 } else {
1813 c = new Call(si->loc(), ident, {IntLit::a(mode), objective});
1814 }
1815 c->type(Type::varbool());
1816 m.addItem(new ConstraintI(Location().introduce(), c));
1817 }
1818
1819 CodeGen& cg;
1820 Model& m;
1821 ModeAnalysis modes;
1822
1823public:
1824 static void run(CodeGen& cg, Model* m) {
1825 EnvInit eb(cg, *m);
1826 iterItems(eb, m);
1827 cg.mode_map = std::move(eb.modes.extract());
1828 }
1829};
1830
1831struct ShowVal {
1832 ShowVal(CodeGen& _cg, CG_Value _v) : cg(_cg), v(_v) {}
1833
1834 CodeGen& cg;
1835 CG_Value v;
1836};
1837std::ostream& operator<<(std::ostream& o, ShowVal s) {
1838 switch (s.v.kind) {
1839 case CG_Value::V_Immi:
1840 o << s.v.value;
1841 break;
1842 case CG_Value::V_Global:
1843 o << s.v.value;
1844 break;
1845 case CG_Value::V_Reg:
1846 o << "R" << s.v.value;
1847 break;
1848 case CG_Value::V_Proc:
1849 o << "p" << s.v.value;
1850 break;
1851 case CG_Value::V_Label:
1852 o << "l" << s.v.value;
1853 }
1854 return o;
1855}
1856
1857template <class O>
1858void show_frag(O& out, CodeGen& cg, std::vector<CG_Instr>& frag) {
1859 auto show = [&cg](CG_Value v) { return ShowVal(cg, v); };
1860
1861 int num_agg = 0;
1862 for (CG_Instr& i : frag) {
1863 auto op(static_cast<BytecodeStream::Instr>(i.tag >> 1));
1864 if (op == BytecodeStream::CLOSE_AGGREGATION) {
1865 num_agg--;
1866 }
1867 for (int j = 0; j < num_agg; ++j) {
1868 out << " ";
1869 }
1870 if (i.tag & 1) {
1871 out << "l" << (i.tag >> 1) << ": ";
1872 continue;
1873 }
1874
1875 out << instr_name(op);
1876 switch (op) {
1877 case BytecodeStream::OPEN_AGGREGATION:
1878 out << " " << agg_name((AggregationCtx::Symbol)i.params[0].value);
1879 num_agg++;
1880 break;
1881 case BytecodeStream::BUILTIN: {
1882 CG_ProcID p(CG_ProcID::of_val(i.params[0]));
1883 assert(p.is_builtin());
1884 out << " " << cg._builtins[p.id()].first;
1885 for (int ii = 1; ii < i.params.size(); ++ii) {
1886 out << " " << show(i.params[ii]);
1887 }
1888 break;
1889 }
1890 case BytecodeStream::CALL: {
1891 // Mode
1892 out << " " << mode_name((BytecodeProc::Mode)i.params[0].value);
1893 // Procedure
1894 CG_ProcID p(CG_ProcID::of_val(i.params[1]));
1895 if (p.is_builtin()) {
1896 out << " " << cg._builtins[p.id()].first;
1897 } else {
1898 out << " " << cg.bytecode[p.id()].ident;
1899 }
1900 // CSE flag
1901 out << " " << show(i.params[2]);
1902 // Arguments
1903 for (int ii = 3; ii < i.params.size(); ++ii) {
1904 out << " " << show(i.params[ii]);
1905 }
1906 break;
1907 }
1908 case BytecodeStream::TCALL: {
1909 // Mode
1910 out << " " << mode_name((BytecodeProc::Mode)i.params[0].value);
1911 // Procedure
1912 CG_ProcID p(CG_ProcID::of_val(i.params[1]));
1913 if (p.is_builtin()) {
1914 out << " " << cg._builtins[p.id()].first;
1915 } else {
1916 out << " " << cg.bytecode[p.id()].ident;
1917 }
1918 // CSE flag
1919 out << " " << show(i.params[2]);
1920 break;
1921 }
1922 default:
1923 for (CG_Value p : i.params) out << " " << show(p);
1924 }
1925 out << std::endl;
1926 }
1927}
1928
1929template <class O>
1930void show(O& out, CodeGen& cg) {
1931 {
1932 GCLock lock;
1933 Model m;
1934 for (auto g : cg.globals_env) {
1935 if (g.second.second) {
1936 TypeInst* ti = g.first->ti();
1937 // TODO: This removes information from the origin model. Could be reverted after printing
1938 if (ti->isarray()) {
1939 std::vector<TypeInst*> ranges(ti->ranges().size());
1940 for (int i = 0; i < ranges.size(); ++i) {
1941 ranges[i] = new TypeInst(Location().introduce(), Type::parint());
1942 }
1943 auto nti = new TypeInst(Location().introduce(), ti->type(), ranges);
1944 g.first->ti(nti);
1945 } else if (ti->domain()) {
1946 auto nti = new TypeInst(Location().introduce(), ti->type());
1947 g.first->ti(nti);
1948 }
1949 g.first->ann().add(new Call(Location().introduce(), constants().ann.global_register,
1950 {IntLit::a(g.second.first)}));
1951 m.addItem(new VarDeclI(Location().introduce(), g.first));
1952 }
1953 }
1954 for (auto fun : cg.req_solver_predicates) {
1955 m.addItem(fun);
1956 }
1957 MiniZinc::Printer p(out, 0);
1958 p.print(&m);
1959 }
1960 out << "@@@@@@@@@@" << std::endl;
1961 for (auto b : cg._builtins) {
1962 out << ":" << b.first << ": " << b.second << std::endl;
1963 }
1964 for (auto& p : cg.bytecode) {
1965 for (BytecodeProc::Mode m : p) {
1966 out << ":" << p.ident << ":" << mode_name(m) << " " << p.arity << std::endl;
1967 show_frag(out, cg, p.body(m));
1968 }
1969 }
1970}
1971
1972/*
1973void post_cond(CodeGen& cg, CG_Builder& frag, CG_Cond::T cond) {
1974 if(!cond.get()) {
1975 assert(!cond.sign());
1976 return;
1977 }
1978
1979 std::vector<int> leaves;
1980 force_and_leaves(leaves, cond, cg, frag);
1981 for(int r_c : leaves)
1982 PUSH_INSTR(frag, BytecodeStream::POST, CG::r(r_c));
1983}
1984*/
1985void post_cond(CodeGen& cg, CG_Builder& frag, CG_Cond::T cond) {
1986 GCLock lock;
1987 if (!cond.get()) {
1988 if (cond.sign()) PUSH_INSTR(frag, BytecodeStream::POST, CG::r(bind_cst(0, cg, frag)));
1989 return;
1990 }
1991 CG_Cond::_T* p(cond.get());
1992 bool sign(cond.sign());
1993 if (p->reg[sign].is_root) return;
1994 if (p->reg[1 - sign].is_root) {
1995 PUSH_INSTR(frag, BytecodeStream::POST, CG::r(bind_cst(0, cg, frag)));
1996 return;
1997 }
1998
1999 if (p->reg[sign].has_reg()) {
2000 PUSH_INSTR(frag, BytecodeStream::POST, CG::r(p->reg[sign].reg));
2001 } else if (p->reg[1 - sign].has_reg()) {
2002 int r(GET_REG(cg));
2003 if (p->reg[1 - sign].is_par) {
2004 PUSH_INSTR(frag, BytecodeStream::NOT, CG::r(p->reg[1 - sign].reg), CG::r(r));
2005 } else {
2006 auto fun =
2007 find_call_fun(cg, {"op_not"}, Type::varbool(), {Type::varbool()}, BytecodeProc::FUN);
2008 assert(std::get<1>(fun) == BytecodeProc::FUN);
2009 PUSH_INSTR(frag, BytecodeStream::CALL, BytecodeProc::FUN, std::get<0>(fun),
2010 CG::i(!std::get<2>(fun)), CG::r(p->reg[1 - sign].reg));
2011 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r));
2012 }
2013 PUSH_INSTR(frag, BytecodeStream::POST, CG::r(r));
2014 p->reg[sign] = CG_Cond::cond_reg(r, p->reg[1 - sign].is_par);
2015 } else if (p->kind() == CG_Cond::CC_Call) {
2016 CG_Cond::C_Call* call(static_cast<CG_Cond::C_Call*>(p));
2017 CG::Mode call_m(CG::Mode::Root, sign);
2018 std::vector<Type> ty(call->ty.begin() + 1, call->ty.end());
2019 auto fun = find_call_fun(cg, call->ident, call->ty[0], ty, call_m);
2020 if (call_m == std::get<1>(fun)) {
2021 PUSH_INSTR(frag, BytecodeStream::CALL, call_m, std::get<0>(fun),
2022 CG::i((!std::get<2>(fun)) && call->cse), call->params);
2023 } else {
2024 assert(std::get<1>(fun) == BytecodeProc::FUN);
2025 std::cerr << "Warning: emitting reification for " << call->ident
2026 << " because no ROOT_NEG version is available\n";
2027 PUSH_INSTR(frag, BytecodeStream::CALL, std::get<1>(fun), std::get<0>(fun),
2028 CG::i((!std::get<2>(fun)) && call->cse), call->params);
2029 int r = GET_REG(cg);
2030 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r));
2031 if (BytecodeProc::is_neg(call->m) != BytecodeProc::is_neg(std::get<1>(fun))) {
2032 if (call->ty[0].ispar()) {
2033 PUSH_INSTR(frag, BytecodeStream::NOT, CG::r(r), CG::r(r));
2034 } else {
2035 auto fun =
2036 find_call_fun(cg, {"op_not"}, Type::varbool(), {Type::varbool()}, BytecodeProc::FUN);
2037 assert(std::get<1>(fun) == BytecodeProc::FUN);
2038 PUSH_INSTR(frag, BytecodeStream::CALL, BytecodeProc::FUN, std::get<0>(fun),
2039 CG::i(!std::get<2>(fun)), CG::r(r));
2040 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r));
2041 }
2042 }
2043 PUSH_INSTR(frag, BytecodeStream::POST, CG::r(r));
2044 }
2045 } else {
2046 assert(p->kind() == CG_Cond::CC_And);
2047 CG_Cond::C_And* conj(reinterpret_cast<CG_Cond::C_And*>(p));
2048 if (!sign) {
2049 // Recurse.
2050 for (CG_Cond::T child : conj->children) post_cond(cg, frag, child);
2051 } else {
2052 // FIXME: Check force context.
2053 PUSH_INSTR(frag, BytecodeStream::POST, CG::r(CG::force(cond, BytecodeProc::FUN, cg, frag)));
2054 }
2055 }
2056 p->reg[sign].is_root = true;
2057}
2058
2059// FIXME: This always forces calls outside the aggregation.
2060void aggregate_cond(CodeGen& cg, CG_Builder& frag, CG_Cond::T cond) {
2061 CG_Cond::_T* p(cond.get());
2062 bool sign(cond.sign());
2063 if (!p) {
2064 // int r_val(CG::locate_immi(1 - sign, cg, frag));
2065 int r_val(bind_cst(1 - sign, cg, frag));
2066 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(r_val));
2067 return;
2068 }
2069 if (p->reg[sign].has_reg()) {
2070 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(p->reg[sign].reg));
2071 return;
2072 } else if (p->reg[1 - sign].has_reg()) {
2073 int r_neg(p->reg[1 - sign].reg);
2074 if (p->reg[1 - sign].is_par) {
2075 int r(GET_REG(cg));
2076 PUSH_INSTR(frag, BytecodeStream::NOT, CG::r(r_neg), CG::r(r));
2077 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(r));
2078 } else {
2079 auto fun =
2080 find_call_fun(cg, {"op_not"}, Type::varbool(), {Type::varbool()}, BytecodeProc::FUN);
2081 assert(std::get<1>(fun) == BytecodeProc::FUN);
2082 PUSH_INSTR(frag, BytecodeStream::CALL, BytecodeProc::FUN, std::get<0>(fun),
2083 CG::i(!std::get<2>(fun)), CG::r(r_neg));
2084 }
2085 return;
2086 }
2087 std::vector<int> var_leaves;
2088 std::vector<int> par_leaves;
2089 if (p->kind() == CG_Cond::CC_And) {
2090 if (!sign) {
2091 force_and_leaves(var_leaves, par_leaves, cond, cg, frag);
2092 int r;
2093 if (var_leaves.empty()) {
2094 r = GET_REG(cg);
2095 PUSH_INSTR(frag, BytecodeStream::MOV, CG::r(par_leaves[0]), CG::r(r));
2096 for (int i = 1; i < par_leaves.size(); ++i) {
2097 PUSH_INSTR(frag, BytecodeStream::AND, CG::r(r), CG::r(par_leaves[i]), CG::r(r));
2098 }
2099 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(r));
2100 } else {
2101 OPEN_AND(cg, frag);
2102 for (int r_c : par_leaves) {
2103 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(r_c));
2104 }
2105 for (int r_c : var_leaves) {
2106 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(r_c));
2107 }
2108 CLOSE_AGG(cg, frag);
2109 }
2110 } else {
2111 force_or_leaves(var_leaves, par_leaves, ~cond, cg, frag);
2112 int r;
2113 if (var_leaves.empty()) {
2114 r = GET_REG(cg);
2115 PUSH_INSTR(frag, BytecodeStream::MOV, CG::r(par_leaves[0]), CG::r(r));
2116 for (int i = 1; i < par_leaves.size(); ++i) {
2117 PUSH_INSTR(frag, BytecodeStream::OR, CG::r(r), CG::r(par_leaves[i]), CG::r(r));
2118 }
2119 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(r));
2120 } else {
2121 OPEN_OR(cg, frag);
2122 for (int r_c : par_leaves) {
2123 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(r_c));
2124 }
2125 for (int r_c : var_leaves) {
2126 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(r_c));
2127 }
2128 CLOSE_AGG(cg, frag);
2129 }
2130 }
2131 } else {
2132 // FIXME: Check force context
2133 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(CG::force(cond, BytecodeProc::FUN, cg, frag)));
2134 }
2135}
2136
2137int locate_range(int l, int u, CodeGen& cg, CG_Builder& frag) {
2138 CG::Binding b;
2139 if (cg.env().cache_lookup_range(l, u, b)) {
2140 return b.first;
2141 }
2142 if (l == 0 && u == 1) {
2143 PUSH_INSTR(frag, BytecodeStream::BUILTIN, cg.find_builtin("boolean_domain"));
2144 int r = GET_REG(cg);
2145 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r));
2146 cg.env().cache_store_range(l, u, std::make_pair(r, CG_Cond::ttt()));
2147 return r;
2148 }
2149
2150 OPEN_VEC(cg, frag);
2151 int r = GET_REG(cg);
2152 PUSH_INSTR(frag, BytecodeStream::IMMI, CG::i(l), CG::r(r));
2153 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(r));
2154 PUSH_INSTR(frag, BytecodeStream::IMMI, CG::i(u), CG::r(r));
2155 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(r));
2156 CLOSE_AGG(cg, frag);
2157 r = GET_REG(cg);
2158 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r));
2159 cg.env().cache_store_range(l, u, std::make_pair(r, CG_Cond::ttt()));
2160 return r;
2161}
2162
2163CG::Binding bind_domain(VarDecl* vd, CodeGen& cg, CG_Builder& frag) {
2164 if (vd->type().bt() == Type::BT_BOOL) {
2165 int r(GET_REG(cg));
2166 PUSH_INSTR(frag, BytecodeStream::BUILTIN, cg.find_builtin("boolean_domain"));
2167 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r));
2168 return {r, CG_Cond::ttt()};
2169 }
2170 if (Expression* d = vd->ti()->domain()) {
2171 // Ignoring partiality here.
2172 return CG::bind(d, cg, frag);
2173 }
2174 int r(GET_REG(cg));
2175 PUSH_INSTR(frag, BytecodeStream::BUILTIN, cg.find_builtin("infinite_domain"));
2176 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r));
2177 return {r, CG_Cond::ttt()};
2178}
2179
2180class Compile : public ItemVisitor {
2181private:
2182 friend class ItemIter<Compile>;
2183
2184 Compile(CodeGen& _cg) : cg(_cg) /*, bool_dom(-1) */ {
2185 // Force the compilation of predicate definitions that can be generated by the compiler
2186 find_call_fun(cg, {"op_not"}, Type::varbool(), {Type::varbool()}, BytecodeProc::FUN);
2187 find_call_fun(cg, {"bool_clause"}, Type::varbool(), {Type::varbool(1), Type::varbool(1)},
2188 BytecodeProc::ROOT, true);
2189 find_call_fun(cg, {"bool_clause_reif"}, Type::varbool(),
2190 {Type::varbool(1), Type::varbool(1), Type::varbool()}, BytecodeProc::ROOT, true);
2191 find_call_fun(cg, {"int_lin_eq"}, Type::varbool(),
2192 {Type::parint(1), Type::varint(1), Type::parint()}, BytecodeProc::ROOT, true);
2193 }
2194
2195 /// Enter model
2196 bool enterModel(Model* m) { return true; }
2197 /// Enter item
2198 bool enter(Item* m) { return true; }
2199 /// Visit variable declaration
2200 void vVarDeclI(VarDeclI* vdi) {
2201 VarDecl* vd(vdi->e());
2202 if (vd->type().isann()) return;
2203 if (vd->type().isopt()) return;
2204 if (vd->type().isvar()) {
2205 // In whatever case, we're going to create something,
2206 // and dump it in a register.
2207 int r_var;
2208 if (vd->e()) {
2209 // Defined
2210 // Evaluate the definition in root context,
2211 // add it to a register
2212 // r_var = CG::locate(vd->e(), BytecodeProc::ROOT, cg, root_frag);
2213 CG::Binding b_var(CG::bind(vd->e(), cg, root_frag));
2214 r_var = b_var.first;
2215 // TODO: Special case for root stuff.
2216 post_cond(cg, root_frag, b_var.second);
2217
2218 if (Expression* d = vd->ti()->domain()) {
2219 if (!vd->ti()->isarray()) {
2220 CG::Binding b_d = CG::bind(d, cg, root_frag);
2221 int r_dp = GET_REG(cg);
2222 PUSH_INSTR(root_frag, BytecodeStream::INTERSECT_DOMAIN, CG::r(r_var), CG::r(b_d.first),
2223 CG::r(r_dp));
2224 post_cond(cg, root_frag, b_d.second);
2225 } else {
2226 // Iterate over the elements of the variable we just created, and
2227 // bind the corresponding domain.
2228 CG::Binding b_d = CG::bind(d, cg, root_frag);
2229 int r_dp = GET_REG(cg);
2230 ITER_ARRAY(cg, root_frag, r_var, [b_d, r_dp](CodeGen& cg, CG_Builder& frag, int r_elt) {
2231 PUSH_INSTR(frag, BytecodeStream::INTERSECT_DOMAIN, CG::r(r_elt), CG::r(b_d.first),
2232 CG::r(r_dp));
2233 });
2234 post_cond(cg, root_frag, b_d.second);
2235 }
2236 }
2237 } else {
2238 CG::Binding b_d(bind_domain(vd, cg, root_frag));
2239 post_cond(cg, root_frag, b_d.second);
2240 int r_d = b_d.first;
2241
2242 r_var = GET_REG(cg);
2243 if (vd->ti()->isarray()) {
2244 // Open nested iterators
2245 int rTMP(GET_REG(cg));
2246 std::vector<int> r_regs;
2247 for (Expression* r : vd->ti()->ranges()) {
2248 Expression* dim(r->template cast<TypeInst>()->domain());
2249 CG::Binding b_reg(CG::bind(dim, cg, root_frag));
2250 post_cond(cg, root_frag, b_reg.second);
2251 r_regs.push_back(b_reg.first);
2252 }
2253 std::vector<Forset> nesting;
2254 OPEN_VEC(cg, root_frag);
2255 for (int r_r : r_regs) {
2256 Forset iter(cg, r_r);
2257 nesting.push_back(iter);
2258 iter.emit_pre(root_frag);
2259 }
2260 PUSH_INSTR(root_frag, BytecodeStream::CALL, BytecodeProc::ROOT,
2261 cg.find_builtin("mk_intvar"), CG::i(0), CG::r(r_d));
2262 for (int r_i = r_regs.size() - 1; r_i >= 0; --r_i) {
2263 nesting[r_i].emit_post(root_frag);
2264 }
2265 CLOSE_AGG(cg, root_frag);
2266
2267 PUSH_INSTR(root_frag, BytecodeStream::POP, CG::r(r_var));
2268 OPEN_VEC(cg, root_frag);
2269 for (int r_r : r_regs) {
2270 PUSH_INSTR(root_frag, BytecodeStream::GET_VEC, CG::r(r_r),
2271 CG::r(bind_cst(1, cg, root_frag)), CG::r(rTMP));
2272 PUSH_INSTR(root_frag, BytecodeStream::PUSH, CG::r(rTMP));
2273 PUSH_INSTR(root_frag, BytecodeStream::GET_VEC, CG::r(r_r),
2274 CG::r(bind_cst(2, cg, root_frag)), CG::r(rTMP));
2275 PUSH_INSTR(root_frag, BytecodeStream::PUSH, CG::r(rTMP));
2276 }
2277 CLOSE_AGG(cg, root_frag);
2278 PUSH_INSTR(root_frag, BytecodeStream::POP, CG::r(rTMP));
2279
2280 PUSH_INSTR(root_frag, BytecodeStream::BUILTIN, cg.find_builtin("array_Xd"), CG::r(r_var),
2281 CG::r(rTMP));
2282 } else {
2283 PUSH_INSTR(root_frag, BytecodeStream::CALL, BytecodeProc::ROOT,
2284 cg.find_builtin("mk_intvar"), CG::i(0), CG::r(r_d));
2285 }
2286 PUSH_INSTR(root_frag, BytecodeStream::POP, CG::r(r_var));
2287 }
2288 // Now copy it into a global, and add it to the env.
2289 int g = cg.add_global(vd, false);
2290 PUSH_INSTR(root_frag, BytecodeStream::STORE_GLOBAL, CG::r(r_var), CG::g(g));
2291
2292 // Since it's still in a register, add it to the current env as well.
2293 cg.env().bind(vd->id()->str(), CG::Binding(r_var, CG_Cond::ttt()));
2294 } else {
2295 // For par identifiers with definitions, we evaluate them.
2296 if (vd->e() && !vd->type().isann()) {
2297 // Evaluate the definition.
2298 // int r = vd->type().ispar() ? CG::locate_par(vd->e(), cg, root_frag) : CG::locate(vd->e(),
2299 // BytecodeProc::ROOT, cg, root_frag);
2300 int r;
2301 if (vd->type().isbool()) {
2302 r = CG::force(CG::compile(vd->e(), cg, root_frag), BytecodeProc::ROOT, cg, root_frag);
2303 } else {
2304 // Par expressions may still introduce constraints.
2305 CG::Binding b_d = CG::bind(vd->e(), cg, root_frag);
2306 post_cond(cg, root_frag, b_d.second);
2307 r = b_d.first;
2308 }
2309 int g = cg.add_global(vd, false);
2310 PUSH_INSTR(root_frag, BytecodeStream::STORE_GLOBAL, CG::r(r), CG::g(g));
2311
2312 cg.env().bind(vd->id()->str(), CG::Binding(r, CG_Cond::ttt()));
2313 }
2314 }
2315 }
2316
2317 /// Visit assign item
2318 void vAssignI(AssignI* ass) {}
2319
2320 void vConstraintI(ConstraintI* c) {
2321 // CG::eval(c->e(), BytecodeProc::ROOT, cg, root_frag);
2322 post_cond(cg, root_frag, CG::compile(c->e(), cg, root_frag));
2323 }
2324
2325 void vFunctionI(FunctionI* f) {
2326 GCLock l;
2327 if (f->ann().contains(constants().ann._export)) {
2328 CG_ProcID body(cg.resolve_fun(f));
2329 // Force the body to be created
2330 if (!body.is_builtin()) {
2331 assert(body.id() < cg.bytecode.size());
2332 if (!cg.bytecode[body.id()].is_available(BytecodeProc::ROOT)) {
2333 cg.bytecode[body.id()].body(BytecodeProc::ROOT);
2334 cg.pending_bodies.push_back(
2335 std::make_pair(f, std::make_pair(BytecodeProc::ROOT, BytecodeProc::ROOT)));
2336 }
2337 }
2338 }
2339 }
2340
2341 // FIXME: This method of saving the CodeGen state is pretty icky.
2342 // CodeGen should probably be split into two objects.
2343 void compile_fun(CG_Builder& frag, const ASTExprVec<VarDecl>& params, Expression* e) {
2344 // Save the codegen state.
2345 auto saved_env = cg.current_env;
2346 cg.current_env = CG_Env<CG::Binding>::spawn(nullptr);
2347 int saved_regs = cg.current_reg_count;
2348
2349 cg.current_reg_count = params.size();
2350
2351 cg._exp_scope.clear();
2352 cg.mode_map.clear();
2353
2354 // Rerun mode analysis
2355 ModeAnalysis modes;
2356 // FIXME: Currently assuming all functions are total.
2357 modes.def(e, BytecodeProc::ROOT);
2358 modes.use(e, BytecodeProc::ROOT);
2359 cg.mode_map = std::move(modes.extract());
2360
2361 // Set up the new env.
2362 {
2363 GCLock l;
2364 for (int ii = 0; ii < params.size(); ++ii) {
2365 cg.env().bind(params[ii]->id()->str(), CG::Binding(ii, CG_Cond::ttt()));
2366 }
2367 }
2368
2369 // Now compile the result.
2370 CG::Binding b_res = CG::bind(e, cg, frag);
2371 if (b_res.second.p) {
2372 // FIXME: What actually happens with this forced result?
2373 // FIXME: Check force context
2374 CG::force(b_res.second, BytecodeProc::FUN, cg, frag);
2375 }
2376 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(b_res.first));
2377 PUSH_INSTR(frag, BytecodeStream::RET);
2378
2379 // now restore everything
2380 cg.current_reg_count = saved_regs;
2381
2382 delete cg.current_env;
2383 cg.current_env = saved_env;
2384 }
2385
2386 void compile_pred(CG_Builder& frag, const ASTExprVec<VarDecl>& params, Mode m, Expression* e) {
2387 // Save the codegen state.
2388 auto saved_env = cg.current_env;
2389 cg.current_env = CG_Env<CG::Binding>::spawn(nullptr);
2390 int saved_regs = cg.current_reg_count;
2391
2392 cg.current_reg_count = params.size();
2393
2394 cg._exp_scope.clear();
2395 cg.mode_map.clear();
2396
2397 // Rerun mode analysis
2398 ModeAnalysis modes;
2399 modes.use(e, m);
2400 cg.mode_map = std::move(modes.extract());
2401
2402 // Set up the new env.
2403 {
2404 GCLock l;
2405 for (int ii = 0; ii < params.size(); ++ii) {
2406 cg.env().bind(params[ii]->id()->str(), CG::Binding(ii, CG_Cond::ttt()));
2407 }
2408 }
2409
2410 // Now compile the result.
2411 CG_Cond::T cond(CG::compile(e, cg, frag));
2412 if (m.strength() == Mode::Root) {
2413 post_cond(cg, frag, m.is_neg() ? ~cond : cond);
2414 } else {
2415 aggregate_cond(cg, frag, m.is_neg() ? ~cond : cond);
2416 }
2417 PUSH_INSTR(frag, BytecodeStream::RET);
2418
2419 cg.current_reg_count = saved_regs;
2420 // then restore everything.
2421 delete cg.current_env;
2422 cg.current_env = saved_env;
2423 }
2424 CodeGen& cg;
2425 CG_Builder root_frag;
2426
2427 // int bool_dom;
2428public:
2429 static void run(CodeGen& cg, Model* m) {
2430 Compile c(cg);
2431 // Compile the main model
2432 OPEN_OTHER(cg, c.root_frag);
2433 iterItems(c, m);
2434 {
2435 int old_reg_count = cg.current_reg_count;
2436 cg.current_reg_count = cg.reg_trail.back();
2437 cg.reg_trail.pop_back();
2438 PUSH_INSTR(c.root_frag, BytecodeStream::CLEAR, CG::r(cg.current_reg_count),
2439 CG::r(old_reg_count - 1));
2440 cg.env_pop();
2441 }
2442 PUSH_INSTR(c.root_frag, BytecodeStream::RET);
2443
2444 // Now generate procedures for any necessary function/predicate bodies.
2445 while (!cg.pending_bodies.empty()) {
2446 GCLock lock;
2447 auto p(cg.pending_bodies.back());
2448 cg.pending_bodies.pop_back();
2449
2450 FunctionI* fun(p.first);
2451 Mode call_mode(p.second.first);
2452 Mode def_mode(p.second.second);
2453 annotate_total(fun);
2454 // Building structures
2455 CG_ProcID proc(cg.resolve_fun(fun));
2456 CG_Builder frag;
2457 // Find the body.
2458 std::vector<Type> arg_types(fun->params().size());
2459 for (int j = 0; j < arg_types.size(); ++j) {
2460 arg_types[j] = fun->params()[j]->type();
2461 }
2462
2463 // Introduce reification if necessary
2464 if (call_mode == BytecodeProc::IMP || call_mode == BytecodeProc::FUN ||
2465 call_mode == BytecodeProc::IMP_NEG || call_mode == BytecodeProc::FUN_NEG) {
2466 auto redef = cg.fun_map.defines_mode(fun->id(), arg_types, call_mode);
2467 if (redef.first) {
2468 std::vector<Expression*> args;
2469 args.reserve(fun->params().size() + 1);
2470 for (int i = 0; i < fun->params().size(); ++i) {
2471 VarDecl* vd = fun->params()[i];
2472 args.emplace_back(vd->id());
2473 }
2474 TypeInst var_bool(Location().introduce(), Type::varbool());
2475 VarDecl new_var(Location().introduce(), &var_bool, "b");
2476 args.emplace_back(new_var.id());
2477 Call call(Location().introduce(), redef.second, args);
2478 call.type(Type::varbool());
2479 Let let(Location().introduce(), {&new_var, &call}, new_var.id());
2480 let.type(Type::varbool());
2481 let.addAnnotation(constants().ann.promise_total);
2482 c.compile_pred(frag, fun->params(), call_mode, &let);
2483 cg.append(proc.id(), call_mode, frag);
2484 continue;
2485 }
2486 }
2487 if (BytecodeProc::is_neg(call_mode)) {
2488 GCLock lock;
2489 ASTString ident(fun->id().str() + "_neg");
2490 auto neg_bodies = std::move(cg.fun_map.get_bodies(ident, arg_types));
2491 if (std::any_of(neg_bodies.begin(), neg_bodies.end(),
2492 [](FunctionI* fi) { return fi->e(); })) {
2493 std::vector<Expression*> args;
2494 args.reserve(fun->params().size());
2495 for (int i = 0; i < fun->params().size(); ++i) {
2496 VarDecl* vd = fun->params()[i];
2497 args.emplace_back(vd->id());
2498 }
2499 Call call(Location().introduce(), ident, args);
2500 call.type(Type::varbool());
2501 // Call negated constraint in positive context (implementation should deal with the
2502 // negation).
2503 c.compile_pred(frag, fun->params(), BytecodeProc::negate(call_mode), &call);
2504 cg.append(proc.id(), call_mode, frag);
2505 continue;
2506 }
2507 }
2508
2509 if (fun->e()) {
2510 if (fun->e()->type().isbool()) {
2511 c.compile_pred(frag, fun->params(), def_mode, fun->e());
2512 } else {
2513 assert(def_mode == BytecodeProc::ROOT);
2514 c.compile_fun(frag, fun->params(), fun->e());
2515 }
2516 } else {
2517 assert(call_mode == BytecodeProc::ROOT);
2518 cg.req_solver_predicates.push_back(fun);
2519 }
2520 cg.append(proc.id(), call_mode, frag);
2521 }
2522
2523 // And finally, add the entry function.
2524 int main_proc = cg.bytecode.size();
2525 cg.bytecode.emplace_back("main", 0);
2526 cg.append(main_proc, BytecodeProc::ROOT, c.root_frag);
2527
2528 show(std::cout, cg);
2529 }
2530};
2531
2532Mode open_conj(Mode ctx, CG_Builder& frag) {
2533 if (ctx == BytecodeProc::ROOT) return ctx;
2534
2535 PUSH_INSTR(frag, BytecodeStream::OPEN_AGGREGATION,
2536 ctx.is_neg() ? AggregationCtx::VCTX_OR : AggregationCtx::VCTX_AND);
2537 return +ctx;
2538}
2539void close_conj(Mode ctx, CG_Builder& frag) {
2540 if (ctx != BytecodeProc::ROOT) PUSH_INSTR(frag, BytecodeStream::CLOSE_AGGREGATION);
2541}
2542Mode open_disj(Mode ctx, CG_Builder& frag) {
2543 if (ctx == BytecodeProc::ROOT_NEG) return ctx;
2544
2545 PUSH_INSTR(frag, BytecodeStream::OPEN_AGGREGATION,
2546 ctx.is_neg() ? AggregationCtx::VCTX_AND : AggregationCtx::VCTX_OR);
2547 return +ctx;
2548}
2549void close_disj(Mode ctx, CG_Builder& frag) {
2550 if (ctx != BytecodeProc::ROOT_NEG) PUSH_INSTR(frag, BytecodeStream::CLOSE_AGGREGATION);
2551}
2552
2553Mode left_child_ctx(Mode ctx, BinOpType b) {
2554 switch (b) {
2555 // Only Boolean operators change the mode.
2556 case BOT_AND:
2557 return ctx.is_neg() ? +ctx : ctx;
2558 case BOT_OR:
2559 case BOT_RIMPL:
2560 return ctx.is_neg() ? ctx : +ctx;
2561 case BOT_IMPL:
2562 return ctx.is_neg() ? -ctx : -(+ctx);
2563 case BOT_EQUIV:
2564 case BOT_XOR:
2565 return *ctx;
2566 default:
2567 return ctx;
2568 }
2569}
2570Mode right_child_ctx(Mode ctx, BinOpType b) {
2571 switch (b) {
2572 // Only Boolean operators change the mode.
2573 case BOT_AND:
2574 return ctx.is_neg() ? +ctx : ctx;
2575 case BOT_OR:
2576 case BOT_IMPL:
2577 return ctx.is_neg() ? ctx : +ctx;
2578 case BOT_RIMPL:
2579 return ctx.is_neg() ? -ctx : -(+ctx);
2580 case BOT_EQUIV:
2581 case BOT_XOR:
2582 return *ctx;
2583 default:
2584 return ctx;
2585 }
2586}
2587Mode child_ctx(Mode ctx, UnOpType u) {
2588 switch (u) {
2589 case UOT_NOT:
2590 return -ctx;
2591 default:
2592 return ctx;
2593 }
2594}
2595
2596void CG::run(CodeGen& cg, Model* m) {
2597 // First, collect the model parameters, and assign them
2598 // global slots.
2599 EnvInit::run(cg, m);
2600 Compile::run(cg, m);
2601}
2602
2603// For a non-Boolean value, place it in a register and collect its partiality.
2604std::pair<int, CG_Cond::T> _bind(Expression* e, CodeGen& cg, CG_Builder& frag) {
2605 // Look up the mode we need to compile e in.
2606 // FIXME: Figure out why some expressions don't have a mode attached.
2607 CG::Mode ctx(BytecodeProc::FUN);
2608 try {
2609 ctx = cg.mode_map.at(e);
2610 } catch (const std::out_of_range& exn) {
2611 }
2612
2613 switch (e->eid()) {
2614 case Expression::E_INTLIT: {
2615 // return std::make_pair(CG::locate_immi(e->template cast<IntLit>()->v().toInt(), cg, frag),
2616 // CG_Cond::ttt());
2617 IntVal i = e->cast<IntLit>()->v();
2618 if (!i.isFinite()) {
2619 int r(GET_REG(cg));
2620 PUSH_INSTR(frag, BytecodeStream::BUILTIN, cg.find_builtin("infinity"),
2621 CG::r(bind_cst(i.isPlusInfinity(), cg, frag)));
2622 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r));
2623 return {r, CG_Cond::ttt()};
2624 }
2625 return {bind_cst(i.toInt(), cg, frag), CG_Cond::ttt()};
2626 }
2627 case Expression::E_FLOATLIT:
2628 // return std::make_pair(CG::locate_par(e->template cast<FloatLit>(), cg, frag), nullptr);
2629 // NOT YET IMPLEMENTED
2630 return CG::Binding(bind_cst(911911, cg, frag), CG_Cond::ttt());
2631 case Expression::E_SETLIT:
2632 return CG::bind(e->template cast<SetLit>(), ctx, cg, frag);
2633 case Expression::E_BOOLLIT:
2634 throw InternalError("bind called on Boolean expression.");
2635 case Expression::E_STRINGLIT:
2636 // NOT YET IMPLEMENTED
2637 return CG::Binding(bind_cst(911911, cg, frag), CG_Cond::ttt());
2638 case Expression::E_ID:
2639 return CG::bind(e->template cast<Id>(), ctx, cg, frag);
2640 case Expression::E_ANON:
2641 throw InternalError("bind reached unexpected expression type: E_ANON.");
2642 case Expression::E_ARRAYLIT:
2643 return CG::bind(e->template cast<ArrayLit>(), ctx, cg, frag);
2644 case Expression::E_ARRAYACCESS:
2645 return CG::bind(e->template cast<ArrayAccess>(), ctx, cg, frag);
2646 case Expression::E_COMP:
2647 return CG::bind(e->template cast<Comprehension>(), ctx, cg, frag);
2648 case Expression::E_ITE:
2649 return CG::bind(e->template cast<ITE>(), ctx, cg, frag);
2650 case Expression::E_BINOP:
2651 return CG::bind(e->template cast<BinOp>(), ctx, cg, frag);
2652 case Expression::E_UNOP:
2653 return CG::bind(e->template cast<UnOp>(), ctx, cg, frag);
2654 case Expression::E_CALL:
2655 return CG::bind(e->template cast<Call>(), ctx, cg, frag);
2656 case Expression::E_LET:
2657 return CG::bind(e->template cast<Let>(), ctx, cg, frag);
2658 case Expression::E_VARDECL:
2659 case Expression::E_TI:
2660 case Expression::E_TIID:
2661 throw InternalError("Bytecode generator encountered unexpected expression type in bind.");
2662 }
2663}
2664
2665CG::Binding CG::bind(Expression* e, CodeGen& cg, CG_Builder& frag) {
2666 try {
2667 return cg.cache_lookup(e);
2668 } catch (const CG_Env<CG::Binding>::NotFound& exn) {
2669 CG::Binding b(_bind(e, cg, frag));
2670 cg.cache_store(e, b);
2671 return b;
2672 }
2673 // return _bind(e, cg, frag); // FIXME
2674}
2675
2676//
2677int CG::locate_immi(int x, CodeGen& cg, CG_Builder& frag) {
2678 int r(GET_REG(cg));
2679 PUSH_INSTR(frag, BytecodeStream::IMMI, CG::i(x), CG::r(r));
2680 return r;
2681}
2682
2683// Modified version of execute-comprehension, executing an arbitrary callable on the innter
2684// expression.
2685template <class F>
2686void execute_comprehension_generic(Comprehension* c, Mode ctx, CodeGen& cg, CG_Builder& frag, F f) {
2687 // Build up the object to build the generator.
2688 std::vector<EmitPost*> nesting;
2689
2690 int depth = 0;
2691
2692 int g = c->n_generators();
2693 int n_gen = c->n_generators();
2694 for (int g = 0; g < n_gen; ++g) {
2695 // Bind the in-expression to a register.
2696 // assert(c->in(g)->type().ispar());
2697 Expression* in(c->in(g));
2698 // std::cout << "Binding R" << r << " to: "; debugprint(in);
2699 // Open the bindings.
2700 cg.env_push();
2701 if (in->type().is_set()) {
2702 int r(CG::bind(in, cg, frag).first);
2703 assert(in->type().ispar());
2704 for (int d = 0; d < c->n_decls(g); ++d) {
2705 Forset* iter(new Forset(cg, r));
2706 depth += 2; // Forset first iterates over the range, then values in the range.
2707 nesting.push_back(iter);
2708 iter->emit_pre(frag);
2709 // Bind vd->id() to iter.val()
2710 VarDecl* vd(c->decl(g, d));
2711 ASTString id(vd->id()->str());
2712 // cg.env().bind(id, Loc::reg(iter.val()));
2713 cg.env().bind(id, CodeGen::Binding(iter->val(), CG_Cond::ttt()));
2714 }
2715 } else {
2716 assert(in->type().isboolarray() || in->type().isintarray() || in->type().isintsetarray());
2717 int r_arr(CG::bind(in, cg, frag).first);
2718 for (int d = 0; d < c->n_decls(g); ++d) {
2719 Foreach* iter(new Foreach(cg, r_arr));
2720 nesting.push_back(iter);
2721 iter->emit_pre(frag);
2722 depth += 1;
2723
2724 VarDecl* vd(c->decl(g, d));
2725 ASTString id(vd->id()->str());
2726 cg.env().bind(id, CodeGen::Binding(iter->val(), CG_Cond::ttt()));
2727 }
2728 }
2729 // Now emit the where-clause
2730 Expression* where(c->where(g));
2731 if (where) {
2732 int lblCont(nesting.back()->cont());
2733 assert(where->type().ispar());
2734 int rC = CG::force(CG::compile(where, cg, frag), BytecodeProc::FUN, cg, frag);
2735 PUSH_INSTR(frag, BytecodeStream::JMPIFNOT, CG::r(rC), CG::l(lblCont));
2736 }
2737 }
2738 // We're now in the deepest scope. Generate code for the body.
2739 f(c->e(), ctx, cg, frag, nesting.back()->cont(), depth);
2740
2741 // Now close the iterators _in reverse order_, and restore the environment.
2742 for (int ii = nesting.size() - 1; ii >= 0; --ii) {
2743 nesting[ii]->emit_post(frag);
2744 delete nesting[ii];
2745 }
2746 for (int ii = 0; ii < n_gen; ++ii) cg.env_pop();
2747}
2748
2749// Specialized version when we're binding and pushing the body.
2750void execute_comprehension_bind(Comprehension* c, Mode ctx, CodeGen& cg, CG_Builder& frag) {
2751 execute_comprehension_generic(
2752 c, ctx, cg, frag,
2753 [](Expression* e, Mode ctx, CodeGen& cg, CG_Builder& frag, int lbl_cont, int depth) {
2754 // Bind and push everything in the comprehension.
2755 CG::Binding b_e = CG::force_or_bind(e, ctx, cg, frag);
2756 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(b_e.first)); // FIXME: Discarding partiality
2757 });
2758}
2759
2760// Special case implementation of folds where body is a generator.
2761CG_Cond::T eval_forall(Call* call, Mode ctx, CodeGen& cg, CG_Builder& frag) {
2762 assert(call->n_args() == 1);
2763 Expression* param = call->arg(0);
2764 // Now check the expression's type. If it's an array literal or
2765 // comprehension, we generate code directly, rather than generating
2766 // a concrete vector.
2767 switch (param->eid()) {
2768 case Expression::E_ARRAYLIT: {
2769 std::vector<CG_Cond::T> conj;
2770 ArrayLit* a(param->cast<ArrayLit>());
2771 int sz(a->size());
2772 for (int ii = 0; ii < sz; ++ii) conj.push_back(CG::compile((*a)[ii], cg, frag));
2773 return CG_Cond::forall(ctx, conj);
2774 } break;
2775 case Expression::E_COMP: {
2776 Comprehension* c(param->cast<Comprehension>());
2777 // Special cases: if we're in root, just post everything.
2778 if (ctx == BytecodeProc::ROOT) {
2779 execute_comprehension_generic(
2780 param->cast<Comprehension>(), ctx, cg, frag,
2781 [](Expression* elt, Mode ctx, CodeGen& cg, CG_Builder& frag, int lbl_cont, int depth) {
2782 CG_Cond::T c = CG::compile(elt, cg, frag);
2783 post_cond(cg, frag, c);
2784 });
2785 ;
2786 return CG_Cond::T::ttt();
2787 }
2788 // If it's par, do shortcutting.
2789 if (c->e()->type().ispar()) {
2790 int r(GET_REG(cg));
2791 PUSH_INSTR(frag, BytecodeStream::IMMI, CG::i(1), CG::r(r));
2792 execute_comprehension_generic(
2793 c, ctx, cg, frag,
2794 [r](Expression* elt, Mode ctx, CodeGen& cg, CG_Builder& frag, int lbl_cont, int depth) {
2795 int r_cond = CG::force(CG::compile(elt, cg, frag), BytecodeProc::FUN, cg, frag);
2796 PUSH_INSTR(frag, BytecodeStream::JMPIF, CG::r(r_cond), CG::l(lbl_cont));
2797 PUSH_INSTR(frag, BytecodeStream::IMMI, CG::i(0), CG::r(r));
2798 PUSH_INSTR(frag, BytecodeStream::ITER_BREAK, CG::i(depth));
2799 });
2800 ;
2801 return CG_Cond::reg(r, true);
2802 } else {
2803 // General case, just aggregate the values.
2804 OPEN_AND(cg, frag);
2805 execute_comprehension_generic(
2806 c, ctx, cg, frag,
2807 [](Expression* elt, Mode ctx, CodeGen& cg, CG_Builder& frag, int lbl_cont, int depth) {
2808 int r_cond =
2809 CG::force(CG::compile(elt, cg, frag), CG::Mode(ctx.strength(), false), cg, frag);
2810 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(r_cond));
2811 });
2812 CLOSE_AGG(cg, frag);
2813 int r(GET_REG(cg));
2814 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r));
2815 return CG_Cond::reg(r, false);
2816 }
2817 }
2818 default: {
2819 int r(GET_REG(cg));
2820 CG::Binding b_param(CG::bind(param, cg, frag));
2821 int r_A(b_param.first);
2822 std::vector<int> p_A;
2823 if (!b_param.second.get()) {
2824 if (b_param.second.sign()) return CG_Cond::T::fff();
2825 } else {
2826 // TODO: It's probably not quicker to split par/var since we need the AND Aggregation anyway
2827 force_and_leaves(p_A, p_A, b_param.second, cg, frag);
2828 }
2829 OPEN_AND(cg, frag);
2830 // First, push the constraints attached to A.
2831 for (int r_c : p_A) {
2832 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(r_c));
2833 }
2834 ITER_ARRAY(cg, frag, r_A, [](CodeGen& cg, CG_Builder& frag, int r_elt) {
2835 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(r_elt));
2836 });
2837 CLOSE_AGG(cg, frag);
2838 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r));
2839 return CG_Cond::reg(r, call->type().ispar());
2840 }
2841 }
2842}
2843// Same as forall, but producing an or-context.
2844CG_Cond::T eval_exists(Call* call, Mode ctx, CodeGen& cg, CG_Builder& frag) {
2845 assert(call->n_args() == 1);
2846 Expression* param = call->arg(0);
2847
2848 // Now check the expression's type. If it's an array literal or
2849 // comprehension, we generate code directly, rather than generating
2850 // a concrete vector.
2851 switch (param->eid()) {
2852 case Expression::E_ARRAYLIT: {
2853 std::vector<CG_Cond::T> disj;
2854 ArrayLit* a(param->cast<ArrayLit>());
2855 int sz(a->size());
2856 for (int ii = 0; ii < sz; ++ii) {
2857 CG_Cond::T elt(CG::compile((*a)[ii], cg, frag));
2858 disj.push_back(elt);
2859 }
2860 return CG_Cond::exists(ctx, disj);
2861 } break;
2862 /*
2863 case Expression::E_COMP: {
2864 Comprehension* c(param->cast<Comprehension>());
2865 execute_comprehension(c, c_ctx, cg, frag);
2866 }
2867 break;
2868 */
2869#if 1
2870 case Expression::E_COMP: {
2871 Comprehension* c(param->cast<Comprehension>());
2872 if (c->e()->type().ispar()) {
2873 int r(GET_REG(cg));
2874 PUSH_INSTR(frag, BytecodeStream::IMMI, CG::i(0), CG::r(r));
2875 execute_comprehension_generic(
2876 c, ctx, cg, frag,
2877 [r](Expression* elt, Mode ctx, CodeGen& cg, CG_Builder& frag, int lbl_cont, int depth) {
2878 int r_cond = CG::force(CG::compile(elt, cg, frag), BytecodeProc::FUN, cg, frag);
2879 PUSH_INSTR(frag, BytecodeStream::JMPIFNOT, CG::r(r_cond), CG::l(lbl_cont));
2880 PUSH_INSTR(frag, BytecodeStream::IMMI, CG::i(1), CG::r(r));
2881 PUSH_INSTR(frag, BytecodeStream::ITER_BREAK, CG::i(depth));
2882 });
2883 return CG_Cond::reg(r, true);
2884 } else {
2885 OPEN_OR(cg, frag);
2886 execute_comprehension_generic(
2887 c, ctx, cg, frag,
2888 [](Expression* elt, Mode ctx, CodeGen& cg, CG_Builder& frag, int lbl_cont, int depth) {
2889 int r_cond =
2890 CG::force(CG::compile(elt, cg, frag), CG::Mode(ctx.strength(), false), cg, frag);
2891 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(r_cond));
2892 });
2893 CLOSE_AGG(cg, frag);
2894 int r(GET_REG(cg));
2895 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r));
2896 return CG_Cond::reg(r, false);
2897 }
2898 } // Fallthrough
2899#endif
2900 default: {
2901 int r(GET_REG(cg));
2902 // Otherwise, get the result into a register...
2903 CG::Binding b_A(CG::bind(param, cg, frag));
2904 int r_A(b_A.first);
2905 // and push every element.
2906 OPEN_OR(cg, frag);
2907 ITER_ARRAY(cg, frag, r_A, [](CodeGen& cg, CG_Builder& frag, int r_elt) {
2908 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(r_elt));
2909 });
2910 CLOSE_AGG(cg, frag);
2911 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r));
2912 return CG_Cond::forall(ctx, b_A.second, CG_Cond::reg(r, call->type().ispar()));
2913 }
2914 }
2915}
2916
2917CG_Cond::T eval_isfixed_b(Call* call, Mode ctx, CodeGen& cg, CG_Builder& frag) {
2918 assert(call->n_args() == 1);
2919 Expression* e(call->arg(0));
2920
2921 if (e->type().ispar()) return CG_Cond::T::ttt();
2922
2923 int r_e;
2924 if (e->type().isbool()) {
2925 CG_Cond::T b_e(CG::compile(e, cg, frag));
2926 if (!b_e.get()) {
2927 return CG_Cond::T::ttt();
2928 }
2929 r_e = CG::force(b_e, ctx, cg, frag);
2930 } else {
2931 CG::Binding b(CG::bind(e, cg, frag));
2932 r_e = b.first;
2933 }
2934 int r(GET_REG(cg));
2935 PUSH_INSTR(frag, BytecodeStream::ISPAR, CG::r(r_e), CG::r(r));
2936 return CG_Cond::reg(r, true);
2937}
2938
2939CG::Binding bind_fix(Call* call, Mode ctx, CodeGen& cg, CG_Builder& frag) {
2940 assert(call->n_args() == 1);
2941
2942 Expression* arg(call->arg(0));
2943 CG::Binding b_arg(CG::bind(arg, cg, frag));
2944 if (arg->type().ispar()) {
2945 return b_arg;
2946 } else if (arg->type().isintarray() || arg->type().isboolarray()) {
2947 int r_cond(GET_REG(cg));
2948 // Init the condition
2949 PUSH_INSTR(frag, BytecodeStream::ISPAR, CG::r(b_arg.first), CG::r(r_cond));
2950
2951 // Gather elements
2952 OPEN_VEC(cg, frag);
2953 ITER_ARRAY(cg, frag, b_arg.first, [](CodeGen& cg, CG_Builder& frag, int r_elt) {
2954 PUSH_INSTR(frag, BytecodeStream::LB, CG::r(r_elt), CG::r(r_elt));
2955 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(r_elt));
2956 });
2957 CLOSE_AGG(cg, frag);
2958 int r_elts(GET_REG(cg));
2959 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r_elts));
2960
2961 // Ensure resulting array has the same index set
2962 PUSH_INSTR(frag, BytecodeStream::BUILTIN, cg.find_builtin("index_set"), CG::r(b_arg.first),
2963 CG::r(bind_cst(0, cg, frag)));
2964 int r_indxs(GET_REG(cg));
2965 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r_indxs));
2966
2967 PUSH_INSTR(frag, BytecodeStream::BUILTIN, cg.find_builtin("array_Xd"), CG::r(r_elts),
2968 CG::r(r_indxs));
2969 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r_elts));
2970
2971 return {r_elts, CG_Cond::forall(ctx, b_arg.second, CG_Cond::reg(r_cond, true))};
2972 } else {
2973 int r(GET_REG(cg));
2974 int r_cond(GET_REG(cg));
2975
2976 PUSH_INSTR(frag, BytecodeStream::ISPAR, CG::r(b_arg.first), CG::r(r_cond));
2977 PUSH_INSTR(frag, BytecodeStream::LB, CG::r(b_arg.first), CG::r(r));
2978
2979 return {r, CG_Cond::forall(ctx, b_arg.second, CG_Cond::reg(r_cond, true))};
2980 }
2981}
2982
2983CG_Cond::T eval_fix(Call* call, Mode ctx, CodeGen& cg, CG_Builder& frag) {
2984 assert(call->n_args() == 1);
2985
2986 // Should we check that the argument is actually fixed??
2987 int r = CG::force(CG::compile(call->arg(0), cg, frag), ctx, cg, frag);
2988 return CG_Cond::reg(r, true);
2989}
2990
2991CG_Cond::T eval_error_b(Call* call, Mode ctx, CodeGen& cg, CG_Builder& frag) {
2992 throw InternalError("Call should only appear in general context.");
2993 return CG_Cond::ttt();
2994}
2995CG::Binding bind_error_g(Call* call, Mode ctx, CodeGen& cg, CG_Builder& frag) {
2996 throw InternalError("Call should only appear in Boolean context.");
2997}
2998CG::Binding bind_sum(Call* call, Mode ctx, CodeGen& cg, CG_Builder& frag) {
2999 GCLock lock;
3000 assert(call->n_args() == 1);
3001 Expression* e = call->arg(0);
3002 // Components of the sum may be partial.
3003 // TODO: Specialise for literals and comprehensions.
3004 CG::Binding b_elts(CG::bind(e, cg, frag));
3005 int r_one(bind_cst(1, cg, frag));
3006
3007 if (e->type().ispar()) {
3008 int r_sum(GET_REG(cg));
3009 PUSH_INSTR(frag, BytecodeStream::IMMI, CG::i(0), CG::r(r_sum));
3010 ITER_ARRAY(cg, frag, b_elts.first, [&](CodeGen& cg, CG_Builder& frag, int r_elt) {
3011 PUSH_INSTR(frag, BytecodeStream::ADDI, CG::r(r_sum), CG::r(r_elt), CG::r(r_sum));
3012 });
3013 return CG::Binding(r_sum, b_elts.second);
3014 }
3015
3016 int r_sz(GET_REG(cg));
3017 int r_ret(GET_REG(cg));
3018
3019 int l_eq0(GET_LABEL(cg));
3020 int l_eq1(GET_LABEL(cg));
3021 int l_end(GET_LABEL(cg));
3022
3023 PUSH_INSTR(frag, BytecodeStream::LENGTH, CG::r(b_elts.first), CG::r(r_sz));
3024 PUSH_INSTR(frag, BytecodeStream::JMPIFNOT, CG::r(r_sz), CG::l(l_eq0));
3025 PUSH_INSTR(frag, BytecodeStream::EQI, CG::r(r_one), CG::r(r_sz), CG::r(r_ret));
3026 PUSH_INSTR(frag, BytecodeStream::JMPIF, CG::r(r_ret), CG::l(l_eq1));
3027
3028 // Sum n arguments
3029 auto fun = find_call_fun(cg, {"sum_cc"}, Type::varint(), {Type::varint(1)}, BytecodeProc::FUN);
3030 assert(std::get<1>(fun) == BytecodeProc::FUN);
3031 PUSH_INSTR(frag, BytecodeStream::CALL, BytecodeProc::FUN, std::get<0>(fun),
3032 CG::i(!std::get<2>(fun)), CG::r(b_elts.first));
3033 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r_ret));
3034 PUSH_INSTR(frag, BytecodeStream::JMP, CG::l(l_end));
3035
3036 // Sum zero arguments (result must be 0)
3037 PUSH_LABEL(frag, l_eq0);
3038 PUSH_INSTR(frag, BytecodeStream::IMMI, CG::i(0), CG::r(r_ret));
3039 PUSH_INSTR(frag, BytecodeStream::JMP, CG::l(l_end));
3040
3041 // Sum 1 arguments (result == a[1])
3042 PUSH_LABEL(frag, l_eq1);
3043 PUSH_INSTR(frag, BytecodeStream::GET_VEC, CG::r(b_elts.first), CG::r(r_one), CG::r(r_ret));
3044
3045 // End of sum
3046 PUSH_LABEL(frag, l_end);
3047 return CG::Binding(r_ret, b_elts.second);
3048}
3049
3050CG::Binding bind_set2array(Call* call, Mode ctx, CodeGen& cg, CG_Builder& frag) {
3051 assert(call->n_args() == 1);
3052 // Bind set
3053 Expression* e = call->arg(0);
3054 CG::Binding b_elts(CG::bind(e, cg, frag));
3055
3056 // Create array
3057
3058 OPEN_VEC(cg, frag);
3059 ITER_SET(cg, frag, b_elts.first, [](CodeGen& cg, CG_Builder& frag, int r_elt) {
3060 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(r_elt));
3061 });
3062 CLOSE_AGG(cg, frag);
3063 int r_ret(GET_REG(cg));
3064 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r_ret));
3065
3066 return {r_ret, b_elts.second};
3067}
3068
3069CG::Binding bind_dom_bounds_array(Call* call, Mode ctx, CodeGen& cg, CG_Builder& frag) {
3070 assert(call->n_args() == 1);
3071 CG::Binding b_A(CG::bind(call->arg(0), cg, frag));
3072
3073 // Open the context here, so we can recover all the registers after.
3074 OPEN_VEC(cg, frag);
3075
3076 int r_lb(GET_REG(cg));
3077 PUSH_INSTR(frag, BytecodeStream::BUILTIN, cg.find_builtin("infinity"),
3078 CG::r(bind_cst(1, cg, frag)));
3079 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r_lb));
3080
3081 int r_ub(GET_REG(cg));
3082 PUSH_INSTR(frag, BytecodeStream::BUILTIN, cg.find_builtin("infinity"),
3083 CG::r(bind_cst(0, cg, frag)));
3084 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r_ub));
3085
3086 // Do the iteration
3087 int r_test(GET_REG(cg));
3088 int r_bound(GET_REG(cg));
3089
3090 int l_lb(GET_LABEL(cg));
3091 int l_ub(GET_LABEL(cg));
3092 // Body
3093 ITER_ARRAY(cg, frag, b_A.first, [&](CodeGen& cg, CG_Builder& frag, int r_elt) {
3094 PUSH_INSTR(frag, BytecodeStream::LB, CG::r(r_elt), CG::r(r_bound));
3095 PUSH_INSTR(frag, BytecodeStream::LEI, CG::r(r_lb), CG::r(r_bound), CG::r(r_test));
3096 PUSH_INSTR(frag, BytecodeStream::JMPIF, CG::r(r_test), CG::l(l_lb));
3097 PUSH_INSTR(frag, BytecodeStream::MOV, CG::r(r_bound), CG::r(r_lb));
3098 PUSH_LABEL(frag, l_lb);
3099 PUSH_INSTR(frag, BytecodeStream::UB, CG::r(r_elt), CG::r(r_bound));
3100 PUSH_INSTR(frag, BytecodeStream::LEI, CG::r(r_bound), CG::r(r_ub), CG::r(r_test));
3101 PUSH_INSTR(frag, BytecodeStream::JMPIF, CG::r(r_test), CG::l(l_ub));
3102 PUSH_INSTR(frag, BytecodeStream::MOV, CG::r(r_bound), CG::r(r_ub));
3103 PUSH_LABEL(frag, l_ub);
3104 });
3105
3106 // Now collect the elements
3107 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(r_lb));
3108 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(r_ub));
3109 CLOSE_AGG(cg, frag);
3110 int r(GET_REG(cg));
3111 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r));
3112 return CG::Binding(r, b_A.second);
3113}
3114
3115CG_Cond::T eval_assert_b(Call* call, Mode ctx, CodeGen& cg, CG_Builder& frag) {
3116 assert(call->arg(0)->type().ispar());
3117 // Evaluate the assertion, abort if it fails.
3118 /*
3119 int r_cond = CG::force(CG::compile(call->arg(0), cg, frag), cg, frag);
3120 int l_okay(GET_LABEL(cg));
3121 PUSH_INSTR(frag, BytecodeStream::JMPIF, CG::r(r_cond), CG::l(l_okay));
3122 PUSH_INSTR(frag, BytecodeStream::ABORT);
3123 PUSH_LABEL(frag, l_okay);
3124 */
3125 // Otherwise, evaluate as usual.
3126 if (call->n_args() == 2) {
3127 return CG_Cond::ttt();
3128 } else {
3129 assert(call->n_args() == 3);
3130 return CG::compile(call->arg(2), cg, frag);
3131 }
3132}
3133
3134CG::Binding bind_assert_g(Call* call, Mode ctx, CodeGen& cg, CG_Builder& frag) {
3135 assert(call->n_args() == 3);
3136 assert(call->arg(0)->type().ispar());
3137 /*
3138 int r_cond = CG::force(CG::compile(call->arg(0), cg, frag), cg, frag);
3139 int l_okay(GET_LABEL(cg));
3140 PUSH_INSTR(frag, BytecodeStream::JMPIF, CG::r(r_cond), CG::l(l_okay));
3141 PUSH_INSTR(frag, BytecodeStream::ABORT);
3142 PUSH_LABEL(frag, l_okay);
3143 */
3144 return CG::bind(call->arg(2), cg, frag);
3145}
3146
3147CG::Binding bind_arrayXd(Call* call, Mode ctx, CodeGen& cg, CG_Builder& frag) {
3148 assert(call->n_args() == 2);
3149 CG::Binding orig(CG::bind(call->arg(0), cg, frag));
3150 CG::Binding target(CG::bind(call->arg(1), cg, frag));
3151
3152 // Get index sets from orig
3153 int r(GET_REG(cg));
3154 PUSH_INSTR(frag, BytecodeStream::BUILTIN, cg.find_builtin("index_set"), CG::r(orig.first),
3155 CG::r(bind_cst(0, cg, frag)));
3156 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r));
3157
3158 // Create new array
3159 PUSH_INSTR(frag, BytecodeStream::BUILTIN, cg.find_builtin("array_Xd"), CG::r(target.first),
3160 CG::r(r));
3161 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r));
3162
3163 return {r, CG_Cond::forall(ctx, orig.second, target.second)};
3164}
3165
3166template <int N>
3167CG::Binding bind_arrayNd(Call* call, Mode ctx, CodeGen& cg, CG_Builder& frag) {
3168 assert(call->n_args() == N + 1);
3169 std::vector<CG_Cond::T> cond;
3170
3171 // Bind all index sets
3172 std::vector<int> r_index(N);
3173 for (int ii = 0; ii < N; ++ii) {
3174 CG::Binding b(CG::bind(call->arg(ii), cg, frag));
3175 r_index[ii] = b.first;
3176 cond.push_back(b.second);
3177 }
3178
3179 // Bind array expression
3180 CG::Binding arr = CG::bind(call->arg(N), cg, frag);
3181
3182 int rI(GET_REG(cg));
3183 OPEN_VEC(cg, frag);
3184 for (int ii = 0; ii < N; ++ii) {
3185 // TODO: Ensure the index set is a range (2-elements)
3186 PUSH_INSTR(frag, BytecodeStream::GET_VEC, CG::r(r_index[ii]), CG::r(bind_cst(1, cg, frag)),
3187 CG::r(rI));
3188 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(rI));
3189 PUSH_INSTR(frag, BytecodeStream::GET_VEC, CG::r(r_index[ii]), CG::r(bind_cst(2, cg, frag)),
3190 CG::r(rI));
3191 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(rI));
3192 }
3193 CLOSE_AGG(cg, frag);
3194 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(rI));
3195
3196 PUSH_INSTR(frag, BytecodeStream::BUILTIN, cg.find_builtin("array_Xd"), CG::r(arr.first),
3197 CG::r(rI));
3198 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(rI));
3199
3200 return {rI, CG_Cond::forall(ctx, cond)};
3201}
3202
3203CG::Binding bind_array1d(Call* call, Mode ctx, CodeGen& cg, CG_Builder& frag) {
3204 if (call->n_args() == 1) {
3205 int rA(GET_REG(cg));
3206 CG::Binding arr = CG::bind(call->arg(0), cg, frag);
3207
3208 PUSH_INSTR(frag, BytecodeStream::BUILTIN, cg.find_builtin("array_Xd"), CG::r(arr.first),
3209 CG::r(bind_cst(0, cg, frag)));
3210 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(rA));
3211
3212 return {rA, arr.second};
3213 } else {
3214 // Index set given by the user
3215 assert(call->n_args() == 2);
3216 return bind_arrayNd<1>(call, ctx, cg, frag);
3217 }
3218}
3219
3220CG::Binding bind_array_union(Call* call, Mode ctx, CodeGen& cg, CG_Builder& frag) {
3221 assert(call->n_args() == 1);
3222 Expression* e = call->arg(0);
3223 // Components of the sum may be partial.
3224 // TODO: Specialise for literals and comprehensions.
3225 CG::Binding b_elts(CG::bind(e, cg, frag));
3226
3227 assert(e->type().ispar()); // TODO: var case
3228 int r_union(GET_REG(cg));
3229 OPEN_VEC(cg, frag);
3230 CLOSE_AGG(cg, frag);
3231 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r_union));
3232
3233 ITER_ARRAY(cg, frag, b_elts.first, [&](CodeGen& cg, CG_Builder& frag, int r_elt) {
3234 PUSH_INSTR(frag, BytecodeStream::UNION, CG::r(r_union), CG::r(r_elt), CG::r(r_union));
3235 });
3236
3237 return {r_union, b_elts.second};
3238}
3239
3240CG::Binding bind_length(Call* call, Mode ctx, CodeGen& cg, CG_Builder& frag) {
3241 assert(call->n_args() == 1);
3242 CG::Binding b(CG::bind(call->arg(0), cg, frag));
3243 int r(GET_REG(cg));
3244 PUSH_INSTR(frag, BytecodeStream::LENGTH, CG::r(b.first), CG::r(r));
3245 return {r, b.second};
3246}
3247
3248CG::Binding bind_lb(Call* call, Mode ctx, CodeGen& cg, CG_Builder& frag) {
3249 assert(call->n_args() == 1);
3250 CG::Binding b(CG::bind(call->arg(0), cg, frag));
3251 int r(GET_REG(cg));
3252 PUSH_INSTR(frag, BytecodeStream::LB, CG::r(b.first), CG::r(r));
3253 return CG::Binding(r, b.second);
3254}
3255CG::Binding bind_ub(Call* call, Mode ctx, CodeGen& cg, CG_Builder& frag) {
3256 assert(call->n_args() == 1);
3257 CG::Binding b(CG::bind(call->arg(0), cg, frag));
3258 int r(GET_REG(cg));
3259 PUSH_INSTR(frag, BytecodeStream::UB, CG::r(b.first), CG::r(r));
3260 return CG::Binding(r, b.second);
3261}
3262CG::Binding bind_dom(Call* call, Mode ctx, CodeGen& cg, CG_Builder& frag) {
3263 assert(call->n_args() == 1);
3264 CG::Binding b(CG::bind(call->arg(0), cg, frag));
3265 int r(GET_REG(cg));
3266 PUSH_INSTR(frag, BytecodeStream::DOM, CG::r(b.first), CG::r(r));
3267 return CG::Binding(r, b.second);
3268}
3269CG::Binding bind_lb_array(Call* call, Mode ctx, CodeGen& cg, CG_Builder& frag) {
3270 assert(call->n_args() == 1);
3271 CG::Binding b_A(CG::bind(call->arg(0), cg, frag));
3272
3273 int r_agg(GET_REG(cg));
3274 PUSH_INSTR(frag, BytecodeStream::BUILTIN, cg.find_builtin("infinity"),
3275 CG::r(bind_cst(1, cg, frag)));
3276 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r_agg));
3277
3278 int r_tmp(GET_REG(cg));
3279 int r_test(GET_REG(cg));
3280 int l_end(GET_LABEL(cg));
3281 ITER_ARRAY(cg, frag, b_A.first, [&](CodeGen& cg, CG_Builder& frag, int r_elt) {
3282 PUSH_INSTR(frag, BytecodeStream::LB, CG::r(r_elt), CG::r(r_tmp));
3283 PUSH_INSTR(frag, BytecodeStream::LTI, CG::r(r_tmp), CG::r(r_agg), CG::r(r_test));
3284 PUSH_INSTR(frag, BytecodeStream::JMPIFNOT, CG::r(r_test), CG::l(l_end));
3285 PUSH_INSTR(frag, BytecodeStream::MOV, CG::r(r_tmp), CG::r(r_agg));
3286 PUSH_LABEL(frag, l_end);
3287 });
3288
3289 return CG::Binding(r_agg, b_A.second);
3290}
3291
3292CG::Binding bind_ub_array(Call* call, Mode ctx, CodeGen& cg, CG_Builder& frag) {
3293 assert(call->n_args() == 1);
3294 CG::Binding b_A(CG::bind(call->arg(0), cg, frag));
3295
3296 int r_agg(GET_REG(cg));
3297 PUSH_INSTR(frag, BytecodeStream::BUILTIN, cg.find_builtin("infinity"),
3298 CG::r(bind_cst(0, cg, frag)));
3299 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r_agg));
3300
3301 int r_tmp(GET_REG(cg));
3302 int r_test(GET_REG(cg));
3303 int l_end(GET_LABEL(cg));
3304 ITER_ARRAY(cg, frag, b_A.first, [&](CodeGen& cg, CG_Builder& frag, int r_elt) {
3305 PUSH_INSTR(frag, BytecodeStream::UB, CG::r(r_elt), CG::r(r_tmp));
3306 PUSH_INSTR(frag, BytecodeStream::LTI, CG::r(r_agg), CG::r(r_tmp), CG::r(r_test));
3307 PUSH_INSTR(frag, BytecodeStream::JMPIFNOT, CG::r(r_test), CG::l(l_end));
3308 PUSH_INSTR(frag, BytecodeStream::MOV, CG::r(r_tmp), CG::r(r_agg));
3309 PUSH_LABEL(frag, l_end);
3310 });
3311
3312 return CG::Binding(r_agg, b_A.second);
3313}
3314
3315CG::Binding bind_dom_array(Call* call, Mode ctx, CodeGen& cg, CG_Builder& frag) {
3316 assert(call->n_args() == 1);
3317 CG::Binding b_A(CG::bind(call->arg(0), cg, frag));
3318
3319 int r_agg(GET_REG(cg));
3320 OPEN_VEC(cg, frag);
3321 CLOSE_AGG(cg, frag);
3322 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r_agg));
3323
3324 int r_tmp(GET_REG(cg));
3325 ITER_ARRAY(cg, frag, b_A.first, [&](CodeGen& cg, CG_Builder& frag, int r_elt) {
3326 PUSH_INSTR(frag, BytecodeStream::DOM, CG::r(r_elt), CG::r(r_tmp));
3327 PUSH_INSTR(frag, BytecodeStream::UNION, CG::r(r_agg), CG::r(r_tmp), CG::r(r_agg));
3328 });
3329
3330 return {r_agg, b_A.second};
3331}
3332
3333CG::Binding bind_index_set(Call* call, Mode ctx, CodeGen& cg, CG_Builder& frag) {
3334 assert(call->n_args() == 1);
3335 assert(call->arg(0)->type().dim() == 1);
3336 CG::Binding b_arg(CG::bind(call->arg(0), cg, frag));
3337
3338 PUSH_INSTR(frag, BytecodeStream::BUILTIN, cg.find_builtin("index_set"), CG::r(b_arg.first),
3339 CG::r(bind_cst(1, cg, frag)));
3340 int r(GET_REG(cg));
3341 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r));
3342
3343 return {r, b_arg.second};
3344}
3345
3346template <int X, int Y>
3347CG::Binding bind_index_set_XofY(Call* call, Mode ctx, CodeGen& cg, CG_Builder& frag) {
3348 assert(call->n_args() == 1);
3349 CG::Binding b_arg(CG::bind(call->arg(0), cg, frag));
3350
3351 PUSH_INSTR(frag, BytecodeStream::BUILTIN, cg.find_builtin("index_set"), CG::r(b_arg.first),
3352 CG::r(bind_cst(X, cg, frag)));
3353 int r(GET_REG(cg));
3354 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r));
3355
3356 return {r, b_arg.second};
3357}
3358
3359CG::Binding bind_bool2int(Call* call, Mode ctx, CodeGen& cg, CG_Builder& frag) {
3360 assert(call->n_args() == 1);
3361 return CG::force_or_bind(call->arg(0), BytecodeProc::FUN, cg, frag);
3362}
3363CG::Binding bind_int2float(Call* call, Mode ctx, CodeGen& cg, CG_Builder& frag) {
3364 assert(call->n_args() == 1);
3365 return CG::bind(call->arg(0), cg, frag);
3366}
3367
3368CG::Binding bind_call(Call* call, Mode ctx, CodeGen& cg, CG_Builder& frag);
3369CG_Cond::T compile_call(Call* call, Mode ctx, CodeGen& cg, CG_Builder& frag);
3370
3371CG::Binding bind_set_max(Call* call, Mode ctx, CodeGen& cg, CG_Builder& frag) {
3372 assert(call->type().ispar());
3373 assert(call->n_args() == 1);
3374 CG::Binding b_A(CG::bind(call->arg(0), cg, frag));
3375 int r(GET_REG(cg));
3376 int r_sz(GET_REG(cg));
3377 PUSH_INSTR(frag, BytecodeStream::LENGTH, CG::r(b_A.first), CG::r(r_sz));
3378 int l_fst(GET_LABEL(cg));
3379 PUSH_INSTR(frag, BytecodeStream::LEI, CG::r(bind_cst(0, cg, frag)), CG::r(r_sz), CG::r(r));
3380 PUSH_INSTR(frag, BytecodeStream::JMPIF, CG::r(r), CG::l(l_fst));
3381 PUSH_INSTR(frag, BytecodeStream::ABORT);
3382 PUSH_LABEL(frag, l_fst);
3383
3384 PUSH_INSTR(frag, BytecodeStream::GET_VEC, CG::r(b_A.first), CG::r(r_sz), CG::r(r));
3385
3386 // TODO: Also should not be allowed on empty sets
3387 return CG::Binding(r, b_A.second);
3388};
3389
3390CG::Binding bind_max(Call* call, Mode ctx, CodeGen& cg, CG_Builder& frag) {
3391 assert(call->type().ispar());
3392 assert(call->n_args() == 1);
3393 CG::Binding b_A(CG::bind(call->arg(0), cg, frag));
3394
3395 int r(GET_REG(cg));
3396 PUSH_INSTR(frag, BytecodeStream::BUILTIN, cg.find_builtin("infinity"),
3397 CG::r(bind_cst(0, cg, frag)));
3398 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r));
3399
3400 int r_test(GET_REG(cg));
3401 int l_end(GET_LABEL(cg));
3402 ITER_ARRAY(cg, frag, b_A.first, [&](CodeGen& cg, CG_Builder& frag, int r_elt) {
3403 PUSH_INSTR(frag, BytecodeStream::LTI, CG::r(r), CG::r(r_elt), CG::r(r_test));
3404 PUSH_INSTR(frag, BytecodeStream::JMPIFNOT, CG::r(r_test), CG::l(l_end));
3405 PUSH_INSTR(frag, BytecodeStream::MOV, CG::r(r_elt), CG::r(r));
3406 PUSH_LABEL(frag, l_end);
3407 });
3408
3409 // TODO: Fail if array size < 1
3410 return CG::Binding(r, CG_Cond::ttt());
3411}
3412
3413CG::Binding bind_arg_max(Call* call, Mode ctx, CodeGen& cg, CG_Builder& frag) {
3414 assert(call->n_args() == 1);
3415 CG::Binding b_A(CG::bind(call->arg(0), cg, frag));
3416 int r(GET_REG(cg));
3417 int r_elt(GET_REG(cg));
3418 int r_v(GET_REG(cg));
3419 int r_test(GET_REG(cg));
3420 int r_index(GET_REG(cg));
3421
3422 PUSH_INSTR(frag, BytecodeStream::BUILTIN, cg.find_builtin("index_set"), CG::r(b_A.first),
3423 CG::r(bind_cst(1, cg, frag)));
3424 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r_index));
3425 PUSH_INSTR(frag, BytecodeStream::BUILTIN, cg.find_builtin("infinity"),
3426 CG::r(bind_cst(0, cg, frag)));
3427 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r_v));
3428
3429 int l_end(GET_LABEL(cg));
3430 ITER_SET(cg, frag, r_index, [&](CodeGen& cg, CG_Builder& frag, int r_i) {
3431 // Array access should be valid since we are using the actual index set.
3432 PUSH_INSTR(frag, BytecodeStream::GET_ARRAY, CG::i(1), CG::r(b_A.first), CG::r(r_i),
3433 CG::r(r_elt), CG::r(r_test));
3434 PUSH_INSTR(frag, BytecodeStream::LTI, CG::r(r_v), CG::r(r_elt), CG::r(r_test));
3435 PUSH_INSTR(frag, BytecodeStream::JMPIFNOT, CG::r(r_test), CG::l(l_end));
3436 PUSH_INSTR(frag, BytecodeStream::MOV, CG::r(r_elt), CG::r(r_v));
3437 PUSH_INSTR(frag, BytecodeStream::MOV, CG::r(r_i), CG::r(r));
3438 PUSH_LABEL(frag, l_end);
3439 });
3440
3441 // TODO: Fail if array size < 1
3442 return CG::Binding(r, CG_Cond::ttt());
3443}
3444
3445CG::Binding bind_arg_min(Call* call, Mode ctx, CodeGen& cg, CG_Builder& frag) {
3446 assert(call->n_args() == 1);
3447 CG::Binding b_A(CG::bind(call->arg(0), cg, frag));
3448 int r(GET_REG(cg));
3449 int r_elt(GET_REG(cg));
3450 int r_v(GET_REG(cg));
3451 int r_test(GET_REG(cg));
3452 int r_index(GET_REG(cg));
3453
3454 PUSH_INSTR(frag, BytecodeStream::BUILTIN, cg.find_builtin("index_set"), CG::r(b_A.first),
3455 CG::r(bind_cst(1, cg, frag)));
3456 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r_index));
3457 PUSH_INSTR(frag, BytecodeStream::BUILTIN, cg.find_builtin("infinity"),
3458 CG::r(bind_cst(1, cg, frag)));
3459 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r_v));
3460
3461 int l_end(GET_LABEL(cg));
3462 ITER_SET(cg, frag, r_index, [&](CodeGen& cg, CG_Builder& frag, int r_i) {
3463 // Array access should be valid since we are using the actual index set.
3464 PUSH_INSTR(frag, BytecodeStream::GET_ARRAY, CG::i(1), CG::r(b_A.first), CG::r(r_i),
3465 CG::r(r_elt), CG::r(r_test));
3466 PUSH_INSTR(frag, BytecodeStream::LTI, CG::r(r_elt), CG::r(r_v), CG::r(r_test));
3467 PUSH_INSTR(frag, BytecodeStream::JMPIFNOT, CG::r(r_test), CG::l(l_end));
3468 PUSH_INSTR(frag, BytecodeStream::MOV, CG::r(r_elt), CG::r(r_v));
3469 PUSH_INSTR(frag, BytecodeStream::MOV, CG::r(r_i), CG::r(r));
3470 PUSH_LABEL(frag, l_end);
3471 });
3472
3473 // TODO: Fail if array size < 1
3474 return CG::Binding(r, CG_Cond::ttt());
3475}
3476
3477CG::Binding bind_set_min(Call* call, Mode ctx, CodeGen& cg, CG_Builder& frag) {
3478 assert(call->type().ispar());
3479 assert(call->n_args() == 1);
3480 CG::Binding b_A(CG::bind(call->arg(0), cg, frag));
3481 int r(GET_REG(cg));
3482 int r_sz(GET_REG(cg));
3483 PUSH_INSTR(frag, BytecodeStream::LENGTH, CG::r(b_A.first), CG::r(r_sz));
3484 int l_fst(GET_LABEL(cg));
3485 PUSH_INSTR(frag, BytecodeStream::LEI, CG::r(bind_cst(1, cg, frag)), CG::r(r_sz), CG::r(r));
3486 PUSH_INSTR(frag, BytecodeStream::JMPIF, CG::r(r), CG::l(l_fst));
3487 PUSH_INSTR(frag, BytecodeStream::ABORT);
3488
3489 PUSH_LABEL(frag, l_fst);
3490 PUSH_INSTR(frag, BytecodeStream::GET_VEC, CG::r(b_A.first), CG::r(bind_cst(1, cg, frag)),
3491 CG::r(r));
3492
3493 return CG::Binding(r, CG_Cond::ttt());
3494}
3495
3496CG::Binding bind_min(Call* call, Mode ctx, CodeGen& cg, CG_Builder& frag) {
3497 assert(call->type().ispar());
3498 assert(call->n_args() == 1);
3499 CG::Binding b_A(CG::bind(call->arg(0), cg, frag));
3500
3501 int r(GET_REG(cg));
3502 PUSH_INSTR(frag, BytecodeStream::BUILTIN, cg.find_builtin("infinity"),
3503 CG::r(bind_cst(1, cg, frag)));
3504 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r));
3505
3506 int r_test(GET_REG(cg));
3507 int l_end(GET_LABEL(cg));
3508 ITER_ARRAY(cg, frag, b_A.first, [&](CodeGen& cg, CG_Builder& frag, int r_elt) {
3509 PUSH_INSTR(frag, BytecodeStream::LTI, CG::r(r_elt), CG::r(r), CG::r(r_test));
3510 PUSH_INSTR(frag, BytecodeStream::JMPIFNOT, CG::r(r_test), CG::l(l_end));
3511 PUSH_INSTR(frag, BytecodeStream::MOV, CG::r(r_elt), CG::r(r));
3512 PUSH_LABEL(frag, l_end);
3513 });
3514
3515 return CG::Binding(r, CG_Cond::ttt());
3516}
3517
3518CG::Binding bind_card(Call* call, Mode ctx, CodeGen& cg, CG_Builder& frag) {
3519 assert(call->type().ispar());
3520 assert(call->n_args() == 1);
3521
3522 CG::Binding b_A(CG::bind(call->arg(0), cg, frag));
3523 int r(GET_REG(cg));
3524 int r_i(GET_REG(cg));
3525 int r_sz(GET_REG(cg));
3526 int r_e(GET_REG(cg));
3527 PUSH_INSTR(frag, BytecodeStream::IMMI, CG::i(0), CG::r(r));
3528
3529 PUSH_INSTR(frag, BytecodeStream::IMMI, CG::i(1), CG::r(r_i));
3530 PUSH_INSTR(frag, BytecodeStream::LENGTH, CG::r(b_A.first), CG::r(r_sz));
3531 int l_hd(GET_LABEL(cg));
3532 int l_tl(GET_LABEL(cg));
3533 PUSH_INSTR(frag, BytecodeStream::LTI, CG::r(r_i), CG::r(r_sz), CG::r(r_e));
3534 PUSH_INSTR(frag, BytecodeStream::JMPIFNOT, CG::r(r_e), CG::l(l_tl));
3535
3536 PUSH_LABEL(frag, l_hd);
3537 PUSH_INSTR(frag, BytecodeStream::INCI, CG::r(r));
3538 PUSH_INSTR(frag, BytecodeStream::GET_VEC, CG::r(b_A.first), CG::r(r_i), CG::r(r_e));
3539 PUSH_INSTR(frag, BytecodeStream::SUBI, CG::r(r), CG::r(r_e), CG::r(r));
3540 PUSH_INSTR(frag, BytecodeStream::INCI, CG::r(r_i));
3541 PUSH_INSTR(frag, BytecodeStream::GET_VEC, CG::r(b_A.first), CG::r(r_i), CG::r(r_e));
3542 PUSH_INSTR(frag, BytecodeStream::INCI, CG::r(r_i));
3543 PUSH_INSTR(frag, BytecodeStream::ADDI, CG::r(r), CG::r(r_e), CG::r(r));
3544
3545 PUSH_INSTR(frag, BytecodeStream::LTI, CG::r(r_i), CG::r(r_sz), CG::r(r_e));
3546 PUSH_INSTR(frag, BytecodeStream::JMPIF, CG::r(r_e), CG::l(l_hd));
3547 PUSH_LABEL(frag, l_tl);
3548 return CG::Binding(r, b_A.second);
3549}
3550
3551CG::Binding bind_internal(Call* call, Mode ctx, CodeGen& cg, CG_Builder& frag) {
3552 std::string name = call->decl()->id().str();
3553 CG_ProcID proc = cg.find_builtin(name);
3554 int r_res(GET_REG(cg));
3555
3556 std::vector<CG_Value> r_args(call->n_args());
3557 std::vector<CG_Cond::T> p_args(call->n_args());
3558 for (int i = 0; i < call->n_args(); ++i) {
3559 CG::Binding b_arg(CG::bind(call->arg(i), cg, frag));
3560 r_args[i] = CG::r(b_arg.first);
3561 p_args[i] = b_arg.second;
3562 }
3563
3564 // Push BUILTIN instruction with the correct id
3565 PUSH_INSTR(frag, BytecodeStream::BUILTIN, proc);
3566 // Append instruction with register arguments
3567 CG_Instr& i = frag.instrs.back();
3568 PUSH_INSTR_OPERAND(i, r_args);
3569
3570 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r_res));
3571
3572 return {r_res, CG_Cond::forall(ctx, p_args)};
3573}
3574
3575CG_Cond::T eval_context_is_root(Call* call, Mode ctx, CodeGen& cg, CG_Builder& frag) {
3576 // TODO: I'm not sure this is actually correct....
3577 assert(call->n_args() == 1);
3578 CG::Mode arg_ctx(BytecodeProc::FUN);
3579 try {
3580 arg_ctx = cg.mode_map.at(call->arg(0));
3581 } catch (const std::out_of_range& exn) {
3582 }
3583
3584 if (arg_ctx == BytecodeProc::ROOT) {
3585 return CG_Cond::ttt();
3586 } else {
3587 return CG_Cond::fff();
3588 }
3589}
3590
3591CG_Cond::T eval_has_bounds(Call* call, Mode ctx, CodeGen& cg, CG_Builder& frag) {
3592 // TODO: Actual implementation!
3593
3594 return CG_Cond::ttt();
3595}
3596
3597CG::Binding bind_TODO(Call* call, Mode ctx, CodeGen& cg, CG_Builder& frag) {
3598 PUSH_INSTR(frag, BytecodeStream::ABORT);
3599 return {0, CG_Cond::fff()};
3600}
3601CG_Cond::T eval_TODO(Call* call, Mode ctx, CodeGen& cg, CG_Builder& frag) {
3602 PUSH_INSTR(frag, BytecodeStream::ABORT);
3603 return CG_Cond::fff();
3604}
3605
3606template <int X>
3607CG_Cond::T eval_argX_only(Call* call, Mode ctx, CodeGen& cg, CG_Builder& frag) {
3608 return CG::compile(call->arg(X - 1), cg, frag);
3609}
3610
3611builtin_table init_builtins(void) {
3612 builtin_table tbl;
3613 Constants& c(constants());
3614 tbl.insert(std::make_pair(c.ids.sum.str(), builtin_t{eval_error_b, bind_sum}));
3615 tbl.insert(std::make_pair(c.ids.exists.str(), builtin_t{eval_exists, bind_error_g}));
3616 tbl.insert(std::make_pair(c.ids.forall.str(), builtin_t{eval_forall, bind_error_g}));
3617 tbl.insert(std::make_pair(c.ids.assert.str(), builtin_t{eval_assert_b, bind_assert_g}));
3618 tbl.insert(std::make_pair("arrayXd", builtin_t{eval_error_b, bind_arrayXd}));
3619 tbl.insert(std::make_pair("array1d", builtin_t{eval_error_b, bind_array1d}));
3620 tbl.insert(std::make_pair("array2d", builtin_t{eval_error_b, bind_arrayNd<2>}));
3621 tbl.insert(std::make_pair("array3d", builtin_t{eval_error_b, bind_arrayNd<3>}));
3622 tbl.insert(std::make_pair("array4d", builtin_t{eval_error_b, bind_arrayNd<4>}));
3623 tbl.insert(std::make_pair("array5d", builtin_t{eval_error_b, bind_arrayNd<5>}));
3624 tbl.insert(std::make_pair("array6d", builtin_t{eval_error_b, bind_arrayNd<6>}));
3625 tbl.insert(std::make_pair("array7d", builtin_t{eval_error_b, bind_arrayNd<7>}));
3626 tbl.insert(std::make_pair("array8d", builtin_t{eval_error_b, bind_arrayNd<8>}));
3627 tbl.insert(std::make_pair("array9d", builtin_t{eval_error_b, bind_arrayNd<9>}));
3628 tbl.insert(std::make_pair("array_union", builtin_t{eval_error_b, bind_array_union}));
3629 tbl.insert(std::make_pair("index_set", builtin_t{eval_error_b, bind_index_set}));
3630 tbl.insert(std::make_pair("index_set_1of2", builtin_t{eval_error_b, bind_index_set_XofY<1, 2>}));
3631 tbl.insert(std::make_pair("index_set_2of2", builtin_t{eval_error_b, bind_index_set_XofY<2, 2>}));
3632 tbl.insert(std::make_pair("index_set_1of3", builtin_t{eval_error_b, bind_index_set_XofY<1, 3>}));
3633 tbl.insert(std::make_pair("index_set_2of3", builtin_t{eval_error_b, bind_index_set_XofY<2, 3>}));
3634 tbl.insert(std::make_pair("index_set_3of3", builtin_t{eval_error_b, bind_index_set_XofY<3, 3>}));
3635 tbl.insert(std::make_pair("index_set_1of4", builtin_t{eval_error_b, bind_index_set_XofY<1, 4>}));
3636 tbl.insert(std::make_pair("index_set_2of4", builtin_t{eval_error_b, bind_index_set_XofY<2, 4>}));
3637 tbl.insert(std::make_pair("index_set_3of4", builtin_t{eval_error_b, bind_index_set_XofY<3, 4>}));
3638 tbl.insert(std::make_pair("index_set_4of4", builtin_t{eval_error_b, bind_index_set_XofY<4, 4>}));
3639 tbl.insert(std::make_pair("length", builtin_t{eval_error_b, bind_length}));
3640 tbl.insert(std::make_pair("lb", builtin_t{eval_error_b, bind_lb}));
3641 tbl.insert(std::make_pair("ub", builtin_t{eval_error_b, bind_ub}));
3642 tbl.insert(std::make_pair("dom", builtin_t{eval_error_b, bind_dom}));
3643 tbl.insert(std::make_pair("lb_array", builtin_t{eval_error_b, bind_lb_array}));
3644 tbl.insert(std::make_pair("ub_array", builtin_t{eval_error_b, bind_ub_array}));
3645 tbl.insert(std::make_pair("dom_array", builtin_t{eval_error_b, bind_dom_array}));
3646 tbl.insert(std::make_pair("set2array", builtin_t{eval_error_b, bind_set2array}));
3647 tbl.insert(std::make_pair("dom_bounds_array", builtin_t{eval_error_b, bind_dom_bounds_array}));
3648 tbl.insert(std::make_pair("arg_max", builtin_t{eval_error_b, bind_arg_max}));
3649 tbl.insert(std::make_pair("arg_min", builtin_t{eval_error_b, bind_arg_min}));
3650 tbl.insert(std::make_pair("card", builtin_t{eval_error_b, bind_card}));
3651 tbl.insert(std::make_pair(c.ids.bool2int.str(), builtin_t{eval_error_b, bind_bool2int}));
3652 tbl.insert(std::make_pair(c.ids.int2float.str(), builtin_t{eval_error_b, bind_bool2int}));
3653 tbl.insert(std::make_pair("uniform", builtin_t{eval_error_b, bind_internal}));
3654 tbl.insert(std::make_pair("sol", builtin_t{eval_error_b, bind_internal}));
3655 tbl.insert(std::make_pair("sort_by", builtin_t{eval_error_b, bind_internal}));
3656 tbl.insert(std::make_pair("floor", builtin_t{eval_error_b, bind_internal}));
3657 tbl.insert(std::make_pair("ceil", builtin_t{eval_error_b, bind_internal}));
3658 tbl.insert(std::make_pair("mzn_in_root_context", builtin_t{eval_context_is_root, bind_error_g}));
3659 tbl.insert(std::make_pair("has_bounds", builtin_t{eval_has_bounds, bind_error_g}));
3660 tbl.insert(std::make_pair("is_fixed", builtin_t{eval_isfixed_b, bind_error_g}));
3661 tbl.insert(std::make_pair("fix", builtin_t{eval_fix, bind_fix}));
3662 tbl.insert(std::make_pair("array_Xd", builtin_t{eval_error_b, bind_internal}));
3663 tbl.insert(std::make_pair("slice_Xd", builtin_t{eval_error_b, bind_internal}));
3664 tbl.insert(std::make_pair("internal_sort", builtin_t{eval_error_b, bind_internal}));
3665 tbl.insert(std::make_pair("internal_max", builtin_t{eval_error_b, bind_max}));
3666 tbl.insert(std::make_pair("internal_set_max", builtin_t{eval_error_b, bind_set_max}));
3667 tbl.insert(std::make_pair("internal_min", builtin_t{eval_error_b, bind_min}));
3668 tbl.insert(std::make_pair("internal_set_min", builtin_t{eval_error_b, bind_set_min}));
3669 tbl.insert(
3670 std::make_pair("symmetry_breaking_constraint", builtin_t{eval_argX_only<1>, bind_error_g}));
3671 tbl.insert(std::make_pair("redundant_constraint", builtin_t{eval_argX_only<1>, bind_error_g}));
3672 // OPTIONAL TYPE INTERNALS
3673 tbl.insert(std::make_pair("reverse_map", builtin_t{eval_error_b, bind_TODO}));
3674 tbl.insert(std::make_pair("occurs", builtin_t{eval_TODO, bind_error_g}));
3675 tbl.insert(std::make_pair("absent", builtin_t{eval_TODO, bind_error_g}));
3676 tbl.insert(std::make_pair("deopt", builtin_t{eval_error_b, bind_TODO}));
3677 return tbl;
3678}
3679builtin_table& builtins(void) {
3680 static builtin_table tbl(init_builtins());
3681 return tbl;
3682}
3683
3684CG::Binding CG::bind(Id* x, Mode ctx, CodeGen& cg, CG_Builder& frag) {
3685 try {
3686 return CG::Binding(cg.env().lookup(x->v()).first, CG_Cond::ttt());
3687 } catch (const CG_Env<CodeGen::Binding>::NotFound& exn) {
3688 VarDecl* vd = follow_id_to_decl(x)->cast<VarDecl>();
3689 int g = cg.find_global(vd);
3690 int r(GET_REG(cg));
3691 PUSH_INSTR(frag, BytecodeStream::LOAD_GLOBAL, CG::g(g), CG::r(r));
3692 return CG::Binding(r, CG_Cond::ttt());
3693 }
3694}
3695
3696CG::Binding CG::bind(SetLit* sl, Mode ctx, CodeGen& cg, CG_Builder& frag) {
3697 bool is_vec(false);
3698 OPEN_VEC(cg, frag);
3699 if (IntSetVal* s = sl->isv()) {
3700 int r_t(GET_REG(cg));
3701 for (int ii = 0; ii < s->size(); ++ii) {
3702 IntVal l(s->min(ii));
3703 IntVal u(s->max(ii));
3704 if (l.isFinite()) {
3705 PUSH_INSTR(frag, BytecodeStream::IMMI, CG::i(l.toInt()), CG::r(r_t));
3706 } else {
3707 assert(l.isMinusInfinity());
3708 PUSH_INSTR(frag, BytecodeStream::BUILTIN, cg.find_builtin("infinity"),
3709 CG::r(bind_cst(0, cg, frag)));
3710 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r_t));
3711 }
3712 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(r_t));
3713 if (u.isFinite()) {
3714 PUSH_INSTR(frag, BytecodeStream::IMMI, CG::i(u.toInt()), CG::r(r_t));
3715 } else {
3716 assert(u.isPlusInfinity());
3717 PUSH_INSTR(frag, BytecodeStream::BUILTIN, cg.find_builtin("infinity"),
3718 CG::r(bind_cst(1, cg, frag)));
3719 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r_t));
3720 }
3721 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(r_t));
3722 }
3723 } else {
3724 is_vec = true;
3725 int sz = sl->v().size();
3726 int r_t(GET_REG(cg));
3727 for (int ii = 0; ii < sz; ii++) {
3728 // Assumes the set is sorted.
3729 /*
3730 IntLit* k(l->v()[ii]->template cast<IntLit>());
3731 assert(k);
3732 PUSH_INSTR(frag, BytecodeStream::IMMI, CG::i(k->v().toInt()), CG::r(r_t));
3733 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(r_t));
3734 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(r_t));
3735 */
3736 CG::Binding b(CG::bind(sl->v()[ii], cg, frag)); // Ignores any partiality.
3737 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(b.first));
3738 }
3739 }
3740 CLOSE_AGG(cg, frag);
3741 int r(GET_REG(cg));
3742 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r));
3743 if (is_vec) PUSH_INSTR(frag, BytecodeStream::MAKE_SET, CG::r(r), CG::r(r));
3744 return CG::Binding(r, CG_Cond::ttt());
3745}
3746
3747CG::Binding CG::bind(ArrayLit* a, Mode ctx, CodeGen& cg, CG_Builder& frag) {
3748 // Build up the array.
3749 std::vector<std::pair<IntLit*, int>> r_vec;
3750 std::vector<CG_Cond::T> p_vec;
3751
3752 int sz(a->size());
3753 for (int ii = 0; ii < sz; ++ii) {
3754 if ((*a)[ii]->type().isbool()) {
3755 CG_Cond::T c(CG::compile((*a)[ii], cg, frag));
3756 if (!c.get()) {
3757 if (!c.sign()) {
3758 r_vec.emplace_back(nullptr, bind_cst(1, cg, frag));
3759 } else {
3760 r_vec.emplace_back(nullptr, bind_cst(0, cg, frag));
3761 }
3762 } else {
3763 r_vec.emplace_back(nullptr, CG::force(c, ctx, cg, frag));
3764 }
3765 } else if (auto il = (*a)[ii]->dyn_cast<IntLit>()) {
3766 // Avoid lookup cost when constructing large array literals
3767 r_vec.emplace_back(il, 0xdeadbeef);
3768 } else {
3769 Binding b_ii(CG::bind((*a)[ii], cg, frag));
3770 r_vec.emplace_back(nullptr, b_ii.first);
3771 p_vec.push_back(b_ii.second);
3772 }
3773 }
3774
3775 // Build Array
3776 int r(GET_REG(cg));
3777 OPEN_VEC(cg, frag);
3778 for (auto r_c : r_vec) {
3779 if (r_c.first) {
3780 assert(r_c.first->v().isFinite());
3781 PUSH_INSTR(frag, BytecodeStream::IMMI, CG::i(r_c.first->v().toInt()), CG::r(r));
3782 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(r));
3783 } else {
3784 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(r_c.second));
3785 }
3786 }
3787 CLOSE_AGG(cg, frag);
3788 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r));
3789
3790 // Add index set if required
3791 if (!(a->dims() == 1 && a->min(0))) {
3792 int rI;
3793 if (a->dims() == 1) {
3794 rI = (locate_range(a->min(0), a->max(0), cg, frag));
3795 } else {
3796 rI = GET_REG(cg);
3797 OPEN_VEC(cg, frag);
3798 for (int ii = 0; ii < a->dims(); ++ii) {
3799 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(bind_cst(a->min(ii), cg, frag)));
3800 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(bind_cst(a->max(ii), cg, frag)));
3801 }
3802 CLOSE_AGG(cg, frag);
3803 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(rI));
3804 }
3805
3806 // Combine array and index sets
3807 PUSH_INSTR(frag, BytecodeStream::BUILTIN, cg.find_builtin("array_Xd"), CG::r(r), CG::r(rI));
3808 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r));
3809 }
3810
3811 return {r, CG_Cond::forall(ctx, p_vec)};
3812}
3813
3814std::pair<int, CG_Cond::T> execute_array_access(int r_A, std::vector<int> r_idxs, CodeGen& cg,
3815 CG_Builder& frag) {
3816 int sz = r_idxs.size();
3817 int r(GET_REG(cg));
3818 int r_cond(GET_REG(cg));
3819 PUSH_INSTR(frag, BytecodeStream::GET_ARRAY, CG::i(sz), CG::r(r_A));
3820 std::vector<CG_Value> r_args(sz + 2);
3821 for (int ii = 0; ii < sz; ++ii) {
3822 r_args[ii] = CG::r(r_idxs[ii]);
3823 }
3824 r_args[sz] = CG::r(r);
3825 r_args[sz + 1] = CG::r(r_cond);
3826 CG_Instr& i = frag.instrs.back();
3827 PUSH_INSTR_OPERAND(i, r_args);
3828 return {r, CG_Cond::reg(r_cond, true)};
3829}
3830
3831CG::Binding CG::bind(ArrayAccess* a, Mode ctx, CodeGen& cg, CG_Builder& frag) {
3832 GCLock lock;
3833 // If the array elements are Boolean, we need to check for partiality
3834 // in the indices, and that the accesses are within-range.
3835 ASTExprVec<Expression> idx(a->idx());
3836 Expression* A(a->v());
3837 int sz(idx.size());
3838
3839 bool is_var = false;
3840 for (int ii = 0; ii < sz; ++ii) {
3841 is_var = is_var || idx[ii]->type().isvar();
3842 }
3843
3844 // Evaluate the indices, put them in registers.
3845 // Collect partiality of the expression.
3846 std::vector<CG_Cond::T> cond;
3847
3848 // Now evaluate the array body, and emit the indices.
3849 std::vector<int> r_idxs(sz);
3850 for (int ii = 0; ii < sz; ++ii) {
3851 CG::Binding b(CG::bind(idx[ii], cg, frag));
3852 r_idxs[ii] = b.first;
3853 cond.push_back(b.second);
3854 }
3855
3856 Binding b_A(CG::bind(A, cg, frag));
3857 int r_A(b_A.first);
3858 cond.push_back(b_A.second);
3859
3860 if (is_var) {
3861 int r = GET_REG(cg);
3862
3863 std::vector<Type> types(sz + 1, Type::varint());
3864 types[sz] = Type::varint(sz);
3865 auto fun = find_call_fun(cg, {"element"}, Type::varint(), types, BytecodeProc::FUN);
3866 assert(std::get<1>(fun) == BytecodeProc::FUN);
3867
3868 std::vector<CG_Value> r_args(sz + 1);
3869 for (int ii = 0; ii < sz; ++ii) {
3870 r_args[ii] = CG::r(r_idxs[ii]);
3871 }
3872 r_args[sz] = CG::r(r_A);
3873
3874 // Push CALL instruction with the correct id
3875 PUSH_INSTR(frag, BytecodeStream::CALL, BytecodeProc::FUN, std::get<0>(fun),
3876 CG::i(!std::get<2>(fun)));
3877 // Append instruction with register arguments
3878 CG_Instr& i = frag.instrs.back();
3879 PUSH_INSTR_OPERAND(i, r_args);
3880
3881 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r));
3882 return {r, CG_Cond::forall(ctx, cond)};
3883 } else {
3884 // Just read the vector, and get the appropriate element.
3885 int r;
3886 CG_Cond::T ncond;
3887 std::tie(r, ncond) = execute_array_access(r_A, r_idxs, cg, frag);
3888 cond.push_back(ncond);
3889 return {r, CG_Cond::forall(ctx, cond)};
3890 }
3891}
3892
3893int make_vec(CodeGen& cg, CG_Builder& frag, const std::vector<int>& regs) {
3894 OPEN_VEC(cg, frag);
3895 for (int r : regs) PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(r));
3896 CLOSE_AGG(cg, frag);
3897 int r_vec(GET_REG(cg));
3898 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r_vec));
3899 return r_vec;
3900}
3901
3902void call_clause(CodeGen& cg, CG_Builder& frag, Mode ctx, const std::vector<int>& pos,
3903 const std::vector<int>& neg) {
3904 GCLock lock;
3905 // Build the arguments vectors.
3906 int r_pos(make_vec(cg, frag, pos));
3907 int r_neg(make_vec(cg, frag, neg));
3908 auto fun =
3909 find_call_fun(cg, {"clause"}, Type::varbool(), {Type::varbool(1), Type::varbool(1)}, ctx);
3910 assert(BytecodeProc::is_neg(ctx) == BytecodeProc::is_neg(std::get<1>(fun)));
3911 PUSH_INSTR(frag, BytecodeStream::CALL, std::get<1>(fun), std::get<0>(fun),
3912 CG::i(!std::get<2>(fun)), CG::r(r_pos), CG::r(r_neg));
3913}
3914
3915int deinterlace(CodeGen& cg, CG_Builder& frag, int vec, int width, int offset) {
3916 int r_sz(GET_REG(cg));
3917 int r_slice(GET_REG(cg));
3918
3919 OPEN_VEC(cg, frag);
3920 // int r_i(CG::locate_immi(1 + offset, cg, frag));
3921 // int r_step(CG::locate_immi(width, cg, frag));
3922 int r_i(bind_cst(1 + offset, cg, frag));
3923 int r_step(bind_cst(width, cg, frag));
3924 int r_elt(GET_REG(cg));
3925
3926 PUSH_INSTR(frag, BytecodeStream::LENGTH, CG::r(vec), CG::r(r_sz));
3927 int l_hd(GET_LABEL(cg));
3928 int l_tl(GET_LABEL(cg));
3929 PUSH_INSTR(frag, BytecodeStream::LEI, CG::r(r_i), CG::r(r_sz), CG::r(r_elt));
3930 PUSH_INSTR(frag, BytecodeStream::JMPIFNOT, CG::r(r_elt), CG::l(l_tl));
3931 PUSH_LABEL(frag, l_hd);
3932 PUSH_INSTR(frag, BytecodeStream::GET_VEC, CG::r(vec), CG::r(r_i), CG::r(r_elt));
3933 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(r_elt));
3934 PUSH_INSTR(frag, BytecodeStream::ADDI, CG::r(r_i), CG::r(r_step), CG::r(r_i));
3935 PUSH_INSTR(frag, BytecodeStream::LEI, CG::r(r_i), CG::r(r_sz), CG::r(r_elt));
3936 PUSH_INSTR(frag, BytecodeStream::JMPIF, CG::r(r_elt), CG::l(l_hd));
3937 PUSH_LABEL(frag, l_tl);
3938 CLOSE_AGG(cg, frag);
3939 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r_slice));
3940
3941 return r_slice;
3942}
3943
3944/*
3945inline int reg_k(int k, CodeGen& cg, CG_Builder& frag, int& r) {
3946 if(r == -1)
3947 r = CG::locate_immi(1, cg, frag);
3948 return r;
3949}
3950*/
3951
3952CG::Binding CG::bind(ITE* ite, Mode ctx, CodeGen& cg, CG_Builder& frag) {
3953 int sz(ite->size());
3954 int r_one(bind_cst(1, cg, frag));
3955
3956 bool all_par = true;
3957 for (int ii = 0; ii < sz; ++ii) {
3958 if (!ite->e_if(ii)->type().ispar()) {
3959 all_par = false;
3960 break;
3961 }
3962 }
3963
3964 if (all_par) {
3965 int l_end(GET_LABEL(cg));
3966 int r_ret(GET_REG(cg));
3967 int r_cond(GET_REG(cg));
3968 PUSH_INSTR(frag, BytecodeStream::IMMI, CG::i(1), CG::r(r_cond));
3969
3970 bool is_total = true;
3971 // We need to interfere with the env, here, because stuff may not be available.
3972 // Except, ite->e_if(0) will always be available.
3973 for (int ii = 0; ii < sz; ++ii) {
3974 int r_sel = CG::force(CG::compile(ite->e_if(ii), cg, frag), BytecodeProc::FUN, cg, frag);
3975 int l_cont(GET_LABEL(cg));
3976 PUSH_INSTR(frag, BytecodeStream::JMPIFNOT, CG::r(r_sel), CG::l(l_cont));
3977 cg.env_push();
3978 if (!ite->e_then(ii)->type().ispar()) all_par = false;
3979 CG::Binding b_res(CG::bind(ite->e_then(ii), cg, frag));
3980 if (b_res.second.get()) {
3981 is_total = false;
3982 int r_condii(CG::force(b_res.second, ctx, cg, frag));
3983 PUSH_INSTR(frag, BytecodeStream::MOV, CG::r(r_condii), CG::r(r_cond));
3984 } else if (!b_res.second.sign()) {
3985 PUSH_INSTR(frag, BytecodeStream::IMMI, CG::i(0), CG::r(r_cond));
3986 }
3987 PUSH_INSTR(frag, BytecodeStream::MOV, CG::r(b_res.first), CG::r(r_ret));
3988 PUSH_INSTR(frag, BytecodeStream::JMP, CG::l(l_end));
3989 cg.env_pop();
3990 cg.env_push();
3991 PUSH_LABEL(frag, l_cont);
3992 }
3993 // Else case.
3994 if (!ite->e_else()->type().ispar()) all_par = false;
3995
3996 CG::Binding b_res(CG::bind(ite->e_else(), cg, frag));
3997 if (b_res.second.get()) {
3998 is_total = false;
3999 int r_condii(CG::force(b_res.second, ctx, cg, frag));
4000 PUSH_INSTR(frag, BytecodeStream::MOV, CG::r(r_condii), CG::r(r_cond));
4001 } else if (!b_res.second.sign()) {
4002 PUSH_INSTR(frag, BytecodeStream::IMMI, CG::i(0), CG::r(r_cond));
4003 }
4004 PUSH_INSTR(frag, BytecodeStream::MOV, CG::r(b_res.first), CG::r(r_ret));
4005 PUSH_LABEL(frag, l_end);
4006 // Now kill the availability of all the expressions.
4007 for (int ii = 0; ii < sz; ++ii) {
4008 cg.env_pop();
4009 }
4010 return {r_ret, is_total ? CG_Cond::ttt() : CG_Cond::reg(r_cond, all_par)};
4011 } else {
4012 GCLock lock;
4013 std::vector<int> r_cond;
4014 std::vector<int> p_res;
4015 std::vector<int> r_res;
4016
4017 bool is_total = true;
4018 for (int ii = 0; ii < sz; ++ii) {
4019 r_cond.push_back(
4020 CG::force(CG::compile(ite->e_if(ii), cg, frag), BytecodeProc::FUN, cg, frag));
4021 CG::Binding b_res(CG::bind(ite->e_then(ii), cg, frag));
4022 r_res.push_back(b_res.first);
4023 // Make sure b_res.second is evaluated _outside_ the aggregation.
4024 if (b_res.second.get()) {
4025 is_total = false;
4026 p_res.push_back(CG::force(b_res.second, ctx, cg, frag));
4027 } else {
4028 if (b_res.second.sign()) {
4029 p_res.push_back(bind_cst(0, cg, frag));
4030 } else {
4031 p_res.push_back(r_one);
4032 }
4033 }
4034 }
4035 Binding b_final = CG::bind(ite->e_else(), cg, frag);
4036 r_cond.push_back(r_one);
4037 r_res.push_back(b_final.first);
4038 if (b_final.second.get()) {
4039 is_total = false;
4040 p_res.push_back(CG::force(b_final.second, ctx, cg, frag));
4041 } else {
4042 if (b_final.second.sign()) {
4043 p_res.push_back(bind_cst(0, cg, frag));
4044 } else {
4045 p_res.push_back(r_one);
4046 }
4047 }
4048
4049 int r_vec_cond(vec2array(r_cond, cg, frag));
4050
4051 int r_part;
4052 if (!is_total) {
4053 int r_vec_part(vec2array(p_res, cg, frag));
4054
4055 auto fun = find_call_fun(cg, {"if_then_else_partiality"}, Type::varbool(),
4056 {Type::varbool(1), Type::varbool(1)}, BytecodeProc::FUN);
4057 assert(std::get<1>(fun) == BytecodeProc::FUN);
4058
4059 PUSH_INSTR(frag, BytecodeStream::CALL, std::get<1>(fun), std::get<0>(fun),
4060 CG::i(!std::get<2>(fun)), CG::r(r_vec_cond), CG::r(r_vec_part));
4061 r_part = GET_REG(cg);
4062 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r_part));
4063 }
4064
4065 int r_vec_res(vec2array(r_res, cg, frag));
4066
4067 auto fun = find_call_fun(cg, {"if_then_else"}, Type::varint(),
4068 {Type::varbool(1), Type::varint(1)}, BytecodeProc::FUN);
4069 assert(std::get<1>(fun) == BytecodeProc::FUN);
4070
4071 int r_ret(GET_REG(cg));
4072 PUSH_INSTR(frag, BytecodeStream::CALL, std::get<1>(fun), std::get<0>(fun),
4073 CG::i(!std::get<2>(fun)), CG::r(r_vec_cond), CG::r(r_vec_res));
4074 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r_ret));
4075
4076 return {r_ret, is_total ? CG_Cond::ttt() : CG_Cond::reg(r_part, false)};
4077 }
4078}
4079
4080CG::Binding CG::bind(BinOp* b, Mode ctx, CodeGen& cg, CG_Builder& frag) {
4081 if (b->type().ispar()) {
4082 CG::Binding b_lhs(CG::force_or_bind(b->lhs(), ctx, cg, frag));
4083 CG::Binding b_rhs(CG::force_or_bind(b->rhs(), ctx, cg, frag));
4084 if (b->lhs()->type().isintset()) {
4085 int r = bind_binop_par_set(cg, frag, b->op(), b_lhs.first, b_rhs.first);
4086 return {r, CG_Cond::ttt()};
4087 }
4088 std::vector<CG_Cond::T> cond = {b_lhs.second, b_rhs.second};
4089
4090 int l_skip;
4091 int r_ret;
4092 if (b->op() == BOT_DIV || b->op() == BOT_IDIV || b->op() == BOT_MOD) {
4093 l_skip = GET_LABEL(cg);
4094 int r_cond = GET_REG(cg);
4095 r_ret = GET_REG(cg);
4096 PUSH_INSTR(frag, BytecodeStream::IMMI, CG::i(0), CG::r(r_ret));
4097 cond.push_back(CG_Cond::reg(r_cond, true));
4098 PUSH_INSTR(frag, BytecodeStream::EQI, CG::r(b_rhs.first), CG::r(r_ret), CG::r(r_cond));
4099 PUSH_INSTR(frag, BytecodeStream::NOT, CG::r(r_cond), CG::r(r_cond));
4100 PUSH_INSTR(frag, BytecodeStream::JMPIFNOT, CG::r(r_cond), CG::l(l_skip));
4101 }
4102 int r = bind_binop_par_int(cg, frag, b->op(), b_lhs.first, b_rhs.first);
4103 if (b->op() == BOT_DIV || b->op() == BOT_IDIV || b->op() == BOT_MOD) {
4104 PUSH_INSTR(frag, BytecodeStream::MOV, CG::r(r), CG::r(r_ret));
4105 r = r_ret;
4106 PUSH_LABEL(frag, l_skip);
4107 }
4108
4109 return {r, CG_Cond::forall(ctx, cond)};
4110 } else {
4111 std::vector<CG_Cond::T> partial;
4112 int r_lhs = CG::force_or_bind(b->lhs(), ctx, partial, cg, frag);
4113 int r_rhs = CG::force_or_bind(b->rhs(), ctx, partial, cg, frag);
4114
4115 int r = GET_REG(cg);
4116 bind_binop_var(cg, frag, BytecodeProc::FUN, b->op(), r_lhs, r_rhs);
4117 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r));
4118
4119 if (b->op() == BOT_DIV || b->op() == BOT_IDIV || b->op() == BOT_MOD) {
4120 // These all require rhs() != 0. Which means we need to evaluate the rhs,
4121 // and put it in a register.
4122 int r_zero(bind_cst(0, cg, frag));
4123 partial.push_back(~linear_cond(cg, frag, BOT_EQ, -ctx, r_rhs, r_zero));
4124 }
4125 return {r, CG_Cond::forall(ctx, partial)};
4126 }
4127}
4128
4129CG::Binding CG::bind(UnOp* u, Mode ctx, CodeGen& cg, CG_Builder& frag) {
4130 // Unop is easy.
4131 switch (u->op()) {
4132 case UOT_NOT:
4133 throw InternalError("Non-Boolean bind called on boolean operator.");
4134 case UOT_PLUS:
4135 return CG::bind(u->e(), cg, frag);
4136 case UOT_MINUS: {
4137 Binding b_e(CG::bind(u->e(), cg, frag));
4138 int r;
4139 if (u->type().isvar()) {
4140 GCLock lock;
4141 auto fun =
4142 find_call_fun(cg, {"op_minus"}, Type::varint(), {Type::varint()}, BytecodeProc::FUN);
4143 assert(std::get<1>(fun) == BytecodeProc::FUN);
4144 PUSH_INSTR(frag, BytecodeStream::CALL, BytecodeProc::FUN, std::get<0>(fun),
4145 CG::i(!std::get<2>(fun)), CG::r(b_e.first));
4146 r = GET_REG(cg);
4147 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r));
4148 } else {
4149 r = GET_REG(cg);
4150 PUSH_INSTR(frag, BytecodeStream::IMMI, CG::i(0), CG::r(r));
4151 PUSH_INSTR(frag, BytecodeStream::SUBI, CG::r(r), CG::r(b_e.first), CG::r(r));
4152 }
4153 return {r, b_e.second};
4154 }
4155 }
4156}
4157
4158CG::Binding bind_call(Call* call, Mode ctx, CodeGen& cg, CG_Builder& frag) {
4159 // Collects the partiality of the arguments
4160 int sz = call->n_args();
4161 std::vector<CG_Value> r_arg(sz);
4162 std::vector<CG_Cond::T> p_arg(sz);
4163 for (int ii = 0; ii < sz; ++ii) {
4164 CG::Binding r_bind(CG::force_or_bind(call->arg(ii), BytecodeProc::FUN, cg, frag));
4165 r_arg[ii] = CG::r(r_bind.first);
4166 p_arg[ii] = r_bind.second;
4167 }
4168
4169 // Bind the value part.
4170 auto fun = find_call_fun(cg, call, BytecodeProc::ROOT);
4171 assert(std::get<1>(fun) == BytecodeProc::FUN);
4172 PUSH_INSTR(frag, BytecodeStream::CALL, BytecodeProc::FUN, std::get<0>(fun),
4173 CG::i((!std::get<2>(fun)) && call->type().isvar()), r_arg);
4174
4175 int r_ret(GET_REG(cg));
4176 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r_ret));
4177
4178 return std::make_pair(r_ret, CG_Cond::forall(ctx, p_arg));
4179}
4180
4181CG::Binding CG::bind(Call* call, Mode ctx, CodeGen& cg, CG_Builder& frag) {
4182 {
4183 GCLock gc;
4184 auto it(builtins().find(call->id().str()));
4185 if (it != builtins().end()) {
4186 return (*it).second.general(call, ctx, cg, frag);
4187 }
4188 }
4189
4190 return bind_call(call, ctx, cg, frag);
4191}
4192
4193CG::Binding CG::bind(Let* let, Mode ctx, CodeGen& cg, CG_Builder& frag) {
4194 std::vector<CG_Cond::T> partial;
4195
4196 cg.env_push();
4197
4198 if (let->ann().contains(constants().ann.promise_total)) {
4199 OPEN_OTHER(cg, frag);
4200 eval_let_body(let, BytecodeProc::ROOT, cg, frag, partial);
4201
4202 CG::Binding b_in(CG::bind(let->in(), cg, frag));
4203 partial.push_back(b_in.second);
4204 post_cond(cg, frag, CG_Cond::forall(BytecodeProc::ROOT, partial));
4205 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(b_in.first));
4206 CLOSE_AGG(cg, frag);
4207 cg.env_pop();
4208
4209 int ret = GET_REG(cg);
4210 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(ret));
4211
4212 return {ret, CG_Cond::forall(ctx, partial)};
4213 }
4214
4215 eval_let_body(let, BytecodeProc::ROOT, cg, frag, partial);
4216 CG::Binding b_in(CG::bind(let->in(), cg, frag));
4217 partial.push_back(b_in.second);
4218
4219 cg.env_pop();
4220 return {b_in.first, CG_Cond::forall(ctx, partial)};
4221}
4222
4223CG::Binding CG::bind(Comprehension* comp, Mode ctx, CodeGen& cg, CG_Builder& frag) {
4224 // Lift out the outer-most comprehension, since it will always
4225 // be executed.
4226 CG::bind(comp->in(0), cg, frag);
4227
4228 cg.env_push();
4229 OPEN_VEC(cg, frag);
4230 execute_comprehension_bind(comp, ctx, cg, frag);
4231 CLOSE_AGG(cg, frag);
4232 cg.env_pop();
4233 int r(GET_REG(cg));
4234 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r));
4235 if (comp->type().is_set()) {
4236 PUSH_INSTR(frag, BytecodeStream::MAKE_SET, CG::r(r), CG::r(r));
4237 }
4238 return CG::Binding(r, CG_Cond::ttt());
4239}
4240
4241CG_Cond::T _compile(Expression* e, CodeGen& cg, CG_Builder& frag) {
4242 // Look up the mode we need to compile e in.
4243 CG::Mode ctx(BytecodeProc::FUN);
4244 try {
4245 ctx = cg.mode_map.at(e);
4246 } catch (const std::out_of_range& exn) {
4247 std::cerr << "%% Missing mode for: ";
4248 debugprint(e);
4249 }
4250
4251 switch (e->eid()) {
4252 case Expression::E_INTLIT:
4253 case Expression::E_FLOATLIT:
4254 case Expression::E_SETLIT:
4255 case Expression::E_STRINGLIT:
4256 case Expression::E_ARRAYLIT:
4257 case Expression::E_COMP:
4258 throw InternalError("compile called on non-Boolean expression.");
4259 case Expression::E_BOOLLIT:
4260 return (e->template cast<BoolLit>()->v()) ? CG_Cond::ttt() : CG_Cond::fff();
4261 case Expression::E_ID:
4262 return CG::compile(e->template cast<Id>(), ctx, cg, frag);
4263 case Expression::E_ANON:
4264 throw InternalError("compile reached unexpected expression type: E_ANON.");
4265 case Expression::E_ARRAYACCESS:
4266 return CG::compile(e->template cast<ArrayAccess>(), ctx, cg, frag);
4267 case Expression::E_ITE:
4268 return CG::compile(e->template cast<ITE>(), ctx, cg, frag);
4269 case Expression::E_BINOP:
4270 return CG::compile(e->template cast<BinOp>(), ctx, cg, frag);
4271 case Expression::E_UNOP:
4272 return CG::compile(e->template cast<UnOp>(), ctx, cg, frag);
4273 case Expression::E_CALL:
4274 return CG::compile(e->template cast<Call>(), ctx, cg, frag);
4275 case Expression::E_LET:
4276 return CG::compile(e->template cast<Let>(), ctx, cg, frag);
4277 case Expression::E_VARDECL:
4278 case Expression::E_TI:
4279 case Expression::E_TIID:
4280 throw InternalError("Bytecode generator encountered unexpected expression type in compile.");
4281 }
4282}
4283
4284CG_Cond::T CG::compile(Expression* e, CodeGen& cg, CG_Builder& frag) {
4285 assert(e->type().isbool());
4286 try {
4287 CG_Cond::T r(cg.cache_lookup(e).second);
4288 return r;
4289 } catch (const CG_Env<CG::Binding>::NotFound& exn) {
4290 CG_Cond::T cond(_compile(e, cg, frag));
4291 CG::Binding b(0xdeadbeef, cond);
4292 cg.cache_store(e, b);
4293 return cond;
4294 }
4295 // return _compile(e, cg, frag); // FIXME: Update env representation.
4296}
4297
4298CG_Cond::T CG::compile(Id* x, Mode ctx, CodeGen& cg, CG_Builder& frag) {
4299 try {
4300 CG::Binding b(cg.env().lookup(x->v()));
4301 // Check if there is a complex condition
4302 if (b.second.get()) {
4303 // If so then the register is a placeholder and the condition holds the value
4304 assert(b.first == 0xdeadbeef);
4305 return b.second;
4306 } else {
4307 // Otherwise the value should be in the register
4308 return CG_Cond::reg(b.first, x->type().ispar());
4309 }
4310 } catch (const CG_Env<Binding>::NotFound& exn) {
4311 VarDecl* vd = follow_id_to_decl(x)->cast<VarDecl>();
4312 int g = cg.find_global(vd);
4313 int r(GET_REG(cg));
4314 PUSH_INSTR(frag, BytecodeStream::LOAD_GLOBAL, CG::g(g), CG::r(r));
4315 return CG_Cond::reg(r, x->type().ispar());
4316 }
4317}
4318
4319CG_Cond::T CG::compile(ArrayAccess* a, Mode ctx, CodeGen& cg, CG_Builder& frag) {
4320 // If the array elements are Boolean, we need to check for partiality
4321 // in the indices, and that the accesses are within-range.
4322 ASTExprVec<Expression> idx(a->idx());
4323 Expression* A(a->v());
4324 int sz(idx.size());
4325
4326 bool is_var = false;
4327 for (int ii = 0; ii < sz; ++ii) {
4328 is_var = is_var || idx[ii]->type().isvar();
4329 }
4330
4331 // Evaluate the indices, put them in registers.
4332 // Collect partiality of the expression.
4333 std::vector<CG_Cond::T> cond;
4334
4335 // Now evaluate the array body, and emit the indices.
4336 std::vector<int> r_idxs(sz);
4337 for (int ii = 0; ii < sz; ++ii) {
4338 CG::Binding b(CG::bind(idx[ii], cg, frag));
4339 r_idxs[ii] = b.first;
4340 cond.push_back(b.second);
4341 }
4342
4343 CG::Binding b_A(CG::bind(A, cg, frag));
4344 int r_A(b_A.first);
4345 cond.push_back(b_A.second);
4346
4347 if (is_var) {
4348 GCLock lock;
4349 std::vector<Type> types(sz + 2, Type::varint());
4350 types[0] = Type::varbool();
4351 types[sz + 1] = Type::varbool(sz);
4352
4353 std::vector<CG_Value> r_args(sz + 1);
4354 for (int ii = 0; ii < sz; ++ii) {
4355 r_args[ii] = CG::r(r_idxs[ii]);
4356 }
4357 r_args[sz] = CG::r(r_A);
4358
4359 cond.push_back(CG_Cond::call({"element"}, -ctx, true, types, r_args));
4360 return CG_Cond::forall(ctx, cond);
4361 } else {
4362 // Just read the vector, and get the appropriate element.
4363 int r;
4364 CG_Cond::T ncond;
4365 std::tie(r, ncond) = execute_array_access(r_A, r_idxs, cg, frag);
4366 cond.push_back(ncond);
4367 cond.push_back(CG_Cond::reg(r, a->type().ispar()));
4368 return CG_Cond::forall(ctx, cond);
4369 }
4370}
4371
4372CG_Cond::T CG::compile(ITE* ite, Mode ctx, CodeGen& cg, CG_Builder& frag) {
4373 int sz(ite->size());
4374
4375 // Check whether all the conditions are par.
4376 bool all_par = true;
4377 for (int ii = 0; ii < sz; ++ii) {
4378 if (!ite->e_if(ii)->type().ispar()) {
4379 all_par = false;
4380 break;
4381 }
4382 }
4383
4384 if (all_par) {
4385 // We need to interfere with the env, here, because stuff may not be available.
4386 // Except, ite->e_if(0) will always be available.
4387 int l_end(GET_LABEL(cg));
4388 int r_ret(GET_REG(cg));
4389 for (int ii = 0; ii < sz; ++ii) {
4390 int r_sel = CG::force(CG::compile(ite->e_if(ii), cg, frag), BytecodeProc::FUN, cg, frag);
4391 int l_cont(GET_LABEL(cg));
4392 PUSH_INSTR(frag, BytecodeStream::JMPIFNOT, CG::r(r_sel), CG::l(l_cont));
4393 cg.env_push();
4394 if (!ite->e_then(ii)->type().ispar()) all_par = false;
4395 int r_val = CG::force(CG::compile(ite->e_then(ii), cg, frag), ctx, cg, frag);
4396 PUSH_INSTR(frag, BytecodeStream::MOV, CG::r(r_val), CG::r(r_ret));
4397 PUSH_INSTR(frag, BytecodeStream::JMP, CG::l(l_end));
4398 cg.env_pop();
4399 cg.env_push();
4400 PUSH_LABEL(frag, l_cont);
4401 }
4402 // Else case.
4403 if (!ite->e_else()->type().ispar()) all_par = false;
4404 int r_val = CG::force(CG::compile(ite->e_else(), cg, frag), ctx, cg, frag);
4405 PUSH_INSTR(frag, BytecodeStream::MOV, CG::r(r_val), CG::r(r_ret));
4406 PUSH_LABEL(frag, l_end);
4407 // Now kill the availability of all the expressions.
4408 for (int ii = 0; ii < sz; ++ii) cg.env_pop();
4409 return CG_Cond::reg(r_ret, all_par);
4410 } else {
4411 GCLock lock;
4412
4413 // Collect conditions
4414 OPEN_VEC(cg, frag);
4415 for (int ii = 0; ii < sz; ++ii) {
4416 int r_if(CG::force(CG::compile(ite->e_if(ii), cg, frag), BytecodeProc::FUN, cg, frag));
4417 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(r_if));
4418 }
4419 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(bind_cst(1, cg, frag)));
4420 CLOSE_AGG(cg, frag);
4421 int r_if(GET_REG(cg));
4422 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r_if));
4423
4424 // Collect results
4425 OPEN_VEC(cg, frag);
4426 for (int ii = 0; ii < sz; ++ii) {
4427 int r_then(CG::force(CG::compile(ite->e_then(ii), cg, frag), ctx, cg, frag));
4428 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(r_then));
4429 }
4430 {
4431 int r_else(CG::force(CG::compile(ite->e_else(), cg, frag), ctx, cg, frag));
4432 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(r_else));
4433 }
4434 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(bind_cst(1, cg, frag)));
4435 CLOSE_AGG(cg, frag);
4436 int r_then(GET_REG(cg));
4437 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r_then));
4438
4439 return CG_Cond::call({"if_then_else"}, BytecodeProc::FUN, true,
4440 {Type::varbool(), Type::varbool(1), Type::varbool(1)},
4441 {CG::r(r_if), CG::r(r_then)});
4442 }
4443}
4444
4445CG_Cond::T shortcut_par_or(Mode ctx, CodeGen& cg, CG_Builder& frag, Expression* lhs,
4446 Expression* rhs) {
4447 Mode f_mode(ctx.strength(), false); // Check
4448 assert(lhs->type().ispar());
4449 int r(GET_REG(cg));
4450 int l_exit(GET_LABEL(cg));
4451 int r_lhs(CG::force(CG::compile(lhs, cg, frag), f_mode, cg, frag));
4452 PUSH_INSTR(frag, BytecodeStream::MOV, CG::r(r_lhs), CG::r(r));
4453 PUSH_INSTR(frag, BytecodeStream::JMPIF, CG::r(r), CG::l(l_exit));
4454 cg.env_push();
4455 int r_rhs(CG::force(CG::compile(rhs, cg, frag), f_mode, cg, frag));
4456 PUSH_INSTR(frag, BytecodeStream::MOV, CG::r(r_rhs), CG::r(r));
4457 cg.env_pop();
4458 PUSH_LABEL(frag, l_exit);
4459 return CG_Cond::reg(r, rhs->type().ispar());
4460}
4461
4462CG_Cond::T shortcut_par_and(Mode ctx, CodeGen& cg, CG_Builder& frag, Expression* lhs,
4463 Expression* rhs) {
4464 Mode f_mode(ctx.strength(), false); // Check
4465 assert(lhs->type().ispar());
4466 int r(GET_REG(cg));
4467 int l_exit(GET_LABEL(cg));
4468 int r_lhs(CG::force(CG::compile(lhs, cg, frag), f_mode, cg, frag));
4469 PUSH_INSTR(frag, BytecodeStream::MOV, CG::r(r_lhs), CG::r(r));
4470 PUSH_INSTR(frag, BytecodeStream::JMPIFNOT, CG::r(r), CG::l(l_exit));
4471 cg.env_push();
4472 int r_rhs(CG::force(CG::compile(rhs, cg, frag), f_mode, cg, frag));
4473 PUSH_INSTR(frag, BytecodeStream::MOV, CG::r(r_rhs), CG::r(r));
4474 cg.env_pop();
4475 PUSH_LABEL(frag, l_exit);
4476 return CG_Cond::reg(r, rhs->type().ispar());
4477}
4478
4479CG_Cond::T CG::compile(BinOp* b, Mode ctx, CodeGen& cg, CG_Builder& frag) {
4480 std::vector<CG_Cond::T> cond;
4481 // For anything we force here, its calling mode is considered positive (because
4482 // it needs to mean what we said.)
4483 CG::Mode f_mode(ctx.strength(), false);
4484 if (b->lhs()->type().dim() > 0) {
4485 GCLock lock;
4486 assert(b->rhs()->type().dim() > 0);
4487 assert(b->op() == BOT_EQ || b->op() == BOT_EQUIV);
4488 int r_lhs = CG::force_or_bind(b->lhs(), f_mode, cond, cg, frag);
4489 int r_rhs = CG::force_or_bind(b->rhs(), f_mode, cond, cg, frag);
4490 cond.push_back(CG_Cond::call(
4491 {"op_equals"}, BytecodeProc::FUN, true,
4492 {b->type().isvar() ? Type::varbool() : Type::parbool(), b->lhs()->type(), b->rhs()->type()},
4493 {CG::r(r_lhs), CG::r(r_rhs)}));
4494 return CG_Cond::forall(ctx, cond);
4495 }
4496 if (b->op() == BOT_AND) {
4497 if (b->lhs()->type().ispar()) return shortcut_par_and(ctx, cg, frag, b->lhs(), b->rhs());
4498 if (b->rhs()->type().ispar()) return shortcut_par_and(ctx, cg, frag, b->rhs(), b->lhs());
4499 } else if (b->op() == BOT_OR) {
4500 if (b->lhs()->type().ispar()) return shortcut_par_or(ctx, cg, frag, b->lhs(), b->rhs());
4501 if (b->rhs()->type().ispar()) return shortcut_par_or(ctx, cg, frag, b->rhs(), b->lhs());
4502 }
4503 if (b->type().ispar()) {
4504 int r_lhs = CG::force_or_bind(b->lhs(), f_mode, cond, cg, frag);
4505 int r_rhs = CG::force_or_bind(b->rhs(), f_mode, cond, cg, frag);
4506 std::vector<int> r_cond;
4507 for (CG_Cond::T c : cond) {
4508 // r_cond.push_back(CG::force(c, ctx, cg, frag));
4509 // FIXME: This is probably safe, assuming all the conditions
4510 // are also par. We need these to be in their literal,
4511 // non-context-adjusted modes for the disentailment check to work.
4512 // If we want to handle non-par conditions, we probably need to
4513 // force in ctx, then flip back.
4514 r_cond.push_back(CG::force(c, f_mode, cg, frag));
4515 }
4516 int r_ret;
4517 if (b->lhs()->type().isintset()) {
4518 r_ret = bind_binop_par_set(cg, frag, b->op(), r_lhs, r_rhs);
4519 } else {
4520 r_ret = bind_binop_par_int(cg, frag, b->op(), r_lhs, r_rhs);
4521 }
4522 if (r_cond.size() > 0) {
4523 // If any conditions don't hold, evaluate to false.
4524 int r(GET_REG(cg));
4525 int l_tl(GET_LABEL(cg));
4526 PUSH_INSTR(frag, BytecodeStream::IMMI, CG::i(0), CG::r(r));
4527 for (int r_c : r_cond) {
4528 PUSH_INSTR(frag, BytecodeStream::JMPIFNOT, CG::r(r_c), CG::l(l_tl));
4529 }
4530 PUSH_INSTR(frag, BytecodeStream::MOV, CG::r(r_ret), CG::r(r));
4531 PUSH_LABEL(frag, l_tl);
4532 return CG_Cond::reg(r, true);
4533 } else {
4534 return CG_Cond::reg(r_ret, true);
4535 }
4536 }
4537 switch (b->op()) {
4538 case BOT_LE:
4539 case BOT_LQ:
4540 case BOT_GR:
4541 case BOT_GQ:
4542 case BOT_EQ:
4543 case BOT_EQUIV:
4544 case BOT_NQ: {
4545 // Potentially partial.
4546 int r_lhs = CG::force_or_bind(b->lhs(), f_mode, cond, cg, frag);
4547 int r_rhs = CG::force_or_bind(b->rhs(), f_mode, cond, cg, frag);
4548 cond.push_back(linear_cond(cg, frag, b->op(), ctx, r_lhs, r_rhs));
4549 return CG_Cond::forall(ctx, cond);
4550 } break;
4551 case BOT_XOR: {
4552 CG_Cond::T c_lhs = CG::compile(b->lhs(), cg, frag);
4553 CG_Cond::T c_rhs = CG::compile(b->rhs(), cg, frag);
4554 return CG_Cond::forall(ctx, CG_Cond::exists(ctx, c_lhs, c_rhs),
4555 CG_Cond::exists(ctx, ~c_lhs, ~c_rhs));
4556 } break;
4557 case BOT_AND: {
4558 cond.push_back(CG::compile(b->lhs(), cg, frag));
4559 cond.push_back(CG::compile(b->rhs(), cg, frag));
4560 return CG_Cond::forall(ctx, cond);
4561 } break;
4562 case BOT_OR: {
4563 cond.push_back(CG::compile(b->lhs(), cg, frag));
4564 cond.push_back(CG::compile(b->rhs(), cg, frag));
4565 return CG_Cond::exists(ctx, cond);
4566 } break;
4567 case BOT_IMPL: {
4568 cond.push_back(~CG::compile(b->lhs(), cg, frag));
4569 cond.push_back(CG::compile(b->rhs(), cg, frag));
4570 return CG_Cond::exists(ctx, cond);
4571 } break;
4572 case BOT_RIMPL: {
4573 cond.push_back(CG::compile(b->lhs(), cg, frag));
4574 cond.push_back(~CG::compile(b->rhs(), cg, frag));
4575 return CG_Cond::exists(ctx, cond);
4576 }
4577 case BOT_IN: {
4578 CG::Binding b_lhs(CG::bind(b->lhs(), cg, frag));
4579 CG::Binding b_rhs(CG::bind(b->rhs(), cg, frag));
4580 assert(b->rhs()->type().ispar());
4581 cond.push_back(b_lhs.second);
4582 cond.push_back(b_rhs.second);
4583 if (ctx == BytecodeProc::ROOT) {
4584 int r(GET_REG(cg));
4585 PUSH_INSTR(frag, BytecodeStream::INTERSECT_DOMAIN, CG::r(b_lhs.first), CG::r(b_rhs.first),
4586 CG::r(r));
4587 // If INTERSECT_DOMAIN fails, then the interpreter will mark inconsistent and ABORT
4588 cond.push_back(CG_Cond::ttt());
4589 } else if (ctx == BytecodeProc::ROOT_NEG) {
4590 int r(GET_REG(cg));
4591 PUSH_INSTR(frag, BytecodeStream::DOM, CG::r(b_lhs.first), CG::r(r));
4592 PUSH_INSTR(frag, BytecodeStream::DIFF, CG::r(r), CG::r(b_rhs.first), CG::r(r));
4593 PUSH_INSTR(frag, BytecodeStream::INTERSECT_DOMAIN, CG::r(b_lhs.first), CG::r(r), CG::r(r));
4594 // If INTERSECT_DOMAIN fails, then the interpreter will mark inconsistent and ABORT
4595 cond.push_back(CG_Cond::ttt());
4596 } else {
4597 GCLock lock;
4598 cond.push_back(CG_Cond::call({"set_in"}, ctx, true,
4599 {Type::varbool(), Type::varint(), Type::varsetint()},
4600 {CG::r(b_lhs.first), CG::r(b_rhs.first)}));
4601 }
4602 return CG_Cond::forall(ctx, cond);
4603 }
4604 default:
4605 break;
4606 }
4607 throw InternalError("Unexpected fall-through in compilation of BinOp.");
4608}
4609
4610CG_Cond::T CG::compile(UnOp* u, Mode ctx, CodeGen& cg, CG_Builder& frag) {
4611 assert(u->op() == UOT_NOT);
4612 return ~CG::compile(u->e(), cg, frag);
4613}
4614
4615CG_Cond::T compile_call(Call* call, Mode ctx, CodeGen& cg, CG_Builder& frag) {
4616 int sz = call->n_args();
4617 std::vector<CG_Value> r_arg(sz);
4618 std::vector<CG_Cond::T> p_arg;
4619
4620 // Evaluate the args, collecting the conditionality.
4621 std::vector<Type> arg_types(sz + 1);
4622 arg_types[0] = call->type();
4623 for (int ii = 0; ii < sz; ++ii) {
4624 arg_types[ii + 1] = call->arg(ii)->type();
4625 r_arg[ii] = CG::r(CG::force_or_bind(call->arg(ii), BytecodeProc::FUN, p_arg, cg, frag));
4626 }
4627
4628 // And finally, add the call itself
4629 p_arg.push_back(CG_Cond::call(call->id(), ctx, call->type().isvar(), arg_types, r_arg));
4630 return CG_Cond::forall(ctx, p_arg);
4631}
4632
4633CG_Cond::T CG::compile(Call* call, Mode ctx, CodeGen& cg, CG_Builder& frag) {
4634 // If we have a builtin for this, dispatch to that instead.
4635 {
4636 GCLock gc;
4637 auto it(builtins().find(call->id().str()));
4638 if (it != builtins().end()) {
4639 return it->second.boolean(call, ctx, cg, frag);
4640 }
4641 }
4642
4643 return compile_call(call, ctx, cg, frag);
4644}
4645
4646void eval_let_body(Let* let, BytecodeProc::Mode ctx, CodeGen& cg, CG_Builder& frag,
4647 std::vector<CG_Cond::T>& conj) {
4648 ASTExprVec<Expression> bindings(let->let());
4649 for (Expression* e : bindings) {
4650 if (auto vd = e->dyn_cast<VarDecl>()) {
4651 // Bind the new definitions in context
4652 CodeGen::Binding to_bind(0xdeadbeef, CG_Cond::ttt());
4653 if (vd->e() && vd->type().isbool()) {
4654 CG_Cond::T cond = CG::compile(vd->e(), cg, frag);
4655 if (!cond.get()) {
4656 to_bind.first = bind_cst(cond.sign(), cg, frag);
4657 } else {
4658 to_bind.second = cond;
4659 }
4660 } else if (vd->e()) {
4661 // FIXME: Assuming domain isn't constraining.
4662 CG::Binding b_v(CG::bind(vd->e(), cg, frag));
4663 to_bind.first = b_v.first;
4664 conj.push_back(b_v.second);
4665 if (Expression* d = vd->ti()->domain()) {
4666 if (!vd->ti()->isarray()) {
4667 CG::Binding b_d = CG::bind(d, cg, frag); // Discarding any constraints on the set.
4668 conj.push_back(b_d.second);
4669 int r_dp = GET_REG(cg);
4670 PUSH_INSTR(frag, BytecodeStream::INTERSECT_DOMAIN, CG::r(to_bind.first),
4671 CG::r(b_d.first), CG::r(r_dp));
4672 }
4673 }
4674 } else {
4675 // Variable declaration. Assumes is total and nonempty.
4676 CG::Binding b_d(bind_domain(vd, cg, frag));
4677 to_bind.first = GET_REG(cg);
4678 if (!vd->ti()->isarray()) {
4679 conj.push_back(b_d.second);
4680 PUSH_INSTR(frag, BytecodeStream::CALL, BytecodeProc::ROOT, cg.find_builtin("mk_intvar"),
4681 CG::i(0), CG::r(b_d.first));
4682 } else {
4683 int rTMP(GET_REG(cg));
4684 std::vector<int> r_regs;
4685 for (Expression* r : vd->ti()->ranges()) {
4686 Expression* dim(r->template cast<TypeInst>()->domain());
4687 CG::Binding b_reg(CG::bind(dim, cg, frag));
4688 // post_cond(cg, frag, b_reg.second);
4689 r_regs.push_back(b_reg.first);
4690 }
4691 std::vector<Forset> nesting;
4692 OPEN_VEC(cg, frag);
4693 for (int r_r : r_regs) {
4694 Forset iter(cg, r_r);
4695 nesting.push_back(iter);
4696 iter.emit_pre(frag);
4697 }
4698 PUSH_INSTR(frag, BytecodeStream::CALL, BytecodeProc::ROOT, cg.find_builtin("mk_intvar"),
4699 CG::i(0), CG::r(b_d.first));
4700 for (int r_i = r_regs.size() - 1; r_i >= 0; --r_i) {
4701 nesting[r_i].emit_post(frag);
4702 }
4703 CLOSE_AGG(cg, frag);
4704 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(to_bind.first));
4705 OPEN_VEC(cg, frag);
4706 for (int r_r : r_regs) {
4707 PUSH_INSTR(frag, BytecodeStream::GET_VEC, CG::r(r_r), CG::r(bind_cst(1, cg, frag)),
4708 CG::r(rTMP));
4709 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(rTMP));
4710 PUSH_INSTR(frag, BytecodeStream::GET_VEC, CG::r(r_r), CG::r(bind_cst(2, cg, frag)),
4711 CG::r(rTMP));
4712 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(rTMP));
4713 }
4714 CLOSE_AGG(cg, frag);
4715 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(rTMP));
4716
4717 PUSH_INSTR(frag, BytecodeStream::BUILTIN, cg.find_builtin("array_Xd"),
4718 CG::r(to_bind.first), CG::r(rTMP));
4719 }
4720 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(to_bind.first));
4721 }
4722 cg.env().bind(vd->id()->v(), to_bind);
4723 } else {
4724 conj.push_back(CG::compile(e, cg, frag));
4725 }
4726 }
4727}
4728
4729CG_Cond::T CG::compile(Let* let, Mode ctx, CodeGen& cg, CG_Builder& frag) {
4730 std::vector<CG_Cond::T> conj;
4731
4732 cg.env_push();
4733
4734 if (let->ann().contains(constants().ann.promise_total)) {
4735 OPEN_OTHER(cg, frag);
4736 eval_let_body(let, BytecodeProc::ROOT, cg, frag, conj);
4737 // int r = CG::force(CG_Cond::forall(ctx, conj), BytecodeProc::ROOT, cg, frag);
4738 post_cond(cg, frag, CG_Cond::forall(BytecodeProc::ROOT, conj));
4739 int r = CG::force(CG::compile(let->in(), cg, frag), ctx, cg, frag);
4740 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(r));
4741 CLOSE_AGG(cg, frag);
4742 r = GET_REG(cg);
4743 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r));
4744 conj.clear();
4745 conj.push_back(CG_Cond::reg(r, let->in()->type().ispar()));
4746 } else {
4747 eval_let_body(let, BytecodeProc::ROOT, cg, frag, conj);
4748 conj.push_back(CG::compile(let->in(), cg, frag));
4749 }
4750 cg.env_pop();
4751 return CG_Cond::forall(ctx, conj);
4752}
4753
4754int CG::vec2array(std::vector<int> vec, CodeGen& cg, CG_Builder& frag) {
4755 int sz(vec.size());
4756 OPEN_VEC(cg, frag);
4757 for (int ii = 0; ii < sz; ++ii) {
4758 PUSH_INSTR(frag, BytecodeStream::PUSH, CG::r(vec[ii]));
4759 }
4760 CLOSE_AGG(cg, frag);
4761 int r_vec(GET_REG(cg));
4762 PUSH_INSTR(frag, BytecodeStream::POP, CG::r(r_vec));
4763
4764 return r_vec;
4765}
4766}; // namespace MiniZinc