[Bug optimization/14627] New: [tree-ssa] extra assignment inserted

[Bug optimization/14627] New: [tree-ssa] extra assignment inserted

[dann at godzilla dot ics dot uci dot edu]

This function:

int foo (int count, int *valid, int *test_val, int val)
{
  int i;
  int one_valid = 0;
  for (i = 0; i < count; i++)
    {
      if (valid[i] && (test_val[i] == val))
        return i;
      else
        if (!one_valid && valid[i])
          one_valid = 1;
    }
  if (one_valid)
    return -2;
  return -1;
}

should not have a "one_valid = 0" assignment in the loop, but it does, see
the .vars dump:

  int one_valid;
  int i;
  int T.4;
  int * T.2;

<bb 0>:
  if (count > 0) goto <L25>; else goto <L12>;

<L25>:;
  i = 0;
  one_valid = 0;

<L0>:;
  T.2 = (int *)((unsigned int)i * 4);
  T.4 = *(T.2 + valid);
  if (T.4 == 0) goto <L3>; else goto <L1>;

<L1>:;
  if (*(T.2 + test_val) != val) goto <L3>; else goto <L2>;

<L2>:;
  return i;

<L3>:;
  if (one_valid == 0) goto <L4>; else goto <L6>;

<L4>:;
  if (T.4 != 0) goto <L5>; else goto <L26>;

<L26>:;
  one_valid = 0;
  goto <bb 7> (<L6>);

<L5>:;
  one_valid = 1;

<L6>:;
  i = i + 1;
  if (i < count) goto <L0>; else goto <L10>;

<L10>:;
  if (one_valid != 0) goto <L11>; else goto <L12>;

<L11>:;
  return -2;

<L12>:;
  return -1;

-- 
           Summary: [tree-ssa] extra assignment inserted
           Product: gcc
           Version: tree-ssa
            Status: UNCONFIRMED
          Severity: normal
          Priority: P2
         Component: optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: dann at godzilla dot ics dot uci dot edu
                CC: gcc-bugs at gcc dot gnu dot org


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

[Bug optimization/14627] [tree-ssa] extra assignment inserted

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-03-18 04:08 -------
Confirmed. I do not know where this is coming from.
It looks like DOM:
<L3>:;
  if (one_valid_2 == 0) goto <L4>; else goto <L6>;

<L4>:;
  if (T.4_14 != 0) goto <L5>; else goto <L6>;

<L5>:;

  # one_valid_1 = PHI <0(5), one_valid_2(4), 1(6)>;
See how the PHI has both 0 and one_valid_2 there when it should have two one_valid_2 and a 1. 

-- 
           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-03-18 04:08:19
               date|                            |
   Target Milestone|---                         |tree-ssa


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

[Bug optimization/14627] [tree-ssa] extra assignment inserted

[dann at godzilla dot ics dot uci dot edu]

------- Additional Comments From dann at godzilla dot ics dot uci dot edu  2004-03-18 18:39 -------
Yep, it seems to be DOM, the extra assignment does not occur with
-fno-tree-dominator-opts. 
It also seems that this issue has been around for a while, it also occurs with an
old gcc version that I have around:
gcc version 3.5-tree-ssa 20031115 (merged 20031111)


-- 


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

[Bug optimization/14627] [tree-ssa] extra assignment inserted

[steven at gcc dot gnu dot org]

------- Additional Comments From steven at gcc dot gnu dot org  2004-03-23 16:07 -------
This way it's a bit smaller: 
 
int foo (int *a, int b) 
{ 
  int i; 
  int one_valid = 0; 
  for (i = 0; i < 10; i++) 
    { 
      if (*a && b) 
        goto done; 
      else 
        if (!one_valid && *a) 
          one_valid = 1; 
    } 
 
done: 
  return one_valid; 
} 
 
When you replace "int *a" with just "int a", the extra assignment isn't there. 
 
 

-- 


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

[Bug optimization/14627] [tree-ssa] extra assignment inserted on the tree level

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-03-23 20:12 -------
The reason for the changing *a to a gets rid of the assignenment is because DOM does 
not work through &&.
Here is a testcase without the && (and is reproducable with a):
int foo (int a, int b)
{
  int i;
  _Bool c = 0;
  for (i = 0; i < 10; i++)
    {
      if (a)
        if (b)
          goto done;
      if (!c){
         if (a)
          c = 1; }
        /*else
          c = 0;*/ //Basically DOM is adding this statement as it knows that c == 0 at this point
             // so it added it to the PHI as 0.
    }

done:
  return c;
}

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |pinskia at gcc dot gnu dot
                   |                            |org
           Severity|normal                      |enhancement
           Keywords|                            |pessimizes-code
            Summary|[tree-ssa] extra assignment |[tree-ssa] extra assignment
                   |inserted                    |inserted on the tree level


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

