LoopPredication.cpp Source File (original) (raw)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

203#include

204

205#define DEBUG_TYPE "loop-predication"

206

207 STATISTIC(TotalConsidered, "Number of guards considered");

208 STATISTIC(TotalWidened, "Number of checks widened");

209

210using namespace llvm;

211

214

217

221

222

223

224

225

227 "loop-predication-latch-probability-scale", cl::Hidden, cl::init(2.0),

228 cl::desc("scale factor for the latch probability. Value should be greater "

229 "than 1. Lower values are ignored"));

230

232 "loop-predication-predicate-widenable-branches-to-deopt", cl::Hidden,

233 cl::desc("Whether or not we should predicate guards "

234 "expressed as widenable branches to deoptimize blocks"),

236

238 "loop-predication-insert-assumes-of-predicated-guards-conditions",

240 cl::desc("Whether or not we should insert assumes of conditions of "

241 "predicated guards"),

243

244namespace {

245

246

247struct LoopICmp {

250 const SCEV *Limit;

252 const SCEV *Limit)

253 : Pred(Pred), IV(IV), Limit(Limit) {}

254 LoopICmp() = default;

255 void dump() {

256 dbgs() << "LoopICmp Pred = " << Pred << ", IV = " << *IV

257 << ", Limit = " << *Limit << "\n";

258 }

259};

260

261class LoopPredication {

263 DominatorTree *DT;

264 ScalarEvolution *SE;

265 LoopInfo *LI;

266 MemorySSAUpdater *MSSAU;

267

268 Loop *L;

269 const DataLayout *DL;

271 LoopICmp LatchCheck;

272

273 bool isSupportedStep(const SCEV* Step);

274 std::optional parseLoopICmp(ICmpInst *ICI);

275 std::optional parseLoopLatchICmp();

276

277

278

279

280

282

283

284

285

286 Instruction *findInsertPt(const SCEVExpander &Expander, Instruction *User,

288

289

290

291

292 bool isLoopInvariantValue(const SCEV* S);

293

294 Value *expandCheck(SCEVExpander &Expander, Instruction *Guard,

295 ICmpInst::Predicate Pred, const SCEV *LHS,

296 const SCEV *RHS);

297

298 std::optional<Value *> widenICmpRangeCheck(ICmpInst *ICI,

299 SCEVExpander &Expander,

300 Instruction *Guard);

301 std::optional<Value *>

302 widenICmpRangeCheckIncrementingLoop(LoopICmp LatchCheck, LoopICmp RangeCheck,

303 SCEVExpander &Expander,

304 Instruction *Guard);

305 std::optional<Value *>

306 widenICmpRangeCheckDecrementingLoop(LoopICmp LatchCheck, LoopICmp RangeCheck,

307 SCEVExpander &Expander,

308 Instruction *Guard);

309 void widenChecks(SmallVectorImpl<Value *> &Checks,

310 SmallVectorImpl<Value *> &WidenedChecks,

311 SCEVExpander &Expander, Instruction *Guard);

312 bool widenGuardConditions(IntrinsicInst *II, SCEVExpander &Expander);

313 bool widenWidenableBranchGuardConditions(BranchInst *Guard, SCEVExpander &Expander);

314

315

316

317

318 bool isLoopProfitableToPredicate();

319

320 bool predicateLoopExits(Loop *L, SCEVExpander &Rewriter);

321

322public:

324 LoopInfo *LI, MemorySSAUpdater *MSSAU)

325 : AA(AA), DT(DT), SE(SE), LI(LI), MSSAU(MSSAU){};

326 bool runOnLoop(Loop *L);

327};

328

329}

330

334 std::unique_ptr MSSAU;

336 MSSAU = std::make_unique(AR.MSSA);

337 LoopPredication LP(&AR.AA, &AR.DT, &AR.SE, &AR.LI,

338 MSSAU ? MSSAU.get() : nullptr);

339 if (!LP.runOnLoop(&L))

341

345 return PA;

346}

347

348std::optional LoopPredication::parseLoopICmp(ICmpInst *ICI) {

352

353 const SCEV *LHSS = SE->getSCEV(LHS);

355 return std::nullopt;

356 const SCEV *RHSS = SE->getSCEV(RHS);

358 return std::nullopt;

359

360

361 if (SE->isLoopInvariant(LHSS, L)) {

365 }

366

368 if (!AR || AR->getLoop() != L)

369 return std::nullopt;

370

371 return LoopICmp(Pred, AR, RHSS);

372}

