Bug 15525

Summary: suggestion to enable cast elimination
Product: gcc Reporter: Tom Tromey <tromey>
Component: javaAssignee: Diego Novillo <dnovillo>
Status: ASSIGNED ---    
Severity: enhancement CC: aph, gcc-bugs, java-prs, mathieu, pinskia, rth
Priority: P2 Keywords: missed-optimization
Version: 4.0.0   
Target Milestone: ---   
Host: Target:
Build: Known to work:
Known to fail: Last reconfirmed: 2006-03-01 02:40:24
Attachments: Initial patch

Description Tom Tromey 2004-05-18 20:42:28 UTC
Diego pointed out on irc today that we could eliminate some
casts by changing the java gimplifier a bit to allow CCP to
do the work for us.

Eg, consider this idiom:

    if (! (x instanceof foo))
      return false;
    foo self = (foo) x;

We could generate code like so:

    int tmp_1 = 0;
    if (! (_Jv_IsInstanceOf (x, &foo.class)) return 0;
    else tmp_1 = 1;

    foo self = tmp_1 ? (foo) x : _Jv_CheckCast (x, &foo.class);

We could do this when generating code for "instanceof" along these lines:
    _Jv_IsInstanceOf(...) ? ({ tmp_1 = 1; 1 }) : 0

With this approach, redundant calls to _Jv_CheckCast would be
automatically eliminated.  Perhaps then we could have an extra
pass to get rid of any remaining temporary variables that we introduced.
Comment 1 Andrew Pinski 2004-05-18 21:08:19 UTC
Confirmed. Actually we generate the following right now for the code you gave which means we do not 
remove the check at all :(

  T.0 = _Jv_IsInstanceOf (x, &foo.class);
  T.1 = !T.0;
  if (T.1)
    {
      return 0B;
    }
  else
    {

    }
  {
    struct foo * self;

    T.2 = _Jv_CheckCast (&foo.class, x);
    self = T.2;
    return self;
  }
Comment 2 Tom Tromey 2004-08-27 20:55:54 UTC
Another approach is not to call _Jv_CheckCast
but to instead turn that into explicit calls
to _Jv_IsInstanceOf and a call to something to
throw the correct exception.  Then if we mark
_Jv_IsInstanceOf as "pure", the optimizers should
be able to eliminate the redundant call.

I have a patch to do this somewhere, I'll upload
it later.
Comment 3 Tom Tromey 2004-09-02 01:26:30 UTC
Created attachment 7019 [details]
Initial patch
Comment 4 Tom Tromey 2004-09-02 01:39:09 UTC
Here's my test case.  This is idiomatic Java code,
the cast is checked but the check is completely redundant
and can be eliminated in theory; that's the goal.

I compiled with:

gcj -c -O3 -fdump-tree-all q.java

{
  int f;
  public boolean equals(Object x)
  {
    if (! (x instanceof q))
      return false;
    q v = (q) x;
    return f == v.f;
  }
}


Before the patch, I seethis in q.java.t60.vars:


;; Function q.equals(java.lang.Object) (_ZN1q6equalsEPN4java4lang6ObjectE)

q.equals(java.lang.Object) (this, x)
{
  int T.2;

<bb 0>:
  if (_Jv_IsInstanceOf (x, &q.class) == 0) goto <L4>; else goto <L1>;

<L4>:;
  T.2 = 0;
  goto <bb 2> (<L2>);

<L1>:;
  T.2 = this->f == _Jv_CheckCast (&q.class, x)->f;

<L2>:;
  return T.2;

}



;; Function () (_ZN1qC1Ev)

() (this)
{
<bb 0>:
  <init> (this) [tail call];
  return;

}


After the patch, q.java.t63.vars:

;; Function q.equals(java.lang.Object) (_ZN1q6equalsEPN4java4lang6ObjectE)

q.equals(java.lang.Object) (this, x)
{
  struct q * iftmp.10;
  int T.6;
  boolean T.3;

<bb 0>:
  T.3 = _Jv_IsInstanceOf (x, &q.class);
  if (x == 0B || !T.3) goto <L11>; else goto <L1>;

<L11>:;
  T.6 = 0;
  goto <bb 7> (<L8>);

<L1>:;
  if (x != 0B) goto <L2>; else goto <L12>;

<L12>:;
  iftmp.10 = 0B;
  goto <bb 6> (<L7>);

<L2>:;
  if (T.3) goto <L3>; else goto <L4>;

<L3>:;
  iftmp.10 = (struct q *) x;
  goto <bb 5> (<L5>);

<L4>:;
  _Jv_ThrowCast (&q.class, x);

<L5>:;

<L7>:;
  T.6 = this->f == iftmp.10->f;

<L8>:;
  return T.6;

}



;; Function () (_ZN1qC1Ev)

() (this)
{
<bb 0>:
  <init> (this) [tail call];
  return;

}

This is an improvement, since we've eliminated an InstanceOf
(the patch works by breaking CheckCast into explicit InstanceOf +
ThrowCast; you won't see the redundant InstanceOf in the first
dump).

With VRP we could also remove the dead call to ThrowCast.
This call is only reached from <L2>, and note earlier that
T.3 is never 0.
Comment 5 Tom Tromey 2005-05-01 00:57:37 UTC
There are a couple more cases where explicit casts can be eliminated.

Code like this will introduce an unneeded cast:

   Object o = "something";
   String s = (String) o;

Of course this is the simplest possible case; I don't know whether
this occurs in real code or not.


Another case is rearranging an array:

   Object[] array = something();
   array[0] = array[1];

This will generate a call to check whether the array can hold the
object, due to the special role arrays play in the type system;
for example this is valid but throws an exception at runtime:

   String[] sarray = ...;
   Object[] oarray = sarray;
   oarray[0] = new Integer(5);

... because Integer can't be cast to String.
In the first array example, we know that the check can be
eliminated because the rhs of the assignment comes from the
same array.

Currently we emit calls to _Jv_CheckArrayStore for this situation.
While we could inline it (making the type check explicit and allowing
elimination in the style of the other parts of this PR), size of the generated
code might be a concern.

Sometimes the precise type of an array is known, for instance if it
is the result of a 'new'.  In this case it would be nice to be able
to eliminate even more checks.