1 #include "encodinggraph.h"
11 EncodingGraph::EncodingGraph(CSolver * _solver) :
17 void EncodingGraph::buildGraph() {
18 ElementIterator it(solver);
20 Element * e = it.next();
34 void EncodingGraph::mergeNodes(EncodingNode *first, EncodingNode *second) {
35 EncodingSubGraph *graph1=graphMap.get(first);
36 EncodingSubGraph *graph2=graphMap.get(second);
37 if (graph1 == NULL && graph2 == NULL) {
38 graph1 = new EncodingSubGraph();
39 graphMap.put(first, graph1);
40 graph1->addNode(first);
42 if (graph1 == NULL && graph2 != NULL) {
45 EncodingNode *tmp = second;
49 if (graph1 != NULL && graph2 != NULL) {
50 SetIteratorEncodingNode * nodeit=graph2->nodeIterator();
51 while(nodeit->hasNext()) {
52 EncodingNode *node=nodeit->next();
53 graph1->addNode(node);
54 graphMap.put(node, graph1);
59 ASSERT(graph1 != NULL && graph2 == NULL);
60 graph1->addNode(second);
61 graphMap.put(second, graph1);
65 void EncodingGraph::processElement(Element *e) {
66 uint size=e->parents.getSize();
67 for(uint i=0;i<size;i++) {
68 ASTNode * n = e->parents.get(i);
71 processPredicate((BooleanPredicate *)n);
74 processFunction((ElementFunction *)n);
82 void EncodingGraph::processFunction(ElementFunction *ef) {
83 Function *f=ef->getFunction();
84 if (f->type==OPERATORFUNC) {
85 FunctionOperator *fo=(FunctionOperator*)f;
86 ASSERT(ef->inputs.getSize() == 2);
87 EncodingNode *left=createNode(ef->inputs.get(0));
88 EncodingNode *right=createNode(ef->inputs.get(1));
89 if (left == NULL && right == NULL)
91 EncodingNode *dst=createNode(ef);
92 EncodingEdge *edge=getEdge(left, right, dst);
97 void EncodingGraph::processPredicate(BooleanPredicate *b) {
98 Predicate *p=b->getPredicate();
99 if (p->type==OPERATORPRED) {
100 PredicateOperator *po=(PredicateOperator *)p;
101 ASSERT(b->inputs.getSize()==2);
102 EncodingNode *left=createNode(b->inputs.get(0));
103 EncodingNode *right=createNode(b->inputs.get(1));
104 if (left == NULL || right == NULL)
106 EncodingEdge *edge=getEdge(left, right, NULL);
107 CompOp op=po->getOp();
116 edge->numComparisons++;
124 static TunableDesc EdgeEncodingDesc(EDGE_UNASSIGNED, EDGE_MATCH, EDGE_UNASSIGNED);
126 EncodingEdge * EncodingGraph::getEdge(EncodingNode *left, EncodingNode *right, EncodingNode *dst) {
127 EncodingEdge e(left, right, dst);
128 EncodingEdge *result = edgeMap.get(&e);
129 if (result == NULL) {
130 result=new EncodingEdge(left, right, dst);
131 VarType v1=left->getType();
132 VarType v2=right->getType();
138 result->setEncoding((EdgeEncodingType)solver->getTuner()->getVarTunable(v1, v2, EDGEENCODING, &EdgeEncodingDesc));
139 edgeMap.put(result, result);
144 EncodingNode::EncodingNode(Set *_s) :
149 uint EncodingNode::getSize() {
153 VarType EncodingNode::getType() {
157 static TunableDesc NodeEncodingDesc(ELEM_UNASSIGNED, BINARYINDEX, ELEM_UNASSIGNED);
159 EncodingNode * EncodingGraph::createNode(Element *e) {
160 if (e->type == ELEMCONST)
162 Set *s = e->getRange();
163 EncodingNode *n = encodingMap.get(s);
165 n = new EncodingNode(s);
166 n->setEncoding((ElementEncodingType)solver->getTuner()->getVarTunable(n->getType(), NODEENCODING, &NodeEncodingDesc));
167 encodingMap.put(s, n);
170 if (discovered.add(e))
175 void EncodingNode::addElement(Element *e) {
179 EncodingEdge::EncodingEdge(EncodingNode *_l, EncodingNode *_r) :
183 encoding(EDGE_UNASSIGNED),
190 EncodingEdge::EncodingEdge(EncodingNode *_left, EncodingNode *_right, EncodingNode *_dst) :
194 encoding(EDGE_UNASSIGNED),
201 uint hashEncodingEdge(EncodingEdge *edge) {
202 uintptr_t hash=(((uintptr_t) edge->left) >> 2) ^ (((uintptr_t)edge->right) >> 4) ^ (((uintptr_t)edge->dst) >> 6);
206 bool equalsEncodingEdge(EncodingEdge *e1, EncodingEdge *e2) {
207 return e1->left == e2->left && e1->right == e2->right && e1->dst == e2->dst;
210 EncodingSubGraph::EncodingSubGraph() {
213 void EncodingSubGraph::addNode(EncodingNode *n) {
216 uint size=s->getSize();
217 for(uint i=0; i<size; i++) {
218 uint64_t val=s->getElement(i);
223 SetIteratorEncodingNode * EncodingSubGraph::nodeIterator() {
224 return nodes.iterator();
227 uint EncodingSubGraph::computeIntersection(Set *s) {
229 uint size=s->getSize();
230 for(uint i=0; i<size; i++) {
231 uint64_t val=s->getElement(i);
232 if (values.contains(val))
238 uint EncodingSubGraph::computeIntersection(EncodingSubGraph *g) {
239 if (g->values.getSize() > values.getSize()) {
240 //iterator over smaller set
241 return g->computeIntersection(this);
245 SetIterator64Int * iter=g->values.iterator();
246 while(iter->hasNext()) {
247 uint64_t val=iter->next();
248 if (values.contains(val))