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