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