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 to express a pre-condition of the form %Op0 Pred %Op1.
53 struct PreconditionTy {
54  CmpInst::Predicate Pred;
55  Value *Op0;
56  Value *Op1;
57 
58  PreconditionTy(CmpInst::Predicate Pred, Value *Op0, Value *Op1)
59  : Pred(Pred), Op0(Op0), Op1(Op1) {}
60 };
61 
62 struct ConstraintTy {
63  SmallVector<int64_t, 8> Coefficients;
64  SmallVector<PreconditionTy, 2> Preconditions;
65 
66  bool IsSigned = false;
67  bool IsEq = false;
68 
69  ConstraintTy() = default;
70 
71  ConstraintTy(SmallVector<int64_t, 8> Coefficients, bool IsSigned)
72  : Coefficients(Coefficients), IsSigned(IsSigned) {}
73 
74  unsigned size() const { return Coefficients.size(); }
75 
76  unsigned empty() const { return Coefficients.empty(); }
77 
78  /// Returns true if any constraint has a non-zero coefficient for any of the
79  /// newly added indices. Zero coefficients for new indices are removed. If it
80  /// returns true, no new variable need to be added to the system.
81  bool needsNewIndices(const DenseMap<Value *, unsigned> &NewIndices) {
82  for (unsigned I = 0; I < NewIndices.size(); ++I) {
83  int64_t Last = Coefficients.pop_back_val();
84  if (Last != 0)
85  return true;
86  }
87  return false;
88  }
89 
90  /// Returns true if all preconditions for this list of constraints are
91  /// satisfied given \p CS and the corresponding \p Value2Index mapping.
92  bool isValid(const ConstraintInfo &Info) const;
93 
94  /// Returns true if there is exactly one constraint in the list and isValid is
95  /// also true.
96  bool isValidSingle(const ConstraintInfo &Info) const {
97  if (size() != 1)
98  return false;
99  return isValid(Info);
100  }
101 };
102 
103 /// Wrapper encapsulating separate constraint systems and corresponding value
104 /// mappings for both unsigned and signed information. Facts are added to and
105 /// conditions are checked against the corresponding system depending on the
106 /// signed-ness of their predicates. While the information is kept separate
107 /// based on signed-ness, certain conditions can be transferred between the two
108 /// systems.
109 class ConstraintInfo {
110  DenseMap<Value *, unsigned> UnsignedValue2Index;
111  DenseMap<Value *, unsigned> SignedValue2Index;
112 
113  ConstraintSystem UnsignedCS;
114  ConstraintSystem SignedCS;
115 
116 public:
117  DenseMap<Value *, unsigned> &getValue2Index(bool Signed) {
118  return Signed ? SignedValue2Index : UnsignedValue2Index;
119  }
120  const DenseMap<Value *, unsigned> &getValue2Index(bool Signed) const {
121  return Signed ? SignedValue2Index : UnsignedValue2Index;
122  }
123 
124  ConstraintSystem &getCS(bool Signed) {
125  return Signed ? SignedCS : UnsignedCS;
126  }
127  const ConstraintSystem &getCS(bool Signed) const {
128  return Signed ? SignedCS : UnsignedCS;
129  }
130 
131  void popLastConstraint(bool Signed) { getCS(Signed).popLastConstraint(); }
132  void popLastNVariables(bool Signed, unsigned N) {
133  getCS(Signed).popLastNVariables(N);
134  }
135 };
136 
137 } // namespace
138 
139 // Decomposes \p V into a vector of pairs of the form { c, X } where c * X. The
140 // sum of the pairs equals \p V. The first pair is the constant-factor and X
141 // must be nullptr. If the expression cannot be decomposed, returns an empty
142 // vector.
145  bool IsSigned) {
146 
147  auto CanUseSExt = [](ConstantInt *CI) {
148  const APInt &Val = CI->getValue();
150  };
151  // Decompose \p V used with a signed predicate.
152  if (IsSigned) {
153  if (auto *CI = dyn_cast<ConstantInt>(V)) {
154  if (CanUseSExt(CI))
155  return {{CI->getSExtValue(), nullptr}};
156  }
157 
158  return {{0, nullptr}, {1, V}};
159  }
160 
161  if (auto *CI = dyn_cast<ConstantInt>(V)) {
162  if (CI->uge(MaxConstraintValue))
163  return {};
164  return {{CI->getZExtValue(), nullptr}};
165  }
166  auto *GEP = dyn_cast<GetElementPtrInst>(V);
167  if (GEP && GEP->getNumOperands() == 2 && GEP->isInBounds()) {
168  Value *Op0, *Op1;
169  ConstantInt *CI;
170 
171  // If the index is zero-extended, it is guaranteed to be positive.
172  if (match(GEP->getOperand(GEP->getNumOperands() - 1),
173  m_ZExt(m_Value(Op0)))) {
174  if (match(Op0, m_NUWShl(m_Value(Op1), m_ConstantInt(CI))) &&
175  CanUseSExt(CI))
176  return {{0, nullptr},
177  {1, GEP->getPointerOperand()},
178  {std::pow(int64_t(2), CI->getSExtValue()), Op1}};
179  if (match(Op0, m_NSWAdd(m_Value(Op1), m_ConstantInt(CI))) &&
180  CanUseSExt(CI))
181  return {{CI->getSExtValue(), nullptr},
182  {1, GEP->getPointerOperand()},
183  {1, Op1}};
184  return {{0, nullptr}, {1, GEP->getPointerOperand()}, {1, Op0}};
185  }
186 
187  if (match(GEP->getOperand(GEP->getNumOperands() - 1), m_ConstantInt(CI)) &&
188  !CI->isNegative() && CanUseSExt(CI))
189  return {{CI->getSExtValue(), nullptr}, {1, GEP->getPointerOperand()}};
190 
192  if (match(GEP->getOperand(GEP->getNumOperands() - 1),
193  m_NUWShl(m_Value(Op0), m_ConstantInt(CI))) &&
194  CanUseSExt(CI))
195  Result = {{0, nullptr},
196  {1, GEP->getPointerOperand()},
197  {std::pow(int64_t(2), CI->getSExtValue()), Op0}};
198  else if (match(GEP->getOperand(GEP->getNumOperands() - 1),
199  m_NSWAdd(m_Value(Op0), m_ConstantInt(CI))) &&
200  CanUseSExt(CI))
201  Result = {{CI->getSExtValue(), nullptr},
202  {1, GEP->getPointerOperand()},
203  {1, Op0}};
204  else {
205  Op0 = GEP->getOperand(GEP->getNumOperands() - 1);
206  Result = {{0, nullptr}, {1, GEP->getPointerOperand()}, {1, Op0}};
207  }
208  // If Op0 is signed non-negative, the GEP is increasing monotonically and
209  // can be de-composed.
210  Preconditions.emplace_back(CmpInst::ICMP_SGE, Op0,
211  ConstantInt::get(Op0->getType(), 0));
212  return Result;
213  }
214 
215  Value *Op0;
216  if (match(V, m_ZExt(m_Value(Op0))))
217  V = Op0;
218 
219  Value *Op1;
220  ConstantInt *CI;
221  if (match(V, m_NUWAdd(m_Value(Op0), m_ConstantInt(CI))) &&
222  !CI->uge(MaxConstraintValue))
223  return {{CI->getZExtValue(), nullptr}, {1, Op0}};
224  if (match(V, m_Add(m_Value(Op0), m_ConstantInt(CI))) && CI->isNegative() &&
225  CanUseSExt(CI)) {
226  Preconditions.emplace_back(
227  CmpInst::ICMP_UGE, Op0,
228  ConstantInt::get(Op0->getType(), CI->getSExtValue() * -1));
229  return {{CI->getSExtValue(), nullptr}, {1, Op0}};
230  }
231  if (match(V, m_NUWAdd(m_Value(Op0), m_Value(Op1))))
232  return {{0, nullptr}, {1, Op0}, {1, Op1}};
233 
234  if (match(V, m_NUWSub(m_Value(Op0), m_ConstantInt(CI))) && CanUseSExt(CI))
235  return {{-1 * CI->getSExtValue(), nullptr}, {1, Op0}};
236  if (match(V, m_NUWSub(m_Value(Op0), m_Value(Op1))))
237  return {{0, nullptr}, {1, Op0}, {-1, Op1}};
238 
239  return {{0, nullptr}, {1, V}};
240 }
241 
242 /// Turn a condition \p CmpI into a vector of constraints, using indices from \p
243 /// Value2Index. Additional indices for newly discovered values are added to \p
244 /// NewIndices.
245 static ConstraintTy
247  const DenseMap<Value *, unsigned> &Value2Index,
248  DenseMap<Value *, unsigned> &NewIndices) {
249  bool IsEq = false;
250  // Try to convert Pred to one of ULE/SLT/SLE/SLT.
251  switch (Pred) {
252  case CmpInst::ICMP_UGT:
253  case CmpInst::ICMP_UGE:
254  case CmpInst::ICMP_SGT:
255  case CmpInst::ICMP_SGE: {
256  Pred = CmpInst::getSwappedPredicate(Pred);
257  std::swap(Op0, Op1);
258  break;
259  }
260  case CmpInst::ICMP_EQ:
261  if (match(Op1, m_Zero())) {
262  Pred = CmpInst::ICMP_ULE;
263  } else {
264  IsEq = true;
265  Pred = CmpInst::ICMP_ULE;
266  }
267  break;
268  case CmpInst::ICMP_NE:
269  if (!match(Op1, m_Zero()))
270  return {};
272  std::swap(Op0, Op1);
273  break;
274  default:
275  break;
276  }
277 
278  // Only ULE and ULT predicates are supported at the moment.
279  if (Pred != CmpInst::ICMP_ULE && Pred != CmpInst::ICMP_ULT &&
280  Pred != CmpInst::ICMP_SLE && Pred != CmpInst::ICMP_SLT)
281  return {};
282 
283  SmallVector<PreconditionTy, 4> Preconditions;
284  bool IsSigned = CmpInst::isSigned(Pred);
286  Preconditions, IsSigned);
288  Preconditions, IsSigned);
289  // Skip if decomposing either of the values failed.
290  if (ADec.empty() || BDec.empty())
291  return {};
292 
293  // Skip trivial constraints without any variables.
294  if (ADec.size() == 1 && BDec.size() == 1)
295  return {};
296 
297  int64_t Offset1 = ADec[0].first;
298  int64_t Offset2 = BDec[0].first;
299  Offset1 *= -1;
300 
301  // Create iterator ranges that skip the constant-factor.
302  auto VariablesA = llvm::drop_begin(ADec);
303  auto VariablesB = llvm::drop_begin(BDec);
304 
305  // First try to look up \p V in Value2Index and NewIndices. Otherwise add a
306  // new entry to NewIndices.
307  auto GetOrAddIndex = [&Value2Index, &NewIndices](Value *V) -> unsigned {
308  auto V2I = Value2Index.find(V);
309  if (V2I != Value2Index.end())
310  return V2I->second;
311  auto Insert =
312  NewIndices.insert({V, Value2Index.size() + NewIndices.size() + 1});
313  return Insert.first->second;
314  };
315 
316  // Make sure all variables have entries in Value2Index or NewIndices.
317  for (const auto &KV :
318  concat<std::pair<int64_t, Value *>>(VariablesA, VariablesB))
319  GetOrAddIndex(KV.second);
320 
321  // Build result constraint, by first adding all coefficients from A and then
322  // subtracting all coefficients from B.
323  ConstraintTy Res(
324  SmallVector<int64_t, 8>(Value2Index.size() + NewIndices.size() + 1, 0),
325  IsSigned);
326  Res.IsEq = IsEq;
327  auto &R = Res.Coefficients;
328  for (const auto &KV : VariablesA)
329  R[GetOrAddIndex(KV.second)] += KV.first;
330 
331  for (const auto &KV : VariablesB)
332  R[GetOrAddIndex(KV.second)] -= KV.first;
333 
334  int64_t OffsetSum;
335  if (AddOverflow(Offset1, Offset2, OffsetSum))
336  return {};
337  if (Pred == (IsSigned ? CmpInst::ICMP_SLT : CmpInst::ICMP_ULT))
338  if (AddOverflow(OffsetSum, int64_t(-1), OffsetSum))
339  return {};
340  R[0] = OffsetSum;
341  Res.Preconditions = std::move(Preconditions);
342  return Res;
343 }
344 
345 static ConstraintTy getConstraint(CmpInst *Cmp, ConstraintInfo &Info,
346  DenseMap<Value *, unsigned> &NewIndices) {
347  return getConstraint(
348  Cmp->getPredicate(), Cmp->getOperand(0), Cmp->getOperand(1),
349  Info.getValue2Index(CmpInst::isSigned(Cmp->getPredicate())), NewIndices);
350 }
351 
352 bool ConstraintTy::isValid(const ConstraintInfo &Info) const {
353  return Coefficients.size() > 0 &&
354  all_of(Preconditions, [&Info](const PreconditionTy &C) {
355  DenseMap<Value *, unsigned> NewIndices;
356  auto R = getConstraint(
357  C.Pred, C.Op0, C.Op1,
358  Info.getValue2Index(CmpInst::isSigned(C.Pred)), NewIndices);
359  // TODO: properly check NewIndices.
360  return NewIndices.empty() && R.Preconditions.empty() && !R.IsEq &&
361  R.size() >= 2 &&
362  Info.getCS(CmpInst::isSigned(C.Pred))
363  .isConditionImplied(R.Coefficients);
364  });
365 }
366 
367 namespace {
368 /// Represents either a condition that holds on entry to a block or a basic
369 /// block, with their respective Dominator DFS in and out numbers.
370 struct ConstraintOrBlock {
371  unsigned NumIn;
372  unsigned NumOut;
373  bool IsBlock;
374  bool Not;
375  union {
376  BasicBlock *BB;
377  CmpInst *Condition;
378  };
379 
380  ConstraintOrBlock(DomTreeNode *DTN)
381  : NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()), IsBlock(true),
382  BB(DTN->getBlock()) {}
383  ConstraintOrBlock(DomTreeNode *DTN, CmpInst *Condition, bool Not)
384  : NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()), IsBlock(false),
385  Not(Not), Condition(Condition) {}
386 };
387 
388 struct StackEntry {
389  unsigned NumIn;
390  unsigned NumOut;
391  Instruction *Condition;
392  bool IsNot;
393  bool IsSigned = false;
394  /// Variables that can be removed from the system once the stack entry gets
395  /// removed.
396  SmallVector<Value *, 2> ValuesToRelease;
397 
398  StackEntry(unsigned NumIn, unsigned NumOut, CmpInst *Condition, bool IsNot,
399  bool IsSigned, SmallVector<Value *, 2> ValuesToRelease)
400  : NumIn(NumIn), NumOut(NumOut), Condition(Condition), IsNot(IsNot),
401  IsSigned(IsSigned), ValuesToRelease(ValuesToRelease) {}
402 };
403 
404 /// Keep state required to build worklist.
405 struct State {
406  DominatorTree &DT;
408 
409  State(DominatorTree &DT) : DT(DT) {}
410 
411  /// Process block \p BB and add known facts to work-list.
412  void addInfoFor(BasicBlock &BB);
413 
414  /// Returns true if we can add a known condition from BB to its successor
415  /// block Succ. Each predecessor of Succ can either be BB or be dominated
416  /// by Succ (e.g. the case when adding a condition from a pre-header to a
417  /// loop header).
418  bool canAddSuccessor(BasicBlock &BB, BasicBlock *Succ) const {
419  if (BB.getSingleSuccessor()) {
420  assert(BB.getSingleSuccessor() == Succ);
421  return DT.properlyDominates(&BB, Succ);
422  }
423  return any_of(successors(&BB),
424  [Succ](const BasicBlock *S) { return S != Succ; }) &&
425  all_of(predecessors(Succ), [&BB, Succ, this](BasicBlock *Pred) {
426  return Pred == &BB || DT.dominates(Succ, Pred);
427  });
428  }
429 };
430 
431 } // namespace
432 
433 #ifndef NDEBUG
434 static void dumpWithNames(ConstraintTy &C,
435  DenseMap<Value *, unsigned> &Value2Index) {
436  SmallVector<std::string> Names(Value2Index.size(), "");
437  for (auto &KV : Value2Index) {
438  Names[KV.second - 1] = std::string("%") + KV.first->getName().str();
439  }
440  ConstraintSystem CS;
441  CS.addVariableRowFill(C.Coefficients);
442  CS.dump(Names);
443 }
444 #endif
445 
446 void State::addInfoFor(BasicBlock &BB) {
447  WorkList.emplace_back(DT.getNode(&BB));
448 
449  // True as long as long as the current instruction is guaranteed to execute.
450  bool GuaranteedToExecute = true;
451  // Scan BB for assume calls.
452  // TODO: also use this scan to queue conditions to simplify, so we can
453  // interleave facts from assumes and conditions to simplify in a single
454  // basic block. And to skip another traversal of each basic block when
455  // simplifying.
456  for (Instruction &I : BB) {
457  Value *Cond;
458  // For now, just handle assumes with a single compare as condition.
459  if (match(&I, m_Intrinsic<Intrinsic::assume>(m_Value(Cond))) &&
460  isa<ICmpInst>(Cond)) {
461  if (GuaranteedToExecute) {
462  // The assume is guaranteed to execute when BB is entered, hence Cond
463  // holds on entry to BB.
464  WorkList.emplace_back(DT.getNode(&BB), cast<ICmpInst>(Cond), false);
465  } else {
466  // Otherwise the condition only holds in the successors.
467  for (BasicBlock *Succ : successors(&BB)) {
468  if (!canAddSuccessor(BB, Succ))
469  continue;
470  WorkList.emplace_back(DT.getNode(Succ), cast<ICmpInst>(Cond), false);
471  }
472  }
473  }
474  GuaranteedToExecute &= isGuaranteedToTransferExecutionToSuccessor(&I);
475  }
476 
477  auto *Br = dyn_cast<BranchInst>(BB.getTerminator());
478  if (!Br || !Br->isConditional())
479  return;
480 
481  // If the condition is an OR of 2 compares and the false successor only has
482  // the current block as predecessor, queue both negated conditions for the
483  // false successor.
484  Value *Op0, *Op1;
485  if (match(Br->getCondition(), m_LogicalOr(m_Value(Op0), m_Value(Op1))) &&
486  isa<ICmpInst>(Op0) && isa<ICmpInst>(Op1)) {
487  BasicBlock *FalseSuccessor = Br->getSuccessor(1);
488  if (canAddSuccessor(BB, FalseSuccessor)) {
489  WorkList.emplace_back(DT.getNode(FalseSuccessor), cast<ICmpInst>(Op0),
490  true);
491  WorkList.emplace_back(DT.getNode(FalseSuccessor), cast<ICmpInst>(Op1),
492  true);
493  }
494  return;
495  }
496 
497  // If the condition is an AND of 2 compares and the true successor only has
498  // the current block as predecessor, queue both conditions for the true
499  // successor.
500  if (match(Br->getCondition(), m_LogicalAnd(m_Value(Op0), m_Value(Op1))) &&
501  isa<ICmpInst>(Op0) && isa<ICmpInst>(Op1)) {
502  BasicBlock *TrueSuccessor = Br->getSuccessor(0);
503  if (canAddSuccessor(BB, TrueSuccessor)) {
504  WorkList.emplace_back(DT.getNode(TrueSuccessor), cast<ICmpInst>(Op0),
505  false);
506  WorkList.emplace_back(DT.getNode(TrueSuccessor), cast<ICmpInst>(Op1),
507  false);
508  }
509  return;
510  }
511 
512  auto *CmpI = dyn_cast<ICmpInst>(Br->getCondition());
513  if (!CmpI)
514  return;
515  if (canAddSuccessor(BB, Br->getSuccessor(0)))
516  WorkList.emplace_back(DT.getNode(Br->getSuccessor(0)), CmpI, false);
517  if (canAddSuccessor(BB, Br->getSuccessor(1)))
518  WorkList.emplace_back(DT.getNode(Br->getSuccessor(1)), CmpI, true);
519 }
520 
521 static void
524  auto DoesConditionHold = [](CmpInst::Predicate Pred, Value *A, Value *B,
525  ConstraintInfo &Info) {
526  DenseMap<Value *, unsigned> NewIndices;
527  auto R = getConstraint(
528  Pred, A, B, Info.getValue2Index(CmpInst::isSigned(Pred)), NewIndices);
529  if (R.size() < 2 || R.needsNewIndices(NewIndices) || !R.isValid(Info))
530  return false;
531 
532  auto &CSToUse = Info.getCS(CmpInst::isSigned(Pred));
533  return CSToUse.isConditionImplied(R.Coefficients);
534  };
535 
536  if (II->getIntrinsicID() == Intrinsic::ssub_with_overflow) {
537  // If A s>= B && B s>= 0, ssub.with.overflow(a, b) should not overflow and
538  // can be simplified to a regular sub.
539  Value *A = II->getArgOperand(0);
540  Value *B = II->getArgOperand(1);
541  if (!DoesConditionHold(CmpInst::ICMP_SGE, A, B, Info) ||
542  !DoesConditionHold(CmpInst::ICMP_SGE, B,
543  ConstantInt::get(A->getType(), 0), Info))
544  return;
545 
547  Value *Sub = nullptr;
548  for (User *U : make_early_inc_range(II->users())) {
549  if (match(U, m_ExtractValue<0>(m_Value()))) {
550  if (!Sub)
551  Sub = Builder.CreateSub(A, B);
552  U->replaceAllUsesWith(Sub);
553  } else if (match(U, m_ExtractValue<1>(m_Value())))
554  U->replaceAllUsesWith(Builder.getFalse());
555  else
556  continue;
557 
558  if (U->use_empty()) {
559  auto *I = cast<Instruction>(U);
560  ToRemove.push_back(I);
561  I->setOperand(0, PoisonValue::get(II->getType()));
562  }
563  }
564 
565  if (II->use_empty())
566  II->eraseFromParent();
567  }
568 }
569 
571  bool Changed = false;
572  DT.updateDFSNumbers();
573 
574  ConstraintInfo Info;
575  State S(DT);
576 
577  // First, collect conditions implied by branches and blocks with their
578  // Dominator DFS in and out numbers.
579  for (BasicBlock &BB : F) {
580  if (!DT.getNode(&BB))
581  continue;
582  S.addInfoFor(BB);
583  }
584 
585  // Next, sort worklist by dominance, so that dominating blocks and conditions
586  // come before blocks and conditions dominated by them. If a block and a
587  // condition have the same numbers, the condition comes before the block, as
588  // it holds on entry to the block.
589  sort(S.WorkList, [](const ConstraintOrBlock &A, const ConstraintOrBlock &B) {
590  return std::tie(A.NumIn, A.IsBlock) < std::tie(B.NumIn, B.IsBlock);
591  });
592 
594 
595  // Finally, process ordered worklist and eliminate implied conditions.
596  SmallVector<StackEntry, 16> DFSInStack;
597  for (ConstraintOrBlock &CB : S.WorkList) {
598  // First, pop entries from the stack that are out-of-scope for CB. Remove
599  // the corresponding entry from the constraint system.
600  while (!DFSInStack.empty()) {
601  auto &E = DFSInStack.back();
602  LLVM_DEBUG(dbgs() << "Top of stack : " << E.NumIn << " " << E.NumOut
603  << "\n");
604  LLVM_DEBUG(dbgs() << "CB: " << CB.NumIn << " " << CB.NumOut << "\n");
605  assert(E.NumIn <= CB.NumIn);
606  if (CB.NumOut <= E.NumOut)
607  break;
608  LLVM_DEBUG(dbgs() << "Removing " << *E.Condition << " " << E.IsNot
609  << "\n");
610  Info.popLastConstraint(E.IsSigned);
611  // Remove variables in the system that went out of scope.
612  auto &Mapping = Info.getValue2Index(E.IsSigned);
613  for (Value *V : E.ValuesToRelease)
614  Mapping.erase(V);
615  Info.popLastNVariables(E.IsSigned, E.ValuesToRelease.size());
616  DFSInStack.pop_back();
617  }
618 
619  LLVM_DEBUG({
620  dbgs() << "Processing ";
621  if (CB.IsBlock)
622  dbgs() << *CB.BB;
623  else
624  dbgs() << *CB.Condition;
625  dbgs() << "\n";
626  });
627 
628  // For a block, check if any CmpInsts become known based on the current set
629  // of constraints.
630  if (CB.IsBlock) {
631  for (Instruction &I : make_early_inc_range(*CB.BB)) {
632  if (auto *II = dyn_cast<WithOverflowInst>(&I)) {
634  continue;
635  }
636  auto *Cmp = dyn_cast<ICmpInst>(&I);
637  if (!Cmp)
638  continue;
639 
640  DenseMap<Value *, unsigned> NewIndices;
641  auto R = getConstraint(Cmp, Info, NewIndices);
642  if (R.IsEq || R.size() < 2 || R.needsNewIndices(NewIndices) ||
643  !R.isValid(Info))
644  continue;
645 
646  auto &CSToUse = Info.getCS(R.IsSigned);
647  if (CSToUse.isConditionImplied(R.Coefficients)) {
648  if (!DebugCounter::shouldExecute(EliminatedCounter))
649  continue;
650 
651  LLVM_DEBUG(dbgs() << "Condition " << *Cmp
652  << " implied by dominating constraints\n");
653  LLVM_DEBUG({
654  for (auto &E : reverse(DFSInStack))
655  dbgs() << " C " << *E.Condition << " " << E.IsNot << "\n";
656  });
657  Cmp->replaceUsesWithIf(
658  ConstantInt::getTrue(F.getParent()->getContext()), [](Use &U) {
659  // Conditions in an assume trivially simplify to true. Skip uses
660  // in assume calls to not destroy the available information.
661  auto *II = dyn_cast<IntrinsicInst>(U.getUser());
662  return !II || II->getIntrinsicID() != Intrinsic::assume;
663  });
664  NumCondsRemoved++;
665  Changed = true;
666  }
667  if (CSToUse.isConditionImplied(
668  ConstraintSystem::negate(R.Coefficients))) {
669  if (!DebugCounter::shouldExecute(EliminatedCounter))
670  continue;
671 
672  LLVM_DEBUG(dbgs() << "Condition !" << *Cmp
673  << " implied by dominating constraints\n");
674  LLVM_DEBUG({
675  for (auto &E : reverse(DFSInStack))
676  dbgs() << " C " << *E.Condition << " " << E.IsNot << "\n";
677  });
678  Cmp->replaceAllUsesWith(
679  ConstantInt::getFalse(F.getParent()->getContext()));
680  NumCondsRemoved++;
681  Changed = true;
682  }
683  }
684  continue;
685  }
686 
687  // Set up a function to restore the predicate at the end of the scope if it
688  // has been negated. Negate the predicate in-place, if required.
689  auto *CI = dyn_cast<ICmpInst>(CB.Condition);
690  auto PredicateRestorer = make_scope_exit([CI, &CB]() {
691  if (CB.Not && CI)
692  CI->setPredicate(CI->getInversePredicate());
693  });
694  if (CB.Not) {
695  if (CI) {
696  CI->setPredicate(CI->getInversePredicate());
697  } else {
698  LLVM_DEBUG(dbgs() << "Can only negate compares so far.\n");
699  continue;
700  }
701  }
702 
703  // Otherwise, add the condition to the system and stack, if we can transform
704  // it into a constraint.
705  DenseMap<Value *, unsigned> NewIndices;
706  auto R = getConstraint(CB.Condition, Info, NewIndices);
707  if (!R.isValid(Info))
708  continue;
709 
710  LLVM_DEBUG(dbgs() << "Adding " << *CB.Condition << " " << CB.Not << "\n");
711  bool Added = false;
712  assert(CmpInst::isSigned(CB.Condition->getPredicate()) == R.IsSigned &&
713  "condition and constraint signs must match");
714  auto &CSToUse = Info.getCS(R.IsSigned);
715  if (R.Coefficients.empty())
716  continue;
717 
718  Added |= CSToUse.addVariableRowFill(R.Coefficients);
719 
720  // If R has been added to the system, queue it for removal once it goes
721  // out-of-scope.
722  if (Added) {
723  SmallVector<Value *, 2> ValuesToRelease;
724  for (auto &KV : NewIndices) {
725  Info.getValue2Index(R.IsSigned).insert(KV);
726  ValuesToRelease.push_back(KV.first);
727  }
728 
729  LLVM_DEBUG({
730  dbgs() << " constraint: ";
731  dumpWithNames(R, Info.getValue2Index(R.IsSigned));
732  });
733 
734  DFSInStack.emplace_back(CB.NumIn, CB.NumOut, CB.Condition, CB.Not,
735  R.IsSigned, ValuesToRelease);
736 
737  if (R.IsEq) {
738  // Also add the inverted constraint for equality constraints.
739  for (auto &Coeff : R.Coefficients)
740  Coeff *= -1;
741  CSToUse.addVariableRowFill(R.Coefficients);
742 
743  DFSInStack.emplace_back(CB.NumIn, CB.NumOut, CB.Condition, CB.Not,
744  R.IsSigned, SmallVector<Value *, 2>());
745  }
746  }
747  }
748 
749 #ifndef NDEBUG
750  unsigned SignedEntries =
751  count_if(DFSInStack, [](const StackEntry &E) { return E.IsSigned; });
752  assert(Info.getCS(false).size() == DFSInStack.size() - SignedEntries &&
753  "updates to CS and DFSInStack are out of sync");
754  assert(Info.getCS(true).size() == SignedEntries &&
755  "updates to CS and DFSInStack are out of sync");
756 #endif
757 
758  for (Instruction *I : ToRemove)
759  I->eraseFromParent();
760  return Changed;
761 }
762 
765  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
766  if (!eliminateConstraints(F, DT))
767  return PreservedAnalyses::all();
768 
771  PA.preserveSet<CFGAnalyses>();
772  return PA;
773 }
774 
775 namespace {
776 
777 class ConstraintElimination : public FunctionPass {
778 public:
779  static char ID;
780 
781  ConstraintElimination() : FunctionPass(ID) {
783  }
784 
785  bool runOnFunction(Function &F) override {
786  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
787  return eliminateConstraints(F, DT);
788  }
789 
790  void getAnalysisUsage(AnalysisUsage &AU) const override {
791  AU.setPreservesCFG();
795  }
796 };
797 
798 } // end anonymous namespace
799 
801 
802 INITIALIZE_PASS_BEGIN(ConstraintElimination, "constraint-elimination",
803  "Constraint Elimination", false, false)
806 INITIALIZE_PASS_END(ConstraintElimination, "constraint-elimination",
807  "Constraint Elimination", false, false)
808 
810  return new ConstraintElimination();
811 }
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
dumpWithNames
static void dumpWithNames(ConstraintTy &C, DenseMap< Value *, unsigned > &Value2Index)
Definition: ConstraintElimination.cpp:434
getConstraint
static ConstraintTy getConstraint(CmpInst::Predicate Pred, Value *Op0, Value *Op1, const DenseMap< Value *, unsigned > &Value2Index, DenseMap< Value *, unsigned > &NewIndices)
Turn a condition CmpI into a vector of constraints, using indices from Value2Index.
Definition: ConstraintElimination.cpp:246
Signed
@ Signed
Definition: NVPTXISelLowering.cpp:4635
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:988
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:1223
llvm::CmpInst::ICMP_SGT
@ ICMP_SGT
signed greater than
Definition: InstrTypes.h:746
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1909
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:380
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
STLExtras.h
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:654
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:1704
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:240
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:1605
eliminateConstraints
static bool eliminateConstraints(Function &F, DominatorTree &DT)
Definition: ConstraintElimination.cpp:570
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::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:1639
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:145
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:919
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:911
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
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:1166
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:535
llvm::PatternMatch::m_NUWAdd
OverflowingBinaryOp_match< LHS, RHS, Instruction::Add, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWAdd(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1199
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:82
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:2562
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:608
llvm::concat
detail::concat_range< ValueT, RangeTs... > concat(RangeTs &&... Ranges)
Concatenated range across two or more ranges.
Definition: STLExtras.h:1075
llvm::DenseMapBase::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:152
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:806
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:1586
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:1612
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:178
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:763
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:874
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::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:867
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::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:5277
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::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1550
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:1207
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:809
tryToSimplifyOverflowMath
static void tryToSimplifyOverflowMath(IntrinsicInst *II, ConstraintInfo &Info, SmallVectorImpl< Instruction * > &ToRemove)
Definition: ConstraintElimination.cpp:522
llvm::ConstantInt::isNegative
bool isNegative() const
Definition: Constants.h:189
SmallVector.h
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:144
llvm::GlobalsAAWrapperPass
Legacy wrapper pass to provide the GlobalsAAResult object.
Definition: GlobalsModRef.h:148
llvm::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:340
llvm::ConstraintSystem::addVariableRowFill
bool addVariableRowFill(ArrayRef< int64_t > R)
Definition: ConstraintSystem.h:55
ScopeExit.h
llvm::SmallVectorImpl< Instruction * >
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:172
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:807
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:2544
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:37
llvm::PoisonValue::get
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1788