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