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);
32 while (it.hasNext()) {
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);
58 while (it.hasNext()) {
59 Element *e = it.next();
62 case ELEMFUNCRETURN: {
63 ElementEncoding *encoding = e->getElementEncoding();
64 if (encoding->getElementEncodingType() == ELEM_UNASSIGNED) {
65 EncodingNode *n = getNode(e);
68 ElementEncodingType encodetype = n->getEncoding();
69 encoding->setElementEncodingType(encodetype);
70 if (encodetype == UNARY || encodetype == ONEHOT) {
71 encoding->encodingArrayInitialization();
72 } else if (encodetype == BINARYINDEX) {
73 EncodingSubGraph *subgraph = graphMap.get(n);
76 uint encodingSize = subgraph->getEncodingMaxVal(n)+1;
77 uint paddedSize = encoding->getSizeEncodingArray(encodingSize);
78 model_print("encoding size=%u\n", encodingSize);
79 model_print("padded=%u\n", paddedSize);
80 encoding->allocInUseArrayElement(paddedSize);
81 encoding->allocEncodingArrayElement(paddedSize);
82 Set *s = e->getRange();
83 for (uint i = 0; i < s->getSize(); i++) {
84 model_print("index=%u\n", i);
85 uint64_t value = s->getElement(i);
86 uint encodingIndex = subgraph->getEncoding(n, value);
87 encoding->setInUseElement(encodingIndex);
88 encoding->encodingArray[encodingIndex] = value;
101 void EncodingGraph::encodeParent(Element *e) {
102 uint size = e->parents.getSize();
103 for (uint i = 0; i < size; i++) {
104 ASTNode *n = e->parents.get(i);
105 if (n->type == PREDICATEOP) {
106 BooleanPredicate *b = (BooleanPredicate *)n;
107 FunctionEncoding *fenc = b->getFunctionEncoding();
108 if (fenc->getFunctionEncodingType() != FUNC_UNASSIGNED)
110 Predicate *p = b->getPredicate();
111 if (p->type == OPERATORPRED) {
112 PredicateOperator *po = (PredicateOperator *)p;
113 ASSERT(b->inputs.getSize() == 2);
114 EncodingNode *left = createNode(b->inputs.get(0));
115 EncodingNode *right = createNode(b->inputs.get(1));
116 if (left == NULL || right == NULL)
118 EncodingEdge *edge = getEdge(left, right, NULL);
119 if (edge != NULL && edge->getEncoding() == EDGE_MATCH) {
120 fenc->setFunctionEncodingType(CIRCUIT);
127 void EncodingGraph::mergeNodes(EncodingNode *first, EncodingNode *second) {
128 EncodingSubGraph *graph1 = graphMap.get(first);
129 EncodingSubGraph *graph2 = graphMap.get(second);
131 first->setEncoding(BINARYINDEX);
133 second->setEncoding(BINARYINDEX);
135 if (graph1 == NULL && graph2 == NULL) {
136 graph1 = new EncodingSubGraph();
137 subgraphs.add(graph1);
138 graphMap.put(first, graph1);
139 graph1->addNode(first);
141 if (graph1 == NULL && graph2 != NULL) {
144 EncodingNode *tmp = second;
148 if (graph1 != NULL && graph2 != NULL) {
149 SetIteratorEncodingNode *nodeit = graph2->nodeIterator();
150 while (nodeit->hasNext()) {
151 EncodingNode *node = nodeit->next();
152 graph1->addNode(node);
153 graphMap.put(node, graph1);
155 subgraphs.remove(graph2);
159 ASSERT(graph1 != NULL && graph2 == NULL);
160 graph1->addNode(second);
161 graphMap.put(second, graph1);
165 void EncodingGraph::processElement(Element *e) {
166 uint size = e->parents.getSize();
167 for (uint i = 0; i < size; i++) {
168 ASTNode *n = e->parents.get(i);
171 processPredicate((BooleanPredicate *)n);
174 processFunction((ElementFunction *)n);
182 void EncodingGraph::processFunction(ElementFunction *ef) {
183 Function *f = ef->getFunction();
184 if (f->type == OPERATORFUNC) {
185 FunctionOperator *fo = (FunctionOperator *)f;
186 ASSERT(ef->inputs.getSize() == 2);
187 EncodingNode *left = createNode(ef->inputs.get(0));
188 EncodingNode *right = createNode(ef->inputs.get(1));
189 if (left == NULL && right == NULL)
191 EncodingNode *dst = createNode(ef);
192 EncodingEdge *edge = createEdge(left, right, dst);
197 void EncodingGraph::processPredicate(BooleanPredicate *b) {
198 Predicate *p = b->getPredicate();
199 if (p->type == OPERATORPRED) {
200 PredicateOperator *po = (PredicateOperator *)p;
201 ASSERT(b->inputs.getSize() == 2);
202 EncodingNode *left = createNode(b->inputs.get(0));
203 EncodingNode *right = createNode(b->inputs.get(1));
204 if (left == NULL || right == NULL)
206 EncodingEdge *edge = createEdge(left, right, NULL);
207 CompOp op = po->getOp();
216 edge->numComparisons++;
224 uint convertSize(uint cost) {
225 cost = 1.2 * cost;// fudge factor
226 return NEXTPOW2(cost);
229 void EncodingGraph::decideEdges() {
230 uint size = edgeVector.getSize();
231 for (uint i = 0; i < size; i++) {
232 EncodingEdge *ee = edgeVector.get(i);
233 EncodingNode *left = ee->left;
234 EncodingNode *right = ee->right;
236 if (ee->encoding != EDGE_UNASSIGNED ||
237 !left->couldBeBinaryIndex() ||
238 !right->couldBeBinaryIndex())
241 uint64_t eeValue = ee->getValue();
245 EncodingSubGraph *leftGraph = graphMap.get(left);
246 EncodingSubGraph *rightGraph = graphMap.get(right);
247 if (leftGraph == NULL && rightGraph != NULL) {
248 EncodingNode *tmp = left; left = right; right = tmp;
249 EncodingSubGraph *tmpsg = leftGraph; leftGraph = rightGraph; rightGraph = tmpsg;
252 uint leftSize = 0, rightSize = 0, newSize = 0;
253 uint64_t totalCost = 0;
254 if (leftGraph == NULL && rightGraph == NULL) {
255 leftSize = convertSize(left->getSize());
256 rightSize = convertSize(right->getSize());
257 newSize = convertSize(left->s->getUnionSize(right->s));
258 newSize = (leftSize > newSize) ? leftSize : newSize;
259 newSize = (rightSize > newSize) ? rightSize : newSize;
260 totalCost = (newSize - leftSize) * left->elements.getSize() +
261 (newSize - rightSize) * right->elements.getSize();
262 } else if (leftGraph != NULL && rightGraph == NULL) {
263 leftSize = convertSize(leftGraph->encodingSize);
264 rightSize = convertSize(right->getSize());
265 newSize = convertSize(leftGraph->estimateNewSize(right));
266 newSize = (leftSize > newSize) ? leftSize : newSize;
267 newSize = (rightSize > newSize) ? rightSize : newSize;
268 totalCost = (newSize - leftSize) * leftGraph->numElements +
269 (newSize - rightSize) * right->elements.getSize();
272 leftSize = convertSize(leftGraph->encodingSize);
273 rightSize = convertSize(rightGraph->encodingSize);
274 newSize = convertSize(leftGraph->estimateNewSize(rightGraph));
275 newSize = (leftSize > newSize) ? leftSize : newSize;
276 newSize = (rightSize > newSize) ? rightSize : newSize;
277 totalCost = (newSize - leftSize) * leftGraph->numElements +
278 (newSize - rightSize) * rightGraph->numElements;
280 double conversionfactor = 0.5;
281 if ((totalCost * conversionfactor) < eeValue) {
283 mergeNodes(left, right);
288 static TunableDesc EdgeEncodingDesc(EDGE_UNASSIGNED, EDGE_MATCH, EDGE_UNASSIGNED);
290 EncodingEdge *EncodingGraph::getEdge(EncodingNode *left, EncodingNode *right, EncodingNode *dst) {
291 EncodingEdge e(left, right, dst);
292 EncodingEdge *result = edgeMap.get(&e);
296 EncodingEdge *EncodingGraph::createEdge(EncodingNode *left, EncodingNode *right, EncodingNode *dst) {
297 EncodingEdge e(left, right, dst);
298 EncodingEdge *result = edgeMap.get(&e);
299 if (result == NULL) {
300 result = new EncodingEdge(left, right, dst);
301 VarType v1 = left->getType();
302 VarType v2 = right->getType();
309 if ((left != NULL && left->couldBeBinaryIndex()) &&
310 (right != NULL) && right->couldBeBinaryIndex()) {
311 EdgeEncodingType type = (EdgeEncodingType)solver->getTuner()->getVarTunable(v1, v2, EDGEENCODING, &EdgeEncodingDesc);
312 result->setEncoding(type);
313 if (type == EDGE_MATCH) {
314 mergeNodes(left, right);
317 edgeMap.put(result, result);
318 edgeVector.push(result);
320 left->edges.add(result);
322 right->edges.add(result);
324 dst->edges.add(result);
329 EncodingNode::EncodingNode(Set *_s) :
333 uint EncodingNode::getSize() const {
337 VarType EncodingNode::getType() const {
341 static TunableDesc NodeEncodingDesc(ELEM_UNASSIGNED, BINARYINDEX, ELEM_UNASSIGNED);
343 EncodingNode *EncodingGraph::createNode(Element *e) {
344 if (e->type == ELEMCONST)
346 Set *s = e->getRange();
347 EncodingNode *n = encodingMap.get(s);
349 n = new EncodingNode(s);
350 n->setEncoding((ElementEncodingType)solver->getTuner()->getVarTunable(n->getType(), NODEENCODING, &NodeEncodingDesc));
352 encodingMap.put(s, n);
358 EncodingNode *EncodingGraph::getNode(Element *e) {
359 if (e->type == ELEMCONST)
361 Set *s = e->getRange();
362 EncodingNode *n = encodingMap.get(s);
366 void EncodingNode::addElement(Element *e) {
370 EncodingEdge::EncodingEdge(EncodingNode *_l, EncodingNode *_r) :
374 encoding(EDGE_UNASSIGNED),
381 EncodingEdge::EncodingEdge(EncodingNode *_left, EncodingNode *_right, EncodingNode *_dst) :
385 encoding(EDGE_UNASSIGNED),
392 uint hashEncodingEdge(EncodingEdge *edge) {
393 uintptr_t hash = (((uintptr_t) edge->left) >> 2) ^ (((uintptr_t)edge->right) >> 4) ^ (((uintptr_t)edge->dst) >> 6);
397 bool equalsEncodingEdge(EncodingEdge *e1, EncodingEdge *e2) {
398 return e1->left == e2->left && e1->right == e2->right && e1->dst == e2->dst;
401 uint64_t EncodingEdge::getValue() const {
402 uint lSize = (left != NULL) ? left->getSize() : 1;
403 uint rSize = (right != NULL) ? right->getSize() : 1;
404 uint min = (lSize < rSize) ? lSize : rSize;
405 return numEquals * min + numComparisons * lSize * rSize;