X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FSelectionDAG%2FScheduleDAG.cpp;h=5a2b4ede27807ac5156e4a0f924519c972fcda43;hb=02b6d25a2702d8857b82d333f290550e3c6ec4dc;hp=3be59952d1e3716e7743d58dfb4f17f2454dd067;hpb=917be6814e0a4e529d290be5d806a054bbbc4a27;p=oota-llvm.git diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp index 3be59952d1e..5a2b4ede278 100644 --- a/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp +++ b/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp @@ -232,39 +232,111 @@ void ScheduleDAG::ComputeLatency(SUnit *SU) { } } +/// CalculateDepths - compute depths using algorithms for the longest +/// paths in the DAG void ScheduleDAG::CalculateDepths() { - std::vector > 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 InDegree(DAGSize); + std::vector 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 > WorkList; - SUnit *Root = SUnitMap[DAG.getRoot().Val].front(); - WorkList.push_back(std::make_pair(Root, 0U)); + unsigned DAGSize = SUnits.size(); + std::vector InDegree(DAGSize); + std::vector 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); } } } @@ -361,21 +433,25 @@ void ScheduleDAG::EmitCopyFromReg(SDNode *Node, unsigned ResNo, 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) @@ -522,14 +598,14 @@ void ScheduleDAG::AddOperand(MachineInstr *MI, SDOperand Op, 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!"); } } @@ -602,8 +678,7 @@ void ScheduleDAG::EmitSubregNode(SDNode *Node, 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 { @@ -863,7 +938,8 @@ void ScheduleDAG::EmitNoop() { TII->insertNoop(*BB, BB->end()); } -void ScheduleDAG::EmitCrossRCCopy(SUnit *SU, DenseMap &VRBaseMap) { +void ScheduleDAG::EmitCrossRCCopy(SUnit *SU, + DenseMap &VRBaseMap) { for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); I != E; ++I) { if (I->isCtrl) continue; // ignore chain preds