-//===-- MSchedGraph.h - Scheduling Graph ------------------------*- C++ -*-===//
+//===-- MSchedGraph.cpp - Scheduling Graph ----------------------*- C++ -*-===//
//
// The LLVM Compiler Infrastructure
//
#define DEBUG_TYPE "ModuloSched"
#include "MSchedGraph.h"
+#include "../../Target/SparcV9/SparcV9RegisterInfo.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/Target/TargetInstrInfo.h"
-#include "Support/Debug.h"
-#include <iostream>
+#include "llvm/Support/Debug.h"
+#include <cstdlib>
using namespace llvm;
MSchedGraphNode::MSchedGraphNode(const MachineInstr* inst,
MSchedGraph *graph,
- unsigned late)
- : Inst(inst), Parent(graph), latency(late) {
+ unsigned late, bool isBranch)
+ : Inst(inst), Parent(graph), latency(late), isBranchInstr(isBranch) {
//Add to the graph
graph->addNode(inst, this);
}
void MSchedGraphNode::print(std::ostream &os) const {
- os << "MSehedGraphNode: Inst=" << *Inst << ", latency= " << latency << "\n";
+ os << "MSchedGraphNode: Inst=" << *Inst << ", latency= " << latency << "\n";
}
MSchedGraphEdge MSchedGraphNode::getInEdge(MSchedGraphNode *pred) {
//Loop over all the successors of our predecessor
//return the edge the corresponds to this in edge
+ for (MSchedGraphNode::succ_iterator I = pred->succ_begin(),
+ E = pred->succ_end(); I != E; ++I) {
+ if (*I == this)
+ return I.getEdge();
+ }
+ assert(0 && "Should have found edge between this node and its predecessor!");
+ abort();
+}
+
+unsigned MSchedGraphNode::getInEdgeNum(MSchedGraphNode *pred) {
+ //Loop over all the successors of our predecessor
+ //return the edge the corresponds to this in edge
+ int count = 0;
for(MSchedGraphNode::succ_iterator I = pred->succ_begin(), E = pred->succ_end();
I != E; ++I) {
if(*I == this)
- return I.getEdge();
+ return count;
+ count++;
}
assert(0 && "Should have found edge between this node and its predecessor!");
-
+ abort();
+}
+bool MSchedGraphNode::isSuccessor(MSchedGraphNode *succ) {
+ for(succ_iterator I = succ_begin(), E = succ_end(); I != E; ++I)
+ if(*I == succ)
+ return true;
+ return false;
+}
+
+
+bool MSchedGraphNode::isPredecessor(MSchedGraphNode *pred) {
+ if(find( Predecessors.begin(), Predecessors.end(), pred) != Predecessors.end())
+ return true;
+ else
+ return false;
}
+
void MSchedGraph::addNode(const MachineInstr *MI,
MSchedGraphNode *node) {
void MSchedGraph::buildNodesAndEdges() {
//Get Machine target information for calculating latency
- const TargetInstrInfo &MTI = Target.getInstrInfo();
+ const TargetInstrInfo *MTI = Target.getInstrInfo();
std::vector<MSchedGraphNode*> memInstructions;
std::map<int, std::vector<OpIndexNodePair> > regNumtoNodeMap;
//using the op code, create a new node for it, and add to the
//graph.
- MachineOpCode MIopCode = MI->getOpcode();
+ MachineOpCode opCode = MI->getOpcode();
int delay;
+#if 0 // FIXME: LOOK INTO THIS
//Check if subsequent instructions can be issued before
//the result is ready, if so use min delay.
- if(MTI.hasResultInterlock(MIopCode))
- delay = MTI.minLatency(MIopCode);
+ if(MTI->hasResultInterlock(MIopCode))
+ delay = MTI->minLatency(MIopCode);
else
- delay = MTI.maxLatency(MIopCode);
+#endif
+ //Get delay
+ delay = MTI->maxLatency(opCode);
//Create new node for this machine instruction and add to the graph.
//Create only if not a nop
- if(MTI.isNop(MIopCode))
+ if(MTI->isNop(opCode))
continue;
//Add PHI to phi instruction list to be processed later
- if (MIopCode == TargetInstrInfo::PHI)
+ if (opCode == TargetInstrInfo::PHI)
phiInstrs.push_back(MI);
+ bool isBranch = false;
+
+ //We want to flag the branch node to treat it special
+ if(MTI->isBranch(opCode))
+ isBranch = true;
+
//Node is created and added to the graph automatically
- MSchedGraphNode *node = new MSchedGraphNode(MI, this, delay);
+ MSchedGraphNode *node = new MSchedGraphNode(MI, this, delay, isBranch);
DEBUG(std::cerr << "Created Node: " << *node << "\n");
-
- //Check OpCode to keep track of memory operations to add memory dependencies later.
- MachineOpCode opCode = MI->getOpcode();
- if(MTI.isLoad(opCode) || MTI.isStore(opCode))
+ //Check OpCode to keep track of memory operations to add memory dependencies later.
+ if(MTI->isLoad(opCode) || MTI->isStore(opCode))
memInstructions.push_back(node);
//Loop over all operands, and put them into the register number to
//Get Operand
const MachineOperand &mOp = MI->getOperand(i);
- //Check if it has an allocated register (Note: this means it
- //is greater then zero because zero is a special register for
- //Sparc that holds the constant zero
+ //Check if it has an allocated register
if(mOp.hasAllocatedReg()) {
int regNum = mOp.getReg();
-
+
+ if(regNum != SparcV9::g0) {
//Put into our map
regNumtoNodeMap[regNum].push_back(std::make_pair(i, node));
+ }
continue;
}
assert((mOp.getVRegValue() != NULL) && "Null value is defined");
//Check if this is a read operation in a phi node, if so DO NOT PROCESS
- if(mOp.isUse() && (MIopCode == TargetInstrInfo::PHI))
+ if(mOp.isUse() && (opCode == TargetInstrInfo::PHI))
continue;
//Src only uses the register (read)
if(srcIsUse)
srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister,
- MSchedGraphEdge::AntiDep, 1);
+ MSchedGraphEdge::AntiDep, 1);
else if(srcIsUseandDef) {
srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister,
- MSchedGraphEdge::AntiDep, 1);
+ MSchedGraphEdge::AntiDep, 1);
srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister,
- MSchedGraphEdge::OutputDep, 1);
+ MSchedGraphEdge::OutputDep, 1);
}
else
srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister,
- MSchedGraphEdge::OutputDep, 1);
+ MSchedGraphEdge::OutputDep, 1);
}
//Dest node is a read
else {
if(!srcIsUse || srcIsUseandDef)
srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister,
- MSchedGraphEdge::TrueDep,1 );
+ MSchedGraphEdge::TrueDep,1 );
}
void MSchedGraph::addMemEdges(const std::vector<MSchedGraphNode*>& memInst) {
//Get Target machine instruction info
- const TargetInstrInfo& TMI = Target.getInstrInfo();
+ const TargetInstrInfo *TMI = Target.getInstrInfo();
//Loop over all memory instructions in the vector
//Knowing that they are in execution, add true, anti, and output dependencies
for(unsigned destIndex = srcIndex + 1; destIndex < memInst.size(); ++destIndex) {
//source is a Load, so add anti-dependencies (store after load)
- if(TMI.isLoad(srcNodeOpCode))
- if(TMI.isStore(memInst[destIndex]->getInst()->getOpcode()))
+ if(TMI->isLoad(srcNodeOpCode))
+ if(TMI->isStore(memInst[destIndex]->getInst()->getOpcode()))
memInst[srcIndex]->addOutEdge(memInst[destIndex],
MSchedGraphEdge::MemoryDep,
MSchedGraphEdge::AntiDep);
//If source is a store, add output and true dependencies
- if(TMI.isStore(srcNodeOpCode)) {
- if(TMI.isStore(memInst[destIndex]->getInst()->getOpcode()))
+ if(TMI->isStore(srcNodeOpCode)) {
+ if(TMI->isStore(memInst[destIndex]->getInst()->getOpcode()))
memInst[srcIndex]->addOutEdge(memInst[destIndex],
MSchedGraphEdge::MemoryDep,
MSchedGraphEdge::OutputDep);
//All instructions before the src in execution order have an iteration delay of 1
for(unsigned destIndex = 0; destIndex < srcIndex; ++destIndex) {
//source is a Load, so add anti-dependencies (store after load)
- if(TMI.isLoad(srcNodeOpCode))
- if(TMI.isStore(memInst[destIndex]->getInst()->getOpcode()))
+ if(TMI->isLoad(srcNodeOpCode))
+ if(TMI->isStore(memInst[destIndex]->getInst()->getOpcode()))
memInst[srcIndex]->addOutEdge(memInst[destIndex],
MSchedGraphEdge::MemoryDep,
MSchedGraphEdge::AntiDep, 1);
- if(TMI.isStore(srcNodeOpCode)) {
- if(TMI.isStore(memInst[destIndex]->getInst()->getOpcode()))
+ if(TMI->isStore(srcNodeOpCode)) {
+ if(TMI->isStore(memInst[destIndex]->getInst()->getOpcode()))
memInst[srcIndex]->addOutEdge(memInst[destIndex],
MSchedGraphEdge::MemoryDep,
MSchedGraphEdge::OutputDep, 1);