LLVM  6.0.0svn
Classes | Namespaces | Macros | Typedefs | Functions | Variables
MachineScheduler.cpp File Reference
#include "llvm/CodeGen/MachineScheduler.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/PriorityQueue.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/CodeGen/LiveInterval.h"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineOperand.h"
#include "llvm/CodeGen/MachinePassRegistry.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/MachineValueType.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/CodeGen/RegisterClassInfo.h"
#include "llvm/CodeGen/RegisterPressure.h"
#include "llvm/CodeGen/ScheduleDAG.h"
#include "llvm/CodeGen/ScheduleDAGInstrs.h"
#include "llvm/CodeGen/ScheduleDAGMutation.h"
#include "llvm/CodeGen/ScheduleDFS.h"
#include "llvm/CodeGen/ScheduleHazardRecognizer.h"
#include "llvm/CodeGen/SlotIndexes.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/CodeGen/TargetLowering.h"
#include "llvm/CodeGen/TargetPassConfig.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSchedule.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/MC/LaneBitmask.h"
#include "llvm/Pass.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/GraphWriter.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iterator>
#include <limits>
#include <memory>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

Go to the source code of this file.

Classes

struct  llvm::GraphTraits< ScheduleDAGMI * >
 
struct  llvm::DOTGraphTraits< ScheduleDAGMI * >
 

Namespaces

 llvm
 Compute iterated dominance frontiers using a linear time algorithm.
 

Macros

#define DEBUG_TYPE   "machine-scheduler"
 

Typedefs

using MBBRegionsVector = SmallVector< SchedRegion, 16 >
 

Functions

cl::opt< boolllvm::ForceTopDown ("misched-topdown", cl::Hidden, cl::desc("Force top-down list scheduling"))
 
cl::opt< boolllvm::ForceBottomUp ("misched-bottomup", cl::Hidden, cl::desc("Force bottom-up list scheduling"))
 
 INITIALIZE_PASS_BEGIN (MachineScheduler, DEBUG_TYPE, "Machine Instruction Scheduler", false, false) INITIALIZE_PASS_END(MachineScheduler
 
 INITIALIZE_PASS (PostMachineScheduler, "postmisched", "PostRA Machine Instruction Scheduler", false, false) PostMachineScheduler
 
static ScheduleDAGInstrsuseDefaultMachineSched (MachineSchedContext *C)
 A dummy default scheduler factory indicates whether the scheduler is overridden on the command line. More...
 
static MachineBasicBlock::const_iterator priorNonDebug (MachineBasicBlock::const_iterator I, MachineBasicBlock::const_iterator Beg)
 Decrement this iterator until reaching the top or a non-debug instr. More...
 
static MachineBasicBlock::iterator priorNonDebug (MachineBasicBlock::iterator I, MachineBasicBlock::const_iterator Beg)
 Non-const version. More...
 
static MachineBasicBlock::const_iterator nextIfDebug (MachineBasicBlock::const_iterator I, MachineBasicBlock::const_iterator End)
 If this iterator is a debug value, increment until reaching the End or a non-debug instruction. More...
 
static MachineBasicBlock::iterator nextIfDebug (MachineBasicBlock::iterator I, MachineBasicBlock::const_iterator End)
 Non-const version. More...
 
static bool isSchedBoundary (MachineBasicBlock::iterator MI, MachineBasicBlock *MBB, MachineFunction *MF, const TargetInstrInfo *TII)
 Return true of the given instruction should not be included in a scheduling region. More...
 
static void getSchedRegions (MachineBasicBlock *MBB, MBBRegionsVector &Regions, bool RegionsTopDown)
 
std::unique_ptr< ScheduleDAGMutationllvm::createLoadClusterDAGMutation (const TargetInstrInfo *TII, const TargetRegisterInfo *TRI)
 
std::unique_ptr< ScheduleDAGMutationllvm::createStoreClusterDAGMutation (const TargetInstrInfo *TII, const TargetRegisterInfo *TRI)
 
std::unique_ptr< ScheduleDAGMutationllvm::createCopyConstrainDAGMutation (const TargetInstrInfo *TII, const TargetRegisterInfo *TRI)
 
static bool checkResourceLimit (unsigned LFactor, unsigned Count, unsigned Latency)
 Given a Count of resource usage and a Latency value, return true if a SchedBoundary becomes resource limited. More...
 
static bool tryLess (int TryVal, int CandVal, GenericSchedulerBase::SchedCandidate &TryCand, GenericSchedulerBase::SchedCandidate &Cand, GenericSchedulerBase::CandReason Reason)
 Return true if this heuristic determines order. More...
 
static bool tryGreater (int TryVal, int CandVal, GenericSchedulerBase::SchedCandidate &TryCand, GenericSchedulerBase::SchedCandidate &Cand, GenericSchedulerBase::CandReason Reason)
 
static bool tryLatency (GenericSchedulerBase::SchedCandidate &TryCand, GenericSchedulerBase::SchedCandidate &Cand, SchedBoundary &Zone)
 
static void tracePick (GenericSchedulerBase::CandReason Reason, bool IsTop)
 
static void tracePick (const GenericSchedulerBase::SchedCandidate &Cand)
 
static bool tryPressure (const PressureChange &TryP, const PressureChange &CandP, GenericSchedulerBase::SchedCandidate &TryCand, GenericSchedulerBase::SchedCandidate &Cand, GenericSchedulerBase::CandReason Reason, const TargetRegisterInfo *TRI, const MachineFunction &MF)
 
static unsigned getWeakLeft (const SUnit *SU, bool isTop)
 
static int biasPhysRegCopy (const SUnit *SU, bool isTop)
 Minimize physical register live ranges. More...
 
static ScheduleDAGInstrscreateConveringSched (MachineSchedContext *C)
 
static ScheduleDAGInstrscreateILPMaxScheduler (MachineSchedContext *C)
 
static ScheduleDAGInstrscreateILPMinScheduler (MachineSchedContext *C)
 
static ScheduleDAGInstrscreateInstructionShuffler (MachineSchedContext *C)
 

Variables

cl::opt< boolllvm::DumpCriticalPathLength ("misched-dcpl", cl::Hidden, cl::desc("Print critical path length to stdout"))
 
static cl::opt< boolViewMISchedDAGs ("view-misched-dags", cl::Hidden, cl::desc("Pop up a window to show MISched dags after they are processed"))
 
static cl::opt< unsignedViewMISchedCutoff ("view-misched-cutoff", cl::Hidden, cl::desc("Hide nodes with more predecessor/successor than cutoff"))
 In some situations a few uninteresting nodes depend on nearly all other nodes in the graph, provide a cutoff to hide them. More...
 
static cl::opt< unsignedMISchedCutoff ("misched-cutoff", cl::Hidden, cl::desc("Stop scheduling after N instructions"), cl::init(~0U))
 
static cl::opt< std::string > SchedOnlyFunc ("misched-only-func", cl::Hidden, cl::desc("Only schedule this function"))
 
static cl::opt< unsignedSchedOnlyBlock ("misched-only-block", cl::Hidden, cl::desc("Only schedule this MBB#"))
 
static cl::opt< unsignedReadyListLimit ("misched-limit", cl::Hidden, cl::desc("Limit ready list to N instructions"), cl::init(256))
 Avoid quadratic complexity in unusually large basic blocks by limiting the size of the ready lists. More...
 
static cl::opt< boolEnableRegPressure ("misched-regpressure", cl::Hidden, cl::desc("Enable register pressure scheduling."), cl::init(true))
 
static cl::opt< boolEnableCyclicPath ("misched-cyclicpath", cl::Hidden, cl::desc("Enable cyclic critical path analysis."), cl::init(true))
 
static cl::opt< boolEnableMemOpCluster ("misched-cluster", cl::Hidden, cl::desc("Enable memop clustering."), cl::init(true))
 
static cl::opt< boolVerifyScheduling ("verify-misched", cl::Hidden, cl::desc("Verify machine instrs before and after machine scheduling"))
 
static const unsigned MinSubtreeSize = 8
 
 DEBUG_TYPE
 
Machine Instruction Scheduler
 
Machine Instruction false
 
static cl::opt< MachineSchedRegistry::ScheduleDAGCtor, false, RegisterPassParser< MachineSchedRegistry > > MachineSchedOpt ("misched", cl::init(&useDefaultMachineSched), cl::Hidden, cl::desc("Machine instruction scheduler to use"))
 MachineSchedOpt allows command line selection of the scheduler. More...
 
static MachineSchedRegistry DefaultSchedRegistry ("default", "Use the target's default scheduler choice.", useDefaultMachineSched)
 
static cl::opt< boolEnableMachineSched ("enable-misched", cl::desc("Enable the machine instruction scheduling pass."), cl::init(true), cl::Hidden)
 
static cl::opt< boolEnablePostRAMachineSched ("enable-post-misched", cl::desc("Enable the post-ra machine instruction scheduling pass."), cl::init(true), cl::Hidden)
 
static const unsigned InvalidCycle = ~0U
 
static MachineSchedRegistry GenericSchedRegistry ("converge", "Standard converging scheduler.", createConveringSched)
 
static MachineSchedRegistry ILPMaxRegistry ("ilpmax", "Schedule bottom-up for max ILP", createILPMaxScheduler)
 
static MachineSchedRegistry ILPMinRegistry ("ilpmin", "Schedule bottom-up for min ILP", createILPMinScheduler)
 
static MachineSchedRegistry ShufflerRegistry ("shuffle", "Shuffle machine instructions alternating directions", createInstructionShuffler)
 

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "machine-scheduler"

Definition at line 72 of file MachineScheduler.cpp.

Typedef Documentation

◆ MBBRegionsVector

using MBBRegionsVector = SmallVector<SchedRegion, 16>

Definition at line 457 of file MachineScheduler.cpp.

Function Documentation

◆ biasPhysRegCopy()

static int biasPhysRegCopy ( const SUnit SU,
bool  isTop 
)
static

Minimize physical register live ranges.

Regalloc wants them adjacent to their physreg def/use.

FIXME: This is an unnecessary check on the critical path. Most are root/leaf copies which can be prescheduled. The rest (e.g. x86 MUL) could be bundled with the operation that produces or consumes the physreg. We'll do this when regalloc has support for parallel copies.

Definition at line 2821 of file MachineScheduler.cpp.

References llvm::SUnit::getInstr(), llvm::MachineInstr::getOperand(), llvm::MachineOperand::getReg(), llvm::MachineInstr::isCopy(), llvm::TargetRegisterInfo::isPhysicalRegister(), MI, llvm::SUnit::NumPredsLeft, and llvm::SUnit::NumSuccsLeft.

Referenced by llvm::GenericScheduler::tryCandidate().

◆ checkResourceLimit()

static bool checkResourceLimit ( unsigned  LFactor,
unsigned  Count,
unsigned  Latency 
)
static

Given a Count of resource usage and a Latency value, return true if a SchedBoundary becomes resource limited.

Definition at line 1836 of file MachineScheduler.cpp.

Referenced by llvm::SchedBoundary::bumpCycle(), llvm::SchedBoundary::bumpNode(), and llvm::GenericSchedulerBase::setPolicy().

◆ createConveringSched()

static ScheduleDAGInstrs* createConveringSched ( MachineSchedContext C)
static

Definition at line 3204 of file MachineScheduler.cpp.

References llvm::createGenericSchedLive(), and GenericSchedRegistry.

◆ createILPMaxScheduler()

static ScheduleDAGInstrs* createILPMaxScheduler ( MachineSchedContext C)
static

Definition at line 3452 of file MachineScheduler.cpp.

Referenced by createILPMinScheduler().

◆ createILPMinScheduler()

static ScheduleDAGInstrs* createILPMinScheduler ( MachineSchedContext C)
static

◆ createInstructionShuffler()

static ScheduleDAGInstrs* createInstructionShuffler ( MachineSchedContext C)
static

◆ getSchedRegions()

static void getSchedRegions ( MachineBasicBlock MBB,
MBBRegionsVector Regions,
bool  RegionsTopDown 
)
static

◆ getWeakLeft()

static unsigned getWeakLeft ( const SUnit SU,
bool  isTop 
)
static

◆ INITIALIZE_PASS()

INITIALIZE_PASS ( PostMachineScheduler  ,
"postmisched"  ,
"PostRA Machine Instruction Scheduler ,
false  ,
false   
)

◆ INITIALIZE_PASS_BEGIN()

INITIALIZE_PASS_BEGIN ( MachineScheduler  ,
DEBUG_TYPE  ,
"Machine Instruction Scheduler ,
false  ,
false   
)

◆ isSchedBoundary()

static bool isSchedBoundary ( MachineBasicBlock::iterator  MI,
MachineBasicBlock MBB,
MachineFunction MF,
const TargetInstrInfo TII 
)
static

Return true of the given instruction should not be included in a scheduling region.

MachineScheduler does not currently support scheduling across calls. To handle calls, the DAG builder needs to be modified to create register anti/output dependencies on the registers clobbered by the call's regmask operand. In PreRA scheduling, the stack pointer adjustment already prevents scheduling across calls. In PostRA scheduling, we need the isCall to enforce the boundary, but there would be no benefit to postRA scheduling across calls this late anyway.

Definition at line 432 of file MachineScheduler.cpp.

References B, E, llvm::TargetInstrInfo::isSchedulingBoundary(), and N.

Referenced by getSchedRegions().

◆ nextIfDebug() [1/2]

If this iterator is a debug value, increment until reaching the End or a non-debug instruction.

Definition at line 291 of file MachineScheduler.cpp.

References llvm::WebAssembly::End, and I.

Referenced by llvm::createCopyConstrainDAGMutation(), llvm::ScheduleDAGMI::initQueues(), nextIfDebug(), llvm::ScheduleDAGMI::schedule(), llvm::ScheduleDAGMILive::scheduleMI(), and llvm::ScheduleDAGMILive::updatePressureDiffs().

◆ nextIfDebug() [2/2]

◆ priorNonDebug() [1/2]

Decrement this iterator until reaching the top or a non-debug instr.

Definition at line 270 of file MachineScheduler.cpp.

References assert(), and I.

Referenced by llvm::createCopyConstrainDAGMutation(), priorNonDebug(), llvm::ScheduleDAGMI::schedule(), and llvm::ScheduleDAGMILive::scheduleMI().

◆ priorNonDebug() [2/2]

◆ tracePick() [1/2]

static void tracePick ( GenericSchedulerBase::CandReason  Reason,
bool  IsTop 
)
static

◆ tracePick() [2/2]

static void tracePick ( const GenericSchedulerBase::SchedCandidate Cand)
static

◆ tryGreater()

static bool tryGreater ( int  TryVal,
int  CandVal,
GenericSchedulerBase::SchedCandidate TryCand,
GenericSchedulerBase::SchedCandidate Cand,
GenericSchedulerBase::CandReason  Reason 
)
static

◆ tryLatency()

static bool tryLatency ( GenericSchedulerBase::SchedCandidate TryCand,
GenericSchedulerBase::SchedCandidate Cand,
SchedBoundary Zone 
)
static

◆ tryLess()

static bool tryLess ( int  TryVal,
int  CandVal,
GenericSchedulerBase::SchedCandidate TryCand,
GenericSchedulerBase::SchedCandidate Cand,
GenericSchedulerBase::CandReason  Reason 
)
static

◆ tryPressure()

◆ useDefaultMachineSched()

static ScheduleDAGInstrs* useDefaultMachineSched ( MachineSchedContext C)
static

A dummy default scheduler factory indicates whether the scheduler is overridden on the command line.

Definition at line 243 of file MachineScheduler.cpp.

References DefaultSchedRegistry, EnableMachineSched, EnablePostRAMachineSched, llvm::cl::Hidden, llvm::cl::init(), and MachineSchedOpt.

Referenced by nextIfDebug().

Variable Documentation

◆ DEBUG_TYPE

DEBUG_TYPE

Definition at line 200 of file MachineScheduler.cpp.

◆ DefaultSchedRegistry

MachineSchedRegistry DefaultSchedRegistry("default", "Use the target's default scheduler choice.", useDefaultMachineSched)
static

Referenced by useDefaultMachineSched().

◆ EnableCyclicPath

cl::opt<bool> EnableCyclicPath("misched-cyclicpath", cl::Hidden, cl::desc("Enable cyclic critical path analysis."), cl::init(true))
static

◆ EnableMachineSched

cl::opt<bool> EnableMachineSched("enable-misched", cl::desc("Enable the machine instruction scheduling pass."), cl::init(true), cl::Hidden)
static

Referenced by useDefaultMachineSched().

◆ EnableMemOpCluster

cl::opt<bool> EnableMemOpCluster("misched-cluster", cl::Hidden, cl::desc("Enable memop clustering."), cl::init(true))
static

◆ EnablePostRAMachineSched

cl::opt<bool> EnablePostRAMachineSched("enable-post-misched", cl::desc("Enable the post-ra machine instruction scheduling pass."), cl::init(true), cl::Hidden)
static

Referenced by useDefaultMachineSched().

◆ EnableRegPressure

cl::opt<bool> EnableRegPressure("misched-regpressure", cl::Hidden, cl::desc("Enable register pressure scheduling."), cl::init(true))
static

◆ false

Definition at line 200 of file MachineScheduler.cpp.

◆ GenericSchedRegistry

MachineSchedRegistry GenericSchedRegistry("converge", "Standard converging scheduler.", createConveringSched)
static

Referenced by createConveringSched().

◆ ILPMaxRegistry

MachineSchedRegistry ILPMaxRegistry("ilpmax", "Schedule bottom-up for max ILP", createILPMaxScheduler)
static

Referenced by createILPMinScheduler().

◆ ILPMinRegistry

MachineSchedRegistry ILPMinRegistry("ilpmin", "Schedule bottom-up for min ILP", createILPMinScheduler)
static

Referenced by createILPMinScheduler().

◆ InvalidCycle

const unsigned InvalidCycle = ~0U
static

Definition at line 1830 of file MachineScheduler.cpp.

Referenced by llvm::SchedBoundary::init().

◆ MachineSchedOpt

cl::opt<MachineSchedRegistry::ScheduleDAGCtor, false, RegisterPassParser<MachineSchedRegistry> > MachineSchedOpt("misched", cl::init(&useDefaultMachineSched), cl::Hidden, cl::desc("Machine instruction scheduler to use"))
static

MachineSchedOpt allows command line selection of the scheduler.

Referenced by nextIfDebug(), and useDefaultMachineSched().

◆ MinSubtreeSize

const unsigned MinSubtreeSize = 8
static

Definition at line 125 of file MachineScheduler.cpp.

◆ MISchedCutoff

cl::opt<unsigned> MISchedCutoff("misched-cutoff", cl::Hidden, cl::desc("Stop scheduling after N instructions"), cl::init(~0U))
static

◆ ReadyListLimit

cl::opt<unsigned> ReadyListLimit("misched-limit", cl::Hidden, cl::desc("Limit ready list to N instructions"), cl::init(256))
static

Avoid quadratic complexity in unusually large basic blocks by limiting the size of the ready lists.

Referenced by llvm::SchedBoundary::releaseNode(), and llvm::SchedBoundary::releasePending().

◆ SchedOnlyBlock

cl::opt<unsigned> SchedOnlyBlock("misched-only-block", cl::Hidden, cl::desc("Only schedule this MBB#"))
static

◆ SchedOnlyFunc

cl::opt<std::string> SchedOnlyFunc("misched-only-func", cl::Hidden, cl::desc("Only schedule this function"))
static

◆ Scheduler

Machine Instruction Scheduler

◆ ShufflerRegistry

MachineSchedRegistry ShufflerRegistry("shuffle", "Shuffle machine instructions alternating directions", createInstructionShuffler)
static

◆ VerifyScheduling

cl::opt<bool> VerifyScheduling("verify-misched", cl::Hidden, cl::desc("Verify machine instrs before and after machine scheduling"))
static

◆ ViewMISchedCutoff

cl::opt<unsigned> ViewMISchedCutoff("view-misched-cutoff", cl::Hidden, cl::desc("Hide nodes with more predecessor/successor than cutoff"))
static

In some situations a few uninteresting nodes depend on nearly all other nodes in the graph, provide a cutoff to hide them.

Referenced by llvm::DOTGraphTraits< ScheduleDAGMI * >::isNodeHidden().

◆ ViewMISchedDAGs

cl::opt<bool> ViewMISchedDAGs("view-misched-dags", cl::Hidden, cl::desc("Pop up a window to show MISched dags after they are processed"))
static