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 int sortEncodingEdge(const void * p1, const void *p2) {
  18         const EncodingEdge * e1 = * (const EncodingEdge **) p1;
  19         const EncodingEdge * e2 = * (const EncodingEdge **) p2;
  20         uint64_t v1 = e1->getValue();
  21         uint64_t v2 = e2->getValue();
  22         if (v1 < v2)
  23                 return 1;
  24         else if (v1 == v2)
  25                 return 0;
  26         else
  27                 return -1;
  28 }
  29
  30 void EncodingGraph::buildGraph() {
  31         ElementIterator it(solver);
  32         while(it.hasNext()) {
  33                 Element * e = it.next();
  34                 switch(e->type) {
  35                 case ELEMSET:
  36                 case ELEMFUNCRETURN:
  37                         processElement(e);
  38                         break;
  39                 case ELEMCONST:
  40                         break;
  41                 default:
  42                         ASSERT(0);
  43                 }
  44         }
  45         bsdqsort(edgeVector.expose(), edgeVector.getSize(), sizeof(EncodingEdge *), sortEncodingEdge);
  46         decideEdges();
  47 }
  48
  49 void EncodingGraph::encode() {
  50         SetIteratorEncodingSubGraph * itesg=subgraphs.iterator();
  51         while(itesg->hasNext()) {
  52                 EncodingSubGraph *sg=itesg->next();
  53                 sg->encode();
  54         }
  55         delete itesg;
  56
  57         ElementIterator it(solver);
  58         while(it.hasNext()) {
  59                 Element * e = it.next();
  60                 switch(e->type) {
  61                 case ELEMSET:
  62                 case ELEMFUNCRETURN: {
  63                         ElementEncoding *encoding=getElementEncoding(e);
  64                         if (encoding->getElementEncodingType() == ELEM_UNASSIGNED) {
  65                                 //Do assignment...
  66                         }
  67                         break;
  68                 }
  69                 default:
  70                         break;
  71                 }
  72         }
  73
  74 }
  75
  76 void EncodingGraph::mergeNodes(EncodingNode *first, EncodingNode *second) {
  77         EncodingSubGraph *graph1=graphMap.get(first);
  78         EncodingSubGraph *graph2=graphMap.get(second);
  79         if (graph1 == NULL && graph2 == NULL) {
  80                 graph1 = new EncodingSubGraph();
  81                 subgraphs.add(graph1);
  82                 graphMap.put(first, graph1);
  83                 graph1->addNode(first);
  84         }
  85         if (graph1 == NULL && graph2 != NULL) {
  86                 graph1 = graph2;
  87                 graph2 = NULL;
  88                 EncodingNode *tmp = second;
  89                 second = first;
  90                 first = tmp;
  91         }
  92         if (graph1 != NULL && graph2 != NULL) {
  93                 SetIteratorEncodingNode * nodeit=graph2->nodeIterator();
  94                 while(nodeit->hasNext()) {
  95                         EncodingNode *node=nodeit->next();
  96                         graph1->addNode(node);
  97                         graphMap.put(node, graph1);
  98                 }
  99                 subgraphs.remove(graph2);
 100                 delete nodeit;
 101                 delete graph2;
 102         } else {
 103                 ASSERT(graph1 != NULL && graph2 == NULL);
 104                 graph1->addNode(second);
 105                 graphMap.put(second, graph1);
 106         }
 107 }
 108
 109 void EncodingGraph::processElement(Element *e) {
 110         uint size=e->parents.getSize();
 111         for(uint i=0;i<size;i++) {
 112                 ASTNode * n = e->parents.get(i);
 113                 switch(n->type) {
 114                 case PREDICATEOP:
 115                         processPredicate((BooleanPredicate *)n);
 116                         break;
 117                 case ELEMFUNCRETURN:
 118                         processFunction((ElementFunction *)n);
 119                         break;
 120                 default:
 121                         ASSERT(0);
 122                 }
 123         }
 124 }
 125
 126 void EncodingGraph::processFunction(ElementFunction *ef) {
 127         Function *f=ef->getFunction();
 128         if (f->type==OPERATORFUNC) {
 129                 FunctionOperator *fo=(FunctionOperator*)f;
 130                 ASSERT(ef->inputs.getSize() == 2);
 131                 EncodingNode *left=createNode(ef->inputs.get(0));
 132                 EncodingNode *right=createNode(ef->inputs.get(1));
 133                 if (left == NULL && right == NULL)
 134                         return;
 135                 EncodingNode *dst=createNode(ef);
 136                 EncodingEdge *edge=getEdge(left, right, dst);
 137                 edge->numArithOps++;
 138         }
 139 }
 140
 141 void EncodingGraph::processPredicate(BooleanPredicate *b) {
 142         Predicate *p=b->getPredicate();
 143         if (p->type==OPERATORPRED) {
 144                 PredicateOperator *po=(PredicateOperator *)p;
 145                 ASSERT(b->inputs.getSize()==2);
 146                 EncodingNode *left=createNode(b->inputs.get(0));
 147                 EncodingNode *right=createNode(b->inputs.get(1));
 148                 if (left == NULL || right == NULL)
 149                         return;
 150                 EncodingEdge *edge=getEdge(left, right, NULL);
 151                 CompOp op=po->getOp();
 152                 switch(op) {
 153                 case SATC_EQUALS:
 154                         edge->numEquals++;
 155                         break;
 156                 case SATC_LT:
 157                 case SATC_LTE:
 158                 case SATC_GT:
 159                 case SATC_GTE:
 160                         edge->numComparisons++;
 161                         break;
 162                 default:
 163                         ASSERT(0);
 164                 }
 165         }
 166 }
 167
 168 uint convertSize(uint cost) {
 169         cost = 1.2 * cost; // fudge factor
 170         return NEXTPOW2(cost);
 171 }
 172
 173 void EncodingGraph::decideEdges() {
 174         uint size=edgeVector.getSize();
 175         for(uint i=0; i<size; i++) {
 176                 EncodingEdge *ee = edgeVector.get(i);
 177                 EncodingNode *left = ee->left;
 178                 EncodingNode *right = ee->right;
 179
 180                 if (ee->encoding != EDGE_UNASSIGNED ||
 181                                 left->encoding != BINARYINDEX ||
 182                                 right->encoding != BINARYINDEX)
 183                         continue;
 184
 185                 uint64_t eeValue = ee->getValue();
 186                 if (eeValue == 0)
 187                         return;
 188
 189                 EncodingSubGraph *leftGraph = graphMap.get(left);
 190                 EncodingSubGraph *rightGraph = graphMap.get(right);
 191                 if (leftGraph == NULL && rightGraph !=NULL) {
 192                         EncodingNode *tmp = left; left=right; right=tmp;
 193                         EncodingSubGraph *tmpsg = leftGraph; leftGraph = rightGraph; rightGraph = tmpsg;
 194                 }
 195
 196                 uint leftSize=0, rightSize=0, newSize=0;
 197                 uint64_t totalCost=0;
 198                 if (leftGraph == NULL && rightGraph == NULL) {
 199                         leftSize=convertSize(left->getSize());
 200                         rightSize=convertSize(right->getSize());
 201                         newSize=convertSize(left->s->getUnionSize(right->s));
 202                         newSize=(leftSize > newSize) ? leftSize: newSize;
 203                         newSize=(rightSize > newSize) ? rightSize: newSize;
 204                         totalCost = (newSize - leftSize) * left->elements.getSize() +
 205                                 (newSize - rightSize) * right->elements.getSize();
 206                 } else if (leftGraph != NULL && rightGraph == NULL) {
 207                         leftSize=convertSize(leftGraph->encodingSize);
 208                         rightSize=convertSize(right->getSize());
 209                         newSize=convertSize(leftGraph->estimateNewSize(right));
 210                         newSize=(leftSize > newSize) ? leftSize: newSize;
 211                         newSize=(rightSize > newSize) ? rightSize: newSize;
 212                         totalCost = (newSize - leftSize) * leftGraph->numElements +
 213                                 (newSize - rightSize) * right->elements.getSize();
 214                 } else {
 215                         //Neither are null
 216                         leftSize=convertSize(leftGraph->encodingSize);
 217                         rightSize=convertSize(rightGraph->encodingSize);
 218                         newSize=convertSize(leftGraph->estimateNewSize(rightGraph));
 219                         newSize=(leftSize > newSize) ? leftSize: newSize;
 220                         newSize=(rightSize > newSize) ? rightSize: newSize;
 221                         totalCost = (newSize - leftSize) * leftGraph->numElements +
 222                                 (newSize - rightSize) * rightGraph->numElements;
 223                 }
 224                 double conversionfactor = 0.5;
 225                 if ((totalCost * conversionfactor) < eeValue) {
 226                         //add the edge
 227                         mergeNodes(left, right);
 228                 }
 229         }
 230 }
 231
 232 static TunableDesc EdgeEncodingDesc(EDGE_UNASSIGNED, EDGE_MATCH, EDGE_UNASSIGNED);
 233
 234 EncodingEdge * EncodingGraph::getEdge(EncodingNode *left, EncodingNode *right, EncodingNode *dst) {
 235         EncodingEdge e(left, right, dst);
 236         EncodingEdge *result = edgeMap.get(&e);
 237         if (result == NULL) {
 238                 result=new EncodingEdge(left, right, dst);
 239                 VarType v1=left->getType();
 240                 VarType v2=right->getType();
 241                 if (v1 > v2) {
 242                         VarType tmp=v2;
 243                         v2=v1;
 244                         v1=tmp;
 245                 }
 246
 247                 if ((left != NULL && left->encoding==BINARYINDEX) &&
 248                                 (right != NULL) && right->encoding==BINARYINDEX) {
 249                         EdgeEncodingType type=(EdgeEncodingType)solver->getTuner()->getVarTunable(v1, v2, EDGEENCODING, &EdgeEncodingDesc);
 250                         result->setEncoding(type);
 251                         if (type == EDGE_MATCH) {
 252                                 mergeNodes(left, right);
 253                         }
 254                 }
 255                 edgeMap.put(result, result);
 256                 edgeVector.push(result);
 257                 if (left != NULL)
 258                         left->edges.add(result);
 259                 if (right != NULL)
 260                         right->edges.add(result);
 261                 if (dst != NULL)
 262                         dst->edges.add(result);
 263         }
 264         return result;
 265 }
 266
 267 EncodingNode::EncodingNode(Set *_s) :
 268         s(_s) {
 269 }
 270
 271 uint EncodingNode::getSize() const {
 272         return s->getSize();
 273 }
 274
 275 VarType EncodingNode::getType() const {
 276         return s->getType();
 277 }
 278
 279 static TunableDesc NodeEncodingDesc(ELEM_UNASSIGNED, BINARYINDEX, ELEM_UNASSIGNED);
 280
 281 EncodingNode * EncodingGraph::createNode(Element *e) {
 282         if (e->type == ELEMCONST)
 283                 return NULL;
 284         Set *s = e->getRange();
 285         EncodingNode *n = encodingMap.get(s);
 286         if (n == NULL) {
 287                 n = new EncodingNode(s);
 288                 n->setEncoding((ElementEncodingType)solver->getTuner()->getVarTunable(n->getType(), NODEENCODING, &NodeEncodingDesc));
 289                 encodingMap.put(s, n);
 290         }
 291         n->addElement(e);
 292         return n;
 293 }
 294
 295 void EncodingNode::addElement(Element *e) {
 296         elements.add(e);
 297 }
 298
 299 EncodingEdge::EncodingEdge(EncodingNode *_l, EncodingNode *_r) :
 300         left(_l),
 301         right(_r),
 302         dst(NULL),
 303         encoding(EDGE_UNASSIGNED),
 304         numArithOps(0),
 305         numEquals(0),
 306         numComparisons(0)
 307 {
 308 }
 309
 310 EncodingEdge::EncodingEdge(EncodingNode *_left, EncodingNode *_right, EncodingNode *_dst) :
 311         left(_left),
 312         right(_right),
 313         dst(_dst),
 314         encoding(EDGE_UNASSIGNED),
 315         numArithOps(0),
 316         numEquals(0),
 317         numComparisons(0)
 318 {
 319 }
 320
 321 uint hashEncodingEdge(EncodingEdge *edge) {
 322         uintptr_t hash=(((uintptr_t) edge->left) >> 2) ^ (((uintptr_t)edge->right) >> 4) ^ (((uintptr_t)edge->dst) >> 6);
 323         return (uint) hash;
 324 }
 325
 326 bool equalsEncodingEdge(EncodingEdge *e1, EncodingEdge *e2) {
 327         return e1->left == e2->left && e1->right == e2->right && e1->dst == e2->dst;
 328 }
 329
 330 uint64_t EncodingEdge::getValue() const {
 331         uint lSize = (left != NULL) ? left->getSize() : 1;
 332         uint rSize = (right != NULL) ? right->getSize() : 1;
 333         uint min = (lSize < rSize) ? lSize : rSize;
 334         return numEquals * min + numComparisons * lSize * rSize;
 335 }
 336
 337