[PATCH 3/3] Fix loop split incorrect count and probability
In tree-ssa-loop-split.c, split_loop and split_loop_on_cond does two kind of split. split_loop only works for single loop and insert edge at exit when split, while split_loop_on_cond is not limited to single loop and insert edge at latch when split. Both split behavior should consider loop count and probability update. For split_loop, loop split condition is moved in front of loop1 and loop2; But split_loop_on_cond moves the condition between loop1 and loop2, this patch does: 1) profile count proportion for both original loop and copied loop without dropping down the true branch's count; 2) probability update in the two loops and between the two loops. Regression tested pass, OK for master? Changes diff for split_loop and split_loop_on_cond cases: 1) diff base/loop-split.c.151t.lsplit patched/loop-split.c.152t.lsplit ... [local count: 118111600]: if (beg_5(D) < end_8(D)) goto ; [89.00%] else goto ; [11.00%] [local count: 105119324]: if (beg2_6(D) < c_9(D)) -goto ; [100.00%] +goto ; [33.00%] else -goto ; [100.00%] +goto ; [67.00%] - [local count: 105119324]: + [local count: 34689377]: _25 = beg_5(D) + 1; _26 = end_8(D) - beg_5(D); _27 = beg2_6(D) + _26; _28 = MIN_EXPR ; - [local count: 955630225]: + [local count: 315357973]: # i_16 = PHI # j_17 = PHI printf ("a: %d %d\n", i_16, j_17); i_11 = i_16 + 1; j_12 = j_17 + 1; if (j_12 < _28) -goto ; [89.00%] +goto ; [29.37%] else -goto ; [11.00%] +goto ; [70.63%] - [local count: 850510901]: + [local count: 280668596]: goto ; [100.00%] - [local count: 105119324]: + [local count: 70429947]: # i_22 = PHI # j_23 = PHI [local count: 955630225]: # i_2 = PHI # j_1 = PHI i_20 = i_2 + 1; j_21 = j_1 + 1; if (end_8(D) > i_20) -goto ; [89.00%] +goto ; [59.63%] else -goto ; [11.00%] +goto ; [40.37%] - [local count: 850510901]: + [local count: 569842305]: goto ; [100.00%] [local count: 105119324]: # i_29 = PHI # j_30 = PHI if (end_8(D) > i_29) goto ; [80.00%] else goto ; [20.00%] [local count: 105119324]: [local count: 118111600]: return 0; } [local count: 118111600]: - if (beg_5(D) < end_8(D)) + _1 = end_6(D) - beg_7(D); + j_9 = _1 + beg2_8(D); + if (end_6(D) > beg_7(D)) goto ; [89.00%] else goto ; [11.00%] [local count: 105119324]: - if (beg2_6(D) < c_9(D)) -goto ; [100.00%] + if (j_9 >= c_11(D)) +goto ; [33.00%] else -goto ; [100.00%] +goto ; [67.00%] - [local count: 105119324]: - _25 = beg_5(D) + 1; - _26 = end_8(D) - beg_5(D); - _27 = beg2_6(D) + _26; - _28 = MIN_EXPR ; - - [local count: 955630225]: - # i_16 = PHI - # j_17 = PHI - printf ("a: %d %d\n", i_16, j_17); - i_11 = i_16 + 1; - j_12 = j_17 + 1; - if (j_12 < _28) -goto ; [89.00%] + [local count: 34689377]: + _27 = end_6(D) + -1; + _28 = beg_7(D) - end_6(D); + _29 = j_9 + _28; + _30 = _29 + 1; + _31 = MAX_EXPR ; + + [local count: 315357973]: + # i_18 = PHI + # j_19 = PHI + printf ("a: %d %d\n", i_18, j_19); + i_13 = i_18 + -1; + j_14 = j_19 + -1; + if (j_14 >= _31) +goto ; [29.37%] else -goto ; [11.00%] +goto ; [70.63%] - [local count: 850510901]: + [local count: 280668596]: goto ; [100.00%] - [local count: 105119324]: - # i_22 = PHI - # j_23 = PHI + [local count: 70429947]: + # i_24 = PHI + # j_25 = PHI [local count: 955630225]: - # i_2 = PHI - # j_1 = PHI - i_20 = i_2 + 1; - j_21 = j_1 + 1; - if (end_8(D) > i_20) + # i_3 = PHI + # j_2 = PHI + i_22 = i_3 + -1; + j_23 = j_2 + -1; + if (beg_7(D) < i_22) goto ; [89.00%] else goto ; [11.00%] - [local count: 850510901]: + [local count: 569842305]: goto ; [100.00%] [local count: 105119324]: - # i_29 = PHI - # j_30 = PHI - if (end_8(D) > i_29) + # i_32 = PHI + # j_33 = PHI + if (beg_7(D) < i_32) goto ; [80.00%] else goto ; [20.00%] [local count: 105119324]: [local count: 118111600]: return 0; } 2) diff base/loop-cond-split-1.c.151t.lsplit patched/loop-cond-split-1.c.151t.lsplit: ... [local count: 118111600]: if (n_7(D) > 0) goto ; [89.00%] else goto ; [11.00%] [local count: 118111600]: return; [local count: 105119324]: pretmp_3 = ga; - [local count: 955630225]: + [local count: 315357973]: # i_13 = PHI # prephitmp_12 = PHI if (prephitmp_12 != 0) goto ; [33.00%] else goto ; [67.00%] [local count: 315357972]: _2 = do_something (); ga = _2; - [local count: 955630225]: + [local count: 315357973]: # prephitmp_5 = PHI i_10 = inc (i_13); if (n_7(D) > i_10) goto ; [89.00%] else goto ; [11.00%] [local count: 105119324]: goto ; [100.00%] - [local count: 850510901]: + [local count: 280668596]: if (prephitmp_12 != 0) -goto ; [100.00%] +
Re: [PATCH 3/3] Fix loop split incorrect count and probability
On 12/7/2021 10:54 PM, Xionghu Luo via Gcc-patches wrote: In tree-ssa-loop-split.c, split_loop and split_loop_on_cond does two kind of split. split_loop only works for single loop and insert edge at exit when split, while split_loop_on_cond is not limited to single loop and insert edge at latch when split. Both split behavior should consider loop count and probability update. For split_loop, loop split condition is moved in front of loop1 and loop2; But split_loop_on_cond moves the condition between loop1 and loop2, this patch does: 1) profile count proportion for both original loop and copied loop without dropping down the true branch's count; 2) probability update in the two loops and between the two loops. Regression tested pass, OK for master? Changes diff for split_loop and split_loop_on_cond cases: 1) diff base/loop-split.c.151t.lsplit patched/loop-split.c.152t.lsplit ... [local count: 118111600]: if (beg_5(D) < end_8(D)) goto ; [89.00%] else goto ; [11.00%] [local count: 105119324]: if (beg2_6(D) < c_9(D)) -goto ; [100.00%] +goto ; [33.00%] else -goto ; [100.00%] +goto ; [67.00%] - [local count: 105119324]: + [local count: 34689377]: _25 = beg_5(D) + 1; _26 = end_8(D) - beg_5(D); _27 = beg2_6(D) + _26; _28 = MIN_EXPR ; - [local count: 955630225]: + [local count: 315357973]: # i_16 = PHI # j_17 = PHI printf ("a: %d %d\n", i_16, j_17); i_11 = i_16 + 1; j_12 = j_17 + 1; if (j_12 < _28) -goto ; [89.00%] +goto ; [29.37%] else -goto ; [11.00%] +goto ; [70.63%] - [local count: 850510901]: + [local count: 280668596]: goto ; [100.00%] - [local count: 105119324]: + [local count: 70429947]: # i_22 = PHI # j_23 = PHI [local count: 955630225]: # i_2 = PHI # j_1 = PHI i_20 = i_2 + 1; j_21 = j_1 + 1; if (end_8(D) > i_20) -goto ; [89.00%] +goto ; [59.63%] else -goto ; [11.00%] +goto ; [40.37%] - [local count: 850510901]: + [local count: 569842305]: goto ; [100.00%] [local count: 105119324]: # i_29 = PHI # j_30 = PHI if (end_8(D) > i_29) goto ; [80.00%] else goto ; [20.00%] [local count: 105119324]: [local count: 118111600]: return 0; } [local count: 118111600]: - if (beg_5(D) < end_8(D)) + _1 = end_6(D) - beg_7(D); + j_9 = _1 + beg2_8(D); + if (end_6(D) > beg_7(D)) goto ; [89.00%] else goto ; [11.00%] [local count: 105119324]: - if (beg2_6(D) < c_9(D)) -goto ; [100.00%] + if (j_9 >= c_11(D)) +goto ; [33.00%] else -goto ; [100.00%] +goto ; [67.00%] - [local count: 105119324]: - _25 = beg_5(D) + 1; - _26 = end_8(D) - beg_5(D); - _27 = beg2_6(D) + _26; - _28 = MIN_EXPR ; - - [local count: 955630225]: - # i_16 = PHI - # j_17 = PHI - printf ("a: %d %d\n", i_16, j_17); - i_11 = i_16 + 1; - j_12 = j_17 + 1; - if (j_12 < _28) -goto ; [89.00%] + [local count: 34689377]: + _27 = end_6(D) + -1; + _28 = beg_7(D) - end_6(D); + _29 = j_9 + _28; + _30 = _29 + 1; + _31 = MAX_EXPR ; + + [local count: 315357973]: + # i_18 = PHI + # j_19 = PHI + printf ("a: %d %d\n", i_18, j_19); + i_13 = i_18 + -1; + j_14 = j_19 + -1; + if (j_14 >= _31) +goto ; [29.37%] else -goto ; [11.00%] +goto ; [70.63%] - [local count: 850510901]: + [local count: 280668596]: goto ; [100.00%] - [local count: 105119324]: - # i_22 = PHI - # j_23 = PHI + [local count: 70429947]: + # i_24 = PHI + # j_25 = PHI [local count: 955630225]: - # i_2 = PHI - # j_1 = PHI - i_20 = i_2 + 1; - j_21 = j_1 + 1; - if (end_8(D) > i_20) + # i_3 = PHI + # j_2 = PHI + i_22 = i_3 + -1; + j_23 = j_2 + -1; + if (beg_7(D) < i_22) goto ; [89.00%] else goto ; [11.00%] - [local count: 850510901]: + [local count: 569842305]: goto ; [100.00%] [local count: 105119324]: - # i_29 = PHI - # j_30 = PHI - if (end_8(D) > i_29) + # i_32 = PHI + # j_33 = PHI + if (beg_7(D) < i_32) goto ; [80.00%] else goto ; [20.00%] [local count: 105119324]: [local count: 118111600]: return 0; } 2) diff base/loop-cond-split-1.c.151t.lsplit patched/loop-cond-split-1.c.151t.lsplit: ... [local count: 118111600]: if (n_7(D) > 0) goto ; [89.00%] else goto ; [11.00%] [local count: 118111600]: return; [local count: 105119324]: pretmp_3 = ga; - [local count: 955630225]: + [local count: 315357973]: # i_13 = PHI # prephitmp_12 = PHI if (prephitmp_12 != 0) goto ; [33.00%] else goto ; [67.00%] [local count: 315357972]: _2 = do_something (); ga = _2; - [local count: 955630225]: + [local count: 315357973]: # prephitmp_5 = PHI i_10 = inc (i_13); if (n_7(D) > i_10) goto ; [89.00%] else goto ; [11.00%] [loca
Re: [PATCH 3/3] Fix loop split incorrect count and probability
On 2021/12/9 07:47, Jeff Law wrote: >> diff --git a/gcc/tree-ssa-loop-split.c b/gcc/tree-ssa-loop-split.c >> index 3f6ad046623..33128061aab 100644 >> --- a/gcc/tree-ssa-loop-split.c >> +++ b/gcc/tree-ssa-loop-split.c >> >> @@ -607,6 +610,38 @@ split_loop (class loop *loop1) >> tree guard_next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge >> (loop1)); >> patch_loop_exit (loop1, guard_stmt, guard_next, newend, >> initial_true); >> + update_ssa (TODO_update_ssa); >> + >> + /* Proportion first loop's bb counts except those dominated by true >> + branch to avoid drop 1s down. */ >> + basic_block *bbs1, *bbs2; >> + bbs1 = get_loop_body (loop1); >> + unsigned j; >> + for (j = 0; j < loop1->num_nodes; j++) >> + if (bbs1[j] == loop1->latch >> + || !dominated_by_p (CDI_DOMINATORS, bbs1[j], true_edge->dest)) >> + bbs1[j]->count >> + = bbs1[j]->count.apply_probability (true_edge->probability); >> + free (bbs1); > It looks like there's two copies of this code in this patch, one in > split_loop and the other in do_split_loop_on_cond. Would it make sense > to factor it out into its own little function? > > >> + >> + /* Proportion second loop's bb counts except those dominated by >> false >> + branch to avoid drop 1s down. */ >> + basic_block bbi_copy = get_bb_copy (false_edge->dest); >> + bbs2 = get_loop_body (loop2); >> + for (j = 0; j < loop2->num_nodes; j++) >> + if (bbs2[j] == loop2->latch >> + || !dominated_by_p (CDI_DOMINATORS, bbs2[j], bbi_copy)) >> + bbs2[j]->count = bbs2[j]->count.apply_probability ( >> + true_edge->probability.invert ()); >> + free (bbs2); > Similarly for this block of code. > > If those can be reasonably factored out into two helper functions to be > called from split_loop and do_split_loop_on_cond, then this is OK with > the refactoring. > > jeff Thanks for the comments, updated as below. Will commit this patchset and the approved patch for LIM if there are no objections: [PATCH v2 3/3] Fix loop split incorrect count and probability In tree-ssa-loop-split.c, split_loop and split_loop_on_cond does two kind of split. split_loop only works for single loop and insert edge at exit when split, while split_loop_on_cond is not limited to single loop and insert edge at latch when split. Both split behavior should consider loop count and probability update. For split_loop, loop split condition is moved in front of loop1 and loop2; But split_loop_on_cond moves the condition between loop1 and loop2, this patch does: 1) profile count proportion for both original loop and copied loop without dropping down the true branch's count; 2) probability update in the two loops and between the two loops. Regression tested pass, OK for master? Changes diff for split_loop and split_loop_on_cond cases: 1) diff base/loop-split.c.151t.lsplit patched/loop-split.c.152t.lsplit ... [local count: 118111600]: _1 = end_6(D) - beg_7(D); j_9 = _1 + beg2_8(D); if (end_6(D) > beg_7(D)) goto ; [89.00%] else goto ; [11.00%] [local count: 105119324]: if (j_9 >= c_11(D)) -goto ; [100.00%] +goto ; [33.00%] else -goto ; [100.00%] +goto ; [67.00%] - [local count: 105119324]: + [local count: 34689377]: _27 = end_6(D) + -1; _28 = beg_7(D) - end_6(D); _29 = j_9 + _28; _30 = _29 + 1; _31 = MAX_EXPR ; - [local count: 955630225]: + [local count: 315357973]: # i_18 = PHI # j_19 = PHI printf ("a: %d %d\n", i_18, j_19); i_13 = i_18 + -1; j_14 = j_19 + -1; if (j_14 >= _31) -goto ; [89.00%] +goto ; [29.37%] else -goto ; [11.00%] +goto ; [70.63%] - [local count: 850510901]: + [local count: 280668596]: goto ; [100.00%] - [local count: 105119324]: + [local count: 70429947]: # i_24 = PHI # j_25 = PHI [local count: 955630225]: # i_3 = PHI # j_2 = PHI i_22 = i_3 + -1; j_23 = j_2 + -1; if (beg_7(D) < i_22) goto ; [89.00%] else goto ; [11.00%] - [local count: 850510901]: + [local count: 569842305]: goto ; [100.00%] [local count: 105119324]: # i_32 = PHI # j_33 = PHI if (beg_7(D) < i_32) goto ; [80.00%] else goto ; [20.00%] [local count: 105119324]: [local count: 118111600]: return 0; } 2) diff base/loop-cond-split-1.c.151t.lsplit patched/loop-cond-split-1.c.151t.lsplit: ... [local count: 118111600]: if (n_7(D) > 0) goto ; [89.00%] else goto ; [11.00%] [local count: 118111600]: return; [local count: 105119324]: pretmp_3 = ga; - [local count: 955630225]: + [local count: 315357973]: # i_13 = PHI # prephitmp_12 = PHI if (prephitmp_12 != 0) goto ; [33.00%] else goto ; [67.00%] [local count: 315357972]: _2 = do_something (); ga = _2; - [local count: 955630225]: + [local count: 315357973]: # prephitmp_5 = PHI i_
Re: [PATCH 3/3] Fix loop split incorrect count and probability
On 2021/12/13 16:57, Xionghu Luo via Gcc-patches wrote: > > > On 2021/12/9 07:47, Jeff Law wrote: >>> diff --git a/gcc/tree-ssa-loop-split.c b/gcc/tree-ssa-loop-split.c >>> index 3f6ad046623..33128061aab 100644 >>> --- a/gcc/tree-ssa-loop-split.c >>> +++ b/gcc/tree-ssa-loop-split.c >>> >>> @@ -607,6 +610,38 @@ split_loop (class loop *loop1) >>> tree guard_next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge >>> (loop1)); >>> patch_loop_exit (loop1, guard_stmt, guard_next, newend, >>> initial_true); >>> + update_ssa (TODO_update_ssa); >>> + >>> + /* Proportion first loop's bb counts except those dominated by true >>> + branch to avoid drop 1s down. */ >>> + basic_block *bbs1, *bbs2; >>> + bbs1 = get_loop_body (loop1); >>> + unsigned j; >>> + for (j = 0; j < loop1->num_nodes; j++) >>> + if (bbs1[j] == loop1->latch >>> + || !dominated_by_p (CDI_DOMINATORS, bbs1[j], true_edge->dest)) >>> + bbs1[j]->count >>> + = bbs1[j]->count.apply_probability (true_edge->probability); >>> + free (bbs1); >> It looks like there's two copies of this code in this patch, one in >> split_loop and the other in do_split_loop_on_cond. Would it make sense >> to factor it out into its own little function? >> >> >>> + >>> + /* Proportion second loop's bb counts except those dominated by >>> false >>> + branch to avoid drop 1s down. */ >>> + basic_block bbi_copy = get_bb_copy (false_edge->dest); >>> + bbs2 = get_loop_body (loop2); >>> + for (j = 0; j < loop2->num_nodes; j++) >>> + if (bbs2[j] == loop2->latch >>> + || !dominated_by_p (CDI_DOMINATORS, bbs2[j], bbi_copy)) >>> + bbs2[j]->count = bbs2[j]->count.apply_probability ( >>> + true_edge->probability.invert ()); >>> + free (bbs2); >> Similarly for this block of code. >> >> If those can be reasonably factored out into two helper functions to be >> called from split_loop and do_split_loop_on_cond, then this is OK with >> the refactoring. >> >> jeff > > > Thanks for the comments, updated as below. Will commit this patchset and the > approved patch for LIM if there are no objections: This patch is committed to r12-6086. > > > [PATCH v2 3/3] Fix loop split incorrect count and probability > > In tree-ssa-loop-split.c, split_loop and split_loop_on_cond does two > kind of split. split_loop only works for single loop and insert edge at > exit when split, while split_loop_on_cond is not limited to single loop > and insert edge at latch when split. Both split behavior should consider > loop count and probability update. For split_loop, loop split condition > is moved in front of loop1 and loop2; But split_loop_on_cond moves the > condition between loop1 and loop2, this patch does: > 1) profile count proportion for both original loop and copied loop > without dropping down the true branch's count; > 2) probability update in the two loops and between the two loops. > > Regression tested pass, OK for master? > > Changes diff for split_loop and split_loop_on_cond cases: > > 1) diff base/loop-split.c.151t.lsplit patched/loop-split.c.152t.lsplit > ... > [local count: 118111600]: >_1 = end_6(D) - beg_7(D); >j_9 = _1 + beg2_8(D); >if (end_6(D) > beg_7(D)) > goto ; [89.00%] >else > goto ; [11.00%] > > [local count: 105119324]: >if (j_9 >= c_11(D)) > -goto ; [100.00%] > +goto ; [33.00%] >else > -goto ; [100.00%] > +goto ; [67.00%] > > - [local count: 105119324]: > + [local count: 34689377]: >_27 = end_6(D) + -1; >_28 = beg_7(D) - end_6(D); >_29 = j_9 + _28; >_30 = _29 + 1; >_31 = MAX_EXPR ; > > - [local count: 955630225]: > + [local count: 315357973]: ># i_18 = PHI ># j_19 = PHI >printf ("a: %d %d\n", i_18, j_19); >i_13 = i_18 + -1; >j_14 = j_19 + -1; >if (j_14 >= _31) > -goto ; [89.00%] > +goto ; [29.37%] >else > -goto ; [11.00%] > +goto ; [70.63%] > > - [local count: 850510901]: > + [local count: 280668596]: >goto ; [100.00%] > > - [local count: 105119324]: > + [local count: 70429947]: ># i_24 = PHI ># j_25 = PHI > > [local count: 955630225]: ># i_3 = PHI ># j_2 = PHI >i_22 = i_3 + -1; >j_23 = j_2 + -1; >if (beg_7(D) < i_22) > goto ; [89.00%] >else > goto ; [11.00%] > > - [local count: 850510901]: > + [local count: 569842305]: >goto ; [100.00%] > > [local count: 105119324]: ># i_32 = PHI ># j_33 = PHI >if (beg_7(D) < i_32) > goto ; [80.00%] >else > goto ; [20.00%] > > [local count: 105119324]: > > [local count: 118111600]: >return 0; > > } > > 2) diff base/loop-cond-split-1.c.151t.lsplit > patched/loop-cond-split-1.c.151t.lsplit: > ... > [local count: 118111600]: >if (n_7(D) > 0) > goto ; [89.00%] >else > goto ; [11.00%] > > [local count: 118111600]: >return; > > [local