#include <DataDependenceGraphBuilder.hh>

Inheritance diagram for DataDependenceGraphBuilder:

Collaboration diagram for DataDependenceGraphBuilder:

Classes
struct	BBData

Public Member Functions
	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)

Protected Types
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
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
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
static const TCEString	RA_NAME = "RA"

Detailed Description

DataDependenceGraphBuilder class is responsible for building data dependence graphs.

Definition at line 70 of file DataDependenceGraphBuilder.hh.

Member Typedef Documentation

◆ AliasAnalyzerVector

typedef std::vector<MemoryAliasAnalyzer*> DataDependenceGraphBuilder::AliasAnalyzerVector

protected

Definition at line 112 of file DataDependenceGraphBuilder.hh.

◆ BasicBlockNodeSet

typedef ControlFlowGraph::NodeSet DataDependenceGraphBuilder::BasicBlockNodeSet

protected

Definition at line 102 of file DataDependenceGraphBuilder.hh.

◆ BBDataList

typedef std::list<BBData*> DataDependenceGraphBuilder::BBDataList

protected

Definition at line 144 of file DataDependenceGraphBuilder.hh.

◆ BBDataMap

typedef std::map<BasicBlockNode*, BBData*> DataDependenceGraphBuilder::BBDataMap

protected

Definition at line 143 of file DataDependenceGraphBuilder.hh.

◆ MNodeSet

typedef DataDependenceGraph::NodeSet DataDependenceGraphBuilder::MNodeSet

protected

Definition at line 103 of file DataDependenceGraphBuilder.hh.

◆ MoveNodeUseMap

typedef LiveRangeData::MoveNodeUseMap DataDependenceGraphBuilder::MoveNodeUseMap

protected

Definition at line 107 of file DataDependenceGraphBuilder.hh.

◆ MoveNodeUseMapSet

typedef LiveRangeData::MoveNodeUseMapSet DataDependenceGraphBuilder::MoveNodeUseMapSet

protected

Definition at line 106 of file DataDependenceGraphBuilder.hh.

◆ MoveNodeUsePair

typedef LiveRangeData::MoveNodeUsePair DataDependenceGraphBuilder::MoveNodeUsePair

protected

Definition at line 109 of file DataDependenceGraphBuilder.hh.

◆ MoveNodeUseSet

typedef LiveRangeData::MoveNodeUseSet DataDependenceGraphBuilder::MoveNodeUseSet

protected

Definition at line 105 of file DataDependenceGraphBuilder.hh.

◆ MoveNodeUseSetPair

typedef LiveRangeData::MoveNodeUseSetPair DataDependenceGraphBuilder::MoveNodeUseSetPair

protected

Definition at line 108 of file DataDependenceGraphBuilder.hh.

◆ SpecialRegisters

typedef std::map<int, TCEString> DataDependenceGraphBuilder::SpecialRegisters

protected

Definition at line 111 of file DataDependenceGraphBuilder.hh.

Member Enumeration Documentation

◆ BBState

enum DataDependenceGraphBuilder::BBState

protected

Enumerator
BB_UNREACHED
BB_QUEUED	Basic block we have not yet encountered.
BB_READY	BB which is queued to be processed.
BB_STATES	BB which is already processed and is not queued.

Definition at line 114 of file DataDependenceGraphBuilder.hh.

                 {
        BB_UNREACHED = 0, /// Basic block we have not yet encountered.
        BB_QUEUED, /// BB which is queued to be processed
        BB_READY, ///BB which is already processed and is not queued.
        BB_STATES};

◆ ConstructionPhase

enum DataDependenceGraphBuilder::ConstructionPhase

protected

Enumerator
REGISTERS_AND_PROGRAM_OPERATIONS
MEMORY_AND_SIDE_EFFECTS

Definition at line 120 of file DataDependenceGraphBuilder.hh.

                           {
        REGISTERS_AND_PROGRAM_OPERATIONS = 0,
        MEMORY_AND_SIDE_EFFECTS};

Constructor & Destructor Documentation

◆ DataDependenceGraphBuilder() [1/2]

POP_COMPILER_DIAGS DataDependenceGraphBuilder::DataDependenceGraphBuilder ( )

Constructor of Data Dependence graph builder.

This constructor does not take special registers from interpass data, so it must analyze them from the code annotations. Used with old frontend.

constant alias AA check aa between global variables.

Definition at line 118 of file DataDependenceGraphBuilder.cc.

                                                       :
    interPassData_(NULL), cfg_(NULL), rvIsParamReg_(false) {
 
    /// constant alias AA check aa between global variables.
    addAliasAnalyzer(new ConstantAliasAnalyzer);
    
#ifdef USE_FALSE_AA
    /// defining USE_FALSE_AA results in faster but
    /// broken code. just for testing theoretical benefits.
    addAliasAnalyzer(new FalseAliasAnalyzer);
#endif
    addAliasAnalyzer(new PRegionAliasAnalyzer);
 
    LLVMTCECmdLineOptions* llvmOptions =
        dynamic_cast<LLVMTCECmdLineOptions*>(
                Application::cmdLineOptions());    
    if (llvmOptions != NULL && llvmOptions->disableLLVMAA() == false) {
        addAliasAnalyzer(new LLVMAliasAnalyzer);
    }
}

References addAliasAnalyzer(), Application::cmdLineOptions(), and LLVMTCECmdLineOptions::disableLLVMAA().

Here is the call graph for this function:

◆ DataDependenceGraphBuilder() [2/2]

DataDependenceGraphBuilder::DataDependenceGraphBuilder ( InterPassData & ipd )

Constructor of Data Dependence graph builder.

This constructor takes special registers from interpass data.

Definition at line 145 of file DataDependenceGraphBuilder.cc.

                                                                         :
    // TODO: when param reg thing works, rvIsParamReg becomes true here
    interPassData_(&ipd), cfg_(NULL), rvIsParamReg_(true) {
 
    // Need to store data about special registers which have semantics
    // between function calls and exits. These are stack pointer,
    // return value register and the secondary "hi bits"
    // return value register.
 
    static const TCEString SP_DATUM = "STACK_POINTER";
    static const TCEString FP_DATUM = "FRAME_POINTER";
    static const TCEString RV_DATUM = "RV_REGISTER";
    // high part of 64-bit return values.
    static const TCEString RV_HIGH_DATUM = "RV_HIGH_REGISTER";
 
    static const TCEString IPARAM_DATUM_PREFIX = "IPARAM";
    static const TCEString VECTOR_RV_PREFIX="VRV_REGISTER";
 
    SchedulerCmdLineOptions* options =
        dynamic_cast<SchedulerCmdLineOptions*>(
                Application::cmdLineOptions());
 
    if (ipd.hasDatum(SP_DATUM)) {
        RegDatum& sp = dynamic_cast<RegDatum&>(ipd.datum(SP_DATUM));
        TCEString spName =  sp.first + '.' + Conversion::toString(sp.second);
        specialRegisters_[REG_SP] = spName;
 
        // create stack alias analyzer if enabled.
        if ((options != NULL && options->enableStackAA())) {
            addAliasAnalyzer(new StackAliasAnalyzer(spName));
        }
 
        if (options != NULL && options->enableOffsetAA()) {
            addAliasAnalyzer(new OffsetAliasAnalyzer(spName));
        }
 
        addAliasAnalyzer(new GlobalVsStackAA(spName));
 
    } else {
        if (Application::verboseLevel() > 
            Application::VERBOSE_LEVEL_DEFAULT) {
            Application::logStream() 
                << "Warning: Stack pointer datum not found "
                << "in interpassdata given to ddg builder. "
                << "May generate invalid code if stack used."
                << std::endl;
        }
    }
 
    if (ipd.hasDatum(RV_DATUM)) {
        RegDatum& rv = dynamic_cast<RegDatum&>(ipd.datum(RV_DATUM));
        TCEString reg = rv.first + '.' + Conversion::toString(rv.second);
        specialRegisters_[REG_RV] = reg;
        if (rvIsParamReg_) {
            allParamRegs_.insert(reg);
        }
 
    } else {
        if (Application::verboseLevel() > 
            Application::VERBOSE_LEVEL_DEFAULT) {
            Application::logStream() 
                << "Warning: Return value register datum not found "
                << "in interpassdata given to ddg builder. "
                << "May generate invalid code if return values used."
                << std::endl;
        }
    }
 
    for(int i = 2;;i++) {
        TCEString datum = IPARAM_DATUM_PREFIX; datum << i;
        if (ipd.hasDatum(datum)) {
            RegDatum& p = dynamic_cast<RegDatum&>(ipd.datum(datum));
            TCEString reg = p.first + '.' + Conversion::toString(p.second);
            specialRegisters_[REG_IPARAM+i-1] = reg;
        } else {
            break;
        }
    }
 
    for (int i = 0;;i++) {
        TCEString datum = VECTOR_RV_PREFIX; datum << i;
        if (ipd.hasDatum(datum)) {
            RegDatum& p = dynamic_cast<RegDatum&>(ipd.datum(datum));
            TCEString reg = p.first + '.' + Conversion::toString(p.second);
            specialRegisters_[REG_VRV-i] = reg;
        } else {
            break;
        }
 
    }
 
    if (ipd.hasDatum(FP_DATUM)) {
        RegDatum& fp = dynamic_cast<RegDatum&>(ipd.datum(FP_DATUM));
        TCEString reg = fp.first + '.' + Conversion::toString(fp.second);
        specialRegisters_[REG_FP] = reg;
    } else {
        if (Application::verboseLevel() >
            Application::VERBOSE_LEVEL_DEFAULT) {
            Application::logStream()
                << "Warning: Frame Pointer Register datum not found "
                << "in interpassdata given to ddg builder. "
                << "May generate invalid code."
                << std::endl;
        }
    }
 
    if (ipd.hasDatum(RV_HIGH_DATUM)) {
        RegDatum& rvh = dynamic_cast<RegDatum&>(ipd.datum(RV_HIGH_DATUM));
        specialRegisters_[REG_RV_HIGH] =
            rvh.first + '.' + Conversion::toString(rvh.second);
    }
 
    // constant alias AA check aa between global variables.
    addAliasAnalyzer(new ConstantAliasAnalyzer);
 
    LLVMTCECmdLineOptions* llvmOptions =
        dynamic_cast<LLVMTCECmdLineOptions*>(
                Application::cmdLineOptions());    
    if (llvmOptions != NULL && llvmOptions->disableLLVMAA() == false) {
        addAliasAnalyzer(new LLVMAliasAnalyzer);
    }
    addAliasAnalyzer(new PRegionAliasAnalyzer);
 
#ifdef USE_FALSE_AA
    /// defining USE_FALSE_AA results in faster but
    /// broken code. just for testing theoretical benefits.
    addAliasAnalyzer(new FalseAliasAnalyzer);
#else
    if ((options != NULL && options->noaliasFunctions() &&
         !options->noaliasFunctions()->empty())) {
        addAliasAnalyzer(new FalseAliasAnalyzer(options->noaliasFunctions()));
    }
#endif
}

References addAliasAnalyzer(), allParamRegs_, Application::cmdLineOptions(), InterPassData::datum(), LLVMTCECmdLineOptions::disableLLVMAA(), InterPassData::hasDatum(), Application::logStream(), options, REG_FP, REG_IPARAM, REG_RV, REG_RV_HIGH, REG_SP, REG_VRV, rvIsParamReg_, specialRegisters_, Conversion::toString(), Application::VERBOSE_LEVEL_DEFAULT, and Application::verboseLevel().

Here is the call graph for this function:

◆ ~DataDependenceGraphBuilder()

DataDependenceGraphBuilder::~DataDependenceGraphBuilder ( )

virtual

Destructor of DataDependenceGraphBuilder

Definition at line 283 of file DataDependenceGraphBuilder.cc.

                                                        {
    SequenceTools::deleteAllItems(aliasAnalyzers_);
}

References aliasAnalyzers_, and SequenceTools::deleteAllItems().

Here is the call graph for this function:

Member Function Documentation

◆ addAliasAnalyzer()

void DataDependenceGraphBuilder::addAliasAnalyzer ( MemoryAliasAnalyzer * analyzer )

Adds a memory alias analyzer to the DDG builder.

Parameters

analyzer object which will analyze memory accesses.

Definition at line 293 of file DataDependenceGraphBuilder.cc.

                                                                          {
    aliasAnalyzers_.push_back(analyzer);
}

References aliasAnalyzers_.

Referenced by DataDependenceGraphBuilder(), and DataDependenceGraphBuilder().

◆ analyzeMemoryAlias()

MemoryAliasAnalyzer::AliasingResult DataDependenceGraphBuilder::analyzeMemoryAlias	(	const ProgramOperation &	pop1,
		const ProgramOperation &	pop2,
		MoveNodeUse::BBRelation	bbInfo
	)

protected

Gets the address-writing move of a move which is a trigger or operand to a memory operation.

If none found, return null

Parameters

mn	moveNode whose address write move is being searched.

Returns: MoveNode which writes address to a mem operation or NULL.

MoveNode* DataDependenceGraphBuilder::addressMove(const MoveNode& mn) { if (mn.isDestinationOperation()) { return addressOperandMove(mn.destinationOperation()); } return NULL; } Delegates the call to all registered memory address alias analyzers.

Returns the first non-unknown result. If no alias analyzer can analyze these, returns ALIAS_UNKNOWN

Returns: Whether the memory accesses in the given moves alias.

Definition at line 1951 of file DataDependenceGraphBuilder.cc.

                                  {
 
    for (unsigned int i = 0; i < aliasAnalyzers_.size(); i++) {
        MemoryAliasAnalyzer* analyzer = aliasAnalyzers_[i];
        MemoryAliasAnalyzer::AliasingResult res =
            analyzer->analyze(*currentDDG_, pop1, pop2, bbInfo);
        if (res != MemoryAliasAnalyzer::ALIAS_UNKNOWN) {
            return res;
        }
    }
    return MemoryAliasAnalyzer::ALIAS_UNKNOWN;
}

References MemoryAliasAnalyzer::ALIAS_UNKNOWN, aliasAnalyzers_, MemoryAliasAnalyzer::analyze(), and currentDDG_.

Referenced by checkAndCreateMemDep(), hasEarlierMemWriteToSameAddressWithSameGuard(), and updateMemAndFuAliveAfter().

Here is the call graph for this function:

◆ appendMoveNodeUse()

void DataDependenceGraphBuilder::appendMoveNodeUse	(	const LiveRangeData::MoveNodeUseSet &	src,
		LiveRangeData::MoveNodeUseSet &	dst,
		bool	setLoopProperty
	)

protected

◆ appendUseMapSets()

bool DataDependenceGraphBuilder::appendUseMapSets	(	const MoveNodeUseMapSet &	srcMap,
		MoveNodeUseMapSet &	dstMap,
		bool	addLoopProperty
	)

protected

◆ build() [1/2]

DataDependenceGraph * DataDependenceGraphBuilder::build	(	ControlFlowGraph &	cfg,
		DataDependenceGraph::AntidependenceLevel	antidependenceLevel,
		const TTAMachine::Machine &	mach,
		const UniversalMachine *	um = `NULL`,
		bool	createMemAndFUDeps = `true`,
		bool	createDeathInformation = `true`,
		llvm::AliasAnalysis *	AA = `NULL`
	)

virtual

Builds a DDG from a CFG.

Parameters

cfg	Control flow graph where the ddg is built from.
antidependenceLevel	level of register antidependencies to create.
um	universalmachine used for the code if registers unallocated. if null, assumed that registers allready allocated.
createMemAndFUDeps	whether to create also memory and fu state(side effect) dependencies or only register deps.
createDeathInformation	whether to search the last usage of all liveranges. This is needed for things like register renamer and threading.

Returns: pointer to the ddg which is created.

Definition at line 2120 of file DataDependenceGraphBuilder.cc.

                           {
 
    mach_ = &mach;
    if (AA) {
        for (unsigned int i = 0; i < aliasAnalyzers_.size(); i++) {
            LLVMAliasAnalyzer* llvmaa = 
            dynamic_cast<LLVMAliasAnalyzer*>(aliasAnalyzers_[i]);
            if (llvmaa != NULL) {
                llvmaa->setLLVMAA(AA);
            }
        }
    }
 
    cfg_ = &cfg;
 
    // @TODO: when CFG subgraphs are in use, 2nd param not always true
    DataDependenceGraph* ddg = new DataDependenceGraph(
        allParamRegs_, cfg.name(), antidependenceLevel, NULL, true, 
        false);
    try {
        // this is just for old frontend code.
        if (um != NULL) {
            findStaticRegisters(*um, specialRegisters_);
        } else {
            findStaticRegisters(cfg, specialRegisters_);
        }
 
        currentDDG_ = ddg;
 
        // do the first phase (register dependencies and operation edges)
        createRegisterDeps();
 
        // then do the second phase - mem and fu deps.
        if (createMemAndFUDeps) {
            createMemAndFUstateDeps();
        }
 
        // search when registers are used for last time.
        // this live range information is used by register renamer and
        // threading.
        if (createDeathInformation) {
            searchRegisterDeaths();
        }
 
        // clear bookkeeping which is not needed anymore.
        clearUnneededBookkeeping();
    } catch (const Exception& e) {
        Application::logStream()
            << e.fileName() << ": " << e.lineNum() << ": " << e.errorMessageStack()
            << std::endl;
        delete ddg;
        throw;
    } catch (...) {
        delete ddg;
        throw;
    }
    ddg->setMachine(mach);
    return ddg;
}

