#include <VirtRegIndependenceGraph.hh>

Collaboration diagram for VirtRegIndependenceGraph:

Public Member Functions
	VirtRegIndependenceGraph (llvm::MachineFunction &mf, llvm::VirtRegMap &vrm)

int	newFalseDepsFromAssign (llvm::LiveInterval *interval, MachineInstrDDG::Register physReg)

void	addNode (MachineInstrDDG::Register virtReg)

void	addEdge (MachineInstrDDG::Register nodeA, MachineInstrDDG::Register nodeB)

std::set< MachineInstrDDG::Register >	adjacentNodes (MachineInstrDDG::Register node)

Private Types
typedef boost::adjacency_list< boost::vecS, boost::vecS, boost::undirectedS, boost::property< boost::vertex_name_t, MachineInstrDDG::Register > >	FDPG

Private Attributes
llvm::VirtRegMap &	vrm_

FDPG	fdpg_

std::map< MachineInstrDDG::Register, FDPG::vertex_descriptor >	vertexMap_

std::map< FDPG::vertex_descriptor, MachineInstrDDG::Register >	vregMap_

Detailed Description

Virtual register independence graph AKA False Dependence Prevention Graph (FDPG).

Nodes in the graph are virtual registers. They have edges between if the live ranges could be scheduled in parallel or reordered if there were no false dependencies. In other words, two virtual registers / live ranges / variables are considered independent in case they do not have real data dependencies between them.

Todo:: This approach has at least the following unsolved problems:

The data is not updated during the register allocation. In case a register needed to be shared and an false dep was added, the independence graph does not reflect this new dependence. This results in too greedy assignments because register sharing might not hurt after one register sharing has added a new antidependence. The DDG height delta-based allocator helped for this.
Actual schedulability is not taken in account. Even in case the nodes were independent, they could have min cycles such that it forces the ordering anyways. For example, a branch in DDG with node N1 of height 4 and another independent branch with node N2 with height 2. N1 cannot be scheduled above N2 anyhow, regardless if there was an extra N2->N1 edge or not due to the register sharing. Currently the FDPG method blindly avoids sharing the reg between N2 and N1, thus increasing the register pressure for no benefit.
Memory dependencies are not taken in account. This results in a too free DDG thus too many falsely independent live ranges, ending with a too greedy allocation.

Definition at line 80 of file VirtRegIndependenceGraph.hh.

Member Typedef Documentation

◆ FDPG

typedef boost::adjacency_list< boost::vecS, boost::vecS, boost::undirectedS, boost::property<boost::vertex_name_t, MachineInstrDDG::Register> > VirtRegIndependenceGraph::FDPG

private

Definition at line 99 of file VirtRegIndependenceGraph.hh.

Constructor & Destructor Documentation

◆ VirtRegIndependenceGraph()

VirtRegIndependenceGraph::VirtRegIndependenceGraph	(	llvm::MachineFunction &	mf,
		llvm::VirtRegMap &	vrm
	)

Constructs the graph from an LLVM MachineFunction.

Definition at line 46 of file VirtRegIndependenceGraph.cc.

                                                  :
    vrm_(vrm) {
 
    MachineInstrDDG tddg(*vrm.TII, *vrm.TRI, mf,  true); 
    MachineInstrDDG::RegisterSet regs = tddg.allRegisters();
#ifdef DEBUG_FDPG    
    Application::logStream() << "building FDPG" << std::endl;
#endif
    // add the virtual regs as nodes 
    for (MachineInstrDDG::RegisterSet::const_iterator i = regs.begin(); 
         i != regs.end(); ++i) {
        MachineInstrDDG::Register reg = *i;
 
        if (llvm::TargetRegisterInfo::isPhysicalRegister(reg)) 
            continue;
 
        addNode(reg);
    }
 
#ifdef DEBUG_FDPG
    Application::logStream() << "finding TDDG paths" << std::endl;
#endif
    // this should speed up hasPath() as all known paths are
    // computed only once
    tddg.findAllPaths();
#ifdef DEBUG_FDPG
    Application::logStream() << "finding TDDG paths done" << std::endl;
#endif
    MachineInstrDDG::RegisterSet unhandledRegs = regs;
    for (MachineInstrDDG::RegisterSet::const_iterator i = regs.begin(); 
         i != regs.end(); ++i) {
        MachineInstrDDG::Register reg = *i;
        MIDDGNode* instrA = tddg.vregDefiner(reg);
        for (MachineInstrDDG::RegisterSet::const_iterator u = 
                 unhandledRegs.begin(); 
             u != unhandledRegs.end(); ++u) {
            MachineInstrDDG::Register otherReg = *u;
            MIDDGNode* instrB = tddg.vregDefiner(otherReg);
            if (instrB == NULL) {
                Application::logStream() 
                    << "could not find definer for " << otherReg << std::endl;
                abortWithError("Cannot proceed.");
            }
            if (!tddg.hasPath(*instrA, *instrB) &&
                !tddg.hasPath(*instrB, *instrA)) {
                addEdge(reg, otherReg);
            }
        }
        unhandledRegs.erase(reg);
    }
#ifdef DEBUG_FDPG
    Application::logStream() << "building FDPG done" << std::endl;
#endif
#if 0
    // this is exremely slow as there are often huge number of edges in FDPG
    std::string s(mf.getFunction()->getNameStr() + "_fdpg.dot");
    std::ofstream o(s.c_str());
    boost::write_graphviz(
        o, fdpg_, make_label_writer(get(boost::vertex_name, fdpg_)));
#endif
}

