CopyingDelaySlotFiller Class Reference

#include <CopyingDelaySlotFiller.hh>

Collaboration diagram for CopyingDelaySlotFiller:

Public Types
typedef std::map< TCEString, TTAProgram::TerminalImmediate * >	PendingImmediateMap

Public Member Functions
	CopyingDelaySlotFiller ()
	~CopyingDelaySlotFiller ()
void	initialize (ControlFlowGraph &cfg, DataDependenceGraph &ddg, const TTAMachine::Machine &machine)
void	fillDelaySlots (ControlFlowGraph &cfg, DataDependenceGraph &ddg, const TTAMachine::Machine &machine)
void	addResourceManager (TTAProgram::BasicBlock &bbn, SimpleResourceManager &rm)
void	bbnScheduled (BasicBlockNode &bbn)
void	finalizeProcedure ()

Static Public Member Functions
static std::pair< int, TTAProgram::Move * >	findJump (TTAProgram::BasicBlock &bb, ControlFlowEdge::CFGEdgePredicate *pred=nullptr)
static std::pair< TTAProgram::Move *, std::shared_ptr< TTAProgram::Immediate > >	findJumpImmediate (int jumpIndex, TTAProgram::Move &jumpMove, TTAProgram::InstructionReferenceManager &irm)

Protected Member Functions
bool	fillDelaySlots (BasicBlockNode &jumpingBB, int delaySlots, bool fillFallThru)

Private Types
enum	BBNStates {   BBN_UNKNOWN = 0, BBN_SCHEDULED = 1, BBN_JUMP_FILLED = 3, BBN_FALLTHRU_FILLED = 5,   BBN_BOTH_FILLED = 7, BBN_TEMPS_CLEANED = 15, BBN_ALL_DONE = 31 }
typedef std::vector< std::list< MoveNode * > >	MoveNodeListVector

Private Member Functions
bool	areAllJumpPredsScheduled (BasicBlockNode &bbn) const
bool	areAllJumpPredsFilled (BasicBlockNode &bbn) const
void	bbFilled (BasicBlockNode &bbn)
bool	mightFillIncomingTo (BasicBlockNode &bbn)
bool	writesRegister (TTAProgram::Move &move, const TTAMachine::RegisterFile *rf, unsigned int registerIndex)
bool	tryToFillSlots (BasicBlockNode &blockToFillNode, BasicBlockNode &nextBBNode, bool fallThru, TTAProgram::Move *jumpMove, int slotsToFill, int removeGuards, int grIndex, const TTAMachine::RegisterFile *grFile, TTAProgram::Move *&skippedJump, int delaySlots)
bool	updateJumpsAndCfg (BasicBlockNode &jumpBBN, BasicBlockNode &fillingBBN, ControlFlowEdge &fillEdge, TTAProgram::Move *jumpAddressMove, std::shared_ptr< TTAProgram::Immediate > jumpAddressImmediate, TTAProgram::Move *jumpMove, int slotsFilled, TTAProgram::Move *skippedJump)
bool	updateFTBBAndCfg (BasicBlockNode &jumpingBB, BasicBlockNode &nextBBN, ControlFlowEdge &edge, int slotsFilled)
void	loseCopies (DataDependenceGraph::NodeSet *keptTempNodes)
bool	collectMoves (BasicBlockNode &blockToFillNode, BasicBlockNode &nextBBN, MoveNodeListVector &moves, int slotsToFill, bool fallThru, int removeGuards, TTAProgram::Move *jumpMove, int grIndex, const TTAMachine::RegisterFile *grFile, TTAProgram::Move *&skippedJump, int delaySlots)
bool	checkImmediatesAfter (TTAProgram::BasicBlock &nextBB, int slotsToFill)
bool	checkIncomingDeps (MoveNode &mnOld, BasicBlockNode &blockToFillNode, int cycleDiff)
bool	tryToAssignNodes (MoveNodeListVector &moves, int slotsToFill, int firstCycleToFill, ResourceManager &rm, int nextBBStart, DataDependenceGraph::NodeSet &tempAssigns)
bool	tryToAssignOtherMovesOfDestOps (MoveNode &mn, int firstCycleToFill, ResourceManager &rm, int lastCycle, int nextBBStart, DataDependenceGraph::NodeSet &tempAssigns)
bool	tryToAssignOtherMovesOfOp (ProgramOperation &po, int firstCycleToFill, ResourceManager &rm, int lastCycle, int nextBBStart, DataDependenceGraph::NodeSet &tempAssigns)
void	unassignTempAssigns (DataDependenceGraph::NodeSet &tempAssigns, SimpleResourceManager &rm)
MoveNode &	getMoveNode (MoveNode &old, BasicBlockNode &bbn, bool fillOverBackEdge)
ProgramOperationPtr	getProgramOperationPtr (ProgramOperationPtr old, BasicBlockNode &bbn, bool fillOverBackEdge)
std::shared_ptr< TTAProgram::Move >	getMove (TTAProgram::Move &old)
bool	poMoved (ProgramOperationPtr po, MoveNodeListVector &movesToCopy, DataDependenceGraph::NodeSet &tempAssigns)
bool	allowedToSpeculate (MoveNode &mn) const
void	finishBB (BasicBlockNode &bbn, bool force=false)

Private Attributes
DataDependenceGraph *	ddg_
ControlFlowGraph *	cfg_
std::map< TTAProgram::BasicBlock *, SimpleResourceManager * >	resourceManagers_
UniversalMachine *	um_
std::map< ProgramOperation *, ProgramOperationPtr, ProgramOperation::Comparator >	programOperations_
std::map< ProgramOperation *, ProgramOperationPtr, ProgramOperation::Comparator >	oldProgramOperations_
std::map< MoveNode *, MoveNode *, MoveNode::Comparator >	moveNodes_
std::map< MoveNode *, MoveNode *, MoveNode::Comparator >	oldMoveNodes_
std::map< TTAProgram::Move *, std::shared_ptr< TTAProgram::Move > >	moves_
std::map< MoveNode *, const TTAMachine::Bus *, MoveNode::Comparator >	moveNodeBuses_
std::map< BasicBlockNode *, DataDependenceGraph::NodeSet >	tempResultNodes_
std::map< BasicBlockNode *, std::set< ProgramOperationPtr, ProgramOperation::Comparator > >	tempPOs_
std::map< MoveNode *, bool, MoveNode::Comparator >	mnOwned_
std::map< BasicBlockNode *, BBNStates >	bbnStatus_
int	delaySlots_
ControlFlowGraph::NodeSet	killedBBs_

Detailed Description

Definition at line 71 of file CopyingDelaySlotFiller.hh.

Member Typedef Documentation

MoveNodeListVector

typedef std::vector<std::list<MoveNode*> > CopyingDelaySlotFiller::MoveNodeListVector

private

Definition at line 105 of file CopyingDelaySlotFiller.hh.

PendingImmediateMap

typedef std::map<TCEString,TTAProgram::TerminalImmediate*> CopyingDelaySlotFiller::PendingImmediateMap

Definition at line 98 of file CopyingDelaySlotFiller.hh.

Member Enumeration Documentation

BBNStates

enum CopyingDelaySlotFiller::BBNStates

private

Enumerator
BBN_UNKNOWN
BBN_SCHEDULED
BBN_JUMP_FILLED
BBN_FALLTHRU_FILLED
BBN_BOTH_FILLED
BBN_TEMPS_CLEANED
BBN_ALL_DONE

Definition at line 209 of file CopyingDelaySlotFiller.hh.

                   { BBN_UNKNOWN = 0, BBN_SCHEDULED = 1, BBN_JUMP_FILLED = 3,
                     BBN_FALLTHRU_FILLED = 5, BBN_BOTH_FILLED = 7,
                     BBN_TEMPS_CLEANED = 15,
                     BBN_ALL_DONE = 31 };

Constructor & Destructor Documentation

CopyingDelaySlotFiller()

CopyingDelaySlotFiller::CopyingDelaySlotFiller

(

)

Constructor.

Definition at line 394 of file CopyingDelaySlotFiller.cc.

                                               {
}

~CopyingDelaySlotFiller()

CopyingDelaySlotFiller::~CopyingDelaySlotFiller

(

)

Destructor.

Definition at line 1692 of file CopyingDelaySlotFiller.cc.

                                                {
    assert(programOperations_.size() == 0);
    assert(moveNodes_.size() == 0);
    assert(mnOwned_.size() == 0);
    assert(moves_.size() == 0);
 
    //should not be needed but lets be sure
//    loseCopies();
}

References assert.

Member Function Documentation

addResourceManager()

void CopyingDelaySlotFiller::addResourceManager	(	TTAProgram::BasicBlock &	bbn,
		SimpleResourceManager &	rm
	)

Definition at line 691 of file CopyingDelaySlotFiller.cc.

                                              {
    resourceManagers_[&bb] = &rm;
    rm.setMaxCycle(INT_MAX);
}

References SimpleResourceManager::setMaxCycle().

Referenced by BBSchedulerController::executeDDGPass().

Here is the call graph for this function:

allowedToSpeculate()

bool CopyingDelaySlotFiller::allowedToSpeculate ( MoveNode &  mn ) const

private

Definition at line 2013 of file CopyingDelaySlotFiller.cc.

                                                                  {
    Move& move = mn.move();
    // TODO: allow even writes if the reg is not alive?
    if (!mn.isDestinationOperation()) {
        return false;
    }
    if (move.isTriggering()) {
        Operation& o = move.destination().operation();
        if (o.writesMemory() || o.hasSideEffects() ||
            o.affectsCount() != 0) {
            return false;
        }
 
        // also may not read memory, because the address may be invalid,
        // if the address comes with bypass from operation with different guard.
        if (o.readsMemory()) {
            if (mn.isSourceOperation() &&
                mn.sourceOperation().triggeringMove()->move().isUnconditional()) {
                return false;
            }
            // and if the address comes from a variable.
            if (mn.isSourceVariable()) {
                return false;
            }
        }
    }
    return true;
}

References Operation::affectsCount(), TTAProgram::Move::destination(), Operation::hasSideEffects(), MoveNode::isDestinationOperation(), MoveNode::isSourceOperation(), MoveNode::isSourceVariable(), TTAProgram::Move::isTriggering(), TTAProgram::Move::isUnconditional(), MoveNode::move(), TTAProgram::Terminal::operation(), Operation::readsMemory(), MoveNode::sourceOperation(), ProgramOperation::triggeringMove(), and Operation::writesMemory().

Here is the call graph for this function:

areAllJumpPredsFilled()

bool CopyingDelaySlotFiller::areAllJumpPredsFilled ( BasicBlockNode &  bbn ) const

private

Checks if all jumps into given basic blocks are filled.

Parameters

bbn	node to check for incoming filled jumps.

Returns

true if all incoming jumps are already filled.

Definition at line 470 of file CopyingDelaySlotFiller.cc.

                                                                            {
    bool allJumpPredsFilled = true;
    ControlFlowGraph::EdgeSet inEdges = cfg_->inEdges(bbn);
    for (ControlFlowGraph::EdgeSet::iterator inIter =
             inEdges.begin(); inIter != inEdges.end();
         inIter++) {
        ControlFlowEdge& cfe = **inIter;
        if (cfe.isJumpEdge()) {
            BasicBlockNode& jumpOrigin = cfg_->tailNode(cfe);
 
            // if some jump to the ft-node has not been scheduled.
            if (jumpOrigin.isNormalBB() &&
                (bbnStatus_[&jumpOrigin] < BBN_JUMP_FILLED ||
                 bbnStatus_[&jumpOrigin] == BBN_FALLTHRU_FILLED)) {
                allJumpPredsFilled = false;
            }
        }
    }
    return allJumpPredsFilled;
}

References ControlFlowEdge::isJumpEdge(), and BasicBlockNode::isNormalBB().

Here is the call graph for this function:

areAllJumpPredsScheduled()

bool CopyingDelaySlotFiller::areAllJumpPredsScheduled ( BasicBlockNode &  bbn ) const

private

Checks whether all incoming jump basic blocks are scheduled.

Parameters

bbn	basic block whose predecessors we are checking.

Returns

true if all BB's which jump into given BB are scheduled.

Definition at line 498 of file CopyingDelaySlotFiller.cc.

                                                                          {
    bool allPredsScheduled = true;
    ControlFlowGraph::EdgeSet inEdges = cfg_->inEdges(bbn);
    for (ControlFlowGraph::EdgeSet::iterator inIter =
             inEdges.begin(); inIter != inEdges.end();
         inIter++) {
        ControlFlowEdge& cfe = **inIter;
        if (cfe.isJumpEdge()) {
            BasicBlockNode& jumpOrigin = cfg_->tailNode(cfe);
 
            // if some jump to the ft-node has not been scheduled.
            if (bbnStatus_[&jumpOrigin] == BBN_UNKNOWN &&
                jumpOrigin.isNormalBB()) {
                allPredsScheduled = false;
            }
        }
    }
    return allPredsScheduled;
}

References ControlFlowEdge::isJumpEdge(), and BasicBlockNode::isNormalBB().

Here is the call graph for this function:

bbFilled()

void CopyingDelaySlotFiller::bbFilled ( BasicBlockNode &  bbn )

private

Executed after delay slots of a BB has been filled.

If both jump and fal-thru are filled, reletes the resource manager.

Definition at line 524 of file CopyingDelaySlotFiller.cc.

                                                    {
    if (bbnStatus_[&bbn] == BBN_BOTH_FILLED) {
        finishBB(bbn);
    }
}

bbnScheduled()

void CopyingDelaySlotFiller::bbnScheduled

(

BasicBlockNode &

bbn

)

Report to the ds filler that a bb has been scheduled.

tries to fill some delay slots and then tries to get rid of the resource managers when no longer needed.

addResourceManager() for the BB should be called before this method.

Parameters

bbn	BasicBlockNode which has been scheduled.

Definition at line 640 of file CopyingDelaySlotFiller.cc.

                                                        {
 
    assert(bbnStatus_[&bbn] == BBN_UNKNOWN);
    // if we don't have the RM got the bb, cannot really do much with it.
    if (resourceManagers_.find(&bbn.basicBlock())==resourceManagers_.end()) {
        return;
    }
 
    bbnStatus_[&bbn] = BBN_SCHEDULED;
 
    // all successors.
    ControlFlowGraph::EdgeSet oEdges = cfg_->outEdges(bbn);
 
    bool fillableSuccessor = false;
    for (ControlFlowGraph::EdgeSet::iterator outIter = oEdges.begin();
         outIter != oEdges.end();) {
        ControlFlowEdge& cfe = **outIter;
 
        // cannot fill calls.
        if (!cfe.isCallPassEdge()) {
            fillableSuccessor = true;
            auto& head = cfg_->headNode(cfe);
            if (mightFillIncomingTo(head)) {
                // the filling might have removed the BBN.
                if (!cfg_->hasNode(bbn)) {
                    return;
                }
                oEdges = cfg_->outEdges(bbn);
                outIter = oEdges.begin();
                continue;
            }
        }
        outIter++;
    }
 
    if (!fillableSuccessor && bbnStatus_[&bbn] != BBN_ALL_DONE) {
        finishBB(bbn);
    }
 
    // can fill incoming jumps if all incoming BBs scheduled.
    mightFillIncomingTo(bbn);
}

References assert, BasicBlockNode::basicBlock(), and ControlFlowEdge::isCallPassEdge().

Referenced by BBSchedulerController::handleBBNode().

Here is the call graph for this function:

checkImmediatesAfter()

bool CopyingDelaySlotFiller::checkImmediatesAfter ( TTAProgram::BasicBlock &  nextBB, int  slotsToFill  )

private

Checks that no later uses of long immediates written in instructions which are being filled to previous basic block.

Parameters

nextBB	The BB where to instructions are filled from
slotsToFill	how many slots are filled

Returns

true if everything ok, false if immediates prevent filling

Definition at line 1146 of file CopyingDelaySlotFiller.cc.

                                         {
    //check imm reads after (safeguard against same imm read twice)
    PendingImmediateMap pendingImmediateMap;
    
    for (int i = slotsToFill; i < nextBB.instructionCount(); i++) {
        Instruction& filler = nextBB.instructionAtIndex(i);
 
        // 0-latency immus
        for (int j = 0; j < filler.immediateCount(); j++) {
            TTAProgram::Immediate& imm = filler.immediate(j);
            const TTAProgram::Terminal& dst = imm.destination();
            const ImmediateUnit& immu = dst.immediateUnit();
            if (immu.latency() == 0) {
                TCEString immName = 
                    immu.name() + '.' + 
                    Conversion::toString(dst.index());
                if (pendingImmediateMap.find(immName) != 
                    pendingImmediateMap.end()) {
                    // same imm written twice without reading it. something wrong.
                    return false;
                }
                pendingImmediateMap[immName] = &imm.value();
            }
        } // imm loop
 
 
        for (int j=0; j < filler. moveCount(); j++) {
            Move& move = filler.move(j);
            if (move.source().isImmediateRegister()) {
                TTAProgram::Terminal& src = move.source();
                TCEString immName = 
                    src.immediateUnit().name() + '.'
                    + Conversion::toString(src.index());
                
                PendingImmediateMap::iterator immWriteIter =
                    pendingImmediateMap.find(immName);
 
                if (immWriteIter == pendingImmediateMap.end()) {
                    // read from immediate reg which ahs not been written
                    // after the filled instructions, ie the limm
                    // is at the instructions which are filled. do not allow 
                    return false;
                }
                pendingImmediateMap.erase(immWriteIter);
            }
        } // move loop
        
        // 1-latency immus
        for (int j = 0; j < filler.immediateCount(); j++) {
            TTAProgram::Immediate& imm = filler.immediate(j);
            const TTAProgram::Terminal& dst = imm.destination();
            const ImmediateUnit& immu = dst.immediateUnit();
            if (immu.latency() == 1) {
                TCEString immName = immu.name() + '.' + 
                    Conversion::toString(dst.index());
                if (pendingImmediateMap.find(immName) != 
                    pendingImmediateMap.end()) {
                    // same imm written twice without reading it. something wrong.
                    return false;
                }
                pendingImmediateMap[immName] = &imm.value();
            }
        } // imm loop
    } // instruction-loop
 
    // if immediates unbalanced at end of the bb. something wrong.
    if (!pendingImmediateMap.empty()) {
        return false;
    }
    return true;
}

References TTAProgram::Immediate::destination(), TTAProgram::Instruction::immediate(), TTAProgram::Instruction::immediateCount(), TTAProgram::Terminal::immediateUnit(), TTAProgram::Terminal::index(), TTAProgram::CodeSnippet::instructionAtIndex(), TTAProgram::CodeSnippet::instructionCount(), TTAProgram::Terminal::isImmediateRegister(), TTAMachine::ImmediateUnit::latency(), TTAProgram::Instruction::move(), TTAMachine::Component::name(), TTAProgram::Move::source(), Conversion::toString(), and TTAProgram::Immediate::value().

Here is the call graph for this function:

checkIncomingDeps()

bool CopyingDelaySlotFiller::checkIncomingDeps ( MoveNode &  mnOld, BasicBlockNode &  blockToFillNode, int  cycleDiff  )

private

Checks that no incoming deps prevent the filling, ie. no data hazards.

Parameters

mnOld	movenode which to fill from successor bb
blockToFillNode	block containing the jump being filled.
firstCycleToFill	index of first instruction where to fill

Returns

true if no data hazards, false if cannot fill.

Definition at line 1228 of file CopyingDelaySlotFiller.cc.

                                                                     {
    DataDependenceGraph::EdgeSet inEdges = ddg_->inEdges(mnOld);
    for (DataDependenceGraph::EdgeSet::iterator ieIter =
             inEdges.begin(); ieIter != inEdges.end(); ieIter++) {
        int mnCycle = mnOld.cycle();
        // slow
        DataDependenceEdge& ddEdge = **ieIter;
        MoveNode& pred = ddg_->tailNode(ddEdge);
        if (pred.isMove()) {
            BasicBlockNode& predBlock = ddg_->getBasicBlockNode(pred);
            if (!pred.isScheduled()) {
                continue;
            }
            
            if (&predBlock == &blockToFillNode) {
                int nodeCycle;
                int delay = 1;
                // guard latency.
                if (ddEdge.dependenceType() ==
                    DataDependenceEdge::DEP_WAR) {
                    if (ddEdge.guardUse()) {
                        delay = pred.guardLatency();
                    }
                    nodeCycle = pred.cycle() - delay+1;
                } else {
                    // if WAW, always 1
                    if (ddEdge.dependenceType() !=
                        DataDependenceEdge::DEP_WAW) {
                        if (ddEdge.guardUse()) {
                            delay = mnOld.guardLatency();
                        }
                    }
                    nodeCycle = pred.cycle()+delay;
                }
                if (nodeCycle > cycleDiff+mnCycle) {
                    return false;
                }
            }
        }
    }
    return true;
}

References MoveNode::cycle(), DataDependenceEdge::DEP_WAR, DataDependenceEdge::DEP_WAW, DataDependenceEdge::dependenceType(), MoveNode::guardLatency(), DataDependenceEdge::guardUse(), MoveNode::isMove(), and MoveNode::isScheduled().

Here is the call graph for this function:

collectMoves()

bool CopyingDelaySlotFiller::collectMoves ( BasicBlockNode &  blockToFillNode, BasicBlockNode &  nextBBN, MoveNodeListVector &  moves, int  slotsToFill, bool  fallThru, int  removeGuards, TTAProgram::Move *  jumpMove, int  grIndex, const TTAMachine::RegisterFile *  grFile, TTAProgram::Move *&  skippedJump, int  delaySlots  )

private

Collects are moves which are to be filled

Parameters

blockToFillNode	basic block node where to fill to
nextBBN	basic blocknode where to fill from
moves	place to store the collected nodes.
slotsToFill	how many delay slots to fill
fallThru	if filling fall-thru
removeGuards	how many first instructions need guard removed.
jumpMove	move which is the jump that is filled
grIndex	index of the guard register of the jump
grFile	register file of the guard of the jump.
skippedJump	if we can skip BB which jumps, sets the skipped jump here

Returns

true if collecting ok, false if failed