References aliasAnalyzers_, allParamRegs_, cfg_, clearUnneededBookkeeping(), createMemAndFUstateDeps(), createRegisterDeps(), currentDDG_, Exception::errorMessageStack(), Exception::fileName(), findStaticRegisters(), Exception::lineNum(), Application::logStream(), mach_, BoostGraph< GraphNode, GraphEdge >::name(), searchRegisterDeaths(), LLVMAliasAnalyzer::setLLVMAA(), DataDependenceGraph::setMachine(), and specialRegisters_.

Referenced by BUMoveNodeSelector::BUMoveNodeSelector(), llvm::LLVMTCEIRBuilder::compileOptimized(), BasicBlockPass::createDDGFromBB(), BBSchedulerController::createDDGFromBB(), CriticalPathBBMoveNodeSelector::CriticalPathBBMoveNodeSelector(), PreOptimizer::handleControlFlowGraph(), BBSchedulerController::handleProcedure(), and ProgramGraph::ProgramGraph().

Here is the call graph for this function:

◆ build() [2/2]

DataDependenceGraph * DataDependenceGraphBuilder::build	(	TTAProgram::BasicBlock &	bb,
		DataDependenceGraph::AntidependenceLevel	registerAntidependenceLevel,
		const TTAMachine::Machine &	mach,
		const TCEString &	ddgName = `"small bb"`,
		const UniversalMachine *	um = `NULL`,
		bool	createMemAndFUDeps = `true`,
		llvm::AliasAnalysis *	AA = `NULL`
	)

virtual

Creates new Data Dependence Graph for the given basic block.

Client has to delete the graph when it is not anymore used.

Parameters

bb	BasicBlockNode whose data dependence graph to build.
registerAntidependenceLevel	which reg antidependencies to create
createMemAndFUDeps	whether to create also memory and fu state(side effect) dependencies or only register deps.

Returns: new DataDependence Graph.

Definition at line 456 of file DataDependenceGraphBuilder.cc.

                           {
 
    mach_ = &mach;
    if (AA) {
        for (unsigned int i = 0; i < aliasAnalyzers_.size(); i++) {
            LLVMAliasAnalyzer* llvmaa = 
                dynamic_cast<LLVMAliasAnalyzer*>(aliasAnalyzers_[i]);
            if (llvmaa != NULL) {
                llvmaa->setLLVMAA(AA);
            }
        }
    }
    if (bb.liveRangeData_ == NULL) {
        bb.liveRangeData_ = new LiveRangeData;
    }
 
    currentBB_ = new BasicBlockNode(bb);
    currentDDG_ = new DataDependenceGraph(
        allParamRegs_, ddgName, registerAntidependenceLevel, currentBB_,
        false,true);
    // GRR, start and end addresses are lost..
 
    currentData_ = new BBData(*currentBB_);
 
    if (um != NULL) {
        findStaticRegisters(*um, specialRegisters_);
    } else {
        findStaticRegisters(bb,specialRegisters_);
    }
    try {
        // first phase. registers , ops and PO's.
        constructIndividualBB(
            REGISTERS_AND_PROGRAM_OPERATIONS);
        if (createMemAndFUDeps) {
            //second phase. mem and fu state deps
            constructIndividualBB(
                MEMORY_AND_SIDE_EFFECTS);
        }
    } catch (Exception&) {
        delete currentDDG_; currentDDG_ = NULL;
        delete currentData_; currentData_ = NULL;
        delete currentBB_; currentBB_ = NULL;
        throw;
    }
 
    clearUnneededBookkeeping(bb, false);
 
    delete currentData_;
    currentData_ = NULL;
    currentDDG_->setMachine(mach);
    return currentDDG_;
}

References aliasAnalyzers_, allParamRegs_, clearUnneededBookkeeping(), constructIndividualBB(), currentBB_, currentData_, currentDDG_, findStaticRegisters(), TTAProgram::BasicBlock::liveRangeData_, mach_, MEMORY_AND_SIDE_EFFECTS, REGISTERS_AND_PROGRAM_OPERATIONS, LLVMAliasAnalyzer::setLLVMAA(), DataDependenceGraph::setMachine(), and specialRegisters_.

Here is the call graph for this function:

◆ changeState()

void DataDependenceGraphBuilder::changeState	(	BBData &	bbd,
		BBState	newState,
		bool	priorize = `false`
	)

protected

Changes state of a basic block in processing. Move BBData into a diffefent list and changes the state data in BBData.

Parameters

bbd	BBData of basic block whose state is being changed
newState	the new state of the basic block.

Definition at line 2217 of file DataDependenceGraphBuilder.cc.

                                                  {
 
    BBState oldState = bbd.state_;
    if (newState != oldState) {
        ContainerTools::removeValueIfExists(blocksByState_[oldState], &bbd);
        bbd.state_ = newState;
        if (priorize) {
            blocksByState_[newState].push_front(&bbd);
        } else {
            blocksByState_[newState].push_back(&bbd);
        }
    }
}

References blocksByState_, ContainerTools::removeValueIfExists(), and DataDependenceGraphBuilder::BBData::state_.

Referenced by createMemAndFUstateDeps(), createRegisterDeps(), iterateBBs(), iterateRegisterDeaths(), queueFirstBB(), searchRegisterDeaths(), setSucceedingPredepsForBB(), and updatePreceedingRegistersUsedAfter().

Here is the call graph for this function:

◆ checkAndCreateMemAntideps()

void DataDependenceGraphBuilder::checkAndCreateMemAntideps	(	MoveNodeUse &	mnd,
		std::set< MoveNodeUse > &	prevNodes,
		DataDependenceEdge::DependenceType	depType,
		bool	traceable
	)

protected

Creates memory dependencies from set of nodes to given nodes.

Does not create if gaurds of aliasing dictate edge not needed. If both guard and aliasing indicate fully transitive case for some prev nodes, then remove these previous nodes from the bookkeeping.

Definition at line 1718 of file DataDependenceGraphBuilder.cc.

                    {
    // create WaW to another in own bb
    for (MoveNodeUseSet::iterator iter =
             prevNodes.begin(); iter != prevNodes.end();) {
        if ((checkAndCreateMemDep(*iter, mnd, depType) || !traceable) &&
            (mnd.mn()->move().isUnconditional() ||
             currentDDG_->sameGuards(*(iter->mn()), *(mnd.mn())))) {
            // remove current element and update iterator to next.
            prevNodes.erase(iter++);
        } else { // just take next from the set
            iter++;
        }
    }
}

References checkAndCreateMemDep(), currentDDG_, TTAProgram::Move::isUnconditional(), MoveNodeUse::mn(), MoveNode::move(), and DataDependenceGraph::sameGuards().

Referenced by processMemWrite().

Here is the call graph for this function:

◆ checkAndCreateMemDep()

bool DataDependenceGraphBuilder::checkAndCreateMemDep	(	MoveNodeUse	prev,
		MoveNodeUse	mnd,
		DataDependenceEdge::DependenceType	depType
	)

protected

Compares a memory op against one previous memory ops and creates dependence if may alias.

Parameters

prev	Previous Memory write movenode
mn	Current memory write movenode
depType	dependence type which to create.

Returns: true if true alias.

Definition at line 1841 of file DataDependenceGraphBuilder.cc.

                                              {
 
    // cannot be dep if opposite guards.
    if (currentDDG_->exclusingGuards(*(prev.mn()), *(mnd.mn()))) {
        return false;
    }
 
    MemoryAliasAnalyzer::AliasingResult aliasResult =
        MemoryAliasAnalyzer::ALIAS_UNKNOWN;
 
    // only for true stores and loads; we cannot analyze aliasing
    // of pseudo dependencies caused by call/return.
    if (!prev.pseudo() && !mnd.pseudo()) {
        ProgramOperation& currPop = mnd.mn()->destinationOperation();
        ProgramOperation& prevPop = prev.mn()->destinationOperation();
 
        const llvm::MachineInstr* instr1 = currPop.machineInstr();
        const llvm::MachineInstr* instr2 = prevPop.machineInstr();
 
        // The LLVM MachineInstructions are not connected to
        // all memory operands, at least not to those in inline
        // assembly blocks (from custom operation calls).
        if (instr1 != NULL && instr2 != NULL) {            
            llvm::MachineInstr::mmo_iterator begin1 =
                instr1->memoperands_begin();
            // Machine instruction could in theory have several memory operands.
            // In practice it is usually just one.
            while (begin1 != instr1->memoperands_end()) {
                llvm::MachineInstr::mmo_iterator begin2 =
                    instr2->memoperands_begin();
 
                while (begin2 != instr2->memoperands_end()) {
                    // Force program ordering between volatile mem accesses.
                    if ((*begin1)->isVolatile() && (*begin2)->isVolatile()) {
#if 0
                        Application::logStream() << "MemDep >> volatile \n";
                        PRINT_VAR(currPop.toString());
                        PRINT_VAR(prevPop.toString());
                        (*begin1)->getValue()->dump();
                        (*begin2)->getValue()->dump();
#endif
                        aliasResult = MemoryAliasAnalyzer::ALIAS_PARTIAL;
                    }
                    begin2++;
                }
                begin1++;
            }
        }
        if (aliasResult == MemoryAliasAnalyzer::ALIAS_UNKNOWN)
            aliasResult = analyzeMemoryAlias(prevPop, currPop, prev.bbRelation());
    }
 
    if (aliasResult != MemoryAliasAnalyzer::ALIAS_FALSE) {
        // if not alias false , have to create mem edge.
        bool trueAlias = (aliasResult == MemoryAliasAnalyzer::ALIAS_TRUE);
        ProgramOperation& prevPo = prev.mn()->destinationOperation();
        for (int i = 0; i < prevPo.inputMoveCount(); i++) {
            if (prev.loop() || &prevPo.inputMove(i) != mnd.mn()) {
                // if operations are always assigned to differnt FU,
                // then skip creating memroy dependency edge
                if (isAlwaysDifferentFU(prev.mn(), mnd.mn())) {
                    continue;
                }
                DataDependenceEdge* dde2 =
                    new DataDependenceEdge(
                        DataDependenceEdge::EDGE_MEMORY, depType, false,
                        trueAlias, prev.pseudo(), mnd.pseudo(),
                        static_cast<int>(prev.loop()));
                currentDDG_->connectOrDeleteEdge(
                    prevPo.inputMove(i), *mnd.mn(), dde2);
            }
        }
        return trueAlias;
    }
    return false;
}

References MemoryAliasAnalyzer::ALIAS_FALSE, MemoryAliasAnalyzer::ALIAS_PARTIAL, MemoryAliasAnalyzer::ALIAS_TRUE, MemoryAliasAnalyzer::ALIAS_UNKNOWN, analyzeMemoryAlias(), MoveNodeUse::bbRelation(), DataDependenceGraph::connectOrDeleteEdge(), currentDDG_, MoveNode::destinationOperation(), DataDependenceEdge::EDGE_MEMORY, DataDependenceGraph::exclusingGuards(), ProgramOperation::inputMove(), ProgramOperation::inputMoveCount(), isAlwaysDifferentFU(), Application::logStream(), MoveNodeUse::loop(), ProgramOperation::machineInstr(), MoveNodeUse::mn(), PRINT_VAR, MoveNodeUse::pseudo(), and ProgramOperation::toString().

Referenced by checkAndCreateMemAntideps(), processMemUse(), updateMemUse(), and updateMemWrite().

Here is the call graph for this function:

◆ clearUnneededBookkeeping() [1/2]

void DataDependenceGraphBuilder::clearUnneededBookkeeping ( )

protected

Clears bookkeeping which is only needed during ddg construction.

Definition at line 2251 of file DataDependenceGraphBuilder.cc.

                                                     {
 
    for (int i = 0; i < cfg_->nodeCount();i++) {
        BasicBlockNode& bbn = cfg_->node(i);
        if (bbn.isNormalBB()) {
            BasicBlock& bb = bbn.basicBlock();
            clearUnneededBookkeeping(bb, true);
        }
    }
}

References BasicBlockNode::basicBlock(), cfg_, clearUnneededBookkeeping(), BasicBlockNode::isNormalBB(), BoostGraph< GraphNode, GraphEdge >::node(), and BoostGraph< GraphNode, GraphEdge >::nodeCount().

Referenced by build(), build(), and clearUnneededBookkeeping().

Here is the call graph for this function:

◆ clearUnneededBookkeeping() [2/2]

void DataDependenceGraphBuilder::clearUnneededBookkeeping	(	TTAProgram::BasicBlock &	bb,
		bool	interBBInformationNeeded = `true`
	)

protected

Clears bookkeeping which is only needed during ddg construction.

Parameters

BB	containing basic blocks which contain the bookkeeping.
interBBInformation	needed whether information about inter-bb- dependencies need to be left intact.

Definition at line 899 of file DataDependenceGraphBuilder.cc.

                                                   {
 
    if (!interBBInformationNeeded) {
        //used by regcopyadder.
        bb.liveRangeData_->regFirstDefines_.clear();
        bb.liveRangeData_->regLastUses_.clear();
 
        // used by both
        bb.liveRangeData_->regDefines_.clear();
 
        // these are neede for live range things
        bb.liveRangeData_->regDefReaches_.clear();
        bb.liveRangeData_->registersUsedAfter_.clear();
        bb.liveRangeData_->regFirstUses_.clear();
    }
    bb.liveRangeData_->regUseReaches_.clear();
    bb.liveRangeData_->regLastKills_.clear();
 
    bb.liveRangeData_->regDefAfter_.clear();
    bb.liveRangeData_->regUseAfter_.clear();
 
    bb.liveRangeData_->memDefines_.clear();
    bb.liveRangeData_->memLastUses_.clear();
 
    bb.liveRangeData_->memFirstUses_.clear();
    bb.liveRangeData_->memFirstDefines_.clear();
 
    bb.liveRangeData_->memDefReaches_.clear();
    bb.liveRangeData_->memUseReaches_.clear();
 
    bb.liveRangeData_->fuDepReaches_.clear();
    bb.liveRangeData_->fuDeps_.clear();
    bb.liveRangeData_->fuDepAfter_.clear();
 
    bb.liveRangeData_->registersUsedInOrAfter_.clear();
}

◆ constructBB()

void DataDependenceGraphBuilder::constructBB ( BasicBlockNodeSet & inputBlocks )

protected

◆ constructIndividualBB() [1/2]

void DataDependenceGraphBuilder::constructIndividualBB	(	BBData &	bbd,
		ConstructionPhase	phase
	)

protected

Constructs a Data Dependence Graph for a single basic block.

Goes thru all moves in the basic block and analyzes their dependencies, creates their ProgramOperations, MoveNodes and Edges, and adds the nodes and edges to the graph. Also used inside implementation of multi-BB-DDG-code. BB being analyzed has to be already set in member variable currentBB_, and the graph created and set into member variable currentBB_.

Parameters

bbd	basic block to constructs.
phase	whether to handle register& operation deps or memory and side-effect dependencies.

Definition at line 531 of file DataDependenceGraphBuilder.cc.

                                          {
 
    currentData_ = &bbd;
    currentBB_ = bbd.bblock_;
 
    // Parallel inline asm block are already marked as scheduled
    // TODO: should BBN have isInlineAsm() method?
    if (currentBB_->isScheduled()) {
        constructIndividualFromInlineAsmBB(phase);
    } else {
        constructIndividualBB(phase);
    }
}

References DataDependenceGraphBuilder::BBData::bblock_, constructIndividualBB(), constructIndividualFromInlineAsmBB(), currentBB_, currentData_, and BasicBlockNode::isScheduled().

Here is the call graph for this function:

◆ constructIndividualBB() [2/2]

void DataDependenceGraphBuilder::constructIndividualBB ( ConstructionPhase phase )

protected

Constructs a Data Dependence Graph for a single basic block.

Goes thru all moves in the basic block and analyzes their dependencies, creates their ProgramOperations, MoveNodes and Edges, and adds the nodes and edges to the graph. Also used inside implementation of multi-BB-DDG-code. BB being analyzed has to be already set in member variable currentBB_, and the graph created and set into member variable currentBB_.

Parameters

phase whether to handle register& operation deps or memory and side-effect dependencies.

