Movatterモバイル変換

Go to the documentation of this file.

1//===- LazyValueInfo.cpp - Value constraint analysis ------------*- C++ -*-===//

2//

3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

4// See https://llvm.org/LICENSE.txt for license information.

5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

6//

7//===----------------------------------------------------------------------===//

8//

9// This file defines the interface for lazy computation of value constraint

10// information.

11//

12//===----------------------------------------------------------------------===//

14#include "llvm/Analysis/LazyValueInfo.h"

15#include "llvm/ADT/DenseSet.h"

16#include "llvm/ADT/STLExtras.h"

17#include "llvm/Analysis/AssumptionCache.h"

18#include "llvm/Analysis/ConstantFolding.h"

19#include "llvm/Analysis/InstructionSimplify.h"

20#include "llvm/Analysis/Passes.h"

21#include "llvm/Analysis/TargetLibraryInfo.h"

22#include "llvm/Analysis/ValueLattice.h"

23#include "llvm/Analysis/ValueTracking.h"

24#include "llvm/IR/AssemblyAnnotationWriter.h"

25#include "llvm/IR/CFG.h"

26#include "llvm/IR/ConstantRange.h"

27#include "llvm/IR/Constants.h"

28#include "llvm/IR/DataLayout.h"

29#include "llvm/IR/Dominators.h"

30#include "llvm/IR/InstrTypes.h"

31#include "llvm/IR/Instructions.h"

32#include "llvm/IR/IntrinsicInst.h"

33#include "llvm/IR/Intrinsics.h"

34#include "llvm/IR/LLVMContext.h"

35#include "llvm/IR/Module.h"

36#include "llvm/IR/PatternMatch.h"

37#include "llvm/IR/ValueHandle.h"

38#include "llvm/InitializePasses.h"

39#include "llvm/Support/Debug.h"

40#include "llvm/Support/FormattedStream.h"

41#include "llvm/Support/KnownBits.h"

42#include "llvm/Support/raw_ostream.h"

43#include <optional>

44using namespacellvm;

45using namespacePatternMatch;

47#define DEBUG_TYPE "lazy-value-info"

49// This is the number of worklist items we will process to try to discover an

50// answer for a given value.

51staticconstunsignedMaxProcessedPerValue = 500;

53charLazyValueInfoWrapperPass::ID = 0;

54LazyValueInfoWrapperPass::LazyValueInfoWrapperPass() :FunctionPass(ID) {

55initializeLazyValueInfoWrapperPassPass(*PassRegistry::getPassRegistry());

56}

57INITIALIZE_PASS_BEGIN(LazyValueInfoWrapperPass,"lazy-value-info",

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

59INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)

60INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)

61INITIALIZE_PASS_END(LazyValueInfoWrapperPass, "lazy-value-info",

62 "LazyValue Information Analysis",false,true)

64namespacellvm {

65FunctionPass *createLazyValueInfoPass() {

66returnnewLazyValueInfoWrapperPass();

67}

68}// namespace llvm

70AnalysisKey LazyValueAnalysis::Key;

72/// Returns true if this lattice value represents at most one possible value.

73/// This is as precise as any lattice value can get while still representing

74/// reachable code.

75staticboolhasSingleValue(constValueLatticeElement &Val) {

76if (Val.isConstantRange() &&

77 Val.getConstantRange().isSingleElement())

78// Integer constants are single element ranges

79returntrue;

80if (Val.isConstant())

81// Non integer constants

82returntrue;

83returnfalse;

84}

86//===----------------------------------------------------------------------===//

87// LazyValueInfoCache Decl

88//===----------------------------------------------------------------------===//

90namespace{

91 /// A callback value handle updates the cache when values are erased.

92classLazyValueInfoCache;

93structLVIValueHandle final :publicCallbackVH {

94 LazyValueInfoCache *Parent;

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

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

99void deleted()override;

100void allUsesReplacedWith(Value *V) override{

101 deleted();

102 }

103 };

104}// end anonymous namespace

105

106namespace{

107usingNonNullPointerSet =SmallDenseSet<AssertingVH<Value>, 2>;

108

109/// This is the cache kept by LazyValueInfo which

110/// maintains information about queries across the clients' queries.

111classLazyValueInfoCache {

112 /// This is all of the cached information for one basic block. It contains

113 /// the per-value lattice elements, as well as a separate set for

114 /// overdefined values to reduce memory usage. Additionally pointers

115 /// dereferenced in the block are cached for nullability queries.

116structBlockCacheEntry {

117SmallDenseMap<AssertingVH<Value>,ValueLatticeElement, 4> LatticeElements;

118SmallDenseSet<AssertingVH<Value>, 4> OverDefined;

119// std::nullopt indicates that the nonnull pointers for this basic block

120// block have not been computed yet.

121 std::optional<NonNullPointerSet> NonNullPointers;

122 };

123

124 /// Cached information per basic block.

125DenseMap<PoisoningVH<BasicBlock>, std::unique_ptr<BlockCacheEntry>>

126 BlockCache;

127 /// Set of value handles used to erase values from the cache on deletion.

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

129

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

131auto It = BlockCache.find_as(BB);

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

133returnnullptr;

134return It->second.get();

135 }

136

137 BlockCacheEntry *getOrCreateBlockEntry(BasicBlock *BB) {

138auto It = BlockCache.find_as(BB);

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

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

141

142return It->second.get();

143 }

144

145void addValueHandle(Value *Val) {

146auto HandleIt = ValueHandles.find_as(Val);

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

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

149 }

150

151public:

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

153constValueLatticeElement &Result) {

154 BlockCacheEntry *Entry = getOrCreateBlockEntry(BB);

155

156// Insert over-defined values into their own cache to reduce memory

157// overhead.

158if (Result.isOverdefined())

159Entry->OverDefined.insert(Val);

160else

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

162

163 addValueHandle(Val);

164 }

165

166 std::optional<ValueLatticeElement> getCachedValueInfo(Value *V,

167BasicBlock *BB) const{

168const BlockCacheEntry *Entry = getBlockEntry(BB);

169if (!Entry)

170return std::nullopt;

171

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

173returnValueLatticeElement::getOverdefined();

174

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

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

177return std::nullopt;

178

179return LatticeIt->second;

180 }

181

182bool

183 isNonNullAtEndOfBlock(Value *V,BasicBlock *BB,

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

185 BlockCacheEntry *Entry = getOrCreateBlockEntry(BB);

186if (!Entry->NonNullPointers) {

187Entry->NonNullPointers = InitFn(BB);

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

189 addValueHandle(V);

190 }

191

192returnEntry->NonNullPointers->count(V);

193 }

194

195 /// clear - Empty the cache.

196void clear() {

197 BlockCache.clear();

198 ValueHandles.clear();

199 }

200

201 /// Inform the cache that a given value has been deleted.

202void eraseValue(Value *V);

203

204 /// This is part of the update interface to inform the cache

205 /// that a block has been deleted.

206void eraseBlock(BasicBlock *BB);

207

208 /// Updates the cache to remove any influence an overdefined value in

209 /// OldSucc might have (unless also overdefined in NewSucc). This just

210 /// flushes elements from the cache and does not add any.

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

212};

213}// namespace

214

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

216for (auto &Pair : BlockCache) {

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

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

219if (Pair.second->NonNullPointers)

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

221 }

222

223auto HandleIt = ValueHandles.find_as(V);

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

225 ValueHandles.erase(HandleIt);

226}

227

228void LVIValueHandle::deleted() {

229// This erasure deallocates *this, so it MUST happen after we're done

230// using any and all members of *this.

231 Parent->eraseValue(*this);

232}

233

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

235 BlockCache.erase(BB);

236}

237

238void LazyValueInfoCache::threadEdgeImpl(BasicBlock *OldSucc,

239BasicBlock *NewSucc) {

240// When an edge in the graph has been threaded, values that we could not

241// determine a value for before (i.e. were marked overdefined) may be

242// possible to solve now. We do NOT try to proactively update these values.

243// Instead, we clear their entries from the cache, and allow lazy updating to

244// recompute them when needed.

245

246// The updating process is fairly simple: we need to drop cached info

247// for all values that were marked overdefined in OldSucc, and for those same

248// values in any successor of OldSucc (except NewSucc) in which they were

249// also marked overdefined.

250 std::vector<BasicBlock*> worklist;

251 worklist.push_back(OldSucc);

252

253const BlockCacheEntry *Entry = getBlockEntry(OldSucc);

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

255return;// Nothing to process here.

256SmallVector<Value *, 4> ValsToClear(Entry->OverDefined.begin(),

257Entry->OverDefined.end());

258

259// Use a worklist to perform a depth-first search of OldSucc's successors.

260// NOTE: We do not need a visited list since any blocks we have already

261// visited will have had their overdefined markers cleared already, and we

262// thus won't loop to their successors.

263while (!worklist.empty()) {

264BasicBlock *ToUpdate = worklist.back();

265 worklist.pop_back();

266

267// Skip blocks only accessible through NewSucc.

268if (ToUpdate == NewSucc)continue;

269

270// If a value was marked overdefined in OldSucc, and is here too...

271auto OI = BlockCache.find_as(ToUpdate);

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

273continue;

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

275

276bool changed =false;

277for (Value *V : ValsToClear) {

278if (!ValueSet.erase(V))

279continue;

280

281// If we removed anything, then we potentially need to update

282// blocks successors too.

283 changed =true;

284 }

285

286if (!changed)continue;

287

288llvm::append_range(worklist,successors(ToUpdate));

289 }

290}

291

292namespacellvm {

293namespace{

294/// An assembly annotator class to print LazyValueCache information in

295/// comments.

296classLazyValueInfoAnnotatedWriter :publicAssemblyAnnotationWriter {

297LazyValueInfoImpl *LVIImpl;

298// While analyzing which blocks we can solve values for, we need the dominator

299// information.

300DominatorTree &DT;

301

302public:

303 LazyValueInfoAnnotatedWriter(LazyValueInfoImpl *L,DominatorTree &DTree)

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

305

306void emitBasicBlockStartAnnot(constBasicBlock *BB,

307formatted_raw_ostream &OS)override;

308

309void emitInstructionAnnot(constInstruction *I,

310formatted_raw_ostream &OS)override;

311};

312}// namespace

313// The actual implementation of the lazy analysis and update.

314classLazyValueInfoImpl {

315

316 /// Cached results from previous queries

317 LazyValueInfoCache TheCache;

318

319 /// This stack holds the state of the value solver during a query.

320 /// It basically emulates the callstack of the naive

321 /// recursive value lookup process.

322SmallVector<std::pair<BasicBlock*, Value*>, 8> BlockValueStack;

323

324 /// Keeps track of which block-value pairs are in BlockValueStack.

325DenseSet<std::pair<BasicBlock*, Value*> > BlockValueSet;

326

327 /// Push BV onto BlockValueStack unless it's already in there.

328 /// Returns true on success.

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

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

331returnfalse;// It's already in the stack.

332

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

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

335 BlockValueStack.push_back(BV);

336returntrue;

337 }

338

339AssumptionCache *AC;///< A pointer to the cache of @llvm.assume calls.

340constDataLayout &DL;///< A mandatory DataLayout

341

342 /// Declaration of the llvm.experimental.guard() intrinsic,

343 /// if it exists in the module.

344Function *GuardDecl;

345

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

347Instruction *CxtI);

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

349BasicBlock *T,

350Instruction *CxtI =nullptr);

351

352// These methods process one work item and may add more. A false value

353// returned means that the work item was not completely processed and must

354// be revisited after going through the new items.

355bool solveBlockValue(Value *Val,BasicBlock *BB);

356 std::optional<ValueLatticeElement> solveBlockValueImpl(Value *Val,

357BasicBlock *BB);

358 std::optional<ValueLatticeElement> solveBlockValueNonLocal(Value *Val,

359BasicBlock *BB);

360 std::optional<ValueLatticeElement> solveBlockValuePHINode(PHINode *PN,

361BasicBlock *BB);

362 std::optional<ValueLatticeElement> solveBlockValueSelect(SelectInst *S,

363BasicBlock *BB);

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

365BasicBlock *BB);

366 std::optional<ValueLatticeElement> solveBlockValueBinaryOpImpl(

367Instruction *I,BasicBlock *BB,

368 std::function<ConstantRange(constConstantRange &,constConstantRange &)>

369 OpFn);

370 std::optional<ValueLatticeElement>

371 solveBlockValueBinaryOp(BinaryOperator *BBI,BasicBlock *BB);

372 std::optional<ValueLatticeElement> solveBlockValueCast(CastInst *CI,

373BasicBlock *BB);

374 std::optional<ValueLatticeElement>

375 solveBlockValueOverflowIntrinsic(WithOverflowInst *WO,BasicBlock *BB);

376 std::optional<ValueLatticeElement> solveBlockValueIntrinsic(IntrinsicInst *II,

377BasicBlock *BB);

378 std::optional<ValueLatticeElement>

379 solveBlockValueInsertElement(InsertElementInst *IEI,BasicBlock *BB);

380 std::optional<ValueLatticeElement>

381 solveBlockValueExtractValue(ExtractValueInst *EVI,BasicBlock *BB);

382bool isNonNullAtEndOfBlock(Value *Val,BasicBlock *BB);

383void intersectAssumeOrGuardBlockValueConstantRange(Value *Val,

384ValueLatticeElement &BBLV,

385Instruction *BBI);

386

387void solve();

388

389// For the following methods, if UseBlockValue is true, the function may

390// push additional values to the worklist and return nullopt. If

391// UseBlockValue is false, it will never return nullopt.

392

393 std::optional<ValueLatticeElement>

394 getValueFromSimpleICmpCondition(CmpInst::Predicate Pred,Value *RHS,

395constAPInt &Offset,Instruction *CxtI,

396bool UseBlockValue);

397

398 std::optional<ValueLatticeElement>

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

400bool UseBlockValue);

401

402 std::optional<ValueLatticeElement>

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

404bool UseBlockValue,unsignedDepth = 0);

405

406 std::optional<ValueLatticeElement> getEdgeValueLocal(Value *Val,

407BasicBlock *BBFrom,

408BasicBlock *BBTo,

409bool UseBlockValue);

410

411public:

412 /// This is the query interface to determine the lattice value for the

413 /// specified Value* at the context instruction (if specified) or at the

414 /// start of the block.

415ValueLatticeElement getValueInBlock(Value *V,BasicBlock *BB,

416Instruction *CxtI =nullptr);

417

