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