HexagonHardwareLoops.cpp Source File (original) (raw)

54#include

55#include

56#include

57#include

58#include

59#include

60#include

61#include

62#include

64using namespace llvm;

66#define DEBUG_TYPE "hwloops"

68#ifndef NDEBUG

74#endif

79 cl::desc("Add a preheader to a hardware loop if one doesn't exist"));

85 cl::desc("Allow speculation of preheader "

86 "instructions"));

88 STATISTIC(NumHWLoops, "Number of loops converted to hardware loops");

90namespace {

92 class CountValue;

100#ifndef NDEBUG

101 static int Counter;

102#endif

103

104 public:

105 static char ID;

106

108

109 bool runOnMachineFunction(MachineFunction &MF) override;

110

111 StringRef getPassName() const override { return "Hexagon Hardware Loops"; }

112

113 void getAnalysisUsage(AnalysisUsage &AU) const override {

114 AU.addRequired();

115 AU.addRequired();

117 }

118

119 private:

120 using LoopFeederMap = std::map<Register, MachineInstr *>;

121

122

123 struct Comparison {

124 enum Kind {

125 EQ = 0x01,

126 NE = 0x02,

127 L = 0x04,

128 G = 0x08,

129 U = 0x40,

130 LTs = L,

131 LEs = L | EQ,

132 GTs = G,

133 GEs = G | EQ,

134 LTu = L | U,

135 LEu = L | EQ | U,

136 GTu = G | U,

137 GEu = G | EQ | U

138 };

139

140 static Kind getSwappedComparison(Kind Cmp) {

141 assert ((!((Cmp & L) && (Cmp & G))) && "Malformed comparison operator");

142 if ((Cmp & L) || (Cmp & G))

143 return (Kind)(Cmp ^ (L|G));

144 return Cmp;

145 }

146

147 static Kind getNegatedComparison(Kind Cmp) {

148 if ((Cmp & L) || (Cmp & G))

149 return (Kind)((Cmp ^ (L | G)) ^ EQ);

150 if ((Cmp & NE) || (Cmp & EQ))

151 return (Kind)(Cmp ^ (EQ | NE));

152 return (Kind)0;

153 }

154

155 static bool isSigned(Kind Cmp) {

156 return (Cmp & (L | G) && !(Cmp & U));

157 }

158

159 static bool isUnsigned(Kind Cmp) {

160 return (Cmp & U);

161 }

162 };

163

164

165

166

167

168

169

170

171

172

173

174

175

176 bool findInductionRegister(MachineLoop *L, Register &Reg,

177 int64_t &IVBump, MachineInstr *&IVOp) const;

178

179

180 Comparison::Kind getComparisonKind(unsigned CondOpc,

181 MachineOperand *InitialValue,

182 const MachineOperand *Endvalue,

183 int64_t IVBump) const;

184

185

186

187

188 CountValue *getLoopTripCount(MachineLoop *L,

189 SmallVectorImpl<MachineInstr *> &OldInsts);

190

191

192

193

194

195

196

197

198 CountValue *computeCount(MachineLoop *Loop, const MachineOperand *Start,

199 const MachineOperand *End, Register IVReg,

200 int64_t IVBump, Comparison::Kind Cmp) const;

201

202

203

204 bool isInvalidLoopOperation(const MachineInstr *MI,

205 bool IsInnerHWLoop) const;

206

207

208

209 bool containsInvalidInstruction(MachineLoop *L, bool IsInnerHWLoop) const;

210

211

212

213 bool convertToHardwareLoop(MachineLoop *L, bool &L0used, bool &L1used);

214

215

216 bool isDead(const MachineInstr *MI,

217 SmallVectorImpl<MachineInstr *> &DeadPhis) const;

218

219

220 void removeIfDead(MachineInstr *MI);

221

222

223

224

225

226 bool orderBumpCompare(MachineInstr *BumpI, MachineInstr *CmpI);

227

228

229

230

231 bool isLoopFeeder(MachineLoop *L, MachineBasicBlock *A, MachineInstr *MI,

232 const MachineOperand *MO,

233 LoopFeederMap &LoopFeederPhi) const;

234

235

236

237 bool phiMayWrapOrUnderflow(MachineInstr *Phi, const MachineOperand *EndVal,

238 MachineBasicBlock *MBB, MachineLoop *L,

239 LoopFeederMap &LoopFeederPhi) const;

240

241

242

243 bool loopCountMayWrapOrUnderFlow(const MachineOperand *InitVal,

244 const MachineOperand *EndVal,

245 MachineBasicBlock *MBB, MachineLoop *L,

246 LoopFeederMap &LoopFeederPhi) const;

247

248

249

250

251 bool checkForImmediate(const MachineOperand &MO, int64_t &Val) const;

252

253

254 bool isImmediate(const MachineOperand &MO) const {

255 int64_t V;

256 return checkForImmediate(MO, V);

257 }

258

259

260 int64_t getImmediate(const MachineOperand &MO) const {

261 int64_t V;

262 if (!checkForImmediate(MO, V))

264 return V;

265 }

266

267

268

269

270 void setImmediate(MachineOperand &MO, int64_t Val);

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291 bool fixupInductionVariable(MachineLoop *L);

292

293

294

295 MachineBasicBlock *createPreheaderForLoop(MachineLoop *L);

296 };

297

298 char HexagonHardwareLoops::ID = 0;

299#ifndef NDEBUG

300 int HexagonHardwareLoops::Counter = 0;

301#endif

302

303

304

305

306 class CountValue {

307 public:

308 enum CountValueType {

309 CV_Register,

310 CV_Immediate

311 };

312

313 private:

314 CountValueType Kind;

315 union Values {

316 Values() : R{Register(), 0} {}

317 Values(const Values&) = default;

318 struct {

320 unsigned Sub;

321 } R;

322 unsigned ImmVal;

323 } Contents;

324

325 public:

326 explicit CountValue(CountValueType t, Register v, unsigned u = 0) {

327 Kind = t;

328 if (Kind == CV_Register) {

329 Contents.R.Reg = v;

330 Contents.R.Sub = u;

331 } else {

332 Contents.ImmVal = v;

333 }

334 }

335

336 bool isReg() const { return Kind == CV_Register; }

337 bool isImm() const { return Kind == CV_Immediate; }

338

340 assert(isReg() && "Wrong CountValue accessor");

341 return Contents.R.Reg;

342 }

343

344 unsigned getSubReg() const {

345 assert(isReg() && "Wrong CountValue accessor");

346 return Contents.R.Sub;

347 }

348

349 unsigned getImm() const {

350 assert(isImm() && "Wrong CountValue accessor");

351 return Contents.ImmVal;

352 }

353

354 void print(raw_ostream &OS, const TargetRegisterInfo *TRI = nullptr) const {

355 if (isReg()) { OS << printReg(Contents.R.Reg, TRI, Contents.R.Sub); }

356 if (isImm()) { OS << Contents.ImmVal; }

357 }

358 };

359

360}

361

363 "Hexagon Hardware Loops", false, false)

368

370 return new HexagonHardwareLoops();

371}

372

373bool HexagonHardwareLoops::runOnMachineFunction(MachineFunction &MF) {

374 LLVM_DEBUG(dbgs() << "********* Hexagon Hardware Loops *********\n");

376 return false;

377

379

380 MLI = &getAnalysis().getLI();

382 MDT = &getAnalysis().getDomTree();

386

387 for (auto &L : *MLI)

388 if (L->isOutermost()) {

389 bool L0Used = false;

390 bool L1Used = false;

391 Changed |= convertToHardwareLoop(L, L0Used, L1Used);

392 }

393

395}

396

