ModuloSchedule.h Source File (original) (raw)

60#ifndef LLVM_CODEGEN_MODULOSCHEDULE_H

61#define LLVM_CODEGEN_MODULOSCHEDULE_H

67#include

68#include

69#include

71namespace llvm {

81private:

88 std::vector<MachineInstr *> ScheduledInstrs;

97 int NumStages;

99public:

100

101

102

103

104

105

106

108 std::vector<MachineInstr *> ScheduledInstrs,

111 : Loop(Loop), ScheduledInstrs(ScheduledInstrs), Cycle(std::move(Cycle)),

112 Stage(std::move(Stage)) {

113 NumStages = 0;

114 for (auto &KV : this->Stage)

115 NumStages = std::max(NumStages, KV.second);

116 ++NumStages;

117 }

118

119

121

122

123

125

126

127

128 int getFirstCycle() { return Cycle[ScheduledInstrs.front()]; }

129

130

131

132 int getFinalCycle() { return Cycle[ScheduledInstrs.back()]; }

133

134

136 auto I = Stage.find(MI);

137 return I == Stage.end() ? -1 : I->second;

138 }

139

140

142 auto I = Cycle.find(MI);

143 return I == Cycle.end() ? -1 : I->second;

144 }

145

146

148 assert(Stage.count(MI) == 0);

149 Stage[MI] = MIStage;

150 }

151

152

154

157};

158

159

160

162public:

164

165private:

169

176

180 std::unique_ptrTargetInstrInfo::PipelinerLoopInfo LoopInfo;

181

182

183

184

185

186 std::map<Register, std::pair<unsigned, bool>> RegToStageDiff;

187

188

190

191 void generatePipelinedLoop();

192 void generateProlog(unsigned LastStage, MachineBasicBlock *KernelBB,

193 ValueMapTy *VRMap, MBBVectorTy &PrologBBs);

194 void generateEpilog(unsigned LastStage, MachineBasicBlock *KernelBB,

196 ValueMapTy *VRMapPhi, MBBVectorTy &EpilogBBs,

197 MBBVectorTy &PrologBBs);

200 ValueMapTy *VRMap, InstrMapTy &InstrMap,

201 unsigned LastStageNum, unsigned CurStageNum,

202 bool IsLast);

205 ValueMapTy *VRMap, ValueMapTy *VRMapPhi,

206 InstrMapTy &InstrMap, unsigned LastStageNum,

207 unsigned CurStageNum, bool IsLast);

209 MBBVectorTy &EpilogBBs);

210 void splitLifetimes(MachineBasicBlock *KernelBB, MBBVectorTy &EpilogBBs);

211 void addBranches(MachineBasicBlock &PreheaderBB, MBBVectorTy &PrologBBs,

213 ValueMapTy *VRMap);

214 bool computeDelta(MachineInstr &MI, unsigned &Delta);

216 unsigned Num);

218 unsigned InstStageNum);

220 unsigned InstStageNum);

221 void updateInstruction(MachineInstr *NewMI, bool LastDef,

222 unsigned CurStageNum, unsigned InstrStageNum,

223 ValueMapTy *VRMap);

225 Register getPrevMapVal(unsigned StageNum, unsigned PhiStage, Register LoopVal,

226 unsigned LoopStage, ValueMapTy *VRMap,

228 void rewritePhiValues(MachineBasicBlock *NewBB, unsigned StageNum,

229 ValueMapTy *VRMap, InstrMapTy &InstrMap);

230 void rewriteScheduledInstr(MachineBasicBlock *BB, InstrMapTy &InstrMap,

231 unsigned CurStageNum, unsigned PhiNum,

235

236

237

238 unsigned getStagesForReg(Register Reg, unsigned CurStage) {

239 std::pair<unsigned, bool> Stages = RegToStageDiff[Reg];

240 if ((int)CurStage > Schedule.getNumStages() - 1 && Stages.first == 0 &&

241 Stages.second)

242 return 1;

243 return Stages.first;

244 }

245

246

247

248

249

250

251

253 std::pair<unsigned, bool> Stages = RegToStageDiff[Reg];

254 if (Stages.second)

255 return Stages.first;

256 return Stages.first - 1;

257 }

258

259public:

260

261

262

263

264

267 : Schedule(S), MF(MF), ST(MF.getSubtarget()), MRI(MF.getRegInfo()),

268 TII(ST.getInstrInfo()), LIS(LIS),

269 InstrChanges(std::move(InstrChanges)) {}

270

271

273

275

276

277

279};

