LLVM  12.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"
22 #include "llvm/IR/Attributes.h"
23 #include "llvm/IR/BasicBlock.h"
24 #include "llvm/IR/CFG.h"
25 #include "llvm/IR/Constant.h"
26 #include "llvm/IR/ConstantRange.h"
27 #include "llvm/IR/Constants.h"
28 #include "llvm/IR/DerivedTypes.h"
29 #include "llvm/IR/Function.h"
30 #include "llvm/IR/IRBuilder.h"
31 #include "llvm/IR/InstrTypes.h"
32 #include "llvm/IR/Instruction.h"
33 #include "llvm/IR/Instructions.h"
34 #include "llvm/IR/IntrinsicInst.h"
35 #include "llvm/IR/Operator.h"
36 #include "llvm/IR/PassManager.h"
37 #include "llvm/IR/Type.h"
38 #include "llvm/IR/Value.h"
39 #include "llvm/InitializePasses.h"
40 #include "llvm/Pass.h"
41 #include "llvm/Support/Casting.h"
43 #include "llvm/Support/Debug.h"
45 #include "llvm/Transforms/Scalar.h"
47 #include <cassert>
48 #include <utility>
49 
50 using namespace llvm;
51 
52 #define DEBUG_TYPE "correlated-value-propagation"
53 
54 STATISTIC(NumPhis, "Number of phis propagated");
55 STATISTIC(NumPhiCommon, "Number of phis deleted via common incoming value");
56 STATISTIC(NumSelects, "Number of selects propagated");
57 STATISTIC(NumMemAccess, "Number of memory access targets propagated");
58 STATISTIC(NumCmps, "Number of comparisons propagated");
59 STATISTIC(NumReturns, "Number of return values propagated");
60 STATISTIC(NumDeadCases, "Number of switch cases removed");
61 STATISTIC(NumSDivSRemsNarrowed,
62  "Number of sdivs/srems whose width was decreased");
63 STATISTIC(NumSDivs, "Number of sdiv converted to udiv");
64 STATISTIC(NumUDivURemsNarrowed,
65  "Number of udivs/urems whose width was decreased");
66 STATISTIC(NumAShrs, "Number of ashr converted to lshr");
67 STATISTIC(NumSRems, "Number of srem converted to urem");
68 STATISTIC(NumSExt, "Number of sext converted to zext");
69 STATISTIC(NumAnd, "Number of ands removed");
70 STATISTIC(NumNW, "Number of no-wrap deductions");
71 STATISTIC(NumNSW, "Number of no-signed-wrap deductions");
72 STATISTIC(NumNUW, "Number of no-unsigned-wrap deductions");
73 STATISTIC(NumAddNW, "Number of no-wrap deductions for add");
74 STATISTIC(NumAddNSW, "Number of no-signed-wrap deductions for add");
75 STATISTIC(NumAddNUW, "Number of no-unsigned-wrap deductions for add");
76 STATISTIC(NumSubNW, "Number of no-wrap deductions for sub");
77 STATISTIC(NumSubNSW, "Number of no-signed-wrap deductions for sub");
78 STATISTIC(NumSubNUW, "Number of no-unsigned-wrap deductions for sub");
79 STATISTIC(NumMulNW, "Number of no-wrap deductions for mul");
80 STATISTIC(NumMulNSW, "Number of no-signed-wrap deductions for mul");
81 STATISTIC(NumMulNUW, "Number of no-unsigned-wrap deductions for mul");
82 STATISTIC(NumShlNW, "Number of no-wrap deductions for shl");
83 STATISTIC(NumShlNSW, "Number of no-signed-wrap deductions for shl");
84 STATISTIC(NumShlNUW, "Number of no-unsigned-wrap deductions for shl");
85 STATISTIC(NumOverflows, "Number of overflow checks removed");
86 STATISTIC(NumSaturating,
87  "Number of saturating arithmetics converted to normal arithmetics");
88 
89 static cl::opt<bool> DontAddNoWrapFlags("cvp-dont-add-nowrap-flags", cl::init(false));
90 
91 namespace {
92 
93  class CorrelatedValuePropagation : public FunctionPass {
94  public:
95  static char ID;
96 
97  CorrelatedValuePropagation(): FunctionPass(ID) {
99  }
100 
101  bool runOnFunction(Function &F) override;
102 
103  void getAnalysisUsage(AnalysisUsage &AU) const override {
109  }
110  };
111 
112 } // end anonymous namespace
113 
115 
116 INITIALIZE_PASS_BEGIN(CorrelatedValuePropagation, "correlated-propagation",
117  "Value Propagation", false, false)
120 INITIALIZE_PASS_END(CorrelatedValuePropagation, "correlated-propagation",
121  "Value Propagation", false, false)
122 
123 // Public interface to the Value Propagation pass
125  return new CorrelatedValuePropagation();
126 }
127 
128 static bool processSelect(SelectInst *S, LazyValueInfo *LVI) {
129  if (S->getType()->isVectorTy()) return false;
130  if (isa<Constant>(S->getCondition())) return false;
131 
132  Constant *C = LVI->getConstant(S->getCondition(), S);
133  if (!C) return false;
134 
136  if (!CI) return false;
137 
138  Value *ReplaceWith = CI->isOne() ? S->getTrueValue() : S->getFalseValue();
139  S->replaceAllUsesWith(ReplaceWith);
140  S->eraseFromParent();
141 
142  ++NumSelects;
143 
144  return true;
145 }
146 
147 /// Try to simplify a phi with constant incoming values that match the edge
148 /// values of a non-constant value on all other edges:
149 /// bb0:
150 /// %isnull = icmp eq i8* %x, null
151 /// br i1 %isnull, label %bb2, label %bb1
152 /// bb1:
153 /// br label %bb2
154 /// bb2:
155 /// %r = phi i8* [ %x, %bb1 ], [ null, %bb0 ]
156 /// -->
157 /// %r = %x
159  DominatorTree *DT) {
160  // Collect incoming constants and initialize possible common value.
161  SmallVector<std::pair<Constant *, unsigned>, 4> IncomingConstants;
162  Value *CommonValue = nullptr;
163  for (unsigned i = 0, e = P->getNumIncomingValues(); i != e; ++i) {
164  Value *Incoming = P->getIncomingValue(i);
165  if (auto *IncomingConstant = dyn_cast<Constant>(Incoming)) {
166  IncomingConstants.push_back(std::make_pair(IncomingConstant, i));
167  } else if (!CommonValue) {
168  // The potential common value is initialized to the first non-constant.
169  CommonValue = Incoming;
170  } else if (Incoming != CommonValue) {
171  // There can be only one non-constant common value.
172  return false;
173  }
174  }
175 
176  if (!CommonValue || IncomingConstants.empty())
177  return false;
178 
179  // The common value must be valid in all incoming blocks.
180  BasicBlock *ToBB = P->getParent();
181  if (auto *CommonInst = dyn_cast<Instruction>(CommonValue))
182  if (!DT->dominates(CommonInst, ToBB))
183  return false;
184 
185  // We have a phi with exactly 1 variable incoming value and 1 or more constant
186  // incoming values. See if all constant incoming values can be mapped back to
187  // the same incoming variable value.
188  for (auto &IncomingConstant : IncomingConstants) {
189  Constant *C = IncomingConstant.first;
190  BasicBlock *IncomingBB = P->getIncomingBlock(IncomingConstant.second);
191  if (C != LVI->getConstantOnEdge(CommonValue, IncomingBB, ToBB, P))
192  return false;
193  }
194 
195  // All constant incoming values map to the same variable along the incoming
196  // edges of the phi. The phi is unnecessary. However, we must drop all
197  // poison-generating flags to ensure that no poison is propagated to the phi
198  // location by performing this substitution.
199  // Warning: If the underlying analysis changes, this may not be enough to
200  // guarantee that poison is not propagated.
201  // TODO: We may be able to re-infer flags by re-analyzing the instruction.
202  if (auto *CommonInst = dyn_cast<Instruction>(CommonValue))
203  CommonInst->dropPoisonGeneratingFlags();
204  P->replaceAllUsesWith(CommonValue);
205  P->eraseFromParent();
206  ++NumPhiCommon;
207  return true;
208 }
209 
211  const SimplifyQuery &SQ) {
212  bool Changed = false;
213 
214  BasicBlock *BB = P->getParent();
215  for (unsigned i = 0, e = P->getNumIncomingValues(); i < e; ++i) {
216  Value *Incoming = P->getIncomingValue(i);
217  if (isa<Constant>(Incoming)) continue;
218 
219  Value *V = LVI->getConstantOnEdge(Incoming, P->getIncomingBlock(i), BB, P);
220 
221  // Look if the incoming value is a select with a scalar condition for which
222  // LVI can tells us the value. In that case replace the incoming value with
223  // the appropriate value of the select. This often allows us to remove the
224  // select later.
225  if (!V) {
226  SelectInst *SI = dyn_cast<SelectInst>(Incoming);
227  if (!SI) continue;
228 
229  Value *Condition = SI->getCondition();
230  if (!Condition->getType()->isVectorTy()) {
231  if (Constant *C = LVI->getConstantOnEdge(
232  Condition, P->getIncomingBlock(i), BB, P)) {
233  if (C->isOneValue()) {
234  V = SI->getTrueValue();
235  } else if (C->isZeroValue()) {
236  V = SI->getFalseValue();
237  }
238  // Once LVI learns to handle vector types, we could also add support
239  // for vector type constants that are not all zeroes or all ones.
240  }
241  }
242 
243  // Look if the select has a constant but LVI tells us that the incoming
244  // value can never be that constant. In that case replace the incoming
245  // value with the other value of the select. This often allows us to
246  // remove the select later.
247  if (!V) {
249  if (!C) continue;
250 
251  if (LVI->getPredicateOnEdge(ICmpInst::ICMP_EQ, SI, C,
252  P->getIncomingBlock(i), BB, P) !=
254  continue;
255  V = SI->getTrueValue();
256  }
257 
258  LLVM_DEBUG(dbgs() << "CVP: Threading PHI over " << *SI << '\n');
259  }
260 
261  P->setIncomingValue(i, V);
262  Changed = true;
263  }
264 
265  if (Value *V = SimplifyInstruction(P, SQ)) {
266  P->replaceAllUsesWith(V);
267  P->eraseFromParent();
268  Changed = true;
269  }
270 
271  if (!Changed)
272  Changed = simplifyCommonValuePhi(P, LVI, DT);
273 
274  if (Changed)
275  ++NumPhis;
276 
277  return Changed;
278 }
279 
281  Value *Pointer = nullptr;
282  if (LoadInst *L = dyn_cast<LoadInst>(I))
283  Pointer = L->getPointerOperand();
284  else
285  Pointer = cast<StoreInst>(I)->getPointerOperand();
286 
287  if (isa<Constant>(Pointer)) return false;
288 
289  Constant *C = LVI->getConstant(Pointer, I);
290  if (!C) return false;
291 
292  ++NumMemAccess;
293  I->replaceUsesOfWith(Pointer, C);
294  return true;
295 }
296 
297 /// See if LazyValueInfo's ability to exploit edge conditions or range
298 /// information is sufficient to prove this comparison. Even for local
299 /// conditions, this can sometimes prove conditions instcombine can't by
300 /// exploiting range information.
301 static bool processCmp(CmpInst *Cmp, LazyValueInfo *LVI) {
302  Value *Op0 = Cmp->getOperand(0);
303  auto *C = dyn_cast<Constant>(Cmp->getOperand(1));
304  if (!C)
305  return false;
306 
307  LazyValueInfo::Tristate Result =
308  LVI->getPredicateAt(Cmp->getPredicate(), Op0, C, Cmp,
309  /*UseBlockValue=*/true);
310  if (Result == LazyValueInfo::Unknown)
311  return false;
312 
313  ++NumCmps;
314  Constant *TorF = ConstantInt::get(Type::getInt1Ty(Cmp->getContext()), Result);
315  Cmp->replaceAllUsesWith(TorF);
316  Cmp->eraseFromParent();
317  return true;
318 }
319 
320 /// Simplify a switch instruction by removing cases which can never fire. If the
321 /// uselessness of a case could be determined locally then constant propagation
322 /// would already have figured it out. Instead, walk the predecessors and
323 /// statically evaluate cases based on information available on that edge. Cases
324 /// that cannot fire no matter what the incoming edge can safely be removed. If
325 /// a case fires on every incoming edge then the entire switch can be removed
326 /// and replaced with a branch to the case destination.
328  DominatorTree *DT) {
330  Value *Cond = I->getCondition();
331  BasicBlock *BB = I->getParent();
332 
333  // If the condition was defined in same block as the switch then LazyValueInfo
334  // currently won't say anything useful about it, though in theory it could.
335  if (isa<Instruction>(Cond) && cast<Instruction>(Cond)->getParent() == BB)
336  return false;
337 
338  // If the switch is unreachable then trying to improve it is a waste of time.
339  pred_iterator PB = pred_begin(BB), PE = pred_end(BB);
340  if (PB == PE) return false;
341 
342  // Analyse each switch case in turn.
343  bool Changed = false;
344  DenseMap<BasicBlock*, int> SuccessorsCount;
345  for (auto *Succ : successors(BB))
346  SuccessorsCount[Succ]++;
347 
348  { // Scope for SwitchInstProfUpdateWrapper. It must not live during
349  // ConstantFoldTerminator() as the underlying SwitchInst can be changed.
351 
352  for (auto CI = SI->case_begin(), CE = SI->case_end(); CI != CE;) {
353  ConstantInt *Case = CI->getCaseValue();
354 
355  // Check to see if the switch condition is equal to/not equal to the case
356  // value on every incoming edge, equal/not equal being the same each time.
358  for (pred_iterator PI = PB; PI != PE; ++PI) {
359  // Is the switch condition equal to the case value?
361  Cond, Case, *PI,
362  BB, SI);
363  // Give up on this case if nothing is known.
364  if (Value == LazyValueInfo::Unknown) {
365  State = LazyValueInfo::Unknown;
366  break;
367  }
368 
369  // If this was the first edge to be visited, record that all other edges
370  // need to give the same result.
371  if (PI == PB) {
372  State = Value;
373  continue;
374  }
375 
376  // If this case is known to fire for some edges and known not to fire for
377  // others then there is nothing we can do - give up.
378  if (Value != State) {
379  State = LazyValueInfo::Unknown;
380  break;
381  }
382  }
383 
384  if (State == LazyValueInfo::False) {
385  // This case never fires - remove it.
386  BasicBlock *Succ = CI->getCaseSuccessor();
387  Succ->removePredecessor(BB);
388  CI = SI.removeCase(CI);
389  CE = SI->case_end();
390 
391  // The condition can be modified by removePredecessor's PHI simplification
392  // logic.
393  Cond = SI->getCondition();
394 
395  ++NumDeadCases;
396  Changed = true;
397  if (--SuccessorsCount[Succ] == 0)
399  continue;
400  }
401  if (State == LazyValueInfo::True) {
402  // This case always fires. Arrange for the switch to be turned into an
403  // unconditional branch by replacing the switch condition with the case
404  // value.
405  SI->setCondition(Case);
406  NumDeadCases += SI->getNumCases();
407  Changed = true;
408  break;
409  }
410 
411  // Increment the case iterator since we didn't delete it.
412  ++CI;
413  }
414  }
415 
416  if (Changed)
417  // If the switch has been simplified to the point where it can be replaced
418  // by a branch then do so now.
419  ConstantFoldTerminator(BB, /*DeleteDeadConditions = */ false,
420  /*TLI = */ nullptr, &DTU);
421  return Changed;
422 }
423 
424 // See if we can prove that the given binary op intrinsic will not overflow.
426  ConstantRange LRange = LVI->getConstantRange(BO->getLHS(), BO);
427  ConstantRange RRange = LVI->getConstantRange(BO->getRHS(), BO);
429  BO->getBinaryOp(), RRange, BO->getNoWrapKind());
430  return NWRegion.contains(LRange);
431 }
432 
434  bool NewNSW, bool NewNUW) {
435  Statistic *OpcNW, *OpcNSW, *OpcNUW;
436  switch (Opcode) {
437  case Instruction::Add:
438  OpcNW = &NumAddNW;
439  OpcNSW = &NumAddNSW;
440  OpcNUW = &NumAddNUW;
441  break;
442  case Instruction::Sub:
443  OpcNW = &NumSubNW;
444  OpcNSW = &NumSubNSW;
445  OpcNUW = &NumSubNUW;
446  break;
447  case Instruction::Mul:
448  OpcNW = &NumMulNW;
449  OpcNSW = &NumMulNSW;
450  OpcNUW = &NumMulNUW;
451  break;
452  case Instruction::Shl:
453  OpcNW = &NumShlNW;
454  OpcNSW = &NumShlNSW;
455  OpcNUW = &NumShlNUW;
456  break;
457  default:
458  llvm_unreachable("Will not be called with other binops");
459  }
460 
461  auto *Inst = dyn_cast<Instruction>(V);
462  if (NewNSW) {
463  ++NumNW;
464  ++*OpcNW;
465  ++NumNSW;
466  ++*OpcNSW;
467  if (Inst)
468  Inst->setHasNoSignedWrap();
469  }
470  if (NewNUW) {
471  ++NumNW;
472  ++*OpcNW;
473  ++NumNUW;
474  ++*OpcNUW;
475  if (Inst)
476  Inst->setHasNoUnsignedWrap();
477  }
478 }
479 
480 static bool processBinOp(BinaryOperator *BinOp, LazyValueInfo *LVI);
481 
482 // Rewrite this with.overflow intrinsic as non-overflowing.
484  IRBuilder<> B(WO);
485  Instruction::BinaryOps Opcode = WO->getBinaryOp();
486  bool NSW = WO->isSigned();
487  bool NUW = !WO->isSigned();
488 
489  Value *NewOp =
490  B.CreateBinOp(Opcode, WO->getLHS(), WO->getRHS(), WO->getName());
491  setDeducedOverflowingFlags(NewOp, Opcode, NSW, NUW);
492 
493  StructType *ST = cast<StructType>(WO->getType());
494  Constant *Struct = ConstantStruct::get(ST,
497  Value *NewI = B.CreateInsertValue(Struct, NewOp, 0);
498  WO->replaceAllUsesWith(NewI);
499  WO->eraseFromParent();
500  ++NumOverflows;
501 
502  // See if we can infer the other no-wrap too.
503  if (auto *BO = dyn_cast<BinaryOperator>(NewOp))
504  processBinOp(BO, LVI);
505 }
506 
508  Instruction::BinaryOps Opcode = SI->getBinaryOp();
509  bool NSW = SI->isSigned();
510  bool NUW = !SI->isSigned();
512  Opcode, SI->getLHS(), SI->getRHS(), SI->getName(), SI);
513  BinOp->setDebugLoc(SI->getDebugLoc());
514  setDeducedOverflowingFlags(BinOp, Opcode, NSW, NUW);
515 
516  SI->replaceAllUsesWith(BinOp);
517  SI->eraseFromParent();
518  ++NumSaturating;
519 
520  // See if we can infer the other no-wrap too.
521  if (auto *BO = dyn_cast<BinaryOperator>(BinOp))
522  processBinOp(BO, LVI);
523 }
524 
525 /// Infer nonnull attributes for the arguments at the specified callsite.
526 static bool processCallSite(CallBase &CB, LazyValueInfo *LVI) {
527 
528  if (auto *WO = dyn_cast<WithOverflowInst>(&CB)) {
529  if (WO->getLHS()->getType()->isIntegerTy() && willNotOverflow(WO, LVI)) {
530  processOverflowIntrinsic(WO, LVI);
531  return true;
532  }
533  }
534 
535  if (auto *SI = dyn_cast<SaturatingInst>(&CB)) {
536  if (SI->getType()->isIntegerTy() && willNotOverflow(SI, LVI)) {
538  return true;
539  }
540  }
541 
542  bool Changed = false;
543 
544  // Deopt bundle operands are intended to capture state with minimal
545  // perturbance of the code otherwise. If we can find a constant value for
546  // any such operand and remove a use of the original value, that's
547  // desireable since it may allow further optimization of that value (e.g. via
548  // single use rules in instcombine). Since deopt uses tend to,
549  // idiomatically, appear along rare conditional paths, it's reasonable likely
550  // we may have a conditional fact with which LVI can fold.
551  if (auto DeoptBundle = CB.getOperandBundle(LLVMContext::OB_deopt)) {
552  for (const Use &ConstU : DeoptBundle->Inputs) {
553  Use &U = const_cast<Use&>(ConstU);
554  Value *V = U.get();
555  if (V->getType()->isVectorTy()) continue;
556  if (isa<Constant>(V)) continue;
557 
558  Constant *C = LVI->getConstant(V, &CB);
559  if (!C) continue;
560  U.set(C);
561  Changed = true;
562  }
563  }
564 
566  unsigned ArgNo = 0;
567 
568  for (Value *V : CB.args()) {
569  PointerType *Type = dyn_cast<PointerType>(V->getType());
570  // Try to mark pointer typed parameters as non-null. We skip the
571  // relatively expensive analysis for constants which are obviously either
572  // null or non-null to start with.
573  if (Type && !CB.paramHasAttr(ArgNo, Attribute::NonNull) &&
574  !isa<Constant>(V) &&
577  &CB) == LazyValueInfo::False)
578  ArgNos.push_back(ArgNo);
579  ArgNo++;
580  }
581 
582  assert(ArgNo == CB.arg_size() && "sanity check");
583 
584  if (ArgNos.empty())
585  return Changed;
586 
587  AttributeList AS = CB.getAttributes();
588  LLVMContext &Ctx = CB.getContext();
589  AS = AS.addParamAttribute(Ctx, ArgNos,
590  Attribute::get(Ctx, Attribute::NonNull));
591  CB.setAttributes(AS);
592 
593  return true;
594 }
595 
596 static bool isNonNegative(Value *V, LazyValueInfo *LVI, Instruction *CxtI) {
597  Constant *Zero = ConstantInt::get(V->getType(), 0);
598  auto Result = LVI->getPredicateAt(ICmpInst::ICMP_SGE, V, Zero, CxtI);
599  return Result == LazyValueInfo::True;
600 }
601 
602 static bool isNonPositive(Value *V, LazyValueInfo *LVI, Instruction *CxtI) {
603  Constant *Zero = ConstantInt::get(V->getType(), 0);
604  auto Result = LVI->getPredicateAt(ICmpInst::ICMP_SLE, V, Zero, CxtI);
605  return Result == LazyValueInfo::True;
606 }
607 
609 
611  if (isNonNegative(V, LVI, CxtI))
612  return Domain::NonNegative;
613  if (isNonPositive(V, LVI, CxtI))
614  return Domain::NonPositive;
615  return Domain::Unknown;
616 }
617 
618 /// Try to shrink a sdiv/srem's width down to the smallest power of two that's
619 /// sufficient to contain its operands.
620 static bool narrowSDivOrSRem(BinaryOperator *Instr, LazyValueInfo *LVI) {
621  assert(Instr->getOpcode() == Instruction::SDiv ||
622  Instr->getOpcode() == Instruction::SRem);
623  if (Instr->getType()->isVectorTy())
624  return false;
625 
626  // Find the smallest power of two bitwidth that's sufficient to hold Instr's
627  // operands.
628  unsigned OrigWidth = Instr->getType()->getIntegerBitWidth();
629 
630  // What is the smallest bit width that can accomodate the entire value ranges
631  // of both of the operands?
632  std::array<Optional<ConstantRange>, 2> CRs;
633  unsigned MinSignedBits = 0;
634  for (auto I : zip(Instr->operands(), CRs)) {
635  std::get<1>(I) = LVI->getConstantRange(std::get<0>(I), Instr);
636  MinSignedBits = std::max(std::get<1>(I)->getMinSignedBits(), MinSignedBits);
637  }
638 
639  // sdiv/srem is UB if divisor is -1 and divident is INT_MIN, so unless we can
640  // prove that such a combination is impossible, we need to bump the bitwidth.
641  if (CRs[1]->contains(APInt::getAllOnesValue(OrigWidth)) &&
642  CRs[0]->contains(
643  APInt::getSignedMinValue(MinSignedBits).sextOrSelf(OrigWidth)))
644  ++MinSignedBits;
645 
646  // Don't shrink below 8 bits wide.
647  unsigned NewWidth = std::max<unsigned>(PowerOf2Ceil(MinSignedBits), 8);
648 
649  // NewWidth might be greater than OrigWidth if OrigWidth is not a power of
650  // two.
651  if (NewWidth >= OrigWidth)
652  return false;
653 
654  ++NumSDivSRemsNarrowed;
655  IRBuilder<> B{Instr};
656  auto *TruncTy = Type::getIntNTy(Instr->getContext(), NewWidth);
657  auto *LHS = B.CreateTruncOrBitCast(Instr->getOperand(0), TruncTy,
658  Instr->getName() + ".lhs.trunc");
659  auto *RHS = B.CreateTruncOrBitCast(Instr->getOperand(1), TruncTy,
660  Instr->getName() + ".rhs.trunc");
661  auto *BO = B.CreateBinOp(Instr->getOpcode(), LHS, RHS, Instr->getName());
662  auto *Sext = B.CreateSExt(BO, Instr->getType(), Instr->getName() + ".sext");
663  if (auto *BinOp = dyn_cast<BinaryOperator>(BO))
664  if (BinOp->getOpcode() == Instruction::SDiv)
665  BinOp->setIsExact(Instr->isExact());
666 
667  Instr->replaceAllUsesWith(Sext);
668  Instr->eraseFromParent();
669  return true;
670 }
671 
672 /// Try to shrink a udiv/urem's width down to the smallest power of two that's
673 /// sufficient to contain its operands.
674 static bool processUDivOrURem(BinaryOperator *Instr, LazyValueInfo *LVI) {
675  assert(Instr->getOpcode() == Instruction::UDiv ||
676  Instr->getOpcode() == Instruction::URem);
677  if (Instr->getType()->isVectorTy())
678  return false;
679 
680  // Find the smallest power of two bitwidth that's sufficient to hold Instr's
681  // operands.
682 
683  // What is the smallest bit width that can accomodate the entire value ranges
684  // of both of the operands?
685  unsigned MaxActiveBits = 0;
686  for (Value *Operand : Instr->operands()) {
687  ConstantRange CR = LVI->getConstantRange(Operand, Instr);
688  MaxActiveBits = std::max(CR.getActiveBits(), MaxActiveBits);
689  }
690  // Don't shrink below 8 bits wide.
691  unsigned NewWidth = std::max<unsigned>(PowerOf2Ceil(MaxActiveBits), 8);
692 
693  // NewWidth might be greater than OrigWidth if OrigWidth is not a power of
694  // two.
695  if (NewWidth >= Instr->getType()->getIntegerBitWidth())
696  return false;
697 
698  ++NumUDivURemsNarrowed;
699  IRBuilder<> B{Instr};
700  auto *TruncTy = Type::getIntNTy(Instr->getContext(), NewWidth);
701  auto *LHS = B.CreateTruncOrBitCast(Instr->getOperand(0), TruncTy,
702  Instr->getName() + ".lhs.trunc");
703  auto *RHS = B.CreateTruncOrBitCast(Instr->getOperand(1), TruncTy,
704  Instr->getName() + ".rhs.trunc");
705  auto *BO = B.CreateBinOp(Instr->getOpcode(), LHS, RHS, Instr->getName());
706  auto *Zext = B.CreateZExt(BO, Instr->getType(), Instr->getName() + ".zext");
707  if (auto *BinOp = dyn_cast<BinaryOperator>(BO))
708  if (BinOp->getOpcode() == Instruction::UDiv)
709  BinOp->setIsExact(Instr->isExact());
710 
711  Instr->replaceAllUsesWith(Zext);
712  Instr->eraseFromParent();
713  return true;
714 }
715 
716 static bool processSRem(BinaryOperator *SDI, LazyValueInfo *LVI) {
717  assert(SDI->getOpcode() == Instruction::SRem);
718  if (SDI->getType()->isVectorTy())
719  return false;
720 
721  struct Operand {
722  Value *V;
723  Domain D;
724  };
725  std::array<Operand, 2> Ops;
726 
727  for (const auto I : zip(Ops, SDI->operands())) {
728  Operand &Op = std::get<0>(I);
729  Op.V = std::get<1>(I);
730  Op.D = getDomain(Op.V, LVI, SDI);
731  if (Op.D == Domain::Unknown)
732  return false;
733  }
734 
735  // We know domains of both of the operands!
736  ++NumSRems;
737 
738  // We need operands to be non-negative, so negate each one that isn't.
739  for (Operand &Op : Ops) {
740  if (Op.D == Domain::NonNegative)
741  continue;
742  auto *BO =
743  BinaryOperator::CreateNeg(Op.V, Op.V->getName() + ".nonneg", SDI);
744  BO->setDebugLoc(SDI->getDebugLoc());
745  Op.V = BO;
746  }
747 
748  auto *URem =
749  BinaryOperator::CreateURem(Ops[0].V, Ops[1].V, SDI->getName(), SDI);
750  URem->setDebugLoc(SDI->getDebugLoc());
751 
752  Value *Res = URem;
753 
754  // If the divident was non-positive, we need to negate the result.
755  if (Ops[0].D == Domain::NonPositive)
756  Res = BinaryOperator::CreateNeg(Res, Res->getName() + ".neg", SDI);
757 
758  SDI->replaceAllUsesWith(Res);
759  SDI->eraseFromParent();
760 
761  // Try to simplify our new urem.
762  processUDivOrURem(URem, LVI);
763 
764  return true;
765 }
766 
767 /// See if LazyValueInfo's ability to exploit edge conditions or range
768 /// information is sufficient to prove the signs of both operands of this SDiv.
769 /// If this is the case, replace the SDiv with a UDiv. Even for local
770 /// conditions, this can sometimes prove conditions instcombine can't by
771 /// exploiting range information.
772 static bool processSDiv(BinaryOperator *SDI, LazyValueInfo *LVI) {
773  assert(SDI->getOpcode() == Instruction::SDiv);
774  if (SDI->getType()->isVectorTy())
775  return false;
776 
777  struct Operand {
778  Value *V;
779  Domain D;
780  };
781  std::array<Operand, 2> Ops;
782 
783  for (const auto I : zip(Ops, SDI->operands())) {
784  Operand &Op = std::get<0>(I);
785  Op.V = std::get<1>(I);
786  Op.D = getDomain(Op.V, LVI, SDI);
787  if (Op.D == Domain::Unknown)
788  return false;
789  }
790 
791  // We know domains of both of the operands!
792  ++NumSDivs;
793 
794  // We need operands to be non-negative, so negate each one that isn't.
795  for (Operand &Op : Ops) {
796  if (Op.D == Domain::NonNegative)
797  continue;
798  auto *BO =
799  BinaryOperator::CreateNeg(Op.V, Op.V->getName() + ".nonneg", SDI);
800  BO->setDebugLoc(SDI->getDebugLoc());
801  Op.V = BO;
802  }
803 
804  auto *UDiv =
805  BinaryOperator::CreateUDiv(Ops[0].V, Ops[1].V, SDI->getName(), SDI);
806  UDiv->setDebugLoc(SDI->getDebugLoc());
807  UDiv->setIsExact(SDI->isExact());
808 
809  Value *Res = UDiv;
810 
811  // If the operands had two different domains, we need to negate the result.
812  if (Ops[0].D != Ops[1].D)
813  Res = BinaryOperator::CreateNeg(Res, Res->getName() + ".neg", SDI);
814 
815  SDI->replaceAllUsesWith(Res);
816  SDI->eraseFromParent();
817 
818  // Try to simplify our new udiv.
819  processUDivOrURem(UDiv, LVI);
820 
821  return true;
822 }
823 
824 static bool processSDivOrSRem(BinaryOperator *Instr, LazyValueInfo *LVI) {
825  assert(Instr->getOpcode() == Instruction::SDiv ||
826  Instr->getOpcode() == Instruction::SRem);
827  if (Instr->getType()->isVectorTy())
828  return false;
829 
830  if (Instr->getOpcode() == Instruction::SDiv)
831  if (processSDiv(Instr, LVI))
832  return true;
833 
834  if (Instr->getOpcode() == Instruction::SRem)
835  if (processSRem(Instr, LVI))
836  return true;
837 
838  return narrowSDivOrSRem(Instr, LVI);
839 }
840 
841 static bool processAShr(BinaryOperator *SDI, LazyValueInfo *LVI) {
842  if (SDI->getType()->isVectorTy())
843  return false;
844 
845  if (!isNonNegative(SDI->getOperand(0), LVI, SDI))
846  return false;
847 
848  ++NumAShrs;
849  auto *BO = BinaryOperator::CreateLShr(SDI->getOperand(0), SDI->getOperand(1),
850  SDI->getName(), SDI);
851  BO->setDebugLoc(SDI->getDebugLoc());
852  BO->setIsExact(SDI->isExact());
853  SDI->replaceAllUsesWith(BO);
854  SDI->eraseFromParent();
855 
856  return true;
857 }
858 
859 static bool processSExt(SExtInst *SDI, LazyValueInfo *LVI) {
860  if (SDI->getType()->isVectorTy())
861  return false;
862 
863  Value *Base = SDI->getOperand(0);
864 
865  if (!isNonNegative(Base, LVI, SDI))
866  return false;
867 
868  ++NumSExt;
869  auto *ZExt =
870  CastInst::CreateZExtOrBitCast(Base, SDI->getType(), SDI->getName(), SDI);
871  ZExt->setDebugLoc(SDI->getDebugLoc());
872  SDI->replaceAllUsesWith(ZExt);
873  SDI->eraseFromParent();
874 
875  return true;
876 }
877 
878 static bool processBinOp(BinaryOperator *BinOp, LazyValueInfo *LVI) {
879  using OBO = OverflowingBinaryOperator;
880 
881  if (DontAddNoWrapFlags)
882  return false;
883 
884  if (BinOp->getType()->isVectorTy())
885  return false;
886 
887  bool NSW = BinOp->hasNoSignedWrap();
888  bool NUW = BinOp->hasNoUnsignedWrap();
889  if (NSW && NUW)
890  return false;
891 
892  Instruction::BinaryOps Opcode = BinOp->getOpcode();
893  Value *LHS = BinOp->getOperand(0);
894  Value *RHS = BinOp->getOperand(1);
895 
896  ConstantRange LRange = LVI->getConstantRange(LHS, BinOp);
897  ConstantRange RRange = LVI->getConstantRange(RHS, BinOp);
898 
899  bool Changed = false;
900  bool NewNUW = false, NewNSW = false;
901  if (!NUW) {
903  Opcode, RRange, OBO::NoUnsignedWrap);
904  NewNUW = NUWRange.contains(LRange);
905  Changed |= NewNUW;
906  }
907  if (!NSW) {
909  Opcode, RRange, OBO::NoSignedWrap);
910  NewNSW = NSWRange.contains(LRange);
911  Changed |= NewNSW;
912  }
913 
914  setDeducedOverflowingFlags(BinOp, Opcode, NewNSW, NewNUW);
915 
916  return Changed;
917 }
918 
919 static bool processAnd(BinaryOperator *BinOp, LazyValueInfo *LVI) {
920  if (BinOp->getType()->isVectorTy())
921  return false;
922 
923  // Pattern match (and lhs, C) where C includes a superset of bits which might
924  // be set in lhs. This is a common truncation idiom created by instcombine.
925  Value *LHS = BinOp->getOperand(0);
926  ConstantInt *RHS = dyn_cast<ConstantInt>(BinOp->getOperand(1));
927  if (!RHS || !RHS->getValue().isMask())
928  return false;
929 
930  // We can only replace the AND with LHS based on range info if the range does
931  // not include undef.
932  ConstantRange LRange =
933  LVI->getConstantRange(LHS, BinOp, /*UndefAllowed=*/false);
934  if (!LRange.getUnsignedMax().ule(RHS->getValue()))
935  return false;
936 
937  BinOp->replaceAllUsesWith(LHS);
938  BinOp->eraseFromParent();
939  NumAnd++;
940  return true;
941 }
942 
943 
945  if (Constant *C = LVI->getConstant(V, At))
946  return C;
947 
948  // TODO: The following really should be sunk inside LVI's core algorithm, or
949  // at least the outer shims around such.
950  auto *C = dyn_cast<CmpInst>(V);
951  if (!C) return nullptr;
952 
953  Value *Op0 = C->getOperand(0);
954  Constant *Op1 = dyn_cast<Constant>(C->getOperand(1));
955  if (!Op1) return nullptr;
956 
957  LazyValueInfo::Tristate Result =
958  LVI->getPredicateAt(C->getPredicate(), Op0, Op1, At);
959  if (Result == LazyValueInfo::Unknown)
960  return nullptr;
961 
962  return (Result == LazyValueInfo::True) ?
965 }
966 
967 static bool runImpl(Function &F, LazyValueInfo *LVI, DominatorTree *DT,
968  const SimplifyQuery &SQ) {
969  bool FnChanged = false;
970  // Visiting in a pre-order depth-first traversal causes us to simplify early
971  // blocks before querying later blocks (which require us to analyze early
972  // blocks). Eagerly simplifying shallow blocks means there is strictly less
973  // work to do for deep blocks. This also means we don't visit unreachable
974  // blocks.
975  for (BasicBlock *BB : depth_first(&F.getEntryBlock())) {
976  bool BBChanged = false;
977  for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) {
978  Instruction *II = &*BI++;
979  switch (II->getOpcode()) {
980  case Instruction::Select:
981  BBChanged |= processSelect(cast<SelectInst>(II), LVI);
982  break;
983  case Instruction::PHI:
984  BBChanged |= processPHI(cast<PHINode>(II), LVI, DT, SQ);
985  break;
986  case Instruction::ICmp:
987  case Instruction::FCmp:
988  BBChanged |= processCmp(cast<CmpInst>(II), LVI);
989  break;
990  case Instruction::Load:
991  case Instruction::Store:
992  BBChanged |= processMemAccess(II, LVI);
993  break;
994  case Instruction::Call:
995  case Instruction::Invoke:
996  BBChanged |= processCallSite(cast<CallBase>(*II), LVI);
997  break;
998  case Instruction::SRem:
999  case Instruction::SDiv:
1000  BBChanged |= processSDivOrSRem(cast<BinaryOperator>(II), LVI);
1001  break;
1002  case Instruction::UDiv:
1003  case Instruction::URem:
1004  BBChanged |= processUDivOrURem(cast<BinaryOperator>(II), LVI);
1005  break;
1006  case Instruction::AShr:
1007  BBChanged |= processAShr(cast<BinaryOperator>(II), LVI);
1008  break;
1009  case Instruction::SExt:
1010  BBChanged |= processSExt(cast<SExtInst>(II), LVI);
1011  break;
1012  case Instruction::Add:
1013  case Instruction::Sub:
1014  case Instruction::Mul:
1015  case Instruction::Shl:
1016  BBChanged |= processBinOp(cast<BinaryOperator>(II), LVI);
1017  break;
1018  case Instruction::And:
1019  BBChanged |= processAnd(cast<BinaryOperator>(II), LVI);
1020  break;
1021  }
1022  }
1023 
1024  Instruction *Term = BB->getTerminator();
1025  switch (Term->getOpcode()) {
1026  case Instruction::Switch:
1027  BBChanged |= processSwitch(cast<SwitchInst>(Term), LVI, DT);
1028  break;
1029  case Instruction::Ret: {
1030  auto *RI = cast<ReturnInst>(Term);
1031  // Try to determine the return value if we can. This is mainly here to
1032  // simplify the writing of unit tests, but also helps to enable IPO by
1033  // constant folding the return values of callees.
1034  auto *RetVal = RI->getReturnValue();
1035  if (!RetVal) break; // handle "ret void"
1036  if (isa<Constant>(RetVal)) break; // nothing to do
1037  if (auto *C = getConstantAt(RetVal, RI, LVI)) {
1038  ++NumReturns;
1039  RI->replaceUsesOfWith(RetVal, C);
1040  BBChanged = true;
1041  }
1042  }
1043  }
1044 
1045  FnChanged |= BBChanged;
1046  }
1047 
1048  return FnChanged;
1049 }
1050 
1052  if (skipFunction(F))
1053  return false;
1054 
1055  LazyValueInfo *LVI = &getAnalysis<LazyValueInfoWrapperPass>().getLVI();
1056  DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1057 
1058  return runImpl(F, LVI, DT, getBestSimplifyQuery(*this, F));
1059 }
1060 
1065 
1066  bool Changed = runImpl(F, LVI, DT, getBestSimplifyQuery(AM, F));
1067 
1068  PreservedAnalyses PA;
1069  if (!Changed) {
1070  PA = PreservedAnalyses::all();
1071  } else {
1072  PA.preserve<GlobalsAA>();
1075  }
1076 
1077  // Keeping LVI alive is expensive, both because it uses a lot of memory, and
1078  // because invalidating values in LVI is expensive. While CVP does preserve
1079  // LVI, we know that passes after JumpThreading+CVP will not need the result
1080  // of this analysis, so we forcefully discard it early.
1081  PA.abandon<LazyValueAnalysis>();
1082  return PA;
1083 }
Legacy wrapper pass to provide the GlobalsAAResult object.
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:77
void abandon()
Mark an analysis as abandoned.
Definition: PassManager.h:209
uint64_t CallInst * C
unsigned getNumCases() const
Return the number of &#39;cases&#39; in this switch instruction, excluding the default case.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:77
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:801
CaseIt case_end()
Returns a read/write iterator that points one past the last in the SwitchInst.
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:718
LLVM_NODISCARD std::enable_if_t< !is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type > dyn_cast(const Y &Val)
Definition: Casting.h:334
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
static IntegerType * getInt1Ty(LLVMContext &C)
Definition: Type.cpp:183
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
static APInt getAllOnesValue(unsigned numBits)
Get the all-ones value.
Definition: APInt.h:567
signed greater or equal
Definition: InstrTypes.h:756
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:785
This class represents lattice values for constants.
Definition: AllocatorList.h:23
static bool narrowSDivOrSRem(BinaryOperator *Instr, LazyValueInfo *LVI)
Try to shrink a sdiv/srem&#39;s width down to the smallest power of two that&#39;s sufficient to contain its ...
BinaryOps getOpcode() const
Definition: InstrTypes.h:395
static bool processPHI(PHINode *P, LazyValueInfo *LVI, DominatorTree *DT, const SimplifyQuery &SQ)
Wrapper around LazyValueInfo.
Type * getElementType(unsigned N) const
Definition: DerivedTypes.h:329
This is the interface for a simple mod/ref and alias analysis over globals.
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
Represents an op.with.overflow intrinsic.
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
Definition: BasicBlock.cpp:338
Value * getCondition() const
static cl::opt< bool > DontAddNoWrapFlags("cvp-dont-add-nowrap-flags", cl::init(false))
static bool processCmp(CmpInst *Cmp, LazyValueInfo *LVI)
See if LazyValueInfo&#39;s ability to exploit edge conditions or range information is sufficient to prove...
const Value * getTrueValue() const
CaseIt case_begin()
Returns a read/write iterator that points to the first case in the SwitchInst.
A wrapper class to simplify modification of SwitchInst cases along with their prof branch_weights met...
static void processSaturatingInst(SaturatingInst *SI, LazyValueInfo *LVI)
static bool processAShr(BinaryOperator *SDI, LazyValueInfo *LVI)
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:856
STATISTIC(NumFunctions, "Total number of functions")
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1137
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:249
F(f)
This class represents a sign extension of integer types.
static bool willNotOverflow(BinaryOpIntrinsic *BO, LazyValueInfo *LVI)
An instruction for reading from memory.
Definition: Instructions.h:174
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:231
const SimplifyQuery getBestSimplifyQuery(Pass &, Function &)
unsigned getNoWrapKind() const
Returns one of OBO::NoSignedWrap or OBO::NoUnsignedWrap.
bool hasNoSignedWrap() const
Determine whether the no signed wrap flag is set.
static void processOverflowIntrinsic(WithOverflowInst *WO, LazyValueInfo *LVI)
return AArch64::GPR64RegClass contains(Reg)
Value * get() const
Definition: Use.h:67
AnalysisUsage & addRequired()
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...
This class represents the LLVM &#39;select&#39; instruction.
Constant * getConstant(Value *V, Instruction *CxtI)
Determine whether the specified value is known to be a constant at the specified instruction.
Class to represent struct types.
Definition: DerivedTypes.h:218
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
This file contains the simple types necessary to represent the attributes associated with functions a...
static bool processSelect(SelectInst *S, LazyValueInfo *LVI)
bool contains(const APInt &Val) const
Return true if the specified value is in the set.
bool paramHasAttr(unsigned ArgNo, Attribute::AttrKind Kind) const
Determine whether the argument or parameter has the given attribute.
static bool runImpl(Function &F, LazyValueInfo *LVI, DominatorTree *DT, const SimplifyQuery &SQ)
bool isOne() const
This is just a convenience method to make client code smaller for a common case.
Definition: Constants.h:208
void setIsExact(bool b=true)
Set or clear the exact flag on this instruction, which must be an operator which supports this flag...
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:246
Value * CreateInsertValue(Value *Agg, Value *Val, ArrayRef< unsigned > Idxs, const Twine &Name="")
Definition: IRBuilder.h:2467
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:131
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:160
Value * getRHS() const
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:511
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:151
Value * getOperand(unsigned i) const
Definition: User.h:169
Class to represent pointers.
Definition: DerivedTypes.h:657
Optional< OperandBundleUse > getOperandBundle(StringRef Name) const
Return an operand bundle by name, if present.
Definition: InstrTypes.h:1908
void replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
Definition: User.cpp:21
SwitchInst::CaseIt removeCase(SwitchInst::CaseIt I)
Delegate the call to the underlying SwitchInst::removeCase() and remove correspondent branch weight...
static bool processUDivOrURem(BinaryOperator *Instr, LazyValueInfo *LVI)
Try to shrink a udiv/urem&#39;s width down to the smallest power of two that&#39;s sufficient to contain its ...
const BasicBlock & getEntryBlock() const
Definition: Function.h:718
Pass * createCorrelatedValuePropagationPass()
static bool runOnFunction(Function &F, bool PostInlining)
#define P(N)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:427
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:362
signed less or equal
Definition: InstrTypes.h:758
static ConstantPointerNull * get(PointerType *T)
Static factory methods - Return objects of the specified value.
Definition: Constants.cpp:1670
void set(Value *Val)
Definition: Value.h:844
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.
unsigned arg_size() const
Definition: InstrTypes.h:1284
static bool processSDiv(BinaryOperator *SDI, LazyValueInfo *LVI)
See if LazyValueInfo&#39;s ability to exploit edge conditions or range information is sufficient to prove...
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
LLVM_NODISCARD AttributeList addParamAttribute(LLVMContext &C, unsigned ArgNo, Attribute::AttrKind Kind) const
Add an argument attribute to the list.
Definition: Attributes.h:444
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:68
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:728
This is an important base class in LLVM.
Definition: Constant.h:41
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static bool isNonNegative(Value *V, LazyValueInfo *LVI, Instruction *CxtI)
bool isSigned() const
Whether the intrinsic is signed or unsigned.
bool isMask(unsigned numBits) const
Definition: APInt.h:500
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:112
correlated Value Propagation
APInt getUnsignedMax() const
Return the largest unsigned value contained in the ConstantRange.
Represent the analysis usage information of a pass.
Analysis pass providing a never-invalidated alias analysis result.
bool dominates(const Value *Def, const Use &U) const
Return true if value Def dominates use U, in the sense that Def is available at U, and could be substituted as the used value without violating the SSA dominance requirement.
Definition: Dominators.cpp:260
Utility class for integer operators which may exhibit overflow - Add, Sub, Mul, and Shl...
Definition: Operator.h:66
constexpr double e
Definition: MathExtras.h:58
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
static Constant * get(StructType *T, ArrayRef< Constant *> V)
Definition: Constants.cpp:1236
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:115
op_range operands()
Definition: User.h:242
void applyUpdatesPermissive(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
static bool processSwitch(SwitchInst *I, LazyValueInfo *LVI, DominatorTree *DT)
Simplify a switch instruction by removing cases which can never fire.
const Value * getCondition() const
Tristate getPredicateAt(unsigned Pred, Value *V, Constant *C, Instruction *CxtI, bool UseBlockValue=false)
Determine whether the specified value comparison with a constant is known to be true or false at the ...
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...
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1684
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
static CastInst * CreateZExtOrBitCast(Value *S, Type *Ty, const Twine &Name="", Instruction *InsertBefore=nullptr)
Create a ZExt or BitCast cast instruction.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
bool isExact() const
Determine whether the exact flag is set.
iterator_range< User::op_iterator > args()
Iteration adapter for range-for loops.
Definition: InstrTypes.h:1277
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
static bool processSRem(BinaryOperator *SDI, LazyValueInfo *LVI)
Tristate
This is used to return true/false/dunno results.
Definition: LazyValueInfo.h:60
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 ...
static void setDeducedOverflowingFlags(Value *V, Instruction::BinaryOps Opcode, bool NewNSW, bool NewNUW)
Iterator for intrusive lists based on ilist_node.
This is the shared class of boolean and integer constants.
Definition: Constants.h:77
void initializeCorrelatedValuePropagationPass(PassRegistry &)
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:350
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:960
Represents a saturating add/sub intrinsic.
This class represents a range of values.
Definition: ConstantRange.h:47
INITIALIZE_PASS_BEGIN(CorrelatedValuePropagation, "correlated-propagation", "Value Propagation", false, false) INITIALIZE_PASS_END(CorrelatedValuePropagation
static IntegerType * getIntNTy(LLVMContext &C, unsigned N)
Definition: Type.cpp:190
unsigned getActiveBits() const
Compute the maximal number of active bits needed to represent every value in this range...
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
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:838
static bool processSExt(SExtInst *SDI, LazyValueInfo *LVI)
static bool processBinOp(BinaryOperator *BinOp, LazyValueInfo *LVI)
unsigned getNumIncomingValues() const
Return the number of incoming edges.
AttributeList getAttributes() const
Return the parameter attributes for this call.
Definition: InstrTypes.h:1427
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:794
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
static bool processSDivOrSRem(BinaryOperator *Instr, LazyValueInfo *LVI)
bool ule(const APInt &RHS) const
Unsigned less or equal comparison.
Definition: APInt.h:1243
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.
const Value * getFalseValue() const
correlated propagation
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:805
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:365
Instruction::BinaryOps getBinaryOp() const
Returns the binary operation underlying the intrinsic.
static bool processCallSite(CallBase &CB, LazyValueInfo *LVI)
Infer nonnull attributes for the arguments at the specified callsite.
void setCondition(Value *V)
unsigned getIntegerBitWidth() const
Definition: DerivedTypes.h:102
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:295
static bool processAnd(BinaryOperator *BinOp, LazyValueInfo *LVI)
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
#define I(x, y, z)
Definition: MD5.cpp:59
void setAttributes(AttributeList A)
Set the parameter attributes for this call.
Definition: InstrTypes.h:1431
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:176
static bool processMemAccess(Instruction *I, LazyValueInfo *LVI)
static Attribute get(LLVMContext &Context, AttrKind Kind, uint64_t Val=0)
Return a uniquified Attribute object.
Definition: Attributes.cpp:81
This class represents an intrinsic that is based on a binary operation.
bool hasNoUnsignedWrap() const
Determine whether the no unsigned wrap flag is set.
const Value * getPointerOperand(const Value *V)
A helper function that returns the pointer operand of a load, store or GEP instruction.
iterator_range< df_iterator< T > > depth_first(const T &G)
Multiway switch.
This pass computes, caches, and vends lazy value constraint information.
Definition: LazyValueInfo.h:31
SmallVector< MachineOperand, 4 > Cond
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)...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
Definition: APInt.h:550
LLVM Value Representation.
Definition: Value.h:75
succ_range successors(Instruction *I)
Definition: CFG.h:260
static const Function * getParent(const Value *V)
Value * CreateBinOp(Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:1531
static Constant * getConstantAt(Value *V, Instruction *At, LazyValueInfo *LVI)
Domain getDomain(Value *V, LazyValueInfo *LVI, Instruction *CxtI)
A container for analyses that lazily runs them and caches their results.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:278
This header defines various interfaces for pass management in LLVM.
void setIncomingValue(unsigned i, Value *V)
#define LLVM_DEBUG(X)
Definition: Debug.h:122
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
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...
Value * SimplifyInstruction(Instruction *I, const SimplifyQuery &Q, OptimizationRemarkEmitter *ORE=nullptr)
See if we can compute a simplified version of this instruction.
Value * getLHS() const
static bool isNonPositive(Value *V, LazyValueInfo *LVI, Instruction *CxtI)
Analysis to compute lazy value information.
uint64_t PowerOf2Ceil(uint64_t A)
Returns the power of two which is greater than or equal to the given value.
Definition: MathExtras.h:703
const BasicBlock * getParent() const
Definition: Instruction.h:94
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)