#include <algorithm>
#include <set>
#include <list>
+#include <map>
#include <stack>
#include <vector>
#include <queue>
STATISTIC(NumUnified , "Number of variables unified");
STATISTIC(NumErased , "Number of redundant constraints erased");
-namespace {
- const unsigned SelfRep = (unsigned)-1;
- const unsigned Unvisited = (unsigned)-1;
- // Position of the function return node relative to the function node.
- const unsigned CallReturnPos = 1;
- // Position of the function call node relative to the function node.
- const unsigned CallFirstArgPos = 2;
+static const unsigned SelfRep = (unsigned)-1;
+static const unsigned Unvisited = (unsigned)-1;
+// Position of the function return node relative to the function node.
+static const unsigned CallReturnPos = 1;
+// Position of the function call node relative to the function node.
+static const unsigned CallFirstArgPos = 2;
+namespace {
struct BitmapKeyInfo {
static inline SparseBitVector<> *getEmptyKey() {
return reinterpret_cast<SparseBitVector<> *>(-1);
// it's thing
struct PairKeyInfo {
static inline std::pair<unsigned, unsigned> getEmptyKey() {
- return std::make_pair(~0UL, ~0UL);
+ return std::make_pair(~0U, ~0U);
}
static inline std::pair<unsigned, unsigned> getTombstoneKey() {
- return std::make_pair(~0UL - 1, ~0UL - 1);
+ return std::make_pair(~0U - 1, ~0U - 1);
}
static unsigned getHashValue(const std::pair<unsigned, unsigned> &P) {
return P.first ^ P.second;
struct ConstraintKeyInfo {
static inline Constraint getEmptyKey() {
- return Constraint(Constraint::Copy, ~0UL, ~0UL, ~0UL);
+ return Constraint(Constraint::Copy, ~0U, ~0U, ~0U);
}
static inline Constraint getTombstoneKey() {
- return Constraint(Constraint::Copy, ~0UL - 1, ~0UL - 1, ~0UL - 1);
+ return Constraint(Constraint::Copy, ~0U - 1, ~0U - 1, ~0U - 1);
}
static unsigned getHashValue(const Constraint &C) {
return C.Src ^ C.Dest ^ C.Type ^ C.Offset;
Timestamp = Counter++;
}
- bool isRep() {
+ bool isRep() const {
return( (int) NodeRep < 0 );
}
};
public:
static char ID;
- Andersens() : ModulePass((intptr_t)&ID) {}
-
- /// isAnalysis - Return true if this pass is implementing an analysis pass.
- virtual bool isAnalysis() const { return true; }
+ Andersens() : ModulePass(&ID) {}
bool runOnModule(Module &M) {
InitializeAliasAnalysis(this);
// Free the constraints list, as we don't need it to respond to alias
// requests.
- ObjectNodes.clear();
- ReturnNodes.clear();
- VarargNodes.clear();
std::vector<Constraint>().swap(Constraints);
+ //These are needed for Print() (-analyze in opt)
+ //ObjectNodes.clear();
+ //ReturnNodes.clear();
+ //VarargNodes.clear();
return false;
}
/// getObject - Return the node corresponding to the memory object for the
/// specified global or allocation instruction.
- unsigned getObject(Value *V) {
+ unsigned getObject(Value *V) const {
DenseMap<Value*, unsigned>::iterator I = ObjectNodes.find(V);
assert(I != ObjectNodes.end() &&
"Value does not have an object in the points-to graph!");
/// getReturnNode - Return the node representing the return value for the
/// specified function.
- unsigned getReturnNode(Function *F) {
+ unsigned getReturnNode(Function *F) const {
DenseMap<Function*, unsigned>::iterator I = ReturnNodes.find(F);
assert(I != ReturnNodes.end() && "Function does not return a value!");
return I->second;
/// getVarargNode - Return the node representing the variable arguments
/// formal for the specified function.
- unsigned getVarargNode(Function *F) {
+ unsigned getVarargNode(Function *F) const {
DenseMap<Function*, unsigned>::iterator I = VarargNodes.find(F);
assert(I != VarargNodes.end() && "Function does not take var args!");
return I->second;
unsigned UniteNodes(unsigned First, unsigned Second,
bool UnionByRank = true);
unsigned FindNode(unsigned Node);
+ unsigned FindNode(unsigned Node) const;
void IdentifyObjects(Module &M);
void CollectConstraints(Module &M);
bool AddConstraintsForExternalCall(CallSite CS, Function *F);
- void PrintNode(Node *N);
- void PrintConstraints();
- void PrintConstraint(const Constraint &);
- void PrintLabels();
- void PrintPointsToGraph();
+ void PrintNode(const Node *N) const;
+ void PrintConstraints() const ;
+ void PrintConstraint(const Constraint &) const;
+ void PrintLabels() const;
+ void PrintPointsToGraph() const;
//===------------------------------------------------------------------===//
// Instruction visitation methods for adding constraints
void visitVAArg(VAArgInst &I);
void visitInstruction(Instruction &I);
+ //===------------------------------------------------------------------===//
+ // Implement Analyize interface
+ //
+ void print(std::ostream &O, const Module* M) const {
+ PrintPointsToGraph();
+ }
};
+}
- char Andersens::ID = 0;
- RegisterPass<Andersens> X("anders-aa",
- "Andersen's Interprocedural Alias Analysis");
- RegisterAnalysisGroup<AliasAnalysis> Y(X);
+char Andersens::ID = 0;
+static RegisterPass<Andersens>
+X("anders-aa", "Andersen's Interprocedural Alias Analysis", false, true);
+static RegisterAnalysisGroup<AliasAnalysis> Y(X);
- // Initialize Timestamp Counter (static).
- unsigned Andersens::Node::Counter = 0;
-}
+// Initialize Timestamp Counter (static).
+unsigned Andersens::Node::Counter = 0;
ModulePass *llvm::createAndersensPass() { return new Andersens(); }
if (N1->PointsTo->empty())
return NoModRef;
-
+#if FULL_UNIVERSAL
+ if (!UniversalSet->PointsTo->test(FindNode(getNode(P))))
+ return NoModRef; // Universal set does not contain P
+#else
if (!N1->PointsTo->test(UniversalSet))
return NoModRef; // P doesn't point to the universal set.
+#endif
}
return AliasAnalysis::getModRefInfo(CS, P, Size);
/// object N, which contains values indicated by C.
void Andersens::AddGlobalInitializerConstraints(unsigned NodeIndex,
Constant *C) {
- if (C->getType()->isFirstClassType()) {
+ if (C->getType()->isSingleValueType()) {
if (isa<PointerType>(C->getType()))
Constraints.push_back(Constraint(Constraint::Copy, NodeIndex,
getNodeForConstantPointer(C)));
F->getName() == "atol" || F->getName() == "atoll" ||
F->getName() == "remove" || F->getName() == "unlink" ||
F->getName() == "rename" || F->getName() == "memcmp" ||
- F->getName() == "llvm.memset.i32" ||
- F->getName() == "llvm.memset.i64" ||
+ F->getName() == "llvm.memset" ||
F->getName() == "strcmp" || F->getName() == "strncmp" ||
F->getName() == "execl" || F->getName() == "execlp" ||
F->getName() == "execle" || F->getName() == "execv" ||
// These functions do induce points-to edges.
- if (F->getName() == "llvm.memcpy.i32" || F->getName() == "llvm.memcpy.i64" ||
- F->getName() == "llvm.memmove.i32" ||F->getName() == "llvm.memmove.i64" ||
+ if (F->getName() == "llvm.memcpy" ||
+ F->getName() == "llvm.memmove" ||
F->getName() == "memmove") {
- // *Dest = *Src, which requires an artificial graph node to represent the
- // constraint. It is broken up into *Dest = temp, temp = *Src
- unsigned FirstArg = getNode(CS.getArgument(0));
- unsigned SecondArg = getNode(CS.getArgument(1));
- unsigned TempArg = GraphNodes.size();
- GraphNodes.push_back(Node());
- Constraints.push_back(Constraint(Constraint::Store,
- FirstArg, TempArg));
- Constraints.push_back(Constraint(Constraint::Load,
- TempArg, SecondArg));
- return true;
+ const FunctionType *FTy = F->getFunctionType();
+ if (FTy->getNumParams() > 1 &&
+ isa<PointerType>(FTy->getParamType(0)) &&
+ isa<PointerType>(FTy->getParamType(1))) {
+
+ // *Dest = *Src, which requires an artificial graph node to represent the
+ // constraint. It is broken up into *Dest = temp, temp = *Src
+ unsigned FirstArg = getNode(CS.getArgument(0));
+ unsigned SecondArg = getNode(CS.getArgument(1));
+ unsigned TempArg = GraphNodes.size();
+ GraphNodes.push_back(Node());
+ Constraints.push_back(Constraint(Constraint::Store,
+ FirstArg, TempArg));
+ Constraints.push_back(Constraint(Constraint::Load,
+ TempArg, SecondArg));
+ // In addition, Dest = Src
+ Constraints.push_back(Constraint(Constraint::Copy,
+ FirstArg, SecondArg));
+ return true;
+ }
}
// Result = Arg0
if (F->getName() == "realloc" || F->getName() == "strchr" ||
F->getName() == "strrchr" || F->getName() == "strstr" ||
F->getName() == "strtok") {
- Constraints.push_back(Constraint(Constraint::Copy,
- getNode(CS.getInstruction()),
- getNode(CS.getArgument(0))));
- return true;
+ const FunctionType *FTy = F->getFunctionType();
+ if (FTy->getNumParams() > 0 &&
+ isa<PointerType>(FTy->getParamType(0))) {
+ Constraints.push_back(Constraint(Constraint::Copy,
+ getNode(CS.getInstruction()),
+ getNode(CS.getArgument(0))));
+ return true;
+ }
}
return false;
// At some point we should just add constraints for the escaping functions
// at solve time, but this slows down solving. For now, we simply mark
// address taken functions as escaping and treat them as external.
- if (!F->hasInternalLinkage() || AnalyzeUsesOfFunction(F))
+ if (!F->hasLocalLinkage() || AnalyzeUsesOfFunction(F))
AddConstraintsForNonInternalLinkage(F);
if (!F->isDeclaration()) {
}
CallSite::arg_iterator ArgI = CS.arg_begin(), ArgE = CS.arg_end();
+ bool external = !F || F->isDeclaration();
if (F) {
// Direct Call
Function::arg_iterator AI = F->arg_begin(), AE = F->arg_end();
- for (; AI != AE && ArgI != ArgE; ++AI, ++ArgI)
- if (isa<PointerType>(AI->getType())) {
- if (isa<PointerType>((*ArgI)->getType())) {
- // Copy the actual argument into the formal argument.
- Constraints.push_back(Constraint(Constraint::Copy, getNode(AI),
- getNode(*ArgI)));
- } else {
- Constraints.push_back(Constraint(Constraint::Copy, getNode(AI),
- UniversalSet));
- }
- } else if (isa<PointerType>((*ArgI)->getType())) {
+ for (; AI != AE && ArgI != ArgE; ++AI, ++ArgI)
+ {
+#if !FULL_UNIVERSAL
+ if (external && isa<PointerType>((*ArgI)->getType()))
+ {
+ // Add constraint that ArgI can now point to anything due to
+ // escaping, as can everything it points to. The second portion of
+ // this should be taken care of by universal = *universal
+ Constraints.push_back(Constraint(Constraint::Copy,
+ getNode(*ArgI),
+ UniversalSet));
+ }
+#endif
+ if (isa<PointerType>(AI->getType())) {
+ if (isa<PointerType>((*ArgI)->getType())) {
+ // Copy the actual argument into the formal argument.
+ Constraints.push_back(Constraint(Constraint::Copy, getNode(AI),
+ getNode(*ArgI)));
+ } else {
+ Constraints.push_back(Constraint(Constraint::Copy, getNode(AI),
+ UniversalSet));
+ }
+ } else if (isa<PointerType>((*ArgI)->getType())) {
#if FULL_UNIVERSAL
- Constraints.push_back(Constraint(Constraint::Copy,
- UniversalSet,
- getNode(*ArgI)));
+ Constraints.push_back(Constraint(Constraint::Copy,
+ UniversalSet,
+ getNode(*ArgI)));
#else
- Constraints.push_back(Constraint(Constraint::Copy,
- getNode(*ArgI),
- UniversalSet));
+ Constraints.push_back(Constraint(Constraint::Copy,
+ getNode(*ArgI),
+ UniversalSet));
#endif
+ }
}
} else {
//Indirect Call
return NodeIndex;
}
-void Andersens::PrintLabels() {
+void Andersens::PrintLabels() const {
for (unsigned i = 0; i < GraphNodes.size(); ++i) {
if (i < FirstRefNode) {
PrintNode(&GraphNodes[i]);
DOUT << "\n";
if (SDTActive)
- if (SDT[Second] >= 0)
+ if (SDT[Second] >= 0) {
if (SDT[First] < 0)
SDT[First] = SDT[Second];
else {
UniteNodes( FindNode(SDT[First]), FindNode(SDT[Second]) );
First = FindNode(First);
}
+ }
return First;
}
return (N->NodeRep = FindNode(N->NodeRep));
}
+// Find the index into GraphNodes of the node representing Node,
+// don't perform path compression along the way (for Print)
+unsigned Andersens::FindNode(unsigned NodeIndex) const {
+ assert (NodeIndex < GraphNodes.size()
+ && "Attempting to find a node that can't exist");
+ const Node *N = &GraphNodes[NodeIndex];
+ if (N->isRep())
+ return NodeIndex;
+ else
+ return FindNode(N->NodeRep);
+}
+
//===----------------------------------------------------------------------===//
// Debugging Output
//===----------------------------------------------------------------------===//
-void Andersens::PrintNode(Node *N) {
+void Andersens::PrintNode(const Node *N) const {
if (N == &GraphNodes[UniversalSet]) {
cerr << "<universal>";
return;
if (N == &GraphNodes[getObject(V)])
cerr << "<mem>";
}
-void Andersens::PrintConstraint(const Constraint &C) {
+void Andersens::PrintConstraint(const Constraint &C) const {
if (C.Type == Constraint::Store) {
cerr << "*";
if (C.Offset != 0)
cerr << "\n";
}
-void Andersens::PrintConstraints() {
+void Andersens::PrintConstraints() const {
cerr << "Constraints:\n";
for (unsigned i = 0, e = Constraints.size(); i != e; ++i)
PrintConstraint(Constraints[i]);
}
-void Andersens::PrintPointsToGraph() {
+void Andersens::PrintPointsToGraph() const {
cerr << "Points-to graph:\n";
for (unsigned i = 0, e = GraphNodes.size(); i != e; ++i) {
- Node *N = &GraphNodes[i];
- if (FindNode (i) != i) {
+ const Node *N = &GraphNodes[i];
+ if (FindNode(i) != i) {
PrintNode(N);
cerr << "\t--> same as ";
PrintNode(&GraphNodes[FindNode(i)]);