280

281

282

284public:

289

291

292

293

295

296protected:

303

304

306

308

310

312

313

314

316

317

319

320

321

325

326

328

330

331

332

334

335

336

338

339

341

342

345

346

348

349

351

352

354

356

357

358

360

363 MI = It->second;

365 }

366

367

369

370 std::unique_ptrTargetInstrInfo::PipelinerLoopInfo LoopInfo;

371};

372

373

374

376private:

380

387

397 std::unique_ptrTargetInstrInfo::PipelinerLoopInfo LoopInfo;

398

399

400

401 int NumUnroll;

402

403 void calcNumUnroll();

404 void generatePipelinedLoop();

406 void generatePhi(MachineInstr *OrigMI, int UnrollNum,

412 InstrMapTy &LastStage0Insts);

415 InstrMapTy &LastStage0Insts);

416 void mergeRegUsesAfterPipeline(Register OrigReg, Register NewReg);

417

419

420 void updateInstrDef(MachineInstr *NewMI, ValueMapTy &VRMap, bool LastDef);

421

422 void generateKernelPhi(Register OrigLoopVal, Register NewLoopVal,

423 unsigned UnrollNum,

426 void updateInstrUse(MachineInstr *MI, int StageNum, int PhaseNum,

429

431 InstrMapTy &LastStage0Insts,

434

435public:

438 : Schedule(S), MF(MF), ST(MF.getSubtarget()), MRI(MF.getRegInfo()),

439 TII(ST.getInstrInfo()), LIS(LIS) {}

440

443};

444

445

446

447

448

449

450

454

455public:

458

459

461};

462

463}

464

465#endif

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

Promote Memory to Register

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

Representation of each machine instruction.

MachineRegisterInfo - Keep track of information for virtual and physical registers,...

static bool canApply(MachineLoop &L)

Check if ModuloScheduleExpanderMVE can be applied to L.

ModuloScheduleExpanderMVE(MachineFunction &MF, ModuloSchedule &S, LiveIntervals &LIS)

Definition ModuloSchedule.h:436

MachineBasicBlock * getRewrittenKernel()

Returns the newly rewritten kernel block, or nullptr if this was optimized away.

Definition ModuloSchedule.h:278

void cleanup()

Performs final cleanup after expansion.

void expand()

Performs the actual expansion.

DenseMap< MachineInstr *, std::pair< Register, int64_t > > InstrChangesTy

Definition ModuloSchedule.h:163

ModuloScheduleExpander(MachineFunction &MF, ModuloSchedule &S, LiveIntervals &LIS, InstrChangesTy InstrChanges)

Create a new ModuloScheduleExpander.

Definition ModuloSchedule.h:265

void annotate()

Performs the annotation.

ModuloScheduleTestAnnotater(MachineFunction &MF, ModuloSchedule &S)

Definition ModuloSchedule.h:456

Represents a schedule for a single-block loop.

Definition ModuloSchedule.h:80

int getNumStages() const

Return the number of stages contained in this schedule, which is the largest stage index + 1.

Definition ModuloSchedule.h:124

MachineLoop * getLoop() const

Return the single-block loop being scheduled.

Definition ModuloSchedule.h:120

ArrayRef< MachineInstr * > getInstructions()

Return the rescheduled instructions in order.

Definition ModuloSchedule.h:153

void print(raw_ostream &OS)

int getCycle(MachineInstr *MI)

Return the cycle that MI is scheduled at, or -1.

Definition ModuloSchedule.h:141

void setStage(MachineInstr *MI, int MIStage)

Set the stage of a newly created instruction.

Definition ModuloSchedule.h:147

int getStage(MachineInstr *MI)

Return the stage that MI is scheduled in, or -1.

Definition ModuloSchedule.h:135

void dump()

Definition ModuloSchedule.h:155

ModuloSchedule(MachineFunction &MF, MachineLoop *Loop, std::vector< MachineInstr * > ScheduledInstrs, DenseMap< MachineInstr *, int > Cycle, DenseMap< MachineInstr *, int > Stage)

Create a new ModuloSchedule.

Definition ModuloSchedule.h:107

int getFirstCycle()

Return the first cycle in the schedule, which is the cycle index of the first instruction.

Definition ModuloSchedule.h:128

int getFinalCycle()

Return the final cycle in the schedule, which is the cycle index of the last instruction.