418 /// This is the query interface to determine the lattice value for the

419 /// specified Value* at the specified instruction using only information

420 /// from assumes/guards and range metadata. Unlike getValueInBlock(), no

421 /// recursive query is performed.

422ValueLatticeElement getValueAt(Value *V,Instruction *CxtI);

423

424 /// This is the query interface to determine the lattice

425 /// value for the specified Value* that is true on the specified edge.

426ValueLatticeElement getValueOnEdge(Value *V,BasicBlock *FromBB,

427BasicBlock *ToBB,

428Instruction *CxtI =nullptr);

429

430ValueLatticeElement getValueAtUse(constUse &U);

431

432 /// Complete flush all previously computed values

433voidclear() {

434 TheCache.clear();

435 }

436

437 /// Printing the LazyValueInfo Analysis.

438voidprintLVI(Function &F,DominatorTree &DTree,raw_ostream &OS) {

439 LazyValueInfoAnnotatedWriter Writer(this, DTree);

440F.print(OS, &Writer);

441 }

442

443 /// This is part of the update interface to remove information related to this

444 /// value from the cache.

445voidforgetValue(Value *V) { TheCache.eraseValue(V); }

446

447 /// This is part of the update interface to inform the cache

448 /// that a block has been deleted.

449voideraseBlock(BasicBlock *BB) {

450 TheCache.eraseBlock(BB);

451 }

452

453 /// This is the update interface to inform the cache that an edge from

454 /// PredBB to OldSucc has been threaded to be from PredBB to NewSucc.

455voidthreadEdge(BasicBlock *PredBB,BasicBlock *OldSucc,BasicBlock *NewSucc);

456

457LazyValueInfoImpl(AssumptionCache *AC,constDataLayout &DL,

458Function *GuardDecl)

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

460};

461}// namespace llvm

462

463void LazyValueInfoImpl::solve() {

464SmallVector<std::pair<BasicBlock *, Value *>, 8> StartingStack =

465 BlockValueStack;

466

467unsigned processedCount = 0;

468while (!BlockValueStack.empty()) {

469 processedCount++;

470// Abort if we have to process too many values to get a result for this one.

471// Because of the design of the overdefined cache currently being per-block

472// to avoid naming-related issues (IE it wants to try to give different

473// results for the same name in different blocks), overdefined results don't

474// get cached globally, which in turn means we will often try to rediscover

475// the same overdefined result again and again. Once something like

476// PredicateInfo is used in LVI or CVP, we should be able to make the

477// overdefined cache global, and remove this throttle.

478if (processedCount >MaxProcessedPerValue) {

479LLVM_DEBUG(

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

481// Fill in the original values

482while (!StartingStack.empty()) {

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

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

485ValueLatticeElement::getOverdefined());

486 StartingStack.pop_back();

487 }

488 BlockValueSet.clear();

489 BlockValueStack.clear();

490return;

491 }

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

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

494unsigned StackSize = BlockValueStack.size();

495 (void) StackSize;

496

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

498// The work item was completely processed.

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

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

501#ifndef NDEBUG

502 std::optional<ValueLatticeElement> BBLV =

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

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

505LLVM_DEBUG(

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

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

508#endif

509

510 BlockValueStack.pop_back();

511 BlockValueSet.erase(e);

512 }else {

513// More work needs to be done before revisiting.

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

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

516 }

517 }

518}

519

520std::optional<ValueLatticeElement>

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

522Instruction *CxtI) {

523// If already a constant, there is nothing to compute.

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

525returnValueLatticeElement::get(VC);

526

527if (std::optional<ValueLatticeElement> OptLatticeVal =

528 TheCache.getCachedValueInfo(Val, BB)) {

529 intersectAssumeOrGuardBlockValueConstantRange(Val, *OptLatticeVal, CxtI);

530return OptLatticeVal;

531 }

532

533// We have hit a cycle, assume overdefined.

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

535returnValueLatticeElement::getOverdefined();

536

537// Yet to be resolved.

538return std::nullopt;

539}

540

541staticValueLatticeElement getFromRangeMetadata(Instruction *BBI) {

542switch (BBI->getOpcode()) {

543default:

544break;

545case Instruction::Call:

546case Instruction::Invoke:

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

548returnValueLatticeElement::getRange(*Range);

549 [[fallthrough]];

550case Instruction::Load:

551if (MDNode *Ranges = BBI->getMetadata(LLVMContext::MD_range))

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

553returnValueLatticeElement::getRange(

554getConstantRangeFromMetadata(*Ranges));

555 }

556break;

557 };

558// Nothing known - will be intersected with other facts

559returnValueLatticeElement::getOverdefined();

560}

561

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

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

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

565"Value should not be in cache");

566

567// Hold off inserting this value into the Cache in case we have to return

568// false and come back later.

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

570if (!Res)

571// Work pushed, will revisit

572returnfalse;

573

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

575returntrue;

576}

577

578std::optional<ValueLatticeElement>

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

580Instruction *BBI = dyn_cast<Instruction>(Val);

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

582return solveBlockValueNonLocal(Val, BB);

583

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

585return solveBlockValuePHINode(PN, BB);

586

587if (auto *SI = dyn_cast<SelectInst>(BBI))

588return solveBlockValueSelect(SI, BB);

589

590// If this value is a nonnull pointer, record it's range and bailout. Note

591// that for all other pointer typed values, we terminate the search at the

592// definition. We could easily extend this to look through geps, bitcasts,

593// and the like to prove non-nullness, but it's not clear that's worth it

594// compile time wise. The context-insensitive value walk done inside

595// isKnownNonZero gets most of the profitable cases at much less expense.

596// This does mean that we have a sensitivity to where the defining

597// instruction is placed, even if it could legally be hoisted much higher.

598// That is unfortunate.

599PointerType *PT = dyn_cast<PointerType>(BBI->getType());

600if (PT &&isKnownNonZero(BBI, DL))

601returnValueLatticeElement::getNot(ConstantPointerNull::get(PT));

602

603if (BBI->getType()->isIntOrIntVectorTy()) {

604if (auto *CI = dyn_cast<CastInst>(BBI))

605return solveBlockValueCast(CI, BB);

606

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

608return solveBlockValueBinaryOp(BO, BB);

609

610if (auto *IEI = dyn_cast<InsertElementInst>(BBI))

611return solveBlockValueInsertElement(IEI, BB);

612

613if (auto *EVI = dyn_cast<ExtractValueInst>(BBI))

614return solveBlockValueExtractValue(EVI, BB);

615

616if (auto *II = dyn_cast<IntrinsicInst>(BBI))

617return solveBlockValueIntrinsic(II, BB);

618 }

619

620LLVM_DEBUG(dbgs() <<" compute BB '" << BB->getName()

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

622returngetFromRangeMetadata(BBI);

623}

624

625staticvoidAddNonNullPointer(Value *Ptr, NonNullPointerSet &PtrSet) {

626// TODO: Use NullPointerIsDefined instead.

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

628 PtrSet.insert(getUnderlyingObject(Ptr));

629}

630

631staticvoidAddNonNullPointersByInstruction(

632Instruction *I, NonNullPointerSet &PtrSet) {

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

634AddNonNullPointer(L->getPointerOperand(), PtrSet);

635 }elseif (StoreInst *S = dyn_cast<StoreInst>(I)) {

636AddNonNullPointer(S->getPointerOperand(), PtrSet);

637 }elseif (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) {

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

639

640// FIXME: check whether it has a valuerange that excludes zero?

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

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

643

644AddNonNullPointer(MI->getRawDest(), PtrSet);

645if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI))

646AddNonNullPointer(MTI->getRawSource(), PtrSet);

647 }

648}

649

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

651if (NullPointerIsDefined(BB->getParent(),

652 Val->getType()->getPointerAddressSpace()))

653returnfalse;

654

655 Val = Val->stripInBoundsOffsets();

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

657 NonNullPointerSet NonNullPointers;

658for (Instruction &I : *BB)

659AddNonNullPointersByInstruction(&I, NonNullPointers);

660return NonNullPointers;

661 });

662}

663

664std::optional<ValueLatticeElement>

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

666ValueLatticeElement Result;// Start Undefined.

667

668// If this is the entry block, we must be asking about an argument.

669if (BB->isEntryBlock()) {

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

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

672returnValueLatticeElement::getRange(*Range);

673returnValueLatticeElement::getOverdefined();

674 }

675

676// Loop over all of our predecessors, merging what we know from them into

677// result. If we encounter an unexplored predecessor, we eagerly explore it

678// in a depth first manner. In practice, this has the effect of discovering

679// paths we can't analyze eagerly without spending compile times analyzing

680// other paths. This heuristic benefits from the fact that predecessors are

681// frequently arranged such that dominating ones come first and we quickly

682// find a path to function entry. TODO: We should consider explicitly

683// canonicalizing to make this true rather than relying on this happy

684// accident.

685for (BasicBlock *Pred :predecessors(BB)) {

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

687if (!EdgeResult)

688// Explore that input, then return here

689return std::nullopt;

690

691Result.mergeIn(*EdgeResult);

692

693// If we hit overdefined, exit early. The BlockVals entry is already set

694// to overdefined.

695if (Result.isOverdefined()) {

696LLVM_DEBUG(dbgs() <<" compute BB '" << BB->getName()

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

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

699returnResult;

700 }

701 }

702

703// Return the merged value, which is more precise than 'overdefined'.

704assert(!Result.isOverdefined());

705returnResult;

706}

707

708std::optional<ValueLatticeElement>

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

710ValueLatticeElement Result;// Start Undefined.

711

712// Loop over all of our predecessors, merging what we know from them into

713// result. See the comment about the chosen traversal order in

714// solveBlockValueNonLocal; the same reasoning applies here.

715for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {

716BasicBlock *PhiBB = PN->getIncomingBlock(i);

717Value *PhiVal = PN->getIncomingValue(i);

718// Note that we can provide PN as the context value to getEdgeValue, even

719// though the results will be cached, because PN is the value being used as

720// the cache key in the caller.

721 std::optional<ValueLatticeElement> EdgeResult =

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

723if (!EdgeResult)

724// Explore that input, then return here

725return std::nullopt;

726

727Result.mergeIn(*EdgeResult);

728

729// If we hit overdefined, exit early. The BlockVals entry is already set

730// to overdefined.

731if (Result.isOverdefined()) {

732LLVM_DEBUG(dbgs() <<" compute BB '" << BB->getName()

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

734

735returnResult;

736 }

737 }

738

739// Return the merged value, which is more precise than 'overdefined'.

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

741returnResult;

742}

743

744// If we can determine a constraint on the value given conditions assumed by

745// the program, intersect those constraints with BBLV

746void LazyValueInfoImpl::intersectAssumeOrGuardBlockValueConstantRange(

747Value *Val,ValueLatticeElement &BBLV,Instruction *BBI) {

748 BBI = BBI ? BBI : dyn_cast<Instruction>(Val);

749if (!BBI)

750return;

751

752BasicBlock *BB = BBI->getParent();

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

754if (!AssumeVH)

755continue;

756

757// Only check assumes in the block of the context instruction. Other

758// assumes will have already been taken into account when the value was

759// propagated from predecessor blocks.

760auto *I = cast<CallInst>(AssumeVH);

761if (I->getParent() != BB || !isValidAssumeForContext(I, BBI))

762continue;

763

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

765/*IsTrueDest*/true,

766/*UseBlockValue*/false));

767 }

768

769// If guards are not used in the module, don't spend time looking for them

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

771 BBI->getIterator() != BB->begin()) {

772for (Instruction &I :

773make_range(std::next(BBI->getIterator().getReverse()), BB->rend())) {

774Value *Cond =nullptr;

775if (match(&I, m_Intrinsic<Intrinsic::experimental_guard>(m_Value(Cond))))

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

777/*IsTrueDest*/true,

778/*UseBlockValue*/false));

779 }

780 }

781

782if (BBLV.isOverdefined()) {

783// Check whether we're checking at the terminator, and the pointer has

784// been dereferenced in this block.

785PointerType *PTy = dyn_cast<PointerType>(Val->getType());

786if (PTy && BB->getTerminator() == BBI &&

787 isNonNullAtEndOfBlock(Val, BB))

788 BBLV =ValueLatticeElement::getNot(ConstantPointerNull::get(PTy));

789 }

790}

791

792std::optional<ValueLatticeElement>

793LazyValueInfoImpl::solveBlockValueSelect(SelectInst *SI,BasicBlock *BB) {

794// Recurse on our inputs if needed

795 std::optional<ValueLatticeElement> OptTrueVal =

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

797if (!OptTrueVal)

798return std::nullopt;

799ValueLatticeElement &TrueVal = *OptTrueVal;

800

801 std::optional<ValueLatticeElement> OptFalseVal =

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

803if (!OptFalseVal)

804return std::nullopt;

805ValueLatticeElement &FalseVal = *OptFalseVal;

806

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

808constConstantRange &TrueCR =TrueVal.asConstantRange(SI->getType());

809constConstantRange &FalseCR =FalseVal.asConstantRange(SI->getType());

810Value *LHS =nullptr;

811Value *RHS =nullptr;

812SelectPatternResult SPR =matchSelectPattern(SI, LHS, RHS);

813// Is this a min specifically of our two inputs? (Avoid the risk of

814// ValueTracking getting smarter looking back past our immediate inputs.)

815if (SelectPatternResult::isMinOrMax(SPR.Flavor) &&

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

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

818ConstantRange ResultCR = [&]() {

819switch (SPR.Flavor) {

820default:

821llvm_unreachable("unexpected minmax type!");

822caseSPF_SMIN:/// Signed minimum

823return TrueCR.smin(FalseCR);

824caseSPF_UMIN:/// Unsigned minimum

825return TrueCR.umin(FalseCR);

826caseSPF_SMAX:/// Signed maximum

827return TrueCR.smax(FalseCR);

828caseSPF_UMAX:/// Unsigned maximum

829return TrueCR.umax(FalseCR);

830 };

831 }();

832returnValueLatticeElement::getRange(

833 ResultCR,TrueVal.isConstantRangeIncludingUndef() ||

834FalseVal.isConstantRangeIncludingUndef());

835 }

836

837if (SPR.Flavor ==SPF_ABS) {

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

839returnValueLatticeElement::getRange(

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

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

842returnValueLatticeElement::getRange(

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

844 }

845

846if (SPR.Flavor ==SPF_NABS) {

847ConstantRange Zero(APInt::getZero(TrueCR.getBitWidth()));

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

849returnValueLatticeElement::getRange(

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

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

852returnValueLatticeElement::getRange(

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

854 }

855 }

856

857// Can we constrain the facts about the true and false values by using the

858// condition itself? This shows up with idioms like e.g. select(a > 5, a, 5).

859// TODO: We could potentially refine an overdefined true value above.

860Value *Cond =SI->getCondition();

861// If the value is undef, a different value may be chosen in

862// the select condition.

863if (isGuaranteedNotToBeUndef(Cond, AC)) {

864TrueVal =

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

866/*IsTrueDest*/true,

867/*UseBlockValue*/false));

868FalseVal =

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

870/*IsTrueDest*/false,

871/*UseBlockValue*/false));

872 }