Definition at line 560 of file DataDependenceGraphBuilder.cc.

                             {
 
    for (int ia = 0; ia < currentBB_->basicBlock().instructionCount(); ia++) {
        Instruction& ins = currentBB_->basicBlock().instructionAtIndex(ia);
 
        for (int i = 0; i < ins.moveCount(); i++) {
            auto movePtr = ins.movePtr(i);
            Move& move = *movePtr;
 
            MoveNode* moveNode = NULL;
 
            // if phase is 0, create the movenode, and handle guard.
            if (phase == REGISTERS_AND_PROGRAM_OPERATIONS) {
                /* In case using the LLVMTCEIRBuilder, the POs have been built already
                   and set to corresponding TerminalFUPorts. Use those MoveNodes and
                   ProgramOperations instead of creating new ones here. NOTE: the
                   ownership of the MoveNodes is transferred to the DDG.
                */
                if (move.destination().isFUPort() && 
                    dynamic_cast<TerminalFUPort&>(move.destination()).
                    hasProgramOperation()) {
                    ProgramOperationPtr po = 
                        dynamic_cast<TerminalFUPort&>(move.destination()).
                        programOperation();
                    if (po->hasMoveNodeForMove(move)) {
                        moveNode = &po->moveNode(move);
                    } else {
                        // the po might be corrupted and point to an old POM's Moves
                        moveNode = new MoveNode(movePtr);
                    }
                } else if (move.source().isFUPort() && 
                           dynamic_cast<TerminalFUPort&>(move.source()).
                           hasProgramOperation()) {
                    ProgramOperationPtr po = 
                        dynamic_cast<TerminalFUPort&>(move.source()).
                        programOperation();
                    if (po->hasMoveNodeForMove(move)) {
                        moveNode = &po->moveNode(move);
                    } else {
                        // the po might be corrupted and point to an old POM's Moves
                        moveNode = new MoveNode(movePtr);
                    }
                } else {
                    moveNode = new MoveNode(movePtr);
                }
                currentDDG_->addNode(*moveNode, *currentBB_);
 
                if (!move.isUnconditional()) {
                    processGuard(*moveNode);
                }
 
                processSource(*moveNode);
 
            } else {
                // on phase 2, just find the already created movenode.
                moveNode = &currentDDG_->nodeOfMove(move);
            }
 
            // destinaition need to be processed in both phases 0 and 1.
            processDestination(*moveNode, phase);
        }
    }
 
    // these are needed no more.
    currentBB_->basicBlock().liveRangeData_->potentialRegKills_.clear();
 
    // Checks if we have some unready program operations at the end
    // of a basic block.
    if (currentData_->destPending_ != NULL ||
        currentData_->readPending_ != NULL) {
 
        TCEString msg = TCEString("Basic block ")
            + Conversion::toString(currentBB_->originalStartAddress())
            + TCEString(" - ")
            + Conversion::toString(currentBB_->originalEndAddress())
            + TCEString(", size : ")
            + Conversion::toString(
                currentBB_->basicBlock().instructionCount())
            + TCEString(" handled but we have unready PO at: ")
            + currentDDG_->name()
            + TCEString(", probably an operation without result move?");
 
        if (currentData_->readPending_ != NULL) {
            msg += "\n\tmissing read: " +
                TCEString(currentData_->readPending_->operation().name());
        }
 
        if (currentData_->destPending_ != NULL) {
            msg += "\n\tmissing dest: " +
                TCEString(currentData_->destPending_->operation().name());
        }
 
        if (cfg_ != NULL) {
            cfg_->writeToDotFile("constructBBbroken_cfg.dot");
        }
 
        throw IllegalProgram(__FILE__,__LINE__,__func__, msg);
    }
}

References __func__, DataDependenceGraph::addNode(), BasicBlockNode::basicBlock(), cfg_, currentBB_, currentData_, currentDDG_, TTAProgram::Move::destination(), DataDependenceGraphBuilder::BBData::destPending_, TTAProgram::CodeSnippet::instructionAtIndex(), TTAProgram::CodeSnippet::instructionCount(), TTAProgram::Terminal::isFUPort(), TTAProgram::Move::isUnconditional(), TTAProgram::BasicBlock::liveRangeData_, TTAProgram::Instruction::moveCount(), TTAProgram::Instruction::movePtr(), BoostGraph< GraphNode, GraphEdge >::name(), DataDependenceGraph::nodeOfMove(), BasicBlockNode::originalEndAddress(), BasicBlockNode::originalStartAddress(), LiveRangeData::potentialRegKills_, processDestination(), processGuard(), processSource(), DataDependenceGraphBuilder::BBData::readPending_, REGISTERS_AND_PROGRAM_OPERATIONS, TTAProgram::Move::source(), Conversion::toString(), and GraphBase< GraphNode, GraphEdge >::writeToDotFile().

Referenced by build(), constructIndividualBB(), and iterateBBs().

Here is the call graph for this function:

◆ constructIndividualFromInlineAsmBB()

void DataDependenceGraphBuilder::constructIndividualFromInlineAsmBB ( ConstructionPhase phase )

protected

Same as constructIndividualBB() but for already fully scheduled and inline asm BB.

@Note: currently, this does not really construct DDG - just creates dummy MoveNodes.

Definition at line 669 of file DataDependenceGraphBuilder.cc.

                             {
 
    if (phase != REGISTERS_AND_PROGRAM_OPERATIONS) {
        return;
    }
    auto& bb = currentBB_->basicBlock();
    assert(currentBB_->isScheduled());
    for (int ia = 0; ia < bb.instructionCount(); ia++) {
        Instruction& ins = bb.instructionAtIndex(ia);
        for (int i = 0; i < ins.moveCount(); i++) {
            MoveNode* moveNode = new MoveNode(ins.movePtr(i));
            currentDDG_->addNode(*moveNode, *currentBB_);
        }
    }
 
    // Process live range with dummy move nodes.
    assert(bb.liveRangeData_);
    LiveRangeData& liveRangeData = *bb.liveRangeData_;
    std::set<TCEString> actualRegUses;
    std::set<TCEString> actualRegDefs;
    for (int i = 0; i < bb.instructionCount(); i++) {
        auto& ins = bb.instructionAtIndex(i);
        for (int m = 0; m < ins.moveCount(); m++) {
            auto& move = ins.move(m);
 
            auto rdReg = move.source().isGPR() ? move.source().toString()
                                               : TCEString("");
            if (!rdReg.empty()) actualRegUses.insert(rdReg);
 
            if (move.isConditional()) {
                const Guard& grd = move.guard().guard();
                const RegisterGuard* grdReg =
                    dynamic_cast<const RegisterGuard*>(&grd);
                if (grdReg) {
                    TCEString regName = grdReg->registerFile()->name() + '.' +
                    Conversion::toString(grdReg->registerIndex());
                    actualRegUses.insert(regName);
                }
            }
 
            auto wrReg = move.destination().isGPR()
                ? move.destination().toString()
                : TCEString("");
            if (!wrReg.empty()) actualRegDefs.insert(wrReg);
        }
    }
 
    auto& iaRegUses = liveRangeData.inlineAsmRegUses_;
    auto effectiveRegUses = SetTools::intersection(iaRegUses, actualRegUses);
    for (auto reg : effectiveRegUses) {
        MoveNode* moveNode = new MoveNode();
        currentDDG_->addNode(*moveNode, *currentBB_);
        liveRangeData.regFirstUses_[reg].insert(*moveNode);
        currentDDG_->updateRegUse(*moveNode, reg, bb);
    }
 
    auto& iaRegDefs = liveRangeData.inlineAsmRegDefs_;
    auto effectiveRegDefs = SetTools::intersection(iaRegDefs, actualRegDefs);
    for (auto reg : effectiveRegDefs) {
        MoveNode* moveNode = new MoveNode();
        currentDDG_->addNode(*moveNode, *currentBB_);
        liveRangeData.regDefines_[reg].insert(*moveNode);
        MoveNodeUse mnd(*moveNode);
        liveRangeData.regKills_[reg] = std::make_pair(mnd, mnd);
    }
 
    for (auto& reg : liveRangeData.inlineAsmClobbers_) {
        MoveNode* moveNode = new MoveNode();
        currentDDG_->addNode(*moveNode, *currentBB_);
        liveRangeData.regDefines_[reg].insert(*moveNode);
        MoveNodeUse mnd(*moveNode);
        liveRangeData.regKills_[reg] = std::make_pair(mnd, mnd);
    }
 
    // Not needed anymore.
    liveRangeData.inlineAsmRegUses_.clear();
    liveRangeData.inlineAsmRegDefs_.clear();
    liveRangeData.inlineAsmClobbers_.clear();
}

References DataDependenceGraph::addNode(), assert, BasicBlockNode::basicBlock(), currentBB_, currentDDG_, LiveRangeData::inlineAsmClobbers_, LiveRangeData::inlineAsmRegDefs_, LiveRangeData::inlineAsmRegUses_, SetTools::intersection(), BasicBlockNode::isScheduled(), TTAProgram::Instruction::moveCount(), TTAProgram::Instruction::movePtr(), TTAMachine::Component::name(), LiveRangeData::regDefines_, LiveRangeData::regFirstUses_, TTAMachine::RegisterGuard::registerFile(), TTAMachine::RegisterGuard::registerIndex(), REGISTERS_AND_PROGRAM_OPERATIONS, LiveRangeData::regKills_, Conversion::toString(), and DataDependenceGraph::updateRegUse().

Referenced by constructIndividualBB().

Here is the call graph for this function:

◆ createMemAndFUstateDeps()

void DataDependenceGraphBuilder::createMemAndFUstateDeps ( )

protected

Does the second phase of ddg construction.

handles mem deps and fu state deps.

Definition at line 2312 of file DataDependenceGraphBuilder.cc.

                                                    {
 
    // initializes states of all BB's to unreached.
    initializeBBStates();
 
    // queues first bb for processing
    queueFirstBB();
 
    // then iterates over all basic blocks.
    iterateBBs(MEMORY_AND_SIDE_EFFECTS);
 
    // all should be constructed, but if there are unreachable BB's
    // we might want to handle those also
    while (!blocksByState_[BB_UNREACHED].empty()) {
        changeState(**blocksByState_[BB_UNREACHED].begin(), BB_QUEUED);
        iterateBBs(MEMORY_AND_SIDE_EFFECTS);
    }
    // free bb data
    AssocTools::deleteAllValues(bbData_);
}

References BB_QUEUED, BB_UNREACHED, bbData_, blocksByState_, changeState(), AssocTools::deleteAllValues(), initializeBBStates(), iterateBBs(), MEMORY_AND_SIDE_EFFECTS, and queueFirstBB().

Referenced by build().

Here is the call graph for this function:

◆ createOperationEdges()

void DataDependenceGraphBuilder::createOperationEdges ( ProgramOperationPtr po )

protected

Creates operand edges between input and output moves of a programoperation.

Parameters

po	ProgramOperation whose egdes we are creating.

Definition at line 1141 of file DataDependenceGraphBuilder.cc.

                            {
 
    const Operation& op = po->operation();
 
    // loop over all input nodes
    for (int i = 0; i < po->inputMoveCount(); i++) {
        MoveNode& inputNode = po->inputMove(i);
        // loop over all output nodes.
        for (int j = 0; j < po->outputMoveCount(); j++) {
            MoveNode& outputNode = po->outputMove(j);
 
            // and create operation edges
            // from all input nodes to all
            // output nodes.
            DataDependenceEdge* dde =
                new DataDependenceEdge(
                    DataDependenceEdge::EDGE_OPERATION,
                    DataDependenceEdge::DEP_UNKNOWN,
                    op.name());
 
            currentDDG_->connectOrDeleteEdge(
                inputNode, outputNode, dde);
        }
    }
}

References DataDependenceGraph::connectOrDeleteEdge(), currentDDG_, DataDependenceEdge::DEP_UNKNOWN, DataDependenceEdge::EDGE_OPERATION, and Operation::name().

Referenced by LLVMTCEDataDependenceGraphBuilder::buildLocalDDG(), and processResultRead().

Here is the call graph for this function:

◆ createRegisterAntideps()

void DataDependenceGraphBuilder::createRegisterAntideps	(	const TCEString &	reg,
		MoveNodeUse &	mnd,
		MoveNodeUseSet &	predecessorNodes,
		DataDependenceEdge::DependenceType	depType,
		bool	guardedKillFound
	)

protected

Creates register antidependencies from set of movenodeuses to one movenode.

Parameters

mnd	Movenode which to creat those dependencies
predecessorNodes	Nodes where to create dependencies from
depType	whether to create WAR or WAW antidependencies
guardedKillFound	if there is a write with same guard to the reg.

Definition at line 1303 of file DataDependenceGraphBuilder.cc.

                           {
 
    // create dep to another in own bb
    for (std::set<MoveNodeUse>::iterator i = predecessorNodes.begin();
         i != predecessorNodes.end();) {
        
        if (depType == DataDependenceEdge::DEP_WAW) {
            // If we do not have a guarded kill, draw edges from all defines.
            // If we have a guarded kill, only draw edges from 
            // unconditional moves, as the guarded kill overshadows the 
            // inconditional writes.
            if (guardedKillFound && i->mn()->move().isUnconditional()) {
                i++;
                continue;
            }
        } else {
            assert(depType == DataDependenceEdge::DEP_WAR);
            // skip if war to itself, ie move foo.1 -> foo.1
            if (i->mn() == mnd.mn()) {
                i++;
                continue;
            }
        }
                    
        // Do not create antideps if have excluding guards
        // But always create antidep if this writes to a reg which is
        // used as guard for the previous move.
        if (!currentDDG_->exclusingGuards(*(i->mn()), *(mnd.mn())) ||
            i->guard()) {
            
            // create dependency edge
            DataDependenceEdge* dde =
                new DataDependenceEdge(
                    mnd.ra() ? DataDependenceEdge::EDGE_RA :
                    DataDependenceEdge::EDGE_REGISTER,
                    depType, reg, i->guard(), false, 
                    i->pseudo(), mnd.pseudo(), i->loop());
            
            // and connect
            currentDDG_->connectOrDeleteEdge(*i->mn(), *mnd.mn(), dde);
            
            // if have same guards, remove the old from bookkeeping
            // this completely overshadows it
            if (currentDDG_->sameGuards(*(i->mn()), *(mnd.mn()))) {
                predecessorNodes.erase(i++);
                continue;
            }
        }
        i++;
    }
}

References assert, DataDependenceGraph::connectOrDeleteEdge(), currentDDG_, DataDependenceEdge::DEP_WAR, DataDependenceEdge::DEP_WAW, DataDependenceEdge::EDGE_RA, DataDependenceEdge::EDGE_REGISTER, DataDependenceGraph::exclusingGuards(), MoveNodeUse::mn(), MoveNodeUse::pseudo(), MoveNodeUse::ra(), and DataDependenceGraph::sameGuards().

Referenced by processRegWrite().

Here is the call graph for this function:

◆ createRegisterDeps()

void DataDependenceGraphBuilder::createRegisterDeps ( )

protected

Does the first phase of ddg construction. handles register deps.

Parameters

cfg	control flow graph containing the code.

Definition at line 2268 of file DataDependenceGraphBuilder.cc.

                                               {
 
    // initializes states of all BB's to unreached.
    initializeBBStates();
 
    // queues first bb for processing
    BasicBlockNode* firstBB = queueFirstBB();
 
    // currentBB need to be set for entry node processing
    currentBB_ = firstBB;
 
    // set entry deps. ( procedure parameter edges )
    MoveNode* entryNode = new MoveNode();
    currentDDG_->addNode(*entryNode, cfg_->entryNode());
 
    processEntryNode(*entryNode);
 
    // iterate over BB's. Loop as long as there are queued BB's.
 
    iterateBBs(REGISTERS_AND_PROGRAM_OPERATIONS);
 
    // all should be constructed, but if there are unreachable BB's
    // we handle those also
    while (!blocksByState_[BB_UNREACHED].empty()) {
        if (Application::verboseLevel() > Application::VERBOSE_LEVEL_DEFAULT) {
            Application::logStream() << "Warning: Unreachable Basic Block!"
                                     << std::endl;
            Application::logStream() << "In procedure: " << cfg_->name() <<
                std::endl;
//            cfg.writeToDotFile("unreachable_bb.dot");
        }
        changeState(**blocksByState_[BB_UNREACHED].begin(), BB_QUEUED);
        iterateBBs(REGISTERS_AND_PROGRAM_OPERATIONS);
    }
    // free bb data
    AssocTools::deleteAllValues(bbData_);
}

References DataDependenceGraph::addNode(), BB_QUEUED, BB_UNREACHED, bbData_, blocksByState_, cfg_, changeState(), currentBB_, currentDDG_, AssocTools::deleteAllValues(), ControlFlowGraph::entryNode(), initializeBBStates(), iterateBBs(), Application::logStream(), BoostGraph< GraphNode, GraphEdge >::name(), processEntryNode(), queueFirstBB(), REGISTERS_AND_PROGRAM_OPERATIONS, Application::VERBOSE_LEVEL_DEFAULT, and Application::verboseLevel().

Referenced by build().

Here is the call graph for this function:

◆ createSideEffectEdges()

void DataDependenceGraphBuilder::createSideEffectEdges	(	MoveNodeUseSet &	prevMoves,
		const MoveNode &	mn,
		Operation &	dop
	)

protected

Definition at line 1646 of file DataDependenceGraphBuilder.cc.

                                                                   {
 
    OperationPool pool;
    if (pool.sharesState(dop) || dop.hasSideEffects()) {
        for (MoveNodeUseSet::iterator i = prevMoves.begin();
             i != prevMoves.end(); i++) {
            const Operation& o = i->mn()->destinationOperation().operation();
 
            // mem writes are handled by memory deps so exclude here
            if ((&dop == &o && o.hasSideEffects()) ||
                dop.dependsOn(o) || o.dependsOn(dop)) {
                // if operations are always assigned to differnt FU,
                // skip creating dependency edge
                if (isAlwaysDifferentFU(&mn, i->mn())) continue;
 
                if (!currentDDG_->exclusingGuards(*(i->mn()), mn)) {
                    DataDependenceEdge* dde =
                        new DataDependenceEdge(
                            DataDependenceEdge::EDGE_FUSTATE,
                            DataDependenceEdge::DEP_UNKNOWN, false,false,false,
                            false, static_cast<int>(i->loop()));
                    currentDDG_->connectOrDeleteEdge(
                        *(i->mn()), mn, dde);
                }
            }
        }
    }
}

