LLVM 24.0.0git
SCCPSolver.cpp
Go to the documentation of this file.
1//===- SCCPSolver.cpp - SCCP Utility --------------------------- *- 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// \file
10// This file implements the Sparse Conditional Constant Propagation (SCCP)
11// utility.
12//
13//===----------------------------------------------------------------------===//
14
16#include "llvm/ADT/SetVector.h"
19#include "llvm/Analysis/Loads.h"
25#include "llvm/IR/IRBuilder.h"
26#include "llvm/IR/InstVisitor.h"
28#include "llvm/IR/NoFolder.h"
29#include "llvm/IR/Operator.h"
32#include "llvm/Support/Debug.h"
36#include <cassert>
37#include <utility>
38#include <vector>
39
40using namespace llvm;
41using namespace PatternMatch;
42
43#define DEBUG_TYPE "sccp"
44
45// The maximum number of range extensions allowed for operations requiring
46// widening.
47static const unsigned MaxNumRangeExtensions = 10;
48
49/// Returns MergeOptions with MaxWidenSteps set to MaxNumRangeExtensions.
54
55namespace llvm {
56
58 return LV.isConstant() ||
60}
61
65
69
71 Constant *Const = getConstantOrNull(V);
72 if (!Const)
73 return false;
74 // Replacing `musttail` instructions with constant breaks `musttail` invariant
75 // unless the call itself can be removed.
76 // Calls with "clang.arc.attachedcall" implicitly use the return value and
77 // those uses cannot be updated with a constant.
79 if (CB && ((CB->isMustTailCall() && !wouldInstructionBeTriviallyDead(CB)) ||
82
83 // Don't zap returns of the callee
84 if (F)
86
87 LLVM_DEBUG(dbgs() << " Can\'t treat the result of call " << *CB
88 << " as a constant\n");
89 return false;
90 }
91
92 // For pointer constants derived from PredicateInfo, the constant may have
93 // different provenance. Take this into account during constant pointer
94 // propagation.
95 if (V->getType()->isPointerTy()) {
96 const auto &LV = getLatticeValueFor(V);
97 if (LV.mayHaveDifferentProvenance()) {
98 const DataLayout &DL = getDataLayout();
99 bool Changed = V->replaceUsesWithIf(Const, [&](Use &U) {
100 bool CanReplace = canReplacePointersInUseIfEqual(U, Const, DL);
101 if (CanReplace)
102 LLVM_DEBUG(dbgs() << " Constant pointer: " << *Const << " = " << *V
103 << '\n');
104 return CanReplace;
105 });
106 return Changed;
107 }
108 }
109
110 LLVM_DEBUG(dbgs() << " Constant: " << *Const << " = " << *V << '\n');
111
112 // Replaces all of the uses of a variable with uses of the constant.
113 V->replaceAllUsesWith(Const);
114 return true;
115}
116
117/// Helper for propagting !implicit.ref metadata from callee to caller before
118/// erasing a call instruction. This ensures that references to global objects
119/// (e.g., copyright strings) are preserved even when calls are optimized away.
121 Function *Callee = CB->getCalledFunction();
122 if (!Callee)
123 return;
124
125 if (!Callee->hasMetadata(LLVMContext::MD_implicit_ref))
126 return;
127
128 Function *Caller = CB->getParent()->getParent();
129 if (!Caller)
130 return;
131
133 Callee->getMetadata(LLVMContext::MD_implicit_ref, MDs);
134 for (MDNode *MD : MDs)
135 Caller->addMetadata(LLVMContext::MD_implicit_ref, *MD);
136}
137
138/// Helper for getting ranges from \p Solver. Instructions inserted during
139/// simplification are unavailable in the solver, so we return a full range for
140/// them.
142 const SmallPtrSetImpl<Value *> &InsertedValues) {
143 if (auto *Const = dyn_cast<Constant>(Op))
144 return Const->toConstantRange();
145 if (InsertedValues.contains(Op)) {
146 unsigned Bitwidth = Op->getType()->getScalarSizeInBits();
147 return ConstantRange::getFull(Bitwidth);
148 }
149 return Solver.getLatticeValueFor(Op).asConstantRange(Op->getType(),
150 /*UndefAllowed=*/false);
151}
152
153/// Try to use \p Inst's value range from \p Solver to infer the NUW flag.
154static bool refineInstruction(SCCPSolver &Solver,
155 const SmallPtrSetImpl<Value *> &InsertedValues,
156 Instruction &Inst) {
157 bool Changed = false;
158 auto GetRange = [&Solver, &InsertedValues](Value *Op) {
159 return getRange(Op, Solver, InsertedValues);
160 };
161
163 if (Inst.hasNoSignedWrap() && Inst.hasNoUnsignedWrap())
164 return false;
165
166 auto RangeA = GetRange(Inst.getOperand(0));
167 auto RangeB = GetRange(Inst.getOperand(1));
168 if (!Inst.hasNoUnsignedWrap()) {
170 Instruction::BinaryOps(Inst.getOpcode()), RangeB,
172 if (NUWRange.contains(RangeA)) {
174 Changed = true;
175 }
176 }
177 if (!Inst.hasNoSignedWrap()) {
179 Instruction::BinaryOps(Inst.getOpcode()), RangeB,
181 if (NSWRange.contains(RangeA)) {
182 Inst.setHasNoSignedWrap();
183 Changed = true;
184 }
185 }
186 } else if (isa<PossiblyNonNegInst>(Inst) && !Inst.hasNonNeg()) {
187 auto Range = GetRange(Inst.getOperand(0));
188 if (Range.isAllNonNegative()) {
189 Inst.setNonNeg();
190 Changed = true;
191 }
192 } else if (TruncInst *TI = dyn_cast<TruncInst>(&Inst)) {
193 if (TI->hasNoSignedWrap() && TI->hasNoUnsignedWrap())
194 return false;
195
196 auto Range = GetRange(Inst.getOperand(0));
197 uint64_t DestWidth = TI->getDestTy()->getScalarSizeInBits();
198 if (!TI->hasNoUnsignedWrap()) {
199 if (Range.getActiveBits() <= DestWidth) {
200 TI->setHasNoUnsignedWrap(true);
201 Changed = true;
202 }
203 }
204 if (!TI->hasNoSignedWrap()) {
205 if (Range.getMinSignedBits() <= DestWidth) {
206 TI->setHasNoSignedWrap(true);
207 Changed = true;
208 }
209 }
210 } else if (auto *GEP = dyn_cast<GetElementPtrInst>(&Inst)) {
211 if (GEP->hasNoUnsignedWrap() || !GEP->hasNoUnsignedSignedWrap())
212 return false;
213
214 if (all_of(GEP->indices(),
215 [&](Value *V) { return GetRange(V).isAllNonNegative(); })) {
216 GEP->setNoWrapFlags(GEP->getNoWrapFlags() |
218 Changed = true;
219 }
220 }
221
222 return Changed;
223}
224
225/// Try to replace signed instructions with their unsigned equivalent.
226static bool replaceSignedInst(SCCPSolver &Solver,
227 SmallPtrSetImpl<Value *> &InsertedValues,
228 Instruction &Inst) {
229 // Determine if a signed value is known to be >= 0.
230 auto isNonNegative = [&Solver, &InsertedValues](Value *V) {
231 return getRange(V, Solver, InsertedValues).isAllNonNegative();
232 };
233
234 Instruction *NewInst = nullptr;
235 switch (Inst.getOpcode()) {
236 case Instruction::SIToFP:
237 case Instruction::SExt: {
238 // If the source value is not negative, this is a zext/uitofp.
239 Value *Op0 = Inst.getOperand(0);
240 if (!isNonNegative(Op0))
241 return false;
242 NewInst = CastInst::Create(Inst.getOpcode() == Instruction::SExt
243 ? Instruction::ZExt
244 : Instruction::UIToFP,
245 Op0, Inst.getType(), "", Inst.getIterator());
246 NewInst->setNonNeg();
247 break;
248 }
249 case Instruction::AShr: {
250 // If the shifted value is not negative, this is a logical shift right.
251 Value *Op0 = Inst.getOperand(0);
252 if (!isNonNegative(Op0))
253 return false;
254 NewInst = BinaryOperator::CreateLShr(Op0, Inst.getOperand(1), "", Inst.getIterator());
255 NewInst->setIsExact(Inst.isExact());
256 break;
257 }
258 case Instruction::SDiv:
259 case Instruction::SRem: {
260 // If both operands are not negative, this is the same as udiv/urem.
261 Value *Op0 = Inst.getOperand(0), *Op1 = Inst.getOperand(1);
262 if (!isNonNegative(Op0) || !isNonNegative(Op1))
263 return false;
264 auto NewOpcode = Inst.getOpcode() == Instruction::SDiv ? Instruction::UDiv
265 : Instruction::URem;
266 NewInst = BinaryOperator::Create(NewOpcode, Op0, Op1, "", Inst.getIterator());
267 if (Inst.getOpcode() == Instruction::SDiv)
268 NewInst->setIsExact(Inst.isExact());
269 break;
270 }
271 default:
272 return false;
273 }
274
275 // Wire up the new instruction and update state.
276 assert(NewInst && "Expected replacement instruction");
277 NewInst->takeName(&Inst);
278 InsertedValues.insert(NewInst);
279 Inst.replaceAllUsesWith(NewInst);
280 NewInst->setDebugLoc(Inst.getDebugLoc());
281 Solver.removeLatticeValueFor(&Inst);
282 Inst.eraseFromParent();
283 return true;
284}
285
286/// Try to use \p Inst's value range from \p Solver to simplify it.
288 SmallPtrSetImpl<Value *> &InsertedValues,
289 Instruction &Inst) {
290 auto GetRange = [&Solver, &InsertedValues](Value *Op) {
291 return getRange(Op, Solver, InsertedValues);
292 };
293
294 Value *X;
295 const APInt *RHSC;
296 // Remove masking operations.
297 if (match(&Inst, m_And(m_Value(X), m_LowBitMask(RHSC)))) {
298 ConstantRange LRange = GetRange(X);
299 if (LRange.getUnsignedMax().ule(*RHSC))
300 return X;
301 }
302
303 // Check if we can simplify [us]cmp(X, Y) to X - Y.
304 if (auto *Cmp = dyn_cast<CmpIntrinsic>(&Inst)) {
305 Value *LHS = Cmp->getOperand(0);
306 Value *RHS = Cmp->getOperand(1);
307 unsigned BitWidth = LHS->getType()->getScalarSizeInBits();
308 // Bail out on 1-bit comparisons.
309 if (BitWidth == 1)
310 return nullptr;
311 ConstantRange LRange = GetRange(LHS);
312 if (LRange.isSizeLargerThan(3))
313 return nullptr;
314 ConstantRange RRange = GetRange(RHS);
315 if (RRange.isSizeLargerThan(3))
316 return nullptr;
317 ConstantRange RHSLower = RRange.sub(APInt(BitWidth, 1));
318 ConstantRange RHSUpper = RRange.add(APInt(BitWidth, 1));
320 Cmp->isSigned() ? CmpInst::ICMP_SLE : CmpInst::ICMP_ULE;
321 if (!RHSLower.icmp(Pred, LRange) || !LRange.icmp(Pred, RHSUpper))
322 return nullptr;
323
324 IRBuilder<NoFolder> Builder(&Inst);
325 Value *Sub = Builder.CreateSub(LHS, RHS, Inst.getName(), /*HasNUW=*/false,
326 /*HasNSW=*/Cmp->isSigned());
327 InsertedValues.insert(Sub);
328 if (Sub->getType() != Inst.getType()) {
329 Sub = Builder.CreateSExtOrTrunc(Sub, Inst.getType());
330 InsertedValues.insert(Sub);
331 }
332 return Sub;
333 }
334
335 // Relax range checks.
336 if (auto *ICmp = dyn_cast<ICmpInst>(&Inst)) {
337 Value *X;
338 auto MatchTwoInstructionExactRangeCheck =
339 [&]() -> std::optional<ConstantRange> {
340 const APInt *RHSC;
341 if (!match(ICmp->getOperand(1), m_APInt(RHSC)))
342 return std::nullopt;
343
344 Value *LHS = ICmp->getOperand(0);
345 ICmpInst::Predicate Pred = ICmp->getPredicate();
346 const APInt *Offset;
348 return ConstantRange::makeExactICmpRegion(Pred, *RHSC).sub(*Offset);
349 // Match icmp eq/ne X & NegPow2, C
350 if (ICmp->isEquality()) {
351 const APInt *Mask;
352 if (match(LHS, m_OneUse(m_And(m_Value(X), m_NegatedPower2(Mask)))) &&
353 RHSC->countr_zero() >= Mask->countr_zero()) {
354 ConstantRange CR(*RHSC, *RHSC - *Mask);
355 return Pred == ICmpInst::ICMP_EQ ? CR : CR.inverse();
356 }
357 }
358 return std::nullopt;
359 };
360
361 if (auto CR = MatchTwoInstructionExactRangeCheck()) {
362 ConstantRange LRange = GetRange(X);
363 // Early exit if we know nothing about X.
364 if (LRange.isFullSet())
365 return nullptr;
366 auto ConvertCRToICmp =
367 [&](const std::optional<ConstantRange> &NewCR) -> Value * {
369 APInt RHS;
370 // Check if we can represent NewCR as an icmp predicate.
371 if (NewCR && NewCR->getEquivalentICmp(Pred, RHS)) {
372 IRBuilder<NoFolder> Builder(&Inst);
373 Value *NewICmp =
374 Builder.CreateICmp(Pred, X, ConstantInt::get(X->getType(), RHS));
375 InsertedValues.insert(NewICmp);
376 return NewICmp;
377 }
378 return nullptr;
379 };
380 // We are allowed to refine the comparison to either true or false for out
381 // of range inputs.
382 // Here we refine the comparison to false, and check if we can narrow the
383 // range check to a simpler test.
384 if (auto *V = ConvertCRToICmp(CR->exactIntersectWith(LRange)))
385 return V;
386 // Here we refine the comparison to true, i.e. we relax the range check.
387 if (auto *V = ConvertCRToICmp(CR->exactUnionWith(LRange.inverse())))
388 return V;
389 }
390 }
391
392 return nullptr;
393}
394
396 SmallPtrSetImpl<Value *> &InsertedValues,
397 Statistic &InstRemovedStat,
398 Statistic &InstReplacedStat) {
399 bool MadeChanges = false;
400 for (Instruction &Inst : make_early_inc_range(BB)) {
401 if (Inst.getType()->isVoidTy())
402 continue;
403 if (tryToReplaceWithConstant(&Inst)) {
404 if (isInstructionTriviallyDead(&Inst)) {
405 // Propagate !implicit.ref before erasing the call.
406 if (auto *CB = dyn_cast<CallBase>(&Inst))
408
409 Inst.eraseFromParent();
410 ++InstRemovedStat;
411 }
412 MadeChanges = true;
413 } else if (replaceSignedInst(*this, InsertedValues, Inst)) {
414 MadeChanges = true;
415 ++InstReplacedStat;
416 } else if (refineInstruction(*this, InsertedValues, Inst)) {
417 MadeChanges = true;
418 } else if (auto *V = simplifyInstruction(*this, InsertedValues, Inst)) {
419 Inst.replaceAllUsesWith(V);
420 Inst.eraseFromParent();
421 ++InstRemovedStat;
422 MadeChanges = true;
423 }
424 }
425 return MadeChanges;
426}
427
429 BasicBlock *&NewUnreachableBB) const {
430 SmallPtrSet<BasicBlock *, 8> FeasibleSuccessors;
431 bool HasNonFeasibleEdges = false;
432 for (BasicBlock *Succ : successors(BB)) {
433 if (isEdgeFeasible(BB, Succ))
434 FeasibleSuccessors.insert(Succ);
435 else
436 HasNonFeasibleEdges = true;
437 }
438
439 // All edges feasible, nothing to do.
440 if (!HasNonFeasibleEdges)
441 return false;
442
443 // SCCP can only determine non-feasible edges for br, switch and indirectbr.
444 Instruction *TI = BB->getTerminator();
446 "Terminator must be a br, switch or indirectbr");
447
448 if (FeasibleSuccessors.size() == 0) {
449 // Branch on undef/poison, replace with unreachable.
452 for (BasicBlock *Succ : successors(BB)) {
453 Succ->removePredecessor(BB);
454 if (SeenSuccs.insert(Succ).second)
455 Updates.push_back({DominatorTree::Delete, BB, Succ});
456 }
457 TI->eraseFromParent();
458 new UnreachableInst(BB->getContext(), BB);
459 DTU.applyUpdatesPermissive(Updates);
460 } else if (FeasibleSuccessors.size() == 1) {
461 // Replace with an unconditional branch to the only feasible successor.
462 BasicBlock *OnlyFeasibleSuccessor = *FeasibleSuccessors.begin();
464 bool HaveSeenOnlyFeasibleSuccessor = false;
465 for (BasicBlock *Succ : successors(BB)) {
466 if (Succ == OnlyFeasibleSuccessor && !HaveSeenOnlyFeasibleSuccessor) {
467 // Don't remove the edge to the only feasible successor the first time
468 // we see it. We still do need to remove any multi-edges to it though.
469 HaveSeenOnlyFeasibleSuccessor = true;
470 continue;
471 }
472
473 Succ->removePredecessor(BB);
474 Updates.push_back({DominatorTree::Delete, BB, Succ});
475 }
476
477 Instruction *BI = UncondBrInst::Create(OnlyFeasibleSuccessor, BB);
478 BI->setDebugLoc(TI->getDebugLoc());
479 TI->eraseFromParent();
480 DTU.applyUpdatesPermissive(Updates);
481 } else if (FeasibleSuccessors.size() > 1) {
484
485 // If the default destination is unfeasible it will never be taken. Replace
486 // it with a new block with a single Unreachable instruction.
487 BasicBlock *DefaultDest = SI->getDefaultDest();
488 if (!FeasibleSuccessors.contains(DefaultDest)) {
489 if (!NewUnreachableBB) {
490 NewUnreachableBB =
491 BasicBlock::Create(DefaultDest->getContext(), "default.unreachable",
492 DefaultDest->getParent(), DefaultDest);
493 auto *UI =
494 new UnreachableInst(DefaultDest->getContext(), NewUnreachableBB);
495 UI->setDebugLoc(DebugLoc::getTemporary());
496 }
497
498 DefaultDest->removePredecessor(BB);
499 SI->setDefaultDest(NewUnreachableBB);
500 Updates.push_back({DominatorTree::Delete, BB, DefaultDest});
501 Updates.push_back({DominatorTree::Insert, BB, NewUnreachableBB});
502 }
503
504 for (auto CI = SI->case_begin(); CI != SI->case_end();) {
505 if (FeasibleSuccessors.contains(CI->getCaseSuccessor())) {
506 ++CI;
507 continue;
508 }
509
510 BasicBlock *Succ = CI->getCaseSuccessor();
511 Succ->removePredecessor(BB);
512 Updates.push_back({DominatorTree::Delete, BB, Succ});
513 SI.removeCase(CI);
514 // Don't increment CI, as we removed a case.
515 }
516
517 DTU.applyUpdatesPermissive(Updates);
518 } else {
519 llvm_unreachable("Must have at least one feasible successor");
520 }
521 return true;
522}
523
524static void inferAttribute(Function *F, unsigned AttrIndex,
525 const ValueLatticeElement &Val) {
526 // If there is a known constant range for the value, add range attribute.
527 if (Val.isConstantRange() && !Val.getConstantRange().isSingleElement()) {
528 // Do not add range attribute if the value may include undef.
530 return;
531
532 // Take the intersection of the existing attribute and the inferred range.
533 Attribute OldAttr = F->getAttributeAtIndex(AttrIndex, Attribute::Range);
535 if (OldAttr.isValid())
536 CR = CR.intersectWith(OldAttr.getRange());
537 F->addAttributeAtIndex(
538 AttrIndex, Attribute::get(F->getContext(), Attribute::Range, CR));
539 return;
540 }
541 // Infer nonnull attribute.
542 if (Val.isNotConstant() && Val.getNotConstant()->getType()->isPointerTy() &&
543 Val.getNotConstant()->isNullValue() &&
544 !F->hasAttributeAtIndex(AttrIndex, Attribute::NonNull)) {
545 F->addAttributeAtIndex(AttrIndex,
546 Attribute::get(F->getContext(), Attribute::NonNull));
547 }
548}
549
551 for (const auto &[F, ReturnValue] : getTrackedRetVals())
552 inferAttribute(F, AttributeList::ReturnIndex, ReturnValue);
553}
554
557 if (!isBlockExecutable(&F->front()))
558 continue;
559 for (Argument &A : F->args())
560 if (!A.getType()->isStructTy())
561 inferAttribute(F, AttributeList::FirstArgIndex + A.getArgNo(),
563 }
564}
565
566/// Helper class for SCCPSolver. This implements the instruction visitor and
567/// holds all the state.
568class SCCPInstVisitor : public InstVisitor<SCCPInstVisitor> {
569 const DataLayout &DL;
570 std::function<const TargetLibraryInfo &(Function &)> GetTLI;
571 /// Basic blocks that are executable (but may not have been visited yet).
572 SmallPtrSet<BasicBlock *, 8> BBExecutable;
573 /// Basic blocks that are executable and have been visited at least once.
576 ValueState; // The state each value is in.
577
578 /// StructValueState - This maintains ValueState for values that have
579 /// StructType, for example for formal arguments, calls, insertelement, etc.
581
582 /// GlobalValue - If we are tracking any values for the contents of a global
583 /// variable, we keep a mapping from the constant accessor to the element of
584 /// the global, to the currently known value. If the value becomes
585 /// overdefined, it's entry is simply removed from this map.
587
588 /// TrackedRetVals - If we are tracking arguments into and the return
589 /// value out of a function, it will have an entry in this map, indicating
590 /// what the known return value for the function is.
592
593 /// TrackedMultipleRetVals - Same as TrackedRetVals, but used for functions
594 /// that return multiple values.
596 TrackedMultipleRetVals;
597
598 /// The set of values whose lattice has been invalidated.
599 /// Populated by resetLatticeValueFor(), cleared after resolving undefs.
600 DenseSet<Value *> Invalidated;
601
602 /// MRVFunctionsTracked - Each function in TrackedMultipleRetVals is
603 /// represented here for efficient lookup.
604 SmallPtrSet<Function *, 16> MRVFunctionsTracked;
605
606 /// A list of functions whose return cannot be modified.
607 SmallPtrSet<Function *, 16> MustPreserveReturnsInFunctions;
608
609 /// TrackingIncomingArguments - This is the set of functions for whose
610 /// arguments we make optimistic assumptions about and try to prove as
611 /// constants.
612 SmallPtrSet<Function *, 16> TrackingIncomingArguments;
613
614 /// Worklist of instructions to re-visit. This only includes instructions
615 /// in blocks that have already been visited at least once.
617
618 /// Current instruction while visiting a block for the first time, used to
619 /// avoid unnecessary instruction worklist insertions. Null if an instruction
620 /// is visited outside a whole-block visitation.
621 Instruction *CurI = nullptr;
622
623 // The BasicBlock work list
625
626 /// KnownFeasibleEdges - Entries in this set are edges which have already had
627 /// PHI nodes retriggered.
628 using Edge = std::pair<BasicBlock *, BasicBlock *>;
629 DenseSet<Edge> KnownFeasibleEdges;
630
632
634
635 LLVMContext &Ctx;
636
637 BumpPtrAllocator PredicateInfoAllocator;
638
639private:
640 ConstantInt *getConstantInt(const ValueLatticeElement &IV, Type *Ty) const {
642 }
643
644 /// Push instruction \p I to the worklist.
645 void pushToWorkList(Instruction *I);
646
647 /// Push users of value \p V to the worklist.
648 void pushUsersToWorkList(Value *V);
649
650 /// Like pushUsersToWorkList(), but also prints a debug message with the
651 /// updated value.
652 void pushUsersToWorkListMsg(ValueLatticeElement &IV, Value *V);
653
654 // markConstant - Make a value be marked as "constant". If the value
655 // is not already a constant, add it to the instruction work list so that
656 // the users of the instruction are updated later.
657 bool markConstant(ValueLatticeElement &IV, Value *V, Constant *C,
658 bool MayIncludeUndef = false);
659
660 bool markConstant(Value *V, Constant *C) {
661 assert(!V->getType()->isStructTy() && "structs should use mergeInValue");
662 return markConstant(ValueState[V], V, C);
663 }
664
665 bool markNotConstant(ValueLatticeElement &IV, Value *V, Constant *C);
666
667 bool markNotNull(ValueLatticeElement &IV, Value *V) {
668 return markNotConstant(IV, V, Constant::getNullValue(V->getType()));
669 }
670
671 /// markConstantRange - Mark the object as constant range with \p CR. If the
672 /// object is not a constant range with the range \p CR, add it to the
673 /// instruction work list so that the users of the instruction are updated
674 /// later.
675 bool markConstantRange(ValueLatticeElement &IV, Value *V,
676 const ConstantRange &CR);
677
678 // markOverdefined - Make a value be marked as "overdefined". If the
679 // value is not already overdefined, add it to the overdefined instruction
680 // work list so that the users of the instruction are updated later.
681 bool markOverdefined(ValueLatticeElement &IV, Value *V);
682
683 /// Merge \p MergeWithV into \p IV and push \p V to the worklist, if \p IV
684 /// changes.
685 bool mergeInValue(ValueLatticeElement &IV, Value *V,
686 const ValueLatticeElement &MergeWithV,
688 /*MayIncludeUndef=*/false, /*CheckWiden=*/false});
689
690 /// getValueState - Return the ValueLatticeElement object that corresponds to
691 /// the value. This function handles the case when the value hasn't been seen
692 /// yet by properly seeding constants etc.
693 ValueLatticeElement &getValueState(Value *V) {
694 assert(!V->getType()->isStructTy() && "Should use getStructValueState");
695
696 auto I = ValueState.try_emplace(V);
697 ValueLatticeElement &LV = I.first->second;
698
699 if (!I.second)
700 return LV; // Common case, already in the map.
701
702 if (auto *C = dyn_cast<Constant>(V))
703 LV.markConstant(C); // Constants are constant
704
705 // All others are unknown by default.
706 return LV;
707 }
708
709 /// getStructValueState - Return the ValueLatticeElement object that
710 /// corresponds to the value/field pair. This function handles the case when
711 /// the value hasn't been seen yet by properly seeding constants etc.
712 ValueLatticeElement &getStructValueState(Value *V, unsigned i) {
713 assert(V->getType()->isStructTy() && "Should use getValueState");
714 assert(i < cast<StructType>(V->getType())->getNumElements() &&
715 "Invalid element #");
716
717 auto I = StructValueState.insert(
718 std::make_pair(std::make_pair(V, i), ValueLatticeElement()));
719 ValueLatticeElement &LV = I.first->second;
720
721 if (!I.second)
722 return LV; // Common case, already in the map.
723
724 if (auto *C = dyn_cast<Constant>(V)) {
725 Constant *Elt = C->getAggregateElement(i);
726
727 if (!Elt)
728 LV.markOverdefined(); // Unknown sort of constant.
729 else
730 LV.markConstant(Elt); // Constants are constant.
731 }
732
733 // All others are underdefined by default.
734 return LV;
735 }
736
737 template <typename FnTy> void forEachLatticeElement(Value *V, FnTy Fn) {
738 if (auto *STy = dyn_cast<StructType>(V->getType())) {
739 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
740 Fn([this, i](Value *Op) -> ValueLatticeElement & {
741 return getStructValueState(Op, i);
742 });
743 } else {
744 Fn([this](Value *Op) -> ValueLatticeElement & {
745 return getValueState(Op);
746 });
747 }
748 }
749
750 /// Traverse the use-def chain of \p Call, marking itself and its users as
751 /// "unknown" on the way.
752 void invalidate(CallBase *Call) {
754 ToInvalidate.push_back(Call);
755
756 while (!ToInvalidate.empty()) {
757 Instruction *Inst = ToInvalidate.pop_back_val();
758
759 if (!Invalidated.insert(Inst).second)
760 continue;
761
762 if (!BBExecutable.count(Inst->getParent()))
763 continue;
764
765 Value *V = nullptr;
766 // For return instructions we need to invalidate the tracked returns map.
767 // Anything else has its lattice in the value map.
768 if (auto *RetInst = dyn_cast<ReturnInst>(Inst)) {
769 Function *F = RetInst->getParent()->getParent();
770 bool Reset = false;
771 if (auto It = TrackedRetVals.find(F); It != TrackedRetVals.end()) {
772 It->second = ValueLatticeElement();
773 Reset = true;
774 } else if (MRVFunctionsTracked.count(F)) {
775 auto *STy = cast<StructType>(F->getReturnType());
776 for (unsigned I = 0, E = STy->getNumElements(); I != E; ++I)
777 TrackedMultipleRetVals[{F, I}] = ValueLatticeElement();
778 Reset = true;
779 }
780 if (Reset) {
781 LLVM_DEBUG(dbgs() << "Invalidated lattice for function "
782 << F->getName() << "\n");
783
784 for (User *U : F->users())
785 if (auto *CB = dyn_cast<CallBase>(U))
786 if (CB->getCalledFunction() == F)
787 ToInvalidate.push_back(CB);
788 }
789 } else if (auto *STy = dyn_cast<StructType>(Inst->getType())) {
790 for (unsigned I = 0, E = STy->getNumElements(); I != E; ++I) {
791 if (auto It = StructValueState.find({Inst, I});
792 It != StructValueState.end()) {
793 It->second = ValueLatticeElement();
794 V = Inst;
795 }
796 }
797 } else if (auto It = ValueState.find(Inst); It != ValueState.end()) {
798 It->second = ValueLatticeElement();
799 V = Inst;
800 }
801
802 if (V) {
803 LLVM_DEBUG(dbgs() << "Invalidated lattice for " << *V << "\n");
804
805 for (User *U : V->users())
806 if (auto *UI = dyn_cast<Instruction>(U))
807 ToInvalidate.push_back(UI);
808
809 auto It = AdditionalUsers.find(V);
810 if (It != AdditionalUsers.end())
811 for (User *U : It->second)
812 if (auto *UI = dyn_cast<Instruction>(U))
813 ToInvalidate.push_back(UI);
814 }
815 }
816 }
817
818 /// markEdgeExecutable - Mark a basic block as executable, adding it to the BB
819 /// work list if it is not already executable.
820 bool markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest);
821
822 // getFeasibleSuccessors - Return a vector of booleans to indicate which
823 // successors are reachable from a given terminator instruction.
824 void getFeasibleSuccessors(Instruction &TI, SmallVectorImpl<bool> &Succs);
825
826 // Add U as additional user of V.
827 void addAdditionalUser(Value *V, User *U) { AdditionalUsers[V].insert(U); }
828
829 void handlePredicate(Instruction *I, Value *CopyOf, const PredicateBase *PI);
830 void handleCallOverdefined(CallBase &CB);
831 void handleCallResult(CallBase &CB);
832 void handleCallArguments(CallBase &CB);
833 void handleExtractOfWithOverflow(ExtractValueInst &EVI,
834 const WithOverflowInst *WO, unsigned Idx);
835 bool isInstFullyOverDefined(Instruction &Inst);
836
837private:
838 friend class InstVisitor<SCCPInstVisitor>;
839
840 // visit implementations - Something changed in this instruction. Either an
841 // operand made a transition, or the instruction is newly executable. Change
842 // the value type of I to reflect these changes if appropriate.
843 void visitPHINode(PHINode &I);
844
845 // Terminators
846
847 void visitReturnInst(ReturnInst &I);
848 void visitTerminator(Instruction &TI);
849
850 void visitCastInst(CastInst &I);
851 void visitSelectInst(SelectInst &I);
852 void visitUnaryOperator(Instruction &I);
853 void visitFreezeInst(FreezeInst &I);
854 void visitBinaryOperator(Instruction &I);
855 void visitCmpInst(CmpInst &I);
856 void visitExtractValueInst(ExtractValueInst &EVI);
857 void visitInsertValueInst(InsertValueInst &IVI);
858
859 void visitCatchSwitchInst(CatchSwitchInst &CPI) {
860 markOverdefined(&CPI);
861 visitTerminator(CPI);
862 }
863
864 // Instructions that cannot be folded away.
865
866 void visitStoreInst(StoreInst &I);
867 void visitLoadInst(LoadInst &I);
868 void visitGetElementPtrInst(GetElementPtrInst &I);
869 void visitAllocaInst(AllocaInst &AI);
870
871 void visitInvokeInst(InvokeInst &II) {
872 visitCallBase(II);
873 visitTerminator(II);
874 }
875
876 void visitCallBrInst(CallBrInst &CBI) {
877 visitCallBase(CBI);
878 visitTerminator(CBI);
879 }
880
881 void visitCallBase(CallBase &CB);
882 void visitResumeInst(ResumeInst &I) { /*returns void*/
883 }
884 void visitUnreachableInst(UnreachableInst &I) { /*returns void*/
885 }
886 void visitFenceInst(FenceInst &I) { /*returns void*/
887 }
888
889 void visitInstruction(Instruction &I);
890
891public:
892 const DataLayout &getDataLayout() const { return DL; }
893
895 FnPredicateInfo.insert({&F, std::make_unique<PredicateInfo>(
896 F, DT, AC, PredicateInfoAllocator)});
897 }
898
900 auto It = FnPredicateInfo.find(&F);
901 if (It == FnPredicateInfo.end())
902 return;
903
904 for (BasicBlock &BB : F) {
905 for (Instruction &Inst : llvm::make_early_inc_range(BB)) {
906 if (auto *BC = dyn_cast<BitCastInst>(&Inst)) {
907 if (BC->getType() == BC->getOperand(0)->getType()) {
908 if (It->second->getPredicateInfoFor(&Inst)) {
909 Value *Op = BC->getOperand(0);
910 Inst.replaceAllUsesWith(Op);
911 Inst.eraseFromParent();
912 }
913 }
914 }
915 }
916 }
917 }
918
919 void visitCallInst(CallInst &I) { visitCallBase(I); }
920
922
924 auto It = FnPredicateInfo.find(I->getParent()->getParent());
925 if (It == FnPredicateInfo.end())
926 return nullptr;
927 return It->second->getPredicateInfoFor(I);
928 }
929
931 std::function<const TargetLibraryInfo &(Function &)> GetTLI,
932 LLVMContext &Ctx)
933 : DL(DL), GetTLI(GetTLI), Ctx(Ctx) {}
934
936 // We only track the contents of scalar globals.
937 if (GV->getValueType()->isSingleValueType()) {
938 ValueLatticeElement &IV = TrackedGlobals[GV];
939 IV.markConstant(GV->getInitializer());
940 }
941 }
942
944 // Add an entry, F -> undef.
945 if (auto *STy = dyn_cast<StructType>(F->getReturnType())) {
946 MRVFunctionsTracked.insert(F);
947 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
948 TrackedMultipleRetVals.try_emplace(std::make_pair(F, i));
949 } else if (!F->getReturnType()->isVoidTy())
950 TrackedRetVals.try_emplace(F);
951 }
952
954 MustPreserveReturnsInFunctions.insert(F);
955 }
956
958 return MustPreserveReturnsInFunctions.count(F);
959 }
960
962 TrackingIncomingArguments.insert(F);
963 }
964
966 return TrackingIncomingArguments.count(F);
967 }
968
970 return TrackingIncomingArguments;
971 }
972
973 void solve();
974
976
978
980 return BBExecutable.count(BB);
981 }
982
983 bool isEdgeFeasible(BasicBlock *From, BasicBlock *To) const;
984
985 std::vector<ValueLatticeElement> getStructLatticeValueFor(Value *V) const {
986 std::vector<ValueLatticeElement> StructValues;
987 auto *STy = dyn_cast<StructType>(V->getType());
988 assert(STy && "getStructLatticeValueFor() can be called only on structs");
989 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
990 auto I = StructValueState.find(std::make_pair(V, i));
991 assert(I != StructValueState.end() && "Value not in valuemap!");
992 StructValues.push_back(I->second);
993 }
994 return StructValues;
995 }
996
997 void removeLatticeValueFor(Value *V) { ValueState.erase(V); }
998
999 /// Invalidate the Lattice Value of \p Call and its users after specializing
1000 /// the call. Then recompute it.
1002 // Calls to void returning functions do not need invalidation.
1003 Function *F = Call->getCalledFunction();
1004 (void)F;
1005 assert(!F->getReturnType()->isVoidTy() &&
1006 (TrackedRetVals.count(F) || MRVFunctionsTracked.count(F)) &&
1007 "All non void specializations should be tracked");
1008 invalidate(Call);
1009 handleCallResult(*Call);
1010 }
1011
1013 assert(!V->getType()->isStructTy() &&
1014 "Should use getStructLatticeValueFor");
1015 auto I = ValueState.find(V);
1016 assert(I != ValueState.end() &&
1017 "V not found in ValueState nor Paramstate map!");
1018 return I->second;
1019 }
1020
1022 return TrackedRetVals;
1023 }
1024
1027 return TrackedGlobals;
1028 }
1029
1031 return MRVFunctionsTracked;
1032 }
1033
1035 if (auto *STy = dyn_cast<StructType>(V->getType()))
1036 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
1037 markOverdefined(getStructValueState(V, i), V);
1038 else
1039 markOverdefined(ValueState[V], V);
1040 }
1041
1043 if (A->getType()->isIntOrIntVectorTy()) {
1044 if (std::optional<ConstantRange> Range = A->getRange())
1046 }
1047 if (A->hasNonNullAttr())
1049 // Assume nothing about the incoming arguments without attributes.
1051 }
1052
1054 if (A->getType()->isStructTy())
1055 return (void)markOverdefined(A);
1056 mergeInValue(ValueState[A], A, getArgAttributeVL(A));
1057 }
1058
1060
1061 Constant *getConstant(const ValueLatticeElement &LV, Type *Ty) const;
1062
1063 Constant *getConstantOrNull(Value *V) const;
1064
1066 const SmallVectorImpl<ArgInfo> &Args);
1067
1069 for (auto &BB : *F)
1070 BBExecutable.erase(&BB);
1071 }
1072
1074 bool ResolvedUndefs = true;
1075 while (ResolvedUndefs) {
1076 solve();
1077 ResolvedUndefs = false;
1078 for (Function &F : M)
1079 ResolvedUndefs |= resolvedUndefsIn(F);
1080 }
1081 }
1082
1084 bool ResolvedUndefs = true;
1085 while (ResolvedUndefs) {
1086 solve();
1087 ResolvedUndefs = false;
1088 for (Function *F : WorkList)
1089 ResolvedUndefs |= resolvedUndefsIn(*F);
1090 }
1091 }
1092
1094 bool ResolvedUndefs = true;
1095 while (ResolvedUndefs) {
1096 solve();
1097 ResolvedUndefs = false;
1098 for (Value *V : Invalidated)
1099 if (auto *I = dyn_cast<Instruction>(V))
1100 ResolvedUndefs |= resolvedUndef(*I);
1101 }
1102 Invalidated.clear();
1103 }
1104};
1105
1106} // namespace llvm
1107
1109 if (!BBExecutable.insert(BB).second)
1110 return false;
1111 LLVM_DEBUG(dbgs() << "Marking Block Executable: " << BB->getName() << '\n');
1112 BBWorkList.push_back(BB); // Add the block to the work list!
1113 return true;
1114}
1115
1116void SCCPInstVisitor::pushToWorkList(Instruction *I) {
1117 // If we're currently visiting a block, do not push any instructions in the
1118 // same blocks that are after the current one, as they will be visited
1119 // anyway. We do have to push updates to earlier instructions (e.g. phi
1120 // nodes or loads of tracked globals).
1121 if (CurI && I->getParent() == CurI->getParent() && CurI->comesBefore(I))
1122 return;
1123 // Only push instructions in already visited blocks. Otherwise we'll handle
1124 // it when we visit the block for the first time.
1125 if (BBVisited.contains(I->getParent()))
1126 InstWorkList.insert(I);
1127}
1128
1129void SCCPInstVisitor::pushUsersToWorkList(Value *V) {
1130 for (User *U : V->users())
1131 if (auto *UI = dyn_cast<Instruction>(U))
1132 pushToWorkList(UI);
1133
1134 auto Iter = AdditionalUsers.find(V);
1135 if (Iter != AdditionalUsers.end()) {
1136 // Copy additional users before notifying them of changes, because new
1137 // users may be added, potentially invalidating the iterator.
1139 for (User *U : Iter->second)
1140 if (auto *UI = dyn_cast<Instruction>(U))
1141 ToNotify.push_back(UI);
1142 for (Instruction *UI : ToNotify)
1143 pushToWorkList(UI);
1144 }
1145}
1146
1147void SCCPInstVisitor::pushUsersToWorkListMsg(ValueLatticeElement &IV,
1148 Value *V) {
1149 LLVM_DEBUG(dbgs() << "updated " << IV << ": " << *V << '\n');
1150 pushUsersToWorkList(V);
1151}
1152
1153bool SCCPInstVisitor::markConstant(ValueLatticeElement &IV, Value *V,
1154 Constant *C, bool MayIncludeUndef) {
1155 if (!IV.markConstant(C, MayIncludeUndef))
1156 return false;
1157 LLVM_DEBUG(dbgs() << "markConstant: " << *C << ": " << *V << '\n');
1158 pushUsersToWorkList(V);
1159 return true;
1160}
1161
1162bool SCCPInstVisitor::markNotConstant(ValueLatticeElement &IV, Value *V,
1163 Constant *C) {
1164 if (!IV.markNotConstant(C))
1165 return false;
1166 LLVM_DEBUG(dbgs() << "markNotConstant: " << *C << ": " << *V << '\n');
1167 pushUsersToWorkList(V);
1168 return true;
1169}
1170
1171bool SCCPInstVisitor::markConstantRange(ValueLatticeElement &IV, Value *V,
1172 const ConstantRange &CR) {
1173 if (!IV.markConstantRange(CR))
1174 return false;
1175 LLVM_DEBUG(dbgs() << "markConstantRange: " << CR << ": " << *V << '\n');
1176 pushUsersToWorkList(V);
1177 return true;
1178}
1179
1180bool SCCPInstVisitor::markOverdefined(ValueLatticeElement &IV, Value *V) {
1181 if (!IV.markOverdefined())
1182 return false;
1183
1184 LLVM_DEBUG(dbgs() << "markOverdefined: ";
1185 if (auto *F = dyn_cast<Function>(V)) dbgs()
1186 << "Function '" << F->getName() << "'\n";
1187 else dbgs() << *V << '\n');
1188 // Only instructions go on the work list
1189 pushUsersToWorkList(V);
1190 return true;
1191}
1192
1194 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
1195 const auto &It = TrackedMultipleRetVals.find(std::make_pair(F, i));
1196 assert(It != TrackedMultipleRetVals.end());
1197 if (!SCCPSolver::isReplaceableConstant(It->second))
1198 return false;
1199 }
1200 return true;
1201}
1202
1204 Type *Ty) const {
1205 if (LV.isConstant()) {
1206 Constant *C = LV.getConstant();
1207 assert(C->getType() == Ty && "Type mismatch");
1208 return C;
1209 }
1210
1211 if (LV.isConstantRange()) {
1212 const auto &CR = LV.getConstantRange();
1213 if (CR.getSingleElement())
1214 return ConstantInt::get(Ty, *CR.getSingleElement());
1215 }
1216 return nullptr;
1217}
1218
1220 Constant *Const = nullptr;
1221 if (V->getType()->isStructTy()) {
1222 std::vector<ValueLatticeElement> LVs = getStructLatticeValueFor(V);
1224 return nullptr;
1225 std::vector<Constant *> ConstVals;
1226 auto *ST = cast<StructType>(V->getType());
1227 for (unsigned I = 0, E = ST->getNumElements(); I != E; ++I) {
1228 const ValueLatticeElement &LV = LVs[I];
1229 ConstVals.push_back(SCCPSolver::isConstant(LV)
1230 ? getConstant(LV, ST->getElementType(I))
1231 : UndefValue::get(ST->getElementType(I)));
1232 }
1233 Const = ConstantStruct::get(ST, ConstVals);
1234 } else {
1237 return nullptr;
1238 Const = SCCPSolver::isConstant(LV) ? getConstant(LV, V->getType())
1239 : UndefValue::get(V->getType());
1240 }
1241 assert(Const && "Constant is nullptr here!");
1242 return Const;
1243}
1244
1246 const SmallVectorImpl<ArgInfo> &Args) {
1247 assert(!Args.empty() && "Specialization without arguments");
1248 assert(F->arg_size() == Args[0].Formal->getParent()->arg_size() &&
1249 "Functions should have the same number of arguments");
1250
1251 auto Iter = Args.begin();
1252 Function::arg_iterator NewArg = F->arg_begin();
1253 Function::arg_iterator OldArg = Args[0].Formal->getParent()->arg_begin();
1254 for (auto End = F->arg_end(); NewArg != End; ++NewArg, ++OldArg) {
1255
1256 LLVM_DEBUG(dbgs() << "SCCP: Marking argument "
1257 << NewArg->getNameOrAsOperand() << "\n");
1258
1259 // Mark the argument constants in the new function
1260 // or copy the lattice state over from the old function.
1261 if (Iter != Args.end() && Iter->Formal == &*OldArg) {
1262 if (auto *STy = dyn_cast<StructType>(NewArg->getType())) {
1263 for (unsigned I = 0, E = STy->getNumElements(); I != E; ++I) {
1264 ValueLatticeElement &NewValue = StructValueState[{&*NewArg, I}];
1265 NewValue.markConstant(Iter->Actual->getAggregateElement(I));
1266 }
1267 } else {
1268 ValueState[&*NewArg].markConstant(Iter->Actual);
1269 }
1270 ++Iter;
1271 } else {
1272 if (auto *STy = dyn_cast<StructType>(NewArg->getType())) {
1273 for (unsigned I = 0, E = STy->getNumElements(); I != E; ++I) {
1274 ValueLatticeElement &NewValue = StructValueState[{&*NewArg, I}];
1275 NewValue = StructValueState[{&*OldArg, I}];
1276 }
1277 } else {
1278 ValueLatticeElement &NewValue = ValueState[&*NewArg];
1279 NewValue = ValueState[&*OldArg];
1280 }
1281 }
1282 }
1283}
1284
1285void SCCPInstVisitor::visitInstruction(Instruction &I) {
1286 // All the instructions we don't do any special handling for just
1287 // go to overdefined.
1288 LLVM_DEBUG(dbgs() << "SCCP: Don't know how to handle: " << I << '\n');
1289 markOverdefined(&I);
1290}
1291
1292bool SCCPInstVisitor::mergeInValue(ValueLatticeElement &IV, Value *V,
1293 const ValueLatticeElement &MergeWithV,
1295 if (IV.mergeIn(MergeWithV, Opts)) {
1296 pushUsersToWorkList(V);
1297 LLVM_DEBUG(dbgs() << "Merged " << MergeWithV << " into " << *V << " : "
1298 << IV << "\n");
1299 return true;
1300 }
1301 return false;
1302}
1303
1304bool SCCPInstVisitor::markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest) {
1305 if (!KnownFeasibleEdges.insert(Edge(Source, Dest)).second)
1306 return false; // This edge is already known to be executable!
1307
1308 if (!markBlockExecutable(Dest)) {
1309 // If the destination is already executable, we just made an *edge*
1310 // feasible that wasn't before. Revisit the PHI nodes in the block
1311 // because they have potentially new operands.
1312 LLVM_DEBUG(dbgs() << "Marking Edge Executable: " << Source->getName()
1313 << " -> " << Dest->getName() << '\n');
1314
1315 for (PHINode &PN : Dest->phis())
1316 pushToWorkList(&PN);
1317 }
1318 return true;
1319}
1320
1321// getFeasibleSuccessors - Return a vector of booleans to indicate which
1322// successors are reachable from a given terminator instruction.
1323void SCCPInstVisitor::getFeasibleSuccessors(Instruction &TI,
1324 SmallVectorImpl<bool> &Succs) {
1325 Succs.resize(TI.getNumSuccessors());
1326 if (isa<UncondBrInst>(TI)) {
1327 Succs[0] = true;
1328 return;
1329 }
1330
1331 if (auto *BI = dyn_cast<CondBrInst>(&TI)) {
1332 const ValueLatticeElement &BCValue = getValueState(BI->getCondition());
1333 ConstantInt *CI = getConstantInt(BCValue, BI->getCondition()->getType());
1334 if (!CI) {
1335 // Overdefined condition variables, and branches on unfoldable constant
1336 // conditions, mean the branch could go either way.
1337 if (!BCValue.isUnknownOrUndef())
1338 Succs[0] = Succs[1] = true;
1339 return;
1340 }
1341
1342 // Constant condition variables mean the branch can only go a single way.
1343 Succs[CI->isZero()] = true;
1344 return;
1345 }
1346
1347 // We cannot analyze special terminators, so consider all successors
1348 // executable.
1349 if (TI.isSpecialTerminator()) {
1350 Succs.assign(TI.getNumSuccessors(), true);
1351 return;
1352 }
1353
1354 if (auto *SI = dyn_cast<SwitchInst>(&TI)) {
1355 if (!SI->getNumCases()) {
1356 Succs[0] = true;
1357 return;
1358 }
1359 const ValueLatticeElement &SCValue = getValueState(SI->getCondition());
1360 if (ConstantInt *CI =
1361 getConstantInt(SCValue, SI->getCondition()->getType())) {
1362 Succs[SI->findCaseValue(CI)->getSuccessorIndex()] = true;
1363 return;
1364 }
1365
1366 // TODO: Switch on undef is UB. Stop passing false once the rest of LLVM
1367 // is ready.
1368 if (SCValue.isConstantRange(/*UndefAllowed=*/false)) {
1369 const ConstantRange &Range = SCValue.getConstantRange();
1370 unsigned ReachableCaseCount = 0;
1371 for (const auto &Case : SI->cases()) {
1372 const APInt &CaseValue = Case.getCaseValue()->getValue();
1373 if (Range.contains(CaseValue)) {
1374 Succs[Case.getSuccessorIndex()] = true;
1375 ++ReachableCaseCount;
1376 }
1377 }
1378
1379 Succs[SI->case_default()->getSuccessorIndex()] =
1380 Range.isSizeLargerThan(ReachableCaseCount);
1381 return;
1382 }
1383
1384 // Overdefined or unknown condition? All destinations are executable!
1385 if (!SCValue.isUnknownOrUndef())
1386 Succs.assign(TI.getNumSuccessors(), true);
1387 return;
1388 }
1389
1390 // In case of indirect branch and its address is a blockaddress, we mark
1391 // the target as executable.
1392 if (auto *IBR = dyn_cast<IndirectBrInst>(&TI)) {
1393 // Casts are folded by visitCastInst.
1394 const ValueLatticeElement &IBRValue = getValueState(IBR->getAddress());
1396 getConstant(IBRValue, IBR->getAddress()->getType()));
1397 if (!Addr) { // Overdefined or unknown condition?
1398 // All destinations are executable!
1399 if (!IBRValue.isUnknownOrUndef())
1400 Succs.assign(TI.getNumSuccessors(), true);
1401 return;
1402 }
1403
1404 BasicBlock *T = Addr->getBasicBlock();
1405 assert(Addr->getFunction() == T->getParent() &&
1406 "Block address of a different function ?");
1407 for (unsigned i = 0; i < IBR->getNumSuccessors(); ++i) {
1408 // This is the target.
1409 if (IBR->getDestination(i) == T) {
1410 Succs[i] = true;
1411 return;
1412 }
1413 }
1414
1415 // If we didn't find our destination in the IBR successor list, then we
1416 // have undefined behavior. Its ok to assume no successor is executable.
1417 return;
1418 }
1419
1420 LLVM_DEBUG(dbgs() << "Unknown terminator instruction: " << TI << '\n');
1421 llvm_unreachable("SCCP: Don't know how to handle this terminator!");
1422}
1423
1424// isEdgeFeasible - Return true if the control flow edge from the 'From' basic
1425// block to the 'To' basic block is currently feasible.
1427 // Check if we've called markEdgeExecutable on the edge yet. (We could
1428 // be more aggressive and try to consider edges which haven't been marked
1429 // yet, but there isn't any need.)
1430 return KnownFeasibleEdges.count(Edge(From, To));
1431}
1432
1433// visit Implementations - Something changed in this instruction, either an
1434// operand made a transition, or the instruction is newly executable. Change
1435// the value type of I to reflect these changes if appropriate. This method
1436// makes sure to do the following actions:
1437//
1438// 1. If a phi node merges two constants in, and has conflicting value coming
1439// from different branches, or if the PHI node merges in an overdefined
1440// value, then the PHI node becomes overdefined.
1441// 2. If a phi node merges only constants in, and they all agree on value, the
1442// PHI node becomes a constant value equal to that.
1443// 3. If V <- x (op) y && isConstant(x) && isConstant(y) V = Constant
1444// 4. If V <- x (op) y && (isOverdefined(x) || isOverdefined(y)) V = Overdefined
1445// 5. If V <- MEM or V <- CALL or V <- (unknown) then V = Overdefined
1446// 6. If a conditional branch has a value that is constant, make the selected
1447// destination executable
1448// 7. If a conditional branch has a value that is overdefined, make all
1449// successors executable.
1450void SCCPInstVisitor::visitPHINode(PHINode &PN) {
1451 // Super-extra-high-degree PHI nodes are unlikely to ever be marked constant,
1452 // and slow us down a lot. Just mark them overdefined.
1453 if (PN.getNumIncomingValues() > 64)
1454 return (void)markOverdefined(&PN);
1455
1456 if (isInstFullyOverDefined(PN))
1457 return;
1458 SmallVector<unsigned> FeasibleIncomingIndices;
1459 for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
1460 if (!isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent()))
1461 continue;
1462 FeasibleIncomingIndices.push_back(i);
1463 }
1464
1465 // Look at all of the executable operands of the PHI node. If any of them
1466 // are overdefined, the PHI becomes overdefined as well. If they are all
1467 // constant, and they agree with each other, the PHI becomes the identical
1468 // constant. If they are constant and don't agree, the PHI is a constant
1469 // range. If there are no executable operands, the PHI remains unknown.
1470 forEachLatticeElement(&PN, [&](auto GetValueState) {
1471 ValueLatticeElement PhiState = GetValueState(&PN);
1472 if (PhiState.isOverdefined())
1473 return;
1474 for (unsigned i : FeasibleIncomingIndices) {
1475 PhiState.mergeIn(GetValueState(PN.getIncomingValue(i)));
1476 if (PhiState.isOverdefined())
1477 break;
1478 }
1479 // We allow up to 1 range extension per active incoming value and one
1480 // additional extension. Note that we manually adjust the number of range
1481 // extensions to match the number of active incoming values. This helps to
1482 // limit multiple extensions caused by the same incoming value, if other
1483 // incoming values are equal.
1484 ValueLatticeElement &PhiStateRef = GetValueState(&PN);
1485 mergeInValue(PhiStateRef, &PN, PhiState,
1486 ValueLatticeElement::MergeOptions().setMaxWidenSteps(
1487 FeasibleIncomingIndices.size() + 1));
1488 PhiStateRef.setNumRangeExtensions(
1489 std::max((unsigned)FeasibleIncomingIndices.size(),
1490 PhiStateRef.getNumRangeExtensions()));
1491 });
1492}
1493
1494void SCCPInstVisitor::visitReturnInst(ReturnInst &I) {
1495 if (I.getNumOperands() == 0)
1496 return; // ret void
1497
1498 Function *F = I.getParent()->getParent();
1499 Value *ResultOp = I.getOperand(0);
1500
1501 // If we are tracking the return value of this function, merge it in.
1502 if (!TrackedRetVals.empty() && !ResultOp->getType()->isStructTy()) {
1503 auto TFRVI = TrackedRetVals.find(F);
1504 if (TFRVI != TrackedRetVals.end()) {
1505 mergeInValue(TFRVI->second, F, getValueState(ResultOp));
1506 return;
1507 }
1508 }
1509
1510 // Handle functions that return multiple values.
1511 if (!TrackedMultipleRetVals.empty()) {
1512 if (auto *STy = dyn_cast<StructType>(ResultOp->getType()))
1513 if (MRVFunctionsTracked.count(F))
1514 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
1515 mergeInValue(TrackedMultipleRetVals[std::make_pair(F, i)], F,
1516 getStructValueState(ResultOp, i));
1517 }
1518}
1519
1520void SCCPInstVisitor::visitTerminator(Instruction &TI) {
1521 SmallVector<bool, 16> SuccFeasible;
1522 getFeasibleSuccessors(TI, SuccFeasible);
1523
1524 BasicBlock *BB = TI.getParent();
1525
1526 // Mark all feasible successors executable.
1527 for (unsigned i = 0, e = SuccFeasible.size(); i != e; ++i)
1528 if (SuccFeasible[i])
1529 markEdgeExecutable(BB, TI.getSuccessor(i));
1530}
1531
1532void SCCPInstVisitor::visitCastInst(CastInst &I) {
1533 // ResolvedUndefsIn might mark I as overdefined. Bail out, even if we would
1534 // discover a concrete value later.
1535 if (ValueState[&I].isOverdefined())
1536 return;
1537
1538 if (auto *BC = dyn_cast<BitCastInst>(&I)) {
1539 if (BC->getType() == BC->getOperand(0)->getType()) {
1540 if (const PredicateBase *PI = getPredicateInfoFor(&I)) {
1541 handlePredicate(&I, I.getOperand(0), PI);
1542 return;
1543 }
1544 }
1545 }
1546
1547 const ValueLatticeElement &OpSt = getValueState(I.getOperand(0));
1548 if (OpSt.isUnknownOrUndef())
1549 return;
1550
1551 if (Constant *OpC = getConstant(OpSt, I.getOperand(0)->getType())) {
1552 // Fold the constant as we build.
1553 if (Constant *C =
1554 ConstantFoldCastOperand(I.getOpcode(), OpC, I.getType(), DL)) {
1555 auto &LV = ValueState[&I];
1556 mergeInValue(LV, &I, ValueLatticeElement::get(C));
1557 return;
1558 }
1559 }
1560
1561 // Ignore bitcasts, as they may change the number of vector elements.
1562 if (I.getDestTy()->isIntOrIntVectorTy() &&
1563 I.getSrcTy()->isIntOrIntVectorTy() &&
1564 I.getOpcode() != Instruction::BitCast) {
1565 ConstantRange OpRange =
1566 OpSt.asConstantRange(I.getSrcTy(), /*UndefAllowed=*/false);
1567 auto &LV = getValueState(&I);
1568
1569 Type *DestTy = I.getDestTy();
1570 ConstantRange Res = ConstantRange::getEmpty(DestTy->getScalarSizeInBits());
1571 if (auto *Trunc = dyn_cast<TruncInst>(&I))
1572 Res = OpRange.truncate(DestTy->getScalarSizeInBits(),
1573 Trunc->getNoWrapKind());
1574 else
1575 Res = OpRange.castOp(I.getOpcode(), DestTy->getScalarSizeInBits());
1576 mergeInValue(LV, &I, ValueLatticeElement::getRange(Res));
1577 } else
1578 markOverdefined(&I);
1579}
1580
1581void SCCPInstVisitor::handleExtractOfWithOverflow(ExtractValueInst &EVI,
1582 const WithOverflowInst *WO,
1583 unsigned Idx) {
1584 Value *LHS = WO->getLHS(), *RHS = WO->getRHS();
1585 Type *Ty = LHS->getType();
1586
1587 addAdditionalUser(LHS, &EVI);
1588 addAdditionalUser(RHS, &EVI);
1589
1590 const ValueLatticeElement &L = getValueState(LHS);
1591 if (L.isUnknownOrUndef())
1592 return; // Wait to resolve.
1593 ConstantRange LR = L.asConstantRange(Ty, /*UndefAllowed=*/false);
1594
1595 const ValueLatticeElement &R = getValueState(RHS);
1596 if (R.isUnknownOrUndef())
1597 return; // Wait to resolve.
1598
1599 ConstantRange RR = R.asConstantRange(Ty, /*UndefAllowed=*/false);
1600 if (Idx == 0) {
1601 ConstantRange Res = LR.binaryOp(WO->getBinaryOp(), RR);
1602 mergeInValue(ValueState[&EVI], &EVI, ValueLatticeElement::getRange(Res));
1603 } else {
1604 assert(Idx == 1 && "Index can only be 0 or 1");
1605 ConstantRange NWRegion = ConstantRange::makeGuaranteedNoWrapRegion(
1606 WO->getBinaryOp(), RR, WO->getNoWrapKind());
1607 if (NWRegion.contains(LR))
1608 return (void)markConstant(&EVI, ConstantInt::getFalse(EVI.getType()));
1609 markOverdefined(&EVI);
1610 }
1611}
1612
1613void SCCPInstVisitor::visitExtractValueInst(ExtractValueInst &EVI) {
1614 // If this returns a struct, mark all elements over defined, we don't track
1615 // structs in structs.
1616 if (EVI.getType()->isStructTy())
1617 return (void)markOverdefined(&EVI);
1618
1619 // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would
1620 // discover a concrete value later.
1621 if (ValueState[&EVI].isOverdefined())
1622 return (void)markOverdefined(&EVI);
1623
1624 // If this is extracting from more than one level of struct, we don't know.
1625 if (EVI.getNumIndices() != 1)
1626 return (void)markOverdefined(&EVI);
1627
1628 Value *AggVal = EVI.getAggregateOperand();
1629 if (AggVal->getType()->isStructTy()) {
1630 unsigned i = *EVI.idx_begin();
1631 if (auto *WO = dyn_cast<WithOverflowInst>(AggVal))
1632 return handleExtractOfWithOverflow(EVI, WO, i);
1633 ValueLatticeElement EltVal = getStructValueState(AggVal, i);
1634 mergeInValue(ValueState[&EVI], &EVI, EltVal);
1635 } else {
1636 // Otherwise, must be extracting from an array.
1637 return (void)markOverdefined(&EVI);
1638 }
1639}
1640
1641void SCCPInstVisitor::visitInsertValueInst(InsertValueInst &IVI) {
1642 auto *STy = dyn_cast<StructType>(IVI.getType());
1643 if (!STy)
1644 return (void)markOverdefined(&IVI);
1645
1646 // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would
1647 // discover a concrete value later.
1648 if (ValueState[&IVI].isOverdefined())
1649 return (void)markOverdefined(&IVI);
1650
1651 // If this has more than one index, we can't handle it, drive all results to
1652 // undef.
1653 if (IVI.getNumIndices() != 1)
1654 return (void)markOverdefined(&IVI);
1655
1656 Value *Aggr = IVI.getAggregateOperand();
1657 unsigned Idx = *IVI.idx_begin();
1658
1659 // Compute the result based on what we're inserting.
1660 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
1661 // This passes through all values that aren't the inserted element.
1662 if (i != Idx) {
1663 ValueLatticeElement EltVal = getStructValueState(Aggr, i);
1664 mergeInValue(getStructValueState(&IVI, i), &IVI, EltVal);
1665 continue;
1666 }
1667
1668 Value *Val = IVI.getInsertedValueOperand();
1669 if (Val->getType()->isStructTy())
1670 // We don't track structs in structs.
1671 markOverdefined(getStructValueState(&IVI, i), &IVI);
1672 else {
1673 ValueLatticeElement InVal = getValueState(Val);
1674 mergeInValue(getStructValueState(&IVI, i), &IVI, InVal);
1675 }
1676 }
1677}
1678
1679void SCCPInstVisitor::visitSelectInst(SelectInst &I) {
1680 // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would
1681 // discover a concrete value later.
1682 if (isInstFullyOverDefined(I))
1683 return (void)markOverdefined(&I);
1684
1685 const ValueLatticeElement &CondValue = getValueState(I.getCondition());
1686 if (CondValue.isUnknownOrUndef())
1687 return;
1688
1689 if (ConstantInt *CondCB =
1690 getConstantInt(CondValue, I.getCondition()->getType())) {
1691 Value *OpVal = CondCB->isZero() ? I.getFalseValue() : I.getTrueValue();
1692 forEachLatticeElement(&I, [&](auto GetValueState) {
1693 ValueLatticeElement OpValState = GetValueState(OpVal);
1694 mergeInValue(GetValueState(&I), &I, OpValState);
1695 });
1696 return;
1697 }
1698
1699 // Otherwise, the condition is overdefined or a constant we can't evaluate.
1700 // See if we can produce something better than overdefined based on the T/F
1701 // value.
1702 forEachLatticeElement(&I, [&](auto GetValueState) {
1703 ValueLatticeElement TVal = GetValueState(I.getTrueValue());
1704 ValueLatticeElement FVal = GetValueState(I.getFalseValue());
1705
1706 ValueLatticeElement &State = GetValueState(&I);
1707 bool Changed = State.mergeIn(TVal);
1708 Changed |= State.mergeIn(FVal);
1709 if (Changed)
1710 pushUsersToWorkListMsg(State, &I);
1711 });
1712}
1713
1714// Handle Unary Operators.
1715void SCCPInstVisitor::visitUnaryOperator(Instruction &I) {
1716 ValueLatticeElement V0State = getValueState(I.getOperand(0));
1717
1718 ValueLatticeElement &IV = ValueState[&I];
1719 // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would
1720 // discover a concrete value later.
1721 if (IV.isOverdefined())
1722 return (void)markOverdefined(&I);
1723
1724 // If something is unknown/undef, wait for it to resolve.
1725 if (V0State.isUnknownOrUndef())
1726 return;
1727
1728 if (SCCPSolver::isConstant(V0State))
1729 if (Constant *C = ConstantFoldUnaryOpOperand(
1730 I.getOpcode(), getConstant(V0State, I.getType()), DL))
1731 return (void)markConstant(IV, &I, C);
1732
1733 markOverdefined(&I);
1734}
1735
1736void SCCPInstVisitor::visitFreezeInst(FreezeInst &I) {
1737 // If this freeze returns a struct, just mark the result overdefined.
1738 // TODO: We could do a lot better than this.
1739 if (I.getType()->isStructTy())
1740 return (void)markOverdefined(&I);
1741
1742 ValueLatticeElement V0State = getValueState(I.getOperand(0));
1743 ValueLatticeElement &IV = ValueState[&I];
1744 // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would
1745 // discover a concrete value later.
1746 if (IV.isOverdefined())
1747 return (void)markOverdefined(&I);
1748
1749 // If something is unknown/undef, wait for it to resolve.
1750 if (V0State.isUnknownOrUndef())
1751 return;
1752
1753 if (SCCPSolver::isConstant(V0State) &&
1754 isGuaranteedNotToBeUndefOrPoison(getConstant(V0State, I.getType())))
1755 return (void)markConstant(IV, &I, getConstant(V0State, I.getType()));
1756
1757 markOverdefined(&I);
1758}
1759
1760// Handle Binary Operators.
1761void SCCPInstVisitor::visitBinaryOperator(Instruction &I) {
1762 ValueLatticeElement V1State = getValueState(I.getOperand(0));
1763 ValueLatticeElement V2State = getValueState(I.getOperand(1));
1764
1765 ValueLatticeElement &IV = ValueState[&I];
1766 if (IV.isOverdefined())
1767 return;
1768
1769 // If something is undef, wait for it to resolve.
1770 if (V1State.isUnknownOrUndef() || V2State.isUnknownOrUndef())
1771 return;
1772
1773 if (V1State.isOverdefined() && V2State.isOverdefined())
1774 return (void)markOverdefined(&I);
1775
1776 // If either of the operands is a constant, try to fold it to a constant.
1777 // TODO: Use information from notconstant better.
1778 if ((V1State.isConstant() || V2State.isConstant())) {
1779 Value *V1 = SCCPSolver::isConstant(V1State)
1780 ? getConstant(V1State, I.getOperand(0)->getType())
1781 : I.getOperand(0);
1782 Value *V2 = SCCPSolver::isConstant(V2State)
1783 ? getConstant(V2State, I.getOperand(1)->getType())
1784 : I.getOperand(1);
1785 Value *R;
1786 if (auto *FPOp = dyn_cast<FPMathOperator>(&I))
1787 R = simplifyBinOp(I.getOpcode(), V1, V2, FPOp->getFastMathFlags(),
1788 SimplifyQuery(DL, &I));
1789 else
1790 R = simplifyBinOp(I.getOpcode(), V1, V2, SimplifyQuery(DL, &I));
1791 auto *C = dyn_cast_or_null<Constant>(R);
1792 if (C) {
1793 // Conservatively assume that the result may be based on operands that may
1794 // be undef. Note that we use mergeInValue to combine the constant with
1795 // the existing lattice value for I, as different constants might be found
1796 // after one of the operands go to overdefined, e.g. due to one operand
1797 // being a special floating value.
1798 ValueLatticeElement NewV;
1799 NewV.markConstant(C, /*MayIncludeUndef=*/true);
1800 return (void)mergeInValue(ValueState[&I], &I, NewV);
1801 }
1802 }
1803
1804 // Only use ranges for binary operators on integers.
1805 if (!I.getType()->isIntOrIntVectorTy())
1806 return markOverdefined(&I);
1807
1808 // Try to simplify to a constant range.
1809 ConstantRange A =
1810 V1State.asConstantRange(I.getType(), /*UndefAllowed=*/false);
1811 ConstantRange B =
1812 V2State.asConstantRange(I.getType(), /*UndefAllowed=*/false);
1813
1814 auto *BO = cast<BinaryOperator>(&I);
1815 ConstantRange R = A.binaryOp(*BO, B);
1816 mergeInValue(ValueState[&I], &I, ValueLatticeElement::getRange(R));
1817}
1818
1819// Handle ICmpInst instruction.
1820void SCCPInstVisitor::visitCmpInst(CmpInst &I) {
1821 // Do not cache this lookup, getValueState calls later in the function might
1822 // invalidate the reference.
1823 if (ValueState[&I].isOverdefined())
1824 return (void)markOverdefined(&I);
1825
1826 Value *Op1 = I.getOperand(0);
1827 Value *Op2 = I.getOperand(1);
1828
1829 // For parameters, use ParamState which includes constant range info if
1830 // available.
1831 auto V1State = getValueState(Op1);
1832 auto V2State = getValueState(Op2);
1833
1834 Constant *C = V1State.getCompare(I.getPredicate(), I.getType(), V2State, DL);
1835 if (C) {
1836 ValueLatticeElement CV;
1837 CV.markConstant(C);
1838 mergeInValue(ValueState[&I], &I, CV);
1839 return;
1840 }
1841
1842 // If operands are still unknown, wait for it to resolve.
1843 if ((V1State.isUnknownOrUndef() || V2State.isUnknownOrUndef()) &&
1844 !SCCPSolver::isConstant(ValueState[&I]))
1845 return;
1846
1847 markOverdefined(&I);
1848}
1849
1850// Handle getelementptr instructions. If all operands are constants then we
1851// can turn this into a getelementptr ConstantExpr.
1852void SCCPInstVisitor::visitGetElementPtrInst(GetElementPtrInst &I) {
1853 if (ValueState[&I].isOverdefined())
1854 return (void)markOverdefined(&I);
1855
1856 const ValueLatticeElement &PtrState = getValueState(I.getPointerOperand());
1857 if (PtrState.isUnknownOrUndef())
1858 return;
1859
1860 // gep inbounds/nuw of non-null is non-null.
1861 if (PtrState.isNotConstant() && PtrState.getNotConstant()->isNullValue()) {
1862 if (I.hasNoUnsignedWrap() ||
1863 (I.isInBounds() &&
1864 !NullPointerIsDefined(I.getFunction(), I.getAddressSpace())))
1865 return (void)markNotNull(ValueState[&I], &I);
1866 return (void)markOverdefined(&I);
1867 }
1868
1870 Operands.reserve(I.getNumOperands());
1871 bool PtrMayHaveDifferentProvenance = PtrState.mayHaveDifferentProvenance();
1872
1873 for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) {
1874 const ValueLatticeElement &State = getValueState(I.getOperand(i));
1875 if (State.isUnknownOrUndef())
1876 return; // Operands are not resolved yet.
1877
1878 if (Constant *C = getConstant(State, I.getOperand(i)->getType())) {
1879 Operands.push_back(C);
1880 continue;
1881 }
1882
1883 return (void)markOverdefined(&I);
1884 }
1885
1886 if (Constant *C = ConstantFoldInstOperands(&I, Operands, DL)) {
1887 mergeInValue(ValueState[&I], &I, ValueLatticeElement::get(C));
1888 // The pointer operand's lattice has found to be a constant, however, the
1889 // returned pointer of the GEP may not be freely substituted, as it may have
1890 // been derived from a pointer with potentially different provenance.
1891 if (PtrMayHaveDifferentProvenance)
1892 ValueState[&I].setMayHaveDifferentProvenance(true);
1893 } else
1894 markOverdefined(&I);
1895}
1896
1897void SCCPInstVisitor::visitAllocaInst(AllocaInst &I) {
1898 if (!NullPointerIsDefined(I.getFunction(), I.getAddressSpace()))
1899 return (void)markNotNull(ValueState[&I], &I);
1900
1901 markOverdefined(&I);
1902}
1903
1904void SCCPInstVisitor::visitStoreInst(StoreInst &SI) {
1905 // If this store is of a struct, ignore it.
1906 if (SI.getOperand(0)->getType()->isStructTy())
1907 return;
1908
1909 if (TrackedGlobals.empty() || !isa<GlobalVariable>(SI.getOperand(1)))
1910 return;
1911
1912 GlobalVariable *GV = cast<GlobalVariable>(SI.getOperand(1));
1913 auto I = TrackedGlobals.find(GV);
1914 if (I == TrackedGlobals.end())
1915 return;
1916
1917 // Get the value we are storing into the global, then merge it.
1918 mergeInValue(I->second, GV, getValueState(SI.getOperand(0)),
1919 ValueLatticeElement::MergeOptions().setCheckWiden(false));
1920 if (I->second.isOverdefined())
1921 TrackedGlobals.erase(I); // No need to keep tracking this!
1922}
1923
1925 if (const auto *CB = dyn_cast<CallBase>(I)) {
1926 if (CB->getType()->isIntOrIntVectorTy())
1927 if (std::optional<ConstantRange> Range = CB->getRange())
1929 if (CB->getType()->isPointerTy() && CB->isReturnNonNull())
1932 }
1933
1934 if (I->getType()->isIntOrIntVectorTy())
1935 if (MDNode *Ranges = I->getMetadata(LLVMContext::MD_range))
1938 if (I->hasMetadata(LLVMContext::MD_nonnull))
1941
1943}
1944
1945// Handle load instructions. If the operand is a constant pointer to a constant
1946// global, we can replace the load with the loaded constant value!
1947void SCCPInstVisitor::visitLoadInst(LoadInst &I) {
1948 // If this load is of a struct or the load is volatile, just mark the result
1949 // as overdefined.
1950 if (I.getType()->isStructTy() || I.isVolatile())
1951 return (void)markOverdefined(&I);
1952
1953 // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would
1954 // discover a concrete value later.
1955 if (ValueState[&I].isOverdefined())
1956 return (void)markOverdefined(&I);
1957
1958 const ValueLatticeElement &PtrVal = getValueState(I.getOperand(0));
1959 if (PtrVal.isUnknownOrUndef())
1960 return; // The pointer is not resolved yet!
1961
1962 if (SCCPSolver::isConstant(PtrVal)) {
1963 Constant *Ptr = getConstant(PtrVal, I.getOperand(0)->getType());
1964 ValueLatticeElement &IV = ValueState[&I];
1965
1966 // load null is undefined.
1967 if (isa<ConstantPointerNull>(Ptr)) {
1968 if (NullPointerIsDefined(I.getFunction(), I.getPointerAddressSpace()))
1969 return (void)markOverdefined(IV, &I);
1970 else
1971 return;
1972 }
1973
1974 // Transform load (constant global) into the value loaded.
1975 if (auto *GV = dyn_cast<GlobalVariable>(Ptr)) {
1976 if (!TrackedGlobals.empty()) {
1977 // If we are tracking this global, merge in the known value for it.
1978 auto It = TrackedGlobals.find(GV);
1979 if (It != TrackedGlobals.end()) {
1980 mergeInValue(IV, &I, It->second, getMaxWidenStepsOpts());
1981 return;
1982 }
1983 }
1984 }
1985
1986 // Transform load from a constant into a constant if possible.
1987 if (Constant *C = ConstantFoldLoadFromConstPtr(Ptr, I.getType(), DL))
1988 return (void)markConstant(IV, &I, C);
1989 }
1990
1991 // Fall back to metadata.
1992 mergeInValue(ValueState[&I], &I, getValueFromMetadata(&I));
1993}
1994
1995void SCCPInstVisitor::visitCallBase(CallBase &CB) {
1996 handleCallResult(CB);
1997 handleCallArguments(CB);
1998}
1999
2000void SCCPInstVisitor::handleCallOverdefined(CallBase &CB) {
2002
2003 // Void return and not tracking callee, just bail.
2004 if (CB.getType()->isVoidTy())
2005 return;
2006
2007 // Always mark struct return as overdefined.
2008 if (CB.getType()->isStructTy())
2009 return (void)markOverdefined(&CB);
2010
2011 if (!F || !F->isDeclaration())
2012 return (void)mergeInValue(ValueState[&CB], &CB, getValueFromMetadata(&CB));
2013
2014 // Otherwise, if we have a single return value case, and if the function is
2015 // a declaration, maybe we can constant fold it.
2016 const TargetLibraryInfo *TLI = &GetTLI(*F);
2017 if (canConstantFoldCallTo(&CB, F, TLI)) {
2019 for (const Use &A : CB.args()) {
2020 if (A.get()->getType()->isStructTy())
2021 return markOverdefined(&CB); // Can't handle struct args.
2022 if (A.get()->getType()->isMetadataTy())
2023 continue; // Carried in CB, not allowed in Operands.
2024 const ValueLatticeElement &State = getValueState(A);
2025
2026 if (State.isUnknownOrUndef())
2027 return; // Operands are not resolved yet.
2028 if (SCCPSolver::isOverdefined(State))
2029 return (void)markOverdefined(&CB);
2030 assert(SCCPSolver::isConstant(State) && "Unknown state!");
2031 Operands.push_back(getConstant(State, A->getType()));
2032 }
2033
2034 if (SCCPSolver::isOverdefined(getValueState(&CB)))
2035 return (void)markOverdefined(&CB);
2036
2037 // If we can constant fold this, mark the result of the call as a
2038 // constant.
2039 if (Constant *C = ConstantFoldCall(&CB, F, Operands, TLI)) {
2040 mergeInValue(ValueState[&CB], &CB, ValueLatticeElement::get(C));
2041 return;
2042 }
2043 }
2044
2045 // Fall back to metadata.
2046 mergeInValue(ValueState[&CB], &CB, getValueFromMetadata(&CB));
2047}
2048
2049void SCCPInstVisitor::handleCallArguments(CallBase &CB) {
2051 // If this is a local function that doesn't have its address taken, mark its
2052 // entry block executable and merge in the actual arguments to the call into
2053 // the formal arguments of the function.
2054 if (TrackingIncomingArguments.count(F)) {
2055 markBlockExecutable(&F->front());
2056
2057 // Propagate information from this call site into the callee.
2058 auto CAI = CB.arg_begin();
2059 for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); AI != E;
2060 ++AI, ++CAI) {
2061 // If this argument is byval, and if the function is not readonly, there
2062 // will be an implicit copy formed of the input aggregate.
2063 if (AI->hasByValAttr() && !F->onlyReadsMemory()) {
2064 markOverdefined(&*AI);
2065 continue;
2066 }
2067
2068 if (auto *STy = dyn_cast<StructType>(AI->getType())) {
2069 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
2070 ValueLatticeElement CallArg = getStructValueState(*CAI, i);
2071 mergeInValue(getStructValueState(&*AI, i), &*AI, CallArg,
2073 }
2074 } else {
2075 ValueLatticeElement CallArg =
2076 getValueState(*CAI).intersect(getArgAttributeVL(&*AI));
2077 mergeInValue(ValueState[&*AI], &*AI, CallArg, getMaxWidenStepsOpts());
2078 }
2079 }
2080 }
2081}
2082
2083void SCCPInstVisitor::handlePredicate(Instruction *I, Value *CopyOf,
2084 const PredicateBase *PI) {
2085 ValueLatticeElement CopyOfVal = getValueState(CopyOf);
2086 const std::optional<PredicateConstraint> &Constraint = PI->getConstraint();
2087 if (!Constraint) {
2088 mergeInValue(ValueState[I], I, CopyOfVal);
2089 return;
2090 }
2091
2092 CmpInst::Predicate Pred = Constraint->Predicate;
2093 Value *OtherOp = Constraint->OtherOp;
2094
2095 // Wait until OtherOp is resolved.
2096 if (getValueState(OtherOp).isUnknown()) {
2097 addAdditionalUser(OtherOp, I);
2098 return;
2099 }
2100
2101 ValueLatticeElement CondVal = getValueState(OtherOp);
2102 ValueLatticeElement &IV = ValueState[I];
2103 if (CondVal.isConstantRange() || CopyOfVal.isConstantRange()) {
2104 auto ImposedCR =
2105 ConstantRange::getFull(DL.getTypeSizeInBits(CopyOf->getType()));
2106
2107 // Get the range imposed by the condition.
2108 if (CondVal.isConstantRange())
2110 Pred, CondVal.getConstantRange());
2111
2112 // Combine range info for the original value with the new range from the
2113 // condition.
2114 auto CopyOfCR = CopyOfVal.asConstantRange(CopyOf->getType(),
2115 /*UndefAllowed=*/true);
2116 // Treat an unresolved input like a full range.
2117 if (CopyOfCR.isEmptySet())
2118 CopyOfCR = ConstantRange::getFull(CopyOfCR.getBitWidth());
2119 auto NewCR = ImposedCR.intersectWith(CopyOfCR);
2120 // If the existing information is != x, do not use the information from
2121 // a chained predicate, as the != x information is more likely to be
2122 // helpful in practice.
2123 if (!CopyOfCR.contains(NewCR) && CopyOfCR.getSingleMissingElement())
2124 NewCR = std::move(CopyOfCR);
2125
2126 // The new range is based on a branch condition. That guarantees that
2127 // neither of the compare operands can be undef in the branch targets,
2128 // unless we have conditions that are always true/false (e.g. icmp ule
2129 // i32, %a, i32_max). For the latter overdefined/empty range will be
2130 // inferred, but the branch will get folded accordingly anyways.
2131 addAdditionalUser(OtherOp, I);
2132 mergeInValue(
2133 IV, I, ValueLatticeElement::getRange(NewCR, /*MayIncludeUndef*/ false));
2134 return;
2135 } else if (Pred == CmpInst::ICMP_EQ &&
2136 (CondVal.isConstant() || CondVal.isNotConstant())) {
2137 // For non-integer values or integer constant expressions, only
2138 // propagate equal constants or not-constants.
2139 addAdditionalUser(OtherOp, I);
2140 if (CopyOf->getType()->isPointerTy())
2141 CondVal.setMayHaveDifferentProvenance(true);
2142 mergeInValue(IV, I, CondVal);
2143 return;
2144 } else if (Pred == CmpInst::ICMP_NE && CondVal.isConstant()) {
2145 // Propagate inequalities.
2146 addAdditionalUser(OtherOp, I);
2147 mergeInValue(IV, I, ValueLatticeElement::getNot(CondVal.getConstant()));
2148 return;
2149 }
2150
2151 return (void)mergeInValue(IV, I, CopyOfVal);
2152}
2153
2154void SCCPInstVisitor::handleCallResult(CallBase &CB) {
2156
2157 if (auto *II = dyn_cast<IntrinsicInst>(&CB)) {
2158 if (II->getIntrinsicID() == Intrinsic::vscale) {
2159 unsigned BitWidth = CB.getType()->getScalarSizeInBits();
2160 const ConstantRange Result = getVScaleRange(II->getFunction(), BitWidth);
2161 return (void)mergeInValue(ValueState[II], II,
2163 }
2164 if (II->getIntrinsicID() == Intrinsic::experimental_get_vector_length) {
2165 Value *CountArg = II->getArgOperand(0);
2166 Value *VF = II->getArgOperand(1);
2167 bool Scalable = cast<ConstantInt>(II->getArgOperand(2))->isOne();
2168
2169 // Computation happens in the larger type.
2170 unsigned BitWidth = std::max(CountArg->getType()->getScalarSizeInBits(),
2171 VF->getType()->getScalarSizeInBits());
2172
2173 ConstantRange Count = getValueState(CountArg)
2174 .asConstantRange(CountArg->getType(), false)
2175 .zeroExtend(BitWidth);
2176 ConstantRange MaxLanes = getValueState(VF)
2177 .asConstantRange(VF->getType(), false)
2178 .zeroExtend(BitWidth);
2179 if (Scalable)
2180 MaxLanes =
2181 MaxLanes.multiply(getVScaleRange(II->getFunction(), BitWidth));
2182
2183 // The result is always less than both Count and MaxLanes.
2184 ConstantRange Result = ConstantRange::getNonEmpty(
2186 APIntOps::umin(Count.getUnsignedMax(), MaxLanes.getUnsignedMax()) +
2187 1);
2188
2189 // If Count <= MaxLanes, getvectorlength(Count, MaxLanes) = Count
2190 if (Count.icmp(CmpInst::ICMP_ULE, MaxLanes))
2191 Result = std::move(Count);
2192
2193 Result = Result.truncate(II->getType()->getScalarSizeInBits());
2194 return (void)mergeInValue(ValueState[II], II,
2196 }
2197
2198 if (ConstantRange::isIntrinsicSupported(II->getIntrinsicID())) {
2199 // Compute result range for intrinsics supported by ConstantRange.
2200 // Do this even if we don't know a range for all operands, as we may
2201 // still know something about the result range, e.g. of abs(x).
2203 for (Value *Op : II->args()) {
2204 const ValueLatticeElement &State = getValueState(Op);
2205 if (State.isUnknownOrUndef())
2206 return;
2207 OpRanges.push_back(
2208 State.asConstantRange(Op->getType(), /*UndefAllowed=*/false));
2209 }
2210
2211 ConstantRange Result =
2212 ConstantRange::intrinsic(II->getIntrinsicID(), OpRanges);
2213 return (void)mergeInValue(ValueState[II], II,
2215 }
2216 }
2217
2218 // The common case is that we aren't tracking the callee, either because we
2219 // are not doing interprocedural analysis or the callee is indirect, or is
2220 // external. Handle these cases first.
2221 if (!F || F->isDeclaration())
2222 return handleCallOverdefined(CB);
2223
2224 // If this is a single/zero retval case, see if we're tracking the function.
2225 if (auto *STy = dyn_cast<StructType>(F->getReturnType())) {
2226 if (!MRVFunctionsTracked.count(F))
2227 return handleCallOverdefined(CB); // Not tracking this callee.
2228
2229 // If we are tracking this callee, propagate the result of the function
2230 // into this call site.
2231 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
2232 mergeInValue(getStructValueState(&CB, i), &CB,
2233 TrackedMultipleRetVals[std::make_pair(F, i)],
2235 } else {
2236 auto TFRVI = TrackedRetVals.find(F);
2237 if (TFRVI == TrackedRetVals.end())
2238 return handleCallOverdefined(CB); // Not tracking this callee.
2239
2240 // If so, propagate the return value of the callee into this call result.
2241 mergeInValue(ValueState[&CB], &CB, TFRVI->second, getMaxWidenStepsOpts());
2242 }
2243}
2244
2245bool SCCPInstVisitor::isInstFullyOverDefined(Instruction &Inst) {
2246 // For structure Type, we handle each member separately.
2247 // A structure object won't be considered as overdefined when
2248 // there is at least one member that is not overdefined.
2249 if (StructType *STy = dyn_cast<StructType>(Inst.getType())) {
2250 for (unsigned i = 0, e = STy->getNumElements(); i < e; ++i) {
2251 if (!getStructValueState(&Inst, i).isOverdefined())
2252 return false;
2253 }
2254 return true;
2255 }
2256
2257 return getValueState(&Inst).isOverdefined();
2258}
2259
2261 // Process the work lists until they are empty!
2262 while (!BBWorkList.empty() || !InstWorkList.empty()) {
2263 // Process the instruction work list.
2264 while (!InstWorkList.empty()) {
2265 Instruction *I = InstWorkList.pop_back_val();
2266 Invalidated.erase(I);
2267
2268 LLVM_DEBUG(dbgs() << "\nPopped off I-WL: " << *I << '\n');
2269
2270 visit(I);
2271 }
2272
2273 // Process the basic block work list.
2274 while (!BBWorkList.empty()) {
2275 BasicBlock *BB = BBWorkList.pop_back_val();
2276 BBVisited.insert(BB);
2277
2278 LLVM_DEBUG(dbgs() << "\nPopped off BBWL: " << *BB << '\n');
2279 for (Instruction &I : *BB) {
2280 CurI = &I;
2281 visit(I);
2282 }
2283 CurI = nullptr;
2284 }
2285 }
2286}
2287
2289 // Look for instructions which produce undef values.
2290 if (I.getType()->isVoidTy())
2291 return false;
2292
2293 if (auto *STy = dyn_cast<StructType>(I.getType())) {
2294 // Only a few things that can be structs matter for undef.
2295
2296 // Tracked calls must never be marked overdefined in resolvedUndefsIn.
2297 if (auto *CB = dyn_cast<CallBase>(&I))
2298 if (Function *F = CB->getCalledFunction())
2299 if (MRVFunctionsTracked.count(F))
2300 return false;
2301
2302 // extractvalue and insertvalue don't need to be marked; they are
2303 // tracked as precisely as their operands.
2305 return false;
2306 // Send the results of everything else to overdefined. We could be
2307 // more precise than this but it isn't worth bothering.
2308 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
2309 ValueLatticeElement &LV = getStructValueState(&I, i);
2310 if (LV.isUnknown()) {
2311 markOverdefined(LV, &I);
2312 return true;
2313 }
2314 }
2315 return false;
2316 }
2317
2318 ValueLatticeElement &LV = getValueState(&I);
2319 if (!LV.isUnknown())
2320 return false;
2321
2322 // There are two reasons a call can have an undef result
2323 // 1. It could be tracked.
2324 // 2. It could be constant-foldable.
2325 // Because of the way we solve return values, tracked calls must
2326 // never be marked overdefined in resolvedUndefsIn.
2327 if (auto *CB = dyn_cast<CallBase>(&I))
2328 if (Function *F = CB->getCalledFunction())
2329 if (TrackedRetVals.count(F))
2330 return false;
2331
2332 if (isa<LoadInst>(I)) {
2333 // A load here means one of two things: a load of undef from a global,
2334 // a load from an unknown pointer. Either way, having it return undef
2335 // is okay.
2336 return false;
2337 }
2338
2339 markOverdefined(&I);
2340 return true;
2341}
2342
2343/// While solving the dataflow for a function, we don't compute a result for
2344/// operations with an undef operand, to allow undef to be lowered to a
2345/// constant later. For example, constant folding of "zext i8 undef to i16"
2346/// would result in "i16 0", and if undef is later lowered to "i8 1", then the
2347/// zext result would become "i16 1" and would result into an overdefined
2348/// lattice value once merged with the previous result. Not computing the
2349/// result of the zext (treating undef the same as unknown) allows us to handle
2350/// a later undef->constant lowering more optimally.
2351///
2352/// However, if the operand remains undef when the solver returns, we do need
2353/// to assign some result to the instruction (otherwise we would treat it as
2354/// unreachable). For simplicity, we mark any instructions that are still
2355/// unknown as overdefined.
2357 bool MadeChange = false;
2358 for (BasicBlock &BB : F) {
2359 if (!BBExecutable.count(&BB))
2360 continue;
2361
2362 for (Instruction &I : BB)
2363 MadeChange |= resolvedUndef(I);
2364 }
2365
2366 LLVM_DEBUG(if (MadeChange) dbgs()
2367 << "\nResolved undefs in " << F.getName() << '\n');
2368
2369 return MadeChange;
2370}
2371
2372//===----------------------------------------------------------------------===//
2373//
2374// SCCPSolver implementations
2375//
2377 const DataLayout &DL,
2378 std::function<const TargetLibraryInfo &(Function &)> GetTLI,
2379 LLVMContext &Ctx)
2380 : Visitor(new SCCPInstVisitor(DL, std::move(GetTLI), Ctx)) {}
2381
2382SCCPSolver::~SCCPSolver() = default;
2383
2385 return Visitor->getDataLayout();
2386}
2387
2389 AssumptionCache &AC) {
2390 Visitor->addPredicateInfo(F, DT, AC);
2391}
2392
2394 Visitor->removeSSACopies(F);
2395}
2396
2398 return Visitor->markBlockExecutable(BB);
2399}
2400
2402 return Visitor->getPredicateInfoFor(I);
2403}
2404
2406 Visitor->trackValueOfGlobalVariable(GV);
2407}
2408
2410 Visitor->addTrackedFunction(F);
2411}
2412
2414 Visitor->addToMustPreserveReturnsInFunctions(F);
2415}
2416
2418 return Visitor->mustPreserveReturn(F);
2419}
2420
2422 Visitor->addArgumentTrackedFunction(F);
2423}
2424
2426 return Visitor->isArgumentTrackedFunction(F);
2427}
2428
2431 return Visitor->getArgumentTrackedFunctions();
2432}
2433
2434void SCCPSolver::solve() { Visitor->solve(); }
2435
2437 return Visitor->resolvedUndefsIn(F);
2438}
2439
2441 Visitor->solveWhileResolvedUndefsIn(M);
2442}
2443
2444void
2446 Visitor->solveWhileResolvedUndefsIn(WorkList);
2447}
2448
2450 Visitor->solveWhileResolvedUndefs();
2451}
2452
2454 return Visitor->isBlockExecutable(BB);
2455}
2456
2458 return Visitor->isEdgeFeasible(From, To);
2459}
2460
2461std::vector<ValueLatticeElement>
2463 return Visitor->getStructLatticeValueFor(V);
2464}
2465
2467 return Visitor->removeLatticeValueFor(V);
2468}
2469
2471 Visitor->resetLatticeValueFor(Call);
2472}
2473
2475 return Visitor->getLatticeValueFor(V);
2476}
2477
2480 return Visitor->getTrackedRetVals();
2481}
2482
2485 return Visitor->getTrackedGlobals();
2486}
2487
2489 return Visitor->getMRVFunctionsTracked();
2490}
2491
2492void SCCPSolver::markOverdefined(Value *V) { Visitor->markOverdefined(V); }
2493
2495 Visitor->trackValueOfArgument(V);
2496}
2497
2499 return Visitor->isStructLatticeConstant(F, STy);
2500}
2501
2503 Type *Ty) const {
2504 return Visitor->getConstant(LV, Ty);
2505}
2506
2508 return Visitor->getConstantOrNull(V);
2509}
2510
2512 const SmallVectorImpl<ArgInfo> &Args) {
2513 Visitor->setLatticeValueForSpecializationArguments(F, Args);
2514}
2515
2517 Visitor->markFunctionUnreachable(F);
2518}
2519
2520void SCCPSolver::visit(Instruction *I) { Visitor->visit(I); }
2521
2522void SCCPSolver::visitCall(CallInst &I) { Visitor->visitCall(I); }
const TargetLowering & TLI
SDValue Pred
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
#define X(NUM, ENUM, NAME)
Definition ELF.h:665
static GCRegistry::Add< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
Hexagon Common GEP
#define F(x, y, z)
Definition MD5.cpp:54
#define I(x, y, z)
Definition MD5.cpp:57
#define T
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
uint64_t IntrinsicInst * II
static ValueLatticeElement::MergeOptions getMaxWidenStepsOpts()
Returns MergeOptions with MaxWidenSteps set to MaxNumRangeExtensions.
static const unsigned MaxNumRangeExtensions
static ValueLatticeElement getValueFromMetadata(const Instruction *I)
SI Fold Operands
std::pair< BasicBlock *, BasicBlock * > Edge
This file implements a set that has insertion order iteration characteristics.
static ConstantInt * getConstantInt(Value *V, const DataLayout &DL)
Extract ConstantInt from value, looking through IntToPtr and PointerNullValue.
#define LLVM_DEBUG(...)
Definition Debug.h:119
Value * RHS
Value * LHS
static const uint32_t IV[8]
Definition blake3_impl.h:83
Class for arbitrary precision integers.
Definition APInt.h:78
unsigned countr_zero() const
Count the number of trailing zero bits.
Definition APInt.h:1659
bool ule(const APInt &RHS) const
Unsigned less or equal comparison.
Definition APInt.h:1154
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
Definition APInt.h:196
an instruction to allocate memory on the stack
This class represents an incoming formal argument to a Function.
Definition Argument.h:32
A cache of @llvm.assume calls within a function.
Functions, function parameters, and return types can have attributes to indicate how they should be t...
Definition Attributes.h:107
LLVM_ABI const ConstantRange & getRange() const
Returns the value of the range attribute.
static LLVM_ABI Attribute get(LLVMContext &Context, AttrKind Kind, uint64_t Val=0)
Return a uniquified Attribute object.
bool isValid() const
Return true if the attribute is any kind of attribute.
Definition Attributes.h:263
LLVM Basic Block Representation.
Definition BasicBlock.h:62
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition BasicBlock.h:509
const Function * getParent() const
Return the enclosing method, or null if none.
Definition BasicBlock.h:213
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition BasicBlock.h:206
LLVM_ABI LLVMContext & getContext() const
Get the context in which this basic block lives.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction; assumes that the block is well-formed.
Definition BasicBlock.h:237
LLVM_ABI void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
LLVM_ABI unsigned getNoWrapKind() const
Returns one of OBO::NoSignedWrap or OBO::NoUnsignedWrap.
LLVM_ABI Instruction::BinaryOps getBinaryOp() const
Returns the binary operation underlying the intrinsic.
static LLVM_ABI BinaryOperator * Create(BinaryOps Op, Value *S1, Value *S2, const Twine &Name=Twine(), InsertPosition InsertBefore=nullptr)
Construct a binary instruction, given the opcode and the two operands.
Function * getFunction() const
Definition Constants.h:1126
BasicBlock * getBasicBlock() const
Definition Constants.h:1125
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
std::optional< OperandBundleUse > getOperandBundle(StringRef Name) const
Return an operand bundle by name, if present.
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation or the function signa...
User::op_iterator arg_begin()
Return the iterator pointing to the beginning of the argument list.
LLVM_ABI bool isMustTailCall() const
Tests if this call site must be tail call optimized.
CallBr instruction, tracking function calls that may not return control but instead transfer it to a ...
This class represents a function call, abstracting a target machine's calling convention.
This is the base class for all instructions that perform data casts.
Definition InstrTypes.h:512
static LLVM_ABI CastInst * Create(Instruction::CastOps, Value *S, Type *Ty, const Twine &Name="", InsertPosition InsertBefore=nullptr)
Provides a way to construct any of the CastInst subclasses using an opcode instead of the subclass's ...
This class is the base class for the comparison instructions.
Definition InstrTypes.h:728
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition InstrTypes.h:740
@ ICMP_SLE
signed less or equal
Definition InstrTypes.h:770
@ ICMP_NE
not equal
Definition InstrTypes.h:762
@ ICMP_ULE
unsigned less or equal
Definition InstrTypes.h:766
This is the shared class of boolean and integer constants.
Definition Constants.h:87
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
Definition Constants.h:219
static LLVM_ABI ConstantInt * getFalse(LLVMContext &Context)
static LLVM_ABI ConstantPointerNull * get(PointerType *T)
Static factory methods - Return objects of the specified value.
This class represents a range of values.
LLVM_ABI ConstantRange add(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an addition of a value in this ran...
const APInt * getSingleElement() const
If this set contains a single element, return it, otherwise return null.
LLVM_ABI ConstantRange castOp(Instruction::CastOps CastOp, uint32_t BitWidth) const
Return a new range representing the possible values resulting from an application of the specified ca...
LLVM_ABI bool isFullSet() const
Return true if this set contains all of the elements possible for this data-type.
LLVM_ABI bool icmp(CmpInst::Predicate Pred, const ConstantRange &Other) const
Does the predicate Pred hold between ranges this and Other?
static LLVM_ABI ConstantRange intrinsic(Intrinsic::ID IntrinsicID, ArrayRef< ConstantRange > Ops)
Compute range of intrinsic result for the given operand ranges.
LLVM_ABI bool isSizeLargerThan(uint64_t MaxSize) const
Compare set size of this range with Value.
static LLVM_ABI bool isIntrinsicSupported(Intrinsic::ID IntrinsicID)
Returns true if ConstantRange calculations are supported for intrinsic with IntrinsicID.
bool isSingleElement() const
Return true if this set contains exactly one member.
LLVM_ABI ConstantRange truncate(uint32_t BitWidth, unsigned NoWrapKind=0) const
Return a new range in the specified integer type, which must be strictly smaller than the current typ...
LLVM_ABI bool isAllNonNegative() const
Return true if all values in this range are non-negative.
static LLVM_ABI ConstantRange makeAllowedICmpRegion(CmpInst::Predicate Pred, const ConstantRange &Other)
Produce the smallest range such that all values that may satisfy the given predicate with any value c...
LLVM_ABI ConstantRange multiply(const ConstantRange &Other, unsigned NoWrapKind=0) const
Return a new range representing the possible values resulting from a multiplication of a value in thi...
static LLVM_ABI ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
LLVM_ABI ConstantRange inverse() const
Return a new range that is the logical not of the current set.
LLVM_ABI bool contains(const APInt &Val) const
Return true if the specified value is in the set.
LLVM_ABI APInt getUnsignedMax() const
Return the largest unsigned value contained in the ConstantRange.
LLVM_ABI ConstantRange intersectWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the intersection of this range with another range.
static ConstantRange getNonEmpty(APInt Lower, APInt Upper)
Create non-empty constant range with the given bounds.
static LLVM_ABI ConstantRange makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp, const ConstantRange &Other, unsigned NoWrapKind)
Produce the largest range containing all X such that "X BinOp Y" is guaranteed not to wrap (overflow)...
LLVM_ABI ConstantRange binaryOp(Instruction::BinaryOps BinOp, const ConstantRange &Other) const
Return a new range representing the possible values resulting from an application of the specified bi...
LLVM_ABI ConstantRange sub(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a subtraction of a value in this r...
static LLVM_ABI Constant * get(StructType *T, ArrayRef< Constant * > V)
This is an important base class in LLVM.
Definition Constant.h:44
bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
Definition Constant.h:65
static LLVM_ABI Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
A parsed version of the target data layout string in and methods for querying it.
Definition DataLayout.h:64
static DebugLoc getTemporary()
Definition DebugLoc.h:152
Implements a dense probed hash-table based set.
Definition DenseSet.h:283
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition Dominators.h:122
This instruction extracts a struct member or array element value from an aggregate value.
unsigned getNumIndices() const
idx_iterator idx_begin() const
This class represents a freeze function that returns random concrete value if an operand is either a ...
Argument * arg_iterator
Definition Function.h:73
static GEPNoWrapFlags noUnsignedWrap()
void applyUpdatesPermissive(ArrayRef< UpdateT > Updates)
Submit updates to all available trees.
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Module * getParent()
Get the module that this global value is contained inside of...
Type * getValueType() const
const Constant * getInitializer() const
getInitializer - Return the initializer for this global variable.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition IRBuilder.h:2990
This instruction inserts a struct field of array element value into an aggregate value.
Value * getInsertedValueOperand()
unsigned getNumIndices() const
idx_iterator idx_begin() const
Base class for instruction visitors.
Definition InstVisitor.h:78
void visit(Iterator Start, Iterator End)
Definition InstVisitor.h:87
LLVM_ABI void setHasNoUnsignedWrap(bool b=true)
Set or clear the nuw flag on this instruction, which must be an operator which supports this flag.
LLVM_ABI bool hasNoUnsignedWrap() const LLVM_READONLY
Determine whether the no unsigned wrap flag is set.
LLVM_ABI unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
LLVM_ABI bool hasNoSignedWrap() const LLVM_READONLY
Determine whether the no signed wrap flag is set.
LLVM_ABI void setHasNoSignedWrap(bool b=true)
Set or clear the nsw flag on this instruction, which must be an operator which supports this flag.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
LLVM_ABI InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
LLVM_ABI bool isExact() const LLVM_READONLY
Determine whether the exact flag is set.
LLVM_ABI BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
LLVM_ABI void setNonNeg(bool b=true)
Set or clear the nneg flag on this instruction, which must be a zext instruction.
LLVM_ABI bool comesBefore(const Instruction *Other) const
Given an instruction Other in the same basic block as this instruction, return true if this instructi...
LLVM_ABI bool hasNonNeg() const LLVM_READONLY
Determine whether the the nneg flag is set.
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
LLVM_ABI void setIsExact(bool b=true)
Set or clear the exact flag on this instruction, which must be an operator which supports this flag.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
bool isSpecialTerminator() const
Invoke instruction.
This is an important class for using LLVM in a threaded context.
Definition LLVMContext.h:76
An instruction for reading from memory.
Metadata node.
Definition Metadata.h:1081
This class implements a map that also provides access to all stored values in a deterministic order.
Definition MapVector.h:39
A Module instance is used to store all the information related to an LLVM module.
Definition Module.h:68
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
LLVM_ABI std::optional< PredicateConstraint > getConstraint() const
Fetch condition in the form of PredicateConstraint, if possible.
Return a value (possibly void), from a function.
Helper class for SCCPSolver.
const MapVector< Function *, ValueLatticeElement > & getTrackedRetVals() const
const PredicateBase * getPredicateInfoFor(Instruction *I)
std::vector< ValueLatticeElement > getStructLatticeValueFor(Value *V) const
bool resolvedUndef(Instruction &I)
void markFunctionUnreachable(Function *F)
bool markBlockExecutable(BasicBlock *BB)
bool resolvedUndefsIn(Function &F)
While solving the dataflow for a function, we don't compute a result for operations with an undef ope...
Constant * getConstant(const ValueLatticeElement &LV, Type *Ty) const
SCCPInstVisitor(const DataLayout &DL, std::function< const TargetLibraryInfo &(Function &)> GetTLI, LLVMContext &Ctx)
const DenseMap< GlobalVariable *, ValueLatticeElement > & getTrackedGlobals() const
const ValueLatticeElement & getLatticeValueFor(Value *V) const
void removeLatticeValueFor(Value *V)
void trackValueOfArgument(Argument *A)
void visitCallInst(CallInst &I)
void markOverdefined(Value *V)
bool isArgumentTrackedFunction(Function *F)
void addTrackedFunction(Function *F)
void solveWhileResolvedUndefsIn(Module &M)
void trackValueOfGlobalVariable(GlobalVariable *GV)
Constant * getConstantOrNull(Value *V) const
void removeSSACopies(Function &F)
const SmallPtrSet< Function *, 16 > & getMRVFunctionsTracked() const
const SmallPtrSetImpl< Function * > & getArgumentTrackedFunctions() const
void resetLatticeValueFor(CallBase *Call)
Invalidate the Lattice Value of Call and its users after specializing the call.
ValueLatticeElement getArgAttributeVL(Argument *A)
void addPredicateInfo(Function &F, DominatorTree &DT, AssumptionCache &AC)
void addToMustPreserveReturnsInFunctions(Function *F)
void addArgumentTrackedFunction(Function *F)
bool isStructLatticeConstant(Function *F, StructType *STy)
void solveWhileResolvedUndefsIn(SmallVectorImpl< Function * > &WorkList)
bool isBlockExecutable(BasicBlock *BB) const
bool mustPreserveReturn(Function *F)
void setLatticeValueForSpecializationArguments(Function *F, const SmallVectorImpl< ArgInfo > &Args)
bool isEdgeFeasible(BasicBlock *From, BasicBlock *To) const
const DataLayout & getDataLayout() const
SCCPSolver - This interface class is a general purpose solver for Sparse Conditional Constant Propaga...
Definition SCCPSolver.h:66
LLVM_ABI void visitCall(CallInst &I)
LLVM_ABI ~SCCPSolver()
LLVM_ABI void resetLatticeValueFor(CallBase *Call)
Invalidate the Lattice Value of Call and its users after specializing the call.
LLVM_ABI void trackValueOfGlobalVariable(GlobalVariable *GV)
trackValueOfGlobalVariable - Clients can use this method to inform the SCCPSolver that it should trac...
LLVM_ABI bool tryToReplaceWithConstant(Value *V)
LLVM_ABI void inferArgAttributes() const
LLVM_ABI bool isStructLatticeConstant(Function *F, StructType *STy)
LLVM_ABI void addPredicateInfo(Function &F, DominatorTree &DT, AssumptionCache &AC)
LLVM_ABI void solve()
Solve - Solve for constants and executable blocks.
LLVM_ABI void visit(Instruction *I)
LLVM_ABI void trackValueOfArgument(Argument *V)
trackValueOfArgument - Mark the specified argument overdefined unless it have range attribute.
LLVM_ABI const DenseMap< GlobalVariable *, ValueLatticeElement > & getTrackedGlobals() const
getTrackedGlobals - Get and return the set of inferred initializers for global variables.
LLVM_ABI void addTrackedFunction(Function *F)
addTrackedFunction - If the SCCP solver is supposed to track calls into and out of the specified func...
LLVM_ABI void solveWhileResolvedUndefsIn(Module &M)
LLVM_ABI const PredicateBase * getPredicateInfoFor(Instruction *I)
LLVM_ABI const SmallPtrSetImpl< Function * > & getArgumentTrackedFunctions() const
LLVM_ABI const SmallPtrSet< Function *, 16 > & getMRVFunctionsTracked() const
getMRVFunctionsTracked - Get the set of functions which return multiple values tracked by the pass.
LLVM_ABI bool resolvedUndefsIn(Function &F)
resolvedUndefsIn - While solving the dataflow for a function, we assume that branches on undef values...
LLVM_ABI const DataLayout & getDataLayout() const
LLVM_ABI void addArgumentTrackedFunction(Function *F)
static LLVM_ABI bool isReplaceableConstant(const ValueLatticeElement &LV)
LLVM_ABI void solveWhileResolvedUndefs()
LLVM_ABI void removeLatticeValueFor(Value *V)
LLVM_ABI std::vector< ValueLatticeElement > getStructLatticeValueFor(Value *V) const
LLVM_ABI Constant * getConstantOrNull(Value *V) const
Return either a Constant or nullptr for a given Value.
LLVM_ABI bool simplifyInstsInBlock(BasicBlock &BB, SmallPtrSetImpl< Value * > &InsertedValues, Statistic &InstRemovedStat, Statistic &InstReplacedStat)
LLVM_ABI Constant * getConstant(const ValueLatticeElement &LV, Type *Ty) const
Helper to return a Constant if LV is either a constant or a constant range with a single element.
LLVM_ABI const ValueLatticeElement & getLatticeValueFor(Value *V) const
LLVM_ABI void addToMustPreserveReturnsInFunctions(Function *F)
Add function to the list of functions whose return cannot be modified.
LLVM_ABI bool removeNonFeasibleEdges(BasicBlock *BB, DomTreeUpdater &DTU, BasicBlock *&NewUnreachableBB) const
LLVM_ABI bool isBlockExecutable(BasicBlock *BB) const
LLVM_ABI void inferReturnAttributes() const
LLVM_ABI bool markBlockExecutable(BasicBlock *BB)
markBlockExecutable - This method can be used by clients to mark all of the blocks that are known to ...
LLVM_ABI void setLatticeValueForSpecializationArguments(Function *F, const SmallVectorImpl< ArgInfo > &Args)
Set the Lattice Value for the arguments of a specialization F.
static LLVM_ABI bool isConstant(const ValueLatticeElement &LV)
LLVM_ABI const MapVector< Function *, ValueLatticeElement > & getTrackedRetVals() const
getTrackedRetVals - Get the inferred return value map.
LLVM_ABI bool isEdgeFeasible(BasicBlock *From, BasicBlock *To) const
LLVM_ABI bool mustPreserveReturn(Function *F)
Returns true if the return of the given function cannot be modified.
static LLVM_ABI bool isOverdefined(const ValueLatticeElement &LV)
LLVM_ABI void markFunctionUnreachable(Function *F)
Mark all of the blocks in function F non-executable.
LLVM_ABI bool isArgumentTrackedFunction(Function *F)
Returns true if the given function is in the solver's set of argument-tracked functions.
LLVM_ABI SCCPSolver(const DataLayout &DL, std::function< const TargetLibraryInfo &(Function &)> GetTLI, LLVMContext &Ctx)
LLVM_ABI void markOverdefined(Value *V)
markOverdefined - Mark the specified value overdefined.
LLVM_ABI void removeSSACopies(Function &F)
This class represents the LLVM 'select' instruction.
size_type size() const
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
iterator begin() const
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
A SetVector that performs no allocations if smaller than a certain size.
Definition SetVector.h:346
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void assign(size_type NumElts, ValueParamT Elt)
void resize(size_type N)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
Class to represent struct types.
unsigned getNumElements() const
Random access to the elements.
A wrapper class to simplify modification of SwitchInst cases along with their prof branch_weights met...
Provides information about what library functions are available for the current target.
This class represents a truncation of integer types.
The instances of the Type class are immutable: once they are created, they are never changed.
Definition Type.h:46
bool isPointerTy() const
True if this is an instance of PointerType.
Definition Type.h:277
bool isSingleValueType() const
Return true if the type is a valid type for a register in codegen.
Definition Type.h:306
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
Definition Type.h:354
bool isStructTy() const
True if this is an instance of StructType.
Definition Type.h:271
bool isVoidTy() const
Return true if this is 'void'.
Definition Type.h:141
static UncondBrInst * Create(BasicBlock *Target, InsertPosition InsertBefore=nullptr)
static LLVM_ABI UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
This function has undefined behavior.
A Use represents the edge between a Value definition and its users.
Definition Use.h:35
Value * getOperand(unsigned i) const
Definition User.h:207
This class represents lattice values for constants.
static ValueLatticeElement getRange(ConstantRange CR, bool MayIncludeUndef=false)
void setMayHaveDifferentProvenance(bool V)
LLVM_ABI Constant * getCompare(CmpInst::Predicate Pred, Type *Ty, const ValueLatticeElement &Other, const DataLayout &DL) const
true, false or undef constants, or nullptr if the comparison cannot be evaluated.
bool isConstantRangeIncludingUndef() const
static ValueLatticeElement getNot(Constant *C)
ConstantRange asConstantRange(unsigned BW, bool UndefAllowed=false) const
void setNumRangeExtensions(unsigned N)
const ConstantRange & getConstantRange(bool UndefAllowed=true) const
Returns the constant range for this value.
bool isConstantRange(bool UndefAllowed=true) const
Returns true if this value is a constant range.
static ValueLatticeElement get(Constant *C)
unsigned getNumRangeExtensions() const
Constant * getNotConstant() const
LLVM_ABI ValueLatticeElement intersect(const ValueLatticeElement &Other) const
Combine two sets of facts about the same value into a single set of facts.
Constant * getConstant() const
bool mergeIn(const ValueLatticeElement &RHS, MergeOptions Opts=MergeOptions())
Updates this object to approximate both this object and RHS.
bool mayHaveDifferentProvenance() const
bool markConstant(Constant *V, bool MayIncludeUndef=false)
static ValueLatticeElement getOverdefined()
LLVM Value Representation.
Definition Value.h:75
Type * getType() const
All values are typed, get the type of this value.
Definition Value.h:257
LLVM_ABI std::string getNameOrAsOperand() const
Definition Value.cpp:456
LLVM_ABI void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition Value.cpp:548
iterator_range< user_iterator > users()
Definition Value.h:428
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
Definition Value.cpp:314
LLVM_ABI void takeName(Value *V)
Transfer the name from V to this value.
Definition Value.cpp:395
Represents an op.with.overflow intrinsic.
const ParentTy * getParent() const
Definition ilist_node.h:34
self_iterator getIterator()
Definition ilist_node.h:123
CallInst * Call
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
const APInt & umin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be unsigned.
Definition APInt.h:2284
@ BasicBlock
Various leaf nodes.
Definition ISDOpcodes.h:83
OneUse_match< SubPat > m_OneUse(const SubPat &SP)
cst_pred_ty< is_lowbit_mask > m_LowBitMask()
Match an integer or vector with only the low bit(s) set.
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
ap_match< APInt > m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
bool match(Val *V, const Pattern &P)
auto m_Value()
Match an arbitrary value and ignore it.
cst_pred_ty< is_negated_power2 > m_NegatedPower2()
Match a integer or vector negated power-of-2.
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".
This is an optimization pass for GlobalISel generic memory operations.
@ Offset
Definition DWP.cpp:577
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition STLExtras.h:1755
static bool replaceSignedInst(SCCPSolver &Solver, SmallPtrSetImpl< Value * > &InsertedValues, Instruction &Inst)
Try to replace signed instructions with their unsigned equivalent.
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:643
auto successors(const MachineBasicBlock *BB)
static ConstantRange getRange(Value *Op, SCCPSolver &Solver, const SmallPtrSetImpl< Value * > &InsertedValues)
Helper for getting ranges from Solver.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition STLExtras.h:649
LLVM_ABI Constant * ConstantFoldCall(const CallBase *Call, Function *F, ArrayRef< Constant * > Operands, const TargetLibraryInfo *TLI=nullptr, bool AllowNonDeterministic=true)
ConstantFoldCall - Attempt to constant fold a call to the specified function with the specified argum...
LLVM_ABI ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
LLVM_ABI bool canConstantFoldCallTo(const CallBase *Call, const Function *F, const TargetLibraryInfo *TLI=nullptr)
canConstantFoldCallTo - Return true if its even possible to fold a call to the specified function.
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Value
Definition InstrProf.h:143
LLVM_ABI Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
auto dyn_cast_or_null(const Y &Val)
Definition Casting.h:753
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition STLExtras.h:1762
LLVM_ABI bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction will return.
Definition Local.cpp:408
NoopStatistic Statistic
Definition Statistic.h:162
LLVM_ABI Constant * ConstantFoldUnaryOpOperand(unsigned Opcode, Constant *Op, const DataLayout &DL)
Attempt to constant fold a unary operation with the specified operand.
LLVM_ABI bool canReplacePointersInUseIfEqual(const Use &U, const Value *To, const DataLayout &DL)
Definition Loads.cpp:926
LLVM_ABI bool NullPointerIsDefined(const Function *F, unsigned AS=0)
Check whether null pointer dereferencing is considered undefined behavior for a given function or an ...
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:209
LLVM_ABI bool wouldInstructionBeTriviallyDead(const Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction would have no side effects if it was not used.
Definition Local.cpp:415
LLVM_ABI ConstantRange getVScaleRange(const Function *F, unsigned BitWidth)
Determine the possible constant range of vscale with the given bit width, based on the vscale_range f...
static void propagateImplicitRefFromCall(CallBase *CB)
Helper for propagting !implicit.ref metadata from callee to caller before erasing a call instruction.
LLVM_ABI Constant * ConstantFoldCastOperand(unsigned Opcode, Constant *C, Type *DestTy, const DataLayout &DL)
Attempt to constant fold a cast with the specified operand.
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
Definition Casting.h:547
LLVM_ABI Value * simplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a BinaryOperator, fold the result or return null.
@ Sub
Subtraction of integers.
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Count
Definition InstrProf.h:145
DWARFExpression::Operation Op
LLVM_ABI bool isGuaranteedNotToBeUndefOrPoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Return true if this function can prove that V does not have undef bits and is never poison.
constexpr unsigned BitWidth
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition STLExtras.h:1933
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:559
LLVM_ABI Constant * ConstantFoldLoadFromConstPtr(Constant *C, Type *Ty, APInt Offset, const DataLayout &DL)
Return the value that a load from C with offset Offset would produce if it is constant and determinab...
BumpPtrAllocatorImpl<> BumpPtrAllocator
The standard BumpPtrAllocator which just uses the default template parameters.
Definition Allocator.h:391
LLVM_ABI Constant * ConstantFoldInstOperands(const Instruction *I, ArrayRef< Constant * > Ops, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, bool AllowNonDeterministic=true)
ConstantFoldInstOperands - Attempt to constant fold an instruction with the specified operands.
@ End
Run the machine verifier once, at the end of the pipeline.
Definition CodeGen.h:320
static bool refineInstruction(SCCPSolver &Solver, const SmallPtrSetImpl< Value * > &InsertedValues, Instruction &Inst)
Try to use Inst's value range from Solver to infer the NUW flag.
static void inferAttribute(Function *F, unsigned AttrIndex, const ValueLatticeElement &Val)
Implement std::hash so that hash_code can be used in STL containers.
Definition BitVector.h:879
Struct to control some aspects related to merging constant ranges.
MergeOptions & setMaxWidenSteps(unsigned Steps=1)