llvm dev - Oct 2016 - LCSSA verification for the top-level loops

Hi Michael,

+CC llvm-dev

My guess is that it would be rather error prone to pinpoint exact places where
we start populating new LPPassManager since it’s created lazily via
LoopPass::assignPassManager. So we are risking to miss adding verifiers in some
of the LPPassManager’s.

One similar idea is to introduce LCSSAVerifier function pass and make LCSSA pass
to be dependant on it. That will allow me to check
‘getAnalysisIfAvaliable<LCSSAVerifier>’  inside of the LPPassManager and
explicitly call LCSSA verification when it’s present. This feels a quite hacky,
but in theory should work.

— Igor

On 14 Oct 2016, at 01:57, Mikhail Zolotukhin <mzolotukhin at apple.com>
wrote:
> Hi Igor,
> 
> I like the second option more, and I think we can do something like this,
or even more general. I'd suggest creating a new loop pass, called e.g.
LoopVerification, and manually (at least for now) add it as a last pass to every
instance of LPM. The pass will directly call isRecursivelyInLCSSA for the
current loop, and later probably can also check other properties like
LoopSimplify This way, the verification will be executed when all loop passes
have finished working with a loop and before going to another loop. We can also
schedule it in between some passes if we'd like to, and we can schedule it
after all loop passes, placing it into a separate LPM instance. What do you
think?
> 
> For now I don't have a good idea on how to utilize PassManager to
schedule such verifiers automatically though:-(
> 
> - Michael
> 
> PS: Did you mean to send it to the list? Chandler might have good ideas
here.
> 
> 
>> On Oct 13, 2016, at 8:30 AM, Igor Laevsky <igor at
azulsystems.com> wrote:
>> 
>> Hi Michael,
>> 
>> In the https://reviews.llvm.org/D25364 we were discussing possibility
of verifying LCSSA only for the top-level loops. I started implementing this but
process appears to be a bit tricky. Problem is that I can’t find a way to check
that LPPassManager contains LCSSA pass without introducing circular dependency
between TransformUtils and Analysis libraries. I have couple of solutions in
mind but wanted to ask your opinion on those, maybe we will be able to arrive at
better decision.
>> 
>> 1. I can introduce list of loops which LCSSAWrapperPass::verifyAnalysis
needs to verify. It will be stored in the LoopInfo and populated in the
LPPassManager main loop. After verification LCSSAWrapperPass will remove loop
from this list.
> 
>> 
>> 2. There could be separate analysis “LCSSAVerification” on which LCSSA
pass will depend. That way I will be able to recognise it inside LPPassManager
and manually call verification of the current loop. Not sure how well our pass
managers can handle such dependencies.
>> 
>> None of those seem particularly appealing to me. What do you think? Is
there any better way?
>> 
>> Thanks,
>> Igor.
>> 
> 
>

> On Oct 14, 2016, at 9:54 AM, Igor Laevsky <igor at azulsystems.com>
wrote:
> 
> Hi Michael,
Hi Igor,
> 
> +CC llvm-dev
> 
> My guess is that it would be rather error prone to pinpoint exact places
where we start populating new LPPassManager since it’s created lazily via
LoopPass::assignPassManager. So we are risking to miss adding verifiers in some
of the LPPassManager’s.
That’s true, I didn’t particularly like that either, but suggested as a
potential workaround.
> 
> One similar idea is to introduce LCSSAVerifier function pass and make LCSSA
pass to be dependant on it. That will allow me to check
‘getAnalysisIfAvaliable<LCSSAVerifier>’  inside of the LPPassManager and
explicitly call LCSSA verification when it’s present. This feels a quite hacky,
but in theory should work.
We’ll always have to hack around something to pass a loop/list of loops to
verify to the function pass. Instead, I think it would be easier to create a
loop pass for LCSSAVerification and make all loop passes preserve it.

This way, when LPM would be verifying preserved analysis, it’ll run the LCSSA
verification for the current loop as well (verifyAnalysis from the new pass). We
can make it depend on the existing LCSSA pass, so that requiring this one would
result in building LCSSA if it’s not built yet. The verification itself will be
moved from the existing LCSSA pass’s verifyAnalysis to the new pass’s
verifyAnalysis (or we can keep verification in the original LCSSA pass as well,
but put it under a flag). Does it make sense?

Thanks,
Michael
> 
> — Igor
> 
> On 14 Oct 2016, at 01:57, Mikhail Zolotukhin <mzolotukhin at
apple.com> wrote:
> 
>> Hi Igor,
>> 
>> I like the second option more, and I think we can do something like
this, or even more general. I'd suggest creating a new loop pass, called
e.g. LoopVerification, and manually (at least for now) add it as a last pass to
every instance of LPM. The pass will directly call isRecursivelyInLCSSA for the
current loop, and later probably can also check other properties like
LoopSimplify This way, the verification will be executed when all loop passes
have finished working with a loop and before going to another loop. We can also
schedule it in between some passes if we'd like to, and we can schedule it
after all loop passes, placing it into a separate LPM instance. What do you
think?
>> 
>> For now I don't have a good idea on how to utilize PassManager to
schedule such verifiers automatically though:-(
>> 
>> - Michael
>> 
>> PS: Did you mean to send it to the list? Chandler might have good ideas
here.
>> 
>> 
>>> On Oct 13, 2016, at 8:30 AM, Igor Laevsky <igor at
azulsystems.com> wrote:
>>> 
>>> Hi Michael,
>>> 
>>> In the https://reviews.llvm.org/D25364 we were discussing
possibility of verifying LCSSA only for the top-level loops. I started
implementing this but process appears to be a bit tricky. Problem is that I
can’t find a way to check that LPPassManager contains LCSSA pass without
introducing circular dependency between TransformUtils and Analysis libraries. I
have couple of solutions in mind but wanted to ask your opinion on those, maybe
we will be able to arrive at better decision.
>>> 
>>> 1. I can introduce list of loops which
LCSSAWrapperPass::verifyAnalysis needs to verify. It will be stored in the
LoopInfo and populated in the LPPassManager main loop. After verification
LCSSAWrapperPass will remove loop from this list.
>> 
>>> 
>>> 2. There could be separate analysis “LCSSAVerification” on which
LCSSA pass will depend. That way I will be able to recognise it inside
LPPassManager and manually call verification of the current loop. Not sure how
well our pass managers can handle such dependencies.
>>> 
>>> None of those seem particularly appealing to me. What do you think?
Is there any better way?
>>> 
>>> Thanks,
>>> Igor.
>>> 
>> 
>> 
>

> On Oct 14, 2016, at 9:54 AM, Igor Laevsky <igor at azulsystems.com>
wrote:
>> 
>> Hi Michael,
> Hi Igor,
Hi Michael,
> 
>> 
>> +CC llvm-dev
>> 
>> My guess is that it would be rather error prone to pinpoint exact
places where we start populating new LPPassManager since it’s created lazily via
LoopPass::assignPassManager. So we are risking to miss adding verifiers in some
of the LPPassManager’s.
> That’s true, I didn’t particularly like that either, but suggested as a
potential workaround.
>> 
>> One similar idea is to introduce LCSSAVerifier function pass and make
LCSSA pass to be dependant on it. That will allow me to check
‘getAnalysisIfAvaliable<LCSSAVerifier>’  inside of the LPPassManager and
explicitly call LCSSA verification when it’s present. This feels a quite hacky,
but in theory should work.
> We’ll always have to hack around something to pass a loop/list of loops to
verify to the function pass. Instead, I think it would be easier to create a
loop pass for LCSSAVerification and make all loop passes preserve it.
> 
> This way, when LPM would be verifying preserved analysis, it’ll run the
LCSSA verification for the current loop as well (verifyAnalysis from the new
pass). We can make it depend on the existing LCSSA pass, so that requiring this
one would result in building LCSSA if it’s not built yet. The verification
itself will be moved from the existing LCSSA pass’s verifyAnalysis to the new
pass’s verifyAnalysis (or we can keep verification in the original LCSSA pass as
well, but put it under a flag). Does it make sense?
Seems like verifyAnalysis for LoopPass doesn’t receive any information about
current loop, which leaves us with the same problem of verifying all loops on
each iteration. I guess we can introduce new verifyLoopAnalysis(Loop *L) method
and call it for all loop passes. It will also require separate
verifyPreservedLoopAnalysis(Loop *L). This seems like a cleanest solution. What
do you think?

What I was referring to is that we can write something like this inside
LPPassManager iteration:
  if (getAnalaysisIfAvaliable<LCSSAVerifier>()) {
CurrentLoop->verifyLCSSA(); )
This will have less impact but feels a bit wrong.
> 
> Thanks,
> Michael
> 
>> 
>> — Igor
>> 
>> On 14 Oct 2016, at 01:57, Mikhail Zolotukhin <mzolotukhin at
apple.com> wrote:
>> 
>>> Hi Igor,
>>> 
>>> I like the second option more, and I think we can do something like
this, or even more general. I'd suggest creating a new loop pass, called
e.g. LoopVerification, and manually (at least for now) add it as a last pass to
every instance of LPM. The pass will directly call isRecursivelyInLCSSA for the
current loop, and later probably can also check other properties like
LoopSimplify This way, the verification will be executed when all loop passes
have finished working with a loop and before going to another loop. We can also
schedule it in between some passes if we'd like to, and we can schedule it
after all loop passes, placing it into a separate LPM instance. What do you
think?
>>> 
>>> For now I don't have a good idea on how to utilize PassManager
to schedule such verifiers automatically though:-(
>>> 
>>> - Michael
>>> 
>>> PS: Did you mean to send it to the list? Chandler might have good
ideas here.
>>> 
>>> 
>>>> On Oct 13, 2016, at 8:30 AM, Igor Laevsky <igor at
azulsystems.com> wrote:
>>>> 
>>>> Hi Michael,
>>>> 
>>>> In the https://reviews.llvm.org/D25364 we were discussing
possibility of verifying LCSSA only for the top-level loops. I started
implementing this but process appears to be a bit tricky. Problem is that I
can’t find a way to check that LPPassManager contains LCSSA pass without
introducing circular dependency between TransformUtils and Analysis libraries. I
have couple of solutions in mind but wanted to ask your opinion on those, maybe
we will be able to arrive at better decision.
>>>> 
>>>> 1. I can introduce list of loops which
LCSSAWrapperPass::verifyAnalysis needs to verify. It will be stored in the
LoopInfo and populated in the LPPassManager main loop. After verification
LCSSAWrapperPass will remove loop from this list.
>>> 
>>>> 
>>>> 2. There could be separate analysis “LCSSAVerification” on
which LCSSA pass will depend. That way I will be able to recognise it inside
LPPassManager and manually call verification of the current loop. Not sure how
well our pass managers can handle such dependencies.
>>>> 
>>>> None of those seem particularly appealing to me. What do you
think? Is there any better way?
>>>> 
>>>> Thanks,
>>>> Igor.
>>>> 
>>> 
>>> 
>> 
>