This is the mail archive of the systemtap@sourceware.org mailing list for the systemtap project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: BZ#2421 - removing duplicate probe handlers


On Fri, 2006-07-21 at 14:13 -0500, David Smith wrote:
> On Fri, 2006-07-21 at 12:01 -0400, Frank Ch. Eigler wrote:
> > Hi -
> > 
> > > > I've been looking into BZ#2421 this week while waiting for people to
> > > > look at the kernel patch.  [...]
> > 
> > OK.
> 
> ...
> 
> > > [...] So, should function duplication removal work globally or only
> > > per probe specification line?
> > 
> > I imagine it working globally.  I believe what we need is a variant of
> > the compiler optimization known as "value numbering".  It could live
> > in a new optimization pass within semantic_pass_optimize.  It could
> > compute a hash value for every function & probe-handler from the
> > bottom up (requiring a new staptree-related visitor, and include
> > referent-names and parse tree types).  Multiple functions &
> > probe-handlers with the same hash value could be duplicate-eliminated.
> > (In the case of functions, all the callers of one of the duplicates
> > would be redirected to a single one.  In the case of probe handlers,
> > their probe_location would be merged.)  (With the addition of a
> > parse-tree-comparison visitor, one could eliminate the slight risk of
> > a hash collision.)

...

> > Does this make sense?  It's a little more ambitious, but want to give
> > it a try?
> > 
> > - FChE
> 
> It makes since in a vague sort of way.  I'll give it a try and look into
> it.

I've been working on this and here's an update.

I made a stab at removing duplicate functions.  I cheated and just
hashed the args/body of functions to do comparisons.  All duplicate
functions are redirected to the first copy found.  A patch is attached.

I'd appreciate any code comments.


As far as probes go, here I ran into conceptual problems.  There are 8
different kinds of probes derived from derived_probe:
alias_derived_probe, be_derived_probe, never_derived_probe,
dwarf_derived_probe, timer_derived_probe, profile_derived_probe,
mark_derived_probe, and hrtimer_derived_probe.  The way the code
generation currently works, it isn't going to be easy to merge a timer
probe with a dwarf_derived_probe for example - all the needed
information won't be there.  (If we merged the dwarf probe into the
timer probe, the timer probe code generation logic isn't going to know
what to do with the dwarf information.  If we merge the timer probe into
the dwarf probe, the dwarf probe code generation logic isn't going to
like the timer probe location not having any dwarf info.)

OK, I thought, I'll just merge probes of the same kind together -
dwarf_derived_probes with dwarf_derived_probes, timer_derived_probes
with timer_derived_probes, etc.  But, the problem here is certain data
is stored at the probe level, not the location level.  For instance,
timer probes store the timer interval at the probe level, not the
location level.  So, if we merged two timer probes together that had
different intervals, we can merge their location information, but they
are going to end up at the same timer interval.  A similar thing happens
with begin/end probes (be_derived_probes).  The fact that this is a
begin probe vs. an end probe is stored at the probe level, not the
location level.  So, if we merge a begin probe and an end probe
together, we're going to end up with either 2 begin probes or 2 end
probes.

Got any ideas here?

Thanks.

-- 
David Smith
dsmith@redhat.com
Red Hat, Inc.
http://www.redhat.com
256.217.0141 (direct)
256.837.0057 (fax)

Index: elaborate.cxx
===================================================================
RCS file: /cvs/systemtap/src/elaborate.cxx,v
retrieving revision 1.62
diff -u -p -r1.62 elaborate.cxx
--- elaborate.cxx	5 Jun 2006 19:45:56 -0000	1.62
+++ elaborate.cxx	1 Aug 2006 17:40:00 -0000
@@ -24,7 +24,7 @@ extern "C" {
 #include <vector>
 #include <algorithm>
 #include <iterator>
-
+#include <ext/hash_map>
 
 using namespace std;
 
@@ -1550,6 +1550,95 @@ void semantic_pass_opt4 (systemtap_sessi
     }
 }
 
+struct duplicate_function_remover: public functioncall_traversing_visitor
+{
+  systemtap_session& s;
+  bool& relaxed_p;
+  map<functiondecl*, functiondecl*>& duplicate_function_map;
+
+  duplicate_function_remover(systemtap_session& sess, bool& r,
+			     map<functiondecl*, functiondecl*>&dfm):
+    s(sess), relaxed_p(r), duplicate_function_map(dfm) {};
+
+  void visit_functioncall (functioncall* e);
+};
+
+void
+duplicate_function_remover::visit_functioncall (functioncall *e)
+{
+  functioncall_traversing_visitor::visit_functioncall (e);
+
+  // If the current function call reference points to a function that
+  // is a duplicate, replace it.
+  if (duplicate_function_map.count(e->referent) != 0)
+    {
+      if (s.verbose>2)
+	  clog << "Changing " << e->referent->name
+	       << " reference to "
+	       << duplicate_function_map[e->referent]->name
+	       << " reference\n";
+      e->tok = duplicate_function_map[e->referent]->tok;
+      e->function = duplicate_function_map[e->referent]->name;
+      e->referent = duplicate_function_map[e->referent];
+
+      relaxed_p = false;
+    }
+}
+
+static size_t
+hash_functiondecl (functiondecl* f)
+{
+  ostringstream s;
+  __gnu_cxx::hash<const char*> hash_func;
+
+  // Get the "name:args body" of the function in s.  We have to
+  // include the args since the function 'x1(a, b)' is different than
+  // the function 'x2(b, a)' even if the bodies of the two functions
+  // are exactly the same.
+  f->printsig(s);
+  f->body->print(s);
+
+  // printsig puts f->name + ':' on the front.  Remove this
+  // (otherwise, functions would never compare equal).
+  string str = s.str().erase(0, f->name.size() + 1);
+
+  // Actually generate the hash.
+  return hash_func(str.c_str());
+}
+
+void semantic_pass_opt5 (systemtap_session& s, bool& relaxed_p)
+{
+  // Walk through all the functions, looking for duplicates.
+  map<size_t, functiondecl*> function_hash_map;
+  map<functiondecl*, functiondecl*> duplicate_function_map;
+  for (unsigned i=0; i < s.functions.size(); i++)
+    {
+      size_t function_hash = hash_functiondecl(s.functions[i]);
+
+      if (function_hash_map.count(function_hash) == 0)
+	// This function is unique.  Remember it.
+	function_hash_map[function_hash] = s.functions[i];
+      else
+	// This function is a duplicate.
+	duplicate_function_map[s.functions[i]]
+	    = function_hash_map[function_hash];
+    }
+
+  // If we have duplicate functions, traverse down the tree, replacing
+  // the appropriate function calls.
+  // duplicate_function_remover::visit_functioncall() handles the
+  // details of replacing the function calls.  Note that we don't
+  // delete the duplicate functiondecl itself, we'll let pass 1 do
+  // that.
+  if (duplicate_function_map.size() != 0)
+    {
+      duplicate_function_remover dfr (s, relaxed_p, duplicate_function_map);
+
+      for (unsigned i=0; i < s.probes.size(); i++)
+	s.probes[i]->body->visit(&dfr);
+    }
+}
+
 
 static int
 semantic_pass_optimize (systemtap_session& s)
@@ -1571,6 +1660,7 @@ semantic_pass_optimize (systemtap_sessio
       semantic_pass_opt2 (s, relaxed_p);
       semantic_pass_opt3 (s, relaxed_p);
       semantic_pass_opt4 (s, relaxed_p);
+      semantic_pass_opt5 (s, relaxed_p);
     }
 
   if (s.probes.size() == 0)

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]