LazyValueInfo.cpp Source File (original) (raw)

43#include

44using namespace llvm;

47#define DEBUG_TYPE "lazy-value-info"

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

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

63 "lvi-per-pred-ranges", cl::Hidden, cl::init(false),

64 cl::desc("Enable tracking of ranges for a value in a block for"

65 "each block predecessor (default = false)"));

67namespace llvm {

71}

82 return true;

85 return true;

86 return false;

87}

93namespace {

95 class LazyValueInfoCache;

96 struct LVIValueHandle final : public CallbackVH {

97 LazyValueInfoCache *Parent;

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

100 : CallbackVH(V), Parent(P) { }

101

102 void deleted() override;

103 void allUsesReplacedWith(Value *V) override {

104 deleted();

105 }

106 };

107}

108

109namespace {

111using BBLatticeElementMap =

113using PredecessorValueLatticeMap =

115

116

117

118class LazyValueInfoCache {

119

120

121

122

123 struct BlockCacheEntry {

124 SmallDenseMap<AssertingVH, ValueLatticeElement, 4> LatticeElements;

125 SmallDenseSet<AssertingVH, 4> OverDefined;

126

127

128 std::optional NonNullPointers;

129

130

131

132 std::optional PredecessorLatticeElements;

133 };

134

135

136 DenseMap<PoisoningVH, std::unique_ptr>

137 BlockCache;

138

139 DenseSet<LVIValueHandle, DenseMapInfo<Value *>> ValueHandles;

140

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

142 auto It = BlockCache.find_as(BB);

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

144 return nullptr;

145 return It->second.get();

146 }

147

148 BlockCacheEntry *getOrCreateBlockEntry(BasicBlock *BB) {

149 auto It = BlockCache.find_as(BB);

150 if (It == BlockCache.end()) {

151 std::unique_ptr BCE =

152 std::make_unique();

154 BCE->PredecessorLatticeElements =

155 std::make_optional();

156 It = BlockCache.insert({BB, std::move(BCE)}).first;

157 }

158

159 return It->second.get();

160 }

161

162 void addValueHandle(Value *Val) {

163 auto HandleIt = ValueHandles.find_as(Val);

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

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

166 }

167

168public:

169 void insertResult(Value *Val, BasicBlock *BB,

170 const ValueLatticeElement &Result) {

171 BlockCacheEntry *Entry = getOrCreateBlockEntry(BB);

172

173

174

175 if (Result.isOverdefined())

176 Entry->OverDefined.insert(Val);

177 else

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

179

180 addValueHandle(Val);

181 }

182

183 void insertPredecessorResults(Value *Val, BasicBlock *BB,

184 BBLatticeElementMap &PredLatticeElements) {

185 BlockCacheEntry *Entry = getOrCreateBlockEntry(BB);

186

187 Entry->PredecessorLatticeElements->insert({Val, PredLatticeElements});

188

189 addValueHandle(Val);

190 }

191

192 std::optional

193 getCachedPredecessorInfo(Value *V, BasicBlock *BB) const {

194 const BlockCacheEntry *Entry = getBlockEntry(BB);

195 if (!Entry)

196 return std::nullopt;

197

198 auto LatticeIt = Entry->PredecessorLatticeElements->find_as(V);

199 if (LatticeIt == Entry->PredecessorLatticeElements->end())

200 return std::nullopt;

201

202 return LatticeIt->second;

203 }

204

205 std::optional getCachedValueInfo(Value *V,

206 BasicBlock *BB) const {

207 const BlockCacheEntry *Entry = getBlockEntry(BB);

208 if (!Entry)

209 return std::nullopt;

210

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

213

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

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

216 return std::nullopt;

217

218 return LatticeIt->second;

219 }

220

221 bool

222 isNonNullAtEndOfBlock(Value *V, BasicBlock *BB,

223 function_ref<NonNullPointerSet(BasicBlock *)> InitFn) {

224 BlockCacheEntry *Entry = getOrCreateBlockEntry(BB);

225 if ( Entry ->NonNullPointers) {

226 Entry->NonNullPointers = InitFn(BB);

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

228 addValueHandle(V);

229 }

230

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

232 }

233

234

235 void clear() {

236 BlockCache.clear();

237 ValueHandles.clear();

238 }

239

240

241 void eraseValue(Value *V);

242

243

244

245 void eraseBlock(BasicBlock *BB);

246

247

248

249

250 void threadEdgeImpl(BasicBlock *OldSucc, BasicBlock *NewSucc);

251};

252}

253

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

255 for (auto &Pair : BlockCache) {

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

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

258 if (Pair.second->NonNullPointers)

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

261 Pair.second->PredecessorLatticeElements->erase(V);

262 }

263

264 auto HandleIt = ValueHandles.find_as(V);

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

266 ValueHandles.erase(HandleIt);

267}

268

269void LVIValueHandle::deleted() {

270

271

272 Parent->eraseValue(*this);

273}

274

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

276

278 for (auto &Pair : BlockCache)

279 Pair.second->PredecessorLatticeElements->clear();

280 BlockCache.erase(BB);

281}

282

283void LazyValueInfoCache::threadEdgeImpl(BasicBlock *OldSucc,

285

286

287

288

289

290

291

292

293

294

295 std::vector<BasicBlock*> worklist;

296 worklist.push_back(OldSucc);

297

298 const BlockCacheEntry *Entry = getBlockEntry(OldSucc);

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

300 return;

302 Entry->OverDefined.end());

