LazyValueInfo.cpp Source File (original) (raw)

43#include

44using namespace llvm;

45using namespace PatternMatch;

47#define DEBUG_TYPE "lazy-value-info"

56}

58 "Lazy Value Information Analysis", false, true)

64namespace llvm {

67}

68}

79 return true;

82 return true;

83 return false;

84}

90namespace {

92 class LazyValueInfoCache;

93 struct LVIValueHandle final : public CallbackVH {

94 LazyValueInfoCache *Parent;

96 LVIValueHandle(Value *V, LazyValueInfoCache *P = nullptr)

99 void deleted() override;

100 void allUsesReplacedWith(Value *V) override {

101 deleted();

102 }

103 };

104}

105

106namespace {

108

109

110

111class LazyValueInfoCache {

112

113

114

115

116 struct BlockCacheEntry {

119

120

121 std::optional NonNullPointers;

122 };

123

124

126 BlockCache;

127

129

130 const BlockCacheEntry *getBlockEntry(BasicBlock *BB) const {

131 auto It = BlockCache.find_as(BB);

132 if (It == BlockCache.end())

133 return nullptr;

134 return It->second.get();

135 }

136

137 BlockCacheEntry *getOrCreateBlockEntry(BasicBlock *BB) {

138 auto It = BlockCache.find_as(BB);

139 if (It == BlockCache.end())

140 It = BlockCache.insert({BB, std::make_unique()}).first;

141

142 return It->second.get();

143 }

144

145 void addValueHandle(Value *Val) {

146 auto HandleIt = ValueHandles.find_as(Val);

147 if (HandleIt == ValueHandles.end())

148 ValueHandles.insert({Val, this});

149 }

150

151public:

154 BlockCacheEntry *Entry = getOrCreateBlockEntry(BB);

155

156

157

158 if (Result.isOverdefined())

159 Entry->OverDefined.insert(Val);

160 else

161 Entry->LatticeElements.insert({Val, Result});

162

163 addValueHandle(Val);

164 }

165

166 std::optional getCachedValueInfo(Value *V,

168 const BlockCacheEntry *Entry = getBlockEntry(BB);

169 if (!Entry)

170 return std::nullopt;

171

172 if (Entry->OverDefined.count(V))

174

175 auto LatticeIt = Entry->LatticeElements.find_as(V);

176 if (LatticeIt == Entry->LatticeElements.end())

177 return std::nullopt;

178

179 return LatticeIt->second;

180 }

181

182 bool

185 BlockCacheEntry *Entry = getOrCreateBlockEntry(BB);

186 if ( Entry ->NonNullPointers) {

187 Entry->NonNullPointers = InitFn(BB);

188 for (Value *V : *Entry->NonNullPointers)

189 addValueHandle(V);

190 }

191

192 return Entry->NonNullPointers->count(V);

193 }

194

195

196 void clear() {

197 BlockCache.clear();

198 ValueHandles.clear();

199 }

200

201

202 void eraseValue(Value *V);

203

204

205

207

208

209

210

212};

213}

214

215void LazyValueInfoCache::eraseValue(Value *V) {

216 for (auto &Pair : BlockCache) {

217 Pair.second->LatticeElements.erase(V);

218 Pair.second->OverDefined.erase(V);

219 if (Pair.second->NonNullPointers)

220 Pair.second->NonNullPointers->erase(V);

221 }

222

223 auto HandleIt = ValueHandles.find_as(V);

224 if (HandleIt != ValueHandles.end())

225 ValueHandles.erase(HandleIt);

226}

227

228void LVIValueHandle::deleted() {

229

230

231 Parent->eraseValue(*this);

232}

233

234void LazyValueInfoCache::eraseBlock(BasicBlock *BB) {

235 BlockCache.erase(BB);

236}

237

238void LazyValueInfoCache::threadEdgeImpl(BasicBlock *OldSucc,

240

241

242

243

244

245

246

247

248

249

250 std::vector<BasicBlock*> worklist;

251 worklist.push_back(OldSucc);

252

253 const BlockCacheEntry *Entry = getBlockEntry(OldSucc);

254 if (!Entry || Entry->OverDefined.empty())

255 return;

257 Entry->OverDefined.end());

258

259

260

261

262

263 while (!worklist.empty()) {

265 worklist.pop_back();

266

267

268 if (ToUpdate == NewSucc) continue;

269

270

271 auto OI = BlockCache.find_as(ToUpdate);

272 if (OI == BlockCache.end() || OI->second->OverDefined.empty())

273 continue;

274 auto &ValueSet = OI->second->OverDefined;

275

276 bool changed = false;

277 for (Value *V : ValsToClear) {

278 if (!ValueSet.erase(V))

279 continue;

280

281

282

283 changed = true;

284 }

285

286 if (!changed) continue;

287

289 }

290}

291