873

874ValueLatticeElement Result =TrueVal;

875Result.mergeIn(FalseVal);

876returnResult;

877}

878

879std::optional<ConstantRange>

880LazyValueInfoImpl::getRangeFor(Value *V,Instruction *CxtI,BasicBlock *BB) {

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

882if (!OptVal)

883return std::nullopt;

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

885}

886

887std::optional<ValueLatticeElement>

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

889// Filter out casts we don't know how to reason about before attempting to

890// recurse on our operand. This can cut a long search short if we know we're

891// not going to be able to get any useful information anways.

892switch (CI->getOpcode()) {

893case Instruction::Trunc:

894case Instruction::SExt:

895case Instruction::ZExt:

896break;

897default:

898// Unhandled instructions are overdefined.

899LLVM_DEBUG(dbgs() <<" compute BB '" << BB->getName()

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

901returnValueLatticeElement::getOverdefined();

902 }

903

904// Figure out the range of the LHS. If that fails, we still apply the

905// transfer rule on the full set since we may be able to locally infer

906// interesting facts.

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

908if (!LHSRes)

909// More work to do before applying this transfer rule.

910return std::nullopt;

911constConstantRange &LHSRange = *LHSRes;

912

913constunsigned ResultBitWidth = CI->getType()->getScalarSizeInBits();

914

915// NOTE: We're currently limited by the set of operations that ConstantRange

916// can evaluate symbolically. Enhancing that set will allows us to analyze

917// more definitions.

918returnValueLatticeElement::getRange(LHSRange.castOp(CI->getOpcode(),

919 ResultBitWidth));

920}

921

922std::optional<ValueLatticeElement>

923LazyValueInfoImpl::solveBlockValueBinaryOpImpl(

924Instruction *I,BasicBlock *BB,

925 std::function<ConstantRange(constConstantRange &,constConstantRange &)>

926 OpFn) {

927Value *LHS =I->getOperand(0);

928Value *RHS =I->getOperand(1);

929

930auto ThreadBinOpOverSelect =

931 [&](Value *X,constConstantRange &CRX,SelectInst *Y,

932bool XIsLHS) -> std::optional<ValueLatticeElement> {

933Value *Cond =Y->getCondition();

934// Only handle selects with constant values.

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

936if (!TrueC)

937return std::nullopt;

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

939if (!FalseC)

940return std::nullopt;

941if (!isGuaranteedNotToBeUndef(Cond, AC))

942return std::nullopt;

943

944ConstantRange TrueX =

945 CRX.intersectWith(getValueFromCondition(X,Cond,/*CondIsTrue=*/true,

946/*UseBlockValue=*/false)

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

948ConstantRange FalseX =

949 CRX.intersectWith(getValueFromCondition(X,Cond,/*CondIsTrue=*/false,

950/*UseBlockValue=*/false)

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

952ConstantRange TrueY = TrueC->toConstantRange();

953ConstantRange FalseY = FalseC->toConstantRange();

954

955if (XIsLHS)

956returnValueLatticeElement::getRange(

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

958returnValueLatticeElement::getRange(

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

960 };

961

962// Figure out the ranges of the operands. If that fails, use a

963// conservative range, but apply the transfer rule anyways. This

964// lets us pick up facts from expressions like "and i32 (call i32

965// @foo()), 32"

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

967if (!LHSRes)

968return std::nullopt;

969

970// Try to thread binop over rhs select

971if (auto *SI = dyn_cast<SelectInst>(RHS)) {

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

973return *Res;

974 }

975

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

977if (!RHSRes)

978return std::nullopt;

979

980// Try to thread binop over lhs select

981if (auto *SI = dyn_cast<SelectInst>(LHS)) {

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

983return *Res;

984 }

985

986constConstantRange &LHSRange = *LHSRes;

987constConstantRange &RHSRange = *RHSRes;

988returnValueLatticeElement::getRange(OpFn(LHSRange, RHSRange));

989}

990

991std::optional<ValueLatticeElement>

992LazyValueInfoImpl::solveBlockValueBinaryOp(BinaryOperator *BO,BasicBlock *BB) {

993assert(BO->getOperand(0)->getType()->isSized() &&

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

995if (auto *OBO = dyn_cast<OverflowingBinaryOperator>(BO)) {

996unsigned NoWrapKind = OBO->getNoWrapKind();

997return solveBlockValueBinaryOpImpl(

998 BO, BB,

999 [BO, NoWrapKind](constConstantRange &CR1,constConstantRange &CR2) {

1000return CR1.overflowingBinaryOp(BO->getOpcode(), CR2, NoWrapKind);

1001 });

1002 }

1003

1004return solveBlockValueBinaryOpImpl(

1005 BO, BB, [BO](constConstantRange &CR1,constConstantRange &CR2) {

1006return CR1.binaryOp(BO->getOpcode(), CR2);

1007 });

1008}

1009

1010std::optional<ValueLatticeElement>

1011LazyValueInfoImpl::solveBlockValueOverflowIntrinsic(WithOverflowInst *WO,

1012BasicBlock *BB) {

1013return solveBlockValueBinaryOpImpl(

1014 WO, BB, [WO](constConstantRange &CR1,constConstantRange &CR2) {

1015return CR1.binaryOp(WO->getBinaryOp(), CR2);

1016 });

1017}

1018

1019std::optional<ValueLatticeElement>

1020LazyValueInfoImpl::solveBlockValueIntrinsic(IntrinsicInst *II,BasicBlock *BB) {

1021ValueLatticeElement MetadataVal =getFromRangeMetadata(II);

1022if (!ConstantRange::isIntrinsicSupported(II->getIntrinsicID())) {

1023LLVM_DEBUG(dbgs() <<" compute BB '" << BB->getName()

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

1025return MetadataVal;

1026 }

1027

1028SmallVector<ConstantRange, 2> OpRanges;

1029for (Value *Op :II->args()) {

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

1031if (!Range)

1032return std::nullopt;

1033 OpRanges.push_back(*Range);

1034 }

1035

1036returnValueLatticeElement::getRange(

1037ConstantRange::intrinsic(II->getIntrinsicID(), OpRanges))

1038 .intersect(MetadataVal);

1039}

1040

1041std::optional<ValueLatticeElement>

1042LazyValueInfoImpl::solveBlockValueInsertElement(InsertElementInst *IEI,

1043BasicBlock *BB) {

1044 std::optional<ValueLatticeElement> OptEltVal =

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

1046if (!OptEltVal)

1047return std::nullopt;

1048ValueLatticeElement &Res = *OptEltVal;

1049

1050 std::optional<ValueLatticeElement> OptVecVal =

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

1052if (!OptVecVal)

1053return std::nullopt;

1054

1055// Bail out if the inserted element is a constant expression. Unlike other

1056// ValueLattice types, these are not considered an implicit splat when a

1057// vector type is used.

1058// We could call ConstantFoldInsertElementInstruction here to handle these.

1059if (OptEltVal->isConstant())

1060returnValueLatticeElement::getOverdefined();

1061

1062 Res.mergeIn(*OptVecVal);

1063return Res;

1064}

1065

1066std::optional<ValueLatticeElement>

1067LazyValueInfoImpl::solveBlockValueExtractValue(ExtractValueInst *EVI,

1068BasicBlock *BB) {

1069if (auto *WO = dyn_cast<WithOverflowInst>(EVI->getAggregateOperand()))

1070if (EVI->getNumIndices() == 1 && *EVI->idx_begin() == 0)

1071return solveBlockValueOverflowIntrinsic(WO, BB);

1072

1073// Handle extractvalue of insertvalue to allow further simplification

1074// based on replaced with.overflow intrinsics.

1075if (Value *V =simplifyExtractValueInst(

1076 EVI->getAggregateOperand(), EVI->getIndices(),

1077 EVI->getDataLayout()))

1078return getBlockValue(V, BB, EVI);

1079

1080LLVM_DEBUG(dbgs() <<" compute BB '" << BB->getName()

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

1082returnValueLatticeElement::getOverdefined();

1083}

1084

1085staticboolmatchICmpOperand(APInt &Offset,Value *LHS,Value *Val,

1086ICmpInst::Predicate Pred) {

1087if (LHS == Val)

1088returntrue;

1089

1090// Handle range checking idiom produced by InstCombine. We will subtract the

1091// offset from the allowed range for RHS in this case.

1092constAPInt *C;

1093if (match(LHS,m_AddLike(m_Specific(Val),m_APInt(C)))) {

1094Offset = *C;

1095returntrue;

1096 }

1097

1098// Handle the symmetric case. This appears in saturation patterns like

1099// (x == 16) ? 16 : (x + 1).

1100if (match(Val,m_AddLike(m_Specific(LHS),m_APInt(C)))) {

1101Offset = -*C;

1102returntrue;

1103 }

1104

1105// If (x | y) < C, then (x < C) && (y < C).

1106if (match(LHS,m_c_Or(m_Specific(Val),m_Value())) &&

1107 (Pred ==ICmpInst::ICMP_ULT || Pred ==ICmpInst::ICMP_ULE))

1108returntrue;

1109

1110// If (x & y) > C, then (x > C) && (y > C).

1111if (match(LHS,m_c_And(m_Specific(Val),m_Value())) &&

1112 (Pred ==ICmpInst::ICMP_UGT || Pred ==ICmpInst::ICMP_UGE))

1113returntrue;

1114

1115returnfalse;

1116}

1117

1118/// Get value range for a "(Val + Offset) Pred RHS" condition.

1119std::optional<ValueLatticeElement>

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

1121Value *RHS,

1122constAPInt &Offset,

1123Instruction *CxtI,

1124bool UseBlockValue) {

1125ConstantRange RHSRange(RHS->getType()->getScalarSizeInBits(),

1126/*isFullSet=*/true);

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

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

1129 }elseif (UseBlockValue) {

1130 std::optional<ValueLatticeElement>R =

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

1132if (!R)

1133return std::nullopt;

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

1135 }

1136

1137ConstantRange TrueValues =

1138ConstantRange::makeAllowedICmpRegion(Pred, RHSRange);

1139returnValueLatticeElement::getRange(TrueValues.subtract(Offset));

1140}

1141

1142static std::optional<ConstantRange>

1143getRangeViaSLT(CmpInst::Predicate Pred,APInt RHS,

1144function_ref<std::optional<ConstantRange>(constAPInt &)> Fn) {

1145bool Invert =false;

1146if (Pred ==ICmpInst::ICMP_SGT || Pred ==ICmpInst::ICMP_SGE) {

1147 Pred =ICmpInst::getInversePredicate(Pred);

1148 Invert =true;

1149 }

1150if (Pred ==ICmpInst::ICMP_SLE) {

1151 Pred =ICmpInst::ICMP_SLT;

1152if (RHS.isMaxSignedValue())

1153return std::nullopt;// Could also return full/empty here, if we wanted.

1154 ++RHS;

1155 }

1156assert(Pred ==ICmpInst::ICMP_SLT &&"Must be signed predicate");

1157if (auto CR = Fn(RHS))

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

1159return std::nullopt;

1160}

1161

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

1163staticValueLatticeElement getValueFromICmpCtpop(ICmpInst::Predicate Pred,

1164Value *RHS) {

1165unsignedBitWidth =RHS->getType()->getScalarSizeInBits();

1166

1167auto *RHSConst = dyn_cast<ConstantInt>(RHS);

1168if (!RHSConst)

1169returnValueLatticeElement::getOverdefined();

1170

1171ConstantRange ResValRange =

1172ConstantRange::makeExactICmpRegion(Pred, RHSConst->getValue());

1173

1174unsigned ResMin = ResValRange.getUnsignedMin().getLimitedValue(BitWidth);

1175unsigned ResMax = ResValRange.getUnsignedMax().getLimitedValue(BitWidth);

1176

1177APInt ValMin =APInt::getLowBitsSet(BitWidth, ResMin);

1178APInt ValMax =APInt::getHighBitsSet(BitWidth, ResMax);

1179returnValueLatticeElement::getRange(

1180ConstantRange::getNonEmpty(std::move(ValMin), ValMax + 1));

1181}

1182

1183std::optional<ValueLatticeElement> LazyValueInfoImpl::getValueFromICmpCondition(

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

1185Value *LHS = ICI->getOperand(0);

1186Value *RHS = ICI->getOperand(1);

1187

1188// Get the predicate that must hold along the considered edge.

1189CmpInst::Predicate EdgePred =

1190 isTrueDest ? ICI->getPredicate() : ICI->getInversePredicate();

1191

1192if (isa<Constant>(RHS)) {

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

1194if (EdgePred ==ICmpInst::ICMP_EQ)

1195returnValueLatticeElement::get(cast<Constant>(RHS));

1196elseif (!isa<UndefValue>(RHS))

1197returnValueLatticeElement::getNot(cast<Constant>(RHS));

1198 }

1199 }

1200

1201Type *Ty = Val->getType();

1202if (!Ty->isIntegerTy())

1203returnValueLatticeElement::getOverdefined();

1204

1205unsignedBitWidth = Ty->getScalarSizeInBits();

1206APInt Offset(BitWidth, 0);

1207if (matchICmpOperand(Offset, LHS, Val, EdgePred))

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

1209 UseBlockValue);

1210

1211CmpInst::Predicate SwappedPred =CmpInst::getSwappedPredicate(EdgePred);

1212if (matchICmpOperand(Offset, RHS, Val, SwappedPred))

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

1214 UseBlockValue);

1215

1216if (match(LHS, m_Intrinsic<Intrinsic::ctpop>(m_Specific(Val))))

1217returngetValueFromICmpCtpop(EdgePred, RHS);

1218

1219constAPInt *Mask, *C;

1220if (match(LHS,m_And(m_Specific(Val),m_APInt(Mask))) &&

1221match(RHS,m_APInt(C))) {

1222// If (Val & Mask) == C then all the masked bits are known and we can

1223// compute a value range based on that.

1224if (EdgePred ==ICmpInst::ICMP_EQ) {

1225KnownBits Known;

1226 Known.Zero = ~*C & *Mask;

1227 Known.One = *C & *Mask;

1228returnValueLatticeElement::getRange(

1229ConstantRange::fromKnownBits(Known,/*IsSigned*/false));

1230 }

1231

1232if (EdgePred ==ICmpInst::ICMP_NE)

1233returnValueLatticeElement::getRange(

1234ConstantRange::makeMaskNotEqualRange(*Mask, *C));

1235 }

1236

1237// If (X urem Modulus) >= C, then X >= C.

1238// If trunc X >= C, then X >= C.

1239// TODO: An upper bound could be computed as well.

1240if (match(LHS,m_CombineOr(m_URem(m_Specific(Val),m_Value()),

1241m_Trunc(m_Specific(Val)))) &&

1242match(RHS,m_APInt(C))) {

1243// Use the icmp region so we don't have to deal with different predicates.

1244ConstantRange CR =ConstantRange::makeExactICmpRegion(EdgePred, *C);

1245if (!CR.isEmptySet())

1246returnValueLatticeElement::getRange(ConstantRange::getNonEmpty(

1247 CR.getUnsignedMin().zext(BitWidth),APInt(BitWidth, 0)));

1248 }

1249

1250// Recognize:

1251// icmp slt (ashr X, ShAmtC), C --> icmp slt X, C << ShAmtC

1252// Preconditions: (C << ShAmtC) >> ShAmtC == C

1253constAPInt *ShAmtC;

1254if (CmpInst::isSigned(EdgePred) &&

1255match(LHS,m_AShr(m_Specific(Val),m_APInt(ShAmtC))) &&

1256match(RHS,m_APInt(C))) {

1257auto CR =getRangeViaSLT(

1258 EdgePred, *C, [&](constAPInt &RHS) -> std::optional<ConstantRange> {

1259APInt New =RHS << *ShAmtC;

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

1261return std::nullopt;

1262returnConstantRange::getNonEmpty(

1263APInt::getSignedMinValue(New.getBitWidth()), New);

1264 });

1265if (CR)

1266returnValueLatticeElement::getRange(*CR);

1267 }

1268

1269// a - b or ptrtoint(a) - ptrtoint(b) ==/!= 0 if a ==/!= b

1270Value *X, *Y;

1271if (ICI->isEquality() &&match(Val,m_Sub(m_Value(X),m_Value(Y)))) {

1272// Peek through ptrtoints

1273match(X,m_PtrToIntSameSize(DL,m_Value(X)));

1274match(Y,m_PtrToIntSameSize(DL,m_Value(Y)));

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

1276Constant *NullVal =Constant::getNullValue(Val->getType());

1277if (EdgePred ==ICmpInst::ICMP_EQ)

1278returnValueLatticeElement::get(NullVal);

1279returnValueLatticeElement::getNot(NullVal);

1280 }

1281 }

1282

1283returnValueLatticeElement::getOverdefined();

1284}

1285

1286// Handle conditions of the form

1287// extractvalue(op.with.overflow(%x, C), 1).

1288staticValueLatticeElement getValueFromOverflowCondition(

1289Value *Val,WithOverflowInst *WO,bool IsTrueDest) {

1290// TODO: This only works with a constant RHS for now. We could also compute

1291// the range of the RHS, but this doesn't fit into the current structure of

1292// the edge value calculation.

1293constAPInt *C;

1294if (WO->getLHS() != Val || !match(WO->getRHS(),m_APInt(C)))

1295returnValueLatticeElement::getOverdefined();

1296

1297// Calculate the possible values of %x for which no overflow occurs.

1298ConstantRange NWR =ConstantRange::makeExactNoWrapRegion(

1299 WO->getBinaryOp(), *C, WO->getNoWrapKind());

1300

1301// If overflow is false, %x is constrained to NWR. If overflow is true, %x is

1302// constrained to it's inverse (all values that might cause overflow).

1303if (IsTrueDest)

1304 NWR = NWR.inverse();

1305returnValueLatticeElement::getRange(NWR);

1306}

1307

1308std::optional<ValueLatticeElement>

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

1310bool IsTrueDest,bool UseBlockValue,

1311unsignedDepth) {

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

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

1314

1315if (auto *EVI = dyn_cast<ExtractValueInst>(Cond))

1316if (auto *WO = dyn_cast<WithOverflowInst>(EVI->getAggregateOperand()))

1317if (EVI->getNumIndices() == 1 && *EVI->idx_begin() == 1)

1318returngetValueFromOverflowCondition(Val, WO, IsTrueDest);

1319

1320if (++Depth ==MaxAnalysisRecursionDepth)

1321returnValueLatticeElement::getOverdefined();

1322

1323Value *N;

1324if (match(Cond,m_Not(m_Value(N))))

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

1326

1327Value *L, *R;

1328bool IsAnd;

1329if (match(Cond,m_LogicalAnd(m_Value(L),m_Value(R))))

1330 IsAnd =true;

1331elseif (match(Cond,m_LogicalOr(m_Value(L),m_Value(R))))

1332 IsAnd =false;

1333else

1334returnValueLatticeElement::getOverdefined();

1335

1336 std::optional<ValueLatticeElement> LV =

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

1338if (!LV)

1339return std::nullopt;

1340 std::optional<ValueLatticeElement> RV =

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

1342if (!RV)

1343return std::nullopt;

1344

1345// if (L && R) -> intersect L and R

1346// if (!(L || R)) -> intersect !L and !R

1347// if (L || R) -> union L and R

1348// if (!(L && R)) -> union !L and !R

1349if (IsTrueDest ^ IsAnd) {

1350 LV->mergeIn(*RV);

1351return *LV;

1352 }

1353

1354return LV->intersect(*RV);

1355}