303

304

305

306

307

308 while (!worklist.empty()) {

309 BasicBlock *ToUpdate = worklist.back();

310 worklist.pop_back();

311

312

313 if (ToUpdate == NewSucc) continue;

314

315

316 auto OI = BlockCache.find_as(ToUpdate);

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

318 continue;

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

320

321 bool changed = false;

322 for (Value *V : ValsToClear) {

323 if (!ValueSet.erase(V))

324 continue;

325

326

327

328 changed = true;

329 }

330

331 if (!changed) continue;

332

334 }

335}

336

337namespace llvm {

338namespace {

339

340

342 LazyValueInfoImpl *LVIImpl;

343

344

345 DominatorTree &DT;

346

347public:

348 LazyValueInfoAnnotatedWriter(LazyValueInfoImpl *L, DominatorTree &DTree)

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

350

351 void emitBasicBlockStartAnnot(const BasicBlock *BB,

352 formatted_raw_ostream &OS) override;

353

354 void emitInstructionAnnot(const Instruction *I,

355 formatted_raw_ostream &OS) override;

356};

357}

358

360

361

362 LazyValueInfoCache TheCache;

363

364

365

366

368

369

371

372

373

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

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

376 return false;

377

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

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

380 BlockValueStack.push_back(BV);

381 return true;

382 }

383

384 AssumptionCache *AC;

385 const DataLayout &DL;

386

387

388

390

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

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

396

397

398

399

401 std::optional solveBlockValueImpl(Value *Val,

403 std::optional solveBlockValueNonLocal(Value *Val,

405 std::optional solveBlockValuePHINode(PHINode *PN,

407 std::optional solveBlockValueSelect(SelectInst *S,

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

411 std::optional solveBlockValueBinaryOpImpl(

414 OpFn);

415 std::optional

417 std::optional solveBlockValueCast(CastInst *CI,

419 std::optional

421 std::optional solveBlockValueIntrinsic(IntrinsicInst *II,

423 std::optional

425 std::optional

428 void intersectAssumeOrGuardBlockValueConstantRange(Value *Val,

431

432 void solve();

433

434

435

436

437

438 std::optional

441 bool UseBlockValue);

442

443 std::optional

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

445 bool UseBlockValue);

447 bool IsTrueDest);

448

449 std::optional

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

451 bool UseBlockValue, unsigned Depth = 0);

452

453 std::optional getEdgeValueLocal(Value *Val,

456 bool UseBlockValue);

457

458public:

459

460

461

464

465

466

467

468

470

471

472

476

478

479

481 TheCache.clear();

482 }

483

484

486 LazyValueInfoAnnotatedWriter Writer(this, DTree);

487 F.print(OS, &Writer);

488 }

489

490

491

493

494

495

497 TheCache.eraseBlock(BB);

498 }

499

500

501

503

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

507};

508}

509

510void LazyValueInfoImpl::solve() {

512 BlockValueStack;

513

514 unsigned processedCount = 0;

515 while (!BlockValueStack.empty()) {

516 processedCount++;

517

518

519

520

521

522

523

524

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

528

529 while (!StartingStack.empty()) {

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

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

534 }

535 BlockValueSet.clear();

536 BlockValueStack.clear();

537 return;

538 }

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

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

541 unsigned StackSize = BlockValueStack.size();

542 (void) StackSize;

543

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

545

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

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

548#ifndef NDEBUG

549 std::optional BBLV =

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

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

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

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

555#endif

556

557 BlockValueStack.pop_back();

558 BlockValueSet.erase(e);

559 } else {

560

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

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

563 }

564 }

565}

566

567std::optional

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

570

573

574 if (std::optional OptLatticeVal =

575 TheCache.getCachedValueInfo(Val, BB)) {

576 intersectAssumeOrGuardBlockValueConstantRange(Val, *OptLatticeVal, CxtI);

577 return OptLatticeVal;

578 }

579

580

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

583

584

585 return std::nullopt;

586}

587

590 default:

591 break;

592 case Instruction::Call:

593 case Instruction::Invoke:

596 [[fallthrough]];

597 case Instruction::Load:

602 }

603 break;

604 };

605

607}

608

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

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

612 "Value should not be in cache");

613

614

615

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

617 if (!Res)

618

619 return false;

620

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

622 return true;

623}

624

625std::optional

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

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

629 return solveBlockValueNonLocal(Val, BB);

630

632 return solveBlockValuePHINode(PN, BB);

633

635 return solveBlockValueSelect(SI, BB);

636

637

638

639

640

641

642

643

644

645

649

652 return solveBlockValueCast(CI, BB);

653

655 return solveBlockValueBinaryOp(BO, BB);

656

658 return solveBlockValueInsertElement(IEI, BB);

659

661 return solveBlockValueExtractValue(EVI, BB);

662

664 return solveBlockValueIntrinsic(II, BB);

665 }

666

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

670}

671

673 bool IsDereferenced = true) {

674

678}

679

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

688

689

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

692

697 for (auto &U : CB->args()) {

698 if (U->getType()->isPointerTy() &&

699 CB->paramHasNonNullAttr(CB->getArgOperandNo(&U),

700 false))

702 }

703 }

704}

705

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

