Movatterモバイル変換

Go to the documentation of this file.

1//===- ModuloSchedule.cpp - Software pipeline schedule expansion ----------===//

2//

3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

4// See https://llvm.org/LICENSE.txt for license information.

5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

6//

7//===----------------------------------------------------------------------===//

9#include "llvm/CodeGen/ModuloSchedule.h"

10#include "llvm/ADT/StringExtras.h"

11#include "llvm/Analysis/MemoryLocation.h"

12#include "llvm/CodeGen/LiveIntervals.h"

13#include "llvm/CodeGen/MachineInstrBuilder.h"

14#include "llvm/CodeGen/MachineLoopInfo.h"

15#include "llvm/CodeGen/MachineRegisterInfo.h"

16#include "llvm/InitializePasses.h"

17#include "llvm/MC/MCContext.h"

18#include "llvm/Support/Debug.h"

19#include "llvm/Support/ErrorHandling.h"

20#include "llvm/Support/raw_ostream.h"

22#define DEBUG_TYPE "pipeliner"

23using namespacellvm;

25staticcl::opt<bool>SwapBranchTargetsMVE(

26"pipeliner-swap-branch-targets-mve",cl::Hidden,cl::init(false),

27cl::desc("Swap target blocks of a conditional branch for MVE expander"));

29voidModuloSchedule::print(raw_ostream &OS) {

30for (MachineInstr *MI : ScheduledInstrs)

31OS <<"[stage " <<getStage(MI) <<" @" <<getCycle(MI) <<"c] " << *MI;

32}

34//===----------------------------------------------------------------------===//

35// ModuloScheduleExpander implementation

36//===----------------------------------------------------------------------===//

38/// Return the register values for the operands of a Phi instruction.

39/// This function assume the instruction is a Phi.

40staticvoidgetPhiRegs(MachineInstr &Phi,MachineBasicBlock *Loop,

41unsigned &InitVal,unsigned &LoopVal) {

42assert(Phi.isPHI() &&"Expecting a Phi.");

44 InitVal = 0;

45 LoopVal = 0;

46for (unsigned i = 1, e = Phi.getNumOperands(); i != e; i += 2)

47if (Phi.getOperand(i + 1).getMBB() !=Loop)

48 InitVal = Phi.getOperand(i).getReg();

49else

50 LoopVal = Phi.getOperand(i).getReg();

52assert(InitVal != 0 && LoopVal != 0 &&"Unexpected Phi structure.");

53}

55/// Return the Phi register value that comes from the incoming block.

56staticunsignedgetInitPhiReg(MachineInstr &Phi,MachineBasicBlock *LoopBB) {

57for (unsigned i = 1, e = Phi.getNumOperands(); i != e; i += 2)

58if (Phi.getOperand(i + 1).getMBB() != LoopBB)

59return Phi.getOperand(i).getReg();

60return 0;

61}

63/// Return the Phi register value that comes the loop block.

64staticunsignedgetLoopPhiReg(MachineInstr &Phi,MachineBasicBlock *LoopBB) {

65for (unsigned i = 1, e = Phi.getNumOperands(); i != e; i += 2)

66if (Phi.getOperand(i + 1).getMBB() == LoopBB)

67return Phi.getOperand(i).getReg();

68return 0;

69}

71voidModuloScheduleExpander::expand() {

72 BB = Schedule.getLoop()->getTopBlock();

73 Preheader = *BB->pred_begin();

74if (Preheader == BB)

75 Preheader = *std::next(BB->pred_begin());

77// Iterate over the definitions in each instruction, and compute the

78// stage difference for each use. Keep the maximum value.

79for (MachineInstr *MI : Schedule.getInstructions()) {

80int DefStage = Schedule.getStage(MI);

81for (constMachineOperand &Op :MI->all_defs()) {

82Register Reg =Op.getReg();

83unsigned MaxDiff = 0;

84bool PhiIsSwapped =false;

85for (MachineOperand &UseOp : MRI.use_operands(Reg)) {

86MachineInstr *UseMI = UseOp.getParent();

87int UseStage = Schedule.getStage(UseMI);

88unsigned Diff = 0;

89if (UseStage != -1 && UseStage >= DefStage)

90 Diff = UseStage - DefStage;

91if (MI->isPHI()) {

92if (isLoopCarried(*MI))

93 ++Diff;

94else

95 PhiIsSwapped =true;

96 }

97 MaxDiff = std::max(Diff, MaxDiff);

98 }

99 RegToStageDiff[Reg] = std::make_pair(MaxDiff, PhiIsSwapped);

100 }

101 }

102

103 generatePipelinedLoop();

104}

105

106void ModuloScheduleExpander::generatePipelinedLoop() {

107LoopInfo = TII->analyzeLoopForPipelining(BB);

108assert(LoopInfo &&"Must be able to analyze loop!");

109

110// Create a new basic block for the kernel and add it to the CFG.

111MachineBasicBlock *KernelBB = MF.CreateMachineBasicBlock(BB->getBasicBlock());

112

113unsigned MaxStageCount = Schedule.getNumStages() - 1;

114

115// Remember the registers that are used in different stages. The index is

116// the iteration, or stage, that the instruction is scheduled in. This is

117// a map between register names in the original block and the names created

118// in each stage of the pipelined loop.

119 ValueMapTy *VRMap =new ValueMapTy[(MaxStageCount + 1) * 2];

120

121// The renaming destination by Phis for the registers across stages.

122// This map is updated during Phis generation to point to the most recent

123// renaming destination.

124 ValueMapTy *VRMapPhi =new ValueMapTy[(MaxStageCount + 1) * 2];

125

126 InstrMapTy InstrMap;

127

128SmallVector<MachineBasicBlock *, 4> PrologBBs;

129

130// Generate the prolog instructions that set up the pipeline.

131 generateProlog(MaxStageCount, KernelBB, VRMap, PrologBBs);

132 MF.insert(BB->getIterator(), KernelBB);

133 LIS.insertMBBInMaps(KernelBB);

134

135// Rearrange the instructions to generate the new, pipelined loop,

136// and update register names as needed.

137for (MachineInstr *CI : Schedule.getInstructions()) {

138if (CI->isPHI())

139continue;

140unsigned StageNum = Schedule.getStage(CI);

141MachineInstr *NewMI = cloneInstr(CI, MaxStageCount, StageNum);

142 updateInstruction(NewMI,false, MaxStageCount, StageNum, VRMap);

143 KernelBB->push_back(NewMI);

144 InstrMap[NewMI] = CI;

145 }

146

147// Copy any terminator instructions to the new kernel, and update

148// names as needed.

149for (MachineInstr &MI : BB->terminators()) {

150MachineInstr *NewMI = MF.CloneMachineInstr(&MI);

151 updateInstruction(NewMI,false, MaxStageCount, 0, VRMap);

152 KernelBB->push_back(NewMI);

153 InstrMap[NewMI] = &MI;

154 }

155

156 NewKernel = KernelBB;

157 KernelBB->transferSuccessors(BB);

158 KernelBB->replaceSuccessor(BB, KernelBB);

159

160 generateExistingPhis(KernelBB, PrologBBs.back(), KernelBB, KernelBB, VRMap,

161 InstrMap, MaxStageCount, MaxStageCount,false);

162 generatePhis(KernelBB, PrologBBs.back(), KernelBB, KernelBB, VRMap, VRMapPhi,

163 InstrMap, MaxStageCount, MaxStageCount,false);

164

165LLVM_DEBUG(dbgs() <<"New block\n"; KernelBB->dump(););

166

167SmallVector<MachineBasicBlock *, 4> EpilogBBs;

168// Generate the epilog instructions to complete the pipeline.

169 generateEpilog(MaxStageCount, KernelBB, BB, VRMap, VRMapPhi, EpilogBBs,

170 PrologBBs);

171

172// We need this step because the register allocation doesn't handle some

173// situations well, so we insert copies to help out.

174 splitLifetimes(KernelBB, EpilogBBs);

175

176// Remove dead instructions due to loop induction variables.

177 removeDeadInstructions(KernelBB, EpilogBBs);

178

179// Add branches between prolog and epilog blocks.

180 addBranches(*Preheader, PrologBBs, KernelBB, EpilogBBs, VRMap);

181

182delete[] VRMap;

183delete[] VRMapPhi;

184}

185

186voidModuloScheduleExpander::cleanup() {

187// Remove the original loop since it's no longer referenced.

188for (auto &I : *BB)

189 LIS.RemoveMachineInstrFromMaps(I);

190 BB->clear();

191 BB->eraseFromParent();

192}

193

194/// Generate the pipeline prolog code.

195void ModuloScheduleExpander::generateProlog(unsigned LastStage,

196MachineBasicBlock *KernelBB,

197 ValueMapTy *VRMap,

198 MBBVectorTy &PrologBBs) {

199MachineBasicBlock *PredBB = Preheader;

200 InstrMapTy InstrMap;

201

202// Generate a basic block for each stage, not including the last stage,

203// which will be generated in the kernel. Each basic block may contain

204// instructions from multiple stages/iterations.

205for (unsigned i = 0; i < LastStage; ++i) {

206// Create and insert the prolog basic block prior to the original loop

207// basic block. The original loop is removed later.

208MachineBasicBlock *NewBB = MF.CreateMachineBasicBlock(BB->getBasicBlock());

209 PrologBBs.push_back(NewBB);

210 MF.insert(BB->getIterator(), NewBB);

211 NewBB->transferSuccessors(PredBB);

212 PredBB->addSuccessor(NewBB);

213 PredBB = NewBB;

214 LIS.insertMBBInMaps(NewBB);

215

216// Generate instructions for each appropriate stage. Process instructions

217// in original program order.

218for (int StageNum = i; StageNum >= 0; --StageNum) {

219for (MachineBasicBlock::iterator BBI = BB->instr_begin(),

220 BBE = BB->getFirstTerminator();

221 BBI != BBE; ++BBI) {

222if (Schedule.getStage(&*BBI) == StageNum) {

223if (BBI->isPHI())

224continue;

225MachineInstr *NewMI =

226 cloneAndChangeInstr(&*BBI, i, (unsigned)StageNum);

227 updateInstruction(NewMI,false, i, (unsigned)StageNum, VRMap);

228 NewBB->push_back(NewMI);

229 InstrMap[NewMI] = &*BBI;

230 }

231 }

232 }

233 rewritePhiValues(NewBB, i, VRMap, InstrMap);

234LLVM_DEBUG({

235dbgs() <<"prolog:\n";

236 NewBB->dump();

237 });

238 }

239

240 PredBB->replaceSuccessor(BB, KernelBB);

241

242// Check if we need to remove the branch from the preheader to the original

243// loop, and replace it with a branch to the new loop.

244unsigned numBranches = TII->removeBranch(*Preheader);

245if (numBranches) {

246SmallVector<MachineOperand, 0>Cond;

247 TII->insertBranch(*Preheader, PrologBBs[0],nullptr,Cond,DebugLoc());

248 }

249}

250

251/// Generate the pipeline epilog code. The epilog code finishes the iterations

252/// that were started in either the prolog or the kernel. We create a basic

253/// block for each stage that needs to complete.

254void ModuloScheduleExpander::generateEpilog(

255unsigned LastStage,MachineBasicBlock *KernelBB,MachineBasicBlock *OrigBB,

256 ValueMapTy *VRMap, ValueMapTy *VRMapPhi, MBBVectorTy &EpilogBBs,

257 MBBVectorTy &PrologBBs) {

258// We need to change the branch from the kernel to the first epilog block, so

259// this call to analyze branch uses the kernel rather than the original BB.

260MachineBasicBlock *TBB =nullptr, *FBB =nullptr;

261SmallVector<MachineOperand, 4>Cond;

262bool checkBranch = TII->analyzeBranch(*KernelBB,TBB, FBB,Cond);

263assert(!checkBranch &&"generateEpilog must be able to analyze the branch");

264if (checkBranch)

265return;

266

267MachineBasicBlock::succ_iterator LoopExitI = KernelBB->succ_begin();

268if (*LoopExitI == KernelBB)

269 ++LoopExitI;

270assert(LoopExitI != KernelBB->succ_end() &&"Expecting a successor");

271MachineBasicBlock *LoopExitBB = *LoopExitI;

272

273MachineBasicBlock *PredBB = KernelBB;

274MachineBasicBlock *EpilogStart = LoopExitBB;

275 InstrMapTy InstrMap;

276

277// Generate a basic block for each stage, not including the last stage,

278// which was generated for the kernel. Each basic block may contain

279// instructions from multiple stages/iterations.

280int EpilogStage = LastStage + 1;

281for (unsigned i = LastStage; i >= 1; --i, ++EpilogStage) {

282MachineBasicBlock *NewBB = MF.CreateMachineBasicBlock();

283 EpilogBBs.push_back(NewBB);

284 MF.insert(BB->getIterator(), NewBB);

285

286 PredBB->replaceSuccessor(LoopExitBB, NewBB);

287 NewBB->addSuccessor(LoopExitBB);

288 LIS.insertMBBInMaps(NewBB);

289

290if (EpilogStart == LoopExitBB)

291 EpilogStart = NewBB;

292

293// Add instructions to the epilog depending on the current block.

294// Process instructions in original program order.

295for (unsigned StageNum = i; StageNum <= LastStage; ++StageNum) {

296for (auto &BBI : *BB) {

297if (BBI.isPHI())

298continue;

299MachineInstr *In = &BBI;

300if ((unsigned)Schedule.getStage(In) == StageNum) {

301// Instructions with memoperands in the epilog are updated with

302// conservative values.

303MachineInstr *NewMI = cloneInstr(In, UINT_MAX, 0);

304 updateInstruction(NewMI, i == 1, EpilogStage, 0, VRMap);

305 NewBB->push_back(NewMI);

306 InstrMap[NewMI] =In;

307 }

308 }

309 }

310 generateExistingPhis(NewBB, PrologBBs[i - 1], PredBB, KernelBB, VRMap,

311 InstrMap, LastStage, EpilogStage, i == 1);

312 generatePhis(NewBB, PrologBBs[i - 1], PredBB, KernelBB, VRMap, VRMapPhi,

313 InstrMap, LastStage, EpilogStage, i == 1);

314 PredBB = NewBB;

315

316LLVM_DEBUG({

317dbgs() <<"epilog:\n";

318 NewBB->dump();

319 });

320 }

321

322// Fix any Phi nodes in the loop exit block.

323 LoopExitBB->replacePhiUsesWith(BB, PredBB);

324

325// Create a branch to the new epilog from the kernel.

326// Remove the original branch and add a new branch to the epilog.

327 TII->removeBranch(*KernelBB);

328assert((OrigBB ==TBB || OrigBB == FBB) &&

329"Unable to determine looping branch direction");

330if (OrigBB !=TBB)

331 TII->insertBranch(*KernelBB, EpilogStart, KernelBB,Cond,DebugLoc());

332else

333 TII->insertBranch(*KernelBB, KernelBB, EpilogStart,Cond,DebugLoc());

334// Add a branch to the loop exit.

335if (EpilogBBs.size() > 0) {

336MachineBasicBlock *LastEpilogBB = EpilogBBs.back();

337SmallVector<MachineOperand, 4> Cond1;

338 TII->insertBranch(*LastEpilogBB, LoopExitBB,nullptr, Cond1,DebugLoc());

339 }

340}

341

342/// Replace all uses of FromReg that appear outside the specified

343/// basic block with ToReg.

344staticvoidreplaceRegUsesAfterLoop(unsigned FromReg,unsigned ToReg,

345MachineBasicBlock *MBB,

346MachineRegisterInfo &MRI,

347LiveIntervals &LIS) {

348for (MachineOperand &O :

349llvm::make_early_inc_range(MRI.use_operands(FromReg)))

350if (O.getParent()->getParent() !=MBB)

351 O.setReg(ToReg);

352if (!LIS.hasInterval(ToReg))

353 LIS.createEmptyInterval(ToReg);

354}

355

356/// Return true if the register has a use that occurs outside the

357/// specified loop.

358staticboolhasUseAfterLoop(unsigned Reg,MachineBasicBlock *BB,

359MachineRegisterInfo &MRI) {

360for (constMachineOperand &MO :MRI.use_operands(Reg))

361if (MO.getParent()->getParent() != BB)

362returntrue;

363returnfalse;

364}

365

366/// Generate Phis for the specific block in the generated pipelined code.

367/// This function looks at the Phis from the original code to guide the

368/// creation of new Phis.

369void ModuloScheduleExpander::generateExistingPhis(

370MachineBasicBlock *NewBB,MachineBasicBlock *BB1,MachineBasicBlock *BB2,

371MachineBasicBlock *KernelBB, ValueMapTy *VRMap, InstrMapTy &InstrMap,

372unsigned LastStageNum,unsigned CurStageNum,bool IsLast) {

373// Compute the stage number for the initial value of the Phi, which

374// comes from the prolog. The prolog to use depends on to which kernel/

375// epilog that we're adding the Phi.

376unsigned PrologStage = 0;

377unsigned PrevStage = 0;

378bool InKernel = (LastStageNum == CurStageNum);

379if (InKernel) {

380 PrologStage = LastStageNum - 1;

381 PrevStage = CurStageNum;

382 }else {

383 PrologStage = LastStageNum - (CurStageNum - LastStageNum);

384 PrevStage = LastStageNum + (CurStageNum - LastStageNum) - 1;

385 }

386

387for (MachineBasicBlock::iterator BBI = BB->instr_begin(),

388 BBE = BB->getFirstNonPHI();

389 BBI != BBE; ++BBI) {

390Register Def = BBI->getOperand(0).getReg();

391

392unsigned InitVal = 0;

393unsigned LoopVal = 0;

394getPhiRegs(*BBI, BB, InitVal, LoopVal);

395

396unsigned PhiOp1 = 0;

397// The Phi value from the loop body typically is defined in the loop, but

398// not always. So, we need to check if the value is defined in the loop.

399unsigned PhiOp2 = LoopVal;

400if (auto It = VRMap[LastStageNum].find(LoopVal);

401 It != VRMap[LastStageNum].end())

402 PhiOp2 = It->second;

403

404int StageScheduled = Schedule.getStage(&*BBI);

405int LoopValStage = Schedule.getStage(MRI.getVRegDef(LoopVal));

406unsigned NumStages = getStagesForReg(Def, CurStageNum);

407if (NumStages == 0) {

408// We don't need to generate a Phi anymore, but we need to rename any uses

409// of the Phi value.

410unsigned NewReg = VRMap[PrevStage][LoopVal];

411 rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, 0, &*BBI, Def,

412 InitVal, NewReg);

413if (VRMap[CurStageNum].count(LoopVal))

414 VRMap[CurStageNum][Def] = VRMap[CurStageNum][LoopVal];

415 }

416// Adjust the number of Phis needed depending on the number of prologs left,

417// and the distance from where the Phi is first scheduled. The number of

418// Phis cannot exceed the number of prolog stages. Each stage can

419// potentially define two values.

420unsigned MaxPhis = PrologStage + 2;

421if (!InKernel && (int)PrologStage <= LoopValStage)

422 MaxPhis = std::max((int)MaxPhis - (int)LoopValStage, 1);

423unsigned NumPhis = std::min(NumStages, MaxPhis);

424

425unsigned NewReg = 0;

426unsigned AccessStage = (LoopValStage != -1) ? LoopValStage : StageScheduled;

427// In the epilog, we may need to look back one stage to get the correct

428// Phi name, because the epilog and prolog blocks execute the same stage.

429// The correct name is from the previous block only when the Phi has

430// been completely scheduled prior to the epilog, and Phi value is not

431// needed in multiple stages.

432int StageDiff = 0;

433if (!InKernel && StageScheduled >= LoopValStage && AccessStage == 0 &&

434 NumPhis == 1)

435 StageDiff = 1;

436// Adjust the computations below when the phi and the loop definition

437// are scheduled in different stages.

438if (InKernel && LoopValStage != -1 && StageScheduled > LoopValStage)

439 StageDiff = StageScheduled - LoopValStage;

440for (unsigned np = 0; np < NumPhis; ++np) {

441// If the Phi hasn't been scheduled, then use the initial Phi operand

442// value. Otherwise, use the scheduled version of the instruction. This

443// is a little complicated when a Phi references another Phi.

444if (np > PrologStage || StageScheduled >= (int)LastStageNum)

445 PhiOp1 = InitVal;

446// Check if the Phi has already been scheduled in a prolog stage.

447elseif (PrologStage >= AccessStage + StageDiff + np &&

448 VRMap[PrologStage - StageDiff - np].count(LoopVal) != 0)

449 PhiOp1 = VRMap[PrologStage - StageDiff - np][LoopVal];

450// Check if the Phi has already been scheduled, but the loop instruction

451// is either another Phi, or doesn't occur in the loop.

452elseif (PrologStage >= AccessStage + StageDiff + np) {

453// If the Phi references another Phi, we need to examine the other

454// Phi to get the correct value.

455 PhiOp1 = LoopVal;

456MachineInstr *InstOp1 = MRI.getVRegDef(PhiOp1);

457int Indirects = 1;

458while (InstOp1 && InstOp1->isPHI() && InstOp1->getParent() == BB) {

459int PhiStage = Schedule.getStage(InstOp1);

460if ((int)(PrologStage - StageDiff - np) < PhiStage + Indirects)

461 PhiOp1 =getInitPhiReg(*InstOp1, BB);

462else

463 PhiOp1 =getLoopPhiReg(*InstOp1, BB);

464 InstOp1 = MRI.getVRegDef(PhiOp1);

465int PhiOpStage = Schedule.getStage(InstOp1);

466int StageAdj = (PhiOpStage != -1 ? PhiStage - PhiOpStage : 0);

467if (PhiOpStage != -1 && PrologStage - StageAdj >= Indirects + np &&

468 VRMap[PrologStage - StageAdj - Indirects - np].count(PhiOp1)) {

469 PhiOp1 = VRMap[PrologStage - StageAdj - Indirects - np][PhiOp1];

470break;

471 }

472 ++Indirects;

473 }

474 }else

475 PhiOp1 = InitVal;

476// If this references a generated Phi in the kernel, get the Phi operand

477// from the incoming block.

478if (MachineInstr *InstOp1 = MRI.getVRegDef(PhiOp1))

479if (InstOp1->isPHI() && InstOp1->getParent() == KernelBB)

480 PhiOp1 =getInitPhiReg(*InstOp1, KernelBB);

481

482MachineInstr *PhiInst = MRI.getVRegDef(LoopVal);

483bool LoopDefIsPhi = PhiInst && PhiInst->isPHI();

484// In the epilog, a map lookup is needed to get the value from the kernel,

485// or previous epilog block. How is does this depends on if the

486// instruction is scheduled in the previous block.

487if (!InKernel) {

488int StageDiffAdj = 0;

489if (LoopValStage != -1 && StageScheduled > LoopValStage)

490 StageDiffAdj = StageScheduled - LoopValStage;

491// Use the loop value defined in the kernel, unless the kernel

492// contains the last definition of the Phi.

493if (np == 0 && PrevStage == LastStageNum &&

494 (StageScheduled != 0 || LoopValStage != 0) &&

495 VRMap[PrevStage - StageDiffAdj].count(LoopVal))

496 PhiOp2 = VRMap[PrevStage - StageDiffAdj][LoopVal];

497// Use the value defined by the Phi. We add one because we switch

498// from looking at the loop value to the Phi definition.

499elseif (np > 0 && PrevStage == LastStageNum &&

500 VRMap[PrevStage - np + 1].count(Def))

501 PhiOp2 = VRMap[PrevStage - np + 1][Def];

502// Use the loop value defined in the kernel.

503elseif (static_cast<unsigned>(LoopValStage) > PrologStage + 1 &&

504 VRMap[PrevStage - StageDiffAdj - np].count(LoopVal))

505 PhiOp2 = VRMap[PrevStage - StageDiffAdj - np][LoopVal];

506// Use the value defined by the Phi, unless we're generating the first

507// epilog and the Phi refers to a Phi in a different stage.

508elseif (VRMap[PrevStage - np].count(Def) &&

509 (!LoopDefIsPhi || (PrevStage != LastStageNum) ||

510 (LoopValStage == StageScheduled)))

511 PhiOp2 = VRMap[PrevStage - np][Def];

512 }

513

514// Check if we can reuse an existing Phi. This occurs when a Phi

515// references another Phi, and the other Phi is scheduled in an

516// earlier stage. We can try to reuse an existing Phi up until the last

517// stage of the current Phi.

518if (LoopDefIsPhi) {

519if (static_cast<int>(PrologStage - np) >= StageScheduled) {

520int LVNumStages = getStagesForPhi(LoopVal);

521int StageDiff = (StageScheduled - LoopValStage);

522 LVNumStages -= StageDiff;

523// Make sure the loop value Phi has been processed already.

524if (LVNumStages > (int)np && VRMap[CurStageNum].count(LoopVal)) {

525 NewReg = PhiOp2;

526unsigned ReuseStage = CurStageNum;

527if (isLoopCarried(*PhiInst))

528 ReuseStage -= LVNumStages;

529// Check if the Phi to reuse has been generated yet. If not, then

530// there is nothing to reuse.

531if (VRMap[ReuseStage - np].count(LoopVal)) {

532 NewReg = VRMap[ReuseStage - np][LoopVal];

533

534 rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, np, &*BBI,

535 Def, NewReg);

536// Update the map with the new Phi name.

537 VRMap[CurStageNum - np][Def] = NewReg;

538 PhiOp2 = NewReg;

539if (VRMap[LastStageNum - np - 1].count(LoopVal))

540 PhiOp2 = VRMap[LastStageNum - np - 1][LoopVal];

541

542if (IsLast && np == NumPhis - 1)

543replaceRegUsesAfterLoop(Def, NewReg, BB, MRI, LIS);

544continue;

545 }

546 }

547 }

548if (InKernel && StageDiff > 0 &&

549 VRMap[CurStageNum - StageDiff - np].count(LoopVal))

550 PhiOp2 = VRMap[CurStageNum - StageDiff - np][LoopVal];

551 }

552

553constTargetRegisterClass *RC = MRI.getRegClass(Def);

554 NewReg = MRI.createVirtualRegister(RC);

555

556MachineInstrBuilder NewPhi =

557BuildMI(*NewBB, NewBB->getFirstNonPHI(),DebugLoc(),

558 TII->get(TargetOpcode::PHI), NewReg);

559 NewPhi.addReg(PhiOp1).addMBB(BB1);

560 NewPhi.addReg(PhiOp2).addMBB(BB2);

561if (np == 0)

562 InstrMap[NewPhi] = &*BBI;

563

564// We define the Phis after creating the new pipelined code, so

565// we need to rename the Phi values in scheduled instructions.

566

567unsigned PrevReg = 0;

568if (InKernel && VRMap[PrevStage - np].count(LoopVal))

569 PrevReg = VRMap[PrevStage - np][LoopVal];

570 rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, np, &*BBI, Def,

571 NewReg, PrevReg);

