LLVM  15.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/Transforms/Scalar.h"
46 #include <cassert>
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  auto *C = dyn_cast<Constant>(Cmp->getOperand(1));
344  if (!C)
345  return false;
346 
347  LazyValueInfo::Tristate Result =
348  LVI->getPredicateAt(Cmp->getPredicate(), Op0, C, Cmp,
349  /*UseBlockValue=*/true);
350  if (Result == LazyValueInfo::Unknown)
351  return false;
352 
353  ++NumCmps;
354  Constant *TorF = ConstantInt::get(Type::getInt1Ty(Cmp->getContext()), Result);
355  Cmp->replaceAllUsesWith(TorF);
356  Cmp->eraseFromParent();
357  return true;
358 }
359 
360 static bool processCmp(CmpInst *Cmp, LazyValueInfo *LVI) {
361  if (constantFoldCmp(Cmp, LVI))
362  return true;
363 
364  if (auto *ICmp = dyn_cast<ICmpInst>(Cmp))
365  if (processICmp(ICmp, LVI))
366  return true;
367 
368  return false;
369 }
370 
371 /// Simplify a switch instruction by removing cases which can never fire. If the
372 /// uselessness of a case could be determined locally then constant propagation
373 /// would already have figured it out. Instead, walk the predecessors and
374 /// statically evaluate cases based on information available on that edge. Cases
375 /// that cannot fire no matter what the incoming edge can safely be removed. If
376 /// a case fires on every incoming edge then the entire switch can be removed
377 /// and replaced with a branch to the case destination.
379  DominatorTree *DT) {
381  Value *Cond = I->getCondition();
382  BasicBlock *BB = I->getParent();
383 
384  // Analyse each switch case in turn.
385  bool Changed = false;
386  DenseMap<BasicBlock*, int> SuccessorsCount;
387  for (auto *Succ : successors(BB))
388  SuccessorsCount[Succ]++;
389 
390  { // Scope for SwitchInstProfUpdateWrapper. It must not live during
391  // ConstantFoldTerminator() as the underlying SwitchInst can be changed.
393 
394  for (auto CI = SI->case_begin(), CE = SI->case_end(); CI != CE;) {
395  ConstantInt *Case = CI->getCaseValue();
397  LVI->getPredicateAt(CmpInst::ICMP_EQ, Cond, Case, I,
398  /* UseBlockValue */ true);
399 
400  if (State == LazyValueInfo::False) {
401  // This case never fires - remove it.
402  BasicBlock *Succ = CI->getCaseSuccessor();
403  Succ->removePredecessor(BB);
404  CI = SI.removeCase(CI);
405  CE = SI->case_end();
406 
407  // The condition can be modified by removePredecessor's PHI simplification
408  // logic.
409  Cond = SI->getCondition();
410 
411  ++NumDeadCases;
412  Changed = true;
413  if (--SuccessorsCount[Succ] == 0)
415  continue;
416  }
417  if (State == LazyValueInfo::True) {
418  // This case always fires. Arrange for the switch to be turned into an
419  // unconditional branch by replacing the switch condition with the case
420  // value.
421  SI->setCondition(Case);
422  NumDeadCases += SI->getNumCases();
423  Changed = true;
424  break;
425  }
426 
427  // Increment the case iterator since we didn't delete it.
428  ++CI;
429  }
430  }
431 
432  if (Changed)
433  // If the switch has been simplified to the point where it can be replaced
434  // by a branch then do so now.
435  ConstantFoldTerminator(BB, /*DeleteDeadConditions = */ false,
436  /*TLI = */ nullptr, &DTU);
437  return Changed;
438 }
439 
440 // See if we can prove that the given binary op intrinsic will not overflow.
442  ConstantRange LRange = LVI->getConstantRange(BO->getLHS(), BO);
443  ConstantRange RRange = LVI->getConstantRange(BO->getRHS(), BO);
445  BO->getBinaryOp(), RRange, BO->getNoWrapKind());
446  return NWRegion.contains(LRange);
447 }
448 
450  bool NewNSW, bool NewNUW) {
451  Statistic *OpcNW, *OpcNSW, *OpcNUW;
452  switch (Opcode) {
453  case Instruction::Add:
454  OpcNW = &NumAddNW;
455  OpcNSW = &NumAddNSW;
456  OpcNUW = &NumAddNUW;
457  break;
458  case Instruction::Sub:
459  OpcNW = &NumSubNW;
460  OpcNSW = &NumSubNSW;
461  OpcNUW = &NumSubNUW;
462  break;
463  case Instruction::Mul:
464  OpcNW = &NumMulNW;
465  OpcNSW = &NumMulNSW;
466  OpcNUW = &NumMulNUW;
467  break;
468  case Instruction::Shl:
469  OpcNW = &NumShlNW;
470  OpcNSW = &NumShlNSW;
471  OpcNUW = &NumShlNUW;
472  break;
473  default:
474  llvm_unreachable("Will not be called with other binops");
475  }
476 
477  auto *Inst = dyn_cast<Instruction>(V);
478  if (NewNSW) {
479  ++NumNW;
480  ++*OpcNW;
481  ++NumNSW;
482  ++*OpcNSW;
483  if (Inst)
484  Inst->setHasNoSignedWrap();
485  }
486  if (NewNUW) {
487  ++NumNW;
488  ++*OpcNW;
489  ++NumNUW;
490  ++*OpcNUW;
491  if (Inst)
492  Inst->setHasNoUnsignedWrap();
493  }
494 }
495 
496 static bool processBinOp(BinaryOperator *BinOp, LazyValueInfo *LVI);
497 
498 // See if @llvm.abs argument is alays positive/negative, and simplify.
499 // Notably, INT_MIN can belong to either range, regardless of the NSW,
500 // because it is negation-invariant.
502  Value *X = II->getArgOperand(0);
503  bool IsIntMinPoison = cast<ConstantInt>(II->getArgOperand(1))->isOne();
504 
505  Type *Ty = X->getType();
506  Constant *IntMin =
509 
510  // Is X in [0, IntMin]? NOTE: INT_MIN is fine!
511  Result = LVI->getPredicateAt(CmpInst::Predicate::ICMP_ULE, X, IntMin, II,
512  /*UseBlockValue=*/true);
513  if (Result == LazyValueInfo::True) {
514  ++NumAbs;
515  II->replaceAllUsesWith(X);
516  II->eraseFromParent();
517  return true;
518  }
519 
520  // Is X in [IntMin, 0]? NOTE: INT_MIN is fine!
522  Result = LVI->getPredicateAt(CmpInst::Predicate::ICMP_SLE, X, Zero, II,
523  /*UseBlockValue=*/true);
524  assert(Result != LazyValueInfo::False && "Should have been handled already.");
525 
526  if (Result == LazyValueInfo::Unknown) {
527  // Argument's range crosses zero.
528  bool Changed = false;
529  if (!IsIntMinPoison) {
530  // Can we at least tell that the argument is never INT_MIN?
531  Result = LVI->getPredicateAt(CmpInst::Predicate::ICMP_NE, X, IntMin, II,
532  /*UseBlockValue=*/true);
533  if (Result == LazyValueInfo::True) {
534  ++NumNSW;
535  ++NumSubNSW;
537  Changed = true;
538  }
539  }
540  return Changed;
541  }
542 
543  IRBuilder<> B(II);
544  Value *NegX = B.CreateNeg(X, II->getName(), /*HasNUW=*/false,
545  /*HasNSW=*/IsIntMinPoison);
546  ++NumAbs;
547  II->replaceAllUsesWith(NegX);
548  II->eraseFromParent();
549 
550  // See if we can infer some no-wrap flags.
551  if (auto *BO = dyn_cast<BinaryOperator>(NegX))
552  processBinOp(BO, LVI);
553 
554  return true;
555 }
556 
557 // See if this min/max intrinsic always picks it's one specific operand.
561  Pred, MM->getLHS(), MM->getRHS(), MM, /*UseBlockValue=*/true);
562  if (Result == LazyValueInfo::Unknown)
563  return false;
564 
565  ++NumMinMax;
566  MM->replaceAllUsesWith(MM->getOperand(!Result));
567  MM->eraseFromParent();
568  return true;
569 }
570 
571 // Rewrite this with.overflow intrinsic as non-overflowing.
573  IRBuilder<> B(WO);
574  Instruction::BinaryOps Opcode = WO->getBinaryOp();
575  bool NSW = WO->isSigned();
576  bool NUW = !WO->isSigned();
577 
578  Value *NewOp =
579  B.CreateBinOp(Opcode, WO->getLHS(), WO->getRHS(), WO->getName());
580  setDeducedOverflowingFlags(NewOp, Opcode, NSW, NUW);
581 
582  StructType *ST = cast<StructType>(WO->getType());
583  Constant *Struct = ConstantStruct::get(ST,
584  { UndefValue::get(ST->getElementType(0)),
585  ConstantInt::getFalse(ST->getElementType(1)) });
586  Value *NewI = B.CreateInsertValue(Struct, NewOp, 0);
587  WO->replaceAllUsesWith(NewI);
588  WO->eraseFromParent();
589  ++NumOverflows;
590 
591  // See if we can infer the other no-wrap too.
592  if (auto *BO = dyn_cast<BinaryOperator>(NewOp))
593  processBinOp(BO, LVI);
594 
595  return true;
596 }
597 
599  Instruction::BinaryOps Opcode = SI->getBinaryOp();
600  bool NSW = SI->isSigned();
601  bool NUW = !SI->isSigned();
603  Opcode, SI->getLHS(), SI->getRHS(), SI->getName(), SI);
604  BinOp->setDebugLoc(SI->getDebugLoc());
605  setDeducedOverflowingFlags(BinOp, Opcode, NSW, NUW);
606 
607  SI->replaceAllUsesWith(BinOp);
608  SI->eraseFromParent();
609  ++NumSaturating;
610 
611  // See if we can infer the other no-wrap too.
612  if (auto *BO = dyn_cast<BinaryOperator>(BinOp))
613  processBinOp(BO, LVI);
614 
615  return true;
616 }
617 
618 /// Infer nonnull attributes for the arguments at the specified callsite.
619 static bool processCallSite(CallBase &CB, LazyValueInfo *LVI) {
620 
621  if (CB.getIntrinsicID() == Intrinsic::abs) {
622  return processAbsIntrinsic(&cast<IntrinsicInst>(CB), LVI);
623  }
624 
625  if (auto *MM = dyn_cast<MinMaxIntrinsic>(&CB)) {
626  return processMinMaxIntrinsic(MM, LVI);
627  }
628 
629  if (auto *WO = dyn_cast<WithOverflowInst>(&CB)) {
630  if (WO->getLHS()->getType()->isIntegerTy() && willNotOverflow(WO, LVI)) {
631  return processOverflowIntrinsic(WO, LVI);
632  }
633  }
634 
635  if (auto *SI = dyn_cast<SaturatingInst>(&CB)) {
636  if (SI->getType()->isIntegerTy() && willNotOverflow(SI, LVI)) {
637  return processSaturatingInst(SI, LVI);
638  }
639  }
640 
641  bool Changed = false;
642 
643  // Deopt bundle operands are intended to capture state with minimal
644  // perturbance of the code otherwise. If we can find a constant value for
645  // any such operand and remove a use of the original value, that's
646  // desireable since it may allow further optimization of that value (e.g. via
647  // single use rules in instcombine). Since deopt uses tend to,
648  // idiomatically, appear along rare conditional paths, it's reasonable likely
649  // we may have a conditional fact with which LVI can fold.
650  if (auto DeoptBundle = CB.getOperandBundle(LLVMContext::OB_deopt)) {
651  for (const Use &ConstU : DeoptBundle->Inputs) {
652  Use &U = const_cast<Use&>(ConstU);
653  Value *V = U.get();
654  if (V->getType()->isVectorTy()) continue;
655  if (isa<Constant>(V)) continue;
656 
657  Constant *C = LVI->getConstant(V, &CB);
658  if (!C) continue;
659  U.set(C);
660  Changed = true;
661  }
662  }
663 
665  unsigned ArgNo = 0;
666 
667  for (Value *V : CB.args()) {
668  PointerType *Type = dyn_cast<PointerType>(V->getType());
669  // Try to mark pointer typed parameters as non-null. We skip the
670  // relatively expensive analysis for constants which are obviously either
671  // null or non-null to start with.
672  if (Type && !CB.paramHasAttr(ArgNo, Attribute::NonNull) &&
673  !isa<Constant>(V) &&
676  /*UseBlockValue=*/false) == LazyValueInfo::False)
677  ArgNos.push_back(ArgNo);
678  ArgNo++;
679  }
680 
681  assert(ArgNo == CB.arg_size() && "Call arguments not processed correctly.");
682 
683  if (ArgNos.empty())
684  return Changed;
685 
686  NumNonNull += ArgNos.size();
687  AttributeList AS = CB.getAttributes();
688  LLVMContext &Ctx = CB.getContext();
689  AS = AS.addParamAttribute(Ctx, ArgNos,
690  Attribute::get(Ctx, Attribute::NonNull));
691  CB.setAttributes(AS);
692 
693  return true;
694 }
695 
696 static bool isNonNegative(Value *V, LazyValueInfo *LVI, Instruction *CxtI) {
697  Constant *Zero = ConstantInt::get(V->getType(), 0);
698  auto Result = LVI->getPredicateAt(ICmpInst::ICMP_SGE, V, Zero, CxtI,
699  /*UseBlockValue=*/true);
700  return Result == LazyValueInfo::True;
701 }
702 
703 static bool isNonPositive(Value *V, LazyValueInfo *LVI, Instruction *CxtI) {
704  Constant *Zero = ConstantInt::get(V->getType(), 0);
705  auto Result = LVI->getPredicateAt(ICmpInst::ICMP_SLE, V, Zero, CxtI,
706  /*UseBlockValue=*/true);
707  return Result == LazyValueInfo::True;
708 }
709 
710 enum class Domain { NonNegative, NonPositive, Unknown };
711 
713  if (isNonNegative(V, LVI, CxtI))
714  return Domain::NonNegative;
715  if (isNonPositive(V, LVI, CxtI))
716  return Domain::NonPositive;
717  return Domain::Unknown;
718 }
719 
720 /// Try to shrink a sdiv/srem's width down to the smallest power of two that's
721 /// sufficient to contain its operands.
722 static bool narrowSDivOrSRem(BinaryOperator *Instr, LazyValueInfo *LVI) {
723  assert(Instr->getOpcode() == Instruction::SDiv ||
724  Instr->getOpcode() == Instruction::SRem);
725  if (Instr->getType()->isVectorTy())
726  return false;
727 
728  // Find the smallest power of two bitwidth that's sufficient to hold Instr's
729  // operands.
730  unsigned OrigWidth = Instr->getType()->getIntegerBitWidth();
731 
732  // What is the smallest bit width that can accomodate the entire value ranges
733  // of both of the operands?
734  std::array<Optional<ConstantRange>, 2> CRs;
735  unsigned MinSignedBits = 0;
736  for (auto I : zip(Instr->operands(), CRs)) {
737  std::get<1>(I) = LVI->getConstantRange(std::get<0>(I), Instr);
738  MinSignedBits = std::max(std::get<1>(I)->getMinSignedBits(), MinSignedBits);
739  }
740 
741  // sdiv/srem is UB if divisor is -1 and divident is INT_MIN, so unless we can
742  // prove that such a combination is impossible, we need to bump the bitwidth.
743  if (CRs[1]->contains(APInt::getAllOnes(OrigWidth)) &&
744  CRs[0]->contains(APInt::getSignedMinValue(MinSignedBits).sext(OrigWidth)))
745  ++MinSignedBits;
746 
747  // Don't shrink below 8 bits wide.
748  unsigned NewWidth = std::max<unsigned>(PowerOf2Ceil(MinSignedBits), 8);
749 
750  // NewWidth might be greater than OrigWidth if OrigWidth is not a power of
751  // two.
752  if (NewWidth >= OrigWidth)
753  return false;
754 
755  ++NumSDivSRemsNarrowed;
756  IRBuilder<> B{Instr};
757  auto *TruncTy = Type::getIntNTy(Instr->getContext(), NewWidth);
758  auto *LHS = B.CreateTruncOrBitCast(Instr->getOperand(0), TruncTy,
759  Instr->getName() + ".lhs.trunc");
760  auto *RHS = B.CreateTruncOrBitCast(Instr->getOperand(1), TruncTy,
761  Instr->getName() + ".rhs.trunc");
762  auto *BO = B.CreateBinOp(Instr->getOpcode(), LHS, RHS, Instr->getName());
763  auto *Sext = B.CreateSExt(BO, Instr->getType(), Instr->getName() + ".sext");
764  if (auto *BinOp = dyn_cast<BinaryOperator>(BO))
765  if (BinOp->getOpcode() == Instruction::SDiv)
766  BinOp->setIsExact(Instr->isExact());
767 
768  Instr->replaceAllUsesWith(Sext);
769  Instr->eraseFromParent();
770  return true;
771 }
772 
773 /// Try to shrink a udiv/urem's width down to the smallest power of two that's
774 /// sufficient to contain its operands.
775 static bool processUDivOrURem(BinaryOperator *Instr, LazyValueInfo *LVI) {
776  assert(Instr->getOpcode() == Instruction::UDiv ||
777  Instr->getOpcode() == Instruction::URem);
778  if (Instr->getType()->isVectorTy())
779  return false;
780 
781  // Find the smallest power of two bitwidth that's sufficient to hold Instr's
782  // operands.
783 
784  // What is the smallest bit width that can accomodate the entire value ranges
785  // of both of the operands?
786  unsigned MaxActiveBits = 0;
787  for (Value *Operand : Instr->operands()) {
788  ConstantRange CR = LVI->getConstantRange(Operand, Instr);
789  MaxActiveBits = std::max(CR.getActiveBits(), MaxActiveBits);
790  }
791  // Don't shrink below 8 bits wide.
792  unsigned NewWidth = std::max<unsigned>(PowerOf2Ceil(MaxActiveBits), 8);
793 
794  // NewWidth might be greater than OrigWidth if OrigWidth is not a power of
795  // two.
796  if (NewWidth >= Instr->getType()->getIntegerBitWidth())
797  return false;
798 
799  ++NumUDivURemsNarrowed;
800  IRBuilder<> B{Instr};
801  auto *TruncTy = Type::getIntNTy(Instr->getContext(), NewWidth);
802  auto *LHS = B.CreateTruncOrBitCast(Instr->getOperand(0), TruncTy,
803  Instr->getName() + ".lhs.trunc");
804  auto *RHS = B.CreateTruncOrBitCast(Instr->getOperand(1), TruncTy,
805  Instr->getName() + ".rhs.trunc");
806  auto *BO = B.CreateBinOp(Instr->getOpcode(), LHS, RHS, Instr->getName());
807  auto *Zext = B.CreateZExt(BO, Instr->getType(), Instr->getName() + ".zext");
808  if (auto *BinOp = dyn_cast<BinaryOperator>(BO))
809  if (BinOp->getOpcode() == Instruction::UDiv)
810  BinOp->setIsExact(Instr->isExact());
811 
812  Instr->replaceAllUsesWith(Zext);
813  Instr->eraseFromParent();
814  return true;
815 }
816 
817 static bool processSRem(BinaryOperator *SDI, LazyValueInfo *LVI) {
818  assert(SDI->getOpcode() == Instruction::SRem);
819  if (SDI->getType()->isVectorTy())
820  return false;
821 
822  struct Operand {
823  Value *V;
824  Domain D;
825  };
826  std::array<Operand, 2> Ops;
827 
828  for (const auto I : zip(Ops, SDI->operands())) {
829  Operand &Op = std::get<0>(I);
830  Op.V = std::get<1>(I);
831  Op.D = getDomain(Op.V, LVI, SDI);
832  if (Op.D == Domain::Unknown)
833  return false;
834  }
835 
836  // We know domains of both of the operands!
837  ++NumSRems;
838 
839  // We need operands to be non-negative, so negate each one that isn't.
840  for (Operand &Op : Ops) {
841  if (Op.D == Domain::NonNegative)
842  continue;
843  auto *BO =
844  BinaryOperator::CreateNeg(Op.V, Op.V->getName() + ".nonneg", SDI);
845  BO->setDebugLoc(SDI->getDebugLoc());
846  Op.V = BO;
847  }
848 
849  auto *URem =
850  BinaryOperator::CreateURem(Ops[0].V, Ops[1].V, SDI->getName(), SDI);
851  URem->setDebugLoc(SDI->getDebugLoc());
852 
853  Value *Res = URem;
854 
855  // If the divident was non-positive, we need to negate the result.
856  if (Ops[0].D == Domain::NonPositive)
857  Res = BinaryOperator::CreateNeg(Res, Res->getName() + ".neg", SDI);
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:1630
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:722
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm::BinaryOpIntrinsic::getBinaryOp
Instruction::BinaryOps getBinaryOp() const
Returns the binary operation underlying the intrinsic.
Definition: IntrinsicInst.cpp:657
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:17
llvm::Type::getInt1Ty
static IntegerType * getInt1Ty(LLVMContext &C)
Definition: Type.cpp:236
llvm::CmpInst::ICMP_EQ
@ ICMP_EQ
equal
Definition: InstrTypes.h:740
llvm::CallBase::getOperandBundle
Optional< OperandBundleUse > getOperandBundle(StringRef Name) const
Return an operand bundle by name, if present.
Definition: InstrTypes.h:2027
Optional.h
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:3572
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:780
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:1735
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:1100
llvm::ConstantStruct::get
static Constant * get(StructType *T, ArrayRef< Constant * > V)
Definition: Constants.cpp:1355
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:90
llvm::BinaryOpIntrinsic::getRHS
Value * getRHS() const
Definition: IntrinsicInst.h:664
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:1185
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:561
llvm::BinaryOpIntrinsic::getLHS
Value * getLHS() const
Definition: IntrinsicInst.h:663
processPHI
static bool processPHI(PHINode *P, LazyValueInfo *LVI, DominatorTree *DT, const SimplifyQuery &SQ)
Definition: CorrelatedValuePropagation.cpp:263
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:640
llvm::Instruction::hasNoUnsignedWrap
bool hasNoUnsignedWrap() const
Determine whether the no unsigned wrap flag is set.
Definition: Instruction.cpp:135
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:619
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:1591
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:425
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:501
llvm::MinMaxIntrinsic::getPredicate
static ICmpInst::Predicate getPredicate(Intrinsic::ID ID)
Returns the comparison predicate underlying the intrinsic.
Definition: IntrinsicInst.h:569
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:729
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:2794
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:775
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
llvm::SPII::Load
@ Load
Definition: SparcInstrInfo.h:32
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: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: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
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
Domain
Domain
Definition: CorrelatedValuePropagation.cpp:710
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:227
llvm::BinaryOpIntrinsic::getNoWrapKind
unsigned getNoWrapKind() const
Returns one of OBO::NoSignedWrap or OBO::NoUnsignedWrap.
Definition: IntrinsicInst.cpp:690
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:449
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:288
llvm::SaturatingInst
Represents a saturating add/sub intrinsic.
Definition: IntrinsicInst.h:698
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:425
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:302
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:1777
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:928
llvm::CorrelatedValuePropagationPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: CorrelatedValuePropagation.cpp:1172
willNotOverflow
static bool willNotOverflow(BinaryOpIntrinsic *BO, LazyValueInfo *LVI)
Definition: CorrelatedValuePropagation.cpp:441
llvm::MCID::Call
@ Call
Definition: MCInstrDesc.h:155
llvm::SPII::Store
@ Store
Definition: SparcInstrInfo.h:33
processMinMaxIntrinsic
static bool processMinMaxIntrinsic(MinMaxIntrinsic *MM, LazyValueInfo *LVI)
Definition: CorrelatedValuePropagation.cpp:558
llvm::Type::getIntegerBitWidth
unsigned getIntegerBitWidth() const
Definition: DerivedTypes.h:97
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:712
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:868
BasicBlock.h
llvm::cl::opt< bool >
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:77
llvm::ICmpInst
This instruction compares its operands according to the predicate given to the constructor.
Definition: Instructions.h:1173
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:378
llvm::BinaryOpIntrinsic::isSigned
bool isSigned() const
Whether the intrinsic is signed or unsigned.
Definition: IntrinsicInst.cpp:677
uint64_t
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:1610
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:572
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:1763
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:68
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
Domain::Unknown
@ Unknown
llvm::DenseMap
Definition: DenseMap.h:716
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::M68kBeads::Term
@ Term
Definition: M68kBaseInfo.h:71
processMemAccess
static bool processMemAccess(Instruction *I, LazyValueInfo *LVI)
Definition: CorrelatedValuePropagation.cpp:294
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
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:618
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:6486
llvm::Instruction::setDebugLoc
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:364
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())
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1724
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:776
llvm::MinMaxIntrinsic::getLHS
Value * getLHS() const
Definition: IntrinsicInst.h:565
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:311
llvm::BinaryOperator
Definition: InstrTypes.h:188
processSRem
static bool processSRem(BinaryOperator *SDI, LazyValueInfo *LVI)
Definition: CorrelatedValuePropagation.cpp:817
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:360
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:137
llvm::LLVMContext::OB_deopt
@ OB_deopt
Definition: LLVMContext.h:90
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:529
llvm::Value::getContext
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:991
ConstantRange.h
llvm::Instruction::isExact
bool isExact() const
Determine whether the exact flag is set.
Definition: Instruction.cpp:195
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:677
llvm::TrackingStatistic
Definition: Statistic.h:50
llvm::SExtInst
This class represents a sign extension of integer types.
Definition: Instructions.h:4845
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:305
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:173
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:1346
llvm::ConstantInt::getFalse
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:883
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:69
Constant.h
llvm::ConstantFoldTerminator
bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions=false, const TargetLibraryInfo *TLI=nullptr, DomTreeUpdater *DTU=nullptr)
If a terminator instruction is predicated on a constant value, convert it into an unconditional branc...
Definition: Local.cpp:125
llvm::ConstantInt::getTrue
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:876
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:6575
llvm::Type::getIntNTy
static IntegerType * getIntNTy(LLVMContext &C, unsigned N)
Definition: Type.cpp:243
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:345
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:703
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:476
llvm::ConstantRange::contains
bool contains(const APInt &Val) const
Return true if the specified value is in the set.
Definition: ConstantRange.cpp:449
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:598
llvm::IntrinsicInst
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:46
llvm::Instruction::BinaryOps
BinaryOps
Definition: Instruction.h:786
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:267
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:548
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:367
processAnd
static bool processAnd(BinaryOperator *BinOp, LazyValueInfo *LVI)
Definition: CorrelatedValuePropagation.cpp:1030
llvm::Instruction::hasNoSignedWrap
bool hasNoSignedWrap() const
Determine whether the no signed wrap flag is set.
Definition: Instruction.cpp:139
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:148
llvm::PHINode
Definition: Instructions.h:2651
llvm::BasicBlock::removePredecessor
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
Definition: BasicBlock.cpp:318
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:5411
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:3230
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:3226
llvm::cl::desc
Definition: CommandLine.h:405
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:1746
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:2778
Value.h
llvm::abs
APFloat abs(APFloat X)
Returns the absolute value of the argument.
Definition: APFloat.h:1282
Domain::NonNegative
@ NonNegative
InitializePasses.h
llvm::DomTreeUpdater::applyUpdatesPermissive
void applyUpdatesPermissive(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
Definition: DomTreeUpdater.cpp:250
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
isNonNegative
static bool isNonNegative(Value *V, LazyValueInfo *LVI, Instruction *CxtI)
Definition: CorrelatedValuePropagation.cpp:696
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:566
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::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38
simplifyCommonValuePhi
static bool simplifyCommonValuePhi(PHINode *P, LazyValueInfo *LVI, DominatorTree *DT)
Try to simplify a phi with constant incoming values that match the edge values of a non-constant valu...
Definition: CorrelatedValuePropagation.cpp:165