Added cg_diff.

git-svn-id: svn://svn.valgrind.org/valgrind/trunk@11193 a5019735-40e9-0310-863c-91ae7b9d1cf9

4 files changed, 472 insertions, 19 deletions

diff --git a/cachegrind/Makefile.am b/cachegrind/Makefile.am
index 81f37df5..308e7d43 100644
--- a/cachegrind/Makefile.am
+++ b/cachegrind/Makefile.am
@@ -8,7 +8,7 @@ EXTRA_DIST = \
 # Headers, etc
 #----------------------------------------------------------------------------
 
-bin_SCRIPTS = cg_annotate
+bin_SCRIPTS = cg_annotate cg_diff
 
 noinst_HEADERS = \
 	cg_arch.h \
diff --git a/cachegrind/cg_annotate.in b/cachegrind/cg_annotate.in
index 3a51d4bd..9dc95658 100644
--- a/cachegrind/cg_annotate.in
+++ b/cachegrind/cg_annotate.in
@@ -120,7 +120,7 @@ my @sort_order;
 # handled this proportion of all the events thresholded.
 my @thresholds;
 
-my $default_threshold = 99;
+my $default_threshold = 0.1;
 
 my $single_threshold  = $default_threshold;
 
@@ -149,8 +149,8 @@ usage: cg_annotate [options] cachegrind-out-file [source-files...]
     --version             show version
     --show=A,B,C          only show figures for events A,B,C [all]
     --sort=A,B,C          sort columns by events A,B,C [event column order]
-    --threshold=<0--100>  percentage of counts (of primary sort event) we
-                          are interested in [$default_threshold%]
+    --threshold=<0--20>   a function is shown if it accounts for more than x% of
+                          the counts of the primary sort event [$default_threshold]
     --auto=yes|no         annotate all source files containing functions
                           that helped reach the event count threshold [no]
     --context=N           print N lines of context before and after