397bool HexagonHardwareLoops::findInductionRegister(MachineLoop *L,

399 int64_t &IVBump,

400 MachineInstr *&IVOp

401 ) const {

402 MachineBasicBlock *Header = L->getHeader();

403 MachineBasicBlock *Preheader = MLI->findLoopPreheader(L, SpecPreheader);

404 MachineBasicBlock *Latch = L->getLoopLatch();

405 MachineBasicBlock *ExitingBlock = L->findLoopControlBlock();

406 if (!Header || !Preheader || !Latch || !ExitingBlock)

407 return false;

408

409

410

411 using RegisterBump = std::pair<Register, int64_t>;

412

413

414

415

416

417 using InductionMap = std::map<Register, RegisterBump>;

418

419 InductionMap IndMap;

420

422

423 for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();

424 I != E && I->isPHI(); ++I) {

425 MachineInstr *Phi = &*I;

426

427

428

429

430 for (unsigned i = 1, n = Phi->getNumOperands(); i < n; i += 2) {

431 if (Phi->getOperand(i+1).getMBB() != Latch)

432 continue;

433

434 Register PhiOpReg = Phi->getOperand(i).getReg();

435 MachineInstr *DI = MRI->getVRegDef(PhiOpReg);

436

438

439

441 MachineOperand &Opnd2 = DI->getOperand(2);

442 int64_t V;

443 if (MRI->getVRegDef(IndReg) == Phi && checkForImmediate(Opnd2, V)) {

445 IndMap.insert(std::make_pair(UpdReg, std::make_pair(IndReg, V)));

446 }

447 }

448 }

449 }

450

452 MachineBasicBlock *TB = nullptr, *FB = nullptr;

454 if (NotAnalyzed)

455 return false;

456

458 unsigned PredPos, PredRegFlags;

459 if ( TII ->getPredReg(Cond, PredR, PredPos, PredRegFlags))

460 return false;

461

462 MachineInstr *PredI = MRI->getVRegDef(PredR);

464 return false;

465

467 int64_t CmpImm = 0, CmpMask = 0;

468 bool CmpAnalyzed =

470

471

472

473 if (!CmpAnalyzed)

474 return false;

475

476

477

478 InductionMap::iterator IndMapEnd = IndMap.end();

479 InductionMap::iterator F = IndMapEnd;

480 if (CmpReg1 != 0) {

481 InductionMap::iterator F1 = IndMap.find(CmpReg1);

482 if (F1 != IndMapEnd)

483 F = F1;

484 }

485 if (CmpReg2 != 0) {

486 InductionMap::iterator F2 = IndMap.find(CmpReg2);

487 if (F2 != IndMapEnd) {

488 if (F != IndMapEnd)

489 return false;

490 F = F2;

491 }

492 }

493 if (F == IndMapEnd)

494 return false;

495

496 Reg = F->second.first;

497 IVBump = F->second.second;

498 IVOp = MRI->getVRegDef(F->first);

499 return true;

500}

501

502

503HexagonHardwareLoops::Comparison::Kind

504HexagonHardwareLoops::getComparisonKind(unsigned CondOpc,

505 MachineOperand *InitialValue,

506 const MachineOperand *EndValue,

507 int64_t IVBump) const {

508 Comparison::Kind Cmp = (Comparison::Kind)0;

509 switch (CondOpc) {

510 case Hexagon::C2_cmpeq:

511 case Hexagon::C2_cmpeqi:

512 case Hexagon::C2_cmpeqp:

513 Cmp = Comparison::EQ;

514 break;

515 case Hexagon::C4_cmpneq:

516 case Hexagon::C4_cmpneqi:

517 Cmp = Comparison::NE;

518 break;

519 case Hexagon::C2_cmplt:

520 Cmp = Comparison::LTs;

521 break;

522 case Hexagon::C2_cmpltu:

523 Cmp = Comparison::LTu;

524 break;

525 case Hexagon::C4_cmplte:

526 case Hexagon::C4_cmpltei:

527 Cmp = Comparison::LEs;

528 break;

529 case Hexagon::C4_cmplteu:

530 case Hexagon::C4_cmplteui:

531 Cmp = Comparison::LEu;

532 break;

533 case Hexagon::C2_cmpgt:

534 case Hexagon::C2_cmpgti:

535 case Hexagon::C2_cmpgtp:

536 Cmp = Comparison::GTs;

537 break;

538 case Hexagon::C2_cmpgtu:

539 case Hexagon::C2_cmpgtui:

540 case Hexagon::C2_cmpgtup:

541 Cmp = Comparison::GTu;

542 break;

543 case Hexagon::C2_cmpgei:

544 Cmp = Comparison::GEs;

545 break;

546 case Hexagon::C2_cmpgeui:

547 Cmp = Comparison::GEs;

548 break;

549 default:

550 return (Comparison::Kind)0;

551 }

552 return Cmp;

553}

554

555

556

557

558

559

560

561

562CountValue *HexagonHardwareLoops::getLoopTripCount(MachineLoop *L,

563 SmallVectorImpl<MachineInstr *> &OldInsts) {

564 MachineBasicBlock *TopMBB = L->getTopBlock();

567 "Loop must have more than one incoming edge!");

568 MachineBasicBlock *Backedge = *PI++;

569 if (PI == TopMBB->pred_end())

570 return nullptr;

571 MachineBasicBlock *Incoming = *PI++;

572 if (PI != TopMBB->pred_end())

573 return nullptr;

574

575

576

577 if (L->contains(Incoming)) {

578 if (L->contains(Backedge))

579 return nullptr;

581 } else if (->contains(Backedge))

582 return nullptr;

583

584

585

586

587 MachineBasicBlock *ExitingBlock = L->findLoopControlBlock();

588 if (!ExitingBlock)

589 return nullptr;

590

592 int64_t IVBump = 0;

593 MachineInstr *IVOp;

594 bool FoundIV = findInductionRegister(L, IVReg, IVBump, IVOp);

595 if (!FoundIV)

596 return nullptr;

597

598 MachineBasicBlock *Preheader = MLI->findLoopPreheader(L, SpecPreheader);

599

600 MachineOperand *InitialValue = nullptr;

601 MachineInstr *IV_Phi = MRI->getVRegDef(IVReg);

602 MachineBasicBlock *Latch = L->getLoopLatch();

603 for (unsigned i = 1, n = IV_Phi->getNumOperands(); i < n; i += 2) {

605 if (MBB == Preheader)

606 InitialValue = &IV_Phi->getOperand(i);

607 else if (MBB == Latch)

608 IVReg = IV_Phi->getOperand(i).getReg();

609 }

610 if (!InitialValue)

611 return nullptr;

612

614 MachineBasicBlock *TB = nullptr, *FB = nullptr;

616 if (NotAnalyzed)

617 return nullptr;

618

619 MachineBasicBlock *Header = L->getHeader();

620

621

622

623 assert (TB && "Exit block without a branch?");

624 if (ExitingBlock != Latch && (TB == Latch || FB == Latch)) {

625 MachineBasicBlock *LTB = nullptr, *LFB = nullptr;

627 bool NotAnalyzed = TII->analyzeBranch(*Latch, LTB, LFB, LCond, false);

628 if (NotAnalyzed)

629 return nullptr;

630 if (TB == Latch)

631 TB = (LTB == Header) ? LTB : LFB;

632 else

633 FB = (LTB == Header) ? LTB: LFB;

634 }

635 assert ((!FB || TB == Header || FB == Header) && "Branches not to header?");

636 if (!TB || (FB && TB != Header && FB != Header))

637 return nullptr;

638

639

640

641

642

643 bool Negated = TII->predOpcodeHasNot(Cond) ^ (TB != Header);

645 unsigned PredPos, PredRegFlags;

646 if ( TII ->getPredReg(Cond, PredReg, PredPos, PredRegFlags))

647 return nullptr;

648 MachineInstr *CondI = MRI->getVRegDef(PredReg);

