OpenASIP 2.2
Loading...
Searching...
No Matches
Public Types | Public Member Functions | Static Public Member Functions | Protected Member Functions | Private Types | Private Member Functions | Private Attributes | List of all members
CopyingDelaySlotFiller Class Reference

#include <CopyingDelaySlotFiller.hh>

Collaboration diagram for CopyingDelaySlotFiller:
Collaboration graph

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)
 
MoveNodegetMoveNode (MoveNode &old, BasicBlockNode &bbn, bool fillOverBackEdge)
 
ProgramOperationPtr getProgramOperationPtr (ProgramOperationPtr old, BasicBlockNode &bbn, bool fillOverBackEdge)
 
std::shared_ptr< TTAProgram::MovegetMove (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

DataDependenceGraphddg_
 
ControlFlowGraphcfg_
 
std::map< TTAProgram::BasicBlock *, SimpleResourceManager * > resourceManagers_
 
UniversalMachineum_
 
std::map< ProgramOperation *, ProgramOperationPtr, ProgramOperation::ComparatorprogramOperations_
 
std::map< ProgramOperation *, ProgramOperationPtr, ProgramOperation::ComparatoroldProgramOperations_
 
std::map< MoveNode *, MoveNode *, MoveNode::ComparatormoveNodes_
 
std::map< MoveNode *, MoveNode *, MoveNode::ComparatoroldMoveNodes_
 
std::map< TTAProgram::Move *, std::shared_ptr< TTAProgram::Move > > moves_
 
std::map< MoveNode *, const TTAMachine::Bus *, MoveNode::ComparatormoveNodeBuses_
 
std::map< BasicBlockNode *, DataDependenceGraph::NodeSettempResultNodes_
 
std::map< BasicBlockNode *, std::set< ProgramOperationPtr, ProgramOperation::Comparator > > tempPOs_
 
std::map< MoveNode *, bool, MoveNode::ComparatormnOwned_
 
std::map< BasicBlockNode *, BBNStatesbbnStatus_
 
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

Definition at line 98 of file CopyingDelaySlotFiller.hh.

Member Enumeration Documentation

◆ BBNStates

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.

Constructor & Destructor Documentation

◆ CopyingDelaySlotFiller()

CopyingDelaySlotFiller::CopyingDelaySlotFiller ( )

Constructor.

Definition at line 394 of file CopyingDelaySlotFiller.cc.

394 {
395}

◆ ~CopyingDelaySlotFiller()

CopyingDelaySlotFiller::~CopyingDelaySlotFiller ( )

Destructor.

Definition at line 1692 of file CopyingDelaySlotFiller.cc.

1692 {
1693 assert(programOperations_.size() == 0);
1694 assert(moveNodes_.size() == 0);
1695 assert(mnOwned_.size() == 0);
1696 assert(moves_.size() == 0);
1697
1698 //should not be needed but lets be sure
1699// loseCopies();
1700}
#define assert(condition)
std::map< ProgramOperation *, ProgramOperationPtr, ProgramOperation::Comparator > programOperations_
std::map< TTAProgram::Move *, std::shared_ptr< TTAProgram::Move > > moves_
std::map< MoveNode *, bool, MoveNode::Comparator > mnOwned_
std::map< MoveNode *, MoveNode *, MoveNode::Comparator > moveNodes_

References assert, mnOwned_, moveNodes_, moves_, and programOperations_.

Member Function Documentation

◆ addResourceManager()

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

Definition at line 691 of file CopyingDelaySlotFiller.cc.

692 {
693 resourceManagers_[&bb] = &rm;
694 rm.setMaxCycle(INT_MAX);
695}
std::map< TTAProgram::BasicBlock *, SimpleResourceManager * > resourceManagers_
void setMaxCycle(unsigned int maxCycle)

References resourceManagers_, and 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.

2013 {
2014 Move& move = mn.move();
2015 // TODO: allow even writes if the reg is not alive?
2016 if (!mn.isDestinationOperation()) {
2017 return false;
2018 }
2019 if (move.isTriggering()) {
2020 Operation& o = move.destination().operation();
2021 if (o.writesMemory() || o.hasSideEffects() ||
2022 o.affectsCount() != 0) {
2023 return false;
2024 }
2025
2026 // also may not read memory, because the address may be invalid,
2027 // if the address comes with bypass from operation with different guard.
2028 if (o.readsMemory()) {
2029 if (mn.isSourceOperation() &&
2031 return false;
2032 }
2033 // and if the address comes from a variable.
2034 if (mn.isSourceVariable()) {
2035 return false;
2036 }
2037 }
2038 }
2039 return true;
2040}
bool isSourceVariable() const
Definition MoveNode.cc:196
ProgramOperation & sourceOperation() const
Definition MoveNode.cc:453
bool isDestinationOperation() const
TTAProgram::Move & move()
bool isSourceOperation() const
Definition MoveNode.cc:168
virtual bool readsMemory() const
Definition Operation.cc:242
virtual bool hasSideEffects() const
Definition Operation.cc:272
virtual int affectsCount() const
Definition Operation.cc:402
virtual bool writesMemory() const
Definition Operation.cc:252
MoveNode * triggeringMove() const
bool isUnconditional() const
Definition Move.cc:154
bool isTriggering() const
Definition Move.cc:284
Terminal & destination() const
Definition Move.cc:323
virtual Operation & operation() const
Definition Terminal.cc:319

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().

Referenced by collectMoves(), tryToAssignNodes(), and tryToAssignOtherMovesOfOp().

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
bbnnode to check for incoming filled jumps.
Returns
true if all incoming jumps are already filled.

Definition at line 470 of file CopyingDelaySlotFiller.cc.

470 {
471 bool allJumpPredsFilled = true;
472 ControlFlowGraph::EdgeSet inEdges = cfg_->inEdges(bbn);
473 for (ControlFlowGraph::EdgeSet::iterator inIter =
474 inEdges.begin(); inIter != inEdges.end();
475 inIter++) {
476 ControlFlowEdge& cfe = **inIter;
477 if (cfe.isJumpEdge()) {
478 BasicBlockNode& jumpOrigin = cfg_->tailNode(cfe);
479
480 // if some jump to the ft-node has not been scheduled.
481 if (jumpOrigin.isNormalBB() &&
482 (bbnStatus_[&jumpOrigin] < BBN_JUMP_FILLED ||
483 bbnStatus_[&jumpOrigin] == BBN_FALLTHRU_FILLED)) {
484 allJumpPredsFilled = false;
485 }
486 }
487 }
488 return allJumpPredsFilled;
489}
bool isNormalBB() const
virtual Node & tailNode(const Edge &edge) const
virtual EdgeSet inEdges(const Node &node) const
bool isJumpEdge() const
std::map< BasicBlockNode *, BBNStates > bbnStatus_
std::set< GraphEdge *, typename GraphEdge::Comparator > EdgeSet
Definition Graph.hh:54

References BBN_FALLTHRU_FILLED, BBN_JUMP_FILLED, bbnStatus_, cfg_, BoostGraph< GraphNode, GraphEdge >::inEdges(), ControlFlowEdge::isJumpEdge(), BasicBlockNode::isNormalBB(), and BoostGraph< GraphNode, GraphEdge >::tailNode().

Referenced by mightFillIncomingTo().

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
bbnbasic 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.

498 {
499 bool allPredsScheduled = true;
500 ControlFlowGraph::EdgeSet inEdges = cfg_->inEdges(bbn);
501 for (ControlFlowGraph::EdgeSet::iterator inIter =
502 inEdges.begin(); inIter != inEdges.end();
503 inIter++) {
504 ControlFlowEdge& cfe = **inIter;
505 if (cfe.isJumpEdge()) {
506 BasicBlockNode& jumpOrigin = cfg_->tailNode(cfe);
507
508 // if some jump to the ft-node has not been scheduled.
509 if (bbnStatus_[&jumpOrigin] == BBN_UNKNOWN &&
510 jumpOrigin.isNormalBB()) {
511 allPredsScheduled = false;
512 }
513 }
514 }
515 return allPredsScheduled;
516}

References BBN_UNKNOWN, bbnStatus_, cfg_, BoostGraph< GraphNode, GraphEdge >::inEdges(), ControlFlowEdge::isJumpEdge(), BasicBlockNode::isNormalBB(), and BoostGraph< GraphNode, GraphEdge >::tailNode().

Referenced by mightFillIncomingTo().

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.

524 {
525 if (bbnStatus_[&bbn] == BBN_BOTH_FILLED) {
526 finishBB(bbn);
527 }
528}
void finishBB(BasicBlockNode &bbn, bool force=false)

References BBN_BOTH_FILLED, bbnStatus_, and finishBB().

Referenced by mightFillIncomingTo().

Here is the call graph for this function:

◆ 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
bbnBasicBlockNode which has been scheduled.

Definition at line 640 of file CopyingDelaySlotFiller.cc.

640 {
641
642 assert(bbnStatus_[&bbn] == BBN_UNKNOWN);
643 // if we don't have the RM got the bb, cannot really do much with it.
644 if (resourceManagers_.find(&bbn.basicBlock())==resourceManagers_.end()) {
645 return;
646 }
647
649
650 // all successors.
652
653 bool fillableSuccessor = false;
654 for (ControlFlowGraph::EdgeSet::iterator outIter = oEdges.begin();
655 outIter != oEdges.end();) {
656 ControlFlowEdge& cfe = **outIter;
657
658 // cannot fill calls.
659 if (!cfe.isCallPassEdge()) {
660 fillableSuccessor = true;
661 auto& head = cfg_->headNode(cfe);
662 if (mightFillIncomingTo(head)) {
663 // the filling might have removed the BBN.
664 if (!cfg_->hasNode(bbn)) {
665 return;
666 }
667 oEdges = cfg_->outEdges(bbn);
668 outIter = oEdges.begin();
669 continue;
670 }
671 }
672 outIter++;
673 }
674
675 if (!fillableSuccessor && bbnStatus_[&bbn] != BBN_ALL_DONE) {
676 finishBB(bbn);
677 }
678
679 // can fill incoming jumps if all incoming BBs scheduled.
681}
TTAProgram::BasicBlock & basicBlock()
virtual Node & headNode(const Edge &edge) const
bool hasNode(const Node &) const
virtual EdgeSet outEdges(const Node &node) const
bool isCallPassEdge() const
bool mightFillIncomingTo(BasicBlockNode &bbn)

References assert, BasicBlockNode::basicBlock(), BBN_ALL_DONE, BBN_SCHEDULED, BBN_UNKNOWN, bbnStatus_, cfg_, finishBB(), BoostGraph< GraphNode, GraphEdge >::hasNode(), BoostGraph< GraphNode, GraphEdge >::headNode(), ControlFlowEdge::isCallPassEdge(), mightFillIncomingTo(), BoostGraph< GraphNode, GraphEdge >::outEdges(), and resourceManagers_.

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
nextBBThe BB where to instructions are filled from
slotsToFillhow many slots are filled
Returns
true if everything ok, false if immediates prevent filling

Definition at line 1146 of file CopyingDelaySlotFiller.cc.

1147 {
1148 //check imm reads after (safeguard against same imm read twice)
1149 PendingImmediateMap pendingImmediateMap;
1150
1151 for (int i = slotsToFill; i < nextBB.instructionCount(); i++) {
1152 Instruction& filler = nextBB.instructionAtIndex(i);
1153
1154 // 0-latency immus
1155 for (int j = 0; j < filler.immediateCount(); j++) {
1156 TTAProgram::Immediate& imm = filler.immediate(j);
1157 const TTAProgram::Terminal& dst = imm.destination();
1158 const ImmediateUnit& immu = dst.immediateUnit();
1159 if (immu.latency() == 0) {
1160 TCEString immName =
1161 immu.name() + '.' +
1163 if (pendingImmediateMap.find(immName) !=
1164 pendingImmediateMap.end()) {
1165 // same imm written twice without reading it. something wrong.
1166 return false;
1167 }
1168 pendingImmediateMap[immName] = &imm.value();
1169 }
1170 } // imm loop
1171
1172
1173 for (int j=0; j < filler. moveCount(); j++) {
1174 Move& move = filler.move(j);
1175 if (move.source().isImmediateRegister()) {
1176 TTAProgram::Terminal& src = move.source();
1177 TCEString immName =
1178 src.immediateUnit().name() + '.'
1179 + Conversion::toString(src.index());
1180
1181 PendingImmediateMap::iterator immWriteIter =
1182 pendingImmediateMap.find(immName);
1183
1184 if (immWriteIter == pendingImmediateMap.end()) {
1185 // read from immediate reg which ahs not been written
1186 // after the filled instructions, ie the limm
1187 // is at the instructions which are filled. do not allow
1188 return false;
1189 }
1190 pendingImmediateMap.erase(immWriteIter);
1191 }
1192 } // move loop
1193
1194 // 1-latency immus
1195 for (int j = 0; j < filler.immediateCount(); j++) {
1196 TTAProgram::Immediate& imm = filler.immediate(j);
1197 const TTAProgram::Terminal& dst = imm.destination();
1198 const ImmediateUnit& immu = dst.immediateUnit();
1199 if (immu.latency() == 1) {
1200 TCEString immName = immu.name() + '.' +
1202 if (pendingImmediateMap.find(immName) !=
1203 pendingImmediateMap.end()) {
1204 // same imm written twice without reading it. something wrong.
1205 return false;
1206 }
1207 pendingImmediateMap[immName] = &imm.value();
1208 }
1209 } // imm loop
1210 } // instruction-loop
1211
1212 // if immediates unbalanced at end of the bb. something wrong.
1213 if (!pendingImmediateMap.empty()) {
1214 return false;
1215 }
1216 return true;
1217}
static std::string toString(const T &source)
std::map< TCEString, TTAProgram::TerminalImmediate * > PendingImmediateMap
virtual TCEString name() const
virtual int latency() const
virtual int instructionCount() const
virtual Instruction & instructionAtIndex(int index) const
TerminalImmediate & value() const
Definition Immediate.cc:103
const Terminal & destination() const
Definition Immediate.cc:92
Move & move(int i) const
Immediate & immediate(int i) const
Terminal & source() const
Definition Move.cc:302
virtual int index() const
Definition Terminal.cc:274
virtual bool isImmediateRegister() const
Definition Terminal.cc:97
virtual const TTAMachine::ImmediateUnit & immediateUnit() const
Definition Terminal.cc:240

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().

Referenced by tryToFillSlots().

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
mnOldmovenode which to fill from successor bb
blockToFillNodeblock containing the jump being filled.
firstCycleToFillindex of first instruction where to fill
Returns
true if no data hazards, false if cannot fill.

Definition at line 1228 of file CopyingDelaySlotFiller.cc.

1229 {
1230 DataDependenceGraph::EdgeSet inEdges = ddg_->inEdges(mnOld);
1231 for (DataDependenceGraph::EdgeSet::iterator ieIter =
1232 inEdges.begin(); ieIter != inEdges.end(); ieIter++) {
1233 int mnCycle = mnOld.cycle();
1234 // slow
1235 DataDependenceEdge& ddEdge = **ieIter;
1236 MoveNode& pred = ddg_->tailNode(ddEdge);
1237 if (pred.isMove()) {
1238 BasicBlockNode& predBlock = ddg_->getBasicBlockNode(pred);
1239 if (!pred.isScheduled()) {
1240 continue;
1241 }
1242
1243 if (&predBlock == &blockToFillNode) {
1244 int nodeCycle;
1245 int delay = 1;
1246 // guard latency.
1247 if (ddEdge.dependenceType() ==
1249 if (ddEdge.guardUse()) {
1250 delay = pred.guardLatency();
1251 }
1252 nodeCycle = pred.cycle() - delay+1;
1253 } else {
1254 // if WAW, always 1
1255 if (ddEdge.dependenceType() !=
1257 if (ddEdge.guardUse()) {
1258 delay = mnOld.guardLatency();
1259 }
1260 }
1261 nodeCycle = pred.cycle()+delay;
1262 }
1263 if (nodeCycle > cycleDiff+mnCycle) {
1264 return false;
1265 }
1266 }
1267 }
1268 }
1269 return true;
1270}
DependenceType dependenceType() const
const BasicBlockNode & getBasicBlockNode(const MoveNode &mn) const
int cycle() const
Definition MoveNode.cc:421
bool isMove() const
int guardLatency() const
Definition MoveNode.cc:779
bool isScheduled() const
Definition MoveNode.cc:409

References MoveNode::cycle(), ddg_, DataDependenceEdge::DEP_WAR, DataDependenceEdge::DEP_WAW, DataDependenceEdge::dependenceType(), DataDependenceGraph::getBasicBlockNode(), MoveNode::guardLatency(), DataDependenceEdge::guardUse(), BoostGraph< GraphNode, GraphEdge >::inEdges(), MoveNode::isMove(), MoveNode::isScheduled(), and BoostGraph< GraphNode, GraphEdge >::tailNode().

Referenced by collectMoves().

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
blockToFillNodebasic block node where to fill to
nextBBNbasic blocknode where to fill from
movesplace to store the collected nodes.
slotsToFillhow many delay slots to fill
fallThruif filling fall-thru
removeGuardshow many first instructions need guard removed.
jumpMovemove which is the jump that is filled
grIndexindex of the guard register of the jump
grFileregister file of the guard of the jump.
skippedJumpif 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.

895 {
896 PendingImmediateMap pendingImmediateMap;
897
898 ControlFlowEdge* connectingEdge =
899 *cfg_->connectingEdges(blockToFillNode, nextBBN).begin();
900 BasicBlock& bb = blockToFillNode.basicBlock();
901 BasicBlock& nextBB = nextBBN.basicBlock();
903 SimpleResourceManager& nextRm = *resourceManagers_[&nextBB];
904
905 int firstIndexToFill =
906 blockToFillNode.basicBlock().instructionCount() - slotsToFill;
907
908 int cycleDiff = firstIndexToFill + rm.smallestCycle() - nextRm.smallestCycle();
909
910 // Find all moves to copy and check their dependencies.
911 // Loop thru instructions first..
912 for (int i = 0; i < slotsToFill; i++) {
913 Instruction& filler = nextBB.instructionAtIndex(i);
914 if (filler.hasCall()) {
915 return false;
916 }
917
918 // loop through all 0-latency immediates fo the instr.
919 for (int j = 0; j < filler.immediateCount(); j++) {
920 // TODO: why immediates not allowed here? what about allowing
921 // with 0-latency?
922 if (&blockToFillNode == &nextBBN) {
923 return false;
924 }
925
926 TTAProgram::Immediate& imm = filler.immediate(j);
927 const TTAProgram::Terminal& dst = imm.destination();
928 const ImmediateUnit& immu = dst.immediateUnit();
929 if (immu.latency() == 0) {
930 TCEString immName = immu.name() + '.' +
932
933 if (AssocTools::containsKey(pendingImmediateMap,immName)) {
934 // there already is write to this imm reg without
935 // a read to it? something is wrong, abort
936 return false;
937 }
938 pendingImmediateMap[immName] = &imm.value();
939 }
940 }
941
942
943 // loop thru all moves in the instr
944 for (int j = 0; j < filler.moveCount(); j++) {
945 Move& oldMove = filler.move(j);
946 bool dontGuard = i < removeGuards;
947 // may fill jump if fills the whole BB and updates the jump.
948 if (oldMove.isControlFlowMove()) {
949 if (oldMove.isJump()) {
950 if (!oldMove.isUnconditional()) {
951 // TODO: if first was uncond jump, and filling whole BB,
952 // this could be allowed.
953 return false;
954 }
955 if (fallThru) {
956 // Allow another jump only to same instruction
957 // than where the filled jump is.
958 if (i != slotsToFill - delaySlots -1) {
959 return false;
960 }
961 } else {
962 if (slotsToFill != nextBB.instructionCount() ||
963 // TODO: find a way to find the source imm of this jump
964 // even if LIMM or tempregcopy.
965 // then no need to abort here.
966 oldMove.source().isGPR() ||
967 oldMove.source().isImmediateRegister()) {
968 return false;
969 }
970 if (oldMove.source().isRA()) {
971 // If updating jumpMove with RA, it may result to an
972 // illegal instruction due to missing connectivity.
973 if (jumpMove == nullptr
975 jumpMove->bus(), oldMove.source().port())) {
976 return false;
977 }
978 }
979 skippedJump = &oldMove;
980 continue; // can be skipped
981 }
982 } else { // unknown cflow op
983 return false;
984 }
985
986 }
987
988 // TODO: should use guard latency here instead of -1
989 // check if it overwrites the guard of the jump
990 if (writesRegister(oldMove, grFile, grIndex)) {
991 // overwriting the guard reg as last thing does not matter,
992 // only allow it in last imported instruction.
993 if (i != slotsToFill-1) {
994 return false;
995 }
996 }
997
998 // do not allow delay slot filling of lbufs op.
999 // this messes up at least the simulator.
1000 MoveNode& mnOld = ddg_->nodeOfMove(oldMove);
1001 if (mnOld.isDestinationOperation() &&
1002 mnOld.destinationOperation().operation().name() == "LBUFS"
1003 && slotsToFill != nextBB.instructionCount()) {
1004 return false;
1005 }
1006
1007 // check all deps
1008 if (!oldMove.isUnconditional()) {
1009 // Do not fill with guarded moves, if jump is guarded,
1010 // might need 2 guards.
1011 // Only allowed if removing the guards anyway.
1012 if (jumpMove != NULL && !jumpMove->isUnconditional()) {
1013 dontGuard = true;
1014 }
1015 // don't allow unconditionals before
1016 // BB start + guard latency (if guard written in last move
1017 // of previous BB)
1018 if (firstIndexToFill < mnOld.guardLatency()-1) {
1019 return false;
1020 }
1021 }
1022
1023 // if a move has no side effects, the guard can be omitted
1024 // and it can be scheduled before the guard is ready.
1025 if (dontGuard) {
1026 if (!allowedToSpeculate(mnOld)) {
1027 return false;
1028 }
1029 } else {
1030 // guard with a portguard? then do not (yet) allow src op.
1031 if (jumpMove != NULL && !jumpMove->isUnconditional() &&
1032 dynamic_cast<const PortGuard*>(&jumpMove->guard().guard())
1033 && mnOld.isSourceOperation()) {
1034 return false;
1035 }
1036 }
1037
1038 // check DDG that no data hazards.
1039 if (!checkIncomingDeps(mnOld, blockToFillNode, cycleDiff)) {
1040 return false;
1041 }
1042
1043 // also copies move
1044 MoveNode& mn = getMoveNode(
1045 mnOld, blockToFillNode, connectingEdge->isBackEdge());
1046 Move& newMove = mn.move();
1047
1048 // reads immediate?
1049 if (newMove.source().isImmediateRegister()) {
1050 TTAProgram::Terminal& src = newMove.source();
1051 TCEString immName =
1052 src.immediateUnit().name() + '.'
1053 + Conversion::toString(src.index());
1054
1055 PendingImmediateMap::iterator immWriteIter =
1056 pendingImmediateMap.find(immName);
1057
1058 // if no write to the imm reg found, fail.
1059 if (immWriteIter == pendingImmediateMap.end()) {
1060 return false;
1061 }
1062 newMove.setSource(immWriteIter->second->copy());
1063 pendingImmediateMap.erase(immWriteIter);
1064 }
1065
1066 if (jumpMove != NULL && !jumpMove->isUnconditional() &&
1067 !dontGuard) {
1068
1069 if (fallThru) {
1070 auto g = CodeGenerator::createInverseGuard(jumpMove->guard());
1071 assert(g != nullptr);
1072 newMove.setGuard(g);
1073 } else {
1074 newMove.setGuard(jumpMove->guard().copy());
1075 }
1076 if (dynamic_cast<const PortGuard*>(
1077 &jumpMove->guard().guard())) {
1078 // TODO: set guard op from the jump?
1079 MoveNode& jumpNode = ddg_->nodeOfMove(*jumpMove);
1080 auto guardOp = jumpNode.guardOperationPtr();
1081 guardOp->addGuardOutputNode(mn);
1082 mn.setGuardOperationPtr(guardOp);
1083 }
1084
1085 MoveNode& jumpNode = ddg_->nodeOfMove(*jumpMove);
1086 ddg_->copyIncomingGuardEdges(jumpNode, mn);
1087 }
1088 moves.at(i).push_back(&mn);
1089 } // move-loop
1090
1091 for (int j = 0; j < filler.immediateCount(); j++) {
1092 if (&blockToFillNode == &nextBBN) {
1093 return false;
1094 }
1095
1096 TTAProgram::Immediate& imm = filler.immediate(j);
1097 const TTAProgram::Terminal& dst = imm.destination();
1098 const ImmediateUnit& immu = dst.immediateUnit();
1099 if (immu.latency() == 1) {
1100 TCEString immName = immu.name() + '.' +
1102
1103 if (AssocTools::containsKey(pendingImmediateMap,immName)) {
1104 // there already is write to this imm reg without
1105 // a read to it? something is wrong, abort
1106 return false;
1107 }
1108 pendingImmediateMap[immName] = &imm.value();
1109 }
1110 }
1111 }
1112
1113 // make sure long guard latencies dont cause trouble with following instructions.
1114 if (nextBB.instructionCount() > slotsToFill) {
1115 Instruction& firstNotToFill = nextBB.instructionAtIndex(slotsToFill);
1116 // loop thru all moves in the instr
1117 for (int j = 0; j < firstNotToFill.moveCount(); j++) {
1118 Move& move = firstNotToFill.move(j);
1119 if (move.isUnconditional()) {
1120 break;
1121 }
1122
1123 MoveNode& mn = ddg_->nodeOfMove(move);
1124
1125 // check DDG that no data hazards.
1126 if (!checkIncomingDeps(mn, blockToFillNode, cycleDiff)) {
1127 return false;
1128 }
1129 }
1130 }
1131
1132 // ok if no pending immediates (ie limm written, not read)
1133 return pendingImmediateMap.empty();
1134}
static bool containsKey(const ContainerType &aContainer, const KeyType &aKey)
EdgeSet connectingEdges(const Node &nTail, const Node &nHead) const
bool isBackEdge() const
bool writesRegister(TTAProgram::Move &move, const TTAMachine::RegisterFile *rf, unsigned int registerIndex)
bool checkIncomingDeps(MoveNode &mnOld, BasicBlockNode &blockToFillNode, int cycleDiff)
bool allowedToSpeculate(MoveNode &mn) const
MoveNode & getMoveNode(MoveNode &old, BasicBlockNode &bbn, bool fillOverBackEdge)
void copyIncomingGuardEdges(const MoveNode &src, MoveNode &dst)
MoveNode & nodeOfMove(const TTAProgram::Move &move)
static bool isConnected(const TTAMachine::Port &sourcePort, const TTAMachine::Port &destinationPort, const TTAMachine::Guard *guard=NULL)
void setGuardOperationPtr(ProgramOperationPtr po)
Definition MoveNode.cc:550
ProgramOperationPtr guardOperationPtr() const
Definition MoveNode.cc:484
ProgramOperation & destinationOperation(unsigned int index=0) const
virtual TCEString name() const
Definition Operation.cc:93
const Operation & operation() const
virtual int smallestCycle() const override
static TTAProgram::MoveGuard * createInverseGuard(const TTAProgram::MoveGuard &mg, const TTAMachine::Bus *bus=NULL)
MoveGuard * copy() const
Definition MoveGuard.cc:96
const TTAMachine::Guard & guard() const
Definition MoveGuard.cc:86
void setSource(Terminal *src)
Definition Move.cc:312
MoveGuard & guard() const
Definition Move.cc:345
bool isControlFlowMove() const
Definition Move.cc:233
bool isJump() const
Definition Move.cc:164
void setGuard(MoveGuard *guard)
Definition Move.cc:360
const TTAMachine::Bus & bus() const
Definition Move.cc:373
virtual bool isRA() const
Definition Terminal.cc:129
virtual bool isGPR() const
Definition Terminal.cc:107
virtual const TTAMachine::Port & port() const
Definition Terminal.cc:378

