}
}
+/// 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);
}
}
}
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 {
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