Re: [RFC] Design and Implementation for Path Splitting for Loop with Conditional IF-THEN-ELSE

[Jeff Law <law at redhat dot com>]

On 05/16/2015 06:49 AM, Ajit Kumar Agarwal wrote:
> I have Designed and  implemented with the following design for the path splitting of the loops with conditional IF-THEN-ELSE.
> The implementation has gone through the bootstrap for Microblaze target along DEJA GNU regressions tests and
> running the MIBench/EEMBC benchmarks. There is no regression seen in Deja GNU tests and Deja C++ tests results are
> better with the path splitting changes(lesser failures). The Mibench/EEMBC benchmarks are run and no performance degradation is
> seen and the performance improvement in telcom_gsm( Mibench benchmarks) of 9.15% and rgbcmy01_lite(EEMBC
> benchmarks) the performance improvement of 9.4% is observed.
>
> Proposal on the below were made earlier on path splitting and the reference is attached.
The first thing I notice is you haven't included any tests for the new 
optimization.  We're trying really hard these days to have tests in the 
suite for this kind of new optimization/feature work.

I don't offhand know if any of the benchmarks you cite above are 
free-enough to derive a testcase from.  But one trick many of us use is 
to instrument the pass and compile some known free software (often gcc 
itself) to find triggering code and use that to generate tests for the 
new transformation.


> Design changes.
>
> 1. The dominators of the block with conditional IF statements say BB1 are found and the join node of the IF-THEN-ELSE
> inside the loops is found on the blocks dominated by the BB1 and are not successor of BB1 are the join node.
This isn't necessarily my area of strength, but it doesn't seem right to 
me.   I guess it would work if there aren't any more nodes in the loop 
after the join block, except for the loop latch, but it doesn't see 
right in the general case.  It might work if you also verify that the IF 
block is the immediate dominator of potential join node.



> 2. The Join node is same as the source of the loops latch basic blocks.
OK.  This is why your initial algorithm in #1 works.

> 3. If the above conditional in (1) and (2) are found the Join node  same as the source of the Loop latch node is
> moved into predecessors and the Join node ( Source of the Loop latch node) is made empty statement block with only
> the phi nodes.
Hopefully you do this by duplicating the join node and manipulating the 
CFG so that the original predecessors of the join each go to their copy 
of the join node.  The copied join nodes unconditionally then pass 
control to the original join node.


> 4. In the process of moving the Join node into its predecessors the result of the phi node in the Join node propagated
> with the corresponding phi arguments  based on which predecessor it came from in the Join blocks and move into its predecessors.
Right.  Note there's a phi-only cprop pass which is designed to do this 
propagation and in theory should be very fast.

> 5. The Dominator INFO is updated after performing the steps of (1) (2) (3) and (4).
Right.  Getting the sequencing of the various updates can be tricky. 
Even more so if you try to do it as a part of jump threading because you 
have to (for example) deal with unreachable blocks in the CFG.


> 6. The Join which is same as the source of the Loop latch node is made empty with only the phi node in the Join node.
Right.

> 7. The implementation is done in Jump threading phase of the machine independent optimization on tree based
> representation. The path splitting is called after the Jump threading optimization is performed.
> The following files are modifed.
>
>      a) tree-vrp.c
>      b) tree-ssa-threadedge.c
>      c) tree-cfg.c
>      d) tree-ssa-threadedge.h
>      e) tree-cfg.h
>      f) cfghooks.c
>
> The diff is attached along with this mail and pasted below.
I would recommend this as a separate pass.  One of the goals for GCC 6 
is to break out the threader into its own pass, if you're piggybacking 
on the threader it just makes this task harder.

Also by implementing this as a distinct pass you have more freedom to 
put it where it really belongs in the optimization pipeline.  Given the 
duplication may end up exposing partial redundancies, dead code & 
propagation opportunities, it's probably best placed before DOM.  That 
also eliminates the need for running phi-only cprop because DOM will 
take care of it for you.

When jump threading is broken out into its own distinct pass, it'll 
probably end up just before or just after your path splitting pass.


> Please share your thoughts and feedbacks on the above optimization and the design and the coding and implementation
> done for the given above design.
Some general notes.  Every function should have a block comment which 
describes what the function does, its arguments & return value.  There 
are many examples throughout the code you can use to understand what 
we're looking for in those function comments.

Those comments are particularly useful during initial review and later 
maintenance, so in the future, please include them, even on RFCs.

You'll need to write a ChangeLog entry.  It's not particularly exciting 
or fun to do, but I regularly find that writing the ChangeLog forces me 
to look at each hunk in the patch and re-justify its purpose.  It's 
common that in doing so I rework the patch because I see something wrong 
or a cleaner/better way to solve a particular problem.


