RegisterRenamer Class Reference

#include <RegisterRenamer.hh>

Collaboration diagram for RegisterRenamer:

Public Types
typedef std::set< const TTAMachine::RegisterFile *, TTAMachine::MachinePart::Comparator >	RegisterFileSet

Public Member Functions
	RegisterRenamer (const TTAMachine::Machine &machine, TTAProgram::BasicBlock &bb)
unsigned int	freeGPRCount () const
void	initialize (DataDependenceGraph &ddg)
bool	renameDestinationRegister (MoveNode &node, bool loopScheduling, bool allowSameRf, bool differentRfOnlyDirectlyReachable, int earliestCycle=-1)
bool	renameSourceRegister (MoveNode &node, bool loopScheduling, bool allowSameRf, bool differentRfOnlyDirectlyReachable, int latestCycle=INT_MAX)
void	setSelector (MoveNodeSelector *selector)
bool	renameLiveRange (LiveRange &liveRange, const TCEString &newReg, bool usedBefore, bool usedAfter, bool loopScheduling)
std::set< TCEString >	findPartiallyUsedRegistersAfterCycle (int bitWidth, int latestCycle) const
std::set< TCEString >	findFreeRegisters (int bitWidth) const
std::set< TCEString >	findPartiallyUsedRegistersInRFAfterCycle (const RegisterFileSet &rfs, int latestCycle) const
std::set< TCEString >	findFreeRegistersInRF (const RegisterFileSet &rfs) const
RegisterFileSet	findConnectedRFs (LiveRange &lr, bool allowLimm)
TTAProgram::BasicBlock &	bb ()
void	renamedToRegister (const TCEString &newReg)
void	revertedRenameToRegister (const TCEString &reg)

Private Member Functions
std::set< TCEString >	registersOfRFs (const RegisterFileSet &rfs) const
void	initializeFreeRegisters ()
std::set< TCEString >	findPartiallyUsedRegistersInRFBeforeCycle (const RegisterFileSet &rfs, int earliestCycle, const DataDependenceGraph::NodeSet &guardMoves) const
std::set< TCEString >	findPartiallyUsedRegistersBeforeCycle (int bitWidth, int earliestCycle, const DataDependenceGraph::NodeSet &guardMoves) const
std::set< TCEString >	findFreeGuardRegisters (const DataDependenceGraph::NodeSet &guardUseNodes, int bitWidth, const RegisterFileSet &rfs) const
std::set< TCEString >	findGuardRegisters (const DataDependenceGraph::NodeSet &guardMoves, const RegisterFileSet &rfs) const
std::set< TCEString >	findGuardRegisters (const TTAMachine::Bus &bus, const RegisterFileSet &rfs) const
void	updateAntiEdgesFromLRTo (LiveRange &liveRange, const TCEString &newReg, TTAProgram::BasicBlock &bb, int loopDepth) const
void	initialize ()

Private Attributes
std::set< TCEString >	allNormalGPRs_
std::set< TCEString >	freeGPRs_
std::set< TCEString >	usedGPRs_
std::set< TCEString >	onlyBeginPartiallyUsedRegs_
std::set< TCEString >	onlyEndPartiallyUsedRegs_
std::set< TCEString >	onlyMidPartiallyUsedRegs_
std::set< const TTAMachine::RegisterFile *, TTAMachine::MachinePart::Comparator >	tempRegFiles_
const TTAMachine::Machine &	machine_
TTAProgram::BasicBlock &	bb_
DataDependenceGraph *	ddg_
MoveNodeSelector *	selector_

Static Private Attributes
static std::map< const TTAMachine::Machine *, std::set< const TTAMachine::RegisterFile *, TTAMachine::MachinePart::Comparator > >	tempRegFileCache_
	To avoid reanalysing machine every time hen new rr created.

Detailed Description

Definition at line 59 of file RegisterRenamer.hh.

Member Typedef Documentation

RegisterFileSet

typedef std::set<const TTAMachine::RegisterFile*, TTAMachine::MachinePart::Comparator> RegisterRenamer::RegisterFileSet

Definition at line 62 of file RegisterRenamer.hh.

Constructor & Destructor Documentation

RegisterRenamer()

RegisterRenamer::RegisterRenamer	(	const TTAMachine::Machine &	machine,
		TTAProgram::BasicBlock &	bb
	)

Constructor.

Parameters

machine

machine for which we are scheudling

RegisterRenamer::RegisterRenamer(const TTAMachine::Machine& machine) : machine_(machine) { initialize(); } Constructor.

Parameters

machine

machine for which we are scheudling

Definition at line 74 of file RegisterRenamer.cc.

                                                                :
    machine_(machine), bb_(bb), ddg_(NULL){
    initialize();
}

References initialize().

Here is the call graph for this function:

Member Function Documentation

bb()

TTAProgram::BasicBlock & RegisterRenamer::bb ( )

inline

Definition at line 102 of file RegisterRenamer.hh.

{ return bb_; }

References bb_.

Referenced by BFRenameLiveRange::operator()(), and updateAntiEdgesFromLRTo().

findConnectedRFs()

RegisterRenamer::RegisterFileSet RegisterRenamer::findConnectedRFs	(	LiveRange &	lr,
		bool	allowLimm
	)

Definition at line 1206 of file RegisterRenamer.cc.

                                                               {
 
    assert(!lr.writes.empty());
    TTAMachine::RegisterFile* originalRF = 
        dynamic_cast<TTAMachine::RegisterFile*>(
            (*lr.writes.begin())->move().destination().port().parentUnit());
    assert(originalRF != 0);
    int bitwidth = originalRF->width();
    std::set<const TTAMachine::RegisterFile*, 
        TTAMachine::MachinePart::Comparator> rv;
 
    // TODO: loop over movenoeds or RF's? this routine could be made faster.
    TTAMachine::Machine::RegisterFileNavigator rfNav = 
        machine_.registerFileNavigator();
    for (int i = 0; i < rfNav.count(); i++) {
        TTAMachine::RegisterFile* rf = rfNav.item(i);
        if (rf->width() != bitwidth) {
            continue;
        }
        MachineConnectivityCheck::PortSet writePorts = 
            MachineConnectivityCheck::findWritePorts(*rf);
        bool connected = true;
        
        for (DataDependenceGraph::NodeSet::iterator j = lr.writes.begin();
             j != lr.writes.end() && connected; j++) {
            const MoveNode& write = **j;
            switch (MachineConnectivityCheck::canSourceWriteToAnyDestinationPort(
                        write, writePorts)) {
            case -1:
                connected = allowLimm;
                break;
            case 0:
                connected = false;
            default:
                break;
            }
        }
        if (!connected) {
            continue;
        }
        
        MachineConnectivityCheck::PortSet readPorts = 
            MachineConnectivityCheck::findReadPorts(*rf);
        
        for (DataDependenceGraph::NodeSet::iterator j = lr.reads.begin();
             j != lr.reads.end() && connected; j++) {
            const MoveNode& read = **j;
            if (!MachineConnectivityCheck::canAnyPortWriteToDestination(
                    readPorts, read)) {
                connected = false;
            }
        }
        if (connected) {
            rv.insert(rf);
        }
    }
    return rv;
}

References assert, MachineConnectivityCheck::canAnyPortWriteToDestination(), MachineConnectivityCheck::canSourceWriteToAnyDestinationPort(), TTAMachine::Machine::Navigator< ComponentType >::count(), MachineConnectivityCheck::findReadPorts(), MachineConnectivityCheck::findWritePorts(), TTAMachine::Machine::Navigator< ComponentType >::item(), machine_, LiveRange::reads, TTAMachine::Machine::registerFileNavigator(), TTAMachine::BaseRegisterFile::width(), and LiveRange::writes.

Referenced by BFRenameLiveRange::operator()(), renameDestinationRegister(), and renameSourceRegister().

Here is the call graph for this function:

findFreeGuardRegisters()

std::set< TCEString > RegisterRenamer::findFreeGuardRegisters ( const DataDependenceGraph::NodeSet &  guardUseNodes, int  bitWidth, const RegisterFileSet &  rfs  ) const

private

Definition at line 437 of file RegisterRenamer.cc.

                                                    {
    std::set<TCEString> availableRegs;
 
    SetTools::intersection(
        (rfs.empty() ?
         findFreeRegisters(bitWidth) :
         findFreeRegistersInRF(rfs)),
        findGuardRegisters(guardUseNodes, rfs),
        availableRegs);
    
    return availableRegs;
}

References findFreeRegisters(), findFreeRegistersInRF(), findGuardRegisters(), and SetTools::intersection().

Referenced by renameDestinationRegister().

Here is the call graph for this function:

findFreeRegisters()

std::set< TCEString > RegisterRenamer::findFreeRegisters

(

int

bitWidth

)

const

Definition at line 418 of file RegisterRenamer.cc.

                        {
 
    std::set<TCEString> availableRegs;
 
    for (std::set<TCEString>::iterator i = freeGPRs_.begin(); 
         i != freeGPRs_.end(); i++) {
 
        TCEString rfName = i->substr(0, i->find('.'));
        TTAMachine::RegisterFile* rf = 
            machine_.registerFileNavigator().item(rfName);
        if (rf->width() == bitWidth) {
            availableRegs.insert(*i);
        }
    }
    return availableRegs;
}

References freeGPRs_, TTAMachine::Machine::Navigator< ComponentType >::item(), machine_, TTAMachine::Machine::registerFileNavigator(), and TTAMachine::BaseRegisterFile::width().

Referenced by findFreeGuardRegisters(), renameDestinationRegister(), and renameSourceRegister().

Here is the call graph for this function:

findFreeRegistersInRF()

std::set< TCEString > RegisterRenamer::findFreeRegistersInRF

(

const RegisterFileSet &

rfs

)

const

Definition at line 223 of file RegisterRenamer.cc.

                                                     {
 
    std::set<TCEString> allowedGprs = registersOfRFs(rfs);
    std::set<TCEString> regs;
    SetTools::intersection(allowedGprs, freeGPRs_, regs);
    return regs;
}

References freeGPRs_, SetTools::intersection(), and registersOfRFs().

Referenced by findFreeGuardRegisters(), BFRenameLiveRange::operator()(), renameDestinationRegister(), and renameSourceRegister().

Here is the call graph for this function:

findGuardRegisters() [1/2]

std::set< TCEString > RegisterRenamer::findGuardRegisters ( const DataDependenceGraph::NodeSet &  guardMoves, const RegisterFileSet &  rfs  ) const

private

Definition at line 1270 of file RegisterRenamer.cc.

                                      {
 
 
    TTAMachine::Bus* bus = NULL;
    for (DataDependenceGraph::NodeSet::iterator i = guardMoves.begin();
         i != guardMoves.end(); i++) {
        const MoveNode& mn = **i;
        const TTAProgram::Move& move = mn.move();
        assert(!move.isUnconditional());
        if (bus == NULL) {
            bus = move.guard().guard().parentBus();
        } else {
            TTAMachine::Bus* bus2 = move.guard().guard().parentBus();
            if (bus != bus2) {
                return std::set<TCEString>();
            }
        }
    }
 
    if (bus != NULL) {
        return findGuardRegisters(*bus, rfs);
    } else {
        return std::set<TCEString>();
    }
}

References assert, findGuardRegisters(), TTAProgram::Move::guard(), TTAProgram::MoveGuard::guard(), TTAProgram::Move::isUnconditional(), MoveNode::move(), and TTAMachine::Guard::parentBus().

Referenced by findFreeGuardRegisters(), findGuardRegisters(), findPartiallyUsedRegistersBeforeCycle(), and findPartiallyUsedRegistersInRFBeforeCycle().

Here is the call graph for this function:

findGuardRegisters() [2/2]

std::set< TCEString > RegisterRenamer::findGuardRegisters ( const TTAMachine::Bus &  bus, const RegisterFileSet &  rfs  ) const

private

Finds registers which can guard moves from the given bus.

Definition at line 1302 of file RegisterRenamer.cc.

                                                                {
    
    std::set<TCEString> trueGuards;
    std::set<TCEString> falseGuards;
 
    // find guard
    for (int i = 0 ; i < bus.guardCount(); i++) {
        TTAMachine::Guard *g = bus.guard(i);
        TTAMachine::RegisterGuard* rg =
            dynamic_cast<TTAMachine::RegisterGuard*>(g);
        if (rg) {
            bool rfOk = true;
            if (!rfs.empty()) {
                if (rfs.find(rg->registerFile()) == rfs.end()) {
                    rfOk = false;
                    continue;
                }
            }
            
            if (rfOk) {
                if (rg->isInverted()) {
                    falseGuards.insert(
                        DisassemblyRegister::registerName(
                            *rg->registerFile(), rg->registerIndex()));
                } else {
                    trueGuards.insert(
                        DisassemblyRegister::registerName(
                            *rg->registerFile(), rg->registerIndex()));
                }
            }
        }
    }
 
    for (std::set<TCEString>::iterator i = trueGuards.begin();
         i != trueGuards.end(); i++) {
        if (falseGuards.find(*i) == falseGuards.end()) {
            trueGuards.erase(i);
            i = trueGuards.begin();
        }
    }
    return trueGuards;
}

References TTAMachine::Bus::guard(), TTAMachine::Bus::guardCount(), TTAMachine::Guard::isInverted(), TTAMachine::RegisterGuard::registerFile(), TTAMachine::RegisterGuard::registerIndex(), and DisassemblyRegister::registerName().

Here is the call graph for this function:

findPartiallyUsedRegistersAfterCycle()

std::set< TCEString > RegisterRenamer::findPartiallyUsedRegistersAfterCycle	(	int	bitWidth,
		int	latestCycle
	)		const

Definition at line 394 of file RegisterRenamer.cc.

                                         {
    std::set<TCEString> availableRegs;
 
    std::set<TCEString> regs = onlyMidPartiallyUsedRegs_;
    AssocTools::append(onlyEndPartiallyUsedRegs_, regs);
    AssocTools::append(usedGPRs_, regs);
 
    for (std::set<TCEString>::iterator i = regs.begin(); 
         i != regs.end(); i++) {
 
        TCEString rfName = i->substr(0, i->find('.'));
        TTAMachine::RegisterFile* rf = 
            machine_.registerFileNavigator().item(rfName);
        unsigned int regIndex = atoi(i->substr(i->find('.')+1).c_str());
        if (ddg_->firstRegisterCycle(*rf, regIndex) > latestCycle && 
            rf->width() == bitWidth) {
            availableRegs.insert(*i);
        }
    }
    return availableRegs;
}

References AssocTools::append(), ddg_, DataDependenceGraph::firstRegisterCycle(), TTAMachine::Machine::Navigator< ComponentType >::item(), machine_, onlyEndPartiallyUsedRegs_, onlyMidPartiallyUsedRegs_, TTAMachine::Machine::registerFileNavigator(), usedGPRs_, and TTAMachine::BaseRegisterFile::width().

Referenced by renameSourceRegister().

Here is the call graph for this function:

findPartiallyUsedRegistersBeforeCycle()

std::set< TCEString > RegisterRenamer::findPartiallyUsedRegistersBeforeCycle ( int  bitWidth, int  earliestCycle, const DataDependenceGraph::NodeSet &  guardMoves  ) const

private

Definition at line 341 of file RegisterRenamer.cc.

                                                        {
    std::set<TCEString> availableRegs;
    // nothing can be scheduled earlier than cycle 0.
    // in that case we have empty set, no need to check.
    if (earliestCycle < 1) {
        return availableRegs;
    }
 
    std::set<TCEString> regs = onlyMidPartiallyUsedRegs_;
    AssocTools::append(onlyBeginPartiallyUsedRegs_, regs);
    AssocTools::append(usedGPRs_, regs);
 
    for (std::set<TCEString>::iterator i = regs.begin(); 
         i != regs.end(); i++) {
 
        TCEString rfName = i->substr(0, i->find('.'));
        TTAMachine::RegisterFile* rf = 
            machine_.registerFileNavigator().item(rfName);
        unsigned int regIndex = atoi(i->substr(i->find('.')+1).c_str());
        if (ddg_->lastRegisterCycle(*rf, regIndex) < earliestCycle && 
            rf->width() == bitWidth) {
            availableRegs.insert(*i);
        }
    }
    // if need to have guards?
    if (guardMoves.empty()) {
        return availableRegs;        
    } else {
#ifdef DEBUG_REGISTER_RENAMER
        if (!liveRange->guards.empty()) {
            std::cerr << "\t\t\t\tpartiallyusedregs: ";
            for (std::set<TCEString>::iterator i = 
                     regs.begin();
                 i != regs.end(); i++) {
                std::cerr << *i << " ";
            }
            std::cerr << std::endl;
        }
#endif
 
        RegisterFileSet rfs; // empty, all rf's
        std::set<TCEString> guardedRegs = 
            findGuardRegisters(guardMoves, rfs);
        std::set<TCEString> guardedAvailableRegs;
        SetTools::intersection(
            availableRegs, guardedRegs, guardedAvailableRegs);
        return guardedAvailableRegs;
    }
}

References AssocTools::append(), ddg_, findGuardRegisters(), SetTools::intersection(), TTAMachine::Machine::Navigator< ComponentType >::item(), DataDependenceGraph::lastRegisterCycle(), machine_, onlyBeginPartiallyUsedRegs_, onlyMidPartiallyUsedRegs_, TTAMachine::Machine::registerFileNavigator(), usedGPRs_, and TTAMachine::BaseRegisterFile::width().

Referenced by renameDestinationRegister().

Here is the call graph for this function:

findPartiallyUsedRegistersInRFAfterCycle()

std::set< TCEString > RegisterRenamer::findPartiallyUsedRegistersInRFAfterCycle	(	const RegisterFileSet &	rfs,
		int	latestCycle
	)		const

Finds registers which are used but only after given earliestCycle.

Definition at line 310 of file RegisterRenamer.cc.

                                                                      {
 
    std::set<TCEString> availableRegs;
    // nothing can be scheduled earlier than cycle 0.
    // in that case we have empty set, no need to check.
 
    std::set<TCEString> allowedGprs = registersOfRFs(rfs);
    std::set<TCEString> regs = usedGPRs_;
    AssocTools::append(onlyEndPartiallyUsedRegs_, regs);
    AssocTools::append(onlyMidPartiallyUsedRegs_, regs);
    std::set<TCEString> regs2;
    SetTools::intersection(allowedGprs, regs, regs2);
    
    // find from used gprs.
    // todo: this is too conservative? leaves one cycle netween war?
    for (std::set<TCEString>::iterator i = regs2.begin(); 
         i != regs2.end(); i++) {
        TCEString rfName = i->substr(0, i->find('.'));
        TTAMachine::RegisterFile* rf = 
            machine_.registerFileNavigator().item(rfName);
 
        unsigned int regIndex = atoi(i->substr(i->find('.')+1).c_str());
        if (ddg_->firstRegisterCycle(*rf, regIndex) > latestCycle) {
            availableRegs.insert(*i);
        }
    }
    return availableRegs;
}

References AssocTools::append(), ddg_, DataDependenceGraph::firstRegisterCycle(), SetTools::intersection(), TTAMachine::Machine::Navigator< ComponentType >::item(), machine_, onlyEndPartiallyUsedRegs_, onlyMidPartiallyUsedRegs_, TTAMachine::Machine::registerFileNavigator(), registersOfRFs(), and usedGPRs_.

Referenced by BFRenameLiveRange::operator()(), and renameSourceRegister().

Here is the call graph for this function:

findPartiallyUsedRegistersInRFBeforeCycle()

std::set< TCEString > RegisterRenamer::findPartiallyUsedRegistersInRFBeforeCycle ( const RegisterFileSet &  rfs, int  earliestCycle, const DataDependenceGraph::NodeSet &  guardMoves  ) const

private

Finds registers which are used but only before given earliestCycle.

Definition at line 260 of file RegisterRenamer.cc.

                                                        {
 
    std::set<TCEString> availableRegs;
    // nothing can be scheduled earlier than cycle 0.
    // in that case we have empty set, no need to check.
    if (earliestCycle < 1) {
        return availableRegs;
    }
 
    std::set<TCEString> allowedGprs = registersOfRFs(rfs);
    std::set<TCEString> regs = usedGPRs_;
    AssocTools::append(onlyBeginPartiallyUsedRegs_, regs);
    AssocTools::append(onlyMidPartiallyUsedRegs_, regs);
    std::set<TCEString> regs2;
    SetTools::intersection(allowedGprs, regs, regs2);
 
    
    // find from used gprs.
    // todo: this is too conservative? leaves one cycle netween war?
    for (std::set<TCEString>::iterator i = regs2.begin(); 
         i != regs2.end(); i++) {
        TCEString rfName = i->substr(0, i->find('.'));
        TTAMachine::RegisterFile* rf = 
            machine_.registerFileNavigator().item(rfName);
 
        unsigned int regIndex = atoi(i->substr(i->find('.')+1).c_str());
        if (ddg_->lastRegisterCycle(*rf, regIndex) < earliestCycle) {
            availableRegs.insert(*i);
        }
    }
    
    // if need to have guards?
    if (guardMoves.empty()) {
        return availableRegs;        
    } else {
        std::set<TCEString> guardedRegs = 
            findGuardRegisters(guardMoves, rfs);
        std::set<TCEString> guardedAvailableRegs;
        SetTools::intersection(
            availableRegs, guardedRegs, guardedAvailableRegs);
        return guardedAvailableRegs;
    }
}

References AssocTools::append(), ddg_, findGuardRegisters(), SetTools::intersection(), TTAMachine::Machine::Navigator< ComponentType >::item(), DataDependenceGraph::lastRegisterCycle(), machine_, onlyBeginPartiallyUsedRegs_, onlyMidPartiallyUsedRegs_, TTAMachine::Machine::registerFileNavigator(), registersOfRFs(), and usedGPRs_.

Referenced by renameDestinationRegister().

Here is the call graph for this function:

freeGPRCount()

unsigned int RegisterRenamer::freeGPRCount ( ) const

inline

Definition at line 66 of file RegisterRenamer.hh.

{ return freeGPRs_.size(); }

References freeGPRs_.

initialize() [1/2]

void RegisterRenamer::initialize ( )

private

Definition at line 87 of file RegisterRenamer.cc.

                            {
    auto regNav = machine_.registerFileNavigator();
 
        auto trCacheIter = tempRegFileCache_.find(&machine_);
 
    if (trCacheIter == tempRegFileCache_.end()) {
        tempRegFiles_ = MachineConnectivityCheck::tempRegisterFiles(machine_);
        tempRegFileCache_[&machine_] = 
            tempRegFiles_;
    } else {
        tempRegFiles_ = trCacheIter->second;
    }
 
    for (int i = 0; i < regNav.count(); i++) {
        bool isTempRf = false;
        TTAMachine::RegisterFile* rf = regNav.item(i);
        if (AssocTools::containsKey(tempRegFiles_, rf)) {
            isTempRf = true;
        }
        unsigned int regCount = isTempRf ? rf->size()-1 : rf->size();
        for (unsigned int j = 0; j < regCount; j++ ) {
            allNormalGPRs_.insert(DisassemblyRegister::registerName(*rf, j));
        }
    }
}

References allNormalGPRs_, AssocTools::containsKey(), machine_, TTAMachine::Machine::registerFileNavigator(), DisassemblyRegister::registerName(), TTAMachine::BaseRegisterFile::size(), tempRegFileCache_, tempRegFiles_, and MachineConnectivityCheck::tempRegisterFiles().

Referenced by RegisterRenamer().

Here is the call graph for this function:

initialize() [2/2]

void RegisterRenamer::initialize

(

DataDependenceGraph &

ddg

)

Definition at line 81 of file RegisterRenamer.cc.

                                                    {
    ddg_ = &ddg;
    initializeFreeRegisters();
}

References ddg_, and initializeFreeRegisters().

Referenced by BUBasicBlockScheduler::handleDDG(), BasicBlockScheduler::handleDDG(), BasicBlockScheduler::handleLoopDDG(), BUBasicBlockScheduler::handleLoopDDG(), and BF2Scheduler::scheduleDDG().

Here is the call graph for this function:

initializeFreeRegisters()

void RegisterRenamer::initializeFreeRegisters ( )

private