292namespace llvm {

293namespace {

294

295

298

299

301

302public:

304 : LVIImpl(L), DT(DTree) {}

305

306 void emitBasicBlockStartAnnot(const BasicBlock *BB,

308

309 void emitInstructionAnnot(const Instruction *I,

311};

312}

313

315

316

317 LazyValueInfoCache TheCache;

318

319

320

321

323

324

326

327

328

329 bool pushBlockValue(const std::pair<BasicBlock *, Value *> &BV) {

330 if (!BlockValueSet.insert(BV).second)

331 return false;

332

333 LLVM_DEBUG(dbgs() << "PUSH: " << *BV.second << " in "

334 << BV.first->getName() << "\n");

336 return true;

337 }

338

339 AssumptionCache *AC;

340 const DataLayout &DL;

341

342

343

345

346 std::optional getBlockValue(Value *Val, BasicBlock *BB,

348 std::optional getEdgeValue(Value *V, BasicBlock *F,

351

352

353

354

356 std::optional solveBlockValueImpl(Value *Val,

358 std::optional solveBlockValueNonLocal(Value *Val,

360 std::optional solveBlockValuePHINode(PHINode *PN,

362 std::optional solveBlockValueSelect(SelectInst *S,

364 std::optional getRangeFor(Value *V, Instruction *CxtI,

366 std::optional solveBlockValueBinaryOpImpl(

369 OpFn);

370 std::optional

372 std::optional solveBlockValueCast(CastInst *CI,

374 std::optional

376 std::optional solveBlockValueIntrinsic(IntrinsicInst *II,

378 std::optional

380 std::optional

383 void intersectAssumeOrGuardBlockValueConstantRange(Value *Val,

386

387 void solve();

388

389

390

391

392

393 std::optional

396 bool UseBlockValue);

397

398 std::optional

399 getValueFromICmpCondition(Value *Val, ICmpInst *ICI, bool isTrueDest,

400 bool UseBlockValue);

401

402 std::optional

403 getValueFromCondition(Value *Val, Value *Cond, bool IsTrueDest,

404 bool UseBlockValue, unsigned Depth = 0);

405

406 std::optional getEdgeValueLocal(Value *Val,

409 bool UseBlockValue);

410

411public:

412

413

414

417

418

419

420

421

423

424

425

429

431

432

434 TheCache.clear();

435 }

436

437

439 LazyValueInfoAnnotatedWriter Writer(this, DTree);

440 F.print(OS, &Writer);

441 }

442

443

444

446

447

448

450 TheCache.eraseBlock(BB);

451 }

452

453

454

456

459 : AC(AC), DL(DL), GuardDecl(GuardDecl) {}

460};

461}

462

463void LazyValueInfoImpl::solve() {

465 BlockValueStack;

466

467 unsigned processedCount = 0;

468 while (!BlockValueStack.empty()) {

469 processedCount++;

470

471

472

473

474

475

476

477

480 dbgs() << "Giving up on stack because we are getting too deep\n");

481

482 while (!StartingStack.empty()) {

483 std::pair<BasicBlock *, Value *> &e = StartingStack.back();

484 TheCache.insertResult(e.second, e.first,

487 }

488 BlockValueSet.clear();

489 BlockValueStack.clear();

490 return;

491 }

492 std::pair<BasicBlock *, Value *> e = BlockValueStack.back();

493 assert(BlockValueSet.count(e) && "Stack value should be in BlockValueSet!");

494 unsigned StackSize = BlockValueStack.size();

495 (void) StackSize;

496

497 if (solveBlockValue(e.second, e.first)) {

498

499 assert(BlockValueStack.size() == StackSize &&

500 BlockValueStack.back() == e && "Nothing should have been pushed!");

501#ifndef NDEBUG

502 std::optional BBLV =

503 TheCache.getCachedValueInfo(e.second, e.first);

504 assert(BBLV && "Result should be in cache!");

506 dbgs() << "POP " << *e.second << " in " << e.first->getName() << " = "

507 << *BBLV << "\n");

508#endif

509

510 BlockValueStack.pop_back();

511 BlockValueSet.erase(e);

512 } else {

513

514 assert(BlockValueStack.size() == StackSize + 1 &&

515 "Exactly one element should have been pushed!");

516 }

517 }

518}

519

520std::optional

521LazyValueInfoImpl::getBlockValue(Value *Val, BasicBlock *BB,

523

524 if (Constant *VC = dyn_cast(Val))

526

527 if (std::optional OptLatticeVal =

528 TheCache.getCachedValueInfo(Val, BB)) {

529 intersectAssumeOrGuardBlockValueConstantRange(Val, *OptLatticeVal, CxtI);

530 return OptLatticeVal;

531 }

532

533

534 if (!pushBlockValue({ BB, Val }))

536

537

538 return std::nullopt;

539}

540

543 default:

544 break;

545 case Instruction::Call:

546 case Instruction::Invoke:

547 if (std::optional Range = cast(BBI)->getRange())

549 [[fallthrough]];

550 case Instruction::Load:

552 if (isa(BBI->getType())) {

555 }

556 break;

557 };

558

560}

561

562bool LazyValueInfoImpl::solveBlockValue(Value *Val, BasicBlock *BB) {

563 assert(!isa(Val) && "Value should not be constant");

564 assert(!TheCache.getCachedValueInfo(Val, BB) &&

565 "Value should not be in cache");

566

567

568

569 std::optional Res = solveBlockValueImpl(Val, BB);

570 if (!Res)

571

572 return false;

573

574 TheCache.insertResult(Val, BB, *Res);

575 return true;

576}

577

578std::optional

579LazyValueInfoImpl::solveBlockValueImpl(Value *Val, BasicBlock *BB) {

580 Instruction *BBI = dyn_cast(Val);

581 if (!BBI || BBI->getParent() != BB)

582 return solveBlockValueNonLocal(Val, BB);

583

584 if (PHINode *PN = dyn_cast(BBI))

585 return solveBlockValuePHINode(PN, BB);

586

587 if (auto *SI = dyn_cast(BBI))

588 return solveBlockValueSelect(SI, BB);

589

590

591

592

593

594

595

596

597

598

602

604 if (auto *CI = dyn_cast(BBI))

605 return solveBlockValueCast(CI, BB);

606

607 if (BinaryOperator *BO = dyn_cast(BBI))

608 return solveBlockValueBinaryOp(BO, BB);

609

610 if (auto *IEI = dyn_cast(BBI))

611 return solveBlockValueInsertElement(IEI, BB);

612

613 if (auto *EVI = dyn_cast(BBI))

614 return solveBlockValueExtractValue(EVI, BB);

615

616 if (auto *II = dyn_cast(BBI))

617 return solveBlockValueIntrinsic(II, BB);

618 }

619

621 << "' - unknown inst def found.\n");

623}

624

626

627 if (Ptr->getType()->getPointerAddressSpace() == 0)

629}

630

633 if (LoadInst *L = dyn_cast(I)) {

635 } else if (StoreInst *S = dyn_cast(I)) {

637 } else if (MemIntrinsic *MI = dyn_cast(I)) {

638 if (MI->isVolatile()) return;

639

640

641 ConstantInt *Len = dyn_cast(MI->getLength());

642 if (!Len || Len->isZero()) return;

643

647 }

648}

649

650bool LazyValueInfoImpl::isNonNullAtEndOfBlock(Value *Val, BasicBlock *BB) {

653 return false;

654

656 return TheCache.isNonNullAtEndOfBlock(Val, BB, [](BasicBlock *BB) {

657 NonNullPointerSet NonNullPointers;

660 return NonNullPointers;

661 });

662}

663

664std::optional

665LazyValueInfoImpl::solveBlockValueNonLocal(Value *Val, BasicBlock *BB) {

667

668

670 assert(isa(Val) && "Unknown live-in to the entry block");

671 if (std::optional Range = cast(Val)->getRange())

674 }

675

676

677

678

679

680

681

682

683

684

686 std::optional EdgeResult = getEdgeValue(Val, Pred, BB);

687 if (!EdgeResult)

688

689 return std::nullopt;

690

691 Result.mergeIn(*EdgeResult);

692

693

694

695 if (Result.isOverdefined()) {

697 << "' - overdefined because of pred '"

698 << Pred->getName() << "' (non local).\n");

700 }

701 }

702

703

706}

707

708std::optional

709LazyValueInfoImpl::solveBlockValuePHINode(PHINode *PN, BasicBlock *BB) {

711

712

713

714

718

719

720

721 std::optional EdgeResult =

722 getEdgeValue(PhiVal, PhiBB, BB, PN);

723 if (!EdgeResult)

724

725 return std::nullopt;

726

727 Result.mergeIn(*EdgeResult);

728

729

730

731 if (Result.isOverdefined()) {

733 << "' - overdefined because of pred (local).\n");

734

736 }

737 }

738

739

740 assert( Result .isOverdefined() && "Possible PHI in entry block?");

742}

743

744

745

746void LazyValueInfoImpl::intersectAssumeOrGuardBlockValueConstantRange(

748 BBI = BBI ? BBI : dyn_cast(Val);

749 if (!BBI)

750 return;

751

754 if (!AssumeVH)

755 continue;

756

757

758

759

760 auto *I = cast(AssumeVH);

762 continue;

763

764 BBLV = BBLV.intersect(*getValueFromCondition(Val, I->getArgOperand(0),

765 true,

766 false));

767 }

768

769

770 if (GuardDecl && !GuardDecl->use_empty() &&

775 if (match(&I, m_IntrinsicIntrinsic::experimental\_guard(m_Value(Cond))))

776 BBLV = BBLV.intersect(*getValueFromCondition(Val, Cond,

777 true,

778 false));

779 }

780 }

781

783

784

787 isNonNullAtEndOfBlock(Val, BB))

789 }

790}

791

792std::optional

794

795 std::optional OptTrueVal =

796 getBlockValue(SI->getTrueValue(), BB, SI);

797 if (!OptTrueVal)

798 return std::nullopt;

800

801 std::optional OptFalseVal =

802 getBlockValue(SI->getFalseValue(), BB, SI);

803 if (!OptFalseVal)

804 return std::nullopt;

806

