LLVM  6.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/Function.h"
31 #include "llvm/IR/InstrTypes.h"
32 #include "llvm/IR/Instruction.h"
33 #include "llvm/IR/Instructions.h"
34 #include "llvm/IR/IntrinsicInst.h"
35 #include "llvm/IR/IRBuilder.h"
36 #include "llvm/IR/Operator.h"
37 #include "llvm/IR/PassManager.h"
38 #include "llvm/IR/Type.h"
39 #include "llvm/IR/Value.h"
40 #include "llvm/Pass.h"
41 #include "llvm/Support/Casting.h"
43 #include "llvm/Support/Debug.h"
45 #include "llvm/Transforms/Scalar.h"
47 #include <cassert>
48 #include <utility>
49 
50 using namespace llvm;
51 
52 #define DEBUG_TYPE "correlated-value-propagation"
53 
54 STATISTIC(NumPhis, "Number of phis propagated");
55 STATISTIC(NumSelects, "Number of selects propagated");
56 STATISTIC(NumMemAccess, "Number of memory access targets propagated");
57 STATISTIC(NumCmps, "Number of comparisons propagated");
58 STATISTIC(NumReturns, "Number of return values propagated");
59 STATISTIC(NumDeadCases, "Number of switch cases removed");
60 STATISTIC(NumSDivs, "Number of sdiv converted to udiv");
61 STATISTIC(NumAShrs, "Number of ashr converted to lshr");
62 STATISTIC(NumSRems, "Number of srem converted to urem");
63 STATISTIC(NumOverflows, "Number of overflow checks removed");
64 
65 static cl::opt<bool> DontProcessAdds("cvp-dont-process-adds", cl::init(true));
66 
67 namespace {
68 
69  class CorrelatedValuePropagation : public FunctionPass {
70  public:
71  static char ID;
72 
73  CorrelatedValuePropagation(): FunctionPass(ID) {
75  }
76 
77  bool runOnFunction(Function &F) override;
78 
79  void getAnalysisUsage(AnalysisUsage &AU) const override {
82  }
83  };
84 
85 } // end anonymous namespace
86 
88 
89 INITIALIZE_PASS_BEGIN(CorrelatedValuePropagation, "correlated-propagation",
90  "Value Propagation", false, false)
92 INITIALIZE_PASS_END(CorrelatedValuePropagation, "correlated-propagation",
93  "Value Propagation", false, false)
94 
95 // Public interface to the Value Propagation pass
97  return new CorrelatedValuePropagation();
98 }
99 
100 static bool processSelect(SelectInst *S, LazyValueInfo *LVI) {
101  if (S->getType()->isVectorTy()) return false;
102  if (isa<Constant>(S->getOperand(0))) return false;
103 
104  Constant *C = LVI->getConstant(S->getOperand(0), S->getParent(), S);
105  if (!C) return false;
106 
108  if (!CI) return false;
109 
110  Value *ReplaceWith = S->getOperand(1);
111  Value *Other = S->getOperand(2);
112  if (!CI->isOne()) std::swap(ReplaceWith, Other);
113  if (ReplaceWith == S) ReplaceWith = UndefValue::get(S->getType());
114 
115  S->replaceAllUsesWith(ReplaceWith);
116  S->eraseFromParent();
117 
118  ++NumSelects;
119 
120  return true;
121 }
122 
123 static bool processPHI(PHINode *P, LazyValueInfo *LVI,
124  const SimplifyQuery &SQ) {
125  bool Changed = false;
126 
127  BasicBlock *BB = P->getParent();
128  for (unsigned i = 0, e = P->getNumIncomingValues(); i < e; ++i) {
129  Value *Incoming = P->getIncomingValue(i);
130  if (isa<Constant>(Incoming)) continue;
131 
132  Value *V = LVI->getConstantOnEdge(Incoming, P->getIncomingBlock(i), BB, P);
133 
134  // Look if the incoming value is a select with a scalar condition for which
135  // LVI can tells us the value. In that case replace the incoming value with
136  // the appropriate value of the select. This often allows us to remove the
137  // select later.
138  if (!V) {
139  SelectInst *SI = dyn_cast<SelectInst>(Incoming);
140  if (!SI) continue;
141 
142  Value *Condition = SI->getCondition();
143  if (!Condition->getType()->isVectorTy()) {
144  if (Constant *C = LVI->getConstantOnEdge(
145  Condition, P->getIncomingBlock(i), BB, P)) {
146  if (C->isOneValue()) {
147  V = SI->getTrueValue();
148  } else if (C->isZeroValue()) {
149  V = SI->getFalseValue();
150  }
151  // Once LVI learns to handle vector types, we could also add support
152  // for vector type constants that are not all zeroes or all ones.
153  }
154  }
155 
156  // Look if the select has a constant but LVI tells us that the incoming
157  // value can never be that constant. In that case replace the incoming
158  // value with the other value of the select. This often allows us to
159  // remove the select later.
160  if (!V) {
162  if (!C) continue;
163 
164  if (LVI->getPredicateOnEdge(ICmpInst::ICMP_EQ, SI, C,
165  P->getIncomingBlock(i), BB, P) !=
167  continue;
168  V = SI->getTrueValue();
169  }
170 
171  DEBUG(dbgs() << "CVP: Threading PHI over " << *SI << '\n');
172  }
173 
174  P->setIncomingValue(i, V);
175  Changed = true;
176  }
177 
178  if (Value *V = SimplifyInstruction(P, SQ)) {
179  P->replaceAllUsesWith(V);
180  P->eraseFromParent();
181  Changed = true;
182  }
183 
184  if (Changed)
185  ++NumPhis;
186 
187  return Changed;
188 }
189 
191  Value *Pointer = nullptr;
192  if (LoadInst *L = dyn_cast<LoadInst>(I))
193  Pointer = L->getPointerOperand();
194  else
195  Pointer = cast<StoreInst>(I)->getPointerOperand();
196 
197  if (isa<Constant>(Pointer)) return false;
198 
199  Constant *C = LVI->getConstant(Pointer, I->getParent(), I);
200  if (!C) return false;
201 
202  ++NumMemAccess;
203  I->replaceUsesOfWith(Pointer, C);
204  return true;
205 }
206 
207 /// See if LazyValueInfo's ability to exploit edge conditions or range
208 /// information is sufficient to prove this comparison. Even for local
209 /// conditions, this can sometimes prove conditions instcombine can't by
210 /// exploiting range information.
211 static bool processCmp(CmpInst *C, LazyValueInfo *LVI) {
212  Value *Op0 = C->getOperand(0);
213  Constant *Op1 = dyn_cast<Constant>(C->getOperand(1));
214  if (!Op1) return false;
215 
216  // As a policy choice, we choose not to waste compile time on anything where
217  // the comparison is testing local values. While LVI can sometimes reason
218  // about such cases, it's not its primary purpose. We do make sure to do
219  // the block local query for uses from terminator instructions, but that's
220  // handled in the code for each terminator.
221  auto *I = dyn_cast<Instruction>(Op0);
222  if (I && I->getParent() == C->getParent())
223  return false;
224 
225  LazyValueInfo::Tristate Result =
226  LVI->getPredicateAt(C->getPredicate(), Op0, Op1, C);
227  if (Result == LazyValueInfo::Unknown) return false;
228 
229  ++NumCmps;
230  if (Result == LazyValueInfo::True)
232  else
234  C->eraseFromParent();
235 
236  return true;
237 }
238 
239 /// Simplify a switch instruction by removing cases which can never fire. If the
240 /// uselessness of a case could be determined locally then constant propagation
241 /// would already have figured it out. Instead, walk the predecessors and
242 /// statically evaluate cases based on information available on that edge. Cases
243 /// that cannot fire no matter what the incoming edge can safely be removed. If
244 /// a case fires on every incoming edge then the entire switch can be removed
245 /// and replaced with a branch to the case destination.
247  Value *Cond = SI->getCondition();
248  BasicBlock *BB = SI->getParent();
249 
250  // If the condition was defined in same block as the switch then LazyValueInfo
251  // currently won't say anything useful about it, though in theory it could.
252  if (isa<Instruction>(Cond) && cast<Instruction>(Cond)->getParent() == BB)
253  return false;
254 
255  // If the switch is unreachable then trying to improve it is a waste of time.
256  pred_iterator PB = pred_begin(BB), PE = pred_end(BB);
257  if (PB == PE) return false;
258 
259  // Analyse each switch case in turn.
260  bool Changed = false;
261  for (auto CI = SI->case_begin(), CE = SI->case_end(); CI != CE;) {
262  ConstantInt *Case = CI->getCaseValue();
263 
264  // Check to see if the switch condition is equal to/not equal to the case
265  // value on every incoming edge, equal/not equal being the same each time.
267  for (pred_iterator PI = PB; PI != PE; ++PI) {
268  // Is the switch condition equal to the case value?
270  Cond, Case, *PI,
271  BB, SI);
272  // Give up on this case if nothing is known.
273  if (Value == LazyValueInfo::Unknown) {
274  State = LazyValueInfo::Unknown;
275  break;
276  }
277 
278  // If this was the first edge to be visited, record that all other edges
279  // need to give the same result.
280  if (PI == PB) {
281  State = Value;
282  continue;
283  }
284 
285  // If this case is known to fire for some edges and known not to fire for
286  // others then there is nothing we can do - give up.
287  if (Value != State) {
288  State = LazyValueInfo::Unknown;
289  break;
290  }
291  }
292 
293  if (State == LazyValueInfo::False) {
294  // This case never fires - remove it.
295  CI->getCaseSuccessor()->removePredecessor(BB);
296  CI = SI->removeCase(CI);
297  CE = SI->case_end();
298 
299  // The condition can be modified by removePredecessor's PHI simplification
300  // logic.
301  Cond = SI->getCondition();
302 
303  ++NumDeadCases;
304  Changed = true;
305  continue;
306  }
307  if (State == LazyValueInfo::True) {
308  // This case always fires. Arrange for the switch to be turned into an
309  // unconditional branch by replacing the switch condition with the case
310  // value.
311  SI->setCondition(Case);
312  NumDeadCases += SI->getNumCases();
313  Changed = true;
314  break;
315  }
316 
317  // Increment the case iterator since we didn't delete it.
318  ++CI;
319  }
320 
321  if (Changed)
322  // If the switch has been simplified to the point where it can be replaced
323  // by a branch then do so now.
325 
326  return Changed;
327 }
328 
329 // See if we can prove that the given overflow intrinsic will not overflow.
331  using OBO = OverflowingBinaryOperator;
332  auto NoWrap = [&] (Instruction::BinaryOps BinOp, unsigned NoWrapKind) {
333  Value *RHS = II->getOperand(1);
334  ConstantRange RRange = LVI->getConstantRange(RHS, II->getParent(), II);
336  BinOp, RRange, NoWrapKind);
337  // As an optimization, do not compute LRange if we do not need it.
338  if (NWRegion.isEmptySet())
339  return false;
340  Value *LHS = II->getOperand(0);
341  ConstantRange LRange = LVI->getConstantRange(LHS, II->getParent(), II);
342  return NWRegion.contains(LRange);
343  };
344  switch (II->getIntrinsicID()) {
345  default:
346  break;
347  case Intrinsic::uadd_with_overflow:
348  return NoWrap(Instruction::Add, OBO::NoUnsignedWrap);
349  case Intrinsic::sadd_with_overflow:
350  return NoWrap(Instruction::Add, OBO::NoSignedWrap);
351  case Intrinsic::usub_with_overflow:
352  return NoWrap(Instruction::Sub, OBO::NoUnsignedWrap);
353  case Intrinsic::ssub_with_overflow:
354  return NoWrap(Instruction::Sub, OBO::NoSignedWrap);
355  }
356  return false;
357 }
358 
360  Value *NewOp = nullptr;
361  switch (II->getIntrinsicID()) {
362  default:
363  llvm_unreachable("Unexpected instruction.");
364  case Intrinsic::uadd_with_overflow:
365  case Intrinsic::sadd_with_overflow:
366  NewOp = BinaryOperator::CreateAdd(II->getOperand(0), II->getOperand(1),
367  II->getName(), II);
368  break;
369  case Intrinsic::usub_with_overflow:
370  case Intrinsic::ssub_with_overflow:
371  NewOp = BinaryOperator::CreateSub(II->getOperand(0), II->getOperand(1),
372  II->getName(), II);
373  break;
374  }
375  ++NumOverflows;
376  IRBuilder<> B(II);
377  Value *NewI = B.CreateInsertValue(UndefValue::get(II->getType()), NewOp, 0);
378  NewI = B.CreateInsertValue(NewI, ConstantInt::getFalse(II->getContext()), 1);
379  II->replaceAllUsesWith(NewI);
380  II->eraseFromParent();
381 }
382 
383 /// Infer nonnull attributes for the arguments at the specified callsite.
384 static bool processCallSite(CallSite CS, LazyValueInfo *LVI) {
386  unsigned ArgNo = 0;
387 
388  if (auto *II = dyn_cast<IntrinsicInst>(CS.getInstruction())) {
389  if (willNotOverflow(II, LVI)) {
391  return true;
392  }
393  }
394 
395  for (Value *V : CS.args()) {
396  PointerType *Type = dyn_cast<PointerType>(V->getType());
397  // Try to mark pointer typed parameters as non-null. We skip the
398  // relatively expensive analysis for constants which are obviously either
399  // null or non-null to start with.
400  if (Type && !CS.paramHasAttr(ArgNo, Attribute::NonNull) &&
401  !isa<Constant>(V) &&
405  ArgNos.push_back(ArgNo);
406  ArgNo++;
407  }
408 
409  assert(ArgNo == CS.arg_size() && "sanity check");
410 
411  if (ArgNos.empty())
412  return false;
413 
415  LLVMContext &Ctx = CS.getInstruction()->getContext();
416  AS = AS.addParamAttribute(Ctx, ArgNos,
417  Attribute::get(Ctx, Attribute::NonNull));
418  CS.setAttributes(AS);
419 
420  return true;
421 }
422 
424  Constant *Zero = ConstantInt::get(SDI->getType(), 0);
425  for (Value *O : SDI->operands()) {
426  auto Result = LVI->getPredicateAt(ICmpInst::ICMP_SGE, O, Zero, SDI);
427  if (Result != LazyValueInfo::True)
428  return false;
429  }
430  return true;
431 }
432 
433 static bool processSRem(BinaryOperator *SDI, LazyValueInfo *LVI) {
434  if (SDI->getType()->isVectorTy() ||
435  !hasPositiveOperands(SDI, LVI))
436  return false;
437 
438  ++NumSRems;
439  auto *BO = BinaryOperator::CreateURem(SDI->getOperand(0), SDI->getOperand(1),
440  SDI->getName(), SDI);
441  SDI->replaceAllUsesWith(BO);
442  SDI->eraseFromParent();
443  return true;
444 }
445 
446 /// See if LazyValueInfo's ability to exploit edge conditions or range
447 /// information is sufficient to prove the both operands of this SDiv are
448 /// positive. If this is the case, replace the SDiv with a UDiv. Even for local
449 /// conditions, this can sometimes prove conditions instcombine can't by
450 /// exploiting range information.
451 static bool processSDiv(BinaryOperator *SDI, LazyValueInfo *LVI) {
452  if (SDI->getType()->isVectorTy() ||
453  !hasPositiveOperands(SDI, LVI))
454  return false;
455 
456  ++NumSDivs;
457  auto *BO = BinaryOperator::CreateUDiv(SDI->getOperand(0), SDI->getOperand(1),
458  SDI->getName(), SDI);
459  BO->setIsExact(SDI->isExact());
460  SDI->replaceAllUsesWith(BO);
461  SDI->eraseFromParent();
462 
463  return true;
464 }
465 
466 static bool processAShr(BinaryOperator *SDI, LazyValueInfo *LVI) {
467  if (SDI->getType()->isVectorTy())
468  return false;
469 
470  Constant *Zero = ConstantInt::get(SDI->getType(), 0);
471  if (LVI->getPredicateAt(ICmpInst::ICMP_SGE, SDI->getOperand(0), Zero, SDI) !=
473  return false;
474 
475  ++NumAShrs;
476  auto *BO = BinaryOperator::CreateLShr(SDI->getOperand(0), SDI->getOperand(1),
477  SDI->getName(), SDI);
478  BO->setIsExact(SDI->isExact());
479  SDI->replaceAllUsesWith(BO);
480  SDI->eraseFromParent();
481 
482  return true;
483 }
484 
485 static bool processAdd(BinaryOperator *AddOp, LazyValueInfo *LVI) {
486  using OBO = OverflowingBinaryOperator;
487 
488  if (DontProcessAdds)
489  return false;
490 
491  if (AddOp->getType()->isVectorTy())
492  return false;
493 
494  bool NSW = AddOp->hasNoSignedWrap();
495  bool NUW = AddOp->hasNoUnsignedWrap();
496  if (NSW && NUW)
497  return false;
498 
499  BasicBlock *BB = AddOp->getParent();
500 
501  Value *LHS = AddOp->getOperand(0);
502  Value *RHS = AddOp->getOperand(1);
503 
504  ConstantRange LRange = LVI->getConstantRange(LHS, BB, AddOp);
505 
506  // Initialize RRange only if we need it. If we know that guaranteed no wrap
507  // range for the given LHS range is empty don't spend time calculating the
508  // range for the RHS.
510  auto LazyRRange = [&] () {
511  if (!RRange)
512  RRange = LVI->getConstantRange(RHS, BB, AddOp);
513  return RRange.getValue();
514  };
515 
516  bool Changed = false;
517  if (!NUW) {
519  BinaryOperator::Add, LRange, OBO::NoUnsignedWrap);
520  if (!NUWRange.isEmptySet()) {
521  bool NewNUW = NUWRange.contains(LazyRRange());
522  AddOp->setHasNoUnsignedWrap(NewNUW);
523  Changed |= NewNUW;
524  }
525  }
526  if (!NSW) {
528  BinaryOperator::Add, LRange, OBO::NoSignedWrap);
529  if (!NSWRange.isEmptySet()) {
530  bool NewNSW = NSWRange.contains(LazyRRange());
531  AddOp->setHasNoSignedWrap(NewNSW);
532  Changed |= NewNSW;
533  }
534  }
535 
536  return Changed;
537 }
538 
540  if (Constant *C = LVI->getConstant(V, At->getParent(), At))
541  return C;
542 
543  // TODO: The following really should be sunk inside LVI's core algorithm, or
544  // at least the outer shims around such.
545  auto *C = dyn_cast<CmpInst>(V);
546  if (!C) return nullptr;
547 
548  Value *Op0 = C->getOperand(0);
549  Constant *Op1 = dyn_cast<Constant>(C->getOperand(1));
550  if (!Op1) return nullptr;
551 
552  LazyValueInfo::Tristate Result =
553  LVI->getPredicateAt(C->getPredicate(), Op0, Op1, At);
554  if (Result == LazyValueInfo::Unknown)
555  return nullptr;
556 
557  return (Result == LazyValueInfo::True) ?
560 }
561 
562 static bool runImpl(Function &F, LazyValueInfo *LVI, const SimplifyQuery &SQ) {
563  bool FnChanged = false;
564  // Visiting in a pre-order depth-first traversal causes us to simplify early
565  // blocks before querying later blocks (which require us to analyze early
566  // blocks). Eagerly simplifying shallow blocks means there is strictly less
567  // work to do for deep blocks. This also means we don't visit unreachable
568  // blocks.
569  for (BasicBlock *BB : depth_first(&F.getEntryBlock())) {
570  bool BBChanged = false;
571  for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) {
572  Instruction *II = &*BI++;
573  switch (II->getOpcode()) {
574  case Instruction::Select:
575  BBChanged |= processSelect(cast<SelectInst>(II), LVI);
576  break;
577  case Instruction::PHI:
578  BBChanged |= processPHI(cast<PHINode>(II), LVI, SQ);
579  break;
580  case Instruction::ICmp:
581  case Instruction::FCmp:
582  BBChanged |= processCmp(cast<CmpInst>(II), LVI);
583  break;
584  case Instruction::Load:
585  case Instruction::Store:
586  BBChanged |= processMemAccess(II, LVI);
587  break;
588  case Instruction::Call:
589  case Instruction::Invoke:
590  BBChanged |= processCallSite(CallSite(II), LVI);
591  break;
592  case Instruction::SRem:
593  BBChanged |= processSRem(cast<BinaryOperator>(II), LVI);
594  break;
595  case Instruction::SDiv:
596  BBChanged |= processSDiv(cast<BinaryOperator>(II), LVI);
597  break;
598  case Instruction::AShr:
599  BBChanged |= processAShr(cast<BinaryOperator>(II), LVI);
600  break;
601  case Instruction::Add:
602  BBChanged |= processAdd(cast<BinaryOperator>(II), LVI);
603  break;
604  }
605  }
606 
607  Instruction *Term = BB->getTerminator();
608  switch (Term->getOpcode()) {
609  case Instruction::Switch:
610  BBChanged |= processSwitch(cast<SwitchInst>(Term), LVI);
611  break;
612  case Instruction::Ret: {
613  auto *RI = cast<ReturnInst>(Term);
614  // Try to determine the return value if we can. This is mainly here to
615  // simplify the writing of unit tests, but also helps to enable IPO by
616  // constant folding the return values of callees.
617  auto *RetVal = RI->getReturnValue();
618  if (!RetVal) break; // handle "ret void"
619  if (isa<Constant>(RetVal)) break; // nothing to do
620  if (auto *C = getConstantAt(RetVal, RI, LVI)) {
621  ++NumReturns;
622  RI->replaceUsesOfWith(RetVal, C);
623  BBChanged = true;
624  }
625  }
626  }
627 
628  FnChanged |= BBChanged;
629  }
630 
631  return FnChanged;
632 }
633 
635  if (skipFunction(F))
636  return false;
637 
638  LazyValueInfo *LVI = &getAnalysis<LazyValueInfoWrapperPass>().getLVI();
639  return runImpl(F, LVI, getBestSimplifyQuery(*this, F));
640 }
641 
644 
646  bool Changed = runImpl(F, LVI, getBestSimplifyQuery(AM, F));
647 
648  if (!Changed)
649  return PreservedAnalyses::all();
651  PA.preserve<GlobalsAA>();
652  return PA;
653 }
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:67
void push_back(const T &Elt)
Definition: SmallVector.h:212
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:522
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:843
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
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...
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
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:728
STATISTIC(NumFunctions, "Total number of functions")
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...
static Value * getPointerOperand(Instruction &Inst)
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:398
bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions=false, const TargetLibraryInfo *TLI=nullptr)
If a terminator instruction is predicated on a constant value, convert it into an unconditional branc...
Definition: Local.cpp:102
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:668
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:736
static bool runImpl(Function &F, LazyValueInfo *LVI, const SimplifyQuery &SQ)
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:127
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:430
static BinaryOperator * CreateAdd(Value *S1, Value *S2, const Twine &Name, Instruction *InsertBefore, Value *FlagsOp)
Value * getOperand(unsigned i) const
Definition: User.h:154
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
const BasicBlock & getEntryBlock() const
Definition: Function.h:572
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:406
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:1305
static bool processSwitch(SwitchInst *SI, LazyValueInfo *LVI)
Simplify a switch instruction by removing cases which can never fire.
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
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:222
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:1319
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 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 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:559
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:515
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:923
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:927
void setCondition(Value *V)
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:61
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:220
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
static const Function * getParent(const Value *V)
#define DEBUG(X)
Definition: Debug.h:118
correlated Value Propagation
static bool processPHI(PHINode *P, LazyValueInfo *LVI, const SimplifyQuery &SQ)
static Constant * getConstantAt(Value *V, Instruction *At, LazyValueInfo *LVI)
A container for analyses that lazily runs them and caches their results.
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:1763
This header defines various interfaces for pass management in LLVM.
void setIncomingValue(unsigned i, Value *V)
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...
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:881
Analysis to compute lazy value information.
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:44
const BasicBlock * getParent() const
Definition: Instruction.h:67