1356

1357// Return true if Usr has Op as an operand, otherwise false.

1358staticboolusesOperand(User *Usr,Value *Op) {

1359returnis_contained(Usr->operands(),Op);

1360}

1361

1362// Return true if the instruction type of Val is supported by

1363// constantFoldUser(). Currently CastInst, BinaryOperator and FreezeInst only.

1364// Call this before calling constantFoldUser() to find out if it's even worth

1365// attempting to call it.

1366staticboolisOperationFoldable(User *Usr) {

1367return isa<CastInst>(Usr) || isa<BinaryOperator>(Usr) || isa<FreezeInst>(Usr);

1368}

1369

1370// Check if Usr can be simplified to an integer constant when the value of one

1371// of its operands Op is an integer constant OpConstVal. If so, return it as an

1372// lattice value range with a single element or otherwise return an overdefined

1373// lattice value.

1374staticValueLatticeElement constantFoldUser(User *Usr,Value *Op,

1375constAPInt &OpConstVal,

1376constDataLayout &DL) {

1377assert(isOperationFoldable(Usr) &&"Precondition");

1378Constant* OpConst =Constant::getIntegerValue(Op->getType(), OpConstVal);

1379// Check if Usr can be simplified to a constant.

1380if (auto *CI = dyn_cast<CastInst>(Usr)) {

1381assert(CI->getOperand(0) ==Op &&"Operand 0 isn't Op");

1382if (auto *C = dyn_cast_or_null<ConstantInt>(

1383simplifyCastInst(CI->getOpcode(), OpConst,

1384 CI->getDestTy(),DL))) {

1385returnValueLatticeElement::getRange(ConstantRange(C->getValue()));

1386 }

1387 }elseif (auto *BO = dyn_cast<BinaryOperator>(Usr)) {

1388bool Op0Match = BO->getOperand(0) ==Op;

1389bool Op1Match = BO->getOperand(1) ==Op;

1390assert((Op0Match || Op1Match) &&

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

1392Value *LHS = Op0Match ? OpConst : BO->getOperand(0);

1393Value *RHS = Op1Match ? OpConst : BO->getOperand(1);

1394if (auto *C = dyn_cast_or_null<ConstantInt>(

1395simplifyBinOp(BO->getOpcode(),LHS,RHS,DL))) {

1396returnValueLatticeElement::getRange(ConstantRange(C->getValue()));

1397 }

1398 }elseif (isa<FreezeInst>(Usr)) {

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

1400returnValueLatticeElement::getRange(ConstantRange(OpConstVal));

1401 }

1402returnValueLatticeElement::getOverdefined();

1403}

1404

1405/// Compute the value of Val on the edge BBFrom -> BBTo.

1406std::optional<ValueLatticeElement>

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

1408BasicBlock *BBTo,bool UseBlockValue) {

1409// TODO: Handle more complex conditionals. If (v == 0 || v2 < 1) is false, we

1410// know that v != 0.

1411if (BranchInst *BI = dyn_cast<BranchInst>(BBFrom->getTerminator())) {

1412// If this is a conditional branch and only one successor goes to BBTo, then

1413// we may be able to infer something from the condition.

1414if (BI->isConditional() &&

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

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

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

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

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

1420

1421// If V is the condition of the branch itself, then we know exactly what

1422// it is.

1423// NB: The condition on a `br` can't be a vector type.

1424if (Condition == Val)

1425returnValueLatticeElement::get(ConstantInt::get(

1426Type::getInt1Ty(Val->getContext()), isTrueDest));

1427

1428// If the condition of the branch is an equality comparison, we may be

1429// able to infer the value.

1430 std::optional<ValueLatticeElement>Result =

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

1432if (!Result)

1433return std::nullopt;

1434

1435if (!Result->isOverdefined())

1436returnResult;

1437

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

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

1440// Check with isOperationFoldable() first to avoid linearly iterating

1441// over the operands unnecessarily which can be expensive for

1442// instructions with many operands.

1443if (isa<IntegerType>(Usr->getType()) &&isOperationFoldable(Usr)) {

1444constDataLayout &DL = BBTo->getDataLayout();

1445if (usesOperand(Usr, Condition)) {

1446// If Val has Condition as an operand and Val can be folded into a

1447// constant with either Condition == true or Condition == false,

1448// propagate the constant.

1449// eg.

1450// ; %Val is true on the edge to %then.

1451// %Val = and i1 %Condition, true.

1452// br %Condition, label %then, label %else

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

1454Result =constantFoldUser(Usr, Condition, ConditionVal, DL);

1455 }else {

1456// If one of Val's operand has an inferred value, we may be able to

1457// infer the value of Val.

1458// eg.

1459// ; %Val is 94 on the edge to %then.

1460// %Val = add i8 %Op, 1

1461// %Condition = icmp eq i8 %Op, 93

1462// br i1 %Condition, label %then, label %else

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

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

1465ValueLatticeElement OpLatticeVal = *getValueFromCondition(

1466Op, Condition, isTrueDest,/*UseBlockValue*/false);

1467if (std::optional<APInt> OpConst =

1468 OpLatticeVal.asConstantInteger()) {

1469Result =constantFoldUser(Usr,Op, *OpConst, DL);

1470break;

1471 }

1472 }

1473 }

1474 }

1475 }

1476if (!Result->isOverdefined())

1477returnResult;

1478 }

1479 }

1480

1481// If the edge was formed by a switch on the value, then we may know exactly

1482// what it is.

1483if (SwitchInst *SI = dyn_cast<SwitchInst>(BBFrom->getTerminator())) {

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

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

1486returnValueLatticeElement::getOverdefined();

1487bool ValUsesConditionAndMayBeFoldable =false;

1488if (Condition != Val) {

1489// Check if Val has Condition as an operand.

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

1491 ValUsesConditionAndMayBeFoldable =isOperationFoldable(Usr) &&

1492usesOperand(Usr, Condition);

1493if (!ValUsesConditionAndMayBeFoldable)

1494returnValueLatticeElement::getOverdefined();

1495 }

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

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

1498

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

1500unsignedBitWidth = Val->getType()->getIntegerBitWidth();

1501ConstantRange EdgesVals(BitWidth, DefaultCase/*isFullSet*/);

1502

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

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

1505ConstantRange EdgeVal(CaseValue);

1506if (ValUsesConditionAndMayBeFoldable) {

1507User *Usr = cast<User>(Val);

1508constDataLayout &DL = BBTo->getDataLayout();

1509ValueLatticeElement EdgeLatticeVal =

1510constantFoldUser(Usr, Condition, CaseValue, DL);

1511if (EdgeLatticeVal.isOverdefined())

1512returnValueLatticeElement::getOverdefined();

1513 EdgeVal = EdgeLatticeVal.getConstantRange();

1514 }

1515if (DefaultCase) {

1516// It is possible that the default destination is the destination of

1517// some cases. We cannot perform difference for those cases.

1518// We know Condition != CaseValue in BBTo. In some cases we can use

1519// this to infer Val == f(Condition) is != f(CaseValue). For now, we

1520// only do this when f is identity (i.e. Val == Condition), but we

1521// should be able to do this for any injective f.

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

1523 EdgesVals = EdgesVals.difference(EdgeVal);

1524 }elseif (Case.getCaseSuccessor() == BBTo)

1525 EdgesVals = EdgesVals.unionWith(EdgeVal);

1526 }

1527returnValueLatticeElement::getRange(std::move(EdgesVals));

1528 }

1529returnValueLatticeElement::getOverdefined();

1530}

1531

1532/// Compute the value of Val on the edge BBFrom -> BBTo or the value at

1533/// the basic block if the edge does not constrain Val.

1534std::optional<ValueLatticeElement>

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

1536BasicBlock *BBTo,Instruction *CxtI) {

1537// If already a constant, there is nothing to compute.

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

1539returnValueLatticeElement::get(VC);

1540

1541 std::optional<ValueLatticeElement> LocalResult =

1542 getEdgeValueLocal(Val, BBFrom, BBTo,/*UseBlockValue*/true);

1543if (!LocalResult)

1544return std::nullopt;

1545

1546if (hasSingleValue(*LocalResult))

1547// Can't get any more precise here

1548return LocalResult;

1549

1550 std::optional<ValueLatticeElement> OptInBlock =

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

1552if (!OptInBlock)

1553return std::nullopt;

1554ValueLatticeElement &InBlock = *OptInBlock;

1555

1556// We can use the context instruction (generically the ultimate instruction

1557// the calling pass is trying to simplify) here, even though the result of

1558// this function is generally cached when called from the solve* functions

1559// (and that cached result might be used with queries using a different

1560// context instruction), because when this function is called from the solve*

1561// functions, the context instruction is not provided. When called from

1562// LazyValueInfoImpl::getValueOnEdge, the context instruction is provided,

1563// but then the result is not cached.

1564 intersectAssumeOrGuardBlockValueConstantRange(Val,InBlock, CxtI);

1565

1566return LocalResult->intersect(InBlock);

1567}

