PPCLoopInstrFormPrep.cpp Source File (original) (raw)

94#include "llvm/IR/IntrinsicsPowerPC.h"

107#include

108#include

109#include

110

111#define DEBUG_TYPE "ppc-loop-instr-form-prep"

112

113using namespace llvm;

114

117 cl::desc("Potential common base number threshold per function "

118 "for PPC loop prep"));

119

122 cl::desc("prefer update form when ds form is also a update form"));

123

126 cl::desc("prepare update form when the load/store increment is a loop "

127 "invariant non-const value."));

128

131 cl::desc("Enable chain commoning in PPC loop prepare pass."));

132

133

134

135

138 cl::desc("Potential PHI threshold per loop for PPC loop prep of update "

139 "form"));

140

143 cl::desc("Potential PHI threshold per loop for PPC loop prep of DS form"));

144

147 cl::desc("Potential PHI threshold per loop for PPC loop prep of DQ form"));

148

149

150

151

152

153

154

155

158 cl::desc("Bucket number per loop for PPC loop chain common"));

159

160

161

162

163

166 cl::desc("Minimal common base load/store instructions triggering DS/DQ form "

167 "preparation"));

168

171 cl::desc("Minimal common base load/store instructions triggering chain "

172 "commoning preparation. Must be not smaller than 4"));

173

174 STATISTIC(PHINodeAlreadyExistsUpdate, "PHI node already in pre-increment form");

175 STATISTIC(PHINodeAlreadyExistsDS, "PHI node already in DS form");

176 STATISTIC(PHINodeAlreadyExistsDQ, "PHI node already in DQ form");

177 STATISTIC(DSFormChainRewritten, "Num of DS form chain rewritten");

178 STATISTIC(DQFormChainRewritten, "Num of DQ form chain rewritten");

179 STATISTIC(UpdFormChainRewritten, "Num of update form chain rewritten");

180 STATISTIC(ChainCommoningRewritten, "Num of commoning chains");

181

182namespace {

183 struct BucketElement {

185 BucketElement(Instruction *I) : Offset(nullptr), Instr(I) {}

186

187 const SCEV *Offset;

189 };

190

191 struct Bucket {

192 Bucket(const SCEV *B, Instruction *I)

193 : BaseSCEV(B), Elements(1, BucketElement(I)) {

194 ChainSize = 0;

195 }

196

197

198 const SCEV *BaseSCEV;

199

200

201

202

204

205

206 unsigned ChainSize;

207

208

210 };

211

212

213

214

215

216 enum PrepForm { UpdateForm = 1, DSForm = 4, DQForm = 16, ChainCommoning };

217

218 class PPCLoopInstrFormPrep : public FunctionPass {

219 public:

220 static char ID;

221

222 PPCLoopInstrFormPrep(PPCTargetMachine &TM) : FunctionPass(ID), TM(&TM) {}

223

224 void getAnalysisUsage(AnalysisUsage &AU) const override {

228 AU.addRequired();

229 }

230

232

233 private:

234 PPCTargetMachine *TM = nullptr;

235 const PPCSubtarget *ST;

236 DominatorTree *DT;

237 LoopInfo *LI;

238 ScalarEvolution *SE;

239 bool PreserveLCSSA;

240 bool HasCandidateForPrepare;

241

242

243

244

245

246 unsigned SuccPrepCount;

247

248 bool runOnLoop(Loop *L);

249

250

251 bool alreadyPrepared(Loop *L, Instruction *MemI,

252 const SCEV *BasePtrStartSCEV,

253 const SCEV *BasePtrIncSCEV, PrepForm Form);

254

255

256 Value *getNodeForInc(Loop *L, Instruction *MemI,

257 const SCEV *BasePtrIncSCEV);

258

259

261

262

263 bool prepareBasesForCommoningChains(Bucket &BucketChain);

264

265

266 bool rewriteLoadStoresForCommoningChains(

267 Loop *L, Bucket &Bucket, SmallPtrSet<BasicBlock *, 16> &BBChanged);

268

269

270

272 Loop *L,

273 std::function<bool(const Instruction *, Value *, const Type *)>

274 isValidCandidate,

275 std::function<bool(const SCEV *)> isValidDiff,

276 unsigned MaxCandidateNum);

277

278

279

280 void addOneCandidate(Instruction *MemI, const SCEV *LSCEV,

282 std::function<bool(const SCEV *)> isValidDiff,

283 unsigned MaxCandidateNum);

284

285

287

288

289

291

292

293

294

295

296

297

298 bool prepareBaseForDispFormChain(Bucket &BucketChain, PrepForm Form);

299

300

301

302

303

304

305 bool prepareBaseForUpdateFormChain(Bucket &BucketChain);

306

307

308

309 bool rewriteLoadStores(Loop *L, Bucket &BucketChain,

310 SmallPtrSet<BasicBlock *, 16> &BBChanged,

311 PrepForm Form);

312

313

314 std::pair<Instruction *, Instruction *>

315 rewriteForBase(Loop *L, const SCEVAddRecExpr *BasePtrSCEV,

316 Instruction *BaseMemI, bool CanPreInc, PrepForm Form,

317 SCEVExpander &SCEVE, SmallPtrSet<Value *, 16> &DeletedPtrs);

318

319

320

322 rewriteForBucketElement(std::pair<Instruction *, Instruction *> Base,

323 const BucketElement &Element, Value *OffToBase,

324 SmallPtrSet<Value *, 16> &DeletedPtrs);

325 };

326

327}

328

329char PPCLoopInstrFormPrep::ID = 0;

330static const char *name = "Prepare loop for ppc preferred instruction forms";

335

340

342 return new PPCLoopInstrFormPrep(TM);

343}

344

346 Value *StrippedBasePtr = BasePtr;

348 StrippedBasePtr = BC->getOperand(0);

350 return GEP->isInBounds();

351

352 return false;

353}

354

