PR10594: Provide a cached dwarf_getscopes_die

This avoids repeated DIE traversal by caching all parents on the first
call, so future calls are just a simple walk up parent links.

* dwflpp.cxx (dwflpp::getscopes_die): New cached function that mimics
  libdw's dwarf_getscopes_die using cached parent links.
  (dwflpp::cache_die_parents): New function to build the parent cache.
  (dwflpp::~dwflpp): Clean up the parent caches.
  (dwflpp::iterate_over_labels): Use the cached getscopes_die.
  (dwflpp::find_variable_and_frame_base): Ditto.
* tapsets.cxx (dwarf_derived_probe::saveargs): Ditto.
  (uprobe_derived_probe::saveargs): Ditto.
  (dwarf_var_expanding_visitor::visit_target_symbol_context): Ditto.

3 files changed, 121 insertions, 20 deletions

diff --git a/dwflpp.cxx b/dwflpp.cxx
index 2437630e..d96f3eda 100644
--- a/dwflpp.cxx
+++ b/dwflpp.cxx
@@ -56,6 +56,10 @@ extern "C" {
 }
 
 
+// debug flag to compare to the uncached version from libdw
+// #define DEBUG_DWFLPP_GETSCOPES 1
+
+
 using namespace std;
 using namespace __gnu_cxx;
 
@@ -110,6 +114,10 @@ dwflpp::~dwflpp()
        it != global_alias_cache.end(); ++it)
     delete it->second;
 
+  for (mod_cu_die_parent_cache_t::iterator it = cu_die_parent_cache.begin();
+       it != cu_die_parent_cache.end(); ++it)
+    delete it->second;
+
   if (dwfl)
     dwfl_end(dwfl);
 }