709 return false;

710

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

713 NonNullPointerSet NonNullPointers;

714 for (Instruction &I : *BB)

716 return NonNullPointers;

717 });

718}

719

720std::optional

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

722 ValueLatticeElement Result;

723

724

730 }

731

732

733

734

735

736

737

738

739

740

741 std::optional PredLatticeElements;

743 PredLatticeElements = std::make_optional();

745

746 if (Pred == BB)

747 continue;

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

749 if (!EdgeResult)

750

751 return std::nullopt;

752

753 Result.mergeIn(*EdgeResult);

754

755

756

757 if (Result.isOverdefined()) {

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

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

762 }

764 PredLatticeElements->insert({Pred, *EdgeResult});

765 }

766

768 TheCache.insertPredecessorResults(Val, BB, *PredLatticeElements);

769

770

773}

774

775std::optional

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

777 ValueLatticeElement Result;

778

779

780

781

782 std::optional PredLatticeElements;

784 PredLatticeElements = std::make_optional();

788

789

790

791 std::optional EdgeResult =

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

793 if (!EdgeResult)

794

795 return std::nullopt;

796

797 Result.mergeIn(*EdgeResult);

798

799

800

801 if (Result.isOverdefined()) {

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

804

806 }

807

809 PredLatticeElements->insert({PhiBB, *EdgeResult});

810 }

811

813 TheCache.insertPredecessorResults(PN, BB, *PredLatticeElements);

814

815

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

818}

819

820

821

822void LazyValueInfoImpl::intersectAssumeOrGuardBlockValueConstantRange(

825 if (!BBI)

826 return;

827

829 for (auto &AssumeVH : AC->assumptionsFor(Val)) {

830 if (!AssumeVH)

831 continue;

832

833

834

835

838 continue;

839

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

841 true,

842 false));

843 }

844

845

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

848 for (Instruction &I :

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

853 true,

854 false));

855 }

856 }

857

859

860

863 isNonNullAtEndOfBlock(Val, BB))

865 }

866}

867

868std::optional

870

871 std::optional OptTrueVal =

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

873 if (!OptTrueVal)

874 return std::nullopt;

875 ValueLatticeElement &TrueVal = *OptTrueVal;

876

877 std::optional OptFalseVal =

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

879 if (!OptFalseVal)

880 return std::nullopt;

881 ValueLatticeElement &FalseVal = *OptFalseVal;

882

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

884 const ConstantRange &TrueCR = TrueVal.asConstantRange(SI->getType());

885 const ConstantRange &FalseCR = FalseVal.asConstantRange(SI->getType());

889

890

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

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

894 ConstantRange ResultCR = [&]() {

895 switch (SPR.Flavor) {

896 default:

898 case SPF_SMIN:

899 return TrueCR.smin(FalseCR);

900 case SPF_UMIN:

901 return TrueCR.umin(FalseCR);

902 case SPF_SMAX:

903 return TrueCR.smax(FalseCR);

904 case SPF_UMAX:

905 return TrueCR.umax(FalseCR);

906 };

907 }();

909 ResultCR, TrueVal.isConstantRangeIncludingUndef() ||

910 FalseVal.isConstantRangeIncludingUndef());

911 }

912

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

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

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

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

920 }

921

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

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

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

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

930 }

931 }

932

933

934

935

937

938

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

942 true,

943 false));

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

946 false,

947 false));

948 }

949

950 TrueVal.mergeIn(FalseVal);

952}

953

954std::optional

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

957 if (!OptVal)

958 return std::nullopt;

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

960}

961

962std::optional

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

964

965

966

968 case Instruction::Trunc:

969 case Instruction::SExt:

970 case Instruction::ZExt:

971 break;

972 default:

973

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

977 }

978

979

980

981

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

983 if (!LHSRes)

984

985 return std::nullopt;

986 const ConstantRange &LHSRange = *LHSRes;

987

989

990

991

992

993 ConstantRange Res = ConstantRange::getEmpty(ResultBitWidth);

995 Res = LHSRange.truncate(ResultBitWidth, Trunc->getNoWrapKind());

996 else

998

1000}

1001

1002std::optional

1003LazyValueInfoImpl::solveBlockValueBinaryOpImpl(

1006 OpFn) {

1009

1010 auto ThreadBinOpOverSelect =

1011 [&](Value *X, const ConstantRange &CRX, SelectInst *Y,

1012 bool XIsLHS) -> std::optional {

1014

1016 if (!TrueC)

1017 return std::nullopt;

1019 if (!FalseC)

1020 return std::nullopt;

1022 return std::nullopt;

1023

1024 ConstantRange TrueX =

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

1026 false)

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

1028 ConstantRange FalseX =

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

1030 false)

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

1034

1035 if (XIsLHS)

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

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

1040 };

1041

1042

1043

1044

1045

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

1047 if (!LHSRes)

1048 return std::nullopt;

1049

1050

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

1053 return *Res;

1054 }

1055

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

1057 if (!RHSRes)

1058 return std::nullopt;

1059

1060

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

1063 return *Res;

1064 }

1065

1066 const ConstantRange &LHSRange = *LHSRes;

1067 const ConstantRange &RHSRange = *RHSRes;

1068

1069 std::optional MergedResult =

1071

1073 return MergedResult;

1074

1075 std::optional PredLHS =

