[Bug c++/32367] New: internal compiler error: in build_polynomial_chrec, at tree-chrec.h:113

[Bug c++/32367] New: internal compiler error: in build_polynomial_chrec, at tree-chrec.h:113

[ubizjak at gmail dot com]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1026 bytes --]

This happens when compiling povray-3.6.1 with gcc version 4.3.0 20070616
(experimental). The testcase (reduced with delta) is attached to the report.

g++ -O2 xxx.cpp
xxx.cpp: In function ‘double pov::Evaluate_TPat(pov::TPATTERN*, double*,
pov::INTERSECTION*)’:
xxx.cpp:146: internal compiler error: in build_polynomial_chrec, at
tree-chrec.h:113
Please submit a full bug report,
with preprocessed source if appropriate.
See <URL:http://gcc.gnu.org/bugs.html> for instructions.


-- 
           Summary: internal compiler error: in build_polynomial_chrec, at
                    tree-chrec.h:113
           Product: gcc
           Version: 4.3.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: ubizjak at gmail dot com
 GCC build triplet: x86_64-pc-linux-gnu
  GCC host triplet: x86_64-pc-linux-gnu
GCC target triplet: x86_64-pc-linux-gnu


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

[Bug c++/32367] internal compiler error: in build_polynomial_chrec, at tree-chrec.h:113

[ubizjak at gmail dot com]

------- Comment #1 from ubizjak at gmail dot com  2007-06-16 16:58 -------
Created an attachment (id=13713)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=13713&action=view)
reduced testcase


-- 


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

[Bug tree-optimization/32367] [4.3 Regression] internal compiler error: in build_polynomial_chrec, at tree-chrec.h:113

[pinskia at gcc dot gnu dot org]

------- Comment #2 from pinskia at gcc dot gnu dot org  2007-06-16 17:21 -------
This was caued by me.


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |pinskia at gcc dot gnu dot
                   |                            |org
          Component|c++                         |tree-optimization
           Keywords|                            |ice-on-valid-code
            Summary|internal compiler error: in |[4.3 Regression] internal
                   |build_polynomial_chrec, at  |compiler error: in
                   |tree-chrec.h:113            |build_polynomial_chrec, at
                   |                            |tree-chrec.h:113
   Target Milestone|---                         |4.3.0


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

[Bug tree-optimization/32367] [4.3 Regression] internal compiler error: in build_polynomial_chrec, at tree-chrec.h:113

[pinskia at gcc dot gnu dot org]

------- Comment #3 from pinskia at gcc dot gnu dot org  2007-06-16 20:03 -------
The chrec is
{{&BinomialCoefficients[0], +, 4}_1, +, {0, +, 4}_1}_1

Which looks ok and correct.

the comment before chrec_component_in_loop_num, says:
/* Returns the evolution part of CHREC in LOOP_NUM when RIGHT is
   true, otherwise returns the initial condition in LOOP_NUM.  */


So the initialize condition here is &BinomialCoefficients[0] p+ 0.

I guess this part needs a fixing.

Note we get in build_polynomial_chrec:
(gdb) p debug_generic_expr (left)
&BinomialCoefficients[0]
$16 = void
(gdb) p debug_generic_expr (right)
{&BinomialCoefficients[0], +, 4}_1

Which does not make sense at all, since we are going to create:
{&BinomialCoefficients[0], +, {&BinomialCoefficients[0], +, 4}_1 }_1

So that means the initialize condition that returns is:
&BinomialCoefficients[0] + &BinomialCoefficients[0]

Which really does not makes any sense at all.

So I just exposed a latent bug in chrec_component_in_loop_num.


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2007-06-16 20:03:48
               date|                            |


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

[Bug tree-optimization/32367] [4.3 Regression] internal compiler error: in build_polynomial_chrec, at tree-chrec.h:113

[pinskia at gcc dot gnu dot org]

------- Comment #4 from pinskia at gcc dot gnu dot org  2007-06-16 20:31 -------
Here is a reduced testcase:
int BinomialCoefficients[17 * 35];
void InitializeBinomialCoefficients ()
{
  unsigned n, k;
  int *ptr = BinomialCoefficients;
  for ( n = 1; n <= 33; ++n)
    {
      for ( k = 1; k < n; ++k)
        ++ptr;
      *ptr = 1;
    }
}


