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();
58 while (it->hasNext()) {
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 if (solver->getTuner()->getTunable(ENCODINGGRAPHOPT, &offon) == 0)
119 SetIteratorEncodingSubGraph *itesg = subgraphs.iterator();
120 model_print("#SubGraph = %u\n", subgraphs.getSize());
121 while (itesg->hasNext()) {
122 EncodingSubGraph *sg = itesg->next();
127 ElementIterator it(solver);
128 while (it.hasNext()) {
129 Element *e = it.next();
132 case ELEMFUNCRETURN: {
133 ElementEncoding *encoding = e->getElementEncoding();
134 if (encoding->getElementEncodingType() == ELEM_UNASSIGNED) {
135 EncodingNode *n = getNode(e);
138 ElementEncodingType encodetype = n->getEncoding();
139 encoding->setElementEncodingType(encodetype);
140 if (encodetype == UNARY || encodetype == ONEHOT) {
141 encoding->encodingArrayInitialization();
142 } else if (encodetype == BINARYINDEX) {
143 EncodingSubGraph *subgraph = graphMap.get(n);
144 DEBUG("graphMap.get(subgraph=%p, n=%p)\n", subgraph, n);
145 if (subgraph == NULL) {
146 encoding->encodingArrayInitialization();
149 uint encodingSize = subgraph->getEncodingMaxVal(n) + 1;
150 uint paddedSize = encoding->getSizeEncodingArray(encodingSize);
151 encoding->allocInUseArrayElement(paddedSize);
152 encoding->allocEncodingArrayElement(paddedSize);
153 Set *s = e->getRange();
154 for (uint i = 0; i < s->getSize(); i++) {
155 uint64_t value = s->getElement(i);
156 uint encodingIndex = subgraph->getEncoding(n, value);
157 encoding->setInUseElement(encodingIndex);
158 ASSERT(encoding->isinUseElement(encodingIndex));
159 encoding->encodingArray[encodingIndex] = value;
172 void EncodingGraph::encodeParent(Element *e) {
173 uint size = e->parents.getSize();
174 for (uint i = 0; i < size; i++) {
175 ASTNode *n = e->parents.get(i);
176 if (n->type == PREDICATEOP) {
177 BooleanPredicate *b = (BooleanPredicate *)n;
178 FunctionEncoding *fenc = b->getFunctionEncoding();
179 if (fenc->getFunctionEncodingType() != FUNC_UNASSIGNED)
181 Predicate *p = b->getPredicate();
182 if (p->type == OPERATORPRED) {
183 PredicateOperator *po = (PredicateOperator *)p;
184 ASSERT(b->inputs.getSize() == 2);
185 EncodingNode *left = createNode(b->inputs.get(0));
186 EncodingNode *right = createNode(b->inputs.get(1));
187 if (left == NULL || right == NULL)
189 EncodingEdge *edge = getEdge(left, right, NULL);
191 EncodingSubGraph *leftGraph = graphMap.get(left);
192 if (leftGraph != NULL && leftGraph == graphMap.get(right)) {
193 fenc->setFunctionEncodingType(CIRCUIT);
201 void EncodingGraph::mergeNodes(EncodingNode *first, EncodingNode *second) {
202 EncodingSubGraph *graph1 = graphMap.get(first);
203 DEBUG("graphMap.get(first=%p, graph1=%p)\n", first, graph1);
204 EncodingSubGraph *graph2 = graphMap.get(second);
205 DEBUG("graphMap.get(second=%p, graph2=%p)\n", second, graph2);
207 first->setEncoding(BINARYINDEX);
209 second->setEncoding(BINARYINDEX);
211 if (graph1 == NULL && graph2 == NULL) {
212 graph1 = new EncodingSubGraph();
213 subgraphs.add(graph1);
214 DEBUG("graphMap.put(first=%p, graph1=%p)\n", first, graph1);
215 graphMap.put(first, graph1);
216 graph1->addNode(first);
218 if (graph1 == NULL && graph2 != NULL) {
221 EncodingNode *tmp = second;
225 if (graph1 != NULL && graph2 != NULL) {
226 if (graph1 == graph2)
229 SetIteratorEncodingNode *nodeit = graph2->nodeIterator();
230 while (nodeit->hasNext()) {
231 EncodingNode *node = nodeit->next();
232 graph1->addNode(node);
233 DEBUG("graphMap.put(node=%p, graph1=%p)\n", node, graph1);
234 graphMap.put(node, graph1);
236 subgraphs.remove(graph2);
238 DEBUG("Deleting graph2 =%p \n", graph2);
241 ASSERT(graph1 != NULL && graph2 == NULL);
242 graph1->addNode(second);
243 DEBUG("graphMap.put(first=%p, graph1=%p)\n", first, graph1);
244 graphMap.put(second, graph1);
248 void EncodingGraph::processElement(Element *e) {
249 uint size = e->parents.getSize();
250 for (uint i = 0; i < size; i++) {
251 ASTNode *n = e->parents.get(i);
254 processPredicate((BooleanPredicate *)n);
257 processFunction((ElementFunction *)n);
265 void EncodingGraph::processFunction(ElementFunction *ef) {
266 Function *f = ef->getFunction();
267 if (f->type == OPERATORFUNC) {
268 FunctionOperator *fo = (FunctionOperator *)f;
269 ASSERT(ef->inputs.getSize() == 2);
270 EncodingNode *left = createNode(ef->inputs.get(0));
271 EncodingNode *right = createNode(ef->inputs.get(1));
272 if (left == NULL && right == NULL)
274 EncodingNode *dst = createNode(ef);
275 EncodingEdge *edge = createEdge(left, right, dst);
280 void EncodingGraph::processPredicate(BooleanPredicate *b) {
281 Predicate *p = b->getPredicate();
282 if (p->type == OPERATORPRED) {
283 PredicateOperator *po = (PredicateOperator *)p;
284 ASSERT(b->inputs.getSize() == 2);
285 EncodingNode *left = createNode(b->inputs.get(0));
286 EncodingNode *right = createNode(b->inputs.get(1));
287 if (left == NULL || right == NULL)
289 EncodingEdge *edge = createEdge(left, right, NULL);
290 CompOp op = po->getOp();
299 edge->numComparisons++;
307 uint convertSize(uint cost) {
308 return NEXTPOW2(cost);
311 void EncodingGraph::decideEdges() {
312 uint size = edgeVector.getSize();
313 for (uint i = 0; i < size; i++) {
314 EncodingEdge *ee = edgeVector.get(i);
315 EncodingNode *left = ee->left;
316 EncodingNode *right = ee->right;
318 if (ee->encoding != EDGE_UNASSIGNED ||
319 !left->couldBeBinaryIndex() ||
320 !right->couldBeBinaryIndex())
323 uint64_t eeValue = ee->getValue();
327 EncodingSubGraph *leftGraph = graphMap.get(left);
328 DEBUG("graphMap.get(left=%p, leftgraph=%p)\n", left, leftGraph);
329 EncodingSubGraph *rightGraph = graphMap.get(right);
330 DEBUG("graphMap.get(right=%p, rightgraph=%p)\n", right, rightGraph);
331 if (leftGraph == NULL && rightGraph != NULL) {
332 EncodingNode *tmp = left; left = right; right = tmp;
333 EncodingSubGraph *tmpsg = leftGraph; leftGraph = rightGraph; rightGraph = tmpsg;
336 uint leftSize = 0, rightSize = 0, newSize = 0, min = 0;
338 if (leftGraph == NULL && rightGraph == NULL) {
339 leftSize = convertSize(left->getSize());
340 rightSize = convertSize(right->getSize());
341 newSize = convertSize(left->s->getUnionSize(right->s));
342 newSize = (leftSize > newSize) ? leftSize : newSize;
343 newSize = (rightSize > newSize) ? rightSize : newSize;
344 min = rightSize > leftSize ? leftSize : rightSize;
345 merge = left->measureSimilarity(right) > 1.5 || min == newSize;
346 } else if (leftGraph != NULL && rightGraph == NULL) {
347 leftSize = convertSize(leftGraph->numValues());
348 rightSize = convertSize(right->getSize());
349 newSize = convertSize(leftGraph->estimateNewSize(right));
350 newSize = (leftSize > newSize) ? leftSize : newSize;
351 newSize = (rightSize > newSize) ? rightSize : newSize;
352 min = rightSize > leftSize ? leftSize : rightSize;
353 // model_print("Merge=%s\tsimilarity=%f\n", max==newSize?"TRUE":"FALSE", left->measureSimilarity(right));
354 merge = leftGraph->measureSimilarity(right) > 1.5 || min == newSize;
357 leftSize = convertSize(leftGraph->numValues());
358 rightSize = convertSize(rightGraph->numValues());
359 newSize = convertSize(leftGraph->estimateNewSize(rightGraph));
360 // model_print("MergingSubGraphs: left=%u\tright=%u\tnewSize=%u\n", leftSize, rightSize, newSize);
361 newSize = (leftSize > newSize) ? leftSize : newSize;
362 newSize = (rightSize > newSize) ? rightSize : newSize;
363 min = rightSize > leftSize ? leftSize : rightSize;
364 // model_print("Merge=%s\tsimilarity=%f\n", max==newSize?"TRUE":"FALSE", leftGraph->measureSimilarity(right));
365 merge = leftGraph->measureSimilarity(rightGraph) > 1.5 || min == newSize;
369 mergeNodes(left, right);
374 static TunableDesc EdgeEncodingDesc(EDGE_UNASSIGNED, EDGE_MATCH, EDGE_UNASSIGNED);
376 EncodingEdge *EncodingGraph::getEdge(EncodingNode *left, EncodingNode *right, EncodingNode *dst) {
377 EncodingEdge e(left, right, dst);
378 EncodingEdge *result = edgeMap.get(&e);
382 EncodingEdge *EncodingGraph::createEdge(EncodingNode *left, EncodingNode *right, EncodingNode *dst) {
383 EncodingEdge e(left, right, dst);
384 EncodingEdge *result = edgeMap.get(&e);
385 if (result == NULL) {
386 result = new EncodingEdge(left, right, dst);
387 VarType v1 = left->getType();
388 VarType v2 = right->getType();
395 if ((left != NULL && left->couldBeBinaryIndex()) &&
396 (right != NULL) && right->couldBeBinaryIndex()) {
397 EdgeEncodingType type = (EdgeEncodingType)solver->getTuner()->getVarTunable(v1, v2, EDGEENCODING, &EdgeEncodingDesc);
398 result->setEncoding(type);
399 if (type == EDGE_MATCH) {
400 mergeNodes(left, right);
403 edgeMap.put(result, result);
404 edgeVector.push(result);
406 left->edges.add(result);
408 right->edges.add(result);
410 dst->edges.add(result);
415 EncodingNode::EncodingNode(Set *_s) :
419 uint EncodingNode::getSize() const {
423 uint64_t EncodingNode::getIndex(uint index) {
424 return s->getElement(index);
427 VarType EncodingNode::getType() const {
431 double EncodingNode::measureSimilarity(EncodingNode *node) {
433 for (uint i = 0, j = 0; i < s->getSize() && j < node->s->getSize(); ) {
434 uint64_t item = s->getElement(i);
435 uint64_t item2 = node->s->getElement(j);
438 else if (item2 > item)
447 return common * 1.0 / s->getSize() + common * 1.0 / node->getSize();
450 EncodingNode *EncodingGraph::createNode(Element *e) {
451 if (e->type == ELEMCONST)
453 Set *s = e->getRange();
454 EncodingNode *n = encodingMap.get(s);
456 n = new EncodingNode(s);
457 n->setEncoding((ElementEncodingType)solver->getTuner()->getVarTunable(n->getType(), NODEENCODING, &NodeEncodingDesc));
459 encodingMap.put(s, n);
465 EncodingNode *EncodingGraph::getNode(Element *e) {
466 if (e->type == ELEMCONST)
468 Set *s = e->getRange();
469 EncodingNode *n = encodingMap.get(s);
473 void EncodingNode::addElement(Element *e) {
477 EncodingEdge::EncodingEdge(EncodingNode *_l, EncodingNode *_r) :
481 encoding(EDGE_UNASSIGNED),
488 EncodingEdge::EncodingEdge(EncodingNode *_left, EncodingNode *_right, EncodingNode *_dst) :
492 encoding(EDGE_UNASSIGNED),
499 uint hashEncodingEdge(EncodingEdge *edge) {
500 uintptr_t hash = (((uintptr_t) edge->left) >> 2) ^ (((uintptr_t)edge->right) >> 4) ^ (((uintptr_t)edge->dst) >> 6);
504 bool equalsEncodingEdge(EncodingEdge *e1, EncodingEdge *e2) {
505 return e1->left == e2->left && e1->right == e2->right && e1->dst == e2->dst;
508 uint64_t EncodingEdge::getValue() const {
509 uint lSize = (left != NULL) ? left->getSize() : 1;
510 uint rSize = (right != NULL) ? right->getSize() : 1;
511 uint min = (lSize < rSize) ? lSize : rSize;
512 return numEquals * min + numComparisons * lSize * rSize;