Definition at line 890 of file CopyingDelaySlotFiller.cc.

                                        {
    PendingImmediateMap pendingImmediateMap;
 
    ControlFlowEdge* connectingEdge =
        *cfg_->connectingEdges(blockToFillNode, nextBBN).begin();
    BasicBlock& bb = blockToFillNode.basicBlock();
    BasicBlock& nextBB = nextBBN.basicBlock();
    SimpleResourceManager& rm = *resourceManagers_[&bb];
    SimpleResourceManager& nextRm = *resourceManagers_[&nextBB];
 
    int firstIndexToFill = 
        blockToFillNode.basicBlock().instructionCount() - slotsToFill;
 
    int cycleDiff = firstIndexToFill + rm.smallestCycle() - nextRm.smallestCycle();
 
    // Find all moves to copy and check their dependencies.
    // Loop thru instructions first..
    for (int i = 0; i < slotsToFill; i++) {
        Instruction& filler = nextBB.instructionAtIndex(i);
        if (filler.hasCall()) {
            return false;
        }
 
        // loop through all 0-latency immediates fo the instr.
        for (int j = 0; j < filler.immediateCount(); j++) {
            // TODO: why immediates not allowed here? what about allowing
            // with 0-latency?
            if (&blockToFillNode == &nextBBN) {
                return false;
            }
 
            TTAProgram::Immediate& imm = filler.immediate(j);
            const TTAProgram::Terminal& dst = imm.destination();
            const ImmediateUnit& immu = dst.immediateUnit();
            if (immu.latency() == 0) {
                TCEString immName = immu.name() + '.' + 
                    Conversion::toString(dst.index());
                
                if (AssocTools::containsKey(pendingImmediateMap,immName)) {
                    // there already is write to this imm reg without
                    // a read to it? something is wrong, abort
                    return false;
                }
                pendingImmediateMap[immName] = &imm.value();
            }
        }
 
 
        // loop thru all moves in the instr
        for (int j = 0; j < filler.moveCount(); j++) {
            Move& oldMove = filler.move(j);
            bool dontGuard = i < removeGuards;
            // may fill jump if fills the whole BB and updates the jump.
            if (oldMove.isControlFlowMove()) {
                if (oldMove.isJump()) {
                    if (!oldMove.isUnconditional()) {
                        // TODO: if first was uncond jump, and filling whole BB,
                        // this could be allowed.
                        return false;
                    }
                    if (fallThru) {
                        // Allow another jump only to same instruction
                        // than where the filled jump is.
                        if (i != slotsToFill - delaySlots -1) {
                            return false;
                        }
                    } else {
                        if (slotsToFill != nextBB.instructionCount() ||
                            // TODO: find a way to find the source imm of this jump
                            // even if LIMM or tempregcopy.
                            // then no need to abort here.
                            oldMove.source().isGPR() ||
                            oldMove.source().isImmediateRegister()) {
                            return false;
                        }
                        if (oldMove.source().isRA()) {
                            // If updating jumpMove with RA, it may result to an
                            // illegal instruction due to missing connectivity.
                            if (jumpMove == nullptr
                                || !MachineConnectivityCheck::isConnected(
                                    jumpMove->bus(), oldMove.source().port())) {
                                return false;
                            }
                        }
                        skippedJump = &oldMove;
                        continue; // can be skipped
                    }
                } else { // unknown cflow op
                    return false;
                }
 
            }
 
            // TODO: should use guard latency here instead of -1
            // check if it overwrites the guard of the jump
            if (writesRegister(oldMove, grFile, grIndex)) {
                // overwriting the guard reg as last thing does not matter,
                // only allow it in last imported instruction.
                if (i != slotsToFill-1) {
                    return false;
                }
            }
            
            // do not allow delay slot filling of lbufs op.
            // this messes up at least the simulator.
            MoveNode& mnOld = ddg_->nodeOfMove(oldMove);
            if (mnOld.isDestinationOperation() &&
                mnOld.destinationOperation().operation().name() == "LBUFS"
                && slotsToFill != nextBB.instructionCount()) {
                return false;
            }
 
            // check all deps
            if (!oldMove.isUnconditional()) {
                // Do not fill with guarded moves, if jump is guarded,
                // might need 2 guards.
                // Only allowed if removing the guards anyway.
                if (jumpMove != NULL && !jumpMove->isUnconditional()) {
                    dontGuard = true;
                }
                // don't allow unconditionals before
                // BB start + guard latency (if guard written in last move
                // of previous BB)
                if (firstIndexToFill < mnOld.guardLatency()-1) {
                    return false;
                }
            }
 
            // if a move has no side effects, the guard can be omitted
            // and it can be scheduled before the guard is ready.
            if (dontGuard) {
                if (!allowedToSpeculate(mnOld)) {
                    return false;
                }
            } else {
                // guard with a portguard? then do not (yet) allow src op.
                if (jumpMove != NULL && !jumpMove->isUnconditional() &&
                    dynamic_cast<const PortGuard*>(&jumpMove->guard().guard())
                    && mnOld.isSourceOperation()) {
                    return false;
                }
            }
 
            // check DDG that no data hazards.
            if (!checkIncomingDeps(mnOld, blockToFillNode, cycleDiff)) {
                return false;
            }
 
            // also copies move
            MoveNode& mn = getMoveNode(
                mnOld, blockToFillNode, connectingEdge->isBackEdge());
            Move& newMove = mn.move();
 
            // reads immediate?
            if (newMove.source().isImmediateRegister()) {
                TTAProgram::Terminal& src = newMove.source();
                TCEString immName = 
                    src.immediateUnit().name() + '.'
                    + Conversion::toString(src.index());
                
                PendingImmediateMap::iterator immWriteIter =
                    pendingImmediateMap.find(immName);
 
                // if no write to the imm reg found, fail.
                if (immWriteIter == pendingImmediateMap.end()) {
                    return false;
                }
                newMove.setSource(immWriteIter->second->copy());
                pendingImmediateMap.erase(immWriteIter);
            }
 
            if (jumpMove != NULL && !jumpMove->isUnconditional() &&
                !dontGuard) {
                
                if (fallThru) {
                    auto g = CodeGenerator::createInverseGuard(jumpMove->guard());
                    assert(g != nullptr);
                    newMove.setGuard(g);
                } else {
                    newMove.setGuard(jumpMove->guard().copy());
                }
                if (dynamic_cast<const PortGuard*>(
                        &jumpMove->guard().guard())) {
                    // TODO: set guard op from the jump?
                    MoveNode& jumpNode = ddg_->nodeOfMove(*jumpMove);
                    auto guardOp = jumpNode.guardOperationPtr();
                    guardOp->addGuardOutputNode(mn);
                    mn.setGuardOperationPtr(guardOp);
                }
 
                MoveNode& jumpNode = ddg_->nodeOfMove(*jumpMove);
                ddg_->copyIncomingGuardEdges(jumpNode, mn);
            }
            moves.at(i).push_back(&mn);
        } // move-loop
 
        for (int j = 0; j < filler.immediateCount(); j++) {
            if (&blockToFillNode == &nextBBN) {
                return false;
            }
 
            TTAProgram::Immediate& imm = filler.immediate(j);
            const TTAProgram::Terminal& dst = imm.destination();
            const ImmediateUnit& immu = dst.immediateUnit();
            if (immu.latency() == 1) {
                TCEString immName = immu.name() + '.' + 
                    Conversion::toString(dst.index());
                
                if (AssocTools::containsKey(pendingImmediateMap,immName)) {
                    // there already is write to this imm reg without
                    // a read to it? something is wrong, abort
                    return false;
                }
                pendingImmediateMap[immName] = &imm.value();
            }
        }
    }
 
    // make sure long guard latencies dont cause trouble with following instructions.
    if (nextBB.instructionCount() > slotsToFill) {
        Instruction& firstNotToFill = nextBB.instructionAtIndex(slotsToFill);
        // loop thru all moves in the instr
        for (int j = 0; j < firstNotToFill.moveCount(); j++) {
            Move& move = firstNotToFill.move(j);
            if (move.isUnconditional()) {
                break;
            }
        
            MoveNode& mn = ddg_->nodeOfMove(move);
        
            // check DDG that no data hazards.
            if (!checkIncomingDeps(mn, blockToFillNode, cycleDiff)) {
                return false;
            }
        }
    }
 
    // ok if no pending immediates (ie limm written, not read)
    return pendingImmediateMap.empty();
}

References assert, BasicBlockNode::basicBlock(), TTAProgram::Move::bus(), AssocTools::containsKey(), TTAProgram::MoveGuard::copy(), TTAProgram::CodeGenerator::createInverseGuard(), TTAProgram::Immediate::destination(), MoveNode::destinationOperation(), TTAProgram::MoveGuard::guard(), TTAProgram::Move::guard(), MoveNode::guardLatency(), MoveNode::guardOperationPtr(), TTAProgram::Instruction::hasCall(), TTAProgram::Instruction::immediate(), TTAProgram::Instruction::immediateCount(), TTAProgram::Terminal::immediateUnit(), TTAProgram::Terminal::index(), TTAProgram::CodeSnippet::instructionAtIndex(), TTAProgram::CodeSnippet::instructionCount(), ControlFlowEdge::isBackEdge(), MachineConnectivityCheck::isConnected(), TTAProgram::Move::isControlFlowMove(), MoveNode::isDestinationOperation(), TTAProgram::Terminal::isGPR(), TTAProgram::Terminal::isImmediateRegister(), TTAProgram::Move::isJump(), TTAProgram::Terminal::isRA(), MoveNode::isSourceOperation(), TTAProgram::Move::isUnconditional(), TTAMachine::ImmediateUnit::latency(), TTAProgram::Instruction::move(), MoveNode::move(), TTAProgram::Instruction::moveCount(), TTAMachine::Component::name(), Operation::name(), ProgramOperation::operation(), TTAProgram::Terminal::port(), TTAProgram::Move::setGuard(), MoveNode::setGuardOperationPtr(), TTAProgram::Move::setSource(), SimpleResourceManager::smallestCycle(), TTAProgram::Move::source(), Conversion::toString(), and TTAProgram::Immediate::value().

Here is the call graph for this function:

fillDelaySlots() [1/2]

bool CopyingDelaySlotFiller::fillDelaySlots ( BasicBlockNode &  jumpingBB, int  delaySlots, bool  fillFallThru  )

protected

Fill delay slots of given BB.

Parameters

jumpingBB	BB to fill delay slots.
delaySlots	number of delay slots in the machine.
fillFallThru	fill from Fall-thru of jump BB?