1568

1569ValueLatticeElement LazyValueInfoImpl::getValueInBlock(Value *V,BasicBlock *BB,

1570Instruction *CxtI) {

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

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

1573

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

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

1576if (!OptResult) {

1577 solve();

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

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

1580 }

1581

1582ValueLatticeElement Result = *OptResult;

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

1584return Result;

1585}

1586

1587ValueLatticeElement LazyValueInfoImpl::getValueAt(Value *V,Instruction *CxtI) {

1588LLVM_DEBUG(dbgs() <<"LVI Getting value " << *V <<" at '" << CxtI->getName()

1589 <<"'\n");

1590

1591if (auto *C = dyn_cast<Constant>(V))

1592returnValueLatticeElement::get(C);

1593

1594ValueLatticeElement Result =ValueLatticeElement::getOverdefined();

1595if (auto *I = dyn_cast<Instruction>(V))

1596 Result =getFromRangeMetadata(I);

1597 intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI);

1598

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

1600return Result;

1601}

1602

1603ValueLatticeElement LazyValueInfoImpl::

1604getValueOnEdge(Value *V,BasicBlock *FromBB,BasicBlock *ToBB,

1605Instruction *CxtI) {

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

1607 << FromBB->getName() <<"' to '" << ToBB->getName()

1608 <<"'\n");

1609

1610 std::optional<ValueLatticeElement> Result =

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

1612while (!Result) {

1613// As the worklist only explicitly tracks block values (but not edge values)

1614// we may have to call solve() multiple times, as the edge value calculation

1615// may request additional block values.

1616 solve();

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

1618 }

1619

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

1621return *Result;

1622}

1623

1624ValueLatticeElement LazyValueInfoImpl::getValueAtUse(constUse &U) {

1625Value *V = U.get();

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

1627ValueLatticeElement VL =getValueInBlock(V, CxtI->getParent(), CxtI);

1628

1629// Check whether the only (possibly transitive) use of the value is in a

1630// position where V can be constrained by a select or branch condition.

1631constUse *CurrU = &U;

1632// TODO: Increase limit?

1633constunsigned MaxUsesToInspect = 3;

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

1635 std::optional<ValueLatticeElement> CondVal;

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

1637if (auto *SI = dyn_cast<SelectInst>(CurrI)) {

1638// If the value is undef, a different value may be chosen in

1639// the select condition and at use.

1640if (!isGuaranteedNotToBeUndef(SI->getCondition(), AC))

1641break;

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

1643 CondVal =

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

1645/*UseBlockValue*/false);

1646elseif (CurrU->getOperandNo() == 2)

1647 CondVal =

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

1649/*UseBlockValue*/false);

1650 }elseif (auto *PHI = dyn_cast<PHINode>(CurrI)) {

1651// TODO: Use non-local query?

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

1653PHI->getParent(),/*UseBlockValue*/false);

1654 }

1655if (CondVal)

1656 VL = VL.intersect(*CondVal);

1657

1658// Only follow one-use chain, to allow direct intersection of conditions.

1659// If there are multiple uses, we would have to intersect with the union of

1660// all conditions at different uses.

1661// Stop walking if we hit a non-speculatable instruction. Even if the

1662// result is only used under a specific condition, executing the

1663// instruction itself may cause side effects or UB already.

1664// This also disallows looking through phi nodes: If the phi node is part

1665// of a cycle, we might end up reasoning about values from different cycle

1666// iterations (PR60629).

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

1668 !isSafeToSpeculativelyExecuteWithVariableReplaced(CurrI))

1669break;

1670 CurrU = &*CurrI->use_begin();

1671 }

1672return VL;

1673}

1674

1675voidLazyValueInfoImpl::threadEdge(BasicBlock *PredBB,BasicBlock *OldSucc,

1676BasicBlock *NewSucc) {

1677 TheCache.threadEdgeImpl(OldSucc, NewSucc);

1678}

1679

1680//===----------------------------------------------------------------------===//

1681// LazyValueInfo Impl

1682//===----------------------------------------------------------------------===//

1683

1684boolLazyValueInfoWrapperPass::runOnFunction(Function &F) {

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

1686

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

1688 Impl->clear();

1689

1690// Fully lazy.

1691returnfalse;

1692}

1693

1694voidLazyValueInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const{

1695 AU.setPreservesAll();

1696 AU.addRequired<AssumptionCacheTracker>();

1697 AU.addRequired<TargetLibraryInfoWrapperPass>();

1698}

1699

1700LazyValueInfo &LazyValueInfoWrapperPass::getLVI() {return Info; }

1701

1702/// This lazily constructs the LazyValueInfoImpl.

1703LazyValueInfoImpl &LazyValueInfo::getOrCreateImpl(constModule *M) {

1704if (!PImpl) {

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

1706constDataLayout &DL = M->getDataLayout();

1707Function *GuardDecl =

1708Intrinsic::getDeclarationIfExists(M, Intrinsic::experimental_guard);

1709 PImpl =newLazyValueInfoImpl(AC, DL, GuardDecl);

1710 }

1711return *static_cast<LazyValueInfoImpl *>(PImpl);

1712}

1713

1714LazyValueInfoImpl *LazyValueInfo::getImpl() {

1715if (!PImpl)

1716returnnullptr;

1717returnstatic_cast<LazyValueInfoImpl *>(PImpl);

1718}

1719

1720LazyValueInfo::~LazyValueInfo() {releaseMemory(); }

1721

1722voidLazyValueInfo::releaseMemory() {

1723// If the cache was allocated, free it.

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

1725delete &*Impl;

1726 PImpl =nullptr;

1727 }

1728}

1729

1730boolLazyValueInfo::invalidate(Function &F,constPreservedAnalyses &PA,

1731FunctionAnalysisManager::Invalidator &Inv) {

1732// We need to invalidate if we have either failed to preserve this analyses

1733// result directly or if any of its dependencies have been invalidated.

1734auto PAC = PA.getChecker<LazyValueAnalysis>();

1735if (!(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>()))

1736returntrue;

1737

1738returnfalse;

1739}

1740

1741voidLazyValueInfoWrapperPass::releaseMemory() { Info.releaseMemory(); }

1742

1743LazyValueInfo LazyValueAnalysis::run(Function &F,

1744FunctionAnalysisManager &FAM) {

1745auto &AC =FAM.getResult<AssumptionAnalysis>(F);

1746

1747returnLazyValueInfo(&AC, &F.getDataLayout());

1748}

1749

1750/// Returns true if we can statically tell that this value will never be a

1751/// "useful" constant. In practice, this means we've got something like an

1752/// alloca or a malloc call for which a comparison against a constant can

1753/// only be guarding dead code. Note that we are potentially giving up some

1754/// precision in dead code (a constant result) in favour of avoiding a

1755/// expensive search for a easily answered common query.

1756staticboolisKnownNonConstant(Value *V) {

1757 V = V->stripPointerCasts();

1758// The return val of alloc cannot be a Constant.

1759if (isa<AllocaInst>(V))

1760returntrue;

1761returnfalse;

1762}

1763

1764Constant *LazyValueInfo::getConstant(Value *V,Instruction *CxtI) {

1765// Bail out early if V is known not to be a Constant.

1766if (isKnownNonConstant(V))

1767returnnullptr;

1768

1769BasicBlock *BB = CxtI->getParent();

1770ValueLatticeElement Result =

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

1772

1773if (Result.isConstant())

1774return Result.getConstant();

1775if (Result.isConstantRange()) {

1776constConstantRange &CR = Result.getConstantRange();

1777if (constAPInt *SingleVal = CR.getSingleElement())

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

1779 }

1780returnnullptr;

1781}

1782

1783ConstantRange LazyValueInfo::getConstantRange(Value *V,Instruction *CxtI,

1784bool UndefAllowed) {

1785BasicBlock *BB = CxtI->getParent();

1786ValueLatticeElement Result =

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

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

1789}

1790

1791ConstantRange LazyValueInfo::getConstantRangeAtUse(constUse &U,

1792bool UndefAllowed) {

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

1794ValueLatticeElement Result =

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

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

1797}

1798

1799/// Determine whether the specified value is known to be a

1800/// constant on the specified edge. Return null if not.

1801Constant *LazyValueInfo::getConstantOnEdge(Value *V,BasicBlock *FromBB,

1802BasicBlock *ToBB,

1803Instruction *CxtI) {

1804Module *M = FromBB->getModule();

1805ValueLatticeElement Result =

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

1807

1808if (Result.isConstant())

1809return Result.getConstant();

1810if (Result.isConstantRange()) {

1811constConstantRange &CR = Result.getConstantRange();

1812if (constAPInt *SingleVal = CR.getSingleElement())

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

1814 }

1815returnnullptr;

1816}

1817

1818ConstantRange LazyValueInfo::getConstantRangeOnEdge(Value *V,

1819BasicBlock *FromBB,

1820BasicBlock *ToBB,

1821Instruction *CxtI) {

1822Module *M = FromBB->getModule();

1823ValueLatticeElement Result =

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

1825// TODO: Should undef be allowed here?

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

1827}

1828

1829staticConstant *getPredicateResult(CmpInst::Predicate Pred,Constant *C,

1830constValueLatticeElement &Val,

1831constDataLayout &DL) {

1832// If we know the value is a constant, evaluate the conditional.

1833if (Val.isConstant())

1834returnConstantFoldCompareInstOperands(Pred, Val.getConstant(),C,DL);

1835

1836Type *ResTy =CmpInst::makeCmpResultType(C->getType());

1837if (Val.isConstantRange()) {

1838constConstantRange &CR = Val.getConstantRange();

1839ConstantRange RHS =C->toConstantRange();

1840if (CR.icmp(Pred,RHS))

1841returnConstantInt::getTrue(ResTy);

1842if (CR.icmp(CmpInst::getInversePredicate(Pred),RHS))

1843returnConstantInt::getFalse(ResTy);

1844returnnullptr;

1845 }

1846

1847if (Val.isNotConstant()) {

1848// If this is an equality comparison, we can try to fold it knowing that

1849// "V != C1".

1850if (Pred ==ICmpInst::ICMP_EQ) {

1851// !C1 == C -> false iff C1 == C.

1852Constant *Res =ConstantFoldCompareInstOperands(

1853ICmpInst::ICMP_NE, Val.getNotConstant(),C,DL);

1854if (Res && Res->isNullValue())

1855returnConstantInt::getFalse(ResTy);

1856 }elseif (Pred ==ICmpInst::ICMP_NE) {

1857// !C1 != C -> true iff C1 == C.

1858Constant *Res =ConstantFoldCompareInstOperands(

1859ICmpInst::ICMP_NE, Val.getNotConstant(),C,DL);

1860if (Res && Res->isNullValue())

1861returnConstantInt::getTrue(ResTy);

1862 }

1863returnnullptr;

1864 }

1865

1866returnnullptr;

1867}

1868

1869/// Determine whether the specified value comparison with a constant is known to

1870/// be true or false on the specified CFG edge. Pred is a CmpInst predicate.

1871Constant *LazyValueInfo::getPredicateOnEdge(CmpInst::Predicate Pred,Value *V,

1872Constant *C,BasicBlock *FromBB,

1873BasicBlock *ToBB,

1874Instruction *CxtI) {

1875Module *M = FromBB->getModule();

1876ValueLatticeElement Result =

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

1878

1879returngetPredicateResult(Pred,C, Result, M->getDataLayout());

1880}

1881

1882Constant *LazyValueInfo::getPredicateAt(CmpInst::Predicate Pred,Value *V,

1883Constant *C,Instruction *CxtI,

1884bool UseBlockValue) {

1885// Is or is not NonNull are common predicates being queried. If

1886// isKnownNonZero can tell us the result of the predicate, we can

1887// return it quickly. But this is only a fastpath, and falling

1888// through would still be correct.

1889Module *M = CxtI->getModule();

1890constDataLayout &DL = M->getDataLayout();

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

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

1893Type *ResTy =CmpInst::makeCmpResultType(C->getType());

1894if (Pred ==ICmpInst::ICMP_EQ)

1895returnConstantInt::getFalse(ResTy);

1896elseif (Pred ==ICmpInst::ICMP_NE)

1897returnConstantInt::getTrue(ResTy);

1898 }

1899

1900auto &Impl = getOrCreateImpl(M);

1901ValueLatticeElement Result =

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

1903 : Impl.getValueAt(V, CxtI);

1904Constant *Ret =getPredicateResult(Pred,C, Result,DL);

1905if (Ret)

1906return Ret;

1907

1908// Note: The following bit of code is somewhat distinct from the rest of LVI;

1909// LVI as a whole tries to compute a lattice value which is conservatively

1910// correct at a given location. In this case, we have a predicate which we

1911// weren't able to prove about the merged result, and we're pushing that

1912// predicate back along each incoming edge to see if we can prove it

1913// separately for each input. As a motivating example, consider:

1914// bb1:

1915// %v1 = ... ; constantrange<1, 5>

1916// br label %merge

1917// bb2:

1918// %v2 = ... ; constantrange<10, 20>

1919// br label %merge

1920// merge:

1921// %phi = phi [%v1, %v2] ; constantrange<1,20>

1922// %pred = icmp eq i32 %phi, 8

1923// We can't tell from the lattice value for '%phi' that '%pred' is false

1924// along each path, but by checking the predicate over each input separately,

1925// we can.

1926// We limit the search to one step backwards from the current BB and value.

1927// We could consider extending this to search further backwards through the

1928// CFG and/or value graph, but there are non-obvious compile time vs quality

1929// tradeoffs.

1930BasicBlock *BB = CxtI->getParent();

1931

1932// Function entry or an unreachable block. Bail to avoid confusing

1933// analysis below.

1934pred_iterator PI =pred_begin(BB), PE =pred_end(BB);

1935if (PI == PE)

1936returnnullptr;

1937

1938// If V is a PHI node in the same block as the context, we need to ask

1939// questions about the predicate as applied to the incoming value along

1940// each edge. This is useful for eliminating cases where the predicate is

1941// known along all incoming edges.

1942if (auto *PHI = dyn_cast<PHINode>(V))

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

1944Constant *Baseline =nullptr;

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

1946Value *Incoming =PHI->getIncomingValue(i);