807 if (TrueVal.isConstantRange() || FalseVal.isConstantRange()) {

813

814

816 ((LHS == SI->getTrueValue() && RHS == SI->getFalseValue()) ||

817 (RHS == SI->getTrueValue() && LHS == SI->getFalseValue()))) {

819 switch (SPR.Flavor) {

820 default:

822 case SPF_SMIN:

823 return TrueCR.smin(FalseCR);

824 case SPF_UMIN:

825 return TrueCR.umin(FalseCR);

826 case SPF_SMAX:

827 return TrueCR.smax(FalseCR);

828 case SPF_UMAX:

829 return TrueCR.umax(FalseCR);

830 };

831 }();

833 ResultCR, TrueVal.isConstantRangeIncludingUndef() ||

834 FalseVal.isConstantRangeIncludingUndef());

835 }

836

838 if (LHS == SI->getTrueValue())

840 TrueCR.abs(), TrueVal.isConstantRangeIncludingUndef());

841 if (LHS == SI->getFalseValue())

843 FalseCR.abs(), FalseVal.isConstantRangeIncludingUndef());

844 }

845

848 if (LHS == SI->getTrueValue())

850 Zero.sub(TrueCR.abs()), FalseVal.isConstantRangeIncludingUndef());

851 if (LHS == SI->getFalseValue())

853 Zero.sub(FalseCR.abs()), FalseVal.isConstantRangeIncludingUndef());

854 }

855 }

856

857

858

859

861

862

865 TrueVal.intersect(*getValueFromCondition(SI->getTrueValue(), Cond,

866 true,

867 false));

869 FalseVal.intersect(*getValueFromCondition(SI->getFalseValue(), Cond,

870 false,

871 false));

872 }

873

875 Result.mergeIn(FalseVal);

877}

878

879std::optional

881 std::optional OptVal = getBlockValue(V, BB, CxtI);

882 if (!OptVal)

883 return std::nullopt;

884 return OptVal->asConstantRange(V->getType());

885}

886

887std::optional

888LazyValueInfoImpl::solveBlockValueCast(CastInst *CI, BasicBlock *BB) {

889

890

891

893 case Instruction::Trunc:

894 case Instruction::SExt:

895 case Instruction::ZExt:

896 break;

897 default:

898

900 << "' - overdefined (unknown cast).\n");

902 }

903

904

905

906

907 std::optional LHSRes = getRangeFor(CI->getOperand(0), CI, BB);

908 if (!LHSRes)

909

910 return std::nullopt;

912

914

915

916

917

919 ResultBitWidth));

920}

921

922std::optional

923LazyValueInfoImpl::solveBlockValueBinaryOpImpl(

926 OpFn) {

929

930 auto ThreadBinOpOverSelect =

932 bool XIsLHS) -> std::optional {

934

935 Constant *TrueC = dyn_cast(Y->getTrueValue());

936 if (!TrueC)

937 return std::nullopt;

938 Constant *FalseC = dyn_cast(Y->getFalseValue());

939 if (!FalseC)

940 return std::nullopt;

942 return std::nullopt;

943

945 CRX.intersectWith(getValueFromCondition(X, Cond, true,

946 false)

947 ->asConstantRange(X->getType()));

949 CRX.intersectWith(getValueFromCondition(X, Cond, false,

950 false)

951 ->asConstantRange(X->getType()));

954

955 if (XIsLHS)

957 OpFn(TrueX, TrueY).unionWith(OpFn(FalseX, FalseY)));

959 OpFn(TrueY, TrueX).unionWith(OpFn(FalseY, FalseX)));

960 };

961

962

963

964

965

966 std::optional LHSRes = getRangeFor(LHS, I, BB);

967 if (!LHSRes)

968 return std::nullopt;

969

970

971 if (auto *SI = dyn_cast(RHS)) {

972 if (auto Res = ThreadBinOpOverSelect(LHS, *LHSRes, SI, true))

973 return *Res;

974 }

975

976 std::optional RHSRes = getRangeFor(RHS, I, BB);

977 if (!RHSRes)

978 return std::nullopt;

979

980

981 if (auto *SI = dyn_cast(LHS)) {

982 if (auto Res = ThreadBinOpOverSelect(RHS, *RHSRes, SI, false))

983 return *Res;

984 }

985

989}

990

991std::optional

994 "all operands to binary operators are sized");

995 if (auto *OBO = dyn_cast(BO)) {

996 unsigned NoWrapKind = OBO->getNoWrapKind();

997 return solveBlockValueBinaryOpImpl(

998 BO, BB,

1001 });

1002 }

1003

1004 return solveBlockValueBinaryOpImpl(

1007 });

1008}

1009

1010std::optional

1011LazyValueInfoImpl::solveBlockValueOverflowIntrinsic(WithOverflowInst *WO,

1013 return solveBlockValueBinaryOpImpl(

1016 });

1017}

1018

1019std::optional

1024 << "' - unknown intrinsic.\n");

1025 return MetadataVal;

1026 }

1027

1030 std::optional Range = getRangeFor(Op, II, BB);

1032 return std::nullopt;

1034 }

1035

1039}

1040

1041std::optional

1042LazyValueInfoImpl::solveBlockValueInsertElement(InsertElementInst *IEI,

1044 std::optional OptEltVal =

1045 getBlockValue(IEI->getOperand(1), BB, IEI);

1046 if (!OptEltVal)

1047 return std::nullopt;

1049

1050 std::optional OptVecVal =

1051 getBlockValue(IEI->getOperand(0), BB, IEI);

1052 if (!OptVecVal)

1053 return std::nullopt;

1054

1055

1056

1057

1058

1059 if (OptEltVal->isConstant())

1061

1062 Res.mergeIn(*OptVecVal);

1063 return Res;

1064}

1065

1066std::optional

1067LazyValueInfoImpl::solveBlockValueExtractValue(ExtractValueInst *EVI,

1071 return solveBlockValueOverflowIntrinsic(WO, BB);

1072

1073

1074

1078 return getBlockValue(V, BB, EVI);

1079

1081 << "' - overdefined (unknown extractvalue).\n");

1083}

1084

1087 if (LHS == Val)

1088 return true;

1089

1090

1091

1095 return true;

1096 }

1097

1098

1099

1102 return true;

1103 }

1104

1105

1108 return true;

1109

1110

1113 return true;

1114

1115 return false;

1116}

1117

1118

1119std::optional

1120LazyValueInfoImpl::getValueFromSimpleICmpCondition(CmpInst::Predicate Pred,

1124 bool UseBlockValue) {

1126 true);

1127 if (ConstantInt *CI = dyn_cast(RHS)) {

1129 } else if (UseBlockValue) {

1130 std::optional R =

1131 getBlockValue(RHS, CxtI->getParent(), CxtI);

1132 if (!R)

1133 return std::nullopt;

1134 RHSRange = R->asConstantRange(RHS->getType());

1135 }

1136

1140}

1141

1142static std::optional

1145 bool Invert = false;

1148 Invert = true;

1149 }

1152 if (RHS.isMaxSignedValue())

1153 return std::nullopt;

1155 }

1157 if (auto CR = Fn(RHS))

1158 return Invert ? CR->inverse() : CR;

1159 return std::nullopt;

1160}

1161

1162

1166

1167 auto *RHSConst = dyn_cast(RHS);

1168 if (!RHSConst)

1170

1173

1176

1181}

1182

