This is an archive of the discontinued LLVM Phabricator instance.

[LoopIdiom] 'left-shift until bittest' idiom: support canonical sign bit mask
ClosedPublic

Authored by lebedev.ri on Nov 18 2020, 10:28 AM.

Details

Summary

If the bitmask is for sign bit, instcombine would have canonicalized
the pattern into a proper sign bit check. Supporting that is still
simple, but requires a bit of a roundtrip - we first have to use
decomposeBitTestICmp(), and the rest again just works.

Diff Detail

Event Timeline

lebedev.ri created this revision.Nov 18 2020, 10:28 AM
craig.topper added inline comments.Nov 18 2020, 10:51 AM
llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
2018

At least for MatchVariableBitMask and MatchConstantBitMask isn't this doing duplicate work finding the ICmp and looking through the phi? And only then checking the differing part of the pattern?

lebedev.ri marked an inline comment as done.

Do recurrence analysis afterwards, not when matching backedge condition.

lebedev.ri updated this revision to Diff 309876.Dec 7 2020, 4:40 AM

Rebased, NFC.

Rebased, NFC.

Rebased, NFC.

This revision is now accepted and ready to land.Dec 23 2020, 9:54 AM

LGTM

Thank you for the review!

Rebased, NFC.

This revision was landed with ongoing or failed builds.Dec 23 2020, 11:29 AM
This revision was automatically updated to reflect the committed changes.
pcc added a subscriber: pcc.Dec 29 2020, 2:23 PM

It looks like this patch caused an assertion failure:

$ cat test.ii
# 1 "" 3
typedef int a;
typedef unsigned b;
struct c {
  template <typename d> c(d e) : f(e) {}
  int f;
};
struct g {
  template <typename h, typename ad> g(h e, ad) : ae(e), af(0) {}
  c ae;
  c af;
};
template <typename ag, typename i> auto ah(ag e, i) { return g(e, 0); }
class j {
public:
  void k();
};
class l;
class m {
public:
  m(int, l, int);
};
class l {
public:
  l(int, int);
};
class n {
  bool o();
  int ax;
};
template <typename> using ay = m;
template <typename, typename> using bc = l;
class p {
public:
  int *m_fn3();
  a q();
};
class r {
public:
  r(int)
      : bh(0, bc<int, int>(int(), bi), bi), bj(int(), bi), bk(int(), bi),
        bl(int(), bi) {
    p bn;
    int *base = bn.m_fn3();
    a bo = base == nullptr ?: bn.q();
    if (bo)
      for (auto bp = ah(bo, 0); __builtin_expect(bp.ae.f >= bp.af.f, false);)
        j().k();
  }
  int bi;
  ay<bc<int, int>> bh;
  bc<int, int> bj;
  bc<b, bool> bk;
  bc<b, int> bl;
};
bool n::o() { r bq(ax); }
$ ~/l2/ra/bin/clang -O2 test.ii
clang: ../llvm/include/llvm/IR/Instructions.h:2767: llvm::Value *llvm::PHINode::getIncomingValueForBlock(const llvm::BasicBlock *) const: Assertion `Idx >= 0 && "Invalid basic block argument!"' failed.
In D91726#2474387, @pcc wrote:

It looks like this patch caused an assertion failure:

$ cat test.ii
# 1 "" 3
typedef int a;
typedef unsigned b;
struct c {
  template <typename d> c(d e) : f(e) {}
  int f;
};
struct g {
  template <typename h, typename ad> g(h e, ad) : ae(e), af(0) {}
  c ae;
  c af;
};
template <typename ag, typename i> auto ah(ag e, i) { return g(e, 0); }
class j {
public:
  void k();
};
class l;
class m {
public:
  m(int, l, int);
};
class l {
public:
  l(int, int);
};
class n {
  bool o();
  int ax;
};
template <typename> using ay = m;
template <typename, typename> using bc = l;
class p {
public:
  int *m_fn3();
  a q();
};
class r {
public:
  r(int)
      : bh(0, bc<int, int>(int(), bi), bi), bj(int(), bi), bk(int(), bi),
        bl(int(), bi) {
    p bn;
    int *base = bn.m_fn3();
    a bo = base == nullptr ?: bn.q();
    if (bo)
      for (auto bp = ah(bo, 0); __builtin_expect(bp.ae.f >= bp.af.f, false);)
        j().k();
  }
  int bi;
  ay<bc<int, int>> bh;
  bc<int, int> bj;
  bc<b, bool> bk;
  bc<b, int> bl;
};
bool n::o() { r bq(ax); }
$ ~/l2/ra/bin/clang -O2 test.ii
clang: ../llvm/include/llvm/IR/Instructions.h:2767: llvm::Value *llvm::PHINode::getIncomingValueForBlock(const llvm::BasicBlock *) const: Assertion `Idx >= 0 && "Invalid basic block argument!"' failed.

Thank you for the reproducer, i'll take a look.

In D91726#2474387, @pcc wrote:

It looks like this patch caused an assertion failure:

$ cat test.ii
# 1 "" 3
typedef int a;
typedef unsigned b;
struct c {
  template <typename d> c(d e) : f(e) {}
  int f;
};
struct g {
  template <typename h, typename ad> g(h e, ad) : ae(e), af(0) {}
  c ae;
  c af;
};
template <typename ag, typename i> auto ah(ag e, i) { return g(e, 0); }
class j {
public:
  void k();
};
class l;
class m {
public:
  m(int, l, int);
};
class l {
public:
  l(int, int);
};
class n {
  bool o();
  int ax;
};
template <typename> using ay = m;
template <typename, typename> using bc = l;
class p {
public:
  int *m_fn3();
  a q();
};
class r {
public:
  r(int)
      : bh(0, bc<int, int>(int(), bi), bi), bj(int(), bi), bk(int(), bi),
        bl(int(), bi) {
    p bn;
    int *base = bn.m_fn3();
    a bo = base == nullptr ?: bn.q();
    if (bo)
      for (auto bp = ah(bo, 0); __builtin_expect(bp.ae.f >= bp.af.f, false);)
        j().k();
  }
  int bi;
  ay<bc<int, int>> bh;
  bc<int, int> bj;
  bc<b, bool> bk;
  bc<b, int> bl;
};
bool n::o() { r bq(ax); }
$ ~/l2/ra/bin/clang -O2 test.ii
clang: ../llvm/include/llvm/IR/Instructions.h:2767: llvm::Value *llvm::PHINode::getIncomingValueForBlock(const llvm::BasicBlock *) const: Assertion `Idx >= 0 && "Invalid basic block argument!"' failed.

Thank you for the reproducer, i'll take a look.

And, that is not a sufficient information for me to reproduce :/
Can you please just give me the IR produced by clang (i.e. -O2 -S -emit-llvm -Xclang -disable-llvm-optzns)?

pcc added a comment.Dec 30 2020, 12:00 PM

Sure, here is the .ll file.


Reproduces with opt -O2 -S test2.ll.

In D91726#2475301, @pcc wrote:

Sure, here is the .ll file.


Reproduces with opt -O2 -S test2.ll.

Thank you, i can reproduce now.
This appears to be a very dumb mistake of forgetting to check the basic block of the PHI node, will fixup in a moment.

In D91726#2475301, @pcc wrote:

Sure, here is the .ll file.


Reproduces with opt -O2 -S test2.ll.

Thank you, i can reproduce now.
This appears to be a very dumb mistake of forgetting to check the basic block of the PHI node, will fixup in a moment.

Fixed in 51879a525649c8151f7e841b66a5cea0e1c8e74e, thank you for the reproducer!