[Bug optimization/13876] loop not fully optimized

[Bug optimization/13876] loop not fully optimized

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-01-27 06:06 -------
This should be able to be done on the tree-ssa.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to fail|                            |2.97 3.0 3.0.1 3.0.2 3.0.3
                   |                            |3.0.4 3.1 3.1.1 3.1.2 3.2
                   |                            |3.2.1 3.2.2 3.2.3 3.3 3.3.1
                   |                            |3.3.2 3.3.3 3.4.0 3.5.0
   Target Milestone|---                         |tree-ssa


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

[Bug optimization/13876] New: loop not fully optimized

[pinskia at gcc dot gnu dot org]

Basically these two functions should produce the same code, the check for NotFound is not needed 
at all.
void g(); void h(); void o();
void t(int l, int *y)
{
int i;
int NotFound;
o();
for(i = 0, NotFound = 1;NotFound && i<l;i++)
{  if (y[i])  { NotFound = 0;  g();  } }
h();
}


void t1(int l, int *y)
{
int i;
int NotFound;
o();
for(i = 0, NotFound = 1;NotFound && i<l;i++)
{  if (y[i])  { NotFound = 0;  g();  break; } }
h();
}

-- 
           Summary: loop not fully optimized
           Product: gcc
           Version: tree-ssa
            Status: UNCONFIRMED
          Keywords: pessimizes-code
          Severity: enhancement
          Priority: P2
         Component: optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: pinskia at gcc dot gnu dot org
                CC: dann at godzilla dot ics dot uci dot edu,gcc-bugs at gcc
                    dot gnu dot org


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

[Bug optimization/13876] loop not fully optimized