356 assert(I && "Invalid paramater!");

357 if (I->hasName())

358 return (I->getName() + Suffix).str();

359 else

360 return "";

361}

362

364 Type **PtrElementType = nullptr) {

365

366 Value *PtrValue = nullptr;

367 Type *PointerElementType = nullptr;

368

370 PtrValue = LMemI->getPointerOperand();

371 PointerElementType = LMemI->getType();

373 PtrValue = SMemI->getPointerOperand();

374 PointerElementType = SMemI->getValueOperand()->getType();

377 if (IMemI->getIntrinsicID() == Intrinsic::prefetch ||

378 IMemI->getIntrinsicID() == Intrinsic::ppc_vsx_lxvp) {

379 PtrValue = IMemI->getArgOperand(0);

380 } else if (IMemI->getIntrinsicID() == Intrinsic::ppc_vsx_stxvp) {

381 PtrValue = IMemI->getArgOperand(1);

382 }

383 }

384

385 if (PtrElementType)

386 *PtrElementType = PointerElementType;

387

388 return PtrValue;

389}

390

391bool PPCLoopInstrFormPrep::runOnFunction(Function &F) {

392 if (skipFunction(F))

393 return false;

394

395 LI = &getAnalysis().getLoopInfo();

396 SE = &getAnalysis().getSE();

397 auto *DTWP = getAnalysisIfAvailable();

398 DT = DTWP ? &DTWP->getDomTree() : nullptr;

399 PreserveLCSSA = mustPreserveAnalysisID(LCSSAID);

401 SuccPrepCount = 0;

402

403 bool MadeChange = false;

404

405 for (Loop *I : *LI)

407 MadeChange |= runOnLoop(L);

408

409 return MadeChange;

410}

411

412

413

414

415

416

417

418bool PPCLoopInstrFormPrep::prepareBasesForCommoningChains(Bucket &CBucket) {

419

420

421

422

423

424

425

426

427

428

429

430

431

432

433

435 "Thredhold can not be smaller than 4!\n");

437 return false;

438

439

440

441 const SCEV *FirstOffset = CBucket.Elements[1].Offset;

442

443

444

445

446 unsigned FirstOffsetReusedCount = 1;

447

448

449

450 unsigned FirstOffsetReusedCountInFirstChain = 1;

451

452 unsigned EleNum = CBucket.Elements.size();

453 bool SawChainSeparater = false;

454 for (unsigned j = 2; j != EleNum; ++j) {

455 if (SE->getMinusSCEV(CBucket.Elements[j].Offset,

456 CBucket.Elements[j - 1].Offset) == FirstOffset) {

457 if (!SawChainSeparater)

458 FirstOffsetReusedCountInFirstChain++;

459 FirstOffsetReusedCount++;

460 } else

461

462

463

464

465

466

467

468

469

470

471

472

473

474

475

476

477 SawChainSeparater = true;

478 }

479

480

481 if (FirstOffsetReusedCount == 1)

482 return false;

483

484 unsigned ChainNum =

485 FirstOffsetReusedCount / FirstOffsetReusedCountInFirstChain;

486

487

488

489 if (!SawChainSeparater)

490 ChainNum = (unsigned)sqrt((double)EleNum);

491

492 CBucket.ChainSize = (unsigned)(EleNum / ChainNum);

493

494

495

496 if (CBucket.ChainSize * ChainNum != EleNum)

497 return false;

498

499 if (SawChainSeparater) {

500

501 for (unsigned i = 1; i < CBucket.ChainSize; i++)

502 for (unsigned j = 1; j < ChainNum; j++)

503 if (CBucket.Elements[i].Offset !=

504 SE->getMinusSCEV(CBucket.Elements[i + j * CBucket.ChainSize].Offset,

505 CBucket.Elements[j * CBucket.ChainSize].Offset))

506 return false;

507 }

508

509 for (unsigned i = 0; i < ChainNum; i++)

510 CBucket.ChainBases.push_back(CBucket.Elements[i * CBucket.ChainSize]);

511

512 LLVM_DEBUG(dbgs() << "Bucket has " << ChainNum << " chains.\n");

513

514 return true;

515}

516

517bool PPCLoopInstrFormPrep::chainCommoning(Loop *L,

519 bool MadeChange = false;

520

521 if (Buckets.empty())

522 return MadeChange;

523

524 SmallPtrSet<BasicBlock *, 16> BBChanged;

525

526 for (auto &Bucket : Buckets) {

527 if (prepareBasesForCommoningChains(Bucket))

528 MadeChange |= rewriteLoadStoresForCommoningChains(L, Bucket, BBChanged);

529 }

530

531 if (MadeChange)

532 for (auto *BB : BBChanged)

534 return MadeChange;

535}

536

