RFC: [SCEV] Add explicit representations of umin/smin

[loladiro]

Summary

Currently we express umin as ~umax(~x, ~y). However, this becomes
a problem for operands in non-integral pointer spaces, because ~x
is not something we can compute for x non-integral. However, since
comparisons are generally still allowed, we are actually able to
express umin(x, y) directly as long as we don't try to express is
as a umax. Support this by adding an explicit umin/smin representation
to SCEV. We do this by factoring the existing getUMax/getSMax functions
into a new function that does all four. The previous two functions
were largely identical, except that the SMax variant used isKnownPredicate
while the UMax variant used isKnownViaNonRecursiveReasoning.

Trying to make the UMax variant also use isKnownPredicate yields to
an infinite recursion, while trying to make the SMax variant use
isKnownViaNonRecursiveReasoning causes
Transforms/IndVarSimplify/backedge-on-min-max.ll to fail.

I would appreciate any insight into which predicate is correct here.

[loladiro]

Fix a small bug discovered during production testing (
when expanding umin/umax, don't go to integers just because
types are unequal - the only reason to do is if one of the
operands in an integer and the other is not).

[mkazantsev]

Hi Keno,

I have a general concern against such changes. In fact, you are introducing an alternative way to express the same thing. umin(a, b) and umax(~a, ~b) are the same, but now have 2 possible notations. It means that whatever pass or analysis that needs to recognize this pattern needs to be aware of both. Whenever the new node was not supported, it might be missed optimization opportunities. And we cannot know for sure how many such places there are, or will be. What motivation do you have for making this change? Is it strong enough to take a risk of missing optimization opportunities that I've just pointed out?

I'd also like to know @sanjoy 's opinion on that.

Also, I didn't get the part about infinite recursion in the commit message. Is this the behavior you are observing in current SCEV, or it only happens with your patch? In former case, please submit a bug with a test on which you can see that. From my memory, we've fixed getUMax to avoid the inifinite recursion, and maybe the same fix is required for SMax.

[loladiro]

I have a general concern against such changes. In fact, you are introducing an alternative way to express the same thing. umin(a, b) and umax(~a, ~b) are the same, but now have 2 possible notations. It means that whatever pass or analysis that needs to recognize this pattern needs to be aware of both. Whenever the new node was not supported, it might be missed optimization opportunities. And we cannot know for sure how many such places there are, or will be. What motivation do you have for making this change? Is it strong enough to take a risk of missing optimization opportunities that I've just pointed out?

I can understand this concern. On the other hand, by obscuring the true meaning of the pattern (it's not trivial to detect that the argument is actually the negation of another argument - there's some code that tries to do it, but it only works for simple expression), so you also lose the opportunity to optimize based on the existence of umin. In general, I don't really see a good way to deal with non-integral address spaces in the absence of a general umin, short of just disabling these optimizations completely for such pointers, which is not desirable. I suppose another alternative would be to make a first class Neg node type (rather than expanding it through as subs and multiplies), such that (~umax(~x, ~y)) could be pattern matched back into the proper form in code generation. I'm not sure that's any better though, since it just pushed this problem further down the expression tree.

Also, I didn't get the part about infinite recursion in the commit message. Is this the behavior you are observing in current SCEV, or it only happens with your patch? In former case, please submit a bug with a test on which you can see that. From my memory, we've fixed getUMax to avoid the inifinite recursion, and maybe the same fix is required for SMax.

Actually, upon doing some more testing here, I misdiagnosed the test failure (there was a heuristic pattern match to detect the old umin pattern - will push a simple fix monetarily). I'll also put up a separate revision to fix up the isKnownPredicate check for SMax to avoid having that be a behavior change in this revision.

[loladiro]

Fix ir names in tests broken by previous commits and proplerly match u/smin.

[tvvikram]

For some %r and an indvar %i, the SCEV for (1 + min(r - 1, i)) in smax terms is: (-1 * ((-1 * (zext i32 %r to i64))<nsw> smax {-1,+,-1}<nw><%for.outerloop>))<nsw>.
With your patch, smax gets converted to smin as: (1 + ((-1 + (zext i32 %r to i64))<nsw> smin {0,+,1}<nuw><nsw><%for.outerloop>)), which is correct.
But, it could be simplified further by distributing 1 over smin(?). I might be missing something here. Maybe your patch needs improvement or the getAddExpr() should be improved to handle smin.
P.S.: I am adding 1 explicitly in my code to the min expression i.e. SE->getAddExpr(<scevForMin>, getOne(<ty>)) in both the above cases.

[loladiro]

Rebased

[loladiro]

Undo a small spurious change I noticed while browsing the diff

[loladiro]

Alright, I have rebased this revision. I'd be happy to make the improvement to getAddExpr requested by @tvikram, since that seems independently useful, but I'd like to come to an agreement with @sanjoy and @mkazantsev on direction first.

[sanjoy]

This change in isolation LGTM (modulo some minor comments inline) -- at the very least having separate umin / smin nodes makes min expressions more readable (as demonstrated by the updates to the test cases).

However, I'm not sure if this is a sufficient solution of your original problem involving non-integral pointers. Fundamentally to do trip counts right with non-integral pointers, we will at least need to teach SCEV the difference between ni pointers and integers so that it does not create SCEV expressions that cannot be lowered. I think we will also need a psub instruction or intrinsic so that we can compute trip counts for loops like:

ptr0 = ... ; ni pointer
ptr1 = ... ; ni pointer at some offset from ptr0

for (i = ptr0; i != ptr1; i++)
  ...

Of course all of these may be "working" in practice today because of various reasons. :)

lib/Analysis/ScalarEvolution.cpp

3573 ↗

(On Diff #196769)

Let's avoid a nested ternary here. Maybe you could instead use an immediately executed lambda.

3589 ↗

(On Diff #196769)

Probably this can just be one loop if you create two APInts, Top and Bottom, or two lambdas IsTop and IsBottom if you're worried about creating large APInts being expensive.

10137 ↗

(On Diff #196769)

Does this case even fire anymore?

lib/Analysis/ScalarEvolutionExpander.cpp

2165 ↗

(On Diff #196769)

Did this overflow 80 cols?

[loladiro]

lib/Analysis/ScalarEvolution.cpp

10137 ↗

(On Diff #196769)

I wanted to avoid regressing the (probably not very likely, but possible) case that somebody might construct ~umax(~x, ~y) manually. However, in retrospect the better way to do that is probably to just pattern match that to umin on construction. Let me try that and remove this case.

[loladiro]

Rebase and address review comments.

[loladiro]

A few minor tweaks.

[loladiro]

@sanjoy Could you take another look to make sure I have addressed your comments to your satisfaction before I commit this?

[sanjoy]

LGTM. If possible (and you haven't already) try bootstrapping clang in a few configurations to double check things are okay.

[rnk]

This broke the polly build:

[14 processes, 32/64 @ 9.3/s : 3.428s ] Building CXX object tools/polly/lib/CMakeFiles/PollyCore.dir/Support/SCEVAffinator.cpp.o
FAILED: tools/polly/lib/CMakeFiles/PollyCore.dir/Support/SCEVAffinator.cpp.o
...
In file included from /usr/local/google/home/rnk/llvm-project/polly/lib/Support/SCEVAffinator.cpp:13:                                                                            
In file included from /usr/local/google/home/rnk/llvm-project/polly/include/polly/Support/SCEVAffinator.h:16:                                                                    
/usr/local/google/home/rnk/llvm-project/llvm/include/llvm/Analysis/ScalarEvolutionExpressions.h:536:30: error: no member named 'visitSMinExpr' in 'polly::SCEVAffinator'         
        return ((SC *)this)->visitSMinExpr((const SCEVSMinExpr *)S);
               ~~~~~~~~~~~~  ^
/usr/local/google/home/rnk/llvm-project/polly/lib/Support/SCEVAffinator.cpp:218:48: note: in instantiation of member function 'llvm::SCEVVisitor<polly::SCEVAffinator, std::pair<isl::noexceptions::pw_aff, isl::noexceptions::set> >::visit' requested here
    PWAC = SCEVVisitor<SCEVAffinator, PWACtx>::visit(Expr);
                                               ^
In file included from /usr/local/google/home/rnk/llvm-project/polly/lib/Support/SCEVAffinator.cpp:13:                                                                            
In file included from /usr/local/google/home/rnk/llvm-project/polly/include/polly/Support/SCEVAffinator.h:16:                                                                    
/usr/local/google/home/rnk/llvm-project/llvm/include/llvm/Analysis/ScalarEvolutionExpressions.h:538:30: error: no member named 'visitUMinExpr' in 'polly::SCEVAffinator'         
        return ((SC *)this)->visitUMinExpr((const SCEVUMinExpr *)S);
               ~~~~~~~~~~~~  ^
2 errors generated.

[loladiro]

Looked straightforward enough. Should be fixed by rPLO360238. I don't usually work on polly, so let me know if I misunderstood something.

llvm/trunk/include/llvm/Analysis/ScalarEvolution.h

public:
 
   /// Returns an expression for a GEP
   ///
   /// \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 *getMinMaxExpr(unsigned 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);

llvm/trunk/include/llvm/Analysis/ScalarEvolutionExpander.h

private:
     Value *visitUDivExpr(const SCEVUDivExpr *S);
 
     Value *visitAddRecExpr(const SCEVAddRecExpr *S);
 
     Value *visitSMaxExpr(const SCEVSMaxExpr *S);
 
     Value *visitUMaxExpr(const SCEVUMaxExpr *S);
 
+    Value *visitSMinExpr(const SCEVSMinExpr *S);
+
+    Value *visitUMinExpr(const SCEVUMinExpr *S);
+
     Value *visitUnknown(const SCEVUnknown *S) {
       return S->getValue();
     }
 
     void rememberInstruction(Value *I);
 
     bool isNormalAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L);
 

llvm/trunk/include/llvm/Analysis/ScalarEvolutionExpressions.h

 class ConstantRange;
 class Loop;
 class Type;
 
   enum SCEVTypes {
     // These should be ordered in terms of increasing complexity to make the
     // folders simpler.
     scConstant, scTruncate, scZeroExtend, scSignExtend, scAddExpr, scMulExpr,
-    scUDivExpr, scAddRecExpr, scUMaxExpr, scSMaxExpr,
+    scUDivExpr, scAddRecExpr, scUMaxExpr, scSMaxExpr, scUMinExpr, scSMinExpr,
     scUnknown, scCouldNotCompute
   };
 
   /// This class represents a constant integer value.
   class SCEVConstant : public SCEV {
     friend class ScalarEvolution;
 
     ConstantInt *V;
public:
     }
 
     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 ||
+      return S->getSCEVType() == scAddExpr || S->getSCEVType() == scMulExpr ||
+             S->getSCEVType() == scSMaxExpr || S->getSCEVType() == scUMaxExpr ||
+             S->getSCEVType() == scSMinExpr || S->getSCEVType() == scUMinExpr ||
              S->getSCEVType() == scAddRecExpr;
     }
   };
 
   /// This node is the base class for n'ary commutative operators.
   class SCEVCommutativeExpr : public SCEVNAryExpr {
   protected:
     SCEVCommutativeExpr(const FoldingSetNodeIDRef ID,
                         enum SCEVTypes T, const SCEV *const *O, size_t N)
       : SCEVNAryExpr(ID, T, O, N) {}
 
   public:
     /// 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;
+      return S->getSCEVType() == scAddExpr || S->getSCEVType() == scMulExpr ||
+             S->getSCEVType() == scSMaxExpr || S->getSCEVType() == scUMaxExpr ||
+             S->getSCEVType() == scSMinExpr || S->getSCEVType() == scUMinExpr;
     }
 
     /// Set flags for a non-recurrence without clearing previously set flags.
     void setNoWrapFlags(NoWrapFlags Flags) {
       SubclassData |= Flags;
     }
   };
 
public:
     const SCEVAddRecExpr *getPostIncExpr(ScalarEvolution &SE) const;
 
     /// Methods for support type inquiry through isa, cast, and dyn_cast:
     static bool classof(const SCEV *S) {
       return S->getSCEVType() == scAddRecExpr;
     }
   };
 
-  /// This class represents a signed maximum selection.
-  class SCEVSMaxExpr : public SCEVCommutativeExpr {
+  /// This node is the base class min/max selections.
+  class SCEVMinMaxExpr : public SCEVCommutativeExpr {
     friend class ScalarEvolution;
 
-    SCEVSMaxExpr(const FoldingSetNodeIDRef ID,
+    static bool isMinMaxType(enum SCEVTypes T) {
+      return T == scSMaxExpr || T == scUMaxExpr || T == scSMinExpr ||
+             T == scUMinExpr;
+    }
+
+  protected:
+    /// Note: Constructing subclasses via this constructor is allowed
+    SCEVMinMaxExpr(const FoldingSetNodeIDRef ID, enum SCEVTypes T,
                    const SCEV *const *O, size_t N)
-      : SCEVCommutativeExpr(ID, scSMaxExpr, O, N) {
-      // Max never overflows.
+        : SCEVCommutativeExpr(ID, T, O, N) {
+      assert(isMinMaxType(T));
+      // Min and max never overflow
       setNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW));
     }
 
   public:
+    static bool classof(const SCEV *S) {
+      return isMinMaxType(static_cast<SCEVTypes>(S->getSCEVType()));
+    }
+
+    static enum SCEVTypes negate(enum SCEVTypes T) {
+      switch (T) {
+      case scSMaxExpr:
+        return scSMinExpr;
+      case scSMinExpr:
+        return scSMaxExpr;
+      case scUMaxExpr:
+        return scUMinExpr;
+      case scUMinExpr:
+        return scUMaxExpr;
+      default:
+        llvm_unreachable("Not a min or max SCEV type!");
+      }
+    }
+  };
+
+  /// This class represents a signed maximum selection.
+  class SCEVSMaxExpr : public SCEVMinMaxExpr {
+    friend class ScalarEvolution;
+
+    SCEVSMaxExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O, size_t N)
+        : SCEVMinMaxExpr(ID, scSMaxExpr, O, N) {}
+
+  public:
     /// Methods for support type inquiry through isa, cast, and dyn_cast:
     static bool classof(const SCEV *S) {
       return S->getSCEVType() == scSMaxExpr;
     }
   };
 
   /// This class represents an unsigned maximum selection.
-  class SCEVUMaxExpr : public SCEVCommutativeExpr {
+  class SCEVUMaxExpr : public SCEVMinMaxExpr {
     friend class ScalarEvolution;
 
-    SCEVUMaxExpr(const FoldingSetNodeIDRef ID,
-                 const SCEV *const *O, size_t N)
-      : SCEVCommutativeExpr(ID, scUMaxExpr, O, N) {
-      // Max never overflows.
-      setNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW));
-    }
+    SCEVUMaxExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O, size_t N)
+        : SCEVMinMaxExpr(ID, scUMaxExpr, O, N) {}
 
   public:
     /// Methods for support type inquiry through isa, cast, and dyn_cast:
     static bool classof(const SCEV *S) {
       return S->getSCEVType() == scUMaxExpr;
     }
   };
 
+  /// This class represents a signed minimum selection.
+  class SCEVSMinExpr : public SCEVMinMaxExpr {
+    friend class ScalarEvolution;
+
+    SCEVSMinExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O, size_t N)
+        : SCEVMinMaxExpr(ID, scSMinExpr, O, N) {}
+
+  public:
+    /// Methods for support type inquiry through isa, cast, and dyn_cast:
+    static bool classof(const SCEV *S) {
+      return S->getSCEVType() == scSMinExpr;
+    }
+  };
+
+  /// This class represents an unsigned minimum selection.
+  class SCEVUMinExpr : public SCEVMinMaxExpr {
+    friend class ScalarEvolution;
+
+    SCEVUMinExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O, size_t N)
+        : SCEVMinMaxExpr(ID, scUMinExpr, O, N) {}
+
+  public:
+    /// Methods for support type inquiry through isa, cast, and dyn_cast:
+    static bool classof(const SCEV *S) {
+      return S->getSCEVType() == scUMinExpr;
+    }
+  };
+
   /// 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 scUDivExpr:
         return ((SC*)this)->visitUDivExpr((const SCEVUDivExpr*)S);
       case scAddRecExpr:
         return ((SC*)this)->visitAddRecExpr((const SCEVAddRecExpr*)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 scUnknown:
         return ((SC*)this)->visitUnknown((const SCEVUnknown*)S);
       case scCouldNotCompute:
         return ((SC*)this)->visitCouldNotCompute((const SCEVCouldNotCompute*)S);
       default:
         llvm_unreachable("Unknown SCEV type!");
       }
     }
void visitAll(const SCEV *Root) {
         case scZeroExtend:
         case scSignExtend:
           push(cast<SCEVCastExpr>(S)->getOperand());
           break;
         case scAddExpr:
         case scMulExpr:
         case scSMaxExpr:
         case scUMaxExpr:
+        case scSMinExpr:
+        case scUMinExpr:
         case scAddRecExpr:
           for (const auto *Op : cast<SCEVNAryExpr>(S)->operands())
             push(Op);
           break;
         case scUDivExpr: {
           const SCEVUDivExpr *UDiv = cast<SCEVUDivExpr>(S);
           push(UDiv->getLHS());
           push(UDiv->getRHS());
const SCEV *visitUMaxExpr(const SCEVUMaxExpr *Expr) {
       bool Changed = false;
       for (auto *Op : Expr->operands()) {
         Operands.push_back(((SC*)this)->visit(Op));
         Changed |= Op != Operands.back();
       }
       return !Changed ? Expr : SE.getUMaxExpr(Operands);
     }
 
+    const SCEV *visitSMinExpr(const SCEVSMinExpr *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.getSMinExpr(Operands);
+    }
+
+    const SCEV *visitUMinExpr(const SCEVUMinExpr *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);
+    }
+
     const SCEV *visitUnknown(const SCEVUnknown *Expr) {
       return Expr;
     }
 
     const SCEV *visitCouldNotCompute(const SCEVCouldNotCompute *Expr) {
       return Expr;
     }
   };

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

if (AR->hasNoSelfWrap() &&
       OS << "nw><";
     AR->getLoop()->getHeader()->printAsOperand(OS, /*PrintType=*/false);
     OS << ">";
     return;
   }
   case scAddExpr:
   case scMulExpr:
   case scUMaxExpr:
-  case scSMaxExpr: {
+  case scSMaxExpr:
+  case scUMinExpr:
+  case scSMinExpr: {
     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;
     }
     OS << "(";
     for (SCEVNAryExpr::op_iterator I = NAry->op_begin(), E = NAry->op_end();
          I != E; ++I) {
       OS << **I;
       if (std::next(I) != E)
         OS << OpStr;
     }
Type *SCEV::getType() const {
   case scTruncate:
   case scZeroExtend:
   case scSignExtend:
     return cast<SCEVCastExpr>(this)->getType();
   case scAddRecExpr:
   case scMulExpr:
   case scUMaxExpr:
   case scSMaxExpr:
+  case scUMinExpr:
+  case scSMinExpr:
     return cast<SCEVNAryExpr>(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:
case scAddRecExpr: {
     }
     EqCacheSCEV.unionSets(LHS, RHS);
     return 0;
   }
 
   case scAddExpr:
   case scMulExpr:
   case scSMaxExpr:
-  case scUMaxExpr: {
+  case scUMaxExpr:
+  case scSMinExpr:
+  case scUMinExpr: {
     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;
 
public:
   // Except in the trivial case described above, we do not know how to divide
   // Expr by Denominator for the following functions with empty implementation.
   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 visitUnknown(const SCEVUnknown *Numerator) {}
   void visitCouldNotCompute(const SCEVCouldNotCompute *Numerator) {}
 
   void visitConstant(const SCEVConstant *Numerator) {
     if (const SCEVConstant *D = dyn_cast<SCEVConstant>(Denominator)) {
       APInt NumeratorVal = Numerator->getAPInt();
       APInt DenominatorVal = D->getAPInt();
       uint32_t NumeratorBW = NumeratorVal.getBitWidth();
if (StructType *STy = dyn_cast<StructType>(CurTy)) {
       TotalOffset = getAddExpr(TotalOffset, LocalOffset);
     }
   }
 
   // Add the total offset from all the GEP indices to the base.
   return getAddExpr(BaseExpr, TotalOffset, Wrap);
 }
 
-const SCEV *ScalarEvolution::getSMaxExpr(const SCEV *LHS,
-                                         const SCEV *RHS) {
-  SmallVector<const SCEV *, 2> Ops = {LHS, RHS};
-  return getSMaxExpr(Ops);
-}
-
 std::tuple<const SCEV *, FoldingSetNodeID, void *>
 ScalarEvolution::findExistingSCEVInCache(int SCEVType,
                                          ArrayRef<const SCEV *> Ops) {
   FoldingSetNodeID ID;
   void *IP = nullptr;
   ID.AddInteger(SCEVType);
   for (unsigned i = 0, e = Ops.size(); i != e; ++i)
     ID.AddPointer(Ops[i]);
   return std::tuple<const SCEV *, FoldingSetNodeID, void *>(
       UniqueSCEVs.FindNodeOrInsertPos(ID, IP), std::move(ID), IP);
 }
 
-const SCEV *
-ScalarEvolution::getSMaxExpr(SmallVectorImpl<const SCEV *> &Ops) {
-  assert(!Ops.empty() && "Cannot get empty smax!");
+const SCEV *ScalarEvolution::getMinMaxExpr(unsigned Kind,
+                                           SmallVectorImpl<const SCEV *> &Ops) {
+  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 &&
-           "SCEVSMaxExpr operand types don't match!");
+           "Operand types don't match!");
 #endif
 
+  bool IsSigned = Kind == scSMaxExpr || Kind == scSMinExpr;
+  bool IsMax = Kind == scSMaxExpr || Kind == scUMaxExpr;
+
   // Sort by complexity, this groups all similar expression types together.
   GroupByComplexity(Ops, &LI, DT);
 
-  // Check if we have created the same SMax expression before.
-  if (const SCEV *S = std::get<0>(findExistingSCEVInCache(scSMaxExpr, Ops))) {
+  // Check if we have created the same expression before.
+  if (const SCEV *S = std::get<0>(findExistingSCEVInCache(Kind, Ops))) {
     return S;
   }
 
   // If there are any constants, fold them together.
   unsigned Idx = 0;
   if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
     ++Idx;
     assert(Idx < Ops.size());
+    auto FoldOp = [&](const APInt &LHS, const APInt &RHS) {
+      if (Kind == scSMaxExpr)
+        return APIntOps::smax(LHS, RHS);
+      else if (Kind == scSMinExpr)
+        return APIntOps::smin(LHS, RHS);
+      else if (Kind == scUMaxExpr)
+        return APIntOps::umax(LHS, RHS);
+      else if (Kind == scUMinExpr)
+        return APIntOps::umin(LHS, RHS);
+      llvm_unreachable("Unknown SCEV min/max opcode");
+    };
+
     while (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
       // We found two constants, fold them together!
       ConstantInt *Fold = ConstantInt::get(
-          getContext(), APIntOps::smax(LHSC->getAPInt(), RHSC->getAPInt()));
+          getContext(), FoldOp(LHSC->getAPInt(), RHSC->getAPInt()));
       Ops[0] = getConstant(Fold);
       Ops.erase(Ops.begin()+1);  // Erase the folded element
       if (Ops.size() == 1) return Ops[0];
       LHSC = cast<SCEVConstant>(Ops[0]);
     }
 
-    // If we are left with a constant minimum-int, strip it off.
-    if (cast<SCEVConstant>(Ops[0])->getValue()->isMinValue(true)) {
+    bool IsMinV = LHSC->getValue()->isMinValue(IsSigned);
+    bool IsMaxV = LHSC->getValue()->isMaxValue(IsSigned);
+
+    if (IsMax ? IsMinV : IsMaxV) {
+      // If we are left with a constant minimum(/maximum)-int, strip it off.
       Ops.erase(Ops.begin());
       --Idx;
-    } else if (cast<SCEVConstant>(Ops[0])->getValue()->isMaxValue(true)) {
-      // If we have an smax with a constant maximum-int, it will always be
-      // maximum-int.
-      return Ops[0];
+    } else if (IsMax ? IsMaxV : IsMinV) {
+      // If we have a max(/min) with a constant maximum(/minimum)-int,
+      // it will always be the extremum.
+      return LHSC;
     }
 
     if (Ops.size() == 1) return Ops[0];
   }
 
-  // Find the first SMax
-  while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scSMaxExpr)
+  // Find the first operation of the same kind
+  while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < Kind)
     ++Idx;
 
-  // Check to see if one of the operands is an SMax. If so, expand its operands
-  // onto our operand list, and recurse to simplify.
+  // 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.
   if (Idx < Ops.size()) {
-    bool DeletedSMax = false;
-    while (const SCEVSMaxExpr *SMax = dyn_cast<SCEVSMaxExpr>(Ops[Idx])) {
+    bool DeletedAny = false;
+    while (Ops[Idx]->getSCEVType() == Kind) {
+      const SCEVMinMaxExpr *SMME = cast<SCEVMinMaxExpr>(Ops[Idx]);
       Ops.erase(Ops.begin()+Idx);
-      Ops.append(SMax->op_begin(), SMax->op_end());
-      DeletedSMax = true;
+      Ops.append(SMME->op_begin(), SMME->op_end());
+      DeletedAny = true;
     }
 
-    if (DeletedSMax)
-      return getSMaxExpr(Ops);
+    if (DeletedAny)
+      return getMinMaxExpr(Kind, Ops);
   }
 
   // Okay, check to see if the same value occurs in the operand list twice.  If
   // so, delete one.  Since we sorted the list, these values are required to
   // be adjacent.
-  for (unsigned i = 0, e = Ops.size()-1; i != e; ++i)
-    //  X smax Y smax Y  -->  X smax Y
-    //  X smax Y         -->  X, if X is always greater than Y
-    if (Ops[i] == Ops[i + 1] || isKnownViaNonRecursiveReasoning(
-                                    ICmpInst::ICMP_SGE, Ops[i], Ops[i + 1])) {
-      Ops.erase(Ops.begin()+i+1, Ops.begin()+i+2);
-      --i; --e;
-    } else if (isKnownViaNonRecursiveReasoning(ICmpInst::ICMP_SLE, Ops[i],
+  llvm::CmpInst::Predicate GEPred =
+      IsSigned ? ICmpInst::ICMP_SGE : ICmpInst::ICMP_UGE;
+  llvm::CmpInst::Predicate LEPred =
+      IsSigned ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_ULE;
+  llvm::CmpInst::Predicate FirstPred = IsMax ? GEPred : LEPred;
+  llvm::CmpInst::Predicate SecondPred = IsMax ? LEPred : GEPred;
+  for (unsigned i = 0, e = Ops.size() - 1; i != e; ++i) {
+    if (Ops[i] == Ops[i + 1] ||
+        isKnownViaNonRecursiveReasoning(FirstPred, Ops[i], Ops[i + 1])) {
+      //  X op Y op Y  -->  X op Y
+      //  X op Y       -->  X, if we know X, Y are ordered appropriately
+      Ops.erase(Ops.begin() + i + 1, Ops.begin() + i + 2);
+      --i;
+      --e;
+    } else if (isKnownViaNonRecursiveReasoning(SecondPred, Ops[i],
                                                Ops[i + 1])) {
-      Ops.erase(Ops.begin()+i, Ops.begin()+i+1);
-      --i; --e;
-    }
+      //  X op Y       -->  Y, if we know X, Y are ordered appropriately
+      Ops.erase(Ops.begin() + i, Ops.begin() + i + 1);
+      --i;
+      --e;
+    }
 
   if (Ops.size() == 1) return Ops[0];
 
   assert(!Ops.empty() && "Reduced smax down to nothing!");
 
-  // Okay, it looks like we really DO need an smax expr.  Check to see if we
+  // Okay, it looks like we really DO need an expr.  Check to see if we
   // already have one, otherwise create a new one.
   const SCEV *ExistingSCEV;
   FoldingSetNodeID ID;
   void *IP;
-  std::tie(ExistingSCEV, ID, IP) = findExistingSCEVInCache(scSMaxExpr, Ops);
+  std::tie(ExistingSCEV, ID, IP) = findExistingSCEVInCache(Kind, Ops);
   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) SCEVSMaxExpr(ID.Intern(SCEVAllocator), O, Ops.size());
+  SCEV *S = new (SCEVAllocator) SCEVMinMaxExpr(
+      ID.Intern(SCEVAllocator), static_cast<SCEVTypes>(Kind), O, Ops.size());
+
   UniqueSCEVs.InsertNode(S, IP);
   addToLoopUseLists(S);
   return S;
 }
 
-const SCEV *ScalarEvolution::getUMaxExpr(const SCEV *LHS,
-                                         const SCEV *RHS) {
+const SCEV *ScalarEvolution::getSMaxExpr(const SCEV *LHS, const SCEV *RHS) {
   SmallVector<const SCEV *, 2> Ops = {LHS, RHS};
-  return getUMaxExpr(Ops);
-}
-
-const SCEV *
-ScalarEvolution::getUMaxExpr(SmallVectorImpl<const SCEV *> &Ops) {
-  assert(!Ops.empty() && "Cannot get empty umax!");
-  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 &&
-           "SCEVUMaxExpr operand types don't match!");
-#endif
-
-  // Sort by complexity, this groups all similar expression types together.
-  GroupByComplexity(Ops, &LI, DT);
-
-  // Check if we have created the same UMax expression before.
-  if (const SCEV *S = std::get<0>(findExistingSCEVInCache(scUMaxExpr, Ops))) {
-    return S;
-  }
-
-  // If there are any constants, fold them together.
-  unsigned Idx = 0;
-  if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
-    ++Idx;
-    assert(Idx < Ops.size());
-    while (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
-      // We found two constants, fold them together!
-      ConstantInt *Fold = ConstantInt::get(
-          getContext(), APIntOps::umax(LHSC->getAPInt(), RHSC->getAPInt()));
-      Ops[0] = getConstant(Fold);
-      Ops.erase(Ops.begin()+1);  // Erase the folded element
-      if (Ops.size() == 1) return Ops[0];
-      LHSC = cast<SCEVConstant>(Ops[0]);
-    }
-
-    // If we are left with a constant minimum-int, strip it off.
-    if (cast<SCEVConstant>(Ops[0])->getValue()->isMinValue(false)) {
-      Ops.erase(Ops.begin());
-      --Idx;
-    } else if (cast<SCEVConstant>(Ops[0])->getValue()->isMaxValue(false)) {
-      // If we have an umax with a constant maximum-int, it will always be
-      // maximum-int.
-      return Ops[0];
-    }
+  return getSMaxExpr(Ops);
 
-    if (Ops.size() == 1) return Ops[0];
-  }
+const SCEV *ScalarEvolution::getSMaxExpr(SmallVectorImpl<const SCEV *> &Ops) {
+  return getMinMaxExpr(scSMaxExpr, Ops);
 
-  // Find the first UMax
-  while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scUMaxExpr)
-    ++Idx;
-
-  // Check to see if one of the operands is a UMax. If so, expand its operands
-  // onto our operand list, and recurse to simplify.
-  if (Idx < Ops.size()) {
-    bool DeletedUMax = false;
-    while (const SCEVUMaxExpr *UMax = dyn_cast<SCEVUMaxExpr>(Ops[Idx])) {
-      Ops.erase(Ops.begin()+Idx);
-      Ops.append(UMax->op_begin(), UMax->op_end());
-      DeletedUMax = true;
-    }
-
-    if (DeletedUMax)
-      return getUMaxExpr(Ops);
-  }
+const SCEV *ScalarEvolution::getUMaxExpr(const SCEV *LHS, const SCEV *RHS) {
+  SmallVector<const SCEV *, 2> Ops = {LHS, RHS};
 
-  // Okay, check to see if the same value occurs in the operand list twice.  If
-  // so, delete one.  Since we sorted the list, these values are required to
-  // be adjacent.
-  for (unsigned i = 0, e = Ops.size()-1; i != e; ++i)
-    //  X umax Y umax Y  -->  X umax Y
-    //  X umax Y         -->  X, if X is always greater than Y
-    if (Ops[i] == Ops[i + 1] || isKnownViaNonRecursiveReasoning(
-                                    ICmpInst::ICMP_UGE, Ops[i], Ops[i + 1])) {
-      Ops.erase(Ops.begin() + i + 1, Ops.begin() + i + 2);
-      --i; --e;
-    } else if (isKnownViaNonRecursiveReasoning(ICmpInst::ICMP_ULE, Ops[i],
-                                               Ops[i + 1])) {
-      Ops.erase(Ops.begin() + i, Ops.begin() + i + 1);
-      --i; --e;
-    }
-
-  if (Ops.size() == 1) return Ops[0];
-
-  assert(!Ops.empty() && "Reduced umax down to nothing!");
-
-  // Okay, it looks like we really DO need a umax expr.  Check to see if we
-  // already have one, otherwise create a new one.
-  const SCEV *ExistingSCEV;
-  FoldingSetNodeID ID;
-  void *IP;
-  std::tie(ExistingSCEV, ID, IP) = findExistingSCEVInCache(scUMaxExpr, Ops);
-  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) SCEVUMaxExpr(ID.Intern(SCEVAllocator),
-                                             O, Ops.size());
-  UniqueSCEVs.InsertNode(S, IP);
-  addToLoopUseLists(S);
-  return S;
+const SCEV *ScalarEvolution::getUMaxExpr(SmallVectorImpl<const SCEV *> &Ops) {
+  return getMinMaxExpr(scUMaxExpr, Ops);
 }
 
 const SCEV *ScalarEvolution::getSMinExpr(const SCEV *LHS,
                                          const SCEV *RHS) {
   SmallVector<const SCEV *, 2> Ops = { LHS, RHS };
   return getSMinExpr(Ops);
 }
 
 const SCEV *ScalarEvolution::getSMinExpr(SmallVectorImpl<const SCEV *> &Ops) {
-  // ~smax(~x, ~y, ~z) == smin(x, y, z).
-  SmallVector<const SCEV *, 2> NotOps;
-  for (auto *S : Ops)
-    NotOps.push_back(getNotSCEV(S));
-  return getNotSCEV(getSMaxExpr(NotOps));
+  return getMinMaxExpr(scSMinExpr, Ops);
 }
 
 const SCEV *ScalarEvolution::getUMinExpr(const SCEV *LHS,
                                          const SCEV *RHS) {
   SmallVector<const SCEV *, 2> Ops = { LHS, RHS };
   return getUMinExpr(Ops);
 }
 
 const SCEV *ScalarEvolution::getUMinExpr(SmallVectorImpl<const SCEV *> &Ops) {
-  assert(!Ops.empty() && "At least one operand must be!");
-  // Trivial case.
-  if (Ops.size() == 1)
-    return Ops[0];
-
-  // ~umax(~x, ~y, ~z) == umin(x, y, z).
-  SmallVector<const SCEV *, 2> NotOps;
-  for (auto *S : Ops)
-    NotOps.push_back(getNotSCEV(S));
-  return getNotSCEV(getUMaxExpr(NotOps));
+  return getMinMaxExpr(scUMinExpr, Ops);
 }
 
 const SCEV *ScalarEvolution::getSizeOfExpr(Type *IntTy, Type *AllocTy) {
   // We can bypass creating a target-independent
   // constant expression and then folding it back into a ConstantInt.
   // This is just a compile-time optimization.
   return getConstant(IntTy, getDataLayout().getTypeAllocSize(AllocTy));
 }
return getConstant(
                cast<ConstantInt>(ConstantExpr::getNeg(VC->getValue())));
 
   Type *Ty = V->getType();
   Ty = getEffectiveSCEVType(Ty);
   return getMulExpr(
       V, getConstant(cast<ConstantInt>(Constant::getAllOnesValue(Ty))), Flags);
 }
 
+/// If Expr computes ~A, return A else return nullptr
+static const SCEV *MatchNotExpr(const SCEV *Expr) {
+  const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Expr);
+  if (!Add || Add->getNumOperands() != 2 ||
+      !Add->getOperand(0)->isAllOnesValue())
+    return nullptr;
+
+  const SCEVMulExpr *AddRHS = dyn_cast<SCEVMulExpr>(Add->getOperand(1));
+  if (!AddRHS || AddRHS->getNumOperands() != 2 ||
+      !AddRHS->getOperand(0)->isAllOnesValue())
+    return nullptr;
+
+  return AddRHS->getOperand(1);
+}
+
 /// Return a SCEV corresponding to ~V = -1-V
 const SCEV *ScalarEvolution::getNotSCEV(const SCEV *V) {
   if (const SCEVConstant *VC = dyn_cast<SCEVConstant>(V))
     return getConstant(
                 cast<ConstantInt>(ConstantExpr::getNot(VC->getValue())));
 
+  // Fold ~(u|s)(min|max)(~x, ~y) to (u|s)(max|min)(x, y)
+  if (const SCEVMinMaxExpr *MME = dyn_cast<SCEVMinMaxExpr>(V)) {
+    auto MatchMinMaxNegation = [&](const SCEVMinMaxExpr *MME) {
+      SmallVector<const SCEV *, 2> MatchedOperands;
+      for (const SCEV *Operand : MME->operands()) {
+        const SCEV *Matched = MatchNotExpr(Operand);
+        if (!Matched)
+          return (const SCEV *)nullptr;
+        MatchedOperands.push_back(Matched);
+      }
+      return getMinMaxExpr(
+          SCEVMinMaxExpr::negate(static_cast<SCEVTypes>(MME->getSCEVType())),
+          MatchedOperands);
+    };
+    if (const SCEV *Replaced = MatchMinMaxNegation(MME))
+      return Replaced;
+  }
+
   Type *Ty = V->getType();
   Ty = getEffectiveSCEVType(Ty);
   const SCEV *AllOnes =
                    getConstant(cast<ConstantInt>(Constant::getAllOnesValue(Ty)));
   return getMinusSCEV(AllOnes, V);
 }
 
 const SCEV *ScalarEvolution::getMinusSCEV(const SCEV *LHS, const SCEV *RHS,
bool setUnavailable() {
       Available = false;
       return false;
     }
 
     bool follow(const SCEV *S) {
       switch (S->getSCEVType()) {
       case scConstant: case scTruncate: case scZeroExtend: case scSignExtend:
       case scAddExpr: case scMulExpr: case scUMaxExpr: case scSMaxExpr:
+      case scUMinExpr:
+      case scSMinExpr:
         // 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
case scUDivExpr: {
       if (Constant *LHS = BuildConstantFromSCEV(SU->getLHS()))
         if (Constant *RHS = BuildConstantFromSCEV(SU->getRHS()))
           if (LHS->getType() == RHS->getType())
             return ConstantExpr::getUDiv(LHS, RHS);
       break;
     }
     case scSMaxExpr:
     case scUMaxExpr:
-      break; // TODO: smax, umax.
+    case scSMinExpr:
+    case scUMinExpr:
+      break; // TODO: smax, umax, smin, umax.
   }
   return nullptr;
 }
 
 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
for (unsigned i = 0, e = Comm->getNumOperands(); i != e; ++i) {
         for (++i; i != e; ++i) {
           OpAtScope = getSCEVAtScope(Comm->getOperand(i), L);
           NewOps.push_back(OpAtScope);
         }
         if (isa<SCEVAddExpr>(Comm))
           return getAddExpr(NewOps);
         if (isa<SCEVMulExpr>(Comm))
           return getMulExpr(NewOps);
-        if (isa<SCEVSMaxExpr>(Comm))
-          return getSMaxExpr(NewOps);
-        if (isa<SCEVUMaxExpr>(Comm))
-          return getUMaxExpr(NewOps);
+        if (isa<SCEVMinMaxExpr>(Comm))
+          return getMinMaxExpr(Comm->getSCEVType(), NewOps);
         llvm_unreachable("Unknown commutative SCEV type!");
       }
     }
     // If we got here, all operands are loop invariant.
     return Comm;
   }
 
   if (const SCEVUDivExpr *Div = dyn_cast<SCEVUDivExpr>(V)) {
bool ScalarEvolution::isImpliedCondOperands(ICmpInst::Predicate Pred,
   return isImpliedCondOperandsHelper(Pred, LHS, RHS,
                                      FoundLHS, FoundRHS) ||
          // ~x < ~y --> x > y
          isImpliedCondOperandsHelper(Pred, LHS, RHS,
                                      getNotSCEV(FoundRHS),
                                      getNotSCEV(FoundLHS));
 }
 
-/// If Expr computes ~A, return A else return nullptr
-static const SCEV *MatchNotExpr(const SCEV *Expr) {
-  const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Expr);
-  if (!Add || Add->getNumOperands() != 2 ||
-      !Add->getOperand(0)->isAllOnesValue())
-    return nullptr;
-
-  const SCEVMulExpr *AddRHS = dyn_cast<SCEVMulExpr>(Add->getOperand(1));
-  if (!AddRHS || AddRHS->getNumOperands() != 2 ||
-      !AddRHS->getOperand(0)->isAllOnesValue())
-    return nullptr;
-
-  return AddRHS->getOperand(1);
-}
-
-/// Is MaybeMaxExpr an SMax or UMax of Candidate and some other values?
-template<typename MaxExprType>
-static bool IsMaxConsistingOf(const SCEV *MaybeMaxExpr,
-                              const SCEV *Candidate) {
-  const MaxExprType *MaxExpr = dyn_cast<MaxExprType>(MaybeMaxExpr);
-  if (!MaxExpr) return false;
-
-  return find(MaxExpr->operands(), Candidate) != MaxExpr->op_end();
-}
-
-/// Is MaybeMinExpr an SMin or UMin of Candidate and some other values?
-template<typename MaxExprType>
-static bool IsMinConsistingOf(ScalarEvolution &SE,
-                              const SCEV *MaybeMinExpr,
+/// Is MaybeMinMaxExpr an (U|S)(Min|Max) of Candidate and some other values?
+template <typename MinMaxExprType>
+static bool IsMinMaxConsistingOf(const SCEV *MaybeMinMaxExpr,
                                  const SCEV *Candidate) {
-  const SCEV *MaybeMaxExpr = MatchNotExpr(MaybeMinExpr);
-  if (!MaybeMaxExpr)
+  const MinMaxExprType *MinMaxExpr = dyn_cast<MinMaxExprType>(MaybeMinMaxExpr);
+  if (!MinMaxExpr)
     return false;
 
-  return IsMaxConsistingOf<MaxExprType>(MaybeMaxExpr, SE.getNotSCEV(Candidate));
+  return find(MinMaxExpr->operands(), Candidate) != MinMaxExpr->op_end();
 }
 
 static bool IsKnownPredicateViaAddRecStart(ScalarEvolution &SE,
                                            ICmpInst::Predicate Pred,
                                            const SCEV *LHS, const SCEV *RHS) {
   // If both sides are affine addrecs for the same loop, with equal
   // steps, and we know the recurrences don't wrap, then we only
   // need to check the predicate on the starting values.
static bool IsKnownPredicateViaMinOrMax(ScalarEvolution &SE,
   default:
     return false;
 
   case ICmpInst::ICMP_SGE:
     std::swap(LHS, RHS);
     LLVM_FALLTHROUGH;
   case ICmpInst::ICMP_SLE:
     return
         // min(A, ...) <= A
-      IsMinConsistingOf<SCEVSMaxExpr>(SE, LHS, RHS) ||
+        IsMinMaxConsistingOf<SCEVSMinExpr>(LHS, RHS) ||
         // A <= max(A, ...)
-      IsMaxConsistingOf<SCEVSMaxExpr>(RHS, LHS);
+        IsMinMaxConsistingOf<SCEVSMaxExpr>(RHS, LHS);
 
   case ICmpInst::ICMP_UGE:
     std::swap(LHS, RHS);
     LLVM_FALLTHROUGH;
   case ICmpInst::ICMP_ULE:
     return
         // min(A, ...) <= A
-      IsMinConsistingOf<SCEVUMaxExpr>(SE, LHS, RHS) ||
+        IsMinMaxConsistingOf<SCEVUMinExpr>(LHS, RHS) ||
         // A <= max(A, ...)
-      IsMaxConsistingOf<SCEVUMaxExpr>(RHS, LHS);
+        IsMinMaxConsistingOf<SCEVUMaxExpr>(RHS, LHS);
   }
 
   llvm_unreachable("covered switch fell through?!");
 }
 
 bool ScalarEvolution::isImpliedViaOperations(ICmpInst::Predicate Pred,
                                              const SCEV *LHS, const SCEV *RHS,
                                              const SCEV *FoundLHS,
for (auto *Op : AR->operands())
         return LoopVariant;
 
     // Otherwise it's loop-invariant.
     return LoopInvariant;
   }
   case scAddExpr:
   case scMulExpr:
   case scUMaxExpr:
-  case scSMaxExpr: {
+  case scSMaxExpr:
+  case scUMinExpr:
+  case scSMinExpr: {
     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;
     }
if (!DT.dominates(AR->getLoop()->getHeader(), BB))
       return DoesNotDominateBlock;
 
     // Fall through into SCEVNAryExpr handling.
     LLVM_FALLTHROUGH;
   }
   case scAddExpr:
   case scMulExpr:
   case scUMaxExpr:
-  case scSMaxExpr: {
+  case scSMaxExpr:
+  case scUMinExpr:
+  case scSMinExpr: {
     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/trunk/lib/Analysis/ScalarEvolutionExpander.cpp

 }
 
 Value *SCEVExpander::visitSMaxExpr(const SCEVSMaxExpr *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.
-    if (S->getOperand(i)->getType() != Ty) {
+    Type *OpTy = S->getOperand(i)->getType();
+    if (OpTy->isIntegerTy() != Ty->isIntegerTy()) {
       Ty = SE.getEffectiveSCEVType(Ty);
       LHS = InsertNoopCastOfTo(LHS, Ty);
     }
     Value *RHS = expandCodeFor(S->getOperand(i), Ty);
     Value *ICmp = Builder.CreateICmpSGT(LHS, RHS);
     rememberInstruction(ICmp);
     Value *Sel = Builder.CreateSelect(ICmp, LHS, RHS, "smax");
     rememberInstruction(Sel);
     LHS = Sel;
   }
   // 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 *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.
-    if (S->getOperand(i)->getType() != Ty) {
+    Type *OpTy = S->getOperand(i)->getType();
+    if (OpTy->isIntegerTy() != Ty->isIntegerTy()) {
       Ty = SE.getEffectiveSCEVType(Ty);
       LHS = InsertNoopCastOfTo(LHS, Ty);
     }
     Value *RHS = expandCodeFor(S->getOperand(i), Ty);
     Value *ICmp = Builder.CreateICmpUGT(LHS, RHS);
     rememberInstruction(ICmp);
     Value *Sel = Builder.CreateSelect(ICmp, LHS, RHS, "umax");
     rememberInstruction(Sel);
     LHS = Sel;
   }
   // 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 *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);
+      LHS = InsertNoopCastOfTo(LHS, Ty);
+    }
+    Value *RHS = expandCodeFor(S->getOperand(i), Ty);
+    Value *ICmp = Builder.CreateICmpSLT(LHS, RHS);
+    rememberInstruction(ICmp);
+    Value *Sel = Builder.CreateSelect(ICmp, LHS, RHS, "smin");
+    rememberInstruction(Sel);
+    LHS = Sel;
+  }
+  // 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 *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);
+      LHS = InsertNoopCastOfTo(LHS, Ty);
+    }
+    Value *RHS = expandCodeFor(S->getOperand(i), Ty);
+    Value *ICmp = Builder.CreateICmpULT(LHS, RHS);
+    rememberInstruction(ICmp);
+    Value *Sel = Builder.CreateSelect(ICmp, LHS, RHS, "umin");
+    rememberInstruction(Sel);
+    LHS = Sel;
+  }
+  // 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::expandCodeFor(const SCEV *SH, Type *Ty,
                                    Instruction *IP) {
   setInsertPoint(IP);
   return expandCodeFor(SH, Ty);
 }
 
 Value *SCEVExpander::expandCodeFor(const SCEV *SH, Type *Ty) {
   // Expand the code for this SCEV.
for (Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock());;
           InsertPt = &*std::next(InsertPt->getIterator());
         break;
       }
     }
   }
 
   // IndVarSimplify sometimes sets the insertion point at the block start, even
   // when there are PHIs at that point.  We must correct for this.