Definition at line 88 of file CopyingDelaySlotFiller.cc.

                                                                  {
    if (cfg_->hasMultipleUnconditionalSuccessors(jumpingBB)) {
        bbnStatus_[&jumpingBB] = BBN_BOTH_FILLED;
        return false;
    }
 
    // do not try to fill loop scheduled, also skip epilog and prolog.
    if (jumpingBB.isLoopScheduled() || jumpingBB.isHWLoop()) {
        bbnStatus_[&jumpingBB] = BBN_BOTH_FILLED;
        return false;
    }
 
    bool cfgChanged = false;
 
    if (fillFallThru) {
        switch (bbnStatus_[&jumpingBB]) {
        case BBN_SCHEDULED:
            bbnStatus_[&jumpingBB] = BBN_FALLTHRU_FILLED;
            break;
        case BBN_JUMP_FILLED:
            bbnStatus_[&jumpingBB] = BBN_BOTH_FILLED;
            break;
        default:
            assert(false);
        }
    } else {
        switch (bbnStatus_[&jumpingBB]) {
        case BBN_SCHEDULED:
            bbnStatus_[&jumpingBB] = BBN_JUMP_FILLED;
            break;
        case BBN_FALLTHRU_FILLED:
            bbnStatus_[&jumpingBB] = BBN_BOTH_FILLED;
            break;
        default:
            assert(false);
        }
    }
    
    ControlFlowGraph::EdgeSet outEdges = cfg_->outEdges(jumpingBB);
 
    InstructionReferenceManager& irm =
        cfg_->program()->instructionReferenceManager();
 
    TTAProgram::BasicBlock& thisBB = jumpingBB.basicBlock();
    std::pair<int, TTAProgram::Move*> jumpData = findJump(thisBB);
    std::pair<Move*, std::shared_ptr<Immediate> > jumpAddressData;
 
    // should be the same
    int jumpIndex = jumpData.first;
    Move* jumpMove = jumpData.second;
 
    // need for imm source only if filling jump, not imm.
    if (!fillFallThru) {
        // jump needed only when filling jump, not fall-thru.
        // not found?
        if (jumpMove == NULL) {
            return false;
        }
 
        if (!jumpMove->source().isInstructionAddress()) {
            // address comes from LIMM, search the write to limm reg.
            jumpAddressData = findJumpImmediate(jumpIndex, *jumpMove, irm);
            if (jumpAddressData.first == NULL && 
                jumpAddressData.second == NULL) {
                //Imm source not found, aborting
                return false;
            }
        } else {
            jumpAddressData.first = jumpMove;
        }
    }
 
    const RegisterFile* grFile = NULL;
    unsigned int grIndex = 0;
 
    // lets be aggressive, fill more than just branch slots?
    int maxFillCount = std::min(
        delaySlots + 12,
        thisBB.instructionCount() - thisBB.skippedFirstInstructions());
 
    int maxGuardedFillCount = 0;
 
    // if we have references to instructions in target BB, cannot put anything
    // before them, so limit how many slots to fill at maximum.
    for (int i = 1 ; i < thisBB.instructionCount(); i++) {
        if (irm.hasReference(thisBB.instructionAtIndex(i))) {
            maxFillCount = std::min(maxFillCount, thisBB.instructionCount()-i);
        }
    }
 
    // if we have conditional jump, find the predicate register
    if (jumpMove != NULL && !jumpMove->isUnconditional()) {
        maxGuardedFillCount = INT_MAX;
        const Guard& g = jumpMove->guard().guard();
        const RegisterGuard* rg = dynamic_cast<const RegisterGuard*>(&g);
        if (rg != NULL) {
            grFile = rg->registerFile();
            grIndex = rg->registerIndex();
        }
 
        // find when the predicate reg is written to and use that
        // to limit how many to bypass.
        MoveNode& jumpNode = ddg_->nodeOfMove(*jumpMove);
        DataDependenceGraph::NodeSet guardDefs =
            ddg_->guardDefMoves(jumpNode);
        if (guardDefs.size() != 1) {
            // many defs, don't know which is the critical one.
            // fill only slots+jump ins
            maxGuardedFillCount = std::min(maxGuardedFillCount,delaySlots+1);
        } else {
            MoveNode& guardDefMove = **guardDefs.begin();
            if (&ddg_->getBasicBlockNode(guardDefMove) == &jumpingBB) {
                SimpleResourceManager& rm = 
                    *resourceManagers_[&jumpingBB.basicBlock()];
                
                int earliestToFill = guardDefMove.cycle() -
                    rm.smallestCycle() +
                    jumpNode.guardLatency();
                
                maxGuardedFillCount =
                    std::min(maxGuardedFillCount,
                             thisBB.instructionCount() - earliestToFill);
            } else {
                // guard written in previous BB?
                // make sure not filled to first insrt if
                // guard latency 2
                maxGuardedFillCount =
                    std::min(maxGuardedFillCount,
                             thisBB.instructionCount() -
                             std::max(0,jumpNode.guardLatency()-1));
            }
        }
    } // jump conditional
 
    // 1 or two items, big loop. These may come in either order, grr.
    for (ControlFlowGraph::EdgeSet::iterator iter = outEdges.begin();
         iter != outEdges.end(); iter++) {
        int slotsFilled = 0;
        int myMaxGuardedFillCount = maxGuardedFillCount;
 
        ControlFlowEdge& edge = **iter;
        if (edge.isFallThroughEdge() != fillFallThru) {
            continue;
        }
        if (edge.isCallPassEdge()) {
            continue;
        }
 
        BasicBlockNode& nextBBN = cfg_->headNode(edge);
 
        // cannot fill if the next is not normal BB.
        if (!nextBBN.isNormalBB() || nextBBN.isLoopScheduled() ||
            nextBBN.isHWLoop()) {
            continue;
        }
 
        int nextInsCount = nextBBN.basicBlock().instructionCount();
        if (&nextBBN == &jumpingBB) {
            // jump to itself. may not fill from instructions 
            // which are itself being filled.
            maxFillCount = std::min(maxFillCount, nextInsCount/2);
        } else {
            // otherwise may fill all other target bb
            maxFillCount = std::min(maxFillCount,nextInsCount);
        }
 
        if (fillFallThru) {
            if (jumpMove != NULL) {
                // test that we can create an inverse guard
                if (jumpMove->isUnconditional()) {
                    continue;
                }
                MoveGuard* invG = CodeGenerator::createInverseGuard(
                    jumpMove->guard());
                if (invG == NULL) {
                    myMaxGuardedFillCount = 0;
                } else {
                    delete invG;
                }
            }
 
            // cannot remove ins if it has refs.
            // -> cannot fill fall instrs which have refs
            for (int i = 0; i < maxFillCount; i++) {
                if (irm.hasReference(
                        nextBBN.basicBlock().instructionAtIndex(i))) {
                    maxFillCount = i;
                }
            }
        }
 
        if (maxFillCount == 0) {
            continue;
        }
 
        // register copy added leaves some inter-bb edges..
        // TODO: remove when registercopyadder handles
        // inter-BB-antideps..
 
        // also delay slot filler itself does not create
        // all edges, at least if filling fall-thru jumps.
        // so always run the routine until fixed,
        // if-fall-thru jumps enabled.
 
        // temporaty solution: fix only if temp reg adder effective
//        if (!fullyConnected) {
        ddg_->fixInterBBAntiEdges(jumpingBB, nextBBN, edge.isBackEdge());
//        }
 
        Move* skippedJump;
        // also try to fill into jump instruction.
        // fillSize = delaySlots still adpcm-3-full-fails, should be +1
        for (int fillSize = maxFillCount; fillSize > 0; fillSize--) {
            int removeGuards = (fillSize > myMaxGuardedFillCount) ?
                fillSize - myMaxGuardedFillCount : 0;
            // then try to do the filling.
            bool ok = tryToFillSlots(
                jumpingBB, nextBBN, fillFallThru, jumpMove, fillSize,
                removeGuards, grIndex, grFile, skippedJump, delaySlots);
            if (ok) {
                slotsFilled = fillSize;
                break;
            }
        }
 
        // filled some slots?
        if (slotsFilled != 0) {
 
            // filled from jump dest or fal-thru?
            if (!fillFallThru) {
                // have to update jump destination
                cfgChanged |= updateJumpsAndCfg(
                    jumpingBB, nextBBN, edge, jumpAddressData.first,
                    jumpAddressData.second, jumpMove, slotsFilled, 
                    skippedJump);
            } else { // fall-thru, skip first instructions.
                cfgChanged |= updateFTBBAndCfg(
                    jumpingBB, nextBBN, edge, slotsFilled);
            }
        }
    }
    return cfgChanged;
}

References assert, BasicBlockNode::basicBlock(), TTAProgram::CodeGenerator::createInverseGuard(), MoveNode::cycle(), TTAProgram::MoveGuard::guard(), TTAProgram::Move::guard(), MoveNode::guardLatency(), TTAProgram::InstructionReferenceManager::hasReference(), TTAProgram::CodeSnippet::instructionAtIndex(), TTAProgram::CodeSnippet::instructionCount(), ControlFlowEdge::isBackEdge(), ControlFlowEdge::isCallPassEdge(), ControlFlowEdge::isFallThroughEdge(), BasicBlockNode::isHWLoop(), TTAProgram::Terminal::isInstructionAddress(), BasicBlockNode::isLoopScheduled(), BasicBlockNode::isNormalBB(), TTAProgram::Move::isUnconditional(), TTAMachine::RegisterGuard::registerFile(), TTAMachine::RegisterGuard::registerIndex(), TTAProgram::BasicBlock::skippedFirstInstructions(), SimpleResourceManager::smallestCycle(), and TTAProgram::Move::source().

Here is the call graph for this function:

fillDelaySlots() [2/2]

void CopyingDelaySlotFiller::fillDelaySlots	(	ControlFlowGraph &	cfg,
		DataDependenceGraph &	ddg,
		const TTAMachine::Machine &	machine
	)

Fills all delay slots for all BB's in the CFG.

Parameters

cfg	ControlFlowGraph where to fill delay slots.
ddg	DataDependenceGraph containing data dependencies.

Definition at line 405 of file CopyingDelaySlotFiller.cc.

                                      {
    um_ = &UniversalMachine::instance();
    int delaySlots = machine.controlUnit()->delaySlots();
 
    cfg_ = &cfg;
    ddg_ = &ddg;
 
    // first fill only jumps
    for (int i = 0; i < cfg.nodeCount(); i++) {
        BasicBlockNode& bbn = cfg.node(i);
        if (bbn.isNormalBB()) {
            if (bbnStatus_[&bbn] == BBN_SCHEDULED ||
                bbnStatus_[&bbn] == BBN_FALLTHRU_FILLED) {
                fillDelaySlots(
                    bbn, delaySlots, false);
            }
        }
    }
 
    // then fill only fall-thru's.
    for (int i = 0; i < cfg.nodeCount(); i++) {
        BasicBlockNode& bbn = cfg.node(i);
        if (bbn.isNormalBB()) {
            if (bbnStatus_[&bbn] == BBN_JUMP_FILLED) {
                fillDelaySlots(
                    bbn, delaySlots, true);
            }
        }
    }
 
    // All is done. Then get rid of data which is no longer needed.
    for (std::map<BasicBlockNode*, BBNStates>::iterator i = 
             bbnStatus_.begin(); i != bbnStatus_.end(); i++) {
        if (i->second != BBN_ALL_DONE) {
            // todo: why is true required here
            finishBB(*i->first); //, true);
        }
    }
    // TODO: why is this not empty? finishBB should clear these.
    for (std::map<BasicBlock*, SimpleResourceManager*>::iterator i =
             resourceManagers_.begin(); i != resourceManagers_.end(); i++) {
        if (i->second != NULL) {
            SimpleResourceManager::disposeRM(i->second);
        }
    }
    resourceManagers_.clear();
//    assert(resourceManagers_.empty());
    tempResultNodes_.clear();
}

References TTAMachine::Machine::controlUnit(), TTAMachine::ControlUnit::delaySlots(), SimpleResourceManager::disposeRM(), UniversalMachine::instance(), BasicBlockNode::isNormalBB(), machine, BoostGraph< GraphNode, GraphEdge >::node(), and BoostGraph< GraphNode, GraphEdge >::nodeCount().

Referenced by llvm::LLVMTCEIRBuilder::compileOptimized(), and BBSchedulerController::handleProcedure().

Here is the call graph for this function:

finalizeProcedure()

void CopyingDelaySlotFiller::finalizeProcedure

(

)

Deletes all removed basic blocks. Can be called after bigddg is deleted.

Definition at line 460 of file CopyingDelaySlotFiller.cc.

                                               {
    AssocTools::deleteAllItems(killedBBs_);
}

References AssocTools::deleteAllItems().

Referenced by BBSchedulerController::handleProcedure().

Here is the call graph for this function:

findJump()

std::pair< int, TTAProgram::Move * > CopyingDelaySlotFiller::findJump ( TTAProgram::BasicBlock &  bb, ControlFlowEdge::CFGEdgePredicate *  pred = nullptr  )

static

Finds the jump move and the index of the instruction where it is from a basic block.

Parameters

bb	basicBlock where to search the jump move

Definition at line 1751 of file CopyingDelaySlotFiller.cc.

                                                                     {
 
    for (int i = bb.instructionCount()-1; i >= 0; i--) {
        Instruction& ins = bb.instructionAtIndex(i);
        for (int j = 0; j < ins.moveCount(); j++ ) {
            Move& move = ins.move(j);
            if (move.isJump()) {
                if (pred == nullptr) {
                    return std::pair<int, TTAProgram::Move*>(i, &move);
                }
                if (move.isUnconditional()) {
                    if (*pred == ControlFlowEdge::CFLOW_EDGE_NORMAL) {
                        return std::pair<int, TTAProgram::Move*>(i, &move);
                    }
                } else {
                    auto& guard = move.guard().guard();
                    if ((*pred == ControlFlowEdge::CFLOW_EDGE_FALSE)
                        == (guard.isInverted())) {
                        return std::pair<int, TTAProgram::Move*>(i, &move);
                    }
                }
            }
        }
        //cal not handled
        if (ins.hasCall()) {
            return std::pair<int, TTAProgram::Move*>(-1,NULL);
        }
    }
    // not found.
    return std::pair<int, TTAProgram::Move*>(-1,NULL);
}

References ControlFlowEdge::CFLOW_EDGE_FALSE, ControlFlowEdge::CFLOW_EDGE_NORMAL, TTAProgram::MoveGuard::guard(), TTAProgram::Move::guard(), TTAProgram::Instruction::hasCall(), TTAProgram::CodeSnippet::instructionAtIndex(), TTAProgram::CodeSnippet::instructionCount(), TTAProgram::Move::isJump(), TTAProgram::Move::isUnconditional(), TTAProgram::Instruction::move(), and TTAProgram::Instruction::moveCount().

Referenced by LoopPrologAndEpilogBuilder::moveJumpDestination().

Here is the call graph for this function:

findJumpImmediate()

std::pair< TTAProgram::Move *, std::shared_ptr< TTAProgram::Immediate > > CopyingDelaySlotFiller::findJumpImmediate ( int  jumpIndex, TTAProgram::Move &  jumpMove, TTAProgram::InstructionReferenceManager &  irm  )

static

Finds the immediate which contains the jump address.

Parameters

