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