1947BasicBlock *PredBB =PHI->getIncomingBlock(i);

1948// Note that PredBB may be BB itself.

1949Constant *Result =

1950getPredicateOnEdge(Pred,Incoming,C, PredBB, BB, CxtI);

1951

1952// Keep going as long as we've seen a consistent known result for

1953// all inputs.

1954 Baseline = (i == 0) ? Result/* First iteration */

1955 : (Baseline == Result ? Baseline

1956 :nullptr);/* All others */

1957if (!Baseline)

1958break;

1959 }

1960if (Baseline)

1961return Baseline;

1962 }

1963

1964// For a comparison where the V is outside this block, it's possible

1965// that we've branched on it before. Look to see if the value is known

1966// on all incoming edges.

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

1968// For predecessor edge, determine if the comparison is true or false

1969// on that edge. If they're all true or all false, we can conclude

1970// the value of the comparison in this block.

1971Constant *Baseline =getPredicateOnEdge(Pred, V,C, *PI, BB, CxtI);

1972if (Baseline) {

1973// Check that all remaining incoming values match the first one.

1974while (++PI != PE) {

1975Constant *Ret =getPredicateOnEdge(Pred, V,C, *PI, BB, CxtI);

1976if (Ret != Baseline)

1977break;

1978 }

1979// If we terminated early, then one of the values didn't match.

1980if (PI == PE) {

1981return Baseline;

1982 }

1983 }

1984 }

1985

1986returnnullptr;

1987}

1988

1989Constant *LazyValueInfo::getPredicateAt(CmpInst::Predicate Pred,Value *LHS,

1990Value *RHS,Instruction *CxtI,

1991bool UseBlockValue) {

1992if (auto *C = dyn_cast<Constant>(RHS))

1993returngetPredicateAt(Pred,LHS,C, CxtI, UseBlockValue);

1994if (auto *C = dyn_cast<Constant>(LHS))

1995returngetPredicateAt(CmpInst::getSwappedPredicate(Pred),RHS,C, CxtI,

1996 UseBlockValue);

1997

1998// Got two non-Constant values. Try to determine the comparison results based

1999// on the block values of the two operands, e.g. because they have

2000// non-overlapping ranges.

2001if (UseBlockValue) {

2002Module *M = CxtI->getModule();

2003ValueLatticeElement L =

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

2005if (L.isOverdefined())

2006returnnullptr;

2007

2008ValueLatticeElement R =

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

2010Type *Ty =CmpInst::makeCmpResultType(LHS->getType());

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

2012 }

2013returnnullptr;

2014}

2015

2016voidLazyValueInfo::threadEdge(BasicBlock *PredBB,BasicBlock *OldSucc,

2017BasicBlock *NewSucc) {

2018if (auto *Impl = getImpl())

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

2020}

2021

2022voidLazyValueInfo::forgetValue(Value *V) {

2023if (auto *Impl = getImpl())

2024 Impl->forgetValue(V);

2025}

2026

2027voidLazyValueInfo::eraseBlock(BasicBlock *BB) {

2028if (auto *Impl = getImpl())

2029 Impl->eraseBlock(BB);

2030}

2031

2032voidLazyValueInfo::clear() {

2033if (auto *Impl = getImpl())

2034 Impl->clear();

2035}

2036

2037voidLazyValueInfo::printLVI(Function &F,DominatorTree &DTree,raw_ostream &OS) {

2038if (auto *Impl = getImpl())

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

2040}

2041

2042// Print the LVI for the function arguments at the start of each basic block.

2043void LazyValueInfoAnnotatedWriter::emitBasicBlockStartAnnot(

2044constBasicBlock *BB,formatted_raw_ostream &OS) {

2045// Find if there are latticevalues defined for arguments of the function.

2046auto *F = BB->getParent();

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

2048ValueLatticeElement Result = LVIImpl->getValueInBlock(

2049const_cast<Argument *>(&Arg),const_cast<BasicBlock *>(BB));

2050if (Result.isUnknown())

2051continue;

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

2053 }

2054}

2055

2056// This function prints the LVI analysis for the instruction I at the beginning

2057// of various basic blocks. It relies on calculated values that are stored in

2058// the LazyValueInfoCache, and in the absence of cached values, recalculate the

2059// LazyValueInfo for `I`, and print that info.

2060void LazyValueInfoAnnotatedWriter::emitInstructionAnnot(

2061constInstruction *I,formatted_raw_ostream &OS) {

2062

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

2064SmallPtrSet<const BasicBlock*, 16> BlocksContainingLVI;

2065// We can generate (solve) LVI values only for blocks that are dominated by

2066// the I's parent. However, to avoid generating LVI for all dominating blocks,

2067// that contain redundant/uninteresting information, we print LVI for

2068// blocks that may use this LVI information (such as immediate successor

2069// blocks, and blocks that contain uses of `I`).

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

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

2072return;

2073ValueLatticeElement Result = LVIImpl->getValueInBlock(

2074const_cast<Instruction *>(I),const_cast<BasicBlock *>(BB));

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

2076 BB->printAsOperand(OS,false);

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

2078 };

2079

2080 printResult(ParentBB);

2081// Print the LVI analysis results for the immediate successor blocks, that

2082// are dominated by `ParentBB`.

2083for (constauto *BBSucc :successors(ParentBB))

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

2085 printResult(BBSucc);

2086

2087// Print LVI in blocks where `I` is used.

2088for (constauto *U :I->users())

2089if (auto *UseI = dyn_cast<Instruction>(U))

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

2091 printResult(UseI->getParent());

2092

2093}

2094

2095PreservedAnalyses LazyValueInfoPrinterPass::run(Function &F,

2096FunctionAnalysisManager &AM) {

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

2098auto &LVI = AM.getResult<LazyValueAnalysis>(F);

2099auto &DTree = AM.getResult<DominatorTreeAnalysis>(F);

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

2101returnPreservedAnalyses::all();

2102}

PHI

Rewrite undef for PHI

Definition:AMDGPURewriteUndefForPHI.cpp:100

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

Definition:ARMSLSHardening.cpp:73

Passes.h

AssemblyAnnotationWriter.h

AssumptionCache.h

true

basic Basic Alias true

Definition:BasicAliasAnalysis.cpp:1981

Analysis

block Block Frequency Analysis

Definition:BlockFrequencyInfo.cpp:300

ConstantFolding.h

ConstantRange.h

Constants.h

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

DataLayout.h

value

Given that RA is a live value

Definition:DeadArgumentElimination.cpp:716

Debug.h

LLVM_DEBUG

#define LLVM_DEBUG(...)

Definition:Debug.h:106

DenseSet.h

This file defines the DenseSet and SmallDenseSet classes.

Dominators.h

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

FormattedStream.h

IRTranslator LLVM IR MI

Definition:IRTranslator.cpp:112

CFG.h

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

IntrinsicInst.h

Module.h

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

InitializePasses.h

InstrTypes.h

getRange

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

Helper method to get range from metadata or attribute.

Definition:InstructionSimplify.cpp:3725

InstructionSimplify.h

static bool isOperationFoldable(User *Usr)

Definition:LazyValueInfo.cpp:1366

AddNonNullPointersByInstruction

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

Definition:LazyValueInfo.cpp:631

getRangeViaSLT

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

Definition:LazyValueInfo.cpp:1143

MaxProcessedPerValue

static const unsigned MaxProcessedPerValue

Definition:LazyValueInfo.cpp:51

getValueFromICmpCtpop

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

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

Definition:LazyValueInfo.cpp:1163

usesOperand

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

Definition:LazyValueInfo.cpp:1358

constantFoldUser

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

Definition:LazyValueInfo.cpp:1374

AddNonNullPointer

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

Definition:LazyValueInfo.cpp:625

getFromRangeMetadata

static ValueLatticeElement getFromRangeMetadata(Instruction *BBI)

Definition:LazyValueInfo.cpp:541

getPredicateResult

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

Definition:LazyValueInfo.cpp:1829

getValueFromOverflowCondition

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

Definition:LazyValueInfo.cpp:1288

info

lazy value info

Definition:LazyValueInfo.cpp:61

isKnownNonConstant

static bool isKnownNonConstant(Value *V)

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

Definition:LazyValueInfo.cpp:1756

matchICmpOperand

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

Definition:LazyValueInfo.cpp:1085

LazyValueInfo.h

Information

Natural Loop Information

Definition:LoopInfo.cpp:1221

#define F(x, y, z)

Definition:MD5.cpp:55

#define I(x, y, z)

Definition:MD5.cpp:58

Range

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

uint64_t IntrinsicInst * II

Definition:NVVMIntrRange.cpp:51

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

#define P(N)

FAM

FunctionAnalysisManager FAM

Definition:PassBuilderBindings.cpp:61

INITIALIZE_PASS_DEPENDENCY

#define INITIALIZE_PASS_DEPENDENCY(depName)

Definition:PassSupport.h:55

INITIALIZE_PASS_END

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

Definition:PassSupport.h:57

INITIALIZE_PASS_BEGIN

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

Definition:PassSupport.h:52

PatternMatch.h

Cond

const SmallVectorImpl< MachineOperand > & Cond

Definition:RISCVRedundantCopyElimination.cpp:75

assert

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

STLExtras.h

This file contains some templates that are useful if you are working with the STL at all.

raw_pwrite_stream & OS

Definition:SampleProfWriter.cpp:51

InBlock

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

Definition:SelectionDAGBuilder.cpp:2423

Ptr

@ Ptr

Definition:TargetLibraryInfo.cpp:77

Value * RHS

Definition:X86PartialReduction.cpp:74

LHS

Value * LHS

Definition:X86PartialReduction.cpp:73

PointerType

Definition:ItaniumDemangle.h:627

llvm::APInt

Class for arbitrary precision integers.

Definition:APInt.h:78

llvm::APInt::zext

APInt zext(unsigned width) const

Zero extend to a new width.

Definition:APInt.cpp:986

llvm::APInt::getSignedMinValue

static APInt getSignedMinValue(unsigned numBits)

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

Definition:APInt.h:219

llvm::APInt::getLimitedValue

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.

Definition:APInt.h:475

llvm::APInt::getLowBitsSet

static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)

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

Definition:APInt.h:306

llvm::APInt::getHighBitsSet

static APInt getHighBitsSet(unsigned numBits, unsigned hiBitsSet)

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

Definition:APInt.h:296

llvm::APInt::getZero

static APInt getZero(unsigned numBits)

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

Definition:APInt.h:200

llvm::AllAnalysesOn