572// If the Phi has been scheduled, use the new name for rewriting.

573if (VRMap[CurStageNum - np].count(Def)) {

574unsignedR = VRMap[CurStageNum - np][Def];

575 rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, np, &*BBI, R,

576 NewReg);

577 }

578

579// Check if we need to rename any uses that occurs after the loop. The

580// register to replace depends on whether the Phi is scheduled in the

581// epilog.

582if (IsLast && np == NumPhis - 1)

583replaceRegUsesAfterLoop(Def, NewReg, BB, MRI, LIS);

584

585// In the kernel, a dependent Phi uses the value from this Phi.

586if (InKernel)

587 PhiOp2 = NewReg;

588

589// Update the map with the new Phi name.

590 VRMap[CurStageNum - np][Def] = NewReg;

591 }

592

593while (NumPhis++ < NumStages) {

594 rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, NumPhis, &*BBI, Def,

595 NewReg, 0);

596 }

597

598// Check if we need to rename a Phi that has been eliminated due to

599// scheduling.

600if (NumStages == 0 && IsLast && VRMap[CurStageNum].count(LoopVal))

601replaceRegUsesAfterLoop(Def, VRMap[CurStageNum][LoopVal], BB, MRI, LIS);

602 }

603}

604

605/// Generate Phis for the specified block in the generated pipelined code.

606/// These are new Phis needed because the definition is scheduled after the

607/// use in the pipelined sequence.

608void ModuloScheduleExpander::generatePhis(

609MachineBasicBlock *NewBB,MachineBasicBlock *BB1,MachineBasicBlock *BB2,

610MachineBasicBlock *KernelBB, ValueMapTy *VRMap, ValueMapTy *VRMapPhi,

611 InstrMapTy &InstrMap,unsigned LastStageNum,unsigned CurStageNum,

612bool IsLast) {

613// Compute the stage number that contains the initial Phi value, and

614// the Phi from the previous stage.

615unsigned PrologStage = 0;

616unsigned PrevStage = 0;

617unsigned StageDiff = CurStageNum - LastStageNum;

618bool InKernel = (StageDiff == 0);

619if (InKernel) {

620 PrologStage = LastStageNum - 1;

621 PrevStage = CurStageNum;

622 }else {

623 PrologStage = LastStageNum - StageDiff;

624 PrevStage = LastStageNum + StageDiff - 1;

625 }

626

627for (MachineBasicBlock::iterator BBI = BB->getFirstNonPHI(),

628 BBE = BB->instr_end();

629 BBI != BBE; ++BBI) {

630for (unsigned i = 0, e = BBI->getNumOperands(); i !=e; ++i) {

631MachineOperand &MO = BBI->getOperand(i);

632if (!MO.isReg() || !MO.isDef() || !MO.getReg().isVirtual())

633continue;

634

635int StageScheduled = Schedule.getStage(&*BBI);

636assert(StageScheduled != -1 &&"Expecting scheduled instruction.");

637Register Def = MO.getReg();

638unsigned NumPhis = getStagesForReg(Def, CurStageNum);

639// An instruction scheduled in stage 0 and is used after the loop

640// requires a phi in the epilog for the last definition from either

641// the kernel or prolog.

642if (!InKernel && NumPhis == 0 && StageScheduled == 0 &&

643hasUseAfterLoop(Def, BB, MRI))

644 NumPhis = 1;

645if (!InKernel && (unsigned)StageScheduled > PrologStage)

646continue;

647

648unsigned PhiOp2;

649if (InKernel) {

650 PhiOp2 = VRMap[PrevStage][Def];

651if (MachineInstr *InstOp2 = MRI.getVRegDef(PhiOp2))

652if (InstOp2->isPHI() && InstOp2->getParent() == NewBB)

653 PhiOp2 =getLoopPhiReg(*InstOp2, BB2);

654 }

655// The number of Phis can't exceed the number of prolog stages. The

656// prolog stage number is zero based.

657if (NumPhis > PrologStage + 1 - StageScheduled)

658 NumPhis = PrologStage + 1 - StageScheduled;

659for (unsigned np = 0; np < NumPhis; ++np) {

660// Example for

661// Org:

662// %Org = ... (Scheduled at Stage#0, NumPhi = 2)

663//

664// Prolog0 (Stage0):

665// %Clone0 = ...

666// Prolog1 (Stage1):

667// %Clone1 = ...

668// Kernel (Stage2):

669// %Phi0 = Phi %Clone1, Prolog1, %Clone2, Kernel

670// %Phi1 = Phi %Clone0, Prolog1, %Phi0, Kernel

671// %Clone2 = ...

672// Epilog0 (Stage3):

673// %Phi2 = Phi %Clone1, Prolog1, %Clone2, Kernel

674// %Phi3 = Phi %Clone0, Prolog1, %Phi0, Kernel

675// Epilog1 (Stage4):

676// %Phi4 = Phi %Clone0, Prolog0, %Phi2, Epilog0

677//

678// VRMap = {0: %Clone0, 1: %Clone1, 2: %Clone2}

679// VRMapPhi (after Kernel) = {0: %Phi1, 1: %Phi0}

680// VRMapPhi (after Epilog0) = {0: %Phi3, 1: %Phi2}

681

682unsigned PhiOp1 = VRMap[PrologStage][Def];

683if (np <= PrologStage)

684 PhiOp1 = VRMap[PrologStage - np][Def];

685if (!InKernel) {

686if (PrevStage == LastStageNum && np == 0)

687 PhiOp2 = VRMap[LastStageNum][Def];

688else

689 PhiOp2 = VRMapPhi[PrevStage - np][Def];

690 }

691

692constTargetRegisterClass *RC = MRI.getRegClass(Def);

693Register NewReg = MRI.createVirtualRegister(RC);

694

695MachineInstrBuilder NewPhi =

696BuildMI(*NewBB, NewBB->getFirstNonPHI(),DebugLoc(),

697 TII->get(TargetOpcode::PHI), NewReg);

698 NewPhi.addReg(PhiOp1).addMBB(BB1);

699 NewPhi.addReg(PhiOp2).addMBB(BB2);

700if (np == 0)

701 InstrMap[NewPhi] = &*BBI;

702

703// Rewrite uses and update the map. The actions depend upon whether

704// we generating code for the kernel or epilog blocks.

705if (InKernel) {

706 rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, np, &*BBI, PhiOp1,

707 NewReg);

708 rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, np, &*BBI, PhiOp2,

709 NewReg);

710

711 PhiOp2 = NewReg;

712 VRMapPhi[PrevStage - np - 1][Def] = NewReg;

713 }else {

714 VRMapPhi[CurStageNum - np][Def] = NewReg;

715if (np == NumPhis - 1)

716 rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, np, &*BBI, Def,

717 NewReg);

718 }

719if (IsLast && np == NumPhis - 1)

720replaceRegUsesAfterLoop(Def, NewReg, BB, MRI, LIS);

721 }

722 }

723 }

724}

725

726/// Remove instructions that generate values with no uses.

727/// Typically, these are induction variable operations that generate values

728/// used in the loop itself. A dead instruction has a definition with

729/// no uses, or uses that occur in the original loop only.

730void ModuloScheduleExpander::removeDeadInstructions(MachineBasicBlock *KernelBB,

731 MBBVectorTy &EpilogBBs) {

732// For each epilog block, check that the value defined by each instruction

733// is used. If not, delete it.

734for (MachineBasicBlock *MBB :llvm::reverse(EpilogBBs))

735for (MachineBasicBlock::reverse_instr_iterator MI =MBB->instr_rbegin(),

736 ME =MBB->instr_rend();

737MI != ME;) {

738// From DeadMachineInstructionElem. Don't delete inline assembly.

739if (MI->isInlineAsm()) {

740 ++MI;

741continue;

742 }

743bool SawStore =false;

744// Check if it's safe to remove the instruction due to side effects.

745// We can, and want to, remove Phis here.

746if (!MI->isSafeToMove(SawStore) && !MI->isPHI()) {

747 ++MI;

748continue;

749 }

750bool used =true;

751for (constMachineOperand &MO :MI->all_defs()) {

752Register reg = MO.getReg();

753// Assume physical registers are used, unless they are marked dead.

754if (reg.isPhysical()) {

755 used = !MO.isDead();

756if (used)

757break;

758continue;

759 }

760unsigned realUses = 0;

761for (constMachineOperand &U : MRI.use_operands(reg)) {

762// Check if there are any uses that occur only in the original

763// loop. If so, that's not a real use.

764if (U.getParent()->getParent() != BB) {

765 realUses++;

766 used =true;

767break;

768 }

769 }

770if (realUses > 0)

771break;

772 used =false;

773 }

774if (!used) {

775 LIS.RemoveMachineInstrFromMaps(*MI);

776MI++->eraseFromParent();

777continue;

778 }

779 ++MI;

780 }

781// In the kernel block, check if we can remove a Phi that generates a value

782// used in an instruction removed in the epilog block.

783for (MachineInstr &MI :llvm::make_early_inc_range(KernelBB->phis())) {

784Register reg =MI.getOperand(0).getReg();

785if (MRI.use_begin(reg) == MRI.use_end()) {

786 LIS.RemoveMachineInstrFromMaps(MI);

787MI.eraseFromParent();

788 }

789 }

790}

791

792/// For loop carried definitions, we split the lifetime of a virtual register

793/// that has uses past the definition in the next iteration. A copy with a new

794/// virtual register is inserted before the definition, which helps with

795/// generating a better register assignment.

796///

797/// v1 = phi(a, v2) v1 = phi(a, v2)

798/// v2 = phi(b, v3) v2 = phi(b, v3)

799/// v3 = .. v4 = copy v1

800/// .. = V1 v3 = ..

801/// .. = v4

802void ModuloScheduleExpander::splitLifetimes(MachineBasicBlock *KernelBB,

803 MBBVectorTy &EpilogBBs) {

804constTargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();

805for (auto &PHI : KernelBB->phis()) {

806Register Def =PHI.getOperand(0).getReg();

807// Check for any Phi definition that used as an operand of another Phi

808// in the same block.

809for (MachineRegisterInfo::use_instr_iterator I = MRI.use_instr_begin(Def),

810 E = MRI.use_instr_end();

811I != E; ++I) {

812if (I->isPHI() &&I->getParent() == KernelBB) {

813// Get the loop carried definition.

814unsigned LCDef =getLoopPhiReg(PHI, KernelBB);

815if (!LCDef)

816continue;

817MachineInstr *MI = MRI.getVRegDef(LCDef);

818if (!MI ||MI->getParent() != KernelBB ||MI->isPHI())

819continue;

820// Search through the rest of the block looking for uses of the Phi

821// definition. If one occurs, then split the lifetime.

822unsigned SplitReg = 0;

823for (auto &BBJ :make_range(MachineBasicBlock::instr_iterator(MI),

824 KernelBB->instr_end()))

825if (BBJ.readsRegister(Def,/*TRI=*/nullptr)) {

826// We split the lifetime when we find the first use.

827if (SplitReg == 0) {

828 SplitReg = MRI.createVirtualRegister(MRI.getRegClass(Def));

829BuildMI(*KernelBB,MI,MI->getDebugLoc(),

830 TII->get(TargetOpcode::COPY), SplitReg)

831 .addReg(Def);

832 }

833 BBJ.substituteRegister(Def, SplitReg, 0, *TRI);

834 }

835if (!SplitReg)

836continue;

837// Search through each of the epilog blocks for any uses to be renamed.

838for (auto &Epilog : EpilogBBs)

839for (auto &I : *Epilog)

840if (I.readsRegister(Def,/*TRI=*/nullptr))

841I.substituteRegister(Def, SplitReg, 0, *TRI);

842break;

843 }

844 }

845 }

846}

847

848/// Remove the incoming block from the Phis in a basic block.

849staticvoidremovePhis(MachineBasicBlock *BB,MachineBasicBlock *Incoming) {

850for (MachineInstr &MI : *BB) {

851if (!MI.isPHI())

852break;

853for (unsigned i = 1, e =MI.getNumOperands(); i != e; i += 2)

854if (MI.getOperand(i + 1).getMBB() ==Incoming) {

855MI.removeOperand(i + 1);

856MI.removeOperand(i);

857break;

858 }

859 }

860}

861

862/// Create branches from each prolog basic block to the appropriate epilog

863/// block. These edges are needed if the loop ends before reaching the

864/// kernel.

865void ModuloScheduleExpander::addBranches(MachineBasicBlock &PreheaderBB,

866 MBBVectorTy &PrologBBs,

867MachineBasicBlock *KernelBB,

868 MBBVectorTy &EpilogBBs,

869 ValueMapTy *VRMap) {

870assert(PrologBBs.size() == EpilogBBs.size() &&"Prolog/Epilog mismatch");

871MachineBasicBlock *LastPro = KernelBB;

872MachineBasicBlock *LastEpi = KernelBB;

873

874// Start from the blocks connected to the kernel and work "out"

875// to the first prolog and the last epilog blocks.

876SmallVector<MachineInstr *, 4> PrevInsts;

877unsigned MaxIter = PrologBBs.size() - 1;

878for (unsigned i = 0, j = MaxIter; i <= MaxIter; ++i, --j) {

879// Add branches to the prolog that go to the corresponding

880// epilog, and the fall-thru prolog/kernel block.

881MachineBasicBlock *Prolog = PrologBBs[j];

882MachineBasicBlock *Epilog = EpilogBBs[i];

883

884SmallVector<MachineOperand, 4>Cond;

885 std::optional<bool> StaticallyGreater =

886LoopInfo->createTripCountGreaterCondition(j + 1, *Prolog,Cond);

887unsigned numAdded = 0;

888if (!StaticallyGreater) {

889Prolog->addSuccessor(Epilog);

890 numAdded = TII->insertBranch(*Prolog,Epilog, LastPro,Cond,DebugLoc());

891 }elseif (*StaticallyGreater ==false) {

892Prolog->addSuccessor(Epilog);

893Prolog->removeSuccessor(LastPro);

894 LastEpi->removeSuccessor(Epilog);

895 numAdded = TII->insertBranch(*Prolog,Epilog,nullptr,Cond,DebugLoc());

896removePhis(Epilog, LastEpi);

897// Remove the blocks that are no longer referenced.

898if (LastPro != LastEpi) {

899 LastEpi->clear();

900 LastEpi->eraseFromParent();

901 }

902if (LastPro == KernelBB) {

903LoopInfo->disposed(&LIS);

904 NewKernel =nullptr;

905 }

906 LastPro->clear();

907 LastPro->eraseFromParent();

908 }else {

909 numAdded = TII->insertBranch(*Prolog, LastPro,nullptr,Cond,DebugLoc());

910removePhis(Epilog,Prolog);

911 }

912 LastPro =Prolog;

913 LastEpi =Epilog;

914for (MachineBasicBlock::reverse_instr_iterator I =Prolog->instr_rbegin(),

915 E =Prolog->instr_rend();

916I != E && numAdded > 0; ++I, --numAdded)

917 updateInstruction(&*I,false, j, 0, VRMap);

918 }

919

920if (NewKernel) {

921LoopInfo->setPreheader(PrologBBs[MaxIter]);

922LoopInfo->adjustTripCount(-(MaxIter + 1));

923 }

924}

925

926/// Return true if we can compute the amount the instruction changes

927/// during each iteration. Set Delta to the amount of the change.

928bool ModuloScheduleExpander::computeDelta(MachineInstr &MI,unsigned &Delta) {

929constTargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();

930constMachineOperand *BaseOp;

931 int64_tOffset;

932bool OffsetIsScalable;

933if (!TII->getMemOperandWithOffset(MI, BaseOp,Offset, OffsetIsScalable,TRI))

934returnfalse;

935

936// FIXME: This algorithm assumes instructions have fixed-size offsets.

937if (OffsetIsScalable)

938returnfalse;

939

940if (!BaseOp->isReg())

941returnfalse;

942

943Register BaseReg = BaseOp->getReg();

944

945MachineRegisterInfo &MRI = MF.getRegInfo();

946// Check if there is a Phi. If so, get the definition in the loop.

947MachineInstr *BaseDef =MRI.getVRegDef(BaseReg);

948if (BaseDef && BaseDef->isPHI()) {

949 BaseReg =getLoopPhiReg(*BaseDef,MI.getParent());

950 BaseDef =MRI.getVRegDef(BaseReg);

951 }

952if (!BaseDef)

953returnfalse;

954

955intD = 0;

956if (!TII->getIncrementValue(*BaseDef,D) &&D >= 0)

957returnfalse;

958

959 Delta =D;

960returntrue;

961}

962

963/// Update the memory operand with a new offset when the pipeliner

964/// generates a new copy of the instruction that refers to a

965/// different memory location.

