X-Git-Url: http://plrg.eecs.uci.edu/git/?p=satune.git;a=blobdiff_plain;f=src%2FASTAnalyses%2FEncoding%2Fencodinggraph.cc;h=3bcf68ea6f823542d2ce810bc763944af560c349;hp=8d34d473d6fcaec7a40930497c138b560004b1b1;hb=7fe0a11814834cc8f5937d059602513eea746c9f;hpb=df77afe03f12fc649314f63b7ca1e27e3164438f

diff --git a/src/ASTAnalyses/Encoding/encodinggraph.cc b/src/ASTAnalyses/Encoding/encodinggraph.cc
index 8d34d47..3bcf68e 100644
--- a/src/ASTAnalyses/Encoding/encodinggraph.cc
+++ b/src/ASTAnalyses/Encoding/encodinggraph.cc
@@ -6,11 +6,25 @@
 #include "set.h"
 #include "csolver.h"
 #include "tunable.h"
+#include "qsort.h"
+#include "subgraph.h"
+#include "elementencoding.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 +42,54 @@ void EncodingGraph::buildGraph() {
 			ASSERT(0);
 		}
 	}
+	bsdqsort(edgeVector.expose(), edgeVector.getSize(), sizeof(EncodingEdge *), sortEncodingEdge);
+	decideEdges();
+}
+
+void EncodingGraph::encode() {
+	SetIteratorEncodingSubGraph * itesg=subgraphs.iterator();
+	while(itesg->hasNext()) {
+		EncodingSubGraph *sg=itesg->next();
+		sg->encode();
+	}
+	delete itesg;
+
+	ElementIterator it(solver);
+	while(it.hasNext()) {
+		Element * e = it.next();
+		switch(e->type) {
+		case ELEMSET:
+		case ELEMFUNCRETURN: {
+			ElementEncoding *encoding=getElementEncoding(e);
+			if (encoding->getElementEncodingType() == ELEM_UNASSIGNED) {
+				EncodingNode *n = getNode(e);
+				ASSERT(n != NULL);
+				ElementEncodingType encodetype=n->getEncoding();
+				encoding->setElementEncodingType(encodetype);
+				if (encodetype == UNARY || encodetype == ONEHOT) {
+					encoding->encodingArrayInitialization();
+				} else if (encodetype == BINARYINDEX) {
+					EncodingSubGraph * subgraph = graphMap.get(n);
+					uint encodingSize = subgraph->getEncodingSize(n);
+					uint paddedSize = encoding->getSizeEncodingArray(encodingSize);
+					encoding->allocInUseArrayElement(paddedSize);
+					encoding->allocEncodingArrayElement(paddedSize);
+					Set * s=e->getRange();
+					for(uint i=0;i<s->getSize();i++) {
+						uint64_t value=s->getElement(i);
+						uint encodingIndex=subgraph->getEncoding(n, value);
+						encoding->setInUseElement(encodingIndex);
+						encoding->encodingArray[encodingIndex] = value;
+					}
+				}
+			}
+			break;
+		}
+		default:
+			break;
+		}
+	}
+	
 }
 
 void EncodingGraph::mergeNodes(EncodingNode *first, EncodingNode *second) {
@@ -35,6 +97,7 @@ void EncodingGraph::mergeNodes(EncodingNode *first, EncodingNode *second) {
 	EncodingSubGraph *graph2=graphMap.get(second);
 	if (graph1 == NULL && graph2 == NULL) {
 		graph1 = new EncodingSubGraph();
+		subgraphs.add(graph1);
 		graphMap.put(first, graph1);
 		graph1->addNode(first);
 	}
@@ -52,6 +115,7 @@ void EncodingGraph::mergeNodes(EncodingNode *first, EncodingNode *second) {
 			graph1->addNode(node);
 			graphMap.put(node, graph1);
 		}
+		subgraphs.remove(graph2);
 		delete nodeit;
 		delete graph2;
 	} else {
@@ -120,6 +184,70 @@ 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; i<size; i++) {
+		EncodingEdge *ee = edgeVector.get(i);
+		EncodingNode *left = ee->left;
+		EncodingNode *right = ee->right;
+		
+		if (ee->encoding != EDGE_UNASSIGNED ||
+				left->encoding != BINARYINDEX ||
+				right->encoding != BINARYINDEX)
+			continue;
+		
+		uint64_t eeValue = ee->getValue();
+		if (eeValue == 0)
+			return;
+
+		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 +262,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 +308,14 @@ EncodingNode * EncodingGraph::createNode(Element *e) {
 		encodingMap.put(s, n);
 	}
 	n->addElement(e);
-	if (discovered.add(e))
-		n->numElements++;
+	return n;
+}
+
+EncodingNode * EncodingGraph::getNode(Element *e) {
+	if (e->type == ELEMCONST)
+		return NULL;
+	Set *s = e->getRange();
+	EncodingNode *n = encodingMap.get(s);
 	return n;
 }
 
@@ -206,19 +354,11 @@ 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; i<size; i++) {
-		uint64_t val=s->getElement(i);
-		values.add(val);
-	}
-}
 
-SetIteratorEncodingNode * EncodingSubGraph::nodeIterator() {
-	return nodes.iterator();
-}