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                                         DEBUG("graphMap.get(subgraph=%p, n=%p)\n", subgraph, n);
  81                                         if (subgraph == NULL){
  82                                                 encoding->encodingArrayInitialization();
  83                                                 continue;
  84                                         }
  85                                         uint encodingSize = subgraph->getEncodingMaxVal(n) + 1;
  86                                         uint paddedSize = encoding->getSizeEncodingArray(encodingSize);
  87                                         encoding->allocInUseArrayElement(paddedSize);
  88                                         encoding->allocEncodingArrayElement(paddedSize);
  89                                         Set *s = e->getRange();
  90                                         for (uint i = 0; i < s->getSize(); 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         DEBUG("graphMap.get(first=%p, graph1=%p)\n", first, graph1);
 136         EncodingSubGraph *graph2 = graphMap.get(second);
 137         DEBUG("graphMap.get(second=%p, graph2=%p)\n", second, graph2);
 138         if (graph1 == NULL)
 139                 first->setEncoding(BINARYINDEX);
 140         if (graph2 == NULL)
 141                 second->setEncoding(BINARYINDEX);
 142
 143         if (graph1 == NULL && graph2 == NULL) {
 144                 graph1 = new EncodingSubGraph();
 145                 subgraphs.add(graph1);
 146                 DEBUG("graphMap.put(first=%p, graph1=%p)\n", first, graph1);
 147                 graphMap.put(first, graph1);
 148                 graph1->addNode(first);
 149         }
 150         if (graph1 == NULL && graph2 != NULL) {
 151                 graph1 = graph2;
 152                 graph2 = NULL;
 153                 EncodingNode *tmp = second;
 154                 second = first;
 155                 first = tmp;
 156         }
 157         if (graph1 != NULL && graph2 != NULL) {
 158                 SetIteratorEncodingNode *nodeit = graph2->nodeIterator();
 159                 while (nodeit->hasNext()) {
 160                         EncodingNode *node = nodeit->next();
 161                         graph1->addNode(node);
 162                         DEBUG("graphMap.put(node=%p, graph1=%p)\n", node, graph1);
 163                         graphMap.put(node, graph1);
 164                 }
 165                 subgraphs.remove(graph2);
 166                 delete nodeit;
 167                 DEBUG("Deleting graph2 =%p \n", graph2);
 168                 delete graph2;
 169         } else {
 170                 ASSERT(graph1 != NULL && graph2 == NULL);
 171                 graph1->addNode(first);
 172                 DEBUG("graphMap.put(first=%p, graph1=%p)\n", first, graph1);
 173                 graphMap.put(first, graph1);
 174         }
 175 }
 176
 177 void EncodingGraph::processElement(Element *e) {
 178         uint size = e->parents.getSize();
 179         for (uint i = 0; i < size; i++) {
 180                 ASTNode *n = e->parents.get(i);
 181                 switch (n->type) {
 182                 case PREDICATEOP:
 183                         processPredicate((BooleanPredicate *)n);
 184                         break;
 185                 case ELEMFUNCRETURN:
 186                         processFunction((ElementFunction *)n);
 187                         break;
 188                 default:
 189                         ASSERT(0);
 190                 }
 191         }
 192 }
 193
 194 void EncodingGraph::processFunction(ElementFunction *ef) {
 195         Function *f = ef->getFunction();
 196         if (f->type == OPERATORFUNC) {
 197                 FunctionOperator *fo = (FunctionOperator *)f;
 198                 ASSERT(ef->inputs.getSize() == 2);
 199                 EncodingNode *left = createNode(ef->inputs.get(0));
 200                 EncodingNode *right = createNode(ef->inputs.get(1));
 201                 if (left == NULL && right == NULL)
 202                         return;
 203                 EncodingNode *dst = createNode(ef);
 204                 EncodingEdge *edge = createEdge(left, right, dst);
 205                 edge->numArithOps++;
 206         }
 207 }
 208
 209 void EncodingGraph::processPredicate(BooleanPredicate *b) {
 210         Predicate *p = b->getPredicate();
 211         if (p->type == OPERATORPRED) {
 212                 PredicateOperator *po = (PredicateOperator *)p;
 213                 ASSERT(b->inputs.getSize() == 2);
 214                 EncodingNode *left = createNode(b->inputs.get(0));
 215                 EncodingNode *right = createNode(b->inputs.get(1));
 216                 if (left == NULL || right == NULL)
 217                         return;
 218                 EncodingEdge *edge = createEdge(left, right, NULL);
 219                 CompOp op = po->getOp();
 220                 switch (op) {
 221                 case SATC_EQUALS:
 222                         edge->numEquals++;
 223                         break;
 224                 case SATC_LT:
 225                 case SATC_LTE:
 226                 case SATC_GT:
 227                 case SATC_GTE:
 228                         edge->numComparisons++;
 229                         break;
 230                 default:
 231                         ASSERT(0);
 232                 }
 233         }
 234 }
 235
 236 uint convertSize(uint cost) {
 237         cost = 1.2 * cost;// fudge factor
 238         return NEXTPOW2(cost);
 239 }
 240
 241 void EncodingGraph::decideEdges() {
 242         uint size = edgeVector.getSize();
 243         for (uint i = 0; i < size; i++) {
 244                 EncodingEdge *ee = edgeVector.get(i);
 245                 EncodingNode *left = ee->left;
 246                 EncodingNode *right = ee->right;
 247
 248                 if (ee->encoding != EDGE_UNASSIGNED ||
 249                                 !left->couldBeBinaryIndex() ||
 250                                 !right->couldBeBinaryIndex())
 251                         continue;
 252
 253                 uint64_t eeValue = ee->getValue();
 254                 if (eeValue == 0)
 255                         return;
 256
 257                 EncodingSubGraph *leftGraph = graphMap.get(left);
 258                 DEBUG("graphMap.get(left=%p, leftgraph=%p)\n", left, leftGraph);
 259                 EncodingSubGraph *rightGraph = graphMap.get(right);
 260                 DEBUG("graphMap.get(right=%p, rightgraph=%p)\n", right, rightGraph);
 261                 if (leftGraph == NULL && rightGraph != NULL) {
 262                         EncodingNode *tmp = left; left = right; right = tmp;
 263                         EncodingSubGraph *tmpsg = leftGraph; leftGraph = rightGraph; rightGraph = tmpsg;
 264                 }
 265
 266                 uint leftSize = 0, rightSize = 0, newSize = 0;
 267                 uint64_t totalCost = 0;
 268                 if (leftGraph == NULL && rightGraph == NULL) {
 269                         leftSize = convertSize(left->getSize());
 270                         rightSize = convertSize(right->getSize());
 271                         newSize = convertSize(left->s->getUnionSize(right->s));
 272                         newSize = (leftSize > newSize) ? leftSize : newSize;
 273                         newSize = (rightSize > newSize) ? rightSize : newSize;
 274                         totalCost = (newSize - leftSize) * left->elements.getSize() +
 275                                                                         (newSize - rightSize) * right->elements.getSize();
 276                 } else if (leftGraph != NULL && rightGraph == NULL) {
 277                         leftSize = convertSize(leftGraph->encodingSize);
 278                         rightSize = convertSize(right->getSize());
 279                         newSize = convertSize(leftGraph->estimateNewSize(right));
 280                         newSize = (leftSize > newSize) ? leftSize : newSize;
 281                         newSize = (rightSize > newSize) ? rightSize : newSize;
 282                         totalCost = (newSize - leftSize) * leftGraph->numElements +
 283                                                                         (newSize - rightSize) * right->elements.getSize();
 284                 } else {
 285                         //Neither are null
 286                         leftSize = convertSize(leftGraph->encodingSize);
 287                         rightSize = convertSize(rightGraph->encodingSize);
 288                         newSize = convertSize(leftGraph->estimateNewSize(rightGraph));
 289                         newSize = (leftSize > newSize) ? leftSize : newSize;
 290                         newSize = (rightSize > newSize) ? rightSize : newSize;
 291                         totalCost = (newSize - leftSize) * leftGraph->numElements +
 292                                                                         (newSize - rightSize) * rightGraph->numElements;
 293                 }
 294                 double conversionfactor = 0.5;
 295                 if (leftGraph != rightGraph && (totalCost * conversionfactor) < eeValue) {
 296                         //add the edge
 297                         mergeNodes(left, right);
 298                 }
 299         }
 300 }
 301
 302 static TunableDesc EdgeEncodingDesc(EDGE_UNASSIGNED, EDGE_MATCH, EDGE_UNASSIGNED);
 303
 304 EncodingEdge *EncodingGraph::getEdge(EncodingNode *left, EncodingNode *right, EncodingNode *dst) {
 305         EncodingEdge e(left, right, dst);
 306         EncodingEdge *result = edgeMap.get(&e);
 307         return result;
 308 }
 309
 310 EncodingEdge *EncodingGraph::createEdge(EncodingNode *left, EncodingNode *right, EncodingNode *dst) {
 311         EncodingEdge e(left, right, dst);
 312         EncodingEdge *result = edgeMap.get(&e);
 313         if (result == NULL) {
 314                 result = new EncodingEdge(left, right, dst);
 315                 VarType v1 = left->getType();
 316                 VarType v2 = right->getType();
 317                 if (v1 > v2) {
 318                         VarType tmp = v2;
 319                         v2 = v1;
 320                         v1 = tmp;
 321                 }
 322
 323                 if ((left != NULL && left->couldBeBinaryIndex()) &&
 324                                 (right != NULL) && right->couldBeBinaryIndex()) {
 325                         EdgeEncodingType type = (EdgeEncodingType)solver->getTuner()->getVarTunable(v1, v2, EDGEENCODING, &EdgeEncodingDesc);
 326                         result->setEncoding(type);
 327                         if (type == EDGE_MATCH) {
 328                                 mergeNodes(left, right);
 329                         }
 330                 }
 331                 edgeMap.put(result, result);
 332                 edgeVector.push(result);
 333                 if (left != NULL)
 334                         left->edges.add(result);
 335                 if (right != NULL)
 336                         right->edges.add(result);
 337                 if (dst != NULL)
 338                         dst->edges.add(result);
 339         }
 340         return result;
 341 }
 342
 343 EncodingNode::EncodingNode(Set *_s) :
 344         s(_s) {
 345 }
 346
 347 uint EncodingNode::getSize() const {
 348         return s->getSize();
 349 }
 350
 351 VarType EncodingNode::getType() const {
 352         return s->getType();
 353 }
 354
 355 static TunableDesc NodeEncodingDesc(ELEM_UNASSIGNED, BINARYINDEX, ELEM_UNASSIGNED);
 356
 357 EncodingNode *EncodingGraph::createNode(Element *e) {
 358         if (e->type == ELEMCONST)
 359                 return NULL;
 360         Set *s = e->getRange();
 361         EncodingNode *n = encodingMap.get(s);
 362         if (n == NULL) {
 363                 n = new EncodingNode(s);
 364                 n->setEncoding((ElementEncodingType)solver->getTuner()->getVarTunable(n->getType(), NODEENCODING, &NodeEncodingDesc));
 365
 366                 encodingMap.put(s, n);
 367         }
 368         n->addElement(e);
 369         return n;
 370 }
 371
 372 EncodingNode *EncodingGraph::getNode(Element *e) {
 373         if (e->type == ELEMCONST)
 374                 return NULL;
 375         Set *s = e->getRange();
 376         EncodingNode *n = encodingMap.get(s);
 377         return n;
 378 }
 379
 380 void EncodingNode::addElement(Element *e) {
 381         elements.add(e);
 382 }
 383
 384 EncodingEdge::EncodingEdge(EncodingNode *_l, EncodingNode *_r) :
 385         left(_l),
 386         right(_r),
 387         dst(NULL),
 388         encoding(EDGE_UNASSIGNED),
 389         numArithOps(0),
 390         numEquals(0),
 391         numComparisons(0)
 392 {
 393 }
 394
 395 EncodingEdge::EncodingEdge(EncodingNode *_left, EncodingNode *_right, EncodingNode *_dst) :
 396         left(_left),
 397         right(_right),
 398         dst(_dst),
 399         encoding(EDGE_UNASSIGNED),
 400         numArithOps(0),
 401         numEquals(0),
 402         numComparisons(0)
 403 {
 404 }
 405
 406 uint hashEncodingEdge(EncodingEdge *edge) {
 407         uintptr_t hash = (((uintptr_t) edge->left) >> 2) ^ (((uintptr_t)edge->right) >> 4) ^ (((uintptr_t)edge->dst) >> 6);
 408         return (uint) hash;
 409 }
 410
 411 bool equalsEncodingEdge(EncodingEdge *e1, EncodingEdge *e2) {
 412         return e1->left == e2->left && e1->right == e2->right && e1->dst == e2->dst;
 413 }
 414
 415 uint64_t EncodingEdge::getValue() const {
 416         uint lSize = (left != NULL) ? left->getSize() : 1;
 417         uint rSize = (right != NULL) ? right->getSize() : 1;
 418         uint min = (lSize < rSize) ? lSize : rSize;
 419         return numEquals * min + numComparisons * lSize * rSize;
 420 }
 421
 422