This is an archive of the discontinued LLVM Phabricator instance.

[LoopInfo] empty() -> isInnermost(), add isOutermost()
ClosedPublic

Authored by baziotis on Jun 30 2020, 11:16 AM.

Diff Detail

Event Timeline

baziotis created this revision.Jun 30 2020, 11:16 AM
Herald added a project: Restricted Project. · View Herald TranscriptJun 30 2020, 11:16 AM

I created the review instead of just committing to discuss that it may be a good idea to even rename this e.g. to "isInnermost()".
With "empty()", it's not clear if the implementation is:
return getSubLoops().empty() or return !getNumBlocks() (or something else)

fhahn added a subscriber: fhahn.Jun 30 2020, 11:49 AM

I created the review instead of just committing to discuss that it may be a good idea to even rename this e.g. to "isInnermost()".
With "empty()", it's not clear if the implementation is:
return getSubLoops().empty() or return !getNumBlocks() (or something else)

I think using empty makes sense in the context of begin() and end() also iterating over subloops.

llvm/include/llvm/Analysis/LoopInfo.h
158

make a doc-comment (///)? It might be good to mention sub-loops in the comment, e.g something like Return true if the loop contains any sub-loops.

I created the review instead of just committing to discuss that it may be a good idea to even rename this e.g. to "isInnermost()".
With "empty()", it's not clear if the implementation is:
return getSubLoops().empty() or return !getNumBlocks() (or something else)

I think using empty makes sense in the context of begin() and end()

Indeed.

also iterating over subloops.

I think that isInnermost() would make even more sense. That is, one iterates until they reach the innermost loop.

Personally, in uses like this: https://github.com/llvm/llvm-project/blob/master/llvm/lib/Analysis/LoopAccessAnalysis.cpp#L1768
it doesn't make much sense (although here it does because of the comment and error msg).

One alternative would be to make an isInnermost() wrapper.

baziotis updated this revision to Diff 274575.Jun 30 2020, 12:02 PM

Address comment.

baziotis marked an inline comment as done.Jun 30 2020, 12:02 PM

I think that isInnermost() would make even more sense.

I'm fine with adding bool isInnermost() const { return empty(); } and while we are at it, bool isOutermost().

@fhahn @Meinersbur @Whitney @etiotto Objections?

I think that isInnermost() would make even more sense.

I'm fine with adding bool isInnermost() const { return empty(); } and while we are at it, bool isOutermost().

@fhahn @Meinersbur @Whitney @etiotto Objections?

I think the proposed name isInnermost is fine. No objections on my part.

I think that isInnermost() would make even more sense.

I'm fine with adding bool isInnermost() const { return empty(); } and while we are at it, bool isOutermost().

@fhahn @Meinersbur @Whitney @etiotto Objections?

No objections as well.

Thanks for the reviews, I'm updating.

baziotis updated this revision to Diff 275259.Jul 2 2020, 4:48 PM

Added isInnermost/Outermost.

fhahn added a comment.Jul 3 2020, 2:23 AM

I think that isInnermost() would make even more sense.

I'm fine with adding bool isInnermost() const { return empty(); } and while we are at it, bool isOutermost().

@fhahn @Meinersbur @Whitney @etiotto Objections?

Hm, adding multiple ways to check the same thing may lead to other problems. IMO it will be more confusing if some places use !L->getParentLoop() and other L->isOutermost(). Same for isInnerMost()/empty().

Loops form a hierarchical structure and personally I think the existing helpers make sense in that context. It is also consistent with similar data structures (for example, I don't think there are isLeaf/isRoot helpers for DominatorTree). I would prefer to keep the interface leaner (with the new docstring for empty the docs are quite explicit), but it is not something I feel too strongly about in this case if others feel the benefit outweighs the cost/churn. If they get added, I think the users should be updated, otherwise things get more confusing than they are now.

I partially agree but also IMHO empty() is confusing enough so that introducing isInnermost/Outermost has benefit that outweighs the cost. A Loop can contain both BBs and loops which is different than DominatorTree AFAIK (which can only contain BBs).
This is a big source of confusion when one comes across it in the code (and as I said, personally I assumed it had to do with the BBs).

Of course though, I don't have any kind of strong opinion. We can wait for other people's opinions.

Hm, adding multiple ways to check the same thing may lead to other problems. IMO it will be more confusing if some places use !L->getParentLoop() and other L->isOutermost().

There are often multiple ways for the same goal, for instance LoadInst::getPointerOperand() and LoadInst::getOperand(0). One makes the intention clearer than the other.

Same for isInnerMost()/empty().

Since these are identical, I'd tend to remove one. In these case I'd remove empty() since Loop does not represent a container.

llvm/include/llvm/Analysis/LoopInfo.h
159

isInnermost should be documented using a doc-string as well (or grouped together with empty() using /// @{ / /// @})

160

make this a doc-string as well?

baziotis marked an inline comment as done.Jul 8 2020, 1:42 AM

Hm, adding multiple ways to check the same thing may lead to other problems. IMO it will be more confusing if some places use !L->getParentLoop() and other L->isOutermost().

There are often multiple ways for the same goal, for instance LoadInst::getPointerOperand() and LoadInst::getOperand(0). One makes the intention clearer than the other.

Same for isInnerMost()/empty().

Since these are identical, I'd tend to remove one. In these case I'd remove empty() since Loop does not represent a container.

This the orthogonality vs expressiveness and I'm sure we all value each under certain circumstances. That said, I too agree that if we were to take
a step towards orthogonality, that would be to replace empty(), rather than not introducing isInnermost/Outermost.

llvm/include/llvm/Analysis/LoopInfo.h
160

I added it as non-doc comment intentionally but probably bad thought. I'll fix that.

@baziotis Are you going to update this diff?

@fhahn OK with renaming empty() to isInnermost()?

baziotis updated this revision to Diff 292968.Sep 19 2020, 8:23 AM
baziotis added a reviewer: fhahn.

@baziotis Are you going to update this diff?

Thanks, I had forgotten about this.

@fhahn OK with renaming empty() to isInnermost()?

I'd say that now we see all the places empty() was used, for most of them the name isInnermost() makes more sense.

fhahn accepted this revision.Sep 20 2020, 3:47 PM

@baziotis Are you going to update this diff?

Thanks, I had forgotten about this.

@fhahn OK with renaming empty() to isInnermost()?

I'd say that now we see all the places empty() was used, for most of them the name isInnermost() makes more sense.

Thanks for updating!

LGTM, although it would be good to also update the code to use isOutermost.

llvm/include/llvm/Analysis/LoopInfo.h
161

It would be good to frame the comment in terms of the returned value, e.g. Return true if the loop does not have a parent loop (= is the outermost loop).

This revision is now accepted and ready to land.Sep 20 2020, 3:47 PM
Meinersbur added inline comments.Sep 20 2020, 5:50 PM
llvm/include/llvm/Analysis/LoopInfo.h
158

Could you please add a remark about the following into the comments: LoopInfo does not detect irreducible control flow, just natural loops. That is, it is possible that there is cyclic control flow within the "innermost loop". LoopVectorize for instance explicitly checks for this, see collectSupportedLoops. There can also be be cyclic control-flow around the "outermost loop" (I think). IMHO this caveat is important to mention.

baziotis updated this revision to Diff 293532.Sep 22 2020, 11:21 AM
baziotis retitled this revision from [NFC][LoopInfo] Document empty() to [LoopInfo] empty() -> isInnermost(), add isOutermost().

Address comments

baziotis added inline comments.Sep 22 2020, 11:23 AM
llvm/include/llvm/Analysis/LoopInfo.h
158

If we wanted to appear on both function's doc, I think I'd have to add it twice. So I added it above both and I mention (natural) in each function.

Meinersbur accepted this revision.Sep 22 2020, 12:13 PM
This revision was automatically updated to reflect the committed changes.

API changes may cause problems to other backends. It is a good idea to test -DLLVM_TARGETS_TO_BUILD=ALL

API changes may cause problems to other backends. It is a good idea to test -DLLVM_TARGETS_TO_BUILD=ALL

True, I'm sorry. I tested all targets and it should be fine now. Thanks to you and @darkbuck for pushing the two fixes.