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);
55 void EncodingGraph::encode() {
56 SetIteratorEncodingSubGraph *itesg = subgraphs.iterator();
57 while (itesg->hasNext()) {
58 EncodingSubGraph *sg = itesg->next();
63 ElementIterator it(solver);
64 while (it.hasNext()) {
65 Element *e = it.next();
68 case ELEMFUNCRETURN: {
69 ElementEncoding *encoding = e->getElementEncoding();
70 if (encoding->getElementEncodingType() == ELEM_UNASSIGNED) {
71 EncodingNode *n = getNode(e);
74 ElementEncodingType encodetype = n->getEncoding();
75 encoding->setElementEncodingType(encodetype);
76 if (encodetype == UNARY || encodetype == ONEHOT) {
77 encoding->encodingArrayInitialization();
78 } else if (encodetype == BINARYINDEX) {
79 EncodingSubGraph *subgraph = graphMap.get(n);
80 DEBUG("graphMap.get(subgraph=%p, n=%p)\n", subgraph, n);
81 if (subgraph == NULL){
82 encoding->encodingArrayInitialization();
85 uint encodingSize = subgraph->getEncodingMaxVal(n) + 1;
86 uint paddedSize = encoding->getSizeEncodingArray(encodingSize);
87 encoding->allocInUseArrayElement(paddedSize);
88 encoding->allocEncodingArrayElement(paddedSize);
89 Set *s = e->getRange();
90 for (uint i = 0; i < s->getSize(); i++) {
91 uint64_t value = s->getElement(i);
92 uint encodingIndex = subgraph->getEncoding(n, value);
93 encoding->setInUseElement(encodingIndex);
94 encoding->encodingArray[encodingIndex] = value;
107 void EncodingGraph::encodeParent(Element *e) {
108 uint size = e->parents.getSize();
109 for (uint i = 0; i < size; i++) {
110 ASTNode *n = e->parents.get(i);
111 if (n->type == PREDICATEOP) {
112 BooleanPredicate *b = (BooleanPredicate *)n;
113 FunctionEncoding *fenc = b->getFunctionEncoding();
114 if (fenc->getFunctionEncodingType() != FUNC_UNASSIGNED)
116 Predicate *p = b->getPredicate();
117 if (p->type == OPERATORPRED) {
118 PredicateOperator *po = (PredicateOperator *)p;
119 ASSERT(b->inputs.getSize() == 2);
120 EncodingNode *left = createNode(b->inputs.get(0));
121 EncodingNode *right = createNode(b->inputs.get(1));
122 if (left == NULL || right == NULL)
124 EncodingEdge *edge = getEdge(left, right, NULL);
125 if (edge != NULL && edge->getEncoding() == EDGE_MATCH) {
126 fenc->setFunctionEncodingType(CIRCUIT);
133 void EncodingGraph::mergeNodes(EncodingNode *first, EncodingNode *second) {
134 EncodingSubGraph *graph1 = graphMap.get(first);
135 DEBUG("graphMap.get(first=%p, graph1=%p)\n", first, graph1);
136 EncodingSubGraph *graph2 = graphMap.get(second);
137 DEBUG("graphMap.get(second=%p, graph2=%p)\n", second, graph2);
139 first->setEncoding(BINARYINDEX);
141 second->setEncoding(BINARYINDEX);
143 if (graph1 == NULL && graph2 == NULL) {
144 graph1 = new EncodingSubGraph();
145 subgraphs.add(graph1);
146 DEBUG("graphMap.put(first=%p, graph1=%p)\n", first, graph1);
147 graphMap.put(first, graph1);
148 graph1->addNode(first);
150 if (graph1 == NULL && graph2 != NULL) {
153 EncodingNode *tmp = second;
157 if (graph1 != NULL && graph2 != NULL) {
158 SetIteratorEncodingNode *nodeit = graph2->nodeIterator();
159 while (nodeit->hasNext()) {
160 EncodingNode *node = nodeit->next();
161 graph1->addNode(node);
162 DEBUG("graphMap.put(node=%p, graph1=%p)\n", node, graph1);
163 graphMap.put(node, graph1);
165 subgraphs.remove(graph2);
167 DEBUG("Deleting graph2 =%p \n", graph2);
170 ASSERT(graph1 != NULL && graph2 == NULL);
171 graph1->addNode(first);
172 DEBUG("graphMap.put(first=%p, graph1=%p)\n", first, graph1);
173 graphMap.put(first, graph1);
177 void EncodingGraph::processElement(Element *e) {
178 uint size = e->parents.getSize();
179 for (uint i = 0; i < size; i++) {
180 ASTNode *n = e->parents.get(i);
183 processPredicate((BooleanPredicate *)n);
186 processFunction((ElementFunction *)n);
194 void EncodingGraph::processFunction(ElementFunction *ef) {
195 Function *f = ef->getFunction();
196 if (f->type == OPERATORFUNC) {
197 FunctionOperator *fo = (FunctionOperator *)f;
198 ASSERT(ef->inputs.getSize() == 2);
199 EncodingNode *left = createNode(ef->inputs.get(0));
200 EncodingNode *right = createNode(ef->inputs.get(1));
201 if (left == NULL && right == NULL)
203 EncodingNode *dst = createNode(ef);
204 EncodingEdge *edge = createEdge(left, right, dst);
209 void EncodingGraph::processPredicate(BooleanPredicate *b) {
210 Predicate *p = b->getPredicate();
211 if (p->type == OPERATORPRED) {
212 PredicateOperator *po = (PredicateOperator *)p;
213 ASSERT(b->inputs.getSize() == 2);
214 EncodingNode *left = createNode(b->inputs.get(0));
215 EncodingNode *right = createNode(b->inputs.get(1));
216 if (left == NULL || right == NULL)
218 EncodingEdge *edge = createEdge(left, right, NULL);
219 CompOp op = po->getOp();
228 edge->numComparisons++;
236 uint convertSize(uint cost) {
237 cost = 1.2 * cost;// fudge factor
238 return NEXTPOW2(cost);
241 void EncodingGraph::decideEdges() {
242 uint size = edgeVector.getSize();
243 for (uint i = 0; i < size; i++) {
244 EncodingEdge *ee = edgeVector.get(i);
245 EncodingNode *left = ee->left;
246 EncodingNode *right = ee->right;
248 if (ee->encoding != EDGE_UNASSIGNED ||
249 !left->couldBeBinaryIndex() ||
250 !right->couldBeBinaryIndex())
253 uint64_t eeValue = ee->getValue();
257 EncodingSubGraph *leftGraph = graphMap.get(left);
258 DEBUG("graphMap.get(left=%p, leftgraph=%p)\n", left, leftGraph);
259 EncodingSubGraph *rightGraph = graphMap.get(right);
260 DEBUG("graphMap.get(right=%p, rightgraph=%p)\n", right, rightGraph);
261 if (leftGraph == NULL && rightGraph != NULL) {
262 EncodingNode *tmp = left; left = right; right = tmp;
263 EncodingSubGraph *tmpsg = leftGraph; leftGraph = rightGraph; rightGraph = tmpsg;
266 uint leftSize = 0, rightSize = 0, newSize = 0;
267 uint64_t totalCost = 0;
268 if (leftGraph == NULL && rightGraph == NULL) {
269 leftSize = convertSize(left->getSize());
270 rightSize = convertSize(right->getSize());
271 newSize = convertSize(left->s->getUnionSize(right->s));
272 newSize = (leftSize > newSize) ? leftSize : newSize;
273 newSize = (rightSize > newSize) ? rightSize : newSize;
274 totalCost = (newSize - leftSize) * left->elements.getSize() +
275 (newSize - rightSize) * right->elements.getSize();
276 } else if (leftGraph != NULL && rightGraph == NULL) {
277 leftSize = convertSize(leftGraph->encodingSize);
278 rightSize = convertSize(right->getSize());
279 newSize = convertSize(leftGraph->estimateNewSize(right));
280 newSize = (leftSize > newSize) ? leftSize : newSize;
281 newSize = (rightSize > newSize) ? rightSize : newSize;
282 totalCost = (newSize - leftSize) * leftGraph->numElements +
283 (newSize - rightSize) * right->elements.getSize();
286 leftSize = convertSize(leftGraph->encodingSize);
287 rightSize = convertSize(rightGraph->encodingSize);
288 newSize = convertSize(leftGraph->estimateNewSize(rightGraph));
289 newSize = (leftSize > newSize) ? leftSize : newSize;
290 newSize = (rightSize > newSize) ? rightSize : newSize;
291 totalCost = (newSize - leftSize) * leftGraph->numElements +
292 (newSize - rightSize) * rightGraph->numElements;
294 double conversionfactor = 0.5;
295 if (leftGraph != rightGraph && (totalCost * conversionfactor) < eeValue) {
297 mergeNodes(left, right);
302 static TunableDesc EdgeEncodingDesc(EDGE_UNASSIGNED, EDGE_MATCH, EDGE_UNASSIGNED);
304 EncodingEdge *EncodingGraph::getEdge(EncodingNode *left, EncodingNode *right, EncodingNode *dst) {
305 EncodingEdge e(left, right, dst);
306 EncodingEdge *result = edgeMap.get(&e);
310 EncodingEdge *EncodingGraph::createEdge(EncodingNode *left, EncodingNode *right, EncodingNode *dst) {
311 EncodingEdge e(left, right, dst);
312 EncodingEdge *result = edgeMap.get(&e);
313 if (result == NULL) {
314 result = new EncodingEdge(left, right, dst);
315 VarType v1 = left->getType();
316 VarType v2 = right->getType();
323 if ((left != NULL && left->couldBeBinaryIndex()) &&
324 (right != NULL) && right->couldBeBinaryIndex()) {
325 EdgeEncodingType type = (EdgeEncodingType)solver->getTuner()->getVarTunable(v1, v2, EDGEENCODING, &EdgeEncodingDesc);
326 result->setEncoding(type);
327 if (type == EDGE_MATCH) {
328 mergeNodes(left, right);
331 edgeMap.put(result, result);
332 edgeVector.push(result);
334 left->edges.add(result);
336 right->edges.add(result);
338 dst->edges.add(result);
343 EncodingNode::EncodingNode(Set *_s) :
347 uint EncodingNode::getSize() const {
351 VarType EncodingNode::getType() const {
355 static TunableDesc NodeEncodingDesc(ELEM_UNASSIGNED, BINARYINDEX, ELEM_UNASSIGNED);
357 EncodingNode *EncodingGraph::createNode(Element *e) {
358 if (e->type == ELEMCONST)
360 Set *s = e->getRange();
361 EncodingNode *n = encodingMap.get(s);
363 n = new EncodingNode(s);
364 n->setEncoding((ElementEncodingType)solver->getTuner()->getVarTunable(n->getType(), NODEENCODING, &NodeEncodingDesc));
366 encodingMap.put(s, n);
372 EncodingNode *EncodingGraph::getNode(Element *e) {
373 if (e->type == ELEMCONST)
375 Set *s = e->getRange();
376 EncodingNode *n = encodingMap.get(s);
380 void EncodingNode::addElement(Element *e) {
384 EncodingEdge::EncodingEdge(EncodingNode *_l, EncodingNode *_r) :
388 encoding(EDGE_UNASSIGNED),
395 EncodingEdge::EncodingEdge(EncodingNode *_left, EncodingNode *_right, EncodingNode *_dst) :
399 encoding(EDGE_UNASSIGNED),
406 uint hashEncodingEdge(EncodingEdge *edge) {
407 uintptr_t hash = (((uintptr_t) edge->left) >> 2) ^ (((uintptr_t)edge->right) >> 4) ^ (((uintptr_t)edge->dst) >> 6);
411 bool equalsEncodingEdge(EncodingEdge *e1, EncodingEdge *e2) {
412 return e1->left == e2->left && e1->right == e2->right && e1->dst == e2->dst;
415 uint64_t EncodingEdge::getValue() const {
416 uint lSize = (left != NULL) ? left->getSize() : 1;
417 uint rSize = (right != NULL) ? right->getSize() : 1;
418 uint min = (lSize < rSize) ? lSize : rSize;
419 return numEquals * min + numComparisons * lSize * rSize;