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 *C, LazyValueInfo *LVI) {
277  Value *Op0 = C->getOperand(0);
278  Constant *Op1 = dyn_cast<Constant>(C->getOperand(1));
279  if (!Op1) return false;
280 
281  // As a policy choice, we choose not to waste compile time on anything where
282  // the comparison is testing local values. While LVI can sometimes reason
283  // about such cases, it's not its primary purpose. We do make sure to do
284  // the block local query for uses from terminator instructions, but that's
285  // handled in the code for each terminator.
286  auto *I = dyn_cast<Instruction>(Op0);
287  if (I && I->getParent() == C->getParent())
288  return false;
289 
291  LVI->getPredicateAt(C->getPredicate(), Op0, Op1, C);
292  if (Result == LazyValueInfo::Unknown) return false;
293 
294  ++NumCmps;
295  if (Result == LazyValueInfo::True)
297  else
299  C->eraseFromParent();
300 
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.
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  Value *NewOp = nullptr;
434  switch (II->getIntrinsicID()) {
435  default:
436  llvm_unreachable("Unexpected instruction.");
437  case Intrinsic::uadd_with_overflow:
438  case Intrinsic::sadd_with_overflow:
439  NewOp = BinaryOperator::CreateAdd(II->getOperand(0), II->getOperand(1),
440  II->getName(), II);
441  break;
442  case Intrinsic::usub_with_overflow:
443  case Intrinsic::ssub_with_overflow:
444  NewOp = BinaryOperator::CreateSub(II->getOperand(0), II->getOperand(1),
445  II->getName(), II);
446  break;
447  }
448  ++NumOverflows;
449  IRBuilder<> B(II);
450  Value *NewI = B.CreateInsertValue(UndefValue::get(II->getType()), NewOp, 0);
451  NewI = B.CreateInsertValue(NewI, ConstantInt::getFalse(II->getContext()), 1);
452  II->replaceAllUsesWith(NewI);
453  II->eraseFromParent();
454 }
455 
456 /// Infer nonnull attributes for the arguments at the specified callsite.
457 static bool processCallSite(CallSite CS, LazyValueInfo *LVI) {
459  unsigned ArgNo = 0;
460 
461  if (auto *II = dyn_cast<IntrinsicInst>(CS.getInstruction())) {
462  if (willNotOverflow(II, LVI)) {
464  return true;
465  }
466  }
467 
468  for (Value *V : CS.args()) {
469  PointerType *Type = dyn_cast<PointerType>(V->getType());
470  // Try to mark pointer typed parameters as non-null. We skip the
471  // relatively expensive analysis for constants which are obviously either
472  // null or non-null to start with.
473  if (Type && !CS.paramHasAttr(ArgNo, Attribute::NonNull) &&
474  !isa<Constant>(V) &&
478  ArgNos.push_back(ArgNo);
479  ArgNo++;
480  }
481 
482  assert(ArgNo == CS.arg_size() && "sanity check");
483 
484  if (ArgNos.empty())
485  return false;
486 
487  AttributeList AS = CS.getAttributes();
488  LLVMContext &Ctx = CS.getInstruction()->getContext();
489  AS = AS.addParamAttribute(Ctx, ArgNos,
490  Attribute::get(Ctx, Attribute::NonNull));
491  CS.setAttributes(AS);
492 
493  return true;
494 }
495 
497  Constant *Zero = ConstantInt::get(SDI->getType(), 0);
498  for (Value *O : SDI->operands()) {
499  auto Result = LVI->getPredicateAt(ICmpInst::ICMP_SGE, O, Zero, SDI);
501  return false;
502  }
503  return true;
504 }
505 
506 /// Try to shrink a udiv/urem's width down to the smallest power of two that's
507 /// sufficient to contain its operands.
508 static bool processUDivOrURem(BinaryOperator *Instr, LazyValueInfo *LVI) {
509  assert(Instr->getOpcode() == Instruction::UDiv ||
510  Instr->getOpcode() == Instruction::URem);
511  if (Instr->getType()->isVectorTy())
512  return false;
513 
514  // Find the smallest power of two bitwidth that's sufficient to hold Instr's
515  // operands.
516  auto OrigWidth = Instr->getType()->getIntegerBitWidth();
517  ConstantRange OperandRange(OrigWidth, /*isFullset=*/false);
518  for (Value *Operand : Instr->operands()) {
519  OperandRange = OperandRange.unionWith(
520  LVI->getConstantRange(Operand, Instr->getParent()));
521  }
522  // Don't shrink below 8 bits wide.
523  unsigned NewWidth = std::max<unsigned>(
524  PowerOf2Ceil(OperandRange.getUnsignedMax().getActiveBits()), 8);
525  // NewWidth might be greater than OrigWidth if OrigWidth is not a power of
526  // two.
527  if (NewWidth >= OrigWidth)
528  return false;
529 
530  ++NumUDivs;
531  auto *TruncTy = Type::getIntNTy(Instr->getContext(), NewWidth);
532  auto *LHS = CastInst::Create(Instruction::Trunc, Instr->getOperand(0), TruncTy,
533  Instr->getName() + ".lhs.trunc", Instr);
534  auto *RHS = CastInst::Create(Instruction::Trunc, Instr->getOperand(1), TruncTy,
535  Instr->getName() + ".rhs.trunc", Instr);
536  auto *BO =
537  BinaryOperator::Create(Instr->getOpcode(), LHS, RHS, Instr->getName(), Instr);
538  auto *Zext = CastInst::Create(Instruction::ZExt, BO, Instr->getType(),
539  Instr->getName() + ".zext", Instr);
540  if (BO->getOpcode() == Instruction::UDiv)
541  BO->setIsExact(Instr->isExact());
542 
543  Instr->replaceAllUsesWith(Zext);
544  Instr->eraseFromParent();
545  return true;
546 }
547 
548 static bool processSRem(BinaryOperator *SDI, LazyValueInfo *LVI) {
549  if (SDI->getType()->isVectorTy() || !hasPositiveOperands(SDI, LVI))
550  return false;
551 
552  ++NumSRems;
553  auto *BO = BinaryOperator::CreateURem(SDI->getOperand(0), SDI->getOperand(1),
554  SDI->getName(), SDI);
555  SDI->replaceAllUsesWith(BO);
556  SDI->eraseFromParent();
557 
558  // Try to process our new urem.
559  processUDivOrURem(BO, LVI);
560 
561  return true;
562 }
563 
564 /// See if LazyValueInfo's ability to exploit edge conditions or range
565 /// information is sufficient to prove the both operands of this SDiv are
566 /// positive. If this is the case, replace the SDiv with a UDiv. Even for local
567 /// conditions, this can sometimes prove conditions instcombine can't by
568 /// exploiting range information.
569 static bool processSDiv(BinaryOperator *SDI, LazyValueInfo *LVI) {
570  if (SDI->getType()->isVectorTy() || !hasPositiveOperands(SDI, LVI))
571  return false;
572 
573  ++NumSDivs;
574  auto *BO = BinaryOperator::CreateUDiv(SDI->getOperand(0), SDI->getOperand(1),
575  SDI->getName(), SDI);
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->setIsExact(SDI->isExact());
599  SDI->replaceAllUsesWith(BO);
600  SDI->eraseFromParent();
601 
602  return true;
603 }
604 
605 static bool processAdd(BinaryOperator *AddOp, LazyValueInfo *LVI) {
606  using OBO = OverflowingBinaryOperator;
607 
608  if (DontProcessAdds)
609  return false;
610 
611  if (AddOp->getType()->isVectorTy())
612  return false;
613 
614  bool NSW = AddOp->hasNoSignedWrap();
615  bool NUW = AddOp->hasNoUnsignedWrap();
616  if (NSW && NUW)
617  return false;
618 
619  BasicBlock *BB = AddOp->getParent();
620 
621  Value *LHS = AddOp->getOperand(0);
622  Value *RHS = AddOp->getOperand(1);
623 
624  ConstantRange LRange = LVI->getConstantRange(LHS, BB, AddOp);
625 
626  // Initialize RRange only if we need it. If we know that guaranteed no wrap
627  // range for the given LHS range is empty don't spend time calculating the
628  // range for the RHS.
630  auto LazyRRange = [&] () {
631  if (!RRange)
632  RRange = LVI->getConstantRange(RHS, BB, AddOp);
633  return RRange.getValue();
634  };
635 
636  bool Changed = false;
637  if (!NUW) {
639  BinaryOperator::Add, LRange, OBO::NoUnsignedWrap);
640  if (!NUWRange.isEmptySet()) {
641  bool NewNUW = NUWRange.contains(LazyRRange());
642  AddOp->setHasNoUnsignedWrap(NewNUW);
643  Changed |= NewNUW;
644  }
645  }
646  if (!NSW) {
648  BinaryOperator::Add, LRange, OBO::NoSignedWrap);
649  if (!NSWRange.isEmptySet()) {
650  bool NewNSW = NSWRange.contains(LazyRRange());
651  AddOp->setHasNoSignedWrap(NewNSW);
652  Changed |= NewNSW;
653  }
654  }
655 
656  return Changed;
657 }
658 
660  if (Constant *C = LVI->getConstant(V, At->getParent(), At))
661  return C;
662 
663  // TODO: The following really should be sunk inside LVI's core algorithm, or
664  // at least the outer shims around such.
665  auto *C = dyn_cast<CmpInst>(V);
666  if (!C) return nullptr;
667 
668  Value *Op0 = C->getOperand(0);
669  Constant *Op1 = dyn_cast<Constant>(C->getOperand(1));
670  if (!Op1) return nullptr;
671 
673  LVI->getPredicateAt(C->getPredicate(), Op0, Op1, At);
674  if (Result == LazyValueInfo::Unknown)
675  return nullptr;
676 
677  return (Result == LazyValueInfo::True) ?
680 }
681 
682 static bool runImpl(Function &F, LazyValueInfo *LVI, DominatorTree *DT,
683  const SimplifyQuery &SQ) {
684  bool FnChanged = false;
685  // Visiting in a pre-order depth-first traversal causes us to simplify early
686  // blocks before querying later blocks (which require us to analyze early
687  // blocks). Eagerly simplifying shallow blocks means there is strictly less
688  // work to do for deep blocks. This also means we don't visit unreachable
689  // blocks.
690  for (BasicBlock *BB : depth_first(&F.getEntryBlock())) {
691  bool BBChanged = false;
692  for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) {
693  Instruction *II = &*BI++;
694  switch (II->getOpcode()) {
695  case Instruction::Select:
696  BBChanged |= processSelect(cast<SelectInst>(II), LVI);
697  break;
698  case Instruction::PHI:
699  BBChanged |= processPHI(cast<PHINode>(II), LVI, DT, SQ);
700  break;
701  case Instruction::ICmp:
702  case Instruction::FCmp:
703  BBChanged |= processCmp(cast<CmpInst>(II), LVI);
704  break;
705  case Instruction::Load:
706  case Instruction::Store:
707  BBChanged |= processMemAccess(II, LVI);
708  break;
709  case Instruction::Call:
710  case Instruction::Invoke:
711  BBChanged |= processCallSite(CallSite(II), LVI);
712  break;
713  case Instruction::SRem:
714  BBChanged |= processSRem(cast<BinaryOperator>(II), LVI);
715  break;
716  case Instruction::SDiv:
717  BBChanged |= processSDiv(cast<BinaryOperator>(II), LVI);
718  break;
719  case Instruction::UDiv:
720  case Instruction::URem:
721  BBChanged |= processUDivOrURem(cast<BinaryOperator>(II), LVI);
722  break;
723  case Instruction::AShr:
724  BBChanged |= processAShr(cast<BinaryOperator>(II), LVI);
725  break;
726  case Instruction::Add:
727  BBChanged |= processAdd(cast<BinaryOperator>(II), LVI);
728  break;
729  }
730  }
731 
732  Instruction *Term = BB->getTerminator();
733  switch (Term->getOpcode()) {
734  case Instruction::Switch:
735  BBChanged |= processSwitch(cast<SwitchInst>(Term), LVI, DT);
736  break;
737  case Instruction::Ret: {
738  auto *RI = cast<ReturnInst>(Term);
739  // Try to determine the return value if we can. This is mainly here to
740  // simplify the writing of unit tests, but also helps to enable IPO by
741  // constant folding the return values of callees.
742  auto *RetVal = RI->getReturnValue();
743  if (!RetVal) break; // handle "ret void"
744  if (isa<Constant>(RetVal)) break; // nothing to do
745  if (auto *C = getConstantAt(RetVal, RI, LVI)) {
746  ++NumReturns;
747  RI->replaceUsesOfWith(RetVal, C);
748  BBChanged = true;
749  }
750  }
751  }
752 
753  FnChanged |= BBChanged;
754  }
755 
756  return FnChanged;
757 }
758 
760  if (skipFunction(F))
761  return false;
762 
763  LazyValueInfo *LVI = &getAnalysis<LazyValueInfoWrapperPass>().getLVI();
764  DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
765 
766  return runImpl(F, LVI, DT, getBestSimplifyQuery(*this, F));
767 }
768 
773 
774  bool Changed = runImpl(F, LVI, DT, getBestSimplifyQuery(AM, F));
775 
776  if (!Changed)
777  return PreservedAnalyses::all();
779  PA.preserve<GlobalsAA>();
781  return PA;
782 }
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:584
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:675
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:295
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
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
BinaryOps getOpcode() const
Definition: InstrTypes.h:355
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
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:714
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))
AttributeList addParamAttribute(LLVMContext &C, unsigned ArgNo, Attribute::AttrKind Kind) const
Add an argument attribute to the list.
Definition: Attributes.h:397
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)
bool contains(const APInt &Val) const
Return true if the specified value is in the set.
ELFYAML::ELF_STO Other
Definition: ELFYAML.cpp:773
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:1527
bool isOne() const
This is just a convenience method to make client code smaller for a common case.
Definition: Constants.h:201
void setIsExact(bool b=true)
Set or clear the exact flag on this instruction, which must be an operator which supports this flag...
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:179
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
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:439
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:145
static BinaryOperator * CreateAdd(Value *S1, Value *S2, const Twine &Name, Instruction *InsertBefore, Value *FlagsOp)
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
Value * getOperand(unsigned i_nocapture) const
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:410
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:1378
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:59
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:1392
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:621
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:577
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
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
static CastInst * Create(Instruction::CastOps, Value *S, Type *Ty, const Twine &Name="", Instruction *InsertBefore=nullptr)
Provides a way to construct any of the CastInst subclasses using an opcode instead of the subclass&#39;s ...
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:759
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
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:224
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:262
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 processCmp(CmpInst *C, LazyValueInfo *LVI)
See if LazyValueInfo&#39;s ability to exploit edge conditions or range information is sufficient to prove...
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:713
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