aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--gcc-4.9/gcc/doc/invoke.texi12
-rw-r--r--gcc-4.9/gcc/params.def15
-rw-r--r--gcc-4.9/gcc/testsuite/gcc.c-torture/compile/pr65735.c21
-rw-r--r--gcc-4.9/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-10.c24
-rw-r--r--gcc-4.9/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-6.c43
-rw-r--r--gcc-4.9/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-7.c127
-rw-r--r--gcc-4.9/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-8.c440
-rw-r--r--gcc-4.9/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-9.c50
-rw-r--r--gcc-4.9/gcc/tree-cfg.c2
-rw-r--r--gcc-4.9/gcc/tree-cfg.h1
-rw-r--r--gcc-4.9/gcc/tree-ssa-threadedge.c288
-rw-r--r--gcc-4.9/gcc/tree-ssa-threadupdate.c272
-rw-r--r--gcc-4.9/gcc/tree-ssa-threadupdate.h1
13 files changed, 1293 insertions, 3 deletions
diff --git a/gcc-4.9/gcc/doc/invoke.texi b/gcc-4.9/gcc/doc/invoke.texi
index f8350c418..b5d9c4ba0 100644
--- a/gcc-4.9/gcc/doc/invoke.texi
+++ b/gcc-4.9/gcc/doc/invoke.texi
@@ -10442,6 +10442,18 @@ is greater or equal to this number, use callbacks instead of inline checks.
E.g. to disable inline code use
@option{--param asan-instrumentation-with-call-threshold=0}.
+@item max-fsm-thread-path-insns
+Maximum number of instructions to copy when duplicating blocks on a
+finite state automaton jump thread path. The default is 100.
+
+@item max-fsm-thread-length
+Maximum number of basic blocks on a finite state automaton jump thread
+path. The default is 10.
+
+@item max-fsm-thread-paths
+Maximum number of new jump thread paths to create for a finite state
+automaton. The default is 50.
+
@end table
@end table
diff --git a/gcc-4.9/gcc/params.def b/gcc-4.9/gcc/params.def
index 3d2c913fd..518d379ed 100644
--- a/gcc-4.9/gcc/params.def
+++ b/gcc-4.9/gcc/params.def
@@ -1389,6 +1389,21 @@ DEFPARAM (PARAM_UNINIT_CONTROL_DEP_ATTEMPTS,
"during uninitialized variable analysis",
1000, 1, 0)
+DEFPARAM (PARAM_MAX_FSM_THREAD_PATH_INSNS,
+ "max-fsm-thread-path-insns",
+ "Maximum number of instructions to copy when duplicating blocks on a finite state automaton jump thread path",
+ 100, 1, 999999)
+
+DEFPARAM (PARAM_MAX_FSM_THREAD_LENGTH,
+ "max-fsm-thread-length",
+ "Maximum number of basic blocks on a finite state automaton jump thread path",
+ 10, 1, 999999)
+
+DEFPARAM (PARAM_MAX_FSM_THREAD_PATHS,
+ "max-fsm-thread-paths",
+ "Maximum number of new jump thread paths to create for a finite state automaton",
+ 50, 1, 999999)
+
/* Fraction of adjusting fp setting cost in framepointer shrinkwrapping. */
DEFPARAM (PARAM_FPSET_COST_FRACTION,
"fpset-cost-fraction",
diff --git a/gcc-4.9/gcc/testsuite/gcc.c-torture/compile/pr65735.c b/gcc-4.9/gcc/testsuite/gcc.c-torture/compile/pr65735.c
new file mode 100644
index 000000000..c30de8ea3
--- /dev/null
+++ b/gcc-4.9/gcc/testsuite/gcc.c-torture/compile/pr65735.c
@@ -0,0 +1,21 @@
+/* PR tree-optimization/65735 */
+
+int foo (void);
+
+void
+bar (int a, int b, int c)
+{
+ while (!a)
+ {
+ c = foo ();
+ if (c == 7)
+ c = b;
+ switch (c)
+ {
+ case 1:
+ a = b++;
+ if (b)
+ b = 1;
+ }
+ }
+}
diff --git a/gcc-4.9/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-10.c b/gcc-4.9/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-10.c
new file mode 100644
index 000000000..4acf580e1
--- /dev/null
+++ b/gcc-4.9/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-10.c
@@ -0,0 +1,24 @@
+/* PR 65177 */
+/* { dg-do compile } */
+/* { dg-options "-O3" } */
+
+typedef struct p7_profile_s {} P7_PROFILE;
+enum p7t_statetype_e {
+ p7T_S = 4, p7T_N = 5, p7T_E = 7, p7T_C = 8, p7T_J = 10, };
+typedef struct p7_trace_s {} P7_TRACE;
+typedef struct p7_gmx_s {
+ int L;
+} P7_GMX;
+static inline int select_c(const P7_PROFILE *gm, const P7_GMX *pp, const P7_GMX *gx, int i) {
+ float path[2];
+ return ((path[0] > path[1]) ? p7T_C : p7T_E);
+}
+void p7_GOATrace(const P7_PROFILE *gm, const P7_GMX *pp, const P7_GMX *gx, P7_TRACE *tr) {
+ int i = gx->L;
+ int sprv, scur;
+ while (sprv != p7T_S) {
+ switch (sprv) { case p7T_C: scur = select_c(gm, pp, gx, i); break; }
+ if ( (scur == p7T_N || scur == p7T_J || scur == p7T_C) && scur == sprv) i--;
+ sprv = scur;
+ }
+}
diff --git a/gcc-4.9/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-6.c b/gcc-4.9/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-6.c
new file mode 100644
index 000000000..bb34a7432
--- /dev/null
+++ b/gcc-4.9/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-6.c
@@ -0,0 +1,43 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-dom1-details" } */
+/* { dg-final { scan-tree-dump-times "FSM" 6 "dom1" } } */
+/* { dg-final { cleanup-tree-dump "dom1" } } */
+
+int sum0, sum1, sum2, sum3;
+int foo (char *s, char **ret)
+{
+ int state=0;
+ char c;
+
+ for (; *s && state != 4; s++)
+ {
+ c = *s;
+ if (c == '*')
+ {
+ s++;
+ break;
+ }
+ switch (state)
+ {
+ case 0:
+ if (c == '+')
+ state = 1;
+ else if (c != '-')
+ sum0+=c;
+ break;
+ case 1:
+ if (c == '+')
+ state = 2;
+ else if (c == '-')
+ state = 0;
+ else
+ sum1+=c;
+ break;
+ default:
+ break;
+ }
+
+ }
+ *ret = s;
+ return state;
+}
diff --git a/gcc-4.9/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-7.c b/gcc-4.9/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-7.c
new file mode 100644
index 000000000..21474f0b4
--- /dev/null
+++ b/gcc-4.9/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-7.c
@@ -0,0 +1,127 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-dom1-details" } */
+/* { dg-final { scan-tree-dump-times "FSM" 19 "dom1" } } */
+/* { dg-final { cleanup-tree-dump "dom1" } } */
+
+enum STATE {
+ S0=0,
+ SI,
+ S1,
+ S2,
+ S3,
+ S4,
+ S5,
+ S6
+};
+
+int bar (enum STATE s);
+
+enum STATE foo (unsigned char **y, unsigned *c)
+{
+ unsigned char *x = *y;
+ unsigned char n;
+ enum STATE s = S0;
+
+ for( ; *x && s != SI; x++ )
+ {
+ n = *x;
+ if (n == 'x')
+ {
+ x++;
+ break;
+ }
+ switch(s)
+ {
+ case S0:
+ if(bar(n))
+ s = S3;
+ else if( n == 'a' || n == 'b' )
+ s = S1;
+ else if( n == 'c' )
+ s = S4;
+ else
+ {
+ s = SI;
+ c[SI]++;
+ }
+ c[S0]++;
+ break;
+ case S1:
+ if(bar(n))
+ {
+ s = S3;
+ c[S1]++;
+ }
+ else if( n == 'c' )
+ {
+ s = S4;
+ c[S1]++;
+ }
+ else
+ {
+ s = SI;
+ c[S1]++;
+ }
+ break;
+ case S3:
+ if( n == 'c' )
+ {
+ s = S4;
+ c[S3]++;
+ }
+ else if(!bar(n))
+ {
+ s = SI;
+ c[S3]++;
+ }
+ break;
+ case S4:
+ if( n == 'E' || n == 'e' )
+ {
+ s = S2;
+ c[S4]++;
+ }
+ else if(!bar(n))
+ {
+ s = SI;
+ c[S4]++;
+ }
+ break;
+ case S2:
+ if( n == 'a' || n == 'b' )
+ {
+ s = S5;
+ c[S2]++;
+ }
+ else
+ {
+ s = SI;
+ c[S2]++;
+ }
+ break;
+ case S5:
+ if(bar(n))
+ {
+ s = S6;
+ c[S5]++;
+ }
+ else
+ {
+ s = SI;
+ c[S5]++;
+ }
+ break;
+ case S6:
+ if(!bar(n))
+ {
+ s = SI;
+ c[SI]++;
+ }
+ break;
+ default:
+ break;
+ }
+ }
+ *y=x;
+ return s;
+}
diff --git a/gcc-4.9/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-8.c b/gcc-4.9/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-8.c
new file mode 100644
index 000000000..9be75aaf2
--- /dev/null
+++ b/gcc-4.9/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-8.c
@@ -0,0 +1,440 @@
+/* PR 64878 */
+/* { dg-options "-O2" } */
+/* { dg-do run } */
+
+struct A { int a1; };
+struct B { char *b1; int b2; int b3; };
+struct C { char *c1; int c2; struct B *c3; };
+extern struct A *f1 (char *s);
+static struct A *f2 (struct C *x);
+__attribute__ ((noinline, noclone)) int f3 (struct A *x, struct A *z) { asm volatile ("" : : "g" (x), "g" (z) : "memory"); return 0; }
+__attribute__ ((noinline, noclone)) void f4 (struct A *x, char *y, struct A *z) { asm volatile ("" : : "g" (x), "g" (z), "g" (y) : "memory"); }
+__attribute__ ((noinline, noclone)) struct B *f5 (void) { static char b[32]; static struct B f3 = { b, 0, 32 }; return &f3; }
+__attribute__ ((noinline, noclone)) int f6 (struct B *p, char *w, int z) { asm volatile ("" : : "g" (p), "g" (w), "g" (z) : "memory"); return 0; }
+__attribute__ ((noinline, noclone)) void f7 (struct B *p) { asm volatile ("" : : "g" (p) : "memory"); }
+__attribute__ ((noinline, noclone)) void f8 (struct B *p) { asm volatile ("" : : "g" (p) : "memory"); }
+__attribute__ ((noinline, noclone)) void f9 (struct A *x) { asm volatile ("" : : "g" (x) : "memory"); }
+__attribute__ ((noinline, noclone)) struct A *f10 (void) { static struct A j; asm volatile ("" : : : "memory"); return &j; }
+__attribute__ ((noinline, noclone)) struct A *f11 (void) { static struct A j; asm volatile ("" : : : "memory"); return &j; }
+__attribute__ ((noinline, noclone)) struct A *f12 (int b) { static struct A j; asm volatile ("" : : "g" (b) : "memory"); return &j; }
+__attribute__ ((noinline, noclone)) struct A *f13 (int i) { static struct A j; asm volatile ("" : : "g" (i) : "memory"); return &j; }
+__attribute__ ((noinline, noclone)) struct A *f14 (double d) { static struct A j; asm volatile ("" : : "g" (&d) : "memory"); return &j; }
+__attribute__ ((noinline, noclone)) struct A *f15 (char *s) { static struct A j; asm volatile ("" : : "g" (s) : "memory"); return &j; }
+char *t = "0123456789abcdef";
+char *u = "0123456789.+-e";
+
+__attribute__ ((noinline, noclone)) struct A *
+f1 (char *s)
+{
+ struct C f;
+ struct A *o;
+ f.c1 = s;
+ f.c2 = 0;
+ f.c3 = f5 ();
+ o = f2 (&f);
+ f8 (f.c3);
+ return o;
+}
+
+static struct A *
+f2 (struct C *x)
+{
+ int a, b, e = 0;
+ struct A *f = 0, *o;
+ char *g = 0;
+ char h = '\0';
+ int i = 0, j = 0;
+ a = 0;
+ b = 1;
+ char c;
+ do
+ {
+ c = x->c1[x->c2];
+ switch (a)
+ {
+ case 0:
+ if (c == ' ')
+ x->c2++;
+ else if (c == '/')
+ {
+ a = 4;
+ j = x->c2++;
+ }
+ else
+ a = b;
+ break;
+ case 1:
+ switch (c)
+ {
+ case '{':
+ a = 0;
+ b = 15;
+ f = f10 ();
+ x->c2++;
+ break;
+ case '[':
+ a = 0;
+ b = 13;
+ f = f11 ();
+ x->c2++;
+ break;
+ case 'N':
+ case 'n':
+ a = 3;
+ j = x->c2++;
+ break;
+ case '"':
+ case '\'':
+ h = c;
+ f7 (x->c3);
+ a = 8;
+ j = ++x->c2;
+ break;
+ case 'T':
+ case 't':
+ case 'F':
+ case 'f':
+ a = 11;
+ j = x->c2++;
+ break;
+ case '0' ... '9':
+ case '-':
+ i = 0;
+ a = 12;
+ j = x->c2++;
+ break;
+ default:
+ e = 1;
+ goto out;
+ }
+ break;
+ case 2:
+ goto out;
+ case 3:
+ if (__builtin_strncmp ("null", x->c1 + j, x->c2 - j))
+ {
+ e = 2;
+ goto out;
+ }
+ if (x->c2 - j == 4)
+ {
+ f = 0;
+ b = 2;
+ a = 0;
+ }
+ else
+ x->c2++;
+ break;
+ case 4:
+ if (c == '*')
+ a = 5;
+ else if (c == '/')
+ a = 6;
+ else
+ {
+ e = 8;
+ goto out;
+ }
+ x->c2++;
+ break;
+ case 5:
+ if (c == '*')
+ a = 7;
+ x->c2++;
+ break;
+ case 6:
+ if (c == '\n')
+ a = 0;
+ x->c2++;
+ break;
+ case 7:
+ if (c == '/')
+ a = 0;
+ else
+ a = 5;
+ x->c2++;
+ break;
+ case 8:
+ if (c == h)
+ {
+ f6 (x->c3, x->c1 + j, x->c2 - j);
+ f = f15 (x->c3->b1);
+ b = 2;
+ a = 0;
+ }
+ else if (c == '\\')
+ {
+ b = 8;
+ a = 9;
+ }
+ x->c2++;
+ break;
+ case 9:
+ switch (c)
+ {
+ case '"':
+ case '\\':
+ f6 (x->c3, x->c1 + j, x->c2 - j - 1);
+ j = x->c2++;
+ a = b;
+ break;
+ case 'b':
+ case 'n':
+ case 'r':
+ case 't':
+ f6 (x->c3, x->c1 + j, x->c2 - j - 1);
+ if (c == 'b')
+ f6 (x->c3, "\b", 1);
+ else if (c == 'n')
+ f6 (x->c3, "\n", 1);
+ else if (c == 'r')
+ f6 (x->c3, "\r", 1);
+ else if (c == 't')
+ f6 (x->c3, "\t", 1);
+ j = ++x->c2;
+ a = b;
+ break;
+ case 'u':
+ f6 (x->c3, x->c1 + j, x->c2 - j - 1);
+ j = ++x->c2;
+ a = 10;
+ break;
+ default:
+ e = 7;
+ goto out;
+ }
+ break;
+ case 10:
+ if (__builtin_strchr (t, c))
+ {
+ x->c2++;
+ if (x->c2 - j == 4)
+ {
+ unsigned char w[3];
+ unsigned int s =
+ (((x->c1[j] <= '9') ? x->c1[j] - '0' : (x->c1[j] & 7) + 9) << 12)
+ + (((x->c1[j + 1] <= '9') ? x->c1[j + 1] - '0' : (x->c1[j + 1] & 7) + 9) << 8)
+ + (((x->c1[j + 2] <= '9') ? x->c1[j + 2] - '0' : (x->c1[j + 2] & 7) + 9) << 4)
+ + ((x->c1[j + 3] <= '9') ? x->c1[j + 3] - '0' : (x->c1[j + 3] & 7) + 9);
+ if (s < 0x80)
+ {
+ w[0] = s;
+ f6 (x->c3, (char *) w, 1);
+ }
+ else if (s < 0x800)
+ {
+ w[0] = 0xc0 | (s >> 6);
+ w[1] = 0x80 | (s & 0x3f);
+ f6 (x->c3, (char *) w, 2);
+ }
+ else
+ {
+ w[0] = 0x0 | (s >> 12);
+ w[1] = 0x80 | ((s >> 6) & 0x3f);
+ w[2] = 0x80 | (s & 0x3f);
+ f6 (x->c3, (char *) w, 3);
+ }
+ j = x->c2;
+ a = b;
+ }
+ }
+ else
+ {
+ e = 7;
+ goto out;
+ }
+ break;
+ case 11:
+ if (__builtin_strncmp ("true", x->c1 + j, x->c2 - j) == 0)
+ {
+ if (x->c2 - j == 4)
+ {
+ f = f12 (1);
+ b = 2;
+ a = 0;
+ }
+ else
+ x->c2++;
+ }
+ else if (__builtin_strncmp ("false", x->c1 + j, x->c2 - j) == 0)
+ {
+ if (x->c2 - j == 5)
+ {
+ f = f12 (0);
+ b = 2;
+ a = 0;
+ }
+ else
+ x->c2++;
+ }
+ else
+ {
+ e = 3;
+ goto out;
+ }
+ break;
+ case 12:
+ if (!c || !__builtin_strchr (u, c))
+ {
+ if (!i)
+ f = f13 (0);
+ else
+ f = f14 (0.0);
+ b = 2;
+ a = 0;
+ }
+ else
+ {
+ if (c == '.' || c == 'e')
+ i = 1;
+ x->c2++;
+ }
+ break;
+ case 13:
+ if (c == ']')
+ {
+ x->c2++;
+ b = 2;
+ a = 0;
+ }
+ else
+ {
+ o = f2 (x);
+ if (((unsigned long) o > (unsigned long) -4000L))
+ {
+ e = 5;
+ goto out;
+ }
+ f3 (f, o);
+ b = 14;
+ a = 0;
+ }
+ break;
+ case 14:
+ if (c == ']')
+ {
+ x->c2++;
+ b = 2;
+ a = 0;
+ }
+ else if (c == ',')
+ {
+ x->c2++;
+ b = 13;
+ a = 0;
+ }
+ else
+ {
+ f9 (f);
+ e = 5;
+ goto out;
+ }
+ break;
+ case 15:
+ a = 16;
+ j = x->c2;
+ break;
+ case 16:
+ if (c == '}')
+ {
+ x->c2++;
+ b = 2;
+ a = 0;
+ }
+ else if (c == '"' || c == '\'')
+ {
+ h = c;
+ f7 (x->c3);
+ a = 17;
+ j = ++x->c2;
+ }
+ else
+ {
+ e = 6;
+ goto out;
+ }
+ break;
+ case 17:
+ if (c == h)
+ {
+ f6 (x->c3, x->c1 + j, x->c2 - j);
+ g = __builtin_strdup (x->c3->b1);
+ b = 18;
+ a = 0;
+ }
+ else if (c == '\\')
+ {
+ b = 17;
+ a = 9;
+ }
+ x->c2++;
+ break;
+ case 18:
+ if (c == ':')
+ {
+ x->c2++;
+ b = 19;
+ a = 0;
+ }
+ else
+ {
+ e = -6;
+ goto out;
+ }
+ break;
+ case 19:
+ o = f2 (x);
+ if (((unsigned long) o > (unsigned long) -4000L))
+ {
+ e = 6;
+ goto out;
+ }
+ f4 (f, g, o);
+ __builtin_free (g);
+ g = 0;
+ b = 20;
+ a = 0;
+ break;
+ case 20:
+ if (c == '}')
+ {
+ x->c2++;
+ b = 2;
+ a = 0;
+ }
+ else if (c == ',')
+ {
+ x->c2++;
+ b = 15;
+ a = 0;
+ }
+ else
+ {
+ e = 6;
+ goto out;
+ }
+ break;
+ }
+ }
+ while (c);
+ if (a != 2 && b != 2)
+ e = 9;
+out:
+ __builtin_free (g);
+ if (e == 0)
+ return f;
+ f9 (f);
+ return 0;
+}
+
+int
+main ()
+{
+ asm volatile ("" : : : "memory");
+ struct A *r = f1 ("{ \"id\": null, \"blahah\": \"foobarbazbar\", \"barbar\": { \"barbarbarba\":"
+ "\"abcdefgh\", \"ijklmnopqr\": \"stuvwxyzabcdefghijklmnopqrstuv\", \"xyzxyz\":"
+ " [ \"1\" ] } }");
+ if (!r)
+ __builtin_abort ();
+ return 0;
+}
diff --git a/gcc-4.9/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-9.c b/gcc-4.9/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-9.c
new file mode 100644
index 000000000..6be42038b
--- /dev/null
+++ b/gcc-4.9/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-9.c
@@ -0,0 +1,50 @@
+/* PR 65048 */
+/* { dg-do compile } */
+/* { dg-options "-O3" } */
+
+int a, b, c, d;
+void fn (void);
+
+int
+foo (x)
+{
+ switch (x)
+ {
+ case 'A':
+ return 'T';
+ case 'U':
+ return 'A';
+ }
+}
+
+void
+bar (int x, int y)
+{
+ switch (c)
+ {
+ case 'U':
+ switch (x)
+ {
+ default:
+ fn ();
+ case 'G':
+ switch (y)
+ {
+ case 'A':
+ d = 7;
+ }
+ }
+ }
+}
+
+void
+baz (void)
+{
+ while (1)
+ {
+ a = foo ();
+ b = foo ();
+ bar (a, b);
+ }
+}
+
diff --git a/gcc-4.9/gcc/tree-cfg.c b/gcc-4.9/gcc/tree-cfg.c
index 29aa8c7a7..d83fb3760 100644
--- a/gcc-4.9/gcc/tree-cfg.c
+++ b/gcc-4.9/gcc/tree-cfg.c
@@ -2667,7 +2667,7 @@ reinstall_phi_args (edge new_edge, edge old_edge)
near its "logical" location. This is of most help to humans looking
at debugging dumps. */
-static basic_block
+basic_block
split_edge_bb_loc (edge edge_in)
{
basic_block dest = edge_in->dest;
diff --git a/gcc-4.9/gcc/tree-cfg.h b/gcc-4.9/gcc/tree-cfg.h
index a115df58b..e6dee8073 100644
--- a/gcc-4.9/gcc/tree-cfg.h
+++ b/gcc-4.9/gcc/tree-cfg.h
@@ -62,6 +62,7 @@ extern void verify_gimple_in_cfg (struct function *);
extern tree gimple_block_label (basic_block);
extern void add_phi_args_after_copy_bb (basic_block);
extern void add_phi_args_after_copy (basic_block *, unsigned, edge);
+extern basic_block split_edge_bb_loc (edge);
extern bool gimple_duplicate_sese_region (edge, edge, basic_block *, unsigned,
basic_block *, bool);
extern bool gimple_duplicate_sese_tail (edge, edge, basic_block *, unsigned,
diff --git a/gcc-4.9/gcc/tree-ssa-threadedge.c b/gcc-4.9/gcc/tree-ssa-threadedge.c
index c715e842d..604123e10 100644
--- a/gcc-4.9/gcc/tree-ssa-threadedge.c
+++ b/gcc-4.9/gcc/tree-ssa-threadedge.c
@@ -48,6 +48,7 @@ along with GCC; see the file COPYING3. If not see
#include "langhooks.h"
#include "params.h"
#include "tree-ssa-threadedge.h"
+#include "tree-ssa-loop.h"
/* To avoid code explosion due to jump threading, we limit the
number of statements we are going to copy. This variable
@@ -617,6 +618,7 @@ simplify_control_stmt_condition (edge e,
rather than use a relational operator. These are simpler to handle. */
if (TREE_CODE (cond) == SSA_NAME)
{
+ tree original_lhs = cond;
cached_lhs = cond;
/* Get the variable's current value from the equivalence chains.
@@ -638,6 +640,12 @@ simplify_control_stmt_condition (edge e,
pass specific callback to try and simplify it further. */
if (cached_lhs && ! is_gimple_min_invariant (cached_lhs))
cached_lhs = (*simplify) (stmt, stmt);
+
+ /* We couldn't find an invariant. But, callers of this
+ function may be able to do something useful with the
+ unmodified destination. */
+ if (!cached_lhs)
+ cached_lhs = original_lhs;
}
else
cached_lhs = NULL;
@@ -897,6 +905,259 @@ thread_around_empty_blocks (edge taken_edge,
return false;
}
+/* Return true if the CFG contains at least one path from START_BB to END_BB.
+ When a path is found, record in PATH the blocks from END_BB to START_BB.
+ VISITED_BBS is used to make sure we don't fall into an infinite loop. Bound
+ the recursion to basic blocks belonging to LOOP. */
+
+static bool
+fsm_find_thread_path (basic_block start_bb, basic_block end_bb,
+ vec<basic_block, va_gc> *&path,
+ pointer_set_t *visited_bbs, loop_p loop)
+{
+ if (loop != start_bb->loop_father)
+ return false;
+
+ if (start_bb == end_bb)
+ {
+ vec_safe_push (path, start_bb);
+ return true;
+ }
+
+ if (!pointer_set_insert (visited_bbs, start_bb))
+ {
+ edge e;
+ edge_iterator ei;
+ FOR_EACH_EDGE (e, ei, start_bb->succs)
+ if (fsm_find_thread_path (e->dest, end_bb, path, visited_bbs, loop))
+ {
+ vec_safe_push (path, start_bb);
+ return true;
+ }
+ }
+
+ return false;
+}
+
+static int max_threaded_paths;
+
+/* We trace the value of the variable EXPR back through any phi nodes looking
+ for places where it gets a constant value and save the path. Stop after
+ having recorded MAX_PATHS jump threading paths. */
+
+static void
+fsm_find_control_statement_thread_paths (tree expr,
+ pointer_set_t *visited_bbs,
+ vec<basic_block, va_gc> *&path,
+ bool seen_loop_phi)
+{
+ tree var = SSA_NAME_VAR (expr);
+ gimple def_stmt = SSA_NAME_DEF_STMT (expr);
+ basic_block var_bb = gimple_bb (def_stmt);
+
+ if (var == NULL || var_bb == NULL)
+ return;
+
+ /* For the moment we assume that an SSA chain only contains phi nodes, and
+ eventually one of the phi arguments will be an integer constant. In the
+ future, this could be extended to also handle simple assignments of
+ arithmetic operations. */
+ if (gimple_code (def_stmt) != GIMPLE_PHI)
+ return;
+
+ /* Avoid infinite recursion. */
+ if (pointer_set_insert (visited_bbs, var_bb))
+ return;
+
+ int next_path_length = 0;
+ basic_block last_bb_in_path = path->last ();
+
+ if (loop_containing_stmt (def_stmt)->header == gimple_bb (def_stmt))
+ {
+ /* Do not walk through more than one loop PHI node. */
+ if (seen_loop_phi)
+ return;
+ seen_loop_phi = true;
+ }
+
+ /* Following the chain of SSA_NAME definitions, we jumped from a definition in
+ LAST_BB_IN_PATH to a definition in VAR_BB. When these basic blocks are
+ different, append to PATH the blocks from LAST_BB_IN_PATH to VAR_BB. */
+ if (var_bb != last_bb_in_path)
+ {
+ edge e;
+ int e_count = 0;
+ edge_iterator ei;
+ vec<basic_block, va_gc> *next_path;
+ vec_alloc (next_path, n_basic_blocks_for_fn (cfun));
+
+ FOR_EACH_EDGE (e, ei, last_bb_in_path->preds)
+ {
+ pointer_set_t *visited_bbs = pointer_set_create ();
+
+ if (fsm_find_thread_path (var_bb, e->src, next_path, visited_bbs,
+ e->src->loop_father))
+ ++e_count;
+
+ pointer_set_destroy (visited_bbs);
+
+ /* If there is more than one path, stop. */
+ if (e_count > 1)
+ {
+ vec_free (next_path);
+ return;
+ }
+ }
+
+ /* Stop if we have not found a path: this could occur when the recursion
+ is stopped by one of the bounds. */
+ if (e_count == 0)
+ {
+ vec_free (next_path);
+ return;
+ }
+
+ /* Append all the nodes from NEXT_PATH to PATH. */
+ vec_safe_splice (path, next_path);
+ next_path_length = next_path->length ();
+ vec_free (next_path);
+ }
+
+ gcc_assert (path->last () == var_bb);
+
+ /* Iterate over the arguments of PHI. */
+ unsigned int i;
+ for (i = 0; i < gimple_phi_num_args (def_stmt); i++)
+ {
+ tree arg = gimple_phi_arg_def (def_stmt, i);
+ basic_block bbi = gimple_phi_arg_edge (def_stmt, i)->src;
+
+ /* Skip edges pointing outside the current loop. */
+ if (!arg || var_bb->loop_father != bbi->loop_father)
+ continue;
+
+ if (TREE_CODE (arg) == SSA_NAME)
+ {
+ vec_safe_push (path, bbi);
+ /* Recursively follow SSA_NAMEs looking for a constant definition. */
+ fsm_find_control_statement_thread_paths (arg, visited_bbs, path,
+ seen_loop_phi);
+
+ path->pop ();
+ continue;
+ }
+
+ if (TREE_CODE (arg) != INTEGER_CST)
+ continue;
+
+ int path_length = path->length ();
+ /* A path with less than 2 basic blocks should not be jump-threaded. */
+ if (path_length < 2)
+ continue;
+
+ if (path_length > PARAM_VALUE (PARAM_MAX_FSM_THREAD_LENGTH))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "FSM jump-thread path not considered: "
+ "the number of basic blocks on the path "
+ "exceeds PARAM_MAX_FSM_THREAD_LENGTH.\n");
+ continue;
+ }
+
+ if (max_threaded_paths <= 0)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "FSM jump-thread path not considered: "
+ "the number of previously recorded FSM paths to thread "
+ "exceeds PARAM_MAX_FSM_THREAD_PATHS.\n");
+ continue;
+ }
+
+ /* Add BBI to the path. */
+ vec_safe_push (path, bbi);
+ ++path_length;
+
+ int n_insns = 0;
+ gimple_stmt_iterator gsi;
+ int j;
+ loop_p loop = (*path)[0]->loop_father;
+ bool path_crosses_loops = false;
+
+ /* Count the number of instructions on the path: as these instructions
+ will have to be duplicated, we will not record the path if there are
+ too many instructions on the path. Also check that all the blocks in
+ the path belong to a single loop. */
+ for (j = 1; j < path_length - 1; j++)
+ {
+ basic_block bb = (*path)[j];
+
+ if (bb->loop_father != loop)
+ {
+ path_crosses_loops = true;
+ break;
+ }
+
+ for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ {
+ gimple stmt = gsi_stmt (gsi);
+ /* Do not count empty statements and labels. */
+ if (gimple_code (stmt) != GIMPLE_NOP
+ && gimple_code (stmt) != GIMPLE_LABEL
+ && !is_gimple_debug (stmt))
+ ++n_insns;
+ }
+ }
+
+ if (path_crosses_loops)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "FSM jump-thread path not considered: "
+ "the path crosses loops.\n");
+ path->pop ();
+ continue;
+ }
+
+ if (n_insns >= PARAM_VALUE (PARAM_MAX_FSM_THREAD_PATH_INSNS))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "FSM jump-thread path not considered: "
+ "the number of instructions on the path "
+ "exceeds PARAM_MAX_FSM_THREAD_PATH_INSNS.\n");
+ path->pop ();
+ continue;
+ }
+
+ vec<jump_thread_edge *> *jump_thread_path
+ = new vec<jump_thread_edge *> ();
+
+ /* Record the edges between the blocks in PATH. */
+ for (j = 0; j < path_length - 1; j++)
+ {
+ edge e = find_edge ((*path)[path_length - j - 1],
+ (*path)[path_length - j - 2]);
+ gcc_assert (e);
+ jump_thread_edge *x = new jump_thread_edge (e, EDGE_FSM_THREAD);
+ jump_thread_path->safe_push (x);
+ }
+
+ /* Add the edge taken when the control variable has value ARG. */
+ edge taken_edge = find_taken_edge ((*path)[0], arg);
+ jump_thread_edge *x
+ = new jump_thread_edge (taken_edge, EDGE_NO_COPY_SRC_BLOCK);
+ jump_thread_path->safe_push (x);
+
+ register_jump_thread (jump_thread_path);
+ --max_threaded_paths;
+
+ /* Remove BBI from the path. */
+ path->pop ();
+ }
+
+ /* Remove all the nodes that we added from NEXT_PATH. */
+ if (next_path_length)
+ vec_safe_truncate (path, (path->length () - next_path_length));
+}
+
/* We are exiting E->src, see if E->dest ends with a conditional
jump which has a known value when reached via E.
@@ -982,7 +1243,10 @@ thread_through_normal_block (edge e,
cond = simplify_control_stmt_condition (e, stmt, dummy_cond, simplify,
handle_dominating_asserts);
- if (cond && is_gimple_min_invariant (cond))
+ if (!cond)
+ return 0;
+
+ if (is_gimple_min_invariant (cond))
{
edge taken_edge = find_taken_edge (e->dest, cond);
basic_block dest = (taken_edge ? taken_edge->dest : NULL);
@@ -1028,6 +1292,28 @@ thread_through_normal_block (edge e,
backedge_seen_p);
return 1;
}
+
+ if (!flag_expensive_optimizations
+ || optimize_function_for_size_p (cfun)
+ || TREE_CODE (cond) != SSA_NAME
+ || e->dest->loop_father != e->src->loop_father
+ || loop_depth (e->dest->loop_father) == 0)
+ return 0;
+
+ /* When COND cannot be simplified, try to find paths from a control
+ statement back through the PHI nodes which would affect that control
+ statement. */
+ vec<basic_block, va_gc> *bb_path;
+ vec_alloc (bb_path, n_basic_blocks_for_fn (cfun));
+ vec_safe_push (bb_path, e->dest);
+ pointer_set_t *visited_bbs = pointer_set_create ();
+
+ max_threaded_paths = PARAM_VALUE (PARAM_MAX_FSM_THREAD_PATHS);
+ fsm_find_control_statement_thread_paths (cond, visited_bbs, bb_path,
+ false);
+
+ pointer_set_destroy (visited_bbs);
+ vec_free (bb_path);
}
return 0;
}
diff --git a/gcc-4.9/gcc/tree-ssa-threadupdate.c b/gcc-4.9/gcc/tree-ssa-threadupdate.c
index f458d6a99..c2f02a6ab 100644
--- a/gcc-4.9/gcc/tree-ssa-threadupdate.c
+++ b/gcc-4.9/gcc/tree-ssa-threadupdate.c
@@ -156,8 +156,9 @@ dump_jump_thread_path (FILE *dump_file, vec<jump_thread_edge *> path,
bool registering)
{
fprintf (dump_file,
- " %s jump thread: (%d, %d) incoming edge; ",
+ " %s%s jump thread: (%d, %d) incoming edge; ",
(registering ? "Registering" : "Cancelling"),
+ (path[0]->type == EDGE_FSM_THREAD ? " FSM": ""),
path[0]->e->src->index, path[0]->e->dest->index);
for (unsigned int i = 1; i < path.length (); i++)
@@ -1622,6 +1623,211 @@ bb_ends_with_multiway_branch (basic_block bb ATTRIBUTE_UNUSED)
return false;
}
+/* Verify that the REGION is a valid jump thread. A jump thread is a special
+ case of SEME Single Entry Multiple Exits region in which all nodes in the
+ REGION have exactly one incoming edge. The only exception is the first block
+ that may not have been connected to the rest of the cfg yet. */
+
+DEBUG_FUNCTION void
+verify_jump_thread (basic_block *region, unsigned n_region)
+{
+ for (unsigned i = 0; i < n_region; i++)
+ gcc_assert (EDGE_COUNT (region[i]->preds) <= 1);
+}
+
+/* Return true when BB is one of the first N items in BBS. */
+
+static inline bool
+bb_in_bbs (basic_block bb, basic_block *bbs, int n)
+{
+ for (int i = 0; i < n; i++)
+ if (bb == bbs[i])
+ return true;
+
+ return false;
+}
+
+/* Duplicates a jump-thread path of N_REGION basic blocks.
+ The ENTRY edge is redirected to the duplicate of the region.
+
+ Remove the last conditional statement in the last basic block in the REGION,
+ and create a single fallthru edge pointing to the same destination as the
+ EXIT edge.
+
+ The new basic blocks are stored to REGION_COPY in the same order as they had
+ in REGION, provided that REGION_COPY is not NULL.
+
+ Returns false if it is unable to copy the region, true otherwise. */
+
+static bool
+duplicate_thread_path (edge entry, edge exit,
+ basic_block *region, unsigned n_region,
+ basic_block *region_copy)
+{
+ unsigned i;
+ bool free_region_copy = false, copying_header = false;
+ struct loop *loop = entry->dest->loop_father;
+ edge exit_copy;
+ edge redirected;
+ int total_freq = 0, entry_freq = 0;
+ gcov_type total_count = 0, entry_count = 0;
+
+ if (!can_copy_bbs_p (region, n_region))
+ return false;
+
+ /* Some sanity checking. Note that we do not check for all possible
+ missuses of the functions. I.e. if you ask to copy something weird,
+ it will work, but the state of structures probably will not be
+ correct. */
+ for (i = 0; i < n_region; i++)
+ {
+ /* We do not handle subloops, i.e. all the blocks must belong to the
+ same loop. */
+ if (region[i]->loop_father != loop)
+ return false;
+ }
+
+ initialize_original_copy_tables ();
+
+ if (copying_header)
+ set_loop_copy (loop, loop_outer (loop));
+ else
+ set_loop_copy (loop, loop);
+
+ if (!region_copy)
+ {
+ region_copy = XNEWVEC (basic_block, n_region);
+ free_region_copy = true;
+ }
+
+ if (entry->dest->count)
+ {
+ total_count = entry->dest->count;
+ entry_count = entry->count;
+ /* Fix up corner cases, to avoid division by zero or creation of negative
+ frequencies. */
+ if (entry_count > total_count)
+ entry_count = total_count;
+ }
+ else
+ {
+ total_freq = entry->dest->frequency;
+ entry_freq = EDGE_FREQUENCY (entry);
+ /* Fix up corner cases, to avoid division by zero or creation of negative
+ frequencies. */
+ if (total_freq == 0)
+ total_freq = 1;
+ else if (entry_freq > total_freq)
+ entry_freq = total_freq;
+ }
+
+ copy_bbs (region, n_region, region_copy, &exit, 1, &exit_copy, loop,
+ split_edge_bb_loc (entry), false);
+
+ /* Fix up: copy_bbs redirects all edges pointing to copied blocks. The
+ following code ensures that all the edges exiting the jump-thread path are
+ redirected back to the original code: these edges are exceptions
+ invalidating the property that is propagated by executing all the blocks of
+ the jump-thread path in order. */
+
+ for (i = 0; i < n_region; i++)
+ {
+ edge e;
+ edge_iterator ei;
+ basic_block bb = region_copy[i];
+
+ if (single_succ_p (bb))
+ {
+ /* Make sure the successor is the next node in the path. */
+ gcc_assert (i + 1 == n_region
+ || region_copy[i + 1] == single_succ_edge (bb)->dest);
+ continue;
+ }
+
+ /* Special case the last block on the path: make sure that it does not
+ jump back on the copied path. */
+ if (i + 1 == n_region)
+ {
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ if (bb_in_bbs (e->dest, region_copy, n_region - 1))
+ {
+ basic_block orig = get_bb_original (e->dest);
+ if (orig)
+ redirect_edge_and_branch_force (e, orig);
+ }
+ continue;
+ }
+
+ /* Redirect all other edges jumping to non-adjacent blocks back to the
+ original code. */
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ if (region_copy[i + 1] != e->dest)
+ {
+ basic_block orig = get_bb_original (e->dest);
+ if (orig)
+ redirect_edge_and_branch_force (e, orig);
+ }
+ }
+
+ if (total_count)
+ {
+ scale_bbs_frequencies_gcov_type (region, n_region,
+ total_count - entry_count,
+ total_count);
+ scale_bbs_frequencies_gcov_type (region_copy, n_region, entry_count,
+ total_count);
+ }
+ else
+ {
+ scale_bbs_frequencies_int (region, n_region, total_freq - entry_freq,
+ total_freq);
+ scale_bbs_frequencies_int (region_copy, n_region, entry_freq, total_freq);
+ }
+
+#ifdef ENABLE_CHECKING
+ verify_jump_thread (region_copy, n_region);
+#endif
+
+ /* Remove the last branch in the jump thread path. */
+ remove_ctrl_stmt_and_useless_edges (region_copy[n_region - 1], exit->dest);
+ edge e = make_edge (region_copy[n_region - 1], exit->dest, EDGE_FALLTHRU);
+
+ if (e) {
+ rescan_loop_exit (e, true, false);
+ e->probability = REG_BR_PROB_BASE;
+ e->count = region_copy[n_region - 1]->count;
+ }
+
+ /* Redirect the entry and add the phi node arguments. */
+ redirected = redirect_edge_and_branch (entry, get_bb_copy (entry->dest));
+ gcc_assert (redirected != NULL);
+ flush_pending_stmts (entry);
+
+ /* Add the other PHI node arguments. */
+ add_phi_args_after_copy (region_copy, n_region, NULL);
+
+ if (free_region_copy)
+ free (region_copy);
+
+ free_original_copy_tables ();
+ return true;
+}
+
+/* Return true when PATH is a valid jump-thread path. */
+
+static bool
+valid_jump_thread_path (vec<jump_thread_edge *> *path)
+{
+ unsigned len = path->length ();
+
+ /* Check that the path is connected. */
+ for (unsigned int j = 0; j < len - 1; j++)
+ if ((*path)[j]->e->dest != (*path)[j+1]->e->src)
+ return false;
+
+ return true;
+}
+
/* Walk through all blocks and thread incoming edges to the appropriate
outgoing edge for each edge pair recorded in THREADED_EDGES.
@@ -1651,6 +1857,70 @@ thread_through_all_blocks (bool may_peel_loop_headers)
threaded_blocks = BITMAP_ALLOC (NULL);
memset (&thread_stats, 0, sizeof (thread_stats));
+ /* Jump-thread all FSM threads before other jump-threads. */
+ for (i = 0; i < paths.length ();)
+ {
+ vec<jump_thread_edge *> *path = paths[i];
+ edge entry = (*path)[0]->e;
+
+ /* Only code-generate FSM jump-threads in this loop. */
+ if ((*path)[0]->type != EDGE_FSM_THREAD)
+ {
+ i++;
+ continue;
+ }
+
+ /* Do not jump-thread twice from the same block. */
+ if (bitmap_bit_p (threaded_blocks, entry->src->index)
+ /* Verify that the jump thread path is still valid: a
+ previous jump-thread may have changed the CFG, and
+ invalidated the current path. */
+ || !valid_jump_thread_path (path))
+ {
+ /* Remove invalid FSM jump-thread paths. */
+ delete_jump_thread_path (path);
+ paths.unordered_remove (i);
+ continue;
+ }
+
+ unsigned len = path->length ();
+ edge exit = (*path)[len - 1]->e;
+ basic_block *region = XNEWVEC (basic_block, len - 1);
+
+ for (unsigned int j = 0; j < len - 1; j++)
+ region[j] = (*path)[j]->e->dest;
+
+ if (duplicate_thread_path (entry, exit, region, len - 1, NULL))
+ {
+ /* We do not update dominance info. */
+ free_dominance_info (CDI_DOMINATORS);
+ bitmap_set_bit (threaded_blocks, entry->src->index);
+ retval = true;
+ }
+
+ delete_jump_thread_path (path);
+ paths.unordered_remove (i);
+ }
+
+ /* Remove from PATHS all the jump-threads starting with an edge already
+ jump-threaded. */
+ for (i = 0; i < paths.length ();)
+ {
+ vec<jump_thread_edge *> *path = paths[i];
+ edge entry = (*path)[0]->e;
+
+ /* Do not jump-thread twice from the same block. */
+ if (bitmap_bit_p (threaded_blocks, entry->src->index))
+ {
+ delete_jump_thread_path (path);
+ paths.unordered_remove (i);
+ }
+ else
+ i++;
+ }
+
+ bitmap_clear (threaded_blocks);
+
mark_threaded_blocks (threaded_blocks);
initialize_original_copy_tables ();
diff --git a/gcc-4.9/gcc/tree-ssa-threadupdate.h b/gcc-4.9/gcc/tree-ssa-threadupdate.h
index 426aca5e6..22c5bceb9 100644
--- a/gcc-4.9/gcc/tree-ssa-threadupdate.h
+++ b/gcc-4.9/gcc/tree-ssa-threadupdate.h
@@ -26,6 +26,7 @@ extern bool thread_through_all_blocks (bool);
enum jump_thread_edge_type
{
EDGE_START_JUMP_THREAD,
+ EDGE_FSM_THREAD,
EDGE_COPY_SRC_BLOCK,
EDGE_COPY_SRC_JOINER_BLOCK,
EDGE_NO_COPY_SRC_BLOCK