Google Git
Sign in
llvm / llvm-archive / 2b509aedda0b950598af9798b43b066b338f0381 / . / poolalloc / lib / DSA / DSGraph.cpp
blob: f2ddbab984573c7bb5cec599c4f9c6d6bee3a210 [file] [log] [blame]
//===- DataStructure.cpp - Implement the core data structure 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 implements the core data structure functionality.
//
//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "dsgraph"
#include "dsa/DSGraphTraits.h"
#include "dsa/DataStructure.h"
#include "dsa/DSGraph.h"
#include "dsa/DSSupport.h"
#include "dsa/DSNode.h"
#include "dsa/stl_util.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/GlobalVariable.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SCCIterator.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Support/Timer.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/GlobalAlias.h"
#include <iostream>
#include <algorithm>
using namespace llvm;
#define COLLAPSE_ARRAYS_AGGRESSIVELY 0
namespace {
STATISTIC (NumCallNodesMerged , "Number of call nodes merged");
STATISTIC (NumDNE , "Number of nodes removed by reachability");
STATISTIC (NumTrivialDNE , "Number of nodes trivially removed");
STATISTIC (NumTrivialGlobalDNE , "Number of globals trivially removed");
STATISTIC (NumFiltered , "Number of calls filtered");
static cl::opt<bool> noDSACallConv("dsa-no-filter-callcc",
cl::desc("Don't filter call sites based on calling convention."),
cl::Hidden,
cl::init(false));
static cl::opt<bool> noDSACallNumArgs("dsa-no-filter-numargs",
cl::desc("Don't filter call sites based on number of arguments."),
cl::Hidden,
cl::init(false));
static cl::opt<bool> noDSACallVA("dsa-no-filter-vararg",
cl::desc("Don't filter call sites based on vararg presense"),
cl::Hidden,
cl::init(true));
static cl::opt<bool> noDSACallFP("dsa-no-filter-intfp",
cl::desc("Don't filter call sites based on implicit integer to FP conversion"),
cl::Hidden,
cl::init(false));
}
extern cl::opt<bool> TypeInferenceOptimize;
// Determines if the DSGraph 'should' have a node for a given value.
static bool shouldHaveNodeForValue(const Value *V) {
// Peer through casts
V = V->stripPointerCasts();
// Only pointers get nodes
if (!isa<PointerType>(V->getType())) return false;
// Undef values, even ones of pointer type, don't get nodes.
if (isa<UndefValue>(V)) return false;
if (isa<ConstantPointerNull>(V))
return false;
// Use the Aliasee of GlobalAliases
// FIXME: This check might not be required, it's here because
// something similar is done in the Local pass.
if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(V))
return shouldHaveNodeForValue(GA->getAliasee());
return true;
}
/// getFunctionNames - Return a space separated list of the name of the
/// functions in this graph (if any)
std::string DSGraph::getFunctionNames() const {
switch (getReturnNodes().size()) {
case 0: return "Globals graph";
case 1: return retnodes_begin()->first->getName();
default:
std::string Return;
for (DSGraph::retnodes_iterator I = retnodes_begin();
I != retnodes_end(); ++I)
Return += I->first->getName().str() + " ";
Return.erase(Return.end()-1, Return.end()); // Remove last space character
return Return;
}
}
DSGraph::DSGraph(DSGraph* G, EquivalenceClasses<const GlobalValue*> &ECs,
SuperSet<Type*>& tss,
unsigned CloneFlags)
: GlobalsGraph(0), ScalarMap(ECs), TD(G->TD), TypeSS(tss) {
UseAuxCalls = false;
cloneInto(G, CloneFlags);
}
DSGraph::~DSGraph() {
FunctionCalls.clear();
AuxFunctionCalls.clear();
ScalarMap.clear();
ReturnNodes.clear();
VANodes.clear();
// Drop all intra-node references, so that assertions don't fail...
for (node_iterator NI = node_begin(), E = node_end(); NI != E; ++NI)
NI->dropAllReferences();
// Free all of the nodes.
Nodes.clear();
}
// dump - Allow inspection of graph in a debugger.
void DSGraph::dump() const { print(errs()); }
void DSGraph::removeFunctionCalls(Function& F) {
FunctionListTy::iterator Erase = FunctionCalls.end();
for (FunctionListTy::iterator I = FunctionCalls.begin();
I != Erase; ) {
if (I->isDirectCall() && I->getCalleeFunc() == &F)
std::swap(*I, *--Erase);
else
++I;
}
FunctionCalls.erase(Erase, FunctionCalls.end());
Erase = AuxFunctionCalls.end();
for (FunctionListTy::iterator I = AuxFunctionCalls.begin();
I != Erase; ) {
if (I->isDirectCall() && I->getCalleeFunc() == &F)
std::swap(*I, *--Erase);
else
++I;
}
AuxFunctionCalls.erase(Erase, AuxFunctionCalls.end());
}
/// addObjectToGraph - This method can be used to add global, stack, and heap
/// objects to the graph. This can be used when updating DSGraphs due to the
/// introduction of new temporary objects. The new object is not pointed to
/// and does not point to any other objects in the graph.
DSNode *DSGraph::addObjectToGraph(Value *Ptr, bool UseDeclaredType) {
assert(isa<PointerType>(Ptr->getType()) && "Ptr is not a pointer!");
DSNode *N = new DSNode(this);
assert(ScalarMap[Ptr].isNull() && "Object already in this graph!");
ScalarMap[Ptr] = N;
if (GlobalValue *GV = dyn_cast<GlobalValue>(Ptr)) {
N->addGlobal(GV);
// } else if (isa<MallocInst>(Ptr)) {
// N->setHeapMarker();
} else if (isa<AllocaInst>(Ptr)) {
N->setAllocaMarker();
} else {
assert(0 && "Illegal memory object input!");
}
return N;
}
/// cloneInto - Clone the specified DSGraph into the current graph. The
/// translated ScalarMap for the old function is filled into the ScalarMap
/// for the graph, the translated ReturnNodes map is returned into
/// ReturnNodes, and the translated VANodes map is return into VANodes.
///
/// The CloneFlags member controls various aspects of the cloning process.
///
void DSGraph::cloneInto( DSGraph* G, unsigned CloneFlags) {
assert(G != this && "Cannot clone graph into itself!");
NodeMapTy OldNodeMap;
// Remove alloca or mod/ref bits as specified...
unsigned BitsToClear = ((CloneFlags & StripAllocaBit)? DSNode::AllocaNode : 0)
| ((CloneFlags & StripModRefBits)? (DSNode::ModifiedNode | DSNode::ReadNode) : 0)
| ((CloneFlags & StripIncompleteBit)? DSNode::IncompleteNode : 0);
BitsToClear |= DSNode::DeadNode; // Clear dead flag...
for (node_const_iterator I = G->node_begin(), E = G->node_end(); I != E; ++I) {
assert(!I->isForwarding() &&
"Forward nodes shouldn't be in node list!");
DSNode *New = new DSNode(*I, this);
New->maskNodeTypes(~BitsToClear);
OldNodeMap[I] = New;
}
// Rewrite the links in the new nodes to point into the current graph now.
// Note that we don't loop over the node's list to do this. The problem is
// that remaping links can cause recursive merging to happen, which means
// that node_iterator's can get easily invalidated! Because of this, we
// loop over the OldNodeMap, which contains all of the new nodes as the
// .second element of the map elements. Also note that if we remap a node
// more than once, we won't break anything.
for (NodeMapTy::iterator I = OldNodeMap.begin(), E = OldNodeMap.end();
I != E; ++I)
I->second.getNode()->remapLinks(OldNodeMap);
// Copy the scalar map... merging all of the global nodes...
for (DSScalarMap::const_iterator I = G->ScalarMap.begin(),
E = G->ScalarMap.end(); I != E; ++I) {
DSNodeHandle &MappedNode = OldNodeMap[I->second.getNode()];
DSNodeHandle &H = ScalarMap.getRawEntryRef(I->first);
DSNode *MappedNodeN = MappedNode.getNode();
H.mergeWith(DSNodeHandle(MappedNodeN,
I->second.getOffset()+MappedNode.getOffset()));
}
if (!(CloneFlags & DontCloneCallNodes)) {
// Copy the function calls list.
for (fc_iterator I = G->fc_begin(), E = G->fc_end(); I != E; ++I)
FunctionCalls.push_back(DSCallSite(*I, OldNodeMap));
}
if (!(CloneFlags & DontCloneAuxCallNodes)) {
// Copy the auxiliary function calls list.
for (afc_iterator I = G->afc_begin(), E = G->afc_end(); I != E; ++I)
AuxFunctionCalls.push_back(DSCallSite(*I, OldNodeMap));
}
// Map the return node pointers over...
for (retnodes_iterator I = G->retnodes_begin(),
E = G->retnodes_end(); I != E; ++I) {
const DSNodeHandle &Ret = I->second;
DSNodeHandle &MappedRet = OldNodeMap[Ret.getNode()];
DSNode *MappedRetN = MappedRet.getNode();
ReturnNodes.insert(std::make_pair(I->first,
DSNodeHandle(MappedRetN,
MappedRet.getOffset()+Ret.getOffset())));
}
// Map the VA node pointers over...
for (vanodes_iterator I = G->vanodes_begin(),
E = G->vanodes_end(); I != E; ++I) {
const DSNodeHandle &VarArg = I->second;
DSNodeHandle &MappedVarArg = OldNodeMap[VarArg.getNode()];
DSNode *MappedVarArgN = MappedVarArg.getNode();
VANodes.insert(std::make_pair(I->first,
DSNodeHandle(MappedVarArgN,
MappedVarArg.getOffset()+VarArg.getOffset())));
}
}
/// spliceFrom - Logically perform the operation of cloning the RHS graph into
/// this graph, then clearing the RHS graph. Instead of performing this as
/// two seperate operations, do it as a single, much faster, one.
///
void DSGraph::spliceFrom(DSGraph* RHS) {
assert(this != RHS && "Splicing self");
// Change all of the nodes in RHS to think we are their parent.
for (NodeListTy::iterator I = RHS->Nodes.begin(), E = RHS->Nodes.end();
I != E; ++I)
I->setParentGraph(this);
// Take all of the nodes.
splice(Nodes, RHS->Nodes);
// Take all of the calls.
splice(FunctionCalls, RHS->FunctionCalls);
splice(AuxFunctionCalls, RHS->AuxFunctionCalls);
// Take all of the return nodes.
splice(ReturnNodes, RHS->ReturnNodes);
// Same for the VA nodes
splice(VANodes, RHS->VANodes);
// Merge the scalar map in.
ScalarMap.spliceFrom(RHS->ScalarMap);
}
/// getFunctionArgumentsForCall - Given a function that is currently in this
/// graph, return the DSNodeHandles that correspond to the pointer-compatible
/// function arguments. The vector is filled in with the return value (or
/// null if it is not pointer compatible), a vararg node (null if not
/// applicable) followed by all of the pointer-compatible arguments.
void DSGraph::getFunctionArgumentsForCall(const Function *F,
std::vector<DSNodeHandle> &Args) const {
Args.push_back(getReturnNodeFor(*F));
Args.push_back(getVANodeFor(*F));
for (Function::const_arg_iterator AI = F->arg_begin(), E = F->arg_end();
AI != E; ++AI)
if (isa<PointerType>(AI->getType())) {
Args.push_back(getNodeForValue(AI));
assert(!Args.back().isNull() && "Pointer argument w/o scalarmap entry!?");
}
}
namespace {
// HackedGraphSCCFinder - This is used to find nodes that have a path from the
// node to a node cloned by the ReachabilityCloner object contained. To be
// extra obnoxious it ignores edges from nodes that are globals, and truncates
// search at RC marked nodes. This is designed as an object so that
// intermediate results can be memoized across invocations of
// PathExistsToClonedNode.
struct HackedGraphSCCFinder {
ReachabilityCloner &RC;
unsigned CurNodeId;
std::vector<const DSNode*> SCCStack;
std::map<const DSNode*, std::pair<unsigned, bool> > NodeInfo;
HackedGraphSCCFinder(ReachabilityCloner &rc) : RC(rc), CurNodeId(1) {
// Remove null pointer as a special case.
NodeInfo[0] = std::make_pair(0, false);
}
std::pair<unsigned, bool> &VisitForSCCs(const DSNode *N);
bool PathExistsToClonedNode(const DSNode *N) {
return VisitForSCCs(N).second;
}
bool PathExistsToClonedNode(const DSCallSite &CS) {
if (PathExistsToClonedNode(CS.getRetVal().getNode()))
return true;
if (CS.isIndirectCall() && PathExistsToClonedNode(CS.getCalleeNode()))
return true;
for (unsigned i = 0, e = CS.getNumPtrArgs(); i != e; ++i)
if (PathExistsToClonedNode(CS.getPtrArg(i).getNode()))
return true;
if (PathExistsToClonedNode(CS.getVAVal().getNode()))
return true;
return false;
}
};
}
std::pair<unsigned, bool> &HackedGraphSCCFinder::
VisitForSCCs(const DSNode *N) {
std::map<const DSNode*, std::pair<unsigned, bool> >::iterator
NodeInfoIt = NodeInfo.lower_bound(N);
if (NodeInfoIt != NodeInfo.end() && NodeInfoIt->first == N)
return NodeInfoIt->second;
unsigned Min = CurNodeId++;
unsigned MyId = Min;
std::pair<unsigned, bool> &ThisNodeInfo =
NodeInfo.insert(NodeInfoIt,
std::make_pair(N, std::make_pair(MyId, false)))->second;
// Base case: if this does reach the cloned graph portion... it does. :)
if (RC.hasClonedNode(N)) {
ThisNodeInfo.second = true;
return ThisNodeInfo;
}
// Base case: if we find a global, this doesn't reach the cloned graph
// portion.
if (N->isGlobalNode()) {
ThisNodeInfo.second = false;
return ThisNodeInfo;
}
SCCStack.push_back(N);
// Otherwise, check all successors.
bool AnyDirectSuccessorsReachClonedNodes = false;
for (DSNode::const_edge_iterator EI = N->edge_begin(), EE = N->edge_end();
EI != EE; ++EI)
if (DSNode * Succ = EI->second.getNode()) {
std::pair<unsigned, bool> &SuccInfo = VisitForSCCs(Succ);
if (SuccInfo.first < Min) Min = SuccInfo.first;
AnyDirectSuccessorsReachClonedNodes |= SuccInfo.second;
}
if (Min != MyId)
return ThisNodeInfo; // Part of a large SCC. Leave self on stack.
if (SCCStack.back() == N) { // Special case single node SCC.
SCCStack.pop_back();
ThisNodeInfo.second = AnyDirectSuccessorsReachClonedNodes;
return ThisNodeInfo;
}
// Find out if any direct successors of any node reach cloned nodes.
if (!AnyDirectSuccessorsReachClonedNodes)
for (unsigned i = SCCStack.size() - 1; SCCStack[i] != N; --i)
for (DSNode::const_edge_iterator EI = N->edge_begin(), EE = N->edge_end();
EI != EE; ++EI)
if (DSNode * N = EI->second.getNode())
if (NodeInfo[N].second) {
AnyDirectSuccessorsReachClonedNodes = true;
goto OutOfLoop;
}
OutOfLoop:
// If any successor reaches a cloned node, mark all nodes in this SCC as
// reaching the cloned node.
if (AnyDirectSuccessorsReachClonedNodes)
while (SCCStack.back() != N) {
NodeInfo[SCCStack.back()].second = true;
SCCStack.pop_back();
}
SCCStack.pop_back();
ThisNodeInfo.second = AnyDirectSuccessorsReachClonedNodes;
return ThisNodeInfo;
}
/// mergeInCallFromOtherGraph - This graph merges in the minimal number of
/// nodes from G2 into 'this' graph, merging the bindings specified by the
/// call site (in this graph) with the bindings specified by the vector in G2.
/// The two DSGraphs must be different.
///
void DSGraph::mergeInGraph(const DSCallSite &CS,
std::vector<DSNodeHandle> &Args,
const DSGraph &Graph, unsigned CloneFlags) {
assert((CloneFlags & DontCloneCallNodes) &&
"Doesn't support copying of call nodes!");
// If this is not a recursive call, clone the graph into this graph...
if (&Graph == this) {
// Merge the return value with the return value of the context.
Args[0].mergeWith(CS.getRetVal());
// Merge var-arg node
Args[1].mergeWith(CS.getVAVal());
// Resolve all of the function arguments.
for (unsigned i = 0, e = CS.getNumPtrArgs(); i != e; ++i) {
if (i == Args.size()-2)
break;
// Add the link from the argument scalar to the provided value.
Args[i+2].mergeWith(CS.getPtrArg(i));
}
return;
}
// Clone the callee's graph into the current graph, keeping track of where
// scalars in the old graph _used_ to point, and of the new nodes matching
// nodes of the old graph.
ReachabilityCloner RC(this, &Graph, CloneFlags);
// Map the return node pointer over.
if (!CS.getRetVal().isNull())
RC.merge(CS.getRetVal(), Args[0]);
// Map the variable arguments
if (!CS.getVAVal().isNull())
RC.merge(CS.getVAVal(), Args[1]);
// Map over all of the arguments.
for (unsigned i = 0, e = CS.getNumPtrArgs(); i != e; ++i) {
if (i == Args.size()-2)
break;
// Add the link from the argument scalar to the provided value.
RC.merge(CS.getPtrArg(i), Args[i+2]);
}
// We generally don't want to copy global nodes or aux calls from the callee
// graph to the caller graph. However, we have to copy them if there is a
// path from the node to a node we have already copied which does not go
// through another global. Compute the set of node that can reach globals and
// aux call nodes to copy over, then do it.
std::vector<const DSCallSite*> AuxCallToCopy;
std::vector<const GlobalValue*> GlobalsToCopy;
// NodesReachCopiedNodes - Memoize results for efficiency. Contains a
// true/false value for every visited node that reaches a copied node without
// going through a global.
HackedGraphSCCFinder SCCFinder(RC);
if (!(CloneFlags & DontCloneAuxCallNodes))
for (afc_const_iterator I = Graph.afc_begin(), E = Graph.afc_end(); I!=E; ++I)
if (!I->isUnresolvable() && SCCFinder.PathExistsToClonedNode(*I))
AuxCallToCopy.push_back(&*I);
// Copy aux calls that are needed.
// Copy these before calculating the globals to be copied, as there might be
// globals that reach the nodes cloned due to aux calls.
for (unsigned i = 0, e = AuxCallToCopy.size(); i != e; ++i)
AuxFunctionCalls.push_back(DSCallSite(*AuxCallToCopy[i], RC));
const DSScalarMap &GSM = Graph.getScalarMap();
for (DSScalarMap::global_iterator GI = GSM.global_begin(),
E = GSM.global_end(); GI != E; ++GI) {
DSNode *GlobalNode = Graph.getNodeForValue(*GI).getNode();
for (DSNode::edge_iterator EI = GlobalNode->edge_begin(),
EE = GlobalNode->edge_end(); EI != EE; ++EI)
if (SCCFinder.PathExistsToClonedNode(EI->second.getNode())) {
GlobalsToCopy.push_back(*GI);
break;
}
}
// Copy globals that are needed.
for (unsigned i = 0, e = GlobalsToCopy.size(); i != e; ++i)
RC.getClonedNH(Graph.getNodeForValue(GlobalsToCopy[i]));
}
/// mergeInGraph - The method is used for merging graphs together. If the
/// argument graph is not *this, it makes a clone of the specified graph, then
/// merges the nodes specified in the call site with the formal arguments in the
/// graph.
///
void DSGraph::mergeInGraph(const DSCallSite &CS, const Function &F,
const DSGraph &Graph, unsigned CloneFlags) {
// Set up argument bindings.
std::vector<DSNodeHandle> Args;
Graph.getFunctionArgumentsForCall(&F, Args);
mergeInGraph(CS, Args, Graph, CloneFlags);
}
/// getCallSiteForArguments - Get the arguments and return value bindings for
/// the specified function in the current graph.
///
DSCallSite DSGraph::getCallSiteForArguments(const Function &F) const {
std::vector<DSNodeHandle> Args;
for (Function::const_arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I)
if (isa<PointerType>(I->getType()))
Args.push_back(getNodeForValue(I));
return DSCallSite(CallSite(), getReturnNodeFor(F), getVANodeFor(F), &F, Args);
}
/// getDSCallSiteForCallSite - Given an LLVM CallSite object that is live in
/// the context of this graph, return the DSCallSite for it.
DSCallSite DSGraph::getDSCallSiteForCallSite(CallSite CS) const {
DSNodeHandle RetVal, VarArg;
Instruction *I = CS.getInstruction();
if (shouldHaveNodeForValue(I))
RetVal = getNodeForValue(I);
//FIXME: Here we trust the signature of the callsite to determine which arguments
//are var-arg and which are fixed. Apparently we can't assume this, but I'm not sure
//of a better way. For now, this assumption is known limitation.
const FunctionType *CalleeFuncType = DSCallSite::FunctionTypeOfCallSite(CS);
int NumFixedArgs = CalleeFuncType->getNumParams();
// Sanity check--this really, really shouldn't happen
if (!CalleeFuncType->isVarArg())
assert(CS.arg_size() == static_cast<unsigned>(NumFixedArgs) &&
"Too many arguments/incorrect function signature!");
std::vector<DSNodeHandle> Args;
Args.reserve(CS.arg_end()-CS.arg_begin());
// Calculate the arguments vector...
for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); I != E; ++I)
if (isa<PointerType>((*I)->getType())) {
DSNodeHandle ArgNode; // Initially empty
if (shouldHaveNodeForValue(*I)) ArgNode = getNodeForValue(*I);
if (I - CS.arg_begin() < NumFixedArgs) {
Args.push_back(ArgNode);
} else {
VarArg.mergeWith(ArgNode);
}
}
//
// Add a new function call entry. We get the called value from the call site
// and strip pointer casts instead of asking the CallSite class to do that
// since CallSite::getCalledFunction() returns 0 if the called value is
// a bit-casted function constant.
//
if (Function *F=dyn_cast<Function>(CS.getCalledValue()->stripPointerCasts()))
return DSCallSite(CS, RetVal, VarArg, F, Args);
else
return DSCallSite(CS, RetVal, VarArg,
getNodeForValue(CS.getCalledValue()).getNode(), Args);
}
// markIncompleteNodes - Mark the specified node as having contents that are not
// known with the current analysis we have performed. Because a node makes all
// of the nodes it can reach incomplete if the node itself is incomplete, we
// must recursively traverse the data structure graph, marking all reachable
// nodes as incomplete.
//
static void markIncompleteNode(DSNode *N) {
// Stop recursion if no node, or if node already marked...
if (N == 0 || N->isIncompleteNode()) return;
// Actually mark the node
N->setIncompleteMarker();
// Recursively process children...
for (DSNode::edge_iterator ii = N->edge_begin(), ee = N->edge_end();
ii != ee; ++ii)
markIncompleteNode(ii->second.getNode());
}
static void markIncomplete(DSCallSite &Call) {
// Then the return value is certainly incomplete!
markIncompleteNode(Call.getRetVal().getNode());
markIncompleteNode(Call.getVAVal().getNode());
// All objects pointed to by function arguments are incomplete!
for (unsigned i = 0, e = Call.getNumPtrArgs(); i != e; ++i)
markIncompleteNode(Call.getPtrArg(i).getNode());
}
// markIncompleteNodes - Traverse the graph, identifying nodes that may be
// modified by other functions that have not been resolved yet. This marks
// nodes that are reachable through three sources of "unknownness":
//
// Global Variables, Function Calls, and Incoming Arguments
//
// For any node that may have unknown components (because something outside the
// scope of current analysis may have modified it), the 'Incomplete' flag is
// added to the NodeType.
//
void DSGraph::markIncompleteNodes(unsigned Flags) {
// Mark any incoming arguments as incomplete.
if (Flags & DSGraph::MarkFormalArgs) {
for (ReturnNodesTy::iterator FI = ReturnNodes.begin(), E =ReturnNodes.end();
FI != E; ++FI) {
const Function &F = *FI->first;
for (Function::const_arg_iterator I = F.arg_begin(), E = F.arg_end();
I != E; ++I)
if (isa<PointerType>(I->getType()))
markIncompleteNode(getNodeForValue(I).getNode());
markIncompleteNode(FI->second.getNode());
}
// Mark all vanodes as incomplete (they are also arguments)
for (vanodes_iterator I = vanodes_begin(), E = vanodes_end();
I != E; ++I)
markIncompleteNode(I->second.getNode());
}
// Mark stuff passed into functions calls as being incomplete.
if (!shouldUseAuxCalls())
for (FunctionListTy::iterator I = FunctionCalls.begin(),
E = FunctionCalls.end(); I != E; ++I)
markIncomplete(*I);
else
for (FunctionListTy::iterator I = AuxFunctionCalls.begin(),
E = AuxFunctionCalls.end(); I != E; ++I)
markIncomplete(*I);
// Mark all global nodes as incomplete that aren't initialized and constant.
if ((Flags & DSGraph::IgnoreGlobals) == 0)
for (DSScalarMap::global_iterator I = ScalarMap.global_begin(),
E = ScalarMap.global_end(); I != E; ++I)
if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(*I)) {
if (!(GV->hasInitializer() && GV->isConstant())){
markIncompleteNode(ScalarMap[GV].getNode());
}
}
// Mark any node with the VAStart flag as incomplete.
if (Flags & DSGraph::MarkVAStart) {
for (node_iterator i=node_begin(); i != node_end(); ++i) {
if (i->isVAStartNode())
markIncompleteNode(i);
}
}
}
//
// Function: markExternalNode()
//
// Description:
// Marks the specified node, and all that's reachable from it, as external.
// It uses 'processedNodes' to track recursion.
//
static void markExternalNode(DSNode *N, DenseSet<DSNode *> & processedNodes) {
// Stop recursion if no node, or if node already processed
if (N == 0 || processedNodes.count(N) ) return;
processedNodes.insert(N);
// Actually mark the node
N->setExternalMarker();
// FIXME: Should we 'collapse' the node as well?
// Recursively process children...
for (DSNode::edge_iterator ii = N->edge_begin(), ee = N->edge_end();
ii != ee; ++ii)
markExternalNode(ii->second.getNode(), processedNodes);
}
// markExternal --marks the specified callsite external, using 'processedNodes' to track recursion.
static void markExternal(const DSCallSite &Call, DenseSet<DSNode *> & processedNodes) {
markExternalNode(Call.getRetVal().getNode(), processedNodes);
markExternalNode(Call.getVAVal().getNode(), processedNodes);
// Mark all pointer arguments...
for (unsigned i = 0, e = Call.getNumPtrArgs(); i != e; ++i)
markExternalNode(Call.getPtrArg(i).getNode(), processedNodes);
}
//
// Method: propagateExternal()
//
// Description:
// Walk the given DSGraph and ensure that, within this graph,
// everything reachable from a node marked External is also marked External.
//
static void propagateExternal(DSGraph * G, DenseSet<DSNode *> & processedNodes) {
DSGraph::node_iterator I = G->node_begin(),
E = G->node_end();
for ( ; I != E; ++I ) {
if (I->isExternalNode())
markExternalNode(&*I, processedNodes);
}
}
//
// Method: computeIntPtrFlags()
//
// Description:
// Mark all nodes that must get P2 flags due to type overlap.
//
void DSGraph::computeIntPtrFlags() {
DSGraph::node_iterator I = node_begin(),
E = node_end();
for ( ; I != E; ++I ) {
I->markIntPtrFlags();
}
}
// computeExternalFlags -- mark all reachable from external as external
void DSGraph::computeExternalFlags(unsigned Flags) {
DenseSet<DSNode *> processedNodes;
// Reset if indicated
if (Flags & ResetExternal) {
maskNodeTypes(~DSNode::ExternalNode);
}
// Make sure that everything reachable from something already external is
// also external
propagateExternal(this, processedNodes);
// If requested, we mark all functions (their formals) in this
// graph (read: SCC) as external.
if (Flags & MarkFormalsExternal) {
for (ReturnNodesTy::iterator FI = ReturnNodes.begin(), E =ReturnNodes.end();
FI != E; ++FI) {
const Function &F = *FI->first;
// Mark its arguments, return value (and vanode) as external.
for (Function::const_arg_iterator I = F.arg_begin(), E = F.arg_end();
I != E; ++I){
if(TypeInferenceOptimize) {
if(I->getName().str() == "argv")
continue;
}
if (isa<PointerType>(I->getType()))
markExternalNode(getNodeForValue(I).getNode(), processedNodes);
}
markExternalNode(FI->second.getNode(), processedNodes);
markExternalNode(getVANodeFor(F).getNode(), processedNodes);
}
}
// If requested, look for callsites to external functions and make
// sure that they're marked external as appropriate.
if (Flags & ProcessCallSites) {
// Get List of all callsites, resolved or not...
std::list<DSCallSite> AllCalls;
AllCalls.insert(AllCalls.begin(), fc_begin(), fc_end());
AllCalls.insert(AllCalls.begin(), afc_begin(), afc_end());
// ...and use that list to find all CallSites that call external functions
// and mark them accordingly.
for (std::list<DSCallSite>::iterator I = AllCalls.begin(),
E = AllCalls.end(); I != E; ++I) {
bool shouldBeMarkedExternal = false;
// Figure out what this callsite calls...
std::vector<const Function *> Functions;
if (I->isDirectCall())
Functions.push_back(I->getCalleeFunc());
else
I->getCalleeNode()->addFullFunctionList(Functions);
// ...And examine each callee:
for (std::vector<const Function *>::iterator II = Functions.begin(),
EE = Functions.end();
(II != EE) && !shouldBeMarkedExternal; ++II) {
// Calls to external functions should be marked external
shouldBeMarkedExternal |= (*II)->isDeclaration();
}
// If this callsite can call external code, it better be the case that
// the pointer arguments and the return values are all marked external
// (and what's reachable from them)
if (shouldBeMarkedExternal) {
markExternal(*I, processedNodes);
}
}
}
// Finally handle all external globals...
for (DSScalarMap::global_iterator I = ScalarMap.global_begin(),
E = ScalarMap.global_end(); I != E; ++I) {
if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(*I)) {
if(TypeInferenceOptimize) {
if(GV->getName().str() == "stderr"){
continue;
}
if(GV->getName().str() == "stdout"){
continue;
}
if(GV->getName().str() == "stdin"){
continue;
}
}
// If the global is external... mark it as such!
DSNode * N = ScalarMap[GV].getNode();
if (!(GV->hasInternalLinkage() || GV->hasPrivateLinkage()) || N->isExternalNode())
markExternalNode(N, processedNodes);
}
}
}
static inline void killIfUselessEdge(DSNodeHandle &Edge) {
if (DSNode * N = Edge.getNode()) // Is there an edge?
if (N->getNumReferrers() == 1) // Does it point to a lonely node?
// No interesting info?
if ((N->getNodeFlags() & ~DSNode::IncompleteNode) == 0
&& N->hasNoType()
&& !N->isNodeCompletelyFolded())
Edge.setTo(0, 0); // Kill the edge!
}
static void removeIdenticalCalls(DSGraph::FunctionListTy &Calls) {
// Remove trivially identical function calls
unsigned NumDeleted = 0;
// First, scan through killing off useless edges and trivially dead callsites
for (DSGraph::FunctionListTy::iterator I = Calls.begin(), E = Calls.end();
I != E; ) {
DSCallSite &CS = *I;
// If the return value or any arguments point to a void node with no
// information at all in it, and the call node is the only node to point
// to it, remove the edge to the node (killing the node).
//
killIfUselessEdge(CS.getRetVal());
killIfUselessEdge(CS.getVAVal());
for (unsigned a = 0, e = CS.getNumPtrArgs(); a != e; ++a)
killIfUselessEdge(CS.getPtrArg(a));
// If this is an indirect callsite, but the Callee DSNode isn't
// tied to from anything, remove it trivially.
if (CS.isIndirectCall()) {
DSNode *Callee = CS.getCalleeNode();
if (Callee->getNumReferrers() == 1 && Callee->isCompleteNode() &&
Callee->isEmptyGlobals()) { // No useful info?
DEBUG(errs() << "WARNING: Useless call site found.\n");
I = Calls.erase(I);
E = Calls.end();
++NumDeleted;
continue;
}
}
++I;
}
// Now scan for redundant indirect callsites
// First, sort by callee (using DSCallSite::operator<)
sort(Calls);
// Then find adjacent callsites that are equivalent and handle accordingly
DSGraph::FunctionListTy::iterator I = Calls.begin();
while((I = std::adjacent_find(I, Calls.end())) != Calls.end()) {
DSGraph::FunctionListTy::iterator Second = I;
DSCallSite &DCS1 = *I, &DCS2 = *++Second;
if (DCS1.isIndirectCall()) {
// Merge them together (into the first one)
DCS1.mergeWith(DCS2);
}
// Remove the second one
++NumDeleted;
Calls.erase(Second);
// Carry on, searching from 'I' (first one)...
}
// Track the number of call nodes merged away...
NumCallNodesMerged += NumDeleted;
if (NumDeleted)
DEBUG(errs() << "Merged " << NumDeleted << " call nodes.\n");
}
// removeTriviallyDeadNodes - After the graph has been constructed, this method
// removes all unreachable nodes that are created because they got merged with
// other nodes in the graph. These nodes will all be trivially unreachable, so
// we don't have to perform any non-trivial analysis here.
//
void DSGraph::removeTriviallyDeadNodes() {
/// NOTE: This code is disabled. This slows down DSA on 177.mesa
/// substantially!
// Loop over all of the nodes in the graph, calling getNode on each field.
// This will cause all nodes to update their forwarding edges, causing
// forwarded nodes to be delete-able. Further, reclaim any memory used by
// useless edge or type entries
for (node_iterator NI = node_begin(), E = node_end(); NI != E; ++NI)
for (DSNode::edge_iterator ii = NI->edge_begin(), ee = NI->edge_end();
ii != ee; ++ii) {
ii->second.getNode()->cleanEdges();
}
// Likewise, forward any edges from the scalar nodes. While we are at it,
// clean house a bit.
for (DSScalarMap::iterator I = ScalarMap.begin(), E = ScalarMap.end();
I != E; ++I)
I->second.getNode();
bool isGlobalsGraph = !GlobalsGraph;
for (NodeListTy::iterator NI = Nodes.begin(), E = Nodes.end(); NI != E; ) {
DSNode &Node = *NI;
// Do not remove *any* global nodes in the globals graph.
// This is a special case because such nodes may not have I, M, R flags set.
if (Node.isGlobalNode() && isGlobalsGraph) {
++NI;
continue;
}
if (Node.isCompleteNode() && !Node.isModifiedNode() && !Node.isReadNode()) {
// This is a useless node if it has no mod/ref info (checked above),
// outgoing edges (which it cannot, as it is not modified in this
// context), and it has no incoming edges. If it is a global node it may
// have all of these properties and still have incoming edges, due to the
// scalar map, so we check those now.
//
if (Node.getNumReferrers() == Node.numGlobals()) {
// Loop through and make sure all of the globals are referring directly
// to the node...
for (DSNode::globals_iterator j = Node.globals_begin(), e = Node.globals_end();
j != e; ++j) {
getNodeForValue(*j).getNode();
assert((getNodeForValue(*j).getNode()) == &Node && "ScalarMap doesn't match globals list!");
}
// Make sure NumReferrers still agrees, if so, the node is truly dead.
if (Node.getNumReferrers() == Node.numGlobals()) {
for (DSNode::globals_iterator j = Node.globals_begin(), e = Node.globals_end();
j != e; ++j)
if (ScalarMap.find(*j) != ScalarMap.end())
ScalarMap.erase(*j);
Node.makeNodeDead();
++NumTrivialGlobalDNE;
}
}
}
if ((Node.getNodeFlags() == 0 && Node.hasNoReferrers())
|| (isGlobalsGraph && Node.hasNoReferrers() && !Node.isGlobalNode())){
// This node is dead!
NI = Nodes.erase(NI); // Erase & remove from node list.
++NumTrivialDNE;
} else {
++NI;
}
}
#if 0
#endif
removeIdenticalCalls(FunctionCalls);
removeIdenticalCalls(AuxFunctionCalls);
}
// CanReachAliveNodes - Simple graph walker that recursively traverses the graph
// looking for a node that is marked alive. If an alive node is found, return
// true, otherwise return false. If an alive node is reachable, this node is
// marked as alive...
//
static bool CanReachAliveNodes(DSNode *N, DenseSet<const DSNode*> &Alive,
DenseSet<const DSNode*> &Visited,
bool IgnoreGlobals) {
if (N == 0) return false;
assert(N->isForwarding() == 0 && "Cannot mark a forwarded node!");
// If this is a global node, it will end up in the globals graph anyway, so we
// don't need to worry about it.
if (IgnoreGlobals && N->isGlobalNode()) return false;
// If we know that this node is alive, return so!
if (Alive.count(N)) return true;
// Otherwise, we don't think the node is alive yet, check for infinite
// recursion.
if (Visited.count(N)) return false; // Found a cycle
Visited.insert(N); // No recursion, insert into Visited...
for (DSNode::edge_iterator I = N->edge_begin(),E = N->edge_end(); I != E; ++I)
if (CanReachAliveNodes(I->second.getNode(), Alive, Visited, IgnoreGlobals)) {
N->markReachableNodes(Alive);
return true;
}
return false;
}
// CallSiteUsesAliveArgs - Return true if the specified call site can reach any
// alive nodes.
//
static bool CallSiteUsesAliveArgs(const DSCallSite &CS,
DenseSet<const DSNode*> &Alive,
DenseSet<const DSNode*> &Visited,
bool IgnoreGlobals) {
if (CanReachAliveNodes(CS.getRetVal().getNode(), Alive, Visited,
IgnoreGlobals))
return true;
if (CanReachAliveNodes(CS.getVAVal().getNode(), Alive, Visited, IgnoreGlobals))
return true;
if (CS.isIndirectCall() &&
CanReachAliveNodes(CS.getCalleeNode(), Alive, Visited, IgnoreGlobals))
return true;
for (unsigned i = 0, e = CS.getNumPtrArgs(); i != e; ++i)
if (CanReachAliveNodes(CS.getPtrArg(i).getNode(), Alive, Visited,
IgnoreGlobals))
return true;
return false;
}
// removeDeadNodes - Use a more powerful reachability analysis to eliminate
// subgraphs that are unreachable. This often occurs because the data
// structure doesn't "escape" into it's caller, and thus should be eliminated
// from the caller's graph entirely. This is only appropriate to use when
// inlining graphs.
//
// This function also clones information about globals back into the globals
// graph before it deletes the nodes.
void DSGraph::removeDeadNodes(unsigned Flags) {
DEBUG(AssertGraphOK(); if (GlobalsGraph) GlobalsGraph->AssertGraphOK());
// Reduce the amount of work we have to do... remove dummy nodes left over by
// merging...
removeTriviallyDeadNodes();
// FIXME: Merge non-trivially identical call nodes...
// Alive - a set that holds all nodes found to be reachable/alive.
DenseSet<const DSNode*> Alive;
std::vector<std::pair<const Value*, DSNode*> > GlobalNodes;
// Copy and merge all information about globals to the GlobalsGraph if this is
// not a final pass (where unreachable globals are removed).
//
// Strip all alloca bits since we are merging information into the globals
// graph.
// Strip all incomplete bits since they are short-lived properties and they
// will be correctly computed when rematerializing nodes into the functions.
//
// This code merges information learned about the globals in 'this' graph
// back into the globals graph, before it deletes any such global nodes,
// (with some new information possibly) from 'this' current function graph.
ReachabilityCloner GGCloner(GlobalsGraph, this, DSGraph::StripAllocaBit |
DSGraph::StripIncompleteBit);
// Mark all nodes reachable by (non-global) scalar nodes as alive...
for (DSScalarMap::iterator I = ScalarMap.begin(), E = ScalarMap.end();
I != E; ++I)
if (isa<GlobalValue > (I->first)) { // Keep track of global nodes
assert(!I->second.isNull() && "Null global node?");
assert(I->second.getNode()->isGlobalNode() && "Should be a global node!");
GlobalNodes.push_back(std::make_pair(I->first, I->second.getNode()));
// Make sure that all globals are cloned over as roots.
if (!(Flags & DSGraph::RemoveUnreachableGlobals) && GlobalsGraph) {
GGCloner.getClonedNH(I->second);
}
} else {
I->second.getNode()->markReachableNodes(Alive);
}
// The return values are alive as well.
for (ReturnNodesTy::iterator I = ReturnNodes.begin(), E = ReturnNodes.end();
I != E; ++I)
I->second.getNode()->markReachableNodes(Alive);
// Mark any nodes reachable by primary calls as alive...
for (fc_iterator I = fc_begin(), E = fc_end(); I != E; ++I)
I->markReachableNodes(Alive);
// Now find globals and aux call nodes that are already live or reach a live
// value (which makes them live in turn), and continue till no more are found.
//
bool Iterate;
DenseSet<const DSNode*> Visited;
std::set<const DSCallSite*> AuxFCallsAlive;
do {
Visited.clear();
// If any global node points to a non-global that is "alive", the global is
// "alive" as well... Remove it from the GlobalNodes list so we only have
// unreachable globals in the list.
//
Iterate = false;
if (!(Flags & DSGraph::RemoveUnreachableGlobals))
for (unsigned i = 0; i != GlobalNodes.size(); ++i)
if (CanReachAliveNodes(GlobalNodes[i].second, Alive, Visited,
Flags & DSGraph::RemoveUnreachableGlobals)) {
std::swap(GlobalNodes[i--], GlobalNodes.back()); // Move to end to...
GlobalNodes.pop_back(); // erase efficiently
Iterate = true;
}
// Mark only unresolvable call nodes for moving to the GlobalsGraph since
// call nodes that get resolved will be difficult to remove from that graph.
// The final unresolved call nodes must be handled specially at the end of
// the BU pass (i.e., in main or other roots of the call graph).
for (afc_iterator CI = afc_begin(), E = afc_end(); CI != E; ++CI)
if (!AuxFCallsAlive.count(&*CI) &&
(CI->isIndirectCall()
|| CallSiteUsesAliveArgs(*CI, Alive, Visited,
Flags & DSGraph::RemoveUnreachableGlobals))) {
CI->markReachableNodes(Alive);
AuxFCallsAlive.insert(&*CI);
Iterate = true;
}
} while (Iterate);
// If only some of the aux calls are alive
if (AuxFCallsAlive.size() != AuxFunctionCalls.size()) {
// Move dead aux function calls to the end of the list
FunctionListTy::iterator Erase = AuxFunctionCalls.end();
for (FunctionListTy::iterator CI = AuxFunctionCalls.begin(); CI != Erase; )
if (AuxFCallsAlive.count(&*CI))
++CI;
else {
// Copy and merge global nodes and dead aux call nodes into the
// GlobalsGraph, and all nodes reachable from those nodes. Update their
// target pointers using the GGCloner.
//
if (!(Flags & DSGraph::RemoveUnreachableGlobals))
GlobalsGraph->AuxFunctionCalls.push_back(DSCallSite(*CI, GGCloner));
std::swap(*CI, *--Erase);
}
AuxFunctionCalls.erase(Erase, AuxFunctionCalls.end());
}
AuxFCallsAlive.clear();
// We are finally done with the GGCloner so we can destroy it.
GGCloner.destroy();
// At this point, any nodes which are visited, but not alive, are nodes
// which can be removed. Loop over all nodes, eliminating completely
// unreachable nodes.
//
std::vector<DSNode*> DeadNodes;
DeadNodes.reserve(Nodes.size());
for (NodeListTy::iterator NI = Nodes.begin(), E = Nodes.end(); NI != E;) {
DSNode *N = NI++;
assert(!N->isForwarding() && "Forwarded node in nodes list?");
if (!Alive.count(N)) {
Nodes.remove(N);
assert(!N->isForwarding() && "Cannot remove a forwarding node!");
DeadNodes.push_back(N);
N->dropAllReferences();
++NumDNE;
}
}
// Remove all unreachable globals from the ScalarMap.
// If flag RemoveUnreachableGlobals is set, GlobalNodes has only dead nodes.
// In either case, the dead nodes will not be in the set Alive.
for (unsigned i = 0, e = GlobalNodes.size(); i != e; ++i)
if (!Alive.count(GlobalNodes[i].second))
ScalarMap.erase(GlobalNodes[i].first);
else
assert((Flags & DSGraph::RemoveUnreachableGlobals) && "non-dead global");
// Delete all dead nodes now since their referrer counts are zero.
for (unsigned i = 0, e = DeadNodes.size(); i != e; ++i)
delete DeadNodes[i];
DEBUG(AssertGraphOK(); GlobalsGraph->AssertGraphOK());
}
void DSGraph::AssertNodeContainsGlobal(const DSNode *N, const GlobalValue *GV) const {
assert(std::find(N->globals_begin(),N->globals_end(), GV) !=
N->globals_end() && "Global value not in node!");
}
void DSGraph::AssertCallSiteInGraph(const DSCallSite &CS) const {
if (CS.isIndirectCall()) {
AssertNodeInGraph(CS.getCalleeNode());
#if 0
if (CS.getNumPtrArgs() && CS.getCalleeNode() == CS.getPtrArg(0).getNode() &&
CS.getCalleeNode() && CS.getCalleeNode()->getGlobals().empty())
DEBUG(errs() << "WARNING: WEIRD CALL SITE FOUND!\n");
#endif
}
AssertNodeInGraph(CS.getRetVal().getNode());
AssertNodeInGraph(CS.getVAVal().getNode());
for (unsigned j = 0, e = CS.getNumPtrArgs(); j != e; ++j)
AssertNodeInGraph(CS.getPtrArg(j).getNode());
}
void DSGraph::AssertCallNodesInGraph() const {
for (fc_iterator I = fc_begin(), E = fc_end(); I != E; ++I)
AssertCallSiteInGraph(*I);
}
void DSGraph::AssertAuxCallNodesInGraph() const {
for (afc_const_iterator I = afc_begin(), E = afc_end(); I != E; ++I)
AssertCallSiteInGraph(*I);
}
void DSGraph::AssertGraphOK() const {
for (node_const_iterator NI = node_begin(), E = node_end(); NI != E; ++NI)
NI->assertOK();
for (ScalarMapTy::const_iterator I = ScalarMap.begin(),
E = ScalarMap.end(); I != E; ++I) {
assert(!I->second.isNull() && "Null node in scalarmap!");
AssertNodeInGraph(I->second.getNode());
if (const GlobalValue *GV = dyn_cast<GlobalValue>(I->first)) {
assert(I->second.getNode()->isGlobalNode() &&
"Global points to node, but node isn't global?");
AssertNodeContainsGlobal(I->second.getNode(), GV);
}
}
AssertCallNodesInGraph();
AssertAuxCallNodesInGraph();
// Check that all pointer arguments to any functions in this graph have
// destinations.
for (ReturnNodesTy::const_iterator RI = ReturnNodes.begin(),
E = ReturnNodes.end();
RI != E; ++RI) {
const Function &F = *RI->first;
for (Function::const_arg_iterator AI = F.arg_begin(); AI != F.arg_end(); ++AI)
if (isa<PointerType>(AI->getType()))
assert(!getNodeForValue(AI).isNull() &&
"Pointer argument must be in the scalar map!");
if (F.isVarArg())
assert(VANodes.find(&F) != VANodes.end() &&
"VarArg function missing VANode!");
}
}
/// computeNodeMapping - Given roots in two different DSGraphs, traverse the
/// nodes reachable from the two graphs, computing the mapping of nodes from the
/// first to the second graph. This mapping may be many-to-one (i.e. the first
/// graph may have multiple nodes representing one node in the second graph),
/// but it will not work if there is a one-to-many or many-to-many mapping.
///
/// Inputs:
/// @NH1 - The first root value for which a node mapping is
/// desired. This value can have a NULL DSNode.
/// @NH2 - The second root value for which a node mapping is
/// desired. This value can have a NULL DSNode.
/// @StrictChecking - Flags whether strict sanity checks should be enforced.
///
/// Outputs:
/// @NodeMap - A mapping of DSNodes to DSNode handles providing the node
/// mapping desired by the caller.
///
/// Notes:
/// FIXME: Why was StrictChecking not passed in the recursive calls?
/// FIXME: Why isn't StrictChecking always desired?
///
void DSGraph::computeNodeMapping(const DSNodeHandle &NH1,
const DSNodeHandle &NH2, NodeMapTy &NodeMap,
bool StrictChecking) {
//
// Get the DSNodes associated with the root values. If either one of them is
// NULL, then we are done.
//
DSNode *N1 = NH1.getNode(), *N2 = NH2.getNode();
if (N1 == 0 || N2 == 0) return;
DSNodeHandle &Entry = NodeMap[N1];
if (!Entry.isNull()) {
// Termination of recursion!
if (StrictChecking) {
assert(Entry.getNode() == N2 && "Inconsistent mapping detected!");
assert((Entry.getOffset() == (NH2.getOffset()-NH1.getOffset()) ||
Entry.getNode()->isNodeCompletelyFolded()) &&
"Inconsistent mapping detected!");
}
return;
}
//
// Modify the entry in the node map so that the DSNode from the first
// DSNodeHandle is mapped to the second DSNodeHandle.
//
// FIXME: AA:I am not sure what the right mapping for the
// following case is. I believe we do not need to create any
// new mapping.
//assert(((signed int)(NH2.getOffset()-NH1.getOffset())>=0) && " Underflow error ");
if(NH2.getOffset() >= NH1.getOffset()) {
Entry.setTo(N2, NH2.getOffset()-NH1.getOffset());
}
//
// The two DSNodes that we have could be strucures with outgoing links to
// other DSNodes. Recursively map such outgoing edges together, too.
//
//
// If the second DSNode has no outgoing edges, then stop processing. There
// is nothing more to do.
//
unsigned N2Size = N2->getSize();
if (N2Size == 0) return; // No edges to map to.
//
// Recursively link outgoing edges together.
//
int N2Idx = NH2.getOffset()-NH1.getOffset();
for (unsigned i = 0, e = N1->getSize(); i < e; ++i) {
const DSNodeHandle &N1NH = N1->getLink(i);
//
// Don't call N2->getLink if not needed (avoiding crash if N2Idx is not
// aligned correctly).
//
if (!N1NH.isNull()) {
//
// Compute the offset into the second DSNode.
//
unsigned offset = 0;
if (unsigned(N2Idx)+i < N2Size)
offset = N2Idx+i;
else
offset = (unsigned(N2Idx+i) % N2Size);
//
// Compute the node mapping for the link.
//
computeNodeMapping (N1NH, N2->getLink(offset), NodeMap, StrictChecking);
}
}
}
/// computeGToGGMapping - Compute the mapping of nodes in the global graph to
/// nodes in this graph.
void DSGraph::computeGToGGMapping(NodeMapTy &NodeMap) {
DSGraph &GG = *getGlobalsGraph();
DSScalarMap &SM = getScalarMap();
//
// Iterate through all values used by this function (i.e., those values in
// the local graph in the function's DSGraph). For each one, compute the
// mapping between its DSNode in the local graph and its DSNode in the
// globals graph.
//
// Note that we use variables to hold intermediate values. This allows us
// to query these values more easily in the debugger.
//
for (DSScalarMap::global_iterator I = SM.global_begin(),
E = SM.global_end(); I != E; ++I) {
// Local value in the scalar map
const Value * LocalValue = *I;
// DSNode Handle for the value in the local graph
DSNodeHandle LocalNodeHandle = SM[LocalValue];
// DSNode Handle for the value in the globals graph
DSNodeHandle GlobalNodeHandle = GG.getNodeForValue(LocalValue);
//
// Add to the node mapping the mapping between the DSNode in the local
// graph and the DSNode in the globals graph.
//
DSGraph::computeNodeMapping(LocalNodeHandle, GlobalNodeHandle, NodeMap);
}
}
/// computeGGToGMapping - Compute the mapping of nodes in the global graph to
/// nodes in this graph. Note that any uses of this method are probably bugs,
/// unless it is known that the globals graph has been merged into this graph!
void DSGraph::computeGGToGMapping(InvNodeMapTy &InvNodeMap) {
NodeMapTy NodeMap;
computeGToGGMapping(NodeMap);
while (!NodeMap.empty()) {
InvNodeMap.insert(std::make_pair(NodeMap.begin()->second,
NodeMap.begin()->first));
NodeMap.erase(NodeMap.begin());
}
}
/// computeCalleeCallerMapping - Given a call from a function in the current
/// graph to the 'Callee' function (which lives in 'CalleeGraph'), compute the
/// mapping of nodes from the callee to nodes in the caller.
void DSGraph::computeCalleeCallerMapping(DSCallSite CS, const Function &Callee,
DSGraph &CalleeGraph,
NodeMapTy &NodeMap) {
DSCallSite CalleeArgs =
CalleeGraph.getCallSiteForArguments(const_cast<Function&>(Callee));
computeNodeMapping(CalleeArgs.getRetVal(), CS.getRetVal(), NodeMap);
computeNodeMapping(CalleeArgs.getVAVal(), CS.getVAVal(), NodeMap);
unsigned NumArgs = CS.getNumPtrArgs();
if (NumArgs > CalleeArgs.getNumPtrArgs())
NumArgs = CalleeArgs.getNumPtrArgs();
for (unsigned i = 0; i != NumArgs; ++i)
computeNodeMapping(CalleeArgs.getPtrArg(i), CS.getPtrArg(i), NodeMap);
// Map the nodes that are pointed to by globals.
DSScalarMap &CalleeSM = CalleeGraph.getScalarMap();
DSScalarMap &CallerSM = getScalarMap();
if (CalleeSM.global_size() >= CallerSM.global_size()) {
for (DSScalarMap::global_iterator GI = CallerSM.global_begin(),
E = CallerSM.global_end(); GI != E; ++GI)
if (CalleeSM.global_count(*GI))
computeNodeMapping(CalleeSM[*GI], CallerSM[*GI], NodeMap);
} else {
for (DSScalarMap::global_iterator GI = CalleeSM.global_begin(),
E = CalleeSM.global_end(); GI != E; ++GI)
if (CallerSM.global_count(*GI))
computeNodeMapping(CalleeSM[*GI], CallerSM[*GI], NodeMap);
}
}
/// updateFromGlobalGraph - This function rematerializes global nodes and
/// nodes reachable from them from the globals graph into the current graph.
///
void DSGraph::updateFromGlobalGraph() {
ReachabilityCloner RC(this, GlobalsGraph, 0);
// Clone the non-up-to-date global nodes into this graph.
for (DSScalarMap::global_iterator I = getScalarMap().global_begin(),
E = getScalarMap().global_end(); I != E; ++I) {
DSScalarMap::iterator It = GlobalsGraph->ScalarMap.find(*I);
if (It != GlobalsGraph->ScalarMap.end())
RC.merge(getNodeForValue(*I), It->second);
}
}
//
// Function: functionIsCallable()
//
// Description:
// Determine whether the specified function can be a target of the specified
// call site. We allow the user to configure what we consider to be
// uncallable at an indirect function call site.
//
// Inputs:
// CS - The call site which calls the function.
// F - The function that is potentially called by CS.
//
// Return value:
// true - The function F can be called by the call site.
// false - The function F cannot be called by the call site.
//
bool
llvm::functionIsCallable (ImmutableCallSite CS, const Function* F) {
//Which targets do we choose?
//Conservative: all of them
//Pretty Safe: same calling convention, otherwise undefined behavior
//Safe on some archs:
//Safe?: vararg call only calling vararg functions
//Safe?: non-vararg call only calling non-vararg functions
//Safe?: iany/ptr can't be interchanged in args w/ float/double
//Not so safe: number of args matching
const PointerType* PT = cast<PointerType>(CS.getCalledValue()->getType());
const FunctionType* FT = cast<FunctionType>(PT->getElementType());
//
// If the calling convention doesn't match, then the function cannot be
// called by this call site.
//
if (!noDSACallConv && CS.getCallingConv() != F->getCallingConv())
return false;
//
// We will consider the byval parameter attribute to be a part of the calling
// convention. If an actual argument is marked byval while the formal
// argument is not (or vice-versa), then the function is not a valid target.
//
if (!noDSACallConv) {
Function::const_arg_iterator farg = F->arg_begin(), fend = F->arg_end();
for (unsigned index = 1; index < (CS.arg_size() + 1) && farg != fend;
++farg, ++index) {
if (CS.isByValArgument(index) != farg->hasByValAttr()) {
return false;
}
}
}
//
// If the caller and callee don't agree on whether the target is a vararg
// function, then the function is not a valid target.
//
if (!noDSACallVA && FT->isVarArg() != F->isVarArg())
return false;
//
// If calling this function from this call site would require an implicit
// integer to floating point cast (or vice-versa), then don't consider the
// function callable from this call site.
//
if (!noDSACallFP) {
unsigned ANumParams = F->getFunctionType()->getNumParams();
unsigned PNumParams = FT->getNumParams();
unsigned NumParams = (ANumParams < PNumParams) ? ANumParams : PNumParams;
for (unsigned index = 0; index < NumParams; ++index) {
Type * AType = F->getFunctionType()->getParamType(index);
Type * PType = FT->getParamType(index);
if ((AType->isFPOrFPVectorTy() && !PType->isFPOrFPVectorTy())
||
(!AType->isFPOrFPVectorTy() && PType->isFPOrFPVectorTy()))
return false;
}
}
if (!noDSACallNumArgs) {
if(CS.arg_size() < F->arg_size()) {
return false;
}
}
//
// We've done all the checks we've cared to do. The function F can be called
// from this call site.
//
return true;
}
//
// Method: buildCallGraph()
//
// Description:
// This method updates the given call graph with new information about targets
// of function calls that can be inferred from the unresolved call sites
// within the DSGraph.
//
// The parameter GlobalFunctionList, is a list of all the address taken
// functions in the module. This is used as the list of targets when a callee
// node is Incomplete.
//
// The parameter 'filter' determines if we should attempt to prune callees
// that are illegal to be called from the callsite.
//
void DSGraph::buildCallGraph(DSCallGraph& DCG, std::vector<const Function*>& GlobalFunctionList, bool filter) const {
//
// Get the list of unresolved call sites.
//
const FunctionListTy& Calls = getFunctionCalls();
for (FunctionListTy::const_iterator ii = Calls.begin(),
ee = Calls.end();
ii != ee; ++ii) {
//
// Direct calls are easy. We know to where they go.
//
if (ii->isDirectCall()) {
DCG.insert(ii->getCallSite(), ii->getCalleeFunc());
} else {
CallSite CS = ii->getCallSite();
std::vector<const Function*> MaybeTargets;
if(ii->getCalleeNode()->isIncompleteNode())
continue;
//
// Get the list of known targets of this function.
//
ii->getCalleeNode()->addFullFunctionList(MaybeTargets);
//
// Ensure that the call graph at least knows about (has a record of) this
// call site.
//
DCG.insert(CS, 0);
//
// Add to the call graph only function targets that have well-defined
// behavior using LLVM semantics.
//
for (std::vector<const Function*>::iterator Fi = MaybeTargets.begin(),
Fe = MaybeTargets.end(); Fi != Fe; ++Fi)
if (!filter || functionIsCallable(CS, *Fi))
DCG.insert(CS, *Fi);
else
++NumFiltered;
for (DSCallSite::MappedSites_t::iterator I = ii->ms_begin(),
E = ii->ms_end(); I != E; ++I) {
CallSite MCS = *I;
for (std::vector<const Function*>::iterator Fi = MaybeTargets.begin(),
Fe = MaybeTargets.end(); Fi != Fe; ++Fi)
if (!filter || functionIsCallable(MCS, *Fi))
DCG.insert(MCS, *Fi);
else
++NumFiltered;
}
}
}
}
void DSGraph::buildCompleteCallGraph(DSCallGraph& DCG,
std::vector<const Function*>& GlobalFunctionList, bool filter) const {
//
// Get the list of unresolved call sites.
//
const FunctionListTy& Calls = getAuxFunctionCalls();
for (FunctionListTy::const_iterator ii = Calls.begin(),
ee = Calls.end();
ii != ee; ++ii) {
if (ii->isDirectCall()) continue;
CallSite CS = ii->getCallSite();
if (DCG.callee_size(CS) != 0) continue;
std::vector<const Function*> MaybeTargets;
MaybeTargets.assign(GlobalFunctionList.begin(), GlobalFunctionList.end());
DCG.insert(CS, 0);
//
// Add to the call graph only function targets that have well-defined
// behavior using LLVM semantics.
//
for (std::vector<const Function*>::iterator Fi = MaybeTargets.begin(),
Fe = MaybeTargets.end(); Fi != Fe; ++Fi)
if (!filter || functionIsCallable(CS, *Fi))
DCG.insert(CS, *Fi);
else
++NumFiltered;
for (DSCallSite::MappedSites_t::iterator I = ii->ms_begin(),
E = ii->ms_end(); I != E; ++I) {
CallSite MCS = *I;
for (std::vector<const Function*>::iterator Fi = MaybeTargets.begin(),
Fe = MaybeTargets.end(); Fi != Fe; ++Fi) {
if (!filter || functionIsCallable(MCS, *Fi))
DCG.insert(MCS, *Fi);
else
++NumFiltered;
}
}
}
svset<const llvm::Function*> callees;
callees.insert(GlobalFunctionList.begin(), GlobalFunctionList.end());
DCG.buildIncompleteCalleeSet(callees);
}