LLVMTCEDataDependenceGraphBuilder Class Reference

#include <LLVMTCEDataDependenceGraphBuilder.hh>

Inheritance diagram for LLVMTCEDataDependenceGraphBuilder:

Collaboration diagram for LLVMTCEDataDependenceGraphBuilder:

Public Member Functions
	LLVMTCEDataDependenceGraphBuilder (InterPassData &ipd)
virtual	~LLVMTCEDataDependenceGraphBuilder ()
virtual DataDependenceGraph *	buildFromCFG (ControlFlowGraph &cGraph, const UniversalMachine *um=NULL)
virtual DataDependenceGraph *	buildFromBB (TTAProgram::BasicBlock &bb, const UniversalMachine *um=NULL)
Public Member Functions inherited from DataDependenceGraphBuilder
	DataDependenceGraphBuilder ()
	DataDependenceGraphBuilder (InterPassData &ipd)
virtual	~DataDependenceGraphBuilder ()
void	addAliasAnalyzer (MemoryAliasAnalyzer *analyzer)
virtual DataDependenceGraph *	build (ControlFlowGraph &cGraph, DataDependenceGraph::AntidependenceLevel antidependenceLevel, const TTAMachine::Machine &mach, const UniversalMachine *um=NULL, bool createMemAndFUDeps=true, bool createDeathInformation=true, llvm::AliasAnalysis *AA=NULL)
virtual DataDependenceGraph *	build (TTAProgram::BasicBlock &bb, DataDependenceGraph::AntidependenceLevel antidependenceLevel, const TTAMachine::Machine &mach, const TCEString &ddgname="small bb", const UniversalMachine *um=NULL, bool createMemAndFUDeps=true, llvm::AliasAnalysis *AA=NULL)

Private Member Functions
void	buildLocalDDG (TTAProgram::BasicBlock &bb)

Additional Inherited Members
Protected Types inherited from DataDependenceGraphBuilder
enum	BBState { BB_UNREACHED = 0 , BB_QUEUED , BB_READY , BB_STATES }
enum	ConstructionPhase { REGISTERS_AND_PROGRAM_OPERATIONS = 0 , MEMORY_AND_SIDE_EFFECTS }
typedef ControlFlowGraph::NodeSet	BasicBlockNodeSet
typedef DataDependenceGraph::NodeSet	MNodeSet
typedef LiveRangeData::MoveNodeUseSet	MoveNodeUseSet
typedef LiveRangeData::MoveNodeUseMapSet	MoveNodeUseMapSet
typedef LiveRangeData::MoveNodeUseMap	MoveNodeUseMap
typedef LiveRangeData::MoveNodeUseSetPair	MoveNodeUseSetPair
typedef LiveRangeData::MoveNodeUsePair	MoveNodeUsePair
typedef std::map< int, TCEString >	SpecialRegisters
typedef std::vector< MemoryAliasAnalyzer * >	AliasAnalyzerVector
typedef std::map< BasicBlockNode *, BBData * >	BBDataMap
typedef std::list< BBData * >	BBDataList
Protected Member Functions inherited from DataDependenceGraphBuilder
bool	isTriggering (const MoveNode &mn)
void	updatePreceedingRegistersUsedAfter (BBData &bbd, bool firstTime)
bool	updateRegistersUsedInOrAfter (BBData &bbd)
bool	updateRegistersAliveAfter (BBData &bbd)
bool	updateMemAndFuAliveAfter (BBData &bbd)
void	createMemAndFUstateDeps ()
void	createRegisterDeps ()
void	initializeBBStates ()
BasicBlockNode *	queueFirstBB ()
void	clearUnneededBookkeeping ()
void	clearUnneededBookkeeping (TTAProgram::BasicBlock &bb, bool aliveInformationNeeded=true)
void	iterateBBs (ConstructionPhase phase)
void	searchRegisterDeaths ()
void	iterateRegisterDeaths ()
void	setSucceedingPredeps (BBData &bbd, bool queueAll, ConstructionPhase phase)
bool	appendUseMapSets (const MoveNodeUseMapSet &srcMap, MoveNodeUseMapSet &dstMap, bool addLoopProperty)
void	setSucceedingPredepsForBB (TTAProgram::BasicBlock &processedBB, BasicBlockNode &successor, bool queueAll, bool loop, ConstructionPhase phase)
void	updateBB (BBData &bbd, ConstructionPhase phase)
void	constructIndividualBB (ConstructionPhase phase)
void	constructIndividualFromInlineAsmBB (ConstructionPhase phase)
void	constructIndividualBB (BBData &bbd, ConstructionPhase)
void	constructBB (BasicBlockNodeSet &inputBlocks)
void	createOperationEdges (ProgramOperationPtr po)
void	processGuard (MoveNode &moveNode)
void	processSource (MoveNode &moveNode)
void	processResultRead (MoveNode &moveNode)
void	processCall (MoveNode &mn)
void	processReturn (MoveNode &moveNode)
void	processEntryNode (MoveNode &mn)
void	processDestination (class MoveNode &moveNode, ConstructionPhase phase)
void	processRegUse (MoveNodeUse mn, const TCEString &reg)
void	updateMemUse (MoveNodeUse mnd, const TCEString &category)
void	processRegWrite (MoveNodeUse mn, const TCEString &reg)
void	updateMemWrite (MoveNodeUse mnd, const TCEString &category)
void	processTriggerPO (class MoveNode &moveNode, Operation &dop)
void	processTriggerRegistersAndOperations (MoveNode &moveNode, Operation &dop)
void	processTriggerMemoryAndFUStates (MoveNode &moveNode, Operation &dop)
void	createTriggerDependencies (class MoveNode &moveNode, class Operation &dop)
void	createSideEffectEdges (MoveNodeUseSet &prevMoves, const MoveNode &mn, Operation &dop)
void	processMemWrite (MoveNodeUse mnd)
void	processMemUse (MoveNodeUse mnd)
void	processOperand (class MoveNode &moveNode, Operation &dop)
MemoryAliasAnalyzer::AliasingResult	analyzeMemoryAlias (const ProgramOperation &pop1, const ProgramOperation &pop2, MoveNodeUse::BBRelation bbInfo)
bool	isAddressTraceable (const ProgramOperation &pop)
TCEString	memoryCategory (const MoveNodeUse &mnd)
bool	checkAndCreateMemDep (MoveNodeUse prev, MoveNodeUse mnd, DataDependenceEdge::DependenceType depType)
void	checkAndCreateMemAntideps (MoveNodeUse &mnd, std::set< MoveNodeUse > &prevNodes, DataDependenceEdge::DependenceType depType, bool traceable)
bool	hasEarlierMemWriteToSameAddressWithSameGuard (MoveNodeUse &mnd, std::set< MoveNodeUse > &defines)
std::set< MoveNodeUse >	earlierWritesWithSameGuard (MoveNodeUse &mnd, std::set< MoveNodeUse > &defines)
bool	hasEarlierWriteWithSameGuard (MoveNodeUse &mnd, std::set< MoveNodeUse > &defines)
void	createRegisterAntideps (const TCEString &reg, MoveNodeUse &mnd, MoveNodeUseSet &predecessorNodes, DataDependenceEdge::DependenceType depType, bool guardedKillFound)
void	changeState (BBData &bbd, BBState newState, bool priorize=false)
bool	isAlwaysDifferentFU (const MoveNode *srcMN, const MoveNode *dstMN)
void	findStaticRegisters (TTAProgram::CodeSnippet &cs, std::map< int, TCEString > &registers)
	find special register data from old frontend code
