1 #include "encodinggraph.h"
11 #include "elementencoding.h"
13 EncodingGraph::EncodingGraph(CSolver *_solver) :
17 EncodingGraph::~EncodingGraph() {
18 subgraphs.resetAndDelete();
19 encodingMap.resetAndDeleteVals();
20 edgeMap.resetAndDeleteVals();
23 int sortEncodingEdge(const void *p1, const void *p2) {
24 const EncodingEdge *e1 = *(const EncodingEdge **) p1;
25 const EncodingEdge *e2 = *(const EncodingEdge **) p2;
26 uint64_t v1 = e1->getValue();
27 uint64_t v2 = e2->getValue();
36 void EncodingGraph::buildGraph() {
37 ElementIterator it(solver);
38 while (it.hasNext()) {
39 Element *e = it.next();
51 bsdqsort(edgeVector.expose(), edgeVector.getSize(), sizeof(EncodingEdge *), sortEncodingEdge);
56 void EncodingGraph::validate() {
57 SetIteratorBooleanEdge* it= solver->getConstraints();
59 BooleanEdge be = it->next();
60 if(be->type == PREDICATEOP){
61 BooleanPredicate *b = (BooleanPredicate *)be.getBoolean();
62 if(b->predicate->type == OPERATORPRED){
63 PredicateOperator* predicate = (PredicateOperator*) b->predicate;
64 if(predicate->getOp() == SATC_EQUALS){
65 ASSERT(b->inputs.getSize() == 2);
66 Element* e1= b->inputs.get(0);
67 Element* e2= b->inputs.get(1);
68 if(e1->type == ELEMCONST || e1->type == ELEMCONST)
70 ElementEncoding *enc1 = e1->getElementEncoding();
71 ElementEncoding *enc2 = e2->getElementEncoding();
72 ASSERT(enc1->getElementEncodingType() != ELEM_UNASSIGNED);
73 ASSERT(enc2->getElementEncodingType() != ELEM_UNASSIGNED);
74 if(enc1->getElementEncodingType() == enc2->getElementEncodingType() && enc1->getElementEncodingType() == BINARYINDEX && b->getFunctionEncoding()->type == CIRCUIT){
75 for(uint i=0; i<enc1->encArraySize; i++){
76 if(enc1->isinUseElement(i)){
77 uint64_t val1 = enc1->encodingArray[i];
78 if(enc2->isinUseElement(i)){
79 ASSERT(val1 == enc2->encodingArray[i]);
81 for(uint j=0; j< enc2->encArraySize; j++){
82 if(enc2->isinUseElement(j)){
83 ASSERT(val1 != enc2->encodingArray[j]);
90 //Now make sure that all the elements in the set are appeared in the encoding array!
91 for(uint k=0; k< b->inputs.getSize(); k++){
92 Element *e = b->inputs.get(k);
93 ElementEncoding *enc = e->getElementEncoding();
94 Set *s = e->getRange();
95 for (uint i = 0; i < s->getSize(); i++) {
96 uint64_t value = s->getElement(i);
98 for(uint j=0; j< enc->encArraySize; j++){
99 if(enc->isinUseElement(j) && enc->encodingArray[j] == value){
115 void EncodingGraph::encode() {
116 SetIteratorEncodingSubGraph *itesg = subgraphs.iterator();
117 while (itesg->hasNext()) {
118 EncodingSubGraph *sg = itesg->next();
123 ElementIterator it(solver);
124 while (it.hasNext()) {
125 Element *e = it.next();
128 case ELEMFUNCRETURN: {
129 ElementEncoding *encoding = e->getElementEncoding();
130 if (encoding->getElementEncodingType() == ELEM_UNASSIGNED) {
131 EncodingNode *n = getNode(e);
134 ElementEncodingType encodetype = n->getEncoding();
135 encoding->setElementEncodingType(encodetype);
136 if (encodetype == UNARY || encodetype == ONEHOT) {
137 encoding->encodingArrayInitialization();
138 } else if (encodetype == BINARYINDEX) {
139 EncodingSubGraph *subgraph = graphMap.get(n);
140 DEBUG("graphMap.get(subgraph=%p, n=%p)\n", subgraph, n);
141 if (subgraph == NULL) {
142 encoding->encodingArrayInitialization();
145 uint encodingSize = subgraph->getEncodingMaxVal(n) + 1;
146 uint paddedSize = encoding->getSizeEncodingArray(encodingSize);
147 encoding->allocInUseArrayElement(paddedSize);
148 encoding->allocEncodingArrayElement(paddedSize);
149 Set *s = e->getRange();
150 for (uint i = 0; i < s->getSize(); i++) {
151 uint64_t value = s->getElement(i);
152 uint encodingIndex = subgraph->getEncoding(n, value);
153 encoding->setInUseElement(encodingIndex);
154 ASSERT(encoding->isinUseElement(encodingIndex));
155 encoding->encodingArray[encodingIndex] = value;
168 void EncodingGraph::encodeParent(Element *e) {
169 uint size = e->parents.getSize();
170 for (uint i = 0; i < size; i++) {
171 ASTNode *n = e->parents.get(i);
172 if (n->type == PREDICATEOP) {
173 BooleanPredicate *b = (BooleanPredicate *)n;
174 FunctionEncoding *fenc = b->getFunctionEncoding();
175 if (fenc->getFunctionEncodingType() != FUNC_UNASSIGNED)
177 Predicate *p = b->getPredicate();
178 if (p->type == OPERATORPRED) {
179 PredicateOperator *po = (PredicateOperator *)p;
180 ASSERT(b->inputs.getSize() == 2);
181 EncodingNode *left = createNode(b->inputs.get(0));
182 EncodingNode *right = createNode(b->inputs.get(1));
183 if (left == NULL || right == NULL)
185 EncodingEdge *edge = getEdge(left, right, NULL);
186 if (edge != NULL && edge->getEncoding() == EDGE_MATCH) {
187 fenc->setFunctionEncodingType(CIRCUIT);
194 void EncodingGraph::mergeNodes(EncodingNode *first, EncodingNode *second) {
195 EncodingSubGraph *graph1 = graphMap.get(first);
196 DEBUG("graphMap.get(first=%p, graph1=%p)\n", first, graph1);
197 EncodingSubGraph *graph2 = graphMap.get(second);
198 DEBUG("graphMap.get(second=%p, graph2=%p)\n", second, graph2);
200 first->setEncoding(BINARYINDEX);
202 second->setEncoding(BINARYINDEX);
204 if (graph1 == NULL && graph2 == NULL) {
205 graph1 = new EncodingSubGraph();
206 subgraphs.add(graph1);
207 DEBUG("graphMap.put(first=%p, graph1=%p)\n", first, graph1);
208 graphMap.put(first, graph1);
209 graph1->addNode(first);
211 if (graph1 == NULL && graph2 != NULL) {
214 EncodingNode *tmp = second;
218 if (graph1 != NULL && graph2 != NULL) {
219 SetIteratorEncodingNode *nodeit = graph2->nodeIterator();
220 while (nodeit->hasNext()) {
221 EncodingNode *node = nodeit->next();
222 graph1->addNode(node);
223 DEBUG("graphMap.put(node=%p, graph1=%p)\n", node, graph1);
224 graphMap.put(node, graph1);
226 subgraphs.remove(graph2);
228 DEBUG("Deleting graph2 =%p \n", graph2);
231 ASSERT(graph1 != NULL && graph2 == NULL);
232 graph1->addNode(second);
233 DEBUG("graphMap.put(first=%p, graph1=%p)\n", first, graph1);
234 graphMap.put(second, graph1);
238 void EncodingGraph::processElement(Element *e) {
239 uint size = e->parents.getSize();
240 for (uint i = 0; i < size; i++) {
241 ASTNode *n = e->parents.get(i);
244 processPredicate((BooleanPredicate *)n);
247 processFunction((ElementFunction *)n);
255 void EncodingGraph::processFunction(ElementFunction *ef) {
256 Function *f = ef->getFunction();
257 if (f->type == OPERATORFUNC) {
258 FunctionOperator *fo = (FunctionOperator *)f;
259 ASSERT(ef->inputs.getSize() == 2);
260 EncodingNode *left = createNode(ef->inputs.get(0));
261 EncodingNode *right = createNode(ef->inputs.get(1));
262 if (left == NULL && right == NULL)
264 EncodingNode *dst = createNode(ef);
265 EncodingEdge *edge = createEdge(left, right, dst);
270 void EncodingGraph::processPredicate(BooleanPredicate *b) {
271 Predicate *p = b->getPredicate();
272 if (p->type == OPERATORPRED) {
273 PredicateOperator *po = (PredicateOperator *)p;
274 ASSERT(b->inputs.getSize() == 2);
275 EncodingNode *left = createNode(b->inputs.get(0));
276 EncodingNode *right = createNode(b->inputs.get(1));
277 if (left == NULL || right == NULL)
279 EncodingEdge *edge = createEdge(left, right, NULL);
280 CompOp op = po->getOp();
289 edge->numComparisons++;
297 uint convertSize(uint cost) {
298 cost = 1.2 * cost;// fudge factor
299 return NEXTPOW2(cost);
302 void EncodingGraph::decideEdges() {
303 uint size = edgeVector.getSize();
304 for (uint i = 0; i < size; i++) {
305 EncodingEdge *ee = edgeVector.get(i);
306 EncodingNode *left = ee->left;
307 EncodingNode *right = ee->right;
309 if (ee->encoding != EDGE_UNASSIGNED ||
310 !left->couldBeBinaryIndex() ||
311 !right->couldBeBinaryIndex())
314 uint64_t eeValue = ee->getValue();
318 EncodingSubGraph *leftGraph = graphMap.get(left);
319 DEBUG("graphMap.get(left=%p, leftgraph=%p)\n", left, leftGraph);
320 EncodingSubGraph *rightGraph = graphMap.get(right);
321 DEBUG("graphMap.get(right=%p, rightgraph=%p)\n", right, rightGraph);
322 if (leftGraph == NULL && rightGraph != NULL) {
323 EncodingNode *tmp = left; left = right; right = tmp;
324 EncodingSubGraph *tmpsg = leftGraph; leftGraph = rightGraph; rightGraph = tmpsg;
327 uint leftSize = 0, rightSize = 0, newSize = 0;
328 uint64_t totalCost = 0;
329 if (leftGraph == NULL && rightGraph == NULL) {
330 leftSize = convertSize(left->getSize());
331 rightSize = convertSize(right->getSize());
332 newSize = convertSize(left->s->getUnionSize(right->s));
333 newSize = (leftSize > newSize) ? leftSize : newSize;
334 newSize = (rightSize > newSize) ? rightSize : newSize;
335 totalCost = (newSize - leftSize) * left->elements.getSize() +
336 (newSize - rightSize) * right->elements.getSize();
337 } else if (leftGraph != NULL && rightGraph == NULL) {
338 leftSize = convertSize(leftGraph->encodingSize);
339 rightSize = convertSize(right->getSize());
340 newSize = convertSize(leftGraph->estimateNewSize(right));
341 newSize = (leftSize > newSize) ? leftSize : newSize;
342 newSize = (rightSize > newSize) ? rightSize : newSize;
343 totalCost = (newSize - leftSize) * leftGraph->numElements +
344 (newSize - rightSize) * right->elements.getSize();
348 //Are we already merged?
349 if (leftGraph == rightGraph)
352 leftSize = convertSize(leftGraph->encodingSize);
353 rightSize = convertSize(rightGraph->encodingSize);
354 newSize = convertSize(leftGraph->estimateNewSize(rightGraph));
355 newSize = (leftSize > newSize) ? leftSize : newSize;
356 newSize = (rightSize > newSize) ? rightSize : newSize;
357 totalCost = (newSize - leftSize) * leftGraph->numElements +
358 (newSize - rightSize) * rightGraph->numElements;
360 double conversionfactor = 0.5;
361 if ((totalCost * conversionfactor) < eeValue) {
363 mergeNodes(left, right);
368 static TunableDesc EdgeEncodingDesc(EDGE_UNASSIGNED, EDGE_MATCH, EDGE_UNASSIGNED);
370 EncodingEdge *EncodingGraph::getEdge(EncodingNode *left, EncodingNode *right, EncodingNode *dst) {
371 EncodingEdge e(left, right, dst);
372 EncodingEdge *result = edgeMap.get(&e);
376 EncodingEdge *EncodingGraph::createEdge(EncodingNode *left, EncodingNode *right, EncodingNode *dst) {
377 EncodingEdge e(left, right, dst);
378 EncodingEdge *result = edgeMap.get(&e);
379 if (result == NULL) {
380 result = new EncodingEdge(left, right, dst);
381 VarType v1 = left->getType();
382 VarType v2 = right->getType();
389 if ((left != NULL && left->couldBeBinaryIndex()) &&
390 (right != NULL) && right->couldBeBinaryIndex()) {
391 EdgeEncodingType type = (EdgeEncodingType)solver->getTuner()->getVarTunable(v1, v2, EDGEENCODING, &EdgeEncodingDesc);
392 result->setEncoding(type);
393 if (type == EDGE_MATCH) {
394 mergeNodes(left, right);
397 edgeMap.put(result, result);
398 edgeVector.push(result);
400 left->edges.add(result);
402 right->edges.add(result);
404 dst->edges.add(result);
409 EncodingNode::EncodingNode(Set *_s) :
413 uint EncodingNode::getSize() const {
417 VarType EncodingNode::getType() const {
421 static TunableDesc NodeEncodingDesc(ELEM_UNASSIGNED, BINARYINDEX, ELEM_UNASSIGNED);
423 EncodingNode *EncodingGraph::createNode(Element *e) {
424 if (e->type == ELEMCONST)
426 Set *s = e->getRange();
427 EncodingNode *n = encodingMap.get(s);
429 n = new EncodingNode(s);
430 n->setEncoding((ElementEncodingType)solver->getTuner()->getVarTunable(n->getType(), NODEENCODING, &NodeEncodingDesc));
432 encodingMap.put(s, n);
438 EncodingNode *EncodingGraph::getNode(Element *e) {
439 if (e->type == ELEMCONST)
441 Set *s = e->getRange();
442 EncodingNode *n = encodingMap.get(s);
446 void EncodingNode::addElement(Element *e) {
450 EncodingEdge::EncodingEdge(EncodingNode *_l, EncodingNode *_r) :
454 encoding(EDGE_UNASSIGNED),
461 EncodingEdge::EncodingEdge(EncodingNode *_left, EncodingNode *_right, EncodingNode *_dst) :
465 encoding(EDGE_UNASSIGNED),
472 uint hashEncodingEdge(EncodingEdge *edge) {
473 uintptr_t hash = (((uintptr_t) edge->left) >> 2) ^ (((uintptr_t)edge->right) >> 4) ^ (((uintptr_t)edge->dst) >> 6);
477 bool equalsEncodingEdge(EncodingEdge *e1, EncodingEdge *e2) {
478 return e1->left == e2->left && e1->right == e2->right && e1->dst == e2->dst;
481 uint64_t EncodingEdge::getValue() const {
482 uint lSize = (left != NULL) ? left->getSize() : 1;
483 uint rSize = (right != NULL) ? right->getSize() : 1;
484 uint min = (lSize < rSize) ? lSize : rSize;
485 return numEquals * min + numComparisons * lSize * rSize;