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