[PATCH] D84713: [DominatorTree] Simplify ChildrenGetter.

2020-08-21 Thread Alina Sbirlea via Phabricator via cfe-commits 
asbirlea added a comment.

Done in https://reviews.llvm.org/rG7ea0ee30588,


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D84713/new/

https://reviews.llvm.org/D84713

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D84713: [DominatorTree] Simplify ChildrenGetter.

2020-08-13 Thread Nikita Popov via Phabricator via cfe-commits 
nikic added a comment.

The regression here seems to be because operations on an empty GraphDiff don't 
optimize out. Not going through GraphDiff but using the same basic logic 
(https://github.com/llvm/llvm-project/commit/4c6a5de8131183ff88f52cc3dda67180e31501a1
 -- going through a separate method seems to be necessary for NRVO) we get back 
at least part of it: 
https://llvm-compile-time-tracker.com/compare.php?from=38537307e502c1ac9a09e6f75f9208db1327a0bf=4c6a5de8131183ff88f52cc3dda67180e31501a1=instructions


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D84713/new/

https://reviews.llvm.org/D84713

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D84713: [DominatorTree] Simplify ChildrenGetter.

2020-07-29 Thread Alina Sbirlea via Phabricator via cfe-commits 
asbirlea added a comment.

I'm looking into it.  If needed this can be reverted as it's not blocking the 
work for DomTree updates with a CFGView.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D84713/new/

https://reviews.llvm.org/D84713

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D84713: [DominatorTree] Simplify ChildrenGetter.

2020-07-29 Thread Nikita Popov via Phabricator via cfe-commits 
nikic added a comment.

This change had a significant negative compile-time impact: 
https://llvm-compile-time-tracker.com/compare.php?from=0b161def6cacff1a63d3cf1a1efe95b550814d7a=e22de4e46d1dd1aacc3a7060d24bcbe89908ba6c=instructions


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D84713/new/

https://reviews.llvm.org/D84713

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D84713: [DominatorTree] Simplify ChildrenGetter.

2020-07-28 Thread Alina Sbirlea via Phabricator via cfe-commits 
This revision was landed with ongoing or failed builds.
This revision was automatically updated to reflect the committed changes.
Closed by commit rGe22de4e46d1d: [DominatorTree] Simplify ChildrenGetter. 
(authored by asbirlea).

Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D84713/new/

https://reviews.llvm.org/D84713

Files:
  clang/include/clang/Analysis/Analyses/Dominators.h
  llvm/include/llvm/Support/GenericDomTreeConstruction.h

Index: llvm/include/llvm/Support/GenericDomTreeConstruction.h
===
--- llvm/include/llvm/Support/GenericDomTreeConstruction.h
+++ llvm/include/llvm/Support/GenericDomTreeConstruction.h
@@ -103,31 +103,13 @@
 // in progress, we need this information to continue it.
   }
 
