LLVM API Documentation

DataStructure.cpp File Reference

#include "llvm/Analysis/DataStructure/DSGraphTraits.h"
#include "llvm/Constants.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/SCCIterator.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Support/Timer.h"
#include <iostream>
#include <algorithm>

Include dependency graph for DataStructure.cpp:

Go to the source code of this file.

Defines

#define COLLAPSE_ARRAYS_AGGRESSIVELY   0
#define TIME_REGION(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 void markIncompleteNode (DSNode *N)
static void markIncomplete (DSCallSite &Call)
static void killIfUselessEdge (DSNodeHandle &Edge)
static bool nodeContainsExternalFunction (const DSNode *N)
static void removeIdenticalCalls (std::list< DSCallSite > &Calls)
static bool CanReachAliveNodes (DSNode *N, hash_set< const DSNode * > &Alive, hash_set< const DSNode * > &Visited, bool IgnoreGlobals)
static bool CallSiteUsesAliveArgs (const DSCallSite &CS, hash_set< const DSNode * > &Alive, hash_set< const DSNode * > &Visited, bool IgnoreGlobals)

Variables

Statistic NumFolds ("dsa","Number of nodes completely folded")
Statistic NumCallNodesMerged ("dsa","Number of call nodes merged")
Statistic NumNodeAllocated ("dsa","Number of nodes allocated")
Statistic NumDNE ("dsa","Number of nodes removed by reachability")
Statistic NumTrivialDNE ("dsa","Number of nodes trivially removed")
Statistic NumTrivialGlobalDNE ("dsa","Number of globals trivially removed")
static cl::opt< unsigned > DSAFieldLimit ("dsa-field-limit", cl::Hidden, cl::desc("Number of fields to track before collapsing a node"), cl::init(256))
const TypeTy
unsigned Offset
unsigned Idx
std::vector< StackState > Stack
const TargetDataTD
ReachabilityClonerRC
unsigned CurNodeId
std::vector< const DSNode * > SCCStack
std::map< const DSNode *,
std::pair< unsigned, bool > > 
NodeInfo


Define Documentation

#define COLLAPSE_ARRAYS_AGGRESSIVELY   0

Definition at line 33 of file DataStructure.cpp.

Referenced by llvm::ReachabilityCloner::merge().

#define TIME_REGION ( VARNAME,
DESC   ) 

Definition at line 52 of file DataStructure.cpp.

Referenced by llvm::DSGraph::cloneInto(), llvm::DSGraph::mergeInGraph(), llvm::DSGraph::removeDeadNodes(), llvm::DSGraph::removeTriviallyDeadNodes(), and llvm::TDDataStructures::runOnModule().


Function Documentation

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

Definition at line 2037 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< const DSNode * > &  Alive,
hash_set< const DSNode * > &  Visited,
bool  IgnoreGlobals 
) [static]

Definition at line 2008 of file DataStructure.cpp.

References E, llvm::DSNode::getForwardNode(), and llvm::DSNode::isGlobalNode().

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 393 of file DataStructure.cpp.

References llvm::Type::isLosslesslyConvertibleTo(), and TD.

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

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

Definition at line 1723 of file DataStructure.cpp.

References llvm::DSNodeHandle::getNode(), llvm::DSNodeHandle::setTo(), and llvm::Type::VoidTy.

Referenced by removeIdenticalCalls().

static void markIncomplete ( DSCallSite Call  )  [static]

Definition at line 1672 of file DataStructure.cpp.

References llvm::Call, and markIncompleteNode().

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

static void markIncompleteNode ( DSNode N  )  [static]

Definition at line 1659 of file DataStructure.cpp.

References E, llvm::DSNode::edge_begin(), llvm::DSNode::edge_end(), llvm::DSNode::isIncomplete(), 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 721 of file DataStructure.cpp.

References V.

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

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

Definition at line 1732 of file DataStructure.cpp.

References llvm::DSNode::addFullFunctionList().

Referenced by removeIdenticalCalls().

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

Definition at line 1740 of file DataStructure.cpp.

References DEBUG, E, llvm::DSCallSite::getCalleeFunc(), llvm::DSCallSite::getCalleeNode(), llvm::DSNode::getGlobalsList(), llvm::DSNodeHandle::getNode(), llvm::DSCallSite::getNumPtrArgs(), llvm::DSNode::getNumReferrers(), llvm::DSCallSite::getPtrArg(), llvm::DSCallSite::getRetVal(), llvm::DSNode::isComplete(), llvm::DSCallSite::isDirectCall(), llvm::Function::isExternal(), llvm::DSCallSite::isIndirectCall(), llvm::DSNodeHandle::isNull(), killIfUselessEdge(), nodeContainsExternalFunction(), NumCallNodesMerged, and NumDeleted.

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


