[EarlyCSE] hoist div/rem when sibling op exists (PR31028)

[spatel]

Summary

This is a more general solution to the SimplifyCFG transform in D30910 as suggested by Eli. It's not quite an "elimination", so we may be stretching the definition of "CSE". I've tried to make the intent clear in the code comments.

1. I'm re-using the existing "DivOpInfo" struct as the hash table key. So the BypassSlowDivision changes are just to move that to a header to make it visible to EarlyCSE. We could change the name (DivRemKey?), but I didn't want to pollute this patch with the cosmetic diffs. Let me know if I should make either of those changes as a pre-commit.

2. There's a TTI-cost-based bailout for targets where hoisting a remainder could be more expensive than we'd like. That was another suggestion from D30910. The last test triggers that check because an i128 mul op is not legal on x86-64, so that mul has cost = 2. We can probably make a more flexible cost calculation, but this should conservatively prevent the transform if a target doesn't have an appropriate mul instruction.

3. The first 7 tests (4 positive and 3 negative) are copied from D30910. I think this solution covers anything we could do in SimplifyCFG, so I'll remove those tests from SimplifyCFG and abandon that patch if this is approved. We get the same improvements to the final x86 and AArch64 asm with this patch.

[spatel]

Ping.

[spatel]

Ping * 2.

[• dberlin]

I dunno. Does EarlyCSE do any other insertion?
I'm somewhat wary.
My general feeling is the insertion should be separate from the rest of what it does, but i understand that's hard in earlycse because it does not really produce an analysis.
I just feel weird be shoving more stuff in there :)
*especially* cost based stuff.

I'd actually feel better even if you did this in GVN or something that at least does insertion right now, even if that's not quite a great solution either.

[spatel]

In D31037#714596, @dberlin wrote:

I dunno. Does EarlyCSE do any other insertion?

This is my first experience with EarlyCSE, but I don't think there's anything else that moves an instruction. Everything else is killing from what I see.

I'm somewhat wary.
My general feeling is the insertion should be separate from the rest of what it does, but i understand that's hard in earlycse because it does not really produce an analysis.
I just feel weird be shoving more stuff in there :)
*especially* cost based stuff.

TTI was here of course, but yes, using the cost model is another potential precedent. :)

I'd actually feel better even if you did this in GVN or something that at least does insertion right now, even if that's not quite a great solution either.

OK, I'll have a (first) look at GVN.

[• dberlin]

(i am generalizing the ability to have instructions that are not in the IR in the value number tables, for NewGVN, but no reason to depend on that for now)

[spatel]

In D31037#714685, @dberlin wrote:

(i am generalizing the ability to have instructions that are not in the IR in the value number tables, for NewGVN, but no reason to depend on that for now)

