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  APInt Low =
345  APInt::getSignedMaxValue(Cond->getType()->getScalarSizeInBits());
346  APInt High =
347  APInt::getSignedMinValue(Cond->getType()->getScalarSizeInBits());
348 
349  SwitchInst::CaseIt CI = SI->case_begin();
350  for (auto CE = SI->case_end(); CI != CE;) {
351  ConstantInt *Case = CI->getCaseValue();
353  LVI->getPredicateAt(CmpInst::ICMP_EQ, Cond, Case, I,
354  /* UseBlockValue */ true);
355 
356  if (State == LazyValueInfo::False) {
357  // This case never fires - remove it.
358  BasicBlock *Succ = CI->getCaseSuccessor();
359  Succ->removePredecessor(BB);
360  CI = SI.removeCase(CI);
361  CE = SI->case_end();
362 
363  // The condition can be modified by removePredecessor's PHI simplification
364  // logic.
365  Cond = SI->getCondition();
366 
367  ++NumDeadCases;
368  Changed = true;
369  if (--SuccessorsCount[Succ] == 0)
371  continue;
372  }
373  if (State == LazyValueInfo::True) {
374  // This case always fires. Arrange for the switch to be turned into an
375  // unconditional branch by replacing the switch condition with the case
376  // value.
377  SI->setCondition(Case);
378  NumDeadCases += SI->getNumCases();
379  Changed = true;
380  break;
381  }
382 
383  // Get Lower/Upper bound from switch cases.
384  Low = APIntOps::smin(Case->getValue(), Low);
385  High = APIntOps::smax(Case->getValue(), High);
386 
387  // Increment the case iterator since we didn't delete it.
388  ++CI;
389  }
390 
391  // Try to simplify default case as unreachable
392  if (CI == SI->case_end() && SI->getNumCases() != 0 &&
393  !isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg())) {
394  const ConstantRange SIRange =
395  LVI->getConstantRange(SI->getCondition(), SI);
396 
397  // If the numbered switch cases cover the entire range of the condition,
398  // then the default case is not reachable.
399  if (SIRange.getSignedMin() == Low && SIRange.getSignedMax() == High &&
400  SI->getNumCases() == High - Low + 1) {
402  Changed = true;
403  }
404  }
405  }
406 
407  if (Changed)
408  // If the switch has been simplified to the point where it can be replaced
409  // by a branch then do so now.
410  ConstantFoldTerminator(BB, /*DeleteDeadConditions = */ false,
411  /*TLI = */ nullptr, &DTU);
412  return Changed;
413 }
414 
415 // See if we can prove that the given binary op intrinsic will not overflow.
417  ConstantRange LRange = LVI->getConstantRange(BO->getLHS(), BO);
418  ConstantRange RRange = LVI->getConstantRange(BO->getRHS(), BO);
420  BO->getBinaryOp(), RRange, BO->getNoWrapKind());
421  return NWRegion.contains(LRange);
422 }
423 
425  bool NewNSW, bool NewNUW) {
426  Statistic *OpcNW, *OpcNSW, *OpcNUW;
427  switch (Opcode) {
428  case Instruction::Add:
429  OpcNW = &NumAddNW;
430  OpcNSW = &NumAddNSW;
431  OpcNUW = &NumAddNUW;
432  break;
433  case Instruction::Sub:
434  OpcNW = &NumSubNW;
435  OpcNSW = &NumSubNSW;
436  OpcNUW = &NumSubNUW;
437  break;
438  case Instruction::Mul:
439  OpcNW = &NumMulNW;
440  OpcNSW = &NumMulNSW;
441  OpcNUW = &NumMulNUW;
442  break;
443  case Instruction::Shl:
444  OpcNW = &NumShlNW;
445  OpcNSW = &NumShlNSW;
446  OpcNUW = &NumShlNUW;
447  break;
448  default:
449  llvm_unreachable("Will not be called with other binops");
450  }
451 
452  auto *Inst = dyn_cast<Instruction>(V);
453  if (NewNSW) {
454  ++NumNW;
455  ++*OpcNW;
456  ++NumNSW;
457  ++*OpcNSW;
458  if (Inst)
459  Inst->setHasNoSignedWrap();
460  }
461  if (NewNUW) {
462  ++NumNW;
463  ++*OpcNW;
464  ++NumNUW;
465  ++*OpcNUW;
466  if (Inst)
467  Inst->setHasNoUnsignedWrap();
468  }
469 }
470 
471 static bool processBinOp(BinaryOperator *BinOp, LazyValueInfo *LVI);
472 
473 // See if @llvm.abs argument is alays positive/negative, and simplify.
474 // Notably, INT_MIN can belong to either range, regardless of the NSW,
475 // because it is negation-invariant.
477  Value *X = II->getArgOperand(0);
478  bool IsIntMinPoison = cast<ConstantInt>(II->getArgOperand(1))->isOne();
479 
480  Type *Ty = X->getType();
481  Constant *IntMin =
484 
485  // Is X in [0, IntMin]? NOTE: INT_MIN is fine!
486  Result = LVI->getPredicateAt(CmpInst::Predicate::ICMP_ULE, X, IntMin, II,
487  /*UseBlockValue=*/true);
488  if (Result == LazyValueInfo::True) {
489  ++NumAbs;
490  II->replaceAllUsesWith(X);
491  II->eraseFromParent();
492  return true;
493  }
494 
495  // Is X in [IntMin, 0]? NOTE: INT_MIN is fine!
497  Result = LVI->getPredicateAt(CmpInst::Predicate::ICMP_SLE, X, Zero, II,
498  /*UseBlockValue=*/true);
499  assert(Result != LazyValueInfo::False && "Should have been handled already.");
500 
501  if (Result == LazyValueInfo::Unknown) {
502  // Argument's range crosses zero.
503  bool Changed = false;
504  if (!IsIntMinPoison) {
505  // Can we at least tell that the argument is never INT_MIN?
506  Result = LVI->getPredicateAt(CmpInst::Predicate::ICMP_NE, X, IntMin, II,
507  /*UseBlockValue=*/true);
508  if (Result == LazyValueInfo::True) {
509  ++NumNSW;
510  ++NumSubNSW;
512  Changed = true;
513  }
514  }
515  return Changed;
516  }
517 
518  IRBuilder<> B(II);
519  Value *NegX = B.CreateNeg(X, II->getName(), /*HasNUW=*/false,
520  /*HasNSW=*/IsIntMinPoison);
521  ++NumAbs;
522  II->replaceAllUsesWith(NegX);
523  II->eraseFromParent();
524 
525  // See if we can infer some no-wrap flags.
526  if (auto *BO = dyn_cast<BinaryOperator>(NegX))
527  processBinOp(BO, LVI);
528 
529  return true;
530 }
531 
532 // See if this min/max intrinsic always picks it's one specific operand.
536  Pred, MM->getLHS(), MM->getRHS(), MM, /*UseBlockValue=*/true);
537  if (Result == LazyValueInfo::Unknown)
538  return false;
539 
540  ++NumMinMax;
541  MM->replaceAllUsesWith(MM->getOperand(!Result));
542  MM->eraseFromParent();
543  return true;
544 }
545 
546 // Rewrite this with.overflow intrinsic as non-overflowing.
548  IRBuilder<> B(WO);
549  Instruction::BinaryOps Opcode = WO->getBinaryOp();
550  bool NSW = WO->isSigned();
551  bool NUW = !WO->isSigned();
552 
553  Value *NewOp =
554  B.CreateBinOp(Opcode, WO->getLHS(), WO->getRHS(), WO->getName());
555  setDeducedOverflowingFlags(NewOp, Opcode, NSW, NUW);
556 
557  StructType *ST = cast<StructType>(WO->getType());
558  Constant *Struct = ConstantStruct::get(ST,
559  { UndefValue::get(ST->getElementType(0)),
560  ConstantInt::getFalse(ST->getElementType(1)) });
561  Value *NewI = B.CreateInsertValue(Struct, NewOp, 0);
562  WO->replaceAllUsesWith(NewI);
563  WO->eraseFromParent();
564  ++NumOverflows;
565 
566  // See if we can infer the other no-wrap too.
567  if (auto *BO = dyn_cast<BinaryOperator>(NewOp))
568  processBinOp(BO, LVI);
569 
570  return true;
571 }
572 
574  Instruction::BinaryOps Opcode = SI->getBinaryOp();
575  bool NSW = SI->isSigned();
576  bool NUW = !SI->isSigned();
578  Opcode, SI->getLHS(), SI->getRHS(), SI->getName(), SI);
579  BinOp->setDebugLoc(SI->getDebugLoc());
580  setDeducedOverflowingFlags(BinOp, Opcode, NSW, NUW);
581 
582  SI->replaceAllUsesWith(BinOp);
583  SI->eraseFromParent();
584  ++NumSaturating;
585 
586  // See if we can infer the other no-wrap too.
587  if (auto *BO = dyn_cast<BinaryOperator>(BinOp))
588  processBinOp(BO, LVI);
589 
590  return true;
591 }
592 
593 /// Infer nonnull attributes for the arguments at the specified callsite.
594 static bool processCallSite(CallBase &CB, LazyValueInfo *LVI) {
595 
596  if (CB.getIntrinsicID() == Intrinsic::abs) {
597  return processAbsIntrinsic(&cast<IntrinsicInst>(CB), LVI);
598  }
599 
600  if (auto *MM = dyn_cast<MinMaxIntrinsic>(&CB)) {
601  return processMinMaxIntrinsic(MM, LVI);
602  }
603 
604  if (auto *WO = dyn_cast<WithOverflowInst>(&CB)) {
605  if (WO->getLHS()->getType()->isIntegerTy() && willNotOverflow(WO, LVI)) {
606  return processOverflowIntrinsic(WO, LVI);
607  }
608  }
609 
610  if (auto *SI = dyn_cast<SaturatingInst>(&CB)) {
611  if (SI->getType()->isIntegerTy() && willNotOverflow(SI, LVI)) {
612  return processSaturatingInst(SI, LVI);
613  }
614  }
615 
616  bool Changed = false;
617 
618  // Deopt bundle operands are intended to capture state with minimal
619  // perturbance of the code otherwise. If we can find a constant value for
620  // any such operand and remove a use of the original value, that's
621  // desireable since it may allow further optimization of that value (e.g. via
622  // single use rules in instcombine). Since deopt uses tend to,
623  // idiomatically, appear along rare conditional paths, it's reasonable likely
624  // we may have a conditional fact with which LVI can fold.
625  if (auto DeoptBundle = CB.getOperandBundle(LLVMContext::OB_deopt)) {
626  for (const Use &ConstU : DeoptBundle->Inputs) {
627  Use &U = const_cast<Use&>(ConstU);
628  Value *V = U.get();
629  if (V->getType()->isVectorTy()) continue;
630  if (isa<Constant>(V)) continue;
631 
632  Constant *C = LVI->getConstant(V, &CB);
633  if (!C) continue;
634  U.set(C);
635  Changed = true;
636  }
637  }
638 
640  unsigned ArgNo = 0;
641 
642  for (Value *V : CB.args()) {
643  PointerType *Type = dyn_cast<PointerType>(V->getType());
644  // Try to mark pointer typed parameters as non-null. We skip the
645  // relatively expensive analysis for constants which are obviously either
646  // null or non-null to start with.
647  if (Type && !CB.paramHasAttr(ArgNo, Attribute::NonNull) &&
648  !isa<Constant>(V) &&
651  /*UseBlockValue=*/false) == LazyValueInfo::False)
652  ArgNos.push_back(ArgNo);
653  ArgNo++;
654  }
655 
656  assert(ArgNo == CB.arg_size() && "sanity check");
657 
658  if (ArgNos.empty())
659  return Changed;
660 
661  NumNonNull += ArgNos.size();
662  AttributeList AS = CB.getAttributes();
663  LLVMContext &Ctx = CB.getContext();
664  AS = AS.addParamAttribute(Ctx, ArgNos,
665  Attribute::get(Ctx, Attribute::NonNull));
666  CB.setAttributes(AS);
667 
668  return true;
669 }
670 
671 static bool isNonNegative(Value *V, LazyValueInfo *LVI, Instruction *CxtI) {
672  Constant *Zero = ConstantInt::get(V->getType(), 0);
673  auto Result = LVI->getPredicateAt(ICmpInst::ICMP_SGE, V, Zero, CxtI,
674  /*UseBlockValue=*/true);
675  return Result == LazyValueInfo::True;
676 }
677 
678 static bool isNonPositive(Value *V, LazyValueInfo *LVI, Instruction *CxtI) {
679  Constant *Zero = ConstantInt::get(V->getType(), 0);
680  auto Result = LVI->getPredicateAt(ICmpInst::ICMP_SLE, V, Zero, CxtI,
681  /*UseBlockValue=*/true);
682  return Result == LazyValueInfo::True;
683 }
684 
685 enum class Domain { NonNegative, NonPositive, Unknown };
686 
688  if (isNonNegative(V, LVI, CxtI))
689  return Domain::NonNegative;
690  if (isNonPositive(V, LVI, CxtI))
691  return Domain::NonPositive;
692  return Domain::Unknown;
693 }
694 
695 /// Try to shrink a sdiv/srem's width down to the smallest power of two that's
696 /// sufficient to contain its operands.
697 static bool narrowSDivOrSRem(BinaryOperator *Instr, LazyValueInfo *LVI) {
698  assert(Instr->getOpcode() == Instruction::SDiv ||
699  Instr->getOpcode() == Instruction::SRem);
700  if (Instr->getType()->isVectorTy())
701  return false;
702 
703  // Find the smallest power of two bitwidth that's sufficient to hold Instr's
704  // operands.
705  unsigned OrigWidth = Instr->getType()->getIntegerBitWidth();
706 
707  // What is the smallest bit width that can accomodate the entire value ranges
708  // of both of the operands?
709  std::array<Optional<ConstantRange>, 2> CRs;
710  unsigned MinSignedBits = 0;
711  for (auto I : zip(Instr->operands(), CRs)) {
712  std::get<1>(I) = LVI->getConstantRange(std::get<0>(I), Instr);
713  MinSignedBits = std::max(std::get<1>(I)->getMinSignedBits(), MinSignedBits);
714  }
715 
716  // sdiv/srem is UB if divisor is -1 and divident is INT_MIN, so unless we can
717  // prove that such a combination is impossible, we need to bump the bitwidth.
718  if (CRs[1]->contains(APInt::getAllOnes(OrigWidth)) &&
719  CRs[0]->contains(
720  APInt::getSignedMinValue(MinSignedBits).sextOrSelf(OrigWidth)))
721  ++MinSignedBits;
722 
723  // Don't shrink below 8 bits wide.
724  unsigned NewWidth = std::max<unsigned>(PowerOf2Ceil(MinSignedBits), 8);
725 
726  // NewWidth might be greater than OrigWidth if OrigWidth is not a power of
727  // two.
728  if (NewWidth >= OrigWidth)
729  return false;
730 
731  ++NumSDivSRemsNarrowed;
732  IRBuilder<> B{Instr};
733  auto *TruncTy = Type::getIntNTy(Instr->getContext(), NewWidth);
734  auto *LHS = B.CreateTruncOrBitCast(Instr->getOperand(0), TruncTy,
735  Instr->getName() + ".lhs.trunc");
736  auto *RHS = B.CreateTruncOrBitCast(Instr->getOperand(1), TruncTy,
737  Instr->getName() + ".rhs.trunc");
738  auto *BO = B.CreateBinOp(Instr->getOpcode(), LHS, RHS, Instr->getName());
739  auto *Sext = B.CreateSExt(BO, Instr->getType(), Instr->getName() + ".sext");
740  if (auto *BinOp = dyn_cast<BinaryOperator>(BO))
741  if (BinOp->getOpcode() == Instruction::SDiv)
742  BinOp->setIsExact(Instr->isExact());
743 
744  Instr->replaceAllUsesWith(Sext);
745  Instr->eraseFromParent();
746  return true;
747 }
748 
749 /// Try to shrink a udiv/urem's width down to the smallest power of two that's
750 /// sufficient to contain its operands.
751 static bool processUDivOrURem(BinaryOperator *Instr, LazyValueInfo *LVI) {
752  assert(Instr->getOpcode() == Instruction::UDiv ||
753  Instr->getOpcode() == Instruction::URem);
754  if (Instr->getType()->isVectorTy())
755  return false;
756 
757  // Find the smallest power of two bitwidth that's sufficient to hold Instr's
758  // operands.
759 
760  // What is the smallest bit width that can accomodate the entire value ranges
761  // of both of the operands?
762  unsigned MaxActiveBits = 0;
763  for (Value *Operand : Instr->operands()) {
764  ConstantRange CR = LVI->getConstantRange(Operand, Instr);
765  MaxActiveBits = std::max(CR.getActiveBits(), MaxActiveBits);
766  }
767  // Don't shrink below 8 bits wide.
768  unsigned NewWidth = std::max<unsigned>(PowerOf2Ceil(MaxActiveBits), 8);
769 
770  // NewWidth might be greater than OrigWidth if OrigWidth is not a power of
771  // two.
772  if (NewWidth >= Instr->getType()->getIntegerBitWidth())
773  return false;
774 
775  ++NumUDivURemsNarrowed;
776  IRBuilder<> B{Instr};
777  auto *TruncTy = Type::getIntNTy(Instr->getContext(), NewWidth);
778  auto *LHS = B.CreateTruncOrBitCast(Instr->getOperand(0), TruncTy,
779  Instr->getName() + ".lhs.trunc");
780  auto *RHS = B.CreateTruncOrBitCast(Instr->getOperand(1), TruncTy,
781  Instr->getName() + ".rhs.trunc");
782  auto *BO = B.CreateBinOp(Instr->getOpcode(), LHS, RHS, Instr->getName());
783  auto *Zext = B.CreateZExt(BO, Instr->getType(), Instr->getName() + ".zext");
784  if (auto *BinOp = dyn_cast<BinaryOperator>(BO))
785  if (BinOp->getOpcode() == Instruction::UDiv)
786  BinOp->setIsExact(Instr->isExact());
787 
788  Instr->replaceAllUsesWith(Zext);
789  Instr->eraseFromParent();
790  return true;
791 }
792 
793 static bool processSRem(BinaryOperator *SDI, LazyValueInfo *LVI) {
794  assert(SDI->getOpcode() == Instruction::SRem);
795  if (SDI->getType()->isVectorTy())
796  return false;
797 
798  struct Operand {
799  Value *V;
800  Domain D;
801  };
802  std::array<Operand, 2> Ops;
803 
804  for (const auto I : zip(Ops, SDI->operands())) {
805  Operand &Op = std::get<0>(I);
806  Op.V = std::get<1>(I);
807  Op.D = getDomain(Op.V, LVI, SDI);
808  if (Op.D == Domain::Unknown)
809  return false;
810  }
811 
812  // We know domains of both of the operands!
813  ++NumSRems;
814 
815  // We need operands to be non-negative, so negate each one that isn't.
816  for (Operand &Op : Ops) {
817  if (Op.D == Domain::NonNegative)
818  continue;
819  auto *BO =
820  BinaryOperator::CreateNeg(Op.V, Op.V->getName() + ".nonneg", SDI);
821  BO->setDebugLoc(SDI->getDebugLoc());
822  Op.V = BO;
823  }
824 
825  auto *URem =
826  BinaryOperator::CreateURem(Ops[0].V, Ops[1].V, SDI->getName(), SDI);
827  URem->setDebugLoc(SDI->getDebugLoc());
828 
829  Value *Res = URem;
830 
831  // If the divident was non-positive, we need to negate the result.
832  if (Ops[0].D == Domain::NonPositive)
833  Res = BinaryOperator::CreateNeg(Res, Res->getName() + ".neg", SDI);
834 
835  SDI->replaceAllUsesWith(Res);
836  SDI->eraseFromParent();
837 
838  // Try to simplify our new urem.
839  processUDivOrURem(URem, LVI);
840 
841  return true;
842 }
843 
844 /// See if LazyValueInfo's ability to exploit edge conditions or range
845 /// information is sufficient to prove the signs of both operands of this SDiv.
846 /// If this is the case, replace the SDiv with a UDiv. Even for local
847 /// conditions, this can sometimes prove conditions instcombine can't by
848 /// exploiting range information.
849 static bool processSDiv(BinaryOperator *SDI, LazyValueInfo *LVI) {
850  assert(SDI->getOpcode() == Instruction::SDiv);
851  if (SDI->getType()->isVectorTy())
852  return false;
853 
854  struct Operand {
855  Value *V;
856  Domain D;
857  };
858  std::array<Operand, 2> Ops;
859 
860  for (const auto I : zip(Ops, SDI->operands())) {
861  Operand &Op = std::get<0>(I);
862  Op.V = std::get<1>(I);
863  Op.D = getDomain(Op.V, LVI, SDI);
864  if (Op.D == Domain::Unknown)
865  return false;
866  }
867 
868  // We know domains of both of the operands!
869  ++NumSDivs;
870 
871  // We need operands to be non-negative, so negate each one that isn't.
872  for (Operand &Op : Ops) {
873  if (Op.D == Domain::NonNegative)
874  continue;
875  auto *BO =
876  BinaryOperator::CreateNeg(Op.V, Op.V->getName() + ".nonneg", SDI);
877  BO->setDebugLoc(SDI->getDebugLoc());
878  Op.V = BO;
879  }
880 
881  auto *UDiv =
882  BinaryOperator::CreateUDiv(Ops[0].V, Ops[1].V, SDI->getName(), SDI);
883  UDiv->setDebugLoc(SDI->getDebugLoc());
884  UDiv->setIsExact(SDI->isExact());
885 
886  Value *Res = UDiv;
887 
888  // If the operands had two different domains, we need to negate the result.
889  if (Ops[0].D != Ops[1].D)
890  Res = BinaryOperator::CreateNeg(Res, Res->getName() + ".neg", SDI);
891 
892  SDI->replaceAllUsesWith(Res);
893  SDI->eraseFromParent();
894 
895  // Try to simplify our new udiv.
896  processUDivOrURem(UDiv, LVI);
897 
898  return true;
899 }
900 
901 static bool processSDivOrSRem(BinaryOperator *Instr, LazyValueInfo *LVI) {
902  assert(Instr->getOpcode() == Instruction::SDiv ||
903  Instr->getOpcode() == Instruction::SRem);
904  if (Instr->getType()->isVectorTy())
905  return false;
906 
907  if (Instr->getOpcode() == Instruction::SDiv)
908  if (processSDiv(Instr, LVI))
909  return true;
910 
911  if (Instr->getOpcode() == Instruction::SRem)
912  if (processSRem(Instr, LVI))
913  return true;
914 
915  return narrowSDivOrSRem(Instr, LVI);
916 }
917 
918 static bool processAShr(BinaryOperator *SDI, LazyValueInfo *LVI) {
919  if (SDI->getType()->isVectorTy())
920  return false;
921 
922  if (!isNonNegative(SDI->getOperand(0), LVI, SDI))
923  return false;
924 
925  ++NumAShrs;
926  auto *BO = BinaryOperator::CreateLShr(SDI->getOperand(0), SDI->getOperand(1),
927  SDI->getName(), SDI);
928  BO->setDebugLoc(SDI->getDebugLoc());
929  BO->setIsExact(SDI->isExact());
930  SDI->replaceAllUsesWith(BO);
931  SDI->eraseFromParent();
932 
933  return true;
934 }
935 
936 static bool processSExt(SExtInst *SDI, LazyValueInfo *LVI) {
937  if (SDI->getType()->isVectorTy())
938  return false;
939 
940  Value *Base = SDI->getOperand(0);
941 
942  if (!isNonNegative(Base, LVI, SDI))
943  return false;
944 
945  ++NumSExt;
946  auto *ZExt =
947  CastInst::CreateZExtOrBitCast(Base, SDI->getType(), SDI->getName(), SDI);
948  ZExt->setDebugLoc(SDI->getDebugLoc());
949  SDI->replaceAllUsesWith(ZExt);
950  SDI->eraseFromParent();
951 
952  return true;
953 }
954 
955 static bool processBinOp(BinaryOperator *BinOp, LazyValueInfo *LVI) {
956  using OBO = OverflowingBinaryOperator;
957 
958  if (BinOp->getType()->isVectorTy())
959  return false;
960 
961  bool NSW = BinOp->hasNoSignedWrap();
962  bool NUW = BinOp->hasNoUnsignedWrap();
963  if (NSW && NUW)
964  return false;
965 
966  Instruction::BinaryOps Opcode = BinOp->getOpcode();
967  Value *LHS = BinOp->getOperand(0);
968  Value *RHS = BinOp->getOperand(1);
969 
970  ConstantRange LRange = LVI->getConstantRange(LHS, BinOp);
971  ConstantRange RRange = LVI->getConstantRange(RHS, BinOp);
972 
973  bool Changed = false;
974  bool NewNUW = false, NewNSW = false;
975  if (!NUW) {
977  Opcode, RRange, OBO::NoUnsignedWrap);
978  NewNUW = NUWRange.contains(LRange);
979  Changed |= NewNUW;
980  }
981  if (!NSW) {
983  Opcode, RRange, OBO::NoSignedWrap);
984  NewNSW = NSWRange.contains(LRange);
985  Changed |= NewNSW;
986  }
987 
988  setDeducedOverflowingFlags(BinOp, Opcode, NewNSW, NewNUW);
989 
990  return Changed;
991 }
992 
993 static bool processAnd(BinaryOperator *BinOp, LazyValueInfo *LVI) {
994  if (BinOp->getType()->isVectorTy())
995  return false;
996 
997  // Pattern match (and lhs, C) where C includes a superset of bits which might
998  // be set in lhs. This is a common truncation idiom created by instcombine.
999  Value *LHS = BinOp->getOperand(0);
1000  ConstantInt *RHS = dyn_cast<ConstantInt>(BinOp->getOperand(1));
1001  if (!RHS || !RHS->getValue().isMask())
1002  return false;
1003 
1004  // We can only replace the AND with LHS based on range info if the range does
1005  // not include undef.
1006  ConstantRange LRange =
1007  LVI->getConstantRange(LHS, BinOp, /*UndefAllowed=*/false);
1008  if (!LRange.getUnsignedMax().ule(RHS->getValue()))
1009  return false;
1010 
1011  BinOp->replaceAllUsesWith(LHS);
1012  BinOp->eraseFromParent();
1013  NumAnd++;
1014  return true;
1015 }
1016 
1017 
1019  if (Constant *C = LVI->getConstant(V, At))
1020  return C;
1021 
1022  // TODO: The following really should be sunk inside LVI's core algorithm, or
1023  // at least the outer shims around such.
1024  auto *C = dyn_cast<CmpInst>(V);
1025  if (!C) return nullptr;
1026 
1027  Value *Op0 = C->getOperand(0);
1028  Constant *Op1 = dyn_cast<Constant>(C->getOperand(1));
1029  if (!Op1) return nullptr;
1030 
1032  C->getPredicate(), Op0, Op1, At, /*UseBlockValue=*/false);
1033  if (Result == LazyValueInfo::Unknown)
1034  return nullptr;
1035 
1036  return (Result == LazyValueInfo::True) ?
1037  ConstantInt::getTrue(C->getContext()) :
1038  ConstantInt::getFalse(C->getContext());
1039 }
1040 
1042  const SimplifyQuery &SQ) {
1043  bool FnChanged = false;
1044  // Visiting in a pre-order depth-first traversal causes us to simplify early
1045  // blocks before querying later blocks (which require us to analyze early
1046  // blocks). Eagerly simplifying shallow blocks means there is strictly less
1047  // work to do for deep blocks. This also means we don't visit unreachable
1048  // blocks.
1049  for (BasicBlock *BB : depth_first(&F.getEntryBlock())) {
1050  bool BBChanged = false;
1051  for (Instruction &II : llvm::make_early_inc_range(*BB)) {
1052  switch (II.getOpcode()) {
1053  case Instruction::Select:
1054  BBChanged |= processSelect(cast<SelectInst>(&II), LVI);
1055  break;
1056  case Instruction::PHI:
1057  BBChanged |= processPHI(cast<PHINode>(&II), LVI, DT, SQ);
1058  break;
1059  case Instruction::ICmp:
1060  case Instruction::FCmp:
1061  BBChanged |= processCmp(cast<CmpInst>(&II), LVI);
1062  break;
1063  case Instruction::Load:
1064  case Instruction::Store:
1065  BBChanged |= processMemAccess(&II, LVI);
1066  break;
1067  case Instruction::Call:
1068  case Instruction::Invoke:
1069  BBChanged |= processCallSite(cast<CallBase>(II), LVI);
1070  break;
1071  case Instruction::SRem:
1072  case Instruction::SDiv:
1073  BBChanged |= processSDivOrSRem(cast<BinaryOperator>(&II), LVI);
1074  break;
1075  case Instruction::UDiv:
1076  case Instruction::URem:
1077  BBChanged |= processUDivOrURem(cast<BinaryOperator>(&II), LVI);
1078  break;
1079  case Instruction::AShr:
1080  BBChanged |= processAShr(cast<BinaryOperator>(&II), LVI);
1081  break;
1082  case Instruction::SExt:
1083  BBChanged |= processSExt(cast<SExtInst>(&II), LVI);
1084  break;
1085  case Instruction::Add:
1086  case Instruction::Sub:
1087  case Instruction::Mul:
1088  case Instruction::Shl:
1089  BBChanged |= processBinOp(cast<BinaryOperator>(&II), LVI);
1090  break;
1091  case Instruction::And:
1092  BBChanged |= processAnd(cast<BinaryOperator>(&II), LVI);
1093  break;
1094  }
1095  }
1096 
1097  Instruction *Term = BB->getTerminator();
1098  switch (Term->getOpcode()) {
1099  case Instruction::Switch:
1100  BBChanged |= processSwitch(cast<SwitchInst>(Term), LVI, DT);
1101  break;
1102  case Instruction::Ret: {
1103  auto *RI = cast<ReturnInst>(Term);
1104  // Try to determine the return value if we can. This is mainly here to
1105  // simplify the writing of unit tests, but also helps to enable IPO by
1106  // constant folding the return values of callees.
1107  auto *RetVal = RI->getReturnValue();
1108  if (!RetVal) break; // handle "ret void"
1109  if (isa<Constant>(RetVal)) break; // nothing to do
1110  if (auto *C = getConstantAt(RetVal, RI, LVI)) {
1111  ++NumReturns;
1112  RI->replaceUsesOfWith(RetVal, C);
1113  BBChanged = true;
1114  }
1115  }
1116  }
1117 
1118  FnChanged |= BBChanged;
1119  }
1120 
1121  return FnChanged;
1122 }
1123 
1125  if (skipFunction(F))
1126  return false;
1127 
1128  LazyValueInfo *LVI = &getAnalysis<LazyValueInfoWrapperPass>().getLVI();
1129  DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1130 
1131  return runImpl(F, LVI, DT, getBestSimplifyQuery(*this, F));
1132 }
1133 
1138 
1139  bool Changed = runImpl(F, LVI, DT, getBestSimplifyQuery(AM, F));
1140 
1141  PreservedAnalyses PA;
1142  if (!Changed) {
1143  PA = PreservedAnalyses::all();
1144  } else {
1147  }
1148 
1149  // Keeping LVI alive is expensive, both because it uses a lot of memory, and
1150  // because invalidating values in LVI is expensive. While CVP does preserve
1151  // LVI, we know that passes after JumpThreading+CVP will not need the result
1152  // of this analysis, so we forcefully discard it early.
1153  PA.abandon<LazyValueAnalysis>();
1154  return PA;
1155 }
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:697
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:3550
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:918
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
High
uint64_t High
Definition: NVVMIntrRange.cpp:61
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
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:594
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::APInt::getSignedMaxValue
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
Definition: APInt.h:191
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:476
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:2652
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::SwitchInst::CaseIteratorImpl
Definition: Instructions.h:3245
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:751
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:849
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:685
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:424
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:1041
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:6291
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:1135
willNotOverflow
static bool willNotOverflow(BinaryOpIntrinsic *BO, LazyValueInfo *LVI)
Definition: CorrelatedValuePropagation.cpp:416
llvm::MCID::Call
@ Call
Definition: MCInstrDesc.h:153
llvm::SPII::Load
@ Load
Definition: SparcInstrInfo.h:32
processMinMaxIntrinsic
static bool processMinMaxIntrinsic(MinMaxIntrinsic *MM, LazyValueInfo *LVI)
Definition: CorrelatedValuePropagation.cpp:533
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:1018
getDomain
Domain getDomain(Value *V, LazyValueInfo *LVI, Instruction *CxtI)
Definition: CorrelatedValuePropagation.cpp:687
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:857
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
llvm::ConstantRange::getSignedMin
APInt getSignedMin() const
Return the smallest signed value contained in the ConstantRange.
Definition: ConstantRange.cpp:387
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:547
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:955
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:572
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::SPII::Store
@ Store
Definition: SparcInstrInfo.h:33
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:732
llvm::MinMaxIntrinsic::getLHS
Value * getLHS() const
Definition: IntrinsicInst.h:527
processSExt
static bool processSExt(SExtInst *SDI, LazyValueInfo *LVI)
Definition: CorrelatedValuePropagation.cpp:936
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
llvm::APIntOps::smin
const APInt & smin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be signed.
Definition: APInt.h:2111
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:793
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:901
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:520
llvm::Value::getContext
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:978
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:4825
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:297
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::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
llvm::ConstantRange::getSignedMax
APInt getSignedMax() const
Return the largest signed value contained in the ConstantRange.
Definition: ConstantRange.cpp:381
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:6380
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::createUnreachableSwitchDefault
void createUnreachableSwitchDefault(SwitchInst *Switch, DomTreeUpdater *DTU=nullptr)
This function removes the default destination from the specified switch.
Definition: Local.cpp:2185
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:678
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:573
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:993
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:2625
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:5274
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:3204
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:3082
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:2636
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:671
Debug.h
llvm::APIntOps::smax
const APInt & smax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be signed.
Definition: APInt.h:2116
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