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

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

547

548 SCEVExpander SCEVE(*SE, "loopprepare-chaincommon");

549

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

551 unsigned BaseElemIdx = Bucket.ChainSize * ChainIdx;

552 const SCEV *BaseSCEV =

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

554 Bucket.Elements[BaseElemIdx].Offset)

555 : Bucket.BaseSCEV;

557

558

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

560 return MadeChange;

561

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

564

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

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

567 false , ChainCommoning, SCEVE, DeletedPtrs);

568

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

570 return MadeChange;

571

572

573

574 SmallPtrSet<Value *, 16> NewPtrs;

576

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

578 ++Idx) {

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

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

582 if (NewPtrs.count(Ptr))

583 continue;

584

585 const SCEV *OffsetSCEV =

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

587 Bucket.Elements[BaseElemIdx].Offset)

588 : Bucket.Elements[Idx].Offset;

589

590

591

592 if (!BaseElemIdx)

593 if (!SCEVE.isSafeToExpand(OffsetSCEV))

594 return false;

595

596 Value *OffsetValue = SCEVE.expandCodeFor(

598

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

600 OffsetValue, DeletedPtrs);

601

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

603 NewPtrs.insert(NewPtr);

604 }

605

606 ++ChainCommoningRewritten;

607 }

608

609

610

611 SCEVE.clear();

612

613 for (auto *Ptr : DeletedPtrs) {

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

617 }

618

619 MadeChange = true;

620 return MadeChange;

621}

622

623

624

625

626

627

628

629

630

631

632

633

634

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

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

637 Instruction *BaseMemI, bool CanPreInc,

638 PrepForm Form, SCEVExpander &SCEVE,

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

640

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

642

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

644

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

647

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

649 Type *I8PtrTy =

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

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

652

653 bool IsConstantInc = false;

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

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

656

657 const SCEVConstant *BasePtrIncConstantSCEV =

659 if (BasePtrIncConstantSCEV)

660 IsConstantInc = true;

661

662

663 if (!IncNode) {

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

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

666 }

667

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

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

673 }

674

675 const SCEV *BasePtrStartSCEV = nullptr;

676 if (CanPreInc) {

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

680 IsConstantInc ? BasePtrIncConstantSCEV

681 : BasePtrIncSCEV);

682 } else

683 BasePtrStartSCEV = BasePtrSCEV->getStart();

684

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

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

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

688 }

689

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

691

693 unsigned HeaderLoopPredCount = pred_size(Header);

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

695

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

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

699

702

703

704

706 if (PI != LoopPredecessor)

707 continue;

708

709 NewPHI->addIncoming(BasePtrStart, LoopPredecessor);

710 }

711

714 if (CanPreInc) {

718 InsPoint);

721 if (PI == LoopPredecessor)

722 continue;

723

725 }

727 NewBasePtr =

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

730 else

731 NewBasePtr = PtrInc;

732 } else {

733

734

736 if (PI == LoopPredecessor)

737 continue;

738

739

740

745 InsPoint);

747

749 }

750 PtrInc = NewPHI;

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

754 Header->getFirstInsertionPt());

755 else

756 NewBasePtr = NewPHI;

757 }

758

759 BasePtr->replaceAllUsesWith(NewBasePtr);

760

761 DeletedPtrs.insert(BasePtr);

762

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

764}

765

766Instruction *PPCLoopInstrFormPrep::rewriteForBucketElement(

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

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

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

772

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

774

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

777

779 if (!Element.Offset ||

782 RealNewPtr = NewBasePtr;

783 } else {

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

786 PtrIP = I->getIterator();

787

790 PtrIP = std::nullopt;

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

793 else if (!PtrIP)

795

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

798 I8Ty, PtrInc, OffToBase,

800 if (PtrIP)

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

802 else

805 RealNewPtr = NewPtr;

806 }

807

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

813 } else

814 ReplNewPtr = RealNewPtr;

815

817 DeletedPtrs.insert(Ptr);

818

819 return ReplNewPtr;

820}

821

822void PPCLoopInstrFormPrep::addOneCandidate(

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

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

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

828

829 bool FoundBucket = false;

830 for (auto &B : Buckets) {

833 continue;

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

835 if (isValidDiff(Diff)) {

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

837 FoundBucket = true;

838 break;

839 }

840 }

841

842 if (!FoundBucket) {

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

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

845 << MaxCandidateNum << "\n");

846 return;

847 }

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

849 }

850}

851

853 Loop *L,

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

855 isValidCandidate,

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

858

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

860 for (auto &J : *BB) {

861 Value *PtrValue = nullptr;

862 Type *PointerElementType = nullptr;

864

865 if (!PtrValue)

866 continue;

867

869 continue;

870

871 if (L->isLoopInvariant(PtrValue))

872 continue;

873

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

877 continue;

878

879

880 HasCandidateForPrepare = true;

881

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

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

884 }