References allowedToSpeculate(), assert, BasicBlockNode::basicBlock(), TTAProgram::Move::bus(), cfg_, checkIncomingDeps(), BoostGraph< GraphNode, GraphEdge >::connectingEdges(), AssocTools::containsKey(), TTAProgram::MoveGuard::copy(), DataDependenceGraph::copyIncomingGuardEdges(), TTAProgram::CodeGenerator::createInverseGuard(), ddg_, TTAProgram::Immediate::destination(), MoveNode::destinationOperation(), getMoveNode(), TTAProgram::Move::guard(), TTAProgram::MoveGuard::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(), MoveNode::move(), TTAProgram::Instruction::move(), TTAProgram::Instruction::moveCount(), TTAMachine::Component::name(), Operation::name(), DataDependenceGraph::nodeOfMove(), ProgramOperation::operation(), TTAProgram::Terminal::port(), resourceManagers_, TTAProgram::Move::setGuard(), MoveNode::setGuardOperationPtr(), TTAProgram::Move::setSource(), SimpleResourceManager::smallestCycle(), TTAProgram::Move::source(), Conversion::toString(), TTAProgram::Immediate::value(), and writesRegister().

Referenced by tryToFillSlots().

◆ fillDelaySlots() [1/2]

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

Fill delay slots of given BB.

