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::processElement(Element *e) {
  34         uint size=e->parents.getSize();
  35         for(uint i=0;i<size;i++) {
  36                 ASTNode * n = e->parents.get(i);
  37                 switch(n->type) {
  38                 case PREDICATEOP:
  39                         processPredicate((BooleanPredicate *)n);
  40                         break;
  41                 case ELEMFUNCRETURN:
  42                         processFunction((ElementFunction *)n);
  43                         break;
  44                 default:
  45                         ASSERT(0);
  46                 }
  47         }
  48 }
  49
  50 void EncodingGraph::processFunction(ElementFunction *ef) {
  51         Function *f=ef->getFunction();
  52         if (f->type==OPERATORFUNC) {
  53                 FunctionOperator *fo=(FunctionOperator*)f;
  54                 ASSERT(ef->inputs.getSize() == 2);
  55                 EncodingNode *left=createNode(ef->inputs.get(0));
  56                 EncodingNode *right=createNode(ef->inputs.get(1));
  57                 if (left == NULL && right == NULL)
  58                         return;
  59                 EncodingNode *dst=createNode(ef);
  60                 EncodingEdge *edge=getEdge(left, right, dst);
  61                 edge->numArithOps++;
  62         }
  63 }
  64
  65 void EncodingGraph::processPredicate(BooleanPredicate *b) {
  66         Predicate *p=b->getPredicate();
  67         if (p->type==OPERATORPRED) {
  68                 PredicateOperator *po=(PredicateOperator *)p;
  69                 ASSERT(b->inputs.getSize()==2);
  70                 EncodingNode *left=createNode(b->inputs.get(0));
  71                 EncodingNode *right=createNode(b->inputs.get(1));
  72                 if (left == NULL || right == NULL)
  73                         return;
  74                 EncodingEdge *edge=getEdge(left, right, NULL);
  75                 CompOp op=po->getOp();
  76                 switch(op) {
  77                 case SATC_EQUALS:
  78                         edge->numEquals++;
  79                         break;
  80                 case SATC_LT:
  81                 case SATC_LTE:
  82                 case SATC_GT:
  83                 case SATC_GTE:
  84                         edge->numComparisons++;
  85                         break;
  86                 default:
  87                         ASSERT(0);
  88                 }
  89         }
  90 }
  91
  92 EncodingEdge * EncodingGraph::getEdge(EncodingNode *left, EncodingNode *right, EncodingNode *dst) {
  93         EncodingEdge e(left, right, dst);
  94         EncodingEdge *result = edgeMap.get(&e);
  95         if (result == NULL) {
  96                 result=new EncodingEdge(left, right, dst);
  97                 edgeMap.put(result, result);
  98         }
  99         return result;
 100 }
 101
 102 EncodingNode::EncodingNode(Set *_s) :
 103         s(_s),
 104         numElements(0) {
 105 }
 106
 107 uint EncodingNode::getSize() {
 108         return s->getSize();
 109 }
 110
 111 VarType EncodingNode::getType() {
 112         return s->getType();
 113 }
 114
 115 //ELEM_UNASSIGNED, ONEHOT, UNARY, BINARYINDEX, ONEHOTBINARY, BINARYVAL
 116
 117 static TunableDesc NodeEncodingType(ELEM_UNASSIGNED, BINARYVAL, ELEM_UNASSIGNED);
 118
 119 EncodingNode * EncodingGraph::createNode(Element *e) {
 120         if (e->type == ELEMCONST)
 121                 return NULL;
 122         Set *s = e->getRange();
 123         EncodingNode *n = encodingMap.get(s);
 124         if (n == NULL) {
 125                 n = new EncodingNode(s);
 126                 n->setEncoding((ElementEncodingType)solver->getTuner()->getVarTunable(n->getType(), NODEENCODING, &NodeEncodingType));
 127                 encodingMap.put(s, n);
 128         }
 129         n->addElement(e);
 130         if (discovered.add(e))
 131                 n->numElements++;
 132         return n;
 133 }
 134
 135 void EncodingNode::addElement(Element *e) {
 136         elements.add(e);
 137 }
 138
 139 EncodingEdge::EncodingEdge(EncodingNode *_l, EncodingNode *_r) :
 140         left(_l),
 141         right(_r),
 142         dst(NULL),
 143         numArithOps(0),
 144         numEquals(0),
 145         numComparisons(0)
 146 {
 147 }
 148
 149 EncodingEdge::EncodingEdge(EncodingNode *_left, EncodingNode *_right, EncodingNode *_dst) :
 150         left(_left),
 151         right(_right),
 152         dst(_dst),
 153         numArithOps(0),
 154         numEquals(0),
 155         numComparisons(0)
 156 {
 157 }
 158
 159 uint hashEncodingEdge(EncodingEdge *edge) {
 160         uintptr_t hash=(((uintptr_t) edge->left) >> 2) ^ (((uintptr_t)edge->right) >> 4) ^ (((uintptr_t)edge->dst) >> 6);
 161         return (uint) hash;
 162 }
 163
 164 bool equalsEncodingEdge(EncodingEdge *e1, EncodingEdge *e2) {
 165         return e1->left == e2->left && e1->right == e2->right && e1->dst == e2->dst;
 166 }