> diff --git a/gcc/cfghooks.c b/gcc/cfghooks.c
> index 9faa339..559ca96 100644
> --- a/gcc/cfghooks.c
> +++ b/gcc/cfghooks.c
> @@ -581,7 +581,7 @@ delete_basic_block (basic_block bb)
>
>         /* If we remove the header or the latch of a loop, mark the loop for
>   	 removal.  */
> -      if (loop->latch == bb
> +      if (loop && loop->latch == bb
>   	  || loop->header == bb)
>   	mark_loop_for_removal (loop);
So what caused you to add this additional test?  In general loop 
structures are supposed to always be available.  The change here implies 
that the loop structures were gone at some point.  That seems at first 
glance a mistake.


> diff --git a/gcc/tree-cfg.c b/gcc/tree-cfg.c
> index aed5254..b25e409 100644
> --- a/gcc/tree-cfg.c
> +++ b/gcc/tree-cfg.c
> @@ -1838,6 +1838,64 @@ replace_uses_by (tree name, tree val)
>       }
>   }
>
> +void
> +gimple_threaded_merge_blocks (basic_block a, basic_block b)
If we keep this function it will need a block comment.

I say "if" for a couple reasons.  First we already have support routines 
that know how to merge blocks.  If you really need to merge blocks you 
should try to use them.

Second, I'm not sure that you really need to worry about block merging 
in this pass.  Just create the duplicates, wire them into the CFG and 
let the existing block merging support handle this problem.



>   static void
> @@ -2061,7 +2119,7 @@ remove_bb (basic_block bb)
>
>         /* If a loop gets removed, clean up the information associated
>   	 with it.  */
> -      if (loop->latch == bb
> +      if (loop && loop->latch == bb
Same concern here as earlier, why don't you have the loop structures 
available when this routine gets called?


>   	  || loop->header == bb)
>   	free_numbers_of_iterations_estimates_loop (loop);
>       }
> @@ -5779,7 +5837,7 @@ gimple_can_duplicate_bb_p (const_basic_block bb ATTRIBUTE_UNUSED)
>   /* Create a duplicate of the basic block BB.  NOTE: This does not
>      preserve SSA form.  */
>
> -static basic_block
> +basic_block
>   gimple_duplicate_bb (basic_block bb)
There's already interfaces for duplicating blocks that you can/should be 
using.  In particular "duplicate_block" or "gimple_duplicate_sese_region".

>   {
>     basic_block new_bb;
> @@ -5858,7 +5916,7 @@ gimple_duplicate_bb (basic_block bb)
>
>   /* Adds phi node arguments for edge E_COPY after basic block duplication.  */
>
> -static void
> +void
>   add_phi_args_after_copy_edge (edge e_copy)
I don't think you'll need this if you use the existing interfaces for 
block duplication.


> diff --git a/gcc/tree-ssa-threadedge.c b/gcc/tree-ssa-threadedge.c
> index 4303a18..2c7d36d 100644
> --- a/gcc/tree-ssa-threadedge.c
> +++ b/gcc/tree-ssa-threadedge.c
> @@ -1359,6 +1359,322 @@ thread_through_normal_block (edge e,
>     return 0;
>   }
>
> +static void
> +replace_threaded_uses (basic_block a,basic_block b)
If you keep this function, then it'll need a function comment.

It looks like this is just doing const/copy propagation.  I think a 
better structure is to implement your optimization as a distinct pass, 
then rely on existing passes such as update_ssa, DOM, CCP to handle 
updating the SSA graph and propagation opportunities exposed by your 
transformation.


Similarly for the other replace_ functions.

}
> +
> +static bool
> +is_def_stmt_assert_expr (basic_block src1, basic_block bb,
> +                        int pred_index)
As a distinct pass I don't think you'd need to handle ASSERT_EXPRs as 
they're removed after VRP has completed.  THe only reason you're running 
into them is because the VRP runs the jump threader as a subroutine.

And it's odd that you also check for MIN_EXPR, I don't see how that's 
useful.  And yet you don't check for MAX_EXPR, so something definitely 
seems odd here.

+
> +void
> +process_path_splitting (basic_block bb)
Function comment.  This seems to be the meat of the transformation.



