Bug fix in merge heuristic
[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
56 void EncodingGraph::validate() {
57         SetIteratorBooleanEdge* it= solver->getConstraints();
58         while(it->hasNext()){
59                 BooleanEdge be = it->next();
60                 if(be->type == PREDICATEOP){
61                         BooleanPredicate *b = (BooleanPredicate *)be.getBoolean();
62                         if(b->predicate->type == OPERATORPRED){
63                                 PredicateOperator* predicate = (PredicateOperator*) b->predicate;
64                                 if(predicate->getOp() == SATC_EQUALS){
65                                         ASSERT(b->inputs.getSize() == 2);
66                                         Element* e1= b->inputs.get(0);
67                                         Element* e2= b->inputs.get(1);
68                                         if(e1->type == ELEMCONST || e1->type == ELEMCONST)
69                                                 continue;
70                                         ElementEncoding *enc1 = e1->getElementEncoding();
71                                         ElementEncoding *enc2 = e2->getElementEncoding();
72                                         ASSERT(enc1->getElementEncodingType() != ELEM_UNASSIGNED);
73                                         ASSERT(enc2->getElementEncodingType() != ELEM_UNASSIGNED);
74                                         if(enc1->getElementEncodingType() == enc2->getElementEncodingType() && enc1->getElementEncodingType() == BINARYINDEX && b->getFunctionEncoding()->type == CIRCUIT){
75                                                 for(uint i=0; i<enc1->encArraySize; i++){
76                                                         if(enc1->isinUseElement(i)){
77                                                                 uint64_t val1 = enc1->encodingArray[i];
78                                                                 if(enc2->isinUseElement(i)){
79                                                                         ASSERT(val1 == enc2->encodingArray[i]);
80                                                                 }else{
81                                                                         for(uint j=0; j< enc2->encArraySize; j++){
82                                                                                 if(enc2->isinUseElement(j)){
83                                                                                         ASSERT(val1 != enc2->encodingArray[j]);
84                                                                                 }
85                                                                         }
86                                                                 }
87                                                         }
88                                                 }
89                                         }
90                                         //Now make sure that all the elements in the set are appeared in the encoding array!
91                                         for(uint k=0; k< b->inputs.getSize(); k++){
92                                                 Element *e = b->inputs.get(k);
93                                                 ElementEncoding *enc = e->getElementEncoding();
94                                                 Set *s = e->getRange();
95                                                 for (uint i = 0; i < s->getSize(); i++) {
96                                                         uint64_t value = s->getElement(i);
97                                                         bool exist=false;
98                                                         for(uint j=0; j< enc->encArraySize; j++){
99                                                                 if(enc->isinUseElement(j) && enc->encodingArray[j] == value){
100                                                                         exist = true;
101                                                                         break;
102                                                                 }
103                                                         }
104                                                         ASSERT(exist);
105                                                 }
106                                         }
107                                 }
108                         }
109                 }
110         }
111         delete it;
112 }
113
114
115 void EncodingGraph::encode() {
116         SetIteratorEncodingSubGraph *itesg = subgraphs.iterator();
117         model_print("#SubGraph = %u", subgraphs.getSize());
118         while (itesg->hasNext()) {
119                 EncodingSubGraph *sg = itesg->next();
120                 sg->encode();
121         }
122         delete itesg;
123
124         ElementIterator it(solver);
125         while (it.hasNext()) {
126                 Element *e = it.next();
127                 switch (e->type) {
128                 case ELEMSET:
129                 case ELEMFUNCRETURN: {
130                         ElementEncoding *encoding = e->getElementEncoding();
131                         if (encoding->getElementEncodingType() == ELEM_UNASSIGNED) {
132                                 EncodingNode *n = getNode(e);
133                                 if (n == NULL)
134                                         continue;
135                                 ElementEncodingType encodetype = n->getEncoding();
136                                 encoding->setElementEncodingType(encodetype);
137                                 if (encodetype == UNARY || encodetype == ONEHOT) {
138                                         encoding->encodingArrayInitialization();
139                                 } else if (encodetype == BINARYINDEX) {
140                                         EncodingSubGraph *subgraph = graphMap.get(n);
141                                         DEBUG("graphMap.get(subgraph=%p, n=%p)\n", subgraph, n);
142                                         if (subgraph == NULL) {
143                                                 encoding->encodingArrayInitialization();
144                                                 continue;
145                                         }
146                                         uint encodingSize = subgraph->getEncodingMaxVal(n) + 1;
147                                         uint paddedSize = encoding->getSizeEncodingArray(encodingSize);
148                                         encoding->allocInUseArrayElement(paddedSize);
149                                         encoding->allocEncodingArrayElement(paddedSize);
150                                         Set *s = e->getRange();
151                                         for (uint i = 0; i < s->getSize(); i++) {
152                                                 uint64_t value = s->getElement(i);
153                                                 uint encodingIndex = subgraph->getEncoding(n, value);
154                                                 encoding->setInUseElement(encodingIndex);
155                                                 ASSERT(encoding->isinUseElement(encodingIndex));
156                                                 encoding->encodingArray[encodingIndex] = value;
157                                         }
158                                 } else{
159                                         model_print("DAMN in encode()\n");
160                                         e->print();
161                                 }
162                         }
163                         break;
164                 }
165                 default:
166                         break;
167                 }
168                 encodeParent(e);
169         }
170 }
171
172 void EncodingGraph::encodeParent(Element *e) {
173         uint size = e->parents.getSize();
174         for (uint i = 0; i < size; i++) {
175                 ASTNode *n = e->parents.get(i);
176                 if (n->type == PREDICATEOP) {
177                         BooleanPredicate *b = (BooleanPredicate *)n;
178                         FunctionEncoding *fenc = b->getFunctionEncoding();
179                         if (fenc->getFunctionEncodingType() != FUNC_UNASSIGNED)
180                                 continue;
181                         Predicate *p = b->getPredicate();
182                         if (p->type == OPERATORPRED) {
183                                 PredicateOperator *po = (PredicateOperator *)p;
184                                 ASSERT(b->inputs.getSize() == 2);
185                                 EncodingNode *left = createNode(b->inputs.get(0));
186                                 EncodingNode *right = createNode(b->inputs.get(1));
187                                 if (left == NULL || right == NULL)
188                                         return;
189                                 EncodingEdge *edge = getEdge(left, right, NULL);
190                                 if (edge != NULL) {
191                                         EncodingSubGraph *leftGraph = graphMap.get(left);
192                                         if (leftGraph != NULL && leftGraph == graphMap.get(right)) {
193                                                 fenc->setFunctionEncodingType(CIRCUIT);
194                                         }
195                                 }
196                         }
197                 }
198         }
199 }
200
201 void EncodingGraph::mergeNodes(EncodingNode *first, EncodingNode *second) {
202         EncodingSubGraph *graph1 = graphMap.get(first);
203         DEBUG("graphMap.get(first=%p, graph1=%p)\n", first, graph1);
204         EncodingSubGraph *graph2 = graphMap.get(second);
205         DEBUG("graphMap.get(second=%p, graph2=%p)\n", second, graph2);
206         if (graph1 == NULL)
207                 first->setEncoding(BINARYINDEX);
208         if (graph2 == NULL)
209                 second->setEncoding(BINARYINDEX);
210         
211         if (graph1 == NULL && graph2 == NULL) {
212                 graph1 = new EncodingSubGraph();
213                 subgraphs.add(graph1);
214                 DEBUG("graphMap.put(first=%p, graph1=%p)\n", first, graph1);
215                 graphMap.put(first, graph1);
216                 graph1->addNode(first);
217         }
218         if (graph1 == NULL && graph2 != NULL) {
219                 graph1 = graph2;
220                 graph2 = NULL;
221                 EncodingNode *tmp = second;
222                 second = first;
223                 first = tmp;
224         }
225         if (graph1 != NULL && graph2 != NULL) {
226                 if (graph1 == graph2)
227                         return;
228
229                 SetIteratorEncodingNode *nodeit = graph2->nodeIterator();
230                 while (nodeit->hasNext()) {
231                         EncodingNode *node = nodeit->next();
232                         graph1->addNode(node);
233                         DEBUG("graphMap.put(node=%p, graph1=%p)\n", node, graph1);
234                         graphMap.put(node, graph1);
235                 }
236                 subgraphs.remove(graph2);
237                 delete nodeit;
238                 DEBUG("Deleting graph2 =%p \n", graph2);
239                 delete graph2;
240         } else {
241                 ASSERT(graph1 != NULL && graph2 == NULL);
242                 graph1->addNode(second);
243                 DEBUG("graphMap.put(first=%p, graph1=%p)\n", first, graph1);
244                 graphMap.put(second, graph1);
245         }
246 }
247
248 void EncodingGraph::processElement(Element *e) {
249         uint size = e->parents.getSize();
250         for (uint i = 0; i < size; i++) {
251                 ASTNode *n = e->parents.get(i);
252                 switch (n->type) {
253                 case PREDICATEOP:
254                         processPredicate((BooleanPredicate *)n);
255                         break;
256                 case ELEMFUNCRETURN:
257                         processFunction((ElementFunction *)n);
258                         break;
259                 default:
260                         ASSERT(0);
261                 }
262         }
263 }
264
265 void EncodingGraph::processFunction(ElementFunction *ef) {
266         Function *f = ef->getFunction();
267         if (f->type == OPERATORFUNC) {
268                 FunctionOperator *fo = (FunctionOperator *)f;
269                 ASSERT(ef->inputs.getSize() == 2);
270                 EncodingNode *left = createNode(ef->inputs.get(0));
271                 EncodingNode *right = createNode(ef->inputs.get(1));
272                 if (left == NULL && right == NULL)
273                         return;
274                 EncodingNode *dst = createNode(ef);
275                 EncodingEdge *edge = createEdge(left, right, dst);
276                 edge->numArithOps++;
277         }
278 }
279
280 void EncodingGraph::processPredicate(BooleanPredicate *b) {
281         Predicate *p = b->getPredicate();
282         if (p->type == OPERATORPRED) {
283                 PredicateOperator *po = (PredicateOperator *)p;
284                 ASSERT(b->inputs.getSize() == 2);
285                 EncodingNode *left = createNode(b->inputs.get(0));
286                 EncodingNode *right = createNode(b->inputs.get(1));
287                 if (left == NULL || right == NULL)
288                         return;
289                 EncodingEdge *edge = createEdge(left, right, NULL);
290                 CompOp op = po->getOp();
291                 switch (op) {
292                 case SATC_EQUALS:
293                         edge->numEquals++;
294                         break;
295                 case SATC_LT:
296                 case SATC_LTE:
297                 case SATC_GT:
298                 case SATC_GTE:
299                         edge->numComparisons++;
300                         break;
301                 default:
302                         ASSERT(0);
303                 }
304         }
305 }
306
307 uint convertSize(uint cost) {
308         cost = FUDGEFACTOR * cost;// fudge factor
309         return NEXTPOW2(cost);
310 }
311
312 void EncodingGraph::decideEdges() {
313         uint size = edgeVector.getSize();
314         for (uint i = 0; i < size; i++) {
315                 EncodingEdge *ee = edgeVector.get(i);
316                 EncodingNode *left = ee->left;
317                 EncodingNode *right = ee->right;
318
319                 if (ee->encoding != EDGE_UNASSIGNED ||
320                                 !left->couldBeBinaryIndex() ||
321                                 !right->couldBeBinaryIndex())
322                         continue;
323
324                 uint64_t eeValue = ee->getValue();
325                 if (eeValue == 0)
326                         return;
327
328                 EncodingSubGraph *leftGraph = graphMap.get(left);
329                 DEBUG("graphMap.get(left=%p, leftgraph=%p)\n", left, leftGraph);
330                 EncodingSubGraph *rightGraph = graphMap.get(right);
331                 DEBUG("graphMap.get(right=%p, rightgraph=%p)\n", right, rightGraph);
332                 if (leftGraph == NULL && rightGraph != NULL) {
333                         EncodingNode *tmp = left; left = right; right = tmp;
334                         EncodingSubGraph *tmpsg = leftGraph; leftGraph = rightGraph; rightGraph = tmpsg;
335                 }
336                 //model_print("Right=%p RGraph=%p\tLeft=%p LGraph=%p\n", right, rightGraph, left, leftGraph);
337                 uint leftSize = 0, rightSize = 0, newSize = 0, max=0;
338                 uint64_t totalCost = 0;
339                 bool merge = false;
340 //              model_print("**************decideEdge*************\n");
341 //              model_print("LeftNode Size = %u\n", left->getSize());
342 //              model_print("rightNode Size = %u\n", right->getSize());
343 //              model_print("UnionSize = %u\n", left->s->getUnionSize(right->s));
344                         
345                 if (leftGraph == NULL && rightGraph == NULL) {
346                         leftSize = convertSize(left->getSize());
347                         rightSize = convertSize(right->getSize());
348                         newSize = convertSize(left->s->getUnionSize(right->s));
349                         newSize = (leftSize > newSize) ? leftSize : newSize;
350                         newSize = (rightSize > newSize) ? rightSize : newSize;
351                         totalCost = (newSize - leftSize) * left->elements.getSize() +
352                                                                         (newSize - rightSize) * right->elements.getSize();
353                         //model_print("leftSize=%u\trighSize=%u\tnewSize=%u\n", leftSize, rightSize, newSize);
354                         max = rightSize > leftSize? rightSize : leftSize;
355                         if(newSize == max){
356                                 merge = true;
357                         }
358                 } else if (leftGraph != NULL && rightGraph == NULL) {
359                         leftSize = convertSize(leftGraph->encodingSize);
360                         rightSize = convertSize(right->getSize());
361                         newSize = convertSize(leftGraph->estimateNewSize(right));
362                         newSize = (leftSize > newSize) ? leftSize : newSize;
363                         newSize = (rightSize > newSize) ? rightSize : newSize;
364                         totalCost = (newSize - leftSize) * leftGraph->numElements +
365                                                                         (newSize - rightSize) * right->elements.getSize();
366                         //model_print("leftSize=%u\trighSize=%u\tnewSize=%u\n", leftSize, rightSize, newSize);
367                         max = rightSize > leftSize? rightSize : leftSize;
368                         if(newSize == max){
369                                 merge = true;
370                         }
371                 } else {
372                         //Neither are null
373                         leftSize = convertSize(leftGraph->encodingSize);
374                         rightSize = convertSize(rightGraph->encodingSize);
375                         newSize = convertSize(leftGraph->estimateNewSize(rightGraph));
376                         newSize = (leftSize > newSize) ? leftSize : newSize;
377                         newSize = (rightSize > newSize) ? rightSize : newSize;
378                         totalCost = (newSize - leftSize) * leftGraph->numElements +
379                                                                         (newSize - rightSize) * rightGraph->numElements;
380 //                      model_print("LeftGraph size=%u\n", leftGraph->encodingSize);
381 //                      model_print("RightGraph size=%u\n", rightGraph->encodingSize);
382 //                      model_print("UnionGraph size = %u\n", leftGraph->estimateNewSize(rightGraph));
383                         if(rightSize < 64 && leftSize < 64){
384                                 merge = true;
385                         }
386                 }
387 //              model_print("******************************\n");
388                 if (merge) {
389                         //add the edge
390                         mergeNodes(left, right);
391                 }
392         }
393 }
394
395 static TunableDesc EdgeEncodingDesc(EDGE_UNASSIGNED, EDGE_MATCH, EDGE_UNASSIGNED);
396
397 EncodingEdge *EncodingGraph::getEdge(EncodingNode *left, EncodingNode *right, EncodingNode *dst) {
398         EncodingEdge e(left, right, dst);
399         EncodingEdge *result = edgeMap.get(&e);
400         return result;
401 }
402
403 EncodingEdge *EncodingGraph::createEdge(EncodingNode *left, EncodingNode *right, EncodingNode *dst) {
404         EncodingEdge e(left, right, dst);
405         EncodingEdge *result = edgeMap.get(&e);
406         if (result == NULL) {
407                 result = new EncodingEdge(left, right, dst);
408                 VarType v1 = left->getType();
409                 VarType v2 = right->getType();
410                 if (v1 > v2) {
411                         VarType tmp = v2;
412                         v2 = v1;
413                         v1 = tmp;
414                 }
415
416                 if ((left != NULL && left->couldBeBinaryIndex()) &&
417                                 (right != NULL) && right->couldBeBinaryIndex()) {
418                         EdgeEncodingType type = (EdgeEncodingType)solver->getTuner()->getVarTunable(v1, v2, EDGEENCODING, &EdgeEncodingDesc);
419                         result->setEncoding(type);
420                         if (type == EDGE_MATCH) {
421                                 mergeNodes(left, right);
422                         }
423                 }
424                 edgeMap.put(result, result);
425                 edgeVector.push(result);
426                 if (left != NULL)
427                         left->edges.add(result);
428                 if (right != NULL)
429                         right->edges.add(result);
430                 if (dst != NULL)
431                         dst->edges.add(result);
432         }
433         return result;
434 }
435
436 EncodingNode::EncodingNode(Set *_s) :
437         s(_s) {
438 }
439
440 uint EncodingNode::getSize() const {
441         return s->getSize();
442 }
443
444 VarType EncodingNode::getType() const {
445         return s->getType();
446 }
447
448 static TunableDesc NodeEncodingDesc(ELEM_UNASSIGNED, BINARYINDEX, ELEM_UNASSIGNED);
449
450 EncodingNode *EncodingGraph::createNode(Element *e) {
451         if (e->type == ELEMCONST)
452                 return NULL;
453         Set *s = e->getRange();
454         EncodingNode *n = encodingMap.get(s);
455         if (n == NULL) {
456                 n = new EncodingNode(s);
457                 n->setEncoding((ElementEncodingType)solver->getTuner()->getVarTunable(n->getType(), NODEENCODING, &NodeEncodingDesc));
458
459                 encodingMap.put(s, n);
460         }
461         n->addElement(e);
462         return n;
463 }
464
465 EncodingNode *EncodingGraph::getNode(Element *e) {
466         if (e->type == ELEMCONST)
467                 return NULL;
468         Set *s = e->getRange();
469         EncodingNode *n = encodingMap.get(s);
470         return n;
471 }
472
473 void EncodingNode::addElement(Element *e) {
474         elements.add(e);
475 }
476
477 EncodingEdge::EncodingEdge(EncodingNode *_l, EncodingNode *_r) :
478         left(_l),
479         right(_r),
480         dst(NULL),
481         encoding(EDGE_UNASSIGNED),
482         numArithOps(0),
483         numEquals(0),
484         numComparisons(0)
485 {
486 }
487
488 EncodingEdge::EncodingEdge(EncodingNode *_left, EncodingNode *_right, EncodingNode *_dst) :
489         left(_left),
490         right(_right),
491         dst(_dst),
492         encoding(EDGE_UNASSIGNED),
493         numArithOps(0),
494         numEquals(0),
495         numComparisons(0)
496 {
497 }
498
499 uint hashEncodingEdge(EncodingEdge *edge) {
500         uintptr_t hash = (((uintptr_t) edge->left) >> 2) ^ (((uintptr_t)edge->right) >> 4) ^ (((uintptr_t)edge->dst) >> 6);
501         return (uint) hash;
502 }
503
504 bool equalsEncodingEdge(EncodingEdge *e1, EncodingEdge *e2) {
505         return e1->left == e2->left && e1->right == e2->right && e1->dst == e2->dst;
506 }
507
508 uint64_t EncodingEdge::getValue() const {
509         uint lSize = (left != NULL) ? left->getSize() : 1;
510         uint rSize = (right != NULL) ? right->getSize() : 1;
511         uint min = (lSize < rSize) ? lSize : rSize;
512         return numEquals * min + numComparisons * lSize * rSize;
513 }
514
515