1 #include "encodinggraph.h"
10 EncodingGraph::EncodingGraph(CSolver * _solver) :
16 void EncodingGraph::buildGraph() {
17 ElementIterator it(solver);
19 Element * e = it.next();
33 void EncodingGraph::mergeNodes(EncodingNode *first, EncodingNode *second) {
34 EncodingSubGraph *graph1=graphMap.get(first);
35 EncodingSubGraph *graph2=graphMap.get(second);
36 if (graph1 == NULL && graph2 == NULL) {
37 graph1 = new EncodingSubGraph();
38 graphMap.put(first, graph1);
39 graph1->addNode(first);
41 if (graph1 == NULL && graph2 != NULL) {
44 EncodingNode *tmp = second;
48 if (graph1 != NULL && graph2 != NULL) {
49 SetIteratorEncodingNode * nodeit=graph2->nodeIterator();
50 while(nodeit->hasNext()) {
51 EncodingNode *node=nodeit->next();
52 graph1->addNode(node);
53 graphMap.put(node, graph1);
58 ASSERT(graph1 != NULL && graph2 == NULL);
59 graph1->addNode(second);
60 graphMap.put(second, graph1);
64 void EncodingGraph::processElement(Element *e) {
65 uint size=e->parents.getSize();
66 for(uint i=0;i<size;i++) {
67 ASTNode * n = e->parents.get(i);
70 processPredicate((BooleanPredicate *)n);
73 processFunction((ElementFunction *)n);
81 void EncodingGraph::processFunction(ElementFunction *ef) {
82 Function *f=ef->getFunction();
83 if (f->type==OPERATORFUNC) {
84 FunctionOperator *fo=(FunctionOperator*)f;
85 ASSERT(ef->inputs.getSize() == 2);
86 EncodingNode *left=createNode(ef->inputs.get(0));
87 EncodingNode *right=createNode(ef->inputs.get(1));
88 if (left == NULL && right == NULL)
90 EncodingNode *dst=createNode(ef);
91 EncodingEdge *edge=getEdge(left, right, dst);
96 void EncodingGraph::processPredicate(BooleanPredicate *b) {
97 Predicate *p=b->getPredicate();
98 if (p->type==OPERATORPRED) {
99 PredicateOperator *po=(PredicateOperator *)p;
100 ASSERT(b->inputs.getSize()==2);
101 EncodingNode *left=createNode(b->inputs.get(0));
102 EncodingNode *right=createNode(b->inputs.get(1));
103 if (left == NULL || right == NULL)
105 EncodingEdge *edge=getEdge(left, right, NULL);
106 CompOp op=po->getOp();
115 edge->numComparisons++;
123 static TunableDesc EdgeEncodingDesc(EDGE_UNASSIGNED, EDGE_MATCH, EDGE_UNASSIGNED);
125 EncodingEdge * EncodingGraph::getEdge(EncodingNode *left, EncodingNode *right, EncodingNode *dst) {
126 EncodingEdge e(left, right, dst);
127 EncodingEdge *result = edgeMap.get(&e);
128 if (result == NULL) {
129 result=new EncodingEdge(left, right, dst);
130 VarType v1=left->getType();
131 VarType v2=right->getType();
137 result->setEncoding((EdgeEncodingType)solver->getTuner()->getVarTunable(v1, v2, EDGEENCODING, &EdgeEncodingDesc));
138 edgeMap.put(result, result);
143 EncodingNode::EncodingNode(Set *_s) :
148 uint EncodingNode::getSize() {
152 VarType EncodingNode::getType() {
156 static TunableDesc NodeEncodingDesc(ELEM_UNASSIGNED, BINARYINDEX, ELEM_UNASSIGNED);
158 EncodingNode * EncodingGraph::createNode(Element *e) {
159 if (e->type == ELEMCONST)
161 Set *s = e->getRange();
162 EncodingNode *n = encodingMap.get(s);
164 n = new EncodingNode(s);
165 n->setEncoding((ElementEncodingType)solver->getTuner()->getVarTunable(n->getType(), NODEENCODING, &NodeEncodingDesc));
166 encodingMap.put(s, n);
169 if (discovered.add(e))
174 void EncodingNode::addElement(Element *e) {
178 EncodingEdge::EncodingEdge(EncodingNode *_l, EncodingNode *_r) :
182 encoding(EDGE_UNASSIGNED),
189 EncodingEdge::EncodingEdge(EncodingNode *_left, EncodingNode *_right, EncodingNode *_dst) :
193 encoding(EDGE_UNASSIGNED),
200 uint hashEncodingEdge(EncodingEdge *edge) {
201 uintptr_t hash=(((uintptr_t) edge->left) >> 2) ^ (((uintptr_t)edge->right) >> 4) ^ (((uintptr_t)edge->dst) >> 6);
205 bool equalsEncodingEdge(EncodingEdge *e1, EncodingEdge *e2) {
206 return e1->left == e2->left && e1->right == e2->right && e1->dst == e2->dst;
209 EncodingSubGraph::EncodingSubGraph() {
212 void EncodingSubGraph::addNode(EncodingNode *n) {
215 uint size=s->getSize();
216 for(uint i=0; i<size; i++) {
217 uint64_t val=s->getElement(i);
222 SetIteratorEncodingNode * EncodingSubGraph::nodeIterator() {
223 return nodes.iterator();
226 uint EncodingSubGraph::computeIntersection(Set *s) {
228 uint size=s->getSize();
229 for(uint i=0; i<size; i++) {
230 uint64_t val=s->getElement(i);
231 if (values.contains(val))
237 uint EncodingSubGraph::computeIntersection(EncodingSubGraph *g) {
238 if (g->values.getSize() > values.getSize()) {
239 //iterator over smaller set
240 return g->computeIntersection(this);
244 SetIterator64Int * iter=g->values.iterator();
245 while(iter->hasNext()) {
246 uint64_t val=iter->next();
247 if (values.contains(val))