/builds/2mk6rsew/0/parcoach/parcoach/src/aSSA/andersen/NodeFactory.cpp

Source (jump to first uncovered line)
#include "parcoach/andersen/NodeFactory.h"

#include "llvm/ADT/SmallVector.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/Constants.h"
#include "llvm/Support/raw_ostream.h"

#include <limits>

using namespace llvm;

unsigned const AndersNodeFactory::InvalidIndex =
    std::numeric_limits<unsigned int>::max();

AndersNodeFactory::AndersNodeFactory() {
  // Note that we can't use std::vector::emplace_back() here because
  // AndersNode's constructors are private hence std::vector cannot see it

  // Node #0 is always the universal ptr: the ptr that we don't know anything
  // about.
  nodes.push_back(AndersNode(AndersNode::VALUE_NODE, 0));
  // Node #0 is always the universal obj: the obj that we don't know anything
  // about.
  nodes.push_back(AndersNode(AndersNode::OBJ_NODE, 1));
  // Node #2 always represents the null pointer.
  nodes.push_back(AndersNode(AndersNode::VALUE_NODE, 2));
  // Node #3 is the object that null pointer points to
  nodes.push_back(AndersNode(AndersNode::OBJ_NODE, 3));

  assert(nodes.size() == 4);
}

NodeIndex AndersNodeFactory::createValueNode(Value const *Val) {
  // errs() << "inserting " << *val << "\n";
  unsigned NextIdx = nodes.size();
  nodes.push_back(AndersNode(AndersNode::VALUE_NODE, NextIdx, Val));
  if (Val != nullptr) {
    assert(!valueNodeMap.count(Val) &&
           "Trying to insert two mappings to revValueNodeMap!");
    valueNodeMap[Val] = NextIdx;
  }

  return NextIdx;
}

NodeIndex AndersNodeFactory::createObjectNode(Value const *Val) {
  unsigned NextIdx = nodes.size();
  nodes.push_back(AndersNode(AndersNode::OBJ_NODE, NextIdx, Val));
  if (Val != nullptr) {
    assert(!objNodeMap.count(Val) &&
           "Trying to insert two mappings to revObjNodeMap!");
    objNodeMap[Val] = NextIdx;
  }

  return NextIdx;
}

NodeIndex AndersNodeFactory::createReturnNode(llvm::Function const *F) {
  unsigned NextIdx = nodes.size();
  nodes.push_back(AndersNode(AndersNode::VALUE_NODE, NextIdx, F));

  assert(!returnMap.count(F) && "Trying to insert two mappings to returnMap!");
  returnMap[F] = NextIdx;

  return NextIdx;
}

NodeIndex AndersNodeFactory::createVarargNode(llvm::Function const *F) {
  unsigned NextIdx = nodes.size();
  nodes.push_back(AndersNode(AndersNode::OBJ_NODE, NextIdx, F));

  assert(!varargMap.count(F) && "Trying to insert two mappings to varargMap!");
  varargMap[F] = NextIdx;

  return NextIdx;
}

NodeIndex AndersNodeFactory::getValueNodeFor(Value const *Val) const {
  if (Constant const *C = dyn_cast<Constant>(Val)) {
    if (!isa<GlobalValue>(C)) {
      return getValueNodeForConstant(C);
    }
  }

  // errs() << "looking up " << *val << "\n";
  auto ItV = valueNodeMap.find(Val);
  if (ItV == valueNodeMap.end()) {
    return InvalidIndex;
  }
  return ItV->second;
}

NodeIndex
AndersNodeFactory::getValueNodeForConstant(llvm::Constant const *C) const {
  assert(isa<PointerType>(C->getType()) && "Not a constant pointer!");

  if (isa<ConstantPointerNull>(C) || isa<UndefValue>(C)) {
    return getNullPtrNode();
  }
  if (GlobalValue const *GV = dyn_cast<GlobalValue>(C)) {
    return getValueNodeFor(GV);
  }

  if (ConstantExpr const *CE = dyn_cast<ConstantExpr>(C)) {
    switch (CE->getOpcode()) {
    // Pointer to any field within a struct is treated as a pointer to the first
    // field
    case Instruction::GetElementPtr:
      return getValueNodeFor(C->getOperand(0));
    case Instruction::IntToPtr:
    case Instruction::PtrToInt:
      return getUniversalPtrNode();
    case Instruction::BitCast:
    case Instruction::AddrSpaceCast:
      return getValueNodeForConstant(CE->getOperand(0));
    default:
      errs() << "Constant Expr not yet handled: " << *CE << "\n";
      llvm_unreachable(0);
    }
  }

  llvm_unreachable("Unknown constant pointer!");
  return InvalidIndex;
}

