[SCEV] Sequential/in-order `UMin` expression

[lebedev.ri]

Summary

This is a very rough proof of concept.

As discussed in https://github.com/llvm/llvm-project/issues/53020 / https://reviews.llvm.org/D116692,
SCEV is forbidden from reasoning about 'backedge taken count'
if the branch condition is a poison-safe logical operation,
which is conservatively correct, but is severely limiting.

Instead, we should have a way to express those
poison blocking properties in SCEV expressions.

The proposed semantics is:

Sequential/in-order min/max SCEV expressions are non-commutative variants
of commutative min/max SCEV expressions. If none of their operands
are poison, then they are functionally equivalent, otherwise,
if the operand that represents the saturation point* of given expression,
comes before the first poison operand, then the whole expression is not poison,
but is said saturation point.

• saturation point - the maximal/minimal possible integer value for the given type

The lowering is straight-forward:

compare each operand to the saturation point,
perform sequential in-order logical-or (poison-safe!) ordered reduction over those checks,
and if reduction returned true then return saturation point
else return the naive min/max reduction over the operands

https://alive2.llvm.org/ce/z/Q7jxvH (2 ops)
https://alive2.llvm.org/ce/z/QCRrhk (3 ops)
Note that we don't need to check the last operand: https://alive2.llvm.org/ce/z/abvHQS
Note that this is not commutative: https://alive2.llvm.org/ce/z/FK9e97

That allows us to handle the patterns in question.

[lebedev.ri]

Precommit the tests.
Drop dead code (safe UMax).

[lebedev.ri]

Fix 3+-operand expansion - unsurprisingly, we must use logical or, i.e. it's poison-blocking form.

[reames]

Before you go any further, can you explain what you mean by "poison safe"? What IR are you hoping to generate in the end, and why is that more correct than what we have previously?

p.s. I understand the current code is broken, and why. I just haven't seen a viable proposal for a fix as of yet.

[nikic]

Thanks, this is about what I had in mind. The need for this is annoying, but I don't really see a way around it.

In D116766#3226340, @reames wrote:

Before you go any further, can you explain what you mean by "poison safe"? What IR are you hoping to generate in the end, and why is that more correct than what we have previously?

p.s. I understand the current code is broken, and why. I just haven't seen a viable proposal for a fix as of yet.

The lowering is X == 0 ? 0 : umin(X, Y), which has the same result as umin(X, Y), except in the case where X == 0 and Y == poison, in which case poison is not propagated. So if you have an always-taken exit with TC=0 that prevents branching on a later poison exit, then this is now modeled correctly.

An alternative lowering would be umin(X, freeze Y).

[nikic]

llvm/lib/Analysis/ScalarEvolution.cpp

3973

getMinMaxExpr() currently assumes that the operands are commutative, e.g. in GroupByComplexity. Some of the folds would have to be skipped or done differently for "safe umin".

[nikic]

Worth noting that we should be using "safe umin" not just for the logical or case, but also when combining exit counts from multiple exits, which is the more common case. It's probably best to do that separately, but that would give a clearer picture of how bad this is in terms of practical impact, because we have a lot more tests for that.

[aqjune]

Since x == 0 ? x : umin(x, y) cannot be represented using the current SCEV operations (at least using the ops in SCEVTypes). I believe the new ops in this patch are necessary.
Another approach to support such expressions would be adding a ternary operator and comparisons to SCEV, but it would require bigger changes, I guess?

On the other hand, I think operations in SCEV must be clear about how it deals with poison values.
Can we assume that inputs/outputs of operations in SCEV can be poison in general, or it is allowed only for certain operations like SafeUMinExpr?

[lebedev.ri]

Thanks for taking a look!

In D116766#3226340, @reames wrote:

Before you go any further, can you explain what you mean by "poison safe"? What IR are you hoping to generate in the end, and why is that more correct than what we have previously?

I believe others have already explained it well before i could.
I've adjusted the differential's description with a bit more blurb and alive2 reasoning.
Let me know if that is still not sufficient.

In D116766, @nikic wrote:

getMinMaxExpr() currently assumes that the operands are commutative, e.g. in GroupByComplexity. Some of the folds would have to be skipped or done differently for "safe umin".

Right. I've now made the expression non-commutative.

In D116766#3226805, @nikic wrote:

Worth noting that we should be using "safe umin" not just for the logical or case, but also when combining exit counts from multiple exits, which is the more common case. It's probably best to do that separately, but that would give a clearer picture of how bad this is in terms of practical impact, because we have a lot more tests for that.

Yep, i really don't want to deal with everything at once :)

Using "safe" really bothered me, i've gone ahead and used "saturating" instead,
since that is what happens in reality: https://alive2.llvm.org/ce/z/abvHQS (+ non-commutativity)

[lebedev.ri]

Naming things is perhaps the hardest part. After thinking about it more,
i feel like what should be emphasized is the sequential-ness of these reductions.
I'm not going to change this myself again, but i'm open to thoughts whether there is a better naming alternative.

[nikic]

I'm on board with the "sequential" name, LGTM from my side. But please wait for @reames to approve as well.

There are some pretty obvious folds we can do (in particular, we should be trying to convert umin_seq to umin with known non-zero/non-poison values), but those are best left for later.

llvm/include/llvm/Analysis/ScalarEvolution.h

632

Still using the old name here.

736

Rename to Sequential here as well for consistency?

llvm/include/llvm/Analysis/ScalarEvolutionExpressions.h

56

Precommit reformat of this file?

552

Is this needed? Doesn't look relevant for minmax.

[lebedev.ri]

Thanks for taking a look!
Squash last few post-rename relics.

Waiting on @reames / @efriedma / @mkazantsev.

llvm/include/llvm/Analysis/ScalarEvolutionExpressions.h

560–561

This is the only user of setNoWrapFlags(), i simply mimic what SCEVMinMaxExpr does.

[reames]

I skimmed the code for a sanity check, but am mostly just commenting on the high level bits.

I'm not convinced this is the right approach, but I also don't want to block iterative progress. My primary concern is that I don't see how this solves the multiple exit case and that I think we're going to end up needing a new representation there, which indirectly solves this problem. However, I think we can work step-wise here, and come back to refactor/clean this up if needed.

Personally, I think I'd have preferred to introduce a freeze node as that seems potentially more reusable, but I have no strong argument there, just a gut feel.

On naming, I'd suggest ordered reduction as that's the term I'm familiar with from the vectorizaion literature for floating point reductions, and poison in integer domain seems analogous, but this is a fairly minor point.

So overall, weakly hesitant, but don't let that stop you.

llvm/include/llvm/IR/IRBuilder.h

1574

I'd expand this comment a bit.

From the vectorization literature, the term is often ordered reduction. Might be good to use the same name.

[lebedev.ri]

@reames thanks for taking a look!
I'm hesitant as to what name is most obvious, that will depend
on the literature/area, and i'm just not seeing anything less contrived.

I do agree that it's possible that some more generic solution
will subsume this fix, but as you have said, there's likely no need
to not be step-by-step process.
I'm somewhat cautious of freeze here, it's a heavy hammer.

With that, does this look good?

[nikic]

In D116766#3231777, @reames wrote:

I skimmed the code for a sanity check, but am mostly just commenting on the high level bits.

I'm not convinced this is the right approach, but I also don't want to block iterative progress. My primary concern is that I don't see how this solves the multiple exit case and that I think we're going to end up needing a new representation there, which indirectly solves this problem. However, I think we can work step-wise here, and come back to refactor/clean this up if needed.

Why do you think this would't solve the multiple exit case? The new node is currently not used for that case, but I do believe it would address that case as well (if used).

[reames]

In D116766#3231853, @nikic wrote:

In D116766#3231777, @reames wrote:

I skimmed the code for a sanity check, but am mostly just commenting on the high level bits.

I'm not convinced this is the right approach, but I also don't want to block iterative progress. My primary concern is that I don't see how this solves the multiple exit case and that I think we're going to end up needing a new representation there, which indirectly solves this problem. However, I think we can work step-wise here, and come back to refactor/clean this up if needed.

Why do you think this would't solve the multiple exit case? The new node is currently not used for that case, but I do believe it would address that case as well (if used).

The case I was thinking of was when exit1 was taken on iteration N, but exit2's condition becomes poison on that same iteration. However, thinking about it harder, I think the existing code is required to simply return N+1 for exit2, and that's not directly a problem. However, by that logic we don't have a problem around multiple exits at all, so I'm clearly missing/forgetting something.

So, maybe it does? I haven't fully thought through that problem yet.

[reames]

In D116766#3231847, @lebedev.ri wrote:

With that, does this look good?

As said before, my remaining comments are non-blocking. You've got a LGTM, go for it.

[lebedev.ri]

In D116766#3231878, @reames wrote:

In D116766#3231847, @lebedev.ri wrote:

With that, does this look good?

As said before, my remaining comments are non-blocking. You've got a LGTM, go for it.

Thank you.

[akhuang]

Hi, this change caused clang to crash in chromium arm builds; could you take a look?

reduced repro

$ cat t.c
int a, b;
int c() {
  int d;
  while (a) {
    int e, f;
    for (; e && d; ++e) {
      g();
      ++d;
    }
    for (; f < e; ++f)
      if (b)
        return 0;
  }
}
$ clang -cc1 -triple thumbv7-unknown-linux-android23 -S -Oz t.c

Thanks!