966void ModuloScheduleExpander::updateMemOperands(MachineInstr &NewMI,

967MachineInstr &OldMI,

968unsigned Num) {

969if (Num == 0)

970return;

971// If the instruction has memory operands, then adjust the offset

972// when the instruction appears in different stages.

973if (NewMI.memoperands_empty())

974return;

975SmallVector<MachineMemOperand *, 2> NewMMOs;

976for (MachineMemOperand *MMO : NewMI.memoperands()) {

977// TODO: Figure out whether isAtomic is really necessary (see D57601).

978if (MMO->isVolatile() || MMO->isAtomic() ||

979 (MMO->isInvariant() && MMO->isDereferenceable()) ||

980 (!MMO->getValue())) {

981 NewMMOs.push_back(MMO);

982continue;

983 }

984unsigned Delta;

985if (Num != UINT_MAX && computeDelta(OldMI, Delta)) {

986 int64_t AdjOffset = Delta * Num;

987 NewMMOs.push_back(

988 MF.getMachineMemOperand(MMO, AdjOffset, MMO->getSize()));

989 }else {

990 NewMMOs.push_back(MF.getMachineMemOperand(

991 MMO, 0,LocationSize::beforeOrAfterPointer()));

992 }

993 }

994 NewMI.setMemRefs(MF, NewMMOs);

995}

996

997/// Clone the instruction for the new pipelined loop and update the

998/// memory operands, if needed.

999MachineInstr *ModuloScheduleExpander::cloneInstr(MachineInstr *OldMI,

1000unsigned CurStageNum,

1001unsigned InstStageNum) {

1002MachineInstr *NewMI = MF.CloneMachineInstr(OldMI);

1003 updateMemOperands(*NewMI, *OldMI, CurStageNum - InstStageNum);

1004return NewMI;

1005}

1006

1007/// Clone the instruction for the new pipelined loop. If needed, this

1008/// function updates the instruction using the values saved in the

1009/// InstrChanges structure.

1010MachineInstr *ModuloScheduleExpander::cloneAndChangeInstr(

1011MachineInstr *OldMI,unsigned CurStageNum,unsigned InstStageNum) {

1012MachineInstr *NewMI = MF.CloneMachineInstr(OldMI);

1013auto It = InstrChanges.find(OldMI);

1014if (It != InstrChanges.end()) {

1015 std::pair<unsigned, int64_t> RegAndOffset = It->second;

1016unsigned BasePos, OffsetPos;

1017if (!TII->getBaseAndOffsetPosition(*OldMI, BasePos, OffsetPos))

1018returnnullptr;

1019 int64_t NewOffset = OldMI->getOperand(OffsetPos).getImm();

1020MachineInstr *LoopDef = findDefInLoop(RegAndOffset.first);

1021if (Schedule.getStage(LoopDef) > (signed)InstStageNum)

1022 NewOffset += RegAndOffset.second * (CurStageNum - InstStageNum);

1023 NewMI->getOperand(OffsetPos).setImm(NewOffset);

1024 }

1025 updateMemOperands(*NewMI, *OldMI, CurStageNum - InstStageNum);

1026return NewMI;

1027}

1028

1029/// Update the machine instruction with new virtual registers. This

1030/// function may change the definitions and/or uses.

1031void ModuloScheduleExpander::updateInstruction(MachineInstr *NewMI,

1032bool LastDef,

1033unsigned CurStageNum,

1034unsigned InstrStageNum,

1035 ValueMapTy *VRMap) {

1036for (MachineOperand &MO : NewMI->operands()) {

1037if (!MO.isReg() || !MO.getReg().isVirtual())

1038continue;

1039Register reg = MO.getReg();

1040if (MO.isDef()) {

1041// Create a new virtual register for the definition.

1042constTargetRegisterClass *RC =MRI.getRegClass(reg);

1043Register NewReg =MRI.createVirtualRegister(RC);

1044 MO.setReg(NewReg);

1045 VRMap[CurStageNum][reg] = NewReg;

1046if (LastDef)

1047replaceRegUsesAfterLoop(reg, NewReg, BB, MRI, LIS);

1048 }elseif (MO.isUse()) {

1049MachineInstr *Def =MRI.getVRegDef(reg);

1050// Compute the stage that contains the last definition for instruction.

1051int DefStageNum = Schedule.getStage(Def);

1052unsigned StageNum = CurStageNum;

1053if (DefStageNum != -1 && (int)InstrStageNum > DefStageNum) {

1054// Compute the difference in stages between the defintion and the use.

1055unsigned StageDiff = (InstrStageNum - DefStageNum);

1056// Make an adjustment to get the last definition.

1057 StageNum -= StageDiff;

1058 }

1059if (auto It = VRMap[StageNum].find(reg); It != VRMap[StageNum].end())

1060 MO.setReg(It->second);

1061 }

1062 }

1063}

1064

1065/// Return the instruction in the loop that defines the register.

1066/// If the definition is a Phi, then follow the Phi operand to

1067/// the instruction in the loop.

1068MachineInstr *ModuloScheduleExpander::findDefInLoop(unsigned Reg) {

1069SmallPtrSet<MachineInstr *, 8> Visited;

1070MachineInstr *Def =MRI.getVRegDef(Reg);

1071while (Def->isPHI()) {

1072if (!Visited.insert(Def).second)

1073break;

1074for (unsigned i = 1, e =Def->getNumOperands(); i < e; i += 2)

1075if (Def->getOperand(i + 1).getMBB() == BB) {

1076Def =MRI.getVRegDef(Def->getOperand(i).getReg());

1077break;

1078 }

1079 }

1080returnDef;

1081}

1082

1083/// Return the new name for the value from the previous stage.

1084unsigned ModuloScheduleExpander::getPrevMapVal(

1085unsigned StageNum,unsigned PhiStage,unsigned LoopVal,unsigned LoopStage,

1086 ValueMapTy *VRMap,MachineBasicBlock *BB) {

1087unsigned PrevVal = 0;

1088if (StageNum > PhiStage) {

1089MachineInstr *LoopInst =MRI.getVRegDef(LoopVal);

1090if (PhiStage == LoopStage && VRMap[StageNum - 1].count(LoopVal))

1091// The name is defined in the previous stage.

1092 PrevVal = VRMap[StageNum - 1][LoopVal];

1093elseif (VRMap[StageNum].count(LoopVal))

1094// The previous name is defined in the current stage when the instruction

1095// order is swapped.

1096 PrevVal = VRMap[StageNum][LoopVal];

1097elseif (!LoopInst->isPHI() || LoopInst->getParent() != BB)

1098// The loop value hasn't yet been scheduled.

1099 PrevVal = LoopVal;

1100elseif (StageNum == PhiStage + 1)

1101// The loop value is another phi, which has not been scheduled.

1102 PrevVal =getInitPhiReg(*LoopInst, BB);

1103elseif (StageNum > PhiStage + 1 && LoopInst->getParent() == BB)

1104// The loop value is another phi, which has been scheduled.

1105 PrevVal =

1106 getPrevMapVal(StageNum - 1, PhiStage,getLoopPhiReg(*LoopInst, BB),

1107 LoopStage, VRMap, BB);

1108 }

1109return PrevVal;

1110}

1111

1112/// Rewrite the Phi values in the specified block to use the mappings

1113/// from the initial operand. Once the Phi is scheduled, we switch

1114/// to using the loop value instead of the Phi value, so those names

1115/// do not need to be rewritten.

1116void ModuloScheduleExpander::rewritePhiValues(MachineBasicBlock *NewBB,

1117unsigned StageNum,

1118 ValueMapTy *VRMap,

1119 InstrMapTy &InstrMap) {

1120for (auto &PHI : BB->phis()) {

1121unsigned InitVal = 0;

1122unsigned LoopVal = 0;

1123getPhiRegs(PHI, BB, InitVal, LoopVal);

1124Register PhiDef =PHI.getOperand(0).getReg();

1125

1126unsigned PhiStage = (unsigned)Schedule.getStage(MRI.getVRegDef(PhiDef));

1127unsigned LoopStage = (unsigned)Schedule.getStage(MRI.getVRegDef(LoopVal));

1128unsigned NumPhis = getStagesForPhi(PhiDef);

1129if (NumPhis > StageNum)

1130 NumPhis = StageNum;

1131for (unsigned np = 0; np <= NumPhis; ++np) {

1132unsigned NewVal =

1133 getPrevMapVal(StageNum - np, PhiStage, LoopVal, LoopStage, VRMap, BB);

1134if (!NewVal)

1135 NewVal = InitVal;

1136 rewriteScheduledInstr(NewBB, InstrMap, StageNum - np, np, &PHI, PhiDef,

1137 NewVal);

1138 }

1139 }

1140}

1141

1142/// Rewrite a previously scheduled instruction to use the register value

1143/// from the new instruction. Make sure the instruction occurs in the

1144/// basic block, and we don't change the uses in the new instruction.

1145void ModuloScheduleExpander::rewriteScheduledInstr(

1146MachineBasicBlock *BB, InstrMapTy &InstrMap,unsigned CurStageNum,

1147unsigned PhiNum,MachineInstr *Phi,unsigned OldReg,unsigned NewReg,

1148unsigned PrevReg) {

1149bool InProlog = (CurStageNum < (unsigned)Schedule.getNumStages() - 1);

1150int StagePhi = Schedule.getStage(Phi) + PhiNum;

1151// Rewrite uses that have been scheduled already to use the new

1152// Phi register.

1153for (MachineOperand &UseOp :

1154llvm::make_early_inc_range(MRI.use_operands(OldReg))) {

1155MachineInstr *UseMI = UseOp.getParent();

1156if (UseMI->getParent() != BB)

1157continue;

1158if (UseMI->isPHI()) {

1159if (!Phi->isPHI() &&UseMI->getOperand(0).getReg() == NewReg)

1160continue;

1161if (getLoopPhiReg(*UseMI, BB) != OldReg)

1162continue;

1163 }

1164InstrMapTy::iterator OrigInstr = InstrMap.find(UseMI);

1165assert(OrigInstr != InstrMap.end() &&"Instruction not scheduled.");

1166MachineInstr *OrigMI = OrigInstr->second;

1167int StageSched = Schedule.getStage(OrigMI);

1168int CycleSched = Schedule.getCycle(OrigMI);

1169unsigned ReplaceReg = 0;

1170// This is the stage for the scheduled instruction.

1171if (StagePhi == StageSched &&Phi->isPHI()) {

1172int CyclePhi = Schedule.getCycle(Phi);

1173if (PrevReg && InProlog)

1174 ReplaceReg = PrevReg;

1175elseif (PrevReg && !isLoopCarried(*Phi) &&

1176 (CyclePhi <= CycleSched || OrigMI->isPHI()))

1177 ReplaceReg = PrevReg;

1178else

1179 ReplaceReg = NewReg;

1180 }

1181// The scheduled instruction occurs before the scheduled Phi, and the

1182// Phi is not loop carried.

1183if (!InProlog && StagePhi + 1 == StageSched && !isLoopCarried(*Phi))

1184 ReplaceReg = NewReg;

1185if (StagePhi > StageSched &&Phi->isPHI())

1186 ReplaceReg = NewReg;

1187if (!InProlog && !Phi->isPHI() && StagePhi < StageSched)

1188 ReplaceReg = NewReg;

1189if (ReplaceReg) {

1190constTargetRegisterClass *NRC =

1191MRI.constrainRegClass(ReplaceReg,MRI.getRegClass(OldReg));

1192if (NRC)

1193 UseOp.setReg(ReplaceReg);

1194else {

1195Register SplitReg =MRI.createVirtualRegister(MRI.getRegClass(OldReg));

1196BuildMI(*BB,UseMI,UseMI->getDebugLoc(), TII->get(TargetOpcode::COPY),

1197 SplitReg)

1198 .addReg(ReplaceReg);

1199 UseOp.setReg(SplitReg);

1200 }

1201 }

1202 }

1203}

1204

1205bool ModuloScheduleExpander::isLoopCarried(MachineInstr &Phi) {

1206if (!Phi.isPHI())

1207returnfalse;

1208int DefCycle = Schedule.getCycle(&Phi);

1209int DefStage = Schedule.getStage(&Phi);

1210

1211unsigned InitVal = 0;

1212unsigned LoopVal = 0;

1213getPhiRegs(Phi,Phi.getParent(), InitVal, LoopVal);

1214MachineInstr *Use =MRI.getVRegDef(LoopVal);

1215if (!Use ||Use->isPHI())

1216returntrue;

1217int LoopCycle = Schedule.getCycle(Use);

1218int LoopStage = Schedule.getStage(Use);

1219return (LoopCycle > DefCycle) || (LoopStage <= DefStage);

1220}

1221

1222//===----------------------------------------------------------------------===//

1223// PeelingModuloScheduleExpander implementation

1224//===----------------------------------------------------------------------===//

1225// This is a reimplementation of ModuloScheduleExpander that works by creating

1226// a fully correct steady-state kernel and peeling off the prolog and epilogs.

1227//===----------------------------------------------------------------------===//

1228

1229namespace{

1230// Remove any dead phis in MBB. Dead phis either have only one block as input

1231// (in which case they are the identity) or have no uses.

1232void EliminateDeadPhis(MachineBasicBlock *MBB,MachineRegisterInfo &MRI,

1233LiveIntervals *LIS,bool KeepSingleSrcPhi =false) {

1234bool Changed =true;

1235while (Changed) {

1236 Changed =false;

1237for (MachineInstr &MI :llvm::make_early_inc_range(MBB->phis())) {

1238assert(MI.isPHI());

1239if (MRI.use_empty(MI.getOperand(0).getReg())) {

1240if (LIS)

1241 LIS->RemoveMachineInstrFromMaps(MI);

1242MI.eraseFromParent();

1243 Changed =true;

1244 }elseif (!KeepSingleSrcPhi &&MI.getNumExplicitOperands() == 3) {

1245constTargetRegisterClass *ConstrainRegClass =

1246MRI.constrainRegClass(MI.getOperand(1).getReg(),

1247MRI.getRegClass(MI.getOperand(0).getReg()));

1248assert(ConstrainRegClass &&

1249"Expected a valid constrained register class!");

1250 (void)ConstrainRegClass;

1251MRI.replaceRegWith(MI.getOperand(0).getReg(),

1252MI.getOperand(1).getReg());

1253if (LIS)

1254 LIS->RemoveMachineInstrFromMaps(MI);

1255MI.eraseFromParent();

1256 Changed =true;

1257 }

1258 }

1259 }

1260}

1261

1262/// Rewrites the kernel block in-place to adhere to the given schedule.

1263/// KernelRewriter holds all of the state required to perform the rewriting.

1264classKernelRewriter {

1265ModuloSchedule &S;

1266MachineBasicBlock *BB;

1267MachineBasicBlock *PreheaderBB, *ExitBB;

1268MachineRegisterInfo &MRI;

1269constTargetInstrInfo *TII;

1270LiveIntervals *LIS;

1271

1272// Map from register class to canonical undef register for that class.

1273DenseMap<const TargetRegisterClass *, Register> Undefs;

1274// Map from <LoopReg, InitReg> to phi register for all created phis. Note that

1275// this map is only used when InitReg is non-undef.

1276DenseMap<std::pair<unsigned, unsigned>,Register> Phis;

1277// Map from LoopReg to phi register where the InitReg is undef.

1278DenseMap<Register, Register> UndefPhis;

1279

1280// Reg is used by MI. Return the new register MI should use to adhere to the

1281// schedule. Insert phis as necessary.

1282Register remapUse(Register Reg,MachineInstr &MI);

1283// Insert a phi that carries LoopReg from the loop body and InitReg otherwise.

1284// If InitReg is not given it is chosen arbitrarily. It will either be undef

1285// or will be chosen so as to share another phi.

1286Register phi(Register LoopReg, std::optional<Register> InitReg = {},

1287constTargetRegisterClass *RC =nullptr);

1288// Create an undef register of the given register class.

1289Register undef(constTargetRegisterClass *RC);

1290

1291public:

1292 KernelRewriter(MachineLoop &L,ModuloSchedule &S,MachineBasicBlock *LoopBB,

1293LiveIntervals *LIS =nullptr);

1294void rewrite();

1295};

1296}// namespace

1297

1298KernelRewriter::KernelRewriter(MachineLoop &L,ModuloSchedule &S,

1299MachineBasicBlock *LoopBB,LiveIntervals *LIS)

1300 : S(S), BB(LoopBB), PreheaderBB(L.getLoopPreheader()),

1301 ExitBB(L.getExitBlock()),MRI(BB->getParent()->getRegInfo()),

1302TII(BB->getParent()->getSubtarget().getInstrInfo()), LIS(LIS) {

1303 PreheaderBB = *BB->pred_begin();

1304if (PreheaderBB == BB)

1305 PreheaderBB = *std::next(BB->pred_begin());

1306}

1307

1308void KernelRewriter::rewrite() {

1309// Rearrange the loop to be in schedule order. Note that the schedule may

1310// contain instructions that are not owned by the loop block (InstrChanges and

1311// friends), so we gracefully handle unowned instructions and delete any

1312// instructions that weren't in the schedule.

1313auto InsertPt = BB->getFirstTerminator();

1314MachineInstr *FirstMI =nullptr;

1315for (MachineInstr *MI : S.getInstructions()) {

1316if (MI->isPHI())

1317continue;

1318if (MI->getParent())

1319MI->removeFromParent();

1320 BB->insert(InsertPt,MI);

1321if (!FirstMI)

1322 FirstMI =MI;

1323 }

1324assert(FirstMI &&"Failed to find first MI in schedule");

1325

1326// At this point all of the scheduled instructions are between FirstMI

1327// and the end of the block. Kill from the first non-phi to FirstMI.

1328for (autoI = BB->getFirstNonPHI();I != FirstMI->getIterator();) {

1329if (LIS)

1330 LIS->RemoveMachineInstrFromMaps(*I);

1331 (I++)->eraseFromParent();

1332 }

1333

1334// Now remap every instruction in the loop.

1335for (MachineInstr &MI : *BB) {

1336if (MI.isPHI() ||MI.isTerminator())

1337continue;

1338for (MachineOperand &MO :MI.uses()) {

1339if (!MO.isReg() || MO.getReg().isPhysical() || MO.isImplicit())

1340continue;

1341Register Reg = remapUse(MO.getReg(),MI);

1342 MO.setReg(Reg);

1343 }

1344 }

1345 EliminateDeadPhis(BB,MRI, LIS);

1346

1347// Ensure a phi exists for all instructions that are either referenced by

1348// an illegal phi or by an instruction outside the loop. This allows us to

1349// treat remaps of these values the same as "normal" values that come from

1350// loop-carried phis.

1351for (autoMI = BB->getFirstNonPHI();MI != BB->end(); ++MI) {

1352if (MI->isPHI()) {

1353Register R =MI->getOperand(0).getReg();

1354phi(R);

1355continue;

1356 }

1357

1358for (MachineOperand &Def :MI->defs()) {

1359for (MachineInstr &MI :MRI.use_instructions(Def.getReg())) {

1360if (MI.getParent() != BB) {

1361phi(Def.getReg());

1362break;

1363 }

1364 }

1365 }

1366 }

1367}

1368

1369Register KernelRewriter::remapUse(Register Reg,MachineInstr &MI) {

1370MachineInstr *Producer =MRI.getUniqueVRegDef(Reg);

1371if (!Producer)

1372returnReg;

1373

1374int ConsumerStage = S.getStage(&MI);

1375if (!Producer->isPHI()) {

1376// Non-phi producers are simple to remap. Insert as many phis as the

1377// difference between the consumer and producer stages.

1378if (Producer->getParent() != BB)

1379// Producer was not inside the loop. Use the register as-is.

1380returnReg;

1381int ProducerStage = S.getStage(Producer);

1382assert(ConsumerStage != -1 &&

1383"In-loop consumer should always be scheduled!");

1384assert(ConsumerStage >= ProducerStage);

1385unsigned StageDiff = ConsumerStage - ProducerStage;

1386

1387for (unsignedI = 0;I < StageDiff; ++I)

1388 Reg =phi(Reg);

1389returnReg;

1390 }

1391

1392// First, dive through the phi chain to find the defaults for the generated

1393// phis.

1394SmallVector<std::optional<Register>, 4> Defaults;

1395Register LoopReg =Reg;

1396auto LoopProducer =Producer;

1397while (LoopProducer->isPHI() && LoopProducer->getParent() == BB) {

1398 LoopReg =getLoopPhiReg(*LoopProducer, BB);

1399 Defaults.emplace_back(getInitPhiReg(*LoopProducer, BB));

1400 LoopProducer =MRI.getUniqueVRegDef(LoopReg);

1401assert(LoopProducer);

1402 }

1403int LoopProducerStage = S.getStage(LoopProducer);

1404

1405 std::optional<Register> IllegalPhiDefault;

1406

1407if (LoopProducerStage == -1) {

1408// Do nothing.

1409 }elseif (LoopProducerStage > ConsumerStage) {

1410// This schedule is only representable if ProducerStage == ConsumerStage+1.

1411// In addition, Consumer's cycle must be scheduled after Producer in the

1412// rescheduled loop. This is enforced by the pipeliner's ASAP and ALAP

1413// functions.

1414#ifndef NDEBUG// Silence unused variables in non-asserts mode.

1415int LoopProducerCycle = S.getCycle(LoopProducer);

1416int ConsumerCycle = S.getCycle(&MI);

1417#endif

1418assert(LoopProducerCycle <= ConsumerCycle);

1419assert(LoopProducerStage == ConsumerStage + 1);

1420// Peel off the first phi from Defaults and insert a phi between producer

1421// and consumer. This phi will not be at the front of the block so we

1422// consider it illegal. It will only exist during the rewrite process; it

1423// needs to exist while we peel off prologs because these could take the

1424// default value. After that we can replace all uses with the loop producer

1425// value.

1426 IllegalPhiDefault = Defaults.front();

1427 Defaults.erase(Defaults.begin());

1428 }else {

1429assert(ConsumerStage >= LoopProducerStage);

1430int StageDiff = ConsumerStage - LoopProducerStage;

1431if (StageDiff > 0) {

1432LLVM_DEBUG(dbgs() <<" -- padding defaults array from " << Defaults.size()

1433 <<" to " << (Defaults.size() + StageDiff) <<"\n");

1434// If we need more phis than we have defaults for, pad out with undefs for

1435// the earliest phis, which are at the end of the defaults chain (the

1436// chain is in reverse order).

1437 Defaults.resize(Defaults.size() + StageDiff,

1438 Defaults.empty() ? std::optional<Register>()

1439 : Defaults.back());

1440 }

1441 }

1442

1443// Now we know the number of stages to jump back, insert the phi chain.

1444auto DefaultI = Defaults.rbegin();

1445while (DefaultI != Defaults.rend())

1446 LoopReg =phi(LoopReg, *DefaultI++,MRI.getRegClass(Reg));

1447

1448if (IllegalPhiDefault) {

1449// The consumer optionally consumes LoopProducer in the same iteration

1450// (because the producer is scheduled at an earlier cycle than the consumer)

1451// or the initial value. To facilitate this we create an illegal block here

1452// by embedding a phi in the middle of the block. We will fix this up

1453// immediately prior to pruning.

1454auto RC =MRI.getRegClass(Reg);

1455Register R =MRI.createVirtualRegister(RC);

1456MachineInstr *IllegalPhi =

1457BuildMI(*BB,MI,DebugLoc(),TII->get(TargetOpcode::PHI), R)

1458 .addReg(*IllegalPhiDefault)

1459 .addMBB(PreheaderBB)// Block choice is arbitrary and has no effect.

1460 .addReg(LoopReg)

1461 .addMBB(BB);// Block choice is arbitrary and has no effect.

1462// Illegal phi should belong to the producer stage so that it can be

1463// filtered correctly during peeling.

1464 S.setStage(IllegalPhi, LoopProducerStage);

1465returnR;

1466 }

1467

1468return LoopReg;

1469}

