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