[LLVMdev] Rotated loop identification

[Andrew Trick]

On Feb 7, 2013, at 10:53 AM, Michele Scandale <michele.scandale at gmail.com> wrote:

>> Thanks for the details. Please add them to a bug report.
> 
> I will do this.

Thanks.

>> InstCombine is certainly interfering with our ability to analyze the loop. I think the problem is that ScalarEvolution cannot reason about signed division. This is a general problem independent of your target. At the moment I'm not sure if we can teach ScalarEvolution to reason about this, or if we can defer certain InstCombine's until after loop passes run, including target-specific loop passes (it's hard for me to say whether this InstCombine really a necessary canonicalization before other passes). A bug report would be appropriate.
> 
> It sounds to me that the same capabilities of InstCombine should be implemented
> also in the ScalarEvolution.

It's doable, just not pretty. We could special-case SCEV's isImpliedCond to look for an sdiv opcode and recognize the inverse of InstCombine's trick. I doubt it makes sense to add an SDIV operator to SCEV since SCEV would want to assume modulus division, and the IR sdiv is a truncating divide.

>> Absent a fix for the above problem, it is certainly possible for you to add target-specific intrinsics. I can't guarantee that it won't interfere with optimization. It might also be possible to add metadata to the loop exit branch when it is cloned by LoopRotate, indicating that the loop is guarded by the same condition. I don't think we want something like this on trunk though since it is a heavy-handed workaround that could be hard to maintain.
> 
> Following also the proposal 'Parallel Loop Metadata' it seems to me that
> basically there's the same problem. Maybe I've not fully understood the things
> but, assuming to have the ability to map metadata to BasicBlocks then such
> informations could be registered directly to the loop header or latch, without
> custom intrinsics and hopefully without interfering with the optimizer.
> 
> What do you think about this?

There's been talk of adding metata do the branch that terminates the loop latch block. What llvm calls the "latch" is just a unique backward branch to the loop header and not necessarilly even a loop exit.

I'm not sure how you would interpret that metadata, since the branch exit may be rewritten (just like the loop guard). For example, the indvars pass may convert it into a != test.

As long as this is brainstorming time, I actually like the idea of an llvm.invariant intrinsic that the optimizers know to ignore. I like it for other purposes, but would happen to work for you as a temporary workaround. It could take one or two IR values (as metadata operands) and a metadata language describing the invariant, such as a relational operator and optional constant. In your case, you want to know that the loop counter's starting value is less than its limit, so you could conveniently plop one of those in the loop preheader. The invariant would only go away if no one else used the value, which in your case would make sense (e.g. if the loop test were rewritten in terms of %b, you probably wouldn't need the invariant any more).

http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20121210/158601.html

But really, the only thing likely to make it onto trunk for this bug is the SCEV fix mentioned above. More details can be discussed in PR15205.

-Andy