[Bug tree-optimization/14627] [tree-ssa] extra assignment inserted on the tree level

[pinskia at gcc dot gnu dot org]

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


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

[Bug tree-optimization/14627] [tree-ssa] extra assignment inserted on the tree level

[steven at gcc dot gnu dot org]

------- Additional Comments From steven at gcc dot gnu dot org  2005-03-19 18:58 -------
Actually you can get this from any trivial "implicit set"-like 
code, for example: 
 
int b; 
void foo (int a) { 
        if (a) 
                a = 3; 
        b = a; 
} 
 
The out-of-ssa pass turns that into  
foo (aD.1461) 
{ 
  intD.0 a.0D.1468; 
 
  # BLOCK 0 
  # PRED: ENTRY [100.0%]  (fallthru,exec) 
  if (aD.1461 != 0) goto <L3>; else goto <L2>; 
  # SUCC: 3 [67.0%]  (true,exec) 1 [33.0%]  (false,exec) 
 
  # BLOCK 3 
  # PRED: 0 [67.0%]  (true,exec) 
<L3>:; 
  a.0D.1468 = 3; 
  goto <bb 2> (<L1>); 
  # SUCC: 2 [100.0%]  (fallthru) 
 
  # BLOCK 1 
  # PRED: 0 [33.0%]  (false,exec) 
<L2>:; 
  a.0D.1468 = 0; 
  # SUCC: 2 [100.0%]  (fallthru) 
 
  # BLOCK 2 
  # PRED: 1 [100.0%]  (fallthru) 3 [100.0%]  (fallthru) 
<L1>:; 
  #   bD.1460_4 = V_MUST_DEF <bD.1460_3>; 
  bD.1460 = a.0D.1468; 
  return; 
  # SUCC: EXIT [100.0%] 
 
} 
 
We do not get rid of the "a.0 = 0" set until the first RTL if conversion 
pass. 
(Also note the useless live range splitting of a!) 
 
This is IMHO a little more important than the normal enhancement request,  
so I'm making this a "normal" bug.  Andrew, any comments on this bug??? 
 

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |amacleod at redhat dot com
           Severity|enhancement                 |normal
      Known to fail|                            |4.0.0 4.1.0


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

[Bug tree-optimization/14627] [tree-ssa] extra assignment inserted on the tree level

[steven at gcc dot gnu dot org]

------- Additional Comments From steven at gcc dot gnu dot org  2005-03-19 19:33 -------
FWIW this bug is a major source of ifcvt1 opportunities, so fixing it 
has positive downstream effects too. 

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |stevenb at suse dot de


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

[Bug tree-optimization/14627] [4.0/4.1 regression] extra assignment inserted on the tree level

[steven at gcc dot gnu dot org]

------- Additional Comments From steven at gcc dot gnu dot org  2005-03-20 00:58 -------
int b; 
void foo (int a) { 
        if (a) 
                a = 3; 
        b = a; 
} 
 
GCC 3.3.5 (hammer-branch) on AMD64 -O2: 
 
foo: 
.LFB3: 
        testl   %edi, %edi 
        movl    $3, %eax 
        cmovne  %eax, %edi 
        movl    %edi, b(%rip) 
        ret 
.LFE3: 
 
GCC 4.1.0 20050317 -O2: 
foo: 
.LFB2: 
        cmpl    $1, %edi 
        sbbl    %eax, %eax 
        notl    %eax 
        andl    $3, %eax 
        movl    %eax, b(%rip) 
        ret 
.LFE2: 
 
GCC 4.1.0 20050317 -O2 -fno-tree-dominator-opts: 
foo: 
.LFB2: 
        testl   %edi, %edi 
        movl    $3, %eax 
        cmovne  %eax, %edi 
        movl    %edi, b(%rip) 
        ret 
.LFE2: 
 
 
This really is DOM's doing, as already mentioned in comment #1.  It pushes 
the constants into the PHI nodes as PHI arguments. 
 
Why do we allow constants as PHI arguments?  I do not see any easy way to 
avoid inserting an assignment that was not there in the original code.  And 
as my example above showed, we never again get rid of the assignment either. 
 
Technically this is even a regression from GCC 3.3 and GCC 3.4. 
 

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[tree-ssa] extra assignment |[4.0/4.1 regression] extra
                   |inserted on the tree level  |assignment inserted on the
                   |                            |tree level


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