References abortWithError, addEdge(), addNode(), MachineInstrDDG::allRegisters(), fdpg_, BoostGraph< GraphNode, GraphEdge >::findAllPaths(), BoostGraph< GraphNode, GraphEdge >::hasPath(), Application::logStream(), and MachineInstrDDG::vregDefiner().

Here is the call graph for this function:

Member Function Documentation

◆ addEdge()

void VirtRegIndependenceGraph::addEdge	(	MachineInstrDDG::Register	nodeA,
		MachineInstrDDG::Register	nodeB
	)

Definition at line 149 of file VirtRegIndependenceGraph.cc.

                                                                  {
    boost::add_edge(vertexMap_[nodeA], vertexMap_[nodeB], fdpg_);
}

References fdpg_, and vertexMap_.

Referenced by VirtRegIndependenceGraph().

◆ addNode()

void VirtRegIndependenceGraph::addNode ( MachineInstrDDG::Register virtReg )

Definition at line 142 of file VirtRegIndependenceGraph.cc.

                                                                 {    
    vertexMap_[virtReg] = boost::add_vertex(fdpg_);
    vregMap_[vertexMap_[virtReg]] = virtReg;
    boost::put(boost::vertex_name, fdpg_, vertexMap_[virtReg], virtReg);
}

References fdpg_, vertexMap_, and vregMap_.

Referenced by VirtRegIndependenceGraph().

◆ adjacentNodes()

std::set< MachineInstrDDG::Register > VirtRegIndependenceGraph::adjacentNodes ( MachineInstrDDG::Register node )

Definition at line 155 of file VirtRegIndependenceGraph.cc.

                                                                    {
    std::set<MachineInstrDDG::Register> nodes;
 
    boost::graph_traits<FDPG>::adjacency_iterator i, end;
    i = boost::adjacent_vertices(vertexMap_[node], fdpg_).first;
    end = boost::adjacent_vertices(vertexMap_[node], fdpg_).second;
    for (; i != end; ++i) {
        MachineInstrDDG::Register virtReg = vregMap_[*i];
        nodes.insert(virtReg);
    }
 
    return nodes;
}

References fdpg_, vertexMap_, and vregMap_.

Referenced by newFalseDepsFromAssign().

◆ newFalseDepsFromAssign()

int VirtRegIndependenceGraph::newFalseDepsFromAssign	(	llvm::LiveInterval *	interval,
		MachineInstrDDG::Register	physReg
	)

Returns the number of new false deps introduced by assigning the given physical register to the given live interval.

Definition at line 114 of file VirtRegIndependenceGraph.cc.

                                                                 {
 
    if (llvm::TargetRegisterInfo::isPhysicalRegister(interval->reg)) {
        Application::logStream() 
            << "Should not see assigned intervals here. Got: " 
            << interval->reg
            << std::endl;
        return true;
    }
 
    // look at all connected live Intervals in the FDPG and see if they have
    // been assigned the same PhysReg we are trying to assign this one
 
    int foundFalseDeps = 0;
    std::set<MachineInstrDDG::Register> adjacent = adjacentNodes(interval->reg);
    for (std::set<MachineInstrDDG::Register>::const_iterator i = 
             adjacent.begin(); i != adjacent.end(); ++i) {
        MachineInstrDDG::Register virtReg = *i;
        bool isPhysRegAssigned = vrm_.hasPhys(virtReg);
        if (isPhysRegAssigned && vrm_.getPhys(virtReg) == physReg) {
            ++foundFalseDeps;
        }
    }
    return foundFalseDeps;
}