649 unsigned CondOpc = CondI->getOpcode();

650

652 int64_t Mask = 0, ImmValue = 0;

653 bool AnalyzedCmp =

655 if (!AnalyzedCmp)

656 return nullptr;

657

658

659

662

663

664

665

666

667

668 Comparison::Kind Cmp;

669 bool isSwapped = false;

670 const MachineOperand &Op1 = CondI->getOperand(1);

671 const MachineOperand &Op2 = CondI->getOperand(2);

672 const MachineOperand *EndValue = nullptr;

673

674 if (Op1.isReg()) {

675 if (Op2.isImm() || Op1.getReg() == IVReg)

676 EndValue = &Op2;

677 else {

678 EndValue = &Op1;

679 isSwapped = true;

680 }

681 }

682

683 if (!EndValue)

684 return nullptr;

685

686 Cmp = getComparisonKind(CondOpc, InitialValue, EndValue, IVBump);

687 if (!Cmp)

688 return nullptr;

689 if (Negated)

690 Cmp = Comparison::getNegatedComparison(Cmp);

691 if (isSwapped)

692 Cmp = Comparison::getSwappedComparison(Cmp);

693

694 if (InitialValue->isReg()) {

696 MachineBasicBlock *DefBB = MRI->getVRegDef(R)->getParent();

698 int64_t V;

699 if (!checkForImmediate(*InitialValue, V))

700 return nullptr;

701 }

703 }

704 if (EndValue->isReg()) {

706 MachineBasicBlock *DefBB = MRI->getVRegDef(R)->getParent();

708 int64_t V;

709 if (!checkForImmediate(*EndValue, V))

710 return nullptr;

711 }

713 }

714

715 return computeCount(L, InitialValue, EndValue, IVReg, IVBump, Cmp);

716}

717

718

719

720

721

722CountValue *HexagonHardwareLoops::computeCount(MachineLoop *Loop,

723 const MachineOperand *Start,

724 const MachineOperand *End,

726 int64_t IVBump,

727 Comparison::Kind Cmp) const {

733

734 if (Cmp == Comparison::EQ)

735 return nullptr;

736

737

738

739 if (Start->isReg()) {

740 const MachineInstr *StartValInstr = MRI->getVRegDef(Start->getReg());

741 if (StartValInstr && (StartValInstr->getOpcode() == Hexagon::A2_tfrsi ||

742 StartValInstr->getOpcode() == Hexagon::A2_tfrpi))

744 }

745 if (End->isReg()) {

746 const MachineInstr *EndValInstr = MRI->getVRegDef(End->getReg());

747 if (EndValInstr && (EndValInstr->getOpcode() == Hexagon::A2_tfrsi ||

748 EndValInstr->getOpcode() == Hexagon::A2_tfrpi))

750 }

751

752 if ( Start ->isReg() && Start ->isImm())

753 return nullptr;

755 return nullptr;

756

757 bool CmpLess = Cmp & Comparison::L;

758 bool CmpGreater = Cmp & Comparison::G;

759 bool CmpHasEqual = Cmp & Comparison::EQ;

760

761

762 if (CmpLess && IVBump < 0)

763

764 return nullptr;

765

766 if (CmpGreater && IVBump > 0)

767

768 return nullptr;

769

770

771 LoopFeederMap LoopFeederPhi;

772

773

774

775

776 if (loopCountMayWrapOrUnderFlow(Start, End, Loop->getLoopPreheader(), Loop,

777 LoopFeederPhi))

778 return nullptr;

779

780 if (Start->isImm() && End->isImm()) {

781

782 int64_t StartV = Start->getImm();

783 int64_t EndV = End->getImm();

784 int64_t Dist = EndV - StartV;

785 if (Dist == 0)

786 return nullptr;

787

788 bool Exact = (Dist % IVBump) == 0;

789

790 if (Cmp == Comparison::NE) {

791 if (!Exact)

792 return nullptr;

793 if ((Dist < 0) ^ (IVBump < 0))

794 return nullptr;

795 }

796

797

798

799 if (CmpHasEqual)

800 Dist = Dist > 0 ? Dist+1 : Dist-1;

801

802

803

804

805

806 if ((CmpLess && Dist < 0) || (CmpGreater && Dist > 0))

807 return nullptr;

808

809

810 int64_t Dist1 = (IVBump > 0) ? (Dist + (IVBump - 1)) / IVBump

811 : (-Dist + (-IVBump - 1)) / (-IVBump);

812 assert (Dist1 > 0 && "Fishy thing. Both operands have the same sign.");

813

814 uint64_t Count = Dist1;

815

816 if (Count > 0xFFFFFFFFULL)

817 return nullptr;

818

819 return new CountValue(CountValue::CV_Immediate, Count);

820 }

821

822

823

824

825

826

827

829 return nullptr;

830

831 MachineBasicBlock *PH = MLI->findLoopPreheader(Loop, SpecPreheader);

832 assert (PH && "Should have a preheader by now");

835 if (InsertPos != PH->end())

836 DL = InsertPos->getDebugLoc();

837

838

839

840

841

842

843

844

845 if (IVBump < 0) {

847 IVBump = -IVBump;

849 }

850

851

852

853 bool RegToImm = Start->isReg() && End->isImm();

854 bool RegToReg = Start->isReg() && End->isReg();

855

856 int64_t StartV = 0, EndV = 0;

857 if (Start->isImm())

858 StartV = Start->getImm();

859 if (End->isImm())

860 EndV = End->getImm();

861

862 int64_t AdjV = 0;

863

864

865

866

867

868

869

870

871 if (CmpHasEqual) {

872

873 if (Start->isImm())

874 StartV--;

875 else if (End->isImm())

876 EndV++;

877 else

878 AdjV += 1;

879 }

880

881 if (Cmp != Comparison::NE) {

882 if (Start->isImm())

883 StartV -= (IVBump-1);

884 else if (End->isImm())

885 EndV += (IVBump-1);

886 else

887 AdjV += (IVBump-1);

888 }

889

891 unsigned SR = 0;

892 if (Start->isReg()) {

894 SR = Start->getSubReg();

895 } else {

898 }

899 const TargetRegisterClass *RC = MRI->getRegClass(R);

900

901

902 if (!SR && RC == &Hexagon::DoubleRegsRegClass)

903 return nullptr;

904 const TargetRegisterClass *IntRC = &Hexagon::IntRegsRegClass;

905

906

908 unsigned DistSR;

909

910

911 if (Start->isImm() && StartV == 0) {

912 DistR = End->getReg();

914 } else {

915 const MCInstrDesc &SubD = RegToReg ? TII->get(Hexagon::A2_sub) :

916 (RegToImm ? TII->get(Hexagon::A2_subri) :

917 TII->get(Hexagon::A2_addi));

918 if (RegToReg || RegToImm) {

919 Register SubR = MRI->createVirtualRegister(IntRC);

920 MachineInstrBuilder SubIB =

921 BuildMI(*PH, InsertPos, DL, SubD, SubR);

922

923 if (RegToReg)

926 else

929 DistR = SubR;

930 } else {

931

932

933

934 const MachineInstr *EndValInstr = MRI->getVRegDef(End->getReg());

935 if (EndValInstr->getOpcode() == Hexagon::A2_addi &&

939 } else {

940 Register SubR = MRI->createVirtualRegister(IntRC);

941 MachineInstrBuilder SubIB =

942 BuildMI(*PH, InsertPos, DL, SubD, SubR);

945 DistR = SubR;

946 }

947 }

948 DistSR = 0;

949 }

950

951

953 unsigned AdjSR;

954

955 if (AdjV == 0) {

956 AdjR = DistR;

957 AdjSR = DistSR;

958 } else {

959

960 Register AddR = MRI->createVirtualRegister(IntRC);

961 MCInstrDesc const &AddD = TII->get(Hexagon::A2_addi);

962 BuildMI(*PH, InsertPos, DL, AddD, AddR)

963 .addReg(DistR, 0, DistSR)

965

966 AdjR = AddR;

967 AdjSR = 0;

968 }

969

970

972 unsigned CountSR;

973

974 if (IVBump == 1) {

975 CountR = AdjR;

976 CountSR = AdjSR;

977 } else {

978

979 unsigned Shift = Log2_32(IVBump);

980

981

982 Register LsrR = MRI->createVirtualRegister(IntRC);

983 const MCInstrDesc &LsrD = TII->get(Hexagon::S2_lsr_i_r);

984 BuildMI(*PH, InsertPos, DL, LsrD, LsrR)

985 .addReg(AdjR, 0, AdjSR)

987

988 CountR = LsrR;

989 CountSR = 0;

990 }

991

992 const TargetRegisterClass *PredRC = &Hexagon::PredRegsRegClass;

994 unsigned MuxSR = CountSR;

995

996

997

998 if (!(Start->isImm() && StartV == 0 && Comparison::isUnsigned(Cmp) &&

999 CmpLess) &&

1000 (CmpLess || CmpGreater)) {

1001

1002

1003

1004 Register DistCheckR = MRI->createVirtualRegister(PredRC);

1005 const MCInstrDesc &DistCheckD = TII->get(Hexagon::C2_cmpgti);

1006 BuildMI(*PH, InsertPos, DL, DistCheckD, DistCheckR)

1007 .addReg(DistR, 0, DistSR)

1008 .addImm((CmpLess) ? 0 : -1);

1009

1010

1011

1012

1013 MuxR = MRI->createVirtualRegister(IntRC);

1014 if (CmpLess) {

1015 const MCInstrDesc &MuxD = TII->get(Hexagon::C2_muxir);

1016 BuildMI(*PH, InsertPos, DL, MuxD, MuxR)

1018 .addReg(CountR, 0, CountSR)

1020 } else {

1021 const MCInstrDesc &MuxD = TII->get(Hexagon::C2_muxri);

1022 BuildMI(*PH, InsertPos, DL, MuxD, MuxR)

1025 .addReg(CountR, 0, CountSR);

1026 }

1027 MuxSR = 0;

1028 }

1029

1030 return new CountValue(CountValue::CV_Register, MuxR, MuxSR);

1031}