1076 TheCache.getCachedPredecessorInfo(LHS, BB);

1077 if (!PredLHS)

1078 return MergedResult;

1079 std::optional PredRHS =

1080 TheCache.getCachedPredecessorInfo(RHS, BB);

1081 if (!PredRHS)

1082 return MergedResult;

1083

1084 const BBLatticeElementMap &LHSPredMap = *PredLHS;

1085 const BBLatticeElementMap &RHSPredMap = *PredRHS;

1086

1087 BBLatticeElementMap PredLatticeElements;

1088 ValueLatticeElement OverallPredResult;

1090 auto LHSIt = LHSPredMap.find_as(Pred);

1091 if (LHSIt == LHSPredMap.end())

1092 return MergedResult;

1093 const ValueLatticeElement &LHSFromPred = LHSIt->second;

1094 std::optional LHSFromPredRes =

1096 if (!LHSFromPredRes)

1097 return MergedResult;

1098

1099 auto RHSIt = RHSPredMap.find_as(Pred);

1100 if (RHSIt == RHSPredMap.end())

1101 return MergedResult;

1102 const ValueLatticeElement &RHSFromPred = RHSIt->second;

1103 std::optional RHSFromPredRes =

1105 if (!RHSFromPredRes)

1106 return MergedResult;

1107

1108 const ConstantRange &LHSFromPredRange = *LHSFromPredRes;

1109 const ConstantRange &RHSFromPredRange = *RHSFromPredRes;

1110 std::optional PredResult =

1112 if (!PredResult)

1113 return MergedResult;

1114 if (PredResult->isOverdefined()) {

1116 dbgs() << " pred BB '" << Pred->getName() << "' for BB '"

1118 << "' overdefined. Discarding all predecessor intervals.\n");

1119 return MergedResult;

1120 }

1121 PredLatticeElements.insert({Pred, *PredResult});

1122 OverallPredResult.mergeIn(*PredResult);

1123 }

1124

1125

1126

1127

1128 TheCache.insertPredecessorResults(I, BB, PredLatticeElements);

1129

1130 LLVM_DEBUG(dbgs() << " Using predecessor intervals, evaluated " << *I

1131 << " to: " << OverallPredResult << ".\n");

1132

1133 if (!MergedResult)

1134 return OverallPredResult;

1135

1136 LLVM_DEBUG(dbgs() << " Intersecting intervals for " << *I << ": "

1137 << OverallPredResult << " and " << MergedResult << ".\n");

1138 return MergedResult->intersect(OverallPredResult);

1139}

1140

1141std::optional

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

1146 unsigned NoWrapKind = OBO->getNoWrapKind();

1147 return solveBlockValueBinaryOpImpl(

1148 BO, BB,

1149 [BO, NoWrapKind](const ConstantRange &CR1, const ConstantRange &CR2) {

1151 });

1152 }

1153

1154 return solveBlockValueBinaryOpImpl(

1155 BO, BB, [BO](const ConstantRange &CR1, const ConstantRange &CR2) {

1157 });

1158}

1159

1160std::optional

1161LazyValueInfoImpl::solveBlockValueOverflowIntrinsic(WithOverflowInst *WO,

1163 return solveBlockValueBinaryOpImpl(

1164 WO, BB, [WO](const ConstantRange &CR1, const ConstantRange &CR2) {

1166 });

1167}

1168

1169std::optional

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

1175 return MetadataVal;

1176 }

1177

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

1182 return std::nullopt;

1184 }

1185

1189}

1190

1191std::optional

1192LazyValueInfoImpl::solveBlockValueInsertElement(InsertElementInst *IEI,

1194 std::optional OptEltVal =

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

1196 if (!OptEltVal)

1197 return std::nullopt;

1198 ValueLatticeElement &Res = *OptEltVal;

1199

1200 std::optional OptVecVal =

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

1202 if (!OptVecVal)

1203 return std::nullopt;

1204

1205

1206

1207

1208

1209 if (OptEltVal->isConstant())

1211

1212 Res.mergeIn(*OptVecVal);

1213 return Res;

1214}

1215

1216std::optional

1217LazyValueInfoImpl::solveBlockValueExtractValue(ExtractValueInst *EVI,

1221 return solveBlockValueOverflowIntrinsic(WO, BB);

1222

1223

1224

1228 return getBlockValue(V, BB, EVI);

1229

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

1233}

1234

1237 if (LHS == Val)

1238 return true;

1239

1240

1241

1245 return true;

1246 }

1247

1248

1249

1252 return true;

1253 }

1254

1255

1258 return true;

1259

1260

1263 return true;

1264

1265 return false;

1266}

1267

1268

1269std::optional

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

1274 bool UseBlockValue) {

1276 true);

1278 RHSRange = ConstantRange(CI->getValue());

1279 } else if (UseBlockValue) {

1280 std::optional R =

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

1282 if (!R)

1283 return std::nullopt;

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

1285 }

1286

1287 ConstantRange TrueValues =

1290}

1291

1292static std::optional

1295 bool Invert = false;

1298 Invert = true;

1299 }

1302 if (RHS.isMaxSignedValue())

1303 return std::nullopt;

1305 }

1307 if (auto CR = Fn(RHS))

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

1309 return std::nullopt;

1310}

1311

1312

1315 unsigned BitWidth = RHS->getType()->getScalarSizeInBits();

1316

