[Bug tree-optimization/47413] New: Constant Propagation and Virtual Function Tables

[Bug tree-optimization/47413] New: Constant Propagation and Virtual Function Tables

[joerg at joergleis dot com]

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

           Summary: Constant Propagation and Virtual Function Tables
           Product: gcc
           Version: 4.5.2
            Status: UNCONFIRMED
          Severity: enhancement
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: joerg@joergleis.com


The tested GCC version does not fully use its knowledge about (constant)
function pointers. In some cases (with LTO), this occurs frequently. The
following example should illustrate it and it's relevance:


    #include <stdio.h>
    #include <stdlib.h>


    /* the types */

    struct obj;

    struct vtab {
        int (*f)(struct obj *obj);
    };

    struct obj {
        const struct vtab *vtab;
    };


    static int f1337(struct obj *obj)
    {
        return 1337;
    }

    static const struct vtab vtab1337 = {
        .f = f1337
    };


    /* the functions */

    static struct obj *create()
    {
        struct obj *obj;

        if (!(obj = malloc(sizeof(struct obj)))) {
            return NULL;
        }

        obj->vtab = &vtab1337;

        return obj;
    }

    static int call(struct obj *obj)
    {
        return obj->vtab->f(obj);
    }


    /* the program */

    int main()
    {
        struct obj *obj;

        if (!(obj = create())) {
            return 0;
        }

        printf("%d\n", call(obj));
        return 1;
    }

When compiling with -O3, I'd expect GCC to just pass 1337 to printf, as it does
without a virtual function table. Instead, it uses its knowledge about obj to
call vtab1337.f(), as in

    call *vtab1337

but doesn't simplify *vtab1337 to f1337, or the entire call to 1337.

[Bug tree-optimization/47413] Constant Propagation and Virtual Function Tables

[rguenth at gcc dot gnu.org]

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

Richard Guenther <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |missed-optimization
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2011.01.25 11:35:50
                 CC|                            |rguenth at gcc dot gnu.org
     Ever Confirmed|0                           |1

--- Comment #1 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-01-25 11:35:50 UTC ---
With GCC 4.6 I see

<bb 3>:
  obj_11->vtab = &vtab1337;
  D.3820_15 = f1337 (obj_11);
  printf (&"%d\n"[0], D.3820_15);

so it calls f1337 directly, but it doesn't inline it.

We are partly confused by the CFG caused by the NULL test:

<bb 2>:
  obj_11 = malloc (8);
  if (obj_11 == 0B)
    goto <bb 4>;
  else
    goto <bb 3>;

<bb 3>:
  obj_11->vtab = &vtab1337;

<bb 4>:
  # obj_12 = PHI <0B(2), obj_11(3)>
  if (obj_12 == 0B)
    goto <bb 6>;
  else
    goto <bb 5>;

<bb 5>:
  D.3822_13 = obj_12->vtab;
  D.3821_14 = D.3822_13->f;
  D.3820_15 = D.3821_14 (obj_12);

so it takes several iterations through different optimizers to eventually
constant propagate the function address (jump-threading the test in BB4,
which only happens late by DOM).

[Bug tree-optimization/47413] Constant Propagation and Virtual Function Tables

