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