#include "llvm/Module.h"
#include "llvm/Pass.h"
#include "llvm/Support/Compiler.h"
+#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/InstIterator.h"
#include "llvm/Support/InstVisitor.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/Passes.h"
#include "llvm/Support/Debug.h"
+#include "llvm/System/Atomic.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/SparseBitVector.h"
#include "llvm/ADT/DenseSet.h"
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);
// for each location equivalent Node.
struct Node {
private:
- static unsigned Counter;
+ static volatile sys::cas_flag Counter;
public:
Value *Val;
// Timestamp a node (used for work list prioritization)
void Stamp() {
- Timestamp = Counter++;
+ Timestamp = sys::AtomicIncrement(&Counter);
+ --Timestamp;
}
bool isRep() const {
public:
static char ID;
- Andersens() : ModulePass((intptr_t)&ID) {}
+ Andersens() : ModulePass(&ID) {}
bool runOnModule(Module &M) {
InitializeAliasAnalysis(this);
#ifndef NDEBUG
V->dump();
#endif
- assert(0 && "Value does not have a node in the points-to graph!");
+ llvm_unreachable("Value does not have a node in the points-to graph!");
}
return I->second;
}
//===------------------------------------------------------------------===//
// Implement Analyize interface
//
- void print(std::ostream &O, const Module* M) const {
+ void print(raw_ostream &O, const Module*) const {
PrintPointsToGraph();
}
};
+}
- char Andersens::ID = 0;
- RegisterPass<Andersens> X("anders-aa",
- "Andersen's Interprocedural Alias Analysis", false,
- true);
- 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).
+volatile llvm::sys::cas_flag Andersens::Node::Counter = 0;
ModulePass *llvm::createAndersensPass() { return new Andersens(); }
case Instruction::BitCast:
return getNodeForConstantPointer(CE->getOperand(0));
default:
- cerr << "Constant Expr not yet handled: " << *CE << "\n";
- assert(0);
+ errs() << "Constant Expr not yet handled: " << *CE << "\n";
+ llvm_unreachable(0);
}
} else {
- assert(0 && "Unknown constant pointer!");
+ llvm_unreachable("Unknown constant pointer!");
}
return 0;
}
case Instruction::BitCast:
return getNodeForConstantPointerTarget(CE->getOperand(0));
default:
- cerr << "Constant Expr not yet handled: " << *CE << "\n";
- assert(0);
+ errs() << "Constant Expr not yet handled: " << *CE << "\n";
+ llvm_unreachable(0);
}
} else {
- assert(0 && "Unknown constant pointer!");
+ llvm_unreachable("Unknown constant pointer!");
}
return 0;
}
/// 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;
if (!isa<PointerType>(V->getType())) return true;
for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ++UI)
- if (dyn_cast<LoadInst>(*UI)) {
+ if (isa<LoadInst>(*UI)) {
return false;
} else if (StoreInst *SI = dyn_cast<StoreInst>(*UI)) {
if (V == SI->getOperand(1)) {
} else if (ICmpInst *ICI = dyn_cast<ICmpInst>(*UI)) {
if (!isa<ConstantPointerNull>(ICI->getOperand(1)))
return true; // Allow comparison against null.
- } else if (dyn_cast<FreeInst>(*UI)) {
+ } else if (isa<FreeInst>(*UI)) {
return false;
} else {
return true;
Constraints.push_back(Constraint(Constraint::AddressOf, getNodeValue(*I),
ObjectIndex));
- if (I->hasInitializer()) {
+ if (I->hasDefinitiveInitializer()) {
AddGlobalInitializerConstraints(ObjectIndex, I->getInitializer());
} else {
// If it doesn't have an initializer (i.e. it's defined in another
// 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()) {
return;
default:
// Is this something we aren't handling yet?
- cerr << "Unknown instruction: " << I;
- abort();
+ errs() << "Unknown instruction: " << I;
+ llvm_unreachable(0);
}
}
}
void Andersens::visitVAArg(VAArgInst &I) {
- assert(0 && "vaarg not handled yet!");
+ llvm_unreachable("vaarg not handled yet!");
}
/// AddConstraintsForCall - Add constraints for a call with actual arguments
return Result;
}
-void dumpToDOUT(SparseBitVector<> *bitmap) {
-#ifndef NDEBUG
- dump(*bitmap, DOUT);
-#endif
-}
-
/// Clump together address taken variables so that the points-to sets use up
/// less space and can be operated on faster.
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;
}
void Andersens::PrintNode(const Node *N) const {
if (N == &GraphNodes[UniversalSet]) {
- cerr << "<universal>";
+ errs() << "<universal>";
return;
} else if (N == &GraphNodes[NullPtr]) {
- cerr << "<nullptr>";
+ errs() << "<nullptr>";
return;
} else if (N == &GraphNodes[NullObject]) {
- cerr << "<null>";
+ errs() << "<null>";
return;
}
if (!N->getValue()) {
- cerr << "artificial" << (intptr_t) N;
+ errs() << "artificial" << (intptr_t) N;
return;
}
if (Function *F = dyn_cast<Function>(V)) {
if (isa<PointerType>(F->getFunctionType()->getReturnType()) &&
N == &GraphNodes[getReturnNode(F)]) {
- cerr << F->getName() << ":retval";
+ errs() << F->getName() << ":retval";
return;
} else if (F->getFunctionType()->isVarArg() &&
N == &GraphNodes[getVarargNode(F)]) {
- cerr << F->getName() << ":vararg";
+ errs() << F->getName() << ":vararg";
return;
}
}
if (Instruction *I = dyn_cast<Instruction>(V))
- cerr << I->getParent()->getParent()->getName() << ":";
+ errs() << I->getParent()->getParent()->getName() << ":";
else if (Argument *Arg = dyn_cast<Argument>(V))
- cerr << Arg->getParent()->getName() << ":";
+ errs() << Arg->getParent()->getName() << ":";
if (V->hasName())
- cerr << V->getName();
+ errs() << V->getName();
else
- cerr << "(unnamed)";
+ errs() << "(unnamed)";
if (isa<GlobalValue>(V) || isa<AllocationInst>(V))
if (N == &GraphNodes[getObject(V)])
- cerr << "<mem>";
+ errs() << "<mem>";
}
void Andersens::PrintConstraint(const Constraint &C) const {
if (C.Type == Constraint::Store) {
- cerr << "*";
+ errs() << "*";
if (C.Offset != 0)
- cerr << "(";
+ errs() << "(";
}
PrintNode(&GraphNodes[C.Dest]);
if (C.Type == Constraint::Store && C.Offset != 0)
- cerr << " + " << C.Offset << ")";
- cerr << " = ";
+ errs() << " + " << C.Offset << ")";
+ errs() << " = ";
if (C.Type == Constraint::Load) {
- cerr << "*";
+ errs() << "*";
if (C.Offset != 0)
- cerr << "(";
+ errs() << "(";
}
else if (C.Type == Constraint::AddressOf)
- cerr << "&";
+ errs() << "&";
PrintNode(&GraphNodes[C.Src]);
if (C.Offset != 0 && C.Type != Constraint::Store)
- cerr << " + " << C.Offset;
+ errs() << " + " << C.Offset;
if (C.Type == Constraint::Load && C.Offset != 0)
- cerr << ")";
- cerr << "\n";
+ errs() << ")";
+ errs() << "\n";
}
void Andersens::PrintConstraints() const {
- cerr << "Constraints:\n";
+ errs() << "Constraints:\n";
for (unsigned i = 0, e = Constraints.size(); i != e; ++i)
PrintConstraint(Constraints[i]);
}
void Andersens::PrintPointsToGraph() const {
- cerr << "Points-to graph:\n";
+ errs() << "Points-to graph:\n";
for (unsigned i = 0, e = GraphNodes.size(); i != e; ++i) {
const Node *N = &GraphNodes[i];
if (FindNode(i) != i) {
PrintNode(N);
- cerr << "\t--> same as ";
+ errs() << "\t--> same as ";
PrintNode(&GraphNodes[FindNode(i)]);
- cerr << "\n";
+ errs() << "\n";
} else {
- cerr << "[" << (N->PointsTo->count()) << "] ";
+ errs() << "[" << (N->PointsTo->count()) << "] ";
PrintNode(N);
- cerr << "\t--> ";
+ errs() << "\t--> ";
bool first = true;
for (SparseBitVector<>::iterator bi = N->PointsTo->begin();
bi != N->PointsTo->end();
++bi) {
if (!first)
- cerr << ", ";
+ errs() << ", ";
PrintNode(&GraphNodes[*bi]);
first = false;
}
- cerr << "\n";
+ errs() << "\n";
}
}
}
projects / oota-llvm.git / blobdiff