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/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());
584  { PoisonValue::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 accommodate 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 accommodate 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  auto *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  Res->setDebugLoc(SDI->getDebugLoc());
859  }
860 
861  SDI->replaceAllUsesWith(Res);
862  SDI->eraseFromParent();
863 
864  // Try to simplify our new urem.
865  processUDivOrURem(URem, LVI);
866 
867  return true;
868 }
869 
870 /// See if LazyValueInfo's ability to exploit edge conditions or range
871 /// information is sufficient to prove the signs of both operands of this SDiv.
872 /// If this is the case, replace the SDiv with a UDiv. Even for local
873 /// conditions, this can sometimes prove conditions instcombine can't by
874 /// exploiting range information.
875 static bool processSDiv(BinaryOperator *SDI, LazyValueInfo *LVI) {
876  assert(SDI->getOpcode() == Instruction::SDiv);
877  if (SDI->getType()->isVectorTy())
878  return false;
879 
880  struct Operand {
881  Value *V;
882  Domain D;
883  };
884  std::array<Operand, 2> Ops;
885 
886  for (const auto I : zip(Ops, SDI->operands())) {
887  Operand &Op = std::get<0>(I);
888  Op.V = std::get<1>(I);
889  Op.D = getDomain(Op.V, LVI, SDI);
890  if (Op.D == Domain::Unknown)
891  return false;
892  }
893 
894  // We know domains of both of the operands!
895  ++NumSDivs;
896 
897  // We need operands to be non-negative, so negate each one that isn't.
898  for (Operand &Op : Ops) {
899  if (Op.D == Domain::NonNegative)
900  continue;
901  auto *BO =
902  BinaryOperator::CreateNeg(Op.V, Op.V->getName() + ".nonneg", SDI);
903  BO->setDebugLoc(SDI->getDebugLoc());
904  Op.V = BO;
905  }
906 
907  auto *UDiv =
908  BinaryOperator::CreateUDiv(Ops[0].V, Ops[1].V, SDI->getName(), SDI);
909  UDiv->setDebugLoc(SDI->getDebugLoc());
910  UDiv->setIsExact(SDI->isExact());
911 
912  Value *Res = UDiv;
913 
914  // If the operands had two different domains, we need to negate the result.
915  if (Ops[0].D != Ops[1].D)
916  Res = BinaryOperator::CreateNeg(Res, Res->getName() + ".neg", SDI);
917 
918  SDI->replaceAllUsesWith(Res);
919  SDI->eraseFromParent();
920 
921  // Try to simplify our new udiv.
922  processUDivOrURem(UDiv, LVI);
923 
924  return true;
925 }
926 
927 static bool processSDivOrSRem(BinaryOperator *Instr, LazyValueInfo *LVI) {
928  assert(Instr->getOpcode() == Instruction::SDiv ||
929  Instr->getOpcode() == Instruction::SRem);
930  if (Instr->getType()->isVectorTy())
931  return false;
932 
933  if (Instr->getOpcode() == Instruction::SDiv)
934  if (processSDiv(Instr, LVI))
935  return true;
936 
937  if (Instr->getOpcode() == Instruction::SRem)
938  if (processSRem(Instr, LVI))
939  return true;
940 
941  return narrowSDivOrSRem(Instr, LVI);
942 }
943 
944 static bool processAShr(BinaryOperator *SDI, LazyValueInfo *LVI) {
945  if (SDI->getType()->isVectorTy())
946  return false;
947 
948  ConstantRange LRange = LVI->getConstantRange(SDI->getOperand(0), SDI);
949  unsigned OrigWidth = SDI->getType()->getIntegerBitWidth();
950  ConstantRange NegOneOrZero =
951  ConstantRange(APInt(OrigWidth, (uint64_t)-1, true), APInt(OrigWidth, 1));
952  if (NegOneOrZero.contains(LRange)) {
953  // ashr of -1 or 0 never changes the value, so drop the whole instruction
954  ++NumAShrsRemoved;
955  SDI->replaceAllUsesWith(SDI->getOperand(0));
956  SDI->eraseFromParent();
957  return true;
958  }
959 
960  if (!isNonNegative(SDI->getOperand(0), LVI, SDI))
961  return false;
962 
963  ++NumAShrsConverted;
964  auto *BO = BinaryOperator::CreateLShr(SDI->getOperand(0), SDI->getOperand(1),
965  "", SDI);
966  BO->takeName(SDI);
967  BO->setDebugLoc(SDI->getDebugLoc());
968  BO->setIsExact(SDI->isExact());
969  SDI->replaceAllUsesWith(BO);
970  SDI->eraseFromParent();
971 
972  return true;
973 }
974 
975 static bool processSExt(SExtInst *SDI, LazyValueInfo *LVI) {
976  if (SDI->getType()->isVectorTy())
977  return false;
978 
979  Value *Base = SDI->getOperand(0);
980 
981  if (!isNonNegative(Base, LVI, SDI))
982  return false;
983 
984  ++NumSExt;
985  auto *ZExt = CastInst::CreateZExtOrBitCast(Base, SDI->getType(), "", SDI);
986  ZExt->takeName(SDI);
987  ZExt->setDebugLoc(SDI->getDebugLoc());
988  SDI->replaceAllUsesWith(ZExt);
989  SDI->eraseFromParent();
990 
991  return true;
992 }
993 
994 static bool processBinOp(BinaryOperator *BinOp, LazyValueInfo *LVI) {
995  using OBO = OverflowingBinaryOperator;
996 
997  if (BinOp->getType()->isVectorTy())
998  return false;
999 
1000  bool NSW = BinOp->hasNoSignedWrap();
1001  bool NUW = BinOp->hasNoUnsignedWrap();
1002  if (NSW && NUW)
1003  return false;
1004 
1005  Instruction::BinaryOps Opcode = BinOp->getOpcode();
1006  Value *LHS = BinOp->getOperand(0);
1007  Value *RHS = BinOp->getOperand(1);
1008 
1009  ConstantRange LRange = LVI->getConstantRange(LHS, BinOp);
1010  ConstantRange RRange = LVI->getConstantRange(RHS, BinOp);
1011 
1012  bool Changed = false;
1013  bool NewNUW = false, NewNSW = false;
1014  if (!NUW) {
1016  Opcode, RRange, OBO::NoUnsignedWrap);
1017  NewNUW = NUWRange.contains(LRange);
1018  Changed |= NewNUW;
1019  }
1020  if (!NSW) {
1022  Opcode, RRange, OBO::NoSignedWrap);
1023  NewNSW = NSWRange.contains(LRange);
1024  Changed |= NewNSW;
1025  }
1026 
1027  setDeducedOverflowingFlags(BinOp, Opcode, NewNSW, NewNUW);
1028 
1029  return Changed;
1030 }
1031 
1032 static bool processAnd(BinaryOperator *BinOp, LazyValueInfo *LVI) {
1033  if (BinOp->getType()->isVectorTy())
1034  return false;
1035 
1036  // Pattern match (and lhs, C) where C includes a superset of bits which might
1037  // be set in lhs. This is a common truncation idiom created by instcombine.
1038  Value *LHS = BinOp->getOperand(0);
1039  ConstantInt *RHS = dyn_cast<ConstantInt>(BinOp->getOperand(1));
1040  if (!RHS || !RHS->getValue().isMask())
1041  return false;
1042 
1043  // We can only replace the AND with LHS based on range info if the range does
1044  // not include undef.
1045  ConstantRange LRange =
1046  LVI->getConstantRange(LHS, BinOp, /*UndefAllowed=*/false);
1047  if (!LRange.getUnsignedMax().ule(RHS->getValue()))
1048  return false;
1049 
1050  BinOp->replaceAllUsesWith(LHS);
1051  BinOp->eraseFromParent();
1052  NumAnd++;
1053  return true;
1054 }
1055 
1056 
1058  if (Constant *C = LVI->getConstant(V, At))
1059  return C;
1060 
1061  // TODO: The following really should be sunk inside LVI's core algorithm, or
1062  // at least the outer shims around such.
1063  auto *C = dyn_cast<CmpInst>(V);
1064  if (!C) return nullptr;
1065 
1066  Value *Op0 = C->getOperand(0);
1067  Constant *Op1 = dyn_cast<Constant>(C->getOperand(1));
1068  if (!Op1) return nullptr;
1069 
1071  C->getPredicate(), Op0, Op1, At, /*UseBlockValue=*/false);
1072  if (Result == LazyValueInfo::Unknown)
1073  return nullptr;
1074 
1075  return (Result == LazyValueInfo::True) ?
1076  ConstantInt::getTrue(C->getContext()) :
1077  ConstantInt::getFalse(C->getContext());
1078 }
1079 
1081  const SimplifyQuery &SQ) {
1082  bool FnChanged = false;
1083  // Visiting in a pre-order depth-first traversal causes us to simplify early
1084  // blocks before querying later blocks (which require us to analyze early
1085  // blocks). Eagerly simplifying shallow blocks means there is strictly less
1086  // work to do for deep blocks. This also means we don't visit unreachable
1087  // blocks.
1088  for (BasicBlock *BB : depth_first(&F.getEntryBlock())) {
1089  bool BBChanged = false;
1090  for (Instruction &II : llvm::make_early_inc_range(*BB)) {
1091  switch (II.getOpcode()) {
1092  case Instruction::Select:
1093  BBChanged |= processSelect(cast<SelectInst>(&II), LVI);
1094  break;
1095  case Instruction::PHI:
1096  BBChanged |= processPHI(cast<PHINode>(&II), LVI, DT, SQ);
1097  break;
1098  case Instruction::ICmp:
1099  case Instruction::FCmp:
1100  BBChanged |= processCmp(cast<CmpInst>(&II), LVI);
1101  break;
1102  case Instruction::Load:
1103  case Instruction::Store:
1104  BBChanged |= processMemAccess(&II, LVI);
1105  break;
1106  case Instruction::Call:
1107  case Instruction::Invoke:
1108  BBChanged |= processCallSite(cast<CallBase>(II), LVI);
1109  break;
1110  case Instruction::SRem:
1111  case Instruction::SDiv:
1112  BBChanged |= processSDivOrSRem(cast<BinaryOperator>(&II), LVI);
1113  break;
1114  case Instruction::UDiv:
1115  case Instruction::URem:
1116  BBChanged |= processUDivOrURem(cast<BinaryOperator>(&II), LVI);
1117  break;
1118  case Instruction::AShr:
1119  BBChanged |= processAShr(cast<BinaryOperator>(&II), LVI);
1120  break;
1121  case Instruction::SExt:
1122  BBChanged |= processSExt(cast<SExtInst>(&II), LVI);
1123  break;
1124  case Instruction::Add:
1125  case Instruction::Sub:
1126  case Instruction::Mul:
1127  case Instruction::Shl:
1128  BBChanged |= processBinOp(cast<BinaryOperator>(&II), LVI);
1129  break;
1130  case Instruction::And:
1131  BBChanged |= processAnd(cast<BinaryOperator>(&II), LVI);
1132  break;
1133  }
1134  }
1135 
1136  Instruction *Term = BB->getTerminator();
1137  switch (Term->getOpcode()) {
1138  case Instruction::Switch:
1139  BBChanged |= processSwitch(cast<SwitchInst>(Term), LVI, DT);
1140  break;
1141  case Instruction::Ret: {
1142  auto *RI = cast<ReturnInst>(Term);
1143  // Try to determine the return value if we can. This is mainly here to
1144  // simplify the writing of unit tests, but also helps to enable IPO by
1145  // constant folding the return values of callees.
1146  auto *RetVal = RI->getReturnValue();
1147  if (!RetVal) break; // handle "ret void"
1148  if (isa<Constant>(RetVal)) break; // nothing to do
1149  if (auto *C = getConstantAt(RetVal, RI, LVI)) {
1150  ++NumReturns;
1151  RI->replaceUsesOfWith(RetVal, C);
1152  BBChanged = true;
1153  }
1154  }
1155  }
1156 
1157  FnChanged |= BBChanged;
1158  }
1159 
1160  return FnChanged;
1161 }
1162 
1164  if (skipFunction(F))
1165  return false;
1166 
1167  LazyValueInfo *LVI = &getAnalysis<LazyValueInfoWrapperPass>().getLVI();
1168  DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1169 
1170  return runImpl(F, LVI, DT, getBestSimplifyQuery(*this, F));
1171 }
1172 
1177 
1178  bool Changed = runImpl(F, LVI, DT, getBestSimplifyQuery(AM, F));
1179 
1180  PreservedAnalyses PA;
1181  if (!Changed) {
1182  PA = PreservedAnalyses::all();
1183  } else {
1186  }
1187 
1188  // Keeping LVI alive is expensive, both because it uses a lot of memory, and
1189  // because invalidating values in LVI is expensive. While CVP does preserve
1190  // LVI, we know that passes after JumpThreading+CVP will not need the result
1191  // of this analysis, so we forcefully discard it early.
1192  PA.abandon<LazyValueAnalysis>();
1193  return PA;
1194 }
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:690
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::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:3620
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: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: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:944
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:668
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:1182
Statistic.h
llvm::BinaryOpIntrinsic::getLHS
Value * getLHS() const
Definition: IntrinsicInst.h:667
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:644
llvm::Instruction::hasNoUnsignedWrap
bool hasNoUnsignedWrap() const
Determine whether the no unsigned wrap flag is set.
Definition: Instruction.cpp:161
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:573
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:631
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:2855
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: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:875
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
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:232
llvm::BinaryOpIntrinsic::getNoWrapKind
unsigned getNoWrapKind() const
Returns one of OBO::NoSignedWrap or OBO::NoUnsignedWrap.
Definition: IntrinsicInst.cpp:723
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: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:702
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:1080
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::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:1174
willNotOverflow
static bool willNotOverflow(BinaryOpIntrinsic *BO, LazyValueInfo *LVI)
Definition: CorrelatedValuePropagation.cpp:441
llvm::MCID::Call
@ Call
Definition: MCInstrDesc.h:155
processMinMaxIntrinsic
static bool processMinMaxIntrinsic(MinMaxIntrinsic *MM, LazyValueInfo *LVI)
Definition: CorrelatedValuePropagation.cpp:558
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:563
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:1057
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: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:378
llvm::BinaryOpIntrinsic::isSigned
bool isSigned() const
Whether the intrinsic is signed or unsigned.
Definition: IntrinsicInst.cpp:710
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:1694
processBinOp
static bool processBinOp(BinaryOperator *BinOp, LazyValueInfo *LVI)
Definition: CorrelatedValuePropagation.cpp:994
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:54
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:439
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:596
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:6454
llvm::Instruction::setDebugLoc
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:351
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:1737
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:755
llvm::MinMaxIntrinsic::getLHS
Value * getLHS() const
Definition: IntrinsicInst.h:569
processSExt
static bool processSExt(SExtInst *SDI, LazyValueInfo *LVI)
Definition: CorrelatedValuePropagation.cpp:975
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:312
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_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:927
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
llvm::Instruction::isExact
bool isExact() const
Determine whether the exact flag is set.
Definition: Instruction.cpp:221
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:681
llvm::TrackingStatistic
Definition: Statistic.h:50
llvm::SExtInst
This class represents a sign extension of integer types.
Definition: Instructions.h:4889
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:342
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: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: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:6543
llvm::Type::getIntNTy
static IntegerType * getIntNTy(LLVMContext &C, unsigned N)
Definition: Type.cpp:243
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:348
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
llvm::LLVMContext::OB_deopt
@ OB_deopt
Definition: LLVMContext.h:89
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:773
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:552
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:354
processAnd
static bool processAnd(BinaryOperator *BinOp, LazyValueInfo *LVI)
Definition: CorrelatedValuePropagation.cpp:1032
llvm::Instruction::hasNoSignedWrap
bool hasNoSignedWrap() const
Determine whether the no signed wrap flag is set.
Definition: Instruction.cpp:165
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:144
llvm::PHINode
Definition: Instructions.h:2699
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:5435
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:3278
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:3287
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: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:2839
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:570
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
llvm::PoisonValue::get
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1727
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