373

379 assert(Ty == RHS->getType() && "expandCheck operands have different types?");

380

381 if (SE->isLoopInvariant(LHS, L) && SE->isLoopInvariant(RHS, L)) {

383 if (SE->isLoopEntryGuardedByCond(L, Pred, LHS, RHS))

384 return Builder.getTrue();

387 return Builder.getFalse();

388 }

389

394 IRBuilder<> Builder(findInsertPt(Guard, {LHSV, RHSV}));

395 return Builder.CreateICmp(Pred, LHSV, RHSV);

396}

397

398

399

400

401

402

403

404

405

406

407

408

409

410

413 const LoopICmp LatchCheck,

414 Type *RangeCheckType) {

416 return false;

417 assert(DL.getTypeSizeInBits(LatchCheck.IV->getType()).getFixedValue() >

418 DL.getTypeSizeInBits(RangeCheckType).getFixedValue() &&

419 "Expected latch check IV type to be larger than range check operand "

420 "type!");

421

422

425 if (!Limit || !Start)

426 return false;

427

428

429

430

431

433 return false;

434

435

436

437 auto RangeCheckTypeBitSize =

438 DL.getTypeSizeInBits(RangeCheckType).getFixedValue();

439 return Start->getAPInt().getActiveBits() < RangeCheckTypeBitSize &&

440 Limit->getAPInt().getActiveBits() < RangeCheckTypeBitSize;

441}

442

443

444

445

448 const LoopICmp LatchCheck,

449 Type *RangeCheckType) {

450

451 auto *LatchType = LatchCheck.IV->getType();

452 if (RangeCheckType == LatchType)

453 return LatchCheck;

454

455 if (DL.getTypeSizeInBits(LatchType).getFixedValue() <

456 DL.getTypeSizeInBits(RangeCheckType).getFixedValue())

457 return std::nullopt;

459 return std::nullopt;

460

461

462 LoopICmp NewLatchCheck;

463 NewLatchCheck.Pred = LatchCheck.Pred;

466 if (!NewLatchCheck.IV)

467 return std::nullopt;

468 NewLatchCheck.Limit = SE.getTruncateExpr(LatchCheck.Limit, RangeCheckType);

470 << "can be represented as range check type:"

471 << *RangeCheckType << "\n");

472 LLVM_DEBUG(dbgs() << "LatchCheck.IV: " << *NewLatchCheck.IV << "\n");

473 LLVM_DEBUG(dbgs() << "LatchCheck.Limit: " << *NewLatchCheck.Limit << "\n");

474 return NewLatchCheck;

475}

476

477bool LoopPredication::isSupportedStep(const SCEV* Step) {

479}

480

484 if (->isLoopInvariant(Op))

485 return Use;

486 return Preheader->getTerminator();

487}

488

492

493

494

496 if (!SE->isLoopInvariant(Op, L) ||

498 return Use;

499 return Preheader->getTerminator();

500}

501

502bool LoopPredication::isLoopInvariantValue(const SCEV* S) {

503

504

505

506

507

508

509

510

511

512

513

514

515

516

517

518

519

520

521

522 if (SE->isLoopInvariant(S, L))

523

524

525 return true;

526

527

528

529

532 if (LI->isUnordered() && L->hasLoopInvariantOperands(LI))

533 if ( isModSet (AA->getModRefInfoMask(LI->getOperand(0))) ||

534 LI->hasMetadata(LLVMContext::MD_invariant_load))

535 return true;

536 return false;

537}

538

539std::optional<Value *> LoopPredication::widenICmpRangeCheckIncrementingLoop(

540 LoopICmp LatchCheck, LoopICmp RangeCheck, SCEVExpander &Expander,

542 auto *Ty = RangeCheck.IV->getType();

543

544

545

546

547

548

549 const SCEV *GuardStart = RangeCheck.IV->getStart();

550 const SCEV *GuardLimit = RangeCheck.Limit;

551 const SCEV *LatchStart = LatchCheck.IV->getStart();

552 const SCEV *LatchLimit = LatchCheck.Limit;

553

554

555

556 if (!isLoopInvariantValue(GuardStart) ||

557 !isLoopInvariantValue(GuardLimit) ||

558 !isLoopInvariantValue(LatchStart) ||

559 !isLoopInvariantValue(LatchLimit)) {

561 return std::nullopt;

562 }

566 return std::nullopt;

567 }

