Off by 1 bug
[satune.git] / src / ASTAnalyses / Encoding / subgraph.h
1 #ifndef SUBGRAPH_H
2 #define SUBGRAPH_H
3 #include "classlist.h"
4 #include "structs.h"
5 #include "graphstructs.h"
6
7 class NodeValuePair {
8 public:
9         NodeValuePair(EncodingNode *n, uint64_t val) : node(n), value(val) {}
10         EncodingNode *node;
11         uint64_t value;
12 };
13
14 class EncodingValue;
15
16 typedef Hashset<EncodingValue *, uintptr_t, PTRSHIFT> HashsetEncodingValue;
17 typedef SetIterator<EncodingValue *, uintptr_t, PTRSHIFT> SetIteratorEncodingValue;
18
19 class EncodingValue {
20 public:
21         EncodingValue(uint64_t _val) : value(_val), encoding(0), inComparison(false), assigned(false) {}
22         void merge(EncodingValue *value);
23         uint64_t value;
24         uint encoding;
25         bool inComparison;
26         bool assigned;
27         HashsetEncodingNode nodes;
28         HashsetEncodingValue larger;
29         HashsetEncodingValue notequals;
30 };
31
32 uint hashNodeValuePair(NodeValuePair *nvp);
33 bool equalsNodeValuePair(NodeValuePair *nvp1, NodeValuePair *nvp2);
34
35 typedef Hashtable<NodeValuePair *, EncodingValue *, uintptr_t, 0, hashNodeValuePair, equalsNodeValuePair> NVPMap;
36
37 class EncodingSubGraph {
38 public:
39         EncodingSubGraph();
40         void addNode(EncodingNode *n);
41         SetIteratorEncodingNode *nodeIterator();
42         void encode();
43         uint getEncoding(EncodingNode *n, uint64_t val);
44         uint getEncodingMaxVal(EncodingNode *n) { return maxEncodingVal;}
45
46         CMEMALLOC;
47 private:
48         uint estimateNewSize(EncodingNode *n);
49         uint estimateNewSize(EncodingSubGraph *sg);
50         void traverseValue(EncodingNode *node, uint64_t value);
51         void computeEncodingValue();
52         void computeComparisons();
53         void computeEqualities();
54         void solveComparisons();
55         void solveEquals();
56         void generateComparison(EncodingNode *left, EncodingNode *right);
57         void generateEquals(EncodingNode *left, EncodingNode *right);
58         void orderEV(EncodingValue *smaller, EncodingValue *larger);
59
60         HashsetEncodingValue values;
61         HashsetEncodingNode nodes;
62         NVPMap map;
63         uint encodingSize;
64         uint numElements;
65         uint maxEncodingVal;
66
67         friend class EncodingGraph;
68 };
69
70 #endif