Re: Loop-split improvements, part 2
> On Fri, Jul 28, 2023 at 9:58 AM Jan Hubicka via Gcc-patches
> wrote:
> >
> > Hi,
> > this patch fixes profile update in the first case of loop splitting.
> > The pass still gives up on very basic testcases:
> >
> > __attribute__ ((noinline,noipa))
> > void test1 (int n)
> > {
> > if (n <= 0 || n > 10)
> > return;
> > for (int i = 0; i <= n; i++)
> > {
> > if (i < n)
> > do_something ();
> > if (a[i])
> > do_something2();
> > }
> > }
> > Here I needed to do the conditoinal that enforces sane value range of n.
> > The reason is that it gives up on:
> > !number_of_iterations_exit (loop1, exit1, , false, true)
> > and without the conditonal we get assumption that n>=0 and not INT_MAX.
> > I think from overflow we shold derive that INT_MAX test is not needed and
> > since
> > the loop does nothing for n<0 it is also just an paranoia.
>
> I only get n != 2147483647 (loop header copying does the n >= 0). Indeed
> this test looks odd. It's because we turn i <= n into i < n + 1 and analyze
> that (our canonical test is LT_EXPR), for this to work n may not be INT_MAX.
Yep, I can't think on how that can disturb loop splitting. The loop
above is similar to one in hmmer so people do loops like that.
We should be able to use the fact that i can not overflow to get rid of
this assumtion, but I am not that famililar with that code...
I think it would help elsewhere too?
>
> In principle it could just look at the scalar evolution for the IV in
> the exit test.
> Aka use simple_iv () and check ->no_overflow?
Yep, I tink that should be enough. It uses simple_iv to analyze the
in-loop conditionals. I will look into that.
Honza
Re: Loop-split improvements, part 2
On Fri, Jul 28, 2023 at 9:58 AM Jan Hubicka via Gcc-patches
wrote:
>
> Hi,
> this patch fixes profile update in the first case of loop splitting.
> The pass still gives up on very basic testcases:
>
> __attribute__ ((noinline,noipa))
> void test1 (int n)
> {
> if (n <= 0 || n > 10)
> return;
> for (int i = 0; i <= n; i++)
> {
> if (i < n)
> do_something ();
> if (a[i])
> do_something2();
> }
> }
> Here I needed to do the conditoinal that enforces sane value range of n.
> The reason is that it gives up on:
> !number_of_iterations_exit (loop1, exit1, , false, true)
> and without the conditonal we get assumption that n>=0 and not INT_MAX.
> I think from overflow we shold derive that INT_MAX test is not needed and
> since
> the loop does nothing for n<0 it is also just an paranoia.
I only get n != 2147483647 (loop header copying does the n >= 0). Indeed
this test looks odd. It's because we turn i <= n into i < n + 1 and analyze
that (our canonical test is LT_EXPR), for this to work n may not be INT_MAX.
> I am not sure how to fix this though :(. In general the pass does not really
> need to compute iteration count. It only needs to know what direction the IVs
> go so it can detect tests that fires in first part of iteration space.
>
> Rich, any idea what the correct test should be?
In principle it could just look at the scalar evolution for the IV in
the exit test.
Aka use simple_iv () and check ->no_overflow?
> In testcase:
> for (int i = 0; i < 200; i++)
> if (i < 150)
> do_something ();
> else
> do_something2 ();
> the old code did wrong update of the exit condition probabilities.
> We know that first loop iterates 150 times and the second loop 50 times
> and we get it by simply scaling loop body by the probability of inner test.
>
> With the patch we now get:
>
>[count: 1000]:
>
>[count: 15]:<- loop 1 correctly iterates 149 times
> # i_10 = PHI
> do_something ();
> i_7 = i_10 + 1;
> if (i_7 <= 149)
> goto ; [99.33%]
> else
> goto ; [0.67%]
>
>[count: 149000]:
> goto ; [100.00%]
>
>[count: 1000]:
> # i_15 = PHI
>
>[count: 49975]:<- loop 2 should iterate 50 times but
>we are slightly wrong
> # i_3 = PHI
> do_something2 ();
> i_14 = i_3 + 1;
> if (i_14 != 200)
> goto ; [98.00%]
> else
> goto ; [2.00%]
>
>[count: 48975]:
> goto ; [100.00%]
>
>[count: 1000]: <- this test is always true becuase it is
> reached form bb 3
> # i_18 = PHI
> if (i_18 != 200)
> goto ; [99.95%]
> else
> goto ; [0.05%]
>
>[count: 1000]:
> return;
>
> The reason why we are slightly wrong is the condtion in bb17 that
> is always true but the pass does not konw it.
>
> Rich any idea how to do that? I think connect_loops should work out
> the cas where the loop exit conditon is never satisfied at the time
> the splitted condition fails for first time.
>
> Also we do not update loop iteration expectancies. If we were able to
> work out if one of the loop has constant iteration count, we could do it
> perfectly.
>
> Before patch on hmmer we get a lot of mismatches:
> Profile report here claims:
> dump id |static mismat|dynamic mismatch |
> |in count |in count |time |
> lsplit | 5+5| 8151850567 +8151850567| 531506481006 +57.9%|
> ldist | 9+4| 15345493501 +7193642934| 606848841056 +14.2%|
> ifcvt | 10+1| 15487514871 +142021370| 689469797790 +13.6%|
> vect| 35 +25| 17558425961 +2070911090| 517375405715 -25.0%|
> cunroll | 42+7| 16898736178 -659689783| 452445796198-4.9%|
> loopdone| 33-9| 2678017188 -14220718990| 330969127663 |
> tracer | 34+1| 2678018710+1522| 330613415364+0.0%|
> fre | 33-1| 2676980249 -1038461| 330465677073-0.0%|
> expand | 28-5| 2497468467 -179511782|--|
>
> With patch
>
> lsplit | 0 |0 | 328723360744-2.3%|
> ldist | 0 |0 | 396193562452 +20.6%|
> ifcvt | 1+1| 71010686+71010686| 478743508522 +20.8%|
> vect| 14 +13|697518955 +626508269| 299398068323 -37.5%|
> cunroll | 13-1|489349408 -208169547| 25839725 -10.5%|
> loopdone| 11-2|402558559-86790849| 201010712702 |
> tracer | 13+2|402977200 +418641| 200651036623+0.0%|
> fre | 13 |402622146 -355054| 200344398654-0.2%|
> expand | 11-2|333608636-69013510|--|
>
> So no mismatches for lsplit and ldist and also lsplit thinks it improves
> speed by 2.3% rather than
Loop-split improvements, part 2
Hi,
this patch fixes profile update in the first case of loop splitting.
The pass still gives up on very basic testcases:
__attribute__ ((noinline,noipa))
void test1 (int n)
{
if (n <= 0 || n > 10)
return;
for (int i = 0; i <= n; i++)
{
if (i < n)
do_something ();
if (a[i])
do_something2();
}
}
Here I needed to do the conditoinal that enforces sane value range of n.
The reason is that it gives up on:
!number_of_iterations_exit (loop1, exit1, , false, true)
and without the conditonal we get assumption that n>=0 and not INT_MAX.
I think from overflow we shold derive that INT_MAX test is not needed and since
the loop does nothing for n<0 it is also just an paranoia.
I am not sure how to fix this though :(. In general the pass does not really
need to compute iteration count. It only needs to know what direction the IVs
go so it can detect tests that fires in first part of iteration space.
Rich, any idea what the correct test should be?
In testcase:
for (int i = 0; i < 200; i++)
if (i < 150)
do_something ();
else
do_something2 ();
the old code did wrong update of the exit condition probabilities.
We know that first loop iterates 150 times and the second loop 50 times
and we get it by simply scaling loop body by the probability of inner test.
With the patch we now get:
[count: 1000]:
[count: 15]:<- loop 1 correctly iterates 149 times
# i_10 = PHI
do_something ();
i_7 = i_10 + 1;
if (i_7 <= 149)
goto ; [99.33%]
else
goto ; [0.67%]
[count: 149000]:
goto ; [100.00%]
[count: 1000]:
# i_15 = PHI
[count: 49975]:<- loop 2 should iterate 50 times but
we are slightly wrong
# i_3 = PHI
do_something2 ();
i_14 = i_3 + 1;
if (i_14 != 200)
goto ; [98.00%]
else
goto ; [2.00%]
[count: 48975]:
goto ; [100.00%]
[count: 1000]: <- this test is always true becuase it is
reached form bb 3
# i_18 = PHI
if (i_18 != 200)
goto ; [99.95%]
else
goto ; [0.05%]
[count: 1000]:
return;
The reason why we are slightly wrong is the condtion in bb17 that
is always true but the pass does not konw it.
Rich any idea how to do that? I think connect_loops should work out
the cas where the loop exit conditon is never satisfied at the time
the splitted condition fails for first time.
Also we do not update loop iteration expectancies. If we were able to
work out if one of the loop has constant iteration count, we could do it
perfectly.
Before patch on hmmer we get a lot of mismatches:
Profile report here claims:
dump id |static mismat|dynamic mismatch |
|in count |in count |time |
lsplit | 5+5| 8151850567 +8151850567| 531506481006 +57.9%|
ldist | 9+4| 15345493501 +7193642934| 606848841056 +14.2%|
ifcvt | 10+1| 15487514871 +142021370| 689469797790 +13.6%|
vect| 35 +25| 17558425961 +2070911090| 517375405715 -25.0%|
cunroll | 42+7| 16898736178 -659689783| 452445796198-4.9%|
loopdone| 33-9| 2678017188 -14220718990| 330969127663 |
tracer | 34+1| 2678018710+1522| 330613415364+0.0%|
fre | 33-1| 2676980249 -1038461| 330465677073-0.0%|
expand | 28-5| 2497468467 -179511782|--|
With patch
lsplit | 0 |0 | 328723360744-2.3%|
ldist | 0 |0 | 396193562452 +20.6%|
ifcvt | 1+1| 71010686+71010686| 478743508522 +20.8%|
vect| 14 +13|697518955 +626508269| 299398068323 -37.5%|
cunroll | 13-1|489349408 -208169547| 25839725 -10.5%|
loopdone| 11-2|402558559-86790849| 201010712702 |
tracer | 13+2|402977200 +418641| 200651036623+0.0%|
fre | 13 |402622146 -355054| 200344398654-0.2%|
expand | 11-2|333608636-69013510|--|
So no mismatches for lsplit and ldist and also lsplit thinks it improves
speed by 2.3% rather than regressig it by 57%.
Update is still not perfect since we do not work out that the second loop
never iterates. Also ldist is still wrong siince time should not go up.
Ifcft wrecks profile by desing since it insert conditonals with both arms 100%
that will be eliminated later after vect. It is not clear to me what happens
in vect though.
Bootstrapped/regtested x86_64-linux, comitted.
gcc/ChangeLog:
PR middle-end/106293
* tree-ssa-loop-split.cc (connect_loops): Change probability
of the test preconditioning second loop to very_likely.
(fix_loop_bb_probability): Handle correctly