568

569

571 SE->getAddExpr(SE->getMinusSCEV(GuardLimit, GuardStart),

572 SE->getMinusSCEV(LatchStart, SE->getOne(Ty)));

573 auto LimitCheckPred =

575

576 LLVM_DEBUG(dbgs() << "LHS: " << *LatchLimit << "\n");

578 LLVM_DEBUG(dbgs() << "Pred: " << LimitCheckPred << "\n");

579

580 auto *LimitCheck =

581 expandCheck(Expander, Guard, LimitCheckPred, LatchLimit, RHS);

582 auto *FirstIterationCheck = expandCheck(Expander, Guard, RangeCheck.Pred,

583 GuardStart, GuardLimit);

584 IRBuilder<> Builder(findInsertPt(Guard, {FirstIterationCheck, LimitCheck}));

586 Builder.CreateAnd(FirstIterationCheck, LimitCheck));

587}

588

589std::optional<Value *> LoopPredication::widenICmpRangeCheckDecrementingLoop(

590 LoopICmp LatchCheck, LoopICmp RangeCheck, SCEVExpander &Expander,

592 auto *Ty = RangeCheck.IV->getType();

593 const SCEV *GuardStart = RangeCheck.IV->getStart();

594 const SCEV *GuardLimit = RangeCheck.Limit;

595 const SCEV *LatchStart = LatchCheck.IV->getStart();

596 const SCEV *LatchLimit = LatchCheck.Limit;

597

598

599

600 if (!isLoopInvariantValue(GuardStart) ||

601 !isLoopInvariantValue(GuardLimit) ||

602 !isLoopInvariantValue(LatchStart) ||

603 !isLoopInvariantValue(LatchLimit)) {

605 return std::nullopt;

606 }

610 return std::nullopt;

611 }

612

613

614 auto *PostDecLatchCheckIV = LatchCheck.IV->getPostIncExpr(*SE);

615 if (RangeCheck.IV != PostDecLatchCheckIV) {

616 LLVM_DEBUG(dbgs() << "Not the same. PostDecLatchCheckIV: "

617 << *PostDecLatchCheckIV

618 << " and RangeCheckIV: " << *RangeCheck.IV << "\n");

619 return std::nullopt;

620 }

621

622

623

624

625

626 auto LimitCheckPred =

628 auto *FirstIterationCheck = expandCheck(Expander, Guard,

630 GuardStart, GuardLimit);

631 auto *LimitCheck = expandCheck(Expander, Guard, LimitCheckPred, LatchLimit,

632 SE->getOne(Ty));

633 IRBuilder<> Builder(findInsertPt(Guard, {FirstIterationCheck, LimitCheck}));

635 Builder.CreateAnd(FirstIterationCheck, LimitCheck));

636}

637

639 LoopICmp& RC) {

640

641

647}

648

649

650

651

652std::optional<Value *>

655 LLVM_DEBUG(dbgs() << "Analyzing ICmpInst condition:\n");

657

658

659

660

661

662 auto RangeCheck = parseLoopICmp(ICI);

663 if (!RangeCheck) {

664 LLVM_DEBUG(dbgs() << "Failed to parse the loop latch condition!\n");

665 return std::nullopt;

666 }

670 LLVM_DEBUG(dbgs() << "Unsupported range check predicate("

671 << RangeCheck->Pred << ")!\n");

672 return std::nullopt;

673 }

674 auto *RangeCheckIV = RangeCheck->IV;

675 if (!RangeCheckIV->isAffine()) {

676 LLVM_DEBUG(dbgs() << "Range check IV is not affine!\n");

677 return std::nullopt;

678 }

679 const SCEV *Step = RangeCheckIV->getStepRecurrence(*SE);

680

681

682 if (!isSupportedStep(Step)) {

683 LLVM_DEBUG(dbgs() << "Range check and latch have IVs different steps!\n");

684 return std::nullopt;

685 }

686 auto *Ty = RangeCheckIV->getType();

688 if (!CurrLatchCheckOpt) {

689 LLVM_DEBUG(dbgs() << "Failed to generate a loop latch check "

690 "corresponding to range type: "

691 << *Ty << "\n");

692 return std::nullopt;

693 }

694

695 LoopICmp CurrLatchCheck = *CurrLatchCheckOpt;

