LLVM  16.0.0git
ConstraintElimination.cpp
Go to the documentation of this file.
1 //===-- ConstraintElimination.cpp - Eliminate conds using constraints. ----===//
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 // Eliminate conditions based on constraints collected from dominating
10 // conditions.
11 //
12 //===----------------------------------------------------------------------===//
13 
15 #include "llvm/ADT/STLExtras.h"
16 #include "llvm/ADT/ScopeExit.h"
17 #include "llvm/ADT/SmallVector.h"
18 #include "llvm/ADT/Statistic.h"
22 #include "llvm/IR/DataLayout.h"
23 #include "llvm/IR/Dominators.h"
24 #include "llvm/IR/Function.h"
26 #include "llvm/IR/IRBuilder.h"
27 #include "llvm/IR/Instructions.h"
28 #include "llvm/IR/PatternMatch.h"
29 #include "llvm/InitializePasses.h"
30 #include "llvm/Pass.h"
31 #include "llvm/Support/Debug.h"
34 #include "llvm/Transforms/Scalar.h"
35 
36 #include <cmath>
37 #include <string>
38 
39 using namespace llvm;
40 using namespace PatternMatch;
41 
42 #define DEBUG_TYPE "constraint-elimination"
43 
44 STATISTIC(NumCondsRemoved, "Number of instructions removed");
45 DEBUG_COUNTER(EliminatedCounter, "conds-eliminated",
46  "Controls which conditions are eliminated");
47 
50 
51 // A helper to multiply 2 signed integers where overflowing is allowed.
52 static int64_t multiplyWithOverflow(int64_t A, int64_t B) {
53  int64_t Result;
54  MulOverflow(A, B, Result);
55  return Result;
56 }
57 
58 // A helper to add 2 signed integers where overflowing is allowed.
59 static int64_t addWithOverflow(int64_t A, int64_t B) {
60  int64_t Result;
61  AddOverflow(A, B, Result);
62  return Result;
63 }
64 
65 namespace {
66 
67 class ConstraintInfo;
68 
69 struct StackEntry {
70  unsigned NumIn;
71  unsigned NumOut;
72  bool IsSigned = false;
73  /// Variables that can be removed from the system once the stack entry gets
74  /// removed.
75  SmallVector<Value *, 2> ValuesToRelease;
76 
77  StackEntry(unsigned NumIn, unsigned NumOut, bool IsSigned,
78  SmallVector<Value *, 2> ValuesToRelease)
79  : NumIn(NumIn), NumOut(NumOut), IsSigned(IsSigned),
80  ValuesToRelease(ValuesToRelease) {}
81 };
82 
83 /// Struct to express a pre-condition of the form %Op0 Pred %Op1.
84 struct PreconditionTy {
85  CmpInst::Predicate Pred;
86  Value *Op0;
87  Value *Op1;
88 
89  PreconditionTy(CmpInst::Predicate Pred, Value *Op0, Value *Op1)
90  : Pred(Pred), Op0(Op0), Op1(Op1) {}
91 };
92 
93 struct ConstraintTy {
94  SmallVector<int64_t, 8> Coefficients;
95  SmallVector<PreconditionTy, 2> Preconditions;
96 
98 
99  bool IsSigned = false;
100  bool IsEq = false;
101 
102  ConstraintTy() = default;
103 
104  ConstraintTy(SmallVector<int64_t, 8> Coefficients, bool IsSigned)
105  : Coefficients(Coefficients), IsSigned(IsSigned) {}
106 
107  unsigned size() const { return Coefficients.size(); }
108 
109  unsigned empty() const { return Coefficients.empty(); }
110 
111  /// Returns true if all preconditions for this list of constraints are
112  /// satisfied given \p CS and the corresponding \p Value2Index mapping.
113  bool isValid(const ConstraintInfo &Info) const;
114 };
115 
116 /// Wrapper encapsulating separate constraint systems and corresponding value
117 /// mappings for both unsigned and signed information. Facts are added to and
118 /// conditions are checked against the corresponding system depending on the
119 /// signed-ness of their predicates. While the information is kept separate
120 /// based on signed-ness, certain conditions can be transferred between the two
121 /// systems.
122 class ConstraintInfo {
123  DenseMap<Value *, unsigned> UnsignedValue2Index;
124  DenseMap<Value *, unsigned> SignedValue2Index;
125 
126  ConstraintSystem UnsignedCS;
127  ConstraintSystem SignedCS;
128 
129  const DataLayout &DL;
130 
131 public:
132  ConstraintInfo(const DataLayout &DL) : DL(DL) {}
133 
134  DenseMap<Value *, unsigned> &getValue2Index(bool Signed) {
135  return Signed ? SignedValue2Index : UnsignedValue2Index;
136  }
137  const DenseMap<Value *, unsigned> &getValue2Index(bool Signed) const {
138  return Signed ? SignedValue2Index : UnsignedValue2Index;
139  }
140 
141  ConstraintSystem &getCS(bool Signed) {
142  return Signed ? SignedCS : UnsignedCS;
143  }
144  const ConstraintSystem &getCS(bool Signed) const {
145  return Signed ? SignedCS : UnsignedCS;
146  }
147 
148  void popLastConstraint(bool Signed) { getCS(Signed).popLastConstraint(); }
149  void popLastNVariables(bool Signed, unsigned N) {
150  getCS(Signed).popLastNVariables(N);
151  }
152 
153  bool doesHold(CmpInst::Predicate Pred, Value *A, Value *B) const;
154 
155  void addFact(CmpInst::Predicate Pred, Value *A, Value *B, unsigned NumIn,
156  unsigned NumOut, SmallVectorImpl<StackEntry> &DFSInStack);
157 
158  /// Turn a comparison of the form \p Op0 \p Pred \p Op1 into a vector of
159  /// constraints, using indices from the corresponding constraint system.
160  /// New variables that need to be added to the system are collected in
161  /// \p NewVariables.
162  ConstraintTy getConstraint(CmpInst::Predicate Pred, Value *Op0, Value *Op1,
163  SmallVectorImpl<Value *> &NewVariables) const;
164 
165  /// Turns a comparison of the form \p Op0 \p Pred \p Op1 into a vector of
166  /// constraints using getConstraint. Returns an empty constraint if the result
167  /// cannot be used to query the existing constraint system, e.g. because it
168  /// would require adding new variables. Also tries to convert signed
169  /// predicates to unsigned ones if possible to allow using the unsigned system
170  /// which increases the effectiveness of the signed <-> unsigned transfer
171  /// logic.
172  ConstraintTy getConstraintForSolving(CmpInst::Predicate Pred, Value *Op0,
173  Value *Op1) const;
174 
175  /// Try to add information from \p A \p Pred \p B to the unsigned/signed
176  /// system if \p Pred is signed/unsigned.
177  void transferToOtherSystem(CmpInst::Predicate Pred, Value *A, Value *B,
178  unsigned NumIn, unsigned NumOut,
179  SmallVectorImpl<StackEntry> &DFSInStack);
180 };
181 
182 /// Represents a (Coefficient * Variable) entry after IR decomposition.
183 struct DecompEntry {
184  int64_t Coefficient;
185  Value *Variable;
186  /// True if the variable is known positive in the current constraint.
187  bool IsKnownPositive;
188 
189  DecompEntry(int64_t Coefficient, Value *Variable,
190  bool IsKnownPositive = false)
191  : Coefficient(Coefficient), Variable(Variable),
192  IsKnownPositive(IsKnownPositive) {}
193 };
194 
195 /// Represents an Offset + Coefficient1 * Variable1 + ... decomposition.
196 struct Decomposition {
197  int64_t Offset = 0;
199 
200  Decomposition(int64_t Offset) : Offset(Offset) {}
201  Decomposition(Value *V, bool IsKnownPositive = false) {
202  Vars.emplace_back(1, V, IsKnownPositive);
203  }
204  Decomposition(int64_t Offset, ArrayRef<DecompEntry> Vars)
205  : Offset(Offset), Vars(Vars) {}
206 
207  void add(int64_t OtherOffset) {
208  Offset = addWithOverflow(Offset, OtherOffset);
209  }
210 
211  void add(const Decomposition &Other) {
212  add(Other.Offset);
213  append_range(Vars, Other.Vars);
214  }
215 
216  void mul(int64_t Factor) {
217  Offset = multiplyWithOverflow(Offset, Factor);
218  for (auto &Var : Vars)
219  Var.Coefficient = multiplyWithOverflow(Var.Coefficient, Factor);
220  }
221 };
222 
223 } // namespace
224 
225 static Decomposition decompose(Value *V,
226  SmallVectorImpl<PreconditionTy> &Preconditions,
227  bool IsSigned, const DataLayout &DL);
228 
229 static bool canUseSExt(ConstantInt *CI) {
230  const APInt &Val = CI->getValue();
232 }
233 
234 static Decomposition
236  SmallVectorImpl<PreconditionTy> &Preconditions, bool IsSigned,
237  const DataLayout &DL) {
238  // Do not reason about pointers where the index size is larger than 64 bits,
239  // as the coefficients used to encode constraints are 64 bit integers.
240  if (DL.getIndexTypeSizeInBits(GEP.getPointerOperand()->getType()) > 64)
241  return &GEP;
242 
243  if (!GEP.isInBounds())
244  return &GEP;
245 
246  Type *PtrTy = GEP.getType()->getScalarType();
247  unsigned BitWidth = DL.getIndexTypeSizeInBits(PtrTy);
248  MapVector<Value *, APInt> VariableOffsets;
249  APInt ConstantOffset(BitWidth, 0);
250  if (!GEP.collectOffset(DL, BitWidth, VariableOffsets, ConstantOffset))
251  return &GEP;
252 
253  // Handle the (gep (gep ....), C) case by incrementing the constant
254  // coefficient of the inner GEP, if C is a constant.
255  auto *InnerGEP = dyn_cast<GetElementPtrInst>(GEP.getPointerOperand());
256  if (VariableOffsets.empty() && InnerGEP && InnerGEP->getNumOperands() == 2) {
257  auto Result = decompose(InnerGEP, Preconditions, IsSigned, DL);
258  Result.add(ConstantOffset.getSExtValue());
259 
260  if (ConstantOffset.isNegative()) {
261  unsigned Scale = DL.getTypeAllocSize(InnerGEP->getResultElementType());
262  int64_t ConstantOffsetI = ConstantOffset.getSExtValue();
263  if (ConstantOffsetI % Scale != 0)
264  return &GEP;
265  // Add pre-condition ensuring the GEP is increasing monotonically and
266  // can be de-composed.
267  // Both sides are normalized by being divided by Scale.
268  Preconditions.emplace_back(
269  CmpInst::ICMP_SGE, InnerGEP->getOperand(1),
270  ConstantInt::get(InnerGEP->getOperand(1)->getType(),
271  -1 * (ConstantOffsetI / Scale)));
272  }
273  return Result;
274  }
275 
276  Decomposition Result(ConstantOffset.getSExtValue(),
277  DecompEntry(1, GEP.getPointerOperand()));
278  for (auto [Index, Scale] : VariableOffsets) {
279  auto IdxResult = decompose(Index, Preconditions, IsSigned, DL);
280  IdxResult.mul(Scale.getSExtValue());
281  Result.add(IdxResult);
282 
283  // If Op0 is signed non-negative, the GEP is increasing monotonically and
284  // can be de-composed.
286  Preconditions.emplace_back(CmpInst::ICMP_SGE, Index,
287  ConstantInt::get(Index->getType(), 0));
288  }
289  return Result;
290 }
291 
292 // Decomposes \p V into a constant offset + list of pairs { Coefficient,
293 // Variable } where Coefficient * Variable. The sum of the constant offset and
294 // pairs equals \p V.
295 static Decomposition decompose(Value *V,
296  SmallVectorImpl<PreconditionTy> &Preconditions,
297  bool IsSigned, const DataLayout &DL) {
298 
299  auto MergeResults = [&Preconditions, IsSigned, &DL](Value *A, Value *B,
300  bool IsSignedB) {
301  auto ResA = decompose(A, Preconditions, IsSigned, DL);
302  auto ResB = decompose(B, Preconditions, IsSignedB, DL);
303  ResA.add(ResB);
304  return ResA;
305  };
306 
307  // Decompose \p V used with a signed predicate.
308  if (IsSigned) {
309  if (auto *CI = dyn_cast<ConstantInt>(V)) {
310  if (canUseSExt(CI))
311  return CI->getSExtValue();
312  }
313  Value *Op0;
314  Value *Op1;
315  if (match(V, m_NSWAdd(m_Value(Op0), m_Value(Op1))))
316  return MergeResults(Op0, Op1, IsSigned);
317 
318  return V;
319  }
320 
321  if (auto *CI = dyn_cast<ConstantInt>(V)) {
322  if (CI->uge(MaxConstraintValue))
323  return V;
324  return int64_t(CI->getZExtValue());
325  }
326 
327  if (auto *GEP = dyn_cast<GetElementPtrInst>(V))
328  return decomposeGEP(*GEP, Preconditions, IsSigned, DL);
329 
330  Value *Op0;
331  bool IsKnownPositive = false;
332  if (match(V, m_ZExt(m_Value(Op0)))) {
333  IsKnownPositive = true;
334  V = Op0;
335  }
336 
337  Value *Op1;
338  ConstantInt *CI;
339  if (match(V, m_NUWAdd(m_Value(Op0), m_Value(Op1)))) {
340  return MergeResults(Op0, Op1, IsSigned);
341  }
342  if (match(V, m_NSWAdd(m_Value(Op0), m_Value(Op1)))) {
343  if (!isKnownNonNegative(Op0, DL, /*Depth=*/MaxAnalysisRecursionDepth - 1))
344  Preconditions.emplace_back(CmpInst::ICMP_SGE, Op0,
345  ConstantInt::get(Op0->getType(), 0));
346  if (!isKnownNonNegative(Op1, DL, /*Depth=*/MaxAnalysisRecursionDepth - 1))
347  Preconditions.emplace_back(CmpInst::ICMP_SGE, Op1,
348  ConstantInt::get(Op1->getType(), 0));
349 
350  return MergeResults(Op0, Op1, IsSigned);
351  }
352 
353  if (match(V, m_Add(m_Value(Op0), m_ConstantInt(CI))) && CI->isNegative() &&
354  canUseSExt(CI)) {
355  Preconditions.emplace_back(
356  CmpInst::ICMP_UGE, Op0,
357  ConstantInt::get(Op0->getType(), CI->getSExtValue() * -1));
358  return MergeResults(Op0, CI, true);
359  }
360 
361  if (match(V, m_NUWShl(m_Value(Op1), m_ConstantInt(CI))) && canUseSExt(CI)) {
362  int64_t Mult = int64_t(std::pow(int64_t(2), CI->getSExtValue()));
363  auto Result = decompose(Op1, Preconditions, IsSigned, DL);
364  Result.mul(Mult);
365  return Result;
366  }
367 
368  if (match(V, m_NUWMul(m_Value(Op1), m_ConstantInt(CI))) && canUseSExt(CI) &&
369  (!CI->isNegative())) {
370  auto Result = decompose(Op1, Preconditions, IsSigned, DL);
371  Result.mul(CI->getSExtValue());
372  return Result;
373  }
374 
375  if (match(V, m_NUWSub(m_Value(Op0), m_ConstantInt(CI))) && canUseSExt(CI))
376  return {-1 * CI->getSExtValue(), {{1, Op0}}};
377  if (match(V, m_NUWSub(m_Value(Op0), m_Value(Op1))))
378  return {0, {{1, Op0}, {-1, Op1}}};
379 
380  return {V, IsKnownPositive};
381 }
382 
383 ConstraintTy
385  SmallVectorImpl<Value *> &NewVariables) const {
386  assert(NewVariables.empty() && "NewVariables must be empty when passed in");
387  bool IsEq = false;
388  // Try to convert Pred to one of ULE/SLT/SLE/SLT.
389  switch (Pred) {
390  case CmpInst::ICMP_UGT:
391  case CmpInst::ICMP_UGE:
392  case CmpInst::ICMP_SGT:
393  case CmpInst::ICMP_SGE: {
394  Pred = CmpInst::getSwappedPredicate(Pred);
395  std::swap(Op0, Op1);
396  break;
397  }
398  case CmpInst::ICMP_EQ:
399  if (match(Op1, m_Zero())) {
400  Pred = CmpInst::ICMP_ULE;
401  } else {
402  IsEq = true;
403  Pred = CmpInst::ICMP_ULE;
404  }
405  break;
406  case CmpInst::ICMP_NE:
407  if (!match(Op1, m_Zero()))
408  return {};
410  std::swap(Op0, Op1);
411  break;
412  default:
413  break;
414  }
415 
416  // Only ULE and ULT predicates are supported at the moment.
417  if (Pred != CmpInst::ICMP_ULE && Pred != CmpInst::ICMP_ULT &&
418  Pred != CmpInst::ICMP_SLE && Pred != CmpInst::ICMP_SLT)
419  return {};
420 
421  SmallVector<PreconditionTy, 4> Preconditions;
422  bool IsSigned = CmpInst::isSigned(Pred);
423  auto &Value2Index = getValue2Index(IsSigned);
425  Preconditions, IsSigned, DL);
427  Preconditions, IsSigned, DL);
428  int64_t Offset1 = ADec.Offset;
429  int64_t Offset2 = BDec.Offset;
430  Offset1 *= -1;
431 
432  auto &VariablesA = ADec.Vars;
433  auto &VariablesB = BDec.Vars;
434 
435  // First try to look up \p V in Value2Index and NewVariables. Otherwise add a
436  // new entry to NewVariables.
437  DenseMap<Value *, unsigned> NewIndexMap;
438  auto GetOrAddIndex = [&Value2Index, &NewVariables,
439  &NewIndexMap](Value *V) -> unsigned {
440  auto V2I = Value2Index.find(V);
441  if (V2I != Value2Index.end())
442  return V2I->second;
443  auto Insert =
444  NewIndexMap.insert({V, Value2Index.size() + NewVariables.size() + 1});
445  if (Insert.second)
446  NewVariables.push_back(V);
447  return Insert.first->second;
448  };
449 
450  // Make sure all variables have entries in Value2Index or NewVariables.
451  for (const auto &KV : concat<DecompEntry>(VariablesA, VariablesB))
452  GetOrAddIndex(KV.Variable);
453 
454  // Build result constraint, by first adding all coefficients from A and then
455  // subtracting all coefficients from B.
456  ConstraintTy Res(
457  SmallVector<int64_t, 8>(Value2Index.size() + NewVariables.size() + 1, 0),
458  IsSigned);
459  // Collect variables that are known to be positive in all uses in the
460  // constraint.
461  DenseMap<Value *, bool> KnownPositiveVariables;
462  Res.IsEq = IsEq;
463  auto &R = Res.Coefficients;
464  for (const auto &KV : VariablesA) {
465  R[GetOrAddIndex(KV.Variable)] += KV.Coefficient;
466  auto I = KnownPositiveVariables.insert({KV.Variable, KV.IsKnownPositive});
467  I.first->second &= KV.IsKnownPositive;
468  }
469 
470  for (const auto &KV : VariablesB) {
471  R[GetOrAddIndex(KV.Variable)] -= KV.Coefficient;
472  auto I = KnownPositiveVariables.insert({KV.Variable, KV.IsKnownPositive});
473  I.first->second &= KV.IsKnownPositive;
474  }
475 
476  int64_t OffsetSum;
477  if (AddOverflow(Offset1, Offset2, OffsetSum))
478  return {};
479  if (Pred == (IsSigned ? CmpInst::ICMP_SLT : CmpInst::ICMP_ULT))
480  if (AddOverflow(OffsetSum, int64_t(-1), OffsetSum))
481  return {};
482  R[0] = OffsetSum;
483  Res.Preconditions = std::move(Preconditions);
484 
485  // Remove any (Coefficient, Variable) entry where the Coefficient is 0 for new
486  // variables.
487  while (!NewVariables.empty()) {
488  int64_t Last = R.back();
489  if (Last != 0)
490  break;
491  R.pop_back();
492  Value *RemovedV = NewVariables.pop_back_val();
493  NewIndexMap.erase(RemovedV);
494  }
495 
496  // Add extra constraints for variables that are known positive.
497  for (auto &KV : KnownPositiveVariables) {
498  if (!KV.second || (Value2Index.find(KV.first) == Value2Index.end() &&
499  NewIndexMap.find(KV.first) == NewIndexMap.end()))
500  continue;
501  SmallVector<int64_t, 8> C(Value2Index.size() + NewVariables.size() + 1, 0);
502  C[GetOrAddIndex(KV.first)] = -1;
503  Res.ExtraInfo.push_back(C);
504  }
505  return Res;
506 }
507 
508 ConstraintTy ConstraintInfo::getConstraintForSolving(CmpInst::Predicate Pred,
509  Value *Op0,
510  Value *Op1) const {
511  // If both operands are known to be non-negative, change signed predicates to
512  // unsigned ones. This increases the reasoning effectiveness in combination
513  // with the signed <-> unsigned transfer logic.
514  if (CmpInst::isSigned(Pred) &&
515  isKnownNonNegative(Op0, DL, /*Depth=*/MaxAnalysisRecursionDepth - 1) &&
516  isKnownNonNegative(Op1, DL, /*Depth=*/MaxAnalysisRecursionDepth - 1))
517  Pred = CmpInst::getUnsignedPredicate(Pred);
518 
519  SmallVector<Value *> NewVariables;
520  ConstraintTy R = getConstraint(Pred, Op0, Op1, NewVariables);
521  if (R.IsEq || !NewVariables.empty())
522  return {};
523  return R;
524 }
525 
526 bool ConstraintTy::isValid(const ConstraintInfo &Info) const {
527  return Coefficients.size() > 0 &&
528  all_of(Preconditions, [&Info](const PreconditionTy &C) {
529  return Info.doesHold(C.Pred, C.Op0, C.Op1);
530  });
531 }
532 
533 bool ConstraintInfo::doesHold(CmpInst::Predicate Pred, Value *A,
534  Value *B) const {
535  auto R = getConstraintForSolving(Pred, A, B);
536  return R.Preconditions.empty() && !R.empty() &&
537  getCS(R.IsSigned).isConditionImplied(R.Coefficients);
538 }
539 
540 void ConstraintInfo::transferToOtherSystem(
541  CmpInst::Predicate Pred, Value *A, Value *B, unsigned NumIn,
542  unsigned NumOut, SmallVectorImpl<StackEntry> &DFSInStack) {
543  // Check if we can combine facts from the signed and unsigned systems to
544  // derive additional facts.
545  if (!A->getType()->isIntegerTy())
546  return;
547  // FIXME: This currently depends on the order we add facts. Ideally we
548  // would first add all known facts and only then try to add additional
549  // facts.
550  switch (Pred) {
551  default:
552  break;
553  case CmpInst::ICMP_ULT:
554  // If B is a signed positive constant, A >=s 0 and A <s B.
555  if (doesHold(CmpInst::ICMP_SGE, B, ConstantInt::get(B->getType(), 0))) {
556  addFact(CmpInst::ICMP_SGE, A, ConstantInt::get(B->getType(), 0), NumIn,
557  NumOut, DFSInStack);
558  addFact(CmpInst::ICMP_SLT, A, B, NumIn, NumOut, DFSInStack);
559  }
560  break;
561  case CmpInst::ICMP_SLT:
562  if (doesHold(CmpInst::ICMP_SGE, A, ConstantInt::get(B->getType(), 0)))
563  addFact(CmpInst::ICMP_ULT, A, B, NumIn, NumOut, DFSInStack);
564  break;
565  case CmpInst::ICMP_SGT:
566  if (doesHold(CmpInst::ICMP_SGE, B, ConstantInt::get(B->getType(), -1)))
567  addFact(CmpInst::ICMP_UGE, A, ConstantInt::get(B->getType(), 0), NumIn,
568  NumOut, DFSInStack);
569  break;
570  case CmpInst::ICMP_SGE:
571  if (doesHold(CmpInst::ICMP_SGE, B, ConstantInt::get(B->getType(), 0))) {
572  addFact(CmpInst::ICMP_UGE, A, B, NumIn, NumOut, DFSInStack);
573  }
574  break;
575  }
576 }
577 
578 namespace {
579 /// Represents either
580 /// * a condition that holds on entry to a block (=conditional fact)
581 /// * an assume (=assume fact)
582 /// * an instruction to simplify.
583 /// It also tracks the Dominator DFS in and out numbers for each entry.
584 struct FactOrCheck {
585  Instruction *Inst;
586  unsigned NumIn;
587  unsigned NumOut;
588  bool IsCheck;
589  bool Not;
590 
591  FactOrCheck(DomTreeNode *DTN, Instruction *Inst, bool IsCheck, bool Not)
592  : Inst(Inst), NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()),
593  IsCheck(IsCheck), Not(Not) {}
594 
595  static FactOrCheck getFact(DomTreeNode *DTN, Instruction *Inst,
596  bool Not = false) {
597  return FactOrCheck(DTN, Inst, false, Not);
598  }
599 
600  static FactOrCheck getCheck(DomTreeNode *DTN, Instruction *Inst) {
601  return FactOrCheck(DTN, Inst, true, false);
602  }
603 
604  bool isAssumeFact() const {
605  if (!IsCheck && isa<IntrinsicInst>(Inst)) {
606  assert(match(Inst, m_Intrinsic<Intrinsic::assume>()));
607  return true;
608  }
609  return false;
610  }
611 
612  bool isConditionFact() const { return !IsCheck && isa<CmpInst>(Inst); }
613 };
614 
615 /// Keep state required to build worklist.
616 struct State {
617  DominatorTree &DT;
619 
620  State(DominatorTree &DT) : DT(DT) {}
621 
622  /// Process block \p BB and add known facts to work-list.
623  void addInfoFor(BasicBlock &BB);
624 
625  /// Returns true if we can add a known condition from BB to its successor
626  /// block Succ. Each predecessor of Succ can either be BB or be dominated
627  /// by Succ (e.g. the case when adding a condition from a pre-header to a
628  /// loop header).
629  bool canAddSuccessor(BasicBlock &BB, BasicBlock *Succ) const {
630  if (BB.getSingleSuccessor()) {
631  assert(BB.getSingleSuccessor() == Succ);
632  return DT.properlyDominates(&BB, Succ);
633  }
634  return any_of(successors(&BB),
635  [Succ](const BasicBlock *S) { return S != Succ; }) &&
636  all_of(predecessors(Succ), [&BB, Succ, this](BasicBlock *Pred) {
637  return Pred == &BB || DT.dominates(Succ, Pred);
638  });
639  }
640 };
641 
642 } // namespace
643 
644 #ifndef NDEBUG
645 static void dumpWithNames(const ConstraintSystem &CS,
646  DenseMap<Value *, unsigned> &Value2Index) {
647  SmallVector<std::string> Names(Value2Index.size(), "");
648  for (auto &KV : Value2Index) {
649  Names[KV.second - 1] = std::string("%") + KV.first->getName().str();
650  }
651  CS.dump(Names);
652 }
653 
655  DenseMap<Value *, unsigned> &Value2Index) {
656  ConstraintSystem CS;
657  CS.addVariableRowFill(C);
658  dumpWithNames(CS, Value2Index);
659 }
660 #endif
661 
662 void State::addInfoFor(BasicBlock &BB) {
663  // True as long as long as the current instruction is guaranteed to execute.
664  bool GuaranteedToExecute = true;
665  // Queue conditions and assumes.
666  for (Instruction &I : BB) {
667  if (auto Cmp = dyn_cast<ICmpInst>(&I)) {
668  WorkList.push_back(FactOrCheck::getCheck(DT.getNode(&BB), Cmp));
669  continue;
670  }
671 
672  if (match(&I, m_Intrinsic<Intrinsic::ssub_with_overflow>())) {
673  WorkList.push_back(FactOrCheck::getCheck(DT.getNode(&BB), &I));
674  continue;
675  }
676 
677  Value *Cond;
678  // For now, just handle assumes with a single compare as condition.
679  if (match(&I, m_Intrinsic<Intrinsic::assume>(m_Value(Cond))) &&
680  isa<ICmpInst>(Cond)) {
681  if (GuaranteedToExecute) {
682  // The assume is guaranteed to execute when BB is entered, hence Cond
683  // holds on entry to BB.
684  WorkList.emplace_back(FactOrCheck::getFact(DT.getNode(I.getParent()),
685  cast<Instruction>(Cond)));
686  } else {
687  WorkList.emplace_back(
688  FactOrCheck::getFact(DT.getNode(I.getParent()), &I));
689  }
690  }
691  GuaranteedToExecute &= isGuaranteedToTransferExecutionToSuccessor(&I);
692  }
693 
694  auto *Br = dyn_cast<BranchInst>(BB.getTerminator());
695  if (!Br || !Br->isConditional())
696  return;
697 
698  Value *Cond = Br->getCondition();
699 
700  // If the condition is a chain of ORs/AND and the successor only has the
701  // current block as predecessor, queue conditions for the successor.
702  Value *Op0, *Op1;
703  if (match(Cond, m_LogicalOr(m_Value(Op0), m_Value(Op1))) ||
704  match(Cond, m_LogicalAnd(m_Value(Op0), m_Value(Op1)))) {
705  bool IsOr = match(Cond, m_LogicalOr());
706  bool IsAnd = match(Cond, m_LogicalAnd());
707  // If there's a select that matches both AND and OR, we need to commit to
708  // one of the options. Arbitrarily pick OR.
709  if (IsOr && IsAnd)
710  IsAnd = false;
711 
712  BasicBlock *Successor = Br->getSuccessor(IsOr ? 1 : 0);
713  if (canAddSuccessor(BB, Successor)) {
714  SmallVector<Value *> CondWorkList;
715  SmallPtrSet<Value *, 8> SeenCond;
716  auto QueueValue = [&CondWorkList, &SeenCond](Value *V) {
717  if (SeenCond.insert(V).second)
718  CondWorkList.push_back(V);
719  };
720  QueueValue(Op1);
721  QueueValue(Op0);
722  while (!CondWorkList.empty()) {
723  Value *Cur = CondWorkList.pop_back_val();
724  if (auto *Cmp = dyn_cast<ICmpInst>(Cur)) {
725  WorkList.emplace_back(
726  FactOrCheck::getFact(DT.getNode(Successor), Cmp, IsOr));
727  continue;
728  }
729  if (IsOr && match(Cur, m_LogicalOr(m_Value(Op0), m_Value(Op1)))) {
730  QueueValue(Op1);
731  QueueValue(Op0);
732  continue;
733  }
734  if (IsAnd && match(Cur, m_LogicalAnd(m_Value(Op0), m_Value(Op1)))) {
735  QueueValue(Op1);
736  QueueValue(Op0);
737  continue;
738  }
739  }
740  }
741  return;
742  }
743 
744  auto *CmpI = dyn_cast<ICmpInst>(Br->getCondition());
745  if (!CmpI)
746  return;
747  if (canAddSuccessor(BB, Br->getSuccessor(0)))
748  WorkList.emplace_back(
749  FactOrCheck::getFact(DT.getNode(Br->getSuccessor(0)), CmpI));
750  if (canAddSuccessor(BB, Br->getSuccessor(1)))
751  WorkList.emplace_back(
752  FactOrCheck::getFact(DT.getNode(Br->getSuccessor(1)), CmpI, true));
753 }
754 
755 static bool checkAndReplaceCondition(CmpInst *Cmp, ConstraintInfo &Info) {
756  LLVM_DEBUG(dbgs() << "Checking " << *Cmp << "\n");
757 
758  CmpInst::Predicate Pred = Cmp->getPredicate();
759  Value *A = Cmp->getOperand(0);
760  Value *B = Cmp->getOperand(1);
761 
762  auto R = Info.getConstraintForSolving(Pred, A, B);
763  if (R.empty() || !R.isValid(Info)){
764  LLVM_DEBUG(dbgs() << " failed to decompose condition\n");
765  return false;
766  }
767 
768  auto &CSToUse = Info.getCS(R.IsSigned);
769 
770  // If there was extra information collected during decomposition, apply
771  // it now and remove it immediately once we are done with reasoning
772  // about the constraint.
773  for (auto &Row : R.ExtraInfo)
774  CSToUse.addVariableRow(Row);
775  auto InfoRestorer = make_scope_exit([&]() {
776  for (unsigned I = 0; I < R.ExtraInfo.size(); ++I)
777  CSToUse.popLastConstraint();
778  });
779 
780  bool Changed = false;
781  if (CSToUse.isConditionImplied(R.Coefficients)) {
782  if (!DebugCounter::shouldExecute(EliminatedCounter))
783  return false;
784 
785  LLVM_DEBUG({
786  dbgs() << "Condition " << *Cmp << " implied by dominating constraints\n";
787  dumpWithNames(CSToUse, Info.getValue2Index(R.IsSigned));
788  });
789  Constant *TrueC =
791  Cmp->replaceUsesWithIf(TrueC, [](Use &U) {
792  // Conditions in an assume trivially simplify to true. Skip uses
793  // in assume calls to not destroy the available information.
794  auto *II = dyn_cast<IntrinsicInst>(U.getUser());
795  return !II || II->getIntrinsicID() != Intrinsic::assume;
796  });
797  NumCondsRemoved++;
798  Changed = true;
799  }
800  if (CSToUse.isConditionImplied(ConstraintSystem::negate(R.Coefficients))) {
801  if (!DebugCounter::shouldExecute(EliminatedCounter))
802  return false;
803 
804  LLVM_DEBUG({
805  dbgs() << "Condition !" << *Cmp << " implied by dominating constraints\n";
806  dumpWithNames(CSToUse, Info.getValue2Index(R.IsSigned));
807  });
808  Constant *FalseC =
810  Cmp->replaceAllUsesWith(FalseC);
811  NumCondsRemoved++;
812  Changed = true;
813  }
814  return Changed;
815 }
816 
817 void ConstraintInfo::addFact(CmpInst::Predicate Pred, Value *A, Value *B,
818  unsigned NumIn, unsigned NumOut,
819  SmallVectorImpl<StackEntry> &DFSInStack) {
820  // If the constraint has a pre-condition, skip the constraint if it does not
821  // hold.
822  SmallVector<Value *> NewVariables;
823  auto R = getConstraint(Pred, A, B, NewVariables);
824  if (!R.isValid(*this))
825  return;
826 
827  LLVM_DEBUG(dbgs() << "Adding '" << CmpInst::getPredicateName(Pred) << " ";
828  A->printAsOperand(dbgs(), false); dbgs() << ", ";
829  B->printAsOperand(dbgs(), false); dbgs() << "'\n");
830  bool Added = false;
831  auto &CSToUse = getCS(R.IsSigned);
832  if (R.Coefficients.empty())
833  return;
834 
835  Added |= CSToUse.addVariableRowFill(R.Coefficients);
836 
837  // If R has been added to the system, add the new variables and queue it for
838  // removal once it goes out-of-scope.
839  if (Added) {
840  SmallVector<Value *, 2> ValuesToRelease;
841  auto &Value2Index = getValue2Index(R.IsSigned);
842  for (Value *V : NewVariables) {
843  Value2Index.insert({V, Value2Index.size() + 1});
844  ValuesToRelease.push_back(V);
845  }
846 
847  LLVM_DEBUG({
848  dbgs() << " constraint: ";
849  dumpWithNames(R.Coefficients, getValue2Index(R.IsSigned));
850  dbgs() << "\n";
851  });
852 
853  DFSInStack.emplace_back(NumIn, NumOut, R.IsSigned, ValuesToRelease);
854 
855  if (R.IsEq) {
856  // Also add the inverted constraint for equality constraints.
857  for (auto &Coeff : R.Coefficients)
858  Coeff *= -1;
859  CSToUse.addVariableRowFill(R.Coefficients);
860 
861  DFSInStack.emplace_back(NumIn, NumOut, R.IsSigned,
863  }
864  }
865 }
866 
869  bool Changed = false;
871  Value *Sub = nullptr;
872  for (User *U : make_early_inc_range(II->users())) {
873  if (match(U, m_ExtractValue<0>(m_Value()))) {
874  if (!Sub)
875  Sub = Builder.CreateSub(A, B);
876  U->replaceAllUsesWith(Sub);
877  Changed = true;
878  } else if (match(U, m_ExtractValue<1>(m_Value()))) {
879  U->replaceAllUsesWith(Builder.getFalse());
880  Changed = true;
881  } else
882  continue;
883 
884  if (U->use_empty()) {
885  auto *I = cast<Instruction>(U);
886  ToRemove.push_back(I);
887  I->setOperand(0, PoisonValue::get(II->getType()));
888  Changed = true;
889  }
890  }
891 
892  if (II->use_empty()) {
893  II->eraseFromParent();
894  Changed = true;
895  }
896  return Changed;
897 }
898 
899 static bool
902  auto DoesConditionHold = [](CmpInst::Predicate Pred, Value *A, Value *B,
903  ConstraintInfo &Info) {
904  auto R = Info.getConstraintForSolving(Pred, A, B);
905  if (R.size() < 2 || !R.isValid(Info))
906  return false;
907 
908  auto &CSToUse = Info.getCS(R.IsSigned);
909  return CSToUse.isConditionImplied(R.Coefficients);
910  };
911 
912  bool Changed = false;
913  if (II->getIntrinsicID() == Intrinsic::ssub_with_overflow) {
914  // If A s>= B && B s>= 0, ssub.with.overflow(a, b) should not overflow and
915  // can be simplified to a regular sub.
916  Value *A = II->getArgOperand(0);
917  Value *B = II->getArgOperand(1);
918  if (!DoesConditionHold(CmpInst::ICMP_SGE, A, B, Info) ||
919  !DoesConditionHold(CmpInst::ICMP_SGE, B,
920  ConstantInt::get(A->getType(), 0), Info))
921  return false;
922  Changed = replaceSubOverflowUses(II, A, B, ToRemove);
923  }
924  return Changed;
925 }
926 
928  bool Changed = false;
929  DT.updateDFSNumbers();
930 
931  ConstraintInfo Info(F.getParent()->getDataLayout());
932  State S(DT);
933 
934  // First, collect conditions implied by branches and blocks with their
935  // Dominator DFS in and out numbers.
936  for (BasicBlock &BB : F) {
937  if (!DT.getNode(&BB))
938  continue;
939  S.addInfoFor(BB);
940  }
941 
942  // Next, sort worklist by dominance, so that dominating conditions to check
943  // and facts come before conditions and facts dominated by them. If a
944  // condition to check and a fact have the same numbers, conditional facts come
945  // first. Assume facts and checks are ordered according to their relative
946  // order in the containing basic block. Also make sure conditions with
947  // constant operands come before conditions without constant operands. This
948  // increases the effectiveness of the current signed <-> unsigned fact
949  // transfer logic.
950  stable_sort(S.WorkList, [](const FactOrCheck &A, const FactOrCheck &B) {
951  auto HasNoConstOp = [](const FactOrCheck &B) {
952  return !isa<ConstantInt>(B.Inst->getOperand(0)) &&
953  !isa<ConstantInt>(B.Inst->getOperand(1));
954  };
955  // If both entries have the same In numbers, conditional facts come first.
956  // Otherwise use the relative order in the basic block.
957  if (A.NumIn == B.NumIn) {
958  if (A.isConditionFact() && B.IsCheck)
959  return true;
960  if (B.isConditionFact() && A.IsCheck)
961  return false;
962  if (A.isConditionFact() && B.isConditionFact()) {
963  bool NoConstOpA = HasNoConstOp(A);
964  bool NoConstOpB = HasNoConstOp(B);
965  return NoConstOpA < NoConstOpB;
966  }
967  return A.Inst->comesBefore(B.Inst);
968  }
969  return A.NumIn < B.NumIn;
970  });
971 
973 
974  // Finally, process ordered worklist and eliminate implied conditions.
975  SmallVector<StackEntry, 16> DFSInStack;
976  for (FactOrCheck &CB : S.WorkList) {
977  // First, pop entries from the stack that are out-of-scope for CB. Remove
978  // the corresponding entry from the constraint system.
979  while (!DFSInStack.empty()) {
980  auto &E = DFSInStack.back();
981  LLVM_DEBUG(dbgs() << "Top of stack : " << E.NumIn << " " << E.NumOut
982  << "\n");
983  LLVM_DEBUG(dbgs() << "CB: " << CB.NumIn << " " << CB.NumOut << "\n");
984  assert(E.NumIn <= CB.NumIn);
985  if (CB.NumOut <= E.NumOut)
986  break;
987  LLVM_DEBUG({
988  dbgs() << "Removing ";
989  dumpWithNames(Info.getCS(E.IsSigned).getLastConstraint(),
990  Info.getValue2Index(E.IsSigned));
991  dbgs() << "\n";
992  });
993 
994  Info.popLastConstraint(E.IsSigned);
995  // Remove variables in the system that went out of scope.
996  auto &Mapping = Info.getValue2Index(E.IsSigned);
997  for (Value *V : E.ValuesToRelease)
998  Mapping.erase(V);
999  Info.popLastNVariables(E.IsSigned, E.ValuesToRelease.size());
1000  DFSInStack.pop_back();
1001  }
1002 
1003  LLVM_DEBUG({
1004  dbgs() << "Processing ";
1005  if (CB.IsCheck)
1006  dbgs() << "condition to simplify: " << *CB.Inst;
1007  else
1008  dbgs() << "fact to add to the system: " << *CB.Inst;
1009  dbgs() << "\n";
1010  });
1011 
1012  // For a block, check if any CmpInsts become known based on the current set
1013  // of constraints.
1014  if (CB.IsCheck) {
1015  if (auto *II = dyn_cast<WithOverflowInst>(CB.Inst)) {
1016  Changed |= tryToSimplifyOverflowMath(II, Info, ToRemove);
1017  } else if (auto *Cmp = dyn_cast<ICmpInst>(CB.Inst)) {
1018  Changed |= checkAndReplaceCondition(Cmp, Info);
1019  }
1020  continue;
1021  }
1022 
1023  ICmpInst::Predicate Pred;
1024  Value *A, *B;
1025  Value *Cmp = CB.Inst;
1026  match(Cmp, m_Intrinsic<Intrinsic::assume>(m_Value(Cmp)));
1027  if (match(Cmp, m_ICmp(Pred, m_Value(A), m_Value(B)))) {
1028  // Use the inverse predicate if required.
1029  if (CB.Not)
1030  Pred = CmpInst::getInversePredicate(Pred);
1031 
1032  Info.addFact(Pred, A, B, CB.NumIn, CB.NumOut, DFSInStack);
1033  Info.transferToOtherSystem(Pred, A, B, CB.NumIn, CB.NumOut, DFSInStack);
1034  }
1035  }
1036 
1037 #ifndef NDEBUG
1038  unsigned SignedEntries =
1039  count_if(DFSInStack, [](const StackEntry &E) { return E.IsSigned; });
1040  assert(Info.getCS(false).size() == DFSInStack.size() - SignedEntries &&
1041  "updates to CS and DFSInStack are out of sync");
1042  assert(Info.getCS(true).size() == SignedEntries &&
1043  "updates to CS and DFSInStack are out of sync");
1044 #endif
1045 
1046  for (Instruction *I : ToRemove)
1047  I->eraseFromParent();
1048  return Changed;
1049 }
1050 
1053  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
1054  if (!eliminateConstraints(F, DT))
1055  return PreservedAnalyses::all();
1056 
1057  PreservedAnalyses PA;
1059  PA.preserveSet<CFGAnalyses>();
1060  return PA;
1061 }
1062 
1063 namespace {
1064 
1065 class ConstraintElimination : public FunctionPass {
1066 public:
1067  static char ID;
1068 
1069  ConstraintElimination() : FunctionPass(ID) {
1071  }
1072 
1073  bool runOnFunction(Function &F) override {
1074  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1075  return eliminateConstraints(F, DT);
1076  }
1077 
1078  void getAnalysisUsage(AnalysisUsage &AU) const override {
1079  AU.setPreservesCFG();
1083  }
1084 };
1085 
1086 } // end anonymous namespace
1087 
1088 char ConstraintElimination::ID = 0;
1089 
1090 INITIALIZE_PASS_BEGIN(ConstraintElimination, "constraint-elimination",
1091  "Constraint Elimination", false, false)
1094 INITIALIZE_PASS_END(ConstraintElimination, "constraint-elimination",
1095  "Constraint Elimination", false, false)
1096 
1098  return new ConstraintElimination();
1099 }
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
Signed
@ Signed
Definition: NVPTXISelLowering.cpp:4715
MaxConstraintValue
static int64_t MaxConstraintValue
Definition: ConstraintElimination.cpp:48
llvm::initializeConstraintEliminationPass
void initializeConstraintEliminationPass(PassRegistry &)
llvm::CmpInst::getSwappedPredicate
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition: InstrTypes.h:849
MathExtras.h
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::CmpInst::ICMP_EQ
@ ICMP_EQ
equal
Definition: InstrTypes.h:740
llvm::isKnownNonNegative
bool isKnownNonNegative(const Value *V, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Returns true if the give value is known to be non-negative.
Definition: ValueTracking.cpp:322
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
llvm::AArch64PACKey::ID
ID
Definition: AArch64BaseInfo.h:818
Insert
Vector Rotate Left Mask Mask Insert
Definition: README_P9.txt:112
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:719
llvm::CmpInst::getUnsignedPredicate
Predicate getUnsignedPredicate()
For example, SLT->ULT, SLE->ULE, SGT->UGT, SGE->UGE, ULT->Failed assert.
Definition: InstrTypes.h:978
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
Scalar.h
checkAndReplaceCondition
static bool checkAndReplaceCondition(CmpInst *Cmp, ConstraintInfo &Info)
Definition: ConstraintElimination.cpp:755
llvm::Function
Definition: Function.h:60
llvm::PseudoProbeReservedId::Last
@ Last
Pass.h
llvm::IntrinsicInst::getIntrinsicID
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
Definition: IntrinsicInst.h:54
GetElementPtrTypeIterator.h
llvm::ConstantInt::getValue
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:133
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
Statistic.h
llvm::PatternMatch::m_Add
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
Definition: PatternMatch.h:979
llvm::APInt::getSExtValue
int64_t getSExtValue() const
Get sign extended value.
Definition: APInt.h:1498
llvm::CmpInst::makeCmpResultType
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
Definition: InstrTypes.h:1044
ToRemove
ReachingDefAnalysis InstSet & ToRemove
Definition: ARMLowOverheadLoops.cpp:547
llvm::IRBuilder<>
llvm::CmpInst::ICMP_NE
@ ICMP_NE
not equal
Definition: InstrTypes.h:741
llvm::MaxAnalysisRecursionDepth
constexpr unsigned MaxAnalysisRecursionDepth
Definition: ValueTracking.h:47
ValueTracking.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
GlobalsModRef.h
llvm::DenseMapBase::erase
bool erase(const KeyT &Val)
Definition: DenseMap.h:302
llvm::PatternMatch::m_NUWShl
OverflowingBinaryOp_match< LHS, RHS, Instruction::Shl, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWShl(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1213
llvm::CmpInst::ICMP_SGT
@ ICMP_SGT
signed greater than
Definition: InstrTypes.h:746
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
ConstraintElimination.h
llvm::DominatorTreeBase::getNode
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Definition: GenericDomTree.h:351
llvm::MapVector
This class implements a map that also provides access to all stored values in a deterministic order.
Definition: MapVector.h:37
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
DEBUG_COUNTER
DEBUG_COUNTER(EliminatedCounter, "conds-eliminated", "Controls which conditions are eliminated")
llvm::successors
auto successors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:29
llvm::CmpInst::ICMP_SLE
@ ICMP_SLE
signed less or equal
Definition: InstrTypes.h:749
llvm::max
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:337
STLExtras.h
llvm::CmpInst::getPredicateName
static StringRef getPredicateName(Predicate P)
Definition: Instructions.cpp:4097
dumpWithNames
static void dumpWithNames(const ConstraintSystem &CS, DenseMap< Value *, unsigned > &Value2Index)
Definition: ConstraintElimination.cpp:645
llvm::count_if
auto count_if(R &&Range, UnaryPredicate P)
Wrapper function around std::count_if to count the number of times an element satisfying a given pred...
Definition: STLExtras.h:1902
multiplyWithOverflow
static int64_t multiplyWithOverflow(int64_t A, int64_t B)
Definition: ConstraintElimination.cpp:52
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:265
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::DominatorTree::dominates
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:122
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
llvm::all_of
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1734
llvm::APInt::isNegative
bool isNegative() const
Determine sign of this APInt.
Definition: APInt.h:312
decompose
static Decomposition decompose(Value *V, SmallVectorImpl< PreconditionTy > &Preconditions, bool IsSigned, const DataLayout &DL)
Definition: ConstraintElimination.cpp:295
eliminateConstraints
static bool eliminateConstraints(Function &F, DominatorTree &DT)
Definition: ConstraintElimination.cpp:927
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:24
llvm::PatternMatch::match
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
llvm::ConstraintSystem
Definition: ConstraintSystem.h:20
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::User
Definition: User.h:44
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::CmpInst::ICMP_ULE
@ ICMP_ULE
unsigned less or equal
Definition: InstrTypes.h:745
llvm::ARM_PROC::A
@ A
Definition: ARMBaseInfo.h:34
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
false
Definition: StackSlotColoring.cpp:141
llvm::dwarf::Index
Index
Definition: Dwarf.h:490
llvm::PatternMatch::m_ZExt
CastClass_match< OpTy, Instruction::ZExt > m_ZExt(const OpTy &Op)
Matches ZExt.
Definition: PatternMatch.h:1629
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::PatternMatch::m_ConstantInt
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
Definition: PatternMatch.h:147
llvm::Instruction
Definition: Instruction.h:42
llvm::DebugCounter::shouldExecute
static bool shouldExecute(unsigned CounterName)
Definition: DebugCounter.h:72
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:306
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::predecessors
auto predecessors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:30
llvm::ConstantInt::get
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:879
llvm::Use::getUser
User * getUser() const
Returns the User that contains this Use.
Definition: Use.h:72
llvm::AddOverflow
std::enable_if_t< std::is_signed< T >::value, T > AddOverflow(T X, T Y, T &Result)
Add two signed integers, computing the two's complement truncated result, returning true if overflow ...
Definition: MathExtras.h:837
Info
Analysis containing CSE Info
Definition: CSEInfo.cpp:27
llvm::DominatorTreeBase::updateDFSNumbers
void updateDFSNumbers() const
updateDFSNumbers - Assign In and Out numbers to the nodes while walking dominator tree in dfs order.
Definition: GenericDomTree.h:732
PatternMatch.h
llvm::Value::use_empty
bool use_empty() const
Definition: Value.h:344
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
llvm::RISCVII::getConstraint
static VConstraintType getConstraint(uint64_t TSFlags)
Definition: RISCVBaseInfo.h:130
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
llvm::dxil::PointerTypeAnalysis::run
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
Definition: PointerTypeAnalysis.cpp:189
llvm::PatternMatch::m_NSWAdd
OverflowingBinaryOp_match< LHS, RHS, Instruction::Add, OverflowingBinaryOperator::NoSignedWrap > m_NSWAdd(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1156
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(ConstraintElimination, "constraint-elimination", "Constraint Elimination", false, false) INITIALIZE_PASS_END(ConstraintElimination
llvm::CmpInst
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:709
llvm::Value::stripPointerCastsSameRepresentation
const Value * stripPointerCastsSameRepresentation() const
Strip off pointer casts, all-zero GEPs and address space casts but ensures the representation of the ...
Definition: Value.cpp:693
llvm::APInt::slt
bool slt(const APInt &RHS) const
Signed less than comparison.
Definition: APInt.h:1100
ConstraintSystem.h
llvm::PPC::Predicate
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
Definition: PPCPredicates.h:26
llvm::PatternMatch::m_Zero
is_zero m_Zero()
Match any null constant or a vector with all elements equal to 0.
Definition: PatternMatch.h:537
llvm::PatternMatch::m_NUWAdd
OverflowingBinaryOp_match< LHS, RHS, Instruction::Add, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWAdd(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1189
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:81
llvm::ConstraintSystem::negate
static SmallVector< int64_t, 8 > negate(SmallVector< int64_t, 8 > R)
Definition: ConstraintSystem.h:71
llvm::AMDGPU::Hwreg::Offset
Offset
Definition: SIDefines.h:419
llvm::ConstraintSystem::popLastConstraint
void popLastConstraint()
Definition: ConstraintSystem.h:83
llvm::PatternMatch::m_LogicalOr
LogicalOp_match< LHS, RHS, Instruction::Or > m_LogicalOr(const LHS &L, const RHS &R)
Matches L || R either in the form of L | R or L ? true : R.
Definition: PatternMatch.h:2572
llvm::LazyValueInfoWrapperPass
Wrapper around LazyValueInfo.
Definition: LazyValueInfo.h:145
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::PreservedAnalyses::preserve
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:173
llvm::ARM_AM::add
@ add
Definition: ARMAddressingModes.h:39
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::DenseMap< Value *, unsigned >
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::GetElementPtrInst
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:929
llvm::make_early_inc_range
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:716
canUseSExt
static bool canUseSExt(ConstantInt *CI)
Definition: ConstraintElimination.cpp:229
llvm::DenseMapBase::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
IRBuilder.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:853
llvm::CmpInst::ICMP_UGE
@ ICMP_UGE
unsigned greater or equal
Definition: InstrTypes.h:743
elimination
constraint elimination
Definition: ConstraintElimination.cpp:1094
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:651
llvm::PatternMatch::m_Value
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:76
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
llvm::CmpInst::ICMP_SLT
@ ICMP_SLT
signed less than
Definition: InstrTypes.h:748
llvm::size
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
Definition: STLExtras.h:1715
llvm::PatternMatch::m_NUWMul
OverflowingBinaryOp_match< LHS, RHS, Instruction::Mul, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWMul(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1205
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::min
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:357
llvm::any_of
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1741
DataLayout.h
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:138
replaceSubOverflowUses
static bool replaceSubOverflowUses(IntrinsicInst *II, Value *A, Value *B, SmallVectorImpl< Instruction * > &ToRemove)
Definition: ConstraintElimination.cpp:867
llvm::AnalysisUsage::setPreservesCFG
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:265
llvm::CmpInst::ICMP_ULT
@ ICMP_ULT
unsigned less than
Definition: InstrTypes.h:744
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
llvm::CFGAnalyses
Represents analyses that only rely on functions' control flow.
Definition: PassManager.h:113
if
if(llvm_vc STREQUAL "") set(fake_version_inc "$
Definition: CMakeLists.txt:14
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
A
* A
Definition: README_ALTIVEC.txt:89
llvm::append_range
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:2013
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:82
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::DominatorTreeBase::properlyDominates
bool properlyDominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
properlyDominates - Returns true iff A dominates B and A != B.
Definition: GenericDomTree.h:392
MinSignedConstraintValue
static int64_t MinSignedConstraintValue
Definition: ConstraintElimination.cpp:49
llvm::ConstantInt::getSExtValue
int64_t getSExtValue() const
Return the constant as a 64-bit integer value after it has been sign extended as appropriate for the ...
Definition: Constants.h:148
llvm::DomTreeNodeBase< BasicBlock >
llvm::DenseMapBase::insert
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:207
llvm::ConstantInt::getFalse
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:834
llvm::make_scope_exit
detail::scope_exit< std::decay_t< Callable > > make_scope_exit(Callable &&F)
Definition: ScopeExit.h:59
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:85
llvm::MapVector::empty
bool empty() const
Definition: MapVector.h:80
llvm::MipsISD::Mult
@ Mult
Definition: MipsISelLowering.h:135
llvm::stable_sort
void stable_sort(R &&Range)
Definition: STLExtras.h:1947
decomposeGEP
static Decomposition decomposeGEP(GetElementPtrInst &GEP, SmallVectorImpl< PreconditionTy > &Preconditions, bool IsSigned, const DataLayout &DL)
Definition: ConstraintElimination.cpp:235
tryToSimplifyOverflowMath
static bool tryToSimplifyOverflowMath(IntrinsicInst *II, ConstraintInfo &Info, SmallVectorImpl< Instruction * > &ToRemove)
Definition: ConstraintElimination.cpp:900
llvm::ConstantInt::getTrue
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:827
llvm::Successor
@ Successor
Definition: SIMachineScheduler.h:35
llvm::DenseMapBase::end
iterator end()
Definition: DenseMap.h:84
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
llvm::X86::FirstMacroFusionInstKind::Cmp
@ Cmp
llvm::isGuaranteedToTransferExecutionToSuccessor
bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
Definition: ValueTracking.cpp:5496
llvm::MulOverflow
std::enable_if_t< std::is_signed< T >::value, T > MulOverflow(T X, T Y, T &Result)
Multiply two signed integers, computing the two's complement truncated result, returning true if an o...
Definition: MathExtras.h:889
Function.h
llvm::BitWidth
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:147
DebugCounter.h
llvm::DenseMapBase::size
unsigned size() const
Definition: DenseMap.h:99
llvm::CmpInst::isSigned
bool isSigned() const
Definition: InstrTypes.h:947
addWithOverflow
static int64_t addWithOverflow(int64_t A, int64_t B)
Definition: ConstraintElimination.cpp:59
llvm::CmpInst::ICMP_SGE
@ ICMP_SGE
signed greater or equal
Definition: InstrTypes.h:747
llvm::IntrinsicInst
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:47
llvm::PatternMatch::m_NUWSub
OverflowingBinaryOp_match< LHS, RHS, Instruction::Sub, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWSub(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1197
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:271
isValid
static bool isValid(const char C)
Returns true if C is a valid mangled character: <0-9a-zA-Z_>.
Definition: RustDemangle.cpp:184
Instructions.h
llvm::PreservedAnalyses::preserveSet
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:188
llvm::createConstraintEliminationPass
FunctionPass * createConstraintEliminationPass()
Definition: ConstraintElimination.cpp:1097
Other
std::optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1252
llvm::ConstantInt::isNegative
bool isNegative() const
Definition: Constants.h:189
SmallVector.h
llvm::PatternMatch::m_ICmp
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
Definition: PatternMatch.h:1394
llvm::CmpInst::ICMP_UGT
@ ICMP_UGT
unsigned greater than
Definition: InstrTypes.h:742
Dominators.h
llvm::CallBase::getArgOperand
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1341
N
#define N
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:91
llvm::SmallVectorImpl::pop_back_val
T pop_back_val()
Definition: SmallVector.h:677
llvm::GlobalsAAWrapperPass
Legacy wrapper pass to provide the GlobalsAAResult object.
Definition: GlobalsModRef.h:142
llvm::ConstraintSystem::addVariableRowFill
bool addVariableRowFill(ArrayRef< int64_t > R)
Definition: ConstraintSystem.h:55
llvm::logicalview::LVComparePass::Added
@ Added
ScopeExit.h
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
llvm::APInt::sgt
bool sgt(const APInt &RHS) const
Signed greater than comparison.
Definition: APInt.h:1171
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
GEP
Hexagon Common GEP
Definition: HexagonCommonGEP.cpp:171
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
Debug.h
llvm::Value::users
iterator_range< user_iterator > users()
Definition: Value.h:421
Elimination
constraint Constraint Elimination
Definition: ConstraintElimination.cpp:1095
llvm::PatternMatch::m_LogicalAnd
LogicalOp_match< LHS, RHS, Instruction::And > m_LogicalAnd(const LHS &L, const RHS &R)
Matches L && R either in the form of L & R or L ? R : false.
Definition: PatternMatch.h:2554
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
llvm::SmallVectorImpl::emplace_back
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:941
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365
llvm::PoisonValue::get
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1732