X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FSelectionDAG%2FScheduleDAGSDNodes.cpp;h=2a6c853a1d1106174cfc21d749583626647229f4;hb=a0e9c6ff437124cd701828e2b380a2febb2996b9;hp=b22440daf16df5fbd3c2cd482626b751470f195d;hpb=aa7744d75fc1769ccc12c65c07bb5b82afa58330;p=oota-llvm.git diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.cpp index b22440daf16..2a6c853a1d1 100644 --- a/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.cpp +++ b/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.cpp @@ -12,7 +12,6 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "pre-RA-sched" #include "ScheduleDAGSDNodes.h" #include "InstrEmitter.h" #include "SDNodeDbgValue.h" @@ -30,24 +29,25 @@ #include "llvm/Support/raw_ostream.h" #include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetLowering.h" -#include "llvm/Target/TargetMachine.h" #include "llvm/Target/TargetRegisterInfo.h" #include "llvm/Target/TargetSubtargetInfo.h" using namespace llvm; +#define DEBUG_TYPE "pre-RA-sched" + STATISTIC(LoadsClustered, "Number of loads clustered together"); -// This allows latency based scheduler to notice high latency instructions -// without a target itinerary. The choise if number here has more to do with -// balancing scheduler heursitics than with the actual machine latency. +// This allows the latency-based scheduler to notice high latency instructions +// without a target itinerary. The choice of number here has more to do with +// balancing scheduler heuristics than with the actual machine latency. static cl::opt HighLatencyCycles( "sched-high-latency-cycles", cl::Hidden, cl::init(10), cl::desc("Roughly estimate the number of cycles that 'long latency'" "instructions take for targets with no itinerary")); ScheduleDAGSDNodes::ScheduleDAGSDNodes(MachineFunction &mf) - : ScheduleDAG(mf), BB(0), DAG(0), - InstrItins(mf.getTarget().getInstrItineraryData()) {} + : ScheduleDAG(mf), BB(nullptr), DAG(nullptr), + InstrItins(mf.getSubtarget().getInstrItineraryData()) {} /// Run - perform scheduling. /// @@ -67,12 +67,12 @@ void ScheduleDAGSDNodes::Run(SelectionDAG *dag, MachineBasicBlock *bb) { /// SUnit *ScheduleDAGSDNodes::newSUnit(SDNode *N) { #ifndef NDEBUG - const SUnit *Addr = 0; + const SUnit *Addr = nullptr; if (!SUnits.empty()) Addr = &SUnits[0]; #endif - SUnits.push_back(SUnit(N, (unsigned)SUnits.size())); - assert((Addr == 0 || Addr == &SUnits[0]) && + SUnits.emplace_back(N, (unsigned)SUnits.size()); + assert((Addr == nullptr || Addr == &SUnits[0]) && "SUnits std::vector reallocated on the fly!"); SUnits.back().OrigNode = &SUnits.back(); SUnit *SU = &SUnits.back(); @@ -119,31 +119,32 @@ static void CheckForPhysRegDependency(SDNode *Def, SDNode *User, unsigned Op, return; unsigned ResNo = User->getOperand(2).getResNo(); - if (Def->isMachineOpcode()) { + if (Def->getOpcode() == ISD::CopyFromReg && + cast(Def->getOperand(1))->getReg() == Reg) { + PhysReg = Reg; + } else if (Def->isMachineOpcode()) { const MCInstrDesc &II = TII->get(Def->getMachineOpcode()); if (ResNo >= II.getNumDefs() && - II.ImplicitDefs[ResNo - II.getNumDefs()] == Reg) { + II.ImplicitDefs[ResNo - II.getNumDefs()] == Reg) PhysReg = Reg; - const TargetRegisterClass *RC = - TRI->getMinimalPhysRegClass(Reg, Def->getValueType(ResNo)); - Cost = RC->getCopyCost(); - } + } + + if (PhysReg != 0) { + const TargetRegisterClass *RC = + TRI->getMinimalPhysRegClass(Reg, Def->getSimpleValueType(ResNo)); + Cost = RC->getCopyCost(); } } // Helper for AddGlue to clone node operands. -static void CloneNodeWithValues(SDNode *N, SelectionDAG *DAG, - SmallVectorImpl &VTs, +static void CloneNodeWithValues(SDNode *N, SelectionDAG *DAG, ArrayRef VTs, SDValue ExtraOper = SDValue()) { - SmallVector Ops; - for (unsigned I = 0, E = N->getNumOperands(); I != E; ++I) - Ops.push_back(N->getOperand(I)); - + SmallVector Ops(N->op_begin(), N->op_end()); if (ExtraOper.getNode()) Ops.push_back(ExtraOper); - SDVTList VTList = DAG->getVTList(&VTs[0], VTs.size()); - MachineSDNode::mmo_iterator Begin = 0, End = 0; + SDVTList VTList = DAG->getVTList(VTs); + MachineSDNode::mmo_iterator Begin = nullptr, End = nullptr; MachineSDNode *MN = dyn_cast(N); // Store memory references. @@ -152,7 +153,7 @@ static void CloneNodeWithValues(SDNode *N, SelectionDAG *DAG, End = MN->memoperands_end(); } - DAG->MorphNodeTo(N, N->getOpcode(), VTList, &Ops[0], Ops.size()); + DAG->MorphNodeTo(N, N->getOpcode(), VTList, Ops); // Reset the memory references if (MN) @@ -160,7 +161,6 @@ static void CloneNodeWithValues(SDNode *N, SelectionDAG *DAG, } static bool AddGlue(SDNode *N, SDValue Glue, bool AddGlue, SelectionDAG *DAG) { - SmallVector VTs; SDNode *GlueDestNode = Glue.getNode(); // Don't add glue from a node to itself. @@ -174,9 +174,7 @@ static bool AddGlue(SDNode *N, SDValue Glue, bool AddGlue, SelectionDAG *DAG) { // Don't add glue to something that already has a glue value. if (N->getValueType(N->getNumValues() - 1) == MVT::Glue) return false; - for (unsigned I = 0, E = N->getNumValues(); I != E; ++I) - VTs.push_back(N->getValueType(I)); - + SmallVector VTs(N->value_begin(), N->value_end()); if (AddGlue) VTs.push_back(MVT::Glue); @@ -192,11 +190,8 @@ static void RemoveUnusedGlue(SDNode *N, SelectionDAG *DAG) { !N->hasAnyUseOfValue(N->getNumValues() - 1)) && "expected an unused glue value"); - SmallVector VTs; - for (unsigned I = 0, E = N->getNumValues()-1; I != E; ++I) - VTs.push_back(N->getValueType(I)); - - CloneNodeWithValues(N, DAG, VTs); + CloneNodeWithValues(N, DAG, + makeArrayRef(N->value_begin(), N->getNumValues() - 1)); } /// ClusterNeighboringLoads - Force nearby loads together by "gluing" them. @@ -205,7 +200,7 @@ static void RemoveUnusedGlue(SDNode *N, SelectionDAG *DAG) { /// outputs to ensure they are scheduled together and in order. This /// optimization may benefit some targets by improving cache locality. void ScheduleDAGSDNodes::ClusterNeighboringLoads(SDNode *Node) { - SDNode *Chain = 0; + SDNode *Chain = nullptr; unsigned NumOps = Node->getNumOperands(); if (Node->getOperand(NumOps-1).getValueType() == MVT::Other) Chain = Node->getOperand(NumOps-1).getNode(); @@ -219,10 +214,13 @@ void ScheduleDAGSDNodes::ClusterNeighboringLoads(SDNode *Node) { DenseMap O2SMap; // Map from offset to SDNode. bool Cluster = false; SDNode *Base = Node; + // This algorithm requires a reasonably low use count before finding a match + // to avoid uselessly blowing up compile time in large blocks. + unsigned UseCount = 0; for (SDNode::use_iterator I = Chain->use_begin(), E = Chain->use_end(); - I != E; ++I) { + I != E && UseCount < 100; ++I, ++UseCount) { SDNode *User = *I; - if (User == Node || !Visited.insert(User)) + if (User == Node || !Visited.insert(User).second) continue; int64_t Offset1, Offset2; if (!TII->areLoadsFromSameBasePtr(Base, User, Offset1, Offset2) || @@ -237,6 +235,8 @@ void ScheduleDAGSDNodes::ClusterNeighboringLoads(SDNode *Node) { if (Offset2 < Offset1) Base = User; Cluster = true; + // Reset UseCount to allow more matches. + UseCount = 0; } if (!Cluster) @@ -266,7 +266,7 @@ void ScheduleDAGSDNodes::ClusterNeighboringLoads(SDNode *Node) { // Cluster loads by adding MVT::Glue outputs and inputs. This also // ensure they are scheduled in order of increasing addresses. SDNode *Lead = Loads[0]; - SDValue InGlue = SDValue(0, 0); + SDValue InGlue = SDValue(nullptr, 0); if (AddGlue(Lead, InGlue, true, DAG)) InGlue = SDValue(Lead, Lead->getNumValues() - 1); for (unsigned I = 1, E = Loads.size(); I != E; ++I) { @@ -289,9 +289,8 @@ void ScheduleDAGSDNodes::ClusterNeighboringLoads(SDNode *Node) { /// ClusterNodes - Cluster certain nodes which should be scheduled together. /// void ScheduleDAGSDNodes::ClusterNodes() { - for (SelectionDAG::allnodes_iterator NI = DAG->allnodes_begin(), - E = DAG->allnodes_end(); NI != E; ++NI) { - SDNode *Node = &*NI; + for (SDNode &NI : DAG->allnodes()) { + SDNode *Node = &NI; if (!Node || !Node->isMachineOpcode()) continue; @@ -308,9 +307,8 @@ void ScheduleDAGSDNodes::BuildSchedUnits() { // to their associated SUnits by holding SUnits table indices. A value // of -1 means the SDNode does not yet have an associated SUnit. unsigned NumNodes = 0; - for (SelectionDAG::allnodes_iterator NI = DAG->allnodes_begin(), - E = DAG->allnodes_end(); NI != E; ++NI) { - NI->setNodeId(-1); + for (SDNode &NI : DAG->allnodes()) { + NI.setNodeId(-1); ++NumNodes; } @@ -332,9 +330,9 @@ void ScheduleDAGSDNodes::BuildSchedUnits() { SDNode *NI = Worklist.pop_back_val(); // Add all operands to the worklist unless they've already been added. - for (unsigned i = 0, e = NI->getNumOperands(); i != e; ++i) - if (Visited.insert(NI->getOperand(i).getNode())) - Worklist.push_back(NI->getOperand(i).getNode()); + for (const SDValue &Op : NI->op_values()) + if (Visited.insert(Op.getNode()).second) + Worklist.push_back(Op.getNode()); if (isPassiveNode(NI)) // Leaf node, e.g. a TargetImmediate. continue; @@ -419,7 +417,7 @@ void ScheduleDAGSDNodes::BuildSchedUnits() { } void ScheduleDAGSDNodes::AddSchedEdges() { - const TargetSubtargetInfo &ST = TM.getSubtarget(); + const TargetSubtargetInfo &ST = MF.getSubtarget(); // Check to see if the scheduler cares about latencies. bool UnitLatencies = forceUnitLatencies(); @@ -541,6 +539,14 @@ void ScheduleDAGSDNodes::RegDefIter::InitNodeNumDefs() { NodeNumDefs = 0; return; } + if (POpc == TargetOpcode::PATCHPOINT && + Node->getValueType(0) == MVT::Other) { + // PATCHPOINT is defined to have one result, but it might really have none + // if we're not using CallingConv::AnyReg. Don't mistake the chain for a + // real definition. + NodeNumDefs = 0; + return; + } unsigned NRegDefs = SchedDAG->TII->get(Node->getMachineOpcode()).getNumDefs(); // Some instructions define regs that are not represented in the selection DAG // (e.g. unused flags). See tMOVi8. Make sure we don't access past NumValues. @@ -567,7 +573,7 @@ void ScheduleDAGSDNodes::RegDefIter::Advance() { return; // Found a normal regdef. } Node = Node->getGluedNode(); - if (Node == NULL) { + if (!Node) { return; // No values left to visit. } InitNodeNumDefs(); @@ -690,21 +696,11 @@ void ScheduleDAGSDNodes::VerifyScheduledSequence(bool isBottomUp) { } #endif // NDEBUG -namespace { - struct OrderSorter { - bool operator()(const std::pair &A, - const std::pair &B) { - return A.first < B.first; - } - }; -} - /// ProcessSDDbgValues - Process SDDbgValues associated with this node. -static void ProcessSDDbgValues(SDNode *N, SelectionDAG *DAG, - InstrEmitter &Emitter, - SmallVector, 32> &Orders, - DenseMap &VRBaseMap, - unsigned Order) { +static void +ProcessSDDbgValues(SDNode *N, SelectionDAG *DAG, InstrEmitter &Emitter, + SmallVectorImpl > &Orders, + DenseMap &VRBaseMap, unsigned Order) { if (!N->getHasDebugValue()) return; @@ -731,13 +727,13 @@ static void ProcessSDDbgValues(SDNode *N, SelectionDAG *DAG, // ProcessSourceNode - Process nodes with source order numbers. These are added // to a vector which EmitSchedule uses to determine how to insert dbg_value // instructions in the right order. -static void ProcessSourceNode(SDNode *N, SelectionDAG *DAG, - InstrEmitter &Emitter, - DenseMap &VRBaseMap, - SmallVector, 32> &Orders, - SmallSet &Seen) { - unsigned Order = DAG->GetOrdering(N); - if (!Order || !Seen.insert(Order)) { +static void +ProcessSourceNode(SDNode *N, SelectionDAG *DAG, InstrEmitter &Emitter, + DenseMap &VRBaseMap, + SmallVectorImpl > &Orders, + SmallSet &Seen) { + unsigned Order = N->getIROrder(); + if (!Order || !Seen.insert(Order).second) { // Process any valid SDDbgValues even if node does not have any order // assigned. ProcessSDDbgValues(N, DAG, Emitter, Orders, VRBaseMap, 0); @@ -745,13 +741,16 @@ static void ProcessSourceNode(SDNode *N, SelectionDAG *DAG, } MachineBasicBlock *BB = Emitter.getBlock(); - if (Emitter.getInsertPos() == BB->begin() || BB->back().isPHI()) { + if (Emitter.getInsertPos() == BB->begin() || BB->back().isPHI() || + // Fast-isel may have inserted some instructions, in which case the + // BB->back().isPHI() test will not fire when we want it to. + std::prev(Emitter.getInsertPos())->isPHI()) { // Did not insert any instruction. - Orders.push_back(std::make_pair(Order, (MachineInstr*)0)); + Orders.push_back(std::make_pair(Order, (MachineInstr*)nullptr)); return; } - Orders.push_back(std::make_pair(Order, prior(Emitter.getInsertPos()))); + Orders.push_back(std::make_pair(Order, std::prev(Emitter.getInsertPos()))); ProcessSDDbgValues(N, DAG, Emitter, Orders, VRBaseMap, Order); } @@ -858,7 +857,7 @@ EmitSchedule(MachineBasicBlock::iterator &InsertPos) { // Sort the source order instructions and use the order to insert debug // values. - std::sort(Orders.begin(), Orders.end(), OrderSorter()); + std::sort(Orders.begin(), Orders.end(), less_first()); SDDbgInfo::DbgIterator DI = DAG->DbgBegin(); SDDbgInfo::DbgIterator DE = DAG->DbgEnd(); @@ -883,7 +882,7 @@ EmitSchedule(MachineBasicBlock::iterator &InsertPos) { // Insert at the instruction, which may be in a different // block, if the block was split by a custom inserter. MachineBasicBlock::iterator Pos = MI; - MI->getParent()->insert(llvm::next(Pos), DbgMI); + MI->getParent()->insert(Pos, DbgMI); } } }