696

697

700 "Range and latch steps should be of same type!");

702 LLVM_DEBUG(dbgs() << "Range and latch have different step values!\n");

703 return std::nullopt;

704 }

705

706 if (Step->isOne())

707 return widenICmpRangeCheckIncrementingLoop(CurrLatchCheck, *RangeCheck,

708 Expander, Guard);

709 else {

711 return widenICmpRangeCheckDecrementingLoop(CurrLatchCheck, *RangeCheck,

712 Expander, Guard);

713 }

714}

715

719 for (auto &Check : Checks)

721 if (auto NewRangeCheck = widenICmpRangeCheck(ICI, Expander, Guard)) {

723 Check = *NewRangeCheck;

724 }

725}

726

727bool LoopPredication::widenGuardConditions(IntrinsicInst *Guard,

731

732 TotalConsidered++;

736 widenChecks(Checks, WidenedChecks, Expander, Guard);

737 if (WidenedChecks.empty())

738 return false;

739

740 TotalWidened += WidenedChecks.size();

741

742

743 IRBuilder<> Builder(findInsertPt(Guard, Checks));

744 Value *AllChecks = Builder.CreateAnd(Checks);

745 auto *OldCond = Guard->getOperand(0);

749 Builder.CreateAssumption(OldCond);

750 }

752

753 LLVM_DEBUG(dbgs() << "Widened checks = " << WidenedChecks.size() << "\n");

754 return true;

755}

756

757bool LoopPredication::widenWidenableBranchGuardConditions(

762

763 TotalConsidered++;

767

768

771 widenChecks(Checks, WidenedChecks, Expander, BI);

772 if (WidenedChecks.empty())

773 return false;

774

775 TotalWidened += WidenedChecks.size();

776

777

778 IRBuilder<> Builder(findInsertPt(BI, Checks));

779 Value *AllChecks = Builder.CreateAnd(Checks);

785

786

787

788 Value *AssumeCond = Builder.CreateAnd(WidenedChecks);

791 auto *PN = Builder.CreatePHI(AssumeCond->getType(), pred_size(IfTrueBB),

792 "assume.cond");

794 PN->addIncoming(Pred == GuardBB ? AssumeCond : Builder.getTrue(), Pred);

795 AssumeCond = PN;

796 }

797 Builder.CreateAssumption(AssumeCond);

798 }

801 "Stopped being a guard after transform?");

802

803 LLVM_DEBUG(dbgs() << "Widened checks = " << WidenedChecks.size() << "\n");

804 return true;

805}

806

807std::optional LoopPredication::parseLoopLatchICmp() {

809

810 BasicBlock *LoopLatch = L->getLoopLatch();

811 if (!LoopLatch) {

812 LLVM_DEBUG(dbgs() << "The loop doesn't have a single latch!\n");

813 return std::nullopt;

814 }

815

818 LLVM_DEBUG(dbgs() << "Failed to match the latch terminator!\n");

819 return std::nullopt;

820 }

823 (TrueDest == L->getHeader() || BI->getSuccessor(1) == L->getHeader()) &&

824 "One of the latch's destinations must be the header");

825

827 if (!ICI) {

828 LLVM_DEBUG(dbgs() << "Failed to match the latch condition!\n");

829 return std::nullopt;

830 }

831 auto Result = parseLoopICmp(ICI);

832 if (!Result) {

833 LLVM_DEBUG(dbgs() << "Failed to parse the loop latch condition!\n");

834 return std::nullopt;

835 }

836

837 if (TrueDest != L->getHeader())

839

840

841

842 if ( Result ->IV->isAffine()) {

843 LLVM_DEBUG(dbgs() << "The induction variable is not affine!\n");

844 return std::nullopt;

845 }

846

847 const SCEV *Step = Result->IV->getStepRecurrence(*SE);

848 if (!isSupportedStep(Step)) {

849 LLVM_DEBUG(dbgs() << "Unsupported loop stride(" << *Step << ")!\n");

850 return std::nullopt;

851 }

852

854 if (Step->isOne()) {

857 } else {

861 }

862 };

863

865 if (IsUnsupportedPredicate(Step, Result->Pred)) {

867 << ")!\n");

868 return std::nullopt;

869 }

870

872}

873