885 return Buckets;

886}

887

888bool PPCLoopInstrFormPrep::prepareBaseForDispFormChain(Bucket &BucketChain,

889 PrepForm Form) {

890

891

892

893

894

895

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

897

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

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

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

901 else {

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

903 ->getAPInt()

904 .urem(Form);

905 if (!RemainderOffsetInfo.contains(Remainder))

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

907 else

908 RemainderOffsetInfo[Remainder].second++;

909 }

910 }

911

912

913

914

915

916

917

918

919

920

921

922

923

924

925

926 unsigned MaxCountRemainder = 0;

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

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

929 It != RemainderOffsetInfo.end() &&

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

931 MaxCountRemainder = j;

932

933

935 return false;

936

937

938

939 if (MaxCountRemainder == 0)

940 return true;

941

942

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

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

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

947 if (E.Offset)

949 else

951 }

952

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

954 BucketChain.Elements[0]);

955 return true;

956}

957

958

959

960

961

962

963

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

965

966

967

968

969

970

971

972

973

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

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

977 continue;

978

979

980 if (j == 0)

981 break;

982

983

984

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

987 break;

988

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

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

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

992 if (E.Offset)

994 else

996 }

997

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

999 break;

1000 }

1001 return true;

1002}

1003

1004bool PPCLoopInstrFormPrep::rewriteLoadStores(

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

1006 PrepForm Form) {

1007 bool MadeChange = false;

1008

1009 const SCEVAddRecExpr *BasePtrSCEV =

1011 if (!BasePtrSCEV->isAffine())

1012 return MadeChange;

1013

1014 SCEVExpander SCEVE(*SE, "loopprepare-formrewrite");

1016 return MadeChange;

1017

1018 SmallPtrSet<Value *, 16> DeletedPtrs;

1019

1020

1021

1022

1023 bool CanPreInc = (Form == UpdateForm ||

1024 ((Form == DSForm) &&

1027 ->getAPInt()

1028 .urem(4) &&

1030

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

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

1033 CanPreInc, Form, SCEVE, DeletedPtrs);

1034

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

1036 return MadeChange;

1037

1038

1039

1040 SmallPtrSet<Value *, 16> NewPtrs;

1042

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

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

1046 if (NewPtrs.count(Ptr))

1047 continue;

1048

1049 Instruction *NewPtr = rewriteForBucketElement(

1052 DeletedPtrs);

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

1054 NewPtrs.insert(NewPtr);

1055 }

1056

1057

1058

1060

1061 for (auto *Ptr : DeletedPtrs) {

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

1065 }

1066

1067 MadeChange = true;

1068

1069 SuccPrepCount++;

1070

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

1072 DSFormChainRewritten++;

1073 else if (Form == DQForm)

1074 DQFormChainRewritten++;

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

1076 UpdFormChainRewritten++;

1077

1078 return MadeChange;

1079}

1080

1081bool PPCLoopInstrFormPrep::updateFormPrep(Loop *L,

1083 bool MadeChange = false;

1084 if (Buckets.empty())

1085 return MadeChange;

1086 SmallPtrSet<BasicBlock *, 16> BBChanged;

1087 for (auto &Bucket : Buckets)

1088

1089

1090 if (prepareBaseForUpdateFormChain(Bucket))

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

1092

1093 if (MadeChange)

1094 for (auto *BB : BBChanged)

1096 return MadeChange;

1097}

1098

1099bool PPCLoopInstrFormPrep::dispFormPrep(Loop *L,

1101 PrepForm Form) {

1102 bool MadeChange = false;

1103

1104 if (Buckets.empty())

1105 return MadeChange;

1106

1107 SmallPtrSet<BasicBlock *, 16> BBChanged;

1108 for (auto &Bucket : Buckets) {

1110 continue;

1111 if (prepareBaseForDispFormChain(Bucket, Form))

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

1113 }

1114

1115 if (MadeChange)

1116 for (auto *BB : BBChanged)

1118 return MadeChange;

1119}

1120

1121

1122

1123

1124

1125

1126

1127

1128

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

1130 const SCEV *BasePtrIncSCEV) {

1131

1132

1135

1137 return nullptr;

1138

1140 if (!BB)

1141 return nullptr;

1142

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

1144

1145 if (!LatchBB)

1146 return nullptr;

1147

1148

1149

1151 for (auto &CurrentPHI : PHIIter) {

1153 if (!CurrentPHINode)

1154 continue;

1155

1157 continue;

1158

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

1160

1162 if (!PHIBasePtrSCEV)

1163 continue;

1164

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

1166

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

1168 continue;

1169

1170

1171

1173 continue;

1176 Value *StrippedBaseI = I;

1178 StrippedBaseI = BC->getOperand(0);

1179

1181 if (!StrippedI)

1182 continue;

1183

1184

1185

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

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

1193 }

1194 }

