#include <MachineInstrDDG.hh>

Inheritance diagram for MachineInstrDDG:

Collaboration diagram for MachineInstrDDG:

Public Types
typedef unsigned	Register

typedef std::set< Register >	RegisterSet

Public Types inherited from BoostGraph< MIDDGNode, MIDDGEdge >
typedef std::set< MIDDGNode *, typename GraphNode::Comparator >	NodeSet

typedef std::set< MIDDGEdge *, typename GraphEdge::Comparator >	EdgeSet

typedef MIDDGNode	Node
	The (base) node type managed by this graph.

typedef MIDDGEdge	Edge
	The (base) edge type managed by this graph.

Public Types inherited from GraphBase< GraphNode, GraphEdge >
typedef std::set< GraphNode *, typename GraphNode::Comparator >	NodeSet

typedef std::set< GraphEdge *, typename GraphEdge::Comparator >	EdgeSet

typedef GraphNode	Node
	Node type of this graph (possibly, a base class).

typedef GraphEdge	Edge
	Edge type of this graph (possibly, a base class).

Public Member Functions
	MachineInstrDDG (const MachineInstrDDG &parent)

	MachineInstrDDG (llvm::MachineFunction &mf, bool onlyTrueDeps=true)

virtual	~MachineInstrDDG ()

RegisterSet	allRegisters () const

MIDDGNode *	vregDefiner (Register vreg) const

MIDDGNode *	lastVregUser (Register vreg) const

int	falseDepHeightDelta (Register vreg, Register physReg) const

void	assignPhysReg (Register vreg, Register physReg)

bool	preceedingNodeUsesOrDefinesReg (const MIDDGNode &node, Register physReg) const

void	computeOptimalSchedule ()

TCEString	dotString () const

void	setPrintOnlyCriticalPath (bool flag)

Public Member Functions inherited from BoostGraph< MIDDGNode, MIDDGEdge >
	BoostGraph (bool allowLoopEdges=true)

	BoostGraph (const TCEString &name, bool allowLoopEdges=true)

	BoostGraph (const BoostGraph &other, bool allowLoopEdges=true)

	~BoostGraph ()

int	nodeCount () const

int	edgeCount () const

Node &	node (const int index) const

Node &	node (const int index, bool cacheResult) const

virtual Edge &	edge (const int index) const

virtual void	addNode (Node &node)

virtual Edge &	outEdge (const Node &node, const int index) const

virtual Edge &	inEdge (const Node &node, const int index) const

virtual EdgeSet	outEdges (const Node &node) const

virtual EdgeSet	inEdges (const Node &node) const

virtual EdgeSet	rootGraphOutEdges (const Node &node) const

virtual EdgeSet	rootGraphInEdges (const Node &node) const

virtual Edge &	rootGraphInEdge (const Node &node, const int index) const

virtual Edge &	rootGraphOutEdge (const Node &node, const int index) const

virtual int	rootGraphInDegree (const Node &node) const

virtual int	rootGraphOutDegree (const Node &node) const

virtual int	outDegree (const Node &node) const

virtual int	inDegree (const Node &node) const

virtual Node &	tailNode (const Edge &edge) const

virtual Node &	headNode (const Edge &edge) const

virtual void	connectNodes (const Node &nTail, const Node &nHead, Edge &e)

virtual void	disconnectNodes (const Node &nTail, const Node &nHead)

virtual void	moveInEdges (const Node &source, const Node &destination)

virtual void	moveOutEdges (const Node &source, const Node &destination)

virtual void	moveInEdge (const Node &source, const Node &destination, Edge &edge, const Node *tail=NULL, bool childs=false)

virtual void	moveOutEdge (const Node &source, const Node &destination, Edge &edge, const Node *head=NULL, bool childs=false)

virtual void	copyInEdge (const Node &destination, Edge &edge, const Node *tail=NULL)

virtual void	copyOutEdge (const Node &destination, Edge &edge, const Node *head=NULL)

virtual void	removeNode (Node &node)

virtual void	removeEdge (Edge &e)

virtual void	dropNode (Node &node)

virtual void	dropEdge (Edge &edge)

virtual bool	hasEdge (const Node &nTail, const Node &nHead) const

virtual NodeSet	rootNodes () const
	useful utility functions

virtual NodeSet	sinkNodes () const

virtual NodeSet	successors (const Node &node, bool ignoreBackEdges=false, bool ignoreForwardEdges=false) const

virtual NodeSet	predecessors (const Node &node, bool ignoreBackEdges=false, bool ignoreForwardEdges=false) const

int	maxPathLength (const MIDDGNode &node) const

int	maxSinkDistance (const MIDDGNode &node) const

int	maxSourceDistance (const MIDDGNode &node) const

bool	isInCriticalPath (const MIDDGNode &node) const

int	height () const

void	findAllPaths () const

void	detachSubgraph (BoostGraph &subGraph)

BoostGraph *	parentGraph ()

BoostGraph *	rootGraph ()

