Hi!
Right now we spent several minutes in verify_tree. The problems I see
is that merge_tlist does the exact opposite of what should it be doing with
copy flag (most merge_tlist calls are with copy=0, thus that means mostly
unnecessary copying, but for the single one for SAVE_EXPR it actually
probably breaks things or can break), the middle-hunk is about one spot
which IMHO uses copy=1 unnecessarily (nothing uses tmp_list2 afterwards).
The most important is the last hunk, the SAVE_EXPR handling was doing
merge_tlist first on the whole tmp_nosp chain (with copy=0 which mistakenly
copied everything, see above), and then doing that again with the whole
tmp_nosp list except the first entry, then except the first two entries etc.
O(n^2) complexity, but IMHO none of the calls but the first one actually
would do anything, because after the first merge_tlist call all entries
should be actually in tmp_list3 (except for duplicates), and so for all
further entries it would be finding a matching entry already (found=1).
With this patch pr60101.c compiles within less than a second.
Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
2014-02-11 Jakub Jelinek <ja...@redhat.com>
PR c/60101
* c-common.c (merge_tlist): If copy is true, call new_tlist,
if false, add ADD itself, rather than vice versa.
(verify_tree): For COND_EXPR, don't call merge_tlist with non-zero
copy. For SAVE_EXPR, only call merge_tlist once.
* c-c++-common/pr60101.c: New test.
--- gcc/c-family/c-common.c.jj 2014-02-08 10:07:12.000000000 +0100
+++ gcc/c-family/c-common.c 2014-02-11 13:18:53.270521683 +0100
@@ -2976,7 +2976,7 @@ merge_tlist (struct tlist **to, struct t
}
if (!found)
{
- *end = copy ? add : new_tlist (NULL, add->expr, add->writer);
+ *end = copy ? new_tlist (NULL, add->expr, add->writer) : add;
end = &(*end)->next;
*end = 0;
}
@@ -3134,7 +3134,7 @@ verify_tree (tree x, struct tlist **pbef
verify_tree (TREE_OPERAND (x, 0), &tmp_before, &tmp_list2, NULL_TREE);
warn_for_collisions (tmp_list2);
merge_tlist (pbefore_sp, tmp_before, 0);
- merge_tlist (pbefore_sp, tmp_list2, 1);
+ merge_tlist (pbefore_sp, tmp_list2, 0);
tmp_list3 = tmp_nosp = 0;
verify_tree (TREE_OPERAND (x, 1), &tmp_list3, &tmp_nosp, NULL_TREE);
@@ -3238,12 +3238,7 @@ verify_tree (tree x, struct tlist **pbef
warn_for_collisions (tmp_nosp);
tmp_list3 = 0;
- while (tmp_nosp)
- {
- struct tlist *t = tmp_nosp;
- tmp_nosp = t->next;
- merge_tlist (&tmp_list3, t, 0);
- }
+ merge_tlist (&tmp_list3, tmp_nosp, 0);
t->cache_before_sp = tmp_before;
t->cache_after_sp = tmp_list3;
}
--- gcc/testsuite/c-c++-common/pr60101.c.jj 2014-02-11 14:55:20.728288546
+0100
+++ gcc/testsuite/c-c++-common/pr60101.c 2014-02-11 13:37:28.000000000
+0100
@@ -0,0 +1,112 @@
+/* PR c/60101 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -Wall" } */
+
+extern int *a, b, *c, *d;
+
+void
+foo (double _Complex *x, double _Complex *y, double _Complex *z, unsigned int
l, int w)
+{
+ unsigned int e = (unsigned int) a[3];
+ double _Complex (*v)[l][4][e][l][4] = (double _Complex (*)[l][4][e][l][4]) z;
+ double _Complex (*f)[l][b][l] = (double _Complex (*)[l][b][l]) y;
+ unsigned int g = c[0] * c[1] * c[2];
+ unsigned int h = d[0] + c[0] * (d[1] + c[1] * d[2]);
+ unsigned int i;
+
+ for (i = 0; i < e; i++)
+ {
+ int j = e * d[3] + i;
+
+ unsigned int n0, n1, n2, n3, n4, n5, n6, n7, n8, n9, n10, n11;
+ float _Complex s = 0.;
+ unsigned int t = 0;
+
+ for (n0 = 0; n0 < l; n0++)
+ for (n1 = 0; n1 < l; n1++)
+ for (n2 = 0; n2 < l; n2++)
+ for (n3 = 0; n3 < l; n3++)
+ for (n4 = 0; n4 < l; n4++)
+ for (n5 = 0; n5 < l; n5++)
+ for (n6 = 0; n6 < l; n6++)
+ for (n7 = 0; n7 < l; n7++)
+ for (n8 = 0; n8 < l; n8++)
+ for (n9 = 0; n9 < l; n9++)
+ for (n10 = 0; n10 < l; n10++)
+ for (n11 = 0; n11 < l; n11++)
+ {
+ if (t % g == h)
+ s
+ += f[n0][n4][j][n8] * f[n1][n5][j][n9] *
~(f[n2][n6][w][n10]) * ~(f[n3][n7][w][n11])
+ * (+0.25 * v[0][n2][0][i][n9][1] *
v[0][n3][0][i][n5][1] * v[0][n10][0][i][n4][1]
+ * v[0][n7][1][i][n8][0] *
v[0][n11][1][i][n1][0] * v[0][n6][1][i][n0][0]
+ + 0.25 * v[0][n2][0][i][n9][1] *
v[0][n3][0][i][n5][1] * v[0][n10][0][i][n4][1]
+ * v[0][n11][1][i][n8][0] *
v[0][n6][1][i][n1][0] * v[0][n7][1][i][n0][0]
+ - 0.5 * v[0][n2][0][i][n9][1] *
v[0][n3][0][i][n5][1] * v[0][n10][0][i][n4][1]
+ * v[0][n11][1][i][n8][0] *
v[0][n7][1][i][n1][0] * v[0][n6][1][i][n0][0]
+ + 0.25 * v[0][n2][0][i][n9][1] *
v[0][n10][0][i][n5][1] * v[0][n3][0][i][n4][1]
+ * v[0][n7][1][i][n8][0] *
v[0][n6][1][i][n1][0] * v[0][n11][1][i][n0][0]
+ - 0.5 * v[0][n2][0][i][n9][1] *
v[0][n10][0][i][n5][1] * v[0][n3][0][i][n4][1]
+ * v[0][n11][1][i][n8][0] *
v[0][n6][1][i][n1][0] * v[0][n7][1][i][n0][0]
+ + 0.25 * v[0][n2][0][i][n9][1] *
v[0][n10][0][i][n5][1] * v[0][n3][0][i][n4][1]
+ * v[0][n11][1][i][n8][0] *
v[0][n7][1][i][n1][0] * v[0][n6][1][i][n0][0]
+ + 0.25 * v[0][n3][0][i][n9][1] *
v[0][n2][0][i][n5][1] * v[0][n10][0][i][n4][1]
+ * v[0][n6][1][i][n8][0] *
v[0][n11][1][i][n1][0] * v[0][n7][1][i][n0][0]
+ - 0.5 * v[0][n3][0][i][n9][1] *
v[0][n2][0][i][n5][1] * v[0][n10][0][i][n4][1]
+ * v[0][n11][1][i][n8][0] *
v[0][n6][1][i][n1][0] * v[0][n7][1][i][n0][0]
+ + 0.25 * v[0][n3][0][i][n9][1] *
v[0][n2][0][i][n5][1] * v[0][n10][0][i][n4][1]
+ * v[0][n11][1][i][n8][0] *
v[0][n7][1][i][n1][0] * v[0][n6][1][i][n0][0]
+ + 0.25 * v[0][n3][0][i][n9][1] *
v[0][n10][0][i][n5][1] * v[0][n2][0][i][n4][1]
+ * v[0][n6][1][i][n8][0] *
v[0][n7][1][i][n1][0] * v[0][n11][1][i][n0][0]
+ + 0.25 * v[0][n3][0][i][n9][1] *
v[0][n10][0][i][n5][1] * v[0][n2][0][i][n4][1]
+ * v[0][n11][1][i][n8][0] *
v[0][n6][1][i][n1][0] * v[0][n7][1][i][n0][0]
+ - 0.5 * v[0][n3][0][i][n9][1] *
v[0][n10][0][i][n5][1] * v[0][n2][0][i][n4][1]
+ * v[0][n11][1][i][n8][0] *
v[0][n7][1][i][n1][0] * v[0][n6][1][i][n0][0]
+ + 0.25 * v[0][n10][0][i][n9][1] *
v[0][n2][0][i][n5][1] * v[0][n3][0][i][n4][1]
+ * v[0][n6][1][i][n8][0] *
v[0][n7][1][i][n1][0] * v[0][n11][1][i][n0][0]
+ - 0.5 * v[0][n10][0][i][n9][1] *
v[0][n2][0][i][n5][1] * v[0][n3][0][i][n4][1]
+ * v[0][n6][1][i][n8][0] *
v[0][n11][1][i][n1][0] * v[0][n7][1][i][n0][0]
+ - 0.5 * v[0][n10][0][i][n9][1] *
v[0][n2][0][i][n5][1] * v[0][n3][0][i][n4][1]
+ * v[0][n7][1][i][n8][0] *
v[0][n6][1][i][n1][0] * v[0][n11][1][i][n0][0]
+ + 0.25 * v[0][n10][0][i][n9][1] *
v[0][n2][0][i][n5][1] * v[0][n3][0][i][n4][1]
+ * v[0][n7][1][i][n8][0] *
v[0][n11][1][i][n1][0] * v[0][n6][1][i][n0][0]
+ + 1. * v[0][n10][0][i][n9][1] *
v[0][n2][0][i][n5][1] * v[0][n3][0][i][n4][1]
+ * v[0][n11][1][i][n8][0] *
v[0][n6][1][i][n1][0] * v[0][n7][1][i][n0][0]
+ - 0.5 * v[0][n10][0][i][n9][1] *
v[0][n2][0][i][n5][1] * v[0][n3][0][i][n4][1]
+ * v[0][n11][1][i][n8][0] *
v[0][n7][1][i][n1][0] * v[0][n6][1][i][n0][0]
+ - 0.5 * v[0][n10][0][i][n9][1] *
v[0][n3][0][i][n5][1] * v[0][n2][0][i][n4][1]
+ * v[0][n6][1][i][n8][0] *
v[0][n7][1][i][n1][0] * v[0][n11][1][i][n0][0]
+ + 0.25 * v[0][n10][0][i][n9][1] *
v[0][n3][0][i][n5][1] * v[0][n2][0][i][n4][1]
+ * v[0][n6][1][i][n8][0] *
v[0][n11][1][i][n1][0] * v[0][n7][1][i][n0][0]
+ + 0.25 * v[0][n10][0][i][n9][1] *
v[0][n3][0][i][n5][1] * v[0][n2][0][i][n4][1]
+ * v[0][n7][1][i][n8][0] *
v[0][n6][1][i][n1][0] * v[0][n11][1][i][n0][0]
+ - 0.5 * v[0][n10][0][i][n9][1] *
v[0][n3][0][i][n5][1] * v[0][n2][0][i][n4][1]
+ * v[0][n7][1][i][n8][0] *
v[0][n11][1][i][n1][0] * v[0][n6][1][i][n0][0]
+ - 0.5 * v[0][n10][0][i][n9][1] *
v[0][n3][0][i][n5][1] * v[0][n2][0][i][n4][1]
+ * v[0][n11][1][i][n8][0] *
v[0][n6][1][i][n1][0] * v[0][n7][1][i][n0][0]
+ + 1. * v[0][n10][0][i][n9][1] *
v[0][n3][0][i][n5][1] * v[0][n2][0][i][n4][1]
+ * v[0][n11][1][i][n8][0] *
v[0][n7][1][i][n1][0] * v[0][n6][1][i][n0][0]
+ + 0.5 * v[0][n6][1][i][n4][1] *
v[0][n2][0][i][n9][1] * v[0][n3][0][i][n5][1]
+ * v[0][n7][1][i][n1][0] *
v[0][n11][1][i][n0][0] * v[0][n10][0][i][n8][0]
+ - 0.25 * v[0][n6][1][i][n4][1] *
v[0][n2][0][i][n9][1] * v[0][n3][0][i][n5][1]
+ * v[0][n11][1][i][n1][0] *
v[0][n7][1][i][n0][0] * v[0][n10][0][i][n8][0]
+ - 0.25 * v[0][n6][1][i][n4][1] *
v[0][n2][0][i][n9][1] * v[0][n3][0][i][n5][1]
+ * v[0][n7][1][i][n8][0] *
v[0][n11][1][i][n0][0] * v[0][n10][0][i][n1][0]
+ + 0.25 * v[0][n6][1][i][n4][1] *
v[0][n2][0][i][n9][1] * v[0][n3][0][i][n5][1]
+ * v[0][n7][1][i][n8][0] *
v[0][n11][1][i][n1][0] * v[0][n10][0][i][n0][0]
+ + 0.25 * v[0][n6][1][i][n4][1] *
v[0][n2][0][i][n9][1] * v[0][n3][0][i][n5][1]
+ * v[0][n11][1][i][n8][0] *
v[0][n7][1][i][n0][0] * v[0][n10][0][i][n1][0]
+ - 0.5 * v[0][n6][1][i][n4][1] *
v[0][n2][0][i][n9][1] * v[0][n3][0][i][n5][1]
+ * v[0][n11][1][i][n8][0] *
v[0][n7][1][i][n1][0] * v[0][n10][0][i][n0][0]
+ - 0.25 * v[0][n6][1][i][n4][1] *
v[0][n2][0][i][n9][1] * v[0][n10][0][i][n5][1]
+ * v[0][n7][1][i][n1][0] *
v[0][n11][1][i][n0][0] * v[0][n3][0][i][n8][0]
+ - 0.25 * v[0][n6][1][i][n4][1] *
v[0][n2][0][i][n9][1] * v[0][n10][0][i][n5][1]
+ * v[0][n7][1][i][n8][0] *
v[0][n11][1][i][n0][0] * v[0][n3][0][i][n1][0]);
+ t++;
+ }
+ int u = (j - w + b) % b;
+ int q = (j >= w ? +1 : -1);
+ int r = q;
+ x[u] += r * s;
+ }
+}
Jakub
