DataStructure.cpp File Reference

#include "llvm/Analysis/DataStructure/DSGraphTraits.h"
#include "llvm/Function.h"
#include "llvm/GlobalVariable.h"
#include "llvm/Instructions.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Assembly/Writer.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Support/Timer.h"
#include <algorithm>

Include dependency graph for DataStructure.cpp:

Go to the source code of this file.

Defines

#define TIME_REGION(VARNAME, DESC) NamedRegionTimer VARNAME(DESC)

Functions

static bool ElementTypesAreCompatible (const Type *T1, const Type *T2, bool AllowLargerT1, const TargetData &TD)

static void MergeSortedVectors (std::vector< GlobalValue * > &Dest, const std::vector< GlobalValue * > &Src)

static bool PathExistsToClonedNode (const DSNode *N, ReachabilityCloner &RC)

static bool PathExistsToClonedNode (const DSCallSite &CS, ReachabilityCloner &RC)

static void markIncompleteNode (DSNode *N)

static void markIncomplete (DSCallSite &Call)

static void killIfUselessEdge (DSNodeHandle &Edge)

static bool nodeContainsExternalFunction (const DSNode *N)

static void removeIdenticalCalls (std::vector< DSCallSite > &Calls)

static bool CanReachAliveNodes (DSNode *N, hash_set< DSNode * > &Alive, hash_set< DSNode * > &Visited, bool IgnoreGlobals)

static bool CallSiteUsesAliveArgs (DSCallSite &CS, hash_set< DSNode * > &Alive, hash_set< DSNode * > &Visited, bool IgnoreGlobals)

Define Documentation

#define TIME_REGION ( VARNAME,
DESC ) NamedRegionTimer VARNAME(DESC)

Definition at line 40 of file DataStructure.cpp.
Referenced by llvm::DSGraph::cloneInto(), llvm::DSGraph::mergeInGraph(), llvm::DSGraph::removeDeadNodes(), llvm::DSGraph::removeTriviallyDeadNodes(), and llvm::DSGraph::updateFromGlobalGraph().

Function Documentation

static bool CallSiteUsesAliveArgs ( DSCallSite & CS,

hash_set< DSNode * > & Alive,

hash_set< DSNode * > & Visited,

bool IgnoreGlobals

) [static]

Definition at line 1744 of file DataStructure.cpp.
References CanReachAliveNodes(), llvm::DSCallSite::getCalleeNode(), llvm::DSNodeHandle::getNode(), llvm::DSCallSite::getNumPtrArgs(), llvm::DSCallSite::getPtrArg(), llvm::DSCallSite::getRetVal(), and llvm::DSCallSite::isIndirectCall().
Referenced by llvm::DSGraph::removeDeadNodes().

static bool CanReachAliveNodes ( DSNode * N,

hash_set< DSNode * > & Alive,

hash_set< DSNode * > & Visited,

bool IgnoreGlobals

) [static]

Definition at line 1714 of file DataStructure.cpp.
References llvm::DSNode::getForwardNode(), llvm::DSNode::getLink(), llvm::DSNodeHandle::getNode(), llvm::DSNode::getSize(), llvm::DSNode::isGlobalNode(), llvm::DSNode::markReachableNodes(), and llvm::DS::PointerSize.
Referenced by CallSiteUsesAliveArgs(), and llvm::DSGraph::removeDeadNodes().

static bool ElementTypesAreCompatible ( const Type * T1,

const Type * T2,

bool AllowLargerT1,

const TargetData & TD

) [static]

ElementTypesAreCompatible - Check to see if the specified types are "physically" compatible. If so, return true, else return false. We only have to check the fields in T1: T2 may be larger than T1. If AllowLargerT1 is true, then we also allow a larger T1.
Definition at line 306 of file DataStructure.cpp.
References llvm::Type::isLosslesslyConvertibleTo().
Referenced by llvm::DSNode::mergeTypeInfo().

static void killIfUselessEdge ( DSNodeHandle & Edge ) [inline, static]

Definition at line 1482 of file DataStructure.cpp.
References llvm::DSNodeHandle::getNode(), llvm::DSNode::getNodeFlags(), llvm::DSNode::getNumReferrers(), llvm::DSNode::getType(), llvm::DSNode::isNodeCompletelyFolded(), llvm::DSNodeHandle::setTo(), and llvm::Type::VoidTy.
Referenced by removeIdenticalCalls().

static void markIncomplete ( DSCallSite & Call ) [static]

Definition at line 1433 of file DataStructure.cpp.
References llvm::DSNodeHandle::getNode(), llvm::DSCallSite::getNumPtrArgs(), llvm::DSCallSite::getPtrArg(), llvm::DSCallSite::getRetVal(), and markIncompleteNode().
Referenced by llvm::DSGraph::markIncompleteNodes().

static void markIncompleteNode ( DSNode * N ) [static]