Parameters
jumpingBBBB to fill delay slots.
delaySlotsnumber of delay slots in the machine.
fillFallThrufill from Fall-thru of jump BB?

Definition at line 88 of file CopyingDelaySlotFiller.cc.

89 {
91 bbnStatus_[&jumpingBB] = BBN_BOTH_FILLED;
92 return false;
93 }
94
95 // do not try to fill loop scheduled, also skip epilog and prolog.
96 if (jumpingBB.isLoopScheduled() || jumpingBB.isHWLoop()) {
97 bbnStatus_[&jumpingBB] = BBN_BOTH_FILLED;
98 return false;
99 }
100
101 bool cfgChanged = false;
102
103 if (fillFallThru) {
104 switch (bbnStatus_[&jumpingBB]) {
105 case BBN_SCHEDULED:
106 bbnStatus_[&jumpingBB] = BBN_FALLTHRU_FILLED;
107 break;
108 case BBN_JUMP_FILLED:
109 bbnStatus_[&jumpingBB] = BBN_BOTH_FILLED;
110 break;
111 default:
112 assert(false);
113 }
114 } else {
115 switch (bbnStatus_[&jumpingBB]) {
116 case BBN_SCHEDULED:
117 bbnStatus_[&jumpingBB] = BBN_JUMP_FILLED;
118 break;
120 bbnStatus_[&jumpingBB] = BBN_BOTH_FILLED;
121 break;
122 default:
123 assert(false);
124 }
125 }
126
127 ControlFlowGraph::EdgeSet outEdges = cfg_->outEdges(jumpingBB);
128
131
132 TTAProgram::BasicBlock& thisBB = jumpingBB.basicBlock();
133 std::pair<int, TTAProgram::Move*> jumpData = findJump(thisBB);
134 std::pair<Move*, std::shared_ptr<Immediate> > jumpAddressData;
135
136 // should be the same
137 int jumpIndex = jumpData.first;
138 Move* jumpMove = jumpData.second;
139
140 // need for imm source only if filling jump, not imm.
141 if (!fillFallThru) {
142 // jump needed only when filling jump, not fall-thru.
143 // not found?
144 if (jumpMove == NULL) {
145 return false;
146 }
147
148 if (!jumpMove->source().isInstructionAddress()) {
149 // address comes from LIMM, search the write to limm reg.
150 jumpAddressData = findJumpImmediate(jumpIndex, *jumpMove, irm);
151 if (jumpAddressData.first == NULL &&
152 jumpAddressData.second == NULL) {
153 //Imm source not found, aborting
154 return false;
155 }
156 } else {
157 jumpAddressData.first = jumpMove;
158 }
159 }
160
161 const RegisterFile* grFile = NULL;
162 unsigned int grIndex = 0;
163
164 // lets be aggressive, fill more than just branch slots?
165 int maxFillCount = std::min(
166 delaySlots + 12,
167 thisBB.instructionCount() - thisBB.skippedFirstInstructions());
168
169 int maxGuardedFillCount = 0;
170
171 // if we have references to instructions in target BB, cannot put anything
172 // before them, so limit how many slots to fill at maximum.
173 for (int i = 1 ; i < thisBB.instructionCount(); i++) {
174 if (irm.hasReference(thisBB.instructionAtIndex(i))) {
175 maxFillCount = std::min(maxFillCount, thisBB.instructionCount()-i);
176 }
177 }
178
179 // if we have conditional jump, find the predicate register
180 if (jumpMove != NULL && !jumpMove->isUnconditional()) {
181 maxGuardedFillCount = INT_MAX;
182 const Guard& g = jumpMove->guard().guard();
183 const RegisterGuard* rg = dynamic_cast<const RegisterGuard*>(&g);
184 if (rg != NULL) {
185 grFile = rg->registerFile();
186 grIndex = rg->registerIndex();
187 }
188
189 // find when the predicate reg is written to and use that
190 // to limit how many to bypass.
191 MoveNode& jumpNode = ddg_->nodeOfMove(*jumpMove);
193 ddg_->guardDefMoves(jumpNode);
194 if (guardDefs.size() != 1) {
195 // many defs, don't know which is the critical one.
196 // fill only slots+jump ins
197 maxGuardedFillCount = std::min(maxGuardedFillCount,delaySlots+1);
198 } else {
199 MoveNode& guardDefMove = **guardDefs.begin();
200 if (&ddg_->getBasicBlockNode(guardDefMove) == &jumpingBB) {
202 *resourceManagers_[&jumpingBB.basicBlock()];
203
204 int earliestToFill = guardDefMove.cycle() -
205 rm.smallestCycle() +
206 jumpNode.guardLatency();
207
208 maxGuardedFillCount =
209 std::min(maxGuardedFillCount,
210 thisBB.instructionCount() - earliestToFill);
211 } else {
212 // guard written in previous BB?
213 // make sure not filled to first insrt if
214 // guard latency 2
215 maxGuardedFillCount =
216 std::min(maxGuardedFillCount,
217 thisBB.instructionCount() -
218 std::max(0,jumpNode.guardLatency()-1));
219 }
220 }
221 } // jump conditional
222
223 // 1 or two items, big loop. These may come in either order, grr.
224 for (ControlFlowGraph::EdgeSet::iterator iter = outEdges.begin();
225 iter != outEdges.end(); iter++) {
226 int slotsFilled = 0;
227 int myMaxGuardedFillCount = maxGuardedFillCount;
228
229 ControlFlowEdge& edge = **iter;
230 if (edge.isFallThroughEdge() != fillFallThru) {
231 continue;
232 }
233 if (edge.isCallPassEdge()) {
234 continue;
235 }
236
237 BasicBlockNode& nextBBN = cfg_->headNode(edge);
238
239 // cannot fill if the next is not normal BB.
240 if (!nextBBN.isNormalBB() || nextBBN.isLoopScheduled() ||
241 nextBBN.isHWLoop()) {
242 continue;
243 }
244
245 int nextInsCount = nextBBN.basicBlock().instructionCount();
246 if (&nextBBN == &jumpingBB) {
247 // jump to itself. may not fill from instructions
248 // which are itself being filled.
249 maxFillCount = std::min(maxFillCount, nextInsCount/2);
250 } else {
251 // otherwise may fill all other target bb
252 maxFillCount = std::min(maxFillCount,nextInsCount);
253 }
254
255 if (fillFallThru) {
256 if (jumpMove != NULL) {
257 // test that we can create an inverse guard
258 if (jumpMove->isUnconditional()) {
259 continue;
260 }
262 jumpMove->guard());
263 if (invG == NULL) {
264 myMaxGuardedFillCount = 0;
265 } else {
266 delete invG;
267 }
268 }
269
270 // cannot remove ins if it has refs.
271 // -> cannot fill fall instrs which have refs
272 for (int i = 0; i < maxFillCount; i++) {
273 if (irm.hasReference(
274 nextBBN.basicBlock().instructionAtIndex(i))) {
275 maxFillCount = i;
276 }
277 }
278 }
279
280 if (maxFillCount == 0) {
281 continue;
282 }
283
284 // register copy added leaves some inter-bb edges..
285 // TODO: remove when registercopyadder handles
286 // inter-BB-antideps..
287
288 // also delay slot filler itself does not create
289 // all edges, at least if filling fall-thru jumps.
290 // so always run the routine until fixed,
291 // if-fall-thru jumps enabled.
292
293 // temporaty solution: fix only if temp reg adder effective
294// if (!fullyConnected) {
295 ddg_->fixInterBBAntiEdges(jumpingBB, nextBBN, edge.isBackEdge());
296// }
297
298 Move* skippedJump;
299 // also try to fill into jump instruction.
300 // fillSize = delaySlots still adpcm-3-full-fails, should be +1
301 for (int fillSize = maxFillCount; fillSize > 0; fillSize--) {
302 int removeGuards = (fillSize > myMaxGuardedFillCount) ?
303 fillSize - myMaxGuardedFillCount : 0;
304 // then try to do the filling.
305 bool ok = tryToFillSlots(
306 jumpingBB, nextBBN, fillFallThru, jumpMove, fillSize,
307 removeGuards, grIndex, grFile, skippedJump, delaySlots);
308 if (ok) {
309 slotsFilled = fillSize;
310 break;
311 }
312 }
313
314 // filled some slots?
315 if (slotsFilled != 0) {
316
317 // filled from jump dest or fal-thru?
318 if (!fillFallThru) {
319 // have to update jump destination
320 cfgChanged |= updateJumpsAndCfg(
321 jumpingBB, nextBBN, edge, jumpAddressData.first,
322 jumpAddressData.second, jumpMove, slotsFilled,
323 skippedJump);
324 } else { // fall-thru, skip first instructions.
325 cfgChanged |= updateFTBBAndCfg(
326 jumpingBB, nextBBN, edge, slotsFilled);
327 }
328 }
329 }
330 return cfgChanged;
331}
bool isLoopScheduled() const
bool isHWLoop() const
bool isFallThroughEdge() const
bool hasMultipleUnconditionalSuccessors(const BasicBlockNode &node) const
TTAProgram::Program * program() const
bool updateFTBBAndCfg(BasicBlockNode &jumpingBB, BasicBlockNode &nextBBN, ControlFlowEdge &edge, int slotsFilled)
static std::pair< TTAProgram::Move *, std::shared_ptr< TTAProgram::Immediate > > findJumpImmediate(int jumpIndex, TTAProgram::Move &jumpMove, TTAProgram::InstructionReferenceManager &irm)
static std::pair< int, TTAProgram::Move * > findJump(TTAProgram::BasicBlock &bb, ControlFlowEdge::CFGEdgePredicate *pred=nullptr)
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)
void fixInterBBAntiEdges(BasicBlockNode &bbn1, BasicBlockNode &bbn2, bool loopEdges)
NodeSet guardDefMoves(const MoveNode &moveNode)
std::set< GraphNode *, typename GraphNode::Comparator > NodeSet
Definition Graph.hh:53
const RegisterFile * registerFile() const
int skippedFirstInstructions() const
Definition BasicBlock.cc:88
InstructionReferenceManager & instructionReferenceManager() const
Definition Program.cc:688
virtual bool isInstructionAddress() const
Definition Terminal.cc:87

