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