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/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/Support/Debug.h" 44#include "llvm/Support/raw_ostream.h" 45#include "llvm/Transforms/Scalar.h" 46#include "llvm/Transforms/Utils/Local.h" 47#include <cassert> 48#include <utility> 49 50using namespace llvm; 51 52#define DEBUG_TYPE "correlated-value-propagation" 53 54STATISTIC(NumPhis, "Number of phis propagated"); 55STATISTIC(NumPhiCommon, "Number of phis deleted via common incoming value"); 56STATISTIC(NumSelects, "Number of selects propagated"); 57STATISTIC(NumMemAccess, "Number of memory access targets propagated"); 58STATISTIC(NumCmps, "Number of comparisons propagated"); 59STATISTIC(NumReturns, "Number of return values propagated"); 60STATISTIC(NumDeadCases, "Number of switch cases removed"); 61STATISTIC(NumSDivs, "Number of sdiv converted to udiv"); 62STATISTIC(NumUDivs, "Number of udivs whose width was decreased"); 63STATISTIC(NumAShrs, "Number of ashr converted to lshr"); 64STATISTIC(NumSRems, "Number of srem converted to urem"); 65STATISTIC(NumSExt, "Number of sext converted to zext"); 66STATISTIC(NumAnd, "Number of ands removed"); 67STATISTIC(NumNW, "Number of no-wrap deductions"); 68STATISTIC(NumNSW, "Number of no-signed-wrap deductions"); 69STATISTIC(NumNUW, "Number of no-unsigned-wrap deductions"); 70STATISTIC(NumAddNW, "Number of no-wrap deductions for add"); 71STATISTIC(NumAddNSW, "Number of no-signed-wrap deductions for add"); 72STATISTIC(NumAddNUW, "Number of no-unsigned-wrap deductions for add"); 73STATISTIC(NumSubNW, "Number of no-wrap deductions for sub"); 74STATISTIC(NumSubNSW, "Number of no-signed-wrap deductions for sub"); 75STATISTIC(NumSubNUW, "Number of no-unsigned-wrap deductions for sub"); 76STATISTIC(NumMulNW, "Number of no-wrap deductions for mul"); 77STATISTIC(NumMulNSW, "Number of no-signed-wrap deductions for mul"); 78STATISTIC(NumMulNUW, "Number of no-unsigned-wrap deductions for mul"); 79STATISTIC(NumShlNW, "Number of no-wrap deductions for shl"); 80STATISTIC(NumShlNSW, "Number of no-signed-wrap deductions for shl"); 81STATISTIC(NumShlNUW, "Number of no-unsigned-wrap deductions for shl"); 82STATISTIC(NumOverflows, "Number of overflow checks removed"); 83STATISTIC(NumSaturating, 84 "Number of saturating arithmetics converted to normal arithmetics"); 85 86static cl::opt<bool> DontAddNoWrapFlags("cvp-dont-add-nowrap-flags", cl::init(false)); 87 88namespace { 89 90 class CorrelatedValuePropagation : public FunctionPass { 91 public: 92 static char ID; 93 94 CorrelatedValuePropagation(): FunctionPass(ID) { 95 initializeCorrelatedValuePropagationPass(*PassRegistry::getPassRegistry()); 96 } 97 98 bool runOnFunction(Function &F) override; 99 100 void getAnalysisUsage(AnalysisUsage &AU) const override { 101 AU.addRequired<DominatorTreeWrapperPass>(); 102 AU.addRequired<LazyValueInfoWrapperPass>(); 103 AU.addPreserved<GlobalsAAWrapperPass>(); 104 AU.addPreserved<DominatorTreeWrapperPass>(); 105 AU.addPreserved<LazyValueInfoWrapperPass>(); 106 } 107 }; 108 109} // end anonymous namespace 110 111char CorrelatedValuePropagation::ID = 0; 112 113INITIALIZE_PASS_BEGIN(CorrelatedValuePropagation, "correlated-propagation", 114 "Value Propagation", false, false) 115INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 116INITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass) 117INITIALIZE_PASS_END(CorrelatedValuePropagation, "correlated-propagation", 118 "Value Propagation", false, false) 119 120// Public interface to the Value Propagation pass 121Pass *llvm::createCorrelatedValuePropagationPass() { 122 return new CorrelatedValuePropagation(); 123} 124 125static bool processSelect(SelectInst *S, LazyValueInfo *LVI) { 126 if (S->getType()->isVectorTy()) return false; 127 if (isa<Constant>(S->getCondition())) return false; 128 129 Constant *C = LVI->getConstant(S->getCondition(), S->getParent(), S); 130 if (!C) return false; 131 132 ConstantInt *CI = dyn_cast<ConstantInt>(C); 133 if (!CI) return false; 134 135 Value *ReplaceWith = CI->isOne() ? S->getTrueValue() : S->getFalseValue(); 136 S->replaceAllUsesWith(ReplaceWith); 137 S->eraseFromParent(); 138 139 ++NumSelects; 140 141 return true; 142} 143 144/// Try to simplify a phi with constant incoming values that match the edge 145/// values of a non-constant value on all other edges: 146/// bb0: 147/// %isnull = icmp eq i8* %x, null 148/// br i1 %isnull, label %bb2, label %bb1 149/// bb1: 150/// br label %bb2 151/// bb2: 152/// %r = phi i8* [ %x, %bb1 ], [ null, %bb0 ] 153/// --> 154/// %r = %x 155static 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 constant 183 // incoming values. See if all constant incoming values can be mapped back to 184 // 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 // All constant incoming values map to the same variable along the incoming 193 // edges of the phi. The phi is unnecessary. However, we must drop all 194 // poison-generating flags to ensure that no poison is propagated to the phi 195 // location by performing this substitution. 196 // Warning: If the underlying analysis changes, this may not be enough to 197 // guarantee that poison is not propagated. 198 // TODO: We may be able to re-infer flags by re-analyzing the instruction. 199 if (auto *CommonInst = dyn_cast<Instruction>(CommonValue)) 200 CommonInst->dropPoisonGeneratingFlags(); 201 P->replaceAllUsesWith(CommonValue); 202 P->eraseFromParent(); 203 ++NumPhiCommon; 204 return true; 205} 206 207static bool processPHI(PHINode *P, LazyValueInfo *LVI, DominatorTree *DT, 208 const SimplifyQuery &SQ) { 209 bool Changed = false; 210 211 BasicBlock *BB = P->getParent(); 212 for (unsigned i = 0, e = P->getNumIncomingValues(); i < e; ++i) { 213 Value *Incoming = P->getIncomingValue(i); 214 if (isa<Constant>(Incoming)) continue; 215 216 Value *V = LVI->getConstantOnEdge(Incoming, P->getIncomingBlock(i), BB, P); 217 218 // Look if the incoming value is a select with a scalar condition for which 219 // LVI can tells us the value. In that case replace the incoming value with 220 // the appropriate value of the select. This often allows us to remove the 221 // select later. 222 if (!V) { 223 SelectInst *SI = dyn_cast<SelectInst>(Incoming); 224 if (!SI) continue; 225 226 Value *Condition = SI->getCondition(); 227 if (!Condition->getType()->isVectorTy()) { 228 if (Constant *C = LVI->getConstantOnEdge( 229 Condition, P->getIncomingBlock(i), BB, P)) { 230 if (C->isOneValue()) { 231 V = SI->getTrueValue(); 232 } else if (C->isZeroValue()) { 233 V = SI->getFalseValue(); 234 } 235 // Once LVI learns to handle vector types, we could also add support 236 // for vector type constants that are not all zeroes or all ones. 237 } 238 } 239 240 // Look if the select has a constant but LVI tells us that the incoming 241 // value can never be that constant. In that case replace the incoming 242 // value with the other value of the select. This often allows us to 243 // remove the select later. 244 if (!V) { 245 Constant *C = dyn_cast<Constant>(SI->getFalseValue()); 246 if (!C) continue; 247 248 if (LVI->getPredicateOnEdge(ICmpInst::ICMP_EQ, SI, C, 249 P->getIncomingBlock(i), BB, P) != 250 LazyValueInfo::False) 251 continue; 252 V = SI->getTrueValue(); 253 } 254 255 LLVM_DEBUG(dbgs() << "CVP: Threading PHI over " << *SI << '\n'); 256 } 257 258 P->setIncomingValue(i, V); 259 Changed = true; 260 } 261 262 if (Value *V = SimplifyInstruction(P, SQ)) { 263 P->replaceAllUsesWith(V); 264 P->eraseFromParent(); 265 Changed = true; 266 } 267 268 if (!Changed) 269 Changed = simplifyCommonValuePhi(P, LVI, DT); 270 271 if (Changed) 272 ++NumPhis; 273 274 return Changed; 275} 276 277static bool processMemAccess(Instruction *I, LazyValueInfo *LVI) { 278 Value *Pointer = nullptr; 279 if (LoadInst *L = dyn_cast<LoadInst>(I)) 280 Pointer = L->getPointerOperand(); 281 else 282 Pointer = cast<StoreInst>(I)->getPointerOperand(); 283 284 if (isa<Constant>(Pointer)) return false; 285 286 Constant *C = LVI->getConstant(Pointer, I->getParent(), I); 287 if (!C) return false; 288 289 ++NumMemAccess; 290 I->replaceUsesOfWith(Pointer, C); 291 return true; 292} 293 294/// See if LazyValueInfo's ability to exploit edge conditions or range 295/// information is sufficient to prove this comparison. Even for local 296/// conditions, this can sometimes prove conditions instcombine can't by 297/// exploiting range information. 298static bool processCmp(CmpInst *Cmp, LazyValueInfo *LVI) { 299 Value *Op0 = Cmp->getOperand(0); 300 auto *C = dyn_cast<Constant>(Cmp->getOperand(1)); 301 if (!C) 302 return false; 303 304 // As a policy choice, we choose not to waste compile time on anything where 305 // the comparison is testing local values. While LVI can sometimes reason 306 // about such cases, it's not its primary purpose. We do make sure to do 307 // the block local query for uses from terminator instructions, but that's 308 // handled in the code for each terminator. As an exception, we allow phi 309 // nodes, for which LVI can thread the condition into predecessors. 310 auto *I = dyn_cast<Instruction>(Op0); 311 if (I && I->getParent() == Cmp->getParent() && !isa<PHINode>(I)) 312 return false; 313 314 LazyValueInfo::Tristate Result = 315 LVI->getPredicateAt(Cmp->getPredicate(), Op0, C, Cmp); 316 if (Result == LazyValueInfo::Unknown) 317 return false; 318 319 ++NumCmps; 320 Constant *TorF = ConstantInt::get(Type::getInt1Ty(Cmp->getContext()), Result); 321 Cmp->replaceAllUsesWith(TorF); 322 Cmp->eraseFromParent(); 323 return true; 324} 325 326/// Simplify a switch instruction by removing cases which can never fire. If the 327/// uselessness of a case could be determined locally then constant propagation 328/// would already have figured it out. Instead, walk the predecessors and 329/// statically evaluate cases based on information available on that edge. Cases 330/// that cannot fire no matter what the incoming edge can safely be removed. If 331/// a case fires on every incoming edge then the entire switch can be removed 332/// and replaced with a branch to the case destination. 333static bool processSwitch(SwitchInst *I, LazyValueInfo *LVI, 334 DominatorTree *DT) { 335 DomTreeUpdater DTU(*DT, DomTreeUpdater::UpdateStrategy::Lazy); 336 Value *Cond = I->getCondition(); 337 BasicBlock *BB = I->getParent(); 338 339 // If the condition was defined in same block as the switch then LazyValueInfo 340 // currently won't say anything useful about it, though in theory it could. 341 if (isa<Instruction>(Cond) && cast<Instruction>(Cond)->getParent() == BB) 342 return false; 343 344 // If the switch is unreachable then trying to improve it is a waste of time. 345 pred_iterator PB = pred_begin(BB), PE = pred_end(BB); 346 if (PB == PE) return false; 347 348 // Analyse each switch case in turn. 349 bool Changed = false; 350 DenseMap<BasicBlock*, int> SuccessorsCount; 351 for (auto *Succ : successors(BB)) 352 SuccessorsCount[Succ]++; 353 354 { // Scope for SwitchInstProfUpdateWrapper. It must not live during 355 // ConstantFoldTerminator() as the underlying SwitchInst can be changed. 356 SwitchInstProfUpdateWrapper SI(*I); 357 358 for (auto CI = SI->case_begin(), CE = SI->case_end(); CI != CE;) { 359 ConstantInt *Case = CI->getCaseValue(); 360 361 // Check to see if the switch condition is equal to/not equal to the case 362 // value on every incoming edge, equal/not equal being the same each time. 363 LazyValueInfo::Tristate State = LazyValueInfo::Unknown; 364 for (pred_iterator PI = PB; PI != PE; ++PI) { 365 // Is the switch condition equal to the case value? 366 LazyValueInfo::Tristate Value = LVI->getPredicateOnEdge(CmpInst::ICMP_EQ, 367 Cond, Case, *PI, 368 BB, SI); 369 // Give up on this case if nothing is known. 370 if (Value == LazyValueInfo::Unknown) { 371 State = LazyValueInfo::Unknown; 372 break; 373 } 374 375 // If this was the first edge to be visited, record that all other edges 376 // need to give the same result. 377 if (PI == PB) { 378 State = Value; 379 continue; 380 } 381 382 // If this case is known to fire for some edges and known not to fire for 383 // others then there is nothing we can do - give up. 384 if (Value != State) { 385 State = LazyValueInfo::Unknown; 386 break; 387 } 388 } 389 390 if (State == LazyValueInfo::False) { 391 // This case never fires - remove it. 392 BasicBlock *Succ = CI->getCaseSuccessor(); 393 Succ->removePredecessor(BB); 394 CI = SI.removeCase(CI); 395 CE = SI->case_end(); 396 397 // The condition can be modified by removePredecessor's PHI simplification 398 // logic. 399 Cond = SI->getCondition(); 400 401 ++NumDeadCases; 402 Changed = true; 403 if (--SuccessorsCount[Succ] == 0) 404 DTU.applyUpdatesPermissive({{DominatorTree::Delete, BB, Succ}}); 405 continue; 406 } 407 if (State == LazyValueInfo::True) { 408 // This case always fires. Arrange for the switch to be turned into an 409 // unconditional branch by replacing the switch condition with the case 410 // value. 411 SI->setCondition(Case); 412 NumDeadCases += SI->getNumCases(); 413 Changed = true; 414 break; 415 } 416 417 // Increment the case iterator since we didn't delete it. 418 ++CI; 419 } 420 } 421 422 if (Changed) 423 // If the switch has been simplified to the point where it can be replaced 424 // by a branch then do so now. 425 ConstantFoldTerminator(BB, /*DeleteDeadConditions = */ false, 426 /*TLI = */ nullptr, &DTU); 427 return Changed; 428} 429 430// See if we can prove that the given binary op intrinsic will not overflow. 431static bool willNotOverflow(BinaryOpIntrinsic *BO, LazyValueInfo *LVI) { 432 ConstantRange LRange = LVI->getConstantRange( 433 BO->getLHS(), BO->getParent(), BO); 434 ConstantRange RRange = LVI->getConstantRange( 435 BO->getRHS(), BO->getParent(), BO); 436 ConstantRange NWRegion = ConstantRange::makeGuaranteedNoWrapRegion( 437 BO->getBinaryOp(), RRange, BO->getNoWrapKind()); 438 return NWRegion.contains(LRange); 439} 440 441static void setDeducedOverflowingFlags(Value *V, Instruction::BinaryOps Opcode, 442 bool NewNSW, bool NewNUW) { 443 Statistic *OpcNW, *OpcNSW, *OpcNUW; 444 switch (Opcode) { 445 case Instruction::Add: 446 OpcNW = &NumAddNW; 447 OpcNSW = &NumAddNSW; 448 OpcNUW = &NumAddNUW; 449 break; 450 case Instruction::Sub: 451 OpcNW = &NumSubNW; 452 OpcNSW = &NumSubNSW; 453 OpcNUW = &NumSubNUW; 454 break; 455 case Instruction::Mul: 456 OpcNW = &NumMulNW; 457 OpcNSW = &NumMulNSW; 458 OpcNUW = &NumMulNUW; 459 break; 460 case Instruction::Shl: 461 OpcNW = &NumShlNW; 462 OpcNSW = &NumShlNSW; 463 OpcNUW = &NumShlNUW; 464 break; 465 default: 466 llvm_unreachable("Will not be called with other binops"); 467 } 468 469 auto *Inst = dyn_cast<Instruction>(V); 470 if (NewNSW) { 471 ++NumNW; 472 ++*OpcNW; 473 ++NumNSW; 474 ++*OpcNSW; 475 if (Inst) 476 Inst->setHasNoSignedWrap(); 477 } 478 if (NewNUW) { 479 ++NumNW; 480 ++*OpcNW; 481 ++NumNUW; 482 ++*OpcNUW; 483 if (Inst) 484 Inst->setHasNoUnsignedWrap(); 485 } 486} 487 488static bool processBinOp(BinaryOperator *BinOp, LazyValueInfo *LVI); 489 490// Rewrite this with.overflow intrinsic as non-overflowing. 491static void processOverflowIntrinsic(WithOverflowInst *WO, LazyValueInfo *LVI) { 492 IRBuilder<> B(WO); 493 Instruction::BinaryOps Opcode = WO->getBinaryOp(); 494 bool NSW = WO->isSigned(); 495 bool NUW = !WO->isSigned(); 496 497 Value *NewOp = 498 B.CreateBinOp(Opcode, WO->getLHS(), WO->getRHS(), WO->getName()); 499 setDeducedOverflowingFlags(NewOp, Opcode, NSW, NUW); 500 501 StructType *ST = cast<StructType>(WO->getType()); 502 Constant *Struct = ConstantStruct::get(ST, 503 { UndefValue::get(ST->getElementType(0)), 504 ConstantInt::getFalse(ST->getElementType(1)) }); 505 Value *NewI = B.CreateInsertValue(Struct, NewOp, 0); 506 WO->replaceAllUsesWith(NewI); 507 WO->eraseFromParent(); 508 ++NumOverflows; 509 510 // See if we can infer the other no-wrap too. 511 if (auto *BO = dyn_cast<BinaryOperator>(NewOp)) 512 processBinOp(BO, LVI); 513} 514 515static void processSaturatingInst(SaturatingInst *SI, LazyValueInfo *LVI) { 516 Instruction::BinaryOps Opcode = SI->getBinaryOp(); 517 bool NSW = SI->isSigned(); 518 bool NUW = !SI->isSigned(); 519 BinaryOperator *BinOp = BinaryOperator::Create( 520 Opcode, SI->getLHS(), SI->getRHS(), SI->getName(), SI); 521 BinOp->setDebugLoc(SI->getDebugLoc()); 522 setDeducedOverflowingFlags(BinOp, Opcode, NSW, NUW); 523 524 SI->replaceAllUsesWith(BinOp); 525 SI->eraseFromParent(); 526 ++NumSaturating; 527 528 // See if we can infer the other no-wrap too. 529 if (auto *BO = dyn_cast<BinaryOperator>(BinOp)) 530 processBinOp(BO, LVI); 531} 532 533/// Infer nonnull attributes for the arguments at the specified callsite. 534static bool processCallSite(CallBase &CB, LazyValueInfo *LVI) { 535 SmallVector<unsigned, 4> ArgNos; 536 unsigned ArgNo = 0; 537 538 if (auto *WO = dyn_cast<WithOverflowInst>(&CB)) { 539 if (WO->getLHS()->getType()->isIntegerTy() && willNotOverflow(WO, LVI)) { 540 processOverflowIntrinsic(WO, LVI); 541 return true; 542 } 543 } 544 545 if (auto *SI = dyn_cast<SaturatingInst>(&CB)) { 546 if (SI->getType()->isIntegerTy() && willNotOverflow(SI, LVI)) { 547 processSaturatingInst(SI, LVI); 548 return true; 549 } 550 } 551 552 // Deopt bundle operands are intended to capture state with minimal 553 // perturbance of the code otherwise. If we can find a constant value for 554 // any such operand and remove a use of the original value, that's 555 // desireable since it may allow further optimization of that value (e.g. via 556 // single use rules in instcombine). Since deopt uses tend to, 557 // idiomatically, appear along rare conditional paths, it's reasonable likely 558 // we may have a conditional fact with which LVI can fold. 559 if (auto DeoptBundle = CB.getOperandBundle(LLVMContext::OB_deopt)) { 560 bool Progress = false; 561 for (const Use &ConstU : DeoptBundle->Inputs) { 562 Use &U = const_cast<Use&>(ConstU); 563 Value *V = U.get(); 564 if (V->getType()->isVectorTy()) continue; 565 if (isa<Constant>(V)) continue; 566 567 Constant *C = LVI->getConstant(V, CB.getParent(), &CB); 568 if (!C) continue; 569 U.set(C); 570 Progress = true; 571 } 572 if (Progress) 573 return true; 574 } 575 576 for (Value *V : CB.args()) { 577 PointerType *Type = dyn_cast<PointerType>(V->getType()); 578 // Try to mark pointer typed parameters as non-null. We skip the 579 // relatively expensive analysis for constants which are obviously either 580 // null or non-null to start with. 581 if (Type && !CB.paramHasAttr(ArgNo, Attribute::NonNull) && 582 !isa<Constant>(V) && 583 LVI->getPredicateAt(ICmpInst::ICMP_EQ, V, 584 ConstantPointerNull::get(Type), 585 &CB) == LazyValueInfo::False) 586 ArgNos.push_back(ArgNo); 587 ArgNo++; 588 } 589 590 assert(ArgNo == CB.arg_size() && "sanity check"); 591 592 if (ArgNos.empty()) 593 return false; 594 595 AttributeList AS = CB.getAttributes(); 596 LLVMContext &Ctx = CB.getContext(); 597 AS = AS.addParamAttribute(Ctx, ArgNos, 598 Attribute::get(Ctx, Attribute::NonNull)); 599 CB.setAttributes(AS); 600 601 return true; 602} 603 604static bool hasPositiveOperands(BinaryOperator *SDI, LazyValueInfo *LVI) { 605 Constant *Zero = ConstantInt::get(SDI->getType(), 0); 606 for (Value *O : SDI->operands()) { 607 auto Result = LVI->getPredicateAt(ICmpInst::ICMP_SGE, O, Zero, SDI); 608 if (Result != LazyValueInfo::True) 609 return false; 610 } 611 return true; 612} 613 614/// Try to shrink a udiv/urem's width down to the smallest power of two that's 615/// sufficient to contain its operands. 616static bool processUDivOrURem(BinaryOperator *Instr, LazyValueInfo *LVI) { 617 assert(Instr->getOpcode() == Instruction::UDiv || 618 Instr->getOpcode() == Instruction::URem); 619 if (Instr->getType()->isVectorTy()) 620 return false; 621 622 // Find the smallest power of two bitwidth that's sufficient to hold Instr's 623 // operands. 624 auto OrigWidth = Instr->getType()->getIntegerBitWidth(); 625 ConstantRange OperandRange(OrigWidth, /*isFullSet=*/false); 626 for (Value *Operand : Instr->operands()) { 627 OperandRange = OperandRange.unionWith( 628 LVI->getConstantRange(Operand, Instr->getParent())); 629 } 630 // Don't shrink below 8 bits wide. 631 unsigned NewWidth = std::max<unsigned>( 632 PowerOf2Ceil(OperandRange.getUnsignedMax().getActiveBits()), 8); 633 // NewWidth might be greater than OrigWidth if OrigWidth is not a power of 634 // two. 635 if (NewWidth >= OrigWidth) 636 return false; 637 638 ++NumUDivs; 639 IRBuilder<> B{Instr}; 640 auto *TruncTy = Type::getIntNTy(Instr->getContext(), NewWidth); 641 auto *LHS = B.CreateTruncOrBitCast(Instr->getOperand(0), TruncTy, 642 Instr->getName() + ".lhs.trunc"); 643 auto *RHS = B.CreateTruncOrBitCast(Instr->getOperand(1), TruncTy, 644 Instr->getName() + ".rhs.trunc"); 645 auto *BO = B.CreateBinOp(Instr->getOpcode(), LHS, RHS, Instr->getName()); 646 auto *Zext = B.CreateZExt(BO, Instr->getType(), Instr->getName() + ".zext"); 647 if (auto *BinOp = dyn_cast<BinaryOperator>(BO)) 648 if (BinOp->getOpcode() == Instruction::UDiv) 649 BinOp->setIsExact(Instr->isExact()); 650 651 Instr->replaceAllUsesWith(Zext); 652 Instr->eraseFromParent(); 653 return true; 654} 655 656static bool processSRem(BinaryOperator *SDI, LazyValueInfo *LVI) { 657 if (SDI->getType()->isVectorTy() || !hasPositiveOperands(SDI, LVI)) 658 return false; 659 660 ++NumSRems; 661 auto *BO = BinaryOperator::CreateURem(SDI->getOperand(0), SDI->getOperand(1), 662 SDI->getName(), SDI); 663 BO->setDebugLoc(SDI->getDebugLoc()); 664 SDI->replaceAllUsesWith(BO); 665 SDI->eraseFromParent(); 666 667 // Try to process our new urem. 668 processUDivOrURem(BO, LVI); 669 670 return true; 671} 672 673/// See if LazyValueInfo's ability to exploit edge conditions or range 674/// information is sufficient to prove the both operands of this SDiv are 675/// positive. If this is the case, replace the SDiv with a UDiv. Even for local 676/// conditions, this can sometimes prove conditions instcombine can't by 677/// exploiting range information. 678static bool processSDiv(BinaryOperator *SDI, LazyValueInfo *LVI) { 679 if (SDI->getType()->isVectorTy() || !hasPositiveOperands(SDI, LVI)) 680 return false; 681 682 ++NumSDivs; 683 auto *BO = BinaryOperator::CreateUDiv(SDI->getOperand(0), SDI->getOperand(1), 684 SDI->getName(), SDI); 685 BO->setDebugLoc(SDI->getDebugLoc()); 686 BO->setIsExact(SDI->isExact()); 687 SDI->replaceAllUsesWith(BO); 688 SDI->eraseFromParent(); 689 690 // Try to simplify our new udiv. 691 processUDivOrURem(BO, LVI); 692 693 return true; 694} 695 696static bool processAShr(BinaryOperator *SDI, LazyValueInfo *LVI) { 697 if (SDI->getType()->isVectorTy()) 698 return false; 699 700 Constant *Zero = ConstantInt::get(SDI->getType(), 0); 701 if (LVI->getPredicateAt(ICmpInst::ICMP_SGE, SDI->getOperand(0), Zero, SDI) != 702 LazyValueInfo::True) 703 return false; 704 705 ++NumAShrs; 706 auto *BO = BinaryOperator::CreateLShr(SDI->getOperand(0), SDI->getOperand(1), 707 SDI->getName(), SDI); 708 BO->setDebugLoc(SDI->getDebugLoc()); 709 BO->setIsExact(SDI->isExact()); 710 SDI->replaceAllUsesWith(BO); 711 SDI->eraseFromParent(); 712 713 return true; 714} 715 716static bool processSExt(SExtInst *SDI, LazyValueInfo *LVI) { 717 if (SDI->getType()->isVectorTy()) 718 return false; 719 720 Value *Base = SDI->getOperand(0); 721 722 Constant *Zero = ConstantInt::get(Base->getType(), 0); 723 if (LVI->getPredicateAt(ICmpInst::ICMP_SGE, Base, Zero, SDI) != 724 LazyValueInfo::True) 725 return false; 726 727 ++NumSExt; 728 auto *ZExt = 729 CastInst::CreateZExtOrBitCast(Base, SDI->getType(), SDI->getName(), SDI); 730 ZExt->setDebugLoc(SDI->getDebugLoc()); 731 SDI->replaceAllUsesWith(ZExt); 732 SDI->eraseFromParent(); 733 734 return true; 735} 736 737static bool processBinOp(BinaryOperator *BinOp, LazyValueInfo *LVI) { 738 using OBO = OverflowingBinaryOperator; 739 740 if (DontAddNoWrapFlags) 741 return false; 742 743 if (BinOp->getType()->isVectorTy()) 744 return false; 745 746 bool NSW = BinOp->hasNoSignedWrap(); 747 bool NUW = BinOp->hasNoUnsignedWrap(); 748 if (NSW && NUW) 749 return false; 750 751 BasicBlock *BB = BinOp->getParent(); 752 753 Instruction::BinaryOps Opcode = BinOp->getOpcode(); 754 Value *LHS = BinOp->getOperand(0); 755 Value *RHS = BinOp->getOperand(1); 756 757 ConstantRange LRange = LVI->getConstantRange(LHS, BB, BinOp); 758 ConstantRange RRange = LVI->getConstantRange(RHS, BB, BinOp); 759 760 bool Changed = false; 761 bool NewNUW = false, NewNSW = false; 762 if (!NUW) { 763 ConstantRange NUWRange = ConstantRange::makeGuaranteedNoWrapRegion( 764 Opcode, RRange, OBO::NoUnsignedWrap); 765 NewNUW = NUWRange.contains(LRange); 766 Changed |= NewNUW; 767 } 768 if (!NSW) { 769 ConstantRange NSWRange = ConstantRange::makeGuaranteedNoWrapRegion( 770 Opcode, RRange, OBO::NoSignedWrap); 771 NewNSW = NSWRange.contains(LRange); 772 Changed |= NewNSW; 773 } 774 775 setDeducedOverflowingFlags(BinOp, Opcode, NewNSW, NewNUW); 776 777 return Changed; 778} 779 780static bool processAnd(BinaryOperator *BinOp, LazyValueInfo *LVI) { 781 if (BinOp->getType()->isVectorTy()) 782 return false; 783 784 // Pattern match (and lhs, C) where C includes a superset of bits which might 785 // be set in lhs. This is a common truncation idiom created by instcombine. 786 BasicBlock *BB = BinOp->getParent(); 787 Value *LHS = BinOp->getOperand(0); 788 ConstantInt *RHS = dyn_cast<ConstantInt>(BinOp->getOperand(1)); 789 if (!RHS || !RHS->getValue().isMask()) 790 return false; 791 792 // We can only replace the AND with LHS based on range info if the range does 793 // not include undef. 794 ConstantRange LRange = 795 LVI->getConstantRange(LHS, BB, BinOp, /*UndefAllowed=*/false); 796 if (!LRange.getUnsignedMax().ule(RHS->getValue())) 797 return false; 798 799 BinOp->replaceAllUsesWith(LHS); 800 BinOp->eraseFromParent(); 801 NumAnd++; 802 return true; 803} 804 805 806static Constant *getConstantAt(Value *V, Instruction *At, LazyValueInfo *LVI) { 807 if (Constant *C = LVI->getConstant(V, At->getParent(), At)) 808 return C; 809 810 // TODO: The following really should be sunk inside LVI's core algorithm, or 811 // at least the outer shims around such. 812 auto *C = dyn_cast<CmpInst>(V); 813 if (!C) return nullptr; 814 815 Value *Op0 = C->getOperand(0); 816 Constant *Op1 = dyn_cast<Constant>(C->getOperand(1)); 817 if (!Op1) return nullptr; 818 819 LazyValueInfo::Tristate Result = 820 LVI->getPredicateAt(C->getPredicate(), Op0, Op1, At); 821 if (Result == LazyValueInfo::Unknown) 822 return nullptr; 823 824 return (Result == LazyValueInfo::True) ? 825 ConstantInt::getTrue(C->getContext()) : 826 ConstantInt::getFalse(C->getContext()); 827} 828 829static bool runImpl(Function &F, LazyValueInfo *LVI, DominatorTree *DT, 830 const SimplifyQuery &SQ) { 831 bool FnChanged = false; 832 // Visiting in a pre-order depth-first traversal causes us to simplify early 833 // blocks before querying later blocks (which require us to analyze early 834 // blocks). Eagerly simplifying shallow blocks means there is strictly less 835 // work to do for deep blocks. This also means we don't visit unreachable 836 // blocks. 837 for (BasicBlock *BB : depth_first(&F.getEntryBlock())) { 838 bool BBChanged = false; 839 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) { 840 Instruction *II = &*BI++; 841 switch (II->getOpcode()) { 842 case Instruction::Select: 843 BBChanged |= processSelect(cast<SelectInst>(II), LVI); 844 break; 845 case Instruction::PHI: 846 BBChanged |= processPHI(cast<PHINode>(II), LVI, DT, SQ); 847 break; 848 case Instruction::ICmp: 849 case Instruction::FCmp: 850 BBChanged |= processCmp(cast<CmpInst>(II), LVI); 851 break; 852 case Instruction::Load: 853 case Instruction::Store: 854 BBChanged |= processMemAccess(II, LVI); 855 break; 856 case Instruction::Call: 857 case Instruction::Invoke: 858 BBChanged |= processCallSite(cast<CallBase>(*II), LVI); 859 break; 860 case Instruction::SRem: 861 BBChanged |= processSRem(cast<BinaryOperator>(II), LVI); 862 break; 863 case Instruction::SDiv: 864 BBChanged |= processSDiv(cast<BinaryOperator>(II), LVI); 865 break; 866 case Instruction::UDiv: 867 case Instruction::URem: 868 BBChanged |= processUDivOrURem(cast<BinaryOperator>(II), LVI); 869 break; 870 case Instruction::AShr: 871 BBChanged |= processAShr(cast<BinaryOperator>(II), LVI); 872 break; 873 case Instruction::SExt: 874 BBChanged |= processSExt(cast<SExtInst>(II), LVI); 875 break; 876 case Instruction::Add: 877 case Instruction::Sub: 878 case Instruction::Mul: 879 case Instruction::Shl: 880 BBChanged |= processBinOp(cast<BinaryOperator>(II), LVI); 881 break; 882 case Instruction::And: 883 BBChanged |= processAnd(cast<BinaryOperator>(II), LVI); 884 break; 885 } 886 } 887 888 Instruction *Term = BB->getTerminator(); 889 switch (Term->getOpcode()) { 890 case Instruction::Switch: 891 BBChanged |= processSwitch(cast<SwitchInst>(Term), LVI, DT); 892 break; 893 case Instruction::Ret: { 894 auto *RI = cast<ReturnInst>(Term); 895 // Try to determine the return value if we can. This is mainly here to 896 // simplify the writing of unit tests, but also helps to enable IPO by 897 // constant folding the return values of callees. 898 auto *RetVal = RI->getReturnValue(); 899 if (!RetVal) break; // handle "ret void" 900 if (isa<Constant>(RetVal)) break; // nothing to do 901 if (auto *C = getConstantAt(RetVal, RI, LVI)) { 902 ++NumReturns; 903 RI->replaceUsesOfWith(RetVal, C); 904 BBChanged = true; 905 } 906 } 907 } 908 909 FnChanged |= BBChanged; 910 } 911 912 return FnChanged; 913} 914 915bool CorrelatedValuePropagation::runOnFunction(Function &F) { 916 if (skipFunction(F)) 917 return false; 918 919 LazyValueInfo *LVI = &getAnalysis<LazyValueInfoWrapperPass>().getLVI(); 920 DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 921 922 return runImpl(F, LVI, DT, getBestSimplifyQuery(*this, F)); 923} 924 925PreservedAnalyses 926CorrelatedValuePropagationPass::run(Function &F, FunctionAnalysisManager &AM) { 927 LazyValueInfo *LVI = &AM.getResult<LazyValueAnalysis>(F); 928 DominatorTree *DT = &AM.getResult<DominatorTreeAnalysis>(F); 929 930 bool Changed = runImpl(F, LVI, DT, getBestSimplifyQuery(AM, F)); 931 932 if (!Changed) 933 return PreservedAnalyses::all(); 934 PreservedAnalyses PA; 935 PA.preserve<GlobalsAA>(); 936 PA.preserve<DominatorTreeAnalysis>(); 937 PA.preserve<LazyValueAnalysis>(); 938 return PA; 939} 940