Definition at line 1420 of file DataStructure.cpp.
References llvm::DSNode::getLink(), llvm::DSNodeHandle::getNode(), llvm::DSNode::getSize(), llvm::DSNode::isIncomplete(), llvm::DS::PointerSize, and llvm::DSNode::setIncompleteMarker().
Referenced by markIncomplete(), and llvm::DSGraph::markIncompleteNodes().

static void MergeSortedVectors ( std::vector< GlobalValue * > & Dest,

const std::vector< GlobalValue * > & Src

) [static]

MergeSortedVectors - Efficiently merge a vector into another vector where duplicates are not allowed and both are sorted. This assumes that 'T's are efficiently copyable and have sane comparison semantics.
Definition at line 584 of file DataStructure.cpp.
References I, and V.
Referenced by llvm::DSNode::mergeGlobals().

static bool nodeContainsExternalFunction ( const DSNode * N ) [inline, static]

Definition at line 1491 of file DataStructure.cpp.
References llvm::DSNode::getGlobals().
Referenced by removeIdenticalCalls().

static bool PathExistsToClonedNode ( const DSCallSite & CS,

ReachabilityCloner & RC

) [static]

Definition at line 1231 of file DataStructure.cpp.
References llvm::DSNodeHandle::getNode(), llvm::DSCallSite::getNumPtrArgs(), llvm::DSCallSite::getPtrArg(), llvm::DSCallSite::getRetVal(), and PathExistsToClonedNode().

static bool PathExistsToClonedNode ( const DSNode * N,

ReachabilityCloner & RC

) [static]

Definition at line 1223 of file DataStructure.cpp.
References llvm::df_begin(), llvm::df_end(), E, llvm::ReachabilityCloner::hasClonedNode(), and I.
Referenced by llvm::DSGraph::mergeInGraph(), and PathExistsToClonedNode().

static void removeIdenticalCalls ( std::vector< DSCallSite > & Calls ) [static]

Definition at line 1499 of file DataStructure.cpp.
References DEBUG, llvm::DSCallSite::getCalleeFunc(), llvm::DSCallSite::getCalleeNode(), llvm::DSNode::getGlobals(), llvm::DSCallSite::getNumPtrArgs(), llvm::DSNode::getNumReferrers(), llvm::DSCallSite::getPtrArg(), llvm::DSCallSite::getRetVal(), llvm::DSNode::isComplete(), llvm::DSCallSite::isDirectCall(), llvm::Function::isExternal(), llvm::DSCallSite::isIndirectCall(), killIfUselessEdge(), llvm::DSCallSite::mergeWith(), nodeContainsExternalFunction(), NumCallNodesMerged, and NumDeleted.
Referenced by llvm::DSGraph::removeTriviallyDeadNodes().

Variable Documentation

Statistic NumCallNodesMerged("dsa","Number of call nodes merged") [static]

Referenced by removeIdenticalCalls().

Statistic NumDNE("dsa","Number of nodes removed by reachability") [static]

Referenced by llvm::DSGraph::removeDeadNodes().

Statistic NumFolds("dsa","Number of nodes completely folded") [static]

Referenced by llvm::DSNode::foldNodeCompletely().

Statistic NumNodeAllocated("dsa","Number of nodes allocated") [static]

Referenced by llvm::DSNode::DSNode().

Statistic NumTrivialDNE("dsa","Number of nodes trivially removed") [static]

Referenced by llvm::DSGraph::removeTriviallyDeadNodes().

Statistic NumTrivialGlobalDNE("dsa","Number of globals trivially removed") [static]

Referenced by llvm::DSGraph::removeTriviallyDeadNodes().


Defines
#define	TIME_REGION(VARNAME, DESC) NamedRegionTimer VARNAME(DESC)
Functions
static bool	ElementTypesAreCompatible (const Type T1, const Type T2, bool AllowLargerT1, const TargetData &TD)
static void	MergeSortedVectors (std::vector< GlobalValue * > &Dest, const std::vector< GlobalValue * > &Src)
static bool	PathExistsToClonedNode (const DSNode *N, ReachabilityCloner &RC)
static bool	PathExistsToClonedNode (const DSCallSite &CS, ReachabilityCloner &RC)
static void	markIncompleteNode (DSNode *N)
static void	markIncomplete (DSCallSite &Call)
static void	killIfUselessEdge (DSNodeHandle &Edge)
static bool	nodeContainsExternalFunction (const DSNode *N)
static void	removeIdenticalCalls (std::vector< DSCallSite > &Calls)
static bool	CanReachAliveNodes (DSNode N, hash_set< DSNode > &Alive, hash_set< DSNode * > &Visited, bool IgnoreGlobals)
static bool	CallSiteUsesAliveArgs (DSCallSite &CS, hash_set< DSNode * > &Alive, hash_set< DSNode * > &Visited, bool IgnoreGlobals)