#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetLowering.h"
+#include "llvm/ADT/Statistic.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/MathExtras.h"
using namespace llvm;
+STATISTIC(NumCommutes, "Number of instructions commuted");
+
ScheduleDAG::ScheduleDAG(SelectionDAG &dag, MachineBasicBlock *bb,
const TargetMachine &tm)
: DAG(dag), BB(bb), TM(tm), RegInfo(BB->getParent()->getRegInfo()) {
bool HasFlagUse = false;
for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end();
UI != E; ++UI)
- if (FlagVal.isOperand(*UI)) {
+ if (FlagVal.isOperandOf(*UI)) {
HasFlagUse = true;
NodeSUnit->FlaggedNodes.push_back(N);
SUnitMap[N].push_back(NodeSUnit);
}
}
+/// CalculateDepths - compute depths using algorithms for the longest
+/// paths in the DAG
void ScheduleDAG::CalculateDepths() {
- std::vector<std::pair<SUnit*, unsigned> > WorkList;
- for (unsigned i = 0, e = SUnits.size(); i != e; ++i)
- if (SUnits[i].Preds.empty())
- WorkList.push_back(std::make_pair(&SUnits[i], 0U));
+ unsigned DAGSize = SUnits.size();
+ std::vector<unsigned> InDegree(DAGSize);
+ std::vector<SUnit*> WorkList;
+ WorkList.reserve(DAGSize);
+
+ // Initialize the data structures
+ for (unsigned i = 0, e = DAGSize; i != e; ++i) {
+ SUnit *SU = &SUnits[i];
+ int NodeNum = SU->NodeNum;
+ unsigned Degree = SU->Preds.size();
+ InDegree[NodeNum] = Degree;
+ SU->Depth = 0;
+
+ // Is it a node without dependencies?
+ if (Degree == 0) {
+ assert(SU->Preds.empty() && "SUnit should have no predecessors");
+ // Collect leaf nodes
+ WorkList.push_back(SU);
+ }
+ }
+ // Process nodes in the topological order
while (!WorkList.empty()) {
- SUnit *SU = WorkList.back().first;
- unsigned Depth = WorkList.back().second;
+ SUnit *SU = WorkList.back();
WorkList.pop_back();
- if (SU->Depth == 0 || Depth > SU->Depth) {
- SU->Depth = Depth;
- for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
- I != E; ++I)
- WorkList.push_back(std::make_pair(I->Dep, Depth+1));
+ unsigned &SUDepth = SU->Depth;
+
+ // Use dynamic programming:
+ // When current node is being processed, all of its dependencies
+ // are already processed.
+ // So, just iterate over all predecessors and take the longest path
+ for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
+ I != E; ++I) {
+ unsigned PredDepth = I->Dep->Depth;
+ if (PredDepth+1 > SUDepth) {
+ SUDepth = PredDepth + 1;
+ }
+ }
+
+ // Update InDegrees of all nodes depending on current SUnit
+ for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
+ I != E; ++I) {
+ SUnit *SU = I->Dep;
+ if (!--InDegree[SU->NodeNum])
+ // If all dependencies of the node are processed already,
+ // then the longest path for the node can be computed now
+ WorkList.push_back(SU);
}
}
}
+/// CalculateHeights - compute heights using algorithms for the longest
+/// paths in the DAG
void ScheduleDAG::CalculateHeights() {
- std::vector<std::pair<SUnit*, unsigned> > WorkList;
- SUnit *Root = SUnitMap[DAG.getRoot().Val].front();
- WorkList.push_back(std::make_pair(Root, 0U));
+ unsigned DAGSize = SUnits.size();
+ std::vector<unsigned> InDegree(DAGSize);
+ std::vector<SUnit*> WorkList;
+ WorkList.reserve(DAGSize);
+
+ // Initialize the data structures
+ for (unsigned i = 0, e = DAGSize; i != e; ++i) {
+ SUnit *SU = &SUnits[i];
+ int NodeNum = SU->NodeNum;
+ unsigned Degree = SU->Succs.size();
+ InDegree[NodeNum] = Degree;
+ SU->Height = 0;
+
+ // Is it a node without dependencies?
+ if (Degree == 0) {
+ assert(SU->Succs.empty() && "Something wrong");
+ assert(WorkList.empty() && "Should be empty");
+ // Collect leaf nodes
+ WorkList.push_back(SU);
+ }
+ }
+ // Process nodes in the topological order
while (!WorkList.empty()) {
- SUnit *SU = WorkList.back().first;
- unsigned Height = WorkList.back().second;
+ SUnit *SU = WorkList.back();
WorkList.pop_back();
- if (SU->Height == 0 || Height > SU->Height) {
- SU->Height = Height;
- for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
- I != E; ++I)
- WorkList.push_back(std::make_pair(I->Dep, Height+1));
+ unsigned &SUHeight = SU->Height;
+
+ // Use dynamic programming:
+ // When current node is being processed, all of its dependencies
+ // are already processed.
+ // So, just iterate over all successors and take the longest path
+ for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
+ I != E; ++I) {
+ unsigned SuccHeight = I->Dep->Height;
+ if (SuccHeight+1 > SUHeight) {
+ SUHeight = SuccHeight + 1;
+ }
+ }
+
+ // Update InDegrees of all nodes depending on current SUnit
+ for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
+ I != E; ++I) {
+ SUnit *SU = I->Dep;
+ if (!--InDegree[SU->NodeNum])
+ // If all dependencies of the node are processed already,
+ // then the longest path for the node can be computed now
+ WorkList.push_back(SU);
}
}
}
}
/// CountOperands - The inputs to target nodes have any actual inputs first,
-/// followed by optional memory operands chain operand, then flag operands.
-/// Compute the number of actual operands that will go into the resulting
-/// MachineInstr.
+/// followed by special operands that describe memory references, then an
+/// optional chain operand, then flag operands. Compute the number of
+/// actual operands that will go into the resulting MachineInstr.
unsigned ScheduleDAG::CountOperands(SDNode *Node) {
- unsigned N = Node->getNumOperands();
- while (N && Node->getOperand(N - 1).getValueType() == MVT::Flag)
- --N;
- if (N && Node->getOperand(N - 1).getValueType() == MVT::Other)
- --N; // Ignore chain if it exists.
+ unsigned N = ComputeMemOperandsEnd(Node);
while (N && isa<MemOperandSDNode>(Node->getOperand(N - 1).Val))
--N; // Ignore MemOperand nodes
return N;
}
-/// CountMemOperands - Find the index of the last MemOperandSDNode operand
-unsigned ScheduleDAG::CountMemOperands(SDNode *Node) {
+/// ComputeMemOperandsEnd - Find the index one past the last MemOperandSDNode
+/// operand
+unsigned ScheduleDAG::ComputeMemOperandsEnd(SDNode *Node) {
unsigned N = Node->getNumOperands();
while (N && Node->getOperand(N - 1).getValueType() == MVT::Flag)
--N;
break;
}
- const TargetRegisterClass *TRC = 0;
+ const TargetRegisterClass *SrcRC = 0, *DstRC = 0;
+ SrcRC = TRI->getPhysicalRegisterRegClass(Node->getValueType(ResNo), SrcReg);
+
// Figure out the register class to create for the destreg.
- if (VRBase)
- TRC = RegInfo.getRegClass(VRBase);
- else
- TRC = TRI->getPhysicalRegisterRegClass(Node->getValueType(ResNo), SrcReg);
+ if (VRBase) {
+ DstRC = RegInfo.getRegClass(VRBase);
+ } else {
+ DstRC = DAG.getTargetLoweringInfo()
+ .getRegClassFor(Node->getValueType(ResNo));
+ }
// If all uses are reading from the src physical register and copying the
// register is either impossible or very expensive, then don't create a copy.
- if (MatchReg && TRC->getCopyCost() < 0) {
+ if (MatchReg && SrcRC->getCopyCost() < 0) {
VRBase = SrcReg;
} else {
// Create the reg, emit the copy.
- VRBase = RegInfo.createVirtualRegister(TRC);
- TII->copyRegToReg(*BB, BB->end(), VRBase, SrcReg, TRC, TRC);
+ VRBase = RegInfo.createVirtualRegister(DstRC);
+ TII->copyRegToReg(*BB, BB->end(), VRBase, SrcReg, DstRC, SrcRC);
}
if (InstanceNo > 0)
unsigned VReg = getVR(Op, VRBaseMap);
MI->addOperand(MachineOperand::CreateReg(VReg, false));
- // Verify that it is right.
+ // Verify that it is right. Note that the reg class of the physreg and the
+ // vreg don't necessarily need to match, but the target copy insertion has
+ // to be able to handle it. This handles things like copies from ST(0) to
+ // an FP vreg on x86.
assert(TargetRegisterInfo::isVirtualRegister(VReg) && "Not a vreg?");
if (II) {
- const TargetRegisterClass *RC =
- getInstrOperandRegClass(TRI, TII, *II, IIOpNum);
- assert(RC && "Don't have operand info for this instruction!");
- assert(RegInfo.getRegClass(VReg) == RC &&
- "Register class of operand and regclass of use don't agree!");
+ assert(getInstrOperandRegClass(TRI, TII, *II, IIOpNum) &&
+ "Don't have operand info for this instruction!");
}
}
if (VRBase) {
// Grab the destination register
- const TargetRegisterClass *DRC = 0;
- DRC = RegInfo.getRegClass(VRBase);
+ const TargetRegisterClass *DRC = RegInfo.getRegClass(VRBase);
assert(SRC && DRC && SRC == DRC &&
"Source subregister and destination must have the same class");
} else {
unsigned NumResults = CountResults(Node);
unsigned NodeOperands = CountOperands(Node);
- unsigned NodeMemOperands = CountMemOperands(Node);
+ unsigned MemOperandsEnd = ComputeMemOperandsEnd(Node);
unsigned NumMIOperands = NodeOperands + NumResults;
bool HasPhysRegOuts = (NumResults > II.getNumDefs()) &&
II.getImplicitDefs() != 0;
AddOperand(MI, Node->getOperand(i), i+II.getNumDefs(), &II, VRBaseMap);
// Emit all of the memory operands of this instruction
- for (unsigned i = NodeOperands; i != NodeMemOperands; ++i)
+ for (unsigned i = NodeOperands; i != MemOperandsEnd; ++i)
AddMemOperand(MI, cast<MemOperandSDNode>(Node->getOperand(i))->MO);
// Commute node if it has been determined to be profitable.
delete MI;
MI = NewMI;
}
+ ++NumCommutes;
}
}
TII->insertNoop(*BB, BB->end());
}
-void ScheduleDAG::EmitCrossRCCopy(SUnit *SU, DenseMap<SUnit*, unsigned> &VRBaseMap) {
+void ScheduleDAG::EmitCrossRCCopy(SUnit *SU,
+ DenseMap<SUnit*, unsigned> &VRBaseMap) {
for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
I != E; ++I) {
if (I->isCtrl) continue; // ignore chain preds
projects / oota-llvm.git / blobdiff