void	findStaticRegisters (ControlFlowGraph &cfg, std::map< int, TCEString > &registers)
void	findStaticRegisters (TTAProgram::Instruction &ins, std::map< int, TCEString > &registers)
void	findStaticRegisters (const UniversalMachine &um, std::map< int, TCEString > &registers)
void	appendMoveNodeUse (const LiveRangeData::MoveNodeUseSet &src, LiveRangeData::MoveNodeUseSet &dst, bool setLoopProperty)
Protected Attributes inherited from DataDependenceGraphBuilder
std::set< TCEString >	allParamRegs_
BBDataList	blocksByState_ [BB_STATES]
BBDataMap	bbData_
BasicBlockNode *	currentBB_
BBData *	currentData_
DataDependenceGraph *	currentDDG_
AliasAnalyzerVector	aliasAnalyzers_
SpecialRegisters	specialRegisters_
	contains stack pointer, RV and parameter registers.
InterPassData *	interPassData_
ControlFlowGraph *	cfg_
bool	rvIsParamReg_
const TTAMachine::Machine *	mach_
Static Protected Attributes inherited from DataDependenceGraphBuilder
static const TCEString	RA_NAME = "RA"

Detailed Description

LLVMTCEDataDependenceGraphBuilder class is repsonsible for building data dependence graphs with assistance from LLVM internal representation data.

Currently used to produce DDGs from the prebypassed sequential code input from the TTA-like LLVM backend.

Definition at line 49 of file LLVMTCEDataDependenceGraphBuilder.hh.

Constructor & Destructor Documentation

LLVMTCEDataDependenceGraphBuilder()

LLVMTCEDataDependenceGraphBuilder::LLVMTCEDataDependenceGraphBuilder ( InterPassData &  ipd )

inline

Definition at line 52 of file LLVMTCEDataDependenceGraphBuilder.hh.

                                                          : 
        DataDependenceGraphBuilder(ipd) {}

~LLVMTCEDataDependenceGraphBuilder()

virtual LLVMTCEDataDependenceGraphBuilder::~LLVMTCEDataDependenceGraphBuilder ( )

inlinevirtual