1183std::optional LazyValueInfoImpl::getValueFromICmpCondition(

1184 Value *Val, ICmpInst *ICI, bool isTrueDest, bool UseBlockValue) {

1187

1188

1191

1192 if (isa(RHS)) {

1193 if (ICI->isEquality() && LHS == Val) {

1196 else if (!isa(RHS))

1198 }

1199 }

1200

1204

1208 return getValueFromSimpleICmpCondition(EdgePred, RHS, Offset, ICI,

1209 UseBlockValue);

1210

1213 return getValueFromSimpleICmpCondition(SwappedPred, LHS, Offset, ICI,

1214 UseBlockValue);

1215

1216 if (match(LHS, m_IntrinsicIntrinsic::ctpop(m_Specific(Val))))

1218

1222

1223

1230 }

1231

1235 }

1236

1237

1238

1239

1243

1248 }

1249

1250

1251

1252

1253 const APInt *ShAmtC;

1258 EdgePred, *C, [&](const APInt &RHS) -> std::optional {

1260 if ((New.ashr(*ShAmtC)) != RHS)

1261 return std::nullopt;

1264 });

1265 if (CR)

1267 }

1268

1269

1272

1275 if ((X == LHS && Y == RHS) || (X == RHS && Y == LHS)) {

1280 }

1281 }

1282

1284}

1285

1286

1287

1290

1291

1292

1296

1297

1300

1301

1302

1303 if (IsTrueDest)

1306}

1307

1308std::optional

1309LazyValueInfoImpl::getValueFromCondition(Value *Val, Value *Cond,

1310 bool IsTrueDest, bool UseBlockValue,

1311 unsigned Depth) {

1312 if (ICmpInst *ICI = dyn_cast(Cond))

1313 return getValueFromICmpCondition(Val, ICI, IsTrueDest, UseBlockValue);

1314

1315 if (auto *EVI = dyn_cast(Cond))

1319

1322

1325 return getValueFromCondition(Val, N, !IsTrueDest, UseBlockValue, Depth);

1326

1328 bool IsAnd;

1330 IsAnd = true;

1332 IsAnd = false;

1333 else

1335

1336 std::optional LV =

1337 getValueFromCondition(Val, L, IsTrueDest, UseBlockValue, Depth);

1338 if (!LV)

1339 return std::nullopt;

1340 std::optional RV =

1341 getValueFromCondition(Val, R, IsTrueDest, UseBlockValue, Depth);

1342 if (!RV)

1343 return std::nullopt;

1344

1345

1346

1347

1348

1349 if (IsTrueDest ^ IsAnd) {

1350 LV->mergeIn(*RV);

1351 return *LV;

1352 }

1353

1354 return LV->intersect(*RV);

1355}

1356

1357

1360}

1361

1362

1363

1364

1365

1367 return isa(Usr) || isa(Usr) || isa(Usr);

1368}

1369

1370

1371

1372

1373

1375 const APInt &OpConstVal,

1379

1380 if (auto *CI = dyn_cast(Usr)) {

1382 if (auto *C = dyn_cast_or_null(

1386 }

1387 } else if (auto *BO = dyn_cast(Usr)) {

1390 assert((Op0Match || Op1Match) &&

1391 "Operand 0 nor Operand 1 isn't a match");

1394 if (auto *C = dyn_cast_or_null(

1397 }

1398 } else if (isa(Usr)) {

1399 assert(cast(Usr)->getOperand(0) == Op && "Operand 0 isn't Op");

1401 }

1403}

1404

1405

1406std::optional

1407LazyValueInfoImpl::getEdgeValueLocal(Value *Val, BasicBlock *BBFrom,

1408 BasicBlock *BBTo, bool UseBlockValue) {

1409

1410

1412

1413

1414 if (BI->isConditional() &&

1415 BI->getSuccessor(0) != BI->getSuccessor(1)) {

1416 bool isTrueDest = BI->getSuccessor(0) == BBTo;

1417 assert(BI->getSuccessor(!isTrueDest) == BBTo &&

1418 "BBTo isn't a successor of BBFrom");

1419 Value *Condition = BI->getCondition();

1420

1421

1422

1423

1424 if (Condition == Val)

1427

1428

1429

1430 std::optional Result =

1431 getValueFromCondition(Val, Condition, isTrueDest, UseBlockValue);

1432 if (!Result)

1433 return std::nullopt;

1434

1435 if ( Result ->isOverdefined())

1437

1438 if (User *Usr = dyn_cast(Val)) {

1439 assert(Result->isOverdefined() && "Result isn't overdefined");

1440

1441

1442

1446

1447

1448

1449

1450

1451

1452

1453 APInt ConditionVal(1, isTrueDest ? 1 : 0);

1455 } else {

1456

1457

1458

1459

1460

1461

1462

1463 for (unsigned i = 0; i < Usr->getNumOperands(); ++i) {

1464 Value *Op = Usr->getOperand(i);

1466 Op, Condition, isTrueDest, false);

1467 if (std::optional OpConst =

1470 break;

1471 }

1472 }

1473 }

1474 }

1475 }

1476 if ( Result ->isOverdefined())

1478 }

1479 }

1480

1481

1482

1484 Value *Condition = SI->getCondition();

1485 if (!isa(Val->getType()))

1487 bool ValUsesConditionAndMayBeFoldable = false;

1488 if (Condition != Val) {

1489

1490 if (User *Usr = dyn_cast(Val))

1493 if (!ValUsesConditionAndMayBeFoldable)

1495 }

1496 assert((Condition == Val || ValUsesConditionAndMayBeFoldable) &&

1497 "Condition != Val nor Val doesn't use Condition");

1498

1499 bool DefaultCase = SI->getDefaultDest() == BBTo;

1502

1503 for (auto Case : SI->cases()) {

1504 APInt CaseValue = Case.getCaseValue()->getValue();

1506 if (ValUsesConditionAndMayBeFoldable) {

1507 User *Usr = cast(Val);

1514 }

1515 if (DefaultCase) {

1516

1517

1518

1519

1520

1521

1522 if (Case.getCaseSuccessor() != BBTo && Condition == Val)

1523 EdgesVals = EdgesVals.difference(EdgeVal);

1524 } else if (Case.getCaseSuccessor() == BBTo)

1525 EdgesVals = EdgesVals.unionWith(EdgeVal);

1526 }

1528 }

1530}

1531

1532

1533

1534std::optional

1535LazyValueInfoImpl::getEdgeValue(Value *Val, BasicBlock *BBFrom,

1537

1538 if (Constant *VC = dyn_cast(Val))

1540

1541 std::optional LocalResult =

1542 getEdgeValueLocal(Val, BBFrom, BBTo, true);

1543 if (!LocalResult)

1544 return std::nullopt;

1545

1547

1548 return LocalResult;

1549

1550 std::optional OptInBlock =

1551 getBlockValue(Val, BBFrom, BBFrom->getTerminator());

1552 if (!OptInBlock)

1553 return std::nullopt;

1555

1556

1557

1558

1559

1560

1561

1562

1563

1564 intersectAssumeOrGuardBlockValueConstantRange(Val, InBlock, CxtI);

1565

1566 return LocalResult->intersect(InBlock);

1567}

1568

1571 LLVM_DEBUG(dbgs() << "LVI Getting block end value " << *V << " at '"

1572 << BB->getName() << "'\n");

1573

1574 assert(BlockValueStack.empty() && BlockValueSet.empty());

1575 std::optional OptResult = getBlockValue(V, BB, CxtI);

1576 if (!OptResult) {

1577 solve();

1578 OptResult = getBlockValue(V, BB, CxtI);

1579 assert(OptResult && "Value not available after solving");

1580 }

1581

1583 LLVM_DEBUG(dbgs() << " Result = " << Result << "\n");

1584 return Result;

1585}

1586

1589 << "'\n");

1590

1591 if (auto *C = dyn_cast(V))

1593

