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