Index: lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
===================================================================
--- lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
+++ lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
@@ -923,31 +923,56 @@
 }
 
 namespace {
-const unsigned MaxDepth = 6;
-typedef Instruction *(*FoldUDivOperandCb)(Value *Op0, Value *Op1,
-                                          const BinaryOperator &I,
-                                          InstCombiner &IC);
-
-/// \brief Used to maintain state for visitUDivOperand().
-struct UDivFoldAction {
-  FoldUDivOperandCb FoldAction; ///< Informs visitUDiv() how to fold this
-                                ///< operand.  This can be zero if this action
-                                ///< joins two actions together.
-
-  Value *OperandToFold;         ///< Which operand to fold.
-  union {
-    Instruction *FoldResult;    ///< The instruction returned when FoldAction is
-                                ///< invoked.
-
-    size_t SelectLHSIdx;        ///< Stores the LHS action index if this action
-                                ///< joins two actions together.
+  const unsigned MaxDepth = 6;
+  typedef Instruction *(*FoldUDivOperandCb)(Value *Op0, Value *Op1,
+                                            const BinaryOperator &I,
+                                            InstCombiner &IC);
+  
+  /// \brief Used to maintain state for visitUDivOperand().
+  struct UDivFoldAction {
+    FoldUDivOperandCb FoldAction; ///< Informs visitUDiv() how to fold this
+    ///< operand.  This can be zero if this action
+    ///< joins two actions together.
+    
+    Value *OperandToFold;         ///< Which operand to fold.
+    union {
+      Instruction *FoldResult;    ///< The instruction returned when FoldAction is
+      ///< invoked.
+      
+      size_t SelectLHSIdx;        ///< Stores the LHS action index if this action
+      ///< joins two actions together.
+    };
+    
+    UDivFoldAction(FoldUDivOperandCb FA, Value *InputOperand)
+    : FoldAction(FA), OperandToFold(InputOperand), FoldResult(nullptr) {}
+    UDivFoldAction(FoldUDivOperandCb FA, Value *InputOperand, size_t SLHS)
+    : FoldAction(FA), OperandToFold(InputOperand), SelectLHSIdx(SLHS) {}
   };
-
-  UDivFoldAction(FoldUDivOperandCb FA, Value *InputOperand)
-      : FoldAction(FA), OperandToFold(InputOperand), FoldResult(nullptr) {}
-  UDivFoldAction(FoldUDivOperandCb FA, Value *InputOperand, size_t SLHS)
-      : FoldAction(FA), OperandToFold(InputOperand), SelectLHSIdx(SLHS) {}
-};
+  
+  typedef Instruction *(*FoldSDivOperandCb)(Value *Op0, Value *Op1,
+                                            const BinaryOperator &I,
+                                            InstCombiner &IC);
+  
+  struct SDivFoldAction {
+    FoldSDivOperandCb FoldAction; ///< Informs visitUDiv() how to fold this
+    ///< operand.  This can be zero if this action
+    ///< joins two actions together.
+    
+    Value *OperandToFold;         ///< Which operand to fold.
+    union {
+      Instruction *FoldResult;    ///< The instruction returned when FoldAction is
+      ///< invoked.
+      
+      size_t SelectLHSIdx;        ///< Stores the LHS action index if this action
+      ///< joins two actions together.
+    };
+    
+    SDivFoldAction(FoldSDivOperandCb FA, Value *InputOperand)
+    : FoldAction(FA), OperandToFold(InputOperand), FoldResult(nullptr) {}
+    SDivFoldAction(FoldSDivOperandCb FA, Value *InputOperand, size_t SLHS)
+    : FoldAction(FA), OperandToFold(InputOperand), SelectLHSIdx(SLHS) {}
+  };
+  
 }
 
 // X udiv 2^C -> X >> C
@@ -1106,6 +1131,40 @@
   return nullptr;
 }
 
+//X sdiv 2^C -> X >> C
+static Instruction *foldSDivPow2Cst(Value *Op0, Value *Op1,
+                                    const BinaryOperator &I, InstCombiner &IC) {
+  const APInt &C = cast<Constant>(Op1)->getUniqueInteger();
+  BinaryOperator *AShr = BinaryOperator::CreateExactAShr(
+                                                         Op0, ConstantInt::get(Op0->getType(), C.logBase2()));
+  return AShr;
+}
+
+static size_t visitSDivOperand(Value *Op0, Value *Op1, const BinaryOperator &I,
+                               SmallVectorImpl<SDivFoldAction> &Actions,
+                               unsigned Depth = 0) {
+  // Check to see if this is an signed division with an exact power of 2,
+  // if so, convert to a right shift.
+  if (match(Op1, m_Power2())) {
+    Actions.push_back(SDivFoldAction(foldSDivPow2Cst, Op1));
+    return Actions.size();
+  }
+  
+  // The remaining tests are all recursive, so bail out if we hit the limit.
+  if (Depth++ == MaxDepth)
+    return 0;
+  
+  if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
+    if (size_t LHSIdx =
+        visitSDivOperand(Op0, SI->getOperand(1), I, Actions, Depth))
+      if (visitSDivOperand(Op0, SI->getOperand(2), I, Actions, Depth)) {
+        Actions.push_back(SDivFoldAction(nullptr, Op1, LHSIdx - 1));
+        return Actions.size();
+      }
+  
+  return 0;
+}
+
 Instruction *InstCombiner::visitSDiv(BinaryOperator &I) {
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 
@@ -1170,7 +1229,37 @@
       }
     }
   }
-
+  
+  SmallVector<SDivFoldAction, 6> SDivActions;
+  if (visitSDivOperand(Op0, Op1, I, SDivActions))
+    for (unsigned i = 0, e = SDivActions.size(); i != e; ++i) {
+      FoldSDivOperandCb Action = SDivActions[i].FoldAction;
+      Value *ActionOp1 = SDivActions[i].OperandToFold;
+      Instruction *Inst;
+      if (Action)
+        Inst = Action(Op0, ActionOp1, I, *this);
+      else {
+        // This action joins two actions together.  The RHS of this action is
+        // simply the last action we processed, we saved the LHS action index in
+        // the joining action.
+        size_t SelectRHSIdx = i - 1;
+        Value *SelectRHS = SDivActions[SelectRHSIdx].FoldResult;
+        size_t SelectLHSIdx = SDivActions[i].SelectLHSIdx;
+        Value *SelectLHS = SDivActions[SelectLHSIdx].FoldResult;
+        Inst = SelectInst::Create(cast<SelectInst>(ActionOp1)->getCondition(),
+                                  SelectLHS, SelectRHS);
+      }
+      
+      // If this is the last action to process, return it to the InstCombiner.
+      // Otherwise, we insert it before the SDiv and record it so that we may
+      // use it as part of a joining action (i.e., a SelectInst).
+      if (e - i != 1) {
+        Inst->insertBefore(&I);
+        SDivActions[i].FoldResult = Inst;
+      } else
+        return Inst;
+    }
+  
   return nullptr;
 }