NodeIndex AndersNodeFactory::getObjectNodeFor(Value const *Val) const {
  if (Constant const *C = dyn_cast<Constant>(Val)) {
    if (!isa<GlobalValue>(C)) {
      return getObjectNodeForConstant(C);
    }
  }

  auto ItV = objNodeMap.find(Val);
  if (ItV == objNodeMap.end()) {
    return InvalidIndex;
  }
  return ItV->second;
}

NodeIndex
AndersNodeFactory::getObjectNodeForConstant(llvm::Constant const *C) const {
  assert(isa<PointerType>(C->getType()) && "Not a constant pointer!");

  if (isa<ConstantPointerNull>(C)) {
    return getNullObjectNode();
  }
  if (GlobalValue const *GV = dyn_cast<GlobalValue>(C)) {
    return getObjectNodeFor(GV);
  }
  if (ConstantExpr const *CE = dyn_cast<ConstantExpr>(C)) {
    switch (CE->getOpcode()) {
    // Pointer to any field within a struct is treated as a pointer to the first
    // field
    case Instruction::GetElementPtr:
      return getObjectNodeForConstant(CE->getOperand(0));
    case Instruction::IntToPtr:
    case Instruction::PtrToInt:
      return getUniversalObjNode();
    case Instruction::BitCast:
    case Instruction::AddrSpaceCast:
      return getObjectNodeForConstant(CE->getOperand(0));
    default:
      errs() << "Constant Expr not yet handled: " << *CE << "\n";
      llvm_unreachable(0);
    }
  }

  llvm_unreachable("Unknown constant pointer!");
  return InvalidIndex;
}

NodeIndex AndersNodeFactory::getReturnNodeFor(llvm::Function const *F) const {
  auto ItF = returnMap.find(F);
  if (ItF == returnMap.end()) {
    return InvalidIndex;
  }
  return ItF->second;
}

NodeIndex AndersNodeFactory::getVarargNodeFor(llvm::Function const *F) const {
  auto ItF = varargMap.find(F);
  if (ItF == varargMap.end()) {
    return InvalidIndex;
  }
  return ItF->second;
}

void AndersNodeFactory::mergeNode(NodeIndex N0, NodeIndex N1) {
  assert(N0 < nodes.size() && N1 < nodes.size());
  nodes[N1].mergeTarget = N0;
}

NodeIndex AndersNodeFactory::getMergeTarget(NodeIndex N) {
  assert(N < nodes.size());
  NodeIndex Ret = nodes[N].mergeTarget;
  if (Ret != N) {
    std::vector<NodeIndex> Path(1, N);
    while (Ret != nodes[Ret].mergeTarget) {
      Path.push_back(Ret);
      Ret = nodes[Ret].mergeTarget;
    }
    for (auto Idx : Path) {
      nodes[Idx].mergeTarget = Ret;
    }
  }
  assert(Ret < nodes.size());
  return Ret;
}

NodeIndex AndersNodeFactory::getMergeTarget(NodeIndex N) const {
  assert(N < nodes.size());
  NodeIndex Ret = nodes[N].mergeTarget;
  while (Ret != nodes[Ret].mergeTarget) {
    Ret = nodes[Ret].mergeTarget;
  }
  return Ret;
}

void AndersNodeFactory::getAllocSites(
    std::vector<llvm::Value const *> &AllocSites) const {
  AllocSites.clear();
  AllocSites.reserve(objNodeMap.size());
  for (auto const &Mapping : objNodeMap) {
    AllocSites.push_back(Mapping.first);
  }
}

#ifndef NDEBUG
void AndersNodeFactory::dumpNode(NodeIndex Idx) const {
  AndersNode const &N = nodes.at(Idx);
  if (N.type == AndersNode::VALUE_NODE) {
    errs() << "[V ";
  } else if (N.type == AndersNode::OBJ_NODE) {
    errs() << "[O ";
  } else {
    assert(false && "Wrong type number!");
  }
  errs() << "#" << N.idx << "]";
}

