On Thu, Dec 3, 2015 at 3:38 PM, Richard Biener
<richard.guent...@gmail.com> wrote:
> On Sat, Nov 14, 2015 at 12:35 AM, Jeff Law <l...@redhat.com> wrote:
>> On 11/13/2015 01:23 PM, Jeff Law wrote:
>>>
>>> On 11/13/2015 11:09 AM, Richard Biener wrote:
>>>
>>>>>
>>>>> BTW Do we have an API for indicating that new blocks have been added to
>>>>>
>>>>> a loop? If so, then we can likely drop the LOOPS_NEED_FIXUP.
>>>>
>>>>
>>>> Please. It's called add_to_loop or so.
>>>
>>> Haha, the block duplication code was handling this already. So in
>>> theory I can just drop the LOOPS_NEED_FIXUP completely. Testing now.
>>>
>>> jeff
>>>
>> Attached is the committed patch for path splitting. As noted above, we
>> didn't need the LOOPS_NEED_FIXUP in the final version, so that wart is gone
>> :-)
>>
>> I do find myself wondering if this can/should be generalized beyond just
>> paths heading to loop backedges. However to do so I think we'd need to be
>> able to undo this transformation reliably and we'd need some heuristics when
>> to duplicate to expose the redundancy vs rely on PRE techniques and jump
>> threading. I vaguely remember a paper which touched on these topics, but I
>> can't seem to find it.
>>
>> Anyway, bootstrapped and regression tested on x86_64-linux-gnu. Installed on
>> the trunk.
>
> This pass is now enabled by default with -Os but has no limits on the amount
> of
> stmts it copies. It also will make all loops with this shape have at least
> two
> exits (if the resulting loop will be disambiguated the inner loop will
> have two exits).
> Having more than one exit will disable almost all loop optimizations after it.
>
> The pass itself documents the transform it does but does zero to motivate it.
>
> What's the benefit of this pass (apart from disrupting further optimizations)?
>
> I can see a _single_ case where duplicating the latch will allow threading
> one of the paths through the loop header to eliminate the original exit. Then
> disambiguation may create a nice nested loop out of this. Of course that
> is only profitable again if you know the remaining single exit of the inner
> loop (exiting to the outer one) is executed infrequently (thus the inner loop
> actually loops).
>
> But no checks other than on the CFG shape exist (oh, it checks it will
> at _least_ copy two stmts!).
>
> Given the profitability constraints above (well, correct me if I am
> wrong on these)
> it looks like the whole transform should be done within the FSM threading
> code which might be able to compute whether there will be an inner loop
> with a single exit only.
>
> I'm inclined to request the pass to be removed again or at least disabled by
> default.
>
> What closed source benchmark was this transform invented for?
Ah, some EEMBC one.
Btw, the testcase that was added shows
if (xc < xm)
{
xk = (unsigned char) (xc < xy ? xc : xy);
}
else
{
xk = (unsigned char) (xm < xy ? xm : xy);
}
which might be better handled by phiopt transforming it into
xk = MIN (xc, MIN (xm, xy))
phiopt1 sees (hooray to GENERIC folding)
xc_26 = ~xr_21;
xm_27 = ~xg_23;
xy_28 = ~xb_25;
if (xr_21 > xg_23)
goto <bb 5>;
else
goto <bb 6>;
<bb 5>:
xk_29 = MIN_EXPR <xc_26, xy_28>;
goto <bb 7>;
<bb 6>:
xk_30 = MIN_EXPR <xm_27, xy_28>;
<bb 7>:
# xk_4 = PHI <xk_29(5), xk_30(6)>
btw, see PR67438 for a similar testcase and the above pattern.
Richard.
> Richard.
>
>>
>>
>>
>> commit c1891376e5dcc99ad8be2d22f9551c03f9bb2729
>> Author: Jeff Law <l...@redhat.com>
>> Date: Fri Nov 13 16:29:34 2015 -0700
>>
>> [Patch,tree-optimization]: Add new path Splitting pass on tree ssa
>> representation
>>
>> * Makefile.in (OBJS): Add gimple-ssa-split-paths.o
>> * common.opt (-fsplit-paths): New flag controlling path splitting.
>> * doc/invoke.texi (fsplit-paths): Document.
>> * opts.c (default_options_table): Add -fsplit-paths to -O2.
>> * passes.def: Add split_paths pass.
>> * timevar.def (TV_SPLIT_PATHS): New timevar.
>> * tracer.c: Include "tracer.h"
>> (ignore_bb_p): No longer static.
>> (transform_duplicate): New function, broken out of tail_duplicate.
>> (tail_duplicate): Use transform_duplicate.
>> * tracer.h (ignore_bb_p): Declare
>> (transform_duplicate): Likewise.
>> * tree-pass.h (make_pass_split_paths): Declare.
>> * gimple-ssa-split-paths.c: New file.
>>
>> * gcc.dg/tree-ssa/split-path-1.c: New test.
>>
>> diff --git a/gcc/ChangeLog b/gcc/ChangeLog
>> index dde2695..a7abe37 100644
>> --- a/gcc/ChangeLog
>> +++ b/gcc/ChangeLog
>> @@ -1,3 +1,21 @@
>> +2015-11-13 Ajit Agarwal <ajit...@xilinx.com>
>> + Jeff Law <l...@redhat.com>
>> +
>> + * Makefile.in (OBJS): Add gimple-ssa-split-paths.o
>> + * common.opt (-fsplit-paths): New flag controlling path splitting.
>> + * doc/invoke.texi (fsplit-paths): Document.
>> + * opts.c (default_options_table): Add -fsplit-paths to -O2.
>> + * passes.def: Add split_paths pass.
>> + * timevar.def (TV_SPLIT_PATHS): New timevar.
>> + * tracer.c: Include "tracer.h"
>> + (ignore_bb_p): No longer static.
>> + (transform_duplicate): New function, broken out of tail_duplicate.
>> + (tail_duplicate): Use transform_duplicate.
>> + * tracer.h (ignore_bb_p): Declare
>> + (transform_duplicate): Likewise.
>> + * tree-pass.h (make_pass_split_paths): Declare.
>> + * gimple-ssa-split-paths.c: New file.
>> +
>> 2015-11-13 Kai Tietz <ktiet...@googlemail.com>
>> Marek Polacek <pola...@redhat.com>
>> Jason Merrill <ja...@redhat.com>
>> diff --git a/gcc/Makefile.in b/gcc/Makefile.in
>> index d3fd5e9..5c294df 100644
>> --- a/gcc/Makefile.in
>> +++ b/gcc/Makefile.in
>> @@ -1277,6 +1277,7 @@ OBJS = \
>> gimple-pretty-print.o \
>> gimple-ssa-backprop.o \
>> gimple-ssa-isolate-paths.o \
>> + gimple-ssa-split-paths.o \
>> gimple-ssa-strength-reduction.o \
>> gimple-streamer-in.o \
>> gimple-streamer-out.o \
>> diff --git a/gcc/common.opt b/gcc/common.opt
>> index 757ce85..3eb520e 100644
>> --- a/gcc/common.opt
>> +++ b/gcc/common.opt
>> @@ -2403,6 +2403,10 @@ ftree-vrp
>> Common Report Var(flag_tree_vrp) Init(0) Optimization
>> Perform Value Range Propagation on trees.
>>
>> +fsplit-paths
>> +Common Report Var(flag_split_paths) Init(0) Optimization
>> +Split paths leading to loop backedges.
>> +
>> funit-at-a-time
>> Common Report Var(flag_unit_at_a_time) Init(1)
>> Compile whole compilation unit at a time.
>> diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
>> index c18df98..eeb79e6 100644
>> --- a/gcc/doc/invoke.texi
>> +++ b/gcc/doc/invoke.texi
>> @@ -354,6 +354,7 @@ Objective-C and Objective-C++ Dialects}.
>> -fdump-tree-fre@r{[}-@var{n}@r{]} @gol
>> -fdump-tree-vtable-verify @gol
>> -fdump-tree-vrp@r{[}-@var{n}@r{]} @gol
>> +-fdump-tree-split-paths@r{[}-@var{n}@r{]} @gol
>> -fdump-tree-storeccp@r{[}-@var{n}@r{]} @gol
>> -fdump-final-insns=@var{file} @gol
>> -fcompare-debug@r{[}=@var{opts}@r{]} -fcompare-debug-second @gol
>> @@ -448,6 +449,7 @@ Objective-C and Objective-C++ Dialects}.
>> -fsel-sched-pipelining -fsel-sched-pipelining-outer-loops @gol
>> -fsemantic-interposition -fshrink-wrap -fsignaling-nans @gol
>> -fsingle-precision-constant -fsplit-ivs-in-unroller @gol
>> +-fsplit-paths @gol
>> -fsplit-wide-types -fssa-backprop -fssa-phiopt @gol
>> -fstack-protector -fstack-protector-all -fstack-protector-strong @gol
>> -fstack-protector-explicit -fstdarg-opt -fstrict-aliasing @gol
>> @@ -7171,6 +7173,11 @@ output on to @file{stderr}. If two conflicting dump
>> filenames are
>> given for the same pass, then the latter option overrides the earlier
>> one.
>>
>> +@item split-paths
>> +@opindex fdump-tree-split-paths
>> +Dump each function after splitting paths to loop backedges. The file
>> +name is made by appending @file{.split-paths} to the source file name.
>> +
>> @item all
>> Turn on all options, except @option{raw}, @option{slim}, @option{verbose}
>> and @option{lineno}.
>> @@ -7808,6 +7815,7 @@ also turns on the following optimization flags:
>> -frerun-cse-after-loop @gol
>> -fsched-interblock -fsched-spec @gol
>> -fschedule-insns -fschedule-insns2 @gol
>> +-fsplit-paths @gol
>> -fstrict-aliasing -fstrict-overflow @gol
>> -ftree-builtin-call-dce @gol
>> -ftree-switch-conversion -ftree-tail-merge @gol
>> @@ -8821,7 +8829,7 @@ currently enabled, but may be enabled by @option{-O2}
>> in the future.
>>
>> @item -ftree-sink
>> @opindex ftree-sink
>> -Perform forward store motion on trees. This flag is
>> +Perform forward store motion on trees. This flag is
>> enabled by default at @option{-O} and higher.
>>
>> @item -ftree-bit-ccp
>> @@ -9127,6 +9135,12 @@ enabled by default at @option{-O2} and higher. Null
>> pointer check
>> elimination is only done if @option{-fdelete-null-pointer-checks} is
>> enabled.
>>
>> +@item -fsplit-paths
>> +@opindex fsplit-paths
>> +Split paths leading to loop backedges. This can improve dead code
>> +elimination and common subexpression elimination. This is enabled by
>> +default at @option{-O2} and above.
>> +
>> @item -fsplit-ivs-in-unroller
>> @opindex fsplit-ivs-in-unroller
>> Enables expression of values of induction variables in later iterations
>> diff --git a/gcc/gimple-ssa-split-paths.c b/gcc/gimple-ssa-split-paths.c
>> new file mode 100644
>> index 0000000..602e916
>> --- /dev/null
>> +++ b/gcc/gimple-ssa-split-paths.c
>> @@ -0,0 +1,270 @@
>> +/* Support routines for Splitting Paths to loop backedges
>> + Copyright (C) 2015 Free Software Foundation, Inc.
>> + Contributed by Ajit Kumar Agarwal <ajit...@xilinx.com>.
>> +
>> + 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/>. */
>> +
>> +#include "config.h"
>> +#include "system.h"
>> +#include "coretypes.h"
>> +#include "backend.h"
>> +#include "tree.h"
>> +#include "gimple.h"
>> +#include "tree-pass.h"
>> +#include "cfganal.h"
>> +#include "cfgloop.h"
>> +#include "gimple-iterator.h"
>> +#include "tracer.h"
>> +
>> +/* Given LATCH, the latch block in a loop, see if the shape of the
>> + path reaching LATCH is suitable for being split by duplication.
>> + If so, return the block that will be duplicated into its predecessor
>> + paths. Else return NULL. */
>> +
>> +static basic_block
>> +find_block_to_duplicate_for_splitting_paths (basic_block latch)
>> +{
>> + /* We should have simple latches at this point. So the latch should
>> + have a single successor. This implies the predecessor of the latch
>> + likely has the loop exit. And it's that predecessor we're most
>> + interested in. To keep things simple, we're going to require that
>> + the latch have a single predecessor too. */
>> + if (single_succ_p (latch) && single_pred_p (latch))
>> + {
>> + basic_block bb = get_immediate_dominator (CDI_DOMINATORS, latch);
>> + gcc_assert (single_pred_edge (latch)->src == bb);
>> +
>> + /* If BB has been marked as not to be duplicated, then honor that
>> + request. */
>> + if (ignore_bb_p (bb))
>> + return NULL;
>> +
>> + gimple *last = gsi_stmt (gsi_last_nondebug_bb (bb));
>> + /* The immediate dominator of the latch must end in a conditional.
>> */
>> + if (!last || gimple_code (last) != GIMPLE_COND)
>> + return NULL;
>> +
>> + /* We're hoping that BB is a join point for an IF-THEN-ELSE diamond
>> + region. Verify that it is.
>> +
>> + First, verify that BB has two predecessors (each arm of the
>> + IF-THEN-ELSE) and two successors (the latch and exit). */
>> + if (EDGE_COUNT (bb->preds) == 2 && EDGE_COUNT (bb->succs) == 2)
>> + {
>> + /* Now verify that BB's immediate dominator ends in a
>> + conditional as well. */
>> + basic_block bb_idom = get_immediate_dominator (CDI_DOMINATORS,
>> bb);
>> + gimple *last = gsi_stmt (gsi_last_nondebug_bb (bb_idom));
>> + if (!last || gimple_code (last) != GIMPLE_COND)
>> + return NULL;
>> +
>> + /* And that BB's immediate dominator's successors are the
>> + the predecessors of BB. */
>> + if (!find_edge (bb_idom, EDGE_PRED (bb, 0)->src)
>> + || !find_edge (bb_idom, EDGE_PRED (bb, 1)->src))
>> + return NULL;
>> +
>> + /* So at this point we have a simple diamond for an IF-THEN-ELSE
>> + construct starting at BB_IDOM, with a join point at BB. BB
>> + pass control outside the loop or to the loop latch.
>> +
>> + We're going to want to create two duplicates of BB, one for
>> + each successor of BB_IDOM. */
>> + return bb;
>> + }
>> + }
>> + return NULL;
>> +}
>> +
>> +/* Return TRUE if BB is a reasonable block to duplicate by examining
>> + its size, false otherwise. BB will always be a loop latch block.
>> +
>> + Should this use the same tests as we do for jump threading? */
>> +
>> +static bool
>> +is_feasible_trace (basic_block bb)
>> +{
>> + int num_stmt = 0;
>> + gimple_stmt_iterator gsi;
>> +
>> + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
>> + {
>> + gimple *stmt = gsi_stmt (gsi);
>> + if (!is_gimple_debug (stmt))
>> + num_stmt++;
>> + }
>> +
>> + /* We may want to limit how many statements we copy. */
>> + if (num_stmt > 1)
>> + return true;
>> +
>> + return false;
>> +}
>> +
>> +/* If the immediate dominator of the latch of the loop is
>> + block with conditional branch, then the loop latch is
>> + duplicated to its predecessors path preserving the SSA
>> + semantics.
>> +
>> + CFG before transformation.
>> +
>> + 2
>> + |
>> + |
>> + +---->3
>> + | / \
>> + | / \
>> + | 4 5
>> + | \ /
>> + | \ /
>> + | 6
>> + | / \
>> + | / \
>> + | 8 7
>> + | | |
>> + ---+ E
>> +
>> +
>> +
>> + Block 8 is the latch. We're going to make copies of block 6 (9 & 10)
>> + and wire things up so they look like this:
>> +
>> + 2
>> + |
>> + |
>> + +---->3
>> + | / \
>> + | / \
>> + | 4 5
>> + | | |
>> + | | |
>> + | 9 10
>> + | |\ /|
>> + | | \ / |
>> + | | 7 |
>> + | | | |
>> + | | E |
>> + | | |
>> + | \ /
>> + | \ /
>> + +-----8
>> +
>> +
>> + Blocks 9 and 10 will get merged into blocks 4 & 5 respectively which
>> + enables CSE, DCE and other optimizations to occur on a larger block
>> + of code. */
>> +
>> +static bool
>> +split_paths ()
>> +{
>> + bool changed = false;
>> + loop_p loop;
>> +
>> + loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
>> + initialize_original_copy_tables ();
>> + calculate_dominance_info (CDI_DOMINATORS);
>> +
>> + FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
>> + {
>> + /* See if there is a block that we can duplicate to split the
>> + path to the loop latch. */
>> + basic_block bb = find_block_to_duplicate_for_splitting_paths
>> (loop->latch);
>> +
>> + /* BB is the merge point for an IF-THEN-ELSE we want to transform.
>> +
>> + Essentially we want to create two duplicates of BB and append
>> + a duplicate to the THEN and ELSE clauses. This will split the
>> + path leading to the latch. BB will be unreachable and removed. */
>> + if (bb && is_feasible_trace (bb))
>> + {
>> + if (dump_file && (dump_flags & TDF_DETAILS))
>> + fprintf (dump_file,
>> + "Duplicating join block %d into predecessor paths\n",
>> + bb->index);
>> + basic_block pred0 = EDGE_PRED (bb, 0)->src;
>> + basic_block pred1 = EDGE_PRED (bb, 1)->src;
>> + transform_duplicate (pred0, bb);
>> + transform_duplicate (pred1, bb);
>> + changed = true;
>> + }
>> + }
>> +
>> + loop_optimizer_finalize ();
>> + free_original_copy_tables ();
>> + return changed;
>> +}
>> +
>> +/* Main entry point for splitting paths. Returns TODO_cleanup_cfg if any
>> + paths where split, otherwise return zero. */
>> +
>> +static unsigned int
>> +execute_split_paths ()
>> +{
>> + /* If we don't have at least 2 real blocks and backedges in the
>> + CFG, then there's no point in trying to perform path splitting. */
>> + if (n_basic_blocks_for_fn (cfun) <= NUM_FIXED_BLOCKS + 1
>> + || !mark_dfs_back_edges ())
>> + return 0;
>> +
>> + bool changed = split_paths();
>> + if (changed)
>> + free_dominance_info (CDI_DOMINATORS);
>> +
>> + return changed ? TODO_cleanup_cfg : 0;
>> +}
>> +
>> +static bool
>> +gate_split_paths ()
>> +{
>> + return flag_split_paths;
>> +}
>> +
>> +namespace {
>> +
>> +const pass_data pass_data_split_paths =
>> +{
>> + GIMPLE_PASS, /* type */
>> + "split-paths", /* name */
>> + OPTGROUP_NONE, /* optinfo_flags */
>> + TV_SPLIT_PATHS, /* tv_id */
>> + PROP_ssa, /* properties_required */
>> + 0, /* properties_provided */
>> + 0, /* properties_destroyed */
>> + 0, /* todo_flags_start */
>> + TODO_update_ssa, /* todo_flags_finish */
>> +};
>> +
>> +class pass_split_paths : public gimple_opt_pass
>> +{
>> + public:
>> + pass_split_paths (gcc::context *ctxt)
>> + : gimple_opt_pass (pass_data_split_paths, ctxt)
>> + {}
>> + /* opt_pass methods: */
>> + opt_pass * clone () { return new pass_split_paths (m_ctxt); }
>> + virtual bool gate (function *) { return gate_split_paths (); }
>> + virtual unsigned int execute (function *) { return execute_split_paths
>> (); }
>> +
>> +}; // class pass_split_paths
>> +
>> +} // anon namespace
>> +
>> +gimple_opt_pass *
>> +make_pass_split_paths (gcc::context *ctxt)
>> +{
>> + return new pass_split_paths (ctxt);
>> +}
>> diff --git a/gcc/opts.c b/gcc/opts.c
>> index 930ae43..be04cf5 100644
>> --- a/gcc/opts.c
>> +++ b/gcc/opts.c
>> @@ -523,6 +523,7 @@ static const struct default_options
>> default_options_table[] =
>> { OPT_LEVELS_2_PLUS, OPT_fisolate_erroneous_paths_dereference, NULL, 1
>> },
>> { OPT_LEVELS_2_PLUS, OPT_fipa_ra, NULL, 1 },
>> { OPT_LEVELS_2_PLUS, OPT_flra_remat, NULL, 1 },
>> + { OPT_LEVELS_2_PLUS, OPT_fsplit_paths, NULL, 1 },
>>
>> /* -O3 optimizations. */
>> { OPT_LEVELS_3_PLUS, OPT_ftree_loop_distribute_patterns, NULL, 1 },
>> diff --git a/gcc/passes.def b/gcc/passes.def
>> index c0ab6b9..db822d3 100644
>> --- a/gcc/passes.def
>> +++ b/gcc/passes.def
>> @@ -274,6 +274,7 @@ along with GCC; see the file COPYING3. If not see
>> POP_INSERT_PASSES ()
>> NEXT_PASS (pass_simduid_cleanup);
>> NEXT_PASS (pass_lower_vector_ssa);
>> + NEXT_PASS (pass_split_paths);
>> NEXT_PASS (pass_cse_reciprocals);
>> NEXT_PASS (pass_reassoc);
>> NEXT_PASS (pass_strength_reduction);
>> diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
>> index 3301130..ee92aaf 100644
>> --- a/gcc/testsuite/ChangeLog
>> +++ b/gcc/testsuite/ChangeLog
>> @@ -1,3 +1,8 @@
>> +2015-11-13 Ajit Agarwal <ajit...@xilinx.com>
>> + Jeff Law <l...@redhat.com>
>> +
>> + * gcc.dg/tree-ssa/split-path-1.c: New test.
>> +
>> 2015-11-13 Nathan Sidwell <nat...@codesourcery.com>
>>
>> * c-c++-common/goacc/loop-auto-1.c: New.
>> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/split-path-1.c
>> b/gcc/testsuite/gcc.dg/tree-ssa/split-path-1.c
>> new file mode 100644
>> index 0000000..1239892
>> --- /dev/null
>> +++ b/gcc/testsuite/gcc.dg/tree-ssa/split-path-1.c
>> @@ -0,0 +1,67 @@
>> +/* { dg-do run } */
>> +/* { dg-options "-O2 -fdump-tree-split-paths-details " } */
>> +
>> +#include <stdio.h>
>> +#include <stdlib.h>
>> +
>> +#define RGBMAX 255
>> +
>> +int
>> +test()
>> +{
>> + int i, Pels;
>> + unsigned char sum = 0;
>> + unsigned char xr, xg, xb;
>> + unsigned char xc, xm, xy, xk;
>> + unsigned char *ReadPtr, *EritePtr;
>> +
>> + ReadPtr = ( unsigned char *) malloc (sizeof (unsigned char) * 100);
>> + EritePtr = ( unsigned char *) malloc (sizeof (unsigned char) * 100);
>> +
>> + for (i = 0; i < 100;i++)
>> + {
>> + ReadPtr[i] = 100 - i;
>> + }
>> +
>> + for (i = 0; i < 100; i++)
>> + {
>> + xr = *ReadPtr++;
>> + xg = *ReadPtr++;
>> + xb = *ReadPtr++;
>> +
>> + xc = (unsigned char) (RGBMAX - xr);
>> + xm = (unsigned char) (RGBMAX - xg);
>> + xy = (unsigned char) (RGBMAX - xb);
>> +
>> + if (xc < xm)
>> + {
>> + xk = (unsigned char) (xc < xy ? xc : xy);
>> + }
>> + else
>> + {
>> + xk = (unsigned char) (xm < xy ? xm : xy);
>> + }
>> +
>> + xc = (unsigned char) (xc - xk);
>> + xm = (unsigned char) (xm - xk);
>> + xy = (unsigned char) (xy - xk);
>> +
>> + *EritePtr++ = xc;
>> + *EritePtr++ = xm;
>> + *EritePtr++ = xy;
>> + *EritePtr++ = xk;
>> + sum += *EritePtr;
>> + }
>> + return sum;
>> +}
>> +
>> +int
>> +main()
>> +{
>> + if (test() != 33)
>> + abort();
>> +
>> + return 0;
>> +}
>> +
>> +/* { dg-final { scan-tree-dump "Duplicating join block" "split-paths" } }
>> */
>> diff --git a/gcc/timevar.def b/gcc/timevar.def
>> index b429faf..45e3b70 100644
>> --- a/gcc/timevar.def
>> +++ b/gcc/timevar.def
>> @@ -252,6 +252,7 @@ DEFTIMEVAR (TV_GCSE_AFTER_RELOAD , "load CSE after
>> reload")
>> DEFTIMEVAR (TV_REE , "ree")
>> DEFTIMEVAR (TV_THREAD_PROLOGUE_AND_EPILOGUE, "thread pro- & epilogue")
>> DEFTIMEVAR (TV_IFCVT2 , "if-conversion 2")
>> +DEFTIMEVAR (TV_SPLIT_PATHS , "split paths")
>> DEFTIMEVAR (TV_COMBINE_STACK_ADJUST , "combine stack adjustments")
>> DEFTIMEVAR (TV_PEEPHOLE2 , "peephole 2")
>> DEFTIMEVAR (TV_RENAME_REGISTERS , "rename registers")
>> diff --git a/gcc/tracer.c b/gcc/tracer.c
>> index 941dc20..c2dba4c 100644
>> --- a/gcc/tracer.c
>> +++ b/gcc/tracer.c
>> @@ -51,9 +51,9 @@
>> #include "tree-inline.h"
>> #include "cfgloop.h"
>> #include "fibonacci_heap.h"
>> +#include "tracer.h"
>>
>> static int count_insns (basic_block);
>> -static bool ignore_bb_p (const_basic_block);
>> static bool better_p (const_edge, const_edge);
>> static edge find_best_successor (basic_block);
>> static edge find_best_predecessor (basic_block);
>> @@ -85,7 +85,7 @@ bb_seen_p (basic_block bb)
>> }
>>
>> /* Return true if we should ignore the basic block for purposes of tracing.
>> */
>> -static bool
>> +bool
>> ignore_bb_p (const_basic_block bb)
>> {
>> if (bb->index < NUM_FIXED_BLOCKS)
>> @@ -226,6 +226,24 @@ find_trace (basic_block bb, basic_block *trace)
>> return i;
>> }
>>
>> +/* Duplicate block BB2, placing it after BB in the CFG. Return the
>> + newly created block. */
>> +basic_block
>> +transform_duplicate (basic_block bb, basic_block bb2)
>> +{
>> + edge e;
>> + basic_block copy;
>> +
>> + e = find_edge (bb, bb2);
>> +
>> + copy = duplicate_block (bb2, e, bb);
>> + flush_pending_stmts (e);
>> +
>> + add_phi_args_after_copy (©, 1, NULL);
>> +
>> + return (copy);
>> +}
>> +
>> /* Look for basic blocks in frequency order, construct traces and tail
>> duplicate
>> if profitable. */
>>
>> @@ -321,17 +339,8 @@ tail_duplicate (void)
>> entries or at least rotate the loop. */
>> && bb2->loop_father->header != bb2)
>> {
>> - edge e;
>> - basic_block copy;
>> -
>> nduplicated += counts [bb2->index];
>> -
>> - e = find_edge (bb, bb2);
>> -
>> - copy = duplicate_block (bb2, e, bb);
>> - flush_pending_stmts (e);
>> -
>> - add_phi_args_after_copy (©, 1, NULL);
>> + basic_block copy = transform_duplicate (bb, bb2);
>>
>> /* Reconsider the original copy of block we've duplicated.
>> Removing the most common predecessor may make it to be
>> diff --git a/gcc/tracer.h b/gcc/tracer.h
>> new file mode 100644
>> index 0000000..cd1792a
>> --- /dev/null
>> +++ b/gcc/tracer.h
>> @@ -0,0 +1,26 @@
>> +/* Header file for Tracer.
>> + Copyright (C) 2015 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 GCC_TRACER_H
>> +#define GCC_TRACER_H
>> +
>> +extern basic_block transform_duplicate (basic_block bb, basic_block bb2);
>> +extern bool ignore_bb_p (const_basic_block bb);
>> +
>> +#endif /* GCC_TRACER_H */
>> diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h
>> index 49e22a9..da67761 100644
>> --- a/gcc/tree-pass.h
>> +++ b/gcc/tree-pass.h
>> @@ -390,6 +390,7 @@ extern gimple_opt_pass *make_pass_tree_loop_done
>> (gcc::context *ctxt);
>> extern gimple_opt_pass *make_pass_ch (gcc::context *ctxt);
>> extern gimple_opt_pass *make_pass_ch_vect (gcc::context *ctxt);
>> extern gimple_opt_pass *make_pass_ccp (gcc::context *ctxt);
>> +extern gimple_opt_pass *make_pass_split_paths (gcc::context *ctxt);
>> extern gimple_opt_pass *make_pass_phi_only_cprop (gcc::context *ctxt);
>> extern gimple_opt_pass *make_pass_build_ssa (gcc::context *ctxt);
>> extern gimple_opt_pass *make_pass_build_alias (gcc::context *ctxt);
>>