-  if (isa<PHINode>(*InsertPt)) 
+  if (isa<PHINode>(*InsertPt))
     InsertPt = &*InsertPt->getParent()->getFirstInsertionPt();
 
   // Check to see if we already expanded this here.
   auto I = InsertedExpressions.find(std::make_pair(S, InsertPt));
   if (I != InsertedExpressions.end())
     return I->second;
 
   SCEVInsertPointGuard Guard(Builder, this);
if (!At)
       At = &ExitingBB->back();
     if (!getRelatedExistingExpansion(
             SE.getAddExpr(S, SE.getConstant(S->getType(), 1)), At, L))
       return true;
   }
 
   // HowManyLessThans uses a Max expression whenever the loop is not guarded by
   // the exit condition.
-  if (isa<SCEVSMaxExpr>(S) || isa<SCEVUMaxExpr>(S))
+  if (isa<SCEVMinMaxExpr>(S))
     return true;
 
   // Recurse past nary expressions, which commonly occur in the
   // BackedgeTakenCount. They may already exist in program code, and if not,
   // they are not too expensive rematerialize.
   if (const SCEVNAryExpr *NAry = dyn_cast<SCEVNAryExpr>(S)) {
     for (auto *Op : NAry->operands())
       if (isHighCostExpansionHelper(Op, L, At, Processed))

llvm/trunk/test/Analysis/LoopAccessAnalysis/memcheck-ni.ll

+; RUN: opt -loop-versioning -S < %s | FileCheck %s
+
+; NB: addrspaces 10-13 are non-integral
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128-ni:10:11:12:13"
+
+%jl_value_t = type opaque
+%jl_array_t = type { i8 addrspace(13)*, i64, i16, i16, i32 }
+
+define void @"japi1_permutedims!_33509"(%jl_value_t addrspace(10)**) {
+; CHECK: [[CMP:%[^ ]*]] = icmp ult double addrspace(13)* [[A:%[^ ]*]], [[B:%[^ ]*]]
+; CHECK: [[SELECT:%[^ ]*]] = select i1 %18, double addrspace(13)* [[A]], double addrspace(13)* [[B]]
+top:
+  %1 = alloca [3 x i64], align 8 
+  %2 = load %jl_value_t addrspace(10)*, %jl_value_t addrspace(10)** %0, align 8
+  %3 = getelementptr inbounds %jl_value_t addrspace(10)*, %jl_value_t addrspace(10)** %0, i64 1
+  %4 = load %jl_value_t addrspace(10)*, %jl_value_t addrspace(10)** %3, align 8
+  %5 = getelementptr inbounds [3 x i64], [3 x i64]* %1, i64 0, i64 0
+  store i64 1, i64* %5, align 8
+  %6 = getelementptr inbounds [3 x i64], [3 x i64]* %1, i64 0, i64 1
+  %7 = load i64, i64* inttoptr (i64 24 to i64*), align 8
+  %8 = addrspacecast %jl_value_t addrspace(10)* %4 to %jl_value_t addrspace(11)*
+  %9 = bitcast %jl_value_t addrspace(11)* %8 to double addrspace(13)* addrspace(11)*
+  %10 = load double addrspace(13)*, double addrspace(13)* addrspace(11)* %9, align 8
+  %11 = addrspacecast %jl_value_t addrspace(10)* %2 to %jl_value_t addrspace(11)*
+  %12 = bitcast %jl_value_t addrspace(11)* %11 to double addrspace(13)* addrspace(11)*
+  %13 = load double addrspace(13)*, double addrspace(13)* addrspace(11)* %12, align 8
+  %14 = load i64, i64* %6, align 8
+  br label %L74
+
+L74:
+  %value_phi20 = phi i64 [ 1, %top ], [ %22, %L74 ]
+  %value_phi21 = phi i64 [ 1, %top ], [ %23, %L74 ]
+  %value_phi22 = phi i64 [ 1, %top ], [ %25, %L74 ]
+  %15 = add i64 %value_phi21, -1
+  %16 = getelementptr inbounds double, double addrspace(13)* %10, i64 %15
+  %17 = bitcast double addrspace(13)* %16 to i64 addrspace(13)*
+  %18 = load i64, i64 addrspace(13)* %17, align 8
+  %19 = add i64 %value_phi20, -1
+  %20 = getelementptr inbounds double, double addrspace(13)* %13, i64 %19
+  %21 = bitcast double addrspace(13)* %20 to i64 addrspace(13)*
+  store i64 %18, i64 addrspace(13)* %21, align 8
+  %22 = add i64 %value_phi20, 1
+  %23 = add i64 %14, %value_phi21
+  %24 = icmp eq i64 %value_phi22, %7
+  %25 = add i64 %value_phi22, 1
+  br i1 %24, label %L94, label %L74
+
+L94:
+  ret void 
+}

llvm/trunk/test/Analysis/LoopAccessAnalysis/reverse-memcheck-bounds.ll

 ; the interval limits.
 
 ;   for (i = 0; i < 10000; i++) {
 ;     B[i] = A[15000 - step * i] * 3;
 ;   }
 
 ; Here it is not obvious what the limits are, since 'step' could be negative.
 
-; CHECK: Low: (-1 + (-1 * ((-60001 + (-1 * %a)) umax (-60001 + (40000 * %step) + (-1 * %a)))))
+; CHECK: Low: ((60000 + %a)<nsw> umin (60000 + (-40000 * %step) + %a)) 
 ; CHECK: High: (4 + ((60000 + %a)<nsw> umax (60000 + (-40000 * %step) + %a)))
 
 define void @g(i64 %step) {
 entry:
   %a = load i32*, i32** @A, align 8
   %b = load i32*, i32** @B, align 8
   br label %for.body
 

llvm/trunk/test/Analysis/ScalarEvolution/2008-07-29-SMinExpr.ll

forinc:   ; preds = %forinc, %entry
   %cmp5 = icmp sgt i32 %dec, %cond
   br i1 %cmp5, label %forinc, label %afterfor
 
 afterfor:   ; preds = %forinc, %entry
   %j.0.lcssa = phi i32 [ -2147483632, %entry ], [ %dec, %forinc ]
   ret i32 %j.0.lcssa
 }
 
-; CHECK: backedge-taken count is (-2147483632 + ((-1 + (-1 * %{{[xy]}})) smax (-1 + (-1 * %{{[xy]}}))))
+; CHECK: backedge-taken count is (-2147483633 + (-1 * (%{{[xy]}} smin %{{[xy]}})))
 

llvm/trunk/test/Analysis/ScalarEvolution/max-expr-cache.ll

bb4:
   %tmp40 = select i1 %tmp39, i32 %tmp38, i32 256
   %tmp41 = add nsw i32 %tmp40, 1
   %tmp42 = icmp sgt i32 %tmp8, %tmp41
   %tmp43 = select i1 %tmp42, i32 %tmp41, i32 %tmp8
   %tmp44 = add nsw i32 %tmp10, 7
   %tmp45 = icmp slt i32 %tmp43, 256
   %tmp46 = select i1 %tmp45, i32 %tmp43, i32 256
 ; CHECK:  %tmp46 = select i1 %tmp45, i32 %tmp43, i32 256
-; CHECK-NEXT:  -->  (-1 + (-1 * (-257 smax (-1 + (-257 smax (-1 + (-257 smax (-1 + (-257 smax (-1 + (-257 smax (-1 + (-257 smax (-1 + (-257 smax (-1 + (-257 smax {(-1 + (-1 * %tmp3)),+,256}<%bb4>))<nsw> smax {(-1 + (-1 * %tmp3)),+,256}<%bb4>))<nsw> smax {(-1 + (-1 * %tmp3)),+,256}<%bb4>))<nsw> smax {(-1 + (-1 * %tmp3)),+,256}<%bb4>))<nsw> smax {(-1 + (-1 * %tmp3)),+,256}<%bb4>))<nsw> smax {(-1 + (-1 * %tmp3)),+,256}<%bb4>))<nsw> smax {(-1 + (-1 * %tmp3)),+,256}<%bb4>))<nsw> smax {(-1 + (-1 * %tmp3)),+,256}<%bb4>))<nsw>)<nsw>
+; CHECK-NEXT:  -->  (256 smin (1 + (256 smin (1 + (256 smin (1 + (256 smin (1 + (256 smin (1 + (256 smin (1 + (256 smin (1 + (256 smin {%tmp3,+,-256}<%bb4>)) smin {%tmp3,+,-256}<%bb4>)) smin {%tmp3,+,-256}<%bb4>)) smin {%tmp3,+,-256}<%bb4>)) smin {%tmp3,+,-256}<%bb4>)) smin {%tmp3,+,-256}<%bb4>)) smin {%tmp3,+,-256}<%bb4>)) smin {%tmp3,+,-256}<%bb4>)
   %tmp47 = icmp sgt i32 %tmp44, %tmp46
   %tmp48 = select i1 %tmp47, i32 %tmp44, i32 %tmp46
   %tmp49 = ashr i32 %tmp48, 3
   %tmp50 = icmp sgt i32 %tmp49, 0
   %tmp51 = select i1 %tmp50, i32 %tmp49, i32 0
   %tmp52 = zext i32 %tmp51 to i64
   br label %bb53
 
bb4:
   %tmp40 = select i1 %tmp39, i32 %tmp38, i32 256
   %tmp41 = add nsw i32 %tmp40, 1
   %tmp42 = icmp ugt i32 %tmp8, %tmp41
   %tmp43 = select i1 %tmp42, i32 %tmp41, i32 %tmp8
   %tmp44 = add nsw i32 %tmp10, 7
   %tmp45 = icmp ult i32 %tmp43, 256
   %tmp46 = select i1 %tmp45, i32 %tmp43, i32 256
 ; CHECK:  %tmp46 = select i1 %tmp45, i32 %tmp43, i32 256
-; CHECK-NEXT:  -->  (-1 + (-1 * (-257 umax (-1 + (-257 umax (-1 + (-257 umax (-1 + (-257 umax (-1 + (-257 umax (-1 + (-257 umax (-1 + (-257 umax (-1 + (-257 umax {(-1 + (-1 * %tmp3)),+,256}<%bb4>))<nsw> umax {(-1 + (-1 * %tmp3)),+,256}<%bb4>))<nsw> umax {(-1 + (-1 * %tmp3)),+,256}<%bb4>))<nsw> umax {(-1 + (-1 * %tmp3)),+,256}<%bb4>))<nsw> umax {(-1 + (-1 * %tmp3)),+,256}<%bb4>))<nsw> umax {(-1 + (-1 * %tmp3)),+,256}<%bb4>))<nsw> umax {(-1 + (-1 * %tmp3)),+,256}<%bb4>))<nsw> umax {(-1 + (-1 * %tmp3)),+,256}<%bb4>))<nsw>)<nsw>  
+; CHECK-NEXT:  --> (256 umin (1 + (256 umin (1 + (256 umin (1 + (256 umin (1 + (256 umin (1 + (256 umin (1 + (256 umin (1 + (256 umin {%tmp3,+,-256}<%bb4>)) umin {%tmp3,+,-256}<%bb4>)) umin {%tmp3,+,-256}<%bb4>)) umin {%tmp3,+,-256}<%bb4>)) umin {%tmp3,+,-256}<%bb4>)) umin {%tmp3,+,-256}<%bb4>)) umin {%tmp3,+,-256}<%bb4>)) umin {%tmp3,+,-256}<%bb4>) 
   %tmp47 = icmp ugt i32 %tmp44, %tmp46
   %tmp48 = select i1 %tmp47, i32 %tmp44, i32 %tmp46
   %tmp49 = ashr i32 %tmp48, 3
   %tmp50 = icmp ugt i32 %tmp49, 0
   %tmp51 = select i1 %tmp50, i32 %tmp49, i32 0
   %tmp52 = zext i32 %tmp51 to i64
   br label %bb53
 

llvm/trunk/test/Analysis/ScalarEvolution/min-max-exprs.ll

 bb2:                                              ; preds = %bb1
   %tmp3 = add nuw nsw i32 %i.0, 3
   %tmp4 = icmp slt i32 %tmp3, %N
   %tmp5 = sext i32 %tmp3 to i64
   %tmp6 = sext i32 %N to i64
   %tmp9 = select i1 %tmp4, i64 %tmp5, i64 %tmp6
 ;                  min(N, i+3)
 ; CHECK:           select i1 %tmp4, i64 %tmp5, i64 %tmp6
-; CHECK-NEXT:  --> (-1 + (-1 * ((-1 + (-1 * (sext i32 {3,+,1}<nuw><%bb1> to i64))<nsw>)<nsw> smax (-1 + (-1 * (sext i32 %N to i64))<nsw>)<nsw>))<nsw>)<nsw>
+; CHECK-NEXT:  --> ((sext i32 {3,+,1}<nuw><%bb1> to i64) smin (sext i32 %N to i64))
   %tmp11 = getelementptr inbounds i32, i32* %A, i64 %tmp9
   %tmp12 = load i32, i32* %tmp11, align 4
   %tmp13 = shl nsw i32 %tmp12, 1
   %tmp14 = icmp sge i32 3, %i.0
   %tmp17 = add nsw i64 %i.0.1, -3
   %tmp19 = select i1 %tmp14, i64 0, i64 %tmp17
 ;                  max(0, i - 3)
 ; CHECK:           select i1 %tmp14, i64 0, i64 %tmp17

llvm/trunk/test/Analysis/ScalarEvolution/predicated-trip-count.ll

 ; true.
 
 ; CHECK: Classifying expressions for: @test2
 
 ; CHECK:      %i.0.ext = sext i16 %i.0 to i32
 ; CHECK-NEXT:    -->  (sext i16 {%Start,+,-1}<%bb3> to i32)
 ; CHECK:       Loop %bb3: Unpredictable backedge-taken count.
 ; CHECK-NEXT:  Loop %bb3: Unpredictable max backedge-taken count.
-; CHECK-NEXT:  Loop %bb3: Predicated backedge-taken count is (2 + (sext i16 %Start to i32) + ((-2 + (-1 * (sext i16 %Start to i32))<nsw>) smax (-1 + (-1 * %M))))
+; CHECK-NEXT:  Loop %bb3: Predicated backedge-taken count is (1 + (sext i16 %Start to i32) + (-1 * ((1 + (sext i16 %Start to i32))<nsw> smin %M)))
 ; CHECK-NEXT:  Predicates:
 ; CHECK-NEXT:    {%Start,+,-1}<%bb3> Added Flags: <nssw>
 
 define void @test2(i32 %N, i32 %M, i16 %Start) {
 entry:
         br label %bb3
 
 bb:             ; preds = %bb3

llvm/trunk/test/Analysis/ScalarEvolution/trip-count14.ll

 if.end:
   %arrayidx = getelementptr i32, i32* %p, i32 %i.0
   store i32 %i.0, i32* %arrayidx, align 4
   %inc = add i32 %i.0, 1
   %cmp1 = icmp slt i32 %i.0, %add
   br i1 %cmp1, label %do.body, label %do.end ; taken either 0 or 2 times
 
 ; CHECK-LABEL: Determining loop execution counts for: @s32_max2_unpredictable_exit
-; CHECK-NEXT: Loop %do.body: <multiple exits> backedge-taken count is (-1 + (-1 * ((-1 + (-1 * ((2 + %n) smax %n)) + %n) umax (-1 + (-1 * %x) + %n))))
+; CHECK-NEXT: Loop %do.body: <multiple exits> backedge-taken count is (((-1 * %n) + ((2 + %n) smax %n)) umin ((-1 * %n) + %x))
 ; CHECK-NEXT: Loop %do.body: max backedge-taken count is 2{{$}}
 
 do.end:
   ret void
 }
 
 define void @u32_max1(i32 %n, i32* %p) {
 entry:

 if.end:
   %arrayidx = getelementptr i32, i32* %p, i32 %i.0
   store i32 %i.0, i32* %arrayidx, align 4
   %inc = add i32 %i.0, 1
   %cmp1 = icmp ult i32 %i.0, %add
   br i1 %cmp1, label %do.body, label %do.end ; taken either 0 or 2 times
 
 ; CHECK-LABEL: Determining loop execution counts for: @u32_max2_unpredictable_exit
-; CHECK-NEXT: Loop %do.body: <multiple exits> backedge-taken count is (-1 + (-1 * ((-1 + (-1 * ((2 + %n) umax %n)) + %n) umax (-1 + (-1 * %x) + %n))))
+; CHECK-NEXT: Loop %do.body: <multiple exits> backedge-taken count is (((-1 * %n) + ((2 + %n) umax %n)) umin ((-1 * %n) + %x))
 ; CHECK-NEXT: Loop %do.body: max backedge-taken count is 2{{$}}
 
 do.end:
   ret void
 }

llvm/trunk/test/Analysis/ScalarEvolution/trip-count3.ll

 ; RUN: opt < %s -scalar-evolution -analyze | FileCheck %s
 
 ; ScalarEvolution can't compute a trip count because it doesn't know if
 ; dividing by the stride will have a remainder. This could theoretically
 ; be teaching it how to use a more elaborate trip count computation.
 
-; CHECK: Loop %bb3.i: backedge-taken count is ((64 + (-64 smax (-1 + (-1 * %0))) + %0) /u 64)
+; CHECK: Loop %bb3.i: backedge-taken count is ((63 + (-1 * (63 smin %0)) + %0) /u 64)
 ; CHECK: Loop %bb3.i: max backedge-taken count is 33554431
 
 %struct.FILE = type { i32, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, %struct._IO_marker*, %struct.FILE*, i32, i32, i64, i16, i8, [1 x i8], i8*, i64, i8*, i8*, i8*, i8*, i64, i32, [20 x i8] }
 %struct.SHA_INFO = type { [5 x i32], i32, i32, [16 x i32] }
 %struct._IO_marker = type { %struct._IO_marker*, %struct.FILE*, i32 }
 
 @_2E_str = external constant [26 x i8]
 @stdin = external global %struct.FILE*

llvm/trunk/test/Transforms/IRCE/conjunctive-checks.ll

 ; RUN: opt -S -verify-loop-info -irce < %s | FileCheck %s
 ; RUN: opt -S -verify-loop-info -passes='require<branch-prob>,loop(irce)' < %s | FileCheck %s
 
 define void @f_0(i32 *%arr, i32 *%a_len_ptr, i32 %n, i1* %cond_buf) {
 ; CHECK-LABEL: @f_0(
 
 ; CHECK: loop.preheader:
-; CHECK: [[not_n:[^ ]+]] = sub i32 -1, %n
-; CHECK: [[not_safe_range_end:[^ ]+]] = sub i32 3, %len
-; CHECK: [[not_exit_main_loop_at_hiclamp_cmp:[^ ]+]] = icmp sgt i32 [[not_n]], [[not_safe_range_end]]
-; CHECK: [[not_exit_main_loop_at_hiclamp:[^ ]+]] = select i1 [[not_exit_main_loop_at_hiclamp_cmp]], i32 [[not_n]], i32 [[not_safe_range_end]]
-; CHECK: [[exit_main_loop_at_hiclamp:[^ ]+]] = sub i32 -1, [[not_exit_main_loop_at_hiclamp]]
+; CHECK: [[len_sub:[^ ]+]] = add i32 %len, -4
+; CHECK: [[exit_main_loop_at_hiclamp_cmp:[^ ]+]] = icmp slt i32 %n, [[len_sub]]
+; CHECK: [[exit_main_loop_at_hiclamp:[^ ]+]] = select i1 [[exit_main_loop_at_hiclamp_cmp]], i32 %n, i32 [[len_sub]]
 ; CHECK: [[exit_main_loop_at_loclamp_cmp:[^ ]+]] = icmp sgt i32 [[exit_main_loop_at_hiclamp]], 0
 ; CHECK: [[exit_main_loop_at_loclamp:[^ ]+]] = select i1 [[exit_main_loop_at_loclamp_cmp]], i32 [[exit_main_loop_at_hiclamp]], i32 0
 ; CHECK: [[enter_main_loop:[^ ]+]] = icmp slt i32 0, [[exit_main_loop_at_loclamp]]
-; CHECK: br i1 [[enter_main_loop]], label %loop.preheader2, label %main.pseudo.exit
+; CHECK: br i1 [[enter_main_loop]], label %[[loop_preheader2:[^ ,]+]], label %main.pseudo.exit
 
-; CHECK: loop.preheader2:
+; CHECK: [[loop_preheader2]]:
 ; CHECK: br label %loop
 
  entry:
   %len = load i32, i32* %a_len_ptr, !range !0
   %first.itr.check = icmp sgt i32 %n, 0
   br i1 %first.itr.check, label %loop, label %exit
 
  loop:
   %idx = phi i32 [ 0, %entry ] , [ %idx.next, %in.bounds ]
   %idx.next = add i32 %idx, 1
   %idx.for.abc = add i32 %idx, 4
   %abc.actual = icmp slt i32 %idx.for.abc, %len
   %cond = load volatile i1, i1* %cond_buf
   %abc = and i1 %cond, %abc.actual
   br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !1
 
 ; CHECK: loop:
 ; CHECK:  %cond = load volatile i1, i1* %cond_buf
 ; CHECK:  %abc = and i1 %cond, true
-; CHECK:  br i1 %abc, label %in.bounds, label %out.of.bounds.loopexit3, !prof !1
+; CHECK:  br i1 %abc, label %in.bounds, label %[[loop_exit:[^ ,]+]], !prof !1
 
-; CHECK: out.of.bounds.loopexit:
+; CHECK: [[loop_exit]]:
 ; CHECK:  br label %out.of.bounds
 
  in.bounds:
   %addr = getelementptr i32, i32* %arr, i32 %idx.for.abc
   store i32 0, i32* %addr
   %next = icmp slt i32 %idx.next, %n
   br i1 %next, label %loop, label %exit
 
  out.of.bounds:
   ret void
 
  exit:
   ret void
 }
 
 define void @f_1(
     i32* %arr_a, i32* %a_len_ptr, i32* %arr_b, i32* %b_len_ptr, i32 %n) {
 ; CHECK-LABEL: @f_1(
 
 ; CHECK: loop.preheader:
-; CHECK: [[not_len_b:[^ ]+]] = sub i32 -1, %len.b
-; CHECK: [[not_len_a:[^ ]+]] = sub i32 -1, %len.a
-; CHECK: [[smax_not_len_cond:[^ ]+]] = icmp sgt i32 [[not_len_b]], [[not_len_a]]
-; CHECK: [[smax_not_len:[^ ]+]] = select i1 [[smax_not_len_cond]], i32 [[not_len_b]], i32 [[not_len_a]]
-; CHECK: [[not_n:[^ ]+]] = sub i32 -1, %n
-; CHECK: [[not_upper_limit_cond_loclamp:[^ ]+]] = icmp sgt i32 [[smax_not_len]], [[not_n]]
-; CHECK: [[not_upper_limit_loclamp:[^ ]+]] = select i1 [[not_upper_limit_cond_loclamp]], i32 [[smax_not_len]], i32 [[not_n]]
-; CHECK: [[upper_limit_loclamp:[^ ]+]] = sub i32 -1, [[not_upper_limit_loclamp]]
+; CHECK: [[smax_len_cond:[^ ]+]] = icmp slt i32 %len.b, %len.a
+; CHECK: [[smax_len:[^ ]+]] = select i1 [[smax_len_cond]], i32 %len.b, i32 %len.a
+; CHECK: [[upper_limit_cond_loclamp:[^ ]+]] = icmp slt i32 [[smax_len]], %n 
+; CHECK: [[upper_limit_loclamp:[^ ]+]] = select i1 [[upper_limit_cond_loclamp]], i32 [[smax_len]], i32 %n
 ; CHECK: [[upper_limit_cmp:[^ ]+]] = icmp sgt i32 [[upper_limit_loclamp]], 0
 ; CHECK: [[upper_limit:[^ ]+]] = select i1 [[upper_limit_cmp]], i32 [[upper_limit_loclamp]], i32 0
 
  entry:
   %len.a = load i32, i32* %a_len_ptr, !range !0
   %len.b = load i32, i32* %b_len_ptr, !range !0
   %first.itr.check = icmp sgt i32 %n, 0
   br i1 %first.itr.check, label %loop, label %exit
 
  loop:
   %idx = phi i32 [ 0, %entry ] , [ %idx.next, %in.bounds ]
   %idx.next = add i32 %idx, 1
   %abc.a = icmp slt i32 %idx, %len.a
   %abc.b = icmp slt i32 %idx, %len.b
   %abc = and i1 %abc.a, %abc.b
   br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !1
 
 ; CHECK: loop:
 ; CHECK:   %abc = and i1 true, true
-; CHECK:   br i1 %abc, label %in.bounds, label %out.of.bounds.loopexit4, !prof !1
+; CHECK:   br i1 %abc, label %in.bounds, label %[[oob_loopexit:[^ ,]+]], !prof !1
 
-; CHECK: out.of.bounds.loopexit:
+; CHECK: [[oob_loopexit]]:
 ; CHECK-NEXT:  br label %out.of.bounds
 
 
  in.bounds:
   %addr.a = getelementptr i32, i32* %arr_a, i32 %idx
   store i32 0, i32* %addr.a
   %addr.b = getelementptr i32, i32* %arr_b, i32 %idx
   store i32 -1, i32* %addr.b

llvm/trunk/test/Transforms/IRCE/decrementing-loop.ll

 
  out.of.bounds:
   ret void
 
  exit:
   ret void
 
 ; CHECK: loop.preheader:
-; CHECK:   [[not_len:[^ ]+]] = sub i32 -1, %len
-; CHECK:   [[not_n:[^ ]+]] = sub i32 -1, %n
-; CHECK:   [[not_len_hiclamp_cmp:[^ ]+]] = icmp sgt i32 [[not_len]], [[not_n]]
-; CHECK:   [[not_len_hiclamp:[^ ]+]] = select i1 [[not_len_hiclamp_cmp]], i32 [[not_len]], i32 [[not_n]]
-; CHECK:   [[len_hiclamp:[^ ]+]] = sub i32 -1, [[not_len_hiclamp]]
+; CHECK:   [[len_hiclamp_cmp:[^ ]+]] = icmp slt i32 %len, %n
+; CHECK:   [[len_hiclamp:[^ ]+]] = select i1 [[len_hiclamp_cmp]], i32 %len, i32 %n
 ; CHECK:   [[not_exit_preloop_at_cmp:[^ ]+]] = icmp sgt i32 [[len_hiclamp]], 0
 ; CHECK:   [[not_exit_preloop_at:[^ ]+]] = select i1 [[not_exit_preloop_at_cmp]], i32 [[len_hiclamp]], i32 0
 ; CHECK:   %exit.preloop.at = add i32 [[not_exit_preloop_at]], -1
 }
 
 ; Make sure that we can eliminate the range check when the loop looks like:
 ; for (i = len.a - 1; i >= 0; --i)
 ;   b[i] = a[i];

llvm/trunk/test/Transforms/IRCE/multiple-access-no-preloop.ll

 
  exit:
   ret void
 }
 
 ; CHECK-LABEL: @multiple_access_no_preloop(
 
 ; CHECK: loop.preheader:
-; CHECK: [[not_len_b:[^ ]+]] = sub i32 -1, %len.b
-; CHECK: [[not_len_a:[^ ]+]] = sub i32 -1, %len.a
-; CHECK: [[smax_not_len_cond:[^ ]+]] = icmp sgt i32 [[not_len_b]], [[not_len_a]]
-; CHECK: [[smax_not_len:[^ ]+]] = select i1 [[smax_not_len_cond]], i32 [[not_len_b]], i32 [[not_len_a]]
-; CHECK: [[not_n:[^ ]+]] = sub i32 -1, %n
-; CHECK: [[not_upper_limit_cond_loclamp:[^ ]+]] = icmp sgt i32 [[smax_not_len]], [[not_n]]
-; CHECK: [[not_upper_limit_loclamp:[^ ]+]] = select i1 [[not_upper_limit_cond_loclamp]], i32 [[smax_not_len]], i32 [[not_n]]
-; CHECK: [[upper_limit_loclamp:[^ ]+]] = sub i32 -1, [[not_upper_limit_loclamp]]
+; CHECK: [[smax_len_cond:[^ ]+]] = icmp slt i32 %len.b, %len.a
+; CHECK: [[smax_len:[^ ]+]] = select i1 [[smax_len_cond]], i32 %len.b, i32 %len.a
+; CHECK: [[upper_limit_cond_loclamp:[^ ]+]] = icmp slt i32 [[smax_len]], %n
+; CHECK: [[upper_limit_loclamp:[^ ]+]] = select i1 [[upper_limit_cond_loclamp]], i32 [[smax_len]], i32 %n
 ; CHECK: [[upper_limit_cmp:[^ ]+]] = icmp sgt i32 [[upper_limit_loclamp]], 0
 ; CHECK: [[upper_limit:[^ ]+]] = select i1 [[upper_limit_cmp]], i32 [[upper_limit_loclamp]], i32 0
 
 ; CHECK: loop:
 ; CHECK: br i1 true, label %in.bounds.a, label %out.of.bounds
 
 ; CHECK: in.bounds.a:
 ; CHECK: br i1 true, label %in.bounds.b, label %out.of.bounds

llvm/trunk/test/Transforms/IRCE/ranges_of_different_types.ll

 ; %exit.mainloop.at = 101
 
 define void @test_01(i32* %arr, i32* %a_len_ptr) #0 {
 
 ; CHECK-LABEL: test_01(
 ; CHECK-NOT:     preloop
 ; CHECK:         entry:
 ; CHECK-NEXT:      %len = load i32, i32* %a_len_ptr, !range !0
-; CHECK-NEXT:      [[SUB1:%[^ ]+]] = sub i32 12, %len
-; CHECK-NEXT:      [[CMP1:%[^ ]+]] = icmp sgt i32 [[SUB1]], -102
-; CHECK-NEXT:      [[SMAX:%[^ ]+]] = select i1 [[CMP1]], i32 [[SUB1]], i32 -102
-; CHECK-NEXT:      [[SUB2:%[^ ]+]] = sub i32 -1, [[SMAX]]
-; CHECK-NEXT:      [[CMP2:%[^ ]+]] = icmp sgt i32 [[SUB2]], 0
-; CHECK-NEXT:      %exit.mainloop.at = select i1 [[CMP2]], i32 [[SUB2]], i32 0
+; CHECK-NEXT:      [[SUB1:%[^ ]+]] = add i32 %len, -13
+; CHECK-NEXT:      [[CMP1:%[^ ]+]] = icmp slt i32 [[SUB1]], 101
+; CHECK-NEXT:      [[SMAX:%[^ ]+]] = select i1 [[CMP1]], i32 [[SUB1]], i32 101
+; CHECK-NEXT:      [[CMP2:%[^ ]+]] = icmp sgt i32 [[SMAX]], 0
+; CHECK-NEXT:      %exit.mainloop.at = select i1 [[CMP2]], i32 [[SMAX]], i32 0
 ; CHECK-NEXT:      [[GOTO_LOOP:%[^ ]+]] = icmp slt i32 0, %exit.mainloop.at
 ; CHECK-NEXT:      br i1 [[GOTO_LOOP]], label %loop.preheader, label %main.pseudo.exit
 ; CHECK:         loop
 ; CHECK:           br i1 true, label %in.bounds
 ; CHECK:         postloop:
 
 entry:
   %len = load i32, i32* %a_len_ptr, !range !0

 define void @test_02(i32* %arr, i32* %a_len_ptr) #0 {
 
 ; CHECK-LABEL: test_02(
 ; CHECK:         entry:
 ; CHECK-NEXT:      %len = load i32, i32* %a_len_ptr, !range !0
 ; CHECK-NEXT:      [[LEN_MINUS_SMAX:%[^ ]+]] = add i32 %len, -2147483647
 ; CHECK-NEXT:      [[CMP1:%[^ ]+]] = icmp sgt i32 [[LEN_MINUS_SMAX]], -13
 ; CHECK-NEXT:      [[SMAX1:%[^ ]+]] = select i1 [[CMP1]], i32 [[LEN_MINUS_SMAX]], i32 -13
-; CHECK-NEXT:      [[ADD1:%[^ ]+]] = add i32 [[SMAX1]], -1
-; CHECK-NEXT:      [[SUB1:%[^ ]+]] = sub i32 [[ADD1]], %len
-; CHECK-NEXT:      [[CMP2:%[^ ]+]] = icmp sgt i32 [[SUB1]], -102
-; CHECK-NEXT:      [[SMAX2:%[^ ]+]] = select i1 [[CMP2]], i32 [[SUB1]], i32 -102
-; CHECK-NEXT:      [[SUB2:%[^ ]+]] = sub i32 -1, [[SMAX2]]
-; CHECK-NEXT:      [[CMP3:%[^ ]+]] = icmp sgt i32 [[SUB2]], 0
-; CHECK-NEXT:      %exit.mainloop.at = select i1 [[CMP3]], i32 [[SUB2]], i32 0
+; CHECK-NEXT:      [[SUB1:%[^ ]+]] = sub i32 %len, [[SMAX1]]
+; CHECK-NEXT:      [[CMP2:%[^ ]+]] = icmp slt i32 [[SUB1]], 101
+; CHECK-NEXT:      [[SMAX2:%[^ ]+]] = select i1 [[CMP2]], i32 [[SUB1]], i32 101
+; CHECK-NEXT:      [[CMP3:%[^ ]+]] = icmp sgt i32 [[SMAX2]], 0
+; CHECK-NEXT:      %exit.mainloop.at = select i1 [[CMP3]], i32 [[SMAX2]], i32 0
 ; CHECK-NEXT:      br i1 true, label %loop.preloop.preheader
 ; CHECK:         loop.preloop:
 ; CHECK-NEXT:      %idx.preloop = phi i32 [ %idx.next.preloop, %in.bounds.preloop ], [ 0, %loop.preloop.preheader ]
 ; CHECK-NEXT:      %idx.next.preloop = add i32 %idx.preloop, 1
 ; CHECK-NEXT:      %idx.offset.preloop = sub i32 %idx.preloop, 13
 ; CHECK-NEXT:      %abc.preloop = icmp ult i32 %idx.offset.preloop, %len
 ; CHECK-NEXT:      br i1 %abc.preloop, label %in.bounds.preloop, label %out.of.bounds.loopexit
 ; CHECK:         in.bounds.preloop:

 ; %exit.mainloop.at = 101
 
 define void @test_03(i32* %arr, i32* %a_len_ptr) #0 {
 
 ; CHECK-LABEL: test_03(
 ; CHECK-NOT:     preloop
 ; CHECK:         entry:
 ; CHECK-NEXT:      %len = load i32, i32* %a_len_ptr, !range !0
-; CHECK-NEXT:      [[SUB1:%[^ ]+]] = sub i32 -2, %len
-; CHECK-NEXT:      [[SUB2:%[^ ]+]] = sub i32 -1, %len
-; CHECK-NEXT:      [[CMP1:%[^ ]+]] = icmp sgt i32 [[SUB2]], -14
-; CHECK-NEXT:      [[SMAX1:%[^ ]+]] = select i1 [[CMP1]], i32 [[SUB2]], i32 -14
-; CHECK-NEXT:      [[SUB3:%[^ ]+]] = sub i32 [[SUB1]], [[SMAX1]]
-; CHECK-NEXT:      [[CMP2:%[^ ]+]] = icmp ugt i32 [[SUB3]], -102
-; CHECK-NEXT:      [[UMAX1:%[^ ]+]] = select i1 [[CMP2]], i32 [[SUB3]], i32 -102
-; CHECK-NEXT:      %exit.mainloop.at = sub i32 -1, [[UMAX1]]
+; CHECK-NEXT:      [[CMP1:%[^ ]+]] = icmp slt i32 %len, 13
+; CHECK-NEXT:      [[SMAX1:%[^ ]+]] = select i1 [[CMP1]], i32 %len, i32 13
+; CHECK-NEXT:      [[SUB3:%[^ ]+]] = sub i32 %len, [[SMAX1]]
+; CHECK-NEXT:      [[CMP2:%[^ ]+]] = icmp ult i32 [[SUB3]], 101
+; CHECK-NEXT:      %exit.mainloop.at = select i1 [[CMP2]], i32 [[SUB3]], i32 101
 ; CHECK-NEXT:      [[CMP3:%[^ ]+]] = icmp ult i32 0, %exit.mainloop.at
 ; CHECK-NEXT:      br i1 [[CMP3]], label %loop.preheader, label %main.pseudo.exit
 ; CHECK:         postloop:
 
 entry:
   %len = load i32, i32* %a_len_ptr, !range !0
   br label %loop
 

 ; %len = SINT_MAX
 ; %exit.mainloop.at = 101
 
 define void @test_04(i32* %arr, i32* %a_len_ptr) #0 {
 
 ; CHECK-LABEL: test_04(
 ; CHECK:         entry:
 ; CHECK-NEXT:      %len = load i32, i32* %a_len_ptr, !range !0
-; CHECK-NEXT:      [[SUB1:%[^ ]+]] = sub i32 -14, %len
-; CHECK-NEXT:      [[CMP1:%[^ ]+]] = icmp ugt i32 [[SUB1]], -102
-; CHECK-NEXT:      [[UMAX1:%[^ ]+]] = select i1 [[CMP1]], i32 [[SUB1]], i32 -102
-; CHECK-NEXT:      %exit.mainloop.at = sub i32 -1, [[UMAX1]]
+; CHECK-NEXT:      [[SUB1:%[^ ]+]] = add i32 %len, 13
+; CHECK-NEXT:      [[CMP1:%[^ ]+]] = icmp ult i32 [[SUB1]], 101
+; CHECK-NEXT:      %exit.mainloop.at = select i1 [[CMP1]], i32 [[SUB1]], i32 101
 ; CHECK-NEXT:      br i1 true, label %loop.preloop.preheader
 ; CHECK:         in.bounds.preloop:
 ; CHECK-NEXT:      %addr.preloop = getelementptr i32, i32* %arr, i32 %idx.preloop
 ; CHECK-NEXT:      store i32 0, i32* %addr.preloop
 ; CHECK-NEXT:      %next.preloop = icmp ult i32 %idx.next.preloop, 101
 ; CHECK-NEXT:      [[PRELOOP_COND:%[^ ]+]] = icmp ult i32 %idx.next.preloop, 13
 ; CHECK-NEXT:      br i1 [[PRELOOP_COND]], label %loop.preloop, label %preloop.exit.selector
 ; CHECK:         postloop:

 
 ; Signed latch, signed RC, positive offset. Same as test_01.
 define void @test_05(i32* %arr, i32* %a_len_ptr) #0 {
 
 ; CHECK-LABEL: test_05(
 ; CHECK-NOT:     preloop
 ; CHECK:         entry:
 ; CHECK-NEXT:      %len = load i32, i32* %a_len_ptr, !range !0
-; CHECK-NEXT:      [[SUB1:%[^ ]+]] = sub i32 12, %len
-; CHECK-NEXT:      [[CMP1:%[^ ]+]] = icmp sgt i32 [[SUB1]], -102
-; CHECK-NEXT:      [[SMAX:%[^ ]+]] = select i1 [[CMP1]], i32 [[SUB1]], i32 -102
-; CHECK-NEXT:      [[SUB2:%[^ ]+]] = sub i32 -1, [[SMAX]]
-; CHECK-NEXT:      [[CMP2:%[^ ]+]] = icmp sgt i32 [[SUB2]], 0
-; CHECK-NEXT:      %exit.mainloop.at = select i1 [[CMP2]], i32 [[SUB2]], i32 0
+; CHECK-NEXT:      [[SUB1:%[^ ]+]] = add i32 %len, -13
+; CHECK-NEXT:      [[CMP1:%[^ ]+]] = icmp slt i32 [[SUB1]], 101
+; CHECK-NEXT:      [[SMAX:%[^ ]+]] = select i1 [[CMP1]], i32 [[SUB1]], i32 101
+; CHECK-NEXT:      [[CMP2:%[^ ]+]] = icmp sgt i32 [[SMAX]], 0
+; CHECK-NEXT:      %exit.mainloop.at = select i1 [[CMP2]], i32 [[SMAX]], i32 0
 ; CHECK-NEXT:      [[GOTO_LOOP:%[^ ]+]] = icmp slt i32 0, %exit.mainloop.at
 ; CHECK-NEXT:      br i1 [[GOTO_LOOP]], label %loop.preheader, label %main.pseudo.exit
 ; CHECK:         loop
 ; CHECK:           br i1 true, label %in.bounds
 ; CHECK:         postloop:
 
 entry:
   %len = load i32, i32* %a_len_ptr, !range !0

 define void @test_06(i32* %arr, i32* %a_len_ptr) #0 {
 
 ; CHECK-LABEL: test_06(
 ; CHECK:         entry:
 ; CHECK-NEXT:      %len = load i32, i32* %a_len_ptr, !range !0
 ; CHECK-NEXT:      [[LEN_MINUS_SMAX:%[^ ]+]] = add i32 %len, -2147483647
 ; CHECK-NEXT:      [[CMP1:%[^ ]+]] = icmp sgt i32 [[LEN_MINUS_SMAX]], -13
 ; CHECK-NEXT:      [[SMAX1:%[^ ]+]] = select i1 [[CMP1]], i32 [[LEN_MINUS_SMAX]], i32 -13
-; CHECK-NEXT:      [[ADD1:%[^ ]+]] = add i32 [[SMAX1]], -1
-; CHECK-NEXT:      [[SUB1:%[^ ]+]] = sub i32 [[ADD1]], %len
-; CHECK-NEXT:      [[CMP2:%[^ ]+]] = icmp sgt i32 [[SUB1]], -102
-; CHECK-NEXT:      [[SMAX2:%[^ ]+]] = select i1 [[CMP2]], i32 [[SUB1]], i32 -102
-; CHECK-NEXT:      [[SUB2:%[^ ]+]] = sub i32 -1, [[SMAX2]]
-; CHECK-NEXT:      [[CMP3:%[^ ]+]] = icmp sgt i32 [[SUB2]], 0
-; CHECK-NEXT:      %exit.mainloop.at = select i1 [[CMP3]], i32 [[SUB2]], i32 0
+; CHECK-NEXT:      [[SUB1:%[^ ]+]] = sub i32 %len, [[SMAX1]]
+; CHECK-NEXT:      [[CMP2:%[^ ]+]] = icmp slt i32 [[SUB1]], 101
+; CHECK-NEXT:      [[SMAX2:%[^ ]+]] = select i1 [[CMP2]], i32 [[SUB1]], i32 101
+; CHECK-NEXT:      [[CMP3:%[^ ]+]] = icmp sgt i32 [[SMAX2]], 0
+; CHECK-NEXT:      %exit.mainloop.at = select i1 [[CMP3]], i32 [[SMAX2]], i32 0
 ; CHECK-NEXT:      br i1 true, label %loop.preloop.preheader
 ; CHECK:         in.bounds.preloop:
 ; CHECK-NEXT:      %addr.preloop = getelementptr i32, i32* %arr, i32 %idx.preloop
 ; CHECK-NEXT:      store i32 0, i32* %addr.preloop
 ; CHECK-NEXT:      %next.preloop = icmp slt i32 %idx.next.preloop, 101
 ; CHECK-NEXT:      [[PRELOOP_COND:%[^ ]+]] = icmp slt i32 %idx.next.preloop, 13
 ; CHECK-NEXT:      br i1 [[PRELOOP_COND]], label %loop.preloop, label %preloop.exit.selector
 ; CHECK:         postloop:

 
 ; Unsigned latch, Unsigned RC, negative offset. Same as test_03.
 define void @test_07(i32* %arr, i32* %a_len_ptr) #0 {
 
 ; CHECK-LABEL: test_07(
 ; CHECK-NOT:     preloop
 ; CHECK:         entry:
 ; CHECK-NEXT:      %len = load i32, i32* %a_len_ptr, !range !0
-; CHECK-NEXT:      [[SUB1:%[^ ]+]] = sub i32 -2, %len
-; CHECK-NEXT:      [[SUB2:%[^ ]+]] = sub i32 -1, %len
-; CHECK-NEXT:      [[CMP1:%[^ ]+]] = icmp sgt i32 [[SUB2]], -14
-; CHECK-NEXT:      [[SMAX1:%[^ ]+]] = select i1 [[CMP1]], i32 [[SUB2]], i32 -14
-; CHECK-NEXT:      [[SUB3:%[^ ]+]] = sub i32 [[SUB1]], [[SMAX1]]
-; CHECK-NEXT:      [[CMP2:%[^ ]+]] = icmp ugt i32 [[SUB3]], -102
-; CHECK-NEXT:      [[UMAX1:%[^ ]+]] = select i1 [[CMP2]], i32 [[SUB3]], i32 -102
-; CHECK-NEXT:      %exit.mainloop.at = sub i32 -1, [[UMAX1]]
+; CHECK-NEXT:      [[CMP1:%[^ ]+]] = icmp slt i32 %len, 13
+; CHECK-NEXT:      [[SMAX1:%[^ ]+]] = select i1 [[CMP1]], i32 %len, i32 13
+; CHECK-NEXT:      [[SUB3:%[^ ]+]] = sub i32 %len, [[SMAX1]]
+; CHECK-NEXT:      [[CMP2:%[^ ]+]] = icmp ult i32 [[SUB3]], 101
+; CHECK-NEXT:      %exit.mainloop.at = select i1 [[CMP2]], i32 [[SUB3]], i32 101
 ; CHECK-NEXT:      [[CMP3:%[^ ]+]] = icmp ult i32 0, %exit.mainloop.at
 ; CHECK-NEXT:      br i1 [[CMP3]], label %loop.preheader, label %main.pseudo.exit
 ; CHECK:         loop
 ; CHECK:           br i1 true, label %in.bounds
 ; CHECK:         postloop:
 
 entry:
   %len = load i32, i32* %a_len_ptr, !range !0

 }
 
 ; Unsigned latch, Unsigned RC, negative offset. Same as test_04.
 define void @test_08(i32* %arr, i32* %a_len_ptr) #0 {
 
 ; CHECK-LABEL: test_08(
 ; CHECK:         entry:
 ; CHECK-NEXT:      %len = load i32, i32* %a_len_ptr, !range !0
-; CHECK-NEXT:      [[SUB1:%[^ ]+]] = sub i32 -14, %len
-; CHECK-NEXT:      [[CMP1:%[^ ]+]] = icmp ugt i32 [[SUB1]], -102
-; CHECK-NEXT:      [[UMAX1:%[^ ]+]] = select i1 [[CMP1]], i32 [[SUB1]], i32 -102
-; CHECK-NEXT:      %exit.mainloop.at = sub i32 -1, [[UMAX1]]
+; CHECK-NEXT:      [[SUB1:%[^ ]+]] = add i32 %len, 13
+; CHECK-NEXT:      [[CMP1:%[^ ]+]] = icmp ult i32 [[SUB1]], 101
+; CHECK-NEXT:      %exit.mainloop.at = select i1 [[CMP1]], i32 [[SUB1]], i32 101
 ; CHECK-NEXT:      br i1 true, label %loop.preloop.preheader
 ; CHECK:         in.bounds.preloop:
 ; CHECK-NEXT:      %addr.preloop = getelementptr i32, i32* %arr, i32 %idx.preloop
 ; CHECK-NEXT:      store i32 0, i32* %addr.preloop
 ; CHECK-NEXT:      %next.preloop = icmp ult i32 %idx.next.preloop, 101
 ; CHECK-NEXT:      [[PRELOOP_COND:%[^ ]+]] = icmp ult i32 %idx.next.preloop, 13
 ; CHECK-NEXT:      br i1 [[PRELOOP_COND]], label %loop.preloop, label %preloop.exit.selector
 ; CHECK:         postloop:

llvm/trunk/test/Transforms/IRCE/rc-negative-bound.ll

 define void @test_03(i32 *%arr, i32 %n, i32 %bound) {
 ; CHECK-LABEL: @test_03(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[FIRST_ITR_CHECK:%.*]] = icmp sgt i32 [[N:%.*]], 0
 ; CHECK-NEXT:    br i1 [[FIRST_ITR_CHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
 ; CHECK:       loop.preheader:
 ; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[BOUND:%.*]], -2147483647
 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp sgt i32 [[TMP0]], 0
-; CHECK-NEXT:    [[SMAX:%.*]] = select i1 [[TMP1]], i32 [[TMP0]], i32 0
-; CHECK-NEXT:    [[TMP2:%.*]] = sub i32 [[BOUND]], [[SMAX]]
-; CHECK-NEXT:    [[TMP3:%.*]] = sub i32 -1, [[BOUND]]
-; CHECK-NEXT:    [[TMP4:%.*]] = icmp sgt i32 [[TMP3]], -1
-; CHECK-NEXT:    [[SMAX1:%.*]] = select i1 [[TMP4]], i32 [[TMP3]], i32 -1
-; CHECK-NEXT:    [[TMP5:%.*]] = sub i32 -1, [[SMAX1]]
-; CHECK-NEXT:    [[TMP6:%.*]] = icmp sgt i32 [[TMP5]], -1
-; CHECK-NEXT:    [[SMAX2:%.*]] = select i1 [[TMP6]], i32 [[TMP5]], i32 -1
-; CHECK-NEXT:    [[TMP7:%.*]] = add i32 [[SMAX2]], 1
-; CHECK-NEXT:    [[TMP8:%.*]] = mul i32 [[TMP2]], [[TMP7]]
-; CHECK-NEXT:    [[TMP9:%.*]] = sub i32 -1, [[TMP8]]
-; CHECK-NEXT:    [[TMP10:%.*]] = sub i32 -1, [[N]]
-; CHECK-NEXT:    [[TMP11:%.*]] = icmp sgt i32 [[TMP9]], [[TMP10]]
-; CHECK-NEXT:    [[SMAX3:%.*]] = select i1 [[TMP11]], i32 [[TMP9]], i32 [[TMP10]]
-; CHECK-NEXT:    [[TMP12:%.*]] = sub i32 -1, [[SMAX3]]
-; CHECK-NEXT:    [[TMP13:%.*]] = icmp sgt i32 [[TMP12]], 0
-; CHECK-NEXT:    [[EXIT_MAINLOOP_AT:%.*]] = select i1 [[TMP13]], i32 [[TMP12]], i32 0
-; CHECK-NEXT:    [[TMP14:%.*]] = icmp slt i32 0, [[EXIT_MAINLOOP_AT]]
-; CHECK-NEXT:    br i1 [[TMP14]], label [[LOOP_PREHEADER5:%.*]], label [[MAIN_PSEUDO_EXIT:%.*]]
-; CHECK:       loop.preheader5:
+; CHECK-NEXT:    [[SMIN:%.*]] = select i1 [[TMP1]], i32 [[TMP0]], i32 0
+; CHECK-NEXT:    [[TMP2:%.*]] = sub i32 [[BOUND]], [[SMIN]]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp slt i32 [[BOUND]], 0
+; CHECK-NEXT:    [[SMAX:%.*]] = select i1 [[TMP3]], i32 [[BOUND]], i32 0
+; CHECK-NEXT:    [[TMP4:%.*]] = icmp sgt i32 [[SMAX]], -1
+; CHECK-NEXT:    [[SMIN1:%.*]] = select i1 [[TMP4]], i32 [[SMAX]], i32 -1
+; CHECK-NEXT:    [[TMP5:%.*]] = add i32 [[SMIN1]], 1
+; CHECK-NEXT:    [[TMP6:%.*]] = mul i32 [[TMP2]], [[TMP5]]
+; CHECK-NEXT:    [[TMP7:%.*]] = icmp slt i32 [[N]], [[TMP6]]
+; CHECK-NEXT:    [[SMAX2:%.*]] = select i1 [[TMP7]], i32 [[N]], i32 [[TMP6]]
+; CHECK-NEXT:    [[TMP8:%.*]] = icmp sgt i32 [[SMAX2]], 0
+; CHECK-NEXT:    [[EXIT_MAINLOOP_AT:%.*]] = select i1 [[TMP8]], i32 [[SMAX2]], i32 0
+; CHECK-NEXT:    [[TMP9:%.*]] = icmp slt i32 0, [[EXIT_MAINLOOP_AT]]
+; CHECK-NEXT:    br i1 [[TMP9]], label [[LOOP_PREHEADER4:%.*]], label [[MAIN_PSEUDO_EXIT:%.*]]
+; CHECK:       loop.preheader4:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[IDX:%.*]] = phi i32 [ [[IDX_NEXT:%.*]], [[IN_BOUNDS:%.*]] ], [ 0, [[LOOP_PREHEADER5]] ]
+; CHECK-NEXT:    [[IDX:%.*]] = phi i32 [ [[IDX_NEXT:%.*]], [[IN_BOUNDS:%.*]] ], [ 0, [[LOOP_PREHEADER4]] ]
 ; CHECK-NEXT:    [[IDX_NEXT]] = add i32 [[IDX]], 1
 ; CHECK-NEXT:    [[ABC:%.*]] = icmp slt i32 [[IDX]], [[BOUND]]
-; CHECK-NEXT:    br i1 true, label [[IN_BOUNDS]], label [[OUT_OF_BOUNDS_LOOPEXIT6:%.*]], !prof !0
+; CHECK-NEXT:    br i1 true, label [[IN_BOUNDS]], label [[OUT_OF_BOUNDS_LOOPEXIT5:%.*]], !prof !0
 ; CHECK:       in.bounds:
 ; CHECK-NEXT:    [[ADDR:%.*]] = getelementptr i32, i32* [[ARR:%.*]], i32 [[IDX]]
 ; CHECK-NEXT:    store i32 0, i32* [[ADDR]]
 ; CHECK-NEXT:    [[NEXT:%.*]] = icmp slt i32 [[IDX_NEXT]], [[N]]
-; CHECK-NEXT:    [[TMP15:%.*]] = icmp slt i32 [[IDX_NEXT]], [[EXIT_MAINLOOP_AT]]
-; CHECK-NEXT:    br i1 [[TMP15]], label [[LOOP]], label [[MAIN_EXIT_SELECTOR:%.*]]
+; CHECK-NEXT:    [[TMP10:%.*]] = icmp slt i32 [[IDX_NEXT]], [[EXIT_MAINLOOP_AT]]
+; CHECK-NEXT:    br i1 [[TMP10]], label [[LOOP]], label [[MAIN_EXIT_SELECTOR:%.*]]
 ; CHECK:       main.exit.selector:
 ; CHECK-NEXT:    [[IDX_NEXT_LCSSA:%.*]] = phi i32 [ [[IDX_NEXT]], [[IN_BOUNDS]] ]
-; CHECK-NEXT:    [[TMP16:%.*]] = icmp slt i32 [[IDX_NEXT_LCSSA]], [[N]]
-; CHECK-NEXT:    br i1 [[TMP16]], label [[MAIN_PSEUDO_EXIT]], label [[EXIT_LOOPEXIT:%.*]]
+; CHECK-NEXT:    [[TMP11:%.*]] = icmp slt i32 [[IDX_NEXT_LCSSA]], [[N]]
+; CHECK-NEXT:    br i1 [[TMP11]], label [[MAIN_PSEUDO_EXIT]], label [[EXIT_LOOPEXIT:%.*]]
 ; CHECK:       main.pseudo.exit:
 ; CHECK-NEXT:    [[IDX_COPY:%.*]] = phi i32 [ 0, [[LOOP_PREHEADER]] ], [ [[IDX_NEXT_LCSSA]], [[MAIN_EXIT_SELECTOR]] ]
 ; CHECK-NEXT:    [[INDVAR_END:%.*]] = phi i32 [ 0, [[LOOP_PREHEADER]] ], [ [[IDX_NEXT_LCSSA]], [[MAIN_EXIT_SELECTOR]] ]
 ; CHECK-NEXT:    br label [[POSTLOOP:%.*]]
 ; CHECK:       out.of.bounds.loopexit:
 ; CHECK-NEXT:    br label [[OUT_OF_BOUNDS:%.*]]
-; CHECK:       out.of.bounds.loopexit6:
+; CHECK:       out.of.bounds.loopexit5:
 ; CHECK-NEXT:    br label [[OUT_OF_BOUNDS]]
 ; CHECK:       out.of.bounds:
 ; CHECK-NEXT:    ret void
 ; CHECK:       exit.loopexit.loopexit:
 ; CHECK-NEXT:    br label [[EXIT_LOOPEXIT]]
 ; CHECK:       exit.loopexit:
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:

 ; RC against a value which is not known to be non-negative. Here we should
 ; expand runtime checks against bound being positive or negative.
 define void @test_04(i32 *%arr, i32 %n, i32 %bound) {
 ; CHECK-LABEL: @test_04(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[FIRST_ITR_CHECK:%.*]] = icmp sgt i32 [[N:%.*]], 0
 ; CHECK-NEXT:    br i1 [[FIRST_ITR_CHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
 ; CHECK:       loop.preheader:
-; CHECK-NEXT:    [[TMP0:%.*]] = sub i32 -1, [[BOUND:%.*]]
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp sgt i32 [[TMP0]], -1
-; CHECK-NEXT:    [[SMAX:%.*]] = select i1 [[TMP1]], i32 [[TMP0]], i32 -1
-; CHECK-NEXT:    [[TMP2:%.*]] = add i32 [[BOUND]], [[SMAX]]
-; CHECK-NEXT:    [[TMP3:%.*]] = add i32 [[TMP2]], 1
-; CHECK-NEXT:    [[TMP4:%.*]] = sub i32 -1, [[SMAX]]
-; CHECK-NEXT:    [[TMP5:%.*]] = icmp sgt i32 [[TMP4]], -1
-; CHECK-NEXT:    [[SMAX1:%.*]] = select i1 [[TMP5]], i32 [[TMP4]], i32 -1
-; CHECK-NEXT:    [[TMP6:%.*]] = add i32 [[SMAX1]], 1
-; CHECK-NEXT:    [[TMP7:%.*]] = mul i32 [[TMP3]], [[TMP6]]
-; CHECK-NEXT:    [[TMP8:%.*]] = sub i32 -1, [[TMP7]]
-; CHECK-NEXT:    [[TMP9:%.*]] = sub i32 -1, [[N]]
-; CHECK-NEXT:    [[TMP10:%.*]] = icmp ugt i32 [[TMP8]], [[TMP9]]
-; CHECK-NEXT:    [[UMAX:%.*]] = select i1 [[TMP10]], i32 [[TMP8]], i32 [[TMP9]]
-; CHECK-NEXT:    [[EXIT_MAINLOOP_AT:%.*]] = sub i32 -1, [[UMAX]]
-; CHECK-NEXT:    [[TMP11:%.*]] = icmp ult i32 0, [[EXIT_MAINLOOP_AT]]
-; CHECK-NEXT:    br i1 [[TMP11]], label [[LOOP_PREHEADER2:%.*]], label [[MAIN_PSEUDO_EXIT:%.*]]
-; CHECK:       loop.preheader2:
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp slt i32 [[BOUND:%.*]], 0
+; CHECK-NEXT:    [[SMAX:%.*]] = select i1 [[TMP0]], i32 [[BOUND]], i32 0
+; CHECK-NEXT:    [[TMP1:%.*]] = sub i32 [[BOUND]], [[SMAX]]
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp sgt i32 [[SMAX]], -1
+; CHECK-NEXT:    [[SMIN:%.*]] = select i1 [[TMP2]], i32 [[SMAX]], i32 -1
+; CHECK-NEXT:    [[TMP3:%.*]] = add i32 [[SMIN]], 1
+; CHECK-NEXT:    [[TMP4:%.*]] = mul i32 [[TMP1]], [[TMP3]]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp ult i32 [[N]], [[TMP4]]
+; CHECK-NEXT:    [[EXIT_MAINLOOP_AT:%.*]] = select i1 [[TMP5]], i32 [[N]], i32 [[TMP4]]
+; CHECK-NEXT:    [[TMP6:%.*]] = icmp ult i32 0, [[EXIT_MAINLOOP_AT]]
+; CHECK-NEXT:    br i1 [[TMP6]], label [[LOOP_PREHEADER1:%.*]], label [[MAIN_PSEUDO_EXIT:%.*]]
+; CHECK:       loop.preheader1:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[IDX:%.*]] = phi i32 [ [[IDX_NEXT:%.*]], [[IN_BOUNDS:%.*]] ], [ 0, [[LOOP_PREHEADER2]] ]
+; CHECK-NEXT:    [[IDX:%.*]] = phi i32 [ [[IDX_NEXT:%.*]], [[IN_BOUNDS:%.*]] ], [ 0, [[LOOP_PREHEADER1]] ]
 ; CHECK-NEXT:    [[IDX_NEXT]] = add i32 [[IDX]], 1
 ; CHECK-NEXT:    [[ABC:%.*]] = icmp slt i32 [[IDX]], [[BOUND]]
-; CHECK-NEXT:    br i1 true, label [[IN_BOUNDS]], label [[OUT_OF_BOUNDS_LOOPEXIT3:%.*]], !prof !0
+; CHECK-NEXT:    br i1 true, label [[IN_BOUNDS]], label [[OUT_OF_BOUNDS_LOOPEXIT2:%.*]], !prof !0
 ; CHECK:       in.bounds:
 ; CHECK-NEXT:    [[ADDR:%.*]] = getelementptr i32, i32* [[ARR:%.*]], i32 [[IDX]]
 ; CHECK-NEXT:    store i32 0, i32* [[ADDR]]
 ; CHECK-NEXT:    [[NEXT:%.*]] = icmp ult i32 [[IDX_NEXT]], [[N]]
-; CHECK-NEXT:    [[TMP12:%.*]] = icmp ult i32 [[IDX_NEXT]], [[EXIT_MAINLOOP_AT]]
-; CHECK-NEXT:    br i1 [[TMP12]], label [[LOOP]], label [[MAIN_EXIT_SELECTOR:%.*]]
+; CHECK-NEXT:    [[TMP7:%.*]] = icmp ult i32 [[IDX_NEXT]], [[EXIT_MAINLOOP_AT]]
+; CHECK-NEXT:    br i1 [[TMP7]], label [[LOOP]], label [[MAIN_EXIT_SELECTOR:%.*]]
 ; CHECK:       main.exit.selector:
 ; CHECK-NEXT:    [[IDX_NEXT_LCSSA:%.*]] = phi i32 [ [[IDX_NEXT]], [[IN_BOUNDS]] ]
-; CHECK-NEXT:    [[TMP13:%.*]] = icmp ult i32 [[IDX_NEXT_LCSSA]], [[N]]
-; CHECK-NEXT:    br i1 [[TMP13]], label [[MAIN_PSEUDO_EXIT]], label [[EXIT_LOOPEXIT:%.*]]
+; CHECK-NEXT:    [[TMP8:%.*]] = icmp ult i32 [[IDX_NEXT_LCSSA]], [[N]]
+; CHECK-NEXT:    br i1 [[TMP8]], label [[MAIN_PSEUDO_EXIT]], label [[EXIT_LOOPEXIT:%.*]]
 ; CHECK:       main.pseudo.exit:
 ; CHECK-NEXT:    [[IDX_COPY:%.*]] = phi i32 [ 0, [[LOOP_PREHEADER]] ], [ [[IDX_NEXT_LCSSA]], [[MAIN_EXIT_SELECTOR]] ]
 ; CHECK-NEXT:    [[INDVAR_END:%.*]] = phi i32 [ 0, [[LOOP_PREHEADER]] ], [ [[IDX_NEXT_LCSSA]], [[MAIN_EXIT_SELECTOR]] ]
 ; CHECK-NEXT:    br label [[POSTLOOP:%.*]]
 ; CHECK:       out.of.bounds.loopexit:
 ; CHECK-NEXT:    br label [[OUT_OF_BOUNDS:%.*]]
-; CHECK:       out.of.bounds.loopexit3:
+; CHECK:       out.of.bounds.loopexit2:
 ; CHECK-NEXT:    br label [[OUT_OF_BOUNDS]]
 ; CHECK:       out.of.bounds:
 ; CHECK-NEXT:    ret void
 ; CHECK:       exit.loopexit.loopexit:
 ; CHECK-NEXT:    br label [[EXIT_LOOPEXIT]]
 ; CHECK:       exit.loopexit:
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:

 define void @test_07(i32 *%arr, i32 %n, i32 %bound) {
 ; CHECK-LABEL: @test_07(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[FIRST_ITR_CHECK:%.*]] = icmp sgt i32 [[N:%.*]], 0
 ; CHECK-NEXT:    br i1 [[FIRST_ITR_CHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
 ; CHECK:       loop.preheader:
 ; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[BOUND:%.*]], -2147483647
 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp sgt i32 [[TMP0]], 0
-; CHECK-NEXT:    [[SMAX:%.*]] = select i1 [[TMP1]], i32 [[TMP0]], i32 0
-; CHECK-NEXT:    [[TMP2:%.*]] = sub i32 [[BOUND]], [[SMAX]]
-; CHECK-NEXT:    [[TMP3:%.*]] = sub i32 -1, [[BOUND]]
-; CHECK-NEXT:    [[TMP4:%.*]] = icmp sgt i32 [[TMP3]], -1
-; CHECK-NEXT:    [[SMAX1:%.*]] = select i1 [[TMP4]], i32 [[TMP3]], i32 -1
-; CHECK-NEXT:    [[TMP5:%.*]] = sub i32 -1, [[SMAX1]]
-; CHECK-NEXT:    [[TMP6:%.*]] = icmp sgt i32 [[TMP5]], -1
-; CHECK-NEXT:    [[SMAX2:%.*]] = select i1 [[TMP6]], i32 [[TMP5]], i32 -1
-; CHECK-NEXT:    [[TMP7:%.*]] = add i32 [[SMAX2]], 1
-; CHECK-NEXT:    [[TMP8:%.*]] = mul i32 [[TMP2]], [[TMP7]]
-; CHECK-NEXT:    [[TMP9:%.*]] = sub i32 -1, [[TMP8]]
-; CHECK-NEXT:    [[TMP10:%.*]] = sub i32 -1, [[N]]
-; CHECK-NEXT:    [[TMP11:%.*]] = icmp sgt i32 [[TMP9]], [[TMP10]]
-; CHECK-NEXT:    [[SMAX3:%.*]] = select i1 [[TMP11]], i32 [[TMP9]], i32 [[TMP10]]
-; CHECK-NEXT:    [[TMP12:%.*]] = sub i32 -1, [[SMAX3]]
-; CHECK-NEXT:    [[TMP13:%.*]] = icmp sgt i32 [[TMP12]], 0
-; CHECK-NEXT:    [[EXIT_MAINLOOP_AT:%.*]] = select i1 [[TMP13]], i32 [[TMP12]], i32 0
-; CHECK-NEXT:    [[TMP14:%.*]] = icmp slt i32 0, [[EXIT_MAINLOOP_AT]]
-; CHECK-NEXT:    br i1 [[TMP14]], label [[LOOP_PREHEADER5:%.*]], label [[MAIN_PSEUDO_EXIT:%.*]]
-; CHECK:       loop.preheader5:
+; CHECK-NEXT:    [[SMIN:%.*]] = select i1 [[TMP1]], i32 [[TMP0]], i32 0
+; CHECK-NEXT:    [[TMP2:%.*]] = sub i32 [[BOUND]], [[SMIN]]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp slt i32 [[BOUND]], 0
+; CHECK-NEXT:    [[SMAX:%.*]] = select i1 [[TMP3]], i32 [[BOUND]], i32 0
+; CHECK-NEXT:    [[TMP4:%.*]] = icmp sgt i32 [[SMAX]], -1
+; CHECK-NEXT:    [[SMIN1:%.*]] = select i1 [[TMP4]], i32 [[SMAX]], i32 -1
+; CHECK-NEXT:    [[TMP5:%.*]] = add i32 [[SMIN1]], 1
+; CHECK-NEXT:    [[TMP6:%.*]] = mul i32 [[TMP2]], [[TMP5]]
+; CHECK-NEXT:    [[TMP7:%.*]] = icmp slt i32 [[N]], [[TMP6]]
+; CHECK-NEXT:    [[SMAX2:%.*]] = select i1 [[TMP7]], i32 [[N]], i32 [[TMP6]]
+; CHECK-NEXT:    [[TMP8:%.*]] = icmp sgt i32 [[SMAX2]], 0
+; CHECK-NEXT:    [[EXIT_MAINLOOP_AT:%.*]] = select i1 [[TMP8]], i32 [[SMAX2]], i32 0
+; CHECK-NEXT:    [[TMP9:%.*]] = icmp slt i32 0, [[EXIT_MAINLOOP_AT]]
+; CHECK-NEXT:    br i1 [[TMP9]], label [[LOOP_PREHEADER4:%.*]], label [[MAIN_PSEUDO_EXIT:%.*]]
+; CHECK:       loop.preheader4:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[IDX:%.*]] = phi i32 [ [[IDX_NEXT:%.*]], [[IN_BOUNDS:%.*]] ], [ 0, [[LOOP_PREHEADER5]] ]
+; CHECK-NEXT:    [[IDX:%.*]] = phi i32 [ [[IDX_NEXT:%.*]], [[IN_BOUNDS:%.*]] ], [ 0, [[LOOP_PREHEADER4]] ]
 ; CHECK-NEXT:    [[IDX_NEXT]] = add i32 [[IDX]], 1
 ; CHECK-NEXT:    [[ABC:%.*]] = icmp ult i32 [[IDX]], [[BOUND]]
-; CHECK-NEXT:    br i1 true, label [[IN_BOUNDS]], label [[OUT_OF_BOUNDS_LOOPEXIT6:%.*]], !prof !0
+; CHECK-NEXT:    br i1 true, label [[IN_BOUNDS]], label [[OUT_OF_BOUNDS_LOOPEXIT5:%.*]], !prof !0
 ; CHECK:       in.bounds:
 ; CHECK-NEXT:    [[ADDR:%.*]] = getelementptr i32, i32* [[ARR:%.*]], i32 [[IDX]]
 ; CHECK-NEXT:    store i32 0, i32* [[ADDR]]
 ; CHECK-NEXT:    [[NEXT:%.*]] = icmp slt i32 [[IDX_NEXT]], [[N]]
-; CHECK-NEXT:    [[TMP15:%.*]] = icmp slt i32 [[IDX_NEXT]], [[EXIT_MAINLOOP_AT]]
-; CHECK-NEXT:    br i1 [[TMP15]], label [[LOOP]], label [[MAIN_EXIT_SELECTOR:%.*]]
+; CHECK-NEXT:    [[TMP10:%.*]] = icmp slt i32 [[IDX_NEXT]], [[EXIT_MAINLOOP_AT]]
+; CHECK-NEXT:    br i1 [[TMP10]], label [[LOOP]], label [[MAIN_EXIT_SELECTOR:%.*]]
 ; CHECK:       main.exit.selector:
 ; CHECK-NEXT:    [[IDX_NEXT_LCSSA:%.*]] = phi i32 [ [[IDX_NEXT]], [[IN_BOUNDS]] ]
-; CHECK-NEXT:    [[TMP16:%.*]] = icmp slt i32 [[IDX_NEXT_LCSSA]], [[N]]
-; CHECK-NEXT:    br i1 [[TMP16]], label [[MAIN_PSEUDO_EXIT]], label [[EXIT_LOOPEXIT:%.*]]
+; CHECK-NEXT:    [[TMP11:%.*]] = icmp slt i32 [[IDX_NEXT_LCSSA]], [[N]]
+; CHECK-NEXT:    br i1 [[TMP11]], label [[MAIN_PSEUDO_EXIT]], label [[EXIT_LOOPEXIT:%.*]]
 ; CHECK:       main.pseudo.exit:
 ; CHECK-NEXT:    [[IDX_COPY:%.*]] = phi i32 [ 0, [[LOOP_PREHEADER]] ], [ [[IDX_NEXT_LCSSA]], [[MAIN_EXIT_SELECTOR]] ]
 ; CHECK-NEXT:    [[INDVAR_END:%.*]] = phi i32 [ 0, [[LOOP_PREHEADER]] ], [ [[IDX_NEXT_LCSSA]], [[MAIN_EXIT_SELECTOR]] ]
 ; CHECK-NEXT:    br label [[POSTLOOP:%.*]]
 ; CHECK:       out.of.bounds.loopexit:
 ; CHECK-NEXT:    br label [[OUT_OF_BOUNDS:%.*]]
-; CHECK:       out.of.bounds.loopexit6:
+; CHECK:       out.of.bounds.loopexit5:
 ; CHECK-NEXT:    br label [[OUT_OF_BOUNDS]]
 ; CHECK:       out.of.bounds:
 ; CHECK-NEXT:    ret void
 ; CHECK:       exit.loopexit.loopexit:
 ; CHECK-NEXT:    br label [[EXIT_LOOPEXIT]]
 ; CHECK:       exit.loopexit:
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:

 ; safely remove this check (see comments in the method
 ; computeSafeIterationSpace).
 define void @test_08(i32 *%arr, i32 %n, i32 %bound) {
 ; CHECK-LABEL: @test_08(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[FIRST_ITR_CHECK:%.*]] = icmp sgt i32 [[N:%.*]], 0
 ; CHECK-NEXT:    br i1 [[FIRST_ITR_CHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
 ; CHECK:       loop.preheader:
-; CHECK-NEXT:    [[TMP0:%.*]] = sub i32 -1, [[BOUND:%.*]]
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp sgt i32 [[TMP0]], -1
-; CHECK-NEXT:    [[SMAX:%.*]] = select i1 [[TMP1]], i32 [[TMP0]], i32 -1
-; CHECK-NEXT:    [[TMP2:%.*]] = add i32 [[BOUND]], [[SMAX]]
-; CHECK-NEXT:    [[TMP3:%.*]] = add i32 [[TMP2]], 1
-; CHECK-NEXT:    [[TMP4:%.*]] = sub i32 -1, [[SMAX]]
-; CHECK-NEXT:    [[TMP5:%.*]] = icmp sgt i32 [[TMP4]], -1
-; CHECK-NEXT:    [[SMAX1:%.*]] = select i1 [[TMP5]], i32 [[TMP4]], i32 -1
-; CHECK-NEXT:    [[TMP6:%.*]] = add i32 [[SMAX1]], 1
-; CHECK-NEXT:    [[TMP7:%.*]] = mul i32 [[TMP3]], [[TMP6]]
-; CHECK-NEXT:    [[TMP8:%.*]] = sub i32 -1, [[TMP7]]
-; CHECK-NEXT:    [[TMP9:%.*]] = sub i32 -1, [[N]]
-; CHECK-NEXT:    [[TMP10:%.*]] = icmp ugt i32 [[TMP8]], [[TMP9]]
-; CHECK-NEXT:    [[UMAX:%.*]] = select i1 [[TMP10]], i32 [[TMP8]], i32 [[TMP9]]
-; CHECK-NEXT:    [[EXIT_MAINLOOP_AT:%.*]] = sub i32 -1, [[UMAX]]
-; CHECK-NEXT:    [[TMP11:%.*]] = icmp ult i32 0, [[EXIT_MAINLOOP_AT]]
-; CHECK-NEXT:    br i1 [[TMP11]], label [[LOOP_PREHEADER2:%.*]], label [[MAIN_PSEUDO_EXIT:%.*]]
-; CHECK:       loop.preheader2:
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp slt i32 [[BOUND:%.*]], 0
+; CHECK-NEXT:    [[SMAX:%.*]] = select i1 [[TMP0]], i32 [[BOUND]], i32 0
+; CHECK-NEXT:    [[TMP1:%.*]] = sub i32 [[BOUND]], [[SMAX]]
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp sgt i32 [[SMAX]], -1
+; CHECK-NEXT:    [[SMIN:%.*]] = select i1 [[TMP2]], i32 [[SMAX]], i32 -1
+; CHECK-NEXT:    [[TMP3:%.*]] = add i32 [[SMIN]], 1
+; CHECK-NEXT:    [[TMP4:%.*]] = mul i32 [[TMP1]], [[TMP3]]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp ult i32 [[N]], [[TMP4]]
+; CHECK-NEXT:    [[EXIT_MAINLOOP_AT:%.*]] = select i1 [[TMP5]], i32 [[N]], i32 [[TMP4]]
+; CHECK-NEXT:    [[TMP6:%.*]] = icmp ult i32 0, [[EXIT_MAINLOOP_AT]]
+; CHECK-NEXT:    br i1 [[TMP6]], label [[LOOP_PREHEADER1:%.*]], label [[MAIN_PSEUDO_EXIT:%.*]]
+; CHECK:       loop.preheader1:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[IDX:%.*]] = phi i32 [ [[IDX_NEXT:%.*]], [[IN_BOUNDS:%.*]] ], [ 0, [[LOOP_PREHEADER2]] ]
+; CHECK-NEXT:    [[IDX:%.*]] = phi i32 [ [[IDX_NEXT:%.*]], [[IN_BOUNDS:%.*]] ], [ 0, [[LOOP_PREHEADER1]] ]
 ; CHECK-NEXT:    [[IDX_NEXT]] = add i32 [[IDX]], 1
 ; CHECK-NEXT:    [[ABC:%.*]] = icmp ult i32 [[IDX]], [[BOUND]]
-; CHECK-NEXT:    br i1 true, label [[IN_BOUNDS]], label [[OUT_OF_BOUNDS_LOOPEXIT3:%.*]], !prof !0
+; CHECK-NEXT:    br i1 true, label [[IN_BOUNDS]], label [[OUT_OF_BOUNDS_LOOPEXIT2:%.*]], !prof !0
 ; CHECK:       in.bounds:
 ; CHECK-NEXT:    [[ADDR:%.*]] = getelementptr i32, i32* [[ARR:%.*]], i32 [[IDX]]
 ; CHECK-NEXT:    store i32 0, i32* [[ADDR]]
 ; CHECK-NEXT:    [[NEXT:%.*]] = icmp ult i32 [[IDX_NEXT]], [[N]]
-; CHECK-NEXT:    [[TMP12:%.*]] = icmp ult i32 [[IDX_NEXT]], [[EXIT_MAINLOOP_AT]]
-; CHECK-NEXT:    br i1 [[TMP12]], label [[LOOP]], label [[MAIN_EXIT_SELECTOR:%.*]]
+; CHECK-NEXT:    [[TMP7:%.*]] = icmp ult i32 [[IDX_NEXT]], [[EXIT_MAINLOOP_AT]]
+; CHECK-NEXT:    br i1 [[TMP7]], label [[LOOP]], label [[MAIN_EXIT_SELECTOR:%.*]]
 ; CHECK:       main.exit.selector:
 ; CHECK-NEXT:    [[IDX_NEXT_LCSSA:%.*]] = phi i32 [ [[IDX_NEXT]], [[IN_BOUNDS]] ]
-; CHECK-NEXT:    [[TMP13:%.*]] = icmp ult i32 [[IDX_NEXT_LCSSA]], [[N]]
-; CHECK-NEXT:    br i1 [[TMP13]], label [[MAIN_PSEUDO_EXIT]], label [[EXIT_LOOPEXIT:%.*]]
+; CHECK-NEXT:    [[TMP8:%.*]] = icmp ult i32 [[IDX_NEXT_LCSSA]], [[N]]
+; CHECK-NEXT:    br i1 [[TMP8]], label [[MAIN_PSEUDO_EXIT]], label [[EXIT_LOOPEXIT:%.*]]
 ; CHECK:       main.pseudo.exit:
 ; CHECK-NEXT:    [[IDX_COPY:%.*]] = phi i32 [ 0, [[LOOP_PREHEADER]] ], [ [[IDX_NEXT_LCSSA]], [[MAIN_EXIT_SELECTOR]] ]
 ; CHECK-NEXT:    [[INDVAR_END:%.*]] = phi i32 [ 0, [[LOOP_PREHEADER]] ], [ [[IDX_NEXT_LCSSA]], [[MAIN_EXIT_SELECTOR]] ]
 ; CHECK-NEXT:    br label [[POSTLOOP:%.*]]
 ; CHECK:       out.of.bounds.loopexit:
 ; CHECK-NEXT:    br label [[OUT_OF_BOUNDS:%.*]]
-; CHECK:       out.of.bounds.loopexit3:
+; CHECK:       out.of.bounds.loopexit2:
 ; CHECK-NEXT:    br label [[OUT_OF_BOUNDS]]
 ; CHECK:       out.of.bounds:
 ; CHECK-NEXT:    ret void
 ; CHECK:       exit.loopexit.loopexit:
 ; CHECK-NEXT:    br label [[EXIT_LOOPEXIT]]
 ; CHECK:       exit.loopexit:
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:

llvm/trunk/test/Transforms/IRCE/single-access-no-preloop.ll

 
  exit:
   ret void
 }
 
 ; CHECK-LABEL: @single_access_no_preloop_with_offset(
 
 ; CHECK: loop.preheader:
-; CHECK: [[not_n:[^ ]+]] = sub i32 -1, %n
-; CHECK: [[not_safe_range_end:[^ ]+]] = sub i32 3, %len
-; CHECK: [[not_exit_main_loop_at_hiclamp_cmp:[^ ]+]] = icmp sgt i32 [[not_n]], [[not_safe_range_end]]
-; CHECK: [[not_exit_main_loop_at_hiclamp:[^ ]+]] = select i1 [[not_exit_main_loop_at_hiclamp_cmp]], i32 [[not_n]], i32 [[not_safe_range_end]]
-; CHECK: [[exit_main_loop_at_hiclamp:[^ ]+]] = sub i32 -1, [[not_exit_main_loop_at_hiclamp]]
+; CHECK: [[safe_range_end:[^ ]+]] = add i32 %len, -4
+; CHECK: [[exit_main_loop_at_hiclamp_cmp:[^ ]+]] = icmp slt i32 %n, [[safe_range_end]]
+; CHECK: [[exit_main_loop_at_hiclamp:[^ ]+]] = select i1 [[exit_main_loop_at_hiclamp_cmp]], i32 %n, i32 [[safe_range_end]]
 ; CHECK: [[exit_main_loop_at_loclamp_cmp:[^ ]+]] = icmp sgt i32 [[exit_main_loop_at_hiclamp]], 0
 ; CHECK: [[exit_main_loop_at_loclamp:[^ ]+]] = select i1 [[exit_main_loop_at_loclamp_cmp]], i32 [[exit_main_loop_at_hiclamp]], i32 0
 ; CHECK: [[enter_main_loop:[^ ]+]] = icmp slt i32 0, [[exit_main_loop_at_loclamp]]
-; CHECK: br i1 [[enter_main_loop]], label %loop.preheader2, label %main.pseudo.exit
+; CHECK: br i1 [[enter_main_loop]], label %[[loop_preheader:[^ ,]+]], label %main.pseudo.exit
 
 ; CHECK: loop:
 ; CHECK: br i1 true, label %in.bounds, label %out.of.bounds
 
 ; CHECK: in.bounds:
 ; CHECK: [[continue_main_loop:[^ ]+]] = icmp slt i32 %idx.next, [[exit_main_loop_at_loclamp]]
 ; CHECK: br i1 [[continue_main_loop]], label %loop, label %main.exit.selector
 

llvm/trunk/test/Transforms/IRCE/single-access-with-preloop.ll

exit:
   ret void
 }
 
 ; CHECK-LABEL: @single_access_with_preloop(
 ; CHECK: loop.preheader:
 ; CHECK: [[check_min_sint_offset:[^ ]+]] = icmp sgt i32 %offset, -2147483647
 ; CHECK: [[safe_offset_preloop:[^ ]+]] = select i1 [[check_min_sint_offset]], i32 %offset, i32 -2147483647
 ; If Offset was a SINT_MIN, we could have an overflow here. That is why we calculated its safe version.
-; CHECK: [[not_safe_start:[^ ]+]] = add i32 [[safe_offset_preloop]], -1
-; CHECK: [[not_n:[^ ]+]] = sub i32 -1, %n
-; CHECK: [[not_exit_preloop_at_cond_loclamp:[^ ]+]] = icmp sgt i32 [[not_safe_start]], [[not_n]]
-; CHECK: [[not_exit_preloop_at_loclamp:[^ ]+]] = select i1 [[not_exit_preloop_at_cond_loclamp]], i32 [[not_safe_start]], i32 [[not_n]]
-; CHECK: [[exit_preloop_at_loclamp:[^ ]+]] = sub i32 -1, [[not_exit_preloop_at_loclamp]]
+; CHECK: [[safe_start:[^ ]+]] = sub i32 0, [[safe_offset_preloop]]
+; CHECK: [[exit_preloop_at_cond_loclamp:[^ ]+]] = icmp slt i32 %n, [[safe_start]]
+; CHECK: [[exit_preloop_at_loclamp:[^ ]+]] = select i1 [[exit_preloop_at_cond_loclamp]], i32 %n, i32 [[safe_start]]
 ; CHECK: [[exit_preloop_at_cond:[^ ]+]] = icmp sgt i32 [[exit_preloop_at_loclamp]], 0
 ; CHECK: [[exit_preloop_at:[^ ]+]] = select i1 [[exit_preloop_at_cond]], i32 [[exit_preloop_at_loclamp]], i32 0
 
 
 ; CHECK: [[len_minus_sint_max:[^ ]+]] = add i32 %len, -2147483647
 ; CHECK: [[check_len_min_sint_offset:[^ ]+]] = icmp sgt i32 %offset, [[len_minus_sint_max]]
 ; CHECK: [[safe_offset_mainloop:[^ ]+]] = select i1 [[check_len_min_sint_offset]], i32 %offset, i32 [[len_minus_sint_max]]
-; CHECK: [[not_safe_start_2:[^ ]+]] = add i32 [[safe_offset_mainloop]], -1
 ; If Offset was a SINT_MIN, we could have an overflow here. That is why we calculated its safe version.
-; CHECK: [[not_safe_upper_end:[^ ]+]] = sub i32 [[not_safe_start_2]], %len
-; CHECK: [[not_exit_mainloop_at_cond_loclamp:[^ ]+]] = icmp sgt i32 [[not_safe_upper_end]], [[not_n]]
-; CHECK: [[not_exit_mainloop_at_loclamp:[^ ]+]] = select i1 [[not_exit_mainloop_at_cond_loclamp]], i32 [[not_safe_upper_end]], i32 [[not_n]]
+; CHECK: [[safe_upper_end:[^ ]+]] = sub i32 %len, [[safe_offset_mainloop]]
+; CHECK: [[exit_mainloop_at_cond_loclamp:[^ ]+]] = icmp slt i32 %n, [[safe_upper_end]]
+; CHECK: [[exit_mainloop_at_loclamp:[^ ]+]] = select i1 [[exit_mainloop_at_cond_loclamp]], i32 %n, i32 [[safe_upper_end]]
 ; CHECK: [[check_offset_mainloop_2:[^ ]+]] = icmp sgt i32 %offset, 0
 ; CHECK: [[safe_offset_mainloop_2:[^ ]+]] = select i1 [[check_offset_mainloop_2]], i32 %offset, i32 0
-; CHECK: [[not_safe_lower_end:[^ ]+]] = add i32 [[safe_offset_mainloop_2]], -2147483648
-; CHECK: [[not_exit_mainloop_at_cond_hiclamp:[^ ]+]] = icmp sgt i32 [[not_exit_mainloop_at_loclamp]], [[not_safe_lower_end]]
-; CHECK: [[not_exit_mainloop_at_hiclamp:[^ ]+]] = select i1 [[not_exit_mainloop_at_cond_hiclamp]], i32 [[not_exit_mainloop_at_loclamp]], i32 [[not_safe_lower_end]]
-; CHECK: [[exit_mainloop_at_hiclamp:[^ ]+]] = sub i32 -1, [[not_exit_mainloop_at_hiclamp]]
+; CHECK: [[safe_lower_end:[^ ]+]] = sub i32 2147483647, [[safe_offset_mainloop_2]]
+; CHECK: [[exit_mainloop_at_cond_hiclamp:[^ ]+]] = icmp slt i32 [[exit_mainloop_at_loclamp]], [[safe_lower_end]]
+; CHECK: [[exit_mainloop_at_hiclamp:[^ ]+]] = select i1 [[exit_mainloop_at_cond_hiclamp]], i32 [[exit_mainloop_at_loclamp]], i32 [[safe_lower_end]]
 ; CHECK: [[exit_mainloop_at_cmp:[^ ]+]] = icmp sgt i32 [[exit_mainloop_at_hiclamp]], 0
 ; CHECK: [[exit_mainloop_at:[^ ]+]] = select i1 [[exit_mainloop_at_cmp]], i32 [[exit_mainloop_at_hiclamp]], i32 0
 
 ; CHECK: mainloop:
 ; CHECK: br label %loop
 
 ; CHECK: loop:
 ; CHECK: %abc.high = icmp slt i32 %array.idx, %len
 ; CHECK: %abc.low = icmp sge i32 %array.idx, 0
 ; CHECK: %abc = and i1 true, true
-; CHECK: br i1 %abc, label %in.bounds, label %out.of.bounds.loopexit11
+; CHECK: br i1 %abc, label %in.bounds, label %[[loopexit:[^ ,]+]]
 
 ; CHECK: in.bounds:
 ; CHECK: [[continue_mainloop_cond:[^ ]+]] = icmp slt i32 %idx.next, [[exit_mainloop_at]]
 ; CHECK: br i1 [[continue_mainloop_cond]], label %loop, label %main.exit.selector
 
 ; CHECK: main.exit.selector:
 ; CHECK: [[mainloop_its_left:[^ ]+]] = icmp slt i32 %idx.next.lcssa, %n
 ; CHECK: br i1 [[mainloop_its_left]], label %main.pseudo.exit, label %exit.loopexit

llvm/trunk/test/Transforms/IRCE/unsigned_comparisons_ugt.ll

 
 ; UGT condition for decreasing loop.
 define void @test_02(i32* %arr, i32* %a_len_ptr) #0 {
 
 ; CHECK: test_02(
 ; CHECK:        entry:
 ; CHECK-NEXT:     %len = load i32, i32* %a_len_ptr, !range !0
 ; CHECK-NEXT:     [[COND1:%[^ ]+]] = icmp ugt i32 %len, 1
-; CHECK-NEXT:     %umax = select i1 [[COND1]], i32 %len, i32 1
-; CHECK-NEXT:     %exit.preloop.at = add i32 %umax, -1
+; CHECK-NEXT:     [[UMIN:%[^ ]+]] = select i1 [[COND1]], i32 %len, i32 1
+; CHECK-NEXT:     %exit.preloop.at = add i32 [[UMIN]], -1
 ; CHECK-NEXT:     [[COND2:%[^ ]+]] = icmp ugt i32 100, %exit.preloop.at
 ; CHECK-NEXT:     br i1 [[COND2]], label %loop.preloop.preheader, label %preloop.pseudo.exit
 ; CHECK:        mainloop:
 ; CHECK-NEXT:     br label %loop
 ; CHECK:        loop:
 ; CHECK-NEXT:     %idx = phi i32 [ %idx.preloop.copy, %mainloop ], [ %idx.next, %in.bounds ]
 ; CHECK-NEXT:     %idx.next = add i32 %idx, -1
 ; CHECK-NEXT:     %abc = icmp ult i32 %idx, %len

 
 ; Check SINT_MAX + 1, test is similar to test_02.
 define void @test_04(i32* %arr, i32* %a_len_ptr) #0 {
 
 ; CHECK: test_04(
 ; CHECK:        entry:
 ; CHECK-NEXT:     %len = load i32, i32* %a_len_ptr, !range !0
 ; CHECK-NEXT:     [[COND1:%[^ ]+]] = icmp ugt i32 %len, 1
-; CHECK-NEXT:     %umax = select i1 [[COND1]], i32 %len, i32 1
-; CHECK-NEXT:     %exit.preloop.at = add i32 %umax, -1
+; CHECK-NEXT:     [[UMIN:%[^ ]+]] = select i1 [[COND1]], i32 %len, i32 1
+; CHECK-NEXT:     %exit.preloop.at = add i32 [[UMIN]], -1
 ; CHECK-NEXT:     [[COND2:%[^ ]+]] = icmp ugt i32 -2147483648, %exit.preloop.at
 ; CHECK-NEXT:     br i1 [[COND2]], label %loop.preloop.preheader, label %preloop.pseudo.exit
 ; CHECK:        mainloop:
 ; CHECK-NEXT:     br label %loop
 ; CHECK:        loop:
 ; CHECK-NEXT:     %idx = phi i32 [ %idx.preloop.copy, %mainloop ], [ %idx.next, %in.bounds ]
 ; CHECK-NEXT:     %idx.next = add i32 %idx, -1
 ; CHECK-NEXT:     %abc = icmp ult i32 %idx, %len

llvm/trunk/test/Transforms/IRCE/unsigned_comparisons_ult.ll

 
 ; ULT condition for decreasing loops.
 define void @test_02(i32* %arr, i32* %a_len_ptr) #0 {
 
 ; CHECK: test_02(
 ; CHECK:        entry:
 ; CHECK-NEXT:     %len = load i32, i32* %a_len_ptr, !range !0
 ; CHECK-NEXT:     [[COND1:%[^ ]+]] = icmp ugt i32 %len, 1
-; CHECK-NEXT:     %umax = select i1 [[COND1]], i32 %len, i32 1
-; CHECK-NEXT:     %exit.preloop.at = add i32 %umax, -1
+; CHECK-NEXT:     [[UMIN:%[^ ]+]] = select i1 [[COND1]], i32 %len, i32 1
+; CHECK-NEXT:     %exit.preloop.at = add i32 [[UMIN]], -1
 ; CHECK-NEXT:     [[COND2:%[^ ]+]] = icmp ugt i32 100, %exit.preloop.at
 ; CHECK-NEXT:     br i1 [[COND2]], label %loop.preloop.preheader, label %preloop.pseudo.exit
 ; CHECK:        mainloop:
 ; CHECK-NEXT:     br label %loop
 ; CHECK:        loop:
 ; CHECK-NEXT:     %idx = phi i32 [ %idx.preloop.copy, %mainloop ], [ %idx.next, %in.bounds ]
 ; CHECK-NEXT:     %idx.next = add i32 %idx, -1
 ; CHECK-NEXT:     %abc = icmp ult i32 %idx, %len

 }
 
 ; Check SINT_MAX + 1, test is similar to test_02.
 define void @test_05(i32* %arr, i32* %a_len_ptr) #0 {
 ; CHECK: test_05(
 ; CHECK:        entry:
 ; CHECK-NEXT:     %len = load i32, i32* %a_len_ptr, !range !0
 ; CHECK-NEXT:     [[COND1:%[^ ]+]] = icmp ugt i32 %len, 1
-; CHECK-NEXT:     %umax = select i1 [[COND1]], i32 %len, i32 1
-; CHECK-NEXT:     %exit.preloop.at = add i32 %umax, -1
+; CHECK-NEXT:     [[UMIN:%[^ ]+]] = select i1 [[COND1]], i32 %len, i32 1
+; CHECK-NEXT:     %exit.preloop.at = add i32 [[UMIN]], -1
 ; CHECK-NEXT:     [[COND2:%[^ ]+]] = icmp ugt i32 -2147483648, %exit.preloop.at
 ; CHECK-NEXT:     br i1 [[COND2]], label %loop.preloop.preheader, label %preloop.pseudo.exit
 ; CHECK:        mainloop:
 ; CHECK-NEXT:     br label %loop
 ; CHECK:        loop:
 ; CHECK-NEXT:     %idx = phi i32 [ %idx.preloop.copy, %mainloop ], [ %idx.next, %in.bounds ]
 ; CHECK-NEXT:     %idx.next = add i32 %idx, -1
 ; CHECK-NEXT:     %abc = icmp ult i32 %idx, %len

llvm/trunk/test/Transforms/IndVarSimplify/replace-loop-exit-folds.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -indvars -S < %s | FileCheck %s
 
 target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
 
 define i32 @remove_loop(i32 %size) {
 ; CHECK-LABEL: @remove_loop(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[TMP0:%.*]] = sub i32 -1, [[SIZE:%.*]]
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp ugt i32 [[TMP0]], -32
-; CHECK-NEXT:    [[UMAX:%.*]] = select i1 [[TMP1]], i32 [[TMP0]], i32 -32
-; CHECK-NEXT:    [[TMP2:%.*]] = add i32 [[SIZE]], [[UMAX]]
-; CHECK-NEXT:    [[TMP3:%.*]] = add i32 [[TMP2]], 32
-; CHECK-NEXT:    [[TMP4:%.*]] = lshr i32 [[TMP3]], 5
-; CHECK-NEXT:    [[TMP5:%.*]] = shl i32 [[TMP4]], 5
+; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[SIZE:%.*]], 31
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i32 [[SIZE]], 31
+; CHECK-NEXT:    [[UMAX:%.*]] = select i1 [[TMP1]], i32 [[SIZE]], i32 31
+; CHECK-NEXT:    [[TMP2:%.*]] = sub i32 [[TMP0]], [[UMAX]]
+; CHECK-NEXT:    [[TMP3:%.*]] = lshr i32 [[TMP2]], 5
+; CHECK-NEXT:    [[TMP4:%.*]] = shl i32 [[TMP3]], 5
 ; CHECK-NEXT:    br label [[WHILE_COND:%.*]]
 ; CHECK:       while.cond:
 ; CHECK-NEXT:    [[SIZE_ADDR_0:%.*]] = phi i32 [ [[SIZE]], [[ENTRY:%.*]] ], [ [[SUB:%.*]], [[WHILE_COND]] ]
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i32 [[SIZE_ADDR_0]], 31
 ; CHECK-NEXT:    [[SUB]] = add i32 [[SIZE_ADDR_0]], -32
 ; CHECK-NEXT:    br i1 [[CMP]], label [[WHILE_COND]], label [[WHILE_END:%.*]]
 ; CHECK:       while.end:
-; CHECK-NEXT:    [[TMP6:%.*]] = sub i32 [[SIZE]], [[TMP5]]
-; CHECK-NEXT:    ret i32 [[TMP6]]
+; CHECK-NEXT:    [[TMP5:%.*]] = sub i32 [[SIZE]], [[TMP4]]
+; CHECK-NEXT:    ret i32 [[TMP5]]
 ;
 entry:
   br label %while.cond
 
 while.cond:                                       ; preds = %while.cond, %entry
   %size.addr.0 = phi i32 [ %size, %entry ], [ %sub, %while.cond ]
   %cmp = icmp ugt i32 %size.addr.0, 31
   %sub = add i32 %size.addr.0, -32

llvm/trunk/test/Transforms/LoopStrengthReduce/2013-01-14-ReuseCast.ll

 ; RUN: opt -loop-reduce -S < %s | FileCheck %s
 ;
 ; LTO of clang, which mistakenly uses no TargetLoweringInfo, causes a
 ; miscompile. ReuseOrCreateCast replace ptrtoint operand with undef.
 ; Reproducing the miscompile requires no triple, hence no "TTI".
 ; rdar://13007381
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
 
 ; Verify that nothing uses the "dead" ptrtoint from "undef".
 ; CHECK-LABEL: @VerifyDiagnosticConsumerTest(
 ; CHECK: bb:
 ; "dead" ptrpoint not emitted (or dead code eliminated) with
 ; current LSR cost model.
 ; CHECK-NOT: = ptrtoint i8* undef to i64
 ; CHECK: .lr.ph
-; CHECK: [[TMP:%[^ ]+]] = add i64 %tmp{{[0-9]+}}, -1
-; CHECK: sub i64 [[TMP]], %tmp{{[0-9]+}}
 ; CHECK: ret void
 define void @VerifyDiagnosticConsumerTest() unnamed_addr nounwind uwtable align 2 {
 bb:
   %tmp3 = call i8* @getCharData() nounwind
   %tmp4 = call i8* @getCharData() nounwind
   %tmp5 = ptrtoint i8* %tmp4 to i64
   %tmp6 = ptrtoint i8* %tmp3 to i64
   %tmp7 = sub i64 %tmp5, %tmp6

llvm/trunk/test/Transforms/LoopVectorize/X86/pr35432.ll

 ; CHECK-NEXT:    [[CALL:%.*]] = call i32 (i32*, ...) bitcast (i32 (...)* @goo to i32 (i32*, ...)*)(i32* nonnull [[I]])
 ; CHECK-NEXT:    [[TMP2:%.*]] = load i32, i32* [[I]], align 4
 ; CHECK-NEXT:    [[STOREMERGE6:%.*]] = trunc i32 [[TMP2]] to i16
 ; CHECK-NEXT:    store i16 [[STOREMERGE6]], i16* [[S]], align 2
 ; CHECK-NEXT:    [[CONV17:%.*]] = and i32 [[TMP2]], 65472
 ; CHECK-NEXT:    [[CMP8:%.*]] = icmp eq i32 [[CONV17]], 0
 ; CHECK-NEXT:    br i1 [[CMP8]], label [[FOR_BODY_LR_PH:%.*]], label [[FOR_END12:%.*]]
 ; CHECK:       for.body.lr.ph:
-; CHECK-NEXT:    [[TMP3:%.*]] = sub i32 -1, [[TMP2]]
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.body:
 ; CHECK-NEXT:    [[STOREMERGE_IN9:%.*]] = phi i32 [ [[TMP2]], [[FOR_BODY_LR_PH]] ], [ [[ADD:%.*]], [[FOR_INC9:%.*]] ]
 ; CHECK-NEXT:    [[CONV52:%.*]] = and i32 [[STOREMERGE_IN9]], 255
 ; CHECK-NEXT:    [[CMP63:%.*]] = icmp ult i32 [[TMP2]], [[CONV52]]
 ; CHECK-NEXT:    br i1 [[CMP63]], label [[FOR_BODY8_LR_PH:%.*]], label [[FOR_INC9]]
 ; CHECK:       for.body8.lr.ph:
 ; CHECK-NEXT:    [[CONV3:%.*]] = trunc i32 [[STOREMERGE_IN9]] to i8
 ; CHECK-NEXT:    [[DOTPROMOTED:%.*]] = load i32, i32* getelementptr inbounds ([192 x [192 x i32]], [192 x [192 x i32]]* @a, i64 0, i64 0, i64 0), align 16
-; CHECK-NEXT:    [[TMP4:%.*]] = add i8 [[CONV3]], -1
-; CHECK-NEXT:    [[TMP5:%.*]] = zext i8 [[TMP4]] to i32
-; CHECK-NEXT:    [[TMP6:%.*]] = sub i32 -1, [[TMP5]]
-; CHECK-NEXT:    [[TMP7:%.*]] = icmp ugt i32 [[TMP3]], [[TMP6]]
-; CHECK-NEXT:    [[UMAX:%.*]] = select i1 [[TMP7]], i32 [[TMP3]], i32 [[TMP6]]
-; CHECK-NEXT:    [[TMP8:%.*]] = add i32 [[UMAX]], 2
-; CHECK-NEXT:    [[TMP9:%.*]] = add i32 [[TMP8]], [[TMP5]]
-; CHECK-NEXT:    [[MIN_ITERS_CHECK:%.*]] = icmp ult i32 [[TMP9]], 8
+; CHECK-NEXT:    [[TMP3:%.*]] = add i8 [[CONV3]], -1
+; CHECK-NEXT:    [[TMP4:%.*]] = zext i8 [[TMP3]] to i32
+; CHECK-NEXT:    [[TMP5:%.*]] = add i32 [[TMP4]], 1
+; CHECK-NEXT:    [[TMP6:%.*]] = icmp ult i32 [[TMP2]], [[TMP4]]
+; CHECK-NEXT:    [[UMAX:%.*]] = select i1 [[TMP6]], i32 [[TMP2]], i32 [[TMP4]]
+; CHECK-NEXT:    [[TMP7:%.*]] = sub i32 [[TMP5]], [[UMAX]]
+; CHECK-NEXT:    [[MIN_ITERS_CHECK:%.*]] = icmp ult i32 [[TMP7]], 8
 ; CHECK-NEXT:    br i1 [[MIN_ITERS_CHECK]], label [[SCALAR_PH:%.*]], label [[VECTOR_SCEVCHECK:%.*]]
 ; CHECK:       vector.scevcheck:
-; CHECK-NEXT:    [[TMP10:%.*]] = add i8 [[CONV3]], -1
-; CHECK-NEXT:    [[TMP11:%.*]] = zext i8 [[TMP10]] to i32
-; CHECK-NEXT:    [[TMP12:%.*]] = sub i32 -1, [[TMP11]]
-; CHECK-NEXT:    [[TMP13:%.*]] = icmp ugt i32 [[TMP3]], [[TMP12]]
-; CHECK-NEXT:    [[UMAX1:%.*]] = select i1 [[TMP13]], i32 [[TMP3]], i32 [[TMP12]]
-; CHECK-NEXT:    [[TMP14:%.*]] = add i32 [[UMAX1]], 1
-; CHECK-NEXT:    [[TMP15:%.*]] = add i32 [[TMP14]], [[TMP11]]
-; CHECK-NEXT:    [[TMP16:%.*]] = trunc i32 [[TMP15]] to i8
-; CHECK-NEXT:    [[MUL:%.*]] = call { i8, i1 } @llvm.umul.with.overflow.i8(i8 1, i8 [[TMP16]])
+; CHECK-NEXT:    [[TMP8:%.*]] = add i8 [[CONV3]], -1
+; CHECK-NEXT:    [[TMP9:%.*]] = zext i8 [[TMP8]] to i32
+; CHECK-NEXT:    [[TMP10:%.*]] = icmp ult i32 [[TMP2]], [[TMP9]]
+; CHECK-NEXT:    [[UMAX1:%.*]] = select i1 [[TMP10]], i32 [[TMP2]], i32 [[TMP9]]
+; CHECK-NEXT:    [[TMP11:%.*]] = sub i32 [[TMP9]], [[UMAX1]]
+; CHECK-NEXT:    [[TMP12:%.*]] = trunc i32 [[TMP11]] to i8
+; CHECK-NEXT:    [[MUL:%.*]] = call { i8, i1 } @llvm.umul.with.overflow.i8(i8 1, i8 [[TMP12]])
 ; CHECK-NEXT:    [[MUL_RESULT:%.*]] = extractvalue { i8, i1 } [[MUL]], 0
 ; CHECK-NEXT:    [[MUL_OVERFLOW:%.*]] = extractvalue { i8, i1 } [[MUL]], 1
-; CHECK-NEXT:    [[TMP17:%.*]] = add i8 [[TMP10]], [[MUL_RESULT]]
-; CHECK-NEXT:    [[TMP18:%.*]] = sub i8 [[TMP10]], [[MUL_RESULT]]
-; CHECK-NEXT:    [[TMP19:%.*]] = icmp ugt i8 [[TMP18]], [[TMP10]]
-; CHECK-NEXT:    [[TMP20:%.*]] = icmp ult i8 [[TMP17]], [[TMP10]]
-; CHECK-NEXT:    [[TMP21:%.*]] = select i1 true, i1 [[TMP19]], i1 [[TMP20]]
-; CHECK-NEXT:    [[TMP22:%.*]] = icmp ugt i32 [[TMP15]], 255
-; CHECK-NEXT:    [[TMP23:%.*]] = or i1 [[TMP21]], [[TMP22]]
-; CHECK-NEXT:    [[TMP24:%.*]] = or i1 [[TMP23]], [[MUL_OVERFLOW]]
-; CHECK-NEXT:    [[TMP25:%.*]] = or i1 false, [[TMP24]]
-; CHECK-NEXT:    br i1 [[TMP25]], label [[SCALAR_PH]], label [[VECTOR_PH:%.*]]
+; CHECK-NEXT:    [[TMP13:%.*]] = add i8 [[TMP8]], [[MUL_RESULT]]
+; CHECK-NEXT:    [[TMP14:%.*]] = sub i8 [[TMP8]], [[MUL_RESULT]]
+; CHECK-NEXT:    [[TMP15:%.*]] = icmp ugt i8 [[TMP14]], [[TMP8]]
+; CHECK-NEXT:    [[TMP16:%.*]] = icmp ult i8 [[TMP13]], [[TMP8]]
+; CHECK-NEXT:    [[TMP17:%.*]] = select i1 true, i1 [[TMP15]], i1 [[TMP16]]
+; CHECK-NEXT:    [[TMP18:%.*]] = icmp ugt i32 [[TMP11]], 255
+; CHECK-NEXT:    [[TMP19:%.*]] = or i1 [[TMP17]], [[TMP18]]
+; CHECK-NEXT:    [[TMP20:%.*]] = or i1 [[TMP19]], [[MUL_OVERFLOW]]
+; CHECK-NEXT:    [[TMP21:%.*]] = or i1 false, [[TMP20]]
+; CHECK-NEXT:    br i1 [[TMP21]], label [[SCALAR_PH]], label [[VECTOR_PH:%.*]]
 ; CHECK:       vector.ph:
-; CHECK-NEXT:    [[N_MOD_VF:%.*]] = urem i32 [[TMP9]], 8
-; CHECK-NEXT:    [[N_VEC:%.*]] = sub i32 [[TMP9]], [[N_MOD_VF]]
+; CHECK-NEXT:    [[N_MOD_VF:%.*]] = urem i32 [[TMP7]], 8
+; CHECK-NEXT:    [[N_VEC:%.*]] = sub i32 [[TMP7]], [[N_MOD_VF]]
 ; CHECK-NEXT:    [[CAST_CRD:%.*]] = trunc i32 [[N_VEC]] to i8
 ; CHECK-NEXT:    [[IND_END:%.*]] = sub i8 [[CONV3]], [[CAST_CRD]]
-; CHECK-NEXT:    [[TMP26:%.*]] = insertelement <4 x i32> zeroinitializer, i32 [[DOTPROMOTED]], i32 0
+; CHECK-NEXT:    [[TMP22:%.*]] = insertelement <4 x i32> zeroinitializer, i32 [[DOTPROMOTED]], i32 0
 ; CHECK-NEXT:    br label [[VECTOR_BODY:%.*]]
 ; CHECK:       vector.body:
 ; CHECK-NEXT:    [[INDEX:%.*]] = phi i32 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ]
-; CHECK-NEXT:    [[VEC_PHI:%.*]] = phi <4 x i32> [ [[TMP26]], [[VECTOR_PH]] ], [ [[TMP30:%.*]], [[VECTOR_BODY]] ]
-; CHECK-NEXT:    [[VEC_PHI2:%.*]] = phi <4 x i32> [ zeroinitializer, [[VECTOR_PH]] ], [ [[TMP31:%.*]], [[VECTOR_BODY]] ]
-; CHECK-NEXT:    [[TMP27:%.*]] = trunc i32 [[INDEX]] to i8
-; CHECK-NEXT:    [[OFFSET_IDX:%.*]] = sub i8 [[CONV3]], [[TMP27]]
+; CHECK-NEXT:    [[VEC_PHI:%.*]] = phi <4 x i32> [ [[TMP22]], [[VECTOR_PH]] ], [ [[TMP26:%.*]], [[VECTOR_BODY]] ]
+; CHECK-NEXT:    [[VEC_PHI2:%.*]] = phi <4 x i32> [ zeroinitializer, [[VECTOR_PH]] ], [ [[TMP27:%.*]], [[VECTOR_BODY]] ]
+; CHECK-NEXT:    [[TMP23:%.*]] = trunc i32 [[INDEX]] to i8
+; CHECK-NEXT:    [[OFFSET_IDX:%.*]] = sub i8 [[CONV3]], [[TMP23]]
 ; CHECK-NEXT:    [[BROADCAST_SPLATINSERT:%.*]] = insertelement <4 x i8> undef, i8 [[OFFSET_IDX]], i32 0
 ; CHECK-NEXT:    [[BROADCAST_SPLAT:%.*]] = shufflevector <4 x i8> [[BROADCAST_SPLATINSERT]], <4 x i8> undef, <4 x i32> zeroinitializer
 ; CHECK-NEXT:    [[INDUCTION:%.*]] = add <4 x i8> [[BROADCAST_SPLAT]], <i8 0, i8 -1, i8 -2, i8 -3>
 ; CHECK-NEXT:    [[INDUCTION3:%.*]] = add <4 x i8> [[BROADCAST_SPLAT]], <i8 -4, i8 -5, i8 -6, i8 -7>
-; CHECK-NEXT:    [[TMP28:%.*]] = add i8 [[OFFSET_IDX]], 0
-; CHECK-NEXT:    [[TMP29:%.*]] = add i8 [[OFFSET_IDX]], -4
-; CHECK-NEXT:    [[TMP30]] = add <4 x i32> [[VEC_PHI]], <i32 1, i32 1, i32 1, i32 1>
-; CHECK-NEXT:    [[TMP31]] = add <4 x i32> [[VEC_PHI2]], <i32 1, i32 1, i32 1, i32 1>
-; CHECK-NEXT:    [[TMP32:%.*]] = add i8 [[TMP28]], -1
-; CHECK-NEXT:    [[TMP33:%.*]] = add i8 [[TMP29]], -1
-; CHECK-NEXT:    [[TMP34:%.*]] = zext i8 [[TMP32]] to i32
-; CHECK-NEXT:    [[TMP35:%.*]] = zext i8 [[TMP33]] to i32
+; CHECK-NEXT:    [[TMP24:%.*]] = add i8 [[OFFSET_IDX]], 0
+; CHECK-NEXT:    [[TMP25:%.*]] = add i8 [[OFFSET_IDX]], -4
+; CHECK-NEXT:    [[TMP26]] = add <4 x i32> [[VEC_PHI]], <i32 1, i32 1, i32 1, i32 1>
+; CHECK-NEXT:    [[TMP27]] = add <4 x i32> [[VEC_PHI2]], <i32 1, i32 1, i32 1, i32 1>
+; CHECK-NEXT:    [[TMP28:%.*]] = add i8 [[TMP24]], -1
+; CHECK-NEXT:    [[TMP29:%.*]] = add i8 [[TMP25]], -1
+; CHECK-NEXT:    [[TMP30:%.*]] = zext i8 [[TMP28]] to i32
+; CHECK-NEXT:    [[TMP31:%.*]] = zext i8 [[TMP29]] to i32
 ; CHECK-NEXT:    [[INDEX_NEXT]] = add i32 [[INDEX]], 8
-; CHECK-NEXT:    [[TMP36:%.*]] = icmp eq i32 [[INDEX_NEXT]], [[N_VEC]]
-; CHECK-NEXT:    br i1 [[TMP36]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop !0
+; CHECK-NEXT:    [[TMP32:%.*]] = icmp eq i32 [[INDEX_NEXT]], [[N_VEC]]
+; CHECK-NEXT:    br i1 [[TMP32]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop !0
 ; CHECK:       middle.block:
-; CHECK-NEXT:    [[BIN_RDX:%.*]] = add <4 x i32> [[TMP31]], [[TMP30]]
+; CHECK-NEXT:    [[BIN_RDX:%.*]] = add <4 x i32> [[TMP27]], [[TMP26]]
 ; CHECK-NEXT:    [[RDX_SHUF:%.*]] = shufflevector <4 x i32> [[BIN_RDX]], <4 x i32> undef, <4 x i32> <i32 2, i32 3, i32 undef, i32 undef>
 ; CHECK-NEXT:    [[BIN_RDX4:%.*]] = add <4 x i32> [[BIN_RDX]], [[RDX_SHUF]]
 ; CHECK-NEXT:    [[RDX_SHUF5:%.*]] = shufflevector <4 x i32> [[BIN_RDX4]], <4 x i32> undef, <4 x i32> <i32 1, i32 undef, i32 undef, i32 undef>
 ; CHECK-NEXT:    [[BIN_RDX6:%.*]] = add <4 x i32> [[BIN_RDX4]], [[RDX_SHUF5]]
-; CHECK-NEXT:    [[TMP37:%.*]] = extractelement <4 x i32> [[BIN_RDX6]], i32 0
-; CHECK-NEXT:    [[CMP_N:%.*]] = icmp eq i32 [[TMP9]], [[N_VEC]]
+; CHECK-NEXT:    [[TMP33:%.*]] = extractelement <4 x i32> [[BIN_RDX6]], i32 0
+; CHECK-NEXT:    [[CMP_N:%.*]] = icmp eq i32 [[TMP7]], [[N_VEC]]
 ; CHECK-NEXT:    br i1 [[CMP_N]], label [[FOR_COND4_FOR_INC9_CRIT_EDGE:%.*]], label [[SCALAR_PH]]
 ; CHECK:       scalar.ph:
 ; CHECK-NEXT:    [[BC_RESUME_VAL:%.*]] = phi i8 [ [[IND_END]], [[MIDDLE_BLOCK]] ], [ [[CONV3]], [[FOR_BODY8_LR_PH]] ], [ [[CONV3]], [[VECTOR_SCEVCHECK]] ]
-; CHECK-NEXT:    [[BC_MERGE_RDX:%.*]] = phi i32 [ [[DOTPROMOTED]], [[FOR_BODY8_LR_PH]] ], [ [[DOTPROMOTED]], [[VECTOR_SCEVCHECK]] ], [ [[TMP37]], [[MIDDLE_BLOCK]] ]
+; CHECK-NEXT:    [[BC_MERGE_RDX:%.*]] = phi i32 [ [[DOTPROMOTED]], [[FOR_BODY8_LR_PH]] ], [ [[DOTPROMOTED]], [[VECTOR_SCEVCHECK]] ], [ [[TMP33]], [[MIDDLE_BLOCK]] ]
 ; CHECK-NEXT:    br label [[FOR_BODY8:%.*]]
 ; CHECK:       for.body8:
 ; CHECK-NEXT:    [[INC5:%.*]] = phi i32 [ [[BC_MERGE_RDX]], [[SCALAR_PH]] ], [ [[INC:%.*]], [[FOR_BODY8]] ]
 ; CHECK-NEXT:    [[C_04:%.*]] = phi i8 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[DEC:%.*]], [[FOR_BODY8]] ]
 ; CHECK-NEXT:    [[INC]] = add i32 [[INC5]], 1
 ; CHECK-NEXT:    [[DEC]] = add i8 [[C_04]], -1
 ; CHECK-NEXT:    [[CONV5:%.*]] = zext i8 [[DEC]] to i32
 ; CHECK-NEXT:    [[CMP6:%.*]] = icmp ult i32 [[TMP2]], [[CONV5]]
 ; CHECK-NEXT:    br i1 [[CMP6]], label [[FOR_BODY8]], label [[FOR_COND4_FOR_INC9_CRIT_EDGE]], !llvm.loop !2
 ; CHECK:       for.cond4.for.inc9_crit_edge:
-; CHECK-NEXT:    [[INC_LCSSA:%.*]] = phi i32 [ [[INC]], [[FOR_BODY8]] ], [ [[TMP37]], [[MIDDLE_BLOCK]] ]
+; CHECK-NEXT:    [[INC_LCSSA:%.*]] = phi i32 [ [[INC]], [[FOR_BODY8]] ], [ [[TMP33]], [[MIDDLE_BLOCK]] ]
 ; CHECK-NEXT:    store i32 [[INC_LCSSA]], i32* getelementptr inbounds ([192 x [192 x i32]], [192 x [192 x i32]]* @a, i64 0, i64 0, i64 0), align 16
 ; CHECK-NEXT:    br label [[FOR_INC9]]
 ; CHECK:       for.inc9:
 ; CHECK-NEXT:    [[CONV10:%.*]] = and i32 [[STOREMERGE_IN9]], 65535
 ; CHECK-NEXT:    [[ADD]] = add nuw nsw i32 [[CONV10]], 1
 ; CHECK-NEXT:    [[CONV1:%.*]] = and i32 [[ADD]], 65472
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[CONV1]], 0
 ; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY]], label [[FOR_COND_FOR_END12_CRIT_EDGE:%.*]]