void AndersNodeFactory::dumpNodeInfo() const {
  errs() << "\n----- Print AndersNodeFactory Info -----\n";
  for (auto const &Node : nodes) {
    dumpNode(Node.getIndex());
    errs() << ", val = ";
    Value const *Val = Node.getValue();
    if (Val == nullptr) {
      errs() << "nullptr";
    } else if (isa<Function>(Val)) {
      errs() << "  <func> " << Val->getName();
    } else {
      errs() << *Val;
    }
    errs() << "\n";
  }

  errs() << "\nReturn Map:\n";
  for (auto const &Mapping : returnMap) {
    errs() << Mapping.first->getName() << "  -->>  [Node #" << Mapping.second
           << "]\n";
  }
  errs() << "\nVararg Map:\n";
  for (auto const &Mapping : varargMap) {
    errs() << Mapping.first->getName() << "  -->>  [Node #" << Mapping.second
           << "]\n";
  }
  errs() << "----- End of Print -----\n";
}

void AndersNodeFactory::dumpRepInfo() const {
  errs() << "\n----- Print Node Merge Info -----\n";
  for (NodeIndex I = 0, E = nodes.size(); I < E; ++I) {
    NodeIndex Rep = getMergeTarget(I);
    if (Rep != I) {
      errs() << I << " -> " << Rep << "\n";
    }
  }
  errs() << "----- End of Print -----\n";
}
#endif

Coverage Report

Created: 2023-10-30 17:15

