src/ASTAnalyses/Encoding/subgraph.cc

   1 #include "subgraph.h"
   2 #include "encodinggraph.h"
   3 #include "set.h"
   4
   5 EncodingSubGraph::EncodingSubGraph() :
   6         encodingSize(0),
   7         numElements(0) {
   8 }
   9
  10 uint hashNodeValuePair(NodeValuePair *nvp) {
  11         return (uint) (nvp->value ^ ((uintptr_t)nvp->node));
  12 }
  13
  14 bool equalsNodeValuePair(NodeValuePair *nvp1, NodeValuePair *nvp2) {
  15         return nvp1->value == nvp2->value && nvp1->node == nvp2->node;
  16 }
  17
  18 uint EncodingSubGraph::estimateNewSize(EncodingSubGraph *sg) {
  19         uint newSize=0;
  20         SetIteratorEncodingNode * nit = sg->nodes.iterator();
  21         while(nit->hasNext()) {
  22                 EncodingNode *en = nit->next();
  23                 uint size=estimateNewSize(en);
  24                 if (size > newSize)
  25                         newSize = size;
  26         }
  27         delete nit;
  28         return newSize;
  29 }
  30
  31 uint EncodingSubGraph::estimateNewSize(EncodingNode *n) {
  32         SetIteratorEncodingEdge * eeit = n->edges.iterator();
  33         uint newsize=n->getSize();
  34         while(eeit->hasNext()) {
  35                 EncodingEdge * ee = eeit->next();
  36                 if (ee->left != NULL && ee->left != n && nodes.contains(ee->left)) {
  37                         uint intersectSize = n->s->getUnionSize(ee->left->s);
  38                         if (intersectSize > newsize)
  39                                 newsize = intersectSize;
  40                 }
  41                 if (ee->right != NULL && ee->right != n && nodes.contains(ee->right)) {
  42                         uint intersectSize = n->s->getUnionSize(ee->right->s);
  43                         if (intersectSize > newsize)
  44                                 newsize = intersectSize;
  45                 }
  46                 if (ee->dst != NULL && ee->dst != n && nodes.contains(ee->dst)) {
  47                         uint intersectSize = n->s->getUnionSize(ee->dst->s);
  48                         if (intersectSize > newsize)
  49                                 newsize = intersectSize;
  50                 }
  51         }
  52         delete eeit;
  53         return newsize;
  54 }
  55
  56 void EncodingSubGraph::addNode(EncodingNode *n) {
  57         nodes.add(n);
  58         uint newSize=estimateNewSize(n);
  59         numElements += n->elements.getSize();
  60         if (newSize > encodingSize)
  61                 encodingSize=newSize;
  62 }
  63
  64 SetIteratorEncodingNode * EncodingSubGraph::nodeIterator() {
  65         return nodes.iterator();
  66 }
  67
  68 void EncodingSubGraph::encode() {
  69         computeEncodingValue();
  70         computeInequalities();
  71 }
  72
  73 void EncodingSubGraph::computeInequalities() {
  74         SetIteratorEncodingNode *nodeit=nodes.iterator();
  75         while(nodeit->hasNext()) {
  76                 EncodingNode *node=nodeit->next();
  77                 SetIteratorEncodingEdge *edgeit=node->edges.iterator();
  78                 while(edgeit->hasNext()) {
  79                         EncodingEdge *edge=edgeit->next();
  80                         if (edge->numComparisons == 0)
  81                                 continue;
  82                         if (edge->left == NULL || !nodes.contains(edge->left))
  83                                 continue;
  84                         if (edge->right == NULL || !nodes.contains(edge->right))
  85                                 continue;
  86                         //examine only once
  87                         if (edge->left != node)
  88                                 continue;
  89                         //We have a comparison edge between two nodes in the subgraph
  90                         generateComparison(edge->left, edge->right);
  91                 }
  92                 delete edgeit;
  93         }
  94         delete nodeit;
  95 }
  96
  97 void EncodingSubGraph::generateComparison(EncodingNode *left, EncodingNode *right) {
  98         Set *lset=left->s;
  99         Set *rset=right->s;
 100         uint lindex=0, rindex=0;
 101         uint lSize=lset->getSize(), rSize=rset->getSize();
 102         uint64_t lVal=lset->getElement(lindex);
 103         NodeValuePair nvp1(left, lVal);
 104         EncodingValue *lev = map.get(&nvp1);
 105         lev->inComparison = true;
 106         uint64_t rVal=rset->getElement(rindex);
 107         NodeValuePair nvp2(right, rVal);
 108         EncodingValue *rev = map.get(&nvp2);
 109         rev->inComparison = true;
 110         EncodingValue *last = NULL;
 111
 112         while(lindex < lSize || rindex < rSize) {
 113                 if (last != NULL) {
 114                         if (lev != NULL)
 115                                 last->larger.push(lev);
 116                         if (rev != NULL && lev != rev)
 117                                 last->larger.push(rev);
 118                 }
 119                 if (lev != rev) {
 120                         if (rev == NULL || lVal < rVal) {
 121                                 if (rev != NULL)
 122                                         lev->larger.push(rev);
 123                                 last = lev;
 124                                 if (++lindex < lSize) {
 125                                         lVal=lset->getElement(lindex);
 126                                         NodeValuePair nvpl(left, lVal);
 127                                         lev = map.get(&nvpl);
 128                                         lev->inComparison = true;
 129                                 } else
 130                                         lev = NULL;
 131                         } else {
 132                                 if (lev != NULL)
 133                                         rev->larger.push(lev);
 134                                 last = rev;
 135                                 if (++rindex < rSize) {
 136                                         rVal=rset->getElement(rindex);
 137                                         NodeValuePair nvpr(right, rVal);
 138                                         rev = map.get(&nvpr);
 139                                         rev->inComparison = true;
 140                                 } else
 141                                         rev = NULL;
 142                         }
 143                 } else {
 144                         last = lev;
 145                         if (++lindex < lSize) {
 146                                 lVal=lset->getElement(lindex);
 147                                 NodeValuePair nvpl(left, lVal);
 148                                 lev = map.get(&nvpl);
 149                                 lev->inComparison = true;
 150                         } else
 151                                 lev = NULL;
 152
 153                         if (++rindex < rSize) {
 154                                 rVal=rset->getElement(rindex);
 155                                 NodeValuePair nvpr(right, rVal);
 156                                 rev = map.get(&nvpr);
 157                                 rev->inComparison = true;
 158                         } else
 159                                 rev = NULL;
 160                 }
 161         }
 162 }
 163
 164 void EncodingSubGraph::computeEncodingValue() {
 165         SetIteratorEncodingNode *nodeit=nodes.iterator();
 166         while(nodeit->hasNext()) {
 167                 EncodingNode *node=nodeit->next();
 168                 Set * set = node->s;
 169                 uint setSize = set->getSize();
 170                 for(uint i=0; i<setSize; i++) {
 171                         uint64_t val = set->getElement(i);
 172                         NodeValuePair nvp(node, val);
 173                         if (!map.contains(&nvp)) {
 174                                 traverseValue(node, val);
 175                         }
 176                 }
 177         }
 178         delete nodeit;
 179 }
 180
 181 void EncodingSubGraph::traverseValue(EncodingNode *node, uint64_t value) {
 182         EncodingValue *ecv=new EncodingValue(value);
 183         HashsetEncodingNode discovered;
 184         Vector<EncodingNode *> tovisit;
 185         tovisit.push(node);
 186         discovered.add(node);
 187         while(tovisit.getSize()!=0) {
 188                 EncodingNode *n=tovisit.last();tovisit.pop();
 189                 //Add encoding node to structures
 190                 ecv->nodes.add(n);
 191                 NodeValuePair *nvp=new NodeValuePair(n, value);
 192                 map.put(nvp, ecv);
 193                 SetIteratorEncodingEdge *edgeit=node->edges.iterator();
 194                 while(edgeit->hasNext()) {
 195                         EncodingEdge *ee=edgeit->next();
 196                         if (!discovered.contains(ee->left) && nodes.contains(ee->left) && ee->left->s->exists(value)) {
 197                                 tovisit.push(ee->left);
 198                                 discovered.add(ee->left);
 199                         }
 200                         if (!discovered.contains(ee->right) && nodes.contains(ee->right) && ee->right->s->exists(value)) {
 201                                 tovisit.push(ee->right);
 202                                 discovered.add(ee->right);
 203                         }
 204                 }
 205                 delete edgeit;
 206         }
 207 }
 208