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(NumSDivs, "Number of sdiv converted to udiv");
62 STATISTIC(NumUDivs, "Number of udivs whose width was decreased");
63 STATISTIC(NumAShrs, "Number of ashr converted to lshr");
64 STATISTIC(NumSRems, "Number of srem converted to urem");
65 STATISTIC(NumSExt, "Number of sext converted to zext");
66 STATISTIC(NumAnd, "Number of ands removed");
67 STATISTIC(NumNW, "Number of no-wrap deductions");
68 STATISTIC(NumNSW, "Number of no-signed-wrap deductions");
69 STATISTIC(NumNUW, "Number of no-unsigned-wrap deductions");
70 STATISTIC(NumAddNW, "Number of no-wrap deductions for add");
71 STATISTIC(NumAddNSW, "Number of no-signed-wrap deductions for add");
72 STATISTIC(NumAddNUW, "Number of no-unsigned-wrap deductions for add");
73 STATISTIC(NumSubNW, "Number of no-wrap deductions for sub");
74 STATISTIC(NumSubNSW, "Number of no-signed-wrap deductions for sub");
75 STATISTIC(NumSubNUW, "Number of no-unsigned-wrap deductions for sub");
76 STATISTIC(NumMulNW, "Number of no-wrap deductions for mul");
77 STATISTIC(NumMulNSW, "Number of no-signed-wrap deductions for mul");
78 STATISTIC(NumMulNUW, "Number of no-unsigned-wrap deductions for mul");
79 STATISTIC(NumShlNW, "Number of no-wrap deductions for shl");
80 STATISTIC(NumShlNSW, "Number of no-signed-wrap deductions for shl");
81 STATISTIC(NumShlNUW, "Number of no-unsigned-wrap deductions for shl");
82 STATISTIC(NumOverflows, "Number of overflow checks removed");
83 STATISTIC(NumSaturating,
84  "Number of saturating arithmetics converted to normal arithmetics");
85 
86 static cl::opt<bool> DontAddNoWrapFlags("cvp-dont-add-nowrap-flags", cl::init(false));
87 
88 namespace {
89 
90  class CorrelatedValuePropagation : public FunctionPass {
91  public:
92  static char ID;
93 
94  CorrelatedValuePropagation(): FunctionPass(ID) {
96  }
97 
98  bool runOnFunction(Function &F) override;
99 
100  void getAnalysisUsage(AnalysisUsage &AU) const override {
106  }
107  };
108 
109 } // end anonymous namespace
110 
112 
113 INITIALIZE_PASS_BEGIN(CorrelatedValuePropagation, "correlated-propagation",
114  "Value Propagation", false, false)
117 INITIALIZE_PASS_END(CorrelatedValuePropagation, "correlated-propagation",
118  "Value Propagation", false, false)
119 
120 // Public interface to the Value Propagation pass
122  return new CorrelatedValuePropagation();
123 }
124 
125 static bool processSelect(SelectInst *S, LazyValueInfo *LVI) {
126  if (S->getType()->isVectorTy()) return false;
127  if (isa<Constant>(S->getCondition())) return false;
128 
129  Constant *C = LVI->getConstant(S->getCondition(), S->getParent(), S);
130  if (!C) return false;
131 
133  if (!CI) return false;
134 
135  Value *ReplaceWith = CI->isOne() ? S->getTrueValue() : S->getFalseValue();
136  S->replaceAllUsesWith(ReplaceWith);
137  S->eraseFromParent();
138 
139  ++NumSelects;
140 
141  return true;
142 }
143 
144 /// Try to simplify a phi with constant incoming values that match the edge
145 /// values of a non-constant value on all other edges:
146 /// bb0:
147 /// %isnull = icmp eq i8* %x, null
148 /// br i1 %isnull, label %bb2, label %bb1
149 /// bb1:
150 /// br label %bb2
151 /// bb2:
152 /// %r = phi i8* [ %x, %bb1 ], [ null, %bb0 ]
153 /// -->
154 /// %r = %x
156  DominatorTree *DT) {
157  // Collect incoming constants and initialize possible common value.
158  SmallVector<std::pair<Constant *, unsigned>, 4> IncomingConstants;
159  Value *CommonValue = nullptr;
160  for (unsigned i = 0, e = P->getNumIncomingValues(); i != e; ++i) {
161  Value *Incoming = P->getIncomingValue(i);
162  if (auto *IncomingConstant = dyn_cast<Constant>(Incoming)) {
163  IncomingConstants.push_back(std::make_pair(IncomingConstant, i));
164  } else if (!CommonValue) {
165  // The potential common value is initialized to the first non-constant.
166  CommonValue = Incoming;
167  } else if (Incoming != CommonValue) {
168  // There can be only one non-constant common value.
169  return false;
170  }
171  }
172 
173  if (!CommonValue || IncomingConstants.empty())
174  return false;
175 
176  // The common value must be valid in all incoming blocks.
177  BasicBlock *ToBB = P->getParent();
178  if (auto *CommonInst = dyn_cast<Instruction>(CommonValue))
179  if (!DT->dominates(CommonInst, ToBB))
180  return false;
181 
182  // We have a phi with exactly 1 variable incoming value and 1 or more constant
183  // incoming values. See if all constant incoming values can be mapped back to
184  // the same incoming variable value.
185  for (auto &IncomingConstant : IncomingConstants) {
186  Constant *C = IncomingConstant.first;
187  BasicBlock *IncomingBB = P->getIncomingBlock(IncomingConstant.second);
188  if (C != LVI->getConstantOnEdge(CommonValue, IncomingBB, ToBB, P))
189  return false;
190  }
191 
192  // All constant incoming values map to the same variable along the incoming
193  // edges of the phi. The phi is unnecessary. However, we must drop all
194  // poison-generating flags to ensure that no poison is propagated to the phi
195  // location by performing this substitution.
196  // Warning: If the underlying analysis changes, this may not be enough to
197  // guarantee that poison is not propagated.
198  // TODO: We may be able to re-infer flags by re-analyzing the instruction.
199  if (auto *CommonInst = dyn_cast<Instruction>(CommonValue))
200  CommonInst->dropPoisonGeneratingFlags();
201  P->replaceAllUsesWith(CommonValue);
202  P->eraseFromParent();
203  ++NumPhiCommon;
204  return true;
205 }
206 
208  const SimplifyQuery &SQ) {
209  bool Changed = false;
210 
211  BasicBlock *BB = P->getParent();
212  for (unsigned i = 0, e = P->getNumIncomingValues(); i < e; ++i) {
213  Value *Incoming = P->getIncomingValue(i);
214  if (isa<Constant>(Incoming)) continue;
215 
216  Value *V = LVI->getConstantOnEdge(Incoming, P->getIncomingBlock(i), BB, P);
217 
218  // Look if the incoming value is a select with a scalar condition for which
219  // LVI can tells us the value. In that case replace the incoming value with
220  // the appropriate value of the select. This often allows us to remove the
221  // select later.
222  if (!V) {
223  SelectInst *SI = dyn_cast<SelectInst>(Incoming);
224  if (!SI) continue;
225 
226  Value *Condition = SI->getCondition();
227  if (!Condition->getType()->isVectorTy()) {
228  if (Constant *C = LVI->getConstantOnEdge(
229  Condition, P->getIncomingBlock(i), BB, P)) {
230  if (C->isOneValue()) {
231  V = SI->getTrueValue();
232  } else if (C->isZeroValue()) {
233  V = SI->getFalseValue();
234  }
235  // Once LVI learns to handle vector types, we could also add support
236  // for vector type constants that are not all zeroes or all ones.
237  }
238  }
239 
240  // Look if the select has a constant but LVI tells us that the incoming
241  // value can never be that constant. In that case replace the incoming
242  // value with the other value of the select. This often allows us to
243  // remove the select later.
244  if (!V) {
246  if (!C) continue;
247 
248  if (LVI->getPredicateOnEdge(ICmpInst::ICMP_EQ, SI, C,
249  P->getIncomingBlock(i), BB, P) !=
251  continue;
252  V = SI->getTrueValue();
253  }
254 
255  LLVM_DEBUG(dbgs() << "CVP: Threading PHI over " << *SI << '\n');
256  }
257 
258  P->setIncomingValue(i, V);
259  Changed = true;
260  }
261 
262  if (Value *V = SimplifyInstruction(P, SQ)) {
263  P->replaceAllUsesWith(V);
264  P->eraseFromParent();
265  Changed = true;
266  }
267 
268  if (!Changed)
269  Changed = simplifyCommonValuePhi(P, LVI, DT);
270 
271  if (Changed)
272  ++NumPhis;
273 
274  return Changed;
275 }
276 
278  Value *Pointer = nullptr;
279  if (LoadInst *L = dyn_cast<LoadInst>(I))
280  Pointer = L->getPointerOperand();
281  else
282  Pointer = cast<StoreInst>(I)->getPointerOperand();
283 
284  if (isa<Constant>(Pointer)) return false;
285 
286  Constant *C = LVI->getConstant(Pointer, I->getParent(), I);
287  if (!C) return false;
288 
289  ++NumMemAccess;
290  I->replaceUsesOfWith(Pointer, C);
291  return true;
292 }
293 
294 /// See if LazyValueInfo's ability to exploit edge conditions or range
295 /// information is sufficient to prove this comparison. Even for local
296 /// conditions, this can sometimes prove conditions instcombine can't by
297 /// exploiting range information.
298 static bool processCmp(CmpInst *Cmp, LazyValueInfo *LVI) {
299  Value *Op0 = Cmp->getOperand(0);
300  auto *C = dyn_cast<Constant>(Cmp->getOperand(1));
301  if (!C)
302  return false;
303 
304  // As a policy choice, we choose not to waste compile time on anything where
305  // the comparison is testing local values. While LVI can sometimes reason
306  // about such cases, it's not its primary purpose. We do make sure to do
307  // the block local query for uses from terminator instructions, but that's
308  // handled in the code for each terminator. As an exception, we allow phi
309  // nodes, for which LVI can thread the condition into predecessors.
310  auto *I = dyn_cast<Instruction>(Op0);
311  if (I && I->getParent() == Cmp->getParent() && !isa<PHINode>(I))
312  return false;
313 
314  LazyValueInfo::Tristate Result =
315  LVI->getPredicateAt(Cmp->getPredicate(), Op0, C, Cmp);
316  if (Result == LazyValueInfo::Unknown)
317  return false;
318 
319  ++NumCmps;
320  Constant *TorF = ConstantInt::get(Type::getInt1Ty(Cmp->getContext()), Result);
321  Cmp->replaceAllUsesWith(TorF);
322  Cmp->eraseFromParent();
323  return true;
324 }
325 
326 /// Simplify a switch instruction by removing cases which can never fire. If the
327 /// uselessness of a case could be determined locally then constant propagation
328 /// would already have figured it out. Instead, walk the predecessors and
329 /// statically evaluate cases based on information available on that edge. Cases
330 /// that cannot fire no matter what the incoming edge can safely be removed. If
331 /// a case fires on every incoming edge then the entire switch can be removed
332 /// and replaced with a branch to the case destination.
334  DominatorTree *DT) {
336  Value *Cond = I->getCondition();
337  BasicBlock *BB = I->getParent();
338 
339  // If the condition was defined in same block as the switch then LazyValueInfo
340  // currently won't say anything useful about it, though in theory it could.
341  if (isa<Instruction>(Cond) && cast<Instruction>(Cond)->getParent() == BB)
342  return false;
343 
344  // If the switch is unreachable then trying to improve it is a waste of time.
345  pred_iterator PB = pred_begin(BB), PE = pred_end(BB);
346  if (PB == PE) return false;
347 
348  // Analyse each switch case in turn.
349  bool Changed = false;
350  DenseMap<BasicBlock*, int> SuccessorsCount;
351  for (auto *Succ : successors(BB))
352  SuccessorsCount[Succ]++;
353 
354  { // Scope for SwitchInstProfUpdateWrapper. It must not live during
355  // ConstantFoldTerminator() as the underlying SwitchInst can be changed.
357 
358  for (auto CI = SI->case_begin(), CE = SI->case_end(); CI != CE;) {
359  ConstantInt *Case = CI->getCaseValue();
360 
361  // Check to see if the switch condition is equal to/not equal to the case
362  // value on every incoming edge, equal/not equal being the same each time.
364  for (pred_iterator PI = PB; PI != PE; ++PI) {
365  // Is the switch condition equal to the case value?
367  Cond, Case, *PI,
368  BB, SI);
369  // Give up on this case if nothing is known.
370  if (Value == LazyValueInfo::Unknown) {
371  State = LazyValueInfo::Unknown;
372  break;
373  }
374 
375  // If this was the first edge to be visited, record that all other edges
376  // need to give the same result.
377  if (PI == PB) {
378  State = Value;
379  continue;
380  }
381 
382  // If this case is known to fire for some edges and known not to fire for
383  // others then there is nothing we can do - give up.
384  if (Value != State) {
385  State = LazyValueInfo::Unknown;
386  break;
387  }
388  }
389 
390  if (State == LazyValueInfo::False) {
391  // This case never fires - remove it.
392  BasicBlock *Succ = CI->getCaseSuccessor();
393  Succ->removePredecessor(BB);
394  CI = SI.removeCase(CI);
395  CE = SI->case_end();
396 
397  // The condition can be modified by removePredecessor's PHI simplification
398  // logic.
399  Cond = SI->getCondition();
400 
401  ++NumDeadCases;
402  Changed = true;
403  if (--SuccessorsCount[Succ] == 0)
405  continue;
406  }
407  if (State == LazyValueInfo::True) {
408  // This case always fires. Arrange for the switch to be turned into an
409  // unconditional branch by replacing the switch condition with the case
410  // value.
411  SI->setCondition(Case);
412  NumDeadCases += SI->getNumCases();
413  Changed = true;
414  break;
415  }
416 
417  // Increment the case iterator since we didn't delete it.
418  ++CI;
419  }
420  }
421 
422  if (Changed)
423  // If the switch has been simplified to the point where it can be replaced
424  // by a branch then do so now.
425  ConstantFoldTerminator(BB, /*DeleteDeadConditions = */ false,
426  /*TLI = */ nullptr, &DTU);
427  return Changed;
428 }
429 
430 // See if we can prove that the given binary op intrinsic will not overflow.
432  ConstantRange LRange = LVI->getConstantRange(
433  BO->getLHS(), BO->getParent(), BO);
434  ConstantRange RRange = LVI->getConstantRange(
435  BO->getRHS(), BO->getParent(), BO);
437  BO->getBinaryOp(), RRange, BO->getNoWrapKind());
438  return NWRegion.contains(LRange);
439 }
440 
442  bool NewNSW, bool NewNUW) {
443  Statistic *OpcNW, *OpcNSW, *OpcNUW;
444  switch (Opcode) {
445  case Instruction::Add:
446  OpcNW = &NumAddNW;
447  OpcNSW = &NumAddNSW;
448  OpcNUW = &NumAddNUW;
449  break;
450  case Instruction::Sub:
451  OpcNW = &NumSubNW;
452  OpcNSW = &NumSubNSW;
453  OpcNUW = &NumSubNUW;
454  break;
455  case Instruction::Mul:
456  OpcNW = &NumMulNW;
457  OpcNSW = &NumMulNSW;
458  OpcNUW = &NumMulNUW;
459  break;
460  case Instruction::Shl:
461  OpcNW = &NumShlNW;
462  OpcNSW = &NumShlNSW;
463  OpcNUW = &NumShlNUW;
464  break;
465  default:
466  llvm_unreachable("Will not be called with other binops");
467  }
468 
469  auto *Inst = dyn_cast<Instruction>(V);
470  if (NewNSW) {
471  ++NumNW;
472  ++*OpcNW;
473  ++NumNSW;
474  ++*OpcNSW;
475  if (Inst)
476  Inst->setHasNoSignedWrap();
477  }
478  if (NewNUW) {
479  ++NumNW;
480  ++*OpcNW;
481  ++NumNUW;
482  ++*OpcNUW;
483  if (Inst)
484  Inst->setHasNoUnsignedWrap();
485  }
486 }
487 
488 static bool processBinOp(BinaryOperator *BinOp, LazyValueInfo *LVI);
489 
490 // Rewrite this with.overflow intrinsic as non-overflowing.
492  IRBuilder<> B(WO);
493  Instruction::BinaryOps Opcode = WO->getBinaryOp();
494  bool NSW = WO->isSigned();
495  bool NUW = !WO->isSigned();
496 
497  Value *NewOp =
498  B.CreateBinOp(Opcode, WO->getLHS(), WO->getRHS(), WO->getName());
499  setDeducedOverflowingFlags(NewOp, Opcode, NSW, NUW);
500 
501  StructType *ST = cast<StructType>(WO->getType());
502  Constant *Struct = ConstantStruct::get(ST,
505  Value *NewI = B.CreateInsertValue(Struct, NewOp, 0);
506  WO->replaceAllUsesWith(NewI);
507  WO->eraseFromParent();
508  ++NumOverflows;
509 
510  // See if we can infer the other no-wrap too.
511  if (auto *BO = dyn_cast<BinaryOperator>(NewOp))
512  processBinOp(BO, LVI);
513 }
514 
516  Instruction::BinaryOps Opcode = SI->getBinaryOp();
517  bool NSW = SI->isSigned();
518  bool NUW = !SI->isSigned();
520  Opcode, SI->getLHS(), SI->getRHS(), SI->getName(), SI);
521  BinOp->setDebugLoc(SI->getDebugLoc());
522  setDeducedOverflowingFlags(BinOp, Opcode, NSW, NUW);
523 
524  SI->replaceAllUsesWith(BinOp);
525  SI->eraseFromParent();
526  ++NumSaturating;
527 
528  // See if we can infer the other no-wrap too.
529  if (auto *BO = dyn_cast<BinaryOperator>(BinOp))
530  processBinOp(BO, LVI);
531 }
532 
533 /// Infer nonnull attributes for the arguments at the specified callsite.
534 static bool processCallSite(CallBase &CB, LazyValueInfo *LVI) {
536  unsigned ArgNo = 0;
537 
538  if (auto *WO = dyn_cast<WithOverflowInst>(&CB)) {
539  if (WO->getLHS()->getType()->isIntegerTy() && willNotOverflow(WO, LVI)) {
540  processOverflowIntrinsic(WO, LVI);
541  return true;
542  }
543  }
544 
545  if (auto *SI = dyn_cast<SaturatingInst>(&CB)) {
546  if (SI->getType()->isIntegerTy() && willNotOverflow(SI, LVI)) {
548  return true;
549  }
550  }
551 
552  // Deopt bundle operands are intended to capture state with minimal
553  // perturbance of the code otherwise. If we can find a constant value for
554  // any such operand and remove a use of the original value, that's
555  // desireable since it may allow further optimization of that value (e.g. via
556  // single use rules in instcombine). Since deopt uses tend to,
557  // idiomatically, appear along rare conditional paths, it's reasonable likely
558  // we may have a conditional fact with which LVI can fold.
559  if (auto DeoptBundle = CB.getOperandBundle(LLVMContext::OB_deopt)) {
560  bool Progress = false;
561  for (const Use &ConstU : DeoptBundle->Inputs) {
562  Use &U = const_cast<Use&>(ConstU);
563  Value *V = U.get();
564  if (V->getType()->isVectorTy()) continue;
565  if (isa<Constant>(V)) continue;
566 
567  Constant *C = LVI->getConstant(V, CB.getParent(), &CB);
568  if (!C) continue;
569  U.set(C);
570  Progress = true;
571  }
572  if (Progress)
573  return true;
574  }
575 
576  for (Value *V : CB.args()) {
577  PointerType *Type = dyn_cast<PointerType>(V->getType());
578  // Try to mark pointer typed parameters as non-null. We skip the
579  // relatively expensive analysis for constants which are obviously either
580  // null or non-null to start with.
581  if (Type && !CB.paramHasAttr(ArgNo, Attribute::NonNull) &&
582  !isa<Constant>(V) &&
585  &CB) == LazyValueInfo::False)
586  ArgNos.push_back(ArgNo);
587  ArgNo++;
588  }
589 
590  assert(ArgNo == CB.arg_size() && "sanity check");
591 
592  if (ArgNos.empty())
593  return false;
594 
595  AttributeList AS = CB.getAttributes();
596  LLVMContext &Ctx = CB.getContext();
597  AS = AS.addParamAttribute(Ctx, ArgNos,
598  Attribute::get(Ctx, Attribute::NonNull));
599  CB.setAttributes(AS);
600 
601  return true;
602 }
603 
605  Constant *Zero = ConstantInt::get(SDI->getType(), 0);
606  for (Value *O : SDI->operands()) {
607  auto Result = LVI->getPredicateAt(ICmpInst::ICMP_SGE, O, Zero, SDI);
608  if (Result != LazyValueInfo::True)
609  return false;
610  }
611  return true;
612 }
613 
614 /// Try to shrink a udiv/urem's width down to the smallest power of two that's
615 /// sufficient to contain its operands.
616 static bool processUDivOrURem(BinaryOperator *Instr, LazyValueInfo *LVI) {
617  assert(Instr->getOpcode() == Instruction::UDiv ||
618  Instr->getOpcode() == Instruction::URem);
619  if (Instr->getType()->isVectorTy())
620  return false;
621 
622  // Find the smallest power of two bitwidth that's sufficient to hold Instr's
623  // operands.
624  auto OrigWidth = Instr->getType()->getIntegerBitWidth();
625  ConstantRange OperandRange(OrigWidth, /*isFullSet=*/false);
626  for (Value *Operand : Instr->operands()) {
627  OperandRange = OperandRange.unionWith(
628  LVI->getConstantRange(Operand, Instr->getParent()));
629  }
630  // Don't shrink below 8 bits wide.
631  unsigned NewWidth = std::max<unsigned>(
632  PowerOf2Ceil(OperandRange.getUnsignedMax().getActiveBits()), 8);
633  // NewWidth might be greater than OrigWidth if OrigWidth is not a power of
634  // two.
635  if (NewWidth >= OrigWidth)
636  return false;
637 
638  ++NumUDivs;
639  IRBuilder<> B{Instr};
640  auto *TruncTy = Type::getIntNTy(Instr->getContext(), NewWidth);
641  auto *LHS = B.CreateTruncOrBitCast(Instr->getOperand(0), TruncTy,
642  Instr->getName() + ".lhs.trunc");
643  auto *RHS = B.CreateTruncOrBitCast(Instr->getOperand(1), TruncTy,
644  Instr->getName() + ".rhs.trunc");
645  auto *BO = B.CreateBinOp(Instr->getOpcode(), LHS, RHS, Instr->getName());
646  auto *Zext = B.CreateZExt(BO, Instr->getType(), Instr->getName() + ".zext");
647  if (auto *BinOp = dyn_cast<BinaryOperator>(BO))
648  if (BinOp->getOpcode() == Instruction::UDiv)
649  BinOp->setIsExact(Instr->isExact());
650 
651  Instr->replaceAllUsesWith(Zext);
652  Instr->eraseFromParent();
653  return true;
654 }
655 
656 static bool processSRem(BinaryOperator *SDI, LazyValueInfo *LVI) {
657  if (SDI->getType()->isVectorTy() || !hasPositiveOperands(SDI, LVI))
658  return false;
659 
660  ++NumSRems;
661  auto *BO = BinaryOperator::CreateURem(SDI->getOperand(0), SDI->getOperand(1),
662  SDI->getName(), SDI);
663  BO->setDebugLoc(SDI->getDebugLoc());
664  SDI->replaceAllUsesWith(BO);
665  SDI->eraseFromParent();
666 
667  // Try to process our new urem.
668  processUDivOrURem(BO, LVI);
669 
670  return true;
671 }
672 
673 /// See if LazyValueInfo's ability to exploit edge conditions or range
674 /// information is sufficient to prove the both operands of this SDiv are
675 /// positive. If this is the case, replace the SDiv with a UDiv. Even for local
676 /// conditions, this can sometimes prove conditions instcombine can't by
677 /// exploiting range information.
678 static bool processSDiv(BinaryOperator *SDI, LazyValueInfo *LVI) {
679  if (SDI->getType()->isVectorTy() || !hasPositiveOperands(SDI, LVI))
680  return false;
681 
682  ++NumSDivs;
683  auto *BO = BinaryOperator::CreateUDiv(SDI->getOperand(0), SDI->getOperand(1),
684  SDI->getName(), SDI);
685  BO->setDebugLoc(SDI->getDebugLoc());
686  BO->setIsExact(SDI->isExact());
687  SDI->replaceAllUsesWith(BO);
688  SDI->eraseFromParent();
689 
690  // Try to simplify our new udiv.
691  processUDivOrURem(BO, LVI);
692 
693  return true;
694 }
695 
696 static bool processAShr(BinaryOperator *SDI, LazyValueInfo *LVI) {
697  if (SDI->getType()->isVectorTy())
698  return false;
699 
700  Constant *Zero = ConstantInt::get(SDI->getType(), 0);
701  if (LVI->getPredicateAt(ICmpInst::ICMP_SGE, SDI->getOperand(0), Zero, SDI) !=
703  return false;
704 
705  ++NumAShrs;
706  auto *BO = BinaryOperator::CreateLShr(SDI->getOperand(0), SDI->getOperand(1),
707  SDI->getName(), SDI);
708  BO->setDebugLoc(SDI->getDebugLoc());
709  BO->setIsExact(SDI->isExact());
710  SDI->replaceAllUsesWith(BO);
711  SDI->eraseFromParent();
712 
713  return true;
714 }
715 
716 static bool processSExt(SExtInst *SDI, LazyValueInfo *LVI) {
717  if (SDI->getType()->isVectorTy())
718  return false;
719 
720  Value *Base = SDI->getOperand(0);
721 
722  Constant *Zero = ConstantInt::get(Base->getType(), 0);
723  if (LVI->getPredicateAt(ICmpInst::ICMP_SGE, Base, Zero, SDI) !=
725  return false;
726 
727  ++NumSExt;
728  auto *ZExt =
729  CastInst::CreateZExtOrBitCast(Base, SDI->getType(), SDI->getName(), SDI);
730  ZExt->setDebugLoc(SDI->getDebugLoc());
731  SDI->replaceAllUsesWith(ZExt);
732  SDI->eraseFromParent();
733 
734  return true;
735 }
736 
737 static bool processBinOp(BinaryOperator *BinOp, LazyValueInfo *LVI) {
738  using OBO = OverflowingBinaryOperator;
739 
740  if (DontAddNoWrapFlags)
741  return false;
742 
743  if (BinOp->getType()->isVectorTy())
744  return false;
745 
746  bool NSW = BinOp->hasNoSignedWrap();
747  bool NUW = BinOp->hasNoUnsignedWrap();
748  if (NSW && NUW)
749  return false;
750 
751  BasicBlock *BB = BinOp->getParent();
752 
753  Instruction::BinaryOps Opcode = BinOp->getOpcode();
754  Value *LHS = BinOp->getOperand(0);
755  Value *RHS = BinOp->getOperand(1);
756 
757  ConstantRange LRange = LVI->getConstantRange(LHS, BB, BinOp);
758  ConstantRange RRange = LVI->getConstantRange(RHS, BB, BinOp);
759 
760  bool Changed = false;
761  bool NewNUW = false, NewNSW = false;
762  if (!NUW) {
764  Opcode, RRange, OBO::NoUnsignedWrap);
765  NewNUW = NUWRange.contains(LRange);
766  Changed |= NewNUW;
767  }
768  if (!NSW) {
770  Opcode, RRange, OBO::NoSignedWrap);
771  NewNSW = NSWRange.contains(LRange);
772  Changed |= NewNSW;
773  }
774 
775  setDeducedOverflowingFlags(BinOp, Opcode, NewNSW, NewNUW);
776 
777  return Changed;
778 }
779 
780 static bool processAnd(BinaryOperator *BinOp, LazyValueInfo *LVI) {
781  if (BinOp->getType()->isVectorTy())
782  return false;
783 
784  // Pattern match (and lhs, C) where C includes a superset of bits which might
785  // be set in lhs. This is a common truncation idiom created by instcombine.
786  BasicBlock *BB = BinOp->getParent();
787  Value *LHS = BinOp->getOperand(0);
788  ConstantInt *RHS = dyn_cast<ConstantInt>(BinOp->getOperand(1));
789  if (!RHS || !RHS->getValue().isMask())
790  return false;
791 
792  // We can only replace the AND with LHS based on range info if the range does
793  // not include undef.
794  ConstantRange LRange =
795  LVI->getConstantRange(LHS, BB, BinOp, /*UndefAllowed=*/false);
796  if (!LRange.getUnsignedMax().ule(RHS->getValue()))
797  return false;
798 
799  BinOp->replaceAllUsesWith(LHS);
800  BinOp->eraseFromParent();
801  NumAnd++;
802  return true;
803 }
804 
805 
807  if (Constant *C = LVI->getConstant(V, At->getParent(), At))
808  return C;
809 
810  // TODO: The following really should be sunk inside LVI's core algorithm, or
811  // at least the outer shims around such.
812  auto *C = dyn_cast<CmpInst>(V);
813  if (!C) return nullptr;
814 
815  Value *Op0 = C->getOperand(0);
816  Constant *Op1 = dyn_cast<Constant>(C->getOperand(1));
817  if (!Op1) return nullptr;
818 
819  LazyValueInfo::Tristate Result =
820  LVI->getPredicateAt(C->getPredicate(), Op0, Op1, At);
821  if (Result == LazyValueInfo::Unknown)
822  return nullptr;
823 
824  return (Result == LazyValueInfo::True) ?
827 }
828 
829 static bool runImpl(Function &F, LazyValueInfo *LVI, DominatorTree *DT,
830  const SimplifyQuery &SQ) {
831  bool FnChanged = false;
832  // Visiting in a pre-order depth-first traversal causes us to simplify early
833  // blocks before querying later blocks (which require us to analyze early
834  // blocks). Eagerly simplifying shallow blocks means there is strictly less
835  // work to do for deep blocks. This also means we don't visit unreachable
836  // blocks.
837  for (BasicBlock *BB : depth_first(&F.getEntryBlock())) {
838  bool BBChanged = false;
839  for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) {
840  Instruction *II = &*BI++;
841  switch (II->getOpcode()) {
842  case Instruction::Select:
843  BBChanged |= processSelect(cast<SelectInst>(II), LVI);
844  break;
845  case Instruction::PHI:
846  BBChanged |= processPHI(cast<PHINode>(II), LVI, DT, SQ);
847  break;
848  case Instruction::ICmp:
849  case Instruction::FCmp:
850  BBChanged |= processCmp(cast<CmpInst>(II), LVI);
851  break;
852  case Instruction::Load:
853  case Instruction::Store:
854  BBChanged |= processMemAccess(II, LVI);
855  break;
856  case Instruction::Call:
857  case Instruction::Invoke:
858  BBChanged |= processCallSite(cast<CallBase>(*II), LVI);
859  break;
860  case Instruction::SRem:
861  BBChanged |= processSRem(cast<BinaryOperator>(II), LVI);
862  break;
863  case Instruction::SDiv:
864  BBChanged |= processSDiv(cast<BinaryOperator>(II), LVI);
865  break;
866  case Instruction::UDiv:
867  case Instruction::URem:
868  BBChanged |= processUDivOrURem(cast<BinaryOperator>(II), LVI);
869  break;
870  case Instruction::AShr:
871  BBChanged |= processAShr(cast<BinaryOperator>(II), LVI);
872  break;
873  case Instruction::SExt:
874  BBChanged |= processSExt(cast<SExtInst>(II), LVI);
875  break;
876  case Instruction::Add:
877  case Instruction::Sub:
878  case Instruction::Mul:
879  case Instruction::Shl:
880  BBChanged |= processBinOp(cast<BinaryOperator>(II), LVI);
881  break;
882  case Instruction::And:
883  BBChanged |= processAnd(cast<BinaryOperator>(II), LVI);
884  break;
885  }
886  }
887 
888  Instruction *Term = BB->getTerminator();
889  switch (Term->getOpcode()) {
890  case Instruction::Switch:
891  BBChanged |= processSwitch(cast<SwitchInst>(Term), LVI, DT);
892  break;
893  case Instruction::Ret: {
894  auto *RI = cast<ReturnInst>(Term);
895  // Try to determine the return value if we can. This is mainly here to
896  // simplify the writing of unit tests, but also helps to enable IPO by
897  // constant folding the return values of callees.
898  auto *RetVal = RI->getReturnValue();
899  if (!RetVal) break; // handle "ret void"
900  if (isa<Constant>(RetVal)) break; // nothing to do
901  if (auto *C = getConstantAt(RetVal, RI, LVI)) {
902  ++NumReturns;
903  RI->replaceUsesOfWith(RetVal, C);
904  BBChanged = true;
905  }
906  }
907  }
908 
909  FnChanged |= BBChanged;
910  }
911 
912  return FnChanged;
913 }
914 
916  if (skipFunction(F))
917  return false;
918 
919  LazyValueInfo *LVI = &getAnalysis<LazyValueInfoWrapperPass>().getLVI();
920  DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
921 
922  return runImpl(F, LVI, DT, getBestSimplifyQuery(*this, F));
923 }
924 
929 
930  bool Changed = runImpl(F, LVI, DT, getBestSimplifyQuery(AM, F));
931 
932  if (!Changed)
933  return PreservedAnalyses::all();
935  PA.preserve<GlobalsAA>();
938  return PA;
939 }
Legacy wrapper pass to provide the GlobalsAAResult object.
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:77
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:80
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:749
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:715
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...
signed greater or equal
Definition: InstrTypes.h:753
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:769
This class represents lattice values for constants.
Definition: AllocatorList.h:23
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:110
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:326
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:826
STATISTIC(NumFunctions, "Total number of functions")
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1100
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:233
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:173
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)
ConstantRange getConstantRange(Value *V, BasicBlock *BB, Instruction *CxtI=nullptr, bool UndefAllowed=true)
Return the ConstantRange constraint that is known to hold for the specified value at the end of the s...
Value * get() const
Definition: Use.h:67
AnalysisUsage & addRequired()
Constant * getConstant(Value *V, BasicBlock *BB, Instruction *CxtI=nullptr)
Determine whether the specified value is known to be a constant at the end of the specified block...
This class represents the LLVM &#39;select&#39; instruction.
static bool hasPositiveOperands(BinaryOperator *SDI, LazyValueInfo *LVI)
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)
unsigned getActiveBits() const
Compute the number of active bits in the value.
Definition: APInt.h:1593
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:244
Value * CreateInsertValue(Value *Agg, Value *Val, ArrayRef< unsigned > Idxs, const Twine &Name="")
Definition: IRBuilder.h:2435
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:486
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
Value * getOperand(unsigned i) const
Definition: User.h:169
Class to represent pointers.
Definition: DerivedTypes.h:662
Optional< OperandBundleUse > getOperandBundle(StringRef Name) const
Return an operand bundle by name, if present.
Definition: InstrTypes.h:1861
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...
SmallVector< MachineOperand, 4 > Cond
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:689
Pass * createCorrelatedValuePropagationPass()
static bool runOnFunction(Function &F, bool PostInlining)
#define P(N)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:434
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:154
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:360
static ConstantPointerNull * get(PointerType *T)
Static factory methods - Return objects of the specified value.
Definition: Constants.cpp:1651
void set(Value *Val)
Definition: Value.h:764
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:1247
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:430
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
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...
bool isSigned() const
Whether the intrinsic is signed or unsigned.
bool isMask(unsigned numBits) const
Definition: APInt.h:499
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.
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:1219
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
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1665
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:160
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:1240
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 ...
Tristate getPredicateAt(unsigned Pred, Value *V, Constant *C, Instruction *CxtI)
Determine whether the specified value comparison with a constant is known to be true or false at 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 &)
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:883
bool dominates(const Instruction *Def, const Use &U) const
Return true if Def dominates a use in User.
Definition: Dominators.cpp:251
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
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:786
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:1390
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:742
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
bool ule(const APInt &RHS) const
Unsigned less or equal comparison.
Definition: APInt.h:1245
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:802
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:363
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:270
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:1394
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:175
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.
ConstantRange unionWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the union of this range with another range.
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
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())
LLVM Value Representation.
Definition: Value.h:74
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:1510
static Constant * getConstantAt(Value *V, Instruction *At, LazyValueInfo *LVI)
A container for analyses that lazily runs them and caches their results.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:262
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
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)