Coverage Report

Created: 2023-10-30 17:15

/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