src/ASTAnalyses/Encoding/encodinggraph.cc

   1 #include "encodinggraph.h"
   2 #include "iterator.h"
   3 #include "element.h"
   4 #include "function.h"
   5 #include "predicate.h"
   6 #include "set.h"
   7 #include "csolver.h"
   8 #include "tunable.h"
   9
  10 EncodingGraph::EncodingGraph(CSolver * _solver) :
  11         solver(_solver) {
  12
  13
  14 }
  15
  16 void EncodingGraph::buildGraph() {
  17         ElementIterator it(solver);
  18         while(it.hasNext()) {
  19                 Element * e = it.next();
  20                 switch(e->type) {
  21                 case ELEMSET:
  22                 case ELEMFUNCRETURN:
  23                         processElement(e);
  24                         break;
  25                 case ELEMCONST:
  26                         break;
  27                 default:
  28                         ASSERT(0);
  29                 }
  30         }
  31 }
  32
  33 void EncodingGraph::mergeNodes(EncodingNode *first, EncodingNode *second) {
  34         EncodingSubGraph *graph1=graphMap.get(first);
  35         EncodingSubGraph *graph2=graphMap.get(second);
  36         if (graph1 == NULL && graph2 == NULL) {
  37                 graph1 = new EncodingSubGraph();
  38                 graphMap.put(first, graph1);
  39                 graph1->addNode(first);
  40         }
  41         if (graph1 == NULL && graph2 != NULL) {
  42                 graph1 = graph2;
  43                 graph2 = NULL;
  44                 EncodingNode *tmp = second;
  45                 second = first;
  46                 first = tmp;
  47         }
  48         if (graph1 != NULL && graph2 != NULL) {
  49                 SetIteratorEncodingNode * nodeit=graph2->nodeIterator();
  50                 while(nodeit->hasNext()) {
  51                         EncodingNode *node=nodeit->next();
  52                         graph1->addNode(node);
  53                         graphMap.put(node, graph1);
  54                 }
  55                 delete nodeit;
  56                 delete graph2;
  57         } else {
  58                 ASSERT(graph1 != NULL && graph2 == NULL);
  59                 graph1->addNode(second);
  60                 graphMap.put(second, graph1);
  61         }
  62 }
  63
  64 void EncodingGraph::processElement(Element *e) {
  65         uint size=e->parents.getSize();
  66         for(uint i=0;i<size;i++) {
  67                 ASTNode * n = e->parents.get(i);
  68                 switch(n->type) {
  69                 case PREDICATEOP:
  70                         processPredicate((BooleanPredicate *)n);
  71                         break;
  72                 case ELEMFUNCRETURN:
  73                         processFunction((ElementFunction *)n);
  74                         break;
  75                 default:
  76                         ASSERT(0);
  77                 }
  78         }
  79 }
  80
  81 void EncodingGraph::processFunction(ElementFunction *ef) {
  82         Function *f=ef->getFunction();
  83         if (f->type==OPERATORFUNC) {
  84                 FunctionOperator *fo=(FunctionOperator*)f;
  85                 ASSERT(ef->inputs.getSize() == 2);
  86                 EncodingNode *left=createNode(ef->inputs.get(0));
  87                 EncodingNode *right=createNode(ef->inputs.get(1));
  88                 if (left == NULL && right == NULL)
  89                         return;
  90                 EncodingNode *dst=createNode(ef);
  91                 EncodingEdge *edge=getEdge(left, right, dst);
  92                 edge->numArithOps++;
  93         }
  94 }
  95
  96 void EncodingGraph::processPredicate(BooleanPredicate *b) {
  97         Predicate *p=b->getPredicate();
  98         if (p->type==OPERATORPRED) {
  99                 PredicateOperator *po=(PredicateOperator *)p;
 100                 ASSERT(b->inputs.getSize()==2);
 101                 EncodingNode *left=createNode(b->inputs.get(0));
 102                 EncodingNode *right=createNode(b->inputs.get(1));
 103                 if (left == NULL || right == NULL)
 104                         return;
 105                 EncodingEdge *edge=getEdge(left, right, NULL);
 106                 CompOp op=po->getOp();
 107                 switch(op) {
 108                 case SATC_EQUALS:
 109                         edge->numEquals++;
 110                         break;
 111                 case SATC_LT:
 112                 case SATC_LTE:
 113                 case SATC_GT:
 114                 case SATC_GTE:
 115                         edge->numComparisons++;
 116                         break;
 117                 default:
 118                         ASSERT(0);
 119                 }
 120         }
 121 }
 122
 123 static TunableDesc EdgeEncodingDesc(EDGE_UNASSIGNED, EDGE_MATCH, EDGE_UNASSIGNED);
 124
 125 EncodingEdge * EncodingGraph::getEdge(EncodingNode *left, EncodingNode *right, EncodingNode *dst) {
 126         EncodingEdge e(left, right, dst);
 127         EncodingEdge *result = edgeMap.get(&e);
 128         if (result == NULL) {
 129                 result=new EncodingEdge(left, right, dst);
 130                 VarType v1=left->getType();
 131                 VarType v2=right->getType();
 132                 if (v1 > v2) {
 133                         VarType tmp=v2;
 134                         v2=v1;
 135                         v1=tmp;
 136                 }
 137                 result->setEncoding((EdgeEncodingType)solver->getTuner()->getVarTunable(v1, v2, EDGEENCODING, &EdgeEncodingDesc));
 138                 edgeMap.put(result, result);
 139         }
 140         return result;
 141 }
 142
 143 EncodingNode::EncodingNode(Set *_s) :
 144         s(_s),
 145         numElements(0) {
 146 }
 147
 148 uint EncodingNode::getSize() {
 149         return s->getSize();
 150 }
 151
 152 VarType EncodingNode::getType() {
 153         return s->getType();
 154 }
 155
 156 static TunableDesc NodeEncodingDesc(ELEM_UNASSIGNED, BINARYINDEX, ELEM_UNASSIGNED);
 157
 158 EncodingNode * EncodingGraph::createNode(Element *e) {
 159         if (e->type == ELEMCONST)
 160                 return NULL;
 161         Set *s = e->getRange();
 162         EncodingNode *n = encodingMap.get(s);
 163         if (n == NULL) {
 164                 n = new EncodingNode(s);
 165                 n->setEncoding((ElementEncodingType)solver->getTuner()->getVarTunable(n->getType(), NODEENCODING, &NodeEncodingDesc));
 166                 encodingMap.put(s, n);
 167         }
 168         n->addElement(e);
 169         if (discovered.add(e))
 170                 n->numElements++;
 171         return n;
 172 }
 173
 174 void EncodingNode::addElement(Element *e) {
 175         elements.add(e);
 176 }
 177
 178 EncodingEdge::EncodingEdge(EncodingNode *_l, EncodingNode *_r) :
 179         left(_l),
 180         right(_r),
 181         dst(NULL),
 182         encoding(EDGE_UNASSIGNED),
 183         numArithOps(0),
 184         numEquals(0),
 185         numComparisons(0)
 186 {
 187 }
 188
 189 EncodingEdge::EncodingEdge(EncodingNode *_left, EncodingNode *_right, EncodingNode *_dst) :
 190         left(_left),
 191         right(_right),
 192         dst(_dst),
 193         encoding(EDGE_UNASSIGNED),
 194         numArithOps(0),
 195         numEquals(0),
 196         numComparisons(0)
 197 {
 198 }
 199
 200 uint hashEncodingEdge(EncodingEdge *edge) {
 201         uintptr_t hash=(((uintptr_t) edge->left) >> 2) ^ (((uintptr_t)edge->right) >> 4) ^ (((uintptr_t)edge->dst) >> 6);
 202         return (uint) hash;
 203 }
 204
 205 bool equalsEncodingEdge(EncodingEdge *e1, EncodingEdge *e2) {
 206         return e1->left == e2->left && e1->right == e2->right && e1->dst == e2->dst;
 207 }
 208
 209 EncodingSubGraph::EncodingSubGraph() {
 210 }
 211
 212 void EncodingSubGraph::addNode(EncodingNode *n) {
 213         nodes.add(n);
 214         Set *s=n->s;
 215         uint size=s->getSize();
 216         for(uint i=0; i<size; i++) {
 217                 uint64_t val=s->getElement(i);
 218                 values.add(val);
 219         }
 220 }
 221
 222 SetIteratorEncodingNode * EncodingSubGraph::nodeIterator() {
 223         return nodes.iterator();
 224 }