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
15#include "llvm/Transforms/Utils/SCCPSolver.h"
16#include "llvm/ADT/SetVector.h"
17#include "llvm/Analysis/ConstantFolding.h"
18#include "llvm/Analysis/InstructionSimplify.h"
19#include "llvm/Analysis/Loads.h"
20#include "llvm/Analysis/ValueLattice.h"
21#include "llvm/Analysis/ValueLatticeUtils.h"
22#include "llvm/Analysis/ValueTracking.h"
23#include "llvm/IR/ConstantRange.h"
24#include "llvm/IR/DerivedTypes.h"
25#include "llvm/IR/IRBuilder.h"
26#include "llvm/IR/InstVisitor.h"
27#include "llvm/IR/Instructions.h"
28#include "llvm/IR/NoFolder.h"
29#include "llvm/IR/Operator.h"
30#include "llvm/IR/PatternMatch.h"
31#include "llvm/Support/Casting.h"
32#include "llvm/Support/Debug.h"
33#include "llvm/Support/ErrorHandling.h"
34#include "llvm/Support/raw_ostream.h"
35#include "llvm/Transforms/Utils/Local.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.
50static ValueLatticeElement::MergeOptions getMaxWidenStepsOpts() {
51 return ValueLatticeElement::MergeOptions().setMaxWidenSteps(
52 MaxNumRangeExtensions);
53}
54
55namespace llvm {
56
57bool SCCPSolver::isConstant(const ValueLatticeElement &LV) {
58 return LV.isConstant() ||
59 (LV.isConstantRange() && LV.getConstantRange().isSingleElement());
60}
61
62bool SCCPSolver::isReplaceableConstant(const ValueLatticeElement &LV) {
63 return isConstant(LV) && !LV.mayHaveDifferentProvenance();
64}
65
66bool SCCPSolver::isOverdefined(const ValueLatticeElement &LV) {
67 return !LV.isUnknownOrUndef() && !SCCPSolver::isConstant(LV);
68}
69
70bool SCCPSolver::tryToReplaceWithConstant(Value *V) {
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.
78 CallBase *CB = dyn_cast<CallBase>(Val: V);
79 if (CB && ((CB->isMustTailCall() && !wouldInstructionBeTriviallyDead(I: CB)) ||
80 CB->getOperandBundle(ID: LLVMContext::OB_clang_arc_attachedcall))) {
81 Function *F = CB->getCalledFunction();
82
83 // Don't zap returns of the callee
84 if (F)
85 addToMustPreserveReturnsInFunctions(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(New: Const, ShouldReplace: [&](Use &U) {
100 bool CanReplace = canReplacePointersInUseIfEqual(U, To: 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(V: 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.
120static void propagateImplicitRefFromCall(CallBase *CB) {
121 Function *Callee = CB->getCalledFunction();
122 if (!Callee)
123 return;
124
125 if (!Callee->hasMetadata(KindID: LLVMContext::MD_implicit_ref))
126 return;
127
128 Function *Caller = CB->getParent()->getParent();
129 if (!Caller)
130 return;
131
132 SmallVector<MDNode *> MDs;
133 Callee->getMetadata(KindID: LLVMContext::MD_implicit_ref, MDs);
134 for (MDNode *MD : MDs)
135 Caller->addMetadata(KindID: LLVMContext::MD_implicit_ref, MD&: *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.
141static ConstantRange getRange(Value *Op, SCCPSolver &Solver,
142 const SmallPtrSetImpl<Value *> &InsertedValues) {
143 if (auto *Const = dyn_cast<Constant>(Val: Op))
144 return Const->toConstantRange();
145 if (InsertedValues.contains(Ptr: Op)) {
146 unsigned Bitwidth = Op->getType()->getScalarSizeInBits();
147 return ConstantRange::getFull(BitWidth: Bitwidth);
148 }
149 return Solver.getLatticeValueFor(V: Op).asConstantRange(Ty: 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
162 if (isa<OverflowingBinaryOperator>(Val: Inst)) {
163 if (Inst.hasNoSignedWrap() && Inst.hasNoUnsignedWrap())
164 return false;
165
166 auto RangeA = GetRange(Inst.getOperand(i: 0));
167 auto RangeB = GetRange(Inst.getOperand(i: 1));
168 if (!Inst.hasNoUnsignedWrap()) {
169 auto NUWRange = ConstantRange::makeGuaranteedNoWrapRegion(
170 BinOp: Instruction::BinaryOps(Inst.getOpcode()), Other: RangeB,
171 NoWrapKind: OverflowingBinaryOperator::NoUnsignedWrap);
172 if (NUWRange.contains(CR: RangeA)) {
173 Inst.setHasNoUnsignedWrap();
174 Changed = true;
175 }
176 }
177 if (!Inst.hasNoSignedWrap()) {
178 auto NSWRange = ConstantRange::makeGuaranteedNoWrapRegion(
179 BinOp: Instruction::BinaryOps(Inst.getOpcode()), Other: RangeB,
180 NoWrapKind: OverflowingBinaryOperator::NoSignedWrap);
181 if (NSWRange.contains(CR: RangeA)) {
182 Inst.setHasNoSignedWrap();
183 Changed = true;
184 }
185 }
186 } else if (isa<PossiblyNonNegInst>(Val: Inst) && !Inst.hasNonNeg()) {
187 auto Range = GetRange(Inst.getOperand(i: 0));
188 if (Range.isAllNonNegative()) {
189 Inst.setNonNeg();
190 Changed = true;
191 }
192 } else if (TruncInst *TI = dyn_cast<TruncInst>(Val: &Inst)) {
193 if (TI->hasNoSignedWrap() && TI->hasNoUnsignedWrap())
194 return false;
195
196 auto Range = GetRange(Inst.getOperand(i: 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>(Val: &Inst)) {
211 if (GEP->hasNoUnsignedWrap() || !GEP->hasNoUnsignedSignedWrap())
212 return false;
213
214 if (all_of(Range: GEP->indices(),
215 P: [&](Value *V) { return GetRange(V).isAllNonNegative(); })) {
216 GEP->setNoWrapFlags(GEP->getNoWrapFlags() |
217 GEPNoWrapFlags::noUnsignedWrap());
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(Op: 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(i: 0);
240 if (!isNonNegative(Op0))
241 return false;
242 NewInst = CastInst::Create(Inst.getOpcode() == Instruction::SExt
243 ? Instruction::ZExt
244 : Instruction::UIToFP,
245 S: Op0, Ty: Inst.getType(), Name: "", InsertBefore: 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(i: 0);
252 if (!isNonNegative(Op0))
253 return false;
254 NewInst = BinaryOperator::CreateLShr(V1: Op0, V2: Inst.getOperand(i: 1), Name: "", InsertBefore: 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(i: 0), *Op1 = Inst.getOperand(i: 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(Op: NewOpcode, S1: Op0, S2: Op1, Name: "", InsertBefore: 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(V: &Inst);
278 InsertedValues.insert(Ptr: NewInst);
279 Inst.replaceAllUsesWith(V: NewInst);
280 NewInst->setDebugLoc(Inst.getDebugLoc());
281 Solver.removeLatticeValueFor(V: &Inst);
282 Inst.eraseFromParent();
283 return true;
284}
285
286/// Try to use \p Inst's value range from \p Solver to simplify it.
287static Value *simplifyInstruction(SCCPSolver &Solver,
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(V: &Inst, P: m_And(L: m_Value(V&: X), R: m_LowBitMask(V&: RHSC)))) {
298 ConstantRange LRange = GetRange(X);
299 if (LRange.getUnsignedMax().ule(RHS: *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>(Val: &Inst)) {
305 Value *LHS = Cmp->getOperand(i_nocapture: 0);
306 Value *RHS = Cmp->getOperand(i_nocapture: 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(MaxSize: 3))
313 return nullptr;
314 ConstantRange RRange = GetRange(RHS);
315 if (RRange.isSizeLargerThan(MaxSize: 3))
316 return nullptr;
317 ConstantRange RHSLower = RRange.sub(Other: APInt(BitWidth, 1));
318 ConstantRange RHSUpper = RRange.add(Other: APInt(BitWidth, 1));
319 ICmpInst::Predicate Pred =
320 Cmp->isSigned() ? CmpInst::ICMP_SLE : CmpInst::ICMP_ULE;
321 if (!RHSLower.icmp(Pred, Other: LRange) || !LRange.icmp(Pred, Other: RHSUpper))
322 return nullptr;
323
324 IRBuilder<NoFolder> Builder(&Inst);
325 Value *Sub = Builder.CreateSub(LHS, RHS, Name: Inst.getName(), /*HasNUW=*/false,
326 /*HasNSW=*/Cmp->isSigned());
327 InsertedValues.insert(Ptr: Sub);
328 if (Sub->getType() != Inst.getType()) {
329 Sub = Builder.CreateSExtOrTrunc(V: Sub, DestTy: Inst.getType());
330 InsertedValues.insert(Ptr: Sub);
331 }
332 return Sub;
333 }
334
335 // Relax range checks.
336 if (auto *ICmp = dyn_cast<ICmpInst>(Val: &Inst)) {
337 Value *X;
338 auto MatchTwoInstructionExactRangeCheck =
339 [&]() -> std::optional<ConstantRange> {
340 const APInt *RHSC;
341 if (!match(V: ICmp->getOperand(i_nocapture: 1), P: m_APInt(Res&: RHSC)))
342 return std::nullopt;
343
344 Value *LHS = ICmp->getOperand(i_nocapture: 0);
345 ICmpInst::Predicate Pred = ICmp->getPredicate();
346 const APInt *Offset;
347 if (match(V: LHS, P: m_OneUse(SubPattern: m_AddLike(L: m_Value(V&: X), R: m_APInt(Res&: Offset)))))
348 return ConstantRange::makeExactICmpRegion(Pred, Other: *RHSC).sub(Other: *Offset);
349 // Match icmp eq/ne X & NegPow2, C
350 if (ICmp->isEquality()) {
351 const APInt *Mask;
352 if (match(V: LHS, P: m_OneUse(SubPattern: m_And(L: m_Value(V&: X), R: m_NegatedPower2(V&: 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 * {
368 ICmpInst::Predicate Pred;
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(P: Pred, LHS: X, RHS: ConstantInt::get(Ty: X->getType(), V: RHS));
375 InsertedValues.insert(Ptr: 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(CR: 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(CR: LRange.inverse())))
388 return V;
389 }
390 }
391
392 return nullptr;
393}
394
395bool SCCPSolver::simplifyInstsInBlock(BasicBlock &BB,
396 SmallPtrSetImpl<Value *> &InsertedValues,
397 Statistic &InstRemovedStat,
398 Statistic &InstReplacedStat) {
399 bool MadeChanges = false;
400 for (Instruction &Inst : make_early_inc_range(Range&: BB)) {
401 if (Inst.getType()->isVoidTy())
402 continue;
403 if (tryToReplaceWithConstant(V: &Inst)) {
404 if (isInstructionTriviallyDead(I: &Inst)) {
405 // Propagate !implicit.ref before erasing the call.
406 if (auto *CB = dyn_cast<CallBase>(Val: &Inst))
407 propagateImplicitRefFromCall(CB);
408
409 Inst.eraseFromParent();
410 ++InstRemovedStat;
411 }
412 MadeChanges = true;
413 } else if (replaceSignedInst(Solver&: *this, InsertedValues, Inst)) {
414 MadeChanges = true;
415 ++InstReplacedStat;
416 } else if (refineInstruction(Solver&: *this, InsertedValues, Inst)) {
417 MadeChanges = true;
418 } else if (auto *V = simplifyInstruction(Solver&: *this, InsertedValues, Inst)) {
419 Inst.replaceAllUsesWith(V);
420 Inst.eraseFromParent();
421 ++InstRemovedStat;
422 MadeChanges = true;
423 }
424 }
425 return MadeChanges;
426}
427
428bool SCCPSolver::removeNonFeasibleEdges(BasicBlock *BB, DomTreeUpdater &DTU,
429 BasicBlock *&NewUnreachableBB) const {
430 SmallPtrSet<BasicBlock *, 8> FeasibleSuccessors;
431 bool HasNonFeasibleEdges = false;
432 for (BasicBlock *Succ : successors(BB)) {
433 if (isEdgeFeasible(From: BB, To: Succ))
434 FeasibleSuccessors.insert(Ptr: 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();
445 assert((isa<UncondBrInst, CondBrInst, SwitchInst, IndirectBrInst>(TI)) &&
446 "Terminator must be a br, switch or indirectbr");
447
448 if (FeasibleSuccessors.size() == 0) {
449 // Branch on undef/poison, replace with unreachable.
450 SmallPtrSet<BasicBlock *, 8> SeenSuccs;
451 SmallVector<DominatorTree::UpdateType, 8> Updates;
452 for (BasicBlock *Succ : successors(BB)) {
453 Succ->removePredecessor(Pred: BB);
454 if (SeenSuccs.insert(Ptr: Succ).second)
455 Updates.push_back(Elt: {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();
463 SmallVector<DominatorTree::UpdateType, 8> Updates;
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(Pred: BB);
474 Updates.push_back(Elt: {DominatorTree::Delete, BB, Succ});
475 }
476
477 Instruction *BI = UncondBrInst::Create(Target: OnlyFeasibleSuccessor, InsertBefore: BB);
478 BI->setDebugLoc(TI->getDebugLoc());
479 TI->eraseFromParent();
480 DTU.applyUpdatesPermissive(Updates);
481 } else if (FeasibleSuccessors.size() > 1) {
482 SwitchInstProfUpdateWrapper SI(*cast<SwitchInst>(Val: TI));
483 SmallVector<DominatorTree::UpdateType, 8> Updates;
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(Ptr: DefaultDest)) {
489 if (!NewUnreachableBB) {
490 NewUnreachableBB =
491 BasicBlock::Create(Context&: DefaultDest->getContext(), Name: "default.unreachable",
492 Parent: DefaultDest->getParent(), InsertBefore: DefaultDest);
493 auto *UI =
494 new UnreachableInst(DefaultDest->getContext(), NewUnreachableBB);
495 UI->setDebugLoc(DebugLoc::getTemporary());
496 }
497
498 DefaultDest->removePredecessor(Pred: BB);
499 SI->setDefaultDest(NewUnreachableBB);
500 Updates.push_back(Elt: {DominatorTree::Delete, BB, DefaultDest});
501 Updates.push_back(Elt: {DominatorTree::Insert, BB, NewUnreachableBB});
502 }
503
504 for (auto CI = SI->case_begin(); CI != SI->case_end();) {
505 if (FeasibleSuccessors.contains(Ptr: CI->getCaseSuccessor())) {
506 ++CI;
507 continue;
508 }
509
510 BasicBlock *Succ = CI->getCaseSuccessor();
511 Succ->removePredecessor(Pred: BB);
512 Updates.push_back(Elt: {DominatorTree::Delete, BB, Succ});
513 SI.removeCase(I: 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.
529 if (Val.isConstantRangeIncludingUndef())
530 return;
531
532 // Take the intersection of the existing attribute and the inferred range.
533 Attribute OldAttr = F->getAttributeAtIndex(i: AttrIndex, Kind: Attribute::Range);
534 ConstantRange CR = Val.getConstantRange();
535 if (OldAttr.isValid())
536 CR = CR.intersectWith(CR: OldAttr.getRange());
537 F->addAttributeAtIndex(
538 i: AttrIndex, Attr: Attribute::get(Context&: F->getContext(), Kind: 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(Idx: AttrIndex, Kind: Attribute::NonNull)) {
545 F->addAttributeAtIndex(i: AttrIndex,
546 Attr: Attribute::get(Context&: F->getContext(), Kind: Attribute::NonNull));
547 }
548}
549
550void SCCPSolver::inferReturnAttributes() const {
551 for (const auto &[F, ReturnValue] : getTrackedRetVals())
552 inferAttribute(F, AttrIndex: AttributeList::ReturnIndex, Val: ReturnValue);
553}
554
555void SCCPSolver::inferArgAttributes() const {
556 for (Function *F : getArgumentTrackedFunctions()) {
557 if (!isBlockExecutable(BB: &F->front()))
558 continue;
559 for (Argument &A : F->args())
560 if (!A.getType()->isStructTy())
561 inferAttribute(F, AttrIndex: AttributeList::FirstArgIndex + A.getArgNo(),
562 Val: getLatticeValueFor(V: &A));
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.
574 SmallPtrSet<BasicBlock *, 8> BBVisited;
575 DenseMap<Value *, ValueLatticeElement>
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.
580 DenseMap<std::pair<Value *, unsigned>, ValueLatticeElement> StructValueState;
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.
586 DenseMap<GlobalVariable *, ValueLatticeElement> TrackedGlobals;
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.
591 MapVector<Function *, ValueLatticeElement> TrackedRetVals;
592
593 /// TrackedMultipleRetVals - Same as TrackedRetVals, but used for functions
594 /// that return multiple values.
595 MapVector<std::pair<Function *, unsigned>, ValueLatticeElement>
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.
616 SmallSetVector<Instruction *, 16> InstWorkList;
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
624 SmallVector<BasicBlock *, 64> BBWorkList;
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
631 DenseMap<Function *, std::unique_ptr<PredicateInfo>> FnPredicateInfo;
632
633 DenseMap<Value *, SmallSetVector<User *, 2>> AdditionalUsers;
634
635 LLVMContext &Ctx;
636
637 BumpPtrAllocator PredicateInfoAllocator;
638
639private:
640 ConstantInt *getConstantInt(const ValueLatticeElement &IV, Type *Ty) const {
641 return dyn_cast_or_null<ConstantInt>(Val: getConstant(LV: IV, Ty));
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(IV&: 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, C: Constant::getNullValue(Ty: 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,
687 ValueLatticeElement::MergeOptions Opts = {
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(Key: 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>(Val: V))
703 LV.markConstant(V: 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 KV: std::make_pair(x: std::make_pair(x&: V, y&: i), y: 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>(Val: V)) {
725 Constant *Elt = C->getAggregateElement(Elt: i);
726
727 if (!Elt)
728 LV.markOverdefined(); // Unknown sort of constant.
729 else
730 LV.markConstant(V: 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>(Val: V->getType())) {
739 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
740 Fn([this, i](Value *Op) -> ValueLatticeElement & {
741 return getStructValueState(V: Op, i);
742 });
743 } else {
744 Fn([this](Value *Op) -> ValueLatticeElement & {
745 return getValueState(V: 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) {
753 SmallVector<Instruction *, 64> ToInvalidate;
754 ToInvalidate.push_back(Elt: Call);
755
756 while (!ToInvalidate.empty()) {
757 Instruction *Inst = ToInvalidate.pop_back_val();
758
759 if (!Invalidated.insert(V: Inst).second)
760 continue;
761
762 if (!BBExecutable.count(Ptr: 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>(Val: Inst)) {
769 Function *F = RetInst->getParent()->getParent();
770 if (auto It = TrackedRetVals.find(Key: F); It != TrackedRetVals.end()) {
771 It->second = ValueLatticeElement();
772 V = F;
773 } else if (MRVFunctionsTracked.count(Ptr: F)) {
774 auto *STy = cast<StructType>(Val: F->getReturnType());
775 for (unsigned I = 0, E = STy->getNumElements(); I != E; ++I)
776 TrackedMultipleRetVals[{F, I}] = ValueLatticeElement();
777 V = F;
778 }
779 } else if (auto *STy = dyn_cast<StructType>(Val: Inst->getType())) {
780 for (unsigned I = 0, E = STy->getNumElements(); I != E; ++I) {
781 if (auto It = StructValueState.find(Val: {Inst, I});
782 It != StructValueState.end()) {
783 It->second = ValueLatticeElement();
784 V = Inst;
785 }
786 }
787 } else if (auto It = ValueState.find(Val: Inst); It != ValueState.end()) {
788 It->second = ValueLatticeElement();
789 V = Inst;
790 }
791
792 if (V) {
793 LLVM_DEBUG(dbgs() << "Invalidated lattice for " << *V << "\n");
794
795 for (User *U : V->users())
796 if (auto *UI = dyn_cast<Instruction>(Val: U))
797 ToInvalidate.push_back(Elt: UI);
798
799 auto It = AdditionalUsers.find(Val: V);
800 if (It != AdditionalUsers.end())
801 for (User *U : It->second)
802 if (auto *UI = dyn_cast<Instruction>(Val: U))
803 ToInvalidate.push_back(Elt: UI);
804 }
805 }
806 }
807
808 /// markEdgeExecutable - Mark a basic block as executable, adding it to the BB
809 /// work list if it is not already executable.
810 bool markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest);
811
812 // getFeasibleSuccessors - Return a vector of booleans to indicate which
813 // successors are reachable from a given terminator instruction.
814 void getFeasibleSuccessors(Instruction &TI, SmallVectorImpl<bool> &Succs);
815
816 // Add U as additional user of V.
817 void addAdditionalUser(Value *V, User *U) { AdditionalUsers[V].insert(X: U); }
818
819 void handlePredicate(Instruction *I, Value *CopyOf, const PredicateBase *PI);
820 void handleCallOverdefined(CallBase &CB);
821 void handleCallResult(CallBase &CB);
822 void handleCallArguments(CallBase &CB);
823 void handleExtractOfWithOverflow(ExtractValueInst &EVI,
824 const WithOverflowInst *WO, unsigned Idx);
825 bool isInstFullyOverDefined(Instruction &Inst);
826
827private:
828 friend class InstVisitor<SCCPInstVisitor>;
829
830 // visit implementations - Something changed in this instruction. Either an
831 // operand made a transition, or the instruction is newly executable. Change
832 // the value type of I to reflect these changes if appropriate.
833 void visitPHINode(PHINode &I);
834
835 // Terminators
836
837 void visitReturnInst(ReturnInst &I);
838 void visitTerminator(Instruction &TI);
839
840 void visitCastInst(CastInst &I);
841 void visitSelectInst(SelectInst &I);
842 void visitUnaryOperator(Instruction &I);
843 void visitFreezeInst(FreezeInst &I);
844 void visitBinaryOperator(Instruction &I);
845 void visitCmpInst(CmpInst &I);
846 void visitExtractValueInst(ExtractValueInst &EVI);
847 void visitInsertValueInst(InsertValueInst &IVI);
848
849 void visitCatchSwitchInst(CatchSwitchInst &CPI) {
850 markOverdefined(V: &CPI);
851 visitTerminator(TI&: CPI);
852 }
853
854 // Instructions that cannot be folded away.
855
856 void visitStoreInst(StoreInst &I);
857 void visitLoadInst(LoadInst &I);
858 void visitGetElementPtrInst(GetElementPtrInst &I);
859 void visitAllocaInst(AllocaInst &AI);
860
861 void visitInvokeInst(InvokeInst &II) {
862 visitCallBase(CB&: II);
863 visitTerminator(TI&: II);
864 }
865
866 void visitCallBrInst(CallBrInst &CBI) {
867 visitCallBase(CB&: CBI);
868 visitTerminator(TI&: CBI);
869 }
870
871 void visitCallBase(CallBase &CB);
872 void visitResumeInst(ResumeInst &I) { /*returns void*/
873 }
874 void visitUnreachableInst(UnreachableInst &I) { /*returns void*/
875 }
876 void visitFenceInst(FenceInst &I) { /*returns void*/
877 }
878
879 void visitInstruction(Instruction &I);
880
881public:
882 const DataLayout &getDataLayout() const { return DL; }
883
884 void addPredicateInfo(Function &F, DominatorTree &DT, AssumptionCache &AC) {
885 FnPredicateInfo.insert(KV: {&F, std::make_unique<PredicateInfo>(
886 args&: F, args&: DT, args&: AC, args&: PredicateInfoAllocator)});
887 }
888
889 void removeSSACopies(Function &F) {
890 auto It = FnPredicateInfo.find(Val: &F);
891 if (It == FnPredicateInfo.end())
892 return;
893
894 for (BasicBlock &BB : F) {
895 for (Instruction &Inst : llvm::make_early_inc_range(Range&: BB)) {
896 if (auto *BC = dyn_cast<BitCastInst>(Val: &Inst)) {
897 if (BC->getType() == BC->getOperand(i_nocapture: 0)->getType()) {
898 if (It->second->getPredicateInfoFor(V: &Inst)) {
899 Value *Op = BC->getOperand(i_nocapture: 0);
900 Inst.replaceAllUsesWith(V: Op);
901 Inst.eraseFromParent();
902 }
903 }
904 }
905 }
906 }
907 }
908
909 void visitCallInst(CallInst &I) { visitCallBase(CB&: I); }
910
911 bool markBlockExecutable(BasicBlock *BB);
912
913 const PredicateBase *getPredicateInfoFor(Instruction *I) {
914 auto It = FnPredicateInfo.find(Val: I->getParent()->getParent());
915 if (It == FnPredicateInfo.end())
916 return nullptr;
917 return It->second->getPredicateInfoFor(V: I);
918 }
919
920 SCCPInstVisitor(const DataLayout &DL,
921 std::function<const TargetLibraryInfo &(Function &)> GetTLI,
922 LLVMContext &Ctx)
923 : DL(DL), GetTLI(GetTLI), Ctx(Ctx) {}
924
925 void trackValueOfGlobalVariable(GlobalVariable *GV) {
926 // We only track the contents of scalar globals.
927 if (GV->getValueType()->isSingleValueType()) {
928 ValueLatticeElement &IV = TrackedGlobals[GV];
929 IV.markConstant(V: GV->getInitializer());
930 }
931 }
932
933 void addTrackedFunction(Function *F) {
934 // Add an entry, F -> undef.
935 if (auto *STy = dyn_cast<StructType>(Val: F->getReturnType())) {
936 MRVFunctionsTracked.insert(Ptr: F);
937 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
938 TrackedMultipleRetVals.try_emplace(Key: std::make_pair(x&: F, y&: i));
939 } else if (!F->getReturnType()->isVoidTy())
940 TrackedRetVals.try_emplace(Key: F);
941 }
942
943 void addToMustPreserveReturnsInFunctions(Function *F) {
944 MustPreserveReturnsInFunctions.insert(Ptr: F);
945 }
946
947 bool mustPreserveReturn(Function *F) {
948 return MustPreserveReturnsInFunctions.count(Ptr: F);
949 }
950
951 void addArgumentTrackedFunction(Function *F) {
952 TrackingIncomingArguments.insert(Ptr: F);
953 }
954
955 bool isArgumentTrackedFunction(Function *F) {
956 return TrackingIncomingArguments.count(Ptr: F);
957 }
958
959 const SmallPtrSetImpl<Function *> &getArgumentTrackedFunctions() const {
960 return TrackingIncomingArguments;
961 }
962
963 void solve();
964
965 bool resolvedUndef(Instruction &I);
966
967 bool resolvedUndefsIn(Function &F);
968
969 bool isBlockExecutable(BasicBlock *BB) const {
970 return BBExecutable.count(Ptr: BB);
971 }
972
973 bool isEdgeFeasible(BasicBlock *From, BasicBlock *To) const;
974
975 std::vector<ValueLatticeElement> getStructLatticeValueFor(Value *V) const {
976 std::vector<ValueLatticeElement> StructValues;
977 auto *STy = dyn_cast<StructType>(Val: V->getType());
978 assert(STy && "getStructLatticeValueFor() can be called only on structs");
979 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
980 auto I = StructValueState.find(Val: std::make_pair(x&: V, y&: i));
981 assert(I != StructValueState.end() && "Value not in valuemap!");
982 StructValues.push_back(x: I->second);
983 }
984 return StructValues;
985 }
986
987 void removeLatticeValueFor(Value *V) { ValueState.erase(Val: V); }
988
989 /// Invalidate the Lattice Value of \p Call and its users after specializing
990 /// the call. Then recompute it.
991 void resetLatticeValueFor(CallBase *Call) {
992 // Calls to void returning functions do not need invalidation.
993 Function *F = Call->getCalledFunction();
994 (void)F;
995 assert(!F->getReturnType()->isVoidTy() &&
996 (TrackedRetVals.count(F) || MRVFunctionsTracked.count(F)) &&
997 "All non void specializations should be tracked");
998 invalidate(Call);
999 handleCallResult(CB&: *Call);
1000 }
1001
1002 const ValueLatticeElement &getLatticeValueFor(Value *V) const {
1003 assert(!V->getType()->isStructTy() &&
1004 "Should use getStructLatticeValueFor");
1005 auto I = ValueState.find(Val: V);
1006 assert(I != ValueState.end() &&
1007 "V not found in ValueState nor Paramstate map!");
1008 return I->second;
1009 }
1010
1011 const MapVector<Function *, ValueLatticeElement> &getTrackedRetVals() const {
1012 return TrackedRetVals;
1013 }
1014
1015 const DenseMap<GlobalVariable *, ValueLatticeElement> &
1016 getTrackedGlobals() const {
1017 return TrackedGlobals;
1018 }
1019
1020 const SmallPtrSet<Function *, 16> &getMRVFunctionsTracked() const {
1021 return MRVFunctionsTracked;
1022 }
1023
1024 void markOverdefined(Value *V) {
1025 if (auto *STy = dyn_cast<StructType>(Val: V->getType()))
1026 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
1027 markOverdefined(IV&: getStructValueState(V, i), V);
1028 else
1029 markOverdefined(IV&: ValueState[V], V);
1030 }
1031
1032 ValueLatticeElement getArgAttributeVL(Argument *A) {
1033 if (A->getType()->isIntOrIntVectorTy()) {
1034 if (std::optional<ConstantRange> Range = A->getRange())
1035 return ValueLatticeElement::getRange(CR: *Range);
1036 }
1037 if (A->hasNonNullAttr())
1038 return ValueLatticeElement::getNot(C: Constant::getNullValue(Ty: A->getType()));
1039 // Assume nothing about the incoming arguments without attributes.
1040 return ValueLatticeElement::getOverdefined();
1041 }
1042
1043 void trackValueOfArgument(Argument *A) {
1044 if (A->getType()->isStructTy())
1045 return (void)markOverdefined(V: A);
1046 mergeInValue(IV&: ValueState[A], V: A, MergeWithV: getArgAttributeVL(A));
1047 }
1048
1049 bool isStructLatticeConstant(Function *F, StructType *STy);
1050
1051 Constant *getConstant(const ValueLatticeElement &LV, Type *Ty) const;
1052
1053 Constant *getConstantOrNull(Value *V) const;
1054
1055 void setLatticeValueForSpecializationArguments(Function *F,
1056 const SmallVectorImpl<ArgInfo> &Args);
1057
1058 void markFunctionUnreachable(Function *F) {
1059 for (auto &BB : *F)
1060 BBExecutable.erase(Ptr: &BB);
1061 }
1062
1063 void solveWhileResolvedUndefsIn(Module &M) {
1064 bool ResolvedUndefs = true;
1065 while (ResolvedUndefs) {
1066 solve();
1067 ResolvedUndefs = false;
1068 for (Function &F : M)
1069 ResolvedUndefs |= resolvedUndefsIn(F);
1070 }
1071 }
1072
1073 void solveWhileResolvedUndefsIn(SmallVectorImpl<Function *> &WorkList) {
1074 bool ResolvedUndefs = true;
1075 while (ResolvedUndefs) {
1076 solve();
1077 ResolvedUndefs = false;
1078 for (Function *F : WorkList)
1079 ResolvedUndefs |= resolvedUndefsIn(F&: *F);
1080 }
1081 }
1082
1083 void solveWhileResolvedUndefs() {
1084 bool ResolvedUndefs = true;
1085 while (ResolvedUndefs) {
1086 solve();
1087 ResolvedUndefs = false;
1088 for (Value *V : Invalidated)
1089 if (auto *I = dyn_cast<Instruction>(Val: V))
1090 ResolvedUndefs |= resolvedUndef(I&: *I);
1091 }
1092 Invalidated.clear();
1093 }
1094};
1095
1096} // namespace llvm
1097
1098bool SCCPInstVisitor::markBlockExecutable(BasicBlock *BB) {
1099 if (!BBExecutable.insert(Ptr: BB).second)
1100 return false;
1101 LLVM_DEBUG(dbgs() << "Marking Block Executable: " << BB->getName() << '\n');
1102 BBWorkList.push_back(Elt: BB); // Add the block to the work list!
1103 return true;
1104}
1105
1106void SCCPInstVisitor::pushToWorkList(Instruction *I) {
1107 // If we're currently visiting a block, do not push any instructions in the
1108 // same blocks that are after the current one, as they will be visited
1109 // anyway. We do have to push updates to earlier instructions (e.g. phi
1110 // nodes or loads of tracked globals).
1111 if (CurI && I->getParent() == CurI->getParent() && CurI->comesBefore(Other: I))
1112 return;
1113 // Only push instructions in already visited blocks. Otherwise we'll handle
1114 // it when we visit the block for the first time.
1115 if (BBVisited.contains(Ptr: I->getParent()))
1116 InstWorkList.insert(X: I);
1117}
1118
1119void SCCPInstVisitor::pushUsersToWorkList(Value *V) {
1120 for (User *U : V->users())
1121 if (auto *UI = dyn_cast<Instruction>(Val: U))
1122 pushToWorkList(I: UI);
1123
1124 auto Iter = AdditionalUsers.find(Val: V);
1125 if (Iter != AdditionalUsers.end()) {
1126 // Copy additional users before notifying them of changes, because new
1127 // users may be added, potentially invalidating the iterator.
1128 SmallVector<Instruction *, 2> ToNotify;
1129 for (User *U : Iter->second)
1130 if (auto *UI = dyn_cast<Instruction>(Val: U))
1131 ToNotify.push_back(Elt: UI);
1132 for (Instruction *UI : ToNotify)
1133 pushToWorkList(I: UI);
1134 }
1135}
1136
1137void SCCPInstVisitor::pushUsersToWorkListMsg(ValueLatticeElement &IV,
1138 Value *V) {
1139 LLVM_DEBUG(dbgs() << "updated " << IV << ": " << *V << '\n');
1140 pushUsersToWorkList(V);
1141}
1142
1143bool SCCPInstVisitor::markConstant(ValueLatticeElement &IV, Value *V,
1144 Constant *C, bool MayIncludeUndef) {
1145 if (!IV.markConstant(V: C, MayIncludeUndef))
1146 return false;
1147 LLVM_DEBUG(dbgs() << "markConstant: " << *C << ": " << *V << '\n');
1148 pushUsersToWorkList(V);
1149 return true;
1150}
1151
1152bool SCCPInstVisitor::markNotConstant(ValueLatticeElement &IV, Value *V,
1153 Constant *C) {
1154 if (!IV.markNotConstant(V: C))
1155 return false;
1156 LLVM_DEBUG(dbgs() << "markNotConstant: " << *C << ": " << *V << '\n');
1157 pushUsersToWorkList(V);
1158 return true;
1159}
1160
1161bool SCCPInstVisitor::markConstantRange(ValueLatticeElement &IV, Value *V,
1162 const ConstantRange &CR) {
1163 if (!IV.markConstantRange(NewR: CR))
1164 return false;
1165 LLVM_DEBUG(dbgs() << "markConstantRange: " << CR << ": " << *V << '\n');
1166 pushUsersToWorkList(V);
1167 return true;
1168}
1169
1170bool SCCPInstVisitor::markOverdefined(ValueLatticeElement &IV, Value *V) {
1171 if (!IV.markOverdefined())
1172 return false;
1173
1174 LLVM_DEBUG(dbgs() << "markOverdefined: ";
1175 if (auto *F = dyn_cast<Function>(V)) dbgs()
1176 << "Function '" << F->getName() << "'\n";
1177 else dbgs() << *V << '\n');
1178 // Only instructions go on the work list
1179 pushUsersToWorkList(V);
1180 return true;
1181}
1182
1183bool SCCPInstVisitor::isStructLatticeConstant(Function *F, StructType *STy) {
1184 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
1185 const auto &It = TrackedMultipleRetVals.find(Key: std::make_pair(x&: F, y&: i));
1186 assert(It != TrackedMultipleRetVals.end());
1187 if (!SCCPSolver::isReplaceableConstant(LV: It->second))
1188 return false;
1189 }
1190 return true;
1191}
1192
1193Constant *SCCPInstVisitor::getConstant(const ValueLatticeElement &LV,
1194 Type *Ty) const {
1195 if (LV.isConstant()) {
1196 Constant *C = LV.getConstant();
1197 assert(C->getType() == Ty && "Type mismatch");
1198 return C;
1199 }
1200
1201 if (LV.isConstantRange()) {
1202 const auto &CR = LV.getConstantRange();
1203 if (CR.getSingleElement())
1204 return ConstantInt::get(Ty, V: *CR.getSingleElement());
1205 }
1206 return nullptr;
1207}
1208
1209Constant *SCCPInstVisitor::getConstantOrNull(Value *V) const {
1210 Constant *Const = nullptr;
1211 if (V->getType()->isStructTy()) {
1212 std::vector<ValueLatticeElement> LVs = getStructLatticeValueFor(V);
1213 if (any_of(Range&: LVs, P: SCCPSolver::isOverdefined))
1214 return nullptr;
1215 std::vector<Constant *> ConstVals;
1216 auto *ST = cast<StructType>(Val: V->getType());
1217 for (unsigned I = 0, E = ST->getNumElements(); I != E; ++I) {
1218 const ValueLatticeElement &LV = LVs[I];
1219 ConstVals.push_back(x: SCCPSolver::isConstant(LV)
1220 ? getConstant(LV, Ty: ST->getElementType(N: I))
1221 : UndefValue::get(T: ST->getElementType(N: I)));
1222 }
1223 Const = ConstantStruct::get(T: ST, V: ConstVals);
1224 } else {
1225 const ValueLatticeElement &LV = getLatticeValueFor(V);
1226 if (SCCPSolver::isOverdefined(LV))
1227 return nullptr;
1228 Const = SCCPSolver::isConstant(LV) ? getConstant(LV, Ty: V->getType())
1229 : UndefValue::get(T: V->getType());
1230 }
1231 assert(Const && "Constant is nullptr here!");
1232 return Const;
1233}
1234
1235void SCCPInstVisitor::setLatticeValueForSpecializationArguments(Function *F,
1236 const SmallVectorImpl<ArgInfo> &Args) {
1237 assert(!Args.empty() && "Specialization without arguments");
1238 assert(F->arg_size() == Args[0].Formal->getParent()->arg_size() &&
1239 "Functions should have the same number of arguments");
1240
1241 auto Iter = Args.begin();
1242 Function::arg_iterator NewArg = F->arg_begin();
1243 Function::arg_iterator OldArg = Args[0].Formal->getParent()->arg_begin();
1244 for (auto End = F->arg_end(); NewArg != End; ++NewArg, ++OldArg) {
1245
1246 LLVM_DEBUG(dbgs() << "SCCP: Marking argument "
1247 << NewArg->getNameOrAsOperand() << "\n");
1248
1249 // Mark the argument constants in the new function
1250 // or copy the lattice state over from the old function.
1251 if (Iter != Args.end() && Iter->Formal == &*OldArg) {
1252 if (auto *STy = dyn_cast<StructType>(Val: NewArg->getType())) {
1253 for (unsigned I = 0, E = STy->getNumElements(); I != E; ++I) {
1254 ValueLatticeElement &NewValue = StructValueState[{&*NewArg, I}];
1255 NewValue.markConstant(V: Iter->Actual->getAggregateElement(Elt: I));
1256 }
1257 } else {
1258 ValueState[&*NewArg].markConstant(V: Iter->Actual);
1259 }
1260 ++Iter;
1261 } else {
1262 if (auto *STy = dyn_cast<StructType>(Val: NewArg->getType())) {
1263 for (unsigned I = 0, E = STy->getNumElements(); I != E; ++I) {
1264 ValueLatticeElement &NewValue = StructValueState[{&*NewArg, I}];
1265 NewValue = StructValueState[{&*OldArg, I}];
1266 }
1267 } else {
1268 ValueLatticeElement &NewValue = ValueState[&*NewArg];
1269 NewValue = ValueState[&*OldArg];
1270 }
1271 }
1272 }
1273}
1274
1275void SCCPInstVisitor::visitInstruction(Instruction &I) {
1276 // All the instructions we don't do any special handling for just
1277 // go to overdefined.
1278 LLVM_DEBUG(dbgs() << "SCCP: Don't know how to handle: " << I << '\n');
1279 markOverdefined(V: &I);
1280}
1281
1282bool SCCPInstVisitor::mergeInValue(ValueLatticeElement &IV, Value *V,
1283 const ValueLatticeElement &MergeWithV,
1284 ValueLatticeElement::MergeOptions Opts) {
1285 if (IV.mergeIn(RHS: MergeWithV, Opts)) {
1286 pushUsersToWorkList(V);
1287 LLVM_DEBUG(dbgs() << "Merged " << MergeWithV << " into " << *V << " : "
1288 << IV << "\n");
1289 return true;
1290 }
1291 return false;
1292}
1293
1294bool SCCPInstVisitor::markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest) {
1295 if (!KnownFeasibleEdges.insert(V: Edge(Source, Dest)).second)
1296 return false; // This edge is already known to be executable!
1297
1298 if (!markBlockExecutable(BB: Dest)) {
1299 // If the destination is already executable, we just made an *edge*
1300 // feasible that wasn't before. Revisit the PHI nodes in the block
1301 // because they have potentially new operands.
1302 LLVM_DEBUG(dbgs() << "Marking Edge Executable: " << Source->getName()
1303 << " -> " << Dest->getName() << '\n');
1304
1305 for (PHINode &PN : Dest->phis())
1306 pushToWorkList(I: &PN);
1307 }
1308 return true;
1309}
1310
1311// getFeasibleSuccessors - Return a vector of booleans to indicate which
1312// successors are reachable from a given terminator instruction.
1313void SCCPInstVisitor::getFeasibleSuccessors(Instruction &TI,
1314 SmallVectorImpl<bool> &Succs) {
1315 Succs.resize(N: TI.getNumSuccessors());
1316 if (isa<UncondBrInst>(Val: TI)) {
1317 Succs[0] = true;
1318 return;
1319 }
1320
1321 if (auto *BI = dyn_cast<CondBrInst>(Val: &TI)) {
1322 const ValueLatticeElement &BCValue = getValueState(V: BI->getCondition());
1323 ConstantInt *CI = getConstantInt(IV: BCValue, Ty: BI->getCondition()->getType());
1324 if (!CI) {
1325 // Overdefined condition variables, and branches on unfoldable constant
1326 // conditions, mean the branch could go either way.
1327 if (!BCValue.isUnknownOrUndef())
1328 Succs[0] = Succs[1] = true;
1329 return;
1330 }
1331
1332 // Constant condition variables mean the branch can only go a single way.
1333 Succs[CI->isZero()] = true;
1334 return;
1335 }
1336
1337 // We cannot analyze special terminators, so consider all successors
1338 // executable.
1339 if (TI.isSpecialTerminator()) {
1340 Succs.assign(NumElts: TI.getNumSuccessors(), Elt: true);
1341 return;
1342 }
1343
1344 if (auto *SI = dyn_cast<SwitchInst>(Val: &TI)) {
1345 if (!SI->getNumCases()) {
1346 Succs[0] = true;
1347 return;
1348 }
1349 const ValueLatticeElement &SCValue = getValueState(V: SI->getCondition());
1350 if (ConstantInt *CI =
1351 getConstantInt(IV: SCValue, Ty: SI->getCondition()->getType())) {
1352 Succs[SI->findCaseValue(C: CI)->getSuccessorIndex()] = true;
1353 return;
1354 }
1355
1356 // TODO: Switch on undef is UB. Stop passing false once the rest of LLVM
1357 // is ready.
1358 if (SCValue.isConstantRange(/*UndefAllowed=*/false)) {
1359 const ConstantRange &Range = SCValue.getConstantRange();
1360 unsigned ReachableCaseCount = 0;
1361 for (const auto &Case : SI->cases()) {
1362 const APInt &CaseValue = Case.getCaseValue()->getValue();
1363 if (Range.contains(Val: CaseValue)) {
1364 Succs[Case.getSuccessorIndex()] = true;
1365 ++ReachableCaseCount;
1366 }
1367 }
1368
1369 Succs[SI->case_default()->getSuccessorIndex()] =
1370 Range.isSizeLargerThan(MaxSize: ReachableCaseCount);
1371 return;
1372 }
1373
1374 // Overdefined or unknown condition? All destinations are executable!
1375 if (!SCValue.isUnknownOrUndef())
1376 Succs.assign(NumElts: TI.getNumSuccessors(), Elt: true);
1377 return;
1378 }
1379
1380 // In case of indirect branch and its address is a blockaddress, we mark
1381 // the target as executable.
1382 if (auto *IBR = dyn_cast<IndirectBrInst>(Val: &TI)) {
1383 // Casts are folded by visitCastInst.
1384 const ValueLatticeElement &IBRValue = getValueState(V: IBR->getAddress());
1385 BlockAddress *Addr = dyn_cast_or_null<BlockAddress>(
1386 Val: getConstant(LV: IBRValue, Ty: IBR->getAddress()->getType()));
1387 if (!Addr) { // Overdefined or unknown condition?
1388 // All destinations are executable!
1389 if (!IBRValue.isUnknownOrUndef())
1390 Succs.assign(NumElts: TI.getNumSuccessors(), Elt: true);
1391 return;
1392 }
1393
1394 BasicBlock *T = Addr->getBasicBlock();
1395 assert(Addr->getFunction() == T->getParent() &&
1396 "Block address of a different function ?");
1397 for (unsigned i = 0; i < IBR->getNumSuccessors(); ++i) {
1398 // This is the target.
1399 if (IBR->getDestination(i) == T) {
1400 Succs[i] = true;
1401 return;
1402 }
1403 }
1404
1405 // If we didn't find our destination in the IBR successor list, then we
1406 // have undefined behavior. Its ok to assume no successor is executable.
1407 return;
1408 }
1409
1410 LLVM_DEBUG(dbgs() << "Unknown terminator instruction: " << TI << '\n');
1411 llvm_unreachable("SCCP: Don't know how to handle this terminator!");
1412}
1413
1414// isEdgeFeasible - Return true if the control flow edge from the 'From' basic
1415// block to the 'To' basic block is currently feasible.
1416bool SCCPInstVisitor::isEdgeFeasible(BasicBlock *From, BasicBlock *To) const {
1417 // Check if we've called markEdgeExecutable on the edge yet. (We could
1418 // be more aggressive and try to consider edges which haven't been marked
1419 // yet, but there isn't any need.)
1420 return KnownFeasibleEdges.count(V: Edge(From, To));
1421}
1422
1423// visit Implementations - Something changed in this instruction, either an
1424// operand made a transition, or the instruction is newly executable. Change
1425// the value type of I to reflect these changes if appropriate. This method
1426// makes sure to do the following actions:
1427//
1428// 1. If a phi node merges two constants in, and has conflicting value coming
1429// from different branches, or if the PHI node merges in an overdefined
1430// value, then the PHI node becomes overdefined.
1431// 2. If a phi node merges only constants in, and they all agree on value, the
1432// PHI node becomes a constant value equal to that.
1433// 3. If V <- x (op) y && isConstant(x) && isConstant(y) V = Constant
1434// 4. If V <- x (op) y && (isOverdefined(x) || isOverdefined(y)) V = Overdefined
1435// 5. If V <- MEM or V <- CALL or V <- (unknown) then V = Overdefined
1436// 6. If a conditional branch has a value that is constant, make the selected
1437// destination executable
1438// 7. If a conditional branch has a value that is overdefined, make all
1439// successors executable.
1440void SCCPInstVisitor::visitPHINode(PHINode &PN) {
1441 // Super-extra-high-degree PHI nodes are unlikely to ever be marked constant,
1442 // and slow us down a lot. Just mark them overdefined.
1443 if (PN.getNumIncomingValues() > 64)
1444 return (void)markOverdefined(V: &PN);
1445
1446 if (isInstFullyOverDefined(Inst&: PN))
1447 return;
1448 SmallVector<unsigned> FeasibleIncomingIndices;
1449 for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
1450 if (!isEdgeFeasible(From: PN.getIncomingBlock(i), To: PN.getParent()))
1451 continue;
1452 FeasibleIncomingIndices.push_back(Elt: i);
1453 }
1454
1455 // Look at all of the executable operands of the PHI node. If any of them
1456 // are overdefined, the PHI becomes overdefined as well. If they are all
1457 // constant, and they agree with each other, the PHI becomes the identical
1458 // constant. If they are constant and don't agree, the PHI is a constant
1459 // range. If there are no executable operands, the PHI remains unknown.
1460 forEachLatticeElement(V: &PN, Fn: [&](auto GetValueState) {
1461 ValueLatticeElement PhiState = GetValueState(&PN);
1462 if (PhiState.isOverdefined())
1463 return;
1464 for (unsigned i : FeasibleIncomingIndices) {
1465 PhiState.mergeIn(RHS: GetValueState(PN.getIncomingValue(i)));
1466 if (PhiState.isOverdefined())
1467 break;
1468 }
1469 // We allow up to 1 range extension per active incoming value and one
1470 // additional extension. Note that we manually adjust the number of range
1471 // extensions to match the number of active incoming values. This helps to
1472 // limit multiple extensions caused by the same incoming value, if other
1473 // incoming values are equal.
1474 ValueLatticeElement &PhiStateRef = GetValueState(&PN);
1475 mergeInValue(IV&: PhiStateRef, V: &PN, MergeWithV: PhiState,
1476 Opts: ValueLatticeElement::MergeOptions().setMaxWidenSteps(
1477 FeasibleIncomingIndices.size() + 1));
1478 PhiStateRef.setNumRangeExtensions(
1479 std::max(a: (unsigned)FeasibleIncomingIndices.size(),
1480 b: PhiStateRef.getNumRangeExtensions()));
1481 });
1482}
1483
1484void SCCPInstVisitor::visitReturnInst(ReturnInst &I) {
1485 if (I.getNumOperands() == 0)
1486 return; // ret void
1487
1488 Function *F = I.getParent()->getParent();
1489 Value *ResultOp = I.getOperand(i_nocapture: 0);
1490
1491 // If we are tracking the return value of this function, merge it in.
1492 if (!TrackedRetVals.empty() && !ResultOp->getType()->isStructTy()) {
1493 auto TFRVI = TrackedRetVals.find(Key: F);
1494 if (TFRVI != TrackedRetVals.end()) {
1495 mergeInValue(IV&: TFRVI->second, V: F, MergeWithV: getValueState(V: ResultOp));
1496 return;
1497 }
1498 }
1499
1500 // Handle functions that return multiple values.
1501 if (!TrackedMultipleRetVals.empty()) {
1502 if (auto *STy = dyn_cast<StructType>(Val: ResultOp->getType()))
1503 if (MRVFunctionsTracked.count(Ptr: F))
1504 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
1505 mergeInValue(IV&: TrackedMultipleRetVals[std::make_pair(x&: F, y&: i)], V: F,
1506 MergeWithV: getStructValueState(V: ResultOp, i));
1507 }
1508}
1509
1510void SCCPInstVisitor::visitTerminator(Instruction &TI) {
1511 SmallVector<bool, 16> SuccFeasible;
1512 getFeasibleSuccessors(TI, Succs&: SuccFeasible);
1513
1514 BasicBlock *BB = TI.getParent();
1515
1516 // Mark all feasible successors executable.
1517 for (unsigned i = 0, e = SuccFeasible.size(); i != e; ++i)
1518 if (SuccFeasible[i])
1519 markEdgeExecutable(Source: BB, Dest: TI.getSuccessor(Idx: i));
1520}
1521
1522void SCCPInstVisitor::visitCastInst(CastInst &I) {
1523 // ResolvedUndefsIn might mark I as overdefined. Bail out, even if we would
1524 // discover a concrete value later.
1525 if (ValueState[&I].isOverdefined())
1526 return;
1527
1528 if (auto *BC = dyn_cast<BitCastInst>(Val: &I)) {
1529 if (BC->getType() == BC->getOperand(i_nocapture: 0)->getType()) {
1530 if (const PredicateBase *PI = getPredicateInfoFor(I: &I)) {
1531 handlePredicate(I: &I, CopyOf: I.getOperand(i_nocapture: 0), PI);
1532 return;
1533 }
1534 }
1535 }
1536
1537 const ValueLatticeElement &OpSt = getValueState(V: I.getOperand(i_nocapture: 0));
1538 if (OpSt.isUnknownOrUndef())
1539 return;
1540
1541 if (Constant *OpC = getConstant(LV: OpSt, Ty: I.getOperand(i_nocapture: 0)->getType())) {
1542 // Fold the constant as we build.
1543 if (Constant *C =
1544 ConstantFoldCastOperand(Opcode: I.getOpcode(), C: OpC, DestTy: I.getType(), DL)) {
1545 auto &LV = ValueState[&I];
1546 mergeInValue(IV&: LV, V: &I, MergeWithV: ValueLatticeElement::get(C));
1547 return;
1548 }
1549 }
1550
1551 // Ignore bitcasts, as they may change the number of vector elements.
1552 if (I.getDestTy()->isIntOrIntVectorTy() &&
1553 I.getSrcTy()->isIntOrIntVectorTy() &&
1554 I.getOpcode() != Instruction::BitCast) {
1555 ConstantRange OpRange =
1556 OpSt.asConstantRange(Ty: I.getSrcTy(), /*UndefAllowed=*/false);
1557 auto &LV = getValueState(V: &I);
1558
1559 Type *DestTy = I.getDestTy();
1560 ConstantRange Res = ConstantRange::getEmpty(BitWidth: DestTy->getScalarSizeInBits());
1561 if (auto *Trunc = dyn_cast<TruncInst>(Val: &I))
1562 Res = OpRange.truncate(BitWidth: DestTy->getScalarSizeInBits(),
1563 NoWrapKind: Trunc->getNoWrapKind());
1564 else
1565 Res = OpRange.castOp(CastOp: I.getOpcode(), BitWidth: DestTy->getScalarSizeInBits());
1566 mergeInValue(IV&: LV, V: &I, MergeWithV: ValueLatticeElement::getRange(CR: Res));
1567 } else
1568 markOverdefined(V: &I);
1569}
1570
1571void SCCPInstVisitor::handleExtractOfWithOverflow(ExtractValueInst &EVI,
1572 const WithOverflowInst *WO,
1573 unsigned Idx) {
1574 Value *LHS = WO->getLHS(), *RHS = WO->getRHS();
1575 Type *Ty = LHS->getType();
1576
1577 addAdditionalUser(V: LHS, U: &EVI);
1578 addAdditionalUser(V: RHS, U: &EVI);
1579
1580 const ValueLatticeElement &L = getValueState(V: LHS);
1581 if (L.isUnknownOrUndef())
1582 return; // Wait to resolve.
1583 ConstantRange LR = L.asConstantRange(Ty, /*UndefAllowed=*/false);
1584
1585 const ValueLatticeElement &R = getValueState(V: RHS);
1586 if (R.isUnknownOrUndef())
1587 return; // Wait to resolve.
1588
1589 ConstantRange RR = R.asConstantRange(Ty, /*UndefAllowed=*/false);
1590 if (Idx == 0) {
1591 ConstantRange Res = LR.binaryOp(BinOp: WO->getBinaryOp(), Other: RR);
1592 mergeInValue(IV&: ValueState[&EVI], V: &EVI, MergeWithV: ValueLatticeElement::getRange(CR: Res));
1593 } else {
1594 assert(Idx == 1 && "Index can only be 0 or 1");
1595 ConstantRange NWRegion = ConstantRange::makeGuaranteedNoWrapRegion(
1596 BinOp: WO->getBinaryOp(), Other: RR, NoWrapKind: WO->getNoWrapKind());
1597 if (NWRegion.contains(CR: LR))
1598 return (void)markConstant(V: &EVI, C: ConstantInt::getFalse(Ty: EVI.getType()));
1599 markOverdefined(V: &EVI);
1600 }
1601}
1602
1603void SCCPInstVisitor::visitExtractValueInst(ExtractValueInst &EVI) {
1604 // If this returns a struct, mark all elements over defined, we don't track
1605 // structs in structs.
1606 if (EVI.getType()->isStructTy())
1607 return (void)markOverdefined(V: &EVI);
1608
1609 // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would
1610 // discover a concrete value later.
1611 if (ValueState[&EVI].isOverdefined())
1612 return (void)markOverdefined(V: &EVI);
1613
1614 // If this is extracting from more than one level of struct, we don't know.
1615 if (EVI.getNumIndices() != 1)
1616 return (void)markOverdefined(V: &EVI);
1617
1618 Value *AggVal = EVI.getAggregateOperand();
1619 if (AggVal->getType()->isStructTy()) {
1620 unsigned i = *EVI.idx_begin();
1621 if (auto *WO = dyn_cast<WithOverflowInst>(Val: AggVal))
1622 return handleExtractOfWithOverflow(EVI, WO, Idx: i);
1623 ValueLatticeElement EltVal = getStructValueState(V: AggVal, i);
1624 mergeInValue(IV&: ValueState[&EVI], V: &EVI, MergeWithV: EltVal);
1625 } else {
1626 // Otherwise, must be extracting from an array.
1627 return (void)markOverdefined(V: &EVI);
1628 }
1629}
1630
1631void SCCPInstVisitor::visitInsertValueInst(InsertValueInst &IVI) {
1632 auto *STy = dyn_cast<StructType>(Val: IVI.getType());
1633 if (!STy)
1634 return (void)markOverdefined(V: &IVI);
1635
1636 // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would
1637 // discover a concrete value later.
1638 if (ValueState[&IVI].isOverdefined())
1639 return (void)markOverdefined(V: &IVI);
1640
1641 // If this has more than one index, we can't handle it, drive all results to
1642 // undef.
1643 if (IVI.getNumIndices() != 1)
1644 return (void)markOverdefined(V: &IVI);
1645
1646 Value *Aggr = IVI.getAggregateOperand();
1647 unsigned Idx = *IVI.idx_begin();
1648
1649 // Compute the result based on what we're inserting.
1650 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
1651 // This passes through all values that aren't the inserted element.
1652 if (i != Idx) {
1653 ValueLatticeElement EltVal = getStructValueState(V: Aggr, i);
1654 mergeInValue(IV&: getStructValueState(V: &IVI, i), V: &IVI, MergeWithV: EltVal);
1655 continue;
1656 }
1657
1658 Value *Val = IVI.getInsertedValueOperand();
1659 if (Val->getType()->isStructTy())
1660 // We don't track structs in structs.
1661 markOverdefined(IV&: getStructValueState(V: &IVI, i), V: &IVI);
1662 else {
1663 ValueLatticeElement InVal = getValueState(V: Val);
1664 mergeInValue(IV&: getStructValueState(V: &IVI, i), V: &IVI, MergeWithV: InVal);
1665 }
1666 }
1667}
1668
1669void SCCPInstVisitor::visitSelectInst(SelectInst &I) {
1670 // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would
1671 // discover a concrete value later.
1672 if (isInstFullyOverDefined(Inst&: I))
1673 return (void)markOverdefined(V: &I);
1674
1675 const ValueLatticeElement &CondValue = getValueState(V: I.getCondition());
1676 if (CondValue.isUnknownOrUndef())
1677 return;
1678
1679 if (ConstantInt *CondCB =
1680 getConstantInt(IV: CondValue, Ty: I.getCondition()->getType())) {
1681 Value *OpVal = CondCB->isZero() ? I.getFalseValue() : I.getTrueValue();
1682 forEachLatticeElement(V: &I, Fn: [&](auto GetValueState) {
1683 ValueLatticeElement OpValState = GetValueState(OpVal);
1684 mergeInValue(IV&: GetValueState(&I), V: &I, MergeWithV: OpValState);
1685 });
1686 return;
1687 }
1688
1689 // Otherwise, the condition is overdefined or a constant we can't evaluate.
1690 // See if we can produce something better than overdefined based on the T/F
1691 // value.
1692 forEachLatticeElement(V: &I, Fn: [&](auto GetValueState) {
1693 ValueLatticeElement TVal = GetValueState(I.getTrueValue());
1694 ValueLatticeElement FVal = GetValueState(I.getFalseValue());
1695
1696 ValueLatticeElement &State = GetValueState(&I);
1697 bool Changed = State.mergeIn(RHS: TVal);
1698 Changed |= State.mergeIn(RHS: FVal);
1699 if (Changed)
1700 pushUsersToWorkListMsg(IV&: State, V: &I);
1701 });
1702}
1703
1704// Handle Unary Operators.
1705void SCCPInstVisitor::visitUnaryOperator(Instruction &I) {
1706 ValueLatticeElement V0State = getValueState(V: I.getOperand(i: 0));
1707
1708 ValueLatticeElement &IV = ValueState[&I];
1709 // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would
1710 // discover a concrete value later.
1711 if (IV.isOverdefined())
1712 return (void)markOverdefined(V: &I);
1713
1714 // If something is unknown/undef, wait for it to resolve.
1715 if (V0State.isUnknownOrUndef())
1716 return;
1717
1718 if (SCCPSolver::isConstant(LV: V0State))
1719 if (Constant *C = ConstantFoldUnaryOpOperand(
1720 Opcode: I.getOpcode(), Op: getConstant(LV: V0State, Ty: I.getType()), DL))
1721 return (void)markConstant(IV, V: &I, C);
1722
1723 markOverdefined(V: &I);
1724}
1725
1726void SCCPInstVisitor::visitFreezeInst(FreezeInst &I) {
1727 // If this freeze returns a struct, just mark the result overdefined.
1728 // TODO: We could do a lot better than this.
1729 if (I.getType()->isStructTy())
1730 return (void)markOverdefined(V: &I);
1731
1732 ValueLatticeElement V0State = getValueState(V: I.getOperand(i_nocapture: 0));
1733 ValueLatticeElement &IV = ValueState[&I];
1734 // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would
1735 // discover a concrete value later.
1736 if (IV.isOverdefined())
1737 return (void)markOverdefined(V: &I);
1738
1739 // If something is unknown/undef, wait for it to resolve.
1740 if (V0State.isUnknownOrUndef())
1741 return;
1742
1743 if (SCCPSolver::isConstant(LV: V0State) &&
1744 isGuaranteedNotToBeUndefOrPoison(V: getConstant(LV: V0State, Ty: I.getType())))
1745 return (void)markConstant(IV, V: &I, C: getConstant(LV: V0State, Ty: I.getType()));
1746
1747 markOverdefined(V: &I);
1748}
1749
1750// Handle Binary Operators.
1751void SCCPInstVisitor::visitBinaryOperator(Instruction &I) {
1752 ValueLatticeElement V1State = getValueState(V: I.getOperand(i: 0));
1753 ValueLatticeElement V2State = getValueState(V: I.getOperand(i: 1));
1754
1755 ValueLatticeElement &IV = ValueState[&I];
1756 if (IV.isOverdefined())
1757 return;
1758
1759 // If something is undef, wait for it to resolve.
1760 if (V1State.isUnknownOrUndef() || V2State.isUnknownOrUndef())
1761 return;
1762
1763 if (V1State.isOverdefined() && V2State.isOverdefined())
1764 return (void)markOverdefined(V: &I);
1765
1766 // If either of the operands is a constant, try to fold it to a constant.
1767 // TODO: Use information from notconstant better.
1768 if ((V1State.isConstant() || V2State.isConstant())) {
1769 Value *V1 = SCCPSolver::isConstant(LV: V1State)
1770 ? getConstant(LV: V1State, Ty: I.getOperand(i: 0)->getType())
1771 : I.getOperand(i: 0);
1772 Value *V2 = SCCPSolver::isConstant(LV: V2State)
1773 ? getConstant(LV: V2State, Ty: I.getOperand(i: 1)->getType())
1774 : I.getOperand(i: 1);
1775 Value *R;
1776 if (auto *FPOp = dyn_cast<FPMathOperator>(Val: &I))
1777 R = simplifyBinOp(Opcode: I.getOpcode(), LHS: V1, RHS: V2, FMF: FPOp->getFastMathFlags(),
1778 Q: SimplifyQuery(DL, &I));
1779 else
1780 R = simplifyBinOp(Opcode: I.getOpcode(), LHS: V1, RHS: V2, Q: SimplifyQuery(DL, &I));
1781 auto *C = dyn_cast_or_null<Constant>(Val: R);
1782 if (C) {
1783 // Conservatively assume that the result may be based on operands that may
1784 // be undef. Note that we use mergeInValue to combine the constant with
1785 // the existing lattice value for I, as different constants might be found
1786 // after one of the operands go to overdefined, e.g. due to one operand
1787 // being a special floating value.
1788 ValueLatticeElement NewV;
1789 NewV.markConstant(V: C, /*MayIncludeUndef=*/true);
1790 return (void)mergeInValue(IV&: ValueState[&I], V: &I, MergeWithV: NewV);
1791 }
1792 }
1793
1794 // Only use ranges for binary operators on integers.
1795 if (!I.getType()->isIntOrIntVectorTy())
1796 return markOverdefined(V: &I);
1797
1798 // Try to simplify to a constant range.
1799 ConstantRange A =
1800 V1State.asConstantRange(Ty: I.getType(), /*UndefAllowed=*/false);
1801 ConstantRange B =
1802 V2State.asConstantRange(Ty: I.getType(), /*UndefAllowed=*/false);
1803
1804 auto *BO = cast<BinaryOperator>(Val: &I);
1805 ConstantRange R = A.binaryOp(BO: *BO, Other: B);
1806 mergeInValue(IV&: ValueState[&I], V: &I, MergeWithV: ValueLatticeElement::getRange(CR: R));
1807}
1808
1809// Handle ICmpInst instruction.
1810void SCCPInstVisitor::visitCmpInst(CmpInst &I) {
1811 // Do not cache this lookup, getValueState calls later in the function might
1812 // invalidate the reference.
1813 if (ValueState[&I].isOverdefined())
1814 return (void)markOverdefined(V: &I);
1815
1816 Value *Op1 = I.getOperand(i_nocapture: 0);
1817 Value *Op2 = I.getOperand(i_nocapture: 1);
1818
1819 // For parameters, use ParamState which includes constant range info if
1820 // available.
1821 auto V1State = getValueState(V: Op1);
1822 auto V2State = getValueState(V: Op2);
1823
1824 Constant *C = V1State.getCompare(Pred: I.getPredicate(), Ty: I.getType(), Other: V2State, DL);
1825 if (C) {
1826 ValueLatticeElement CV;
1827 CV.markConstant(V: C);
1828 mergeInValue(IV&: ValueState[&I], V: &I, MergeWithV: CV);
1829 return;
1830 }
1831
1832 // If operands are still unknown, wait for it to resolve.
1833 if ((V1State.isUnknownOrUndef() || V2State.isUnknownOrUndef()) &&
1834 !SCCPSolver::isConstant(LV: ValueState[&I]))
1835 return;
1836
1837 markOverdefined(V: &I);
1838}
1839
1840// Handle getelementptr instructions. If all operands are constants then we
1841// can turn this into a getelementptr ConstantExpr.
1842void SCCPInstVisitor::visitGetElementPtrInst(GetElementPtrInst &I) {
1843 if (ValueState[&I].isOverdefined())
1844 return (void)markOverdefined(V: &I);
1845
1846 const ValueLatticeElement &PtrState = getValueState(V: I.getPointerOperand());
1847 if (PtrState.isUnknownOrUndef())
1848 return;
1849
1850 // gep inbounds/nuw of non-null is non-null.
1851 if (PtrState.isNotConstant() && PtrState.getNotConstant()->isNullValue()) {
1852 if (I.hasNoUnsignedWrap() ||
1853 (I.isInBounds() &&
1854 !NullPointerIsDefined(F: I.getFunction(), AS: I.getAddressSpace())))
1855 return (void)markNotNull(IV&: ValueState[&I], V: &I);
1856 return (void)markOverdefined(V: &I);
1857 }
1858
1859 SmallVector<Constant *, 8> Operands;
1860 Operands.reserve(N: I.getNumOperands());
1861 bool PtrMayHaveDifferentProvenance = PtrState.mayHaveDifferentProvenance();
1862
1863 for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) {
1864 const ValueLatticeElement &State = getValueState(V: I.getOperand(i_nocapture: i));
1865 if (State.isUnknownOrUndef())
1866 return; // Operands are not resolved yet.
1867
1868 if (Constant *C = getConstant(LV: State, Ty: I.getOperand(i_nocapture: i)->getType())) {
1869 Operands.push_back(Elt: C);
1870 continue;
1871 }
1872
1873 return (void)markOverdefined(V: &I);
1874 }
1875
1876 if (Constant *C = ConstantFoldInstOperands(I: &I, Ops: Operands, DL)) {
1877 mergeInValue(IV&: ValueState[&I], V: &I, MergeWithV: ValueLatticeElement::get(C));
1878 // The pointer operand's lattice has found to be a constant, however, the
1879 // returned pointer of the GEP may not be freely substituted, as it may have
1880 // been derived from a pointer with potentially different provenance.
1881 if (PtrMayHaveDifferentProvenance)
1882 ValueState[&I].setMayHaveDifferentProvenance(true);
1883 } else
1884 markOverdefined(V: &I);
1885}
1886
1887void SCCPInstVisitor::visitAllocaInst(AllocaInst &I) {
1888 if (!NullPointerIsDefined(F: I.getFunction(), AS: I.getAddressSpace()))
1889 return (void)markNotNull(IV&: ValueState[&I], V: &I);
1890
1891 markOverdefined(V: &I);
1892}
1893
1894void SCCPInstVisitor::visitStoreInst(StoreInst &SI) {
1895 // If this store is of a struct, ignore it.
1896 if (SI.getOperand(i_nocapture: 0)->getType()->isStructTy())
1897 return;
1898
1899 if (TrackedGlobals.empty() || !isa<GlobalVariable>(Val: SI.getOperand(i_nocapture: 1)))
1900 return;
1901
1902 GlobalVariable *GV = cast<GlobalVariable>(Val: SI.getOperand(i_nocapture: 1));
1903 auto I = TrackedGlobals.find(Val: GV);
1904 if (I == TrackedGlobals.end())
1905 return;
1906
1907 // Get the value we are storing into the global, then merge it.
1908 mergeInValue(IV&: I->second, V: GV, MergeWithV: getValueState(V: SI.getOperand(i_nocapture: 0)),
1909 Opts: ValueLatticeElement::MergeOptions().setCheckWiden(false));
1910 if (I->second.isOverdefined())
1911 TrackedGlobals.erase(I); // No need to keep tracking this!
1912}
1913
1914static ValueLatticeElement getValueFromMetadata(const Instruction *I) {
1915 if (const auto *CB = dyn_cast<CallBase>(Val: I)) {
1916 if (CB->getType()->isIntOrIntVectorTy())
1917 if (std::optional<ConstantRange> Range = CB->getRange())
1918 return ValueLatticeElement::getRange(CR: *Range);
1919 if (CB->getType()->isPointerTy() && CB->isReturnNonNull())
1920 return ValueLatticeElement::getNot(
1921 C: ConstantPointerNull::get(T: cast<PointerType>(Val: I->getType())));
1922 }
1923
1924 if (I->getType()->isIntOrIntVectorTy())
1925 if (MDNode *Ranges = I->getMetadata(KindID: LLVMContext::MD_range))
1926 return ValueLatticeElement::getRange(
1927 CR: getConstantRangeFromMetadata(RangeMD: *Ranges));
1928 if (I->hasMetadata(KindID: LLVMContext::MD_nonnull))
1929 return ValueLatticeElement::getNot(
1930 C: ConstantPointerNull::get(T: cast<PointerType>(Val: I->getType())));
1931
1932 return ValueLatticeElement::getOverdefined();
1933}
1934
1935// Handle load instructions. If the operand is a constant pointer to a constant
1936// global, we can replace the load with the loaded constant value!
1937void SCCPInstVisitor::visitLoadInst(LoadInst &I) {
1938 // If this load is of a struct or the load is volatile, just mark the result
1939 // as overdefined.
1940 if (I.getType()->isStructTy() || I.isVolatile())
1941 return (void)markOverdefined(V: &I);
1942
1943 // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would
1944 // discover a concrete value later.
1945 if (ValueState[&I].isOverdefined())
1946 return (void)markOverdefined(V: &I);
1947
1948 const ValueLatticeElement &PtrVal = getValueState(V: I.getOperand(i_nocapture: 0));
1949 if (PtrVal.isUnknownOrUndef())
1950 return; // The pointer is not resolved yet!
1951
1952 if (SCCPSolver::isConstant(LV: PtrVal)) {
1953 Constant *Ptr = getConstant(LV: PtrVal, Ty: I.getOperand(i_nocapture: 0)->getType());
1954 ValueLatticeElement &IV = ValueState[&I];
1955
1956 // load null is undefined.
1957 if (isa<ConstantPointerNull>(Val: Ptr)) {
1958 if (NullPointerIsDefined(F: I.getFunction(), AS: I.getPointerAddressSpace()))
1959 return (void)markOverdefined(IV, V: &I);
1960 else
1961 return;
1962 }
1963
1964 // Transform load (constant global) into the value loaded.
1965 if (auto *GV = dyn_cast<GlobalVariable>(Val: Ptr)) {
1966 if (!TrackedGlobals.empty()) {
1967 // If we are tracking this global, merge in the known value for it.
1968 auto It = TrackedGlobals.find(Val: GV);
1969 if (It != TrackedGlobals.end()) {
1970 mergeInValue(IV, V: &I, MergeWithV: It->second, Opts: getMaxWidenStepsOpts());
1971 return;
1972 }
1973 }
1974 }
1975
1976 // Transform load from a constant into a constant if possible.
1977 if (Constant *C = ConstantFoldLoadFromConstPtr(C: Ptr, Ty: I.getType(), DL))
1978 return (void)markConstant(IV, V: &I, C);
1979 }
1980
1981 // Fall back to metadata.
1982 mergeInValue(IV&: ValueState[&I], V: &I, MergeWithV: getValueFromMetadata(I: &I));
1983}
1984
1985void SCCPInstVisitor::visitCallBase(CallBase &CB) {
1986 handleCallResult(CB);
1987 handleCallArguments(CB);
1988}
1989
1990void SCCPInstVisitor::handleCallOverdefined(CallBase &CB) {
1991 Function *F = CB.getCalledFunction();
1992
1993 // Void return and not tracking callee, just bail.
1994 if (CB.getType()->isVoidTy())
1995 return;
1996
1997 // Always mark struct return as overdefined.
1998 if (CB.getType()->isStructTy())
1999 return (void)markOverdefined(V: &CB);
2000
2001 if (!F || !F->isDeclaration())
2002 return (void)mergeInValue(IV&: ValueState[&CB], V: &CB, MergeWithV: getValueFromMetadata(I: &CB));
2003
2004 // Otherwise, if we have a single return value case, and if the function is
2005 // a declaration, maybe we can constant fold it.
2006 const TargetLibraryInfo *TLI = &GetTLI(*F);
2007 if (canConstantFoldCallTo(Call: &CB, F, TLI)) {
2008 SmallVector<Constant *, 8> Operands;
2009 for (const Use &A : CB.args()) {
2010 if (A.get()->getType()->isStructTy())
2011 return markOverdefined(V: &CB); // Can't handle struct args.
2012 if (A.get()->getType()->isMetadataTy())
2013 continue; // Carried in CB, not allowed in Operands.
2014 const ValueLatticeElement &State = getValueState(V: A);
2015
2016 if (State.isUnknownOrUndef())
2017 return; // Operands are not resolved yet.
2018 if (SCCPSolver::isOverdefined(LV: State))
2019 return (void)markOverdefined(V: &CB);
2020 assert(SCCPSolver::isConstant(State) && "Unknown state!");
2021 Operands.push_back(Elt: getConstant(LV: State, Ty: A->getType()));
2022 }
2023
2024 if (SCCPSolver::isOverdefined(LV: getValueState(V: &CB)))
2025 return (void)markOverdefined(V: &CB);
2026
2027 // If we can constant fold this, mark the result of the call as a
2028 // constant.
2029 if (Constant *C = ConstantFoldCall(Call: &CB, F, Operands, TLI)) {
2030 mergeInValue(IV&: ValueState[&CB], V: &CB, MergeWithV: ValueLatticeElement::get(C));
2031 return;
2032 }
2033 }
2034
2035 // Fall back to metadata.
2036 mergeInValue(IV&: ValueState[&CB], V: &CB, MergeWithV: getValueFromMetadata(I: &CB));
2037}
2038
2039void SCCPInstVisitor::handleCallArguments(CallBase &CB) {
2040 Function *F = CB.getCalledFunction();
2041 // If this is a local function that doesn't have its address taken, mark its
2042 // entry block executable and merge in the actual arguments to the call into
2043 // the formal arguments of the function.
2044 if (TrackingIncomingArguments.count(Ptr: F)) {
2045 markBlockExecutable(BB: &F->front());
2046
2047 // Propagate information from this call site into the callee.
2048 auto CAI = CB.arg_begin();
2049 for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); AI != E;
2050 ++AI, ++CAI) {
2051 // If this argument is byval, and if the function is not readonly, there
2052 // will be an implicit copy formed of the input aggregate.
2053 if (AI->hasByValAttr() && !F->onlyReadsMemory()) {
2054 markOverdefined(V: &*AI);
2055 continue;
2056 }
2057
2058 if (auto *STy = dyn_cast<StructType>(Val: AI->getType())) {
2059 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
2060 ValueLatticeElement CallArg = getStructValueState(V: *CAI, i);
2061 mergeInValue(IV&: getStructValueState(V: &*AI, i), V: &*AI, MergeWithV: CallArg,
2062 Opts: getMaxWidenStepsOpts());
2063 }
2064 } else {
2065 ValueLatticeElement CallArg =
2066 getValueState(V: *CAI).intersect(Other: getArgAttributeVL(A: &*AI));
2067 mergeInValue(IV&: ValueState[&*AI], V: &*AI, MergeWithV: CallArg, Opts: getMaxWidenStepsOpts());
2068 }
2069 }
2070 }
2071}
2072
2073void SCCPInstVisitor::handlePredicate(Instruction *I, Value *CopyOf,
2074 const PredicateBase *PI) {
2075 ValueLatticeElement CopyOfVal = getValueState(V: CopyOf);
2076 const std::optional<PredicateConstraint> &Constraint = PI->getConstraint();
2077 if (!Constraint) {
2078 mergeInValue(IV&: ValueState[I], V: I, MergeWithV: CopyOfVal);
2079 return;
2080 }
2081
2082 CmpInst::Predicate Pred = Constraint->Predicate;
2083 Value *OtherOp = Constraint->OtherOp;
2084
2085 // Wait until OtherOp is resolved.
2086 if (getValueState(V: OtherOp).isUnknown()) {
2087 addAdditionalUser(V: OtherOp, U: I);
2088 return;
2089 }
2090
2091 ValueLatticeElement CondVal = getValueState(V: OtherOp);
2092 ValueLatticeElement &IV = ValueState[I];
2093 if (CondVal.isConstantRange() || CopyOfVal.isConstantRange()) {
2094 auto ImposedCR =
2095 ConstantRange::getFull(BitWidth: DL.getTypeSizeInBits(Ty: CopyOf->getType()));
2096
2097 // Get the range imposed by the condition.
2098 if (CondVal.isConstantRange())
2099 ImposedCR = ConstantRange::makeAllowedICmpRegion(
2100 Pred, Other: CondVal.getConstantRange());
2101
2102 // Combine range info for the original value with the new range from the
2103 // condition.
2104 auto CopyOfCR = CopyOfVal.asConstantRange(Ty: CopyOf->getType(),
2105 /*UndefAllowed=*/true);
2106 // Treat an unresolved input like a full range.
2107 if (CopyOfCR.isEmptySet())
2108 CopyOfCR = ConstantRange::getFull(BitWidth: CopyOfCR.getBitWidth());
2109 auto NewCR = ImposedCR.intersectWith(CR: CopyOfCR);
2110 // If the existing information is != x, do not use the information from
2111 // a chained predicate, as the != x information is more likely to be
2112 // helpful in practice.
2113 if (!CopyOfCR.contains(CR: NewCR) && CopyOfCR.getSingleMissingElement())
2114 NewCR = std::move(CopyOfCR);
2115
2116 // The new range is based on a branch condition. That guarantees that
2117 // neither of the compare operands can be undef in the branch targets,
2118 // unless we have conditions that are always true/false (e.g. icmp ule
2119 // i32, %a, i32_max). For the latter overdefined/empty range will be
2120 // inferred, but the branch will get folded accordingly anyways.
2121 addAdditionalUser(V: OtherOp, U: I);
2122 mergeInValue(
2123 IV, V: I, MergeWithV: ValueLatticeElement::getRange(CR: NewCR, /*MayIncludeUndef*/ false));
2124 return;
2125 } else if (Pred == CmpInst::ICMP_EQ &&
2126 (CondVal.isConstant() || CondVal.isNotConstant())) {
2127 // For non-integer values or integer constant expressions, only
2128 // propagate equal constants or not-constants.
2129 addAdditionalUser(V: OtherOp, U: I);
2130 if (CopyOf->getType()->isPointerTy())
2131 CondVal.setMayHaveDifferentProvenance(true);
2132 mergeInValue(IV, V: I, MergeWithV: CondVal);
2133 return;
2134 } else if (Pred == CmpInst::ICMP_NE && CondVal.isConstant()) {
2135 // Propagate inequalities.
2136 addAdditionalUser(V: OtherOp, U: I);
2137 mergeInValue(IV, V: I, MergeWithV: ValueLatticeElement::getNot(C: CondVal.getConstant()));
2138 return;
2139 }
2140
2141 return (void)mergeInValue(IV, V: I, MergeWithV: CopyOfVal);
2142}
2143
2144void SCCPInstVisitor::handleCallResult(CallBase &CB) {
2145 Function *F = CB.getCalledFunction();
2146
2147 if (auto *II = dyn_cast<IntrinsicInst>(Val: &CB)) {
2148 if (II->getIntrinsicID() == Intrinsic::vscale) {
2149 unsigned BitWidth = CB.getType()->getScalarSizeInBits();
2150 const ConstantRange Result = getVScaleRange(F: II->getFunction(), BitWidth);
2151 return (void)mergeInValue(IV&: ValueState[II], V: II,
2152 MergeWithV: ValueLatticeElement::getRange(CR: Result));
2153 }
2154 if (II->getIntrinsicID() == Intrinsic::experimental_get_vector_length) {
2155 Value *CountArg = II->getArgOperand(i: 0);
2156 Value *VF = II->getArgOperand(i: 1);
2157 bool Scalable = cast<ConstantInt>(Val: II->getArgOperand(i: 2))->isOne();
2158
2159 // Computation happens in the larger type.
2160 unsigned BitWidth = std::max(a: CountArg->getType()->getScalarSizeInBits(),
2161 b: VF->getType()->getScalarSizeInBits());
2162
2163 ConstantRange Count = getValueState(V: CountArg)
2164 .asConstantRange(Ty: CountArg->getType(), UndefAllowed: false)
2165 .zeroExtend(BitWidth);
2166 ConstantRange MaxLanes = getValueState(V: VF)
2167 .asConstantRange(Ty: VF->getType(), UndefAllowed: false)
2168 .zeroExtend(BitWidth);
2169 if (Scalable)
2170 MaxLanes =
2171 MaxLanes.multiply(Other: getVScaleRange(F: II->getFunction(), BitWidth));
2172
2173 // The result is always less than both Count and MaxLanes.
2174 ConstantRange Result = ConstantRange::getNonEmpty(
2175 Lower: APInt::getZero(numBits: BitWidth),
2176 Upper: APIntOps::umin(A: Count.getUnsignedMax(), B: MaxLanes.getUnsignedMax()) +
2177 1);
2178
2179 // If Count <= MaxLanes, getvectorlength(Count, MaxLanes) = Count
2180 if (Count.icmp(Pred: CmpInst::ICMP_ULE, Other: MaxLanes))
2181 Result = std::move(Count);
2182
2183 Result = Result.truncate(BitWidth: II->getType()->getScalarSizeInBits());
2184 return (void)mergeInValue(IV&: ValueState[II], V: II,
2185 MergeWithV: ValueLatticeElement::getRange(CR: Result));
2186 }
2187
2188 if (ConstantRange::isIntrinsicSupported(IntrinsicID: II->getIntrinsicID())) {
2189 // Compute result range for intrinsics supported by ConstantRange.
2190 // Do this even if we don't know a range for all operands, as we may
2191 // still know something about the result range, e.g. of abs(x).
2192 SmallVector<ConstantRange, 2> OpRanges;
2193 for (Value *Op : II->args()) {
2194 const ValueLatticeElement &State = getValueState(V: Op);
2195 if (State.isUnknownOrUndef())
2196 return;
2197 OpRanges.push_back(
2198 Elt: State.asConstantRange(Ty: Op->getType(), /*UndefAllowed=*/false));
2199 }
2200
2201 ConstantRange Result =
2202 ConstantRange::intrinsic(IntrinsicID: II->getIntrinsicID(), Ops: OpRanges);
2203 return (void)mergeInValue(IV&: ValueState[II], V: II,
2204 MergeWithV: ValueLatticeElement::getRange(CR: Result));
2205 }
2206 }
2207
2208 // The common case is that we aren't tracking the callee, either because we
2209 // are not doing interprocedural analysis or the callee is indirect, or is
2210 // external. Handle these cases first.
2211 if (!F || F->isDeclaration())
2212 return handleCallOverdefined(CB);
2213
2214 // If this is a single/zero retval case, see if we're tracking the function.
2215 if (auto *STy = dyn_cast<StructType>(Val: F->getReturnType())) {
2216 if (!MRVFunctionsTracked.count(Ptr: F))
2217 return handleCallOverdefined(CB); // Not tracking this callee.
2218
2219 // If we are tracking this callee, propagate the result of the function
2220 // into this call site.
2221 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
2222 mergeInValue(IV&: getStructValueState(V: &CB, i), V: &CB,
2223 MergeWithV: TrackedMultipleRetVals[std::make_pair(x&: F, y&: i)],
2224 Opts: getMaxWidenStepsOpts());
2225 } else {
2226 auto TFRVI = TrackedRetVals.find(Key: F);
2227 if (TFRVI == TrackedRetVals.end())
2228 return handleCallOverdefined(CB); // Not tracking this callee.
2229
2230 // If so, propagate the return value of the callee into this call result.
2231 mergeInValue(IV&: ValueState[&CB], V: &CB, MergeWithV: TFRVI->second, Opts: getMaxWidenStepsOpts());
2232 }
2233}
2234
2235bool SCCPInstVisitor::isInstFullyOverDefined(Instruction &Inst) {
2236 // For structure Type, we handle each member separately.
2237 // A structure object won't be considered as overdefined when
2238 // there is at least one member that is not overdefined.
2239 if (StructType *STy = dyn_cast<StructType>(Val: Inst.getType())) {
2240 for (unsigned i = 0, e = STy->getNumElements(); i < e; ++i) {
2241 if (!getStructValueState(V: &Inst, i).isOverdefined())
2242 return false;
2243 }
2244 return true;
2245 }
2246
2247 return getValueState(V: &Inst).isOverdefined();
2248}
2249
2250void SCCPInstVisitor::solve() {
2251 // Process the work lists until they are empty!
2252 while (!BBWorkList.empty() || !InstWorkList.empty()) {
2253 // Process the instruction work list.
2254 while (!InstWorkList.empty()) {
2255 Instruction *I = InstWorkList.pop_back_val();
2256 Invalidated.erase(V: I);
2257
2258 LLVM_DEBUG(dbgs() << "\nPopped off I-WL: " << *I << '\n');
2259
2260 visit(I);
2261 }
2262
2263 // Process the basic block work list.
2264 while (!BBWorkList.empty()) {
2265 BasicBlock *BB = BBWorkList.pop_back_val();
2266 BBVisited.insert(Ptr: BB);
2267
2268 LLVM_DEBUG(dbgs() << "\nPopped off BBWL: " << *BB << '\n');
2269 for (Instruction &I : *BB) {
2270 CurI = &I;
2271 visit(I);
2272 }
2273 CurI = nullptr;
2274 }
2275 }
2276}
2277
2278bool SCCPInstVisitor::resolvedUndef(Instruction &I) {
2279 // Look for instructions which produce undef values.
2280 if (I.getType()->isVoidTy())
2281 return false;
2282
2283 if (auto *STy = dyn_cast<StructType>(Val: I.getType())) {
2284 // Only a few things that can be structs matter for undef.
2285
2286 // Tracked calls must never be marked overdefined in resolvedUndefsIn.
2287 if (auto *CB = dyn_cast<CallBase>(Val: &I))
2288 if (Function *F = CB->getCalledFunction())
2289 if (MRVFunctionsTracked.count(Ptr: F))
2290 return false;
2291
2292 // extractvalue and insertvalue don't need to be marked; they are
2293 // tracked as precisely as their operands.
2294 if (isa<ExtractValueInst>(Val: I) || isa<InsertValueInst>(Val: I))
2295 return false;
2296 // Send the results of everything else to overdefined. We could be
2297 // more precise than this but it isn't worth bothering.
2298 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
2299 ValueLatticeElement &LV = getStructValueState(V: &I, i);
2300 if (LV.isUnknown()) {
2301 markOverdefined(IV&: LV, V: &I);
2302 return true;
2303 }
2304 }
2305 return false;
2306 }
2307
2308 ValueLatticeElement &LV = getValueState(V: &I);
2309 if (!LV.isUnknown())
2310 return false;
2311
2312 // There are two reasons a call can have an undef result
2313 // 1. It could be tracked.
2314 // 2. It could be constant-foldable.
2315 // Because of the way we solve return values, tracked calls must
2316 // never be marked overdefined in resolvedUndefsIn.
2317 if (auto *CB = dyn_cast<CallBase>(Val: &I))
2318 if (Function *F = CB->getCalledFunction())
2319 if (TrackedRetVals.count(Key: F))
2320 return false;
2321
2322 if (isa<LoadInst>(Val: I)) {
2323 // A load here means one of two things: a load of undef from a global,
2324 // a load from an unknown pointer. Either way, having it return undef
2325 // is okay.
2326 return false;
2327 }
2328
2329 markOverdefined(V: &I);
2330 return true;
2331}
2332
2333/// While solving the dataflow for a function, we don't compute a result for
2334/// operations with an undef operand, to allow undef to be lowered to a
2335/// constant later. For example, constant folding of "zext i8 undef to i16"
2336/// would result in "i16 0", and if undef is later lowered to "i8 1", then the
2337/// zext result would become "i16 1" and would result into an overdefined
2338/// lattice value once merged with the previous result. Not computing the
2339/// result of the zext (treating undef the same as unknown) allows us to handle
2340/// a later undef->constant lowering more optimally.
2341///
2342/// However, if the operand remains undef when the solver returns, we do need
2343/// to assign some result to the instruction (otherwise we would treat it as
2344/// unreachable). For simplicity, we mark any instructions that are still
2345/// unknown as overdefined.
2346bool SCCPInstVisitor::resolvedUndefsIn(Function &F) {
2347 bool MadeChange = false;
2348 for (BasicBlock &BB : F) {
2349 if (!BBExecutable.count(Ptr: &BB))
2350 continue;
2351
2352 for (Instruction &I : BB)
2353 MadeChange |= resolvedUndef(I);
2354 }
2355
2356 LLVM_DEBUG(if (MadeChange) dbgs()
2357 << "\nResolved undefs in " << F.getName() << '\n');
2358
2359 return MadeChange;
2360}
2361
2362//===----------------------------------------------------------------------===//
2363//
2364// SCCPSolver implementations
2365//
2366SCCPSolver::SCCPSolver(
2367 const DataLayout &DL,
2368 std::function<const TargetLibraryInfo &(Function &)> GetTLI,
2369 LLVMContext &Ctx)
2370 : Visitor(new SCCPInstVisitor(DL, std::move(GetTLI), Ctx)) {}
2371
2372SCCPSolver::~SCCPSolver() = default;
2373
2374const DataLayout &SCCPSolver::getDataLayout() const {
2375 return Visitor->getDataLayout();
2376}
2377
2378void SCCPSolver::addPredicateInfo(Function &F, DominatorTree &DT,
2379 AssumptionCache &AC) {
2380 Visitor->addPredicateInfo(F, DT, AC);
2381}
2382
2383void SCCPSolver::removeSSACopies(Function &F) {
2384 Visitor->removeSSACopies(F);
2385}
2386
2387bool SCCPSolver::markBlockExecutable(BasicBlock *BB) {
2388 return Visitor->markBlockExecutable(BB);
2389}
2390
2391const PredicateBase *SCCPSolver::getPredicateInfoFor(Instruction *I) {
2392 return Visitor->getPredicateInfoFor(I);
2393}
2394
2395void SCCPSolver::trackValueOfGlobalVariable(GlobalVariable *GV) {
2396 Visitor->trackValueOfGlobalVariable(GV);
2397}
2398
2399void SCCPSolver::addTrackedFunction(Function *F) {
2400 Visitor->addTrackedFunction(F);
2401}
2402
2403void SCCPSolver::addToMustPreserveReturnsInFunctions(Function *F) {
2404 Visitor->addToMustPreserveReturnsInFunctions(F);
2405}
2406
2407bool SCCPSolver::mustPreserveReturn(Function *F) {
2408 return Visitor->mustPreserveReturn(F);
2409}
2410
2411void SCCPSolver::addArgumentTrackedFunction(Function *F) {
2412 Visitor->addArgumentTrackedFunction(F);
2413}
2414
2415bool SCCPSolver::isArgumentTrackedFunction(Function *F) {
2416 return Visitor->isArgumentTrackedFunction(F);
2417}
2418
2419const SmallPtrSetImpl<Function *> &
2420SCCPSolver::getArgumentTrackedFunctions() const {
2421 return Visitor->getArgumentTrackedFunctions();
2422}
2423
2424void SCCPSolver::solve() { Visitor->solve(); }
2425
2426bool SCCPSolver::resolvedUndefsIn(Function &F) {
2427 return Visitor->resolvedUndefsIn(F);
2428}
2429
2430void SCCPSolver::solveWhileResolvedUndefsIn(Module &M) {
2431 Visitor->solveWhileResolvedUndefsIn(M);
2432}
2433
2434void
2435SCCPSolver::solveWhileResolvedUndefsIn(SmallVectorImpl<Function *> &WorkList) {
2436 Visitor->solveWhileResolvedUndefsIn(WorkList);
2437}
2438
2439void SCCPSolver::solveWhileResolvedUndefs() {
2440 Visitor->solveWhileResolvedUndefs();
2441}
2442
2443bool SCCPSolver::isBlockExecutable(BasicBlock *BB) const {
2444 return Visitor->isBlockExecutable(BB);
2445}
2446
2447bool SCCPSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) const {
2448 return Visitor->isEdgeFeasible(From, To);
2449}
2450
2451std::vector<ValueLatticeElement>
2452SCCPSolver::getStructLatticeValueFor(Value *V) const {
2453 return Visitor->getStructLatticeValueFor(V);
2454}
2455
2456void SCCPSolver::removeLatticeValueFor(Value *V) {
2457 return Visitor->removeLatticeValueFor(V);
2458}
2459
2460void SCCPSolver::resetLatticeValueFor(CallBase *Call) {
2461 Visitor->resetLatticeValueFor(Call);
2462}
2463
2464const ValueLatticeElement &SCCPSolver::getLatticeValueFor(Value *V) const {
2465 return Visitor->getLatticeValueFor(V);
2466}
2467
2468const MapVector<Function *, ValueLatticeElement> &
2469SCCPSolver::getTrackedRetVals() const {
2470 return Visitor->getTrackedRetVals();
2471}
2472
2473const DenseMap<GlobalVariable *, ValueLatticeElement> &
2474SCCPSolver::getTrackedGlobals() const {
2475 return Visitor->getTrackedGlobals();
2476}
2477
2478const SmallPtrSet<Function *, 16> &SCCPSolver::getMRVFunctionsTracked() const {
2479 return Visitor->getMRVFunctionsTracked();
2480}
2481
2482void SCCPSolver::markOverdefined(Value *V) { Visitor->markOverdefined(V); }
2483
2484void SCCPSolver::trackValueOfArgument(Argument *V) {
2485 Visitor->trackValueOfArgument(A: V);
2486}
2487
2488bool SCCPSolver::isStructLatticeConstant(Function *F, StructType *STy) {
2489 return Visitor->isStructLatticeConstant(F, STy);
2490}
2491
2492Constant *SCCPSolver::getConstant(const ValueLatticeElement &LV,
2493 Type *Ty) const {
2494 return Visitor->getConstant(LV, Ty);
2495}
2496
2497Constant *SCCPSolver::getConstantOrNull(Value *V) const {
2498 return Visitor->getConstantOrNull(V);
2499}
2500
2501void SCCPSolver::setLatticeValueForSpecializationArguments(Function *F,
2502 const SmallVectorImpl<ArgInfo> &Args) {
2503 Visitor->setLatticeValueForSpecializationArguments(F, Args);
2504}
2505
2506void SCCPSolver::markFunctionUnreachable(Function *F) {
2507 Visitor->markFunctionUnreachable(F);
2508}
2509
2510void SCCPSolver::visit(Instruction *I) { Visitor->visit(I); }
2511
2512void SCCPSolver::visitCall(CallInst &I) { Visitor->visitCall(I); }
2513