1470

1471Register KernelRewriter::phi(Register LoopReg, std::optional<Register> InitReg,

1472constTargetRegisterClass *RC) {

1473// If the init register is not undef, try and find an existing phi.

1474if (InitReg) {

1475autoI = Phis.find({LoopReg, *InitReg});

1476if (I != Phis.end())

1477returnI->second;

1478 }else {

1479for (auto &KV : Phis) {

1480if (KV.first.first == LoopReg)

1481return KV.second;

1482 }

1483 }

1484

1485// InitReg is either undef or no existing phi takes InitReg as input. Try and

1486// find a phi that takes undef as input.

1487autoI = UndefPhis.find(LoopReg);

1488if (I != UndefPhis.end()) {

1489Register R =I->second;

1490if (!InitReg)

1491// Found a phi taking undef as input, and this input is undef so return

1492// without any more changes.

1493returnR;

1494// Found a phi taking undef as input, so rewrite it to take InitReg.

1495MachineInstr *MI =MRI.getVRegDef(R);

1496MI->getOperand(1).setReg(*InitReg);

1497 Phis.insert({{LoopReg, *InitReg},R});

1498constTargetRegisterClass *ConstrainRegClass =

1499MRI.constrainRegClass(R,MRI.getRegClass(*InitReg));

1500assert(ConstrainRegClass &&"Expected a valid constrained register class!");

1501 (void)ConstrainRegClass;

1502 UndefPhis.erase(I);

1503returnR;

1504 }

1505

1506// Failed to find any existing phi to reuse, so create a new one.

1507if (!RC)

1508 RC =MRI.getRegClass(LoopReg);

1509Register R =MRI.createVirtualRegister(RC);

1510if (InitReg) {

1511constTargetRegisterClass *ConstrainRegClass =

1512MRI.constrainRegClass(R,MRI.getRegClass(*InitReg));

1513assert(ConstrainRegClass &&"Expected a valid constrained register class!");

1514 (void)ConstrainRegClass;

1515 }

1516BuildMI(*BB, BB->getFirstNonPHI(),DebugLoc(),TII->get(TargetOpcode::PHI), R)

1517 .addReg(InitReg ? *InitReg : undef(RC))

1518 .addMBB(PreheaderBB)

1519 .addReg(LoopReg)

1520 .addMBB(BB);

1521if (!InitReg)

1522 UndefPhis[LoopReg] =R;

1523else

1524 Phis[{LoopReg, *InitReg}] =R;

1525returnR;

1526}

1527

1528Register KernelRewriter::undef(constTargetRegisterClass *RC) {

1529Register &R = Undefs[RC];

1530if (R == 0) {

1531// Create an IMPLICIT_DEF that defines this register if we need it.

1532// All uses of this should be removed by the time we have finished unrolling

1533// prologs and epilogs.

1534R =MRI.createVirtualRegister(RC);

1535auto *InsertBB = &PreheaderBB->getParent()->front();

1536BuildMI(*InsertBB, InsertBB->getFirstTerminator(),DebugLoc(),

1537TII->get(TargetOpcode::IMPLICIT_DEF), R);

1538 }

1539returnR;

1540}

1541

1542namespace{

1543/// Describes an operand in the kernel of a pipelined loop. Characteristics of

1544/// the operand are discovered, such as how many in-loop PHIs it has to jump

1545/// through and defaults for these phis.

1546classKernelOperandInfo {

1547MachineBasicBlock *BB;

1548MachineRegisterInfo &MRI;

1549SmallVector<Register, 4> PhiDefaults;

1550MachineOperand *Source;

1551MachineOperand *Target;

1552

1553public:

1554 KernelOperandInfo(MachineOperand *MO,MachineRegisterInfo &MRI,

1555constSmallPtrSetImpl<MachineInstr *> &IllegalPhis)

1556 :MRI(MRI) {

1557Source = MO;

1558 BB = MO->getParent()->getParent();

1559while (isRegInLoop(MO)) {

1560MachineInstr *MI =MRI.getVRegDef(MO->getReg());

1561if (MI->isFullCopy()) {

1562 MO = &MI->getOperand(1);

1563continue;

1564 }

1565if (!MI->isPHI())

1566break;

1567// If this is an illegal phi, don't count it in distance.

1568if (IllegalPhis.count(MI)) {

1569 MO = &MI->getOperand(3);

1570continue;

1571 }

1572

1573Register Default =getInitPhiReg(*MI, BB);

1574 MO =MI->getOperand(2).getMBB() == BB ? &MI->getOperand(1)

1575 : &MI->getOperand(3);

1576 PhiDefaults.push_back(Default);

1577 }

1578Target = MO;

1579 }

1580

1581booloperator==(const KernelOperandInfo &Other) const{

1582return PhiDefaults.size() ==Other.PhiDefaults.size();

1583 }

1584

1585voidprint(raw_ostream &OS) const{

1586OS <<"use of " << *Source <<": distance(" << PhiDefaults.size() <<") in "

1587 << *Source->getParent();

1588 }

1589

1590private:

1591bool isRegInLoop(MachineOperand *MO) {

1592return MO->isReg() && MO->getReg().isVirtual() &&

1593MRI.getVRegDef(MO->getReg())->getParent() == BB;

1594 }

1595};

1596}// namespace

1597

1598MachineBasicBlock *

1599PeelingModuloScheduleExpander::peelKernel(LoopPeelDirection LPD) {

1600MachineBasicBlock *NewBB =PeelSingleBlockLoop(LPD,BB,MRI,TII);

1601if (LPD ==LPD_Front)

1602PeeledFront.push_back(NewBB);

1603else

1604PeeledBack.push_front(NewBB);

1605for (autoI =BB->begin(), NI = NewBB->begin(); !I->isTerminator();

1606 ++I, ++NI) {

1607CanonicalMIs[&*I] = &*I;

1608CanonicalMIs[&*NI] = &*I;

1609BlockMIs[{NewBB, &*I}] = &*NI;

1610BlockMIs[{BB, &*I}] = &*I;

1611 }

1612return NewBB;

1613}

1614

1615voidPeelingModuloScheduleExpander::filterInstructions(MachineBasicBlock *MB,

1616int MinStage) {

1617for (autoI = MB->getFirstInstrTerminator()->getReverseIterator();

1618I != std::next(MB->getFirstNonPHI()->getReverseIterator());) {

1619MachineInstr *MI = &*I++;

1620int Stage =getStage(MI);

1621if (Stage == -1 || Stage >= MinStage)

1622continue;

1623

1624for (MachineOperand &DefMO :MI->defs()) {

1625SmallVector<std::pair<MachineInstr *, Register>, 4> Subs;

1626for (MachineInstr &UseMI :MRI.use_instructions(DefMO.getReg())) {

1627// Only PHIs can use values from this block by construction.

1628// Match with the equivalent PHI in B.

1629assert(UseMI.isPHI());

1630Register Reg =getEquivalentRegisterIn(UseMI.getOperand(0).getReg(),

1631MI->getParent());

1632 Subs.emplace_back(&UseMI, Reg);

1633 }

1634for (auto &Sub : Subs)

1635 Sub.first->substituteRegister(DefMO.getReg(), Sub.second,/*SubIdx=*/0,

1636 *MRI.getTargetRegisterInfo());

1637 }

1638if (LIS)

1639LIS->RemoveMachineInstrFromMaps(*MI);

1640MI->eraseFromParent();

1641 }

1642}

1643

1644voidPeelingModuloScheduleExpander::moveStageBetweenBlocks(

1645MachineBasicBlock *DestBB,MachineBasicBlock *SourceBB,unsigned Stage) {

1646auto InsertPt = DestBB->getFirstNonPHI();

1647DenseMap<Register, Register> Remaps;

1648for (MachineInstr &MI :llvm::make_early_inc_range(

1649llvm::make_range(SourceBB->getFirstNonPHI(), SourceBB->end()))) {

1650if (MI.isPHI()) {

1651// This is an illegal PHI. If we move any instructions using an illegal

1652// PHI, we need to create a legal Phi.

1653if (getStage(&MI) != Stage) {

1654// The legal Phi is not necessary if the illegal phi's stage

1655// is being moved.

1656Register PhiR =MI.getOperand(0).getReg();

1657auto RC =MRI.getRegClass(PhiR);

1658Register NR =MRI.createVirtualRegister(RC);

1659MachineInstr *NI =BuildMI(*DestBB, DestBB->getFirstNonPHI(),

1660DebugLoc(),TII->get(TargetOpcode::PHI), NR)

1661 .addReg(PhiR)

1662 .addMBB(SourceBB);

1663BlockMIs[{DestBB,CanonicalMIs[&MI]}] = NI;

1664CanonicalMIs[NI] =CanonicalMIs[&MI];

1665 Remaps[PhiR] = NR;

1666 }

1667 }

1668if (getStage(&MI) != Stage)

1669continue;

1670MI.removeFromParent();

1671 DestBB->insert(InsertPt, &MI);

1672auto *KernelMI =CanonicalMIs[&MI];

1673BlockMIs[{DestBB, KernelMI}] = &MI;

1674BlockMIs.erase({SourceBB, KernelMI});

1675 }

1676SmallVector<MachineInstr *, 4> PhiToDelete;

1677for (MachineInstr &MI : DestBB->phis()) {

1678assert(MI.getNumOperands() == 3);

1679MachineInstr *Def =MRI.getVRegDef(MI.getOperand(1).getReg());

1680// If the instruction referenced by the phi is moved inside the block

1681// we don't need the phi anymore.

1682if (getStage(Def) == Stage) {

1683Register PhiReg =MI.getOperand(0).getReg();

1684assert(Def->findRegisterDefOperandIdx(MI.getOperand(1).getReg(),

1685/*TRI=*/nullptr) != -1);

1686MRI.replaceRegWith(MI.getOperand(0).getReg(),MI.getOperand(1).getReg());

1687MI.getOperand(0).setReg(PhiReg);

1688 PhiToDelete.push_back(&MI);

1689 }

1690 }

1691for (auto *P : PhiToDelete)

1692P->eraseFromParent();

1693 InsertPt = DestBB->getFirstNonPHI();

1694// Helper to clone Phi instructions into the destination block. We clone Phi

1695// greedily to avoid combinatorial explosion of Phi instructions.

1696auto clonePhi = [&](MachineInstr *Phi) {

1697MachineInstr *NewMI =MF.CloneMachineInstr(Phi);

1698 DestBB->insert(InsertPt, NewMI);

1699Register OrigR = Phi->getOperand(0).getReg();

1700Register R =MRI.createVirtualRegister(MRI.getRegClass(OrigR));

1701 NewMI->getOperand(0).setReg(R);

1702 NewMI->getOperand(1).setReg(OrigR);

1703 NewMI->getOperand(2).setMBB(*DestBB->pred_begin());

1704 Remaps[OrigR] = R;

1705CanonicalMIs[NewMI] =CanonicalMIs[Phi];

1706BlockMIs[{DestBB,CanonicalMIs[Phi]}] = NewMI;

1707PhiNodeLoopIteration[NewMI] =PhiNodeLoopIteration[Phi];

1708return R;

1709 };

1710for (autoI = DestBB->getFirstNonPHI();I != DestBB->end(); ++I) {

1711for (MachineOperand &MO :I->uses()) {

1712if (!MO.isReg())

1713continue;

1714if (auto It = Remaps.find(MO.getReg()); It != Remaps.end())

1715 MO.setReg(It->second);

1716else {

1717// If we are using a phi from the source block we need to add a new phi

1718// pointing to the old one.

1719MachineInstr *Use =MRI.getUniqueVRegDef(MO.getReg());

1720if (Use &&Use->isPHI() &&Use->getParent() == SourceBB) {

1721Register R = clonePhi(Use);

1722 MO.setReg(R);

1723 }

1724 }

1725 }

1726 }

1727}

1728

1729Register

1730PeelingModuloScheduleExpander::getPhiCanonicalReg(MachineInstr *CanonicalPhi,

1731MachineInstr *Phi) {

1732unsigned distance =PhiNodeLoopIteration[Phi];

1733MachineInstr *CanonicalUse = CanonicalPhi;

1734Register CanonicalUseReg = CanonicalUse->getOperand(0).getReg();

1735for (unsignedI = 0;I < distance; ++I) {

1736assert(CanonicalUse->isPHI());

1737assert(CanonicalUse->getNumOperands() == 5);

1738unsigned LoopRegIdx = 3, InitRegIdx = 1;

1739if (CanonicalUse->getOperand(2).getMBB() == CanonicalUse->getParent())

1740std::swap(LoopRegIdx, InitRegIdx);

1741 CanonicalUseReg = CanonicalUse->getOperand(LoopRegIdx).getReg();

1742 CanonicalUse =MRI.getVRegDef(CanonicalUseReg);

1743 }

1744return CanonicalUseReg;

1745}

1746

1747voidPeelingModuloScheduleExpander::peelPrologAndEpilogs() {

1748BitVector LS(Schedule.getNumStages(),true);

1749BitVector AS(Schedule.getNumStages(),true);

1750LiveStages[BB] = LS;

1751AvailableStages[BB] = AS;

1752

1753// Peel out the prologs.

1754 LS.reset();

1755for (intI = 0;I <Schedule.getNumStages() - 1; ++I) {

1756 LS[I] =true;

1757Prologs.push_back(peelKernel(LPD_Front));

1758LiveStages[Prologs.back()] = LS;

1759AvailableStages[Prologs.back()] = LS;

1760 }

1761

1762// Create a block that will end up as the new loop exiting block (dominated by

1763// all prologs and epilogs). It will only contain PHIs, in the same order as

1764// BB's PHIs. This gives us a poor-man's LCSSA with the inductive property

1765// that the exiting block is a (sub) clone of BB. This in turn gives us the

1766// property that any value deffed in BB but used outside of BB is used by a

1767// PHI in the exiting block.

1768MachineBasicBlock *ExitingBB =CreateLCSSAExitingBlock();

1769 EliminateDeadPhis(ExitingBB,MRI,LIS,/*KeepSingleSrcPhi=*/true);

1770// Push out the epilogs, again in reverse order.

1771// We can't assume anything about the minumum loop trip count at this point,

1772// so emit a fairly complex epilog.

1773

1774// We first peel number of stages minus one epilogue. Then we remove dead

1775// stages and reorder instructions based on their stage. If we have 3 stages

1776// we generate first:

1777// E0[3, 2, 1]

1778// E1[3', 2']

1779// E2[3'']

1780// And then we move instructions based on their stages to have:

1781// E0[3]

1782// E1[2, 3']

1783// E2[1, 2', 3'']

1784// The transformation is legal because we only move instructions past

1785// instructions of a previous loop iteration.

1786for (intI = 1;I <=Schedule.getNumStages() - 1; ++I) {

1787Epilogs.push_back(peelKernel(LPD_Back));

1788MachineBasicBlock *B =Epilogs.back();

1789filterInstructions(B,Schedule.getNumStages() -I);

1790// Keep track at which iteration each phi belongs to. We need it to know

1791// what version of the variable to use during prologue/epilogue stitching.

1792 EliminateDeadPhis(B,MRI,LIS,/*KeepSingleSrcPhi=*/true);

1793for (MachineInstr &Phi :B->phis())

1794PhiNodeLoopIteration[&Phi] =Schedule.getNumStages() -I;

1795 }

1796for (size_tI = 0;I <Epilogs.size();I++) {

1797 LS.reset();

1798for (size_t J =I; J <Epilogs.size(); J++) {

1799int Iteration = J;

1800unsigned Stage =Schedule.getNumStages() - 1 +I - J;

1801// Move stage one block at a time so that Phi nodes are updated correctly.

1802for (size_t K = Iteration; K >I; K--)

1803moveStageBetweenBlocks(Epilogs[K - 1],Epilogs[K], Stage);

1804 LS[Stage] =true;

1805 }

1806LiveStages[Epilogs[I]] = LS;

1807AvailableStages[Epilogs[I]] = AS;

1808 }

1809

1810// Now we've defined all the prolog and epilog blocks as a fallthrough

1811// sequence, add the edges that will be followed if the loop trip count is

1812// lower than the number of stages (connecting prologs directly with epilogs).

1813auto PI =Prologs.begin();

1814auto EI =Epilogs.begin();

1815assert(Prologs.size() ==Epilogs.size());

1816for (; PI !=Prologs.end(); ++PI, ++EI) {

1817MachineBasicBlock *Pred = *(*EI)->pred_begin();

1818 (*PI)->addSuccessor(*EI);

1819for (MachineInstr &MI : (*EI)->phis()) {

1820Register Reg =MI.getOperand(1).getReg();

1821MachineInstr *Use =MRI.getUniqueVRegDef(Reg);

1822if (Use &&Use->getParent() == Pred) {

1823MachineInstr *CanonicalUse =CanonicalMIs[Use];

1824if (CanonicalUse->isPHI()) {

1825// If the use comes from a phi we need to skip as many phi as the

1826// distance between the epilogue and the kernel. Trace through the phi

1827// chain to find the right value.

1828 Reg =getPhiCanonicalReg(CanonicalUse,Use);

1829 }

1830 Reg =getEquivalentRegisterIn(Reg, *PI);

1831 }

1832MI.addOperand(MachineOperand::CreateReg(Reg,/*isDef=*/false));

1833MI.addOperand(MachineOperand::CreateMBB(*PI));

1834 }

1835 }

1836

1837// Create a list of all blocks in order.

1838SmallVector<MachineBasicBlock *, 8>Blocks;

1839llvm::copy(PeeledFront, std::back_inserter(Blocks));

1840Blocks.push_back(BB);

1841llvm::copy(PeeledBack, std::back_inserter(Blocks));

1842

1843// Iterate in reverse order over all instructions, remapping as we go.

1844for (MachineBasicBlock *B :reverse(Blocks)) {

1845for (autoI =B->instr_rbegin();

1846I != std::next(B->getFirstNonPHI()->getReverseIterator());) {

1847MachineBasicBlock::reverse_instr_iterator MI =I++;

1848rewriteUsesOf(&*MI);

1849 }

1850 }

1851for (auto *MI :IllegalPhisToDelete) {

1852if (LIS)

1853LIS->RemoveMachineInstrFromMaps(*MI);

1854MI->eraseFromParent();

1855 }

1856IllegalPhisToDelete.clear();

1857

1858// Now all remapping has been done, we're free to optimize the generated code.

1859for (MachineBasicBlock *B :reverse(Blocks))

1860 EliminateDeadPhis(B,MRI,LIS);

1861 EliminateDeadPhis(ExitingBB,MRI,LIS);

1862}

1863

1864MachineBasicBlock *PeelingModuloScheduleExpander::CreateLCSSAExitingBlock() {

1865MachineFunction &MF = *BB->getParent();

1866MachineBasicBlock *Exit = *BB->succ_begin();

1867if (Exit ==BB)

1868 Exit = *std::next(BB->succ_begin());

1869

1870MachineBasicBlock *NewBB =MF.CreateMachineBasicBlock(BB->getBasicBlock());

1871MF.insert(std::next(BB->getIterator()), NewBB);

1872

1873// Clone all phis in BB into NewBB and rewrite.

1874for (MachineInstr &MI :BB->phis()) {

1875auto RC =MRI.getRegClass(MI.getOperand(0).getReg());

1876Register OldR =MI.getOperand(3).getReg();

1877Register R =MRI.createVirtualRegister(RC);

1878SmallVector<MachineInstr *, 4>Uses;

1879for (MachineInstr &Use :MRI.use_instructions(OldR))

1880if (Use.getParent() !=BB)

1881Uses.push_back(&Use);

1882for (MachineInstr *Use :Uses)

1883Use->substituteRegister(OldR, R,/*SubIdx=*/0,

1884 *MRI.getTargetRegisterInfo());

1885MachineInstr *NI =BuildMI(NewBB,DebugLoc(),TII->get(TargetOpcode::PHI), R)

1886 .addReg(OldR)

1887 .addMBB(BB);

1888BlockMIs[{NewBB, &MI}] = NI;

1889CanonicalMIs[NI] = &MI;

1890 }

1891BB->replaceSuccessor(Exit, NewBB);

1892 Exit->replacePhiUsesWith(BB, NewBB);

1893 NewBB->addSuccessor(Exit);

1894

1895MachineBasicBlock *TBB =nullptr, *FBB =nullptr;

1896SmallVector<MachineOperand, 4>Cond;

1897bool CanAnalyzeBr = !TII->analyzeBranch(*BB,TBB, FBB,Cond);

1898 (void)CanAnalyzeBr;

1899assert(CanAnalyzeBr &&"Must be able to analyze the loop branch!");

1900TII->removeBranch(*BB);

1901TII->insertBranch(*BB,TBB == Exit ? NewBB :TBB, FBB == Exit ? NewBB : FBB,

1902Cond,DebugLoc());

1903TII->insertUnconditionalBranch(*NewBB, Exit,DebugLoc());

1904return NewBB;

1905}