1032

1033

1034bool HexagonHardwareLoops::isInvalidLoopOperation(const MachineInstr *MI,

1035 bool IsInnerHWLoop) const {

1036

1037

1038 if (MI->getDesc().isCall())

1039 return TII ->doesNotReturn(*MI);

1040

1041

1042 using namespace Hexagon;

1043

1044 static const Register Regs01[] = { LC0, SA0, LC1, SA1 };

1045 static const Register Regs1[] = { LC1, SA1 };

1046 auto CheckRegs = IsInnerHWLoop ? ArrayRef(Regs01) : ArrayRef(Regs1);

1047 for (Register R : CheckRegs)

1048 if (MI->modifiesRegister(R, TRI))

1049 return true;

1050

1051 return false;

1052}

1053

1054

1055

1056bool HexagonHardwareLoops::containsInvalidInstruction(MachineLoop *L,

1057 bool IsInnerHWLoop) const {

1060 for (MachineBasicBlock *MBB : L->getBlocks()) {

1061 for (const MachineInstr &MI : *MBB) {

1062 if (isInvalidLoopOperation(&MI, IsInnerHWLoop)) {

1063 LLVM_DEBUG(dbgs() << "\nCannot convert to hw_loop due to:";

1065 return true;

1066 }

1067 }

1068 }

1069 return false;

1070}

1071

1072

1073

1074

1075

1076bool HexagonHardwareLoops::isDead(const MachineInstr *MI,

1077 SmallVectorImpl<MachineInstr *> &DeadPhis) const {

1078

1079 for (const MachineOperand &MO : MI->operands()) {

1081 continue;

1082

1084 if (MRI->use_nodbg_empty(Reg))

1085 continue;

1086

1088

1089

1090

1091

1092 use_nodbg_iterator I = MRI->use_nodbg_begin(Reg);

1093 use_nodbg_iterator End = MRI->use_nodbg_end();

1094 if (std::next(I) != End || ->getParent()->isPHI())

1095 return false;

1096

1097 MachineInstr *OnePhi = I->getParent();

1098 for (const MachineOperand &OPO : OnePhi->operands()) {

1099 if (!OPO.isReg() || !OPO.isDef())

1100 continue;

1101

1102 Register OPReg = OPO.getReg();

1103 use_nodbg_iterator nextJ;

1104 for (use_nodbg_iterator J = MRI->use_nodbg_begin(OPReg);

1105 J != End; J = nextJ) {

1106 nextJ = std::next(J);

1107 MachineOperand &Use = *J;

1108 MachineInstr *UseMI = Use.getParent();

1109

1110

1112 return false;

1113 }

1114 }

1116 }

1117

1118

1119 return true;

1120}

1121

1122void HexagonHardwareLoops::removeIfDead(MachineInstr *MI) {

1123

1124

1128

1129

1130

1131

1132 for (const MachineOperand &MO : MI->operands()) {

1134 continue;

1136

1137

1138 for (MachineOperand &MO :

1142 continue;

1145 }

1146 }

1147

1148 MI->eraseFromParent();

1149 for (unsigned i = 0; i < DeadPhis.size(); ++i)

1150 DeadPhis[i]->eraseFromParent();

1151 }

1152}

1153

1154

1155

1156

1157

1158

1159

1160

1161

1162bool HexagonHardwareLoops::convertToHardwareLoop(MachineLoop *L,

1163 bool &RecL0used,

1164 bool &RecL1used) {

1165

1166 assert(L->getHeader() && "Loop without a header?");

1167

1169 bool L0Used = false;

1170 bool L1Used = false;

1171

1172

1173 for (MachineLoop *I : *L) {

1174 Changed |= convertToHardwareLoop(I, RecL0used, RecL1used);

1175 L0Used |= RecL0used;

1176 L1Used |= RecL1used;

1177 }

1178

1179

1180 if (Changed && L0Used && L1Used)

1182

1183 unsigned LOOP_i;

1184 unsigned LOOP_r;

1185 unsigned ENDLOOP;

1186

1187

1188

1189

1190 unsigned IsInnerHWLoop = 1;

1191

1192 if (L0Used) {

1193 LOOP_i = Hexagon::J2_loop1i;

1194 LOOP_r = Hexagon::J2_loop1r;

1195 ENDLOOP = Hexagon::ENDLOOP1;

1196 IsInnerHWLoop = 0;

1197 } else {

1198 LOOP_i = Hexagon::J2_loop0i;

1199 LOOP_r = Hexagon::J2_loop0r;

1200 ENDLOOP = Hexagon::ENDLOOP0;

1201 }

1202

1203#ifndef NDEBUG

1204

1206 if (Limit >= 0) {

1208 return false;

1209 Counter++;

1210 }

1211#endif

1212

1213

1214 if (containsInvalidInstruction(L, IsInnerHWLoop))

1215 return false;

1216

1217 MachineBasicBlock *LastMBB = L->findLoopControlBlock();

1218

1219 if (!LastMBB)

1220 return false;

1221

1223 if (LastI == LastMBB->end())

1224 return false;

1225

1226

1227 if (!fixupInductionVariable(L))

1228 return false;

1229

1230

1231

1232 MachineBasicBlock *Preheader = MLI->findLoopPreheader(L, SpecPreheader);

1233 if (!Preheader) {

1234 Preheader = createPreheaderForLoop(L);

1235 if (!Preheader)

1236 return false;

1237 }

1238

1240

1241 SmallVector<MachineInstr*, 2> OldInsts;

1242

1243 CountValue *TripCount = getLoopTripCount(L, OldInsts);

1244 if (!TripCount)

1245 return false;

1246

1247

1248 if (TripCount->isReg()) {

1249

1250

1251 MachineInstr *TCDef = MRI->getVRegDef(TripCount->getReg());

1252 MachineBasicBlock *BBDef = TCDef->getParent();

1253 if (!MDT->dominates(BBDef, Preheader))

1254 return false;

1255 }

1256

1257

1258 MachineBasicBlock *TopBlock = L->getTopBlock();

1259 MachineBasicBlock *ExitingBlock = L->findLoopControlBlock();

1260 MachineBasicBlock *LoopStart = nullptr;

1261 if (ExitingBlock != L->getLoopLatch()) {

1262 MachineBasicBlock *TB = nullptr, *FB = nullptr;

1264

1266 return false;

1267

1268 if (L->contains(TB))

1269 LoopStart = TB;

1270 else if (L->contains(FB))

1271 LoopStart = FB;

1272 else

1273 return false;

1274 }

1275 else

1276 LoopStart = TopBlock;

1277

1278

1279 LLVM_DEBUG(dbgs() << "Change to hardware loop at "; L->dump());

1281 if (InsertPos != Preheader->end())

1282 DL = InsertPos->getDebugLoc();

1283

1284 if (TripCount->isReg()) {

1285

1286 Register CountReg = MRI->createVirtualRegister(&Hexagon::IntRegsRegClass);

1287 BuildMI(*Preheader, InsertPos, DL, TII->get(TargetOpcode::COPY), CountReg)

1288 .addReg(TripCount->getReg(), 0, TripCount->getSubReg());

1289

1292 } else {

1293 assert(TripCount->isImm() && "Expecting immediate value for trip count");

1294

1295

1296

1297 int64_t CountImm = TripCount->getImm();

1298 if ( TII ->isValidOffset(LOOP_i, CountImm, TRI)) {

1299 Register CountReg = MRI->createVirtualRegister(&Hexagon::IntRegsRegClass);

1300 BuildMI(*Preheader, InsertPos, DL, TII->get(Hexagon::A2_tfrsi), CountReg)

1304 } else

1307 }

1308

1309

1311

1312

1313 DebugLoc LastIDL = LastI->getDebugLoc();

1315

1316

1317

1318

1319 if (LastI->getOpcode() == Hexagon::J2_jumpt ||

1320 LastI->getOpcode() == Hexagon::J2_jumpf) {

1321

1322 MachineBasicBlock *BranchTarget = LastI->getOperand(1).getMBB();

1323 LastI = LastMBB->erase(LastI);

1324 if (->contains(BranchTarget)) {

1325 if (LastI != LastMBB->end())

1326 LastI = LastMBB->erase(LastI);

1329 }

1330 } else {

1331

1332 LastMBB->erase(LastI);

1333 }

1334 delete TripCount;

1335

1336

1337

1338 for (unsigned i = 0; i < OldInsts.size(); ++i)

1339 removeIfDead(OldInsts[i]);

1340

1341 ++NumHWLoops;

1342

1343

1344

1345

1346 if (L0Used)

1347 RecL1used = true;

1348 else

1349 RecL0used = true;

1350

1351 return true;

1352}

1353

1354bool HexagonHardwareLoops::orderBumpCompare(MachineInstr *BumpI,

1355 MachineInstr *CmpI) {

1356 assert (BumpI != CmpI && "Bump and compare in the same instruction?");

1357

1358 MachineBasicBlock *BB = BumpI->getParent();

1360 return false;

1361

1363

1364

1365 for (instr_iterator I(BumpI), E = BB->instr_end(); I != E; ++I)

1366 if (&*I == CmpI)

1367 return true;

1368

1369

1371 bool FoundBump = false;

1372 instr_iterator CmpIt = CmpI->getIterator(), NextIt = std::next(CmpIt);

1373 for (instr_iterator I = NextIt, E = BB->instr_end(); I != E; ++I) {

1374 MachineInstr *In = &*I;

1375 for (unsigned i = 0, n = In->getNumOperands(); i < n; ++i) {

1376 MachineOperand &MO = In->getOperand(i);

1378 if (MO.getReg() == PredR)

1379 return false;

1380 }

1381 }

1382

1383 if (In == BumpI) {

1385 FoundBump = true;

1386 break;

1387 }

1388 }

1389 assert (FoundBump && "Cannot determine instruction order");

1390 return FoundBump;

1391}

1392

1393

1394

1395

1396

1397

1398bool HexagonHardwareLoops::isLoopFeeder(MachineLoop *L, MachineBasicBlock *A,

1399 MachineInstr *MI,

1400 const MachineOperand *MO,

1401 LoopFeederMap &LoopFeederPhi) const {

1402 if (LoopFeederPhi.find(MO->getReg()) == LoopFeederPhi.end()) {

1405

1407 return false;

1408 MachineInstr *Def = MRI->getVRegDef(MO->getReg());

1409 LoopFeederPhi.insert(std::make_pair(MO->getReg(), Def));

1410 return true;

1411 } else

1412

1413 return false;

1414}

1415

1416

1417

1418bool HexagonHardwareLoops::phiMayWrapOrUnderflow(

1419 MachineInstr *Phi, const MachineOperand *EndVal, MachineBasicBlock *MBB,

1420 MachineLoop *L, LoopFeederMap &LoopFeederPhi) const {

1421 assert(Phi->isPHI() && "Expecting a Phi.");

1422

1423

1424 for (int i = 1, n = Phi->getNumOperands(); i < n; i += 2)

1425 if (isLoopFeeder(L, MBB, Phi, &(Phi->getOperand(i)), LoopFeederPhi))

1426 if (loopCountMayWrapOrUnderFlow(&(Phi->getOperand(i)), EndVal,

1427 Phi->getParent(), L, LoopFeederPhi))

1428 return true;

1429 return false;

1430}

1431

1432

1433

1434

1435

1436

1437

1438

1439

1440

1441

1442

1443

1444

1445

1446bool HexagonHardwareLoops::loopCountMayWrapOrUnderFlow(

1447 const MachineOperand *InitVal, const MachineOperand *EndVal,

1448 MachineBasicBlock *MBB, MachineLoop *L,

1449 LoopFeederMap &LoopFeederPhi) const {

1450

1451 if (!InitVal->isReg())

1452 return false;

1453

1454 if (!EndVal->isImm())

1455 return false;

1456

1457

1458

1459 int64_t Imm;

1460 if (checkForImmediate(*InitVal, Imm))

1461 return (EndVal->getImm() == Imm);

1462

1464

1465

1467 return true;

1468

1469 MachineInstr *Def = MRI->getVRegDef(Reg);

1470 if (!Def)

1471 return true;

1472

1473

1474

1475 if (Def->isPHI() && !phiMayWrapOrUnderflow(Def, EndVal, Def->getParent(),

1476 L, LoopFeederPhi))

1477 return false;

1478 if (Def->isCopy() && !loopCountMayWrapOrUnderFlow(&(Def->getOperand(1)),

1479 EndVal, Def->getParent(),

1480 L, LoopFeederPhi))

1481 return false;

1482

1483

1484

1485

1487 E = MRI->use_instr_nodbg_end(); I != E; ++I) {

1488 MachineInstr *MI = &*I;

1490 int64_t CmpMask = 0, CmpValue = 0;

1491

1493 continue;

1494

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

1498 continue;

1499

1500 Comparison::Kind Cmp =

1501 getComparisonKind(MI->getOpcode(), nullptr, nullptr, 0);

1502 if (Cmp == 0)

1503 continue;

1505 Cmp = Comparison::getNegatedComparison(Cmp);

1506 if (CmpReg2 != 0 && CmpReg2 == Reg)

1507 Cmp = Comparison::getSwappedComparison(Cmp);

1508

1509

1510 if (Comparison::isSigned(Cmp))

1511 return false;

1512

1513

1514

1515

1516 if ((Cmp & Comparison::G) || Cmp == Comparison::NE)

1517 return false;

1518 }

