From e429b2b27c998f21bc9c836718f1506d01d9dcf3 Mon Sep 17 00:00:00 2001 From: bdemsky Date: Wed, 13 Sep 2017 23:22:51 -0700 Subject: [PATCH] Subgraphing code in place --- src/AST/set.cc | 25 +++ src/AST/set.h | 1 + src/ASTAnalyses/Encoding/encodinggraph.cc | 186 +++++++++++++++++----- src/ASTAnalyses/Encoding/encodinggraph.h | 24 ++- src/Collections/array.h | 4 +- src/Collections/cppvector.h | 6 +- src/Collections/hashset.h | 4 +- src/Collections/vector.h | 2 +- 8 files changed, 195 insertions(+), 57 deletions(-) diff --git a/src/AST/set.cc b/src/AST/set.cc index 54c6679..6e150ff 100644 --- a/src/AST/set.cc +++ b/src/AST/set.cc @@ -82,6 +82,31 @@ Set *Set::clone(CSolver *solver, CloneMap *map) { return s; } +uint Set::getUnionSize(Set *s) { + uint sSize = s->getSize(); + uint thisSize = getSize(); + uint sIndex = 0; + uint thisIndex = 0; + uint sum = 0; + uint64_t sValue = s->getElement(sIndex); + uint64_t thisValue = getElement(thisIndex); + while(thisIndex < thisSize && sIndex < sSize) { + if (sValue < thisValue) { + sValue = s->getElement(++sIndex); + sum++; + } else if (thisValue < sValue) { + thisValue = getElement(++thisIndex); + sum++; + } else { + thisValue = getElement(++thisIndex); + sValue = s->getElement(++sIndex); + sum++; + } + } + sum += (thisSize - thisIndex) + (sSize - sIndex); + + return sum; +} void Set::serialize(Serializer* serializer){ if(serializer->isSerialized(this)) diff --git a/src/AST/set.h b/src/AST/set.h index 6dbeac0..2eb4828 100644 --- a/src/AST/set.h +++ b/src/AST/set.h @@ -24,6 +24,7 @@ public: uint64_t getNewUniqueItem() {return low++;} uint64_t getMemberAt(uint index); uint64_t getElement(uint index); + uint getUnionSize(Set *s); virtual Set *clone(CSolver *solver, CloneMap *map); virtual void serialize(Serializer* serializer); CMEMALLOC; diff --git a/src/ASTAnalyses/Encoding/encodinggraph.cc b/src/ASTAnalyses/Encoding/encodinggraph.cc index 8fe908a..4fdc1c6 100644 --- a/src/ASTAnalyses/Encoding/encodinggraph.cc +++ b/src/ASTAnalyses/Encoding/encodinggraph.cc @@ -6,11 +6,23 @@ #include "set.h" #include "csolver.h" #include "tunable.h" +#include "qsort.h" EncodingGraph::EncodingGraph(CSolver * _solver) : solver(_solver) { - +} +int sortEncodingEdge(const void * p1, const void *p2) { + const EncodingEdge * e1 = * (const EncodingEdge **) p1; + const EncodingEdge * e2 = * (const EncodingEdge **) p2; + uint64_t v1 = e1->getValue(); + uint64_t v2 = e2->getValue(); + if (v1 < v2) + return 1; + else if (v1 == v2) + return 0; + else + return -1; } void EncodingGraph::buildGraph() { @@ -28,6 +40,7 @@ void EncodingGraph::buildGraph() { ASSERT(0); } } + bsdqsort(edgeVector.expose(), edgeVector.getSize(), sizeof(EncodingEdge *), sortEncodingEdge); } void EncodingGraph::mergeNodes(EncodingNode *first, EncodingNode *second) { @@ -120,6 +133,66 @@ void EncodingGraph::processPredicate(BooleanPredicate *b) { } } +uint convertSize(uint cost) { + cost = 1.2 * cost; // fudge factor + return NEXTPOW2(cost); +} + +void EncodingGraph::decideEdges() { + uint size=edgeVector.getSize(); + for(uint i=0; iencoding != EDGE_UNASSIGNED) + continue; + + uint64_t eeValue = ee->getValue(); + if (eeValue == 0) + return; + EncodingNode *left = ee->left; + EncodingNode *right = ee->right; + EncodingSubGraph *leftGraph = graphMap.get(left); + EncodingSubGraph *rightGraph = graphMap.get(right); + if (leftGraph == NULL && rightGraph !=NULL) { + EncodingNode *tmp = left; left=right; right=tmp; + EncodingSubGraph *tmpsg = leftGraph; leftGraph = rightGraph; rightGraph = tmpsg; + } + + uint leftSize=0, rightSize=0, newSize=0; + uint64_t totalCost=0; + if (leftGraph == NULL && rightGraph == NULL) { + leftSize=convertSize(left->getSize()); + rightSize=convertSize(right->getSize()); + newSize=convertSize(left->s->getUnionSize(right->s)); + newSize=(leftSize > newSize) ? leftSize: newSize; + newSize=(rightSize > newSize) ? rightSize: newSize; + totalCost = (newSize - leftSize) * left->elements.getSize() + + (newSize - rightSize) * right->elements.getSize(); + } else if (leftGraph != NULL && rightGraph == NULL) { + leftSize=convertSize(leftGraph->encodingSize); + rightSize=convertSize(right->getSize()); + newSize=convertSize(leftGraph->estimateNewSize(right)); + newSize=(leftSize > newSize) ? leftSize: newSize; + newSize=(rightSize > newSize) ? rightSize: newSize; + totalCost = (newSize - leftSize) * leftGraph->numElements + + (newSize - rightSize) * right->elements.getSize(); + } else { + //Neither are null + leftSize=convertSize(leftGraph->encodingSize); + rightSize=convertSize(rightGraph->encodingSize); + newSize=convertSize(leftGraph->estimateNewSize(rightGraph)); + newSize=(leftSize > newSize) ? leftSize: newSize; + newSize=(rightSize > newSize) ? rightSize: newSize; + totalCost = (newSize - leftSize) * leftGraph->numElements + + (newSize - rightSize) * rightGraph->numElements; + } + double conversionfactor = 0.5; + if ((totalCost * conversionfactor) < eeValue) { + //add the edge + mergeNodes(left, right); + } + } +} + static TunableDesc EdgeEncodingDesc(EDGE_UNASSIGNED, EDGE_MATCH, EDGE_UNASSIGNED); EncodingEdge * EncodingGraph::getEdge(EncodingNode *left, EncodingNode *right, EncodingNode *dst) { @@ -134,22 +207,36 @@ EncodingEdge * EncodingGraph::getEdge(EncodingNode *left, EncodingNode *right, E v2=v1; v1=tmp; } - result->setEncoding((EdgeEncodingType)solver->getTuner()->getVarTunable(v1, v2, EDGEENCODING, &EdgeEncodingDesc)); + + if ((left != NULL && left->encoding==BINARYINDEX) && + (right != NULL) && right->encoding==BINARYINDEX) { + EdgeEncodingType type=(EdgeEncodingType)solver->getTuner()->getVarTunable(v1, v2, EDGEENCODING, &EdgeEncodingDesc); + result->setEncoding(type); + if (type == EDGE_MATCH) { + mergeNodes(left, right); + } + } edgeMap.put(result, result); + edgeVector.push(result); + if (left != NULL) + left->edges.add(result); + if (right != NULL) + right->edges.add(result); + if (dst != NULL) + dst->edges.add(result); } return result; } EncodingNode::EncodingNode(Set *_s) : - s(_s), - numElements(0) { + s(_s) { } -uint EncodingNode::getSize() { +uint EncodingNode::getSize() const { return s->getSize(); } -VarType EncodingNode::getType() { +VarType EncodingNode::getType() const { return s->getType(); } @@ -166,8 +253,6 @@ EncodingNode * EncodingGraph::createNode(Element *e) { encodingMap.put(s, n); } n->addElement(e); - if (discovered.add(e)) - n->numElements++; return n; } @@ -206,47 +291,64 @@ bool equalsEncodingEdge(EncodingEdge *e1, EncodingEdge *e2) { return e1->left == e2->left && e1->right == e2->right && e1->dst == e2->dst; } -EncodingSubGraph::EncodingSubGraph() { +uint64_t EncodingEdge::getValue() const { + uint lSize = (left != NULL) ? left->getSize() : 1; + uint rSize = (right != NULL) ? right->getSize() : 1; + uint min = (lSize < rSize) ? lSize : rSize; + return numEquals * min + numComparisons * lSize * rSize; } -void EncodingSubGraph::addNode(EncodingNode *n) { - nodes.add(n); - Set *s=n->s; - uint size=s->getSize(); - for(uint i=0; igetElement(i); - values.add(val); - } +EncodingSubGraph::EncodingSubGraph() : + encodingSize(0), + numElements(0) { } -SetIteratorEncodingNode * EncodingSubGraph::nodeIterator() { - return nodes.iterator(); +uint EncodingSubGraph::estimateNewSize(EncodingSubGraph *sg) { + uint newSize=0; + SetIteratorEncodingNode * nit = sg->nodes.iterator(); + while(nit->hasNext()) { + EncodingNode *en = nit->next(); + uint size=estimateNewSize(en); + if (size > newSize) + newSize = size; + } + delete nit; + return newSize; } -uint EncodingSubGraph::computeIntersection(Set *s) { - uint intersect=0; - uint size=s->getSize(); - for(uint i=0; igetElement(i); - if (values.contains(val)) - intersect++; +uint EncodingSubGraph::estimateNewSize(EncodingNode *n) { + SetIteratorEncodingEdge * eeit = n->edges.iterator(); + uint newsize=n->getSize(); + while(eeit->hasNext()) { + EncodingEdge * ee = eeit->next(); + if (ee->left != NULL && ee->left != n && nodes.contains(ee->left)) { + uint intersectSize = n->s->getUnionSize(ee->left->s); + if (intersectSize > newsize) + newsize = intersectSize; + } + if (ee->right != NULL && ee->right != n && nodes.contains(ee->right)) { + uint intersectSize = n->s->getUnionSize(ee->right->s); + if (intersectSize > newsize) + newsize = intersectSize; + } + if (ee->dst != NULL && ee->dst != n && nodes.contains(ee->dst)) { + uint intersectSize = n->s->getUnionSize(ee->dst->s); + if (intersectSize > newsize) + newsize = intersectSize; + } } - return intersect; + delete eeit; + return newsize; } -uint EncodingSubGraph::computeIntersection(EncodingSubGraph *g) { - if (g->values.getSize() > values.getSize()) { - //iterator over smaller set - return g->computeIntersection(this); - } - - uint intersect=0; - SetIterator64Int * iter=g->values.iterator(); - while(iter->hasNext()) { - uint64_t val=iter->next(); - if (values.contains(val)) - intersect++; - } - delete iter; - return intersect; +void EncodingSubGraph::addNode(EncodingNode *n) { + nodes.add(n); + uint newSize=estimateNewSize(n); + numElements += n->elements.getSize(); + if (newSize > encodingSize) + encodingSize=newSize; +} + +SetIteratorEncodingNode * EncodingSubGraph::nodeIterator() { + return nodes.iterator(); } diff --git a/src/ASTAnalyses/Encoding/encodinggraph.h b/src/ASTAnalyses/Encoding/encodinggraph.h index 4057dd2..f452dac 100644 --- a/src/ASTAnalyses/Encoding/encodinggraph.h +++ b/src/ASTAnalyses/Encoding/encodinggraph.h @@ -11,6 +11,9 @@ class EncodingSubGraph; typedef Hashtable HashtableEdge; typedef Hashset HashsetEncodingNode; typedef SetIterator SetIteratorEncodingNode; +typedef Hashset HashsetEncodingEdge; +typedef SetIterator SetIteratorEncodingEdge; + typedef Hashtable HashtableNodeToSubGraph; class EncodingGraph { @@ -23,10 +26,11 @@ class EncodingGraph { CSolver * solver; HashtableEncoding encodingMap; HashtableEdge edgeMap; + Vector edgeVector; HashsetElement discovered; HashtableNodeToSubGraph graphMap; - + void decideEdges(); void mergeNodes(EncodingNode *first, EncodingNode *second); void processElement(Element *e); void processFunction(ElementFunction *f); @@ -39,15 +43,15 @@ class EncodingNode { public: EncodingNode(Set *_s); void addElement(Element *e); - uint getSize(); - VarType getType(); + uint getSize() const; + VarType getType() const; void setEncoding(ElementEncodingType e) {encoding=e;} CMEMALLOC; private: Set *s; HashsetElement elements; - uint numElements; + HashsetEncodingEdge edges; ElementEncodingType encoding; friend class EncodingGraph; friend class EncodingSubGraph; @@ -58,13 +62,17 @@ class EncodingSubGraph { EncodingSubGraph(); void addNode(EncodingNode *n); SetIteratorEncodingNode * nodeIterator(); - uint computeIntersection(Set *s); - uint computeIntersection(EncodingSubGraph *g); CMEMALLOC; private: + uint estimateNewSize(EncodingNode *n); + uint estimateNewSize(EncodingSubGraph *sg); + HashsetEncodingNode nodes; - Hashset64Int values; + uint encodingSize; + uint numElements; + + friend class EncodingGraph; }; enum EdgeEncodingType { EDGE_UNASSIGNED, EDGE_BREAK, EDGE_MATCH}; @@ -75,6 +83,7 @@ class EncodingEdge { EncodingEdge(EncodingNode *_l, EncodingNode *_r); EncodingEdge(EncodingNode *_l, EncodingNode *_r, EncodingNode *_d); void setEncoding(EdgeEncodingType e) {encoding=e;} + uint64_t getValue() const; CMEMALLOC; private: @@ -88,6 +97,7 @@ class EncodingEdge { friend uint hashEncodingEdge(EncodingEdge *edge); friend bool equalsEncodingEdge(EncodingEdge *e1, EncodingEdge *e2); friend class EncodingGraph; + friend class EncodingSubGraph; }; #endif diff --git a/src/Collections/array.h b/src/Collections/array.h index 496bdc6..03d83cd 100644 --- a/src/Collections/array.h +++ b/src/Collections/array.h @@ -27,7 +27,7 @@ public: } } - type get(uint index) { + type get(uint index) const { return array[index]; } @@ -35,7 +35,7 @@ public: array[index] = item; } - uint getSize() { + uint getSize() const { return size; } diff --git a/src/Collections/cppvector.h b/src/Collections/cppvector.h index e9164df..2d4cc19 100644 --- a/src/Collections/cppvector.h +++ b/src/Collections/cppvector.h @@ -24,7 +24,7 @@ public: size--; } - type last() { + type last() const { return array[size - 1]; } @@ -49,7 +49,7 @@ public: array[size++] = item; } - type get(uint index) { + type get(uint index) const { return array[index]; } @@ -63,7 +63,7 @@ public: array[index] = item; } - uint getSize() { + uint getSize() const { return size; } diff --git a/src/Collections/hashset.h b/src/Collections/hashset.h index cdba3b2..13edbf9 100644 --- a/src/Collections/hashset.h +++ b/src/Collections/hashset.h @@ -205,11 +205,11 @@ public: return true; } - unsigned int getSize() { + unsigned int getSize() const { return table->getSize(); } - bool isEmpty() { + bool isEmpty() const { return getSize() == 0; } diff --git a/src/Collections/vector.h b/src/Collections/vector.h index ac32d85..58e7abd 100644 --- a/src/Collections/vector.h +++ b/src/Collections/vector.h @@ -81,7 +81,7 @@ void setVector ## name(Vector ## name * vector, uint index, type item) { \ vector->array[index] = item; \ } \ - uint getSizeVector ## name(Vector ## name * vector) { \ + uint getSizeVector ## name(const Vector ## name * vector) { \ return vector->size; \ } \ void deleteVector ## name(Vector ## name * vector) { \ -- 2.34.1