const BoostGraph *	rootGraph () const

bool	hasNode (const Node &) const

virtual const TCEString &	name () const

void	setName (const TCEString &newName)

bool	hasPath (MIDDGNode &src, const MIDDGNode &dest) const

void	restoreNodeFromParent (MIDDGNode &node)

bool	detectIllegalCycles () const

EdgeSet	connectingEdges (const Node &nTail, const Node &nHead) const

Public Member Functions inherited from GraphBase< GraphNode, GraphEdge >
	GraphBase ()

virtual	~GraphBase ()

virtual int	outDegree (const Node &node) const =0

virtual int	inDegree (const Node &node) const =0

virtual Edge &	outEdge (const Node &node, const int index) const =0

virtual Edge &	inEdge (const Node &node, const int index) const =0

virtual EdgeSet	outEdges (const Node &node) const =0

virtual EdgeSet	inEdges (const Node &node) const =0

virtual Node &	tailNode (const Edge &edge) const =0

virtual Node &	headNode (const Edge &edge) const =0

virtual bool	hasEdge (const Node &nTail, const Node &nHead) const =0

virtual EdgeSet	connectingEdges (const Node &nTail, const Node &nHead) const =0

virtual void	writeToDotFile (const TCEString &fileName) const

virtual void	addNode (Node &node)=0

virtual void	removeNode (Node &node)=0

virtual void	removeEdge (Edge &e)=0

virtual void	connectNodes (const Node &nTail, const Node &nHead, Edge &e)=0

virtual void	disconnectNodes (const Node &nTail, const Node &nHead)=0

Private Types
typedef std::map< Register, MIDDGNode * >	DefinerMap

typedef std::map< Register, NodeSet >	UserMap

typedef std::map< Register, Register >	RegisterMap

Private Member Functions
std::pair< MIDDGNode , MIDDGNode >	createFalseDepEdge (Register vreg, Register physReg) const

Private Attributes
RegisterSet	allRegisters_

DefinerMap	definers_

UserMap	users_

NodeSet	nodes_

std::set< MIDDGEdge * >	edges_

std::map< Register, MIDDGNode * >	lastPhysRegUsers_

std::map< Register, MIDDGNode * >	lastPhysRegDefiners_

RegisterMap	regAssignments_

const bool	onlyTrueDeps_

int	smallestCycle_

int	largestCycle_

std::map< int, std::list< MIDDGNode * > >	schedule_

llvm::MachineFunction &	mf_

const llvm::TargetRegisterInfo *	regInfo_

bool	printOnlyCriticalPath_

Additional Inherited Members
Protected Types inherited from BoostGraph< MIDDGNode, MIDDGEdge >
typedef std::set< RemovedEdgeDatum >	RemovedEdgeMap

typedef boost::adjacency_list< boost::listS, boost::vecS, boost::bidirectionalS, Node , Edge >	Graph
	Internal graph type, providing actual graph-like operations. This type definition relies on bundled properties of boost library, which need the host compiler to support partial template specialisation.

typedef boost::graph_traits< Graph >	GraphTraits
	Traits characterising the internal graph type.

typedef GraphTraits::out_edge_iterator	OutEdgeIter
	Output edge iterator type.

typedef GraphTraits::in_edge_iterator	InEdgeIter
	Input edge iterator type.

typedef GraphTraits::edge_iterator	EdgeIter
	Iterator type for the list of all edges in the graph.

typedef GraphTraits::vertex_iterator	NodeIter
	Iterator type for the list of all nodes in the graph.

typedef GraphTraits::edge_descriptor	EdgeDescriptor
	Type with which edges of the graph are seen internally.

typedef GraphTraits::vertex_descriptor	NodeDescriptor
	Type with which nodes of the graph are seen internally.

typedef hash_map< const Edge *, EdgeDescriptor, GraphHashFunctions >	EdgeDescMap

typedef hash_map< const Node *, NodeDescriptor, GraphHashFunctions >	NodeDescMap

typedef std::vector< std::vector< int > >	PathCache

Protected Member Functions inherited from BoostGraph< MIDDGNode, MIDDGEdge >
Node &	tailNode (const Edge &edge, const NodeDescriptor &headNode) const

Node &	headNode (const Edge &edge, const NodeDescriptor &tailNode) const

virtual void	connectNodes (const Node &nTail, const Node &nHead, Edge &e, GraphBase< MIDDGNode, MIDDGEdge > *modifier, bool creatingSG=false)

void	moveInEdges (const Node &source, const Node &destination, BoostGraph *modifierGraph)

virtual void	moveOutEdges (const Node &source, const Node &destination, BoostGraph *modifierGraph)

virtual void	removeNode (Node &node, BoostGraph *modifierGraph)

virtual void	removeEdge (Edge &e, const MIDDGNode tailNode, const MIDDGNode headNode, BoostGraph *modifierGraph=NULL)

bool	hasEdge (const Node &nTail, const Node &nHead, const Edge &edge) const

bool	hasEdge (const Edge &edge, const Node nTail=NULL, const Node nHead=NULL) const

void	restoreRemovedEdges (RemovedEdgeMap removedEdges)

EdgeDescriptor	descriptor (const Edge &e) const

NodeDescriptor	descriptor (const Node &n) const

EdgeDescriptor	edgeDescriptor (const NodeDescriptor &tailNode, const Edge &e) const

EdgeDescriptor	edgeDescriptor (const Edge &e, const NodeDescriptor &headNode) const

EdgeDescriptor	connectingEdge (const Node &nTail, const Node &nHead) const

void	replaceNodeWithLastNode (MIDDGNode &dest)

void	calculatePathLengths () const

void	calculatePathLengthsFast () const

void	calculateSinkDistance (const MIDDGNode &node, int len, bool looping=false) const

void	calculateSourceDistances (const MIDDGNode *startNode=NULL, int startingLength=0, bool looping=false) const

void	calculatePathLengthsOnConnect (const MIDDGNode &nTail, const MIDDGNode &nHead, MIDDGEdge &e)

void	sinkDistDecreased (const MIDDGNode &n) const

void	sourceDistDecreased (const MIDDGNode &n) const

virtual int	edgeWeight (MIDDGEdge &e, const MIDDGNode &n) const

void	clearDescriptorCache (EdgeSet edges)

void	constructSubGraph (BoostGraph &subGraph, NodeSet &nodes)

Protected Member Functions inherited from GraphBase< GraphNode, GraphEdge >
virtual bool	hasNode (const Node &) const =0

Protected Attributes inherited from BoostGraph< MIDDGNode, MIDDGEdge >
std::unordered_map< const MIDDGNode *, int >	sourceDistances_

std::unordered_map< const MIDDGNode *, int >	sinkDistances_

std::unordered_map< const MIDDGNode *, int >	loopingSourceDistances_

std::unordered_map< const MIDDGNode *, int >	loopingSinkDistances_

int	height_

Graph	graph_
	The internal graph structure.

EdgeDescMap	edgeDescriptors_

NodeDescMap	nodeDescriptors_

BoostGraph< MIDDGNode, MIDDGEdge > *	parentGraph_

std::vector< BoostGraph< MIDDGNode, MIDDGEdge > * >	childGraphs_

TCEString	name_

int	sgCounter_

std::set< Edge * >	ownedEdges_

bool	allowLoopEdges_

PathCache *	pathCache_

Detailed Description

Data Dependence Graph constructed from non-register allocated LLVM MachineInstructions.

Only true dependencies supported at the moment. Later we can might add support for adding the false dependencies introduced by the register allocator, if needed.

Definition at line 140 of file MachineInstrDDG.hh.

Member Typedef Documentation

◆ DefinerMap

typedef std::map<Register, MIDDGNode*> MachineInstrDDG::DefinerMap

private

Definition at line 173 of file MachineInstrDDG.hh.

◆ Register

typedef unsigned MachineInstrDDG::Register

Definition at line 143 of file MachineInstrDDG.hh.

◆ RegisterMap

typedef std::map<Register, Register> MachineInstrDDG::RegisterMap

private

Definition at line 175 of file MachineInstrDDG.hh.

◆ RegisterSet

typedef std::set<Register> MachineInstrDDG::RegisterSet

Definition at line 144 of file MachineInstrDDG.hh.

◆ UserMap

typedef std::map<Register, NodeSet> MachineInstrDDG::UserMap

private

Definition at line 174 of file MachineInstrDDG.hh.

Constructor & Destructor Documentation

◆ MachineInstrDDG() [1/2]

MachineInstrDDG::MachineInstrDDG ( const MachineInstrDDG & parent )

explicit

Constructor for creating a subgraph.

Definition at line 181 of file MachineInstrDDG.cc.

                                                              : 
    BoostGraph<MIDDGNode, MIDDGEdge>(
        std::string(parent.name(), true)),
    onlyTrueDeps_(parent.onlyTrueDeps_), mf_(parent.mf_) {
}

◆ MachineInstrDDG() [2/2]

POP_COMPILER_DIAGS MachineInstrDDG::MachineInstrDDG	(	llvm::MachineFunction &	mf,
		bool	onlyTrueDeps = `true`
	)

Constructs a DDG out of MachineInstructions.

Only true dependencies are supported at the moment.