1318 if (!RHSConst)

1320

1323

1326

1331}

1332

1333std::optional LazyValueInfoImpl::getValueFromICmpCondition(

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

1337

1338

1341

1348 }

1349 }

1350

1354

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

1359 UseBlockValue);

1360

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

1364 UseBlockValue);

1365

1368

1369 const APInt *Mask, *C;

1372

1373

1375 KnownBits Known;

1380 }

1381

1385 }

1386

1387

1388

1389

1393

1398 }

1399

1400

1401

1402

1403 const APInt *ShAmtC;

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

1409 APInt New = RHS << *ShAmtC;

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

1411 return std::nullopt;

1414 });

1415 if (CR)

1417 }

1418

1419

1422

1430 }

1431 }

1432

1434}

1435

1438 bool IsTrueDest) {

1440

1443

1445

1447 if (IsTrueDest)

1450 }

1451

1452 if (IsTrueDest)

1455}

1456

1457

1458

1461

1462

1463

1467

1468

1471

1472

1473

1474 if (IsTrueDest)

1477}

1478

1479std::optional

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

1481 bool IsTrueDest, bool UseBlockValue,

1482 unsigned Depth) {

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

1485

1487 return getValueFromTrunc(Val, Trunc, IsTrueDest);

1488

1493

1496

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

1500

1502 bool IsAnd;

1504 IsAnd = true;

1506 IsAnd = false;

1507 else

1509

1510 std::optional LV =

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

1512 if (!LV)

1513 return std::nullopt;

1514 std::optional RV =

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

1516 if (!RV)

1517 return std::nullopt;

1518

1519

1520

1521

1522

1523 if (IsTrueDest ^ IsAnd) {

1524 LV->mergeIn(*RV);

1525 return *LV;

1526 }

1527

1528 return LV->intersect(*RV);

1529}

1530

1531

1535

1536

1537

1538

1539

1543

1544

1545

1546

1547

1549 const APInt &OpConstVal,

1553

1560 }

1564 assert((Op0Match || Op1Match) &&

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

1571 }

1575 }

1577}

1578

1579

1580std::optional

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

1582 BasicBlock *BBTo, bool UseBlockValue) {

1583

1584

1586

1587

1588 if (BI->isConditional() &&

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

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

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

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

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

1594

1595

1596

1597

1598 if (Condition == Val)

1601

1602

1603

1604 std::optional Result =

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

1606 if (!Result)

1607 return std::nullopt;

1608

1609 if ( Result ->isOverdefined())

1611

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

1614

1615

1616

1620

1621

1622

1623

1624

1625

1626

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

1630 ValueLatticeElement OpLatticeVal =

1631 *getValueFromCondition(Usr->getOperand(0), Condition,

1632 isTrueDest, false);

1633

1635 const unsigned ResultBitWidth =

1636 Usr->getType()->getScalarSizeInBits();

1641

1645 }

1651 }

1653 } else {

1654

1655

1656

1657

1658

1659

1660

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

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

1663 ValueLatticeElement OpLatticeVal = *getValueFromCondition(

1664 Op, Condition, isTrueDest, false);

1665 if (std::optional OpConst =

1668 break;

1669 }

1670 }

1671 }

1672 }

1673 }

1674 if ( Result ->isOverdefined())

1676 }

1677 }

1678

1679

1680

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

1685 bool ValUsesConditionAndMayBeFoldable = false;

1686 if (Condition != Val) {

1687

1691 if (!ValUsesConditionAndMayBeFoldable)

1693 }

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

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

1696

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

1699 ConstantRange EdgesVals(BitWidth, DefaultCase);

1700

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

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

1703 ConstantRange EdgeVal(CaseValue);

1704 if (ValUsesConditionAndMayBeFoldable) {

1707 ValueLatticeElement EdgeLatticeVal =

1712 }

1713 if (DefaultCase) {

1714

1715

1716

1717

1718

1719

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

1721 EdgesVals = EdgesVals.difference(EdgeVal);

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

1723 EdgesVals = EdgesVals.unionWith(EdgeVal);

1724 }

1726 }

1728}

1729

1730

1731

1732std::optional

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

1735

1738

1739 std::optional LocalResult =

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

1741 if (!LocalResult)

1742 return std::nullopt;

1743

1745

1746 return LocalResult;

1747

1748 std::optional OptInBlock =

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

1750 if (!OptInBlock)

1751 return std::nullopt;

1752 ValueLatticeElement &InBlock = *OptInBlock;

1753

1754

1755

1756

1757

1758

1759

1760

1761

1762 intersectAssumeOrGuardBlockValueConstantRange(Val, InBlock, CxtI);

1763

1764 return LocalResult->intersect(InBlock);

1765}

1766

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

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

1771

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

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

1774 if (!OptResult) {

1775 solve();

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

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

1778 }

1779

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

1781 return *OptResult;

1782}

1783

1786 << "'\n");

1787

1790

1794 intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI);

1795

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

1797 return Result;

1798}

1799

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

1805 << "'\n");

1806

1807 std::optional Result =

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

1809 while (!Result) {

1810

1811

1812

1813 solve();

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

1815 }

1816

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

1818 return *Result;

1819}

1820

1822 Value *V = U.get();

1825

1826

1827

1828 const Use *CurrU = &U;

1829

1830 const unsigned MaxUsesToInspect = 3;

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

