On Mon, Mar 22, 2021 at 12:00 PM bin.cheng via Gcc-patches <gcc-patches@gcc.gnu.org> wrote: > > Hi, > > This is the patch for PR98736. The root cause is like: > > Use programing order preserved RPO in loop distribution. > > Tree loop distribution uses RPO to build reduced dependence graph, > it's important that RPO preserves the original programing order and > usually it does. However, when distributing loop nest, the exit bb > could be placed before some loop basic blocks while after loop header. > > This patch fixes the issue by preferring loop exit edge in DFS when > computing RPO. > > In the patch, I just duplicated and created new function > loop_first_rev_post_order_compute_fn. > I am not sure if I should change the original function > pre_and_rev_post_order_compute_fn > (maybe not at this stage)? I am neither sure about the name, though haven't > got a better one. > Any comment is appreciated?
So your new function seems to do what rev_post_order_and_mark_dfs_back_seme does when you specify for_iteration = true. Specifically that function then does If FOR_ITERATION is true then compute an RPO where SCCs form a contiguous region in the RPO array. it in particular should handle the situation well where there are multiple exits from a loop to different outer loops (consider a switch stmt exiting to the immediate outer or to the next outer loop) - something your patch likely still handles "randomly" (though we of course generally do not handle such exits well). The idea of the rev_post_order_and_mark_dfs_back_seme algorithm is to treat SCCs as single nodes for the "outermost" RPO walk and then continuously expand SCCs from outer to inner. So for the testcase I'm quite sure using the this function for computing the RPO would work but extra thoughts are appreciated. Thanks, Richard. > Bootstrap and test on x86_64. > > Thanks, > bin > > gcc/ChangeLog: > > PR tree-optimization/98736 > * cfganal.c (loop_first_rev_post_order_compute_fn): New function. > * cfganal.h (loop_first_rev_post_order_compute_fn): New decl. > * tree-loop-distribution.c (loop_distribution::bb_top_order_init): > Compute RPO with programing order preserved by calling above. > > gcc/testsuite/ChangeLog: > > PR tree-optimization/98736 > * gcc.c-torture/execute/pr98736.c: New test.