537bool PPCLoopInstrFormPrep::rewriteLoadStoresForCommoningChains(

538 Loop *L, Bucket &Bucket, SmallPtrSet<BasicBlock *, 16> &BBChanged) {

539 bool MadeChange = false;

540

541 assert(Bucket.Elements.size() ==

542 Bucket.ChainBases.size() * Bucket.ChainSize &&

543 "invalid bucket for chain commoning!\n");

544 SmallPtrSet<Value *, 16> DeletedPtrs;

545

547 BasicBlock *LoopPredecessor = L->getLoopPredecessor();

548

549 SCEVExpander SCEVE(*SE, Header->getDataLayout(),

550 "loopprepare-chaincommon");

551

552 for (unsigned ChainIdx = 0; ChainIdx < Bucket.ChainBases.size(); ++ChainIdx) {

553 unsigned BaseElemIdx = Bucket.ChainSize * ChainIdx;

554 const SCEV *BaseSCEV =

555 ChainIdx ? SE->getAddExpr(Bucket.BaseSCEV,

556 Bucket.Elements[BaseElemIdx].Offset)

557 : Bucket.BaseSCEV;

559

560

561 if (!SCEVE.isSafeToExpand(BasePtrSCEV->getStart()))

562 return MadeChange;

563

565 "Invalid SCEV type for the base ptr for a candidate chain!\n");

566

567 std::pair<Instruction *, Instruction *> Base = rewriteForBase(

568 L, BasePtrSCEV, Bucket.Elements[BaseElemIdx].Instr,

569 false , ChainCommoning, SCEVE, DeletedPtrs);

570

571 if ( Base .first || Base .second)

572 return MadeChange;

573

574

575

576 SmallPtrSet<Value *, 16> NewPtrs;

578

579 for (unsigned Idx = BaseElemIdx + 1; Idx < BaseElemIdx + Bucket.ChainSize;

580 ++Idx) {

581 BucketElement &I = Bucket.Elements[Idx];

583 assert(Ptr && "No pointer operand");

584 if (NewPtrs.count(Ptr))

585 continue;

586

587 const SCEV *OffsetSCEV =

588 BaseElemIdx ? SE->getMinusSCEV(Bucket.Elements[Idx].Offset,

589 Bucket.Elements[BaseElemIdx].Offset)

590 : Bucket.Elements[Idx].Offset;

591

592

593

594 if (!BaseElemIdx)

595 if (!SCEVE.isSafeToExpand(OffsetSCEV))

596 return false;

597

598 Value *OffsetValue = SCEVE.expandCodeFor(

600

601 Instruction *NewPtr = rewriteForBucketElement(Base, Bucket.Elements[Idx],

602 OffsetValue, DeletedPtrs);

603

604 assert(NewPtr && "Wrong rewrite!\n");

605 NewPtrs.insert(NewPtr);

606 }

607

608 ++ChainCommoningRewritten;

609 }

610

611

612

613 SCEVE.clear();

614

615 for (auto *Ptr : DeletedPtrs) {

617 BBChanged.insert(IDel->getParent());

619 }

620

621 MadeChange = true;

622 return MadeChange;

623}

624

625

626

627

628

629

630

631

632

633

634

635

636

637std::pair<Instruction *, Instruction *>

638PPCLoopInstrFormPrep::rewriteForBase(Loop *L, const SCEVAddRecExpr *BasePtrSCEV,

639 Instruction *BaseMemI, bool CanPreInc,

640 PrepForm Form, SCEVExpander &SCEVE,

641 SmallPtrSet<Value *, 16> &DeletedPtrs) {

642

643 LLVM_DEBUG(dbgs() << "PIP: Transforming: " << *BasePtrSCEV << "\n");

644

645 assert(BasePtrSCEV->getLoop() == L && "AddRec for the wrong loop?");

646

648 assert(BasePtr && "No pointer operand");

649

650 Type *I8Ty = Type::getInt8Ty(BaseMemI->getParent()->getContext());

651 Type *I8PtrTy =

652 PointerType::get(BaseMemI->getParent()->getContext(),

653 BasePtr->getType()->getPointerAddressSpace());

654

655 bool IsConstantInc = false;

656 const SCEV *BasePtrIncSCEV = BasePtrSCEV->getStepRecurrence(*SE);

657 Value *IncNode = getNodeForInc(L, BaseMemI, BasePtrIncSCEV);

658

659 const SCEVConstant *BasePtrIncConstantSCEV =

661 if (BasePtrIncConstantSCEV)

662 IsConstantInc = true;

663

664

665 if (!IncNode) {

666 LLVM_DEBUG(dbgs() << "Loop Increasement can not be represented!\n");

667 return std::make_pair(nullptr, nullptr);

668 }

669

673 << "Update form prepare for non-const increment is not enabled!\n");

674 return std::make_pair(nullptr, nullptr);

675 }

676

677 const SCEV *BasePtrStartSCEV = nullptr;

678 if (CanPreInc) {

680 "Increment is not loop invariant!\n");

682 IsConstantInc ? BasePtrIncConstantSCEV

683 : BasePtrIncSCEV);

684 } else

685 BasePtrStartSCEV = BasePtrSCEV->getStart();

686

687 if (alreadyPrepared(L, BaseMemI, BasePtrStartSCEV, BasePtrIncSCEV, Form)) {

688 LLVM_DEBUG(dbgs() << "Instruction form is already prepared!\n");

689 return std::make_pair(nullptr, nullptr);

690 }

691

692 LLVM_DEBUG(dbgs() << "PIP: New start is: " << *BasePtrStartSCEV << "\n");

693

695 unsigned HeaderLoopPredCount = pred_size(Header);

696 BasicBlock *LoopPredecessor = L->getLoopPredecessor();

697

698 PHINode *NewPHI = PHINode::Create(I8PtrTy, HeaderLoopPredCount,

700 NewPHI->insertBefore(Header->getFirstNonPHIIt());

701

704

705

706

708 if (PI != LoopPredecessor)

709 continue;

710

711 NewPHI->addIncoming(BasePtrStart, LoopPredecessor);

712 }

713

716 if (CanPreInc) {

720 InsPoint);

723 if (PI == LoopPredecessor)

724 continue;

725

727 }

729 NewBasePtr =

730 new BitCastInst(PtrInc, BasePtr->getType(),

732 else

733 NewBasePtr = PtrInc;

734 } else {

735

736

738 if (PI == LoopPredecessor)

739 continue;

740

741

742

747 InsPoint);

749

751 }

752 PtrInc = NewPHI;

754 NewBasePtr = new BitCastInst(NewPHI, BasePtr->getType(),

756 Header->getFirstInsertionPt());

757 else

758 NewBasePtr = NewPHI;

759 }

760

761 BasePtr->replaceAllUsesWith(NewBasePtr);

762

763 DeletedPtrs.insert(BasePtr);

764

765 return std::make_pair(NewBasePtr, PtrInc);

766}

767

