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