874bool LoopPredication::isLoopProfitableToPredicate() {

876 return true;

877

879 L->getExitEdges(ExitEdges);

880

881

882 if (ExitEdges.size() == 1)

883 return true;

884

885

886

887

888

889

890 auto *LatchBlock = L->getLoopLatch();

891 assert(LatchBlock && "Should have a single latch at this point!");

892 auto *LatchTerm = LatchBlock->getTerminator();

893 assert(LatchTerm->getNumSuccessors() == 2 &&

894 "expected to be an exiting block with 2 succs!");

895 unsigned LatchBrExitIdx =

896 LatchTerm->getSuccessor(0) == L->getHeader() ? 1 : 0;

897

898

899

900

901

902

903

904 auto *LatchExitBlock = LatchTerm->getSuccessor(LatchBrExitIdx);

906 LatchExitBlock->getTerminatingDeoptimizeCall())

907 return false;

908

909

910

912 return true;

913

914 auto ComputeBranchProbability =

918 unsigned NumSucc = Term->getNumSuccessors();

922 uint64_t Numerator = 0, Denominator = 0;

924 if (Term->getSuccessor(i) == ExitBlock)

925 Numerator += Weight;

926 Denominator += Weight;

927 }

928

929 if (Denominator == 0)

932 } else {

933 assert(LatchBlock != ExitingBlock &&

934 "Latch term should always have profile data!");

935

937 }

938 };

939

941 ComputeBranchProbability(LatchBlock, LatchExitBlock);

942

943

944

946 if (ScaleFactor < 1) {

949 << "Ignored user setting for loop-predication-latch-probability-scale: "

952 ScaleFactor = 1.0;

953 }

954 const auto LatchProbabilityThreshold = LatchExitProbability * ScaleFactor;

955

956 for (const auto &ExitEdge : ExitEdges) {

958 ComputeBranchProbability(ExitEdge.first, ExitEdge.second);

959

960

961 if (ExitingBlockProbability > LatchProbabilityThreshold)

962 return false;

963 }

964

965

966

967

968 return true;

969}

970

971

972

974

975

976

977

978

979

980 BasicBlock *BB = L->getLoopPreheader();

981 if (!BB)

982 return nullptr;

983 do {

986 BB = Pred;

987 continue;

988 }

989 break;

990 } while (true);

991

995 return BI;

996 }

997 return nullptr;

998}

999

1000

1001

1002

1007 L->getExitingBlocks(ExitingBlocks);

1008

1010 for (BasicBlock *ExitingBB : ExitingBlocks) {

1013 continue;

1015 "We should only have known counts for exiting blocks that "

1016 "dominate latch!");

1017 ExitCounts.push_back(ExitCount);

1018 }

1019 if (ExitCounts.size() < 2)

1022}

1023

1024

1025

1026

1027

1028

1029

1031

1032

1033

1034

1035

1036

1037

1038

1039

1040

1041

1042

1043

1044

1045

1046

1047

1048

1050 L->getExitingBlocks(ExitingBlocks);

1051

1052 if (ExitingBlocks.empty())

1053 return false;

1054

1055 auto *Latch = L->getLoopLatch();

1056 if (!Latch)

1057 return false;

1058

1060 if (!WidenableBR)

1061 return false;

1062

1063 const SCEV *LatchEC = SE->getExitCount(L, Latch);

1065 return false;

1066

1067

1068

1069

1070

1071

1072

1073 bool ChangedLoop = false;

1074

1075 for (auto *ExitingBB : ExitingBlocks) {

1076 if (LI->getLoopFor(ExitingBB) != L)

1077 continue;

1078

1080 if (!BI)

1081 continue;

1082

1085 assert(WC->hasOneUse() && "Not appropriate widenable branch!");

1086 WC->user_back()->replaceUsesOfWith(

1088 ChangedLoop = true;

1089 }

1090 }

1091 if (ChangedLoop)

1092 SE->forgetLoop(L);

1093

1094

1095

1096

1098

1099

1100

1101

1102

1103

1104

1107 !SE->isLoopInvariant(MinEC, L) ||

1108 Rewriter .isSafeToExpandAt(MinEC, IP))

1109 return ChangedLoop;

1110

1111 Rewriter.setInsertPoint(IP);

1113

1114 bool InvalidateLoop = false;

1115 Value *MinECV = nullptr;