Definition ModuloSchedule.h:132

MachineFunction & MF

Definition ModuloSchedule.h:298

const TargetSubtargetInfo & ST

Definition ModuloSchedule.h:299

std::deque< MachineBasicBlock * > PeeledBack

Definition ModuloSchedule.h:327

SmallVector< MachineInstr *, 4 > IllegalPhisToDelete

Illegal phis that need to be deleted once we re-link stages.

Definition ModuloSchedule.h:329

DenseMap< MachineInstr *, MachineInstr * > CanonicalMIs

CanonicalMIs and BlockMIs form a bidirectional map between any of the loop kernel clones.

Definition ModuloSchedule.h:322

SmallVector< MachineBasicBlock *, 4 > Prologs

All prolog and epilog blocks.

Definition ModuloSchedule.h:309

MachineBasicBlock * peelKernel(LoopPeelDirection LPD)

Peels one iteration of the rewritten kernel (BB) in the specified direction.

ModuloSchedule & Schedule

Definition ModuloSchedule.h:297

std::deque< MachineBasicBlock * > PeeledFront

State passed from peelKernel to peelPrologAndEpilogs().

Definition ModuloSchedule.h:327

unsigned getStage(MachineInstr *MI)

Helper to get the stage of an instruction in the schedule.

Definition ModuloSchedule.h:361

void rewriteUsesOf(MachineInstr *MI)

Change all users of MI, if MI is predicated out (LiveStages[MI->getParent()] == false).

SmallVector< MachineBasicBlock *, 4 > Epilogs

Definition ModuloSchedule.h:309

DenseMap< MachineBasicBlock *, BitVector > AvailableStages

For every block, the stages that are available.

Definition ModuloSchedule.h:315

std::unique_ptr< TargetInstrInfo::PipelinerLoopInfo > LoopInfo

Target loop info before kernel peeling.

Definition ModuloSchedule.h:370

DenseMap< std::pair< MachineBasicBlock *, MachineInstr * >, MachineInstr * > BlockMIs

Definition ModuloSchedule.h:324

All prolog and epilog blocks are clones of the kernel, so any produced register in one block has an c...

MachineBasicBlock * Preheader

The original loop preheader.

Definition ModuloSchedule.h:307

PeelingModuloScheduleExpander(MachineFunction &MF, ModuloSchedule &S, LiveIntervals *LIS)

Definition ModuloSchedule.h:285

void rewriteKernel()

Converts BB from the original loop body to the rewritten, pipelined steady-state.

DenseMap< MachineInstr *, unsigned > PhiNodeLoopIteration

When peeling the epilogue keep track of the distance between the phi nodes and the kernel.

Definition ModuloSchedule.h:318

DenseMap< MachineBasicBlock *, BitVector > LiveStages

For every block, the stages that are produced.

Definition ModuloSchedule.h:311

const TargetInstrInfo * TII

Definition ModuloSchedule.h:301

void filterInstructions(MachineBasicBlock *MB, int MinStage)

void peelPrologAndEpilogs()

Peel the kernel forwards and backwards to produce prologs and epilogs, and stitch them together.

MachineBasicBlock * BB

The original loop block that gets rewritten in-place.

Definition ModuloSchedule.h:305

void fixupBranches()

Insert branches between prologs, kernel and epilogs.

LiveIntervals * LIS

Definition ModuloSchedule.h:302

MachineBasicBlock * CreateLCSSAExitingBlock()

Create a poor-man's LCSSA by cloning only the PHIs from the kernel block to a block dominated by all ...

void validateAgainstModuloScheduleExpander()

Runs ModuloScheduleExpander and treats it as a golden input to validate aspects of the code generated...

Helper function to find the right canonical register for a phi instruction coming from a peeled out p...

MachineRegisterInfo & MRI

Definition ModuloSchedule.h:300

void moveStageBetweenBlocks(MachineBasicBlock *DestBB, MachineBasicBlock *SourceBB, unsigned Stage)

Wrapper class representing virtual and physical registers.

This class consists of common code factored out of the SmallVector class to reduce code duplication b...

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

TargetInstrInfo - Interface to description of machine instruction set.

TargetSubtargetInfo - Generic base class for all target subtargets.

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

This is an optimization pass for GlobalISel generic memory operations.

LLVM_ABI raw_ostream & dbgs()

dbgs() - This returns a reference to a raw_ostream for debugging messages.

OutputIt move(R &&Range, OutputIt Out)

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

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