[nathanchance]

Just in case it is something different than the Chromium report, I see an assertion failure while building the Linux kernel. Reduced reproducer:

$ cat route.i
struct snd_pcm_plugin_channel {
  int enabled : 1;
} snd_pcm_area_copy(), *zero_areas_dvp;
int route_transfer_plugin_1_0, route_transfer_plugin_0_0;
void route_transfer() {
  int nsrcs, ndsts, dst;
  nsrcs = route_transfer_plugin_0_0;
  ndsts = route_transfer_plugin_1_0;
  dst = 0;
  for (; dst < ndsts && dst < nsrcs; ++dst)
    snd_pcm_area_copy();
  ndsts = dst;
  dst = 0;
  for (; dst < ndsts; ++dst)
    zero_areas_dvp->enabled = 0;
}

$ clang --target=aarch64-linux-gnu -O1 -c -o /dev/null route.i

$ clang --target=aarch64-linux-gnu -O2 -c -o /dev/null route.i
Unknown SCEV type!
UNREACHABLE executed at /home/nathan/cbl/github/tc-build/llvm-project/llvm/lib/Analysis/ScalarEvolution.cpp:9299!
...

[reames]

I've disabled this in f62f47f5. If you see failures after that, let me know and I'll do a full revert.

[nathanchance]

f62f47f5e1f641b41d3b7d593c058ebec2883534 hides the assertion failure for me.

[lebedev.ri]

Thanks! That was the same failure.
Reduced and relanded/fixed in rG76a0abbc13cdfd3ae71f8db8a9376f65a9f6f725.

llvm/include/llvm/Analysis/ScalarEvolution.h

public:
   /// \p GEP The GEP. The indices contained in the GEP itself are ignored,
   /// instead we use IndexExprs.
   /// \p IndexExprs The expressions for the indices.
   const SCEV *getGEPExpr(GEPOperator *GEP,
                          const SmallVectorImpl<const SCEV *> &IndexExprs);
   const SCEV *getAbsExpr(const SCEV *Op, bool IsNSW);
   const SCEV *getMinMaxExpr(SCEVTypes Kind,
                             SmallVectorImpl<const SCEV *> &Operands);
+  const SCEV *getSaturatingMinMaxExpr(SCEVTypes Kind,
+                                      SmallVectorImpl<const SCEV *> &Operands);
   const SCEV *getSMaxExpr(const SCEV *LHS, const SCEV *RHS);
   const SCEV *getSMaxExpr(SmallVectorImpl<const SCEV *> &Operands);
   const SCEV *getUMaxExpr(const SCEV *LHS, const SCEV *RHS);
   const SCEV *getUMaxExpr(SmallVectorImpl<const SCEV *> &Operands);
   const SCEV *getSMinExpr(const SCEV *LHS, const SCEV *RHS);
   const SCEV *getSMinExpr(SmallVectorImpl<const SCEV *> &Operands);
-  const SCEV *getUMinExpr(const SCEV *LHS, const SCEV *RHS);
-  const SCEV *getUMinExpr(SmallVectorImpl<const SCEV *> &Operands);
+  const SCEV *getUMinExpr(const SCEV *LHS, const SCEV *RHS,
+                          bool Saturating = false);
+  const SCEV *getUMinExpr(SmallVectorImpl<const SCEV *> &Operands,
+                          bool Saturating = false);
   const SCEV *getUnknown(Value *V);
   const SCEV *getCouldNotCompute();
 
   /// Return a SCEV for the constant 0 of a specific type.
   const SCEV *getZero(Type *Ty) { return getConstant(Ty, 0); }
 
   /// Return a SCEV for the constant 1 of a specific type.
   const SCEV *getOne(Type *Ty) { return getConstant(Ty, 1); }
public:
   const SCEV *getTruncateOrNoop(const SCEV *V, Type *Ty);
 
   /// Promote the operands to the wider of the types using zero-extension, and
   /// then perform a umax operation with them.
   const SCEV *getUMaxFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS);
 
   /// Promote the operands to the wider of the types using zero-extension, and
   /// then perform a umin operation with them.
-  const SCEV *getUMinFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS);
+  const SCEV *getUMinFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS,
+                                         bool Saturating = false);
 
   /// Promote the operands to the wider of the types using zero-extension, and
   /// then perform a umin operation with them. N-ary function.
-  const SCEV *getUMinFromMismatchedTypes(SmallVectorImpl<const SCEV *> &Ops);
+  const SCEV *getUMinFromMismatchedTypes(SmallVectorImpl<const SCEV *> &Ops,
+                                         bool Saturating = false);
 
   /// Transitively follow the chain of pointer-type operands until reaching a
   /// SCEV that does not have a single pointer operand. This returns a
   /// SCEVUnknown pointer for well-formed pointer-type expressions, but corner
   /// cases do exist.
   const SCEV *getPointerBase(const SCEV *V);
 
   /// Compute an expression equivalent to S - getPointerBase(S).

llvm/include/llvm/Analysis/ScalarEvolutionDivision.h

public:
   void visitTruncateExpr(const SCEVTruncateExpr *Numerator) {}
   void visitZeroExtendExpr(const SCEVZeroExtendExpr *Numerator) {}
   void visitSignExtendExpr(const SCEVSignExtendExpr *Numerator) {}
   void visitUDivExpr(const SCEVUDivExpr *Numerator) {}
   void visitSMaxExpr(const SCEVSMaxExpr *Numerator) {}
   void visitUMaxExpr(const SCEVUMaxExpr *Numerator) {}
   void visitSMinExpr(const SCEVSMinExpr *Numerator) {}
   void visitUMinExpr(const SCEVUMinExpr *Numerator) {}
+  void visitSequentialUMinExpr(const SCEVSequentialUMinExpr *Numerator) {}
   void visitUnknown(const SCEVUnknown *Numerator) {}
   void visitCouldNotCompute(const SCEVCouldNotCompute *Numerator) {}
 
   void visitConstant(const SCEVConstant *Numerator);
 
   void visitAddRecExpr(const SCEVAddRecExpr *Numerator);
 
   void visitAddExpr(const SCEVAddExpr *Numerator);

