[LLVMdev] Rotated loop identification

[Hal Finkel]

----- Original Message -----
> From: "Andrew Trick" <atrick at apple.com>
> To: "Michele Scandale" <michele.scandale at gmail.com>
> Cc: "llvmdev at cs.uiuc.edu List" <llvmdev at cs.uiuc.edu>
> Sent: Thursday, February 7, 2013 11:56:42 PM
> Subject: Re: [LLVMdev] Rotated loop identification
> 
> 
> 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

If you're in favor of this approach, can I pop out of the woodwork and say that it appears that we have a reasonably-large group of contributors in favor of an invariant intrinsic and we should move forward on that basis?

Thanks again,
Hal

> 
> 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
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>