InstCombine: Turn (zext A) udiv (zext B) into (zext (A udiv B)). Same for urem or...

This obviously helps a lot if the division would be turned into a libcall
(think i64 udiv on i386), but div is also one of the few remaining instructions
on modern CPUs that become more expensive when the bitwidth gets bigger.

This also helps register pressure on i386 when dividing chars, divb needs
two 8-bit parts of a 16 bit register as input where divl uses two registers.

int foo(unsigned char a) { return a/10; }
int bar(unsigned char a, unsigned char b) { return a/b; }

compiles into (x86_64)
_foo:
  imull $205, %edi, %eax
  shrl  $11, %eax
  ret
_bar:
  movzbl        %dil, %eax
  divb  %sil, %al
  movzbl        %al, %eax
  ret

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@130615 91177308-0d34-0410-b5e6-96231b3b80d8

diff --git a/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp b/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
index b4f4da6fb0e74cfd0c6c098c25517b1a6443a57c..230b80e27241bf7d4ce804b3bf52f75af056906b 100644 (file)
--- a/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
+++ b/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
@@ -336,6 +336,19 @@ Instruction *InstCombiner::commonIDivTransforms(BinaryOperator &I) {
   return 0;
 }
 
+/// dyn_castZExtVal - Checks if V is a zext or constant that can
+/// be truncated to Ty without losing bits.
+static Value *dyn_castZExtVal(Value *V, const Type *Ty) {
+  if (ZExtInst *Z = dyn_cast<ZExtInst>(V)) {
+    if (Z->getSrcTy() == Ty)
+      return Z->getOperand(0);
+  } else if (ConstantInt *C = dyn_cast<ConstantInt>(V)) {
+    if (C->getValue().getActiveBits() <= cast<IntegerType>(Ty)->getBitWidth())
+      return ConstantExpr::getTrunc(C, Ty);
+  }
+  return 0;
+}
+
 Instruction *InstCombiner::visitUDiv(BinaryOperator &I) {
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 
@@ -394,6 +407,14 @@ Instruction *InstCombiner::visitUDiv(BinaryOperator &I) {
       return SelectInst::Create(Cond, TSI, FSI);
     }
   }
+
+  // (zext A) udiv (zext B) --> zext (A udiv B)
+  if (ZExtInst *ZOp0 = dyn_cast<ZExtInst>(Op0))
+    if (Value *ZOp1 = dyn_castZExtVal(Op1, ZOp0->getSrcTy()))
+      return new ZExtInst(Builder->CreateUDiv(ZOp0->getOperand(0), ZOp1, "div",
+                                              I.isExact()),
+                          I.getType());
+
   return 0;
 }
 
@@ -568,7 +589,13 @@ Instruction *InstCombiner::visitURem(BinaryOperator &I) {
       return SelectInst::Create(Cond, TrueAnd, FalseAnd);
     }
   }
-  
+
+  // (zext A) urem (zext B) --> zext (A urem B)
+  if (ZExtInst *ZOp0 = dyn_cast<ZExtInst>(Op0))
+    if (Value *ZOp1 = dyn_castZExtVal(Op1, ZOp0->getSrcTy()))
+      return new ZExtInst(Builder->CreateURem(ZOp0->getOperand(0), ZOp1),
+                          I.getType());
+
   return 0;
 }
 

diff --git a/test/Transforms/InstCombine/udivrem-change-width.ll b/test/Transforms/InstCombine/udivrem-change-width.ll
index 9983944df8d722b8ddf04f988ce5ac99f544bb6d..b388a3b0634ec52932f7f874d2286c129215a4e6 100644 (file)
--- a/test/Transforms/InstCombine/udivrem-change-width.ll
+++ b/test/Transforms/InstCombine/udivrem-change-width.ll
@@ -1,14 +1,16 @@
-; RUN: opt < %s -instcombine -S | not grep zext
-; PR4548
+; RUN: opt < %s -instcombine -S | FileCheck %s
 
 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"
 
+; PR4548
 define i8 @udiv_i8(i8 %a, i8 %b) nounwind {
   %conv = zext i8 %a to i32       
   %conv2 = zext i8 %b to i32      
   %div = udiv i32 %conv, %conv2   
   %conv3 = trunc i32 %div to i8   
   ret i8 %conv3
+; CHECK: @udiv_i8
+; CHECK: udiv i8 %a, %b
 }
 
 define i8 @urem_i8(i8 %a, i8 %b) nounwind {
@@ -17,5 +19,44 @@ define i8 @urem_i8(i8 %a, i8 %b) nounwind {
   %div = urem i32 %conv, %conv2   
   %conv3 = trunc i32 %div to i8   
   ret i8 %conv3
+; CHECK: @urem_i8
+; CHECK: urem i8 %a, %b
 }
 
+define i32 @udiv_i32(i8 %a, i8 %b) nounwind {
+  %conv = zext i8 %a to i32
+  %conv2 = zext i8 %b to i32
+  %div = udiv i32 %conv, %conv2
+  ret i32 %div
+; CHECK: @udiv_i32
+; CHECK: udiv i8 %a, %b
+; CHECK: zext
+}
+
+define i32 @urem_i32(i8 %a, i8 %b) nounwind {
+  %conv = zext i8 %a to i32
+  %conv2 = zext i8 %b to i32
+  %div = urem i32 %conv, %conv2
+  ret i32 %div
+; CHECK: @urem_i32
+; CHECK: urem i8 %a, %b
+; CHECK: zext
+}
+
+define i32 @udiv_i32_c(i8 %a) nounwind {
+  %conv = zext i8 %a to i32
+  %div = udiv i32 %conv, 10
+  ret i32 %div
+; CHECK: @udiv_i32_c
+; CHECK: udiv i8 %a, 10
+; CHECK: zext
+}
+
+define i32 @urem_i32_c(i8 %a) nounwind {
+  %conv = zext i8 %a to i32
+  %div = urem i32 %conv, 10
+  ret i32 %div
+; CHECK: @urem_i32_c
+; CHECK: urem i8 %a, 10
+; CHECK: zext
+}