[pinskia at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |dalej at gcc dot gnu dot org


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

[Bug optimization/13876] loop not fully optimized

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-01-28 22:03 -------
This is a problem with jump threading as if you change the fcuntion t to be:
void t(int l, int *y)
{
  int i;
  int NotFound;
  o();
  for(i = 0, NotFound = 1;i<l;i++)
  {
    if (y[i])  
    {
      NotFound = 0;
      g();
    }
    if (!NotFound)
      break;
  }
  h(NotFound);
}

It works correctly but changing it to:
void t(int l, int *y)
{
  int i;
  int NotFound;
  o();
  for(i = 0, NotFound = 1;i<l;i++)
  {
    if (!NotFound)
      break;
    if (y[i])  
    {
      NotFound = 0;
      g();
    }
  }
  h(NotFound);
}
It does not.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |law at gcc dot gnu dot org
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
   Last reconfirmed|0000-00-00 00:00:00         |2004-01-28 22:03:27
               date|                            |


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

[Bug optimization/13876] loop not fully optimized

[law at redhat dot com]

------- Additional Comments From law at redhat dot com  2004-01-29 22:14 -------
Subject: Re:  loop not fully optimized 

In message <20040128220328.24048.qmail@sources.redhat.com>, "pinskia at gcc dot
 gnu dot org" writes:
 >
 >------- Additional Comments From pinskia at gcc dot gnu dot org  2004-01-28 2
 >2:03 -------
 >This is a problem with jump threading as if you change the fcuntion t to be:
 >void t(int l, int *y)
 >{
 >  int i;
 >  int NotFound;
 >  o();
 >  for(i = 0, NotFound = 1;i<l;i++)
 >  {
 >    if (y[i])  
 >    {
 >      NotFound = 0;
 >      g();
 >    }
 >    if (!NotFound)
 >      break;
 >  }
 >  h(NotFound);
 >}
 >
 >It works correctly but changing it to:
 >void t(int l, int *y)
 >{
 >  int i;
 >  int NotFound;
 >  o();
 >  for(i = 0, NotFound = 1;i<l;i++)
 >  {
 >    if (!NotFound)
 >      break;
 >    if (y[i])  
 >    {
 >      NotFound = 0;
 >      g();
 >    }
 >  }
 >  h(NotFound);
 >}
 >It does not.
Right.  This is actually something I had already started looking at and
addressing it is going to be a reasonable amount of work.

To correctly handle this we need to record temporary equivalences for
every PHI we pass through during the dominator walk so that a temporary
equivalence created by a PHI in an earlier block can be used to thread
through a later block.  Right now we only record temporary equivalences
for the PHI in the block we want to thread through.

If we look at the dump if your code we have:

  # BLOCK 0
  # PRED: ENTRY [100.0%]  (fallthru,exec)
  #   MT.4_17 = VDEF <MT.4_16>;
  o ();
  goto <bb 5> (<L4>);
  # SUCC: 5 [100.0%]  (fallthru,exec)

  # BLOCK 1
  # PRED: 5 [95.0%]  (true,exec)
<L0>:;
  if (NotFound_3 == 0) goto <L5>; else goto <L1>;
  # SUCC: 2 [95.0%]  (false,exec) 6 [5.0%]  (true,exec)

  # BLOCK 2
  # PRED: 1 [95.0%]  (false,exec)
<L1>:;
  i.0_7 = (unsigned int)i_1;
  T.1_8 = i.0_7 * 4;
  T.2_10 = T.1_8 + y_9;
  #   VUSE <MT.4_15>;
  T.3_11 = *T.2_10;
  if (T.3_11 != 0) goto <L2>; else goto <L3>;
  # SUCC: 4 [70.0%]  (false,exec) 3 [30.0%]  (true,exec)

  # BLOCK 3
  # PRED: 2 [30.0%]  (true,exec)
<L2>:;
  #   MT.4_19 = VDEF <MT.4_15>;
  g ();
  # SUCC: 4 [100.0%]  (fallthru,exec)

  # BLOCK 4
  # PRED: 2 [70.0%]  (false,exec) 3 [100.0%]  (fallthru,exec)
  # MT.4_14 = PHI <MT.4_15(2), MT.4_19(3)>;
  # NotFound_2 = PHI <NotFound_3(2), 0(3)>;
<L3>:;
  i_12 = i_1 + 1;
  # SUCC: 5 [100.0%]  (fallthru,dfs_back,exec)

  # BLOCK 5
  # PRED: 4 [100.0%]  (fallthru,dfs_back,exec) 0 [100.0%]  (fallthru,exec)
  # MT.4_15 = PHI <MT.4_17(0), MT.4_14(4)>;
  # NotFound_3 = PHI <1(0), NotFound_2(4)>;
  # i_1 = PHI <0(0), i_12(4)>;
<L4>:;
  if (i_1 < l_6) goto <L0>; else goto <L5>;
  # SUCC: 6 [5.0%]  (false,exec) 1 [95.0%]  (true,exec)

  # BLOCK 6
  # PRED: 5 [5.0%]  (false,exec) 1 [5.0%]  (true,exec)
<L5>:;
  #   MT.4_18 = VDEF <MT.4_15>;
  h (NotFound_3);
  return;
  # SUCC: EXIT [100.0%]

}

We need to record a temporary equivalence NotFound_3 = 0 when we start
processing block #5 so that we can use that equivalence to eliminate
the test in block #1.

To do this effectively we really need a temporary equivalence table which
is maintained through the dominator walk for the sole use by the jump
threader -- these equivalences can't be used for const/copy propagation
for example since they are specific to a particular path through the
dominator tree.

Note this will not fix the first testcase you mention in the PR -- something
more complex is necessary to analyze the behavior of NotFound.  See "Beyond
Induction Variables" from Gerlek, Stolz & Wolfe -- IIRC their analysis would
be able to determine the behavior of NotFound in the loop and optimize
the code appropriately.  I think everyone would agree that having the kind of
analysis mentioned in that paper needs to be on the "plan".


jeff



-- 


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

[Bug tree-optimization/13876] loop not fully optimized

[pinskia at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|3.5.0                       |---


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

[Bug tree-optimization/13876] loop not fully optimized

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-05-07 18:52 -------
The orginal testcase in comment #0 is fixed now but not the one in comment #2.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|2005-04-16 17:31:17         |2005-05-07 18:52:59
               date|                            |


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