1595 if (auto *I = dyn_cast(V))

1597 intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI);

1598

1599 LLVM_DEBUG(dbgs() << " Result = " << Result << "\n");

1600 return Result;

1601}

1602

1606 LLVM_DEBUG(dbgs() << "LVI Getting edge value " << *V << " from '"

1608 << "'\n");

1609

1610 std::optional Result =

1611 getEdgeValue(V, FromBB, ToBB, CxtI);

1612 while (!Result) {

1613

1614

1615

1616 solve();

1617 Result = getEdgeValue(V, FromBB, ToBB, CxtI);

1618 }

1619

1620 LLVM_DEBUG(dbgs() << " Result = " << *Result << "\n");

1621 return *Result;

1622}

1623

1625 Value *V = U.get();

1626 auto *CxtI = cast(U.getUser());

1628

1629

1630

1631 const Use *CurrU = &U;

1632

1633 const unsigned MaxUsesToInspect = 3;

1634 for (unsigned I = 0; I < MaxUsesToInspect; ++I) {

1635 std::optional CondVal;

1636 auto *CurrI = cast(CurrU->getUser());

1637 if (auto *SI = dyn_cast(CurrI)) {

1638

1639

1641 break;

1642 if (CurrU->getOperandNo() == 1)

1643 CondVal =

1644 *getValueFromCondition(V, SI->getCondition(), true,

1645 false);

1646 else if (CurrU->getOperandNo() == 2)

1647 CondVal =

1648 *getValueFromCondition(V, SI->getCondition(), false,

1649 false);

1650 } else if (auto *PHI = dyn_cast(CurrI)) {

1651

1652 CondVal = *getEdgeValueLocal(V, PHI->getIncomingBlock(*CurrU),

1653 PHI->getParent(), false);

1654 }

1655 if (CondVal)

1657

1658

1659

1660

1661

1662

1663

1664

1665

1666

1667 if (!CurrI->hasOneUse() ||

1669 break;

1671 }

1672 return VL;

1673}

1674

1677 TheCache.threadEdgeImpl(OldSucc, NewSucc);

1678}

1679

1680

1681

1682

1683

1685 Info.AC = &getAnalysis().getAssumptionCache(F);

1686

1687 if (auto *Impl = Info.getImpl())

1689

1690

1691 return false;

1692}

1693

1698}

1699

1701

1702

1704 if (!PImpl) {

1705 assert(M && "getCache() called with a null Module");

1710 }

1712}

1713

1715 if (!PImpl)

1716 return nullptr;

1718}

1719

1721

1723

1724 if (auto *Impl = getImpl()) {

1725 delete &*Impl;

1726 PImpl = nullptr;

1727 }

1728}

1729

1732

1733

1736 return true;

1737

1738 return false;

1739}

1740

1742

1746

1748}

1749

1750

1751

1752

1753

1754

1755

1757 V = V->stripPointerCasts();

1758

1759 if (isa(V))

1760 return true;

1761 return false;

1762}

1763

1765

1767 return nullptr;

1768

1772

1773 if (Result.isConstant())

1774 return Result.getConstant();

1775 if (Result.isConstantRange()) {

1776 const ConstantRange &CR = Result.getConstantRange();

1778 return ConstantInt::get(V->getType(), *SingleVal);

1779 }

1780 return nullptr;

1781}

1782

1784 bool UndefAllowed) {

1788 return Result.asConstantRange(V->getType(), UndefAllowed);

1789}

1790

1792 bool UndefAllowed) {

1793 auto *Inst = cast(U.getUser());

1795 getOrCreateImpl(Inst->getModule()).getValueAtUse(U);

1796 return Result.asConstantRange(U->getType(), UndefAllowed);

1797}

1798

1799

1800

1806 getOrCreateImpl(M).getValueOnEdge(V, FromBB, ToBB, CxtI);

1807

1808 if (Result.isConstant())

1809 return Result.getConstant();

1810 if (Result.isConstantRange()) {

1811 const ConstantRange &CR = Result.getConstantRange();

1813 return ConstantInt::get(V->getType(), *SingleVal);

1814 }

1815 return nullptr;

1816}

1817

1824 getOrCreateImpl(M).getValueOnEdge(V, FromBB, ToBB, CxtI);

1825

1826 return Result.asConstantRange(V->getType(), true);

1827}

1828

1832

1835

1844 return nullptr;

1845 }

1846

1848

1849

1851

1857

1862 }

1863 return nullptr;

1864 }

1865

1866 return nullptr;

1867}

1868

1869

1870

1877 getOrCreateImpl(M).getValueOnEdge(V, FromBB, ToBB, CxtI);

1878

1880}

1881

1884 bool UseBlockValue) {

1885

1886

1887

1888

1891 if (V->getType()->isPointerTy() && C->isNullValue() &&

1892 isKnownNonZero(V->stripPointerCastsSameRepresentation(), DL)) {

1898 }

1899

1900 auto &Impl = getOrCreateImpl(M);

1902 UseBlockValue ? Impl.getValueInBlock(V, CxtI->getParent(), CxtI)

1903 : Impl.getValueAt(V, CxtI);

1905 if (Ret)

1906 return Ret;

1907

1908

1909

1910

1911

1912

1913

1914

1915

1916

1917

1918

1919

1920

1921

1922

1923

1924

1925

1926

1927

1928

1929

1931

1932

1933

1935 if (PI == PE)

1936 return nullptr;

1937

1938

1939

1940

1941

1942 if (auto *PHI = dyn_cast(V))

1943 if (PHI->getParent() == BB) {

1944 Constant *Baseline = nullptr;

1945 for (unsigned i = 0, e = PHI->getNumIncomingValues(); i < e; i++) {

1948

1951

1952

1953

1954 Baseline = (i == 0) ? Result

1955 : (Baseline == Result ? Baseline

1956 : nullptr);

1957 if (!Baseline)

1958 break;

1959 }

1960 if (Baseline)

1961 return Baseline;

1962 }

1963

1964

1965

1966

1967 if (!isa(V) || cast(V)->getParent() != BB) {

1968

1969

1970

1972 if (Baseline) {

1973

1974 while (++PI != PE) {

1976 if (Ret != Baseline)

1977 break;

1978 }

1979

1980 if (PI == PE) {

1981 return Baseline;

1982 }

1983 }

1984 }

1985

1986 return nullptr;

1987}

1988

1991 bool UseBlockValue) {

1992 if (auto *C = dyn_cast(RHS))

1994 if (auto *C = dyn_cast(LHS))

1996 UseBlockValue);

1997

1998

1999

2000

2001 if (UseBlockValue) {

2005 if (L.isOverdefined())

2006 return nullptr;

2007

2011 return L.getCompare(Pred, Ty, R, M->getDataLayout());

2012 }

2013 return nullptr;

2014}

2015

2018 if (auto *Impl = getImpl())

2019 Impl->threadEdge(PredBB, OldSucc, NewSucc);

2020}

2021

2023 if (auto *Impl = getImpl())

2024 Impl->forgetValue(V);

2025}

2026

2028 if (auto *Impl = getImpl())

2029 Impl->eraseBlock(BB);

2030}

2031

2033 if (auto *Impl = getImpl())

2034 Impl->clear();

2035}

2036

2038 if (auto *Impl = getImpl())

2039 Impl->printLVI(F, DTree, OS);

2040}

2041

2042

2043void LazyValueInfoAnnotatedWriter::emitBasicBlockStartAnnot(

2045

2047 for (const auto &Arg : F->args()) {

2050 if (Result.isUnknown())

2051 continue;

2052 OS << "; LatticeVal for: '" << Arg << "' is: " << Result << "\n";

2053 }

2054}

