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 if (conflict->assigned) {
65 encodingArray.setExpand(conflict->encoding, true);
70 for (; encoding < encodingArray.getSize(); encoding++) {
71 //See if this is unassigned
72 if (!encodingArray.get(encoding))
75 if (encoding > maxEncodingVal)
76 maxEncodingVal = encoding;
77 ev->encoding = encoding;
82 void EncodingSubGraph::solveComparisons() {
83 HashsetEncodingValue discovered;
84 Vector<EncodingValue *> tovisit;
85 SetIteratorEncodingValue *valIt = values.iterator();
86 while (valIt->hasNext()) {
87 EncodingValue *ev = valIt->next();
88 if (discovered.add(ev)) {
90 while (tovisit.getSize() != 0) {
91 EncodingValue *val = tovisit.last(); tovisit.pop();
92 SetIteratorEncodingValue *nextIt = val->larger.iterator();
93 uint minVal = val->encoding + 1;
94 while (nextIt->hasNext()) {
95 EncodingValue *nextVal = nextIt->next();
96 if (nextVal->encoding < minVal) {
97 if (minVal > maxEncodingVal)
98 maxEncodingVal = minVal;
99 nextVal->encoding = minVal;
100 discovered.add(nextVal);
101 tovisit.push(nextVal);
111 uint EncodingSubGraph::estimateNewSize(EncodingSubGraph *sg) {
113 SetIteratorEncodingNode *nit = sg->nodes.iterator();
114 while (nit->hasNext()) {
115 EncodingNode *en = nit->next();
116 uint size = estimateNewSize(en);
124 uint EncodingSubGraph::estimateNewSize(EncodingNode *n) {
125 SetIteratorEncodingEdge *eeit = n->edges.iterator();
126 uint newsize = n->getSize();
127 while (eeit->hasNext()) {
128 EncodingEdge *ee = eeit->next();
129 if (ee->left != NULL && ee->left != n && nodes.contains(ee->left)) {
130 uint intersectSize = n->s->getUnionSize(ee->left->s);
131 if (intersectSize > newsize)
132 newsize = intersectSize;
134 if (ee->right != NULL && ee->right != n && nodes.contains(ee->right)) {
135 uint intersectSize = n->s->getUnionSize(ee->right->s);
136 if (intersectSize > newsize)
137 newsize = intersectSize;
139 if (ee->dst != NULL && ee->dst != n && nodes.contains(ee->dst)) {
140 uint intersectSize = n->s->getUnionSize(ee->dst->s);
141 if (intersectSize > newsize)
142 newsize = intersectSize;
149 void EncodingSubGraph::addNode(EncodingNode *n) {
151 uint newSize = estimateNewSize(n);
152 numElements += n->elements.getSize();
153 if (newSize > encodingSize)
154 encodingSize = newSize;
157 SetIteratorEncodingNode *EncodingSubGraph::nodeIterator() {
158 return nodes.iterator();
161 void EncodingSubGraph::encode() {
162 computeEncodingValue();
163 computeComparisons();
169 void EncodingSubGraph::computeEqualities() {
170 SetIteratorEncodingNode *nodeit = nodes.iterator();
171 while (nodeit->hasNext()) {
172 EncodingNode *node = nodeit->next();
173 generateEquals(node, node);
175 SetIteratorEncodingEdge *edgeit = node->edges.iterator();
176 while (edgeit->hasNext()) {
177 EncodingEdge *edge = edgeit->next();
178 //skip over comparisons as we have already handled them
179 if (edge->numComparisons != 0)
181 if (edge->numEquals == 0)
183 if (edge->left == NULL || !nodes.contains(edge->left))
185 if (edge->right == NULL || !nodes.contains(edge->right))
188 if (edge->left != node)
190 //We have a comparison edge between two nodes in the subgraph
191 //For now we don't support multiple encoding values with the same encoding....
192 //So we enforce != constraints for every Set...
193 if (edge->left != edge->right)
194 generateEquals(edge->left, edge->right);
201 void EncodingSubGraph::computeComparisons() {
202 SetIteratorEncodingNode *nodeit = nodes.iterator();
203 while (nodeit->hasNext()) {
204 EncodingNode *node = nodeit->next();
205 SetIteratorEncodingEdge *edgeit = node->edges.iterator();
206 while (edgeit->hasNext()) {
207 EncodingEdge *edge = edgeit->next();
208 if (edge->numComparisons == 0)
210 if (edge->left == NULL || !nodes.contains(edge->left))
212 if (edge->right == NULL || !nodes.contains(edge->right))
215 if (edge->left != node)
217 //We have a comparison edge between two nodes in the subgraph
218 generateComparison(edge->left, edge->right);
225 void EncodingSubGraph::orderEV(EncodingValue *earlier, EncodingValue *later) {
226 earlier->larger.add(later);
229 void EncodingSubGraph::generateEquals(EncodingNode *left, EncodingNode *right) {
231 Set *rset = right->s;
232 uint lSize = lset->getSize(), rSize = rset->getSize();
233 for (uint lindex = 0; lindex < lSize; lindex++) {
234 for (uint rindex = 0; rindex < rSize; rindex++) {
235 uint64_t lVal = lset->getElement(lindex);
236 NodeValuePair nvp1(left, lVal);
237 EncodingValue *lev = map.get(&nvp1);
238 uint64_t rVal = rset->getElement(rindex);
239 NodeValuePair nvp2(right, rVal);
240 EncodingValue *rev = map.get(&nvp2);
242 if (lev->inComparison && rev->inComparison) {
243 //Need to assign during comparison stage...
244 //Thus promote to comparison
251 lev->notequals.add(rev);
252 rev->notequals.add(lev);
259 void EncodingSubGraph::generateComparison(EncodingNode *left, EncodingNode *right) {
261 Set *rset = right->s;
262 uint lindex = 0, rindex = 0;
263 uint lSize = lset->getSize(), rSize = rset->getSize();
264 uint64_t lVal = lset->getElement(lindex);
265 NodeValuePair nvp1(left, lVal);
266 EncodingValue *lev = map.get(&nvp1);
267 lev->inComparison = true;
268 uint64_t rVal = rset->getElement(rindex);
269 NodeValuePair nvp2(right, rVal);
270 EncodingValue *rev = map.get(&nvp2);
271 rev->inComparison = true;
272 EncodingValue *last = NULL;
274 while (lindex < lSize || rindex < rSize) {
278 if (rev != NULL && lev != rev)
283 (lev != NULL && lVal < rVal)) {
287 if (++lindex < lSize) {
288 lVal = lset->getElement(lindex);
289 NodeValuePair nvpl(left, lVal);
290 lev = map.get(&nvpl);
291 lev->inComparison = true;
298 if (++rindex < rSize) {
299 rVal = rset->getElement(rindex);
300 NodeValuePair nvpr(right, rVal);
301 rev = map.get(&nvpr);
302 rev->inComparison = true;
308 if (++lindex < lSize) {
309 lVal = lset->getElement(lindex);
310 NodeValuePair nvpl(left, lVal);
311 lev = map.get(&nvpl);
312 lev->inComparison = true;
316 if (++rindex < rSize) {
317 rVal = rset->getElement(rindex);
318 NodeValuePair nvpr(right, rVal);
319 rev = map.get(&nvpr);
320 rev->inComparison = true;
327 void EncodingSubGraph::computeEncodingValue() {
328 SetIteratorEncodingNode *nodeit = nodes.iterator();
329 while (nodeit->hasNext()) {
330 EncodingNode *node = nodeit->next();
332 uint setSize = set->getSize();
333 for (uint i = 0; i < setSize; i++) {
334 uint64_t val = set->getElement(i);
335 NodeValuePair nvp(node, val);
336 if (!map.contains(&nvp)) {
337 traverseValue(node, val);
344 void EncodingSubGraph::traverseValue(EncodingNode *node, uint64_t value) {
345 EncodingValue *ecv = new EncodingValue(value);
347 HashsetEncodingNode discovered;
348 Vector<EncodingNode *> tovisit;
350 discovered.add(node);
351 while (tovisit.getSize() != 0) {
352 EncodingNode *n = tovisit.last();tovisit.pop();
353 //Add encoding node to structures
355 NodeValuePair *nvp = new NodeValuePair(n, value);
357 SetIteratorEncodingEdge *edgeit = node->edges.iterator();
358 while (edgeit->hasNext()) {
359 EncodingEdge *ee = edgeit->next();
360 if (!discovered.contains(ee->left) && nodes.contains(ee->left) && ee->left->s->exists(value)) {
361 tovisit.push(ee->left);
362 discovered.add(ee->left);
364 if (!discovered.contains(ee->right) && nodes.contains(ee->right) && ee->right->s->exists(value)) {
365 tovisit.push(ee->right);
366 discovered.add(ee->right);