-- 


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

[Bug tree-optimization/32367] [4.3 Regression] internal compiler error: in build_polynomial_chrec, at tree-chrec.h:113

[pinskia at gcc dot gnu dot org]

------- Comment #5 from pinskia at gcc dot gnu dot org  2007-06-16 20:40 -------
Actually I reduced it a little too far (I had fixed the ICE in one case but was
reducing another ICE):
int BinomialCoefficientsInited = 0;
int BinomialCoefficients[17 * 35];
double Evaluate_TPat (void)
{
        unsigned n, k;
        if (BinomialCoefficientsInited == 0)
        {
                int *ptr = BinomialCoefficients;
                for (n = 1; n <= 33; ++n)
                {
                        for (k = 1; k < n; ++k)
                                ++ptr;
                        *ptr = 1;
                }
        }    
}


-- 


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

[Bug tree-optimization/32367] [4.3 Regression] internal compiler error: in build_polynomial_chrec, at tree-chrec.h:113

[pinskia at gcc dot gnu dot org]

------- Comment #6 from pinskia at gcc dot gnu dot org  2007-06-16 20:55 -------
This patch works for me (and I think it is correct):
Index: tree-chrec.c
===================================================================
--- tree-chrec.c        (revision 125757)
+++ tree-chrec.c        (working copy)
@@ -712,6 +712,10 @@
          else
            component = CHREC_LEFT (chrec);

+         if (!right && TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC
+             && CHREC_VARIABLE (CHREC_LEFT (chrec)) == CHREC_VARIABLE (chrec))
+           return chrec_component_in_loop_num (CHREC_LEFT (chrec), loop_num,
right);
+
          if (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
              || CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec))
            return component;


-- 


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

[Bug tree-optimization/32367] [4.3 Regression] internal compiler error: in build_polynomial_chrec, at tree-chrec.h:113

[pinskia at gcc dot gnu dot org]

------- Comment #7 from pinskia at gcc dot gnu dot org  2007-06-16 21:16 -------
But I am not 100% the rest of the correct is correct.
Daniel/Pop,
  Could you look into my patch to see if it is correct?  My pointer_plus
exposed a latent bug with chrec_component_in_loop_num:
for 
initial_condition_in_loop_num({{&BinomialCoefficients[0], +, 4}_1, +, {0, +,
4}_1}_1, 1)
We were creating:
{&BinomialCoefficients[0], +, {&BinomialCoefficients[0], +, 4}_1 }_1

Which does not make sense at all. because the second iteration of the loop, we
would have
&BinomialCoefficients[0] + &BinomialCoefficients[0] which does not make sense.


Do you agree that for
initial_condition_in_loop_num({{&BinomialCoefficients[0], +, 4}_1, +, {0, +,
4}_1}_1, 1)

Should return &BinomialCoefficients[0] ?

Thanks,
Andrew Pinski


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |dberlin at gcc dot gnu dot
                   |                            |org, spop at gcc dot gnu dot
                   |                            |org


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

[Bug tree-optimization/32367] [4.3 Regression] internal compiler error: in build_polynomial_chrec, at tree-chrec.h:113

[pinskia at gcc dot gnu dot org]

------- Comment #8 from pinskia at gcc dot gnu dot org  2007-06-16 21:41 -------
here is a testcase which also crashes for i686 (32bits):
int BinomialCoefficientsInited = 0;
int BinomialCoefficients[17 * 35];
double Evaluate_TPat (void)
{
        unsigned short n, k;
        if (BinomialCoefficientsInited == 0)
        {
                int *ptr = BinomialCoefficients;
                for (n = 1; n <= 33; ++n)
                {
                        for (k = 1; k < n; ++k)
                                ++ptr;
                        *ptr = 1;
                }
        }
}


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  GCC build triplet|x86_64-pc-linux-gnu         |
   GCC host triplet|x86_64-pc-linux-gnu         |
 GCC target triplet|x86_64-pc-linux-gnu         |


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