2055

2056

2057

2058

2059

2060void LazyValueInfoAnnotatedWriter::emitInstructionAnnot(

2062

2063 auto *ParentBB = I->getParent();

2065

2066

2067

2068

2069

2070 auto printResult = [&](const BasicBlock *BB) {

2071 if (!BlocksContainingLVI.insert(BB).second)

2072 return;

2075 OS << "; LatticeVal for: '" << *I << "' in BB: '";

2077 OS << "' is: " << Result << "\n";

2078 };

2079

2080 printResult(ParentBB);

2081

2082

2083 for (const auto *BBSucc : successors(ParentBB))

2084 if (DT.dominates(ParentBB, BBSucc))

2085 printResult(BBSucc);

2086

2087

2088 for (const auto *U : I->users())

2089 if (auto *UseI = dyn_cast(U))

2090 if (!isa(UseI) || DT.dominates(ParentBB, UseI->getParent()))

2091 printResult(UseI->getParent());

2092

2093}

2094

2097 OS << "LVI for function '" << F.getName() << "':\n";

2100 LVI.printLVI(F, DTree, OS);

2102}

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

block Block Frequency Analysis

This file contains the declarations for the subclasses of Constant, which represent the different fla...

Given that RA is a live value

This file defines the DenseSet and SmallDenseSet classes.

static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")

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

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

static std::optional< ConstantRange > getRange(Value *V, const InstrInfoQuery &IIQ)

Helper method to get range from metadata or attribute.

static bool isOperationFoldable(User *Usr)

static void AddNonNullPointersByInstruction(Instruction *I, NonNullPointerSet &PtrSet)

static std::optional< ConstantRange > getRangeViaSLT(CmpInst::Predicate Pred, APInt RHS, function_ref< std::optional< ConstantRange >(const APInt &)> Fn)

static const unsigned MaxProcessedPerValue

static ValueLatticeElement getValueFromICmpCtpop(ICmpInst::Predicate Pred, Value *RHS)

Get value range for a "ctpop(Val) Pred RHS" condition.

static bool usesOperand(User *Usr, Value *Op)

static ValueLatticeElement constantFoldUser(User *Usr, Value *Op, const APInt &OpConstVal, const DataLayout &DL)

static void AddNonNullPointer(Value *Ptr, NonNullPointerSet &PtrSet)

static ValueLatticeElement getFromRangeMetadata(Instruction *BBI)

static Constant * getPredicateResult(CmpInst::Predicate Pred, Constant *C, const ValueLatticeElement &Val, const DataLayout &DL)

static ValueLatticeElement getValueFromOverflowCondition(Value *Val, WithOverflowInst *WO, bool IsTrueDest)

static bool isKnownNonConstant(Value *V)

Returns true if we can statically tell that this value will never be a "useful" constant.

static bool matchICmpOperand(APInt &Offset, Value *LHS, Value *Val, ICmpInst::Predicate Pred)

ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))

uint64_t IntrinsicInst * II

static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")

FunctionAnalysisManager FAM

#define INITIALIZE_PASS_DEPENDENCY(depName)

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

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

const SmallVectorImpl< MachineOperand > & Cond

assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())

static bool InBlock(const Value *V, const BasicBlock *BB)

Class for arbitrary precision integers.

APInt zext(unsigned width) const

Zero extend to a new width.

static APInt getSignedMinValue(unsigned numBits)

Gets minimum signed value of APInt for a specific bit width.

uint64_t getLimitedValue(uint64_t Limit=UINT64_MAX) const

If this value is smaller than the specified limit, return it, otherwise return the limit value.

static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)

Constructs an APInt value that has the bottom loBitsSet bits set.

static APInt getHighBitsSet(unsigned numBits, unsigned hiBitsSet)

Constructs an APInt value that has the top hiBitsSet bits set.

static APInt getZero(unsigned numBits)

Get the '0' value for the specified bit-width.

This templated class represents "all analyses that operate over " (e....

API to communicate dependencies between analyses during invalidation.

A container for analyses that lazily runs them and caches their results.

PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)

Get the result of an analysis pass for a given IR unit.

Represent the analysis usage information of a pass.

AnalysisUsage & addRequired()

void setPreservesAll()

Set by analyses that do not transform their input at all.

This class represents an incoming formal argument to a Function.

A function analysis which provides an AssumptionCache.

An immutable pass that tracks lazily created AssumptionCache objects.

A cache of @llvm.assume calls within a function.

void clear()

Clear the cache of @llvm.assume intrinsics for a function.

MutableArrayRef< ResultElem > assumptionsFor(const Value *V)

Access the list of assumptions which affect this value.

LLVM Basic Block Representation.

iterator begin()

Instruction iterator methods.

bool isEntryBlock() const

Return true if this is the entry block of the containing function.

const Function * getParent() const

Return the enclosing method, or null if none.

const DataLayout & getDataLayout() const

Get the data layout of the module this basic block belongs to.

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

const Instruction & back() const

const Module * getModule() const

Return the module owning the function this basic block belongs to, or nullptr if the function does no...

unsigned getNoWrapKind() const

Returns one of OBO::NoSignedWrap or OBO::NoUnsignedWrap.

Instruction::BinaryOps getBinaryOp() const

Returns the binary operation underlying the intrinsic.

BinaryOps getOpcode() const

Conditional or Unconditional Branch instruction.

Value handle with callbacks on RAUW and destruction.

This is the base class for all instructions that perform data casts.

Instruction::CastOps getOpcode() const

Return the opcode of this CastInst.

Type * getDestTy() const

Return the destination type, as a convenience.

static Type * makeCmpResultType(Type *opnd_type)

Create a result type for fcmp/icmp.

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.

This is the shared class of boolean and integer constants.

static ConstantInt * getTrue(LLVMContext &Context)

static ConstantInt * getFalse(LLVMContext &Context)

static ConstantPointerNull * get(PointerType *T)

Static factory methods - Return objects of the specified value.

This class represents a range of values.

ConstantRange subtract(const APInt &CI) const

Subtract the specified constant from the endpoints of this constant range.

const APInt * getSingleElement() const

If this set contains a single element, return it, otherwise return null.

static ConstantRange fromKnownBits(const KnownBits &Known, bool IsSigned)

Initialize a range based on a known bits constraint.

ConstantRange castOp(Instruction::CastOps CastOp, uint32_t BitWidth) const

Return a new range representing the possible values resulting from an application of the specified ca...

ConstantRange umin(const ConstantRange &Other) const

Return a new range representing the possible values resulting from an unsigned minimum of a value in ...

APInt getUnsignedMin() const

Return the smallest unsigned value contained in the ConstantRange.

ConstantRange difference(const ConstantRange &CR) const

Subtract the specified range from this range (aka relative complement of the sets).

bool icmp(CmpInst::Predicate Pred, const ConstantRange &Other) const

Does the predicate Pred hold between ranges this and Other? NOTE: false does not mean that inverse pr...

static ConstantRange intrinsic(Intrinsic::ID IntrinsicID, ArrayRef< ConstantRange > Ops)

Compute range of intrinsic result for the given operand ranges.

bool isEmptySet() const

Return true if this set contains no members.

ConstantRange abs(bool IntMinIsPoison=false) const

Calculate absolute value range.

static bool isIntrinsicSupported(Intrinsic::ID IntrinsicID)

Returns true if ConstantRange calculations are supported for intrinsic with IntrinsicID.

ConstantRange overflowingBinaryOp(Instruction::BinaryOps BinOp, const ConstantRange &Other, unsigned NoWrapKind) const

