LLVM API Documentation

Defines | Functions | Variables
ScheduleDAGRRList.cpp File Reference
#include "llvm/CodeGen/SchedulerRegistry.h"
#include "ScheduleDAGSDNodes.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/ScheduleHazardRecognizer.h"
#include "llvm/CodeGen/SelectionDAGISel.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/InlineAsm.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetLowering.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetRegisterInfo.h"
#include "llvm/Target/TargetSubtargetInfo.h"
#include <climits>
Include dependency graph for ScheduleDAGRRList.cpp:

Go to the source code of this file.

Defines

#define DEBUG_TYPE   "pre-RA-sched"

Functions

 STATISTIC (NumBacktracks,"Number of times scheduler backtracked")
 STATISTIC (NumUnfolds,"Number of nodes unfolded")
 STATISTIC (NumDups,"Number of duplicated nodes")
 STATISTIC (NumPRCopies,"Number of physical register copies")
static void GetCostForDef (const ScheduleDAGSDNodes::RegDefIter &RegDefPos, const TargetLowering *TLI, const TargetInstrInfo *TII, const TargetRegisterInfo *TRI, unsigned &RegClass, unsigned &Cost, const MachineFunction &MF)
static bool IsChainDependent (SDNode *Outer, SDNode *Inner, unsigned NestLevel, const TargetInstrInfo *TII)
static SDNode * FindCallSeqStart (SDNode *N, unsigned &NestLevel, unsigned &MaxNest, const TargetInstrInfo *TII)
static void resetVRegCycle (SUnit *SU)
static bool isOperandOf (const SUnit *SU, SDNode *N)
static EVT getPhysicalRegisterVT (SDNode *N, unsigned Reg, const TargetInstrInfo *TII)
static void CheckForLiveRegDef (SUnit *SU, unsigned Reg, std::vector< SUnit * > &LiveRegDefs, SmallSet< unsigned, 4 > &RegAdded, SmallVectorImpl< unsigned > &LRegs, const TargetRegisterInfo *TRI)
static void CheckForLiveRegDefMasked (SUnit *SU, const uint32_t *RegMask, std::vector< SUnit * > &LiveRegDefs, SmallSet< unsigned, 4 > &RegAdded, SmallVectorImpl< unsigned > &LRegs)
static const uint32_t * getNodeRegMask (const SDNode *N)
 getNodeRegMask - Returns the register mask attached to an SDNode, if any.
static int checkSpecialNodes (const SUnit *left, const SUnit *right)
static unsigned CalcNodeSethiUllmanNumber (const SUnit *SU, std::vector< unsigned > &SUNumbers)
static unsigned closestSucc (const SUnit *SU)
static unsigned calcMaxScratches (const SUnit *SU)
static bool hasOnlyLiveInOpers (const SUnit *SU)
static bool hasOnlyLiveOutUses (const SUnit *SU)
static void initVRegCycle (SUnit *SU)
static bool hasVRegCycleUse (const SUnit *SU)
static bool BUHasStall (SUnit *SU, int Height, RegReductionPQBase *SPQ)
static int BUCompareLatency (SUnit *left, SUnit *right, bool checkPref, RegReductionPQBase *SPQ)
static bool BURRSort (SUnit *left, SUnit *right, RegReductionPQBase *SPQ)
static bool canEnableCoalescing (SUnit *SU)
static bool canClobberReachingPhysRegUse (const SUnit *DepSU, const SUnit *SU, ScheduleDAGRRList *scheduleDAG, const TargetInstrInfo *TII, const TargetRegisterInfo *TRI)
static bool canClobberPhysRegDefs (const SUnit *SuccSU, const SUnit *SU, const TargetInstrInfo *TII, const TargetRegisterInfo *TRI)

Variables

