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 SDNodeFindCallSeqStart (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< boolDisableSchedCycles ("disable-sched-cycles", cl::Hidden, cl::init(false), cl::desc("Disable cycle-level precision during preRA scheduling"))
static cl::opt< boolDisableSchedRegPressure ("disable-sched-reg-pressure", cl::Hidden, cl::init(false), cl::desc("Disable regpressure priority in sched=list-ilp"))
static cl::opt< boolDisableSchedLiveUses ("disable-sched-live-uses", cl::Hidden, cl::init(true), cl::desc("Disable live use priority in sched=list-ilp"))
static cl::opt< boolDisableSchedVRegCycle ("disable-sched-vrcycle", cl::Hidden, cl::init(false), cl::desc("Disable virtual register cycle interference checks"))
static cl::opt< boolDisableSchedPhysRegJoin ("disable-sched-physreg-join", cl::Hidden, cl::init(false), cl::desc("Disable physreg def-use affinity"))
static cl::opt< boolDisableSchedStalls ("disable-sched-stalls", cl::Hidden, cl::init(true), cl::desc("Disable no-stall priority in sched=list-ilp"))
static cl::opt< boolDisableSchedCriticalPath ("disable-sched-critical-path", cl::Hidden, cl::init(false), cl::desc("Disable critical path priority in sched=list-ilp"))
static cl::opt< boolDisableSchedHeight ("disable-sched-height", cl::Hidden, cl::init(false), cl::desc("Disable scheduled-height priority in sched=list-ilp"))
static cl::opt< boolDisable2AddrHack ("disable-2addr-hack", cl::Hidden, cl::init(true), cl::desc("Disable scheduler's two-address hack"))
static cl::opt< intMaxReorderWindow ("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< unsignedAvgIPC ("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]