[LLVM][PASSES][InstSimplify] Add (X << Y) % X -> 0

[AntonBikineev]

Summary

@spatel
I've added that missing fold you mentioned in D42032. I'll also quickly add new tests in a separated patch and rebase this patch as soon as those tests get committed.

[spatel]

LGTM.

[spatel]

Let me know if you'd like me to commit this for you.

[lebedev.ri]

Looking at https://reviews.llvm.org/people/revisions/1398/ i think you can ask for the commit rights now. Just a thought.

[AntonBikineev]

In D42341#983893, @lebedev.ri wrote:

Looking at https://reviews.llvm.org/people/revisions/1398/ i think you can ask for the commit rights now. Just a thought.

Thanks for noting that! I was just granted with commit access and checked it using this patch.

lib/Analysis/InstructionSimplify.cpp

static Value *simplifyRem(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1,
 
   // (X % Y) % Y -> X % Y
   if ((Opcode == Instruction::SRem &&
        match(Op0, m_SRem(m_Value(), m_Specific(Op1)))) ||
       (Opcode == Instruction::URem &&
        match(Op0, m_URem(m_Value(), m_Specific(Op1)))))
     return Op0;
 
+  // (X << Y) % X -> 0
+  if ((Opcode == Instruction::SRem &&
+       match(Op0, m_NSWShl(m_Specific(Op1), m_Value()))) ||
+      (Opcode == Instruction::URem &&
+       match(Op0, m_NUWShl(m_Specific(Op1), m_Value()))))
+    return Constant::getNullValue(Op0->getType());
+
   // If the operation is with the result of a select instruction, check whether
   // operating on either branch of the select always yields the same value.
   if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
     if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, Q, MaxRecurse))
       return V;
 
   // If the operation is with the result of a phi instruction, check whether
   // operating on all incoming values of the phi always yields the same value.

test/Transforms/InstSimplify/rem.ll

;
   %urem = urem i32 %call, 3
   ret i32 %urem
 }
 
 !0 = !{i32 0, i32 3}
 
 define i32 @rem5(i32 %x, i32 %y) {
 ; CHECK-LABEL: @rem5(
-; CHECK-NEXT:    [[SHL:%.*]] = shl nsw i32 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[MOD:%.*]] = srem i32 [[SHL]], [[X]]
-; CHECK-NEXT:    ret i32 [[MOD]]
+; CHECK-NEXT:    ret i32 0
 ;
   %shl = shl nsw i32 %x, %y
   %mod = srem i32 %shl, %x
   ret i32 %mod
 }
 
 define <2 x i32> @rem6(<2 x i32> %x, <2 x i32> %y) {
 ; CHECK-LABEL: @rem6(
-; CHECK-NEXT:    [[SHL:%.*]] = shl nsw <2 x i32> [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[MOD:%.*]] = srem <2 x i32> [[SHL]], [[X]]
-; CHECK-NEXT:    ret <2 x i32> [[MOD]]
+; CHECK-NEXT:    ret <2 x i32> zeroinitializer
 ;
   %shl = shl nsw <2 x i32> %x, %y
   %mod = srem <2 x i32> %shl, %x
   ret <2 x i32> %mod
 }
 
 ; make sure the previous fold doesn't take place for wrapped shifts
 
 define i32 @rem7(i32 %x, i32 %y) {
 ; CHECK-LABEL: @rem7(
 ; CHECK-NEXT:    [[SHL:%.*]] = shl i32 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[MOD:%.*]] = srem i32 [[SHL]], [[X]]
 ; CHECK-NEXT:    ret i32 [[MOD]]
 ;
   %shl = shl i32 %x, %y
   %mod = srem i32 %shl, %x
   ret i32 %mod
 }
 
 define i32 @rem8(i32 %x, i32 %y) {
 ; CHECK-LABEL: @rem8(
-; CHECK-NEXT:    [[SHL:%.*]] = shl nuw i32 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[MOD:%.*]] = urem i32 [[SHL]], [[X]]
-; CHECK-NEXT:    ret i32 [[MOD]]
+; CHECK-NEXT:    ret i32 0
 ;
   %shl = shl nuw i32 %x, %y
   %mod = urem i32 %shl, %x
   ret i32 %mod
 }
 
 define <2 x i32> @rem9(<2 x i32> %x, <2 x i32> %y) {
 ; CHECK-LABEL: @rem9(
-; CHECK-NEXT:    [[SHL:%.*]] = shl nuw <2 x i32> [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[MOD:%.*]] = urem <2 x i32> [[SHL]], [[X]]
-; CHECK-NEXT:    ret <2 x i32> [[MOD]]
+; CHECK-NEXT:    ret <2 x i32> zeroinitializer
 ;
   %shl = shl nuw <2 x i32> %x, %y
   %mod = urem <2 x i32> %shl, %x
   ret <2 x i32> %mod
 }
 
 ; make sure the previous fold doesn't take place for wrapped shifts