LLVM  15.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/Dominators.h"
23 #include "llvm/IR/Function.h"
24 #include "llvm/IR/IRBuilder.h"
25 #include "llvm/IR/Instructions.h"
26 #include "llvm/IR/PatternMatch.h"
27 #include "llvm/InitializePasses.h"
28 #include "llvm/Pass.h"
29 #include "llvm/Support/Debug.h"
32 #include "llvm/Transforms/Scalar.h"
33 
34 #include <string>
35 
36 using namespace llvm;
37 using namespace PatternMatch;
38 
39 #define DEBUG_TYPE "constraint-elimination"
40 
41 STATISTIC(NumCondsRemoved, "Number of instructions removed");
42 DEBUG_COUNTER(EliminatedCounter, "conds-eliminated",
43  "Controls which conditions are eliminated");
44 
47 
48 namespace {
49 
50 class ConstraintInfo;
51 
52 struct StackEntry {
53  unsigned NumIn;
54  unsigned NumOut;
55  bool IsNot;
56  bool IsSigned = false;
57  /// Variables that can be removed from the system once the stack entry gets
58  /// removed.
59  SmallVector<Value *, 2> ValuesToRelease;
60 
61  StackEntry(unsigned NumIn, unsigned NumOut, bool IsNot, bool IsSigned,
62  SmallVector<Value *, 2> ValuesToRelease)
63  : NumIn(NumIn), NumOut(NumOut), IsNot(IsNot), IsSigned(IsSigned),
64  ValuesToRelease(ValuesToRelease) {}
65 };
66 
67 /// Struct to express a pre-condition of the form %Op0 Pred %Op1.
68 struct PreconditionTy {
69  CmpInst::Predicate Pred;
70  Value *Op0;
71  Value *Op1;
72 
73  PreconditionTy(CmpInst::Predicate Pred, Value *Op0, Value *Op1)
74  : Pred(Pred), Op0(Op0), Op1(Op1) {}
75 };
76 
77 struct ConstraintTy {
78  SmallVector<int64_t, 8> Coefficients;
79  SmallVector<PreconditionTy, 2> Preconditions;
80 
81  bool IsSigned = false;
82  bool IsEq = false;
83 
84  ConstraintTy() = default;
85 
86  ConstraintTy(SmallVector<int64_t, 8> Coefficients, bool IsSigned)
87  : Coefficients(Coefficients), IsSigned(IsSigned) {}
88 
89  unsigned size() const { return Coefficients.size(); }
90 
91  unsigned empty() const { return Coefficients.empty(); }
92 
93  /// Returns true if any constraint has a non-zero coefficient for any of the
94  /// newly added indices. Zero coefficients for new indices are removed. If it
95  /// returns true, no new variable need to be added to the system.
96  bool needsNewIndices(const DenseMap<Value *, unsigned> &NewIndices) {
97  for (unsigned I = 0; I < NewIndices.size(); ++I) {
98  int64_t Last = Coefficients.pop_back_val();
99  if (Last != 0)
100  return true;
101  }
102  return false;
103  }
104 
105  /// Returns true if all preconditions for this list of constraints are
106  /// satisfied given \p CS and the corresponding \p Value2Index mapping.
107  bool isValid(const ConstraintInfo &Info) const;
108 };
109 
110 /// Wrapper encapsulating separate constraint systems and corresponding value
111 /// mappings for both unsigned and signed information. Facts are added to and
112 /// conditions are checked against the corresponding system depending on the
113 /// signed-ness of their predicates. While the information is kept separate
114 /// based on signed-ness, certain conditions can be transferred between the two
115 /// systems.
116 class ConstraintInfo {
117  DenseMap<Value *, unsigned> UnsignedValue2Index;
118  DenseMap<Value *, unsigned> SignedValue2Index;
119 
120  ConstraintSystem UnsignedCS;
121  ConstraintSystem SignedCS;
122 
123 public:
124  DenseMap<Value *, unsigned> &getValue2Index(bool Signed) {
125  return Signed ? SignedValue2Index : UnsignedValue2Index;
126  }
127  const DenseMap<Value *, unsigned> &getValue2Index(bool Signed) const {
128  return Signed ? SignedValue2Index : UnsignedValue2Index;
129  }
130 
131  ConstraintSystem &getCS(bool Signed) {
132  return Signed ? SignedCS : UnsignedCS;
133  }
134  const ConstraintSystem &getCS(bool Signed) const {
135  return Signed ? SignedCS : UnsignedCS;
136  }
137 
138  void popLastConstraint(bool Signed) { getCS(Signed).popLastConstraint(); }
139  void popLastNVariables(bool Signed, unsigned N) {
140  getCS(Signed).popLastNVariables(N);
141  }
142 
143  bool doesHold(CmpInst::Predicate Pred, Value *A, Value *B) const;
144 
145  void addFact(CmpInst::Predicate Pred, Value *A, Value *B, bool IsNegated,
146  unsigned NumIn, unsigned NumOut,
147  SmallVectorImpl<StackEntry> &DFSInStack);
148 
149  /// Turn a comparison of the form \p Op0 \p Pred \p Op1 into a vector of
150  /// constraints, using indices from the corresponding constraint system.
151  /// Additional indices for newly discovered values are added to \p NewIndices.
152  ConstraintTy getConstraint(CmpInst::Predicate Pred, Value *Op0, Value *Op1,
153  DenseMap<Value *, unsigned> &NewIndices) const;
154 
155  /// Turn a condition \p CmpI into a vector of constraints, using indices from
156  /// the corresponding constraint system. Additional indices for newly
157  /// discovered values are added to \p NewIndices.
158  ConstraintTy getConstraint(CmpInst *Cmp,
159  DenseMap<Value *, unsigned> &NewIndices) const {
160  return getConstraint(Cmp->getPredicate(), Cmp->getOperand(0),
161  Cmp->getOperand(1), NewIndices);
162  }
163 
164  /// Try to add information from \p A \p Pred \p B to the unsigned/signed
165  /// system if \p Pred is signed/unsigned.
166  void transferToOtherSystem(CmpInst::Predicate Pred, Value *A, Value *B,
167  bool IsNegated, unsigned NumIn, unsigned NumOut,
168  SmallVectorImpl<StackEntry> &DFSInStack);
169 };
170 
171 } // namespace
172 
173 // Decomposes \p V into a vector of pairs of the form { c, X } where c * X. The
174 // sum of the pairs equals \p V. The first pair is the constant-factor and X
175 // must be nullptr. If the expression cannot be decomposed, returns an empty
176 // vector.
179  bool IsSigned) {
180 
181  auto CanUseSExt = [](ConstantInt *CI) {
182  const APInt &Val = CI->getValue();
184  };
185  // Decompose \p V used with a signed predicate.
186  if (IsSigned) {
187  if (auto *CI = dyn_cast<ConstantInt>(V)) {
188  if (CanUseSExt(CI))
189  return {{CI->getSExtValue(), nullptr}};
190  }
191 
192  return {{0, nullptr}, {1, V}};
193  }
194 
195  if (auto *CI = dyn_cast<ConstantInt>(V)) {
196  if (CI->uge(MaxConstraintValue))
197  return {};
198  return {{CI->getZExtValue(), nullptr}};
199  }
200  auto *GEP = dyn_cast<GetElementPtrInst>(V);
201  if (GEP && GEP->getNumOperands() == 2 && GEP->isInBounds()) {
202  Value *Op0, *Op1;
203  ConstantInt *CI;
204 
205  // If the index is zero-extended, it is guaranteed to be positive.
206  if (match(GEP->getOperand(GEP->getNumOperands() - 1),
207  m_ZExt(m_Value(Op0)))) {
208  if (match(Op0, m_NUWShl(m_Value(Op1), m_ConstantInt(CI))) &&
209  CanUseSExt(CI))
210  return {{0, nullptr},
211  {1, GEP->getPointerOperand()},
212  {std::pow(int64_t(2), CI->getSExtValue()), Op1}};
213  if (match(Op0, m_NSWAdd(m_Value(Op1), m_ConstantInt(CI))) &&
214  CanUseSExt(CI))
215  return {{CI->getSExtValue(), nullptr},
216  {1, GEP->getPointerOperand()},
217  {1, Op1}};
218  return {{0, nullptr}, {1, GEP->getPointerOperand()}, {1, Op0}};
219  }
220 
221  if (match(GEP->getOperand(GEP->getNumOperands() - 1), m_ConstantInt(CI)) &&
222  !CI->isNegative() && CanUseSExt(CI))
223  return {{CI->getSExtValue(), nullptr}, {1, GEP->getPointerOperand()}};
224 
226  if (match(GEP->getOperand(GEP->getNumOperands() - 1),
227  m_NUWShl(m_Value(Op0), m_ConstantInt(CI))) &&
228  CanUseSExt(CI))
229  Result = {{0, nullptr},
230  {1, GEP->getPointerOperand()},
231  {std::pow(int64_t(2), CI->getSExtValue()), Op0}};
232  else if (match(GEP->getOperand(GEP->getNumOperands() - 1),
233  m_NSWAdd(m_Value(Op0), m_ConstantInt(CI))) &&
234  CanUseSExt(CI))
235  Result = {{CI->getSExtValue(), nullptr},
236  {1, GEP->getPointerOperand()},
237  {1, Op0}};
238  else {
239  Op0 = GEP->getOperand(GEP->getNumOperands() - 1);
240  Result = {{0, nullptr}, {1, GEP->getPointerOperand()}, {1, Op0}};
241  }
242  // If Op0 is signed non-negative, the GEP is increasing monotonically and
243  // can be de-composed.
244  Preconditions.emplace_back(CmpInst::ICMP_SGE, Op0,
245  ConstantInt::get(Op0->getType(), 0));
246  return Result;
247  }
248 
249  Value *Op0;
250  if (match(V, m_ZExt(m_Value(Op0))))
251  V = Op0;
252 
253  Value *Op1;
254  ConstantInt *CI;
255  if (match(V, m_NUWAdd(m_Value(Op0), m_ConstantInt(CI))) &&
256  !CI->uge(MaxConstraintValue))
257  return {{CI->getZExtValue(), nullptr}, {1, Op0}};
258  if (match(V, m_Add(m_Value(Op0), m_ConstantInt(CI))) && CI->isNegative() &&
259  CanUseSExt(CI)) {
260  Preconditions.emplace_back(
261  CmpInst::ICMP_UGE, Op0,
262  ConstantInt::get(Op0->getType(), CI->getSExtValue() * -1));
263  return {{CI->getSExtValue(), nullptr}, {1, Op0}};
264  }
265  if (match(V, m_NUWAdd(m_Value(Op0), m_Value(Op1))))
266  return {{0, nullptr}, {1, Op0}, {1, Op1}};
267 
268  if (match(V, m_NUWSub(m_Value(Op0), m_ConstantInt(CI))) && CanUseSExt(CI))
269  return {{-1 * CI->getSExtValue(), nullptr}, {1, Op0}};
270  if (match(V, m_NUWSub(m_Value(Op0), m_Value(Op1))))
271  return {{0, nullptr}, {1, Op0}, {-1, Op1}};
272 
273  return {{0, nullptr}, {1, V}};
274 }
275 
276 ConstraintTy
278  DenseMap<Value *, unsigned> &NewIndices) const {
279  bool IsEq = false;
280  // Try to convert Pred to one of ULE/SLT/SLE/SLT.
281  switch (Pred) {
282  case CmpInst::ICMP_UGT:
283  case CmpInst::ICMP_UGE:
284  case CmpInst::ICMP_SGT:
285  case CmpInst::ICMP_SGE: {
286  Pred = CmpInst::getSwappedPredicate(Pred);
287  std::swap(Op0, Op1);
288  break;
289  }
290  case CmpInst::ICMP_EQ:
291  if (match(Op1, m_Zero())) {
292  Pred = CmpInst::ICMP_ULE;
293  } else {
294  IsEq = true;
295  Pred = CmpInst::ICMP_ULE;
296  }
297  break;
298  case CmpInst::ICMP_NE:
299  if (!match(Op1, m_Zero()))
300  return {};
302  std::swap(Op0, Op1);
303  break;
304  default:
305  break;
306  }
307 
308  // Only ULE and ULT predicates are supported at the moment.
309  if (Pred != CmpInst::ICMP_ULE && Pred != CmpInst::ICMP_ULT &&
310  Pred != CmpInst::ICMP_SLE && Pred != CmpInst::ICMP_SLT)
311  return {};
312 
313  SmallVector<PreconditionTy, 4> Preconditions;
314  bool IsSigned = CmpInst::isSigned(Pred);
315  auto &Value2Index = getValue2Index(IsSigned);
317  Preconditions, IsSigned);
319  Preconditions, IsSigned);
320  // Skip if decomposing either of the values failed.
321  if (ADec.empty() || BDec.empty())
322  return {};
323 
324  int64_t Offset1 = ADec[0].first;
325  int64_t Offset2 = BDec[0].first;
326  Offset1 *= -1;
327 
328  // Create iterator ranges that skip the constant-factor.
329  auto VariablesA = llvm::drop_begin(ADec);
330  auto VariablesB = llvm::drop_begin(BDec);
331 
332  // First try to look up \p V in Value2Index and NewIndices. Otherwise add a
333  // new entry to NewIndices.
334  auto GetOrAddIndex = [&Value2Index, &NewIndices](Value *V) -> unsigned {
335  auto V2I = Value2Index.find(V);
336  if (V2I != Value2Index.end())
337  return V2I->second;
338  auto Insert =
339  NewIndices.insert({V, Value2Index.size() + NewIndices.size() + 1});
340  return Insert.first->second;
341  };
342 
343  // Make sure all variables have entries in Value2Index or NewIndices.
344  for (const auto &KV :
345  concat<std::pair<int64_t, Value *>>(VariablesA, VariablesB))
346  GetOrAddIndex(KV.second);
347 
348  // Build result constraint, by first adding all coefficients from A and then
349  // subtracting all coefficients from B.
350  ConstraintTy Res(
351  SmallVector<int64_t, 8>(Value2Index.size() + NewIndices.size() + 1, 0),
352  IsSigned);
353  Res.IsEq = IsEq;
354  auto &R = Res.Coefficients;
355  for (const auto &KV : VariablesA)
356  R[GetOrAddIndex(KV.second)] += KV.first;
357 
358  for (const auto &KV : VariablesB)
359  R[GetOrAddIndex(KV.second)] -= KV.first;
360 
361  int64_t OffsetSum;
362  if (AddOverflow(Offset1, Offset2, OffsetSum))
363  return {};
364  if (Pred == (IsSigned ? CmpInst::ICMP_SLT : CmpInst::ICMP_ULT))
365  if (AddOverflow(OffsetSum, int64_t(-1), OffsetSum))
366  return {};
367  R[0] = OffsetSum;
368  Res.Preconditions = std::move(Preconditions);
369  return Res;
370 }
371 
372 bool ConstraintTy::isValid(const ConstraintInfo &Info) const {
373  return Coefficients.size() > 0 &&
374  all_of(Preconditions, [&Info](const PreconditionTy &C) {
375  return Info.doesHold(C.Pred, C.Op0, C.Op1);
376  });
377 }
378 
379 bool ConstraintInfo::doesHold(CmpInst::Predicate Pred, Value *A,
380  Value *B) const {
381  DenseMap<Value *, unsigned> NewIndices;
382  auto R = getConstraint(Pred, A, B, NewIndices);
383 
384  if (!NewIndices.empty())
385  return false;
386 
387  // TODO: properly check NewIndices.
388  return NewIndices.empty() && R.Preconditions.empty() && !R.IsEq &&
389  !R.empty() &&
390  getCS(CmpInst::isSigned(Pred)).isConditionImplied(R.Coefficients);
391 }
392 
393 void ConstraintInfo::transferToOtherSystem(
394  CmpInst::Predicate Pred, Value *A, Value *B, bool IsNegated, unsigned NumIn,
395  unsigned NumOut, SmallVectorImpl<StackEntry> &DFSInStack) {
396  // Check if we can combine facts from the signed and unsigned systems to
397  // derive additional facts.
398  if (!A->getType()->isIntegerTy())
399  return;
400  // FIXME: This currently depends on the order we add facts. Ideally we
401  // would first add all known facts and only then try to add additional
402  // facts.
403  switch (Pred) {
404  default:
405  break;
406  case CmpInst::ICMP_ULT:
407  // If B is a signed positive constant, A >=s 0 and A <s B.
408  if (doesHold(CmpInst::ICMP_SGE, B, ConstantInt::get(B->getType(), 0))) {
409  addFact(CmpInst::ICMP_SGE, A, ConstantInt::get(B->getType(), 0),
410  IsNegated, NumIn, NumOut, DFSInStack);
411  addFact(CmpInst::ICMP_SLT, A, B, IsNegated, NumIn, NumOut, DFSInStack);
412  }
413  break;
414  case CmpInst::ICMP_SLT:
415  if (doesHold(CmpInst::ICMP_SGE, A, ConstantInt::get(B->getType(), 0)))
416  addFact(CmpInst::ICMP_ULT, A, B, IsNegated, NumIn, NumOut, DFSInStack);
417  break;
418  case CmpInst::ICMP_SGT:
419  if (doesHold(CmpInst::ICMP_SGE, B, ConstantInt::get(B->getType(), -1)))
420  addFact(CmpInst::ICMP_UGE, A, ConstantInt::get(B->getType(), 0),
421  IsNegated, NumIn, NumOut, DFSInStack);
422  break;
423  case CmpInst::ICMP_SGE:
424  if (doesHold(CmpInst::ICMP_SGE, B, ConstantInt::get(B->getType(), 0))) {
425  addFact(CmpInst::ICMP_UGE, A, B, IsNegated, NumIn, NumOut, DFSInStack);
426  }
427  break;
428  }
429 }
430 
431 namespace {
432 /// Represents either a condition that holds on entry to a block or a basic
433 /// block, with their respective Dominator DFS in and out numbers.
434 struct ConstraintOrBlock {
435  unsigned NumIn;
436  unsigned NumOut;
437  bool IsBlock;
438  bool Not;
439  union {
440  BasicBlock *BB;
441  CmpInst *Condition;
442  };
443 
444  ConstraintOrBlock(DomTreeNode *DTN)
445  : NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()), IsBlock(true),
446  BB(DTN->getBlock()) {}
447  ConstraintOrBlock(DomTreeNode *DTN, CmpInst *Condition, bool Not)
448  : NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()), IsBlock(false),
449  Not(Not), Condition(Condition) {}
450 };
451 
452 /// Keep state required to build worklist.
453 struct State {
454  DominatorTree &DT;
456 
457  State(DominatorTree &DT) : DT(DT) {}
458 
459  /// Process block \p BB and add known facts to work-list.
460  void addInfoFor(BasicBlock &BB);
461 
462  /// Returns true if we can add a known condition from BB to its successor
463  /// block Succ. Each predecessor of Succ can either be BB or be dominated
464  /// by Succ (e.g. the case when adding a condition from a pre-header to a
465  /// loop header).
466  bool canAddSuccessor(BasicBlock &BB, BasicBlock *Succ) const {
467  if (BB.getSingleSuccessor()) {
468  assert(BB.getSingleSuccessor() == Succ);
469  return DT.properlyDominates(&BB, Succ);
470  }
471  return any_of(successors(&BB),
472  [Succ](const BasicBlock *S) { return S != Succ; }) &&
473  all_of(predecessors(Succ), [&BB, Succ, this](BasicBlock *Pred) {
474  return Pred == &BB || DT.dominates(Succ, Pred);
475  });
476  }
477 };
478 
479 } // namespace
480 
481 #ifndef NDEBUG
482 static void dumpWithNames(const ConstraintSystem &CS,
483  DenseMap<Value *, unsigned> &Value2Index) {
484  SmallVector<std::string> Names(Value2Index.size(), "");
485  for (auto &KV : Value2Index) {
486  Names[KV.second - 1] = std::string("%") + KV.first->getName().str();
487  }
488  CS.dump(Names);
489 }
490 
492  DenseMap<Value *, unsigned> &Value2Index) {
493  ConstraintSystem CS;
494  CS.addVariableRowFill(C);
495  dumpWithNames(CS, Value2Index);
496 }
497 #endif
498 
499 void State::addInfoFor(BasicBlock &BB) {
500  WorkList.emplace_back(DT.getNode(&BB));
501 
502  // True as long as long as the current instruction is guaranteed to execute.
503  bool GuaranteedToExecute = true;
504  // Scan BB for assume calls.
505  // TODO: also use this scan to queue conditions to simplify, so we can
506  // interleave facts from assumes and conditions to simplify in a single
507  // basic block. And to skip another traversal of each basic block when
508  // simplifying.
509  for (Instruction &I : BB) {
510  Value *Cond;
511  // For now, just handle assumes with a single compare as condition.
512  if (match(&I, m_Intrinsic<Intrinsic::assume>(m_Value(Cond))) &&
513  isa<ICmpInst>(Cond)) {
514  if (GuaranteedToExecute) {
515  // The assume is guaranteed to execute when BB is entered, hence Cond
516  // holds on entry to BB.
517  WorkList.emplace_back(DT.getNode(&BB), cast<ICmpInst>(Cond), false);
518  } else {
519  // Otherwise the condition only holds in the successors.
520  for (BasicBlock *Succ : successors(&BB)) {
521  if (!canAddSuccessor(BB, Succ))
522  continue;
523  WorkList.emplace_back(DT.getNode(Succ), cast<ICmpInst>(Cond), false);
524  }
525  }
526  }
527  GuaranteedToExecute &= isGuaranteedToTransferExecutionToSuccessor(&I);
528  }
529 
530  auto *Br = dyn_cast<BranchInst>(BB.getTerminator());
531  if (!Br || !Br->isConditional())
532  return;
533 
534  // If the condition is an OR of 2 compares and the false successor only has
535  // the current block as predecessor, queue both negated conditions for the
536  // false successor.
537  Value *Op0, *Op1;
538  if (match(Br->getCondition(), m_LogicalOr(m_Value(Op0), m_Value(Op1))) &&
539  isa<ICmpInst>(Op0) && isa<ICmpInst>(Op1)) {
540  BasicBlock *FalseSuccessor = Br->getSuccessor(1);
541  if (canAddSuccessor(BB, FalseSuccessor)) {
542  WorkList.emplace_back(DT.getNode(FalseSuccessor), cast<ICmpInst>(Op0),
543  true);
544  WorkList.emplace_back(DT.getNode(FalseSuccessor), cast<ICmpInst>(Op1),
545  true);
546  }
547  return;
548  }
549 
550  // If the condition is an AND of 2 compares and the true successor only has
551  // the current block as predecessor, queue both conditions for the true
552  // successor.
553  if (match(Br->getCondition(), m_LogicalAnd(m_Value(Op0), m_Value(Op1))) &&
554  isa<ICmpInst>(Op0) && isa<ICmpInst>(Op1)) {
555  BasicBlock *TrueSuccessor = Br->getSuccessor(0);
556  if (canAddSuccessor(BB, TrueSuccessor)) {
557  WorkList.emplace_back(DT.getNode(TrueSuccessor), cast<ICmpInst>(Op0),
558  false);
559  WorkList.emplace_back(DT.getNode(TrueSuccessor), cast<ICmpInst>(Op1),
560  false);
561  }
562  return;
563  }
564 
565  auto *CmpI = dyn_cast<ICmpInst>(Br->getCondition());
566  if (!CmpI)
567  return;
568  if (canAddSuccessor(BB, Br->getSuccessor(0)))
569  WorkList.emplace_back(DT.getNode(Br->getSuccessor(0)), CmpI, false);
570  if (canAddSuccessor(BB, Br->getSuccessor(1)))
571  WorkList.emplace_back(DT.getNode(Br->getSuccessor(1)), CmpI, true);
572 }
573 
574 void ConstraintInfo::addFact(CmpInst::Predicate Pred, Value *A, Value *B,
575  bool IsNegated, unsigned NumIn, unsigned NumOut,
576  SmallVectorImpl<StackEntry> &DFSInStack) {
577  // If the constraint has a pre-condition, skip the constraint if it does not
578  // hold.
579  DenseMap<Value *, unsigned> NewIndices;
580  auto R = getConstraint(Pred, A, B, NewIndices);
581  if (!R.isValid(*this))
582  return;
583 
584  //LLVM_DEBUG(dbgs() << "Adding " << *Condition << " " << IsNegated << "\n");
585  bool Added = false;
586  assert(CmpInst::isSigned(Pred) == R.IsSigned &&
587  "condition and constraint signs must match");
588  auto &CSToUse = getCS(R.IsSigned);
589  if (R.Coefficients.empty())
590  return;
591 
592  Added |= CSToUse.addVariableRowFill(R.Coefficients);
593 
594  // If R has been added to the system, queue it for removal once it goes
595  // out-of-scope.
596  if (Added) {
597  SmallVector<Value *, 2> ValuesToRelease;
598  for (auto &KV : NewIndices) {
599  getValue2Index(R.IsSigned).insert(KV);
600  ValuesToRelease.push_back(KV.first);
601  }
602 
603  LLVM_DEBUG({
604  dbgs() << " constraint: ";
605  dumpWithNames(R.Coefficients, getValue2Index(R.IsSigned));
606  });
607 
608  DFSInStack.emplace_back(NumIn, NumOut, IsNegated, R.IsSigned,
609  ValuesToRelease);
610 
611  if (R.IsEq) {
612  // Also add the inverted constraint for equality constraints.
613  for (auto &Coeff : R.Coefficients)
614  Coeff *= -1;
615  CSToUse.addVariableRowFill(R.Coefficients);
616 
617  DFSInStack.emplace_back(NumIn, NumOut, IsNegated, R.IsSigned,
619  }
620  }
621 }
622 
623 static void
626  auto DoesConditionHold = [](CmpInst::Predicate Pred, Value *A, Value *B,
627  ConstraintInfo &Info) {
628  DenseMap<Value *, unsigned> NewIndices;
629  auto R = Info.getConstraint(Pred, A, B, NewIndices);
630  if (R.size() < 2 || R.needsNewIndices(NewIndices) || !R.isValid(Info))
631  return false;
632 
633  auto &CSToUse = Info.getCS(CmpInst::isSigned(Pred));
634  return CSToUse.isConditionImplied(R.Coefficients);
635  };
636 
637  if (II->getIntrinsicID() == Intrinsic::ssub_with_overflow) {
638  // If A s>= B && B s>= 0, ssub.with.overflow(a, b) should not overflow and
639  // can be simplified to a regular sub.
640  Value *A = II->getArgOperand(0);
641  Value *B = II->getArgOperand(1);
642  if (!DoesConditionHold(CmpInst::ICMP_SGE, A, B, Info) ||
643  !DoesConditionHold(CmpInst::ICMP_SGE, B,
644  ConstantInt::get(A->getType(), 0), Info))
645  return;
646 
648  Value *Sub = nullptr;
649  for (User *U : make_early_inc_range(II->users())) {
650  if (match(U, m_ExtractValue<0>(m_Value()))) {
651  if (!Sub)
652  Sub = Builder.CreateSub(A, B);
653  U->replaceAllUsesWith(Sub);
654  } else if (match(U, m_ExtractValue<1>(m_Value())))
655  U->replaceAllUsesWith(Builder.getFalse());
656  else
657  continue;
658 
659  if (U->use_empty()) {
660  auto *I = cast<Instruction>(U);
661  ToRemove.push_back(I);
662  I->setOperand(0, PoisonValue::get(II->getType()));
663  }
664  }
665 
666  if (II->use_empty())
667  II->eraseFromParent();
668  }
669 }
670 
672  bool Changed = false;
673  DT.updateDFSNumbers();
674 
675  ConstraintInfo Info;
676  State S(DT);
677 
678  // First, collect conditions implied by branches and blocks with their
679  // Dominator DFS in and out numbers.
680  for (BasicBlock &BB : F) {
681  if (!DT.getNode(&BB))
682  continue;
683  S.addInfoFor(BB);
684  }
685 
686  // Next, sort worklist by dominance, so that dominating blocks and conditions
687  // come before blocks and conditions dominated by them. If a block and a
688  // condition have the same numbers, the condition comes before the block, as
689  // it holds on entry to the block.
690  stable_sort(S.WorkList, [](const ConstraintOrBlock &A, const ConstraintOrBlock &B) {
691  return std::tie(A.NumIn, A.IsBlock) < std::tie(B.NumIn, B.IsBlock);
692  });
693 
695 
696  // Finally, process ordered worklist and eliminate implied conditions.
697  SmallVector<StackEntry, 16> DFSInStack;
698  for (ConstraintOrBlock &CB : S.WorkList) {
699  // First, pop entries from the stack that are out-of-scope for CB. Remove
700  // the corresponding entry from the constraint system.
701  while (!DFSInStack.empty()) {
702  auto &E = DFSInStack.back();
703  LLVM_DEBUG(dbgs() << "Top of stack : " << E.NumIn << " " << E.NumOut
704  << "\n");
705  LLVM_DEBUG(dbgs() << "CB: " << CB.NumIn << " " << CB.NumOut << "\n");
706  assert(E.NumIn <= CB.NumIn);
707  if (CB.NumOut <= E.NumOut)
708  break;
709  LLVM_DEBUG({
710  dbgs() << "Removing ";
711  dumpWithNames(Info.getCS(E.IsSigned).getLastConstraint(),
712  Info.getValue2Index(E.IsSigned));
713  dbgs() << "\n";
714  });
715 
716  Info.popLastConstraint(E.IsSigned);
717  // Remove variables in the system that went out of scope.
718  auto &Mapping = Info.getValue2Index(E.IsSigned);
719  for (Value *V : E.ValuesToRelease)
720  Mapping.erase(V);
721  Info.popLastNVariables(E.IsSigned, E.ValuesToRelease.size());
722  DFSInStack.pop_back();
723  }
724 
725  LLVM_DEBUG({
726  dbgs() << "Processing ";
727  if (CB.IsBlock)
728  dbgs() << *CB.BB;
729  else
730  dbgs() << *CB.Condition;
731  dbgs() << "\n";
732  });
733 
734  // For a block, check if any CmpInsts become known based on the current set
735  // of constraints.
736  if (CB.IsBlock) {
737  for (Instruction &I : make_early_inc_range(*CB.BB)) {
738  if (auto *II = dyn_cast<WithOverflowInst>(&I)) {
740  continue;
741  }
742  auto *Cmp = dyn_cast<ICmpInst>(&I);
743  if (!Cmp)
744  continue;
745 
746  DenseMap<Value *, unsigned> NewIndices;
747  auto R = Info.getConstraint(Cmp, NewIndices);
748  if (R.IsEq || R.empty() || R.needsNewIndices(NewIndices) ||
749  !R.isValid(Info))
750  continue;
751 
752  auto &CSToUse = Info.getCS(R.IsSigned);
753  if (CSToUse.isConditionImplied(R.Coefficients)) {
754  if (!DebugCounter::shouldExecute(EliminatedCounter))
755  continue;
756 
757  LLVM_DEBUG({
758  dbgs() << "Condition " << *Cmp
759  << " implied by dominating constraints\n";
760  dumpWithNames(CSToUse, Info.getValue2Index(R.IsSigned));
761  });
762  Cmp->replaceUsesWithIf(
763  ConstantInt::getTrue(F.getParent()->getContext()), [](Use &U) {
764  // Conditions in an assume trivially simplify to true. Skip uses
765  // in assume calls to not destroy the available information.
766  auto *II = dyn_cast<IntrinsicInst>(U.getUser());
767  return !II || II->getIntrinsicID() != Intrinsic::assume;
768  });
769  NumCondsRemoved++;
770  Changed = true;
771  }
772  if (CSToUse.isConditionImplied(
773  ConstraintSystem::negate(R.Coefficients))) {
774  if (!DebugCounter::shouldExecute(EliminatedCounter))
775  continue;
776 
777  LLVM_DEBUG({
778  dbgs() << "Condition !" << *Cmp
779  << " implied by dominating constraints\n";
780  dumpWithNames(CSToUse, Info.getValue2Index(R.IsSigned));
781  });
782  Cmp->replaceAllUsesWith(
783  ConstantInt::getFalse(F.getParent()->getContext()));
784  NumCondsRemoved++;
785  Changed = true;
786  }
787  }
788  continue;
789  }
790 
791  // Set up a function to restore the predicate at the end of the scope if it
792  // has been negated. Negate the predicate in-place, if required.
793  auto *CI = dyn_cast<ICmpInst>(CB.Condition);
794  auto PredicateRestorer = make_scope_exit([CI, &CB]() {
795  if (CB.Not && CI)
796  CI->setPredicate(CI->getInversePredicate());
797  });
798  if (CB.Not) {
799  if (CI) {
800  CI->setPredicate(CI->getInversePredicate());
801  } else {
802  LLVM_DEBUG(dbgs() << "Can only negate compares so far.\n");
803  continue;
804  }
805  }
806 
807  ICmpInst::Predicate Pred;
808  Value *A, *B;
809  if (match(CB.Condition, m_ICmp(Pred, m_Value(A), m_Value(B)))) {
810  // Otherwise, add the condition to the system and stack, if we can
811  // transform it into a constraint.
812  Info.addFact(Pred, A, B, CB.Not, CB.NumIn, CB.NumOut, DFSInStack);
813  Info.transferToOtherSystem(Pred, A, B, CB.Not, CB.NumIn, CB.NumOut,
814  DFSInStack);
815  }
816  }
817 
818 #ifndef NDEBUG
819  unsigned SignedEntries =
820  count_if(DFSInStack, [](const StackEntry &E) { return E.IsSigned; });
821  assert(Info.getCS(false).size() == DFSInStack.size() - SignedEntries &&
822  "updates to CS and DFSInStack are out of sync");
823  assert(Info.getCS(true).size() == SignedEntries &&
824  "updates to CS and DFSInStack are out of sync");
825 #endif
826 
827  for (Instruction *I : ToRemove)
828  I->eraseFromParent();
829  return Changed;
830 }
831 
834  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
835  if (!eliminateConstraints(F, DT))
836  return PreservedAnalyses::all();
837 
840  PA.preserveSet<CFGAnalyses>();
841  return PA;
842 }
843 
844 namespace {
845 
846 class ConstraintElimination : public FunctionPass {
847 public:
848  static char ID;
849 
850  ConstraintElimination() : FunctionPass(ID) {
852  }
853 
854  bool runOnFunction(Function &F) override {
855  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
856  return eliminateConstraints(F, DT);
857  }
858 
859  void getAnalysisUsage(AnalysisUsage &AU) const override {
860  AU.setPreservesCFG();
864  }
865 };
866 
867 } // end anonymous namespace
868 
870 
871 INITIALIZE_PASS_BEGIN(ConstraintElimination, "constraint-elimination",
872  "Constraint Elimination", false, false)
875 INITIALIZE_PASS_END(ConstraintElimination, "constraint-elimination",
876  "Constraint Elimination", false, false)
877 
879  return new ConstraintElimination();
880 }
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:4637
MaxConstraintValue
static int64_t MaxConstraintValue
Definition: ConstraintElimination.cpp:45
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:17
llvm::CmpInst::ICMP_EQ
@ ICMP_EQ
equal
Definition: InstrTypes.h:740
llvm::drop_begin
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Definition: STLExtras.h:280
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::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:780
Scalar.h
llvm::Function
Definition: Function.h:60
Pass.h
llvm::IntrinsicInst::getIntrinsicID
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
Definition: IntrinsicInst.h:53
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
Statistic.h
llvm::PatternMatch::m_Add
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
Definition: PatternMatch.h:973
ToRemove
ReachingDefAnalysis InstSet & ToRemove
Definition: ARMLowOverheadLoops.cpp:542
llvm::IRBuilder<>
llvm::CmpInst::ICMP_NE
@ ICMP_NE
not equal
Definition: InstrTypes.h:741
ValueTracking.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
GlobalsModRef.h
llvm::PatternMatch::m_NUWShl
OverflowingBinaryOp_match< LHS, RHS, Instruction::Shl, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWShl(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1207
llvm::CmpInst::ICMP_SGT
@ ICMP_SGT
signed greater than
Definition: InstrTypes.h:746
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1886
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
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::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:654
dumpWithNames
static void dumpWithNames(const ConstraintSystem &CS, DenseMap< Value *, unsigned > &Value2Index)
Definition: ConstraintElimination.cpp:482
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:1716
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:241
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:1617
eliminateConstraints
static bool eliminateConstraints(Function &F, DominatorTree &DT)
Definition: ConstraintElimination.cpp:671
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
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::PatternMatch::m_ZExt
CastClass_match< OpTy, Instruction::ZExt > m_ZExt(const OpTy &Op)
Matches ZExt.
Definition: PatternMatch.h:1623
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::make_scope_exit
LLVM_NODISCARD detail::scope_exit< typename std::decay< Callable >::type > make_scope_exit(Callable &&F)
Definition: ScopeExit.h:59
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:74
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:302
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:926
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:918
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::PatternMatch::m_NSWAdd
OverflowingBinaryOp_match< LHS, RHS, Instruction::Add, OverflowingBinaryOperator::NoSignedWrap > m_NSWAdd(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1150
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:690
llvm::APInt::slt
bool slt(const APInt &RHS) const
Signed less than comparison.
Definition: APInt.h:1080
ConstraintSystem.h
llvm::PatternMatch::m_Zero
is_zero m_Zero()
Match any null constant or a vector with all elements equal to 0.
Definition: PatternMatch.h:531
llvm::PatternMatch::m_NUWAdd
OverflowingBinaryOp_match< LHS, RHS, Instruction::Add, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWAdd(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1183
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:77
llvm::ConstraintSystem::negate
static SmallVector< int64_t, 8 > negate(SmallVector< int64_t, 8 > R)
Definition: ConstraintSystem.h:71
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:2549
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
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::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:618
llvm::concat
detail::concat_range< ValueT, RangeTs... > concat(RangeTs &&... Ranges)
Concatenated range across two or more ranges.
Definition: STLExtras.h:1085
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::IndexedInstrProf::HashT::Last
@ Last
llvm::CmpInst::ICMP_UGE
@ ICMP_UGE
unsigned greater or equal
Definition: InstrTypes.h:743
elimination
constraint elimination
Definition: ConstraintElimination.cpp:875
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:1598
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:1624
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:137
llvm::AnalysisUsage::setPreservesCFG
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:263
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
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:82
llvm::ConstraintEliminationPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &)
Definition: ConstraintElimination.cpp:832
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:46
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:209
llvm::ConstantInt::getFalse
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:881
llvm::ConstantInt::getZExtValue
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
Definition: Constants.h:142
llvm::DenseMapBase::empty
LLVM_NODISCARD bool empty() const
Definition: DenseMap.h:98
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
llvm::stable_sort
void stable_sort(R &&Range)
Definition: STLExtras.h:1761
llvm::empty
constexpr bool empty(const T &RangeOrContainer)
Test whether RangeOrContainer is empty. Similar to C++17 std::empty.
Definition: STLExtras.h:268
llvm::ConstantInt::getTrue
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:874
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:5430
llvm::ConstantInt::uge
bool uge(uint64_t Num) const
This function will return true iff this constant represents a value with active bits bigger than 64 b...
Definition: Constants.h:237
Function.h
DebugCounter.h
llvm::DenseMapBase::size
unsigned size() const
Definition: DenseMap.h:101
llvm::CmpInst::isSigned
bool isSigned() const
Definition: InstrTypes.h:947
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:46
llvm::PatternMatch::m_NUWSub
OverflowingBinaryOp_match< LHS, RHS, Instruction::Sub, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWSub(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1191
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:267
isValid
static bool isValid(const char C)
Returns true if C is a valid mangled character: <0-9a-zA-Z_>.
Definition: RustDemangle.cpp:187
Instructions.h
llvm::PreservedAnalyses::preserveSet
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:188
llvm::createConstraintEliminationPass
FunctionPass * createConstraintEliminationPass()
Definition: ConstraintElimination.cpp:878
tryToSimplifyOverflowMath
static void tryToSimplifyOverflowMath(IntrinsicInst *II, ConstraintInfo &Info, SmallVectorImpl< Instruction * > &ToRemove)
Definition: ConstraintElimination.cpp:624
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:1388
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
decompose
static SmallVector< std::pair< int64_t, Value * >, 4 > decompose(Value *V, SmallVector< PreconditionTy, 4 > &Preconditions, bool IsSigned)
Definition: ConstraintElimination.cpp:178
llvm::GlobalsAAWrapperPass
Legacy wrapper pass to provide the GlobalsAAResult object.
Definition: GlobalsModRef.h:148
llvm::ConstraintSystem::addVariableRowFill
bool addVariableRowFill(ArrayRef< int64_t > R)
Definition: ConstraintSystem.h:55
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:1151
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:876
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:2531
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:927
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38
llvm::SmallVectorImpl::insert
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:792
llvm::PoisonValue::get
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1787