Definition at line 66 of file MachineInstrDDG.cc.

                       :
    BoostGraph<MIDDGNode, MIDDGEdge>(
        std::string(mf.getFunction().getName().str()) + "_middg", true),
    onlyTrueDeps_(onlyTrueDeps), mf_(mf), 
    regInfo_(mf_.getTarget().getSubtargetImpl(
                 mf_.getFunction())->getRegisterInfo())
    , printOnlyCriticalPath_(false) {
    int instructions = 0;
    for (llvm::MachineFunction::const_iterator bbi = mf.begin(); 
         bbi != mf.end(); ++bbi) {
        const llvm::MachineBasicBlock& bb = *bbi;
        for (llvm::MachineBasicBlock::const_iterator ii = bb.begin(); 
             ii != bb.end(); ++ii) {
            const llvm::MachineInstr& i = *ii;
            MIDDGNode* node = new MIDDGNode(i, instructions);
            nodes_.insert(node);
            addNode(*node);
            assert(hasNode(*node));
            ++instructions;
            for (unsigned oi = 0; oi < i.getNumOperands(); ++oi) {
                const llvm::MachineOperand& operand = i.getOperand(oi);
                if (!operand.isReg())
                    continue;
 
                if (operand.isUndef()) {
                    // this is probably a global register defined in some other
                    // function, thus it can be ignored (only reads from it in this func)
                    continue;
                }
                if (operand.isImplicit()) {
                    // the call clobbered regs
                    continue;
                }                    
 
                if (llvm::Register::isPhysicalRegister(
                        operand.getReg())) {
 
                    // only physical reg at this point should be the stack pointer,
                    // which is a global reg we can ignore
#ifdef DEBUG_MI_DDG
                    Application::logStream() 
                        << "found a phys reg " << operand.getReg() 
                        << std::endl;
                    if (operand.getType() == llvm::MachineOperand::MO_FrameIndex)
                        Application::logStream() << "SP";
#endif
                    continue;
                }
 
                if (operand.isUse()) {
                    users_[operand.getReg()].insert(node);
#ifdef DEBUG_MI_DDG
                    Application::logStream()
                        << "uses: " << operand.getReg() << std::endl;
#endif
                } else if (operand.isDef()) {
                    if (definers_[operand.getReg()] != NULL) {
                        // in case we already have a definer, use the
                        // one from the different basic block to avoid loops
                        if (definers_[operand.getReg()]->machineInstr()->
                            getParent() != &bb) {
#ifdef DEBUG_MI_DDG
                            Application::logStream()
                                << "found a potential back edge case, "
                                << "using the definer from another BB"
                                << std::endl;
#endif
                            continue;
                        }
                    } else {
                        definers_[operand.getReg()] = node;
                    }
                } else {
#ifdef DEBUG_MI_DDG
                    Application::logStream()
                        << "unknown operand " << oi << std::endl;
#endif
                    continue;
                }
                allRegisters_.insert(operand.getReg());
            }
        }
    }
 
 
    for (DefinerMap::iterator i = definers_.begin(); i != definers_.end(); 
         ++i) {
        Register reg = (*i).first;
        MIDDGNode* source = (*i).second;
        NodeSet& users = users_[reg];
        for (std::set<MIDDGNode*>::iterator u = users.begin(); u != users.end();
             ++u) {
            MIDDGNode* dest = *u;
 
            if (hasPath(*dest, *source)) {
#ifdef DEBUG_MI_DDG
                Application::logStream() 
                    << "ignoring edge that would create a loop"
                    << std::endl;
#endif
                continue;
            }
 
            MIDDGEdge* edge = new MIDDGEdge(reg);
            edges_.insert(edge);
            connectNodes(*source, *dest, *edge);
        }
    }
}

References BoostGraph< MIDDGNode, MIDDGEdge >::addNode(), allRegisters_, assert, BoostGraph< MIDDGNode, MIDDGEdge >::connectNodes(), definers_, BoostGraph< MIDDGNode, MIDDGEdge >::edge(), edges_, BoostGraph< MIDDGNode, MIDDGEdge >::hasNode(), BoostGraph< MIDDGNode, MIDDGEdge >::hasPath(), Application::logStream(), BoostGraph< MIDDGNode, MIDDGEdge >::node(), nodes_, and users_.

Here is the call graph for this function:

◆ ~MachineInstrDDG()

MachineInstrDDG::~MachineInstrDDG ( )

virtual

Definition at line 188 of file MachineInstrDDG.cc.

188 {

189}

Member Function Documentation

◆ allRegisters()

RegisterSet MachineInstrDDG::allRegisters ( ) const

inline

Definition at line 154 of file MachineInstrDDG.hh.

154{ return allRegisters_; }

References allRegisters_.

Referenced by VirtRegIndependenceGraph::VirtRegIndependenceGraph().

◆ assignPhysReg()

void MachineInstrDDG::assignPhysReg	(	Register	vreg,
		Register	physReg
	)

Assigns the given physical register to the given virtual register.

Does not yet add false dependence edges, just updates the last phys reg use bookkeeping.

