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