PATCH: Devirtualization using profiling feedback

[Tomas Bily <tbily at suse dot cz>]

Hi, 

 i am sendig patch for devirtualization virtual calls using profile feedback. 

 Greetings 

 Tomas

ps. devirt-prof.C is c++ testcase and indir-call-prof.c is c testcase

---

PROBLEM DESC.: Devirtualization of virtual calls and directing indirect calls

  A) Lets have an indirect call p (...) where p is pointer to function (type of
  "sometype (*p) (args)"). In some programs there could be p nearly constant. 

  B) Lets have an virtual call p->somemethod (...) where p is instance of class
  with virtual method "somemethod". In some programs there could be p nearly
  constant class.

  Determine most common function call in A) and most common class in B). Use
  this information to improve code effectivity (espetialy info for inliner).

PROBLEM SOLUTION:

 Use actual gcc tree-profiling capability to measure most common func/class.

 1) Assign unique id to every finction/method:

  To structure cgraph_node was added attribute "pid" which is computed in
  function cgraph_finalize_function.

 2) STAGE generating profile:
 
  to every object file add two static variables:

  static void (*__gcov_indirect_call_callee) ();
  static gcov_type* __gcov_indirect_call_counters;

  before each virtual or indirect call add code:

  __gcov_indirect_call_counters = get_relevant_counter_ptr (); 
  __gcov_indirect_call_callee = (void *) indirect call argument;

  At the begining every called function or method (method uniquely determine
  class) add code:

  if (__gcov_indirect_call_callee == my_address)
     __gcov_one_value_profile (__gcov_indirect_call_counters, my pid);

 3) STAGE using profile:

  For every checked indirect/virtual call determine if most common pid of
  function/class method has probability more than 50%. If yes modify code of
  this call to:

  if (actual_callee_addres == addres_of_most_common_function/method)
    do direct call
  else
    old call

Attachment: devirt.patch
Description: Text document

/* { dg-options "-O2 -fdump-tree-optimized -fdump-tree-tree_profile" } */

struct A {
  A () {}

  virtual int AA (void)
  { return 0; }

};

struct B : public A {
  B () {}

  virtual int AA (void)
  { return 1; }
};

int
main (void)
{
  A a;
  B b;
  
  A* p;

  p = &a;
  p->AA ();

  p = &b;
  p->AA ();
  
  return 0;
}

/* { dg-final-use { scan-tree-dump "Devirtualizing.* AA transformation on insn" "tree_profile"} } */                                                  
/* { dg-final-use { scan-tree-dump-not "Invalid sum" "optimized"} } */                                                                                
/* { dg-final-use { cleanup-tree-dump "optimized" } } */                                                                                              
/* { dg-final-use { cleanup-tree-dump "tree_profile" } } */                                                                                           

/* { dg-options "-O2 -fdump-tree-optimized -fdump-tree-tree_profile" } */

static int a1 (void)
{
    return 10;
}

static int a2 (void)
{
    return 0;
}

typedef int (*tp) (void);

static tp aa [] = {a2, a1, a1, a1, a1};

void setp (int (**pp) (void), int i)
{
  if (!i)
    *pp = aa [i];
  else
    *pp = aa [(i & 2) + 1];
}

int
main (void)
{
  int (*p) (void);
  int  i;

  for (i = 0; i < 10; i ++)
    {
	setp (&p, i);
	p ();
    }
  
  return 0;
}

/* { dg-final-use { scan-tree-dump "Devirtualizing.* a1 transformation on insn" "tree_profile"} } */
/* { dg-final-use { scan-tree-dump-not "Invalid sum" "optimized"} } */                                                                                
/* { dg-final-use { cleanup-tree-dump "optimized" } } */                                                                                              
/* { dg-final-use { cleanup-tree-dump "tree_profile" } } */

Attachment: Changelog.txt
Description: Text document