@@ -591,6 +599,89 @@ dwflpp::iterate_over_inline_instances (int (* callback)(Dwarf_Die * die, void *
 }
 
 
+void
+dwflpp::cache_die_parents(cu_die_parent_cache_t* parents, Dwarf_Die* die)
+{
+  // Record and recurse through DIEs we care about
+  Dwarf_Die child, import;
+  if (dwarf_child(die, &child) == 0)
+    do
+      {
+        switch (dwarf_tag (&child))
+          {
+          // normal tags to recurse
+          case DW_TAG_compile_unit:
+          case DW_TAG_module:
+          case DW_TAG_lexical_block:
+          case DW_TAG_with_stmt:
+          case DW_TAG_catch_block:
+          case DW_TAG_try_block:
+          case DW_TAG_entry_point:
+          case DW_TAG_inlined_subroutine:
+          case DW_TAG_subprogram:
+            parents->insert(make_pair(child.addr, *die));
+            cache_die_parents(parents, &child);
+            break;
+
+          // record only, nothing to recurse
+          case DW_TAG_label:
+            parents->insert(make_pair(child.addr, *die));
+            break;
+
+          // imported dies should be followed
+          case DW_TAG_imported_unit:
+            if (dwarf_attr_die(&child, DW_AT_import, &import))
+              {
+                parents->insert(make_pair(import.addr, *die));
+                cache_die_parents(parents, &import);
+              }
+            break;
+
+          // nothing to do for other tags
+          default:
+            break;
+          }
+      }
+    while (dwarf_siblingof(&child, &child) == 0);
+}
+
+
+vector<Dwarf_Die>
+dwflpp::getscopes_die(Dwarf_Die* die)
+{
+  assert (cu);
+
+  cu_die_parent_cache_t *parents = cu_die_parent_cache[cu->addr];
+  if (!parents)
+    {
+      parents = new cu_die_parent_cache_t;
+      cu_die_parent_cache[cu->addr] = parents;
+      cache_die_parents(parents, cu);
+      if (sess.verbose > 4)
+        clog << "die parent cache " << module_name << ":" << cu_name()
+             << " size " << parents->size() << endl;
+    }
+
+  vector<Dwarf_Die> scopes;
+  scopes.push_back(*die);
+  for (cu_die_parent_cache_t::iterator it = parents->find(die->addr);
+       it != parents->end(); it = parents->find(it->second.addr))
+    scopes.push_back(it->second);
+
+#ifdef DEBUG_DWFLPP_GETSCOPES
+  Dwarf_Die *dscopes;
+  int nscopes = dwarf_getscopes_die(die, &dscopes);
+
+  assert(nscopes == (int)scopes.size());
+  for (unsigned i = 0; i < scopes.size(); ++i)
+    assert(scopes[i].addr == dscopes[i].addr);
+  free(dscopes);
+#endif
+
+  return scopes;
+}
+
+
 int
 dwflpp::global_alias_caching_callback(Dwarf_Die *die, void *arg)
 {
@@ -1025,9 +1116,8 @@ dwflpp::iterate_over_labels (Dwarf_Die *begin_die,
               Dwarf_Addr stmt_addr;
               if (dwarf_lowpc (&die, &stmt_addr) == 0)
                 {
-                  Dwarf_Die *scopes;
-                  int nscopes = dwarf_getscopes_die (&die, &scopes);
-                  if (nscopes > 1)
+                  vector<Dwarf_Die> scopes = getscopes_die(&die);
+                  if (scopes.size() > 1)
                     callback(current_function, name, file, dline,
                              &scopes[1], stmt_addr, q);
                 }
@@ -1491,6 +1581,7 @@ dwflpp::find_variable_and_frame_base (Dwarf_Die *scope_die,
    * as returned by dwarf_getscopes for the address, starting with the
    * declaring_scope that the variable was found in.
    */
+  vector<Dwarf_Die> vscopes;
   for (int inner = declaring_scope;
        inner < nscopes && fb_attr == NULL;
        ++inner)
@@ -1511,8 +1602,10 @@ dwflpp::find_variable_and_frame_base (Dwarf_Die *scope_die,
            * subroutine is inlined to find the appropriate frame base. */
            if (declaring_scope != -1)
              {
-               nscopes = dwarf_getscopes_die (&scopes[inner], &scopes);
-               if (nscopes == -1)
+               vscopes = getscopes_die(&scopes[inner]);
+               scopes = &vscopes[0];
+               nscopes = vscopes.size();
+               if (!nscopes)
                  throw semantic_error ("unable to get die scopes for '" +
                                        local + "' in an inlined subroutines",
                                        e->tok);
diff --git a/dwflpp.h b/dwflpp.h
index 74a3ae00..e047fcba 100644
--- a/dwflpp.h
+++ b/dwflpp.h
@@ -65,6 +65,12 @@ typedef unordered_map<void*, cu_function_cache_t*> mod_cu_function_cache_t;
 // inline function die -> instance die[]
 typedef unordered_map<void*, std::vector<Dwarf_Die>*> cu_inl_function_cache_t;
 
+// die -> parent die
+typedef unordered_map<void*, Dwarf_Die> cu_die_parent_cache_t;
+
+// cu die -> (die -> parent die)
+typedef unordered_map<void*, cu_die_parent_cache_t*> mod_cu_die_parent_cache_t;
+
 typedef std::vector<func_info> func_info_map_t;
 typedef std::vector<inline_instance_info> inline_instance_map_t;
 
@@ -201,6 +207,8 @@ struct dwflpp
   void iterate_over_inline_instances (int (* callback)(Dwarf_Die * die, void * arg),
                                       void * data);
 
+  std::vector<Dwarf_Die> getscopes_die(Dwarf_Die* die);
+
   Dwarf_Die *declaration_resolve(const char *name);
 
   mod_cu_function_cache_t cu_function_cache;
@@ -292,6 +300,9 @@ private:
   cu_inl_function_cache_t cu_inl_function_cache;
   void cache_inline_instances (Dwarf_Die* die);
 
+  mod_cu_die_parent_cache_t cu_die_parent_cache;
+  void cache_die_parents(cu_die_parent_cache_t* parents, Dwarf_Die* die);
+
   /* The global alias cache is used to resolve any DIE found in a
    * module that is stubbed out with DW_AT_declaration with a defining
    * DIE found in a different module.  The current assumption is that
diff --git a/tapsets.cxx b/tapsets.cxx
index 7912ed99..346fa7f3 100644
--- a/tapsets.cxx
+++ b/tapsets.cxx
@@ -355,7 +355,7 @@ struct dwarf_derived_probe: public derived_probe
   void emit_probe_local_init(translator_output * o);
 
   string args;
-  void saveargs(Dwarf_Die* scope_die);
+  void saveargs(dwarf_query& q, Dwarf_Die* scope_die);
   void printargs(std::ostream &o) const;
 
   // Pattern registration helpers.
@@ -401,7 +401,7 @@ struct uprobe_derived_probe: public derived_probe
                         bool return_p);
 
   string args;
-  void saveargs(Dwarf_Die* scope_die);
+  void saveargs(dwarf_query& q, Dwarf_Die* scope_die);
   void printargs(std::ostream &o) const;
 
   void printsig (std::ostream &o) const;
@@ -2110,10 +2110,8 @@ dwarf_var_expanding_visitor::visit_target_symbol_saved_return (target_symbol* e)
 void
 dwarf_var_expanding_visitor::visit_target_symbol_context (target_symbol* e)
 {
-  Dwarf_Die *scopes;
-  if (dwarf_getscopes_die (scope_die, &scopes) == 0)
+  if (null_die(scope_die))
     return;
-  auto_free free_scopes(scopes);
 
   target_symbol *tsym = new target_symbol;
   print_format* pf = new print_format;
@@ -2161,6 +2159,7 @@ dwarf_var_expanding_visitor::visit_target_symbol_context (target_symbol* e)
       // non-.return probe: support $$parms, $$vars, $$locals
       bool first = true;
       Dwarf_Die result;
+      vector<Dwarf_Die> scopes = q.dw.getscopes_die(scope_die);
       if (dwarf_child (&scopes[0], &result) == 0)
         do
           {
@@ -2745,7 +2744,7 @@ dwarf_derived_probe::dwarf_derived_probe(const string& funcname,
 
   // Save the local variables for listing mode
   if (q.sess.listing_mode_vars)
-    saveargs(scope_die);
+    saveargs(q, scope_die);
 
   // Reset the sole element of the "locations" vector as a
   // "reverse-engineered" form of the incoming (q.base_loc) probe
@@ -2812,12 +2811,10 @@ dwarf_derived_probe::dwarf_derived_probe(const string& funcname,
 
 
 void
-dwarf_derived_probe::saveargs(Dwarf_Die* scope_die)
+dwarf_derived_probe::saveargs(dwarf_query& q, Dwarf_Die* scope_die)
 {
-  Dwarf_Die *scopes;
-  if (!null_die(scope_die) && dwarf_getscopes_die (scope_die, &scopes) == 0)
+  if (null_die(scope_die))
     return;
-  auto_free free_scopes(scopes);
 
   stringstream argstream;
   string type_name;
@@ -2829,6 +2826,7 @@ dwarf_derived_probe::saveargs(Dwarf_Die* scope_die)
     argstream << " $return:" << type_name;
 
   Dwarf_Die arg;
+  vector<Dwarf_Die> scopes = q.dw.getscopes_die(scope_die);
   if (dwarf_child (&scopes[0], &arg) == 0)
     do
       {
@@ -4232,7 +4230,7 @@ uprobe_derived_probe::uprobe_derived_probe (const string& function,
 
   // Save the local variables for listing mode
   if (q.sess.listing_mode_vars)
-    saveargs(scope_die);
+    saveargs(q, scope_die);
 
   // Reset the sole element of the "locations" vector as a
   // "reverse-engineered" form of the incoming (q.base_loc) probe
@@ -4308,14 +4306,12 @@ uprobe_derived_probe::uprobe_derived_probe (probe *base,
 
 
 void
-uprobe_derived_probe::saveargs(Dwarf_Die* scope_die)
+uprobe_derived_probe::saveargs(dwarf_query& q, Dwarf_Die* scope_die)
 {
   // same as dwarf_derived_probe::saveargs
 
-  Dwarf_Die *scopes;
-  if (!null_die(scope_die) && dwarf_getscopes_die (scope_die, &scopes) == 0)
+  if (null_die(scope_die))
     return;
-  auto_free free_scopes(scopes);
 
   stringstream argstream;
   string type_name;
@@ -4327,6 +4323,7 @@ uprobe_derived_probe::saveargs(Dwarf_Die* scope_die)
     argstream << " $return:" << type_name;
 
   Dwarf_Die arg;
+  vector<Dwarf_Die> scopes = q.dw.getscopes_die(scope_die);
   if (dwarf_child (&scopes[0], &arg) == 0)
     do
       {