768Instruction *PPCLoopInstrFormPrep::rewriteForBucketElement(

769 std::pair<Instruction *, Instruction *> Base, const BucketElement &Element,

770 Value *OffToBase, SmallPtrSet<Value *, 16> &DeletedPtrs) {

773 assert((NewBasePtr && PtrInc) && "base does not exist!\n");

774

775 Type *I8Ty = Type::getInt8Ty(PtrInc->getParent()->getContext());

776

778 assert(Ptr && "No pointer operand");

779

781 if (!Element.Offset ||

784 RealNewPtr = NewBasePtr;

785 } else {

786 std::optionalBasicBlock::iterator PtrIP = std::nullopt;

788 PtrIP = I->getIterator();

789

792 PtrIP = std::nullopt;

794 PtrIP = (*PtrIP)->getParent()->getFirstInsertionPt();

795 else if (!PtrIP)

797

798 assert(OffToBase && "There should be an offset for non base element!\n");

800 I8Ty, PtrInc, OffToBase,

802 if (PtrIP)

803 NewPtr->insertBefore(*(*PtrIP)->getParent(), *PtrIP);

804 else

807 RealNewPtr = NewPtr;

808 }

809

812 ReplNewPtr = new BitCastInst(RealNewPtr, Ptr->getType(),

815 } else

816 ReplNewPtr = RealNewPtr;

817

819 DeletedPtrs.insert(Ptr);

820

821 return ReplNewPtr;

822}

823

824void PPCLoopInstrFormPrep::addOneCandidate(

826 std::function<bool(const SCEV *)> isValidDiff, unsigned MaxCandidateNum) {

828 "Candidate should be a memory instruction.");

829 assert(LSCEV && "Invalid SCEV for Ptr value.");

830

831 bool FoundBucket = false;

832 for (auto &B : Buckets) {

835 continue;

836 const SCEV *Diff = SE->getMinusSCEV(LSCEV, B.BaseSCEV);

837 if (isValidDiff(Diff)) {

838 B.Elements.push_back(BucketElement(Diff, MemI));

839 FoundBucket = true;

840 break;

841 }

842 }

843

844 if (!FoundBucket) {

845 if (Buckets.size() == MaxCandidateNum) {

846 LLVM_DEBUG(dbgs() << "Can not prepare more chains, reach maximum limit "

847 << MaxCandidateNum << "\n");

848 return;

849 }

850 Buckets.push_back(Bucket(LSCEV, MemI));

851 }

852}

853

855 Loop *L,

856 std::function<bool(const Instruction *, Value *, const Type *)>

857 isValidCandidate,

858 std::function<bool(const SCEV *)> isValidDiff, unsigned MaxCandidateNum) {

860

861 for (const auto &BB : L->blocks())

862 for (auto &J : *BB) {

863 Value *PtrValue = nullptr;

864 Type *PointerElementType = nullptr;

866

867 if (!PtrValue)

868 continue;

869

871 continue;

872

873 if (L->isLoopInvariant(PtrValue))

874 continue;

875

878 if (!LARSCEV || LARSCEV->getLoop() != L)

879 continue;

880

881

882 HasCandidateForPrepare = true;

883

884 if (isValidCandidate(&J, PtrValue, PointerElementType))

885 addOneCandidate(&J, LSCEV, Buckets, isValidDiff, MaxCandidateNum);

886 }

887 return Buckets;

888}

889

890bool PPCLoopInstrFormPrep::prepareBaseForDispFormChain(Bucket &BucketChain,

891 PrepForm Form) {

892

893

894

895

896

897

898 DenseMap<unsigned, std::pair<unsigned, unsigned>> RemainderOffsetInfo;

899

900 for (unsigned j = 0, je = BucketChain.Elements.size(); j != je; ++j) {

901 if (!BucketChain.Elements[j].Offset)

902 RemainderOffsetInfo[0] = std::make_pair(0, 1);

903 else {

904 unsigned Remainder = cast(BucketChain.Elements[j].Offset)

905 ->getAPInt()

906 .urem(Form);

907 if (!RemainderOffsetInfo.contains(Remainder))

908 RemainderOffsetInfo[Remainder] = std::make_pair(j, 1);

909 else

910 RemainderOffsetInfo[Remainder].second++;

911 }

912 }

913

914

915

916

917

918

919

920

921

922

923

924

925

926

927

928 unsigned MaxCountRemainder = 0;

929 for (unsigned j = 0; j < (unsigned)Form; j++)

930 if (auto It = RemainderOffsetInfo.find(j);

931 It != RemainderOffsetInfo.end() &&

932 It->second.second > RemainderOffsetInfo[MaxCountRemainder].second)

933 MaxCountRemainder = j;

934

935

937 return false;

938

939

940

941 if (MaxCountRemainder == 0)

942 return true;

943

944

946 BucketChain.Elements[RemainderOffsetInfo[MaxCountRemainder].first].Offset;

947 BucketChain.BaseSCEV = SE->getAddExpr(BucketChain.BaseSCEV, Offset);

948 for (auto &E : BucketChain.Elements) {

949 if (E.Offset)

951 else

953 }

954

955 std::swap(BucketChain.Elements[RemainderOffsetInfo[MaxCountRemainder].first],

956 BucketChain.Elements[0]);

957 return true;

958}

959

960

961

962

963

964

965