[Bug tree-optimization/32367] [4.3 Regression] internal compiler error: in build_polynomial_chrec, at tree-chrec.h:113

[spop at gcc dot gnu dot org]

------- Comment #9 from spop at gcc dot gnu dot org  2007-06-17 13:38 -------
Subject: Re:  [4.3 Regression] internal compiler error: in
build_polynomial_chrec, at tree-chrec.h:113

{{&BinomialCoefficients[0], +, 4}_1, +, {0, +, 4}_1}_1
does not look good: the left part should be invariant in loop_1.
It's most certainly the code in scev analysis that is in fault here.
I'll have a look.  Thanks for pointing me to the bug.

Sebastian


-- 


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

[Bug tree-optimization/32367] [4.3 Regression] internal compiler error: in build_polynomial_chrec, at tree-chrec.h:113

[pinskia at gcc dot gnu dot org]

------- Comment #10 from pinskia at gcc dot gnu dot org  2007-06-17 17:32 -------
> {{&BinomialCoefficients[0], +, 4}_1, +, {0, +, 4}_1}_1
> does not look good: the left part should be invariant in loop_1.
> It's most certainly the code in scev analysis that is in fault here.
> I'll have a look.  Thanks for pointing me to the bug.

Ok, thanks.  Just to let people know, {{&BinomialCoefficients[0], +, 4}_1, +,
{0, +, 4}_1}_1 was also showing up on the trunk before the pointer_plus was
merged in.


-- 


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

[Bug tree-optimization/32367] [4.3 Regression] internal compiler error: in build_polynomial_chrec, at tree-chrec.h:113

[spop at gcc dot gnu dot org]

------- Comment #11 from spop at gcc dot gnu dot org  2007-06-17 19:13 -------
Subject: Re:  [4.3 Regression] internal compiler error: in
build_polynomial_chrec, at tree-chrec.h:113

The ptrplus patch contains the following code:

