LLVM API Documentation
#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 Type * | Ty |
unsigned | Offset |
unsigned | Idx |
std::vector< StackState > | Stack |
const TargetData & | TD |
ReachabilityCloner & | RC |
unsigned | CurNodeId |
std::vector< const DSNode * > | SCCStack |
std::map< const DSNode *, std::pair< unsigned, bool > > | NodeInfo |
#define COLLAPSE_ARRAYS_AGGRESSIVELY 0 |
#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().
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().
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().
Definition at line 1415 of file DataStructure.cpp.
Statistic NumCallNodesMerged("dsa","Number of call nodes merged") [static] |
Referenced by removeIdenticalCalls().
Referenced by llvm::DSGraph::removeDeadNodes().
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().
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().
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().
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().