[COMMITTED 77/77] gccrs: forever-stack: Add dfs_cache

From: Arthur Cohen <[email protected]>

We do a *lot* of depth-first-search during name resolution, so having a
temporary cache for the results speeds up the compilation of core by quite
a lot. This is just a simple version that can be improved.

On my machine, this shaves off almost 3 minutes from compiling core.

gcc/rust/ChangeLog:

	* resolve/rust-forever-stack.h: Declare new cache API.
	* resolve/rust-forever-stack.hxx: Implement it and use it within
	dfs_cache.
---
 gcc/rust/resolve/rust-forever-stack.h   |  4 ++++
 gcc/rust/resolve/rust-forever-stack.hxx | 28 ++++++++++++++++++++++++-
 2 files changed, 31 insertions(+), 1 deletion(-)

diff --git a/gcc/rust/resolve/rust-forever-stack.h b/gcc/rust/resolve/rust-forever-stack.h
index 0f95d0d7323..eb21331166c 100644
--- a/gcc/rust/resolve/rust-forever-stack.h
+++ b/gcc/rust/resolve/rust-forever-stack.h
@@ -796,6 +796,10 @@ public:
   tl::optional<const Node &> dfs_node (const Node &starting_point,
 				       NodeId to_find) const;
 
+  std::unordered_map<NodeId, Node &> dfs_cache;
+  tl::optional<Node &> check_cache (NodeId to_find);
+  void cache (NodeId found, Node &result);
+
   bool forward_declared (NodeId definition, NodeId usage)
   {
     if (peek ().kind != Rib::Kind::ForwardTypeParamBan)
diff --git a/gcc/rust/resolve/rust-forever-stack.hxx b/gcc/rust/resolve/rust-forever-stack.hxx
index e901ddbca1c..d7b121a6dd2 100644
--- a/gcc/rust/resolve/rust-forever-stack.hxx
+++ b/gcc/rust/resolve/rust-forever-stack.hxx
@@ -610,8 +610,15 @@ tl::optional<typename ForeverStack<N>::Node &>
 ForeverStack<N>::dfs_node (ForeverStack<N>::Node &starting_point,
 			   NodeId to_find)
 {
+  if (auto found = check_cache (to_find))
+    return found;
+
   if (starting_point.id == to_find)
-    return starting_point;
+    {
+      cache (to_find, starting_point);
+
+      return starting_point;
+    }
 
   for (auto &child : starting_point.children)
     {
@@ -643,6 +650,25 @@ ForeverStack<N>::dfs_node (const ForeverStack<N>::Node &starting_point,
   return tl::nullopt;
 }
 
+template <Namespace N>
+tl::optional<typename ForeverStack<N>::Node &>
+ForeverStack<N>::check_cache (NodeId to_find)
+{
+  auto entry = dfs_cache.find (to_find);
+
+  if (entry != dfs_cache.end ())
+    return entry->second;
+
+  return tl::nullopt;
+}
+
+template <Namespace N>
+void
+ForeverStack<N>::cache (NodeId found, typename ForeverStack<N>::Node &result)
+{
+  dfs_cache.insert ({found, result});
+}
+
 template <Namespace N>
 tl::optional<Rib &>
 ForeverStack<N>::to_rib (NodeId rib_id)
-- 
2.50.1