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