Ehren's Blog

Analysis and type madness

Posted in Seneca by ehren on November 18, 2009

I’ve created a simple Dehydra script to check for alwayszero functions. There are some issues however. Here’s the script:

function process_function(f, body)
{
  if (f.type.type.name == 'void' || !f.isVirtual) {
    return;
  }

  var alwayszero = true;

  function processStatements(stmts) {
    for(var j = 0; j < stmts.statements.length; j++) {
      var s = stmts.statements[j];
      if (s.isReturn && s.value != 0) {
        alwayszero = false; 
      }
    }
  }

  for (var i = 0; i < body.length; i++) {
    processStatements(body[i]);
  }

  if (alwayszero) {
    print("alwayszero function: " + f.loc.file + " on line " + f.loc.line +
          ", column " + f.loc.column + " : " + f.type.type.name + " " + f.name);
  }
}

I actually have a more elegant version using a for in loop and iterate_vars but after watching that Douglas Crockford lecture I’m a bit paranoid about such things (both report the same results though).

After doing a bit of post-processing on the output I can report the following:

Functions meeting the above criteria are encountered 5920 times during compilation but most of these are duplicates since there are quite a few method definitions within include files.

Removing all of the duplicates reduces the number to 243 instances encountered (shouldn’t be too difficult to patch manually or with some shell script hackery).

A link to the list of 243 unique instances is here. The full output list can be obtained here (warning: big file).

Unfortunately I have encountered at least one false positive with this script:

gfxFont.cpp on line 960, column 35 : gfxFont::RunMetrics gfxFont::Measure(gfxTextRun*, PRUint32, PRUint32, gfxFont::BoundingBoxType, gfxContext*, gfxFont::Spacing*)

Viewing the definition here, I’m not sure why this function was captured by my analysis but I’ll have to investigate. Ultimately, I think doing this with a Treehydra script might make more sense. There’s already an existing script that does all the heavy lifting, but I haven’t been able to link this into an independent analysis pass on mozilla-central (yet).

Edit: Argh… found another false positive here:
nsSVGContainerFrame.cpp on line 264, column 82 : gfxRect nsSVGDisplayContainerFrame::GetBBoxContribution(const gfxMatrix&)

More Issues:

When I get the plugin ready to go with mozilla, I’ll add a script to xpcom/analysis to ensure that every function which has the user(("alwayszero")) attribute meets the above criteria.

As to excluding non-virtual member functions from the analysis, as far as I can tell GCC should already be able to optimize these away. Perhaps there’s a corner case I haven’t considered though.

Another issue I thought of today is that this script can potentially flag floating point functions as alwayszero which will result in bad things happening if I apply my plugin as originally written to them.

Luckily a fix to the plugin was not that difficult:

static bool
sane_tree_type (tree t)
{
  enum tree_code code = TREE_CODE (TREE_TYPE (t));
  return code == INTEGER_TYPE || code == BOOLEAN_TYPE;
}

 /* other stuff --- see previous posts for context */

static unsigned int
execute_alwayszero_opt (void)
{
  gimple_stmt_iterator gsi;
  basic_block bb;

  FOR_EACH_BB (bb)
    {
      for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
        {
          gimple stmt = gsi_stmt (gsi);

          tree lhs = gimple_get_lhs (stmt);

          if (is_gimple_call (stmt) && lhs != NULL_TREE &&
              is_alwayszero_function (stmt) && sane_tree_type (lhs))
            {
              tree zero = build_int_cst (TREE_TYPE (lhs), 0);
              gimple assign = gimple_build_assign_stat (lhs, zero);
              tree var = create_tmp_var (TREE_TYPE (lhs), "dummy_var");
              add_referenced_var (var);
              mark_sym_for_renaming (var);
              gimple_call_set_lhs (stmt, var);
              gsi_insert_after (&gsi, assign, GSI_CONTINUE_LINKING);
            }
        }
    }

  return 0;
} 

This will exclude pointer types as well which is probably a good thing. If it’s really necessary to optimize away alwayszero REAL_TYPE functions this could be done as well, but they will have to be handled separately. Actually this should be pretty easy but it’s not really a priority at the moment. It probably makes more sense to check the type of the function rather than that of the lhs, but consider the above a proof of concept.

The next step is getting my plugin to work with the GCC 4.3.4 with backported plugin support used to build Dehydra which I now know will not be too difficult. The main issue is that the gimple_stmt_iterator is nowhere to be seen (even though it shows up in the Changelog … wtf) so I’ll have to use the block_stmt_iterator instead which will require a slight bit more ugliness.

The main problem though is getting a plugin to build under the GCC 4.3.4 with backported plugin support used to build Dehydra. 4.5 includes a separate plugin include directory and an easy to use -print-file-name=plugin flag to get at the directory. I’ve tried hacking a build rule into the existing configure script in Dehydra but I’m a complete noob with make and configure stuff so I haven’t had any success yet. Hopefully I can rectify this shortly.

Also, I’ve been attempting to get FF built with 4.5 but have encountered some issues. Once I get a nice sequence of steps that follows the instructions on this page I’ll bring this to the attention of the GCC people.

Advertisements

2 Responses

Subscribe to comments with RSS.

  1. Peter Liu said, on November 19, 2009 at 12:27 pm

    Hi, Ehren.

    The link to Douglas Crockford Lectures is invalid.

    Peter.

  2. ehren said, on November 19, 2009 at 1:10 pm

    Hey Peter,

    It should work now.

    Ehren


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: