LLVM  13.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"
22 #include "llvm/IR/Attributes.h"
23 #include "llvm/IR/BasicBlock.h"
24 #include "llvm/IR/CFG.h"
25 #include "llvm/IR/Constant.h"
26 #include "llvm/IR/ConstantRange.h"
27 #include "llvm/IR/Constants.h"
28 #include "llvm/IR/DerivedTypes.h"
29 #include "llvm/IR/Function.h"
30 #include "llvm/IR/IRBuilder.h"
31 #include "llvm/IR/InstrTypes.h"
32 #include "llvm/IR/Instruction.h"
33 #include "llvm/IR/Instructions.h"
34 #include "llvm/IR/IntrinsicInst.h"
35 #include "llvm/IR/Operator.h"
36 #include "llvm/IR/PassManager.h"
37 #include "llvm/IR/Type.h"
38 #include "llvm/IR/Value.h"
39 #include "llvm/InitializePasses.h"
40 #include "llvm/Pass.h"
41 #include "llvm/Support/Casting.h"
43 #include "llvm/Support/Debug.h"
45 #include "llvm/Transforms/Scalar.h"
47 #include <cassert>
48 #include <utility>
49 
50 using namespace llvm;
51 
52 #define DEBUG_TYPE "correlated-value-propagation"
53 
54 STATISTIC(NumPhis, "Number of phis propagated");
55 STATISTIC(NumPhiCommon, "Number of phis deleted via common incoming value");
56 STATISTIC(NumSelects, "Number of selects propagated");
57 STATISTIC(NumMemAccess, "Number of memory access targets propagated");
58 STATISTIC(NumCmps, "Number of comparisons propagated");
59 STATISTIC(NumReturns, "Number of return values propagated");
60 STATISTIC(NumDeadCases, "Number of switch cases removed");
61 STATISTIC(NumSDivSRemsNarrowed,
62  "Number of sdivs/srems whose width was decreased");
63 STATISTIC(NumSDivs, "Number of sdiv converted to udiv");
64 STATISTIC(NumUDivURemsNarrowed,
65  "Number of udivs/urems whose width was decreased");
66 STATISTIC(NumAShrs, "Number of ashr converted to lshr");
67 STATISTIC(NumSRems, "Number of srem converted to urem");
68 STATISTIC(NumSExt, "Number of sext converted to zext");
69 STATISTIC(NumAnd, "Number of ands removed");
70 STATISTIC(NumNW, "Number of no-wrap deductions");
71 STATISTIC(NumNSW, "Number of no-signed-wrap deductions");
72 STATISTIC(NumNUW, "Number of no-unsigned-wrap deductions");
73 STATISTIC(NumAddNW, "Number of no-wrap deductions for add");
74 STATISTIC(NumAddNSW, "Number of no-signed-wrap deductions for add");
75 STATISTIC(NumAddNUW, "Number of no-unsigned-wrap deductions for add");
76 STATISTIC(NumSubNW, "Number of no-wrap deductions for sub");
77 STATISTIC(NumSubNSW, "Number of no-signed-wrap deductions for sub");
78 STATISTIC(NumSubNUW, "Number of no-unsigned-wrap deductions for sub");
79 STATISTIC(NumMulNW, "Number of no-wrap deductions for mul");
80 STATISTIC(NumMulNSW, "Number of no-signed-wrap deductions for mul");
81 STATISTIC(NumMulNUW, "Number of no-unsigned-wrap deductions for mul");
82 STATISTIC(NumShlNW, "Number of no-wrap deductions for shl");
83 STATISTIC(NumShlNSW, "Number of no-signed-wrap deductions for shl");
84 STATISTIC(NumShlNUW, "Number of no-unsigned-wrap deductions for shl");
85 STATISTIC(NumAbs, "Number of llvm.abs intrinsics removed");
86 STATISTIC(NumOverflows, "Number of overflow checks removed");
87 STATISTIC(NumSaturating,
88  "Number of saturating arithmetics converted to normal arithmetics");
89 STATISTIC(NumNonNull, "Number of function pointer arguments marked non-null");
90 STATISTIC(NumMinMax, "Number of llvm.[us]{min,max} intrinsics removed");
91 
92 namespace {
93 
94  class CorrelatedValuePropagation : public FunctionPass {
95  public:
96  static char ID;
97 
98  CorrelatedValuePropagation(): FunctionPass(ID) {
100  }
101 
102  bool runOnFunction(Function &F) override;
103 
104  void getAnalysisUsage(AnalysisUsage &AU) const override {
110  }
111  };
112 
113 } // end anonymous namespace
114 
116 
117 INITIALIZE_PASS_BEGIN(CorrelatedValuePropagation, "correlated-propagation",
118  "Value Propagation", false, false)
121 INITIALIZE_PASS_END(CorrelatedValuePropagation, "correlated-propagation",
123 
124 // Public interface to the Value Propagation pass
126  return new CorrelatedValuePropagation();
127 }
128 
130  if (S->getType()->isVectorTy()) return false;
131  if (isa<Constant>(S->getCondition())) return false;
132 
133  Constant *C = LVI->getConstant(S->getCondition(), S);
134  if (!C) return false;
135 
136  ConstantInt *CI = dyn_cast<ConstantInt>(C);
137  if (!CI) return false;
138 
139  Value *ReplaceWith = CI->isOne() ? S->getTrueValue() : S->getFalseValue();
140  S->replaceAllUsesWith(ReplaceWith);
141  S->eraseFromParent();
142 
143  ++NumSelects;
144 
145  return true;
146 }
147 
148 /// Try to simplify a phi with constant incoming values that match the edge
149 /// values of a non-constant value on all other edges:
150 /// bb0:
151 /// %isnull = icmp eq i8* %x, null
152 /// br i1 %isnull, label %bb2, label %bb1
153 /// bb1:
154 /// br label %bb2
155 /// bb2:
156 /// %r = phi i8* [ %x, %bb1 ], [ null, %bb0 ]
157 /// -->
158 /// %r = %x
160  DominatorTree *DT) {
161  // Collect incoming constants and initialize possible common value.
162  SmallVector<std::pair<Constant *, unsigned>, 4> IncomingConstants;
163  Value *CommonValue = nullptr;
164  for (unsigned i = 0, e = P->getNumIncomingValues(); i != e; ++i) {
165  Value *Incoming = P->getIncomingValue(i);
166  if (auto *IncomingConstant = dyn_cast<Constant>(Incoming)) {
167  IncomingConstants.push_back(std::make_pair(IncomingConstant, i));
168  } else if (!CommonValue) {
169  // The potential common value is initialized to the first non-constant.
170  CommonValue = Incoming;
171  } else if (Incoming != CommonValue) {
172  // There can be only one non-constant common value.
173  return false;
174  }
175  }
176 
177  if (!CommonValue || IncomingConstants.empty())
178  return false;
179 
180  // The common value must be valid in all incoming blocks.
181  BasicBlock *ToBB = P->getParent();
182  if (auto *CommonInst = dyn_cast<Instruction>(CommonValue))
183  if (!DT->dominates(CommonInst, ToBB))
184  return false;
185 
186  // We have a phi with exactly 1 variable incoming value and 1 or more constant
187  // incoming values. See if all constant incoming values can be mapped back to
188  // the same incoming variable value.
189  for (auto &IncomingConstant : IncomingConstants) {
190  Constant *C = IncomingConstant.first;
191  BasicBlock *IncomingBB = P->getIncomingBlock(IncomingConstant.second);
192  if (C != LVI->getConstantOnEdge(CommonValue, IncomingBB, ToBB, P))
193  return false;
194  }
195 
196  // All constant incoming values map to the same variable along the incoming
197  // edges of the phi. The phi is unnecessary. However, we must drop all
198  // poison-generating flags to ensure that no poison is propagated to the phi
199  // location by performing this substitution.
200  // Warning: If the underlying analysis changes, this may not be enough to
201  // guarantee that poison is not propagated.
202  // TODO: We may be able to re-infer flags by re-analyzing the instruction.
203  if (auto *CommonInst = dyn_cast<Instruction>(CommonValue))
204  CommonInst->dropPoisonGeneratingFlags();
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::getAllOnesValue(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 (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) {
1027  Instruction *II = &*BI++;
1028  switch (II->getOpcode()) {
1029  case Instruction::Select:
1030  BBChanged |= processSelect(cast<SelectInst>(II), LVI);
1031  break;
1032  case Instruction::PHI:
1033  BBChanged |= processPHI(cast<PHINode>(II), LVI, DT, SQ);
1034  break;
1035  case Instruction::ICmp:
1036  case Instruction::FCmp:
1037  BBChanged |= processCmp(cast<CmpInst>(II), LVI);
1038  break;
1039  case Instruction::Load:
1040  case Instruction::Store:
1041  BBChanged |= processMemAccess(II, LVI);
1042  break;
1043  case Instruction::Call:
1044  case Instruction::Invoke:
1045  BBChanged |= processCallSite(cast<CallBase>(*II), LVI);
1046  break;
1047  case Instruction::SRem:
1048  case Instruction::SDiv:
1049  BBChanged |= processSDivOrSRem(cast<BinaryOperator>(II), LVI);
1050  break;
1051  case Instruction::UDiv:
1052  case Instruction::URem:
1053  BBChanged |= processUDivOrURem(cast<BinaryOperator>(II), LVI);
1054  break;
1055  case Instruction::AShr:
1056  BBChanged |= processAShr(cast<BinaryOperator>(II), LVI);
1057  break;
1058  case Instruction::SExt:
1059  BBChanged |= processSExt(cast<SExtInst>(II), LVI);
1060  break;
1061  case Instruction::Add:
1062  case Instruction::Sub:
1063  case Instruction::Mul:
1064  case Instruction::Shl:
1065  BBChanged |= processBinOp(cast<BinaryOperator>(II), LVI);
1066  break;
1067  case Instruction::And:
1068  BBChanged |= processAnd(cast<BinaryOperator>(II), LVI);
1069  break;
1070  }
1071  }
1072 
1073  Instruction *Term = BB->getTerminator();
1074  switch (Term->getOpcode()) {
1075  case Instruction::Switch:
1076  BBChanged |= processSwitch(cast<SwitchInst>(Term), LVI, DT);
1077  break;
1078  case Instruction::Ret: {
1079  auto *RI = cast<ReturnInst>(Term);
1080  // Try to determine the return value if we can. This is mainly here to
1081  // simplify the writing of unit tests, but also helps to enable IPO by
1082  // constant folding the return values of callees.
1083  auto *RetVal = RI->getReturnValue();
1084  if (!RetVal) break; // handle "ret void"
1085  if (isa<Constant>(RetVal)) break; // nothing to do
1086  if (auto *C = getConstantAt(RetVal, RI, LVI)) {
1087  ++NumReturns;
1088  RI->replaceUsesOfWith(RetVal, C);
1089  BBChanged = true;
1090  }
1091  }
1092  }
1093 
1094  FnChanged |= BBChanged;
1095  }
1096 
1097  return FnChanged;
1098 }
1099 
1101  if (skipFunction(F))
1102  return false;
1103 
1104  LazyValueInfo *LVI = &getAnalysis<LazyValueInfoWrapperPass>().getLVI();
1105  DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1106 
1107  return runImpl(F, LVI, DT, getBestSimplifyQuery(*this, F));
1108 }
1109 
1114 
1115  bool Changed = runImpl(F, LVI, DT, getBestSimplifyQuery(AM, F));
1116 
1117  PreservedAnalyses PA;
1118  if (!Changed) {
1119  PA = PreservedAnalyses::all();
1120  } else {
1121  PA.preserve<GlobalsAA>();
1124  }
1125 
1126  // Keeping LVI alive is expensive, both because it uses a lot of memory, and
1127  // because invalidating values in LVI is expensive. While CVP does preserve
1128  // LVI, we know that passes after JumpThreading+CVP will not need the result
1129  // of this analysis, so we forcefully discard it early.
1130  PA.abandon<LazyValueAnalysis>();
1131  return PA;
1132 }
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:1603
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::GlobalsAA
Analysis pass providing a never-invalidated alias analysis result.
Definition: GlobalsModRef.h:132
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:387
processSelect
static bool processSelect(SelectInst *S, LazyValueInfo *LVI)
Definition: CorrelatedValuePropagation.cpp:129
llvm
Definition: AllocatorList.h:23
llvm::Type::getInt1Ty
static IntegerType * getInt1Ty(LLVMContext &C)
Definition: Type.cpp:194
llvm::M68kBeads::Term
@ Term
Definition: M68kBaseInfo.h:71
llvm::CmpInst::ICMP_EQ
@ ICMP_EQ
equal
Definition: InstrTypes.h:743
llvm::CallBase::getOperandBundle
Optional< OperandBundleUse > getOperandBundle(StringRef Name) const
Return an operand bundle by name, if present.
Definition: InstrTypes.h:1967
Optional.h
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:722
llvm::User::operands
op_range operands()
Definition: User.h:242
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:90
llvm::SwitchInstProfUpdateWrapper
A wrapper class to simplify modification of SwitchInst cases along with their prof branch_weights met...
Definition: Instructions.h:3497
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:769
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:1708
Scalar.h
llvm::APInt::isMask
bool isMask(unsigned numBits) const
Definition: APInt.h:500
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:1243
llvm::ConstantStruct::get
static Constant * get(StructType *T, ArrayRef< Constant * > V)
Definition: Constants.cpp:1326
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:131
llvm::BinaryOpIntrinsic::getRHS
Value * getRHS() const
Definition: IntrinsicInst.h:530
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:467
llvm::BinaryOpIntrinsic::getLHS
Value * getLHS() const
Definition: IntrinsicInst.h:529
processPHI
static bool processPHI(PHINode *P, LazyValueInfo *LVI, DominatorTree *DT, const SimplifyQuery &SQ)
Definition: CorrelatedValuePropagation.cpp:211
llvm::SPII::Load
@ Load
Definition: SparcInstrInfo.h:32
llvm::IRBuilder<>
llvm::Use::get
Value * get() const
Definition: Use.h:67
DomTreeUpdater.h
llvm::BinaryOpIntrinsic
This class represents an intrinsic that is based on a binary operation.
Definition: IntrinsicInst.h:506
llvm::Instruction::hasNoUnsignedWrap
bool hasNoUnsignedWrap() const
Determine whether the no unsigned wrap flag is set.
Definition: Instruction.cpp:132
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:1564
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:46
llvm::AttributeList
Definition: Attributes.h:385
llvm::CallBase::getAttributes
AttributeList getAttributes() const
Return the parameter attributes for this call.
Definition: InstrTypes.h:1472
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:752
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:2562
llvm::successors
succ_range successors(Instruction *I)
Definition: CFG.h:262
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:122
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:132
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:121
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:77
llvm::Instruction::getOpcode
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:160
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:883
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:1476
SI
@ SI
Definition: SIInstrInfo.cpp:7475
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
Domain
Domain
Definition: CorrelatedValuePropagation.cpp:660
llvm::Type::isVectorTy
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:235
llvm::BinaryOpIntrinsic::getNoWrapKind
unsigned getNoWrapKind() const
Returns one of OBO::NoSignedWrap or OBO::NoUnsignedWrap.
Definition: IntrinsicInst.cpp:420
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:564
llvm::BinaryOperator::getOpcode
BinaryOps getOpcode() const
Definition: InstrTypes.h:395
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:147
llvm::ConstantRange::getUnsignedMax
APInt getUnsignedMax() const
Return the largest unsigned value contained in the ConstantRange.
Definition: ConstantRange.cpp:370
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:5816
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:281
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:1784
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:899
llvm::CorrelatedValuePropagationPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: CorrelatedValuePropagation.cpp:1111
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:96
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:712
llvm::Use::set
void set(Value *Val)
Definition: Value.h:872
BasicBlock.h
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:407
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:1583
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:1770
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::PointerType
Class to represent pointers.
Definition: DerivedTypes.h:634
Propagation
correlated Value Propagation
Definition: CorrelatedValuePropagation.cpp:122
llvm::Instruction::setDebugLoc
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:362
llvm::createCorrelatedValuePropagationPass
Pass * createCorrelatedValuePropagationPass()
Definition: CorrelatedValuePropagation.cpp:125
IRBuilder.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1715
llvm::MinMaxIntrinsic::getPredicate
ICmpInst::Predicate getPredicate() const
Returns the comparison predicate underlying the intrinsic.
Definition: IntrinsicInst.h:485
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:719
llvm::MinMaxIntrinsic::getLHS
Value * getLHS() const
Definition: IntrinsicInst.h:481
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:307
llvm::BinaryOperator
Definition: InstrTypes.h:190
processSRem
static bool processSRem(BinaryOperator *SDI, LazyValueInfo *LVI)
Definition: CorrelatedValuePropagation.cpp:768
llvm::APInt::getAllOnesValue
static APInt getAllOnesValue(unsigned numBits)
Get the all-ones value.
Definition: APInt.h:567
llvm::StructType
Class to represent struct types.
Definition: DerivedTypes.h:212
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:167
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:527
llvm::Value::getContext
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:952
ConstantRange.h
llvm::Instruction::isExact
bool isExact() const
Determine whether the exact flag is set.
Definition: Instruction.cpp:165
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:66
llvm::WithOverflowInst
Represents an op.with.overflow intrinsic.
Definition: IntrinsicInst.h:543
llvm::TrackingStatistic
Definition: Statistic.h:49
llvm::LLVMContext::OB_deopt
@ OB_deopt
Definition: LLVMContext.h:90
llvm::SExtInst
This class represents a sign extension of integer types.
Definition: Instructions.h:4771
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:299
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:174
llvm::CallBase::paramHasAttr
bool paramHasAttr(unsigned ArgNo, Attribute::AttrKind Kind) const
Determine whether the argument or parameter has the given attribute.
Definition: Instructions.cpp:339
llvm::CallBase::setArgOperand
void setArgOperand(unsigned i, Value *v)
Definition: InstrTypes.h:1346
llvm::SPII::Store
@ Store
Definition: SparcInstrInfo.h:33
llvm::ConstantInt::getFalse
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:854
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:847
llvm::Constant::getNullValue
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Definition: Constants.cpp:347
llvm::getBestSimplifyQuery
const SimplifyQuery getBestSimplifyQuery(Pass &, Function &)
Definition: InstructionSimplify.cpp:6060
llvm::Type::getIntNTy
static IntegerType * getIntNTy(LLVMContext &C, unsigned N)
Definition: Type.cpp:201
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:314
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:1329
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:421
llvm::ConstantRange::contains
bool contains(const APInt &Val) const
Return true if the specified value is in the set.
Definition: ConstantRange.cpp:394
llvm::CmpInst::ICMP_SGE
@ ICMP_SGE
signed greater or equal
Definition: InstrTypes.h:750
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:550
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:768
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:464
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:365
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:136
llvm::CallBase::getArgOperand
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1341
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:2572
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:1164
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:198
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:3151
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:2986
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:1719
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:2546
Value.h
llvm::abs
APFloat abs(APFloat X)
Returns the absolute value of the argument.
Definition: APFloat.h:1272
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:1322
llvm::MinMaxIntrinsic::getRHS
Value * getRHS() const
Definition: IntrinsicInst.h:482
llvm::DominatorTreeBase< BasicBlock, false >::Delete
static constexpr UpdateKind Delete
Definition: GenericDomTree.h:243
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:38
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:159