Definition at line 114 of file RegisterRenamer.cc.

                                         {
    
    assert(ddg_ != NULL);
    freeGPRs_ = allNormalGPRs_;
    onlyBeginPartiallyUsedRegs_.clear();
    onlyEndPartiallyUsedRegs_.clear();
    onlyMidPartiallyUsedRegs_.clear();
 
    std::map<TCEString,int> lastUses;
 
    // find regs inside this BB.
    for (int i = 0; i < ddg_->nodeCount(); i++) {
        MoveNode& node = ddg_->node(i);
 
        // any write to a reg means it's not alive.
        TTAProgram::Terminal& dest = node.move().destination();
        if (dest.isGPR()) {
            TCEString regName = DisassemblyRegister::registerName(
                dest.registerFile(), dest.index());
            onlyMidPartiallyUsedRegs_.insert(regName);
        }
        TTAProgram::Terminal& src = node.move().source();
        if (src.isGPR()) {
            TCEString regName = DisassemblyRegister::registerName(
                src.registerFile(), src.index());
            onlyMidPartiallyUsedRegs_.insert(regName);
        }
    }
 
    // then loop for deps outside or inside this bb.
    for (std::set<TCEString>::iterator allIter = freeGPRs_.begin(); 
         allIter != freeGPRs_.end();) {
        bool aliveOver = false;
        bool aliveAtBeginning = false;
        bool aliveAtEnd = false;
        bool aliveAtMid = false;
        // defined before and used here or after?
        if (bb_.liveRangeData_->regDefReaches_.find(*allIter) != 
            bb_.liveRangeData_->regDefReaches_.end()) {
            if (bb_.liveRangeData_->registersUsedAfter_.find(*allIter) 
                != bb_.liveRangeData_->registersUsedAfter_.end()) {
                aliveOver = true;
            }
            if (bb_.liveRangeData_->regFirstUses_.find(*allIter) != 
                bb_.liveRangeData_->regFirstUses_.end()) {
                aliveAtBeginning = true;
                LiveRangeData::MoveNodeUseMapSet::iterator i =
                    bb_.liveRangeData_->regLastUses_.find(*allIter);
                if (i != bb_.liveRangeData_->regLastUses_.end()) {
                    LiveRangeData::MoveNodeUseSet& lastUses = i->second;
                    for (LiveRangeData::MoveNodeUseSet::iterator j = 
                             lastUses.begin(); j != lastUses.end(); j++) {
                        if (j->pseudo()) {
                            aliveOver = true;
                        }
                    }
                }
            }
            aliveAtBeginning = true;
        }
        // used after this?
        if (bb_.liveRangeData_->registersUsedAfter_.find(*allIter) != 
            bb_.liveRangeData_->registersUsedAfter_.end()) {
            // defined here?
            if (bb_.liveRangeData_->regDefines_.find(*allIter) != 
                bb_.liveRangeData_->regDefines_.end()) {
                aliveAtEnd = true;
            }            
        }
        
        if (aliveAtEnd && aliveAtBeginning) {
            aliveOver = true;
        }
 
        // TODO: why was this here?
        if (onlyMidPartiallyUsedRegs_.find(*allIter) != 
            onlyMidPartiallyUsedRegs_.end()) {
            aliveAtMid = true;
        }
 
        if (aliveOver) {
            // can not be used for renaming.
            onlyMidPartiallyUsedRegs_.erase(*allIter);
            freeGPRs_.erase(allIter++);
        } else {
            if (aliveAtBeginning) {
                onlyBeginPartiallyUsedRegs_.insert(*allIter);
 
                onlyMidPartiallyUsedRegs_.erase(*allIter);
                freeGPRs_.erase(allIter++);
            } else {
                if (aliveAtEnd) {
                    onlyEndPartiallyUsedRegs_.insert(*allIter);
 
                    onlyMidPartiallyUsedRegs_.erase(*allIter);
                    freeGPRs_.erase(allIter++);
                } else { // only mid if has reads of writes?
                    if (aliveAtMid) {
                        freeGPRs_.erase(allIter++);
                    } else {
                        allIter++;
                    }
                }
            }
        }
    }
}

References allNormalGPRs_, assert, bb_, ddg_, TTAProgram::Move::destination(), freeGPRs_, TTAProgram::Terminal::index(), TTAProgram::Terminal::isGPR(), TTAProgram::BasicBlock::liveRangeData_, MoveNode::move(), BoostGraph< GraphNode, GraphEdge >::node(), BoostGraph< GraphNode, GraphEdge >::nodeCount(), onlyBeginPartiallyUsedRegs_, onlyEndPartiallyUsedRegs_, onlyMidPartiallyUsedRegs_, LiveRangeData::regDefines_, LiveRangeData::regDefReaches_, LiveRangeData::regFirstUses_, TTAProgram::Terminal::registerFile(), DisassemblyRegister::registerName(), LiveRangeData::registersUsedAfter_, LiveRangeData::regLastUses_, and TTAProgram::Move::source().

Referenced by initialize().

Here is the call graph for this function:

registersOfRFs()

std::set< TCEString > RegisterRenamer::registersOfRFs ( const RegisterFileSet &  rfs ) const

private

Definition at line 233 of file RegisterRenamer.cc.

                                      {
 
    std::set<TCEString> gprs;
    for (std::set<const TTAMachine::RegisterFile*,
             TTAMachine::MachinePart::Comparator>::iterator i = rfs.begin();
         i != rfs.end(); i++) {
        bool isTempRF = false;
        const TTAMachine::RegisterFile* rf = *i;
        if (AssocTools::containsKey(tempRegFiles_, rf)) {
            isTempRF = true;
        }
        int lowestFreeIndex = 0;
        if (rf->zeroRegister()) {
            lowestFreeIndex = 1;
        }
        for (int j = lowestFreeIndex;
             j < (isTempRF ? rf->size() - 1 : rf->size()); j++) {
            gprs.insert(DisassemblyRegister::registerName(*rf, j));
        }
    }
    return gprs;
}

References AssocTools::containsKey(), DisassemblyRegister::registerName(), TTAMachine::BaseRegisterFile::size(), tempRegFiles_, and TTAMachine::RegisterFile::zeroRegister().

Referenced by findFreeRegistersInRF(), findPartiallyUsedRegistersInRFAfterCycle(), and findPartiallyUsedRegistersInRFBeforeCycle().

Here is the call graph for this function:

renameDestinationRegister()

bool RegisterRenamer::renameDestinationRegister	(	MoveNode &	node,
		bool	loopScheduling,
		bool	allowSameRf,
		bool	differentRfOnlyDirectlyReachable,
		int	earliestCycle = -1
	)

Renames destination register of a move (from the move itself and from all other moves in same liverange)