-  template  struct ChildrenGetter {
-using ResultTy = SmallVector;
-
-static ResultTy Get(NodePtr N, std::integral_constant) {
-  auto RChildren = reverse(children(N));
-  return ResultTy(RChildren.begin(), RChildren.end());
-}
-
-static ResultTy Get(NodePtr N, std::integral_constant) {
-  auto IChildren = inverse_children(N);
-  return ResultTy(IChildren.begin(), IChildren.end());
-}
-
-using Tag = std::integral_constant;
-
-// The function below is the core part of the batch updater. It allows the
-// Depth Based Search algorithm to perform incremental updates in lockstep
-// with updates to the CFG. We emulated lockstep CFG updates by getting its
-// next snapshots by reverse-applying future updates.
-static ResultTy Get(NodePtr N, BatchUpdatePtr BUI) {
-  if (!BUI)
-return Get(N, Tag());
+  template 
+  static SmallVector getChildren(NodePtr N, BatchUpdatePtr BUI) {
+if (BUI)
   return BUI->PreViewCFG.template getChildren(N);
-}
-  };
+GraphDiffT GD;
+return GD.template getChildren(N);
+  }
 
   NodePtr getIDom(NodePtr BB) const {
 auto InfoIt = NodeToInfo.find(BB);
@@ -194,8 +176,7 @@
   NumToNode.push_back(BB);
 
   constexpr bool Direction = IsReverse != IsPostDom;  // XOR.
-  for (const NodePtr Succ :
-   ChildrenGetter::Get(BB, BatchUpdates)) {
+  for (const NodePtr Succ : getChildren(BB, BatchUpdates)) {
 const auto SIT = NodeToInfo.find(Succ);
 // Don't visit nodes more than once but remember to collect
 // ReverseChildren.
@@ -330,7 +311,7 @@
   // to CFG nodes within infinite loops.
   static bool HasForwardSuccessors(const NodePtr N, BatchUpdatePtr BUI) {
 assert(N && "N must be a valid node");
-return !ChildrenGetter::Get(N, BUI).empty();
+return !getChildren(N, BUI).empty();
   }
 
   static NodePtr GetEntryNode(const DomTreeT ) {
@@ -748,8 +729,7 @@
 //
 // Invariant: there is an optimal path from `To` to TN with the minimum
 // depth being CurrentLevel.
-for (const NodePtr Succ :
- ChildrenGetter::Get(TN->getBlock(), BUI)) {
+for (const NodePtr Succ : getChildren(TN->getBlock(), BUI)) {
   const TreeNodePtr SuccTN = DT.getNode(Succ);
   assert(SuccTN &&
  "Unreachable successor found at reachable insertion");
@@ -879,7 +859,7 @@
 // the DomTree about it.
 // The check is O(N), so run it only in debug configuration.
 auto IsSuccessor = [BUI](const NodePtr SuccCandidate, const NodePtr Of) {
-  auto Successors = ChildrenGetter::Get(Of, BUI);
+  auto Successors = getChildren(Of, BUI);
   return llvm::find(Successors, SuccCandidate) != Successors.end();
 };
 (void)IsSuccessor;
@@ -967,7 +947,7 @@
 LLVM_DEBUG(dbgs() << "IsReachableFromIDom " << BlockNamePrinter(TN)
   << "\n");
 auto TNB = TN->getBlock();
-for (const NodePtr Pred : ChildrenGetter::Get(TNB, BUI)) {
+for (const NodePtr Pred : getChildren(TNB, BUI)) {
   LLVM_DEBUG(dbgs() << "\tPred " << BlockNamePrinter(Pred) << "\n");
   if (!DT.getNode(Pred)) continue;
 
Index: clang/include/clang/Analysis/Analyses/Dominators.h
===
--- clang/include/clang/Analysis/Analyses/Dominators.h
+++ clang/include/clang/Analysis/Analyses/Dominators.h
@@ -273,76 +273,6 @@
 
 namespace llvm {
 
-/// Clang's CFG contains nullpointers for unreachable succesors, e.g. when an
-/// if statement's condition is always false, it's 'then' branch is represented
-/// with a nullptr. This however will result in a nullpointer derefernece for
-/// dominator tree calculation.
-///
-/// To circumvent this, let's just crudely specialize the children getters
-/// used in LLVM's dominator tree builder.
-namespace DomTreeBuilder {
-
-using ClangCFGDomChildrenGetter =
-SemiNCAInfo::ChildrenGetter<
- /*Inverse=*/false>;
-
-template <>
-template <>
-inline ClangCFGDomChildrenGetter::ResultTy ClangCFGDomChildrenGetter::Get(
-

[PATCH] D84713: [DominatorTree] Simplify ChildrenGetter.

2020-07-28 Thread Alina Sbirlea via Phabricator via cfe-commits 
asbirlea updated this revision to Diff 281382.
asbirlea added a comment.

Renamed ChildrenGet to getChildren. The same name only exists in GraphDiff, 
it's ok to keep a consistent naming.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D84713/new/

https://reviews.llvm.org/D84713

Files:
  clang/include/clang/Analysis/Analyses/Dominators.h
  llvm/include/llvm/Support/GenericDomTreeConstruction.h

Index: llvm/include/llvm/Support/GenericDomTreeConstruction.h
===
--- llvm/include/llvm/Support/GenericDomTreeConstruction.h
+++ llvm/include/llvm/Support/GenericDomTreeConstruction.h
@@ -103,31 +103,13 @@
 // in progress, we need this information to continue it.
   }
 
-  template  struct ChildrenGetter {
-using ResultTy = SmallVector;
-
-static ResultTy Get(NodePtr N, std::integral_constant) {
-  auto RChildren = reverse(children(N));
-  return ResultTy(RChildren.begin(), RChildren.end());
-}
-
-static ResultTy Get(NodePtr N, std::integral_constant) {
-  auto IChildren = inverse_children(N);
-  return ResultTy(IChildren.begin(), IChildren.end());
-}
-
-using Tag = std::integral_constant;
-
-// The function below is the core part of the batch updater. It allows the
-// Depth Based Search algorithm to perform incremental updates in lockstep
-// with updates to the CFG. We emulated lockstep CFG updates by getting its
-// next snapshots by reverse-applying future updates.
-static ResultTy Get(NodePtr N, BatchUpdatePtr BUI) {
-  if (!BUI)
-return Get(N, Tag());
+  template 
+  static SmallVector getChildren(NodePtr N, BatchUpdatePtr BUI) {
+if (BUI)
   return BUI->PreViewCFG.template getChildren(N);
-}
-  };
+GraphDiffT GD;
+return GD.template getChildren(N);
+  }
 
   NodePtr getIDom(NodePtr BB) const {
 auto InfoIt = NodeToInfo.find(BB);
@@ -194,8 +176,7 @@
   NumToNode.push_back(BB);
 
   constexpr bool Direction = IsReverse != IsPostDom;  // XOR.
-  for (const NodePtr Succ :
-   ChildrenGetter::Get(BB, BatchUpdates)) {
+  for (const NodePtr Succ : getChildren(BB, BatchUpdates)) {
 const auto SIT = NodeToInfo.find(Succ);
 // Don't visit nodes more than once but remember to collect
 // ReverseChildren.
@@ -330,7 +311,7 @@
   // to CFG nodes within infinite loops.
   static bool HasForwardSuccessors(const NodePtr N, BatchUpdatePtr BUI) {
 assert(N && "N must be a valid node");
-return !ChildrenGetter::Get(N, BUI).empty();
+return !getChildren(N, BUI).empty();
   }
 
   static NodePtr GetEntryNode(const DomTreeT ) {
@@ -748,8 +729,7 @@
 //
 // Invariant: there is an optimal path from `To` to TN with the minimum
 // depth being CurrentLevel.
-for (const NodePtr Succ :
- ChildrenGetter::Get(TN->getBlock(), BUI)) {
+for (const NodePtr Succ : getChildren(TN->getBlock(), BUI)) {
   const TreeNodePtr SuccTN = DT.getNode(Succ);
   assert(SuccTN &&
  "Unreachable successor found at reachable insertion");
@@ -879,7 +859,7 @@
 // the DomTree about it.
 // The check is O(N), so run it only in debug configuration.
 auto IsSuccessor = [BUI](const NodePtr SuccCandidate, const NodePtr Of) {
-  auto Successors = ChildrenGetter::Get(Of, BUI);
+  auto Successors = getChildren(Of, BUI);
   return llvm::find(Successors, SuccCandidate) != Successors.end();
 };
 (void)IsSuccessor;
@@ -967,7 +947,7 @@
 LLVM_DEBUG(dbgs() << "IsReachableFromIDom " << BlockNamePrinter(TN)
   << "\n");
 auto TNB = TN->getBlock();
-for (const NodePtr Pred : ChildrenGetter::Get(TNB, BUI)) {
+for (const NodePtr Pred : getChildren(TNB, BUI)) {
   LLVM_DEBUG(dbgs() << "\tPred " << BlockNamePrinter(Pred) << "\n");
   if (!DT.getNode(Pred)) continue;
 
Index: clang/include/clang/Analysis/Analyses/Dominators.h
===
--- clang/include/clang/Analysis/Analyses/Dominators.h
+++ clang/include/clang/Analysis/Analyses/Dominators.h
@@ -273,76 +273,6 @@
 
 namespace llvm {
 
-/// Clang's CFG contains nullpointers for unreachable succesors, e.g. when an
-/// if statement's condition is always false, it's 'then' branch is represented
-/// with a nullptr. This however will result in a nullpointer derefernece for
-/// dominator tree calculation.
-///
-/// To circumvent this, let's just crudely specialize the children getters
-/// used in LLVM's dominator tree builder.
-namespace DomTreeBuilder {
-
-using ClangCFGDomChildrenGetter =
-SemiNCAInfo::ChildrenGetter<
- /*Inverse=*/false>;
-
-template <>
-template <>
-inline ClangCFGDomChildrenGetter::ResultTy ClangCFGDomChildrenGetter::Get(
-clang::CFGBlock *N, std::integral_constant) {
-

[PATCH] D84713: [DominatorTree] Simplify ChildrenGetter.

2020-07-27 Thread David Blaikie via Phabricator via cfe-commits 
dblaikie added a comment.

In D84713#2177408 , @kuhar wrote:

> LGTM.
>
> One tiny nit: the function name `ChildrenGet` sounds kind of backwards to me, 
> but it seems like the other direction is already taken.


If there are both "ChildrenGet" and "GetChildren" in the same scope, seems like 
we probably should address that rather than having one awkwardly named & the 
ensuing lack of clarity.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D84713/new/

https://reviews.llvm.org/D84713



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D84713: [DominatorTree] Simplify ChildrenGetter.

2020-07-27 Thread Jakub Kuderski via Phabricator via cfe-commits 
kuhar accepted this revision.
kuhar added a comment.
This revision is now accepted and ready to land.

LGTM.

One tiny nit: the function name `ChildrenGet` sounds kind of backwards to me, 
but it seems like the other direction is already taken.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D84713/new/

https://reviews.llvm.org/D84713



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D84713: [DominatorTree] Simplify ChildrenGetter.

2020-07-27 Thread Alina Sbirlea via Phabricator via cfe-commits 
asbirlea created this revision.
asbirlea added reviewers: kuhar, dblaikie.
Herald added projects: clang, LLVM.
Herald added a subscriber: cfe-commits.

Simplify ChildrenGetter to a simple wrapper around a GraphDiff call.
GraphDiff already handles nullptr in children, so the special casing in
clang can also be removed.


Repository:
  rG LLVM Github Monorepo

https://reviews.llvm.org/D84713

Files:
  clang/include/clang/Analysis/Analyses/Dominators.h
  llvm/include/llvm/Support/GenericDomTreeConstruction.h

Index: llvm/include/llvm/Support/GenericDomTreeConstruction.h
===
--- llvm/include/llvm/Support/GenericDomTreeConstruction.h
+++ llvm/include/llvm/Support/GenericDomTreeConstruction.h
@@ -103,31 +103,13 @@
 // in progress, we need this information to continue it.
   }
 
-  template  struct ChildrenGetter {
-using ResultTy = SmallVector;
-
-static ResultTy Get(NodePtr N, std::integral_constant) {
-  auto RChildren = reverse(children(N));
-  return ResultTy(RChildren.begin(), RChildren.end());
-}
-
-static ResultTy Get(NodePtr N, std::integral_constant) {
-  auto IChildren = inverse_children(N);
-  return ResultTy(IChildren.begin(), IChildren.end());
-}
-
-using Tag = std::integral_constant;
-
-// The function below is the core part of the batch updater. It allows the
-// Depth Based Search algorithm to perform incremental updates in lockstep
-// with updates to the CFG. We emulated lockstep CFG updates by getting its
-// next snapshots by reverse-applying future updates.
-static ResultTy Get(NodePtr N, BatchUpdatePtr BUI) {
-  if (!BUI)
-return Get(N, Tag());
+  template 
+  static SmallVector ChildrenGet(NodePtr N, BatchUpdatePtr BUI) {
+if (BUI)
   return BUI->PreViewCFG.template getChildren(N);
-}
-  };
+GraphDiffT GD;
+return GD.template getChildren(N);
+  }
 
   NodePtr getIDom(NodePtr BB) const {
 auto InfoIt = NodeToInfo.find(BB);
@@ -194,8 +176,7 @@
   NumToNode.push_back(BB);
 
   constexpr bool Direction = IsReverse != IsPostDom;  // XOR.
-  for (const NodePtr Succ :
-   ChildrenGetter::Get(BB, BatchUpdates)) {
+  for (const NodePtr Succ : ChildrenGet(BB, BatchUpdates)) {
 const auto SIT = NodeToInfo.find(Succ);
 // Don't visit nodes more than once but remember to collect
 // ReverseChildren.
@@ -330,7 +311,7 @@
   // to CFG nodes within infinite loops.
   static bool HasForwardSuccessors(const NodePtr N, BatchUpdatePtr BUI) {
 assert(N && "N must be a valid node");
-return !ChildrenGetter::Get(N, BUI).empty();
+return !ChildrenGet(N, BUI).empty();
   }
 
   static NodePtr GetEntryNode(const DomTreeT ) {
@@ -748,8 +729,7 @@
 //
 // Invariant: there is an optimal path from `To` to TN with the minimum
 // depth being CurrentLevel.
-for (const NodePtr Succ :
- ChildrenGetter::Get(TN->getBlock(), BUI)) {
+for (const NodePtr Succ : ChildrenGet(TN->getBlock(), BUI)) {
   const TreeNodePtr SuccTN = DT.getNode(Succ);
   assert(SuccTN &&
  "Unreachable successor found at reachable insertion");
@@ -879,7 +859,7 @@
 // the DomTree about it.
 // The check is O(N), so run it only in debug configuration.
 auto IsSuccessor = [BUI](const NodePtr SuccCandidate, const NodePtr Of) {
-  auto Successors = ChildrenGetter::Get(Of, BUI);
+  auto Successors = ChildrenGet(Of, BUI);
   return llvm::find(Successors, SuccCandidate) != Successors.end();
 };
 (void)IsSuccessor;
@@ -967,7 +947,7 @@
 LLVM_DEBUG(dbgs() << "IsReachableFromIDom " << BlockNamePrinter(TN)
   << "\n");
 auto TNB = TN->getBlock();
-for (const NodePtr Pred : ChildrenGetter::Get(TNB, BUI)) {
+for (const NodePtr Pred : ChildrenGet(TNB, BUI)) {
   LLVM_DEBUG(dbgs() << "\tPred " << BlockNamePrinter(Pred) << "\n");
   if (!DT.getNode(Pred)) continue;
 
Index: clang/include/clang/Analysis/Analyses/Dominators.h
===
--- clang/include/clang/Analysis/Analyses/Dominators.h
+++ clang/include/clang/Analysis/Analyses/Dominators.h
@@ -273,76 +273,6 @@
 
 namespace llvm {
 
-/// Clang's CFG contains nullpointers for unreachable succesors, e.g. when an
-/// if statement's condition is always false, it's 'then' branch is represented
-/// with a nullptr. This however will result in a nullpointer derefernece for
-/// dominator tree calculation.
-///
-/// To circumvent this, let's just crudely specialize the children getters
-/// used in LLVM's dominator tree builder.
-namespace DomTreeBuilder {
-
-using ClangCFGDomChildrenGetter =
-SemiNCAInfo::ChildrenGetter<
- /*Inverse=*/false>;
-
-template <>
-template <>
-inline ClangCFGDomChildrenGetter::ResultTy