Bug 20132 - Pessimization of induction variable and missed hoisting opportunity
Summary: Pessimization of induction variable and missed hoisting opportunity
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: tree-optimization (show other bugs)
Version: unknown
: P2 enhancement
Target Milestone: 4.1.0
Assignee: Not yet assigned to anyone
URL:
Keywords: missed-optimization, TREE
Depends on:
Blocks: 19721
  Show dependency treegraph
 
Reported: 2005-02-21 23:51 UTC by Kazu Hirata
Modified: 2005-03-11 19:59 UTC (History)
2 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2005-02-22 00:12:02


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Kazu Hirata 2005-02-21 23:51:45 UTC
Consider:

int
foo (int length, const char *fmt)
{
  int i;
  for (i = length; i >= 0; i--)
    {
      switch (fmt[i])
        {
        case 48:
          break;
        default:
          return 1;
        }
    }
  return 0;
}

I get:

foo (length, fmt)
{
  unsigned int D.1180;
  unsigned int ivtmp.5;
  int D.1146;

<bb 0>:
  if (length >= 0) goto <L15>; else goto <L6>;

<L15>:;
  ivtmp.5 = 0;

<L0>:;
  D.1180 = (unsigned int) length;
  switch (*((const char *) ivtmp.5 + fmt + (const char *) D.1180))
    {
      case 48: goto <L1>;
      default : goto <L16>;
    }

<L16>:;
  D.1146 = 1;
  goto <bb 6> (<L17>);

<L1>:;
  ivtmp.5 = ivtmp.5 - 1;
  if (ivtmp.5 != D.1180 * 0ffffffff + 0ffffffff) goto <L0>; else goto <L6>;

<L6>:;
  D.1146 = 0;

<L17>:;
  return D.1146;

}

The following should be hoisted out of the loop.

  D.1180 = (unsigned int) length;

This

  D.1180 * 0ffffffff + 0ffffffff

should be folded to

  ~D.1180

and of course hoisted out of the loop.

The folding part is also mentioned in PR 20130.

RTL optimizers hoist ~D.1180 out of the loop.

Having said all this, the induction variable should be counting down toward 0.

That is, instead of

  ivtmp.5 = 0;
  :
  :
  switch (*((const char *) ivtmp.5 + fmt + (const char *) D.1180))
  :
  :
  ivtmp.5 = ivtmp.5 - 1;
  if (ivtmp.5 != D.1180 * 0ffffffff + 0ffffffff) goto <L0>; else goto <L6>;

we should be doing

  ivtmp.5 = (unsigned int) D.1180;
  :
  :
  switch (*((const char *) ivtmp.5 + fmt))
  :
  :
  ivtmp.5 = ivtmp.5 - 1;
  if (ivtmp.5 >= 0) goto <L0>; else goto <L6>;

This way, we don't have to keep D.1180 in the loop.
And we can compare against 0 at the end.
Comment 1 Andrew Pinski 2005-02-22 00:12:02 UTC
Confirmed.
Comment 2 James A. Morrison 2005-03-11 05:14:16 UTC
I think this is fixed.  This is my tree dump with my patches to 20130 and 15784:
;; Function foo (foo)

foo (length, fmt)
{
  int D.1243;
  int i;
  int D.1225;

<bb 0>:
  if (length >= 0) goto <L15>; else goto <L6>;

<L15>:;
  i = length;

<L0>:;
  switch (*((const char *) (long unsigned int) i + fmt))
    {
      case 48: goto <L3>;
      default : goto <L16>;
    }

<L16>:;
  D.1225 = 1;
  goto <bb 6> (<L17>);

<L3>:;
  i = i - 1;
  D.1243 = -000000001;
  if (i != D.1243) goto <L0>; else goto <L6>;

<L6>:;
  D.1225 = 0;

<L17>:;
  return D.1225;

}

Comment 3 Andrew Pinski 2005-03-11 19:59:29 UTC
Confirmed fixed for me too so closing as such.  I think we choose better iv with the fold patches 
installed.