Merge branch 'encoding'
[satune.git] / 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 }