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/Optional.h" 16 #include "llvm/ADT/SmallVector.h" 17 #include "llvm/ADT/Statistic.h" 18 #include "llvm/Analysis/DomTreeUpdater.h" 19 #include "llvm/Analysis/GlobalsModRef.h" 20 #include "llvm/Analysis/InstructionSimplify.h" 21 #include "llvm/Analysis/LazyValueInfo.h" 22 #include "llvm/Analysis/ValueTracking.h" 23 #include "llvm/IR/Attributes.h" 24 #include "llvm/IR/BasicBlock.h" 25 #include "llvm/IR/CFG.h" 26 #include "llvm/IR/Constant.h" 27 #include "llvm/IR/ConstantRange.h" 28 #include "llvm/IR/Constants.h" 29 #include "llvm/IR/DerivedTypes.h" 30 #include "llvm/IR/Function.h" 31 #include "llvm/IR/IRBuilder.h" 32 #include "llvm/IR/InstrTypes.h" 33 #include "llvm/IR/Instruction.h" 34 #include "llvm/IR/Instructions.h" 35 #include "llvm/IR/IntrinsicInst.h" 36 #include "llvm/IR/Operator.h" 37 #include "llvm/IR/PassManager.h" 38 #include "llvm/IR/Type.h" 39 #include "llvm/IR/Value.h" 40 #include "llvm/InitializePasses.h" 41 #include "llvm/Pass.h" 42 #include "llvm/Support/Casting.h" 43 #include "llvm/Support/CommandLine.h" 44 #include "llvm/Transforms/Scalar.h" 45 #include "llvm/Transforms/Utils/Local.h" 46 #include <cassert> 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 98 namespace { 99 100 class CorrelatedValuePropagation : public FunctionPass { 101 public: 102 static char ID; 103 104 CorrelatedValuePropagation(): FunctionPass(ID) { 105 initializeCorrelatedValuePropagationPass(*PassRegistry::getPassRegistry()); 106 } 107 108 bool runOnFunction(Function &F) override; 109 110 void getAnalysisUsage(AnalysisUsage &AU) const override { 111 AU.addRequired<DominatorTreeWrapperPass>(); 112 AU.addRequired<LazyValueInfoWrapperPass>(); 113 AU.addPreserved<GlobalsAAWrapperPass>(); 114 AU.addPreserved<DominatorTreeWrapperPass>(); 115 AU.addPreserved<LazyValueInfoWrapperPass>(); 116 } 117 }; 118 119 } // end anonymous namespace 120 121 char CorrelatedValuePropagation::ID = 0; 122 123 INITIALIZE_PASS_BEGIN(CorrelatedValuePropagation, "correlated-propagation", 124 "Value Propagation", false, false) 125 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 126 INITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass) 127 INITIALIZE_PASS_END(CorrelatedValuePropagation, "correlated-propagation", 128 "Value Propagation", false, false) 129 130 // Public interface to the Value Propagation pass 131 Pass *llvm::createCorrelatedValuePropagationPass() { 132 return new CorrelatedValuePropagation(); 133 } 134 135 static bool processSelect(SelectInst *S, LazyValueInfo *LVI) { 136 if (S->getType()->isVectorTy()) return false; 137 if (isa<Constant>(S->getCondition())) return false; 138 139 Constant *C = LVI->getConstant(S->getCondition(), S); 140 if (!C) return false; 141 142 ConstantInt *CI = dyn_cast<ConstantInt>(C); 143 if (!CI) return false; 144 145 Value *ReplaceWith = CI->isOne() ? S->getTrueValue() : S->getFalseValue(); 146 S->replaceAllUsesWith(ReplaceWith); 147 S->eraseFromParent(); 148 149 ++NumSelects; 150 151 return true; 152 } 153 154 /// Try to simplify a phi with constant incoming values that match the edge 155 /// values of a non-constant value on all other edges: 156 /// bb0: 157 /// %isnull = icmp eq i8* %x, null 158 /// br i1 %isnull, label %bb2, label %bb1 159 /// bb1: 160 /// br label %bb2 161 /// bb2: 162 /// %r = phi i8* [ %x, %bb1 ], [ null, %bb0 ] 163 /// --> 164 /// %r = %x 165 static bool simplifyCommonValuePhi(PHINode *P, LazyValueInfo *LVI, 166 DominatorTree *DT) { 167 // Collect incoming constants and initialize possible common value. 168 SmallVector<std::pair<Constant *, unsigned>, 4> IncomingConstants; 169 Value *CommonValue = nullptr; 170 for (unsigned i = 0, e = P->getNumIncomingValues(); i != e; ++i) { 171 Value *Incoming = P->getIncomingValue(i); 172 if (auto *IncomingConstant = dyn_cast<Constant>(Incoming)) { 173 IncomingConstants.push_back(std::make_pair(IncomingConstant, i)); 174 } else if (!CommonValue) { 175 // The potential common value is initialized to the first non-constant. 176 CommonValue = Incoming; 177 } else if (Incoming != CommonValue) { 178 // There can be only one non-constant common value. 179 return false; 180 } 181 } 182 183 if (!CommonValue || IncomingConstants.empty()) 184 return false; 185 186 // The common value must be valid in all incoming blocks. 187 BasicBlock *ToBB = P->getParent(); 188 if (auto *CommonInst = dyn_cast<Instruction>(CommonValue)) 189 if (!DT->dominates(CommonInst, ToBB)) 190 return false; 191 192 // We have a phi with exactly 1 variable incoming value and 1 or more constant 193 // incoming values. See if all constant incoming values can be mapped back to 194 // the same incoming variable value. 195 for (auto &IncomingConstant : IncomingConstants) { 196 Constant *C = IncomingConstant.first; 197 BasicBlock *IncomingBB = P->getIncomingBlock(IncomingConstant.second); 198 if (C != LVI->getConstantOnEdge(CommonValue, IncomingBB, ToBB, P)) 199 return false; 200 } 201 202 // LVI only guarantees that the value matches a certain constant if the value 203 // is not poison. Make sure we don't replace a well-defined value with poison. 204 // This is usually satisfied due to a prior branch on the value. 205 if (!isGuaranteedNotToBePoison(CommonValue, nullptr, P, DT)) 206 return false; 207 208 // All constant incoming values map to the same variable along the incoming 209 // edges of the phi. The phi is unnecessary. 210 P->replaceAllUsesWith(CommonValue); 211 P->eraseFromParent(); 212 ++NumPhiCommon; 213 return true; 214 } 215 216 static Value *getValueOnEdge(LazyValueInfo *LVI, Value *Incoming, 217 BasicBlock *From, BasicBlock *To, 218 Instruction *CxtI) { 219 if (Constant *C = LVI->getConstantOnEdge(Incoming, From, To, CxtI)) 220 return C; 221 222 // Look if the incoming value is a select with a scalar condition for which 223 // LVI can tells us the value. In that case replace the incoming value with 224 // the appropriate value of the select. This often allows us to remove the 225 // select later. 226 auto *SI = dyn_cast<SelectInst>(Incoming); 227 if (!SI) 228 return nullptr; 229 230 // Once LVI learns to handle vector types, we could also add support 231 // for vector type constants that are not all zeroes or all ones. 232 Value *Condition = SI->getCondition(); 233 if (!Condition->getType()->isVectorTy()) { 234 if (Constant *C = LVI->getConstantOnEdge(Condition, From, To, CxtI)) { 235 if (C->isOneValue()) 236 return SI->getTrueValue(); 237 if (C->isZeroValue()) 238 return SI->getFalseValue(); 239 } 240 } 241 242 // Look if the select has a constant but LVI tells us that the incoming 243 // value can never be that constant. In that case replace the incoming 244 // value with the other value of the select. This often allows us to 245 // remove the select later. 246 247 // The "false" case 248 if (auto *C = dyn_cast<Constant>(SI->getFalseValue())) 249 if (LVI->getPredicateOnEdge(ICmpInst::ICMP_EQ, SI, C, From, To, CxtI) == 250 LazyValueInfo::False) 251 return SI->getTrueValue(); 252 253 // The "true" case, 254 // similar to the select "false" case, but try the select "true" value 255 if (auto *C = dyn_cast<Constant>(SI->getTrueValue())) 256 if (LVI->getPredicateOnEdge(ICmpInst::ICMP_EQ, SI, C, From, To, CxtI) == 257 LazyValueInfo::False) 258 return SI->getFalseValue(); 259 260 return nullptr; 261 } 262 263 static bool processPHI(PHINode *P, LazyValueInfo *LVI, DominatorTree *DT, 264 const SimplifyQuery &SQ) { 265 bool Changed = false; 266 267 BasicBlock *BB = P->getParent(); 268 for (unsigned i = 0, e = P->getNumIncomingValues(); i < e; ++i) { 269 Value *Incoming = P->getIncomingValue(i); 270 if (isa<Constant>(Incoming)) continue; 271 272 Value *V = getValueOnEdge(LVI, Incoming, P->getIncomingBlock(i), BB, P); 273 if (V) { 274 P->setIncomingValue(i, V); 275 Changed = true; 276 } 277 } 278 279 if (Value *V = simplifyInstruction(P, SQ)) { 280 P->replaceAllUsesWith(V); 281 P->eraseFromParent(); 282 Changed = true; 283 } 284 285 if (!Changed) 286 Changed = simplifyCommonValuePhi(P, LVI, DT); 287 288 if (Changed) 289 ++NumPhis; 290 291 return Changed; 292 } 293 294 static bool processMemAccess(Instruction *I, LazyValueInfo *LVI) { 295 Value *Pointer = nullptr; 296 if (LoadInst *L = dyn_cast<LoadInst>(I)) 297 Pointer = L->getPointerOperand(); 298 else 299 Pointer = cast<StoreInst>(I)->getPointerOperand(); 300 301 if (isa<Constant>(Pointer)) return false; 302 303 Constant *C = LVI->getConstant(Pointer, I); 304 if (!C) return false; 305 306 ++NumMemAccess; 307 I->replaceUsesOfWith(Pointer, C); 308 return true; 309 } 310 311 static bool processICmp(ICmpInst *Cmp, LazyValueInfo *LVI) { 312 if (!CanonicalizeICmpPredicatesToUnsigned) 313 return false; 314 315 // Only for signed relational comparisons of scalar integers. 316 if (Cmp->getType()->isVectorTy() || 317 !Cmp->getOperand(0)->getType()->isIntegerTy()) 318 return false; 319 320 if (!Cmp->isSigned()) 321 return false; 322 323 ICmpInst::Predicate UnsignedPred = 324 ConstantRange::getEquivalentPredWithFlippedSignedness( 325 Cmp->getPredicate(), LVI->getConstantRange(Cmp->getOperand(0), Cmp), 326 LVI->getConstantRange(Cmp->getOperand(1), Cmp)); 327 328 if (UnsignedPred == ICmpInst::Predicate::BAD_ICMP_PREDICATE) 329 return false; 330 331 ++NumSICmps; 332 Cmp->setPredicate(UnsignedPred); 333 334 return true; 335 } 336 337 /// See if LazyValueInfo's ability to exploit edge conditions or range 338 /// information is sufficient to prove this comparison. Even for local 339 /// conditions, this can sometimes prove conditions instcombine can't by 340 /// exploiting range information. 341 static bool constantFoldCmp(CmpInst *Cmp, LazyValueInfo *LVI) { 342 Value *Op0 = Cmp->getOperand(0); 343 auto *C = dyn_cast<Constant>(Cmp->getOperand(1)); 344 if (!C) 345 return false; 346 347 LazyValueInfo::Tristate Result = 348 LVI->getPredicateAt(Cmp->getPredicate(), Op0, C, Cmp, 349 /*UseBlockValue=*/true); 350 if (Result == LazyValueInfo::Unknown) 351 return false; 352 353 ++NumCmps; 354 Constant *TorF = ConstantInt::get(Type::getInt1Ty(Cmp->getContext()), 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->getConstantRange(BO->getLHS(), BO); 443 ConstantRange RRange = LVI->getConstantRange(BO->getRHS(), BO); 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 static bool isNonNegative(Value *V, LazyValueInfo *LVI, Instruction *CxtI) { 697 Constant *Zero = ConstantInt::get(V->getType(), 0); 698 auto Result = LVI->getPredicateAt(ICmpInst::ICMP_SGE, V, Zero, CxtI, 699 /*UseBlockValue=*/true); 700 return Result == LazyValueInfo::True; 701 } 702 703 static bool isNonPositive(Value *V, LazyValueInfo *LVI, Instruction *CxtI) { 704 Constant *Zero = ConstantInt::get(V->getType(), 0); 705 auto Result = LVI->getPredicateAt(ICmpInst::ICMP_SLE, V, Zero, CxtI, 706 /*UseBlockValue=*/true); 707 return Result == LazyValueInfo::True; 708 } 709 710 enum class Domain { NonNegative, NonPositive, Unknown }; 711 712 Domain getDomain(Value *V, LazyValueInfo *LVI, Instruction *CxtI) { 713 if (isNonNegative(V, LVI, CxtI)) 714 return Domain::NonNegative; 715 if (isNonPositive(V, LVI, CxtI)) 716 return Domain::NonPositive; 717 return Domain::Unknown; 718 } 719 720 /// Try to shrink a sdiv/srem's width down to the smallest power of two that's 721 /// sufficient to contain its operands. 722 static bool narrowSDivOrSRem(BinaryOperator *Instr, LazyValueInfo *LVI) { 723 assert(Instr->getOpcode() == Instruction::SDiv || 724 Instr->getOpcode() == Instruction::SRem); 725 if (Instr->getType()->isVectorTy()) 726 return false; 727 728 // Find the smallest power of two bitwidth that's sufficient to hold Instr's 729 // operands. 730 unsigned OrigWidth = Instr->getType()->getIntegerBitWidth(); 731 732 // What is the smallest bit width that can accomodate the entire value ranges 733 // of both of the operands? 734 std::array<Optional<ConstantRange>, 2> CRs; 735 unsigned MinSignedBits = 0; 736 for (auto I : zip(Instr->operands(), CRs)) { 737 std::get<1>(I) = LVI->getConstantRange(std::get<0>(I), Instr); 738 MinSignedBits = std::max(std::get<1>(I)->getMinSignedBits(), MinSignedBits); 739 } 740 741 // sdiv/srem is UB if divisor is -1 and divident is INT_MIN, so unless we can 742 // prove that such a combination is impossible, we need to bump the bitwidth. 743 if (CRs[1]->contains(APInt::getAllOnes(OrigWidth)) && 744 CRs[0]->contains(APInt::getSignedMinValue(MinSignedBits).sext(OrigWidth))) 745 ++MinSignedBits; 746 747 // Don't shrink below 8 bits wide. 748 unsigned NewWidth = std::max<unsigned>(PowerOf2Ceil(MinSignedBits), 8); 749 750 // NewWidth might be greater than OrigWidth if OrigWidth is not a power of 751 // two. 752 if (NewWidth >= OrigWidth) 753 return false; 754 755 ++NumSDivSRemsNarrowed; 756 IRBuilder<> B{Instr}; 757 auto *TruncTy = Type::getIntNTy(Instr->getContext(), NewWidth); 758 auto *LHS = B.CreateTruncOrBitCast(Instr->getOperand(0), TruncTy, 759 Instr->getName() + ".lhs.trunc"); 760 auto *RHS = B.CreateTruncOrBitCast(Instr->getOperand(1), TruncTy, 761 Instr->getName() + ".rhs.trunc"); 762 auto *BO = B.CreateBinOp(Instr->getOpcode(), LHS, RHS, Instr->getName()); 763 auto *Sext = B.CreateSExt(BO, Instr->getType(), Instr->getName() + ".sext"); 764 if (auto *BinOp = dyn_cast<BinaryOperator>(BO)) 765 if (BinOp->getOpcode() == Instruction::SDiv) 766 BinOp->setIsExact(Instr->isExact()); 767 768 Instr->replaceAllUsesWith(Sext); 769 Instr->eraseFromParent(); 770 return true; 771 } 772 773 /// Try to shrink a udiv/urem's width down to the smallest power of two that's 774 /// sufficient to contain its operands. 775 static bool processUDivOrURem(BinaryOperator *Instr, LazyValueInfo *LVI) { 776 assert(Instr->getOpcode() == Instruction::UDiv || 777 Instr->getOpcode() == Instruction::URem); 778 if (Instr->getType()->isVectorTy()) 779 return false; 780 781 // Find the smallest power of two bitwidth that's sufficient to hold Instr's 782 // operands. 783 784 // What is the smallest bit width that can accomodate the entire value ranges 785 // of both of the operands? 786 unsigned MaxActiveBits = 0; 787 for (Value *Operand : Instr->operands()) { 788 ConstantRange CR = LVI->getConstantRange(Operand, Instr); 789 MaxActiveBits = std::max(CR.getActiveBits(), MaxActiveBits); 790 } 791 // Don't shrink below 8 bits wide. 792 unsigned NewWidth = std::max<unsigned>(PowerOf2Ceil(MaxActiveBits), 8); 793 794 // NewWidth might be greater than OrigWidth if OrigWidth is not a power of 795 // two. 796 if (NewWidth >= Instr->getType()->getIntegerBitWidth()) 797 return false; 798 799 ++NumUDivURemsNarrowed; 800 IRBuilder<> B{Instr}; 801 auto *TruncTy = Type::getIntNTy(Instr->getContext(), NewWidth); 802 auto *LHS = B.CreateTruncOrBitCast(Instr->getOperand(0), TruncTy, 803 Instr->getName() + ".lhs.trunc"); 804 auto *RHS = B.CreateTruncOrBitCast(Instr->getOperand(1), TruncTy, 805 Instr->getName() + ".rhs.trunc"); 806 auto *BO = B.CreateBinOp(Instr->getOpcode(), LHS, RHS, Instr->getName()); 807 auto *Zext = B.CreateZExt(BO, Instr->getType(), Instr->getName() + ".zext"); 808 if (auto *BinOp = dyn_cast<BinaryOperator>(BO)) 809 if (BinOp->getOpcode() == Instruction::UDiv) 810 BinOp->setIsExact(Instr->isExact()); 811 812 Instr->replaceAllUsesWith(Zext); 813 Instr->eraseFromParent(); 814 return true; 815 } 816 817 static bool processSRem(BinaryOperator *SDI, LazyValueInfo *LVI) { 818 assert(SDI->getOpcode() == Instruction::SRem); 819 if (SDI->getType()->isVectorTy()) 820 return false; 821 822 struct Operand { 823 Value *V; 824 Domain D; 825 }; 826 std::array<Operand, 2> Ops; 827 828 for (const auto I : zip(Ops, SDI->operands())) { 829 Operand &Op = std::get<0>(I); 830 Op.V = std::get<1>(I); 831 Op.D = getDomain(Op.V, LVI, SDI); 832 if (Op.D == Domain::Unknown) 833 return false; 834 } 835 836 // We know domains of both of the operands! 837 ++NumSRems; 838 839 // We need operands to be non-negative, so negate each one that isn't. 840 for (Operand &Op : Ops) { 841 if (Op.D == Domain::NonNegative) 842 continue; 843 auto *BO = 844 BinaryOperator::CreateNeg(Op.V, Op.V->getName() + ".nonneg", SDI); 845 BO->setDebugLoc(SDI->getDebugLoc()); 846 Op.V = BO; 847 } 848 849 auto *URem = 850 BinaryOperator::CreateURem(Ops[0].V, Ops[1].V, SDI->getName(), SDI); 851 URem->setDebugLoc(SDI->getDebugLoc()); 852 853 Value *Res = URem; 854 855 // If the divident was non-positive, we need to negate the result. 856 if (Ops[0].D == Domain::NonPositive) 857 Res = BinaryOperator::CreateNeg(Res, Res->getName() + ".neg", SDI); 858 859 SDI->replaceAllUsesWith(Res); 860 SDI->eraseFromParent(); 861 862 // Try to simplify our new urem. 863 processUDivOrURem(URem, LVI); 864 865 return true; 866 } 867 868 /// See if LazyValueInfo's ability to exploit edge conditions or range 869 /// information is sufficient to prove the signs of both operands of this SDiv. 870 /// If this is the case, replace the SDiv with a UDiv. Even for local 871 /// conditions, this can sometimes prove conditions instcombine can't by 872 /// exploiting range information. 873 static bool processSDiv(BinaryOperator *SDI, LazyValueInfo *LVI) { 874 assert(SDI->getOpcode() == Instruction::SDiv); 875 if (SDI->getType()->isVectorTy()) 876 return false; 877 878 struct Operand { 879 Value *V; 880 Domain D; 881 }; 882 std::array<Operand, 2> Ops; 883 884 for (const auto I : zip(Ops, SDI->operands())) { 885 Operand &Op = std::get<0>(I); 886 Op.V = std::get<1>(I); 887 Op.D = getDomain(Op.V, LVI, SDI); 888 if (Op.D == Domain::Unknown) 889 return false; 890 } 891 892 // We know domains of both of the operands! 893 ++NumSDivs; 894 895 // We need operands to be non-negative, so negate each one that isn't. 896 for (Operand &Op : Ops) { 897 if (Op.D == Domain::NonNegative) 898 continue; 899 auto *BO = 900 BinaryOperator::CreateNeg(Op.V, Op.V->getName() + ".nonneg", SDI); 901 BO->setDebugLoc(SDI->getDebugLoc()); 902 Op.V = BO; 903 } 904 905 auto *UDiv = 906 BinaryOperator::CreateUDiv(Ops[0].V, Ops[1].V, SDI->getName(), SDI); 907 UDiv->setDebugLoc(SDI->getDebugLoc()); 908 UDiv->setIsExact(SDI->isExact()); 909 910 Value *Res = UDiv; 911 912 // If the operands had two different domains, we need to negate the result. 913 if (Ops[0].D != Ops[1].D) 914 Res = BinaryOperator::CreateNeg(Res, Res->getName() + ".neg", SDI); 915 916 SDI->replaceAllUsesWith(Res); 917 SDI->eraseFromParent(); 918 919 // Try to simplify our new udiv. 920 processUDivOrURem(UDiv, LVI); 921 922 return true; 923 } 924 925 static bool processSDivOrSRem(BinaryOperator *Instr, LazyValueInfo *LVI) { 926 assert(Instr->getOpcode() == Instruction::SDiv || 927 Instr->getOpcode() == Instruction::SRem); 928 if (Instr->getType()->isVectorTy()) 929 return false; 930 931 if (Instr->getOpcode() == Instruction::SDiv) 932 if (processSDiv(Instr, LVI)) 933 return true; 934 935 if (Instr->getOpcode() == Instruction::SRem) 936 if (processSRem(Instr, LVI)) 937 return true; 938 939 return narrowSDivOrSRem(Instr, LVI); 940 } 941 942 static bool processAShr(BinaryOperator *SDI, LazyValueInfo *LVI) { 943 if (SDI->getType()->isVectorTy()) 944 return false; 945 946 ConstantRange LRange = LVI->getConstantRange(SDI->getOperand(0), SDI); 947 unsigned OrigWidth = SDI->getType()->getIntegerBitWidth(); 948 ConstantRange NegOneOrZero = 949 ConstantRange(APInt(OrigWidth, (uint64_t)-1, true), APInt(OrigWidth, 1)); 950 if (NegOneOrZero.contains(LRange)) { 951 // ashr of -1 or 0 never changes the value, so drop the whole instruction 952 ++NumAShrsRemoved; 953 SDI->replaceAllUsesWith(SDI->getOperand(0)); 954 SDI->eraseFromParent(); 955 return true; 956 } 957 958 if (!isNonNegative(SDI->getOperand(0), LVI, SDI)) 959 return false; 960 961 ++NumAShrsConverted; 962 auto *BO = BinaryOperator::CreateLShr(SDI->getOperand(0), SDI->getOperand(1), 963 "", SDI); 964 BO->takeName(SDI); 965 BO->setDebugLoc(SDI->getDebugLoc()); 966 BO->setIsExact(SDI->isExact()); 967 SDI->replaceAllUsesWith(BO); 968 SDI->eraseFromParent(); 969 970 return true; 971 } 972 973 static bool processSExt(SExtInst *SDI, LazyValueInfo *LVI) { 974 if (SDI->getType()->isVectorTy()) 975 return false; 976 977 Value *Base = SDI->getOperand(0); 978 979 if (!isNonNegative(Base, LVI, SDI)) 980 return false; 981 982 ++NumSExt; 983 auto *ZExt = CastInst::CreateZExtOrBitCast(Base, SDI->getType(), "", SDI); 984 ZExt->takeName(SDI); 985 ZExt->setDebugLoc(SDI->getDebugLoc()); 986 SDI->replaceAllUsesWith(ZExt); 987 SDI->eraseFromParent(); 988 989 return true; 990 } 991 992 static bool processBinOp(BinaryOperator *BinOp, LazyValueInfo *LVI) { 993 using OBO = OverflowingBinaryOperator; 994 995 if (BinOp->getType()->isVectorTy()) 996 return false; 997 998 bool NSW = BinOp->hasNoSignedWrap(); 999 bool NUW = BinOp->hasNoUnsignedWrap(); 1000 if (NSW && NUW) 1001 return false; 1002 1003 Instruction::BinaryOps Opcode = BinOp->getOpcode(); 1004 Value *LHS = BinOp->getOperand(0); 1005 Value *RHS = BinOp->getOperand(1); 1006 1007 ConstantRange LRange = LVI->getConstantRange(LHS, BinOp); 1008 ConstantRange RRange = LVI->getConstantRange(RHS, BinOp); 1009 1010 bool Changed = false; 1011 bool NewNUW = false, NewNSW = false; 1012 if (!NUW) { 1013 ConstantRange NUWRange = ConstantRange::makeGuaranteedNoWrapRegion( 1014 Opcode, RRange, OBO::NoUnsignedWrap); 1015 NewNUW = NUWRange.contains(LRange); 1016 Changed |= NewNUW; 1017 } 1018 if (!NSW) { 1019 ConstantRange NSWRange = ConstantRange::makeGuaranteedNoWrapRegion( 1020 Opcode, RRange, OBO::NoSignedWrap); 1021 NewNSW = NSWRange.contains(LRange); 1022 Changed |= NewNSW; 1023 } 1024 1025 setDeducedOverflowingFlags(BinOp, Opcode, NewNSW, NewNUW); 1026 1027 return Changed; 1028 } 1029 1030 static bool processAnd(BinaryOperator *BinOp, LazyValueInfo *LVI) { 1031 if (BinOp->getType()->isVectorTy()) 1032 return false; 1033 1034 // Pattern match (and lhs, C) where C includes a superset of bits which might 1035 // be set in lhs. This is a common truncation idiom created by instcombine. 1036 Value *LHS = BinOp->getOperand(0); 1037 ConstantInt *RHS = dyn_cast<ConstantInt>(BinOp->getOperand(1)); 1038 if (!RHS || !RHS->getValue().isMask()) 1039 return false; 1040 1041 // We can only replace the AND with LHS based on range info if the range does 1042 // not include undef. 1043 ConstantRange LRange = 1044 LVI->getConstantRange(LHS, BinOp, /*UndefAllowed=*/false); 1045 if (!LRange.getUnsignedMax().ule(RHS->getValue())) 1046 return false; 1047 1048 BinOp->replaceAllUsesWith(LHS); 1049 BinOp->eraseFromParent(); 1050 NumAnd++; 1051 return true; 1052 } 1053 1054 1055 static Constant *getConstantAt(Value *V, Instruction *At, LazyValueInfo *LVI) { 1056 if (Constant *C = LVI->getConstant(V, At)) 1057 return C; 1058 1059 // TODO: The following really should be sunk inside LVI's core algorithm, or 1060 // at least the outer shims around such. 1061 auto *C = dyn_cast<CmpInst>(V); 1062 if (!C) return nullptr; 1063 1064 Value *Op0 = C->getOperand(0); 1065 Constant *Op1 = dyn_cast<Constant>(C->getOperand(1)); 1066 if (!Op1) return nullptr; 1067 1068 LazyValueInfo::Tristate Result = LVI->getPredicateAt( 1069 C->getPredicate(), Op0, Op1, At, /*UseBlockValue=*/false); 1070 if (Result == LazyValueInfo::Unknown) 1071 return nullptr; 1072 1073 return (Result == LazyValueInfo::True) ? 1074 ConstantInt::getTrue(C->getContext()) : 1075 ConstantInt::getFalse(C->getContext()); 1076 } 1077 1078 static bool runImpl(Function &F, LazyValueInfo *LVI, DominatorTree *DT, 1079 const SimplifyQuery &SQ) { 1080 bool FnChanged = false; 1081 // Visiting in a pre-order depth-first traversal causes us to simplify early 1082 // blocks before querying later blocks (which require us to analyze early 1083 // blocks). Eagerly simplifying shallow blocks means there is strictly less 1084 // work to do for deep blocks. This also means we don't visit unreachable 1085 // blocks. 1086 for (BasicBlock *BB : depth_first(&F.getEntryBlock())) { 1087 bool BBChanged = false; 1088 for (Instruction &II : llvm::make_early_inc_range(*BB)) { 1089 switch (II.getOpcode()) { 1090 case Instruction::Select: 1091 BBChanged |= processSelect(cast<SelectInst>(&II), LVI); 1092 break; 1093 case Instruction::PHI: 1094 BBChanged |= processPHI(cast<PHINode>(&II), LVI, DT, SQ); 1095 break; 1096 case Instruction::ICmp: 1097 case Instruction::FCmp: 1098 BBChanged |= processCmp(cast<CmpInst>(&II), LVI); 1099 break; 1100 case Instruction::Load: 1101 case Instruction::Store: 1102 BBChanged |= processMemAccess(&II, LVI); 1103 break; 1104 case Instruction::Call: 1105 case Instruction::Invoke: 1106 BBChanged |= processCallSite(cast<CallBase>(II), LVI); 1107 break; 1108 case Instruction::SRem: 1109 case Instruction::SDiv: 1110 BBChanged |= processSDivOrSRem(cast<BinaryOperator>(&II), LVI); 1111 break; 1112 case Instruction::UDiv: 1113 case Instruction::URem: 1114 BBChanged |= processUDivOrURem(cast<BinaryOperator>(&II), LVI); 1115 break; 1116 case Instruction::AShr: 1117 BBChanged |= processAShr(cast<BinaryOperator>(&II), LVI); 1118 break; 1119 case Instruction::SExt: 1120 BBChanged |= processSExt(cast<SExtInst>(&II), LVI); 1121 break; 1122 case Instruction::Add: 1123 case Instruction::Sub: 1124 case Instruction::Mul: 1125 case Instruction::Shl: 1126 BBChanged |= processBinOp(cast<BinaryOperator>(&II), LVI); 1127 break; 1128 case Instruction::And: 1129 BBChanged |= processAnd(cast<BinaryOperator>(&II), LVI); 1130 break; 1131 } 1132 } 1133 1134 Instruction *Term = BB->getTerminator(); 1135 switch (Term->getOpcode()) { 1136 case Instruction::Switch: 1137 BBChanged |= processSwitch(cast<SwitchInst>(Term), LVI, DT); 1138 break; 1139 case Instruction::Ret: { 1140 auto *RI = cast<ReturnInst>(Term); 1141 // Try to determine the return value if we can. This is mainly here to 1142 // simplify the writing of unit tests, but also helps to enable IPO by 1143 // constant folding the return values of callees. 1144 auto *RetVal = RI->getReturnValue(); 1145 if (!RetVal) break; // handle "ret void" 1146 if (isa<Constant>(RetVal)) break; // nothing to do 1147 if (auto *C = getConstantAt(RetVal, RI, LVI)) { 1148 ++NumReturns; 1149 RI->replaceUsesOfWith(RetVal, C); 1150 BBChanged = true; 1151 } 1152 } 1153 } 1154 1155 FnChanged |= BBChanged; 1156 } 1157 1158 return FnChanged; 1159 } 1160 1161 bool CorrelatedValuePropagation::runOnFunction(Function &F) { 1162 if (skipFunction(F)) 1163 return false; 1164 1165 LazyValueInfo *LVI = &getAnalysis<LazyValueInfoWrapperPass>().getLVI(); 1166 DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 1167 1168 return runImpl(F, LVI, DT, getBestSimplifyQuery(*this, F)); 1169 } 1170 1171 PreservedAnalyses 1172 CorrelatedValuePropagationPass::run(Function &F, FunctionAnalysisManager &AM) { 1173 LazyValueInfo *LVI = &AM.getResult<LazyValueAnalysis>(F); 1174 DominatorTree *DT = &AM.getResult<DominatorTreeAnalysis>(F); 1175 1176 bool Changed = runImpl(F, LVI, DT, getBestSimplifyQuery(AM, F)); 1177 1178 PreservedAnalyses PA; 1179 if (!Changed) { 1180 PA = PreservedAnalyses::all(); 1181 } else { 1182 PA.preserve<DominatorTreeAnalysis>(); 1183 PA.preserve<LazyValueAnalysis>(); 1184 } 1185 1186 // Keeping LVI alive is expensive, both because it uses a lot of memory, and 1187 // because invalidating values in LVI is expensive. While CVP does preserve 1188 // LVI, we know that passes after JumpThreading+CVP will not need the result 1189 // of this analysis, so we forcefully discard it early. 1190 PA.abandon<LazyValueAnalysis>(); 1191 return PA; 1192 } 1193