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