This is an archive of the discontinued LLVM Phabricator instance.

[LoopInfo] Add a routine for verification by recomputation.
ClosedPublic

Authored by mzolotukhin on Aug 11 2016, 6:41 PM.

Details

Summary

Current implementation of LI verifier isn't ideal and fails to detect
some cases when LI is incorrect. For instance, it checks that all
recorded loops are in a correct form, but it has no way to check if
there are no more other (unrecorded in LI) loops in the function. This
patch adds a way to detect such bugs.

Examples of potential use:

  • In PR28888 loop-unroll breaks LI, but we don't detect it (with this patch we will).
  • IRCE breaks LI in IRCE/with-parent-loops.ll test. I'm xfail-ing this test for now (I'll file a separate PR for it).

Diff Detail

Event Timeline

mzolotukhin retitled this revision from to [LoopInfo] Add a routine for verification by recomputation..
mzolotukhin updated this object.
mzolotukhin added reviewers: chandlerc, sanjoy, hfinkel.
mzolotukhin added subscribers: silvas, llvm-commits.

I filed PR28944 for the IRCE issue.

chandlerc added inline comments.Aug 11 2016, 7:04 PM
lib/Analysis/LoopInfo.cpp
707–708

Rather than this, how about putting this into verify (and behind a command line flag if necessary) and computing a fresh DomTree rather than trusting whatever the analysis manager might have?

  • Move new verifier to the existing verify() routine.
  • Remove XFAIL.
mzolotukhin marked an inline comment as done.Aug 23 2016, 5:55 PM

Hi,

I moved the new logic to verify() routine, does it look good? I'm not convinced that we need to recalculate DT though: we have a separate verifier for it and in my view recalculating it here would be functionality duplication to some extent. IOW I think we should rely on DT being correct and use verifiers to make sure it holds true; if we don't trust corresponding verifiers, we should fix them. Does it make sense?

Thanks,
Michael

chandlerc accepted this revision.Aug 31 2016, 2:00 AM
chandlerc edited edge metadata.

Sorry for the delay. Feel free to commit, this is all just nit picky stuff that can be sorted out and even changed afterward if desired.

I moved the new logic to verify() routine, does it look good? I'm not convinced that we need to recalculate DT though: we have a separate verifier for it and in my view recalculating it here would be functionality duplication to some extent. IOW I think we should rely on DT being correct and use verifiers to make sure it holds true; if we don't trust corresponding verifiers, we should fix them. Does it make sense?

It makes a certain amount of sense. I guess my view is more that if someone adds the loop verify pass because their loop pass is misbehaving, it'll be frustrating of the verify misses the issue because of an out-of-date dominator tree.

We could instead verify the dominator tree, or just compute a known-correct one. I could see reasonable arguments in both directions.

As perhaps a better rationale -- imagine someone is writing code to update LoopInfo (and possibly DominatorTree). They call verify as part of their update to debug stuff. Is it reasonable to have imposed an ordering requirement that the dominator tree update be applied first?

Anyways, this isn't a big deal, just that I somewhat prefer that where possible each verify step be as free-standing of other passes and state as possible in order to isolate problems. And here, we can compute the dominator tree with a single function call so it seems very much low-cost.

Some minor comments below about the particular code used. Happy for these to be "post commit" comments or whatever that you address as you go.

include/llvm/Analysis/LoopInfoImpl.h
535–541

Why not a lambda below? It wouldn't need to be a generic lambda as its already inside a function template and within that context you have specific types BlockT and LoopT already.

544

Same question, why not a lambda?

549–552

std::sort and std::equals? Seems simpler and there is no order concern.

This revision is now accepted and ready to land.Aug 31 2016, 2:00 AM
This revision was automatically updated to reflect the committed changes.

Thanks, committed in r280280.

For DT recalculation we need to get Function from somewhere and I don't see an easy way to get it now. As for DT verification, it's possible, and I don't feel strong about either way, but slightly prefer keeping the stuff separate as we have an easy way to invoke each verifier both from command line and in the code.

Thanks,
Michael

include/llvm/Analysis/LoopInfoImpl.h
535–541

Can lambda be recursive?

544

Fixed.

549–552

Done, thanks!

mehdi_amini added inline comments.Aug 31 2016, 1:06 PM
llvm/trunk/include/llvm/Analysis/LoopInfoImpl.h
552 ↗(On Diff #69894)

I'd expect it to be possible to get the Function at any time using BBMap.begin().first->getParent() here (assuming an early exit if empty earlier).