[PATCH] D77341: [DomTree] Replace ChildrenGetter with GraphTraits over GraphDiff.

[Alina Sbirlea via Phabricator via cfe-commits]

This revision was automatically updated to reflect the committed changes.
Closed by commit rG8bf4c1f4fb25: Reapply [DomTree] Replace ChildrenGetter 
with GraphTraits over GraphDiff. (authored by asbirlea).

Changed prior to commit:
  https://reviews.llvm.org/D77341?vs=280326=280590#toc

Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D77341

Files:
  llvm/include/llvm/IR/Dominators.h
  llvm/include/llvm/Support/CFGDiff.h
  llvm/include/llvm/Support/GenericDomTree.h
  llvm/include/llvm/Support/GenericDomTreeConstruction.h
  llvm/lib/IR/Dominators.cpp

Index: llvm/lib/IR/Dominators.cpp
===
--- llvm/lib/IR/Dominators.cpp
+++ llvm/lib/IR/Dominators.cpp
@@ -90,9 +90,10 @@
 DomTreeBuilder::BBPostDomTree , BasicBlock *From, BasicBlock *To);
 
 template void llvm::DomTreeBuilder::ApplyUpdates(
-DomTreeBuilder::BBDomTree , DomTreeBuilder::BBUpdates);
+DomTreeBuilder::BBDomTree , DomTreeBuilder::BBDomTreeGraphDiff &);
 template void llvm::DomTreeBuilder::ApplyUpdates(
-DomTreeBuilder::BBPostDomTree , DomTreeBuilder::BBUpdates);
+DomTreeBuilder::BBPostDomTree ,
+DomTreeBuilder::BBPostDomTreeGraphDiff &);
 
 template bool llvm::DomTreeBuilder::Verify(
 const DomTreeBuilder::BBDomTree ,
Index: llvm/include/llvm/Support/GenericDomTreeConstruction.h
===
--- llvm/include/llvm/Support/GenericDomTreeConstruction.h
+++ llvm/include/llvm/Support/GenericDomTreeConstruction.h
@@ -58,6 +58,7 @@
   using TreeNodePtr = DomTreeNodeBase *;
   using RootsT = decltype(DomTreeT::Roots);
   static constexpr bool IsPostDom = DomTreeT::IsPostDominator;
+  using GraphDiffT = GraphDiff;
 
   // Information record used by Semi-NCA during tree construction.
   struct InfoRec {
@@ -77,28 +78,27 @@
   using UpdateT = typename DomTreeT::UpdateType;
   using UpdateKind = typename DomTreeT::UpdateKind;
   struct BatchUpdateInfo {
-SmallVector Updates;
-using NodePtrAndKind = PointerIntPair;
-
-// In order to be able to walk a CFG that is out of sync with the CFG
-// DominatorTree last knew about, use the list of updates to reconstruct
-// previous CFG versions of the current CFG. For each node, we store a set
-// of its virtually added/deleted future successors and predecessors.
-// Note that these children are from the future relative to what the
-// DominatorTree knows about -- using them to gets us some snapshot of the
-// CFG from the past (relative to the state of the CFG).
-DenseMap> FutureSuccessors;
-DenseMap> FuturePredecessors;
+// Note: Updates inside PreViewCFG are aleady legalized.
+BatchUpdateInfo(GraphDiffT )
+: PreViewCFG(PreViewCFG),
+  NumLegalized(PreViewCFG.getNumLegalizedUpdates()) {}
+
 // Remembers if the whole tree was recalculated at some point during the
 // current batch update.
 bool IsRecalculated = false;
+GraphDiffT 
+const size_t NumLegalized;
   };
 
   BatchUpdateInfo *BatchUpdates;
   using BatchUpdatePtr = BatchUpdateInfo *;
+  std::unique_ptr EmptyGD;
 
   // If BUI is a nullptr, then there's no batch update in progress.
-  SemiNCAInfo(BatchUpdatePtr BUI) : BatchUpdates(BUI) {}
+  SemiNCAInfo(BatchUpdatePtr BUI) : BatchUpdates(BUI) {
+if (!BatchUpdates)
+  EmptyGD = std::make_unique();
+  }
 
   void clear() {
 NumToNode = {nullptr}; // Restore to initial state with a dummy start node.
@@ -107,8 +107,7 @@
 // in progress, we need this information to continue it.
   }
 
-  template 
-  struct ChildrenGetter {
+  template  struct ChildrenGetter {
 using ResultTy = SmallVector;
 
 static ResultTy Get(NodePtr N, std::integral_constant) {
@@ -121,50 +120,16 @@
   return ResultTy(IChildren.begin(), IChildren.end());
 }
 
-using Tag = std::integral_constant;
+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) {
-  ResultTy Res = Get(N, Tag());
-  // If there's no batch update in progress, simply return node's children.
-  if (!BUI) return Res;
-
-  // CFG children are actually its *most current* children, and we have to
-  // reverse-apply the future updates to get the node's children at the
-  // point in time the update was performed.
-  auto  = (Inverse != IsPostDom) ? BUI->FuturePredecessors
-: BUI->FutureSuccessors;
-  auto FCIt = FutureChildren.find(N);
-  if (FCIt == FutureChildren.end()) return Res;
-
-  for (auto 

[PATCH] D77341: [DomTree] Replace ChildrenGetter with GraphTraits over GraphDiff.

[Alina Sbirlea via Phabricator via cfe-commits]

asbirlea added a comment.

Great, thank you for confirming :-)


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D77341



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

[PATCH] D77341: [DomTree] Replace ChildrenGetter with GraphTraits over GraphDiff.

[Nikita Popov via Phabricator via cfe-commits]

nikic added a comment.

Numbers for the newest version: 
https://llvm-compile-time-tracker.com/compare.php?from=183342c0a9850e60dd7a004b651c83dfb3a7d25e=eabcf534fe8760d14c95b40f07c61450c819d643=instructions

This is now a geomean 0.2% regressions, and I don't see any large outliers for 
individual files either (everything is below 2%). So this should be fine now, 
at least where compile-time impact is concerned :)


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D77341



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

[PATCH] D77341: [DomTree] Replace ChildrenGetter with GraphTraits over GraphDiff.

[Alina Sbirlea via Phabricator via cfe-commits]

asbirlea added a comment.

Yes. The difference in perf in instructions and cycles count is due to 
reversing the update order.
I'm still not seeing meaningful changes in wall-time even with the update order 
reversed, but reliable wall-time testing is hard.

I do have changes that

- drop the GraphTraits usage entirely in favor of the getChildren() method in 
GraphDiff
- refactor the hashmaps in GraphDiff

but I plan to send those separately.


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D77341



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

[PATCH] D77341: [DomTree] Replace ChildrenGetter with GraphTraits over GraphDiff.

[David Blaikie via Phabricator via cfe-commits]

dblaikie added a comment.

In D77341#2171305 , @asbirlea wrote:

> The increase in number of instructions and cycles was caused by reversing the 
> order in which the updates are applied by GraphDiff.
>  I'll look into re-adding some of the original cleanups in a follow-up patch.


Fascinating - and you were able to reproduce this by just reversing the order 
in the old code (using ChildrenGetter/building a vector and returning it - not 
using all the iterator adapters, etc) and that the performance problem was no 
longer present in the new code if you changed its order to match?

Huh. (again, sorry this has been such a slog :/)


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D77341



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

[PATCH] D77341: [DomTree] Replace ChildrenGetter with GraphTraits over GraphDiff.

[Alina Sbirlea via Phabricator via cfe-commits]

asbirlea updated this revision to Diff 280326.
asbirlea added a comment.

The increase in number of instructions and cycles was caused by reversing the 
order in which the updates are applied by GraphDiff.
I'll look into re-adding some of the original cleanups in a follow-up patch.


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D77341

Files:
  llvm/include/llvm/IR/Dominators.h
  llvm/include/llvm/Support/CFGDiff.h
  llvm/include/llvm/Support/GenericDomTree.h
  llvm/include/llvm/Support/GenericDomTreeConstruction.h
  llvm/lib/IR/Dominators.cpp

Index: llvm/lib/IR/Dominators.cpp
===
--- llvm/lib/IR/Dominators.cpp
+++ llvm/lib/IR/Dominators.cpp
@@ -90,9 +90,10 @@
 DomTreeBuilder::BBPostDomTree , BasicBlock *From, BasicBlock *To);
 
 template void llvm::DomTreeBuilder::ApplyUpdates(
-DomTreeBuilder::BBDomTree , DomTreeBuilder::BBUpdates);
+DomTreeBuilder::BBDomTree , DomTreeBuilder::BBDomTreeGraphDiff &);
 template void llvm::DomTreeBuilder::ApplyUpdates(
-DomTreeBuilder::BBPostDomTree , DomTreeBuilder::BBUpdates);
+DomTreeBuilder::BBPostDomTree ,
+DomTreeBuilder::BBPostDomTreeGraphDiff &);
 
 template bool llvm::DomTreeBuilder::Verify(
 const DomTreeBuilder::BBDomTree ,
Index: llvm/include/llvm/Support/GenericDomTreeConstruction.h
===
--- llvm/include/llvm/Support/GenericDomTreeConstruction.h
+++ llvm/include/llvm/Support/GenericDomTreeConstruction.h
@@ -58,6 +58,7 @@
   using TreeNodePtr = DomTreeNodeBase *;
   using RootsT = decltype(DomTreeT::Roots);
   static constexpr bool IsPostDom = DomTreeT::IsPostDominator;
+  using GraphDiffT = GraphDiff;
 
   // Information record used by Semi-NCA during tree construction.
   struct InfoRec {
@@ -77,28 +78,27 @@
   using UpdateT = typename DomTreeT::UpdateType;
   using UpdateKind = typename DomTreeT::UpdateKind;
   struct BatchUpdateInfo {
-SmallVector Updates;
-using NodePtrAndKind = PointerIntPair;
-
-// In order to be able to walk a CFG that is out of sync with the CFG
-// DominatorTree last knew about, use the list of updates to reconstruct
-// previous CFG versions of the current CFG. For each node, we store a set
-// of its virtually added/deleted future successors and predecessors.
-// Note that these children are from the future relative to what the
-// DominatorTree knows about -- using them to gets us some snapshot of the
-// CFG from the past (relative to the state of the CFG).
-DenseMap> FutureSuccessors;
-DenseMap> FuturePredecessors;
+// Note: Updates inside PreViewCFG are aleady legalized.
+BatchUpdateInfo(GraphDiffT )
+: PreViewCFG(PreViewCFG),
+  NumLegalized(PreViewCFG.getNumLegalizedUpdates()) {}
+
 // Remembers if the whole tree was recalculated at some point during the
 // current batch update.
 bool IsRecalculated = false;
+GraphDiffT 
+const size_t NumLegalized;
   };
 
   BatchUpdateInfo *BatchUpdates;
   using BatchUpdatePtr = BatchUpdateInfo *;
+  std::unique_ptr EmptyGD;
 
   // If BUI is a nullptr, then there's no batch update in progress.
-  SemiNCAInfo(BatchUpdatePtr BUI) : BatchUpdates(BUI) {}
+  SemiNCAInfo(BatchUpdatePtr BUI) : BatchUpdates(BUI) {
+if (!BatchUpdates)
+  EmptyGD = std::make_unique();
+  }
 
   void clear() {
 NumToNode = {nullptr}; // Restore to initial state with a dummy start node.
@@ -107,8 +107,7 @@
 // in progress, we need this information to continue it.
   }
 
-  template 
-  struct ChildrenGetter {
+  template  struct ChildrenGetter {
 using ResultTy = SmallVector;
 
 static ResultTy Get(NodePtr N, std::integral_constant) {
@@ -121,50 +120,16 @@
   return ResultTy(IChildren.begin(), IChildren.end());
 }
 
-using Tag = std::integral_constant;
+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) {
-  ResultTy Res = Get(N, Tag());
-  // If there's no batch update in progress, simply return node's children.
-  if (!BUI) return Res;
-
-  // CFG children are actually its *most current* children, and we have to
-  // reverse-apply the future updates to get the node's children at the
-  // point in time the update was performed.
-  auto  = (Inverse != IsPostDom) ? BUI->FuturePredecessors
-: BUI->FutureSuccessors;
-  auto FCIt = FutureChildren.find(N);
-  if (FCIt == FutureChildren.end()) return Res;
-
-  for (auto ChildAndKind 

[PATCH] D77341: [DomTree] Replace ChildrenGetter with GraphTraits over GraphDiff.

[Nikita Popov via Phabricator via cfe-commits]

nikic added a comment.

In D77341#2144974 , @asbirlea wrote:

> Thank you for the testing. Could you help with with instructions on how to 
> run the tracker myself?
>  My local testing showed a negligible regression for mafft and a negligible 
> improvement on other benchmarks, so it looked like noise on average.


The tracker just compiles test-suite under `perf stat` using the cached cmake 
configs. If I pick out the file with the largest regression (mafft 
`constants.c` in `ReleaseThinLTO` config with 18% regression) I can reproduce 
this locally as follows:

  perf stat /home/nikic/llvm-project/build/bin/clang -DNDEBUG  -O3 
-fomit-frame-pointer -flto=thin -DNDEBUG   -w -Werror=date-time -DLLVM -MD -MT 
MultiSource/Benchmarks/mafft/CMakeFiles/pairlocalalign.dir/constants.c.o -MF 
MultiSource/Benchmarks/mafft/CMakeFiles/pairlocalalign.dir/constants.c.o.d -o 
MultiSource/Benchmarks/mafft/CMakeFiles/pairlocalalign.dir/constants.c.o   -c 
../MultiSource/Benchmarks/mafft/constants.c

This gives me 3.5M instructions before and 4.2M instructions after. Those 
particular numbers are for an assertion-enabled build (the numbers on the 
website are without assertions.)


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D77341



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

[PATCH] D77341: [DomTree] Replace ChildrenGetter with GraphTraits over GraphDiff.

[Alina Sbirlea via Phabricator via cfe-commits]

asbirlea added a comment.

Thank you for the testing. Could you help with with instructions on how to run 
the tracker myself?
My local testing showed a negligible regression for mafft and a negligible 
improvement on other benchmarks, so it looked like noise on average.


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D77341



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

[PATCH] D77341: [DomTree] Replace ChildrenGetter with GraphTraits over GraphDiff.

[Nikita Popov via Phabricator via cfe-commits]

nikic added a comment.

Numbers for the new patch: 
https://llvm-compile-time-tracker.com/compare.php?from=c0308fd154f9a945608bd42630dc81dce5edfb40=e6e3534e77961cfa65d36828de5c75f36a25d009=instructions

The regression is definitely smaller now, but still fairly large. E.g. > 2% on 
mafft.


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D77341



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

[PATCH] D77341: [DomTree] Replace ChildrenGetter with GraphTraits over GraphDiff.

[Alina Sbirlea via Phabricator via cfe-commits]

asbirlea updated this revision to Diff 276891.
asbirlea added a comment.

Nit: re-add `const`s


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D77341

Files:
  llvm/include/llvm/IR/Dominators.h
  llvm/include/llvm/Support/CFGDiff.h
  llvm/include/llvm/Support/GenericDomTree.h
  llvm/include/llvm/Support/GenericDomTreeConstruction.h
  llvm/lib/IR/Dominators.cpp

Index: llvm/lib/IR/Dominators.cpp
===
--- llvm/lib/IR/Dominators.cpp
+++ llvm/lib/IR/Dominators.cpp
@@ -90,9 +90,10 @@
 DomTreeBuilder::BBPostDomTree , BasicBlock *From, BasicBlock *To);
 
 template void llvm::DomTreeBuilder::ApplyUpdates(
-DomTreeBuilder::BBDomTree , DomTreeBuilder::BBUpdates);
+DomTreeBuilder::BBDomTree , DomTreeBuilder::BBDomTreeGraphDiff &);
 template void llvm::DomTreeBuilder::ApplyUpdates(
-DomTreeBuilder::BBPostDomTree , DomTreeBuilder::BBUpdates);
+DomTreeBuilder::BBPostDomTree ,
+DomTreeBuilder::BBPostDomTreeGraphDiff &);
 
 template bool llvm::DomTreeBuilder::Verify(
 const DomTreeBuilder::BBDomTree ,
Index: llvm/include/llvm/Support/GenericDomTreeConstruction.h
===
--- llvm/include/llvm/Support/GenericDomTreeConstruction.h
+++ llvm/include/llvm/Support/GenericDomTreeConstruction.h
@@ -58,6 +58,7 @@
   using TreeNodePtr = DomTreeNodeBase *;
   using RootsT = decltype(DomTreeT::Roots);
   static constexpr bool IsPostDom = DomTreeT::IsPostDominator;
+  using GraphDiffT = GraphDiff;
 
   // Information record used by Semi-NCA during tree construction.
   struct InfoRec {
@@ -77,28 +78,27 @@
   using UpdateT = typename DomTreeT::UpdateType;
   using UpdateKind = typename DomTreeT::UpdateKind;
   struct BatchUpdateInfo {
-SmallVector Updates;
-using NodePtrAndKind = PointerIntPair;
-
-// In order to be able to walk a CFG that is out of sync with the CFG
-// DominatorTree last knew about, use the list of updates to reconstruct
-// previous CFG versions of the current CFG. For each node, we store a set
-// of its virtually added/deleted future successors and predecessors.
-// Note that these children are from the future relative to what the
-// DominatorTree knows about -- using them to gets us some snapshot of the
-// CFG from the past (relative to the state of the CFG).
-DenseMap> FutureSuccessors;
-DenseMap> FuturePredecessors;
+// Note: Updates inside PreViewCFG are aleady legalized.
+BatchUpdateInfo(GraphDiffT )
+: PreViewCFG(PreViewCFG),
+  NumLegalized(PreViewCFG.getNumLegalizedUpdates()) {}
+
 // Remembers if the whole tree was recalculated at some point during the
 // current batch update.
 bool IsRecalculated = false;
+GraphDiffT 
+const size_t NumLegalized;
   };
 
   BatchUpdateInfo *BatchUpdates;
   using BatchUpdatePtr = BatchUpdateInfo *;
+  std::unique_ptr EmptyGD;
 
   // If BUI is a nullptr, then there's no batch update in progress.
-  SemiNCAInfo(BatchUpdatePtr BUI) : BatchUpdates(BUI) {}
+  SemiNCAInfo(BatchUpdatePtr BUI) : BatchUpdates(BUI) {
+if (!BatchUpdates)
+  EmptyGD = std::make_unique();
+  }
 
   void clear() {
 NumToNode = {nullptr}; // Restore to initial state with a dummy start node.
@@ -107,8 +107,7 @@
 // in progress, we need this information to continue it.
   }
 
-  template 
-  struct ChildrenGetter {
+  template  struct ChildrenGetter {
 using ResultTy = SmallVector;
 
 static ResultTy Get(NodePtr N, std::integral_constant) {
@@ -121,49 +120,23 @@
   return ResultTy(IChildren.begin(), IChildren.end());
 }
 
-using Tag = std::integral_constant;
+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) {
-  ResultTy Res = Get(N, Tag());
-  // If there's no batch update in progress, simply return node's children.
-  if (!BUI) return Res;
-
-  // CFG children are actually its *most current* children, and we have to
-  // reverse-apply the future updates to get the node's children at the
-  // point in time the update was performed.
-  auto  = (Inverse != IsPostDom) ? BUI->FuturePredecessors
-: BUI->FutureSuccessors;
-  auto FCIt = FutureChildren.find(N);
-  if (FCIt == FutureChildren.end()) return Res;
-
-  for (auto ChildAndKind : FCIt->second) {
-const NodePtr Child = ChildAndKind.getPointer();
-const UpdateKind UK = ChildAndKind.getInt();
-
-// Reverse-apply the future update.
-

[PATCH] D77341: [DomTree] Replace ChildrenGetter with GraphTraits over GraphDiff.

[Alina Sbirlea via Phabricator via cfe-commits]

asbirlea updated this revision to Diff 276890.
asbirlea added a comment.
This revision is now accepted and ready to land.

Updated to include the part of the patch that's moving the Updates to a CFGDiff 
object. Splitting off from the clean-up work merging the two branches when BUI 
is null.
This patch does not exhibit the compile-time regression which caused it to be 
reverted previously.


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D77341

Files:
  llvm/include/llvm/IR/Dominators.h
  llvm/include/llvm/Support/CFGDiff.h
  llvm/include/llvm/Support/GenericDomTree.h
  llvm/include/llvm/Support/GenericDomTreeConstruction.h
  llvm/lib/IR/Dominators.cpp

Index: llvm/lib/IR/Dominators.cpp
===
--- llvm/lib/IR/Dominators.cpp
+++ llvm/lib/IR/Dominators.cpp
@@ -90,9 +90,10 @@
 DomTreeBuilder::BBPostDomTree , BasicBlock *From, BasicBlock *To);
 
 template void llvm::DomTreeBuilder::ApplyUpdates(
-DomTreeBuilder::BBDomTree , DomTreeBuilder::BBUpdates);
+DomTreeBuilder::BBDomTree , DomTreeBuilder::BBDomTreeGraphDiff &);
 template void llvm::DomTreeBuilder::ApplyUpdates(
-DomTreeBuilder::BBPostDomTree , DomTreeBuilder::BBUpdates);
+DomTreeBuilder::BBPostDomTree ,
+DomTreeBuilder::BBPostDomTreeGraphDiff &);
 
 template bool llvm::DomTreeBuilder::Verify(
 const DomTreeBuilder::BBDomTree ,
Index: llvm/include/llvm/Support/GenericDomTreeConstruction.h
===
--- llvm/include/llvm/Support/GenericDomTreeConstruction.h
+++ llvm/include/llvm/Support/GenericDomTreeConstruction.h
@@ -58,6 +58,7 @@
   using TreeNodePtr = DomTreeNodeBase *;
   using RootsT = decltype(DomTreeT::Roots);
   static constexpr bool IsPostDom = DomTreeT::IsPostDominator;
+  using GraphDiffT = GraphDiff;
 
   // Information record used by Semi-NCA during tree construction.
   struct InfoRec {
@@ -77,28 +78,27 @@
   using UpdateT = typename DomTreeT::UpdateType;
   using UpdateKind = typename DomTreeT::UpdateKind;
   struct BatchUpdateInfo {
-SmallVector Updates;
-using NodePtrAndKind = PointerIntPair;
-
-// In order to be able to walk a CFG that is out of sync with the CFG
-// DominatorTree last knew about, use the list of updates to reconstruct
-// previous CFG versions of the current CFG. For each node, we store a set
-// of its virtually added/deleted future successors and predecessors.
-// Note that these children are from the future relative to what the
-// DominatorTree knows about -- using them to gets us some snapshot of the
-// CFG from the past (relative to the state of the CFG).
-DenseMap> FutureSuccessors;
-DenseMap> FuturePredecessors;
+// Note: Updates inside PreViewCFG are aleady legalized.
+BatchUpdateInfo(GraphDiffT )
+: PreViewCFG(PreViewCFG),
+  NumLegalized(PreViewCFG.getNumLegalizedUpdates()) {}
+
 // Remembers if the whole tree was recalculated at some point during the
 // current batch update.
 bool IsRecalculated = false;
+GraphDiffT 
+const size_t NumLegalized;
   };
 
   BatchUpdateInfo *BatchUpdates;
   using BatchUpdatePtr = BatchUpdateInfo *;
+  std::unique_ptr EmptyGD;
 
   // If BUI is a nullptr, then there's no batch update in progress.
-  SemiNCAInfo(BatchUpdatePtr BUI) : BatchUpdates(BUI) {}
+  SemiNCAInfo(BatchUpdatePtr BUI) : BatchUpdates(BUI) {
+if (!BatchUpdates)
+  EmptyGD = std::make_unique();
+  }
 
   void clear() {
 NumToNode = {nullptr}; // Restore to initial state with a dummy start node.
@@ -107,8 +107,7 @@
 // in progress, we need this information to continue it.
   }
 
-  template 
-  struct ChildrenGetter {
+  template  struct ChildrenGetter {
 using ResultTy = SmallVector;
 
 static ResultTy Get(NodePtr N, std::integral_constant) {
@@ -121,49 +120,23 @@
   return ResultTy(IChildren.begin(), IChildren.end());
 }
 
-using Tag = std::integral_constant;
+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) {
-  ResultTy Res = Get(N, Tag());
-  // If there's no batch update in progress, simply return node's children.
-  if (!BUI) return Res;
-
-  // CFG children are actually its *most current* children, and we have to
-  // reverse-apply the future updates to get the node's children at the
-  // point in time the update was performed.
-  auto  = (Inverse != IsPostDom) ? BUI->FuturePredecessors
-: BUI->FutureSuccessors;
-  auto FCIt 

[PATCH] D77341: [DomTree] Replace ChildrenGetter with GraphTraits over GraphDiff.

[Alina Sbirlea via Phabricator via cfe-commits]

asbirlea reopened this revision.
asbirlea added a comment.
This revision is now accepted and ready to land.
Herald added a project: LLVM.

I'm working to update this revision to address the compile-time regression.
Re-opening so I can rebase and add misc fixes and will mark as changes planned 
until I address the compile-time issue.


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D77341



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

[PATCH] D77341: [DomTree] Replace ChildrenGetter with GraphTraits over GraphDiff.

[Alina Sbirlea via Phabricator via cfe-commits]

asbirlea updated this revision to Diff 261404.
asbirlea added a comment.

Rebase.


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D77341

Files:
  clang/include/clang/Analysis/Analyses/Dominators.h
  llvm/include/llvm/IR/Dominators.h
  llvm/include/llvm/Support/CFGDiff.h
  llvm/include/llvm/Support/GenericDomTree.h
  llvm/include/llvm/Support/GenericDomTreeConstruction.h
  llvm/lib/IR/Dominators.cpp

Index: llvm/lib/IR/Dominators.cpp
===
--- llvm/lib/IR/Dominators.cpp
+++ llvm/lib/IR/Dominators.cpp
@@ -90,9 +90,10 @@
 DomTreeBuilder::BBPostDomTree , BasicBlock *From, BasicBlock *To);
 
 template void llvm::DomTreeBuilder::ApplyUpdates(
-DomTreeBuilder::BBDomTree , DomTreeBuilder::BBUpdates);
+DomTreeBuilder::BBDomTree , DomTreeBuilder::BBDomTreeGraphDiff &);
 template void llvm::DomTreeBuilder::ApplyUpdates(
-DomTreeBuilder::BBPostDomTree , DomTreeBuilder::BBUpdates);
+DomTreeBuilder::BBPostDomTree ,
+DomTreeBuilder::BBPostDomTreeGraphDiff &);
 
 template bool llvm::DomTreeBuilder::Verify(
 const DomTreeBuilder::BBDomTree ,
Index: llvm/include/llvm/Support/GenericDomTreeConstruction.h
===
--- llvm/include/llvm/Support/GenericDomTreeConstruction.h
+++ llvm/include/llvm/Support/GenericDomTreeConstruction.h
@@ -58,6 +58,13 @@
   using TreeNodePtr = DomTreeNodeBase *;
   using RootsT = decltype(DomTreeT::Roots);
   static constexpr bool IsPostDom = DomTreeT::IsPostDominator;
+  using GraphDiffT = GraphDiff;
+  using GraphDiffNodePair = std::pair;
+  using GraphDiffInvNodePair = std::pair>;
+  using GraphDiffNodePairIfDomT =
+  std::conditional_t;
+  using GraphDiffNodePairIfPDomT =
+  std::conditional_t;
 
   // Information record used by Semi-NCA during tree construction.
   struct InfoRec {
@@ -77,28 +84,27 @@
   using UpdateT = typename DomTreeT::UpdateType;
   using UpdateKind = typename DomTreeT::UpdateKind;
   struct BatchUpdateInfo {
-SmallVector Updates;
-using NodePtrAndKind = PointerIntPair;
-
-// In order to be able to walk a CFG that is out of sync with the CFG
-// DominatorTree last knew about, use the list of updates to reconstruct
-// previous CFG versions of the current CFG. For each node, we store a set
-// of its virtually added/deleted future successors and predecessors.
-// Note that these children are from the future relative to what the
-// DominatorTree knows about -- using them to gets us some snapshot of the
-// CFG from the past (relative to the state of the CFG).
-DenseMap> FutureSuccessors;
-DenseMap> FuturePredecessors;
+// Note: Updates inside PreViewCFG are aleady legalized.
+BatchUpdateInfo(GraphDiffT )
+: PreViewCFG(PreViewCFG),
+  NumLegalized(PreViewCFG.getNumLegalizedUpdates()) {}
+
 // Remembers if the whole tree was recalculated at some point during the
 // current batch update.
 bool IsRecalculated = false;
+GraphDiffT 
+const size_t NumLegalized;
   };
 
   BatchUpdateInfo *BatchUpdates;
   using BatchUpdatePtr = BatchUpdateInfo *;
+  std::unique_ptr EmptyGD;
 
   // If BUI is a nullptr, then there's no batch update in progress.
-  SemiNCAInfo(BatchUpdatePtr BUI) : BatchUpdates(BUI) {}
+  SemiNCAInfo(BatchUpdatePtr BUI) : BatchUpdates(BUI) {
+if (!BatchUpdates)
+  EmptyGD = std::make_unique();
+  }
 
   void clear() {
 NumToNode = {nullptr}; // Restore to initial state with a dummy start node.
@@ -107,67 +113,6 @@
 // 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) {
-  ResultTy Res = Get(N, Tag());
-  // If there's no batch update in progress, simply return node's children.
-  if (!BUI) return Res;
-
-  // CFG children are actually its *most current* children, and we have to
-  // reverse-apply the future updates to get the node's children at the
-  // point in time the update was performed.
-  auto  = (Inverse != IsPostDom) ? BUI->FuturePredecessors
-

[PATCH] D77341: [DomTree] Replace ChildrenGetter with GraphTraits over GraphDiff.

[Nikita Popov via Phabricator via cfe-commits]

nikic added a comment.

This change causes a 2.5% compile-time regression across the board, see 
http://llvm-compile-time-tracker.com/compare.php?from=37bcf2df01cfa47e4509a5d225a23e2ca95005e6=a90374988e4eb8c50d91e11f4e61cdbd5debb235=instructions.
 Can you please try to find a cheaper way to approach this issue?


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D77341



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

[PATCH] D77341: [DomTree] Replace ChildrenGetter with GraphTraits over GraphDiff.

[Mehdi AMINI via Phabricator via cfe-commits]

mehdi_amini added inline comments.



Comment at: llvm/include/llvm/Support/GenericDomTree.h:32
 #include "llvm/ADT/SmallVector.h"
+#include "llvm/IR/CFGDiff.h"
 #include "llvm/Support/CFGUpdate.h"

mehdi_amini wrote:
> dblaikie wrote:
> > mehdi_amini wrote:
> > > This looks like a layering violation to me here: I wouldn't expect a 
> > > generic utility in Support to introduce a dependency on IR.
> > > 
> > > I speculatively reverted in 
> > > https://github.com/llvm/llvm-project/commit/57d2d48399b63c0ef1dda490fdaf28efbb80c2c0
> > >  while we can figure it out.
> > Yep - agreed on the layering violation. Thanks for the catch/revert!
> > 
> > I /think/ CFGDiff.h is independent of IR & shouldn't include IR/CFG.h and 
> > then can move into Support. Ah, yeah, when I did 
> > 30804d0a3fb23325c4b455108e59d00213b83891 & related work, that's what made 
> > it independent of IR.
> > 
> > Moved it over to Support in a838aadae3f20b9644e2ad553d3d558a91fd8fd7
> Thanks! Re-landed in 0445c64998d14b81f0d3a3182011fc5eae47fa71
Actually reverted again as it breaks the MLIR build in a different way, I won't 
be able to look into this in more details right now.

(I ran `ninja check` but I forgot that `check` is not `check-all`...)


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D77341



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

[PATCH] D77341: [DomTree] Replace ChildrenGetter with GraphTraits over GraphDiff.

[Mehdi AMINI via Phabricator via cfe-commits]

mehdi_amini added inline comments.



Comment at: llvm/include/llvm/Support/GenericDomTree.h:32
 #include "llvm/ADT/SmallVector.h"
+#include "llvm/IR/CFGDiff.h"
 #include "llvm/Support/CFGUpdate.h"

dblaikie wrote:
> mehdi_amini wrote:
> > This looks like a layering violation to me here: I wouldn't expect a 
> > generic utility in Support to introduce a dependency on IR.
> > 
> > I speculatively reverted in 
> > https://github.com/llvm/llvm-project/commit/57d2d48399b63c0ef1dda490fdaf28efbb80c2c0
> >  while we can figure it out.
> Yep - agreed on the layering violation. Thanks for the catch/revert!
> 
> I /think/ CFGDiff.h is independent of IR & shouldn't include IR/CFG.h and 
> then can move into Support. Ah, yeah, when I did 
> 30804d0a3fb23325c4b455108e59d00213b83891 & related work, that's what made it 
> independent of IR.
> 
> Moved it over to Support in a838aadae3f20b9644e2ad553d3d558a91fd8fd7
Thanks! Re-landed in 0445c64998d14b81f0d3a3182011fc5eae47fa71


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D77341



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

[PATCH] D77341: [DomTree] Replace ChildrenGetter with GraphTraits over GraphDiff.

[David Blaikie via Phabricator via cfe-commits]

dblaikie added inline comments.



Comment at: llvm/include/llvm/Support/GenericDomTree.h:32
 #include "llvm/ADT/SmallVector.h"
+#include "llvm/IR/CFGDiff.h"
 #include "llvm/Support/CFGUpdate.h"

mehdi_amini wrote:
> This looks like a layering violation to me here: I wouldn't expect a generic 
> utility in Support to introduce a dependency on IR.
> 
> I speculatively reverted in 
> https://github.com/llvm/llvm-project/commit/57d2d48399b63c0ef1dda490fdaf28efbb80c2c0
>  while we can figure it out.
Yep - agreed on the layering violation. Thanks for the catch/revert!

I /think/ CFGDiff.h is independent of IR & shouldn't include IR/CFG.h and then 
can move into Support. Ah, yeah, when I did 
30804d0a3fb23325c4b455108e59d00213b83891 & related work, that's what made it 
independent of IR.

Moved it over to Support in a838aadae3f20b9644e2ad553d3d558a91fd8fd7


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D77341



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

[PATCH] D77341: [DomTree] Replace ChildrenGetter with GraphTraits over GraphDiff.

[Mehdi AMINI via Phabricator via cfe-commits]

mehdi_amini added inline comments.



Comment at: llvm/include/llvm/Support/GenericDomTree.h:32
 #include "llvm/ADT/SmallVector.h"
+#include "llvm/IR/CFGDiff.h"
 #include "llvm/Support/CFGUpdate.h"

This looks like a layering violation to me here: I wouldn't expect a generic 
utility in Support to introduce a dependency on IR.

I speculatively reverted in 
https://github.com/llvm/llvm-project/commit/57d2d48399b63c0ef1dda490fdaf28efbb80c2c0
 while we can figure it out.


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D77341



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

[PATCH] D77341: [DomTree] Replace ChildrenGetter with GraphTraits over GraphDiff.

[Mehdi AMINI via Phabricator via cfe-commits]

mehdi_amini added a comment.

In D77341#1973827 , @bondhugula wrote:

> @asbirlea This has broken the MLIR build. Could you please build with 
> `-DLLVM_ENABLE_PROJECTS=mlir`?


If you use arcanist, you get pre-merge testing on Phabricator :)


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D77341



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

[PATCH] D77341: [DomTree] Replace ChildrenGetter with GraphTraits over GraphDiff.

[Uday Bondhugula via Phabricator via cfe-commits]

bondhugula added a comment.

@asbirlea This has broken the MLIR build. Could you please build with 
`-DLLVM_ENABLE_PROJECTS=mlir`?

  FAILED: tools/mlir/lib/Analysis/CMakeFiles/MLIRAnalysis.dir/Dominance.cpp.o 
  /usr/lib64/ccache/clang++  -DGTEST_HAS_RTTI=0 
-DMLIR_CUDA_CONVERSIONS_ENABLED=1 -D_DEBUG -D_GNU_SOURCE 
-D__STDC_CONSTANT_MACROS -D__STDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS 
-Itools/mlir/lib/Analysis -I/home/uday/llvm-project/mlir/lib/Analysis 
-I/usr/include/libxml2 -Iinclude -I/home/uday/llvm-project/llvm/include 
-I/home/uday/llvm-project/mlir/include -Itools/mlir/include -fPIC 
-fvisibility-inlines-hidden -Werror=date-time 
-Werror=unguarded-availability-new -Wall -Wextra -Wno-unused-parameter 
-Wwrite-strings -Wcast-qual -Wmissing-field-initializers -pedantic 
-Wno-long-long -Wimplicit-fallthrough -Wcovered-switch-default 
-Wno-noexcept-type -Wnon-virtual-dtor -Wdelete-non-virtual-dtor 
-Wstring-conversion -fdiagnostics-color -ffunction-sections -fdata-sections -O2 
-fno-exceptions -fno-rtti -UNDEBUG -std=c++14 -MD -MT 
tools/mlir/lib/Analysis/CMakeFiles/MLIRAnalysis.dir/Dominance.cpp.o -MF 
tools/mlir/lib/Analysis/CMakeFiles/MLIRAnalysis.dir/Dominance.cpp.o.d -o 
tools/mlir/lib/Analysis/CMakeFiles/MLIRAnalysis.dir/Dominance.cpp.o -c 
/home/uday/llvm-project/mlir/lib/Analysis/Dominance.cpp
  In file included from 
/home/uday/llvm-project/mlir/lib/Analysis/Dominance.cpp:14:
  In file included from 
/home/uday/llvm-project/mlir/include/mlir/Analysis/Dominance.h:12:
  In file included from 
/home/uday/llvm-project/mlir/include/mlir/IR/RegionGraphTraits.h:18:
  In file included from 
/home/uday/llvm-project/mlir/include/mlir/IR/Region.h:16:
  In file included from /home/uday/llvm-project/mlir/include/mlir/IR/Block.h:16:
  In file included from 
/home/uday/llvm-project/mlir/include/mlir/IR/BlockSupport.h:16:
  In file included from /home/uday/llvm-project/mlir/include/mlir/IR/Value.h:16:
  In file included from /home/uday/llvm-project/mlir/include/mlir/IR/Types.h:12:
  In file included from 
/home/uday/llvm-project/mlir/include/mlir/IR/TypeSupport.h:17:
  In file included from 
/home/uday/llvm-project/mlir/include/mlir/IR/StorageUniquerSupport.h:17:
  In file included from 
/home/uday/llvm-project/mlir/include/mlir/Support/STLExtras.h:18:
  In file included from 
/home/uday/llvm-project/llvm/include/llvm/ADT/STLExtras.h:20:
  /home/uday/llvm-project/llvm/include/llvm/ADT/iterator.h:366:17: error: 
indirection requires pointer operand ('const mlir::PredecessorIterator' invalid)
  NR.second = *this->I;


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D77341



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

Re: [PATCH] D77341: [DomTree] Replace ChildrenGetter with GraphTraits over GraphDiff.

[Alina Sbirlea via cfe-commits]

I'm hoping rG5da1671bf823 fixes them. Please let me know if not and I will
revert.

Alina

On Thu, Apr 9, 2020 at 7:03 PM Stella Stamenova via Phabricator <
revi...@reviews.llvm.org> wrote:

> stella.stamenova added a comment.
>
> It looks like this broke the windows lldb buildbot:
>
> lab.llvm.org:8011/builders/lldb-x64-windows-ninja/builds/15542
>
> It already had a test failure, so you probably didn’t get the email.
>
>
> Repository:
>   rG LLVM Github Monorepo
>
> CHANGES SINCE LAST ACTION
>   https://reviews.llvm.org/D77341/new/
>
> https://reviews.llvm.org/D77341
>
>
>
>
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D77341: [DomTree] Replace ChildrenGetter with GraphTraits over GraphDiff.

[Stella Stamenova via Phabricator via cfe-commits]

stella.stamenova added a comment.

It looks like this broke the windows lldb buildbot:

lab.llvm.org:8011/builders/lldb-x64-windows-ninja/builds/15542

It already had a test failure, so you probably didn’t get the email.


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D77341



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

[PATCH] D77341: [DomTree] Replace ChildrenGetter with GraphTraits over GraphDiff.

[Alina Sbirlea via Phabricator via cfe-commits]

This revision was automatically updated to reflect the committed changes.
Closed by commit rGa90374988e4e: [DomTree] Replace ChildrenGetter with 
GraphTraits over GraphDiff. (authored by asbirlea).

Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D77341

Files:
  clang/include/clang/Analysis/Analyses/Dominators.h
  llvm/include/llvm/IR/CFGDiff.h
  llvm/include/llvm/IR/Dominators.h
  llvm/include/llvm/Support/GenericDomTree.h
  llvm/include/llvm/Support/GenericDomTreeConstruction.h
  llvm/lib/IR/Dominators.cpp

Index: llvm/lib/IR/Dominators.cpp
===
--- llvm/lib/IR/Dominators.cpp
+++ llvm/lib/IR/Dominators.cpp
@@ -90,9 +90,10 @@
 DomTreeBuilder::BBPostDomTree , BasicBlock *From, BasicBlock *To);
 
 template void llvm::DomTreeBuilder::ApplyUpdates(
-DomTreeBuilder::BBDomTree , DomTreeBuilder::BBUpdates);
+DomTreeBuilder::BBDomTree , DomTreeBuilder::BBDomTreeGraphDiff &);
 template void llvm::DomTreeBuilder::ApplyUpdates(
-DomTreeBuilder::BBPostDomTree , DomTreeBuilder::BBUpdates);
+DomTreeBuilder::BBPostDomTree ,
+DomTreeBuilder::BBPostDomTreeGraphDiff &);
 
 template bool llvm::DomTreeBuilder::Verify(
 const DomTreeBuilder::BBDomTree ,
Index: llvm/include/llvm/Support/GenericDomTreeConstruction.h
===
--- llvm/include/llvm/Support/GenericDomTreeConstruction.h
+++ llvm/include/llvm/Support/GenericDomTreeConstruction.h
@@ -58,6 +58,13 @@
   using TreeNodePtr = DomTreeNodeBase *;
   using RootsT = decltype(DomTreeT::Roots);
   static constexpr bool IsPostDom = DomTreeT::IsPostDominator;
+  using GraphDiffT = GraphDiff;
+  using GraphDiffNodePair = std::pair;
+  using GraphDiffInvNodePair = std::pair>;
+  using GraphDiffNodePairIfDomT =
+  std::conditional_t;
+  using GraphDiffNodePairIfPDomT =
+  std::conditional_t;
 
   // Information record used by Semi-NCA during tree construction.
   struct InfoRec {
@@ -77,28 +84,27 @@
   using UpdateT = typename DomTreeT::UpdateType;
   using UpdateKind = typename DomTreeT::UpdateKind;
   struct BatchUpdateInfo {
-SmallVector Updates;
-using NodePtrAndKind = PointerIntPair;
-
-// In order to be able to walk a CFG that is out of sync with the CFG
-// DominatorTree last knew about, use the list of updates to reconstruct
-// previous CFG versions of the current CFG. For each node, we store a set
-// of its virtually added/deleted future successors and predecessors.
-// Note that these children are from the future relative to what the
-// DominatorTree knows about -- using them to gets us some snapshot of the
-// CFG from the past (relative to the state of the CFG).
-DenseMap> FutureSuccessors;
-DenseMap> FuturePredecessors;
+// Note: Updates inside PreViewCFG are aleady legalized.
+BatchUpdateInfo(GraphDiffT )
+: PreViewCFG(PreViewCFG),
+  NumLegalized(PreViewCFG.getNumLegalizedUpdates()) {}
+
 // Remembers if the whole tree was recalculated at some point during the
 // current batch update.
 bool IsRecalculated = false;
+GraphDiffT 
+const size_t NumLegalized;
   };
 
   BatchUpdateInfo *BatchUpdates;
   using BatchUpdatePtr = BatchUpdateInfo *;
+  std::unique_ptr EmptyGD;
 
   // If BUI is a nullptr, then there's no batch update in progress.
-  SemiNCAInfo(BatchUpdatePtr BUI) : BatchUpdates(BUI) {}
+  SemiNCAInfo(BatchUpdatePtr BUI) : BatchUpdates(BUI) {
+if (!BatchUpdates)
+  EmptyGD = std::make_unique();
+  }
 
   void clear() {
 NumToNode = {nullptr}; // Restore to initial state with a dummy start node.
@@ -107,67 +113,6 @@
 // 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) {
-  ResultTy Res = Get(N, Tag());
-  // If there's no batch update in progress, simply return node's children.
-  if (!BUI) return Res;
-
-  // CFG children are actually its *most current* children, and we have to
-  // reverse-apply the future updates to get the node's children at the
-  // point in time 

[PATCH] D77341: [DomTree] Replace ChildrenGetter with GraphTraits over GraphDiff.

[Alina Sbirlea via Phabricator via cfe-commits]

asbirlea marked 2 inline comments as done.
asbirlea added a comment.

Thank you for all the comments.




Comment at: llvm/include/llvm/Support/GenericDomTreeConstruction.h:325
+auto  = BUI ? BUI->PreViewCFG : EmptyGD;
+return !empty(children({, N}));
   }

kuhar wrote:
> asbirlea wrote:
> > kuhar wrote:
> > > This pattern repeats a few times. Could it be pushed into a helper 
> > > function to get something like this?
> > > 
> > > ```
> > > return !empty(children(GetGraphDiffNodePair(BUI, N)));
> > > ```
> > > 
> > My dilemma here is how to not allocate a GraphDiffT instance. There are 4 
> > cases where the pattern is inside a static method and once in a class 
> > method. I used a stack var for the 4 cases and a unique_ptr for the class 
> > method.
> > 
> > Sure, I can do:
> > ```
> > static auto getGDNPair(BUI, EmptyGD, N) {
> > return std::make_pair<>(BUI ? BUI->PreViewCFG : EmptyGD, N);
> > }
> > {
> > ...
> > GraphDiffT EmptyGD;
> > return !empty(children(getGDNPair(BUI, , N)));
> > }
> > ```
> > But it felt like moving one line at the callsite to a oneline helper is not 
> > making things much better.
> > 
> > 
> > I was hoping for something more along the lines of:
> > ```
> > return !empty(children({getGD(BUI), N});
> > ```
> > Or, ensure BUI is always non-null, and simplify to:
> > ```
> > return !empty(children({BUI->PreViewCFG, N});
> > ```
> > 
> > 
> > Thoughts?
> Does allocating a GD have a big cost?
> 
> I think you could get away with returning a temporary GD object that would 
> die as soon as the expression evaluation ends -- should be no different than 
> placing it on the stack just before the function call.
> 
> Overall, I still don't understand why you try to avoid creating a wrapper 
> function / struct that returns children, and call `childredn<...>(...)` 
> directly. Either way, I being able to write:
> ```
> return !empty(children({getGD(BUI), N});
> ```
> or 
> ```
> return !empty(getChildren(BUI, N));
> ```
> would definitely be concise and readable enough IMO.
> Does allocating a GD have a big cost?
AFAIU, dynamically allocating the object does, vs having a stack variable.


I'll do a follow-up cleanup attempt.


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D77341



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

[PATCH] D77341: [DomTree] Replace ChildrenGetter with GraphTraits over GraphDiff.

[Jakub Kuderski via Phabricator via cfe-commits]

kuhar accepted this revision.
kuhar added a comment.
This revision is now accepted and ready to land.

Looks good to me overall. I don't want to block it over the cosmetic issues 
like allocating the empty GD object.




Comment at: llvm/include/llvm/Support/GenericDomTreeConstruction.h:325
+auto  = BUI ? BUI->PreViewCFG : EmptyGD;
+return !empty(children({, N}));
   }

asbirlea wrote:
> kuhar wrote:
> > This pattern repeats a few times. Could it be pushed into a helper function 
> > to get something like this?
> > 
> > ```
> > return !empty(children(GetGraphDiffNodePair(BUI, N)));
> > ```
> > 
> My dilemma here is how to not allocate a GraphDiffT instance. There are 4 
> cases where the pattern is inside a static method and once in a class method. 
> I used a stack var for the 4 cases and a unique_ptr for the class method.
> 
> Sure, I can do:
> ```
> static auto getGDNPair(BUI, EmptyGD, N) {
> return std::make_pair<>(BUI ? BUI->PreViewCFG : EmptyGD, N);
> }
> {
> ...
> GraphDiffT EmptyGD;
> return !empty(children(getGDNPair(BUI, , N)));
> }
> ```
> But it felt like moving one line at the callsite to a oneline helper is not 
> making things much better.
> 
> 
> I was hoping for something more along the lines of:
> ```
> return !empty(children({getGD(BUI), N});
> ```
> Or, ensure BUI is always non-null, and simplify to:
> ```
> return !empty(children({BUI->PreViewCFG, N});
> ```
> 
> 
> Thoughts?
Does allocating a GD have a big cost?

I think you could get away with returning a temporary GD object that would die 
as soon as the expression evaluation ends -- should be no different than 
placing it on the stack just before the function call.

Overall, I still don't understand why you try to avoid creating a wrapper 
function / struct that returns children, and call `childredn<...>(...)` 
directly. Either way, I being able to write:
```
return !empty(children({getGD(BUI), N});
```
or 
```
return !empty(getChildren(BUI, N));
```
would definitely be concise and readable enough IMO.


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D77341



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

[PATCH] D77341: [DomTree] Replace ChildrenGetter with GraphTraits over GraphDiff.

[Alina Sbirlea via Phabricator via cfe-commits]

asbirlea marked 4 inline comments as done.
asbirlea added inline comments.



Comment at: llvm/include/llvm/Support/GenericDomTreeConstruction.h:325
+auto  = BUI ? BUI->PreViewCFG : EmptyGD;
+return !empty(children({, N}));
   }

kuhar wrote:
> This pattern repeats a few times. Could it be pushed into a helper function 
> to get something like this?
> 
> ```
> return !empty(children(GetGraphDiffNodePair(BUI, N)));
> ```
> 
My dilemma here is how to not allocate a GraphDiffT instance. There are 4 cases 
where the pattern is inside a static method and once in a class method. I used 
a stack var for the 4 cases and a unique_ptr for the class method.

Sure, I can do:
```
static auto getGDNPair(BUI, EmptyGD, N) {
return std::make_pair<>(BUI ? BUI->PreViewCFG : EmptyGD, N);
}
{
...
GraphDiffT EmptyGD;
return !empty(children(getGDNPair(BUI, , N)));
}
```
But it felt like moving one line at the callsite to a oneline helper is not 
making things much better.


I was hoping for something more along the lines of:
```
return !empty(children({getGD(BUI), N});
```
Or, ensure BUI is always non-null, and simplify to:
```
return !empty(children({BUI->PreViewCFG, N});
```


Thoughts?


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D77341



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

[PATCH] D77341: [DomTree] Replace ChildrenGetter with GraphTraits over GraphDiff.

[Alina Sbirlea via Phabricator via cfe-commits]

asbirlea updated this revision to Diff 255852.
asbirlea marked an inline comment as done.
asbirlea added a comment.

Name anonymous namespace.


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D77341

Files:
  clang/include/clang/Analysis/Analyses/Dominators.h
  llvm/include/llvm/IR/CFGDiff.h
  llvm/include/llvm/IR/Dominators.h
  llvm/include/llvm/Support/GenericDomTree.h
  llvm/include/llvm/Support/GenericDomTreeConstruction.h
  llvm/lib/IR/Dominators.cpp

Index: llvm/lib/IR/Dominators.cpp
===
--- llvm/lib/IR/Dominators.cpp
+++ llvm/lib/IR/Dominators.cpp
@@ -90,9 +90,10 @@
 DomTreeBuilder::BBPostDomTree , BasicBlock *From, BasicBlock *To);
 
 template void llvm::DomTreeBuilder::ApplyUpdates(
-DomTreeBuilder::BBDomTree , DomTreeBuilder::BBUpdates);
+DomTreeBuilder::BBDomTree , DomTreeBuilder::BBDomTreeGraphDiff &);
 template void llvm::DomTreeBuilder::ApplyUpdates(
-DomTreeBuilder::BBPostDomTree , DomTreeBuilder::BBUpdates);
+DomTreeBuilder::BBPostDomTree ,
+DomTreeBuilder::BBPostDomTreeGraphDiff &);
 
 template bool llvm::DomTreeBuilder::Verify(
 const DomTreeBuilder::BBDomTree ,
Index: llvm/include/llvm/Support/GenericDomTreeConstruction.h
===
--- llvm/include/llvm/Support/GenericDomTreeConstruction.h
+++ llvm/include/llvm/Support/GenericDomTreeConstruction.h
@@ -58,6 +58,13 @@
   using TreeNodePtr = DomTreeNodeBase *;
   using RootsT = decltype(DomTreeT::Roots);
   static constexpr bool IsPostDom = DomTreeT::IsPostDominator;
+  using GraphDiffT = GraphDiff;
+  using GraphDiffNodePair = std::pair;
+  using GraphDiffInvNodePair = std::pair>;
+  using GraphDiffNodePairIfDomT =
+  std::conditional_t;
+  using GraphDiffNodePairIfPDomT =
+  std::conditional_t;
 
   // Information record used by Semi-NCA during tree construction.
   struct InfoRec {
@@ -77,28 +84,27 @@
   using UpdateT = typename DomTreeT::UpdateType;
   using UpdateKind = typename DomTreeT::UpdateKind;
   struct BatchUpdateInfo {
-SmallVector Updates;
-using NodePtrAndKind = PointerIntPair;
-
-// In order to be able to walk a CFG that is out of sync with the CFG
-// DominatorTree last knew about, use the list of updates to reconstruct
-// previous CFG versions of the current CFG. For each node, we store a set
-// of its virtually added/deleted future successors and predecessors.
-// Note that these children are from the future relative to what the
-// DominatorTree knows about -- using them to gets us some snapshot of the
-// CFG from the past (relative to the state of the CFG).
-DenseMap> FutureSuccessors;
-DenseMap> FuturePredecessors;
+// Note: Updates inside PreViewCFG are aleady legalized.
+BatchUpdateInfo(GraphDiffT )
+: PreViewCFG(PreViewCFG),
+  NumLegalized(PreViewCFG.getNumLegalizedUpdates()) {}
+
 // Remembers if the whole tree was recalculated at some point during the
 // current batch update.
 bool IsRecalculated = false;
+GraphDiffT 
+const size_t NumLegalized;
   };
 
   BatchUpdateInfo *BatchUpdates;
   using BatchUpdatePtr = BatchUpdateInfo *;
+  std::unique_ptr EmptyGD;
 
   // If BUI is a nullptr, then there's no batch update in progress.
-  SemiNCAInfo(BatchUpdatePtr BUI) : BatchUpdates(BUI) {}
+  SemiNCAInfo(BatchUpdatePtr BUI) : BatchUpdates(BUI) {
+if (!BatchUpdates)
+  EmptyGD = std::make_unique();
+  }
 
   void clear() {
 NumToNode = {nullptr}; // Restore to initial state with a dummy start node.
@@ -107,67 +113,6 @@
 // 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) {
-  ResultTy Res = Get(N, Tag());
-  // If there's no batch update in progress, simply return node's children.
-  if (!BUI) return Res;
-
-  // CFG children are actually its *most current* children, and we have to
-  // reverse-apply the future updates to get the node's children at the
-  // point in time the update was performed.
-  auto  = (Inverse != 

[PATCH] D77341: [DomTree] Replace ChildrenGetter with GraphTraits over GraphDiff.

[David Blaikie via Phabricator via cfe-commits]

dblaikie added inline comments.



Comment at: llvm/include/llvm/IR/CFGDiff.h:198
 
+namespace {
+template 

kuhar wrote:
> kuhar wrote:
> > What benefit does an anonymous namespace in a header have over a named one, 
> > e.g., `detail`/`impl`? Doesn't it make it more difficult to deduplicate 
> > symbols across different translation units? Not sure what the best 
> > practices are in C++ now in this area.
> Found an article on this matter: 
> https://wiki.sei.cmu.edu/confluence/display/cplusplus/DCL59-CPP.+Do+not+define+an+unnamed+namespace+in+a+header+file
Oh, yeah, sorry I didn't spot that - yeah, anonymous namespaces in header files 
are a no-go. This should be a `detail` (`detail` outnumbers `impl` 361 to 41 in 
the LLVM project) namespace within the llvm namespace as suggested.


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D77341



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

[PATCH] D77341: [DomTree] Replace ChildrenGetter with GraphTraits over GraphDiff.

[Jakub Kuderski via Phabricator via cfe-commits]

kuhar added inline comments.



Comment at: llvm/include/llvm/IR/CFGDiff.h:198
 
+namespace {
+template 

kuhar wrote:
> What benefit does an anonymous namespace in a header have over a named one, 
> e.g., `detail`/`impl`? Doesn't it make it more difficult to deduplicate 
> symbols across different translation units? Not sure what the best practices 
> are in C++ now in this area.
Found an article on this matter: 
https://wiki.sei.cmu.edu/confluence/display/cplusplus/DCL59-CPP.+Do+not+define+an+unnamed+namespace+in+a+header+file


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D77341



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

[PATCH] D77341: [DomTree] Replace ChildrenGetter with GraphTraits over GraphDiff.

[Jakub Kuderski via Phabricator via cfe-commits]

kuhar added a comment.

In D77341#1960854 , @asbirlea wrote:

> Address comments.


Thanks for the changes and explanations. It think with a few more tweaks this 
will be a good refactoring step towards phasing out BUI.




Comment at: llvm/include/llvm/IR/CFGDiff.h:198
 
+namespace {
+template 

What benefit does an anonymous namespace in a header have over a named one, 
e.g., `detail`/`impl`? Doesn't it make it more difficult to deduplicate symbols 
across different translation units? Not sure what the best practices are in C++ 
now in this area.



Comment at: llvm/include/llvm/Support/GenericDomTreeConstruction.h:325
+auto  = BUI ? BUI->PreViewCFG : EmptyGD;
+return !empty(children({, N}));
   }

This pattern repeats a few times. Could it be pushed into a helper function to 
get something like this?

```
return !empty(children(GetGraphDiffNodePair(BUI, N)));
```



Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D77341



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

[PATCH] D77341: [DomTree] Replace ChildrenGetter with GraphTraits over GraphDiff.

[Alina Sbirlea via Phabricator via cfe-commits]

asbirlea updated this revision to Diff 254943.
asbirlea marked 16 inline comments as done.
asbirlea added a comment.

Address comments.


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D77341

Files:
  clang/include/clang/Analysis/Analyses/Dominators.h
  llvm/include/llvm/IR/CFGDiff.h
  llvm/include/llvm/IR/Dominators.h
  llvm/include/llvm/Support/GenericDomTree.h
  llvm/include/llvm/Support/GenericDomTreeConstruction.h
  llvm/lib/IR/Dominators.cpp

Index: llvm/lib/IR/Dominators.cpp
===
--- llvm/lib/IR/Dominators.cpp
+++ llvm/lib/IR/Dominators.cpp
@@ -90,9 +90,10 @@
 DomTreeBuilder::BBPostDomTree , BasicBlock *From, BasicBlock *To);
 
 template void llvm::DomTreeBuilder::ApplyUpdates(
-DomTreeBuilder::BBDomTree , DomTreeBuilder::BBUpdates);
+DomTreeBuilder::BBDomTree , DomTreeBuilder::BBDomTreeGraphDiff &);
 template void llvm::DomTreeBuilder::ApplyUpdates(
-DomTreeBuilder::BBPostDomTree , DomTreeBuilder::BBUpdates);
+DomTreeBuilder::BBPostDomTree ,
+DomTreeBuilder::BBPostDomTreeGraphDiff &);
 
 template bool llvm::DomTreeBuilder::Verify(
 const DomTreeBuilder::BBDomTree ,
Index: llvm/include/llvm/Support/GenericDomTreeConstruction.h
===
--- llvm/include/llvm/Support/GenericDomTreeConstruction.h
+++ llvm/include/llvm/Support/GenericDomTreeConstruction.h
@@ -58,6 +58,13 @@
   using TreeNodePtr = DomTreeNodeBase *;
   using RootsT = decltype(DomTreeT::Roots);
   static constexpr bool IsPostDom = DomTreeT::IsPostDominator;
+  using GraphDiffT = GraphDiff;
+  using GraphDiffNodePair = std::pair;
+  using GraphDiffInvNodePair = std::pair>;
+  using GraphDiffNodePairIfDomT =
+  std::conditional_t;
+  using GraphDiffNodePairIfPDomT =
+  std::conditional_t;
 
   // Information record used by Semi-NCA during tree construction.
   struct InfoRec {
@@ -77,28 +84,27 @@
   using UpdateT = typename DomTreeT::UpdateType;
   using UpdateKind = typename DomTreeT::UpdateKind;
   struct BatchUpdateInfo {
-SmallVector Updates;
-using NodePtrAndKind = PointerIntPair;
-
-// In order to be able to walk a CFG that is out of sync with the CFG
-// DominatorTree last knew about, use the list of updates to reconstruct
-// previous CFG versions of the current CFG. For each node, we store a set
-// of its virtually added/deleted future successors and predecessors.
-// Note that these children are from the future relative to what the
-// DominatorTree knows about -- using them to gets us some snapshot of the
-// CFG from the past (relative to the state of the CFG).
-DenseMap> FutureSuccessors;
-DenseMap> FuturePredecessors;
+// Note: Updates inside PreViewCFG are aleady legalized.
+BatchUpdateInfo(GraphDiffT )
+: PreViewCFG(PreViewCFG),
+  NumLegalized(PreViewCFG.getNumLegalizedUpdates()) {}
+
 // Remembers if the whole tree was recalculated at some point during the
 // current batch update.
 bool IsRecalculated = false;
+GraphDiffT 
+const size_t NumLegalized;
   };
 
   BatchUpdateInfo *BatchUpdates;
   using BatchUpdatePtr = BatchUpdateInfo *;
+  std::unique_ptr EmptyGD;
 
   // If BUI is a nullptr, then there's no batch update in progress.
-  SemiNCAInfo(BatchUpdatePtr BUI) : BatchUpdates(BUI) {}
+  SemiNCAInfo(BatchUpdatePtr BUI) : BatchUpdates(BUI) {
+if (!BatchUpdates)
+  EmptyGD = std::make_unique();
+  }
 
   void clear() {
 NumToNode = {nullptr}; // Restore to initial state with a dummy start node.
@@ -107,67 +113,6 @@
 // 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) {
-  ResultTy Res = Get(N, Tag());
-  // If there's no batch update in progress, simply return node's children.
-  if (!BUI) return Res;
-
-  // CFG children are actually its *most current* children, and we have to
-  // reverse-apply the future updates to get the node's children at the
-  // point in time the update was performed.
-  auto  = (Inverse != 

[PATCH] D77341: [DomTree] Replace ChildrenGetter with GraphTraits over GraphDiff.

[Alina Sbirlea via Phabricator via cfe-commits]

asbirlea added inline comments.



Comment at: llvm/include/llvm/Support/GenericDomTreeConstruction.h:185
+  std::make_pair(GDTmp, BB);
+  for (auto  : children(GDNodePair)) {
+const NodePtr Succ = Pair.second;

kuhar wrote:
> Won't children infer the template parameter based on the passes value? I 
> don't get why the template argument type is a pair where the second argument 
> is a directed nodeptr, but the runtime value is always a plain nodeptr. 
> Couldn't the second pair type also be directed for `GDNodePair`?
The directed nodeptr is the equivalent of a bool inside GraphDiff translating 
to what kind of children do you want; the second pair argument bears no info of 
that kind, only the actual NodePtr for which we desire the children.



Comment at: llvm/include/llvm/Support/GenericDomTreeConstruction.h:186
+  for (auto  : children(GDNodePair)) {
+const NodePtr Succ = Pair.second;
 const auto SIT = NodeToInfo.find(Succ);

kuhar wrote:
> kuhar wrote:
> > Could this new code be a hoisted into a helper function?
> Or alternatively, could the old `ChildrenGetter` be implemented with these 5 
> magic lines?
I think it looks much cleaner after the latest update, let me know what you 
think.



Comment at: llvm/include/llvm/Support/GenericDomTreeConstruction.h:1543
+  // FIXME: Updated to use the PreViewCFG and behave the same as until now.
+  // This behavior is however incorrect; this actually needs the PostViewCFG.
+  GraphDiff PreViewCFG(

kuhar wrote:
> Does this care about the direction (pre- or post-) at all, or does it need 
> some CFG view? Why is pre-view incorrect?
The purpose of this method was to update the DT assuming an additional list of 
updates (the argument given). In practice, the BUI argument is ignored in the 
`CalculateFromScratch` call below. Hence we need the additional changes to 
support this kind of updates inside `CalculateFromScratch` and the other 
methods.


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D77341



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

[PATCH] D77341: [DomTree] Replace ChildrenGetter with GraphTraits over GraphDiff.

[Jakub Kuderski via Phabricator via cfe-commits]

kuhar added inline comments.



Comment at: llvm/include/llvm/IR/CFGDiff.h:199
+namespace {
+template  struct reverse_if_helper;
+template <> struct reverse_if_helper {

You can use two helper functions taking `integral_constant` 
tags -- should be less verbose



Comment at: llvm/include/llvm/Support/GenericDomTreeConstruction.h:89
 bool IsRecalculated = false;
+GraphDiffT *PreViewOfCFG;
+const size_t NumLegalized;

nit: Why pointer instead of keeping a reference?



Comment at: llvm/include/llvm/Support/GenericDomTreeConstruction.h:177
   constexpr bool Direction = IsReverse != IsPostDom;  // XOR.
-  for (const NodePtr Succ :
-   ChildrenGetter::Get(BB, BatchUpdates)) {
+  typedef
+  typename std::conditional, NodePtr>::type

nit: use `using` instead of `typefef`.



Comment at: llvm/include/llvm/Support/GenericDomTreeConstruction.h:178
+  typedef
+  typename std::conditional, NodePtr>::type
+  IsRevType;

nit: can we use `std::conditional_t<...>` in c++14 to get rid of `typename` and 
`::type`? Or does it make some buildbots unhappy?



Comment at: llvm/include/llvm/Support/GenericDomTreeConstruction.h:179
+  typename std::conditional, NodePtr>::type
+  IsRevType;
+  using GraphDiffBBPair = std::pair;

nit: I don't find this name very informative. Maybe something like `DirectedBB`?



Comment at: llvm/include/llvm/Support/GenericDomTreeConstruction.h:183
+  BatchUpdates ? BatchUpdates->PreViewOfCFG : EmptyGD.get();
+  std::pair GDNodePair =
+  std::make_pair(GDTmp, BB);

`std::pair GDNodePair(GDTmp, BB)`



Comment at: llvm/include/llvm/Support/GenericDomTreeConstruction.h:185
+  std::make_pair(GDTmp, BB);
+  for (auto  : children(GDNodePair)) {
+const NodePtr Succ = Pair.second;

Won't children infer the template parameter based on the passes value? I don't 
get why the template argument type is a pair where the second argument is a 
directed nodeptr, but the runtime value is always a plain nodeptr. Couldn't the 
second pair type also be directed for `GDNodePair`?



Comment at: llvm/include/llvm/Support/GenericDomTreeConstruction.h:186
+  for (auto  : children(GDNodePair)) {
+const NodePtr Succ = Pair.second;
 const auto SIT = NodeToInfo.find(Succ);

Could this new code be a hoisted into a helper function?



Comment at: llvm/include/llvm/Support/GenericDomTreeConstruction.h:1146
   if (Update.getKind() == UpdateKind::Insert)
-DT.insertEdge(Update.getFrom(), Update.getTo());
+InsertEdge(DT, nullptr, Update.getFrom(), Update.getTo());
   else

Could you add a comment next to the nullptr with the argument name?



Comment at: llvm/include/llvm/Support/GenericDomTreeConstruction.h:1543
+  // FIXME: Updated to use the PreViewCFG and behave the same as until now.
+  // This behavior is however incorrect; this actually needs the PostViewCFG.
+  GraphDiff PreViewCFG(

Does this care about the direction (pre- or post-) at all, or does it need some 
CFG view? Why is pre-view incorrect?


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D77341



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

[PATCH] D77341: [DomTree] Replace ChildrenGetter with GraphTraits over GraphDiff.

[Jakub Kuderski via Phabricator via cfe-commits]

kuhar added inline comments.



Comment at: llvm/include/llvm/Support/GenericDomTreeConstruction.h:186
+  for (auto  : children(GDNodePair)) {
+const NodePtr Succ = Pair.second;
 const auto SIT = NodeToInfo.find(Succ);

kuhar wrote:
> Could this new code be a hoisted into a helper function?
Or alternatively, could the old `ChildrenGetter` be implemented with these 5 
magic lines?


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D77341



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

[PATCH] D77341: [DomTree] Replace ChildrenGetter with GraphTraits over GraphDiff.

[David Blaikie via Phabricator via cfe-commits]

dblaikie added a comment.

Couple of small nits, but I'll leave most of the review to someoen else here - 
I /think/ it's beyond my context/experience (but if necessary, poke me and I 
can look more/ask more questions/etc)




Comment at: llvm/include/llvm/Support/GenericDomTreeConstruction.h:324-325
+const GraphDiffT *GDTmp = BUI ? BUI->PreViewOfCFG : 
+std::pair GDNodePair =
+std::make_pair(GDTmp, N);
+for (auto  : children(GDNodePair)) {

No need for make_pair if you're going to specify the types on the LHS, could 
write this as:
```
std::pair<...> GDNodePair(GDTmp, N);
```
(similarly two instances further down in this patch - make_pair or explicit 
type, not both)


Or you could use auto on the LHS given the types of the two parameters seem 
close enough that it's not too surprising what make_pair produces, maybe even 
just roll it all in together:
```
return !empty(children(std::make_pair(GDTmp, N)));
```



Comment at: llvm/include/llvm/Support/GenericDomTreeConstruction.h:326-330
+for (auto  : children(GDNodePair)) {
+  (void)Pair;
+  return true;
+}
+return false;

Probably write this as (if I'm understanding the code/intent correctly):
```
return !empty(children(GDNodePair));
```


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D77341



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

[PATCH] D77341: [DomTree] Replace ChildrenGetter with GraphTraits over GraphDiff.

[Alina Sbirlea via Phabricator via cfe-commits]

asbirlea added a comment.

I sent this out to get some general feedback, but I'd like to be able to 
simplify the fact that this is replacing a `for` over `ChildrenGetter` with a 
`for` over `children(pair)`, plus 5 lines to set up the type and pair; 
one simplification is around getting the type inside `children` 
(`GraphDiffBBPair`) and another around having the BUI or not; for the latter 
I'm considering updating a few places such that BUI is never nullptr.


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D77341



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

[PATCH] D77341: [DomTree] Replace ChildrenGetter with GraphTraits over GraphDiff.

[Alina Sbirlea via Phabricator via cfe-commits]

asbirlea created this revision.
asbirlea added reviewers: kuhar, dblaikie, NutshellySima.
Herald added subscribers: cfe-commits, hiraditya.
Herald added a project: clang.
asbirlea added a comment.
asbirlea added a parent revision: D77167: [GraphDiff] Extend GraphDiff to track 
a list of updates..

I sent this out to get some general feedback, but I'd like to be able to 
simplify the fact that this is replacing a `for` over `ChildrenGetter` with a 
`for` over `children(pair)`, plus 5 lines to set up the type and pair; 
one simplification is around getting the type inside `children` 
(`GraphDiffBBPair`) and another around having the BUI or not; for the latter 
I'm considering updating a few places such that BUI is never nullptr.


This replaces the ChildrenGetter inside the DominatorTree with
GraphTraits over a GraphDiff object, an object which encapsulated the
view of the previous CFG.
This also simplifies the extentions in clang which use DominatorTree, as
GraphDiff also filters nullptrs.


Repository:
  rG LLVM Github Monorepo

https://reviews.llvm.org/D77341

Files:
  clang/include/clang/Analysis/Analyses/Dominators.h
  llvm/include/llvm/IR/CFGDiff.h
  llvm/include/llvm/IR/Dominators.h
  llvm/include/llvm/Support/GenericDomTree.h
  llvm/include/llvm/Support/GenericDomTreeConstruction.h
  llvm/lib/IR/Dominators.cpp

Index: llvm/lib/IR/Dominators.cpp
===
--- llvm/lib/IR/Dominators.cpp
+++ llvm/lib/IR/Dominators.cpp
@@ -90,9 +90,10 @@
 DomTreeBuilder::BBPostDomTree , BasicBlock *From, BasicBlock *To);
 
 template void llvm::DomTreeBuilder::ApplyUpdates(
-DomTreeBuilder::BBDomTree , DomTreeBuilder::BBUpdates);
+DomTreeBuilder::BBDomTree , DomTreeBuilder::BBDomTreeGraphDiff &);
 template void llvm::DomTreeBuilder::ApplyUpdates(
-DomTreeBuilder::BBPostDomTree , DomTreeBuilder::BBUpdates);
+DomTreeBuilder::BBPostDomTree ,
+DomTreeBuilder::BBPostDomTreeGraphDiff &);
 
 template bool llvm::DomTreeBuilder::Verify(
 const DomTreeBuilder::BBDomTree ,
Index: llvm/include/llvm/Support/GenericDomTreeConstruction.h
===
--- llvm/include/llvm/Support/GenericDomTreeConstruction.h
+++ llvm/include/llvm/Support/GenericDomTreeConstruction.h
@@ -58,6 +58,7 @@
   using TreeNodePtr = DomTreeNodeBase *;
   using RootsT = decltype(DomTreeT::Roots);
   static constexpr bool IsPostDom = DomTreeT::IsPostDominator;
+  using GraphDiffT = GraphDiff;
 
   // Information record used by Semi-NCA during tree construction.
   struct InfoRec {
@@ -77,28 +78,27 @@
   using UpdateT = typename DomTreeT::UpdateType;
   using UpdateKind = typename DomTreeT::UpdateKind;
   struct BatchUpdateInfo {
-SmallVector Updates;
-using NodePtrAndKind = PointerIntPair;
-
-// In order to be able to walk a CFG that is out of sync with the CFG
-// DominatorTree last knew about, use the list of updates to reconstruct
-// previous CFG versions of the current CFG. For each node, we store a set
-// of its virtually added/deleted future successors and predecessors.
-// Note that these children are from the future relative to what the
-// DominatorTree knows about -- using them to gets us some snapshot of the
-// CFG from the past (relative to the state of the CFG).
-DenseMap> FutureSuccessors;
-DenseMap> FuturePredecessors;
+// Note: Updates inside PreViewOfCFG are aleady legalized.
+BatchUpdateInfo(GraphDiffT )
+: PreViewOfCFG(),
+  NumLegalized(PreViewOfCFG.getNumLegalizedUpdates()) {}
+
 // Remembers if the whole tree was recalculated at some point during the
 // current batch update.
 bool IsRecalculated = false;
+GraphDiffT *PreViewOfCFG;
+const size_t NumLegalized;
   };
 
   BatchUpdateInfo *BatchUpdates;
   using BatchUpdatePtr = BatchUpdateInfo *;
+  std::unique_ptr EmptyGD;
 
   // If BUI is a nullptr, then there's no batch update in progress.
-  SemiNCAInfo(BatchUpdatePtr BUI) : BatchUpdates(BUI) {}
+  SemiNCAInfo(BatchUpdatePtr BUI) : BatchUpdates(BUI) {
+if (!BatchUpdates)
+  EmptyGD = std::make_unique();
+  }
 
   void clear() {
 NumToNode = {nullptr}; // Restore to initial state with a dummy start node.
@@ -107,67 +107,6 @@
 // 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