[Bug tree-optimization/34244] New: [4.3 Regression] VRP/SCEV miscompiles Firefox

["rguenth at gcc dot gnu dot org" <gcc-bugzilla at gcc dot gnu dot org>]

int* GetParent(void);
int* FindCommonAncestor(int *aNode1, int *aNode2)
{
  if (aNode1 && aNode2) {
    int offset = 0; 
    int *anc1 = aNode1;
    for (;;) {
      ++offset;
      int * parent = GetParent();
      if (!parent)
        break;
      anc1 = parent;
    }
    int *anc2 = aNode2;
    for (;;) { 
      --offset;
      int * parent = GetParent();
      if (!parent)
        break;
      anc2 = parent;
    }
    if (anc1 == anc2) {
      anc1 = aNode1;
      anc2 = aNode2;
      while (offset > 0) {
        anc1 = GetParent();
        --offset;
      }
      while (offset < 0) {
        anc2 = GetParent();
        ++offset;
      }
      while (anc1 != anc2) {
        anc1 = GetParent();
        anc2 = GetParent();
      }
      return anc1;
    }
  }
  return 0;
}

Folding predicate offset_5 < 0 to 0
Folded statement: if (offset_5 < 0)
            into: if (0)

that is, the second last loop is never executed according to VRP/SCEV because
the exit value of the third last loop

<bb 26>:
  offset_48 = ASSERT_EXPR <offset_4, offset_4 <= 0>;

is adjusted to [0, 0] by SCEV:

Visiting statement:
offset_48 = ASSERT_EXPR <offset_4, offset_4 <= 0>;

(analyze_scalar_evolution
  (loop_nb = 0)
  (scalar = offset_48)
(get_scalar_evolution
  (scalar = offset_48)
  (scalar_evolution = ))
(analyze_scalar_evolution
  (loop_nb = 0)
  (scalar = offset_4)
(get_scalar_evolution
  (scalar = offset_4)
  (scalar_evolution = ))
(analyze_initial_condition
  (loop_phi_node =
offset_4 = PHI <offset_37(10), offset_32(9)>)
  (init_cond = offset_37))
(analyze_evolution_in_loop
  (loop_phi_node = offset_4 = PHI <offset_37(10), offset_32(9)>)
(add_to_evolution
  (loop_nb = 3)
  (chrec_before = offset_37)
  (to_add = -1)
  (res = {offset_37, +, -1}_3))
  (evolution_function = {offset_37, +, -1}_3))
(set_scalar_evolution
  (scalar = offset_4)
  (scalar_evolution = {offset_37, +, -1}_3))
(number_of_iterations_in_loop
(analyze_scalar_evolution
  (loop_nb = 3)
  (scalar = offset_4)
(get_scalar_evolution
  (scalar = offset_4)
  (scalar_evolution = {offset_37, +, -1}_3))
(set_scalar_evolution
  (scalar = offset_4)
  (scalar_evolution = {offset_37, +, -1}_3))
)
(analyze_scalar_evolution
  (loop_nb = 3)
  (scalar = 0)
(get_scalar_evolution
  (scalar = 0)
  (scalar_evolution = 0))
)
Analyzing # of iterations of loop 3
  exit condition 0 < [offset_46, + , -1](no_overflow)
  bounds on difference of bases: -2147483648 ... 2147483647
  result:
    # of iterations (unsigned int) offset_46, bounded by 2147483647
  (set_nb_iterations_in_loop = (unsigned int) offset_46))
(chrec_apply 
  (varying_loop = 3
) 
  (chrec = {offset_37, +, -1}_3)
  (x = offset_46)
  (res = offset_37 - offset_46))
(analyze_scalar_evolution
  (loop_nb = 0)
  (scalar = offset_37)
(get_scalar_evolution 
  (scalar = offset_37)
  (scalar_evolution = ))
(analyze_scalar_evolution
  (loop_nb = 0)
  (scalar = offset_46)
(get_scalar_evolution 
  (scalar = offset_46)
  (scalar_evolution = ))
(analyze_scalar_evolution
  (loop_nb = 0)
  (scalar = offset_24)
(get_scalar_evolution 
  (scalar = offset_24)
  (scalar_evolution = {offset_40 + -1, +, -1}_2))
(number_of_iterations_in_loop
(analyze_scalar_evolution
  (loop_nb = 2)
  (scalar = parent_25)
(get_scalar_evolution 
  (scalar = parent_25)
  (scalar_evolution = parent_25))
(set_scalar_evolution 
  (scalar = parent_25)
  (scalar_evolution = parent_25))
)
(analyze_scalar_evolution
  (loop_nb = 2)
  (scalar = parent_25)
(get_scalar_evolution 
  (scalar = parent_25)
  (scalar_evolution = parent_25))
(set_scalar_evolution 
  (scalar = parent_25)
  (scalar_evolution = parent_25))
) 
  (set_nb_iterations_in_loop = scev_not_known))
)
(set_scalar_evolution 
  (scalar = offset_46)
  (scalar_evolution = offset_24))
)
(set_scalar_evolution 
  (scalar = offset_37)
  (scalar_evolution = offset_24))
)
(analyze_scalar_evolution
  (loop_nb = 0)
  (scalar = offset_46)
(get_scalar_evolution
  (scalar = offset_46)
  (scalar_evolution = offset_24))
(set_scalar_evolution
  (scalar = offset_46)
  (scalar_evolution = offset_24))
)
)
(set_scalar_evolution
  (scalar = offset_48)
  (scalar_evolution = 0))
)
(instantiate_parameters
  (loop_nb = 0)
  (chrec = 0)
  (res = 0))
Found new range for offset_48: [0, 0]

where the particular error looks like this:

Analyzing # of iterations of loop 3
  exit condition 0 < [offset_46, + , -1](no_overflow)
  bounds on difference of bases: -2147483648 ... 2147483647
  result:
    # of iterations (unsigned int) offset_46, bounded by 2147483647
  (set_nb_iterations_in_loop = (unsigned int) offset_46))

as it may be zero, in case offset_46 is <= 0.

Sebastian, Zdenek - any idea what goes wrong here?


-- 
           Summary: [4.3 Regression] VRP/SCEV miscompiles Firefox
           Product: gcc
           Version: 4.3.0
            Status: UNCONFIRMED
          Keywords: wrong-code
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: rguenth at gcc dot gnu dot org


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