diff options
Diffstat (limited to 'lib/CodeGen/SelectionDAG')
| -rw-r--r-- | lib/CodeGen/SelectionDAG/CMakeLists.txt | 5 | ||||
| -rw-r--r-- | lib/CodeGen/SelectionDAG/LatencyPriorityQueue.cpp | 165 | ||||
| -rw-r--r-- | lib/CodeGen/SelectionDAG/LatencyPriorityQueue.h | 124 | ||||
| -rw-r--r-- | lib/CodeGen/SelectionDAG/ScheduleDAG.cpp | 522 | ||||
| -rw-r--r-- | lib/CodeGen/SelectionDAG/ScheduleDAGFast.cpp | 6 | ||||
| -rw-r--r-- | lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp | 12 | ||||
| -rw-r--r-- | lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp | 6 | ||||
| -rw-r--r-- | lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.cpp | 257 | ||||
| -rw-r--r-- | lib/CodeGen/SelectionDAG/ScheduleDAGSDNodesEmit.cpp (renamed from lib/CodeGen/SelectionDAG/ScheduleDAGEmit.cpp) | 92 | ||||
| -rw-r--r-- | lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp | 2 | ||||
| -rw-r--r-- | lib/CodeGen/SelectionDAG/SelectionDAGPrinter.cpp | 90 |
11 files changed, 301 insertions, 980 deletions
diff --git a/lib/CodeGen/SelectionDAG/CMakeLists.txt b/lib/CodeGen/SelectionDAG/CMakeLists.txt index a3654c2..186e3d1 100644 --- a/lib/CodeGen/SelectionDAG/CMakeLists.txt +++ b/lib/CodeGen/SelectionDAG/CMakeLists.txt @@ -2,15 +2,14 @@ add_llvm_library(LLVMSelectionDAG CallingConvLower.cpp DAGCombiner.cpp FastISel.cpp - LatencyPriorityQueue.cpp LegalizeDAG.cpp LegalizeFloatTypes.cpp LegalizeIntegerTypes.cpp LegalizeTypes.cpp LegalizeTypesGeneric.cpp LegalizeVectorTypes.cpp - ScheduleDAG.cpp - ScheduleDAGEmit.cpp + ScheduleDAGSDNodes.cpp + ScheduleDAGSDNodesEmit.cpp ScheduleDAGFast.cpp ScheduleDAGList.cpp ScheduleDAGRRList.cpp diff --git a/lib/CodeGen/SelectionDAG/LatencyPriorityQueue.cpp b/lib/CodeGen/SelectionDAG/LatencyPriorityQueue.cpp deleted file mode 100644 index ae73f20..0000000 --- a/lib/CodeGen/SelectionDAG/LatencyPriorityQueue.cpp +++ /dev/null @@ -1,165 +0,0 @@ -//===---- LatencyPriorityQueue.cpp - A latency-oriented priority queue ----===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file implements the LatencyPriorityQueue class, which is a -// SchedulingPriorityQueue that schedules using latency information to -// reduce the length of the critical path through the basic block. -// -//===----------------------------------------------------------------------===// - -#define DEBUG_TYPE "scheduler" -#include "LatencyPriorityQueue.h" -#include "llvm/Support/Debug.h" -using namespace llvm; - -bool latency_sort::operator()(const SUnit *LHS, const SUnit *RHS) const { - unsigned LHSNum = LHS->NodeNum; - unsigned RHSNum = RHS->NodeNum; - - // The most important heuristic is scheduling the critical path. - unsigned LHSLatency = PQ->getLatency(LHSNum); - unsigned RHSLatency = PQ->getLatency(RHSNum); - if (LHSLatency < RHSLatency) return true; - if (LHSLatency > RHSLatency) return false; - - // After that, if two nodes have identical latencies, look to see if one will - // unblock more other nodes than the other. - unsigned LHSBlocked = PQ->getNumSolelyBlockNodes(LHSNum); - unsigned RHSBlocked = PQ->getNumSolelyBlockNodes(RHSNum); - if (LHSBlocked < RHSBlocked) return true; - if (LHSBlocked > RHSBlocked) return false; - - // Finally, just to provide a stable ordering, use the node number as a - // deciding factor. - return LHSNum < RHSNum; -} - - -/// CalcNodePriority - Calculate the maximal path from the node to the exit. -/// -int LatencyPriorityQueue::CalcLatency(const SUnit &SU) { - int &Latency = Latencies[SU.NodeNum]; - if (Latency != -1) - return Latency; - - std::vector<const SUnit*> WorkList; - WorkList.push_back(&SU); - while (!WorkList.empty()) { - const SUnit *Cur = WorkList.back(); - bool AllDone = true; - int MaxSuccLatency = 0; - for (SUnit::const_succ_iterator I = Cur->Succs.begin(),E = Cur->Succs.end(); - I != E; ++I) { - int SuccLatency = Latencies[I->Dep->NodeNum]; - if (SuccLatency == -1) { - AllDone = false; - WorkList.push_back(I->Dep); - } else { - MaxSuccLatency = std::max(MaxSuccLatency, SuccLatency); - } - } - if (AllDone) { - Latencies[Cur->NodeNum] = MaxSuccLatency + Cur->Latency; - WorkList.pop_back(); - } - } - - return Latency; -} - -/// CalculatePriorities - Calculate priorities of all scheduling units. -void LatencyPriorityQueue::CalculatePriorities() { - Latencies.assign(SUnits->size(), -1); - NumNodesSolelyBlocking.assign(SUnits->size(), 0); - - // For each node, calculate the maximal path from the node to the exit. - std::vector<std::pair<const SUnit*, unsigned> > WorkList; - for (unsigned i = 0, e = SUnits->size(); i != e; ++i) { - const SUnit *SU = &(*SUnits)[i]; - if (SU->Succs.empty()) - WorkList.push_back(std::make_pair(SU, 0U)); - } - - while (!WorkList.empty()) { - const SUnit *SU = WorkList.back().first; - unsigned SuccLat = WorkList.back().second; - WorkList.pop_back(); - int &Latency = Latencies[SU->NodeNum]; - if (Latency == -1 || (SU->Latency + SuccLat) > (unsigned)Latency) { - Latency = SU->Latency + SuccLat; - for (SUnit::const_pred_iterator I = SU->Preds.begin(),E = SU->Preds.end(); - I != E; ++I) - WorkList.push_back(std::make_pair(I->Dep, Latency)); - } - } -} - -/// getSingleUnscheduledPred - If there is exactly one unscheduled predecessor -/// of SU, return it, otherwise return null. -SUnit *LatencyPriorityQueue::getSingleUnscheduledPred(SUnit *SU) { - SUnit *OnlyAvailablePred = 0; - for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); - I != E; ++I) { - SUnit &Pred = *I->Dep; - if (!Pred.isScheduled) { - // We found an available, but not scheduled, predecessor. If it's the - // only one we have found, keep track of it... otherwise give up. - if (OnlyAvailablePred && OnlyAvailablePred != &Pred) - return 0; - OnlyAvailablePred = &Pred; - } - } - - return OnlyAvailablePred; -} - -void LatencyPriorityQueue::push_impl(SUnit *SU) { - // Look at all of the successors of this node. Count the number of nodes that - // this node is the sole unscheduled node for. - unsigned NumNodesBlocking = 0; - for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); - I != E; ++I) - if (getSingleUnscheduledPred(I->Dep) == SU) - ++NumNodesBlocking; - NumNodesSolelyBlocking[SU->NodeNum] = NumNodesBlocking; - - Queue.push(SU); -} - - -// ScheduledNode - As nodes are scheduled, we look to see if there are any -// successor nodes that have a single unscheduled predecessor. If so, that -// single predecessor has a higher priority, since scheduling it will make -// the node available. -void LatencyPriorityQueue::ScheduledNode(SUnit *SU) { - for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); - I != E; ++I) - AdjustPriorityOfUnscheduledPreds(I->Dep); -} - -/// AdjustPriorityOfUnscheduledPreds - One of the predecessors of SU was just -/// scheduled. If SU is not itself available, then there is at least one -/// predecessor node that has not been scheduled yet. If SU has exactly ONE -/// unscheduled predecessor, we want to increase its priority: it getting -/// scheduled will make this node available, so it is better than some other -/// node of the same priority that will not make a node available. -void LatencyPriorityQueue::AdjustPriorityOfUnscheduledPreds(SUnit *SU) { - if (SU->isAvailable) return; // All preds scheduled. - - SUnit *OnlyAvailablePred = getSingleUnscheduledPred(SU); - if (OnlyAvailablePred == 0 || !OnlyAvailablePred->isAvailable) return; - - // Okay, we found a single predecessor that is available, but not scheduled. - // Since it is available, it must be in the priority queue. First remove it. - remove(OnlyAvailablePred); - - // Reinsert the node into the priority queue, which recomputes its - // NumNodesSolelyBlocking value. - push(OnlyAvailablePred); -} diff --git a/lib/CodeGen/SelectionDAG/LatencyPriorityQueue.h b/lib/CodeGen/SelectionDAG/LatencyPriorityQueue.h deleted file mode 100644 index 5b2b02b..0000000 --- a/lib/CodeGen/SelectionDAG/LatencyPriorityQueue.h +++ /dev/null @@ -1,124 +0,0 @@ -//===---- LatencyPriorityQueue.h - A latency-oriented priority queue ------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file declares the LatencyPriorityQueue class, which is a -// SchedulingPriorityQueue that schedules using latency information to -// reduce the length of the critical path through the basic block. -// -//===----------------------------------------------------------------------===// - -#ifndef LATENCY_PRIORITY_QUEUE_H -#define LATENCY_PRIORITY_QUEUE_H - -#include "llvm/CodeGen/ScheduleDAG.h" -#include "llvm/ADT/PriorityQueue.h" - -namespace llvm { - class LatencyPriorityQueue; - - /// Sorting functions for the Available queue. - struct latency_sort : public std::binary_function<SUnit*, SUnit*, bool> { - LatencyPriorityQueue *PQ; - explicit latency_sort(LatencyPriorityQueue *pq) : PQ(pq) {} - - bool operator()(const SUnit* left, const SUnit* right) const; - }; - - class LatencyPriorityQueue : public SchedulingPriorityQueue { - // SUnits - The SUnits for the current graph. - std::vector<SUnit> *SUnits; - - // Latencies - The latency (max of latency from this node to the bb exit) - // for each node. - std::vector<int> Latencies; - - /// NumNodesSolelyBlocking - This vector contains, for every node in the - /// Queue, the number of nodes that the node is the sole unscheduled - /// predecessor for. This is used as a tie-breaker heuristic for better - /// mobility. - std::vector<unsigned> NumNodesSolelyBlocking; - - PriorityQueue<SUnit*, std::vector<SUnit*>, latency_sort> Queue; - public: - LatencyPriorityQueue() : Queue(latency_sort(this)) { - } - - void initNodes(std::vector<SUnit> &sunits) { - SUnits = &sunits; - // Calculate node priorities. - CalculatePriorities(); - } - - void addNode(const SUnit *SU) { - Latencies.resize(SUnits->size(), -1); - NumNodesSolelyBlocking.resize(SUnits->size(), 0); - CalcLatency(*SU); - } - - void updateNode(const SUnit *SU) { - Latencies[SU->NodeNum] = -1; - CalcLatency(*SU); - } - - void releaseState() { - SUnits = 0; - Latencies.clear(); - } - - unsigned getLatency(unsigned NodeNum) const { - assert(NodeNum < Latencies.size()); - return Latencies[NodeNum]; - } - - unsigned getNumSolelyBlockNodes(unsigned NodeNum) const { - assert(NodeNum < NumNodesSolelyBlocking.size()); - return NumNodesSolelyBlocking[NodeNum]; - } - - unsigned size() const { return Queue.size(); } - - bool empty() const { return Queue.empty(); } - - virtual void push(SUnit *U) { - push_impl(U); - } - void push_impl(SUnit *U); - - void push_all(const std::vector<SUnit *> &Nodes) { - for (unsigned i = 0, e = Nodes.size(); i != e; ++i) - push_impl(Nodes[i]); - } - - SUnit *pop() { - if (empty()) return NULL; - SUnit *V = Queue.top(); - Queue.pop(); - return V; - } - - void remove(SUnit *SU) { - assert(!Queue.empty() && "Not in queue!"); - Queue.erase_one(SU); - } - - // ScheduledNode - As nodes are scheduled, we look to see if there are any - // successor nodes that have a single unscheduled predecessor. If so, that - // single predecessor has a higher priority, since scheduling it will make - // the node available. - void ScheduledNode(SUnit *Node); - - private: - void CalculatePriorities(); - int CalcLatency(const SUnit &SU); - void AdjustPriorityOfUnscheduledPreds(SUnit *SU); - SUnit *getSingleUnscheduledPred(SUnit *SU); - }; -} - -#endif diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp deleted file mode 100644 index c2e2175..0000000 --- a/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp +++ /dev/null @@ -1,522 +0,0 @@ -//===---- ScheduleDAG.cpp - Implement the ScheduleDAG class ---------------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This implements the ScheduleDAG class, which is a base class used by -// scheduling implementation classes. -// -//===----------------------------------------------------------------------===// - -#define DEBUG_TYPE "pre-RA-sched" -#include "llvm/CodeGen/ScheduleDAG.h" -#include "llvm/Target/TargetMachine.h" -#include "llvm/Target/TargetInstrInfo.h" -#include "llvm/Target/TargetRegisterInfo.h" -#include "llvm/Support/Debug.h" -#include "llvm/Support/raw_ostream.h" -using namespace llvm; - -ScheduleDAG::ScheduleDAG(SelectionDAG *dag, MachineBasicBlock *bb, - const TargetMachine &tm) - : DAG(dag), BB(bb), TM(tm), MRI(BB->getParent()->getRegInfo()) { - TII = TM.getInstrInfo(); - MF = BB->getParent(); - TRI = TM.getRegisterInfo(); - TLI = TM.getTargetLowering(); - ConstPool = MF->getConstantPool(); -} - -/// CheckForPhysRegDependency - Check if the dependency between def and use of -/// a specified operand is a physical register dependency. If so, returns the -/// register and the cost of copying the register. -static void CheckForPhysRegDependency(SDNode *Def, SDNode *User, unsigned Op, - const TargetRegisterInfo *TRI, - const TargetInstrInfo *TII, - unsigned &PhysReg, int &Cost) { - if (Op != 2 || User->getOpcode() != ISD::CopyToReg) - return; - - unsigned Reg = cast<RegisterSDNode>(User->getOperand(1))->getReg(); - if (TargetRegisterInfo::isVirtualRegister(Reg)) - return; - - unsigned ResNo = User->getOperand(2).getResNo(); - if (Def->isMachineOpcode()) { - const TargetInstrDesc &II = TII->get(Def->getMachineOpcode()); - if (ResNo >= II.getNumDefs() && - II.ImplicitDefs[ResNo - II.getNumDefs()] == Reg) { - PhysReg = Reg; - const TargetRegisterClass *RC = - TRI->getPhysicalRegisterRegClass(Reg, Def->getValueType(ResNo)); - Cost = RC->getCopyCost(); - } - } -} - -SUnit *ScheduleDAG::Clone(SUnit *Old) { - SUnit *SU = NewSUnit(Old->getNode()); - SU->OrigNode = Old->OrigNode; - SU->Latency = Old->Latency; - SU->isTwoAddress = Old->isTwoAddress; - SU->isCommutable = Old->isCommutable; - SU->hasPhysRegDefs = Old->hasPhysRegDefs; - return SU; -} - - -/// BuildSchedUnits - Build SUnits from the selection dag that we are input. -/// This SUnit graph is similar to the SelectionDAG, but represents flagged -/// together nodes with a single SUnit. -void ScheduleDAG::BuildSchedUnits() { - // For post-regalloc scheduling, build the SUnits from the MachineInstrs - // in the MachineBasicBlock. - if (!DAG) { - BuildSchedUnitsFromMBB(); - return; - } - - // Reserve entries in the vector for each of the SUnits we are creating. This - // ensure that reallocation of the vector won't happen, so SUnit*'s won't get - // invalidated. - SUnits.reserve(DAG->allnodes_size()); - - // During scheduling, the NodeId field of SDNode is used to map SDNodes - // to their associated SUnits by holding SUnits table indices. A value - // of -1 means the SDNode does not yet have an associated SUnit. - for (SelectionDAG::allnodes_iterator NI = DAG->allnodes_begin(), - E = DAG->allnodes_end(); NI != E; ++NI) - NI->setNodeId(-1); - - for (SelectionDAG::allnodes_iterator NI = DAG->allnodes_begin(), - E = DAG->allnodes_end(); NI != E; ++NI) { - if (isPassiveNode(NI)) // Leaf node, e.g. a TargetImmediate. - continue; - - // If this node has already been processed, stop now. - if (NI->getNodeId() != -1) continue; - - SUnit *NodeSUnit = NewSUnit(NI); - - // See if anything is flagged to this node, if so, add them to flagged - // nodes. Nodes can have at most one flag input and one flag output. Flags - // are required the be the last operand and result of a node. - - // Scan up to find flagged preds. - SDNode *N = NI; - if (N->getNumOperands() && - N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Flag) { - do { - N = N->getOperand(N->getNumOperands()-1).getNode(); - assert(N->getNodeId() == -1 && "Node already inserted!"); - N->setNodeId(NodeSUnit->NodeNum); - } while (N->getNumOperands() && - N->getOperand(N->getNumOperands()-1).getValueType()== MVT::Flag); - } - - // Scan down to find any flagged succs. - N = NI; - while (N->getValueType(N->getNumValues()-1) == MVT::Flag) { - SDValue FlagVal(N, N->getNumValues()-1); - - // There are either zero or one users of the Flag result. - bool HasFlagUse = false; - for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end(); - UI != E; ++UI) - if (FlagVal.isOperandOf(*UI)) { - HasFlagUse = true; - assert(N->getNodeId() == -1 && "Node already inserted!"); - N->setNodeId(NodeSUnit->NodeNum); - N = *UI; - break; - } - if (!HasFlagUse) break; - } - - // If there are flag operands involved, N is now the bottom-most node - // of the sequence of nodes that are flagged together. - // Update the SUnit. - NodeSUnit->setNode(N); - assert(N->getNodeId() == -1 && "Node already inserted!"); - N->setNodeId(NodeSUnit->NodeNum); - - ComputeLatency(NodeSUnit); - } - - // Pass 2: add the preds, succs, etc. - for (unsigned su = 0, e = SUnits.size(); su != e; ++su) { - SUnit *SU = &SUnits[su]; - SDNode *MainNode = SU->getNode(); - - if (MainNode->isMachineOpcode()) { - unsigned Opc = MainNode->getMachineOpcode(); - const TargetInstrDesc &TID = TII->get(Opc); - for (unsigned i = 0; i != TID.getNumOperands(); ++i) { - if (TID.getOperandConstraint(i, TOI::TIED_TO) != -1) { - SU->isTwoAddress = true; - break; - } - } - if (TID.isCommutable()) - SU->isCommutable = true; - } - - // Find all predecessors and successors of the group. - for (SDNode *N = SU->getNode(); N; N = N->getFlaggedNode()) { - if (N->isMachineOpcode() && - TII->get(N->getMachineOpcode()).getImplicitDefs() && - CountResults(N) > TII->get(N->getMachineOpcode()).getNumDefs()) - SU->hasPhysRegDefs = true; - - for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { - SDNode *OpN = N->getOperand(i).getNode(); - if (isPassiveNode(OpN)) continue; // Not scheduled. - SUnit *OpSU = &SUnits[OpN->getNodeId()]; - assert(OpSU && "Node has no SUnit!"); - if (OpSU == SU) continue; // In the same group. - - MVT OpVT = N->getOperand(i).getValueType(); - assert(OpVT != MVT::Flag && "Flagged nodes should be in same sunit!"); - bool isChain = OpVT == MVT::Other; - - unsigned PhysReg = 0; - int Cost = 1; - // Determine if this is a physical register dependency. - CheckForPhysRegDependency(OpN, N, i, TRI, TII, PhysReg, Cost); - SU->addPred(OpSU, isChain, false, PhysReg, Cost); - } - } - } -} - -void ScheduleDAG::BuildSchedUnitsFromMBB() { - SUnits.clear(); - SUnits.reserve(BB->size()); - - std::vector<SUnit *> PendingLoads; - SUnit *Terminator = 0; - SUnit *Chain = 0; - SUnit *Defs[TargetRegisterInfo::FirstVirtualRegister] = {}; - std::vector<SUnit *> Uses[TargetRegisterInfo::FirstVirtualRegister] = {}; - int Cost = 1; // FIXME - - for (MachineBasicBlock::iterator MII = BB->end(), MIE = BB->begin(); - MII != MIE; --MII) { - MachineInstr *MI = prior(MII); - SUnit *SU = NewSUnit(MI); - - for (unsigned j = 0, n = MI->getNumOperands(); j != n; ++j) { - const MachineOperand &MO = MI->getOperand(j); - if (!MO.isReg()) continue; - unsigned Reg = MO.getReg(); - if (Reg == 0) continue; - - assert(TRI->isPhysicalRegister(Reg) && "Virtual register encountered!"); - std::vector<SUnit *> &UseList = Uses[Reg]; - SUnit *&Def = Defs[Reg]; - // Optionally add output and anti dependences - if (Def && Def != SU) - Def->addPred(SU, /*isCtrl=*/true, /*isSpecial=*/false, - /*PhyReg=*/Reg, Cost); - for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { - SUnit *&Def = Defs[*Alias]; - if (Def && Def != SU) - Def->addPred(SU, /*isCtrl=*/true, /*isSpecial=*/false, - /*PhyReg=*/*Alias, Cost); - } - - if (MO.isDef()) { - // Add any data dependencies. - for (unsigned i = 0, e = UseList.size(); i != e; ++i) - if (UseList[i] != SU) - UseList[i]->addPred(SU, /*isCtrl=*/false, /*isSpecial=*/false, - /*PhysReg=*/Reg, Cost); - for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { - std::vector<SUnit *> &UseList = Uses[*Alias]; - for (unsigned i = 0, e = UseList.size(); i != e; ++i) - if (UseList[i] != SU) - UseList[i]->addPred(SU, /*isCtrl=*/false, /*isSpecial=*/false, - /*PhysReg=*/*Alias, Cost); - } - - UseList.clear(); - Def = SU; - } else { - UseList.push_back(SU); - } - } - bool False = false; - bool True = true; - if (!MI->isSafeToMove(TII, False)) { - if (Chain) - Chain->addPred(SU, /*isCtrl=*/false, /*isSpecial=*/false); - for (unsigned k = 0, m = PendingLoads.size(); k != m; ++k) - PendingLoads[k]->addPred(SU, /*isCtrl=*/false, /*isSpecial=*/false); - PendingLoads.clear(); - Chain = SU; - } else if (!MI->isSafeToMove(TII, True)) { - if (Chain) - Chain->addPred(SU, /*isCtrl=*/false, /*isSpecial=*/false); - PendingLoads.push_back(SU); - } - if (Terminator && SU->Succs.empty()) - Terminator->addPred(SU, /*isCtrl=*/false, /*isSpecial=*/false); - if (MI->getDesc().isTerminator()) - Terminator = SU; - } -} - -void ScheduleDAG::ComputeLatency(SUnit *SU) { - const InstrItineraryData &InstrItins = TM.getInstrItineraryData(); - - // Compute the latency for the node. We use the sum of the latencies for - // all nodes flagged together into this SUnit. - if (InstrItins.isEmpty()) { - // No latency information. - SU->Latency = 1; - return; - } - - SU->Latency = 0; - for (SDNode *N = SU->getNode(); N; N = N->getFlaggedNode()) { - if (N->isMachineOpcode()) { - unsigned SchedClass = TII->get(N->getMachineOpcode()).getSchedClass(); - const InstrStage *S = InstrItins.begin(SchedClass); - const InstrStage *E = InstrItins.end(SchedClass); - for (; S != E; ++S) - SU->Latency += S->Cycles; - } - } -} - -/// CalculateDepths - compute depths using algorithms for the longest -/// paths in the DAG -void ScheduleDAG::CalculateDepths() { - unsigned DAGSize = SUnits.size(); - std::vector<SUnit*> WorkList; - WorkList.reserve(DAGSize); - - // Initialize the data structures - for (unsigned i = 0, e = DAGSize; i != e; ++i) { - SUnit *SU = &SUnits[i]; - unsigned Degree = SU->Preds.size(); - // Temporarily use the Depth field as scratch space for the degree count. - SU->Depth = Degree; - - // 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(); - WorkList.pop_back(); - unsigned SUDepth = 0; - - // 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; - } - } - - SU->Depth = SUDepth; - - // Update degrees 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 (!--SU->Depth) - // 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() { - unsigned DAGSize = SUnits.size(); - std::vector<SUnit*> WorkList; - WorkList.reserve(DAGSize); - - // Initialize the data structures - for (unsigned i = 0, e = DAGSize; i != e; ++i) { - SUnit *SU = &SUnits[i]; - unsigned Degree = SU->Succs.size(); - // Temporarily use the Height field as scratch space for the degree count. - SU->Height = Degree; - - // 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(); - WorkList.pop_back(); - unsigned SUHeight = 0; - - // 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; - } - } - - SU->Height = SUHeight; - - // Update degrees 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 (!--SU->Height) - // If all dependencies of the node are processed already, - // then the longest path for the node can be computed now - WorkList.push_back(SU); - } - } -} - -/// CountResults - The results of target nodes have register or immediate -/// operands first, then an optional chain, and optional flag operands (which do -/// not go into the resulting MachineInstr). -unsigned ScheduleDAG::CountResults(SDNode *Node) { - unsigned N = Node->getNumValues(); - while (N && Node->getValueType(N - 1) == MVT::Flag) - --N; - if (N && Node->getValueType(N - 1) == MVT::Other) - --N; // Skip over chain result. - return N; -} - -/// CountOperands - The inputs to target nodes have any actual inputs first, -/// followed by special operands that describe memory references, then an -/// optional chain operand, then an optional flag operand. Compute the number -/// of actual operands that will go into the resulting MachineInstr. -unsigned ScheduleDAG::CountOperands(SDNode *Node) { - unsigned N = ComputeMemOperandsEnd(Node); - while (N && isa<MemOperandSDNode>(Node->getOperand(N - 1).getNode())) - --N; // Ignore MEMOPERAND nodes - return N; -} - -/// 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; - if (N && Node->getOperand(N - 1).getValueType() == MVT::Other) - --N; // Ignore chain if it exists. - return N; -} - - -/// dump - dump the schedule. -void ScheduleDAG::dumpSchedule() const { - for (unsigned i = 0, e = Sequence.size(); i != e; i++) { - if (SUnit *SU = Sequence[i]) - SU->dump(this); - else - cerr << "**** NOOP ****\n"; - } -} - - -/// Run - perform scheduling. -/// -void ScheduleDAG::Run() { - Schedule(); - - DOUT << "*** Final schedule ***\n"; - DEBUG(dumpSchedule()); - DOUT << "\n"; -} - -/// SUnit - Scheduling unit. It's an wrapper around either a single SDNode or -/// a group of nodes flagged together. -void SUnit::print(raw_ostream &O, const ScheduleDAG *G) const { - O << "SU(" << NodeNum << "): "; - if (getNode()) { - SmallVector<SDNode *, 4> FlaggedNodes; - for (SDNode *N = getNode(); N; N = N->getFlaggedNode()) - FlaggedNodes.push_back(N); - while (!FlaggedNodes.empty()) { - O << " "; - FlaggedNodes.back()->print(O, G->DAG); - O << "\n"; - FlaggedNodes.pop_back(); - } - } else { - O << "CROSS RC COPY\n"; - } -} - -void SUnit::dump(const ScheduleDAG *G) const { - print(errs(), G); -} - -void SUnit::dumpAll(const ScheduleDAG *G) const { - dump(G); - - cerr << " # preds left : " << NumPredsLeft << "\n"; - cerr << " # succs left : " << NumSuccsLeft << "\n"; - cerr << " Latency : " << Latency << "\n"; - cerr << " Depth : " << Depth << "\n"; - cerr << " Height : " << Height << "\n"; - - if (Preds.size() != 0) { - cerr << " Predecessors:\n"; - for (SUnit::const_succ_iterator I = Preds.begin(), E = Preds.end(); - I != E; ++I) { - if (I->isCtrl) - cerr << " ch #"; - else - cerr << " val #"; - cerr << I->Dep << " - SU(" << I->Dep->NodeNum << ")"; - if (I->isSpecial) - cerr << " *"; - cerr << "\n"; - } - } - if (Succs.size() != 0) { - cerr << " Successors:\n"; - for (SUnit::const_succ_iterator I = Succs.begin(), E = Succs.end(); - I != E; ++I) { - if (I->isCtrl) - cerr << " ch #"; - else - cerr << " val #"; - cerr << I->Dep << " - SU(" << I->Dep->NodeNum << ")"; - if (I->isSpecial) - cerr << " *"; - cerr << "\n"; - } - } - cerr << "\n"; -} diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGFast.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGFast.cpp index 0af0358..8f3198e 100644 --- a/lib/CodeGen/SelectionDAG/ScheduleDAGFast.cpp +++ b/lib/CodeGen/SelectionDAG/ScheduleDAGFast.cpp @@ -12,7 +12,7 @@ //===----------------------------------------------------------------------===// #define DEBUG_TYPE "pre-RA-sched" -#include "llvm/CodeGen/ScheduleDAG.h" +#include "llvm/CodeGen/ScheduleDAGSDNodes.h" #include "llvm/CodeGen/SchedulerRegistry.h" #include "llvm/Target/TargetRegisterInfo.h" #include "llvm/Target/TargetData.h" @@ -58,7 +58,7 @@ namespace { //===----------------------------------------------------------------------===// /// ScheduleDAGFast - The actual "fast" list scheduler implementation. /// -class VISIBILITY_HIDDEN ScheduleDAGFast : public ScheduleDAG { +class VISIBILITY_HIDDEN ScheduleDAGFast : public ScheduleDAGSDNodes { private: /// AvailableQueue - The priority queue to use for the available SUnits. FastPriorityQueue AvailableQueue; @@ -73,7 +73,7 @@ private: public: ScheduleDAGFast(SelectionDAG *dag, MachineBasicBlock *bb, const TargetMachine &tm) - : ScheduleDAG(dag, bb, tm) {} + : ScheduleDAGSDNodes(dag, bb, tm) {} void Schedule(); diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp index c2c9110..e1a24a1 100644 --- a/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp +++ b/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp @@ -19,7 +19,8 @@ //===----------------------------------------------------------------------===// #define DEBUG_TYPE "pre-RA-sched" -#include "llvm/CodeGen/ScheduleDAG.h" +#include "llvm/CodeGen/LatencyPriorityQueue.h" +#include "llvm/CodeGen/ScheduleDAGSDNodes.h" #include "llvm/CodeGen/SchedulerRegistry.h" #include "llvm/CodeGen/SelectionDAGISel.h" #include "llvm/Target/TargetRegisterInfo.h" @@ -30,7 +31,6 @@ #include "llvm/Support/Compiler.h" #include "llvm/ADT/PriorityQueue.h" #include "llvm/ADT/Statistic.h" -#include "LatencyPriorityQueue.h" #include <climits> using namespace llvm; @@ -46,7 +46,7 @@ namespace { /// ScheduleDAGList - The actual list scheduler implementation. This supports /// top-down scheduling. /// -class VISIBILITY_HIDDEN ScheduleDAGList : public ScheduleDAG { +class VISIBILITY_HIDDEN ScheduleDAGList : public ScheduleDAGSDNodes { private: /// AvailableQueue - The priority queue to use for the available SUnits. /// @@ -66,7 +66,7 @@ public: const TargetMachine &tm, SchedulingPriorityQueue *availqueue, HazardRecognizer *HR) - : ScheduleDAG(dag, bb, tm), + : ScheduleDAGSDNodes(dag, bb, tm), AvailableQueue(availqueue), HazardRec(HR) { } @@ -212,13 +212,13 @@ void ScheduleDAGList::ListScheduleTopDown() { if (!N) break; FoundNode = N; } - + HazardRecognizer::HazardType HT = HazardRec->getHazardType(FoundNode); if (HT == HazardRecognizer::NoHazard) { FoundSUnit = CurSUnit; break; } - + // Remember if this is a noop hazard. HasNoopHazards |= HT == HazardRecognizer::NoopHazard; diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp index 7c3f6bb..45a1ca0 100644 --- a/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp +++ b/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp @@ -16,7 +16,7 @@ //===----------------------------------------------------------------------===// #define DEBUG_TYPE "pre-RA-sched" -#include "llvm/CodeGen/ScheduleDAG.h" +#include "llvm/CodeGen/ScheduleDAGSDNodes.h" #include "llvm/CodeGen/SchedulerRegistry.h" #include "llvm/Target/TargetRegisterInfo.h" #include "llvm/Target/TargetData.h" @@ -53,7 +53,7 @@ namespace { /// ScheduleDAGRRList - The actual register reduction list scheduler /// implementation. This supports both top-down and bottom-up scheduling. /// -class VISIBILITY_HIDDEN ScheduleDAGRRList : public ScheduleDAG { +class VISIBILITY_HIDDEN ScheduleDAGRRList : public ScheduleDAGSDNodes { private: /// isBottomUp - This is true if the scheduling problem is bottom-up, false if /// it is top-down. @@ -77,7 +77,7 @@ public: ScheduleDAGRRList(SelectionDAG *dag, MachineBasicBlock *bb, const TargetMachine &tm, bool isbottomup, bool f, SchedulingPriorityQueue *availqueue) - : ScheduleDAG(dag, bb, tm), isBottomUp(isbottomup), Fast(f), + : ScheduleDAGSDNodes(dag, bb, tm), isBottomUp(isbottomup), Fast(f), AvailableQueue(availqueue) { } diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.cpp new file mode 100644 index 0000000..9d32d9a --- /dev/null +++ b/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.cpp @@ -0,0 +1,257 @@ +//===--- ScheduleDAGSDNodes.cpp - Implement the ScheduleDAGSDNodes class --===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This implements the ScheduleDAG class, which is a base class used by +// scheduling implementation classes. +// +//===----------------------------------------------------------------------===// + +#define DEBUG_TYPE "pre-RA-sched" +#include "llvm/CodeGen/ScheduleDAGSDNodes.h" +#include "llvm/CodeGen/SelectionDAG.h" +#include "llvm/Target/TargetMachine.h" +#include "llvm/Target/TargetInstrInfo.h" +#include "llvm/Target/TargetRegisterInfo.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" +using namespace llvm; + +ScheduleDAGSDNodes::ScheduleDAGSDNodes(SelectionDAG *dag, MachineBasicBlock *bb, + const TargetMachine &tm) + : ScheduleDAG(dag, bb, tm) { +} + +SUnit *ScheduleDAGSDNodes::Clone(SUnit *Old) { + SUnit *SU = NewSUnit(Old->getNode()); + SU->OrigNode = Old->OrigNode; + SU->Latency = Old->Latency; + SU->isTwoAddress = Old->isTwoAddress; + SU->isCommutable = Old->isCommutable; + SU->hasPhysRegDefs = Old->hasPhysRegDefs; + return SU; +} + +/// CheckForPhysRegDependency - Check if the dependency between def and use of +/// a specified operand is a physical register dependency. If so, returns the +/// register and the cost of copying the register. +static void CheckForPhysRegDependency(SDNode *Def, SDNode *User, unsigned Op, + const TargetRegisterInfo *TRI, + const TargetInstrInfo *TII, + unsigned &PhysReg, int &Cost) { + if (Op != 2 || User->getOpcode() != ISD::CopyToReg) + return; + + unsigned Reg = cast<RegisterSDNode>(User->getOperand(1))->getReg(); + if (TargetRegisterInfo::isVirtualRegister(Reg)) + return; + + unsigned ResNo = User->getOperand(2).getResNo(); + if (Def->isMachineOpcode()) { + const TargetInstrDesc &II = TII->get(Def->getMachineOpcode()); + if (ResNo >= II.getNumDefs() && + II.ImplicitDefs[ResNo - II.getNumDefs()] == Reg) { + PhysReg = Reg; + const TargetRegisterClass *RC = + TRI->getPhysicalRegisterRegClass(Reg, Def->getValueType(ResNo)); + Cost = RC->getCopyCost(); + } + } +} + +/// BuildSchedUnits - Build SUnits from the selection dag that we are input. +/// This SUnit graph is similar to the SelectionDAG, but represents flagged +/// together nodes with a single SUnit. +void ScheduleDAGSDNodes::BuildSchedUnits() { + // Reserve entries in the vector for each of the SUnits we are creating. This + // ensure that reallocation of the vector won't happen, so SUnit*'s won't get + // invalidated. + SUnits.reserve(DAG->allnodes_size()); + + // During scheduling, the NodeId field of SDNode is used to map SDNodes + // to their associated SUnits by holding SUnits table indices. A value + // of -1 means the SDNode does not yet have an associated SUnit. + for (SelectionDAG::allnodes_iterator NI = DAG->allnodes_begin(), + E = DAG->allnodes_end(); NI != E; ++NI) + NI->setNodeId(-1); + + for (SelectionDAG::allnodes_iterator NI = DAG->allnodes_begin(), + E = DAG->allnodes_end(); NI != E; ++NI) { + if (isPassiveNode(NI)) // Leaf node, e.g. a TargetImmediate. + continue; + + // If this node has already been processed, stop now. + if (NI->getNodeId() != -1) continue; + + SUnit *NodeSUnit = NewSUnit(NI); + + // See if anything is flagged to this node, if so, add them to flagged + // nodes. Nodes can have at most one flag input and one flag output. Flags + // are required the be the last operand and result of a node. + + // Scan up to find flagged preds. + SDNode *N = NI; + if (N->getNumOperands() && + N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Flag) { + do { + N = N->getOperand(N->getNumOperands()-1).getNode(); + assert(N->getNodeId() == -1 && "Node already inserted!"); + N->setNodeId(NodeSUnit->NodeNum); + } while (N->getNumOperands() && + N->getOperand(N->getNumOperands()-1).getValueType()== MVT::Flag); + } + + // Scan down to find any flagged succs. + N = NI; + while (N->getValueType(N->getNumValues()-1) == MVT::Flag) { + SDValue FlagVal(N, N->getNumValues()-1); + + // There are either zero or one users of the Flag result. + bool HasFlagUse = false; + for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end(); + UI != E; ++UI) + if (FlagVal.isOperandOf(*UI)) { + HasFlagUse = true; + assert(N->getNodeId() == -1 && "Node already inserted!"); + N->setNodeId(NodeSUnit->NodeNum); + N = *UI; + break; + } + if (!HasFlagUse) break; + } + + // If there are flag operands involved, N is now the bottom-most node + // of the sequence of nodes that are flagged together. + // Update the SUnit. + NodeSUnit->setNode(N); + assert(N->getNodeId() == -1 && "Node already inserted!"); + N->setNodeId(NodeSUnit->NodeNum); + + ComputeLatency(NodeSUnit); + } + + // Pass 2: add the preds, succs, etc. + for (unsigned su = 0, e = SUnits.size(); su != e; ++su) { + SUnit *SU = &SUnits[su]; + SDNode *MainNode = SU->getNode(); + + if (MainNode->isMachineOpcode()) { + unsigned Opc = MainNode->getMachineOpcode(); + const TargetInstrDesc &TID = TII->get(Opc); + for (unsigned i = 0; i != TID.getNumOperands(); ++i) { + if (TID.getOperandConstraint(i, TOI::TIED_TO) != -1) { + SU->isTwoAddress = true; + break; + } + } + if (TID.isCommutable()) + SU->isCommutable = true; + } + + // Find all predecessors and successors of the group. + for (SDNode *N = SU->getNode(); N; N = N->getFlaggedNode()) { + if (N->isMachineOpcode() && + TII->get(N->getMachineOpcode()).getImplicitDefs() && + CountResults(N) > TII->get(N->getMachineOpcode()).getNumDefs()) + SU->hasPhysRegDefs = true; + + for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { + SDNode *OpN = N->getOperand(i).getNode(); + if (isPassiveNode(OpN)) continue; // Not scheduled. + SUnit *OpSU = &SUnits[OpN->getNodeId()]; + assert(OpSU && "Node has no SUnit!"); + if (OpSU == SU) continue; // In the same group. + + MVT OpVT = N->getOperand(i).getValueType(); + assert(OpVT != MVT::Flag && "Flagged nodes should be in same sunit!"); + bool isChain = OpVT == MVT::Other; + + unsigned PhysReg = 0; + int Cost = 1; + // Determine if this is a physical register dependency. + CheckForPhysRegDependency(OpN, N, i, TRI, TII, PhysReg, Cost); + SU->addPred(OpSU, isChain, false, PhysReg, Cost); + } + } + } +} + +void ScheduleDAGSDNodes::ComputeLatency(SUnit *SU) { + const InstrItineraryData &InstrItins = TM.getInstrItineraryData(); + + // Compute the latency for the node. We use the sum of the latencies for + // all nodes flagged together into this SUnit. + if (InstrItins.isEmpty()) { + // No latency information. + SU->Latency = 1; + return; + } + + SU->Latency = 0; + for (SDNode *N = SU->getNode(); N; N = N->getFlaggedNode()) { + if (N->isMachineOpcode()) { + unsigned SchedClass = TII->get(N->getMachineOpcode()).getSchedClass(); + const InstrStage *S = InstrItins.begin(SchedClass); + const InstrStage *E = InstrItins.end(SchedClass); + for (; S != E; ++S) + SU->Latency += S->Cycles; + } + } +} + +/// CountResults - The results of target nodes have register or immediate +/// operands first, then an optional chain, and optional flag operands (which do +/// not go into the resulting MachineInstr). +unsigned ScheduleDAGSDNodes::CountResults(SDNode *Node) { + unsigned N = Node->getNumValues(); + while (N && Node->getValueType(N - 1) == MVT::Flag) + --N; + if (N && Node->getValueType(N - 1) == MVT::Other) + --N; // Skip over chain result. + return N; +} + +/// CountOperands - The inputs to target nodes have any actual inputs first, +/// followed by special operands that describe memory references, then an +/// optional chain operand, then an optional flag operand. Compute the number +/// of actual operands that will go into the resulting MachineInstr. +unsigned ScheduleDAGSDNodes::CountOperands(SDNode *Node) { + unsigned N = ComputeMemOperandsEnd(Node); + while (N && isa<MemOperandSDNode>(Node->getOperand(N - 1).getNode())) + --N; // Ignore MEMOPERAND nodes + return N; +} + +/// ComputeMemOperandsEnd - Find the index one past the last MemOperandSDNode +/// operand +unsigned ScheduleDAGSDNodes::ComputeMemOperandsEnd(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. + return N; +} + + +void ScheduleDAGSDNodes::dumpNode(const SUnit *SU) const { + if (SU->getNode()) + SU->getNode()->dump(DAG); + else + cerr << "CROSS RC COPY "; + cerr << "\n"; + SmallVector<SDNode *, 4> FlaggedNodes; + for (SDNode *N = SU->getNode()->getFlaggedNode(); N; N = N->getFlaggedNode()) + FlaggedNodes.push_back(N); + while (!FlaggedNodes.empty()) { + cerr << " "; + FlaggedNodes.back()->dump(DAG); + cerr << "\n"; + FlaggedNodes.pop_back(); + } +} diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGEmit.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodesEmit.cpp index 0c67973..dc9313b 100644 --- a/lib/CodeGen/SelectionDAG/ScheduleDAGEmit.cpp +++ b/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodesEmit.cpp @@ -13,7 +13,7 @@ //===----------------------------------------------------------------------===// #define DEBUG_TYPE "pre-RA-sched" -#include "llvm/CodeGen/ScheduleDAG.h" +#include "llvm/CodeGen/ScheduleDAGSDNodes.h" #include "llvm/CodeGen/MachineConstantPool.h" #include "llvm/CodeGen/MachineFunction.h" #include "llvm/CodeGen/MachineInstrBuilder.h" @@ -47,9 +47,9 @@ getInstrOperandRegClass(const TargetRegisterInfo *TRI, /// EmitCopyFromReg - Generate machine code for an CopyFromReg node or an /// implicit physical register output. -void ScheduleDAG::EmitCopyFromReg(SDNode *Node, unsigned ResNo, - bool IsClone, unsigned SrcReg, - DenseMap<SDValue, unsigned> &VRBaseMap) { +void ScheduleDAGSDNodes::EmitCopyFromReg(SDNode *Node, unsigned ResNo, + bool IsClone, unsigned SrcReg, + DenseMap<SDValue, unsigned> &VRBaseMap) { unsigned VRBase = 0; if (TargetRegisterInfo::isVirtualRegister(SrcReg)) { // Just use the input register directly! @@ -142,8 +142,8 @@ void ScheduleDAG::EmitCopyFromReg(SDNode *Node, unsigned ResNo, /// getDstOfCopyToRegUse - If the only use of the specified result number of /// node is a CopyToReg, return its destination register. Return 0 otherwise. -unsigned ScheduleDAG::getDstOfOnlyCopyToRegUse(SDNode *Node, - unsigned ResNo) const { +unsigned ScheduleDAGSDNodes::getDstOfOnlyCopyToRegUse(SDNode *Node, + unsigned ResNo) const { if (!Node->hasOneUse()) return 0; @@ -158,7 +158,7 @@ unsigned ScheduleDAG::getDstOfOnlyCopyToRegUse(SDNode *Node, return 0; } -void ScheduleDAG::CreateVirtualRegisters(SDNode *Node, MachineInstr *MI, +void ScheduleDAGSDNodes::CreateVirtualRegisters(SDNode *Node, MachineInstr *MI, const TargetInstrDesc &II, DenseMap<SDValue, unsigned> &VRBaseMap) { assert(Node->getMachineOpcode() != TargetInstrInfo::IMPLICIT_DEF && @@ -202,8 +202,8 @@ void ScheduleDAG::CreateVirtualRegisters(SDNode *Node, MachineInstr *MI, /// getVR - Return the virtual register corresponding to the specified result /// of the specified node. -unsigned ScheduleDAG::getVR(SDValue Op, - DenseMap<SDValue, unsigned> &VRBaseMap) { +unsigned ScheduleDAGSDNodes::getVR(SDValue Op, + DenseMap<SDValue, unsigned> &VRBaseMap) { if (Op.isMachineOpcode() && Op.getMachineOpcode() == TargetInstrInfo::IMPLICIT_DEF) { // Add an IMPLICIT_DEF instruction before every use. @@ -228,10 +228,10 @@ unsigned ScheduleDAG::getVR(SDValue Op, /// specifies the instruction information for the node, and IIOpNum is the /// operand number (in the II) that we are adding. IIOpNum and II are used for /// assertions only. -void ScheduleDAG::AddOperand(MachineInstr *MI, SDValue Op, - unsigned IIOpNum, - const TargetInstrDesc *II, - DenseMap<SDValue, unsigned> &VRBaseMap) { +void ScheduleDAGSDNodes::AddOperand(MachineInstr *MI, SDValue Op, + unsigned IIOpNum, + const TargetInstrDesc *II, + DenseMap<SDValue, unsigned> &VRBaseMap) { if (Op.isMachineOpcode()) { // Note that this case is redundant with the final else block, but we // include it because it is the most common and it makes the logic @@ -328,10 +328,6 @@ void ScheduleDAG::AddOperand(MachineInstr *MI, SDValue Op, } } -void ScheduleDAG::AddMemOperand(MachineInstr *MI, const MachineMemOperand &MO) { - MI->addMemOperand(*MF, MO); -} - /// getSubRegisterRegClass - Returns the register class of specified register /// class' "SubIdx"'th sub-register class. static const TargetRegisterClass* @@ -361,8 +357,8 @@ getSuperRegisterRegClass(const TargetRegisterClass *TRC, /// EmitSubregNode - Generate machine code for subreg nodes. /// -void ScheduleDAG::EmitSubregNode(SDNode *Node, - DenseMap<SDValue, unsigned> &VRBaseMap) { +void ScheduleDAGSDNodes::EmitSubregNode(SDNode *Node, + DenseMap<SDValue, unsigned> &VRBaseMap) { unsigned VRBase = 0; unsigned Opc = Node->getMachineOpcode(); @@ -456,8 +452,8 @@ void ScheduleDAG::EmitSubregNode(SDNode *Node, /// EmitNode - Generate machine code for an node and needed dependencies. /// -void ScheduleDAG::EmitNode(SDNode *Node, bool IsClone, - DenseMap<SDValue, unsigned> &VRBaseMap) { +void ScheduleDAGSDNodes::EmitNode(SDNode *Node, bool IsClone, + DenseMap<SDValue, unsigned> &VRBaseMap) { // If machine instruction if (Node->isMachineOpcode()) { unsigned Opc = Node->getMachineOpcode(); @@ -634,53 +630,8 @@ void ScheduleDAG::EmitNode(SDNode *Node, bool IsClone, } } -void ScheduleDAG::EmitNoop() { - TII->insertNoop(*BB, BB->end()); -} - -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 - if (!I->Dep->getNode()) { - // Copy to physical register. - DenseMap<SUnit*, unsigned>::iterator VRI = VRBaseMap.find(I->Dep); - assert(VRI != VRBaseMap.end() && "Node emitted out of order - late"); - // Find the destination physical register. - unsigned Reg = 0; - for (SUnit::const_succ_iterator II = SU->Succs.begin(), - EE = SU->Succs.end(); II != EE; ++II) { - if (I->Reg) { - Reg = I->Reg; - break; - } - } - assert(I->Reg && "Unknown physical register!"); - TII->copyRegToReg(*BB, BB->end(), Reg, VRI->second, - SU->CopyDstRC, SU->CopySrcRC); - } else { - // Copy from physical register. - assert(I->Reg && "Unknown physical register!"); - unsigned VRBase = MRI.createVirtualRegister(SU->CopyDstRC); - bool isNew = VRBaseMap.insert(std::make_pair(SU, VRBase)).second; - isNew = isNew; // Silence compiler warning. - assert(isNew && "Node emitted out of order - early"); - TII->copyRegToReg(*BB, BB->end(), VRBase, I->Reg, - SU->CopyDstRC, SU->CopySrcRC); - } - break; - } -} - /// EmitSchedule - Emit the machine code in scheduled order. -MachineBasicBlock *ScheduleDAG::EmitSchedule() { - // For post-regalloc scheduling, we're rescheduling the instructions in the - // block, so start by removing them from the block. - if (!DAG) - while (!BB->empty()) - BB->remove(BB->begin()); - +MachineBasicBlock *ScheduleDAGSDNodes::EmitSchedule() { DenseMap<SDValue, unsigned> VRBaseMap; DenseMap<SUnit*, unsigned> CopyVRBaseMap; for (unsigned i = 0, e = Sequence.size(); i != e; i++) { @@ -691,13 +642,6 @@ MachineBasicBlock *ScheduleDAG::EmitSchedule() { continue; } - // For post-regalloc scheduling, we already have the instruction; - // just append it to the block. - if (!DAG) { - BB->push_back(SU->getInstr()); - continue; - } - // For pre-regalloc scheduling, create instructions corresponding to the // SDNode and any flagged SDNodes and append them to the block. SmallVector<SDNode *, 4> FlaggedNodes; diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp index 23822fa..e43b325 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp +++ b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp @@ -34,7 +34,7 @@ #include "llvm/CodeGen/MachineJumpTableInfo.h" #include "llvm/CodeGen/MachineModuleInfo.h" #include "llvm/CodeGen/MachineRegisterInfo.h" -#include "llvm/CodeGen/ScheduleDAG.h" +#include "llvm/CodeGen/ScheduleDAGSDNodes.h" #include "llvm/CodeGen/SchedulerRegistry.h" #include "llvm/CodeGen/SelectionDAG.h" #include "llvm/Target/TargetRegisterInfo.h" diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGPrinter.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGPrinter.cpp index d748108..03b78c3 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAGPrinter.cpp +++ b/lib/CodeGen/SelectionDAG/SelectionDAGPrinter.cpp @@ -15,7 +15,7 @@ #include "llvm/Function.h" #include "llvm/Assembly/Writer.h" #include "llvm/CodeGen/SelectionDAG.h" -#include "llvm/CodeGen/ScheduleDAG.h" +#include "llvm/CodeGen/ScheduleDAGSDNodes.h" #include "llvm/CodeGen/MachineConstantPool.h" #include "llvm/CodeGen/MachineFunction.h" #include "llvm/CodeGen/MachineModuleInfo.h" @@ -383,71 +383,7 @@ void SelectionDAG::setSubgraphColor(SDNode *N, const char *Color) { #endif } -namespace llvm { - template<> - struct DOTGraphTraits<ScheduleDAG*> : public DefaultDOTGraphTraits { - static std::string getGraphName(const ScheduleDAG *G) { - return G->MF->getFunction()->getName(); - } - - static bool renderGraphFromBottomUp() { - return true; - } - - static bool hasNodeAddressLabel(const SUnit *Node, - const ScheduleDAG *Graph) { - return true; - } - - /// If you want to override the dot attributes printed for a particular - /// edge, override this method. - template<typename EdgeIter> - static std::string getEdgeAttributes(const void *Node, EdgeIter EI) { - if (EI.isSpecialDep()) - return "color=cyan,style=dashed"; - if (EI.isCtrlDep()) - return "color=blue,style=dashed"; - return ""; - } - - - static std::string getNodeLabel(const SUnit *Node, - const ScheduleDAG *Graph); - static std::string getNodeAttributes(const SUnit *N, - const ScheduleDAG *Graph) { - return "shape=Mrecord"; - } - - static void addCustomGraphFeatures(ScheduleDAG *G, - GraphWriter<ScheduleDAG*> &GW) { - // Draw a special "GraphRoot" node to indicate the root of the graph. - GW.emitSimpleNode(0, "plaintext=circle", "GraphRoot"); - if (G->DAG) { - // For an SDNode-based ScheduleDAG, point to the root of the ScheduleDAG. - const SDNode *N = G->DAG->getRoot().getNode(); - if (N && N->getNodeId() != -1) - GW.emitEdge(0, -1, &G->SUnits[N->getNodeId()], -1, - "color=blue,style=dashed"); - } else { - // For a MachineInstr-based ScheduleDAG, find a root to point to. - for (unsigned i = 0, e = G->SUnits.size(); i != e; ++i) { - if (G->SUnits[i].Succs.empty()) { - GW.emitEdge(0, -1, &G->SUnits[i], -1, - "color=blue,style=dashed"); - break; - } - } - } - } - }; -} - -std::string DOTGraphTraits<ScheduleDAG*>::getNodeLabel(const SUnit *SU, - const ScheduleDAG *G) { - return G->getGraphNodeLabel(SU); -} - -std::string ScheduleDAG::getGraphNodeLabel(const SUnit *SU) const { +std::string ScheduleDAGSDNodes::getGraphNodeLabel(const SUnit *SU) const { std::string s; raw_string_ostream O(s); O << "SU(" << SU->NodeNum << "): "; @@ -467,17 +403,13 @@ std::string ScheduleDAG::getGraphNodeLabel(const SUnit *SU) const { return O.str(); } -/// viewGraph - Pop up a ghostview window with the reachable parts of the DAG -/// rendered using 'dot'. -/// -void ScheduleDAG::viewGraph() { -// This code is only for debugging! -#ifndef NDEBUG - ViewGraph(this, "dag." + MF->getFunction()->getName(), - "Scheduling-Units Graph for " + MF->getFunction()->getName() + ':' + - BB->getBasicBlock()->getName()); -#else - cerr << "ScheduleDAG::viewGraph is only available in debug builds on " - << "systems with Graphviz or gv!\n"; -#endif // NDEBUG +void ScheduleDAGSDNodes::getCustomGraphFeatures(GraphWriter<ScheduleDAG*> &GW) const { + if (DAG) { + // Draw a special "GraphRoot" node to indicate the root of the graph. + GW.emitSimpleNode(0, "plaintext=circle", "GraphRoot"); + const SDNode *N = DAG->getRoot().getNode(); + if (N && N->getNodeId() != -1) + GW.emitEdge(0, -1, &SUnits[N->getNodeId()], -1, + "color=blue,style=dashed"); + } } |