Scheduler.h Source File (original) (raw)

21#ifndef LLVM_TRANSFORMS_VECTORIZE_SANDBOXVECTORIZER_SCHEDULER_H

22#define LLVM_TRANSFORMS_VECTORIZE_SANDBOXVECTORIZER_SCHEDULER_H

27#include

32public:

39 bool IsTerm1 = I1->isTerminator();

40 bool IsTerm2 = I2->isTerminator();

41 if (IsTerm1 != IsTerm2)

43 return IsTerm1 > IsTerm2;

46 if (IsPHI1 != IsPHI2)

48 return IsPHI1 < IsPHI2;

50 return I2->comesBefore(I1);

51 }

52};

61 std::priority_queue<DGNode *, std::vector<DGNode *>, PriorityCmp> List;

63public:

66#ifndef NDEBUG

67 assert(->scheduled() && "Don't insert a scheduled node!");

68 auto ListCopy = List;

69 while (!ListCopy.empty()) {

70 DGNode *Top = ListCopy.top();

71 ListCopy.pop();

72 assert(Top != N && "Node already exists in ready list!");

73 }

74#endif

75 List.push(N);

76 }

78 auto *Back = List.top();

79 List.pop();

80 return Back;

81 }

82 bool empty() const { return List.empty(); }

83 void clear() { List = {}; }

89 Keep.reserve(List.size());

90 while (!List.empty()) {

91 auto *Top = List.top();

92 List.pop();

93 if (Top == N)

94 break;

95 Keep.push_back(Top);

96 }

97 for (auto *KeepN : Keep)

98 List.push(KeepN);

99 }

100#ifndef NDEBUG

103#endif

104};

105

106

107

109public:

111

112private:

114

115

119

120public:

123 for (auto *N : this->Nodes)

124 N->setSchedBundle(*this);

125 }

126

128

131 for (auto *N : this->Nodes)

132 N->clearSchedBundle();

133 }

134 bool empty() const { return Nodes.empty(); }

135

136

137

138 bool isSingleton() const { return Nodes.size() == 1u; }

146

148

150

152

154 return all_of(Nodes, [](const auto *N) { return N->ready(); });

155 }

156#ifndef NDEBUG

159#endif

160};

161

162

163class Scheduler {

164

165

166

168

169

173

174

175

176 std::optionalBasicBlock::iterator ScheduleTopItOpt;

177

179

181

182 std::optionalContext::CallbackID CreateInstrCB;

183

184

185

187

188

191

193

194

195

196 void scheduleAndUpdateReadyList(SchedBundle &Bndl);

197

198 enum class BndlSchedState {

199 NoneScheduled,

200 AlreadyScheduled,

201

202 TemporarilyScheduled,

203

204

205

206 FullyScheduled,

207

208 };

209

212

214

217

218public:

220

221

222 CreateInstrCB = Ctx.registerCreateInstrCallback(

223 [this](Instruction *I) { notifyCreateInstr(I); });

224 }

226 if (CreateInstrCB)

227 Ctx.unregisterCreateInstrCallback(*CreateInstrCB);

228 }

229

230

231

232

233

235

237 Bndls.clear();

238

239 DAG.clear();

240 ReadyList.clear();

241 ScheduleTopItOpt = std::nullopt;

242 ScheduledBB = nullptr;

243 assert(Bndls.empty() && DAG.empty() && ReadyList.empty() &&

244 !ScheduleTopItOpt && ScheduledBB == nullptr &&

245 "Expected empty state!");

246 }

247

248#ifndef NDEBUG

251#endif

252};

253

254

255

257public:

262 return Sched.getBndlSchedState(Instrs);

263 }

264};

265

266}

267

268#endif

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

#define LLVM_DUMP_METHOD

Mark debug helper function definitions like dump() that should not be stripped from debug builds.

Machine Instruction Scheduler

ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...

InstListType::iterator iterator

Instruction iterators...

This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.

This class implements an extremely fast bulk output stream that can only output to a stream.

