[InstSimplify] sdiv a (1 srem b) --> a

[floatshadow]

Summary

Try to fix issue https://github.com/llvm/llvm-project/issues/62163

as (1 srem X) is not equivalent with zext (X != 1), pattern sdiv a (1 srem b) miss the optimization.

[nikic]

This is missing a lot of conjugate patterns. You can do the same for udiv and there are related patterns for urem and srem as well. You want to extend this code: https://github.com/llvm/llvm-project/blob/1eb74f7e83ffb3f9d00e5987cead3b12e00bbe82/llvm/lib/Analysis/InstructionSimplify.cpp#L1053-L1061

[floatshadow]

now this patch will figure out other conjugate patterns like [u]sdiv X (1 [u]srem Y) --> X and [u]srem X (1 [u]srem Y) --> 0

[junaire]

llvm/test/Transforms/InstSimplify/div.ll

437 ↗

(On Diff #516108)

split the tests into a separate revision so we can see the diff more clearly. (You can add a parent revision

[floatshadow]

clean diff following what junaire proposes

Depends on D149012

[nikic]

Thanks! This will still a miss other patterns that can only be zero or one. For example a mask with 1: https://alive2.llvm.org/ce/z/A_ffYe

You can handle these by calling computeKnownBits() and checking the number of leading zeros.

[floatshadow]

use computeKnownBits() to check if the divisor can only be zero or one.

another question is can this method replace the original pattern match like match(Op1, m_One())? I worry about the performance of computeKnownBits().

[floatshadow]

@nikic I checked PR51762 test in Transforms/InstCombine/zext-or-icmp.ll

%lor.ext = zext i1 %spec.select57 to i32
%t2 = load i32, ptr %d, align 4
%conv15 = sext i16 %t1 to i32
%cmp16 = icmp sge i32 %t2, %conv15
%conv17 = zext i1 %cmp16 to i32
%t3 = load i32, ptr %f, align 4
%add = add nsw i32 %t3, %conv17
store i32 %add, ptr %f, align 4
%rem18 = srem i32 %lor.ext, %add
%conv19 = zext i32 %rem18 to i64

%div = udiv i64 %insert.insert41, %conv19
%trunc33 = trunc i64 %div to i32
store i32 %trunc33, ptr %d, align 8
%r = icmp ult i64 %insert.insert41, %conv19
call void @llvm.assume(i1 %r)

as %cond19 = zext (srem (zext i1) %add), %cond can only be zero or one
the main branch looks at llvm.assume, and deduce %insert.insert41 = 0, thus store i32 %trunc33, ptr %d, align 8 becomes store i32 0, ptr %d, align 8
I do some trace which shows the call stack: simplifyUdiv --> isDivZero -> simplifyICmpWithDominatingAssume

as for current patch, it seems udiv will first enter simplifyDivRem which do the fold, replace %udiv with %insert.insert41 (done by computeKnownBits).
later trunc replace %insert.insert41 with %insert.insert39: opt debug logs

ADD DEFERRED:   %insert.insert41 = or i64 %insert.shift52, %insert.ext39
IC: Mod =   %trunc33 = trunc i64 %insert.insert41 to i32
    New =   %trunc33 = trunc i64 %insert.ext39 to i32

thus store i32 %trunc33, ptr %d, align 8 becomes store i32 %sroa38, ptr %d, align 8

I am not sure what I should do now, alive2 tells me that the transforms seems correct https://alive2.llvm.org/ce/z/NfVsmT

[nikic]

In D149001#4290441, @floatshadow wrote:

another question is can this method replace the original pattern match like match(Op1, m_One())? I worry about the performance of computeKnownBits().

It's okay to replace in this case. Division instructions are very rare, so this is not particularly performance sensitive.

I am not sure what I should do now, alive2 tells me that the transforms seems correct https://alive2.llvm.org/ce/z/NfVsmT

You can just regenerate the test. It's a fuzzer generated test case, so we don't really care as long as it doesn't infinite loop / miscompile.

[floatshadow]

address comments

1. remove old pattern matching m_One() and m_ZExt()
2. regenerate test PR51762 test in Transforms/InstCombine/zext-or-icmp.ll

[nikic]

This looks good to me, but it looks like you need to regenerate some clang OpenMP tests as well. Not sure why/where those run InstSimplify, but the failures look legitimate.

llvm/lib/Analysis/InstructionSimplify.cpp

1059

I'd feel better about a == here.

[floatshadow]

regenerate failed clang OpenMP tests.

[nikic]

LGTM. If you don't have commit access, can you please share the Name <email> to use for attribution?

[floatshadow]

llvm/lib/Analysis/InstructionSimplify.cpp

1059

== is better. Thanks for the suggestion.

[floatshadow]

In D149001#4292100, @nikic wrote:

LGTM. If you don't have commit access, can you please share the Name <email> to use for attribution?

This my first revision LOL.
Siyuan Zhu, [e-mail]

llvm/lib/Analysis/InstructionSimplify.cpp

 //===- InstructionSimplify.cpp - Fold instruction operands ----------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
static Value *simplifyDivRem(Instruction::BinaryOps Opcode, Value *Op0,
   if (Op0 == Op1)
     return IsDiv ? ConstantInt::get(Ty, 1) : Constant::getNullValue(Ty);
 
   // X / 1 -> X
   // X % 1 -> 0
   // If this is a boolean op (single-bit element type), we can't have
   // division-by-zero or remainder-by-zero, so assume the divisor is 1.
   // Similarly, if we're zero-extending a boolean divisor, then assume it's a 1.
+  // If this is an integer remainder (1 % Y), assume similarly the divisor is 1.
   Value *X;
   if (match(Op1, m_One()) || Ty->isIntOrIntVectorTy(1) ||
-      (match(Op1, m_ZExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)))
+      (match(Op1, m_ZExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)) ||
+      match(Op1, m_IRem(m_One(), m_Value())))
     return IsDiv ? Op0 : Constant::getNullValue(Ty);
 
   // If X * Y does not overflow, then:
   //   X * Y / Y -> X
   //   X * Y % Y -> 0
   if (match(Op0, m_c_Mul(m_Value(X), m_Specific(Op1)))) {
     auto *Mul = cast<OverflowingBinaryOperator>(Op0);
     // The multiplication can't overflow if it is defined not to, or if