Page MenuHomePhabricator

CycleInfo: Introduce cycles as a generalization of loops
AcceptedPublic

Authored by sameerds on Oct 28 2021, 2:19 AM.

Details

Summary

LLVM loops cannot represent irreducible structures in the CFG. This
change introduce the concept of cycles as a generalization loops,
along with a CycleInfo analysis that discover a nested
hierarchy of such cycles. This is based on Havlak (1997), Nesting of
Reducible and Irreducible Loops.

The cycle analysis is implemented as a generic template and then
instatiated for LLVM IR and Machine IR. The template relies on a new
GenericSsaContext template which must be specialized when used for
each IR.

This review is a restart of an older review request:
https://reviews.llvm.org/D83094

Original implementation by Nicolai Hähnle <nicolai.haehnle@amd.com>,
with recent refactoring by Sameer Sahasrabuddhe <sameer.sahasrabuddhe@amd.com>

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes

How much boilerplate would you need to support MLIR as well?

This change is a rehash of an earlier attempt, which involved a lot of discussion about moving towards a common abstraction for CFG + SSA. The issues are more involved than boilerplate in the implementation (hint: MLIR does not have PHI nodes). The following email would be a good starting point if you want to dive in:

[llvm-dev] [RFC] Abstracting over SSA form IRs to implement generic analyses
Nicolai Hähnle
https://lists.llvm.org/pipermail/llvm-dev/2020-December/147433.html

(The added test seems to fail the CI right now)

sameerds updated this revision to Diff 383281.Oct 29 2021, 2:50 AM

Addressed review comments

foad added inline comments.Oct 29 2021, 2:57 AM
llvm/include/llvm/ADT/GenericCycleInfo.h
137

Typo "possibly"

sameerds marked 16 inline comments as done.Oct 29 2021, 3:03 AM
sameerds added inline comments.
llvm/docs/UserGuides.rst
30

I thought so too, but this original source file is DOS formatted, and Emacs faithfully added the Windows-style new lines.

llvm/include/llvm/ADT/GenericCycleImpl.h
21

I am not sure what the objection is. This comment simply explains what to do if there is an LLVM_DEBUG occurrence. This file specifically does not define DEBUG_TYPE so that the messages can be enabled by the file that actually specializes these templates. It so happens that this particular file does not contain any LLVM_DEBUG messages, but I am using this as a standard header for more such files in the pipeline.

llvm/include/llvm/ADT/GenericCycleInfo.h
55

An internet search revealed that things get interesting when a single-line comment has a trailing backslash and useful code on the next line. The backslash eats up the new-line , and on some platforms, depending on the definition of new-line, the useful code is eaten up by the comment.

Clearly, no such issue here inside a block of single-line comments.

226

Those braces enclose an initializer list and not a block of statements. Hence no space inside them.

foad added inline comments.Oct 29 2021, 3:13 AM
llvm/include/llvm/ADT/GenericCycleImpl.h
21

No strong objection, it just seems like the kind of comment you could put in any header file in the whole project, which suggests to me that it's not adding much value.

llvm/include/llvm/ADT/GenericCycleInfo.h
226

Good point! I'm still not used to braced initializer lists.

arsenm added inline comments.Oct 29 2021, 6:13 AM
llvm/include/llvm/ADT/GenericCycleImpl.h
21

I thought you had to define LLVM_DEBUG after any includes to avoid some issue

sameerds updated this revision to Diff 383997.Nov 2 2021, 1:39 AM
sameerds marked 3 inline comments as done.
  • added specific wording from paper to description of cycle tree
  • added LLVM_DEBUG to implementation
  • fixed typos
sameerds marked 7 inline comments as done.Nov 2 2021, 1:43 AM
sameerds added inline comments.
llvm/docs/CycleTerminology.rst
86