References DataDependenceGraph::connectOrDeleteEdge(), currentDDG_, DataDependenceEdge::DEP_UNKNOWN, Operation::dependsOn(), DataDependenceEdge::EDGE_FUSTATE, DataDependenceGraph::exclusingGuards(), Operation::hasSideEffects(), and isAlwaysDifferentFU().

Referenced by createTriggerDependencies(), and updateBB().

Here is the call graph for this function:

◆ createTriggerDependencies()

void DataDependenceGraphBuilder::createTriggerDependencies	(	class MoveNode &	moveNode,
		class Operation &	dop
	)

protected

Analyzes operation of a trigger write.

If memory read, calls processMemRead to manage memory read dependencies. Manages FU State dependencies between operations.

Parameters

moveNode	mnData related to a move which triggers an operation
dop	Operation being triggered

Definition at line 1596 of file DataDependenceGraphBuilder.cc.

                                        {
 
    if (dop.readsMemory()) {
        processMemUse(MoveNodeUse(moveNode));
    } //TODO: avoid drawing antidep to itself
 
    if (dop.writesMemory()) {
        processMemWrite(MoveNodeUse(moveNode));
    } 
 
    createSideEffectEdges(currentBB_->basicBlock().liveRangeData_->fuDeps_, moveNode, dop);
    createSideEffectEdges(
        currentBB_->basicBlock().liveRangeData_->fuDepReaches_, moveNode, dop);
 
    OperationPool pool;
    if (dop.hasSideEffects() || pool.sharesState(dop)) {
 
        // remove old same op from bookkeeping.
        // this should prevent exponential explosion of edge count.
        if (dop.hasSideEffects() && moveNode.move().isUnconditional()) {
            for (MoveNodeUseSet::iterator iter =
                     currentBB_->basicBlock().liveRangeData_->fuDeps_.begin();
                 iter != currentBB_->basicBlock().liveRangeData_->fuDeps_.end(); iter++) {
 
                const Operation& o = 
                    iter->mn()->destinationOperation().operation();
                if (&o == &dop) {
                    currentBB_->basicBlock().liveRangeData_->fuDeps_.erase(iter);
                    break;
                }
            }
        }
        // add the new one to bookkeeping
        currentBB_->basicBlock().liveRangeData_->fuDeps_.insert(MoveNodeUse(moveNode));
    }
}

References BasicBlockNode::basicBlock(), createSideEffectEdges(), currentBB_, LiveRangeData::fuDepReaches_, LiveRangeData::fuDeps_, Operation::hasSideEffects(), TTAProgram::Move::isUnconditional(), TTAProgram::BasicBlock::liveRangeData_, MoveNode::move(), processMemUse(), processMemWrite(), Operation::readsMemory(), and Operation::writesMemory().

Referenced by processTriggerMemoryAndFUStates().

Here is the call graph for this function:

◆ earlierWritesWithSameGuard()

std::set< MoveNodeUse > DataDependenceGraphBuilder::earlierWritesWithSameGuard	(	MoveNodeUse &	mnd,
		std::set< MoveNodeUse > &	defines
	)

protected

Definition at line 1200 of file DataDependenceGraphBuilder.cc.

                                                    {
 
    std::set<MoveNodeUse> results;
    // first just check if there is earlier write to this reg with same guard..
    for (std::set<MoveNodeUse>::iterator i = defines.begin();
         i != defines.end(); i++) {
        // if earlier write to this reg with same guard..
        if (!mnd.guard() &&
            !i->mn()->move().isUnconditional() &&
            currentDDG_->sameGuards(*(i->mn()), *(mnd.mn()))) {
            results.insert(*i);
        }
    }
    return results;
}

References currentDDG_, MoveNodeUse::guard(), MoveNodeUse::mn(), and DataDependenceGraph::sameGuards().

Referenced by processRegUse().

Here is the call graph for this function:

◆ findStaticRegisters() [1/4]

void DataDependenceGraphBuilder::findStaticRegisters	(	const UniversalMachine &	um,
		std::map< int, TCEString > &	registers
	)

protected

Initializes the static register table from register from UniversalMachine.

Needed for analysis of data dependencies of parameter registers, SP, RV etc.

Parameters

um	UniversalMachine
registers	map where to store those registers.

Definition at line 421 of file DataDependenceGraphBuilder.cc.

                                                                  {
    RegisterFile& rf = um.integerRegisterFile();
 
    for (int i = 0; i < 6; i++) {
        TerminalRegister tr(*rf.port(0), i);
        TCEString reg = DisassemblyRegister::registerName(tr); 
        registers[i] = reg;
        if (i > REG_SP) {
            allParamRegs_.insert(reg);
        }
    }
}

References allParamRegs_, UniversalMachine::integerRegisterFile(), TTAMachine::BaseRegisterFile::port(), REG_SP, and DisassemblyRegister::registerName().

Here is the call graph for this function:

◆ findStaticRegisters() [2/4]

void DataDependenceGraphBuilder::findStaticRegisters	(	ControlFlowGraph &	cfg,
		std::map< int, TCEString > &	registers
	)

protected

Tries to find annotations which tell the static registers from a program.

Used only with the old gcc frontend.

Parameters

cfg	cfg where to search the annotations.

Definition at line 324 of file DataDependenceGraphBuilder.cc.

                                      {
    for (int i = 0; i < cfg.nodeCount(); i++) {
        BasicBlockNode& bbn = cfg.node(i);
        if (bbn.isNormalBB()) {
            findStaticRegisters(bbn.basicBlock(), registers);
        }
    }
}

References BasicBlockNode::basicBlock(), findStaticRegisters(), BasicBlockNode::isNormalBB(), BoostGraph< GraphNode, GraphEdge >::node(), and BoostGraph< GraphNode, GraphEdge >::nodeCount().

Here is the call graph for this function:

◆ findStaticRegisters() [3/4]

void DataDependenceGraphBuilder::findStaticRegisters	(	TTAProgram::CodeSnippet &	cs,
		std::map< int, TCEString > &	registers
	)

protected

find special register data from old frontend code

Tries to find annotations which tell the static registers from a program.

Used only with the old gcc frontend.

Parameters

cs	codesnippet where to search the annotations.

Definition at line 306 of file DataDependenceGraphBuilder.cc.

                                      {
    for (int i = 0; i < cs.instructionCount(); i++) {
        Instruction& ins = cs.instructionAtIndex(i);
        findStaticRegisters(ins, registers);
    }
}

References findStaticRegisters(), TTAProgram::CodeSnippet::instructionAtIndex(), and TTAProgram::CodeSnippet::instructionCount().

Referenced by build(), build(), findStaticRegisters(), and findStaticRegisters().

Here is the call graph for this function:

◆ findStaticRegisters() [4/4]

void DataDependenceGraphBuilder::findStaticRegisters	(	TTAProgram::Instruction &	ins,
		std::map< int, TCEString > &	registers
	)

protected

Tries to find annotations which tell the static registers from a program.

Used only with the old gcc frontend.

Parameters

ins	instruction where to search the annotations.

Definition at line 344 of file DataDependenceGraphBuilder.cc.

                                      {
 
    try {
        for (int i = 0; i < ins.moveCount(); i++) {
            Move& move = ins.move(i);
            for (int j = 0; j < move.annotationCount(); j++) {
                ProgramAnnotation anno = move.annotation(j);
                switch (anno.id()) {
                    case ProgramAnnotation::ANN_REGISTER_RV_READ: {
                        registers[REG_RV] = DisassemblyRegister::registerName(
                            move.source());
                        break;
                    }
                    case ProgramAnnotation::ANN_REGISTER_RV_SAVE: {
                        registers[REG_RV] = DisassemblyRegister::registerName(
                            move.destination());
                        break;
                    }
                    case ProgramAnnotation::ANN_REGISTER_SP_READ: {
                        registers[REG_SP] = DisassemblyRegister::registerName(
                            move.source());
                        break;
                    }
                    case ProgramAnnotation::ANN_REGISTER_SP_SAVE: {
                        registers[REG_SP] = DisassemblyRegister::registerName(
                            move.destination());
                        break;
                    }
                    case ProgramAnnotation::ANN_REGISTER_IPARAM_READ: {
/* this fixes one unit test silent breakage but another will then happen - unit test
   tpef's seem to contain a bit broken code
                        Terminal& src = move.source();
                        if (!src.isGPR()) {
                            break;
                        }
*/
                        TCEString reg = 
                            DisassemblyRegister::registerName(move.source());
                        registers[
                            REG_IPARAM+Conversion::toInt(anno.stringValue())] =
                            reg;
                        allParamRegs_.insert(reg);
                        break;
                    }
                    case ProgramAnnotation::ANN_REGISTER_IPARAM_SAVE: {
                        TCEString reg =
                            DisassemblyRegister::registerName(move.destination());
                        registers[
                            REG_IPARAM+Conversion::toInt(anno.stringValue())] =
                            reg;
                        allParamRegs_.insert(reg);
                        break;
                    }
                    default:
                        //TODO: frame pointer, not yet implemented
                        break;
                }
            }
        }
    } catch (std::bad_cast& e) {
        throw IllegalProgram(__FILE__,__LINE__, __func__, "Illegal annotation");
    }
}

Here is the call graph for this function:

◆ hasEarlierMemWriteToSameAddressWithSameGuard()

bool DataDependenceGraphBuilder::hasEarlierMemWriteToSameAddressWithSameGuard	(	MoveNodeUse &	mnd,
		std::set< MoveNodeUse > &	defines
	)

protected

Checks if there is an earlier write to same address or with same guard.

Parameters

mnd	the current node dictating guard and mem address to check.
defines	set of earlier writes to check for the write.

Definition at line 1688 of file DataDependenceGraphBuilder.cc.

                                                    {
    // first just check if there is earlier write to this mem address
    // with same guard.
    for (std::set<MoveNodeUse>::iterator i = defines.begin();
         i != defines.end(); i++) {
        // if earlier write to this reg with same guard..
        if (currentDDG_->sameGuards(*(i->mn()), *(mnd.mn()))) {
            ProgramOperation& curPop = mnd.mn()->destinationOperation();
            ProgramOperation& prevPop = (i->mn())->destinationOperation();
//            MoveNode* currentAddress = addressMove(*mnd.mn());
//            MoveNode* prevAddress = addressMove(*(i->mn()));
            if (!isAddressTraceable(prevPop) ||
                analyzeMemoryAlias(prevPop, curPop, i->bbRelation()) ==
                MemoryAliasAnalyzer::ALIAS_TRUE) {
                return true;
            }
        }
    }
    return false;
}

References MemoryAliasAnalyzer::ALIAS_TRUE, analyzeMemoryAlias(), currentDDG_, MoveNode::destinationOperation(), isAddressTraceable(), MoveNodeUse::mn(), and DataDependenceGraph::sameGuards().

Referenced by processMemUse(), and processMemWrite().

Here is the call graph for this function:

◆ hasEarlierWriteWithSameGuard()

bool DataDependenceGraphBuilder::hasEarlierWriteWithSameGuard	(	MoveNodeUse &	mnd,
		std::set< MoveNodeUse > &	defines
	)

protected

Checks whether there is a previous alive write with same guard than given node.

The origin of the guard value is tracked from DDG, not only plain guard is done.

Parameters

mnd	MoveNode containing the guard.
defines	set of earlier writes which to check.

Definition at line 1183 of file DataDependenceGraphBuilder.cc.

                                                    {
 
    // first just check if there is earlier write to this reg with same guard..
    for (std::set<MoveNodeUse>::iterator i = defines.begin();
         i != defines.end(); i++) {
        // if earlier write to this reg with same guard..
        if (!mnd.guard() &&
            !i->mn()->move().isUnconditional() &&
            currentDDG_->sameGuards(*(i->mn()), *(mnd.mn()))) {
            return true;
        }
    }
    return false;
}

References currentDDG_, MoveNodeUse::guard(), MoveNodeUse::mn(), and DataDependenceGraph::sameGuards().

Referenced by processRegWrite().

Here is the call graph for this function:

◆ initializeBBStates()

void DataDependenceGraphBuilder::initializeBBStates ( )

protected

Initializes states of all BB's to unreached

Definition at line 2191 of file DataDependenceGraphBuilder.cc.

                                               {
 
    // initialize state lists
    for (int bbi = 0; bbi < cfg_->nodeCount(); bbi++) {
        BasicBlockNode& bbn = cfg_->node(bbi);
        BasicBlock& bb = bbn.basicBlock();
        if (bb.liveRangeData_ == NULL) {
            bb.liveRangeData_ = new LiveRangeData;
        }
        BBData* bbd = new BBData(bbn);
        bbData_[&bbn] = bbd;
        // in the beginning all are unreached
        if (bbn.isNormalBB()) {
            blocksByState_[BB_UNREACHED].push_back(bbd);
        }
    }
}

References BasicBlockNode::basicBlock(), BB_UNREACHED, bbData_, blocksByState_, cfg_, BasicBlockNode::isNormalBB(), TTAProgram::BasicBlock::liveRangeData_, BoostGraph< GraphNode, GraphEdge >::node(), and BoostGraph< GraphNode, GraphEdge >::nodeCount().

Referenced by createMemAndFUstateDeps(), createRegisterDeps(), and searchRegisterDeaths().

Here is the call graph for this function:

◆ isAddressTraceable()

bool DataDependenceGraphBuilder::isAddressTraceable ( const ProgramOperation & pop )

protected

Can some analyzer say something about this address?

Parameters

mn	Movenode containing memory address write.

Returns: true if some alias analyzer knows something about the address, ie can return something else than ALIAS_UNKNOWN.

Definition at line 1974 of file DataDependenceGraphBuilder.cc.

                                                                          {
 
    for (unsigned int i = 0; i < aliasAnalyzers_.size(); i++) {
        if (aliasAnalyzers_.at(i)->isAddressTraceable(*currentDDG_, pop)) {
            return true;
        }
    }
    return false;
}

References aliasAnalyzers_, and currentDDG_.

Referenced by hasEarlierMemWriteToSameAddressWithSameGuard(), and processMemWrite().

◆ isAlwaysDifferentFU()

bool DataDependenceGraphBuilder::isAlwaysDifferentFU	(	const MoveNode *	srcMN,
		const MoveNode *	dstMN
	)

protected

Check if operations are assigned to differnt FU

Operations forced to different FUs are independent since the operation state is per FU. Check if the moves have forced set of FUs and if the sets overlap.

Parameters

srcMN	MoveNode first node for dependency check
dstMN	MoveNode for which dependency needs to be checked

Returns: Nodes are alawys mapped to different FU

Definition at line 2994 of file DataDependenceGraphBuilder.cc.

                                                  {
    if (srcMN->move().hasAnnotations(
            TTAProgram::ProgramAnnotation::ANN_ALLOWED_UNIT_DST) &&
        dstMN->move().hasAnnotations(
            TTAProgram::ProgramAnnotation::ANN_ALLOWED_UNIT_DST)) {
        bool alwaysDifferentFUs = true;
        for (int idx = 0;
             idx < srcMN->move().annotationCount(
                       TTAProgram::ProgramAnnotation::ANN_ALLOWED_UNIT_DST);
             ++idx) {
            if (dstMN->move().hasAnnotation(
                    TTAProgram::ProgramAnnotation::ANN_ALLOWED_UNIT_DST,
                    srcMN->move()
                        .annotation(
                            idx, TTAProgram::ProgramAnnotation::
                                     ANN_ALLOWED_UNIT_DST)
                        .stringValue())) {
                alwaysDifferentFUs = false;
                break;
            }
        }
        return alwaysDifferentFUs;
    }
    return false;
}

References TTAProgram::ProgramAnnotation::ANN_ALLOWED_UNIT_DST, TTAProgram::AnnotatedInstructionElement::annotation(), TTAProgram::AnnotatedInstructionElement::hasAnnotation(), TTAProgram::AnnotatedInstructionElement::hasAnnotations(), and MoveNode::move().

Referenced by checkAndCreateMemDep(), and createSideEffectEdges().

Here is the call graph for this function:

◆ isTriggering()

bool DataDependenceGraphBuilder::isTriggering ( const MoveNode & mn )

protected

Definition at line 810 of file DataDependenceGraphBuilder.cc.

                                                                {
    int destIndex = mn.move().destination().operationIndex();
    const Operation& op = mn.destinationOperation().operation();
    int triggerIndex = MachineInfo::triggerIndex(*mach_, op);
    switch (triggerIndex) {
    case -1: {
        TCEString msg = "Trigger index ambiguous for operation: ";
        msg << op.name() << " in the machine.";
        throw IllegalMachine(__FILE__,__LINE__,__func__, msg);
        break; 
    }
    case 0: {
        TCEString msg = "Operation: ";
        msg << op.name() << " Not found from the machine";
        throw CompileError(__FILE__,__LINE__,__func__, msg);
        break;
    }
    default:
        return triggerIndex == destIndex;
    }
}

References __func__, TTAProgram::Move::destination(), MoveNode::destinationOperation(), mach_, MoveNode::move(), Operation::name(), ProgramOperation::operation(), TTAProgram::Terminal::operationIndex(), and MachineInfo::triggerIndex().

Referenced by processDestination().

Here is the call graph for this function:

◆ iterateBBs()

void DataDependenceGraphBuilder::iterateBBs ( ConstructionPhase phase )

protected

Iterates over basic blocks as long as there is some BB to process.

Handles a BB, updates the live value lists of its successors. If incoming live values of a BB change, it's scheduled for reprocessing.

Parameters