Definition at line 506 of file MachineInstrDDG.cc.

                                                              {
 
    regAssignments_[vreg] = physReg;
 
    MIDDGNode* lastDefiner = vregDefiner(vreg);
 
    if (lastPhysRegDefiners_.find(physReg) != lastPhysRegDefiners_.end()) {
        MIDDGNode* previousDefiner = lastPhysRegDefiners_[physReg];
        if (lastDefiner == NULL ||
            previousDefiner->sequentialAddress() >
            lastDefiner->sequentialAddress()) {
            lastDefiner = previousDefiner;            
        }
    }
    if (lastDefiner != NULL) {
        lastPhysRegDefiners_[physReg] = lastDefiner;
    }
 
    MIDDGNode* lastUser = NULL;
    if (lastPhysRegUsers_.find(physReg) != lastPhysRegUsers_.end()) {
        lastUser = lastPhysRegUsers_[physReg];
    }
 
    MIDDGNode* lastVregUser = this->lastVregUser(vreg);
    if (lastVregUser != NULL) {
        if (lastUser == NULL || 
            lastVregUser->sequentialAddress() > 
            lastUser->sequentialAddress()) {
            lastUser = lastVregUser;
        }
    }
    if (lastUser != NULL) {
        lastPhysRegUsers_[physReg] = lastUser;
    }
 
    std::pair<MIDDGNode*, MIDDGNode*> fdep = 
        createFalseDepEdge(vreg, physReg);
 
    if (fdep.first != NULL && fdep.second != NULL &&
        fdep.first != fdep.second) {
        MIDDGEdge* edge = new MIDDGEdge(physReg, MIDDGEdge::DEP_WAR);
        edges_.insert(edge);
#if 0
        Application::logStream()
            << "adding edge: " << edge->toString() << " from "
            << fdep.first->sequentialAddress() << " to "
            << fdep.second->sequentialAddress() << std::endl;
#endif
        connectNodes(*fdep.first, *fdep.second, *edge);
    }
}

References BoostGraph< MIDDGNode, MIDDGEdge >::connectNodes(), createFalseDepEdge(), MIDDGEdge::DEP_WAR, BoostGraph< MIDDGNode, MIDDGEdge >::edge(), edges_, lastPhysRegDefiners_, lastPhysRegUsers_, lastVregUser(), Application::logStream(), regAssignments_, MIDDGNode::sequentialAddress(), GraphEdge::toString(), and vregDefiner().

Here is the call graph for this function:

◆ computeOptimalSchedule()

void MachineInstrDDG::computeOptimalSchedule ( )

Computes optimal top-down schedule assuming infinite resources and that each operation completes in one cycle.

Definition at line 356 of file MachineInstrDDG.cc.

                                        {
    smallestCycle_ = 0;
    largestCycle_ = 0;
    schedule_.clear();
    for (int nc = 0; nc < nodeCount(); ++nc) {
        MIDDGNode& n = node(nc);
        int cycle = maxSourceDistance(n);
        n.setOptimalCycle(cycle);
        largestCycle_ = std::max(cycle, largestCycle_);
        schedule_[cycle].push_back(&n);
    }
}

References largestCycle_, BoostGraph< MIDDGNode, MIDDGEdge >::maxSourceDistance(), BoostGraph< MIDDGNode, MIDDGEdge >::node(), BoostGraph< MIDDGNode, MIDDGEdge >::nodeCount(), schedule_, MIDDGNode::setOptimalCycle(), and smallestCycle_.

Referenced by InstructionPatternAnalyzer::runOnMachineFunction().

Here is the call graph for this function:

◆ createFalseDepEdge()

std::pair< MIDDGNode , MIDDGNode > MachineInstrDDG::createFalseDepEdge	(	Register	vreg,
		Register	physReg
	)		const

private

Creates a false dependency edge introduced when the given virtual reg is assigned the given physical register.

Does not add the edge to the graph. Note, only creates a single edge although in a multi-BB DDG there is usually many in case edge spans CFG branch points. Returns a pair with NULLs in case no false dep is introduced.

Definition at line 202 of file MachineInstrDDG.cc.

                                                                         {
 
    MIDDGNode* null = NULL;
    std::pair<MIDDGNode*, MIDDGNode*> none = std::make_pair(null, null);
 
 
    if (lastPhysRegUsers_.find(physReg) == lastPhysRegUsers_.end()) {
        return none;
    }
 
    MIDDGNode* lastPhysRegUser = (*lastPhysRegUsers_.find(physReg)).second;
 
    if (this->vregDefiner(vreg) == NULL) {
        // could not find a definer for the given vreg, thus probably
        // a global register such as stack pointer, there won't be
        // many assignment possibilities for them anyways
        return none;
    }
    MIDDGNode* vregDefiner = this->vregDefiner(vreg);
    MIDDGNode* lastVregUser = this->lastVregUser(vreg);
 
    MIDDGNode* lastPhysRegDefiner = NULL;
    if (lastPhysRegDefiners_.find(physReg) != lastPhysRegDefiners_.end()) {
        lastPhysRegDefiner = (*lastPhysRegDefiners_.find(physReg)).second;
    }
 
    assert(vregDefiner != NULL);
 
    // the source and destination nodes for the introduced antidep
    MIDDGNode* source = NULL;
    MIDDGNode* dest = NULL;
 
    // the sequential instruction ordering defines the dep direction
    if (vregDefiner->sequentialAddress() > 
        lastPhysRegUser->sequentialAddress()) {
        source = lastPhysRegUser;
        dest = vregDefiner;
    } else {
        if (lastVregUser == NULL) {
            // only writes to the vreg, thus it would be WaW
            source = vregDefiner;
        } else {
            source = lastVregUser;
        }
 
        if (lastPhysRegDefiner != NULL) {
            dest = lastPhysRegDefiner;
        } else {
            dest = lastPhysRegUser;
        }
    }
 
    // ignore loop edges for now, but signal edges to itself as they are
    // cheap false deps which should be treated as such
    if (dest != source && hasPath(*dest, *source))
        return none; 
 
    return std::make_pair(source, dest);
}

