this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2
3/*
4 * Main authors:
5 * Graeme Gange <graeme.gange@monash.edu>
6 */
7
8/* This Source Code Form is subject to the terms of the Mozilla Public
9 * License, v. 2.0. If a copy of the MPL was not distributed with this
10 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
11
12#ifndef __MINIZINC_CODEGEN_ANALYSIS_HPP__
13#define __MINIZINC_CODEGEN_ANALYSIS_HPP__
14#include <minizinc/ast.hh>
15#include <minizinc/astiterator.hh>
16#include <minizinc/codegen.hh>
17
18#include <queue>
19
20// From a given top-level expression and
21// mode, what is the weakest mode covering
22// all occurrences of each sub-expression?
23namespace MiniZinc {
24
25static void annotate_total(FunctionI* func) {
26 class AnnotateTotal : public EVisitor {
27 public:
28 void vLet(Let& let) {
29 let.addAnnotation(constants().ann.promise_total);
30 ASTExprVec<Expression> bindings(let.let());
31 for (auto expr : bindings) {
32 if (expr->eid() != Expression::E_VARDECL) {
33 // Must be a constraint, so it's a use.
34 assert(expr->type().isbool());
35 expr->addAnnotation(constants().ann.promise_total);
36 }
37 }
38 }
39 } _at;
40 if (func->ann().contains(constants().ann.promise_total)) {
41 topDown(_at, func->e());
42 }
43}
44
45class ModeAnalysis {
46 enum Occurrence { Def = 0, Use = 1 };
47
48public:
49 // There are two relevant modes for an expression: the mode
50 // where the value is introduced, and the mode where the value
51 // is used.
52 // This distinction mostly matters for let-bindings or definitions
53 // which construct results containing Booleans (i.e. array [int] of var bool).
54 // At the end, Boolean values are built according to their use-context, and
55 // non-Boolean values by their def-context.
56
57 // We use user_flag0 and user_flag1 to track whether
58 // the definition and use-modes are queued.
59 inline void enqueue(Expression* e, Occurrence o) {
60 if (e->isUnboxedVal()) return;
61 if (o == Def) {
62 if (!e->user_flag0()) {
63 e->user_flag0(true);
64 worklist.push(reinterpret_cast<uintptr_t>(e));
65 }
66 } else {
67 if (!e->user_flag1()) {
68 e->user_flag1(true);
69 worklist.push(reinterpret_cast<uintptr_t>(e) | 1);
70 }
71 }
72 }
73
74 void update(Expression* e, Occurrence o, CG::Mode m) {
75 if (e->type().isbool()) {
76 if (o == Def) {
77 // We only keep Use-modes for Boolean things.
78 return;
79 }
80 if (e->ann().contains(constants().ann.promise_total)) {
81 m = BytecodeProc::ROOT;
82 }
83 }
84 ExprMap<CG::Mode>::t& t(o == Def ? def_map : use_map);
85 auto it(t.find(e));
86 if (it == t.end()) {
87 // First time we've seen e.
88 t.insert(std::make_pair(e, m));
89 } else {
90 if (it->second.is_submode(m)) return;
91 it->second = it->second.join(m);
92 }
93 enqueue(e, o);
94 }
95
96 void update(FunctionI* fun, Occurrence o, CG::Mode m) {
97 // We only keep Use-modes for Boolean things.
98 /*
99 if(o == Def) {
100 if(e->type().isbool())
101 return;
102 if(e->ann().contains(constants().ann.promise_total))
103 m = BytecodeProc::ROOT;
104 }
105 ExprMap<CG::Mode>::t& t(o == Def ? def_map : use_map);
106 auto it(t.find(e));
107 if(it == t.end()) {
108 // First time we've seen e.
109 t.insert(std::make_pair(e, m));
110 } else {
111 if(it->second.is_submode(m))
112 return;
113 it->second = it->second.join(m);
114 }
115 enqueue(e, o);
116 */
117 }
118
119 // Better to make this fifo, but... whatever.
120 void process(void) {
121 while (!worklist.empty()) {
122 uintptr_t tag(worklist.front());
123 worklist.pop();
124 Expression* e(reinterpret_cast<Expression*>(tag & ~((uintptr_t)1)));
125 Occurrence o(static_cast<Occurrence>(tag & 1));
126 // Clear the queued-ness flags
127 if (o == Def)
128 e->user_flag0(false);
129 else
130 e->user_flag1(false);
131
132 // Get the updated mode for e.
133 ExprMap<CG::Mode>::t& t(o == Def ? def_map : use_map);
134 CG::Mode m(t.at(e));
135 switch (e->eid()) {
136 case Expression::E_INTLIT:
137 case Expression::E_FLOATLIT:
138 case Expression::E_SETLIT:
139 case Expression::E_BOOLLIT:
140 case Expression::E_STRINGLIT:
141 case Expression::E_ANON:
142 break;
143 case Expression::E_ID:
144 vId(*e->template cast<Id>(), o, m);
145 break;
146 case Expression::E_ARRAYLIT:
147 vArrayLit(*e->template cast<ArrayLit>(), o, m);
148 break;
149 case Expression::E_ARRAYACCESS:
150 vArrayAccess(*e->template cast<ArrayAccess>(), o, m);
151 break;
152 case Expression::E_COMP:
153 vComprehension(*e->template cast<Comprehension>(), o, m);
154 break;
155 case Expression::E_ITE:
156 vITE(*e->template cast<ITE>(), o, m);
157 break;
158 case Expression::E_BINOP:
159 vBinOp(*e->template cast<BinOp>(), o, m);
160 break;
161 case Expression::E_UNOP:
162 vUnOp(*e->template cast<UnOp>(), o, m);
163 break;
164 case Expression::E_CALL:
165 vCall(*e->template cast<Call>(), o, m);
166 break;
167 case Expression::E_VARDECL:
168 vVarDecl(*e->template cast<VarDecl>(), o, m);
169 break;
170 case Expression::E_LET:
171 vLet(*e->template cast<Let>(), o, m);
172 break;
173 /*
174 case Expression::E_TI:
175 _t.vTypeInst(*c._e->template cast<TypeInst>());
176 break;
177 case Expression::E_TIID:
178 _t.vTIId(*c._e->template cast<TIId>());
179 break;
180 */
181 default:
182 throw InternalError("Mode analyser encounted unexpected expression type.");
183 }
184 }
185 }
186
187 ModeAnalysis(void) {}
188
189 void def(Expression* e, CG::Mode m) { update(e, Def, m); }
190
191 void use(Expression* e, CG::Mode m) {
192 if (e->type().isbool())
193 update(e, Use, m);
194 else
195 update(e, Def, m);
196 }
197
198 ExprMap<CG::Mode>::t extract(void) {
199 // Compute the fixpoint.
200 process();
201 // Now fuse the two maps.
202 // Start from the def_map, and add any Boolean uses.
203 ExprMap<CG::Mode>::t fused(def_map);
204 for (auto p : use_map) {
205 /*
206 if(p.first->type().isbool())
207 fused.insert(p);
208 */
209 // If we haven't stored a def-mode, we should
210 // apply the use-mode.
211 fused.insert(p);
212 }
213 return fused;
214 }
215 /*
216 static ExprMap<CG::Mode> run(Expression* e, CG::Mode m) {
217 ModeAnalysis analyzer;
218 analyzer.update(e, Use, m);
219 analyzer.process();
220
221 // Now we fuse the two maps.
222 }
223 */
224
225 std::queue<uintptr_t> worklist;
226 ExprMap<CG::Mode>::t def_map;
227 ExprMap<CG::Mode>::t use_map;
228
229 /// Visit identifier
230 void vId(Id&, Occurrence, CG::Mode);
231 /// Visit array literal
232 void vArrayLit(ArrayLit&, Occurrence, CG::Mode);
233 /// Visit array access
234 void vArrayAccess(ArrayAccess&, Occurrence, CG::Mode);
235 /// Visit array comprehension
236 void vComprehension(Comprehension&, Occurrence, CG::Mode);
237 /// Visit if-then-else
238 void vITE(ITE&, Occurrence, CG::Mode);
239 /// Visit binary operator
240 void vBinOp(BinOp&, Occurrence, CG::Mode);
241 /// Visit unary operator
242 void vUnOp(UnOp&, Occurrence, CG::Mode);
243 /// Visit call
244 void vCall(Call&, Occurrence, CG::Mode);
245 /// Visit let
246 void vLet(Let&, Occurrence, CG::Mode);
247 /// Visit variable declaration
248 void vVarDecl(VarDecl&, Occurrence, CG::Mode);
249
250 // Process a function body.
251 void vFunctionI(FunctionI&, Occurrence, CG::Mode);
252};
253
254}; // namespace MiniZinc
255
256#endif