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
130

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
150

SmallVector?

154

SmallVector?

161

Not sure where this uint typedef is coming from

480

Is this in a future patch?

llvm/lib/Analysis/GenericCycleInfo.cpp
81

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

100

I think there is an is_contained for this pattern

137

!is_contained

179

Unused variable warning in release build

193–201

Might as well put these in the header?

345

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

428

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)

440–441

is_contained

445

Unused variable in release

454

is_contained

473

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
130

GenericDomTree was a left-over, removed locally.

150

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.

154

Also following LoopBase.

161

Locally changed to unsigned.

480

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
81

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.

100

TIL. Locally replaced this throughout my changes.

345

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.

428

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
421

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

428

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.Fri, Jul 24, 8:58 AM
nhaehnle added inline comments.
llvm/lib/Analysis/GenericCycleInfo.cpp
428

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.Fri, Jul 24, 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.Tue, Aug 4, 1:52 PM

LGTM

This revision is now accepted and ready to land.Tue, Aug 4, 1:52 PM
tschuett added inline comments.
llvm/include/llvm/Analysis/GenericCycleInfo.h
147

m_XX looks like LLDB coding style and not LLVM.

nhaehnle updated this revision to Diff 284196.Sun, Aug 9, 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