2 #include "encodinggraph.h"
6 EncodingSubGraph::EncodingSubGraph() :
12 EncodingSubGraph::~EncodingSubGraph() {
13 map.resetAndDeleteKeys();
14 values.resetAndDelete();
17 uint hashNodeValuePair(NodeValuePair *nvp) {
18 return (uint) (nvp->value ^ ((uintptr_t)nvp->node));
21 bool equalsNodeValuePair(NodeValuePair *nvp1, NodeValuePair *nvp2) {
22 return nvp1->value == nvp2->value && nvp1->node == nvp2->node;
25 int sortEncodingValue(const void *p1, const void *p2) {
26 const EncodingValue *e1 = *(const EncodingValue **) p1;
27 const EncodingValue *e2 = *(const EncodingValue **) p2;
28 uint se1 = e1->notequals.getSize();
29 uint se2 = e2->notequals.getSize();
38 uint EncodingSubGraph::getEncoding(EncodingNode *n, uint64_t val) {
39 NodeValuePair nvp(n, val);
40 EncodingValue *ev = map.get(&nvp);
44 void EncodingSubGraph::solveEquals() {
45 Vector<EncodingValue *> toEncode;
46 Vector<bool> encodingArray;
47 SetIteratorEncodingValue *valIt = values.iterator();
48 while (valIt->hasNext()) {
49 EncodingValue *ev = valIt->next();
50 if (!ev->inComparison)
56 bsdqsort(toEncode.expose(), toEncode.getSize(), sizeof(EncodingValue *), sortEncodingValue);
57 uint toEncodeSize = toEncode.getSize();
58 for (uint i = 0; i < toEncodeSize; i++) {
59 EncodingValue *ev = toEncode.get(i);
60 encodingArray.clear();
61 SetIteratorEncodingValue *conflictIt = ev->notequals.iterator();
62 while (conflictIt->hasNext()) {
63 EncodingValue *conflict = conflictIt->next();
64 ASSERT(conflict->value != ev->value);
65 if (conflict->assigned) {
66 encodingArray.setExpand(conflict->encoding, true);
71 for (; encoding < encodingArray.getSize(); encoding++) {
72 //See if this is unassigned
73 if (!encodingArray.get(encoding))
76 if (encoding > maxEncodingVal)
77 maxEncodingVal = encoding;
78 ev->encoding = encoding;
83 void EncodingSubGraph::solveComparisons() {
84 HashsetEncodingValue discovered;
85 Vector<EncodingValue *> tovisit;
86 SetIteratorEncodingValue *valIt = values.iterator();
87 while (valIt->hasNext()) {
88 EncodingValue *ev = valIt->next();
89 if (discovered.add(ev)) {
91 while (tovisit.getSize() != 0) {
92 EncodingValue *val = tovisit.last(); tovisit.pop();
93 SetIteratorEncodingValue *nextIt = val->larger.iterator();
94 uint minVal = val->encoding + 1;
95 while (nextIt->hasNext()) {
96 EncodingValue *nextVal = nextIt->next();
97 if (nextVal->encoding < minVal) {
98 if (minVal > maxEncodingVal)
99 maxEncodingVal = minVal;
100 nextVal->encoding = minVal;
101 discovered.add(nextVal);
102 tovisit.push(nextVal);
112 uint EncodingSubGraph::estimateNewSize(EncodingSubGraph *sg) {
114 SetIteratorEncodingNode *nit = sg->nodes.iterator();
115 while (nit->hasNext()) {
116 EncodingNode *en = nit->next();
117 uint size = estimateNewSize(en);
125 uint EncodingSubGraph::estimateNewSize(EncodingNode *n) {
126 SetIteratorEncodingEdge *eeit = n->edges.iterator();
127 uint newsize = n->getSize();
128 while (eeit->hasNext()) {
129 EncodingEdge *ee = eeit->next();
130 if (ee->left != NULL && ee->left != n && nodes.contains(ee->left)) {
131 uint intersectSize = n->s->getUnionSize(ee->left->s);
132 if (intersectSize > newsize)
133 newsize = intersectSize;
135 if (ee->right != NULL && ee->right != n && nodes.contains(ee->right)) {
136 uint intersectSize = n->s->getUnionSize(ee->right->s);
137 if (intersectSize > newsize)
138 newsize = intersectSize;
140 if (ee->dst != NULL && ee->dst != n && nodes.contains(ee->dst)) {
141 uint intersectSize = n->s->getUnionSize(ee->dst->s);
142 if (intersectSize > newsize)
143 newsize = intersectSize;
150 void EncodingSubGraph::addNode(EncodingNode *n) {
152 uint newSize = estimateNewSize(n);
153 numElements += n->elements.getSize();
154 if (newSize > encodingSize)
155 encodingSize = newSize;
158 SetIteratorEncodingNode *EncodingSubGraph::nodeIterator() {
159 return nodes.iterator();
162 void EncodingSubGraph::encode() {
163 computeEncodingValue();
164 computeComparisons();
170 void EncodingSubGraph::computeEqualities() {
171 SetIteratorEncodingNode *nodeit = nodes.iterator();
172 while (nodeit->hasNext()) {
173 EncodingNode *node = nodeit->next();
174 generateEquals(node, node);
176 SetIteratorEncodingEdge *edgeit = node->edges.iterator();
177 while (edgeit->hasNext()) {
178 EncodingEdge *edge = edgeit->next();
179 //skip over comparisons as we have already handled them
180 if (edge->numComparisons != 0)
182 if (edge->numEquals == 0)
184 if (edge->left == NULL || !nodes.contains(edge->left))
186 if (edge->right == NULL || !nodes.contains(edge->right))
189 if (edge->left != node)
191 //We have a comparison edge between two nodes in the subgraph
192 //For now we don't support multiple encoding values with the same encoding....
193 //So we enforce != constraints for every Set...
194 if (edge->left != edge->right)
195 generateEquals(edge->left, edge->right);
202 void EncodingSubGraph::computeComparisons() {
203 SetIteratorEncodingNode *nodeit = nodes.iterator();
204 while (nodeit->hasNext()) {
205 EncodingNode *node = nodeit->next();
206 SetIteratorEncodingEdge *edgeit = node->edges.iterator();
207 while (edgeit->hasNext()) {
208 EncodingEdge *edge = edgeit->next();
209 if (edge->numComparisons == 0)
211 if (edge->left == NULL || !nodes.contains(edge->left))
213 if (edge->right == NULL || !nodes.contains(edge->right))
216 if (edge->left != node)
218 //We have a comparison edge between two nodes in the subgraph
219 generateComparison(edge->left, edge->right);
226 void EncodingSubGraph::orderEV(EncodingValue *earlier, EncodingValue *later) {
227 earlier->larger.add(later);
230 void EncodingSubGraph::generateEquals(EncodingNode *left, EncodingNode *right) {
232 Set *rset = right->s;
233 uint lSize = lset->getSize(), rSize = rset->getSize();
234 for (uint lindex = 0; lindex < lSize; lindex++) {
235 for (uint rindex = 0; rindex < rSize; rindex++) {
236 uint64_t lVal = lset->getElement(lindex);
237 NodeValuePair nvp1(left, lVal);
238 EncodingValue *lev = map.get(&nvp1);
239 uint64_t rVal = rset->getElement(rindex);
240 NodeValuePair nvp2(right, rVal);
241 EncodingValue *rev = map.get(&nvp2);
243 ASSERT(lVal != rVal);
244 if (lev->inComparison && rev->inComparison) {
245 //Need to assign during comparison stage...
246 //Thus promote to comparison
253 lev->notequals.add(rev);
254 rev->notequals.add(lev);
261 void EncodingSubGraph::generateComparison(EncodingNode *left, EncodingNode *right) {
263 Set *rset = right->s;
264 uint lindex = 0, rindex = 0;
265 uint lSize = lset->getSize(), rSize = rset->getSize();
266 uint64_t lVal = lset->getElement(lindex);
267 NodeValuePair nvp1(left, lVal);
268 EncodingValue *lev = map.get(&nvp1);
269 lev->inComparison = true;
270 uint64_t rVal = rset->getElement(rindex);
271 NodeValuePair nvp2(right, rVal);
272 EncodingValue *rev = map.get(&nvp2);
273 rev->inComparison = true;
274 EncodingValue *last = NULL;
276 while (lindex < lSize || rindex < rSize) {
280 if (rev != NULL && lev != rev)
285 (lev != NULL && lVal < rVal)) {
289 if (++lindex < lSize) {
290 lVal = lset->getElement(lindex);
291 NodeValuePair nvpl(left, lVal);
292 lev = map.get(&nvpl);
293 lev->inComparison = true;
300 if (++rindex < rSize) {
301 rVal = rset->getElement(rindex);
302 NodeValuePair nvpr(right, rVal);
303 rev = map.get(&nvpr);
304 rev->inComparison = true;
310 if (++lindex < lSize) {
311 lVal = lset->getElement(lindex);
312 NodeValuePair nvpl(left, lVal);
313 lev = map.get(&nvpl);
314 lev->inComparison = true;
318 if (++rindex < rSize) {
319 rVal = rset->getElement(rindex);
320 NodeValuePair nvpr(right, rVal);
321 rev = map.get(&nvpr);
322 rev->inComparison = true;
329 void EncodingSubGraph::computeEncodingValue() {
330 SetIteratorEncodingNode *nodeit = nodes.iterator();
331 while (nodeit->hasNext()) {
332 EncodingNode *node = nodeit->next();
334 uint setSize = set->getSize();
335 for (uint i = 0; i < setSize; i++) {
336 uint64_t val = set->getElement(i);
337 NodeValuePair nvp(node, val);
338 if (!map.contains(&nvp)) {
339 traverseValue(node, val);
346 void EncodingSubGraph::traverseValue(EncodingNode *node, uint64_t value) {
347 EncodingValue *ecv = new EncodingValue(value);
349 HashsetEncodingNode discovered;
350 Vector<EncodingNode *> tovisit;
352 discovered.add(node);
353 while (tovisit.getSize() != 0) {
354 EncodingNode *n = tovisit.last();tovisit.pop();
355 //Add encoding node to structures
356 NodeValuePair *nvp = new NodeValuePair(n, value);
357 if(map.contains(nvp))
361 ASSERT(node != NULL);
362 SetIteratorEncodingEdge *edgeit = n->edges.iterator();
363 while (edgeit->hasNext()) {
364 EncodingEdge *ee = edgeit->next();
365 if (!discovered.contains(ee->left) && nodes.contains(ee->left) && ee->left->s->exists(value)) {
366 tovisit.push(ee->left);
367 discovered.add(ee->left);
368 ASSERT(discovered.contains(ee->left));
370 if (!discovered.contains(ee->right) && nodes.contains(ee->right) && ee->right->s->exists(value)) {
371 tovisit.push(ee->right);
372 discovered.add(ee->right);
373 ASSERT(discovered.contains(ee->right));