I (finally) got around to looking at NewGVN by way of PR34228 ( https://bugs.llvm.org/show_bug.cgi?id=34228 ), and this functionality doesn't fit there either based on my limited understanding.

We don't want to keep adding weird stuff into existing passes, so are there objections to making this into a new single-purpose "hoist-div-rem" pass just for this transform?

[spatel]

Abandoning in favor of a stand-alone pass to do the same thing (D37121).

include/llvm/Transforms/Utils/BypassSlowDivision.h

 
 #ifndef LLVM_TRANSFORMS_UTILS_BYPASSSLOWDIVISION_H
 #define LLVM_TRANSFORMS_UTILS_BYPASSSLOWDIVISION_H
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/IR/Function.h"
 
 namespace llvm {
+struct DivOpInfo {
+  bool SignedOp;
+  Value *Dividend;
+  Value *Divisor;
+
+  DivOpInfo(bool InSignedOp, Value *InDividend, Value *InDivisor)
+      : SignedOp(InSignedOp), Dividend(InDividend), Divisor(InDivisor) {}
+};
+
+template <> struct DenseMapInfo<DivOpInfo> {
+  static bool isEqual(const DivOpInfo &Val1, const DivOpInfo &Val2) {
+    return Val1.SignedOp == Val2.SignedOp && Val1.Dividend == Val2.Dividend &&
+           Val1.Divisor == Val2.Divisor;
+  }
+
+  static DivOpInfo getEmptyKey() { return DivOpInfo(false, nullptr, nullptr); }
+
+  static DivOpInfo getTombstoneKey() {
+    return DivOpInfo(true, nullptr, nullptr);
+  }
+
+  static unsigned getHashValue(const DivOpInfo &Val) {
+    return (unsigned)(reinterpret_cast<uintptr_t>(Val.Dividend) ^
+                      reinterpret_cast<uintptr_t>(Val.Divisor)) ^
+           (unsigned)Val.SignedOp;
+  }
+};
 
 /// This optimization identifies DIV instructions in a BB that can be
 /// profitably bypassed and carried out with a shorter, faster divide.
 ///
 /// This optimization may add basic blocks immediately after BB; for obvious
 /// reasons, you shouldn't pass those blocks to bypassSlowDivision.
 bool bypassSlowDivision(
     BasicBlock *BB, const DenseMap<unsigned int, unsigned int> &BypassWidth);
 
 } // End llvm namespace
 
 #endif

lib/Transforms/Scalar/EarlyCSE.cpp

 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/RecyclingAllocator.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Scalar.h"
+#include "llvm/Transforms/Utils/BypassSlowDivision.h"
 #include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Transforms/Utils/MemorySSA.h"
 #include "llvm/Transforms/Utils/MemorySSAUpdater.h"
 #include <deque>
 using namespace llvm;
 using namespace llvm::PatternMatch;
 
 #define DEBUG_TYPE "early-cse"
public:
   /// \brief A scoped hash table of the current values of read-only call
   /// values.
   ///
   /// It uses the same generation count as loads.
   typedef ScopedHashTable<CallValue, std::pair<Instruction *, unsigned>>
       CallHTType;
   CallHTType AvailableCalls;
 
+  /// A scoped hash table of division and remainder instructions. We use this to
+  /// hoist matching div/rem instructions into the same basic block because
+  /// remainder contains the implicitly shared division.
+  typedef ScopedHashTable<DivOpInfo, Instruction *> DivRemHTType;
+  DivRemHTType AvailableDivRems;
+
   /// \brief This is the current generation of the memory value.
   unsigned CurrentGeneration;
 
   /// \brief Set up the EarlyCSE runner for a particular function.
   EarlyCSE(const TargetLibraryInfo &TLI, const TargetTransformInfo &TTI,
            DominatorTree &DT, AssumptionCache &AC, MemorySSA *MSSA)
       : TLI(TLI), TTI(TTI), DT(DT), AC(AC), MSSA(MSSA),
         MSSAUpdater(make_unique<MemorySSAUpdater>(MSSA)), CurrentGeneration(0) {
   }
 
   bool run();
 
 private:
   // Almost a POD, but needs to call the constructors for the scoped hash
   // tables so that a new scope gets pushed on. These are RAII so that the
   // scope gets popped when the NodeScope is destroyed.
   class NodeScope {
   public:
     NodeScope(ScopedHTType &AvailableValues, LoadHTType &AvailableLoads,
-              CallHTType &AvailableCalls)
+              CallHTType &AvailableCalls, DivRemHTType &AvailableDivRems)
         : Scope(AvailableValues), LoadScope(AvailableLoads),
-          CallScope(AvailableCalls) {}
+          CallScope(AvailableCalls), DivRemScope(AvailableDivRems) {}
 
   private:
     NodeScope(const NodeScope &) = delete;
     void operator=(const NodeScope &) = delete;
 
     ScopedHTType::ScopeTy Scope;
     LoadHTType::ScopeTy LoadScope;
     CallHTType::ScopeTy CallScope;
+    DivRemHTType::ScopeTy DivRemScope;
   };
 
   // Contains all the needed information to create a stack for doing a depth
   // first traversal of the tree. This includes scopes for values, loads, and
   // calls as well as the generation. There is a child iterator so that the
   // children do not need to be store separately.
   class StackNode {
   public:
     StackNode(ScopedHTType &AvailableValues, LoadHTType &AvailableLoads,
-              CallHTType &AvailableCalls, unsigned cg, DomTreeNode *n,
-              DomTreeNode::iterator child, DomTreeNode::iterator end)
+              CallHTType &AvailableCalls, DivRemHTType &AvailableDivRems,
+              unsigned cg, DomTreeNode *n, DomTreeNode::iterator child,
+              DomTreeNode::iterator end)
         : CurrentGeneration(cg), ChildGeneration(cg), Node(n), ChildIter(child),