References assert, BasicBlockNode::basicBlock(), TTAProgram::CodeGenerator::createInverseGuard(), MoveNode::cycle(), TTAProgram::Move::guard(), TTAProgram::MoveGuard::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
cfgControlFlowGraph where to fill delay slots.
ddgDataDependenceGraph containing data dependencies.

Definition at line 405 of file CopyingDelaySlotFiller.cc.

407 {
409 int delaySlots = machine.controlUnit()->delaySlots();
410
411 cfg_ = &cfg;
412 ddg_ = &ddg;
413
414 // first fill only jumps
415 for (int i = 0; i < cfg.nodeCount(); i++) {
416 BasicBlockNode& bbn = cfg.node(i);
417 if (bbn.isNormalBB()) {
418 if (bbnStatus_[&bbn] == BBN_SCHEDULED ||
421 bbn, delaySlots, false);
422 }
423 }
424 }
425
426 // then fill only fall-thru's.
427 for (int i = 0; i < cfg.nodeCount(); i++) {
428 BasicBlockNode& bbn = cfg.node(i);
429 if (bbn.isNormalBB()) {
430 if (bbnStatus_[&bbn] == BBN_JUMP_FILLED) {
432 bbn, delaySlots, true);
433 }
434 }
435 }
436
437 // All is done. Then get rid of data which is no longer needed.
438 for (std::map<BasicBlockNode*, BBNStates>::iterator i =
439 bbnStatus_.begin(); i != bbnStatus_.end(); i++) {
440 if (i->second != BBN_ALL_DONE) {
441 // todo: why is true required here
442 finishBB(*i->first); //, true);
443 }
444 }
445 // TODO: why is this not empty? finishBB should clear these.
446 for (std::map<BasicBlock*, SimpleResourceManager*>::iterator i =
447 resourceManagers_.begin(); i != resourceManagers_.end(); i++) {
448 if (i->second != NULL) {
450 }
451 }
452 resourceManagers_.clear();
453// assert(resourceManagers_.empty());
454 tempResultNodes_.clear();
455}
TTAMachine::Machine * machine
the architecture definition of the estimated processor
int nodeCount() const
Node & node(const int index) const
std::map< BasicBlockNode *, DataDependenceGraph::NodeSet > tempResultNodes_
void fillDelaySlots(ControlFlowGraph &cfg, DataDependenceGraph &ddg, const TTAMachine::Machine &machine)
static void disposeRM(SimpleResourceManager *rm, bool allowReuse=true)
virtual ControlUnit * controlUnit() const
Definition Machine.cc:345
static UniversalMachine & instance()

References BBN_ALL_DONE, BBN_FALLTHRU_FILLED, BBN_JUMP_FILLED, BBN_SCHEDULED, bbnStatus_, cfg_, TTAMachine::Machine::controlUnit(), ddg_, TTAMachine::ControlUnit::delaySlots(), SimpleResourceManager::disposeRM(), fillDelaySlots(), finishBB(), UniversalMachine::instance(), BasicBlockNode::isNormalBB(), machine, BoostGraph< GraphNode, GraphEdge >::node(), BoostGraph< GraphNode, GraphEdge >::nodeCount(), resourceManagers_, tempResultNodes_, and um_.

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

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.

460 {
462}
static void deleteAllItems(ContainerType &aMap)
ControlFlowGraph::NodeSet killedBBs_

References AssocTools::deleteAllItems(), and killedBBs_.

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
bbbasicBlock where to search the jump move

Definition at line 1751 of file CopyingDelaySlotFiller.cc.

1752 {
1753
1754 for (int i = bb.instructionCount()-1; i >= 0; i--) {
1755 Instruction& ins = bb.instructionAtIndex(i);
1756 for (int j = 0; j < ins.moveCount(); j++ ) {
1757 Move& move = ins.move(j);
1758 if (move.isJump()) {
1759 if (pred == nullptr) {
1760 return std::pair<int, TTAProgram::Move*>(i, &move);
1761 }
1762 if (move.isUnconditional()) {
1764 return std::pair<int, TTAProgram::Move*>(i, &move);
1765 }
1766 } else {
1767 auto& guard = move.guard().guard();
1769 == (guard.isInverted())) {
1770 return std::pair<int, TTAProgram::Move*>(i, &move);
1771 }
1772 }
1773 }
1774 }
1775 //cal not handled
1776 if (ins.hasCall()) {
1777 return std::pair<int, TTAProgram::Move*>(-1,NULL);
1778 }
1779 }
1780 // not found.
1781 return std::pair<int, TTAProgram::Move*>(-1,NULL);
1782}

References ControlFlowEdge::CFLOW_EDGE_FALSE, ControlFlowEdge::CFLOW_EDGE_NORMAL, TTAProgram::Move::guard(), TTAProgram::MoveGuard::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
jumpIndexindex of the instruction containin the jump in the BB.
jumpMovethe move containing the jump.
Returns
Immediate containing jump address or NULL if not found.

Definition at line 705 of file CopyingDelaySlotFiller.cc.

706 {
707 BasicBlock& bb = static_cast<BasicBlock&>(jumpMove.parent().parent());
708 Move* irMove = &jumpMove;
709 int irIndex = jumpIndex;
710
711 // Register copy or some unknown source.
712 // should handle unlimited number of reg. copies.
713 // Note: the jump address can be written outside the BB
714 // if it's an indirect branch (e.g. LLVM address of label
715 // extension).
716 if (irMove->source().isGPR()) {
717 const RegisterFile* rf = &irMove->source().registerFile();
718 int regIndex = static_cast<int>(irMove->source().index());
719 int found = false;
720 int i;
721 // if has refernces, the imm may be written in another BB.
722 // we can not (yet) track that!
723 if (irm.hasReference(bb.instructionAtIndex(irIndex))) {
724 return std::pair<Move*,std::shared_ptr<Immediate> >(nullptr, nullptr);
725 }
726 for (i = irIndex -1 ; i >= bb.skippedFirstInstructions() && !found;
727 i-- ) {
728 Instruction &ins = bb.instructionAtIndex(i);
729 // if has refernces, the imm may be written in another BB.
730 // we can not (yet) track that!
731 if (irm.hasReference(ins)) {
732 return std::pair<Move*,std::shared_ptr<Immediate> >(
733 nullptr, nullptr);
734 }
735 for (int j = 0; j < ins.moveCount(); j++ ) {
736 Move& move = ins.move(j);
737 if (move.destination().isGPR()) {
738 if (&move.destination().registerFile() == rf &&
739 move.destination().index() == regIndex) {
740 irMove = &move;
741 irIndex = i;
742 found = true;
743 break;
744 }
745 }
746 }
747 }
748 // jump imm not found.
749 if (i < bb.skippedFirstInstructions() && !found) {
750 return std::pair<Move*,std::shared_ptr<Immediate> >(
751 nullptr, nullptr);
752 }
753 }
754 if (irMove->source().isImmediate()) {
755 return std::pair<Move*,std::shared_ptr<Immediate> >(irMove, nullptr);
756 }
757
758 // then read the actual immediate
759 if (irMove->source().isImmediateRegister()) {
760 const ImmediateUnit& immu = irMove->source().immediateUnit();
761 int index = static_cast<int>(irMove->source().index());
762 for (int i = irIndex - immu.latency(); i >= 0; i--) {
763 Instruction &ins = bb.instructionAtIndex(i);
764 for (int j = 0; j < ins.immediateCount(); j++) {
765 auto imm = ins.immediatePtr(j);
766 if (imm->destination().index() == index &&
767 &imm->destination().immediateUnit() == &immu) {
768 return std::pair<Move*,std::shared_ptr<Immediate> >(
769 nullptr, imm);
770 }
771 }
772 // if has refernces, the imm may be written in another BB.
773 // we can not (yet) track that!
774 if (irm.hasReference(ins)) {
775 return std::pair<Move*,std::shared_ptr<Immediate> >(
776 nullptr, nullptr);
777 }
778 }
779 }
780 return std::pair<Move*, std::shared_ptr<Immediate> >(nullptr, nullptr);
781}
std::shared_ptr< Immediate > immediatePtr(int i) const
CodeSnippet & parent() const
Instruction & parent() const
Definition Move.cc:115
virtual bool isImmediate() const
Definition Terminal.cc:63
virtual const TTAMachine::RegisterFile & registerFile() const
Definition Terminal.cc:225

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::Instruction::parent(), TTAProgram::Move::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.

