More EncodingGraph work
authorbdemsky <bdemsky@uci.edu>
Mon, 11 Sep 2017 23:21:15 +0000 (16:21 -0700)
committerbdemsky <bdemsky@uci.edu>
Mon, 11 Sep 2017 23:21:15 +0000 (16:21 -0700)
src/ASTAnalyses/Encoding/encodinggraph.cc
src/ASTAnalyses/Encoding/encodinggraph.h
src/Collections/structs.h
src/Tuner/tunable.h

index b2cac1a..8d34d47 100644 (file)
@@ -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;i<size;i++) {
@@ -89,11 +120,21 @@ void EncodingGraph::processPredicate(BooleanPredicate *b) {
        }
 }
 
+static TunableDesc EdgeEncodingDesc(EDGE_UNASSIGNED, EDGE_MATCH, EDGE_UNASSIGNED);
+
 EncodingEdge * EncodingGraph::getEdge(EncodingNode *left, EncodingNode *right, EncodingNode *dst) {
        EncodingEdge e(left, right, dst);
        EncodingEdge *result = edgeMap.get(&e);
        if (result == NULL) {
                result=new EncodingEdge(left, right, dst);
+               VarType v1=left->getType();
+               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; i<size; i++) {
+               uint64_t val=s->getElement(i);
+               values.add(val);
+       }
+}
+
+SetIteratorEncodingNode * EncodingSubGraph::nodeIterator() {
+       return nodes.iterator();
+}
index 62e3b8f..e44ccfd 100644 (file)
@@ -5,8 +5,13 @@
 
 uint hashEncodingEdge(EncodingEdge *edge);
 bool equalsEncodingEdge(EncodingEdge *e1, EncodingEdge *e2);
+class EncodingSubGraph;
+
 
 typedef Hashtable<EncodingEdge *, EncodingEdge *, uintptr_t, PTRSHIFT, hashEncodingEdge, equalsEncodingEdge> HashtableEdge;
+typedef Hashset<EncodingNode *, uintptr_t, PTRSHIFT> HashsetEncodingNode;
+typedef SetIterator<EncodingNode *, uintptr_t, PTRSHIFT> SetIteratorEncodingNode;
+typedef Hashtable<EncodingNode *, EncodingSubGraph *, uintptr_t, PTRSHIFT> 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
index 6ee69ab..1e957ae 100644 (file)
@@ -26,6 +26,7 @@ typedef Hashset<OrderElement *, uintptr_t, PTRSHIFT, order_element_hash_function
 typedef Hashset<Boolean *, uintptr_t, PTRSHIFT> HashsetBoolean;
 typedef Hashset<Element *, uintptr_t, PTRSHIFT> HashsetElement;
 typedef SetIterator<Boolean *, uintptr_t, PTRSHIFT> SetIteratorBoolean;
+typedef Hashset<uint64_t, uint64_t, 0> Hashset64Int;
 
 typedef Hashtable<OrderNode *, HashsetOrderNode *, uintptr_t, PTRSHIFT> HashtableNodeToNodeSet;
 typedef Hashtable<OrderPair *, OrderPair *, uintptr_t, PTRSHIFT, order_pair_hash_function, order_pair_equals> HashtableOrderPair;
@@ -33,6 +34,9 @@ typedef Hashtable<void *, void *, uintptr_t, PTRSHIFT> CloneMap;
 
 
 typedef Hashtable<Set *, EncodingNode *, uintptr_t, PTRSHIFT> HashtableEncoding;
+typedef Hashset<EncodingNode *, uintptr_t, PTRSHIFT> HashsetEncodingNode;
+typedef SetIterator<EncodingNode *, uintptr_t, PTRSHIFT> SetIteratorEncodingNode;
+
 
 typedef SetIterator<TableEntry *, uintptr_t, PTRSHIFT, table_entry_hash_function, table_entry_equals> SetIteratorTableEntry;
 typedef SetIterator<OrderEdge *, uintptr_t, PTRSHIFT, order_edge_hash_function, order_edge_equals> SetIteratorOrderEdge;
index 050d46f..012f420 100644 (file)
@@ -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