I think this needs to say "D properly dominates", with the usual convention that a block dominates itself but does not properly dominate itself. (We don't seem to have a domination terminology doc.)

Fixed this by requiring that D is not contained in P. The statement is not true if D is in P!

llvm/include/llvm/ADT/GenericCycleImpl.h
21

Fixed all of this by defining DEBUG_TYPE in the template implementation itself. This is closer to how the macro is defined in other header files.

sameerds updated this revision to Diff 384646.Nov 3 2021, 8:35 PM
sameerds marked 2 inline comments as done.

"uint" broke the Windows build

foad added a reviewer: ruiling.Nov 4 2021, 1:26 AM

LGTM overall. I only skimmed through the algorithmic parts. Personally I would be happy to take it on trust that the analysis does what Havlak says and works as described, unless someone volunteers to do a much deeper review of the implementation.

llvm/include/llvm/ADT/GenericCycleInfo.h
297

Typoe "filed".

ruiling added inline comments.Nov 5 2021, 7:33 PM
llvm/docs/CycleTerminology.rst
30

Why do we need this root cycle? All the blocks of a function mostly do not even form a strongly connected region. And this is quite different from the way LoopInfo works.

sameerds added inline comments.Nov 5 2021, 11:18 PM
llvm/docs/CycleTerminology.rst
30

Why do we need this root cycle? All the blocks of a function mostly do not even form a strongly connected region. And this is quite different from the way LoopInfo works.

I should copy a comment from GenericCycleInfo class to this spec. Essentially, the "root" is a placeholder cycle that allows CycleInfo to be treated as a single tree. Then we can use GraphTraits as follows (see validateTree() in GenericCycleImpl.h):

for (const CycleT *cycle : depth_first(getRoot())) { ... }
ruiling added inline comments.Sun, Nov 7, 5:54 AM
llvm/docs/CycleTerminology.rst
30

My point is that the root cycle is actually not a cycle based on the definition of cycle. And If we want to check whether a block is inside any loop, we just check whether getLoopFor(block) returns nullptr, but that is not true in CycleInfo. This may be confusing for people switching from LoopInfo to CycleInfo. Am I over-concerned? I am not familiar with GraphTraits. So if we follow the same idea as LoopInfo, code will be quite complex, right?

ruiling added inline comments.Sun, Nov 7, 10:11 PM
llvm/include/llvm/ADT/GenericCycleImpl.h
72

The implementation here looks good to me. just a few comments on the naming.

84

I think we capitalize the term DFS when naming variables within LLVM? at least I found most occurrences of DFS are capitalized.

98

Cycle is too general here. What about NewCycle to indicate that this is the newly discovered cycle?

139

I think it may be better to rename C as OuterMostCycle or some other reasonable name indicating that this is the outermost cycle discovered so far for this block.

critson added inline comments.Wed, Nov 10, 7:11 PM
llvm/lib/CodeGen/MachineSsaContext.cpp
43 ↗(On Diff #384646)

This needs to be able to deal with physical registers.

sameerds updated this revision to Diff 386460.Thu, Nov 11, 2:25 AM
  • Fixed some doxygen comments.
  • Eliminated the "root" cycle.
  • Cycle should not point to CycleInfo; it's hard to update that reference. Fixed the side-effects of eliminating that reference.
  • Fixed names mentioned in review comments.
  • Extracted two helper functions: getTopLevelParent() and moveToNewParent(). Both very helpful in improving readability.
  • SsaContext now keeps a reference to the Function so that user analyses can retrieve it. Forward looking change, found to be useful in later analyses not introduced yet.
sameerds marked 6 inline comments as done and an inline comment as not done.Thu, Nov 11, 2:29 AM
sameerds added inline comments.
llvm/docs/CycleTerminology.rst
30

I see now. Thanks for pointing out the parallel with LoopInfo, it might be useful in the future. I've now eliminated the root cycle. Luckily, it did not cause much side-effects in other places.

llvm/include/llvm/ADT/GenericCycleImpl.h
84

CamelCase for acronym seems to be pretty inconsistent in the LLVM codebase, and the coding standard does not say anything specific. For example, I found instances of both Cfg/CFG and Dag/DAG. I am happy to change the name it if there is a strong preference for "DFS" instead of "Dfs". But in support of my choice, CamelCase makes it easier to read "DfsInfo" compared to "DFSInfo". This is especially so when joining two acronyms, like "CfgSsa" compared to "CFGSSA".

I have this vague memory that once upon a time, the LLVM coding standard recommended that only the first letter be capitalized, but now I am not sure if I am just misremembering something else.

llvm/lib/CodeGen/MachineSsaContext.cpp
43 ↗(On Diff #384646)

Does the new check look better? From the implementation, it seems that getUniqueVRegDef() will gracefully handle physical registers.

Do you have any users of the analysis or any plans? Otherwise, it could be seen as dead code?

Do you have any users of the analysis or any plans? Otherwise, it could be seen as dead code?

I'm desperately awaiting this to serve as the basis for a replacement control flow lowering scheme for AMDGPU

Do you have any users of the analysis or any plans? Otherwise, it could be seen as dead code?

I'm desperately awaiting this to serve as the basis for a replacement control flow lowering scheme for AMDGPU

Thanks!

sameerds updated this revision to Diff 386768.Fri, Nov 12, 2:04 AM
sameerds marked an inline comment as done.

rebase

Thanks for this revision, the refactor make lots of sense to me. I have added some further comments. Other parts look pretty good to me.

llvm/docs/CycleTerminology.rst
34–35

It would be better we are not treating nullptr as the root-cycle unless we really have to. My understanding is that nullptr is just saying that this is the outermost cycle, it does not have any parent.

65

I am not good at English wording. But is it meaningful to say two basic blocks are siblings to each other if both of them are not in any cycle?

llvm/include/llvm/ADT/GenericCycleImpl.h
84

I think we have not explicitly require UPPERCASE for acronym in LLVM. But if you grep in LLVM source code, DFS/SSA/CFG/DAG vs Dfs/Ssa/Cfg/Dag. I think you will easily notice 90% are using the UPPERCASE. Yes, there are some occurrence of the latter version, which I don't think is a good idea. I don't like such kind of divergence situation. technically I don't have preference for one over another. But I really like most of the code could be in the same form regarding this.

278

typo, "contains \p B".

291

While it is reasonable to return nullptr when querying parent cycle of top level cycle. It does not sound reasonable that we say nullptr contains an ordinary cycle. Do you have any use case that can demonstrate we need to define the behavior of contains() to return true if input A is nullptr to get expected result? I don't know what the case you have shown contains(getCycle(F), getCycle(G) used for. IMO, null input value is just non-applicable here, we should just return false if either A or B is nullptr.

sameerds marked 3 inline comments as done.Thu, Nov 18, 7:29 PM
sameerds added inline comments.
llvm/docs/CycleTerminology.rst
34–35

Not everything can be measured with the metric of "unless we have to". Treating nullptr as the "vacuous root" (please note the term "vacuous") is worth the convenience it provides.

This is not a novelty, it happens often in formal definitions, including the paper by Havlak that this implementation is based on. Such vacuous objects are used to make life easy for inductive reasoning about formalisms. To look at it differently, think of it as 0! defined as 1 just to make it easy to write an inductive definition of the factorial function.

65

It's not about the language used. This section defines terms, and I am defining what a sibling is when neither of them are in a "real" cycle because they are both in a "vacuous" root cycle.

llvm/include/llvm/ADT/GenericCycleImpl.h
291

While the code does not contain an explicit call to contains(getCycle(F), getCycle(G), it does contain calls to contains() where one of the arguments became null just because the caller went up the hierarchy. It is much more consistent to handle this situation inside contains() than adding if (!cycle) { // then that means we are the toplevel } in multiple places.

Where it matters, I have used Optional<Cycle*> to differentiate between "no cycle" and "root cycle". I believe that my interpretation of nullptr is convenient enough that I am willing to go use the Optional<> type where it needs to be disambiguated. In fact, that is the very purpose for the existence of types like llvm::Optional<>, std::opt, and Haskell Maybe.

ruiling added inline comments.Fri, Nov 19, 7:34 PM
llvm/docs/CycleTerminology.rst
34–35

I am sorry I still don't get the point why treating nullptr as the root cycle is necessary here. And I also don't understand why "vacuous root" would help the argument here. The reason I don't want a root cycle (either a null or non-null) is it is counter-intuitive. It just makes CycleInfo different from the way LoopInfo works without any real benefits.

llvm/include/llvm/ADT/GenericCycleImpl.h
291

Could you help show me when we will passing nullptr to the first argument of contains() and we really depends on the return value should be TRUE to make caller algorithm work correctly?
Do we have many places need to check against nullptr before passing to the first argument as if (CycleA && contains(CycleA, CycleB))? And explicitly checking against a real-existed cycle for the first argument before calling this function sounds a clear way to me. I would even like we put an assert here that the first argument is not null:-)

sameerds added inline comments.Fri, Nov 19, 11:46 PM
llvm/docs/CycleTerminology.rst
34–35

Yeah, compatibility with LoopInfo definitely over-rules all my other arguments. I had been going over the interface, and I realised that CycleInfo::contains() and Loop::contains() are clearly in different places. If there is an occasion to unify them in a single interface, things will get pretty awkward.

In fact, this might be a good time to audit the entire interface and make sure it looks exactly like LoopInfo. Thanks for not letting go of this! :D

llvm/include/llvm/ADT/GenericCycleImpl.h
291

I am now working on a change that removes the special meaning of nullptr completely just because of LoopInfo. I did discover places that broke, where now I have to do if (!CycleA || contains(CycleA, CycleB). I might even be able to replace some of the !CycleA with a preceding assert instead. But none of these places are a strong justification for the current behaviour of contains().

sameerds updated this revision to Diff 389090.EditedMon, Nov 22, 8:49 PM
  • rebase
  • replace Dfg and Ssa with uppercase versions
  • eliminate any interpretation of nullptr as root cycle
  • move two functions from CycleInfo to Cycle, just like LoopInfo
  • small cleanup to the cycle terminology, pointed out by @nhaehnle
foad added inline comments.Tue, Nov 23, 1:12 AM
llvm/include/llvm/CodeGen/MachineSSAContext.h
2

Capitalize SSA

11

Capitalize SSA

sameerds updated this revision to Diff 389146.Tue, Nov 23, 3:27 AM
  • rebase
  • removed the "vacuous root" from the cycle description
sameerds added inline comments.Tue, Nov 23, 3:59 AM
llvm/include/llvm/CodeGen/MachineSSAContext.h
2

I didn't notice this when I uploaded an update a few minutes ago. I feel very bad about another update triggering yet another build in the CI system. I have fixed the problem in both places, as well as one last place that I missed in the commit description. Thanks!

ruiling accepted this revision.Tue, Nov 23, 7:26 PM

LGTM. please wait a few days before committing in case others have further comments.

llvm/include/llvm/ADT/GenericCycleInfo.h
18–25

Can you update this part to match the document?

200–202

Can you update the comment?

llvm/include/llvm/InitializePasses.h
448

This belongs to a future change?

This revision is now accepted and ready to land.Tue, Nov 23, 7:26 PM

Thank you for doing this. I'm happy with the big picture of the change obviously, though I noticed a few things inline.

llvm/include/llvm/ADT/GenericCycleImpl.h
35

Other code in this file uses the new style function definition syntax, so perhaps do so here as well to be consistent?

69

-machine, since this is generic code

llvm/include/llvm/ADT/GenericCycleInfo.h
15–16

How about moving everything of this file comment to the new CycleTerminology document (that isn't already there) and then just refer to that document here?

llvm/include/llvm/InitializePasses.h
122–123

These two don't belong here

llvm/lib/IR/SSAContext.cpp
2

Wrong filename

sameerds updated this revision to Diff 390255.Sun, Nov 28, 10:22 PM
  • rebase
  • addressed review comments
sameerds marked 17 inline comments as done.Sun, Nov 28, 10:27 PM
sameerds added inline comments.
llvm/include/llvm/ADT/GenericCycleImpl.h
35

I am not sure what you mean here ... this definition passes clang-format and clang-tidy. If you mean the lowercase ::contains, then that is valid camelBack where the first letter must be lowercase.

llvm/include/llvm/ADT/GenericCycleInfo.h
15–16

Added appropriate sections to CycleTerminology.rst.

LGTM

llvm/include/llvm/ADT/GenericCycleImpl.h
35

I meant the auto foo(...) -> T syntax.

llvm/include/llvm/ADT/GenericCycleInfo.h
10

Maybe add a "See docs/CycleTerminology.rst for a high-level overview." comment?

foad accepted this revision.Mon, Dec 6, 1:38 AM

I said:

LGTM overall. I only skimmed through the algorithmic parts. Personally I would be happy to take it on trust that the analysis does what Havlak says and works as described, unless someone volunteers to do a much deeper review of the implementation.

Still LGTM. Thanks @ruiling for doing a much more detailed review!