Re: TREE_UNCHANGING?

[Bryce McKinlay <bryce at waitaki dot otago dot ac dot nz>]

Tom Tromey wrote:

>Jason> Of course, that's not true until the object is fully
>Jason> constructed, and inlined constructors could cause trouble.  And
>Jason> have, in my experimentation with TREE_CONSTANT;
>Jason> g++.rfg/21027_14+.C was misoptimized because I was assigning
>Jason> multiple times to an UNCHANGING location.
>
>This would still be useful for gcj.  In Java, the vtable really never
>changes (at least, as long as vtables aren't moved by the GC -- but we
>already assume a non-moving collector).  
>

Even if the collector moved vtables it wouldn't matter - the contents of 
the vtable doesn't change so it doesn't matter if its cached in a 
register or whatever.

>Superclass constructors always see the end vtable.
>

Right. In Java the vtable pointer is set before any constructor code is 
run (and a vtable for a class must be laid out before any instances of 
that class can exist), so no problems there.

>For gcj we'd also like to be able to tell the compiler that the length
>field of an array never changes.  It is set when the array is
>constructed, but that happens in C++ and is hidden from gcj.  I think
>this is similar to saying that the vtable pointer can't change.  I had
>some example code a few months ago where I assumed gcj would optimize
>out a redundant length check, but didn't.
>  
>

Hoisting of vtable and array-length lookups would both be very useful 
optimizations for Java. A while back I spent some time messing with 
TREE_READONLY, TREE_CONSTANT, and the alias stuff trying to get it to 
happen, but as you noticed, it doesn't work.

I think the reason, as Daniel Berlin said, is that the loop code 
believes that the dereference can trap and thus refuses to hoist it. In 
many cases this is a valid reason to not optimize it, since if there are 
side-effects between the start of the loop and the potentially trapping 
instruction then a NullPointerException would be thrown with the program 
in the wrong state. This problem could often be avoided by peeling the 
first iteration.

However there are also many cases where the lookup could be legitimately 
hoisted without peeling: when the object reference is proven to be 
non-null (because it has been rereferenced already), or when there are 
no side effects that could change the externally-visible state.

Example:

class Call
{
  void a() {}
 
  static void foo(Call c)
  {
    for (int i=0; i < 500000; i++)
      {
        c.a();
      }
  }
}

Currently we get:

    movl    $_ZN4Call6class$E, (%esp)
    movl    8(%ebp), %esi    #  c,  c
    call    _Jv_InitClass
.L3:
    cmpl    $499999, %ebx    #  i
    jg    .L2
    movl    %esi, (%esp)    #  c
    movl    (%esi), %eax    #  <variable>.vtable
    incl    %ebx    #  i
    call    *28(%eax)
    jmp    .L3


In this case the *28(%eax) could be put in a register outside the loop 
because even if there is an exception when loading it the external state 
of the program is uneffected - "c" and "i" are both local.

It gets a bit more interesting with indirect dispatch:

    movl    $_ZN4Call6class$E, (%esp)
    movl    8(%ebp), %esi    #  c,  c
    call    _Jv_InitClass
    movl    otable+4, %edi    #  otable
.L3:
    cmpl    $499999, %ebx    #  i
    jg    .L2
    movl    %esi, (%esp)    #  c
    movl    (%esi), %eax    #  <variable>.vtable
    incl    %ebx    #  i
    call    *(%edi,%eax)
    jmp    .L3


Here the otable lookup has been hoisted (because it is truely static), 
but the vtable lookup is not. Interestingly the indirect dispatch code 
executes faster anyway, but if the final address to call - ie the result 
of dereferencing (%edi + %eax) - were hoisted then it would be another 
clear win.

regards

Bryce.