This patch conveys information about the blocks/edges in a jump
threading path. Of particular interest is information about the source
block in each edge of the path -- the nature of the block determines our
copy strategy (empty -- no copy, normal copy, joiner copy).
Rather than rediscover the nature of those blocks during the CFG/SSA
graph updating, it's easier to just attach the information to each edge
in the path. That's precisely what this patch does.
The SSA/CFG updating code isn't making much use of this yet, that's a
follow-on change. This change is strictly designed to get the
information into the updating code.
Bootstrapped and regression tested on x86_64-unknown-linux-gnu.
Installed on trunk.
diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 5adbaeb..8871aca 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,26 @@
+2013-09-25 Jeff Law <l...@redhat.com>
+
+ * tree-flow.h (thread_through_all_blocks): Prototype moved into
+ tree-ssa-threadupdate.h.
+ (register_jump_thread): Similarly.
+ * tree-ssa-threadupdate.h: New header file.
+ * tree-ssa-dom.c: Include tree-ssa-threadupdate.h.
+ * tree-vrp.c: Likewise.
+ * tree-ssa-threadedge.c: Include tree-ssa-threadupdate.h.
+ (thread_around_empty_blocks): Change type of path vector argument to
+ an edge,type pair from just an edge. Initialize both elements when
+ appending to a jump threading path. Tweak references to elements
+ appropriately.
+ (thread_across_edge): Similarly. Release memory for the elements
+ as needed.
+ * tree-ssa-threadupdate.c: Include tree-ssa-threadupdate.h.
+ (dump_jump_thread_path): New function broken out from
+ register_jump_thread.
+ (register_jump_thread): Use dump_jump_thread_path. Change type of
+ path vector entries. Search the path for NULL edges and dump
+ the path if one is found. Tweak the conversion of path to 3-edge
+ form to use the block copy type information embedded in the path.
+
2013-09-25 Yvan Roux <yvan.r...@linaro.org>
* lra.c (update_inc_notes): Remove all REG_DEAD and REG_UNUSED notes.
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 634e747..a264056 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,6 @@
+2013-09-25 Jeff Law <l...@redhat.com>
+
+ * gcc.dg/tree-ssa/ssa-dom-thread-3.c: Update expected output.
2013-09-25 Tobias Burnus <bur...@net-b.de>
PR fortran/58436
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-3.c
b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-3.c
index d2a1fbb..222a97b 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-3.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-3.c
@@ -43,7 +43,6 @@ expand_one_var (tree var, unsigned char toplevel, unsigned
char really_expand)
}
/* We should thread the jump, through an intermediate block. */
/* { dg-final { scan-tree-dump-times "Threaded" 1 "dom1"} } */
-/* { dg-final { scan-tree-dump-times "Registering jump thread .through joiner
block.: \\(.*\\); \\(.*\\); \\(.*\\);" 1 "dom1"} } */
-
+/* { dg-final { scan-tree-dump-times "Registering jump thread: \\(.*\\)
incoming edge; \\(.*\\) joiner; \\(.*\\) nocopy;" 1 "dom1"} } */
/* { dg-final { cleanup-tree-dump "dom1" } } */
diff --git a/gcc/tree-flow.h b/gcc/tree-flow.h
index 2f64abc..ee69179 100644
--- a/gcc/tree-flow.h
+++ b/gcc/tree-flow.h
@@ -641,10 +641,6 @@ bool multiplier_allowed_in_address_p (HOST_WIDE_INT, enum
machine_mode,
addr_space_t);
bool may_be_nonaddressable_p (tree expr);
-/* In tree-ssa-threadupdate.c. */
-extern bool thread_through_all_blocks (bool);
-extern void register_jump_thread (vec<edge>, bool);
-
/* In gimplify.c */
tree force_gimple_operand_1 (tree, gimple_seq *, gimple_predicate, tree);
tree force_gimple_operand (tree, gimple_seq *, bool, tree);
diff --git a/gcc/tree-ssa-dom.c b/gcc/tree-ssa-dom.c
index f0cc0ee..81119c3 100644
--- a/gcc/tree-ssa-dom.c
+++ b/gcc/tree-ssa-dom.c
@@ -34,6 +34,7 @@ along with GCC; see the file COPYING3. If not see
#include "domwalk.h"
#include "tree-pass.h"
#include "tree-ssa-propagate.h"
+#include "tree-ssa-threadupdate.h"
#include "langhooks.h"
#include "params.h"
diff --git a/gcc/tree-ssa-threadedge.c b/gcc/tree-ssa-threadedge.c
index 2ca56342..467d982 100644
--- a/gcc/tree-ssa-threadedge.c
+++ b/gcc/tree-ssa-threadedge.c
@@ -32,6 +32,7 @@ along with GCC; see the file COPYING3. If not see
#include "dumpfile.h"
#include "tree-ssa.h"
#include "tree-ssa-propagate.h"
+#include "tree-ssa-threadupdate.h"
#include "langhooks.h"
#include "params.h"
@@ -753,7 +754,7 @@ thread_around_empty_blocks (edge taken_edge,
bool handle_dominating_asserts,
tree (*simplify) (gimple, gimple),
bitmap visited,
- vec<edge> *path)
+ vec<jump_thread_edge *> *path)
{
basic_block bb = taken_edge->dest;
gimple_stmt_iterator gsi;
@@ -791,8 +792,10 @@ thread_around_empty_blocks (edge taken_edge,
if ((taken_edge->flags & EDGE_DFS_BACK) == 0
&& !bitmap_bit_p (visited, taken_edge->dest->index))
{
+ jump_thread_edge *x
+ = new jump_thread_edge (taken_edge, EDGE_NO_COPY_SRC_BLOCK);
+ path->safe_push (x);
bitmap_set_bit (visited, taken_edge->dest->index);
- path->safe_push (taken_edge);
return thread_around_empty_blocks (taken_edge,
dummy_cond,
handle_dominating_asserts,
@@ -828,7 +831,11 @@ thread_around_empty_blocks (edge taken_edge,
if (bitmap_bit_p (visited, taken_edge->dest->index))
return false;
bitmap_set_bit (visited, taken_edge->dest->index);
- path->safe_push (taken_edge);
+
+ jump_thread_edge *x
+ = new jump_thread_edge (taken_edge, EDGE_NO_COPY_SRC_BLOCK);
+ path->safe_push (x);
+
thread_around_empty_blocks (taken_edge,
dummy_cond,
handle_dominating_asserts,
@@ -922,9 +929,13 @@ thread_across_edge (gimple dummy_cond,
if (dest == NULL || dest == e->dest)
goto fail;
- vec<edge> path = vNULL;
- path.safe_push (e);
- path.safe_push (taken_edge);
+ vec<jump_thread_edge *> path = vNULL;
+ jump_thread_edge *x
+ = new jump_thread_edge (e, EDGE_START_JUMP_THREAD);
+ path.safe_push (x);
+
+ x = new jump_thread_edge (taken_edge, EDGE_COPY_SRC_BLOCK);
+ path.safe_push (x);
/* See if we can thread through DEST as well, this helps capture
secondary effects of threading without having to re-run DOM or
@@ -947,8 +958,11 @@ thread_across_edge (gimple dummy_cond,
}
remove_temporary_equivalences (stack);
- propagate_threaded_block_debug_into (path.last ()->dest, e->dest);
- register_jump_thread (path, false);
+ propagate_threaded_block_debug_into (path.last ()->e->dest,
+ e->dest);
+ register_jump_thread (path);
+ for (unsigned int i = 0; i < path.length (); i++)
+ delete path[i];
path.release ();
return;
}
@@ -978,15 +992,18 @@ thread_across_edge (gimple dummy_cond,
bitmap_clear (visited);
bitmap_set_bit (visited, taken_edge->dest->index);
bitmap_set_bit (visited, e->dest->index);
- vec<edge> path = vNULL;
+ vec<jump_thread_edge *> path = vNULL;
/* Record whether or not we were able to thread through a successor
of E->dest. */
- path.safe_push (e);
- path.safe_push (taken_edge);
+ jump_thread_edge *x = new jump_thread_edge (e, EDGE_START_JUMP_THREAD);
+ path.safe_push (x);
+
+ x = new jump_thread_edge (taken_edge, EDGE_COPY_SRC_JOINER_BLOCK);
+ path.safe_push (x);
found = false;
if ((e->flags & EDGE_DFS_BACK) == 0
- || ! cond_arg_set_in_bb (path.last (), e->dest))
+ || ! cond_arg_set_in_bb (path.last ()->e, e->dest))
found = thread_around_empty_blocks (taken_edge,
dummy_cond,
handle_dominating_asserts,
@@ -998,11 +1015,13 @@ thread_across_edge (gimple dummy_cond,
record the jump threading opportunity. */
if (found)
{
- propagate_threaded_block_debug_into (path.last ()->dest,
+ propagate_threaded_block_debug_into (path.last ()->e->dest,
taken_edge->dest);
- register_jump_thread (path, true);
+ register_jump_thread (path);
}
+ for (unsigned int i = 0; i < path.length (); i++)
+ delete path[i];
path.release();
}
BITMAP_FREE (visited);
diff --git a/gcc/tree-ssa-threadupdate.c b/gcc/tree-ssa-threadupdate.c
index fd5234c..75273ca 100644
--- a/gcc/tree-ssa-threadupdate.c
+++ b/gcc/tree-ssa-threadupdate.c
@@ -27,6 +27,7 @@ along with GCC; see the file COPYING3. If not see
#include "basic-block.h"
#include "function.h"
#include "tree-ssa.h"
+#include "tree-ssa-threadupdate.h"
#include "dumpfile.h"
#include "cfgloop.h"
#include "hash-table.h"
@@ -1380,6 +1381,39 @@ thread_through_all_blocks (bool may_peel_loop_headers)
return retval;
}
+/* Dump a jump threading path, including annotations about each
+ edge in the path. */
+
+static void
+dump_jump_thread_path (FILE *dump_file, vec<jump_thread_edge *> path)
+{
+ fprintf (dump_file,
+ " Registering jump thread: (%d, %d) incoming edge; ",
+ path[0]->e->src->index, path[0]->e->dest->index);
+
+ for (unsigned int i = 1; i < path.length (); i++)
+ {
+ /* We can get paths with a NULL edge when the final destination
+ of a jump thread turns out to be a constant address. We dump
+ those paths when debugging, so we have to be prepared for that
+ possibility here. */
+ if (path[i]->e == NULL)
+ continue;
+
+ if (path[i]->type == EDGE_COPY_SRC_JOINER_BLOCK)
+ fprintf (dump_file, " (%d, %d) joiner; ",
+ path[i]->e->src->index, path[i]->e->dest->index);
+ if (path[i]->type == EDGE_COPY_SRC_BLOCK)
+ fprintf (dump_file, " (%d, %d) normal;",
+ path[i]->e->src->index, path[i]->e->dest->index);
+ if (path[i]->type == EDGE_NO_COPY_SRC_BLOCK)
+ fprintf (dump_file, " (%d, %d) nocopy;",
+ path[i]->e->src->index, path[i]->e->dest->index);
+ }
+ fputc ('\n', dump_file);
+}
+
+
/* Register a jump threading opportunity. We queue up all the jump
threading opportunities discovered by a pass and update the CFG
and SSA form all at once.
@@ -1389,43 +1423,47 @@ thread_through_all_blocks (bool may_peel_loop_headers)
after fixing the SSA graph. */
void
-register_jump_thread (vec<edge> path, bool through_joiner)
+register_jump_thread (vec<jump_thread_edge *> path)
{
- /* Convert PATH into 3 edge representation we've been using. This
- is temporary until we convert this file to use a path representation
- throughout. */
- edge e = path[0];
- edge e2 = path[1];
- edge e3;
-
- if (!through_joiner)
- e3 = NULL;
- else
- e3 = path.last ();
+ /* First make sure there are no NULL outgoing edges on the jump threading
+ path. That can happen for jumping to a constant address. */
+ for (unsigned int i = 0; i < path.length (); i++)
+ if (path[i]->e == NULL)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file,
+ "Found NULL edge in jump threading path. Cancelling jump
thread:\n");
+ dump_jump_thread_path (dump_file, path);
+ }
+ return;
+ }
- /* This can occur if we're jumping to a constant address or
- or something similar. Just get out now. */
- if (e2 == NULL)
- return;
+ if (!threaded_edges.exists ())
+ threaded_edges.create (15);
if (dump_file && (dump_flags & TDF_DETAILS))
- {
- unsigned int i;
+ dump_jump_thread_path (dump_file, path);
- fprintf (dump_file,
- " Registering jump thread %s:",
- through_joiner ? "(through joiner block)" : "");
+ /* The first entry in the vector is always the start of the
+ jump threading path. */
+ threaded_edges.safe_push (path[0]->e);
- for (i = 0; i < path.length (); i++)
- fprintf (dump_file, " (%d, %d); ",
- path[i]->src->index, path[i]->dest->index);
- fputc ('\n', dump_file);
- }
-
- if (!threaded_edges.exists ())
- threaded_edges.create (15);
+ /* In our 3-edge representation, the joiner, if it exists is always the
+ 2nd edge and the final block on the path is the 3rd edge. If no
+ jointer exists, then the final block on the path is the 2nd edge
+ and the 3rd edge is NULL.
- threaded_edges.safe_push (e);
- threaded_edges.safe_push (e2);
- threaded_edges.safe_push (e3);
+ With upcoming improvements, we're going to be holding onto the entire
+ path, so we'll be able to clean this wart up shortly. */
+ if (path[1]->type == EDGE_COPY_SRC_JOINER_BLOCK)
+ {
+ threaded_edges.safe_push (path[1]->e);
+ threaded_edges.safe_push (path.last ()->e);
+ }
+ else
+ {
+ threaded_edges.safe_push (path.last ()->e);
+ threaded_edges.safe_push (NULL);
+ }
}
diff --git a/gcc/tree-ssa-threadupdate.h b/gcc/tree-ssa-threadupdate.h
new file mode 100644
index 0000000..723f5bb
--- /dev/null
+++ b/gcc/tree-ssa-threadupdate.h
@@ -0,0 +1,45 @@
+/* Communication between registering jump thread requests and
+ updating the SSA/CFG for jump threading.
+ Copyright (C) 2013 Free Software Foundation, Inc.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 3, or (at your option)
+any later version.
+
+GCC is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
+
+#ifndef _TREE_SSA_THREADUPDATE_H
+#define _TREE_SSA_THREADUPDATE_H 1
+
+/* In tree-ssa-threadupdate.c. */
+extern bool thread_through_all_blocks (bool);
+enum jump_thread_edge_type
+{
+ EDGE_START_JUMP_THREAD,
+ EDGE_COPY_SRC_BLOCK,
+ EDGE_COPY_SRC_JOINER_BLOCK,
+ EDGE_NO_COPY_SRC_BLOCK
+};
+
+class jump_thread_edge
+{
+public:
+ jump_thread_edge (edge e, enum jump_thread_edge_type type)
+ : e (e), type (type) {}
+
+ edge e;
+ enum jump_thread_edge_type type;
+};
+
+extern void register_jump_thread (vec<class jump_thread_edge *>);
+#endif
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 0d50af7..1600724 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -36,6 +36,7 @@ along with GCC; see the file COPYING3. If not see
#include "tree-scalar-evolution.h"
#include "tree-ssa-propagate.h"
#include "tree-chrec.h"
+#include "tree-ssa-threadupdate.h"
#include "gimple-fold.h"
#include "expr.h"
#include "optabs.h"