phase whether to handle register& operation deps or memory and side-effect dependencies.

Definition at line 2345 of file DataDependenceGraphBuilder.cc.

                             {
 
    while (!blocksByState_[BB_QUEUED].empty()) {
        std::list<BBData*>::iterator bbIter =
            blocksByState_[BB_QUEUED].begin();
        BBData& bbd = **bbIter;
 
        // construct or update BB
        if (bbd.constructed_) {
            updateBB(bbd, phase);
        } else {
            constructIndividualBB(bbd, phase);
        }
        // mark as ready
        changeState(bbd, BB_READY);
 
        // create deps after and update that to succeeding BBs.
        // succeeding BB's are also queued to be scheduled here.
        // queue succeeding BB's in case either
        // * their input data has changed
        // * current BB was processed for the first time
        if (phase == REGISTERS_AND_PROGRAM_OPERATIONS) {
            if (updateRegistersAliveAfter(bbd) || !bbd.constructed_) {
                setSucceedingPredeps(bbd, !bbd.constructed_, phase);
            }
        } else {
            if (updateMemAndFuAliveAfter(bbd) || !bbd.constructed_) {
                setSucceedingPredeps(bbd, !bbd.constructed_, phase);
            }
        }
 
        bbd.constructed_ = true;
    }
}

References BB_QUEUED, BB_READY, blocksByState_, changeState(), DataDependenceGraphBuilder::BBData::constructed_, constructIndividualBB(), REGISTERS_AND_PROGRAM_OPERATIONS, setSucceedingPredeps(), updateBB(), updateMemAndFuAliveAfter(), and updateRegistersAliveAfter().

Referenced by createMemAndFUstateDeps(), and createRegisterDeps().

Here is the call graph for this function:

◆ iterateRegisterDeaths()

void DataDependenceGraphBuilder::iterateRegisterDeaths ( )

protected

Iterates thru all queued BB's and find register deaths from them.

Loops as long as something keeps changing.

Definition at line 2924 of file DataDependenceGraphBuilder.cc.

                                                  {
 
    // loop as long as we have unprocessed/changed BB's
    while (!blocksByState_[BB_QUEUED].empty()) {
        std::list<BBData*>::iterator bbIter =
            blocksByState_[BB_QUEUED].begin();
        BBData& bbd = **bbIter;
 
        // mark as ready
        changeState(bbd, BB_READY);
 
        if (updateRegistersUsedInOrAfter(bbd) || (!bbd.constructed_)) {
            // if there asre more registers read after start of this BB,
            // have to update this information to preceedign BBs,
            // and check if they need to be reprocessed.
            updatePreceedingRegistersUsedAfter(bbd, !bbd.constructed_);
        }
        bbd.constructed_ = true;
    }
}

References BB_QUEUED, BB_READY, blocksByState_, changeState(), DataDependenceGraphBuilder::BBData::constructed_, updatePreceedingRegistersUsedAfter(), and updateRegistersUsedInOrAfter().

Referenced by searchRegisterDeaths().

Here is the call graph for this function:

◆ memoryCategory()

TCEString DataDependenceGraphBuilder::memoryCategory ( const MoveNodeUse & mnd )

protected

Checks into which category this memory address belongs.

Memory accesses in different categories cannot alias, and there is separate bookkeeping for every category. Current implementation separates spills, different alias spaces, restrict keywords and opencl work items.

Parameters

mnd	MoveNodeUse which transfers the address of the memory operation.

Returns: string which is then used as key for map. unique for different categories, empty for the default category.

@TODO: create some memorycategorizer interface for this analysis?

Definition at line 1999 of file DataDependenceGraphBuilder.cc.

                                                                 {
 
    TCEString category;
 
//    MoveNode* addressNode = addressMove(*mnd.mn());
//    if (addressNode != NULL && addressNode->isMove()) {
    const TTAProgram::Move& move = mnd.mn()->move();//addressNode->move();
    
    // spill annotations are in all operands.
    for (int j = 0; j < move.annotationCount(); j++) {
        TTAProgram::ProgramAnnotation anno = move.annotation(j);
        if (anno.id() ==
            TTAProgram::ProgramAnnotation::ANN_STACKUSE_SPILL) {
            return "_SPILL";
        }
        if (anno.id() ==
            TTAProgram::ProgramAnnotation::ANN_STACKUSE_RA_SAVE) {
            return "_RA";
        }
        if (anno.id() ==
            TTAProgram::ProgramAnnotation::ANN_STACKUSE_FP_SAVE) {
            return "_FP";
        }
        if (anno.id() ==
            TTAProgram::ProgramAnnotation::ANN_CONSTANT_MEM) {
            return "_CONSTANT";
        }
    }
    if (!mnd.mn()->isDestinationOperation()) {
        PRINT_VAR(mnd.mn()->toString());
        abortWithError("Not destination operation!");
    }
    ProgramOperation& po = mnd.mn()->destinationOperation();
 
    LLVMTCECmdLineOptions* llvmOptions =
        dynamic_cast<LLVMTCECmdLineOptions*>(
                Application::cmdLineOptions());
    if (llvmOptions == NULL || !llvmOptions->disableAddressSpaceAA()) {
        // address space
        for (int i = 0; i < po.inputMoveCount(); i++) {
            MoveNode& mn = po.inputMove(i);
            Move& m = mn.move();
            if (m.hasAnnotations(
                    ProgramAnnotation::ANN_POINTER_ADDR_SPACE)) {
                if (m.annotation(
                        0, ProgramAnnotation::ANN_POINTER_ADDR_SPACE).stringValue()
                    != "0") {
                    category +=
                        "_AS:" +
                        m.annotation(
                            0, ProgramAnnotation::ANN_POINTER_ADDR_SPACE)
                        .stringValue();
                    break;
                }
            }
        }
    }
    for (int i = 0; i < po.inputMoveCount(); i++) {
        MoveNode& mn = po.inputMove(i);
        Move& m = mn.move();
        TCEString pointerName = "";
        // restrict keyword.
        if (m.hasAnnotations(
                ProgramAnnotation::ANN_POINTER_NAME) &&
            m.hasAnnotations(
                ProgramAnnotation::ANN_POINTER_NOALIAS)) {
            pointerName =
                m.annotation(
                    0, ProgramAnnotation::ANN_POINTER_NAME).stringValue();
            category += "_RESTRICT:" + pointerName;            
            break;
        }
    }
 
    /* OpenCL work item variable access.
       
    OpenCL kernels enforce memory consistency for local and global
    memory only at explicit barrier() calls within a work group.
    Thus, all memory accesses between work items can be considered
    independent in alias analysis in the regions between barrier
    calls. 
    */ 
    for (int i = 0; i < po.inputMoveCount(); i++) {
        MoveNode& mn = po.inputMove(i);
        Move& m = mn.move();
        if (m.hasAnnotations(ProgramAnnotation::ANN_OPENCL_WORK_ITEM_ID)) {
            category += 
                "_OPENCL_WI:" + 
                Conversion::toHexString(
                    m.annotation(
                        0, ProgramAnnotation::ANN_OPENCL_WORK_ITEM_ID).
                    intValue(), 8);
            break;
        }
    }
    return category;
}

Referenced by processMemUse(), and processMemWrite().

Here is the call graph for this function:

◆ processCall()

void DataDependenceGraphBuilder::processCall ( MoveNode & mn )

protected

Processes a call of a function.

Pseudo-reads from parameter registers and SP, writes to RV and RA.

Parameters

mn	MoveNode containg the function call move.

Definition at line 1532 of file DataDependenceGraphBuilder.cc.

                                                    {
 
    // calls mess up RA. But immediately, not after delay slots?
    processRegWrite(
        MoveNodeUse(mn, false, true, false), RA_NAME);
 
    // MoveNodeUse for sp and rv(not guard, not ra, is pseudo)
    MoveNodeUse mnd2(mn, false,false, true);
 
    // call is considered read of sp
    TCEString sp = specialRegisters_[REG_SP];
    if (sp != "") {
        processRegUse(mnd2,sp);
    }
 
    // call is considered as write of RV
    TCEString rv = specialRegisters_[REG_RV];
    if (rv != "") {
        if (rvIsParamReg_) {
            processRegUse(mnd2,rv);
        }
        processRegWrite(mnd2,rv);
    }
 
    // process all vector rv values
    for (int i = REG_VRV;;i--) {
        auto vrvIt = specialRegisters_.find(i);
        if (vrvIt != specialRegisters_.end()) {
            processRegWrite(mnd2, vrvIt->second);
        } else {
            break;
        }
    }
 
    // call is considered as write of RV high (64-bit return values)
    TCEString rvh = specialRegisters_[REG_RV_HIGH];
    if (rvh != "") {
        processRegWrite(mnd2, rvh);
    }
 
    // params
    for (int i = 0; i < 4;i++) {
        TCEString paramReg = specialRegisters_[REG_IPARAM+i];
        if (paramReg != "") {
            processRegUse(mnd2, paramReg);
        }
    }
}

References processRegUse(), processRegWrite(), RA_NAME, REG_IPARAM, REG_RV, REG_RV_HIGH, REG_SP, REG_VRV, rvIsParamReg_, and specialRegisters_.

Referenced by processTriggerRegistersAndOperations().

Here is the call graph for this function:

◆ processDestination()

void DataDependenceGraphBuilder::processDestination	(	class MoveNode &	moveNode,
		ConstructionPhase	phase
	)

protected

Analyzes destination of a move. Updates bookkeeping and handles WaW and WaR dependencies of the move.

Checks whether destination is operation or register and calls other functions to do the actual dependence checks etc.

Parameters

moveNode	MoveNode whose destination is being processed.
phase	whether to handle register& operation deps or memory and side-effect dependencies.

Definition at line 844 of file DataDependenceGraphBuilder.cc.

                                                 {
    Terminal& dest = moveNode.move().destination();
 
    // is this a operand to an operation?
    if (dest.isFUPort()) {
        if (!(dynamic_cast<const SpecialRegisterPort*>(&dest.port()))) {
            TerminalFUPort& tfpd = dynamic_cast<TerminalFUPort&>(dest);
            Operation &dop = tfpd.hintOperation();
 
            if (phase == REGISTERS_AND_PROGRAM_OPERATIONS) {
                if (tfpd.isOpcodeSetting()) {
                    processTriggerRegistersAndOperations(
                        moveNode, dop);
                } else {
                    processOperand(moveNode, dop);
                }
            } else { // memory and fu state deps
                if (dop.usesMemory() || dop.hasSideEffects() ||
                    dop.affectsCount() || dop.affectedByCount() ||
                    moveNode.move().isControlFlowMove()) {
                    if (isTriggering(moveNode)) {
                        processTriggerMemoryAndFUStates(moveNode, dop);
                    }
                }
            }
        } else {  // RA write
            if (phase == REGISTERS_AND_PROGRAM_OPERATIONS) {
                processRegWrite(MoveNodeUse(moveNode,false,true), RA_NAME);
            }
        }
    } else {
        if (dest.isGPR()) {
            // we do not care about register reads in second phase
            if (phase == REGISTERS_AND_PROGRAM_OPERATIONS) {
                TerminalRegister& tr = dynamic_cast<TerminalRegister&>(dest);
                TCEString regName = DisassemblyRegister::registerName(tr);
                processRegWrite(MoveNodeUse(moveNode), regName);
            }
        } else { // something else
            throw IllegalProgram(__FILE__,__LINE__,__func__,
                                 "Move has illegal destination" +
                                 moveNode.toString());
        }
    }
}

References __func__, Operation::affectedByCount(), Operation::affectsCount(), TTAProgram::Move::destination(), Operation::hasSideEffects(), TTAProgram::TerminalFUPort::hintOperation(), TTAProgram::Move::isControlFlowMove(), TTAProgram::Terminal::isFUPort(), TTAProgram::Terminal::isGPR(), TTAProgram::TerminalFUPort::isOpcodeSetting(), isTriggering(), MoveNode::move(), TTAProgram::Terminal::port(), processOperand(), processRegWrite(), processTriggerMemoryAndFUStates(), processTriggerRegistersAndOperations(), RA_NAME, DisassemblyRegister::registerName(), REGISTERS_AND_PROGRAM_OPERATIONS, MoveNode::toString(), and Operation::usesMemory().

Referenced by constructIndividualBB().

Here is the call graph for this function:

◆ processEntryNode()

void DataDependenceGraphBuilder::processEntryNode ( MoveNode & mn )

protected

Processes the pseudo deps from entry node.

This procedure must be called when currentBB is the first real BB of the procedure.

Definition at line 2694 of file DataDependenceGraphBuilder.cc.

                                                              {
 
    // initializes RA
    currentBB_->basicBlock().liveRangeData_->regDefReaches_[RA_NAME].insert(mn);
 
    // sp
    MoveNodeUse mnd2(mn);
    TCEString sp = specialRegisters_[REG_SP];
    if (sp != "") {
        currentBB_->basicBlock().liveRangeData_->regDefReaches_[sp].insert(mnd2);
    }
 
    if (rvIsParamReg_) {
        TCEString rv = specialRegisters_[REG_RV];
        if (rv != "") {
            currentBB_->basicBlock().liveRangeData_->regDefReaches_[rv].insert(
                mnd2);
        }
    }
 
    // params
    // this is for old frontend generated code.
    for (int i = 0;;i++) {
        TCEString paramReg = specialRegisters_[REG_IPARAM+i];
        if(paramReg != "") {
            currentBB_->basicBlock().liveRangeData_->regDefReaches_[paramReg].insert(mnd2);
        } else {
            break;
        }
    }
 
    TCEString fp = specialRegisters_[REG_FP];
    if (fp != "") {
        currentBB_->basicBlock().liveRangeData_->regDefReaches_[fp].insert(
            mnd2);
    }
}

References BasicBlockNode::basicBlock(), currentBB_, TTAProgram::BasicBlock::liveRangeData_, RA_NAME, REG_FP, REG_IPARAM, REG_RV, REG_SP, LiveRangeData::regDefReaches_, rvIsParamReg_, and specialRegisters_.

Referenced by createRegisterDeps().

Here is the call graph for this function:

◆ processGuard()

void DataDependenceGraphBuilder::processGuard ( MoveNode & moveNode )

protected

Analyzes dependencies related to guard usage.

Finds the guard register used for the guard and the move Which writes the guard register, and creates a guard egde between them.

Parameters

moveNode MNData of move containing guarded move.

Definition at line 760 of file DataDependenceGraphBuilder.cc.

                                                           {
 
    // new code
    const Guard& g = moveNode.move().guard().guard();
    const RegisterGuard* rg = dynamic_cast<const RegisterGuard*>(&g);
    if (rg != NULL) {
        TCEString regName = rg->registerFile()->name() + '.' +
            Conversion::toString(rg->registerIndex());
        processRegUse(MoveNodeUse(moveNode, true),regName);
    } else {
        throw IllegalProgram(
            __FILE__,__LINE__,__func__,
            "Analysis for port guards not supported! used in: "
            + moveNode.toString());
    }
}

References __func__, TTAProgram::Move::guard(), TTAProgram::MoveGuard::guard(), MoveNode::move(), TTAMachine::Component::name(), processRegUse(), TTAMachine::RegisterGuard::registerFile(), TTAMachine::RegisterGuard::registerIndex(), MoveNode::toString(), and Conversion::toString().

Referenced by constructIndividualBB().

Here is the call graph for this function:

◆ processMemUse()

void DataDependenceGraphBuilder::processMemUse ( MoveNodeUse mnd )

protected

Processes a memory read.

Creates dependence edges and updates bookkeeping.

Parameters

mnd	MoveNodeUse of MoveNode being processed.

Definition at line 1800 of file DataDependenceGraphBuilder.cc.

                                                         {
 
    TCEString category = memoryCategory(mnd);
 
    // can be multiple if some write predicated
    std::set<MoveNodeUse>& defines =
        currentBB_->basicBlock().liveRangeData_->memDefines_[category];
 
    // no kills/barriers to this one in this basic block.
    if (currentBB_->basicBlock().liveRangeData_->memKills_[category].mn() == NULL) {
 
        // check if there is "guarded kill" to this mem address
        bool guardedKillFound = 
            hasEarlierMemWriteToSameAddressWithSameGuard(mnd, defines);
 
        if (!guardedKillFound) {
            currentBB_->basicBlock().liveRangeData_->memFirstUses_[category].insert(mnd);
            // so create deps from previous BB's
            updateMemUse(mnd, category);
        }
    }
 
    // create deps from writes in this BB.LIVERANGEDATA_->
    for (MoveNodeUseSet::iterator iter =
             defines.begin(); iter != defines.end(); iter++) {
        checkAndCreateMemDep(*iter, mnd, DataDependenceEdge::DEP_RAW);
    }
    // update bookkeeping.
    currentBB_->basicBlock().liveRangeData_->memLastUses_[category].insert(mnd);
}

References BasicBlockNode::basicBlock(), checkAndCreateMemDep(), currentBB_, DataDependenceEdge::DEP_RAW, hasEarlierMemWriteToSameAddressWithSameGuard(), TTAProgram::BasicBlock::liveRangeData_, LiveRangeData::memDefines_, LiveRangeData::memFirstUses_, LiveRangeData::memKills_, LiveRangeData::memLastUses_, memoryCategory(), and updateMemUse().

Referenced by createTriggerDependencies().

Here is the call graph for this function:

◆ processMemWrite()