1832 std::optional CondVal;

1835

1836

1838 break;

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

1840 CondVal =

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

1842 false);

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

1844 CondVal =

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

1846 false);

1848

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

1850 PHI->getParent(), false);

1851 }

1852 if (CondVal)

1854

1855

1856

1857

1858

1859

1860

1861

1862

1863

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

1866 CurrI, false))

1867 break;

1869 }

1870 return VL;

1871}

1872

1875 TheCache.threadEdgeImpl(OldSucc, NewSucc);

1876}

1877

1878

1879

1880

1881

1884

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

1886 Impl->clear();

1887

1888

1889 return false;

1890}

1891

1897

1899

1900

1902 if (!PImpl) {

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

1908 }

1909 return *PImpl;

1910}

1911

1913

1915

1917

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

1919 delete &*Impl;

1920 PImpl = nullptr;

1921 }

1922}

1923

1925 FunctionAnalysisManager::Invalidator &Inv) {

1926

1927

1930 return true;

1931

1932 return false;

1933}

1934

1936

1943

1944

1945

1946

1947

1948

1949

1951 V = V->stripPointerCasts();

1952

1954 return true;

1955 return false;

1956}

1957

1959

1961 return nullptr;

1962

1965 getOrCreateImpl(BB->getModule()).getValueInBlock(V, BB, CxtI);

1966

1967 if (Result.isConstant())

1968 return Result.getConstant();

1969 if (Result.isConstantRange()) {

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

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

1973 }

1974 return nullptr;

1975}

1976

1978 bool UndefAllowed) {

1981 getOrCreateImpl(BB->getModule()).getValueInBlock(V, BB, CxtI);

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

1983}

1984

1986 bool UndefAllowed) {

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

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

1991}

1992

1993

1994

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

2001

2002 if (Result.isConstant())

2003 return Result.getConstant();

2004 if (Result.isConstantRange()) {

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

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

2008 }

2009 return nullptr;

2010}

2011

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

2019

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

2021}

2022

2026

2029

2038 return nullptr;

2039 }

2040

2042

2043

2045

2051

2056 }

2057 return nullptr;

2058 }

2059

2060 return nullptr;

2061}

2062

2063

2064

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

2072

2074}

2075

2078 bool UseBlockValue) {

2079

2080

2081

2082

2084 const DataLayout &DL = M->getDataLayout();

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

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

2092 }

2093

2094 auto &Impl = getOrCreateImpl(M);

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

2097 : Impl.getValueAt(V, CxtI);

2099 if (Ret)

2100 return Ret;

2101

2102

2103

2104

2105

2106

2107

2108

2109

2110

2111

2112

2113

2114

2115

2116

2117

2118

2119

2120

2121

2122

2123

2125

2126

2127

2129 if (PI == PE)

2130 return nullptr;

2131

2132

2133

2134

2135

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

2138 Constant *Baseline = nullptr;

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

2142

2145

2146

2147

2148 Baseline = (i == 0) ? Result

2149 : (Baseline == Result ? Baseline

2150 : nullptr);

2151 if (!Baseline)

2152 break;

2153 }

2154 if (Baseline)

2155 return Baseline;

2156 }

2157

2158

2159

2160

2162

2163

2164

2166 if (Baseline) {

2167

2168 while (++PI != PE) {

2170 if (Ret != Baseline)

2171 break;

2172 }

2173

2174 if (PI == PE) {

2175 return Baseline;

2176 }

2177 }

2178 }

2179

2180 return nullptr;

2181}

2182

2185 bool UseBlockValue) {

2187 return getPredicateAt(Pred, LHS, C, CxtI, UseBlockValue);

2190 UseBlockValue);

2191

2192

2193

2194

2195 if (UseBlockValue) {

2198 getOrCreateImpl(M).getValueInBlock(LHS, CxtI->getParent(), CxtI);

2199 if (L.isOverdefined())

2200 return nullptr;

2201

2203 getOrCreateImpl(M).getValueInBlock(RHS, CxtI->getParent(), CxtI);

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

2206 }

2207 return nullptr;

2208}

2209

2212 if (auto *Impl = getImpl())

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

2214}

2215

2217 if (auto *Impl = getImpl())

2218 Impl->forgetValue(V);

2219}

2220

2222 if (auto *Impl = getImpl())

2223 Impl->eraseBlock(BB);

2224}

2225

2227 if (auto *Impl = getImpl())

2228 Impl->clear();

2229}

2230

2232 if (auto *Impl = getImpl())

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

2234}

2235

2236

2237void LazyValueInfoAnnotatedWriter::emitBasicBlockStartAnnot(

2239

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

2244 if (Result.isUnknown())

2245 continue;

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

2247 }

2248}

2249

2250

2251

2252

2253

2254void LazyValueInfoAnnotatedWriter::emitInstructionAnnot(

2255 const Instruction *I, formatted_raw_ostream &OS) {

2256

2258 SmallPtrSet<const BasicBlock*, 16> BlocksContainingLVI;

2259

2260

2261

2262

2263

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

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

2266 return;

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

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

2272 };

2273

2274 printResult(ParentBB);

2275

2276

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

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

2279 printResult(BBSucc);

2280

2281

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

2285 printResult(UseI->getParent());

2286

2287}

2288

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

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

2296}

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

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

static const Function * getParent(const Value *V)

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

