llvm dev - Feb 2013 - [LLVMdev] Rotated loop identification

> Thanks for the details. Please add them to a bug report.
I will do this.
> 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.
> 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?

Thanks again.

Best regards,
Michele Scandale

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

----- 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
>

On 02/08/2013 06:56 AM, Andrew Trick wrote:
> 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
>
I read the post you suggested. If I understood correctly the idea I like it very
much. Just to better understand, when you say <<< It would be generally
useful
to model an intrinsic that is free and not a strong use but does have control 
dependence. That's what I call a meta-intrinsic. >>> you mean that
this class of
intrinsics cannot be removed because they have no uses and the can't be
moved
freely, e.g. hoisted from a loop?
Indeed, if they handle a value (they are users), that value would never be 
eliminated if the only user is the meta-intrinsic itself? Maybe this kind of 
behaviour must be a parameter respect to the semantic you need to implement (At 
the end, if the intrinsic is the only user and during lowering is simply 
eliminated all the values used can be checked to be dead and deleted in that
case).
IMHO this is like a property that an intrinsic can have or not and the proposed 
llvm.invariant intrinsic is a particular intrinsic that has this property and 
whose semantic is to describe invariant facts (the metadata language you
mentioned).

Thanks again.

Best regards,
Michele Scandale