1116 for (BasicBlock *ExitingBB : ExitingBlocks) {

1117

1118

1119

1120 if (LI->getLoopFor(ExitingBB) != L)

1121 continue;

1122

1123

1125 if (!BI)

1126 continue;

1127

1128

1130 continue;

1131

1132 const SCEV *ExitCount = SE->getExitCount(L, ExitingBB);

1135 Rewriter .isSafeToExpandAt(ExitCount, WidenableBR))

1136 continue;

1137

1138 const bool ExitIfTrue = ->contains(*succ_begin(ExitingBB));

1141 continue;

1142

1143

1144

1145

1146

1147

1148

1149

1150

1152 if (!MinECV)

1153 MinECV = Rewriter.expandCodeFor(MinEC);

1157 ECV = B.CreateZExt(ECV, WiderTy);

1158 RHS = B.CreateZExt(RHS, WiderTy);

1159 }

1160 assert(!Latch || DT->dominates(ExitingBB, Latch));

1162

1163

1164

1165 NewCond = B.CreateFreeze(NewCond);

1166

1168

1171 InvalidateLoop = true;

1172 }

1173

1174 if (InvalidateLoop)

1175

1176

1177

1178

1179 SE->forgetLoop(L);

1180

1181

1182 return true;

1183}

1184

1185bool LoopPredication::runOnLoop(Loop *Loop) {

1187

1190

1191 Module *M = L->getHeader()->getModule();

1192

1193

1194 auto *GuardDecl =

1196 bool HasIntrinsicGuards = GuardDecl && !GuardDecl->use_empty();

1198 M, Intrinsic::experimental_widenable_condition);

1199 bool HasWidenableConditions =

1201 if (!HasIntrinsicGuards && !HasWidenableConditions)

1202 return false;

1203

1204 DL = &M->getDataLayout();

1205

1206 Preheader = L->getLoopPreheader();

1207 if (!Preheader)

1208 return false;

1209

1210 auto LatchCheckOpt = parseLoopLatchICmp();

1211 if (!LatchCheckOpt)

1212 return false;

1213 LatchCheck = *LatchCheckOpt;

1214

1217

1218 if (!isLoopProfitableToPredicate()) {

1219 LLVM_DEBUG(dbgs() << "Loop not profitable to predicate!\n");

1220 return false;

1221 }

1222

1223

1226 for (const auto BB : L->blocks()) {

1227 for (auto &I : *BB)

1232 GuardsAsWidenableBranches.push_back(

1234 }

1235

1236 SCEVExpander Expander(*SE, *DL, "loop-predication");

1238 for (auto *Guard : Guards)

1239 Changed |= widenGuardConditions(Guard, Expander);

1240 for (auto *Guard : GuardsAsWidenableBranches)

1241 Changed |= widenWidenableBranchGuardConditions(Guard, Expander);

1242 Changed |= predicateLoopExits(L, Expander);

1243

1245 MSSAU->getMemorySSA()->verifyMemorySSA();

1247}

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

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

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

Module.h This file contains the declarations for the Module class.

static cl::opt< bool > LoopPredication("indvars-predicate-loops", cl::Hidden, cl::init(true), cl::desc("Predicate conditions in read only loops"))

static cl::opt< bool > SkipProfitabilityChecks("irce-skip-profitability-checks", cl::Hidden, cl::init(false))

const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]

static cl::opt< float > LatchExitProbabilityScale("loop-predication-latch-probability-scale", cl::Hidden, cl::init(2.0), cl::desc("scale factor for the latch probability. Value should be greater " "than 1. Lower values are ignored"))

static void normalizePredicate(ScalarEvolution *SE, Loop *L, LoopICmp &RC)

Definition LoopPredication.cpp:638

static cl::opt< bool > SkipProfitabilityChecks("loop-predication-skip-profitability-checks", cl::Hidden, cl::init(false))

static const SCEV * getMinAnalyzeableBackedgeTakenCount(ScalarEvolution &SE, DominatorTree &DT, Loop *L)

Return the minimum of all analyzeable exit counts.

Definition LoopPredication.cpp:1003

static cl::opt< bool > EnableCountDownLoop("loop-predication-enable-count-down-loop", cl::Hidden, cl::init(true))

static cl::opt< bool > EnableIVTruncation("loop-predication-enable-iv-truncation", cl::Hidden, cl::init(true))

static std::optional< LoopICmp > generateLoopLatchCheck(const DataLayout &DL, ScalarEvolution &SE, const LoopICmp LatchCheck, Type *RangeCheckType)

Definition LoopPredication.cpp:446

