/builds/2mk6rsew/0/parcoach/parcoach/src/include/parcoach/andersen/NodeFactory.h
Line | Count | Source (jump to first uncovered line) |
1 | | #ifndef ANDERSEN_NODE_FACTORY_H |
2 | | #define ANDERSEN_NODE_FACTORY_H |
3 | | |
4 | | #include "llvm/ADT/DenseMap.h" |
5 | | #include "llvm/IR/Constants.h" |
6 | | #include "llvm/IR/DataLayout.h" |
7 | | #include "llvm/IR/Function.h" |
8 | | #include "llvm/IR/Value.h" |
9 | | |
10 | | #include <vector> |
11 | | |
12 | | // AndersNode class - This class is used to represent a node in the constraint |
13 | | // graph. Due to various optimizations, it is not always the case that there is |
14 | | // always a mapping from a Node to a Value. (In particular, we add artificial |
15 | | // Node's that represent the set of pointed-to variables shared for each |
16 | | // location equivalent Node. Ordinary clients are not allowed to create |
17 | | // AndersNode objects. To guarantee index consistency, AndersNodes (and its |
18 | | // subclasses) instances should only be created through AndersNodeFactory. |
19 | | typedef unsigned NodeIndex; |
20 | | class AndersNode { |
21 | | public: |
22 | | enum AndersNodeType { VALUE_NODE, OBJ_NODE }; |
23 | | |
24 | | private: |
25 | | AndersNodeType type; |
26 | | NodeIndex idx, mergeTarget; |
27 | | llvm::Value const *value; |
28 | | AndersNode(AndersNodeType t, unsigned i, llvm::Value const *v = nullptr) |
29 | 121k | : type(t), idx(i), mergeTarget(i), value(v) {} |
30 | | |
31 | | public: |
32 | 0 | NodeIndex getIndex() const { return idx; } |
33 | 394k | llvm::Value const *getValue() const { return value; } |
34 | | |
35 | | friend class AndersNodeFactory; |
36 | | }; |
37 | | |
38 | | // This is the factory class of AndersNode |
39 | | // It use a vectors to hold all Nodes in the program |
40 | | // Since vectors may invalidate all element pointers/iterators when resizing, it |
41 | | // is impossible to return AndersNode* in public interfaces without using |
42 | | // std::unique_ptr and heap allocations. Therefore, we use plain integers to |
43 | | // represent nodes for public functions like createXXX and getXXX. This is ugly, |
44 | | // but it is efficient. |
45 | | class AndersNodeFactory { |
46 | | public: |
47 | | // The largest unsigned int is reserved for invalid index |
48 | | static unsigned const InvalidIndex; |
49 | | |
50 | | private: |
51 | | // The set of nodes |
52 | | std::vector<AndersNode> nodes; |
53 | | |
54 | | // Some special indices |
55 | | static const NodeIndex UniversalPtrIndex = 0; |
56 | | static const NodeIndex UniversalObjIndex = 1; |
57 | | static const NodeIndex NullPtrIndex = 2; |
58 | | static const NodeIndex NullObjectIndex = 3; |
59 | | |
60 | | // valueNodeMap - This map indicates the AndersNode* that a particular Value* |
61 | | // corresponds to |
62 | | llvm::DenseMap<llvm::Value const *, NodeIndex> valueNodeMap; |
63 | | |
64 | | // ObjectNodes - This map contains entries for each memory object in the |
65 | | // program: globals, alloca's and mallocs. We are able to represent them as |
66 | | // llvm::Value* because we're modeling the heap with the simplest |
67 | | // allocation-site approach |
68 | | llvm::DenseMap<llvm::Value const *, NodeIndex> objNodeMap; |
69 | | |
70 | | // returnMap - This map contains an entry for each function in the program |
71 | | // that returns a ptr. |
72 | | llvm::DenseMap<llvm::Function const *, NodeIndex> returnMap; |
73 | | |
74 | | // varargMap - This map contains the entry used to represent all pointers |
75 | | // passed through the varargs portion of a function call for a particular |
76 | | // function. An entry is not present in this map for functions that do not |
77 | | // take variable arguments. |
78 | | llvm::DenseMap<llvm::Function const *, NodeIndex> varargMap; |
79 | | |
80 | | public: |
81 | | AndersNodeFactory(); |
82 | | |
83 | | // Factory methods |
84 | | NodeIndex createValueNode(llvm::Value const *val = nullptr); |
85 | | NodeIndex createObjectNode(llvm::Value const *val = nullptr); |
86 | | NodeIndex createReturnNode(llvm::Function const *f); |
87 | | NodeIndex createVarargNode(llvm::Function const *f); |
88 | | |
89 | | // Map lookup interfaces (return InvalidIndex if value not found) |
90 | | NodeIndex getValueNodeFor(llvm::Value const *val) const; |
91 | | NodeIndex getValueNodeForConstant(llvm::Constant const *c) const; |
92 | | NodeIndex getObjectNodeFor(llvm::Value const *val) const; |
93 | | NodeIndex getObjectNodeForConstant(llvm::Constant const *c) const; |
94 | | NodeIndex getReturnNodeFor(llvm::Function const *f) const; |
95 | | NodeIndex getVarargNodeFor(llvm::Function const *f) const; |
96 | | |
97 | | // Node merge interfaces |
98 | | void mergeNode(NodeIndex n0, NodeIndex n1); // Merge n1 into n0 |
99 | | NodeIndex getMergeTarget(NodeIndex n); |
100 | | NodeIndex getMergeTarget(NodeIndex n) const; |
101 | | |
102 | | // Pointer arithmetic |
103 | 0 | bool isObjectNode(NodeIndex i) const { |
104 | 0 | return (nodes.at(i).type == AndersNode::OBJ_NODE); |
105 | 0 | } |
106 | 0 | NodeIndex getOffsetObjectNode(NodeIndex n, unsigned offset) const { |
107 | 0 | assert(isObjectNode(n + offset)); |
108 | 0 | return n + offset; |
109 | 0 | } |
110 | | |
111 | | // Special node getters |
112 | 305k | NodeIndex getUniversalPtrNode() const { return UniversalPtrIndex; } |
113 | 11.6k | NodeIndex getUniversalObjNode() const { return UniversalObjIndex; } |
114 | 2.58k | NodeIndex getNullPtrNode() const { return NullPtrIndex; } |
115 | 396k | NodeIndex getNullObjectNode() const { return NullObjectIndex; } |
116 | | |
117 | | // Value getters |
118 | 394k | llvm::Value const *getValueForNode(NodeIndex i) const { |
119 | 394k | return nodes.at(i).getValue(); |
120 | 394k | } |
121 | | void getAllocSites(std::vector<llvm::Value const *> &) const; |
122 | | |
123 | | // Value remover |
124 | 0 | void removeNodeForValue(llvm::Value const *val) { valueNodeMap.erase(val); } |
125 | | |
126 | | // Size getters |
127 | 37.5k | unsigned getNumNodes() const { return nodes.size(); } |
128 | | #ifndef NDEBUG |
129 | | // For debugging purpose |
130 | | void dumpNode(NodeIndex) const; |
131 | | void dumpNodeInfo() const; |
132 | | void dumpRepInfo() const; |
133 | | #endif |
134 | | }; |
135 | | |
136 | | #endif |