1519

1520

1521

1522

1523 if ( Def ->isCopy() && Def ->isPHI())

1524 return false;

1525

1526 return true;

1527}

1528

1529bool HexagonHardwareLoops::checkForImmediate(const MachineOperand &MO,

1530 int64_t &Val) const {

1531 if (MO.isImm()) {

1533 return true;

1534 }

1535 if (!MO.isReg())

1536 return false;

1537

1538

1539

1540

1541 int64_t TV;

1542

1544 if (.isVirtual())

1545 return false;

1546 MachineInstr *DI = MRI->getVRegDef(R);

1547 unsigned DOpc = DI->getOpcode();

1548 switch (DOpc) {

1549 case TargetOpcode::COPY:

1550 case Hexagon::A2_tfrsi:

1551 case Hexagon::A2_tfrpi:

1552 case Hexagon::CONST32:

1553 case Hexagon::CONST64:

1554

1555

1556

1557 if (!checkForImmediate(DI->getOperand(1), TV))

1558 return false;

1559 break;

1560 case Hexagon::A2_combineii:

1561 case Hexagon::A4_combineir:

1562 case Hexagon::A4_combineii:

1563 case Hexagon::A4_combineri:

1564 case Hexagon::A2_combinew: {

1565 const MachineOperand &S1 = DI->getOperand(1);

1566 const MachineOperand &S2 = DI->getOperand(2);

1567 int64_t V1, V2;

1568 if (!checkForImmediate(S1, V1) || !checkForImmediate(S2, V2))

1569 return false;

1570 TV = V2 | (static_cast<uint64_t>(V1) << 32);

1571 break;

1572 }

1573 case TargetOpcode::REG_SEQUENCE: {

1574 const MachineOperand &S1 = DI->getOperand(1);

1575 const MachineOperand &S3 = DI->getOperand(3);

1576 int64_t V1, V3;

1577 if (!checkForImmediate(S1, V1) || !checkForImmediate(S3, V3))

1578 return false;

1581 if (Sub2 == Hexagon::isub_lo && Sub4 == Hexagon::isub_hi)

1582 TV = V1 | (V3 << 32);

1583 else if (Sub2 == Hexagon::isub_hi && Sub4 == Hexagon::isub_lo)

1584 TV = V3 | (V1 << 32);

1585 else

1587 break;

1588 }

1589

1590 default:

1591 return false;

1592 }

1593

1594

1595

1597 case Hexagon::isub_lo:

1598 Val = TV & 0xFFFFFFFFULL;

1599 break;

1600 case Hexagon::isub_hi:

1601 Val = (TV >> 32) & 0xFFFFFFFFULL;

1602 break;

1603 default:

1604 Val = TV;

1605 break;

1606 }

1607 return true;

1608}

1609

1610void HexagonHardwareLoops::setImmediate(MachineOperand &MO, int64_t Val) {

1611 if (MO.isImm()) {

1613 return;

1614 }

1615

1618 MachineInstr *DI = MRI->getVRegDef(R);

1619

1620 const TargetRegisterClass *RC = MRI->getRegClass(R);

1621 Register NewR = MRI->createVirtualRegister(RC);

1622 MachineBasicBlock &B = *DI->getParent();

1626}

1627

1628bool HexagonHardwareLoops::fixupInductionVariable(MachineLoop *L) {

1629 MachineBasicBlock *Header = L->getHeader();

1630 MachineBasicBlock *Latch = L->getLoopLatch();

1631 MachineBasicBlock *ExitingBlock = L->findLoopControlBlock();

1632

1633 if (!(Header && Latch && ExitingBlock))

1634 return false;

1635

1636

1637

1638 using RegisterBump = std::pair<Register, int64_t>;

1639 using RegisterInduction = std::pair<Register, RegisterBump>;

1640 using RegisterInductionSet = std::set;

1641

1642

1643 RegisterInductionSet IndRegs;

1644

1645

1646

1647

1649

1650 for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();

1651 I != E && I->isPHI(); ++I) {

1652 MachineInstr *Phi = &*I;

1653

1654

1655 for (unsigned i = 1, n = Phi->getNumOperands(); i < n; i += 2) {

1656 if (Phi->getOperand(i+1).getMBB() != Latch)

1657 continue;

1658

1659 Register PhiReg = Phi->getOperand(i).getReg();

1660 MachineInstr *DI = MRI->getVRegDef(PhiReg);

1661

1663

1664

1666 MachineOperand &Opnd2 = DI->getOperand(2);

1667 int64_t V;

1668 if (MRI->getVRegDef(IndReg) == Phi && checkForImmediate(Opnd2, V)) {

1670 IndRegs.insert(std::make_pair(UpdReg, std::make_pair(IndReg, V)));

1671 }

1672 }

1673 }

1674 }

1675

1676 if (IndRegs.empty())

1677 return false;

1678

1679 MachineBasicBlock *TB = nullptr, *FB = nullptr;

1681

1683 if (NotAnalyzed || Cond.empty())

1684 return false;

1685

1686 if (ExitingBlock != Latch && (TB == Latch || FB == Latch)) {

1687 MachineBasicBlock *LTB = nullptr, *LFB = nullptr;

1689 bool NotAnalyzed = TII->analyzeBranch(*Latch, LTB, LFB, LCond, false);

1690 if (NotAnalyzed)

1691 return false;

1692

1693

1694

1695 if (TB == Latch)

1696 TB = (LTB == Header) ? LTB : LFB;

1697 else

1698 FB = (LTB == Header) ? LTB : LFB;

1699 }

1700 if (TB != Header) {

1701 if (FB != Header) {

1702

1703 return false;

1704 }

1705

1706

1707

1708

1709

1710

1712 return false;

1713 }

1714

1715

1716

1717

1718

1719

1720 unsigned CSz = Cond.size();

1721 if (CSz != 1 && CSz != 2)

1722 return false;

1723

1725 return false;

1726

1728 MachineInstr *PredDef = MRI->getVRegDef(P);

1729

1731 return false;

1732

1733 SmallSet<Register,2> CmpRegs;

1734 MachineOperand *CmpImmOp = nullptr;

1735

1736

1737

1738

1739

1740 for (MachineOperand &MO : PredDef->operands()) {

1741 if (MO.isReg()) {

1742

1743

1745 continue;

1746 if (MO.isUse()) {

1747 if (!isImmediate(MO)) {

1749 continue;

1750 }

1751

1752 if (CmpImmOp)

1753 return false;

1754 CmpImmOp = &MO;

1755 }

1756 } else if (MO.isImm()) {

1757 if (CmpImmOp)

1758 return false;

1759 CmpImmOp = &MO;

1760 }

1761 }

1762

1763 if (CmpRegs.empty())

1764 return false;

1765

1766