static RegisterScheduler burrListDAGScheduler ("list-burr","Bottom-up register reduction list scheduling", createBURRListDAGScheduler)
static RegisterScheduler sourceListDAGScheduler ("source","Similar to list-burr but schedules in source ""order when possible", createSourceListDAGScheduler)
static RegisterScheduler hybridListDAGScheduler ("list-hybrid","Bottom-up register pressure aware list scheduling ""which tries to balance latency and register pressure", createHybridListDAGScheduler)
static RegisterScheduler ILPListDAGScheduler ("list-ilp","Bottom-up register pressure aware list scheduling ""which tries to balance ILP and register pressure", createILPListDAGScheduler)
static cl::opt< bool > DisableSchedCycles ("disable-sched-cycles", cl::Hidden, cl::init(false), cl::desc("Disable cycle-level precision during preRA scheduling"))
static cl::opt< bool > DisableSchedRegPressure ("disable-sched-reg-pressure", cl::Hidden, cl::init(false), cl::desc("Disable regpressure priority in sched=list-ilp"))
static cl::opt< bool > DisableSchedLiveUses ("disable-sched-live-uses", cl::Hidden, cl::init(true), cl::desc("Disable live use priority in sched=list-ilp"))
static cl::opt< bool > DisableSchedVRegCycle ("disable-sched-vrcycle", cl::Hidden, cl::init(false), cl::desc("Disable virtual register cycle interference checks"))
static cl::opt< bool > DisableSchedPhysRegJoin ("disable-sched-physreg-join", cl::Hidden, cl::init(false), cl::desc("Disable physreg def-use affinity"))
static cl::opt< bool > DisableSchedStalls ("disable-sched-stalls", cl::Hidden, cl::init(true), cl::desc("Disable no-stall priority in sched=list-ilp"))
static cl::opt< bool > DisableSchedCriticalPath ("disable-sched-critical-path", cl::Hidden, cl::init(false), cl::desc("Disable critical path priority in sched=list-ilp"))
static cl::opt< bool > DisableSchedHeight ("disable-sched-height", cl::Hidden, cl::init(false), cl::desc("Disable scheduled-height priority in sched=list-ilp"))
static cl::opt< bool > Disable2AddrHack ("disable-2addr-hack", cl::Hidden, cl::init(true), cl::desc("Disable scheduler's two-address hack"))
static cl::opt< int > MaxReorderWindow ("max-sched-reorder", cl::Hidden, cl::init(6), cl::desc("Number of instructions to allow ahead of the critical path ""in sched=list-ilp"))
static cl::opt< unsigned > AvgIPC ("sched-avg-ipc", cl::Hidden, cl::init(1), cl::desc("Average inst/cycle whan no target itinerary exists."))

Define Documentation

#define DEBUG_TYPE   "pre-RA-sched"

Definition at line 39 of file ScheduleDAGRRList.cpp.


Function Documentation

static int BUCompareLatency ( SUnit *  left,
SUnit *  right,
bool  checkPref,
RegReductionPQBase *  SPQ 
) [static]
static bool BUHasStall ( SUnit *  SU,
int  Height,
RegReductionPQBase *  SPQ 
) [static]

Definition at line 2329 of file ScheduleDAGRRList.cpp.

References llvm::ScheduleHazardRecognizer::NoHazard.

Referenced by BUCompareLatency().

static bool BURRSort ( SUnit *  left,
SUnit *  right,
RegReductionPQBase *  SPQ 
) [static]
static unsigned calcMaxScratches ( const SUnit *  SU) [static]

calcMaxScratches - Returns an cost estimate of the worse case requirement for scratch registers, i.e. number of data dependencies.

Definition at line 2207 of file ScheduleDAGRRList.cpp.

References llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::SmallVectorTemplateCommon< T, typename >::end(), I, and llvm::SUnit::Preds.

Referenced by BURRSort().

static unsigned CalcNodeSethiUllmanNumber ( const SUnit *  SU,
std::vector< unsigned > &  SUNumbers 
) [static]

CalcNodeSethiUllmanNumber - Compute Sethi Ullman number. Smaller number is the higher priority.

Definition at line 1837 of file ScheduleDAGRRList.cpp.

References llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::SmallVectorTemplateCommon< T, typename >::end(), I, llvm::SUnit::NodeNum, and llvm::SUnit::Preds.

static bool canClobberPhysRegDefs ( const SUnit *  SuccSU,
const SUnit *  SU,
const TargetInstrInfo *  TII,
const TargetRegisterInfo *  TRI 
) [static]
static bool canClobberReachingPhysRegUse ( const SUnit *  DepSU,
const SUnit *  SU,
ScheduleDAGRRList *  scheduleDAG,
const TargetInstrInfo *  TII,
const TargetRegisterInfo *  TRI 
) [static]

canClobberReachingPhysRegUse - True if SU would clobber one of it's successor's explicit physregs whose definition can reach DepSU. i.e. DepSU should not be scheduled above SU.

Definition at line 2705 of file ScheduleDAGRRList.cpp.

References llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::MachineOperand::clobbersPhysReg(), llvm::SmallVectorTemplateCommon< T, typename >::end(), llvm::MCInstrInfo::get(), llvm::SDNode::getMachineOpcode(), llvm::SUnit::getNode(), getNodeRegMask(), llvm::SUnit::Preds, llvm::TargetRegisterInfo::regsOverlap(), and llvm::SUnit::Succs.