Return a new range representing the possible values resulting from an application of the specified ov...

bool isSingleElement() const

Return true if this set contains exactly one member.

ConstantRange umax(const ConstantRange &Other) const

Return a new range representing the possible values resulting from an unsigned maximum of a value in ...

static ConstantRange makeAllowedICmpRegion(CmpInst::Predicate Pred, const ConstantRange &Other)

Produce the smallest range such that all values that may satisfy the given predicate with any value c...

ConstantRange unionWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const

Return the range that results from the union of this range with another range.

static ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)

Produce the exact range such that all values in the returned range satisfy the given predicate with a...

ConstantRange inverse() const

Return a new range that is the logical not of the current set.

APInt getUnsignedMax() const

Return the largest unsigned value contained in the ConstantRange.

ConstantRange intersectWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const

Return the range that results from the intersection of this range with another range.

static ConstantRange makeMaskNotEqualRange(const APInt &Mask, const APInt &C)

Initialize a range containing all values X that satisfy (X & Mask) != C.

static ConstantRange getNonEmpty(APInt Lower, APInt Upper)

Create non-empty constant range with the given bounds.

ConstantRange smin(const ConstantRange &Other) const

Return a new range representing the possible values resulting from a signed minimum of a value in thi...

uint32_t getBitWidth() const

Get the bit width of this ConstantRange.

ConstantRange smax(const ConstantRange &Other) const

Return a new range representing the possible values resulting from a signed maximum of a value in thi...

ConstantRange binaryOp(Instruction::BinaryOps BinOp, const ConstantRange &Other) const

Return a new range representing the possible values resulting from an application of the specified bi...

static ConstantRange makeExactNoWrapRegion(Instruction::BinaryOps BinOp, const APInt &Other, unsigned NoWrapKind)

Produce the range that contains X if and only if "X BinOp Other" does not wrap.

This is an important base class in LLVM.

static Constant * getIntegerValue(Type *Ty, const APInt &V)

Return the value for an integer or pointer constant, or a vector thereof, with the given scalar value...

ConstantRange toConstantRange() const

Convert constant to an approximate constant range.

static Constant * getNullValue(Type *Ty)

Constructor to create a '0' constant of arbitrary type.

bool isNullValue() const

Return true if this is the value that would be returned by getNullValue.

This class represents an Operation in the Expression.

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

iterator find_as(const LookupKeyT &Val)

Alternate version of find() which allows a different, and possibly less expensive,...

std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)

Implements a dense probed hash-table based set.

Analysis pass which computes a DominatorTree.

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

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

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

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

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.

This instruction inserts a single (scalar) element into a VectorType value.

const Module * getModule() const

Return the module owning the function this instruction belongs to or nullptr it the function does not...

MDNode * getMetadata(unsigned KindID) const

Get the metadata of given kind attached to this Instruction.

unsigned getOpcode() const

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

const DataLayout & getDataLayout() const

Get the data layout of the module this instruction belongs to.

A wrapper class for inspecting calls to intrinsic functions.

Analysis to compute lazy value information.

Result run(Function &F, FunctionAnalysisManager &FAM)

ValueLatticeElement getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB, Instruction *CxtI=nullptr)

This is the query interface to determine the lattice value for the specified Value* that is true on t...

ValueLatticeElement getValueAt(Value *V, Instruction *CxtI)

This is the query interface to determine the lattice value for the specified Value* at the specified ...

void threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc, BasicBlock *NewSucc)

This is the update interface to inform the cache that an edge from PredBB to OldSucc has been threade...

void printLVI(Function &F, DominatorTree &DTree, raw_ostream &OS)

Printing the LazyValueInfo Analysis.

void forgetValue(Value *V)

This is part of the update interface to remove information related to this value from the cache.

void eraseBlock(BasicBlock *BB)

This is part of the update interface to inform the cache that a block has been deleted.

void clear()

Complete flush all previously computed values.

LazyValueInfoImpl(AssumptionCache *AC, const DataLayout &DL, Function *GuardDecl)

ValueLatticeElement getValueInBlock(Value *V, BasicBlock *BB, Instruction *CxtI=nullptr)

This is the query interface to determine the lattice value for the specified Value* at the context in...

ValueLatticeElement getValueAtUse(const Use &U)

PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

Wrapper around LazyValueInfo.

bool runOnFunction(Function &F) override

runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.

void releaseMemory() override

releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...

void getAnalysisUsage(AnalysisUsage &AU) const override

getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...

LazyValueInfoWrapperPass()

This pass computes, caches, and vends lazy value constraint information.

void eraseBlock(BasicBlock *BB)

Inform the analysis cache that we have erased a block.

ConstantRange getConstantRangeAtUse(const Use &U, bool UndefAllowed)

Return the ConstantRange constraint that is known to hold for the value at a specific use-site.

ConstantRange getConstantRange(Value *V, Instruction *CxtI, bool UndefAllowed)

Return the ConstantRange constraint that is known to hold for the specified value at the specified in...

void threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc, BasicBlock *NewSucc)

Inform the analysis cache that we have threaded an edge from PredBB to OldSucc to be from PredBB to N...

Constant * getPredicateOnEdge(CmpInst::Predicate Pred, Value *V, Constant *C, BasicBlock *FromBB, BasicBlock *ToBB, Instruction *CxtI=nullptr)

Determine whether the specified value comparison with a constant is known to be true or false on the ...

Constant * getConstantOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB, Instruction *CxtI=nullptr)

Determine whether the specified value is known to be a constant on the specified edge.

ConstantRange getConstantRangeOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB, Instruction *CxtI=nullptr)

Return the ConstantRage constraint that is known to hold for the specified value on the specified edg...

Constant * getConstant(Value *V, Instruction *CxtI)

Determine whether the specified value is known to be a constant at the specified instruction.

void printLVI(Function &F, DominatorTree &DTree, raw_ostream &OS)

Print the \LazyValueInfo Analysis.

void forgetValue(Value *V)

Remove information related to this value from the cache.

void clear()

Complete flush all previously computed values.

Constant * getPredicateAt(CmpInst::Predicate Pred, Value *V, Constant *C, Instruction *CxtI, bool UseBlockValue)

Determine whether the specified value comparison with a constant is known to be true or false at the ...

bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)

Handle invalidation events in the new pass manager.

An instruction for reading from memory.

This is the common base class for memset/memcpy/memmove.

This class wraps the llvm.memcpy/memmove intrinsics.

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

BasicBlock * getIncomingBlock(unsigned i) const

Return incoming basic block number i.

Value * getIncomingValue(unsigned i) const

Return incoming value number x.

unsigned getNumIncomingValues() const

Return the number of incoming edges.

static PassRegistry * getPassRegistry()

getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...

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.

PreservedAnalysisChecker getChecker() const

Build a checker for this PreservedAnalyses and the specified analysis type.

This class represents the LLVM 'select' instruction.

Implements a dense probed hash-table based set with some number of buckets stored inline.

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

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

SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.

void push_back(const T &Elt)

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

An instruction for storing to memory.

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

unsigned getIntegerBitWidth() const

bool isIntOrIntVectorTy() const

Return true if this is an integer type or a vector of integer types.

static IntegerType * getInt1Ty(LLVMContext &C)

unsigned getPointerAddressSpace() const

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

unsigned getScalarSizeInBits() const LLVM_READONLY

If this is a vector type, return the getPrimitiveSizeInBits value for the element type.

bool isSized(SmallPtrSetImpl< Type * > *Visited=nullptr) const

Return true if it makes sense to take the size of this type.

