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
   8 EncodingGraph::EncodingGraph(CSolver * _solver) :
   9         solver(_solver) {
  10
  11
  12 }
  13
  14 void EncodingGraph::buildGraph() {
  15         ElementIterator it(solver);
  16         while(it.hasNext()) {
  17                 Element * e = it.next();
  18                 switch(e->type) {
  19                 case ELEMSET:
  20                 case ELEMFUNCRETURN:
  21                         processElement(e);
  22                         break;
  23                 case ELEMCONST:
  24                         break;
  25                 default:
  26                         ASSERT(0);
  27                 }
  28         }
  29 }
  30
  31 void EncodingGraph::processElement(Element *e) {
  32         uint size=e->parents.getSize();
  33         for(uint i=0;i<size;i++) {
  34                 ASTNode * n = e->parents.get(i);
  35                 switch(n->type) {
  36                 case PREDICATEOP:
  37                         processPredicate((BooleanPredicate *)n);
  38                         break;
  39                 case ELEMFUNCRETURN:
  40                         processFunction((ElementFunction *)n);
  41                         break;
  42                 default:
  43                         ASSERT(0);
  44                 }
  45         }
  46 }
  47
  48 void EncodingGraph::processFunction(ElementFunction *ef) {
  49         Function *f=ef->getFunction();
  50         if (f->type==OPERATORFUNC) {
  51                 FunctionOperator *fo=(FunctionOperator*)f;
  52                 ASSERT(ef->inputs.getSize() == 2);
  53                 EncodingNode *left=createNode(ef->inputs.get(0));
  54                 EncodingNode *right=createNode(ef->inputs.get(1));
  55                 if (left == NULL && right == NULL)
  56                         return;
  57                 EncodingNode *dst=createNode(ef);
  58                 EncodingEdge *edge=getEdge(left, right, dst);
  59                 edge->numArithOps++;
  60         }
  61 }
  62
  63 void EncodingGraph::processPredicate(BooleanPredicate *b) {
  64         Predicate *p=b->getPredicate();
  65         if (p->type==OPERATORPRED) {
  66                 PredicateOperator *po=(PredicateOperator *)p;
  67                 ASSERT(b->inputs.getSize()==2);
  68                 EncodingNode *left=createNode(b->inputs.get(0));
  69                 EncodingNode *right=createNode(b->inputs.get(1));
  70                 if (left == NULL || right == NULL)
  71                         return;
  72                 EncodingEdge *edge=getEdge(left, right, NULL);
  73                 CompOp op=po->getOp();
  74                 switch(op) {
  75                 case SATC_EQUALS:
  76                         edge->numEquals++;
  77                         break;
  78                 case SATC_LT:
  79                 case SATC_LTE:
  80                 case SATC_GT:
  81                 case SATC_GTE:
  82                         edge->numComparisons++;
  83                         break;
  84                 default:
  85                         ASSERT(0);
  86                 }
  87         }
  88 }
  89
  90 EncodingEdge * EncodingGraph::getEdge(EncodingNode *left, EncodingNode *right, EncodingNode *dst) {
  91         EncodingEdge e(left, right, dst);
  92         EncodingEdge *result = edgeMap.get(&e);
  93         if (result == NULL) {
  94                 result=new EncodingEdge(left, right, dst);
  95                 edgeMap.put(result, result);
  96         }
  97         return result;
  98 }
  99
 100 EncodingNode::EncodingNode(Set *_s) :
 101         s(_s),
 102         numElements(0) {
 103 }
 104
 105 uint EncodingNode::getSize() {
 106         return s->getSize();
 107 }
 108
 109 EncodingNode * EncodingGraph::createNode(Element *e) {
 110         if (e->type == ELEMCONST)
 111                 return NULL;
 112         Set *s = e->getRange();
 113         EncodingNode *n = encodingMap.get(s);
 114         if (n == NULL) {
 115                 n = new EncodingNode(s);
 116                 encodingMap.put(s, n);
 117         }
 118         n->addElement(e);
 119         if (discovered.add(e))
 120                 n->numElements++;
 121         return n;
 122 }
 123
 124 void EncodingNode::addElement(Element *e) {
 125         elements.add(e);
 126 }
 127
 128 EncodingEdge::EncodingEdge(EncodingNode *_l, EncodingNode *_r) :
 129         left(_l),
 130         right(_r),
 131         dst(NULL),
 132         numArithOps(0),
 133         numEquals(0),
 134         numComparisons(0)
 135 {
 136 }
 137
 138 EncodingEdge::EncodingEdge(EncodingNode *_left, EncodingNode *_right, EncodingNode *_dst) :
 139         left(_left),
 140         right(_right),
 141         dst(_dst),
 142         numArithOps(0),
 143         numEquals(0),
 144         numComparisons(0)
 145 {
 146 }
 147
 148 uint hashEncodingEdge(EncodingEdge *edge) {
 149         uintptr_t hash=(((uintptr_t) edge->left) >> 2) ^ (((uintptr_t)edge->right) >> 4) ^ (((uintptr_t)edge->dst) >> 6);
 150         return (uint) hash;
 151 }
 152
 153 bool equalsEncodingEdge(EncodingEdge *e1, EncodingEdge *e2) {
 154         return e1->left == e2->left && e1->right == e2->right && e1->dst == e2->dst;
 155 }