void DataDependenceGraphBuilder::processMemWrite ( MoveNodeUse mnd )

protected

Updates memory operation bookkeeping and creates WaR and WaW memory dependencies.

Parameters

moveNode MoveNodeUse related to Move whose memory write to are processing.

Definition at line 1744 of file DataDependenceGraphBuilder.cc.

                                                           {
 
    TCEString category = memoryCategory(mnd);
 
    std::set<MoveNodeUse>& defines =
        currentBB_->basicBlock().liveRangeData_->memDefines_[category];
 
    std::set<MoveNodeUse>& lastUses =
        currentBB_->basicBlock().liveRangeData_->memLastUses_[category];
 
    // check if no earlier barriers/kills to this one in this bb?
    if (currentBB_->basicBlock().liveRangeData_->memKills_[category].mn() == NULL) {
 
        // is this a kill?
        if (mnd.mn()->move().isUnconditional() &&
            !isAddressTraceable(mnd.mn()->destinationOperation())) {
            currentBB_->basicBlock().liveRangeData_->memKills_[category] = mnd;
        }
 
        // check if there is "guarded kill" to this mem address
        bool guardedKillFound = 
            hasEarlierMemWriteToSameAddressWithSameGuard(mnd, defines);
        
        if (!guardedKillFound) {
            // may have incoming WaW's / WaRs to this
            currentBB_->basicBlock().liveRangeData_->memFirstDefines_[category].insert(mnd);
            updateMemWrite(mnd, category);
        }
    }
 
    bool traceable = isAddressTraceable(mnd.mn()->destinationOperation());
 
    checkAndCreateMemAntideps(
        mnd, defines, DataDependenceEdge::DEP_WAW, traceable);
 
    checkAndCreateMemAntideps(
        mnd, lastUses, DataDependenceEdge::DEP_WAR, traceable);
 
    // does this kill previous deps?
    if (mnd.mn()->move().isUnconditional() && !traceable) {
        currentBB_->basicBlock().liveRangeData_->memLastKill_[category] = mnd;
        defines.clear();
        lastUses.clear();
    }
 
    defines.insert(mnd);
}

References BasicBlockNode::basicBlock(), checkAndCreateMemAntideps(), currentBB_, DataDependenceEdge::DEP_WAR, DataDependenceEdge::DEP_WAW, MoveNode::destinationOperation(), hasEarlierMemWriteToSameAddressWithSameGuard(), isAddressTraceable(), TTAProgram::Move::isUnconditional(), TTAProgram::BasicBlock::liveRangeData_, LiveRangeData::memDefines_, LiveRangeData::memFirstDefines_, LiveRangeData::memKills_, LiveRangeData::memLastKill_, LiveRangeData::memLastUses_, memoryCategory(), MoveNodeUse::mn(), MoveNode::move(), and updateMemWrite().

Referenced by createTriggerDependencies(), and processTriggerMemoryAndFUStates().

Here is the call graph for this function:

◆ processOperand()

void DataDependenceGraphBuilder::processOperand	(	class MoveNode &	moveNode,
		Operation &	dop
	)

protected

Analyzes operand writes.

Part of ProgramOperation creation.

Parameters

moveNode	mnData related to a move which writes a parameter.
dop	Operation whose parameter is being written.

Definition at line 1062 of file DataDependenceGraphBuilder.cc.

                                        {
 
    // first operands already analyzed for PO? 
    // then update existing.
    if (currentData_->destPending_ != NULL) {
        ProgramOperationPtr po = currentData_->destPending_;
 
        assert(&dop == &po->operation());
 
        if (!po->isComplete()) {
            po->addInputNode(moveNode);
            moveNode.addDestinationOperationPtr(po);
        } else {
            // The MoveNode and the PO has been created before entering DDG
            // building (in LLVMTCEBuilder.cc).
        }
        return;
    }
 
    // create a new ProgramOperation
    TerminalFUPort& tfpd = 
        dynamic_cast<TerminalFUPort&>(moveNode.move().destination());
    ProgramOperationPtr po;
    if (tfpd.hasProgramOperation()) {
        po = tfpd.programOperation();
    } else {
        po = ProgramOperationPtr(new ProgramOperation(dop));
        moveNode.addDestinationOperationPtr(po);
        po->addInputNode(moveNode);
    }
    currentData_->destPending_ = po;
}

References MoveNode::addDestinationOperationPtr(), assert, currentData_, TTAProgram::Move::destination(), DataDependenceGraphBuilder::BBData::destPending_, TTAProgram::TerminalFUPort::hasProgramOperation(), MoveNode::move(), and TTAProgram::TerminalFUPort::programOperation().

Referenced by processDestination().

Here is the call graph for this function:

◆ processRegUse()

void DataDependenceGraphBuilder::processRegUse	(	MoveNodeUse	mnd,
		const TCEString &	reg
	)

protected

Handles a usage of a register value.

The usage can be either register read or guard usage. Creates the incoming edges and handles bookkeping related to the register read.

Parameters

mnd	Data about the register use
reg	Register containing the value being used.

Definition at line 1229 of file DataDependenceGraphBuilder.cc.

                                           {
 
    // We may have multiple definitions to a register alive 
    // (statically) at same time if some of the writes were guarded,
    // so we don't know which of them were actually executed,
    // so we have a set instead of single value.
    std::set<MoveNodeUse>& defines =
        currentBB_->basicBlock().liveRangeData_->regDefines_[reg];
 
    std::set<MoveNodeUse> sameGuardDefines = earlierWritesWithSameGuard(mnd, defines);
    // find if we have a earlier write with same guard. In this case
    // no need to draw dependencies over it.
    bool guardedKillFound = !sameGuardDefines.empty();
 
    // then create the edges. if no guarded kill found,
    // all non-exclusive. if guarded kill found, not to uncond move.
    for (std::set<MoveNodeUse>::iterator i = defines.begin();
         i != defines.end(); i++) {
        // If we do not have a guarded kill, draw edges from all defines.
        // If we have a guarded kill, only draw edges from 
        // unconditional moves, as the guarded kill overshadows the 
        // inconditional writes.
        if (!guardedKillFound || (!i->mn()->move().isUnconditional() &&
                                  !currentDDG_->hasRegWaw(*i, sameGuardDefines))) {
            if (!currentDDG_->exclusingGuards(*(i->mn()), *(mnd.mn()))) {
                DataDependenceEdge* dde =
                    new DataDependenceEdge(
                        mnd.ra() ? DataDependenceEdge::EDGE_RA :
                        DataDependenceEdge::EDGE_REGISTER,
                        DataDependenceEdge::DEP_RAW, reg, mnd.guard(), false,
                        i->pseudo(), mnd.pseudo(), i->loop());
 
                currentDDG_->connectOrDeleteEdge(*i->mn(), *mnd.mn(), dde);
            }
        }
    }
 
    // writes in previous BB's killed or not?
    // if not(this bb has a kill), has to check deps from incoming BB's.
    if (currentBB_->basicBlock().liveRangeData_->regKills_.find(reg) ==
        currentBB_->basicBlock().liveRangeData_->regKills_.end()) {
 
        if (!guardedKillFound) {
            // process dependencies from previous BB's
            currentBB_->basicBlock().liveRangeData_->regFirstUses_[reg].
                insert(mnd);
 
            currentDDG_->updateRegUse(mnd, reg, currentBB_->basicBlock());
        }
    }
    currentBB_->basicBlock().liveRangeData_->regLastUses_[reg].insert(mnd);
 
    // Two writes to opposite guard may create a combined kill-pair.
    // But if this is a read between them, it has to be marked in order
    // to save bookkeeping about this move when the another write occurs.
    // So mark here that we have a read if we have one guarded write
    // in our bookkeeping as potential half of a kill pair.
    std::map<TCEString, std::pair<MoveNodeUse, bool> >::iterator iter =
        currentBB_->basicBlock().liveRangeData_->potentialRegKills_.find(reg);
    if (iter != currentBB_->basicBlock().liveRangeData_->potentialRegKills_.end()) {
        iter->second.second = true;
    }
}

References BasicBlockNode::basicBlock(), DataDependenceGraph::connectOrDeleteEdge(), currentBB_, currentDDG_, DataDependenceEdge::DEP_RAW, earlierWritesWithSameGuard(), DataDependenceEdge::EDGE_RA, DataDependenceEdge::EDGE_REGISTER, DataDependenceGraph::exclusingGuards(), MoveNodeUse::guard(), DataDependenceGraph::hasRegWaw(), TTAProgram::BasicBlock::liveRangeData_, MoveNodeUse::mn(), LiveRangeData::potentialRegKills_, MoveNodeUse::pseudo(), MoveNodeUse::ra(), LiveRangeData::regDefines_, LiveRangeData::regFirstUses_, LiveRangeData::regKills_, LiveRangeData::regLastUses_, and DataDependenceGraph::updateRegUse().

Referenced by processCall(), processGuard(), processReturn(), and processSource().

Here is the call graph for this function:

◆ processRegWrite()

void DataDependenceGraphBuilder::processRegWrite	(	MoveNodeUse	mnd,
		const TCEString &	reg
	)

protected

Analyzes a write to a register.

Creates dependence edges and updates bookkeeping.

Parameters

mnd	MoveNodeUse containing MoveNode that writes a register
reg	register being written by the given movenode.

Definition at line 1369 of file DataDependenceGraphBuilder.cc.

                                           {
 
    // We may have multiple definitions to a register alive 
    // (statically) at same time if some of the writes were guarded,
    // so we don't know which of them were actually executed,
    // so we have a set instead of single value.
    std::set<MoveNodeUse>& defines =
        currentBB_->basicBlock().liveRangeData_->regDefines_[reg];
 
    // Set of register reads which after last kill.
    std::set<MoveNodeUse>& lastUses =
        currentBB_->basicBlock().liveRangeData_->regLastUses_[reg];
 
    // find if we have a earlier write with same guard. In this case
    // no need to draw dependencies over it.
    bool guardedKillFound = hasEarlierWriteWithSameGuard(mnd, defines);
 
    // if no kills to this reg in this BB, this one kills it.
    if (currentBB_->basicBlock().liveRangeData_->regKills_.find(reg) ==
        currentBB_->basicBlock().liveRangeData_->regKills_.end()) {
 
        // is this alone a kill?
        if (mnd.mn()->move().isUnconditional()) {
            currentBB_->basicBlock().liveRangeData_->regKills_[reg].first = mnd;
            currentBB_->basicBlock().liveRangeData_->regKills_[reg].second = MoveNodeUse();
        } else {
            // two guarded moves with opposite guards together may be a kill.
            // Check if we have such previous guarded write with opposite
            // guard.
            std::map<TCEString, std::pair<MoveNodeUse, bool> >::iterator
                iter =
                currentBB_->basicBlock().liveRangeData_->potentialRegKills_.find(reg);
            if (iter != currentBB_->basicBlock().liveRangeData_->potentialRegKills_.end() &&
                currentDDG_->exclusingGuards(
                    *(iter->second.first.mn()), *(mnd.mn()))) {
                currentBB_->basicBlock().liveRangeData_->regKills_[reg].first =
                    iter->second.first;
                currentBB_->basicBlock().liveRangeData_->regKills_[reg].second = mnd;
            }
        }
        if (!guardedKillFound) {
            // may have incoming WaW's / WaRs to this
            // insert to bookkeeping for further analysis.
            currentBB_->basicBlock().liveRangeData_->regFirstDefines_[reg].insert(mnd);
 
            // do we need to create some inter-bb-antideps?
            if (currentDDG_->hasSingleBBLoopRegisterAntidependencies()) {
                // deps from other BB.LIVERANGEDATA_->
                currentDDG_->updateRegWrite(
                    mnd, reg, currentBB_->basicBlock());
            }
        }
    }
 
    // Create antideps to defines and uses in this same BB.LIVERANGEDATA_->
    if (currentDDG_->hasIntraBBRegisterAntidependencies()) {
        createRegisterAntideps(
            reg, mnd, defines, DataDependenceEdge::DEP_WAW, guardedKillFound);
 
        createRegisterAntideps(
            reg, mnd, lastUses, DataDependenceEdge::DEP_WAR, 
            guardedKillFound);
    }
 
    // if unconditional, this kills previous deps.
    if (mnd.mn()->move().isUnconditional()) {
        defines.clear();
 
        currentBB_->basicBlock().liveRangeData_->regLastKills_[reg].first = mnd;
        currentBB_->basicBlock().liveRangeData_->regLastKills_[reg].second = MoveNodeUse();
 
        // clear reads to given reg.
        lastUses.clear();
        currentBB_->basicBlock().liveRangeData_->potentialRegKills_.erase(reg);
    } else {
        // two guarded moves with opposite guards together may be a kill.
        // Check if we have such previous guarded write with opposite
        // guard.
        std::map<TCEString, std::pair<MoveNodeUse, bool> >::iterator iter =
            currentBB_->basicBlock().liveRangeData_->potentialRegKills_.find(reg);
        if (iter != currentBB_->basicBlock().liveRangeData_->potentialRegKills_.end() &&
            currentDDG_->exclusingGuards(
                *(iter->second.first.mn()), *(mnd.mn()))) {
 
            // found earlier write which is exclusive with this one.
            // mark that these two together are a kill.
            currentBB_->basicBlock().liveRangeData_->regLastKills_[reg].first =
                iter->second.first;
            currentBB_->basicBlock().liveRangeData_->regLastKills_[reg].second = mnd;
 
            // If we have no usage of the register between these two
            // writes forming the kill pair, we can clear our bookkeeping.
 
            // only leave the other part of the kill to defines.
            defines.clear();
            defines.insert(iter->second.first);
 
            if (!iter->second.second) {
                // clear reads to given reg.
                lastUses.clear();
            }
        }
        currentBB_->basicBlock().liveRangeData_->potentialRegKills_[reg] =
            std::pair<MoveNodeUse, bool>(mnd, false);
    }
    defines.insert(mnd);
}

References BasicBlockNode::basicBlock(), createRegisterAntideps(), currentBB_, currentDDG_, DataDependenceEdge::DEP_WAR, DataDependenceEdge::DEP_WAW, DataDependenceGraph::exclusingGuards(), hasEarlierWriteWithSameGuard(), DataDependenceGraph::hasIntraBBRegisterAntidependencies(), DataDependenceGraph::hasSingleBBLoopRegisterAntidependencies(), TTAProgram::Move::isUnconditional(), TTAProgram::BasicBlock::liveRangeData_, MoveNodeUse::mn(), MoveNode::move(), LiveRangeData::potentialRegKills_, LiveRangeData::regDefines_, LiveRangeData::regFirstDefines_, LiveRangeData::regKills_, LiveRangeData::regLastKills_, LiveRangeData::regLastUses_, and DataDependenceGraph::updateRegWrite().

Referenced by processCall(), and processDestination().

Here is the call graph for this function:

◆ processResultRead()

void DataDependenceGraphBuilder::processResultRead ( MoveNode & moveNode )

protected

Analyzes a source of a result read.

Handles program operation creation and operation dependence creation.

Parameters

moveNode MoveNode of the move being analyzed.

Definition at line 1104 of file DataDependenceGraphBuilder.cc.

                                                                {
 
    // Goes thru all programoperations lacking result read.
    // There should be only one if well-behaving
    // universalmachine code.
    if (currentData_->readPending_ != NULL) {
        ProgramOperationPtr po = currentData_->readPending_;
        currentData_->poReadsHandled_++;
        
        if (!po->isComplete()) {
            po->addOutputNode(moveNode);
            moveNode.setSourceOperationPtr(po);
        }
 
        // if this PO is ready, remove from list of incomplete ones
        if (currentData_->poReadsHandled_ >= 
            po->operation().numberOfOutputs()) {
            createOperationEdges(po);
            currentData_->readPending_ = ProgramOperationPtr();
            currentDDG_->addProgramOperation(po);
            currentData_->poReadsHandled_ = 0;
        }
        return;
    }
    throw IllegalProgram(
        __FILE__, __LINE__, __func__,
        (boost::format("Result move '%s' without operands") %
         moveNode.move().toString()).str());
}

References __func__, DataDependenceGraph::addProgramOperation(), createOperationEdges(), currentData_, currentDDG_, MoveNode::move(), DataDependenceGraphBuilder::BBData::poReadsHandled_, DataDependenceGraphBuilder::BBData::readPending_, MoveNode::setSourceOperationPtr(), and TTAProgram::Move::toString().

Referenced by processSource().

Here is the call graph for this function:

◆ processReturn()

void DataDependenceGraphBuilder::processReturn ( MoveNode & moveNode )

protected

Processes a return from a function.

Creates pseudo-read-deps to SP and RV registers.

Parameters

moveNode moveNode containg the return move.

Definition at line 1486 of file DataDependenceGraphBuilder.cc.

                                                            {
    TCEString sp = specialRegisters_[REG_SP];
 
    // return is considered as read of sp; 
    // sp must be correct at the end of the procedure.
    if (sp != "") {
        processRegUse(MoveNodeUse(moveNode,false,false,true),sp);
    }
 
    // return is considered as read of RV.
    TCEString rv = specialRegisters_[REG_RV];
    if (rv != "") {
        processRegUse(MoveNodeUse(moveNode,false,false,true),rv);
    }
 
    // process all vector rv values
    for (int i = REG_VRV;;i--) {
        auto vrvIt = specialRegisters_.find(i);
        if (vrvIt != specialRegisters_.end()) {
            processRegUse(
                MoveNodeUse(moveNode,false,false,true),vrvIt->second);
        } else {
            break;
        }
    }
 
    // return is also considered as read of RV high(for 64-bit RV's)
    TCEString rvh = specialRegisters_[REG_RV_HIGH];
    if (rvh != "") {
        processRegUse(MoveNodeUse(moveNode,false,false,true),rvh);
    }
 
    TCEString fp = specialRegisters_[REG_FP];
    if (fp != "") {
        processRegUse(MoveNodeUse(moveNode,false,false,true),fp);
    }
}

