summaryrefslogtreecommitdiffstats
path: root/lib/Analysis/IPA
diff options
context:
space:
mode:
Diffstat (limited to 'lib/Analysis/IPA')
-rw-r--r--lib/Analysis/IPA/Andersens.cpp168
-rw-r--r--lib/Analysis/IPA/CallGraph.cpp102
-rw-r--r--lib/Analysis/IPA/CallGraphSCCPass.cpp295
-rw-r--r--lib/Analysis/IPA/FindUsedTypes.cpp11
-rw-r--r--lib/Analysis/IPA/GlobalsModRef.cpp9
5 files changed, 403 insertions, 182 deletions
diff --git a/lib/Analysis/IPA/Andersens.cpp b/lib/Analysis/IPA/Andersens.cpp
index 3fb6526..1c9159d 100644
--- a/lib/Analysis/IPA/Andersens.cpp
+++ b/lib/Analysis/IPA/Andersens.cpp
@@ -60,9 +60,11 @@
#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/MallocHelper.h"
#include "llvm/Analysis/Passes.h"
#include "llvm/Support/Debug.h"
#include "llvm/System/Atomic.h"
@@ -84,7 +86,9 @@
#define FULL_UNIVERSAL 0
using namespace llvm;
+#ifndef NDEBUG
STATISTIC(NumIters , "Number of iterations to reach convergence");
+#endif
STATISTIC(NumConstraints, "Number of constraints");
STATISTIC(NumNodes , "Number of nodes");
STATISTIC(NumUnified , "Number of variables unified");
@@ -507,7 +511,7 @@ namespace {
#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;
}
@@ -589,9 +593,12 @@ namespace {
friend class InstVisitor<Andersens>;
void visitReturnInst(ReturnInst &RI);
void visitInvokeInst(InvokeInst &II) { visitCallSite(CallSite(&II)); }
- void visitCallInst(CallInst &CI) { visitCallSite(CallSite(&CI)); }
+ void visitCallInst(CallInst &CI) {
+ if (isMalloc(&CI)) visitAllocationInst(CI);
+ else visitCallSite(CallSite(&CI));
+ }
void visitCallSite(CallSite CS);
- void visitAllocationInst(AllocationInst &AI);
+ void visitAllocationInst(Instruction &I);
void visitLoadInst(LoadInst &LI);
void visitStoreInst(StoreInst &SI);
void visitGetElementPtrInst(GetElementPtrInst &GEP);
@@ -606,7 +613,7 @@ namespace {
//===------------------------------------------------------------------===//
// Implement Analyize interface
//
- void print(std::ostream &O, const Module* M) const {
+ void print(raw_ostream &O, const Module*) const {
PrintPointsToGraph();
}
};
@@ -614,7 +621,8 @@ namespace {
char Andersens::ID = 0;
static RegisterPass<Andersens>
-X("anders-aa", "Andersen's Interprocedural Alias Analysis", false, true);
+X("anders-aa", "Andersen's Interprocedural Alias Analysis (experimental)",
+ false, true);
static RegisterAnalysisGroup<AliasAnalysis> Y(X);
// Initialize Timestamp Counter (static).
@@ -786,6 +794,8 @@ void Andersens::IdentifyObjects(Module &M) {
ValueNodes[&*II] = NumObjects++;
if (AllocationInst *AI = dyn_cast<AllocationInst>(&*II))
ObjectNodes[AI] = NumObjects++;
+ else if (isMalloc(&*II))
+ ObjectNodes[&*II] = NumObjects++;
}
// Calls to inline asm need to be added as well because the callee isn't
@@ -825,11 +835,11 @@ unsigned Andersens::getNodeForConstantPointer(Constant *C) {
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;
}
@@ -852,11 +862,11 @@ unsigned Andersens::getNodeForConstantPointerTarget(Constant *C) {
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;
}
@@ -996,7 +1006,7 @@ bool Andersens::AnalyzeUsesOfFunction(Value *V) {
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)) {
@@ -1027,7 +1037,7 @@ bool Andersens::AnalyzeUsesOfFunction(Value *V) {
} 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;
@@ -1060,7 +1070,7 @@ void Andersens::CollectConstraints(Module &M) {
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
@@ -1152,15 +1162,15 @@ void Andersens::visitInstruction(Instruction &I) {
return;
default:
// Is this something we aren't handling yet?
- cerr << "Unknown instruction: " << I;
- abort();
+ errs() << "Unknown instruction: " << I;
+ llvm_unreachable(0);
}
}
-void Andersens::visitAllocationInst(AllocationInst &AI) {
- unsigned ObjectIndex = getObject(&AI);
- GraphNodes[ObjectIndex].setValue(&AI);
- Constraints.push_back(Constraint(Constraint::AddressOf, getNodeValue(AI),
+void Andersens::visitAllocationInst(Instruction &I) {
+ unsigned ObjectIndex = getObject(&I);
+ GraphNodes[ObjectIndex].setValue(&I);
+ Constraints.push_back(Constraint(Constraint::AddressOf, getNodeValue(I),
ObjectIndex));
}
@@ -1243,7 +1253,7 @@ void Andersens::visitSelectInst(SelectInst &SI) {
}
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
@@ -1395,12 +1405,6 @@ bool Andersens::Node::intersectsIgnoring(Node *N, unsigned Ignoring) const {
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.
@@ -1424,7 +1428,7 @@ void Andersens::ClumpAddressTaken() {
unsigned Pos = NewPos++;
Translate[i] = Pos;
NewGraphNodes.push_back(GraphNodes[i]);
- DOUT << "Renumbering node " << i << " to node " << Pos << "\n";
+ DEBUG(errs() << "Renumbering node " << i << " to node " << Pos << "\n");
}
// I believe this ends up being faster than making two vectors and splicing
@@ -1434,7 +1438,7 @@ void Andersens::ClumpAddressTaken() {
unsigned Pos = NewPos++;
Translate[i] = Pos;
NewGraphNodes.push_back(GraphNodes[i]);
- DOUT << "Renumbering node " << i << " to node " << Pos << "\n";
+ DEBUG(errs() << "Renumbering node " << i << " to node " << Pos << "\n");
}
}
@@ -1443,7 +1447,7 @@ void Andersens::ClumpAddressTaken() {
unsigned Pos = NewPos++;
Translate[i] = Pos;
NewGraphNodes.push_back(GraphNodes[i]);
- DOUT << "Renumbering node " << i << " to node " << Pos << "\n";
+ DEBUG(errs() << "Renumbering node " << i << " to node " << Pos << "\n");
}
}
@@ -1515,7 +1519,7 @@ void Andersens::ClumpAddressTaken() {
/// receive &D from E anyway.
void Andersens::HVN() {
- DOUT << "Beginning HVN\n";
+ DEBUG(errs() << "Beginning HVN\n");
// Build a predecessor graph. This is like our constraint graph with the
// edges going in the opposite direction, and there are edges for all the
// constraints, instead of just copy constraints. We also build implicit
@@ -1586,7 +1590,7 @@ void Andersens::HVN() {
Node2DFS.clear();
Node2Deleted.clear();
Node2Visited.clear();
- DOUT << "Finished HVN\n";
+ DEBUG(errs() << "Finished HVN\n");
}
@@ -1710,7 +1714,7 @@ void Andersens::HVNValNum(unsigned NodeIndex) {
/// and is equivalent to value numbering the collapsed constraint graph
/// including evaluating unions.
void Andersens::HU() {
- DOUT << "Beginning HU\n";
+ DEBUG(errs() << "Beginning HU\n");
// Build a predecessor graph. This is like our constraint graph with the
// edges going in the opposite direction, and there are edges for all the
// constraints, instead of just copy constraints. We also build implicit
@@ -1790,7 +1794,7 @@ void Andersens::HU() {
}
// PEClass nodes will be deleted by the deleting of N->PointsTo in our caller.
Set2PEClass.clear();
- DOUT << "Finished HU\n";
+ DEBUG(errs() << "Finished HU\n");
}
@@ -1968,12 +1972,12 @@ void Andersens::RewriteConstraints() {
// to anything.
if (LHSLabel == 0) {
DEBUG(PrintNode(&GraphNodes[LHSNode]));
- DOUT << " is a non-pointer, ignoring constraint.\n";
+ DEBUG(errs() << " is a non-pointer, ignoring constraint.\n");
continue;
}
if (RHSLabel == 0) {
DEBUG(PrintNode(&GraphNodes[RHSNode]));
- DOUT << " is a non-pointer, ignoring constraint.\n";
+ DEBUG(errs() << " is a non-pointer, ignoring constraint.\n");
continue;
}
// This constraint may be useless, and it may become useless as we translate
@@ -2021,19 +2025,19 @@ void Andersens::PrintLabels() const {
if (i < FirstRefNode) {
PrintNode(&GraphNodes[i]);
} else if (i < FirstAdrNode) {
- DOUT << "REF(";
+ DEBUG(errs() << "REF(");
PrintNode(&GraphNodes[i-FirstRefNode]);
- DOUT <<")";
+ DEBUG(errs() <<")");
} else {
- DOUT << "ADR(";
+ DEBUG(errs() << "ADR(");
PrintNode(&GraphNodes[i-FirstAdrNode]);
- DOUT <<")";
+ DEBUG(errs() <<")");
}
- DOUT << " has pointer label " << GraphNodes[i].PointerEquivLabel
+ DEBUG(errs() << " has pointer label " << GraphNodes[i].PointerEquivLabel
<< " and SCC rep " << VSSCCRep[i]
<< " and is " << (GraphNodes[i].Direct ? "Direct" : "Not direct")
- << "\n";
+ << "\n");
}
}
@@ -2047,7 +2051,7 @@ void Andersens::PrintLabels() const {
/// operation are stored in SDT and are later used in SolveContraints()
/// and UniteNodes().
void Andersens::HCD() {
- DOUT << "Starting HCD.\n";
+ DEBUG(errs() << "Starting HCD.\n");
HCDSCCRep.resize(GraphNodes.size());
for (unsigned i = 0; i < GraphNodes.size(); ++i) {
@@ -2096,7 +2100,7 @@ void Andersens::HCD() {
Node2Visited.clear();
Node2Deleted.clear();
HCDSCCRep.clear();
- DOUT << "HCD complete.\n";
+ DEBUG(errs() << "HCD complete.\n");
}
// Component of HCD:
@@ -2168,7 +2172,7 @@ void Andersens::Search(unsigned Node) {
/// Optimize the constraints by performing offline variable substitution and
/// other optimizations.
void Andersens::OptimizeConstraints() {
- DOUT << "Beginning constraint optimization\n";
+ DEBUG(errs() << "Beginning constraint optimization\n");
SDTActive = false;
@@ -2252,7 +2256,7 @@ void Andersens::OptimizeConstraints() {
// HCD complete.
- DOUT << "Finished constraint optimization\n";
+ DEBUG(errs() << "Finished constraint optimization\n");
FirstRefNode = 0;
FirstAdrNode = 0;
}
@@ -2260,7 +2264,7 @@ void Andersens::OptimizeConstraints() {
/// Unite pointer but not location equivalent variables, now that the constraint
/// graph is built.
void Andersens::UnitePointerEquivalences() {
- DOUT << "Uniting remaining pointer equivalences\n";
+ DEBUG(errs() << "Uniting remaining pointer equivalences\n");
for (unsigned i = 0; i < GraphNodes.size(); ++i) {
if (GraphNodes[i].AddressTaken && GraphNodes[i].isRep()) {
unsigned Label = GraphNodes[i].PointerEquivLabel;
@@ -2269,7 +2273,7 @@ void Andersens::UnitePointerEquivalences() {
UniteNodes(i, PENLEClass2Node[Label]);
}
}
- DOUT << "Finished remaining pointer equivalences\n";
+ DEBUG(errs() << "Finished remaining pointer equivalences\n");
PENLEClass2Node.clear();
}
@@ -2425,7 +2429,7 @@ void Andersens::SolveConstraints() {
std::vector<unsigned int> RSV;
#endif
while( !CurrWL->empty() ) {
- DOUT << "Starting iteration #" << ++NumIters << "\n";
+ DEBUG(errs() << "Starting iteration #" << ++NumIters << "\n");
Node* CurrNode;
unsigned CurrNodeIndex;
@@ -2728,11 +2732,11 @@ unsigned Andersens::UniteNodes(unsigned First, unsigned Second,
SecondNode->OldPointsTo = NULL;
NumUnified++;
- DOUT << "Unified Node ";
+ DEBUG(errs() << "Unified Node ");
DEBUG(PrintNode(FirstNode));
- DOUT << " and Node ";
+ DEBUG(errs() << " and Node ");
DEBUG(PrintNode(SecondNode));
- DOUT << "\n";
+ DEBUG(errs() << "\n");
if (SDTActive)
if (SDT[Second] >= 0) {
@@ -2777,17 +2781,17 @@ unsigned Andersens::FindNode(unsigned NodeIndex) const {
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;
}
@@ -2796,85 +2800,85 @@ void Andersens::PrintNode(const Node *N) const {
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 (isa<GlobalValue>(V) || isa<AllocationInst>(V) || isMalloc(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";
}
}
}
diff --git a/lib/Analysis/IPA/CallGraph.cpp b/lib/Analysis/IPA/CallGraph.cpp
index 6dabcdb..e2b288d 100644
--- a/lib/Analysis/IPA/CallGraph.cpp
+++ b/lib/Analysis/IPA/CallGraph.cpp
@@ -18,8 +18,7 @@
#include "llvm/IntrinsicInst.h"
#include "llvm/Support/CallSite.h"
#include "llvm/Support/Compiler.h"
-#include "llvm/Support/Streams.h"
-#include <ostream>
+#include "llvm/Support/raw_ostream.h"
using namespace llvm;
namespace {
@@ -54,7 +53,7 @@ public:
CallsExternalNode = new CallGraphNode(0);
Root = 0;
- // Add every function to the call graph...
+ // Add every function to the call graph.
for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
addToCallGraph(I);
@@ -68,30 +67,21 @@ public:
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: ";
+ virtual void print(raw_ostream &OS, const Module *) const {
+ OS << "CallGraph Root is: ";
if (Function *F = getRoot()->getFunction())
- o << F->getName() << "\n";
- else
- o << "<<null function: 0x" << getRoot() << ">>\n";
+ OS << F->getName() << "\n";
+ else {
+ OS << "<<null function: 0x" << getRoot() << ">>\n";
+ }
- CallGraph::print(o, M);
+ CallGraph::print(OS, 0);
}
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; }
@@ -179,21 +169,20 @@ void CallGraph::initialize(Module &M) {
}
void CallGraph::destroy() {
- if (!FunctionMap.empty()) {
- for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end();
- I != E; ++I)
- delete I->second;
- FunctionMap.clear();
- }
+ if (FunctionMap.empty()) return;
+
+ 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 {
+void CallGraph::print(raw_ostream &OS, Module*) const {
for (CallGraph::const_iterator I = begin(), E = end(); I != E; ++I)
I->second->print(OS);
}
-
void CallGraph::dump() const {
- print(cerr, 0);
+ print(errs(), 0);
}
//===----------------------------------------------------------------------===//
@@ -207,7 +196,7 @@ void CallGraph::dump() const {
// is to dropAllReferences before calling this.
//
Function *CallGraph::removeFunctionFromModule(CallGraphNode *CGN) {
- assert(CGN->CalledFunctions.empty() && "Cannot remove function from call "
+ assert(CGN->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
@@ -217,20 +206,6 @@ Function *CallGraph::removeFunctionFromModule(CallGraphNode *CGN) {
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.
@@ -242,11 +217,13 @@ CallGraphNode *CallGraph::getOrInsertFunction(const Function *F) {
return CGN = new CallGraphNode(const_cast<Function*>(F));
}
-void CallGraphNode::print(std::ostream &OS) const {
+void CallGraphNode::print(raw_ostream &OS) const {
if (Function *F = getFunction())
- OS << "Call graph node for function: '" << F->getName() <<"'\n";
+ OS << "Call graph node for function: '" << F->getName() << "'";
else
- OS << "Call graph node <<null function: 0x" << this << ">>:\n";
+ OS << "Call graph node <<null function>>";
+
+ OS << "<<0x" << this << ">> #uses=" << getNumReferences() << '\n';
for (const_iterator I = begin(), E = end(); I != E; ++I)
if (Function *FI = I->second->getFunction())
@@ -256,7 +233,7 @@ void CallGraphNode::print(std::ostream &OS) const {
OS << "\n";
}
-void CallGraphNode::dump() const { print(cerr); }
+void CallGraphNode::dump() const { print(errs()); }
/// removeCallEdgeFor - This method removes the edge in the node for the
/// specified call site. Note that this method takes linear time, so it
@@ -264,8 +241,10 @@ void CallGraphNode::dump() const { print(cerr); }
void CallGraphNode::removeCallEdgeFor(CallSite CS) {
for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) {
assert(I != CalledFunctions.end() && "Cannot find callsite to remove!");
- if (I->first == CS) {
- CalledFunctions.erase(I);
+ if (I->first == CS.getInstruction()) {
+ I->second->DropRef();
+ *I = CalledFunctions.back();
+ CalledFunctions.pop_back();
return;
}
}
@@ -278,6 +257,7 @@ void CallGraphNode::removeCallEdgeFor(CallSite CS) {
void CallGraphNode::removeAnyCallEdgeTo(CallGraphNode *Callee) {
for (unsigned i = 0, e = CalledFunctions.size(); i != e; ++i)
if (CalledFunctions[i].second == Callee) {
+ Callee->DropRef();
CalledFunctions[i] = CalledFunctions.back();
CalledFunctions.pop_back();
--i; --e;
@@ -290,21 +270,27 @@ void CallGraphNode::removeOneAbstractEdgeTo(CallGraphNode *Callee) {
for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) {
assert(I != CalledFunctions.end() && "Cannot find callee to remove!");
CallRecord &CR = *I;
- if (CR.second == Callee && !CR.first.getInstruction()) {
- CalledFunctions.erase(I);
+ if (CR.second == Callee && CR.first == 0) {
+ Callee->DropRef();
+ *I = CalledFunctions.back();
+ CalledFunctions.pop_back();
return;
}
}
}
-/// replaceCallSite - Make the edge in the node for Old CallSite be for
-/// New CallSite instead. Note that this method takes linear time, so it
-/// should be used sparingly.
-void CallGraphNode::replaceCallSite(CallSite Old, CallSite New) {
+/// replaceCallEdge - This method replaces the edge in the node for the
+/// specified call site with a new one. Note that this method takes linear
+/// time, so it should be used sparingly.
+void CallGraphNode::replaceCallEdge(CallSite CS,
+ CallSite NewCS, CallGraphNode *NewNode){
for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) {
- assert(I != CalledFunctions.end() && "Cannot find callsite to replace!");
- if (I->first == Old) {
- I->first = New;
+ assert(I != CalledFunctions.end() && "Cannot find callsite to remove!");
+ if (I->first == CS.getInstruction()) {
+ I->second->DropRef();
+ I->first = NewCS.getInstruction();
+ I->second = NewNode;
+ NewNode->AddRef();
return;
}
}
diff --git a/lib/Analysis/IPA/CallGraphSCCPass.cpp b/lib/Analysis/IPA/CallGraphSCCPass.cpp
index 3880d0a..a96a5c5 100644
--- a/lib/Analysis/IPA/CallGraphSCCPass.cpp
+++ b/lib/Analysis/IPA/CallGraphSCCPass.cpp
@@ -15,22 +15,25 @@
//
//===----------------------------------------------------------------------===//
+#define DEBUG_TYPE "cgscc-passmgr"
#include "llvm/CallGraphSCCPass.h"
#include "llvm/Analysis/CallGraph.h"
#include "llvm/ADT/SCCIterator.h"
#include "llvm/PassManagers.h"
#include "llvm/Function.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/IntrinsicInst.h"
+#include "llvm/Support/raw_ostream.h"
using namespace llvm;
//===----------------------------------------------------------------------===//
// CGPassManager
//
-/// CGPassManager manages FPPassManagers and CalLGraphSCCPasses.
+/// CGPassManager manages FPPassManagers and CallGraphSCCPasses.
namespace {
class CGPassManager : public ModulePass, public PMDataManager {
-
public:
static char ID;
explicit CGPassManager(int Depth)
@@ -56,7 +59,7 @@ public:
// Print passes managed by this manager
void dumpPassStructure(unsigned Offset) {
- llvm::cerr << std::string(Offset*2, ' ') << "Call Graph SCC Pass Manager\n";
+ errs().indent(Offset*2) << "Call Graph SCC Pass Manager\n";
for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
Pass *P = getContainedPass(Index);
P->dumpPassStructure(Offset + 1);
@@ -65,56 +68,275 @@ public:
}
Pass *getContainedPass(unsigned N) {
- assert ( N < PassVector.size() && "Pass number out of range!");
- Pass *FP = static_cast<Pass *>(PassVector[N]);
- return FP;
+ assert(N < PassVector.size() && "Pass number out of range!");
+ return static_cast<Pass *>(PassVector[N]);
}
virtual PassManagerType getPassManagerType() const {
return PMT_CallGraphPassManager;
}
+
+private:
+ bool RunPassOnSCC(Pass *P, std::vector<CallGraphNode*> &CurSCC,
+ CallGraph &CG, bool &CallGraphUpToDate);
+ void RefreshCallGraph(std::vector<CallGraphNode*> &CurSCC, CallGraph &CG,
+ bool IsCheckingMode);
};
-}
+} // end anonymous namespace.
char CGPassManager::ID = 0;
+
+bool CGPassManager::RunPassOnSCC(Pass *P, std::vector<CallGraphNode*> &CurSCC,
+ CallGraph &CG, bool &CallGraphUpToDate) {
+ bool Changed = false;
+ if (CallGraphSCCPass *CGSP = dynamic_cast<CallGraphSCCPass*>(P)) {
+ if (!CallGraphUpToDate) {
+ RefreshCallGraph(CurSCC, CG, false);
+ CallGraphUpToDate = true;
+ }
+
+ Timer *T = StartPassTimer(CGSP);
+ Changed = CGSP->runOnSCC(CurSCC);
+ StopPassTimer(CGSP, T);
+
+ // After the CGSCCPass is done, when assertions are enabled, use
+ // RefreshCallGraph to verify that the callgraph was correctly updated.
+#ifndef NDEBUG
+ if (Changed)
+ RefreshCallGraph(CurSCC, CG, true);
+#endif
+
+ return Changed;
+ }
+
+ FPPassManager *FPP = dynamic_cast<FPPassManager *>(P);
+ assert(FPP && "Invalid CGPassManager member");
+
+ // Run pass P on all functions in the current SCC.
+ for (unsigned i = 0, e = CurSCC.size(); i != e; ++i) {
+ if (Function *F = CurSCC[i]->getFunction()) {
+ dumpPassInfo(P, EXECUTION_MSG, ON_FUNCTION_MSG, F->getName());
+ Timer *T = StartPassTimer(FPP);
+ Changed |= FPP->runOnFunction(*F);
+ StopPassTimer(FPP, T);
+ }
+ }
+
+ // The function pass(es) modified the IR, they may have clobbered the
+ // callgraph.
+ if (Changed && CallGraphUpToDate) {
+ DEBUG(errs() << "CGSCCPASSMGR: Pass Dirtied SCC: "
+ << P->getPassName() << '\n');
+ CallGraphUpToDate = false;
+ }
+ return Changed;
+}
+
+
+/// RefreshCallGraph - Scan the functions in the specified CFG and resync the
+/// callgraph with the call sites found in it. This is used after
+/// FunctionPasses have potentially munged the callgraph, and can be used after
+/// CallGraphSCC passes to verify that they correctly updated the callgraph.
+///
+void CGPassManager::RefreshCallGraph(std::vector<CallGraphNode*> &CurSCC,
+ CallGraph &CG, bool CheckingMode) {
+ DenseMap<Value*, CallGraphNode*> CallSites;
+
+ DEBUG(errs() << "CGSCCPASSMGR: Refreshing SCC with " << CurSCC.size()
+ << " nodes:\n";
+ for (unsigned i = 0, e = CurSCC.size(); i != e; ++i)
+ CurSCC[i]->dump();
+ );
+
+ bool MadeChange = false;
+
+ // Scan all functions in the SCC.
+ for (unsigned sccidx = 0, e = CurSCC.size(); sccidx != e; ++sccidx) {
+ CallGraphNode *CGN = CurSCC[sccidx];
+ Function *F = CGN->getFunction();
+ if (F == 0 || F->isDeclaration()) continue;
+
+ // Walk the function body looking for call sites. Sync up the call sites in
+ // CGN with those actually in the function.
+
+ // Get the set of call sites currently in the function.
+ for (CallGraphNode::iterator I = CGN->begin(), E = CGN->end(); I != E; ) {
+ // If this call site is null, then the function pass deleted the call
+ // entirely and the WeakVH nulled it out.
+ if (I->first == 0 ||
+ // If we've already seen this call site, then the FunctionPass RAUW'd
+ // one call with another, which resulted in two "uses" in the edge
+ // list of the same call.
+ CallSites.count(I->first) ||
+
+ // If the call edge is not from a call or invoke, then the function
+ // pass RAUW'd a call with another value. This can happen when
+ // constant folding happens of well known functions etc.
+ CallSite::get(I->first).getInstruction() == 0) {
+ assert(!CheckingMode &&
+ "CallGraphSCCPass did not update the CallGraph correctly!");
+
+ // Just remove the edge from the set of callees, keep track of whether
+ // I points to the last element of the vector.
+ bool WasLast = I + 1 == E;
+ CGN->removeCallEdge(I);
+
+ // If I pointed to the last element of the vector, we have to bail out:
+ // iterator checking rejects comparisons of the resultant pointer with
+ // end.
+ if (WasLast)
+ break;
+ E = CGN->end();
+ continue;
+ }
+
+ assert(!CallSites.count(I->first) &&
+ "Call site occurs in node multiple times");
+ CallSites.insert(std::make_pair(I->first, I->second));
+ ++I;
+ }
+
+ // Loop over all of the instructions in the function, getting the callsites.
+ for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
+ for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
+ CallSite CS = CallSite::get(I);
+ if (!CS.getInstruction() || isa<DbgInfoIntrinsic>(I)) continue;
+
+ // If this call site already existed in the callgraph, just verify it
+ // matches up to expectations and remove it from CallSites.
+ DenseMap<Value*, CallGraphNode*>::iterator ExistingIt =
+ CallSites.find(CS.getInstruction());
+ if (ExistingIt != CallSites.end()) {
+ CallGraphNode *ExistingNode = ExistingIt->second;
+
+ // Remove from CallSites since we have now seen it.
+ CallSites.erase(ExistingIt);
+
+ // Verify that the callee is right.
+ if (ExistingNode->getFunction() == CS.getCalledFunction())
+ continue;
+
+ // If we are in checking mode, we are not allowed to actually mutate
+ // the callgraph. If this is a case where we can infer that the
+ // callgraph is less precise than it could be (e.g. an indirect call
+ // site could be turned direct), don't reject it in checking mode, and
+ // don't tweak it to be more precise.
+ if (CheckingMode && CS.getCalledFunction() &&
+ ExistingNode->getFunction() == 0)
+ continue;
+
+ assert(!CheckingMode &&
+ "CallGraphSCCPass did not update the CallGraph correctly!");
+
+ // If not, we either went from a direct call to indirect, indirect to
+ // direct, or direct to different direct.
+ CallGraphNode *CalleeNode;
+ if (Function *Callee = CS.getCalledFunction())
+ CalleeNode = CG.getOrInsertFunction(Callee);
+ else
+ CalleeNode = CG.getCallsExternalNode();
+
+ // Update the edge target in CGN.
+ for (CallGraphNode::iterator I = CGN->begin(); ; ++I) {
+ assert(I != CGN->end() && "Didn't find call entry");
+ if (I->first == CS.getInstruction()) {
+ I->second = CalleeNode;
+ break;
+ }
+ }
+ MadeChange = true;
+ continue;
+ }
+
+ assert(!CheckingMode &&
+ "CallGraphSCCPass did not update the CallGraph correctly!");
+
+ // If the call site didn't exist in the CGN yet, add it. We assume that
+ // newly introduced call sites won't be indirect. This could be fixed
+ // in the future.
+ CallGraphNode *CalleeNode;
+ if (Function *Callee = CS.getCalledFunction())
+ CalleeNode = CG.getOrInsertFunction(Callee);
+ else
+ CalleeNode = CG.getCallsExternalNode();
+
+ CGN->addCalledFunction(CS, CalleeNode);
+ MadeChange = true;
+ }
+
+ // After scanning this function, if we still have entries in callsites, then
+ // they are dangling pointers. WeakVH should save us for this, so abort if
+ // this happens.
+ assert(CallSites.empty() && "Dangling pointers found in call sites map");
+
+ // Periodically do an explicit clear to remove tombstones when processing
+ // large scc's.
+ if ((sccidx & 15) == 0)
+ CallSites.clear();
+ }
+
+ DEBUG(if (MadeChange) {
+ errs() << "CGSCCPASSMGR: Refreshed SCC is now:\n";
+ for (unsigned i = 0, e = CurSCC.size(); i != e; ++i)
+ CurSCC[i]->dump();
+ } else {
+ errs() << "CGSCCPASSMGR: SCC Refresh didn't change call graph.\n";
+ }
+ );
+}
+
/// 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);
-
- dumpPassInfo(P, EXECUTION_MSG, ON_CG_MSG, "");
+ std::vector<CallGraphNode*> CurSCC;
+
+ // Walk the callgraph in bottom-up SCC order.
+ for (scc_iterator<CallGraph*> CGI = scc_begin(&CG), E = scc_end(&CG);
+ CGI != E;) {
+ // Copy the current SCC and increment past it so that the pass can hack
+ // on the SCC if it wants to without invalidating our iterator.
+ CurSCC = *CGI;
+ ++CGI;
+
+
+ // CallGraphUpToDate - Keep track of whether the callgraph is known to be
+ // up-to-date or not. The CGSSC pass manager runs two types of passes:
+ // CallGraphSCC Passes and other random function passes. Because other
+ // random function passes are not CallGraph aware, they may clobber the
+ // call graph by introducing new calls or deleting other ones. This flag
+ // is set to false when we run a function pass so that we know to clean up
+ // the callgraph when we need to run a CGSCCPass again.
+ bool CallGraphUpToDate = true;
+
+ // Run all passes on current SCC.
+ for (unsigned PassNo = 0, e = getNumContainedPasses();
+ PassNo != e; ++PassNo) {
+ Pass *P = getContainedPass(PassNo);
+
+ // If we're in -debug-pass=Executions mode, construct the SCC node list,
+ // otherwise avoid constructing this string as it is expensive.
+ if (isPassDebuggingExecutionsOrMore()) {
+ std::string Functions;
+#ifndef NDEBUG
+ raw_string_ostream OS(Functions);
+ for (unsigned i = 0, e = CurSCC.size(); i != e; ++i) {
+ if (i) OS << ", ";
+ CurSCC[i]->print(OS);
+ }
+ OS.flush();
+#endif
+ dumpPassInfo(P, EXECUTION_MSG, ON_CG_MSG, Functions);
+ }
dumpRequiredSet(P);
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->getNameStart());
- Changed |= FPP->runOnFunction(*F);
- }
- }
- }
- StopPassTimer(P);
+ // Actually run this pass on the current SCC.
+ Changed |= RunPassOnSCC(P, CurSCC, CG, CallGraphUpToDate);
if (Changed)
dumpPassInfo(P, MODIFICATION_MSG, ON_CG_MSG, "");
@@ -125,6 +347,11 @@ bool CGPassManager::runOnModule(Module &M) {
recordAvailableAnalysis(P);
removeDeadPasses(P, "", ON_CG_MSG);
}
+
+ // If the callgraph was left out of date (because the last pass run was a
+ // functionpass), refresh it before we move on to the next SCC.
+ if (!CallGraphUpToDate)
+ RefreshCallGraph(CurSCC, CG, false);
}
Changed |= doFinalization(CG);
return Changed;
diff --git a/lib/Analysis/IPA/FindUsedTypes.cpp b/lib/Analysis/IPA/FindUsedTypes.cpp
index 920ee37..c4fb0b9 100644
--- a/lib/Analysis/IPA/FindUsedTypes.cpp
+++ b/lib/Analysis/IPA/FindUsedTypes.cpp
@@ -92,13 +92,12 @@ bool FindUsedTypes::runOnModule(Module &m) {
// passed in, then the types are printed symbolically if possible, using the
// symbol table from the module.
//
-void FindUsedTypes::print(std::ostream &OS, const Module *M) const {
- raw_os_ostream RO(OS);
- RO << "Types in use by this module:\n";
+void FindUsedTypes::print(raw_ostream &OS, const Module *M) const {
+ OS << "Types in use by this module:\n";
for (std::set<const Type *>::const_iterator I = UsedTypes.begin(),
E = UsedTypes.end(); I != E; ++I) {
- RO << " ";
- WriteTypeSymbolic(RO, *I, M);
- RO << '\n';
+ OS << " ";
+ WriteTypeSymbolic(OS, *I, M);
+ OS << '\n';
}
}
diff --git a/lib/Analysis/IPA/GlobalsModRef.cpp b/lib/Analysis/IPA/GlobalsModRef.cpp
index 2e9884a..f5c1108 100644
--- a/lib/Analysis/IPA/GlobalsModRef.cpp
+++ b/lib/Analysis/IPA/GlobalsModRef.cpp
@@ -23,6 +23,7 @@
#include "llvm/DerivedTypes.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/CallGraph.h"
+#include "llvm/Analysis/MallocHelper.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/InstIterator.h"
@@ -236,6 +237,9 @@ bool GlobalsModRef::AnalyzeUsesOfPointer(Value *V,
}
} else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(*UI)) {
if (AnalyzeUsesOfPointer(GEP, Readers, Writers)) return true;
+ } else if (BitCastInst *BCI = dyn_cast<BitCastInst>(*UI)) {
+ if (AnalyzeUsesOfPointer(BCI, Readers, Writers, OkayStoreDest))
+ 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.
@@ -299,7 +303,7 @@ bool GlobalsModRef::AnalyzeIndirectGlobalMemory(GlobalValue *GV) {
// Check the value being stored.
Value *Ptr = SI->getOperand(0)->getUnderlyingObject();
- if (isa<MallocInst>(Ptr)) {
+ if (isa<MallocInst>(Ptr) || isMalloc(Ptr)) {
// Okay, easy case.
} else if (CallInst *CI = dyn_cast<CallInst>(Ptr)) {
Function *F = CI->getCalledFunction();
@@ -435,7 +439,8 @@ void GlobalsModRef::AnalyzeCallGraph(CallGraph &CG, Module &M) {
if (cast<StoreInst>(*II).isVolatile())
// Treat volatile stores as reading memory somewhere.
FunctionEffect |= Ref;
- } else if (isa<MallocInst>(*II) || isa<FreeInst>(*II)) {
+ } else if (isa<MallocInst>(*II) || isa<FreeInst>(*II) ||
+ isMalloc(&cast<Instruction>(*II))) {
FunctionEffect |= ModRef;
}
OpenPOWER on IntegriCloud