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