Definition at line 458 of file RegisterRenamer.cc.

                       {
    
    if (!node.isMove() || !node.move().destination().isGPR()) {
        return false;
    }
    const TTAMachine::RegisterFile& rf = 
        node.move().destination().registerFile();
    
    // don't allow using same reg multiple times if loop scheduling.
    // unscheudling would cause problems, missing war edges.
    if (loopScheduling) {
        earliestCycle = -1;
    }
    // first find used fully scheduled ones!
    bool reused = true;
    
    std::unique_ptr<LiveRange> liveRange(
        ddg_->findLiveRange(node, true, false));
 
    if (liveRange->writes.empty()) {
        return false;
    }
    std::set<TCEString> availableRegisters;
 
    if (!liveRange->noneScheduled()) {
        // not yet allow guards rename when some movenodes of lr
        // already sched
        if (!allowSameRf) {
            return false;
        }
        RegisterFileSet rfs;
        rfs.insert(&rf);
        earliestCycle = std::min(earliestCycle, liveRange->firstCycle());
        availableRegisters = 
            findPartiallyUsedRegistersInRFBeforeCycle(rfs, earliestCycle,
                                                      liveRange->guards);
    } else { // none scheduled.
        if (tempRegFiles_.empty()) {
 
#ifdef DEBUG_REG_RENAMER
            if (!liveRange->guards.empty()) {
                std::cerr<<"\t\tSearching for avail guard regs before cycle:" 
                         << earliestCycle << std::endl;
            }
#endif
 
            availableRegisters = 
                findPartiallyUsedRegistersBeforeCycle(
                    rf.width(), earliestCycle, liveRange->guards);
 
#ifdef DEBUG_REG_RENAMER
            if (!liveRange->guards.empty()) {
                std::cerr << "\t\t\tfound free gaurd regs: ";
                for (std::set<TCEString>::iterator i = 
                         availableRegisters.begin();
                     i != availableRegisters.end(); i++) {
                    std::cerr << *i << " ";
                }
                std::cerr << std::endl;
            }
#endif
 
        } else {
            if (!differentRfOnlyDirectlyReachable) {
                // only connected RFs
                RegisterFileSet rfs = findConnectedRFs(*liveRange, false);
                availableRegisters = 
                    findPartiallyUsedRegistersInRFBeforeCycle(
                        rfs, earliestCycle, liveRange->guards);
                if (availableRegisters.empty()) {
                    // allow usasge of limm.
                    rfs = findConnectedRFs(*liveRange, true);
                    availableRegisters = 
                        findPartiallyUsedRegistersInRFBeforeCycle(
                            rfs, earliestCycle, liveRange->guards);
                }
            }
        }
    } // if not guards - after this can be guards
    if (availableRegisters.empty()) {
        reused = false;
        
        if (!liveRange->noneScheduled()) {
            if (liveRange->guards.empty()) {
                RegisterFileSet rfs;
                rfs.insert(&rf);
                availableRegisters = 
                    findFreeRegistersInRF(rfs);
            }
        } else {
            if (tempRegFiles_.empty()) {
                if (liveRange->guards.empty()) {
                    availableRegisters = 
                        findFreeRegisters(rf.width());
                } else { // guards use..
#ifdef DEBUG_REG_RENAMER
                    std::cerr << "\t\tSearching for avail guard regs" << std::endl;
#endif
                    RegisterFileSet rfs; // empty, use all RF's
                    availableRegisters =
                        findFreeGuardRegisters(
                            liveRange->guards, rf.width(), rfs);
#ifdef DEBUG_REG_RENAMER
                    std::cerr << "\t\t\tfound free gaurd regs: ";
                    for (std::set<TCEString>::iterator i = 
                             availableRegisters.begin();
                         i != availableRegisters.end(); i++) {
                        std::cerr << *i << " ";
                    }
                    std::cerr << std::endl;
#endif
                }
                
            } else {
                // TODO: this disables guard renaming with regcopyadder
                if (liveRange->guards.empty()) {
                    if (!differentRfOnlyDirectlyReachable) {
                        // only connected RFs
                        RegisterFileSet rfs = 
                            findConnectedRFs(*liveRange, false);
                        availableRegisters = 
                            findFreeRegistersInRF(rfs);
                        if (availableRegisters.empty()) {
                            // allow usage of LIMM
                            rfs = findConnectedRFs(*liveRange, true);
                            availableRegisters = 
                                findFreeRegistersInRF(rfs);
                        }
                    }
                } else {
                    // guards. use only same rf for now.
                    // TODO: update findconnectedRF's to work with guards
                    RegisterFileSet rfs;
                    rfs.insert(&rf);
                    availableRegisters = 
                        findFreeGuardRegisters(
                            liveRange->guards, rf.width(), rfs);
                }
            }
        }
        if (availableRegisters.empty()) {
            return false;
        }
    }
    
    // then actually do it.
    return renameLiveRange(
        *liveRange, *availableRegisters.begin(), 
        reused, false, loopScheduling);
}

References ddg_, TTAProgram::Move::destination(), findConnectedRFs(), findFreeGuardRegisters(), findFreeRegisters(), findFreeRegistersInRF(), DataDependenceGraph::findLiveRange(), findPartiallyUsedRegistersBeforeCycle(), findPartiallyUsedRegistersInRFBeforeCycle(), TTAProgram::Terminal::isGPR(), MoveNode::isMove(), MoveNode::move(), TTAProgram::Terminal::registerFile(), renameLiveRange(), tempRegFiles_, and TTAMachine::BaseRegisterFile::width().

Referenced by BUBasicBlockScheduler::scheduleMove(), and BasicBlockScheduler::scheduleMove().

Here is the call graph for this function:

renamedToRegister()

void RegisterRenamer::renamedToRegister

(

const TCEString &

newReg

)

Definition at line 1094 of file RegisterRenamer.cc.

                                                               {
 
    freeGPRs_.erase(newReg);
 
    onlyBeginPartiallyUsedRegs_.erase(newReg);
    onlyEndPartiallyUsedRegs_.erase(newReg);
    onlyMidPartiallyUsedRegs_.erase(newReg);
 
    usedGPRs_.insert(newReg);
 
}

References freeGPRs_, onlyBeginPartiallyUsedRegs_, onlyEndPartiallyUsedRegs_, onlyMidPartiallyUsedRegs_, and usedGPRs_.

Referenced by BFRenameLiveRange::renameLiveRange(), and renameLiveRange().

renameLiveRange()

bool RegisterRenamer::renameLiveRange	(	LiveRange &	liveRange,
		const TCEString &	newReg,
		bool	usedBefore,
		bool	usedAfter,
		bool	loopScheduling
	)

