LLVM  8.0.1
Macros | Functions | Variables
ScheduleDAGRRList.cpp File Reference
#include "ScheduleDAGSDNodes.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/CodeGen/ISDOpcodes.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineOperand.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/ScheduleDAG.h"
#include "llvm/CodeGen/ScheduleHazardRecognizer.h"
#include "llvm/CodeGen/SchedulerRegistry.h"
#include "llvm/CodeGen/SelectionDAGISel.h"
#include "llvm/CodeGen/SelectionDAGNodes.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/CodeGen/TargetLowering.h"
#include "llvm/CodeGen/TargetOpcodes.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/Config/llvm-config.h"
#include "llvm/IR/InlineAsm.h"
#include "llvm/MC/MCInstrDesc.h"
#include "llvm/MC/MCRegisterInfo.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CodeGen.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/MachineValueType.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <cstdlib>
#include <iterator>
#include <limits>
#include <memory>
#include <utility>
#include <vector>
Include dependency graph for ScheduleDAGRRList.cpp:

Go to the source code of this file.

Macros

#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)
 GetCostForDef - Looks up the register class and cost for a given definition. More...
 
static bool IsChainDependent (SDNode *Outer, SDNode *Inner, unsigned NestLevel, const TargetInstrInfo *TII)
 IsChainDependent - Test if Outer is reachable from Inner through chain dependencies. More...
 
static SDNodeFindCallSeqStart (SDNode *N, unsigned &NestLevel, unsigned &MaxNest, const TargetInstrInfo *TII)
 FindCallSeqStart - Starting from the (lowered) CALLSEQ_END node, locate the corresponding (lowered) CALLSEQ_BEGIN node. More...
 
static void resetVRegCycle (SUnit *SU)
 
static bool isOperandOf (const SUnit *SU, SDNode *N)
 
static MVT getPhysicalRegisterVT (SDNode *N, unsigned Reg, const TargetInstrInfo *TII)
 getPhysicalRegisterVT - Returns the ValueType of the physical register definition of the specified node. More...
 
static void CheckForLiveRegDef (SUnit *SU, unsigned Reg, SUnit **LiveRegDefs, SmallSet< unsigned, 4 > &RegAdded, SmallVectorImpl< unsigned > &LRegs, const TargetRegisterInfo *TRI)
 CheckForLiveRegDef - Return true and update live register vector if the specified register def of the specified SUnit clobbers any "live" registers. More...
 
static void CheckForLiveRegDefMasked (SUnit *SU, const uint32_t *RegMask, ArrayRef< SUnit *> LiveRegDefs, SmallSet< unsigned, 4 > &RegAdded, SmallVectorImpl< unsigned > &LRegs)
 CheckForLiveRegDefMasked - Check for any live physregs that are clobbered by RegMask, and add them to LRegs. More...
 
static const uint32_tgetNodeRegMask (const SDNode *N)
 getNodeRegMask - Returns the register mask attached to an SDNode, if any. More...
 
static int checkSpecialNodes (const SUnit *left, const SUnit *right)
 
static unsigned CalcNodeSethiUllmanNumber (const SUnit *SU, std::vector< unsigned > &SUNumbers)
 CalcNodeSethiUllmanNumber - Compute Sethi Ullman number. More...
 
static unsigned closestSucc (const SUnit *SU)
 closestSucc - Returns the scheduled cycle of the successor which is closest to the current cycle. More...
 
static unsigned calcMaxScratches (const SUnit *SU)
 calcMaxScratches - Returns an cost estimate of the worse case requirement for scratch registers, i.e. More...
 
static bool hasOnlyLiveInOpers (const SUnit *SU)
 hasOnlyLiveInOpers - Return true if SU has only value predecessors that are CopyFromReg from a virtual register. More...
 
