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

[baziotis]

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]

In D82895#2123465, @baziotis wrote:

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.

[baziotis]

In D82895#2123566, @fhahn wrote:

In D82895#2123465, @baziotis wrote:

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]

Address comment.

[jdoerfert]

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?

[etiotto]

In D82895#2129028, @jdoerfert wrote:

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.

[Whitney]

In D82895#2129028, @jdoerfert wrote:

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.

[baziotis]

Thanks for the reviews, I'm updating.

[baziotis]

Added isInnermost/Outermost.

[fhahn]

In D82895#2129028, @jdoerfert wrote:

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.

[baziotis]

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.

[Meinersbur]

In D82895#2130151, @fhahn wrote:

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

160

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

161

make this a doc-string as well?

[baziotis]

In D82895#2137834, @Meinersbur wrote:

In D82895#2130151, @fhahn wrote:

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

161

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

[Meinersbur]

@baziotis Are you going to update this diff?

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

[baziotis]

@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]

In D82895#2283534, @baziotis wrote:

@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

162

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).

[Meinersbur]

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]

Address comments

[baziotis]

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.

[MaskRay]

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

[baziotis]

In D82895#2288745, @MaskRay wrote:

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.

llvm/include/llvm/Analysis/LoopInfo.h

public:
   }
   typedef typename std::vector<LoopT *>::const_iterator iterator;
   typedef
       typename std::vector<LoopT *>::const_reverse_iterator reverse_iterator;
   iterator begin() const { return getSubLoops().begin(); }
   iterator end() const { return getSubLoops().end(); }
   reverse_iterator rbegin() const { return getSubLoops().rbegin(); }
   reverse_iterator rend() const { return getSubLoops().rend(); }
+  /// Return true if the loop does not contain any sub-loops.
   bool empty() const { return getSubLoops().empty(); }
+  bool isInnermost() const { return empty(); }
+  // Outermost is the same as top-level.
+  bool isOutermost() const { return getParentLoop() == nullptr; }
 
   /// Get a list of the basic blocks which make up this loop.
   ArrayRef<BlockT *> getBlocks() const {
     assert(!isInvalid() && "Loop not in a valid state!");
     return Blocks;
   }
   typedef typename ArrayRef<BlockT *>::const_iterator block_iterator;
   block_iterator block_begin() const { return getBlocks().begin(); }