LLVM  14.0.0git
CorrelatedValuePropagation.cpp
Go to the documentation of this file.
1 //===- CorrelatedValuePropagation.cpp - Propagate CFG-derived info --------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements the Correlated Value Propagation pass.
10 //
11 //===----------------------------------------------------------------------===//
12 
15 #include "llvm/ADT/Optional.h"
16 #include "llvm/ADT/SmallVector.h"
17 #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/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/IRBuilder.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/Operator.h"
37 #include "llvm/IR/PassManager.h"
38 #include "llvm/IR/Type.h"
39 #include "llvm/IR/Value.h"
40 #include "llvm/InitializePasses.h"
41 #include "llvm/Pass.h"
42 #include "llvm/Support/Casting.h"
44 #include "llvm/Support/Debug.h"
46 #include "llvm/Transforms/Scalar.h"
48 #include <cassert>
49 #include <utility>
50 
51 using namespace llvm;
52 
53 #define DEBUG_TYPE "correlated-value-propagation"
54 
55 STATISTIC(NumPhis, "Number of phis propagated");
56 STATISTIC(NumPhiCommon, "Number of phis deleted via common incoming value");
57 STATISTIC(NumSelects, "Number of selects propagated");
58 STATISTIC(NumMemAccess, "Number of memory access targets propagated");
59 STATISTIC(NumCmps, "Number of comparisons propagated");
60 STATISTIC(NumReturns, "Number of return values propagated");
61 STATISTIC(NumDeadCases, "Number of switch cases removed");
62 STATISTIC(NumSDivSRemsNarrowed,
63  "Number of sdivs/srems whose width was decreased");
64 STATISTIC(NumSDivs, "Number of sdiv converted to udiv");
65 STATISTIC(NumUDivURemsNarrowed,
66  "Number of udivs/urems whose width was decreased");
67 STATISTIC(NumAShrs, "Number of ashr converted to lshr");
68 STATISTIC(NumSRems, "Number of srem converted to urem");
69 STATISTIC(NumSExt, "Number of sext converted to zext");
70 STATISTIC(NumAnd, "Number of ands removed");
71 STATISTIC(NumNW, "Number of no-wrap deductions");
72 STATISTIC(NumNSW, "Number of no-signed-wrap deductions");
73 STATISTIC(NumNUW, "Number of no-unsigned-wrap deductions");
74 STATISTIC(NumAddNW, "Number of no-wrap deductions for add");
75 STATISTIC(NumAddNSW, "Number of no-signed-wrap deductions for add");
76 STATISTIC(NumAddNUW, "Number of no-unsigned-wrap deductions for add");
77 STATISTIC(NumSubNW, "Number of no-wrap deductions for sub");
78 STATISTIC(NumSubNSW, "Number of no-signed-wrap deductions for sub");
79 STATISTIC(NumSubNUW, "Number of no-unsigned-wrap deductions for sub");
80 STATISTIC(NumMulNW, "Number of no-wrap deductions for mul");
81 STATISTIC(NumMulNSW, "Number of no-signed-wrap deductions for mul");
82 STATISTIC(NumMulNUW, "Number of no-unsigned-wrap deductions for mul");
83 STATISTIC(NumShlNW, "Number of no-wrap deductions for shl");
84 STATISTIC(NumShlNSW, "Number of no-signed-wrap deductions for shl");
85 STATISTIC(NumShlNUW, "Number of no-unsigned-wrap deductions for shl");
86 STATISTIC(NumAbs, "Number of llvm.abs intrinsics removed");
87 STATISTIC(NumOverflows, "Number of overflow checks removed");
88 STATISTIC(NumSaturating,
89  "Number of saturating arithmetics converted to normal arithmetics");
90 STATISTIC(NumNonNull, "Number of function pointer arguments marked non-null");
91 STATISTIC(NumMinMax, "Number of llvm.[us]{min,max} intrinsics removed");
92 
93 namespace {
94 
95  class CorrelatedValuePropagation : public FunctionPass {
96  public:
97  static char ID;
98 
99  CorrelatedValuePropagation(): FunctionPass(ID) {
101  }
102 
103  bool runOnFunction(Function &F) override;
104 
105  void getAnalysisUsage(AnalysisUsage &AU) const override {
111  }
112  };
113 
114 } // end anonymous namespace
115 
117 
118 INITIALIZE_PASS_BEGIN(CorrelatedValuePropagation, "correlated-propagation",
119  "Value Propagation", false, false)
122 INITIALIZE_PASS_END(CorrelatedValuePropagation, "correlated-propagation",
124 
125 // Public interface to the Value Propagation pass
127  return new CorrelatedValuePropagation();
128 }
129 
131  if (S->getType()->isVectorTy()) return false;
132  if (isa<Constant>(S->getCondition())) return false;
133 
134  Constant *C = LVI->getConstant(S->getCondition(), S);
135  if (!C) return false;
136 
137  ConstantInt *CI = dyn_cast<ConstantInt>(C);
138  if (!CI) return false;
139 
140  Value *ReplaceWith = CI->isOne() ? S->getTrueValue() : S->getFalseValue();
141  S->replaceAllUsesWith(ReplaceWith);
142  S->eraseFromParent();
143 
144  ++NumSelects;
145 
146  return true;
147 }
148 
149 /// Try to simplify a phi with constant incoming values that match the edge
150 /// values of a non-constant value on all other edges:
151 /// bb0:
152 /// %isnull = icmp eq i8* %x, null
153 /// br i1 %isnull, label %bb2, label %bb1
154 /// bb1:
155 /// br label %bb2
156 /// bb2:
157 /// %r = phi i8* [ %x, %bb1 ], [ null, %bb0 ]
158 /// -->
159 /// %r = %x
161  DominatorTree *DT) {
162  // Collect incoming constants and initialize possible common value.
163  SmallVector<std::pair<Constant *, unsigned>, 4> IncomingConstants;
164  Value *CommonValue = nullptr;
165  for (unsigned i = 0, e = P->getNumIncomingValues(); i != e; ++i) {
166  Value *Incoming = P->getIncomingValue(i);
167  if (auto *IncomingConstant = dyn_cast<Constant>(Incoming)) {
168  IncomingConstants.push_back(std::make_pair(IncomingConstant, i));
169  } else if (!CommonValue) {
170  // The potential common value is initialized to the first non-constant.
171  CommonValue = Incoming;
172  } else if (Incoming != CommonValue) {
173  // There can be only one non-constant common value.
174  return false;
175  }
176  }
177 
178  if (!CommonValue || IncomingConstants.empty())
179  return false;
180 
181  // The common value must be valid in all incoming blocks.
182  BasicBlock *ToBB = P->getParent();
183  if (auto *CommonInst = dyn_cast<Instruction>(CommonValue))
184  if (!DT->dominates(CommonInst, ToBB))
185  return false;
186 
187  // We have a phi with exactly 1 variable incoming value and 1 or more constant
188  // incoming values. See if all constant incoming values can be mapped back to
189  // the same incoming variable value.
190  for (auto &IncomingConstant : IncomingConstants) {
191  Constant *C = IncomingConstant.first;
192  BasicBlock *IncomingBB = P->getIncomingBlock(IncomingConstant.second);
193  if (C != LVI->getConstantOnEdge(CommonValue, IncomingBB, ToBB, P))
194  return false;
195  }
196 
197  // LVI only guarantees that the value matches a certain constant if the value
198  // is not poison. Make sure we don't replace a well-defined value with poison.
199  // This is usually satisfied due to a prior branch on the value.
200  if (!isGuaranteedNotToBePoison(CommonValue, nullptr, P, DT))
201  return false;
202 
203  // All constant incoming values map to the same variable along the incoming
204  // edges of the phi. The phi is unnecessary.
205  P->replaceAllUsesWith(CommonValue);
206  P->eraseFromParent();
207  ++NumPhiCommon;
208  return true;
209 }
210 
212  const SimplifyQuery &SQ) {
213  bool Changed = false;
214 
215  BasicBlock *BB = P->getParent();
216  for (unsigned i = 0, e = P->getNumIncomingValues(); i < e; ++i) {
217  Value *Incoming = P->getIncomingValue(i);
218  if (isa<Constant>(Incoming)) continue;
219 
220  Value *V = LVI->getConstantOnEdge(Incoming, P->getIncomingBlock(i), BB, P);
221 
222  // Look if the incoming value is a select with a scalar condition for which
223  // LVI can tells us the value. In that case replace the incoming value with
224  // the appropriate value of the select. This often allows us to remove the
225  // select later.
226  if (!V) {
227  SelectInst *SI = dyn_cast<SelectInst>(Incoming);
228  if (!SI) continue;
229 
230  Value *Condition = SI->getCondition();
231  if (!Condition->getType()->isVectorTy()) {
232  if (Constant *C = LVI->getConstantOnEdge(
233  Condition, P->getIncomingBlock(i), BB, P)) {
234  if (C->isOneValue()) {
235  V = SI->getTrueValue();
236  } else if (C->isZeroValue()) {
237  V = SI->getFalseValue();
238  }
239  // Once LVI learns to handle vector types, we could also add support
240  // for vector type constants that are not all zeroes or all ones.
241  }
242  }
243 
244  // Look if the select has a constant but LVI tells us that the incoming
245  // value can never be that constant. In that case replace the incoming
246  // value with the other value of the select. This often allows us to
247  // remove the select later.
248  if (!V) {
249  Constant *C = dyn_cast<Constant>(SI->getFalseValue());
250  if (!C) continue;
251 
253  P->getIncomingBlock(i), BB, P) !=
255  continue;
256  V = SI->getTrueValue();
257  }
258 
259  LLVM_DEBUG(dbgs() << "CVP: Threading PHI over " << *SI << '\n');
260  }
261 
262  P->setIncomingValue(i, V);
263  Changed = true;
264  }
265 
266  if (Value *V = SimplifyInstruction(P, SQ)) {
267  P->replaceAllUsesWith(V);
268  P->eraseFromParent();
269  Changed = true;
270  }
271 
272  if (!Changed)
273  Changed = simplifyCommonValuePhi(P, LVI, DT);
274 
275  if (Changed)
276  ++NumPhis;
277 
278  return Changed;
279 }
280 
282  Value *Pointer = nullptr;
283  if (LoadInst *L = dyn_cast<LoadInst>(I))
284  Pointer = L->getPointerOperand();
285  else
286  Pointer = cast<StoreInst>(I)->getPointerOperand();
287 
288  if (isa<Constant>(Pointer)) return false;
289 
290  Constant *C = LVI->getConstant(Pointer, I);
291  if (!C) return false;
292 
293  ++NumMemAccess;
294  I->replaceUsesOfWith(Pointer, C);
295  return true;
296 }
297 
298 /// See if LazyValueInfo's ability to exploit edge conditions or range
299 /// information is sufficient to prove this comparison. Even for local
300 /// conditions, this can sometimes prove conditions instcombine can't by
301 /// exploiting range information.
302 static bool processCmp(CmpInst *Cmp, LazyValueInfo *LVI) {
303  Value *Op0 = Cmp->getOperand(0);
304  auto *C = dyn_cast<Constant>(Cmp->getOperand(1));
305  if (!C)
306  return false;
307 
308  LazyValueInfo::Tristate Result =
309  LVI->getPredicateAt(Cmp->getPredicate(), Op0, C, Cmp,
310  /*UseBlockValue=*/true);
311  if (Result == LazyValueInfo::Unknown)
312  return false;
313 
314  ++NumCmps;
315  Constant *TorF = ConstantInt::get(Type::getInt1Ty(Cmp->getContext()), Result);
316  Cmp->replaceAllUsesWith(TorF);
317  Cmp->eraseFromParent();
318  return true;
319 }
320 
321 /// Simplify a switch instruction by removing cases which can never fire. If the
322 /// uselessness of a case could be determined locally then constant propagation
323 /// would already have figured it out. Instead, walk the predecessors and
324 /// statically evaluate cases based on information available on that edge. Cases
325 /// that cannot fire no matter what the incoming edge can safely be removed. If
326 /// a case fires on every incoming edge then the entire switch can be removed
327 /// and replaced with a branch to the case destination.
329  DominatorTree *DT) {
331  Value *Cond = I->getCondition();
332  BasicBlock *BB = I->getParent();
333 
334  // Analyse each switch case in turn.
335  bool Changed = false;
336  DenseMap<BasicBlock*, int> SuccessorsCount;
337  for (auto *Succ : successors(BB))
338  SuccessorsCount[Succ]++;
339 
340  { // Scope for SwitchInstProfUpdateWrapper. It must not live during
341  // ConstantFoldTerminator() as the underlying SwitchInst can be changed.
343 
344  for (auto CI = SI->case_begin(), CE = SI->case_end(); CI != CE;) {
345  ConstantInt *Case = CI->getCaseValue();
347  LVI->getPredicateAt(CmpInst::ICMP_EQ, Cond, Case, I,
348  /* UseBlockValue */ true);
349 
350  if (State == LazyValueInfo::False) {
351  // This case never fires - remove it.
352  BasicBlock *Succ = CI->getCaseSuccessor();
353  Succ->removePredecessor(BB);
354  CI = SI.removeCase(CI);
355  CE = SI->case_end();
356 
357  // The condition can be modified by removePredecessor's PHI simplification
358  // logic.
359  Cond = SI->getCondition();
360 
361  ++NumDeadCases;
362  Changed = true;
363  if (--SuccessorsCount[Succ] == 0)
365  continue;
366  }
367  if (State == LazyValueInfo::True) {
368  // This case always fires. Arrange for the switch to be turned into an
369  // unconditional branch by replacing the switch condition with the case
370  // value.
371  SI->setCondition(Case);
372  NumDeadCases += SI->getNumCases();
373  Changed = true;
374  break;
375  }
376 
377  // Increment the case iterator since we didn't delete it.
378  ++CI;
379  }
380  }
381 
382  if (Changed)
383  // If the switch has been simplified to the point where it can be replaced
384  // by a branch then do so now.
385  ConstantFoldTerminator(BB, /*DeleteDeadConditions = */ false,
386  /*TLI = */ nullptr, &DTU);
387  return Changed;
388 }
389 
390 // See if we can prove that the given binary op intrinsic will not overflow.
392  ConstantRange LRange = LVI->getConstantRange(BO->getLHS(), BO);
393  ConstantRange RRange = LVI->getConstantRange(BO->getRHS(), BO);
395  BO->getBinaryOp(), RRange, BO->getNoWrapKind());
396  return NWRegion.contains(LRange);
397 }
398 
400  bool NewNSW, bool NewNUW) {
401  Statistic *OpcNW, *OpcNSW, *OpcNUW;
402  switch (Opcode) {
403  case Instruction::Add:
404  OpcNW = &NumAddNW;
405  OpcNSW = &NumAddNSW;
406  OpcNUW = &NumAddNUW;
407  break;
408  case Instruction::Sub:
409  OpcNW = &NumSubNW;
410  OpcNSW = &NumSubNSW;
411  OpcNUW = &NumSubNUW;
412  break;
413  case Instruction::Mul:
414  OpcNW = &NumMulNW;
415  OpcNSW = &NumMulNSW;
416  OpcNUW = &NumMulNUW;
417  break;
418  case Instruction::Shl:
419  OpcNW = &NumShlNW;
420  OpcNSW = &NumShlNSW;
421  OpcNUW = &NumShlNUW;
422  break;
423  default:
424  llvm_unreachable("Will not be called with other binops");
425  }
426 
427  auto *Inst = dyn_cast<Instruction>(V);
428  if (NewNSW) {
429  ++NumNW;
430  ++*OpcNW;
431  ++NumNSW;
432  ++*OpcNSW;
433  if (Inst)
434  Inst->setHasNoSignedWrap();
435  }
436  if (NewNUW) {
437  ++NumNW;
438  ++*OpcNW;
439  ++NumNUW;
440  ++*OpcNUW;
441  if (Inst)
442  Inst->setHasNoUnsignedWrap();
443  }
444 }
445 
446 static bool processBinOp(BinaryOperator *BinOp, LazyValueInfo *LVI);
447 
448 // See if @llvm.abs argument is alays positive/negative, and simplify.
449 // Notably, INT_MIN can belong to either range, regardless of the NSW,
450 // because it is negation-invariant.
452  Value *X = II->getArgOperand(0);
453  bool IsIntMinPoison = cast<ConstantInt>(II->getArgOperand(1))->isOne();
454 
455  Type *Ty = X->getType();
456  Constant *IntMin =
459 
460  // Is X in [0, IntMin]? NOTE: INT_MIN is fine!
461  Result = LVI->getPredicateAt(CmpInst::Predicate::ICMP_ULE, X, IntMin, II,
462  /*UseBlockValue=*/true);
463  if (Result == LazyValueInfo::True) {
464  ++NumAbs;
465  II->replaceAllUsesWith(X);
466  II->eraseFromParent();
467  return true;
468  }
469 
470  // Is X in [IntMin, 0]? NOTE: INT_MIN is fine!
472  Result = LVI->getPredicateAt(CmpInst::Predicate::ICMP_SLE, X, Zero, II,
473  /*UseBlockValue=*/true);
474  assert(Result != LazyValueInfo::False && "Should have been handled already.");
475 
476  if (Result == LazyValueInfo::Unknown) {
477  // Argument's range crosses zero.
478  bool Changed = false;
479  if (!IsIntMinPoison) {
480  // Can we at least tell that the argument is never INT_MIN?
481  Result = LVI->getPredicateAt(CmpInst::Predicate::ICMP_NE, X, IntMin, II,
482  /*UseBlockValue=*/true);
483  if (Result == LazyValueInfo::True) {
484  ++NumNSW;
485  ++NumSubNSW;
487  Changed = true;
488  }
489  }
490  return Changed;
491  }
492 
493  IRBuilder<> B(II);
494  Value *NegX = B.CreateNeg(X, II->getName(), /*HasNUW=*/false,
495  /*HasNSW=*/IsIntMinPoison);
496  ++NumAbs;
497  II->replaceAllUsesWith(NegX);
498  II->eraseFromParent();
499 
500  // See if we can infer some no-wrap flags.
501  if (auto *BO = dyn_cast<BinaryOperator>(NegX))
502  processBinOp(BO, LVI);
503 
504  return true;
505 }
506 
507 // See if this min/max intrinsic always picks it's one specific operand.
511  Pred, MM->getLHS(), MM->getRHS(), MM, /*UseBlockValue=*/true);
512  if (Result == LazyValueInfo::Unknown)
513  return false;
514 
515  ++NumMinMax;
516  MM->replaceAllUsesWith(MM->getOperand(!Result));
517  MM->eraseFromParent();
518  return true;
519 }
520 
521 // Rewrite this with.overflow intrinsic as non-overflowing.
523  IRBuilder<> B(WO);
524  Instruction::BinaryOps Opcode = WO->getBinaryOp();
525  bool NSW = WO->isSigned();
526  bool NUW = !WO->isSigned();
527 
528  Value *NewOp =
529  B.CreateBinOp(Opcode, WO->getLHS(), WO->getRHS(), WO->getName());
530  setDeducedOverflowingFlags(NewOp, Opcode, NSW, NUW);
531 
532  StructType *ST = cast<StructType>(WO->getType());
533  Constant *Struct = ConstantStruct::get(ST,
534  { UndefValue::get(ST->getElementType(0)),
535  ConstantInt::getFalse(ST->getElementType(1)) });
536  Value *NewI = B.CreateInsertValue(Struct, NewOp, 0);
537  WO->replaceAllUsesWith(NewI);
538  WO->eraseFromParent();
539  ++NumOverflows;
540 
541  // See if we can infer the other no-wrap too.
542  if (auto *BO = dyn_cast<BinaryOperator>(NewOp))
543  processBinOp(BO, LVI);
544 
545  return true;
546 }
547 
549  Instruction::BinaryOps Opcode = SI->getBinaryOp();
550  bool NSW = SI->isSigned();
551  bool NUW = !SI->isSigned();
553  Opcode, SI->getLHS(), SI->getRHS(), SI->getName(), SI);
554  BinOp->setDebugLoc(SI->getDebugLoc());
555  setDeducedOverflowingFlags(BinOp, Opcode, NSW, NUW);
556 
557  SI->replaceAllUsesWith(BinOp);
558  SI->eraseFromParent();
559  ++NumSaturating;
560 
561  // See if we can infer the other no-wrap too.
562  if (auto *BO = dyn_cast<BinaryOperator>(BinOp))
563  processBinOp(BO, LVI);
564 
565  return true;
566 }
567 
568 /// Infer nonnull attributes for the arguments at the specified callsite.
569 static bool processCallSite(CallBase &CB, LazyValueInfo *LVI) {
570 
571  if (CB.getIntrinsicID() == Intrinsic::abs) {
572  return processAbsIntrinsic(&cast<IntrinsicInst>(CB), LVI);
573  }
574 
575  if (auto *MM = dyn_cast<MinMaxIntrinsic>(&CB)) {
576  return processMinMaxIntrinsic(MM, LVI);
577  }
578 
579  if (auto *WO = dyn_cast<WithOverflowInst>(&CB)) {
580  if (WO->getLHS()->getType()->isIntegerTy() && willNotOverflow(WO, LVI)) {
581  return processOverflowIntrinsic(WO, LVI);
582  }
583  }
584 
585  if (auto *SI = dyn_cast<SaturatingInst>(&CB)) {
586  if (SI->getType()->isIntegerTy() && willNotOverflow(SI, LVI)) {
587  return processSaturatingInst(SI, LVI);
588  }
589  }
590 
591  bool Changed = false;
592 
593  // Deopt bundle operands are intended to capture state with minimal
594  // perturbance of the code otherwise. If we can find a constant value for
595  // any such operand and remove a use of the original value, that's
596  // desireable since it may allow further optimization of that value (e.g. via
597  // single use rules in instcombine). Since deopt uses tend to,
598  // idiomatically, appear along rare conditional paths, it's reasonable likely
599  // we may have a conditional fact with which LVI can fold.
600  if (auto DeoptBundle = CB.getOperandBundle(LLVMContext::OB_deopt)) {
601  for (const Use &ConstU : DeoptBundle->Inputs) {
602  Use &U = const_cast<Use&>(ConstU);
603  Value *V = U.get();
604  if (V->getType()->isVectorTy()) continue;
605  if (isa<Constant>(V)) continue;
606 
607  Constant *C = LVI->getConstant(V, &CB);
608  if (!C) continue;
609  U.set(C);
610  Changed = true;
611  }
612  }
613 
615  unsigned ArgNo = 0;
616 
617  for (Value *V : CB.args()) {
618  PointerType *Type = dyn_cast<PointerType>(V->getType());
619  // Try to mark pointer typed parameters as non-null. We skip the
620  // relatively expensive analysis for constants which are obviously either
621  // null or non-null to start with.
622  if (Type && !CB.paramHasAttr(ArgNo, Attribute::NonNull) &&
623  !isa<Constant>(V) &&
626  /*UseBlockValue=*/false) == LazyValueInfo::False)
627  ArgNos.push_back(ArgNo);
628  ArgNo++;
629  }
630 
631  assert(ArgNo == CB.arg_size() && "sanity check");
632 
633  if (ArgNos.empty())
634  return Changed;
635 
636  NumNonNull += ArgNos.size();
637  AttributeList AS = CB.getAttributes();
638  LLVMContext &Ctx = CB.getContext();
639  AS = AS.addParamAttribute(Ctx, ArgNos,
640  Attribute::get(Ctx, Attribute::NonNull));
641  CB.setAttributes(AS);
642 
643  return true;
644 }
645 
646 static bool isNonNegative(Value *V, LazyValueInfo *LVI, Instruction *CxtI) {
647  Constant *Zero = ConstantInt::get(V->getType(), 0);
648  auto Result = LVI->getPredicateAt(ICmpInst::ICMP_SGE, V, Zero, CxtI,
649  /*UseBlockValue=*/true);
650  return Result == LazyValueInfo::True;
651 }
652 
653 static bool isNonPositive(Value *V, LazyValueInfo *LVI, Instruction *CxtI) {
654  Constant *Zero = ConstantInt::get(V->getType(), 0);
655  auto Result = LVI->getPredicateAt(ICmpInst::ICMP_SLE, V, Zero, CxtI,
656  /*UseBlockValue=*/true);
657  return Result == LazyValueInfo::True;
658 }
659 
660 enum class Domain { NonNegative, NonPositive, Unknown };
661 
663  if (isNonNegative(V, LVI, CxtI))
664  return Domain::NonNegative;
665  if (isNonPositive(V, LVI, CxtI))
666  return Domain::NonPositive;
667  return Domain::Unknown;
668 }
669 
670 /// Try to shrink a sdiv/srem's width down to the smallest power of two that's
671 /// sufficient to contain its operands.
672 static bool narrowSDivOrSRem(BinaryOperator *Instr, LazyValueInfo *LVI) {
673  assert(Instr->getOpcode() == Instruction::SDiv ||
674  Instr->getOpcode() == Instruction::SRem);
675  if (Instr->getType()->isVectorTy())
676  return false;
677 
678  // Find the smallest power of two bitwidth that's sufficient to hold Instr's
679  // operands.
680  unsigned OrigWidth = Instr->getType()->getIntegerBitWidth();
681 
682  // What is the smallest bit width that can accomodate the entire value ranges
683  // of both of the operands?
684  std::array<Optional<ConstantRange>, 2> CRs;
685  unsigned MinSignedBits = 0;
686  for (auto I : zip(Instr->operands(), CRs)) {
687  std::get<1>(I) = LVI->getConstantRange(std::get<0>(I), Instr);
688  MinSignedBits = std::max(std::get<1>(I)->getMinSignedBits(), MinSignedBits);
689  }
690 
691  // sdiv/srem is UB if divisor is -1 and divident is INT_MIN, so unless we can
692  // prove that such a combination is impossible, we need to bump the bitwidth.
693  if (CRs[1]->contains(APInt::getAllOnes(OrigWidth)) &&
694  CRs[0]->contains(
695  APInt::getSignedMinValue(MinSignedBits).sextOrSelf(OrigWidth)))
696  ++MinSignedBits;
697 
698  // Don't shrink below 8 bits wide.
699  unsigned NewWidth = std::max<unsigned>(PowerOf2Ceil(MinSignedBits), 8);
700 
701  // NewWidth might be greater than OrigWidth if OrigWidth is not a power of
702  // two.
703  if (NewWidth >= OrigWidth)
704  return false;
705 
706  ++NumSDivSRemsNarrowed;
707  IRBuilder<> B{Instr};
708  auto *TruncTy = Type::getIntNTy(Instr->getContext(), NewWidth);
709  auto *LHS = B.CreateTruncOrBitCast(Instr->getOperand(0), TruncTy,
710  Instr->getName() + ".lhs.trunc");
711  auto *RHS = B.CreateTruncOrBitCast(Instr->getOperand(1), TruncTy,
712  Instr->getName() + ".rhs.trunc");
713  auto *BO = B.CreateBinOp(Instr->getOpcode(), LHS, RHS, Instr->getName());
714  auto *Sext = B.CreateSExt(BO, Instr->getType(), Instr->getName() + ".sext");
715  if (auto *BinOp = dyn_cast<BinaryOperator>(BO))
716  if (BinOp->getOpcode() == Instruction::SDiv)
717  BinOp->setIsExact(Instr->isExact());
718 
719  Instr->replaceAllUsesWith(Sext);
720  Instr->eraseFromParent();
721  return true;
722 }
723 
724 /// Try to shrink a udiv/urem's width down to the smallest power of two that's
725 /// sufficient to contain its operands.
726 static bool processUDivOrURem(BinaryOperator *Instr, LazyValueInfo *LVI) {
727  assert(Instr->getOpcode() == Instruction::UDiv ||
728  Instr->getOpcode() == Instruction::URem);
729  if (Instr->getType()->isVectorTy())
730  return false;
731 
732  // Find the smallest power of two bitwidth that's sufficient to hold Instr's
733  // operands.
734 
735  // What is the smallest bit width that can accomodate the entire value ranges
736  // of both of the operands?
737  unsigned MaxActiveBits = 0;
738  for (Value *Operand : Instr->operands()) {
739  ConstantRange CR = LVI->getConstantRange(Operand, Instr);
740  MaxActiveBits = std::max(CR.getActiveBits(), MaxActiveBits);
741  }
742  // Don't shrink below 8 bits wide.
743  unsigned NewWidth = std::max<unsigned>(PowerOf2Ceil(MaxActiveBits), 8);
744 
745  // NewWidth might be greater than OrigWidth if OrigWidth is not a power of
746  // two.
747  if (NewWidth >= Instr->getType()->getIntegerBitWidth())
748  return false;
749 
750  ++NumUDivURemsNarrowed;
751  IRBuilder<> B{Instr};
752  auto *TruncTy = Type::getIntNTy(Instr->getContext(), NewWidth);
753  auto *LHS = B.CreateTruncOrBitCast(Instr->getOperand(0), TruncTy,
754  Instr->getName() + ".lhs.trunc");
755  auto *RHS = B.CreateTruncOrBitCast(Instr->getOperand(1), TruncTy,
756  Instr->getName() + ".rhs.trunc");
757  auto *BO = B.CreateBinOp(Instr->getOpcode(), LHS, RHS, Instr->getName());
758  auto *Zext = B.CreateZExt(BO, Instr->getType(), Instr->getName() + ".zext");
759  if (auto *BinOp = dyn_cast<BinaryOperator>(BO))
760  if (BinOp->getOpcode() == Instruction::UDiv)
761  BinOp->setIsExact(Instr->isExact());
762 
763  Instr->replaceAllUsesWith(Zext);
764  Instr->eraseFromParent();
765  return true;
766 }
767 
768 static bool processSRem(BinaryOperator *SDI, LazyValueInfo *LVI) {
769  assert(SDI->getOpcode() == Instruction::SRem);
770  if (SDI->getType()->isVectorTy())
771  return false;
772 
773  struct Operand {
774  Value *V;
775  Domain D;
776  };
777  std::array<Operand, 2> Ops;
778 
779  for (const auto I : zip(Ops, SDI->operands())) {
780  Operand &Op = std::get<0>(I);
781  Op.V = std::get<1>(I);
782  Op.D = getDomain(Op.V, LVI, SDI);
783  if (Op.D == Domain::Unknown)
784  return false;
785  }
786 
787  // We know domains of both of the operands!
788  ++NumSRems;
789 
790  // We need operands to be non-negative, so negate each one that isn't.
791  for (Operand &Op : Ops) {
792  if (Op.D == Domain::NonNegative)
793  continue;
794  auto *BO =
795  BinaryOperator::CreateNeg(Op.V, Op.V->getName() + ".nonneg", SDI);
796  BO->setDebugLoc(SDI->getDebugLoc());
797  Op.V = BO;
798  }
799 
800  auto *URem =
801  BinaryOperator::CreateURem(Ops[0].V, Ops[1].V, SDI->getName(), SDI);
802  URem->setDebugLoc(SDI->getDebugLoc());
803 
804  Value *Res = URem;
805 
806  // If the divident was non-positive, we need to negate the result.
807  if (Ops[0].D == Domain::NonPositive)
808  Res = BinaryOperator::CreateNeg(Res, Res->getName() + ".neg", SDI);
809 
810  SDI->replaceAllUsesWith(Res);
811  SDI->eraseFromParent();
812 
813  // Try to simplify our new urem.
814  processUDivOrURem(URem, LVI);
815 
816  return true;
817 }
818 
819 /// See if LazyValueInfo's ability to exploit edge conditions or range
820 /// information is sufficient to prove the signs of both operands of this SDiv.
821 /// If this is the case, replace the SDiv with a UDiv. Even for local
822 /// conditions, this can sometimes prove conditions instcombine can't by
823 /// exploiting range information.
824 static bool processSDiv(BinaryOperator *SDI, LazyValueInfo *LVI) {
825  assert(SDI->getOpcode() == Instruction::SDiv);
826  if (SDI->getType()->isVectorTy())
827  return false;
828 
829  struct Operand {
830  Value *V;
831  Domain D;
832  };
833  std::array<Operand, 2> Ops;
834 
835  for (const auto I : zip(Ops, SDI->operands())) {
836  Operand &Op = std::get<0>(I);
837  Op.V = std::get<1>(I);
838  Op.D = getDomain(Op.V, LVI, SDI);
839  if (Op.D == Domain::Unknown)
840  return false;
841  }
842 
843  // We know domains of both of the operands!
844  ++NumSDivs;
845 
846  // We need operands to be non-negative, so negate each one that isn't.
847  for (Operand &Op : Ops) {
848  if (Op.D == Domain::NonNegative)
849  continue;
850  auto *BO =
851  BinaryOperator::CreateNeg(Op.V, Op.V->getName() + ".nonneg", SDI);
852  BO->setDebugLoc(SDI->getDebugLoc());
853  Op.V = BO;
854  }
855 
856  auto *UDiv =
857  BinaryOperator::CreateUDiv(Ops[0].V, Ops[1].V, SDI->getName(), SDI);
858  UDiv->setDebugLoc(SDI->getDebugLoc());
859  UDiv->setIsExact(SDI->isExact());
860 
861  Value *Res = UDiv;
862 
863  // If the operands had two different domains, we need to negate the result.
864  if (Ops[0].D != Ops[1].D)
865  Res = BinaryOperator::CreateNeg(Res, Res->getName() + ".neg", SDI);
866 
867  SDI->replaceAllUsesWith(Res);
868  SDI->eraseFromParent();
869 
870  // Try to simplify our new udiv.
871  processUDivOrURem(UDiv, LVI);
872 
873  return true;
874 }
875 
876 static bool processSDivOrSRem(BinaryOperator *Instr, LazyValueInfo *LVI) {
877  assert(Instr->getOpcode() == Instruction::SDiv ||
878  Instr->getOpcode() == Instruction::SRem);
879  if (Instr->getType()->isVectorTy())
880  return false;
881 
882  if (Instr->getOpcode() == Instruction::SDiv)
883  if (processSDiv(Instr, LVI))
884  return true;
885 
886  if (Instr->getOpcode() == Instruction::SRem)
887  if (processSRem(Instr, LVI))
888  return true;
889 
890  return narrowSDivOrSRem(Instr, LVI);
891 }
892 
893 static bool processAShr(BinaryOperator *SDI, LazyValueInfo *LVI) {
894  if (SDI->getType()->isVectorTy())
895  return false;
896 
897  if (!isNonNegative(SDI->getOperand(0), LVI, SDI))
898  return false;
899 
900  ++NumAShrs;
901  auto *BO = BinaryOperator::CreateLShr(SDI->getOperand(0), SDI->getOperand(1),
902  SDI->getName(), SDI);
903  BO->setDebugLoc(SDI->getDebugLoc());
904  BO->setIsExact(SDI->isExact());
905  SDI->replaceAllUsesWith(BO);
906  SDI->eraseFromParent();
907 
908  return true;
909 }
910 
911 static bool processSExt(SExtInst *SDI, LazyValueInfo *LVI) {
912  if (SDI->getType()->isVectorTy())
913  return false;
914 
915  Value *Base = SDI->getOperand(0);
916 
917  if (!isNonNegative(Base, LVI, SDI))
918  return false;
919 
920  ++NumSExt;
921  auto *ZExt =
922  CastInst::CreateZExtOrBitCast(Base, SDI->getType(), SDI->getName(), SDI);
923  ZExt->setDebugLoc(SDI->getDebugLoc());
924  SDI->replaceAllUsesWith(ZExt);
925  SDI->eraseFromParent();
926 
927  return true;
928 }
929 
930 static bool processBinOp(BinaryOperator *BinOp, LazyValueInfo *LVI) {
931  using OBO = OverflowingBinaryOperator;
932 
933  if (BinOp->getType()->isVectorTy())
934  return false;
935 
936  bool NSW = BinOp->hasNoSignedWrap();
937  bool NUW = BinOp->hasNoUnsignedWrap();
938  if (NSW && NUW)
939  return false;
940 
941  Instruction::BinaryOps Opcode = BinOp->getOpcode();
942  Value *LHS = BinOp->getOperand(0);
943  Value *RHS = BinOp->getOperand(1);
944 
945  ConstantRange LRange = LVI->getConstantRange(LHS, BinOp);
946  ConstantRange RRange = LVI->getConstantRange(RHS, BinOp);
947 
948  bool Changed = false;
949  bool NewNUW = false, NewNSW = false;
950  if (!NUW) {
952  Opcode, RRange, OBO::NoUnsignedWrap);
953  NewNUW = NUWRange.contains(LRange);
954  Changed |= NewNUW;
955  }
956  if (!NSW) {
958  Opcode, RRange, OBO::NoSignedWrap);
959  NewNSW = NSWRange.contains(LRange);
960  Changed |= NewNSW;
961  }
962 
963  setDeducedOverflowingFlags(BinOp, Opcode, NewNSW, NewNUW);
964 
965  return Changed;
966 }
967 
968 static bool processAnd(BinaryOperator *BinOp, LazyValueInfo *LVI) {
969  if (BinOp->getType()->isVectorTy())
970  return false;
971 
972  // Pattern match (and lhs, C) where C includes a superset of bits which might
973  // be set in lhs. This is a common truncation idiom created by instcombine.
974  Value *LHS = BinOp->getOperand(0);
975  ConstantInt *RHS = dyn_cast<ConstantInt>(BinOp->getOperand(1));
976  if (!RHS || !RHS->getValue().isMask())
977  return false;
978 
979  // We can only replace the AND with LHS based on range info if the range does
980  // not include undef.
981  ConstantRange LRange =
982  LVI->getConstantRange(LHS, BinOp, /*UndefAllowed=*/false);
983  if (!LRange.getUnsignedMax().ule(RHS->getValue()))
984  return false;
985 
986  BinOp->replaceAllUsesWith(LHS);
987  BinOp->eraseFromParent();
988  NumAnd++;
989  return true;
990 }
991 
992 
994  if (Constant *C = LVI->getConstant(V, At))
995  return C;
996 
997  // TODO: The following really should be sunk inside LVI's core algorithm, or
998  // at least the outer shims around such.
999  auto *C = dyn_cast<CmpInst>(V);
1000  if (!C) return nullptr;
1001 
1002  Value *Op0 = C->getOperand(0);
1003  Constant *Op1 = dyn_cast<Constant>(C->getOperand(1));
1004  if (!Op1) return nullptr;
1005 
1007  C->getPredicate(), Op0, Op1, At, /*UseBlockValue=*/false);
1008  if (Result == LazyValueInfo::Unknown)
1009  return nullptr;
1010 
1011  return (Result == LazyValueInfo::True) ?
1012  ConstantInt::getTrue(C->getContext()) :
1013  ConstantInt::getFalse(C->getContext());
1014 }
1015 
1017  const SimplifyQuery &SQ) {
1018  bool FnChanged = false;
1019  // Visiting in a pre-order depth-first traversal causes us to simplify early
1020  // blocks before querying later blocks (which require us to analyze early
1021  // blocks). Eagerly simplifying shallow blocks means there is strictly less
1022  // work to do for deep blocks. This also means we don't visit unreachable
1023  // blocks.
1024  for (BasicBlock *BB : depth_first(&F.getEntryBlock())) {
1025  bool BBChanged = false;
1026  for (Instruction &II : llvm::make_early_inc_range(*BB)) {
1027  switch (II.getOpcode()) {
1028  case Instruction::Select:
1029  BBChanged |= processSelect(cast<SelectInst>(&II), LVI);
1030  break;
1031  case Instruction::PHI:
1032  BBChanged |= processPHI(cast<PHINode>(&II), LVI, DT, SQ);
1033  break;
1034  case Instruction::ICmp:
1035  case Instruction::FCmp:
1036  BBChanged |= processCmp(cast<CmpInst>(&II), LVI);
1037  break;
1038  case Instruction::Load:
1039  case Instruction::Store:
1040  BBChanged |= processMemAccess(&II, LVI);
1041  break;
1042  case Instruction::Call:
1043  case Instruction::Invoke:
1044  BBChanged |= processCallSite(cast<CallBase>(II), LVI);
1045  break;
1046  case Instruction::SRem:
1047  case Instruction::SDiv:
1048  BBChanged |= processSDivOrSRem(cast<BinaryOperator>(&II), LVI);
1049  break;
1050  case Instruction::UDiv:
1051  case Instruction::URem:
1052  BBChanged |= processUDivOrURem(cast<BinaryOperator>(&II), LVI);
1053  break;
1054  case Instruction::AShr:
1055  BBChanged |= processAShr(cast<BinaryOperator>(&II), LVI);
1056  break;
1057  case Instruction::SExt:
1058  BBChanged |= processSExt(cast<SExtInst>(&II), LVI);
1059  break;
1060  case Instruction::Add:
1061  case Instruction::Sub:
1062  case Instruction::Mul:
1063  case Instruction::Shl:
1064  BBChanged |= processBinOp(cast<BinaryOperator>(&II), LVI);
1065  break;
1066  case Instruction::And:
1067  BBChanged |= processAnd(cast<BinaryOperator>(&II), LVI);
1068  break;
1069  }
1070  }
1071 
1072  Instruction *Term = BB->getTerminator();
1073  switch (Term->getOpcode()) {
1074  case Instruction::Switch:
1075  BBChanged |= processSwitch(cast<SwitchInst>(Term), LVI, DT);
1076  break;
1077  case Instruction::Ret: {
1078  auto *RI = cast<ReturnInst>(Term);
1079  // Try to determine the return value if we can. This is mainly here to
1080  // simplify the writing of unit tests, but also helps to enable IPO by
1081  // constant folding the return values of callees.
1082  auto *RetVal = RI->getReturnValue();
1083  if (!RetVal) break; // handle "ret void"
1084  if (isa<Constant>(RetVal)) break; // nothing to do
1085  if (auto *C = getConstantAt(RetVal, RI, LVI)) {
1086  ++NumReturns;
1087  RI->replaceUsesOfWith(RetVal, C);
1088  BBChanged = true;
1089  }
1090  }
1091  }
1092 
1093  FnChanged |= BBChanged;
1094  }
1095 
1096  return FnChanged;
1097 }
1098 
1100  if (skipFunction(F))
1101  return false;
1102 
1103  LazyValueInfo *LVI = &getAnalysis<LazyValueInfoWrapperPass>().getLVI();
1104  DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1105 
1106  return runImpl(F, LVI, DT, getBestSimplifyQuery(*this, F));
1107 }
1108 
1113 
1114  bool Changed = runImpl(F, LVI, DT, getBestSimplifyQuery(AM, F));
1115 
1116  PreservedAnalyses PA;
1117  if (!Changed) {
1118  PA = PreservedAnalyses::all();
1119  } else {
1122  }
1123 
1124  // Keeping LVI alive is expensive, both because it uses a lot of memory, and
1125  // because invalidating values in LVI is expensive. While CVP does preserve
1126  // LVI, we know that passes after JumpThreading+CVP will not need the result
1127  // of this analysis, so we forcefully discard it early.
1128  PA.abandon<LazyValueAnalysis>();
1129  return PA;
1130 }
llvm::LazyValueInfo::getConstantOnEdge
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.
Definition: LazyValueInfo.cpp:1622
i
i
Definition: README.txt:29
narrowSDivOrSRem
static bool narrowSDivOrSRem(BinaryOperator *Instr, LazyValueInfo *LVI)
Try to shrink a sdiv/srem's width down to the smallest power of two that's sufficient to contain its ...
Definition: CorrelatedValuePropagation.cpp:672
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::BinaryOpIntrinsic::getBinaryOp
Instruction::BinaryOps getBinaryOp() const
Returns the binary operation underlying the intrinsic.
Definition: IntrinsicInst.cpp:558
processSelect
static bool processSelect(SelectInst *S, LazyValueInfo *LVI)
Definition: CorrelatedValuePropagation.cpp:130
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::Type::getInt1Ty
static IntegerType * getInt1Ty(LLVMContext &C)
Definition: Type.cpp:200
llvm::CmpInst::ICMP_EQ
@ ICMP_EQ
equal
Definition: InstrTypes.h:741
llvm::CallBase::getOperandBundle
Optional< OperandBundleUse > getOperandBundle(StringRef Name) const
Return an operand bundle by name, if present.
Definition: InstrTypes.h:1987
Optional.h
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:720
llvm::User::operands
op_range operands()
Definition: User.h:242
llvm::SwitchInstProfUpdateWrapper
A wrapper class to simplify modification of SwitchInst cases along with their prof branch_weights met...
Definition: Instructions.h:3558
IntrinsicInst.h
llvm::SimplifyQuery
Definition: InstructionSimplify.h:94
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:779
llvm::LazyValueInfo::getPredicateOnEdge
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 ...
Definition: LazyValueInfo.cpp:1727
Scalar.h
llvm::APInt::isMask
bool isMask(unsigned numBits) const
Definition: APInt.h:462
CorrelatedValuePropagation.h
llvm::Function
Definition: Function.h:61
llvm::APInt::ule
bool ule(const APInt &RHS) const
Unsigned less or equal comparison.
Definition: APInt.h:1075
llvm::ConstantStruct::get
static Constant * get(StructType *T, ArrayRef< Constant * > V)
Definition: Constants.cpp:1327
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
Pass.h
processAShr
static bool processAShr(BinaryOperator *SDI, LazyValueInfo *LVI)
Definition: CorrelatedValuePropagation.cpp:893
contains
return AArch64::GPR64RegClass contains(Reg)
llvm::Attribute::get
static Attribute get(LLVMContext &Context, AttrKind Kind, uint64_t Val=0)
Return a uniquified Attribute object.
Definition: Attributes.cpp:92
llvm::ConstantInt::getValue
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:133
llvm::BinaryOpIntrinsic::getRHS
Value * getRHS() const
Definition: IntrinsicInst.h:576
llvm::LazyValueAnalysis
Analysis to compute lazy value information.
Definition: LazyValueInfo.h:131
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
Statistic.h
llvm::AttributeList::addParamAttribute
LLVM_NODISCARD AttributeList addParamAttribute(LLVMContext &C, unsigned ArgNo, Attribute::AttrKind Kind) const
Add an argument attribute to the list.
Definition: Attributes.h:532
llvm::BinaryOpIntrinsic::getLHS
Value * getLHS() const
Definition: IntrinsicInst.h:575
processPHI
static bool processPHI(PHINode *P, LazyValueInfo *LVI, DominatorTree *DT, const SimplifyQuery &SQ)
Definition: CorrelatedValuePropagation.cpp:211
llvm::IRBuilder<>
llvm::Use::get
Value * get() const
Definition: Use.h:67
llvm::SPII::Store
@ Store
Definition: SparcInstrInfo.h:33
DomTreeUpdater.h
llvm::BinaryOpIntrinsic
This class represents an intrinsic that is based on a binary operation.
Definition: IntrinsicInst.h:552
llvm::Instruction::hasNoUnsignedWrap
bool hasNoUnsignedWrap() const
Determine whether the no unsigned wrap flag is set.
Definition: Instruction.cpp:136
ValueTracking.h
Local.h
llvm::PreservedAnalyses::abandon
void abandon()
Mark an analysis as abandoned.
Definition: PassManager.h:209
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
GlobalsModRef.h
processCallSite
static bool processCallSite(CallBase &CB, LazyValueInfo *LVI)
Infer nonnull attributes for the arguments at the specified callsite.
Definition: CorrelatedValuePropagation.cpp:569
llvm::LazyValueInfo::getConstant
Constant * getConstant(Value *V, Instruction *CxtI)
Determine whether the specified value is known to be a constant at the specified instruction.
Definition: LazyValueInfo.cpp:1583
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
llvm::AttributeList
Definition: Attributes.h:398
llvm::CallBase::getAttributes
AttributeList getAttributes() const
Return the parameter attributes for this call.
Definition: InstrTypes.h:1468
processAbsIntrinsic
static bool processAbsIntrinsic(IntrinsicInst *II, LazyValueInfo *LVI)
Definition: CorrelatedValuePropagation.cpp:451
Operator.h
llvm::initializeCorrelatedValuePropagationPass
void initializeCorrelatedValuePropagationPass(PassRegistry &)
llvm::CmpInst::ICMP_SLE
@ ICMP_SLE
signed less or equal
Definition: InstrTypes.h:750
LazyValueInfo.h
llvm::MipsISD::Ret
@ Ret
Definition: MipsISelLowering.h:116
llvm::PowerOf2Ceil
uint64_t PowerOf2Ceil(uint64_t A)
Returns the power of two which is greater than or equal to the given value.
Definition: MathExtras.h:702
llvm::BinaryOperator::CreateNeg
NUW NUW NUW NUW Exact static Exact BinaryOperator * CreateNeg(Value *Op, const Twine &Name="", Instruction *InsertBefore=nullptr)
Helper functions to construct and inspect unary operations (NEG and NOT) via binary operators SUB and...
Definition: Instructions.cpp:2690
llvm::successors
succ_range successors(Instruction *I)
Definition: CFG.h:262
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
DepthFirstIterator.h
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::DomTreeUpdater::UpdateStrategy::Lazy
@ Lazy
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
processUDivOrURem
static bool processUDivOrURem(BinaryOperator *Instr, LazyValueInfo *LVI)
Try to shrink a udiv/urem's width down to the smallest power of two that's sufficient to contain its ...
Definition: CorrelatedValuePropagation.cpp:726
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::DominatorTree::dominates
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:115
Instruction.h
CommandLine.h
propagation
correlated propagation
Definition: CorrelatedValuePropagation.cpp:122
processSDiv
static bool processSDiv(BinaryOperator *SDI, LazyValueInfo *LVI)
See if LazyValueInfo's ability to exploit edge conditions or range information is sufficient to prove...
Definition: CorrelatedValuePropagation.cpp:824
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
Constants.h
llvm::LazyValueInfo::Unknown
@ Unknown
Definition: LazyValueInfo.h:61
llvm::CmpInst::getNonStrictPredicate
Predicate getNonStrictPredicate() const
For example, SGT -> SGE, SLT -> SLE, ULT -> ULE, UGT -> UGE.
Definition: InstrTypes.h:880
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
InstrTypes.h
llvm::CallBase::setAttributes
void setAttributes(AttributeList A)
Set the parameter attributes for this call.
Definition: InstrTypes.h:1472
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
Domain
Domain
Definition: CorrelatedValuePropagation.cpp:660
llvm::APInt::getAllOnes
static APInt getAllOnes(unsigned numBits)
Return an APInt of a specified width with all bits set.
Definition: APInt.h:216
llvm::Type::isVectorTy
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:237
llvm::BinaryOpIntrinsic::getNoWrapKind
unsigned getNoWrapKind() const
Returns one of OBO::NoSignedWrap or OBO::NoUnsignedWrap.
Definition: IntrinsicInst.cpp:591
false
Definition: StackSlotColoring.cpp:142
llvm::LazyValueInfo::True
@ True
Definition: LazyValueInfo.h:61
setDeducedOverflowingFlags
static void setDeducedOverflowingFlags(Value *V, Instruction::BinaryOps Opcode, bool NewNSW, bool NewNUW)
Definition: CorrelatedValuePropagation.cpp:399
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::ConstantRange::makeGuaranteedNoWrapRegion
static ConstantRange makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp, const ConstantRange &Other, unsigned NoWrapKind)
Produce the largest range containing all X such that "X BinOp Y" is guaranteed not to wrap (overflow)...
Definition: ConstantRange.cpp:231
llvm::SaturatingInst
Represents a saturating add/sub intrinsic.
Definition: IntrinsicInst.h:610
llvm::BinaryOperator::getOpcode
BinaryOps getOpcode() const
Definition: InstrTypes.h:393
runImpl
static bool runImpl(Function &F, LazyValueInfo *LVI, DominatorTree *DT, const SimplifyQuery &SQ)
Definition: CorrelatedValuePropagation.cpp:1016
llvm::Instruction
Definition: Instruction.h:45
llvm::Type::getScalarSizeInBits
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
Definition: Type.cpp:153
llvm::ConstantRange::getUnsignedMax
APInt getUnsignedMax() const
Return the largest unsigned value contained in the ConstantRange.
Definition: ConstantRange.cpp:369
llvm::SimplifyInstruction
Value * SimplifyInstruction(Instruction *I, const SimplifyQuery &Q, OptimizationRemarkEmitter *ORE=nullptr)
See if we can compute a simplified version of this instruction.
Definition: InstructionSimplify.cpp:6293
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:287
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1771
llvm::DomTreeUpdater
Definition: DomTreeUpdater.h:28
llvm::ConstantInt::get
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:900
llvm::CorrelatedValuePropagationPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: CorrelatedValuePropagation.cpp:1110
willNotOverflow
static bool willNotOverflow(BinaryOpIntrinsic *BO, LazyValueInfo *LVI)
Definition: CorrelatedValuePropagation.cpp:391
llvm::MCID::Call
@ Call
Definition: MCInstrDesc.h:153
processMinMaxIntrinsic
static bool processMinMaxIntrinsic(MinMaxIntrinsic *MM, LazyValueInfo *LVI)
Definition: CorrelatedValuePropagation.cpp:508
llvm::Type::getIntegerBitWidth
unsigned getIntegerBitWidth() const
Definition: DerivedTypes.h:97
llvm::M68kBeads::Term
@ Term
Definition: M68kBaseInfo.h:71
Type.h
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
getConstantAt
static Constant * getConstantAt(Value *V, Instruction *At, LazyValueInfo *LVI)
Definition: CorrelatedValuePropagation.cpp:993
getDomain
Domain getDomain(Value *V, LazyValueInfo *LVI, Instruction *CxtI)
Definition: CorrelatedValuePropagation.cpp:662
CFG.h
llvm::CmpInst
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:710
llvm::Use::set
void set(Value *Val)
Definition: Value.h:864
BasicBlock.h
llvm::LLVMContext::OB_deopt
@ OB_deopt
Definition: LLVMContext.h:90
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:78
processSwitch
static bool processSwitch(SwitchInst *I, LazyValueInfo *LVI, DominatorTree *DT)
Simplify a switch instruction by removing cases which can never fire.
Definition: CorrelatedValuePropagation.cpp:328
llvm::BinaryOpIntrinsic::isSigned
bool isSigned() const
Whether the intrinsic is signed or unsigned.
Definition: IntrinsicInst.cpp:578
D
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
llvm::LazyValueInfo::getConstantRange
ConstantRange getConstantRange(Value *V, Instruction *CxtI, bool UndefAllowed=true)
Return the ConstantRange constraint that is known to hold for the specified value at the specified in...
Definition: LazyValueInfo.cpp:1602
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(CorrelatedValuePropagation, "correlated-propagation", "Value Propagation", false, false) INITIALIZE_PASS_END(CorrelatedValuePropagation
llvm::ARM_MB::ST
@ ST
Definition: ARMBaseInfo.h:73
processOverflowIntrinsic
static bool processOverflowIntrinsic(WithOverflowInst *WO, LazyValueInfo *LVI)
Definition: CorrelatedValuePropagation.cpp:522
llvm::LazyValueInfoWrapperPass
Wrapper around LazyValueInfo.
Definition: LazyValueInfo.h:142
llvm::PreservedAnalyses::preserve
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:176
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::ConstantPointerNull::get
static ConstantPointerNull * get(PointerType *T)
Static factory methods - Return objects of the specified value.
Definition: Constants.cpp:1757
processBinOp
static bool processBinOp(BinaryOperator *BinOp, LazyValueInfo *LVI)
Definition: CorrelatedValuePropagation.cpp:930
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:68
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
Domain::Unknown
@ Unknown
llvm::DenseMap
Definition: DenseMap.h:714
I
#define I(x, y, z)
Definition: MD5.cpp:59
processMemAccess
static bool processMemAccess(Instruction *I, LazyValueInfo *LVI)
Definition: CorrelatedValuePropagation.cpp:281
llvm::make_early_inc_range
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:576
llvm::PointerType
Class to represent pointers.
Definition: DerivedTypes.h:632
Propagation
correlated Value Propagation
Definition: CorrelatedValuePropagation.cpp:123
llvm::Instruction::setDebugLoc
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:367
llvm::createCorrelatedValuePropagationPass
Pass * createCorrelatedValuePropagationPass()
Definition: CorrelatedValuePropagation.cpp:126
IRBuilder.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1738
llvm::MinMaxIntrinsic::getPredicate
ICmpInst::Predicate getPredicate() const
Returns the comparison predicate underlying the intrinsic.
Definition: IntrinsicInst.h:531
llvm::LazyValueInfo
This pass computes, caches, and vends lazy value constraint information.
Definition: LazyValueInfo.h:31
llvm::zip
detail::zippy< detail::zip_shortest, T, U, Args... > zip(T &&t, U &&u, Args &&... args)
zip iterator for two or more iteratable types.
Definition: STLExtras.h:736
llvm::MinMaxIntrinsic::getLHS
Value * getLHS() const
Definition: IntrinsicInst.h:527
processSExt
static bool processSExt(SExtInst *SDI, LazyValueInfo *LVI)
Definition: CorrelatedValuePropagation.cpp:911
llvm::CallBase::getIntrinsicID
Intrinsic::ID getIntrinsicID() const
Returns the intrinsic ID of the intrinsic called or Intrinsic::not_intrinsic if the called function i...
Definition: Instructions.cpp:311
llvm::BinaryOperator
Definition: InstrTypes.h:189
processSRem
static bool processSRem(BinaryOperator *SDI, LazyValueInfo *LVI)
Definition: CorrelatedValuePropagation.cpp:768
llvm::StructType
Class to represent struct types.
Definition: DerivedTypes.h:213
processCmp
static bool processCmp(CmpInst *Cmp, LazyValueInfo *LVI)
See if LazyValueInfo's ability to exploit edge conditions or range information is sufficient to prove...
Definition: CorrelatedValuePropagation.cpp:302
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:179
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:136
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
processSDivOrSRem
static bool processSDivOrSRem(BinaryOperator *Instr, LazyValueInfo *LVI)
Definition: CorrelatedValuePropagation.cpp:876
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
llvm::Value::replaceAllUsesWith
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:532
llvm::Value::getContext
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:990
ConstantRange.h
llvm::Instruction::isExact
bool isExact() const
Determine whether the exact flag is set.
Definition: Instruction.cpp:186
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::OverflowingBinaryOperator
Utility class for integer operators which may exhibit overflow - Add, Sub, Mul, and Shl.
Definition: Operator.h:67
llvm::WithOverflowInst
Represents an op.with.overflow intrinsic.
Definition: IntrinsicInst.h:589
llvm::TrackingStatistic
Definition: Statistic.h:49
llvm::SExtInst
This class represents a sign extension of integer types.
Definition: Instructions.h:4833
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:175
llvm::CallBase::paramHasAttr
bool paramHasAttr(unsigned ArgNo, Attribute::AttrKind Kind) const
Determine whether the argument or parameter has the given attribute.
Definition: Instructions.cpp:341
llvm::SPII::Load
@ Load
Definition: SparcInstrInfo.h:32
llvm::CallBase::setArgOperand
void setArgOperand(unsigned i, Value *v)
Definition: InstrTypes.h:1343
llvm::ConstantInt::getFalse
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:855
llvm::depth_first
iterator_range< df_iterator< T > > depth_first(const T &G)
Definition: DepthFirstIterator.h:229
llvm::MCID::Select
@ Select
Definition: MCInstrDesc.h:162
Attributes.h
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
Constant.h
llvm::ConstantFoldTerminator
bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions=false, const TargetLibraryInfo *TLI=nullptr, DomTreeUpdater *DTU=nullptr)
If a terminator instruction is predicated on a constant value, convert it into an unconditional branc...
Definition: Local.cpp:128
llvm::ConstantInt::getTrue
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:848
llvm::Constant::getNullValue
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Definition: Constants.cpp:348
llvm::getBestSimplifyQuery
const SimplifyQuery getBestSimplifyQuery(Pass &, Function &)
Definition: InstructionSimplify.cpp:6382
llvm::Type::getIntNTy
static IntegerType * getIntNTy(LLVMContext &C, unsigned N)
Definition: Type.cpp:207
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:321
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
llvm::CallBase::arg_size
unsigned arg_size() const
Definition: InstrTypes.h:1326
Casting.h
Function.h
Domain::NonPositive
@ NonPositive
isNonPositive
static bool isNonPositive(Value *V, LazyValueInfo *LVI, Instruction *CxtI)
Definition: CorrelatedValuePropagation.cpp:653
PassManager.h
llvm::ConstantRange::getActiveBits
unsigned getActiveBits() const
Compute the maximal number of active bits needed to represent every value in this range.
Definition: ConstantRange.cpp:420
llvm::ConstantRange::contains
bool contains(const APInt &Val) const
Return true if the specified value is in the set.
Definition: ConstantRange.cpp:393
llvm::CmpInst::ICMP_SGE
@ ICMP_SGE
signed greater or equal
Definition: InstrTypes.h:748
llvm::MCID::Add
@ Add
Definition: MCInstrDesc.h:183
llvm::APInt::getSignedMinValue
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
Definition: APInt.h:201
llvm::ConstantRange
This class represents a range of values.
Definition: ConstantRange.h:47
processSaturatingInst
static bool processSaturatingInst(SaturatingInst *SI, LazyValueInfo *LVI)
Definition: CorrelatedValuePropagation.cpp:548
llvm::IntrinsicInst
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:45
llvm::Instruction::BinaryOps
BinaryOps
Definition: Instruction.h:785
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:252
llvm::Pass
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:91
Instructions.h
llvm::MinMaxIntrinsic
This class represents min/max intrinsics.
Definition: IntrinsicInst.h:510
SmallVector.h
llvm::LazyValueInfo::Tristate
Tristate
This is used to return true/false/dunno results.
Definition: LazyValueInfo.h:60
llvm::Instruction::getDebugLoc
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:370
processAnd
static bool processAnd(BinaryOperator *BinOp, LazyValueInfo *LVI)
Definition: CorrelatedValuePropagation.cpp:968
llvm::Instruction::hasNoSignedWrap
bool hasNoSignedWrap() const
Determine whether the no signed wrap flag is set.
Definition: Instruction.cpp:140
llvm::CallBase::getArgOperand
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1338
InstructionSimplify.h
llvm::GlobalsAAWrapperPass
Legacy wrapper pass to provide the GlobalsAAResult object.
Definition: GlobalsModRef.h:143
llvm::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:340
llvm::PHINode
Definition: Instructions.h:2633
llvm::BasicBlock::removePredecessor
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
Definition: BasicBlock.cpp:321
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1161
DerivedTypes.h
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
llvm::ConstantInt::isOne
bool isOne() const
This is just a convenience method to make client code smaller for a common case.
Definition: Constants.h:200
llvm::isGuaranteedNotToBePoison
bool isGuaranteedNotToBePoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Definition: ValueTracking.cpp:5270
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::SwitchInst
Multiway switch.
Definition: Instructions.h:3212
llvm::LazyValueInfo::False
@ False
Definition: LazyValueInfo.h:61
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
llvm::CastInst::CreateZExtOrBitCast
static CastInst * CreateZExtOrBitCast(Value *S, Type *Ty, const Twine &Name="", Instruction *InsertBefore=nullptr)
Create a ZExt or BitCast cast instruction.
Definition: Instructions.cpp:3120
raw_ostream.h
llvm::LazyValueInfo::getPredicateAt
Tristate getPredicateAt(unsigned Pred, Value *V, Constant *C, Instruction *CxtI, bool UseBlockValue)
Determine whether the specified value comparison with a constant is known to be true or false at the ...
Definition: LazyValueInfo.cpp:1738
llvm::BinaryOperator::Create
static BinaryOperator * Create(BinaryOps Op, Value *S1, Value *S2, const Twine &Name=Twine(), Instruction *InsertBefore=nullptr)
Construct a binary instruction, given the opcode and the two operands.
Definition: Instructions.cpp:2674
Value.h
llvm::abs
APFloat abs(APFloat X)
Returns the absolute value of the argument.
Definition: APFloat.h:1284
Domain::NonNegative
@ NonNegative
InitializePasses.h
llvm::DomTreeUpdater::applyUpdatesPermissive
void applyUpdatesPermissive(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
Definition: DomTreeUpdater.cpp:249
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
isNonNegative
static bool isNonNegative(Value *V, LazyValueInfo *LVI, Instruction *CxtI)
Definition: CorrelatedValuePropagation.cpp:646
Debug.h
llvm::CallBase::args
iterator_range< User::op_iterator > args()
Iteration adapter for range-for loops.
Definition: InstrTypes.h:1319
llvm::MinMaxIntrinsic::getRHS
Value * getRHS() const
Definition: IntrinsicInst.h:528
llvm::DominatorTreeBase< BasicBlock, false >::Delete
static constexpr UpdateKind Delete
Definition: GenericDomTree.h:243
llvm::sampleprof::Base
@ Base
Definition: Discriminator.h:58
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37
simplifyCommonValuePhi
static bool simplifyCommonValuePhi(PHINode *P, LazyValueInfo *LVI, DominatorTree *DT)
Try to simplify a phi with constant incoming values that match the edge values of a non-constant valu...
Definition: CorrelatedValuePropagation.cpp:160