References processRegUse(), REG_FP, REG_RV, REG_RV_HIGH, REG_SP, REG_VRV, and specialRegisters_.

Referenced by processSource().

Here is the call graph for this function:

◆ processSource()

void DataDependenceGraphBuilder::processSource ( MoveNode & moveNode )

protected

Analysis a source of a move and processes it's dependencies, and if it's a result read then also participates in ProgramOperation creation.

Parameters

moveNode Movenode being analyzed.

Definition at line 785 of file DataDependenceGraphBuilder.cc.

                                                            {
    Terminal& source = moveNode.move().source();
 
    // is this result move of an operation?
    if (source.isFUPort()) {
        if (!(dynamic_cast<const SpecialRegisterPort*>(&source.port()))) {
            processResultRead(moveNode);
        } else {
            // handle read from RA.
            processRegUse(MoveNodeUse(moveNode, false, true), RA_NAME);
 
            if (moveNode.move().isReturn()) {
                processReturn(moveNode);
            }
        }
    } else {
        if (source.isGPR()) {
            TerminalRegister& tr = dynamic_cast<TerminalRegister&>(source);
            TCEString regName = DisassemblyRegister::registerName(tr);
            processRegUse(MoveNodeUse(moveNode), regName);
        }
    }
}

References TTAProgram::Terminal::isFUPort(), TTAProgram::Terminal::isGPR(), TTAProgram::Move::isReturn(), MoveNode::move(), TTAProgram::Terminal::port(), processRegUse(), processResultRead(), processReturn(), RA_NAME, DisassemblyRegister::registerName(), and TTAProgram::Move::source().

Referenced by constructIndividualBB().

Here is the call graph for this function:

◆ processTriggerMemoryAndFUStates()

void DataDependenceGraphBuilder::processTriggerMemoryAndFUStates	(	MoveNode &	moveNode,
		Operation &	dop
	)

protected

Analyze write to a trigger of an operation.

Participates in ProgramOperation building. Calls createTriggerDependencies(moveNode, dop) to create the memory and fu state dependence egdes of the operation. Checks if operation is call and if it is, processes the call-related memory dependencies.

Parameters

moveNode	mnData related to a move which triggers an operation
dop	Operation being triggered

Definition at line 1040 of file DataDependenceGraphBuilder.cc.

                                        {
 
    createTriggerDependencies(moveNode, dop);
    
    // handle call mem deps
    if (moveNode.move().isFunctionCall()) {
        // no guard, is not ra, is pseudo.
        MoveNodeUse mnd2(moveNode, false, false, true);
        processMemWrite(mnd2);
    }
}

References createTriggerDependencies(), TTAProgram::Move::isFunctionCall(), MoveNode::move(), and processMemWrite().

Referenced by processDestination().

Here is the call graph for this function:

◆ processTriggerPO()

void DataDependenceGraphBuilder::processTriggerPO	(	class MoveNode &	moveNode,
		Operation &	dop
	)

protected

Handles ProgramOperation creation for a triggering move.

Parameters

moveNode	triggering movenode.
dop	operation which is being triggered by the movenode.

Definition at line 948 of file DataDependenceGraphBuilder.cc.

                                        {
    if (currentData_->destPending_ != NULL) {
        ProgramOperationPtr po = currentData_->destPending_;
        
        if (&dop != &po->operation()) {
            std::cerr << "pending po: " << po->toString() << std::endl;
            std::cerr << "current dop: " << dop.name() << std::endl;
            currentDDG_->writeToDotFile("build_fail_po.dot");
        }
        assert(&dop == &po->operation());
        if (!po->isComplete()) {
            po->addInputNode(moveNode);
            moveNode.addDestinationOperationPtr(po);
        }
        if (po->isReady()) {
            currentData_->destPending_ = ProgramOperationPtr();
            if (dop.numberOfOutputs() > 0) {
                assert(currentData_->readPending_ == NULL);
                currentData_->readPending_ = po;
        currentData_->poReadsHandled_ = 0;
            } else {
                currentDDG_->addProgramOperation(po);
            }
        } else {
            throw IllegalProgram(
                __FILE__, __LINE__, __func__, 
                "Trigger before all operands.");
        }
        return;
    }
    // only one triggering input?
    if (dop.numberOfInputs() == 1) {
        TerminalFUPort& tfpd = 
            dynamic_cast<TerminalFUPort&>(moveNode.move().destination());
        ProgramOperationPtr po;
        if (tfpd.hasProgramOperation()) {
            po = tfpd.programOperation();
        } else {
            po = ProgramOperationPtr(new ProgramOperation(dop));
            moveNode.addDestinationOperationPtr(po);
            po->addInputNode(moveNode);
        }
        if (dop.numberOfOutputs()) {
            assert(currentData_->readPending_ == NULL);
            currentData_->readPending_ = po;
        } else {
            currentDDG_->addProgramOperation(po);
        }
    } else { // trigger came too early
        const TCEString moveDisasm =
            POMDisassembler::disassemble(moveNode.move());
        throw IllegalProgram(
            __FILE__,__LINE__, __func__,
            TCEString("Trigger without operand in ") + moveDisasm);
    }
}

References __func__, MoveNode::addDestinationOperationPtr(), DataDependenceGraph::addProgramOperation(), assert, currentData_, currentDDG_, TTAProgram::Move::destination(), DataDependenceGraphBuilder::BBData::destPending_, POMDisassembler::disassemble(), TTAProgram::TerminalFUPort::hasProgramOperation(), MoveNode::move(), Operation::name(), Operation::numberOfInputs(), Operation::numberOfOutputs(), DataDependenceGraphBuilder::BBData::poReadsHandled_, TTAProgram::TerminalFUPort::programOperation(), DataDependenceGraphBuilder::BBData::readPending_, and GraphBase< GraphNode, GraphEdge >::writeToDotFile().

Referenced by processTriggerRegistersAndOperations().

Here is the call graph for this function:

◆ processTriggerRegistersAndOperations()

void DataDependenceGraphBuilder::processTriggerRegistersAndOperations	(	MoveNode &	moveNode,
		Operation &	dop
	)

protected

Analyze write to a trigger of an operation.

Participates in ProgramOperation building. Calls createTriggerDependencies(moveNode, dop) to create the register and operation dependence egdes of the operation. Checks if operation is call and if it is, processes the call-related register dependencies.

Parameters

moveNode	mnData related to a move which triggers an operation
dop	Operation being triggered

Definition at line 1018 of file DataDependenceGraphBuilder.cc.

                                        {
 
    processTriggerPO(moveNode, dop);
    
    if (moveNode.move().isFunctionCall()) {
        processCall(moveNode);
    }
}

References TTAProgram::Move::isFunctionCall(), MoveNode::move(), processCall(), and processTriggerPO().

Referenced by processDestination().

Here is the call graph for this function:

◆ queueFirstBB()

BasicBlockNode * DataDependenceGraphBuilder::queueFirstBB ( )

protected

Queues first basic block to be processed.

Returns: the first basic block node

Definition at line 2238 of file DataDependenceGraphBuilder.cc.

                                         {
    // get first BB where to start
    BasicBlockNodeSet firstBBs = cfg_->successors(cfg_->entryNode());
    assert(firstBBs.size() == 1);
    BasicBlockNode* firstBB = *firstBBs.begin();
    changeState(*(bbData_[firstBB]), BB_QUEUED);
    return firstBB;
}

References assert, BB_QUEUED, bbData_, cfg_, changeState(), ControlFlowGraph::entryNode(), and BoostGraph< GraphNode, GraphEdge >::successors().

Referenced by createMemAndFUstateDeps(), and createRegisterDeps().

Here is the call graph for this function:

◆ searchRegisterDeaths()

void DataDependenceGraphBuilder::searchRegisterDeaths ( )

protected

Searches the last usages a registers.

This information is used for checking whether given register contains live value at given cycle.

Definition at line 2882 of file DataDependenceGraphBuilder.cc.

                                                 {
 
    // initializes states of all BB's to unreached.
    initializeBBStates();
 
    // start from end of cfg. (sink nodes), queue them
    ControlFlowGraph::NodeSet lastBBs = cfg_->sinkNodes();
    for (ControlFlowGraph::NodeSet::iterator iter =
             lastBBs.begin(); iter != lastBBs.end(); iter++) {
        changeState(*(bbData_[*iter]), BB_QUEUED);
    }
 
    // then iterate over all BB's, going from BB to it's
    // predecessors.
    iterateRegisterDeaths();
 
    // all should have gone thru, but if there are 4ever loop causing
    // BB's not reachable from the end.
    // we might want to handle those also.
    while (!blocksByState_[BB_UNREACHED].empty()) {
        if (Application::verboseLevel() > Application::VERBOSE_LEVEL_DEFAULT) {
            Application::logStream() << "Warning: BB in 4ever loop!"
                                     << std::endl;
            Application::logStream() << "In procedure: " << cfg_->name() <<
                std::endl;
//            cfg.writeToDotFile("4everloop_bb.dot");
        }
        changeState(**blocksByState_[BB_UNREACHED].begin(), BB_QUEUED);
 
        iterateRegisterDeaths();
    }
 
    // free bb data
    AssocTools::deleteAllValues(bbData_);
}

References BB_QUEUED, BB_UNREACHED, bbData_, blocksByState_, cfg_, changeState(), AssocTools::deleteAllValues(), initializeBBStates(), iterateRegisterDeaths(), Application::logStream(), BoostGraph< GraphNode, GraphEdge >::name(), BoostGraph< GraphNode, GraphEdge >::sinkNodes(), Application::VERBOSE_LEVEL_DEFAULT, and Application::verboseLevel().

Referenced by build().

Here is the call graph for this function:

◆ setSucceedingPredeps()

void DataDependenceGraphBuilder::setSucceedingPredeps	(	BBData &	bbd,
		bool	queueAll,
		ConstructionPhase	phase
	)

protected

Sets outgoing data from this BB to incoming data of successors.

Also queues them to be reprocessed if they are changed.

Parameters

bbd	BBD whose successors will be updated.
queueAll	If true, queues all successors even if they do not change.
phase	whether to handle register& operation deps or memory and side-effect dependencies.

Definition at line 2424 of file DataDependenceGraphBuilder.cc.

                             {
    BasicBlockNode& bbn = *bbd.bblock_;
    BasicBlock& bb = bbn.basicBlock();
 
    BasicBlockNodeSet forwardSuccessors = cfg_->successors(bbn, true);
    for (BasicBlockNodeSet::iterator succIter = forwardSuccessors.begin();
         succIter != forwardSuccessors.end(); succIter++) {
        setSucceedingPredepsForBB(
            bb, **succIter, queueAll, false, phase);
    }
 
    // successors over loop edges.
    BasicBlockNodeSet backwardSuccessors = cfg_->successors(bbn, false, true);
    for (BasicBlockNodeSet::iterator succIter = backwardSuccessors.begin();
         succIter != backwardSuccessors.end(); succIter++) {
        setSucceedingPredepsForBB(
            bb, **succIter, queueAll, true, phase);
    }
}

References BasicBlockNode::basicBlock(), DataDependenceGraphBuilder::BBData::bblock_, cfg_, setSucceedingPredepsForBB(), and BoostGraph< GraphNode, GraphEdge >::successors().

Referenced by iterateBBs().

Here is the call graph for this function:

◆ setSucceedingPredepsForBB()

void DataDependenceGraphBuilder::setSucceedingPredepsForBB	(	TTAProgram::BasicBlock &	processedBB,
		BasicBlockNode &	successor,
		bool	queueAll,
		bool	loop,
		ConstructionPhase	phase
	)

protected

Sets outgoing data from this BB to incoming data of one successor.

Also queues them to be reprocessed if they are changed.

Parameters

bb	BB whose successor will be updated.
successor	successor BB whose incoming data is being updated.
queueAll	If true, queues all successors even if they do not change.
loop	whether to add loop property to the copied bookkeeping, ie create edges with loop property.
phase	whether to handle register& operation deps or memory and side-effect dependencies.

Definition at line 2460 of file DataDependenceGraphBuilder.cc.

                             {
 
    BasicBlock& succBB = successor.basicBlock();
    BBData& succData = *bbData_[&successor];
    bool changed = false;
 
    if (phase == REGISTERS_AND_PROGRAM_OPERATIONS) {
        changed |= LiveRangeData::appendUseMapSets(
            bb.liveRangeData_->regDefAfter_, 
            succBB.liveRangeData_->regDefReaches_, loop);
 
        if (currentDDG_->hasAllRegisterAntidependencies() || 
            (&bb == &succBB && 
             currentDDG_->hasSingleBBLoopRegisterAntidependencies())) {
            changed |= LiveRangeData::appendUseMapSets(
                bb.liveRangeData_->regUseAfter_, 
                succBB.liveRangeData_->regUseReaches_, loop);
        }
    } else {
        // mem deps + fu state deps
 
        changed |= LiveRangeData::appendUseMapSets(
            bb.liveRangeData_->memDefAfter_, 
            succBB.liveRangeData_->memDefReaches_, loop);
 
        changed |= LiveRangeData::appendUseMapSets(
            bb.liveRangeData_->memUseAfter_, 
            succBB.liveRangeData_->memUseReaches_, loop);
 
        size_t size = succBB.liveRangeData_->fuDepReaches_.size();
        LiveRangeData::appendMoveNodeUse(
            bb.liveRangeData_->fuDepAfter_, 
            succBB.liveRangeData_->fuDepReaches_, loop);
        if (succBB.liveRangeData_->fuDepReaches_.size() > size) {
            changed = true;
        }
    }
 
    // need to queue successor for update?
    if (changed || queueAll) {
        changeState(succData, BB_QUEUED, loop);
    }
}

References LiveRangeData::appendMoveNodeUse(), LiveRangeData::appendUseMapSets(), BasicBlockNode::basicBlock(), BB_QUEUED, bbData_, changeState(), currentDDG_, LiveRangeData::fuDepAfter_, LiveRangeData::fuDepReaches_, DataDependenceGraph::hasAllRegisterAntidependencies(), DataDependenceGraph::hasSingleBBLoopRegisterAntidependencies(), TTAProgram::BasicBlock::liveRangeData_, LiveRangeData::memDefAfter_, LiveRangeData::memDefReaches_, LiveRangeData::memUseAfter_, LiveRangeData::memUseReaches_, LiveRangeData::regDefAfter_, LiveRangeData::regDefReaches_, REGISTERS_AND_PROGRAM_OPERATIONS, LiveRangeData::regUseAfter_, and LiveRangeData::regUseReaches_.

Referenced by setSucceedingPredeps().

Here is the call graph for this function:

◆ updateBB()

void DataDependenceGraphBuilder::updateBB	(	BBData &	bbd,
		ConstructionPhase	phase
	)

protected

Reprocesses a basic block which has already once been processed.

Checks dependencies to first uses and definitions of registers, does not recreate edges inside the basic block.

Parameters

bbd	BBData for basic block which is being reprocessed.
phase	whether to handle register& operation deps or memory and side-effect dependencies.

Definition at line 2743 of file DataDependenceGraphBuilder.cc.

                                          {
    currentData_ = &bbd;
    currentBB_ = bbd.bblock_;
    BasicBlock& bb = bbd.bblock_->basicBlock();
 
    // register and operation dependencies
    if (phase == REGISTERS_AND_PROGRAM_OPERATIONS) {
        //loop all regs having ext deps and create reg edges
        for (MoveNodeUseMapSet::iterator firstUseIter =
                 bb.liveRangeData_->regFirstUses_.begin();
             firstUseIter != bb.liveRangeData_->regFirstUses_.end();
             firstUseIter++) {
            TCEString reg = firstUseIter->first;
            std::set<MoveNodeUse>& firstUseSet = firstUseIter->second;
            for (std::set<MoveNodeUse>::iterator iter2 = firstUseSet.begin();
                 iter2 != firstUseSet.end(); iter2++) {
                currentDDG_->updateRegUse(
                    *iter2, reg, currentBB_->basicBlock());
            }
        }
 
        if (currentDDG_->hasSingleBBLoopRegisterAntidependencies()) {
            // antidependencies to registers
            for (MoveNodeUseMapSet::iterator firstDefineIter =
                     bb.liveRangeData_->regFirstDefines_.begin();
                 firstDefineIter != bb.liveRangeData_->regFirstDefines_.end(); 
                 firstDefineIter++) {
                TCEString reg = firstDefineIter->first;
                std::set<MoveNodeUse>& firstDefineSet = 
                    firstDefineIter->second;
                for (std::set<MoveNodeUse>::iterator iter2=
                         firstDefineSet.begin();
                     iter2 != firstDefineSet.end(); iter2++) {
                    currentDDG_->updateRegWrite(
                        *iter2, reg, currentBB_->basicBlock());
                }
            }
        }
    } else {
        // phase 1 .. mem deps and fu state/side effect dependencies.
 
        //loop all first mem uses having ext deps and create mem edges
        for (MoveNodeUseMapSet::iterator firstUseIter =
                 bb.liveRangeData_->memFirstUses_.begin();
             firstUseIter != bb.liveRangeData_->memFirstUses_.end(); 
             firstUseIter++) {
            TCEString category = firstUseIter->first;
            std::set<MoveNodeUse>& firstUseSet = firstUseIter->second;
            for (std::set<MoveNodeUse>::iterator iter2 = firstUseSet.begin();
                 iter2 != firstUseSet.end(); iter2++) {
                updateMemUse(*iter2, category);
            }
        }
 
        // antidependencies to memory
        for (MoveNodeUseMapSet::iterator firstDefineIter =
                 bb.liveRangeData_->memFirstDefines_.begin();
             firstDefineIter != bb.liveRangeData_->memFirstDefines_.end();
             firstDefineIter++) {
            TCEString category = firstDefineIter->first;
            std::set<MoveNodeUse>& firstDefineSet = firstDefineIter->second;
            for (std::set<MoveNodeUse>::iterator iter2=firstDefineSet.begin();
                 iter2 != firstDefineSet.end(); iter2++) {
                updateMemWrite(*iter2, category);
            }
        }
 
        // and fu state deps
        for (MoveNodeUseSet::iterator iter =
                 bb.liveRangeData_->fuDeps_.begin();
             iter != bb.liveRangeData_->fuDeps_.end(); iter++) {
            Terminal& dest = iter->mn()->move().destination();
            TerminalFUPort& tfpd = dynamic_cast<TerminalFUPort&>(dest);
            Operation &dop = tfpd.hintOperation();
            createSideEffectEdges(
                currentBB_->basicBlock().liveRangeData_->fuDepReaches_, 
                *iter->mn(), dop);
        }
    }
}

