LLVM  12.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/SmallVector.h"
17 #include "llvm/ADT/Statistic.h"
20 #include "llvm/IR/DataLayout.h"
21 #include "llvm/IR/Dominators.h"
22 #include "llvm/IR/Function.h"
23 #include "llvm/IR/Instructions.h"
24 #include "llvm/IR/PatternMatch.h"
25 #include "llvm/InitializePasses.h"
26 #include "llvm/Pass.h"
27 #include "llvm/Support/Debug.h"
29 #include "llvm/Transforms/Scalar.h"
30 
31 using namespace llvm;
32 using namespace PatternMatch;
33 
34 #define DEBUG_TYPE "constraint-elimination"
35 
36 STATISTIC(NumCondsRemoved, "Number of instructions removed");
37 DEBUG_COUNTER(EliminatedCounter, "conds-eliminated",
38  "Controls which conditions are eliminated");
39 
41 
42 // Decomposes \p V into a vector of pairs of the form { c, X } where c * X. The
43 // sum of the pairs equals \p V. The first pair is the constant-factor and X
44 // must be nullptr. If the expression cannot be decomposed, returns an empty
45 // vector.
47  if (auto *CI = dyn_cast<ConstantInt>(V)) {
48  if (CI->isNegative() || CI->uge(MaxConstraintValue))
49  return {};
50  return {{CI->getSExtValue(), nullptr}};
51  }
52  auto *GEP = dyn_cast<GetElementPtrInst>(V);
53  if (GEP && GEP->getNumOperands() == 2) {
54  if (isa<ConstantInt>(GEP->getOperand(GEP->getNumOperands() - 1))) {
55  return {{cast<ConstantInt>(GEP->getOperand(GEP->getNumOperands() - 1))
56  ->getSExtValue(),
57  nullptr},
58  {1, GEP->getPointerOperand()}};
59  }
60  Value *Op0;
61  ConstantInt *CI;
62  if (match(GEP->getOperand(GEP->getNumOperands() - 1),
63  m_NUWShl(m_Value(Op0), m_ConstantInt(CI))))
64  return {{0, nullptr},
65  {1, GEP->getPointerOperand()},
66  {std::pow(int64_t(2), CI->getSExtValue()), Op0}};
67  if (match(GEP->getOperand(GEP->getNumOperands() - 1),
68  m_ZExt(m_NUWShl(m_Value(Op0), m_ConstantInt(CI)))))
69  return {{0, nullptr},
70  {1, GEP->getPointerOperand()},
71  {std::pow(int64_t(2), CI->getSExtValue()), Op0}};
72 
73  return {{0, nullptr},
74  {1, GEP->getPointerOperand()},
75  {1, GEP->getOperand(GEP->getNumOperands() - 1)}};
76  }
77 
78  Value *Op0;
79  Value *Op1;
80  ConstantInt *CI;
81  if (match(V, m_NUWAdd(m_Value(Op0), m_ConstantInt(CI))))
82  return {{CI->getSExtValue(), nullptr}, {1, Op0}};
83  if (match(V, m_NUWAdd(m_Value(Op0), m_Value(Op1))))
84  return {{0, nullptr}, {1, Op0}, {1, Op1}};
85 
86  if (match(V, m_NUWSub(m_Value(Op0), m_ConstantInt(CI))))
87  return {{-1 * CI->getSExtValue(), nullptr}, {1, Op0}};
88  if (match(V, m_NUWSub(m_Value(Op0), m_Value(Op1))))
89  return {{0, nullptr}, {1, Op0}, {1, Op1}};
90 
91  return {{0, nullptr}, {1, V}};
92 }
93 
94 /// Turn a condition \p CmpI into a constraint vector, using indices from \p
95 /// Value2Index. If \p ShouldAdd is true, new indices are added for values not
96 /// yet in \p Value2Index.
99  DenseMap<Value *, unsigned> &Value2Index, bool ShouldAdd) {
100  int64_t Offset1 = 0;
101  int64_t Offset2 = 0;
102 
103  auto TryToGetIndex = [ShouldAdd,
104  &Value2Index](Value *V) -> Optional<unsigned> {
105  if (ShouldAdd) {
106  Value2Index.insert({V, Value2Index.size() + 1});
107  return Value2Index[V];
108  }
109  auto I = Value2Index.find(V);
110  if (I == Value2Index.end())
111  return None;
112  return I->second;
113  };
114 
115  if (Pred == CmpInst::ICMP_UGT || Pred == CmpInst::ICMP_UGE)
116  return getConstraint(CmpInst::getSwappedPredicate(Pred), Op1, Op0,
117  Value2Index, ShouldAdd);
118 
119  // Only ULE and ULT predicates are supported at the moment.
120  if (Pred != CmpInst::ICMP_ULE && Pred != CmpInst::ICMP_ULT)
121  return {};
122 
123  auto ADec = decompose(Op0);
124  auto BDec = decompose(Op1);
125  // Skip if decomposing either of the values failed.
126  if (ADec.empty() || BDec.empty())
127  return {};
128 
129  // Skip trivial constraints without any variables.
130  if (ADec.size() == 1 && BDec.size() == 1)
131  return {};
132 
133  Offset1 = ADec[0].first;
134  Offset2 = BDec[0].first;
135  Offset1 *= -1;
136 
137  // Create iterator ranges that skip the constant-factor.
138  auto VariablesA = make_range(std::next(ADec.begin()), ADec.end());
139  auto VariablesB = make_range(std::next(BDec.begin()), BDec.end());
140 
141  // Check if each referenced value in the constraint is already in the system
142  // or can be added (if ShouldAdd is true).
143  for (const auto &KV :
144  concat<std::pair<int64_t, Value *>>(VariablesA, VariablesB))
145  if (!TryToGetIndex(KV.second))
146  return {};
147 
148  // Build result constraint, by first adding all coefficients from A and then
149  // subtracting all coefficients from B.
150  SmallVector<int64_t, 8> R(Value2Index.size() + 1, 0);
151  for (const auto &KV : VariablesA)
152  R[Value2Index[KV.second]] += KV.first;
153 
154  for (const auto &KV : VariablesB)
155  R[Value2Index[KV.second]] -= KV.first;
156 
157  R[0] = Offset1 + Offset2 + (Pred == CmpInst::ICMP_ULT ? -1 : 0);
158  return R;
159 }
160 
163  bool ShouldAdd) {
164  return getConstraint(Cmp->getPredicate(), Cmp->getOperand(0),
165  Cmp->getOperand(1), Value2Index, ShouldAdd);
166 }
167 
168 namespace {
169 /// Represents either a condition that holds on entry to a block or a basic
170 /// block, with their respective Dominator DFS in and out numbers.
171 struct ConstraintOrBlock {
172  unsigned NumIn;
173  unsigned NumOut;
174  bool IsBlock;
175  bool Not;
176  union {
177  BasicBlock *BB;
178  CmpInst *Condition;
179  };
180 
181  ConstraintOrBlock(DomTreeNode *DTN)
182  : NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()), IsBlock(true),
183  BB(DTN->getBlock()) {}
184  ConstraintOrBlock(DomTreeNode *DTN, CmpInst *Condition, bool Not)
185  : NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()), IsBlock(false),
186  Not(Not), Condition(Condition) {}
187 };
188 
189 struct StackEntry {
190  unsigned NumIn;
191  unsigned NumOut;
192  CmpInst *Condition;
193  bool IsNot;
194 
195  StackEntry(unsigned NumIn, unsigned NumOut, CmpInst *Condition, bool IsNot)
196  : NumIn(NumIn), NumOut(NumOut), Condition(Condition), IsNot(IsNot) {}
197 };
198 } // namespace
199 
201  bool Changed = false;
202  DT.updateDFSNumbers();
203  ConstraintSystem CS;
204 
206 
207  // First, collect conditions implied by branches and blocks with their
208  // Dominator DFS in and out numbers.
209  for (BasicBlock &BB : F) {
210  if (!DT.getNode(&BB))
211  continue;
212  WorkList.emplace_back(DT.getNode(&BB));
213 
214  auto *Br = dyn_cast<BranchInst>(BB.getTerminator());
215  if (!Br || !Br->isConditional())
216  continue;
217 
218  // If the condition is an OR of 2 compares and the false successor only has
219  // the current block as predecessor, queue both negated conditions for the
220  // false successor.
221  Value *Op0, *Op1;
222  if (match(Br->getCondition(), m_LogicalOr(m_Value(Op0), m_Value(Op1))) &&
223  match(Op0, m_Cmp()) && match(Op1, m_Cmp())) {
224  BasicBlock *FalseSuccessor = Br->getSuccessor(1);
225  if (FalseSuccessor->getSinglePredecessor()) {
226  WorkList.emplace_back(DT.getNode(FalseSuccessor), cast<CmpInst>(Op0),
227  true);
228  WorkList.emplace_back(DT.getNode(FalseSuccessor), cast<CmpInst>(Op1),
229  true);
230  }
231  continue;
232  }
233 
234  // If the condition is an AND of 2 compares and the true successor only has
235  // the current block as predecessor, queue both conditions for the true
236  // successor.
237  if (match(Br->getCondition(), m_LogicalAnd(m_Value(Op0), m_Value(Op1))) &&
238  match(Op0, m_Cmp()) && match(Op1, m_Cmp())) {
239  BasicBlock *TrueSuccessor = Br->getSuccessor(0);
240  if (TrueSuccessor->getSinglePredecessor()) {
241  WorkList.emplace_back(DT.getNode(TrueSuccessor), cast<CmpInst>(Op0),
242  false);
243  WorkList.emplace_back(DT.getNode(TrueSuccessor), cast<CmpInst>(Op1),
244  false);
245  }
246  continue;
247  }
248 
249  auto *CmpI = dyn_cast<CmpInst>(Br->getCondition());
250  if (!CmpI)
251  continue;
252  if (Br->getSuccessor(0)->getSinglePredecessor())
253  WorkList.emplace_back(DT.getNode(Br->getSuccessor(0)), CmpI, false);
254  if (Br->getSuccessor(1)->getSinglePredecessor())
255  WorkList.emplace_back(DT.getNode(Br->getSuccessor(1)), CmpI, true);
256  }
257 
258  // Next, sort worklist by dominance, so that dominating blocks and conditions
259  // come before blocks and conditions dominated by them. If a block and a
260  // condition have the same numbers, the condition comes before the block, as
261  // it holds on entry to the block.
262  sort(WorkList, [](const ConstraintOrBlock &A, const ConstraintOrBlock &B) {
263  return std::tie(A.NumIn, A.IsBlock) < std::tie(B.NumIn, B.IsBlock);
264  });
265 
266  // Finally, process ordered worklist and eliminate implied conditions.
267  SmallVector<StackEntry, 16> DFSInStack;
268  DenseMap<Value *, unsigned> Value2Index;
269  for (ConstraintOrBlock &CB : WorkList) {
270  // First, pop entries from the stack that are out-of-scope for CB. Remove
271  // the corresponding entry from the constraint system.
272  while (!DFSInStack.empty()) {
273  auto &E = DFSInStack.back();
274  LLVM_DEBUG(dbgs() << "Top of stack : " << E.NumIn << " " << E.NumOut
275  << "\n");
276  LLVM_DEBUG(dbgs() << "CB: " << CB.NumIn << " " << CB.NumOut << "\n");
277  assert(E.NumIn <= CB.NumIn);
278  if (CB.NumOut <= E.NumOut)
279  break;
280  LLVM_DEBUG(dbgs() << "Removing " << *E.Condition << " " << E.IsNot
281  << "\n");
282  DFSInStack.pop_back();
283  CS.popLastConstraint();
284  }
285 
286  LLVM_DEBUG({
287  dbgs() << "Processing ";
288  if (CB.IsBlock)
289  dbgs() << *CB.BB;
290  else
291  dbgs() << *CB.Condition;
292  dbgs() << "\n";
293  });
294 
295  // For a block, check if any CmpInsts become known based on the current set
296  // of constraints.
297  if (CB.IsBlock) {
298  for (Instruction &I : *CB.BB) {
299  auto *Cmp = dyn_cast<CmpInst>(&I);
300  if (!Cmp)
301  continue;
302  auto R = getConstraint(Cmp, Value2Index, false);
303  if (R.empty() || R.size() == 1)
304  continue;
305  if (CS.isConditionImplied(R)) {
306  if (!DebugCounter::shouldExecute(EliminatedCounter))
307  continue;
308 
309  LLVM_DEBUG(dbgs() << "Condition " << *Cmp
310  << " implied by dominating constraints\n");
311  LLVM_DEBUG({
312  for (auto &E : reverse(DFSInStack))
313  dbgs() << " C " << *E.Condition << " " << E.IsNot << "\n";
314  });
315  Cmp->replaceAllUsesWith(
316  ConstantInt::getTrue(F.getParent()->getContext()));
317  NumCondsRemoved++;
318  Changed = true;
319  }
321  if (!DebugCounter::shouldExecute(EliminatedCounter))
322  continue;
323 
324  LLVM_DEBUG(dbgs() << "Condition !" << *Cmp
325  << " implied by dominating constraints\n");
326  LLVM_DEBUG({
327  for (auto &E : reverse(DFSInStack))
328  dbgs() << " C " << *E.Condition << " " << E.IsNot << "\n";
329  });
330  Cmp->replaceAllUsesWith(
331  ConstantInt::getFalse(F.getParent()->getContext()));
332  NumCondsRemoved++;
333  Changed = true;
334  }
335  }
336  continue;
337  }
338 
339  // Otherwise, add the condition to the system and stack, if we can transform
340  // it into a constraint.
341  auto R = getConstraint(CB.Condition, Value2Index, true);
342  if (R.empty())
343  continue;
344 
345  LLVM_DEBUG(dbgs() << "Adding " << *CB.Condition << " " << CB.Not << "\n");
346  if (CB.Not)
348 
349  // If R has been added to the system, queue it for removal once it goes
350  // out-of-scope.
351  if (CS.addVariableRowFill(R))
352  DFSInStack.emplace_back(CB.NumIn, CB.NumOut, CB.Condition, CB.Not);
353  }
354 
355  return Changed;
356 }
357 
360  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
361  if (!eliminateConstraints(F, DT))
362  return PreservedAnalyses::all();
363 
366  PA.preserve<GlobalsAA>();
367  PA.preserveSet<CFGAnalyses>();
368  return PA;
369 }
370 
371 namespace {
372 
373 class ConstraintElimination : public FunctionPass {
374 public:
375  static char ID;
376 
377  ConstraintElimination() : FunctionPass(ID) {
379  }
380 
381  bool runOnFunction(Function &F) override {
382  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
383  return eliminateConstraints(F, DT);
384  }
385 
386  void getAnalysisUsage(AnalysisUsage &AU) const override {
387  AU.setPreservesCFG();
391  }
392 };
393 
394 } // end anonymous namespace
395 
397 
398 INITIALIZE_PASS_BEGIN(ConstraintElimination, "constraint-elimination",
399  "Constraint Elimination", false, false)
402 INITIALIZE_PASS_END(ConstraintElimination, "constraint-elimination",
403  "Constraint Elimination", false, false)
404 
406  return new ConstraintElimination();
407 }
Legacy wrapper pass to provide the GlobalsAAResult object.
detail::concat_range< ValueT, RangeTs... > concat(RangeTs &&... Ranges)
Concatenated range across two or more ranges.
Definition: STLExtras.h:1020
const NoneType None
Definition: None.h:23
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:822
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:856
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:76
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:712
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
static SmallVector< int64_t, 8 > negate(SmallVector< int64_t, 8 > R)
class_match< CmpInst > m_Cmp()
Matches any compare instruction and ignore it.
Definition: PatternMatch.h:89
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:785
This class represents lattice values for constants.
Definition: AllocatorList.h:23
Wrapper around LazyValueInfo.
This is the interface for a simple mod/ref and alias analysis over globals.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &)
unsigned less than
Definition: InstrTypes.h:747
INITIALIZE_PASS_BEGIN(ConstraintElimination, "constraint-elimination", "Constraint Elimination", false, false) INITIALIZE_PASS_END(ConstraintElimination
STATISTIC(NumFunctions, "Total number of functions")
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:249
F(f)
Hexagon Common GEP
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:722
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:207
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
AnalysisUsage & addRequired()
This file provides an implementation of debug counters.
OverflowingBinaryOp_match< LHS, RHS, Instruction::Add, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWAdd(const LHS &L, const RHS &R)
static SmallVector< int64_t, 8 > getConstraint(CmpInst::Predicate Pred, Value *Op0, Value *Op1, DenseMap< Value *, unsigned > &Value2Index, bool ShouldAdd)
Turn a condition CmpI into a constraint vector, using indices from Value2Index.
CastClass_match< OpTy, Instruction::ZExt > m_ZExt(const OpTy &Op)
Matches ZExt.
unsigned greater or equal
Definition: InstrTypes.h:746
static SmallVector< std::pair< int64_t, Value * >, 4 > decompose(Value *V)
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
Definition: PatternMatch.h:101
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
static bool runOnFunction(Function &F, bool PostInlining)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:264
bool isConditionImplied(SmallVector< int64_t, 8 > R)
OverflowingBinaryOp_match< LHS, RHS, Instruction::Shl, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWShl(const LHS &L, const RHS &R)
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
static int64_t MaxConstraintValue
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
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.
Represent the analysis usage information of a pass.
unsigned greater than
Definition: InstrTypes.h:745
Analysis pass providing a never-invalidated alias analysis result.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
static bool shouldExecute(unsigned CounterName)
Definition: DebugCounter.h:74
unsigned size() const
Definition: DenseMap.h:100
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1439
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
This is the shared class of boolean and integer constants.
Definition: Constants.h:77
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:350
constraint Constraint Elimination
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1116
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:253
void initializeConstraintEliminationPass(PassRegistry &)
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:815
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
FunctionPass * createConstraintEliminationPass()
unsigned less or equal
Definition: InstrTypes.h:748
Represents analyses that only rely on functions' control flow.
Definition: PassManager.h:116
static bool eliminateConstraints(Function &F, DominatorTree &DT)
DEBUG_COUNTER(EliminatedCounter, "conds-eliminated", "Controls which conditions are eliminated")
OverflowingBinaryOp_match< LHS, RHS, Instruction::Sub, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWSub(const LHS &L, const RHS &R)
basic Basic Alias true
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:191
#define I(x, y, z)
Definition: MD5.cpp:59
iterator end()
Definition: DenseMap.h:83
bool addVariableRowFill(const SmallVector< int64_t, 8 > &R)
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.
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:176
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void updateDFSNumbers() const
updateDFSNumbers - Assign In and Out numbers to the nodes while walking dominator tree in dfs order.
LLVM Value Representation.
Definition: Value.h:75
constraint elimination
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition: InstrTypes.h:839
A container for analyses that lazily runs them and caches their results.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:278
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:152
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:338
#define LLVM_DEBUG(X)
Definition: Debug.h:122
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)