[Bug tree-optimization/14627] [4.0/4.1 regression] extra assignment inserted on the tree level

[amacleod at redhat dot com]

------- Additional Comments From amacleod at redhat dot com  2005-03-21 15:52 -------
Well, I dont think there is anything out of ssa should do here. a_1 and a_2 are
2 distinct live ranges, and should therefore be generated that way.  There isnt
much choice about the 2 assignments either. 

Perhaps the best thing would be a pass before out of ssa which does the opposite
of that DOM optimization. It goes through the program looking for these
equivilences, and replaces the constant with the variable its equivilent to.

  if (a_2 != 0) goto <L1>; else goto <L2>;
<L2>:;
  # a_1 = PHI <0(1), 3(0)>;
<L1>:;
  #   b_4 = V_MUST_DEF <b_3>;
  b = a_1;
  return;

the PHI could then be turned into:
  # a_1 = PHI <a_2(1), 3(0)>

which would result in code closer to what you are looking for. It would undo
anything that wasn't profitable, and we're likely to get better code in general
I would think. It would also take care of when that assignment to zero was
explcitly made instead of implicit. Simply disabling/handcuffing DOM or other
optimizations to prevent the situation wouldn't help then.


It would also get the original case:

<L3>:;
  if (one_valid_9 == 0) goto <L4>; else goto <L6>; <L4>:;

  if (D.1132_16 != 0) goto <L6>; else goto <L23>; <L23>:;

  # one_valid_21 = PHI <one_valid_9(3), 0(5), 1(4)>;

It can tell that one_valid_9 is implicitly 0 from block 5, and change this back to :
<L3>:;
  if (one_valid_9 == 0) goto <L4>; else goto <L6>; <L4>:;

  if (D.1132_16 != 0) goto <L6>; else goto <L23>; <L23>:;

  # one_valid_21 = PHI <one_valid_9(3), one_valid_9(5), 1(4)>;
                                        ^^^^^^^^^^^

Just what we need, more DOM eh :-) This is kinda anti-DOM :-)

We would simply be focusing on constants in the PHI arguments and looking to 
replace them, when possible, with an implicit value of an ssa version of the PHI
result.  There isnt much point to changing it to a different variable since you
will still get an assignment.  There also may not be much point in using an SSA
version which isnt already in the argument list of the PHI sometimes. You might
create a new overlapping live range, which could cause even more havoc.  So its
pretty specialized.  I would think it would be fairly quick.

Your other choice would be a post-ssa pass which works with memory variables and
tries to propagate copies around. It should be pretty trivial to replace the
output from your sample program to get:

<bb 0>:
  if (a != 0) goto <L3>; else goto <L2>;
<L3>:;
  b = 3;
  goto <bb 2> (<L1>);
<L2>:;
  b = 0;
<L1>:;
  return;

It would, however, miss the original test cases problem.

-- 


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

[Bug tree-optimization/14627] [4.0/4.1 regression] extra assignment inserted on the tree level

[stevenb at suse dot de]

------- Additional Comments From stevenb at suse dot de  2005-03-21 16:51 -------
Subject: Re:  [4.0/4.1 regression] extra assignment inserted on the tree level

On Mar 21, 2005 04:53 PM, amacleod at redhat dot com > Perhaps the best thing would be a pass before out of ssa which does the opposite
> of that DOM optimization.

Wouldn't it be much easier to just disallow GIMPLE invariants
as PHI arguments?



-- 


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

[Bug tree-optimization/14627] [4.0/4.1 regression] extra assignment inserted on the tree level

[law at redhat dot com]

------- Additional Comments From law at redhat dot com  2005-03-21 17:20 -------
Subject: Re:  [4.0/4.1 regression] extra
	assignment inserted on the tree level

On Mon, 2005-03-21 at 15:53 +0000, amacleod at redhat dot com wrote:
> ------- Additional Comments From amacleod at redhat dot com  2005-03-21 15:52 -------
> Well, I dont think there is anything out of ssa should do here. a_1 and a_2 are
> 2 distinct live ranges, and should therefore be generated that way.  There isnt
> much choice about the 2 assignments either. 
> 
> Perhaps the best thing would be a pass before out of ssa which does the opposite
> of that DOM optimization. It goes through the program looking for these
> equivilences, and replaces the constant with the variable its equivilent to.
Kind-of funny.  I've got code somewhere around here which does that
which I put on my 4.1 queue :-)

What the code does is a domwalk recording a reverse mapping of
equivalences created by conditionals.  When we encounter a PHI
node where the argument is either a constant or an SSA_NAME
with a different underlying variable than the PHI result, we
lookup the argument in our table of reverse equivalences and
see which (if any) of the equivalences would be a better choice
than the current PHI argument.