Definition at line 714 of file RegisterRenamer.cc.

                                         {
 
    if (liveRange.writes.size() <1) {
        return false;
    }
    
    if (liveRange.reads.size() == 0 && liveRange.guards.size() == 0) {
        return false;
    }
 
    assert(newReg.length() > 2);
    TCEString rfName = newReg.substr(0, newReg.find('.'));
    TTAMachine::RegisterFile* rf = 
        machine_.registerFileNavigator().item(rfName);
    
    int newRegIndex = 
        atoi(newReg.substr(newReg.find('.')+1).c_str());
 
    if (usedBefore) {
        // create antidependencies from the previous use of this temp reg.
 
        //todo: if in a loop, create antidependencies to first ones in the BB.
        DataDependenceGraph::NodeSet lastReads = 
            ddg_->lastScheduledRegisterReads(
                *rf, newRegIndex);
        
        DataDependenceGraph::NodeSet lastWrites = 
            ddg_->lastScheduledRegisterWrites(
                *rf, newRegIndex);
 
        DataDependenceGraph::NodeSet lastGuards = 
            ddg_->lastScheduledRegisterGuardReads(
                *rf, newRegIndex);
 
        // create the deps.
        for (DataDependenceGraph::NodeSet::iterator i = 
                 liveRange.writes.begin(); i != liveRange.writes.end(); i++) {
 
            // create WAR's from previous reads
            for (DataDependenceGraph::NodeSet::iterator 
                     j = lastReads.begin(); j != lastReads.end(); j++) {
 
                DataDependenceEdge* edge = new DataDependenceEdge(
                    DataDependenceEdge::EDGE_REGISTER,
                    DataDependenceEdge::DEP_WAR, newReg);
 
                ddg_->connectNodes(**j, **i, *edge);
            }
 
            // create WAR's from previous guard uses
            for (DataDependenceGraph::NodeSet::iterator 
                     j = lastGuards.begin(); j != lastGuards.end(); j++) {
 
                DataDependenceEdge* edge = new DataDependenceEdge(
                    DataDependenceEdge::EDGE_REGISTER,
                    DataDependenceEdge::DEP_WAR, newReg, true);
 
                ddg_->connectNodes(**j, **i, *edge);
            }
 
            // create WAW's from previous writes.
            for (DataDependenceGraph::NodeSet::iterator 
                     j = lastWrites.begin(); j != lastWrites.end(); j++) {
 
                DataDependenceEdge* edge = new DataDependenceEdge(
                    DataDependenceEdge::EDGE_REGISTER,
                    DataDependenceEdge::DEP_WAW, newReg);
 
                ddg_->connectNodes(**j, **i, *edge);
            }
        }
    } else {
        // this is not used before.
 
        // update bookkeeping about first use of this reg
        if (!usedAfter)
            assert(bb_.liveRangeData_->regFirstUses_[newReg].empty());
 
        // killing write.
        if (liveRange.writes.size() == 1 && 
            (*liveRange.writes.begin())->move().isUnconditional()) {
            bb_.liveRangeData_->regKills_[newReg].first = 
                MoveNodeUse(**liveRange.writes.begin());
            bb_.liveRangeData_->regFirstDefines_[newReg].clear();
            bb_.liveRangeData_->regFirstUses_[newReg].clear();            
        }
 
        // for writing.
        for (DataDependenceGraph::NodeSet::iterator i = 
                 liveRange.writes.begin(); i != liveRange.writes.end(); i++) {
 
            MoveNodeUse mnd(**i);
            bb_.liveRangeData_->regFirstDefines_[newReg].insert(mnd);
            // TODO: only if intra-bb-antideps enabled?
            static_cast<DataDependenceGraph*>(ddg_->rootGraph())->
                updateRegWrite(mnd, newReg, bb_);
        }
 
        // for reading.
        for (DataDependenceGraph::NodeSet::iterator i = 
                 liveRange.reads.begin(); i != liveRange.reads.end(); i++) {
 
            MoveNodeUse mnd(**i);
            bb_.liveRangeData_->regFirstUses_[newReg].insert(mnd);
            // no need to create raw deps here
        }
 
        // for guards.
        for (DataDependenceGraph::NodeSet::iterator i = 
                 liveRange.guards.begin(); i != liveRange.guards.end(); i++) {
 
            MoveNodeUse mnd(**i);
            bb_.liveRangeData_->regFirstUses_[newReg].insert(mnd);
            // no need to create raw deps here
        }
 
    }
 
    if (usedAfter) {
        
        DataDependenceGraph::NodeSet firstWrites = 
            ddg_->firstScheduledRegisterWrites(
                *rf, newRegIndex);
 
        // make sure no circular antidep path
        for (DataDependenceGraph::NodeSet::iterator 
                 j = firstWrites.begin(); j != firstWrites.end(); j++) {
 
            for (DataDependenceGraph::NodeSet::iterator i = 
                     liveRange.reads.begin(); i != liveRange.reads.end(); 
                 i++) {
                if (ddg_->hasPath(**j, **i)) {
                    return false;
                }
            }
 
            for (DataDependenceGraph::NodeSet::iterator i = 
                     liveRange.writes.begin(); i != liveRange.writes.end(); 
                 i++) {
                if (ddg_->hasPath(**j, **i)) {
                    return false;
                }
            }
        }
 
 
        // create the antidep deps.
 
        for (DataDependenceGraph::NodeSet::iterator 
                 j = firstWrites.begin(); j != firstWrites.end(); j++) {
            
            // WaW's
            for (DataDependenceGraph::NodeSet::iterator i = 
                     liveRange.writes.begin(); i != liveRange.writes.end(); 
                 i++) {
                
                DataDependenceEdge* edge = new DataDependenceEdge(
                    DataDependenceEdge::EDGE_REGISTER,
                    DataDependenceEdge::DEP_WAW, newReg);
                
                ddg_->connectNodes(**i,**j, *edge);
            }
        
            // WaR's
            for (DataDependenceGraph::NodeSet::iterator i = 
                     liveRange.reads.begin(); i != liveRange.reads.end(); 
                 i++) {
                DataDependenceEdge* edge = new DataDependenceEdge(
                    DataDependenceEdge::EDGE_REGISTER,
                    DataDependenceEdge::DEP_WAR, newReg);
                
                ddg_->connectNodes(**i,**j, *edge);
            }
        }
 
    } else {
 
        // killing write.
        if (liveRange.writes.size() == 1 && 
            (*liveRange.writes.begin())->move().isUnconditional()) {
            bb_.liveRangeData_->regLastKills_[newReg].first = 
                MoveNodeUse(**liveRange.writes.begin());
            bb_.liveRangeData_->regDefines_[newReg].clear();
        }
 
        // for writing.
        for (DataDependenceGraph::NodeSet::iterator i = 
                 liveRange.writes.begin(); i != liveRange.writes.end(); i++) {
 
            MoveNodeUse mnd(**i);
            bb_.liveRangeData_->regDefines_[newReg].insert(mnd);
        }
 
        // for reading.
        for (DataDependenceGraph::NodeSet::iterator i = 
                 liveRange.reads.begin(); i != liveRange.reads.end(); i++) {
 
            MoveNodeUse mnd(**i);
            bb_.liveRangeData_->regLastUses_[newReg].insert(mnd);
        }
 
        // need to create backedges to first if we are loop scheduling.
        if (loopScheduling) {
            updateAntiEdgesFromLRTo(liveRange, newReg, bb_, 1);
        }
    }
 
    // first update the movenodes.
 
    // for writes.
    for (DataDependenceGraph::NodeSet::iterator i = liveRange.writes.begin();
         i != liveRange.writes.end(); i++) {
        TTAProgram::Move& move = (**i).move();
        const TTAMachine::Port& oldPort = move.destination().port();
        if (oldPort.parentUnit() == rf) {
            move.setDestination(new TTAProgram::TerminalRegister(
                                    oldPort, newRegIndex));
        } else {
            move.setDestination(new TTAProgram::TerminalRegister(
                                    *rf->firstWritePort(), newRegIndex));
        }
 
    }
 
    // for reads.
    for (DataDependenceGraph::NodeSet::iterator i = liveRange.reads.begin();
         i != liveRange.reads.end(); i++) {
        TTAProgram::Move& move = (**i).move();
        const TTAMachine::Port& oldPort = move.source().port();
        if (oldPort.parentUnit() == rf) {
            move.setSource(new TTAProgram::TerminalRegister(
                           oldPort, newRegIndex));
        } else {
            move.setSource(new TTAProgram::TerminalRegister(
                               *rf->firstReadPort(), newRegIndex));
        }
    }
 
 
    // for reads.
    for (DataDependenceGraph::NodeSet::iterator i = liveRange.guards.begin();
         i != liveRange.guards.end(); i++) {
        MoveNode& mn = **i;
        TTAProgram::Move& move = mn.move();
        const TTAMachine::Guard& guard = move.guard().guard();
        // TODO: update the guard here
 
#ifdef DEBUG_REG_RENAMER
 
        TTAMachine::Bus& bus = move.bus();
 
        std::cerr << "We should be updating guard here for: " 
                  << mn.toString()
                  << std::endl;
        std::cerr << "\tnew guard reg: " << rf->name() << "." << newRegIndex
                  << std::endl;
        
        std::cerr << "\tBus: " << bus.name() << std::endl;
 
#endif
        TTAMachine::Bus* guardBus =  guard.parentBus();
#ifdef DEBUG_REG_RENAMER
        std::cerr << "\tGuard bus: " << guardBus->name() << std::endl;
#endif
        for (int j = 0 ; j < guardBus->guardCount(); j++) {
            TTAMachine::Guard *g = guardBus->guard(j);
            TTAMachine::RegisterGuard* rg =
                dynamic_cast<TTAMachine::RegisterGuard*>(g);
            if (rg) {
                if (rg->registerFile() == rf &&
                    rg->registerIndex() == newRegIndex &&
                    rg->isInverted() == guard.isInverted()) {
                    move.setGuard(new TTAProgram::MoveGuard(*g));
#ifdef DEBUG_REG_RENAMER
                    std::cerr << "\tset new guard: " << mn.toString()
                              << std::endl;
#endif
                }
            }
        }
        
    }
 
 
 
 
 
 
    
 
 
 
    // then update ddg and notify selector.
 
    // for writes.
    for (DataDependenceGraph::NodeSet::iterator i = liveRange.writes.begin();
         i != liveRange.writes.end(); i++) {
 
        DataDependenceGraph::NodeSet writeSuccessors =
            ddg_->successors(**i);
 
        DataDependenceGraph::NodeSet writePredecessors =
            ddg_->predecessors(**i);
 
        ddg_->destRenamed(**i);
 
        // notify successors of write to prevent orphan nodes.
        for (DataDependenceGraph::NodeSet::iterator iter =
                 writeSuccessors.begin();
             iter != writeSuccessors.end(); iter++) {
            selector_->mightBeReady(**iter);
        }
 
        // notify successors of write to prevent orphan nodes.
        for (DataDependenceGraph::NodeSet::iterator iter =
                 writePredecessors.begin();
             iter != writePredecessors.end(); iter++) {
            selector_->mightBeReady(**iter);
        }
 
    }
 
    // for reads
    for (DataDependenceGraph::NodeSet::iterator i = liveRange.reads.begin();
         i != liveRange.reads.end(); i++) {
        DataDependenceGraph::NodeSet successors =
            ddg_->successors(**i);
 
        ddg_->sourceRenamed(**i);
 
        DataDependenceGraph::NodeSet predecessors =
            ddg_->predecessors(**i);
        
        // notify successors to prevent orphan nodes.
        for (DataDependenceGraph::NodeSet::iterator iter =
                 successors.begin();
             iter != successors.end(); iter++) {
            selector_->mightBeReady(**iter);
        }
 
        // notify successors to prevent orphan nodes.
        for (DataDependenceGraph::NodeSet::iterator iter =
                 predecessors.begin();
             iter != predecessors.end(); iter++) {
            selector_->mightBeReady(**iter);
        }
    }
 
    // for guards
    for (DataDependenceGraph::NodeSet::iterator i = liveRange.guards.begin();
         i != liveRange.guards.end(); i++) {
        DataDependenceGraph::NodeSet successors =
            ddg_->successors(**i);
 
        ddg_->guardRenamed(**i);
 
        DataDependenceGraph::NodeSet predecessors =
            ddg_->predecessors(**i);
        
        // notify successors to prevent orphan nodes.
        for (DataDependenceGraph::NodeSet::iterator iter =
                 successors.begin();
             iter != successors.end(); iter++) {
            selector_->mightBeReady(**iter);
        }
 
        // notify successors to prevent orphan nodes.
        for (DataDependenceGraph::NodeSet::iterator iter =
                 predecessors.begin();
             iter != predecessors.end(); iter++) {
            selector_->mightBeReady(**iter);
        }
    }
 
    renamedToRegister(newReg);
    return true;
}

