xref: /llvm-project/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp (revision e82b5b5bbd1a97c289988a9bf2007511d35eb5cf)
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/GetElementPtrTypeIterator.h"
26 #include "llvm/IR/IRBuilder.h"
27 #include "llvm/IR/Instructions.h"
28 #include "llvm/IR/PatternMatch.h"
29 #include "llvm/InitializePasses.h"
30 #include "llvm/Pass.h"
31 #include "llvm/Support/Debug.h"
32 #include "llvm/Support/DebugCounter.h"
33 #include "llvm/Support/MathExtras.h"
34 #include "llvm/Transforms/Scalar.h"
35 
36 #include <cmath>
37 #include <string>
38 
39 using namespace llvm;
40 using namespace PatternMatch;
41 
42 #define DEBUG_TYPE "constraint-elimination"
43 
44 STATISTIC(NumCondsRemoved, "Number of instructions removed");
45 DEBUG_COUNTER(EliminatedCounter, "conds-eliminated",
46               "Controls which conditions are eliminated");
47 
48 static int64_t MaxConstraintValue = std::numeric_limits<int64_t>::max();
49 static int64_t MinSignedConstraintValue = std::numeric_limits<int64_t>::min();
50 
51 // A helper to multiply 2 signed integers where overflowing is allowed.
52 static int64_t multiplyWithOverflow(int64_t A, int64_t B) {
53   int64_t Result;
54   MulOverflow(A, B, Result);
55   return Result;
56 }
57 
58 // A helper to add 2 signed integers where overflowing is allowed.
59 static int64_t addWithOverflow(int64_t A, int64_t B) {
60   int64_t Result;
61   AddOverflow(A, B, Result);
62   return Result;
63 }
64 
65 namespace {
66 
67 class ConstraintInfo;
68 
69 struct StackEntry {
70   unsigned NumIn;
71   unsigned NumOut;
72   bool IsSigned = false;
73   /// Variables that can be removed from the system once the stack entry gets
74   /// removed.
75   SmallVector<Value *, 2> ValuesToRelease;
76 
77   StackEntry(unsigned NumIn, unsigned NumOut, bool IsSigned,
78              SmallVector<Value *, 2> ValuesToRelease)
79       : NumIn(NumIn), NumOut(NumOut), IsSigned(IsSigned),
80         ValuesToRelease(ValuesToRelease) {}
81 };
82 
83 /// Struct to express a pre-condition of the form %Op0 Pred %Op1.
84 struct PreconditionTy {
85   CmpInst::Predicate Pred;
86   Value *Op0;
87   Value *Op1;
88 
89   PreconditionTy(CmpInst::Predicate Pred, Value *Op0, Value *Op1)
90       : Pred(Pred), Op0(Op0), Op1(Op1) {}
91 };
92 
93 struct ConstraintTy {
94   SmallVector<int64_t, 8> Coefficients;
95   SmallVector<PreconditionTy, 2> Preconditions;
96 
97   SmallVector<SmallVector<int64_t, 8>> ExtraInfo;
98 
99   bool IsSigned = false;
100   bool IsEq = false;
101 
102   ConstraintTy() = default;
103 
104   ConstraintTy(SmallVector<int64_t, 8> Coefficients, bool IsSigned)
105       : Coefficients(Coefficients), IsSigned(IsSigned) {}
106 
107   unsigned size() const { return Coefficients.size(); }
108 
109   unsigned empty() const { return Coefficients.empty(); }
110 
111   /// Returns true if all preconditions for this list of constraints are
112   /// satisfied given \p CS and the corresponding \p Value2Index mapping.
113   bool isValid(const ConstraintInfo &Info) const;
114 };
115 
116 /// Wrapper encapsulating separate constraint systems and corresponding value
117 /// mappings for both unsigned and signed information. Facts are added to and
118 /// conditions are checked against the corresponding system depending on the
119 /// signed-ness of their predicates. While the information is kept separate
120 /// based on signed-ness, certain conditions can be transferred between the two
121 /// systems.
122 class ConstraintInfo {
123   DenseMap<Value *, unsigned> UnsignedValue2Index;
124   DenseMap<Value *, unsigned> SignedValue2Index;
125 
126   ConstraintSystem UnsignedCS;
127   ConstraintSystem SignedCS;
128 
129   const DataLayout &DL;
130 
131 public:
132   ConstraintInfo(const DataLayout &DL) : DL(DL) {}
133 
134   DenseMap<Value *, unsigned> &getValue2Index(bool Signed) {
135     return Signed ? SignedValue2Index : UnsignedValue2Index;
136   }
137   const DenseMap<Value *, unsigned> &getValue2Index(bool Signed) const {
138     return Signed ? SignedValue2Index : UnsignedValue2Index;
139   }
140 
141   ConstraintSystem &getCS(bool Signed) {
142     return Signed ? SignedCS : UnsignedCS;
143   }
144   const ConstraintSystem &getCS(bool Signed) const {
145     return Signed ? SignedCS : UnsignedCS;
146   }
147 
148   void popLastConstraint(bool Signed) { getCS(Signed).popLastConstraint(); }
149   void popLastNVariables(bool Signed, unsigned N) {
150     getCS(Signed).popLastNVariables(N);
151   }
152 
153   bool doesHold(CmpInst::Predicate Pred, Value *A, Value *B) const;
154 
155   void addFact(CmpInst::Predicate Pred, Value *A, Value *B, unsigned NumIn,
156                unsigned NumOut, SmallVectorImpl<StackEntry> &DFSInStack);
157 
158   /// Turn a comparison of the form \p Op0 \p Pred \p Op1 into a vector of
159   /// constraints, using indices from the corresponding constraint system.
160   /// New variables that need to be added to the system are collected in
161   /// \p NewVariables.
162   ConstraintTy getConstraint(CmpInst::Predicate Pred, Value *Op0, Value *Op1,
163                              SmallVectorImpl<Value *> &NewVariables) const;
164 
165   /// Turns a comparison of the form \p Op0 \p Pred \p Op1 into a vector of
166   /// constraints using getConstraint. Returns an empty constraint if the result
167   /// cannot be used to query the existing constraint system, e.g. because it
168   /// would require adding new variables. Also tries to convert signed
169   /// predicates to unsigned ones if possible to allow using the unsigned system
170   /// which increases the effectiveness of the signed <-> unsigned transfer
171   /// logic.
172   ConstraintTy getConstraintForSolving(CmpInst::Predicate Pred, Value *Op0,
173                                        Value *Op1) const;
174 
175   /// Try to add information from \p A \p Pred \p B to the unsigned/signed
176   /// system if \p Pred is signed/unsigned.
177   void transferToOtherSystem(CmpInst::Predicate Pred, Value *A, Value *B,
178                              unsigned NumIn, unsigned NumOut,
179                              SmallVectorImpl<StackEntry> &DFSInStack);
180 };
181 
182 /// Represents a (Coefficient * Variable) entry after IR decomposition.
183 struct DecompEntry {
184   int64_t Coefficient;
185   Value *Variable;
186   /// True if the variable is known positive in the current constraint.
187   bool IsKnownPositive;
188 
189   DecompEntry(int64_t Coefficient, Value *Variable,
190               bool IsKnownPositive = false)
191       : Coefficient(Coefficient), Variable(Variable),
192         IsKnownPositive(IsKnownPositive) {}
193 };
194 
195 /// Represents an Offset + Coefficient1 * Variable1 + ... decomposition.
196 struct Decomposition {
197   int64_t Offset = 0;
198   SmallVector<DecompEntry, 3> Vars;
199 
200   Decomposition(int64_t Offset) : Offset(Offset) {}
201   Decomposition(Value *V, bool IsKnownPositive = false) {
202     Vars.emplace_back(1, V, IsKnownPositive);
203   }
204   Decomposition(int64_t Offset, ArrayRef<DecompEntry> Vars)
205       : Offset(Offset), Vars(Vars) {}
206 
207   void add(int64_t OtherOffset) {
208     Offset = addWithOverflow(Offset, OtherOffset);
209   }
210 
211   void add(const Decomposition &Other) {
212     add(Other.Offset);
213     append_range(Vars, Other.Vars);
214   }
215 
216   void mul(int64_t Factor) {
217     Offset = multiplyWithOverflow(Offset, Factor);
218     for (auto &Var : Vars)
219       Var.Coefficient = multiplyWithOverflow(Var.Coefficient, Factor);
220   }
221 };
222 
223 } // namespace
224 
225 static Decomposition decompose(Value *V,
226                                SmallVector<PreconditionTy, 4> &Preconditions,
227                                bool IsSigned, const DataLayout &DL);
228 
229 static bool canUseSExt(ConstantInt *CI) {
230   const APInt &Val = CI->getValue();
231   return Val.sgt(MinSignedConstraintValue) && Val.slt(MaxConstraintValue);
232 }
233 
234 static Decomposition decomposeGEP(GetElementPtrInst &GEP,
235                                   SmallVector<PreconditionTy, 4> &Preconditions,
236                                   bool IsSigned, const DataLayout &DL) {
237   // Do not reason about pointers where the index size is larger than 64 bits,
238   // as the coefficients used to encode constraints are 64 bit integers.
239   if (DL.getIndexTypeSizeInBits(GEP.getPointerOperand()->getType()) > 64)
240     return &GEP;
241 
242   if (!GEP.isInBounds())
243     return &GEP;
244 
245   // Handle the (gep (gep ....), C) case by incrementing the constant
246   // coefficient of the inner GEP, if C is a constant.
247   auto *InnerGEP = dyn_cast<GetElementPtrInst>(GEP.getPointerOperand());
248   if (InnerGEP && GEP.getNumOperands() == 2 &&
249       isa<ConstantInt>(GEP.getOperand(1))) {
250     APInt Offset = cast<ConstantInt>(GEP.getOperand(1))->getValue();
251     auto Result = decompose(InnerGEP, Preconditions, IsSigned, DL);
252 
253     auto GTI = gep_type_begin(GEP);
254     // Bail out for scalable vectors for now.
255     if (isa<ScalableVectorType>(GTI.getIndexedType()))
256       return &GEP;
257     int64_t Scale = static_cast<int64_t>(
258         DL.getTypeAllocSize(GTI.getIndexedType()).getFixedSize());
259 
260     Result.add(multiplyWithOverflow(Scale, Offset.getSExtValue()));
261     if (Offset.isNegative()) {
262       // Add pre-condition ensuring the GEP is increasing monotonically and
263       // can be de-composed.
264       Preconditions.emplace_back(
265           CmpInst::ICMP_SGE, InnerGEP->getOperand(1),
266           ConstantInt::get(InnerGEP->getOperand(1)->getType(),
267                            -1 * Offset.getSExtValue()));
268     }
269     return Result;
270   }
271 
272   Decomposition Result = GEP.getPointerOperand();
273   gep_type_iterator GTI = gep_type_begin(GEP);
274   for (User::const_op_iterator I = GEP.op_begin() + 1, E = GEP.op_end(); I != E;
275        ++I, ++GTI) {
276     Value *Index = *I;
277 
278     // Bail out for scalable vectors for now.
279     if (isa<ScalableVectorType>(GTI.getIndexedType()))
280       return &GEP;
281 
282     // Struct indices must be constants (and reference an existing field). Add
283     // them to the constant factor.
284     if (StructType *STy = GTI.getStructTypeOrNull()) {
285       // For a struct, add the member offset.
286       unsigned FieldNo = cast<ConstantInt>(Index)->getZExtValue();
287       if (FieldNo == 0)
288         continue;
289 
290       // Add offset to constant factor.
291       Result.add(int64_t(DL.getStructLayout(STy)->getElementOffset(FieldNo)));
292       continue;
293     }
294 
295     // For an array/pointer, add the element offset, explicitly scaled.
296     unsigned Scale = DL.getTypeAllocSize(GTI.getIndexedType()).getFixedSize();
297 
298     auto IdxResult = decompose(Index, Preconditions, IsSigned, DL);
299     IdxResult.mul(Scale);
300     Result.add(IdxResult);
301 
302     // If Op0 is signed non-negative, the GEP is increasing monotonically and
303     // can be de-composed.
304     if (!isKnownNonNegative(Index, DL, /*Depth=*/MaxAnalysisRecursionDepth - 1))
305       Preconditions.emplace_back(CmpInst::ICMP_SGE, Index,
306                                  ConstantInt::get(Index->getType(), 0));
307   }
308   return Result;
309 }
310 
311 // Decomposes \p V into a vector of entries of the form { Coefficient, Variable
312 // } where Coefficient * Variable. The sum of the pairs equals \p V.  The first
313 // pair is the constant-factor and X must be nullptr. If the expression cannot
314 // be decomposed, returns an empty vector.
315 static Decomposition decompose(Value *V,
316                                SmallVector<PreconditionTy, 4> &Preconditions,
317                                bool IsSigned, const DataLayout &DL) {
318 
319   auto MergeResults = [&Preconditions, IsSigned, &DL](Value *A, Value *B,
320                                                       bool IsSignedB) {
321     auto ResA = decompose(A, Preconditions, IsSigned, DL);
322     auto ResB = decompose(B, Preconditions, IsSignedB, DL);
323     ResA.add(ResB);
324     return ResA;
325   };
326 
327   // Decompose \p V used with a signed predicate.
328   if (IsSigned) {
329     if (auto *CI = dyn_cast<ConstantInt>(V)) {
330       if (canUseSExt(CI))
331         return CI->getSExtValue();
332     }
333     Value *Op0;
334     Value *Op1;
335     if (match(V, m_NSWAdd(m_Value(Op0), m_Value(Op1))))
336       return MergeResults(Op0, Op1, IsSigned);
337 
338     return V;
339   }
340 
341   if (auto *CI = dyn_cast<ConstantInt>(V)) {
342     if (CI->uge(MaxConstraintValue))
343       return V;
344     return int64_t(CI->getZExtValue());
345   }
346 
347   if (auto *GEP = dyn_cast<GetElementPtrInst>(V))
348     return decomposeGEP(*GEP, Preconditions, IsSigned, DL);
349 
350   Value *Op0;
351   bool IsKnownPositive = false;
352   if (match(V, m_ZExt(m_Value(Op0)))) {
353     IsKnownPositive = true;
354     V = Op0;
355   }
356 
357   Value *Op1;
358   ConstantInt *CI;
359   if (match(V, m_NUWAdd(m_Value(Op0), m_Value(Op1)))) {
360     return MergeResults(Op0, Op1, IsSigned);
361   }
362   if (match(V, m_NSWAdd(m_Value(Op0), m_Value(Op1)))) {
363     if (!isKnownNonNegative(Op0, DL, /*Depth=*/MaxAnalysisRecursionDepth - 1))
364       Preconditions.emplace_back(CmpInst::ICMP_SGE, Op0,
365                                  ConstantInt::get(Op0->getType(), 0));
366     if (!isKnownNonNegative(Op1, DL, /*Depth=*/MaxAnalysisRecursionDepth - 1))
367       Preconditions.emplace_back(CmpInst::ICMP_SGE, Op1,
368                                  ConstantInt::get(Op1->getType(), 0));
369 
370     return MergeResults(Op0, Op1, IsSigned);
371   }
372 
373   if (match(V, m_Add(m_Value(Op0), m_ConstantInt(CI))) && CI->isNegative() &&
374       canUseSExt(CI)) {
375     Preconditions.emplace_back(
376         CmpInst::ICMP_UGE, Op0,
377         ConstantInt::get(Op0->getType(), CI->getSExtValue() * -1));
378     return MergeResults(Op0, CI, true);
379   }
380 
381   if (match(V, m_NUWShl(m_Value(Op1), m_ConstantInt(CI))) && canUseSExt(CI)) {
382     int64_t Mult = int64_t(std::pow(int64_t(2), CI->getSExtValue()));
383     auto Result = decompose(Op1, Preconditions, IsSigned, DL);
384     Result.mul(Mult);
385     return Result;
386   }
387 
388   if (match(V, m_NUWMul(m_Value(Op1), m_ConstantInt(CI))) && canUseSExt(CI) &&
389       (!CI->isNegative())) {
390     auto Result = decompose(Op1, Preconditions, IsSigned, DL);
391     Result.mul(CI->getSExtValue());
392     return Result;
393   }
394 
395   if (match(V, m_NUWSub(m_Value(Op0), m_ConstantInt(CI))) && canUseSExt(CI))
396     return {-1 * CI->getSExtValue(), {{1, Op0}}};
397   if (match(V, m_NUWSub(m_Value(Op0), m_Value(Op1))))
398     return {0, {{1, Op0}, {-1, Op1}}};
399 
400   return {V, IsKnownPositive};
401 }
402 
403 ConstraintTy
404 ConstraintInfo::getConstraint(CmpInst::Predicate Pred, Value *Op0, Value *Op1,
405                               SmallVectorImpl<Value *> &NewVariables) const {
406   assert(NewVariables.empty() && "NewVariables must be empty when passed in");
407   bool IsEq = false;
408   // Try to convert Pred to one of ULE/SLT/SLE/SLT.
409   switch (Pred) {
410   case CmpInst::ICMP_UGT:
411   case CmpInst::ICMP_UGE:
412   case CmpInst::ICMP_SGT:
413   case CmpInst::ICMP_SGE: {
414     Pred = CmpInst::getSwappedPredicate(Pred);
415     std::swap(Op0, Op1);
416     break;
417   }
418   case CmpInst::ICMP_EQ:
419     if (match(Op1, m_Zero())) {
420       Pred = CmpInst::ICMP_ULE;
421     } else {
422       IsEq = true;
423       Pred = CmpInst::ICMP_ULE;
424     }
425     break;
426   case CmpInst::ICMP_NE:
427     if (!match(Op1, m_Zero()))
428       return {};
429     Pred = CmpInst::getSwappedPredicate(CmpInst::ICMP_UGT);
430     std::swap(Op0, Op1);
431     break;
432   default:
433     break;
434   }
435 
436   // Only ULE and ULT predicates are supported at the moment.
437   if (Pred != CmpInst::ICMP_ULE && Pred != CmpInst::ICMP_ULT &&
438       Pred != CmpInst::ICMP_SLE && Pred != CmpInst::ICMP_SLT)
439     return {};
440 
441   SmallVector<PreconditionTy, 4> Preconditions;
442   bool IsSigned = CmpInst::isSigned(Pred);
443   auto &Value2Index = getValue2Index(IsSigned);
444   auto ADec = decompose(Op0->stripPointerCastsSameRepresentation(),
445                         Preconditions, IsSigned, DL);
446   auto BDec = decompose(Op1->stripPointerCastsSameRepresentation(),
447                         Preconditions, IsSigned, DL);
448   int64_t Offset1 = ADec.Offset;
449   int64_t Offset2 = BDec.Offset;
450   Offset1 *= -1;
451 
452   auto &VariablesA = ADec.Vars;
453   auto &VariablesB = BDec.Vars;
454 
455   // First try to look up \p V in Value2Index and NewVariables. Otherwise add a
456   // new entry to NewVariables.
457   DenseMap<Value *, unsigned> NewIndexMap;
458   auto GetOrAddIndex = [&Value2Index, &NewVariables,
459                         &NewIndexMap](Value *V) -> unsigned {
460     auto V2I = Value2Index.find(V);
461     if (V2I != Value2Index.end())
462       return V2I->second;
463     auto Insert =
464         NewIndexMap.insert({V, Value2Index.size() + NewVariables.size() + 1});
465     if (Insert.second)
466       NewVariables.push_back(V);
467     return Insert.first->second;
468   };
469 
470   // Make sure all variables have entries in Value2Index or NewVariables.
471   for (const auto &KV : concat<DecompEntry>(VariablesA, VariablesB))
472     GetOrAddIndex(KV.Variable);
473 
474   // Build result constraint, by first adding all coefficients from A and then
475   // subtracting all coefficients from B.
476   ConstraintTy Res(
477       SmallVector<int64_t, 8>(Value2Index.size() + NewVariables.size() + 1, 0),
478       IsSigned);
479   // Collect variables that are known to be positive in all uses in the
480   // constraint.
481   DenseMap<Value *, bool> KnownPositiveVariables;
482   Res.IsEq = IsEq;
483   auto &R = Res.Coefficients;
484   for (const auto &KV : VariablesA) {
485     R[GetOrAddIndex(KV.Variable)] += KV.Coefficient;
486     auto I = KnownPositiveVariables.insert({KV.Variable, KV.IsKnownPositive});
487     I.first->second &= KV.IsKnownPositive;
488   }
489 
490   for (const auto &KV : VariablesB) {
491     R[GetOrAddIndex(KV.Variable)] -= KV.Coefficient;
492     auto I = KnownPositiveVariables.insert({KV.Variable, KV.IsKnownPositive});
493     I.first->second &= KV.IsKnownPositive;
494   }
495 
496   int64_t OffsetSum;
497   if (AddOverflow(Offset1, Offset2, OffsetSum))
498     return {};
499   if (Pred == (IsSigned ? CmpInst::ICMP_SLT : CmpInst::ICMP_ULT))
500     if (AddOverflow(OffsetSum, int64_t(-1), OffsetSum))
501       return {};
502   R[0] = OffsetSum;
503   Res.Preconditions = std::move(Preconditions);
504 
505   // Remove any (Coefficient, Variable) entry where the Coefficient is 0 for new
506   // variables.
507   while (!NewVariables.empty()) {
508     int64_t Last = R.back();
509     if (Last != 0)
510       break;
511     R.pop_back();
512     Value *RemovedV = NewVariables.pop_back_val();
513     NewIndexMap.erase(RemovedV);
514   }
515 
516   // Add extra constraints for variables that are known positive.
517   for (auto &KV : KnownPositiveVariables) {
518     if (!KV.second || (Value2Index.find(KV.first) == Value2Index.end() &&
519                        NewIndexMap.find(KV.first) == NewIndexMap.end()))
520       continue;
521     SmallVector<int64_t, 8> C(Value2Index.size() + NewVariables.size() + 1, 0);
522     C[GetOrAddIndex(KV.first)] = -1;
523     Res.ExtraInfo.push_back(C);
524   }
525   return Res;
526 }
527 
528 ConstraintTy ConstraintInfo::getConstraintForSolving(CmpInst::Predicate Pred,
529                                                      Value *Op0,
530                                                      Value *Op1) const {
531   // If both operands are known to be non-negative, change signed predicates to
532   // unsigned ones. This increases the reasoning effectiveness in combination
533   // with the signed <-> unsigned transfer logic.
534   if (CmpInst::isSigned(Pred) &&
535       isKnownNonNegative(Op0, DL, /*Depth=*/MaxAnalysisRecursionDepth - 1) &&
536       isKnownNonNegative(Op1, DL, /*Depth=*/MaxAnalysisRecursionDepth - 1))
537     Pred = CmpInst::getUnsignedPredicate(Pred);
538 
539   SmallVector<Value *> NewVariables;
540   ConstraintTy R = getConstraint(Pred, Op0, Op1, NewVariables);
541   if (R.IsEq || !NewVariables.empty())
542     return {};
543   return R;
544 }
545 
546 bool ConstraintTy::isValid(const ConstraintInfo &Info) const {
547   return Coefficients.size() > 0 &&
548          all_of(Preconditions, [&Info](const PreconditionTy &C) {
549            return Info.doesHold(C.Pred, C.Op0, C.Op1);
550          });
551 }
552 
553 bool ConstraintInfo::doesHold(CmpInst::Predicate Pred, Value *A,
554                               Value *B) const {
555   auto R = getConstraintForSolving(Pred, A, B);
556   return R.Preconditions.empty() && !R.empty() &&
557          getCS(R.IsSigned).isConditionImplied(R.Coefficients);
558 }
559 
560 void ConstraintInfo::transferToOtherSystem(
561     CmpInst::Predicate Pred, Value *A, Value *B, unsigned NumIn,
562     unsigned NumOut, SmallVectorImpl<StackEntry> &DFSInStack) {
563   // Check if we can combine facts from the signed and unsigned systems to
564   // derive additional facts.
565   if (!A->getType()->isIntegerTy())
566     return;
567   // FIXME: This currently depends on the order we add facts. Ideally we
568   // would first add all known facts and only then try to add additional
569   // facts.
570   switch (Pred) {
571   default:
572     break;
573   case CmpInst::ICMP_ULT:
574     //  If B is a signed positive constant, A >=s 0 and A <s B.
575     if (doesHold(CmpInst::ICMP_SGE, B, ConstantInt::get(B->getType(), 0))) {
576       addFact(CmpInst::ICMP_SGE, A, ConstantInt::get(B->getType(), 0), NumIn,
577               NumOut, DFSInStack);
578       addFact(CmpInst::ICMP_SLT, A, B, NumIn, NumOut, DFSInStack);
579     }
580     break;
581   case CmpInst::ICMP_SLT:
582     if (doesHold(CmpInst::ICMP_SGE, A, ConstantInt::get(B->getType(), 0)))
583       addFact(CmpInst::ICMP_ULT, A, B, NumIn, NumOut, DFSInStack);
584     break;
585   case CmpInst::ICMP_SGT:
586     if (doesHold(CmpInst::ICMP_SGE, B, ConstantInt::get(B->getType(), -1)))
587       addFact(CmpInst::ICMP_UGE, A, ConstantInt::get(B->getType(), 0), NumIn,
588               NumOut, DFSInStack);
589     break;
590   case CmpInst::ICMP_SGE:
591     if (doesHold(CmpInst::ICMP_SGE, B, ConstantInt::get(B->getType(), 0))) {
592       addFact(CmpInst::ICMP_UGE, A, B, NumIn, NumOut, DFSInStack);
593     }
594     break;
595   }
596 }
597 
598 namespace {
599 /// Represents either a condition that holds on entry to a block or a basic
600 /// block, with their respective Dominator DFS in and out numbers.
601 struct ConstraintOrBlock {
602   unsigned NumIn;
603   unsigned NumOut;
604   bool IsBlock;
605   bool Not;
606   union {
607     BasicBlock *BB;
608     CmpInst *Condition;
609   };
610 
611   ConstraintOrBlock(DomTreeNode *DTN)
612       : NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()), IsBlock(true),
613         BB(DTN->getBlock()) {}
614   ConstraintOrBlock(DomTreeNode *DTN, CmpInst *Condition, bool Not)
615       : NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()), IsBlock(false),
616         Not(Not), Condition(Condition) {}
617 };
618 
619 /// Keep state required to build worklist.
620 struct State {
621   DominatorTree &DT;
622   SmallVector<ConstraintOrBlock, 64> WorkList;
623 
624   State(DominatorTree &DT) : DT(DT) {}
625 
626   /// Process block \p BB and add known facts to work-list.
627   void addInfoFor(BasicBlock &BB);
628 
629   /// Returns true if we can add a known condition from BB to its successor
630   /// block Succ. Each predecessor of Succ can either be BB or be dominated
631   /// by Succ (e.g. the case when adding a condition from a pre-header to a
632   /// loop header).
633   bool canAddSuccessor(BasicBlock &BB, BasicBlock *Succ) const {
634     if (BB.getSingleSuccessor()) {
635       assert(BB.getSingleSuccessor() == Succ);
636       return DT.properlyDominates(&BB, Succ);
637     }
638     return any_of(successors(&BB),
639                   [Succ](const BasicBlock *S) { return S != Succ; }) &&
640            all_of(predecessors(Succ), [&BB, Succ, this](BasicBlock *Pred) {
641              return Pred == &BB || DT.dominates(Succ, Pred);
642            });
643   }
644 };
645 
646 } // namespace
647 
648 #ifndef NDEBUG
649 static void dumpWithNames(const ConstraintSystem &CS,
650                           DenseMap<Value *, unsigned> &Value2Index) {
651   SmallVector<std::string> Names(Value2Index.size(), "");
652   for (auto &KV : Value2Index) {
653     Names[KV.second - 1] = std::string("%") + KV.first->getName().str();
654   }
655   CS.dump(Names);
656 }
657 
658 static void dumpWithNames(ArrayRef<int64_t> C,
659                           DenseMap<Value *, unsigned> &Value2Index) {
660   ConstraintSystem CS;
661   CS.addVariableRowFill(C);
662   dumpWithNames(CS, Value2Index);
663 }
664 #endif
665 
666 void State::addInfoFor(BasicBlock &BB) {
667   WorkList.emplace_back(DT.getNode(&BB));
668 
669   // True as long as long as the current instruction is guaranteed to execute.
670   bool GuaranteedToExecute = true;
671   // Scan BB for assume calls.
672   // TODO: also use this scan to queue conditions to simplify, so we can
673   // interleave facts from assumes and conditions to simplify in a single
674   // basic block. And to skip another traversal of each basic block when
675   // simplifying.
676   for (Instruction &I : BB) {
677     Value *Cond;
678     // For now, just handle assumes with a single compare as condition.
679     if (match(&I, m_Intrinsic<Intrinsic::assume>(m_Value(Cond))) &&
680         isa<ICmpInst>(Cond)) {
681       if (GuaranteedToExecute) {
682         // The assume is guaranteed to execute when BB is entered, hence Cond
683         // holds on entry to BB.
684         WorkList.emplace_back(DT.getNode(&BB), cast<ICmpInst>(Cond), false);
685       } else {
686         // Otherwise the condition only holds in the successors.
687         for (BasicBlock *Succ : successors(&BB)) {
688           if (!canAddSuccessor(BB, Succ))
689             continue;
690           WorkList.emplace_back(DT.getNode(Succ), cast<ICmpInst>(Cond), false);
691         }
692       }
693     }
694     GuaranteedToExecute &= isGuaranteedToTransferExecutionToSuccessor(&I);
695   }
696 
697   auto *Br = dyn_cast<BranchInst>(BB.getTerminator());
698   if (!Br || !Br->isConditional())
699     return;
700 
701   Value *Cond = Br->getCondition();
702 
703   // If the condition is a chain of ORs/AND and the successor only has the
704   // current block as predecessor, queue conditions for the successor.
705   Value *Op0, *Op1;
706   if (match(Cond, m_LogicalOr(m_Value(Op0), m_Value(Op1))) ||
707       match(Cond, m_LogicalAnd(m_Value(Op0), m_Value(Op1)))) {
708     bool IsOr = match(Cond, m_LogicalOr());
709     bool IsAnd = match(Cond, m_LogicalAnd());
710     // If there's a select that matches both AND and OR, we need to commit to
711     // one of the options. Arbitrarily pick OR.
712     if (IsOr && IsAnd)
713       IsAnd = false;
714 
715     BasicBlock *Successor = Br->getSuccessor(IsOr ? 1 : 0);
716     if (canAddSuccessor(BB, Successor)) {
717       SmallVector<Value *> CondWorkList;
718       SmallPtrSet<Value *, 8> SeenCond;
719       auto QueueValue = [&CondWorkList, &SeenCond](Value *V) {
720         if (SeenCond.insert(V).second)
721           CondWorkList.push_back(V);
722       };
723       QueueValue(Op1);
724       QueueValue(Op0);
725       while (!CondWorkList.empty()) {
726         Value *Cur = CondWorkList.pop_back_val();
727         if (auto *Cmp = dyn_cast<ICmpInst>(Cur)) {
728           WorkList.emplace_back(DT.getNode(Successor), Cmp, IsOr);
729           continue;
730         }
731         if (IsOr && match(Cur, m_LogicalOr(m_Value(Op0), m_Value(Op1)))) {
732           QueueValue(Op1);
733           QueueValue(Op0);
734           continue;
735         }
736         if (IsAnd && match(Cur, m_LogicalAnd(m_Value(Op0), m_Value(Op1)))) {
737           QueueValue(Op1);
738           QueueValue(Op0);
739           continue;
740         }
741       }
742     }
743     return;
744   }
745 
746   auto *CmpI = dyn_cast<ICmpInst>(Br->getCondition());
747   if (!CmpI)
748     return;
749   if (canAddSuccessor(BB, Br->getSuccessor(0)))
750     WorkList.emplace_back(DT.getNode(Br->getSuccessor(0)), CmpI, false);
751   if (canAddSuccessor(BB, Br->getSuccessor(1)))
752     WorkList.emplace_back(DT.getNode(Br->getSuccessor(1)), CmpI, true);
753 }
754 
755 static bool checkAndReplaceCondition(CmpInst *Cmp, ConstraintInfo &Info) {
756   LLVM_DEBUG(dbgs() << "Checking " << *Cmp << "\n");
757 
758   CmpInst::Predicate Pred = Cmp->getPredicate();
759   Value *A = Cmp->getOperand(0);
760   Value *B = Cmp->getOperand(1);
761 
762   auto R = Info.getConstraintForSolving(Pred, A, B);
763   if (R.empty() || !R.isValid(Info)){
764     LLVM_DEBUG(dbgs() << "   failed to decompose condition\n");
765     return false;
766   }
767 
768   auto &CSToUse = Info.getCS(R.IsSigned);
769 
770   // If there was extra information collected during decomposition, apply
771   // it now and remove it immediately once we are done with reasoning
772   // about the constraint.
773   for (auto &Row : R.ExtraInfo)
774     CSToUse.addVariableRow(Row);
775   auto InfoRestorer = make_scope_exit([&]() {
776     for (unsigned I = 0; I < R.ExtraInfo.size(); ++I)
777       CSToUse.popLastConstraint();
778   });
779 
780   bool Changed = false;
781   if (CSToUse.isConditionImplied(R.Coefficients)) {
782     if (!DebugCounter::shouldExecute(EliminatedCounter))
783       return false;
784 
785     LLVM_DEBUG({
786       dbgs() << "Condition " << *Cmp << " implied by dominating constraints\n";
787       dumpWithNames(CSToUse, Info.getValue2Index(R.IsSigned));
788     });
789     Constant *TrueC =
790         ConstantInt::getTrue(CmpInst::makeCmpResultType(Cmp->getType()));
791     Cmp->replaceUsesWithIf(TrueC, [](Use &U) {
792       // Conditions in an assume trivially simplify to true. Skip uses
793       // in assume calls to not destroy the available information.
794       auto *II = dyn_cast<IntrinsicInst>(U.getUser());
795       return !II || II->getIntrinsicID() != Intrinsic::assume;
796     });
797     NumCondsRemoved++;
798     Changed = true;
799   }
800   if (CSToUse.isConditionImplied(ConstraintSystem::negate(R.Coefficients))) {
801     if (!DebugCounter::shouldExecute(EliminatedCounter))
802       return false;
803 
804     LLVM_DEBUG({
805       dbgs() << "Condition !" << *Cmp << " implied by dominating constraints\n";
806       dumpWithNames(CSToUse, Info.getValue2Index(R.IsSigned));
807     });
808     Constant *FalseC =
809         ConstantInt::getFalse(CmpInst::makeCmpResultType(Cmp->getType()));
810     Cmp->replaceAllUsesWith(FalseC);
811     NumCondsRemoved++;
812     Changed = true;
813   }
814   return Changed;
815 }
816 
817 void ConstraintInfo::addFact(CmpInst::Predicate Pred, Value *A, Value *B,
818                              unsigned NumIn, unsigned NumOut,
819                              SmallVectorImpl<StackEntry> &DFSInStack) {
820   // If the constraint has a pre-condition, skip the constraint if it does not
821   // hold.
822   SmallVector<Value *> NewVariables;
823   auto R = getConstraint(Pred, A, B, NewVariables);
824   if (!R.isValid(*this))
825     return;
826 
827   LLVM_DEBUG(dbgs() << "Adding '" << CmpInst::getPredicateName(Pred) << " ";
828              A->printAsOperand(dbgs(), false); dbgs() << ", ";
829              B->printAsOperand(dbgs(), false); dbgs() << "'\n");
830   bool Added = false;
831   auto &CSToUse = getCS(R.IsSigned);
832   if (R.Coefficients.empty())
833     return;
834 
835   Added |= CSToUse.addVariableRowFill(R.Coefficients);
836 
837   // If R has been added to the system, add the new variables and queue it for
838   // removal once it goes out-of-scope.
839   if (Added) {
840     SmallVector<Value *, 2> ValuesToRelease;
841     auto &Value2Index = getValue2Index(R.IsSigned);
842     for (Value *V : NewVariables) {
843       Value2Index.insert({V, Value2Index.size() + 1});
844       ValuesToRelease.push_back(V);
845     }
846 
847     LLVM_DEBUG({
848       dbgs() << "  constraint: ";
849       dumpWithNames(R.Coefficients, getValue2Index(R.IsSigned));
850       dbgs() << "\n";
851     });
852 
853     DFSInStack.emplace_back(NumIn, NumOut, R.IsSigned, ValuesToRelease);
854 
855     if (R.IsEq) {
856       // Also add the inverted constraint for equality constraints.
857       for (auto &Coeff : R.Coefficients)
858         Coeff *= -1;
859       CSToUse.addVariableRowFill(R.Coefficients);
860 
861       DFSInStack.emplace_back(NumIn, NumOut, R.IsSigned,
862                               SmallVector<Value *, 2>());
863     }
864   }
865 }
866 
867 static bool replaceSubOverflowUses(IntrinsicInst *II, Value *A, Value *B,
868                                    SmallVectorImpl<Instruction *> &ToRemove) {
869   bool Changed = false;
870   IRBuilder<> Builder(II->getParent(), II->getIterator());
871   Value *Sub = nullptr;
872   for (User *U : make_early_inc_range(II->users())) {
873     if (match(U, m_ExtractValue<0>(m_Value()))) {
874       if (!Sub)
875         Sub = Builder.CreateSub(A, B);
876       U->replaceAllUsesWith(Sub);
877       Changed = true;
878     } else if (match(U, m_ExtractValue<1>(m_Value()))) {
879       U->replaceAllUsesWith(Builder.getFalse());
880       Changed = true;
881     } else
882       continue;
883 
884     if (U->use_empty()) {
885       auto *I = cast<Instruction>(U);
886       ToRemove.push_back(I);
887       I->setOperand(0, PoisonValue::get(II->getType()));
888       Changed = true;
889     }
890   }
891 
892   if (II->use_empty()) {
893     II->eraseFromParent();
894     Changed = true;
895   }
896   return Changed;
897 }
898 
899 static bool
900 tryToSimplifyOverflowMath(IntrinsicInst *II, ConstraintInfo &Info,
901                           SmallVectorImpl<Instruction *> &ToRemove) {
902   auto DoesConditionHold = [](CmpInst::Predicate Pred, Value *A, Value *B,
903                               ConstraintInfo &Info) {
904     auto R = Info.getConstraintForSolving(Pred, A, B);
905     if (R.size() < 2 || !R.isValid(Info))
906       return false;
907 
908     auto &CSToUse = Info.getCS(R.IsSigned);
909     return CSToUse.isConditionImplied(R.Coefficients);
910   };
911 
912   bool Changed = false;
913   if (II->getIntrinsicID() == Intrinsic::ssub_with_overflow) {
914     // If A s>= B && B s>= 0, ssub.with.overflow(a, b) should not overflow and
915     // can be simplified to a regular sub.
916     Value *A = II->getArgOperand(0);
917     Value *B = II->getArgOperand(1);
918     if (!DoesConditionHold(CmpInst::ICMP_SGE, A, B, Info) ||
919         !DoesConditionHold(CmpInst::ICMP_SGE, B,
920                            ConstantInt::get(A->getType(), 0), Info))
921       return false;
922     Changed = replaceSubOverflowUses(II, A, B, ToRemove);
923   }
924   return Changed;
925 }
926 
927 static bool eliminateConstraints(Function &F, DominatorTree &DT) {
928   bool Changed = false;
929   DT.updateDFSNumbers();
930 
931   ConstraintInfo Info(F.getParent()->getDataLayout());
932   State S(DT);
933 
934   // First, collect conditions implied by branches and blocks with their
935   // Dominator DFS in and out numbers.
936   for (BasicBlock &BB : F) {
937     if (!DT.getNode(&BB))
938       continue;
939     S.addInfoFor(BB);
940   }
941 
942   // Next, sort worklist by dominance, so that dominating blocks and conditions
943   // come before blocks and conditions dominated by them. If a block and a
944   // condition have the same numbers, the condition comes before the block, as
945   // it holds on entry to the block. Also make sure conditions with constant
946   // operands come before conditions without constant operands. This increases
947   // the effectiveness of the current signed <-> unsigned fact transfer logic.
948   stable_sort(
949       S.WorkList, [](const ConstraintOrBlock &A, const ConstraintOrBlock &B) {
950         auto HasNoConstOp = [](const ConstraintOrBlock &B) {
951           return !B.IsBlock && !isa<ConstantInt>(B.Condition->getOperand(0)) &&
952                  !isa<ConstantInt>(B.Condition->getOperand(1));
953         };
954         bool NoConstOpA = HasNoConstOp(A);
955         bool NoConstOpB = HasNoConstOp(B);
956         return std::tie(A.NumIn, A.IsBlock, NoConstOpA) <
957                std::tie(B.NumIn, B.IsBlock, NoConstOpB);
958       });
959 
960   SmallVector<Instruction *> ToRemove;
961 
962   // Finally, process ordered worklist and eliminate implied conditions.
963   SmallVector<StackEntry, 16> DFSInStack;
964   for (ConstraintOrBlock &CB : S.WorkList) {
965     // First, pop entries from the stack that are out-of-scope for CB. Remove
966     // the corresponding entry from the constraint system.
967     while (!DFSInStack.empty()) {
968       auto &E = DFSInStack.back();
969       LLVM_DEBUG(dbgs() << "Top of stack : " << E.NumIn << " " << E.NumOut
970                         << "\n");
971       LLVM_DEBUG(dbgs() << "CB: " << CB.NumIn << " " << CB.NumOut << "\n");
972       assert(E.NumIn <= CB.NumIn);
973       if (CB.NumOut <= E.NumOut)
974         break;
975       LLVM_DEBUG({
976         dbgs() << "Removing ";
977         dumpWithNames(Info.getCS(E.IsSigned).getLastConstraint(),
978                       Info.getValue2Index(E.IsSigned));
979         dbgs() << "\n";
980       });
981 
982       Info.popLastConstraint(E.IsSigned);
983       // Remove variables in the system that went out of scope.
984       auto &Mapping = Info.getValue2Index(E.IsSigned);
985       for (Value *V : E.ValuesToRelease)
986         Mapping.erase(V);
987       Info.popLastNVariables(E.IsSigned, E.ValuesToRelease.size());
988       DFSInStack.pop_back();
989     }
990 
991     LLVM_DEBUG({
992       dbgs() << "Processing ";
993       if (CB.IsBlock)
994         dbgs() << *CB.BB;
995       else
996         dbgs() << *CB.Condition;
997       dbgs() << "\n";
998     });
999 
1000     // For a block, check if any CmpInsts become known based on the current set
1001     // of constraints.
1002     if (CB.IsBlock) {
1003       for (Instruction &I : make_early_inc_range(*CB.BB)) {
1004         if (auto *II = dyn_cast<WithOverflowInst>(&I)) {
1005           Changed |= tryToSimplifyOverflowMath(II, Info, ToRemove);
1006           continue;
1007         }
1008         auto *Cmp = dyn_cast<ICmpInst>(&I);
1009         if (!Cmp)
1010           continue;
1011 
1012         Changed |= checkAndReplaceCondition(Cmp, Info);
1013       }
1014       continue;
1015     }
1016 
1017     ICmpInst::Predicate Pred;
1018     Value *A, *B;
1019     if (match(CB.Condition, m_ICmp(Pred, m_Value(A), m_Value(B)))) {
1020       // Use the inverse predicate if required.
1021       if (CB.Not)
1022         Pred = CmpInst::getInversePredicate(Pred);
1023 
1024       Info.addFact(Pred, A, B, CB.NumIn, CB.NumOut, DFSInStack);
1025       Info.transferToOtherSystem(Pred, A, B, CB.NumIn, CB.NumOut, DFSInStack);
1026     }
1027   }
1028 
1029 #ifndef NDEBUG
1030   unsigned SignedEntries =
1031       count_if(DFSInStack, [](const StackEntry &E) { return E.IsSigned; });
1032   assert(Info.getCS(false).size() == DFSInStack.size() - SignedEntries &&
1033          "updates to CS and DFSInStack are out of sync");
1034   assert(Info.getCS(true).size() == SignedEntries &&
1035          "updates to CS and DFSInStack are out of sync");
1036 #endif
1037 
1038   for (Instruction *I : ToRemove)
1039     I->eraseFromParent();
1040   return Changed;
1041 }
1042 
1043 PreservedAnalyses ConstraintEliminationPass::run(Function &F,
1044                                                  FunctionAnalysisManager &AM) {
1045   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
1046   if (!eliminateConstraints(F, DT))
1047     return PreservedAnalyses::all();
1048 
1049   PreservedAnalyses PA;
1050   PA.preserve<DominatorTreeAnalysis>();
1051   PA.preserveSet<CFGAnalyses>();
1052   return PA;
1053 }
1054 
1055 namespace {
1056 
1057 class ConstraintElimination : public FunctionPass {
1058 public:
1059   static char ID;
1060 
1061   ConstraintElimination() : FunctionPass(ID) {
1062     initializeConstraintEliminationPass(*PassRegistry::getPassRegistry());
1063   }
1064 
1065   bool runOnFunction(Function &F) override {
1066     auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1067     return eliminateConstraints(F, DT);
1068   }
1069 
1070   void getAnalysisUsage(AnalysisUsage &AU) const override {
1071     AU.setPreservesCFG();
1072     AU.addRequired<DominatorTreeWrapperPass>();
1073     AU.addPreserved<GlobalsAAWrapperPass>();
1074     AU.addPreserved<DominatorTreeWrapperPass>();
1075   }
1076 };
1077 
1078 } // end anonymous namespace
1079 
1080 char ConstraintElimination::ID = 0;
1081 
1082 INITIALIZE_PASS_BEGIN(ConstraintElimination, "constraint-elimination",
1083                       "Constraint Elimination", false, false)
1084 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
1085 INITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass)
1086 INITIALIZE_PASS_END(ConstraintElimination, "constraint-elimination",
1087                     "Constraint Elimination", false, false)
1088 
1089 FunctionPass *llvm::createConstraintEliminationPass() {
1090   return new ConstraintElimination();
1091 }
1092