LLVM  9.0.0svn
CorrelatedValuePropagation.cpp
Go to the documentation of this file.
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 
15 #include "llvm/ADT/Optional.h"
16 #include "llvm/ADT/SmallVector.h"
17 #include "llvm/ADT/Statistic.h"
22 #include "llvm/IR/Attributes.h"
23 #include "llvm/IR/BasicBlock.h"
24 #include "llvm/IR/CFG.h"
25 #include "llvm/IR/CallSite.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/Pass.h"
41 #include "llvm/Support/Casting.h"
43 #include "llvm/Support/Debug.h"
45 #include "llvm/Transforms/Scalar.h"
47 #include <cassert>
48 #include <utility>
49 
50 using namespace llvm;
51 
52 #define DEBUG_TYPE "correlated-value-propagation"
53 
54 STATISTIC(NumPhis, "Number of phis propagated");
55 STATISTIC(NumPhiCommon, "Number of phis deleted via common incoming value");
56 STATISTIC(NumSelects, "Number of selects propagated");
57 STATISTIC(NumMemAccess, "Number of memory access targets propagated");
58 STATISTIC(NumCmps, "Number of comparisons propagated");
59 STATISTIC(NumReturns, "Number of return values propagated");
60 STATISTIC(NumDeadCases, "Number of switch cases removed");
61 STATISTIC(NumSDivs, "Number of sdiv converted to udiv");
62 STATISTIC(NumUDivs, "Number of udivs whose width was decreased");
63 STATISTIC(NumAShrs, "Number of ashr converted to lshr");
64 STATISTIC(NumSRems, "Number of srem converted to urem");
65 STATISTIC(NumOverflows, "Number of overflow checks removed");
66 STATISTIC(NumSaturating,
67  "Number of saturating arithmetics converted to normal arithmetics");
68 
69 static cl::opt<bool> DontAddNoWrapFlags("cvp-dont-add-nowrap-flags", cl::init(false));
70 
71 namespace {
72 
73  class CorrelatedValuePropagation : public FunctionPass {
74  public:
75  static char ID;
76 
77  CorrelatedValuePropagation(): FunctionPass(ID) {
79  }
80 
81  bool runOnFunction(Function &F) override;
82 
83  void getAnalysisUsage(AnalysisUsage &AU) const override {
88  }
89  };
90 
91 } // end anonymous namespace
92 
94 
95 INITIALIZE_PASS_BEGIN(CorrelatedValuePropagation, "correlated-propagation",
96  "Value Propagation", false, false)
99 INITIALIZE_PASS_END(CorrelatedValuePropagation, "correlated-propagation",
100  "Value Propagation", false, false)
101 
102 // Public interface to the Value Propagation pass
104  return new CorrelatedValuePropagation();
105 }
106 
107 static bool processSelect(SelectInst *S, LazyValueInfo *LVI) {
108  if (S->getType()->isVectorTy()) return false;
109  if (isa<Constant>(S->getOperand(0))) return false;
110 
111  Constant *C = LVI->getConstant(S->getCondition(), S->getParent(), S);
112  if (!C) return false;
113 
115  if (!CI) return false;
116 
117  Value *ReplaceWith = S->getTrueValue();
118  Value *Other = S->getFalseValue();
119  if (!CI->isOne()) std::swap(ReplaceWith, Other);
120  if (ReplaceWith == S) ReplaceWith = UndefValue::get(S->getType());
121 
122  S->replaceAllUsesWith(ReplaceWith);
123  S->eraseFromParent();
124 
125  ++NumSelects;
126 
127  return true;
128 }
129 
130 /// Try to simplify a phi with constant incoming values that match the edge
131 /// values of a non-constant value on all other edges:
132 /// bb0:
133 /// %isnull = icmp eq i8* %x, null
134 /// br i1 %isnull, label %bb2, label %bb1
135 /// bb1:
136 /// br label %bb2
137 /// bb2:
138 /// %r = phi i8* [ %x, %bb1 ], [ null, %bb0 ]
139 /// -->
140 /// %r = %x
142  DominatorTree *DT) {
143  // Collect incoming constants and initialize possible common value.
144  SmallVector<std::pair<Constant *, unsigned>, 4> IncomingConstants;
145  Value *CommonValue = nullptr;
146  for (unsigned i = 0, e = P->getNumIncomingValues(); i != e; ++i) {
147  Value *Incoming = P->getIncomingValue(i);
148  if (auto *IncomingConstant = dyn_cast<Constant>(Incoming)) {
149  IncomingConstants.push_back(std::make_pair(IncomingConstant, i));
150  } else if (!CommonValue) {
151  // The potential common value is initialized to the first non-constant.
152  CommonValue = Incoming;
153  } else if (Incoming != CommonValue) {
154  // There can be only one non-constant common value.
155  return false;
156  }
157  }
158 
159  if (!CommonValue || IncomingConstants.empty())
160  return false;
161 
162  // The common value must be valid in all incoming blocks.
163  BasicBlock *ToBB = P->getParent();
164  if (auto *CommonInst = dyn_cast<Instruction>(CommonValue))
165  if (!DT->dominates(CommonInst, ToBB))
166  return false;
167 
168  // We have a phi with exactly 1 variable incoming value and 1 or more constant
169  // incoming values. See if all constant incoming values can be mapped back to
170  // the same incoming variable value.
171  for (auto &IncomingConstant : IncomingConstants) {
172  Constant *C = IncomingConstant.first;
173  BasicBlock *IncomingBB = P->getIncomingBlock(IncomingConstant.second);
174  if (C != LVI->getConstantOnEdge(CommonValue, IncomingBB, ToBB, P))
175  return false;
176  }
177 
178  // All constant incoming values map to the same variable along the incoming
179  // edges of the phi. The phi is unnecessary.
180  P->replaceAllUsesWith(CommonValue);
181  P->eraseFromParent();
182  ++NumPhiCommon;
183  return true;
184 }
185 
187  const SimplifyQuery &SQ) {
188  bool Changed = false;
189 
190  BasicBlock *BB = P->getParent();
191  for (unsigned i = 0, e = P->getNumIncomingValues(); i < e; ++i) {
192  Value *Incoming = P->getIncomingValue(i);
193  if (isa<Constant>(Incoming)) continue;
194 
195  Value *V = LVI->getConstantOnEdge(Incoming, P->getIncomingBlock(i), BB, P);
196 
197  // Look if the incoming value is a select with a scalar condition for which
198  // LVI can tells us the value. In that case replace the incoming value with
199  // the appropriate value of the select. This often allows us to remove the
200  // select later.
201  if (!V) {
202  SelectInst *SI = dyn_cast<SelectInst>(Incoming);
203  if (!SI) continue;
204 
205  Value *Condition = SI->getCondition();
206  if (!Condition->getType()->isVectorTy()) {
207  if (Constant *C = LVI->getConstantOnEdge(
208  Condition, P->getIncomingBlock(i), BB, P)) {
209  if (C->isOneValue()) {
210  V = SI->getTrueValue();
211  } else if (C->isZeroValue()) {
212  V = SI->getFalseValue();
213  }
214  // Once LVI learns to handle vector types, we could also add support
215  // for vector type constants that are not all zeroes or all ones.
216  }
217  }
218 
219  // Look if the select has a constant but LVI tells us that the incoming
220  // value can never be that constant. In that case replace the incoming
221  // value with the other value of the select. This often allows us to
222  // remove the select later.
223  if (!V) {
225  if (!C) continue;
226 
227  if (LVI->getPredicateOnEdge(ICmpInst::ICMP_EQ, SI, C,
228  P->getIncomingBlock(i), BB, P) !=
230  continue;
231  V = SI->getTrueValue();
232  }
233 
234  LLVM_DEBUG(dbgs() << "CVP: Threading PHI over " << *SI << '\n');
235  }
236 
237  P->setIncomingValue(i, V);
238  Changed = true;
239  }
240 
241  if (Value *V = SimplifyInstruction(P, SQ)) {
242  P->replaceAllUsesWith(V);
243  P->eraseFromParent();
244  Changed = true;
245  }
246 
247  if (!Changed)
248  Changed = simplifyCommonValuePhi(P, LVI, DT);
249 
250  if (Changed)
251  ++NumPhis;
252 
253  return Changed;
254 }
255 
257  Value *Pointer = nullptr;
258  if (LoadInst *L = dyn_cast<LoadInst>(I))
259  Pointer = L->getPointerOperand();
260  else
261  Pointer = cast<StoreInst>(I)->getPointerOperand();
262 
263  if (isa<Constant>(Pointer)) return false;
264 
265  Constant *C = LVI->getConstant(Pointer, I->getParent(), I);
266  if (!C) return false;
267 
268  ++NumMemAccess;
269  I->replaceUsesOfWith(Pointer, C);
270  return true;
271 }
272 
273 /// See if LazyValueInfo's ability to exploit edge conditions or range
274 /// information is sufficient to prove this comparison. Even for local
275 /// conditions, this can sometimes prove conditions instcombine can't by
276 /// exploiting range information.
277 static bool processCmp(CmpInst *Cmp, LazyValueInfo *LVI) {
278  Value *Op0 = Cmp->getOperand(0);
279  auto *C = dyn_cast<Constant>(Cmp->getOperand(1));
280  if (!C)
281  return false;
282 
283  // As a policy choice, we choose not to waste compile time on anything where
284  // the comparison is testing local values. While LVI can sometimes reason
285  // about such cases, it's not its primary purpose. We do make sure to do
286  // the block local query for uses from terminator instructions, but that's
287  // handled in the code for each terminator.
288  auto *I = dyn_cast<Instruction>(Op0);
289  if (I && I->getParent() == Cmp->getParent())
290  return false;
291 
292  LazyValueInfo::Tristate Result =
293  LVI->getPredicateAt(Cmp->getPredicate(), Op0, C, Cmp);
294  if (Result == LazyValueInfo::Unknown)
295  return false;
296 
297  ++NumCmps;
298  Constant *TorF = ConstantInt::get(Type::getInt1Ty(Cmp->getContext()), Result);
299  Cmp->replaceAllUsesWith(TorF);
300  Cmp->eraseFromParent();
301  return true;
302 }
303 
304 /// Simplify a switch instruction by removing cases which can never fire. If the
305 /// uselessness of a case could be determined locally then constant propagation
306 /// would already have figured it out. Instead, walk the predecessors and
307 /// statically evaluate cases based on information available on that edge. Cases
308 /// that cannot fire no matter what the incoming edge can safely be removed. If
309 /// a case fires on every incoming edge then the entire switch can be removed
310 /// and replaced with a branch to the case destination.
312  DominatorTree *DT) {
314  Value *Cond = I->getCondition();
315  BasicBlock *BB = I->getParent();
316 
317  // If the condition was defined in same block as the switch then LazyValueInfo
318  // currently won't say anything useful about it, though in theory it could.
319  if (isa<Instruction>(Cond) && cast<Instruction>(Cond)->getParent() == BB)
320  return false;
321 
322  // If the switch is unreachable then trying to improve it is a waste of time.
323  pred_iterator PB = pred_begin(BB), PE = pred_end(BB);
324  if (PB == PE) return false;
325 
326  // Analyse each switch case in turn.
327  bool Changed = false;
328  DenseMap<BasicBlock*, int> SuccessorsCount;
329  for (auto *Succ : successors(BB))
330  SuccessorsCount[Succ]++;
331 
332  { // Scope for SwitchInstProfUpdateWrapper. It must not live during
333  // ConstantFoldTerminator() as the underlying SwitchInst can be changed.
335 
336  for (auto CI = SI->case_begin(), CE = SI->case_end(); CI != CE;) {
337  ConstantInt *Case = CI->getCaseValue();
338 
339  // Check to see if the switch condition is equal to/not equal to the case
340  // value on every incoming edge, equal/not equal being the same each time.
342  for (pred_iterator PI = PB; PI != PE; ++PI) {
343  // Is the switch condition equal to the case value?
345  Cond, Case, *PI,
346  BB, SI);
347  // Give up on this case if nothing is known.
348  if (Value == LazyValueInfo::Unknown) {
349  State = LazyValueInfo::Unknown;
350  break;
351  }
352 
353  // If this was the first edge to be visited, record that all other edges
354  // need to give the same result.
355  if (PI == PB) {
356  State = Value;
357  continue;
358  }
359 
360  // If this case is known to fire for some edges and known not to fire for
361  // others then there is nothing we can do - give up.
362  if (Value != State) {
363  State = LazyValueInfo::Unknown;
364  break;
365  }
366  }
367 
368  if (State == LazyValueInfo::False) {
369  // This case never fires - remove it.
370  BasicBlock *Succ = CI->getCaseSuccessor();
371  Succ->removePredecessor(BB);
372  CI = SI.removeCase(CI);
373  CE = SI->case_end();
374 
375  // The condition can be modified by removePredecessor's PHI simplification
376  // logic.
377  Cond = SI->getCondition();
378 
379  ++NumDeadCases;
380  Changed = true;
381  if (--SuccessorsCount[Succ] == 0)
383  continue;
384  }
385  if (State == LazyValueInfo::True) {
386  // This case always fires. Arrange for the switch to be turned into an
387  // unconditional branch by replacing the switch condition with the case
388  // value.
389  SI->setCondition(Case);
390  NumDeadCases += SI->getNumCases();
391  Changed = true;
392  break;
393  }
394 
395  // Increment the case iterator since we didn't delete it.
396  ++CI;
397  }
398  }
399 
400  if (Changed)
401  // If the switch has been simplified to the point where it can be replaced
402  // by a branch then do so now.
403  ConstantFoldTerminator(BB, /*DeleteDeadConditions = */ false,
404  /*TLI = */ nullptr, &DTU);
405  return Changed;
406 }
407 
408 // See if we can prove that the given binary op intrinsic will not overflow.
410  ConstantRange LRange = LVI->getConstantRange(
411  BO->getLHS(), BO->getParent(), BO);
412  ConstantRange RRange = LVI->getConstantRange(
413  BO->getRHS(), BO->getParent(), BO);
415  BO->getBinaryOp(), RRange, BO->getNoWrapKind());
416  return NWRegion.contains(LRange);
417 }
418 
420  IRBuilder<> B(WO);
421  Value *NewOp = B.CreateBinOp(
422  WO->getBinaryOp(), WO->getLHS(), WO->getRHS(), WO->getName());
423  // Constant-folding could have happened.
424  if (auto *Inst = dyn_cast<Instruction>(NewOp)) {
425  if (WO->isSigned())
426  Inst->setHasNoSignedWrap();
427  else
428  Inst->setHasNoUnsignedWrap();
429  }
430 
431  Value *NewI = B.CreateInsertValue(UndefValue::get(WO->getType()), NewOp, 0);
432  NewI = B.CreateInsertValue(NewI, ConstantInt::getFalse(WO->getContext()), 1);
433  WO->replaceAllUsesWith(NewI);
434  WO->eraseFromParent();
435  ++NumOverflows;
436 }
437 
440  SI->getBinaryOp(), SI->getLHS(), SI->getRHS(), SI->getName(), SI);
441  BinOp->setDebugLoc(SI->getDebugLoc());
442  if (SI->isSigned())
443  BinOp->setHasNoSignedWrap();
444  else
445  BinOp->setHasNoUnsignedWrap();
446 
447  SI->replaceAllUsesWith(BinOp);
448  SI->eraseFromParent();
449  ++NumSaturating;
450 }
451 
452 /// Infer nonnull attributes for the arguments at the specified callsite.
453 static bool processCallSite(CallSite CS, LazyValueInfo *LVI) {
455  unsigned ArgNo = 0;
456 
457  if (auto *WO = dyn_cast<WithOverflowInst>(CS.getInstruction())) {
458  if (WO->getLHS()->getType()->isIntegerTy() && willNotOverflow(WO, LVI)) {
460  return true;
461  }
462  }
463 
464  if (auto *SI = dyn_cast<SaturatingInst>(CS.getInstruction())) {
465  if (SI->getType()->isIntegerTy() && willNotOverflow(SI, LVI)) {
467  return true;
468  }
469  }
470 
471  // Deopt bundle operands are intended to capture state with minimal
472  // perturbance of the code otherwise. If we can find a constant value for
473  // any such operand and remove a use of the original value, that's
474  // desireable since it may allow further optimization of that value (e.g. via
475  // single use rules in instcombine). Since deopt uses tend to,
476  // idiomatically, appear along rare conditional paths, it's reasonable likely
477  // we may have a conditional fact with which LVI can fold.
478  if (auto DeoptBundle = CS.getOperandBundle(LLVMContext::OB_deopt)) {
479  bool Progress = false;
480  for (const Use &ConstU : DeoptBundle->Inputs) {
481  Use &U = const_cast<Use&>(ConstU);
482  Value *V = U.get();
483  if (V->getType()->isVectorTy()) continue;
484  if (isa<Constant>(V)) continue;
485 
486  Constant *C = LVI->getConstant(V, CS.getParent(), CS.getInstruction());
487  if (!C) continue;
488  U.set(C);
489  Progress = true;
490  }
491  if (Progress)
492  return true;
493  }
494 
495  for (Value *V : CS.args()) {
496  PointerType *Type = dyn_cast<PointerType>(V->getType());
497  // Try to mark pointer typed parameters as non-null. We skip the
498  // relatively expensive analysis for constants which are obviously either
499  // null or non-null to start with.
500  if (Type && !CS.paramHasAttr(ArgNo, Attribute::NonNull) &&
501  !isa<Constant>(V) &&
505  ArgNos.push_back(ArgNo);
506  ArgNo++;
507  }
508 
509  assert(ArgNo == CS.arg_size() && "sanity check");
510 
511  if (ArgNos.empty())
512  return false;
513 
514  AttributeList AS = CS.getAttributes();
515  LLVMContext &Ctx = CS.getInstruction()->getContext();
516  AS = AS.addParamAttribute(Ctx, ArgNos,
517  Attribute::get(Ctx, Attribute::NonNull));
518  CS.setAttributes(AS);
519 
520  return true;
521 }
522 
524  Constant *Zero = ConstantInt::get(SDI->getType(), 0);
525  for (Value *O : SDI->operands()) {
526  auto Result = LVI->getPredicateAt(ICmpInst::ICMP_SGE, O, Zero, SDI);
527  if (Result != LazyValueInfo::True)
528  return false;
529  }
530  return true;
531 }
532 
533 /// Try to shrink a udiv/urem's width down to the smallest power of two that's
534 /// sufficient to contain its operands.
535 static bool processUDivOrURem(BinaryOperator *Instr, LazyValueInfo *LVI) {
536  assert(Instr->getOpcode() == Instruction::UDiv ||
537  Instr->getOpcode() == Instruction::URem);
538  if (Instr->getType()->isVectorTy())
539  return false;
540 
541  // Find the smallest power of two bitwidth that's sufficient to hold Instr's
542  // operands.
543  auto OrigWidth = Instr->getType()->getIntegerBitWidth();
544  ConstantRange OperandRange(OrigWidth, /*isFullset=*/false);
545  for (Value *Operand : Instr->operands()) {
546  OperandRange = OperandRange.unionWith(
547  LVI->getConstantRange(Operand, Instr->getParent()));
548  }
549  // Don't shrink below 8 bits wide.
550  unsigned NewWidth = std::max<unsigned>(
551  PowerOf2Ceil(OperandRange.getUnsignedMax().getActiveBits()), 8);
552  // NewWidth might be greater than OrigWidth if OrigWidth is not a power of
553  // two.
554  if (NewWidth >= OrigWidth)
555  return false;
556 
557  ++NumUDivs;
558  IRBuilder<> B{Instr};
559  auto *TruncTy = Type::getIntNTy(Instr->getContext(), NewWidth);
560  auto *LHS = B.CreateTruncOrBitCast(Instr->getOperand(0), TruncTy,
561  Instr->getName() + ".lhs.trunc");
562  auto *RHS = B.CreateTruncOrBitCast(Instr->getOperand(1), TruncTy,
563  Instr->getName() + ".rhs.trunc");
564  auto *BO = B.CreateBinOp(Instr->getOpcode(), LHS, RHS, Instr->getName());
565  auto *Zext = B.CreateZExt(BO, Instr->getType(), Instr->getName() + ".zext");
566  if (auto *BinOp = dyn_cast<BinaryOperator>(BO))
567  if (BinOp->getOpcode() == Instruction::UDiv)
568  BinOp->setIsExact(Instr->isExact());
569 
570  Instr->replaceAllUsesWith(Zext);
571  Instr->eraseFromParent();
572  return true;
573 }
574 
575 static bool processSRem(BinaryOperator *SDI, LazyValueInfo *LVI) {
576  if (SDI->getType()->isVectorTy() || !hasPositiveOperands(SDI, LVI))
577  return false;
578 
579  ++NumSRems;
580  auto *BO = BinaryOperator::CreateURem(SDI->getOperand(0), SDI->getOperand(1),
581  SDI->getName(), SDI);
582  BO->setDebugLoc(SDI->getDebugLoc());
583  SDI->replaceAllUsesWith(BO);
584  SDI->eraseFromParent();
585 
586  // Try to process our new urem.
587  processUDivOrURem(BO, LVI);
588 
589  return true;
590 }
591 
592 /// See if LazyValueInfo's ability to exploit edge conditions or range
593 /// information is sufficient to prove the both operands of this SDiv are
594 /// positive. If this is the case, replace the SDiv with a UDiv. Even for local
595 /// conditions, this can sometimes prove conditions instcombine can't by
596 /// exploiting range information.
597 static bool processSDiv(BinaryOperator *SDI, LazyValueInfo *LVI) {
598  if (SDI->getType()->isVectorTy() || !hasPositiveOperands(SDI, LVI))
599  return false;
600 
601  ++NumSDivs;
602  auto *BO = BinaryOperator::CreateUDiv(SDI->getOperand(0), SDI->getOperand(1),
603  SDI->getName(), SDI);
604  BO->setDebugLoc(SDI->getDebugLoc());
605  BO->setIsExact(SDI->isExact());
606  SDI->replaceAllUsesWith(BO);
607  SDI->eraseFromParent();
608 
609  // Try to simplify our new udiv.
610  processUDivOrURem(BO, LVI);
611 
612  return true;
613 }
614 
615 static bool processAShr(BinaryOperator *SDI, LazyValueInfo *LVI) {
616  if (SDI->getType()->isVectorTy())
617  return false;
618 
619  Constant *Zero = ConstantInt::get(SDI->getType(), 0);
620  if (LVI->getPredicateAt(ICmpInst::ICMP_SGE, SDI->getOperand(0), Zero, SDI) !=
622  return false;
623 
624  ++NumAShrs;
625  auto *BO = BinaryOperator::CreateLShr(SDI->getOperand(0), SDI->getOperand(1),
626  SDI->getName(), SDI);
627  BO->setDebugLoc(SDI->getDebugLoc());
628  BO->setIsExact(SDI->isExact());
629  SDI->replaceAllUsesWith(BO);
630  SDI->eraseFromParent();
631 
632  return true;
633 }
634 
635 static bool processBinOp(BinaryOperator *BinOp, LazyValueInfo *LVI) {
636  using OBO = OverflowingBinaryOperator;
637 
638  if (DontAddNoWrapFlags)
639  return false;
640 
641  if (BinOp->getType()->isVectorTy())
642  return false;
643 
644  bool NSW = BinOp->hasNoSignedWrap();
645  bool NUW = BinOp->hasNoUnsignedWrap();
646  if (NSW && NUW)
647  return false;
648 
649  BasicBlock *BB = BinOp->getParent();
650 
651  Value *LHS = BinOp->getOperand(0);
652  Value *RHS = BinOp->getOperand(1);
653 
654  ConstantRange LRange = LVI->getConstantRange(LHS, BB, BinOp);
655  ConstantRange RRange = LVI->getConstantRange(RHS, BB, BinOp);
656 
657  bool Changed = false;
658  if (!NUW) {
660  BinOp->getOpcode(), RRange, OBO::NoUnsignedWrap);
661  bool NewNUW = NUWRange.contains(LRange);
662  BinOp->setHasNoUnsignedWrap(NewNUW);
663  Changed |= NewNUW;
664  }
665  if (!NSW) {
667  BinOp->getOpcode(), RRange, OBO::NoSignedWrap);
668  bool NewNSW = NSWRange.contains(LRange);
669  BinOp->setHasNoSignedWrap(NewNSW);
670  Changed |= NewNSW;
671  }
672 
673  return Changed;
674 }
675 
677  if (Constant *C = LVI->getConstant(V, At->getParent(), At))
678  return C;
679 
680  // TODO: The following really should be sunk inside LVI's core algorithm, or
681  // at least the outer shims around such.
682  auto *C = dyn_cast<CmpInst>(V);
683  if (!C) return nullptr;
684 
685  Value *Op0 = C->getOperand(0);
686  Constant *Op1 = dyn_cast<Constant>(C->getOperand(1));
687  if (!Op1) return nullptr;
688 
689  LazyValueInfo::Tristate Result =
690  LVI->getPredicateAt(C->getPredicate(), Op0, Op1, At);
691  if (Result == LazyValueInfo::Unknown)
692  return nullptr;
693 
694  return (Result == LazyValueInfo::True) ?
697 }
698 
699 static bool runImpl(Function &F, LazyValueInfo *LVI, DominatorTree *DT,
700  const SimplifyQuery &SQ) {
701  bool FnChanged = false;
702  // Visiting in a pre-order depth-first traversal causes us to simplify early
703  // blocks before querying later blocks (which require us to analyze early
704  // blocks). Eagerly simplifying shallow blocks means there is strictly less
705  // work to do for deep blocks. This also means we don't visit unreachable
706  // blocks.
707  for (BasicBlock *BB : depth_first(&F.getEntryBlock())) {
708  bool BBChanged = false;
709  for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) {
710  Instruction *II = &*BI++;
711  switch (II->getOpcode()) {
712  case Instruction::Select:
713  BBChanged |= processSelect(cast<SelectInst>(II), LVI);
714  break;
715  case Instruction::PHI:
716  BBChanged |= processPHI(cast<PHINode>(II), LVI, DT, SQ);
717  break;
718  case Instruction::ICmp:
719  case Instruction::FCmp:
720  BBChanged |= processCmp(cast<CmpInst>(II), LVI);
721  break;
722  case Instruction::Load:
723  case Instruction::Store:
724  BBChanged |= processMemAccess(II, LVI);
725  break;
726  case Instruction::Call:
727  case Instruction::Invoke:
728  BBChanged |= processCallSite(CallSite(II), LVI);
729  break;
730  case Instruction::SRem:
731  BBChanged |= processSRem(cast<BinaryOperator>(II), LVI);
732  break;
733  case Instruction::SDiv:
734  BBChanged |= processSDiv(cast<BinaryOperator>(II), LVI);
735  break;
736  case Instruction::UDiv:
737  case Instruction::URem:
738  BBChanged |= processUDivOrURem(cast<BinaryOperator>(II), LVI);
739  break;
740  case Instruction::AShr:
741  BBChanged |= processAShr(cast<BinaryOperator>(II), LVI);
742  break;
743  case Instruction::Add:
744  case Instruction::Sub:
745  BBChanged |= processBinOp(cast<BinaryOperator>(II), LVI);
746  break;
747  }
748  }
749 
750  Instruction *Term = BB->getTerminator();
751  switch (Term->getOpcode()) {
752  case Instruction::Switch:
753  BBChanged |= processSwitch(cast<SwitchInst>(Term), LVI, DT);
754  break;
755  case Instruction::Ret: {
756  auto *RI = cast<ReturnInst>(Term);
757  // Try to determine the return value if we can. This is mainly here to
758  // simplify the writing of unit tests, but also helps to enable IPO by
759  // constant folding the return values of callees.
760  auto *RetVal = RI->getReturnValue();
761  if (!RetVal) break; // handle "ret void"
762  if (isa<Constant>(RetVal)) break; // nothing to do
763  if (auto *C = getConstantAt(RetVal, RI, LVI)) {
764  ++NumReturns;
765  RI->replaceUsesOfWith(RetVal, C);
766  BBChanged = true;
767  }
768  }
769  }
770 
771  FnChanged |= BBChanged;
772  }
773 
774  return FnChanged;
775 }
776 
778  if (skipFunction(F))
779  return false;
780 
781  LazyValueInfo *LVI = &getAnalysis<LazyValueInfoWrapperPass>().getLVI();
782  DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
783 
784  return runImpl(F, LVI, DT, getBestSimplifyQuery(*this, F));
785 }
786 
791 
792  bool Changed = runImpl(F, LVI, DT, getBestSimplifyQuery(AM, F));
793 
794  if (!Changed)
795  return PreservedAnalyses::all();
797  PA.preserve<GlobalsAA>();
799  return PA;
800 }
Legacy wrapper pass to provide the GlobalsAAResult object.
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:80
uint64_t CallInst * C
unsigned getNumCases() const
Return the number of &#39;cases&#39; in this switch instruction, excluding the default case.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:67
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:594
CaseIt case_end()
Returns a read/write iterator that points one past the last in the SwitchInst.
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:722
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
static IntegerType * getInt1Ty(LLVMContext &C)
Definition: Type.cpp:172
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Value * getPointerOperand(Value *V)
A helper function that returns the pointer operand of a load, store or GEP instruction.
Value * CreateBinOp(Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:1458
ConstantRange getConstantRange(Value *V, BasicBlock *BB, Instruction *CxtI=nullptr)
Return the ConstantRange constraint that is known to hold for the specified value at the end of the s...
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:776
This class represents lattice values for constants.
Definition: AllocatorList.h:23
BinaryOps getOpcode() const
Definition: InstrTypes.h:402
static bool processPHI(PHINode *P, LazyValueInfo *LVI, DominatorTree *DT, const SimplifyQuery &SQ)
Wrapper around LazyValueInfo.
This is the interface for a simple mod/ref and alias analysis over globals.
bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions=false, const TargetLibraryInfo *TLI=nullptr, DomTreeUpdater *DTU=nullptr)
If a terminator instruction is predicated on a constant value, convert it into an unconditional branc...
Definition: Local.cpp:109
void setAttributes(AttributeList PAL)
Set the parameter attributes of the call.
Definition: CallSite.h:341
Represents an op.with.overflow intrinsic.
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Notify the BasicBlock that the predecessor Pred is no longer able to reach it.
Definition: BasicBlock.cpp:301
static void processOverflowIntrinsic(WithOverflowInst *WO)
Value * getCondition() const
static cl::opt< bool > DontAddNoWrapFlags("cvp-dont-add-nowrap-flags", cl::init(false))
static bool processCmp(CmpInst *Cmp, LazyValueInfo *LVI)
See if LazyValueInfo&#39;s ability to exploit edge conditions or range information is sufficient to prove...
const Value * getTrueValue() const
CaseIt case_begin()
Returns a read/write iterator that points to the first case in the SwitchInst.
A wrapper class to simplify modification of SwitchInst cases along with their prof branch_weights met...
static bool processAShr(BinaryOperator *SDI, LazyValueInfo *LVI)
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:732
STATISTIC(NumFunctions, "Total number of functions")
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:230
F(f)
static bool willNotOverflow(BinaryOpIntrinsic *BO, LazyValueInfo *LVI)
An instruction for reading from memory.
Definition: Instructions.h:167
Optional< OperandBundleUse > getOperandBundle(StringRef Name) const
Definition: CallSite.h:568
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:229
const SimplifyQuery getBestSimplifyQuery(Pass &, Function &)
unsigned getNoWrapKind() const
Returns one of OBO::NoSignedWrap or OBO::NoUnsignedWrap.
bool hasNoSignedWrap() const
Determine whether the no signed wrap flag is set.
Value * get() const
Definition: Use.h:107
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
Constant * getConstant(Value *V, BasicBlock *BB, Instruction *CxtI=nullptr)
Determine whether the specified value is known to be a constant at the end of the specified block...
This class represents the LLVM &#39;select&#39; instruction.
static bool hasPositiveOperands(BinaryOperator *SDI, LazyValueInfo *LVI)
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:779
This file contains the simple types necessary to represent the attributes associated with functions a...
static bool processSelect(SelectInst *S, LazyValueInfo *LVI)
bool contains(const APInt &Val) const
Return true if the specified value is in the set.
ELFYAML::ELF_STO Other
Definition: ELFYAML.cpp:877
static bool runImpl(Function &F, LazyValueInfo *LVI, DominatorTree *DT, const SimplifyQuery &SQ)
InstrTy * getInstruction() const
Definition: CallSite.h:96
unsigned getActiveBits() const
Compute the number of active bits in the value.
Definition: APInt.h:1532
bool isOne() const
This is just a convenience method to make client code smaller for a common case.
Definition: Constants.h:200
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:244
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:125
bool paramHasAttr(unsigned ArgNo, Attribute::AttrKind Kind) const
Return true if the call or the callee has the given attribute.
Definition: CallSite.h:385
Value * getRHS() const
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:429
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
Value * getOperand(unsigned i) const
Definition: User.h:169
Class to represent pointers.
Definition: DerivedTypes.h:544
void replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
Definition: User.cpp:20
SwitchInst::CaseIt removeCase(SwitchInst::CaseIt I)
Delegate the call to the underlying SwitchInst::removeCase() and remove correspondent branch weight...
static bool processUDivOrURem(BinaryOperator *Instr, LazyValueInfo *LVI)
Try to shrink a udiv/urem&#39;s width down to the smallest power of two that&#39;s sufficient to contain its ...
const BasicBlock & getEntryBlock() const
Definition: Function.h:664
Pass * createCorrelatedValuePropagationPass()
static bool runOnFunction(Function &F, bool PostInlining)
#define P(N)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:318
static ConstantPointerNull * get(PointerType *T)
Static factory methods - Return objects of the specified value.
Definition: Constants.cpp:1410
void set(Value *Val)
Definition: Value.h:710
Constant * getConstantOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB, Instruction *CxtI=nullptr)
Determine whether the specified value is known to be a constant on the specified edge.
static bool processSDiv(BinaryOperator *SDI, LazyValueInfo *LVI)
See if LazyValueInfo&#39;s ability to exploit edge conditions or range information is sufficient to prove...
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
LLVM_NODISCARD AttributeList addParamAttribute(LLVMContext &C, unsigned ArgNo, Attribute::AttrKind Kind) const
Add an argument attribute to the list.
Definition: Attributes.h:412
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:45
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:64
This is an important base class in LLVM.
Definition: Constant.h:41
This file contains the declarations for the subclasses of Constant, which represent the different fla...
bool isSigned() const
Whether the intrinsic is signed or unsigned.
AttributeList getAttributes() const
Get the parameter attributes of the call.
Definition: CallSite.h:337
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:112
correlated Value Propagation
APInt getUnsignedMax() const
Return the largest unsigned value contained in the ConstantRange.
Represent the analysis usage information of a pass.
Analysis pass providing a never-invalidated alias analysis result.
Utility class for integer operators which may exhibit overflow - Add, Sub, Mul, and Shl...
Definition: Operator.h:66
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:115
op_range operands()
Definition: User.h:237
void applyUpdatesPermissive(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
static bool processSwitch(SwitchInst *I, LazyValueInfo *LVI, DominatorTree *DT)
Simplify a switch instruction by removing cases which can never fire.
const Value * getCondition() const
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1424
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
bool isExact() const
Determine whether the exact flag is set.
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
iterator_range< IterTy > args() const
Definition: CallSite.h:222
static bool processSRem(BinaryOperator *SDI, LazyValueInfo *LVI)
Tristate
This is used to return true/false/dunno results.
Definition: LazyValueInfo.h:62
Tristate getPredicateOnEdge(unsigned Pred, Value *V, Constant *C, BasicBlock *FromBB, BasicBlock *ToBB, Instruction *CxtI=nullptr)
Determine whether the specified value comparison with a constant is known to be true or false on the ...
Tristate getPredicateAt(unsigned Pred, Value *V, Constant *C, Instruction *CxtI)
Determine whether the specified value comparison with a constant is known to be true or false at the ...
void setHasNoSignedWrap(bool b=true)
Set or clear the nsw flag on this instruction, which must be an operator which supports this flag...
Iterator for intrusive lists based on ilist_node.
This is the shared class of boolean and integer constants.
Definition: Constants.h:83
void initializeCorrelatedValuePropagationPass(PassRegistry &)
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
bool dominates(const Instruction *Def, const Use &U) const
Return true if Def dominates a use in User.
Definition: Dominators.cpp:248
Represents a saturating add/sub intrinsic.
unsigned arg_size() const
Definition: CallSite.h:226
This class represents a range of values.
Definition: ConstantRange.h:47
INITIALIZE_PASS_BEGIN(CorrelatedValuePropagation, "correlated-propagation", "Value Propagation", false, false) INITIALIZE_PASS_END(CorrelatedValuePropagation
static IntegerType * getIntNTy(LLVMContext &C, unsigned N)
Definition: Type.cpp:179
static Constant * get(Type *Ty, uint64_t V, bool isSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:631
static bool processBinOp(BinaryOperator *BinOp, LazyValueInfo *LVI)
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:587
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:940
BBTy * getParent() const
Get the basic block containing the call site.
Definition: CallSite.h:101
static BinaryOperator * Create(BinaryOps Op, Value *S1, Value *S2, const Twine &Name=Twine(), Instruction *InsertBefore=nullptr)
Construct a binary instruction, given the opcode and the two operands.
const Value * getFalseValue() const
static bool processCallSite(CallSite CS, LazyValueInfo *LVI)
Infer nonnull attributes for the arguments at the specified callsite.
correlated propagation
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:807
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:321
Instruction::BinaryOps getBinaryOp() const
Returns the binary operation underlying the intrinsic.
void setCondition(Value *V)
unsigned getIntegerBitWidth() const
Definition: DerivedTypes.h:97
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
#define I(x, y, z)
Definition: MD5.cpp:58
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:332
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:174
static bool processMemAccess(Instruction *I, LazyValueInfo *LVI)
static Attribute get(LLVMContext &Context, AttrKind Kind, uint64_t Val=0)
Return a uniquified Attribute object.
Definition: Attributes.cpp:80
This class represents an intrinsic that is based on a binary operation.
bool hasNoUnsignedWrap() const
Determine whether the no unsigned wrap flag is set.
ConstantRange unionWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the union of this range with another range.
iterator_range< df_iterator< T > > depth_first(const T &G)
void setHasNoUnsignedWrap(bool b=true)
Set or clear the nuw flag on this instruction, which must be an operator which supports this flag...
Multiway switch.
This pass computes, caches, and vends lazy value constraint information.
Definition: LazyValueInfo.h:31
static ConstantRange makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp, const ConstantRange &Other, unsigned NoWrapKind)
Produce the largest range containing all X such that "X BinOp Y" is guaranteed not to wrap (overflow)...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Value Representation.
Definition: Value.h:72
succ_range successors(Instruction *I)
Definition: CFG.h:259
static const Function * getParent(const Value *V)
static Constant * getConstantAt(Value *V, Instruction *At, LazyValueInfo *LVI)
A container for analyses that lazily runs them and caches their results.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:259
static void processSaturatingInst(SaturatingInst *SI)
Value * CreateInsertValue(Value *Agg, Value *Val, ArrayRef< unsigned > Idxs, const Twine &Name="")
Definition: IRBuilder.h:2313
This header defines various interfaces for pass management in LLVM.
void setIncomingValue(unsigned i, Value *V)
#define LLVM_DEBUG(X)
Definition: Debug.h:122
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
static bool simplifyCommonValuePhi(PHINode *P, LazyValueInfo *LVI, DominatorTree *DT)
Try to simplify a phi with constant incoming values that match the edge values of a non-constant valu...
Value * SimplifyInstruction(Instruction *I, const SimplifyQuery &Q, OptimizationRemarkEmitter *ORE=nullptr)
See if we can compute a simplified version of this instruction.
Value * getLHS() const
signed greater or equal
Definition: InstrTypes.h:760
Analysis to compute lazy value information.
uint64_t PowerOf2Ceil(uint64_t A)
Returns the power of two which is greater than or equal to the given value.
Definition: MathExtras.h:658
const BasicBlock * getParent() const
Definition: Instruction.h:66