Variable Documentation

unsigned CurNodeId

Definition at line 1413 of file DataStructure.cpp.

cl::opt<unsigned> DSAFieldLimit("dsa-field-limit", cl::Hidden, cl::desc("Number of fields to track before collapsing a node"), cl::init(256)) [static]

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

unsigned Idx

Definition at line 302 of file DataStructure.cpp.

Referenced by llvm::ConstantFoldExtractElementInstruction(), llvm::ConstantFoldInsertElementInstruction(), llvm::ConvertConstantType< ConstantExpr, Type >::convert(), EvaluateStoreInto(), llvm::Interpreter::executeGEPOperation(), llvm::SCEVMulExpr::get(), llvm::SCEVAddExpr::get(), GetAddressedElementFromGlobal(), getAggregateConstantElement(), llvm::GetElementPtrInst::GetElementPtrInst(), llvm::ConstantExpr::getExtractElement(), llvm::ConstantExpr::getExtractElementTy(), llvm::GetElementPtrInst::getIndexedType(), llvm::ConstantExpr::getInsertElement(), llvm::ConstantExpr::getInsertElementTy(), llvm::DOTGraphTraits< const Function * >::getNodeLabel(), llvm::StructType::getTypeAtIndex(), llvm::X86TargetLowering::LowerOperation(), llvm::MapValue(), OptimizeGEPExpression(), llvm::BytecodeReader::ParseInstruction(), RemapOperand(), llvm::PHINode::removeIncomingValue(), and llvm::SelectionDAGLowering::visitGetElementPtr().

std::map<const DSNode*, std::pair<unsigned, bool> > NodeInfo

Definition at line 1415 of file DataStructure.cpp.

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().

unsigned Offset

Definition at line 301 of file DataStructure.cpp.

Referenced by llvm::MachineInstrBuilder::addConstantPoolIndex(), llvm::addConstantPoolReference(), llvm::addFrameReference(), llvm::MachineInstrBuilder::addGlobalAddress(), CompilationCallback(), ConvertOperandToType(), llvm::ModulePassManager::dumpPassStructure(), llvm::FunctionPassManagerT::dumpPassStructure(), llvm::BasicBlockPassManager::dumpPassStructure(), llvm::PassManagerT< llvm::BBTraits >::dumpPassStructure(), llvm::X86RegisterInfo::eliminateFrameIndex(), llvm::SparcRegisterInfo::eliminateFrameIndex(), llvm::PPCRegisterInfo::eliminateFrameIndex(), llvm::IA64RegisterInfo::eliminateFrameIndex(), llvm::AlphaRegisterInfo::eliminateFrameIndex(), llvm::AsmPrinter::EmitConstantPool(), llvm::AsmPrinter::EmitConstantValueOnly(), llvm::MachineConstantPool::getConstantPoolIndex(), llvm::ExecutionEngine::getConstantValue(), llvm::ConstantPoolSDNode::getOffset(), llvm::GlobalAddressSDNode::getOffset(), llvm::DSNodeIterator< NodeTy >::getOffset(), llvm::X86TargetLowering::LowerOperation(), llvm::AlphaTargetLowering::LowerOperation(), OperandConvertibleToType(), llvm::DSNodeIterator< NodeTy >::operator *(), llvm::DSNodeIterator< NodeTy >::operator++(), llvm::DSNodeIterator< NodeTy >::operator=(), llvm::DSNodeIterator< NodeTy >::operator==(), PPC32CompilationCallbackC(), llvm::X86IntelAsmPrinter::printOp(), llvm::X86ATTAsmPrinter::printOperand(), RemoveFromWorklist(), llvm::SelectionDAGLowering::visitGetElementPtr(), llvm::SelectionDAGLowering::visitMemIntrinsic(), and llvm::GraphWriter< GraphType >::writeEdge().

ReachabilityCloner& RC

Definition at line 1412 of file DataStructure.cpp.