1767 for (RegisterInductionSet::iterator I = IndRegs.begin(), E = IndRegs.end();

1768 I != E; ++I) {

1769

1770

1771

1772 if (CmpRegs.count(I->first))

1773 return true;

1774

1775

1776

1777

1778 const RegisterBump &RB = I->second;

1779 if (CmpRegs.count(RB.first)) {

1780 if (!CmpImmOp) {

1781

1782

1783 MachineInstr *IndI = nullptr;

1784 MachineInstr *nonIndI = nullptr;

1785 MachineOperand *IndMO = nullptr;

1786 MachineOperand *nonIndMO = nullptr;

1787

1788 for (unsigned i = 1, n = PredDef->getNumOperands(); i < n; ++i) {

1789 MachineOperand &MO = PredDef->getOperand(i);

1790 if (MO.isReg() && MO.getReg() == RB.first) {

1792 << ") = " << *(MRI->getVRegDef(I->first)));

1793 if (IndI)

1794 return false;

1795

1796 IndI = MRI->getVRegDef(I->first);

1797 IndMO = &MO;

1798 } else if (MO.isReg()) {

1800 << ") = " << *(MRI->getVRegDef(MO.getReg())));

1801 if (nonIndI)

1802 return false;

1803

1804 nonIndI = MRI->getVRegDef(MO.getReg());

1805 nonIndMO = &MO;

1806 }

1807 }

1808 if (IndI && nonIndI &&

1809 nonIndI->getOpcode() == Hexagon::A2_addi &&

1812 bool Order = orderBumpCompare(IndI, PredDef);

1813 if (Order) {

1814 IndMO->setReg(I->first);

1816 return true;

1817 }

1818 }

1819 return false;

1820 }

1821

1822

1823

1824 Comparison::Kind Cmp =

1825 getComparisonKind(PredDef->getOpcode(), nullptr, nullptr, 0);

1826 if (!Cmp || Comparison::isUnsigned(Cmp))

1827 return false;

1828

1829

1830

1831

1832 int64_t CmpImm = getImmediate(*CmpImmOp);

1833 int64_t V = RB.second;

1834

1835 if (((V > 0) && (CmpImm > INT64_MAX - V)) ||

1836 ((V < 0) && (CmpImm < INT64_MIN - V)))

1837 return false;

1838 CmpImm += V;

1839

1840

1841

1842 if (CmpImmOp->isImm() && TII ->isExtendable(*PredDef) &&

1843 TII ->isValidOffset(PredDef->getOpcode(), CmpImm, TRI, false))

1844 return false;

1845

1846

1847

1848 MachineInstr *BumpI = MRI->getVRegDef(I->first);

1849 bool Order = orderBumpCompare(BumpI, PredDef);

1850 if (!Order)

1851 return false;

1852

1853

1854 setImmediate(*CmpImmOp, CmpImm);

1855 for (MachineOperand &MO : PredDef->operands()) {

1856 if (MO.isReg() && MO.getReg() == RB.first) {

1858 return true;

1859 }

1860 }

1861 }

1862 }

1863

1864 return false;

1865}

1866

1867

1868MachineBasicBlock *HexagonHardwareLoops::createPreheaderForLoop(

1869 MachineLoop *L) {

1870 if (MachineBasicBlock *TmpPH = MLI->findLoopPreheader(L, SpecPreheader))

1871 return TmpPH;

1873 return nullptr;

1874

1875 MachineBasicBlock *Header = L->getHeader();

1876 MachineBasicBlock *Latch = L->getLoopLatch();

1877 MachineBasicBlock *ExitingBlock = L->findLoopControlBlock();

1878 MachineFunction *MF = Header->getParent();

1880

1881#ifndef NDEBUG

1883 return nullptr;

1884#endif

1885

1886 if (!Latch || !ExitingBlock || Header->hasAddressTaken())

1887 return nullptr;

1888

1890

1891

1892

1893 using MBBVector = std::vector<MachineBasicBlock *>;

1894

1895 MBBVector Preds(Header->pred_begin(), Header->pred_end());

1897 MachineBasicBlock *TB = nullptr, *FB = nullptr;

1898

1900 return nullptr;

1901

1902 for (MachineBasicBlock *PB : Preds) {

1904 if (NotAnalyzed)

1905 return nullptr;

1906 }

1907

1909 MF->insert(Header->getIterator(), NewPH);

1910

1911 if (Header->pred_size() > 2) {

1912

1913

1914

1915

1916

1917 for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();

1918 I != E && I->isPHI(); ++I) {

1919 MachineInstr *PN = &*I;

1920

1921 const MCInstrDesc &PD = TII->get(TargetOpcode::PHI);

1922 MachineInstr *NewPN = MF->CreateMachineInstr(PD, DL);

1923 NewPH->insert(NewPH->end(), NewPN);

1924

1926 const TargetRegisterClass *RC = MRI->getRegClass(PR);

1927 Register NewPR = MRI->createVirtualRegister(RC);

1929

1930

1931

1932 for (unsigned i = 1, n = PN->getNumOperands(); i < n; i += 2) {

1936 if (PredB == Latch)

1937 continue;

1938

1943 }

1944

1945

1946

1947 for (int i = PN->getNumOperands()-2; i > 0; i -= 2) {

1949 if (PredB != Latch) {

1952 }

1953 }

1956 }

1957 } else {

1958 assert(Header->pred_size() == 2);

1959

1960

1961

1962

1963

1964

1965 for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();

1966 I != E && I->isPHI(); ++I) {

1967 MachineInstr *PN = &*I;

1968 for (unsigned i = 1, n = PN->getNumOperands(); i < n; i += 2) {

1969 MachineOperand &MO = PN->getOperand(i+1);

1970 if (MO.getMBB() != Latch)

1972 }

1973 }

1974 }

1975

1976

1977

1978

1981

1982 TB = FB = nullptr;

1983

1984 for (MachineBasicBlock *PB : Preds) {

1985 if (PB != Latch) {

1988 (void)NotAnalyzed;

1989 assert (!NotAnalyzed && "Should be analyzable!");

1990 if (TB != Header && (Tmp2.empty() || FB != Header))

1992 PB->ReplaceUsesOfBlockWith(Header, NewPH);

1993 }

1994 }

1995

1996

1997

1998 TB = FB = nullptr;

1999 bool LatchNotAnalyzed = TII->analyzeBranch(*Latch, TB, FB, Tmp2, false);

2000 (void)LatchNotAnalyzed;

2001 assert (!LatchNotAnalyzed && "Should be analyzable!");

2002 if (!TB && !FB)

2004

2005

2008

2009 MachineLoop *ParentLoop = L->getParentLoop();

2010 if (ParentLoop)

2012

2013

2014 if (MDT) {

2017 MDT->addNewBlock(NewPH, DHN->getBlock());

2019 }

2020 }

2021 }

2022

2023 return NewPH;

2024}

unsigned const MachineRegisterInfo * MRI

MachineInstrBuilder & UseMI

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

const TargetInstrInfo & TII

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")

static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")

static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")

static bool isSigned(unsigned int Opcode)

static cl::opt< bool > HWCreatePreheader("hexagon-hwloop-preheader", cl::Hidden, cl::init(true), cl::desc("Add a preheader to a hardware loop if one doesn't exist"))

static cl::opt< bool > SpecPreheader("hwloop-spec-preheader", cl::Hidden, cl::desc("Allow speculation of preheader " "instructions"))

static cl::opt< std::string > PHFn("hexagon-hwloop-phfn", cl::Hidden, cl::init(""))

static cl::opt< int > HWLoopLimit("hexagon-max-hwloop", cl::Hidden, cl::init(-1))

Promote Memory to Register

static MCRegister getReg(const MCDisassembler *D, unsigned RC, unsigned RegNo)

static bool isReg(const MCInst &MI, unsigned OpNo)

PassBuilder PB(Machine, PassOpts->PTO, std::nullopt, &PIC)

#define INITIALIZE_PASS_DEPENDENCY(depName)

#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)

#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)

SmallVector< MachineBasicBlock *, 4 > MBBVector

const SmallVectorImpl< MachineOperand > MachineBasicBlock * TBB

const SmallVectorImpl< MachineOperand > & Cond

bool isDead(const MachineInstr &MI, const MachineRegisterInfo &MRI)

This file defines the SmallSet class.

This file defines the SmallVector class.

This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...

