It's not necessary to do rounding for alloca operations when the requested
alignment is equal to the stack alignment.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@40004 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Analysis/IPA/Andersens.cpp b/lib/Analysis/IPA/Andersens.cpp
new file mode 100644
index 0000000..4c0d246
--- /dev/null
+++ b/lib/Analysis/IPA/Andersens.cpp
@@ -0,0 +1,1177 @@
+//===- Andersens.cpp - Andersen's Interprocedural Alias Analysis ----------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines a very simple implementation of Andersen's interprocedural
+// alias analysis. This implementation does not include any of the fancy
+// features that make Andersen's reasonably efficient (like cycle elimination or
+// variable substitution), but it should be useful for getting precision
+// numbers and can be extended in the future.
+//
+// In pointer analysis terms, this is a subset-based, flow-insensitive,
+// field-insensitive, and context-insensitive algorithm pointer algorithm.
+//
+// This algorithm is implemented as three stages:
+// 1. Object identification.
+// 2. Inclusion constraint identification.
+// 3. Inclusion constraint solving.
+//
+// The object identification stage identifies all of the memory objects in the
+// program, which includes globals, heap allocated objects, and stack allocated
+// objects.
+//
+// The inclusion constraint identification stage finds all inclusion constraints
+// in the program by scanning the program, looking for pointer assignments and
+// other statements that effect the points-to graph. For a statement like "A =
+// B", this statement is processed to indicate that A can point to anything that
+// B can point to. Constraints can handle copies, loads, and stores.
+//
+// The inclusion constraint solving phase iteratively propagates the inclusion
+// constraints until a fixed point is reached. This is an O(N^3) algorithm.
+//
+// In the initial pass, all indirect function calls are completely ignored. As
+// the analysis discovers new targets of function pointers, it iteratively
+// resolves a precise (and conservative) call graph. Also related, this
+// analysis initially assumes that all internal functions have known incoming
+// pointers. If we find that an internal function's address escapes outside of
+// the program, we update this assumption.
+//
+// Future Improvements:
+// This implementation of Andersen's algorithm is extremely slow. To make it
+// scale reasonably well, the inclusion constraints could be sorted (easy),
+// offline variable substitution would be a huge win (straight-forward), and
+// online cycle elimination (trickier) might help as well.
+//
+//===----------------------------------------------------------------------===//
+
+#define DEBUG_TYPE "anders-aa"
+#include "llvm/Constants.h"
+#include "llvm/DerivedTypes.h"
+#include "llvm/Instructions.h"
+#include "llvm/Module.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/Compiler.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/ADT/Statistic.h"
+#include <algorithm>
+#include <set>
+using namespace llvm;
+
+STATISTIC(NumIters , "Number of iterations to reach convergence");
+STATISTIC(NumConstraints , "Number of constraints");
+STATISTIC(NumNodes , "Number of nodes");
+STATISTIC(NumEscapingFunctions, "Number of internal functions that escape");
+STATISTIC(NumIndirectCallees , "Number of indirect callees found");
+
+namespace {
+ class VISIBILITY_HIDDEN Andersens : public ModulePass, public AliasAnalysis,
+ private InstVisitor<Andersens> {
+ public:
+ static char ID; // Class identification, replacement for typeinfo
+ Andersens() : ModulePass((intptr_t)&ID) {}
+ private:
+ /// Node class - This class is used to represent a memory object in the
+ /// program, and is the primitive used to build the points-to graph.
+ class Node {
+ std::vector<Node*> Pointees;
+ Value *Val;
+ public:
+ static const unsigned ID; // Pass identification, replacement for typeid
+ Node() : Val(0) {}
+ Node *setValue(Value *V) {
+ assert(Val == 0 && "Value already set for this node!");
+ Val = V;
+ return this;
+ }
+
+ /// getValue - Return the LLVM value corresponding to this node.
+ ///
+ Value *getValue() const { return Val; }
+
+ typedef std::vector<Node*>::const_iterator iterator;
+ iterator begin() const { return Pointees.begin(); }
+ iterator end() const { return Pointees.end(); }
+
+ /// addPointerTo - Add a pointer to the list of pointees of this node,
+ /// returning true if this caused a new pointer to be added, or false if
+ /// we already knew about the points-to relation.
+ bool addPointerTo(Node *N) {
+ std::vector<Node*>::iterator I = std::lower_bound(Pointees.begin(),
+ Pointees.end(),
+ N);
+ if (I != Pointees.end() && *I == N)
+ return false;
+ Pointees.insert(I, N);
+ return true;
+ }
+
+ /// intersects - Return true if the points-to set of this node intersects
+ /// with the points-to set of the specified node.
+ bool intersects(Node *N) const;
+
+ /// intersectsIgnoring - Return true if the points-to set of this node
+ /// intersects with the points-to set of the specified node on any nodes
+ /// except for the specified node to ignore.
+ bool intersectsIgnoring(Node *N, Node *Ignoring) const;
+
+ // Constraint application methods.
+ bool copyFrom(Node *N);
+ bool loadFrom(Node *N);
+ bool storeThrough(Node *N);
+ };
+
+ /// GraphNodes - This vector is populated as part of the object
+ /// identification stage of the analysis, which populates this vector with a
+ /// node for each memory object and fills in the ValueNodes map.
+ std::vector<Node> GraphNodes;
+
+ /// ValueNodes - This map indicates the Node that a particular Value* is
+ /// represented by. This contains entries for all pointers.
+ std::map<Value*, unsigned> ValueNodes;
+
+ /// ObjectNodes - This map contains entries for each memory object in the
+ /// program: globals, alloca's and mallocs.
+ std::map<Value*, unsigned> ObjectNodes;
+
+ /// ReturnNodes - This map contains an entry for each function in the
+ /// program that returns a value.
+ std::map<Function*, unsigned> ReturnNodes;
+
+ /// VarargNodes - This map contains the entry used to represent all pointers
+ /// passed through the varargs portion of a function call for a particular
+ /// function. An entry is not present in this map for functions that do not
+ /// take variable arguments.
+ std::map<Function*, unsigned> VarargNodes;
+
+ /// Constraint - Objects of this structure are used to represent the various
+ /// constraints identified by the algorithm. The constraints are 'copy',
+ /// for statements like "A = B", 'load' for statements like "A = *B", and
+ /// 'store' for statements like "*A = B".
+ struct Constraint {
+ enum ConstraintType { Copy, Load, Store } Type;
+ Node *Dest, *Src;
+
+ Constraint(ConstraintType Ty, Node *D, Node *S)
+ : Type(Ty), Dest(D), Src(S) {}
+ };
+
+ /// Constraints - This vector contains a list of all of the constraints
+ /// identified by the program.
+ std::vector<Constraint> Constraints;
+
+ /// EscapingInternalFunctions - This set contains all of the internal
+ /// functions that are found to escape from the program. If the address of
+ /// an internal function is passed to an external function or otherwise
+ /// escapes from the analyzed portion of the program, we must assume that
+ /// any pointer arguments can alias the universal node. This set keeps
+ /// track of those functions we are assuming to escape so far.
+ std::set<Function*> EscapingInternalFunctions;
+
+ /// IndirectCalls - This contains a list of all of the indirect call sites
+ /// in the program. Since the call graph is iteratively discovered, we may
+ /// need to add constraints to our graph as we find new targets of function
+ /// pointers.
+ std::vector<CallSite> IndirectCalls;
+
+ /// IndirectCallees - For each call site in the indirect calls list, keep
+ /// track of the callees that we have discovered so far. As the analysis
+ /// proceeds, more callees are discovered, until the call graph finally
+ /// stabilizes.
+ std::map<CallSite, std::vector<Function*> > IndirectCallees;
+
+ /// This enum defines the GraphNodes indices that correspond to important
+ /// fixed sets.
+ enum {
+ UniversalSet = 0,
+ NullPtr = 1,
+ NullObject = 2
+ };
+
+ public:
+ bool runOnModule(Module &M) {
+ InitializeAliasAnalysis(this);
+ IdentifyObjects(M);
+ CollectConstraints(M);
+ DEBUG(PrintConstraints());
+ SolveConstraints();
+ DEBUG(PrintPointsToGraph());
+
+ // Free the constraints list, as we don't need it to respond to alias
+ // requests.
+ ObjectNodes.clear();
+ ReturnNodes.clear();
+ VarargNodes.clear();
+ EscapingInternalFunctions.clear();
+ std::vector<Constraint>().swap(Constraints);
+ return false;
+ }
+
+ void releaseMemory() {
+ // FIXME: Until we have transitively required passes working correctly,
+ // this cannot be enabled! Otherwise, using -count-aa with the pass
+ // causes memory to be freed too early. :(
+#if 0
+ // The memory objects and ValueNodes data structures at the only ones that
+ // are still live after construction.
+ std::vector<Node>().swap(GraphNodes);
+ ValueNodes.clear();
+#endif
+ }
+
+ virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+ AliasAnalysis::getAnalysisUsage(AU);
+ AU.setPreservesAll(); // Does not transform code
+ }
+
+ //------------------------------------------------
+ // Implement the AliasAnalysis API
+ //
+ AliasResult alias(const Value *V1, unsigned V1Size,
+ const Value *V2, unsigned V2Size);
+ virtual ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size);
+ virtual ModRefResult getModRefInfo(CallSite CS1, CallSite CS2);
+ void getMustAliases(Value *P, std::vector<Value*> &RetVals);
+ bool pointsToConstantMemory(const Value *P);
+
+ virtual void deleteValue(Value *V) {
+ ValueNodes.erase(V);
+ getAnalysis<AliasAnalysis>().deleteValue(V);
+ }
+
+ virtual void copyValue(Value *From, Value *To) {
+ ValueNodes[To] = ValueNodes[From];
+ getAnalysis<AliasAnalysis>().copyValue(From, To);
+ }
+
+ private:
+ /// getNode - Return the node corresponding to the specified pointer scalar.
+ ///
+ Node *getNode(Value *V) {
+ if (Constant *C = dyn_cast<Constant>(V))
+ if (!isa<GlobalValue>(C))
+ return getNodeForConstantPointer(C);
+
+ std::map<Value*, unsigned>::iterator I = ValueNodes.find(V);
+ if (I == ValueNodes.end()) {
+#ifndef NDEBUG
+ V->dump();
+#endif
+ assert(0 && "Value does not have a node in the points-to graph!");
+ }
+ return &GraphNodes[I->second];
+ }
+
+ /// getObject - Return the node corresponding to the memory object for the
+ /// specified global or allocation instruction.
+ Node *getObject(Value *V) {
+ std::map<Value*, unsigned>::iterator I = ObjectNodes.find(V);
+ assert(I != ObjectNodes.end() &&
+ "Value does not have an object in the points-to graph!");
+ return &GraphNodes[I->second];
+ }
+
+ /// getReturnNode - Return the node representing the return value for the
+ /// specified function.
+ Node *getReturnNode(Function *F) {
+ std::map<Function*, unsigned>::iterator I = ReturnNodes.find(F);
+ assert(I != ReturnNodes.end() && "Function does not return a value!");
+ return &GraphNodes[I->second];
+ }
+
+ /// getVarargNode - Return the node representing the variable arguments
+ /// formal for the specified function.
+ Node *getVarargNode(Function *F) {
+ std::map<Function*, unsigned>::iterator I = VarargNodes.find(F);
+ assert(I != VarargNodes.end() && "Function does not take var args!");
+ return &GraphNodes[I->second];
+ }
+
+ /// getNodeValue - Get the node for the specified LLVM value and set the
+ /// value for it to be the specified value.
+ Node *getNodeValue(Value &V) {
+ return getNode(&V)->setValue(&V);
+ }
+
+ void IdentifyObjects(Module &M);
+ void CollectConstraints(Module &M);
+ void SolveConstraints();
+
+ Node *getNodeForConstantPointer(Constant *C);
+ Node *getNodeForConstantPointerTarget(Constant *C);
+ void AddGlobalInitializerConstraints(Node *N, Constant *C);
+
+ void AddConstraintsForNonInternalLinkage(Function *F);
+ void AddConstraintsForCall(CallSite CS, Function *F);
+ bool AddConstraintsForExternalCall(CallSite CS, Function *F);
+
+
+ void PrintNode(Node *N);
+ void PrintConstraints();
+ void PrintPointsToGraph();
+
+ //===------------------------------------------------------------------===//
+ // Instruction visitation methods for adding constraints
+ //
+ friend class InstVisitor<Andersens>;
+ void visitReturnInst(ReturnInst &RI);
+ void visitInvokeInst(InvokeInst &II) { visitCallSite(CallSite(&II)); }
+ void visitCallInst(CallInst &CI) { visitCallSite(CallSite(&CI)); }
+ void visitCallSite(CallSite CS);
+ void visitAllocationInst(AllocationInst &AI);
+ void visitLoadInst(LoadInst &LI);
+ void visitStoreInst(StoreInst &SI);
+ void visitGetElementPtrInst(GetElementPtrInst &GEP);
+ void visitPHINode(PHINode &PN);
+ void visitCastInst(CastInst &CI);
+ void visitICmpInst(ICmpInst &ICI) {} // NOOP!
+ void visitFCmpInst(FCmpInst &ICI) {} // NOOP!
+ void visitSelectInst(SelectInst &SI);
+ void visitVAArg(VAArgInst &I);
+ void visitInstruction(Instruction &I);
+ };
+
+ char Andersens::ID = 0;
+ RegisterPass<Andersens> X("anders-aa",
+ "Andersen's Interprocedural Alias Analysis");
+ RegisterAnalysisGroup<AliasAnalysis> Y(X);
+}
+
+ModulePass *llvm::createAndersensPass() { return new Andersens(); }
+
+//===----------------------------------------------------------------------===//
+// AliasAnalysis Interface Implementation
+//===----------------------------------------------------------------------===//
+
+AliasAnalysis::AliasResult Andersens::alias(const Value *V1, unsigned V1Size,
+ const Value *V2, unsigned V2Size) {
+ Node *N1 = getNode(const_cast<Value*>(V1));
+ Node *N2 = getNode(const_cast<Value*>(V2));
+
+ // Check to see if the two pointers are known to not alias. They don't alias
+ // if their points-to sets do not intersect.
+ if (!N1->intersectsIgnoring(N2, &GraphNodes[NullObject]))
+ return NoAlias;
+
+ return AliasAnalysis::alias(V1, V1Size, V2, V2Size);
+}
+
+AliasAnalysis::ModRefResult
+Andersens::getModRefInfo(CallSite CS, Value *P, unsigned Size) {
+ // The only thing useful that we can contribute for mod/ref information is
+ // when calling external function calls: if we know that memory never escapes
+ // from the program, it cannot be modified by an external call.
+ //
+ // NOTE: This is not really safe, at least not when the entire program is not
+ // available. The deal is that the external function could call back into the
+ // program and modify stuff. We ignore this technical niggle for now. This
+ // is, after all, a "research quality" implementation of Andersen's analysis.
+ if (Function *F = CS.getCalledFunction())
+ if (F->isDeclaration()) {
+ Node *N1 = getNode(P);
+
+ if (N1->begin() == N1->end())
+ return NoModRef; // P doesn't point to anything.
+
+ // Get the first pointee.
+ Node *FirstPointee = *N1->begin();
+ if (FirstPointee != &GraphNodes[UniversalSet])
+ return NoModRef; // P doesn't point to the universal set.
+ }
+
+ return AliasAnalysis::getModRefInfo(CS, P, Size);
+}
+
+AliasAnalysis::ModRefResult
+Andersens::getModRefInfo(CallSite CS1, CallSite CS2) {
+ return AliasAnalysis::getModRefInfo(CS1,CS2);
+}
+
+/// getMustAlias - We can provide must alias information if we know that a
+/// pointer can only point to a specific function or the null pointer.
+/// Unfortunately we cannot determine must-alias information for global
+/// variables or any other memory memory objects because we do not track whether
+/// a pointer points to the beginning of an object or a field of it.
+void Andersens::getMustAliases(Value *P, std::vector<Value*> &RetVals) {
+ Node *N = getNode(P);
+ Node::iterator I = N->begin();
+ if (I != N->end()) {
+ // If there is exactly one element in the points-to set for the object...
+ ++I;
+ if (I == N->end()) {
+ Node *Pointee = *N->begin();
+
+ // If a function is the only object in the points-to set, then it must be
+ // the destination. Note that we can't handle global variables here,
+ // because we don't know if the pointer is actually pointing to a field of
+ // the global or to the beginning of it.
+ if (Value *V = Pointee->getValue()) {
+ if (Function *F = dyn_cast<Function>(V))
+ RetVals.push_back(F);
+ } else {
+ // If the object in the points-to set is the null object, then the null
+ // pointer is a must alias.
+ if (Pointee == &GraphNodes[NullObject])
+ RetVals.push_back(Constant::getNullValue(P->getType()));
+ }
+ }
+ }
+
+ AliasAnalysis::getMustAliases(P, RetVals);
+}
+
+/// pointsToConstantMemory - If we can determine that this pointer only points
+/// to constant memory, return true. In practice, this means that if the
+/// pointer can only point to constant globals, functions, or the null pointer,
+/// return true.
+///
+bool Andersens::pointsToConstantMemory(const Value *P) {
+ Node *N = getNode((Value*)P);
+ for (Node::iterator I = N->begin(), E = N->end(); I != E; ++I) {
+ if (Value *V = (*I)->getValue()) {
+ if (!isa<GlobalValue>(V) || (isa<GlobalVariable>(V) &&
+ !cast<GlobalVariable>(V)->isConstant()))
+ return AliasAnalysis::pointsToConstantMemory(P);
+ } else {
+ if (*I != &GraphNodes[NullObject])
+ return AliasAnalysis::pointsToConstantMemory(P);
+ }
+ }
+
+ return true;
+}
+
+//===----------------------------------------------------------------------===//
+// Object Identification Phase
+//===----------------------------------------------------------------------===//
+
+/// IdentifyObjects - This stage scans the program, adding an entry to the
+/// GraphNodes list for each memory object in the program (global stack or
+/// heap), and populates the ValueNodes and ObjectNodes maps for these objects.
+///
+void Andersens::IdentifyObjects(Module &M) {
+ unsigned NumObjects = 0;
+
+ // Object #0 is always the universal set: the object that we don't know
+ // anything about.
+ assert(NumObjects == UniversalSet && "Something changed!");
+ ++NumObjects;
+
+ // Object #1 always represents the null pointer.
+ assert(NumObjects == NullPtr && "Something changed!");
+ ++NumObjects;
+
+ // Object #2 always represents the null object (the object pointed to by null)
+ assert(NumObjects == NullObject && "Something changed!");
+ ++NumObjects;
+
+ // Add all the globals first.
+ for (Module::global_iterator I = M.global_begin(), E = M.global_end();
+ I != E; ++I) {
+ ObjectNodes[I] = NumObjects++;
+ ValueNodes[I] = NumObjects++;
+ }
+
+ // Add nodes for all of the functions and the instructions inside of them.
+ for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) {
+ // The function itself is a memory object.
+ ValueNodes[F] = NumObjects++;
+ ObjectNodes[F] = NumObjects++;
+ if (isa<PointerType>(F->getFunctionType()->getReturnType()))
+ ReturnNodes[F] = NumObjects++;
+ if (F->getFunctionType()->isVarArg())
+ VarargNodes[F] = NumObjects++;
+
+ // Add nodes for all of the incoming pointer arguments.
+ for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end();
+ I != E; ++I)
+ if (isa<PointerType>(I->getType()))
+ ValueNodes[I] = NumObjects++;
+
+ // Scan the function body, creating a memory object for each heap/stack
+ // allocation in the body of the function and a node to represent all
+ // pointer values defined by instructions and used as operands.
+ for (inst_iterator II = inst_begin(F), E = inst_end(F); II != E; ++II) {
+ // If this is an heap or stack allocation, create a node for the memory
+ // object.
+ if (isa<PointerType>(II->getType())) {
+ ValueNodes[&*II] = NumObjects++;
+ if (AllocationInst *AI = dyn_cast<AllocationInst>(&*II))
+ ObjectNodes[AI] = NumObjects++;
+ }
+ }
+ }
+
+ // Now that we know how many objects to create, make them all now!
+ GraphNodes.resize(NumObjects);
+ NumNodes += NumObjects;
+}
+
+//===----------------------------------------------------------------------===//
+// Constraint Identification Phase
+//===----------------------------------------------------------------------===//
+
+/// getNodeForConstantPointer - Return the node corresponding to the constant
+/// pointer itself.
+Andersens::Node *Andersens::getNodeForConstantPointer(Constant *C) {
+ assert(isa<PointerType>(C->getType()) && "Not a constant pointer!");
+
+ if (isa<ConstantPointerNull>(C) || isa<UndefValue>(C))
+ return &GraphNodes[NullPtr];
+ else if (GlobalValue *GV = dyn_cast<GlobalValue>(C))
+ return getNode(GV);
+ else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
+ switch (CE->getOpcode()) {
+ case Instruction::GetElementPtr:
+ return getNodeForConstantPointer(CE->getOperand(0));
+ case Instruction::IntToPtr:
+ return &GraphNodes[UniversalSet];
+ case Instruction::BitCast:
+ return getNodeForConstantPointer(CE->getOperand(0));
+ default:
+ cerr << "Constant Expr not yet handled: " << *CE << "\n";
+ assert(0);
+ }
+ } else {
+ assert(0 && "Unknown constant pointer!");
+ }
+ return 0;
+}
+
+/// getNodeForConstantPointerTarget - Return the node POINTED TO by the
+/// specified constant pointer.
+Andersens::Node *Andersens::getNodeForConstantPointerTarget(Constant *C) {
+ assert(isa<PointerType>(C->getType()) && "Not a constant pointer!");
+
+ if (isa<ConstantPointerNull>(C))
+ return &GraphNodes[NullObject];
+ else if (GlobalValue *GV = dyn_cast<GlobalValue>(C))
+ return getObject(GV);
+ else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
+ switch (CE->getOpcode()) {
+ case Instruction::GetElementPtr:
+ return getNodeForConstantPointerTarget(CE->getOperand(0));
+ case Instruction::IntToPtr:
+ return &GraphNodes[UniversalSet];
+ case Instruction::BitCast:
+ return getNodeForConstantPointerTarget(CE->getOperand(0));
+ default:
+ cerr << "Constant Expr not yet handled: " << *CE << "\n";
+ assert(0);
+ }
+ } else {
+ assert(0 && "Unknown constant pointer!");
+ }
+ return 0;
+}
+
+/// AddGlobalInitializerConstraints - Add inclusion constraints for the memory
+/// object N, which contains values indicated by C.
+void Andersens::AddGlobalInitializerConstraints(Node *N, Constant *C) {
+ if (C->getType()->isFirstClassType()) {
+ if (isa<PointerType>(C->getType()))
+ N->copyFrom(getNodeForConstantPointer(C));
+
+ } else if (C->isNullValue()) {
+ N->addPointerTo(&GraphNodes[NullObject]);
+ return;
+ } else if (!isa<UndefValue>(C)) {
+ // If this is an array or struct, include constraints for each element.
+ assert(isa<ConstantArray>(C) || isa<ConstantStruct>(C));
+ for (unsigned i = 0, e = C->getNumOperands(); i != e; ++i)
+ AddGlobalInitializerConstraints(N, cast<Constant>(C->getOperand(i)));
+ }
+}
+
+/// AddConstraintsForNonInternalLinkage - If this function does not have
+/// internal linkage, realize that we can't trust anything passed into or
+/// returned by this function.
+void Andersens::AddConstraintsForNonInternalLinkage(Function *F) {
+ for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); I != E; ++I)
+ if (isa<PointerType>(I->getType()))
+ // If this is an argument of an externally accessible function, the
+ // incoming pointer might point to anything.
+ Constraints.push_back(Constraint(Constraint::Copy, getNode(I),
+ &GraphNodes[UniversalSet]));
+}
+
+/// AddConstraintsForCall - If this is a call to a "known" function, add the
+/// constraints and return true. If this is a call to an unknown function,
+/// return false.
+bool Andersens::AddConstraintsForExternalCall(CallSite CS, Function *F) {
+ assert(F->isDeclaration() && "Not an external function!");
+
+ // These functions don't induce any points-to constraints.
+ if (F->getName() == "atoi" || F->getName() == "atof" ||
+ 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() == "strcmp" || F->getName() == "strncmp" ||
+ F->getName() == "execl" || F->getName() == "execlp" ||
+ F->getName() == "execle" || F->getName() == "execv" ||
+ F->getName() == "execvp" || F->getName() == "chmod" ||
+ F->getName() == "puts" || F->getName() == "write" ||
+ F->getName() == "open" || F->getName() == "create" ||
+ F->getName() == "truncate" || F->getName() == "chdir" ||
+ F->getName() == "mkdir" || F->getName() == "rmdir" ||
+ F->getName() == "read" || F->getName() == "pipe" ||
+ F->getName() == "wait" || F->getName() == "time" ||
+ F->getName() == "stat" || F->getName() == "fstat" ||
+ F->getName() == "lstat" || F->getName() == "strtod" ||
+ F->getName() == "strtof" || F->getName() == "strtold" ||
+ F->getName() == "fopen" || F->getName() == "fdopen" ||
+ F->getName() == "freopen" ||
+ F->getName() == "fflush" || F->getName() == "feof" ||
+ F->getName() == "fileno" || F->getName() == "clearerr" ||
+ F->getName() == "rewind" || F->getName() == "ftell" ||
+ F->getName() == "ferror" || F->getName() == "fgetc" ||
+ F->getName() == "fgetc" || F->getName() == "_IO_getc" ||
+ F->getName() == "fwrite" || F->getName() == "fread" ||
+ F->getName() == "fgets" || F->getName() == "ungetc" ||
+ F->getName() == "fputc" ||
+ F->getName() == "fputs" || F->getName() == "putc" ||
+ F->getName() == "ftell" || F->getName() == "rewind" ||
+ F->getName() == "_IO_putc" || F->getName() == "fseek" ||
+ F->getName() == "fgetpos" || F->getName() == "fsetpos" ||
+ F->getName() == "printf" || F->getName() == "fprintf" ||
+ F->getName() == "sprintf" || F->getName() == "vprintf" ||
+ F->getName() == "vfprintf" || F->getName() == "vsprintf" ||
+ F->getName() == "scanf" || F->getName() == "fscanf" ||
+ F->getName() == "sscanf" || F->getName() == "__assert_fail" ||
+ F->getName() == "modf")
+ return true;
+
+
+ // 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" ||
+ F->getName() == "memmove") {
+ // Note: this is a poor approximation, this says Dest = Src, instead of
+ // *Dest = *Src.
+ Constraints.push_back(Constraint(Constraint::Copy,
+ getNode(CS.getArgument(0)),
+ getNode(CS.getArgument(1))));
+ 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;
+ }
+
+ return false;
+}
+
+
+
+/// CollectConstraints - This stage scans the program, adding a constraint to
+/// the Constraints list for each instruction in the program that induces a
+/// constraint, and setting up the initial points-to graph.
+///
+void Andersens::CollectConstraints(Module &M) {
+ // First, the universal set points to itself.
+ GraphNodes[UniversalSet].addPointerTo(&GraphNodes[UniversalSet]);
+ //Constraints.push_back(Constraint(Constraint::Load, &GraphNodes[UniversalSet],
+ // &GraphNodes[UniversalSet]));
+ Constraints.push_back(Constraint(Constraint::Store, &GraphNodes[UniversalSet],
+ &GraphNodes[UniversalSet]));
+
+ // Next, the null pointer points to the null object.
+ GraphNodes[NullPtr].addPointerTo(&GraphNodes[NullObject]);
+
+ // Next, add any constraints on global variables and their initializers.
+ for (Module::global_iterator I = M.global_begin(), E = M.global_end();
+ I != E; ++I) {
+ // Associate the address of the global object as pointing to the memory for
+ // the global: &G = <G memory>
+ Node *Object = getObject(I);
+ Object->setValue(I);
+ getNodeValue(*I)->addPointerTo(Object);
+
+ if (I->hasInitializer()) {
+ AddGlobalInitializerConstraints(Object, I->getInitializer());
+ } else {
+ // If it doesn't have an initializer (i.e. it's defined in another
+ // translation unit), it points to the universal set.
+ Constraints.push_back(Constraint(Constraint::Copy, Object,
+ &GraphNodes[UniversalSet]));
+ }
+ }
+
+ for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) {
+ // Make the function address point to the function object.
+ getNodeValue(*F)->addPointerTo(getObject(F)->setValue(F));
+
+ // Set up the return value node.
+ if (isa<PointerType>(F->getFunctionType()->getReturnType()))
+ getReturnNode(F)->setValue(F);
+ if (F->getFunctionType()->isVarArg())
+ getVarargNode(F)->setValue(F);
+
+ // Set up incoming argument nodes.
+ for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end();
+ I != E; ++I)
+ if (isa<PointerType>(I->getType()))
+ getNodeValue(*I);
+
+ if (!F->hasInternalLinkage())
+ AddConstraintsForNonInternalLinkage(F);
+
+ if (!F->isDeclaration()) {
+ // Scan the function body, creating a memory object for each heap/stack
+ // allocation in the body of the function and a node to represent all
+ // pointer values defined by instructions and used as operands.
+ visit(F);
+ } else {
+ // External functions that return pointers return the universal set.
+ if (isa<PointerType>(F->getFunctionType()->getReturnType()))
+ Constraints.push_back(Constraint(Constraint::Copy,
+ getReturnNode(F),
+ &GraphNodes[UniversalSet]));
+
+ // Any pointers that are passed into the function have the universal set
+ // stored into them.
+ for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end();
+ I != E; ++I)
+ if (isa<PointerType>(I->getType())) {
+ // Pointers passed into external functions could have anything stored
+ // through them.
+ Constraints.push_back(Constraint(Constraint::Store, getNode(I),
+ &GraphNodes[UniversalSet]));
+ // Memory objects passed into external function calls can have the
+ // universal set point to them.
+ Constraints.push_back(Constraint(Constraint::Copy,
+ &GraphNodes[UniversalSet],
+ getNode(I)));
+ }
+
+ // If this is an external varargs function, it can also store pointers
+ // into any pointers passed through the varargs section.
+ if (F->getFunctionType()->isVarArg())
+ Constraints.push_back(Constraint(Constraint::Store, getVarargNode(F),
+ &GraphNodes[UniversalSet]));
+ }
+ }
+ NumConstraints += Constraints.size();
+}
+
+
+void Andersens::visitInstruction(Instruction &I) {
+#ifdef NDEBUG
+ return; // This function is just a big assert.
+#endif
+ if (isa<BinaryOperator>(I))
+ return;
+ // Most instructions don't have any effect on pointer values.
+ switch (I.getOpcode()) {
+ case Instruction::Br:
+ case Instruction::Switch:
+ case Instruction::Unwind:
+ case Instruction::Unreachable:
+ case Instruction::Free:
+ case Instruction::ICmp:
+ case Instruction::FCmp:
+ return;
+ default:
+ // Is this something we aren't handling yet?
+ cerr << "Unknown instruction: " << I;
+ abort();
+ }
+}
+
+void Andersens::visitAllocationInst(AllocationInst &AI) {
+ getNodeValue(AI)->addPointerTo(getObject(&AI)->setValue(&AI));
+}
+
+void Andersens::visitReturnInst(ReturnInst &RI) {
+ if (RI.getNumOperands() && isa<PointerType>(RI.getOperand(0)->getType()))
+ // return V --> <Copy/retval{F}/v>
+ Constraints.push_back(Constraint(Constraint::Copy,
+ getReturnNode(RI.getParent()->getParent()),
+ getNode(RI.getOperand(0))));
+}
+
+void Andersens::visitLoadInst(LoadInst &LI) {
+ if (isa<PointerType>(LI.getType()))
+ // P1 = load P2 --> <Load/P1/P2>
+ Constraints.push_back(Constraint(Constraint::Load, getNodeValue(LI),
+ getNode(LI.getOperand(0))));
+}
+
+void Andersens::visitStoreInst(StoreInst &SI) {
+ if (isa<PointerType>(SI.getOperand(0)->getType()))
+ // store P1, P2 --> <Store/P2/P1>
+ Constraints.push_back(Constraint(Constraint::Store,
+ getNode(SI.getOperand(1)),
+ getNode(SI.getOperand(0))));
+}
+
+void Andersens::visitGetElementPtrInst(GetElementPtrInst &GEP) {
+ // P1 = getelementptr P2, ... --> <Copy/P1/P2>
+ Constraints.push_back(Constraint(Constraint::Copy, getNodeValue(GEP),
+ getNode(GEP.getOperand(0))));
+}
+
+void Andersens::visitPHINode(PHINode &PN) {
+ if (isa<PointerType>(PN.getType())) {
+ Node *PNN = getNodeValue(PN);
+ for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
+ // P1 = phi P2, P3 --> <Copy/P1/P2>, <Copy/P1/P3>, ...
+ Constraints.push_back(Constraint(Constraint::Copy, PNN,
+ getNode(PN.getIncomingValue(i))));
+ }
+}
+
+void Andersens::visitCastInst(CastInst &CI) {
+ Value *Op = CI.getOperand(0);
+ if (isa<PointerType>(CI.getType())) {
+ if (isa<PointerType>(Op->getType())) {
+ // P1 = cast P2 --> <Copy/P1/P2>
+ Constraints.push_back(Constraint(Constraint::Copy, getNodeValue(CI),
+ getNode(CI.getOperand(0))));
+ } else {
+ // P1 = cast int --> <Copy/P1/Univ>
+#if 0
+ Constraints.push_back(Constraint(Constraint::Copy, getNodeValue(CI),
+ &GraphNodes[UniversalSet]));
+#else
+ getNodeValue(CI);
+#endif
+ }
+ } else if (isa<PointerType>(Op->getType())) {
+ // int = cast P1 --> <Copy/Univ/P1>
+#if 0
+ Constraints.push_back(Constraint(Constraint::Copy,
+ &GraphNodes[UniversalSet],
+ getNode(CI.getOperand(0))));
+#else
+ getNode(CI.getOperand(0));
+#endif
+ }
+}
+
+void Andersens::visitSelectInst(SelectInst &SI) {
+ if (isa<PointerType>(SI.getType())) {
+ Node *SIN = getNodeValue(SI);
+ // P1 = select C, P2, P3 ---> <Copy/P1/P2>, <Copy/P1/P3>
+ Constraints.push_back(Constraint(Constraint::Copy, SIN,
+ getNode(SI.getOperand(1))));
+ Constraints.push_back(Constraint(Constraint::Copy, SIN,
+ getNode(SI.getOperand(2))));
+ }
+}
+
+void Andersens::visitVAArg(VAArgInst &I) {
+ assert(0 && "vaarg not handled yet!");
+}
+
+/// AddConstraintsForCall - Add constraints for a call with actual arguments
+/// specified by CS to the function specified by F. Note that the types of
+/// arguments might not match up in the case where this is an indirect call and
+/// the function pointer has been casted. If this is the case, do something
+/// reasonable.
+void Andersens::AddConstraintsForCall(CallSite CS, Function *F) {
+ // If this is a call to an external function, handle it directly to get some
+ // taste of context sensitivity.
+ if (F->isDeclaration() && AddConstraintsForExternalCall(CS, F))
+ return;
+
+ if (isa<PointerType>(CS.getType())) {
+ Node *CSN = getNode(CS.getInstruction());
+ if (isa<PointerType>(F->getFunctionType()->getReturnType())) {
+ Constraints.push_back(Constraint(Constraint::Copy, CSN,
+ getReturnNode(F)));
+ } else {
+ // If the function returns a non-pointer value, handle this just like we
+ // treat a nonpointer cast to pointer.
+ Constraints.push_back(Constraint(Constraint::Copy, CSN,
+ &GraphNodes[UniversalSet]));
+ }
+ } else if (isa<PointerType>(F->getFunctionType()->getReturnType())) {
+ Constraints.push_back(Constraint(Constraint::Copy,
+ &GraphNodes[UniversalSet],
+ getReturnNode(F)));
+ }
+
+ Function::arg_iterator AI = F->arg_begin(), AE = F->arg_end();
+ CallSite::arg_iterator ArgI = CS.arg_begin(), ArgE = CS.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),
+ &GraphNodes[UniversalSet]));
+ }
+ } else if (isa<PointerType>((*ArgI)->getType())) {
+ Constraints.push_back(Constraint(Constraint::Copy,
+ &GraphNodes[UniversalSet],
+ getNode(*ArgI)));
+ }
+
+ // Copy all pointers passed through the varargs section to the varargs node.
+ if (F->getFunctionType()->isVarArg())
+ for (; ArgI != ArgE; ++ArgI)
+ if (isa<PointerType>((*ArgI)->getType()))
+ Constraints.push_back(Constraint(Constraint::Copy, getVarargNode(F),
+ getNode(*ArgI)));
+ // If more arguments are passed in than we track, just drop them on the floor.
+}
+
+void Andersens::visitCallSite(CallSite CS) {
+ if (isa<PointerType>(CS.getType()))
+ getNodeValue(*CS.getInstruction());
+
+ if (Function *F = CS.getCalledFunction()) {
+ AddConstraintsForCall(CS, F);
+ } else {
+ // We don't handle indirect call sites yet. Keep track of them for when we
+ // discover the call graph incrementally.
+ IndirectCalls.push_back(CS);
+ }
+}
+
+//===----------------------------------------------------------------------===//
+// Constraint Solving Phase
+//===----------------------------------------------------------------------===//
+
+/// intersects - Return true if the points-to set of this node intersects
+/// with the points-to set of the specified node.
+bool Andersens::Node::intersects(Node *N) const {
+ iterator I1 = begin(), I2 = N->begin(), E1 = end(), E2 = N->end();
+ while (I1 != E1 && I2 != E2) {
+ if (*I1 == *I2) return true;
+ if (*I1 < *I2)
+ ++I1;
+ else
+ ++I2;
+ }
+ return false;
+}
+
+/// intersectsIgnoring - Return true if the points-to set of this node
+/// intersects with the points-to set of the specified node on any nodes
+/// except for the specified node to ignore.
+bool Andersens::Node::intersectsIgnoring(Node *N, Node *Ignoring) const {
+ iterator I1 = begin(), I2 = N->begin(), E1 = end(), E2 = N->end();
+ while (I1 != E1 && I2 != E2) {
+ if (*I1 == *I2) {
+ if (*I1 != Ignoring) return true;
+ ++I1; ++I2;
+ } else if (*I1 < *I2)
+ ++I1;
+ else
+ ++I2;
+ }
+ return false;
+}
+
+// Copy constraint: all edges out of the source node get copied to the
+// destination node. This returns true if a change is made.
+bool Andersens::Node::copyFrom(Node *N) {
+ // Use a mostly linear-time merge since both of the lists are sorted.
+ bool Changed = false;
+ iterator I = N->begin(), E = N->end();
+ unsigned i = 0;
+ while (I != E && i != Pointees.size()) {
+ if (Pointees[i] < *I) {
+ ++i;
+ } else if (Pointees[i] == *I) {
+ ++i; ++I;
+ } else {
+ // We found a new element to copy over.
+ Changed = true;
+ Pointees.insert(Pointees.begin()+i, *I);
+ ++i; ++I;
+ }
+ }
+
+ if (I != E) {
+ Pointees.insert(Pointees.end(), I, E);
+ Changed = true;
+ }
+
+ return Changed;
+}
+
+bool Andersens::Node::loadFrom(Node *N) {
+ bool Changed = false;
+ for (iterator I = N->begin(), E = N->end(); I != E; ++I)
+ Changed |= copyFrom(*I);
+ return Changed;
+}
+
+bool Andersens::Node::storeThrough(Node *N) {
+ bool Changed = false;
+ for (iterator I = begin(), E = end(); I != E; ++I)
+ Changed |= (*I)->copyFrom(N);
+ return Changed;
+}
+
+
+/// SolveConstraints - This stage iteratively processes the constraints list
+/// propagating constraints (adding edges to the Nodes in the points-to graph)
+/// until a fixed point is reached.
+///
+void Andersens::SolveConstraints() {
+ bool Changed = true;
+ unsigned Iteration = 0;
+ while (Changed) {
+ Changed = false;
+ ++NumIters;
+ DOUT << "Starting iteration #" << Iteration++ << "!\n";
+
+ // Loop over all of the constraints, applying them in turn.
+ for (unsigned i = 0, e = Constraints.size(); i != e; ++i) {
+ Constraint &C = Constraints[i];
+ switch (C.Type) {
+ case Constraint::Copy:
+ Changed |= C.Dest->copyFrom(C.Src);
+ break;
+ case Constraint::Load:
+ Changed |= C.Dest->loadFrom(C.Src);
+ break;
+ case Constraint::Store:
+ Changed |= C.Dest->storeThrough(C.Src);
+ break;
+ default:
+ assert(0 && "Unknown constraint!");
+ }
+ }
+
+ if (Changed) {
+ // Check to see if any internal function's addresses have been passed to
+ // external functions. If so, we have to assume that their incoming
+ // arguments could be anything. If there are any internal functions in
+ // the universal node that we don't know about, we must iterate.
+ for (Node::iterator I = GraphNodes[UniversalSet].begin(),
+ E = GraphNodes[UniversalSet].end(); I != E; ++I)
+ if (Function *F = dyn_cast_or_null<Function>((*I)->getValue()))
+ if (F->hasInternalLinkage() &&
+ EscapingInternalFunctions.insert(F).second) {
+ // We found a function that is just now escaping. Mark it as if it
+ // didn't have internal linkage.
+ AddConstraintsForNonInternalLinkage(F);
+ DOUT << "Found escaping internal function: " << F->getName() <<"\n";
+ ++NumEscapingFunctions;
+ }
+
+ // Check to see if we have discovered any new callees of the indirect call
+ // sites. If so, add constraints to the analysis.
+ for (unsigned i = 0, e = IndirectCalls.size(); i != e; ++i) {
+ CallSite CS = IndirectCalls[i];
+ std::vector<Function*> &KnownCallees = IndirectCallees[CS];
+ Node *CN = getNode(CS.getCalledValue());
+
+ for (Node::iterator NI = CN->begin(), E = CN->end(); NI != E; ++NI)
+ if (Function *F = dyn_cast_or_null<Function>((*NI)->getValue())) {
+ std::vector<Function*>::iterator IP =
+ std::lower_bound(KnownCallees.begin(), KnownCallees.end(), F);
+ if (IP == KnownCallees.end() || *IP != F) {
+ // Add the constraints for the call now.
+ AddConstraintsForCall(CS, F);
+ DOUT << "Found actual callee '"
+ << F->getName() << "' for call: "
+ << *CS.getInstruction() << "\n";
+ ++NumIndirectCallees;
+ KnownCallees.insert(IP, F);
+ }
+ }
+ }
+ }
+ }
+}
+
+
+
+//===----------------------------------------------------------------------===//
+// Debugging Output
+//===----------------------------------------------------------------------===//
+
+void Andersens::PrintNode(Node *N) {
+ if (N == &GraphNodes[UniversalSet]) {
+ cerr << "<universal>";
+ return;
+ } else if (N == &GraphNodes[NullPtr]) {
+ cerr << "<nullptr>";
+ return;
+ } else if (N == &GraphNodes[NullObject]) {
+ cerr << "<null>";
+ return;
+ }
+
+ assert(N->getValue() != 0 && "Never set node label!");
+ Value *V = N->getValue();
+ if (Function *F = dyn_cast<Function>(V)) {
+ if (isa<PointerType>(F->getFunctionType()->getReturnType()) &&
+ N == getReturnNode(F)) {
+ cerr << F->getName() << ":retval";
+ return;
+ } else if (F->getFunctionType()->isVarArg() && N == getVarargNode(F)) {
+ cerr << F->getName() << ":vararg";
+ return;
+ }
+ }
+
+ if (Instruction *I = dyn_cast<Instruction>(V))
+ cerr << I->getParent()->getParent()->getName() << ":";
+ else if (Argument *Arg = dyn_cast<Argument>(V))
+ cerr << Arg->getParent()->getName() << ":";
+
+ if (V->hasName())
+ cerr << V->getName();
+ else
+ cerr << "(unnamed)";
+
+ if (isa<GlobalValue>(V) || isa<AllocationInst>(V))
+ if (N == getObject(V))
+ cerr << "<mem>";
+}
+
+void Andersens::PrintConstraints() {
+ cerr << "Constraints:\n";
+ for (unsigned i = 0, e = Constraints.size(); i != e; ++i) {
+ cerr << " #" << i << ": ";
+ Constraint &C = Constraints[i];
+ if (C.Type == Constraint::Store)
+ cerr << "*";
+ PrintNode(C.Dest);
+ cerr << " = ";
+ if (C.Type == Constraint::Load)
+ cerr << "*";
+ PrintNode(C.Src);
+ cerr << "\n";
+ }
+}
+
+void Andersens::PrintPointsToGraph() {
+ cerr << "Points-to graph:\n";
+ for (unsigned i = 0, e = GraphNodes.size(); i != e; ++i) {
+ Node *N = &GraphNodes[i];
+ cerr << "[" << (N->end() - N->begin()) << "] ";
+ PrintNode(N);
+ cerr << "\t--> ";
+ for (Node::iterator I = N->begin(), E = N->end(); I != E; ++I) {
+ if (I != N->begin()) cerr << ", ";
+ PrintNode(*I);
+ }
+ cerr << "\n";
+ }
+}
diff --git a/lib/Analysis/IPA/CallGraph.cpp b/lib/Analysis/IPA/CallGraph.cpp
new file mode 100644
index 0000000..5f9850c
--- /dev/null
+++ b/lib/Analysis/IPA/CallGraph.cpp
@@ -0,0 +1,309 @@
+//===- CallGraph.cpp - Build a Module's call graph ------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the CallGraph class and provides the BasicCallGraph
+// default implementation.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/CallGraph.h"
+#include "llvm/Module.h"
+#include "llvm/Instructions.h"
+#include "llvm/Support/CallSite.h"
+#include "llvm/Support/Compiler.h"
+#include "llvm/Support/Streams.h"
+#include <ostream>
+using namespace llvm;
+
+/// isOnlyADirectCall - Return true if this callsite is *just* a direct call to
+/// the specified function. Specifically return false if the callsite also
+/// takes the address of the function.
+static bool isOnlyADirectCall(Function *F, CallSite CS) {
+ if (!CS.getInstruction()) return false;
+ for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); I != E; ++I)
+ if (*I == F) return false;
+ return true;
+}
+
+namespace {
+
+//===----------------------------------------------------------------------===//
+// BasicCallGraph class definition
+//
+class VISIBILITY_HIDDEN BasicCallGraph : public CallGraph, public ModulePass {
+ // Root is root of the call graph, or the external node if a 'main' function
+ // couldn't be found.
+ //
+ CallGraphNode *Root;
+
+ // ExternalCallingNode - This node has edges to all external functions and
+ // those internal functions that have their address taken.
+ CallGraphNode *ExternalCallingNode;
+
+ // CallsExternalNode - This node has edges to it from all functions making
+ // indirect calls or calling an external function.
+ CallGraphNode *CallsExternalNode;
+
+public:
+ static char ID; // Class identification, replacement for typeinfo
+ BasicCallGraph() : ModulePass((intptr_t)&ID), Root(0),
+ ExternalCallingNode(0), CallsExternalNode(0) {}
+
+ // runOnModule - Compute the call graph for the specified module.
+ virtual bool runOnModule(Module &M) {
+ CallGraph::initialize(M);
+
+ ExternalCallingNode = getOrInsertFunction(0);
+ CallsExternalNode = new CallGraphNode(0);
+ Root = 0;
+
+ // Add every function to the call graph...
+ for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
+ addToCallGraph(I);
+
+ // If we didn't find a main function, use the external call graph node
+ if (Root == 0) Root = ExternalCallingNode;
+
+ return false;
+ }
+
+ virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.setPreservesAll();
+ }
+
+ void print(std::ostream *o, const Module *M) const {
+ if (o) print(*o, M);
+ }
+
+ virtual void print(std::ostream &o, const Module *M) const {
+ o << "CallGraph Root is: ";
+ if (Function *F = getRoot()->getFunction())
+ o << F->getName() << "\n";
+ else
+ o << "<<null function: 0x" << getRoot() << ">>\n";
+
+ CallGraph::print(o, M);
+ }
+
+ virtual void releaseMemory() {
+ destroy();
+ }
+
+ /// dump - Print out this call graph.
+ ///
+ inline void dump() const {
+ print(cerr, Mod);
+ }
+
+ CallGraphNode* getExternalCallingNode() const { return ExternalCallingNode; }
+ CallGraphNode* getCallsExternalNode() const { return CallsExternalNode; }
+
+ // getRoot - Return the root of the call graph, which is either main, or if
+ // main cannot be found, the external node.
+ //
+ CallGraphNode *getRoot() { return Root; }
+ const CallGraphNode *getRoot() const { return Root; }
+
+private:
+ //===---------------------------------------------------------------------
+ // Implementation of CallGraph construction
+ //
+
+ // addToCallGraph - Add a function to the call graph, and link the node to all
+ // of the functions that it calls.
+ //
+ void addToCallGraph(Function *F) {
+ CallGraphNode *Node = getOrInsertFunction(F);
+
+ // If this function has external linkage, anything could call it.
+ if (!F->hasInternalLinkage()) {
+ ExternalCallingNode->addCalledFunction(CallSite(), Node);
+
+ // Found the entry point?
+ if (F->getName() == "main") {
+ if (Root) // Found multiple external mains? Don't pick one.
+ Root = ExternalCallingNode;
+ else
+ Root = Node; // Found a main, keep track of it!
+ }
+ }
+
+ // If this function is not defined in this translation unit, it could call
+ // anything.
+ if (F->isDeclaration() && !F->getIntrinsicID())
+ Node->addCalledFunction(CallSite(), CallsExternalNode);
+
+ // Loop over all of the users of the function... looking for callers...
+ //
+ bool isUsedExternally = false;
+ for (Value::use_iterator I = F->use_begin(), E = F->use_end(); I != E; ++I){
+ if (Instruction *Inst = dyn_cast<Instruction>(*I)) {
+ CallSite CS = CallSite::get(Inst);
+ if (isOnlyADirectCall(F, CS))
+ getOrInsertFunction(Inst->getParent()->getParent())
+ ->addCalledFunction(CS, Node);
+ else
+ isUsedExternally = true;
+ } else if (GlobalValue *GV = dyn_cast<GlobalValue>(*I)) {
+ for (Value::use_iterator I = GV->use_begin(), E = GV->use_end();
+ I != E; ++I)
+ if (Instruction *Inst = dyn_cast<Instruction>(*I)) {
+ CallSite CS = CallSite::get(Inst);
+ if (isOnlyADirectCall(F, CS))
+ getOrInsertFunction(Inst->getParent()->getParent())
+ ->addCalledFunction(CS, Node);
+ else
+ isUsedExternally = true;
+ } else {
+ isUsedExternally = true;
+ }
+ } else { // Can't classify the user!
+ isUsedExternally = true;
+ }
+ }
+ if (isUsedExternally)
+ ExternalCallingNode->addCalledFunction(CallSite(), Node);
+
+ // Look for an indirect function call.
+ for (Function::iterator BB = F->begin(), BBE = F->end(); BB != BBE; ++BB)
+ for (BasicBlock::iterator II = BB->begin(), IE = BB->end();
+ II != IE; ++II) {
+ CallSite CS = CallSite::get(II);
+ if (CS.getInstruction() && !CS.getCalledFunction())
+ Node->addCalledFunction(CS, CallsExternalNode);
+ }
+ }
+
+ //
+ // destroy - Release memory for the call graph
+ virtual void destroy() {
+ /// CallsExternalNode is not in the function map, delete it explicitly.
+ delete CallsExternalNode;
+ CallsExternalNode = 0;
+ CallGraph::destroy();
+ }
+};
+
+RegisterAnalysisGroup<CallGraph> X("Call Graph");
+RegisterPass<BasicCallGraph> Y("basiccg", "Basic CallGraph Construction");
+RegisterAnalysisGroup<CallGraph, true> Z(Y);
+
+} //End anonymous namespace
+
+char CallGraph::ID = 0;
+char BasicCallGraph::ID = 0;
+
+void CallGraph::initialize(Module &M) {
+ Mod = &M;
+}
+
+void CallGraph::destroy() {
+ if (!FunctionMap.empty()) {
+ for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end();
+ I != E; ++I)
+ delete I->second;
+ FunctionMap.clear();
+ }
+}
+
+void CallGraph::print(std::ostream &OS, const Module *M) const {
+ for (CallGraph::const_iterator I = begin(), E = end(); I != E; ++I)
+ I->second->print(OS);
+}
+
+void CallGraph::dump() const {
+ print(cerr, 0);
+}
+
+//===----------------------------------------------------------------------===//
+// Implementations of public modification methods
+//
+
+// removeFunctionFromModule - Unlink the function from this module, returning
+// it. Because this removes the function from the module, the call graph node
+// is destroyed. This is only valid if the function does not call any other
+// functions (ie, there are no edges in it's CGN). The easiest way to do this
+// is to dropAllReferences before calling this.
+//
+Function *CallGraph::removeFunctionFromModule(CallGraphNode *CGN) {
+ assert(CGN->CalledFunctions.empty() && "Cannot remove function from call "
+ "graph if it references other functions!");
+ Function *F = CGN->getFunction(); // Get the function for the call graph node
+ delete CGN; // Delete the call graph node for this func
+ FunctionMap.erase(F); // Remove the call graph node from the map
+
+ Mod->getFunctionList().remove(F);
+ return F;
+}
+
+// changeFunction - This method changes the function associated with this
+// CallGraphNode, for use by transformations that need to change the prototype
+// of a Function (thus they must create a new Function and move the old code
+// over).
+void CallGraph::changeFunction(Function *OldF, Function *NewF) {
+ iterator I = FunctionMap.find(OldF);
+ CallGraphNode *&New = FunctionMap[NewF];
+ assert(I != FunctionMap.end() && I->second && !New &&
+ "OldF didn't exist in CG or NewF already does!");
+ New = I->second;
+ New->F = NewF;
+ FunctionMap.erase(I);
+}
+
+// getOrInsertFunction - This method is identical to calling operator[], but
+// it will insert a new CallGraphNode for the specified function if one does
+// not already exist.
+CallGraphNode *CallGraph::getOrInsertFunction(const Function *F) {
+ CallGraphNode *&CGN = FunctionMap[F];
+ if (CGN) return CGN;
+
+ assert((!F || F->getParent() == Mod) && "Function not in current module!");
+ return CGN = new CallGraphNode(const_cast<Function*>(F));
+}
+
+void CallGraphNode::print(std::ostream &OS) const {
+ if (Function *F = getFunction())
+ OS << "Call graph node for function: '" << F->getName() <<"'\n";
+ else
+ OS << "Call graph node <<null function: 0x" << this << ">>:\n";
+
+ for (const_iterator I = begin(), E = end(); I != E; ++I)
+ if (I->second->getFunction())
+ OS << " Calls function '" << I->second->getFunction()->getName() <<"'\n";
+ else
+ OS << " Calls external node\n";
+ OS << "\n";
+}
+
+void CallGraphNode::dump() const { print(cerr); }
+
+void CallGraphNode::removeCallEdgeTo(CallGraphNode *Callee) {
+ for (unsigned i = CalledFunctions.size(); ; --i) {
+ assert(i && "Cannot find callee to remove!");
+ if (CalledFunctions[i-1].second == Callee) {
+ CalledFunctions.erase(CalledFunctions.begin()+i-1);
+ return;
+ }
+ }
+}
+
+// removeAnyCallEdgeTo - This method removes any call edges from this node to
+// the specified callee function. This takes more time to execute than
+// removeCallEdgeTo, so it should not be used unless necessary.
+void CallGraphNode::removeAnyCallEdgeTo(CallGraphNode *Callee) {
+ for (unsigned i = 0, e = CalledFunctions.size(); i != e; ++i)
+ if (CalledFunctions[i].second == Callee) {
+ CalledFunctions[i] = CalledFunctions.back();
+ CalledFunctions.pop_back();
+ --i; --e;
+ }
+}
+
+// Enuse that users of CallGraph.h also link with this file
+DEFINING_FILE_FOR(CallGraph)
diff --git a/lib/Analysis/IPA/CallGraphSCCPass.cpp b/lib/Analysis/IPA/CallGraphSCCPass.cpp
new file mode 100644
index 0000000..a7e9dd0
--- /dev/null
+++ b/lib/Analysis/IPA/CallGraphSCCPass.cpp
@@ -0,0 +1,196 @@
+//===- CallGraphSCCPass.cpp - Pass that operates BU on call graph ---------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the CallGraphSCCPass class, which is used for passes
+// which are implemented as bottom-up traversals on the call graph. Because
+// there may be cycles in the call graph, passes of this type operate on the
+// call-graph in SCC order: that is, they process function bottom-up, except for
+// recursive functions, which they process all at once.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CallGraphSCCPass.h"
+#include "llvm/Analysis/CallGraph.h"
+#include "llvm/ADT/SCCIterator.h"
+#include "llvm/PassManagers.h"
+#include "llvm/Function.h"
+using namespace llvm;
+
+//===----------------------------------------------------------------------===//
+// CGPassManager
+//
+/// CGPassManager manages FPPassManagers and CalLGraphSCCPasses.
+
+class CGPassManager : public ModulePass, public PMDataManager {
+
+public:
+ static char ID;
+ CGPassManager(int Depth)
+ : ModulePass((intptr_t)&ID), PMDataManager(Depth) { }
+
+ /// run - Execute all of the passes scheduled for execution. Keep track of
+ /// whether any of the passes modifies the module, and if so, return true.
+ bool runOnModule(Module &M);
+
+ bool doInitialization(CallGraph &CG);
+ bool doFinalization(CallGraph &CG);
+
+ /// Pass Manager itself does not invalidate any analysis info.
+ void getAnalysisUsage(AnalysisUsage &Info) const {
+ // CGPassManager walks SCC and it needs CallGraph.
+ Info.addRequired<CallGraph>();
+ Info.setPreservesAll();
+ }
+
+ virtual const char *getPassName() const {
+ return "CallGraph Pass Manager";
+ }
+
+ // Print passes managed by this manager
+ void dumpPassStructure(unsigned Offset) {
+ llvm::cerr << std::string(Offset*2, ' ') << "Call Graph SCC Pass Manager\n";
+ for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
+ Pass *P = getContainedPass(Index);
+ P->dumpPassStructure(Offset + 1);
+ dumpLastUses(P, Offset+1);
+ }
+ }
+
+ Pass *getContainedPass(unsigned N) {
+ assert ( N < PassVector.size() && "Pass number out of range!");
+ Pass *FP = static_cast<Pass *>(PassVector[N]);
+ return FP;
+ }
+
+ virtual PassManagerType getPassManagerType() const {
+ return PMT_CallGraphPassManager;
+ }
+};
+
+char CGPassManager::ID = 0;
+/// run - Execute all of the passes scheduled for execution. Keep track of
+/// whether any of the passes modifies the module, and if so, return true.
+bool CGPassManager::runOnModule(Module &M) {
+ CallGraph &CG = getAnalysis<CallGraph>();
+ bool Changed = doInitialization(CG);
+
+ // Walk SCC
+ for (scc_iterator<CallGraph*> I = scc_begin(&CG), E = scc_end(&CG);
+ I != E; ++I) {
+
+ // Run all passes on current SCC
+ for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
+ Pass *P = getContainedPass(Index);
+ AnalysisUsage AnUsage;
+ P->getAnalysisUsage(AnUsage);
+
+ dumpPassInfo(P, EXECUTION_MSG, ON_CG_MSG, "");
+ dumpAnalysisSetInfo("Required", P, AnUsage.getRequiredSet());
+
+ initializeAnalysisImpl(P);
+
+ StartPassTimer(P);
+ if (CallGraphSCCPass *CGSP = dynamic_cast<CallGraphSCCPass *>(P))
+ Changed |= CGSP->runOnSCC(*I); // TODO : What if CG is changed ?
+ else {
+ FPPassManager *FPP = dynamic_cast<FPPassManager *>(P);
+ assert (FPP && "Invalid CGPassManager member");
+
+ // Run pass P on all functions current SCC
+ std::vector<CallGraphNode*> &SCC = *I;
+ for (unsigned i = 0, e = SCC.size(); i != e; ++i) {
+ Function *F = SCC[i]->getFunction();
+ if (F) {
+ dumpPassInfo(P, EXECUTION_MSG, ON_FUNCTION_MSG, F->getName());
+ Changed |= FPP->runOnFunction(*F);
+ }
+ }
+ }
+ StopPassTimer(P);
+
+ if (Changed)
+ dumpPassInfo(P, MODIFICATION_MSG, ON_CG_MSG, "");
+ dumpAnalysisSetInfo("Preserved", P, AnUsage.getPreservedSet());
+
+ removeNotPreservedAnalysis(P);
+ recordAvailableAnalysis(P);
+ removeDeadPasses(P, "", ON_CG_MSG);
+ }
+ }
+ Changed |= doFinalization(CG);
+ return Changed;
+}
+
+/// Initialize CG
+bool CGPassManager::doInitialization(CallGraph &CG) {
+ bool Changed = false;
+ for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
+ Pass *P = getContainedPass(Index);
+ if (CallGraphSCCPass *CGSP = dynamic_cast<CallGraphSCCPass *>(P))
+ Changed |= CGSP->doInitialization(CG);
+ }
+ return Changed;
+}
+
+/// Finalize CG
+bool CGPassManager::doFinalization(CallGraph &CG) {
+ bool Changed = false;
+ for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
+ Pass *P = getContainedPass(Index);
+ if (CallGraphSCCPass *CGSP = dynamic_cast<CallGraphSCCPass *>(P))
+ Changed |= CGSP->doFinalization(CG);
+ }
+ return Changed;
+}
+
+/// Assign pass manager to manage this pass.
+void CallGraphSCCPass::assignPassManager(PMStack &PMS,
+ PassManagerType PreferredType) {
+ // Find CGPassManager
+ while (!PMS.empty()) {
+ if (PMS.top()->getPassManagerType() > PMT_CallGraphPassManager)
+ PMS.pop();
+ else;
+ break;
+ }
+
+ CGPassManager *CGP = dynamic_cast<CGPassManager *>(PMS.top());
+
+ // Create new Call Graph SCC Pass Manager if it does not exist.
+ if (!CGP) {
+
+ assert (!PMS.empty() && "Unable to create Call Graph Pass Manager");
+ PMDataManager *PMD = PMS.top();
+
+ // [1] Create new Call Graph Pass Manager
+ CGP = new CGPassManager(PMD->getDepth() + 1);
+
+ // [2] Set up new manager's top level manager
+ PMTopLevelManager *TPM = PMD->getTopLevelManager();
+ TPM->addIndirectPassManager(CGP);
+
+ // [3] Assign manager to manage this new manager. This may create
+ // and push new managers into PMS
+ Pass *P = dynamic_cast<Pass *>(CGP);
+ TPM->schedulePass(P);
+
+ // [4] Push new manager into PMS
+ PMS.push(CGP);
+ }
+
+ CGP->add(this);
+}
+
+/// getAnalysisUsage - For this class, we declare that we require and preserve
+/// the call graph. If the derived class implements this method, it should
+/// always explicitly call the implementation here.
+void CallGraphSCCPass::getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.addRequired<CallGraph>();
+ AU.addPreserved<CallGraph>();
+}
diff --git a/lib/Analysis/IPA/FindUsedTypes.cpp b/lib/Analysis/IPA/FindUsedTypes.cpp
new file mode 100644
index 0000000..a954414
--- /dev/null
+++ b/lib/Analysis/IPA/FindUsedTypes.cpp
@@ -0,0 +1,101 @@
+//===- FindUsedTypes.cpp - Find all Types used by a module ----------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass is used to seek out all of the types in use by the program. Note
+// that this analysis explicitly does not include types only used by the symbol
+// table.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/FindUsedTypes.h"
+#include "llvm/Constants.h"
+#include "llvm/DerivedTypes.h"
+#include "llvm/Module.h"
+#include "llvm/Assembly/Writer.h"
+#include "llvm/Support/InstIterator.h"
+using namespace llvm;
+
+char FindUsedTypes::ID = 0;
+static RegisterPass<FindUsedTypes>
+X("printusedtypes", "Find Used Types");
+
+// IncorporateType - Incorporate one type and all of its subtypes into the
+// collection of used types.
+//
+void FindUsedTypes::IncorporateType(const Type *Ty) {
+ // If ty doesn't already exist in the used types map, add it now, otherwise
+ // return.
+ if (!UsedTypes.insert(Ty).second) return; // Already contain Ty.
+
+ // Make sure to add any types this type references now.
+ //
+ for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end();
+ I != E; ++I)
+ IncorporateType(*I);
+}
+
+void FindUsedTypes::IncorporateValue(const Value *V) {
+ IncorporateType(V->getType());
+
+ // If this is a constant, it could be using other types...
+ if (const Constant *C = dyn_cast<Constant>(V)) {
+ if (!isa<GlobalValue>(C))
+ for (User::const_op_iterator OI = C->op_begin(), OE = C->op_end();
+ OI != OE; ++OI)
+ IncorporateValue(*OI);
+ }
+}
+
+
+// run - This incorporates all types used by the specified module
+//
+bool FindUsedTypes::runOnModule(Module &m) {
+ UsedTypes.clear(); // reset if run multiple times...
+
+ // Loop over global variables, incorporating their types
+ for (Module::const_global_iterator I = m.global_begin(), E = m.global_end(); I != E; ++I) {
+ IncorporateType(I->getType());
+ if (I->hasInitializer())
+ IncorporateValue(I->getInitializer());
+ }
+
+ for (Module::iterator MI = m.begin(), ME = m.end(); MI != ME; ++MI) {
+ IncorporateType(MI->getType());
+ const Function &F = *MI;
+
+ // Loop over all of the instructions in the function, adding their return
+ // type as well as the types of their operands.
+ //
+ for (const_inst_iterator II = inst_begin(F), IE = inst_end(F);
+ II != IE; ++II) {
+ const Instruction &I = *II;
+
+ IncorporateType(I.getType()); // Incorporate the type of the instruction
+ for (User::const_op_iterator OI = I.op_begin(), OE = I.op_end();
+ OI != OE; ++OI)
+ IncorporateValue(*OI); // Insert inst operand types as well
+ }
+ }
+
+ return false;
+}
+
+// Print the types found in the module. If the optional Module parameter is
+// passed in, then the types are printed symbolically if possible, using the
+// symbol table from the module.
+//
+void FindUsedTypes::print(std::ostream &o, const Module *M) const {
+ o << "Types in use by this module:\n";
+ for (std::set<const Type *>::const_iterator I = UsedTypes.begin(),
+ E = UsedTypes.end(); I != E; ++I)
+ WriteTypeSymbolic(o << " ", *I, M) << "\n";
+}
+
+// Ensure that this file gets linked in when FindUsedTypes.h is used.
+DEFINING_FILE_FOR(FindUsedTypes)
diff --git a/lib/Analysis/IPA/GlobalsModRef.cpp b/lib/Analysis/IPA/GlobalsModRef.cpp
new file mode 100644
index 0000000..63ddb89
--- /dev/null
+++ b/lib/Analysis/IPA/GlobalsModRef.cpp
@@ -0,0 +1,554 @@
+//===- GlobalsModRef.cpp - Simple Mod/Ref Analysis for Globals ------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This simple pass provides alias and mod/ref information for global values
+// that do not have their address taken, and keeps track of whether functions
+// read or write memory (are "pure"). For this simple (but very common) case,
+// we can provide pretty accurate and useful information.
+//
+//===----------------------------------------------------------------------===//
+
+#define DEBUG_TYPE "globalsmodref-aa"
+#include "llvm/Analysis/Passes.h"
+#include "llvm/Module.h"
+#include "llvm/Pass.h"
+#include "llvm/Instructions.h"
+#include "llvm/Constants.h"
+#include "llvm/DerivedTypes.h"
+#include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Analysis/CallGraph.h"
+#include "llvm/Support/Compiler.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/InstIterator.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/ADT/SCCIterator.h"
+#include <set>
+using namespace llvm;
+
+STATISTIC(NumNonAddrTakenGlobalVars,
+ "Number of global vars without address taken");
+STATISTIC(NumNonAddrTakenFunctions,"Number of functions without address taken");
+STATISTIC(NumNoMemFunctions, "Number of functions that do not access memory");
+STATISTIC(NumReadMemFunctions, "Number of functions that only read memory");
+STATISTIC(NumIndirectGlobalVars, "Number of indirect global objects");
+
+namespace {
+ /// FunctionRecord - One instance of this structure is stored for every
+ /// function in the program. Later, the entries for these functions are
+ /// removed if the function is found to call an external function (in which
+ /// case we know nothing about it.
+ struct VISIBILITY_HIDDEN FunctionRecord {
+ /// GlobalInfo - Maintain mod/ref info for all of the globals without
+ /// addresses taken that are read or written (transitively) by this
+ /// function.
+ std::map<GlobalValue*, unsigned> GlobalInfo;
+
+ unsigned getInfoForGlobal(GlobalValue *GV) const {
+ std::map<GlobalValue*, unsigned>::const_iterator I = GlobalInfo.find(GV);
+ if (I != GlobalInfo.end())
+ return I->second;
+ return 0;
+ }
+
+ /// FunctionEffect - Capture whether or not this function reads or writes to
+ /// ANY memory. If not, we can do a lot of aggressive analysis on it.
+ unsigned FunctionEffect;
+
+ FunctionRecord() : FunctionEffect(0) {}
+ };
+
+ /// GlobalsModRef - The actual analysis pass.
+ class VISIBILITY_HIDDEN GlobalsModRef
+ : public ModulePass, public AliasAnalysis {
+ /// NonAddressTakenGlobals - The globals that do not have their addresses
+ /// taken.
+ std::set<GlobalValue*> NonAddressTakenGlobals;
+
+ /// IndirectGlobals - The memory pointed to by this global is known to be
+ /// 'owned' by the global.
+ std::set<GlobalValue*> IndirectGlobals;
+
+ /// AllocsForIndirectGlobals - If an instruction allocates memory for an
+ /// indirect global, this map indicates which one.
+ std::map<Value*, GlobalValue*> AllocsForIndirectGlobals;
+
+ /// FunctionInfo - For each function, keep track of what globals are
+ /// modified or read.
+ std::map<Function*, FunctionRecord> FunctionInfo;
+
+ public:
+ static char ID;
+ GlobalsModRef() : ModulePass((intptr_t)&ID) {}
+
+ bool runOnModule(Module &M) {
+ InitializeAliasAnalysis(this); // set up super class
+ AnalyzeGlobals(M); // find non-addr taken globals
+ AnalyzeCallGraph(getAnalysis<CallGraph>(), M); // Propagate on CG
+ return false;
+ }
+
+ virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+ AliasAnalysis::getAnalysisUsage(AU);
+ AU.addRequired<CallGraph>();
+ AU.setPreservesAll(); // Does not transform code
+ }
+
+ //------------------------------------------------
+ // Implement the AliasAnalysis API
+ //
+ AliasResult alias(const Value *V1, unsigned V1Size,
+ const Value *V2, unsigned V2Size);
+ ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size);
+ ModRefResult getModRefInfo(CallSite CS1, CallSite CS2) {
+ return AliasAnalysis::getModRefInfo(CS1,CS2);
+ }
+ bool hasNoModRefInfoForCalls() const { return false; }
+
+ /// getModRefBehavior - Return the behavior of the specified function if
+ /// called from the specified call site. The call site may be null in which
+ /// case the most generic behavior of this function should be returned.
+ virtual ModRefBehavior getModRefBehavior(Function *F, CallSite CS,
+ std::vector<PointerAccessInfo> *Info) {
+ if (FunctionRecord *FR = getFunctionInfo(F))
+ if (FR->FunctionEffect == 0)
+ return DoesNotAccessMemory;
+ else if ((FR->FunctionEffect & Mod) == 0)
+ return OnlyReadsMemory;
+ return AliasAnalysis::getModRefBehavior(F, CS, Info);
+ }
+
+ virtual void deleteValue(Value *V);
+ virtual void copyValue(Value *From, Value *To);
+
+ private:
+ /// getFunctionInfo - Return the function info for the function, or null if
+ /// the function calls an external function (in which case we don't have
+ /// anything useful to say about it).
+ FunctionRecord *getFunctionInfo(Function *F) {
+ std::map<Function*, FunctionRecord>::iterator I = FunctionInfo.find(F);
+ if (I != FunctionInfo.end())
+ return &I->second;
+ return 0;
+ }
+
+ void AnalyzeGlobals(Module &M);
+ void AnalyzeCallGraph(CallGraph &CG, Module &M);
+ void AnalyzeSCC(std::vector<CallGraphNode *> &SCC);
+ bool AnalyzeUsesOfPointer(Value *V, std::vector<Function*> &Readers,
+ std::vector<Function*> &Writers,
+ GlobalValue *OkayStoreDest = 0);
+ bool AnalyzeIndirectGlobalMemory(GlobalValue *GV);
+ };
+
+ char GlobalsModRef::ID = 0;
+ RegisterPass<GlobalsModRef> X("globalsmodref-aa",
+ "Simple mod/ref analysis for globals");
+ RegisterAnalysisGroup<AliasAnalysis> Y(X);
+}
+
+Pass *llvm::createGlobalsModRefPass() { return new GlobalsModRef(); }
+
+/// getUnderlyingObject - This traverses the use chain to figure out what object
+/// the specified value points to. If the value points to, or is derived from,
+/// a global object, return it.
+static Value *getUnderlyingObject(Value *V) {
+ if (!isa<PointerType>(V->getType())) return V;
+
+ // If we are at some type of object... return it.
+ if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) return GV;
+
+ // Traverse through different addressing mechanisms.
+ if (Instruction *I = dyn_cast<Instruction>(V)) {
+ if (isa<BitCastInst>(I) || isa<GetElementPtrInst>(I))
+ return getUnderlyingObject(I->getOperand(0));
+ } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
+ if (CE->getOpcode() == Instruction::BitCast ||
+ CE->getOpcode() == Instruction::GetElementPtr)
+ return getUnderlyingObject(CE->getOperand(0));
+ }
+
+ // Othewise, we don't know what this is, return it as the base pointer.
+ return V;
+}
+
+/// AnalyzeGlobals - Scan through the users of all of the internal
+/// GlobalValue's in the program. If none of them have their "Address taken"
+/// (really, their address passed to something nontrivial), record this fact,
+/// and record the functions that they are used directly in.
+void GlobalsModRef::AnalyzeGlobals(Module &M) {
+ std::vector<Function*> Readers, Writers;
+ for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
+ if (I->hasInternalLinkage()) {
+ if (!AnalyzeUsesOfPointer(I, Readers, Writers)) {
+ // Remember that we are tracking this global.
+ NonAddressTakenGlobals.insert(I);
+ ++NumNonAddrTakenFunctions;
+ }
+ Readers.clear(); Writers.clear();
+ }
+
+ for (Module::global_iterator I = M.global_begin(), E = M.global_end();
+ I != E; ++I)
+ if (I->hasInternalLinkage()) {
+ if (!AnalyzeUsesOfPointer(I, Readers, Writers)) {
+ // Remember that we are tracking this global, and the mod/ref fns
+ NonAddressTakenGlobals.insert(I);
+ for (unsigned i = 0, e = Readers.size(); i != e; ++i)
+ FunctionInfo[Readers[i]].GlobalInfo[I] |= Ref;
+
+ if (!I->isConstant()) // No need to keep track of writers to constants
+ for (unsigned i = 0, e = Writers.size(); i != e; ++i)
+ FunctionInfo[Writers[i]].GlobalInfo[I] |= Mod;
+ ++NumNonAddrTakenGlobalVars;
+
+ // If this global holds a pointer type, see if it is an indirect global.
+ if (isa<PointerType>(I->getType()->getElementType()) &&
+ AnalyzeIndirectGlobalMemory(I))
+ ++NumIndirectGlobalVars;
+ }
+ Readers.clear(); Writers.clear();
+ }
+}
+
+/// AnalyzeUsesOfPointer - Look at all of the users of the specified pointer.
+/// If this is used by anything complex (i.e., the address escapes), return
+/// true. Also, while we are at it, keep track of those functions that read and
+/// write to the value.
+///
+/// If OkayStoreDest is non-null, stores into this global are allowed.
+bool GlobalsModRef::AnalyzeUsesOfPointer(Value *V,
+ std::vector<Function*> &Readers,
+ std::vector<Function*> &Writers,
+ GlobalValue *OkayStoreDest) {
+ if (!isa<PointerType>(V->getType())) return true;
+
+ for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ++UI)
+ if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) {
+ Readers.push_back(LI->getParent()->getParent());
+ } else if (StoreInst *SI = dyn_cast<StoreInst>(*UI)) {
+ if (V == SI->getOperand(1)) {
+ Writers.push_back(SI->getParent()->getParent());
+ } else if (SI->getOperand(1) != OkayStoreDest) {
+ return true; // Storing the pointer
+ }
+ } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(*UI)) {
+ if (AnalyzeUsesOfPointer(GEP, Readers, Writers)) return true;
+ } else if (CallInst *CI = dyn_cast<CallInst>(*UI)) {
+ // Make sure that this is just the function being called, not that it is
+ // passing into the function.
+ for (unsigned i = 1, e = CI->getNumOperands(); i != e; ++i)
+ if (CI->getOperand(i) == V) return true;
+ } else if (InvokeInst *II = dyn_cast<InvokeInst>(*UI)) {
+ // Make sure that this is just the function being called, not that it is
+ // passing into the function.
+ for (unsigned i = 3, e = II->getNumOperands(); i != e; ++i)
+ if (II->getOperand(i) == V) return true;
+ } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(*UI)) {
+ if (CE->getOpcode() == Instruction::GetElementPtr ||
+ CE->getOpcode() == Instruction::BitCast) {
+ if (AnalyzeUsesOfPointer(CE, Readers, Writers))
+ return true;
+ } else {
+ return true;
+ }
+ } else if (ICmpInst *ICI = dyn_cast<ICmpInst>(*UI)) {
+ if (!isa<ConstantPointerNull>(ICI->getOperand(1)))
+ return true; // Allow comparison against null.
+ } else if (FreeInst *F = dyn_cast<FreeInst>(*UI)) {
+ Writers.push_back(F->getParent()->getParent());
+ } else {
+ return true;
+ }
+ return false;
+}
+
+/// AnalyzeIndirectGlobalMemory - We found an non-address-taken global variable
+/// which holds a pointer type. See if the global always points to non-aliased
+/// heap memory: that is, all initializers of the globals are allocations, and
+/// those allocations have no use other than initialization of the global.
+/// Further, all loads out of GV must directly use the memory, not store the
+/// pointer somewhere. If this is true, we consider the memory pointed to by
+/// GV to be owned by GV and can disambiguate other pointers from it.
+bool GlobalsModRef::AnalyzeIndirectGlobalMemory(GlobalValue *GV) {
+ // Keep track of values related to the allocation of the memory, f.e. the
+ // value produced by the malloc call and any casts.
+ std::vector<Value*> AllocRelatedValues;
+
+ // Walk the user list of the global. If we find anything other than a direct
+ // load or store, bail out.
+ for (Value::use_iterator I = GV->use_begin(), E = GV->use_end(); I != E; ++I){
+ if (LoadInst *LI = dyn_cast<LoadInst>(*I)) {
+ // The pointer loaded from the global can only be used in simple ways:
+ // we allow addressing of it and loading storing to it. We do *not* allow
+ // storing the loaded pointer somewhere else or passing to a function.
+ std::vector<Function*> ReadersWriters;
+ if (AnalyzeUsesOfPointer(LI, ReadersWriters, ReadersWriters))
+ return false; // Loaded pointer escapes.
+ // TODO: Could try some IP mod/ref of the loaded pointer.
+ } else if (StoreInst *SI = dyn_cast<StoreInst>(*I)) {
+ // Storing the global itself.
+ if (SI->getOperand(0) == GV) return false;
+
+ // If storing the null pointer, ignore it.
+ if (isa<ConstantPointerNull>(SI->getOperand(0)))
+ continue;
+
+ // Check the value being stored.
+ Value *Ptr = getUnderlyingObject(SI->getOperand(0));
+
+ if (isa<MallocInst>(Ptr)) {
+ // Okay, easy case.
+ } else if (CallInst *CI = dyn_cast<CallInst>(Ptr)) {
+ Function *F = CI->getCalledFunction();
+ if (!F || !F->isDeclaration()) return false; // Too hard to analyze.
+ if (F->getName() != "calloc") return false; // Not calloc.
+ } else {
+ return false; // Too hard to analyze.
+ }
+
+ // Analyze all uses of the allocation. If any of them are used in a
+ // non-simple way (e.g. stored to another global) bail out.
+ std::vector<Function*> ReadersWriters;
+ if (AnalyzeUsesOfPointer(Ptr, ReadersWriters, ReadersWriters, GV))
+ return false; // Loaded pointer escapes.
+
+ // Remember that this allocation is related to the indirect global.
+ AllocRelatedValues.push_back(Ptr);
+ } else {
+ // Something complex, bail out.
+ return false;
+ }
+ }
+
+ // Okay, this is an indirect global. Remember all of the allocations for
+ // this global in AllocsForIndirectGlobals.
+ while (!AllocRelatedValues.empty()) {
+ AllocsForIndirectGlobals[AllocRelatedValues.back()] = GV;
+ AllocRelatedValues.pop_back();
+ }
+ IndirectGlobals.insert(GV);
+ return true;
+}
+
+/// AnalyzeCallGraph - At this point, we know the functions where globals are
+/// immediately stored to and read from. Propagate this information up the call
+/// graph to all callers and compute the mod/ref info for all memory for each
+/// function.
+void GlobalsModRef::AnalyzeCallGraph(CallGraph &CG, Module &M) {
+ // We do a bottom-up SCC traversal of the call graph. In other words, we
+ // visit all callees before callers (leaf-first).
+ for (scc_iterator<CallGraph*> I = scc_begin(&CG), E = scc_end(&CG); I!=E; ++I)
+ if ((*I).size() != 1) {
+ AnalyzeSCC(*I);
+ } else if (Function *F = (*I)[0]->getFunction()) {
+ if (!F->isDeclaration()) {
+ // Nonexternal function.
+ AnalyzeSCC(*I);
+ } else {
+ // Otherwise external function. Handle intrinsics and other special
+ // cases here.
+ if (getAnalysis<AliasAnalysis>().doesNotAccessMemory(F))
+ // If it does not access memory, process the function, causing us to
+ // realize it doesn't do anything (the body is empty).
+ AnalyzeSCC(*I);
+ else {
+ // Otherwise, don't process it. This will cause us to conservatively
+ // assume the worst.
+ }
+ }
+ } else {
+ // Do not process the external node, assume the worst.
+ }
+}
+
+void GlobalsModRef::AnalyzeSCC(std::vector<CallGraphNode *> &SCC) {
+ assert(!SCC.empty() && "SCC with no functions?");
+ FunctionRecord &FR = FunctionInfo[SCC[0]->getFunction()];
+
+ bool CallsExternal = false;
+ unsigned FunctionEffect = 0;
+
+ // Collect the mod/ref properties due to called functions. We only compute
+ // one mod-ref set
+ for (unsigned i = 0, e = SCC.size(); i != e && !CallsExternal; ++i)
+ for (CallGraphNode::iterator CI = SCC[i]->begin(), E = SCC[i]->end();
+ CI != E; ++CI)
+ if (Function *Callee = CI->second->getFunction()) {
+ if (FunctionRecord *CalleeFR = getFunctionInfo(Callee)) {
+ // Propagate function effect up.
+ FunctionEffect |= CalleeFR->FunctionEffect;
+
+ // Incorporate callee's effects on globals into our info.
+ for (std::map<GlobalValue*, unsigned>::iterator GI =
+ CalleeFR->GlobalInfo.begin(), E = CalleeFR->GlobalInfo.end();
+ GI != E; ++GI)
+ FR.GlobalInfo[GI->first] |= GI->second;
+
+ } else {
+ // Okay, if we can't say anything about it, maybe some other alias
+ // analysis can.
+ ModRefBehavior MRB =
+ AliasAnalysis::getModRefBehavior(Callee, CallSite());
+ if (MRB != DoesNotAccessMemory) {
+ // FIXME: could make this more aggressive for functions that just
+ // read memory. We should just say they read all globals.
+ CallsExternal = true;
+ break;
+ }
+ }
+ } else {
+ CallsExternal = true;
+ break;
+ }
+
+ // If this SCC calls an external function, we can't say anything about it, so
+ // remove all SCC functions from the FunctionInfo map.
+ if (CallsExternal) {
+ for (unsigned i = 0, e = SCC.size(); i != e; ++i)
+ FunctionInfo.erase(SCC[i]->getFunction());
+ return;
+ }
+
+ // Otherwise, unless we already know that this function mod/refs memory, scan
+ // the function bodies to see if there are any explicit loads or stores.
+ if (FunctionEffect != ModRef) {
+ for (unsigned i = 0, e = SCC.size(); i != e && FunctionEffect != ModRef;++i)
+ for (inst_iterator II = inst_begin(SCC[i]->getFunction()),
+ E = inst_end(SCC[i]->getFunction());
+ II != E && FunctionEffect != ModRef; ++II)
+ if (isa<LoadInst>(*II))
+ FunctionEffect |= Ref;
+ else if (isa<StoreInst>(*II))
+ FunctionEffect |= Mod;
+ else if (isa<MallocInst>(*II) || isa<FreeInst>(*II))
+ FunctionEffect |= ModRef;
+ }
+
+ if ((FunctionEffect & Mod) == 0)
+ ++NumReadMemFunctions;
+ if (FunctionEffect == 0)
+ ++NumNoMemFunctions;
+ FR.FunctionEffect = FunctionEffect;
+
+ // Finally, now that we know the full effect on this SCC, clone the
+ // information to each function in the SCC.
+ for (unsigned i = 1, e = SCC.size(); i != e; ++i)
+ FunctionInfo[SCC[i]->getFunction()] = FR;
+}
+
+
+
+/// alias - If one of the pointers is to a global that we are tracking, and the
+/// other is some random pointer, we know there cannot be an alias, because the
+/// address of the global isn't taken.
+AliasAnalysis::AliasResult
+GlobalsModRef::alias(const Value *V1, unsigned V1Size,
+ const Value *V2, unsigned V2Size) {
+ // Get the base object these pointers point to.
+ Value *UV1 = getUnderlyingObject(const_cast<Value*>(V1));
+ Value *UV2 = getUnderlyingObject(const_cast<Value*>(V2));
+
+ // If either of the underlying values is a global, they may be non-addr-taken
+ // globals, which we can answer queries about.
+ GlobalValue *GV1 = dyn_cast<GlobalValue>(UV1);
+ GlobalValue *GV2 = dyn_cast<GlobalValue>(UV2);
+ if (GV1 || GV2) {
+ // If the global's address is taken, pretend we don't know it's a pointer to
+ // the global.
+ if (GV1 && !NonAddressTakenGlobals.count(GV1)) GV1 = 0;
+ if (GV2 && !NonAddressTakenGlobals.count(GV2)) GV2 = 0;
+
+ // If the the two pointers are derived from two different non-addr-taken
+ // globals, or if one is and the other isn't, we know these can't alias.
+ if ((GV1 || GV2) && GV1 != GV2)
+ return NoAlias;
+
+ // Otherwise if they are both derived from the same addr-taken global, we
+ // can't know the two accesses don't overlap.
+ }
+
+ // These pointers may be based on the memory owned by an indirect global. If
+ // so, we may be able to handle this. First check to see if the base pointer
+ // is a direct load from an indirect global.
+ GV1 = GV2 = 0;
+ if (LoadInst *LI = dyn_cast<LoadInst>(UV1))
+ if (GlobalVariable *GV = dyn_cast<GlobalVariable>(LI->getOperand(0)))
+ if (IndirectGlobals.count(GV))
+ GV1 = GV;
+ if (LoadInst *LI = dyn_cast<LoadInst>(UV2))
+ if (GlobalVariable *GV = dyn_cast<GlobalVariable>(LI->getOperand(0)))
+ if (IndirectGlobals.count(GV))
+ GV2 = GV;
+
+ // These pointers may also be from an allocation for the indirect global. If
+ // so, also handle them.
+ if (AllocsForIndirectGlobals.count(UV1))
+ GV1 = AllocsForIndirectGlobals[UV1];
+ if (AllocsForIndirectGlobals.count(UV2))
+ GV2 = AllocsForIndirectGlobals[UV2];
+
+ // Now that we know whether the two pointers are related to indirect globals,
+ // use this to disambiguate the pointers. If either pointer is based on an
+ // indirect global and if they are not both based on the same indirect global,
+ // they cannot alias.
+ if ((GV1 || GV2) && GV1 != GV2)
+ return NoAlias;
+
+ return AliasAnalysis::alias(V1, V1Size, V2, V2Size);
+}
+
+AliasAnalysis::ModRefResult
+GlobalsModRef::getModRefInfo(CallSite CS, Value *P, unsigned Size) {
+ unsigned Known = ModRef;
+
+ // If we are asking for mod/ref info of a direct call with a pointer to a
+ // global we are tracking, return information if we have it.
+ if (GlobalValue *GV = dyn_cast<GlobalValue>(getUnderlyingObject(P)))
+ if (GV->hasInternalLinkage())
+ if (Function *F = CS.getCalledFunction())
+ if (NonAddressTakenGlobals.count(GV))
+ if (FunctionRecord *FR = getFunctionInfo(F))
+ Known = FR->getInfoForGlobal(GV);
+
+ if (Known == NoModRef)
+ return NoModRef; // No need to query other mod/ref analyses
+ return ModRefResult(Known & AliasAnalysis::getModRefInfo(CS, P, Size));
+}
+
+
+//===----------------------------------------------------------------------===//
+// Methods to update the analysis as a result of the client transformation.
+//
+void GlobalsModRef::deleteValue(Value *V) {
+ if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
+ if (NonAddressTakenGlobals.erase(GV)) {
+ // This global might be an indirect global. If so, remove it and remove
+ // any AllocRelatedValues for it.
+ if (IndirectGlobals.erase(GV)) {
+ // Remove any entries in AllocsForIndirectGlobals for this global.
+ for (std::map<Value*, GlobalValue*>::iterator
+ I = AllocsForIndirectGlobals.begin(),
+ E = AllocsForIndirectGlobals.end(); I != E; ) {
+ if (I->second == GV) {
+ AllocsForIndirectGlobals.erase(I++);
+ } else {
+ ++I;
+ }
+ }
+ }
+ }
+ }
+
+ // Otherwise, if this is an allocation related to an indirect global, remove
+ // it.
+ AllocsForIndirectGlobals.erase(V);
+}
+
+void GlobalsModRef::copyValue(Value *From, Value *To) {
+}
diff --git a/lib/Analysis/IPA/Makefile b/lib/Analysis/IPA/Makefile
new file mode 100644
index 0000000..786e743
--- /dev/null
+++ b/lib/Analysis/IPA/Makefile
@@ -0,0 +1,14 @@
+##===- lib/Analysis/IPA/Makefile ---------------------------*- Makefile -*-===##
+#
+# The LLVM Compiler Infrastructure
+#
+# This file was developed by the LLVM research group and is distributed under
+# the University of Illinois Open Source License. See LICENSE.TXT for details.
+#
+##===----------------------------------------------------------------------===##
+
+LEVEL = ../../..
+LIBRARYNAME = LLVMipa
+BUILD_ARCHIVE = 1
+include $(LEVEL)/Makefile.common
+