Referenced by AddLiveIn(), llvm::TargetLowering::addRegisterClass(), llvm::VirtRegMap::assignVirt2StackSlot(), llvm::X86RegisterInfo::copyRegToReg(), llvm::SparcRegisterInfo::copyRegToReg(), llvm::PPCRegisterInfo::copyRegToReg(), llvm::IA64RegisterInfo::copyRegToReg(), llvm::AlphaRegisterInfo::copyRegToReg(), llvm::DSGraph::DSGraph(), EmitGEPOffset(), llvm::MRegisterInfo::getAllocatableSet(), llvm::TargetLowering::getRegClassFor(), llvm::SelectionDAGLowering::GetRegistersForValue(), isAllocatableRegister(), llvm::X86RegisterInfo::loadRegFromStackSlot(), llvm::SparcRegisterInfo::loadRegFromStackSlot(), llvm::PPCRegisterInfo::loadRegFromStackSlot(), llvm::IA64RegisterInfo::loadRegFromStackSlot(), llvm::AlphaRegisterInfo::loadRegFromStackSlot(), llvm::markRegisterUsed(), llvm::DSGraph::mergeInGraph(), llvm::LiveIntervals::runOnMachineFunction(), llvm::EquivClassGraphs::runOnModule(), llvm::CompleteBUDataStructures::runOnModule(), llvm::BUDataStructures::runOnModule(), llvm::V9LiveRange::setRegClass(), llvm::X86RegisterInfo::storeRegToStackSlot(), llvm::SparcRegisterInfo::storeRegToStackSlot(), llvm::PPCRegisterInfo::storeRegToStackSlot(), llvm::IA64RegisterInfo::storeRegToStackSlot(), and llvm::AlphaRegisterInfo::storeRegToStackSlot().

std::vector<const DSNode*> SCCStack

Definition at line 1414 of file DataStructure.cpp.

std::vector<StackState> Stack

Definition at line 307 of file DataStructure.cpp.

Referenced by llvm::EquivClassGraphs::runOnModule(), llvm::CompleteBUDataStructures::runOnModule(), and llvm::BUDataStructures::runOnModule().

const TargetData& TD

Definition at line 308 of file DataStructure.cpp.

Referenced by llvm::ConvertExpressionToType(), ConvertOperandToType(), llvm::ConvertValueToNewType(), llvm::X86SharedAsmPrinter::doFinalization(), ElementTypesAreCompatible(), llvm::AsmPrinter::EmitConstantPool(), llvm::AsmPrinter::EmitConstantValueOnly(), EmitGEPOffset(), llvm::AsmPrinter::EmitGlobalConstant(), llvm::ExpressionConvertibleToType(), llvm::MachineConstantPool::getConstantPoolIndex(), GetKnownAlignment(), getStructOffsetStep(), llvm::getStructOffsetType(), getTypeInfo(), isEliminableCastOfCast(), llvm::DSNode::mergeTypeInfo(), OperandConvertibleToType(), OptimizeGEPExpression(), OptimizeOnceStoredGlobal(), ProcessGlobalsWithSameName(), llvm::PromoteMemToReg(), llvm::LocalDataStructures::runOnModule(), llvm::ValueConvertibleToType(), and ValueRequiresCast().

const Type* Ty

Definition at line 300 of file DataStructure.cpp.

