Re: [PATCH] Be careful about combined chain with length == 0 (PR, tree-optimization/70754).
On Fri, Jan 20, 2017 at 3:30 PM, Bin.Chengwrote: > On Thu, Jan 19, 2017 at 12:07 PM, Bin.Cheng wrote: >> On Thu, Jan 19, 2017 at 11:22 AM, Richard Biener >> wrote: >>> On Thu, Jan 19, 2017 at 11:25 AM, Bin.Cheng wrote: On Thu, Jan 19, 2017 at 9:42 AM, Richard Biener >>> >>> Or a later pass introduced it (in this case, the vectorizer). >>> Predcom could be the only pass that can handle such case as it understands data reference better. Note Martin's patch is not to skip handling of length == 0 chain, later ref will still be CSEed with result of root ref, only the combination operation like chain1 + chain2 is skipped. In this case, following dom should be able to handle such (loop independent) cse opportunities. >>> >>> I must admit I don't completely understand the consequences of this >>> disabling but of course DOM should also be able to handle the CSE >>> (ok, DOM is known to be quite weak with memory equivalence but >>> it's not that data-dependence is really better in all cases). >>> >>> Can't we simply re-order refs in new_chain appropriately or handle >>> this case in combinable_refs_p instead? >> It's not refs need to be reordered, root ref always dominates others. >> But yes, we need to find a dominator insertion place for combined >> operation. Looking at function reassociate_to_the_same_stmt, it >> simply inserts new_stmt at root_stmt of root ref, which causes ICE in >> this case. The new_stmt needs to be inserted at a place also >> dominating combination of later refs. We can either compute the >> information in place, or compute and pass the information from >> previous combinable_refs_p. This should be the real fix. > Hi All, > As analyzed, root cause is Predcom inserts combined stmt at place only > wrto the root refs. This is not enough because after combination, > result is also used by the following combined refs, not only root > refs. This patch fixes the ICE by processing all refs reversely and > computing dominance point for insertion. When it comes to the root > refs, dominance point is ready for use. > Bootstrap and test on x86_64 and AArch64 ongoing, is it OK if no failures? Ok. RIchard. > Thanks, > bin > 2017-01-19 Bin Cheng > > PR tree-optimization/70754 > * tree-predcom.c (stmt_combining_refs): New parameter INSERT_BEFORE. > (reassociate_to_the_same_stmt): New parameter INSERT_BEFORE. Insert > combined stmt before it if not NULL. > (combine_chains): Process refs reversely and compute dominance point > for root ref. > > gcc/testsuite/ChangeLog > 2017-01-19 Bin Cheng > > PR tree-optimization/70754 > * gfortran.dg/pr70754.f90: New test. > >>> That is, I understand the patch as a hack as it should be always >>> possible to find dominating refs? >>> >>> In fact the point of the assert tells us a simpler fix may be >>> >>> Index: tree-predcom.c >>> === >>> --- tree-predcom.c (revision 244519) >>> +++ tree-predcom.c (working copy) >>> @@ -2330,6 +2334,12 @@ combine_chains (chain_p ch1, chain_p ch2 >>> break; >>> } >>> } >>> + if (new_chain->length == 0 >>> + && ! new_chain->has_max_use_after) >>> +{ >>> + release_chain (new_chain); >>> + return NULL; >>> +} >>> >>>ch1->combined = true; >>>ch2->combined = true; >>> >>> which obviously matches the assert we run into for the testcase? I'd >>> be ok with that >>> (no stmt_dominates_stmt_p, heh) with a suitable comment before it. >>> >>> Richard. >>>
Re: [PATCH] Be careful about combined chain with length == 0 (PR, tree-optimization/70754).
On Thu, Jan 19, 2017 at 12:07 PM, Bin.Chengwrote: > On Thu, Jan 19, 2017 at 11:22 AM, Richard Biener > wrote: >> On Thu, Jan 19, 2017 at 11:25 AM, Bin.Cheng wrote: >>> On Thu, Jan 19, 2017 at 9:42 AM, Richard Biener >> >> Or a later pass introduced it (in this case, the vectorizer). >> >>> Predcom could be the >>> only pass that can handle such case as it understands data reference >>> better. Note Martin's patch is not to skip handling of length == 0 >>> chain, later ref will still be CSEed with result of root ref, only the >>> combination operation like chain1 + chain2 is skipped. In this case, >>> following dom should be able to handle such (loop independent) cse >>> opportunities. >> >> I must admit I don't completely understand the consequences of this >> disabling but of course DOM should also be able to handle the CSE >> (ok, DOM is known to be quite weak with memory equivalence but >> it's not that data-dependence is really better in all cases). >> >> Can't we simply re-order refs in new_chain appropriately or handle >> this case in combinable_refs_p instead? > It's not refs need to be reordered, root ref always dominates others. > But yes, we need to find a dominator insertion place for combined > operation. Looking at function reassociate_to_the_same_stmt, it > simply inserts new_stmt at root_stmt of root ref, which causes ICE in > this case. The new_stmt needs to be inserted at a place also > dominating combination of later refs. We can either compute the > information in place, or compute and pass the information from > previous combinable_refs_p. This should be the real fix. Hi All, As analyzed, root cause is Predcom inserts combined stmt at place only wrto the root refs. This is not enough because after combination, result is also used by the following combined refs, not only root refs. This patch fixes the ICE by processing all refs reversely and computing dominance point for insertion. When it comes to the root refs, dominance point is ready for use. Bootstrap and test on x86_64 and AArch64 ongoing, is it OK if no failures? Thanks, bin 2017-01-19 Bin Cheng PR tree-optimization/70754 * tree-predcom.c (stmt_combining_refs): New parameter INSERT_BEFORE. (reassociate_to_the_same_stmt): New parameter INSERT_BEFORE. Insert combined stmt before it if not NULL. (combine_chains): Process refs reversely and compute dominance point for root ref. gcc/testsuite/ChangeLog 2017-01-19 Bin Cheng PR tree-optimization/70754 * gfortran.dg/pr70754.f90: New test. >> That is, I understand the patch as a hack as it should be always >> possible to find dominating refs? >> >> In fact the point of the assert tells us a simpler fix may be >> >> Index: tree-predcom.c >> === >> --- tree-predcom.c (revision 244519) >> +++ tree-predcom.c (working copy) >> @@ -2330,6 +2334,12 @@ combine_chains (chain_p ch1, chain_p ch2 >> break; >> } >> } >> + if (new_chain->length == 0 >> + && ! new_chain->has_max_use_after) >> +{ >> + release_chain (new_chain); >> + return NULL; >> +} >> >>ch1->combined = true; >>ch2->combined = true; >> >> which obviously matches the assert we run into for the testcase? I'd >> be ok with that >> (no stmt_dominates_stmt_p, heh) with a suitable comment before it. >> >> Richard. >> diff --git a/gcc/testsuite/gfortran.dg/pr70754.f90 b/gcc/testsuite/gfortran.dg/pr70754.f90 new file mode 100644 index 000..d7e790c --- /dev/null +++ b/gcc/testsuite/gfortran.dg/pr70754.f90 @@ -0,0 +1,35 @@ +! { dg-do compile } +! { dg-options "-Ofast" } +module m + implicit none + private + save + + integer, parameter, public :: & +ii4 = selected_int_kind(6), & +rr8 = selected_real_kind(13) + + integer (ii4), dimension(40,40,199), public :: xyz + public :: foo +contains + subroutine foo(a) +real (rr8), dimension(40,40), intent(out) :: a +real (rr8), dimension(40,40) :: b +integer (ii4), dimension(40,40) :: c +integer i, j + +do i=1,20 + b(i,j) = 123 * a(i,j) + 34 * a(i,j+1) & + + 34 * a(i,j-1) + a(i+1,j+1) & + + a(i+1,j-1) + a(i-1,j+1) & + + a(i-1,j-1) + c(i,j) = 123 +end do + +where ((xyz(:,:,2) /= 0) .and. (c /= 0)) + a = b/real(c) +elsewhere + a = 456 +endwhere + end subroutine foo +end module m diff --git a/gcc/tree-predcom.c b/gcc/tree-predcom.c index f0b70a6..9723e9c 100644 --- a/gcc/tree-predcom.c +++ b/gcc/tree-predcom.c @@ -2164,10 +2164,11 @@ remove_name_from_operation (gimple *stmt, tree op) } /* Reassociates the expression in that NAME1 and NAME2 are used so that they - are combined in a single statement, and returns this statement. */ + are combined in a single statement, and returns
Re: [PATCH] Be careful about combined chain with length == 0 (PR, tree-optimization/70754).
On Thu, Jan 19, 2017 at 11:22 AM, Richard Bienerwrote: > On Thu, Jan 19, 2017 at 11:25 AM, Bin.Cheng wrote: >> On Thu, Jan 19, 2017 at 9:42 AM, Richard Biener >> wrote: >>> On Wed, Jan 18, 2017 at 4:32 PM, Bin.Cheng wrote: On Wed, Jan 18, 2017 at 2:54 PM, Richard Biener wrote: > On Wed, Jan 18, 2017 at 11:10 AM, Martin Liška wrote: >> Hello. >> >> >> Patch can bootstrap on ppc64le-redhat-linux and survives regression >> tests. >> >> Ready to be installed? > > I'm not sure. If we have such zero distance refs in the IL at the > time pcom runs then not handling > them will pessimize code-gen for cases where they are part of a larger > chain. Esp. I don't like Do you mean different chains distributed because of MAX_DISTANCE by "larger chain"? With the patch, such chain of refs would still be pred-commoned, just the arithmetic operation not combined, which could be handled by later DOM? > another stmt_dominates_stmt_p call and thus rather not handle length > == 0 at all... Not handle length == 0 chains at all may be sub-optimal. As you said, such chain of refs at the point may simply because previous dom/cse fail to analyze the references. > > We already seem to go great length in associating stuff when combining > stuff thus isn't this > maybe an artifact of this association? Maybe we simply need to sort > the new chain after > combining it so the root stmt comes last? > > Note that there seems to be only a single length per chain but not all > refs in a chain need to > have the same distance. This means your fix is likely incomplete? > What prevents the situation > to arise for distance != 0? Yes, it's possible for two refs have the same distance in a chain with length > 0. But that should not be a problem, because existing uses are replaced by newly generated PHI variables which always dominate the uses, right? >>> >>> I must admit I don't know predcom in such detail but then can we handle >>> distance == 0 by simply inserting a PHI for those as well (a degenerate >>> one of course)? Or can for distance == 0 the ref be not loop invariant? >> Not sure if I understand the question correctly. Distance is >> difference of niter between one ref and the root ref of the chain, so >> 0 distance/length doesn't mean a loop invariant, it's very likely two >> (exactly the same) references in each loop iteration, the address of >> reference is still a SCEV. OTOH, invariant chain has invariant >> address, and is handled separately. For the first question, it's >> length, rather than distance that decides how the chain is handled. >> For length > 0 chain, we have to insert PHIs to pass carried result of >> memory reference, even some refs may have 0 distance to the root ref. >>> >>> Note that for length == 0 all refs in the chain will have a dependence >>> distance >>> of zero. So my first argument probably doesn't hold and we could simply >>> remove handling of length == 0 chains and rely on CSE? >> I am not sure, that CSE opportunity of references exists at this point >> means previous cse pass failed for some reason. > > Or a later pass introduced it (in this case, the vectorizer). > >> Predcom could be the >> only pass that can handle such case as it understands data reference >> better. Note Martin's patch is not to skip handling of length == 0 >> chain, later ref will still be CSEed with result of root ref, only the >> combination operation like chain1 + chain2 is skipped. In this case, >> following dom should be able to handle such (loop independent) cse >> opportunities. > > I must admit I don't completely understand the consequences of this > disabling but of course DOM should also be able to handle the CSE > (ok, DOM is known to be quite weak with memory equivalence but > it's not that data-dependence is really better in all cases). > > Can't we simply re-order refs in new_chain appropriately or handle > this case in combinable_refs_p instead? It's not refs need to be reordered, root ref always dominates others. But yes, we need to find a dominator insertion place for combined operation. Looking at function reassociate_to_the_same_stmt, it simply inserts new_stmt at root_stmt of root ref, which causes ICE in this case. The new_stmt needs to be inserted at a place also dominating combination of later refs. We can either compute the information in place, or compute and pass the information from previous combinable_refs_p. This should be the real fix. Thanks, bin > > That is, I understand the patch as a hack as it should be always > possible to find dominating refs? > > In fact the point of the assert tells us a simpler fix may be > > Index: tree-predcom.c >
Re: [PATCH] Be careful about combined chain with length == 0 (PR, tree-optimization/70754).
On Thu, Jan 19, 2017 at 11:25 AM, Bin.Chengwrote: > On Thu, Jan 19, 2017 at 9:42 AM, Richard Biener > wrote: >> On Wed, Jan 18, 2017 at 4:32 PM, Bin.Cheng wrote: >>> On Wed, Jan 18, 2017 at 2:54 PM, Richard Biener >>> wrote: On Wed, Jan 18, 2017 at 11:10 AM, Martin Liška wrote: > Hello. > > > Patch can bootstrap on ppc64le-redhat-linux and survives regression tests. > > Ready to be installed? I'm not sure. If we have such zero distance refs in the IL at the time pcom runs then not handling them will pessimize code-gen for cases where they are part of a larger chain. Esp. I don't like >>> Do you mean different chains distributed because of MAX_DISTANCE by >>> "larger chain"? With the patch, such chain of refs would still be >>> pred-commoned, just the arithmetic operation not combined, which could >>> be handled by later DOM? another stmt_dominates_stmt_p call and thus rather not handle length == 0 at all... >>> Not handle length == 0 chains at all may be sub-optimal. As you said, >>> such chain of refs at the point may simply because previous dom/cse >>> fail to analyze the references. We already seem to go great length in associating stuff when combining stuff thus isn't this maybe an artifact of this association? Maybe we simply need to sort the new chain after combining it so the root stmt comes last? Note that there seems to be only a single length per chain but not all refs in a chain need to have the same distance. This means your fix is likely incomplete? What prevents the situation to arise for distance != 0? >>> Yes, it's possible for two refs have the same distance in a chain with >>> length > 0. But that should not be a problem, because existing uses >>> are replaced by newly generated PHI variables which always dominate >>> the uses, right? >> >> I must admit I don't know predcom in such detail but then can we handle >> distance == 0 by simply inserting a PHI for those as well (a degenerate >> one of course)? Or can for distance == 0 the ref be not loop invariant? > Not sure if I understand the question correctly. Distance is > difference of niter between one ref and the root ref of the chain, so > 0 distance/length doesn't mean a loop invariant, it's very likely two > (exactly the same) references in each loop iteration, the address of > reference is still a SCEV. OTOH, invariant chain has invariant > address, and is handled separately. For the first question, it's > length, rather than distance that decides how the chain is handled. > For length > 0 chain, we have to insert PHIs to pass carried result of > memory reference, even some refs may have 0 distance to the root ref. >> >> Note that for length == 0 all refs in the chain will have a dependence >> distance >> of zero. So my first argument probably doesn't hold and we could simply >> remove handling of length == 0 chains and rely on CSE? > I am not sure, that CSE opportunity of references exists at this point > means previous cse pass failed for some reason. Or a later pass introduced it (in this case, the vectorizer). > Predcom could be the > only pass that can handle such case as it understands data reference > better. Note Martin's patch is not to skip handling of length == 0 > chain, later ref will still be CSEed with result of root ref, only the > combination operation like chain1 + chain2 is skipped. In this case, > following dom should be able to handle such (loop independent) cse > opportunities. I must admit I don't completely understand the consequences of this disabling but of course DOM should also be able to handle the CSE (ok, DOM is known to be quite weak with memory equivalence but it's not that data-dependence is really better in all cases). Can't we simply re-order refs in new_chain appropriately or handle this case in combinable_refs_p instead? That is, I understand the patch as a hack as it should be always possible to find dominating refs? In fact the point of the assert tells us a simpler fix may be Index: tree-predcom.c === --- tree-predcom.c (revision 244519) +++ tree-predcom.c (working copy) @@ -2330,6 +2334,12 @@ combine_chains (chain_p ch1, chain_p ch2 break; } } + if (new_chain->length == 0 + && ! new_chain->has_max_use_after) +{ + release_chain (new_chain); + return NULL; +} ch1->combined = true; ch2->combined = true; which obviously matches the assert we run into for the testcase? I'd be ok with that (no stmt_dominates_stmt_p, heh) with a suitable comment before it. Richard. > > Thanks, > bin >> >> Richard. >> >>> Thanks, >>> bin Richard. > Martin >
Re: [PATCH] Be careful about combined chain with length == 0 (PR, tree-optimization/70754).
On Thu, Jan 19, 2017 at 9:42 AM, Richard Bienerwrote: > On Wed, Jan 18, 2017 at 4:32 PM, Bin.Cheng wrote: >> On Wed, Jan 18, 2017 at 2:54 PM, Richard Biener >> wrote: >>> On Wed, Jan 18, 2017 at 11:10 AM, Martin Liška wrote: Hello. Patch can bootstrap on ppc64le-redhat-linux and survives regression tests. Ready to be installed? >>> >>> I'm not sure. If we have such zero distance refs in the IL at the >>> time pcom runs then not handling >>> them will pessimize code-gen for cases where they are part of a larger >>> chain. Esp. I don't like >> Do you mean different chains distributed because of MAX_DISTANCE by >> "larger chain"? With the patch, such chain of refs would still be >> pred-commoned, just the arithmetic operation not combined, which could >> be handled by later DOM? >>> another stmt_dominates_stmt_p call and thus rather not handle length >>> == 0 at all... >> Not handle length == 0 chains at all may be sub-optimal. As you said, >> such chain of refs at the point may simply because previous dom/cse >> fail to analyze the references. >>> >>> We already seem to go great length in associating stuff when combining >>> stuff thus isn't this >>> maybe an artifact of this association? Maybe we simply need to sort >>> the new chain after >>> combining it so the root stmt comes last? >>> >>> Note that there seems to be only a single length per chain but not all >>> refs in a chain need to >>> have the same distance. This means your fix is likely incomplete? >>> What prevents the situation >>> to arise for distance != 0? >> Yes, it's possible for two refs have the same distance in a chain with >> length > 0. But that should not be a problem, because existing uses >> are replaced by newly generated PHI variables which always dominate >> the uses, right? > > I must admit I don't know predcom in such detail but then can we handle > distance == 0 by simply inserting a PHI for those as well (a degenerate > one of course)? Or can for distance == 0 the ref be not loop invariant? Not sure if I understand the question correctly. Distance is difference of niter between one ref and the root ref of the chain, so 0 distance/length doesn't mean a loop invariant, it's very likely two (exactly the same) references in each loop iteration, the address of reference is still a SCEV. OTOH, invariant chain has invariant address, and is handled separately. For the first question, it's length, rather than distance that decides how the chain is handled. For length > 0 chain, we have to insert PHIs to pass carried result of memory reference, even some refs may have 0 distance to the root ref. > > Note that for length == 0 all refs in the chain will have a dependence > distance > of zero. So my first argument probably doesn't hold and we could simply > remove handling of length == 0 chains and rely on CSE? I am not sure, that CSE opportunity of references exists at this point means previous cse pass failed for some reason. Predcom could be the only pass that can handle such case as it understands data reference better. Note Martin's patch is not to skip handling of length == 0 chain, later ref will still be CSEed with result of root ref, only the combination operation like chain1 + chain2 is skipped. In this case, following dom should be able to handle such (loop independent) cse opportunities. Thanks, bin > > Richard. > >> Thanks, >> bin >>> >>> Richard. >>> Martin
Re: [PATCH] Be careful about combined chain with length == 0 (PR, tree-optimization/70754).
On Wed, Jan 18, 2017 at 4:32 PM, Bin.Chengwrote: > On Wed, Jan 18, 2017 at 2:54 PM, Richard Biener > wrote: >> On Wed, Jan 18, 2017 at 11:10 AM, Martin Liška wrote: >>> Hello. >>> >>> >>> Patch can bootstrap on ppc64le-redhat-linux and survives regression tests. >>> >>> Ready to be installed? >> >> I'm not sure. If we have such zero distance refs in the IL at the >> time pcom runs then not handling >> them will pessimize code-gen for cases where they are part of a larger >> chain. Esp. I don't like > Do you mean different chains distributed because of MAX_DISTANCE by > "larger chain"? With the patch, such chain of refs would still be > pred-commoned, just the arithmetic operation not combined, which could > be handled by later DOM? >> another stmt_dominates_stmt_p call and thus rather not handle length >> == 0 at all... > Not handle length == 0 chains at all may be sub-optimal. As you said, > such chain of refs at the point may simply because previous dom/cse > fail to analyze the references. >> >> We already seem to go great length in associating stuff when combining >> stuff thus isn't this >> maybe an artifact of this association? Maybe we simply need to sort >> the new chain after >> combining it so the root stmt comes last? >> >> Note that there seems to be only a single length per chain but not all >> refs in a chain need to >> have the same distance. This means your fix is likely incomplete? >> What prevents the situation >> to arise for distance != 0? > Yes, it's possible for two refs have the same distance in a chain with > length > 0. But that should not be a problem, because existing uses > are replaced by newly generated PHI variables which always dominate > the uses, right? I must admit I don't know predcom in such detail but then can we handle distance == 0 by simply inserting a PHI for those as well (a degenerate one of course)? Or can for distance == 0 the ref be not loop invariant? Note that for length == 0 all refs in the chain will have a dependence distance of zero. So my first argument probably doesn't hold and we could simply remove handling of length == 0 chains and rely on CSE? Richard. > Thanks, > bin >> >> Richard. >> >>> Martin >>>
Re: [PATCH] Be careful about combined chain with length == 0 (PR, tree-optimization/70754).
On Wed, Jan 18, 2017 at 2:54 PM, Richard Bienerwrote: > On Wed, Jan 18, 2017 at 11:10 AM, Martin Liška wrote: >> Hello. >> >> >> Patch can bootstrap on ppc64le-redhat-linux and survives regression tests. >> >> Ready to be installed? > > I'm not sure. If we have such zero distance refs in the IL at the > time pcom runs then not handling > them will pessimize code-gen for cases where they are part of a larger > chain. Esp. I don't like Do you mean different chains distributed because of MAX_DISTANCE by "larger chain"? With the patch, such chain of refs would still be pred-commoned, just the arithmetic operation not combined, which could be handled by later DOM? > another stmt_dominates_stmt_p call and thus rather not handle length > == 0 at all... Not handle length == 0 chains at all may be sub-optimal. As you said, such chain of refs at the point may simply because previous dom/cse fail to analyze the references. > > We already seem to go great length in associating stuff when combining > stuff thus isn't this > maybe an artifact of this association? Maybe we simply need to sort > the new chain after > combining it so the root stmt comes last? > > Note that there seems to be only a single length per chain but not all > refs in a chain need to > have the same distance. This means your fix is likely incomplete? > What prevents the situation > to arise for distance != 0? Yes, it's possible for two refs have the same distance in a chain with length > 0. But that should not be a problem, because existing uses are replaced by newly generated PHI variables which always dominate the uses, right? Thanks, bin > > Richard. > >> Martin >>
Re: [PATCH] Be careful about combined chain with length == 0 (PR, tree-optimization/70754).
On Wed, Jan 18, 2017 at 11:10:32AM +0100, Martin Liška wrote: > Hello. > > After basic understanding of loop predictive commoning, the problematic > combined chain is: > > Loads-only chain 0x38b6730 (combined) > max distance 0 > references: > MEM[(real(kind=8) *)vectp_a.29_81] (id 1) > offset 20 > distance 0 > MEM[(real(kind=8) *)vectp_a.38_141] (id 3) > offset 20 > distance 0 > > Loads-only chain 0x38b68b0 (combined) > max distance 0 > references: > MEM[(real(kind=8) *)vectp_a.23_102] (id 0) > offset 0 > distance 0 > MEM[(real(kind=8) *)vectp_a.33_33] (id 2) > offset 0 > distance 0 > > Combination chain 0x38b65b0 > max distance 0, may reuse first > equal to 0x38b6730 + 0x38b68b0 in type vector(2) real(kind=8) > references: > combination ref > in statement predreastmp.48_10 = vect__32.31_78 + vect__28.25_100; > > distance 0 > combination ref > in statement predreastmp.50_17 = vect__42.41_138 + vect__38.36_29; > > distance 0 > > It's important to note that distance is equal to zero (happening within a > same loop iteration). > Aforementioned chains correspond to: > > ... > r2: vect__28.25_100 = MEM[(real(kind=8) *)vectp_a.23_102]; > vectp_a.23_99 = vectp_a.23_102 + 16; > vect__28.26_98 = MEM[(real(kind=8) *)vectp_a.23_99]; > vect__82.27_97 = vect__22.22_108; > vect__82.27_96 = vect__22.22_107; > vect__79.28_95 = vect__82.27_97 + vect__84.17_120; > vect__79.28_94 = vect__82.27_96 + vect__84.17_119; > r1: vect__32.31_78 = MEM[(real(kind=8) *)vectp_a.29_81]; > vectp_a.29_77 = vectp_a.29_81 + 16; > vect__32.32_76 = MEM[(real(kind=8) *)vectp_a.29_77]; > vect__38.35_39 = MEM[(real(kind=8) *)vectp_a.33_57]; > r2': vectp_a.33_33 = vectp_a.33_57 + 16; > vect__38.36_29 = MEM[(real(kind=8) *)vectp_a.33_33]; > vect__56.37_23 = vect__38.35_39; > vect__56.37_15 = vect__32.32_76; > vect__42.40_161 = MEM[(real(kind=8) *)vectp_a.38_163]; > vectp_a.38_141 = vectp_a.38_163 + 16; > r1': vect__42.41_138 = MEM[(real(kind=8) *)vectp_a.38_141]; > vect__54.42_135 = vect__42.40_161 + vect__56.37_23; > r1'+r2': predreastmp.50_17 = vect__42.41_138 + vect__38.36_29; > predreastmp.51_18 = vect__56.37_15; > vect__54.42_134 = predreastmp.50_17; > r1+r2: predreastmp.48_10 = vect__32.31_78 + vect__28.25_100; > ... > > Problematic construct is that while having load-only chains r1->r1' and > r2->r2', the combination > is actually r1'+r2'->r1+r2, which cause the troubles. I believe the proper > fix is to reject such > combinations where combined root stmt does not dominate usages. It's probably > corner case as it does > not reuse any values among loop iterations (which is main motivation of the > pass), it's doing PRE > if I'm right. > > Patch can bootstrap on ppc64le-redhat-linux and survives regression tests. I could bootstrap on aarch64-none-linux-gnu without any issues, regression tests are fine and the testcase compiles without ICE. Thanks for fixing this. VP. > > Ready to be installed? > Martin > > From 41b153cf975374fff48419ec8ac5991ac134735f Mon Sep 17 00:00:00 2001 > From: marxin <mli...@suse.cz> > Date: Tue, 17 Jan 2017 14:22:40 +0100 > Subject: [PATCH] Be careful about combined chain with length == 0 (PR > tree-optimization/70754). > > gcc/testsuite/ChangeLog: > > 2017-01-17 Martin Liska <mli...@suse.cz> > > PR tree-optimization/70754 > * gfortran.dg/pr70754.f90: New test. > > gcc/ChangeLog: > > 2017-01-17 Martin Liska <mli...@suse.cz> > > PR tree-optimization/70754 > * tree-predcom.c (combine_chains): Do not create a combined chain > with length equal to zero when root_stmt does not dominate > stmts of references. > --- > gcc/testsuite/gfortran.dg/pr70754.f90 | 35 > +++ > gcc/tree-predcom.c| 10 ++ > 2 files changed, 45 insertions(+) > create mode 100644 gcc/testsuite/gfortran.dg/pr70754.f90 > > diff --git a/gcc/testsuite/gfortran.dg/pr70754.f90 > b/gcc/testsuite/gfortran.dg/pr70754.f90 > new file mode 100644 > index 000..758901ce2b2 > --- /dev/null > +++ b/gcc/testsuite/gfortran.dg/pr70754.f90 > @@ -0,0 +1,35 @@ > +! { dg-options "-Ofast" } > + > +module m > + implicit none > + private > + save > + > + integer, parameter, public :: & > +ii4 = selected_int_kind(6), & > +rr8 = selected_real_kind(13) > + > + integer (ii4), dimension(40,40,199), public :: xyz > + public :: foo
Re: [PATCH] Be careful about combined chain with length == 0 (PR, tree-optimization/70754).
On Wed, Jan 18, 2017 at 11:10 AM, Martin Liškawrote: > Hello. > > After basic understanding of loop predictive commoning, the problematic > combined chain is: > > Loads-only chain 0x38b6730 (combined) > max distance 0 > references: > MEM[(real(kind=8) *)vectp_a.29_81] (id 1) > offset 20 > distance 0 > MEM[(real(kind=8) *)vectp_a.38_141] (id 3) > offset 20 > distance 0 > > Loads-only chain 0x38b68b0 (combined) > max distance 0 > references: > MEM[(real(kind=8) *)vectp_a.23_102] (id 0) > offset 0 > distance 0 > MEM[(real(kind=8) *)vectp_a.33_33] (id 2) > offset 0 > distance 0 > > Combination chain 0x38b65b0 > max distance 0, may reuse first > equal to 0x38b6730 + 0x38b68b0 in type vector(2) real(kind=8) > references: > combination ref > in statement predreastmp.48_10 = vect__32.31_78 + vect__28.25_100; > > distance 0 > combination ref > in statement predreastmp.50_17 = vect__42.41_138 + vect__38.36_29; > > distance 0 > > It's important to note that distance is equal to zero (happening within a > same loop iteration). > Aforementioned chains correspond to: > > ... > r2: vect__28.25_100 = MEM[(real(kind=8) *)vectp_a.23_102]; > vectp_a.23_99 = vectp_a.23_102 + 16; > vect__28.26_98 = MEM[(real(kind=8) *)vectp_a.23_99]; > vect__82.27_97 = vect__22.22_108; > vect__82.27_96 = vect__22.22_107; > vect__79.28_95 = vect__82.27_97 + vect__84.17_120; > vect__79.28_94 = vect__82.27_96 + vect__84.17_119; > r1: vect__32.31_78 = MEM[(real(kind=8) *)vectp_a.29_81]; > vectp_a.29_77 = vectp_a.29_81 + 16; > vect__32.32_76 = MEM[(real(kind=8) *)vectp_a.29_77]; > vect__38.35_39 = MEM[(real(kind=8) *)vectp_a.33_57]; > r2': vectp_a.33_33 = vectp_a.33_57 + 16; > vect__38.36_29 = MEM[(real(kind=8) *)vectp_a.33_33]; > vect__56.37_23 = vect__38.35_39; > vect__56.37_15 = vect__32.32_76; > vect__42.40_161 = MEM[(real(kind=8) *)vectp_a.38_163]; > vectp_a.38_141 = vectp_a.38_163 + 16; > r1': vect__42.41_138 = MEM[(real(kind=8) *)vectp_a.38_141]; > vect__54.42_135 = vect__42.40_161 + vect__56.37_23; > r1'+r2': predreastmp.50_17 = vect__42.41_138 + vect__38.36_29; > predreastmp.51_18 = vect__56.37_15; > vect__54.42_134 = predreastmp.50_17; > r1+r2: predreastmp.48_10 = vect__32.31_78 + vect__28.25_100; > ... > > Problematic construct is that while having load-only chains r1->r1' and > r2->r2', the combination > is actually r1'+r2'->r1+r2, which cause the troubles. I believe the proper > fix is to reject such > combinations where combined root stmt does not dominate usages. It's probably > corner case as it does > not reuse any values among loop iterations (which is main motivation of the > pass), it's doing PRE > if I'm right. > > Patch can bootstrap on ppc64le-redhat-linux and survives regression tests. > > Ready to be installed? I'm not sure. If we have such zero distance refs in the IL at the time pcom runs then not handling them will pessimize code-gen for cases where they are part of a larger chain. Esp. I don't like another stmt_dominates_stmt_p call and thus rather not handle length == 0 at all... We already seem to go great length in associating stuff when combining stuff thus isn't this maybe an artifact of this association? Maybe we simply need to sort the new chain after combining it so the root stmt comes last? Note that there seems to be only a single length per chain but not all refs in a chain need to have the same distance. This means your fix is likely incomplete? What prevents the situation to arise for distance != 0? Richard. > Martin >
Re: [PATCH] Be careful about combined chain with length == 0 (PR, tree-optimization/70754).
On Wed, Jan 18, 2017 at 10:10 AM, Martin Liškawrote: > Hello. > > After basic understanding of loop predictive commoning, the problematic > combined chain is: > > Loads-only chain 0x38b6730 (combined) > max distance 0 > references: > MEM[(real(kind=8) *)vectp_a.29_81] (id 1) > offset 20 > distance 0 > MEM[(real(kind=8) *)vectp_a.38_141] (id 3) > offset 20 > distance 0 > > Loads-only chain 0x38b68b0 (combined) > max distance 0 > references: > MEM[(real(kind=8) *)vectp_a.23_102] (id 0) > offset 0 > distance 0 > MEM[(real(kind=8) *)vectp_a.33_33] (id 2) > offset 0 > distance 0 > > Combination chain 0x38b65b0 > max distance 0, may reuse first > equal to 0x38b6730 + 0x38b68b0 in type vector(2) real(kind=8) > references: > combination ref > in statement predreastmp.48_10 = vect__32.31_78 + vect__28.25_100; > > distance 0 > combination ref > in statement predreastmp.50_17 = vect__42.41_138 + vect__38.36_29; > > distance 0 > > It's important to note that distance is equal to zero (happening within a > same loop iteration). > Aforementioned chains correspond to: > > ... > r2: vect__28.25_100 = MEM[(real(kind=8) *)vectp_a.23_102]; > vectp_a.23_99 = vectp_a.23_102 + 16; > vect__28.26_98 = MEM[(real(kind=8) *)vectp_a.23_99]; > vect__82.27_97 = vect__22.22_108; > vect__82.27_96 = vect__22.22_107; > vect__79.28_95 = vect__82.27_97 + vect__84.17_120; > vect__79.28_94 = vect__82.27_96 + vect__84.17_119; > r1: vect__32.31_78 = MEM[(real(kind=8) *)vectp_a.29_81]; > vectp_a.29_77 = vectp_a.29_81 + 16; > vect__32.32_76 = MEM[(real(kind=8) *)vectp_a.29_77]; > vect__38.35_39 = MEM[(real(kind=8) *)vectp_a.33_57]; > r2': vectp_a.33_33 = vectp_a.33_57 + 16; > vect__38.36_29 = MEM[(real(kind=8) *)vectp_a.33_33]; > vect__56.37_23 = vect__38.35_39; > vect__56.37_15 = vect__32.32_76; > vect__42.40_161 = MEM[(real(kind=8) *)vectp_a.38_163]; > vectp_a.38_141 = vectp_a.38_163 + 16; > r1': vect__42.41_138 = MEM[(real(kind=8) *)vectp_a.38_141]; > vect__54.42_135 = vect__42.40_161 + vect__56.37_23; > r1'+r2': predreastmp.50_17 = vect__42.41_138 + vect__38.36_29; > predreastmp.51_18 = vect__56.37_15; > vect__54.42_134 = predreastmp.50_17; > r1+r2: predreastmp.48_10 = vect__32.31_78 + vect__28.25_100; > ... > > Problematic construct is that while having load-only chains r1->r1' and > r2->r2', the combination > is actually r1'+r2'->r1+r2, which cause the troubles. I believe the proper > fix is to reject such > combinations where combined root stmt does not dominate usages. It's probably > corner case as it does > not reuse any values among loop iterations (which is main motivation of the > pass), it's doing PRE > if I'm right. I think this is OK, though I can't approve it. Later DOM pass should be able to pick up the redundant combination operation between predreastmp.50_17 and predreastmp.48_10, could you double check this? Thanks, bin > > Patch can bootstrap on ppc64le-redhat-linux and survives regression tests. > > Ready to be installed? > Martin >
[PATCH] Be careful about combined chain with length == 0 (PR, tree-optimization/70754).
Hello. After basic understanding of loop predictive commoning, the problematic combined chain is: Loads-only chain 0x38b6730 (combined) max distance 0 references: MEM[(real(kind=8) *)vectp_a.29_81] (id 1) offset 20 distance 0 MEM[(real(kind=8) *)vectp_a.38_141] (id 3) offset 20 distance 0 Loads-only chain 0x38b68b0 (combined) max distance 0 references: MEM[(real(kind=8) *)vectp_a.23_102] (id 0) offset 0 distance 0 MEM[(real(kind=8) *)vectp_a.33_33] (id 2) offset 0 distance 0 Combination chain 0x38b65b0 max distance 0, may reuse first equal to 0x38b6730 + 0x38b68b0 in type vector(2) real(kind=8) references: combination ref in statement predreastmp.48_10 = vect__32.31_78 + vect__28.25_100; distance 0 combination ref in statement predreastmp.50_17 = vect__42.41_138 + vect__38.36_29; distance 0 It's important to note that distance is equal to zero (happening within a same loop iteration). Aforementioned chains correspond to: ... r2: vect__28.25_100 = MEM[(real(kind=8) *)vectp_a.23_102]; vectp_a.23_99 = vectp_a.23_102 + 16; vect__28.26_98 = MEM[(real(kind=8) *)vectp_a.23_99]; vect__82.27_97 = vect__22.22_108; vect__82.27_96 = vect__22.22_107; vect__79.28_95 = vect__82.27_97 + vect__84.17_120; vect__79.28_94 = vect__82.27_96 + vect__84.17_119; r1: vect__32.31_78 = MEM[(real(kind=8) *)vectp_a.29_81]; vectp_a.29_77 = vectp_a.29_81 + 16; vect__32.32_76 = MEM[(real(kind=8) *)vectp_a.29_77]; vect__38.35_39 = MEM[(real(kind=8) *)vectp_a.33_57]; r2': vectp_a.33_33 = vectp_a.33_57 + 16; vect__38.36_29 = MEM[(real(kind=8) *)vectp_a.33_33]; vect__56.37_23 = vect__38.35_39; vect__56.37_15 = vect__32.32_76; vect__42.40_161 = MEM[(real(kind=8) *)vectp_a.38_163]; vectp_a.38_141 = vectp_a.38_163 + 16; r1': vect__42.41_138 = MEM[(real(kind=8) *)vectp_a.38_141]; vect__54.42_135 = vect__42.40_161 + vect__56.37_23; r1'+r2': predreastmp.50_17 = vect__42.41_138 + vect__38.36_29; predreastmp.51_18 = vect__56.37_15; vect__54.42_134 = predreastmp.50_17; r1+r2: predreastmp.48_10 = vect__32.31_78 + vect__28.25_100; ... Problematic construct is that while having load-only chains r1->r1' and r2->r2', the combination is actually r1'+r2'->r1+r2, which cause the troubles. I believe the proper fix is to reject such combinations where combined root stmt does not dominate usages. It's probably corner case as it does not reuse any values among loop iterations (which is main motivation of the pass), it's doing PRE if I'm right. Patch can bootstrap on ppc64le-redhat-linux and survives regression tests. Ready to be installed? Martin >From 41b153cf975374fff48419ec8ac5991ac134735f Mon Sep 17 00:00:00 2001 From: marxin <mli...@suse.cz> Date: Tue, 17 Jan 2017 14:22:40 +0100 Subject: [PATCH] Be careful about combined chain with length == 0 (PR tree-optimization/70754). gcc/testsuite/ChangeLog: 2017-01-17 Martin Liska <mli...@suse.cz> PR tree-optimization/70754 * gfortran.dg/pr70754.f90: New test. gcc/ChangeLog: 2017-01-17 Martin Liska <mli...@suse.cz> PR tree-optimization/70754 * tree-predcom.c (combine_chains): Do not create a combined chain with length equal to zero when root_stmt does not dominate stmts of references. --- gcc/testsuite/gfortran.dg/pr70754.f90 | 35 +++ gcc/tree-predcom.c| 10 ++ 2 files changed, 45 insertions(+) create mode 100644 gcc/testsuite/gfortran.dg/pr70754.f90 diff --git a/gcc/testsuite/gfortran.dg/pr70754.f90 b/gcc/testsuite/gfortran.dg/pr70754.f90 new file mode 100644 index 000..758901ce2b2 --- /dev/null +++ b/gcc/testsuite/gfortran.dg/pr70754.f90 @@ -0,0 +1,35 @@ +! { dg-options "-Ofast" } + +module m + implicit none + private + save + + integer, parameter, public :: & +ii4 = selected_int_kind(6), & +rr8 = selected_real_kind(13) + + integer (ii4), dimension(40,40,199), public :: xyz + public :: foo +contains + subroutine foo(a) +real (rr8), dimension(40,40), intent(out) :: a +real (rr8), dimension(40,40) :: b +integer (ii4), dimension(40,40) :: c +integer i, j + +do i=1,8 + b(i,j) = 123 * a(i,j) + a(i,j+1) & + + a(i,j) + a(i+1,j+1) & + + a(i+1,j) + a(i-1,j+1) & + + a(i-1,j) + c(i,j) = 123 +end do + +where ((xyz(:,:,2) /= 0) .and. (c /= 0)) + a = b/real(c) +elsewhere + a = 456 +endwhere + end subroutine foo +end module m diff --git a/gcc/tree-predcom.c b/gcc/tree-predcom.c index f0b70a61fb8..768f976cb87 100644 --- a/gcc/tree-predcom.c +++ b/gcc/tree-predcom.c @@ -2323,6 +2323,16 @@ combine_chains (chain_p ch1, chain_p ch2) root_stmt = get_chain_root (new_chain)->stmt; for (i = 1; new_chain->refs.iterate (i, ); i++) { + /* PR tree-optimization/70754 + Fo