[llvm-dev] Why LLVM cannot optimize this?

[Sanjoy Das via llvm-dev]

[+CC Andy]

A similar issue also comes up in cases like this:

int clz(unsigned long val) {
  unsigned result = sizeof(unsigned long);
  if (val) {
    do {
      result--;
      val >>= 1;
    } while (val);
  }
  return result;
}

where we'd like to be able to compute the tripcount of the loop as
"sizeof(long) - clz(val) - 1" and get rid of the loop entirely via
RewriteLoopExitValues.

The reason why the above issue is "similar" to wanting a "SCEVPowExpr"
is that both are examples of SCEV node kinds that will be useful in
some very specific cases; but probably is not seen widely enough that
teaching whole of ScalarEvolution how to simplify these is a good
idea.

To get around this, I've been thinking (and only thinking, no code yet
:) ) about adding a possible "SCEVIntrinsicExpr", parameterized by an
"OpCode", like SCEVIntrinsicExpr::Pow or
SCEVIntrinsicExpr::CountLeadingZeroes.  The idea is that these would
be a low-overhead way of adding new kinds of expressions to the SCEV
hierarchy, with the only constraints being:

 - They're a pure, mathematically function of their input values
 - SCEVExpander knows how to expand them
 - It is always safe to treat them as SCEVUnknowns

-- Sanjoy