A DependencyGraph Node that points to an Instruction and contains memory dependency edges.

void setSchedBundle(SchedBundle &SB)

Instruction * getInstruction() const

A sandboxir::User with operands, opcode and linked with previous/next instructions in an instruction ...

Definition Scheduler.h:31

bool operator()(const DGNode *N1, const DGNode *N2)

Definition Scheduler.h:33

The list holding nodes that are ready to schedule. Used by the scheduler.

Definition Scheduler.h:55

LLVM_DUMP_METHOD void dump() const

void remove(DGNode *N)

\Removes N if found in the ready list.

Definition Scheduler.h:85

bool empty() const

Definition Scheduler.h:82

DGNode * pop()

Definition Scheduler.h:77

void clear()

Definition Scheduler.h:83

void insert(DGNode *N)

Definition Scheduler.h:65

ReadyListContainer()

Definition Scheduler.h:64

The nodes that need to be scheduled back-to-back in a single scheduling cycle form a SchedBundle.

Definition Scheduler.h:108

LLVM_ABI DGNode * getBot() const

\Returns the bundle node that comes after the others in program order.

SchedBundle(ContainerTy &&Nodes)

Definition Scheduler.h:122

SchedBundle & operator=(const SchedBundle &Other)=delete

Copy Assignment (unimplemented).

LLVM_ABI DGNode * getTop() const

\Returns the bundle node that comes before the others in program order.

iterator end()

Definition Scheduler.h:143

iterator begin()

Definition Scheduler.h:142

bool isSingleton() const

Singleton bundles are created when scheduling instructions temporarily to fill in the schedule until ...

Definition Scheduler.h:138

bool ready() const

\Returns true if all nodes in the bundle are ready.

Definition Scheduler.h:153

~SchedBundle()

Definition Scheduler.h:130

SmallVector< DGNode *, 4 > ContainerTy

Definition Scheduler.h:110

const_iterator begin() const

Definition Scheduler.h:144

LLVM_DUMP_METHOD void dump() const

SchedBundle(const SchedBundle &Other)=delete

Copy CTOR (unimplemented).

DGNode * back() const

Definition Scheduler.h:139

ContainerTy::iterator iterator

Definition Scheduler.h:140

const_iterator end() const

Definition Scheduler.h:145

ContainerTy::const_iterator const_iterator

Definition Scheduler.h:141

bool empty() const

Definition Scheduler.h:134

LLVM_ABI void cluster(BasicBlock::iterator Where)

Move all bundle instructions to Where back-to-back.

A client-attorney class for accessing the Scheduler's internals (used for unit tests).

Definition Scheduler.h:256

static BndlSchedState getBndlSchedState(const Scheduler &Sched, ArrayRef< Instruction * > Instrs)

Definition Scheduler.h:260

Scheduler::BndlSchedState BndlSchedState

Definition Scheduler.h:259

static DependencyGraph & getDAG(Scheduler &Sched)

Definition Scheduler.h:258

The list scheduler.

Definition Scheduler.h:163

friend class SchedulerInternalsAttorney

Definition Scheduler.h:171

LLVM_DUMP_METHOD void dump() const

LLVM_ABI bool trySchedule(ArrayRef< Instruction * > Instrs)

Tries to build a schedule that includes all of Instrs scheduled at the same scheduling cycle.

void clear()

Clear the scheduler's state, including the DAG.

Definition Scheduler.h:236

~Scheduler()

Definition Scheduler.h:225

Scheduler(AAResults &AA, Context &Ctx)

Definition Scheduler.h:219

Abstract Attribute helper functions.

BasicBlock(llvm::BasicBlock *BB, Context &SBCtx)

bool all_of(R &&range, UnaryPredicate P)

Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.

void erase(Container &C, ValueType V)

Wrapper function to remove a value from a container:

bool isa(const From &Val)

isa - Return true if the parameter to the template is an instance of one of the template type argu...

OutputIt move(R &&Range, OutputIt Out)

Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.

@ Keep

No function return thunk.

Implement std::hash so that hash_code can be used in STL containers.