1906

1907Register

1908PeelingModuloScheduleExpander::getEquivalentRegisterIn(Register Reg,

1909MachineBasicBlock *BB) {

1910MachineInstr *MI =MRI.getUniqueVRegDef(Reg);

1911unsigned OpIdx =MI->findRegisterDefOperandIdx(Reg,/*TRI=*/nullptr);

1912returnBlockMIs[{BB,CanonicalMIs[MI]}]->getOperand(OpIdx).getReg();

1913}

1914

1915voidPeelingModuloScheduleExpander::rewriteUsesOf(MachineInstr *MI) {

1916if (MI->isPHI()) {

1917// This is an illegal PHI. The loop-carried (desired) value is operand 3,

1918// and it is produced by this block.

1919Register PhiR =MI->getOperand(0).getReg();

1920Register R =MI->getOperand(3).getReg();

1921int RMIStage =getStage(MRI.getUniqueVRegDef(R));

1922if (RMIStage != -1 && !AvailableStages[MI->getParent()].test(RMIStage))

1923 R =MI->getOperand(1).getReg();

1924MRI.setRegClass(R,MRI.getRegClass(PhiR));

1925MRI.replaceRegWith(PhiR, R);

1926// Postpone deleting the Phi as it may be referenced by BlockMIs and used

1927// later to figure out how to remap registers.

1928MI->getOperand(0).setReg(PhiR);

1929IllegalPhisToDelete.push_back(MI);

1930return;

1931 }

1932

1933int Stage =getStage(MI);

1934if (Stage == -1 ||LiveStages.count(MI->getParent()) == 0 ||

1935LiveStages[MI->getParent()].test(Stage))

1936// Instruction is live, no rewriting to do.

1937return;

1938

1939for (MachineOperand &DefMO :MI->defs()) {

1940SmallVector<std::pair<MachineInstr *, Register>, 4> Subs;

1941for (MachineInstr &UseMI :MRI.use_instructions(DefMO.getReg())) {

1942// Only PHIs can use values from this block by construction.

1943// Match with the equivalent PHI in B.

1944assert(UseMI.isPHI());

1945Register Reg =getEquivalentRegisterIn(UseMI.getOperand(0).getReg(),

1946MI->getParent());

1947 Subs.emplace_back(&UseMI, Reg);

1948 }

1949for (auto &Sub : Subs)

1950 Sub.first->substituteRegister(DefMO.getReg(), Sub.second,/*SubIdx=*/0,

1951 *MRI.getTargetRegisterInfo());

1952 }

1953if (LIS)

1954LIS->RemoveMachineInstrFromMaps(*MI);

1955MI->eraseFromParent();

1956}

1957

1958voidPeelingModuloScheduleExpander::fixupBranches() {

1959// Work outwards from the kernel.

1960bool KernelDisposed =false;

1961int TC =Schedule.getNumStages() - 1;

1962for (auto PI =Prologs.rbegin(), EI =Epilogs.rbegin(); PI !=Prologs.rend();

1963 ++PI, ++EI, --TC) {

1964MachineBasicBlock *Prolog = *PI;

1965MachineBasicBlock *Fallthrough = *Prolog->succ_begin();

1966MachineBasicBlock *Epilog = *EI;

1967SmallVector<MachineOperand, 4>Cond;

1968TII->removeBranch(*Prolog);

1969 std::optional<bool> StaticallyGreater =

1970LoopInfo->createTripCountGreaterCondition(TC, *Prolog,Cond);

1971if (!StaticallyGreater) {

1972LLVM_DEBUG(dbgs() <<"Dynamic: TC > " << TC <<"\n");

1973// Dynamically branch based on Cond.

1974TII->insertBranch(*Prolog,Epilog, Fallthrough,Cond,DebugLoc());

1975 }elseif (*StaticallyGreater ==false) {

1976LLVM_DEBUG(dbgs() <<"Static-false: TC > " << TC <<"\n");

1977// Prolog never falls through; branch to epilog and orphan interior

1978// blocks. Leave it to unreachable-block-elim to clean up.

1979Prolog->removeSuccessor(Fallthrough);

1980for (MachineInstr &P : Fallthrough->phis()) {

1981P.removeOperand(2);

1982P.removeOperand(1);

1983 }

1984TII->insertUnconditionalBranch(*Prolog,Epilog,DebugLoc());

1985 KernelDisposed =true;

1986 }else {

1987LLVM_DEBUG(dbgs() <<"Static-true: TC > " << TC <<"\n");

1988// Prolog always falls through; remove incoming values in epilog.

1989Prolog->removeSuccessor(Epilog);

1990for (MachineInstr &P :Epilog->phis()) {

1991P.removeOperand(4);

1992P.removeOperand(3);

1993 }

1994 }

1995 }

1996

1997if (!KernelDisposed) {

1998LoopInfo->adjustTripCount(-(Schedule.getNumStages() - 1));

1999LoopInfo->setPreheader(Prologs.back());

2000 }else {

2001LoopInfo->disposed();

2002 }

2003}

2004

2005voidPeelingModuloScheduleExpander::rewriteKernel() {

2006 KernelRewriter KR(*Schedule.getLoop(),Schedule,BB);

2007 KR.rewrite();

2008}

2009

2010voidPeelingModuloScheduleExpander::expand() {

2011BB =Schedule.getLoop()->getTopBlock();

2012Preheader =Schedule.getLoop()->getLoopPreheader();

2013LLVM_DEBUG(Schedule.dump());

2014LoopInfo =TII->analyzeLoopForPipelining(BB);

2015assert(LoopInfo);

2016

2017rewriteKernel();

2018peelPrologAndEpilogs();

2019fixupBranches();

2020}

2021

2022voidPeelingModuloScheduleExpander::validateAgainstModuloScheduleExpander() {

2023BB =Schedule.getLoop()->getTopBlock();

2024Preheader =Schedule.getLoop()->getLoopPreheader();

2025

2026// Dump the schedule before we invalidate and remap all its instructions.

2027// Stash it in a string so we can print it if we found an error.

2028 std::string ScheduleDump;

2029raw_string_ostream OS(ScheduleDump);

2030Schedule.print(OS);

2031OS.flush();

2032

2033// First, run the normal ModuleScheduleExpander. We don't support any

2034// InstrChanges.

2035assert(LIS &&"Requires LiveIntervals!");

2036ModuloScheduleExpander MSE(MF,Schedule, *LIS,

2037ModuloScheduleExpander::InstrChangesTy());

2038 MSE.expand();

2039MachineBasicBlock *ExpandedKernel = MSE.getRewrittenKernel();

2040if (!ExpandedKernel) {

2041// The expander optimized away the kernel. We can't do any useful checking.

2042 MSE.cleanup();

2043return;

2044 }

2045// Before running the KernelRewriter, re-add BB into the CFG.

2046Preheader->addSuccessor(BB);

2047

2048// Now run the new expansion algorithm.

2049 KernelRewriter KR(*Schedule.getLoop(),Schedule,BB);

2050 KR.rewrite();

2051peelPrologAndEpilogs();

2052

2053// Collect all illegal phis that the new algorithm created. We'll give these

2054// to KernelOperandInfo.

2055SmallPtrSet<MachineInstr *, 4> IllegalPhis;

2056for (auto NI =BB->getFirstNonPHI(); NI !=BB->end(); ++NI) {

2057if (NI->isPHI())

2058 IllegalPhis.insert(&*NI);

2059 }

2060

2061// Co-iterate across both kernels. We expect them to be identical apart from

2062// phis and full COPYs (we look through both).

2063SmallVector<std::pair<KernelOperandInfo, KernelOperandInfo>, 8> KOIs;

2064auto OI = ExpandedKernel->begin();

2065auto NI =BB->begin();

2066for (; !OI->isTerminator() && !NI->isTerminator(); ++OI, ++NI) {

2067while (OI->isPHI() || OI->isFullCopy())

2068 ++OI;

2069while (NI->isPHI() || NI->isFullCopy())

2070 ++NI;

2071assert(OI->getOpcode() == NI->getOpcode() &&"Opcodes don't match?!");

2072// Analyze every operand separately.

2073for (auto OOpI = OI->operands_begin(), NOpI = NI->operands_begin();

2074 OOpI != OI->operands_end(); ++OOpI, ++NOpI)

2075 KOIs.emplace_back(KernelOperandInfo(&*OOpI,MRI, IllegalPhis),

2076 KernelOperandInfo(&*NOpI,MRI, IllegalPhis));

2077 }

2078

2079boolFailed =false;

2080for (auto &OldAndNew : KOIs) {

2081if (OldAndNew.first == OldAndNew.second)

2082continue;

2083Failed =true;

2084errs() <<"Modulo kernel validation error: [\n";

2085errs() <<" [golden] ";

2086 OldAndNew.first.print(errs());

2087errs() <<" ";

2088 OldAndNew.second.print(errs());

2089errs() <<"]\n";

2090 }

2091

2092if (Failed) {

2093errs() <<"Golden reference kernel:\n";

2094 ExpandedKernel->print(errs());

2095errs() <<"New kernel:\n";

2096BB->print(errs());

2097errs() << ScheduleDump;

2098report_fatal_error(

2099"Modulo kernel validation (-pipeliner-experimental-cg) failed");

2100 }

2101

2102// Cleanup by removing BB from the CFG again as the original

2103// ModuloScheduleExpander intended.

2104Preheader->removeSuccessor(BB);

2105 MSE.cleanup();

2106}

2107

2108MachineInstr *ModuloScheduleExpanderMVE::cloneInstr(MachineInstr *OldMI) {

2109MachineInstr *NewMI = MF.CloneMachineInstr(OldMI);

2110

2111// TODO: Offset information needs to be corrected.

2112 NewMI->dropMemRefs(MF);

2113

2114return NewMI;

2115}

2116

2117/// Create a dedicated exit for Loop. Exit is the original exit for Loop.

2118/// If it is already dedicated exit, return it. Otherwise, insert a new

2119/// block between them and return the new block.

2120staticMachineBasicBlock *createDedicatedExit(MachineBasicBlock *Loop,

2121MachineBasicBlock *Exit) {

2122if (Exit->pred_size() == 1)

2123return Exit;

2124

2125MachineFunction *MF =Loop->getParent();

2126constTargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();

2127

2128MachineBasicBlock *NewExit =

2129 MF->CreateMachineBasicBlock(Loop->getBasicBlock());

2130 MF->insert(Loop->getIterator(), NewExit);

2131

2132MachineBasicBlock *TBB =nullptr, *FBB =nullptr;

2133SmallVector<MachineOperand, 4>Cond;

2134TII->analyzeBranch(*Loop,TBB, FBB,Cond);

2135if (TBB ==Loop)

2136 FBB = NewExit;

2137elseif (FBB ==Loop)

2138TBB = NewExit;

2139else

2140llvm_unreachable("unexpected loop structure");

2141TII->removeBranch(*Loop);

2142TII->insertBranch(*Loop,TBB, FBB,Cond,DebugLoc());

2143Loop->replaceSuccessor(Exit, NewExit);

2144TII->insertUnconditionalBranch(*NewExit, Exit,DebugLoc());

2145 NewExit->addSuccessor(Exit);

2146

2147 Exit->replacePhiUsesWith(Loop, NewExit);

2148

2149return NewExit;

2150}

2151

2152/// Insert branch code into the end of MBB. It branches to GreaterThan if the

2153/// remaining trip count for instructions in LastStage0Insts is greater than

2154/// RequiredTC, and to Otherwise otherwise.

2155void ModuloScheduleExpanderMVE::insertCondBranch(MachineBasicBlock &MBB,

2156int RequiredTC,

2157 InstrMapTy &LastStage0Insts,

2158MachineBasicBlock &GreaterThan,

2159MachineBasicBlock &Otherwise) {

2160SmallVector<MachineOperand, 4>Cond;

2161LoopInfo->createRemainingIterationsGreaterCondition(RequiredTC,MBB,Cond,

2162 LastStage0Insts);

2163

2164if (SwapBranchTargetsMVE) {

2165// Set SwapBranchTargetsMVE to true if a target prefers to replace TBB and

2166// FBB for optimal performance.

2167if (TII->reverseBranchCondition(Cond))

2168llvm_unreachable("can not reverse branch condition");

2169 TII->insertBranch(MBB, &Otherwise, &GreaterThan,Cond,DebugLoc());

2170 }else {

2171 TII->insertBranch(MBB, &GreaterThan, &Otherwise,Cond,DebugLoc());

2172 }

2173}

2174

2175/// Generate a pipelined loop that is unrolled by using MVE algorithm and any

2176/// other necessary blocks. The control flow is modified to execute the

2177/// pipelined loop if the trip count satisfies the condition, otherwise the

2178/// original loop. The original loop is also used to execute the remainder

2179/// iterations which occur due to unrolling.

2180void ModuloScheduleExpanderMVE::generatePipelinedLoop() {

2181// The control flow for pipelining with MVE:

2182//

2183// OrigPreheader:

2184// // The block that is originally the loop preheader

2185// goto Check

2186//

2187// Check:

2188// // Check whether the trip count satisfies the requirements to pipeline.

2189// if (LoopCounter > NumStages + NumUnroll - 2)

2190// // The minimum number of iterations to pipeline =

2191// // iterations executed in prolog/epilog (NumStages-1) +

2192// // iterations executed in one kernel run (NumUnroll)

2193// goto Prolog

2194// // fallback to the original loop

2195// goto NewPreheader

2196//

2197// Prolog:

2198// // All prolog stages. There are no direct branches to the epilogue.

2199// goto NewKernel

2200//

2201// NewKernel:

2202// // NumUnroll copies of the kernel

2203// if (LoopCounter > MVE-1)

2204// goto NewKernel

2205// goto Epilog

2206//

2207// Epilog:

2208// // All epilog stages.

2209// if (LoopCounter > 0)

2210// // The remainder is executed in the original loop

2211// goto NewPreheader

2212// goto NewExit

2213//

2214// NewPreheader:

2215// // Newly created preheader for the original loop.

2216// // The initial values of the phis in the loop are merged from two paths.

2217// NewInitVal = Phi OrigInitVal, Check, PipelineLastVal, Epilog

2218// goto OrigKernel

2219//

2220// OrigKernel:

2221// // The original loop block.

2222// if (LoopCounter != 0)

2223// goto OrigKernel

2224// goto NewExit

2225//

2226// NewExit:

2227// // Newly created dedicated exit for the original loop.

2228// // Merge values which are referenced after the loop

2229// Merged = Phi OrigVal, OrigKernel, PipelineVal, Epilog

2230// goto OrigExit

2231//

2232// OrigExit:

2233// // The block that is originally the loop exit.

2234// // If it is already deicated exit, NewExit is not created.

2235

2236// An example of where each stage is executed:

2237// Assume #Stages 3, #MVE 4, #Iterations 12

2238// Iter 0 1 2 3 4 5 6 7 8 9 10-11

2239// -------------------------------------------------

2240// Stage 0 Prolog#0

2241// Stage 1 0 Prolog#1

2242// Stage 2 1 0 Kernel Unroll#0 Iter#0

2243// Stage 2 1 0 Kernel Unroll#1 Iter#0

2244// Stage 2 1 0 Kernel Unroll#2 Iter#0

2245// Stage 2 1 0 Kernel Unroll#3 Iter#0

2246// Stage 2 1 0 Kernel Unroll#0 Iter#1

2247// Stage 2 1 0 Kernel Unroll#1 Iter#1

2248// Stage 2 1 0 Kernel Unroll#2 Iter#1

2249// Stage 2 1 0 Kernel Unroll#3 Iter#1

2250// Stage 2 1 Epilog#0

2251// Stage 2 Epilog#1

2252// Stage 0-2 OrigKernel

2253

2254LoopInfo = TII->analyzeLoopForPipelining(OrigKernel);

2255assert(LoopInfo &&"Must be able to analyze loop!");

2256

2257 calcNumUnroll();

2258

2259 Check = MF.CreateMachineBasicBlock(OrigKernel->getBasicBlock());

2260Prolog = MF.CreateMachineBasicBlock(OrigKernel->getBasicBlock());

2261 NewKernel = MF.CreateMachineBasicBlock(OrigKernel->getBasicBlock());

2262Epilog = MF.CreateMachineBasicBlock(OrigKernel->getBasicBlock());

2263 NewPreheader = MF.CreateMachineBasicBlock(OrigKernel->getBasicBlock());

2264

2265 MF.insert(OrigKernel->getIterator(), Check);

2266 MF.insert(OrigKernel->getIterator(), Prolog);

2267 MF.insert(OrigKernel->getIterator(), NewKernel);

2268 MF.insert(OrigKernel->getIterator(), Epilog);

2269 MF.insert(OrigKernel->getIterator(), NewPreheader);

2270

2271 NewExit =createDedicatedExit(OrigKernel, OrigExit);

2272

2273 NewPreheader->transferSuccessorsAndUpdatePHIs(OrigPreheader);

2274 TII->insertUnconditionalBranch(*NewPreheader, OrigKernel,DebugLoc());

2275

2276 OrigPreheader->addSuccessor(Check);

2277 TII->removeBranch(*OrigPreheader);

2278 TII->insertUnconditionalBranch(*OrigPreheader, Check,DebugLoc());

2279

2280 Check->addSuccessor(Prolog);

2281 Check->addSuccessor(NewPreheader);

2282

2283Prolog->addSuccessor(NewKernel);

2284

2285 NewKernel->addSuccessor(NewKernel);

2286 NewKernel->addSuccessor(Epilog);

2287

2288Epilog->addSuccessor(NewPreheader);

2289Epilog->addSuccessor(NewExit);

2290

2291 InstrMapTy LastStage0Insts;

2292 insertCondBranch(*Check, Schedule.getNumStages() + NumUnroll - 2,

2293 LastStage0Insts, *Prolog, *NewPreheader);

2294

2295// VRMaps map (prolog/kernel/epilog phase#, original register#) to new

2296// register#

2297SmallVector<ValueMapTy> PrologVRMap, KernelVRMap, EpilogVRMap;

2298 generateProlog(PrologVRMap);

2299 generateKernel(PrologVRMap, KernelVRMap, LastStage0Insts);

2300 generateEpilog(KernelVRMap, EpilogVRMap, LastStage0Insts);

2301}

2302

2303/// Replace MI's use operands according to the maps.

2304void ModuloScheduleExpanderMVE::updateInstrUse(

2305MachineInstr *MI,int StageNum,int PhaseNum,

2306SmallVectorImpl<ValueMapTy> &CurVRMap,

2307SmallVectorImpl<ValueMapTy> *PrevVRMap) {

2308// If MI is in the prolog/kernel/epilog block, CurVRMap is

2309// PrologVRMap/KernelVRMap/EpilogVRMap respectively.

2310// PrevVRMap is nullptr/PhiVRMap/KernelVRMap respectively.

2311// Refer to the appropriate map according to the stage difference between

2312// MI and the definition of an operand.

2313

2314for (MachineOperand &UseMO :MI->uses()) {

2315if (!UseMO.isReg() || !UseMO.getReg().isVirtual())

2316continue;

2317int DiffStage = 0;

2318Register OrigReg = UseMO.getReg();

2319MachineInstr *DefInst =MRI.getVRegDef(OrigReg);

2320if (!DefInst || DefInst->getParent() != OrigKernel)

2321continue;

2322unsigned InitReg = 0;

2323unsigned DefReg = OrigReg;

2324if (DefInst->isPHI()) {

2325 ++DiffStage;

2326unsigned LoopReg;

2327getPhiRegs(*DefInst, OrigKernel, InitReg, LoopReg);

2328// LoopReg is guaranteed to be defined within the loop by canApply()

2329 DefReg = LoopReg;

2330 DefInst =MRI.getVRegDef(LoopReg);

2331 }

2332unsigned DefStageNum = Schedule.getStage(DefInst);

2333 DiffStage += StageNum - DefStageNum;

2334Register NewReg;

2335if (PhaseNum >= DiffStage && CurVRMap[PhaseNum - DiffStage].count(DefReg))

2336// NewReg is defined in a previous phase of the same block

2337 NewReg = CurVRMap[PhaseNum - DiffStage][DefReg];

2338elseif (!PrevVRMap)

2339// Since this is the first iteration, refer the initial register of the

2340// loop

2341 NewReg = InitReg;

2342else

2343// Cases where DiffStage is larger than PhaseNum.

2344// If MI is in the kernel block, the value is defined by the previous

2345// iteration and PhiVRMap is referenced. If MI is in the epilog block, the

2346// value is defined in the kernel block and KernelVRMap is referenced.

2347 NewReg = (*PrevVRMap)[PrevVRMap->size() - (DiffStage - PhaseNum)][DefReg];

2348

2349constTargetRegisterClass *NRC =

2350MRI.constrainRegClass(NewReg,MRI.getRegClass(OrigReg));

2351if (NRC)

2352 UseMO.setReg(NewReg);

2353else {

2354Register SplitReg =MRI.createVirtualRegister(MRI.getRegClass(OrigReg));

2355BuildMI(*OrigKernel,MI,MI->getDebugLoc(), TII->get(TargetOpcode::COPY),

2356 SplitReg)

2357 .addReg(NewReg);

2358 UseMO.setReg(SplitReg);

2359 }

2360 }

2361}

2362

2363/// Return a phi if Reg is referenced by the phi.

2364/// canApply() guarantees that at most only one such phi exists.

