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