Line	Count	Source (jump to first uncovered line)
1		#include "parcoach/andersen/NodeFactory.h"
2
3		#include "llvm/ADT/SmallVector.h"
4		#include "llvm/Analysis/ValueTracking.h"
5		#include "llvm/IR/Constants.h"
6		#include "llvm/Support/raw_ostream.h"
7
8		#include <limits>
9
10		using namespace llvm;
11
12		unsigned const AndersNodeFactory::InvalidIndex =
13		std::numeric_limits<unsigned int>::max();
14
15	1.76k	AndersNodeFactory::AndersNodeFactory() {
16		// Note that we can't use std::vector::emplace_back() here because
17		// AndersNode's constructors are private hence std::vector cannot see it
18
19		// Node #0 is always the universal ptr: the ptr that we don't know anything
20		// about.
21	1.76k	nodes.push_back(AndersNode(AndersNode::VALUE_NODE, 0));
22		// Node #0 is always the universal obj: the obj that we don't know anything
23		// about.
24	1.76k	nodes.push_back(AndersNode(AndersNode::OBJ_NODE, 1));
25		// Node #2 always represents the null pointer.
26	1.76k	nodes.push_back(AndersNode(AndersNode::VALUE_NODE, 2));
27		// Node #3 is the object that null pointer points to
28	1.76k	nodes.push_back(AndersNode(AndersNode::OBJ_NODE, 3));
29
30	1.76k	assert(nodes.size() == 4);
31	1.76k	}
32
33	72.0k	NodeIndex AndersNodeFactory::createValueNode(Value const *Val) {
34		// errs() << "inserting " << *val << "\n";
35	72.0k	unsigned NextIdx = nodes.size();
36	72.0k	nodes.push_back(AndersNode(AndersNode::VALUE_NODE, NextIdx, Val));
37	72.0k	if (Val != nullptr) {
38	72.0k	assert(!valueNodeMap.count(Val) &&
39	72.0k	"Trying to insert two mappings to revValueNodeMap!");
40	72.0k	valueNodeMap[Val] = NextIdx;
41	72.0k	}
42
43	72.0k	return NextIdx;
44	72.0k	}
45
46	42.3k	NodeIndex AndersNodeFactory::createObjectNode(Value const *Val) {
47	42.3k	unsigned NextIdx = nodes.size();
48	42.3k	nodes.push_back(AndersNode(AndersNode::OBJ_NODE, NextIdx, Val));
49	42.3k	if (Val != nullptr) {
50	42.3k	assert(!objNodeMap.count(Val) &&
51	42.3k	"Trying to insert two mappings to revObjNodeMap!");
52	42.3k	objNodeMap[Val] = NextIdx;
53	42.3k	}
54
55	42.3k	return NextIdx;
56	42.3k	}
57
58	0	NodeIndex AndersNodeFactory::createReturnNode(llvm::Function const *F) {
59	0	unsigned NextIdx = nodes.size();
60	0	nodes.push_back(AndersNode(AndersNode::VALUE_NODE, NextIdx, F));
61
62	0	assert(!returnMap.count(F) && "Trying to insert two mappings to returnMap!");
63	0	returnMap[F] = NextIdx;
64
65	0	return NextIdx;
66	0	}
67
68	0	NodeIndex AndersNodeFactory::createVarargNode(llvm::Function const *F) {
69	0	unsigned NextIdx = nodes.size();
70	0	nodes.push_back(AndersNode(AndersNode::OBJ_NODE, NextIdx, F));
71
72	0	assert(!varargMap.count(F) && "Trying to insert two mappings to varargMap!");
73	0	varargMap[F] = NextIdx;
74
75	0	return NextIdx;
76	0	}
77
78	411k	NodeIndex AndersNodeFactory::getValueNodeFor(Value const *Val) const {
79	411k	if (Constant const *C = dyn_cast<Constant>(Val)) {
80	29.7k	if (!isa<GlobalValue>(C)) {
81	824	return getValueNodeForConstant(C);
82	824	}
83	29.7k	}
84
85		// errs() << "looking up " << *val << "\n";
86	411k	auto ItV = valueNodeMap.find(Val);
87	411k	if (ItV == valueNodeMap.end()) {
88	22	return InvalidIndex;
89	22	}
90	411k	return ItV->second;
91	411k	}
92
93		NodeIndex
94	824	AndersNodeFactory::getValueNodeForConstant(llvm::Constant const *C) const {
95	824	assert(isa<PointerType>(C->getType()) && "Not a constant pointer!");
96
97	824	if (isa<ConstantPointerNull>(C) \|\| isa<UndefValue>(C)) {
98	824	return getNullPtrNode();
99	824	}
100	0	if (GlobalValue const *GV = dyn_cast<GlobalValue>(C)) {
101	0	return getValueNodeFor(GV);
102	0	}
103
104	0	if (ConstantExpr const *CE = dyn_cast<ConstantExpr>(C)) {
105	0	switch (CE->getOpcode()) {
106		// Pointer to any field within a struct is treated as a pointer to the first
107		// field
108	0	case Instruction::GetElementPtr:
109	0	return getValueNodeFor(C->getOperand(0));
110	0	case Instruction::IntToPtr:
111	0	case Instruction::PtrToInt:
112	0	return getUniversalPtrNode();
113	0	case Instruction::BitCast:
114	0	case Instruction::AddrSpaceCast:
115	0	return getValueNodeForConstant(CE->getOperand(0));
116	0	default:
117	0	errs() << "Constant Expr not yet handled: " << *CE << "\n";
118	0	llvm_unreachable(0);
119	0	}
120	0	}
121
122	0	llvm_unreachable("Unknown constant pointer!");
123	0	return InvalidIndex;
124	0	}
125
126	11.6k	NodeIndex AndersNodeFactory::getObjectNodeFor(Value const *Val) const {
127	11.6k	if (Constant const *C = dyn_cast<Constant>(Val)) {
128	11.6k	if (!isa<GlobalValue>(C)) {
129	0	return getObjectNodeForConstant(C);
130	0	}
131	11.6k	}
132
133	11.6k	auto ItV = objNodeMap.find(Val);
134	11.6k	if (ItV == objNodeMap.end()) {
135	0	return InvalidIndex;
136	0	}
137	11.6k	return ItV->second;
138	11.6k	}
139
140		NodeIndex
141	50	AndersNodeFactory::getObjectNodeForConstant(llvm::Constant const *C) const {
142	50	assert(isa<PointerType>(C->getType()) && "Not a constant pointer!");
143
144	50	if (isa<ConstantPointerNull>(C)) {
145	0	return getNullObjectNode();
146	0	}
147	50	if (GlobalValue const *GV = dyn_cast<GlobalValue>(C)) {
148	50	return getObjectNodeFor(GV);
149	50	}
150	0	if (ConstantExpr const *CE = dyn_cast<ConstantExpr>(C)) {
151	0	switch (CE->getOpcode()) {
152		// Pointer to any field within a struct is treated as a pointer to the first
153		// field
154	0	case Instruction::GetElementPtr:
155	0	return getObjectNodeForConstant(CE->getOperand(0));
156	0	case Instruction::IntToPtr:
157	0	case Instruction::PtrToInt:
158	0	return getUniversalObjNode();
159	0	case Instruction::BitCast:
160	0	case Instruction::AddrSpaceCast:
161	0	return getObjectNodeForConstant(CE->getOperand(0));
162	0	default:
163	0	errs() << "Constant Expr not yet handled: " << *CE << "\n";
164	0	llvm_unreachable(0);
165	0	}
166	0	}
167
168	0	llvm_unreachable("Unknown constant pointer!");
169	0	return InvalidIndex;
170	0	}
171
172	0	NodeIndex AndersNodeFactory::getReturnNodeFor(llvm::Function const *F) const {
173	0	auto ItF = returnMap.find(F);
174	0	if (ItF == returnMap.end()) {
175	0	return InvalidIndex;
176	0	}
177	0	return ItF->second;
178	0	}
179
180	0	NodeIndex AndersNodeFactory::getVarargNodeFor(llvm::Function const *F) const {
181	0	auto ItF = varargMap.find(F);
182	0	if (ItF == varargMap.end()) {
183	0	return InvalidIndex;
184	0	}
185	0	return ItF->second;
186	0	}
187
188	0	void AndersNodeFactory::mergeNode(NodeIndex N0, NodeIndex N1) {
189	0	assert(N0 < nodes.size() && N1 < nodes.size());
190	0	nodes[N1].mergeTarget = N0;
191	0	}
192
193	916k	NodeIndex AndersNodeFactory::getMergeTarget(NodeIndex N) {
194	916k	assert(N < nodes.size());
195	916k	NodeIndex Ret = nodes[N].mergeTarget;
196	916k	if (Ret != N) {
197	0	std::vector<NodeIndex> Path(1, N);
198	0	while (Ret != nodes[Ret].mergeTarget) {
199	0	Path.push_back(Ret);
200	0	Ret = nodes[Ret].mergeTarget;
201	0	}
202	0	for (auto Idx : Path) {
203	0	nodes[Idx].mergeTarget = Ret;
204	0	}
205	0	}
206	916k	assert(Ret < nodes.size());
207	916k	return Ret;
208	916k	}
209
210	256k	NodeIndex AndersNodeFactory::getMergeTarget(NodeIndex N) const {
211	256k	assert(N < nodes.size());
212	256k	NodeIndex Ret = nodes[N].mergeTarget;
213	256k	while (Ret != nodes[Ret].mergeTarget) {
214	0	Ret = nodes[Ret].mergeTarget;
215	0	}
216	256k	return Ret;
217	256k	}
218
219		void AndersNodeFactory::getAllocSites(
220	3.52k	std::vector<llvm::Value const *> &AllocSites) const {
221	3.52k	AllocSites.clear();
222	3.52k	AllocSites.reserve(objNodeMap.size());
223	84.6k	for (auto const &Mapping : objNodeMap) {
224	84.6k	AllocSites.push_back(Mapping.first);
225	84.6k	}
226	3.52k	}
227
228		#ifndef NDEBUG
229		void AndersNodeFactory::dumpNode(NodeIndex Idx) const {
230		AndersNode const &N = nodes.at(Idx);
231		if (N.type == AndersNode::VALUE_NODE) {
232		errs() << "[V ";
233		} else if (N.type == AndersNode::OBJ_NODE) {
234		errs() << "[O ";
235		} else {
236		assert(false && "Wrong type number!");
237		}
238		errs() << "#" << N.idx << "]";
239		}
240
241		void AndersNodeFactory::dumpNodeInfo() const {
242		errs() << "\n----- Print AndersNodeFactory Info -----\n";
243		for (auto const &Node : nodes) {
244		dumpNode(Node.getIndex());
245		errs() << ", val = ";
246		Value const *Val = Node.getValue();
247		if (Val == nullptr) {
248		errs() << "nullptr";
249		} else if (isa<Function>(Val)) {
250		errs() << " <func> " << Val->getName();
251		} else {
252		errs() << *Val;
253		}
254		errs() << "\n";
255		}
256
257		errs() << "\nReturn Map:\n";
258		for (auto const &Mapping : returnMap) {
259		errs() << Mapping.first->getName() << " -->> [Node #" << Mapping.second
260		<< "]\n";
261		}
262		errs() << "\nVararg Map:\n";
263		for (auto const &Mapping : varargMap) {
264		errs() << Mapping.first->getName() << " -->> [Node #" << Mapping.second
265		<< "]\n";
266		}
267		errs() << "----- End of Print -----\n";
268		}
269
270		void AndersNodeFactory::dumpRepInfo() const {
271		errs() << "\n----- Print Node Merge Info -----\n";
272		for (NodeIndex I = 0, E = nodes.size(); I < E; ++I) {
273		NodeIndex Rep = getMergeTarget(I);
274		if (Rep != I) {
275		errs() << I << " -> " << Rep << "\n";
276		}
277		}
278		errs() << "----- End of Print -----\n";
279		}
280		#endif