static bool hasOnlyLiveOutUses (const SUnit *SU)
 hasOnlyLiveOutUses - Return true if SU has only value successors that are CopyToReg to a virtual register. More...
 
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)
 canClobberReachingPhysRegUse - True if SU would clobber one of it's successor's explicit physregs whose definition can reach DepSU. More...
 
static bool canClobberPhysRegDefs (const SUnit *SuccSU, const SUnit *SU, const TargetInstrInfo *TII, const TargetRegisterInfo *TRI)
 canClobberPhysRegDefs - True if SU would clobber one of SuccSU's physical register defs. More...
 

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< 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< unsignedAvgIPC ("sched-avg-ipc", cl::Hidden, cl::init(1), cl::desc("Average inst/cycle whan no target itinerary exists."))
 

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "pre-RA-sched"

Definition at line 63 of file ScheduleDAGRRList.cpp.

Function Documentation

◆ BUCompareLatency()

static int BUCompareLatency ( SUnit left,
SUnit right,
bool  checkPref,
RegReductionPQBase *  SPQ 
)
static

◆ BUHasStall()

static bool BUHasStall ( SUnit SU,
int  Height,
RegReductionPQBase *  SPQ 
)
static

◆ BURRSort()

static bool BURRSort ( SUnit left,
SUnit right,
RegReductionPQBase *  SPQ 
)
static

◆ calcMaxScratches()

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 2328 of file ScheduleDAGRRList.cpp.

References llvm::SDep::isCtrl(), and llvm::SUnit::Preds.

Referenced by BURRSort().

◆ CalcNodeSethiUllmanNumber()

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

◆ canClobberPhysRegDefs()

static bool canClobberPhysRegDefs ( const SUnit SuccSU,
const SUnit SU,
const TargetInstrInfo TII,
const TargetRegisterInfo TRI 
)
static

◆ canClobberReachingPhysRegUse()

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 2820 of file ScheduleDAGRRList.cpp.

References llvm::MachineOperand::clobbersPhysReg(), llvm::MCInstrInfo::get(), llvm::SDNode::getMachineOpcode(), llvm::SUnit::getNode(), getNodeRegMask(), llvm::SDep::getReg(), llvm::SDep::getSUnit(), llvm::SDep::isAssignedRegDep(), llvm::SUnit::Preds, llvm::TargetRegisterInfo::regsOverlap(), and llvm::SUnit::Succs.

◆ canEnableCoalescing()

static bool canEnableCoalescing ( SUnit SU)
static

◆ CheckForLiveRegDef()

static void CheckForLiveRegDef ( SUnit SU,
unsigned  Reg,
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 1286 of file ScheduleDAGRRList.cpp.

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

Referenced by getNodeRegMask().

◆ CheckForLiveRegDefMasked()

static void CheckForLiveRegDefMasked ( SUnit SU,
const uint32_t RegMask,
ArrayRef< 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 1308 of file ScheduleDAGRRList.cpp.

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

◆ checkSpecialNodes()

static int checkSpecialNodes ( const SUnit left,
const SUnit right 
)
static

Definition at line 1914 of file ScheduleDAGRRList.cpp.

References llvm::SUnit::isScheduleLow.

Referenced by BURRSort(), and canEnableCoalescing().

◆ closestSucc()

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 2310 of file ScheduleDAGRRList.cpp.

References llvm::ISD::CopyToReg, llvm::SUnit::getHeight(), llvm::SUnit::getNode(), llvm::SDNode::getOpcode(), llvm::SDep::getSUnit(), llvm::SDep::isCtrl(), and llvm::SUnit::Succs.

Referenced by BURRSort().

◆ FindCallSeqStart()

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 484 of file ScheduleDAGRRList.cpp.

References assert(), llvm::ISD::EntryToken, llvm::TargetInstrInfo::getCallFrameDestroyOpcode(), llvm::TargetInstrInfo::getCallFrameSetupOpcode(), llvm::SDNode::getMachineOpcode(), llvm::SDNode::getOpcode(), llvm::SDep::getReg(), llvm::SDep::getSUnit(), llvm::SDep::isAssignedRegDep(), llvm::SDNode::isMachineOpcode(), llvm::max(), N, llvm::SDNode::op_values(), llvm::MVT::Other, llvm::SUnit::Preds, TII, llvm::ISD::TokenFactor, and TRI.

◆ GetCostForDef()

static void GetCostForDef ( const ScheduleDAGSDNodes::RegDefIter RegDefPos,
const TargetLowering TLI,
const TargetInstrInfo TII,
const TargetRegisterInfo TRI,
unsigned RegClass,
unsigned Cost,
const MachineFunction MF 
)
static

GetCostForDef - Looks up the register class and cost for a given definition.

Typically this just means looking up the representative register class, but for untyped values (MVT::Untyped) it means inspecting the node's opcode to determine what register class is being generated.

Definition at line 304 of file ScheduleDAGRRList.cpp.

References llvm::ScheduleDAGSDNodes::RegDefIter::GetValue(), and llvm::MVT::Untyped.

Referenced by CalcNodeSethiUllmanNumber().

◆ getNodeRegMask()

static const uint32_t* getNodeRegMask ( const SDNode N)
static

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

Definition at line 1323 of file ScheduleDAGRRList.cpp.

References CheckForLiveRegDef(), llvm::SDep::getReg(), llvm::SDep::getSUnit(), llvm::SDep::isAssignedRegDep(), llvm::SDNode::op_values(), llvm::SUnit::Preds, and TRI.

Referenced by canClobberPhysRegDefs(), and canClobberReachingPhysRegUse().

◆ getPhysicalRegisterVT()

static MVT 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 1265 of file ScheduleDAGRRList.cpp.

References assert(), llvm::ISD::CopyFromReg, llvm::MCInstrInfo::get(), llvm::MCInstrDesc::getImplicitDefs(), llvm::SDNode::getMachineOpcode(), llvm::MCInstrDesc::getNumDefs(), llvm::SDNode::getOpcode(), llvm::SDNode::getSimpleValueType(), and llvm::MCInstrDesc::ImplicitDefs.

◆ hasOnlyLiveInOpers()

static bool hasOnlyLiveInOpers ( const SUnit SU)
static

hasOnlyLiveInOpers - Return true if SU has only value predecessors that are CopyFromReg from a virtual register.

Definition at line 2339 of file ScheduleDAGRRList.cpp.

References llvm::ISD::CopyFromReg, llvm::SUnit::getNode(), llvm::SDNode::getOpcode(), llvm::SDNode::getOperand(), getReg(), llvm::SDep::getSUnit(), llvm::SDep::isCtrl(), llvm::TargetRegisterInfo::isVirtualRegister(), and llvm::SUnit::Preds.

Referenced by initVRegCycle().

◆ hasOnlyLiveOutUses()

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 2361 of file ScheduleDAGRRList.cpp.

References llvm::ISD::CopyToReg, llvm::SUnit::getNode(), llvm::SDNode::getOpcode(), llvm::SDNode::getOperand(), getReg(), llvm::SDep::getSUnit(), llvm::SDep::isCtrl(), llvm::TargetRegisterInfo::isVirtualRegister(), and llvm::SUnit::Succs.

Referenced by initVRegCycle().

◆ hasVRegCycleUse()

static bool hasVRegCycleUse ( const SUnit SU)
static

◆ initVRegCycle()

static void initVRegCycle ( SUnit SU)
static

◆ IsChainDependent()

static bool IsChainDependent ( SDNode Outer,
SDNode Inner,
unsigned  NestLevel,
const TargetInstrInfo TII 
)
static

◆ isOperandOf()

static bool isOperandOf ( const SUnit SU,
SDNode N 
)
static

◆ resetVRegCycle()

static void resetVRegCycle ( SUnit SU)
static

◆ STATISTIC() [1/4]

STATISTIC ( NumBacktracks  ,
"Number of times scheduler backtracked"   
)

◆ STATISTIC() [2/4]

STATISTIC ( NumUnfolds  ,
"Number of nodes unfolded"   
)

◆ STATISTIC() [3/4]

STATISTIC ( NumDups  ,
"Number of duplicated nodes  
)

◆ STATISTIC() [4/4]

STATISTIC ( NumPRCopies  ,
"Number of physical register copies  
)

Variable Documentation

◆ AvgIPC

cl::opt<unsigned> AvgIPC("sched-avg-ipc", cl::Hidden, cl::init(1), cl::desc("Average inst/cycle whan no target itinerary exists."))
static

◆ burrListDAGScheduler

RegisterScheduler burrListDAGScheduler("list-burr", "Bottom-up register reduction list scheduling", createBURRListDAGScheduler)
static

◆ Disable2AddrHack

cl::opt<bool> Disable2AddrHack("disable-2addr-hack", cl::Hidden, cl::init(true), cl::desc("Disable scheduler's two-address hack"))
static

Referenced by canEnableCoalescing().

◆ DisableSchedCriticalPath

cl::opt<bool> DisableSchedCriticalPath("disable-sched-critical-path", cl::Hidden, cl::init(false), cl::desc("Disable critical path priority in sched=list-ilp"))
static

◆ DisableSchedCycles

cl::opt<bool> DisableSchedCycles("disable-sched-cycles", cl::Hidden, cl::init(false), cl::desc("Disable cycle-level precision during preRA scheduling"))
static

Referenced by BUCompareLatency(), and BURRSort().

◆ DisableSchedHeight

cl::opt<bool> DisableSchedHeight("disable-sched-height", cl::Hidden, cl::init(false), cl::desc("Disable scheduled-height priority in sched=list-ilp"))
static

◆ DisableSchedLiveUses

cl::opt<bool> DisableSchedLiveUses("disable-sched-live-uses", cl::Hidden, cl::init(true), cl::desc("Disable live use priority in sched=list-ilp"))
static

Referenced by canEnableCoalescing().

◆ DisableSchedPhysRegJoin

cl::opt<bool> DisableSchedPhysRegJoin("disable-sched-physreg-join", cl::Hidden, cl::init(false), cl::desc("Disable physreg def-use affinity"))
static

Referenced by BURRSort().

◆ DisableSchedRegPressure

cl::opt<bool> DisableSchedRegPressure("disable-sched-reg-pressure", cl::Hidden, cl::init(false), cl::desc("Disable regpressure priority in sched=list-ilp"))
static

Referenced by canEnableCoalescing().

◆ DisableSchedStalls

cl::opt<bool> DisableSchedStalls("disable-sched-stalls", cl::Hidden, cl::init(true), cl::desc("Disable no-stall priority in sched=list-ilp"))
static

Referenced by canEnableCoalescing().

◆ DisableSchedVRegCycle

cl::opt<bool> DisableSchedVRegCycle("disable-sched-vrcycle", cl::Hidden, cl::init(false), cl::desc("Disable virtual register cycle interference checks"))
static

Referenced by initVRegCycle().

◆ hybridListDAGScheduler

RegisterScheduler hybridListDAGScheduler("list-hybrid", "Bottom-up register pressure aware list scheduling " "which tries to balance latency and register pressure", createHybridListDAGScheduler)
static

◆ ILPListDAGScheduler

RegisterScheduler ILPListDAGScheduler("list-ilp", "Bottom-up register pressure aware list scheduling " "which tries to balance ILP and register pressure", createILPListDAGScheduler)
static

◆ MaxReorderWindow

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

◆ sourceListDAGScheduler

RegisterScheduler sourceListDAGScheduler("source", "Similar to list-burr but schedules in source " "order when possible", createSourceListDAGScheduler)
static