From df77afe03f12fc649314f63b7ca1e27e3164438f Mon Sep 17 00:00:00 2001 From: bdemsky Date: Mon, 11 Sep 2017 16:21:15 -0700 Subject: [PATCH] More EncodingGraph work --- src/ASTAnalyses/Encoding/encodinggraph.cc | 64 ++++++++++++++++++++++- src/ASTAnalyses/Encoding/encodinggraph.h | 31 +++++++++++ src/Collections/structs.h | 4 ++ src/Tuner/tunable.h | 2 +- 4 files changed, 98 insertions(+), 3 deletions(-) diff --git a/src/ASTAnalyses/Encoding/encodinggraph.cc b/src/ASTAnalyses/Encoding/encodinggraph.cc index b2cac1a..8d34d47 100644 --- a/src/ASTAnalyses/Encoding/encodinggraph.cc +++ b/src/ASTAnalyses/Encoding/encodinggraph.cc @@ -30,6 +30,37 @@ void EncodingGraph::buildGraph() { } } +void EncodingGraph::mergeNodes(EncodingNode *first, EncodingNode *second) { + EncodingSubGraph *graph1=graphMap.get(first); + EncodingSubGraph *graph2=graphMap.get(second); + if (graph1 == NULL && graph2 == NULL) { + graph1 = new EncodingSubGraph(); + graphMap.put(first, graph1); + graph1->addNode(first); + } + if (graph1 == NULL && graph2 != NULL) { + graph1 = graph2; + graph2 = NULL; + EncodingNode *tmp = second; + second = first; + first = tmp; + } + if (graph1 != NULL && graph2 != NULL) { + SetIteratorEncodingNode * nodeit=graph2->nodeIterator(); + while(nodeit->hasNext()) { + EncodingNode *node=nodeit->next(); + graph1->addNode(node); + graphMap.put(node, graph1); + } + delete nodeit; + delete graph2; + } else { + ASSERT(graph1 != NULL && graph2 == NULL); + graph1->addNode(second); + graphMap.put(second, graph1); + } +} + void EncodingGraph::processElement(Element *e) { uint size=e->parents.getSize(); for(uint i=0;igetType(); + VarType v2=right->getType(); + if (v1 > v2) { + VarType tmp=v2; + v2=v1; + v1=tmp; + } + result->setEncoding((EdgeEncodingType)solver->getTuner()->getVarTunable(v1, v2, EDGEENCODING, &EdgeEncodingDesc)); edgeMap.put(result, result); } return result; @@ -112,7 +153,7 @@ VarType EncodingNode::getType() { return s->getType(); } -static TunableDesc NodeEncodingType(ELEM_UNASSIGNED, BINARYVAL, ELEM_UNASSIGNED); +static TunableDesc NodeEncodingDesc(ELEM_UNASSIGNED, BINARYINDEX, ELEM_UNASSIGNED); EncodingNode * EncodingGraph::createNode(Element *e) { if (e->type == ELEMCONST) @@ -121,7 +162,7 @@ EncodingNode * EncodingGraph::createNode(Element *e) { EncodingNode *n = encodingMap.get(s); if (n == NULL) { n = new EncodingNode(s); - n->setEncoding((ElementEncodingType)solver->getTuner()->getVarTunable(n->getType(), NODEENCODING, &NodeEncodingType)); + n->setEncoding((ElementEncodingType)solver->getTuner()->getVarTunable(n->getType(), NODEENCODING, &NodeEncodingDesc)); encodingMap.put(s, n); } n->addElement(e); @@ -138,6 +179,7 @@ EncodingEdge::EncodingEdge(EncodingNode *_l, EncodingNode *_r) : left(_l), right(_r), dst(NULL), + encoding(EDGE_UNASSIGNED), numArithOps(0), numEquals(0), numComparisons(0) @@ -148,6 +190,7 @@ EncodingEdge::EncodingEdge(EncodingNode *_left, EncodingNode *_right, EncodingNo left(_left), right(_right), dst(_dst), + encoding(EDGE_UNASSIGNED), numArithOps(0), numEquals(0), numComparisons(0) @@ -162,3 +205,20 @@ uint hashEncodingEdge(EncodingEdge *edge) { bool equalsEncodingEdge(EncodingEdge *e1, EncodingEdge *e2) { return e1->left == e2->left && e1->right == e2->right && e1->dst == e2->dst; } + +EncodingSubGraph::EncodingSubGraph() { +} + +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); + } +} + +SetIteratorEncodingNode * EncodingSubGraph::nodeIterator() { + return nodes.iterator(); +} diff --git a/src/ASTAnalyses/Encoding/encodinggraph.h b/src/ASTAnalyses/Encoding/encodinggraph.h index 62e3b8f..e44ccfd 100644 --- a/src/ASTAnalyses/Encoding/encodinggraph.h +++ b/src/ASTAnalyses/Encoding/encodinggraph.h @@ -5,8 +5,13 @@ uint hashEncodingEdge(EncodingEdge *edge); bool equalsEncodingEdge(EncodingEdge *e1, EncodingEdge *e2); +class EncodingSubGraph; + typedef Hashtable HashtableEdge; +typedef Hashset HashsetEncodingNode; +typedef SetIterator SetIteratorEncodingNode; +typedef Hashtable HashtableNodeToSubGraph; class EncodingGraph { public: @@ -19,6 +24,10 @@ class EncodingGraph { HashtableEncoding encodingMap; HashtableEdge edgeMap; HashsetElement discovered; + HashtableNodeToSubGraph graphMap; + + + void mergeNodes(EncodingNode *first, EncodingNode *second); void processElement(Element *e); void processFunction(ElementFunction *f); void processPredicate(BooleanPredicate *b); @@ -41,17 +50,36 @@ class EncodingNode { uint numElements; ElementEncodingType encoding; friend class EncodingGraph; + friend class EncodingSubGraph; +}; + +class EncodingSubGraph { + public: + EncodingSubGraph(); + void addNode(EncodingNode *n); + SetIteratorEncodingNode * nodeIterator(); + + CMEMALLOC; + private: + HashsetEncodingNode nodes; + Hashset64Int values; }; +enum EdgeEncodingType { EDGE_UNASSIGNED, EDGE_BREAK, EDGE_MATCH}; +typedef enum EdgeEncodingType EdgeEncodingType; + class EncodingEdge { public: EncodingEdge(EncodingNode *_l, EncodingNode *_r); EncodingEdge(EncodingNode *_l, EncodingNode *_r, EncodingNode *_d); + void setEncoding(EdgeEncodingType e) {encoding=e;} CMEMALLOC; + private: EncodingNode *left; EncodingNode *right; EncodingNode *dst; + EdgeEncodingType encoding; uint numArithOps; uint numEquals; uint numComparisons; @@ -59,4 +87,7 @@ class EncodingEdge { friend bool equalsEncodingEdge(EncodingEdge *e1, EncodingEdge *e2); friend class EncodingGraph; }; + + + #endif diff --git a/src/Collections/structs.h b/src/Collections/structs.h index 6ee69ab..1e957ae 100644 --- a/src/Collections/structs.h +++ b/src/Collections/structs.h @@ -26,6 +26,7 @@ typedef Hashset HashsetBoolean; typedef Hashset HashsetElement; typedef SetIterator SetIteratorBoolean; +typedef Hashset Hashset64Int; typedef Hashtable HashtableNodeToNodeSet; typedef Hashtable HashtableOrderPair; @@ -33,6 +34,9 @@ typedef Hashtable CloneMap; typedef Hashtable HashtableEncoding; +typedef Hashset HashsetEncodingNode; +typedef SetIterator SetIteratorEncodingNode; + typedef SetIterator SetIteratorTableEntry; typedef SetIterator SetIteratorOrderEdge; diff --git a/src/Tuner/tunable.h b/src/Tuner/tunable.h index 050d46f..012f420 100644 --- a/src/Tuner/tunable.h +++ b/src/Tuner/tunable.h @@ -39,6 +39,6 @@ public: static TunableDesc onoff(0, 1, 1); static TunableDesc offon(0, 1, 0); -enum Tunables {DECOMPOSEORDER, MUSTREACHGLOBAL, MUSTREACHLOCAL, MUSTREACHPRUNE, OPTIMIZEORDERSTRUCTURE, ORDERINTEGERENCODING, PREPROCESS, NODEENCODING}; +enum Tunables {DECOMPOSEORDER, MUSTREACHGLOBAL, MUSTREACHLOCAL, MUSTREACHPRUNE, OPTIMIZEORDERSTRUCTURE, ORDERINTEGERENCODING, PREPROCESS, NODEENCODING, EDGEENCODING}; typedef enum Tunables Tunables; #endif -- 2.34.1