HexagonMachineScheduler.h revision 3e59040810d0e6e04269ac8f781fa44df6088458
13e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin//===-- HexagonMachineScheduler.h - Custom Hexagon MI scheduler. ----===// 23e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin// 33e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin// The LLVM Compiler Infrastructure 43e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin// 53e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin// This file is distributed under the University of Illinois Open Source 63e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin// License. See LICENSE.TXT for details. 73e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin// 83e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin//===----------------------------------------------------------------------===// 93e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin// 103e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin// Custom Hexagon MI scheduler. 113e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin// 123e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin//===----------------------------------------------------------------------===// 133e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 143e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin#ifndef HEXAGONASMPRINTER_H 153e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin#define HEXAGONASMPRINTER_H 163e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 173e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin#include "llvm/CodeGen/LiveIntervalAnalysis.h" 183e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin#include "llvm/CodeGen/MachineScheduler.h" 193e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin#include "llvm/CodeGen/Passes.h" 203e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin#include "llvm/CodeGen/RegisterClassInfo.h" 213e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin#include "llvm/CodeGen/RegisterPressure.h" 223e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin#include "llvm/CodeGen/ResourcePriorityQueue.h" 233e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin#include "llvm/CodeGen/ScheduleDAGInstrs.h" 243e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin#include "llvm/CodeGen/ScheduleHazardRecognizer.h" 253e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin#include "llvm/Analysis/AliasAnalysis.h" 263e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin#include "llvm/Target/TargetInstrInfo.h" 273e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin#include "llvm/Support/CommandLine.h" 283e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin#include "llvm/Support/Debug.h" 293e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin#include "llvm/Support/ErrorHandling.h" 303e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin#include "llvm/Support/raw_ostream.h" 313e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin#include "llvm/ADT/OwningPtr.h" 323e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin#include "llvm/ADT/PriorityQueue.h" 333e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 343e59040810d0e6e04269ac8f781fa44df6088458Sergei Larinusing namespace llvm; 353e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 363e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin//===----------------------------------------------------------------------===// 373e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin// MachineSchedStrategy - Interface to a machine scheduling algorithm. 383e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin//===----------------------------------------------------------------------===// 393e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 403e59040810d0e6e04269ac8f781fa44df6088458Sergei Larinnamespace llvm { 413e59040810d0e6e04269ac8f781fa44df6088458Sergei Larinclass VLIWMachineScheduler; 423e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 433e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin/// MachineSchedStrategy - Interface used by VLIWMachineScheduler to drive the selected 443e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin/// scheduling algorithm. 453e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin/// 463e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin/// If this works well and targets wish to reuse VLIWMachineScheduler, we may expose it 473e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin/// in ScheduleDAGInstrs.h 483e59040810d0e6e04269ac8f781fa44df6088458Sergei Larinclass MachineSchedStrategy { 493e59040810d0e6e04269ac8f781fa44df6088458Sergei Larinpublic: 503e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin virtual ~MachineSchedStrategy() {} 513e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 523e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin /// Initialize the strategy after building the DAG for a new region. 533e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin virtual void initialize(VLIWMachineScheduler *DAG) = 0; 543e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 553e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin /// Pick the next node to schedule, or return NULL. Set IsTopNode to true to 563e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin /// schedule the node at the top of the unscheduled region. Otherwise it will 573e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin /// be scheduled at the bottom. 583e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin virtual SUnit *pickNode(bool &IsTopNode) = 0; 593e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 603e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin /// Notify MachineSchedStrategy that VLIWMachineScheduler has scheduled a node. 613e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin virtual void schedNode(SUnit *SU, bool IsTopNode) = 0; 623e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 633e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin /// When all predecessor dependencies have been resolved, free this node for 643e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin /// top-down scheduling. 653e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin virtual void releaseTopNode(SUnit *SU) = 0; 663e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin /// When all successor dependencies have been resolved, free this node for 673e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin /// bottom-up scheduling. 683e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin virtual void releaseBottomNode(SUnit *SU) = 0; 693e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin}; 703e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 713e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin//===----------------------------------------------------------------------===// 723e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin// ConvergingVLIWScheduler - Implementation of the standard MachineSchedStrategy. 733e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin//===----------------------------------------------------------------------===// 743e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 753e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin/// ReadyQueue encapsulates vector of "ready" SUnits with basic convenience 763e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin/// methods for pushing and removing nodes. ReadyQueue's are uniquely identified 773e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin/// by an ID. SUnit::NodeQueueId is a mask of the ReadyQueues the SUnit is in. 783e59040810d0e6e04269ac8f781fa44df6088458Sergei Larinclass ReadyQueue { 793e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin unsigned ID; 803e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin std::string Name; 813e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin std::vector<SUnit*> Queue; 823e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 833e59040810d0e6e04269ac8f781fa44df6088458Sergei Larinpublic: 843e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin ReadyQueue(unsigned id, const Twine &name): ID(id), Name(name.str()) {} 853e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 863e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin unsigned getID() const { return ID; } 873e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 883e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin StringRef getName() const { return Name; } 893e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 903e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin // SU is in this queue if it's NodeQueueID is a superset of this ID. 913e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin bool isInQueue(SUnit *SU) const { return (SU->NodeQueueId & ID); } 923e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 933e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin bool empty() const { return Queue.empty(); } 943e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 953e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin unsigned size() const { return Queue.size(); } 963e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 973e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin typedef std::vector<SUnit*>::iterator iterator; 983e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 993e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin iterator begin() { return Queue.begin(); } 1003e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 1013e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin iterator end() { return Queue.end(); } 1023e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 1033e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin iterator find(SUnit *SU) { 1043e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin return std::find(Queue.begin(), Queue.end(), SU); 1053e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin } 1063e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 1073e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin void push(SUnit *SU) { 1083e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin Queue.push_back(SU); 1093e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin SU->NodeQueueId |= ID; 1103e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin } 1113e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 1123e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin void remove(iterator I) { 1133e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin (*I)->NodeQueueId &= ~ID; 1143e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin *I = Queue.back(); 1153e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin Queue.pop_back(); 1163e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin } 1173e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 1183e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin void dump() { 1193e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin dbgs() << Name << ": "; 1203e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin for (unsigned i = 0, e = Queue.size(); i < e; ++i) 1213e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin dbgs() << Queue[i]->NodeNum << " "; 1223e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin dbgs() << "\n"; 1233e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin } 1243e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin}; 1253e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 1263e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin/// ConvergingVLIWScheduler shrinks the unscheduled zone using heuristics to balance 1273e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin/// the schedule. 1283e59040810d0e6e04269ac8f781fa44df6088458Sergei Larinclass ConvergingVLIWScheduler : public MachineSchedStrategy { 1293e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 1303e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin /// Store the state used by ConvergingVLIWScheduler heuristics, required for the 1313e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin /// lifetime of one invocation of pickNode(). 1323e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin struct SchedCandidate { 1333e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin // The best SUnit candidate. 1343e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin SUnit *SU; 1353e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 1363e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin // Register pressure values for the best candidate. 1373e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin RegPressureDelta RPDelta; 1383e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 1393e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin // Best scheduling cost. 1403e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin int SCost; 1413e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 1423e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin SchedCandidate(): SU(NULL), SCost(0) {} 1433e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin }; 1443e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin /// Represent the type of SchedCandidate found within a single queue. 1453e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin enum CandResult { 1463e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin NoCand, NodeOrder, SingleExcess, SingleCritical, SingleMax, MultiPressure, 1473e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin BestCost}; 1483e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 1493e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin /// Each Scheduling boundary is associated with ready queues. It tracks the 1503e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin /// current cycle in whichever direction at has moved, and maintains the state 1513e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin /// of "hazards" and other interlocks at the current cycle. 1523e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin struct SchedBoundary { 1533e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin VLIWMachineScheduler *DAG; 1543e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 1553e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin ReadyQueue Available; 1563e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin ReadyQueue Pending; 1573e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin bool CheckPending; 1583e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 1593e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin ScheduleHazardRecognizer *HazardRec; 1603e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 1613e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin unsigned CurrCycle; 1623e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin unsigned IssueCount; 1633e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 1643e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin /// MinReadyCycle - Cycle of the soonest available instruction. 1653e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin unsigned MinReadyCycle; 1663e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 1673e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin // Remember the greatest min operand latency. 1683e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin unsigned MaxMinLatency; 1693e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 1703e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin /// Pending queues extend the ready queues with the same ID and the 1713e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin /// PendingFlag set. 1723e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin SchedBoundary(unsigned ID, const Twine &Name): 1733e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin DAG(0), Available(ID, Name+".A"), 1743e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin Pending(ID << ConvergingVLIWScheduler::LogMaxQID, Name+".P"), 1753e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin CheckPending(false), HazardRec(0), CurrCycle(0), IssueCount(0), 1763e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin MinReadyCycle(UINT_MAX), MaxMinLatency(0) {} 1773e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 1783e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin ~SchedBoundary() { delete HazardRec; } 1793e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 1803e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin bool isTop() const { 1813e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin return Available.getID() == ConvergingVLIWScheduler::TopQID; 1823e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin } 1833e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 1843e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin bool checkHazard(SUnit *SU); 1853e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 1863e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin void releaseNode(SUnit *SU, unsigned ReadyCycle); 1873e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 1883e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin void bumpCycle(); 1893e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 1903e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin void bumpNode(SUnit *SU); 1913e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 1923e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin void releasePending(); 1933e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 1943e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin void removeReady(SUnit *SU); 1953e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 1963e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin SUnit *pickOnlyChoice(); 1973e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin }; 1983e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 1993e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin VLIWMachineScheduler *DAG; 2003e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin const TargetRegisterInfo *TRI; 2013e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 2023e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin // State of the top and bottom scheduled instruction boundaries. 2033e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin SchedBoundary Top; 2043e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin SchedBoundary Bot; 2053e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 2063e59040810d0e6e04269ac8f781fa44df6088458Sergei Larinpublic: 2073e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin /// SUnit::NodeQueueId: 0 (none), 1 (top), 2 (bot), 3 (both) 2083e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin enum { 2093e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin TopQID = 1, 2103e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin BotQID = 2, 2113e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin LogMaxQID = 2 2123e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin }; 2133e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 2143e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin ConvergingVLIWScheduler(): 2153e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin DAG(0), TRI(0), Top(TopQID, "TopQ"), Bot(BotQID, "BotQ") {} 2163e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 2173e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin virtual void initialize(VLIWMachineScheduler *dag); 2183e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 2193e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin virtual SUnit *pickNode(bool &IsTopNode); 2203e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 2213e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin virtual void schedNode(SUnit *SU, bool IsTopNode); 2223e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 2233e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin virtual void releaseTopNode(SUnit *SU); 2243e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 2253e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin virtual void releaseBottomNode(SUnit *SU); 2263e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 2273e59040810d0e6e04269ac8f781fa44df6088458Sergei Larinprotected: 2283e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin SUnit *pickNodeBidrectional(bool &IsTopNode); 2293e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 2303e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin int SchedulingCost(ReadyQueue &Q, 2313e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin SUnit *SU, SchedCandidate &Candidate, 2323e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin RegPressureDelta &Delta, bool verbose); 2333e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 2343e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin CandResult pickNodeFromQueue(ReadyQueue &Q, 2353e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin const RegPressureTracker &RPTracker, 2363e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin SchedCandidate &Candidate); 2373e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin#ifndef NDEBUG 2383e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin void traceCandidate(const char *Label, const ReadyQueue &Q, SUnit *SU, 2393e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin PressureElement P = PressureElement()); 2403e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin#endif 2413e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin}; 2423e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 2433e59040810d0e6e04269ac8f781fa44df6088458Sergei Larinclass VLIWResourceModel { 2443e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin /// ResourcesModel - Represents VLIW state. 2453e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin /// Not limited to VLIW targets per say, but assumes 2463e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin /// definition of DFA by a target. 2473e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin DFAPacketizer *ResourcesModel; 2483e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 2493e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin const InstrItineraryData *InstrItins; 2503e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 2513e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin /// Local packet/bundle model. Purely 2523e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin /// internal to the MI schedulre at the time. 2533e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin std::vector<SUnit*> Packet; 2543e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 2553e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin /// Total packets created. 2563e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin unsigned TotalPackets; 2573e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 2583e59040810d0e6e04269ac8f781fa44df6088458Sergei Larinpublic: 2593e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin VLIWResourceModel(MachineSchedContext *C, const InstrItineraryData *IID) : 2603e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin InstrItins(IID), TotalPackets(0) { 2613e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin const TargetMachine &TM = C->MF->getTarget(); 2623e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin ResourcesModel = TM.getInstrInfo()->CreateTargetScheduleState(&TM,NULL); 2633e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 2643e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin // This hard requirement could be relaxed, but for now do not let it proceed. 2653e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin assert(ResourcesModel && "Unimplemented CreateTargetScheduleState."); 2663e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 2673e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin Packet.resize(InstrItins->SchedModel->IssueWidth); 2683e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin Packet.clear(); 2693e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin ResourcesModel->clearResources(); 2703e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin } 2713e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 2723e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin ~VLIWResourceModel() { 2733e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin delete ResourcesModel; 2743e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin } 2753e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 2763e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin void resetPacketState() { 2773e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin Packet.clear(); 2783e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin } 2793e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 2803e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin void resetDFA() { 2813e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin ResourcesModel->clearResources(); 2823e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin } 2833e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 2843e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin bool isResourceAvailable(SUnit *SU); 2853e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin void reserveResources(SUnit *SU); 2863e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin unsigned getTotalPackets() const { return TotalPackets; } 2873e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin}; 2883e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 2893e59040810d0e6e04269ac8f781fa44df6088458Sergei Larinclass VLIWMachineScheduler : public ScheduleDAGInstrs { 2903e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin /// AA - AliasAnalysis for making memory reference queries. 2913e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin AliasAnalysis *AA; 2923e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 2933e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin RegisterClassInfo *RegClassInfo; 2943e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin MachineSchedStrategy *SchedImpl; 2953e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 2963e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin /// state separatly for top/bottom sectioins. 2973e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin VLIWResourceModel *TopResourceModel; 2983e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin VLIWResourceModel *BotResourceModel; 2993e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 3003e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin MachineBasicBlock::iterator LiveRegionEnd; 3013e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 3023e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin /// Register pressure in this region computed by buildSchedGraph. 3033e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin IntervalPressure RegPressure; 3043e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin RegPressureTracker RPTracker; 3053e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 3063e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin /// List of pressure sets that exceed the target's pressure limit before 3073e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin /// scheduling, listed in increasing set ID order. Each pressure set is paired 3083e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin /// with its max pressure in the currently scheduled regions. 3093e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin std::vector<PressureElement> RegionCriticalPSets; 3103e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 3113e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin /// The top of the unscheduled zone. 3123e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin MachineBasicBlock::iterator CurrentTop; 3133e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin IntervalPressure TopPressure; 3143e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin RegPressureTracker TopRPTracker; 3153e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 3163e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin /// The bottom of the unscheduled zone. 3173e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin MachineBasicBlock::iterator CurrentBottom; 3183e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin IntervalPressure BotPressure; 3193e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin RegPressureTracker BotRPTracker; 3203e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 3213e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin#ifndef NDEBUG 3223e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin /// The number of instructions scheduled so far. Used to cut off the 3233e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin /// scheduler at the point determined by misched-cutoff. 3243e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin unsigned NumInstrsScheduled; 3253e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin#endif 3263e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 3273e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin /// Total packets in the region. 3283e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin unsigned TotalPackets; 3293e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 3303e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin const MachineLoopInfo *MLI; 3313e59040810d0e6e04269ac8f781fa44df6088458Sergei Larinpublic: 3323e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin VLIWMachineScheduler(MachineSchedContext *C, MachineSchedStrategy *S): 3333e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin ScheduleDAGInstrs(*C->MF, *C->MLI, *C->MDT, /*IsPostRA=*/false, C->LIS), 3343e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin AA(C->AA), RegClassInfo(C->RegClassInfo), SchedImpl(S), 3353e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin RPTracker(RegPressure), CurrentTop(), TopRPTracker(TopPressure), 3363e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin CurrentBottom(), BotRPTracker(BotPressure), MLI(C->MLI) { 3373e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 3383e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin TopResourceModel = new VLIWResourceModel(C, InstrItins); 3393e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin BotResourceModel = new VLIWResourceModel(C, InstrItins); 3403e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 3413e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin#ifndef NDEBUG 3423e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin NumInstrsScheduled = 0; 3433e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin#endif 3443e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin TotalPackets = 0; 3453e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin } 3463e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 3473e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin virtual ~VLIWMachineScheduler() { 3483e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin delete SchedImpl; 3493e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin delete TopResourceModel; 3503e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin delete BotResourceModel; 3513e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin } 3523e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 3533e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin MachineBasicBlock::iterator top() const { return CurrentTop; } 3543e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin MachineBasicBlock::iterator bottom() const { return CurrentBottom; } 3553e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 3563e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin /// Implement the ScheduleDAGInstrs interface for handling the next scheduling 3573e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin /// region. This covers all instructions in a block, while schedule() may only 3583e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin /// cover a subset. 3593e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin void enterRegion(MachineBasicBlock *bb, 3603e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin MachineBasicBlock::iterator begin, 3613e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin MachineBasicBlock::iterator end, 3623e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin unsigned endcount); 3633e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 3643e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin /// Schedule - This is called back from ScheduleDAGInstrs::Run() when it's 3653e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin /// time to do some work. 3663e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin void schedule(); 3673e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 3683e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin unsigned CurCycle; 3693e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 3703e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin /// Get current register pressure for the top scheduled instructions. 3713e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin const IntervalPressure &getTopPressure() const { return TopPressure; } 3723e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin const RegPressureTracker &getTopRPTracker() const { return TopRPTracker; } 3733e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 3743e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin /// Get current register pressure for the bottom scheduled instructions. 3753e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin const IntervalPressure &getBotPressure() const { return BotPressure; } 3763e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin const RegPressureTracker &getBotRPTracker() const { return BotRPTracker; } 3773e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 3783e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin /// Get register pressure for the entire scheduling region before scheduling. 3793e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin const IntervalPressure &getRegPressure() const { return RegPressure; } 3803e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 3813e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin const std::vector<PressureElement> &getRegionCriticalPSets() const { 3823e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin return RegionCriticalPSets; 3833e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin } 3843e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 3853e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin VLIWResourceModel *getTopResourceModel() { return TopResourceModel; }; 3863e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin VLIWResourceModel *getBotResourceModel() { return BotResourceModel; }; 3873e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 3883e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin /// getIssueWidth - Return the max instructions per scheduling group. 3893e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin unsigned getIssueWidth() const { 3903e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin return (InstrItins && InstrItins->SchedModel) 3913e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin ? InstrItins->SchedModel->IssueWidth : 1; 3923e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin } 3933e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 3943e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin /// getNumMicroOps - Return the number of issue slots required for this MI. 3953e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin unsigned getNumMicroOps(MachineInstr *MI) const { 3963e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin if (!InstrItins) return 1; 3973e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin int UOps = InstrItins->getNumMicroOps(MI->getDesc().getSchedClass()); 3983e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin return (UOps >= 0) ? UOps : TII->getNumMicroOps(InstrItins, MI); 3993e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin } 4003e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 4013e59040810d0e6e04269ac8f781fa44df6088458Sergei Larinprivate: 4023e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin void scheduleNodeTopDown(SUnit *SU); 4033e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin void listScheduleTopDown(); 4043e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 4053e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin void initRegPressure(); 4063e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin void updateScheduledPressure(std::vector<unsigned> NewMaxPressure); 4073e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 4083e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin void moveInstruction(MachineInstr *MI, MachineBasicBlock::iterator InsertPos); 4093e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin bool checkSchedLimit(); 4103e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 4113e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin void releaseRoots(); 4123e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 4133e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin void releaseSucc(SUnit *SU, SDep *SuccEdge); 4143e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin void releaseSuccessors(SUnit *SU); 4153e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin void releasePred(SUnit *SU, SDep *PredEdge); 4163e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin void releasePredecessors(SUnit *SU); 4173e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 4183e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin void placeDebugValues(); 4193e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin}; 4203e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin} // namespace 4213e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 4223e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin 4233e59040810d0e6e04269ac8f781fa44df6088458Sergei Larin#endif 424