LLVM  7.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"
23 #include "llvm/IR/Attributes.h"
24 #include "llvm/IR/BasicBlock.h"
25 #include "llvm/IR/CFG.h"
26 #include "llvm/IR/CallSite.h"
27 #include "llvm/IR/Constant.h"
28 #include "llvm/IR/ConstantRange.h"
29 #include "llvm/IR/Constants.h"
30 #include "llvm/IR/DerivedTypes.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"
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 
67 static cl::opt<bool> DontProcessAdds("cvp-dont-process-adds", cl::init(true));
68 
69 namespace {
70 
71  class CorrelatedValuePropagation : public FunctionPass {
72  public:
73  static char ID;
74 
75  CorrelatedValuePropagation(): FunctionPass(ID) {
77  }
78 
79  bool runOnFunction(Function &F) override;
80 
81  void getAnalysisUsage(AnalysisUsage &AU) const override {
86  }
87  };
88 
89 } // end anonymous namespace
90 
92 
93 INITIALIZE_PASS_BEGIN(CorrelatedValuePropagation, "correlated-propagation",
94  "Value Propagation", false, false)
97 INITIALIZE_PASS_END(CorrelatedValuePropagation, "correlated-propagation",
98  "Value Propagation", false, false)
99 
100 // Public interface to the Value Propagation pass
102  return new CorrelatedValuePropagation();
103 }
104 
105 static bool processSelect(SelectInst *S, LazyValueInfo *LVI) {
106  if (S->getType()->isVectorTy()) return false;
107  if (isa<Constant>(S->getOperand(0))) return false;
108 
109  Constant *C = LVI->getConstant(S->getCondition(), S->getParent(), S);
110  if (!C) return false;
111 
113  if (!CI) return false;
114 
115  Value *ReplaceWith = S->getTrueValue();
116  Value *Other = S->getFalseValue();
117  if (!CI->isOne()) std::swap(ReplaceWith, Other);
118  if (ReplaceWith == S) ReplaceWith = UndefValue::get(S->getType());
119 
120  S->replaceAllUsesWith(ReplaceWith);
121  S->eraseFromParent();
122 
123  ++NumSelects;
124 
125  return true;
126 }
127 
128 /// Try to simplify a phi with constant incoming values that match the edge
129 /// values of a non-constant value on all other edges:
130 /// bb0:
131 /// %isnull = icmp eq i8* %x, null
132 /// br i1 %isnull, label %bb2, label %bb1
133 /// bb1:
134 /// br label %bb2
135 /// bb2:
136 /// %r = phi i8* [ %x, %bb1 ], [ null, %bb0 ]
137 /// -->
138 /// %r = %x
140  DominatorTree *DT) {
141  // Collect incoming constants and initialize possible common value.
142  SmallVector<std::pair<Constant *, unsigned>, 4> IncomingConstants;
143  Value *CommonValue = nullptr;
144  for (unsigned i = 0, e = P->getNumIncomingValues(); i != e; ++i) {
145  Value *Incoming = P->getIncomingValue(i);
146  if (auto *IncomingConstant = dyn_cast<Constant>(Incoming)) {
147  IncomingConstants.push_back(std::make_pair(IncomingConstant, i));
148  } else if (!CommonValue) {
149  // The potential common value is initialized to the first non-constant.
150  CommonValue = Incoming;
151  } else if (Incoming != CommonValue) {
152  // There can be only one non-constant common value.
153  return false;
154  }
155  }
156 
157  if (!CommonValue || IncomingConstants.empty())
158  return false;
159 
160  // The common value must be valid in all incoming blocks.
161  BasicBlock *ToBB = P->getParent();
162  if (auto *CommonInst = dyn_cast<Instruction>(CommonValue))
163  if (!DT->dominates(CommonInst, ToBB))
164  return false;
165 
166  // We have a phi with exactly 1 variable incoming value and 1 or more constant
167  // incoming values. See if all constant incoming values can be mapped back to
168  // the same incoming variable value.
169  for (auto &IncomingConstant : IncomingConstants) {
170  Constant *C = IncomingConstant.first;
171  BasicBlock *IncomingBB = P->getIncomingBlock(IncomingConstant.second);
172  if (C != LVI->getConstantOnEdge(CommonValue, IncomingBB, ToBB, P))
173  return false;
174  }
175 
176  // All constant incoming values map to the same variable along the incoming
177  // edges of the phi. The phi is unnecessary.
178  P->replaceAllUsesWith(CommonValue);
179  P->eraseFromParent();
180  ++NumPhiCommon;
181  return true;
182 }
183 
185  const SimplifyQuery &SQ) {
186  bool Changed = false;
187 
188  BasicBlock *BB = P->getParent();
189  for (unsigned i = 0, e = P->getNumIncomingValues(); i < e; ++i) {
190  Value *Incoming = P->getIncomingValue(i);
191  if (isa<Constant>(Incoming)) continue;
192 
193  Value *V = LVI->getConstantOnEdge(Incoming, P->getIncomingBlock(i), BB, P);
194 
195  // Look if the incoming value is a select with a scalar condition for which
196  // LVI can tells us the value. In that case replace the incoming value with
197  // the appropriate value of the select. This often allows us to remove the
198  // select later.
199  if (!V) {
200  SelectInst *SI = dyn_cast<SelectInst>(Incoming);
201  if (!SI) continue;
202 
203  Value *Condition = SI->getCondition();
204  if (!Condition->getType()->isVectorTy()) {
205  if (Constant *C = LVI->getConstantOnEdge(
206  Condition, P->getIncomingBlock(i), BB, P)) {
207  if (C->isOneValue()) {
208  V = SI->getTrueValue();
209  } else if (C->isZeroValue()) {
210  V = SI->getFalseValue();
211  }
212  // Once LVI learns to handle vector types, we could also add support
213  // for vector type constants that are not all zeroes or all ones.
214  }
215  }
216 
217  // Look if the select has a constant but LVI tells us that the incoming
218  // value can never be that constant. In that case replace the incoming
219  // value with the other value of the select. This often allows us to
220  // remove the select later.
221  if (!V) {
223  if (!C) continue;
224 
225  if (LVI->getPredicateOnEdge(ICmpInst::ICMP_EQ, SI, C,
226  P->getIncomingBlock(i), BB, P) !=
228  continue;
229  V = SI->getTrueValue();
230  }
231 
232  LLVM_DEBUG(dbgs() << "CVP: Threading PHI over " << *SI << '\n');
233  }
234 
235  P->setIncomingValue(i, V);
236  Changed = true;
237  }
238 
239  if (Value *V = SimplifyInstruction(P, SQ)) {
240  P->replaceAllUsesWith(V);
241  P->eraseFromParent();
242  Changed = true;
243  }
244 
245  if (!Changed)
246  Changed = simplifyCommonValuePhi(P, LVI, DT);
247 
248  if (Changed)
249  ++NumPhis;
250 
251  return Changed;
252 }
253 
255  Value *Pointer = nullptr;
256  if (LoadInst *L = dyn_cast<LoadInst>(I))
257  Pointer = L->getPointerOperand();
258  else
259  Pointer = cast<StoreInst>(I)->getPointerOperand();
260 
261  if (isa<Constant>(Pointer)) return false;
262 
263  Constant *C = LVI->getConstant(Pointer, I->getParent(), I);
264  if (!C) return false;
265 
266  ++NumMemAccess;
267  I->replaceUsesOfWith(Pointer, C);
268  return true;
269 }
270 
271 /// See if LazyValueInfo's ability to exploit edge conditions or range
272 /// information is sufficient to prove this comparison. Even for local
273 /// conditions, this can sometimes prove conditions instcombine can't by
274 /// exploiting range information.
275 static bool processCmp(CmpInst *C, LazyValueInfo *LVI) {
276  Value *Op0 = C->getOperand(0);
277  Constant *Op1 = dyn_cast<Constant>(C->getOperand(1));
278  if (!Op1) return false;
279 
280  // As a policy choice, we choose not to waste compile time on anything where
281  // the comparison is testing local values. While LVI can sometimes reason
282  // about such cases, it's not its primary purpose. We do make sure to do
283  // the block local query for uses from terminator instructions, but that's
284  // handled in the code for each terminator.
285  auto *I = dyn_cast<Instruction>(Op0);
286  if (I && I->getParent() == C->getParent())
287  return false;
288 
289  LazyValueInfo::Tristate Result =
290  LVI->getPredicateAt(C->getPredicate(), Op0, Op1, C);
291  if (Result == LazyValueInfo::Unknown) return false;
292 
293  ++NumCmps;
294  if (Result == LazyValueInfo::True)
296  else
298  C->eraseFromParent();
299 
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  Value *Cond = SI->getCondition();
312  BasicBlock *BB = SI->getParent();
313 
314  // If the condition was defined in same block as the switch then LazyValueInfo
315  // currently won't say anything useful about it, though in theory it could.
316  if (isa<Instruction>(Cond) && cast<Instruction>(Cond)->getParent() == BB)
317  return false;
318 
319  // If the switch is unreachable then trying to improve it is a waste of time.
320  pred_iterator PB = pred_begin(BB), PE = pred_end(BB);
321  if (PB == PE) return false;
322 
323  // Analyse each switch case in turn.
324  bool Changed = false;
325  DenseMap<BasicBlock*, int> SuccessorsCount;
326  for (auto *Succ : successors(BB))
327  SuccessorsCount[Succ]++;
328 
329  for (auto CI = SI->case_begin(), CE = SI->case_end(); CI != CE;) {
330  ConstantInt *Case = CI->getCaseValue();
331 
332  // Check to see if the switch condition is equal to/not equal to the case
333  // value on every incoming edge, equal/not equal being the same each time.
335  for (pred_iterator PI = PB; PI != PE; ++PI) {
336  // Is the switch condition equal to the case value?
338  Cond, Case, *PI,
339  BB, SI);
340  // Give up on this case if nothing is known.
341  if (Value == LazyValueInfo::Unknown) {
342  State = LazyValueInfo::Unknown;
343  break;
344  }
345 
346  // If this was the first edge to be visited, record that all other edges
347  // need to give the same result.
348  if (PI == PB) {
349  State = Value;
350  continue;
351  }
352 
353  // If this case is known to fire for some edges and known not to fire for
354  // others then there is nothing we can do - give up.
355  if (Value != State) {
356  State = LazyValueInfo::Unknown;
357  break;
358  }
359  }
360 
361  if (State == LazyValueInfo::False) {
362  // This case never fires - remove it.
363  BasicBlock *Succ = CI->getCaseSuccessor();
364  Succ->removePredecessor(BB);
365  CI = SI->removeCase(CI);
366  CE = SI->case_end();
367 
368  // The condition can be modified by removePredecessor's PHI simplification
369  // logic.
370  Cond = SI->getCondition();
371 
372  ++NumDeadCases;
373  Changed = true;
374  if (--SuccessorsCount[Succ] == 0)
375  DT->deleteEdge(BB, Succ);
376  continue;
377  }
378  if (State == LazyValueInfo::True) {
379  // This case always fires. Arrange for the switch to be turned into an
380  // unconditional branch by replacing the switch condition with the case
381  // value.
382  SI->setCondition(Case);
383  NumDeadCases += SI->getNumCases();
384  Changed = true;
385  break;
386  }
387 
388  // Increment the case iterator since we didn't delete it.
389  ++CI;
390  }
391 
392  if (Changed) {
393  // If the switch has been simplified to the point where it can be replaced
394  // by a branch then do so now.
395  DeferredDominance DDT(*DT);
396  ConstantFoldTerminator(BB, /*DeleteDeadConditions = */ false,
397  /*TLI = */ nullptr, &DDT);
398  DDT.flush();
399  }
400 
401  return Changed;
402 }
403 
404 // See if we can prove that the given overflow intrinsic will not overflow.
406  using OBO = OverflowingBinaryOperator;
407  auto NoWrap = [&] (Instruction::BinaryOps BinOp, unsigned NoWrapKind) {
408  Value *RHS = II->getOperand(1);
409  ConstantRange RRange = LVI->getConstantRange(RHS, II->getParent(), II);
411  BinOp, RRange, NoWrapKind);
412  // As an optimization, do not compute LRange if we do not need it.
413  if (NWRegion.isEmptySet())
414  return false;
415  Value *LHS = II->getOperand(0);
416  ConstantRange LRange = LVI->getConstantRange(LHS, II->getParent(), II);
417  return NWRegion.contains(LRange);
418  };
419  switch (II->getIntrinsicID()) {
420  default:
421  break;
422  case Intrinsic::uadd_with_overflow:
423  return NoWrap(Instruction::Add, OBO::NoUnsignedWrap);
424  case Intrinsic::sadd_with_overflow:
425  return NoWrap(Instruction::Add, OBO::NoSignedWrap);
426  case Intrinsic::usub_with_overflow:
427  return NoWrap(Instruction::Sub, OBO::NoUnsignedWrap);
428  case Intrinsic::ssub_with_overflow:
429  return NoWrap(Instruction::Sub, OBO::NoSignedWrap);
430  }
431  return false;
432 }
433 
435  Value *NewOp = nullptr;
436  switch (II->getIntrinsicID()) {
437  default:
438  llvm_unreachable("Unexpected instruction.");
439  case Intrinsic::uadd_with_overflow:
440  case Intrinsic::sadd_with_overflow:
441  NewOp = BinaryOperator::CreateAdd(II->getOperand(0), II->getOperand(1),
442  II->getName(), II);
443  break;
444  case Intrinsic::usub_with_overflow:
445  case Intrinsic::ssub_with_overflow:
446  NewOp = BinaryOperator::CreateSub(II->getOperand(0), II->getOperand(1),
447  II->getName(), II);
448  break;
449  }
450  ++NumOverflows;
451  IRBuilder<> B(II);
452  Value *NewI = B.CreateInsertValue(UndefValue::get(II->getType()), NewOp, 0);
453  NewI = B.CreateInsertValue(NewI, ConstantInt::getFalse(II->getContext()), 1);
454  II->replaceAllUsesWith(NewI);
455  II->eraseFromParent();
456 }
457 
458 /// Infer nonnull attributes for the arguments at the specified callsite.
459 static bool processCallSite(CallSite CS, LazyValueInfo *LVI) {
461  unsigned ArgNo = 0;
462 
463  if (auto *II = dyn_cast<IntrinsicInst>(CS.getInstruction())) {
464  if (willNotOverflow(II, LVI)) {
466  return true;
467  }
468  }
469 
470  for (Value *V : CS.args()) {
471  PointerType *Type = dyn_cast<PointerType>(V->getType());
472  // Try to mark pointer typed parameters as non-null. We skip the
473  // relatively expensive analysis for constants which are obviously either
474  // null or non-null to start with.
475  if (Type && !CS.paramHasAttr(ArgNo, Attribute::NonNull) &&
476  !isa<Constant>(V) &&
480  ArgNos.push_back(ArgNo);
481  ArgNo++;
482  }
483 
484  assert(ArgNo == CS.arg_size() && "sanity check");
485 
486  if (ArgNos.empty())
487  return false;
488 
490  LLVMContext &Ctx = CS.getInstruction()->getContext();
491  AS = AS.addParamAttribute(Ctx, ArgNos,
492  Attribute::get(Ctx, Attribute::NonNull));
493  CS.setAttributes(AS);
494 
495  return true;
496 }
497 
499  Constant *Zero = ConstantInt::get(SDI->getType(), 0);
500  for (Value *O : SDI->operands()) {
501  auto Result = LVI->getPredicateAt(ICmpInst::ICMP_SGE, O, Zero, SDI);
502  if (Result != LazyValueInfo::True)
503  return false;
504  }
505  return true;
506 }
507 
508 /// Try to shrink a udiv/urem's width down to the smallest power of two that's
509 /// sufficient to contain its operands.
510 static bool processUDivOrURem(BinaryOperator *Instr, LazyValueInfo *LVI) {
511  assert(Instr->getOpcode() == Instruction::UDiv ||
512  Instr->getOpcode() == Instruction::URem);
513  if (Instr->getType()->isVectorTy())
514  return false;
515 
516  // Find the smallest power of two bitwidth that's sufficient to hold Instr's
517  // operands.
518  auto OrigWidth = Instr->getType()->getIntegerBitWidth();
519  ConstantRange OperandRange(OrigWidth, /*isFullset=*/false);
520  for (Value *Operand : Instr->operands()) {
521  OperandRange = OperandRange.unionWith(
522  LVI->getConstantRange(Operand, Instr->getParent()));
523  }
524  // Don't shrink below 8 bits wide.
525  unsigned NewWidth = std::max<unsigned>(
526  PowerOf2Ceil(OperandRange.getUnsignedMax().getActiveBits()), 8);
527  // NewWidth might be greater than OrigWidth if OrigWidth is not a power of
528  // two.
529  if (NewWidth >= OrigWidth)
530  return false;
531 
532  ++NumUDivs;
533  auto *TruncTy = Type::getIntNTy(Instr->getContext(), NewWidth);
534  auto *LHS = CastInst::Create(Instruction::Trunc, Instr->getOperand(0), TruncTy,
535  Instr->getName() + ".lhs.trunc", Instr);
536  auto *RHS = CastInst::Create(Instruction::Trunc, Instr->getOperand(1), TruncTy,
537  Instr->getName() + ".rhs.trunc", Instr);
538  auto *BO =
539  BinaryOperator::Create(Instr->getOpcode(), LHS, RHS, Instr->getName(), Instr);
540  auto *Zext = CastInst::Create(Instruction::ZExt, BO, Instr->getType(),
541  Instr->getName() + ".zext", Instr);
542  if (BO->getOpcode() == Instruction::UDiv)
543  BO->setIsExact(Instr->isExact());
544 
545  Instr->replaceAllUsesWith(Zext);
546  Instr->eraseFromParent();
547  return true;
548 }
549 
550 static bool processSRem(BinaryOperator *SDI, LazyValueInfo *LVI) {
551  if (SDI->getType()->isVectorTy() || !hasPositiveOperands(SDI, LVI))
552  return false;
553 
554  ++NumSRems;
555  auto *BO = BinaryOperator::CreateURem(SDI->getOperand(0), SDI->getOperand(1),
556  SDI->getName(), SDI);
557  SDI->replaceAllUsesWith(BO);
558  SDI->eraseFromParent();
559 
560  // Try to process our new urem.
561  processUDivOrURem(BO, LVI);
562 
563  return true;
564 }
565 
566 /// See if LazyValueInfo's ability to exploit edge conditions or range
567 /// information is sufficient to prove the both operands of this SDiv are
568 /// positive. If this is the case, replace the SDiv with a UDiv. Even for local
569 /// conditions, this can sometimes prove conditions instcombine can't by
570 /// exploiting range information.
571 static bool processSDiv(BinaryOperator *SDI, LazyValueInfo *LVI) {
572  if (SDI->getType()->isVectorTy() || !hasPositiveOperands(SDI, LVI))
573  return false;
574 
575  ++NumSDivs;
576  auto *BO = BinaryOperator::CreateUDiv(SDI->getOperand(0), SDI->getOperand(1),
577  SDI->getName(), SDI);
578  BO->setIsExact(SDI->isExact());
579  SDI->replaceAllUsesWith(BO);
580  SDI->eraseFromParent();
581 
582  // Try to simplify our new udiv.
583  processUDivOrURem(BO, LVI);
584 
585  return true;
586 }
587 
588 static bool processAShr(BinaryOperator *SDI, LazyValueInfo *LVI) {
589  if (SDI->getType()->isVectorTy())
590  return false;
591 
592  Constant *Zero = ConstantInt::get(SDI->getType(), 0);
593  if (LVI->getPredicateAt(ICmpInst::ICMP_SGE, SDI->getOperand(0), Zero, SDI) !=
595  return false;
596 
597  ++NumAShrs;
598  auto *BO = BinaryOperator::CreateLShr(SDI->getOperand(0), SDI->getOperand(1),
599  SDI->getName(), SDI);
600  BO->setIsExact(SDI->isExact());
601  SDI->replaceAllUsesWith(BO);
602  SDI->eraseFromParent();
603 
604  return true;
605 }
606 
607 static bool processAdd(BinaryOperator *AddOp, LazyValueInfo *LVI) {
608  using OBO = OverflowingBinaryOperator;
609 
610  if (DontProcessAdds)
611  return false;
612 
613  if (AddOp->getType()->isVectorTy())
614  return false;
615 
616  bool NSW = AddOp->hasNoSignedWrap();
617  bool NUW = AddOp->hasNoUnsignedWrap();
618  if (NSW && NUW)
619  return false;
620 
621  BasicBlock *BB = AddOp->getParent();
622 
623  Value *LHS = AddOp->getOperand(0);
624  Value *RHS = AddOp->getOperand(1);
625 
626  ConstantRange LRange = LVI->getConstantRange(LHS, BB, AddOp);
627 
628  // Initialize RRange only if we need it. If we know that guaranteed no wrap
629  // range for the given LHS range is empty don't spend time calculating the
630  // range for the RHS.
632  auto LazyRRange = [&] () {
633  if (!RRange)
634  RRange = LVI->getConstantRange(RHS, BB, AddOp);
635  return RRange.getValue();
636  };
637 
638  bool Changed = false;
639  if (!NUW) {
641  BinaryOperator::Add, LRange, OBO::NoUnsignedWrap);
642  if (!NUWRange.isEmptySet()) {
643  bool NewNUW = NUWRange.contains(LazyRRange());
644  AddOp->setHasNoUnsignedWrap(NewNUW);
645  Changed |= NewNUW;
646  }
647  }
648  if (!NSW) {
650  BinaryOperator::Add, LRange, OBO::NoSignedWrap);
651  if (!NSWRange.isEmptySet()) {
652  bool NewNSW = NSWRange.contains(LazyRRange());
653  AddOp->setHasNoSignedWrap(NewNSW);
654  Changed |= NewNSW;
655  }
656  }
657 
658  return Changed;
659 }
660 
662  if (Constant *C = LVI->getConstant(V, At->getParent(), At))
663  return C;
664 
665  // TODO: The following really should be sunk inside LVI's core algorithm, or
666  // at least the outer shims around such.
667  auto *C = dyn_cast<CmpInst>(V);
668  if (!C) return nullptr;
669 
670  Value *Op0 = C->getOperand(0);
671  Constant *Op1 = dyn_cast<Constant>(C->getOperand(1));
672  if (!Op1) return nullptr;
673 
674  LazyValueInfo::Tristate Result =
675  LVI->getPredicateAt(C->getPredicate(), Op0, Op1, At);
676  if (Result == LazyValueInfo::Unknown)
677  return nullptr;
678 
679  return (Result == LazyValueInfo::True) ?
682 }
683 
684 static bool runImpl(Function &F, LazyValueInfo *LVI, DominatorTree *DT,
685  const SimplifyQuery &SQ) {
686  bool FnChanged = false;
687  // Visiting in a pre-order depth-first traversal causes us to simplify early
688  // blocks before querying later blocks (which require us to analyze early
689  // blocks). Eagerly simplifying shallow blocks means there is strictly less
690  // work to do for deep blocks. This also means we don't visit unreachable
691  // blocks.
692  for (BasicBlock *BB : depth_first(&F.getEntryBlock())) {
693  bool BBChanged = false;
694  for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) {
695  Instruction *II = &*BI++;
696  switch (II->getOpcode()) {
697  case Instruction::Select:
698  BBChanged |= processSelect(cast<SelectInst>(II), LVI);
699  break;
700  case Instruction::PHI:
701  BBChanged |= processPHI(cast<PHINode>(II), LVI, DT, SQ);
702  break;
703  case Instruction::ICmp:
704  case Instruction::FCmp:
705  BBChanged |= processCmp(cast<CmpInst>(II), LVI);
706  break;
707  case Instruction::Load:
708  case Instruction::Store:
709  BBChanged |= processMemAccess(II, LVI);
710  break;
711  case Instruction::Call:
712  case Instruction::Invoke:
713  BBChanged |= processCallSite(CallSite(II), LVI);
714  break;
715  case Instruction::SRem:
716  BBChanged |= processSRem(cast<BinaryOperator>(II), LVI);
717  break;
718  case Instruction::SDiv:
719  BBChanged |= processSDiv(cast<BinaryOperator>(II), LVI);
720  break;
721  case Instruction::UDiv:
722  case Instruction::URem:
723  BBChanged |= processUDivOrURem(cast<BinaryOperator>(II), LVI);
724  break;
725  case Instruction::AShr:
726  BBChanged |= processAShr(cast<BinaryOperator>(II), LVI);
727  break;
728  case Instruction::Add:
729  BBChanged |= processAdd(cast<BinaryOperator>(II), LVI);
730  break;
731  }
732  }
733 
734  Instruction *Term = BB->getTerminator();
735  switch (Term->getOpcode()) {
736  case Instruction::Switch:
737  BBChanged |= processSwitch(cast<SwitchInst>(Term), LVI, DT);
738  break;
739  case Instruction::Ret: {
740  auto *RI = cast<ReturnInst>(Term);
741  // Try to determine the return value if we can. This is mainly here to
742  // simplify the writing of unit tests, but also helps to enable IPO by
743  // constant folding the return values of callees.
744  auto *RetVal = RI->getReturnValue();
745  if (!RetVal) break; // handle "ret void"
746  if (isa<Constant>(RetVal)) break; // nothing to do
747  if (auto *C = getConstantAt(RetVal, RI, LVI)) {
748  ++NumReturns;
749  RI->replaceUsesOfWith(RetVal, C);
750  BBChanged = true;
751  }
752  }
753  }
754 
755  FnChanged |= BBChanged;
756  }
757 
758  return FnChanged;
759 }
760 
762  if (skipFunction(F))
763  return false;
764 
765  LazyValueInfo *LVI = &getAnalysis<LazyValueInfoWrapperPass>().getLVI();
766  DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
767 
768  return runImpl(F, LVI, DT, getBestSimplifyQuery(*this, F));
769 }
770 
775 
776  bool Changed = runImpl(F, LVI, DT, getBestSimplifyQuery(AM, F));
777 
778  if (!Changed)
779  return PreservedAnalyses::all();
781  PA.preserve<GlobalsAA>();
783  return PA;
784 }
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:574
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:875
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:687
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
BinaryOps getOpcode() const
Definition: InstrTypes.h:555
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.
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:713
STATISTIC(NumFunctions, "Total number of functions")
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:225
F(f)
An instruction for reading from memory.
Definition: Instructions.h:164
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:227
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:731
void deleteEdge(NodeT *From, NodeT *To)
Inform the dominator tree about a CFG edge deletion and update the tree.
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:770
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:1517
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
DominatorTree & flush()
Flushes all pending updates and block deletions.
Definition: Dominators.cpp:443
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:142
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:626
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:153
static ConstantPointerNull * get(PointerType *T)
Static factory methods - Return objects of the specified value.
Definition: Constants.cpp:1368
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.
bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions=false, const TargetLibraryInfo *TLI=nullptr, DeferredDominance *DDT=nullptr)
If a terminator instruction is predicated on a constant value, convert it into an unconditional branc...
Definition: Local.cpp:103
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:1382
const AMDGPUAS & AS
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
#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:861
bool dominates(const Instruction *Def, const Use &U) const
Return true if Def dominates a use in User.
Definition: Dominators.cpp:244
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:611
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:567
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:924
Class to defer updates to a DominatorTree.
Definition: Dominators.h:307
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:959
void setCondition(Value *V)
unsigned getIntegerBitWidth() const
Definition: DerivedTypes.h:97
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:62
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: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: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 nsw 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(BasicBlock *BB)
Definition: CFG.h:149
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:254
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:1971
This header defines various interfaces for pass management in LLVM.
void setIncomingValue(unsigned i, Value *V)
#define LLVM_DEBUG(X)
Definition: Debug.h:119
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:913
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:651
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:44
const BasicBlock * getParent() const
Definition: Instruction.h:67