References assert, BoostGraph< MIDDGNode, MIDDGEdge >::hasPath(), lastPhysRegDefiners_, lastPhysRegUsers_, lastVregUser(), MIDDGNode::sequentialAddress(), and vregDefiner().

Referenced by assignPhysReg(), and falseDepHeightDelta().

Here is the call graph for this function:

◆ dotString()

TCEString MachineInstrDDG::dotString ( ) const

virtual

Reimplemented from GraphBase< GraphNode, GraphEdge >.

Definition at line 370 of file MachineInstrDDG.cc.

                                 {
    std::ostringstream s;
    s << "digraph " << name() << " {" << std::endl;
 
    const bool scheduled = nodeCount() > 1 && node(0).optimalCycle() != -1;
    
    if (scheduled) {
        // print the "time line" to visualize the schedule
        s << "\t{" << std::endl
          << "\t\tnode [shape=plaintext];" << std::endl
          << "\t\t";
        const int smallest = smallestCycle_;
        const int largest = largestCycle_;
        for (int c = smallest; c <= largest; ++c) {
            s << "\"cycle " << c << "\" -> ";
        }
        s << "\"cycle " << largest + 1 << "\"; " 
          << std::endl << "\t}" << std::endl;
    
        // print the nodes that have cycles
        for (int c = smallest; c <= largest; ++c) {
            std::list<MIDDGNode*> ops = schedule_[c];
            if (ops.size() > 0) {
                s << "\t{ rank = same; \"cycle " << c << "\"; ";
                for (std::list<MIDDGNode*>::iterator i = ops.begin(); 
                     i != ops.end(); ++i) {
                    MIDDGNode& n = **i; 
                    if (n.osalOperationName() == "llvm::DBG_VALUE")
                        continue;
                    if (printOnlyCriticalPath_ && !isInCriticalPath(n))
                        continue;
                    s << "n" << n.nodeID() << "; ";
                }
                s << "}" << std::endl;
            }        
        }
 
 
        typedef std::map<TCEString, int> OpCountMap;
        // Count how many times each operation could be potentially
        // executed in parallel in an optimal schedule. This can direct
        // the intial architecture design.
        OpCountMap maxParallelOps;
        // The operation mix. I.e., the static occurence of operations
        // in the code.
        OpCountMap operationMix;
 
        for (int c = smallest; c <= largest; ++c) {
            std::list<MIDDGNode*> ops = schedule_[c];
            if (ops.size() == 0) continue;
 
            std::map<TCEString, int> parallelOpsAtCycle;
            for (std::list<MIDDGNode*>::iterator i = ops.begin(); 
                 i != ops.end(); ++i) {
                MIDDGNode& n = **i;        
                TCEString opName = n.osalOperationName();
                if (opName == "" || opName == "?jump") continue;
                operationMix[opName]++;
                parallelOpsAtCycle[opName]++;
            }
 
            for (OpCountMap::const_iterator i = parallelOpsAtCycle.begin();
                 i != parallelOpsAtCycle.end(); ++i) {
                TCEString opName = (*i).first;
                int count = (*i).second;
                maxParallelOps[opName] = 
                    std::max(maxParallelOps[opName], count);
            }
        }
 
        const int COL_WIDTH = 14;
        // print statistics of the graph as a comment
        s << "/* statistics: " << std::endl << std::endl;
        s << std::setw(COL_WIDTH) << std::right << "virtual regs: ";
        s << definers_.size() << std::endl << std::endl;
        s << std::setw(COL_WIDTH) << std::right << "operation stats: ";
        s << std::endl << std::endl;
        
        for (OpCountMap::const_iterator i = maxParallelOps.begin();
             i != maxParallelOps.end(); ++i) {
            TCEString opName = (*i).first;
            int parCount = (*i).second;
            int total = operationMix[opName];
            s << std::setw(COL_WIDTH) << std::right << opName + ": ";
            s << std::setw(COL_WIDTH) << std::right << total;
            s << " total, " << std::setw(COL_WIDTH) << std::right 
              << parCount << " at most in parallel" << std::endl;
        }
        s << "*/" << std::endl;
    }
    // first print all the nodes and their properties
    for (int i = 0; i < nodeCount(); ++i) {
        Node& n = node(i);
        if (n.osalOperationName() == "llvm::DBG_VALUE")
            continue;
        if (printOnlyCriticalPath_ && !isInCriticalPath(n))
            continue;
 
        s << "\tn" << n.nodeID()
          << " [" << n.dotString();
        if (isInCriticalPath(n))
            s << ",shape=box,color=\"red\"";
        s  << "]; " << std::endl;
    }
 
    // edges
    for (int count = edgeCount(), i = 0; i < count ; ++i) {
        Edge& e = edge(i);
        Node& tail = tailNode(e);
        Node& head = headNode(e);
 
        if (printOnlyCriticalPath_ && !isInCriticalPath(tail) &&
            !isInCriticalPath(head))
            continue;
 
        s << "\tn" << tail.nodeID() << " -> n" 
          << head.nodeID() << "[" 
          << e.dotString();
        if (isInCriticalPath(tail) && isInCriticalPath(head))
            s << ",color=red";
        s << "];" << std::endl;
    }
 
    s << "}" << std::endl;   
 
    return s.str();    
 
}

