Fix some memory leaks
[satune.git] / src / ASTAnalyses / Encoding / encodinggraph.cc
1 #include "encodinggraph.h"
2 #include "iterator.h"
3 #include "element.h"
4 #include "function.h"
5 #include "predicate.h"
6 #include "set.h"
7 #include "csolver.h"
8 #include "tunable.h"
9 #include "qsort.h"
10 #include "subgraph.h"
11 #include "elementencoding.h"
12
13 EncodingGraph::EncodingGraph(CSolver *_solver) :
14         solver(_solver) {
15 }
16
17 EncodingGraph::~EncodingGraph() {
18         subgraphs.resetAndDelete();
19         encodingMap.resetAndDeleteVals();
20         edgeMap.resetAndDeleteVals();
21 }
22
23 int sortEncodingEdge(const void *p1, const void *p2) {
24         const EncodingEdge *e1 = *(const EncodingEdge **) p1;
25         const EncodingEdge *e2 = *(const EncodingEdge **) p2;
26         uint64_t v1 = e1->getValue();
27         uint64_t v2 = e2->getValue();
28         if (v1 < v2)
29                 return 1;
30         else if (v1 == v2)
31                 return 0;
32         else
33                 return -1;
34 }
35
36 void EncodingGraph::buildGraph() {
37         ElementIterator it(solver);
38         while (it.hasNext()) {
39                 Element *e = it.next();
40                 switch (e->type) {
41                 case ELEMSET:
42                 case ELEMFUNCRETURN:
43                         processElement(e);
44                         break;
45                 case ELEMCONST:
46                         break;
47                 default:
48                         ASSERT(0);
49                 }
50         }
51         bsdqsort(edgeVector.expose(), edgeVector.getSize(), sizeof(EncodingEdge *), sortEncodingEdge);
52         decideEdges();
53 }
54
55 void EncodingGraph::encode() {
56         SetIteratorEncodingSubGraph *itesg = subgraphs.iterator();
57         while (itesg->hasNext()) {
58                 EncodingSubGraph *sg = itesg->next();
59                 sg->encode();
60         }
61         delete itesg;
62
63         ElementIterator it(solver);
64         while (it.hasNext()) {
65                 Element *e = it.next();
66                 switch (e->type) {
67                 case ELEMSET:
68                 case ELEMFUNCRETURN: {
69                         ElementEncoding *encoding = e->getElementEncoding();
70                         if (encoding->getElementEncodingType() == ELEM_UNASSIGNED) {
71                                 EncodingNode *n = getNode(e);
72                                 if (n == NULL)
73                                         continue;
74                                 ElementEncodingType encodetype = n->getEncoding();
75                                 encoding->setElementEncodingType(encodetype);
76                                 if (encodetype == UNARY || encodetype == ONEHOT) {
77                                         encoding->encodingArrayInitialization();
78                                 } else if (encodetype == BINARYINDEX) {
79                                         EncodingSubGraph *subgraph = graphMap.get(n);
80                                         if (subgraph == NULL)
81                                                 continue;
82                                         uint encodingSize = subgraph->getEncodingMaxVal(n)+1;
83                                         uint paddedSize = encoding->getSizeEncodingArray(encodingSize);
84                                         model_print("encoding size=%u\n", encodingSize);
85                                         model_print("padded=%u\n", paddedSize);
86                                         encoding->allocInUseArrayElement(paddedSize);
87                                         encoding->allocEncodingArrayElement(paddedSize);
88                                         Set *s = e->getRange();
89                                         for (uint i = 0; i < s->getSize(); i++) {
90                                                 model_print("index=%u\n", i);
91                                                 uint64_t value = s->getElement(i);
92                                                 uint encodingIndex = subgraph->getEncoding(n, value);
93                                                 encoding->setInUseElement(encodingIndex);
94                                                 encoding->encodingArray[encodingIndex] = value;
95                                         }
96                                 }
97                         }
98                         break;
99                 }
100                 default:
101                         break;
102                 }
103                 encodeParent(e);
104         }
105 }
106
107 void EncodingGraph::encodeParent(Element *e) {
108         uint size = e->parents.getSize();
109         for (uint i = 0; i < size; i++) {
110                 ASTNode *n = e->parents.get(i);
111                 if (n->type == PREDICATEOP) {
112                         BooleanPredicate *b = (BooleanPredicate *)n;
113                         FunctionEncoding *fenc = b->getFunctionEncoding();
114                         if (fenc->getFunctionEncodingType() != FUNC_UNASSIGNED)
115                                 continue;
116                         Predicate *p = b->getPredicate();
117                         if (p->type == OPERATORPRED) {
118                                 PredicateOperator *po = (PredicateOperator *)p;
119                                 ASSERT(b->inputs.getSize() == 2);
120                                 EncodingNode *left = createNode(b->inputs.get(0));
121                                 EncodingNode *right = createNode(b->inputs.get(1));
122                                 if (left == NULL || right == NULL)
123                                         return;
124                                 EncodingEdge *edge = getEdge(left, right, NULL);
125                                 if (edge != NULL && edge->getEncoding() == EDGE_MATCH) {
126                                         fenc->setFunctionEncodingType(CIRCUIT);
127                                 }
128                         }
129                 }
130         }
131 }
132
133 void EncodingGraph::mergeNodes(EncodingNode *first, EncodingNode *second) {
134         EncodingSubGraph *graph1 = graphMap.get(first);
135         EncodingSubGraph *graph2 = graphMap.get(second);
136         if (graph1 == NULL)
137                 first->setEncoding(BINARYINDEX);
138         if (graph2 == NULL)
139                 second->setEncoding(BINARYINDEX);
140
141         if (graph1 == NULL && graph2 == NULL) {
142                 graph1 = new EncodingSubGraph();
143                 subgraphs.add(graph1);
144                 graphMap.put(first, graph1);
145                 graph1->addNode(first);
146         }
147         if (graph1 == NULL && graph2 != NULL) {
148                 graph1 = graph2;
149                 graph2 = NULL;
150                 EncodingNode *tmp = second;
151                 second = first;
152                 first = tmp;
153         }
154         if (graph1 != NULL && graph2 != NULL) {
155                 SetIteratorEncodingNode *nodeit = graph2->nodeIterator();
156                 while (nodeit->hasNext()) {
157                         EncodingNode *node = nodeit->next();
158                         graph1->addNode(node);
159                         graphMap.put(node, graph1);
160                 }
161                 subgraphs.remove(graph2);
162                 delete nodeit;
163                 delete graph2;
164         } else {
165                 ASSERT(graph1 != NULL && graph2 == NULL);
166                 graph1->addNode(second);
167                 graphMap.put(second, graph1);
168         }
169 }
170
171 void EncodingGraph::processElement(Element *e) {
172         uint size = e->parents.getSize();
173         for (uint i = 0; i < size; i++) {
174                 ASTNode *n = e->parents.get(i);
175                 switch (n->type) {
176                 case PREDICATEOP:
177                         processPredicate((BooleanPredicate *)n);
178                         break;
179                 case ELEMFUNCRETURN:
180                         processFunction((ElementFunction *)n);
181                         break;
182                 default:
183                         ASSERT(0);
184                 }
185         }
186 }
187
188 void EncodingGraph::processFunction(ElementFunction *ef) {
189         Function *f = ef->getFunction();
190         if (f->type == OPERATORFUNC) {
191                 FunctionOperator *fo = (FunctionOperator *)f;
192                 ASSERT(ef->inputs.getSize() == 2);
193                 EncodingNode *left = createNode(ef->inputs.get(0));
194                 EncodingNode *right = createNode(ef->inputs.get(1));
195                 if (left == NULL && right == NULL)
196                         return;
197                 EncodingNode *dst = createNode(ef);
198                 EncodingEdge *edge = createEdge(left, right, dst);
199                 edge->numArithOps++;
200         }
201 }
202
203 void EncodingGraph::processPredicate(BooleanPredicate *b) {
204         Predicate *p = b->getPredicate();
205         if (p->type == OPERATORPRED) {
206                 PredicateOperator *po = (PredicateOperator *)p;
207                 ASSERT(b->inputs.getSize() == 2);
208                 EncodingNode *left = createNode(b->inputs.get(0));
209                 EncodingNode *right = createNode(b->inputs.get(1));
210                 if (left == NULL || right == NULL)
211                         return;
212                 EncodingEdge *edge = createEdge(left, right, NULL);
213                 CompOp op = po->getOp();
214                 switch (op) {
215                 case SATC_EQUALS:
216                         edge->numEquals++;
217                         break;
218                 case SATC_LT:
219                 case SATC_LTE:
220                 case SATC_GT:
221                 case SATC_GTE:
222                         edge->numComparisons++;
223                         break;
224                 default:
225                         ASSERT(0);
226                 }
227         }
228 }
229
230 uint convertSize(uint cost) {
231         cost = 1.2 * cost;// fudge factor
232         return NEXTPOW2(cost);
233 }
234
235 void EncodingGraph::decideEdges() {
236         uint size = edgeVector.getSize();
237         for (uint i = 0; i < size; i++) {
238                 EncodingEdge *ee = edgeVector.get(i);
239                 EncodingNode *left = ee->left;
240                 EncodingNode *right = ee->right;
241
242                 if (ee->encoding != EDGE_UNASSIGNED ||
243                                 !left->couldBeBinaryIndex() ||
244                                 !right->couldBeBinaryIndex())
245                         continue;
246
247                 uint64_t eeValue = ee->getValue();
248                 if (eeValue == 0)
249                         return;
250
251                 EncodingSubGraph *leftGraph = graphMap.get(left);
252                 EncodingSubGraph *rightGraph = graphMap.get(right);
253                 if (leftGraph == NULL && rightGraph != NULL) {
254                         EncodingNode *tmp = left; left = right; right = tmp;
255                         EncodingSubGraph *tmpsg = leftGraph; leftGraph = rightGraph; rightGraph = tmpsg;
256                 }
257
258                 uint leftSize = 0, rightSize = 0, newSize = 0;
259                 uint64_t totalCost = 0;
260                 if (leftGraph == NULL && rightGraph == NULL) {
261                         leftSize = convertSize(left->getSize());
262                         rightSize = convertSize(right->getSize());
263                         newSize = convertSize(left->s->getUnionSize(right->s));
264                         newSize = (leftSize > newSize) ? leftSize : newSize;
265                         newSize = (rightSize > newSize) ? rightSize : newSize;
266                         totalCost = (newSize - leftSize) * left->elements.getSize() +
267                                                                         (newSize - rightSize) * right->elements.getSize();
268                 } else if (leftGraph != NULL && rightGraph == NULL) {
269                         leftSize = convertSize(leftGraph->encodingSize);
270                         rightSize = convertSize(right->getSize());
271                         newSize = convertSize(leftGraph->estimateNewSize(right));
272                         newSize = (leftSize > newSize) ? leftSize : newSize;
273                         newSize = (rightSize > newSize) ? rightSize : newSize;
274                         totalCost = (newSize - leftSize) * leftGraph->numElements +
275                                                                         (newSize - rightSize) * right->elements.getSize();
276                 } else {
277                         //Neither are null
278                         leftSize = convertSize(leftGraph->encodingSize);
279                         rightSize = convertSize(rightGraph->encodingSize);
280                         newSize = convertSize(leftGraph->estimateNewSize(rightGraph));
281                         newSize = (leftSize > newSize) ? leftSize : newSize;
282                         newSize = (rightSize > newSize) ? rightSize : newSize;
283                         totalCost = (newSize - leftSize) * leftGraph->numElements +
284                                                                         (newSize - rightSize) * rightGraph->numElements;
285                 }
286                 double conversionfactor = 0.5;
287                 if ((totalCost * conversionfactor) < eeValue) {
288                         //add the edge
289                         mergeNodes(left, right);
290                 }
291         }
292 }
293
294 static TunableDesc EdgeEncodingDesc(EDGE_UNASSIGNED, EDGE_MATCH, EDGE_UNASSIGNED);
295
296 EncodingEdge *EncodingGraph::getEdge(EncodingNode *left, EncodingNode *right, EncodingNode *dst) {
297         EncodingEdge e(left, right, dst);
298         EncodingEdge *result = edgeMap.get(&e);
299         return result;
300 }
301
302 EncodingEdge *EncodingGraph::createEdge(EncodingNode *left, EncodingNode *right, EncodingNode *dst) {
303         EncodingEdge e(left, right, dst);
304         EncodingEdge *result = edgeMap.get(&e);
305         if (result == NULL) {
306                 result = new EncodingEdge(left, right, dst);
307                 VarType v1 = left->getType();
308                 VarType v2 = right->getType();
309                 if (v1 > v2) {
310                         VarType tmp = v2;
311                         v2 = v1;
312                         v1 = tmp;
313                 }
314
315                 if ((left != NULL && left->couldBeBinaryIndex()) &&
316                                 (right != NULL) && right->couldBeBinaryIndex()) {
317                         EdgeEncodingType type = (EdgeEncodingType)solver->getTuner()->getVarTunable(v1, v2, EDGEENCODING, &EdgeEncodingDesc);
318                         result->setEncoding(type);
319                         if (type == EDGE_MATCH) {
320                                 mergeNodes(left, right);
321                         }
322                 }
323                 edgeMap.put(result, result);
324                 edgeVector.push(result);
325                 if (left != NULL)
326                         left->edges.add(result);
327                 if (right != NULL)
328                         right->edges.add(result);
329                 if (dst != NULL)
330                         dst->edges.add(result);
331         }
332         return result;
333 }
334
335 EncodingNode::EncodingNode(Set *_s) :
336         s(_s) {
337 }
338
339 uint EncodingNode::getSize() const {
340         return s->getSize();
341 }
342
343 VarType EncodingNode::getType() const {
344         return s->getType();
345 }
346
347 static TunableDesc NodeEncodingDesc(ELEM_UNASSIGNED, BINARYINDEX, ELEM_UNASSIGNED);
348
349 EncodingNode *EncodingGraph::createNode(Element *e) {
350         if (e->type == ELEMCONST)
351                 return NULL;
352         Set *s = e->getRange();
353         EncodingNode *n = encodingMap.get(s);
354         if (n == NULL) {
355                 n = new EncodingNode(s);
356                 n->setEncoding((ElementEncodingType)solver->getTuner()->getVarTunable(n->getType(), NODEENCODING, &NodeEncodingDesc));
357
358                 encodingMap.put(s, n);
359         }
360         n->addElement(e);
361         return n;
362 }
363
364 EncodingNode *EncodingGraph::getNode(Element *e) {
365         if (e->type == ELEMCONST)
366                 return NULL;
367         Set *s = e->getRange();
368         EncodingNode *n = encodingMap.get(s);
369         return n;
370 }
371
372 void EncodingNode::addElement(Element *e) {
373         elements.add(e);
374 }
375
376 EncodingEdge::EncodingEdge(EncodingNode *_l, EncodingNode *_r) :
377         left(_l),
378         right(_r),
379         dst(NULL),
380         encoding(EDGE_UNASSIGNED),
381         numArithOps(0),
382         numEquals(0),
383         numComparisons(0)
384 {
385 }
386
387 EncodingEdge::EncodingEdge(EncodingNode *_left, EncodingNode *_right, EncodingNode *_dst) :
388         left(_left),
389         right(_right),
390         dst(_dst),
391         encoding(EDGE_UNASSIGNED),
392         numArithOps(0),
393         numEquals(0),
394         numComparisons(0)
395 {
396 }
397
398 uint hashEncodingEdge(EncodingEdge *edge) {
399         uintptr_t hash = (((uintptr_t) edge->left) >> 2) ^ (((uintptr_t)edge->right) >> 4) ^ (((uintptr_t)edge->dst) >> 6);
400         return (uint) hash;
401 }
402
403 bool equalsEncodingEdge(EncodingEdge *e1, EncodingEdge *e2) {
404         return e1->left == e2->left && e1->right == e2->right && e1->dst == e2->dst;
405 }
406
407 uint64_t EncodingEdge::getValue() const {
408         uint lSize = (left != NULL) ? left->getSize() : 1;
409         uint rSize = (right != NULL) ? right->getSize() : 1;
410         uint min = (lSize < rSize) ? lSize : rSize;
411         return numEquals * min + numComparisons * lSize * rSize;
412 }
413
414