-          EndIter(end), Scopes(AvailableValues, AvailableLoads, AvailableCalls),
+          EndIter(end), Scopes(AvailableValues, AvailableLoads, AvailableCalls,
+                               AvailableDivRems),
           Processed(false) {}
 
     // Accessors.
     unsigned currentGeneration() { return CurrentGeneration; }
     unsigned childGeneration() { return ChildGeneration; }
     void childGeneration(unsigned generation) { ChildGeneration = generation; }
     DomTreeNode *node() { return Node; }
     DomTreeNode::iterator childIter() { return ChildIter; }
Value *getOrCreateResult(Value *Inst, Type *ExpectedType) const {
     assert(isa<IntrinsicInst>(Inst) && "Instruction not supported");
     return TTI.getOrCreateResultFromMemIntrinsic(cast<IntrinsicInst>(Inst),
                                                  ExpectedType);
   }
 
   bool isSameMemGeneration(unsigned EarlierGeneration, unsigned LaterGeneration,
                            Instruction *EarlierInst, Instruction *LaterInst);
 
+  bool hoistDivRem(Instruction &I);
+
   void removeMSSA(Instruction *Inst) {
     if (!MSSA)
       return;
     // Removing a store here can leave MemorySSA in an unoptimized state by
     // creating MemoryPhis that have identical arguments and by creating
     // MemoryUses whose defining access is not an actual clobber.  We handle the
     // phi case eagerly here.  The non-optimized MemoryUse case is lazily
     // updated by MemorySSA getClobberingMemoryAccess.
bool EarlyCSE::isSameMemGeneration(unsigned EarlierGeneration,
   // LaterInst, if LaterDef dominates EarlierInst then it can't occur between
   // EarlierInst and LaterInst and neither can any other write that potentially
   // clobbers LaterInst.
   MemoryAccess *LaterDef =
       MSSA->getWalker()->getClobberingMemoryAccess(LaterInst);
   return MSSA->dominates(LaterDef, MSSA->getMemoryAccess(EarlierInst));
 }
 
+/// Division is a hidden subexpression of remainder:
+/// X % Y <--> X - ((X / Y) * Y)
+/// If both values are used in this function, we want to calculate them in the
+/// same basic block for performance because the expensive division component
+/// will be shared (either as a unified divrem instruction on the target or by
+/// using the intermediate division result while calcuating remainder). Return
+/// true if a division or remainder is hoisted.
+bool EarlyCSE::hoistDivRem(Instruction &I) {
+  bool IsSigned, IsRem;
+  switch (I.getOpcode()) {
+  case Instruction::SDiv: IsSigned = true;  IsRem = false; break;
+  case Instruction::UDiv: IsSigned = false; IsRem = false; break;
+  case Instruction::SRem: IsSigned = true;  IsRem = true;  break;
+  case Instruction::URem: IsSigned = false; IsRem = true;  break;
+  default: return false;
+  }
+
+  // We are looking for pairs of instructions such as sdiv X, Y and srem X, Y.
+  // Ie, the sign of the operation, the dividend, and the divisor must match.
+  DivOpInfo DivRemKey(IsSigned, I.getOperand(0), I.getOperand(1));
+  if (Instruction *DivRem = AvailableDivRems.lookup(DivRemKey)) {
+    // If the pair is already in the same block, there's nothing to change.
+    if (DivRem->getParent() == I.getParent())
+      return false;
+
+    // Only hoist a remainder instruction if the implicit multiply is cheap. We
+    // may be speculatively executing that extra operation (and the subtract
+    // that we assume is cheap) when the original code did not.
+    if (IsRem && TTI.getArithmeticInstrCost(Instruction::Mul, I.getType()) > 1)
+      return false;
+
+    // Otherwise, hoist this instruction up to its sibling.
+    I.moveBefore(DivRem);
+    return true;
+  }
+
+  // This operation isn't in the hash table yet. Save it.
+  AvailableDivRems.insert(DivRemKey, &I);
+  return false;
+}
+
 bool EarlyCSE::processNode(DomTreeNode *Node) {
   bool Changed = false;
   BasicBlock *BB = Node->getBlock();
 
   // If this block has a single predecessor, then the predecessor is the parent
   // of the domtree node and all of the live out memory values are still current
   // in this block.  If this block has multiple predecessors, then they could
   // have invalidated the live-out memory values of our parent value.  For now,
if (SimpleValue::canHandle(Inst)) {
         Inst->eraseFromParent();
         Changed = true;
         ++NumCSE;
         continue;
       }
 
       // Otherwise, just remember that this value is available.
       AvailableValues.insert(Inst, Inst);
+
+      // And look for an additional CSE opportunity for division and remainder.
+      Changed |= hoistDivRem(*Inst);
       continue;
     }
 
     ParseMemoryInst MemInst(Inst, TTI);
     // If this is a non-volatile load, process it.
     if (MemInst.isValid() && MemInst.isLoad()) {
       // (conservatively) we can't peak past the ordering implied by this
       // operation, but we can add this load to our set of available values
bool EarlyCSE::run() {
   // specific access patterns. For more information see the mailing list
   // discussion on this:
   // http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20120116/135228.html
   std::deque<StackNode *> nodesToProcess;
 
   bool Changed = false;
 
   // Process the root node.
-  nodesToProcess.push_back(new StackNode(
-      AvailableValues, AvailableLoads, AvailableCalls, CurrentGeneration,
-      DT.getRootNode(), DT.getRootNode()->begin(), DT.getRootNode()->end()));
+  nodesToProcess.push_back(
+      new StackNode(AvailableValues, AvailableLoads, AvailableCalls,
+                    AvailableDivRems, CurrentGeneration, DT.getRootNode(),
+                    DT.getRootNode()->begin(), DT.getRootNode()->end()));
 
   // Save the current generation.
   unsigned LiveOutGeneration = CurrentGeneration;
 
   // Process the stack.
   while (!nodesToProcess.empty()) {
     // Grab the first item off the stack. Set the current generation, remove
     // the node from the stack, and process it.
     StackNode *NodeToProcess = nodesToProcess.back();
 
     // Initialize class members.
     CurrentGeneration = NodeToProcess->currentGeneration();
 
     // Check if the node needs to be processed.
     if (!NodeToProcess->isProcessed()) {
       // Process the node.
       Changed |= processNode(NodeToProcess->node());
       NodeToProcess->childGeneration(CurrentGeneration);
       NodeToProcess->process();
     } else if (NodeToProcess->childIter() != NodeToProcess->end()) {
       // Push the next child onto the stack.
       DomTreeNode *child = NodeToProcess->nextChild();
       nodesToProcess.push_back(
           new StackNode(AvailableValues, AvailableLoads, AvailableCalls,
-                        NodeToProcess->childGeneration(), child, child->begin(),
-                        child->end()));
+                        AvailableDivRems, NodeToProcess->childGeneration(),
+                        child, child->begin(), child->end()));
     } else {
       // It has been processed, and there are no more children to process,
       // so delete it and pop it off the stack.
       delete NodeToProcess;
       nodesToProcess.pop_back();
     }
   } // while (!nodes...)
 

lib/Transforms/Utils/BypassSlowDivision.cpp

 #include "llvm/IR/Instructions.h"
 #include "llvm/Transforms/Utils/Local.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "bypass-slow-division"
 
 namespace {
-  struct DivOpInfo {
-    bool SignedOp;
-    Value *Dividend;
-    Value *Divisor;
-
-    DivOpInfo(bool InSignedOp, Value *InDividend, Value *InDivisor)
-      : SignedOp(InSignedOp), Dividend(InDividend), Divisor(InDivisor) {}
-  };
-
   struct QuotRemPair {
     Value *Quotient;
     Value *Remainder;
 
     QuotRemPair(Value *InQuotient, Value *InRemainder)
         : Quotient(InQuotient), Remainder(InRemainder) {}
   };
 
   /// A quotient and remainder, plus a BB from which they logically "originate".
   /// If you use Quotient or Remainder in a Phi node, you should use BB as its
   /// corresponding predecessor.
   struct QuotRemWithBB {
     BasicBlock *BB = nullptr;
     Value *Quotient = nullptr;
     Value *Remainder = nullptr;
   };
 }
 
 namespace llvm {
-  template<>
-  struct DenseMapInfo<DivOpInfo> {
-    static bool isEqual(const DivOpInfo &Val1, const DivOpInfo &Val2) {
-      return Val1.SignedOp == Val2.SignedOp &&
-             Val1.Dividend == Val2.Dividend &&
-             Val1.Divisor == Val2.Divisor;
-    }
-
-    static DivOpInfo getEmptyKey() {
-      return DivOpInfo(false, nullptr, nullptr);
-    }
-
-    static DivOpInfo getTombstoneKey() {
-      return DivOpInfo(true, nullptr, nullptr);
-    }
-
-    static unsigned getHashValue(const DivOpInfo &Val) {
-      return (unsigned)(reinterpret_cast<uintptr_t>(Val.Dividend) ^
-                        reinterpret_cast<uintptr_t>(Val.Divisor)) ^
-                        (unsigned)Val.SignedOp;
-    }
-  };
-
   typedef DenseMap<DivOpInfo, QuotRemPair> DivCacheTy;
   typedef DenseMap<unsigned, unsigned> BypassWidthsTy;
 }
 
 namespace {
 enum ValueRange {
   /// Operand definitely fits into BypassType. No runtime checks are needed.
   VALRNG_SHORT,

test/Transforms/EarlyCSE/div-rem-pairs.ll

+; RUN: opt -early-cse -S < %s | FileCheck %s
+
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-unknown"
+
+; Hoist the sdiv because it's safe and free.
+; PR31028 - https://bugs.llvm.org/show_bug.cgi?id=31028
+
+define i32 @hoist_sdiv(i32 %a, i32 %b) {
+; CHECK-LABEL: @hoist_sdiv(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[DIV:%.*]] = sdiv i32 %a, %b
+; CHECK-NEXT:    [[REM:%.*]] = srem i32 %a, %b
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[REM]], 42
+; CHECK-NEXT:    br i1 [[CMP]], label %if, label %end
+; CHECK:       if:
+; CHECK-NEXT:    br label %end
+; CHECK:       end:
+; CHECK-NEXT:    [[RET:%.*]] = phi i32 [ [[DIV]], %if ], [ 3, %entry ]
+; CHECK-NEXT:    ret i32 [[RET]]
+;
+entry:
+  %rem = srem i32 %a, %b
+  %cmp = icmp eq i32 %rem, 42
+  br i1 %cmp, label %if, label %end
+
+if:
+  %div = sdiv i32 %a, %b
+  br label %end
+
+end:
+  %ret = phi i32 [ %div, %if ], [ 3, %entry ]
+  ret i32 %ret
+}
+
+; Hoist the udiv because it's safe and free.
+
+define i64 @hoist_udiv(i64 %a, i64 %b) {
+; CHECK-LABEL: @hoist_udiv(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[DIV:%.*]] = udiv i64 %a, %b
+; CHECK-NEXT:    [[REM:%.*]] = urem i64 %a, %b
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i64 [[REM]], 42
+; CHECK-NEXT:    br i1 [[CMP]], label %if, label %end
+; CHECK:       if:
+; CHECK-NEXT:    br label %end
+; CHECK:       end:
+; CHECK-NEXT:    [[RET:%.*]] = phi i64 [ [[DIV]], %if ], [ 3, %entry ]
+; CHECK-NEXT:    ret i64 [[RET]]
+;
+entry:
+  %rem = urem i64 %a, %b
+  %cmp = icmp eq i64 %rem, 42
+  br i1 %cmp, label %if, label %end
+
+if:
+  %div = udiv i64 %a, %b
+  br label %end
+
+end:
+  %ret = phi i64 [ %div, %if ], [ 3, %entry ]
+  ret i64 %ret
+}
+
+; Hoist the srem because it's safe and the additional cost over div is not great.
+
+define i16 @hoist_srem(i16 %a, i16 %b) {
+; CHECK-LABEL: @hoist_srem(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[REM:%.*]] = srem i16 %a, %b
+; CHECK-NEXT:    [[DIV:%.*]] = sdiv i16 %a, %b
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i16 [[DIV]], 42
+; CHECK-NEXT:    br i1 [[CMP]], label %if, label %end
+; CHECK:       if:
+; CHECK-NEXT:    br label %end
+; CHECK:       end:
+; CHECK-NEXT:    [[RET:%.*]] = phi i16 [ [[REM]], %if ], [ 3, %entry ]
+; CHECK-NEXT:    ret i16 [[RET]]
+;
+entry:
+  %div = sdiv i16 %a, %b
+  %cmp = icmp eq i16 %div, 42
+  br i1 %cmp, label %if, label %end
+
+if:
+  %rem = srem i16 %a, %b
+  br label %end
+
+end:
+  %ret = phi i16 [ %rem, %if ], [ 3, %entry ]
+  ret i16 %ret
+}
+
+; Hoist the urem because it's safe and the additional cost over div is not great.
+
+define i8 @hoist_urem(i8 %a, i8 %b) {
+; CHECK-LABEL: @hoist_urem(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[REM:%.*]] = urem i8 %a, %b
+; CHECK-NEXT:    [[DIV:%.*]] = udiv i8 %a, %b
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[DIV]], 42
+; CHECK-NEXT:    br i1 [[CMP]], label %if, label %end
+; CHECK:       if:
+; CHECK-NEXT:    br label %end
+; CHECK:       end:
+; CHECK-NEXT:    [[RET:%.*]] = phi i8 [ [[REM]], %if ], [ 3, %entry ]
+; CHECK-NEXT:    ret i8 [[RET]]
+;
+entry:
+  %div = udiv i8 %a, %b
+  %cmp = icmp eq i8 %div, 42
+  br i1 %cmp, label %if, label %end
+
+if:
+  %rem = urem i8 %a, %b
+  br label %end
+
+end:
+  %ret = phi i8 [ %rem, %if ], [ 3, %entry ]
+  ret i8 %ret
+}
+
+; If the ops don't match, don't do anything: signedness.
+
+define i32 @dont_hoist_udiv(i32 %a, i32 %b) {
+; CHECK-LABEL: @dont_hoist_udiv(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[REM:%.*]] = srem i32 %a, %b
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[REM]], 42
+; CHECK-NEXT:    br i1 [[CMP]], label %if, label %end
+; CHECK:       if:
+; CHECK-NEXT:    [[DIV:%.*]] = udiv i32 %a, %b
+; CHECK-NEXT:    br label %end
+; CHECK:       end:
+; CHECK-NEXT:    [[RET:%.*]] = phi i32 [ [[DIV]], %if ], [ 3, %entry ]
+; CHECK-NEXT:    ret i32 [[RET]]
+;
+entry:
+  %rem = srem i32 %a, %b
+  %cmp = icmp eq i32 %rem, 42
+  br i1 %cmp, label %if, label %end
+
+if:
+  %div = udiv i32 %a, %b
+  br label %end
+
+end:
+  %ret = phi i32 [ %div, %if ], [ 3, %entry ]
+  ret i32 %ret
+}
+
+; If the ops don't match, don't do anything: operation.
+
+define i32 @dont_hoist_srem(i32 %a, i32 %b) {
+; CHECK-LABEL: @dont_hoist_srem(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[REM:%.*]] = urem i32 %a, %b
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[REM]], 42
+; CHECK-NEXT:    br i1 [[CMP]], label %if, label %end
+; CHECK:       if:
+; CHECK-NEXT:    [[REM2:%.*]] = srem i32 %a, %b
+; CHECK-NEXT:    br label %end
+; CHECK:       end:
+; CHECK-NEXT:    [[RET:%.*]] = phi i32 [ [[REM2]], %if ], [ 3, %entry ]
+; CHECK-NEXT:    ret i32 [[RET]]
+;
+entry:
+  %rem = urem i32 %a, %b
+  %cmp = icmp eq i32 %rem, 42
+  br i1 %cmp, label %if, label %end
+
+if:
+  %rem2 = srem i32 %a, %b
+  br label %end
+
+end:
+  %ret = phi i32 [ %rem2, %if ], [ 3, %entry ]
+  ret i32 %ret
+}
+
+; If the ops don't match, don't do anything: operands.
+
+define i32 @dont_hoist_sdiv(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @dont_hoist_sdiv(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[REM:%.*]] = srem i32 %a, %b
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[REM]], 42
+; CHECK-NEXT:    br i1 [[CMP]], label %if, label %end
+; CHECK:       if:
+; CHECK-NEXT:    [[DIV:%.*]] = sdiv i32 %a, %c
+; CHECK-NEXT:    br label %end
+; CHECK:       end:
+; CHECK-NEXT:    [[RET:%.*]] = phi i32 [ [[DIV]], %if ], [ 3, %entry ]
+; CHECK-NEXT:    ret i32 [[RET]]
+;
+entry:
+  %rem = srem i32 %a, %b
+  %cmp = icmp eq i32 %rem, 42
+  br i1 %cmp, label %if, label %end
+
+if:
+  %div = sdiv i32 %a, %c
+  br label %end
+
+end:
+  %ret = phi i32 [ %div, %if ], [ 3, %entry ]
+  ret i32 %ret
+}
+
+; If the rem is much more expensive than div, don't do anything.
+
+define i128 @dont_hoist_urem(i128 %a, i128 %b) {
+; CHECK-LABEL: @dont_hoist_urem(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[DIV:%.*]] = udiv i128 %a, %b
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i128 [[DIV]], 42
+; CHECK-NEXT:    br i1 [[CMP]], label %if, label %end
+; CHECK:       if:
+; CHECK-NEXT:    [[REM:%.*]] = urem i128 %a, %b
+; CHECK-NEXT:    br label %end
+; CHECK:       end:
+; CHECK-NEXT:    [[RET:%.*]] = phi i128 [ [[REM]], %if ], [ 3, %entry ]
+; CHECK-NEXT:    ret i128 [[RET]]
+;
+entry:
+  %div = udiv i128 %a, %b
+  %cmp = icmp eq i128 %div, 42
+  br i1 %cmp, label %if, label %end
+
+if:
+  %rem = urem i128 %a, %b
+  br label %end
+
+end:
+  %ret = phi i128 [ %rem, %if ], [ 3, %entry ]
+  ret i128 %ret
+}
+