Here is the call graph for this function:

◆ falseDepHeightDelta()

int MachineInstrDDG::falseDepHeightDelta	(	Register	vreg,
		Register	physReg
	)		const

Returns the "height delta" of an antidep edge created in case the given virtual register is assigned the given physical register.

Height delta is the difference between the DDG height of the source definer node and the DDG height of the latest read node of the physReg. The direction of the introduced false dep edge is determined from the sequential instruction order, direction is assumed to be from the earlier instruction to the later. Thus, an edge with 0 or greater height dep potentially constraints the schedule by potentially heightening the DDG. However, this is not generally the case in case the critical path length is not increased by the assignment.

Parameters

vreg	The virtual register to test.
physReg	The physical register assigment to test.

Returns: The height delta of the false dep from the assignment, or INT_MIN in case no false dep would be produced.

Definition at line 281 of file MachineInstrDDG.cc.

                                                                          {
 
    std::pair<MIDDGNode*, MIDDGNode*> fdep = 
        createFalseDepEdge(vreg, physReg);
 
    int hdelta = INT_MIN;
    if (fdep.first != NULL && fdep.second != NULL) {
        if (fdep.first == fdep.second)
            return -1; // treat fdep to itself as the least harmful one
        hdelta = 
            maxSourceDistance(*fdep.first) - maxSourceDistance(*fdep.second);
    }
    return hdelta;
}

References createFalseDepEdge(), and BoostGraph< MIDDGNode, MIDDGEdge >::maxSourceDistance().

Here is the call graph for this function:

◆ lastVregUser()

MIDDGNode * MachineInstrDDG::lastVregUser ( Register vreg ) const

Definition at line 297 of file MachineInstrDDG.cc.

                                                 {
    int lastUse = -1;
    MIDDGNode* lastUser = NULL;
    if (users_.find(vreg) == users_.end())
        return NULL;
 
    NodeSet& users = (*users_.find(vreg)).second;
    for (NodeSet::const_iterator i = users.begin(); i != users.end(); 
         ++i) {
        MIDDGNode* node = *i;
        if (lastUse < node->sequentialAddress()) {
            lastUse = node->sequentialAddress();
            lastUser = node;
        }
    }
    return lastUser;
}

References BoostGraph< MIDDGNode, MIDDGEdge >::node(), and users_.

Referenced by assignPhysReg(), and createFalseDepEdge().

Here is the call graph for this function:

◆ preceedingNodeUsesOrDefinesReg()

bool MachineInstrDDG::preceedingNodeUsesOrDefinesReg	(	const MIDDGNode &	node,
		Register	physReg
	)		const

Checks if there is at least one preceeding node to the given node that defines or uses the given physical register.

Also the uses in the same node are considered.

Definition at line 322 of file MachineInstrDDG.cc.

                                                   {
 
    NodeSet pred = predecessors(node);
    pred.insert(const_cast<MIDDGNode*>(&node));
    for (NodeSet::const_iterator i = pred.begin(); i != pred.end(); ++i) {
        MIDDGNode& p = (**i);
        const llvm::MachineInstr* instr = p.machineInstr();
        for (unsigned operand = 0; operand < instr->getNumOperands(); 
             ++operand) {
            const llvm::MachineOperand& mo = instr->getOperand(operand);
            if (!mo.isReg())
                continue;
            if (mo.getReg() == physReg ||
                (regAssignments_.find(mo.getReg()) != regAssignments_.end() &&
                 (*regAssignments_.find(mo.getReg())).second == physReg)) {
                return true;
            }
        }
        
        if (instr->readsRegister(physReg) || 
            instr->modifiesRegister(physReg, regInfo_)) {
            return true;
        } 
    }
    return false;
}

References MIDDGNode::machineInstr(), BoostGraph< MIDDGNode, MIDDGEdge >::node(), BoostGraph< MIDDGNode, MIDDGEdge >::predecessors(), regAssignments_, and regInfo_.

Here is the call graph for this function:

◆ setPrintOnlyCriticalPath()