1195 }

1196 return nullptr;

1197}

1198

1199

1200

1201

1202

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

1204 const SCEV *BasePtrStartSCEV,

1205 const SCEV *BasePtrIncSCEV,

1206 PrepForm Form) {

1208 if (!BB)

1209 return false;

1210

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

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

1213

1214 if (!PredBB || !LatchBB)

1215 return false;

1216

1217

1219 for (auto & CurrentPHI : PHIIter) {

1221 if (!CurrentPHINode)

1222 continue;

1223

1225 continue;

1226

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

1228

1230 if (!PHIBasePtrSCEV)

1231 continue;

1232

1233 const SCEVConstant *PHIBasePtrIncSCEV =

1235 if (!PHIBasePtrIncSCEV)

1236 continue;

1237

1243 if (PHIBasePtrIncSCEV == BasePtrIncSCEV) {

1244

1245

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

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

1248 ++PHINodeAlreadyExistsUpdate;

1249 return true;

1250 }

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

1255 if (Form == DSForm)

1256 ++PHINodeAlreadyExistsDS;

1257 else

1258 ++PHINodeAlreadyExistsDQ;

1259 return true;

1260 }

1261 }

1262 }

1263 }

1264 }

1265 }

1266 return false;

1267}

1268

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

1270 bool MadeChange = false;

1271

1272

1273 if (->isInnermost())

1274 return MadeChange;

1275

1276

1278 return MadeChange;

1279

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

1281

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

1283

1284

1285

1286 if (!LoopPredecessor ||

1289 if (LoopPredecessor)

1290 MadeChange = true;

1291 }

1292 if (!LoopPredecessor) {

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

1294 return MadeChange;

1295 }

1296

1297

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

1299 const Type *PointerElementType) {

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

1301

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

1303 return false;

1304

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

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

1308 return false;

1309

1310

1311

1312

1313

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

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

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

1318 return false;

1319 if (const SCEVConstant *StepConst =

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

1323 return false;

1324 }

1325 }

1326 return true;

1327 };

1328

1329

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

1331 const Type *PointerElementType) {

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

1334 return false;

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

1336 (PointerElementType->isFloatTy()) ||

1337 (PointerElementType->isDoubleTy()) ||

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

1341 };

1342

1343

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

1345 const Type *PointerElementType) {

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

1347

1349 if (II)

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

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

1352

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

1354 };

1355

1356

1357

1358

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

1360 const Type *PointerElementType) {

1361 const SCEVAddRecExpr *ARSCEV =

1363 if (!ARSCEV)

1364 return false;

1365

1367 return false;

1368

1370

1371

1373 return true;

1374

1376

1377

1378 if (!ASCEV)

1379 return false;

1380

1381

1382

1383 bool SawPointer = false;

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

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

1386 if (SawPointer)

1387 return false;

1388 SawPointer = true;

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

1390 return false;

1391 }

1392

1393 return SawPointer;

1394 };

1395

1396

1397

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

1400 };

1401

1402

1403

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

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

1406

1407

1409 return false;

1410

1411

1413 return true;

1414

1416 if (!ADiff)

1417 return false;

1418

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

1420 if (->getType()->isIntegerTy())

1421 return false;

1422

1423 return true;

1424 };

1425

1426 HasCandidateForPrepare = false;

1427

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

1429

1430

1432 L, isUpdateFormCandidate, isValidConstantDiff, MaxVarsUpdateForm);

1433

1434

1435 if (!UpdateFormBuckets.empty())

1436 MadeChange |= updateFormPrep(L, UpdateFormBuckets);

1437 else if (!HasCandidateForPrepare) {

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

1441

1442 return MadeChange;

1443 }

1444

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

1446

1447

1449 L, isDSFormCandidate, isValidConstantDiff, MaxVarsDSForm);

1450

1451

1452 if (!DSFormBuckets.empty())

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

1454

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

1456

1457

1459 L, isDQFormCandidate, isValidConstantDiff, MaxVarsDQForm);

1460

1461

1462 if (!DQFormBuckets.empty())

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

1464

1465

1466

1467

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

1470 return MadeChange;

1471 }

1472

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

1475 collectCandidates(L, isChainCommoningCandidate, isValidChainCommoningDiff,

1477

1478

1479 if (!Buckets.empty())

1480 MadeChange |= chainCommoning(L, Buckets);

1481

1482 return MadeChange;

1483}

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.