This templated class represents "all analyses that operate over <a particular IR unit>" (e....

Definition:Analysis.h:49

llvm::AnalysisManager::Invalidator

API to communicate dependencies between analyses during invalidation.

Definition:PassManager.h:292

llvm::AnalysisManager

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

Definition:PassManager.h:253

llvm::AnalysisManager::getResult

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

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

Definition:PassManager.h:410

llvm::AnalysisUsage

Represent the analysis usage information of a pass.

Definition:PassAnalysisSupport.h:47

llvm::AnalysisUsage::addRequired

AnalysisUsage & addRequired()

Definition:PassAnalysisSupport.h:75

llvm::AnalysisUsage::setPreservesAll

void setPreservesAll()

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

Definition:PassAnalysisSupport.h:130

llvm::Argument

This class represents an incoming formal argument to a Function.

Definition:Argument.h:31

llvm::AssemblyAnnotationWriter

Definition:AssemblyAnnotationWriter.h:27

llvm::AssumptionAnalysis

A function analysis which provides an AssumptionCache.

Definition:AssumptionCache.h:173

llvm::AssumptionCacheTracker

An immutable pass that tracks lazily created AssumptionCache objects.

Definition:AssumptionCache.h:204

llvm::AssumptionCache

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

Definition:AssumptionCache.h:42

llvm::AssumptionCache::clear

void clear()

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

Definition:AssumptionCache.h:136

llvm::AssumptionCache::assumptionsFor

MutableArrayRef< ResultElem > assumptionsFor(const Value *V)

Access the list of assumptions which affect this value.

Definition:AssumptionCache.h:157

llvm::BasicBlock

LLVM Basic Block Representation.

Definition:BasicBlock.h:61

llvm::BasicBlock::begin

iterator begin()

Instruction iterator methods.

Definition:BasicBlock.h:461

llvm::BasicBlock::isEntryBlock

bool isEntryBlock() const

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

Definition:BasicBlock.cpp:593

llvm::BasicBlock::getParent

const Function * getParent() const

Return the enclosing method, or null if none.

Definition:BasicBlock.h:220

llvm::BasicBlock::getDataLayout

const DataLayout & getDataLayout() const

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

Definition:BasicBlock.cpp:296

llvm::BasicBlock::rend

reverse_iterator rend()

Definition:BasicBlock.h:479

llvm::BasicBlock::getTerminator

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

Definition:BasicBlock.h:240

llvm::BasicBlock::back

const Instruction & back() const

Definition:BasicBlock.h:486

llvm::BasicBlock::getModule

const Module * getModule() const

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

Definition:BasicBlock.cpp:292

llvm::BinaryOpIntrinsic::getRHS

Value * getRHS() const

Definition:IntrinsicInst.h:914

llvm::BinaryOpIntrinsic::getNoWrapKind

unsigned getNoWrapKind() const

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

Definition:IntrinsicInst.cpp:835

llvm::BinaryOpIntrinsic::getBinaryOp

Instruction::BinaryOps getBinaryOp() const

Returns the binary operation underlying the intrinsic.

Definition:IntrinsicInst.cpp:802

llvm::BinaryOpIntrinsic::getLHS

Value * getLHS() const

Definition:IntrinsicInst.h:913

llvm::BinaryOperator

Definition:InstrTypes.h:170

llvm::BinaryOperator::getOpcode

BinaryOps getOpcode() const

Definition:InstrTypes.h:370

llvm::BranchInst

Conditional or Unconditional Branch instruction.

Definition:Instructions.h:3016

llvm::CallbackVH

Value handle with callbacks on RAUW and destruction.

Definition:ValueHandle.h:383

llvm::CastInst

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

Definition:InstrTypes.h:444

llvm::CastInst::getOpcode

Instruction::CastOps getOpcode() const

Return the opcode of this CastInst.

Definition:InstrTypes.h:608

llvm::CastInst::getDestTy

Type * getDestTy() const

Return the destination type, as a convenience.

Definition:InstrTypes.h:615

llvm::CmpInst::makeCmpResultType

static Type * makeCmpResultType(Type *opnd_type)

Create a result type for fcmp/icmp.

Definition:InstrTypes.h:980

llvm::CmpInst::Predicate

Predicate

This enumeration lists the possible predicates for CmpInst subclasses.

Definition:InstrTypes.h:673

llvm::CmpInst::ICMP_SLT

@ ICMP_SLT

signed less than

Definition:InstrTypes.h:702

llvm::CmpInst::ICMP_SLE

@ ICMP_SLE

signed less or equal

Definition:InstrTypes.h:703

llvm::CmpInst::ICMP_UGE

@ ICMP_UGE

unsigned greater or equal

Definition:InstrTypes.h:697

llvm::CmpInst::ICMP_UGT

@ ICMP_UGT

unsigned greater than

Definition:InstrTypes.h:696

llvm::CmpInst::ICMP_SGT

@ ICMP_SGT

signed greater than

Definition:InstrTypes.h:700

llvm::CmpInst::ICMP_ULT

@ ICMP_ULT

unsigned less than

Definition:InstrTypes.h:698

llvm::CmpInst::ICMP_EQ

@ ICMP_EQ

equal

Definition:InstrTypes.h:694

llvm::CmpInst::ICMP_NE

@ ICMP_NE

not equal

Definition:InstrTypes.h:695

llvm::CmpInst::ICMP_SGE

@ ICMP_SGE

signed greater or equal

Definition:InstrTypes.h:701

llvm::CmpInst::ICMP_ULE

@ ICMP_ULE

unsigned less or equal

Definition:InstrTypes.h:699

llvm::CmpInst::isSigned

bool isSigned() const

Definition:InstrTypes.h:928

llvm::CmpInst::getSwappedPredicate

Predicate getSwappedPredicate() const

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

Definition:InstrTypes.h:825

llvm::CmpInst::getInversePredicate

Predicate getInversePredicate() const

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

Definition:InstrTypes.h:787

llvm::CmpInst::getPredicate

Predicate getPredicate() const

Return the predicate for this instruction.

Definition:InstrTypes.h:763

llvm::ConstantInt

This is the shared class of boolean and integer constants.

Definition:Constants.h:83

llvm::ConstantInt::getTrue

static ConstantInt * getTrue(LLVMContext &Context)

Definition:Constants.cpp:866

llvm::ConstantInt::getFalse

static ConstantInt * getFalse(LLVMContext &Context)

Definition:Constants.cpp:873

llvm::ConstantPointerNull::get

static ConstantPointerNull * get(PointerType *T)

Static factory methods - Return objects of the specified value.

Definition:Constants.cpp:1826

llvm::ConstantRange

This class represents a range of values.

Definition:ConstantRange.h:47

llvm::ConstantRange::subtract

ConstantRange subtract(const APInt &CI) const

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

Definition:ConstantRange.cpp:549

llvm::ConstantRange::getSingleElement

const APInt * getSingleElement() const

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

Definition:ConstantRange.h:251

llvm::ConstantRange::fromKnownBits

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

Initialize a range based on a known bits constraint.

Definition:ConstantRange.cpp:60

llvm::ConstantRange::castOp

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

Definition:ConstantRange.cpp:778

llvm::ConstantRange::umin

ConstantRange umin(const ConstantRange &Other) const

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

Definition:ConstantRange.cpp:1324

llvm::ConstantRange::getUnsignedMin

APInt getUnsignedMin() const

Return the smallest unsigned value contained in the ConstantRange.

Definition:ConstantRange.cpp:489

llvm::ConstantRange::difference

ConstantRange difference(const ConstantRange &CR) const

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

Definition:ConstantRange.cpp:557

llvm::ConstantRange::icmp

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

Definition:ConstantRange.cpp:243

llvm::ConstantRange::intrinsic

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

Compute range of intrinsic result for the given operand ranges.

Definition:ConstantRange.cpp:1021

llvm::ConstantRange::isEmptySet

bool isEmptySet() const

Return true if this set contains no members.

Definition:ConstantRange.cpp:418

llvm::ConstantRange::abs

ConstantRange abs(bool IntMinIsPoison=false) const

Calculate absolute value range.

Definition:ConstantRange.cpp:1943

llvm::ConstantRange::isIntrinsicSupported

static bool isIntrinsicSupported(Intrinsic::ID IntrinsicID)

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

Definition:ConstantRange.cpp:1001

llvm::ConstantRange::overflowingBinaryOp

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

Definition:ConstantRange.cpp:980

llvm::ConstantRange::isSingleElement

bool isSingleElement() const

Return true if this set contains exactly one member.

Definition:ConstantRange.h:266

llvm::ConstantRange::umax

ConstantRange umax(const ConstantRange &Other) const

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

Definition:ConstantRange.cpp:1296

llvm::ConstantRange::makeAllowedICmpRegion

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

Definition:ConstantRange.cpp:98

llvm::ConstantRange::unionWith

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

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

Definition:ConstantRange.cpp:687

llvm::ConstantRange::makeExactICmpRegion

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

Definition:ConstantRange.cpp:158

llvm::ConstantRange::inverse

ConstantRange inverse() const

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

Definition:ConstantRange.cpp:1935

llvm::ConstantRange::getUnsignedMax

APInt getUnsignedMax() const

Return the largest unsigned value contained in the ConstantRange.

Definition:ConstantRange.cpp:483

llvm::ConstantRange::intersectWith

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

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

Definition:ConstantRange.cpp:581

llvm::ConstantRange::makeMaskNotEqualRange

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

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

Definition:ConstantRange.cpp:397

llvm::ConstantRange::getNonEmpty

static ConstantRange getNonEmpty(APInt Lower, APInt Upper)

Create non-empty constant range with the given bounds.

Definition:ConstantRange.h:84

llvm::ConstantRange::smin

ConstantRange smin(const ConstantRange &Other) const

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

Definition:ConstantRange.cpp:1310

llvm::ConstantRange::getBitWidth

uint32_t getBitWidth() const

Get the bit width of this ConstantRange.

Definition:ConstantRange.h:209

llvm::ConstantRange::smax

ConstantRange smax(const ConstantRange &Other) const

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

Definition:ConstantRange.cpp:1282

llvm::ConstantRange::binaryOp

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

Definition:ConstantRange.cpp:935

llvm::ConstantRange::makeExactNoWrapRegion

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.

Definition:ConstantRange.cpp:389

llvm::Constant

This is an important base class in LLVM.

Definition:Constant.h:42

llvm::Constant::getIntegerValue

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

Definition:Constants.cpp:403

llvm::Constant::toConstantRange

ConstantRange toConstantRange() const

Convert constant to an approximate constant range.

Definition:Constants.cpp:1785

llvm::Constant::getNullValue

static Constant * getNullValue(Type *Ty)

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

Definition:Constants.cpp:373

llvm::Constant::isNullValue

bool isNullValue() const

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

Definition:Constants.cpp:90

llvm::DWARFExpression::Operation

This class represents an Operation in the Expression.

Definition:DWARFExpression.h:32

llvm::DataLayout

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

Definition:DataLayout.h:63

llvm::DenseMapBase::find_as

iterator find_as(const LookupKeyT &Val)

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

Definition:DenseMap.h:176

llvm::DenseMapBase::end

iterator end()

Definition:DenseMap.h:84

llvm::DenseMapBase::insert

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

Definition:DenseMap.h:211

llvm::DenseMapBase::clear

void clear()

Definition:DenseMap.h:110

llvm::DenseMap

Definition:DenseMap.h:727

llvm::DenseSet

Implements a dense probed hash-table based set.

Definition:DenseSet.h:278

llvm::DominatorTreeAnalysis

Analysis pass which computes a DominatorTree.

Definition:Dominators.h:279

llvm::DominatorTree

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

Definition:Dominators.h:162

llvm::DominatorTree::dominates

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

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

Definition:Dominators.cpp:122

llvm::ExtractValueInst

This instruction extracts a struct member or array element value from an aggregate value.

Definition:Instructions.h:2397

llvm::ExtractValueInst::getIndices

ArrayRef< unsigned > getIndices() const

Definition:Instructions.h:2449

llvm::ExtractValueInst::getNumIndices

unsigned getNumIndices() const

Definition:Instructions.h:2453

llvm::ExtractValueInst::getAggregateOperand

Value * getAggregateOperand()

Definition:Instructions.h:2439

llvm::ExtractValueInst::idx_begin

idx_iterator idx_begin() const

Definition:Instructions.h:2433

llvm::FunctionPass

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

Definition:Pass.h:310

llvm::Function

Definition:Function.h:63

llvm::ICmpInst

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

Definition:Instructions.h:1158

llvm::ICmpInst::isEquality

static bool isEquality(Predicate P)

Return true if this predicate is either EQ or NE.

Definition:Instructions.h:1285

llvm::InsertElementInst

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

Definition:Instructions.h:1834

llvm::Instruction

Definition:Instruction.h:68

llvm::Instruction::getModule

const Module * getModule() const

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

Definition:Instruction.cpp:68

llvm::Instruction::getMetadata

MDNode * getMetadata(unsigned KindID) const

Get the metadata of given kind attached to this Instruction.

Definition:Instruction.h:426

llvm::Instruction::getOpcode

unsigned getOpcode() const

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

Definition:Instruction.h:310

llvm::Instruction::getDataLayout

const DataLayout & getDataLayout() const

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

Definition:Instruction.cpp:76

llvm::IntrinsicInst

A wrapper class for inspecting calls to intrinsic functions.

Definition:IntrinsicInst.h:48

llvm::LazyValueAnalysis

Analysis to compute lazy value information.

Definition:LazyValueInfo.h:139

llvm::LazyValueAnalysis::run

Result run(Function &F, FunctionAnalysisManager &FAM)

Definition:LazyValueInfo.cpp:1743

llvm::LazyValueInfoImpl

Definition:LazyValueInfo.cpp:314

llvm::LazyValueInfoImpl::getValueOnEdge

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:1604

llvm::LazyValueInfoImpl::getValueAt

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:1587

llvm::LazyValueInfoImpl::threadEdge

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:1675

llvm::LazyValueInfoImpl::printLVI

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

Printing the LazyValueInfo Analysis.

Definition:LazyValueInfo.cpp:438

llvm::LazyValueInfoImpl::forgetValue

void forgetValue(Value *V)

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

Definition:LazyValueInfo.cpp:445

llvm::LazyValueInfoImpl::eraseBlock

void eraseBlock(BasicBlock *BB)

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

Definition:LazyValueInfo.cpp:449

llvm::LazyValueInfoImpl::clear

void clear()

Complete flush all previously computed values.

Definition:LazyValueInfo.cpp:433

llvm::LazyValueInfoImpl::LazyValueInfoImpl

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

Definition:LazyValueInfo.cpp:457

llvm::LazyValueInfoImpl::getValueInBlock

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:1569

llvm::LazyValueInfoImpl::getValueAtUse

ValueLatticeElement getValueAtUse(const Use &U)

Definition:LazyValueInfo.cpp:1624

llvm::LazyValueInfoPrinterPass::run

PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

Definition:LazyValueInfo.cpp:2095

llvm::LazyValueInfoWrapperPass

Wrapper around LazyValueInfo.

Definition:LazyValueInfo.h:163

llvm::LazyValueInfoWrapperPass::runOnFunction

bool runOnFunction(Function &F) override

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

Definition:LazyValueInfo.cpp:1684

llvm::LazyValueInfoWrapperPass::releaseMemory

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:1741

llvm::LazyValueInfoWrapperPass::getAnalysisUsage

void getAnalysisUsage(AnalysisUsage &AU) const override

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

Definition:LazyValueInfo.cpp:1694

llvm::LazyValueInfoWrapperPass::ID

static char ID

Definition:LazyValueInfo.h:167

llvm::LazyValueInfoWrapperPass::getLVI

LazyValueInfo & getLVI()

Definition:LazyValueInfo.cpp:1700

llvm::LazyValueInfoWrapperPass::LazyValueInfoWrapperPass

LazyValueInfoWrapperPass()

Definition:LazyValueInfo.cpp:54

llvm::LazyValueInfo

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

Definition:LazyValueInfo.h:32

llvm::LazyValueInfo::eraseBlock

void eraseBlock(BasicBlock *BB)

Inform the analysis cache that we have erased a block.

Definition:LazyValueInfo.cpp:2027

llvm::LazyValueInfo::getConstantRangeAtUse

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:1791

llvm::LazyValueInfo::getConstantRange

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:1783

llvm::LazyValueInfo::threadEdge

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:2016

llvm::LazyValueInfo::getPredicateOnEdge

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:1871

llvm::LazyValueInfo::releaseMemory

void releaseMemory()

Definition:LazyValueInfo.cpp:1722

llvm::LazyValueInfo::getConstantOnEdge

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:1801

llvm::LazyValueInfo::getConstantRangeOnEdge

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:1818

llvm::LazyValueInfo::getConstant

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

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

Definition:LazyValueInfo.cpp:1764

llvm::LazyValueInfo::printLVI

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

Print the \LazyValueInfo Analysis.

Definition:LazyValueInfo.cpp:2037

llvm::LazyValueInfo::forgetValue

void forgetValue(Value *V)

Remove information related to this value from the cache.

Definition:LazyValueInfo.cpp:2022

llvm::LazyValueInfo::clear

void clear()

Complete flush all previously computed values.

Definition:LazyValueInfo.cpp:2032

llvm::LazyValueInfo::getPredicateAt

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:1882

llvm::LazyValueInfo::~LazyValueInfo

~LazyValueInfo()

Definition:LazyValueInfo.cpp:1720

llvm::LazyValueInfo::invalidate

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

Handle invalidation events in the new pass manager.

Definition:LazyValueInfo.cpp:1730

llvm::LoadInst

An instruction for reading from memory.

Definition:Instructions.h:176

llvm::MDNode

Metadata node.

Definition:Metadata.h:1073

llvm::MemIntrinsic

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

Definition:IntrinsicInst.h:1205

llvm::MemTransferInst

This class wraps the llvm.memcpy/memmove intrinsics.

Definition:IntrinsicInst.h:1302

llvm::Module

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

Definition:Module.h:65

llvm::PHINode

Definition:Instructions.h:2600

llvm::PHINode::getIncomingBlock

BasicBlock * getIncomingBlock(unsigned i) const

Return incoming basic block number i.

Definition:Instructions.h:2695

llvm::PHINode::getIncomingValue

Value * getIncomingValue(unsigned i) const

Return incoming value number x.

Definition:Instructions.h:2675

llvm::PHINode::getNumIncomingValues

unsigned getNumIncomingValues() const

Return the number of incoming edges.

Definition:Instructions.h:2671

llvm::PassRegistry::getPassRegistry

static PassRegistry * getPassRegistry()

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

Definition:PassRegistry.cpp:24

llvm::PredIterator

Definition:CFG.h:42

llvm::PreservedAnalyses

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

Definition:Analysis.h:111

llvm::PreservedAnalyses::all

static PreservedAnalyses all()

Construct a special preserved set that preserves all passes.

Definition:Analysis.h:117

llvm::PreservedAnalyses::getChecker

PreservedAnalysisChecker getChecker() const

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

Definition:Analysis.h:264

llvm::SelectInst

This class represents the LLVM 'select' instruction.

Definition:Instructions.h:1657

llvm::SmallDenseMap

Definition:DenseMap.h:883

llvm::SmallDenseSet

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

Definition:DenseSet.h:298

llvm::SmallPtrSetImpl::insert

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

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

Definition:SmallPtrSet.h:384

llvm::SmallPtrSet

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

Definition:SmallPtrSet.h:519

llvm::SmallVectorBase::empty

bool empty() const

Definition:SmallVector.h:81

llvm::SmallVectorTemplateBase::pop_back

void pop_back()

Definition:SmallVector.h:425

llvm::SmallVectorTemplateBase::push_back

void push_back(const T &Elt)

Definition:SmallVector.h:413

llvm::SmallVectorTemplateCommon::back

reference back()

Definition:SmallVector.h:308

llvm::SmallVector

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

Definition:SmallVector.h:1196

llvm::StoreInst

An instruction for storing to memory.

Definition:Instructions.h:292

llvm::SwitchInst

Multiway switch.

Definition:Instructions.h:3154

llvm::TargetLibraryInfoWrapperPass

Definition:TargetLibraryInfo.h:639

llvm::Type

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

Definition:Type.h:45

llvm::Type::getIntegerBitWidth

unsigned getIntegerBitWidth() const

llvm::Type::isIntOrIntVectorTy

bool isIntOrIntVectorTy() const

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

Definition:Type.h:243

llvm::Type::getInt1Ty

static IntegerType * getInt1Ty(LLVMContext &C)

llvm::Type::getPointerAddressSpace

unsigned getPointerAddressSpace() const

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

llvm::Type::getScalarSizeInBits

unsigned getScalarSizeInBits() const LLVM_READONLY

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

llvm::Type::isSized

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

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

Definition:Type.h:310

llvm::Type::isIntegerTy

bool isIntegerTy() const

True if this is an instance of IntegerType.

Definition:Type.h:237

llvm::Use

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

Definition:Use.h:43

llvm::User

Definition:User.h:44

llvm::User::operands

op_range operands()

Definition:User.h:288

llvm::User::getOperand

Value * getOperand(unsigned i) const

Definition:User.h:228

llvm::ValueLatticeElement

This class represents lattice values for constants.

Definition:ValueLattice.h:26

llvm::ValueLatticeElement::getRange

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

Definition:ValueLattice.h:211

llvm::ValueLatticeElement::isOverdefined

bool isOverdefined() const

Definition:ValueLattice.h:250

llvm::ValueLatticeElement::getNot

static ValueLatticeElement getNot(Constant *C)

Definition:ValueLattice.h:205

llvm::ValueLatticeElement::isNotConstant

bool isNotConstant() const

Definition:ValueLattice.h:238

llvm::ValueLatticeElement::asConstantInteger

std::optional< APInt > asConstantInteger() const

Definition:ValueLattice.h:272

llvm::ValueLatticeElement::isConstant

bool isConstant() const

Definition:ValueLattice.h:237

llvm::ValueLatticeElement::getConstantRange

const ConstantRange & getConstantRange(bool UndefAllowed=true) const

Returns the constant range for this value.

Definition:ValueLattice.h:266

llvm::ValueLatticeElement::isConstantRange

bool isConstantRange(bool UndefAllowed=true) const

Returns true if this value is a constant range.

Definition:ValueLattice.h:246

llvm::ValueLatticeElement::get

static ValueLatticeElement get(Constant *C)

Definition:ValueLattice.h:200

llvm::ValueLatticeElement::getNotConstant

Constant * getNotConstant() const

Definition:ValueLattice.h:257

llvm::ValueLatticeElement::intersect

ValueLatticeElement intersect(const ValueLatticeElement &Other) const

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

Definition:ValueLattice.cpp:78

llvm::ValueLatticeElement::getConstant

Constant * getConstant() const

Definition:ValueLattice.h:252

llvm::ValueLatticeElement::mergeIn

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

Updates this object to approximate both this object and RHS.

Definition:ValueLattice.h:399

llvm::ValueLatticeElement::getOverdefined

static ValueLatticeElement getOverdefined()

Definition:ValueLattice.h:228

llvm::Value

LLVM Value Representation.

Definition:Value.h:74

llvm::Value::getType

Type * getType() const

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

Definition:Value.h:255

llvm::Value::stripInBoundsOffsets

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

Strip off pointer casts and inbounds GEPs.

Definition:Value.cpp:786

llvm::Value::use_begin

use_iterator use_begin()

Definition:Value.h:360

llvm::Value::printAsOperand

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.

Definition:AsmWriter.cpp:5144

llvm::Value::use_empty

bool use_empty() const

Definition:Value.h:344

llvm::Value::getContext

LLVMContext & getContext() const

All values hold a context through their type.

Definition:Value.cpp:1075

llvm::Value::getName

StringRef getName() const

Return a constant reference to the value's name.

Definition:Value.cpp:309

llvm::WithOverflowInst

Represents an op.with.overflow intrinsic.

Definition:IntrinsicInst.h:927

llvm::detail::DenseSetImpl::insert

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

Definition:DenseSet.h:213

llvm::detail::DenseSetImpl::clear

void clear()

Definition:DenseSet.h:92

llvm::detail::DenseSetImpl::find_as

iterator find_as(const LookupKeyT &Val)

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

Definition:DenseSet.h:202

llvm::detail::DenseSetImpl::end

iterator end()

Definition:DenseSet.h:182

llvm::detail::DenseSetImpl::erase

bool erase(const ValueT &V)

Definition:DenseSet.h:97

llvm::formatted_raw_ostream

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

Definition:FormattedStream.h:30

llvm::function_ref

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

Definition:STLFunctionalExtras.h:37

llvm::ilist_detail::node_parent_access::getParent

const ParentTy * getParent() const

Definition:ilist_node.h:32

llvm::ilist_node_impl::getIterator

self_iterator getIterator()

Definition:ilist_node.h:132

llvm::raw_ostream

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

Definition:raw_ostream.h:52

unsigned

llvm_unreachable

#define llvm_unreachable(msg)

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

Definition:ErrorHandling.h:143

false

Definition:StackSlotColoring.cpp:193

llvm::BitmaskEnumDetail::Mask

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.

Definition:BitmaskEnum.h:125

llvm::COFF::Entry

@ Entry

Definition:COFF.h:844

llvm::CallingConv::C

@ C

The default llvm calling convention, compatible with C.

Definition:CallingConv.h:34

llvm::Intrinsic::getDeclarationIfExists

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

This version supports overloaded intrinsics.

Definition:Intrinsics.cpp:747

llvm::M68k::MemAddrModeKind::V

@ V

llvm::M68k::MemAddrModeKind::L

@ L

llvm::PatternMatch::m_And

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

Definition:PatternMatch.h:1216

llvm::PatternMatch::m_PtrToIntSameSize

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

Definition:PatternMatch.h:2061

llvm::PatternMatch::m_AShr

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

Definition:PatternMatch.h:1246

llvm::PatternMatch::m_URem

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

Definition:PatternMatch.h:1198

llvm::PatternMatch::m_c_And

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.

Definition:PatternMatch.h:2798

llvm::PatternMatch::m_Trunc

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

Matches Trunc.

Definition:PatternMatch.h:2075

llvm::PatternMatch::match

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

Definition:PatternMatch.h:49

llvm::PatternMatch::m_Specific

specificval_ty m_Specific(const Value *V)

Match if we have a specific specified value.

Definition:PatternMatch.h:885

llvm::PatternMatch::m_LogicalOr

auto m_LogicalOr()

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

Definition:PatternMatch.h:3099

llvm::PatternMatch::m_AddLike

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

Definition:PatternMatch.h:1409

llvm::PatternMatch::m_APInt

apint_match m_APInt(const APInt *&Res)

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

Definition:PatternMatch.h:299

llvm::PatternMatch::m_Value

class_match< Value > m_Value()

Match an arbitrary value and ignore it.

Definition:PatternMatch.h:92

llvm::PatternMatch::m_LogicalAnd

auto m_LogicalAnd()

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

Definition:PatternMatch.h:3081

llvm::PatternMatch::m_Not

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

Definition:PatternMatch.h:2467

llvm::PatternMatch::m_c_Or

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.

Definition:PatternMatch.h:2805

llvm::PatternMatch::m_Sub

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

Definition:PatternMatch.h:1114

llvm::PatternMatch::m_CombineOr

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

Combine two pattern matchers matching L || R.

Definition:PatternMatch.h:239

llvm::RISCVFenceField::R

@ R

Definition:RISCVBaseInfo.h:373

llvm::SIEncodingFamily::SI

@ SI

Definition:SIDefines.h:36

llvm::logicalview::LVAttributeKind::Zero

@ Zero

llvm::ms_demangle::IntrinsicFunctionKind::New

@ New

llvm::ms_demangle::QualifierMangleMode::Result

@ Result

llvm::numbers::e

constexpr double e

Definition:MathExtras.h:47

llvm::tgtok::TrueVal

@ TrueVal

Definition:TGLexer.h:58

llvm::tgtok::FalseVal

@ FalseVal

Definition:TGLexer.h:59

llvm

This is an optimization pass for GlobalISel generic memory operations.

Definition:AddressRanges.h:18

llvm::Offset

@ Offset

Definition:DWP.cpp:480

llvm::isValidAssumeForContext

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

Definition:ValueTracking.cpp:509

llvm::isSafeToSpeculativelyExecuteWithVariableReplaced

bool isSafeToSpeculativelyExecuteWithVariableReplaced(const Instruction *I)

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

Definition:ValueTracking.h:847

llvm::Depth

@ Depth

Definition:SIMachineScheduler.h:36

llvm::pred_end

auto pred_end(const MachineBasicBlock *BB)

Definition:MachineBasicBlock.h:1385

llvm::successors

auto successors(const MachineBasicBlock *BB)

Definition:MachineBasicBlock.h:1376

llvm::make_range

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

Convenience function for iterating over sub-ranges.

Definition:iterator_range.h:77

llvm::append_range

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

Wrapper function to append range R to container C.

Definition:STLExtras.h:2115

llvm::getUnderlyingObject

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

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

Definition:ValueTracking.cpp:6775

llvm::ConstantFoldCompareInstOperands

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.

Definition:ConstantFolding.cpp:1186

llvm::isGuaranteedNotToBeUndef

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.

Definition:ValueTracking.cpp:7863

llvm::getConstantRangeFromMetadata

ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)