2365staticMachineInstr *getLoopPhiUser(Register Reg,MachineBasicBlock *Loop) {

2366for (MachineInstr &Phi :Loop->phis()) {

2367unsigned InitVal, LoopVal;

2368getPhiRegs(Phi,Loop, InitVal, LoopVal);

2369if (LoopVal == Reg)

2370return Φ

2371 }

2372returnnullptr;

2373}

2374

2375/// Generate phis for registers defined by OrigMI.

2376void ModuloScheduleExpanderMVE::generatePhi(

2377MachineInstr *OrigMI,int UnrollNum,

2378SmallVectorImpl<ValueMapTy> &PrologVRMap,

2379SmallVectorImpl<ValueMapTy> &KernelVRMap,

2380SmallVectorImpl<ValueMapTy> &PhiVRMap) {

2381int StageNum = Schedule.getStage(OrigMI);

2382bool UsePrologReg;

2383if (Schedule.getNumStages() - NumUnroll + UnrollNum - 1 >= StageNum)

2384 UsePrologReg =true;

2385elseif (Schedule.getNumStages() - NumUnroll + UnrollNum == StageNum)

2386 UsePrologReg =false;

2387else

2388return;

2389

2390// Examples that show which stages are merged by phi.

2391// Meaning of the symbol following the stage number:

2392// a/b: Stages with the same letter are merged (UsePrologReg == true)

2393// +: Merged with the initial value (UsePrologReg == false)

2394// *: No phis required

2395//

2396// #Stages 3, #MVE 4

2397// Iter 0 1 2 3 4 5 6 7 8

2398// -----------------------------------------

2399// Stage 0a Prolog#0

2400// Stage 1a 0b Prolog#1

2401// Stage 2* 1* 0* Kernel Unroll#0

2402// Stage 2* 1* 0+ Kernel Unroll#1

2403// Stage 2* 1+ 0a Kernel Unroll#2

2404// Stage 2+ 1a 0b Kernel Unroll#3

2405//

2406// #Stages 3, #MVE 2

2407// Iter 0 1 2 3 4 5 6 7 8

2408// -----------------------------------------

2409// Stage 0a Prolog#0

2410// Stage 1a 0b Prolog#1

2411// Stage 2* 1+ 0a Kernel Unroll#0

2412// Stage 2+ 1a 0b Kernel Unroll#1

2413//

2414// #Stages 3, #MVE 1

2415// Iter 0 1 2 3 4 5 6 7 8

2416// -----------------------------------------

2417// Stage 0* Prolog#0

2418// Stage 1a 0b Prolog#1

2419// Stage 2+ 1a 0b Kernel Unroll#0

2420

2421for (MachineOperand &DefMO : OrigMI->defs()) {

2422if (!DefMO.isReg() || DefMO.isDead())

2423continue;

2424Register OrigReg = DefMO.getReg();

2425auto NewReg = KernelVRMap[UnrollNum].find(OrigReg);

2426if (NewReg == KernelVRMap[UnrollNum].end())

2427continue;

2428Register CorrespondReg;

2429if (UsePrologReg) {

2430int PrologNum = Schedule.getNumStages() - NumUnroll + UnrollNum - 1;

2431 CorrespondReg = PrologVRMap[PrologNum][OrigReg];

2432 }else {

2433MachineInstr *Phi =getLoopPhiUser(OrigReg, OrigKernel);

2434if (!Phi)

2435continue;

2436 CorrespondReg =getInitPhiReg(*Phi, OrigKernel);

2437 }

2438

2439assert(CorrespondReg.isValid());

2440Register PhiReg =MRI.createVirtualRegister(MRI.getRegClass(OrigReg));

2441BuildMI(*NewKernel, NewKernel->getFirstNonPHI(),DebugLoc(),

2442 TII->get(TargetOpcode::PHI), PhiReg)

2443 .addReg(NewReg->second)

2444 .addMBB(NewKernel)

2445 .addReg(CorrespondReg)

2446 .addMBB(Prolog);

2447 PhiVRMap[UnrollNum][OrigReg] = PhiReg;

2448 }

2449}

2450

2451staticvoidreplacePhiSrc(MachineInstr &Phi,Register OrigReg,Register NewReg,

2452MachineBasicBlock *NewMBB) {

2453for (unsignedIdx = 1;Idx < Phi.getNumOperands();Idx += 2) {

2454if (Phi.getOperand(Idx).getReg() == OrigReg) {

2455 Phi.getOperand(Idx).setReg(NewReg);

2456 Phi.getOperand(Idx + 1).setMBB(NewMBB);

2457return;

2458 }

2459 }

2460}

2461

2462/// Generate phis that merge values from multiple routes

2463void ModuloScheduleExpanderMVE::mergeRegUsesAfterPipeline(Register OrigReg,

2464Register NewReg) {

2465SmallVector<MachineOperand *> UsesAfterLoop;

2466SmallVector<MachineInstr *> LoopPhis;

2467for (MachineRegisterInfo::use_iterator I =MRI.use_begin(OrigReg),

2468 E =MRI.use_end();

2469I != E; ++I) {

2470MachineOperand &O = *I;

2471if (O.getParent()->getParent() != OrigKernel &&

2472O.getParent()->getParent() != Prolog &&

2473O.getParent()->getParent() != NewKernel &&

2474O.getParent()->getParent() != Epilog)

2475 UsesAfterLoop.push_back(&O);

2476if (O.getParent()->getParent() == OrigKernel &&O.getParent()->isPHI())

2477 LoopPhis.push_back(O.getParent());

2478 }

2479

2480// Merge the route that only execute the pipelined loop (when there are no

2481// remaining iterations) with the route that execute the original loop.

2482if (!UsesAfterLoop.empty()) {

2483Register PhiReg =MRI.createVirtualRegister(MRI.getRegClass(OrigReg));

2484BuildMI(*NewExit, NewExit->getFirstNonPHI(),DebugLoc(),

2485 TII->get(TargetOpcode::PHI), PhiReg)

2486 .addReg(OrigReg)

2487 .addMBB(OrigKernel)

2488 .addReg(NewReg)

2489 .addMBB(Epilog);

2490

2491for (MachineOperand *MO : UsesAfterLoop)

2492 MO->setReg(PhiReg);

2493

2494if (!LIS.hasInterval(PhiReg))

2495 LIS.createEmptyInterval(PhiReg);

2496 }

2497

2498// Merge routes from the pipelined loop and the bypassed route before the

2499// original loop

2500if (!LoopPhis.empty()) {

2501for (MachineInstr *Phi : LoopPhis) {

2502unsigned InitReg, LoopReg;

2503getPhiRegs(*Phi, OrigKernel, InitReg, LoopReg);

2504Register NewInit =MRI.createVirtualRegister(MRI.getRegClass(InitReg));

2505BuildMI(*NewPreheader, NewPreheader->getFirstNonPHI(),Phi->getDebugLoc(),

2506 TII->get(TargetOpcode::PHI), NewInit)

2507 .addReg(InitReg)

2508 .addMBB(Check)

2509 .addReg(NewReg)

2510 .addMBB(Epilog);

2511replacePhiSrc(*Phi, InitReg, NewInit, NewPreheader);

2512 }

2513 }

2514}

2515

2516void ModuloScheduleExpanderMVE::generateProlog(

2517SmallVectorImpl<ValueMapTy> &PrologVRMap) {

2518 PrologVRMap.clear();

2519 PrologVRMap.resize(Schedule.getNumStages() - 1);

2520DenseMap<MachineInstr *, std::pair<int, int>> NewMIMap;

2521for (int PrologNum = 0; PrologNum < Schedule.getNumStages() - 1;

2522 ++PrologNum) {

2523for (MachineInstr *MI : Schedule.getInstructions()) {

2524if (MI->isPHI())

2525continue;

2526int StageNum = Schedule.getStage(MI);

2527if (StageNum > PrologNum)

2528continue;

2529MachineInstr *NewMI = cloneInstr(MI);

2530 updateInstrDef(NewMI, PrologVRMap[PrologNum],false);

2531 NewMIMap[NewMI] = {PrologNum, StageNum};

2532Prolog->push_back(NewMI);

2533 }

2534 }

2535

2536for (autoI : NewMIMap) {

2537MachineInstr *MI =I.first;

2538int PrologNum =I.second.first;

2539int StageNum =I.second.second;

2540 updateInstrUse(MI, StageNum, PrologNum, PrologVRMap,nullptr);

2541 }

2542

2543LLVM_DEBUG({

2544dbgs() <<"prolog:\n";

2545Prolog->dump();

2546 });

2547}

2548

2549void ModuloScheduleExpanderMVE::generateKernel(

2550SmallVectorImpl<ValueMapTy> &PrologVRMap,

2551SmallVectorImpl<ValueMapTy> &KernelVRMap, InstrMapTy &LastStage0Insts) {

2552 KernelVRMap.clear();

2553 KernelVRMap.resize(NumUnroll);

2554SmallVector<ValueMapTy> PhiVRMap;

2555 PhiVRMap.resize(NumUnroll);

2556DenseMap<MachineInstr *, std::pair<int, int>> NewMIMap;

2557DenseMap<MachineInstr *, MachineInstr *> MIMapLastStage0;

2558for (int UnrollNum = 0; UnrollNum < NumUnroll; ++UnrollNum) {

2559for (MachineInstr *MI : Schedule.getInstructions()) {

2560if (MI->isPHI())

2561continue;

2562int StageNum = Schedule.getStage(MI);

2563MachineInstr *NewMI = cloneInstr(MI);

2564if (UnrollNum == NumUnroll - 1)

2565 LastStage0Insts[MI] = NewMI;

2566 updateInstrDef(NewMI, KernelVRMap[UnrollNum],

2567 (UnrollNum == NumUnroll - 1 && StageNum == 0));

2568 generatePhi(MI, UnrollNum, PrologVRMap, KernelVRMap, PhiVRMap);

2569 NewMIMap[NewMI] = {UnrollNum, StageNum};

2570 NewKernel->push_back(NewMI);

2571 }

2572 }

2573

2574for (autoI : NewMIMap) {

2575MachineInstr *MI =I.first;

2576int UnrollNum =I.second.first;

2577int StageNum =I.second.second;

2578 updateInstrUse(MI, StageNum, UnrollNum, KernelVRMap, &PhiVRMap);

2579 }

2580

2581// If remaining trip count is greater than NumUnroll-1, loop continues

2582 insertCondBranch(*NewKernel, NumUnroll - 1, LastStage0Insts, *NewKernel,

2583 *Epilog);

2584

2585LLVM_DEBUG({

2586dbgs() <<"kernel:\n";

2587 NewKernel->dump();

2588 });

2589}

2590

2591void ModuloScheduleExpanderMVE::generateEpilog(

2592SmallVectorImpl<ValueMapTy> &KernelVRMap,

2593SmallVectorImpl<ValueMapTy> &EpilogVRMap, InstrMapTy &LastStage0Insts) {

2594 EpilogVRMap.clear();

2595 EpilogVRMap.resize(Schedule.getNumStages() - 1);

2596DenseMap<MachineInstr *, std::pair<int, int>> NewMIMap;

2597for (int EpilogNum = 0; EpilogNum < Schedule.getNumStages() - 1;

2598 ++EpilogNum) {

2599for (MachineInstr *MI : Schedule.getInstructions()) {

2600if (MI->isPHI())

2601continue;

2602int StageNum = Schedule.getStage(MI);

2603if (StageNum <= EpilogNum)

2604continue;

2605MachineInstr *NewMI = cloneInstr(MI);

2606 updateInstrDef(NewMI, EpilogVRMap[EpilogNum], StageNum - 1 == EpilogNum);

2607 NewMIMap[NewMI] = {EpilogNum, StageNum};

2608Epilog->push_back(NewMI);

2609 }

2610 }

2611

2612for (autoI : NewMIMap) {

2613MachineInstr *MI =I.first;

2614int EpilogNum =I.second.first;

2615int StageNum =I.second.second;

2616 updateInstrUse(MI, StageNum, EpilogNum, EpilogVRMap, &KernelVRMap);

2617 }

2618

2619// If there are remaining iterations, they are executed in the original loop.

2620// Instructions related to loop control, such as loop counter comparison,

2621// are indicated by shouldIgnoreForPipelining() and are assumed to be placed

2622// in stage 0. Thus, the map is for the last one in the kernel.

2623 insertCondBranch(*Epilog, 0, LastStage0Insts, *NewPreheader, *NewExit);

2624

2625LLVM_DEBUG({

2626dbgs() <<"epilog:\n";

2627Epilog->dump();

2628 });

2629}

2630

2631/// Calculate the number of unroll required and set it to NumUnroll

2632void ModuloScheduleExpanderMVE::calcNumUnroll() {

2633DenseMap<MachineInstr *, unsigned> Inst2Idx;

2634 NumUnroll = 1;

2635for (unsignedI = 0;I < Schedule.getInstructions().size(); ++I)

2636 Inst2Idx[Schedule.getInstructions()[I]] =I;

2637

2638for (MachineInstr *MI : Schedule.getInstructions()) {

2639if (MI->isPHI())

2640continue;

2641int StageNum = Schedule.getStage(MI);

2642for (constMachineOperand &MO :MI->uses()) {

2643if (!MO.isReg() || !MO.getReg().isVirtual())

2644continue;

2645MachineInstr *DefMI =MRI.getVRegDef(MO.getReg());

2646if (DefMI->getParent() != OrigKernel)

2647continue;

2648

2649int NumUnrollLocal = 1;

2650if (DefMI->isPHI()) {

2651 ++NumUnrollLocal;

2652// canApply() guarantees that DefMI is not phi and is an instruction in

2653// the loop

2654DefMI =MRI.getVRegDef(getLoopPhiReg(*DefMI, OrigKernel));

2655 }

2656 NumUnrollLocal += StageNum - Schedule.getStage(DefMI);

2657if (Inst2Idx[MI] <= Inst2Idx[DefMI])

2658 --NumUnrollLocal;

2659 NumUnroll = std::max(NumUnroll, NumUnrollLocal);

2660 }

2661 }

2662LLVM_DEBUG(dbgs() <<"NumUnroll: " << NumUnroll <<"\n");

2663}

2664

2665/// Create new virtual registers for definitions of NewMI and update NewMI.

2666/// If the definitions are referenced after the pipelined loop, phis are

2667/// created to merge with other routes.

2668void ModuloScheduleExpanderMVE::updateInstrDef(MachineInstr *NewMI,

2669 ValueMapTy &VRMap,

2670bool LastDef) {

2671for (MachineOperand &MO : NewMI->all_defs()) {

2672if (!MO.getReg().isVirtual())

2673continue;

2674Register Reg = MO.getReg();

2675constTargetRegisterClass *RC =MRI.getRegClass(Reg);

2676Register NewReg =MRI.createVirtualRegister(RC);

2677 MO.setReg(NewReg);

2678 VRMap[Reg] = NewReg;

2679if (LastDef)

2680 mergeRegUsesAfterPipeline(Reg, NewReg);

2681 }

2682}

2683

2684voidModuloScheduleExpanderMVE::expand() {

2685 OrigKernel = Schedule.getLoop()->getTopBlock();

2686 OrigPreheader = Schedule.getLoop()->getLoopPreheader();

2687 OrigExit = Schedule.getLoop()->getExitBlock();

2688

2689LLVM_DEBUG(Schedule.dump());

2690

2691 generatePipelinedLoop();

2692}

2693

2694/// Check if ModuloScheduleExpanderMVE can be applied to L

2695boolModuloScheduleExpanderMVE::canApply(MachineLoop &L) {

2696if (!L.getExitBlock()) {

2697LLVM_DEBUG(dbgs() <<"Can not apply MVE expander: No single exit block.\n");

2698returnfalse;

2699 }

2700

2701MachineBasicBlock *BB = L.getTopBlock();

2702MachineRegisterInfo &MRI = BB->getParent()->getRegInfo();

2703

2704// Put some constraints on the operands of the phis to simplify the

2705// transformation

2706DenseSet<unsigned> UsedByPhi;

2707for (MachineInstr &MI : BB->phis()) {

2708// Registers defined by phis must be used only inside the loop and be never

2709// used by phis.

2710for (MachineOperand &MO :MI.defs())

2711if (MO.isReg())

2712for (MachineInstr &Ref :MRI.use_instructions(MO.getReg()))

2713if (Ref.getParent() != BB ||Ref.isPHI()) {

2714LLVM_DEBUG(dbgs() <<"Can not apply MVE expander: A phi result is "

2715"referenced outside of the loop or by phi.\n");

2716returnfalse;

2717 }

2718

2719// A source register from the loop block must be defined inside the loop.

2720// A register defined inside the loop must be referenced by only one phi at

2721// most.

2722unsigned InitVal, LoopVal;

2723getPhiRegs(MI,MI.getParent(), InitVal, LoopVal);

2724if (!Register(LoopVal).isVirtual() ||

2725MRI.getVRegDef(LoopVal)->getParent() != BB) {

2726LLVM_DEBUG(

2727dbgs() <<"Can not apply MVE expander: A phi source value coming "

2728"from the loop is not defined in the loop.\n");

2729returnfalse;

2730 }

2731if (UsedByPhi.count(LoopVal)) {

2732LLVM_DEBUG(dbgs() <<"Can not apply MVE expander: A value defined in the "

2733"loop is referenced by two or more phis.\n");

2734returnfalse;

2735 }

2736 UsedByPhi.insert(LoopVal);

2737 }

2738

2739returntrue;

2740}

2741

2742//===----------------------------------------------------------------------===//

2743// ModuloScheduleTestPass implementation

2744//===----------------------------------------------------------------------===//

2745// This pass constructs a ModuloSchedule from its module and runs

2746// ModuloScheduleExpander.

2747//

2748// The module is expected to contain a single-block analyzable loop.

2749// The total order of instructions is taken from the loop as-is.

2750// Instructions are expected to be annotated with a PostInstrSymbol.

2751// This PostInstrSymbol must have the following format:

2752// "Stage=%d Cycle=%d".

2753//===----------------------------------------------------------------------===//

2754

2755namespace{

2756classModuloScheduleTest :publicMachineFunctionPass {

2757public:

2758staticcharID;

2759

2760 ModuloScheduleTest() :MachineFunctionPass(ID) {

2761initializeModuloScheduleTestPass(*PassRegistry::getPassRegistry());

2762 }

2763

2764bool runOnMachineFunction(MachineFunction &MF)override;

2765void runOnLoop(MachineFunction &MF,MachineLoop &L);

2766

2767void getAnalysisUsage(AnalysisUsage &AU) const override{

2768 AU.addRequired<MachineLoopInfoWrapperPass>();

2769 AU.addRequired<LiveIntervalsWrapperPass>();

2770MachineFunctionPass::getAnalysisUsage(AU);

2771 }

2772};

2773}// namespace

2774

2775char ModuloScheduleTest::ID = 0;

2776

2777INITIALIZE_PASS_BEGIN(ModuloScheduleTest,"modulo-schedule-test",

2778"Modulo Schedule test pass",false,false)

2779INITIALIZE_PASS_DEPENDENCY(MachineLoopInfoWrapperPass)

2780INITIALIZE_PASS_DEPENDENCY(LiveIntervalsWrapperPass)

2781INITIALIZE_PASS_END(ModuloScheduleTest, "modulo-schedule-test",

2782 "Modulo Scheduletest pass",false,false)

2783

2784bool ModuloScheduleTest::runOnMachineFunction(MachineFunction &MF) {

2785MachineLoopInfo &MLI = getAnalysis<MachineLoopInfoWrapperPass>().getLI();

2786for (auto *L : MLI) {

2787if (L->getTopBlock() != L->getBottomBlock())

2788continue;

2789 runOnLoop(MF, *L);

2790returnfalse;

2791 }

2792returnfalse;

2793}

2794

2795staticvoidparseSymbolString(StringRef S,int &Cycle,int &Stage) {

2796 std::pair<StringRef, StringRef> StageAndCycle = getToken(S,"_");

2797 std::pair<StringRef, StringRef> StageTokenAndValue =

2798 getToken(StageAndCycle.first,"-");

2799 std::pair<StringRef, StringRef> CycleTokenAndValue =

2800 getToken(StageAndCycle.second,"-");

2801if (StageTokenAndValue.first !="Stage" ||

2802 CycleTokenAndValue.first !="_Cycle") {

2803llvm_unreachable(

2804"Bad post-instr symbol syntax: see comment in ModuloScheduleTest");

2805return;

2806 }

2807

2808 StageTokenAndValue.second.drop_front().getAsInteger(10, Stage);

2809 CycleTokenAndValue.second.drop_front().getAsInteger(10,Cycle);

2810

2811dbgs() <<" Stage=" << Stage <<", Cycle=" <<Cycle <<"\n";

2812}

2813

2814void ModuloScheduleTest::runOnLoop(MachineFunction &MF,MachineLoop &L) {

2815LiveIntervals &LIS = getAnalysis<LiveIntervalsWrapperPass>().getLIS();

2816MachineBasicBlock *BB =L.getTopBlock();

2817dbgs() <<"--- ModuloScheduleTest running on BB#" << BB->getNumber() <<"\n";

2818

2819DenseMap<MachineInstr *, int>Cycle, Stage;

2820 std::vector<MachineInstr *> Instrs;

2821for (MachineInstr &MI : *BB) {

2822if (MI.isTerminator())

2823continue;

2824 Instrs.push_back(&MI);

2825if (MCSymbol *Sym =MI.getPostInstrSymbol()) {

2826dbgs() <<"Parsing post-instr symbol for " <<MI;

2827parseSymbolString(Sym->getName(),Cycle[&MI], Stage[&MI]);

2828 }

2829 }

2830

2831ModuloSchedule MS(MF, &L, std::move(Instrs), std::move(Cycle),

2832 std::move(Stage));

2833ModuloScheduleExpander MSE(

2834 MF, MS, LIS,/*InstrChanges=*/ModuloScheduleExpander::InstrChangesTy());

2835 MSE.expand();

2836 MSE.cleanup();

2837}