bool isIntegerTy() const

True if this is an instance of IntegerType.

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

Value * getOperand(unsigned i) const

This class represents lattice values for constants.

static ValueLatticeElement getRange(ConstantRange CR, bool MayIncludeUndef=false)

bool isOverdefined() const

static ValueLatticeElement getNot(Constant *C)

bool isNotConstant() const

std::optional< APInt > asConstantInteger() const

const ConstantRange & getConstantRange(bool UndefAllowed=true) const

Returns the constant range for this value.

bool isConstantRange(bool UndefAllowed=true) const

Returns true if this value is a constant range.

static ValueLatticeElement get(Constant *C)

Constant * getNotConstant() const

ValueLatticeElement intersect(const ValueLatticeElement &Other) const

Combine two sets of facts about the same value into a single set of facts.

Constant * getConstant() const

bool mergeIn(const ValueLatticeElement &RHS, MergeOptions Opts=MergeOptions())

Updates this object to approximate both this object and RHS.

static ValueLatticeElement getOverdefined()

LLVM Value Representation.

Type * getType() const

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

const Value * stripInBoundsOffsets(function_ref< void(const Value *)> Func=[](const Value *) {}) const

Strip off pointer casts and inbounds GEPs.

void printAsOperand(raw_ostream &O, bool PrintType=true, const Module *M=nullptr) const

Print the name of this Value out to the specified raw_ostream.

LLVMContext & getContext() const

All values hold a context through their type.

StringRef getName() const

Return a constant reference to the value's name.

Represents an op.with.overflow intrinsic.

std::pair< iterator, bool > insert(const ValueT &V)

iterator find_as(const LookupKeyT &Val)

Alternative version of find() which allows a different, and possibly less expensive,...

bool erase(const ValueT &V)

formatted_raw_ostream - A raw_ostream that wraps another one and keeps track of line and column posit...

An efficient, type-erasing, non-owning reference to a callable.

const ParentTy * getParent() const

self_iterator getIterator()

This class implements an extremely fast bulk output stream that can only output to a stream.

#define llvm_unreachable(msg)

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

constexpr std::underlying_type_t< E > Mask()

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

@ C

The default llvm calling convention, compatible with C.

Function * getDeclarationIfExists(Module *M, ID id, ArrayRef< Type * > Tys, FunctionType *FT=nullptr)

This version supports overloaded intrinsics.

BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)

PtrToIntSameSize_match< OpTy > m_PtrToIntSameSize(const DataLayout &DL, const OpTy &Op)

BinaryOp_match< LHS, RHS, Instruction::AShr > m_AShr(const LHS &L, const RHS &R)

BinaryOp_match< LHS, RHS, Instruction::URem > m_URem(const LHS &L, const RHS &R)

BinaryOp_match< LHS, RHS, Instruction::And, true > m_c_And(const LHS &L, const RHS &R)

Matches an And with LHS and RHS in either order.

CastInst_match< OpTy, TruncInst > m_Trunc(const OpTy &Op)

Matches Trunc.

bool match(Val *V, const Pattern &P)

specificval_ty m_Specific(const Value *V)

Match if we have a specific specified value.

auto m_LogicalOr()

Matches L || R where L and R are arbitrary values.

match_combine_or< BinaryOp_match< LHS, RHS, Instruction::Add >, DisjointOr_match< LHS, RHS > > m_AddLike(const LHS &L, const RHS &R)

Match either "add" or "or disjoint".

apint_match m_APInt(const APInt *&Res)

Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.

class_match< Value > m_Value()

Match an arbitrary value and ignore it.

auto m_LogicalAnd()

Matches L && R where L and R are arbitrary values.

BinaryOp_match< cst_pred_ty< is_all_ones >, ValTy, Instruction::Xor, true > m_Not(const ValTy &V)

Matches a 'Not' as 'xor V, -1' or 'xor -1, V'.

BinaryOp_match< LHS, RHS, Instruction::Or, true > m_c_Or(const LHS &L, const RHS &R)

Matches an Or with LHS and RHS in either order.

BinaryOp_match< LHS, RHS, Instruction::Sub > m_Sub(const LHS &L, const RHS &R)

match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)

Combine two pattern matchers matching L || R.

This is an optimization pass for GlobalISel generic memory operations.

bool isValidAssumeForContext(const Instruction *I, const Instruction *CxtI, const DominatorTree *DT=nullptr, bool AllowEphemerals=false)

Return true if it is valid to use the assumptions provided by an assume intrinsic,...

bool isSafeToSpeculativelyExecuteWithVariableReplaced(const Instruction *I)

Don't use information from its non-constant operands.

auto pred_end(const MachineBasicBlock *BB)

auto successors(const MachineBasicBlock *BB)

iterator_range< T > make_range(T x, T y)

Convenience function for iterating over sub-ranges.

void append_range(Container &C, Range &&R)

Wrapper function to append range R to container C.

const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=6)

This method strips off any GEP address adjustments, pointer casts or llvm.threadlocal....

Constant * ConstantFoldCompareInstOperands(unsigned Predicate, Constant *LHS, Constant *RHS, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, const Instruction *I=nullptr)

Attempt to constant fold a compare instruction (icmp/fcmp) with the specified operands.

bool isGuaranteedNotToBeUndef(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)

Returns true if V cannot be undef, but may be poison.

ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)

Parse out a conservative ConstantRange from !range metadata.

Value * simplifyCastInst(unsigned CastOpc, Value *Op, Type *Ty, const SimplifyQuery &Q)

Given operands for a CastInst, fold the result or return null.

FunctionPass * createLazyValueInfoPass()

createLazyValueInfoPass - This creates an instance of the LazyValueInfo pass.

constexpr unsigned MaxAnalysisRecursionDepth

@ SPF_ABS

Floating point maxnum.

@ SPF_NABS

Absolute value.

@ SPF_UMIN

Signed minimum.

@ SPF_UMAX

Signed maximum.

@ SPF_SMAX

Unsigned minimum.

SelectPatternResult matchSelectPattern(Value *V, Value *&LHS, Value *&RHS, Instruction::CastOps *CastOp=nullptr, unsigned Depth=0)

Pattern match integer [SU]MIN, [SU]MAX and ABS idioms, returning the kind and providing the out param...

bool NullPointerIsDefined(const Function *F, unsigned AS=0)

Check whether null pointer dereferencing is considered undefined behavior for a given function or an ...

raw_ostream & dbgs()

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

Value * simplifyExtractValueInst(Value *Agg, ArrayRef< unsigned > Idxs, const SimplifyQuery &Q)

Given operands for an ExtractValueInst, fold the result or return null.

bool isKnownNonZero(const Value *V, const SimplifyQuery &Q, unsigned Depth=0)

Return true if the given value is known to be non-zero when defined.

Value * simplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, const SimplifyQuery &Q)

Given operands for a BinaryOperator, fold the result or return null.

DWARFExpression::Operation Op

static bool hasSingleValue(const ValueLatticeElement &Val)

constexpr unsigned BitWidth

auto pred_begin(const MachineBasicBlock *BB)

auto predecessors(const MachineBasicBlock *BB)

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

Returns true if Element is found in Range.

void initializeLazyValueInfoWrapperPassPass(PassRegistry &)

A special type used by analysis passes to provide an address that identifies that particular analysis...

Incoming for lane maks phi as machine instruction, incoming register Reg and incoming block Block are...

SelectPatternFlavor Flavor

static bool isMinOrMax(SelectPatternFlavor SPF)

When implementing this min/max pattern as fcmp; select, does the fcmp have to be ordered?