X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FSelectionDAG%2FScheduleDAG.cpp;h=5a2b4ede27807ac5156e4a0f924519c972fcda43;hb=02b6d25a2702d8857b82d333f290550e3c6ec4dc;hp=da79a991c243421bf0e59d0d4c3ba6cf7b7aab0e;hpb=42a77880a83b76112a1f42ce16b46dbde01cd0a8;p=oota-llvm.git diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp index da79a991c24..5a2b4ede278 100644 --- a/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp +++ b/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp @@ -24,10 +24,13 @@ #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()) { @@ -125,7 +128,7 @@ void ScheduleDAG::BuildSchedUnits() { 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); @@ -229,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); } } } @@ -358,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) @@ -519,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!"); } } @@ -599,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 { @@ -733,6 +811,7 @@ void ScheduleDAG::EmitNode(SDNode *Node, unsigned InstanceNo, delete MI; MI = NewMI; } + ++NumCommutes; } } @@ -859,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