1 #include "encodinggraph.h"
11 #include "elementencoding.h"
13 EncodingGraph::EncodingGraph(CSolver * _solver) :
17 int sortEncodingEdge(const void * p1, const void *p2) {
18 const EncodingEdge * e1 = * (const EncodingEdge **) p1;
19 const EncodingEdge * e2 = * (const EncodingEdge **) p2;
20 uint64_t v1 = e1->getValue();
21 uint64_t v2 = e2->getValue();
30 void EncodingGraph::buildGraph() {
31 ElementIterator it(solver);
33 Element * e = it.next();
45 bsdqsort(edgeVector.expose(), edgeVector.getSize(), sizeof(EncodingEdge *), sortEncodingEdge);
49 void EncodingGraph::encode() {
50 SetIteratorEncodingSubGraph * itesg=subgraphs.iterator();
51 while(itesg->hasNext()) {
52 EncodingSubGraph *sg=itesg->next();
57 ElementIterator it(solver);
59 Element * e = it.next();
62 case ELEMFUNCRETURN: {
63 ElementEncoding *encoding=getElementEncoding(e);
64 if (encoding->getElementEncodingType() == ELEM_UNASSIGNED) {
65 EncodingNode *n = getNode(e);
67 ElementEncodingType encodetype=n->getEncoding();
68 encoding->setElementEncodingType(encodetype);
69 if (encodetype == UNARY || encodetype == ONEHOT) {
70 encoding->encodingArrayInitialization();
71 } else if (encodetype == BINARYINDEX) {
72 EncodingSubGraph * subgraph = graphMap.get(n);
73 uint encodingSize = subgraph->getEncodingSize(n);
74 uint paddedSize = encoding->getSizeEncodingArray(encodingSize);
75 encoding->allocInUseArrayElement(paddedSize);
76 encoding->allocEncodingArrayElement(paddedSize);
77 Set * s=e->getRange();
78 for(uint i=0;i<s->getSize();i++) {
79 uint64_t value=s->getElement(i);
80 uint encodingIndex=subgraph->getEncoding(n, value);
81 encoding->setInUseElement(encodingIndex);
82 encoding->encodingArray[encodingIndex] = value;
95 void EncodingGraph::mergeNodes(EncodingNode *first, EncodingNode *second) {
96 EncodingSubGraph *graph1=graphMap.get(first);
97 EncodingSubGraph *graph2=graphMap.get(second);
98 if (graph1 == NULL && graph2 == NULL) {
99 graph1 = new EncodingSubGraph();
100 subgraphs.add(graph1);
101 graphMap.put(first, graph1);
102 graph1->addNode(first);
104 if (graph1 == NULL && graph2 != NULL) {
107 EncodingNode *tmp = second;
111 if (graph1 != NULL && graph2 != NULL) {
112 SetIteratorEncodingNode * nodeit=graph2->nodeIterator();
113 while(nodeit->hasNext()) {
114 EncodingNode *node=nodeit->next();
115 graph1->addNode(node);
116 graphMap.put(node, graph1);
118 subgraphs.remove(graph2);
122 ASSERT(graph1 != NULL && graph2 == NULL);
123 graph1->addNode(second);
124 graphMap.put(second, graph1);
128 void EncodingGraph::processElement(Element *e) {
129 uint size=e->parents.getSize();
130 for(uint i=0;i<size;i++) {
131 ASTNode * n = e->parents.get(i);
134 processPredicate((BooleanPredicate *)n);
137 processFunction((ElementFunction *)n);
145 void EncodingGraph::processFunction(ElementFunction *ef) {
146 Function *f=ef->getFunction();
147 if (f->type==OPERATORFUNC) {
148 FunctionOperator *fo=(FunctionOperator*)f;
149 ASSERT(ef->inputs.getSize() == 2);
150 EncodingNode *left=createNode(ef->inputs.get(0));
151 EncodingNode *right=createNode(ef->inputs.get(1));
152 if (left == NULL && right == NULL)
154 EncodingNode *dst=createNode(ef);
155 EncodingEdge *edge=getEdge(left, right, dst);
160 void EncodingGraph::processPredicate(BooleanPredicate *b) {
161 Predicate *p=b->getPredicate();
162 if (p->type==OPERATORPRED) {
163 PredicateOperator *po=(PredicateOperator *)p;
164 ASSERT(b->inputs.getSize()==2);
165 EncodingNode *left=createNode(b->inputs.get(0));
166 EncodingNode *right=createNode(b->inputs.get(1));
167 if (left == NULL || right == NULL)
169 EncodingEdge *edge=getEdge(left, right, NULL);
170 CompOp op=po->getOp();
179 edge->numComparisons++;
187 uint convertSize(uint cost) {
188 cost = 1.2 * cost; // fudge factor
189 return NEXTPOW2(cost);
192 void EncodingGraph::decideEdges() {
193 uint size=edgeVector.getSize();
194 for(uint i=0; i<size; i++) {
195 EncodingEdge *ee = edgeVector.get(i);
196 EncodingNode *left = ee->left;
197 EncodingNode *right = ee->right;
199 if (ee->encoding != EDGE_UNASSIGNED ||
200 left->encoding != BINARYINDEX ||
201 right->encoding != BINARYINDEX)
204 uint64_t eeValue = ee->getValue();
208 EncodingSubGraph *leftGraph = graphMap.get(left);
209 EncodingSubGraph *rightGraph = graphMap.get(right);
210 if (leftGraph == NULL && rightGraph !=NULL) {
211 EncodingNode *tmp = left; left=right; right=tmp;
212 EncodingSubGraph *tmpsg = leftGraph; leftGraph = rightGraph; rightGraph = tmpsg;
215 uint leftSize=0, rightSize=0, newSize=0;
216 uint64_t totalCost=0;
217 if (leftGraph == NULL && rightGraph == NULL) {
218 leftSize=convertSize(left->getSize());
219 rightSize=convertSize(right->getSize());
220 newSize=convertSize(left->s->getUnionSize(right->s));
221 newSize=(leftSize > newSize) ? leftSize: newSize;
222 newSize=(rightSize > newSize) ? rightSize: newSize;
223 totalCost = (newSize - leftSize) * left->elements.getSize() +
224 (newSize - rightSize) * right->elements.getSize();
225 } else if (leftGraph != NULL && rightGraph == NULL) {
226 leftSize=convertSize(leftGraph->encodingSize);
227 rightSize=convertSize(right->getSize());
228 newSize=convertSize(leftGraph->estimateNewSize(right));
229 newSize=(leftSize > newSize) ? leftSize: newSize;
230 newSize=(rightSize > newSize) ? rightSize: newSize;
231 totalCost = (newSize - leftSize) * leftGraph->numElements +
232 (newSize - rightSize) * right->elements.getSize();
235 leftSize=convertSize(leftGraph->encodingSize);
236 rightSize=convertSize(rightGraph->encodingSize);
237 newSize=convertSize(leftGraph->estimateNewSize(rightGraph));
238 newSize=(leftSize > newSize) ? leftSize: newSize;
239 newSize=(rightSize > newSize) ? rightSize: newSize;
240 totalCost = (newSize - leftSize) * leftGraph->numElements +
241 (newSize - rightSize) * rightGraph->numElements;
243 double conversionfactor = 0.5;
244 if ((totalCost * conversionfactor) < eeValue) {
246 mergeNodes(left, right);
251 static TunableDesc EdgeEncodingDesc(EDGE_UNASSIGNED, EDGE_MATCH, EDGE_UNASSIGNED);
253 EncodingEdge * EncodingGraph::getEdge(EncodingNode *left, EncodingNode *right, EncodingNode *dst) {
254 EncodingEdge e(left, right, dst);
255 EncodingEdge *result = edgeMap.get(&e);
256 if (result == NULL) {
257 result=new EncodingEdge(left, right, dst);
258 VarType v1=left->getType();
259 VarType v2=right->getType();
266 if ((left != NULL && left->encoding==BINARYINDEX) &&
267 (right != NULL) && right->encoding==BINARYINDEX) {
268 EdgeEncodingType type=(EdgeEncodingType)solver->getTuner()->getVarTunable(v1, v2, EDGEENCODING, &EdgeEncodingDesc);
269 result->setEncoding(type);
270 if (type == EDGE_MATCH) {
271 mergeNodes(left, right);
274 edgeMap.put(result, result);
275 edgeVector.push(result);
277 left->edges.add(result);
279 right->edges.add(result);
281 dst->edges.add(result);
286 EncodingNode::EncodingNode(Set *_s) :
290 uint EncodingNode::getSize() const {
294 VarType EncodingNode::getType() const {
298 static TunableDesc NodeEncodingDesc(ELEM_UNASSIGNED, BINARYINDEX, ELEM_UNASSIGNED);
300 EncodingNode * EncodingGraph::createNode(Element *e) {
301 if (e->type == ELEMCONST)
303 Set *s = e->getRange();
304 EncodingNode *n = encodingMap.get(s);
306 n = new EncodingNode(s);
307 n->setEncoding((ElementEncodingType)solver->getTuner()->getVarTunable(n->getType(), NODEENCODING, &NodeEncodingDesc));
308 encodingMap.put(s, n);
314 EncodingNode * EncodingGraph::getNode(Element *e) {
315 if (e->type == ELEMCONST)
317 Set *s = e->getRange();
318 EncodingNode *n = encodingMap.get(s);
322 void EncodingNode::addElement(Element *e) {
326 EncodingEdge::EncodingEdge(EncodingNode *_l, EncodingNode *_r) :
330 encoding(EDGE_UNASSIGNED),
337 EncodingEdge::EncodingEdge(EncodingNode *_left, EncodingNode *_right, EncodingNode *_dst) :
341 encoding(EDGE_UNASSIGNED),
348 uint hashEncodingEdge(EncodingEdge *edge) {
349 uintptr_t hash=(((uintptr_t) edge->left) >> 2) ^ (((uintptr_t)edge->right) >> 4) ^ (((uintptr_t)edge->dst) >> 6);
353 bool equalsEncodingEdge(EncodingEdge *e1, EncodingEdge *e2) {
354 return e1->left == e2->left && e1->right == e2->right && e1->dst == e2->dst;
357 uint64_t EncodingEdge::getValue() const {
358 uint lSize = (left != NULL) ? left->getSize() : 1;
359 uint rSize = (right != NULL) ? right->getSize() : 1;
360 uint min = (lSize < rSize) ? lSize : rSize;
361 return numEquals * min + numComparisons * lSize * rSize;