[InstCombine] fold mul with decremented "shl -1" factor (2nd try)
authorSanjay Patel <spatel@rotateright.com>
Wed, 2 Nov 2022 13:15:11 +0000 (09:15 -0400)
committerSanjay Patel <spatel@rotateright.com>
Wed, 2 Nov 2022 13:30:01 +0000 (09:30 -0400)
commitf03b069c5b70b59a9cb391a4c41250083aa6b2b4
tree6cf078a6a9510712d795bb5b2171ee84dab51f94
parent88d34d46260e62ee4640b4fa50d3f3e70c75f198
[InstCombine] fold mul with decremented "shl -1" factor (2nd try)

This is a corrected version of:
bc886e9b587b

I made a copy-paste error that created an "add" instead of the
intended "sub" on that attempt. The regression tests showed the
bug, but I overlooked that.

As I said in a comment on issue #58717, the bug reports resulting
from the botched patch confirm that the pattern does occur in
many real-world applications, so hopefully eliminating the multiply
results in better code.

I added one more regression test in this version of the patch,
and here's an Alive2 proof to show that exact example:
https://alive2.llvm.org/ce/z/dge7VC

Original commit message:

This is a sibling to:
6064e92b0a84
...but we canonicalize the shl+add to shl+xor,
so the pattern is different than I expected:
https://alive2.llvm.org/ce/z/8CX16e

I have not found any patterns that are safe
to propagate no-wrap, so that is not included
here.

Differential Revision: https://reviews.llvm.org/D137157
llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
llvm/test/Transforms/InstCombine/mul.ll