void MachineInstrDDG::setPrintOnlyCriticalPath ( bool flag )

inline

Definition at line 170 of file MachineInstrDDG.hh.

170{ printOnlyCriticalPath_ = flag; }

References printOnlyCriticalPath_.

Referenced by InstructionPatternAnalyzer::runOnMachineFunction().

◆ vregDefiner()

MIDDGNode * MachineInstrDDG::vregDefiner ( Register vreg ) const

inline

Definition at line 156 of file MachineInstrDDG.hh.

156{ return definers_[vreg]; };

References definers_.

Referenced by assignPhysReg(), createFalseDepEdge(), and VirtRegIndependenceGraph::VirtRegIndependenceGraph().

Member Data Documentation

◆ allRegisters_

RegisterSet MachineInstrDDG::allRegisters_

private

Definition at line 181 of file MachineInstrDDG.hh.

Referenced by allRegisters(), and MachineInstrDDG().

◆ definers_

DefinerMap MachineInstrDDG::definers_

mutableprivate

Definition at line 183 of file MachineInstrDDG.hh.

Referenced by dotString(), MachineInstrDDG(), and vregDefiner().

◆ edges_

std::set<MIDDGEdge*> MachineInstrDDG::edges_

private

Definition at line 187 of file MachineInstrDDG.hh.

Referenced by assignPhysReg(), and MachineInstrDDG().

◆ largestCycle_

int MachineInstrDDG::largestCycle_

private

Definition at line 197 of file MachineInstrDDG.hh.

Referenced by computeOptimalSchedule(), and dotString().

◆ lastPhysRegDefiners_

std::map<Register, MIDDGNode*> MachineInstrDDG::lastPhysRegDefiners_

private

Definition at line 189 of file MachineInstrDDG.hh.

Referenced by assignPhysReg(), and createFalseDepEdge().

◆ lastPhysRegUsers_

std::map<Register, MIDDGNode*> MachineInstrDDG::lastPhysRegUsers_

private

Definition at line 188 of file MachineInstrDDG.hh.

Referenced by assignPhysReg(), and createFalseDepEdge().

◆ mf_

llvm::MachineFunction& MachineInstrDDG::mf_

private

Definition at line 200 of file MachineInstrDDG.hh.

◆ nodes_

NodeSet MachineInstrDDG::nodes_

private

Definition at line 186 of file MachineInstrDDG.hh.

Referenced by MachineInstrDDG().

◆ onlyTrueDeps_

const bool MachineInstrDDG::onlyTrueDeps_

private

Definition at line 193 of file MachineInstrDDG.hh.

◆ printOnlyCriticalPath_

bool MachineInstrDDG::printOnlyCriticalPath_

private

Definition at line 203 of file MachineInstrDDG.hh.

Referenced by dotString(), and setPrintOnlyCriticalPath().

◆ regAssignments_

RegisterMap MachineInstrDDG::regAssignments_

private

Definition at line 190 of file MachineInstrDDG.hh.

Referenced by assignPhysReg(), and preceedingNodeUsesOrDefinesReg().

◆ regInfo_

const llvm::TargetRegisterInfo* MachineInstrDDG::regInfo_

private

Definition at line 201 of file MachineInstrDDG.hh.

Referenced by preceedingNodeUsesOrDefinesReg().

◆ schedule_

std::map<int, std::list<MIDDGNode*> > MachineInstrDDG::schedule_

mutableprivate

Definition at line 198 of file MachineInstrDDG.hh.

Referenced by computeOptimalSchedule(), and dotString().

◆ smallestCycle_

int MachineInstrDDG::smallestCycle_

private

Definition at line 196 of file MachineInstrDDG.hh.

Referenced by computeOptimalSchedule(), and dotString().

◆ users_

UserMap MachineInstrDDG::users_

mutableprivate

Definition at line 184 of file MachineInstrDDG.hh.

Referenced by lastVregUser(), and MachineInstrDDG().

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

Public Types

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ DefinerMap

◆ Register

◆ RegisterMap

◆ RegisterSet

◆ UserMap

Constructor & Destructor Documentation

◆ MachineInstrDDG() [1/2]

◆ MachineInstrDDG() [2/2]

◆ ~MachineInstrDDG()

Member Function Documentation

◆ allRegisters()

◆ assignPhysReg()

◆ computeOptimalSchedule()

◆ createFalseDepEdge()

◆ dotString()

◆ falseDepHeightDelta()

◆ lastVregUser()

◆ preceedingNodeUsesOrDefinesReg()

◆ setPrintOnlyCriticalPath()

◆ vregDefiner()

Member Data Documentation

◆ allRegisters_

◆ definers_

◆ edges_

◆ largestCycle_

◆ lastPhysRegDefiners_

◆ lastPhysRegUsers_

◆ mf_

◆ nodes_

◆ onlyTrueDeps_

◆ printOnlyCriticalPath_

◆ regAssignments_

◆ regInfo_

◆ schedule_

◆ smallestCycle_

◆ users_