966bool PPCLoopInstrFormPrep::prepareBaseForUpdateFormChain(Bucket &BucketChain) {

967

968

969

970

971

972

973

974

975

976 for (int j = 0, je = BucketChain.Elements.size(); j != je; ++j) {

978 if (II->getIntrinsicID() == Intrinsic::prefetch)

979 continue;

980

981

982 if (j == 0)

983 break;

984

985

986

987 if (!BucketChain.Elements[j].Offset ||

989 break;

990

991 const SCEV *Offset = BucketChain.Elements[j].Offset;

992 BucketChain.BaseSCEV = SE->getAddExpr(BucketChain.BaseSCEV, Offset);

993 for (auto &E : BucketChain.Elements) {

994 if (E.Offset)

996 else

998 }

999

1000 std::swap(BucketChain.Elements[j], BucketChain.Elements[0]);

1001 break;

1002 }

1003 return true;

1004}

1005

1006bool PPCLoopInstrFormPrep::rewriteLoadStores(

1007 Loop *L, Bucket &BucketChain, SmallPtrSet<BasicBlock *, 16> &BBChanged,

1008 PrepForm Form) {

1009 bool MadeChange = false;

1010

1011 const SCEVAddRecExpr *BasePtrSCEV =

1013 if (!BasePtrSCEV->isAffine())

1014 return MadeChange;

1015

1017 SCEVExpander SCEVE(*SE, Header->getDataLayout(),

1018 "loopprepare-formrewrite");

1020 return MadeChange;

1021

1022 SmallPtrSet<Value *, 16> DeletedPtrs;

1023

1024

1025

1026

1027 bool CanPreInc = (Form == UpdateForm ||

1028 ((Form == DSForm) &&

1031 ->getAPInt()

1032 .urem(4) &&

1034

1035 std::pair<Instruction *, Instruction *> Base =

1036 rewriteForBase(L, BasePtrSCEV, BucketChain.Elements.begin()->Instr,

1037 CanPreInc, Form, SCEVE, DeletedPtrs);

1038

1039 if ( Base .first || Base .second)

1040 return MadeChange;

1041

1042

1043

1044 SmallPtrSet<Value *, 16> NewPtrs;

1046

1047 for (const BucketElement &BE : llvm::drop_begin(BucketChain.Elements)) {

1049 assert(Ptr && "No pointer operand");

1050 if (NewPtrs.count(Ptr))

1051 continue;

1052

1053 Instruction *NewPtr = rewriteForBucketElement(

1056 DeletedPtrs);

1057 assert(NewPtr && "wrong rewrite!\n");

1058 NewPtrs.insert(NewPtr);

1059 }

1060

1061

1062

1064

1065 for (auto *Ptr : DeletedPtrs) {

1067 BBChanged.insert(IDel->getParent());

1069 }

1070

1071 MadeChange = true;

1072

1073 SuccPrepCount++;

1074

1075 if (Form == DSForm && !CanPreInc)

1076 DSFormChainRewritten++;

1077 else if (Form == DQForm)

1078 DQFormChainRewritten++;

1079 else if (Form == UpdateForm || (Form == DSForm && CanPreInc))

1080 UpdFormChainRewritten++;

1081

1082 return MadeChange;

1083}

1084

1085bool PPCLoopInstrFormPrep::updateFormPrep(Loop *L,

1087 bool MadeChange = false;

1088 if (Buckets.empty())

1089 return MadeChange;

1090 SmallPtrSet<BasicBlock *, 16> BBChanged;

1091 for (auto &Bucket : Buckets)

1092

1093

1094 if (prepareBaseForUpdateFormChain(Bucket))

1095 MadeChange |= rewriteLoadStores(L, Bucket, BBChanged, UpdateForm);

1096

1097 if (MadeChange)

1098 for (auto *BB : BBChanged)

1100 return MadeChange;

1101}

1102

1103bool PPCLoopInstrFormPrep::dispFormPrep(Loop *L,

1105 PrepForm Form) {

1106 bool MadeChange = false;

1107

1108 if (Buckets.empty())

1109 return MadeChange;

1110

1111 SmallPtrSet<BasicBlock *, 16> BBChanged;

1112 for (auto &Bucket : Buckets) {

1114 continue;

1115 if (prepareBaseForDispFormChain(Bucket, Form))

1116 MadeChange |= rewriteLoadStores(L, Bucket, BBChanged, Form);

1117 }

1118

1119 if (MadeChange)

1120 for (auto *BB : BBChanged)

1122 return MadeChange;

1123}

1124

1125

1126

1127

1128

1129

1130

1131

1132

1133Value *PPCLoopInstrFormPrep::getNodeForInc(Loop *L, Instruction *MemI,

1134 const SCEV *BasePtrIncSCEV) {

1135

1136

1139

1141 return nullptr;

1142

1144 if (!BB)

1145 return nullptr;

1146

1147 BasicBlock *LatchBB = L->getLoopLatch();

1148

1149 if (!LatchBB)

1150 return nullptr;

1151

1152

1153

1155 for (auto &CurrentPHI : PHIIter) {

1157 if (!CurrentPHINode)

1158 continue;

1159

1161 continue;

1162

1163 const SCEV *PHISCEV = SE->getSCEVAtScope(CurrentPHINode, L);

1164

1166 if (!PHIBasePtrSCEV)

1167 continue;

1168

1169 const SCEV *PHIBasePtrIncSCEV = PHIBasePtrSCEV->getStepRecurrence(*SE);

1170

1171 if (!PHIBasePtrIncSCEV || (PHIBasePtrIncSCEV != BasePtrIncSCEV))

1172 continue;

1173

1174

1175

1177 continue;

1180 Value *StrippedBaseI = I;

1182 StrippedBaseI = BC->getOperand(0);

1183

1185 if (!StrippedI)

1186 continue;

1187

1188

1189

1190 if (StrippedI->getOpcode() == Instruction::Add ||

1191 (StrippedI->getOpcode() == Instruction::GetElementPtr &&

1197 }

1198 }

1199 }

1200 return nullptr;

1201}

1202

1203

1204

1205

1206

1207bool PPCLoopInstrFormPrep::alreadyPrepared(Loop *L, Instruction *MemI,

1208 const SCEV *BasePtrStartSCEV,

1209 const SCEV *BasePtrIncSCEV,

1210 PrepForm Form) {

1212 if (!BB)

1213 return false;

1214

1215 BasicBlock *PredBB = L->getLoopPredecessor();

1216 BasicBlock *LatchBB = L->getLoopLatch();

1217

1218 if (!PredBB || !LatchBB)

1219 return false;

1220

1221

1223 for (auto & CurrentPHI : PHIIter) {

1225 if (!CurrentPHINode)

1226 continue;

1227

1229 continue;

1230

1231 const SCEV *PHISCEV = SE->getSCEVAtScope(CurrentPHINode, L);

1232

1234 if (!PHIBasePtrSCEV)

1235 continue;

1236

1237 const SCEVConstant *PHIBasePtrIncSCEV =

1239 if (!PHIBasePtrIncSCEV)

1240 continue;

1241

1247 if (PHIBasePtrIncSCEV == BasePtrIncSCEV) {

1248

1249

1250 if ((Form == UpdateForm || Form == ChainCommoning ) &&

1251 PHIBasePtrSCEV->getStart() == BasePtrStartSCEV) {

1252 ++PHINodeAlreadyExistsUpdate;

1253 return true;

1254 }

1255 if (Form == DSForm || Form == DQForm) {

1259 if (Form == DSForm)

1260 ++PHINodeAlreadyExistsDS;

1261 else

1262 ++PHINodeAlreadyExistsDQ;

1263 return true;

1264 }

1265 }

1266 }

1267 }

1268 }

1269 }

1270 return false;

1271}