2838

2839//===----------------------------------------------------------------------===//

2840// ModuloScheduleTestAnnotater implementation

2841//===----------------------------------------------------------------------===//

2842

2843voidModuloScheduleTestAnnotater::annotate() {

2844for (MachineInstr *MI : S.getInstructions()) {

2845SmallVector<char, 16> SV;

2846raw_svector_ostream OS(SV);

2847OS <<"Stage-" << S.getStage(MI) <<"_Cycle-" << S.getCycle(MI);

2848MCSymbol *Sym = MF.getContext().getOrCreateSymbol(OS.str());

2849MI->setPostInstrSymbol(MF,Sym);

2850 }

2851}

MRI

unsigned const MachineRegisterInfo * MRI

Definition:AArch64AdvSIMDScalarPass.cpp:105

UseMI

MachineInstrBuilder & UseMI

Definition:AArch64ExpandPseudoInsts.cpp:112

DefMI

MachineInstrBuilder MachineInstrBuilder & DefMI

Definition:AArch64ExpandPseudoInsts.cpp:113

Prolog

@ Prolog

Definition:AArch64LowerHomogeneousPrologEpilog.cpp:124

Epilog

@ Epilog

Definition:AArch64LowerHomogeneousPrologEpilog.cpp:124

PHI

Rewrite undef for PHI

Definition:AMDGPURewriteUndefForPHI.cpp:100

MBB

MachineBasicBlock & MBB

Definition:ARMSLSHardening.cpp:71

static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)

Definition:ArchiveWriter.cpp:205

getParent

static const Function * getParent(const Value *V)

Definition:BasicAliasAnalysis.cpp:863

static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")

static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")

Idx

Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx

Definition:DeadArgumentElimination.cpp:353

Debug.h

LLVM_DEBUG

#define LLVM_DEBUG(...)

Definition:Debug.h:106

Default

@ Default

Definition:DwarfDebug.cpp:87

Other

std::optional< std::vector< StOtherPiece > > Other

Definition:ELFYAML.cpp:1315

Blocks

DenseMap< Block *, BlockRelaxAux > Blocks

Definition:ELF_riscv.cpp:507

Sym

Symbol * Sym

Definition:ELF_riscv.cpp:479

pass

global merge Global merge function pass

Definition:GlobalMergeFunctions.cpp:623

TII

const HexagonInstrInfo * TII

Definition:HexagonCopyToCombine.cpp:125

IRTranslator LLVM IR MI

Definition:IRTranslator.cpp:112

InitializePasses.h

LiveIntervals.h

MCContext.h

#define I(x, y, z)

Definition:MD5.cpp:58

MachineInstrBuilder.h

MachineLoopInfo.h

getLoopPhiReg

static unsigned getLoopPhiReg(const MachineInstr &Phi, const MachineBasicBlock *LoopBB)

Return the Phi register value that comes the loop block.

Definition:MachinePipeliner.cpp:774

getPhiRegs

static void getPhiRegs(MachineInstr &Phi, MachineBasicBlock *Loop, unsigned &InitVal, unsigned &LoopVal)

Return the register values for the operands of a Phi instruction.

Definition:MachinePipeliner.cpp:758

MachineRegisterInfo.h

TRI

unsigned const TargetRegisterInfo * TRI

Definition:MachineSink.cpp:2029

Reg

unsigned Reg

Definition:MachineSink.cpp:2028

MemoryLocation.h

This file provides utility analysis objects describing memory locations.

createDedicatedExit

static MachineBasicBlock * createDedicatedExit(MachineBasicBlock *Loop, MachineBasicBlock *Exit)

Create a dedicated exit for Loop.

Definition:ModuloSchedule.cpp:2120

test

modulo schedule test

Definition:ModuloSchedule.cpp:2781

removePhis

static void removePhis(MachineBasicBlock *BB, MachineBasicBlock *Incoming)

Remove the incoming block from the Phis in a basic block.

Definition:ModuloSchedule.cpp:849

getLoopPhiReg

static unsigned getLoopPhiReg(MachineInstr &Phi, MachineBasicBlock *LoopBB)

Return the Phi register value that comes the loop block.

Definition:ModuloSchedule.cpp:64

replaceRegUsesAfterLoop

static void replaceRegUsesAfterLoop(unsigned FromReg, unsigned ToReg, MachineBasicBlock *MBB, MachineRegisterInfo &MRI, LiveIntervals &LIS)

Replace all uses of FromReg that appear outside the specified basic block with ToReg.

Definition:ModuloSchedule.cpp:344

replacePhiSrc

static void replacePhiSrc(MachineInstr &Phi, Register OrigReg, Register NewReg, MachineBasicBlock *NewMBB)

Definition:ModuloSchedule.cpp:2451

getLoopPhiUser

static MachineInstr * getLoopPhiUser(Register Reg, MachineBasicBlock *Loop)

Return a phi if Reg is referenced by the phi.

Definition:ModuloSchedule.cpp:2365

parseSymbolString

static void parseSymbolString(StringRef S, int &Cycle, int &Stage)

Definition:ModuloSchedule.cpp:2795

SwapBranchTargetsMVE

static cl::opt< bool > SwapBranchTargetsMVE("pipeliner-swap-branch-targets-mve", cl::Hidden, cl::init(false), cl::desc("Swap target blocks of a conditional branch for MVE expander"))

hasUseAfterLoop

static bool hasUseAfterLoop(unsigned Reg, MachineBasicBlock *BB, MachineRegisterInfo &MRI)

Return true if the register has a use that occurs outside the specified loop.

Definition:ModuloSchedule.cpp:358

getInitPhiReg

static unsigned getInitPhiReg(MachineInstr &Phi, MachineBasicBlock *LoopBB)

Return the Phi register value that comes from the incoming block.

Definition:ModuloSchedule.cpp:56

ModuloSchedule.h

#define P(N)

INITIALIZE_PASS_DEPENDENCY

#define INITIALIZE_PASS_DEPENDENCY(depName)

Definition:PassSupport.h:55

INITIALIZE_PASS_END

#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)

Definition:PassSupport.h:57

INITIALIZE_PASS_BEGIN

#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)

Definition:PassSupport.h:52

TBB

const SmallVectorImpl< MachineOperand > MachineBasicBlock * TBB

Definition:RISCVRedundantCopyElimination.cpp:76

Cond

const SmallVectorImpl< MachineOperand > & Cond

Definition:RISCVRedundantCopyElimination.cpp:75

Uses

Remove Loads Into Fake Uses

Definition:RemoveLoadsIntoFakeUses.cpp:74

assert

assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())

raw_pwrite_stream & OS

Definition:SampleProfWriter.cpp:51

StringExtras.h

This file contains some functions that are useful when dealing with strings.

llvm::AnalysisUsage

Represent the analysis usage information of a pass.

Definition:PassAnalysisSupport.h:47

llvm::AnalysisUsage::addRequired

AnalysisUsage & addRequired()

Definition:PassAnalysisSupport.h:75

llvm::BitVector

Definition:BitVector.h:82

llvm::DWARFExpression::Operation

This class represents an Operation in the Expression.

Definition:DWARFExpression.h:32

llvm::DebugLoc

A debug info location.

Definition:DebugLoc.h:33

llvm::DenseMapBase::find

iterator find(const_arg_type_t< KeyT > Val)

Definition:DenseMap.h:156

llvm::DenseMapBase::iterator

DenseMapIterator< KeyT, ValueT, KeyInfoT, BucketT > iterator

Definition:DenseMap.h:71

llvm::DenseMapBase::end

iterator end()

Definition:DenseMap.h:84

llvm::DenseMap

Definition:DenseMap.h:727

llvm::DenseSet

Implements a dense probed hash-table based set.

Definition:DenseSet.h:278

llvm::GenericCycle

A possibly irreducible generalization of a Loop.

Definition:GenericCycleInfo.h:44

llvm::HexagonInstrInfo::removeBranch

unsigned removeBranch(MachineBasicBlock &MBB, int *BytesRemoved=nullptr) const override

Remove the branching code at the end of the specific MBB.

Definition:HexagonInstrInfo.cpp:604

llvm::HexagonInstrInfo::analyzeBranch

bool analyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB, MachineBasicBlock *&FBB, SmallVectorImpl< MachineOperand > &Cond, bool AllowModify) const override