This file defines the DenseSet and SmallDenseSet classes.

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 bool isOperationFoldable(User *Usr)

Definition LazyValueInfo.cpp:1540

static void AddNonNullPointer(Value *Ptr, NonNullPointerSet &PtrSet, bool IsDereferenced=true)

Definition LazyValueInfo.cpp:672

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

Definition LazyValueInfo.cpp:680

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

Definition LazyValueInfo.cpp:1293

static const unsigned MaxProcessedPerValue

Definition LazyValueInfo.cpp:51

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

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

Definition LazyValueInfo.cpp:1313

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

Definition LazyValueInfo.cpp:1532

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

Definition LazyValueInfo.cpp:1548

static ValueLatticeElement getFromRangeMetadata(Instruction *BBI)

Definition LazyValueInfo.cpp:588

lazy value Lazy Value Information static true cl::opt< bool > PerPredRanges("lvi-per-pred-ranges", cl::Hidden, cl::init(false), cl::desc("Enable tracking of ranges for a value in a block for" "each block predecessor (default = false)"))

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

Definition LazyValueInfo.cpp:2023

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

Definition LazyValueInfo.cpp:1459

static bool isKnownNonConstant(Value *V)

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

Definition LazyValueInfo.cpp:1950

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

Definition LazyValueInfo.cpp:1235

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

uint64_t IntrinsicInst * II

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

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

static TableGen::Emitter::Opt Y("gen-skeleton-entry", EmitSkeleton, "Generate example skeleton entry")

static TableGen::Emitter::OptClass< SkeletonEmitter > X("gen-skeleton-class", "Generate example skeleton class")

static std::optional< unsigned > getOpcode(ArrayRef< VPValue * > Values)

Returns the opcode of Values or ~0 if they do not all agree.

Class for arbitrary precision integers.

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

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.

LLVM Basic Block Representation.

iterator begin()

Instruction iterator methods.

const Function * getParent() const

Return the enclosing method, or null if none.

LLVM_ABI bool isEntryBlock() const

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

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

LLVM_ABI const Module * getModule() const

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

LLVM_ABI unsigned getNoWrapKind() const

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

LLVM_ABI Instruction::BinaryOps getBinaryOp() const

Returns the binary operation underlying the intrinsic.

BinaryOps getOpcode() const

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 LLVM_ABI ConstantInt * getTrue(LLVMContext &Context)

static LLVM_ABI ConstantInt * getFalse(LLVMContext &Context)

static LLVM_ABI ConstantPointerNull * get(PointerType *T)

Static factory methods - Return objects of the specified value.

This class represents a range of values.

LLVM_ABI 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 LLVM_ABI ConstantRange fromKnownBits(const KnownBits &Known, bool IsSigned)

Initialize a range based on a known bits constraint.

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

LLVM_ABI ConstantRange umin(const ConstantRange &Other) const

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

LLVM_ABI APInt getUnsignedMin() const

Return the smallest unsigned value contained in the ConstantRange.

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

Does the predicate Pred hold between ranges this and Other?

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

Compute range of intrinsic result for the given operand ranges.

LLVM_ABI bool isEmptySet() const

Return true if this set contains no members.

LLVM_ABI ConstantRange abs(bool IntMinIsPoison=false) const

Calculate absolute value range.

static LLVM_ABI bool isIntrinsicSupported(Intrinsic::ID IntrinsicID)

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

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

LLVM_ABI ConstantRange truncate(uint32_t BitWidth, unsigned NoWrapKind=0) const

Return a new range in the specified integer type, which must be strictly smaller than the current typ...

LLVM_ABI ConstantRange umax(const ConstantRange &Other) const

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

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

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

LLVM_ABI ConstantRange inverse() const

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

LLVM_ABI APInt getUnsignedMax() const

Return the largest unsigned value contained in the ConstantRange.

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

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

LLVM_ABI ConstantRange smax(const ConstantRange &Other) const

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

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

LLVM_ABI ConstantRange toConstantRange() const

Convert constant to an approximate constant range.

static LLVM_ABI Constant * getAllOnesValue(Type *Ty)

static LLVM_ABI Constant * getNullValue(Type *Ty)

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

LLVM_ABI bool isNullValue() const

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

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.

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.

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

Module * getParent()

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

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.

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

LLVM_ABI 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)

Definition LazyValueInfo.cpp:1937

Definition LazyValueInfo.cpp:359

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

Definition LazyValueInfo.cpp:1801

ValueLatticeElement getValueAt(Value *V, Instruction *CxtI)

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

Definition LazyValueInfo.cpp:1784

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

Definition LazyValueInfo.cpp:1873

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

Printing the LazyValueInfo Analysis.

Definition LazyValueInfo.cpp:485

void forgetValue(Value *V)

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

Definition LazyValueInfo.cpp:492

void eraseBlock(BasicBlock *BB)

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

Definition LazyValueInfo.cpp:496

void clear()

Complete flush all previously computed values.

Definition LazyValueInfo.cpp:480

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

Definition LazyValueInfo.cpp:504

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

Definition LazyValueInfo.cpp:1767

ValueLatticeElement getValueAtUse(const Use &U)

Definition LazyValueInfo.cpp:1821

PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

Definition LazyValueInfo.cpp:2289

Wrapper around LazyValueInfo.

bool runOnFunction(Function &F) override

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