static cl::opt< bool > PredicateWidenableBranchGuards("loop-predication-predicate-widenable-branches-to-deopt", cl::Hidden, cl::desc("Whether or not we should predicate guards " "expressed as widenable branches to deoptimize blocks"), cl::init(true))

static bool isSafeToTruncateWideIVType(const DataLayout &DL, ScalarEvolution &SE, const LoopICmp LatchCheck, Type *RangeCheckType)

Definition LoopPredication.cpp:411

static cl::opt< bool > InsertAssumesOfPredicatedGuardsConditions("loop-predication-insert-assumes-of-predicated-guards-conditions", cl::Hidden, cl::desc("Whether or not we should insert assumes of conditions of " "predicated guards"), cl::init(true))

static BranchInst * FindWidenableTerminatorAboveLoop(Loop *L, LoopInfo &LI)

If we can (cheaply) find a widenable branch which controls entry into the loop, return it.

Definition LoopPredication.cpp:973

This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...

uint64_t IntrinsicInst * II

This file contains the declarations for profiling metadata utility functions.

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

#define STATISTIC(VARNAME, DESC)

Virtual Register Rewriter

static const uint32_t IV[8]

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

LLVM Basic Block Representation.

LLVM_ABI const_iterator getFirstInsertionPt() const

Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...

LLVM_ABI const BasicBlock * getSinglePredecessor() const

Return the predecessor of this block if it has a single predecessor block.

LLVM_ABI const BasicBlock * getUniquePredecessor() const

Return the predecessor of this block if it has a unique predecessor block.

LLVM_ABI const BasicBlock * getSingleSuccessor() const

Return the successor of this block if it has a single successor.

InstListType::iterator iterator

Instruction iterators...

LLVM_ABI const CallInst * getPostdominatingDeoptimizeCall() const

Returns the call instruction calling @llvm.experimental.deoptimize that is present either in current ...

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

Conditional or Unconditional Branch instruction.

void setCondition(Value *V)

bool isConditional() const

BasicBlock * getSuccessor(unsigned i) const

Value * getCondition() const

static LLVM_ABI BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)

Predicate

This enumeration lists the possible predicates for CmpInst subclasses.

@ ICMP_SLT

signed less than

@ ICMP_SLE

signed less or equal

@ ICMP_UGE

unsigned greater or equal

@ ICMP_UGT

unsigned greater than

@ ICMP_SGT

signed greater than

@ ICMP_ULT

unsigned less than

@ ICMP_SGE

signed greater or equal

@ ICMP_ULE

unsigned less or equal

Predicate getSwappedPredicate() const

For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.

Predicate getInversePredicate() const

For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...

Predicate getPredicate() const

Return the predicate for this instruction.

Predicate getFlippedStrictnessPredicate() const

For predicate of kind "is X or equal to 0" returns the predicate "is X".

static LLVM_ABI ConstantInt * getTrue(LLVMContext &Context)

A parsed version of the target data layout string in and methods for querying it.

Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.

LLVM_ABI bool dominates(const BasicBlock *BB, const Use &U) const

Return true if the (end of the) basic block BB dominates the use U.

This instruction compares its operands according to the predicate given to the constructor.

static bool isEquality(Predicate P)

Return true if this predicate is either EQ or NE.

Value * CreateFreeze(Value *V, const Twine &Name="")

Value * CreateICmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="")

This provides a uniform API for creating instructions and inserting them into a basic block: either a...

A wrapper class for inspecting calls to intrinsic functions.

This class provides an interface for updating the loop pass manager based on mutations to the loop ne...

PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)

Definition LoopPredication.cpp:331

Represents a single loop in the control flow graph.

An analysis that produces MemorySSA for a function.

A Module instance is used to store all the information related to an LLVM module.

A set of analyses that are preserved following a run of a transformation pass.

static PreservedAnalyses all()

Construct a special preserved set that preserves all passes.

This node represents a polynomial recurrence on the trip count of the specified loop.

const SCEV * getStart() const

const SCEV * getStepRecurrence(ScalarEvolution &SE) const

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

LLVM_ABI const SCEVAddRecExpr * getPostIncExpr(ScalarEvolution &SE) const

Return an expression representing the value of this expression one iteration of the loop ahead.

const Loop * getLoop() const

This class uses information about analyze scalars to rewrite expressions in canonical form.