1272

1273bool PPCLoopInstrFormPrep::runOnLoop(Loop *L) {

1274 bool MadeChange = false;

1275

1276

1277 if (->isInnermost())

1278 return MadeChange;

1279

1280

1282 return MadeChange;

1283

1284 LLVM_DEBUG(dbgs() << "PIP: Examining: " << *L << "\n");

1285

1286 BasicBlock *LoopPredecessor = L->getLoopPredecessor();

1287

1288

1289

1290 if (!LoopPredecessor ||

1293 if (LoopPredecessor)

1294 MadeChange = true;

1295 }

1296 if (!LoopPredecessor) {

1297 LLVM_DEBUG(dbgs() << "PIP fails since no predecessor for current loop.\n");

1298 return MadeChange;

1299 }

1300

1301

1302 auto isUpdateFormCandidate = [&](const Instruction *I, Value *PtrValue,

1303 const Type *PointerElementType) {

1304 assert((PtrValue && I) && "Invalid parameter!");

1305

1306 if (ST && ST->hasAltivec() && PointerElementType->isVectorTy())

1307 return false;

1308

1310 if (II && ((II->getIntrinsicID() == Intrinsic::ppc_vsx_lxvp) ||

1311 II->getIntrinsicID() == Intrinsic::ppc_vsx_stxvp))

1312 return false;

1313

1314

1315

1316

1317

1318 if (PointerElementType->isIntegerTy(64)) {

1319 const SCEV *LSCEV = SE->getSCEVAtScope(PtrValue, L);

1321 if (!LARSCEV || LARSCEV->getLoop() != L)

1322 return false;

1323 if (const SCEVConstant *StepConst =

1325 const APInt &ConstInt = StepConst->getValue()->getValue();

1327 return false;

1328 }

1329 }

1330 return true;

1331 };

1332

1333

1334 auto isDSFormCandidate = [](const Instruction *I, Value *PtrValue,

1335 const Type *PointerElementType) {

1336 assert((PtrValue && I) && "Invalid parameter!");

1338 return false;

1339 return (PointerElementType->isIntegerTy(64)) ||

1340 (PointerElementType->isFloatTy()) ||

1341 (PointerElementType->isDoubleTy()) ||

1344 [](const User *U) { return isa(U); }));

1345 };

1346

1347

1348 auto isDQFormCandidate = [&](const Instruction *I, Value *PtrValue,

1349 const Type *PointerElementType) {

1350 assert((PtrValue && I) && "Invalid parameter!");

1351

1353 if (II)

1354 return II->getIntrinsicID() == Intrinsic::ppc_vsx_lxvp ||

1355 II->getIntrinsicID() == Intrinsic::ppc_vsx_stxvp;

1356

1357 return ST && ST->hasP9Vector() && (PointerElementType->isVectorTy());

1358 };

1359

1360

1361

1362

1363 auto isChainCommoningCandidate = [&](const Instruction *I, Value *PtrValue,

1364 const Type *PointerElementType) {

1365 const SCEVAddRecExpr *ARSCEV =

1367 if (!ARSCEV)

1368 return false;

1369

1371 return false;

1372

1374

1375

1377 return true;

1378

1380

1381

1382 if (!ASCEV)

1383 return false;

1384

1385

1386

1387 bool SawPointer = false;

1388 for (const SCEV *Op : ASCEV->operands()) {

1389 if (Op->getType()->isPointerTy()) {

1390 if (SawPointer)

1391 return false;

1392 SawPointer = true;

1393 } else if (->getType()->isIntegerTy())

1394 return false;

1395 }

1396

1397 return SawPointer;

1398 };

1399

1400

1401

1402 auto isValidConstantDiff = [](const SCEV *Diff) {

1404 };

1405

1406

1407

1408 auto isValidChainCommoningDiff = [](const SCEV *Diff) {

1409 assert(Diff && "Invalid Diff!\n");

1410

1411

1413 return false;

1414

1415

1417 return true;

1418

1420 if (!ADiff)

1421 return false;

1422

1423 for (const SCEV *Op : ADiff->operands())

1424 if (->getType()->isIntegerTy())

1425 return false;

1426

1427 return true;

1428 };

1429

1430 HasCandidateForPrepare = false;

1431

1432 LLVM_DEBUG(dbgs() << "Start to prepare for update form.\n");

1433

1434

1436 L, isUpdateFormCandidate, isValidConstantDiff, MaxVarsUpdateForm);

1437

1438

1439 if (!UpdateFormBuckets.empty())

1440 MadeChange |= updateFormPrep(L, UpdateFormBuckets);

