[Bug optimization/13835] New: [tree-ssa] Several loops detected instead of a single one

[Bug optimization/13835] New: [tree-ssa] Several loops detected instead of a single one

[spop at gcc dot gnu dot org]

Hi, 

That's another bug I'm seeing after the merge of the tree-ssa to lno from 
2004-01-20.  I cannot fix the following testcast from the scalar evolution
analysis testsuite:

-----------------------------------------------
bool foo (int);

int main (void)
{
  int a = -100;
  int b = 2;
  int c = 3;
  
  while (a)
    {
      /* Exercises if-phi-nodes.  */
      if (foo (a))
	a += b;
      else
	a += c;
      
      b++;
      c++;
    }
}
-----------------------------------------------

because instead of having a single loop as everybody would have expected, 
for the above snipet, I get two nested loops.  I suspect the dom-pass, 
for having unsafely transformed the program, but that's just a guess.
I haven't investigated the real causes of this bug yet.  

The following representation has been dumped using the usual debug_loop_ir ()

loop_0
{
  bb_0 (preds = {bb_-1}, succs = {bb_2})
  {
  <bb 0>:
    goto <bb 2> (<L1>);

  }
  bb_5 (preds = {bb_4}, succs = {bb_-2})
  {
  <L5>:;
    return;

  }
  loop_1
  {
    bb_6 (preds = {bb_1}, succs = {bb_2})
    {
    <L6>:;

    }
    bb_2 (preds = {bb_6, bb_0}, succs = {bb_4})
    {
      # c_22 = PHI <3(0), c_35(6)>;
      # b_4 = PHI <2(0), b_34(6)>;
      # a_3 = PHI <-100(0), a_2(6)>;
    <L1>:;
      a_33 = a_3 + b_4;
      goto <bb 4> (<L3>);

    }
    loop_2
    {
      bb_1 (preds = {bb_4}, succs = {bb_3, bb_6})
      {
      <L0>:;
        if (a_2 <= 29) goto <L6>; else goto <L2>;

      }
      bb_3 (preds = {bb_1}, succs = {bb_4})
      {
      <L2>:;
        a_36 = a_2 + c_35;

      }
      bb_4 (preds = {bb_3, bb_2}, succs = {bb_5, bb_1})
      {
        # c_23 = PHI <c_22(2), c_35(3)>;
        # b_1 = PHI <b_4(2), b_34(3)>;
        # a_2 = PHI <a_33(2), a_36(3)>;
      <L3>:;
        b_34 = b_1 + 1;
        c_35 = c_23 + 1;
        if (a_2 != 0) goto <L0>; else goto <L5>;

      }
    }
  }
}

-- 
           Summary: [tree-ssa] Several loops detected instead of a single
                    one
           Product: gcc
           Version: tree-ssa
            Status: UNCONFIRMED
          Severity: critical
          Priority: P2
         Component: optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: spop at gcc dot gnu dot org
                CC: gcc-bugs at gcc dot gnu dot org


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

[Bug optimization/13835] [tree-ssa] Several loops detected instead of a single one

[pinskia at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |tree-ssa


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

[Bug optimization/13835] [tree-ssa] Several loops detected instead of a single one

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-01-24 03:37 -------
Confirmed, again this is caused by the jump threading which is causing extra memory 
problems and forgeting to update PHI's.  I think jump threading should not do jumps for 
loops at all and let loop header duplication do its work.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
           Keywords|                            |memory-hog
   Last reconfirmed|0000-00-00 00:00:00         |2004-01-24 03:37:39
               date|                            |


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

[Bug optimization/13835] [tree-ssa] Several loops detected instead of a single one

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-03-07 09:28 -------
Still an issue:
Created preheader block for loop 2
;; 3 loops found, 3 levels
;;
;; Loop 0:
;;  header -1, latch -2, pre-header -1
;;  depth 0, level 3, outer -1
;;  nodes: -1 0 1 4 2 3 8 7 5 6 -2
;;
;; Loop 1:
;;  header 3, latch 2, pre-header -1
;;  depth 1, level 2, outer 0
;;  nodes: 3 2 6 1 7 8 4
;;
;; Loop 2:
;;  header 7, latch 8, pre-header -1
;;  depth 2, level 1, outer 1
;;  nodes: 7 8 6
;; 0 succs { 3 }
;; 1 succs { 4 2 }
;; 4 succs { 7 }
;; 2 succs { 3 }
;; 3 succs { 1 5 }
;; 8 succs { 7 }
;; 7 succs { 5 6 }
;; 5 succs { -2 }
;; 6 succs { 2 8 }

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|2004-01-24 03:37:39         |2004-03-07 09:28:37
               date|                            |


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

[Bug optimization/13835] [tree-ssa] Several loops detected instead of a single one

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-03-16 00:21 -------
Actually it has nothing to do with the header at all.
The issue is more that DOM created two loops as it dected a >=29, a is always positive 
as b and c will always be positive.  This is not true for -fwrapv but that is off by default for 
C.
I do not see this as wrong code because there is too loops and DOM is right here.  The 
real problem is that the two loops are independent but loop dectection is not decting 
them.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|critical                    |normal
           Keywords|memory-hog                  |
   Target Milestone|tree-ssa                    |lno


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

[Bug tree-optimization/13835] [tree-ssa] Several loops detected instead of a single one

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-08-12 06:42 -------
Fixed:
;; Function main (main)

;; 2 loops found, 2 levels
;;
;; Loop 0:
;;  header -1, latch -2, pre-header -1
;;  depth 0, level 2, outer -1
;;  nodes: -1 0 1 2 3 4 6 5 -2
;;
;; Loop 1:
;;  header 1, latch 6, pre-header -1
;;  depth 1, level 1, outer 0
;;  nodes: 1 6 4 3 2
;; 0 succs { 1 }
;; 1 succs { 3 2 }
;; 2 succs { 4 }
;; 3 succs { 4 }
;; 4 succs { 5 6 }
;; 6 succs { 1 }
;; 5 succs { -2 }

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |FIXED
   Target Milestone|lno                         |3.5.0


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