Experimental post-pass scheduling support. Post-pass scheduling
is currently off by default, and can be enabled with
-disable-post-RA-scheduler=false.
This doesn't have a significant impact on most code yet because it doesn't
yet do anything to address anti-dependencies and it doesn't attempt to
disambiguate memory references. Also, several popular targets
don't have pipeline descriptions yet.
The majority of the changes here are splitting the SelectionDAG-specific
code out of ScheduleDAG, so that ScheduleDAG can be moved to
libLLVMCodeGen.a. The interface between ScheduleDAG-using code and
the rest of the scheduling code is somewhat rough and will evolve.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@59676 91177308-0d34-0410-b5e6-96231b3b80d8
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 @@
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 @@
//===----------------------------------------------------------------------===//
/// 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 @@
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 @@
/// 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 @@
const TargetMachine &tm,
SchedulingPriorityQueue *availqueue,
HazardRecognizer *HR)
- : ScheduleDAG(dag, bb, tm),
+ : ScheduleDAGSDNodes(dag, bb, tm),
AvailableQueue(availqueue), HazardRec(HR) {
}
@@ -212,13 +212,13 @@
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 @@
/// 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 @@
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
similarity index 89%
rename from lib/CodeGen/SelectionDAG/ScheduleDAGEmit.cpp
rename to 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 @@
/// 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 @@
/// 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 @@
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 @@
/// 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 @@
/// 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::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 @@
/// 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 @@
/// 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::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 @@
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 @@
#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 @@
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");
+ }
}