1c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick//==- MachineScheduler.h - MachineInstr Scheduling Pass ----------*- C++ -*-==// 2c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick// 3c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick// The LLVM Compiler Infrastructure 4c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick// 5c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick// This file is distributed under the University of Illinois Open Source 6c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick// License. See LICENSE.TXT for details. 7c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick// 8c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick//===----------------------------------------------------------------------===// 9c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick// 10f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// This file provides an interface for customizing the standard MachineScheduler 11f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// pass. Note that the entire pass may be replaced as follows: 12f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// 13f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// <Target>TargetMachine::createPassConfig(PassManagerBase &PM) { 14f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// PM.substitutePass(&MachineSchedulerID, &CustomSchedulerPassID); 15f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// ...} 16f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// 17f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// The MachineScheduler pass is only responsible for choosing the regions to be 18f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// scheduled. Targets can override the DAG builder and scheduler without 19f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// replacing the pass as follows: 20f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// 21f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// ScheduleDAGInstrs *<Target>PassConfig:: 22f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// createMachineScheduler(MachineSchedContext *C) { 23f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// return new CustomMachineScheduler(C); 24f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// } 25f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// 2636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// The default scheduler, ScheduleDAGMILive, builds the DAG and drives list 27f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// scheduling while updating the instruction stream, register pressure, and live 28f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// intervals. Most targets don't need to override the DAG builder and list 29f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// schedulier, but subtargets that require custom scheduling heuristics may 30f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// plugin an alternate MachineSchedStrategy. The strategy is responsible for 31f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// selecting the highest priority node from the list: 32f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// 33f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// ScheduleDAGInstrs *<Target>PassConfig:: 34f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// createMachineScheduler(MachineSchedContext *C) { 35f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// return new ScheduleDAGMI(C, CustomStrategy(C)); 36f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// } 37f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// 38f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// The DAG builder can also be customized in a sense by adding DAG mutations 39f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// that will run after DAG building and before list scheduling. DAG mutations 40f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// can adjust dependencies based on target-specific knowledge or add weak edges 41f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// to aid heuristics: 42f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// 43f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// ScheduleDAGInstrs *<Target>PassConfig:: 44f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// createMachineScheduler(MachineSchedContext *C) { 45f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// ScheduleDAGMI *DAG = new ScheduleDAGMI(C, CustomStrategy(C)); 46f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// DAG->addMutation(new CustomDependencies(DAG->TII, DAG->TRI)); 47f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// return DAG; 48f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// } 49f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// 50f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// A target that supports alternative schedulers can use the 51f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// MachineSchedRegistry to allow command line selection. This can be done by 52c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick// implementing the following boilerplate: 53c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick// 54c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick// static ScheduleDAGInstrs *createCustomMachineSched(MachineSchedContext *C) { 55c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick// return new CustomMachineScheduler(C); 56c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick// } 57c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick// static MachineSchedRegistry 58d04ec0c855176ebddd459c044bdd24f49938fae4Andrew Trick// SchedCustomRegistry("custom", "Run my target's custom scheduler", 59d04ec0c855176ebddd459c044bdd24f49938fae4Andrew Trick// createCustomMachineSched); 60d04ec0c855176ebddd459c044bdd24f49938fae4Andrew Trick// 61f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// 62f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// Finally, subtargets that don't need to implement custom heuristics but would 63f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// like to configure the GenericScheduler's policy for a given scheduler region, 64f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// including scheduling direction and register pressure tracking policy, can do 65f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// this: 66f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// 67f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// void <SubTarget>Subtarget:: 68f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// overrideSchedPolicy(MachineSchedPolicy &Policy, 69f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// MachineInstr *begin, 70f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// MachineInstr *end, 71f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// unsigned NumRegionInstrs) const { 72f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// Policy.<Flag> = true; 73f45edcc3818757234c20d4d5975c0b992bf1f95eAndrew Trick// } 74c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick// 75c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick//===----------------------------------------------------------------------===// 76c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick 77674be02d525d4e24bc6943ed9274958c580bcfbcJakub Staszak#ifndef LLVM_CODEGEN_MACHINESCHEDULER_H 78674be02d525d4e24bc6943ed9274958c580bcfbcJakub Staszak#define LLVM_CODEGEN_MACHINESCHEDULER_H 79c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick 80c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick#include "llvm/CodeGen/MachinePassRegistry.h" 8178e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick#include "llvm/CodeGen/RegisterPressure.h" 8278e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick#include "llvm/CodeGen/ScheduleDAGInstrs.h" 83c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick 84dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#include <memory> 85dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 86c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Tricknamespace llvm { 87c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick 8878e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trickextern cl::opt<bool> ForceTopDown; 8978e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trickextern cl::opt<bool> ForceBottomUp; 9078e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick 91c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trickclass AliasAnalysis; 92c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trickclass LiveIntervals; 93c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trickclass MachineDominatorTree; 94c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trickclass MachineLoopInfo; 9523d59c2fb847f1869b72bcbda67052ac6b2aaee9Andrew Trickclass RegisterClassInfo; 96c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trickclass ScheduleDAGInstrs; 97178f7d08a41f2e9432b96cd27f0c8ea42fa0ac9eAndrew Trickclass SchedDFSResult; 9836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesclass ScheduleHazardRecognizer; 99c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick 100c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick/// MachineSchedContext provides enough context from the MachineScheduler pass 101c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick/// for the target to instantiate a scheduler. 102c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trickstruct MachineSchedContext { 103c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick MachineFunction *MF; 104c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick const MachineLoopInfo *MLI; 105c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick const MachineDominatorTree *MDT; 106d04ec0c855176ebddd459c044bdd24f49938fae4Andrew Trick const TargetPassConfig *PassConfig; 107c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick AliasAnalysis *AA; 108c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick LiveIntervals *LIS; 109c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick 11086b7e2acc9e3b55b8afdfeabda124cc6547e943bAndrew Trick RegisterClassInfo *RegClassInfo; 111006e1abf76148626fb38de1b643c2d31de7f08a7Andrew Trick 11286b7e2acc9e3b55b8afdfeabda124cc6547e943bAndrew Trick MachineSchedContext(); 11386b7e2acc9e3b55b8afdfeabda124cc6547e943bAndrew Trick virtual ~MachineSchedContext(); 114c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick}; 115c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick 116c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick/// MachineSchedRegistry provides a selection of available machine instruction 117c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick/// schedulers. 118c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trickclass MachineSchedRegistry : public MachinePassRegistryNode { 119c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trickpublic: 120c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick typedef ScheduleDAGInstrs *(*ScheduleDAGCtor)(MachineSchedContext *); 121c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick 122c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick // RegisterPassParser requires a (misnamed) FunctionPassCtor type. 123c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick typedef ScheduleDAGCtor FunctionPassCtor; 124c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick 125c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick static MachinePassRegistry Registry; 126c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick 127c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick MachineSchedRegistry(const char *N, const char *D, ScheduleDAGCtor C) 128c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick : MachinePassRegistryNode(N, D, (MachinePassCtor)C) { 129c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick Registry.Add(this); 130c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick } 131c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick ~MachineSchedRegistry() { Registry.Remove(this); } 132c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick 133c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick // Accessors. 134c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick // 135c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick MachineSchedRegistry *getNext() const { 136c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick return (MachineSchedRegistry *)MachinePassRegistryNode::getNext(); 137c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick } 138c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick static MachineSchedRegistry *getList() { 139c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick return (MachineSchedRegistry *)Registry.getList(); 140c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick } 141c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick static void setListener(MachinePassRegistryListener *L) { 142c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick Registry.setListener(L); 143c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick } 144c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick}; 145c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick 14678e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trickclass ScheduleDAGMI; 14778e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick 14838e61122f27a8ca4ef0578eaf6dc5242880d2918Andrew Trick/// Define a generic scheduling policy for targets that don't provide their own 14938e61122f27a8ca4ef0578eaf6dc5242880d2918Andrew Trick/// MachineSchedStrategy. This can be overriden for each scheduling region 15038e61122f27a8ca4ef0578eaf6dc5242880d2918Andrew Trick/// before building the DAG. 15138e61122f27a8ca4ef0578eaf6dc5242880d2918Andrew Trickstruct MachineSchedPolicy { 15238e61122f27a8ca4ef0578eaf6dc5242880d2918Andrew Trick // Allow the scheduler to disable register pressure tracking. 15338e61122f27a8ca4ef0578eaf6dc5242880d2918Andrew Trick bool ShouldTrackPressure; 15438e61122f27a8ca4ef0578eaf6dc5242880d2918Andrew Trick 15538e61122f27a8ca4ef0578eaf6dc5242880d2918Andrew Trick // Allow the scheduler to force top-down or bottom-up scheduling. If neither 15638e61122f27a8ca4ef0578eaf6dc5242880d2918Andrew Trick // is true, the scheduler runs in both directions and converges. 15738e61122f27a8ca4ef0578eaf6dc5242880d2918Andrew Trick bool OnlyTopDown; 15838e61122f27a8ca4ef0578eaf6dc5242880d2918Andrew Trick bool OnlyBottomUp; 15938e61122f27a8ca4ef0578eaf6dc5242880d2918Andrew Trick 16036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MachineSchedPolicy(): ShouldTrackPressure(false), OnlyTopDown(false), 16136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines OnlyBottomUp(false) {} 16238e61122f27a8ca4ef0578eaf6dc5242880d2918Andrew Trick}; 16338e61122f27a8ca4ef0578eaf6dc5242880d2918Andrew Trick 16478e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick/// MachineSchedStrategy - Interface to the scheduling algorithm used by 16578e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick/// ScheduleDAGMI. 16638e61122f27a8ca4ef0578eaf6dc5242880d2918Andrew Trick/// 16738e61122f27a8ca4ef0578eaf6dc5242880d2918Andrew Trick/// Initialization sequence: 16838e61122f27a8ca4ef0578eaf6dc5242880d2918Andrew Trick/// initPolicy -> shouldTrackPressure -> initialize(DAG) -> registerRoots 16978e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trickclass MachineSchedStrategy { 170354362524a72b3fa43a6c09380b7ae3b2380cbbaJuergen Ributzka virtual void anchor(); 17178e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trickpublic: 17278e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick virtual ~MachineSchedStrategy() {} 17378e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick 17438e61122f27a8ca4ef0578eaf6dc5242880d2918Andrew Trick /// Optionally override the per-region scheduling policy. 17538e61122f27a8ca4ef0578eaf6dc5242880d2918Andrew Trick virtual void initPolicy(MachineBasicBlock::iterator Begin, 17638e61122f27a8ca4ef0578eaf6dc5242880d2918Andrew Trick MachineBasicBlock::iterator End, 17738e61122f27a8ca4ef0578eaf6dc5242880d2918Andrew Trick unsigned NumRegionInstrs) {} 17838e61122f27a8ca4ef0578eaf6dc5242880d2918Andrew Trick 17916bb45c5c8e918efa732fd7d0b31c0f31dc2a979Andrew Trick /// Check if pressure tracking is needed before building the DAG and 18038e61122f27a8ca4ef0578eaf6dc5242880d2918Andrew Trick /// initializing this strategy. Called after initPolicy. 18138e61122f27a8ca4ef0578eaf6dc5242880d2918Andrew Trick virtual bool shouldTrackPressure() const { return true; } 18216bb45c5c8e918efa732fd7d0b31c0f31dc2a979Andrew Trick 18378e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick /// Initialize the strategy after building the DAG for a new region. 18478e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick virtual void initialize(ScheduleDAGMI *DAG) = 0; 18578e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick 1861e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick /// Notify this strategy that all roots have been released (including those 1871e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick /// that depend on EntrySU or ExitSU). 1881e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick virtual void registerRoots() {} 1891e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick 19078e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick /// Pick the next node to schedule, or return NULL. Set IsTopNode to true to 19178e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick /// schedule the node at the top of the unscheduled region. Otherwise it will 19278e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick /// be scheduled at the bottom. 19378e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick virtual SUnit *pickNode(bool &IsTopNode) = 0; 19478e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick 195178f7d08a41f2e9432b96cd27f0c8ea42fa0ac9eAndrew Trick /// \brief Scheduler callback to notify that a new subtree is scheduled. 196178f7d08a41f2e9432b96cd27f0c8ea42fa0ac9eAndrew Trick virtual void scheduleTree(unsigned SubtreeID) {} 197178f7d08a41f2e9432b96cd27f0c8ea42fa0ac9eAndrew Trick 19878e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick /// Notify MachineSchedStrategy that ScheduleDAGMI has scheduled an 19978e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick /// instruction and updated scheduled/remaining flags in the DAG nodes. 20078e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick virtual void schedNode(SUnit *SU, bool IsTopNode) = 0; 20178e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick 20278e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick /// When all predecessor dependencies have been resolved, free this node for 20378e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick /// top-down scheduling. 20478e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick virtual void releaseTopNode(SUnit *SU) = 0; 20578e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick /// When all successor dependencies have been resolved, free this node for 20678e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick /// bottom-up scheduling. 20778e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick virtual void releaseBottomNode(SUnit *SU) = 0; 20878e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick}; 20978e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick 210d039b383e76e6658846dca9eee3fe7f221a2f938Andrew Trick/// Mutate the DAG as a postpass after normal DAG building. 211d039b383e76e6658846dca9eee3fe7f221a2f938Andrew Trickclass ScheduleDAGMutation { 212354362524a72b3fa43a6c09380b7ae3b2380cbbaJuergen Ributzka virtual void anchor(); 213d039b383e76e6658846dca9eee3fe7f221a2f938Andrew Trickpublic: 214d039b383e76e6658846dca9eee3fe7f221a2f938Andrew Trick virtual ~ScheduleDAGMutation() {} 215d039b383e76e6658846dca9eee3fe7f221a2f938Andrew Trick 216d039b383e76e6658846dca9eee3fe7f221a2f938Andrew Trick virtual void apply(ScheduleDAGMI *DAG) = 0; 217d039b383e76e6658846dca9eee3fe7f221a2f938Andrew Trick}; 218d039b383e76e6658846dca9eee3fe7f221a2f938Andrew Trick 21936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// ScheduleDAGMI is an implementation of ScheduleDAGInstrs that simply 22036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// schedules machine instructions according to the given MachineSchedStrategy 22136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// without much extra book-keeping. This is the common functionality between 22236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// PreRA and PostRA MachineScheduler. 22378e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trickclass ScheduleDAGMI : public ScheduleDAGInstrs { 22478e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trickprotected: 22578e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick AliasAnalysis *AA; 226dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines std::unique_ptr<MachineSchedStrategy> SchedImpl; 22778e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick 2289b5caaa9c452f262a52dd5ac7ebbc722da5a63deAndrew Trick /// Topo - A topological ordering for SUnits which permits fast IsReachable 2299b5caaa9c452f262a52dd5ac7ebbc722da5a63deAndrew Trick /// and similar queries. 2309b5caaa9c452f262a52dd5ac7ebbc722da5a63deAndrew Trick ScheduleDAGTopologicalSort Topo; 2319b5caaa9c452f262a52dd5ac7ebbc722da5a63deAndrew Trick 232d039b383e76e6658846dca9eee3fe7f221a2f938Andrew Trick /// Ordered list of DAG postprocessing steps. 233dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines std::vector<std::unique_ptr<ScheduleDAGMutation>> Mutations; 234d039b383e76e6658846dca9eee3fe7f221a2f938Andrew Trick 23578e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick /// The top of the unscheduled zone. 23678e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick MachineBasicBlock::iterator CurrentTop; 23778e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick 23878e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick /// The bottom of the unscheduled zone. 23978e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick MachineBasicBlock::iterator CurrentBottom; 24078e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick 2419b5caaa9c452f262a52dd5ac7ebbc722da5a63deAndrew Trick /// Record the next node in a scheduled cluster. 2429b5caaa9c452f262a52dd5ac7ebbc722da5a63deAndrew Trick const SUnit *NextClusterPred; 2439b5caaa9c452f262a52dd5ac7ebbc722da5a63deAndrew Trick const SUnit *NextClusterSucc; 2449b5caaa9c452f262a52dd5ac7ebbc722da5a63deAndrew Trick 24578e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick#ifndef NDEBUG 24678e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick /// The number of instructions scheduled so far. Used to cut off the 24778e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick /// scheduler at the point determined by misched-cutoff. 24878e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick unsigned NumInstrsScheduled; 24978e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick#endif 25078e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trickpublic: 251dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ScheduleDAGMI(MachineSchedContext *C, std::unique_ptr<MachineSchedStrategy> S, 252dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines bool IsPostRA) 253dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines : ScheduleDAGInstrs(*C->MF, *C->MLI, *C->MDT, IsPostRA, 254dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines /*RemoveKillFlags=*/IsPostRA, C->LIS), 255dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines AA(C->AA), SchedImpl(std::move(S)), Topo(SUnits, &ExitSU), CurrentTop(), 256dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines CurrentBottom(), NextClusterPred(nullptr), NextClusterSucc(nullptr) { 25778e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick#ifndef NDEBUG 25878e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick NumInstrsScheduled = 0; 25978e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick#endif 26078e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick } 26178e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick 262dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Provide a vtable anchor 263dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ~ScheduleDAGMI() override; 26478e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick 26536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Return true if this DAG supports VReg liveness and RegPressure. 26636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines virtual bool hasVRegLiveness() const { return false; } 26740b52bb8f2b4f63f6d99e347af0c48945f9cb4d2Andrew Trick 268d039b383e76e6658846dca9eee3fe7f221a2f938Andrew Trick /// Add a postprocessing step to the DAG builder. 269d039b383e76e6658846dca9eee3fe7f221a2f938Andrew Trick /// Mutations are applied in the order that they are added after normal DAG 270d039b383e76e6658846dca9eee3fe7f221a2f938Andrew Trick /// building and before MachineSchedStrategy initialization. 2719b5caaa9c452f262a52dd5ac7ebbc722da5a63deAndrew Trick /// 2729b5caaa9c452f262a52dd5ac7ebbc722da5a63deAndrew Trick /// ScheduleDAGMI takes ownership of the Mutation object. 273dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines void addMutation(std::unique_ptr<ScheduleDAGMutation> Mutation) { 274dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Mutations.push_back(std::move(Mutation)); 275d039b383e76e6658846dca9eee3fe7f221a2f938Andrew Trick } 276d039b383e76e6658846dca9eee3fe7f221a2f938Andrew Trick 277e38afe1e335084134f7830ba6f2208e2ddde59b4Andrew Trick /// \brief True if an edge can be added from PredSU to SuccSU without creating 278e38afe1e335084134f7830ba6f2208e2ddde59b4Andrew Trick /// a cycle. 279e38afe1e335084134f7830ba6f2208e2ddde59b4Andrew Trick bool canAddEdge(SUnit *SuccSU, SUnit *PredSU); 280e38afe1e335084134f7830ba6f2208e2ddde59b4Andrew Trick 2819b5caaa9c452f262a52dd5ac7ebbc722da5a63deAndrew Trick /// \brief Add a DAG edge to the given SU with the given predecessor 2829b5caaa9c452f262a52dd5ac7ebbc722da5a63deAndrew Trick /// dependence data. 2839b5caaa9c452f262a52dd5ac7ebbc722da5a63deAndrew Trick /// 2849b5caaa9c452f262a52dd5ac7ebbc722da5a63deAndrew Trick /// \returns true if the edge may be added without creating a cycle OR if an 2859b5caaa9c452f262a52dd5ac7ebbc722da5a63deAndrew Trick /// equivalent edge already existed (false indicates failure). 2869b5caaa9c452f262a52dd5ac7ebbc722da5a63deAndrew Trick bool addEdge(SUnit *SuccSU, const SDep &PredDep); 2879b5caaa9c452f262a52dd5ac7ebbc722da5a63deAndrew Trick 28878e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick MachineBasicBlock::iterator top() const { return CurrentTop; } 28978e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick MachineBasicBlock::iterator bottom() const { return CurrentBottom; } 29078e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick 29178e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick /// Implement the ScheduleDAGInstrs interface for handling the next scheduling 29278e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick /// region. This covers all instructions in a block, while schedule() may only 29378e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick /// cover a subset. 29478e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick void enterRegion(MachineBasicBlock *bb, 29578e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick MachineBasicBlock::iterator begin, 29678e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick MachineBasicBlock::iterator end, 29736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned regioninstrs) override; 29878e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick 29978e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick /// Implement ScheduleDAGInstrs interface for scheduling a sequence of 30078e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick /// reorderable instructions. 30136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void schedule() override; 30278e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick 3034392f0f407fe4e2a9ec53b2560a1cbf86357c190Andrew Trick /// Change the position of an instruction within the basic block and update 3044392f0f407fe4e2a9ec53b2560a1cbf86357c190Andrew Trick /// live ranges and region boundary iterators. 3054392f0f407fe4e2a9ec53b2560a1cbf86357c190Andrew Trick void moveInstruction(MachineInstr *MI, MachineBasicBlock::iterator InsertPos); 3064392f0f407fe4e2a9ec53b2560a1cbf86357c190Andrew Trick 30736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const SUnit *getNextClusterPred() const { return NextClusterPred; } 30836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 30936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const SUnit *getNextClusterSucc() const { return NextClusterSucc; } 31036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 31136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void viewGraph(const Twine &Name, const Twine &Title) override; 31236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void viewGraph() override; 31336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 31436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesprotected: 31536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Top-Level entry points for the schedule() driver... 31636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 31736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Apply each ScheduleDAGMutation step in order. This allows different 31836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// instances of ScheduleDAGMI to perform custom DAG postprocessing. 31936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void postprocessDAG(); 32036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 32136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Release ExitSU predecessors and setup scheduler queues. 32236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void initQueues(ArrayRef<SUnit*> TopRoots, ArrayRef<SUnit*> BotRoots); 32336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 32436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Update scheduler DAG and queues after scheduling an instruction. 32536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void updateQueues(SUnit *SU, bool IsTopNode); 32636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 32736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Reinsert debug_values recorded in ScheduleDAGInstrs::DbgValues. 32836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void placeDebugValues(); 32936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 33036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// \brief dump the scheduled Sequence. 33136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void dumpSchedule() const; 33236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 33336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Lesser helpers... 33436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool checkSchedLimit(); 33536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 33636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void findRootsAndBiasEdges(SmallVectorImpl<SUnit*> &TopRoots, 33736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SmallVectorImpl<SUnit*> &BotRoots); 33836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 33936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void releaseSucc(SUnit *SU, SDep *SuccEdge); 34036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void releaseSuccessors(SUnit *SU); 34136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void releasePred(SUnit *SU, SDep *PredEdge); 34236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void releasePredecessors(SUnit *SU); 34336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines}; 34436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 34536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// ScheduleDAGMILive is an implementation of ScheduleDAGInstrs that schedules 34636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// machine instructions while updating LiveIntervals and tracking regpressure. 34736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesclass ScheduleDAGMILive : public ScheduleDAGMI { 34836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesprotected: 34936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines RegisterClassInfo *RegClassInfo; 35036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 35136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Information about DAG subtrees. If DFSResult is NULL, then SchedulerTrees 35236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// will be empty. 35336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SchedDFSResult *DFSResult; 35436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BitVector ScheduledTrees; 35536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 35636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MachineBasicBlock::iterator LiveRegionEnd; 35736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 35836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Map each SU to its summary of pressure changes. This array is updated for 35936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // liveness during bottom-up scheduling. Top-down scheduling may proceed but 36036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // has no affect on the pressure diffs. 36136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PressureDiffs SUPressureDiffs; 36236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 36336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Register pressure in this region computed by initRegPressure. 36436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool ShouldTrackPressure; 36536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines IntervalPressure RegPressure; 36636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines RegPressureTracker RPTracker; 36736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 36836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// List of pressure sets that exceed the target's pressure limit before 36936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// scheduling, listed in increasing set ID order. Each pressure set is paired 37036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// with its max pressure in the currently scheduled regions. 37136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines std::vector<PressureChange> RegionCriticalPSets; 37236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 37336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// The top of the unscheduled zone. 37436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines IntervalPressure TopPressure; 37536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines RegPressureTracker TopRPTracker; 37636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 37736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// The bottom of the unscheduled zone. 37836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines IntervalPressure BotPressure; 37936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines RegPressureTracker BotRPTracker; 38036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 38136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinespublic: 382dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ScheduleDAGMILive(MachineSchedContext *C, 383dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines std::unique_ptr<MachineSchedStrategy> S) 384dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines : ScheduleDAGMI(C, std::move(S), /*IsPostRA=*/false), 385dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines RegClassInfo(C->RegClassInfo), DFSResult(nullptr), 386dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ShouldTrackPressure(false), RPTracker(RegPressure), 387dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines TopRPTracker(TopPressure), BotRPTracker(BotPressure) {} 38836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 38936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines virtual ~ScheduleDAGMILive(); 39036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 39136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Return true if this DAG supports VReg liveness and RegPressure. 39236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool hasVRegLiveness() const override { return true; } 39336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 39436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// \brief Return true if register pressure tracking is enabled. 39536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool isTrackingPressure() const { return ShouldTrackPressure; } 39636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 39778e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick /// Get current register pressure for the top scheduled instructions. 39878e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick const IntervalPressure &getTopPressure() const { return TopPressure; } 39978e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick const RegPressureTracker &getTopRPTracker() const { return TopRPTracker; } 40078e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick 40178e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick /// Get current register pressure for the bottom scheduled instructions. 40278e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick const IntervalPressure &getBotPressure() const { return BotPressure; } 40378e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick const RegPressureTracker &getBotRPTracker() const { return BotRPTracker; } 40478e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick 40578e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick /// Get register pressure for the entire scheduling region before scheduling. 40678e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick const IntervalPressure &getRegPressure() const { return RegPressure; } 40778e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick 4084c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick const std::vector<PressureChange> &getRegionCriticalPSets() const { 40978e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick return RegionCriticalPSets; 41078e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick } 41178e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick 4124c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick PressureDiff &getPressureDiff(const SUnit *SU) { 4134c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick return SUPressureDiffs[SU->NodeNum]; 4144c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick } 4154c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick 4164e1fb1894048455d49d62543b3f83672b27b0000Andrew Trick /// Compute a DFSResult after DAG building is complete, and before any 417178f7d08a41f2e9432b96cd27f0c8ea42fa0ac9eAndrew Trick /// queue comparisons. 4184e1fb1894048455d49d62543b3f83672b27b0000Andrew Trick void computeDFSResult(); 419178f7d08a41f2e9432b96cd27f0c8ea42fa0ac9eAndrew Trick 420178f7d08a41f2e9432b96cd27f0c8ea42fa0ac9eAndrew Trick /// Return a non-null DFS result if the scheduling strategy initialized it. 421178f7d08a41f2e9432b96cd27f0c8ea42fa0ac9eAndrew Trick const SchedDFSResult *getDFSResult() const { return DFSResult; } 422178f7d08a41f2e9432b96cd27f0c8ea42fa0ac9eAndrew Trick 423178f7d08a41f2e9432b96cd27f0c8ea42fa0ac9eAndrew Trick BitVector &getScheduledTrees() { return ScheduledTrees; } 424178f7d08a41f2e9432b96cd27f0c8ea42fa0ac9eAndrew Trick 42536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Implement the ScheduleDAGInstrs interface for handling the next scheduling 42636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// region. This covers all instructions in a block, while schedule() may only 42736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// cover a subset. 42836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void enterRegion(MachineBasicBlock *bb, 42936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MachineBasicBlock::iterator begin, 43036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MachineBasicBlock::iterator end, 43136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned regioninstrs) override; 43236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 43336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Implement ScheduleDAGInstrs interface for scheduling a sequence of 43436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// reorderable instructions. 43536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void schedule() override; 43636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 437851bb2c9cbbd3b1847def5ca7ea8dadf457298b5Andrew Trick /// Compute the cyclic critical path through the DAG. 438851bb2c9cbbd3b1847def5ca7ea8dadf457298b5Andrew Trick unsigned computeCyclicCriticalPath(); 439851bb2c9cbbd3b1847def5ca7ea8dadf457298b5Andrew Trick 44078e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trickprotected: 44178e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick // Top-Level entry points for the schedule() driver... 44278e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick 44378e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick /// Call ScheduleDAGInstrs::buildSchedGraph with register pressure tracking 44478e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick /// enabled. This sets up three trackers. RPTracker will cover the entire DAG 44578e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick /// region, TopTracker and BottomTracker will be initialized to the top and 44678e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick /// bottom of the DAG region without covereing any unscheduled instruction. 44778e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick void buildDAGWithRegPressure(); 44878e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick 44978e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick /// Move an instruction and update register pressure. 45078e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick void scheduleMI(SUnit *SU, bool IsTopNode); 45178e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick 45278e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick // Lesser helpers... 45378e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick 45478e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick void initRegPressure(); 45578e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick 456663bd9922776e5f7bc17dfc574efe3fe05ceb12cAndrew Trick void updatePressureDiffs(ArrayRef<unsigned> LiveUses); 457663bd9922776e5f7bc17dfc574efe3fe05ceb12cAndrew Trick 458fb386db636d134b0b72cf0a37075906cf8f7248cAndrew Trick void updateScheduledPressure(const SUnit *SU, 459fb386db636d134b0b72cf0a37075906cf8f7248cAndrew Trick const std::vector<unsigned> &NewMaxPressure); 46036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines}; 46178e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick 46236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines//===----------------------------------------------------------------------===// 46336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 46436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// Helpers for implementing custom MachineSchedStrategy classes. These take 46536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// care of the book-keeping associated with list scheduling heuristics. 46636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 46736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines//===----------------------------------------------------------------------===// 46878e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick 46936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// ReadyQueue encapsulates vector of "ready" SUnits with basic convenience 47036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// methods for pushing and removing nodes. ReadyQueue's are uniquely identified 47136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// by an ID. SUnit::NodeQueueId is a mask of the ReadyQueues the SUnit is in. 47236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 47336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// This is a convenience class that may be used by implementations of 47436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// MachineSchedStrategy. 47536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesclass ReadyQueue { 47636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned ID; 47736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines std::string Name; 47836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines std::vector<SUnit*> Queue; 47978e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick 48036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinespublic: 48136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ReadyQueue(unsigned id, const Twine &name): ID(id), Name(name.str()) {} 48236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 48336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned getID() const { return ID; } 48436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 48536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines StringRef getName() const { return Name; } 48636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 48736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // SU is in this queue if it's NodeQueueID is a superset of this ID. 48836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool isInQueue(SUnit *SU) const { return (SU->NodeQueueId & ID); } 48936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 49036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool empty() const { return Queue.empty(); } 49136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 49236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void clear() { Queue.clear(); } 49336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 49436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned size() const { return Queue.size(); } 49536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 49636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines typedef std::vector<SUnit*>::iterator iterator; 49736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 49836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines iterator begin() { return Queue.begin(); } 49936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 50036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines iterator end() { return Queue.end(); } 50136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 50236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ArrayRef<SUnit*> elements() { return Queue; } 50336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 50436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines iterator find(SUnit *SU) { 50536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return std::find(Queue.begin(), Queue.end(), SU); 50636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 50736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 50836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void push(SUnit *SU) { 50936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Queue.push_back(SU); 51036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SU->NodeQueueId |= ID; 51136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 51236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 51336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines iterator remove(iterator I) { 51436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines (*I)->NodeQueueId &= ~ID; 51536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines *I = Queue.back(); 51636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned idx = I - Queue.begin(); 51736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Queue.pop_back(); 51836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return Queue.begin() + idx; 51936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 52036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 52136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void dump(); 52236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines}; 52336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 52436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// Summarize the unscheduled region. 52536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesstruct SchedRemainder { 52636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Critical path through the DAG in expected latency. 52736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned CriticalPath; 52836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned CyclicCritPath; 52936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 53036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Scaled count of micro-ops left to schedule. 53136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned RemIssueCount; 53236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 53336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool IsAcyclicLatencyLimited; 53436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 53536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Unscheduled resources 53636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SmallVector<unsigned, 16> RemainingCounts; 53736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 53836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void reset() { 53936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines CriticalPath = 0; 54036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines CyclicCritPath = 0; 54136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines RemIssueCount = 0; 54236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines IsAcyclicLatencyLimited = false; 54336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines RemainingCounts.clear(); 54436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 54536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 54636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SchedRemainder() { reset(); } 54736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 54836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void init(ScheduleDAGMI *DAG, const TargetSchedModel *SchedModel); 54936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines}; 55036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 55136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// Each Scheduling boundary is associated with ready queues. It tracks the 55236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// current cycle in the direction of movement, and maintains the state 55336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// of "hazards" and other interlocks at the current cycle. 55436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesclass SchedBoundary { 55536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinespublic: 55636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// SUnit::NodeQueueId: 0 (none), 1 (top), 2 (bot), 3 (both) 55736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines enum { 55836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines TopQID = 1, 55936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BotQID = 2, 56036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines LogMaxQID = 2 56136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines }; 56236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 56336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ScheduleDAGMI *DAG; 56436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const TargetSchedModel *SchedModel; 56536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SchedRemainder *Rem; 56636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 56736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ReadyQueue Available; 56836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ReadyQueue Pending; 56936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 57036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ScheduleHazardRecognizer *HazardRec; 57136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 57236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesprivate: 57336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// True if the pending Q should be checked/updated before scheduling another 57436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// instruction. 57536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool CheckPending; 57636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 57736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // For heuristics, keep a list of the nodes that immediately depend on the 57836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // most recently scheduled node. 57936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SmallPtrSet<const SUnit*, 8> NextSUs; 58036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 58136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Number of cycles it takes to issue the instructions scheduled in this 58236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// zone. It is defined as: scheduled-micro-ops / issue-width + stalls. 58336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// See getStalls(). 58436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned CurrCycle; 58536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 58636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Micro-ops issued in the current cycle 58736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned CurrMOps; 58836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 58936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// MinReadyCycle - Cycle of the soonest available instruction. 59036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned MinReadyCycle; 59136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 59236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // The expected latency of the critical path in this scheduled zone. 59336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned ExpectedLatency; 59436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 59536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // The latency of dependence chains leading into this zone. 59636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // For each node scheduled bottom-up: DLat = max DLat, N.Depth. 59736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // For each cycle scheduled: DLat -= 1. 59836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned DependentLatency; 59936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 60036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Count the scheduled (issued) micro-ops that can be retired by 60136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// time=CurrCycle assuming the first scheduled instr is retired at time=0. 60236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned RetiredMOps; 60336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 60436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Count scheduled resources that have been executed. Resources are 60536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // considered executed if they become ready in the time that it takes to 60636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // saturate any resource including the one in question. Counts are scaled 60736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // for direct comparison with other resources. Counts can be compared with 60836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // MOps * getMicroOpFactor and Latency * getLatencyFactor. 60936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SmallVector<unsigned, 16> ExecutedResCounts; 61036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 61136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Cache the max count for a single resource. 61236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned MaxExecutedResCount; 61336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 61436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Cache the critical resources ID in this scheduled zone. 61536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned ZoneCritResIdx; 61636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 61736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Is the scheduled region resource limited vs. latency limited. 61836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool IsResourceLimited; 61936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 62036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Record the highest cycle at which each resource has been reserved by a 62136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // scheduled instruction. 62236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SmallVector<unsigned, 16> ReservedCycles; 62336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 62436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#ifndef NDEBUG 625cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // Remember the greatest possible stall as an upper bound on the number of 62636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // times we should retry the pending queue because of a hazard. 627cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines unsigned MaxObservedStall; 62836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#endif 62936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 63036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinespublic: 63136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Pending queues extend the ready queues with the same ID and the 63236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// PendingFlag set. 63336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SchedBoundary(unsigned ID, const Twine &Name): 634dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DAG(nullptr), SchedModel(nullptr), Rem(nullptr), Available(ID, Name+".A"), 63536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Pending(ID << LogMaxQID, Name+".P"), 636dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines HazardRec(nullptr) { 63736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines reset(); 63836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 63936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 64036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ~SchedBoundary(); 64136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 64236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void reset(); 64336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 64436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void init(ScheduleDAGMI *dag, const TargetSchedModel *smodel, 64536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SchedRemainder *rem); 64636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 64736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool isTop() const { 64836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return Available.getID() == TopQID; 64936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 65036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 65136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Number of cycles to issue the instructions scheduled in this zone. 65236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned getCurrCycle() const { return CurrCycle; } 65336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 65436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Micro-ops issued in the current cycle 65536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned getCurrMOps() const { return CurrMOps; } 65636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 65736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Return true if the given SU is used by the most recently scheduled 65836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// instruction. 65936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool isNextSU(const SUnit *SU) const { return NextSUs.count(SU); } 66036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 66136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // The latency of dependence chains leading into this zone. 66236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned getDependentLatency() const { return DependentLatency; } 66336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 66436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Get the number of latency cycles "covered" by the scheduled 66536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// instructions. This is the larger of the critical path within the zone 66636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// and the number of cycles required to issue the instructions. 66736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned getScheduledLatency() const { 66836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return std::max(ExpectedLatency, CurrCycle); 66936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 67036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 67136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned getUnscheduledLatency(SUnit *SU) const { 67236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return isTop() ? SU->getHeight() : SU->getDepth(); 67336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 67436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 67536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned getResourceCount(unsigned ResIdx) const { 67636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return ExecutedResCounts[ResIdx]; 67736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 67836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 67936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Get the scaled count of scheduled micro-ops and resources, including 68036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// executed resources. 68136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned getCriticalCount() const { 68236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!ZoneCritResIdx) 68336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return RetiredMOps * SchedModel->getMicroOpFactor(); 68436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return getResourceCount(ZoneCritResIdx); 68536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 68636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 68736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Get a scaled count for the minimum execution time of the scheduled 68836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// micro-ops that are ready to execute by getExecutedCount. Notice the 68936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// feedback loop. 69036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned getExecutedCount() const { 69136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return std::max(CurrCycle * SchedModel->getLatencyFactor(), 69236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MaxExecutedResCount); 69336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 69436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 69536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned getZoneCritResIdx() const { return ZoneCritResIdx; } 69636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 69736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Is the scheduled region resource limited vs. latency limited. 69836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool isResourceLimited() const { return IsResourceLimited; } 69936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 70036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Get the difference between the given SUnit's ready time and the current 70136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// cycle. 70236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned getLatencyStallCycles(SUnit *SU); 70336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 70436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned getNextResourceCycle(unsigned PIdx, unsigned Cycles); 70536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 70636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool checkHazard(SUnit *SU); 70736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 70836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned findMaxLatency(ArrayRef<SUnit*> ReadySUs); 70936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 71036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned getOtherResourceCount(unsigned &OtherCritIdx); 71136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 71236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void releaseNode(SUnit *SU, unsigned ReadyCycle); 71336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 71436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void releaseTopNode(SUnit *SU); 71536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 71636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void releaseBottomNode(SUnit *SU); 71736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 71836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void bumpCycle(unsigned NextCycle); 71936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 72036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void incExecutedResources(unsigned PIdx, unsigned Count); 72136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 72236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned countResource(unsigned PIdx, unsigned Cycles, unsigned ReadyCycle); 72336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 72436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void bumpNode(SUnit *SU); 72536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 72636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void releasePending(); 72736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 72836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void removeReady(SUnit *SU); 72936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 73036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Call this before applying any other heuristics to the Available queue. 73136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Updates the Available/Pending Q's if necessary and returns the single 73236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// available instruction, or NULL if there are multiple candidates. 73336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SUnit *pickOnlyChoice(); 73436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 73536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#ifndef NDEBUG 73636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void dumpScheduledState(); 73736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#endif 73878e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick}; 73978e5efe1b202f71975ad93f33b1fda21d83fd1fbAndrew Trick 740cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines/// Base class for GenericScheduler. This class maintains information about 741cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines/// scheduling candidates based on TargetSchedModel making it easy to implement 742cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines/// heuristics for either preRA or postRA scheduling. 743cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hinesclass GenericSchedulerBase : public MachineSchedStrategy { 744cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hinespublic: 745cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines /// Represent the type of SchedCandidate found within a single queue. 746cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines /// pickNodeBidirectional depends on these listed by decreasing priority. 747cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines enum CandReason { 748cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines NoCand, PhysRegCopy, RegExcess, RegCritical, Stall, Cluster, Weak, RegMax, 749cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines ResourceReduce, ResourceDemand, BotHeightReduce, BotPathReduce, 750cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines TopDepthReduce, TopPathReduce, NextDefUse, NodeOrder}; 751cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 752cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines#ifndef NDEBUG 753cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines static const char *getReasonStr(GenericSchedulerBase::CandReason Reason); 754cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines#endif 755cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 756cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines /// Policy for scheduling the next instruction in the candidate's zone. 757cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines struct CandPolicy { 758cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines bool ReduceLatency; 759cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines unsigned ReduceResIdx; 760cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines unsigned DemandResIdx; 761cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 762cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines CandPolicy(): ReduceLatency(false), ReduceResIdx(0), DemandResIdx(0) {} 763cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines }; 764cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 765cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines /// Status of an instruction's critical resource consumption. 766cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines struct SchedResourceDelta { 767cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // Count critical resources in the scheduled region required by SU. 768cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines unsigned CritResources; 769cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 770cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // Count critical resources from another region consumed by SU. 771cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines unsigned DemandedResources; 772cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 773cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines SchedResourceDelta(): CritResources(0), DemandedResources(0) {} 774cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 775cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines bool operator==(const SchedResourceDelta &RHS) const { 776cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return CritResources == RHS.CritResources 777cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines && DemandedResources == RHS.DemandedResources; 778cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } 779cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines bool operator!=(const SchedResourceDelta &RHS) const { 780cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return !operator==(RHS); 781cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } 782cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines }; 783cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 784cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines /// Store the state used by GenericScheduler heuristics, required for the 785cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines /// lifetime of one invocation of pickNode(). 786cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines struct SchedCandidate { 787cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines CandPolicy Policy; 788cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 789cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // The best SUnit candidate. 790cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines SUnit *SU; 791cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 792cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // The reason for this candidate. 793cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines CandReason Reason; 794cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 795cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // Set of reasons that apply to multiple candidates. 796cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines uint32_t RepeatReasonSet; 797cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 798cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // Register pressure values for the best candidate. 799cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines RegPressureDelta RPDelta; 800cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 801cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // Critical resource consumption of the best candidate. 802cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines SchedResourceDelta ResDelta; 803cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 804cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines SchedCandidate(const CandPolicy &policy) 805cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines : Policy(policy), SU(nullptr), Reason(NoCand), RepeatReasonSet(0) {} 806cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 807cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines bool isValid() const { return SU; } 808cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 809cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // Copy the status of another candidate without changing policy. 810cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines void setBest(SchedCandidate &Best) { 811cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines assert(Best.Reason != NoCand && "uninitialized Sched candidate"); 812cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines SU = Best.SU; 813cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Reason = Best.Reason; 814cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines RPDelta = Best.RPDelta; 815cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines ResDelta = Best.ResDelta; 816cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } 817cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 818cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines bool isRepeat(CandReason R) { return RepeatReasonSet & (1 << R); } 819cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines void setRepeat(CandReason R) { RepeatReasonSet |= (1 << R); } 820cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 821cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines void initResourceDelta(const ScheduleDAGMI *DAG, 822cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines const TargetSchedModel *SchedModel); 823cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines }; 824cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 825cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hinesprotected: 826cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines const MachineSchedContext *Context; 827cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines const TargetSchedModel *SchedModel; 828cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines const TargetRegisterInfo *TRI; 829cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 830cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines SchedRemainder Rem; 831cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hinesprotected: 832cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines GenericSchedulerBase(const MachineSchedContext *C): 833cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Context(C), SchedModel(nullptr), TRI(nullptr) {} 834cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 835cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines void setPolicy(CandPolicy &Policy, bool IsPostRA, SchedBoundary &CurrZone, 836cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines SchedBoundary *OtherZone); 837cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 838cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines#ifndef NDEBUG 839cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines void traceCandidate(const SchedCandidate &Cand); 840cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines#endif 841cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines}; 842cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 843cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines/// GenericScheduler shrinks the unscheduled zone using heuristics to balance 844cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines/// the schedule. 845cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hinesclass GenericScheduler : public GenericSchedulerBase { 846cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines ScheduleDAGMILive *DAG; 847cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 848cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // State of the top and bottom scheduled instruction boundaries. 849cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines SchedBoundary Top; 850cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines SchedBoundary Bot; 851cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 852cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines MachineSchedPolicy RegionPolicy; 853cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hinespublic: 854cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines GenericScheduler(const MachineSchedContext *C): 855cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines GenericSchedulerBase(C), DAG(nullptr), Top(SchedBoundary::TopQID, "TopQ"), 856cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Bot(SchedBoundary::BotQID, "BotQ") {} 857cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 858cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines void initPolicy(MachineBasicBlock::iterator Begin, 859cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines MachineBasicBlock::iterator End, 860cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines unsigned NumRegionInstrs) override; 861cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 862cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines bool shouldTrackPressure() const override { 863cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return RegionPolicy.ShouldTrackPressure; 864cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } 865cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 866cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines void initialize(ScheduleDAGMI *dag) override; 867cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 868cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines SUnit *pickNode(bool &IsTopNode) override; 869cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 870cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines void schedNode(SUnit *SU, bool IsTopNode) override; 871cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 872cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines void releaseTopNode(SUnit *SU) override { 873cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Top.releaseTopNode(SU); 874cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } 875cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 876cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines void releaseBottomNode(SUnit *SU) override { 877cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Bot.releaseBottomNode(SU); 878cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } 879cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 880cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines void registerRoots() override; 881cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 882cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hinesprotected: 883cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines void checkAcyclicLatency(); 884cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 885cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines void tryCandidate(SchedCandidate &Cand, 886cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines SchedCandidate &TryCand, 887cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines SchedBoundary &Zone, 888cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines const RegPressureTracker &RPTracker, 889cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines RegPressureTracker &TempTracker); 890cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 891cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines SUnit *pickNodeBidirectional(bool &IsTopNode); 892cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 893cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines void pickNodeFromQueue(SchedBoundary &Zone, 894cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines const RegPressureTracker &RPTracker, 895cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines SchedCandidate &Candidate); 896cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 897cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines void reschedulePhysRegCopies(SUnit *SU, bool isTop); 898cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines}; 899cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 900cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines/// PostGenericScheduler - Interface to the scheduling algorithm used by 901cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines/// ScheduleDAGMI. 902cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines/// 903cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines/// Callbacks from ScheduleDAGMI: 904cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines/// initPolicy -> initialize(DAG) -> registerRoots -> pickNode ... 905cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hinesclass PostGenericScheduler : public GenericSchedulerBase { 906cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines ScheduleDAGMI *DAG; 907cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines SchedBoundary Top; 908cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines SmallVector<SUnit*, 8> BotRoots; 909cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hinespublic: 910cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines PostGenericScheduler(const MachineSchedContext *C): 911cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines GenericSchedulerBase(C), Top(SchedBoundary::TopQID, "TopQ") {} 912cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 913cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines virtual ~PostGenericScheduler() {} 914cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 915cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines void initPolicy(MachineBasicBlock::iterator Begin, 916cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines MachineBasicBlock::iterator End, 917cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines unsigned NumRegionInstrs) override { 918cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines /* no configurable policy */ 919cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines }; 920cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 921cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines /// PostRA scheduling does not track pressure. 922cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines bool shouldTrackPressure() const override { return false; } 923cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 924cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines void initialize(ScheduleDAGMI *Dag) override; 925cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 926cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines void registerRoots() override; 927cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 928cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines SUnit *pickNode(bool &IsTopNode) override; 929cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 930cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines void scheduleTree(unsigned SubtreeID) override { 931cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines llvm_unreachable("PostRA scheduler does not support subtree analysis."); 932cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } 933cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 934cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines void schedNode(SUnit *SU, bool IsTopNode) override; 935cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 936cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines void releaseTopNode(SUnit *SU) override { 937cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Top.releaseTopNode(SU); 938cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } 939cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 940cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // Only called for roots. 941cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines void releaseBottomNode(SUnit *SU) override { 942cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines BotRoots.push_back(SU); 943cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } 944cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 945cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hinesprotected: 946cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines void tryCandidate(SchedCandidate &Cand, SchedCandidate &TryCand); 947cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 948cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines void pickNodeFromQueue(SchedCandidate &Cand); 949cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines}; 950cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 951c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick} // namespace llvm 952c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick 953c174eaf9481e3f7a6695d4f19e62e2b6f005c4e9Andrew Trick#endif 954