/usr/include/llvm-3.9/llvm/CodeGen/ScheduleDAGInstrs.h is in llvm-3.9-dev 1:3.9.1-19ubuntu1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 | //==- ScheduleDAGInstrs.h - MachineInstr Scheduling --------------*- C++ -*-==//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements the ScheduleDAGInstrs class, which implements
// scheduling for a MachineInstr-based dependency graph.
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_CODEGEN_SCHEDULEDAGINSTRS_H
#define LLVM_CODEGEN_SCHEDULEDAGINSTRS_H
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/SparseMultiSet.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 <list>
namespace llvm {
class MachineFrameInfo;
class MachineLoopInfo;
class MachineDominatorTree;
class RegPressureTracker;
class PressureDiffs;
/// An individual mapping from virtual register number to SUnit.
struct VReg2SUnit {
unsigned VirtReg;
LaneBitmask LaneMask;
SUnit *SU;
VReg2SUnit(unsigned VReg, LaneBitmask LaneMask, SUnit *SU)
: VirtReg(VReg), LaneMask(LaneMask), SU(SU) {}
unsigned getSparseSetIndex() const {
return TargetRegisterInfo::virtReg2Index(VirtReg);
}
};
/// Mapping from virtual register to SUnit including an operand index.
struct VReg2SUnitOperIdx : public VReg2SUnit {
unsigned OperandIndex;
VReg2SUnitOperIdx(unsigned VReg, LaneBitmask LaneMask,
unsigned OperandIndex, SUnit *SU)
: VReg2SUnit(VReg, LaneMask, SU), OperandIndex(OperandIndex) {}
};
/// Record a physical register access.
/// For non-data-dependent uses, OpIdx == -1.
struct PhysRegSUOper {
SUnit *SU;
int OpIdx;
unsigned Reg;
PhysRegSUOper(SUnit *su, int op, unsigned R): SU(su), OpIdx(op), Reg(R) {}
unsigned getSparseSetIndex() const { return Reg; }
};
/// 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;
/// 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
/// between scheduling regions in constant time as long as ValueT does not
/// 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> VReg2SUnitMultiMap;
typedef SparseMultiSet<VReg2SUnitOperIdx, VirtReg2IndexFunctor>
VReg2SUnitOperIdxMultiMap;
typedef PointerUnion<const Value *, const PseudoSourceValue *> ValueType;
struct UnderlyingObject : PointerIntPair<ValueType, 1, bool> {
UnderlyingObject(ValueType V, bool MayAlias)
: PointerIntPair<ValueType, 1, bool>(V, MayAlias) {}
ValueType getValue() const { return getPointer(); }
bool mayAlias() const { return getInt(); }
};
typedef SmallVector<UnderlyingObject, 4> UnderlyingObjectsVector;
/// ScheduleDAGInstrs - A ScheduleDAG subclass for scheduling lists of
/// MachineInstrs.
class ScheduleDAGInstrs : public ScheduleDAG {
protected:
const MachineLoopInfo *MLI;
const MachineFrameInfo *MFI;
/// TargetSchedModel provides an interface to the machine model.
TargetSchedModel SchedModel;
/// 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 override
/// TargetInstrInfo::isSchedulingBoundary then enable this flag to indicate
/// it has taken responsibility for scheduling the terminator correctly.
bool CanHandleTerminators;
/// Whether lane masks should get tracked.
bool TrackLaneMasks;
/// State specific to the current scheduling region.
/// ------------------------------------------------
/// The block in which to insert instructions
MachineBasicBlock *BB;
/// The beginning of the range to be scheduled.
MachineBasicBlock::iterator RegionBegin;
/// The end of the range to be scheduled.
MachineBasicBlock::iterator RegionEnd;
/// 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.
VReg2SUnitMultiMap VRegUses;
/// State internal to DAG building.
/// -------------------------------
/// Defs, Uses - Remember where defs and uses of each register are as we
/// iterate upward through the instructions. This is allocated here instead
/// of inside BuildSchedGraph to avoid the need for it to be initialized and
/// destructed for each block.
Reg2SUnitsMap Defs;
Reg2SUnitsMap Uses;
/// Tracks the last instruction(s) in this region defining each virtual
/// register. There may be multiple current definitions for a register with
/// disjunct lanemasks.
VReg2SUnitMultiMap CurrentVRegDefs;
/// Tracks the last instructions in this region using each virtual register.
VReg2SUnitOperIdxMultiMap CurrentVRegUses;
AliasAnalysis *AAForDep;
/// Remember a generic side-effecting instruction as we proceed.
/// No other SU ever gets scheduled around it (except in the special
/// case of a huge region that gets reduced).
SUnit *BarrierChain;
public:
/// A list of SUnits, used in Value2SUsMap, during DAG construction.
/// Note: to gain speed it might be worth investigating an optimized
/// implementation of this data structure, such as a singly linked list
/// with a memory pool (SmallVector was tried but slow and SparseSet is not
/// applicable).
typedef std::list<SUnit *> SUList;
protected:
/// A map from ValueType to SUList, used during DAG construction,
/// as a means of remembering which SUs depend on which memory
/// locations.
class Value2SUsMap;
/// Remove in FIFO order some SUs from huge maps.
void reduceHugeMemNodeMaps(Value2SUsMap &stores,
Value2SUsMap &loads, unsigned N);
/// Add a chain edge between SUa and SUb, but only if both AliasAnalysis
/// and Target fail to deny the dependency.
void addChainDependency(SUnit *SUa, SUnit *SUb,
unsigned Latency = 0);
/// Add dependencies as needed from all SUs in list to SU.
void addChainDependencies(SUnit *SU, SUList &sus, unsigned Latency) {
for (auto *su : sus)
addChainDependency(SU, su, Latency);
}
/// Add dependencies as needed from all SUs in map, to SU.
void addChainDependencies(SUnit *SU, Value2SUsMap &Val2SUsMap);
/// Add dependencies as needed to SU, from all SUs mapped to V.
void addChainDependencies(SUnit *SU, Value2SUsMap &Val2SUsMap,
ValueType V);
/// Add barrier chain edges from all SUs in map, and then clear
/// the map. This is equivalent to insertBarrierChain(), but
/// optimized for the common case where the new BarrierChain (a
/// global memory object) has a higher NodeNum than all SUs in
/// map. It is assumed BarrierChain has been set before calling
/// this.
void addBarrierChain(Value2SUsMap &map);
/// Insert a barrier chain in a huge region, far below current
/// SU. Add barrier chain edges from all SUs in map with higher
/// NodeNums than this new BarrierChain, and remove them from
/// map. It is assumed BarrierChain has been set before calling
/// this.
void insertBarrierChain(Value2SUsMap &map);
/// For an unanalyzable memory access, this Value is used in maps.
UndefValue *UnknownValue;
/// DbgValues - Remember instruction that precedes DBG_VALUE.
/// These are generated by buildSchedGraph but persist so they can be
/// referenced when emitting the final schedule.
typedef std::vector<std::pair<MachineInstr *, MachineInstr *> >
DbgValueVector;
DbgValueVector DbgValues;
MachineInstr *FirstDbgValue;
/// Set of live physical registers for updating kill flags.
BitVector LiveRegs;
public:
explicit ScheduleDAGInstrs(MachineFunction &mf,
const MachineLoopInfo *mli,
bool RemoveKillFlags = false);
~ScheduleDAGInstrs() override {}
/// \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 && SchedModel.hasInstrSchedModel())
SU->SchedClass = SchedModel.resolveSchedClass(SU->getInstr());
return SU->SchedClass;
}
/// begin - Return an iterator to the top of the current scheduling region.
MachineBasicBlock::iterator begin() const { return RegionBegin; }
/// end - Return an iterator to the bottom of the current scheduling region.
MachineBasicBlock::iterator end() const { return RegionEnd; }
/// newSUnit - Creates a new SUnit and return a ptr to it.
SUnit *newSUnit(MachineInstr *MI);
/// getSUnit - Return an existing SUnit for this MI, or NULL.
SUnit *getSUnit(MachineInstr *MI) const;
/// startBlock - Prepare to perform scheduling in the given block.
virtual void startBlock(MachineBasicBlock *BB);
/// finishBlock - Clean up after scheduling in the given block.
virtual void finishBlock();
/// Initialize the scheduler state for the next scheduling region.
virtual void enterRegion(MachineBasicBlock *bb,
MachineBasicBlock::iterator begin,
MachineBasicBlock::iterator end,
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 = nullptr,
PressureDiffs *PDiffs = nullptr,
LiveIntervals *LIS = nullptr,
bool TrackLaneMasks = false);
/// addSchedBarrierDeps - Add dependencies from instructions in the current
/// list of instructions being scheduled to scheduling barrier. We want to
/// make sure instructions which define registers that are either used by
/// the terminator or are live-out are properly scheduled. This is
/// especially important when the definition latency of the return value(s)
/// are too high to be hidden by the branch or when the liveout registers
/// used by instructions in the fallthrough block.
void addSchedBarrierDeps();
/// schedule - Order nodes according to selected style, filling
/// in the Sequence member.
///
/// Typically, a scheduling algorithm will implement schedule() without
/// overriding enterRegion() or exitRegion().
virtual void schedule() = 0;
/// finalizeSchedule - Allow targets to perform final scheduling actions at
/// the level of the whole MachineFunction. By default does nothing.
virtual void finalizeSchedule() {}
void dumpNode(const SUnit *SU) const override;
/// Return a label for a DAG node that points to an instruction.
std::string getGraphNodeLabel(const SUnit *SU) const override;
/// Return a label for the region of code covered by the DAG.
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);
/// Returns a mask for which lanes get read/written by the given (register)
/// machine operand.
LaneBitmask getLaneMaskForMO(const MachineOperand &MO) const;
void collectVRegUses(SUnit *SU);
};
/// newSUnit - Creates a new SUnit and return a ptr to it.
inline SUnit *ScheduleDAGInstrs::newSUnit(MachineInstr *MI) {
#ifndef NDEBUG
const SUnit *Addr = SUnits.empty() ? nullptr : &SUnits[0];
#endif
SUnits.emplace_back(MI, (unsigned)SUnits.size());
assert((Addr == nullptr || Addr == &SUnits[0]) &&
"SUnits std::vector reallocated on the fly!");
SUnits.back().OrigNode = &SUnits.back();
return &SUnits.back();
}
/// getSUnit - Return an existing SUnit for this MI, or NULL.
inline SUnit *ScheduleDAGInstrs::getSUnit(MachineInstr *MI) const {
DenseMap<MachineInstr*, SUnit*>::const_iterator I = MISUnitMap.find(MI);
if (I == MISUnitMap.end())
return nullptr;
return I->second;
}
} // namespace llvm
#endif
|