LLVM 19.0.0git
CorrelatedValuePropagation.cpp
Go to the documentation of this file.
1//===- CorrelatedValuePropagation.cpp - Propagate CFG-derived info --------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file implements the Correlated Value Propagation pass.
10//
11//===----------------------------------------------------------------------===//
12
16#include "llvm/ADT/Statistic.h"
22#include "llvm/IR/Attributes.h"
23#include "llvm/IR/BasicBlock.h"
24#include "llvm/IR/CFG.h"
25#include "llvm/IR/Constant.h"
27#include "llvm/IR/Constants.h"
29#include "llvm/IR/Function.h"
30#include "llvm/IR/IRBuilder.h"
31#include "llvm/IR/InstrTypes.h"
32#include "llvm/IR/Instruction.h"
35#include "llvm/IR/Operator.h"
36#include "llvm/IR/PassManager.h"
37#include "llvm/IR/Type.h"
38#include "llvm/IR/Value.h"
42#include <cassert>
43#include <optional>
44#include <utility>
45
46using namespace llvm;
47
48#define DEBUG_TYPE "correlated-value-propagation"
49
50STATISTIC(NumPhis, "Number of phis propagated");
51STATISTIC(NumPhiCommon, "Number of phis deleted via common incoming value");
52STATISTIC(NumSelects, "Number of selects propagated");
53STATISTIC(NumCmps, "Number of comparisons propagated");
54STATISTIC(NumReturns, "Number of return values propagated");
55STATISTIC(NumDeadCases, "Number of switch cases removed");
56STATISTIC(NumSDivSRemsNarrowed,
57 "Number of sdivs/srems whose width was decreased");
58STATISTIC(NumSDivs, "Number of sdiv converted to udiv");
59STATISTIC(NumUDivURemsNarrowed,
60 "Number of udivs/urems whose width was decreased");
61STATISTIC(NumAShrsConverted, "Number of ashr converted to lshr");
62STATISTIC(NumAShrsRemoved, "Number of ashr removed");
63STATISTIC(NumSRems, "Number of srem converted to urem");
64STATISTIC(NumSExt, "Number of sext converted to zext");
65STATISTIC(NumSICmps, "Number of signed icmp preds simplified to unsigned");
66STATISTIC(NumAnd, "Number of ands removed");
67STATISTIC(NumNW, "Number of no-wrap deductions");
68STATISTIC(NumNSW, "Number of no-signed-wrap deductions");
69STATISTIC(NumNUW, "Number of no-unsigned-wrap deductions");
70STATISTIC(NumAddNW, "Number of no-wrap deductions for add");
71STATISTIC(NumAddNSW, "Number of no-signed-wrap deductions for add");
72STATISTIC(NumAddNUW, "Number of no-unsigned-wrap deductions for add");
73STATISTIC(NumSubNW, "Number of no-wrap deductions for sub");
74STATISTIC(NumSubNSW, "Number of no-signed-wrap deductions for sub");
75STATISTIC(NumSubNUW, "Number of no-unsigned-wrap deductions for sub");
76STATISTIC(NumMulNW, "Number of no-wrap deductions for mul");
77STATISTIC(NumMulNSW, "Number of no-signed-wrap deductions for mul");
78STATISTIC(NumMulNUW, "Number of no-unsigned-wrap deductions for mul");
79STATISTIC(NumShlNW, "Number of no-wrap deductions for shl");
80STATISTIC(NumShlNSW, "Number of no-signed-wrap deductions for shl");
81STATISTIC(NumShlNUW, "Number of no-unsigned-wrap deductions for shl");
82STATISTIC(NumAbs, "Number of llvm.abs intrinsics removed");
83STATISTIC(NumOverflows, "Number of overflow checks removed");
84STATISTIC(NumSaturating,
85 "Number of saturating arithmetics converted to normal arithmetics");
86STATISTIC(NumNonNull, "Number of function pointer arguments marked non-null");
87STATISTIC(NumMinMax, "Number of llvm.[us]{min,max} intrinsics removed");
88STATISTIC(NumSMinMax,
89 "Number of llvm.s{min,max} intrinsics simplified to unsigned");
90STATISTIC(NumUDivURemsNarrowedExpanded,
91 "Number of bound udiv's/urem's expanded");
92STATISTIC(NumZExt, "Number of non-negative deductions");
93
95 if (Constant *C = LVI->getConstant(V, At))
96 return C;
97
98 // TODO: The following really should be sunk inside LVI's core algorithm, or
99 // at least the outer shims around such.
100 auto *C = dyn_cast<CmpInst>(V);
101 if (!C)
102 return nullptr;
103
104 Value *Op0 = C->getOperand(0);
105 Constant *Op1 = dyn_cast<Constant>(C->getOperand(1));
106 if (!Op1)
107 return nullptr;
108
110 C->getPredicate(), Op0, Op1, At, /*UseBlockValue=*/false);
111 if (Result == LazyValueInfo::Unknown)
112 return nullptr;
113
114 return (Result == LazyValueInfo::True)
115 ? ConstantInt::getTrue(C->getContext())
116 : ConstantInt::getFalse(C->getContext());
117}
118
120 if (S->getType()->isVectorTy() || isa<Constant>(S->getCondition()))
121 return false;
122
123 bool Changed = false;
124 for (Use &U : make_early_inc_range(S->uses())) {
125 auto *I = cast<Instruction>(U.getUser());
126 Constant *C;
127 if (auto *PN = dyn_cast<PHINode>(I))
128 C = LVI->getConstantOnEdge(S->getCondition(), PN->getIncomingBlock(U),
129 I->getParent(), I);
130 else
131 C = getConstantAt(S->getCondition(), I, LVI);
132
133 auto *CI = dyn_cast_or_null<ConstantInt>(C);
134 if (!CI)
135 continue;
136
137 U.set(CI->isOne() ? S->getTrueValue() : S->getFalseValue());
138 Changed = true;
139 ++NumSelects;
140 }
141
142 if (Changed && S->use_empty())
143 S->eraseFromParent();
144
145 return Changed;
146}
147
148/// Try to simplify a phi with constant incoming values that match the edge
149/// values of a non-constant value on all other edges:
150/// bb0:
151/// %isnull = icmp eq i8* %x, null
152/// br i1 %isnull, label %bb2, label %bb1
153/// bb1:
154/// br label %bb2
155/// bb2:
156/// %r = phi i8* [ %x, %bb1 ], [ null, %bb0 ]
157/// -->
158/// %r = %x
160 DominatorTree *DT) {
161 // Collect incoming constants and initialize possible common value.
163 Value *CommonValue = nullptr;
164 for (unsigned i = 0, e = P->getNumIncomingValues(); i != e; ++i) {
165 Value *Incoming = P->getIncomingValue(i);
166 if (auto *IncomingConstant = dyn_cast<Constant>(Incoming)) {
167 IncomingConstants.push_back(std::make_pair(IncomingConstant, i));
168 } else if (!CommonValue) {
169 // The potential common value is initialized to the first non-constant.
170 CommonValue = Incoming;
171 } else if (Incoming != CommonValue) {
172 // There can be only one non-constant common value.
173 return false;
174 }
175 }
176
177 if (!CommonValue || IncomingConstants.empty())
178 return false;
179
180 // The common value must be valid in all incoming blocks.
181 BasicBlock *ToBB = P->getParent();
182 if (auto *CommonInst = dyn_cast<Instruction>(CommonValue))
183 if (!DT->dominates(CommonInst, ToBB))
184 return false;
185
186 // We have a phi with exactly 1 variable incoming value and 1 or more constant
187 // incoming values. See if all constant incoming values can be mapped back to
188 // the same incoming variable value.
189 for (auto &IncomingConstant : IncomingConstants) {
190 Constant *C = IncomingConstant.first;
191 BasicBlock *IncomingBB = P->getIncomingBlock(IncomingConstant.second);
192 if (C != LVI->getConstantOnEdge(CommonValue, IncomingBB, ToBB, P))
193 return false;
194 }
195
196 // LVI only guarantees that the value matches a certain constant if the value
197 // is not poison. Make sure we don't replace a well-defined value with poison.
198 // This is usually satisfied due to a prior branch on the value.
199 if (!isGuaranteedNotToBePoison(CommonValue, nullptr, P, DT))
200 return false;
201
202 // All constant incoming values map to the same variable along the incoming
203 // edges of the phi. The phi is unnecessary.
204 P->replaceAllUsesWith(CommonValue);
205 P->eraseFromParent();
206 ++NumPhiCommon;
207 return true;
208}
209
212 Instruction *CxtI) {
213 if (Constant *C = LVI->getConstantOnEdge(Incoming, From, To, CxtI))
214 return C;
215
216 // Look if the incoming value is a select with a scalar condition for which
217 // LVI can tells us the value. In that case replace the incoming value with
218 // the appropriate value of the select. This often allows us to remove the
219 // select later.
220 auto *SI = dyn_cast<SelectInst>(Incoming);
221 if (!SI)
222 return nullptr;
223
224 // Once LVI learns to handle vector types, we could also add support
225 // for vector type constants that are not all zeroes or all ones.
226 Value *Condition = SI->getCondition();
227 if (!Condition->getType()->isVectorTy()) {
228 if (Constant *C = LVI->getConstantOnEdge(Condition, From, To, CxtI)) {
229 if (C->isOneValue())
230 return SI->getTrueValue();
231 if (C->isZeroValue())
232 return SI->getFalseValue();
233 }
234 }
235
236 // Look if the select has a constant but LVI tells us that the incoming
237 // value can never be that constant. In that case replace the incoming
238 // value with the other value of the select. This often allows us to
239 // remove the select later.
240
241 // The "false" case
242 if (auto *C = dyn_cast<Constant>(SI->getFalseValue()))
243 if (LVI->getPredicateOnEdge(ICmpInst::ICMP_EQ, SI, C, From, To, CxtI) ==
245 return SI->getTrueValue();
246
247 // The "true" case,
248 // similar to the select "false" case, but try the select "true" value
249 if (auto *C = dyn_cast<Constant>(SI->getTrueValue()))
250 if (LVI->getPredicateOnEdge(ICmpInst::ICMP_EQ, SI, C, From, To, CxtI) ==
252 return SI->getFalseValue();
253
254 return nullptr;
255}
256
258 const SimplifyQuery &SQ) {
259 bool Changed = false;
260
261 BasicBlock *BB = P->getParent();
262 for (unsigned i = 0, e = P->getNumIncomingValues(); i < e; ++i) {
263 Value *Incoming = P->getIncomingValue(i);
264 if (isa<Constant>(Incoming)) continue;
265
266 Value *V = getValueOnEdge(LVI, Incoming, P->getIncomingBlock(i), BB, P);
267 if (V) {
268 P->setIncomingValue(i, V);
269 Changed = true;
270 }
271 }
272
273 if (Value *V = simplifyInstruction(P, SQ)) {
274 P->replaceAllUsesWith(V);
275 P->eraseFromParent();
276 Changed = true;
277 }
278
279 if (!Changed)
280 Changed = simplifyCommonValuePhi(P, LVI, DT);
281
282 if (Changed)
283 ++NumPhis;
284
285 return Changed;
286}
287
288static bool processICmp(ICmpInst *Cmp, LazyValueInfo *LVI) {
289 // Only for signed relational comparisons of scalar integers.
290 if (Cmp->getType()->isVectorTy() ||
291 !Cmp->getOperand(0)->getType()->isIntegerTy())
292 return false;
293
294 if (!Cmp->isSigned())
295 return false;
296
297 ICmpInst::Predicate UnsignedPred =
299 Cmp->getPredicate(),
300 LVI->getConstantRangeAtUse(Cmp->getOperandUse(0),
301 /*UndefAllowed*/ true),
302 LVI->getConstantRangeAtUse(Cmp->getOperandUse(1),
303 /*UndefAllowed*/ true));
304
305 if (UnsignedPred == ICmpInst::Predicate::BAD_ICMP_PREDICATE)
306 return false;
307
308 ++NumSICmps;
309 Cmp->setPredicate(UnsignedPred);
310
311 return true;
312}
313
314/// See if LazyValueInfo's ability to exploit edge conditions or range
315/// information is sufficient to prove this comparison. Even for local
316/// conditions, this can sometimes prove conditions instcombine can't by
317/// exploiting range information.
318static bool constantFoldCmp(CmpInst *Cmp, LazyValueInfo *LVI) {
319 Value *Op0 = Cmp->getOperand(0);
320 Value *Op1 = Cmp->getOperand(1);
322 LVI->getPredicateAt(Cmp->getPredicate(), Op0, Op1, Cmp,
323 /*UseBlockValue=*/true);
324 if (Result == LazyValueInfo::Unknown)
325 return false;
326
327 ++NumCmps;
328 Constant *TorF =
329 ConstantInt::get(CmpInst::makeCmpResultType(Op0->getType()), Result);
330 Cmp->replaceAllUsesWith(TorF);
331 Cmp->eraseFromParent();
332 return true;
333}
334
335static bool processCmp(CmpInst *Cmp, LazyValueInfo *LVI) {
336 if (constantFoldCmp(Cmp, LVI))
337 return true;
338
339 if (auto *ICmp = dyn_cast<ICmpInst>(Cmp))
340 if (processICmp(ICmp, LVI))
341 return true;
342
343 return false;
344}
345
346/// Simplify a switch instruction by removing cases which can never fire. If the
347/// uselessness of a case could be determined locally then constant propagation
348/// would already have figured it out. Instead, walk the predecessors and
349/// statically evaluate cases based on information available on that edge. Cases
350/// that cannot fire no matter what the incoming edge can safely be removed. If
351/// a case fires on every incoming edge then the entire switch can be removed
352/// and replaced with a branch to the case destination.
354 DominatorTree *DT) {
355 DomTreeUpdater DTU(*DT, DomTreeUpdater::UpdateStrategy::Lazy);
356 Value *Cond = I->getCondition();
357 BasicBlock *BB = I->getParent();
358
359 // Analyse each switch case in turn.
360 bool Changed = false;
361 DenseMap<BasicBlock*, int> SuccessorsCount;
362 for (auto *Succ : successors(BB))
363 SuccessorsCount[Succ]++;
364
365 { // Scope for SwitchInstProfUpdateWrapper. It must not live during
366 // ConstantFoldTerminator() as the underlying SwitchInst can be changed.
368
369 for (auto CI = SI->case_begin(), CE = SI->case_end(); CI != CE;) {
370 ConstantInt *Case = CI->getCaseValue();
373 /* UseBlockValue */ true);
374
375 if (State == LazyValueInfo::False) {
376 // This case never fires - remove it.
377 BasicBlock *Succ = CI->getCaseSuccessor();
378 Succ->removePredecessor(BB);
379 CI = SI.removeCase(CI);
380 CE = SI->case_end();
381
382 // The condition can be modified by removePredecessor's PHI simplification
383 // logic.
384 Cond = SI->getCondition();
385
386 ++NumDeadCases;
387 Changed = true;
388 if (--SuccessorsCount[Succ] == 0)
389 DTU.applyUpdatesPermissive({{DominatorTree::Delete, BB, Succ}});
390 continue;
391 }
392 if (State == LazyValueInfo::True) {
393 // This case always fires. Arrange for the switch to be turned into an
394 // unconditional branch by replacing the switch condition with the case
395 // value.
396 SI->setCondition(Case);
397 NumDeadCases += SI->getNumCases();
398 Changed = true;
399 break;
400 }
401
402 // Increment the case iterator since we didn't delete it.
403 ++CI;
404 }
405 }
406
407 if (Changed)
408 // If the switch has been simplified to the point where it can be replaced
409 // by a branch then do so now.
410 ConstantFoldTerminator(BB, /*DeleteDeadConditions = */ false,
411 /*TLI = */ nullptr, &DTU);
412 return Changed;
413}
414
415// See if we can prove that the given binary op intrinsic will not overflow.
417 ConstantRange LRange =
418 LVI->getConstantRangeAtUse(BO->getOperandUse(0), /*UndefAllowed*/ false);
419 ConstantRange RRange =
420 LVI->getConstantRangeAtUse(BO->getOperandUse(1), /*UndefAllowed*/ false);
422 BO->getBinaryOp(), RRange, BO->getNoWrapKind());
423 return NWRegion.contains(LRange);
424}
425
427 bool NewNSW, bool NewNUW) {
428 Statistic *OpcNW, *OpcNSW, *OpcNUW;
429 switch (Opcode) {
430 case Instruction::Add:
431 OpcNW = &NumAddNW;
432 OpcNSW = &NumAddNSW;
433 OpcNUW = &NumAddNUW;
434 break;
435 case Instruction::Sub:
436 OpcNW = &NumSubNW;
437 OpcNSW = &NumSubNSW;
438 OpcNUW = &NumSubNUW;
439 break;
440 case Instruction::Mul:
441 OpcNW = &NumMulNW;
442 OpcNSW = &NumMulNSW;
443 OpcNUW = &NumMulNUW;
444 break;
445 case Instruction::Shl:
446 OpcNW = &NumShlNW;
447 OpcNSW = &NumShlNSW;
448 OpcNUW = &NumShlNUW;
449 break;
450 default:
451 llvm_unreachable("Will not be called with other binops");
452 }
453
454 auto *Inst = dyn_cast<Instruction>(V);
455 if (NewNSW) {
456 ++NumNW;
457 ++*OpcNW;
458 ++NumNSW;
459 ++*OpcNSW;
460 if (Inst)
461 Inst->setHasNoSignedWrap();
462 }
463 if (NewNUW) {
464 ++NumNW;
465 ++*OpcNW;
466 ++NumNUW;
467 ++*OpcNUW;
468 if (Inst)
469 Inst->setHasNoUnsignedWrap();
470 }
471}
472
473static bool processBinOp(BinaryOperator *BinOp, LazyValueInfo *LVI);
474
475// See if @llvm.abs argument is alays positive/negative, and simplify.
476// Notably, INT_MIN can belong to either range, regardless of the NSW,
477// because it is negation-invariant.
479 Value *X = II->getArgOperand(0);
480 Type *Ty = X->getType();
481 if (!Ty->isIntegerTy())
482 return false;
483
484 bool IsIntMinPoison = cast<ConstantInt>(II->getArgOperand(1))->isOne();
487 II->getOperandUse(0), /*UndefAllowed*/ IsIntMinPoison);
488
489 // Is X in [0, IntMin]? NOTE: INT_MIN is fine!
490 if (Range.icmp(CmpInst::ICMP_ULE, IntMin)) {
491 ++NumAbs;
493 II->eraseFromParent();
494 return true;
495 }
496
497 // Is X in [IntMin, 0]? NOTE: INT_MIN is fine!
498 if (Range.getSignedMax().isNonPositive()) {
499 IRBuilder<> B(II);
500 Value *NegX = B.CreateNeg(X, II->getName(), /*HasNUW=*/false,
501 /*HasNSW=*/IsIntMinPoison);
502 ++NumAbs;
503 II->replaceAllUsesWith(NegX);
504 II->eraseFromParent();
505
506 // See if we can infer some no-wrap flags.
507 if (auto *BO = dyn_cast<BinaryOperator>(NegX))
508 processBinOp(BO, LVI);
509
510 return true;
511 }
512
513 // Argument's range crosses zero.
514 // Can we at least tell that the argument is never INT_MIN?
515 if (!IsIntMinPoison && !Range.contains(IntMin)) {
516 ++NumNSW;
517 ++NumSubNSW;
519 return true;
520 }
521 return false;
522}
523
524// See if this min/max intrinsic always picks it's one specific operand.
525// If not, check whether we can canonicalize signed minmax into unsigned version
529 /*UndefAllowed*/ false);
531 /*UndefAllowed*/ false);
532 if (LHS_CR.icmp(Pred, RHS_CR)) {
533 ++NumMinMax;
534 MM->replaceAllUsesWith(MM->getLHS());
535 MM->eraseFromParent();
536 return true;
537 }
538 if (RHS_CR.icmp(Pred, LHS_CR)) {
539 ++NumMinMax;
540 MM->replaceAllUsesWith(MM->getRHS());
541 MM->eraseFromParent();
542 return true;
543 }
544
545 if (MM->isSigned() &&
547 RHS_CR)) {
548 ++NumSMinMax;
549 IRBuilder<> B(MM);
550 MM->replaceAllUsesWith(B.CreateBinaryIntrinsic(
551 MM->getIntrinsicID() == Intrinsic::smin ? Intrinsic::umin
552 : Intrinsic::umax,
553 MM->getLHS(), MM->getRHS()));
554 MM->eraseFromParent();
555 return true;
556 }
557
558 return false;
559}
560
561// Rewrite this with.overflow intrinsic as non-overflowing.
563 IRBuilder<> B(WO);
564 Instruction::BinaryOps Opcode = WO->getBinaryOp();
565 bool NSW = WO->isSigned();
566 bool NUW = !WO->isSigned();
567
568 Value *NewOp =
569 B.CreateBinOp(Opcode, WO->getLHS(), WO->getRHS(), WO->getName());
570 setDeducedOverflowingFlags(NewOp, Opcode, NSW, NUW);
571
572 StructType *ST = cast<StructType>(WO->getType());
574 { PoisonValue::get(ST->getElementType(0)),
575 ConstantInt::getFalse(ST->getElementType(1)) });
576 Value *NewI = B.CreateInsertValue(Struct, NewOp, 0);
577 WO->replaceAllUsesWith(NewI);
578 WO->eraseFromParent();
579 ++NumOverflows;
580
581 // See if we can infer the other no-wrap too.
582 if (auto *BO = dyn_cast<BinaryOperator>(NewOp))
583 processBinOp(BO, LVI);
584
585 return true;
586}
587
589 Instruction::BinaryOps Opcode = SI->getBinaryOp();
590 bool NSW = SI->isSigned();
591 bool NUW = !SI->isSigned();
593 Opcode, SI->getLHS(), SI->getRHS(), SI->getName(), SI->getIterator());
594 BinOp->setDebugLoc(SI->getDebugLoc());
595 setDeducedOverflowingFlags(BinOp, Opcode, NSW, NUW);
596
597 SI->replaceAllUsesWith(BinOp);
598 SI->eraseFromParent();
599 ++NumSaturating;
600
601 // See if we can infer the other no-wrap too.
602 if (auto *BO = dyn_cast<BinaryOperator>(BinOp))
603 processBinOp(BO, LVI);
604
605 return true;
606}
607
608/// Infer nonnull attributes for the arguments at the specified callsite.
609static bool processCallSite(CallBase &CB, LazyValueInfo *LVI) {
610
611 if (CB.getIntrinsicID() == Intrinsic::abs) {
612 return processAbsIntrinsic(&cast<IntrinsicInst>(CB), LVI);
613 }
614
615 if (auto *MM = dyn_cast<MinMaxIntrinsic>(&CB)) {
616 return processMinMaxIntrinsic(MM, LVI);
617 }
618
619 if (auto *WO = dyn_cast<WithOverflowInst>(&CB)) {
620 if (WO->getLHS()->getType()->isIntegerTy() && willNotOverflow(WO, LVI)) {
621 return processOverflowIntrinsic(WO, LVI);
622 }
623 }
624
625 if (auto *SI = dyn_cast<SaturatingInst>(&CB)) {
626 if (SI->getType()->isIntegerTy() && willNotOverflow(SI, LVI)) {
627 return processSaturatingInst(SI, LVI);
628 }
629 }
630
631 bool Changed = false;
632
633 // Deopt bundle operands are intended to capture state with minimal
634 // perturbance of the code otherwise. If we can find a constant value for
635 // any such operand and remove a use of the original value, that's
636 // desireable since it may allow further optimization of that value (e.g. via
637 // single use rules in instcombine). Since deopt uses tend to,
638 // idiomatically, appear along rare conditional paths, it's reasonable likely
639 // we may have a conditional fact with which LVI can fold.
640 if (auto DeoptBundle = CB.getOperandBundle(LLVMContext::OB_deopt)) {
641 for (const Use &ConstU : DeoptBundle->Inputs) {
642 Use &U = const_cast<Use&>(ConstU);
643 Value *V = U.get();
644 if (V->getType()->isVectorTy()) continue;
645 if (isa<Constant>(V)) continue;
646
647 Constant *C = LVI->getConstant(V, &CB);
648 if (!C) continue;
649 U.set(C);
650 Changed = true;
651 }
652 }
653
655 unsigned ArgNo = 0;
656
657 for (Value *V : CB.args()) {
658 PointerType *Type = dyn_cast<PointerType>(V->getType());
659 // Try to mark pointer typed parameters as non-null. We skip the
660 // relatively expensive analysis for constants which are obviously either
661 // null or non-null to start with.
662 if (Type && !CB.paramHasAttr(ArgNo, Attribute::NonNull) &&
663 !isa<Constant>(V) &&
664 LVI->getPredicateAt(ICmpInst::ICMP_EQ, V,
666 /*UseBlockValue=*/false) == LazyValueInfo::False)
667 ArgNos.push_back(ArgNo);
668 ArgNo++;
669 }
670
671 assert(ArgNo == CB.arg_size() && "Call arguments not processed correctly.");
672
673 if (ArgNos.empty())
674 return Changed;
675
676 NumNonNull += ArgNos.size();
678 LLVMContext &Ctx = CB.getContext();
679 AS = AS.addParamAttribute(Ctx, ArgNos,
680 Attribute::get(Ctx, Attribute::NonNull));
681 CB.setAttributes(AS);
682
683 return true;
684}
685
687
688static Domain getDomain(const ConstantRange &CR) {
689 if (CR.isAllNonNegative())
690 return Domain::NonNegative;
691 if (CR.icmp(ICmpInst::ICMP_SLE, APInt::getZero(CR.getBitWidth())))
692 return Domain::NonPositive;
693 return Domain::Unknown;
694}
695
696/// Try to shrink a sdiv/srem's width down to the smallest power of two that's
697/// sufficient to contain its operands.
698static bool narrowSDivOrSRem(BinaryOperator *Instr, const ConstantRange &LCR,
699 const ConstantRange &RCR) {
700 assert(Instr->getOpcode() == Instruction::SDiv ||
701 Instr->getOpcode() == Instruction::SRem);
702 assert(!Instr->getType()->isVectorTy());
703
704 // Find the smallest power of two bitwidth that's sufficient to hold Instr's
705 // operands.
706 unsigned OrigWidth = Instr->getType()->getIntegerBitWidth();
707
708 // What is the smallest bit width that can accommodate the entire value ranges
709 // of both of the operands?
710 unsigned MinSignedBits =
711 std::max(LCR.getMinSignedBits(), RCR.getMinSignedBits());
712
713 // sdiv/srem is UB if divisor is -1 and divident is INT_MIN, so unless we can
714 // prove that such a combination is impossible, we need to bump the bitwidth.
715 if (RCR.contains(APInt::getAllOnes(OrigWidth)) &&
716 LCR.contains(APInt::getSignedMinValue(MinSignedBits).sext(OrigWidth)))
717 ++MinSignedBits;
718
719 // Don't shrink below 8 bits wide.
720 unsigned NewWidth = std::max<unsigned>(PowerOf2Ceil(MinSignedBits), 8);
721
722 // NewWidth might be greater than OrigWidth if OrigWidth is not a power of
723 // two.
724 if (NewWidth >= OrigWidth)
725 return false;
726
727 ++NumSDivSRemsNarrowed;
728 IRBuilder<> B{Instr};
729 auto *TruncTy = Type::getIntNTy(Instr->getContext(), NewWidth);
730 auto *LHS = B.CreateTruncOrBitCast(Instr->getOperand(0), TruncTy,
731 Instr->getName() + ".lhs.trunc");
732 auto *RHS = B.CreateTruncOrBitCast(Instr->getOperand(1), TruncTy,
733 Instr->getName() + ".rhs.trunc");
734 auto *BO = B.CreateBinOp(Instr->getOpcode(), LHS, RHS, Instr->getName());
735 auto *Sext = B.CreateSExt(BO, Instr->getType(), Instr->getName() + ".sext");
736 if (auto *BinOp = dyn_cast<BinaryOperator>(BO))
737 if (BinOp->getOpcode() == Instruction::SDiv)
738 BinOp->setIsExact(Instr->isExact());
739
740 Instr->replaceAllUsesWith(Sext);
741 Instr->eraseFromParent();
742 return true;
743}
744
745static bool expandUDivOrURem(BinaryOperator *Instr, const ConstantRange &XCR,
746 const ConstantRange &YCR) {
747 Type *Ty = Instr->getType();
748 assert(Instr->getOpcode() == Instruction::UDiv ||
749 Instr->getOpcode() == Instruction::URem);
750 assert(!Ty->isVectorTy());
751 bool IsRem = Instr->getOpcode() == Instruction::URem;
752
753 Value *X = Instr->getOperand(0);
754 Value *Y = Instr->getOperand(1);
755
756 // X u/ Y -> 0 iff X u< Y
757 // X u% Y -> X iff X u< Y
758 if (XCR.icmp(ICmpInst::ICMP_ULT, YCR)) {
759 Instr->replaceAllUsesWith(IsRem ? X : Constant::getNullValue(Ty));
760 Instr->eraseFromParent();
761 ++NumUDivURemsNarrowedExpanded;
762 return true;
763 }
764
765 // Given
766 // R = X u% Y
767 // We can represent the modulo operation as a loop/self-recursion:
768 // urem_rec(X, Y):
769 // Z = X - Y
770 // if X u< Y
771 // ret X
772 // else
773 // ret urem_rec(Z, Y)
774 // which isn't better, but if we only need a single iteration
775 // to compute the answer, this becomes quite good:
776 // R = X < Y ? X : X - Y iff X u< 2*Y (w/ unsigned saturation)
777 // Now, we do not care about all full multiples of Y in X, they do not change
778 // the answer, thus we could rewrite the expression as:
779 // X* = X - (Y * |_ X / Y _|)
780 // R = X* % Y
781 // so we don't need the *first* iteration to return, we just need to
782 // know *which* iteration will always return, so we could also rewrite it as:
783 // X* = X - (Y * |_ X / Y _|)
784 // R = X* % Y iff X* u< 2*Y (w/ unsigned saturation)
785 // but that does not seem profitable here.
786
787 // Even if we don't know X's range, the divisor may be so large, X can't ever
788 // be 2x larger than that. I.e. if divisor is always negative.
789 if (!XCR.icmp(ICmpInst::ICMP_ULT,
790 YCR.umul_sat(APInt(YCR.getBitWidth(), 2))) &&
791 !YCR.isAllNegative())
792 return false;
793
794 IRBuilder<> B(Instr);
795 Value *ExpandedOp;
796 if (XCR.icmp(ICmpInst::ICMP_UGE, YCR)) {
797 // If X is between Y and 2*Y the result is known.
798 if (IsRem)
799 ExpandedOp = B.CreateNUWSub(X, Y);
800 else
801 ExpandedOp = ConstantInt::get(Instr->getType(), 1);
802 } else if (IsRem) {
803 // NOTE: this transformation introduces two uses of X,
804 // but it may be undef so we must freeze it first.
805 Value *FrozenX = X;
807 FrozenX = B.CreateFreeze(X, X->getName() + ".frozen");
808 Value *FrozenY = Y;
810 FrozenY = B.CreateFreeze(Y, Y->getName() + ".frozen");
811 auto *AdjX = B.CreateNUWSub(FrozenX, FrozenY, Instr->getName() + ".urem");
812 auto *Cmp = B.CreateICmp(ICmpInst::ICMP_ULT, FrozenX, FrozenY,
813 Instr->getName() + ".cmp");
814 ExpandedOp = B.CreateSelect(Cmp, FrozenX, AdjX);
815 } else {
816 auto *Cmp =
817 B.CreateICmp(ICmpInst::ICMP_UGE, X, Y, Instr->getName() + ".cmp");
818 ExpandedOp = B.CreateZExt(Cmp, Ty, Instr->getName() + ".udiv");
819 }
820 ExpandedOp->takeName(Instr);
821 Instr->replaceAllUsesWith(ExpandedOp);
822 Instr->eraseFromParent();
823 ++NumUDivURemsNarrowedExpanded;
824 return true;
825}
826
827/// Try to shrink a udiv/urem's width down to the smallest power of two that's
828/// sufficient to contain its operands.
829static bool narrowUDivOrURem(BinaryOperator *Instr, const ConstantRange &XCR,
830 const ConstantRange &YCR) {
831 assert(Instr->getOpcode() == Instruction::UDiv ||
832 Instr->getOpcode() == Instruction::URem);
833 assert(!Instr->getType()->isVectorTy());
834
835 // Find the smallest power of two bitwidth that's sufficient to hold Instr's
836 // operands.
837
838 // What is the smallest bit width that can accommodate the entire value ranges
839 // of both of the operands?
840 unsigned MaxActiveBits = std::max(XCR.getActiveBits(), YCR.getActiveBits());
841 // Don't shrink below 8 bits wide.
842 unsigned NewWidth = std::max<unsigned>(PowerOf2Ceil(MaxActiveBits), 8);
843
844 // NewWidth might be greater than OrigWidth if OrigWidth is not a power of
845 // two.
846 if (NewWidth >= Instr->getType()->getIntegerBitWidth())
847 return false;
848
849 ++NumUDivURemsNarrowed;
850 IRBuilder<> B{Instr};
851 auto *TruncTy = Type::getIntNTy(Instr->getContext(), NewWidth);
852 auto *LHS = B.CreateTruncOrBitCast(Instr->getOperand(0), TruncTy,
853 Instr->getName() + ".lhs.trunc");
854 auto *RHS = B.CreateTruncOrBitCast(Instr->getOperand(1), TruncTy,
855 Instr->getName() + ".rhs.trunc");
856 auto *BO = B.CreateBinOp(Instr->getOpcode(), LHS, RHS, Instr->getName());
857 auto *Zext = B.CreateZExt(BO, Instr->getType(), Instr->getName() + ".zext");
858 if (auto *BinOp = dyn_cast<BinaryOperator>(BO))
859 if (BinOp->getOpcode() == Instruction::UDiv)
860 BinOp->setIsExact(Instr->isExact());
861
862 Instr->replaceAllUsesWith(Zext);
863 Instr->eraseFromParent();
864 return true;
865}
866
868 assert(Instr->getOpcode() == Instruction::UDiv ||
869 Instr->getOpcode() == Instruction::URem);
870 if (Instr->getType()->isVectorTy())
871 return false;
872
873 ConstantRange XCR = LVI->getConstantRangeAtUse(Instr->getOperandUse(0),
874 /*UndefAllowed*/ false);
875 // Allow undef for RHS, as we can assume it is division by zero UB.
876 ConstantRange YCR = LVI->getConstantRangeAtUse(Instr->getOperandUse(1),
877 /*UndefAllowed*/ true);
878 if (expandUDivOrURem(Instr, XCR, YCR))
879 return true;
880
881 return narrowUDivOrURem(Instr, XCR, YCR);
882}
883
884static bool processSRem(BinaryOperator *SDI, const ConstantRange &LCR,
885 const ConstantRange &RCR, LazyValueInfo *LVI) {
886 assert(SDI->getOpcode() == Instruction::SRem);
887 assert(!SDI->getType()->isVectorTy());
888
889 if (LCR.abs().icmp(CmpInst::ICMP_ULT, RCR.abs())) {
890 SDI->replaceAllUsesWith(SDI->getOperand(0));
891 SDI->eraseFromParent();
892 return true;
893 }
894
895 struct Operand {
896 Value *V;
897 Domain D;
898 };
899 std::array<Operand, 2> Ops = {{{SDI->getOperand(0), getDomain(LCR)},
900 {SDI->getOperand(1), getDomain(RCR)}}};
901 if (Ops[0].D == Domain::Unknown || Ops[1].D == Domain::Unknown)
902 return false;
903
904 // We know domains of both of the operands!
905 ++NumSRems;
906
907 // We need operands to be non-negative, so negate each one that isn't.
908 for (Operand &Op : Ops) {
909 if (Op.D == Domain::NonNegative)
910 continue;
911 auto *BO = BinaryOperator::CreateNeg(Op.V, Op.V->getName() + ".nonneg",
912 SDI->getIterator());
913 BO->setDebugLoc(SDI->getDebugLoc());
914 Op.V = BO;
915 }
916
917 auto *URem = BinaryOperator::CreateURem(Ops[0].V, Ops[1].V, SDI->getName(),
918 SDI->getIterator());
919 URem->setDebugLoc(SDI->getDebugLoc());
920
921 auto *Res = URem;
922
923 // If the divident was non-positive, we need to negate the result.
924 if (Ops[0].D == Domain::NonPositive) {
925 Res = BinaryOperator::CreateNeg(Res, Res->getName() + ".neg",
926 SDI->getIterator());
927 Res->setDebugLoc(SDI->getDebugLoc());
928 }
929
930 SDI->replaceAllUsesWith(Res);
931 SDI->eraseFromParent();
932
933 // Try to simplify our new urem.
934 processUDivOrURem(URem, LVI);
935
936 return true;
937}
938
939/// See if LazyValueInfo's ability to exploit edge conditions or range
940/// information is sufficient to prove the signs of both operands of this SDiv.
941/// If this is the case, replace the SDiv with a UDiv. Even for local
942/// conditions, this can sometimes prove conditions instcombine can't by
943/// exploiting range information.
944static bool processSDiv(BinaryOperator *SDI, const ConstantRange &LCR,
945 const ConstantRange &RCR, LazyValueInfo *LVI) {
946 assert(SDI->getOpcode() == Instruction::SDiv);
947 assert(!SDI->getType()->isVectorTy());
948
949 // Check whether the division folds to a constant.
950 ConstantRange DivCR = LCR.sdiv(RCR);
951 if (const APInt *Elem = DivCR.getSingleElement()) {
952 SDI->replaceAllUsesWith(ConstantInt::get(SDI->getType(), *Elem));
953 SDI->eraseFromParent();
954 return true;
955 }
956
957 struct Operand {
958 Value *V;
959 Domain D;
960 };
961 std::array<Operand, 2> Ops = {{{SDI->getOperand(0), getDomain(LCR)},
962 {SDI->getOperand(1), getDomain(RCR)}}};
963 if (Ops[0].D == Domain::Unknown || Ops[1].D == Domain::Unknown)
964 return false;
965
966 // We know domains of both of the operands!
967 ++NumSDivs;
968
969 // We need operands to be non-negative, so negate each one that isn't.
970 for (Operand &Op : Ops) {
971 if (Op.D == Domain::NonNegative)
972 continue;
973 auto *BO = BinaryOperator::CreateNeg(Op.V, Op.V->getName() + ".nonneg",
974 SDI->getIterator());
975 BO->setDebugLoc(SDI->getDebugLoc());
976 Op.V = BO;
977 }
978
979 auto *UDiv = BinaryOperator::CreateUDiv(Ops[0].V, Ops[1].V, SDI->getName(),
980 SDI->getIterator());
981 UDiv->setDebugLoc(SDI->getDebugLoc());
982 UDiv->setIsExact(SDI->isExact());
983
984 auto *Res = UDiv;
985
986 // If the operands had two different domains, we need to negate the result.
987 if (Ops[0].D != Ops[1].D) {
988 Res = BinaryOperator::CreateNeg(Res, Res->getName() + ".neg",
989 SDI->getIterator());
990 Res->setDebugLoc(SDI->getDebugLoc());
991 }
992
993 SDI->replaceAllUsesWith(Res);
994 SDI->eraseFromParent();
995
996 // Try to simplify our new udiv.
997 processUDivOrURem(UDiv, LVI);
998
999 return true;
1000}
1001
1003 assert(Instr->getOpcode() == Instruction::SDiv ||
1004 Instr->getOpcode() == Instruction::SRem);
1005 if (Instr->getType()->isVectorTy())
1006 return false;
1007
1008 ConstantRange LCR =
1009 LVI->getConstantRangeAtUse(Instr->getOperandUse(0), /*AllowUndef*/ false);
1010 // Allow undef for RHS, as we can assume it is division by zero UB.
1011 ConstantRange RCR =
1012 LVI->getConstantRangeAtUse(Instr->getOperandUse(1), /*AlloweUndef*/ true);
1013 if (Instr->getOpcode() == Instruction::SDiv)
1014 if (processSDiv(Instr, LCR, RCR, LVI))
1015 return true;
1016
1017 if (Instr->getOpcode() == Instruction::SRem) {
1018 if (processSRem(Instr, LCR, RCR, LVI))
1019 return true;
1020 }
1021
1022 return narrowSDivOrSRem(Instr, LCR, RCR);
1023}
1024
1026 if (SDI->getType()->isVectorTy())
1027 return false;
1028
1029 ConstantRange LRange =
1030 LVI->getConstantRangeAtUse(SDI->getOperandUse(0), /*UndefAllowed*/ false);
1031 unsigned OrigWidth = SDI->getType()->getIntegerBitWidth();
1032 ConstantRange NegOneOrZero =
1033 ConstantRange(APInt(OrigWidth, (uint64_t)-1, true), APInt(OrigWidth, 1));
1034 if (NegOneOrZero.contains(LRange)) {
1035 // ashr of -1 or 0 never changes the value, so drop the whole instruction
1036 ++NumAShrsRemoved;
1037 SDI->replaceAllUsesWith(SDI->getOperand(0));
1038 SDI->eraseFromParent();
1039 return true;
1040 }
1041
1042 if (!LRange.isAllNonNegative())
1043 return false;
1044
1045 ++NumAShrsConverted;
1046 auto *BO = BinaryOperator::CreateLShr(SDI->getOperand(0), SDI->getOperand(1),
1047 "", SDI->getIterator());
1048 BO->takeName(SDI);
1049 BO->setDebugLoc(SDI->getDebugLoc());
1050 BO->setIsExact(SDI->isExact());
1051 SDI->replaceAllUsesWith(BO);
1052 SDI->eraseFromParent();
1053
1054 return true;
1055}
1056
1057static bool processSExt(SExtInst *SDI, LazyValueInfo *LVI) {
1058 if (SDI->getType()->isVectorTy())
1059 return false;
1060
1061 const Use &Base = SDI->getOperandUse(0);
1062 if (!LVI->getConstantRangeAtUse(Base, /*UndefAllowed*/ false)
1064 return false;
1065
1066 ++NumSExt;
1067 auto *ZExt = CastInst::CreateZExtOrBitCast(Base, SDI->getType(), "",
1068 SDI->getIterator());
1069 ZExt->takeName(SDI);
1070 ZExt->setDebugLoc(SDI->getDebugLoc());
1071 ZExt->setNonNeg();
1072 SDI->replaceAllUsesWith(ZExt);
1073 SDI->eraseFromParent();
1074
1075 return true;
1076}
1077
1078static bool processZExt(ZExtInst *ZExt, LazyValueInfo *LVI) {
1079 if (ZExt->getType()->isVectorTy())
1080 return false;
1081
1082 if (ZExt->hasNonNeg())
1083 return false;
1084
1085 const Use &Base = ZExt->getOperandUse(0);
1086 if (!LVI->getConstantRangeAtUse(Base, /*UndefAllowed*/ false)
1088 return false;
1089
1090 ++NumZExt;
1091 ZExt->setNonNeg();
1092
1093 return true;
1094}
1095
1096static bool processBinOp(BinaryOperator *BinOp, LazyValueInfo *LVI) {
1097 using OBO = OverflowingBinaryOperator;
1098
1099 if (BinOp->getType()->isVectorTy())
1100 return false;
1101
1102 bool NSW = BinOp->hasNoSignedWrap();
1103 bool NUW = BinOp->hasNoUnsignedWrap();
1104 if (NSW && NUW)
1105 return false;
1106
1107 Instruction::BinaryOps Opcode = BinOp->getOpcode();
1108 Value *LHS = BinOp->getOperand(0);
1109 Value *RHS = BinOp->getOperand(1);
1110
1111 ConstantRange LRange =
1112 LVI->getConstantRange(LHS, BinOp, /*UndefAllowed*/ false);
1113 ConstantRange RRange =
1114 LVI->getConstantRange(RHS, BinOp, /*UndefAllowed*/ false);
1115
1116 bool Changed = false;
1117 bool NewNUW = false, NewNSW = false;
1118 if (!NUW) {
1120 Opcode, RRange, OBO::NoUnsignedWrap);
1121 NewNUW = NUWRange.contains(LRange);
1122 Changed |= NewNUW;
1123 }
1124 if (!NSW) {
1126 Opcode, RRange, OBO::NoSignedWrap);
1127 NewNSW = NSWRange.contains(LRange);
1128 Changed |= NewNSW;
1129 }
1130
1131 setDeducedOverflowingFlags(BinOp, Opcode, NewNSW, NewNUW);
1132
1133 return Changed;
1134}
1135
1136static bool processAnd(BinaryOperator *BinOp, LazyValueInfo *LVI) {
1137 if (BinOp->getType()->isVectorTy())
1138 return false;
1139
1140 // Pattern match (and lhs, C) where C includes a superset of bits which might
1141 // be set in lhs. This is a common truncation idiom created by instcombine.
1142 const Use &LHS = BinOp->getOperandUse(0);
1143 ConstantInt *RHS = dyn_cast<ConstantInt>(BinOp->getOperand(1));
1144 if (!RHS || !RHS->getValue().isMask())
1145 return false;
1146
1147 // We can only replace the AND with LHS based on range info if the range does
1148 // not include undef.
1149 ConstantRange LRange =
1150 LVI->getConstantRangeAtUse(LHS, /*UndefAllowed=*/false);
1151 if (!LRange.getUnsignedMax().ule(RHS->getValue()))
1152 return false;
1153
1154 BinOp->replaceAllUsesWith(LHS);
1155 BinOp->eraseFromParent();
1156 NumAnd++;
1157 return true;
1158}
1159
1161 const SimplifyQuery &SQ) {
1162 bool FnChanged = false;
1163 // Visiting in a pre-order depth-first traversal causes us to simplify early
1164 // blocks before querying later blocks (which require us to analyze early
1165 // blocks). Eagerly simplifying shallow blocks means there is strictly less
1166 // work to do for deep blocks. This also means we don't visit unreachable
1167 // blocks.
1168 for (BasicBlock *BB : depth_first(&F.getEntryBlock())) {
1169 bool BBChanged = false;
1170 for (Instruction &II : llvm::make_early_inc_range(*BB)) {
1171 switch (II.getOpcode()) {
1172 case Instruction::Select:
1173 BBChanged |= processSelect(cast<SelectInst>(&II), LVI);
1174 break;
1175 case Instruction::PHI:
1176 BBChanged |= processPHI(cast<PHINode>(&II), LVI, DT, SQ);
1177 break;
1178 case Instruction::ICmp:
1179 case Instruction::FCmp:
1180 BBChanged |= processCmp(cast<CmpInst>(&II), LVI);
1181 break;
1182 case Instruction::Call:
1183 case Instruction::Invoke:
1184 BBChanged |= processCallSite(cast<CallBase>(II), LVI);
1185 break;
1186 case Instruction::SRem:
1187 case Instruction::SDiv:
1188 BBChanged |= processSDivOrSRem(cast<BinaryOperator>(&II), LVI);
1189 break;
1190 case Instruction::UDiv:
1191 case Instruction::URem:
1192 BBChanged |= processUDivOrURem(cast<BinaryOperator>(&II), LVI);
1193 break;
1194 case Instruction::AShr:
1195 BBChanged |= processAShr(cast<BinaryOperator>(&II), LVI);
1196 break;
1197 case Instruction::SExt:
1198 BBChanged |= processSExt(cast<SExtInst>(&II), LVI);
1199 break;
1200 case Instruction::ZExt:
1201 BBChanged |= processZExt(cast<ZExtInst>(&II), LVI);
1202 break;
1203 case Instruction::Add:
1204 case Instruction::Sub:
1205 case Instruction::Mul:
1206 case Instruction::Shl:
1207 BBChanged |= processBinOp(cast<BinaryOperator>(&II), LVI);
1208 break;
1209 case Instruction::And:
1210 BBChanged |= processAnd(cast<BinaryOperator>(&II), LVI);
1211 break;
1212 }
1213 }
1214
1215 Instruction *Term = BB->getTerminator();
1216 switch (Term->getOpcode()) {
1217 case Instruction::Switch:
1218 BBChanged |= processSwitch(cast<SwitchInst>(Term), LVI, DT);
1219 break;
1220 case Instruction::Ret: {
1221 auto *RI = cast<ReturnInst>(Term);
1222 // Try to determine the return value if we can. This is mainly here to
1223 // simplify the writing of unit tests, but also helps to enable IPO by
1224 // constant folding the return values of callees.
1225 auto *RetVal = RI->getReturnValue();
1226 if (!RetVal) break; // handle "ret void"
1227 if (isa<Constant>(RetVal)) break; // nothing to do
1228 if (auto *C = getConstantAt(RetVal, RI, LVI)) {
1229 ++NumReturns;
1230 RI->replaceUsesOfWith(RetVal, C);
1231 BBChanged = true;
1232 }
1233 }
1234 }
1235
1236 FnChanged |= BBChanged;
1237 }
1238
1239 return FnChanged;
1240}
1241
1246
1247 bool Changed = runImpl(F, LVI, DT, getBestSimplifyQuery(AM, F));
1248
1250 if (!Changed) {
1252 } else {
1255 }
1256
1257 // Keeping LVI alive is expensive, both because it uses a lot of memory, and
1258 // because invalidating values in LVI is expensive. While CVP does preserve
1259 // LVI, we know that passes after JumpThreading+CVP will not need the result
1260 // of this analysis, so we forcefully discard it early.
1262 return PA;
1263}
This file contains the simple types necessary to represent the attributes associated with functions a...
BlockVerifier::State From
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static bool processICmp(ICmpInst *Cmp, LazyValueInfo *LVI)
static bool processAnd(BinaryOperator *BinOp, LazyValueInfo *LVI)
static bool processOverflowIntrinsic(WithOverflowInst *WO, LazyValueInfo *LVI)
static bool processSDivOrSRem(BinaryOperator *Instr, LazyValueInfo *LVI)
static bool expandUDivOrURem(BinaryOperator *Instr, const ConstantRange &XCR, const ConstantRange &YCR)
static bool constantFoldCmp(CmpInst *Cmp, LazyValueInfo *LVI)
See if LazyValueInfo's ability to exploit edge conditions or range information is sufficient to prove...
static bool processSaturatingInst(SaturatingInst *SI, LazyValueInfo *LVI)
static Value * getValueOnEdge(LazyValueInfo *LVI, Value *Incoming, BasicBlock *From, BasicBlock *To, Instruction *CxtI)
static bool narrowUDivOrURem(BinaryOperator *Instr, const ConstantRange &XCR, const ConstantRange &YCR)
Try to shrink a udiv/urem's width down to the smallest power of two that's sufficient to contain its ...
static bool willNotOverflow(BinaryOpIntrinsic *BO, LazyValueInfo *LVI)
static bool processSelect(SelectInst *S, LazyValueInfo *LVI)
static bool runImpl(Function &F, LazyValueInfo *LVI, DominatorTree *DT, const SimplifyQuery &SQ)
static void setDeducedOverflowingFlags(Value *V, Instruction::BinaryOps Opcode, bool NewNSW, bool NewNUW)
static bool processMinMaxIntrinsic(MinMaxIntrinsic *MM, LazyValueInfo *LVI)
static bool processBinOp(BinaryOperator *BinOp, LazyValueInfo *LVI)
static bool simplifyCommonValuePhi(PHINode *P, LazyValueInfo *LVI, DominatorTree *DT)
Try to simplify a phi with constant incoming values that match the edge values of a non-constant valu...
static bool processSRem(BinaryOperator *SDI, const ConstantRange &LCR, const ConstantRange &RCR, LazyValueInfo *LVI)
static Domain getDomain(const ConstantRange &CR)
static bool processPHI(PHINode *P, LazyValueInfo *LVI, DominatorTree *DT, const SimplifyQuery &SQ)
static bool processUDivOrURem(BinaryOperator *Instr, LazyValueInfo *LVI)
@ NonNegative
@ NonPositive
static bool processSDiv(BinaryOperator *SDI, const ConstantRange &LCR, const ConstantRange &RCR, LazyValueInfo *LVI)
See if LazyValueInfo's ability to exploit edge conditions or range information is sufficient to prove...
static bool processAShr(BinaryOperator *SDI, LazyValueInfo *LVI)
static bool processZExt(ZExtInst *ZExt, LazyValueInfo *LVI)
static bool narrowSDivOrSRem(BinaryOperator *Instr, const ConstantRange &LCR, const ConstantRange &RCR)
Try to shrink a sdiv/srem's width down to the smallest power of two that's sufficient to contain its ...
static bool processSExt(SExtInst *SDI, LazyValueInfo *LVI)
static bool processSwitch(SwitchInst *I, LazyValueInfo *LVI, DominatorTree *DT)
Simplify a switch instruction by removing cases which can never fire.
static Constant * getConstantAt(Value *V, Instruction *At, LazyValueInfo *LVI)
static bool processCmp(CmpInst *Cmp, LazyValueInfo *LVI)
static bool processAbsIntrinsic(IntrinsicInst *II, LazyValueInfo *LVI)
static bool processCallSite(CallBase &CB, LazyValueInfo *LVI)
Infer nonnull attributes for the arguments at the specified callsite.
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
static bool runImpl(Function &F, const TargetLowering &TLI)
This is the interface for a simple mod/ref and alias analysis over globals.
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
#define P(N)
This header defines various interfaces for pass management in LLVM.
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:167
@ Struct
Value * RHS
Value * LHS
Class for arbitrary precision integers.
Definition: APInt.h:76
static APInt getAllOnes(unsigned numBits)
Return an APInt of a specified width with all bits set.
Definition: APInt.h:212
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
Definition: APInt.h:197
bool ule(const APInt &RHS) const
Unsigned less or equal comparison.
Definition: APInt.h:1128
APInt sext(unsigned width) const
Sign extend to a new width.
Definition: APInt.cpp:954
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
Definition: APInt.h:178
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:348
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:500
AttributeList addParamAttribute(LLVMContext &C, unsigned ArgNo, Attribute::AttrKind Kind) const
Add an argument attribute to the list.
Definition: Attributes.h:589
static Attribute get(LLVMContext &Context, AttrKind Kind, uint64_t Val=0)
Return a uniquified Attribute object.
Definition: Attributes.cpp:93
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
Definition: BasicBlock.cpp:496
This class represents an intrinsic that is based on a binary operation.
Value * getRHS() const
unsigned getNoWrapKind() const
Returns one of OBO::NoSignedWrap or OBO::NoUnsignedWrap.
bool isSigned() const
Whether the intrinsic is signed or unsigned.
Instruction::BinaryOps getBinaryOp() const
Returns the binary operation underlying the intrinsic.
Value * getLHS() const
static BinaryOperator * Create(BinaryOps Op, Value *S1, Value *S2, const Twine &Name, BasicBlock::iterator InsertBefore)
Construct a binary instruction, given the opcode and the two operands.
BinaryOps getOpcode() const
Definition: InstrTypes.h:491
static BinaryOperator * CreateNeg(Value *Op, const Twine &Name, BasicBlock::iterator InsertBefore)
Helper functions to construct and inspect unary operations (NEG and NOT) via binary operators SUB and...
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1455
std::optional< OperandBundleUse > getOperandBundle(StringRef Name) const
Return an operand bundle by name, if present.
Definition: InstrTypes.h:2357
bool paramHasAttr(unsigned ArgNo, Attribute::AttrKind Kind) const
Determine whether the argument or parameter has the given attribute.
void setAttributes(AttributeList A)
Set the parameter attributes for this call.
Definition: InstrTypes.h:1784
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1648
void setArgOperand(unsigned i, Value *v)
Definition: InstrTypes.h:1653
Intrinsic::ID getIntrinsicID() const
Returns the intrinsic ID of the intrinsic called or Intrinsic::not_intrinsic if the called function i...
iterator_range< User::op_iterator > args()
Iteration adapter for range-for loops.
Definition: InstrTypes.h:1639
unsigned arg_size() const
Definition: InstrTypes.h:1646
AttributeList getAttributes() const
Return the parameter attributes for this call.
Definition: InstrTypes.h:1780
static CastInst * CreateZExtOrBitCast(Value *S, Type *Ty, const Twine &Name, BasicBlock::iterator InsertBefore)
Create a ZExt or BitCast cast instruction.
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:955
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
Definition: InstrTypes.h:1323
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:965
@ ICMP_ULT
unsigned less than
Definition: InstrTypes.h:990
@ ICMP_EQ
equal
Definition: InstrTypes.h:986
@ ICMP_ULE
unsigned less or equal
Definition: InstrTypes.h:991
Predicate getNonStrictPredicate() const
For example, SGT -> SGE, SLT -> SLE, ULT -> ULE, UGT -> UGE.
Definition: InstrTypes.h:1172
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:849
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:856
static ConstantPointerNull * get(PointerType *T)
Static factory methods - Return objects of the specified value.
Definition: Constants.cpp:1775
This class represents a range of values.
Definition: ConstantRange.h:47
unsigned getActiveBits() const
Compute the maximal number of active bits needed to represent every value in this range.
ConstantRange umul_sat(const ConstantRange &Other) const
Perform an unsigned saturating multiplication of two constant ranges.
static CmpInst::Predicate getEquivalentPredWithFlippedSignedness(CmpInst::Predicate Pred, const ConstantRange &CR1, const ConstantRange &CR2)
If the comparison between constant ranges this and Other is insensitive to the signedness of the comp...
const APInt * getSingleElement() const
If this set contains a single element, return it, otherwise return null.
bool isAllNegative() const
Return true if all values in this range are negative.
bool icmp(CmpInst::Predicate Pred, const ConstantRange &Other) const
Does the predicate Pred hold between ranges this and Other? NOTE: false does not mean that inverse pr...
ConstantRange abs(bool IntMinIsPoison=false) const
Calculate absolute value range.
bool isAllNonNegative() const
Return true if all values in this range are non-negative.
ConstantRange sdiv(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a signed division of a value in th...
bool contains(const APInt &Val) const
Return true if the specified value is in the set.
APInt getUnsignedMax() const
Return the largest unsigned value contained in the ConstantRange.
static bool areInsensitiveToSignednessOfICmpPredicate(const ConstantRange &CR1, const ConstantRange &CR2)
Return true iff CR1 ult CR2 is equivalent to CR1 slt CR2.
static ConstantRange makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp, const ConstantRange &Other, unsigned NoWrapKind)
Produce the largest range containing all X such that "X BinOp Y" is guaranteed not to wrap (overflow)...
unsigned getMinSignedBits() const
Compute the maximal number of bits needed to represent every value in this signed range.
uint32_t getBitWidth() const
Get the bit width of this ConstantRange.
static Constant * get(StructType *T, ArrayRef< Constant * > V)
Definition: Constants.cpp:1356
This is an important base class in LLVM.
Definition: Constant.h:41
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Definition: Constants.cpp:370
This class represents an Operation in the Expression.
void applyUpdatesPermissive(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:279
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:122
This instruction compares its operands according to the predicate given to the constructor.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2649
bool hasNoUnsignedWrap() const LLVM_READONLY
Determine whether the no unsigned wrap flag is set.
bool hasNoSignedWrap() const LLVM_READONLY
Determine whether the no signed wrap flag is set.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:453
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
bool isExact() const LLVM_READONLY
Determine whether the exact flag is set.
void setNonNeg(bool b=true)
Set or clear the nneg flag on this instruction, which must be a zext instruction.
bool hasNonNeg() const LLVM_READONLY
Determine whether the the nneg flag is set.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:450
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:47
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
Definition: IntrinsicInst.h:54
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
Analysis to compute lazy value information.
This pass computes, caches, and vends lazy value constraint information.
Definition: LazyValueInfo.h:31
ConstantRange getConstantRangeAtUse(const Use &U, bool UndefAllowed)
Return the ConstantRange constraint that is known to hold for the value at a specific use-site.
ConstantRange getConstantRange(Value *V, Instruction *CxtI, bool UndefAllowed)
Return the ConstantRange constraint that is known to hold for the specified value at the specified in...
Tristate
This is used to return true/false/dunno results.
Definition: LazyValueInfo.h:61
Constant * getConstantOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB, Instruction *CxtI=nullptr)
Determine whether the specified value is known to be a constant on the specified edge.
Tristate getPredicateOnEdge(unsigned Pred, Value *V, Constant *C, BasicBlock *FromBB, BasicBlock *ToBB, Instruction *CxtI=nullptr)
Determine whether the specified value comparison with a constant is known to be true or false on the ...
Tristate getPredicateAt(unsigned Pred, Value *V, Constant *C, Instruction *CxtI, bool UseBlockValue)
Determine whether the specified value comparison with a constant is known to be true or false at the ...
Constant * getConstant(Value *V, Instruction *CxtI)
Determine whether the specified value is known to be a constant at the specified instruction.
This class represents min/max intrinsics.
Value * getLHS() const
Value * getRHS() const
static ICmpInst::Predicate getPredicate(Intrinsic::ID ID)
Returns the comparison predicate underlying the intrinsic.
static bool isSigned(Intrinsic::ID ID)
Whether the intrinsic is signed or unsigned.
Utility class for integer operators which may exhibit overflow - Add, Sub, Mul, and Shl.
Definition: Operator.h:75
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1827
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:109
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:115
void abandon()
Mark an analysis as abandoned.
Definition: Analysis.h:162
void preserve()
Mark an analysis as preserved.
Definition: Analysis.h:129
This class represents a sign extension of integer types.
Represents a saturating add/sub intrinsic.
This class represents the LLVM 'select' instruction.
const Value * getFalseValue() const
const Value * getCondition() const
const Value * getTrueValue() const
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
Class to represent struct types.
Definition: DerivedTypes.h:216
A wrapper class to simplify modification of SwitchInst cases along with their prof branch_weights met...
Multiway switch.
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
unsigned getIntegerBitWidth() const
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:265
static IntegerType * getIntNTy(LLVMContext &C, unsigned N)
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:228
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
const Use & getOperandUse(unsigned i) const
Definition: User.h:182
Value * getOperand(unsigned i) const
Definition: User.h:169
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:534
bool use_empty() const
Definition: Value.h:344
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:1074
iterator_range< use_iterator > uses()
Definition: Value.h:376
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:383
Represents an op.with.overflow intrinsic.
This class represents zero extension of integer types.
self_iterator getIterator()
Definition: ilist_node.h:109
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions=false, const TargetLibraryInfo *TLI=nullptr, DomTreeUpdater *DTU=nullptr)
If a terminator instruction is predicated on a constant value, convert it into an unconditional branc...
Definition: Local.cpp:129
auto successors(const MachineBasicBlock *BB)
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:665
bool isGuaranteedNotToBeUndef(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Returns true if V cannot be undef, but may be poison.
uint64_t PowerOf2Ceil(uint64_t A)
Returns the power of two which is greater than or equal to the given value.
Definition: MathExtras.h:361
Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
iterator_range< df_iterator< T > > depth_first(const T &G)
bool isGuaranteedNotToBePoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Returns true if V cannot be poison, but may be undef.
const SimplifyQuery getBestSimplifyQuery(Pass &, Function &)
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Incoming for lane maks phi as machine instruction, incoming register Reg and incoming block Block are...