Page MenuHomePhabricator

[NFCI] Improve efficiency of isPotentiallyReachableFromManyDomTree.
Needs ReviewPublic

Authored by nicholas on Apr 16 2019, 12:48 AM.
This revision needs review, but there are no reviewers specified.

Details

Reviewers
None
Summary

df_iterator is intended for directed acyclic graphs, and as such keeps a list of visited nodes to not reenter. There is no need for that complexity when visiting a tree, such as DominatorTree. This reduces the amount of work done for each dominated node.

Diff Detail

Event Timeline

nicholas created this revision.Apr 16 2019, 12:48 AM
Herald added a project: Restricted Project. · View Herald TranscriptApr 16 2019, 12:48 AM
kuhar added a subscriber: kuhar.Apr 17 2019, 8:55 AM

IMO you could introduce df_iterator_tree_storage by a slight modification to the default one:

// df_iterator_storage - A private class which is used to figure out where to
// store the visited set.
template<class SetType, bool External>   // Non-external set
class df_iterator_storage {
public:
  SetType Visited;
};

Where your custom SetType does nothing on insertion and always returns that count is 0. Then you could potentially give it an alias like df_tree_iterator, or some better name.