Ehren's Blog

A GCC Hack (My 0.1 Release)

Posted in Seneca by ehren on October 24, 2009

It’s late and I have not been able to fix what I believe is a bug preventing access to the attribute flags of indirect calls to virtual member functions from within tree-ssa-ccp.c (as described in my last post). I’ve posted a clearer overview of the bug that doesn’t involve my attribute on the project wiki in case anyone has a suggestion. For now though, I’ve decided to bypass the call flags problem and move onto the optimization since I have to release something for my 0.1 in DPS909.

Seneca’s IT people are still blocking subversion so I won’t post a proper patch but when you find out what I’ve done you won’t want to compile any air traffic control software with my custom GCC anyway. I’ll just cut to the chase and post the function that contains my modifications (I haven’t even created a separate handle_attribute function but this is just a proof of concept):

/* Evaluate statement STMT.  If the statement produces an output value and
   its evaluation changes the lattice value of its output, return
   SSA_PROP_INTERESTING and set *OUTPUT_P to the SSA_NAME holding the
   output value.
   
   If STMT is a conditional branch and we can determine its truth
   value, set *TAKEN_EDGE_P accordingly.  If STMT produces a varying
   value, return SSA_PROP_VARYING.  */

static enum ssa_prop_result
ccp_visit_stmt (gimple stmt, edge *taken_edge_p, tree *output_p)
{
  tree def;
  ssa_op_iter iter;

  if (dump_file && (dump_flags & TDF_DETAILS))
    {
      fprintf (dump_file, "\nVisiting statement:\n");
      print_gimple_stmt (dump_file, stmt, 0, dump_flags);
    }

  switch (gimple_code (stmt))
    {
      case GIMPLE_ASSIGN:
        /* If the statement is an assignment that produces a single
           output value, evaluate its RHS to see if the lattice value of
           its output has changed.  */
        return visit_assignment (stmt, output_p);

      case GIMPLE_CALL:
        /* A value-returning call also performs an assignment.  */
        if (gimple_call_lhs (stmt) != NULL_TREE)
          {            
            /* Handle alwayszero functions */
            FILE* fp = fopen ("alwayszero.txt", "r");  /* Hack */  
            if (fp)
         /* if (gimple_call_flags (stmt) & ECF_ALWAYSZERO) */
              {
                tree lhs = gimple_get_lhs (stmt);
                tree zero = build_int_cst (TREE_TYPE (lhs), 0);
                prop_value_t zero_constant;
                zero_constant.value = zero;
                zero_constant.lattice_val = CONSTANT;
                set_lattice_value(lhs, zero_constant);
                *output_p = lhs;

                fclose(fp);

                return SSA_PROP_INTERESTING;
              }
            else
              return visit_assignment (stmt, output_p);
          }
        break;

      case GIMPLE_COND:
      case GIMPLE_SWITCH:
        /* If STMT is a conditional branch, see if we can determine
           which branch will be taken.   */
        /* FIXME.  It appears that we should be able to optimize
           computed GOTOs here as well.  */
        return visit_cond_stmt (stmt, taken_edge_p);

      default:
        break;
    }

  /* Any other kind of statement is not interesting for constant
     propagation and, therefore, not worth simulating.  */
  if (dump_file && (dump_flags & TDF_DETAILS))
    fprintf (dump_file, "No interesting values produced.  Marked VARYING.\n");

  /* Definitions made by statements other than assignments to
     SSA_NAMEs represent unknown modifications to their outputs.
     Mark them VARYING.  */
  FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
    {
      prop_value_t v = { VARYING, NULL_TREE };
      set_lattice_value (def, v);
    }

  return SSA_PROP_VARYING;
}

As you can see, if alwayszero.txt is in the current directory, EVERY assignment with a rhs function call that’s complex enough to invoke the propagation engine will have its lhs set to zero.

Here’s a demonstration:

/* blah.h */
class Blah {
 public:
  virtual int blah() __attribute__((alwayszero));
};

/* blah.cpp */
#include "blah.h"
int Blah::blah() 
{
  return 5;
}

/* main.cpp */
#include <cstdio>
#include "blah.h"
int main()
{
  Blah b;
  Blah* p = &b;
  int x;
  x = p->blah();
  printf("%d\n", x);
  return 0;
}

With the system’s compiler:

$ g++ main.cpp blah.cpp -O2
In file included from main.cpp:4:
blah.h:5: warning: ‘alwayszero’ attribute directive ignored
In file included from blah.cpp:3:
blah.h:5: warning: ‘alwayszero’ attribute directive ignored
$ ./a.out
5
$

With the custom compiler:

$ ~/gcc/dist/bin/g++ main.cpp blah.cpp -O2
$ ./a.out
0
$

(note that the alwayszero attribute is unnecessary here since with this hack every propagation worthy value returning call will have it’s return value set to zero when alwayszero.txt is present. See this post for an overview of adding the attribute.)

I should also mention that when asking on #gcc about the attribute recognition problem, I was pointed towards tree-vrp.c. I ended up misinterpreted this advice as a suggestion about where to look for alternative methods of accessing the call flags and not how to approach the optimization in general. However, this file is where I found the build_int_cst function which creates a new tree representing an integer constant.

To make sure the optimization works as expected, I modified main.cpp to look like this:

/* main.cpp */
#include <cstdio>
#include "blah.h"
int main()
{
  Blah b;
  Blah* p = &b;
  int x;
  x = p->blah();
  if (x) 
    {
       printf("blah\n");
       printf("blah\n");
       printf("blah\n");
       printf("blah\n");
       printf("blah\n");
       /* etc (2000+ more times) */
    }
  return 0;
}

The resulting executable size when compiled with the system’s GCC is over 16 MB. The executable size when compiled with the modified version is about 7 KB. Also, with more applicability to the Mozilla use case, when changing the blah member function of the test program to return 0 instead of 5 the unnecessary branch is still kept when compiling with the normal GCC (executable size is still 16 MB), even though it’s clear this branch will never be used. I now see, as Taras mentioned, that dynamic linking mucks everything up (edit: oops dynamic dispatch != dynamic linking).

Before I go to sleep I’d like to briefly return to the call flag recognition problem. The following is an alternative way of determining the attributes of a gimple call:

    tree t = gimple_call_fn (stmt);       
    if (t != NULL_TREE)
      {
        tree fntype = TREE_TYPE (t);
        tree attr = lookup_attribute ("alwayszero", TYPE_ATTRIBUTES (fntype));
        if (attr != NULL_TREE)
          /* do stuff */
      }

This also does not work from tree-ssa-ccp.c with my Blah example.

Also, I noticed that the alwayszero attribute came up in the static mailing list under a discussion of plugins. Once the call flags issue has been solved I suppose my next step will be to convert this to a GCC plugin which will probably involve moving this optimization into a separate pass. I will have to investigate how to modularize this code while still hooking into the propagation engine.

I’d also like to remark that I finished before midnight!! (HST)

*Edit: A solution to the attribute problem is probably not essential since this code should be moved into its own pass anyway.

Advertisements

2 Responses

Subscribe to comments with RSS.

  1. […] to gcc, Mozilla, and Ehren.  How far has he gotten two months into the project?  Pretty damn close.  How is this possible?  It comes back to the question of peers, and the potential of open source […]

  2. David said, on January 4, 2012 at 12:02 pm

    I have a question….. Is it possible to manipulate the gimple during the compilation process at pass cfg for example.

    Example of manipulation – a=b+c changed to a=b-c

    Thanks


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: