[X86] Do not lower scalar sdiv/udiv to a shifts + mul sequence when optimizing for minsize

[mkuper]

Summary

There are some cases where the mul sequence is smaller, but for the most part, using a div is preferable.

This does not apply to vectors, since x86 doesn't have vector idiv, and a vector mul/shifts sequence ought to be smaller than a scalarized division.
(Of course, this really depends on the type, since we may not have vector muls/shifts either, but I'd rather just keep the existing behavior for the vector case)

[spatel]

Since we're making these virtual functions, can we have them return 'false' by default and eliminate the member variables (IntDivIsCheap, Pow2SDivIsCheap) in TargetLowering? It doesn't look like anything in tree even overrides these, so changes would be minimal.

[mkuper]

Thanks, Sanjay.

I was thinking about preserving the API for out-of-tree targets, but, I agree, it does look somewhat redundant. You're probably right, the state variables can go away.

Also, it doesn't look like there are any in-tree targets that actually have different settings for isPow2SDivCheap() and isIntDivCheap().
Looking at the history, isPow2SDivCheap() was introduced in 2005 for the benefit of PPC (with the comment "This will probably go away in the future."), and PPC was the only in-tree user until 2014, at which point Hal removed that use.

I'll update the patch to remove the Pow2SDiv interface entirely, and remove the state variable for IntDiv.

[mkuper]

Updated to refactor the TLI interface as suggested.
I'll split this into two patches when I commit - one for the refactoring, and one for the x86 change.

[spatel]

A couple of nits in the comments. Otherwise, LGTM.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2188

Missing period.

lib/Target/X86/X86ISelLowering.cpp

26428–26431

Use "division" in these lines rather than "div"

include/llvm/Target/TargetLowering.h

public:
   virtual bool
   shouldExpandBuildVectorWithShuffles(EVT /* VT */,
                                       unsigned DefinedValues) const {
     return DefinedValues < 3;
   }
 
   /// Return true if integer divide is usually cheaper than a sequence of
   /// several shifts, adds, and multiplies for this target.
-  bool isIntDivCheap() const { return IntDivIsCheap; }
+  /// The definition of "cheaper" may depend on whether we're optimizing
+  /// for speed or for size.
+  virtual bool isIntDivCheap(EVT VT, bool OptSize) const { 
+    return false;
+  }
 
   /// Return true if sqrt(x) is as cheap or cheaper than 1 / rsqrt(x)
   bool isFsqrtCheap() const {
     return FsqrtIsCheap;
   }
 
   /// Returns true if target has indicated at least one type should be bypassed.
   bool isSlowDivBypassed() const { return !BypassSlowDivWidths.empty(); }
 
   /// Returns map of slow types for division or remainder with corresponding
   /// fast types
   const DenseMap<unsigned int, unsigned int> &getBypassSlowDivWidths() const {
     return BypassSlowDivWidths;
   }
 
-  /// Return true if pow2 sdiv is cheaper than a chain of sra/srl/add/sra.
-  bool isPow2SDivCheap() const { return Pow2SDivIsCheap; }
-
   /// Return true if Flow Control is an expensive operation that should be
   /// avoided.
   bool isJumpExpensive() const { return JumpIsExpensive; }
 
   /// Return true if selects are only cheaper than branches if the branch is
   /// unlikely to be predicted right.
   bool isPredictableSelectExpensive() const {
     return PredictableSelectIsExpensive;
void setHasExtractBitsInsn(bool hasExtractInsn = true) {
     HasExtractBitsInsn = hasExtractInsn;
   }
 
   /// Tells the code generator not to expand logic operations on comparison
   /// predicates into separate sequences that increase the amount of flow
   /// control.
   void setJumpIsExpensive(bool isExpensive = true);
 
-  /// Tells the code generator that integer divide is expensive, and if
-  /// possible, should be replaced by an alternate sequence of instructions not
-  /// containing an integer divide.
-  void setIntDivIsCheap(bool isCheap = true) { IntDivIsCheap = isCheap; }
-
   /// Tells the code generator that fsqrt is cheap, and should not be replaced
   /// with an alternative sequence of instructions.
   void setFsqrtIsCheap(bool isCheap = true) { FsqrtIsCheap = isCheap; }
 
   /// Tells the code generator that this target supports floating point
   /// exceptions and cares about preserving floating point exception behavior.
   void setHasFloatingPointExceptions(bool FPExceptions = true) {
     HasFloatingPointExceptions = FPExceptions;
   }
 
   /// Tells the code generator which bitwidths to bypass.
   void addBypassSlowDiv(unsigned int SlowBitWidth, unsigned int FastBitWidth) {
     BypassSlowDivWidths[SlowBitWidth] = FastBitWidth;
   }
 
-  /// Tells the code generator that it shouldn't generate sra/srl/add/sra for a
-  /// signed divide by power of two; let the target handle it.
-  void setPow2SDivIsCheap(bool isCheap = true) { Pow2SDivIsCheap = isCheap; }
-
   /// Add the specified register class as an available regclass for the
   /// specified value type. This indicates the selector can handle values of
   /// that class natively.
   void addRegisterClass(MVT VT, const TargetRegisterClass *RC) {
     assert((unsigned)VT.SimpleTy < array_lengthof(RegClassForVT));
     AvailableRegClasses.push_back(std::make_pair(VT, RC));
     RegClassForVT[VT.SimpleTy] = RC;
   }
private:
   bool HasMultipleConditionRegisters;
 
   /// Tells the code generator that the target has BitExtract instructions.
   /// The code generator will aggressively sink "shift"s into the blocks of
   /// their users if the users will generate "and" instructions which can be
   /// combined with "shift" to BitExtract instructions.
   bool HasExtractBitsInsn;
 
-  /// Tells the code generator not to expand integer divides by constants into a
-  /// sequence of muls, adds, and shifts.  This is a hack until a real cost
-  /// model is in place.  If we ever optimize for size, this will be set to true
-  /// unconditionally.
-  bool IntDivIsCheap;
-
   // Don't expand fsqrt with an approximation based on the inverse sqrt.
   bool FsqrtIsCheap;
 
   /// Tells the code generator to bypass slow divide or remainder
   /// instructions. For example, BypassSlowDivWidths[32,8] tells the code
   /// generator to bypass 32-bit integer div/rem with an 8-bit unsigned integer
   /// div/rem when the operands are positive and less than 256.
   DenseMap <unsigned int, unsigned int> BypassSlowDivWidths;
 
-  /// Tells the code generator that it shouldn't generate sra/srl/add/sra for a
-  /// signed divide by power of two; let the target handle it.
-  bool Pow2SDivIsCheap;
-
   /// Tells the code generator that it shouldn't generate extra flow control
   /// instructions and should attempt to combine flow control instructions via
   /// predication.
   bool JumpIsExpensive;
 
   /// Whether the target supports or cares about preserving floating point
   /// exception behavior.
   bool HasFloatingPointExceptions;

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

SDValue DAGCombiner::visitSDIV(SDNode *N) {
   // If we know the sign bits of both operands are zero, strength reduce to a
   // udiv instead.  Handles (X&15) /s 4 -> X&15 >> 2
   if (!VT.isVector()) {
     if (DAG.SignBitIsZero(N1) && DAG.SignBitIsZero(N0))
       return DAG.getNode(ISD::UDIV, SDLoc(N), N1.getValueType(),
                          N0, N1);
   }
 
+  bool MinSize = DAG.getMachineFunction().getFunction()->optForMinSize();
   // fold (sdiv X, pow2) -> simple ops after legalize
   // FIXME: We check for the exact bit here because the generic lowering gives
   // better results in that case. The target-specific lowering should learn how
   // to handle exact sdivs efficiently.
   if (N1C && !N1C->isNullValue() && !N1C->isOpaque() &&
       !cast<BinaryWithFlagsSDNode>(N)->Flags.hasExact() &&
       (N1C->getAPIntValue().isPowerOf2() ||
        (-N1C->getAPIntValue()).isPowerOf2())) {
-    // If dividing by powers of two is cheap, then don't perform the following
-    // fold.
-    if (TLI.isPow2SDivCheap())
+    // If integer division is cheap, then don't perform the following fold
+    if (TLI.isIntDivCheap(N->getValueType(0), MinSize))
       return SDValue();
 
     // Target-specific implementation of sdiv x, pow2.
     if (SDValue Res = BuildSDIVPow2(N))
       return Res;
 
     unsigned lg2 = N1C->getAPIntValue().countTrailingZeros();
     SDLoc DL(N);
if (N1C->getAPIntValue().isNonNegative())
       return SRA;
 
     AddToWorklist(SRA.getNode());
     return DAG.getNode(ISD::SUB, DL, VT, DAG.getConstant(0, DL, VT), SRA);
   }
 
   // If integer divide is expensive and we satisfy the requirements, emit an
   // alternate sequence.
-  if (N1C && !TLI.isIntDivCheap())
+  if (N1C && !TLI.isIntDivCheap(N->getValueType(0), MinSize))
     if (SDValue Op = BuildSDIV(N))
       return Op;
 
   // undef / X -> 0
   if (N0.getOpcode() == ISD::UNDEF)
     return DAG.getConstant(0, SDLoc(N), VT);
   // X / undef -> undef
   if (N1.getOpcode() == ISD::UNDEF)
if (ConstantSDNode *SHC = getAsNonOpaqueConstant(N1.getOperand(0))) {
                                   DAG.getConstant(SHC->getAPIntValue()
                                                                   .logBase2(),
                                                   DL, ADDVT));
         AddToWorklist(Add.getNode());
         return DAG.getNode(ISD::SRL, DL, VT, N0, Add);
       }
     }
   }
