[InstCombine] Added transformation from sdiv to ashr

[IlyaKrotov]

Summary

Replace division of positive signed integer by power of 2 with a simple shift.

[majnemer]

You don't have any testcases.

What stops you from transforming sdiv i32 %x, 2 into ashr i32 %x, 1 ? Such a transform wouldn't be correct because the two are not equivalent when %x is -1.

The transform on line 1215 already tries to turn signed division into unsigned division when it is safe to do so. From there, unsigned division will be canonicalized into a shift when we can.

lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

1138–1139

This doesn't look correctly formatted, please use clang-format.

lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

static Value *dyn_castZExtVal(Value *V, Type *Ty) {
   } else if (ConstantInt *C = dyn_cast<ConstantInt>(V)) {
     if (C->getValue().getActiveBits() <= cast<IntegerType>(Ty)->getBitWidth())
       return ConstantExpr::getTrunc(C, Ty);
   }
   return nullptr;
 }
 
 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.
     };
     
     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
 static Instruction *foldUDivPow2Cst(Value *Op0, Value *Op1,
                                     const BinaryOperator &I, InstCombiner &IC) {
   const APInt &C = cast<Constant>(Op1)->getUniqueInteger();
   BinaryOperator *LShr = BinaryOperator::CreateLShr(
       Op0, ConstantInt::get(Op0->getType(), C.logBase2()));
for (unsigned i = 0, e = UDivActions.size(); i != e; ++i) {
         UDivActions[i].FoldResult = Inst;
       } else
         return Inst;
     }
 
   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);
 
   if (Value *V = SimplifyVectorOp(I))
     return ReplaceInstUsesWith(I, V);
 
   if (Value *V = SimplifySDivInst(Op0, Op1, DL, TLI, DT, AC))
     return ReplaceInstUsesWith(I, V);
if (MaskedValueIsZero(Op0, Mask, 0, &I)) {
         // INT_MIN, and X sdiv INT_MIN == X udiv INT_MIN == 0 if X doesn't have
         // the sign bit set.
         auto *BO = BinaryOperator::CreateUDiv(Op0, Op1, I.getName());
         BO->setIsExact(I.isExact());
         return BO;
       }
     }
   }
   
+  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;
 }
 
 /// CvtFDivConstToReciprocal tries to convert X/C into X*1/C if C not a special
 /// FP value and:
 ///    1) 1/C is exact, or
 ///    2) reciprocal is allowed.
 /// If the conversion was successful, the simplified expression "X * 1/C" is