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

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

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.

Hi Igor,

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

Indeed, I see the issue now.

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?

The thing is that we seemingly haven’t had loop analyses so far, and probably never will have them, as analyses usually work in at least a function scope. While adding verifyPreservedLoopAnalysis and verifyLoopAnalysis seem kind of ok to me, I think in the end it will only be used for verification of LCSSA and LoopSimplify, which I don’t really like.

What I was referring to is that we can write something like this inside LPPassManager iteration:
if (getAnalaysisIfAvaliable()) { CurrentLoop->verifyLCSSA(); )
This will have less impact but feels a bit wrong.

Originally I didn’t like this idea, but the more I think about it the more I like it. Currently all loop passes use (or should use) getLoopAnalysisUsage to record their pass requirements, so all of them should operate on the same set of analyses. What we can do is to add a function verifyLoopAnalyses to LPM and make it call verifiers for all these analyses.

So, instead of
if (getAnalaysisIfAvaliable()) { CurrentLoop->verifyLCSSA(); )
we will have
verifyLoopAnalyses(CurrentLoop);
which will do:
CurrentLoop->verifyLCSSA();
CurrentLoop->verifyLoopSimplify(); // For beginning we can skip everything except LCSSA
CurrentLoop->verifySomethingElse()

etc.

What do you think?

  • Michael

Hi Igor,

Hi Michael,

Hi Igor,

Hi Michael,

Hi Michael,

What I was referring to is that we can write something like this inside LPPassManager iteration:
if (getAnalaysisIfAvaliable()) { CurrentLoop->verifyLCSSA(); )
This will have less impact but feels a bit wrong.

Originally I didn’t like this idea, but the more I think about it the more I like it. Currently all loop passes use (or should use) getLoopAnalysisUsage to record their pass requirements, so all of them should operate on the same set of analyses. What we can do is to add a function verifyLoopAnalyses to LPM and make it call verifiers for all these analyses.

So, instead of
if (getAnalaysisIfAvaliable()) { CurrentLoop->verifyLCSSA(); )
we will have
verifyLoopAnalyses(CurrentLoop);
which will do:
CurrentLoop->verifyLCSSA();
CurrentLoop->verifyLoopSimplify(); // For beginning we can skip everything except LCSSA
CurrentLoop->verifySomethingElse()

etc.

What do you think?

Unfortunately there are loop print passes (LoopPassPrinter and PrintLoopPassWrapper) which don’t require LCSSA. And I think it’s important to support ability to print loops without mandatory LCSSA verification. Probably loop printers can be converted to function passes, but in that case we will execute them only once per LPPassManager, which is also not an option. Now I’m not sure how to better bypass this issue. Do you have any ideas?

Hi Igor,

Hi Igor,

Hi Michael,

Hi Igor,

Hi Michael,

Hi Michael,

What I was referring to is that we can write something like this inside LPPassManager iteration:
if (getAnalaysisIfAvaliable()) { CurrentLoop->verifyLCSSA(); )
This will have less impact but feels a bit wrong.

Originally I didn’t like this idea, but the more I think about it the more I like it. Currently all loop passes use (or should use) getLoopAnalysisUsage to record their pass requirements, so all of them should operate on the same set of analyses. What we can do is to add a function verifyLoopAnalyses to LPM and make it call verifiers for all these analyses.

So, instead of
if (getAnalaysisIfAvaliable()) { CurrentLoop->verifyLCSSA(); )
we will have
verifyLoopAnalyses(CurrentLoop);
which will do:
CurrentLoop->verifyLCSSA();
CurrentLoop->verifyLoopSimplify(); // For beginning we can skip everything except LCSSA
CurrentLoop->verifySomethingElse()

etc.

What do you think?

Unfortunately there are loop print passes (LoopPassPrinter and PrintLoopPassWrapper) which don’t require LCSSA. And I think it’s important to support ability to print loops without mandatory LCSSA verification.

In this case we can leave “if(getAnalaysisIfAvaliable())” as you suggested originally. However, what do we lose if we require all loop passes to require and preserve LCSSA? Why can’t we just require LCSSA in the loop printers as well? We discussed that with Chandler some time ago, and there even was an idea to make it an IR property (i.e. IR would be considered invalid if LCSSA is broken) - it’s still just an idea though.

Probably loop printers can be converted to function passes, but in that case we will execute them only once per LPPassManager, which is also not an option. Now I’m not sure how to better bypass this issue. Do you have any ideas?

Michael

Hi Michael,

Unfortunately there are loop print passes (LoopPassPrinter and PrintLoopPassWrapper) which don’t require LCSSA. And I think it’s important to support ability to print loops without mandatory LCSSA verification.

In this case we can leave “if(getAnalaysisIfAvaliable())” as you suggested originally. However, what do we lose if we require all loop passes to require and preserve LCSSA? Why can’t we just require LCSSA in the loop printers as well? We discussed that with Chandler some time ago, and there even was an idea to make it an IR property (i.e. IR would be considered invalid if LCSSA is broken) - it’s still just an idea though.

I think it’s useful to assume that loop pass printer never changes the IR and always prints it exactly as it is. Unless, of course, we introduce general invariant that loops are always in the LCSSA form. But current problem alone seems like a weak motivation for doing such thing.
I’ll proceed with “getAnalaysisIfAvaliable” approach then and will send a review in the near future.

  • Igor