This would allow us to kill the current code which runs after
we go out of SSA form which tries to eliminate the constant loads
and copies in arms of conditionals.

Finding the code might be a PITA (it was many many months ago), it
might be easier to just recreate it again -- it wasn't terribly
complicated, and it did a pretty decent job at eliminating constant
loads and some copies.
jeff



-- 


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

[Bug tree-optimization/14627] [4.0/4.1 regression] extra assignment inserted on the tree level

[law at redhat dot com]

------- Additional Comments From law at redhat dot com  2005-03-21 17:22 -------
Subject: Re:  [4.0/4.1 regression] extra
	assignment inserted on the tree level

On Mon, 2005-03-21 at 16:51 +0000, stevenb at suse dot de wrote:
> ------- Additional Comments From stevenb at suse dot de  2005-03-21 16:51 -------
> Subject: Re:  [4.0/4.1 regression] extra assignment inserted on the tree level
> 
> On Mar 21, 2005 04:53 PM, amacleod at redhat dot com > Perhaps the best thing would be a pass before out of ssa which does the opposite
> > of that DOM optimization.
> 
> Wouldn't it be much easier to just disallow GIMPLE invariants
> as PHI arguments?
It would be easier, but it would be a step backwards in terms of
optimizations and our ability to subsume the bulk of CSE.

We could disallow this kind of propagation if the equivalency came
from following a conditional.  That would be a smaller step backards,
but I believe if you look at the anti-dom/unpropagation approach that
Andrew and I mentioned you'll get the best of both worlds.

jeff




-- 


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

[Bug tree-optimization/14627] [4.0/4.1 regression] extra assignment inserted on the tree level

[law at redhat dot com]

------- Additional Comments From law at redhat dot com  2005-04-13 04:55 -------
Should be fixed now.

-- 


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

[Bug tree-optimization/14627] [4.0/4.1 regression] extra assignment inserted on the tree level

[steven at gcc dot gnu dot org]

------- Additional Comments From steven at gcc dot gnu dot org  2005-04-24 14:22 -------
Jeff, "should be fixed now" is not helpful.  Either it is fixed, so you 
should close the bug, or it is not, in which case your remark would not 
be true. 
 
Also, when you commit a patch that fixes a PR, you should mention the PR 
number in the ChangeLog. 
 
But you know all this.  Too bad you don't follow this practice  :-( 
 
Closing as FIXED. 
 

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |FIXED


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

[Bug tree-optimization/14627] [4.0/4.1 regression] extra assignment inserted on the tree level

[pinskia at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |4.1.0


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

[Bug tree-optimization/14627] [4.0/4.1 regression] extra assignment inserted on the tree level

[law at redhat dot com]

------- Additional Comments From law at redhat dot com  2005-04-24 15:31 -------
Subject: Re:  [4.0/4.1 regression] extra
	assignment inserted on the tree level

On Sun, 2005-04-24 at 14:22 +0000, steven at gcc dot gnu dot org wrote:
> ------- Additional Comments From steven at gcc dot gnu dot org  2005-04-24 14:22 -------
> Jeff, "should be fixed now" is not helpful.  Either it is fixed, so you 
> should close the bug, or it is not, in which case your remark would not 
> be true. 
I've never been able to close bugs unless they were assigned to me. 
Otherwise I would.

jeff




-- 


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

[Bug tree-optimization/14627] [4.0/4.1 regression] extra assignment inserted on the tree level

[dberlin at dberlin dot org]

------- Additional Comments From dberlin at gcc dot gnu dot org  2005-04-24 19:13 -------
Subject: Re:  [4.0/4.1 regression] extra
	assignment inserted on the tree level

On Sun, 2005-04-24 at 15:31 +0000, law at redhat dot com wrote:
> ------- Additional Comments From law at redhat dot com  2005-04-24 15:31 -------
> Subject: Re:  [4.0/4.1 regression] extra
> 	assignment inserted on the tree level
> 
> On Sun, 2005-04-24 at 14:22 +0000, steven at gcc dot gnu dot org wrote:
> > ------- Additional Comments From steven at gcc dot gnu dot org  2005-04-24 14:22 -------
> > Jeff, "should be fixed now" is not helpful.  Either it is fixed, so you 
> > should close the bug, or it is not, in which case your remark would not 
> > be true. 
> I've never been able to close bugs unless they were assigned to me. 
> Otherwise I would.
> 
> jeff

You probably should have mentioned this to me at some point.
Once steven did on IRC, i just went and fixed it.
	
> 
> 
> 
> 



-- 


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