jumpIndex	index of the instruction containin the jump in the BB.
jumpMove	the move containing the jump.

Returns

Immediate containing jump address or NULL if not found.

Definition at line 705 of file CopyingDelaySlotFiller.cc.

                                                                     {
    BasicBlock& bb = static_cast<BasicBlock&>(jumpMove.parent().parent());
    Move* irMove = &jumpMove;
    int irIndex = jumpIndex;
 
    // Register copy or some unknown source.
    // should handle unlimited number of reg. copies.
    // Note: the jump address can be written outside the BB
    // if it's an indirect branch (e.g. LLVM address of label
    // extension).
    if (irMove->source().isGPR()) {
        const RegisterFile* rf = &irMove->source().registerFile();
        int regIndex = static_cast<int>(irMove->source().index());
        int found = false;
        int i;
        // if has refernces, the imm may be written in another BB.
        // we can not (yet) track that!
        if (irm.hasReference(bb.instructionAtIndex(irIndex))) {
            return std::pair<Move*,std::shared_ptr<Immediate> >(nullptr, nullptr);
        }
        for (i = irIndex -1 ; i >= bb.skippedFirstInstructions() && !found; 
             i-- ) {
            Instruction &ins = bb.instructionAtIndex(i);
            // if has refernces, the imm may be written in another BB.
            // we can not (yet) track that!
            if (irm.hasReference(ins)) {
                return std::pair<Move*,std::shared_ptr<Immediate> >(
                    nullptr, nullptr);
            }
            for (int j = 0; j < ins.moveCount(); j++ ) {
                Move& move = ins.move(j);
                if (move.destination().isGPR()) {
                    if (&move.destination().registerFile() == rf &&
                        move.destination().index() == regIndex) {
                        irMove = &move;
                        irIndex = i;
                        found = true;
                        break;
                    } 
                }
            }
        }
        // jump imm not found.
        if (i < bb.skippedFirstInstructions() && !found) {
            return std::pair<Move*,std::shared_ptr<Immediate> >(
                nullptr, nullptr);
        }
    }
    if (irMove->source().isImmediate()) {
        return std::pair<Move*,std::shared_ptr<Immediate> >(irMove, nullptr);
    }
 
    // then read the actual immediate
    if (irMove->source().isImmediateRegister()) {
        const ImmediateUnit& immu = irMove->source().immediateUnit();
        int index = static_cast<int>(irMove->source().index());
        for (int i = irIndex - immu.latency(); i >= 0; i--) {
            Instruction &ins = bb.instructionAtIndex(i);
            for (int j = 0; j < ins.immediateCount(); j++) {
                auto imm = ins.immediatePtr(j);
                if (imm->destination().index() == index &&
                    &imm->destination().immediateUnit() == &immu) {
                    return std::pair<Move*,std::shared_ptr<Immediate> >(
                        nullptr, imm);
                }
            }
            // if has refernces, the imm may be written in another BB.
            // we can not (yet) track that!
            if (irm.hasReference(ins)) {
                return std::pair<Move*,std::shared_ptr<Immediate> >(
                    nullptr, nullptr);
            }
        }
    }
    return std::pair<Move*, std::shared_ptr<Immediate> >(nullptr, nullptr);
}

References TTAProgram::Move::destination(), TTAProgram::InstructionReferenceManager::hasReference(), TTAProgram::Instruction::immediateCount(), TTAProgram::Instruction::immediatePtr(), TTAProgram::Terminal::immediateUnit(), TTAProgram::Terminal::index(), TTAProgram::CodeSnippet::instructionAtIndex(), TTAProgram::Terminal::isGPR(), TTAProgram::Terminal::isImmediate(), TTAProgram::Terminal::isImmediateRegister(), TTAMachine::ImmediateUnit::latency(), TTAProgram::Instruction::move(), TTAProgram::Instruction::moveCount(), TTAProgram::Move::parent(), TTAProgram::Instruction::parent(), TTAProgram::Terminal::registerFile(), TTAProgram::BasicBlock::skippedFirstInstructions(), and TTAProgram::Move::source().

Referenced by LoopPrologAndEpilogBuilder::moveJumpDestination().

Here is the call graph for this function:

finishBB()

void CopyingDelaySlotFiller::finishBB ( BasicBlockNode &  bbn, bool  force = false  )

private

Definition at line 1949 of file CopyingDelaySlotFiller.cc.

                                                                {
 
    std::map<BasicBlockNode*,DataDependenceGraph::NodeSet>::iterator
        i = tempResultNodes_.find(&bbn);
 
    if (i != tempResultNodes_.end()) {
        DataDependenceGraph::NodeSet& ns = i->second;
        if (!ns.empty()) {
            std::map<BasicBlock*,SimpleResourceManager*>::iterator rmi =
                resourceManagers_.find(&i->first->basicBlock());
            assert (rmi != resourceManagers_.end());
            SimpleResourceManager& rm = *rmi->second;
            unassignTempAssigns(ns, rm);
        }
    }
 
    bbnStatus_[&bbn] = BBN_TEMPS_CLEANED;
 
    if (!force) {
        // all predecessors. If some not scheduled, do not yet remove the  rm.
        // then stay in state BBN_TEMPS_CLEANED;
        ControlFlowGraph::EdgeSet iEdges = cfg_->inEdges(bbn);
        
        for (ControlFlowGraph::EdgeSet::iterator inIter = iEdges.begin();
             inIter != iEdges.end(); inIter++) {
            ControlFlowEdge& cfe = **inIter;
            // cannot fill calls.
            if (!cfe.isCallPassEdge()) {
                BasicBlockNode& prevBBN = cfg_->tailNode(cfe);
                if (prevBBN.isNormalBB() && 
                    bbnStatus_[&prevBBN] < BBN_BOTH_FILLED) {
                    return;
                }
            }
        }
    }
 
    // delete the RM. go to state BBN_ALL_DONE
    std::map<BasicBlock*,SimpleResourceManager*>::iterator rmi =
        resourceManagers_.find(&bbn.basicBlock());
    if (rmi != resourceManagers_.end()) {
        if (rmi->second != NULL) {
            SimpleResourceManager::disposeRM(rmi->second);
        }
        resourceManagers_.erase(rmi);
    }
    bbnStatus_[&bbn] = BBN_ALL_DONE;
 
}

References assert, BasicBlockNode::basicBlock(), SimpleResourceManager::disposeRM(), ControlFlowEdge::isCallPassEdge(), and BasicBlockNode::isNormalBB().

Here is the call graph for this function:

getMove()

std::shared_ptr< Move > CopyingDelaySlotFiller::getMove ( TTAProgram::Move &  old )

private

Gets a corresponding move to a given move in the next BB.

If no corresponding move created, creates one

Parameters

old	Move in jump target BB.

Returns

new Move for this BB.

Definition at line 1578 of file CopyingDelaySlotFiller.cc.

                                         {
    if (AssocTools::containsKey(moves_,&old)) {
        return moves_[&old];
    } else {
        MoveNode& oldMN = ddg_->nodeOfMove(old);
 
        auto newMove = old.copy();
        newMove->setBus(um_->universalBus());
 
        Terminal& source = newMove->source();
        if (oldMN.isSourceOperation()) {
            assert(source.isFUPort());
            std::string fuName = source.functionUnit().name();
        //TODO: which is the correct annotation here?
            TTAProgram::ProgramAnnotation srcUnit(
                TTAProgram::ProgramAnnotation::ANN_CONN_CANDIDATE_UNIT_SRC,
                fuName);
            newMove->setAnnotation(srcUnit);
 
            const Operation &srcOp = oldMN.sourceOperation().operation();
            HWOperation& hwop = *um_->universalFunctionUnit().operation(
                srcOp.name());
            newMove->setSource(new TerminalFUPort(
                                   hwop, old.source().operationIndex()));
        } else {
            if (source.isRA()) {
                newMove->setSource(
                    new TerminalFUPort(
                        *um_->controlUnit()->returnAddressPort()));
            }
        }
 
        Terminal& dest = newMove->destination();
        if (oldMN.isDestinationOperation()) {
            assert(dest.isFUPort());
 
            std::string fuName = dest.functionUnit().name();
        //TODO: which is the correct annotation here?
            TTAProgram::ProgramAnnotation dstUnit(
                TTAProgram::ProgramAnnotation::ANN_CONN_CANDIDATE_UNIT_DST, 
                fuName);
            newMove->setAnnotation(dstUnit);
 
            const Operation &dstOp = oldMN.destinationOperation().operation();
            HWOperation& hwop = *um_->universalFunctionUnit().operation(
                dstOp.name());
            newMove->setDestination(new TerminalFUPort(
                                   hwop, old.destination().operationIndex()));
        } else {
            if (dest.isRA()) {
                newMove->setDestination(
                    new TerminalFUPort(
                        *um_->controlUnit()->returnAddressPort()));
            }
        }
 
 
        moves_[&old] = newMove;
 
        // set guard of new move to be same as old move.
        if (!old.isUnconditional()) {
            TTAProgram::MoveGuard* g = old.guard().copy();
            newMove->setGuard(g);
        }
        return newMove;
    }
}

References TTAProgram::ProgramAnnotation::ANN_CONN_CANDIDATE_UNIT_DST, TTAProgram::ProgramAnnotation::ANN_CONN_CANDIDATE_UNIT_SRC, assert, AssocTools::containsKey(), TTAProgram::MoveGuard::copy(), TTAProgram::Move::copy(), TTAProgram::Move::destination(), MoveNode::destinationOperation(), TTAProgram::Terminal::functionUnit(), TTAProgram::Move::guard(), MoveNode::isDestinationOperation(), TTAProgram::Terminal::isFUPort(), TTAProgram::Terminal::isRA(), MoveNode::isSourceOperation(), TTAProgram::Move::isUnconditional(), TTAMachine::Component::name(), Operation::name(), ProgramOperation::operation(), TTAProgram::Terminal::operationIndex(), TTAProgram::Move::source(), and MoveNode::sourceOperation().

Here is the call graph for this function:

getMoveNode()

MoveNode & CopyingDelaySlotFiller::getMoveNode ( MoveNode &  old, BasicBlockNode &  bbn, bool  fillOverBackEdge  )

private

Gets a corresponding MoveNode a given move in the next BB.

If no corresponding MoveNode created, creates one

Parameters

old	ProgramOperation in jump target BB.

Returns

new MoveNode for this BB.

Definition at line 1497 of file CopyingDelaySlotFiller.cc.

                                                               {
    if (AssocTools::containsKey(moveNodes_,&old)) {
        return *moveNodes_[&old];
    } else {
        auto movePtr = getMove(old.move());
        MoveNode *newMN = new MoveNode(movePtr);
        ddg_->addNode(*newMN, bbn);
        ddg_->copyDependencies(old,*newMN, false, fillOverBackEdge);
        moveNodeBuses_[newMN] = &old.move().bus();
 
        moveNodes_[&old] = newMN;
        oldMoveNodes_[newMN] = &old;
        mnOwned_[newMN] = true;
        if (old.isSourceOperation()) {
            newMN->setSourceOperationPtr(
                getProgramOperationPtr(
                    old.sourceOperationPtr(), bbn, fillOverBackEdge));
            assert(newMN->isSourceOperation());
        }
        if (old.isGuardOperation()) {
            newMN->setGuardOperationPtr(
                getProgramOperationPtr(old.guardOperationPtr(), bbn, fillOverBackEdge));
        }
        if (old.isDestinationOperation()) {
            for (unsigned int i = 0; i < old.destinationOperationCount(); i++) {
                newMN->addDestinationOperationPtr(
                    getProgramOperationPtr(
                        old.destinationOperationPtr(i), bbn, fillOverBackEdge));
            }
            assert(newMN->isDestinationOperation());
        }
        return *newMN;
    }
}

References MoveNode::addDestinationOperationPtr(), assert, TTAProgram::Move::bus(), AssocTools::containsKey(), MoveNode::destinationOperationCount(), MoveNode::destinationOperationPtr(), MoveNode::guardOperationPtr(), MoveNode::isDestinationOperation(), MoveNode::isGuardOperation(), MoveNode::isSourceOperation(), MoveNode::move(), MoveNode::setGuardOperationPtr(), MoveNode::setSourceOperationPtr(), and MoveNode::sourceOperationPtr().

