LLVM  14.0.0git
ConstraintElimination.cpp
Go to the documentation of this file.
1 //===-- ConstraintElimination.cpp - Eliminate conds using constraints. ----===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // Eliminate conditions based on constraints collected from dominating
10 // conditions.
11 //
12 //===----------------------------------------------------------------------===//
13 
15 #include "llvm/ADT/STLExtras.h"
16 #include "llvm/ADT/ScopeExit.h"
17 #include "llvm/ADT/SmallVector.h"
18 #include "llvm/ADT/Statistic.h"
22 #include "llvm/IR/DataLayout.h"
23 #include "llvm/IR/Dominators.h"
24 #include "llvm/IR/Function.h"
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"
31 #include "llvm/Transforms/Scalar.h"
32 
33 #include <string>
34 
35 using namespace llvm;
36 using namespace PatternMatch;
37 
38 #define DEBUG_TYPE "constraint-elimination"
39 
40 STATISTIC(NumCondsRemoved, "Number of instructions removed");
41 DEBUG_COUNTER(EliminatedCounter, "conds-eliminated",
42  "Controls which conditions are eliminated");
43 
45 
46 // Decomposes \p V into a vector of pairs of the form { c, X } where c * X. The
47 // sum of the pairs equals \p V. The first pair is the constant-factor and X
48 // must be nullptr. If the expression cannot be decomposed, returns an empty
49 // vector.
51  if (auto *CI = dyn_cast<ConstantInt>(V)) {
52  if (CI->isNegative() || CI->uge(MaxConstraintValue))
53  return {};
54  return {{CI->getSExtValue(), nullptr}};
55  }
56  auto *GEP = dyn_cast<GetElementPtrInst>(V);
57  if (GEP && GEP->getNumOperands() == 2 && GEP->isInBounds()) {
58  Value *Op0, *Op1;
59  ConstantInt *CI;
60 
61  // If the index is zero-extended, it is guaranteed to be positive.
62  if (match(GEP->getOperand(GEP->getNumOperands() - 1),
63  m_ZExt(m_Value(Op0)))) {
64  if (match(Op0, m_NUWShl(m_Value(Op1), m_ConstantInt(CI))))
65  return {{0, nullptr},
66  {1, GEP->getPointerOperand()},
67  {std::pow(int64_t(2), CI->getSExtValue()), Op1}};
68  if (match(Op0, m_NSWAdd(m_Value(Op1), m_ConstantInt(CI))))
69  return {{CI->getSExtValue(), nullptr},
70  {1, GEP->getPointerOperand()},
71  {1, Op1}};
72  return {{0, nullptr}, {1, GEP->getPointerOperand()}, {1, Op0}};
73  }
74 
75  if (match(GEP->getOperand(GEP->getNumOperands() - 1), m_ConstantInt(CI)) &&
76  !CI->isNegative())
77  return {{CI->getSExtValue(), nullptr}, {1, GEP->getPointerOperand()}};
78 
80  if (match(GEP->getOperand(GEP->getNumOperands() - 1),
81  m_NUWShl(m_Value(Op0), m_ConstantInt(CI))))
82  Result = {{0, nullptr},
83  {1, GEP->getPointerOperand()},
84  {std::pow(int64_t(2), CI->getSExtValue()), Op0}};
85  else if (match(GEP->getOperand(GEP->getNumOperands() - 1),
86  m_NSWAdd(m_Value(Op0), m_ConstantInt(CI))))
87  Result = {{CI->getSExtValue(), nullptr},
88  {1, GEP->getPointerOperand()},
89  {1, Op0}};
90  else {
91  Op0 = GEP->getOperand(GEP->getNumOperands() - 1);
92  Result = {{0, nullptr}, {1, GEP->getPointerOperand()}, {1, Op0}};
93  }
94  return Result;
95  }
96 
97  Value *Op0;
98  if (match(V, m_ZExt(m_Value(Op0))))
99  V = Op0;
100 
101  Value *Op1;
102  ConstantInt *CI;
103  if (match(V, m_NUWAdd(m_Value(Op0), m_ConstantInt(CI))))
104  return {{CI->getSExtValue(), nullptr}, {1, Op0}};
105  if (match(V, m_NUWAdd(m_Value(Op0), m_Value(Op1))))
106  return {{0, nullptr}, {1, Op0}, {1, Op1}};
107 
108  if (match(V, m_NUWSub(m_Value(Op0), m_ConstantInt(CI))))
109  return {{-1 * CI->getSExtValue(), nullptr}, {1, Op0}};
110  if (match(V, m_NUWSub(m_Value(Op0), m_Value(Op1))))
111  return {{0, nullptr}, {1, Op0}, {1, Op1}};
112 
113  return {{0, nullptr}, {1, V}};
114 }
115 
116 struct ConstraintTy {
118 
120  : Coefficients(Coefficients) {}
121 
122  unsigned size() const { return Coefficients.size(); }
123 };
124 
125 /// Turn a condition \p CmpI into a vector of constraints, using indices from \p
126 /// Value2Index. Additional indices for newly discovered values are added to \p
127 /// NewIndices.
130  const DenseMap<Value *, unsigned> &Value2Index,
131  DenseMap<Value *, unsigned> &NewIndices) {
132  int64_t Offset1 = 0;
133  int64_t Offset2 = 0;
134 
135  // First try to look up \p V in Value2Index and NewIndices. Otherwise add a
136  // new entry to NewIndices.
137  auto GetOrAddIndex = [&Value2Index, &NewIndices](Value *V) -> unsigned {
138  auto V2I = Value2Index.find(V);
139  if (V2I != Value2Index.end())
140  return V2I->second;
141  auto NewI = NewIndices.find(V);
142  if (NewI != NewIndices.end())
143  return NewI->second;
144  auto Insert =
145  NewIndices.insert({V, Value2Index.size() + NewIndices.size() + 1});
146  return Insert.first->second;
147  };
148 
149  if (Pred == CmpInst::ICMP_UGT || Pred == CmpInst::ICMP_UGE)
150  return getConstraint(CmpInst::getSwappedPredicate(Pred), Op1, Op0,
151  Value2Index, NewIndices);
152 
153  if (Pred == CmpInst::ICMP_EQ) {
154  auto A =
155  getConstraint(CmpInst::ICMP_UGE, Op0, Op1, Value2Index, NewIndices);
156  auto B =
157  getConstraint(CmpInst::ICMP_ULE, Op0, Op1, Value2Index, NewIndices);
158  append_range(A, B);
159  return A;
160  }
161 
162  if (Pred == CmpInst::ICMP_NE && match(Op1, m_Zero())) {
163  return getConstraint(CmpInst::ICMP_UGT, Op0, Op1, Value2Index, NewIndices);
164  }
165 
166  // Only ULE and ULT predicates are supported at the moment.
167  if (Pred != CmpInst::ICMP_ULE && Pred != CmpInst::ICMP_ULT)
168  return {};
169 
170  auto ADec = decompose(Op0->stripPointerCastsSameRepresentation());
171  auto BDec = decompose(Op1->stripPointerCastsSameRepresentation());
172  // Skip if decomposing either of the values failed.
173  if (ADec.empty() || BDec.empty())
174  return {};
175 
176  // Skip trivial constraints without any variables.
177  if (ADec.size() == 1 && BDec.size() == 1)
178  return {};
179 
180  Offset1 = ADec[0].first;
181  Offset2 = BDec[0].first;
182  Offset1 *= -1;
183 
184  // Create iterator ranges that skip the constant-factor.
185  auto VariablesA = llvm::drop_begin(ADec);
186  auto VariablesB = llvm::drop_begin(BDec);
187 
188  // Make sure all variables have entries in Value2Index or NewIndices.
189  for (const auto &KV :
190  concat<std::pair<int64_t, Value *>>(VariablesA, VariablesB))
191  GetOrAddIndex(KV.second);
192 
193  // Build result constraint, by first adding all coefficients from A and then
194  // subtracting all coefficients from B.
195  SmallVector<int64_t, 8> R(Value2Index.size() + NewIndices.size() + 1, 0);
196  for (const auto &KV : VariablesA)
197  R[GetOrAddIndex(KV.second)] += KV.first;
198 
199  for (const auto &KV : VariablesB)
200  R[GetOrAddIndex(KV.second)] -= KV.first;
201 
202  R[0] = Offset1 + Offset2 + (Pred == CmpInst::ICMP_ULT ? -1 : 0);
203  return {R};
204 }
205 
208  DenseMap<Value *, unsigned> &NewIndices) {
209  return getConstraint(Cmp->getPredicate(), Cmp->getOperand(0),
210  Cmp->getOperand(1), Value2Index, NewIndices);
211 }
212 
213 namespace {
214 /// Represents either a condition that holds on entry to a block or a basic
215 /// block, with their respective Dominator DFS in and out numbers.
216 struct ConstraintOrBlock {
217  unsigned NumIn;
218  unsigned NumOut;
219  bool IsBlock;
220  bool Not;
221  union {
222  BasicBlock *BB;
223  CmpInst *Condition;
224  };
225 
226  ConstraintOrBlock(DomTreeNode *DTN)
227  : NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()), IsBlock(true),
228  BB(DTN->getBlock()) {}
229  ConstraintOrBlock(DomTreeNode *DTN, CmpInst *Condition, bool Not)
230  : NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()), IsBlock(false),
231  Not(Not), Condition(Condition) {}
232 };
233 
234 struct StackEntry {
235  unsigned NumIn;
236  unsigned NumOut;
237  CmpInst *Condition;
238  bool IsNot;
239 
240  StackEntry(unsigned NumIn, unsigned NumOut, CmpInst *Condition, bool IsNot)
241  : NumIn(NumIn), NumOut(NumOut), Condition(Condition), IsNot(IsNot) {}
242 };
243 } // namespace
244 
245 #ifndef NDEBUG
247  DenseMap<Value *, unsigned> &Value2Index) {
248  SmallVector<std::string> Names(Value2Index.size(), "");
249  for (auto &KV : Value2Index) {
250  Names[KV.second - 1] = std::string("%") + KV.first->getName().str();
251  }
252  ConstraintSystem CS;
253  CS.addVariableRowFill(C.Coefficients);
254  CS.dump(Names);
255 }
256 #endif
257 
259  bool Changed = false;
260  DT.updateDFSNumbers();
261  ConstraintSystem CS;
262 
264 
265  // First, collect conditions implied by branches and blocks with their
266  // Dominator DFS in and out numbers.
267  for (BasicBlock &BB : F) {
268  if (!DT.getNode(&BB))
269  continue;
270  WorkList.emplace_back(DT.getNode(&BB));
271 
272  // True as long as long as the current instruction is guaranteed to execute.
273  bool GuaranteedToExecute = true;
274  // Scan BB for assume calls.
275  // TODO: also use this scan to queue conditions to simplify, so we can
276  // interleave facts from assumes and conditions to simplify in a single
277  // basic block. And to skip another traversal of each basic block when
278  // simplifying.
279  for (Instruction &I : BB) {
280  Value *Cond;
281  // For now, just handle assumes with a single compare as condition.
282  if (match(&I, m_Intrinsic<Intrinsic::assume>(m_Value(Cond))) &&
283  isa<CmpInst>(Cond)) {
284  if (GuaranteedToExecute) {
285  // The assume is guaranteed to execute when BB is entered, hence Cond
286  // holds on entry to BB.
287  WorkList.emplace_back(DT.getNode(&BB), cast<CmpInst>(Cond), false);
288  } else {
289  // Otherwise the condition only holds in the successors.
290  for (BasicBlock *Succ : successors(&BB))
291  WorkList.emplace_back(DT.getNode(Succ), cast<CmpInst>(Cond), false);
292  }
293  }
294  GuaranteedToExecute &= isGuaranteedToTransferExecutionToSuccessor(&I);
295  }
296 
297  auto *Br = dyn_cast<BranchInst>(BB.getTerminator());
298  if (!Br || !Br->isConditional())
299  continue;
300 
301  // Returns true if we can add a known condition from BB to its successor
302  // block Succ. Each predecessor of Succ can either be BB or be dominated by
303  // Succ (e.g. the case when adding a condition from a pre-header to a loop
304  // header).
305  auto CanAdd = [&BB, &DT](BasicBlock *Succ) {
306  return all_of(predecessors(Succ), [&BB, &DT, Succ](BasicBlock *Pred) {
307  return Pred == &BB || DT.dominates(Succ, Pred);
308  });
309  };
310  // If the condition is an OR of 2 compares and the false successor only has
311  // the current block as predecessor, queue both negated conditions for the
312  // false successor.
313  Value *Op0, *Op1;
314  if (match(Br->getCondition(), m_LogicalOr(m_Value(Op0), m_Value(Op1))) &&
315  match(Op0, m_Cmp()) && match(Op1, m_Cmp())) {
316  BasicBlock *FalseSuccessor = Br->getSuccessor(1);
317  if (CanAdd(FalseSuccessor)) {
318  WorkList.emplace_back(DT.getNode(FalseSuccessor), cast<CmpInst>(Op0),
319  true);
320  WorkList.emplace_back(DT.getNode(FalseSuccessor), cast<CmpInst>(Op1),
321  true);
322  }
323  continue;
324  }
325 
326  // If the condition is an AND of 2 compares and the true successor only has
327  // the current block as predecessor, queue both conditions for the true
328  // successor.
329  if (match(Br->getCondition(), m_LogicalAnd(m_Value(Op0), m_Value(Op1))) &&
330  match(Op0, m_Cmp()) && match(Op1, m_Cmp())) {
331  BasicBlock *TrueSuccessor = Br->getSuccessor(0);
332  if (CanAdd(TrueSuccessor)) {
333  WorkList.emplace_back(DT.getNode(TrueSuccessor), cast<CmpInst>(Op0),
334  false);
335  WorkList.emplace_back(DT.getNode(TrueSuccessor), cast<CmpInst>(Op1),
336  false);
337  }
338  continue;
339  }
340 
341  auto *CmpI = dyn_cast<CmpInst>(Br->getCondition());
342  if (!CmpI)
343  continue;
344  if (CanAdd(Br->getSuccessor(0)))
345  WorkList.emplace_back(DT.getNode(Br->getSuccessor(0)), CmpI, false);
346  if (CanAdd(Br->getSuccessor(1)))
347  WorkList.emplace_back(DT.getNode(Br->getSuccessor(1)), CmpI, true);
348  }
349 
350  // Next, sort worklist by dominance, so that dominating blocks and conditions
351  // come before blocks and conditions dominated by them. If a block and a
352  // condition have the same numbers, the condition comes before the block, as
353  // it holds on entry to the block.
354  sort(WorkList, [](const ConstraintOrBlock &A, const ConstraintOrBlock &B) {
355  return std::tie(A.NumIn, A.IsBlock) < std::tie(B.NumIn, B.IsBlock);
356  });
357 
358  // Finally, process ordered worklist and eliminate implied conditions.
359  SmallVector<StackEntry, 16> DFSInStack;
360  DenseMap<Value *, unsigned> Value2Index;
361  for (ConstraintOrBlock &CB : WorkList) {
362  // First, pop entries from the stack that are out-of-scope for CB. Remove
363  // the corresponding entry from the constraint system.
364  while (!DFSInStack.empty()) {
365  auto &E = DFSInStack.back();
366  LLVM_DEBUG(dbgs() << "Top of stack : " << E.NumIn << " " << E.NumOut
367  << "\n");
368  LLVM_DEBUG(dbgs() << "CB: " << CB.NumIn << " " << CB.NumOut << "\n");
369  assert(E.NumIn <= CB.NumIn);
370  if (CB.NumOut <= E.NumOut)
371  break;
372  LLVM_DEBUG(dbgs() << "Removing " << *E.Condition << " " << E.IsNot
373  << "\n");
374  DFSInStack.pop_back();
375  CS.popLastConstraint();
376  }
377 
378  LLVM_DEBUG({
379  dbgs() << "Processing ";
380  if (CB.IsBlock)
381  dbgs() << *CB.BB;
382  else
383  dbgs() << *CB.Condition;
384  dbgs() << "\n";
385  });
386 
387  // For a block, check if any CmpInsts become known based on the current set
388  // of constraints.
389  if (CB.IsBlock) {
390  for (Instruction &I : *CB.BB) {
391  auto *Cmp = dyn_cast<CmpInst>(&I);
392  if (!Cmp)
393  continue;
394 
395  DenseMap<Value *, unsigned> NewIndices;
396  auto R = getConstraint(Cmp, Value2Index, NewIndices);
397  if (R.size() != 1)
398  continue;
399 
400  // Check if all coefficients of new indices are 0 after building the
401  // constraint. Skip if any of the new indices has a non-null
402  // coefficient.
403  bool HasNewIndex = false;
404  for (unsigned I = 0; I < NewIndices.size(); ++I) {
405  int64_t Last = R[0].Coefficients.pop_back_val();
406  if (Last != 0) {
407  HasNewIndex = true;
408  break;
409  }
410  }
411  if (HasNewIndex || R[0].size() == 1)
412  continue;
413 
414  if (CS.isConditionImplied(R[0].Coefficients)) {
415  if (!DebugCounter::shouldExecute(EliminatedCounter))
416  continue;
417 
418  LLVM_DEBUG(dbgs() << "Condition " << *Cmp
419  << " implied by dominating constraints\n");
420  LLVM_DEBUG({
421  for (auto &E : reverse(DFSInStack))
422  dbgs() << " C " << *E.Condition << " " << E.IsNot << "\n";
423  });
424  Cmp->replaceUsesWithIf(
425  ConstantInt::getTrue(F.getParent()->getContext()), [](Use &U) {
426  // Conditions in an assume trivially simplify to true. Skip uses
427  // in assume calls to not destroy the available information.
428  auto *II = dyn_cast<IntrinsicInst>(U.getUser());
429  return !II || II->getIntrinsicID() != Intrinsic::assume;
430  });
431  NumCondsRemoved++;
432  Changed = true;
433  }
434  if (CS.isConditionImplied(
435  ConstraintSystem::negate(R[0].Coefficients))) {
436  if (!DebugCounter::shouldExecute(EliminatedCounter))
437  continue;
438 
439  LLVM_DEBUG(dbgs() << "Condition !" << *Cmp
440  << " implied by dominating constraints\n");
441  LLVM_DEBUG({
442  for (auto &E : reverse(DFSInStack))
443  dbgs() << " C " << *E.Condition << " " << E.IsNot << "\n";
444  });
445  Cmp->replaceAllUsesWith(
446  ConstantInt::getFalse(F.getParent()->getContext()));
447  NumCondsRemoved++;
448  Changed = true;
449  }
450  }
451  continue;
452  }
453 
454  // Set up a function to restore the predicate at the end of the scope if it
455  // has been negated. Negate the predicate in-place, if required.
456  auto *CI = dyn_cast<CmpInst>(CB.Condition);
457  auto PredicateRestorer = make_scope_exit([CI, &CB]() {
458  if (CB.Not && CI)
459  CI->setPredicate(CI->getInversePredicate());
460  });
461  if (CB.Not) {
462  if (CI) {
463  CI->setPredicate(CI->getInversePredicate());
464  } else {
465  LLVM_DEBUG(dbgs() << "Can only negate compares so far.\n");
466  continue;
467  }
468  }
469 
470  // Otherwise, add the condition to the system and stack, if we can transform
471  // it into a constraint.
472  DenseMap<Value *, unsigned> NewIndices;
473  auto R = getConstraint(CB.Condition, Value2Index, NewIndices);
474  if (R.empty())
475  continue;
476 
477  for (auto &KV : NewIndices)
478  Value2Index.insert(KV);
479 
480  LLVM_DEBUG(dbgs() << "Adding " << *CB.Condition << " " << CB.Not << "\n");
481  bool Added = false;
482  for (auto &C : R) {
483  auto Coeffs = C.Coefficients;
484  LLVM_DEBUG({
485  dbgs() << " constraint: ";
486  dumpWithNames(C, Value2Index);
487  });
488  Added |= CS.addVariableRowFill(Coeffs);
489  // If R has been added to the system, queue it for removal once it goes
490  // out-of-scope.
491  if (Added)
492  DFSInStack.emplace_back(CB.NumIn, CB.NumOut, CB.Condition, CB.Not);
493  }
494  }
495 
496  assert(CS.size() == DFSInStack.size() &&
497  "updates to CS and DFSInStack are out of sync");
498  return Changed;
499 }
500 
503  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
504  if (!eliminateConstraints(F, DT))
505  return PreservedAnalyses::all();
506 
509  PA.preserveSet<CFGAnalyses>();
510  return PA;
511 }
512 
513 namespace {
514 
515 class ConstraintElimination : public FunctionPass {
516 public:
517  static char ID;
518 
519  ConstraintElimination() : FunctionPass(ID) {
521  }
522 
523  bool runOnFunction(Function &F) override {
524  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
525  return eliminateConstraints(F, DT);
526  }
527 
528  void getAnalysisUsage(AnalysisUsage &AU) const override {
529  AU.setPreservesCFG();
533  }
534 };
535 
536 } // end anonymous namespace
537 
539 
540 INITIALIZE_PASS_BEGIN(ConstraintElimination, "constraint-elimination",
541  "Constraint Elimination", false, false)
544 INITIALIZE_PASS_END(ConstraintElimination, "constraint-elimination",
545  "Constraint Elimination", false, false)
546 
548  return new ConstraintElimination();
549 }
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
dumpWithNames
static void dumpWithNames(ConstraintTy &C, DenseMap< Value *, unsigned > &Value2Index)
Definition: ConstraintElimination.cpp:246
llvm::predecessors
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:127
MaxConstraintValue
static int64_t MaxConstraintValue
Definition: ConstraintElimination.cpp:44
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:836
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::ConstraintSystem::addVariableRowFill
bool addVariableRowFill(const SmallVector< int64_t, 8 > &R)
Definition: ConstraintSystem.h:56
llvm::CmpInst::ICMP_EQ
@ ICMP_EQ
equal
Definition: InstrTypes.h:741
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:266
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:720
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:779
Scalar.h
llvm::Function
Definition: Function.h:61
Pass.h
getConstraint
static SmallVector< ConstraintTy, 4 > 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:129
decompose
static SmallVector< std::pair< int64_t, Value * >, 4 > decompose(Value *V)
Definition: ConstraintElimination.cpp:50
ConstraintTy::size
unsigned size() const
Definition: ConstraintElimination.cpp:122
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
Statistic.h
llvm::CmpInst::ICMP_NE
@ ICMP_NE
not equal
Definition: InstrTypes.h:742
llvm::ConstraintSystem::isConditionImplied
bool isConditionImplied(SmallVector< int64_t, 8 > R)
Definition: ConstraintSystem.cpp:145
ValueTracking.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
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:1243
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:333
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")
ConstraintTy
Definition: ConstraintElimination.cpp:116
STLExtras.h
llvm::successors
succ_range successors(Instruction *I)
Definition: CFG.h:262
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:198
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
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:115
ConstraintTy::Coefficients
SmallVector< int64_t, 8 > Coefficients
Definition: ConstraintElimination.cpp:117
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:1551
eliminateConstraints
static bool eliminateConstraints(Function &F, DominatorTree &DT)
Definition: ConstraintElimination.cpp:258
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:21
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
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:746
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:142
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:58
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:45
llvm::DebugCounter::shouldExecute
static bool shouldExecute(unsigned CounterName)
Definition: DebugCounter.h:74
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:287
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
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::ConstraintSystem::size
unsigned size() const
Returns the number of rows in the constraint system.
Definition: ConstraintSystem.h:81
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:1186
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:710
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:1219
llvm::ConstraintSystem::negate
static SmallVector< int64_t, 8 > negate(SmallVector< int64_t, 8 > R)
Definition: ConstraintSystem.h:67
llvm::ConstraintSystem::popLastConstraint
void popLastConstraint()
Definition: ConstraintSystem.h:78
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:2510
llvm::LazyValueInfoWrapperPass
Wrapper around LazyValueInfo.
Definition: LazyValueInfo.h:142
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::PreservedAnalyses::preserve
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:176
llvm::DenseMap< Value *, unsigned >
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::concat
detail::concat_range< ValueT, RangeTs... > concat(RangeTs &&... Ranges)
Concatenated range across two or more ranges.
Definition: STLExtras.h:1028
llvm::DenseMapBase::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::CmpInst::ICMP_UGE
@ ICMP_UGE
unsigned greater or equal
Definition: InstrTypes.h:744
elimination
constraint elimination
Definition: ConstraintElimination.cpp:544
llvm::PatternMatch::m_Value
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:76
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:1532
DataLayout.h
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:179
llvm::AnalysisUsage::setPreservesCFG
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:253
llvm::CmpInst::ICMP_ULT
@ ICMP_ULT
unsigned less than
Definition: InstrTypes.h:745
llvm::CFGAnalyses
Represents analyses that only rely on functions' control flow.
Definition: PassManager.h:116
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
llvm::append_range
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:1748
llvm::ConstraintEliminationPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &)
Definition: ConstraintElimination.cpp:501
llvm::ConstantInt::getSExtValue
int64_t getSExtValue() const
Return the constant as a 64-bit integer value after it has been sign extended as appropriate for the ...
Definition: Constants.h:148
llvm::DomTreeNodeBase< BasicBlock >
llvm::DenseMapBase::insert
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:207
llvm::ConstantInt::getFalse
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:855
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
llvm::ConstantInt::getTrue
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:848
llvm::DenseMapBase::end
iterator end()
Definition: DenseMap.h:83
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
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:5294
Function.h
DebugCounter.h
llvm::DenseMapBase::size
unsigned size() const
Definition: DenseMap.h:100
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1492
llvm::PatternMatch::m_NUWSub
OverflowingBinaryOp_match< LHS, RHS, Instruction::Sub, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWSub(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1227
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:252
Instructions.h
llvm::PreservedAnalyses::preserveSet
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:191
llvm::createConstraintEliminationPass
FunctionPass * createConstraintEliminationPass()
Definition: ConstraintElimination.cpp:547
ConstraintTy::ConstraintTy
ConstraintTy(SmallVector< int64_t, 8 > Coefficients)
Definition: ConstraintElimination.cpp:119
llvm::ConstantInt::isNegative
bool isNegative() const
Definition: Constants.h:189
SmallVector.h
llvm::CmpInst::ICMP_UGT
@ ICMP_UGT
unsigned greater than
Definition: InstrTypes.h:743
Dominators.h
llvm::GlobalsAAWrapperPass
Legacy wrapper pass to provide the GlobalsAAResult object.
Definition: GlobalsModRef.h:143
llvm::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:340
ScopeExit.h
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
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
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1857
llvm::PatternMatch::m_Cmp
class_match< CmpInst > m_Cmp()
Matches any compare instruction and ignore it.
Definition: PatternMatch.h:89
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
Debug.h
Elimination
constraint Constraint Elimination
Definition: ConstraintElimination.cpp:545
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:2499
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
llvm::SmallVectorImpl::emplace_back
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:908
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37