1441 else if (!HasCandidateForPrepare) {

1444 << "No prepare candidates found, stop praparation for current loop!\n");

1445

1446 return MadeChange;

1447 }

1448

1449 LLVM_DEBUG(dbgs() << "Start to prepare for DS form.\n");

1450

1451

1453 L, isDSFormCandidate, isValidConstantDiff, MaxVarsDSForm);

1454

1455

1456 if (!DSFormBuckets.empty())

1457 MadeChange |= dispFormPrep(L, DSFormBuckets, DSForm);

1458

1459 LLVM_DEBUG(dbgs() << "Start to prepare for DQ form.\n");

1460

1461

1463 L, isDQFormCandidate, isValidConstantDiff, MaxVarsDQForm);

1464

1465

1466 if (!DQFormBuckets.empty())

1467 MadeChange |= dispFormPrep(L, DQFormBuckets, DQForm);

1468

1469

1470

1471

1473 LLVM_DEBUG(dbgs() << "Chain commoning is not enabled.\n");

1474 return MadeChange;

1475 }

1476

1477 LLVM_DEBUG(dbgs() << "Start to prepare for chain commoning.\n");

1479 collectCandidates(L, isChainCommoningCandidate, isValidChainCommoningDiff,

1481

1482

1483 if (!Buckets.empty())

1484 MadeChange |= chainCommoning(L, Buckets);

1485

1486 return MadeChange;

1487}

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

static const Function * getParent(const Value *V)

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

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

This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.

static bool runOnFunction(Function &F, bool PostInlining)

This file provides various utilities for inspecting and working with the control flow graph in LLVM I...

uint64_t IntrinsicInst * II

static cl::opt< unsigned > ChainCommonPrepMinThreshold("ppc-chaincommon-min-threshold", cl::Hidden, cl::init(4), cl::desc("Minimal common base load/store instructions triggering chain " "commoning preparation. Must be not smaller than 4"))

static cl::opt< unsigned > MaxVarsDQForm("ppc-dqprep-max-vars", cl::Hidden, cl::init(8), cl::desc("Potential PHI threshold per loop for PPC loop prep of DQ form"))

static constexpr StringRef GEPNodeOffNameSuffix

Definition PPCLoopInstrFormPrep.cpp:339

static cl::opt< unsigned > DispFormPrepMinThreshold("ppc-dispprep-min-threshold", cl::Hidden, cl::init(2), cl::desc("Minimal common base load/store instructions triggering DS/DQ form " "preparation"))

static Value * getPointerOperandAndType(Value *MemI, Type **PtrElementType=nullptr)

Definition PPCLoopInstrFormPrep.cpp:363

static constexpr StringRef GEPNodeIncNameSuffix

Definition PPCLoopInstrFormPrep.cpp:338

static cl::opt< unsigned > MaxVarsDSForm("ppc-dsprep-max-vars", cl::Hidden, cl::init(3), cl::desc("Potential PHI threshold per loop for PPC loop prep of DS form"))

static std::string getInstrName(const Value *I, StringRef Suffix)

Definition PPCLoopInstrFormPrep.cpp:355

static constexpr StringRef PHINodeNameSuffix

Definition PPCLoopInstrFormPrep.cpp:336

static cl::opt< unsigned > MaxVarsUpdateForm("ppc-preinc-prep-max-vars", cl::Hidden, cl::init(3), cl::desc("Potential PHI threshold per loop for PPC loop prep of update " "form"))

static cl::opt< unsigned > MaxVarsChainCommon("ppc-chaincommon-max-vars", cl::Hidden, cl::init(4), cl::desc("Bucket number per loop for PPC loop chain common"))

static bool IsPtrInBounds(Value *BasePtr)

Definition PPCLoopInstrFormPrep.cpp:345

static cl::opt< unsigned > MaxVarsPrep("ppc-formprep-max-vars", cl::Hidden, cl::init(24), cl::desc("Potential common base number threshold per function " "for PPC loop prep"))

static cl::opt< bool > PreferUpdateForm("ppc-formprep-prefer-update", cl::init(true), cl::Hidden, cl::desc("prefer update form when ds form is also a update form"))

static cl::opt< bool > EnableChainCommoning("ppc-formprep-chain-commoning", cl::init(false), cl::Hidden, cl::desc("Enable chain commoning in PPC loop prepare pass."))

static constexpr StringRef CastNodeNameSuffix

Definition PPCLoopInstrFormPrep.cpp:337

static cl::opt< bool > EnableUpdateFormForNonConstInc("ppc-formprep-update-nonconst-inc", cl::init(false), cl::Hidden, cl::desc("prepare update form when the load/store increment is a loop " "invariant non-const value."))

#define INITIALIZE_PASS_DEPENDENCY(depName)

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

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

This file defines the SmallPtrSet 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)

LLVM_ABI APInt urem(const APInt &RHS) const

Unsigned remainder operation.

bool isSignedIntN(unsigned N) const

Check if this APInt has an N-bits signed integer value.

LLVM_ABI APInt srem(const APInt &RHS) const

Function for signed remainder operation.

AnalysisUsage & addRequired()

AnalysisUsage & addPreserved()

Add the specified Pass class to the set of analyses preserved by this pass.

iterator_range< const_phi_iterator > phis() const

Returns a range that iterates over the phis in the basic block.

InstListType::iterator iterator

Instruction iterators...

const Instruction * getTerminator() const LLVM_READONLY

Returns the terminator instruction if the block is well formed or null if the block is not well forme...

This class represents a no-op cast from one type to another.

iterator find(const_arg_type_t< KeyT > Val)

bool contains(const_arg_type_t< KeyT > Val) const

Return true if the specified key is in the map, false otherwise.

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

an instruction for type-safe pointer arithmetic to access elements of arrays and structs

static GetElementPtrInst * Create(Type *PointeeType, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)

LLVM_ABI void setIsInBounds(bool b=true)