*************** interpret_rhs_modify_stmt (struct loop *
*** 1611,1616 ****
--- 1615,1630 ----

    switch (TREE_CODE (opnd1))
      {
+     case POINTER_PLUS_EXPR:
+       opnd10 = TREE_OPERAND (opnd1, 0);
+       opnd11 = TREE_OPERAND (opnd1, 1);
+       chrec10 = analyze_scalar_evolution (loop, opnd10);
+       chrec11 = analyze_scalar_evolution (loop, opnd11);
+       chrec10 = chrec_convert (type, chrec10, at_stmt);
+       chrec11 = chrec_convert (sizetype, chrec11, at_stmt);
+       res = chrec_fold_plus (type, chrec10, chrec11);
+       break;
+
      case PLUS_EXPR:
        opnd10 = TREE_OPERAND (opnd1, 0);
        opnd11 = TREE_OPERAND (opnd1, 1);

At this point we have the following values:
(gdb) call debug_generic_expr (chrec10)
{ptr_7, +, (unsigned int) (n_20 + 65535) * 4}_1
(gdb) call debug_generic_expr (chrec11)
(unsigned int) {n_6 + 65535, +, 1}_1 * 4
(gdb) call debug_generic_expr (res)
{ptr_7 + (unsigned int) {n_6 + 65535, +, 1}_1 * 4, +, (unsigned int)
(n_20 + 65535) * 4}_1

chrec_fold_plus is completely disturbed by the "complicated" MULT_EXPR
"{}_1 * 4", and just considers this expression to be constant, and
finally it builds "ptr_7 + (unsigned int) {n_6 + 65535, +, 1}_1 * 4".

The code in chrec_fold_multiply that is producing this MULT_EXPR is:

          return fold_build2 (MULT_EXPR, type, op0, op1);

(gdb) p op0
$42 = (tree) 0xb7c27444
(gdb) pgs
4

(gdb) p op1
$43 = (tree) 0xb7ccf6a0
(gdb) pgs
(unsigned int) (n_20 + 65535);

(gdb) pt
 <nop_expr 0xb7ccf6a0
    type <integer_type 0xb7c36000 unsigned int public unsigned sizetype SI
        size <integer_cst 0xb7c27658 constant invariant 32>
        unit size <integer_cst 0xb7c27444 constant invariant 4>
        align 32 symtab 0 alias set -1 canonical type 0xb7c3c0d8
precision 32 min <integer_cst 0xb7c27674 0> max <integer_cst
0xb7c27c08 -1>>

    arg 0 <plus_expr 0xb7c2d948
        type <integer_type 0xb7c36288 short unsigned int
sizes-gimplified public unsigned HI
            size <integer_cst 0xb7c275b0 constant invariant 16>
            unit size <integer_cst 0xb7c275cc constant invariant 2>
            align 16 symtab 0 alias set -1 canonical type 0xb7c36288
precision 16 min <integer_cst 0xb7c275e8 0> max <integer_cst
0xb7c27594 65535>>

        arg 0 <ssa_name 0xb7cdb5e4 type <integer_type 0xb7c36288 short
unsigned int>
            var <var_decl 0xb7cd70b8 n> def_stmt <gimple_modify_stmt
0xb7cda770>
            version 20>
        arg 1 <integer_cst 0xb7c27594 constant invariant 65535>>>

And here, unfortunately fold_build2 does not further simplify this
expression because of the cast to uint around the PLUS_EXPR.


-- 


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

[Bug tree-optimization/32367] [4.3 Regression] internal compiler error: in build_polynomial_chrec, at tree-chrec.h:113

[spop at gcc dot gnu dot org]

------- Comment #12 from spop at gcc dot gnu dot org  2007-06-17 19:16 -------
Subject: Re:  [4.3 Regression] internal compiler error: in
build_polynomial_chrec, at tree-chrec.h:113

> Ok, thanks.  Just to let people know, {{&BinomialCoefficients[0], +, 4}_1, +,
> {0, +, 4}_1}_1 was also showing up on the trunk before the pointer_plus was
> merged in.
>

In the fix for this bug, I'm going to include the following assert
such that this inconsistency will not occur anymore.

Index: tree-chrec.h
===================================================================
--- tree-chrec.h        (revision 125771)
+++ tree-chrec.h        (working copy)
@@ -83,6 +83,7 @@ extern bool tree_contains_chrecs (tree,
 extern bool evolution_function_is_affine_multivariate_p (tree, int);
 extern bool evolution_function_is_univariate_p (tree);
 extern unsigned nb_vars_in_chrec (tree);
+extern bool evolution_function_is_invariant_p (tree, int);

 /* Determines whether CHREC is equal to zero.  */

@@ -114,6 +115,8 @@ build_polynomial_chrec (unsigned loop_nu
   else
     gcc_assert (TREE_TYPE (left) == TREE_TYPE (right));

+  gcc_assert (evolution_function_is_invariant_p (left, loop_num));
+
   if (chrec_zerop (right))
     return left;

@@ -140,7 +143,6 @@ evolution_function_is_constant_p (tree c
     }
 }

-extern bool evolution_function_is_invariant_p (tree, int);
 /* Determine whether the given tree is an affine evolution function or not. 
*/

 static inline bool


-- 


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

[Bug tree-optimization/32367] [4.3 Regression] internal compiler error: in build_polynomial_chrec, at tree-chrec.h:113

[spop at gcc dot gnu dot org]

------- Comment #13 from spop at gcc dot gnu dot org  2007-06-19 18:35 -------
Subject: Bug 32367

Author: spop
Date: Tue Jun 19 18:35:39 2007
New Revision: 125855

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=125855
Log:
        PR tree-optimization/32367
        * tree-chrec.h (build_polynomial_chrec): Verify that the left hand side 
        of the chrec has no evolution in that loop.
        * testsuite/gcc.dg/tree-ssa/pr32367.c: New.


Added:
    trunk/gcc/testsuite/gcc.dg/tree-ssa/pr32367.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/tree-chrec.h


-- 


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

[Bug tree-optimization/32367] [4.3 Regression] internal compiler error: in build_polynomial_chrec, at tree-chrec.h:113

[pinskia at gcc dot gnu dot org]

------- Comment #14 from pinskia at gcc dot gnu dot org  2007-06-25 01:54 -------
Fixed.


-- 

pinskia at gcc dot gnu dot org changed:

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


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