src/ASTAnalyses/Encoding/subgraph.cc

   1 #include "subgraph.h"
   2 #include "encodinggraph.h"
   3 #include "set.h"
   4 #include "qsort.h"
   5
   6 EncodingSubGraph::EncodingSubGraph() :
   7         encodingSize(0),
   8         numElements(0),
   9         maxEncodingVal(0) {
  10 }
  11
  12 uint hashNodeValuePair(NodeValuePair *nvp) {
  13         return (uint) (nvp->value ^ ((uintptr_t)nvp->node));
  14 }
  15
  16 bool equalsNodeValuePair(NodeValuePair *nvp1, NodeValuePair *nvp2) {
  17         return nvp1->value == nvp2->value && nvp1->node == nvp2->node;
  18 }
  19
  20 int sortEncodingValue(const void *p1, const void *p2) {
  21         const EncodingValue * e1 = * (const EncodingValue **) p1;
  22         const EncodingValue * e2 = * (const EncodingValue **) p2;
  23         uint se1=e1->notequals.getSize();
  24         uint se2=e2->notequals.getSize();
  25         if (se1 > se2)
  26                 return -1;
  27         else if (se2 == se1)
  28                 return 0;
  29         else
  30                 return 1;
  31 }
  32
  33 uint EncodingSubGraph::getEncoding(EncodingNode *n, uint64_t val) {
  34         NodeValuePair nvp(n, val);
  35         EncodingValue *ev = map.get(&nvp);
  36         return ev->encoding;
  37 }
  38
  39 void EncodingSubGraph::solveEquals() {
  40         Vector<EncodingValue *> toEncode;
  41         Vector<bool> encodingArray;
  42         SetIteratorEncodingValue *valIt=values.iterator();
  43         while(valIt->hasNext()) {
  44                 EncodingValue *ev=valIt->next();
  45                 if (!ev->inComparison)
  46                         toEncode.push(ev);
  47                 else
  48                         ev->assigned = true;
  49         }
  50         delete valIt;
  51         bsdqsort(toEncode.expose(), toEncode.getSize(), sizeof(EncodingValue *), sortEncodingValue);
  52         uint toEncodeSize=toEncode.getSize();
  53         for(uint i=0; i<toEncodeSize; i++) {
  54                 EncodingValue * ev=toEncode.get(i);
  55                 encodingArray.clear();
  56                 SetIteratorEncodingValue *conflictIt=ev->notequals.iterator();
  57                 while(conflictIt->hasNext()) {
  58                         EncodingValue * conflict=conflictIt->next();
  59                         if (conflict->assigned) {
  60                                 encodingArray.setExpand(conflict->encoding, true);
  61                         }
  62                 }
  63                 delete conflictIt;
  64                 uint encoding=0;
  65                 for(;encoding<encodingArray.getSize();encoding++) {
  66                         //See if this is unassigned
  67                         if (!encodingArray.get(encoding))
  68                                 break;
  69                 }
  70                 if (encoding > maxEncodingVal)
  71                         maxEncodingVal = encoding;
  72                 ev->encoding = encoding;
  73                 ev->assigned = true;
  74         }
  75 }
  76
  77 void EncodingSubGraph::solveComparisons() {
  78         HashsetEncodingValue discovered;
  79         Vector<EncodingValue *> tovisit;
  80         SetIteratorEncodingValue *valIt=values.iterator();
  81         while(valIt->hasNext()) {
  82                 EncodingValue *ev=valIt->next();
  83                 if (discovered.add(ev)) {
  84                         tovisit.push(ev);
  85                         while(tovisit.getSize()!=0) {
  86                                 EncodingValue * val=tovisit.last(); tovisit.pop();
  87                                 SetIteratorEncodingValue *nextIt=val->larger.iterator();
  88                                 uint minVal = val->encoding + 1;
  89                                 while(nextIt->hasNext()) {
  90                                         EncodingValue *nextVal=nextIt->next();
  91                                         if (nextVal->encoding < minVal) {
  92                                                 if (minVal > maxEncodingVal)
  93                                                         maxEncodingVal = minVal;
  94                                                 nextVal->encoding = minVal;
  95                                                 discovered.add(nextVal);
  96                                                 tovisit.push(nextVal);
  97                                         }
  98                                 }
  99                                 delete nextIt;
 100                         }
 101                 }
 102         }
 103         delete valIt;
 104 }
 105
 106 uint EncodingSubGraph::estimateNewSize(EncodingSubGraph *sg) {
 107         uint newSize=0;
 108         SetIteratorEncodingNode * nit = sg->nodes.iterator();
 109         while(nit->hasNext()) {
 110                 EncodingNode *en = nit->next();
 111                 uint size=estimateNewSize(en);
 112                 if (size > newSize)
 113                         newSize = size;
 114         }
 115         delete nit;
 116         return newSize;
 117 }
 118
 119 uint EncodingSubGraph::estimateNewSize(EncodingNode *n) {
 120         SetIteratorEncodingEdge * eeit = n->edges.iterator();
 121         uint newsize=n->getSize();
 122         while(eeit->hasNext()) {
 123                 EncodingEdge * ee = eeit->next();
 124                 if (ee->left != NULL && ee->left != n && nodes.contains(ee->left)) {
 125                         uint intersectSize = n->s->getUnionSize(ee->left->s);
 126                         if (intersectSize > newsize)
 127                                 newsize = intersectSize;
 128                 }
 129                 if (ee->right != NULL && ee->right != n && nodes.contains(ee->right)) {
 130                         uint intersectSize = n->s->getUnionSize(ee->right->s);
 131                         if (intersectSize > newsize)
 132                                 newsize = intersectSize;
 133                 }
 134                 if (ee->dst != NULL && ee->dst != n && nodes.contains(ee->dst)) {
 135                         uint intersectSize = n->s->getUnionSize(ee->dst->s);
 136                         if (intersectSize > newsize)
 137                                 newsize = intersectSize;
 138                 }
 139         }
 140         delete eeit;
 141         return newsize;
 142 }
 143
 144 void EncodingSubGraph::addNode(EncodingNode *n) {
 145         nodes.add(n);
 146         uint newSize=estimateNewSize(n);
 147         numElements += n->elements.getSize();
 148         if (newSize > encodingSize)
 149                 encodingSize=newSize;
 150 }
 151
 152 SetIteratorEncodingNode * EncodingSubGraph::nodeIterator() {
 153         return nodes.iterator();
 154 }
 155
 156 void EncodingSubGraph::encode() {
 157         computeEncodingValue();
 158         computeComparisons();
 159         computeEqualities();
 160         solveComparisons();
 161         solveEquals();
 162 }
 163
 164 void EncodingSubGraph::computeEqualities() {
 165         SetIteratorEncodingNode *nodeit=nodes.iterator();
 166         while(nodeit->hasNext()) {
 167                 EncodingNode *node=nodeit->next();
 168                 generateEquals(node, node);
 169
 170                 SetIteratorEncodingEdge *edgeit=node->edges.iterator();
 171                 while(edgeit->hasNext()) {
 172                         EncodingEdge *edge=edgeit->next();
 173                         //skip over comparisons as we have already handled them
 174                         if (edge->numComparisons != 0)
 175                                 continue;
 176                         if (edge->numEquals == 0)
 177                                 continue;
 178                         if (edge->left == NULL || !nodes.contains(edge->left))
 179                                 continue;
 180                         if (edge->right == NULL || !nodes.contains(edge->right))
 181                                 continue;
 182                         //examine only once
 183                         if (edge->left != node)
 184                                 continue;
 185                         //We have a comparison edge between two nodes in the subgraph
 186                         //For now we don't support multiple encoding values with the same encoding....
 187                         //So we enforce != constraints for every Set...
 188                         if (edge->left != edge->right)
 189                                 generateEquals(edge->left, edge->right);
 190                 }
 191                 delete edgeit;
 192         }
 193         delete nodeit;
 194 }
 195
 196 void EncodingSubGraph::computeComparisons() {
 197         SetIteratorEncodingNode *nodeit=nodes.iterator();
 198         while(nodeit->hasNext()) {
 199                 EncodingNode *node=nodeit->next();
 200                 SetIteratorEncodingEdge *edgeit=node->edges.iterator();
 201                 while(edgeit->hasNext()) {
 202                         EncodingEdge *edge=edgeit->next();
 203                         if (edge->numComparisons == 0)
 204                                 continue;
 205                         if (edge->left == NULL || !nodes.contains(edge->left))
 206                                 continue;
 207                         if (edge->right == NULL || !nodes.contains(edge->right))
 208                                 continue;
 209                         //examine only once
 210                         if (edge->left != node)
 211                                 continue;
 212                         //We have a comparison edge between two nodes in the subgraph
 213                         generateComparison(edge->left, edge->right);
 214                 }
 215                 delete edgeit;
 216         }
 217         delete nodeit;
 218
 219
 220 }
 221
 222 void EncodingSubGraph::orderEV(EncodingValue *earlier, EncodingValue *later) {
 223         earlier->larger.add(later);
 224 }
 225
 226 void EncodingSubGraph::generateEquals(EncodingNode *left, EncodingNode *right) {
 227         Set *lset=left->s;
 228         Set *rset=right->s;
 229         uint lSize=lset->getSize(), rSize=rset->getSize();
 230         for(uint lindex=0; lindex < lSize; lindex++) {
 231                 for(uint rindex=0; rindex < rSize; rindex++) {
 232                         uint64_t lVal=lset->getElement(lindex);
 233                         NodeValuePair nvp1(left, lVal);
 234                         EncodingValue *lev = map.get(&nvp1);
 235                         uint64_t rVal=rset->getElement(rindex);
 236                         NodeValuePair nvp2(right, rVal);
 237                         EncodingValue *rev = map.get(&nvp2);
 238                         if (lev != rev) {
 239                                 if (lev->inComparison && rev->inComparison) {
 240                                         //Need to assign during comparison stage...
 241                                         //Thus promote to comparison
 242                                         if (lVal < rVal) {
 243                                                 orderEV(lev, rev);
 244                                         } else {
 245                                                 orderEV(rev, lev);
 246                                         }
 247                                 } else {
 248                                         lev->notequals.add(rev);
 249                                         rev->notequals.add(lev);
 250                                 }
 251                         }
 252                 }
 253         }
 254 }
 255
 256 void EncodingSubGraph::generateComparison(EncodingNode *left, EncodingNode *right) {
 257         Set *lset=left->s;
 258         Set *rset=right->s;
 259         uint lindex=0, rindex=0;
 260         uint lSize=lset->getSize(), rSize=rset->getSize();
 261         uint64_t lVal=lset->getElement(lindex);
 262         NodeValuePair nvp1(left, lVal);
 263         EncodingValue *lev = map.get(&nvp1);
 264         lev->inComparison = true;
 265         uint64_t rVal=rset->getElement(rindex);
 266         NodeValuePair nvp2(right, rVal);
 267         EncodingValue *rev = map.get(&nvp2);
 268         rev->inComparison = true;
 269         EncodingValue *last = NULL;
 270
 271         while(lindex < lSize || rindex < rSize) {
 272                 if (last != NULL) {
 273                         if (lev != NULL)
 274                                 orderEV(last, lev);
 275                         if (rev != NULL && lev != rev)
 276                                 orderEV(last, rev);
 277                 }
 278                 if (lev != rev) {
 279                         if (rev == NULL || lVal < rVal) {
 280                                 if (rev != NULL)
 281                                         orderEV(lev, rev);
 282                                 last = lev;
 283                                 if (++lindex < lSize) {
 284                                         lVal=lset->getElement(lindex);
 285                                         NodeValuePair nvpl(left, lVal);
 286                                         lev = map.get(&nvpl);
 287                                         lev->inComparison = true;
 288                                 } else
 289                                         lev = NULL;
 290                         } else {
 291                                 if (lev != NULL)
 292                                         orderEV(rev, lev);
 293                                 last = rev;
 294                                 if (++rindex < rSize) {
 295                                         rVal=rset->getElement(rindex);
 296                                         NodeValuePair nvpr(right, rVal);
 297                                         rev = map.get(&nvpr);
 298                                         rev->inComparison = true;
 299                                 } else
 300                                         rev = NULL;
 301                         }
 302                 } else {
 303                         last = lev;
 304                         if (++lindex < lSize) {
 305                                 lVal=lset->getElement(lindex);
 306                                 NodeValuePair nvpl(left, lVal);
 307                                 lev = map.get(&nvpl);
 308                                 lev->inComparison = true;
 309                         } else
 310                                 lev = NULL;
 311
 312                         if (++rindex < rSize) {
 313                                 rVal=rset->getElement(rindex);
 314                                 NodeValuePair nvpr(right, rVal);
 315                                 rev = map.get(&nvpr);
 316                                 rev->inComparison = true;
 317                         } else
 318                                 rev = NULL;
 319                 }
 320         }
 321 }
 322
 323 void EncodingSubGraph::computeEncodingValue() {
 324         SetIteratorEncodingNode *nodeit=nodes.iterator();
 325         while(nodeit->hasNext()) {
 326                 EncodingNode *node=nodeit->next();
 327                 Set * set = node->s;
 328                 uint setSize = set->getSize();
 329                 for(uint i=0; i<setSize; i++) {
 330                         uint64_t val = set->getElement(i);
 331                         NodeValuePair nvp(node, val);
 332                         if (!map.contains(&nvp)) {
 333                                 traverseValue(node, val);
 334                         }
 335                 }
 336         }
 337         delete nodeit;
 338 }
 339
 340 void EncodingSubGraph::traverseValue(EncodingNode *node, uint64_t value) {
 341         EncodingValue *ecv=new EncodingValue(value);
 342         values.add(ecv);
 343         HashsetEncodingNode discovered;
 344         Vector<EncodingNode *> tovisit;
 345         tovisit.push(node);
 346         discovered.add(node);
 347         while(tovisit.getSize()!=0) {
 348                 EncodingNode *n=tovisit.last();tovisit.pop();
 349                 //Add encoding node to structures
 350                 ecv->nodes.add(n);
 351                 NodeValuePair *nvp=new NodeValuePair(n, value);
 352                 map.put(nvp, ecv);
 353                 SetIteratorEncodingEdge *edgeit=node->edges.iterator();
 354                 while(edgeit->hasNext()) {
 355                         EncodingEdge *ee=edgeit->next();
 356                         if (!discovered.contains(ee->left) && nodes.contains(ee->left) && ee->left->s->exists(value)) {
 357                                 tovisit.push(ee->left);
 358                                 discovered.add(ee->left);
 359                         }
 360                         if (!discovered.contains(ee->right) && nodes.contains(ee->right) && ee->right->s->exists(value)) {
 361                                 tovisit.push(ee->right);
 362                                 discovered.add(ee->right);
 363                         }
 364                 }
 365                 delete edgeit;
 366         }
 367 }
 368