References assert, bb_, TTAProgram::Move::bus(), BoostGraph< GraphNode, GraphEdge >::connectNodes(), ddg_, DataDependenceEdge::DEP_WAR, DataDependenceEdge::DEP_WAW, TTAProgram::Move::destination(), DataDependenceGraph::destRenamed(), DataDependenceEdge::EDGE_REGISTER, TTAMachine::RegisterFile::firstReadPort(), DataDependenceGraph::firstScheduledRegisterWrites(), TTAMachine::RegisterFile::firstWritePort(), TTAProgram::Move::guard(), TTAProgram::MoveGuard::guard(), TTAMachine::Bus::guard(), TTAMachine::Bus::guardCount(), DataDependenceGraph::guardRenamed(), LiveRange::guards, BoostGraph< GraphNode, GraphEdge >::hasPath(), TTAMachine::Guard::isInverted(), TTAMachine::Machine::Navigator< ComponentType >::item(), DataDependenceGraph::lastScheduledRegisterGuardReads(), DataDependenceGraph::lastScheduledRegisterReads(), DataDependenceGraph::lastScheduledRegisterWrites(), TTAProgram::BasicBlock::liveRangeData_, machine_, MoveNodeSelector::mightBeReady(), MoveNode::move(), TTAMachine::Component::name(), TTAMachine::Guard::parentBus(), TTAMachine::Port::parentUnit(), TTAProgram::Terminal::port(), BoostGraph< GraphNode, GraphEdge >::predecessors(), LiveRange::reads, LiveRangeData::regDefines_, LiveRangeData::regFirstDefines_, LiveRangeData::regFirstUses_, TTAMachine::RegisterGuard::registerFile(), TTAMachine::Machine::registerFileNavigator(), TTAMachine::RegisterGuard::registerIndex(), LiveRangeData::regKills_, LiveRangeData::regLastKills_, LiveRangeData::regLastUses_, renamedToRegister(), BoostGraph< GraphNode, GraphEdge >::rootGraph(), selector_, TTAProgram::Move::setDestination(), TTAProgram::Move::setGuard(), TTAProgram::Move::setSource(), TTAProgram::Move::source(), DataDependenceGraph::sourceRenamed(), BoostGraph< GraphNode, GraphEdge >::successors(), MoveNode::toString(), updateAntiEdgesFromLRTo(), and LiveRange::writes.

Referenced by renameDestinationRegister(), and renameSourceRegister().

Here is the call graph for this function:

renameSourceRegister()

bool RegisterRenamer::renameSourceRegister	(	MoveNode &	node,
		bool	loopScheduling,
		bool	allowSameRf,
		bool	differentRfOnlyDirectlyReachable,
		int	latestCycle = INT_MAX
	)

Renames source register of a move (from the move itself and from all other moves in same liverange)

Definition at line 617 of file RegisterRenamer.cc.

                                                                              {
 
    if (!node.isMove() || !node.move().source().isGPR()) {
        return false;
    }
    const TTAMachine::RegisterFile& rf = 
        node.move().source().registerFile();
    
    if (loopScheduling) {
        latestCycle = -1;
    }
 
    // first find used fully scheduled ones!
    bool reused = true;
 
    std::unique_ptr<LiveRange> liveRange(
        ddg_->findLiveRange(node, false, false));
 
    if (liveRange->writes.empty()) {
        return false;
    }
    std::set<TCEString> availableRegisters;
 
    if (!liveRange->noneScheduled()) {
        if (!allowSameRf) {
            return false;
        }
        std::set<const TTAMachine::RegisterFile*,
            TTAMachine::MachinePart::Comparator> rfs;
        rfs.insert(&rf);
        latestCycle = std::max(latestCycle, liveRange->lastCycle());
 
        availableRegisters = 
        findPartiallyUsedRegistersInRFAfterCycle(rfs, latestCycle);
    } else { 
        if (tempRegFiles_.empty()) {
            availableRegisters = 
                findPartiallyUsedRegistersAfterCycle(rf.width(), latestCycle);
        } else {
            if (!differentRfOnlyDirectlyReachable) {
                // only connected RFs
                std::set<const TTAMachine::RegisterFile*, 
                    TTAMachine::MachinePart::Comparator> 
                rfs = findConnectedRFs(*liveRange, false);
                availableRegisters = 
                    findPartiallyUsedRegistersInRFAfterCycle(rfs, latestCycle);
                if (availableRegisters.empty()) {
                    rfs = findConnectedRFs(*liveRange, true);
                    availableRegisters = 
                        findPartiallyUsedRegistersInRFAfterCycle(
                            rfs, latestCycle);
                }
            }
        }
    }        
 
    if (availableRegisters.empty()) {
        reused = false;
 
        if (!liveRange->noneScheduled()) {
            std::set<const TTAMachine::RegisterFile*,
                TTAMachine::MachinePart::Comparator> rfs;
            rfs.insert(&rf);
            availableRegisters = 
                findFreeRegistersInRF(rfs);
        } else {
            if (tempRegFiles_.empty()) {
                availableRegisters = 
                    findFreeRegisters(rf.width());
            } else { 
                if (!differentRfOnlyDirectlyReachable) {
                    // only connected RFs
                    std::set<const TTAMachine::RegisterFile*,
                        TTAMachine::MachinePart::Comparator> 
                    rfs = findConnectedRFs(*liveRange, false);
                    availableRegisters = findFreeRegistersInRF(rfs);
                    if (availableRegisters.empty()) {
                        rfs = findConnectedRFs(*liveRange, true);
                        availableRegisters = findFreeRegistersInRF(rfs);
                    }
                }
            }
        }
        if (availableRegisters.empty()) {
            return false;
        }
    }
    
    return
        renameLiveRange(
            *liveRange, *availableRegisters.begin(), false, reused, 
            loopScheduling);
}

References ddg_, findConnectedRFs(), findFreeRegisters(), findFreeRegistersInRF(), DataDependenceGraph::findLiveRange(), findPartiallyUsedRegistersAfterCycle(), findPartiallyUsedRegistersInRFAfterCycle(), TTAProgram::Terminal::isGPR(), MoveNode::isMove(), MoveNode::move(), TTAProgram::Terminal::registerFile(), renameLiveRange(), TTAProgram::Move::source(), tempRegFiles_, and TTAMachine::BaseRegisterFile::width().

Referenced by BUBasicBlockScheduler::scheduleMove(), and BasicBlockScheduler::scheduleMove().

Here is the call graph for this function:

revertedRenameToRegister()

void RegisterRenamer::revertedRenameToRegister

(

const TCEString &

reg

)

Definition at line 1106 of file RegisterRenamer.cc.

                                                                   {
    if (bb_.liveRangeData_->regFirstUses_[reg].empty() &&
        bb_.liveRangeData_->regLastUses_[reg].empty() &&
        bb_.liveRangeData_->regDefines_[reg].empty() &&
        bb_.liveRangeData_->regFirstDefines_[reg].empty()) {
        freeGPRs_.insert(reg);
    }
}

References bb_, freeGPRs_, TTAProgram::BasicBlock::liveRangeData_, LiveRangeData::regDefines_, LiveRangeData::regFirstDefines_, LiveRangeData::regFirstUses_, and LiveRangeData::regLastUses_.

Referenced by BFRenameLiveRange::undoOnlyMe().

setSelector()

void RegisterRenamer::setSelector

(

MoveNodeSelector *

selector

)