1949 {
1950
1951 std::map<BasicBlockNode*,DataDependenceGraph::NodeSet>::iterator
1952 i = tempResultNodes_.find(&bbn);
1953
1954 if (i != tempResultNodes_.end()) {
1955 DataDependenceGraph::NodeSet& ns = i->second;
1956 if (!ns.empty()) {
1957 std::map<BasicBlock*,SimpleResourceManager*>::iterator rmi =
1958 resourceManagers_.find(&i->first->basicBlock());
1959 assert (rmi != resourceManagers_.end());
1960 SimpleResourceManager& rm = *rmi->second;
1961 unassignTempAssigns(ns, rm);
1962 }
1963 }
1964
1966
1967 if (!force) {
1968 // all predecessors. If some not scheduled, do not yet remove the rm.
1969 // then stay in state BBN_TEMPS_CLEANED;
1970 ControlFlowGraph::EdgeSet iEdges = cfg_->inEdges(bbn);
1971
1972 for (ControlFlowGraph::EdgeSet::iterator inIter = iEdges.begin();
1973 inIter != iEdges.end(); inIter++) {
1974 ControlFlowEdge& cfe = **inIter;
1975 // cannot fill calls.
1976 if (!cfe.isCallPassEdge()) {
1977 BasicBlockNode& prevBBN = cfg_->tailNode(cfe);
1978 if (prevBBN.isNormalBB() &&
1979 bbnStatus_[&prevBBN] < BBN_BOTH_FILLED) {
1980 return;
1981 }
1982 }
1983 }
1984 }
1985
1986 // delete the RM. go to state BBN_ALL_DONE
1987 std::map<BasicBlock*,SimpleResourceManager*>::iterator rmi =
1988 resourceManagers_.find(&bbn.basicBlock());
1989 if (rmi != resourceManagers_.end()) {
1990 if (rmi->second != NULL) {
1992 }
1993 resourceManagers_.erase(rmi);
1994 }
1995 bbnStatus_[&bbn] = BBN_ALL_DONE;
1996
1997}
void unassignTempAssigns(DataDependenceGraph::NodeSet &tempAssigns, SimpleResourceManager &rm)

References assert, BasicBlockNode::basicBlock(), BBN_ALL_DONE, BBN_BOTH_FILLED, BBN_TEMPS_CLEANED, bbnStatus_, cfg_, SimpleResourceManager::disposeRM(), BoostGraph< GraphNode, GraphEdge >::inEdges(), ControlFlowEdge::isCallPassEdge(), BasicBlockNode::isNormalBB(), resourceManagers_, BoostGraph< GraphNode, GraphEdge >::tailNode(), tempResultNodes_, and unassignTempAssigns().

Referenced by bbFilled(), bbnScheduled(), fillDelaySlots(), updateFTBBAndCfg(), and updateJumpsAndCfg().

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
oldMove in jump target BB.
Returns
new Move for this BB.

Definition at line 1578 of file CopyingDelaySlotFiller.cc.

1578 {
1579 if (AssocTools::containsKey(moves_,&old)) {
1580 return moves_[&old];
1581 } else {
1582 MoveNode& oldMN = ddg_->nodeOfMove(old);
1583
1584 auto newMove = old.copy();
1585 newMove->setBus(um_->universalBus());
1586
1587 Terminal& source = newMove->source();
1588 if (oldMN.isSourceOperation()) {
1589 assert(source.isFUPort());
1590 std::string fuName = source.functionUnit().name();
1591 //TODO: which is the correct annotation here?
1594 fuName);
1595 newMove->setAnnotation(srcUnit);
1596
1597 const Operation &srcOp = oldMN.sourceOperation().operation();
1599 srcOp.name());
1600 newMove->setSource(new TerminalFUPort(
1601 hwop, old.source().operationIndex()));
1602 } else {
1603 if (source.isRA()) {
1604 newMove->setSource(
1605 new TerminalFUPort(
1607 }
1608 }
1609
1610 Terminal& dest = newMove->destination();
1611 if (oldMN.isDestinationOperation()) {
1612 assert(dest.isFUPort());
1613
1614 std::string fuName = dest.functionUnit().name();
1615 //TODO: which is the correct annotation here?
1618 fuName);
1619 newMove->setAnnotation(dstUnit);
1620
1621 const Operation &dstOp = oldMN.destinationOperation().operation();
1623 dstOp.name());
1624 newMove->setDestination(new TerminalFUPort(
1625 hwop, old.destination().operationIndex()));
1626 } else {
1627 if (dest.isRA()) {
1628 newMove->setDestination(
1629 new TerminalFUPort(
1631 }
1632 }
1633
1634
1635 moves_[&old] = newMove;
1636
1637 // set guard of new move to be same as old move.
1638 if (!old.isUnconditional()) {
1639 TTAProgram::MoveGuard* g = old.guard().copy();
1640 newMove->setGuard(g);
1641 }
1642 return newMove;
1643 }
1644}
SpecialRegisterPort * returnAddressPort() const
std::shared_ptr< Move > copy() const
Definition Move.cc:413
@ ANN_CONN_CANDIDATE_UNIT_DST
Dst. unit candidate.
@ ANN_CONN_CANDIDATE_UNIT_SRC
Src. unit candidate.
virtual const TTAMachine::FunctionUnit & functionUnit() const
Definition Terminal.cc:251
virtual int operationIndex() const
Definition Terminal.cc:364
virtual bool isFUPort() const
Definition Terminal.cc:118
virtual TTAMachine::HWOperation * operation(const std::string &name) const
UniversalFunctionUnit & universalFunctionUnit() const
TTAMachine::Bus & universalBus() const

References TTAProgram::ProgramAnnotation::ANN_CONN_CANDIDATE_UNIT_DST, TTAProgram::ProgramAnnotation::ANN_CONN_CANDIDATE_UNIT_SRC, assert, AssocTools::containsKey(), TTAMachine::Machine::controlUnit(), TTAProgram::Move::copy(), TTAProgram::MoveGuard::copy(), ddg_, TTAProgram::Move::destination(), MoveNode::destinationOperation(), TTAProgram::Terminal::functionUnit(), TTAProgram::Move::guard(), MoveNode::isDestinationOperation(), TTAProgram::Terminal::isFUPort(), TTAProgram::Terminal::isRA(), MoveNode::isSourceOperation(), TTAProgram::Move::isUnconditional(), moves_, TTAMachine::Component::name(), Operation::name(), DataDependenceGraph::nodeOfMove(), ProgramOperation::operation(), UniversalFunctionUnit::operation(), TTAProgram::Terminal::operationIndex(), TTAMachine::ControlUnit::returnAddressPort(), TTAProgram::Move::source(), MoveNode::sourceOperation(), um_, UniversalMachine::universalBus(), and UniversalMachine::universalFunctionUnit().

Referenced by getMoveNode().

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
oldProgramOperation in jump target BB.
Returns
new MoveNode for this BB.

Definition at line 1497 of file CopyingDelaySlotFiller.cc.

1498 {
1500 return *moveNodes_[&old];
1501 } else {
1502 auto movePtr = getMove(old.move());
1503 MoveNode *newMN = new MoveNode(movePtr);
1504 ddg_->addNode(*newMN, bbn);
1505 ddg_->copyDependencies(old,*newMN, false, fillOverBackEdge);
1506 moveNodeBuses_[newMN] = &old.move().bus();
1507
1508 moveNodes_[&old] = newMN;
1509 oldMoveNodes_[newMN] = &old;
1510 mnOwned_[newMN] = true;
1511 if (old.isSourceOperation()) {
1512 newMN->setSourceOperationPtr(
1514 old.sourceOperationPtr(), bbn, fillOverBackEdge));
1515 assert(newMN->isSourceOperation());
1516 }
1517 if (old.isGuardOperation()) {
1518 newMN->setGuardOperationPtr(
1519 getProgramOperationPtr(old.guardOperationPtr(), bbn, fillOverBackEdge));
1520 }
1521 if (old.isDestinationOperation()) {
1522 for (unsigned int i = 0; i < old.destinationOperationCount(); i++) {
1525 old.destinationOperationPtr(i), bbn, fillOverBackEdge));
1526 }
1528 }
1529 return *newMN;
1530 }
1531}
ProgramOperationPtr getProgramOperationPtr(ProgramOperationPtr old, BasicBlockNode &bbn, bool fillOverBackEdge)
std::map< MoveNode *, MoveNode *, MoveNode::Comparator > oldMoveNodes_
std::shared_ptr< TTAProgram::Move > getMove(TTAProgram::Move &old)
std::map< MoveNode *, const TTAMachine::Bus *, MoveNode::Comparator > moveNodeBuses_
void copyDependencies(const MoveNode &src, MoveNode &dst, bool ignoreSameBBBackedges, bool moveOverLoopEdge=true)
void addNode(MoveNode &moveNode)
void setSourceOperationPtr(ProgramOperationPtr po)
Definition MoveNode.cc:541
ProgramOperationPtr sourceOperationPtr() const
Definition MoveNode.cc:458
unsigned int destinationOperationCount() const
bool isGuardOperation() const
Definition MoveNode.cc:181
ProgramOperationPtr destinationOperationPtr(unsigned int index=0) const
void addDestinationOperationPtr(ProgramOperationPtr po)
Definition MoveNode.cc:533

References MoveNode::addDestinationOperationPtr(), DataDependenceGraph::addNode(), assert, TTAProgram::Move::bus(), AssocTools::containsKey(), DataDependenceGraph::copyDependencies(), ddg_, MoveNode::destinationOperationCount(), MoveNode::destinationOperationPtr(), getMove(), getProgramOperationPtr(), MoveNode::guardOperationPtr(), MoveNode::isDestinationOperation(), MoveNode::isGuardOperation(), MoveNode::isSourceOperation(), mnOwned_, MoveNode::move(), moveNodeBuses_, moveNodes_, oldMoveNodes_, MoveNode::setGuardOperationPtr(), MoveNode::setSourceOperationPtr(), and MoveNode::sourceOperationPtr().

Referenced by collectMoves(), and getProgramOperationPtr().

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
oldProgramOperation in jump target BB.
Returns
new ProgramOperation for this BB.

Definition at line 1542 of file CopyingDelaySlotFiller.cc.