Here is the call graph for this function:

getProgramOperationPtr()

ProgramOperationPtr CopyingDelaySlotFiller::getProgramOperationPtr ( ProgramOperationPtr  old, BasicBlockNode &  bbn, bool  fillOverBackEdge  )

private

Gets a corresponding ProgramOperation to a given move in the next BB.

If no corresponding ProgramOperation created, creates one

Parameters

old	ProgramOperation in jump target BB.

Returns

new ProgramOperation for this BB.

Definition at line 1542 of file CopyingDelaySlotFiller.cc.

                                                                         {
    if (AssocTools::containsKey(programOperations_, old.get())) {
        return programOperations_[old.get()];
    } else {
        ProgramOperationPtr po = 
            ProgramOperationPtr(
                new ProgramOperation(old->operation()));
        programOperations_[old.get()] = po;
        oldProgramOperations_[po.get()] = old;
        for (int i = 0; i < old->inputMoveCount();i++) {
            MoveNode& mn = old->inputMove(i);
            assert(mn.isDestinationOperation());
            po->addInputNode(getMoveNode(mn, bbn, fillOverBackEdge));
        }
        for (int j = 0; j < old->outputMoveCount();j++) {
            MoveNode& mn = old->outputMove(j);
            if (mn.isSourceOperation()) {
                po->addOutputNode(getMoveNode(mn,bbn,fillOverBackEdge));
            } else {
                po->addGuardOutputNode(getMoveNode(mn,bbn, fillOverBackEdge));
            }
        }
        return po;
    }
}

References assert, AssocTools::containsKey(), MoveNode::isDestinationOperation(), and MoveNode::isSourceOperation().

Here is the call graph for this function:

initialize()

void CopyingDelaySlotFiller::initialize	(	ControlFlowGraph &	cfg,
		DataDependenceGraph &	ddg,
		const TTAMachine::Machine &	machine
	)

Initializes the delay slot filler for given procedure.

Has to be called before it can be used.

Parameters

cfg	ControlFlowGraph of the procedure. @ddg ddg whole-procedure ddg of the procedure.
machine	machine we are scheduling to.
um	universalmachine.

Definition at line 1937 of file CopyingDelaySlotFiller.cc.

                                      {
    cfg_ = &cfg;
    ddg_ = &ddg;
    um_ = &UniversalMachine::instance();
 
    delaySlots_ = machine.controlUnit()->delaySlots();
    bbnStatus_.clear();
}

References TTAMachine::Machine::controlUnit(), TTAMachine::ControlUnit::delaySlots(), UniversalMachine::instance(), and machine.

Referenced by llvm::LLVMTCEIRBuilder::compileOptimized(), and BBSchedulerController::handleProcedure().

Here is the call graph for this function:

loseCopies()

void CopyingDelaySlotFiller::loseCopies ( DataDependenceGraph::NodeSet *  keptTempNodes )

private

Deletes MoveNodes and programOperations not put into final graph.

Loses all bookkeeping of corresponging stuff between BB's

Definition at line 1651 of file CopyingDelaySlotFiller.cc.

                                               {
 
    std::list<MoveNode*> toDeleteNodes;
    for (std::map<MoveNode*,MoveNode*,MoveNode::Comparator>::iterator mnIter =
             moveNodes_.begin(); mnIter != moveNodes_.end();
         mnIter++ ) {
        MoveNode* second = mnIter->second;
        if (mnOwned_[second] == true) {
            mnOwned_.erase(second);
 
            if ((keptTempNodes == NULL || 
                 (keptTempNodes->find(second) == keptTempNodes->end()))
                && !second->isScheduled()) {
                // queue to be deleted
                toDeleteNodes.push_back(second);
            }
        }
    }
    moveNodes_.clear();
    moveNodeBuses_.clear();
    mnOwned_.clear();
    oldMoveNodes_.clear();
 
    // actually delete the movenodes.
    for (std::list<MoveNode*>::iterator i = toDeleteNodes.begin();
         i != toDeleteNodes.end(); i++) {
        assert (!(*i)->isScheduled());
        ddg_->removeNode(**i);
        delete *i;
    }
 
    moves_.clear();
 
    programOperations_.clear();
    oldProgramOperations_.clear();
}

References assert, and MoveNode::isScheduled().

Here is the call graph for this function:

mightFillIncomingTo()

bool CopyingDelaySlotFiller::mightFillIncomingTo ( BasicBlockNode &  bbn )

private

Checks if jumps and fall-thrus into BB can be filled and fills them if it can

Parameters

bbn	just destination basic block.

Returns

if anything was filled.

Definition at line 537 of file CopyingDelaySlotFiller.cc.

                                                                    {
    if (bbnStatus_[&bbn] == BBN_UNKNOWN) {
        return false;
    }
    if (!areAllJumpPredsScheduled(bbn)) {
        return false;
    }
 
    bool cfgChanged = false;
    bool cfgChangedAfterRecheck = false;
 
    ControlFlowGraph::EdgeSet jumpEdges = cfg_->incomingJumpEdges(bbn);
 
    // first fill all incoming jumps.
    for (auto inIter = jumpEdges.begin(); inIter != jumpEdges.end();) {
        ControlFlowEdge& cfe = **inIter;
        BasicBlockNode& jumpOrigin = cfg_->tailNode(cfe);
 
        if (jumpOrigin.isNormalBB() &&
            (bbnStatus_[&jumpOrigin] == BBN_SCHEDULED ||
             bbnStatus_[&jumpOrigin] == BBN_FALLTHRU_FILLED)) {
 
            bool changed = fillDelaySlots(jumpOrigin, delaySlots_, false);
            cfgChanged |= changed;
            cfgChangedAfterRecheck |= changed;
 
            bbFilled(jumpOrigin);
 
            BasicBlockNode* fallThruSisterNode =
                cfg_->fallThruSuccessor(jumpOrigin);
 
            // so we have some left-behind sister NODE
            if (fallThruSisterNode != NULL &&
                bbnStatus_[fallThruSisterNode] > BBN_UNKNOWN &&
                bbnStatus_[&jumpOrigin] < BBN_TEMPS_CLEANED &&
                areAllJumpPredsFilled(*fallThruSisterNode)) {
                changed = fillDelaySlots(jumpOrigin, delaySlots_, true);
                cfgChanged |= changed;
                cfgChangedAfterRecheck |= changed;
                bbFilled(jumpOrigin);
                // may have been removed totally.
            }
 
            // If we changed the cfg, loafd the inedges again.
            if (cfgChangedAfterRecheck) {
                if (!cfg_->hasNode(bbn)) {
                    return true;
                }
                cfgChangedAfterRecheck = false;
                jumpEdges = cfg_->incomingJumpEdges(bbn);
                inIter = jumpEdges.begin();
                continue;
            }
        }
        inIter++;
    }
 
    // No Fts to fill if the whole Basic Block is gone!
    if (cfgChanged && !cfg_->hasNode(bbn)) {
        return true;
    }
 
    // then all incoming jumps should be filled, fall-throughs can fill
    auto ftEdge = cfg_->incomingFTEdge(bbn);
    // may still be call pass, which is not allowed.
    if (ftEdge != nullptr && ftEdge->isFallThroughEdge()) {
        BasicBlockNode& ftOrigin = cfg_->tailNode(*ftEdge);
 
        // fall thru-predecessor can be filled if it's scheduled.
        if (bbnStatus_[&ftOrigin] == BBN_JUMP_FILLED) {
            cfgChanged |= fillDelaySlots(ftOrigin, delaySlots_, true);
            bbFilled(ftOrigin);
        } else {
            // do not take space from backwards jumps, ie loop jumps.
            if (bbnStatus_[&ftOrigin] == BBN_SCHEDULED) {
                BasicBlockNode* jumpSisterNode =
                    cfg_->jumpSuccessor(bbn);
                if (jumpSisterNode != NULL &&
                    jumpSisterNode->originalStartAddress() >
                    bbn.originalStartAddress() &&
                    areAllJumpPredsFilled(*jumpSisterNode)) {
 
                    cfgChanged |= fillDelaySlots(ftOrigin, delaySlots_, true);
                    bbFilled(ftOrigin);
                }
            }
        }
    }
    return cfgChanged;
}

References BasicBlockNode::isNormalBB(), and BasicBlockNode::originalStartAddress().

Here is the call graph for this function:

poMoved()

bool CopyingDelaySlotFiller::poMoved ( ProgramOperationPtr  po, MoveNodeListVector &  movesToCopy, DataDependenceGraph::NodeSet &  tempAssigns  )

private

This method may get slow with a big machine

Checks whether some of the moves in the given programOperation is copied to the given BB. If they are, also the programOperation is copied to the new BB.

Parameters

po	ProgramOperation to check. @movesToCopy all the moves that are copies from one BB to another

Returns

whether some of Moves referenced by po are in movesToCopy.

Definition at line 1716 of file CopyingDelaySlotFiller.cc.

                                             {
    for (int i = 0; i < po->inputMoveCount(); i++) {
        MoveNode& mn = po->inputMove(i);
        if (tempAssigns.find(&mn) != tempAssigns.end()) {
            return true;
        }
        for (unsigned int j = 0; j < movesToCopy.size(); j++) {
            std::list<MoveNode*>& moveList = movesToCopy.at(j);
            for (std::list<MoveNode*>::iterator iter = moveList.begin();
                 iter != moveList.end(); iter++) {
                if (&mn == *iter) {
                    return true;
                }
            }
        }
    }
    for (int i = 0; i < po->outputMoveCount(); i++) {
        MoveNode& mn = po->outputMove(i);
        if (tempAssigns.find(&mn) != tempAssigns.end()) {
            return true;
        }
    }
    return false;
}

tryToAssignNodes()

bool CopyingDelaySlotFiller::tryToAssignNodes ( MoveNodeListVector &  moves, int  slotsToFill, int  firstCycleToFill, ResourceManager &  rm, int  nextBBStart, DataDependenceGraph::NodeSet &  tempAssigns  )

private

Assigns moves which have been copied to the succeeding basic block into instructions in the basic block which is being filled.

Parameters

moves	moves to assign
slotsToFill	number of instructions to fill
firstCycleToFill	cycle where to fill first instruction
rm	resourcemanager to the bb being filled to.

Returns

true if the filling succeeded, false if failed.