Registers the selector being used to the bypasser.

If the bypasser has been registered to the selector, bypasses can notify the selector about dependence changes. Currently it notifies the successors of a node being removed due dead result elimination.

Parameters

selector

selector which bypasser notifies on some dependence changes.

Definition at line 1126 of file RegisterRenamer.cc.

                                                       {
    selector_ = selector;
}

References selector_.

Referenced by BUBasicBlockScheduler::handleDDG(), BasicBlockScheduler::handleDDG(), BF2Scheduler::handleLoopDDG(), BasicBlockScheduler::handleLoopDDG(), BUBasicBlockScheduler::handleLoopDDG(), and BF2Scheduler::scheduleDDG().

updateAntiEdgesFromLRTo()

void RegisterRenamer::updateAntiEdgesFromLRTo ( LiveRange &  liveRange, const TCEString &  newReg, TTAProgram::BasicBlock &  bb, int  loopDepth  ) const

private

Updates antidep edges from this liverange to first def of some other bb.

Parameters

liveRange	liverange which is the origin of the deps
newReg	name of the new register
bb	destination BB where to draw the edges to @loopDepth loop depth of added edges.

Definition at line 1139 of file RegisterRenamer.cc.

                         {
    std::set<MoveNodeUse>& firstDefs = 
        bb.liveRangeData_->regFirstDefines_[newReg];
    
    for (std::set<MoveNodeUse>::iterator i = firstDefs.begin();
         i != firstDefs.end(); i++) {
        
        const MoveNodeUse& destination = *i;
        if (ddg_->hasNode(*destination.mn())) {
            
            //WaW's of writes.
            for (DataDependenceGraph::NodeSet::iterator j = 
                     liveRange.writes.begin(); 
                 j != liveRange.writes.end(); j++) {
                
                // create dependency edge
                DataDependenceEdge* dde =
                    new DataDependenceEdge(
                        DataDependenceEdge::EDGE_REGISTER,
                        DataDependenceEdge::DEP_WAW, newReg, 
                        false, false, false, destination.pseudo(), loopDepth);
                
                // and connect.
                ddg_->connectOrDeleteEdge(
                    **j, *destination.mn(), dde);
            }
            
            //War's of reads.
            for (DataDependenceGraph::NodeSet::iterator j = 
                     liveRange.reads.begin(); 
                 j != liveRange.reads.end(); j++) {
                
                // create dependency edge
                DataDependenceEdge* dde =
                    new DataDependenceEdge(
                        DataDependenceEdge::EDGE_REGISTER,
                        DataDependenceEdge::DEP_WAR, newReg, 
                        false, false, false, destination.pseudo(), 1);
                
                // and connect.
                ddg_->connectOrDeleteEdge(
                    **j, *destination.mn(), dde);
            }
 
            //War's of guards.
            for (DataDependenceGraph::NodeSet::iterator j = 
                     liveRange.guards.begin(); 
                 j != liveRange.guards.end(); j++) {
                
                // create dependency edge
                DataDependenceEdge* dde =
                    new DataDependenceEdge(
                        DataDependenceEdge::EDGE_REGISTER,
                        DataDependenceEdge::DEP_WAR, newReg, 
                        true, false, false, destination.pseudo(), 1);
                
                // and connect.
                ddg_->connectOrDeleteEdge(
                    **j, *destination.mn(), dde);
            }
        }
    }
}

References bb(), DataDependenceGraph::connectOrDeleteEdge(), ddg_, DataDependenceEdge::DEP_WAR, DataDependenceEdge::DEP_WAW, DataDependenceEdge::EDGE_REGISTER, LiveRange::guards, BoostGraph< GraphNode, GraphEdge >::hasNode(), TTAProgram::BasicBlock::liveRangeData_, MoveNodeUse::mn(), MoveNodeUse::pseudo(), LiveRange::reads, LiveRangeData::regFirstDefines_, and LiveRange::writes.

Referenced by renameLiveRange().

Here is the call graph for this function:

Member Data Documentation

allNormalGPRs_

std::set<TCEString> RegisterRenamer::allNormalGPRs_

private

Definition at line 140 of file RegisterRenamer.hh.

Referenced by initialize(), and initializeFreeRegisters().

bb_

TTAProgram::BasicBlock& RegisterRenamer::bb_

private

Definition at line 162 of file RegisterRenamer.hh.

Referenced by bb(), initializeFreeRegisters(), renameLiveRange(), and revertedRenameToRegister().

ddg_

DataDependenceGraph* RegisterRenamer::ddg_

private

Definition at line 163 of file RegisterRenamer.hh.

Referenced by findPartiallyUsedRegistersAfterCycle(), findPartiallyUsedRegistersBeforeCycle(), findPartiallyUsedRegistersInRFAfterCycle(), findPartiallyUsedRegistersInRFBeforeCycle(), initialize(), initializeFreeRegisters(), renameDestinationRegister(), renameLiveRange(), renameSourceRegister(), and updateAntiEdgesFromLRTo().

freeGPRs_

std::set<TCEString> RegisterRenamer::freeGPRs_

private

Definition at line 141 of file RegisterRenamer.hh.

Referenced by findFreeRegisters(), findFreeRegistersInRF(), freeGPRCount(), initializeFreeRegisters(), renamedToRegister(), and revertedRenameToRegister().

machine_

const TTAMachine::Machine& RegisterRenamer::machine_

private

Definition at line 161 of file RegisterRenamer.hh.

Referenced by findConnectedRFs(), findFreeRegisters(), findPartiallyUsedRegistersAfterCycle(), findPartiallyUsedRegistersBeforeCycle(), findPartiallyUsedRegistersInRFAfterCycle(), findPartiallyUsedRegistersInRFBeforeCycle(), initialize(), and renameLiveRange().

onlyBeginPartiallyUsedRegs_

std::set<TCEString> RegisterRenamer::onlyBeginPartiallyUsedRegs_

private

Definition at line 149 of file RegisterRenamer.hh.

Referenced by findPartiallyUsedRegistersBeforeCycle(), findPartiallyUsedRegistersInRFBeforeCycle(), initializeFreeRegisters(), and renamedToRegister().

onlyEndPartiallyUsedRegs_

std::set<TCEString> RegisterRenamer::onlyEndPartiallyUsedRegs_

private

Definition at line 151 of file RegisterRenamer.hh.

Referenced by findPartiallyUsedRegistersAfterCycle(), findPartiallyUsedRegistersInRFAfterCycle(), initializeFreeRegisters(), and renamedToRegister().

onlyMidPartiallyUsedRegs_

std::set<TCEString> RegisterRenamer::onlyMidPartiallyUsedRegs_

private

Definition at line 152 of file RegisterRenamer.hh.

Referenced by findPartiallyUsedRegistersAfterCycle(), findPartiallyUsedRegistersBeforeCycle(), findPartiallyUsedRegistersInRFAfterCycle(), findPartiallyUsedRegistersInRFBeforeCycle(), initializeFreeRegisters(), and renamedToRegister().

selector_

MoveNodeSelector* RegisterRenamer::selector_

private

Definition at line 165 of file RegisterRenamer.hh.

Referenced by renameLiveRange(), and setSelector().

tempRegFileCache_

std::map< const TTAMachine::Machine *, std::set< const TTAMachine::RegisterFile *, TTAMachine::MachinePart::Comparator > > RegisterRenamer::tempRegFileCache_

staticprivate

To avoid reanalysing machine every time hen new rr created.

Definition at line 157 of file RegisterRenamer.hh.

Referenced by initialize().

tempRegFiles_

std::set<const TTAMachine::RegisterFile*, TTAMachine::MachinePart::Comparator> RegisterRenamer::tempRegFiles_

private

Definition at line 159 of file RegisterRenamer.hh.

Referenced by initialize(), registersOfRFs(), renameDestinationRegister(), and renameSourceRegister().

usedGPRs_

std::set<TCEString> RegisterRenamer::usedGPRs_

private

Definition at line 145 of file RegisterRenamer.hh.

Referenced by findPartiallyUsedRegistersAfterCycle(), findPartiallyUsedRegistersBeforeCycle(), findPartiallyUsedRegistersInRFAfterCycle(), findPartiallyUsedRegistersInRFBeforeCycle(), and renamedToRegister().

---

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

• RegisterRenamer.hh
• RegisterRenamer.cc