#define STATISTIC(VARNAME, DESC)

AnalysisUsage & addRequired()

DomTreeNodeBase * getIDom() const

void changeImmediateDominator(DomTreeNodeBase< NodeT > *N, DomTreeNodeBase< NodeT > *NewIDom)

changeImmediateDominator - This method is used to update the dominator tree information when a node's...

DomTreeNodeBase< NodeT > * addNewBlock(NodeT *BB, NodeT *DomBB)

Add a new node to the dominator tree information.

DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const

getNode - return the (Post)DominatorTree node for the specified basic block.

bool properlyDominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const

properlyDominates - Returns true iff A dominates B and A != B.

FunctionPass class - This class is used to implement most global optimizations.

const HexagonInstrInfo * getInstrInfo() const override

const HexagonRegisterInfo * getRegisterInfo() const override

void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)

This method is used by other analyses to update loop information.

BlockT * getLoopPreheader() const

If there is a preheader for this loop, return it.

bool isAdd() const

Return true if the instruction is an add instruction.

const MCInstrDesc & get(unsigned Opcode) const

Return the machine instruction descriptor that corresponds to the specified instruction opcode.

LLVM_ABI instr_iterator insert(instr_iterator I, MachineInstr *M)

Insert MI into the instruction list before I, possibly inside a bundle.

LLVM_ABI iterator getFirstTerminator()

Returns an iterator to the first terminator instruction of this basic block.

LLVM_ABI void addSuccessor(MachineBasicBlock *Succ, BranchProbability Prob=BranchProbability::getUnknown())

Add Succ as a successor of this MachineBasicBlock.

SmallVectorImpl< MachineBasicBlock * >::iterator pred_iterator

Instructions::iterator instr_iterator

pred_iterator pred_begin()

instr_iterator instr_end()

LLVM_ABI instr_iterator erase(instr_iterator I)

Remove an instruction from the instruction list and delete it.

void splice(iterator Where, MachineBasicBlock *Other, iterator From)

Take an instruction from MBB 'Other' at the position From, and insert it into this MBB right before '...

MachineInstrBundleIterator< MachineInstr > iterator

void setMachineBlockAddressTaken()

Set this block to indicate that its address is used as something other than the target of a terminato...

Analysis pass which computes a MachineDominatorTree.

DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...

bool dominates(const MachineInstr *A, const MachineInstr *B) const

MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...

void getAnalysisUsage(AnalysisUsage &AU) const override

getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.

const TargetSubtargetInfo & getSubtarget() const

getSubtarget - Return the subtarget for which this machine code is being compiled.

StringRef getName() const

getName - Return the name of the corresponding LLVM function.

MachineRegisterInfo & getRegInfo()

getRegInfo - Return information about the registers currently in use.

Function & getFunction()

Return the LLVM function that this machine code represents.

MachineBasicBlock * CreateMachineBasicBlock(const BasicBlock *BB=nullptr, std::optional< UniqueBBID > BBID=std::nullopt)

CreateMachineInstr - Allocate a new MachineInstr.

void insert(iterator MBBI, MachineBasicBlock *MBB)

const MachineInstrBuilder & addImm(int64_t Val) const

Add a new immediate operand.

const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const

Add a new virtual register operand.

const MachineInstrBuilder & addMBB(MachineBasicBlock *MBB, unsigned TargetFlags=0) const

unsigned getOpcode() const

Returns the opcode of this MachineInstr.

const MachineBasicBlock * getParent() const

unsigned getNumOperands() const

Retuns the total number of operands.

LLVM_ABI void addOperand(MachineFunction &MF, const MachineOperand &Op)

Add the specified operand to the instruction.

bool isCompare(QueryType Type=IgnoreBundle) const

Return true if this instruction is a comparison.

const MCInstrDesc & getDesc() const

Returns the target instruction descriptor of this MachineInstr.

const DebugLoc & getDebugLoc() const

Returns the debug location id of this MachineInstr.

LLVM_ABI void removeOperand(unsigned OpNo)

Erase an operand from an instruction, leaving it with one fewer operand than it started with.

const MachineOperand & getOperand(unsigned i) const

void setSubReg(unsigned subReg)

unsigned getSubReg() const

void setImm(int64_t immVal)

bool isReg() const

isReg - Tests if this is a MO_Register operand.

MachineBasicBlock * getMBB() const

LLVM_ABI void setReg(Register Reg)

Change the register this operand corresponds to.

bool isImm() const

isImm - Tests if this is a MO_Immediate operand.

MachineInstr * getParent()

getParent - Return the instruction that this operand belongs to.

void setMBB(MachineBasicBlock *MBB)

getReg - Returns the register number.

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)

static MachineOperand CreateMBB(MachineBasicBlock *MBB, unsigned TargetFlags=0)

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

defusechain_instr_iterator< true, false, true, true > use_instr_nodbg_iterator

use_instr_nodbg_iterator/use_instr_nodbg_begin/use_instr_nodbg_end - Walk all uses of the specified r...

defusechain_iterator< true, false, true, true, false > use_nodbg_iterator

use_nodbg_iterator/use_nodbg_begin/use_nodbg_end - Walk all uses of the specified register,...

constexpr bool isVirtual() const

Return true if the specified register number is in the virtual register namespace.

size_type count(const T &V) const

count - Return 1 if the element is in the set, 0 otherwise.

std::pair< const_iterator, bool > insert(const T &V)

insert - Insert an element into the set if it isn't already there.

void push_back(const T &Elt)

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....

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.

virtual bool analyzeCompare(const MachineInstr &MI, Register &SrcReg, Register &SrcReg2, int64_t &Mask, int64_t &Value) const

For a comparison instruction, return the source registers in SrcReg and SrcReg2 if having two registe...

self_iterator getIterator()

#define llvm_unreachable(msg)

Marks that the current location is not supposed to be reachable.

constexpr std::underlying_type_t< E > Mask()

Get a bitmask with 1s in all places up to the high-order bit of E's largest value.

unsigned ID

LLVM IR allows to use arbitrary numbers as calling convention identifiers.

@ TB

TB - TwoByte - Set if this instruction has a two byte opcode, which starts with a 0x0F byte before th...

@ PD

PD - Prefix code for packed double precision vector floating point operations performed in the SSE re...

initializer< Ty > init(const Ty &Val)

NodeAddr< DefNode * > Def

NodeAddr< PhiNode * > Phi

NodeAddr< UseNode * > Use

This is an optimization pass for GlobalISel generic memory operations.

Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr, unsigned DynamicVGPRBlockSize=0)

MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)

Builder interface. Specify how to create the initial instruction itself.

iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)

Make a range that does early increment to allow mutation of the underlying range without disrupting i...

constexpr bool isPowerOf2_64(uint64_t Value)

Return true if the argument is a power of two > 0 (64 bit edition.)

unsigned Log2_32(uint32_t Value)

Return the floor log base 2 of the specified value, -1 if the value is zero.

MachineInstr * getImm(const MachineOperand &MO, const MachineRegisterInfo *MRI)

LLVM_ABI raw_ostream & dbgs()

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

FunctionPass * createHexagonHardwareLoops()

Definition HexagonHardwareLoops.cpp:369

FunctionAddr VTableAddr Count

class LLVM_GSL_OWNER SmallVector

Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...

DomTreeNodeBase< MachineBasicBlock > MachineDomTreeNode

@ Sub

Subtraction of integers.

ArrayRef(const T &OneElt) -> ArrayRef< T >

bool is_contained(R &&Range, const E &Element)

Returns true if Element is found in Range.

LLVM_ABI Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)

Prints virtual and physical registers with or without a TRI instance.

LLVM_ABI Printable printMBBReference(const MachineBasicBlock &MBB)

Prints a machine basic block reference.

void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)

Implement std::swap in terms of BitVector swap.