1543 {
1545 return programOperations_[old.get()];
1546 } else {
1549 new ProgramOperation(old->operation()));
1550 programOperations_[old.get()] = po;
1551 oldProgramOperations_[po.get()] = old;
1552 for (int i = 0; i < old->inputMoveCount();i++) {
1553 MoveNode& mn = old->inputMove(i);
1555 po->addInputNode(getMoveNode(mn, bbn, fillOverBackEdge));
1556 }
1557 for (int j = 0; j < old->outputMoveCount();j++) {
1558 MoveNode& mn = old->outputMove(j);
1559 if (mn.isSourceOperation()) {
1560 po->addOutputNode(getMoveNode(mn,bbn,fillOverBackEdge));
1561 } else {
1562 po->addGuardOutputNode(getMoveNode(mn,bbn, fillOverBackEdge));
1563 }
1564 }
1565 return po;
1566 }
1567}
std::shared_ptr< ProgramOperation > ProgramOperationPtr
Definition MoveNode.hh:53
std::map< ProgramOperation *, ProgramOperationPtr, ProgramOperation::Comparator > oldProgramOperations_

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

Referenced by getMoveNode().

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
cfgControlFlowGraph of the procedure. @ddg ddg whole-procedure ddg of the procedure.
machinemachine we are scheduling to.
umuniversalmachine.

Definition at line 1937 of file CopyingDelaySlotFiller.cc.

1939 {
1940 cfg_ = &cfg;
1941 ddg_ = &ddg;
1943
1945 bbnStatus_.clear();
1946}

References bbnStatus_, cfg_, TTAMachine::Machine::controlUnit(), ddg_, TTAMachine::ControlUnit::delaySlots(), delaySlots_, UniversalMachine::instance(), machine, and um_.

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.

1652 {
1653
1654 std::list<MoveNode*> toDeleteNodes;
1655 for (std::map<MoveNode*,MoveNode*,MoveNode::Comparator>::iterator mnIter =
1656 moveNodes_.begin(); mnIter != moveNodes_.end();
1657 mnIter++ ) {
1658 MoveNode* second = mnIter->second;
1659 if (mnOwned_[second] == true) {
1660 mnOwned_.erase(second);
1661
1662 if ((keptTempNodes == NULL ||
1663 (keptTempNodes->find(second) == keptTempNodes->end()))
1664 && !second->isScheduled()) {
1665 // queue to be deleted
1666 toDeleteNodes.push_back(second);
1667 }
1668 }
1669 }
1670 moveNodes_.clear();
1671 moveNodeBuses_.clear();
1672 mnOwned_.clear();
1673 oldMoveNodes_.clear();
1674
1675 // actually delete the movenodes.
1676 for (std::list<MoveNode*>::iterator i = toDeleteNodes.begin();
1677 i != toDeleteNodes.end(); i++) {
1678 assert (!(*i)->isScheduled());
1679 ddg_->removeNode(**i);
1680 delete *i;
1681 }
1682
1683 moves_.clear();
1684
1685 programOperations_.clear();
1686 oldProgramOperations_.clear();
1687}
void removeNode(MoveNode &node)

References assert, ddg_, MoveNode::isScheduled(), mnOwned_, moveNodeBuses_, moveNodes_, moves_, oldMoveNodes_, oldProgramOperations_, programOperations_, and DataDependenceGraph::removeNode().

Referenced by tryToFillSlots().

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
bbnjust destination basic block.
Returns
if anything was filled.

Definition at line 537 of file CopyingDelaySlotFiller.cc.

537 {
538 if (bbnStatus_[&bbn] == BBN_UNKNOWN) {
539 return false;
540 }
541 if (!areAllJumpPredsScheduled(bbn)) {
542 return false;
543 }
544
545 bool cfgChanged = false;
546 bool cfgChangedAfterRecheck = false;
547
549
550 // first fill all incoming jumps.
551 for (auto inIter = jumpEdges.begin(); inIter != jumpEdges.end();) {
552 ControlFlowEdge& cfe = **inIter;
553 BasicBlockNode& jumpOrigin = cfg_->tailNode(cfe);
554
555 if (jumpOrigin.isNormalBB() &&
556 (bbnStatus_[&jumpOrigin] == BBN_SCHEDULED ||
557 bbnStatus_[&jumpOrigin] == BBN_FALLTHRU_FILLED)) {
558
559 bool changed = fillDelaySlots(jumpOrigin, delaySlots_, false);
560 cfgChanged |= changed;
561 cfgChangedAfterRecheck |= changed;
562
563 bbFilled(jumpOrigin);
564
565 BasicBlockNode* fallThruSisterNode =
566 cfg_->fallThruSuccessor(jumpOrigin);
567
568 // so we have some left-behind sister NODE
569 if (fallThruSisterNode != NULL &&
570 bbnStatus_[fallThruSisterNode] > BBN_UNKNOWN &&
571 bbnStatus_[&jumpOrigin] < BBN_TEMPS_CLEANED &&
572 areAllJumpPredsFilled(*fallThruSisterNode)) {
573 changed = fillDelaySlots(jumpOrigin, delaySlots_, true);
574 cfgChanged |= changed;
575 cfgChangedAfterRecheck |= changed;
576 bbFilled(jumpOrigin);
577 // may have been removed totally.
578 }
579
580 // If we changed the cfg, loafd the inedges again.
581 if (cfgChangedAfterRecheck) {
582 if (!cfg_->hasNode(bbn)) {
583 return true;
584 }
585 cfgChangedAfterRecheck = false;
586 jumpEdges = cfg_->incomingJumpEdges(bbn);
587 inIter = jumpEdges.begin();
588 continue;
589 }
590 }
591 inIter++;
592 }
593
594 // No Fts to fill if the whole Basic Block is gone!
595 if (cfgChanged && !cfg_->hasNode(bbn)) {
596 return true;
597 }
598
599 // then all incoming jumps should be filled, fall-throughs can fill
600 auto ftEdge = cfg_->incomingFTEdge(bbn);
601 // may still be call pass, which is not allowed.
602 if (ftEdge != nullptr && ftEdge->isFallThroughEdge()) {
603 BasicBlockNode& ftOrigin = cfg_->tailNode(*ftEdge);
604
605 // fall thru-predecessor can be filled if it's scheduled.
606 if (bbnStatus_[&ftOrigin] == BBN_JUMP_FILLED) {
607 cfgChanged |= fillDelaySlots(ftOrigin, delaySlots_, true);
608 bbFilled(ftOrigin);
609 } else {
610 // do not take space from backwards jumps, ie loop jumps.
611 if (bbnStatus_[&ftOrigin] == BBN_SCHEDULED) {
612 BasicBlockNode* jumpSisterNode =
613 cfg_->jumpSuccessor(bbn);
614 if (jumpSisterNode != NULL &&
615 jumpSisterNode->originalStartAddress() >
616 bbn.originalStartAddress() &&
617 areAllJumpPredsFilled(*jumpSisterNode)) {
618
619 cfgChanged |= fillDelaySlots(ftOrigin, delaySlots_, true);
620 bbFilled(ftOrigin);
621 }
622 }
623 }
624 }
625 return cfgChanged;
626}
InstructionAddress originalStartAddress() const
BasicBlockNode * fallThruSuccessor(const BasicBlockNode &bbn) const
ControlFlowEdge * incomingFTEdge(const BasicBlockNode &bbn) const
BasicBlockNode * jumpSuccessor(BasicBlockNode &bbn)
EdgeSet incomingJumpEdges(const BasicBlockNode &bbn) const
bool areAllJumpPredsFilled(BasicBlockNode &bbn) const
bool areAllJumpPredsScheduled(BasicBlockNode &bbn) const
void bbFilled(BasicBlockNode &bbn)

References areAllJumpPredsFilled(), areAllJumpPredsScheduled(), bbFilled(), BBN_FALLTHRU_FILLED, BBN_JUMP_FILLED, BBN_SCHEDULED, BBN_TEMPS_CLEANED, BBN_UNKNOWN, bbnStatus_, cfg_, delaySlots_, ControlFlowGraph::fallThruSuccessor(), fillDelaySlots(), BoostGraph< GraphNode, GraphEdge >::hasNode(), ControlFlowGraph::incomingFTEdge(), ControlFlowGraph::incomingJumpEdges(), BasicBlockNode::isNormalBB(), ControlFlowGraph::jumpSuccessor(), BasicBlockNode::originalStartAddress(), and BoostGraph< GraphNode, GraphEdge >::tailNode().

Referenced by bbnScheduled().

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
poProgramOperation 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.

1718 {
1719 for (int i = 0; i < po->inputMoveCount(); i++) {
1720 MoveNode& mn = po->inputMove(i);
1721 if (tempAssigns.find(&mn) != tempAssigns.end()) {
1722 return true;
1723 }
1724 for (unsigned int j = 0; j < movesToCopy.size(); j++) {
1725 std::list<MoveNode*>& moveList = movesToCopy.at(j);
1726 for (std::list<MoveNode*>::iterator iter = moveList.begin();
1727 iter != moveList.end(); iter++) {
1728 if (&mn == *iter) {
1729 return true;
1730 }
1731 }
1732 }
1733 }
1734 for (int i = 0; i < po->outputMoveCount(); i++) {
1735 MoveNode& mn = po->outputMove(i);
1736 if (tempAssigns.find(&mn) != tempAssigns.end()) {
1737 return true;
1738 }
1739 }
1740 return false;
1741}

◆ 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
movesmoves to assign
slotsToFillnumber of instructions to fill
firstCycleToFillcycle where to fill first instruction
rmresourcemanager to the bb being filled to.
Returns
true if the filling succeeded, false if failed.

Definition at line 1283 of file CopyingDelaySlotFiller.cc.