Definition at line 54 of file LLVMTCEDataDependenceGraphBuilder.hh.

{}

Member Function Documentation

buildFromBB()

DataDependenceGraph * LLVMTCEDataDependenceGraphBuilder::buildFromBB ( TTAProgram::BasicBlock &  bb, const UniversalMachine *  um = NULL  )

virtual

Definition at line 54 of file LLVMTCEDataDependenceGraphBuilder.cc.

                                                       {
    currentDDG_ = new DataDependenceGraph(allParamRegs_);
    buildLocalDDG(bb);
    return currentDDG_;
}

References DataDependenceGraphBuilder::allParamRegs_, buildLocalDDG(), and DataDependenceGraphBuilder::currentDDG_.

Here is the call graph for this function:

buildFromCFG()

DataDependenceGraph * LLVMTCEDataDependenceGraphBuilder::buildFromCFG ( ControlFlowGraph &  cGraph, const UniversalMachine *  um = NULL  )

virtual

Definition at line 38 of file LLVMTCEDataDependenceGraphBuilder.cc.

                                                       {
 
    currentDDG_ = new DataDependenceGraph(allParamRegs_);
    for (int bbi = 0; bbi < cGraph.nodeCount(); ++bbi) {
        BasicBlockNode& bbnode = cGraph.node(bbi);
        buildLocalDDG(bbnode.basicBlock());
    }
    /* TODO: 
       buildGlobalEdges(cGraph);
    */
    currentDDG_->writeToDotFile("ddg.dot");
    return currentDDG_;
}

References DataDependenceGraphBuilder::allParamRegs_, BasicBlockNode::basicBlock(), buildLocalDDG(), DataDependenceGraphBuilder::currentDDG_, BoostGraph< GraphNode, GraphEdge >::node(), BoostGraph< GraphNode, GraphEdge >::nodeCount(), and GraphBase< GraphNode, GraphEdge >::writeToDotFile().

Here is the call graph for this function:

buildLocalDDG()

void LLVMTCEDataDependenceGraphBuilder::buildLocalDDG ( TTAProgram::BasicBlock &  bb )

private

Definition at line 62 of file LLVMTCEDataDependenceGraphBuilder.cc.

                                                                         {
    MoveNodeGroupBuilder mngb;
    MoveNodeGroupBuilder::MoveNodeGroupList* mngs =
        mngb.build(bb);
 
    /*
      For starters, ensure the original order by chaining the
      MNs with UNKNOWN edges and add operation edges also.
 
      This should trigger the problems with RM so those can be
      worked on simultaneously.
     */
    MoveNode* lastMN = NULL;
    for (MoveNodeGroupBuilder::MoveNodeGroupList::const_iterator i =
             mngs->begin(); i != mngs->end(); ++i) {
        MoveNodeGroup& mng = **i;
//        PRINT_VAR(mng.toString());
        if (mng.isOperation()) {
            currentDDG_->addProgramOperation(mng.programOperationPtr());
        }
        MoveNode* newLastMN = &mng.node(0);
        for (int mni = 0; mni < mng.nodeCount(); ++mni) {
            MoveNode& mn = mng.node(mni);
            currentDDG_->addNode(mn);
            if (lastMN != NULL) {
                DataDependenceEdge* edge =
                    new DataDependenceEdge(
                        DataDependenceEdge::EDGE_REGISTER, 
                        DataDependenceEdge::DEP_UNKNOWN);             
                currentDDG_->connectNodes(*lastMN, mn, *edge);
            }
            if (mn.move().source().isFUPort())
                newLastMN = &mn;
        }
        lastMN = newLastMN;
    }
 
    for (MoveNodeGroupBuilder::MoveNodeGroupList::const_iterator i =
             mngs->begin(); i != mngs->end(); ++i) {
        MoveNodeGroup& mng = **i;
        if (mng.isOperation()) {
            createOperationEdges(mng.programOperationPtr());
        }
    }   
}

References DataDependenceGraph::addNode(), DataDependenceGraph::addProgramOperation(), MoveNodeGroupBuilder::build(), BoostGraph< GraphNode, GraphEdge >::connectNodes(), DataDependenceGraphBuilder::createOperationEdges(), DataDependenceGraphBuilder::currentDDG_, DataDependenceEdge::DEP_UNKNOWN, DataDependenceEdge::EDGE_REGISTER, TTAProgram::Terminal::isFUPort(), MoveNodeGroup::isOperation(), MoveNode::move(), MoveNodeGroup::node(), MoveNodeGroup::nodeCount(), MoveNodeGroup::programOperationPtr(), and TTAProgram::Move::source().

Referenced by buildFromBB(), and buildFromCFG().

Here is the call graph for this function:

---

The documentation for this class was generated from the following files:

• LLVMTCEDataDependenceGraphBuilder.hh
• LLVMTCEDataDependenceGraphBuilder.cc