> +{
> +  vec<basic_block> bbs;
> +  basic_block bb1;
> +  unsigned int i;
> +  edge_iterator ei;
> +  edge e1;
> +  bool found = false ,found1;
> +
> +  bbs = get_all_dominated_blocks (CDI_DOMINATORS,
> +                                  bb );
> +  FOR_EACH_VEC_ELT (bbs, i, bb1)
> +  {
> +    found1 = false;
> +    FOR_EACH_EDGE (e1, ei, bb->succs)
> +    {
> +      if (bb1 == e1->dest)
> +        {
> +          found = true;
> +          found1 = true;
> +        }
> +    }
> +    if (!found1 && found)
> +      {
> +        unsigned int num_preds = 0;
> +        found = false;
> +
> +        FOR_EACH_EDGE (e1, ei, bb1->succs)
> +        {
> +          if (e1->flags & (EDGE_DFS_BACK))
> +            found = true;
> +        }
> +
> +        if (found && EDGE_COUNT(bb1->preds) == 2)
> +          {
> +            basic_block temp_bb = bb1;
> +            basic_block src1,src2;
> +            unsigned int k = 0, num_stmt = 0, num_phis = 0;
> +            bool is_src1 = false, is_src2 = false;
> +            gimple_stmt_iterator  psi,gsi;
> +
> +            FOR_EACH_EDGE (e1, ei, bb1->preds)
> +            {
> +              if ((e1->flags & (EDGE_DFS_BACK)))
> +                continue;
> +              if (k == 1)
> +                {
> +                  if (single_succ_p(e1->src) &&
> +                      single_succ_edge (e1->src)->flags & EDGE_FALLTHRU)
> +                    {
> +                      src2 = e1->src;
> +                      is_src2 = true;
> +                    }
> +                }
> +                else
> +                  {
> +                    if (single_succ_p(e1->src) &&
> +                        single_succ_edge (e1->src)->flags & EDGE_FALLTHRU)
> +                      {
> +                        is_src1 = true;
> +                        src1 = e1->src;
> +                      }
> +                  }
> +                k++;
> +           }
> +          for (gsi = gsi_start_bb (bb1); !gsi_end_p (gsi); gsi_next (&gsi))
> +            num_stmt++;
> +
> +          if ((num_stmt > 1) && is_src1 && is_src2)
> +            {
> +              bool found_non_virtual_result = false;
> +
> +              for (psi = gsi_start_phis (bb1); !gsi_end_p (psi); )
> +                 {
> +                   gimple stmt = gsi_stmt (psi);
> +
> +                   if (!virtual_operand_p (gimple_phi_result (stmt)))
> +                     num_phis++;
> +                   else
> +                     found_non_virtual_result = true;
> +
> +                   gsi_next(&psi);
> +                }
> +
> +              if ((num_phis >1) || found_non_virtual_result)
> +                return;
> +
> +              if (!(is_def_stmt_assert_expr (src1, bb1, 1) &&
> +                  is_def_stmt_assert_expr (src2, bb1, 2)))
> +                return;
So up to this point is just identification of candidates.  Seems like it 
ought to factor into its own function.

And from here to the end of the function is the actual transformation, 
which feels like it should factor into its own function as well.

> +
> +              temp_bb = gimple_duplicate_bb (bb1);
> +
> +              replace_threaded_uses (bb1, temp_bb);
> +
> +              make_edge (src1, temp_bb, EDGE_FALLTHRU);
> +
> +              make_edge (src2,temp_bb,EDGE_FALLTHRU);
> +
> +              FOR_EACH_EDGE (e1, ei, temp_bb->preds)
> +                add_phi_args_after_copy_edge (e1);
> +
> +              replace_phis(temp_bb, bb1);
> +
> +              replace_uses_phi(bb1, 1);
> +
> +              gimple_threaded_merge_blocks (src1, bb1);
> +
> +              replace_uses_phi(temp_bb, 2);
> +
> +              gimple_threaded_merge_blocks (src2, temp_bb);

> +
> +              while (EDGE_COUNT (temp_bb->preds) != 0)
> +                remove_edge (EDGE_PRED (temp_bb, 0));
> +
> +              while (EDGE_COUNT (temp_bb->succs) != 0)
> +                remove_edge (EDGE_SUCC (temp_bb, 0));
> +
> +              if (dom_info_available_p (CDI_DOMINATORS))
> +                delete_from_dominance_info (CDI_DOMINATORS, temp_bb);
> +
> +              if (dom_info_available_p (CDI_POST_DOMINATORS))
> +                delete_from_dominance_info (CDI_POST_DOMINATORS, temp_bb);
> +
> +              remove_phi_nodes (temp_bb);
> +              expunge_block (temp_bb);
> +
> +              return;
> +            }
> +          }
> +      }
> +  }
> +}
> +


> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
> index fbecdf7..c0db184 100644
> --- a/gcc/tree-vrp.c
> +++ b/gcc/tree-vrp.c
> @@ -10141,6 +10141,10 @@ identify_jump_threads (void)
>   	      thread_across_edge (dummy, e, true, &equiv_stack,
>   				  simplify_stmt_for_jump_threading);
>   	    }
> +          if (gimple_code(last) == GIMPLE_COND)
> +            {
> +              process_path_splitting(bb);
So instead of running this as a subroutine of vrp, make it a first class 
pass.  Then find the right place to put the pass.  I think that'll 
ultimately be cleaner and simpler as you won't be trying to duplicate 
things like const/copy propagation.


Overall I like the the transformation you're trying to make, but would 
like to see this as a separate pass, if it can't be a separate pass, 
please indicate why.  Second, you should be looking to re-use existing 
block duplication routines, SSA updating, etc as much as possible.

jeff