This is an archive of the discontinued LLVM Phabricator instance.

[STLExtras] Add distance() for ranges, pred_size(), and succ_size()
ClosedPublic

Authored by vsk on May 9 2018, 5:29 PM.

Details

Summary

This commit adds a wrapper for std::distance() which works with ranges.
As it would be a common case to write distance(predecessors(BB)), this
also introduces pred_size() and succ_size() helpers to make that
easier to write.

Diff Detail

Event Timeline

vsk created this revision.May 9 2018, 5:29 PM

I sort of wonder if we should have a pred_size and succ_size helper.

lib/AsmParser/LLParser.cpp
6759–6760

Should this just be V->getNumUses()?

lib/Bitcode/Writer/ValueEnumerator.cpp
492

V->getNumUses()?

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp
1814

Def->getNumUses()

vsk added a comment.May 10 2018, 11:18 AM

I sort of wonder if we should have a pred_size and succ_size helper.

One motivation for this might be that meaning of distance(predecessors(b)) isn't obvious at first glance. Is that your concern?

If so, maybe it would be even simpler to name the new helper size. This would be more general than introducing pred_size/succ_size/etc, and might be easier to read overall. Wdyt?

I think if its equivalent to range-based version of std::distance its name should be llvm::distance.

My comment was just an observation that a majority of the uses were for predecessors/successors and maybe we should just make that easier. We already have pred_empty and succ_empty. pred_size and succ_size don't seem like much of a stretch.

vsk updated this revision to Diff 146214.May 10 2018, 1:31 PM
vsk marked 3 inline comments as done.
vsk retitled this revision from [STLExtras] Add a range-based distance() to [STLExtras] Add distance() for ranges, pred_size(), and succ_size().
vsk edited the summary of this revision. (Show Details)
  • Add {pred,succ}_size helpers and use getNumUses() as suggested.
bjope accepted this revision.May 10 2018, 3:18 PM

Nice, I was looking for something like this when updating MergedLoadStoreMotion.cpp.

LGTM! (assuming that @craig.topper is happy with the last update)

This revision is now accepted and ready to land.May 10 2018, 3:18 PM
This revision was automatically updated to reflect the committed changes.

I feel like a range-based version of std::distance isn't so much distance
anymore, by virtue of it being over a range & is actually probably more
suitably named 'size'. (in the case of std::distance, the name is really
talking about the two elements separately "what's the distance from this
iterator to this other iterator" not talking about a range defined by those
two iterators - so the name make sense there in a way that I don't think it
makes sense for ranges ("what is the distance of a range?" isn't a
cromulant question, I think... ))

I'd vote for llvm::size (& I think the general idea/concept/thing is a good
thing to add).

Though I guess one issue with size/distance is: how expensive is this? I'd
sort of be inclined only to provide this for ranges over random access
iterators (so it's only O(1), never O(N)), maybe? Let the more obscure
cases use std::distance(begin, end) to hopefully clarify that they're
weird/interesting/maybe expensive.