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