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