LLVM  13.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"
21 #include "llvm/IR/DataLayout.h"
22 #include "llvm/IR/Dominators.h"
23 #include "llvm/IR/Function.h"
24 #include "llvm/IR/Instructions.h"
25 #include "llvm/IR/PatternMatch.h"
26 #include "llvm/InitializePasses.h"
27 #include "llvm/Pass.h"
28 #include "llvm/Support/Debug.h"
30 #include "llvm/Transforms/Scalar.h"
31 
32 #include <string>
33 
34 using namespace llvm;
35 using namespace PatternMatch;
36 
37 #define DEBUG_TYPE "constraint-elimination"
38 
39 STATISTIC(NumCondsRemoved, "Number of instructions removed");
40 DEBUG_COUNTER(EliminatedCounter, "conds-eliminated",
41  "Controls which conditions are eliminated");
42 
44 
45 // Decomposes \p V into a vector of pairs of the form { c, X } where c * X. The
46 // sum of the pairs equals \p V. The first pair is the constant-factor and X
47 // must be nullptr. If the expression cannot be decomposed, returns an empty
48 // vector.
50  if (auto *CI = dyn_cast<ConstantInt>(V)) {
51  if (CI->isNegative() || CI->uge(MaxConstraintValue))
52  return {};
53  return {{CI->getSExtValue(), nullptr}};
54  }
55  auto *GEP = dyn_cast<GetElementPtrInst>(V);
56  if (GEP && GEP->getNumOperands() == 2 && GEP->isInBounds()) {
57  Value *Op0, *Op1;
58  ConstantInt *CI;
59 
60  // If the index is zero-extended, it is guaranteed to be positive.
61  if (match(GEP->getOperand(GEP->getNumOperands() - 1),
62  m_ZExt(m_Value(Op0)))) {
63  if (match(Op0, m_NUWShl(m_Value(Op1), m_ConstantInt(CI))))
64  return {{0, nullptr},
65  {1, GEP->getPointerOperand()},
66  {std::pow(int64_t(2), CI->getSExtValue()), Op1}};
67  if (match(Op0, m_NSWAdd(m_Value(Op1), m_ConstantInt(CI))))
68  return {{CI->getSExtValue(), nullptr},
69  {1, GEP->getPointerOperand()},
70  {1, Op1}};
71  return {{0, nullptr}, {1, GEP->getPointerOperand()}, {1, Op0}};
72  }
73 
74  if (match(GEP->getOperand(GEP->getNumOperands() - 1), m_ConstantInt(CI)) &&
75  !CI->isNegative())
76  return {{CI->getSExtValue(), nullptr}, {1, GEP->getPointerOperand()}};
77 
79  if (match(GEP->getOperand(GEP->getNumOperands() - 1),
80  m_NUWShl(m_Value(Op0), m_ConstantInt(CI))))
81  Result = {{0, nullptr},
82  {1, GEP->getPointerOperand()},
83  {std::pow(int64_t(2), CI->getSExtValue()), Op0}};
84  else if (match(GEP->getOperand(GEP->getNumOperands() - 1),
85  m_NSWAdd(m_Value(Op0), m_ConstantInt(CI))))
86  Result = {{CI->getSExtValue(), nullptr},
87  {1, GEP->getPointerOperand()},
88  {1, Op0}};
89  else {
90  Op0 = GEP->getOperand(GEP->getNumOperands() - 1);
91  Result = {{0, nullptr}, {1, GEP->getPointerOperand()}, {1, Op0}};
92  }
93  return Result;
94  }
95 
96  Value *Op0;
97  if (match(V, m_ZExt(m_Value(Op0))))
98  V = Op0;
99 
100  Value *Op1;
101  ConstantInt *CI;
102  if (match(V, m_NUWAdd(m_Value(Op0), m_ConstantInt(CI))))
103  return {{CI->getSExtValue(), nullptr}, {1, Op0}};
104  if (match(V, m_NUWAdd(m_Value(Op0), m_Value(Op1))))
105  return {{0, nullptr}, {1, Op0}, {1, Op1}};
106 
107  if (match(V, m_NUWSub(m_Value(Op0), m_ConstantInt(CI))))
108  return {{-1 * CI->getSExtValue(), nullptr}, {1, Op0}};
109  if (match(V, m_NUWSub(m_Value(Op0), m_Value(Op1))))
110  return {{0, nullptr}, {1, Op0}, {1, Op1}};
111 
112  return {{0, nullptr}, {1, V}};
113 }
114 
115 struct ConstraintTy {
117 
119  : Coefficients(Coefficients) {}
120 
121  unsigned size() const { return Coefficients.size(); }
122 };
123 
124 /// Turn a condition \p CmpI into a vector of constraints, using indices from \p
125 /// Value2Index. Additional indices for newly discovered values are added to \p
126 /// NewIndices.
129  const DenseMap<Value *, unsigned> &Value2Index,
130  DenseMap<Value *, unsigned> &NewIndices) {
131  int64_t Offset1 = 0;
132  int64_t Offset2 = 0;
133 
134  // First try to look up \p V in Value2Index and NewIndices. Otherwise add a
135  // new entry to NewIndices.
136  auto GetOrAddIndex = [&Value2Index, &NewIndices](Value *V) -> unsigned {
137  auto V2I = Value2Index.find(V);
138  if (V2I != Value2Index.end())
139  return V2I->second;
140  auto NewI = NewIndices.find(V);
141  if (NewI != NewIndices.end())
142  return NewI->second;
143  auto Insert =
144  NewIndices.insert({V, Value2Index.size() + NewIndices.size() + 1});
145  return Insert.first->second;
146  };
147 
148  if (Pred == CmpInst::ICMP_UGT || Pred == CmpInst::ICMP_UGE)
149  return getConstraint(CmpInst::getSwappedPredicate(Pred), Op1, Op0,
150  Value2Index, NewIndices);
151 
152  if (Pred == CmpInst::ICMP_EQ) {
153  auto A =
154  getConstraint(CmpInst::ICMP_UGE, Op0, Op1, Value2Index, NewIndices);
155  auto B =
156  getConstraint(CmpInst::ICMP_ULE, Op0, Op1, Value2Index, NewIndices);
157  append_range(A, B);
158  return A;
159  }
160 
161  if (Pred == CmpInst::ICMP_NE && match(Op1, m_Zero())) {
162  return getConstraint(CmpInst::ICMP_UGT, Op0, Op1, Value2Index, NewIndices);
163  }
164 
165  // Only ULE and ULT predicates are supported at the moment.
166  if (Pred != CmpInst::ICMP_ULE && Pred != CmpInst::ICMP_ULT)
167  return {};
168 
169  auto ADec = decompose(Op0->stripPointerCastsSameRepresentation());
170  auto BDec = decompose(Op1->stripPointerCastsSameRepresentation());
171  // Skip if decomposing either of the values failed.
172  if (ADec.empty() || BDec.empty())
173  return {};
174 
175  // Skip trivial constraints without any variables.
176  if (ADec.size() == 1 && BDec.size() == 1)
177  return {};
178 
179  Offset1 = ADec[0].first;
180  Offset2 = BDec[0].first;
181  Offset1 *= -1;
182 
183  // Create iterator ranges that skip the constant-factor.
184  auto VariablesA = llvm::drop_begin(ADec);
185  auto VariablesB = llvm::drop_begin(BDec);
186 
187  // Make sure all variables have entries in Value2Index or NewIndices.
188  for (const auto &KV :
189  concat<std::pair<int64_t, Value *>>(VariablesA, VariablesB))
190  GetOrAddIndex(KV.second);
191 
192  // Build result constraint, by first adding all coefficients from A and then
193  // subtracting all coefficients from B.
194  SmallVector<int64_t, 8> R(Value2Index.size() + NewIndices.size() + 1, 0);
195  for (const auto &KV : VariablesA)
196  R[GetOrAddIndex(KV.second)] += KV.first;
197 
198  for (const auto &KV : VariablesB)
199  R[GetOrAddIndex(KV.second)] -= KV.first;
200 
201  R[0] = Offset1 + Offset2 + (Pred == CmpInst::ICMP_ULT ? -1 : 0);
202  return {R};
203 }
204 
207  DenseMap<Value *, unsigned> &NewIndices) {
208  return getConstraint(Cmp->getPredicate(), Cmp->getOperand(0),
209  Cmp->getOperand(1), Value2Index, NewIndices);
210 }
211 
212 namespace {
213 /// Represents either a condition that holds on entry to a block or a basic
214 /// block, with their respective Dominator DFS in and out numbers.
215 struct ConstraintOrBlock {
216  unsigned NumIn;
217  unsigned NumOut;
218  bool IsBlock;
219  bool Not;
220  union {
221  BasicBlock *BB;
222  CmpInst *Condition;
223  };
224 
225  ConstraintOrBlock(DomTreeNode *DTN)
226  : NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()), IsBlock(true),
227  BB(DTN->getBlock()) {}
228  ConstraintOrBlock(DomTreeNode *DTN, CmpInst *Condition, bool Not)
229  : NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()), IsBlock(false),
230  Not(Not), Condition(Condition) {}
231 };
232 
233 struct StackEntry {
234  unsigned NumIn;
235  unsigned NumOut;
236  CmpInst *Condition;
237  bool IsNot;
238 
239  StackEntry(unsigned NumIn, unsigned NumOut, CmpInst *Condition, bool IsNot)
240  : NumIn(NumIn), NumOut(NumOut), Condition(Condition), IsNot(IsNot) {}
241 };
242 } // namespace
243 
244 #ifndef NDEBUG
246  DenseMap<Value *, unsigned> &Value2Index) {
247  SmallVector<std::string> Names(Value2Index.size(), "");
248  for (auto &KV : Value2Index) {
249  Names[KV.second - 1] = std::string("%") + KV.first->getName().str();
250  }
251  ConstraintSystem CS;
252  CS.addVariableRowFill(C.Coefficients);
253  CS.dump(Names);
254 }
255 #endif
256 
258  bool Changed = false;
259  DT.updateDFSNumbers();
260  ConstraintSystem CS;
261 
263 
264  // First, collect conditions implied by branches and blocks with their
265  // Dominator DFS in and out numbers.
266  for (BasicBlock &BB : F) {
267  if (!DT.getNode(&BB))
268  continue;
269  WorkList.emplace_back(DT.getNode(&BB));
270 
271  auto *Br = dyn_cast<BranchInst>(BB.getTerminator());
272  if (!Br || !Br->isConditional())
273  continue;
274 
275  // Returns true if we can add a known condition from BB to its successor
276  // block Succ. Each predecessor of Succ can either be BB or be dominated by
277  // Succ (e.g. the case when adding a condition from a pre-header to a loop
278  // header).
279  auto CanAdd = [&BB, &DT](BasicBlock *Succ) {
280  return all_of(predecessors(Succ), [&BB, &DT, Succ](BasicBlock *Pred) {
281  return Pred == &BB || DT.dominates(Succ, Pred);
282  });
283  };
284  // If the condition is an OR of 2 compares and the false successor only has
285  // the current block as predecessor, queue both negated conditions for the
286  // false successor.
287  Value *Op0, *Op1;
288  if (match(Br->getCondition(), m_LogicalOr(m_Value(Op0), m_Value(Op1))) &&
289  match(Op0, m_Cmp()) && match(Op1, m_Cmp())) {
290  BasicBlock *FalseSuccessor = Br->getSuccessor(1);
291  if (CanAdd(FalseSuccessor)) {
292  WorkList.emplace_back(DT.getNode(FalseSuccessor), cast<CmpInst>(Op0),
293  true);
294  WorkList.emplace_back(DT.getNode(FalseSuccessor), cast<CmpInst>(Op1),
295  true);
296  }
297  continue;
298  }
299 
300  // If the condition is an AND of 2 compares and the true successor only has
301  // the current block as predecessor, queue both conditions for the true
302  // successor.
303  if (match(Br->getCondition(), m_LogicalAnd(m_Value(Op0), m_Value(Op1))) &&
304  match(Op0, m_Cmp()) && match(Op1, m_Cmp())) {
305  BasicBlock *TrueSuccessor = Br->getSuccessor(0);
306  if (CanAdd(TrueSuccessor)) {
307  WorkList.emplace_back(DT.getNode(TrueSuccessor), cast<CmpInst>(Op0),
308  false);
309  WorkList.emplace_back(DT.getNode(TrueSuccessor), cast<CmpInst>(Op1),
310  false);
311  }
312  continue;
313  }
314 
315  auto *CmpI = dyn_cast<CmpInst>(Br->getCondition());
316  if (!CmpI)
317  continue;
318  if (CanAdd(Br->getSuccessor(0)))
319  WorkList.emplace_back(DT.getNode(Br->getSuccessor(0)), CmpI, false);
320  if (CanAdd(Br->getSuccessor(1)))
321  WorkList.emplace_back(DT.getNode(Br->getSuccessor(1)), CmpI, true);
322  }
323 
324  // Next, sort worklist by dominance, so that dominating blocks and conditions
325  // come before blocks and conditions dominated by them. If a block and a
326  // condition have the same numbers, the condition comes before the block, as
327  // it holds on entry to the block.
328  sort(WorkList, [](const ConstraintOrBlock &A, const ConstraintOrBlock &B) {
329  return std::tie(A.NumIn, A.IsBlock) < std::tie(B.NumIn, B.IsBlock);
330  });
331 
332  // Finally, process ordered worklist and eliminate implied conditions.
333  SmallVector<StackEntry, 16> DFSInStack;
334  DenseMap<Value *, unsigned> Value2Index;
335  for (ConstraintOrBlock &CB : WorkList) {
336  // First, pop entries from the stack that are out-of-scope for CB. Remove
337  // the corresponding entry from the constraint system.
338  while (!DFSInStack.empty()) {
339  auto &E = DFSInStack.back();
340  LLVM_DEBUG(dbgs() << "Top of stack : " << E.NumIn << " " << E.NumOut
341  << "\n");
342  LLVM_DEBUG(dbgs() << "CB: " << CB.NumIn << " " << CB.NumOut << "\n");
343  assert(E.NumIn <= CB.NumIn);
344  if (CB.NumOut <= E.NumOut)
345  break;
346  LLVM_DEBUG(dbgs() << "Removing " << *E.Condition << " " << E.IsNot
347  << "\n");
348  DFSInStack.pop_back();
349  CS.popLastConstraint();
350  }
351 
352  LLVM_DEBUG({
353  dbgs() << "Processing ";
354  if (CB.IsBlock)
355  dbgs() << *CB.BB;
356  else
357  dbgs() << *CB.Condition;
358  dbgs() << "\n";
359  });
360 
361  // For a block, check if any CmpInsts become known based on the current set
362  // of constraints.
363  if (CB.IsBlock) {
364  for (Instruction &I : *CB.BB) {
365  auto *Cmp = dyn_cast<CmpInst>(&I);
366  if (!Cmp)
367  continue;
368 
369  DenseMap<Value *, unsigned> NewIndices;
370  auto R = getConstraint(Cmp, Value2Index, NewIndices);
371  if (R.size() != 1)
372  continue;
373 
374  // Check if all coefficients of new indices are 0 after building the
375  // constraint. Skip if any of the new indices has a non-null
376  // coefficient.
377  bool HasNewIndex = false;
378  for (unsigned I = 0; I < NewIndices.size(); ++I) {
379  int64_t Last = R[0].Coefficients.pop_back_val();
380  if (Last != 0) {
381  HasNewIndex = true;
382  break;
383  }
384  }
385  if (HasNewIndex || R[0].size() == 1)
386  continue;
387 
388  if (CS.isConditionImplied(R[0].Coefficients)) {
389  if (!DebugCounter::shouldExecute(EliminatedCounter))
390  continue;
391 
392  LLVM_DEBUG(dbgs() << "Condition " << *Cmp
393  << " implied by dominating constraints\n");
394  LLVM_DEBUG({
395  for (auto &E : reverse(DFSInStack))
396  dbgs() << " C " << *E.Condition << " " << E.IsNot << "\n";
397  });
398  Cmp->replaceAllUsesWith(
399  ConstantInt::getTrue(F.getParent()->getContext()));
400  NumCondsRemoved++;
401  Changed = true;
402  }
403  if (CS.isConditionImplied(
404  ConstraintSystem::negate(R[0].Coefficients))) {
405  if (!DebugCounter::shouldExecute(EliminatedCounter))
406  continue;
407 
408  LLVM_DEBUG(dbgs() << "Condition !" << *Cmp
409  << " implied by dominating constraints\n");
410  LLVM_DEBUG({
411  for (auto &E : reverse(DFSInStack))
412  dbgs() << " C " << *E.Condition << " " << E.IsNot << "\n";
413  });
414  Cmp->replaceAllUsesWith(
415  ConstantInt::getFalse(F.getParent()->getContext()));
416  NumCondsRemoved++;
417  Changed = true;
418  }
419  }
420  continue;
421  }
422 
423  // Set up a function to restore the predicate at the end of the scope if it
424  // has been negated. Negate the predicate in-place, if required.
425  auto *CI = dyn_cast<CmpInst>(CB.Condition);
426  auto PredicateRestorer = make_scope_exit([CI, &CB]() {
427  if (CB.Not && CI)
428  CI->setPredicate(CI->getInversePredicate());
429  });
430  if (CB.Not) {
431  if (CI) {
432  CI->setPredicate(CI->getInversePredicate());
433  } else {
434  LLVM_DEBUG(dbgs() << "Can only negate compares so far.\n");
435  continue;
436  }
437  }
438 
439  // Otherwise, add the condition to the system and stack, if we can transform
440  // it into a constraint.
441  DenseMap<Value *, unsigned> NewIndices;
442  auto R = getConstraint(CB.Condition, Value2Index, NewIndices);
443  if (R.empty())
444  continue;
445 
446  for (auto &KV : NewIndices)
447  Value2Index.insert(KV);
448 
449  LLVM_DEBUG(dbgs() << "Adding " << *CB.Condition << " " << CB.Not << "\n");
450  bool Added = false;
451  for (auto &C : R) {
452  auto Coeffs = C.Coefficients;
453  LLVM_DEBUG({
454  dbgs() << " constraint: ";
455  dumpWithNames(C, Value2Index);
456  });
457  Added |= CS.addVariableRowFill(Coeffs);
458  // If R has been added to the system, queue it for removal once it goes
459  // out-of-scope.
460  if (Added)
461  DFSInStack.emplace_back(CB.NumIn, CB.NumOut, CB.Condition, CB.Not);
462  }
463  }
464 
465  assert(CS.size() == DFSInStack.size() &&
466  "updates to CS and DFSInStack are out of sync");
467  return Changed;
468 }
469 
472  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
473  if (!eliminateConstraints(F, DT))
474  return PreservedAnalyses::all();
475 
478  PA.preserve<GlobalsAA>();
479  PA.preserveSet<CFGAnalyses>();
480  return PA;
481 }
482 
483 namespace {
484 
485 class ConstraintElimination : public FunctionPass {
486 public:
487  static char ID;
488 
489  ConstraintElimination() : FunctionPass(ID) {
491  }
492 
493  bool runOnFunction(Function &F) override {
494  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
495  return eliminateConstraints(F, DT);
496  }
497 
498  void getAnalysisUsage(AnalysisUsage &AU) const override {
499  AU.setPreservesCFG();
503  }
504 };
505 
506 } // end anonymous namespace
507 
509 
510 INITIALIZE_PASS_BEGIN(ConstraintElimination, "constraint-elimination",
511  "Constraint Elimination", false, false)
514 INITIALIZE_PASS_END(ConstraintElimination, "constraint-elimination",
515  "Constraint Elimination", false, false)
516 
518  return new ConstraintElimination();
519 }
llvm::GlobalsAA
Analysis pass providing a never-invalidated alias analysis result.
Definition: GlobalsModRef.h:132
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:245
llvm::predecessors
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:127
MaxConstraintValue
static int64_t MaxConstraintValue
Definition: ConstraintElimination.cpp:43
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:839
llvm
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:743
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:722
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:785
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:128
decompose
static SmallVector< std::pair< int64_t, Value * >, 4 > decompose(Value *V)
Definition: ConstraintElimination.cpp:49
ConstraintTy::size
unsigned size() const
Definition: ConstraintElimination.cpp:121
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:744
llvm::ConstraintSystem::isConditionImplied
bool isConditionImplied(SmallVector< int64_t, 8 > R)
Definition: ConstraintSystem.cpp:145
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:329
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:115
STLExtras.h
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:122
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:133
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:132
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:116
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:77
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:1482
eliminateConstraints
static bool eliminateConstraints(Function &F, DominatorTree &DT)
Definition: ConstraintElimination.cpp:257
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:748
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:281
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:712
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:2506
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:1011
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:746
elimination
constraint elimination
Definition: ConstraintElimination.cpp:514
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:1463
DataLayout.h
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:747
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:1667
llvm::ConstraintEliminationPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &)
Definition: ConstraintElimination.cpp:470
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:146
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:840
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
llvm::ConstantInt::getTrue
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:833
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
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:1423
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:517
ConstraintTy::ConstraintTy
ConstraintTy(SmallVector< int64_t, 8 > Coefficients)
Definition: ConstraintElimination.cpp:118
llvm::ConstantInt::isNegative
bool isNegative() const
Definition: Constants.h:187
SmallVector.h
llvm::CmpInst::ICMP_UGT
@ ICMP_UGT
unsigned greater than
Definition: InstrTypes.h:745
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:171
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1797
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:515
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:2495
llvm::SmallVectorImpl::emplace_back
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:908
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38