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