+  
   // fold (udiv x, c) -> alternate
-  if (N1C && !TLI.isIntDivCheap())
+  bool MinSize = DAG.getMachineFunction().getFunction()->optForMinSize();
+  if (N1C && !TLI.isIntDivCheap(N->getValueType(0), MinSize))
     if (SDValue Op = BuildUDIV(N))
       return Op;
 
   // undef / X -> 0
   if (N0.getOpcode() == ISD::UNDEF)
     return DAG.getConstant(0, SDLoc(N), VT);
   // X / undef -> undef
   if (N1.getOpcode() == ISD::UNDEF)

lib/CodeGen/TargetLoweringBase.cpp

TargetLoweringBase::TargetLoweringBase(const TargetMachine &tm) : TM(tm) {
   MaxStoresPerMemset = MaxStoresPerMemcpy = MaxStoresPerMemmove = 8;
   MaxStoresPerMemsetOptSize = MaxStoresPerMemcpyOptSize
     = MaxStoresPerMemmoveOptSize = 4;
   UseUnderscoreSetJmp = false;
   UseUnderscoreLongJmp = false;
   SelectIsExpensive = false;
   HasMultipleConditionRegisters = false;
   HasExtractBitsInsn = false;
-  IntDivIsCheap = false;
   FsqrtIsCheap = false;
-  Pow2SDivIsCheap = false;
   JumpIsExpensive = JumpIsExpensiveOverride;
   PredictableSelectIsExpensive = false;
   MaskAndBranchFoldingIsLegal = false;
   EnableExtLdPromotion = false;
   HasFloatingPointExceptions = true;
   StackPointerRegisterToSaveRestore = 0;
   ExceptionPointerRegister = 0;
   ExceptionSelectorRegister = 0;

lib/Target/AMDGPU/AMDGPUISelLowering.cpp

AMDGPUTargetLowering::AMDGPUTargetLowering(TargetMachine &TM,
   // SI at least has hardware support for floating point exceptions, but no way
   // of using or handling them is implemented. They are also optional in OpenCL
   // (Section 7.3)
   setHasFloatingPointExceptions(false);
 
   setSelectIsExpensive(false);
   PredictableSelectIsExpensive = false;
 
-  // There are no integer divide instructions, and these expand to a pretty
-  // large sequence of instructions.
-  setIntDivIsCheap(false);
-  setPow2SDivIsCheap(false);
   setFsqrtIsCheap(true);
 
   // FIXME: Need to really handle these.
   MaxStoresPerMemcpy  = 4096;
   MaxStoresPerMemmove = 4096;
   MaxStoresPerMemset  = 4096;
 }
 

lib/Target/MSP430/MSP430ISelLowering.cpp

MSP430TargetLowering::MSP430TargetLowering(const TargetMachine &TM,
   // Set up the register classes.
   addRegisterClass(MVT::i8,  &MSP430::GR8RegClass);
   addRegisterClass(MVT::i16, &MSP430::GR16RegClass);
 
   // Compute derived properties from the register classes
   computeRegisterProperties(STI.getRegisterInfo());
 
   // Provide all sorts of operation actions
-
-  // Division is expensive
-  setIntDivIsCheap(false);
-
   setStackPointerRegisterToSaveRestore(MSP430::SP);
   setBooleanContents(ZeroOrOneBooleanContent);
   setBooleanVectorContents(ZeroOrOneBooleanContent); // FIXME: Is this correct?
 
   // We have post-incremented loads / stores.
   setIndexedLoadAction(ISD::POST_INC, MVT::i8, Legal);
   setIndexedLoadAction(ISD::POST_INC, MVT::i16, Legal);
 

lib/Target/X86/X86ISelLowering.h

SDValue BuildFILD(SDValue Op, EVT SrcVT, SDValue Chain, SDValue StackSlot,
                       SelectionDAG &DAG) const;
 
     bool isNoopAddrSpaceCast(unsigned SrcAS, unsigned DestAS) const override;
 
     bool useLoadStackGuardNode() const override;
     /// \brief Customize the preferred legalization strategy for certain types.
     LegalizeTypeAction getPreferredVectorAction(EVT VT) const override;
 
+    bool isIntDivCheap(EVT VT, bool OptSize) const override;
+
   protected:
     std::pair<const TargetRegisterClass *, uint8_t>
     findRepresentativeClass(const TargetRegisterInfo *TRI,
                             MVT VT) const override;
 
   private:
     /// Keep a pointer to the X86Subtarget around so that we can
     /// make the right decision when generating code for different targets.

lib/Target/X86/X86ISelLowering.cpp

if (isLegalAddressingMode(DL, AM, Ty, AS))
     // as soon as we use a second register.
     return AM.Scale != 0;
   return -1;
 }
 
 bool X86TargetLowering::isTargetFTOL() const {
   return Subtarget->isTargetKnownWindowsMSVC() && !Subtarget->is64Bit();
 }
+
+bool X86TargetLowering::isIntDivCheap(EVT VT, bool OptSize) const {
+  // Integer division on x86 is expensive. However, when aggressively optimizing
+  // for code size, we prefer to leave the div as is, as it is usually smaller
+  // than the alternative sequence.
+  // The exception to this is vector divs. Since we don't have vector integer
+  // division, leaving the div as-is is a loss even in terms of size, because it
+  // will have to be scalarized, while the alternative code sequence can be
+  // performed in vector form.
+  return OptSize && !VT.isVector();
+}

lib/Target/XCore/XCoreISelLowering.cpp

XCoreTargetLowering::XCoreTargetLowering(const TargetMachine &TM,
     : TargetLowering(TM), TM(TM), Subtarget(Subtarget) {
 
   // Set up the register classes.
   addRegisterClass(MVT::i32, &XCore::GRRegsRegClass);
 
   // Compute derived properties from the register classes
   computeRegisterProperties(Subtarget.getRegisterInfo());
 
-  // Division is expensive
-  setIntDivIsCheap(false);
-
   setStackPointerRegisterToSaveRestore(XCore::SP);
 
   setSchedulingPreference(Sched::Source);
 
   // Use i32 for setcc operations results (slt, sgt, ...).
   setBooleanContents(ZeroOrOneBooleanContent);
   setBooleanVectorContents(ZeroOrOneBooleanContent); // FIXME: Is this correct?
 

test/CodeGen/X86/divide-by-constant.ll

define i8 @test9(i8 %x) nounwind {
   %div = udiv i8 %x, 116
   ret i8 %div
 ; CHECK-LABEL: test9:
 ; CHECK: shrb $2
 ; CHECK: imull $71
 ; CHECK: shrl $11
 ; CHECK: ret
 }
+
+define i32 @testsize1(i32 %x) minsize nounwind {
+entry:
+  %div = sdiv i32 %x, 32
+  ret i32 %div
+; CHECK-LABEL: testsize1:
+; CHECK: divl
+}
+
+define i32 @testsize2(i32 %x) minsize nounwind {
+entry:
+  %div = sdiv i32 %x, 33
+  ret i32 %div
+; CHECK-LABEL: testsize2:
+; CHECK: divl
+}
+
+define i32 @testsize3(i32 %x) minsize nounwind {
+entry:
+  %div = udiv i32 %x, 32
+  ret i32 %div
+; CHECK-LABEL: testsize3:
+; CHECK: shrl
+}
+
+define i32 @testsize4(i32 %x) minsize nounwind {
+entry:
+  %div = udiv i32 %x, 33
+  ret i32 %div
+; CHECK-LABEL: testsize4:
+; CHECK: divl
+}

test/CodeGen/X86/vec_sdiv_to_shift.ll

 ; RUN: llc < %s -march=x86-64 -mcpu=penryn -mattr=+avx2 | FileCheck %s
 
 
 define <8 x i16> @sdiv_vec8x16(<8 x i16> %var) {
 entry:
 ; CHECK: sdiv_vec8x16
 ; CHECK: psraw  $15
 ; CHECK: vpsrlw  $11
 ; CHECK: vpaddw
 ; CHECK: vpsraw  $5
 ; CHECK: ret
   %0 = sdiv <8 x i16> %var, <i16 32, i16 32, i16 32, i16 32, i16 32, i16 32, i16 32, i16 32>
   ret <8 x i16> %0
 }
 
+define <8 x i16> @sdiv_vec8x16_minsize(<8 x i16> %var) minsize {
+entry:
+; CHECK: sdiv_vec8x16_minsize
+; CHECK: psraw  $15
+; CHECK: vpsrlw  $11
+; CHECK: vpaddw
+; CHECK: vpsraw  $5
+; CHECK: ret
+  %0 = sdiv <8 x i16> %var, <i16 32, i16 32, i16 32, i16 32, i16 32, i16 32, i16 32, i16 32>
+  ret <8 x i16> %0
+}
+
+
 define <4 x i32> @sdiv_zero(<4 x i32> %var) {
 entry:
 ; CHECK: sdiv_zero
 ; CHECK-NOT: sra
 ; CHECK: ret
   %0 = sdiv <4 x i32> %var, <i32 0, i32 0, i32 0, i32 0>
   ret <4 x i32> %0
 }