1286 {
1287 bool failed = false;
1288
1289 // then try to assign the nodes
1290 for (unsigned int i = 0; i < (unsigned)slotsToFill &&
1291 i < moves.size() && !failed; i++) {
1292 list<MoveNode*>& movesInThisCycle = moves.at(i);
1293 int currentCycle = firstCycleToFill + i;
1294
1295 for (std::list<MoveNode*>::iterator iter = movesInThisCycle.begin();
1296 iter != movesInThisCycle.end() && !failed; iter++) {
1297 MoveNode& mn = **iter;
1298
1299 if (!mn.isScheduled()) {
1300
1301 // if cannot assign move, try to remove
1302 // predicate(of allowed) and try again
1303 if (!rm.canAssign(currentCycle, mn)) {
1304 if (!mn.move().isUnconditional()) {
1305 MoveNode* old = oldMoveNodes_[&mn];
1306 if (old == NULL) {
1307 failed = true;
1308 break;
1309 }
1310 if (allowedToSpeculate(*old)) {
1311 if (mn.isGuardOperation()) {
1312 auto guardOp = mn.guardOperationPtr();
1313 guardOp->removeGuardOutputNode(mn);
1315 }
1316 mn.move().setGuard(nullptr);
1317 } else {
1318 failed = true;
1319 break;
1320 }
1321 if (!rm.canAssign(currentCycle, mn)) {
1322 failed = true;
1323 break;
1324 }
1325 } else {
1326 failed = true;
1327 break;
1328 }
1329 }
1330
1331 rm.assign(currentCycle, mn);
1332 } else {
1333 if (mn.cycle() != currentCycle) {
1334 failed = true;
1335 break;
1336 }
1337 }
1338 assert(mn.isScheduled());
1339 assert(mn.cycle() == currentCycle);
1340
1341 if (mn.move().source().isImmediateRegister()) {
1342 const ImmediateUnit& immu = mn.move().source().immediateUnit();
1343 bool limmFound = false;
1344 for (int j = (firstCycleToFill+i-immu.latency());
1345 j >= firstCycleToFill && !limmFound; j--) {
1346 const Instruction* ins = rm.instruction(j);
1347 for (int k = 0; k < ins->immediateCount(); k++) {
1348 Immediate& imm = ins->immediate(k);
1349 if (imm.destination().equals(mn.move().source())) {
1350 limmFound = true;
1351 break;
1352 }
1353 }
1354 }
1355 // limm too early?
1356 if (!limmFound) {
1357 failed = true;
1358 break;
1359 }
1360 }
1361
1362 // if not destination operand, no need to check
1363 // other moves of the operation.
1364 if (!mn.isDestinationOperation()) {
1365 continue;
1366 }
1367
1368 // check that result and other operand scheduling is possible
1369 // if not, this can not be scheuduled either.
1370 // even though alone would be possible
1372 mn, firstCycleToFill, rm,
1373 firstCycleToFill + (slotsToFill-1), nextBBStart,
1374 tempAssigns)) {
1375 failed = true;
1376 break;
1377 }
1378 }
1379 }
1380 if (failed) {
1381
1382 // and also movenodes assigned to delay slots.
1383 for (int i = 0; i < slotsToFill; i++) {
1384 list<MoveNode*>& movesInThisCycle = moves.at(i);
1385 for (std::list<MoveNode*>::iterator iter =
1386 movesInThisCycle.begin();
1387 iter != movesInThisCycle.end();iter++) {
1388 MoveNode& mn = **iter;
1389 if (mn.isScheduled()) {
1390 rm.unassign(mn);
1391 }
1392 }
1393 }
1394 return false;
1395 }
1396 return true;
1397}
bool tryToAssignOtherMovesOfDestOps(MoveNode &mn, int firstCycleToFill, ResourceManager &rm, int lastCycle, int nextBBStart, DataDependenceGraph::NodeSet &tempAssigns)
void unsetGuardOperation()
Definition MoveNode.cc:771
virtual TTAProgram::Instruction * instruction(int cycle) const =0
virtual bool canAssign(int cycle, MoveNode &node, const TTAMachine::Bus *bus=nullptr, const TTAMachine::FunctionUnit *srcFU=nullptr, const TTAMachine::FunctionUnit *dstFU=nullptr, int immWriteCycle=-1, const TTAMachine::ImmediateUnit *immu=nullptr, int immRegIndex=-1) const =0
virtual void unassign(MoveNode &node)=0
virtual void assign(int cycle, MoveNode &node, const TTAMachine::Bus *bus=nullptr, const TTAMachine::FunctionUnit *srcFU=nullptr, const TTAMachine::FunctionUnit *dstFU=nullptr, int immWriteCycle=-1, const TTAMachine::ImmediateUnit *immu=nullptr, int immRegIndex=-1)=0
virtual bool equals(const Terminal &other) const =0

References allowedToSpeculate(), 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(), oldMoveNodes_, TTAProgram::Move::setGuard(), TTAProgram::Move::source(), tryToAssignOtherMovesOfDestOps(), ResourceManager::unassign(), and MoveNode::unsetGuardOperation().

Referenced by tryToFillSlots().

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.

1406 {
1407
1408 for (unsigned int i = 0; i < mn.destinationOperationCount(); i++) {
1410 if (!tryToAssignOtherMovesOfOp(po, firstCycleToFill, rm, lastCycle,
1411 nextBBStart, tempAssigns)) {
1412 return false;
1413 }
1414 }
1415 return true;
1416}
bool tryToAssignOtherMovesOfOp(ProgramOperation &po, int firstCycleToFill, ResourceManager &rm, int lastCycle, int nextBBStart, DataDependenceGraph::NodeSet &tempAssigns)

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

Referenced by tryToAssignNodes().

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.

1420 {
1421
1422 // first inputs.
1423 if (!po.areInputsAssigned()) {
1424 for (int j = 0; j < po.inputMoveCount(); j++) {
1425 MoveNode& operMn = po.inputMove(j);
1426 // schedule only those not scheduled
1427 if (!operMn.isScheduled()) {
1428 int mnCycle =
1429 firstCycleToFill +
1430 oldMoveNodes_[&operMn]->cycle() -
1431 nextBBStart;
1432 const TTAMachine::Bus* bus =
1433 mnCycle > lastCycle ? moveNodeBuses_[&operMn] : nullptr;
1435 if (!rm.canAssign(mnCycle, operMn, bus)) {
1436 if (operMn.move().isUnconditional()) {
1437 return false;
1438 }
1439 if (!allowedToSpeculate(operMn)) {
1440 return false;
1441 }
1442 if (operMn.isGuardOperation()) {
1443 auto guardOp = operMn.guardOperationPtr();
1444 guardOp->removeGuardOutputNode(operMn);
1445 operMn.unsetGuardOperation();
1446 }
1447 operMn.move().setGuard(nullptr);
1448 if (!rm.canAssign(mnCycle, operMn, bus)) {
1449 return false;
1450 }
1451 }
1452
1453 rm.assign(mnCycle, operMn);
1454 // need to be removed at end
1455 if (mnCycle > lastCycle) {
1456 tempAssigns.insert(&operMn);
1457 }
1458 }
1459 } // end for
1460 }
1461
1462 // then outputs.
1463 for (int j = 0; j < po.outputMoveCount(); j++) {
1464 MoveNode& resMn = po.outputMove(j);
1465 if (!resMn.isScheduled()) {
1466 int mnCycle =
1467 firstCycleToFill + oldMoveNodes_[&resMn]->cycle() -
1468 nextBBStart;
1469
1470 const TTAMachine::Bus* bus =
1471 mnCycle > lastCycle ? moveNodeBuses_[&resMn] : nullptr;
1472 if (!rm.canAssign(mnCycle, resMn, bus)) {
1473 return false;
1474 } else {
1475 rm.assign(mnCycle, resMn);
1476 if (mnCycle > lastCycle) {
1477 tempAssigns.insert(&resMn);
1478 }
1479 }
1480 }
1481 }
1482 return true;
1483}
int outputMoveCount() const
int inputMoveCount() const
MoveNode & inputMove(int index) const
MoveNode & outputMove(int index) const

References allowedToSpeculate(), 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(), moveNodeBuses_, oldMoveNodes_, ProgramOperation::outputMove(), ProgramOperation::outputMoveCount(), TTAProgram::Move::setGuard(), and MoveNode::unsetGuardOperation().

Referenced by tryToAssignOtherMovesOfDestOps().

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
blockToFillBB containing the delay slots.
nextBBblock where from to copy the instructions.
slotsToFillhow many slots tries to fill
removeGuardshow many first instructions need guard removed.
grIndexindex of the guard register of the jump
grFileregister file of the guard of the jump.
skippedJumpif 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.

820 {
821 skippedJump = NULL;
822 BasicBlock& blockToFill = blockToFillNode.basicBlock();
823 SimpleResourceManager& rm = *resourceManagers_[&blockToFill];
824 BasicBlock& nextBB = nextBBNode.basicBlock();
825 SimpleResourceManager* nextRm = resourceManagers_[&nextBB];
826
827 if (nextRm == NULL) {
828 return false;
829 }
830
831 int firstCycleToFill =
832 rm.smallestCycle() + blockToFill.instructionCount() - slotsToFill;
833 int nextBBStart = nextRm->smallestCycle();
834
835 MoveNodeListVector moves(slotsToFill);
836
837 // Collect all the moves to fill.
838 if (!collectMoves(
839 blockToFillNode, nextBBNode, moves, slotsToFill,fallThru,
840 removeGuards, jumpMove, grIndex, grFile, skippedJump,
841 delaySlots)) {
842 loseCopies(NULL);
843 return false;
844 }
845
846 //check imm reads after (safeguard against same imm read twice)
847 if (!checkImmediatesAfter(nextBB, slotsToFill)) {
848 loseCopies(NULL);
849 return false;
850 }
851
852 // now we have got all the movenodes we are going to fill.
853 // then try to assign them to the block where they are being filled to.
854
855 // set containing po result moves etc.
857 if (tryToAssignNodes(moves, slotsToFill, firstCycleToFill,rm, nextBBStart,
858 tempAssigns)) {
859 // we succeeded.
860 // delete temporaty copies of other movenodes.
861 loseCopies(&tempAssigns);
862
863 AssocTools::append(tempAssigns, tempResultNodes_[&blockToFillNode]);
864 return true;
865 } else {
866 loseCopies(&tempAssigns);
867 unassignTempAssigns(tempAssigns, rm);
868 // failing. delete created movenodes and report failure
869 return false;
870 }
871}
static void append(const ContainerType &src, ContainerType &dest)
std::vector< std::list< MoveNode * > > MoveNodeListVector
void loseCopies(DataDependenceGraph::NodeSet *keptTempNodes)
bool tryToAssignNodes(MoveNodeListVector &moves, int slotsToFill, int firstCycleToFill, ResourceManager &rm, int nextBBStart, DataDependenceGraph::NodeSet &tempAssigns)
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)

References AssocTools::append(), BasicBlockNode::basicBlock(), checkImmediatesAfter(), collectMoves(), TTAProgram::CodeSnippet::instructionCount(), loseCopies(), resourceManagers_, SimpleResourceManager::smallestCycle(), tempResultNodes_, tryToAssignNodes(), and unassignTempAssigns().

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.

2002 {
2003 for (DataDependenceGraph::NodeSet::iterator j = tempAssigns.begin();
2004 j != tempAssigns.end(); j++) {
2005 assert((**j).isScheduled());
2006 rm.unassign(**j);
2007 ddg_->removeNode(**j);
2008 delete *j;
2009 }
2010 tempAssigns.clear();
2011}
virtual void unassign(MoveNode &node) override

References assert, ddg_, DataDependenceGraph::removeNode(), and SimpleResourceManager::unassign().

Referenced by finishBB(), and tryToFillSlots().

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.

335 {
336
339
340 for (int i = 0; i < slotsFilled; i++) {
341 assert(!irm.hasReference(
342 nextBBN.basicBlock().instructionAtIndex(i)));
343 }
344
345 if (slotsFilled == nextBBN.basicBlock().instructionCount() &&
346 cfg_->inDegree(nextBBN) == 1) {
347 auto oEdges = cfg_->outEdges(nextBBN);
348 assert(oEdges.size() == 1);
349 ControlFlowEdge& laterEdge = **oEdges.begin();
350 BasicBlockNode& newDestNode = cfg_->headNode(laterEdge);
351
352 // update CFG because jump dest moved.
353 // the predicate is the same as the original
354 // fall-trhough, but if later is a jump or call pass.
355 // this is also a jump or call pass.
356 ControlFlowEdge* newEdge =
357 new ControlFlowEdge(
358 edge.edgePredicate(), laterEdge.edgeType());
359 cfg_->disconnectNodes(jumpingBB, nextBBN);
360 cfg_->connectNodes(jumpingBB, newDestNode, *newEdge);
361
362 cfg_->removeNode(nextBBN);
363 finishBB(nextBBN, true);
364
365 for (int i = 0;
366 i < nextBBN.basicBlock().instructionCount(); i++) {
367 Instruction& ins =
368 nextBBN.basicBlock().instructionAtIndex(i);
369 while(ins.moveCount()) {
370 Move& move = ins.move(0);
371 MoveNode & mn = ddg_->nodeOfMove(move);
372 ddg_->removeNode(mn);
373 delete &mn;
374 ins.removeMove(move);
375 }
376 while (ins.immediateCount()) {
377 Immediate& imm = ins.immediate(0);
378 ins.removeImmediate(imm);
379 }
380 }
381 delete &nextBBN;
382 // cfg changed
383 return true;
384 } else {
385 nextBBN.basicBlock().skipFirstInstructions(slotsFilled);
386 // cfg not changed
387 return false;
388 }
389}
virtual void disconnectNodes(const Node &nTail, const Node &nHead)
virtual void removeNode(Node &node)
virtual int inDegree(const Node &node) const
virtual void connectNodes(const Node &nTail, const Node &nHead, Edge &e)
CFGEdgeType edgeType()
CFGEdgePredicate edgePredicate() const
void skipFirstInstructions(int count)
Definition BasicBlock.cc:98
void removeImmediate(Immediate &imm)
void removeMove(Move &move)