Parse out a conservative ConstantRange from !range metadata.

Definition:ConstantRange.cpp:2264

llvm::simplifyCastInst

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

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

Definition:InstructionSimplify.cpp:5399

llvm::createLazyValueInfoPass

FunctionPass * createLazyValueInfoPass()

createLazyValueInfoPass - This creates an instance of the LazyValueInfo pass.

Definition:LazyValueInfo.cpp:65

llvm::MaxAnalysisRecursionDepth

constexpr unsigned MaxAnalysisRecursionDepth

Definition:ValueTracking.h:44

llvm::SPF_ABS

@ SPF_ABS

Floating point maxnum.

Definition:ValueTracking.h:1121

llvm::SPF_NABS

@ SPF_NABS

Absolute value.

Definition:ValueTracking.h:1122

llvm::SPF_UMIN

@ SPF_UMIN

Signed minimum.

Definition:ValueTracking.h:1116

llvm::SPF_UMAX

@ SPF_UMAX

Signed maximum.

Definition:ValueTracking.h:1118

llvm::SPF_SMIN

@ SPF_SMIN

Definition:ValueTracking.h:1115

llvm::SPF_SMAX

@ SPF_SMAX

Unsigned minimum.

Definition:ValueTracking.h:1117

llvm::matchSelectPattern

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

Definition:ValueTracking.cpp:9054

llvm::NullPointerIsDefined

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

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

Definition:Function.cpp:1187

llvm::dbgs

raw_ostream & dbgs()

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

Definition:Debug.cpp:163

llvm::simplifyExtractValueInst

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

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

Definition:InstructionSimplify.cpp:5247

llvm::isKnownNonZero

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.

Definition:ValueTracking.cpp:3494

llvm::simplifyBinOp

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

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

Definition:InstructionSimplify.cpp:6116

llvm::Op

DWARFExpression::Operation Op

Definition:DWARFExpression.cpp:22

llvm::hasSingleValue

static bool hasSingleValue(const ValueLatticeElement &Val)

Definition:ValueLattice.cpp:56

llvm::BitWidth

constexpr unsigned BitWidth

Definition:BitmaskEnum.h:217

llvm::pred_begin

auto pred_begin(const MachineBasicBlock *BB)

Definition:MachineBasicBlock.h:1383

llvm::predecessors

auto predecessors(const MachineBasicBlock *BB)

Definition:MachineBasicBlock.h:1377

llvm::is_contained

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

Returns true if Element is found in Range.

Definition:STLExtras.h:1903

llvm::initializeLazyValueInfoWrapperPassPass

void initializeLazyValueInfoWrapperPassPass(PassRegistry &)

raw_ostream.h

#define N

llvm::AnalysisKey

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

Definition:Analysis.h:28

llvm::Incoming

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

Definition:SILowerI1Copies.h:25

llvm::KnownBits

Definition:KnownBits.h:23

llvm::KnownBits::One

APInt One

Definition:KnownBits.h:25

llvm::KnownBits::Zero

APInt Zero

Definition:KnownBits.h:24

llvm::SelectPatternResult

Definition:ValueTracking.h:1136

llvm::SelectPatternResult::Flavor

SelectPatternFlavor Flavor

Definition:ValueTracking.h:1137

llvm::SelectPatternResult::isMinOrMax

static bool isMinOrMax(SelectPatternFlavor SPF)

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

Definition:ValueTracking.h:1145