static bool canEnableCoalescing ( SUnit *  SU) [static]
static void CheckForLiveRegDef ( SUnit *  SU,
unsigned  Reg,
std::vector< SUnit * > &  LiveRegDefs,
SmallSet< unsigned, 4 > &  RegAdded,
SmallVectorImpl< unsigned > &  LRegs,
const TargetRegisterInfo *  TRI 
) [static]

CheckForLiveRegDef - Return true and update live register vector if the specified register def of the specified SUnit clobbers any "live" registers.

Definition at line 1209 of file ScheduleDAGRRList.cpp.

References llvm::SmallSet< T, N, C >::insert(), llvm::MCRegAliasIterator::isValid(), and llvm::SmallVectorTemplateBase< T, isPodLike >::push_back().

static void CheckForLiveRegDefMasked ( SUnit *  SU,
const uint32_t *  RegMask,
std::vector< SUnit * > &  LiveRegDefs,
SmallSet< unsigned, 4 > &  RegAdded,
SmallVectorImpl< unsigned > &  LRegs 
) [static]

CheckForLiveRegDefMasked - Check for any live physregs that are clobbered by RegMask, and add them to LRegs.

Definition at line 1231 of file ScheduleDAGRRList.cpp.

References llvm::MachineOperand::clobbersPhysReg(), llvm::SmallSet< T, N, C >::insert(), and llvm::SmallVectorTemplateBase< T, isPodLike >::push_back().

static int checkSpecialNodes ( const SUnit *  left,
const SUnit *  right 
) [static]

Definition at line 1826 of file ScheduleDAGRRList.cpp.

References llvm::SUnit::isScheduleLow.

static unsigned closestSucc ( const SUnit *  SU) [static]

closestSucc - Returns the scheduled cycle of the successor which is closest to the current cycle.

Definition at line 2188 of file ScheduleDAGRRList.cpp.

References llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::ISD::CopyToReg, llvm::SmallVectorTemplateCommon< T, typename >::end(), I, and llvm::SUnit::Succs.

Referenced by BURRSort().

static SDNode* FindCallSeqStart ( SDNode *  N,
unsigned &  NestLevel,
unsigned &  MaxNest,
const TargetInstrInfo *  TII 
) [static]

FindCallSeqStart - Starting from the (lowered) CALLSEQ_END node, locate the corresponding (lowered) CALLSEQ_BEGIN node.

NestLevel and MaxNested are used in recursion to indcate the current level of nesting of CALLSEQ_BEGIN and CALLSEQ_END pairs, as well as the maximum level seen so far.

TODO: It would be better to give CALLSEQ_END an explicit operand to point to the corresponding CALLSEQ_BEGIN to avoid needing to search for it.

Definition at line 461 of file ScheduleDAGRRList.cpp.

References llvm::ISD::EntryToken, llvm::TargetInstrInfo::getCallFrameDestroyOpcode(), llvm::TargetInstrInfo::getCallFrameSetupOpcode(), llvm::SDNode::getMachineOpcode(), llvm::SDValue::getNode(), llvm::SDNode::getNumOperands(), llvm::SDNode::getOpcode(), llvm::SDNode::getOperand(), llvm::SDValue::getValueType(), llvm::SDNode::isMachineOpcode(), llvm::MVT::Other, TII, and llvm::ISD::TokenFactor.

static void GetCostForDef ( const ScheduleDAGSDNodes::RegDefIter &  RegDefPos,
const TargetLowering *  TLI,
const TargetInstrInfo *  TII,
const TargetRegisterInfo *  TRI,
unsigned &  RegClass,
unsigned &  Cost,
const MachineFunction &  MF 
) [static]
static const uint32_t* getNodeRegMask ( const SDNode *  N) [static]

getNodeRegMask - Returns the register mask attached to an SDNode, if any.

Definition at line 1246 of file ScheduleDAGRRList.cpp.

References llvm::SDValue::getNode(), llvm::SDNode::getNumOperands(), and llvm::SDNode::getOperand().

Referenced by canClobberPhysRegDefs(), and canClobberReachingPhysRegUse().

static EVT getPhysicalRegisterVT ( SDNode *  N,
unsigned  Reg,
const TargetInstrInfo *  TII 
) [static]

getPhysicalRegisterVT - Returns the ValueType of the physical register definition of the specified node. FIXME: Move to SelectionDAG?

Definition at line 1194 of file ScheduleDAGRRList.cpp.

References llvm::MCInstrInfo::get(), llvm::MCInstrDesc::getImplicitDefs(), llvm::SDNode::getMachineOpcode(), llvm::MCInstrDesc::getNumDefs(), llvm::SDNode::getValueType(), and llvm::MCInstrDesc::ImplicitDefs.