Definition LazyValueInfo.cpp:1882

void releaseMemory() override

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

Definition LazyValueInfo.cpp:1935

void getAnalysisUsage(AnalysisUsage &AU) const override

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

Definition LazyValueInfo.cpp:1892

LazyValueInfo & getLVI()

Definition LazyValueInfo.cpp:1898

LazyValueInfoWrapperPass()

Definition LazyValueInfo.cpp:54

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

void eraseBlock(BasicBlock *BB)

Inform the analysis cache that we have erased a block.

Definition LazyValueInfo.cpp:2221

ConstantRange getConstantRangeAtUse(const Use &U, bool UndefAllowed)

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

Definition LazyValueInfo.cpp:1985

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

Definition LazyValueInfo.cpp:1977

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

Definition LazyValueInfo.cpp:2210

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

Definition LazyValueInfo.cpp:2065

void releaseMemory()

Definition LazyValueInfo.cpp:1916

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.

Definition LazyValueInfo.cpp:1995

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

Definition LazyValueInfo.cpp:2012

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

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

Definition LazyValueInfo.cpp:1958

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

Print the \LazyValueInfo Analysis.

Definition LazyValueInfo.cpp:2231

void forgetValue(Value *V)

Remove information related to this value from the cache.

Definition LazyValueInfo.cpp:2216

void clear()

Complete flush all previously computed values.

Definition LazyValueInfo.cpp:2226

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

Definition LazyValueInfo.cpp:2076

~LazyValueInfo()

Definition LazyValueInfo.cpp:1914

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

Handle invalidation events in the new pass manager.

Definition LazyValueInfo.cpp:1924

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.

AnalysisType & getAnalysis() const

getAnalysis() - This function is used by subclasses to get to the analysis information ...

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.

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.

This class represents a truncation of integer types.

unsigned getNoWrapKind() const

Returns the no-wrap kind of the operation.

bool hasNoUnsignedWrap() const

Test whether this operation is known to never undergo unsigned overflow, aka the nuw property.

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

LLVM_ABI unsigned getIntegerBitWidth() const

bool isIntOrIntVectorTy() const

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

LLVM_ABI unsigned getPointerAddressSpace() const

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

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

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

LLVM_ABI unsigned getScalarSizeInBits() const LLVM_READONLY

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

static LLVM_ABI IntegerType * getInt1Ty(LLVMContext &C)

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)

ConstantRange asConstantRange(unsigned BW, bool UndefAllowed=false) const

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

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

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

Strip off pointer casts and inbounds GEPs.

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

LLVM_ABI LLVMContext & getContext() const

All values hold a context through their type.

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

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

BinaryOp_match< SrcTy, SpecificConstantMatch, TargetOpcode::G_XOR, true > m_Not(const SrcTy &&Src)

Matches a register not-ed by a G_XOR.

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)

ap_match< APInt > m_APInt(const APInt *&Res)

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

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.

IntrinsicID_match m_Intrinsic()

Match intrinsic calls like this: m_IntrinsicIntrinsic::fabs(m_Value(X))

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

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< 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 namespace contains all of the command line option processing machinery.

@ User

could "use" a pointer

friend class Instruction

Iterator for Instructions in a `BasicBlock.

This is an optimization pass for GlobalISel generic memory operations.

FunctionAddr VTableAddr Value

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

auto pred_end(const MachineBasicBlock *BB)

decltype(auto) dyn_cast(const From &Val)

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

auto successors(const MachineBasicBlock *BB)

static ConstantRange getRange(Value *Op, SCCPSolver &Solver, const SmallPtrSetImpl< Value * > &InsertedValues)

Helper for getting ranges from Solver.

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.

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

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

LLVM_ABI ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)

Parse out a conservative ConstantRange from !range metadata.

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

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

LLVM_ABI FunctionPass * createLazyValueInfoPass()

createLazyValueInfoPass - This creates an instance of the LazyValueInfo pass.

Definition LazyValueInfo.cpp:68

auto dyn_cast_or_null(const Y &Val)

constexpr unsigned MaxAnalysisRecursionDepth

@ SPF_ABS

Floating point maxnum.

@ SPF_NABS

Absolute value.

@ SPF_UMIN

Signed minimum.

@ SPF_UMAX

Signed maximum.

@ SPF_SMAX

Unsigned minimum.

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

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

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

LLVM_ABI raw_ostream & dbgs()

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

LLVM_ABI Constant * ConstantFoldCastOperand(unsigned Opcode, Constant *C, Type *DestTy, const DataLayout &DL)

Attempt to constant fold a cast with the specified operand.

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

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

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

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

LLVM_ABI 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

bool isSafeToSpeculativelyExecuteWithVariableReplaced(const Instruction *I, bool IgnoreUBImplyingAttrs=true)

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

PredIterator< BasicBlock, Value::user_iterator > pred_iterator

static bool hasSingleValue(const ValueLatticeElement &Val)

constexpr unsigned BitWidth

auto pred_begin(const MachineBasicBlock *BB)

decltype(auto) cast(const From &Val)

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

auto predecessors(const MachineBasicBlock *BB)

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

Returns true if Element is found in Range.

AnalysisManager< Function > FunctionAnalysisManager

Convenience typedef for the Function analysis manager.

LLVM_ABI const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=MaxLookupSearchDepth)

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

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?