References assert, BasicBlockNode::basicBlock(), cfg_, BoostGraph< GraphNode, GraphEdge >::connectNodes(), ddg_, BoostGraph< GraphNode, GraphEdge >::disconnectNodes(), ControlFlowEdge::edgePredicate(), ControlFlowEdge::edgeType(), finishBB(), TTAProgram::InstructionReferenceManager::hasReference(), BoostGraph< GraphNode, GraphEdge >::headNode(), TTAProgram::Instruction::immediate(), TTAProgram::Instruction::immediateCount(), BoostGraph< GraphNode, GraphEdge >::inDegree(), TTAProgram::CodeSnippet::instructionAtIndex(), TTAProgram::CodeSnippet::instructionCount(), TTAProgram::Program::instructionReferenceManager(), TTAProgram::Instruction::move(), TTAProgram::Instruction::moveCount(), DataDependenceGraph::nodeOfMove(), BoostGraph< GraphNode, GraphEdge >::outEdges(), ControlFlowGraph::program(), TTAProgram::Instruction::removeImmediate(), TTAProgram::Instruction::removeMove(), DataDependenceGraph::removeNode(), BoostGraph< GraphNode, GraphEdge >::removeNode(), 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
jumpBBNbasic block whose delay slots are filled
fillingBBNnext basic block where the instructions are taken
fillEdgeCFG edge connecting the basic blocks.
jumpAddressjump address being updated to new one.
slotsFilledhow many delay slots were filled.
Returns
true if removed a basic block or an cfg edge.

Definition at line 1796 of file CopyingDelaySlotFiller.cc.

1800 {
1801
1802 bool cfgChanged = false;
1803 TerminalInstructionReference* jumpAddress = jumpAddressMove != NULL ?
1804 dynamic_cast<TerminalInstructionReference*>(
1805 &jumpAddressMove->source()) :
1806 dynamic_cast<TerminalInstructionReference*>(
1807 &jumpAddressImmediate->value());
1808
1809 BasicBlock& nextBB = fillingBBN.basicBlock();
1811 instructionReferenceManager();
1812 // TODO: only the correct jump one, nto both
1813 assert(slotsFilled <= nextBB.instructionCount());
1814
1815 // filled whole block, jumping to next bb.
1816 if (slotsFilled == nextBB.instructionCount()) {
1817
1819 cfg_->successors(fillingBBN);
1820 if (nextBBs.size() != 1) {
1821 std::string msg = "no succeessors but no jump";
1822 throw IllegalProgram(__FILE__,__LINE__,__func__, msg);
1823 }
1824
1825 BasicBlockNode& newDestNode = **nextBBs.begin();
1826
1827 // update CFG because jump dest moved.
1828 ControlFlowEdge* newEdge = new ControlFlowEdge(fillEdge);
1829 cfg_->disconnectNodes(jumpBBN, fillingBBN);
1830 cfg_->connectNodes(jumpBBN, newDestNode, *newEdge);
1831 cfgChanged = true;
1832
1833 if (skippedJump != NULL) {
1834 // if we skipped a jump. that jump may have already been filled,
1835 // and then the dest is the dest of that jump,
1836 // not beginning of a bb.
1837 if (skippedJump->isReturn()) {
1838 assert(jumpMove != NULL);
1839 jumpMove->setSource(skippedJump->source().copy());
1842 ANN_STACKFRAME_PROCEDURE_RETURN);
1843 jumpMove->setAnnotation(annotation);
1844 if (jumpAddressMove != NULL && jumpAddressMove != jumpMove) {
1845 jumpAddressMove->parent().removeMove(
1846 *jumpAddressMove);
1847 } else {
1848 // get rid of the insructionreference by setting
1849 // value of the imm to 0.
1850 // better way would be deleting the imm but it's
1851 // much more complicated
1852 if (jumpAddressImmediate != NULL) {
1853 jumpAddressImmediate->setValue(
1854 new TerminalImmediate(SimValue(0,1)));
1855 }
1856 }
1857 }
1858 else {
1860 skippedJump->source().instructionReference();
1861 jumpAddress->setInstructionReference(ir);
1862 }
1863 } else {
1864 // else the dest is the first instruction of the bb after the
1865 // filling bb, skipping the skipped instructions.
1867 newDestNode.basicBlock().instructionAtIndex(
1868 newDestNode.basicBlock().skippedFirstInstructions()));
1869 jumpAddress->setInstructionReference(ir);
1870 }
1871
1872 // if filling block became dead, remove it.
1873 if (cfg_->inDegree(fillingBBN) == 0) {
1874 assert(!irm.hasReference(nextBB.instructionAtIndex(0)));
1875
1876 // no fall-thru, removed only jump to bb.
1877 // remove whole bb then.
1878 cfg_->removeNode(fillingBBN);
1879 finishBB(fillingBBN, true);
1880
1881 for (int i = 0; i < nextBB.instructionCount(); i++) {
1882 Instruction& ins = nextBB.instructionAtIndex(i);
1883 while(ins.moveCount()) {
1884 Move& move = ins.move(0);
1885 MoveNode & mn = ddg_->nodeOfMove(move);
1886 ddg_->removeNode(mn);
1887 delete &mn;
1888 ins.removeMove(move);
1889 }
1890 while (ins.immediateCount()) {
1891 Immediate& imm = ins.immediate(0);
1892 ins.removeImmediate(imm);
1893 }
1894
1895 }
1896 delete &fillingBBN;
1897 }
1898
1899 } else { // not filled whole block.
1900 assert(skippedJump == NULL);
1901 assert(slotsFilled >= nextBB.skippedFirstInstructions());
1903 nextBB.instructionAtIndex(slotsFilled));
1904 jumpAddress->setInstructionReference(ir);
1905
1906 // remove the first instructions that are dead.
1907 if (cfg_->incomingFTEdge(fillingBBN) == nullptr
1908 && &fillingBBN != &cfg_->firstNormalNode()) {
1909 int deadInsCount = 0;
1910 while (nextBB.instructionCount() > deadInsCount &&
1911 !irm.hasReference(
1912 nextBB.instructionAtIndex(deadInsCount))) {
1913 deadInsCount++;
1914 }
1915 nextBB.skipFirstInstructions(deadInsCount);
1916 if (deadInsCount >= nextBB.instructionCount()) {
1917 throw IllegalProgram(
1918 __FILE__,__LINE__,__func__,
1919 "BB got empty illegally");
1920 }
1921 }
1922 }
1923 return cfgChanged;
1924}
#define __func__
virtual NodeSet successors(const Node &node, bool ignoreBackEdges=false, bool ignoreForwardEdges=false) const
BasicBlockNode & firstNormalNode() const
void setAnnotation(const ProgramAnnotation &annotation)
InstructionReference createReference(Instruction &ins)
bool isReturn() const
Definition Move.cc:259
virtual void setInstructionReference(InstructionReference ref)
virtual Terminal * copy() const =0
virtual const InstructionReference & instructionReference() const
Definition Terminal.cc:188

References __func__, assert, BasicBlockNode::basicBlock(), cfg_, BoostGraph< GraphNode, GraphEdge >::connectNodes(), TTAProgram::Terminal::copy(), TTAProgram::InstructionReferenceManager::createReference(), ddg_, BoostGraph< GraphNode, GraphEdge >::disconnectNodes(), finishBB(), ControlFlowGraph::firstNormalNode(), TTAProgram::InstructionReferenceManager::hasReference(), TTAProgram::Instruction::immediate(), TTAProgram::Instruction::immediateCount(), ControlFlowGraph::incomingFTEdge(), BoostGraph< GraphNode, GraphEdge >::inDegree(), TTAProgram::CodeSnippet::instructionAtIndex(), TTAProgram::CodeSnippet::instructionCount(), TTAProgram::Terminal::instructionReference(), TTAProgram::Move::isReturn(), TTAProgram::Instruction::move(), TTAProgram::Instruction::moveCount(), DataDependenceGraph::nodeOfMove(), TTAProgram::Move::parent(), ControlFlowGraph::program(), TTAProgram::Instruction::removeImmediate(), TTAProgram::Instruction::removeMove(), DataDependenceGraph::removeNode(), BoostGraph< GraphNode, GraphEdge >::removeNode(), TTAProgram::AnnotatedInstructionElement::setAnnotation(), TTAProgram::TerminalInstructionReference::setInstructionReference(), TTAProgram::Move::setSource(), TTAProgram::BasicBlock::skipFirstInstructions(), TTAProgram::BasicBlock::skippedFirstInstructions(), TTAProgram::Move::source(), and BoostGraph< GraphNode, GraphEdge >::successors().

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
moveto check
rfRegisterFile containing the register
registerIndexindex of the register.

Definition at line 789 of file CopyingDelaySlotFiller.cc.

790 {
791 Terminal& term = move.destination();
792 if (term.isGPR()) {
793 TerminalRegister& rd = dynamic_cast<TerminalRegister&>(term);
794 if ( &rd.registerFile() == rf && rd.index() ==
795 static_cast<int>(registerIndex)) {
796 return true;
797 }
798 }
799 return false;
800}
virtual int index() const
virtual const TTAMachine::RegisterFile & registerFile() const

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

Referenced by collectMoves().

Here is the call graph for this function:

Member Data Documentation

◆ bbnStatus_

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

◆ cfg_

ControlFlowGraph* CopyingDelaySlotFiller::cfg_
private

◆ ddg_

DataDependenceGraph* CopyingDelaySlotFiller::ddg_
private

◆ delaySlots_

int CopyingDelaySlotFiller::delaySlots_
private

Definition at line 217 of file CopyingDelaySlotFiller.hh.

Referenced by initialize(), and mightFillIncomingTo().

◆ killedBBs_

ControlFlowGraph::NodeSet CopyingDelaySlotFiller::killedBBs_
private

Definition at line 219 of file CopyingDelaySlotFiller.hh.

Referenced by finalizeProcedure().

◆ mnOwned_

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

Definition at line 206 of file CopyingDelaySlotFiller.hh.

Referenced by getMoveNode(), loseCopies(), and ~CopyingDelaySlotFiller().

◆ moveNodeBuses_

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

Definition at line 199 of file CopyingDelaySlotFiller.hh.

Referenced by getMoveNode(), loseCopies(), and tryToAssignOtherMovesOfOp().

◆ moveNodes_

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

Definition at line 196 of file CopyingDelaySlotFiller.hh.

Referenced by getMoveNode(), loseCopies(), and ~CopyingDelaySlotFiller().

◆ moves_

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

Definition at line 198 of file CopyingDelaySlotFiller.hh.

Referenced by getMove(), loseCopies(), and ~CopyingDelaySlotFiller().

◆ oldMoveNodes_

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

◆ oldProgramOperations_

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

Definition at line 195 of file CopyingDelaySlotFiller.hh.

Referenced by getProgramOperationPtr(), and loseCopies().

◆ programOperations_

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

◆ resourceManagers_

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

◆ 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.

Referenced by fillDelaySlots(), finishBB(), and tryToFillSlots().

◆ um_

UniversalMachine* CopyingDelaySlotFiller::um_
private

Definition at line 189 of file CopyingDelaySlotFiller.hh.

Referenced by fillDelaySlots(), getMove(), and initialize().


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