Referenced by DirectRules< ConstantClass, BuiltinType, Ty, DirectIntRules< ConstantClass, BuiltinType, Ty > >::Add(), llvm::MachineInstrBuilder::addCCReg(), llvm::MachineInstrBuilder::addMReg(), llvm::DSGraph::addObjectToGraph(), llvm::MachineInstrBuilder::addReg(), llvm::Module::addTypeName(), DirectIntRules< ConstantClass, BuiltinType, Ty >::And(), llvm::generic_gep_type_iterator< ItTy >::begin(), ByteswapSCANFResults(), calcTypeName(), CastArg(), checkType(), Coerce(), ComputeSignedMinMaxValuesFromKnownBits(), ComputeUnsignedMinMaxValuesFromKnownBits(), llvm::ConstantFoldCall(), llvm::ConstantFoldFP(), llvm::ConstantFoldGetElementPtr(), llvm::ConstantRange::ConstantRange(), llvm::ConvertExpressionToType(), ConvertOperandToType(), llvm::ConstantCreator< ConstantExpr, Type, ExprMapKeyType >::create(), llvm::ConstantCreator< UndefValue, Type, ValType >::create(), llvm::ConstantCreator< ConstantPointerNull, PointerType, ValType >::create(), llvm::ConstantCreator< ConstantAggregateZero, Type, ValType >::create(), llvm::ConstantCreator< ConstantFP, Type, uint32_t >::create(), llvm::ConstantCreator< ConstantFP, Type, uint64_t >::create(), DirectFPRules< ConstantClass, BuiltinType, Ty >::Div(), DirectIntRules< ConstantClass, BuiltinType, Ty >::Div(), DirectRules< ConstantClass, BuiltinType, Ty, DirectIntRules< ConstantClass, BuiltinType, Ty > >::Div(), llvm::AsmPrinter::EmitConstantValueOnly(), llvm::ExecutionEngine::emitGlobals(), llvm::SCEVAddRecExpr::evaluateAtIteration(), EvaluateFunction(), executeAddInst(), executeAndInst(), executeDivInst(), executeMulInst(), executeOrInst(), executeRemInst(), executeSetEQInst(), executeSetGEInst(), executeSetGTInst(), executeSetLEInst(), executeSetLTInst(), executeSetNEInst(), executeShlInst(), executeShrInst(), executeSubInst(), executeXorInst(), llvm::SCEVExpander::expandCodeFor(), llvm::SCEVExpander::expandInTy(), llvm::ExpressionConvertibleToType(), fillTypeNameTable(), findOptimalStorageSize(), llvm::FunctionLoweringInfo::FunctionLoweringInfo(), llvm::PATypeHolder::get(), llvm::SCEVAddExpr::get(), GetConstantInType(), llvm::Module::getFunction(), llvm::Module::getGlobalVariable(), llvm::TargetData::getIndexedOffset(), llvm::GetElementPtrInst::getIndexedType(), llvm::MachineFunction::getInfo(), llvm::SCEVUnknown::getIntegerSCEV(), llvm::SelectionDAGLowering::getLoadFrom(), getOrCreateDesc(), llvm::SCEVExpander::getOrInsertCanonicalInductionVariable(), llvm::Module::getOrInsertFunction(), llvm::SlotCalculator::getPlane(), llvm::getPointedToComposite(), getPromotedType(), llvm::Value::getRawType(), getSize(), llvm::SlotMachine::getSlot(), llvm::TargetData::getStructLayout(), llvm::getStructOffsetType(), getSubElementHash(), llvm::DISerializer::getTagType(), getTruncateOrZeroExtend(), llvm::Value::getType(), llvm::SCEVSDivExpr::getType(), llvm::DSNode::getType(), llvm::TargetData::getTypeAlignment(), llvm::TargetData::getTypeAlignmentShift(), getTypeDescription(), llvm::Mangler::getTypeID(), getTypeID(), getTypeInfo(), llvm::Module::getTypeName(), llvm::TargetData::getTypeSize(), llvm::SymbolTable::getUniqueName(), getVal(), getValNonImprovising(), llvm::SCEV::getValueRange(), llvm::TargetLowering::getValueType(), HandleUpRefs(), hasNullValue(), llvm::SequentialType::indexValid(), llvm::SCEVExpander::InsertCastOfTo(), llvm::TargetData::InvalidateStructLayoutInfo(), llvm::Type::isLosslesslyConvertibleTo(), isMaybeZeroSizedType(), llvm::DS::isPointerType(), llvm::ExecutionEngine::LoadValueFromMemory(), llvm::SymbolTable::lookup(), lookupInSymbolTable(), DirectRules< ConstantClass, BuiltinType, Ty, DirectIntRules< ConstantClass, BuiltinType, Ty > >::Mul(), OperandConvertibleToType(), llvm::CachedWriter::operator<<(), OptimizeGEPExpression(), DirectIntRules< ConstantClass, BuiltinType, Ty >::Or(), llvm::BytecodeReader::ParseConstantPoolValue(), ParseGlobalVariable(), llvm::BytecodeReader::ParseModuleGlobalInfo(), llvm::BytecodeReader::ParseStringConstants(), PartialFact(), printTypeInt(), DirectFPRules< ConstantClass, BuiltinType, Ty >::Rem(), DirectIntRules< ConstantClass, BuiltinType, Ty >::Rem(), llvm::TypeMapBase::RemoveFromTypesByHash(), llvm::DISerializer::Serialize(), DirectIntRules< ConstantClass, BuiltinType, Ty >::Shl(), ShouldNukeSymtabEntry(), DirectIntRules< ConstantClass, BuiltinType, Ty >::Shr(), SRAGlobal(), llvm::ExecutionEngine::StoreValueToMemory(), DirectRules< ConstantClass, BuiltinType, Ty, DirectIntRules< ConstantClass, BuiltinType, Ty > >::Sub(), ToStr(), llvm::ConstantRange::truncate(), llvm::TypeMapBase::TypeBecameConcrete(), TypeContains(), TypeHasCycleThroughItself(), TypesEqual(), llvm::ValueConvertibleToType(), ValueRequiresCast(), llvm::SCEVExpander::visitAddExpr(), llvm::SCEVExpander::visitAddRecExpr(), llvm::SelectionDAGLowering::visitAlloca(), llvm::Interpreter::visitAllocationInst(), llvm::SelectionDAGLowering::visitBinary(), llvm::Interpreter::visitBinaryOperator(), llvm::Interpreter::visitCallSite(), llvm::SelectionDAGLowering::visitGetElementPtr(), llvm::SCEVExpander::visitMulExpr(), llvm::SCEVExpander::visitSDivExpr(), llvm::Interpreter::visitShl(), llvm::Interpreter::visitShr(), llvm::Interpreter::visitVAArgInst(), llvm::AssemblyWriter::write(), llvm::WriteAsOperand(), llvm::WriteTypeSymbolic(), DirectIntRules< ConstantClass, BuiltinType, Ty >::Xor(), and llvm::ConstantRange::zeroExtend().