[hubicka at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=47413

Jan Hubicka <hubicka at gcc dot gnu.org> changed:

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

--- Comment #2 from Jan Hubicka <hubicka at gcc dot gnu.org> ---
Current mainline gets pretty close:
;; Function int f1337(obj*) (_ZL5f1337P3obj, funcdef_no=19, decl_uid=3418,
cgraph_uid=19, symbol_order=19)

int f1337(obj*) (struct obj * obj)
{
  <bb 2>:
  return 1337;

}



;; Function int main() (main, funcdef_no=22, decl_uid=3427, cgraph_uid=22,
symbol_order=22) (executed once)

Removing basic block 5
int main() ()
{
  struct obj * obj;
  int _1;
  int _10;

  <bb 2>:
  obj_7 = malloc (8);
  if (obj_7 == 0B)
    goto <bb 4>;
  else
    goto <bb 3>;

  <bb 3>:
  obj_7->vtab = &vtab1337;
  _10 = f1337 (obj_7);
  printf ("%d\n", _10);

  <bb 4>:
  # _1 = PHI <0(2), 1(3)>
  return _1;

}

So we are down to one missing inline. After FRE we get:

  <bb 2>:
  obj_13 = malloc (8);
  if (obj_13 == 0B)
    goto <bb 4>;
  else
    goto <bb 3>;

  <bb 3>:
  obj_13->vtab = &vtab1337;

  <bb 4>:
  # _14 = PHI <0B(2), obj_13(3)>
  if (_14 == 0B)
    goto <bb 6>;
  else
    goto <bb 5>;

  <bb 5>:
  _4 = _14->vtab;
  _15 = _4->f;
  _16 = _15 (_14);
  printf ("%d\n", _16);


So purely local problem. I suppose FRE could propagate through by knowing that
on the other path program with segfault?

[Bug tree-optimization/47413] Constant Propagation and Virtual Function Tables

[rguenther at suse dot de]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=47413

--- Comment #3 from rguenther at suse dot de <rguenther at suse dot de> ---
On Fri, 26 Sep 2014, hubicka at gcc dot gnu.org wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=47413
> 
> Jan Hubicka <hubicka at gcc dot gnu.org> changed:
> 
>            What    |Removed                     |Added
> ----------------------------------------------------------------------------
>                  CC|                            |hubicka at gcc dot gnu.org
> 
> --- Comment #2 from Jan Hubicka <hubicka at gcc dot gnu.org> ---
> Current mainline gets pretty close:
> ;; Function int f1337(obj*) (_ZL5f1337P3obj, funcdef_no=19, decl_uid=3418,
> cgraph_uid=19, symbol_order=19)
> 
> int f1337(obj*) (struct obj * obj)
> {
>   <bb 2>:
>   return 1337;
> 
> }
> 
> 
> 
> ;; Function int main() (main, funcdef_no=22, decl_uid=3427, cgraph_uid=22,
> symbol_order=22) (executed once)
> 
> Removing basic block 5
> int main() ()
> {
>   struct obj * obj;
>   int _1;
>   int _10;
> 
>   <bb 2>:
>   obj_7 = malloc (8);
>   if (obj_7 == 0B)
>     goto <bb 4>;
>   else
>     goto <bb 3>;
> 
>   <bb 3>:
>   obj_7->vtab = &vtab1337;
>   _10 = f1337 (obj_7);
>   printf ("%d\n", _10);
> 
>   <bb 4>:
>   # _1 = PHI <0(2), 1(3)>
>   return _1;
> 
> }
> 
> So we are down to one missing inline. After FRE we get:
> 
>   <bb 2>:
>   obj_13 = malloc (8);
>   if (obj_13 == 0B)
>     goto <bb 4>;
>   else
>     goto <bb 3>;
> 
>   <bb 3>:
>   obj_13->vtab = &vtab1337;
> 
>   <bb 4>:
>   # _14 = PHI <0B(2), obj_13(3)>
>   if (_14 == 0B)
>     goto <bb 6>;
>   else
>     goto <bb 5>;
> 
>   <bb 5>:
>   _4 = _14->vtab;
>   _15 = _4->f;
>   _16 = _15 (_14);
>   printf ("%d\n", _16);
> 
> 
> So purely local problem. I suppose FRE could propagate through by knowing that
> on the other path program with segfault?

Not in the way value-numbering works (it value-numbers _14 as VARYING
obviously).  The above feels like a missed jump-threading opportunity
to me.  Eventually we could also help DOM/copyprop with replacing
the test by _14 != ohj_13 ...

In my view DOM should be able to figure out a value for _14
on the else edge as well (doesn't exactly fit DOM but certainly
most easily implemented there)