Definition at line 1283 of file CopyingDelaySlotFiller.cc.

                                                              {
    bool failed = false;
 
    // then try to assign the nodes
    for (unsigned int i = 0; i < (unsigned)slotsToFill && 
             i < moves.size() && !failed; i++) {
        list<MoveNode*>& movesInThisCycle = moves.at(i);
        int currentCycle = firstCycleToFill + i;
 
        for (std::list<MoveNode*>::iterator iter = movesInThisCycle.begin();
             iter != movesInThisCycle.end() && !failed; iter++) {
            MoveNode& mn = **iter;
 
            if (!mn.isScheduled()) {
                
                // if cannot assign move, try to remove
                // predicate(of allowed) and try again
                if (!rm.canAssign(currentCycle, mn)) {
                    if (!mn.move().isUnconditional()) {
                        MoveNode* old = oldMoveNodes_[&mn];
                        if (old == NULL) {
                            failed = true;
                            break;
                        }
                        if (allowedToSpeculate(*old)) {
                            if (mn.isGuardOperation()) {
                                auto guardOp = mn.guardOperationPtr();
                                guardOp->removeGuardOutputNode(mn);
                                mn.unsetGuardOperation();
                            }
                            mn.move().setGuard(nullptr);
                        } else {
                            failed = true;
                            break;
                        }
                        if (!rm.canAssign(currentCycle, mn)) {
                            failed = true;
                            break;
                        }
                    } else {
                        failed = true;
                        break;
                    }
                }
                
                rm.assign(currentCycle, mn);
            } else {
                if (mn.cycle() != currentCycle) {
                    failed = true;
                    break;
                }
            }
            assert(mn.isScheduled());
            assert(mn.cycle() == currentCycle);
            
            if (mn.move().source().isImmediateRegister()) {
                const ImmediateUnit& immu = mn.move().source().immediateUnit();
                bool limmFound = false;
                for (int j = (firstCycleToFill+i-immu.latency()); 
                     j >= firstCycleToFill && !limmFound; j--) {
                    const Instruction* ins = rm.instruction(j);
                    for (int k = 0; k < ins->immediateCount(); k++) {
                        Immediate& imm = ins->immediate(k);
                        if (imm.destination().equals(mn.move().source())) {
                            limmFound = true;
                            break;
                        }
                    }
                }
                // limm too early?
                if (!limmFound) {
                    failed = true;
                    break;
                }
            }
 
            // if not destination operand, no need to check
            // other moves of the operation.
            if (!mn.isDestinationOperation()) {
                continue;
            }
 
            // check that result and other operand scheduling is possible
            // if not, this can not be scheuduled either.
            // even though alone would be possible
            if (!tryToAssignOtherMovesOfDestOps(
                    mn, firstCycleToFill, rm, 
                    firstCycleToFill + (slotsToFill-1), nextBBStart,
                    tempAssigns)) {
                failed = true;
                break;
            }
        }
    }
    if (failed) {
 
        // and also movenodes assigned to delay slots.
        for (int i = 0; i < slotsToFill; i++) {
            list<MoveNode*>& movesInThisCycle = moves.at(i);
            for (std::list<MoveNode*>::iterator iter =
                     movesInThisCycle.begin();
                 iter != movesInThisCycle.end();iter++) {
                MoveNode& mn = **iter;
                if (mn.isScheduled()) {
                    rm.unassign(mn);
                }
            }
        }
        return false;
    }
    return true;
}

References assert, ResourceManager::assign(), ResourceManager::canAssign(), MoveNode::cycle(), TTAProgram::Immediate::destination(), TTAProgram::Terminal::equals(), MoveNode::guardOperationPtr(), TTAProgram::Instruction::immediate(), TTAProgram::Instruction::immediateCount(), TTAProgram::Terminal::immediateUnit(), ResourceManager::instruction(), MoveNode::isDestinationOperation(), MoveNode::isGuardOperation(), TTAProgram::Terminal::isImmediateRegister(), MoveNode::isScheduled(), TTAProgram::Move::isUnconditional(), TTAMachine::ImmediateUnit::latency(), MoveNode::move(), TTAProgram::Move::setGuard(), TTAProgram::Move::source(), ResourceManager::unassign(), and MoveNode::unsetGuardOperation().

Here is the call graph for this function:

tryToAssignOtherMovesOfDestOps()

bool CopyingDelaySlotFiller::tryToAssignOtherMovesOfDestOps ( MoveNode &  mn, int  firstCycleToFill, ResourceManager &  rm, int  lastCycle, int  nextBBStart, DataDependenceGraph::NodeSet &  tempAssigns  )

private

Checks that all other moves of an operation can be scheduled at same relative cycles than they were in the another BB.

Definition at line 1404 of file CopyingDelaySlotFiller.cc.

                                                              {
 
    for (unsigned int i = 0; i < mn.destinationOperationCount(); i++) {
        ProgramOperation& po = mn.destinationOperation(i);
        if (!tryToAssignOtherMovesOfOp(po, firstCycleToFill, rm, lastCycle,
                                       nextBBStart, tempAssigns)) {
            return false;
        }
    }
    return true;
}

References MoveNode::destinationOperation(), and MoveNode::destinationOperationCount().

Here is the call graph for this function:

tryToAssignOtherMovesOfOp()

bool CopyingDelaySlotFiller::tryToAssignOtherMovesOfOp ( ProgramOperation &  po, int  firstCycleToFill, ResourceManager &  rm, int  lastCycle, int  nextBBStart, DataDependenceGraph::NodeSet &  tempAssigns  )

private

Definition at line 1418 of file CopyingDelaySlotFiller.cc.

                                                              {
 
    // first inputs.
    if (!po.areInputsAssigned()) {
        for (int j = 0; j < po.inputMoveCount(); j++) {
            MoveNode& operMn = po.inputMove(j);
            // schedule only those not scheduled
            if (!operMn.isScheduled()) {
                int mnCycle =
                    firstCycleToFill +
                    oldMoveNodes_[&operMn]->cycle() -
                    nextBBStart;
                const TTAMachine::Bus* bus =
                    mnCycle > lastCycle ? moveNodeBuses_[&operMn] : nullptr;
                assert(operMn.isDestinationOperation());
                if (!rm.canAssign(mnCycle, operMn, bus)) {
                    if (operMn.move().isUnconditional()) {
                        return false;
                    }
                    if (!allowedToSpeculate(operMn)) {
                        return false;
                    }
                    if (operMn.isGuardOperation()) {
                        auto guardOp = operMn.guardOperationPtr();
                        guardOp->removeGuardOutputNode(operMn);
                        operMn.unsetGuardOperation();
                    }
                    operMn.move().setGuard(nullptr);
                    if (!rm.canAssign(mnCycle, operMn, bus)) {
                        return false;
                    }
                }
 
                rm.assign(mnCycle, operMn);
                // need to be removed at end
                if (mnCycle > lastCycle) {
                    tempAssigns.insert(&operMn);
                }
            }
        } // end for
    }
 
    // then outputs.
    for (int j = 0; j < po.outputMoveCount(); j++) {
        MoveNode& resMn = po.outputMove(j);
        if (!resMn.isScheduled()) {
            int mnCycle =
                firstCycleToFill + oldMoveNodes_[&resMn]->cycle() - 
                nextBBStart;
 
            const TTAMachine::Bus* bus =
                mnCycle > lastCycle ? moveNodeBuses_[&resMn] : nullptr;
            if (!rm.canAssign(mnCycle, resMn, bus)) {
                return false;
            } else {
                rm.assign(mnCycle, resMn);
                if (mnCycle > lastCycle) {
                    tempAssigns.insert(&resMn);
                }
            }
        }
    }
    return true;
}

References ProgramOperation::areInputsAssigned(), assert, ResourceManager::assign(), ResourceManager::canAssign(), MoveNode::cycle(), MoveNode::guardOperationPtr(), ProgramOperation::inputMove(), ProgramOperation::inputMoveCount(), MoveNode::isDestinationOperation(), MoveNode::isGuardOperation(), MoveNode::isScheduled(), TTAProgram::Move::isUnconditional(), MoveNode::move(), ProgramOperation::outputMove(), ProgramOperation::outputMoveCount(), TTAProgram::Move::setGuard(), and MoveNode::unsetGuardOperation().

Here is the call graph for this function:

tryToFillSlots()

bool CopyingDelaySlotFiller::tryToFillSlots ( BasicBlockNode &  blockToFillNode, BasicBlockNode &  nextBBNode, bool  fallThru, TTAProgram::Move *  jumpMove, int  slotsToFill, int  removeGuards, int  grIndex, const TTAMachine::RegisterFile *  grFile, TTAProgram::Move *&  skippedJump, int  delaySlots  )

private

Tries to fill n slots from other BB.

Aborts cannot fill all of the slots

Parameters

blockToFill	BB containing the delay slots.
nextBB	block where from to copy the instructions.
slotsToFill	how many slots tries to fill
removeGuards	how many first instructions need guard removed.
grIndex	index of the guard register of the jump
grFile	register file of the guard of the jump.
skippedJump	if we can skip BB which jumps, sets the skipped jump here

Returns

of fill succeeded, false if failed.

Definition at line 817 of file CopyingDelaySlotFiller.cc.

                                                                    {
    skippedJump = NULL;
    BasicBlock& blockToFill = blockToFillNode.basicBlock();
    SimpleResourceManager& rm = *resourceManagers_[&blockToFill];
    BasicBlock& nextBB = nextBBNode.basicBlock();
    SimpleResourceManager* nextRm = resourceManagers_[&nextBB];
 
    if (nextRm == NULL) {
        return false;
    }
 
    int firstCycleToFill = 
        rm.smallestCycle() + blockToFill.instructionCount() - slotsToFill;
    int nextBBStart = nextRm->smallestCycle();
    
    MoveNodeListVector moves(slotsToFill);
 
    // Collect all the moves to fill.
    if (!collectMoves(
            blockToFillNode, nextBBNode, moves, slotsToFill,fallThru, 
            removeGuards, jumpMove, grIndex, grFile, skippedJump,
            delaySlots)) {
        loseCopies(NULL);
        return false;
    }
 
    //check imm reads after (safeguard against same imm read twice)
    if (!checkImmediatesAfter(nextBB, slotsToFill)) {
        loseCopies(NULL);
        return false;
    }
    
    // now we have got all the movenodes we are going to fill.
    // then try to assign them to the block where they are being filled to.
 
    // set containing po result moves etc.
    DataDependenceGraph::NodeSet tempAssigns;
    if (tryToAssignNodes(moves, slotsToFill, firstCycleToFill,rm, nextBBStart, 
                         tempAssigns)) {
        // we succeeded. 
        // delete temporaty copies of other movenodes.
        loseCopies(&tempAssigns);
 
        AssocTools::append(tempAssigns, tempResultNodes_[&blockToFillNode]);
        return true;
    } else {
        loseCopies(&tempAssigns);
        unassignTempAssigns(tempAssigns, rm);
        // failing. delete created movenodes and report failure
        return false;
    }
}

References AssocTools::append(), BasicBlockNode::basicBlock(), TTAProgram::CodeSnippet::instructionCount(), and SimpleResourceManager::smallestCycle().

Here is the call graph for this function:

unassignTempAssigns()

void CopyingDelaySlotFiller::unassignTempAssigns ( DataDependenceGraph::NodeSet &  tempAssigns, SimpleResourceManager &  rm  )

private

Definition at line 2000 of file CopyingDelaySlotFiller.cc.

                               {
    for (DataDependenceGraph::NodeSet::iterator j = tempAssigns.begin(); 
         j != tempAssigns.end(); j++) {
        assert((**j).isScheduled());
        rm.unassign(**j);
        ddg_->removeNode(**j);
        delete *j;
    }
    tempAssigns.clear();
}

References assert, and SimpleResourceManager::unassign().

Here is the call graph for this function:

updateFTBBAndCfg()

bool CopyingDelaySlotFiller::updateFTBBAndCfg ( BasicBlockNode &  jumpingBB, BasicBlockNode &  nextBBN, ControlFlowEdge &  edge, int  slotsFilled  )

private

Definition at line 333 of file CopyingDelaySlotFiller.cc.

                                            {
 
    InstructionReferenceManager& irm =
        cfg_->program()->instructionReferenceManager();
 
    for (int i = 0; i < slotsFilled; i++) {
        assert(!irm.hasReference(
                   nextBBN.basicBlock().instructionAtIndex(i)));
    }
 
    if (slotsFilled == nextBBN.basicBlock().instructionCount() &&
        cfg_->inDegree(nextBBN) == 1) {
        auto oEdges = cfg_->outEdges(nextBBN);
        assert(oEdges.size() == 1);
        ControlFlowEdge& laterEdge = **oEdges.begin();
        BasicBlockNode& newDestNode = cfg_->headNode(laterEdge);
 
        // update CFG because jump dest moved.
        // the predicate is the same as the original
        // fall-trhough, but if later is a jump or call pass.
        // this is also a jump or call pass.
        ControlFlowEdge* newEdge =
            new ControlFlowEdge(
                edge.edgePredicate(), laterEdge.edgeType());
        cfg_->disconnectNodes(jumpingBB, nextBBN);
        cfg_->connectNodes(jumpingBB, newDestNode, *newEdge);
 
        cfg_->removeNode(nextBBN);
        finishBB(nextBBN, true);
 
        for (int i = 0;
             i < nextBBN.basicBlock().instructionCount(); i++) {
            Instruction& ins =
                nextBBN.basicBlock().instructionAtIndex(i);
            while(ins.moveCount()) {
                Move& move = ins.move(0);
                MoveNode & mn = ddg_->nodeOfMove(move);
                ddg_->removeNode(mn);
                delete &mn;
                ins.removeMove(move);
            }
            while (ins.immediateCount()) {
                Immediate& imm = ins.immediate(0);
                ins.removeImmediate(imm);
            }
        }
        delete &nextBBN;
        // cfg changed
        return true;
    } else {
        nextBBN.basicBlock().skipFirstInstructions(slotsFilled);
        // cfg not changed
        return false;
    }
}

References assert, BasicBlockNode::basicBlock(), ControlFlowEdge::edgePredicate(), ControlFlowEdge::edgeType(), TTAProgram::InstructionReferenceManager::hasReference(), TTAProgram::Instruction::immediate(), TTAProgram::Instruction::immediateCount(), TTAProgram::CodeSnippet::instructionAtIndex(), TTAProgram::CodeSnippet::instructionCount(), TTAProgram::Instruction::move(), TTAProgram::Instruction::moveCount(), TTAProgram::Instruction::removeImmediate(), TTAProgram::Instruction::removeMove(), and TTAProgram::BasicBlock::skipFirstInstructions().

Here is the call graph for this function:

updateJumpsAndCfg()

bool CopyingDelaySlotFiller::updateJumpsAndCfg ( BasicBlockNode &  jumpBBN, BasicBlockNode &  fillingBBN, ControlFlowEdge &  fillEdge, TTAProgram::Move *  jumpAddressMove, std::shared_ptr< TTAProgram::Immediate >  jumpAddressImmediate, TTAProgram::Move *  jumpMove, int  slotsFilled, TTAProgram::Move *  skippedJump  )

private

Updates jump instruction jump address to the new one. Also updates CFG if it is changed due completely skipped BB.

Parameters

jumpBBN	basic block whose delay slots are filled
fillingBBN	next basic block where the instructions are taken
fillEdge	CFG edge connecting the basic blocks.
jumpAddress	jump address being updated to new one.
slotsFilled	how many delay slots were filled.

Returns

true if removed a basic block or an cfg edge.

Definition at line 1796 of file CopyingDelaySlotFiller.cc.

                                                        {
 
    bool cfgChanged = false;
    TerminalInstructionReference* jumpAddress = jumpAddressMove != NULL ?
        dynamic_cast<TerminalInstructionReference*>(
            &jumpAddressMove->source()) :
        dynamic_cast<TerminalInstructionReference*>(
            &jumpAddressImmediate->value());
 
    BasicBlock& nextBB = fillingBBN.basicBlock();
    InstructionReferenceManager& irm = cfg_->program()->
        instructionReferenceManager();
    // TODO: only the correct jump one, nto both
    assert(slotsFilled <= nextBB.instructionCount());
 
    // filled whole block, jumping to next bb.
    if (slotsFilled == nextBB.instructionCount()) {
 
        ControlFlowGraph::NodeSet nextBBs =
            cfg_->successors(fillingBBN);
        if (nextBBs.size() != 1) {
            std::string msg = "no succeessors but no jump";
            throw IllegalProgram(__FILE__,__LINE__,__func__, msg);
        }
 
        BasicBlockNode& newDestNode = **nextBBs.begin();
 
        // update CFG because jump dest moved.
        ControlFlowEdge* newEdge = new ControlFlowEdge(fillEdge);
        cfg_->disconnectNodes(jumpBBN, fillingBBN);
        cfg_->connectNodes(jumpBBN, newDestNode, *newEdge);
        cfgChanged = true;
 
        if (skippedJump != NULL) {
            // if we skipped a jump. that jump may have already been filled,
            // and then the dest is the dest of that jump,
            // not beginning of a bb.
            if (skippedJump->isReturn()) {
                assert(jumpMove != NULL);
                jumpMove->setSource(skippedJump->source().copy());
                TTAProgram::ProgramAnnotation annotation(
                    TTAProgram::ProgramAnnotation::
                    ANN_STACKFRAME_PROCEDURE_RETURN);
                jumpMove->setAnnotation(annotation);
                if (jumpAddressMove != NULL && jumpAddressMove != jumpMove) {
                    jumpAddressMove->parent().removeMove(
                        *jumpAddressMove);
                } else {
                    // get rid of the insructionreference by setting
                    // value of the imm to 0.
                    // better way would be deleting the imm but it's
                    // much more complicated
                    if (jumpAddressImmediate != NULL) {
                        jumpAddressImmediate->setValue(
                            new TerminalImmediate(SimValue(0,1)));
                    }
                }
            }
            else {
                InstructionReference ir = 
                    skippedJump->source().instructionReference();
                jumpAddress->setInstructionReference(ir);
            }
        } else {
            // else the dest is the first instruction of the bb after the 
            // filling bb, skipping the skipped instructions.
            InstructionReference ir = irm.createReference(
                newDestNode.basicBlock().instructionAtIndex(
                    newDestNode.basicBlock().skippedFirstInstructions()));
            jumpAddress->setInstructionReference(ir);
        }
               
        // if filling block became dead, remove it.
        if (cfg_->inDegree(fillingBBN) == 0) {
            assert(!irm.hasReference(nextBB.instructionAtIndex(0)));
 
            // no fall-thru, removed only jump to bb.
            // remove whole bb then.
            cfg_->removeNode(fillingBBN);
            finishBB(fillingBBN, true);
 
            for (int i = 0; i < nextBB.instructionCount(); i++) {
                Instruction& ins = nextBB.instructionAtIndex(i);
                while(ins.moveCount()) {
                    Move& move = ins.move(0);
                    MoveNode & mn = ddg_->nodeOfMove(move);
                    ddg_->removeNode(mn);
                    delete &mn;
                    ins.removeMove(move);
                }
                while (ins.immediateCount()) {
                    Immediate& imm = ins.immediate(0);
                    ins.removeImmediate(imm);
                }
                    
            }
            delete &fillingBBN;
        }
 
    } else { // not filled whole block.
        assert(skippedJump == NULL);
        assert(slotsFilled >= nextBB.skippedFirstInstructions());
        InstructionReference ir = irm.createReference(
            nextBB.instructionAtIndex(slotsFilled));
        jumpAddress->setInstructionReference(ir);
 
        // remove the first instructions that are dead.
        if (cfg_->incomingFTEdge(fillingBBN) == nullptr
        && &fillingBBN != &cfg_->firstNormalNode()) {
            int deadInsCount = 0;
            while (nextBB.instructionCount() > deadInsCount &&
                   !irm.hasReference(
                       nextBB.instructionAtIndex(deadInsCount))) {
                deadInsCount++;
            }
            nextBB.skipFirstInstructions(deadInsCount);
            if (deadInsCount >= nextBB.instructionCount()) {
                throw IllegalProgram(
                    __FILE__,__LINE__,__func__,
                    "BB got empty illegally");
            }
        }
    }
    return cfgChanged;
}

References __func__, assert, BasicBlockNode::basicBlock(), TTAProgram::Terminal::copy(), TTAProgram::InstructionReferenceManager::createReference(), TTAProgram::InstructionReferenceManager::hasReference(), TTAProgram::Instruction::immediate(), TTAProgram::Instruction::immediateCount(), TTAProgram::CodeSnippet::instructionAtIndex(), TTAProgram::Terminal::instructionReference(), TTAProgram::Move::isReturn(), TTAProgram::Instruction::move(), TTAProgram::Instruction::moveCount(), TTAProgram::Move::parent(), TTAProgram::Instruction::removeImmediate(), TTAProgram::Instruction::removeMove(), TTAProgram::AnnotatedInstructionElement::setAnnotation(), TTAProgram::TerminalInstructionReference::setInstructionReference(), TTAProgram::Move::setSource(), TTAProgram::Immediate::setValue(), TTAProgram::BasicBlock::skippedFirstInstructions(), TTAProgram::Move::source(), and TTAProgram::Immediate::value().

Here is the call graph for this function:

writesRegister()

bool CopyingDelaySlotFiller::writesRegister ( TTAProgram::Move &  move, const TTAMachine::RegisterFile *  rf, unsigned int  registerIndex  )

private

Checks whether given move writes to given register

Parameters

move	to check
rf	RegisterFile containing the register
registerIndex	index of the register.

Definition at line 789 of file CopyingDelaySlotFiller.cc.

                                                                    {
    Terminal& term = move.destination();
    if (term.isGPR()) {
        TerminalRegister& rd = dynamic_cast<TerminalRegister&>(term);
        if ( &rd.registerFile() == rf && rd.index() ==
             static_cast<int>(registerIndex)) {
            return true;
        }
    }
    return false;
}

References TTAProgram::Move::destination(), TTAProgram::TerminalRegister::index(), TTAProgram::Terminal::isGPR(), and TTAProgram::TerminalRegister::registerFile().

Here is the call graph for this function:

Member Data Documentation

bbnStatus_

std::map<BasicBlockNode*, BBNStates> CopyingDelaySlotFiller::bbnStatus_

mutableprivate

Definition at line 215 of file CopyingDelaySlotFiller.hh.

cfg_

ControlFlowGraph* CopyingDelaySlotFiller::cfg_

private

Definition at line 186 of file CopyingDelaySlotFiller.hh.

ddg_

DataDependenceGraph* CopyingDelaySlotFiller::ddg_

private

Definition at line 185 of file CopyingDelaySlotFiller.hh.

delaySlots_

int CopyingDelaySlotFiller::delaySlots_

private

Definition at line 217 of file CopyingDelaySlotFiller.hh.

killedBBs_

ControlFlowGraph::NodeSet CopyingDelaySlotFiller::killedBBs_

private

Definition at line 219 of file CopyingDelaySlotFiller.hh.

mnOwned_

std::map<MoveNode*,bool,MoveNode::Comparator> CopyingDelaySlotFiller::mnOwned_

private

Definition at line 206 of file CopyingDelaySlotFiller.hh.

moveNodeBuses_

std::map<MoveNode*, const TTAMachine::Bus*, MoveNode::Comparator> CopyingDelaySlotFiller::moveNodeBuses_

private

Definition at line 199 of file CopyingDelaySlotFiller.hh.

moveNodes_

std::map<MoveNode*,MoveNode*,MoveNode::Comparator> CopyingDelaySlotFiller::moveNodes_

private

Definition at line 196 of file CopyingDelaySlotFiller.hh.

moves_

std::map<TTAProgram::Move*, std::shared_ptr<TTAProgram::Move> > CopyingDelaySlotFiller::moves_

private

Definition at line 198 of file CopyingDelaySlotFiller.hh.

oldMoveNodes_

std::map<MoveNode*,MoveNode*,MoveNode::Comparator> CopyingDelaySlotFiller::oldMoveNodes_

private

Definition at line 197 of file CopyingDelaySlotFiller.hh.

oldProgramOperations_

std::map<ProgramOperation*, ProgramOperationPtr, ProgramOperation::Comparator> CopyingDelaySlotFiller::oldProgramOperations_

private

Definition at line 195 of file CopyingDelaySlotFiller.hh.

programOperations_

std::map<ProgramOperation*, ProgramOperationPtr, ProgramOperation::Comparator> CopyingDelaySlotFiller::programOperations_

private

Definition at line 193 of file CopyingDelaySlotFiller.hh.

resourceManagers_

std::map<TTAProgram::BasicBlock*,SimpleResourceManager*> CopyingDelaySlotFiller::resourceManagers_

private

Definition at line 188 of file CopyingDelaySlotFiller.hh.

tempPOs_

std::map<BasicBlockNode*, std::set< ProgramOperationPtr, ProgramOperation::Comparator> > CopyingDelaySlotFiller::tempPOs_

private

Definition at line 203 of file CopyingDelaySlotFiller.hh.

tempResultNodes_

std::map<BasicBlockNode*, DataDependenceGraph::NodeSet> CopyingDelaySlotFiller::tempResultNodes_

private

Definition at line 201 of file CopyingDelaySlotFiller.hh.

um_

UniversalMachine* CopyingDelaySlotFiller::um_

private

Definition at line 189 of file CopyingDelaySlotFiller.hh.

---

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

• CopyingDelaySlotFiller.hh
• CopyingDelaySlotFiller.cc