[Bug tree-optimization/54505] New: RFE: Inline function tables

[Bug tree-optimization/54505] New: RFE: Inline function tables

[avi at redhat dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54505

             Bug #: 54505
           Summary: RFE: Inline function tables
    Classification: Unclassified
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: enhancement
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: avi@redhat.com


It is common to see code such as

  static const int (*ftable[])(struct context *) = { 
      [V1] = f1,
      [V2] = f2,
      ...
  };

  ...

  {
      ftable[nr](context);
  }

However, this is less efficient than an equivalent switch () statement since
the calling convention must be observed.  Some registers are clobbered, others
must be set to the arguments, and the functions must have a prolog and an
epilogue.

It is easy to recognize the pattern though and convert it into an equivalent
switch:

  switch (nr) {
  case V1:
      f1(context);
      break;
  case V2:
      f2(context);
      break;
  ...
  }

[Bug tree-optimization/54505] RFE: Inline function tables

[steven at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54505

Steven Bosscher <steven at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |steven at gcc dot gnu.org

--- Comment #1 from Steven Bosscher <steven at gcc dot gnu.org> 2012-09-06 17:29:02 UTC ---

struct context;

#undef ONE
#undef EIGHT
#define ONE(X)        extern const int f0##X (struct context *);
#define EIGHT(X)    ONE(X##0) ONE(X##1) ONE(X##2) ONE(X##3) \
            ONE(X##4) ONE(X##5) ONE(X##6) ONE(X##7)
EIGHT(0)
EIGHT(1)


#undef ONE
#undef EIGHT
#define ONE(X)        [X] = f0##X,
#define EIGHT(X)    ONE(X##0) ONE(X##1) ONE(X##2) ONE(X##3) \
            ONE(X##4) ONE(X##5) ONE(X##6) ONE(X##7)

static const int (*ftable[])(struct context *) = { 
EIGHT(0)
EIGHT(1)
0
};

extern int foo (int, struct context *);

int
foo (int v, struct context *context)
{
  ftable[v](context);
}

[Bug tree-optimization/54505] RFE: Inline function tables

[steven at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54505

Steven Bosscher <steven at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|steven at gcc dot gnu.org   |

--- Comment #2 from Steven Bosscher <steven at gcc dot gnu.org> 2012-09-06 17:30:43 UTC ---
I don't think this transformation would always be an improvement. Had a
developer wanted to use a switch, I'd think he/she would have used one. A
dispatch table is much more code-size efficient compared to a switch.

[Bug tree-optimization/54505] RFE: Inline function tables

[pinskia at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54505

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> 2012-09-06 19:25:29 UTC ---
I think this optimization is only a benefit when the following happens:
1) all functions will be inlined (not just a wrapper though).
2) the table is small

[Bug tree-optimization/54505] RFE: Inline function tables

[avi at redhat dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54505

--- Comment #4 from Avi Kivity <avi at redhat dot com> 2012-09-09 11:12:53 UTC ---
(In reply to comment #2)
> I don't think this transformation would always be an improvement. 

gcc should make the transformation when it improves the code (like all other
transformations).

> Had a
> developer wanted to use a switch, I'd think he/she would have used one. A
> dispatch table is much more code-size efficient compared to a switch.

gcc often transforms a switch to a dispatch table, with the difference that the
function call convention is not used.  Instead, register values are maintained
across the call, and instead of call/ret, jmp/jmp (on x86) are used.

gcc should allow the programmer to write the code in the cleanest way, and
transform it to the most performing way.  In the same way that gcc converts
some multiplies to a shift, it should convert some indirect function calls to a
non-function dispatch table.  It's inlining but on a larger scale.

[Bug tree-optimization/54505] RFE: Inline function tables

[steven at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54505

Steven Bosscher <steven at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
                 CC|                            |steven at gcc dot gnu.org
         Resolution|                            |WORKSFORME

--- Comment #5 from Steven Bosscher <steven at gcc dot gnu.org> 2012-09-09 21:27:30 UTC ---

> gcc should make the transformation when it improves the code (like
> all other transformations).

And how is gcc supposed to tell when this is an improvement? Your "like all
other transformations" makes no sense, this is not something simple like
constant propagation or redundancy elimination that's almost always a win.

> gcc often transforms a switch to a dispatch table,

Yes, an existing switch, that someone wrote or generated deliberately as a
switch.


> gcc should allow the programmer to write the code in the cleanest way,
> and transform it to the most performing way.

Kicking in open doors doesn't help.


A compiler is not an omniscient, omnipotent translator. If the compiler can't
tell whether the transformation is profitable, it has to use some heuristics to
make a best guess.

In this case, the trade-off is expanding a compact indirect call to a large
body of a switch statement. This might increase the number of branches (e.g. if
the switch is lowered as a decision tree), it could ruin icache, and it may go
against the intent of the programmer. There are no immediately obvious benefits
visible to the compiler.

With -fprofile-use GCC already performs inlining of the most frequently called
callee of an indirect function calls table. It's the only situation where GCC
can be sure that the transformation is profitable.

If you want a switch, write a switch.