static bool hasOnlyLiveInOpers ( const SUnit *  SU) [static]
static bool hasOnlyLiveOutUses ( const SUnit *  SU) [static]

hasOnlyLiveOutUses - Return true if SU has only value successors that are CopyToReg to a virtual register. This SU def is probably a liveout and it has no other use. It should be scheduled closer to the terminator.

Definition at line 2242 of file ScheduleDAGRRList.cpp.

References llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::ISD::CopyToReg, llvm::SmallVectorTemplateCommon< T, typename >::end(), llvm::SUnit::getNode(), llvm::SDNode::getOpcode(), llvm::SDNode::getOperand(), getReg(), I, llvm::TargetRegisterInfo::isVirtualRegister(), and llvm::SUnit::Succs.

Referenced by initVRegCycle().

static bool hasVRegCycleUse ( const SUnit *  SU) [static]
static void initVRegCycle ( SUnit *  SU) [static]
static bool IsChainDependent ( SDNode *  Outer,
SDNode *  Inner,
unsigned  NestLevel,
const TargetInstrInfo *  TII 
) [static]
static bool isOperandOf ( const SUnit *  SU,
SDNode *  N 
) [static]

Definition at line 929 of file ScheduleDAGRRList.cpp.

References llvm::SDNode::getGluedNode(), and llvm::SUnit::getNode().

static void resetVRegCycle ( SUnit *  SU) [static]
STATISTIC ( NumBacktracks  ,
"Number of times scheduler backtracked"   
)
STATISTIC ( NumUnfolds  ,
"Number of nodes unfolded"   
)
STATISTIC ( NumDups  ,
"Number of duplicated nodes"   
)
STATISTIC ( NumPRCopies  ,
"Number of physical register copies"   
)

Variable Documentation

cl::opt<unsigned> AvgIPC("sched-avg-ipc", cl::Hidden, cl::init(1), cl::desc("Average inst/cycle whan no target itinerary exists.")) [static]
RegisterScheduler burrListDAGScheduler("list-burr","Bottom-up register reduction list scheduling", createBURRListDAGScheduler) [static]
cl::opt<bool> Disable2AddrHack("disable-2addr-hack", cl::Hidden, cl::init(true), cl::desc("Disable scheduler's two-address hack")) [static]
cl::opt<bool> DisableSchedCriticalPath("disable-sched-critical-path", cl::Hidden, cl::init(false), cl::desc("Disable critical path priority in sched=list-ilp")) [static]
cl::opt<bool> DisableSchedCycles("disable-sched-cycles", cl::Hidden, cl::init(false), cl::desc("Disable cycle-level precision during preRA scheduling")) [static]

Referenced by BURRSort().

cl::opt<bool> DisableSchedHeight("disable-sched-height", cl::Hidden, cl::init(false), cl::desc("Disable scheduled-height priority in sched=list-ilp")) [static]
cl::opt<bool> DisableSchedLiveUses("disable-sched-live-uses", cl::Hidden, cl::init(true), cl::desc("Disable live use priority in sched=list-ilp")) [static]
cl::opt<bool> DisableSchedPhysRegJoin("disable-sched-physreg-join", cl::Hidden, cl::init(false), cl::desc("Disable physreg def-use affinity")) [static]

Referenced by BURRSort().

cl::opt<bool> DisableSchedRegPressure("disable-sched-reg-pressure", cl::Hidden, cl::init(false), cl::desc("Disable regpressure priority in sched=list-ilp")) [static]
cl::opt<bool> DisableSchedStalls("disable-sched-stalls", cl::Hidden, cl::init(true), cl::desc("Disable no-stall priority in sched=list-ilp")) [static]
cl::opt<bool> DisableSchedVRegCycle("disable-sched-vrcycle", cl::Hidden, cl::init(false), cl::desc("Disable virtual register cycle interference checks")) [static]

Referenced by initVRegCycle().

RegisterScheduler hybridListDAGScheduler("list-hybrid","Bottom-up register pressure aware list scheduling ""which tries to balance latency and register pressure", createHybridListDAGScheduler) [static]
RegisterScheduler ILPListDAGScheduler("list-ilp","Bottom-up register pressure aware list scheduling ""which tries to balance ILP and register pressure", createILPListDAGScheduler) [static]
cl::opt<int> MaxReorderWindow("max-sched-reorder", cl::Hidden, cl::init(6), cl::desc("Number of instructions to allow ahead of the critical path ""in sched=list-ilp")) [static]
RegisterScheduler sourceListDAGScheduler("source","Similar to list-burr but schedules in source ""order when possible", createSourceListDAGScheduler) [static]