Page MenuHomePhabricator

Analysis: Add a GenericCycleInfo analysis
AcceptedPublic

Authored by nhaehnle on Jul 2 2020, 2:10 PM.

Details

Summary

This analysis allows algorithms to capture all loops, including irreducible
loops, in a structured way. Based on Havlak (1997), Nesting of Reducible and
Irreducible Loops. See the definition of a "cycle" in the header file and
the IR test cases for more detail.

This patch also immediately adds (new and old-style) IR function passes.

Change-Id: I91f0d001d18906126961dc4aa2f8727ad4aff87c

Diff Detail

Event Timeline

nhaehnle created this revision.Jul 2 2020, 2:10 PM
Herald added a project: Restricted Project. · View Herald TranscriptJul 2 2020, 2:10 PM

I'll have to leave the implementation review to analysis specialists, but I noticed a few minors.

llvm/include/llvm/Analysis/CycleInfo.h
20

Do you need to include BasicBlock + Dominators? Can you use forward declarations instead?

llvm/include/llvm/Analysis/GenericCycleInfo.h
129 ↗(On Diff #275236)

Do you need to include all these? Can you use forward declarations got any instead?

arsenm added inline comments.Jul 3 2020, 7:35 AM
llvm/include/llvm/Analysis/GenericCycleInfo.h
149 ↗(On Diff #275236)

SmallVector?

153 ↗(On Diff #275236)

SmallVector?

160 ↗(On Diff #275236)

Not sure where this uint typedef is coming from

479 ↗(On Diff #275236)

Is this in a future patch?

llvm/lib/Analysis/GenericCycleInfo.cpp
80 ↗(On Diff #275236)

I think auto hurts here, and this should explicitly be std::unique_ptr

99 ↗(On Diff #275236)

I think there is an is_contained for this pattern

136 ↗(On Diff #275236)

!is_contained

178 ↗(On Diff #275236)

Unused variable warning in release build

192–200 ↗(On Diff #275236)

Might as well put these in the header?

344 ↗(On Diff #275236)

I expect documentation comments on the declarations in the header, not in the implementation

427 ↗(On Diff #275236)

I think it would be more helpful to have this return a bool for fail/pass, and not directly assert. The assert conditions could print more about why it's not valid (although there so many asserts, this might be annoying)

439–440 ↗(On Diff #275236)

is_contained

444 ↗(On Diff #275236)

Unused variable in release

453 ↗(On Diff #275236)

is_contained

472 ↗(On Diff #275236)

is_contained

nhaehnle marked 17 inline comments as done.Jul 3 2020, 12:06 PM

Thank you for the feedback. I've addressed things locally, will update the patch once I've gone through the whole series (probably on Monday)

llvm/include/llvm/Analysis/CycleInfo.h
20

Cleaned up locally.

llvm/include/llvm/Analysis/GenericCycleInfo.h
129 ↗(On Diff #275236)

GenericDomTree was a left-over, removed locally.

149 ↗(On Diff #275236)

This is following LoopBase, which uses a std::vector for child loops. I think it makes sense, given that most loops probably don't have any child loops.

m_entries is different: LoopBase doesn't have an equivalent, and we'd expect almost all loops to be natural loops, i.e. with exactly one entry.

153 ↗(On Diff #275236)

Also following LoopBase.

160 ↗(On Diff #275236)

Locally changed to unsigned.

479 ↗(On Diff #275236)

No. I found it hard to implement these kind of templates correctly without code that actually uses them, and since LoopInfo doesn't implement those parts of GraphTraits either, well...

llvm/lib/Analysis/GenericCycleInfo.cpp
80 ↗(On Diff #275236)

You mean in terms of readability? I thought it'd be clear because the type is on the RHS, but in any case I've changed it locally.

99 ↗(On Diff #275236)

TIL. Locally replaced this throughout my changes.

344 ↗(On Diff #275236)

Hmm, I've found different precedents for this in LLVM, e.g. IRBuilder.cpp has a bunch of documentation comments on methods.

Personally, I find it more convenient in the source file: IDEs generally pick the comments up either way, and this keeps the header files leaner which allows the reader to get a quicker overview of what the class offers.

427 ↗(On Diff #275236)

It's not clear to me why the fail/pass return would be more helpful?

nhaehnle updated this revision to Diff 275815.Jul 6 2020, 1:04 PM
  • cleanup #includes
  • use is_contained instead of llvm::find(range, ...) != range.end() pattern
  • mark some variables as unused in release builds
  • address additional review comments
arsenm added inline comments.Jul 9 2020, 2:53 PM
llvm/lib/Analysis/GenericCycleInfo.cpp
420 ↗(On Diff #275815)

If this is going to be assert-based, might as well disable the whole function ifndef NDEBUG?

427 ↗(On Diff #275236)

I sometimes have called these type of verifiers in the middle of passes in gdb but it's not that important

nhaehnle marked an inline comment as done.Jul 24 2020, 8:58 AM
nhaehnle added inline comments.
llvm/lib/Analysis/GenericCycleInfo.cpp
427 ↗(On Diff #275236)

I'm going down the error message path. It is slightly more convenient -- the error messages probably aren't the most helpful, but at least they are distinct so you can always put a breakpoint there if you want to explore further.

nhaehnle updated this revision to Diff 280484.Jul 24 2020, 9:14 AM
v6:
- rename {to,from}Generic -> {wrap,unwrap}Ref
- validateTree prints errors and returns bool now instead of
  using assertions
arsenm accepted this revision.Aug 4 2020, 1:52 PM

LGTM

This revision is now accepted and ready to land.Aug 4 2020, 1:52 PM
tschuett added inline comments.
llvm/include/llvm/Analysis/GenericCycleInfo.h
146 ↗(On Diff #280484)

m_XX looks like LLDB coding style and not LLVM.

nhaehnle updated this revision to Diff 284196.Aug 9 2020, 7:15 AM
v7:
- add llvm::Cycle alias
- add GenericCycleBase::isRoot and fix ::isNaturalLoop
- fix a number of bugs in GenericCycleInfoBase::extendCycle
  and add a `transferredBlocks` argument
- use a "check" macro in validateTree so that a single breakpoint can
  catch all validation errors
nhaehnle updated this revision to Diff 310473.Dec 9 2020, 2:47 AM

v9:

  • rebase on factored-out Handle infrastructure