llvm/include/llvm/Analysis/ScalarEvolutionExpressions.h

 namespace llvm {
 
 class APInt;
 class Constant;
 class ConstantRange;
 class Loop;
 class Type;
 
-  enum SCEVTypes : unsigned short {
-    // These should be ordered in terms of increasing complexity to make the
-    // folders simpler.
-    scConstant, scTruncate, scZeroExtend, scSignExtend, scAddExpr, scMulExpr,
-    scUDivExpr, scAddRecExpr, scUMaxExpr, scSMaxExpr, scUMinExpr, scSMinExpr,
-    scPtrToInt, scUnknown, scCouldNotCompute
-  };
+  scConstant,
+  scTruncate,
+  scZeroExtend,
+  scSignExtend,
+  scAddExpr,
+  scMulExpr,
+  scUDivExpr,
+  scAddRecExpr,
+  scUMaxExpr,
+  scSMaxExpr,
+  scUMinExpr,
+  scSMinExpr,
+  scPtrToInt,
+  scSequentialUMinExpr,
+  scUnknown,
+  scCouldNotCompute
 
-  /// This class represents a constant integer value.
-  class SCEVConstant : public SCEV {
-    friend class ScalarEvolution;
 
-    ConstantInt *V;
 
-    SCEVConstant(const FoldingSetNodeIDRef ID, ConstantInt *v) :
-      SCEV(ID, scConstant, 1), V(v) {}
+  SCEVConstant(const FoldingSetNodeIDRef ID, ConstantInt *v)
+      : SCEV(ID, scConstant, 1), V(v) {}
 
-  public:
-    ConstantInt *getValue() const { return V; }
-    const APInt &getAPInt() const { return getValue()->getValue(); }
 
-    Type *getType() const { return V->getType(); }
 
-    /// Methods for support type inquiry through isa, cast, and dyn_cast:
-    static bool classof(const SCEV *S) {
-      return S->getSCEVType() == scConstant;
-    }
-  };
+  static bool classof(const SCEV *S) { return S->getSCEVType() == scConstant; }
 
   inline unsigned short computeExpressionSize(ArrayRef<const SCEV *> Args) {
     APInt Size(16, 1);
     for (auto *Arg : Args)
       Size = Size.uadd_sat(APInt(16, Arg->getExpressionSize()));
     return (unsigned short)Size.getZExtValue();
   }
 
bool hasNoSelfWrap() const {
       return getNoWrapFlags(FlagNW) != FlagAnyWrap;
     }
 
     /// Methods for support type inquiry through isa, cast, and dyn_cast:
     static bool classof(const SCEV *S) {
       return S->getSCEVType() == scAddExpr || S->getSCEVType() == scMulExpr ||
              S->getSCEVType() == scSMaxExpr || S->getSCEVType() == scUMaxExpr ||
              S->getSCEVType() == scSMinExpr || S->getSCEVType() == scUMinExpr ||
+             S->getSCEVType() == scSequentialUMinExpr ||
              S->getSCEVType() == scAddRecExpr;
     }
   };
 
   /// This node is the base class for n'ary commutative operators.
   class SCEVCommutativeExpr : public SCEVNAryExpr {
   protected:
     SCEVCommutativeExpr(const FoldingSetNodeIDRef ID,
public:
 
   public:
     /// Methods for support type inquiry through isa, cast, and dyn_cast:
     static bool classof(const SCEV *S) {
       return S->getSCEVType() == scUMinExpr;
     }
   };
 
+  /// This node is the base class for sequential/in-order min/max selections.
+  /// Note that their fundamental difference from SCEVMinMaxExpr's is that they
+  /// are early-returning upon reaching saturation point.
+  /// I.e. given `0 umin_seq poison`, the result will be `0`,
+  /// while the result of `0 umin poison` is `poison`.
+  class SCEVSequentialMinMaxExpr : public SCEVNAryExpr {
+    friend class ScalarEvolution;
+
+    static bool isSequentialMinMaxType(enum SCEVTypes T) {
+      return T == scSequentialUMinExpr;
+    }
+
+    /// Set flags for a non-recurrence without clearing previously set flags.
+    void setNoWrapFlags(NoWrapFlags Flags) { SubclassData |= Flags; }
+
+  protected:
+    /// Note: Constructing subclasses via this constructor is allowed
+    SCEVSequentialMinMaxExpr(const FoldingSetNodeIDRef ID, enum SCEVTypes T,
+                             const SCEV *const *O, size_t N)
+        : SCEVNAryExpr(ID, T, O, N) {
+      assert(isSequentialMinMaxType(T));
+      // Min and max never overflow
+      setNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW));
+    }
+
+  public:
+    Type *getType() const { return getOperand(0)->getType(); }
+
+    static bool classof(const SCEV *S) {
+      return isSequentialMinMaxType(S->getSCEVType());
+    }
+  };
+
+  /// This class represents a sequential/in-order unsigned minimum selection.
+  class SCEVSequentialUMinExpr : public SCEVSequentialMinMaxExpr {
+    friend class ScalarEvolution;
+
+    SCEVSequentialUMinExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O,
+                           size_t N)
+        : SCEVSequentialMinMaxExpr(ID, scSequentialUMinExpr, O, N) {}
+
+  public:
+    /// Methods for support type inquiry through isa, cast, and dyn_cast:
+    static bool classof(const SCEV *S) {
+      return S->getSCEVType() == scSequentialUMinExpr;
+    }
+  };
+
   /// This means that we are dealing with an entirely unknown SCEV
   /// value, and only represent it as its LLVM Value.  This is the
   /// "bottom" value for the analysis.
   class SCEVUnknown final : public SCEV, private CallbackVH {
     friend class ScalarEvolution;
 
     /// The parent ScalarEvolution value. This is used to update the
     /// parent's maps when the value associated with a SCEVUnknown is
RetVal visit(const SCEV *S) {
       case scSMaxExpr:
         return ((SC*)this)->visitSMaxExpr((const SCEVSMaxExpr*)S);
       case scUMaxExpr:
         return ((SC*)this)->visitUMaxExpr((const SCEVUMaxExpr*)S);
       case scSMinExpr:
         return ((SC *)this)->visitSMinExpr((const SCEVSMinExpr *)S);
       case scUMinExpr:
         return ((SC *)this)->visitUMinExpr((const SCEVUMinExpr *)S);
+      case scSequentialUMinExpr:
+        return ((SC *)this)
+            ->visitSequentialUMinExpr((const SCEVSequentialUMinExpr *)S);
       case scUnknown:
         return ((SC*)this)->visitUnknown((const SCEVUnknown*)S);
       case scCouldNotCompute:
         return ((SC*)this)->visitCouldNotCompute((const SCEVCouldNotCompute*)S);
       }
       llvm_unreachable("Unknown SCEV kind!");
     }
 
void visitAll(const SCEV *Root) {
           push(cast<SCEVCastExpr>(S)->getOperand());
           continue;
         case scAddExpr:
         case scMulExpr:
         case scSMaxExpr:
         case scUMaxExpr:
         case scSMinExpr:
         case scUMinExpr:
+        case scSequentialUMinExpr:
         case scAddRecExpr:
           for (const auto *Op : cast<SCEVNAryExpr>(S)->operands())
             push(Op);
           continue;
         case scUDivExpr: {
           const SCEVUDivExpr *UDiv = cast<SCEVUDivExpr>(S);
           push(UDiv->getLHS());
           push(UDiv->getRHS());
const SCEV *visitUMinExpr(const SCEVUMinExpr *Expr) {
       bool Changed = false;
       for (auto *Op : Expr->operands()) {
         Operands.push_back(((SC *)this)->visit(Op));
         Changed |= Op != Operands.back();
       }
       return !Changed ? Expr : SE.getUMinExpr(Operands);
     }
 
+    const SCEV *visitSequentialUMinExpr(const SCEVSequentialUMinExpr *Expr) {
+      SmallVector<const SCEV *, 2> Operands;
+      bool Changed = false;
+      for (auto *Op : Expr->operands()) {
+        Operands.push_back(((SC *)this)->visit(Op));
+        Changed |= Op != Operands.back();
+      }
+      return !Changed ? Expr : SE.getUMinExpr(Operands, /*Saturating=*/true);
+    }
+
     const SCEV *visitUnknown(const SCEVUnknown *Expr) {
       return Expr;
     }
 
     const SCEV *visitCouldNotCompute(const SCEVCouldNotCompute *Expr) {
       return Expr;
     }
   };

llvm/include/llvm/IR/IRBuilder.h

public:
   }
 
   Value *CreateLogicalOr(Value *Cond1, Value *Cond2, const Twine &Name = "") {
     assert(Cond2->getType()->isIntOrIntVectorTy(1));
     return CreateSelect(Cond1, ConstantInt::getAllOnesValue(Cond2->getType()),
                         Cond2, Name);
   }
 
+  // NOTE: this is sequential, non-commutative reduction!
+  Value *CreateLogicalOr(ArrayRef<Value *> Ops) {
+    assert(!Ops.empty());
+    Value *Accum = Ops[0];
+    for (unsigned i = 1; i < Ops.size(); i++)
+      Accum = CreateLogicalOr(Accum, Ops[i]);
+    return Accum;
+  }
+
   CallInst *CreateConstrainedFPBinOp(
       Intrinsic::ID ID, Value *L, Value *R, Instruction *FMFSource = nullptr,
       const Twine &Name = "", MDNode *FPMathTag = nullptr,
       Optional<RoundingMode> Rounding = None,
       Optional<fp::ExceptionBehavior> Except = None);
 
   Value *CreateNeg(Value *V, const Twine &Name = "",
                    bool HasNUW = false, bool HasNSW = false) {

llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h

private:
   ScalarEvolution::ValueOffsetPair
   FindValueInExprValueMap(const SCEV *S, const Instruction *InsertPt);
 
   Value *expand(const SCEV *S);
 
   /// Determine the most "relevant" loop for the given SCEV.
   const Loop *getRelevantLoop(const SCEV *);
 
+  Value *expandSMaxExpr(const SCEVNAryExpr *S);
+
+  Value *expandUMaxExpr(const SCEVNAryExpr *S);
+
+  Value *expandSMinExpr(const SCEVNAryExpr *S);
+
+  Value *expandUMinExpr(const SCEVNAryExpr *S);
+
   Value *visitConstant(const SCEVConstant *S) { return S->getValue(); }
 
   Value *visitPtrToIntExpr(const SCEVPtrToIntExpr *S);
 
   Value *visitTruncateExpr(const SCEVTruncateExpr *S);
 
   Value *visitZeroExtendExpr(const SCEVZeroExtendExpr *S);
 
private:
   Value *visitSMaxExpr(const SCEVSMaxExpr *S);
 
   Value *visitUMaxExpr(const SCEVUMaxExpr *S);
 
   Value *visitSMinExpr(const SCEVSMinExpr *S);
 
   Value *visitUMinExpr(const SCEVUMinExpr *S);
 
+  Value *visitSequentialUMinExpr(const SCEVSequentialUMinExpr *S);
+
   Value *visitUnknown(const SCEVUnknown *S) { return S->getValue(); }
 
   void rememberInstruction(Value *I);
 
   bool isNormalAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L);
 
   bool isExpandedAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L);
 

llvm/lib/Analysis/ScalarEvolution.cpp

case scAddRecExpr: {
     OS << ">";
     return;
   }
   case scAddExpr:
   case scMulExpr:
   case scUMaxExpr:
   case scSMaxExpr:
   case scUMinExpr:
-  case scSMinExpr: {
+  case scSMinExpr:
+  case scSequentialUMinExpr: {
     const SCEVNAryExpr *NAry = cast<SCEVNAryExpr>(this);
     const char *OpStr = nullptr;
     switch (NAry->getSCEVType()) {
     case scAddExpr: OpStr = " + "; break;
     case scMulExpr: OpStr = " * "; break;
     case scUMaxExpr: OpStr = " umax "; break;
     case scSMaxExpr: OpStr = " smax "; break;
     case scUMinExpr:
       OpStr = " umin ";
       break;
     case scSMinExpr:
       OpStr = " smin ";
       break;
+    case scSequentialUMinExpr:
+      OpStr = " umin_seq ";
+      break;
     default:
       llvm_unreachable("There are no other nary expression types.");
     }
     OS << "(";
     ListSeparator LS(OpStr);
     for (const SCEV *Op : NAry->operands())
       OS << LS << *Op;
     OS << ")";
case scAddRecExpr:
     return cast<SCEVAddRecExpr>(this)->getType();
   case scMulExpr:
     return cast<SCEVMulExpr>(this)->getType();
   case scUMaxExpr:
   case scSMaxExpr:
   case scUMinExpr:
   case scSMinExpr:
     return cast<SCEVMinMaxExpr>(this)->getType();
+  case scSequentialUMinExpr:
+    return cast<SCEVSequentialMinMaxExpr>(this)->getType();
   case scAddExpr:
     return cast<SCEVAddExpr>(this)->getType();
   case scUDivExpr:
     return cast<SCEVUDivExpr>(this)->getType();
   case scUnknown:
     return cast<SCEVUnknown>(this)->getType();
   case scCouldNotCompute:
     llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
case scAddRecExpr: {
     return 0;
   }
 
   case scAddExpr:
   case scMulExpr:
   case scSMaxExpr:
   case scUMaxExpr:
   case scSMinExpr:
-  case scUMinExpr: {
+  case scUMinExpr:
+  case scSequentialUMinExpr: {
     const SCEVNAryExpr *LC = cast<SCEVNAryExpr>(LHS);
     const SCEVNAryExpr *RC = cast<SCEVNAryExpr>(RHS);
 
     // Lexicographically compare n-ary expressions.
     unsigned LNumOps = LC->getNumOperands(), RNumOps = RC->getNumOperands();
     if (LNumOps != RNumOps)
       return (int)LNumOps - (int)RNumOps;
 

 
 const SCEV *ScalarEvolution::getAbsExpr(const SCEV *Op, bool IsNSW) {
   SCEV::NoWrapFlags Flags = IsNSW ? SCEV::FlagNSW : SCEV::FlagAnyWrap;
   return getSMaxExpr(Op, getNegativeSCEV(Op, Flags));
 }
 
 const SCEV *ScalarEvolution::getMinMaxExpr(SCEVTypes Kind,
                                            SmallVectorImpl<const SCEV *> &Ops) {
+  assert(SCEVMinMaxExpr::isMinMaxType(Kind) && "Not a SCEVMinMaxExpr!");
   assert(!Ops.empty() && "Cannot get empty (u|s)(min|max)!");
   if (Ops.size() == 1) return Ops[0];
 #ifndef NDEBUG
   Type *ETy = getEffectiveSCEVType(Ops[0]->getType());
   for (unsigned i = 1, e = Ops.size(); i != e; ++i) {
     assert(getEffectiveSCEVType(Ops[i]->getType()) == ETy &&
            "Operand types don't match!");
     assert(Ops[0]->getType()->isPointerTy() ==
#endif
   SCEV *S = new (SCEVAllocator)
       SCEVMinMaxExpr(ID.Intern(SCEVAllocator), Kind, O, Ops.size());
 
   UniqueSCEVs.InsertNode(S, IP);
   registerUser(S, Ops);
   return S;
 }
 
+const SCEV *
+ScalarEvolution::getSaturatingMinMaxExpr(SCEVTypes Kind,
+                                         SmallVectorImpl<const SCEV *> &Ops) {
+  assert(SCEVSequentialMinMaxExpr::isSequentialMinMaxType(Kind) &&
+         "Not a SCEVSequentialMinMaxExpr!");
+  assert(!Ops.empty() && "Cannot get empty (u|s)(min|max)!");
+  if (Ops.size() == 1)
+    return Ops[0];
+#ifndef NDEBUG
+  Type *ETy = getEffectiveSCEVType(Ops[0]->getType());
+  for (unsigned i = 1, e = Ops.size(); i != e; ++i) {
+    assert(getEffectiveSCEVType(Ops[i]->getType()) == ETy &&
+           "Operand types don't match!");
+    assert(Ops[0]->getType()->isPointerTy() ==
+               Ops[i]->getType()->isPointerTy() &&
+           "min/max should be consistently pointerish");
+  }
+#endif
+
+  // Note that SCEVSequentialMinMaxExpr is *NOT* commutative,
+  // so we can *NOT* do any kind of sorting of the expressions!
+
+  // Check if we have created the same expression before.
+  if (const SCEV *S = findExistingSCEVInCache(Kind, Ops))
+    return S;
+
+  // FIXME: there are *some* simplifications that we can do here.
+
+  // Check to see if one of the operands is of the same kind. If so, expand its
+  // operands onto our operand list, and recurse to simplify.
+  {
+    unsigned Idx = 0;
+    bool DeletedAny = false;
+    while (Idx < Ops.size()) {
+      if (Ops[Idx]->getSCEVType() != Kind) {
+        ++Idx;
+        continue;
+      }
+      const auto *SMME = cast<SCEVSequentialMinMaxExpr>(Ops[Idx]);
+      Ops.erase(Ops.begin() + Idx);
+      Ops.insert(Ops.begin() + Idx, SMME->op_begin(), SMME->op_end());
+      DeletedAny = true;
+    }
+
+    if (DeletedAny)
+      return getSaturatingMinMaxExpr(Kind, Ops);
+  }
+
+  // Okay, it looks like we really DO need an expr.  Check to see if we
+  // already have one, otherwise create a new one.
+  FoldingSetNodeID ID;
+  ID.AddInteger(Kind);
+  for (unsigned i = 0, e = Ops.size(); i != e; ++i)
+    ID.AddPointer(Ops[i]);
+  void *IP = nullptr;
+  const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(ID, IP);
+  if (ExistingSCEV)
+    return ExistingSCEV;
+
+  const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size());
+  std::uninitialized_copy(Ops.begin(), Ops.end(), O);
+  SCEV *S = new (SCEVAllocator)
+      SCEVSequentialMinMaxExpr(ID.Intern(SCEVAllocator), Kind, O, Ops.size());
+
+  UniqueSCEVs.InsertNode(S, IP);
+  registerUser(S, Ops);
+  return S;
+}
+
 const SCEV *ScalarEvolution::getSMaxExpr(const SCEV *LHS, const SCEV *RHS) {
   SmallVector<const SCEV *, 2> Ops = {LHS, RHS};
   return getSMaxExpr(Ops);
 }
 
 const SCEV *ScalarEvolution::getSMaxExpr(SmallVectorImpl<const SCEV *> &Ops) {
   return getMinMaxExpr(scSMaxExpr, Ops);
 }
const SCEV *ScalarEvolution::getSMinExpr(const SCEV *LHS,
   SmallVector<const SCEV *, 2> Ops = { LHS, RHS };
   return getSMinExpr(Ops);
 }
 
 const SCEV *ScalarEvolution::getSMinExpr(SmallVectorImpl<const SCEV *> &Ops) {
   return getMinMaxExpr(scSMinExpr, Ops);
 }
 
-const SCEV *ScalarEvolution::getUMinExpr(const SCEV *LHS,
-                                         const SCEV *RHS) {
+const SCEV *ScalarEvolution::getUMinExpr(const SCEV *LHS, const SCEV *RHS,
+                                         bool Saturating) {
   SmallVector<const SCEV *, 2> Ops = { LHS, RHS };
-  return getUMinExpr(Ops);
+  return getUMinExpr(Ops, Saturating);
 }
 
-const SCEV *ScalarEvolution::getUMinExpr(SmallVectorImpl<const SCEV *> &Ops) {
-  return getMinMaxExpr(scUMinExpr, Ops);
+const SCEV *ScalarEvolution::getUMinExpr(SmallVectorImpl<const SCEV *> &Ops,
+                                         bool Saturating) {
+  return Saturating ? getSaturatingMinMaxExpr(scSequentialUMinExpr, Ops)
+                    : getMinMaxExpr(scUMinExpr, Ops);
 }
 
 const SCEV *
 ScalarEvolution::getSizeOfScalableVectorExpr(Type *IntTy,
                                              ScalableVectorType *ScalableTy) {
   Constant *NullPtr = Constant::getNullValue(ScalableTy->getPointerTo());
   Constant *One = ConstantInt::get(IntTy, 1);
   Constant *GEP = ConstantExpr::getGetElementPtr(ScalableTy, NullPtr, One);
if (getTypeSizeInBits(LHS->getType()) > getTypeSizeInBits(RHS->getType()))
     PromotedRHS = getZeroExtendExpr(RHS, LHS->getType());
   else
     PromotedLHS = getNoopOrZeroExtend(LHS, RHS->getType());
 
   return getUMaxExpr(PromotedLHS, PromotedRHS);
 }
 
 const SCEV *ScalarEvolution::getUMinFromMismatchedTypes(const SCEV *LHS,
-                                                        const SCEV *RHS) {
+                                                        const SCEV *RHS,
+                                                        bool Saturating) {
   SmallVector<const SCEV *, 2> Ops = { LHS, RHS };
-  return getUMinFromMismatchedTypes(Ops);
+  return getUMinFromMismatchedTypes(Ops, Saturating);
 }
 
-const SCEV *ScalarEvolution::getUMinFromMismatchedTypes(
-    SmallVectorImpl<const SCEV *> &Ops) {
+const SCEV *
+ScalarEvolution::getUMinFromMismatchedTypes(SmallVectorImpl<const SCEV *> &Ops,
+                                            bool Saturating) {
   assert(!Ops.empty() && "At least one operand must be!");
   // Trivial case.
   if (Ops.size() == 1)
     return Ops[0];
 
   // Find the max type first.
   Type *MaxType = nullptr;
   for (auto *S : Ops)
     if (MaxType)
       MaxType = getWiderType(MaxType, S->getType());
     else
       MaxType = S->getType();
   assert(MaxType && "Failed to find maximum type!");
 
   // Extend all ops to max type.
   SmallVector<const SCEV *, 2> PromotedOps;
   for (auto *S : Ops)
     PromotedOps.push_back(getNoopOrZeroExtend(S, MaxType));
 
   // Generate umin.
-  return getUMinExpr(PromotedOps);
+  return getUMinExpr(PromotedOps, Saturating);
 }
 
 const SCEV *ScalarEvolution::getPointerBase(const SCEV *V) {
   // A pointer operand may evaluate to a nonpointer expression, such as null.
   if (!V->getType()->isPointerTy())
     return V;
 
   while (true) {
bool follow(const SCEV *S) {
       case scZeroExtend:
       case scSignExtend:
       case scAddExpr:
       case scMulExpr:
       case scUMaxExpr:
       case scSMaxExpr:
       case scUMinExpr:
       case scSMinExpr:
+      case scSequentialUMinExpr:
         // These expressions are available if their operand(s) is/are.
         return true;
 
       case scAddRecExpr: {
         // We allow add recurrences that are on the loop BB is in, or some
         // outer loop.  This guarantees availability because the value of the
         // add recurrence at BB is simply the "current" value of the induction
         // variable.  We can relax this in the future; for instance an add
ScalarEvolution::getRangeRef(const SCEV *S,
   if (const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(S)) {
     ConstantRange X = getRangeRef(Mul->getOperand(0), SignHint);
     for (unsigned i = 1, e = Mul->getNumOperands(); i != e; ++i)
       X = X.multiply(getRangeRef(Mul->getOperand(i), SignHint));
     return setRange(Mul, SignHint,
                     ConservativeResult.intersectWith(X, RangeType));
   }
 
-  if (isa<SCEVMinMaxExpr>(S)) {
+  if (isa<SCEVMinMaxExpr>(S) || isa<SCEVSequentialMinMaxExpr>(S)) {
     Intrinsic::ID ID;
     switch (S->getSCEVType()) {
     case scUMaxExpr:
       ID = Intrinsic::umax;
       break;
     case scSMaxExpr:
       ID = Intrinsic::smax;
       break;
     case scUMinExpr:
+    case scSequentialUMinExpr:
       ID = Intrinsic::umin;
       break;
     case scSMinExpr:
       ID = Intrinsic::smin;
       break;
     default:
-      llvm_unreachable("Unknown SCEVMinMaxExpr.");
+      llvm_unreachable("Unknown SCEVMinMaxExpr/SCEVSequentialMinMaxExpr.");
     }
 
     const auto *NAry = cast<SCEVNAryExpr>(S);
     ConstantRange X = getRangeRef(NAry->getOperand(0), SignHint);
     for (unsigned i = 1, e = NAry->getNumOperands(); i != e; ++i)
       X = X.intrinsic(ID, {X, getRangeRef(NAry->getOperand(i), SignHint)});
     return setRange(S, SignHint,
                     ConservativeResult.intersectWith(X, RangeType));
if (!PoisonSafe)
       // (2) EL1.ExactNotTaken is non-poison
       // (3) EL0.ExactNotTaken is zero (BECount should be simply zero and
       //     it cannot be umin(0, ..))
       // The PoisonSafe assignment below is simplified and the assertion after
       // BECount calculation fully guarantees the condition (3).
       PoisonSafe = isa<SCEVConstant>(EL0.ExactNotTaken) ||
                    isa<SCEVConstant>(EL1.ExactNotTaken);
     if (EL0.ExactNotTaken != getCouldNotCompute() &&
-        EL1.ExactNotTaken != getCouldNotCompute() && PoisonSafe) {
-      BECount =
-          getUMinFromMismatchedTypes(EL0.ExactNotTaken, EL1.ExactNotTaken);
+        EL1.ExactNotTaken != getCouldNotCompute()) {
+      BECount = getUMinFromMismatchedTypes(EL0.ExactNotTaken, EL1.ExactNotTaken,
+                                           /*Saturating=*/!PoisonSafe);
 
       // If EL0.ExactNotTaken was zero and ExitCond was a short-circuit form,
       // it should have been simplified to zero (see the condition (3) above)
       assert(!isa<BinaryOperator>(ExitCond) || !EL0.ExactNotTaken->isZero() ||
              BECount->isZero());
     }
     if (EL0.MaxNotTaken == getCouldNotCompute())
       MaxBECount = EL1.MaxNotTaken;
if (Constant *LHS = BuildConstantFromSCEV(SU->getLHS()))
         if (LHS->getType() == RHS->getType())
           return ConstantExpr::getUDiv(LHS, RHS);
     return nullptr;
   }
   case scSMaxExpr:
   case scUMaxExpr:
   case scSMinExpr:
   case scUMinExpr:
-    return nullptr; // TODO: smax, umax, smin, umax.
+  case scSequentialUMinExpr:
+    return nullptr; // TODO: smax, umax, smin, umax, umin_seq.
   }
   llvm_unreachable("Unknown SCEV kind!");
 }
 
 const SCEV *ScalarEvolution::computeSCEVAtScope(const SCEV *V, const Loop *L) {
   if (isa<SCEVConstant>(V)) return V;
 
   // If this instruction is evolved from a constant-evolving PHI, compute the
return
         IsMinMaxConsistingOf<SCEVSMaxExpr>(RHS, LHS);
 
   case ICmpInst::ICMP_UGE:
     std::swap(LHS, RHS);
     LLVM_FALLTHROUGH;
   case ICmpInst::ICMP_ULE:
     return
         // min(A, ...) <= A
+        // FIXME: what about umin_seq?
         IsMinMaxConsistingOf<SCEVUMinExpr>(LHS, RHS) ||
         // A <= max(A, ...)
         IsMinMaxConsistingOf<SCEVUMaxExpr>(RHS, LHS);
   }
 
   llvm_unreachable("covered switch fell through?!");
 }
 
case scAddRecExpr: {
     // Otherwise it's loop-invariant.
     return LoopInvariant;
   }
   case scAddExpr:
   case scMulExpr:
   case scUMaxExpr:
   case scSMaxExpr:
   case scUMinExpr:
-  case scSMinExpr: {
+  case scSMinExpr:
+  case scSequentialUMinExpr: {
     bool HasVarying = false;
     for (auto *Op : cast<SCEVNAryExpr>(S)->operands()) {
       LoopDisposition D = getLoopDisposition(Op, L);
       if (D == LoopVariant)
         return LoopVariant;
       if (D == LoopComputable)
         HasVarying = true;
     }
case scAddRecExpr: {
     // Fall through into SCEVNAryExpr handling.
     LLVM_FALLTHROUGH;
   }
   case scAddExpr:
   case scMulExpr:
   case scUMaxExpr:
   case scSMaxExpr:
   case scUMinExpr:
-  case scSMinExpr: {
+  case scSMinExpr:
+  case scSequentialUMinExpr: {
     const SCEVNAryExpr *NAry = cast<SCEVNAryExpr>(S);
     bool Proper = true;
     for (const SCEV *NAryOp : NAry->operands()) {
       BlockDisposition D = getBlockDisposition(NAryOp, BB);
       if (D == DoesNotDominateBlock)
         return DoesNotDominateBlock;
       if (D == DominatesBlock)
         Proper = false;

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

 Value *SCEVExpander::visitSignExtendExpr(const SCEVSignExtendExpr *S) {
   Type *Ty = SE.getEffectiveSCEVType(S->getType());
   Value *V = expandCodeForImpl(
       S->getOperand(), SE.getEffectiveSCEVType(S->getOperand()->getType()),
       false);
   return Builder.CreateSExt(V, Ty);
 }
 
-Value *SCEVExpander::visitSMaxExpr(const SCEVSMaxExpr *S) {
+Value *SCEVExpander::expandSMaxExpr(const SCEVNAryExpr *S) {
   Value *LHS = expand(S->getOperand(S->getNumOperands()-1));
   Type *Ty = LHS->getType();
   for (int i = S->getNumOperands()-2; i >= 0; --i) {
     // In the case of mixed integer and pointer types, do the
     // rest of the comparisons as integer.
     Type *OpTy = S->getOperand(i)->getType();
     if (OpTy->isIntegerTy() != Ty->isIntegerTy()) {
       Ty = SE.getEffectiveSCEVType(Ty);
Value *SCEVExpander::expandSMaxExpr(const SCEVNAryExpr *S) {
   }
   // In the case of mixed integer and pointer types, cast the
   // final result back to the pointer type.
   if (LHS->getType() != S->getType())
     LHS = InsertNoopCastOfTo(LHS, S->getType());
   return LHS;
 }
 
-Value *SCEVExpander::visitUMaxExpr(const SCEVUMaxExpr *S) {
+Value *SCEVExpander::expandUMaxExpr(const SCEVNAryExpr *S) {
   Value *LHS = expand(S->getOperand(S->getNumOperands()-1));
   Type *Ty = LHS->getType();
   for (int i = S->getNumOperands()-2; i >= 0; --i) {
     // In the case of mixed integer and pointer types, do the
     // rest of the comparisons as integer.
     Type *OpTy = S->getOperand(i)->getType();
     if (OpTy->isIntegerTy() != Ty->isIntegerTy()) {
       Ty = SE.getEffectiveSCEVType(Ty);
Value *SCEVExpander::expandUMaxExpr(const SCEVNAryExpr *S) {
   }
   // In the case of mixed integer and pointer types, cast the
   // final result back to the pointer type.
   if (LHS->getType() != S->getType())
     LHS = InsertNoopCastOfTo(LHS, S->getType());
   return LHS;
 }
 
-Value *SCEVExpander::visitSMinExpr(const SCEVSMinExpr *S) {
+Value *SCEVExpander::expandSMinExpr(const SCEVNAryExpr *S) {
   Value *LHS = expand(S->getOperand(S->getNumOperands() - 1));
   Type *Ty = LHS->getType();
   for (int i = S->getNumOperands() - 2; i >= 0; --i) {
     // In the case of mixed integer and pointer types, do the
     // rest of the comparisons as integer.
     Type *OpTy = S->getOperand(i)->getType();
     if (OpTy->isIntegerTy() != Ty->isIntegerTy()) {
       Ty = SE.getEffectiveSCEVType(Ty);
Value *SCEVExpander::expandSMinExpr(const SCEVNAryExpr *S) {
   }
   // In the case of mixed integer and pointer types, cast the
   // final result back to the pointer type.
   if (LHS->getType() != S->getType())
     LHS = InsertNoopCastOfTo(LHS, S->getType());
   return LHS;
 }
 
-Value *SCEVExpander::visitUMinExpr(const SCEVUMinExpr *S) {
+Value *SCEVExpander::expandUMinExpr(const SCEVNAryExpr *S) {
   Value *LHS = expand(S->getOperand(S->getNumOperands() - 1));
   Type *Ty = LHS->getType();
   for (int i = S->getNumOperands() - 2; i >= 0; --i) {
     // In the case of mixed integer and pointer types, do the
     // rest of the comparisons as integer.
     Type *OpTy = S->getOperand(i)->getType();
     if (OpTy->isIntegerTy() != Ty->isIntegerTy()) {
       Ty = SE.getEffectiveSCEVType(Ty);
Value *SCEVExpander::expandUMinExpr(const SCEVNAryExpr *S) {
   }
   // In the case of mixed integer and pointer types, cast the
   // final result back to the pointer type.
   if (LHS->getType() != S->getType())
     LHS = InsertNoopCastOfTo(LHS, S->getType());
   return LHS;
 }
 
+Value *SCEVExpander::visitSMaxExpr(const SCEVSMaxExpr *S) {
+  return expandSMaxExpr(S);
+}
+
+Value *SCEVExpander::visitUMaxExpr(const SCEVUMaxExpr *S) {
+  return expandUMaxExpr(S);
+}
+
+Value *SCEVExpander::visitSMinExpr(const SCEVSMinExpr *S) {
+  return expandSMinExpr(S);
+}
+
+Value *SCEVExpander::visitUMinExpr(const SCEVUMinExpr *S) {
+  return expandUMinExpr(S);
+}
+
+Value *SCEVExpander::visitSequentialUMinExpr(const SCEVSequentialUMinExpr *S) {
+  SmallVector<Value *> Ops;
+  for (const SCEV *Op : S->operands())
+    Ops.emplace_back(expand(Op));
+
+  Value *SaturationPoint =
+      MinMaxIntrinsic::getSaturationPoint(Intrinsic::umin, S->getType());
+
+  SmallVector<Value *> OpIsZero;
+  for (Value *Op : ArrayRef<Value *>(Ops).drop_back())
+    OpIsZero.emplace_back(Builder.CreateICmpEQ(Op, SaturationPoint));
+
+  Value *AnyOpIsZero = Builder.CreateLogicalOr(OpIsZero);
+
+  Value *NaiveUMin = expandUMinExpr(S);
+  return Builder.CreateSelect(AnyOpIsZero, SaturationPoint, NaiveUMin);
+}
+
 Value *SCEVExpander::expandCodeForImpl(const SCEV *SH, Type *Ty,
                                        Instruction *IP, bool Root) {
   setInsertPoint(IP);
   Value *V = expandCodeForImpl(SH, Ty, Root);
   return V;
 }
 
 Value *SCEVExpander::expandCodeForImpl(const SCEV *SH, Type *Ty, bool Root) {
case scMulExpr:
     // TODO: this is a very pessimistic cost modelling for Mul,
     // because of Bin Pow algorithm actually used by the expander,
     // see SCEVExpander::visitMulExpr(), ExpandOpBinPowN().
     Cost = ArithCost(Instruction::Mul, S->getNumOperands() - 1);
     break;
   case scSMaxExpr:
   case scUMaxExpr:
   case scSMinExpr:
-  case scUMinExpr: {
+  case scUMinExpr:
+  case scSequentialUMinExpr: {
     // FIXME: should this ask the cost for Intrinsic's?
+    // The reduction tree.
     Cost += CmpSelCost(Instruction::ICmp, S->getNumOperands() - 1, 0, 1);
     Cost += CmpSelCost(Instruction::Select, S->getNumOperands() - 1, 0, 2);
+    switch (S->getSCEVType()) {
+    case scSequentialUMinExpr: {
+      // The safety net against poison.
+      // FIXME: this is broken.
+      Cost += CmpSelCost(Instruction::ICmp, S->getNumOperands() - 1, 0, 0);
+      Cost += ArithCost(Instruction::Or,
+                        S->getNumOperands() > 2 ? S->getNumOperands() - 2 : 0);
+      Cost += CmpSelCost(Instruction::Select, 1, 0, 1);
+      break;
+    }
+    default:
+      assert(!isa<SCEVSequentialMinMaxExpr>(S) &&
+             "Unhandled SCEV expression type?");
+      break;
+    }
     break;
   }
   case scAddRecExpr: {
     // In this polynominal, we may have some zero operands, and we shouldn't
     // really charge for those. So how many non-zero coeffients are there?
     int NumTerms = llvm::count_if(S->operands(), [](const SCEV *Op) {
                                     return !Op->isZero();
                                   });
Cost +=
         costAndCollectOperands<SCEVUDivExpr>(WorkItem, TTI, CostKind, Worklist);
     return false; // Will answer upon next entry into this function.
   }
   case scAddExpr:
   case scMulExpr:
   case scUMaxExpr:
   case scSMaxExpr:
   case scUMinExpr:
-  case scSMinExpr: {
+  case scSMinExpr:
+  case scSequentialUMinExpr: {
     assert(cast<SCEVNAryExpr>(S)->getNumOperands() > 1 &&
            "Nary expr should have more than 1 operand.");
     // The simple nary expr will require one less op (or pair of ops)
     // than the number of it's terms.
     Cost +=
         costAndCollectOperands<SCEVNAryExpr>(WorkItem, TTI, CostKind, Worklist);
     return Cost > Budget;
   }

llvm/test/Analysis/ScalarEvolution/exit-count-select-safe.ll

 ; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py
 ; RUN: opt -disable-output "-passes=print<scalar-evolution>" %s 2>&1 | FileCheck %s
 
-; exact-not-taken cannot be umin(n, m) because it is possible for (n, m) to be (0, poison)
-; https://alive2.llvm.org/ce/z/NsP9ue
 define i32 @logical_and_2ops(i32 %n, i32 %m) {
 ; CHECK-LABEL: 'logical_and_2ops'
 ; CHECK-NEXT:  Classifying expressions for: @logical_and_2ops
 ; CHECK-NEXT:    %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
-; CHECK-NEXT:    --> {0,+,1}<%loop> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {0,+,1}<%loop> U: full-set S: full-set Exits: (%n umin_seq %m) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %i.next = add i32 %i, 1
-; CHECK-NEXT:    --> {1,+,1}<%loop> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {1,+,1}<%loop> U: full-set S: full-set Exits: (1 + (%n umin_seq %m)) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %cond = select i1 %cond_p0, i1 %cond_p1, i1 false
 ; CHECK-NEXT:    --> %cond U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 ; CHECK-NEXT:  Determining loop execution counts for: @logical_and_2ops
-; CHECK-NEXT:  Loop %loop: Unpredictable backedge-taken count.
+; CHECK-NEXT:  Loop %loop: backedge-taken count is (%n umin_seq %m)
 ; CHECK-NEXT:  Loop %loop: max backedge-taken count is -1
-; CHECK-NEXT:  Loop %loop: Unpredictable predicated backedge-taken count.
+; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is (%n umin_seq %m)
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %loop: Trip multiple is 1
 ;
 entry:
   br label %loop
 loop:
   %i = phi i32 [0, %entry], [%i.next, %loop]
   %i.next = add i32 %i, 1
   %cond_p0 = icmp ult i32 %i, %n
   %cond_p1 = icmp ult i32 %i, %m
   %cond = select i1 %cond_p0, i1 %cond_p1, i1 false
   br i1 %cond, label %loop, label %exit
 exit:
   ret i32 %i
 }
 
-; exact-not-taken cannot be umin(n, m) because it is possible for (n, m) to be (0, poison)
-; https://alive2.llvm.org/ce/z/ApRitq
 define i32 @logical_or_2ops(i32 %n, i32 %m) {
 ; CHECK-LABEL: 'logical_or_2ops'
 ; CHECK-NEXT:  Classifying expressions for: @logical_or_2ops
 ; CHECK-NEXT:    %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
-; CHECK-NEXT:    --> {0,+,1}<%loop> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {0,+,1}<%loop> U: full-set S: full-set Exits: (%n umin_seq %m) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %i.next = add i32 %i, 1
-; CHECK-NEXT:    --> {1,+,1}<%loop> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {1,+,1}<%loop> U: full-set S: full-set Exits: (1 + (%n umin_seq %m)) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %cond = select i1 %cond_p0, i1 true, i1 %cond_p1
 ; CHECK-NEXT:    --> %cond U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 ; CHECK-NEXT:  Determining loop execution counts for: @logical_or_2ops
-; CHECK-NEXT:  Loop %loop: Unpredictable backedge-taken count.
+; CHECK-NEXT:  Loop %loop: backedge-taken count is (%n umin_seq %m)
 ; CHECK-NEXT:  Loop %loop: max backedge-taken count is -1
-; CHECK-NEXT:  Loop %loop: Unpredictable predicated backedge-taken count.
+; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is (%n umin_seq %m)
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %loop: Trip multiple is 1
 ;
 entry:
   br label %loop
 loop:
   %i = phi i32 [0, %entry], [%i.next, %loop]
   %i.next = add i32 %i, 1
   %cond_p0 = icmp uge i32 %i, %n
   %cond_p1 = icmp uge i32 %i, %m
   %cond = select i1 %cond_p0, i1 true, i1 %cond_p1
   br i1 %cond, label %exit, label %loop
 exit:
   ret i32 %i
 }
 
 define i32 @logical_and_3ops(i32 %n, i32 %m, i32 %k) {
 ; CHECK-LABEL: 'logical_and_3ops'
 ; CHECK-NEXT:  Classifying expressions for: @logical_and_3ops
 ; CHECK-NEXT:    %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
-; CHECK-NEXT:    --> {0,+,1}<%loop> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {0,+,1}<%loop> U: full-set S: full-set Exits: (%n umin_seq %m umin_seq %k) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %i.next = add i32 %i, 1
-; CHECK-NEXT:    --> {1,+,1}<%loop> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {1,+,1}<%loop> U: full-set S: full-set Exits: (1 + (%n umin_seq %m umin_seq %k)) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %cond_p3 = select i1 %cond_p0, i1 %cond_p1, i1 false
 ; CHECK-NEXT:    --> %cond_p3 U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 ; CHECK-NEXT:    %cond = select i1 %cond_p3, i1 %cond_p2, i1 false
 ; CHECK-NEXT:    --> %cond U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 ; CHECK-NEXT:  Determining loop execution counts for: @logical_and_3ops
-; CHECK-NEXT:  Loop %loop: Unpredictable backedge-taken count.
+; CHECK-NEXT:  Loop %loop: backedge-taken count is (%n umin_seq %m umin_seq %k)
 ; CHECK-NEXT:  Loop %loop: max backedge-taken count is -1
-; CHECK-NEXT:  Loop %loop: Unpredictable predicated backedge-taken count.
+; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is (%n umin_seq %m umin_seq %k)
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %loop: Trip multiple is 1
 ;
 entry:
   br label %loop
 loop:
   %i = phi i32 [0, %entry], [%i.next, %loop]
   %i.next = add i32 %i, 1
   %cond_p0 = icmp ult i32 %i, %n
   %cond_p1 = icmp ult i32 %i, %m
   %cond_p2 = icmp ult i32 %i, %k
   %cond_p3 = select i1 %cond_p0, i1 %cond_p1, i1 false
   %cond = select i1 %cond_p3, i1 %cond_p2, i1 false
   br i1 %cond, label %loop, label %exit
 exit:
   ret i32 %i
 }
 
 define i32 @logical_or_3ops(i32 %n, i32 %m, i32 %k) {
 ; CHECK-LABEL: 'logical_or_3ops'
 ; CHECK-NEXT:  Classifying expressions for: @logical_or_3ops
 ; CHECK-NEXT:    %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
-; CHECK-NEXT:    --> {0,+,1}<%loop> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {0,+,1}<%loop> U: full-set S: full-set Exits: (%n umin_seq %m umin_seq %k) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %i.next = add i32 %i, 1
-; CHECK-NEXT:    --> {1,+,1}<%loop> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {1,+,1}<%loop> U: full-set S: full-set Exits: (1 + (%n umin_seq %m umin_seq %k)) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %cond_p3 = select i1 %cond_p0, i1 true, i1 %cond_p1
 ; CHECK-NEXT:    --> %cond_p3 U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 ; CHECK-NEXT:    %cond = select i1 %cond_p3, i1 true, i1 %cond_p2
 ; CHECK-NEXT:    --> %cond U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 ; CHECK-NEXT:  Determining loop execution counts for: @logical_or_3ops
-; CHECK-NEXT:  Loop %loop: Unpredictable backedge-taken count.
+; CHECK-NEXT:  Loop %loop: backedge-taken count is (%n umin_seq %m umin_seq %k)
 ; CHECK-NEXT:  Loop %loop: max backedge-taken count is -1
-; CHECK-NEXT:  Loop %loop: Unpredictable predicated backedge-taken count.
+; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is (%n umin_seq %m umin_seq %k)
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %loop: Trip multiple is 1
 ;
 entry:
   br label %loop
 loop:
   %i = phi i32 [0, %entry], [%i.next, %loop]
   %i.next = add i32 %i, 1
   %cond_p0 = icmp uge i32 %i, %n
   %cond_p1 = icmp uge i32 %i, %m
   %cond_p2 = icmp uge i32 %i, %k
   %cond_p3 = select i1 %cond_p0, i1 true, i1 %cond_p1
   %cond = select i1 %cond_p3, i1 true, i1 %cond_p2
   br i1 %cond, label %exit, label %loop
 exit:
   ret i32 %i
 }

llvm/test/Transforms/IndVarSimplify/exit-count-select.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -indvars -S | FileCheck %s
 
 define i32 @logical_and_2ops(i32 %n, i32 %m) {
 ; CHECK-LABEL: @logical_and_2ops(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[UMIN:%.*]] = call i32 @llvm.umin.i32(i32 [[M:%.*]], i32 [[N:%.*]])
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP]] ]
-; CHECK-NEXT:    [[I_NEXT]] = add i32 [[I]], 1
-; CHECK-NEXT:    [[COND_P0:%.*]] = icmp ult i32 [[I]], [[N:%.*]]
-; CHECK-NEXT:    [[COND_P1:%.*]] = icmp ult i32 [[I]], [[M:%.*]]
-; CHECK-NEXT:    [[COND:%.*]] = select i1 [[COND_P0]], i1 [[COND_P1]], i1 false
-; CHECK-NEXT:    br i1 [[COND]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK-NEXT:    br i1 false, label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[I_LCSSA:%.*]] = phi i32 [ [[I]], [[LOOP]] ]
-; CHECK-NEXT:    ret i32 [[I_LCSSA]]
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp eq i32 [[N]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[TMP0]], i32 0, i32 [[UMIN]]
+; CHECK-NEXT:    ret i32 [[TMP1]]
 ;
 entry:
   br label %loop
 loop:
   %i = phi i32 [0, %entry], [%i.next, %loop]
   %i.next = add i32 %i, 1
   %cond_p0 = icmp ult i32 %i, %n
   %cond_p1 = icmp ult i32 %i, %m
   %cond = select i1 %cond_p0, i1 %cond_p1, i1 false
   br i1 %cond, label %loop, label %exit
 exit:
   ret i32 %i
 }
 
 define i32 @logical_or_2ops(i32 %n, i32 %m) {
 ; CHECK-LABEL: @logical_or_2ops(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[UMIN:%.*]] = call i32 @llvm.umin.i32(i32 [[M:%.*]], i32 [[N:%.*]])
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP]] ]
-; CHECK-NEXT:    [[I_NEXT]] = add i32 [[I]], 1
-; CHECK-NEXT:    [[COND_P0:%.*]] = icmp uge i32 [[I]], [[N:%.*]]
-; CHECK-NEXT:    [[COND_P1:%.*]] = icmp uge i32 [[I]], [[M:%.*]]
-; CHECK-NEXT:    [[COND:%.*]] = select i1 [[COND_P0]], i1 true, i1 [[COND_P1]]
-; CHECK-NEXT:    br i1 [[COND]], label [[EXIT:%.*]], label [[LOOP]]
+; CHECK-NEXT:    br i1 true, label [[EXIT:%.*]], label [[LOOP]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[I_LCSSA:%.*]] = phi i32 [ [[I]], [[LOOP]] ]
-; CHECK-NEXT:    ret i32 [[I_LCSSA]]
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp eq i32 [[N]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[TMP0]], i32 0, i32 [[UMIN]]
+; CHECK-NEXT:    ret i32 [[TMP1]]
 ;
 entry:
   br label %loop
 loop:
   %i = phi i32 [0, %entry], [%i.next, %loop]
   %i.next = add i32 %i, 1
   %cond_p0 = icmp uge i32 %i, %n
   %cond_p1 = icmp uge i32 %i, %m
   %cond = select i1 %cond_p0, i1 true, i1 %cond_p1
   br i1 %cond, label %exit, label %loop
 exit:
   ret i32 %i
 }
 
 define i32 @logical_and_3ops(i32 %n, i32 %m, i32 %k) {
 ; CHECK-LABEL: @logical_and_3ops(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp eq i32 [[M:%.*]], 0
+; CHECK-NEXT:    [[UMIN:%.*]] = call i32 @llvm.umin.i32(i32 [[K:%.*]], i32 [[M]])
+; CHECK-NEXT:    [[UMIN1:%.*]] = call i32 @llvm.umin.i32(i32 [[UMIN]], i32 [[N:%.*]])
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP]] ]
-; CHECK-NEXT:    [[I_NEXT]] = add i32 [[I]], 1
-; CHECK-NEXT:    [[COND_P0:%.*]] = icmp ult i32 [[I]], [[N:%.*]]
-; CHECK-NEXT:    [[COND_P1:%.*]] = icmp ult i32 [[I]], [[M:%.*]]
-; CHECK-NEXT:    [[COND_P2:%.*]] = icmp ult i32 [[I]], [[K:%.*]]
-; CHECK-NEXT:    [[COND_P3:%.*]] = select i1 [[COND_P0]], i1 [[COND_P1]], i1 false
-; CHECK-NEXT:    [[COND:%.*]] = select i1 [[COND_P3]], i1 [[COND_P2]], i1 false
-; CHECK-NEXT:    br i1 [[COND]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK-NEXT:    br i1 false, label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[I_LCSSA:%.*]] = phi i32 [ [[I]], [[LOOP]] ]
-; CHECK-NEXT:    ret i32 [[I_LCSSA]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i32 [[N]], 0
+; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[TMP1]], i1 true, i1 [[TMP0]]
+; CHECK-NEXT:    [[TMP3:%.*]] = select i1 [[TMP2]], i32 0, i32 [[UMIN1]]
+; CHECK-NEXT:    ret i32 [[TMP3]]
 ;
 entry:
   br label %loop
 loop:
   %i = phi i32 [0, %entry], [%i.next, %loop]
   %i.next = add i32 %i, 1
   %cond_p0 = icmp ult i32 %i, %n
   %cond_p1 = icmp ult i32 %i, %m
   %cond_p2 = icmp ult i32 %i, %k
   %cond_p3 = select i1 %cond_p0, i1 %cond_p1, i1 false
   %cond = select i1 %cond_p3, i1 %cond_p2, i1 false
   br i1 %cond, label %loop, label %exit
 exit:
   ret i32 %i
 }
 
 define i32 @logical_or_3ops(i32 %n, i32 %m, i32 %k) {
 ; CHECK-LABEL: @logical_or_3ops(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp eq i32 [[M:%.*]], 0
+; CHECK-NEXT:    [[UMIN:%.*]] = call i32 @llvm.umin.i32(i32 [[K:%.*]], i32 [[M]])
+; CHECK-NEXT:    [[UMIN1:%.*]] = call i32 @llvm.umin.i32(i32 [[UMIN]], i32 [[N:%.*]])
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP]] ]
-; CHECK-NEXT:    [[I_NEXT]] = add i32 [[I]], 1
-; CHECK-NEXT:    [[COND_P0:%.*]] = icmp uge i32 [[I]], [[N:%.*]]
-; CHECK-NEXT:    [[COND_P1:%.*]] = icmp uge i32 [[I]], [[M:%.*]]
-; CHECK-NEXT:    [[COND_P2:%.*]] = icmp uge i32 [[I]], [[K:%.*]]
-; CHECK-NEXT:    [[COND_P3:%.*]] = select i1 [[COND_P0]], i1 true, i1 [[COND_P1]]
-; CHECK-NEXT:    [[COND:%.*]] = select i1 [[COND_P3]], i1 true, i1 [[COND_P2]]
-; CHECK-NEXT:    br i1 [[COND]], label [[EXIT:%.*]], label [[LOOP]]
+; CHECK-NEXT:    br i1 true, label [[EXIT:%.*]], label [[LOOP]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[I_LCSSA:%.*]] = phi i32 [ [[I]], [[LOOP]] ]
-; CHECK-NEXT:    ret i32 [[I_LCSSA]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i32 [[N]], 0
+; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[TMP1]], i1 true, i1 [[TMP0]]
+; CHECK-NEXT:    [[TMP3:%.*]] = select i1 [[TMP2]], i32 0, i32 [[UMIN1]]
+; CHECK-NEXT:    ret i32 [[TMP3]]
 ;
 entry:
   br label %loop
 loop:
   %i = phi i32 [0, %entry], [%i.next, %loop]
   %i.next = add i32 %i, 1
   %cond_p0 = icmp uge i32 %i, %n
   %cond_p1 = icmp uge i32 %i, %m
   %cond_p2 = icmp uge i32 %i, %k
   %cond_p3 = select i1 %cond_p0, i1 true, i1 %cond_p1
   %cond = select i1 %cond_p3, i1 true, i1 %cond_p2
   br i1 %cond, label %exit, label %loop
 exit:
   ret i32 %i
 }

polly/include/polly/Support/SCEVAffinator.h

private:
   PWACtx visitAddExpr(const llvm::SCEVAddExpr *E);
   PWACtx visitMulExpr(const llvm::SCEVMulExpr *E);
   PWACtx visitUDivExpr(const llvm::SCEVUDivExpr *E);
   PWACtx visitAddRecExpr(const llvm::SCEVAddRecExpr *E);
   PWACtx visitSMaxExpr(const llvm::SCEVSMaxExpr *E);
   PWACtx visitSMinExpr(const llvm::SCEVSMinExpr *E);
   PWACtx visitUMaxExpr(const llvm::SCEVUMaxExpr *E);
   PWACtx visitUMinExpr(const llvm::SCEVUMinExpr *E);
+  PWACtx visitSequentialUMinExpr(const llvm::SCEVSequentialUMinExpr *E);
   PWACtx visitUnknown(const llvm::SCEVUnknown *E);
   PWACtx visitSDivInstruction(llvm::Instruction *SDiv);
   PWACtx visitSRemInstruction(llvm::Instruction *SRem);
   PWACtx complexityBailout();
 
   friend struct llvm::SCEVVisitor<SCEVAffinator, PWACtx>;
 };
 } // namespace polly
 
 #endif

polly/lib/Support/SCEVAffinator.cpp

 PWACtx SCEVAffinator::visitUMaxExpr(const SCEVUMaxExpr *Expr) {
   llvm_unreachable("SCEVUMaxExpr not yet supported");
 }
 
 PWACtx SCEVAffinator::visitUMinExpr(const SCEVUMinExpr *Expr) {
   llvm_unreachable("SCEVUMinExpr not yet supported");
 }
 
+PWACtx
+SCEVAffinator::visitSequentialUMinExpr(const SCEVSequentialUMinExpr *Expr) {
+  llvm_unreachable("SCEVSequentialUMinExpr not yet supported");
+}
+
 PWACtx SCEVAffinator::visitUDivExpr(const SCEVUDivExpr *Expr) {
   // The handling of unsigned division is basically the same as for signed
   // division, except the interpretation of the operands. As the divisor
   // has to be constant in both cases we can simply interpret it as an
   // unsigned value without additional complexity in the representation.
   // For the dividend we could choose from the different representation
   // schemes introduced for zero-extend operations but for now we will
   // simply use an assumption.

polly/lib/Support/SCEVValidator.cpp

for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) {
         LLVM_DEBUG(dbgs() << "INVALID: UMinExpr has a non-constant operand");
         return ValidatorResult(SCEVType::INVALID);
       }
     }
 
     return ValidatorResult(SCEVType::PARAM, Expr);
   }
 
+  class ValidatorResult
+  visitSequentialUMinExpr(const SCEVSequentialUMinExpr *Expr) {
+    // We do not support unsigned min operations. If 'Expr' is constant during
+    // Scop execution we treat this as a parameter, otherwise we bail out.
+    for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) {
+      ValidatorResult Op = visit(Expr->getOperand(i));
+
+      if (!Op.isConstant()) {
+        LLVM_DEBUG(
+            dbgs() << "INVALID: SafeUMinExpr has a non-constant operand");
+        return ValidatorResult(SCEVType::INVALID);
+      }
+    }
+
+    return ValidatorResult(SCEVType::PARAM, Expr);
+  }
+
   ValidatorResult visitGenericInst(Instruction *I, const SCEV *S) {
     if (R->contains(I)) {
       LLVM_DEBUG(dbgs() << "INVALID: UnknownExpr references an instruction "
                            "within the region\n");
       return ValidatorResult(SCEVType::INVALID);
     }
 
     return ValidatorResult(SCEVType::PARAM, S);

polly/lib/Support/ScopHelper.cpp

const SCEV *visitUMinExpr(const SCEVUMinExpr *E) {
     return SE.getUMinExpr(NewOps);
   }
   const SCEV *visitSMinExpr(const SCEVSMinExpr *E) {
     SmallVector<const SCEV *, 4> NewOps;
     for (const SCEV *Op : E->operands())
       NewOps.push_back(visit(Op));
     return SE.getSMinExpr(NewOps);
   }
+  const SCEV *visitSequentialUMinExpr(const SCEVSequentialUMinExpr *E) {
+    SmallVector<const SCEV *, 4> NewOps;
+    for (const SCEV *Op : E->operands())
+      NewOps.push_back(visit(Op));
+    return SE.getUMinExpr(NewOps, /*Saturating=*/true);
+  }
   const SCEV *visitAddRecExpr(const SCEVAddRecExpr *E) {
     SmallVector<const SCEV *, 4> NewOps;
     for (const SCEV *Op : E->operands())
       NewOps.push_back(visit(Op));
     return SE.getAddRecExpr(NewOps, E->getLoop(), E->getNoWrapFlags());
   }
   ///}
 };