Set or clear the inbounds flag on this GEP instruction.

Module * getParent()

Get the module that this global value is contained inside of...

LLVM_ABI void insertBefore(InstListType::iterator InsertPos)

Insert an unlinked instruction into a basic block immediately before the specified position.

unsigned getOpcode() const

Returns a member of one of the enums like Instruction::Add.

LLVM_ABI void insertAfter(Instruction *InsertPos)

Insert an unlinked instruction into a basic block immediately after the specified instruction.

A wrapper class for inspecting calls to intrinsic functions.

An instruction for reading from memory.

The legacy pass manager's analysis pass to compute loop information.

void addIncoming(Value *V, BasicBlock *BB)

Add an incoming value to the end of the PHI list.

Value * getIncomingValueForBlock(const BasicBlock *BB) const

BasicBlock * getIncomingBlock(unsigned i) const

Return incoming basic block number i.

int getBasicBlockIndex(const BasicBlock *BB) const

Return the first index of the specified basic block in the value list for this PHI.

unsigned getNumIncomingValues() const

Return the number of incoming edges.

static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)

Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...

Common code between 32-bit and 64-bit PowerPC targets.

const PPCSubtarget * getSubtargetImpl(const Function &F) const override

Virtual method implemented by subclasses that returns a reference to that target's TargetSubtargetInf...

const SCEV * getStart() const

const SCEV * getStepRecurrence(ScalarEvolution &SE) const

Constructs and returns the recurrence indicating how much this expression steps by.

bool isAffine() const

Return true if this represents an expression A + B*x where A and B are loop invariant values.

const Loop * getLoop() const

const APInt & getAPInt() const

LLVM_ABI bool isSafeToExpand(const SCEV *S) const

Return true if the given expression is safe to expand in the sense that all materialized values are s...

void clear()

Erase the contents of the InsertedExpressions map so that users trying to expand the same expression ...

LLVM_ABI Value * expandCodeFor(const SCEV *SH, Type *Ty, BasicBlock::iterator I)

Insert code to directly compute the specified SCEV expression into the program.

ArrayRef< const SCEV * > operands() const

This class represents an analyzed expression in the program.

LLVM_ABI Type * getType() const

Return the LLVM type of this SCEV expression.

LLVM_ABI const SCEV * getNegativeSCEV(const SCEV *V, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)

Return the SCEV object corresponding to -V.

LLVM_ABI const SCEV * getSCEVAtScope(const SCEV *S, const Loop *L)

Return a SCEV expression for the specified value at the specified scope in the program.

LLVM_ABI bool isLoopInvariant(const SCEV *S, const Loop *L)

Return true if the value of the given SCEV is unchanging in the specified loop.

LLVM_ABI bool isSCEVable(Type *Ty) const

Test if values of the given type are analyzable within the SCEV framework.

LLVM_ABI const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)

Return LHS-RHS.

LLVM_ABI const SCEV * getAddExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)

Get a canonical add expression, or something simpler if possible.

size_type count(ConstPtrType Ptr) const

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

std::pair< iterator, bool > insert(PtrType Ptr)

Inserts Ptr if and only if there is no element in the container equal to Ptr.

An instruction for storing to memory.

StringRef - Represent a constant reference to a string, i.e.

The instances of the Type class are immutable: once they are created, they are never changed.

bool isVectorTy() const

True if this is an instance of VectorType.

bool isFloatTy() const

Return true if this is 'float', a 32-bit IEEE fp type.

LLVM_ABI unsigned getPointerAddressSpace() const

Get the address space of this pointer or pointer vector type.

static LLVM_ABI IntegerType * getInt8Ty(LLVMContext &C)

bool isDoubleTy() const

Return true if this is 'double', a 64-bit IEEE fp type.

bool isIntegerTy() const

True if this is an instance of IntegerType.

bool isVoidTy() const

Return true if this is 'void'.

Value * getOperand(unsigned i) const

unsigned getNumOperands() const

LLVM Value Representation.

Type * getType() const

All values are typed, get the type of this value.

LLVM_ABI void replaceAllUsesWith(Value *V)

Change all uses of this to point to a new Value.

LLVM_ABI LLVMContext & getContext() const

All values hold a context through their type.

const ParentTy * getParent() const

self_iterator getIterator()

@ BasicBlock

Various leaf nodes.

initializer< Ty > init(const Ty &Val)

friend class Instruction

Iterator for Instructions in a `BasicBlock.

This is an optimization pass for GlobalISel generic memory operations.

auto drop_begin(T &&RangeOrContainer, size_t N=1)

Return a range covering RangeOrContainer with the first N elements excluded.

FunctionAddr VTableAddr Value

LLVM_ABI BasicBlock * InsertPreheaderForLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)

InsertPreheaderForLoop - Once we discover that a loop doesn't have a preheader, this method is called...

LLVM_ABI bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())

If the specified value is a trivially dead instruction, delete it.

FunctionPass * createPPCLoopInstrFormPrepPass(PPCTargetMachine &TM)

Definition PPCLoopInstrFormPrep.cpp:341

decltype(auto) dyn_cast(const From &Val)

dyn_cast - Return the argument parameter cast to the specified type.

auto pred_size(const MachineBasicBlock *BB)

bool any_of(R &&range, UnaryPredicate P)

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

LLVM_ABI bool DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr)

Examine each PHI in the given block and delete it if it is dead.

LLVM_ABI raw_ostream & dbgs()

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

class LLVM_GSL_OWNER SmallVector

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

bool isa(const From &Val)

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

iterator_range(Container &&) -> iterator_range< llvm::detail::IterOfRange< Container > >

DWARFExpression::Operation Op

decltype(auto) cast(const From &Val)

cast - Return the argument parameter cast to the specified type.

auto predecessors(const MachineBasicBlock *BB)

iterator_range< df_iterator< T > > depth_first(const T &G)

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

Implement std::swap in terms of BitVector swap.