@@ -217,7 +217,7 @@ sub process_cmd_line()
             # --threshold=X (tolerates a trailing '%')
             } elsif ($arg =~ /^--threshold=([\d\.]+)%?$/) {
                 $single_threshold = $1;
-                ($1 >= 0 && $1 <= 100) or die($usage);
+                ($1 >= 0 && $1 <= 20) or die($usage);
 
             # --auto=yes|no
             } elsif ($arg =~ /^--auto=yes$/) {
@@ -377,7 +377,7 @@ sub read_input_file()
     # the primary sort event, and 0% for the rest.
     if (not @thresholds) {
         foreach my $e (@sort_order) {
-            push(@thresholds, 0);
+            push(@thresholds, 100);
         }
         $thresholds[0] = $single_threshold;
     }
@@ -617,17 +617,18 @@ sub print_summary_and_fn_totals ()
     # Print functions, stopping when the threshold has been reached.
     foreach my $fn_name (@fn_fullnames) {
 
+        my $fn_CC = $fn_totals{$fn_name};
+
         # Stop when we've reached all the thresholds
-        my $reached_all_thresholds = 1;
+        my $any_thresholds_exceeded = 0;
         foreach my $i (0 .. scalar @thresholds - 1) {
-            my $prop = safe_div(abs($curr_totals[$i] * 100),
+            my $prop = safe_div(abs($fn_CC->[$sort_order[$i]] * 100),
                                 abs($summary_CC->[$sort_order[$i]]));
-            $reached_all_thresholds &&= ($prop >= $thresholds[$i]);
+            $any_thresholds_exceeded ||= ($prop >= $thresholds[$i]);
         }
-        last if $reached_all_thresholds;
+        last if not $any_thresholds_exceeded;
 
         # Print function results
-        my $fn_CC = $fn_totals{$fn_name};
         print_CC($fn_CC, $fn_CC_col_widths);
         print(" $fn_name\n");
 
diff --git a/cachegrind/cg_diff.in b/cachegrind/cg_diff.in
new file mode 100755
index 00000000..951066e4
--- /dev/null
+++ b/cachegrind/cg_diff.in
@@ -0,0 +1,328 @@
+#! @PERL@
+
+##--------------------------------------------------------------------##
+##--- Cachegrind's differencer.                         cg_diff.in ---##
+##--------------------------------------------------------------------##
+
+#  This file is part of Cachegrind, a Valgrind tool for cache
+#  profiling programs.
+#
+#  Copyright (C) 2002-2010 Nicholas Nethercote
+#     njn@valgrind.org
+#
+#  This program is free software; you can redistribute it and/or
+#  modify it under the terms of the GNU General Public License as
+#  published by the Free Software Foundation; either version 2 of the
+#  License, or (at your option) any later version.
+#
+#  This program is distributed in the hope that it will be useful, but
+#  WITHOUT ANY WARRANTY; without even the implied warranty of
+#  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+#  General Public License for more details.
+#
+#  You should have received a copy of the GNU General Public License
+#  along with this program; if not, write to the Free Software
+#  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
+#  02111-1307, USA.
+#
+#  The GNU General Public License is contained in the file COPYING.
+
+#----------------------------------------------------------------------------
+# This is a very cut-down and modified version of cg_annotate.
+#----------------------------------------------------------------------------
+
+use warnings;
+use strict;
+
+#----------------------------------------------------------------------------
+# Global variables
+#----------------------------------------------------------------------------
+
+# Version number
+my $version = "@VERSION@";
+
+# Usage message.
+my $usage = <<END
+usage: cg_diff [options] <cachegrind-out-file1> <cachegrind-out-file2>
+
+  options for the user, with defaults in [ ], are:
+    -h --help             show this message
+    -v --version          show version
+    --mod-filename=<expr> a Perl search-and-replace expression that is applied
+                          to filenames, eg. --mod-filename='s/prog[0-9]/projN/'
+
+  cg_diff is Copyright (C) 2010-2010 Nicholas Nethercote.
+  and licensed under the GNU General Public License, version 2.
+  Bug reports, feedback, admiration, abuse, etc, to: njn\@valgrind.org.
+                                                
+END
+;
+
+# --mod-filename expression
+my $mod_filename = undef;
+
+#-----------------------------------------------------------------------------
+# Argument and option handling
+#-----------------------------------------------------------------------------
+sub process_cmd_line() 
+{
+    my ($file1, $file2) = (undef, undef);
+
+    for my $arg (@ARGV) { 
+
+        if ($arg =~ /^-/) {
+            # --version
+            if ($arg =~ /^-v$|^--version$/) {
+                die("cg_diff-$version\n");
+
+            } elsif ($arg =~ /^--mod-filename=(.*)/) {
+                $mod_filename = $1;
+
+            } else {            # -h and --help fall under this case
+                die($usage);
+            }
+
+        } elsif (not defined($file1)) {
+            $file1 = $arg;
+
+        } elsif (not defined($file2)) {
+            $file2 = $arg;
+
+        } else {
+            die($usage);
+        }
+    }
+
+    # Must have specified two input files.
+    if (not defined $file1 or not defined $file2) {
+        die($usage);
+    }
+
+    return ($file1, $file2);
+}
+
+#-----------------------------------------------------------------------------
+# Reading of input file
+#-----------------------------------------------------------------------------
+sub max ($$) 
+{
+    my ($x, $y) = @_;
+    return ($x > $y ? $x : $y);
+}
+
+# Add the two arrays;  any '.' entries are ignored.  Two tricky things:
+# 1. If $a2->[$i] is undefined, it defaults to 0 which is what we want; we turn
+#    off warnings to allow this.  This makes things about 10% faster than
+#    checking for definedness ourselves.
+# 2. We don't add an undefined count or a ".", even though it's value is 0,
+#    because we don't want to make an $a2->[$i] that is undef become 0
+#    unnecessarily.
+sub add_array_a_to_b ($$) 
+{
+    my ($a, $b) = @_;
+
+    my $n = max(scalar @$a, scalar @$b);
+    $^W = 0;
+    foreach my $i (0 .. $n-1) {
+        $b->[$i] += $a->[$i] if (defined $a->[$i] && "." ne $a->[$i]);
+    }
+    $^W = 1;
+}
+
+sub sub_array_b_from_a ($$) 
+{
+    my ($a, $b) = @_;
+
+    my $n = max(scalar @$a, scalar @$b);
+    $^W = 0;
+    foreach my $i (0 .. $n-1) {
+        $a->[$i] -= $b->[$i];       # XXX: doesn't handle '.' entries
+    }
+    $^W = 1;
+}
+
+# Add each event count to the CC array.  '.' counts become undef, as do
+# missing entries (implicitly).
+sub line_to_CC ($$)
+{
+    my ($line, $numEvents) = @_;
+
+    my @CC = (split /\s+/, $line);
+    (@CC <= $numEvents) or die("Line $.: too many event counts\n");
+    return \@CC;
+}
+
+sub read_input_file($) 
+{
+    my ($input_file) = @_;
+
+    open(INPUTFILE, "< $input_file") 
+         || die "Cannot open $input_file for reading\n";
+
+    # Read "desc:" lines.
+    my $desc;
+    my $line;
+    while ($line = <INPUTFILE>) {
+        if ($line =~ s/desc:\s+//) {
+            $desc .= $line;
+        } else {
+            last;
+        }
+    }
+
+    # Read "cmd:" line (Nb: will already be in $line from "desc:" loop above).
+    ($line =~ s/^cmd:\s+//) or die("Line $.: missing command line\n");
+    my $cmd = $line;
+    chomp($cmd);    # Remove newline
+
+    # Read "events:" line.  We make a temporary hash in which the Nth event's
+    # value is N, which is useful for handling --show/--sort options below.
+    $line = <INPUTFILE>;
+    (defined $line && $line =~ s/^events:\s+//) 
+        or die("Line $.: missing events line\n");
+    my @events = split(/\s+/, $line);
+    my $numEvents = scalar @events;
+
+    my $currFileName;
+    my $currFileFuncName;
+
+    my %CCs;                    # hash("$filename#$funcname" => CC array)
+    my $currCC = undef;         # CC array
+
+    my $summaryCC;
+
+    # Read body of input file.
+    while (<INPUTFILE>) {
+        s/#.*$//;   # remove comments
+        if (s/^(\d+)\s+//) {
+            my $CC = line_to_CC($_, $numEvents);
+            defined($currCC) || die;
+            add_array_a_to_b($CC, $currCC);
+
+        } elsif (s/^fn=(.*)$//) {
+            defined($currFileName) || die;
+            $currFileFuncName = "$currFileName#$1";
+            $currCC = $CCs{$currFileFuncName};
+            if (not defined $currCC) {
+                $currCC = [];
+                $CCs{$currFileFuncName} = $currCC;
+            }
+
+        } elsif (s/^fl=(.*)$//) {
+            $currFileName = $1;
+            if (defined $mod_filename) {
+                eval "\$currFileName =~ $mod_filename";
+            }
+            # Assume that a "fn=" line is followed by a "fl=" line.
+            $currFileFuncName = undef;  
+
+        } elsif (s/^\s*$//) {
+            # blank, do nothing
+        
+        } elsif (s/^summary:\s+//) {
+            $summaryCC = line_to_CC($_, $numEvents);
+            (scalar(@$summaryCC) == @events) 
+                or die("Line $.: summary event and total event mismatch\n");
+
+        } else {
+            warn("WARNING: line $. malformed, ignoring\n");
+        }
+    }
+
+    # Check if summary line was present
+    if (not defined $summaryCC) {
+        die("missing final summary line, aborting\n");
+    }
+
+    close(INPUTFILE);
+
+    return ($cmd, \@events, \%CCs, $summaryCC);
+}
+
+#----------------------------------------------------------------------------
+# "main()"
+#----------------------------------------------------------------------------
+# Commands seen in the files.  Need not match.
+my $cmd1;
+my $cmd2;
+
+# Events seen in the files.  They must match.
+my $events1;
+my $events2;
+
+# Individual CCs, organised by filename/funcname/line_num.
+# hashref("$filename#$funcname", CC array)
+my $CCs1;
+my $CCs2;
+
+# Total counts for summary (an arrayref).
+my $summaryCC1;
+my $summaryCC2;
+
+#----------------------------------------------------------------------------
+# Read the input files
+#----------------------------------------------------------------------------
+my ($file1, $file2) = process_cmd_line();
+($cmd1, $events1, $CCs1, $summaryCC1) = read_input_file($file1);
+($cmd2, $events2, $CCs2, $summaryCC2) = read_input_file($file2);
+
+#----------------------------------------------------------------------------
+# Check the events match
+#----------------------------------------------------------------------------
+my $n = max(scalar @$events1, scalar @$events2);
+$^W = 0;    # turn off warnings, because we might hit undefs
+foreach my $i (0 .. $n-1) {
+    ($events1->[$i] eq $events2->[$i]) || die "events don't match, aborting\n";
+}
+$^W = 1;
+
+#----------------------------------------------------------------------------
+# Do the subtraction: CCs2 -= CCs1
+#----------------------------------------------------------------------------
+while (my ($filefuncname, $CC1) = each(%$CCs1)) {
+    my $CC2 = $CCs2->{$filefuncname};
+    if (not defined $CC2) {
+        $CC2 = [];
+        sub_array_b_from_a($CC2, $CC1);     # CC2 -= CC1
+        $CCs2->{$filefuncname} = $CC2;
+    } else {
+        sub_array_b_from_a($CC2, $CC1);     # CC2 -= CC1
+    }
+}
+sub_array_b_from_a($summaryCC2, $summaryCC1);
+
+#----------------------------------------------------------------------------
+# Print the result, in CCs2
+#----------------------------------------------------------------------------
+print("desc: Files compared:   $file1; $file2\n");
+print("cmd:  $cmd1; $cmd2\n");
+print("events: ");
+for my $e (@$events1) {
+    print(" $e");
+}
+print("\n");
+
+while (my ($filefuncname, $CC) = each(%$CCs2)) {
+
+    my @x = split(/#/, $filefuncname);
+    (scalar @x == 2) || die;
+
+    print("fl=$x[0]\n");
+    print("fn=$x[1]\n");
+
+    print("0");
+    foreach my $n (@$CC) {
+        print(" $n");
+    }
+    print("\n");
+}
+
+print("summary:");
+foreach my $n (@$summaryCC2) {
+    print(" $n");
+}
+print("\n");
+
+##--------------------------------------------------------------------##
+##--- end                                                          ---##
+##--------------------------------------------------------------------##
diff --git a/cachegrind/docs/cg-manual.xml b/cachegrind/docs/cg-manual.xml
index e8ab23db..b312771f 100644
--- a/cachegrind/docs/cg-manual.xml
+++ b/cachegrind/docs/cg-manual.xml
@@ -98,8 +98,10 @@ be normally run.</para>
 <para>Then, you need to run Cachegrind itself to gather the profiling
 information, and then run cg_annotate to get a detailed presentation of that
 information.  As an optional intermediate step, you can use cg_merge to sum
-together the outputs of multiple Cachegrind runs, into a single file which
-you then use as the input for cg_annotate.</para>
+together the outputs of multiple Cachegrind runs into a single file which
+you then use as the input for cg_annotate.  Alternatively, you can use
+cg_diff to difference the outputs of two Cachegrind runs into a signel file
+which you then use as the input for cg_annotate.</para>
 
 
 <sect2 id="cg-manual.running-cachegrind" xreflabel="Running Cachegrind">
@@ -697,6 +699,85 @@ fail these checks.</para>
 </sect2>
 
 
+<sect2 id="cg-manual.cg_diff" xreflabel="cg_diff">
+<title>Differencing Profiles with cg_diff</title>
+
+<para>
+cg_diff is a simple program which
+reads two profile files, as created by Cachegrind, finds the difference
+between them, and writes the results into another file in the same format.
+You can then examine the merged results using
+<computeroutput>cg_annotate &lt;filename&gt;</computeroutput>, as
+described above.  This is very useful if you want to measure how a change to
+a program affected its performance.
+</para>
+
+<para>
+cg_diff is invoked as follows:
+</para>
+
+<programlisting><![CDATA[
+cg_diff file1 file2]]></programlisting>
+
+<para>
+It reads and checks <computeroutput>file1</computeroutput>, then read
+and checks <computeroutput>file2</computeroutput>, then computes the
+difference (effectively <computeroutput>file1</computeroutput> -
+<computeroutput>file2</computeroutput>).  The final results are written to
+standard output.</para>
+
+<para>
+Costs are summed on a per-function basis.  Per-line costs are not summed,
+because doing so is too difficult.  For example, consider differencing two
+profiles, one from a single-file program A, and one from the same program A
+where a single blank line was inserted at the top of the file.  Every single
+per-line count has changed.  In comparison, the per-function counts have not
+changed.  The per-function count differences are still very useful for
+determining differences between programs.  Note that because the result is
+the difference of two profiles, many of the counts will be negative;  this
+indicates that the counts for the relevant function are fewer in the second
+version than those in the first version.</para>
+
+<para>
+cg_diff does not attempt to check
+that the input files come from runs of the same executable.  It will
+happily merge together profile files from completely unrelated
+programs.  It does however check that the
+<computeroutput>Events:</computeroutput> lines of all the inputs are
+identical, so as to ensure that the addition of costs makes sense.
+For example, it would be nonsensical for it to add a number indicating
+D1 read references to a number from a different file indicating L2
+write misses.</para>
+
+<para>
+A number of other syntax and sanity checks are done whilst reading the
+inputs.  cg_diff will stop and
+attempt to print a helpful error message if any of the input files
+fail these checks.</para>
+
+<para>
+Sometimes you will want to compare Cachegrind profiles of two versions of a
+program that you have sitting side-by-side.  For example, you might have
+<computeroutput>version1/prog.c</computeroutput> and
+<computeroutput>version2/prog.c</computeroutput>, where the second is
+slightly different to the first.  A straight comparison of the two will not
+be useful -- because functions are qualified with filenames, a function
+<function>f</function> will be listed as
+<computeroutput>version1/prog.c:f</computeroutput> for the first version but
+<computeroutput>version2/prog.c:f</computeroutput> for the second
+version.</para>
+
+<para>
+When this happens, you can use the <option>--mod-filename</option> option.
+Its argument is a Perl search-and-replace expression that will be applied
+to all the filenames in both Cachegrind output files.  It can be used to
+remove minor differences in filenames.  For example, the option
+<option>--mod-filename='s/version[0-9]/versionN/'</option> will suffice for
+this case.</para>
+
+</sect2>
+
+
 </sect1>
 
 
@@ -842,21 +923,21 @@ fail these checks.</para>
 
   <varlistentry>
     <term>
-      <option><![CDATA[--threshold=X [default: 99%] ]]></option>
+      <option><![CDATA[--threshold=X [default: 0.1%] ]]></option>
     </term>
     <listitem>
       <para>Sets the threshold for the function-by-function
-      summary.  Functions are shown that account for more than X%
-      of the primary sort event.  If auto-annotating, also affects
-      which files are annotated.</para>
+      summary.  A function is shown if it accounts for more than X%
+      of the counts for the primary sort event.  If auto-annotating, also
+      affects which files are annotated.</para>
         
       <para>Note: thresholds can be set for more than one of the
       events by appending any events for the
       <option>--sort</option> option with a colon
       and a number (no spaces, though).  E.g. if you want to see
-      the functions that cover 99% of L2 read misses and 99% of L2
+      each function that covers more than 1% of L2 read misses or 1% of L2
       write misses, use this option:</para>
-      <para><option>--sort=D2mr:99,D2mw:99</option></para>
+      <para><option>--sort=D2mr:1,D2mw:1</option></para>
     </listitem>
   </varlistentry>
 
@@ -900,6 +981,49 @@ fail these checks.</para>
 </sect1>
 
 
+<sect1 id="cg-manual.diffopts" xreflabel="cg_diff Command-line Options">
+<title>cg_diff Command-line Options</title>
+
+<!-- start of xi:include in the manpage -->
+<variablelist id="cg_diff.opts.list">
+
+  <varlistentry>
+    <term>
+      <option><![CDATA[-h --help ]]></option>
+    </term>
+    <listitem>
+      <para>Show the help message.</para>
+    </listitem>
+  </varlistentry>
+
+  <varlistentry>
+    <term>
+      <option><![CDATA[--version ]]></option>
+    </term>
+    <listitem>
+      <para>Show the version number.</para>
+    </listitem>
+  </varlistentry>
+
+  <varlistentry>
+    <term>
+      <option><![CDATA[--mod-filename=<expr> [default: none]]]></option>
+    </term>
+    <listitem>
+      <para>Specifies a Perl search-and-replace expression that is applied
+      to all filenames.  Useful for removing minor differences in paths
+      between two different versions of a program that are sitting in
+      different directories.</para>
+    </listitem>
+  </varlistentry>
+
+</variablelist>
+<!-- end of xi:include in the manpage -->
+  
+</sect1>
+
+
+
 
 <sect1 id="cg-manual.acting-on"
        xreflabel="Acting on Cachegrind's Information">