#ifndef LLVM_CODEGEN_SCHEDULEDAGINSTRS_H
#define LLVM_CODEGEN_SCHEDULEDAGINSTRS_H
-#include "llvm/ADT/SmallSet.h"
-#include "llvm/ADT/SparseSet.h"
#include "llvm/ADT/SparseMultiSet.h"
-#include "llvm/CodeGen/MachineDominators.h"
-#include "llvm/CodeGen/MachineLoopInfo.h"
+#include "llvm/ADT/SparseSet.h"
#include "llvm/CodeGen/ScheduleDAG.h"
#include "llvm/CodeGen/TargetSchedule.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Target/TargetRegisterInfo.h"
-#include <map>
namespace llvm {
+ class MachineFrameInfo;
class MachineLoopInfo;
class MachineDominatorTree;
class LiveIntervals;
class RegPressureTracker;
+ class PressureDiffs;
/// An individual mapping from virtual register number to SUnit.
struct VReg2SUnit {
};
/// Record a physical register access.
- /// For non data-dependent uses, OpIdx == -1.
+ /// For non-data-dependent uses, OpIdx == -1.
struct PhysRegSUOper {
SUnit *SU;
int OpIdx;
/// Use a SparseMultiSet to track physical registers. Storage is only
/// allocated once for the pass. It can be cleared in constant time and reused
/// without any frees.
- typedef SparseMultiSet<PhysRegSUOper, llvm::identity<unsigned>, uint16_t> Reg2SUnitsMap;
+ typedef SparseMultiSet<PhysRegSUOper, llvm::identity<unsigned>, uint16_t>
+ Reg2SUnitsMap;
/// Use SparseSet as a SparseMap by relying on the fact that it never
/// compares ValueT's, only unsigned keys. This allows the set to be cleared
/// require a destructor.
typedef SparseSet<VReg2SUnit, VirtReg2IndexFunctor> VReg2SUnitMap;
+ /// Track local uses of virtual registers. These uses are gathered by the DAG
+ /// builder and may be consulted by the scheduler to avoid iterating an entire
+ /// vreg use list.
+ typedef SparseMultiSet<VReg2SUnit, VirtReg2IndexFunctor> VReg2UseMap;
+
/// ScheduleDAGInstrs - A ScheduleDAG subclass for scheduling lists of
/// MachineInstrs.
class ScheduleDAGInstrs : public ScheduleDAG {
protected:
- const MachineLoopInfo &MLI;
- const MachineDominatorTree &MDT;
+ const MachineLoopInfo *MLI;
const MachineFrameInfo *MFI;
/// Live Intervals provides reaching defs in preRA scheduling.
/// isPostRA flag indicates vregs cannot be present.
bool IsPostRA;
- /// UnitLatencies (misnamed) flag avoids computing def-use latencies, using
- /// the def-side latency only.
- bool UnitLatencies;
+ /// True if the DAG builder should remove kill flags (in preparation for
+ /// rescheduling).
+ bool RemoveKillFlags;
/// The standard DAG builder does not normally include terminators as DAG
/// nodes because it does not create the necessary dependencies to prevent
- /// reordering. A specialized scheduler can overide
+ /// reordering. A specialized scheduler can override
/// TargetInstrInfo::isSchedulingBoundary then enable this flag to indicate
/// it has taken responsibility for scheduling the terminator correctly.
bool CanHandleTerminators;
/// The end of the range to be scheduled.
MachineBasicBlock::iterator RegionEnd;
- /// The index in BB of RegionEnd.
- unsigned EndIndex;
+ /// Instructions in this region (distance(RegionBegin, RegionEnd)).
+ unsigned NumRegionInstrs;
/// After calling BuildSchedGraph, each machine instruction in the current
/// scheduling region is mapped to an SUnit.
DenseMap<MachineInstr*, SUnit*> MISUnitMap;
+ /// After calling BuildSchedGraph, each vreg used in the scheduling region
+ /// is mapped to a set of SUnits. These include all local vreg uses, not
+ /// just the uses for a singly defined vreg.
+ VReg2UseMap VRegUses;
+
/// State internal to DAG building.
/// -------------------------------
Reg2SUnitsMap Defs;
Reg2SUnitsMap Uses;
- /// Track the last instructon in this region defining each virtual register.
+ /// Track the last instruction in this region defining each virtual register.
VReg2SUnitMap VRegDefs;
/// PendingLoads - Remember where unknown loads are after the most recent
DbgValueVector DbgValues;
MachineInstr *FirstDbgValue;
+ /// Set of live physical registers for updating kill flags.
+ BitVector LiveRegs;
+
public:
explicit ScheduleDAGInstrs(MachineFunction &mf,
- const MachineLoopInfo &mli,
- const MachineDominatorTree &mdt,
+ const MachineLoopInfo *mli,
bool IsPostRAFlag,
- LiveIntervals *LIS = 0);
+ bool RemoveKillFlags = false,
+ LiveIntervals *LIS = nullptr);
virtual ~ScheduleDAGInstrs() {}
+ bool isPostRA() const { return IsPostRA; }
+
+ /// \brief Expose LiveIntervals for use in DAG mutators and such.
+ LiveIntervals *getLIS() const { return LIS; }
+
/// \brief Get the machine model for instruction scheduling.
const TargetSchedModel *getSchedModel() const { return &SchedModel; }
/// \brief Resolve and cache a resolved scheduling class for an SUnit.
const MCSchedClassDesc *getSchedClass(SUnit *SU) const {
- if (!SU->SchedClass)
+ if (!SU->SchedClass && SchedModel.hasInstrSchedModel())
SU->SchedClass = SchedModel.resolveSchedClass(SU->getInstr());
return SU->SchedClass;
}
virtual void enterRegion(MachineBasicBlock *bb,
MachineBasicBlock::iterator begin,
MachineBasicBlock::iterator end,
- unsigned endcount);
+ unsigned regioninstrs);
/// Notify that the scheduler has finished scheduling the current region.
virtual void exitRegion();
/// buildSchedGraph - Build SUnits from the MachineBasicBlock that we are
/// input.
- void buildSchedGraph(AliasAnalysis *AA, RegPressureTracker *RPTracker = 0);
+ void buildSchedGraph(AliasAnalysis *AA,
+ RegPressureTracker *RPTracker = nullptr,
+ PressureDiffs *PDiffs = nullptr);
/// addSchedBarrierDeps - Add dependencies from instructions in the current
/// list of instructions being scheduled to scheduling barrier. We want to
/// the level of the whole MachineFunction. By default does nothing.
virtual void finalizeSchedule() {}
- virtual void dumpNode(const SUnit *SU) const;
+ void dumpNode(const SUnit *SU) const override;
/// Return a label for a DAG node that points to an instruction.
- virtual std::string getGraphNodeLabel(const SUnit *SU) const;
+ std::string getGraphNodeLabel(const SUnit *SU) const override;
/// Return a label for the region of code covered by the DAG.
- virtual std::string getDAGName() const;
+ std::string getDAGName() const override;
+ /// \brief Fix register kill flags that scheduling has made invalid.
+ void fixupKills(MachineBasicBlock *MBB);
protected:
void initSUnits();
void addPhysRegDataDeps(SUnit *SU, unsigned OperIdx);
void addPhysRegDeps(SUnit *SU, unsigned OperIdx);
void addVRegDefDeps(SUnit *SU, unsigned OperIdx);
void addVRegUseDeps(SUnit *SU, unsigned OperIdx);
+
+ /// \brief PostRA helper for rewriting kill flags.
+ void startBlockForKills(MachineBasicBlock *BB);
+
+ /// \brief Toggle a register operand kill flag.
+ ///
+ /// Other adjustments may be made to the instruction if necessary. Return
+ /// true if the operand has been deleted, false if not.
+ bool toggleKillFlag(MachineInstr *MI, MachineOperand &MO);
};
/// newSUnit - Creates a new SUnit and return a ptr to it.
inline SUnit *ScheduleDAGInstrs::newSUnit(MachineInstr *MI) {
#ifndef NDEBUG
- const SUnit *Addr = SUnits.empty() ? 0 : &SUnits[0];
+ const SUnit *Addr = SUnits.empty() ? nullptr : &SUnits[0];
#endif
SUnits.push_back(SUnit(MI, (unsigned)SUnits.size()));
- assert((Addr == 0 || Addr == &SUnits[0]) &&
+ assert((Addr == nullptr || Addr == &SUnits[0]) &&
"SUnits std::vector reallocated on the fly!");
SUnits.back().OrigNode = &SUnits.back();
return &SUnits.back();
inline SUnit *ScheduleDAGInstrs::getSUnit(MachineInstr *MI) const {
DenseMap<MachineInstr*, SUnit*>::const_iterator I = MISUnitMap.find(MI);
if (I == MISUnitMap.end())
- return 0;
+ return nullptr;
return I->second;
}
} // namespace llvm