LLVM  10.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 {
89  }
90  };
91 
92 } // end anonymous namespace
93 
95 
96 INITIALIZE_PASS_BEGIN(CorrelatedValuePropagation, "correlated-propagation",
97  "Value Propagation", false, false)
100 INITIALIZE_PASS_END(CorrelatedValuePropagation, "correlated-propagation",
101  "Value Propagation", false, false)
102 
103 // Public interface to the Value Propagation pass
105  return new CorrelatedValuePropagation();
106 }
107 
108 static bool processSelect(SelectInst *S, LazyValueInfo *LVI) {
109  if (S->getType()->isVectorTy()) return false;
110  if (isa<Constant>(S->getOperand(0))) return false;
111 
112  Constant *C = LVI->getConstant(S->getCondition(), S->getParent(), S);
113  if (!C) return false;
114 
116  if (!CI) return false;
117 
118  Value *ReplaceWith = S->getTrueValue();
119  Value *Other = S->getFalseValue();
120  if (!CI->isOne()) std::swap(ReplaceWith, Other);
121  if (ReplaceWith == S) ReplaceWith = UndefValue::get(S->getType());
122 
123  S->replaceAllUsesWith(ReplaceWith);
124  S->eraseFromParent();
125 
126  ++NumSelects;
127 
128  return true;
129 }
130 
131 /// Try to simplify a phi with constant incoming values that match the edge
132 /// values of a non-constant value on all other edges:
133 /// bb0:
134 /// %isnull = icmp eq i8* %x, null
135 /// br i1 %isnull, label %bb2, label %bb1
136 /// bb1:
137 /// br label %bb2
138 /// bb2:
139 /// %r = phi i8* [ %x, %bb1 ], [ null, %bb0 ]
140 /// -->
141 /// %r = %x
143  DominatorTree *DT) {
144  // Collect incoming constants and initialize possible common value.
145  SmallVector<std::pair<Constant *, unsigned>, 4> IncomingConstants;
146  Value *CommonValue = nullptr;
147  for (unsigned i = 0, e = P->getNumIncomingValues(); i != e; ++i) {
148  Value *Incoming = P->getIncomingValue(i);
149  if (auto *IncomingConstant = dyn_cast<Constant>(Incoming)) {
150  IncomingConstants.push_back(std::make_pair(IncomingConstant, i));
151  } else if (!CommonValue) {
152  // The potential common value is initialized to the first non-constant.
153  CommonValue = Incoming;
154  } else if (Incoming != CommonValue) {
155  // There can be only one non-constant common value.
156  return false;
157  }
158  }
159 
160  if (!CommonValue || IncomingConstants.empty())
161  return false;
162 
163  // The common value must be valid in all incoming blocks.
164  BasicBlock *ToBB = P->getParent();
165  if (auto *CommonInst = dyn_cast<Instruction>(CommonValue))
166  if (!DT->dominates(CommonInst, ToBB))
167  return false;
168 
169  // We have a phi with exactly 1 variable incoming value and 1 or more constant
170  // incoming values. See if all constant incoming values can be mapped back to
171  // the same incoming variable value.
172  for (auto &IncomingConstant : IncomingConstants) {
173  Constant *C = IncomingConstant.first;
174  BasicBlock *IncomingBB = P->getIncomingBlock(IncomingConstant.second);
175  if (C != LVI->getConstantOnEdge(CommonValue, IncomingBB, ToBB, P))
176  return false;
177  }
178 
179  // All constant incoming values map to the same variable along the incoming
180  // edges of the phi. The phi is unnecessary.
181  P->replaceAllUsesWith(CommonValue);
182  P->eraseFromParent();
183  ++NumPhiCommon;
184  return true;
185 }
186 
188  const SimplifyQuery &SQ) {
189  bool Changed = false;
190 
191  BasicBlock *BB = P->getParent();
192  for (unsigned i = 0, e = P->getNumIncomingValues(); i < e; ++i) {
193  Value *Incoming = P->getIncomingValue(i);
194  if (isa<Constant>(Incoming)) continue;
195 
196  Value *V = LVI->getConstantOnEdge(Incoming, P->getIncomingBlock(i), BB, P);
197 
198  // Look if the incoming value is a select with a scalar condition for which
199  // LVI can tells us the value. In that case replace the incoming value with
200  // the appropriate value of the select. This often allows us to remove the
201  // select later.
202  if (!V) {
203  SelectInst *SI = dyn_cast<SelectInst>(Incoming);
204  if (!SI) continue;
205 
206  Value *Condition = SI->getCondition();
207  if (!Condition->getType()->isVectorTy()) {
208  if (Constant *C = LVI->getConstantOnEdge(
209  Condition, P->getIncomingBlock(i), BB, P)) {
210  if (C->isOneValue()) {
211  V = SI->getTrueValue();
212  } else if (C->isZeroValue()) {
213  V = SI->getFalseValue();
214  }
215  // Once LVI learns to handle vector types, we could also add support
216  // for vector type constants that are not all zeroes or all ones.
217  }
218  }
219 
220  // Look if the select has a constant but LVI tells us that the incoming
221  // value can never be that constant. In that case replace the incoming
222  // value with the other value of the select. This often allows us to
223  // remove the select later.
224  if (!V) {
226  if (!C) continue;
227 
228  if (LVI->getPredicateOnEdge(ICmpInst::ICMP_EQ, SI, C,
229  P->getIncomingBlock(i), BB, P) !=
231  continue;
232  V = SI->getTrueValue();
233  }
234 
235  LLVM_DEBUG(dbgs() << "CVP: Threading PHI over " << *SI << '\n');
236  }
237 
238  P->setIncomingValue(i, V);
239  Changed = true;
240  }
241 
242  if (Value *V = SimplifyInstruction(P, SQ)) {
243  P->replaceAllUsesWith(V);
244  P->eraseFromParent();
245  Changed = true;
246  }
247 
248  if (!Changed)
249  Changed = simplifyCommonValuePhi(P, LVI, DT);
250 
251  if (Changed)
252  ++NumPhis;
253 
254  return Changed;
255 }
256 
258  Value *Pointer = nullptr;
259  if (LoadInst *L = dyn_cast<LoadInst>(I))
260  Pointer = L->getPointerOperand();
261  else
262  Pointer = cast<StoreInst>(I)->getPointerOperand();
263 
264  if (isa<Constant>(Pointer)) return false;
265 
266  Constant *C = LVI->getConstant(Pointer, I->getParent(), I);
267  if (!C) return false;
268 
269  ++NumMemAccess;
270  I->replaceUsesOfWith(Pointer, C);
271  return true;
272 }
273 
274 /// See if LazyValueInfo's ability to exploit edge conditions or range
275 /// information is sufficient to prove this comparison. Even for local
276 /// conditions, this can sometimes prove conditions instcombine can't by
277 /// exploiting range information.
278 static bool processCmp(CmpInst *Cmp, LazyValueInfo *LVI) {
279  Value *Op0 = Cmp->getOperand(0);
280  auto *C = dyn_cast<Constant>(Cmp->getOperand(1));
281  if (!C)
282  return false;
283 
284  // As a policy choice, we choose not to waste compile time on anything where
285  // the comparison is testing local values. While LVI can sometimes reason
286  // about such cases, it's not its primary purpose. We do make sure to do
287  // the block local query for uses from terminator instructions, but that's
288  // handled in the code for each terminator.
289  auto *I = dyn_cast<Instruction>(Op0);
290  if (I && I->getParent() == Cmp->getParent())
291  return false;
292 
293  LazyValueInfo::Tristate Result =
294  LVI->getPredicateAt(Cmp->getPredicate(), Op0, C, Cmp);
295  if (Result == LazyValueInfo::Unknown)
296  return false;
297 
298  ++NumCmps;
299  Constant *TorF = ConstantInt::get(Type::getInt1Ty(Cmp->getContext()), Result);
300  Cmp->replaceAllUsesWith(TorF);
301  Cmp->eraseFromParent();
302  return true;
303 }
304 
305 /// Simplify a switch instruction by removing cases which can never fire. If the
306 /// uselessness of a case could be determined locally then constant propagation
307 /// would already have figured it out. Instead, walk the predecessors and
308 /// statically evaluate cases based on information available on that edge. Cases
309 /// that cannot fire no matter what the incoming edge can safely be removed. If
310 /// a case fires on every incoming edge then the entire switch can be removed
311 /// and replaced with a branch to the case destination.
313  DominatorTree *DT) {
315  Value *Cond = I->getCondition();
316  BasicBlock *BB = I->getParent();
317 
318  // If the condition was defined in same block as the switch then LazyValueInfo
319  // currently won't say anything useful about it, though in theory it could.
320  if (isa<Instruction>(Cond) && cast<Instruction>(Cond)->getParent() == BB)
321  return false;
322 
323  // If the switch is unreachable then trying to improve it is a waste of time.
324  pred_iterator PB = pred_begin(BB), PE = pred_end(BB);
325  if (PB == PE) return false;
326 
327  // Analyse each switch case in turn.
328  bool Changed = false;
329  DenseMap<BasicBlock*, int> SuccessorsCount;
330  for (auto *Succ : successors(BB))
331  SuccessorsCount[Succ]++;
332 
333  { // Scope for SwitchInstProfUpdateWrapper. It must not live during
334  // ConstantFoldTerminator() as the underlying SwitchInst can be changed.
336 
337  for (auto CI = SI->case_begin(), CE = SI->case_end(); CI != CE;) {
338  ConstantInt *Case = CI->getCaseValue();
339 
340  // Check to see if the switch condition is equal to/not equal to the case
341  // value on every incoming edge, equal/not equal being the same each time.
343  for (pred_iterator PI = PB; PI != PE; ++PI) {
344  // Is the switch condition equal to the case value?
346  Cond, Case, *PI,
347  BB, SI);
348  // Give up on this case if nothing is known.
349  if (Value == LazyValueInfo::Unknown) {
350  State = LazyValueInfo::Unknown;
351  break;
352  }
353 
354  // If this was the first edge to be visited, record that all other edges
355  // need to give the same result.
356  if (PI == PB) {
357  State = Value;
358  continue;
359  }
360 
361  // If this case is known to fire for some edges and known not to fire for
362  // others then there is nothing we can do - give up.
363  if (Value != State) {
364  State = LazyValueInfo::Unknown;
365  break;
366  }
367  }
368 
369  if (State == LazyValueInfo::False) {
370  // This case never fires - remove it.
371  BasicBlock *Succ = CI->getCaseSuccessor();
372  Succ->removePredecessor(BB);
373  CI = SI.removeCase(CI);
374  CE = SI->case_end();
375 
376  // The condition can be modified by removePredecessor's PHI simplification
377  // logic.
378  Cond = SI->getCondition();
379 
380  ++NumDeadCases;
381  Changed = true;
382  if (--SuccessorsCount[Succ] == 0)
384  continue;
385  }
386  if (State == LazyValueInfo::True) {
387  // This case always fires. Arrange for the switch to be turned into an
388  // unconditional branch by replacing the switch condition with the case
389  // value.
390  SI->setCondition(Case);
391  NumDeadCases += SI->getNumCases();
392  Changed = true;
393  break;
394  }
395 
396  // Increment the case iterator since we didn't delete it.
397  ++CI;
398  }
399  }
400 
401  if (Changed)
402  // If the switch has been simplified to the point where it can be replaced
403  // by a branch then do so now.
404  ConstantFoldTerminator(BB, /*DeleteDeadConditions = */ false,
405  /*TLI = */ nullptr, &DTU);
406  return Changed;
407 }
408 
409 // See if we can prove that the given binary op intrinsic will not overflow.
411  ConstantRange LRange = LVI->getConstantRange(
412  BO->getLHS(), BO->getParent(), BO);
413  ConstantRange RRange = LVI->getConstantRange(
414  BO->getRHS(), BO->getParent(), BO);
416  BO->getBinaryOp(), RRange, BO->getNoWrapKind());
417  return NWRegion.contains(LRange);
418 }
419 
420 // Rewrite this with.overflow intrinsic as non-overflowing.
422  IRBuilder<> B(WO);
423  Value *NewOp = B.CreateBinOp(
424  WO->getBinaryOp(), WO->getLHS(), WO->getRHS(), WO->getName());
425  // Constant-folding could have happened.
426  if (auto *Inst = dyn_cast<Instruction>(NewOp)) {
427  if (WO->isSigned())
428  Inst->setHasNoSignedWrap();
429  else
430  Inst->setHasNoUnsignedWrap();
431  }
432 
433  StructType *ST = cast<StructType>(WO->getType());
434  Constant *Struct = ConstantStruct::get(ST,
437  Value *NewI = B.CreateInsertValue(Struct, NewOp, 0);
438  WO->replaceAllUsesWith(NewI);
439  WO->eraseFromParent();
440  ++NumOverflows;
441 }
442 
445  SI->getBinaryOp(), SI->getLHS(), SI->getRHS(), SI->getName(), SI);
446  BinOp->setDebugLoc(SI->getDebugLoc());
447  if (SI->isSigned())
448  BinOp->setHasNoSignedWrap();
449  else
450  BinOp->setHasNoUnsignedWrap();
451 
452  SI->replaceAllUsesWith(BinOp);
453  SI->eraseFromParent();
454  ++NumSaturating;
455 }
456 
457 /// Infer nonnull attributes for the arguments at the specified callsite.
458 static bool processCallSite(CallSite CS, LazyValueInfo *LVI) {
460  unsigned ArgNo = 0;
461 
462  if (auto *WO = dyn_cast<WithOverflowInst>(CS.getInstruction())) {
463  if (WO->getLHS()->getType()->isIntegerTy() && willNotOverflow(WO, LVI)) {
465  return true;
466  }
467  }
468 
469  if (auto *SI = dyn_cast<SaturatingInst>(CS.getInstruction())) {
470  if (SI->getType()->isIntegerTy() && willNotOverflow(SI, LVI)) {
472  return true;
473  }
474  }
475 
476  // Deopt bundle operands are intended to capture state with minimal
477  // perturbance of the code otherwise. If we can find a constant value for
478  // any such operand and remove a use of the original value, that's
479  // desireable since it may allow further optimization of that value (e.g. via
480  // single use rules in instcombine). Since deopt uses tend to,
481  // idiomatically, appear along rare conditional paths, it's reasonable likely
482  // we may have a conditional fact with which LVI can fold.
483  if (auto DeoptBundle = CS.getOperandBundle(LLVMContext::OB_deopt)) {
484  bool Progress = false;
485  for (const Use &ConstU : DeoptBundle->Inputs) {
486  Use &U = const_cast<Use&>(ConstU);
487  Value *V = U.get();
488  if (V->getType()->isVectorTy()) continue;
489  if (isa<Constant>(V)) continue;
490 
491  Constant *C = LVI->getConstant(V, CS.getParent(), CS.getInstruction());
492  if (!C) continue;
493  U.set(C);
494  Progress = true;
495  }
496  if (Progress)
497  return true;
498  }
499 
500  for (Value *V : CS.args()) {
501  PointerType *Type = dyn_cast<PointerType>(V->getType());
502  // Try to mark pointer typed parameters as non-null. We skip the
503  // relatively expensive analysis for constants which are obviously either
504  // null or non-null to start with.
505  if (Type && !CS.paramHasAttr(ArgNo, Attribute::NonNull) &&
506  !isa<Constant>(V) &&
510  ArgNos.push_back(ArgNo);
511  ArgNo++;
512  }
513 
514  assert(ArgNo == CS.arg_size() && "sanity check");
515 
516  if (ArgNos.empty())
517  return false;
518 
519  AttributeList AS = CS.getAttributes();
520  LLVMContext &Ctx = CS.getInstruction()->getContext();
521  AS = AS.addParamAttribute(Ctx, ArgNos,
522  Attribute::get(Ctx, Attribute::NonNull));
523  CS.setAttributes(AS);
524 
525  return true;
526 }
527 
529  Constant *Zero = ConstantInt::get(SDI->getType(), 0);
530  for (Value *O : SDI->operands()) {
531  auto Result = LVI->getPredicateAt(ICmpInst::ICMP_SGE, O, Zero, SDI);
532  if (Result != LazyValueInfo::True)
533  return false;
534  }
535  return true;
536 }
537 
538 /// Try to shrink a udiv/urem's width down to the smallest power of two that's
539 /// sufficient to contain its operands.
540 static bool processUDivOrURem(BinaryOperator *Instr, LazyValueInfo *LVI) {
541  assert(Instr->getOpcode() == Instruction::UDiv ||
542  Instr->getOpcode() == Instruction::URem);
543  if (Instr->getType()->isVectorTy())
544  return false;
545 
546  // Find the smallest power of two bitwidth that's sufficient to hold Instr's
547  // operands.
548  auto OrigWidth = Instr->getType()->getIntegerBitWidth();
549  ConstantRange OperandRange(OrigWidth, /*isFullSet=*/false);
550  for (Value *Operand : Instr->operands()) {
551  OperandRange = OperandRange.unionWith(
552  LVI->getConstantRange(Operand, Instr->getParent()));
553  }
554  // Don't shrink below 8 bits wide.
555  unsigned NewWidth = std::max<unsigned>(
556  PowerOf2Ceil(OperandRange.getUnsignedMax().getActiveBits()), 8);
557  // NewWidth might be greater than OrigWidth if OrigWidth is not a power of
558  // two.
559  if (NewWidth >= OrigWidth)
560  return false;
561 
562  ++NumUDivs;
563  IRBuilder<> B{Instr};
564  auto *TruncTy = Type::getIntNTy(Instr->getContext(), NewWidth);
565  auto *LHS = B.CreateTruncOrBitCast(Instr->getOperand(0), TruncTy,
566  Instr->getName() + ".lhs.trunc");
567  auto *RHS = B.CreateTruncOrBitCast(Instr->getOperand(1), TruncTy,
568  Instr->getName() + ".rhs.trunc");
569  auto *BO = B.CreateBinOp(Instr->getOpcode(), LHS, RHS, Instr->getName());
570  auto *Zext = B.CreateZExt(BO, Instr->getType(), Instr->getName() + ".zext");
571  if (auto *BinOp = dyn_cast<BinaryOperator>(BO))
572  if (BinOp->getOpcode() == Instruction::UDiv)
573  BinOp->setIsExact(Instr->isExact());
574 
575  Instr->replaceAllUsesWith(Zext);
576  Instr->eraseFromParent();
577  return true;
578 }
579 
580 static bool processSRem(BinaryOperator *SDI, LazyValueInfo *LVI) {
581  if (SDI->getType()->isVectorTy() || !hasPositiveOperands(SDI, LVI))
582  return false;
583 
584  ++NumSRems;
585  auto *BO = BinaryOperator::CreateURem(SDI->getOperand(0), SDI->getOperand(1),
586  SDI->getName(), SDI);
587  BO->setDebugLoc(SDI->getDebugLoc());
588  SDI->replaceAllUsesWith(BO);
589  SDI->eraseFromParent();
590 
591  // Try to process our new urem.
592  processUDivOrURem(BO, LVI);
593 
594  return true;
595 }
596 
597 /// See if LazyValueInfo's ability to exploit edge conditions or range
598 /// information is sufficient to prove the both operands of this SDiv are
599 /// positive. If this is the case, replace the SDiv with a UDiv. Even for local
600 /// conditions, this can sometimes prove conditions instcombine can't by
601 /// exploiting range information.
602 static bool processSDiv(BinaryOperator *SDI, LazyValueInfo *LVI) {
603  if (SDI->getType()->isVectorTy() || !hasPositiveOperands(SDI, LVI))
604  return false;
605 
606  ++NumSDivs;
607  auto *BO = BinaryOperator::CreateUDiv(SDI->getOperand(0), SDI->getOperand(1),
608  SDI->getName(), SDI);
609  BO->setDebugLoc(SDI->getDebugLoc());
610  BO->setIsExact(SDI->isExact());
611  SDI->replaceAllUsesWith(BO);
612  SDI->eraseFromParent();
613 
614  // Try to simplify our new udiv.
615  processUDivOrURem(BO, LVI);
616 
617  return true;
618 }
619 
620 static bool processAShr(BinaryOperator *SDI, LazyValueInfo *LVI) {
621  if (SDI->getType()->isVectorTy())
622  return false;
623 
624  Constant *Zero = ConstantInt::get(SDI->getType(), 0);
625  if (LVI->getPredicateAt(ICmpInst::ICMP_SGE, SDI->getOperand(0), Zero, SDI) !=
627  return false;
628 
629  ++NumAShrs;
630  auto *BO = BinaryOperator::CreateLShr(SDI->getOperand(0), SDI->getOperand(1),
631  SDI->getName(), SDI);
632  BO->setDebugLoc(SDI->getDebugLoc());
633  BO->setIsExact(SDI->isExact());
634  SDI->replaceAllUsesWith(BO);
635  SDI->eraseFromParent();
636 
637  return true;
638 }
639 
640 static bool processBinOp(BinaryOperator *BinOp, LazyValueInfo *LVI) {
641  using OBO = OverflowingBinaryOperator;
642 
643  if (DontAddNoWrapFlags)
644  return false;
645 
646  if (BinOp->getType()->isVectorTy())
647  return false;
648 
649  bool NSW = BinOp->hasNoSignedWrap();
650  bool NUW = BinOp->hasNoUnsignedWrap();
651  if (NSW && NUW)
652  return false;
653 
654  BasicBlock *BB = BinOp->getParent();
655 
656  Value *LHS = BinOp->getOperand(0);
657  Value *RHS = BinOp->getOperand(1);
658 
659  ConstantRange LRange = LVI->getConstantRange(LHS, BB, BinOp);
660  ConstantRange RRange = LVI->getConstantRange(RHS, BB, BinOp);
661 
662  bool Changed = false;
663  if (!NUW) {
665  BinOp->getOpcode(), RRange, OBO::NoUnsignedWrap);
666  bool NewNUW = NUWRange.contains(LRange);
667  BinOp->setHasNoUnsignedWrap(NewNUW);
668  Changed |= NewNUW;
669  }
670  if (!NSW) {
672  BinOp->getOpcode(), RRange, OBO::NoSignedWrap);
673  bool NewNSW = NSWRange.contains(LRange);
674  BinOp->setHasNoSignedWrap(NewNSW);
675  Changed |= NewNSW;
676  }
677 
678  return Changed;
679 }
680 
682  if (Constant *C = LVI->getConstant(V, At->getParent(), At))
683  return C;
684 
685  // TODO: The following really should be sunk inside LVI's core algorithm, or
686  // at least the outer shims around such.
687  auto *C = dyn_cast<CmpInst>(V);
688  if (!C) return nullptr;
689 
690  Value *Op0 = C->getOperand(0);
691  Constant *Op1 = dyn_cast<Constant>(C->getOperand(1));
692  if (!Op1) return nullptr;
693 
694  LazyValueInfo::Tristate Result =
695  LVI->getPredicateAt(C->getPredicate(), Op0, Op1, At);
696  if (Result == LazyValueInfo::Unknown)
697  return nullptr;
698 
699  return (Result == LazyValueInfo::True) ?
702 }
703 
704 static bool runImpl(Function &F, LazyValueInfo *LVI, DominatorTree *DT,
705  const SimplifyQuery &SQ) {
706  bool FnChanged = false;
707  // Visiting in a pre-order depth-first traversal causes us to simplify early
708  // blocks before querying later blocks (which require us to analyze early
709  // blocks). Eagerly simplifying shallow blocks means there is strictly less
710  // work to do for deep blocks. This also means we don't visit unreachable
711  // blocks.
712  for (BasicBlock *BB : depth_first(&F.getEntryBlock())) {
713  bool BBChanged = false;
714  for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) {
715  Instruction *II = &*BI++;
716  switch (II->getOpcode()) {
717  case Instruction::Select:
718  BBChanged |= processSelect(cast<SelectInst>(II), LVI);
719  break;
720  case Instruction::PHI:
721  BBChanged |= processPHI(cast<PHINode>(II), LVI, DT, SQ);
722  break;
723  case Instruction::ICmp:
724  case Instruction::FCmp:
725  BBChanged |= processCmp(cast<CmpInst>(II), LVI);
726  break;
727  case Instruction::Load:
728  case Instruction::Store:
729  BBChanged |= processMemAccess(II, LVI);
730  break;
731  case Instruction::Call:
732  case Instruction::Invoke:
733  BBChanged |= processCallSite(CallSite(II), LVI);
734  break;
735  case Instruction::SRem:
736  BBChanged |= processSRem(cast<BinaryOperator>(II), LVI);
737  break;
738  case Instruction::SDiv:
739  BBChanged |= processSDiv(cast<BinaryOperator>(II), LVI);
740  break;
741  case Instruction::UDiv:
742  case Instruction::URem:
743  BBChanged |= processUDivOrURem(cast<BinaryOperator>(II), LVI);
744  break;
745  case Instruction::AShr:
746  BBChanged |= processAShr(cast<BinaryOperator>(II), LVI);
747  break;
748  case Instruction::Add:
749  case Instruction::Sub:
750  BBChanged |= processBinOp(cast<BinaryOperator>(II), LVI);
751  break;
752  }
753  }
754 
755  Instruction *Term = BB->getTerminator();
756  switch (Term->getOpcode()) {
757  case Instruction::Switch:
758  BBChanged |= processSwitch(cast<SwitchInst>(Term), LVI, DT);
759  break;
760  case Instruction::Ret: {
761  auto *RI = cast<ReturnInst>(Term);
762  // Try to determine the return value if we can. This is mainly here to
763  // simplify the writing of unit tests, but also helps to enable IPO by
764  // constant folding the return values of callees.
765  auto *RetVal = RI->getReturnValue();
766  if (!RetVal) break; // handle "ret void"
767  if (isa<Constant>(RetVal)) break; // nothing to do
768  if (auto *C = getConstantAt(RetVal, RI, LVI)) {
769  ++NumReturns;
770  RI->replaceUsesOfWith(RetVal, C);
771  BBChanged = true;
772  }
773  }
774  }
775 
776  FnChanged |= BBChanged;
777  }
778 
779  return FnChanged;
780 }
781 
783  if (skipFunction(F))
784  return false;
785 
786  LazyValueInfo *LVI = &getAnalysis<LazyValueInfoWrapperPass>().getLVI();
787  DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
788 
789  return runImpl(F, LVI, DT, getBestSimplifyQuery(*this, F));
790 }
791 
796 
797  bool Changed = runImpl(F, LVI, DT, getBestSimplifyQuery(AM, F));
798 
799  if (!Changed)
800  return PreservedAnalyses::all();
802  PA.preserve<GlobalsAA>();
805  return PA;
806 }
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:616
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 * 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.
Type * getElementType(unsigned N) const
Definition: DerivedTypes.h:346
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))
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:952
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:733
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)
Class to represent struct types.
Definition: DerivedTypes.h:233
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.
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:1541
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:245
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:328
static ConstantPointerNull * get(PointerType *T)
Static factory methods - Return objects of the specified value.
Definition: Constants.cpp:1432
void set(Value *Val)
Definition: Value.h:719
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:413
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
static Constant * get(StructType *T, ArrayRef< Constant *> V)
Definition: Constants.cpp:1075
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:1446
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:653
static bool processBinOp(BinaryOperator *BinOp, LazyValueInfo *LVI)
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:609
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:331
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.
const Value * getPointerOperand(const Value *V)
A helper function that returns the pointer operand of a load, store or GEP instruction.
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:73
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:2357
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:663
const BasicBlock * getParent() const
Definition: Instruction.h:66