LLVM_ABI bool isSafeToExpandAt(const SCEV *S, const Instruction *InsertionPoint) const

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

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

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

This means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...

This class represents an analyzed expression in the program.

LLVM_ABI bool isOne() const

Return true if the expression is a constant one.

LLVM_ABI bool isAllOnesValue() const

Return true if the expression is a constant all-ones value.

LLVM_ABI Type * getType() const

Return the LLVM type of this SCEV expression.

The main scalar evolution driver.

LLVM_ABI const SCEV * getTruncateExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)

LLVM_ABI const SCEV * getUMinFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS, bool Sequential=false)

Promote the operands to the wider of the types using zero-extension, and then perform a umin operatio...

LLVM_ABI std::optional< MonotonicPredicateType > getMonotonicPredicateType(const SCEVAddRecExpr *LHS, ICmpInst::Predicate Pred)

If, for all loop invariant X, the predicate "LHS `Pred` X" is monotonically increasing or decreasing,...

LLVM_ABI const SCEV * getCouldNotCompute()

LLVM_ABI const SCEV * getExitCount(const Loop *L, const BasicBlock *ExitingBlock, ExitCountKind Kind=Exact)

Return the number of times the backedge executes before the given exit would be taken; if not exactly...

LLVM_ABI bool isKnownPredicate(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)

Test if the given expression is known to satisfy the condition described by Pred, LHS,...

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

void push_back(const T &Elt)

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

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

bool isPointerTy() const

True if this is an instance of PointerType.

A Use represents the edge between a Value definition and its users.

void setOperand(unsigned i, Value *Val)

Value * getOperand(unsigned i) const

LLVM Value Representation.

Type * getType() const

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

LLVM_ABI LLVMContext & getContext() const

All values hold a context through their type.

LLVM_ABI void dump() const

Support for debugging, callable in GDB: V->dump()

const ParentTy * getParent() const

Abstract Attribute helper functions.

@ BasicBlock

Various leaf nodes.

LLVM_ABI Function * getDeclarationIfExists(const Module *M, ID id)

Look up the Function declaration of the intrinsic id in the Module M and return it if it exists.

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.

void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)

FunctionAddr VTableAddr Value

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.

auto enumerate(FirstRange &&First, RestRanges &&...Rest)

Given two or more input ranges, returns a new range whose values are tuples (A, B,...

decltype(auto) dyn_cast(const From &Val)

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

void widenWidenableBranch(BranchInst *WidenableBR, Value *NewCond)

Given a branch we know is widenable (defined per Analysis/GuardUtils.h), widen it such that condition...

Value * extractWidenableCondition(const User *U)

auto pred_size(const MachineBasicBlock *BB)

void parseWidenableGuard(const User *U, llvm::SmallVectorImpl< Value * > &Checks)

AnalysisManager< Loop, LoopStandardAnalysisResults & > LoopAnalysisManager

The loop analysis manager.

bool isGuard(const User *U)

Returns true iff U has semantics of a guard expressed in a form of call of llvm.experimental....

LLVM_ABI MDNode * getValidBranchWeightMDNode(const Instruction &I)

Get the valid branch weights metadata node.

bool isModSet(const ModRefInfo MRI)

LLVM_ABI bool hasValidBranchWeightMD(const Instruction &I)

Checks if an instructions has valid Branch Weight Metadata.

LLVM_ABI raw_ostream & dbgs()

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

bool isa(const From &Val)

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

RNSuccIterator< NodeRef, BlockT, RegionT > succ_begin(NodeRef Node)

bool isWidenableBranch(const User *U)

Returns true iff U is a widenable branch (that is, extractWidenableCondition returns widenable condit...

LLVM_ABI bool VerifyMemorySSA

Enables verification of MemorySSA.

bool isGuardAsWidenableBranch(const User *U)

Returns true iff U has semantics of a guard expressed in a form of a widenable conditional branch to ...

DWARFExpression::Operation Op

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

LLVM_ABI bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)

Extract branch weights from MD_prof metadata.

decltype(auto) cast(const From &Val)

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

LLVM_ABI PreservedAnalyses getLoopPassPreservedAnalyses()

Returns the minimum set of Analyses that all loop passes must preserve.

auto predecessors(const MachineBasicBlock *BB)

AAResults AliasAnalysis

Temporary typedef for legacy code that uses a generic AliasAnalysis pointer or reference.

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

Implement std::swap in terms of BitVector swap.

The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...