References BasicBlockNode::basicBlock(), DataDependenceGraphBuilder::BBData::bblock_, createSideEffectEdges(), currentBB_, currentData_, currentDDG_, LiveRangeData::fuDepReaches_, LiveRangeData::fuDeps_, DataDependenceGraph::hasSingleBBLoopRegisterAntidependencies(), TTAProgram::TerminalFUPort::hintOperation(), TTAProgram::BasicBlock::liveRangeData_, LiveRangeData::memFirstDefines_, LiveRangeData::memFirstUses_, LiveRangeData::regFirstDefines_, LiveRangeData::regFirstUses_, REGISTERS_AND_PROGRAM_OPERATIONS, updateMemUse(), updateMemWrite(), DataDependenceGraph::updateRegUse(), and DataDependenceGraph::updateRegWrite().

Referenced by iterateBBs().

Here is the call graph for this function:

◆ updateMemAndFuAliveAfter()

bool DataDependenceGraphBuilder::updateMemAndFuAliveAfter ( BBData & bbd )

protected

Updates live mem access lists and fu state usages after a basic block has been processed.

Copies use and write definitions from the basic block and it's prodecessors to the after alive data structures.

Parameters

bbd	BBData for bb being processed

Returns: true if the after alive data structures have been changed

Definition at line 2592 of file DataDependenceGraphBuilder.cc.

                                                                     {
    BasicBlock& bb = bbd.bblock_->basicBlock();
    bool changed = false;
 
    // copy mem definitions that are alive
    for (MoveNodeUseMapSet::iterator iter = bb.liveRangeData_->memDefReaches_.begin();
         iter != bb.liveRangeData_->memDefReaches_.end(); iter++) {
 
        TCEString category = iter->first;
        std::set<MoveNodeUse>& preDefs = iter->second;
        std::set<MoveNodeUse>& defAfter = bb.liveRangeData_->memDefAfter_[category];
        std::set<MoveNodeUse>& ownDefines = bb.liveRangeData_->memDefines_[category];
        size_t size = defAfter.size();
 
        // only copy incomin dep if this has no unconditional writes,
        if (bb.liveRangeData_->memKills_.find(category) == bb.liveRangeData_->memKills_.end()) {
            for (std::set<MoveNodeUse>::iterator i = preDefs.begin();
                 i != preDefs.end(); i++ ) {
//                MoveNode* preAddress = addressMove(*(i->mn()));
                ProgramOperation& prevPop = i->mn()->destinationOperation();
 
                bool overWritten = false;
                for (std::set<MoveNodeUse>::iterator j = ownDefines.begin();
                     j != ownDefines.end(); j++) {
                    if (j->mn()->move().isUnconditional()) {
//                        MoveNode* ownAddress = addressMove(*(j->mn()));
                        ProgramOperation& ownPop = j->mn()->destinationOperation();
                        if (analyzeMemoryAlias(prevPop, ownPop, i->bbRelation()) ==
                            MemoryAliasAnalyzer::ALIAS_TRUE) {
                            overWritten = true;
                            break;
                        }
                    }
                }
                if (!overWritten) {
                    defAfter.insert(*i);
                }
            }
        }
        // if size increased, the data has changed
        if (size < defAfter.size()) {
            changed = true;
        }
    }
    // own deps. need to do only once but now does after every.
    changed |= LiveRangeData::appendUseMapSets(
        bb.liveRangeData_->memDefines_,
        bb.liveRangeData_->memDefAfter_, false);
 
    // copy uses that are alive
    for (MoveNodeUseMapSet::iterator iter = bb.liveRangeData_->memUseReaches_.begin();
         iter != bb.liveRangeData_->memUseReaches_.end(); iter++) {
 
        TCEString category = iter->first;
        std::set<MoveNodeUse>& preUses = iter->second;
        std::set<MoveNodeUse>& useAfter = bb.liveRangeData_->memUseAfter_[category];
        std::set<MoveNodeUse>& ownDefines = bb.liveRangeData_->memDefines_[category];
 
        size_t size = useAfter.size();
        if (bb.liveRangeData_->memKills_.find(category) == bb.liveRangeData_->memKills_.end()) {
            for (std::set<MoveNodeUse>::iterator i = preUses.begin();
                 i != preUses.end(); i++ ) {
//                MoveNode* preAddress = addressMove(*(i->mn()));
                ProgramOperation& prevPop = i->mn()->destinationOperation();
                bool overWritten = false;
                for (std::set<MoveNodeUse>::iterator j =
                         ownDefines.begin(); j != ownDefines.end(); j++) {
                    if (j->mn()->move().isUnconditional()) {
                        ProgramOperation& ownPop = j->mn()->destinationOperation();
                        if (analyzeMemoryAlias(prevPop, ownPop, i->bbRelation()) ==
                            MemoryAliasAnalyzer::ALIAS_TRUE) {
                            overWritten = true;
                            break;
                        }
                    }
                }
                if (!overWritten) {
                    useAfter.insert(*i);
                }
            }
        }
        // if size increased, the data has changed
        if (size < useAfter.size()) {
            changed = true;
        }
    }
 
    // fu deps
    size_t size = bb.liveRangeData_->fuDepAfter_.size();
    AssocTools::append(bb.liveRangeData_->fuDeps_, bb.liveRangeData_->fuDepAfter_);
    if (bb.liveRangeData_->fuDepAfter_.size() > size) {
        changed = true;
    }
    return changed;
}

References MemoryAliasAnalyzer::ALIAS_TRUE, analyzeMemoryAlias(), AssocTools::append(), LiveRangeData::appendUseMapSets(), BasicBlockNode::basicBlock(), DataDependenceGraphBuilder::BBData::bblock_, LiveRangeData::fuDepAfter_, LiveRangeData::fuDeps_, TTAProgram::BasicBlock::liveRangeData_, LiveRangeData::memDefAfter_, LiveRangeData::memDefines_, LiveRangeData::memDefReaches_, LiveRangeData::memKills_, LiveRangeData::memUseAfter_, and LiveRangeData::memUseReaches_.

Referenced by iterateBBs().

Here is the call graph for this function:

◆ updateMemUse()

void DataDependenceGraphBuilder::updateMemUse	(	MoveNodeUse	mnd,
		const TCEString &	category
	)

protected

Checks memory read against uses and defs in incoming basic blocks. Creates the needed dependence edges.

Parameters

mnd	MoveNodeUse of movenode being processed.
category	which memory category this memory write belongs.

Definition at line 2859 of file DataDependenceGraphBuilder.cc.

                                                {
 
    for (MoveNodeUseSet::iterator iter =
             currentBB_->basicBlock().liveRangeData_->memDefReaches_[category].begin();
        iter != currentBB_->basicBlock().liveRangeData_->memDefReaches_[category].end();
        iter++) {
        checkAndCreateMemDep(*iter, mnd,DataDependenceEdge::DEP_RAW);
    }
}

References BasicBlockNode::basicBlock(), checkAndCreateMemDep(), currentBB_, DataDependenceEdge::DEP_RAW, TTAProgram::BasicBlock::liveRangeData_, and LiveRangeData::memDefReaches_.

Referenced by processMemUse(), and updateBB().

Here is the call graph for this function:

◆ updateMemWrite()

void DataDependenceGraphBuilder::updateMemWrite	(	MoveNodeUse	mnd,
		const TCEString &	category
	)

protected

Checks memory write against uses and defs in incoming basic blocks. Creates the needed dependence edges.

Parameters

mnd	MoveNodeUse of movenode being processed.
category	which memory category this memory write belongs.

Definition at line 2833 of file DataDependenceGraphBuilder.cc.

                                                {
 
    // create waw edges from all alive writes to this node.
    for (MoveNodeUseSet::iterator iter =
        currentBB_->basicBlock().liveRangeData_->memDefReaches_[category].begin();
        iter != currentBB_->basicBlock().liveRangeData_->memDefReaches_[category].end();) {
        checkAndCreateMemDep(*iter++, mnd, DataDependenceEdge::DEP_WAW);
    }
 
    // create war edges from all alive reads to this node.
    for (MoveNodeUseSet::iterator iter = currentBB_->basicBlock().liveRangeData_->
            memUseReaches_[category].begin();
        iter != currentBB_->basicBlock().liveRangeData_->memUseReaches_[category].end();) {
        checkAndCreateMemDep(*iter++, mnd, DataDependenceEdge::DEP_WAR);
    }
}

References BasicBlockNode::basicBlock(), checkAndCreateMemDep(), currentBB_, DataDependenceEdge::DEP_WAR, DataDependenceEdge::DEP_WAW, TTAProgram::BasicBlock::liveRangeData_, LiveRangeData::memDefReaches_, and LiveRangeData::memUseReaches_.

Referenced by processMemWrite(), and updateBB().

Here is the call graph for this function:

◆ updatePreceedingRegistersUsedAfter()

void DataDependenceGraphBuilder::updatePreceedingRegistersUsedAfter	(	BBData &	bbd,
		bool	firstTime
	)

protected

Updates bookkeeping used for calculating register deaths.

Marks registers used at or after some BB to it's predecessor BB's.

Parameters

bbd	basic block to process.
firstTime	whether this BB is analyzer for the first time.

Definition at line 2390 of file DataDependenceGraphBuilder.cc.

                                 {
    BasicBlockNode& bbn = *bbd.bblock_;
    BasicBlock& bb = bbn.basicBlock();
    BasicBlockNodeSet predecessors = cfg_->predecessors(bbn);
    for (BasicBlockNodeSet::iterator predIter = predecessors.begin();
         predIter != predecessors.end(); predIter++) {
        BasicBlockNode* pred = *predIter;
        BasicBlock& predBB = pred->basicBlock();
        BBData& predData = *bbData_[pred];
        size_t size = predBB.liveRangeData_->registersUsedAfter_.size();
        AssocTools::append(
            bb.liveRangeData_->registersUsedInOrAfter_, predBB.liveRangeData_->registersUsedAfter_);
 
        // if updated, need to be handled again.
        if (predBB.liveRangeData_->registersUsedAfter_.size() > size || firstTime) {
            if (predData.state_ != BB_QUEUED) {
                changeState(predData, BB_QUEUED);
            }
        }
    }
}

References AssocTools::append(), BasicBlockNode::basicBlock(), BB_QUEUED, bbData_, DataDependenceGraphBuilder::BBData::bblock_, cfg_, changeState(), TTAProgram::BasicBlock::liveRangeData_, BoostGraph< GraphNode, GraphEdge >::predecessors(), LiveRangeData::registersUsedAfter_, LiveRangeData::registersUsedInOrAfter_, and DataDependenceGraphBuilder::BBData::state_.

Referenced by iterateRegisterDeaths().

Here is the call graph for this function:

◆ updateRegistersAliveAfter()

bool DataDependenceGraphBuilder::updateRegistersAliveAfter ( BBData & bbd )

protected

Updates live register lists after a basic block has been processed.

Copies use and define definitions from the basic block and it's prodecessors to the after alive data structures.

Parameters

bbd	BBData for bb being processed

Returns: true if the after alive data structures have been changed

Definition at line 2519 of file DataDependenceGraphBuilder.cc.

                 {
    BasicBlock& bb = bbd.bblock_->basicBlock();
    bool changed = false;
 
    // copy reg definitions that are alive
    for (MoveNodeUseMapSet::iterator iter = 
             bb.liveRangeData_->regDefReaches_.begin();
         iter != bb.liveRangeData_->regDefReaches_.end(); iter++) {
        
        TCEString reg = iter->first;
        std::set<MoveNodeUse>& preDefs = iter->second;
        // todo: clear or not?
        std::set<MoveNodeUse>& defAfter = bb.liveRangeData_->regDefAfter_[reg];
        size_t size = defAfter.size();
 
        // only copy incomin dep if this has no unconditional writes
        if (bb.liveRangeData_->regKills_.find(reg) == bb.liveRangeData_->regKills_.end()) {
            for (std::set<MoveNodeUse>::iterator i = preDefs.begin();
                 i != preDefs.end(); i++ ) {
                defAfter.insert(*i);
            }
        }
        // if size increased, the data has changed
        if (size < defAfter.size()) {
            changed = true;
        }
    }
    // own deps. need to do only once but now does after every.
    changed |= LiveRangeData::appendUseMapSets(
        bb.liveRangeData_->regDefines_, 
        bb.liveRangeData_->regDefAfter_, false);
    
    if (currentDDG_->hasAllRegisterAntidependencies()) {
        // copy uses that are alive
        for (MoveNodeUseMapSet::iterator iter =
                 bb.liveRangeData_->regUseReaches_.begin(); iter != bb.liveRangeData_->regUseReaches_.end();
             iter++) {
            TCEString reg = iter->first;
            std::set<MoveNodeUse>& preUses = iter->second;
            std::set<MoveNodeUse>& useAfter = bb.liveRangeData_->regUseAfter_[reg];
            size_t size = useAfter.size();
            if (bb.liveRangeData_->regKills_.find(reg) == bb.liveRangeData_->regKills_.end()) {
                for (std::set<MoveNodeUse>::iterator i = preUses.begin();
                     i != preUses.end(); i++ ) {
                    useAfter.insert(*i);
                }
            }
            // if size increased, the data has changed
            if (size < useAfter.size()) {
                changed = true;
            }
        }
    }
    
    // own deps. need to do only once but now does after every.
    changed |= LiveRangeData::appendUseMapSets(
        bb.liveRangeData_->regLastUses_,
        bb.liveRangeData_->regUseAfter_, false);
    return changed;
}

References LiveRangeData::appendUseMapSets(), BasicBlockNode::basicBlock(), DataDependenceGraphBuilder::BBData::bblock_, currentDDG_, DataDependenceGraph::hasAllRegisterAntidependencies(), TTAProgram::BasicBlock::liveRangeData_, LiveRangeData::regDefAfter_, LiveRangeData::regDefines_, LiveRangeData::regDefReaches_, LiveRangeData::regKills_, LiveRangeData::regLastUses_, LiveRangeData::regUseAfter_, and LiveRangeData::regUseReaches_.

Referenced by iterateBBs().

Here is the call graph for this function:

◆ updateRegistersUsedInOrAfter()

bool DataDependenceGraphBuilder::updateRegistersUsedInOrAfter ( BBData & bbd )

protected

Updates bookkeeping about registers used in this or later BBs.

This is a helper function used by searchRegisterDeaths() method.

Parameters

bbd	Data about one basicblock.

Returns: whether the bookkeeping was changed, ie the predecessors of this BB need to be reprocessed.

Definition at line 2955 of file DataDependenceGraphBuilder.cc.

                 {
    BasicBlock& bb = bbd.bblock_->basicBlock();
    size_t size = bb.liveRangeData_->registersUsedInOrAfter_.size();
 
    // if definition not here, it's earlier - copy.
    // if definition here, not alive unless read here.
    for (std::set<TCEString>::iterator i = bb.liveRangeData_->registersUsedAfter_.begin();
         i != bb.liveRangeData_->registersUsedAfter_.end(); i++) {
        // if not written in this, written earlier.
        if (bb.liveRangeData_->regKills_.find(*i) == bb.liveRangeData_->regKills_.end()) {
            bb.liveRangeData_->registersUsedInOrAfter_.insert(*i);
        }
    }
 
    // reads in this BB.liveRangeData_-> Only reads whose defining value comes/can come
    // outside this BB.liveRangeData_->
    for (MoveNodeUseMapSet::iterator i = bb.liveRangeData_->regFirstUses_.begin();
         i != bb.liveRangeData_->regFirstUses_.end(); i++) {
        bb.liveRangeData_->registersUsedInOrAfter_.insert(i->first);
    }
    if (bb.liveRangeData_->registersUsedInOrAfter_.size() > size) {
        return true;
    }
    return false;
}