xref: /llvm-project/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp (revision 80eea38d8dfa02d9f1312faa1f922f14cd3e4da0)
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 
14 #include "llvm/Transforms/Scalar/ConstraintElimination.h"
15 #include "llvm/ADT/STLExtras.h"
16 #include "llvm/ADT/ScopeExit.h"
17 #include "llvm/ADT/SmallVector.h"
18 #include "llvm/ADT/Statistic.h"
19 #include "llvm/Analysis/ConstraintSystem.h"
20 #include "llvm/Analysis/GlobalsModRef.h"
21 #include "llvm/Analysis/ValueTracking.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"
30 #include "llvm/Support/DebugCounter.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 
44 static int64_t MaxConstraintValue = std::numeric_limits<int64_t>::max();
45 static int64_t MinSignedConstraintValue = std::numeric_limits<int64_t>::min();
46 
47 namespace {
48 
49 /// Wrapper encapsulating separate constraint systems and corresponding value
50 /// mappings for both unsigned and signed information. Facts are added to and
51 /// conditions are checked against the corresponding system depending on the
52 /// signed-ness of their predicates. While the information is kept separate
53 /// based on signed-ness, certain conditions can be transferred between the two
54 /// systems.
55 class ConstraintInfo {
56   DenseMap<Value *, unsigned> UnsignedValue2Index;
57   DenseMap<Value *, unsigned> SignedValue2Index;
58 
59   ConstraintSystem UnsignedCS;
60   ConstraintSystem SignedCS;
61 
62 public:
63   DenseMap<Value *, unsigned> &getValue2Index(bool Signed) {
64     return Signed ? SignedValue2Index : UnsignedValue2Index;
65   }
66   const DenseMap<Value *, unsigned> &getValue2Index(bool Signed) const {
67     return Signed ? SignedValue2Index : UnsignedValue2Index;
68   }
69 
70   ConstraintSystem &getCS(bool Signed) {
71     return Signed ? SignedCS : UnsignedCS;
72   }
73   const ConstraintSystem &getCS(bool Signed) const {
74     return Signed ? SignedCS : UnsignedCS;
75   }
76 
77   void popLastConstraint(bool Signed) { getCS(Signed).popLastConstraint(); }
78 };
79 
80 /// Struct to express a pre-condition of the form %Op0 Pred %Op1.
81 struct PreconditionTy {
82   CmpInst::Predicate Pred;
83   Value *Op0;
84   Value *Op1;
85 
86   PreconditionTy(CmpInst::Predicate Pred, Value *Op0, Value *Op1)
87       : Pred(Pred), Op0(Op0), Op1(Op1) {}
88 };
89 
90 struct ConstraintTy {
91   SmallVector<int64_t, 8> Coefficients;
92 
93   bool IsSigned;
94 
95   ConstraintTy(SmallVector<int64_t, 8> Coefficients, bool IsSigned)
96       : Coefficients(Coefficients), IsSigned(IsSigned) {}
97 
98   unsigned size() const { return Coefficients.size(); }
99 };
100 
101 /// Struct to manage a list of constraints with pre-conditions that must be
102 /// satisfied before using the constraints.
103 struct ConstraintListTy {
104   SmallVector<ConstraintTy, 4> Constraints;
105   SmallVector<PreconditionTy, 4> Preconditions;
106 
107   ConstraintListTy() = default;
108 
109   ConstraintListTy(ArrayRef<ConstraintTy> Constraints,
110                    ArrayRef<PreconditionTy> Preconditions)
111       : Constraints(Constraints.begin(), Constraints.end()),
112         Preconditions(Preconditions.begin(), Preconditions.end()) {}
113 
114   void mergeIn(const ConstraintListTy &Other) {
115     append_range(Constraints, Other.Constraints);
116     // TODO: Do smarter merges here, e.g. exclude duplicates.
117     append_range(Preconditions, Other.Preconditions);
118   }
119 
120   unsigned size() const { return Constraints.size(); }
121 
122   unsigned empty() const { return Constraints.empty(); }
123 
124   /// Returns true if any constraint has a non-zero coefficient for any of the
125   /// newly added indices. Zero coefficients for new indices are removed. If it
126   /// returns true, no new variable need to be added to the system.
127   bool needsNewIndices(const DenseMap<Value *, unsigned> &NewIndices) {
128     assert(size() == 1);
129     for (unsigned I = 0; I < NewIndices.size(); ++I) {
130       int64_t Last = get(0).Coefficients.pop_back_val();
131       if (Last != 0)
132         return true;
133     }
134     return false;
135   }
136 
137   ConstraintTy &get(unsigned I) { return Constraints[I]; }
138 
139   /// Returns true if all preconditions for this list of constraints are
140   /// satisfied given \p CS and the corresponding \p Value2Index mapping.
141   bool isValid(const ConstraintInfo &Info) const;
142 
143   /// Returns true if there is exactly one constraint in the list and isValid is
144   /// also true.
145   bool isValidSingle(const ConstraintInfo &Info) const {
146     if (size() != 1)
147       return false;
148     return isValid(Info);
149   }
150 };
151 
152 } // namespace
153 
154 // Decomposes \p V into a vector of pairs of the form { c, X } where c * X. The
155 // sum of the pairs equals \p V.  The first pair is the constant-factor and X
156 // must be nullptr. If the expression cannot be decomposed, returns an empty
157 // vector.
158 static SmallVector<std::pair<int64_t, Value *>, 4>
159 decompose(Value *V, SmallVector<PreconditionTy, 4> &Preconditions,
160           bool IsSigned) {
161 
162   // Decompose \p V used with a signed predicate.
163   if (IsSigned) {
164     if (auto *CI = dyn_cast<ConstantInt>(V)) {
165       const APInt &Val = CI->getValue();
166       if (Val.sle(MinSignedConstraintValue) || Val.sge(MaxConstraintValue))
167         return {};
168       return {{CI->getSExtValue(), nullptr}};
169     }
170 
171     return {{0, nullptr}, {1, V}};
172   }
173 
174   if (auto *CI = dyn_cast<ConstantInt>(V)) {
175     if (CI->isNegative() || CI->uge(MaxConstraintValue))
176       return {};
177     return {{CI->getSExtValue(), nullptr}};
178   }
179   auto *GEP = dyn_cast<GetElementPtrInst>(V);
180   if (GEP && GEP->getNumOperands() == 2 && GEP->isInBounds()) {
181     Value *Op0, *Op1;
182     ConstantInt *CI;
183 
184     // If the index is zero-extended, it is guaranteed to be positive.
185     if (match(GEP->getOperand(GEP->getNumOperands() - 1),
186               m_ZExt(m_Value(Op0)))) {
187       if (match(Op0, m_NUWShl(m_Value(Op1), m_ConstantInt(CI))))
188         return {{0, nullptr},
189                 {1, GEP->getPointerOperand()},
190                 {std::pow(int64_t(2), CI->getSExtValue()), Op1}};
191       if (match(Op0, m_NSWAdd(m_Value(Op1), m_ConstantInt(CI))))
192         return {{CI->getSExtValue(), nullptr},
193                 {1, GEP->getPointerOperand()},
194                 {1, Op1}};
195       return {{0, nullptr}, {1, GEP->getPointerOperand()}, {1, Op0}};
196     }
197 
198     if (match(GEP->getOperand(GEP->getNumOperands() - 1), m_ConstantInt(CI)) &&
199         !CI->isNegative())
200       return {{CI->getSExtValue(), nullptr}, {1, GEP->getPointerOperand()}};
201 
202     SmallVector<std::pair<int64_t, Value *>, 4> Result;
203     if (match(GEP->getOperand(GEP->getNumOperands() - 1),
204               m_NUWShl(m_Value(Op0), m_ConstantInt(CI))))
205       Result = {{0, nullptr},
206                 {1, GEP->getPointerOperand()},
207                 {std::pow(int64_t(2), CI->getSExtValue()), Op0}};
208     else if (match(GEP->getOperand(GEP->getNumOperands() - 1),
209                    m_NSWAdd(m_Value(Op0), m_ConstantInt(CI))))
210       Result = {{CI->getSExtValue(), nullptr},
211                 {1, GEP->getPointerOperand()},
212                 {1, Op0}};
213     else {
214       Op0 = GEP->getOperand(GEP->getNumOperands() - 1);
215       Result = {{0, nullptr}, {1, GEP->getPointerOperand()}, {1, Op0}};
216     }
217     // If Op0 is signed non-negative, the GEP is increasing monotonically and
218     // can be de-composed.
219     Preconditions.emplace_back(CmpInst::ICMP_SGE, Op0,
220                                ConstantInt::get(Op0->getType(), 0));
221     return Result;
222   }
223 
224   Value *Op0;
225   if (match(V, m_ZExt(m_Value(Op0))))
226     V = Op0;
227 
228   Value *Op1;
229   ConstantInt *CI;
230   if (match(V, m_NUWAdd(m_Value(Op0), m_ConstantInt(CI))))
231     return {{CI->getSExtValue(), nullptr}, {1, Op0}};
232   if (match(V, m_NUWAdd(m_Value(Op0), m_Value(Op1))))
233     return {{0, nullptr}, {1, Op0}, {1, Op1}};
234 
235   if (match(V, m_NUWSub(m_Value(Op0), m_ConstantInt(CI))))
236     return {{-1 * CI->getSExtValue(), nullptr}, {1, Op0}};
237   if (match(V, m_NUWSub(m_Value(Op0), m_Value(Op1))))
238     return {{0, nullptr}, {1, Op0}, {-1, Op1}};
239 
240   return {{0, nullptr}, {1, V}};
241 }
242 
243 /// Turn a condition \p CmpI into a vector of constraints, using indices from \p
244 /// Value2Index. Additional indices for newly discovered values are added to \p
245 /// NewIndices.
246 static ConstraintListTy
247 getConstraint(CmpInst::Predicate Pred, Value *Op0, Value *Op1,
248               const DenseMap<Value *, unsigned> &Value2Index,
249               DenseMap<Value *, unsigned> &NewIndices) {
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       auto A =
265           getConstraint(CmpInst::ICMP_UGE, Op0, Op1, Value2Index, NewIndices);
266       auto B =
267           getConstraint(CmpInst::ICMP_ULE, Op0, Op1, Value2Index, NewIndices);
268       A.mergeIn(B);
269       return A;
270     }
271     break;
272   case CmpInst::ICMP_NE:
273     if (!match(Op1, m_Zero()))
274       return {};
275     Pred = CmpInst::getSwappedPredicate(CmpInst::ICMP_UGT);
276     std::swap(Op0, Op1);
277     break;
278   default:
279     break;
280   }
281 
282   // Only ULE and ULT predicates are supported at the moment.
283   if (Pred != CmpInst::ICMP_ULE && Pred != CmpInst::ICMP_ULT &&
284       Pred != CmpInst::ICMP_SLE && Pred != CmpInst::ICMP_SLT)
285     return {};
286 
287   SmallVector<PreconditionTy, 4> Preconditions;
288   bool IsSigned = CmpInst::isSigned(Pred);
289   auto ADec = decompose(Op0->stripPointerCastsSameRepresentation(),
290                         Preconditions, IsSigned);
291   auto BDec = decompose(Op1->stripPointerCastsSameRepresentation(),
292                         Preconditions, IsSigned);
293   // Skip if decomposing either of the values failed.
294   if (ADec.empty() || BDec.empty())
295     return {};
296 
297   // Skip trivial constraints without any variables.
298   if (ADec.size() == 1 && BDec.size() == 1)
299     return {};
300 
301   int64_t Offset1 = ADec[0].first;
302   int64_t Offset2 = BDec[0].first;
303   Offset1 *= -1;
304 
305   // Create iterator ranges that skip the constant-factor.
306   auto VariablesA = llvm::drop_begin(ADec);
307   auto VariablesB = llvm::drop_begin(BDec);
308 
309   // First try to look up \p V in Value2Index and NewIndices. Otherwise add a
310   // new entry to NewIndices.
311   auto GetOrAddIndex = [&Value2Index, &NewIndices](Value *V) -> unsigned {
312     auto V2I = Value2Index.find(V);
313     if (V2I != Value2Index.end())
314       return V2I->second;
315     auto Insert =
316         NewIndices.insert({V, Value2Index.size() + NewIndices.size() + 1});
317     return Insert.first->second;
318   };
319 
320   // Make sure all variables have entries in Value2Index or NewIndices.
321   for (const auto &KV :
322        concat<std::pair<int64_t, Value *>>(VariablesA, VariablesB))
323     GetOrAddIndex(KV.second);
324 
325   // Build result constraint, by first adding all coefficients from A and then
326   // subtracting all coefficients from B.
327   SmallVector<int64_t, 8> R(Value2Index.size() + NewIndices.size() + 1, 0);
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   R[0] = Offset1 + Offset2 +
335          (Pred == (IsSigned ? CmpInst::ICMP_SLT : CmpInst::ICMP_ULT) ? -1 : 0);
336   return {{{R, IsSigned}}, Preconditions};
337 }
338 
339 static ConstraintListTy getConstraint(CmpInst *Cmp, ConstraintInfo &Info,
340                                       DenseMap<Value *, unsigned> &NewIndices) {
341   return getConstraint(
342       Cmp->getPredicate(), Cmp->getOperand(0), Cmp->getOperand(1),
343       Info.getValue2Index(CmpInst::isSigned(Cmp->getPredicate())), NewIndices);
344 }
345 
346 bool ConstraintListTy::isValid(const ConstraintInfo &Info) const {
347   return all_of(Preconditions, [&Info](const PreconditionTy &C) {
348     DenseMap<Value *, unsigned> NewIndices;
349     auto R = getConstraint(C.Pred, C.Op0, C.Op1,
350                            Info.getValue2Index(CmpInst::isSigned(C.Pred)),
351                            NewIndices);
352     // TODO: properly check NewIndices.
353     return NewIndices.empty() && R.Preconditions.empty() && R.size() == 1 &&
354            Info.getCS(CmpInst::isSigned(C.Pred))
355                .isConditionImplied(R.get(0).Coefficients);
356   });
357 }
358 
359 namespace {
360 /// Represents either a condition that holds on entry to a block or a basic
361 /// block, with their respective Dominator DFS in and out numbers.
362 struct ConstraintOrBlock {
363   unsigned NumIn;
364   unsigned NumOut;
365   bool IsBlock;
366   bool Not;
367   union {
368     BasicBlock *BB;
369     CmpInst *Condition;
370   };
371 
372   ConstraintOrBlock(DomTreeNode *DTN)
373       : NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()), IsBlock(true),
374         BB(DTN->getBlock()) {}
375   ConstraintOrBlock(DomTreeNode *DTN, CmpInst *Condition, bool Not)
376       : NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()), IsBlock(false),
377         Not(Not), Condition(Condition) {}
378 };
379 
380 struct StackEntry {
381   unsigned NumIn;
382   unsigned NumOut;
383   Instruction *Condition;
384   bool IsNot;
385   bool IsSigned = false;
386 
387   StackEntry(unsigned NumIn, unsigned NumOut, Instruction *Condition,
388              bool IsNot, bool IsSigned)
389       : NumIn(NumIn), NumOut(NumOut), Condition(Condition), IsNot(IsNot),
390         IsSigned(IsSigned) {}
391 };
392 } // namespace
393 
394 #ifndef NDEBUG
395 static void dumpWithNames(ConstraintTy &C,
396                           DenseMap<Value *, unsigned> &Value2Index) {
397   SmallVector<std::string> Names(Value2Index.size(), "");
398   for (auto &KV : Value2Index) {
399     Names[KV.second - 1] = std::string("%") + KV.first->getName().str();
400   }
401   ConstraintSystem CS;
402   CS.addVariableRowFill(C.Coefficients);
403   CS.dump(Names);
404 }
405 #endif
406 
407 static bool eliminateConstraints(Function &F, DominatorTree &DT) {
408   bool Changed = false;
409   DT.updateDFSNumbers();
410 
411   ConstraintInfo Info;
412 
413   SmallVector<ConstraintOrBlock, 64> WorkList;
414 
415   // First, collect conditions implied by branches and blocks with their
416   // Dominator DFS in and out numbers.
417   for (BasicBlock &BB : F) {
418     if (!DT.getNode(&BB))
419       continue;
420     WorkList.emplace_back(DT.getNode(&BB));
421 
422     // True as long as long as the current instruction is guaranteed to execute.
423     bool GuaranteedToExecute = true;
424     // Scan BB for assume calls.
425     // TODO: also use this scan to queue conditions to simplify, so we can
426     // interleave facts from assumes and conditions to simplify in a single
427     // basic block. And to skip another traversal of each basic block when
428     // simplifying.
429     for (Instruction &I : BB) {
430       Value *Cond;
431       // For now, just handle assumes with a single compare as condition.
432       if (match(&I, m_Intrinsic<Intrinsic::assume>(m_Value(Cond))) &&
433           isa<ICmpInst>(Cond)) {
434         if (GuaranteedToExecute) {
435           // The assume is guaranteed to execute when BB is entered, hence Cond
436           // holds on entry to BB.
437           WorkList.emplace_back(DT.getNode(&BB), cast<ICmpInst>(Cond), false);
438         } else {
439           // Otherwise the condition only holds in the successors.
440           for (BasicBlock *Succ : successors(&BB))
441             WorkList.emplace_back(DT.getNode(Succ), cast<ICmpInst>(Cond),
442                                   false);
443         }
444       }
445       GuaranteedToExecute &= isGuaranteedToTransferExecutionToSuccessor(&I);
446     }
447 
448     auto *Br = dyn_cast<BranchInst>(BB.getTerminator());
449     if (!Br || !Br->isConditional())
450       continue;
451 
452     // Returns true if we can add a known condition from BB to its successor
453     // block Succ. Each predecessor of Succ can either be BB or be dominated by
454     // Succ (e.g. the case when adding a condition from a pre-header to a loop
455     // header).
456     auto CanAdd = [&BB, &DT](BasicBlock *Succ) {
457       assert(isa<BranchInst>(BB.getTerminator()));
458       return any_of(successors(&BB),
459                     [Succ](const BasicBlock *S) { return S != Succ; }) &&
460              all_of(predecessors(Succ), [&BB, &DT, Succ](BasicBlock *Pred) {
461                return Pred == &BB || DT.dominates(Succ, Pred);
462              });
463     };
464     // If the condition is an OR of 2 compares and the false successor only has
465     // the current block as predecessor, queue both negated conditions for the
466     // false successor.
467     Value *Op0, *Op1;
468     if (match(Br->getCondition(), m_LogicalOr(m_Value(Op0), m_Value(Op1))) &&
469         isa<ICmpInst>(Op0) && isa<ICmpInst>(Op1)) {
470       BasicBlock *FalseSuccessor = Br->getSuccessor(1);
471       if (CanAdd(FalseSuccessor)) {
472         WorkList.emplace_back(DT.getNode(FalseSuccessor), cast<ICmpInst>(Op0),
473                               true);
474         WorkList.emplace_back(DT.getNode(FalseSuccessor), cast<ICmpInst>(Op1),
475                               true);
476       }
477       continue;
478     }
479 
480     // If the condition is an AND of 2 compares and the true successor only has
481     // the current block as predecessor, queue both conditions for the true
482     // successor.
483     if (match(Br->getCondition(), m_LogicalAnd(m_Value(Op0), m_Value(Op1))) &&
484         isa<ICmpInst>(Op0) && isa<ICmpInst>(Op1)) {
485       BasicBlock *TrueSuccessor = Br->getSuccessor(0);
486       if (CanAdd(TrueSuccessor)) {
487         WorkList.emplace_back(DT.getNode(TrueSuccessor), cast<ICmpInst>(Op0),
488                               false);
489         WorkList.emplace_back(DT.getNode(TrueSuccessor), cast<ICmpInst>(Op1),
490                               false);
491       }
492       continue;
493     }
494 
495     auto *CmpI = dyn_cast<ICmpInst>(Br->getCondition());
496     if (!CmpI)
497       continue;
498     if (CanAdd(Br->getSuccessor(0)))
499       WorkList.emplace_back(DT.getNode(Br->getSuccessor(0)), CmpI, false);
500     if (CanAdd(Br->getSuccessor(1)))
501       WorkList.emplace_back(DT.getNode(Br->getSuccessor(1)), CmpI, true);
502   }
503 
504   // Next, sort worklist by dominance, so that dominating blocks and conditions
505   // come before blocks and conditions dominated by them. If a block and a
506   // condition have the same numbers, the condition comes before the block, as
507   // it holds on entry to the block.
508   sort(WorkList, [](const ConstraintOrBlock &A, const ConstraintOrBlock &B) {
509     return std::tie(A.NumIn, A.IsBlock) < std::tie(B.NumIn, B.IsBlock);
510   });
511 
512   // Finally, process ordered worklist and eliminate implied conditions.
513   SmallVector<StackEntry, 16> DFSInStack;
514   for (ConstraintOrBlock &CB : WorkList) {
515     // First, pop entries from the stack that are out-of-scope for CB. Remove
516     // the corresponding entry from the constraint system.
517     while (!DFSInStack.empty()) {
518       auto &E = DFSInStack.back();
519       LLVM_DEBUG(dbgs() << "Top of stack : " << E.NumIn << " " << E.NumOut
520                         << "\n");
521       LLVM_DEBUG(dbgs() << "CB: " << CB.NumIn << " " << CB.NumOut << "\n");
522       assert(E.NumIn <= CB.NumIn);
523       if (CB.NumOut <= E.NumOut)
524         break;
525       LLVM_DEBUG(dbgs() << "Removing " << *E.Condition << " " << E.IsNot
526                         << "\n");
527       DFSInStack.pop_back();
528       Info.popLastConstraint(E.IsSigned);
529     }
530 
531     LLVM_DEBUG({
532       dbgs() << "Processing ";
533       if (CB.IsBlock)
534         dbgs() << *CB.BB;
535       else
536         dbgs() << *CB.Condition;
537       dbgs() << "\n";
538     });
539 
540     // For a block, check if any CmpInsts become known based on the current set
541     // of constraints.
542     if (CB.IsBlock) {
543       for (Instruction &I : *CB.BB) {
544         auto *Cmp = dyn_cast<ICmpInst>(&I);
545         if (!Cmp)
546           continue;
547 
548         DenseMap<Value *, unsigned> NewIndices;
549         auto R = getConstraint(Cmp, Info, NewIndices);
550         if (!R.isValidSingle(Info) || R.needsNewIndices(NewIndices))
551           continue;
552 
553         auto &CSToUse = Info.getCS(R.get(0).IsSigned);
554         if (CSToUse.isConditionImplied(R.get(0).Coefficients)) {
555           if (!DebugCounter::shouldExecute(EliminatedCounter))
556             continue;
557 
558           LLVM_DEBUG(dbgs() << "Condition " << *Cmp
559                             << " implied by dominating constraints\n");
560           LLVM_DEBUG({
561             for (auto &E : reverse(DFSInStack))
562               dbgs() << "   C " << *E.Condition << " " << E.IsNot << "\n";
563           });
564           Cmp->replaceUsesWithIf(
565               ConstantInt::getTrue(F.getParent()->getContext()), [](Use &U) {
566                 // Conditions in an assume trivially simplify to true. Skip uses
567                 // in assume calls to not destroy the available information.
568                 auto *II = dyn_cast<IntrinsicInst>(U.getUser());
569                 return !II || II->getIntrinsicID() != Intrinsic::assume;
570               });
571           NumCondsRemoved++;
572           Changed = true;
573         }
574         if (CSToUse.isConditionImplied(
575                 ConstraintSystem::negate(R.get(0).Coefficients))) {
576           if (!DebugCounter::shouldExecute(EliminatedCounter))
577             continue;
578 
579           LLVM_DEBUG(dbgs() << "Condition !" << *Cmp
580                             << " implied by dominating constraints\n");
581           LLVM_DEBUG({
582             for (auto &E : reverse(DFSInStack))
583               dbgs() << "   C " << *E.Condition << " " << E.IsNot << "\n";
584           });
585           Cmp->replaceAllUsesWith(
586               ConstantInt::getFalse(F.getParent()->getContext()));
587           NumCondsRemoved++;
588           Changed = true;
589         }
590       }
591       continue;
592     }
593 
594     // Set up a function to restore the predicate at the end of the scope if it
595     // has been negated. Negate the predicate in-place, if required.
596     auto *CI = dyn_cast<ICmpInst>(CB.Condition);
597     auto PredicateRestorer = make_scope_exit([CI, &CB]() {
598       if (CB.Not && CI)
599         CI->setPredicate(CI->getInversePredicate());
600     });
601     if (CB.Not) {
602       if (CI) {
603         CI->setPredicate(CI->getInversePredicate());
604       } else {
605         LLVM_DEBUG(dbgs() << "Can only negate compares so far.\n");
606         continue;
607       }
608     }
609 
610     // Otherwise, add the condition to the system and stack, if we can transform
611     // it into a constraint.
612     DenseMap<Value *, unsigned> NewIndices;
613     auto R = getConstraint(CB.Condition, Info, NewIndices);
614     if (!R.isValid(Info))
615       continue;
616 
617     for (auto &KV : NewIndices)
618       Info.getValue2Index(CmpInst::isSigned(CB.Condition->getPredicate()))
619           .insert(KV);
620 
621     LLVM_DEBUG(dbgs() << "Adding " << *CB.Condition << " " << CB.Not << "\n");
622     bool Added = false;
623     for (auto &E : R.Constraints) {
624       auto &CSToUse = Info.getCS(E.IsSigned);
625       if (E.Coefficients.empty())
626         continue;
627 
628       LLVM_DEBUG({
629         dbgs() << "  constraint: ";
630         dumpWithNames(E, Info.getValue2Index(E.IsSigned));
631       });
632 
633       Added |= CSToUse.addVariableRowFill(E.Coefficients);
634 
635       // If R has been added to the system, queue it for removal once it goes
636       // out-of-scope.
637       if (Added)
638         DFSInStack.emplace_back(CB.NumIn, CB.NumOut, CB.Condition, CB.Not,
639                                 E.IsSigned);
640     }
641   }
642 
643 #ifndef NDEBUG
644   unsigned SignedEntries =
645       count_if(DFSInStack, [](const StackEntry &E) { return E.IsSigned; });
646   assert(Info.getCS(false).size() == DFSInStack.size() - SignedEntries &&
647          "updates to CS and DFSInStack are out of sync");
648   assert(Info.getCS(true).size() == SignedEntries &&
649          "updates to CS and DFSInStack are out of sync");
650 #endif
651 
652   return Changed;
653 }
654 
655 PreservedAnalyses ConstraintEliminationPass::run(Function &F,
656                                                  FunctionAnalysisManager &AM) {
657   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
658   if (!eliminateConstraints(F, DT))
659     return PreservedAnalyses::all();
660 
661   PreservedAnalyses PA;
662   PA.preserve<DominatorTreeAnalysis>();
663   PA.preserveSet<CFGAnalyses>();
664   return PA;
665 }
666 
667 namespace {
668 
669 class ConstraintElimination : public FunctionPass {
670 public:
671   static char ID;
672 
673   ConstraintElimination() : FunctionPass(ID) {
674     initializeConstraintEliminationPass(*PassRegistry::getPassRegistry());
675   }
676 
677   bool runOnFunction(Function &F) override {
678     auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
679     return eliminateConstraints(F, DT);
680   }
681 
682   void getAnalysisUsage(AnalysisUsage &AU) const override {
683     AU.setPreservesCFG();
684     AU.addRequired<DominatorTreeWrapperPass>();
685     AU.addPreserved<GlobalsAAWrapperPass>();
686     AU.addPreserved<DominatorTreeWrapperPass>();
687   }
688 };
689 
690 } // end anonymous namespace
691 
692 char ConstraintElimination::ID = 0;
693 
694 INITIALIZE_PASS_BEGIN(ConstraintElimination, "constraint-elimination",
695                       "Constraint Elimination", false, false)
696 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
697 INITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass)
698 INITIALIZE_PASS_END(ConstraintElimination, "constraint-elimination",
699                     "Constraint Elimination", false, false)
700 
701 FunctionPass *llvm::createConstraintEliminationPass() {
702   return new ConstraintElimination();
703 }
704