Analyze the branching code at the end of MBB, returning true if it cannot be understood (e....

Definition:HexagonInstrInfo.cpp:434

llvm::HexagonInstrInfo::insertBranch

unsigned insertBranch(MachineBasicBlock &MBB, MachineBasicBlock *TBB, MachineBasicBlock *FBB, ArrayRef< MachineOperand > Cond, const DebugLoc &DL, int *BytesAdded=nullptr) const override

Insert branch code into the end of the specified MachineBasicBlock.

Definition:HexagonInstrInfo.cpp:627

llvm::LiveIntervalsWrapperPass

Definition:LiveIntervals.h:527

llvm::LiveIntervals

Definition:LiveIntervals.h:55

llvm::LiveIntervals::hasInterval

bool hasInterval(Register Reg) const

Definition:LiveIntervals.h:144

llvm::LiveIntervals::insertMBBInMaps

void insertMBBInMaps(MachineBasicBlock *MBB)

Definition:LiveIntervals.h:276

llvm::LiveIntervals::RemoveMachineInstrFromMaps

void RemoveMachineInstrFromMaps(MachineInstr &MI)

Definition:LiveIntervals.h:293

llvm::LiveIntervals::createEmptyInterval

LiveInterval & createEmptyInterval(Register Reg)

Interval creation.

Definition:LiveIntervals.h:149

llvm::LocationSize::beforeOrAfterPointer

static constexpr LocationSize beforeOrAfterPointer()

Any location before or after the base pointer (but still within the underlying object).

Definition:MemoryLocation.h:137

llvm::LoopBase::getExitBlock

BlockT * getExitBlock() const

If getExitBlocks would return exactly one block, return that block.

Definition:GenericLoopInfoImpl.h:107

llvm::LoopBase::getLoopPreheader

BlockT * getLoopPreheader() const

If there is a preheader for this loop, return it.

Definition:GenericLoopInfoImpl.h:210

llvm::LoopInfo

Definition:LoopInfo.h:407

llvm::Loop

Represents a single loop in the control flow graph.

Definition:LoopInfo.h:39

llvm::MCContext::getOrCreateSymbol

MCSymbol * getOrCreateSymbol(const Twine &Name)

Lookup the symbol inside with the specified Name.

Definition:MCContext.cpp:212

llvm::MCInstrInfo::get

const MCInstrDesc & get(unsigned Opcode) const

Return the machine instruction descriptor that corresponds to the specified instruction opcode.

Definition:MCInstrInfo.h:63

llvm::MCSymbol

MCSymbol - Instances of this class represent a symbol name in the MC file, and MCSymbols are created ...

Definition:MCSymbol.h:41

llvm::MachineBasicBlock

Definition:MachineBasicBlock.h:125

llvm::MachineBasicBlock::transferSuccessorsAndUpdatePHIs

void transferSuccessorsAndUpdatePHIs(MachineBasicBlock *FromMBB)

Transfers all the successors, as in transferSuccessors, and update PHI operands in the successor bloc...

Definition:MachineBasicBlock.cpp:937

llvm::MachineBasicBlock::replacePhiUsesWith

void replacePhiUsesWith(MachineBasicBlock *Old, MachineBasicBlock *New)

Update all phi nodes in this basic block to refer to basic block New instead of basic block Old.

Definition:MachineBasicBlock.cpp:1503

llvm::MachineBasicBlock::instr_begin

instr_iterator instr_begin()

Definition:MachineBasicBlock.h:339

llvm::MachineBasicBlock::clear

void clear()

Definition:MachineBasicBlock.h:1101

llvm::MachineBasicBlock::replaceSuccessor

void replaceSuccessor(MachineBasicBlock *Old, MachineBasicBlock *New)

Replace successor OLD with NEW and update probability info.

Definition:MachineBasicBlock.cpp:859

llvm::MachineBasicBlock::transferSuccessors

void transferSuccessors(MachineBasicBlock *FromMBB)

Transfers all the successors from MBB to this machine basic block (i.e., copies all the successors Fr...

Definition:MachineBasicBlock.cpp:917

llvm::MachineBasicBlock::insert

instr_iterator insert(instr_iterator I, MachineInstr *M)

Insert MI into the instruction list before I, possibly inside a bundle.

Definition:MachineBasicBlock.cpp:1456

llvm::MachineBasicBlock::phis

iterator_range< iterator > phis()

Returns a range that iterates over the phis in the basic block.

Definition:MachineBasicBlock.h:383

llvm::MachineBasicBlock::instr_rbegin

reverse_instr_iterator instr_rbegin()

Definition:MachineBasicBlock.h:343

llvm::MachineBasicBlock::getNumber

int getNumber() const

MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...

Definition:MachineBasicBlock.h:1217

llvm::MachineBasicBlock::push_back

void push_back(MachineInstr *MI)

Definition:MachineBasicBlock.h:1002

llvm::MachineBasicBlock::succ_end

succ_iterator succ_end()

Definition:MachineBasicBlock.h:423

llvm::MachineBasicBlock::getBasicBlock

const BasicBlock * getBasicBlock() const

Return the LLVM basic block that this instance corresponded to originally.

Definition:MachineBasicBlock.h:256

llvm::MachineBasicBlock::succ_begin

succ_iterator succ_begin()

Definition:MachineBasicBlock.h:421

llvm::MachineBasicBlock::getFirstTerminator

iterator getFirstTerminator()

Returns an iterator to the first terminator instruction of this basic block.

Definition:MachineBasicBlock.cpp:244

llvm::MachineBasicBlock::dump

void dump() const

Definition:MachineBasicBlock.cpp:301

llvm::MachineBasicBlock::addSuccessor

void addSuccessor(MachineBasicBlock *Succ, BranchProbability Prob=BranchProbability::getUnknown())

Add Succ as a successor of this MachineBasicBlock.

Definition:MachineBasicBlock.cpp:798

llvm::MachineBasicBlock::succ_iterator

SmallVectorImpl< MachineBasicBlock * >::iterator succ_iterator

Definition:MachineBasicBlock.h:394

llvm::MachineBasicBlock::removeSuccessor

void removeSuccessor(MachineBasicBlock *Succ, bool NormalizeSuccProbs=false)

Remove successor from the successors list of this MachineBasicBlock.

Definition:MachineBasicBlock.cpp:836

llvm::MachineBasicBlock::getFirstNonPHI

iterator getFirstNonPHI()

Returns a pointer to the first instruction in this block that is not a PHINode instruction.

Definition:MachineBasicBlock.cpp:202

llvm::MachineBasicBlock::begin

iterator begin()

Definition:MachineBasicBlock.h:355

llvm::MachineBasicBlock::print

void print(raw_ostream &OS, const SlotIndexes *=nullptr, bool IsStandalone=true) const

Definition:MachineBasicBlock.cpp:345

llvm::MachineBasicBlock::instr_rend

reverse_instr_iterator instr_rend()

Definition:MachineBasicBlock.h:345

llvm::MachineBasicBlock::instr_iterator

Instructions::iterator instr_iterator

Definition:MachineBasicBlock.h:314

llvm::MachineBasicBlock::pred_begin

pred_iterator pred_begin()

Definition:MachineBasicBlock.h:405

llvm::MachineBasicBlock::eraseFromParent

void eraseFromParent()

This method unlinks 'this' from the containing function and deletes it.

Definition:MachineBasicBlock.cpp:1476

llvm::MachineBasicBlock::instr_end

instr_iterator instr_end()

Definition:MachineBasicBlock.h:341

llvm::MachineBasicBlock::end

iterator end()

Definition:MachineBasicBlock.h:357

llvm::MachineBasicBlock::back

MachineInstr & back()

Definition:MachineBasicBlock.h:335

llvm::MachineBasicBlock::getParent

const MachineFunction * getParent() const

Return the MachineFunction containing this basic block.

Definition:MachineBasicBlock.h:311

llvm::MachineBasicBlock::terminators

iterator_range< iterator > terminators()

Definition:MachineBasicBlock.h:375

llvm::MachineBasicBlock::getFirstInstrTerminator

instr_iterator getFirstInstrTerminator()

Same getFirstTerminator but it ignores bundles and return an instr_iterator instead.

Definition:MachineBasicBlock.cpp:253

llvm::MachineBasicBlock::reverse_instr_iterator

Instructions::reverse_iterator reverse_instr_iterator

Definition:MachineBasicBlock.h:316

llvm::MachineFunctionPass

MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...

Definition:MachineFunctionPass.h:30

llvm::MachineFunctionPass::getAnalysisUsage

void getAnalysisUsage(AnalysisUsage &AU) const override

getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.

Definition:MachineFunctionPass.cpp:169

llvm::MachineFunction

Definition:MachineFunction.h:267

llvm::MachineFunction::getSubtarget

const TargetSubtargetInfo & getSubtarget() const

getSubtarget - Return the subtarget for which this machine code is being compiled.

Definition:MachineFunction.h:733

llvm::MachineFunction::getMachineMemOperand

MachineMemOperand * getMachineMemOperand(MachinePointerInfo PtrInfo, MachineMemOperand::Flags f, LLT MemTy, Align base_alignment, const AAMDNodes &AAInfo=AAMDNodes(), const MDNode *Ranges=nullptr, SyncScope::ID SSID=SyncScope::System, AtomicOrdering Ordering=AtomicOrdering::NotAtomic, AtomicOrdering FailureOrdering=AtomicOrdering::NotAtomic)

getMachineMemOperand - Allocate a new MachineMemOperand.

Definition:MachineFunction.cpp:536

llvm::MachineFunction::getContext

MCContext & getContext() const

Definition:MachineFunction.h:690

llvm::MachineFunction::getRegInfo

MachineRegisterInfo & getRegInfo()

getRegInfo - Return information about the registers currently in use.

Definition:MachineFunction.h:743

llvm::MachineFunction::CloneMachineInstr

MachineInstr * CloneMachineInstr(const MachineInstr *Orig)

Create a new MachineInstr which is a copy of Orig, identical in all ways except the instruction has n...

Definition:MachineFunction.cpp:439

llvm::MachineFunction::front

const MachineBasicBlock & front() const

Definition:MachineFunction.h:959

llvm::MachineFunction::CreateMachineBasicBlock

MachineBasicBlock * CreateMachineBasicBlock(const BasicBlock *BB=nullptr, std::optional< UniqueBBID > BBID=std::nullopt)

CreateMachineBasicBlock - Allocate a new MachineBasicBlock.

Definition:MachineFunction.cpp:499

llvm::MachineFunction::insert

void insert(iterator MBBI, MachineBasicBlock *MBB)

Definition:MachineFunction.h:966

llvm::MachineInstrBuilder

Definition:MachineInstrBuilder.h:71

llvm::MachineInstrBuilder::getReg

Get the register for the operand index.

Definition:MachineInstrBuilder.h:96

llvm::MachineInstrBuilder::addReg

const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const

Add a new virtual register operand.

Definition:MachineInstrBuilder.h:99

llvm::MachineInstrBuilder::addMBB

const MachineInstrBuilder & addMBB(MachineBasicBlock *MBB, unsigned TargetFlags=0) const

Definition:MachineInstrBuilder.h:148

llvm::MachineInstrBundleIterator< MachineInstr >

llvm::MachineInstr

Representation of each machine instruction.

Definition:MachineInstr.h:71

llvm::MachineInstr::getParent

const MachineBasicBlock * getParent() const

Definition:MachineInstr.h:349

llvm::MachineInstr::getNumOperands

unsigned getNumOperands() const

Retuns the total number of operands.

Definition:MachineInstr.h:580

llvm::MachineInstr::memoperands_empty

bool memoperands_empty() const

Return true if we don't have any memory operands which described the memory access done by this instr...

Definition:MachineInstr.h:820

llvm::MachineInstr::setMemRefs

void setMemRefs(MachineFunction &MF, ArrayRef< MachineMemOperand * > MemRefs)

Assign this MachineInstr's memory reference descriptor list.

Definition:MachineInstr.cpp:370

llvm::MachineInstr::dropMemRefs

void dropMemRefs(MachineFunction &MF)

Clear this MachineInstr's memory reference descriptor list.

Definition:MachineInstr.cpp:361

llvm::MachineInstr::operands

iterator_range< mop_iterator > operands()

Definition:MachineInstr.h:693

llvm::MachineInstr::defs

iterator_range< mop_iterator > defs()

Returns a range over all explicit operands that are register definitions.

Definition:MachineInstr.h:730

llvm::MachineInstr::memoperands

ArrayRef< MachineMemOperand * > memoperands() const

Access to memory operands of the instruction.

Definition:MachineInstr.h:790

llvm::MachineInstr::getDebugLoc

const DebugLoc & getDebugLoc() const

Returns the debug location id of this MachineInstr.

Definition:MachineInstr.h:501

llvm::MachineInstr::isPHI

bool isPHI() const

Definition:MachineInstr.h:1406

llvm::MachineInstr::getOperand

const MachineOperand & getOperand(unsigned i) const

Definition:MachineInstr.h:587

llvm::MachineInstr::all_defs

iterator_range< filtered_mop_iterator > all_defs()

Returns an iterator range over all operands that are (explicit or implicit) register defs.

Definition:MachineInstr.h:764

llvm::MachineLoopInfoWrapperPass

Definition:MachineLoopInfo.h:156

llvm::MachineLoopInfo

Definition:MachineLoopInfo.h:105

llvm::MachineLoop

Definition:MachineLoopInfo.h:46

llvm::MachineLoop::getTopBlock

MachineBasicBlock * getTopBlock()

Return the "top" block in the loop, which is the first block in the linear layout,...

Definition:MachineLoopInfo.cpp:89

llvm::MachineMemOperand

A description of a memory reference used in the backend.

Definition:MachineMemOperand.h:129

llvm::MachineOperand

MachineOperand class - Representation of each machine instruction operand.

Definition:MachineOperand.h:48

llvm::MachineOperand::setImm

void setImm(int64_t immVal)

Definition:MachineOperand.h:685

llvm::MachineOperand::getImm

int64_t getImm() const

Definition:MachineOperand.h:556

llvm::MachineOperand::isImplicit

bool isImplicit() const

Definition:MachineOperand.h:389

llvm::MachineOperand::isReg

bool isReg() const

isReg - Tests if this is a MO_Register operand.

Definition:MachineOperand.h:329

llvm::MachineOperand::getMBB

MachineBasicBlock * getMBB() const

Definition:MachineOperand.h:571

llvm::MachineOperand::setReg

void setReg(Register Reg)

Change the register this operand corresponds to.

Definition:MachineOperand.cpp:61

llvm::MachineOperand::isUse

bool isUse() const

Definition:MachineOperand.h:379

llvm::MachineOperand::isDef

bool isDef() const

Definition:MachineOperand.h:384

llvm::MachineOperand::getParent

MachineInstr * getParent()

getParent - Return the instruction that this operand belongs to.

Definition:MachineOperand.h:243

llvm::MachineOperand::setMBB

void setMBB(MachineBasicBlock *MBB)

Definition:MachineOperand.h:728

llvm::MachineOperand::isDead

bool isDead() const

Definition:MachineOperand.h:394

llvm::MachineOperand::getReg

getReg - Returns the register number.

Definition:MachineOperand.h:369

llvm::MachineOperand::CreateReg

static MachineOperand CreateReg(Register Reg, bool isDef, bool isImp=false, bool isKill=false, bool isDead=false, bool isUndef=false, bool isEarlyClobber=false, unsigned SubReg=0, bool isDebug=false, bool isInternalRead=false, bool isRenamable=false)

Definition:MachineOperand.h:838

llvm::MachineOperand::CreateMBB

static MachineOperand CreateMBB(MachineBasicBlock *MBB, unsigned TargetFlags=0)

Definition:MachineOperand.h:863

llvm::MachineRegisterInfo::defusechain_instr_iterator

defusechain_iterator - This class provides iterator support for machine operands in the function that...

Definition:MachineRegisterInfo.h:1155

llvm::MachineRegisterInfo::defusechain_iterator

reg_begin/reg_end - Provide iteration support to walk over all definitions and uses of a register wit...

Definition:MachineRegisterInfo.h:1050

llvm::MachineRegisterInfo

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

Definition:MachineRegisterInfo.h:51

llvm::MachineRegisterInfo::getRegClass

const TargetRegisterClass * getRegClass(Register Reg) const

Return the register class of the specified virtual register.

Definition:MachineRegisterInfo.h:655

llvm::MachineRegisterInfo::getVRegDef

MachineInstr * getVRegDef(Register Reg) const

getVRegDef - Return the machine instr that defines the specified virtual register or null if none is ...

Definition:MachineRegisterInfo.cpp:406

llvm::MachineRegisterInfo::use_instr_begin

use_instr_iterator use_instr_begin(Register RegNo) const

Definition:MachineRegisterInfo.h:493

llvm::MachineRegisterInfo::createVirtualRegister

createVirtualRegister - Create and return a new virtual register in the function with the specified r...

Definition:MachineRegisterInfo.cpp:156

llvm::MachineRegisterInfo::use_instr_end

static use_instr_iterator use_instr_end()

Definition:MachineRegisterInfo.h:496

llvm::MachineRegisterInfo::setRegClass

void setRegClass(Register Reg, const TargetRegisterClass *RC)

setRegClass - Set the register class of the specified virtual register.

Definition:MachineRegisterInfo.cpp:58

llvm::MachineRegisterInfo::use_instructions

iterator_range< use_instr_iterator > use_instructions(Register Reg) const

Definition:MachineRegisterInfo.h:501

llvm::MachineRegisterInfo::getTargetRegisterInfo

const TargetRegisterInfo * getTargetRegisterInfo() const

Definition:MachineRegisterInfo.h:157

llvm::MachineRegisterInfo::use_begin

use_iterator use_begin(Register RegNo) const

Definition:MachineRegisterInfo.h:480

llvm::MachineRegisterInfo::use_end

static use_iterator use_end()

Definition:MachineRegisterInfo.h:483

llvm::MachineRegisterInfo::use_operands

iterator_range< use_iterator > use_operands(Register Reg) const

Definition:MachineRegisterInfo.h:485

llvm::MachineRegisterInfo::replaceRegWith

void replaceRegWith(Register FromReg, Register ToReg)

replaceRegWith - Replace all instances of FromReg with ToReg in the machine function.

Definition:MachineRegisterInfo.cpp:388

llvm::MachineRegisterInfo::getUniqueVRegDef

MachineInstr * getUniqueVRegDef(Register Reg) const

getUniqueVRegDef - Return the unique machine instr that defines the specified virtual register or nul...

Definition:MachineRegisterInfo.cpp:419

llvm::ModuloScheduleExpanderMVE::expand

void expand()

Definition:ModuloSchedule.cpp:2684

llvm::ModuloScheduleExpanderMVE::canApply

static bool canApply(MachineLoop &L)

Check if ModuloScheduleExpanderMVE can be applied to L.

Definition:ModuloSchedule.cpp:2695

llvm::ModuloScheduleExpander

The ModuloScheduleExpander takes a ModuloSchedule and expands it in-place, rewriting the old loop and...

Definition:ModuloSchedule.h:161

llvm::ModuloScheduleExpander::getRewrittenKernel

MachineBasicBlock * getRewrittenKernel()

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

Definition:ModuloSchedule.h:278

llvm::ModuloScheduleExpander::cleanup

void cleanup()

Performs final cleanup after expansion.

Definition:ModuloSchedule.cpp:186

llvm::ModuloScheduleExpander::expand

void expand()

Performs the actual expansion.

Definition:ModuloSchedule.cpp:71

llvm::ModuloScheduleTestAnnotater::annotate

void annotate()

Performs the annotation.

Definition:ModuloSchedule.cpp:2843

llvm::ModuloSchedule

Represents a schedule for a single-block loop.

Definition:ModuloSchedule.h:80

llvm::ModuloSchedule::getNumStages

int getNumStages() const

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

Definition:ModuloSchedule.h:124

llvm::ModuloSchedule::getLoop

MachineLoop * getLoop() const

Return the single-block loop being scheduled.

Definition:ModuloSchedule.h:120

llvm::ModuloSchedule::getInstructions

ArrayRef< MachineInstr * > getInstructions()

Return the rescheduled instructions in order.

Definition:ModuloSchedule.h:153

llvm::ModuloSchedule::print

void print(raw_ostream &OS)

Definition:ModuloSchedule.cpp:29

llvm::ModuloSchedule::getCycle

int getCycle(MachineInstr *MI)

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

Definition:ModuloSchedule.h:141

llvm::ModuloSchedule::setStage

void setStage(MachineInstr *MI, int MIStage)

Set the stage of a newly created instruction.

Definition:ModuloSchedule.h:147

llvm::ModuloSchedule::getStage

int getStage(MachineInstr *MI)

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

Definition:ModuloSchedule.h:135

llvm::ModuloSchedule::dump

void dump()

Definition:ModuloSchedule.h:155

llvm::PassRegistry::getPassRegistry

static PassRegistry * getPassRegistry()

getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...

Definition:PassRegistry.cpp:24

llvm::PeelingModuloScheduleExpander::MF

MachineFunction & MF

Definition:ModuloSchedule.h:298

llvm::PeelingModuloScheduleExpander::PeeledBack

std::deque< MachineBasicBlock * > PeeledBack

Definition:ModuloSchedule.h:327

llvm::PeelingModuloScheduleExpander::IllegalPhisToDelete

SmallVector< MachineInstr *, 4 > IllegalPhisToDelete

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

Definition:ModuloSchedule.h:329

llvm::PeelingModuloScheduleExpander::expand

void expand()

Definition:ModuloSchedule.cpp:2010

llvm::PeelingModuloScheduleExpander::CanonicalMIs

DenseMap< MachineInstr *, MachineInstr * > CanonicalMIs

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

Definition:ModuloSchedule.h:322

llvm::PeelingModuloScheduleExpander::Prologs

SmallVector< MachineBasicBlock *, 4 > Prologs

All prolog and epilog blocks.

Definition:ModuloSchedule.h:309

llvm::PeelingModuloScheduleExpander::peelKernel

MachineBasicBlock * peelKernel(LoopPeelDirection LPD)

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

Definition:ModuloSchedule.cpp:1599

llvm::PeelingModuloScheduleExpander::Schedule

ModuloSchedule & Schedule

Definition:ModuloSchedule.h:297

llvm::PeelingModuloScheduleExpander::PeeledFront

std::deque< MachineBasicBlock * > PeeledFront

State passed from peelKernel to peelPrologAndEpilogs().

Definition:ModuloSchedule.h:327

llvm::PeelingModuloScheduleExpander::getStage

unsigned getStage(MachineInstr *MI)

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

Definition:ModuloSchedule.h:361

llvm::PeelingModuloScheduleExpander::rewriteUsesOf

void rewriteUsesOf(MachineInstr *MI)

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

Definition:ModuloSchedule.cpp:1915

llvm::PeelingModuloScheduleExpander::Epilogs

SmallVector< MachineBasicBlock *, 4 > Epilogs

Definition:ModuloSchedule.h:309

llvm::PeelingModuloScheduleExpander::AvailableStages

DenseMap< MachineBasicBlock *, BitVector > AvailableStages

For every block, the stages that are available.

Definition:ModuloSchedule.h:315

llvm::PeelingModuloScheduleExpander::BlockMIs

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

Definition:ModuloSchedule.h:324

llvm::PeelingModuloScheduleExpander::getEquivalentRegisterIn

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

Definition:ModuloSchedule.cpp:1908

llvm::PeelingModuloScheduleExpander::Preheader

MachineBasicBlock * Preheader

The original loop preheader.

Definition:ModuloSchedule.h:307

llvm::PeelingModuloScheduleExpander::rewriteKernel

void rewriteKernel()

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

Definition:ModuloSchedule.cpp:2005

llvm::PeelingModuloScheduleExpander::PhiNodeLoopIteration

DenseMap< MachineInstr *, unsigned > PhiNodeLoopIteration

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

Definition:ModuloSchedule.h:318

llvm::PeelingModuloScheduleExpander::LiveStages

DenseMap< MachineBasicBlock *, BitVector > LiveStages

For every block, the stages that are produced.

Definition:ModuloSchedule.h:311

llvm::PeelingModuloScheduleExpander::TII

const TargetInstrInfo * TII

Definition:ModuloSchedule.h:301

llvm::PeelingModuloScheduleExpander::filterInstructions

void filterInstructions(MachineBasicBlock *MB, int MinStage)

Definition:ModuloSchedule.cpp:1615

llvm::PeelingModuloScheduleExpander::peelPrologAndEpilogs

void peelPrologAndEpilogs()

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

Definition:ModuloSchedule.cpp:1747

llvm::PeelingModuloScheduleExpander::BB

MachineBasicBlock * BB

The original loop block that gets rewritten in-place.

Definition:ModuloSchedule.h:305

llvm::PeelingModuloScheduleExpander::fixupBranches

void fixupBranches()

Insert branches between prologs, kernel and epilogs.

Definition:ModuloSchedule.cpp:1958

llvm::PeelingModuloScheduleExpander::LIS

LiveIntervals * LIS

Definition:ModuloSchedule.h:302

llvm::PeelingModuloScheduleExpander::CreateLCSSAExitingBlock

MachineBasicBlock * CreateLCSSAExitingBlock()

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

Definition:ModuloSchedule.cpp:1864

llvm::PeelingModuloScheduleExpander::validateAgainstModuloScheduleExpander

void validateAgainstModuloScheduleExpander()

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

Definition:ModuloSchedule.cpp:2022

llvm::PeelingModuloScheduleExpander::getPhiCanonicalReg

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

Definition:ModuloSchedule.cpp:1730

llvm::PeelingModuloScheduleExpander::MRI

MachineRegisterInfo & MRI

Definition:ModuloSchedule.h:300

llvm::PeelingModuloScheduleExpander::moveStageBetweenBlocks

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

Definition:ModuloSchedule.cpp:1644

llvm::Register

Wrapper class representing virtual and physical registers.

Definition:Register.h:19

llvm::Register::isValid

constexpr bool isValid() const

Definition:Register.h:115

llvm::Register::isVirtual

constexpr bool isVirtual() const

Return true if the specified register number is in the virtual register namespace.

Definition:Register.h:91

llvm::Register::isPhysical

constexpr bool isPhysical() const

Return true if the specified register number is in the physical register namespace.

Definition:Register.h:95

llvm::SmallPtrSetImpl

A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...

Definition:SmallPtrSet.h:363

llvm::SmallPtrSetImpl::count

size_type count(ConstPtrType Ptr) const

count - Return 1 if the specified pointer is in the set, 0 otherwise.

Definition:SmallPtrSet.h:452

llvm::SmallPtrSetImpl::insert

std::pair< iterator, bool > insert(PtrType Ptr)

Inserts Ptr if and only if there is no element in the container equal to Ptr.

Definition:SmallPtrSet.h:384

llvm::SmallPtrSet

SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.

Definition:SmallPtrSet.h:519

llvm::SmallVectorBase::empty

bool empty() const

Definition:SmallVector.h:81

llvm::SmallVectorBase::size

size_t size() const

Definition:SmallVector.h:78

llvm::SmallVectorImpl

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

Definition:SmallVector.h:573

llvm::SmallVectorImpl::emplace_back

reference emplace_back(ArgTypes &&... Args)

Definition:SmallVector.h:937

llvm::SmallVectorImpl::erase

iterator erase(const_iterator CI)

Definition:SmallVector.h:737

llvm::SmallVectorImpl::clear

void clear()

Definition:SmallVector.h:610

llvm::SmallVectorImpl::resize

void resize(size_type N)

Definition:SmallVector.h:638

llvm::SmallVectorTemplateBase::push_back

void push_back(const T &Elt)

Definition:SmallVector.h:413

llvm::SmallVectorTemplateCommon::rbegin

reverse_iterator rbegin()

Definition:SmallVector.h:273

llvm::SmallVectorTemplateCommon::front

reference front()

Definition:SmallVector.h:299

llvm::SmallVectorTemplateCommon::begin

iterator begin()

Definition:SmallVector.h:267

llvm::SmallVectorTemplateCommon::back

reference back()

Definition:SmallVector.h:308

llvm::SmallVectorTemplateCommon::rend

reverse_iterator rend()

Definition:SmallVector.h:275

llvm::SmallVector

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

Definition:SmallVector.h:1196

llvm::StringRef

StringRef - Represent a constant reference to a string, i.e.

Definition:StringRef.h:51

llvm::TargetInstrInfo

TargetInstrInfo - Interface to description of machine instruction set.

Definition:TargetInstrInfo.h:112

llvm::TargetInstrInfo::reverseBranchCondition

virtual bool reverseBranchCondition(SmallVectorImpl< MachineOperand > &Cond) const

Reverses the branch condition of the specified condition list, returning false on success and true if...

Definition:TargetInstrInfo.h:1592

llvm::TargetInstrInfo::removeBranch

virtual unsigned removeBranch(MachineBasicBlock &MBB, int *BytesRemoved=nullptr) const

Remove the branching code at the end of the specific MBB.

Definition:TargetInstrInfo.h:714

llvm::TargetInstrInfo::analyzeLoopForPipelining

virtual std::unique_ptr< PipelinerLoopInfo > analyzeLoopForPipelining(MachineBasicBlock *LoopBB) const

Analyze loop L, which must be a single-basic-block loop, and if the conditions can be understood enou...

Definition:TargetInstrInfo.h:823

llvm::TargetInstrInfo::analyzeBranch

virtual bool analyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB, MachineBasicBlock *&FBB, SmallVectorImpl< MachineOperand > &Cond, bool AllowModify=false) const

Analyze the branching code at the end of MBB, returning true if it cannot be understood (e....

Definition:TargetInstrInfo.h:661

llvm::TargetInstrInfo::getBaseAndOffsetPosition

virtual bool getBaseAndOffsetPosition(const MachineInstr &MI, unsigned &BasePos, unsigned &OffsetPos) const

Return true if the instruction contains a base register and offset.

Definition:TargetInstrInfo.h:1512

llvm::TargetInstrInfo::insertBranch

virtual unsigned insertBranch(MachineBasicBlock &MBB, MachineBasicBlock *TBB, MachineBasicBlock *FBB, ArrayRef< MachineOperand > Cond, const DebugLoc &DL, int *BytesAdded=nullptr) const

Insert branch code into the end of the specified MachineBasicBlock.

Definition:TargetInstrInfo.h:732

llvm::TargetInstrInfo::insertUnconditionalBranch

unsigned insertUnconditionalBranch(MachineBasicBlock &MBB, MachineBasicBlock *DestBB, const DebugLoc &DL, int *BytesAdded=nullptr) const

Definition:TargetInstrInfo.h:740

llvm::TargetInstrInfo::getIncrementValue

virtual bool getIncrementValue(const MachineInstr &MI, int &Value) const

If the instruction is an increment of a constant value, return the amount.

Definition:TargetInstrInfo.h:1560

llvm::TargetInstrInfo::getMemOperandWithOffset

bool getMemOperandWithOffset(const MachineInstr &MI, const MachineOperand *&BaseOp, int64_t &Offset, bool &OffsetIsScalable, const TargetRegisterInfo *TRI) const

Get the base operand and byte offset of an instruction that reads/writes memory.

Definition:TargetInstrInfo.cpp:1426

llvm::TargetRegisterClass

Definition:TargetRegisterInfo.h:44

llvm::TargetRegisterInfo

TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...

Definition:TargetRegisterInfo.h:235

llvm::TargetSubtargetInfo::getRegisterInfo

virtual const TargetRegisterInfo * getRegisterInfo() const

getRegisterInfo - If register information is available, return it.

Definition:TargetSubtargetInfo.h:129

llvm::TargetSubtargetInfo::getInstrInfo

virtual const TargetInstrInfo * getInstrInfo() const

Definition:TargetSubtargetInfo.h:97

llvm::Target

Target - Wrapper for Target specific information.

Definition:TargetRegistry.h:144

llvm::Use

A Use represents the edge between a Value definition and its users.

Definition:Use.h:43

llvm::cl::opt

Definition:CommandLine.h:1423

llvm::detail::DenseSetImpl::insert

std::pair< iterator, bool > insert(const ValueT &V)

Definition:DenseSet.h:213

llvm::detail::DenseSetImpl::count

size_type count(const_arg_type_t< ValueT > V) const

Return 1 if the specified key is in the set, 0 otherwise.

Definition:DenseSet.h:95

llvm::ilist_node_impl::getIterator

self_iterator getIterator()

Definition:ilist_node.h:132

llvm::raw_ostream

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

Definition:raw_ostream.h:52

llvm::raw_ostream::flush

void flush()

Definition:raw_ostream.h:198

llvm::raw_string_ostream

A raw_ostream that writes to an std::string.

Definition:raw_ostream.h:661

llvm::raw_svector_ostream

A raw_ostream that writes to an SmallVector or SmallString.

Definition:raw_ostream.h:691

unsigned

ErrorHandling.h

llvm_unreachable

#define llvm_unreachable(msg)

Marks that the current location is not supposed to be reachable.

Definition:ErrorHandling.h:143

false

Definition:StackSlotColoring.cpp:193

llvm::CallingConv::ID

unsigned ID

LLVM IR allows to use arbitrary numbers as calling convention identifiers.

Definition:CallingConv.h:24

llvm::M68k::MemAddrModeKind::j

@ j

llvm::M68k::MemAddrModeKind::U

@ U

llvm::M68k::MemAddrModeKind::L

@ L

llvm::RISCVFenceField::R

@ R

Definition:RISCVBaseInfo.h:373

llvm::RISCVFenceField::O

@ O

Definition:RISCVBaseInfo.h:372

llvm::Sched::Source

@ Source

Definition:TargetLowering.h:102

llvm::X86Disassembler::Reg

Reg

All possible values of the reg field in the ModR/M byte.

Definition:X86DisassemblerDecoder.h:621

llvm::cl::Hidden

@ Hidden

Definition:CommandLine.h:137

llvm::cl::init

initializer< Ty > init(const Ty &Val)

Definition:CommandLine.h:443

llvm::logicalview::LVAttributeKind::Producer

@ Producer

llvm::numbers::e

constexpr double e

Definition:MathExtras.h:47

llvm::numbers::phi

constexpr double phi

Definition:MathExtras.h:61

llvm::rdf::Phi

NodeAddr< PhiNode * > Phi

Definition:RDFGraph.h:390

llvm::rdf::Def

NodeAddr< DefNode * > Def

Definition:RDFGraph.h:384

llvm::sys::path::end

const_iterator end(StringRef path LLVM_LIFETIME_BOUND)

Get end iterator over path.

Definition:Path.cpp:235

llvm::tgtok::In

@ In

Definition:TGLexer.h:84

llvm

This is an optimization pass for GlobalISel generic memory operations.

Definition:AddressRanges.h:18

llvm::Offset

@ Offset

Definition:DWP.cpp:480

llvm::find

auto find(R &&Range, const T &Val)

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

Definition:STLExtras.h:1759

llvm::PeelSingleBlockLoop

MachineBasicBlock * PeelSingleBlockLoop(LoopPeelDirection Direction, MachineBasicBlock *Loop, MachineRegisterInfo &MRI, const TargetInstrInfo *TII)

Peels a single block loop.

Definition:MachineLoopUtils.cpp:26

llvm::size

auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)

Get the size of a range.

Definition:STLExtras.h:1697

llvm::BuildMI

MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)

Builder interface. Specify how to create the initial instruction itself.

Definition:MachineInstrBuilder.h:373

llvm::Failed

testing::Matcher< const detail::ErrorHolder & > Failed()

Definition:Error.h:198

llvm::make_range

iterator_range< T > make_range(T x, T y)

Convenience function for iterating over sub-ranges.