2 #include "encodinggraph.h"
6 EncodingSubGraph::EncodingSubGraph() :
12 uint hashNodeValuePair(NodeValuePair *nvp) {
13 return (uint) (nvp->value ^ ((uintptr_t)nvp->node));
16 bool equalsNodeValuePair(NodeValuePair *nvp1, NodeValuePair *nvp2) {
17 return nvp1->value == nvp2->value && nvp1->node == nvp2->node;
20 int sortEncodingValue(const void *p1, const void *p2) {
21 const EncodingValue *e1 = *(const EncodingValue **) p1;
22 const EncodingValue *e2 = *(const EncodingValue **) p2;
23 uint se1 = e1->notequals.getSize();
24 uint se2 = e2->notequals.getSize();
33 uint EncodingSubGraph::getEncoding(EncodingNode *n, uint64_t val) {
34 NodeValuePair nvp(n, val);
35 EncodingValue *ev = map.get(&nvp);
39 void EncodingSubGraph::solveEquals() {
40 Vector<EncodingValue *> toEncode;
41 Vector<bool> encodingArray;
42 SetIteratorEncodingValue *valIt = values.iterator();
43 while (valIt->hasNext()) {
44 EncodingValue *ev = valIt->next();
45 if (!ev->inComparison)
51 bsdqsort(toEncode.expose(), toEncode.getSize(), sizeof(EncodingValue *), sortEncodingValue);
52 uint toEncodeSize = toEncode.getSize();
53 for (uint i = 0; i < toEncodeSize; i++) {
54 EncodingValue *ev = toEncode.get(i);
55 encodingArray.clear();
56 SetIteratorEncodingValue *conflictIt = ev->notequals.iterator();
57 while (conflictIt->hasNext()) {
58 EncodingValue *conflict = conflictIt->next();
59 if (conflict->assigned) {
60 encodingArray.setExpand(conflict->encoding, true);
65 for (; encoding < encodingArray.getSize(); encoding++) {
66 //See if this is unassigned
67 if (!encodingArray.get(encoding))
70 if (encoding > maxEncodingVal)
71 maxEncodingVal = encoding;
72 ev->encoding = encoding;
77 void EncodingSubGraph::solveComparisons() {
78 HashsetEncodingValue discovered;
79 Vector<EncodingValue *> tovisit;
80 SetIteratorEncodingValue *valIt = values.iterator();
81 while (valIt->hasNext()) {
82 EncodingValue *ev = valIt->next();
83 if (discovered.add(ev)) {
85 while (tovisit.getSize() != 0) {
86 EncodingValue *val = tovisit.last(); tovisit.pop();
87 SetIteratorEncodingValue *nextIt = val->larger.iterator();
88 uint minVal = val->encoding + 1;
89 while (nextIt->hasNext()) {
90 EncodingValue *nextVal = nextIt->next();
91 if (nextVal->encoding < minVal) {
92 if (minVal > maxEncodingVal)
93 maxEncodingVal = minVal;
94 nextVal->encoding = minVal;
95 discovered.add(nextVal);
96 tovisit.push(nextVal);
106 uint EncodingSubGraph::estimateNewSize(EncodingSubGraph *sg) {
108 SetIteratorEncodingNode *nit = sg->nodes.iterator();
109 while (nit->hasNext()) {
110 EncodingNode *en = nit->next();
111 uint size = estimateNewSize(en);
119 uint EncodingSubGraph::estimateNewSize(EncodingNode *n) {
120 SetIteratorEncodingEdge *eeit = n->edges.iterator();
121 uint newsize = n->getSize();
122 while (eeit->hasNext()) {
123 EncodingEdge *ee = eeit->next();
124 if (ee->left != NULL && ee->left != n && nodes.contains(ee->left)) {
125 uint intersectSize = n->s->getUnionSize(ee->left->s);
126 if (intersectSize > newsize)
127 newsize = intersectSize;
129 if (ee->right != NULL && ee->right != n && nodes.contains(ee->right)) {
130 uint intersectSize = n->s->getUnionSize(ee->right->s);
131 if (intersectSize > newsize)
132 newsize = intersectSize;
134 if (ee->dst != NULL && ee->dst != n && nodes.contains(ee->dst)) {
135 uint intersectSize = n->s->getUnionSize(ee->dst->s);
136 if (intersectSize > newsize)
137 newsize = intersectSize;
144 void EncodingSubGraph::addNode(EncodingNode *n) {
146 uint newSize = estimateNewSize(n);
147 numElements += n->elements.getSize();
148 if (newSize > encodingSize)
149 encodingSize = newSize;
152 SetIteratorEncodingNode *EncodingSubGraph::nodeIterator() {
153 return nodes.iterator();
156 void EncodingSubGraph::encode() {
157 computeEncodingValue();
158 computeComparisons();
164 void EncodingSubGraph::computeEqualities() {
165 SetIteratorEncodingNode *nodeit = nodes.iterator();
166 while (nodeit->hasNext()) {
167 EncodingNode *node = nodeit->next();
168 generateEquals(node, node);
170 SetIteratorEncodingEdge *edgeit = node->edges.iterator();
171 while (edgeit->hasNext()) {
172 EncodingEdge *edge = edgeit->next();
173 //skip over comparisons as we have already handled them
174 if (edge->numComparisons != 0)
176 if (edge->numEquals == 0)
178 if (edge->left == NULL || !nodes.contains(edge->left))
180 if (edge->right == NULL || !nodes.contains(edge->right))
183 if (edge->left != node)
185 //We have a comparison edge between two nodes in the subgraph
186 //For now we don't support multiple encoding values with the same encoding....
187 //So we enforce != constraints for every Set...
188 if (edge->left != edge->right)
189 generateEquals(edge->left, edge->right);
196 void EncodingSubGraph::computeComparisons() {
197 SetIteratorEncodingNode *nodeit = nodes.iterator();
198 while (nodeit->hasNext()) {
199 EncodingNode *node = nodeit->next();
200 SetIteratorEncodingEdge *edgeit = node->edges.iterator();
201 while (edgeit->hasNext()) {
202 EncodingEdge *edge = edgeit->next();
203 if (edge->numComparisons == 0)
205 if (edge->left == NULL || !nodes.contains(edge->left))
207 if (edge->right == NULL || !nodes.contains(edge->right))
210 if (edge->left != node)
212 //We have a comparison edge between two nodes in the subgraph
213 generateComparison(edge->left, edge->right);
220 void EncodingSubGraph::orderEV(EncodingValue *earlier, EncodingValue *later) {
221 earlier->larger.add(later);
224 void EncodingSubGraph::generateEquals(EncodingNode *left, EncodingNode *right) {
226 Set *rset = right->s;
227 uint lSize = lset->getSize(), rSize = rset->getSize();
228 for (uint lindex = 0; lindex < lSize; lindex++) {
229 for (uint rindex = 0; rindex < rSize; rindex++) {
230 uint64_t lVal = lset->getElement(lindex);
231 NodeValuePair nvp1(left, lVal);
232 EncodingValue *lev = map.get(&nvp1);
233 uint64_t rVal = rset->getElement(rindex);
234 NodeValuePair nvp2(right, rVal);
235 EncodingValue *rev = map.get(&nvp2);
237 if (lev->inComparison && rev->inComparison) {
238 //Need to assign during comparison stage...
239 //Thus promote to comparison
246 lev->notequals.add(rev);
247 rev->notequals.add(lev);
254 void EncodingSubGraph::generateComparison(EncodingNode *left, EncodingNode *right) {
256 Set *rset = right->s;
257 uint lindex = 0, rindex = 0;
258 uint lSize = lset->getSize(), rSize = rset->getSize();
259 uint64_t lVal = lset->getElement(lindex);
260 NodeValuePair nvp1(left, lVal);
261 EncodingValue *lev = map.get(&nvp1);
262 lev->inComparison = true;
263 uint64_t rVal = rset->getElement(rindex);
264 NodeValuePair nvp2(right, rVal);
265 EncodingValue *rev = map.get(&nvp2);
266 rev->inComparison = true;
267 EncodingValue *last = NULL;
269 while (lindex < lSize || rindex < rSize) {
273 if (rev != NULL && lev != rev)
278 (lev != NULL && lVal < rVal)) {
282 if (++lindex < lSize) {
283 lVal = lset->getElement(lindex);
284 NodeValuePair nvpl(left, lVal);
285 lev = map.get(&nvpl);
286 lev->inComparison = true;
293 if (++rindex < rSize) {
294 rVal = rset->getElement(rindex);
295 NodeValuePair nvpr(right, rVal);
296 rev = map.get(&nvpr);
297 rev->inComparison = true;
303 if (++lindex < lSize) {
304 lVal = lset->getElement(lindex);
305 NodeValuePair nvpl(left, lVal);
306 lev = map.get(&nvpl);
307 lev->inComparison = true;
311 if (++rindex < rSize) {
312 rVal = rset->getElement(rindex);
313 NodeValuePair nvpr(right, rVal);
314 rev = map.get(&nvpr);
315 rev->inComparison = true;
322 void EncodingSubGraph::computeEncodingValue() {
323 SetIteratorEncodingNode *nodeit = nodes.iterator();
324 while (nodeit->hasNext()) {
325 EncodingNode *node = nodeit->next();
327 uint setSize = set->getSize();
328 for (uint i = 0; i < setSize; i++) {
329 uint64_t val = set->getElement(i);
330 NodeValuePair nvp(node, val);
331 if (!map.contains(&nvp)) {
332 traverseValue(node, val);
339 void EncodingSubGraph::traverseValue(EncodingNode *node, uint64_t value) {
340 EncodingValue *ecv = new EncodingValue(value);
342 HashsetEncodingNode discovered;
343 Vector<EncodingNode *> tovisit;
345 discovered.add(node);
346 while (tovisit.getSize() != 0) {
347 EncodingNode *n = tovisit.last();tovisit.pop();
348 //Add encoding node to structures
350 NodeValuePair *nvp = new NodeValuePair(n, value);
352 SetIteratorEncodingEdge *edgeit = node->edges.iterator();
353 while (edgeit->hasNext()) {
354 EncodingEdge *ee = edgeit->next();
355 if (!discovered.contains(ee->left) && nodes.contains(ee->left) && ee->left->s->exists(value)) {
356 tovisit.push(ee->left);
357 discovered.add(ee->left);
359 if (!discovered.contains(ee->right) && nodes.contains(ee->right) && ee->right->s->exists(value)) {
360 tovisit.push(ee->right);
361 discovered.add(ee->right);