| Message ID | f878cf36-465a-79c3-f37f-bffb8aa0d240@redhat.com |
|---|---|
| State | New |
| Headers | show |
| Series | [RFC/PATCH] updating global ranges and their effect on __builtin_unreachable code | expand |
On Wed, Jun 2, 2021 at 12:34 PM Aldy Hernandez via Gcc-patches <gcc-patches@gcc.gnu.org> wrote: > > We've been having "issues" in our branch when exporting to the global > space ranges that take into account previously known ranges > (SSA_NAME_RANGE_INFO, etc). For the longest time we had the export > feature turned off because it had the potential of removing > __builtin_unreachable code early in the pipeline. This was causing one > or two tests to fail. > > I finally got fed up, and investigated why. > > Take the following code: > > i_4 = somerandom (); > if (i_4 < 0) > goto <bb 3>; [INV] > else > goto <bb 4>; [INV] > > <bb 3> : > __builtin_unreachable (); > > <bb 4> : > > It turns out that both legacy evrp and VRP have code that notices the > above pattern and sets the *global* range for i_4 to [0,MAX]. That is, > the range for i_4 is set, not at BB4, but at the definition site. See > uses of assert_unreachable_fallthru_edge_p() for details. > > This global range causes subsequent passes (VRP1 in the testcase below), > to remove the checks and the __builtin_unreachable code altogether. > > // pr80776-1.c > int somerandom (void); > void > Foo (void) > { > int i = somerandom (); > if (! (0 <= i)) > __builtin_unreachable (); > if (! (0 <= i && i <= 999999)) > __builtin_unreachable (); > sprintf (number, "%d", i); > } > > This means that by the time the -Wformat-overflow warning runs, the > above sprintf has been left unguarded, and a bogus warning is issued. > > Currently the above test does not warn, but that's because of an > oversight in export_global_ranges(). This function is disregarding > known global ranges (SSA_NAME_RANGE_INFO and SSA_NAME_PTR_INFO) and only > setting ranges the ranger knows about. > > For the above test the IL is: > > <bb 2> : > i_4 = somerandom (); > if (i_4 < 0) > goto <bb 3>; [INV] > else > goto <bb 4>; [INV] > > <bb 3> : > __builtin_unreachable (); > > <bb 4> : > i.0_1 = (unsigned int) i_4; > if (i.0_1 > 999999) > goto <bb 5>; [INV] > else > goto <bb 6>; [INV] > > <bb 5> : > __builtin_unreachable (); > > <bb 6> : > _7 = __builtin___sprintf_chk (&number, 1, 7, "%d", i_4); > > > Legacy evrp has determined that the range for i_4 is [0,MAX] per my > analysis above, but ranger has no known range for i_4 at the definition > site. So at export_global_ranges time, ranger leaves the [0,MAX] alone. > > OTOH, evrp sets the global range at the definition for i.0_1 to > [0,999999] per the same unreachable feature. However, ranger has > correctly determined that the range for i.0_1 at the definition is > [0,MAX], which it then proceeds to export. Since the current > export_global_ranges (mistakenly) does not take into account previous > global ranges, the ranges in the global tables end up like this: > > i_4: [0, MAX] > i.0_1: [0, MAX] > > This causes the first unreachable block to be removed in VRP1, but the > second one to remain. Later VRP can determine that i_4 in the sprintf > call is [0,999999], and no warning is issued. > > But... the missing bogus warning is due to current export_global_ranges > ignoring SSA_NAME_RANGE_INFO and friends, something which I'd like to > fix. However, fixing this, gets us back to: > > i_4: [0, MAX] > i.0_1: [0, 999999] > > Which means, we'll be back to removing the unreachable blocks and > issuing a warning in pr80776-1.c (like we have been since the beginning > of time). > > The attached patch fixes export_global_ranges to the expected behavior, > and adds the previous XFAIL to pr80776-1.c, while documenting why this > warning is issued in the first place. > > Once legacy evrp is removed, this won't be an issue, as ranges in the IL > will tell the truth. However, this will mean that we will no longer > remove the first __builtin_unreachable combo. But ISTM, that would be > correct behavior ??. > > BTW, in addition to this patch we could explore removing the > assert_unreachable_fallthru_edge_p() use in the evrp_analyzer, since it > is no longer needed to get the warnings in the testcases in the original > PR correctly (gcc.dg/pr80776-[12].c). But the whole point of all this singing and dancing is not to make warnings but to be able to implement assert (); or assume (); that will result in no code but optimization based on the assumption. That means that all the checks guarding __builtin_unreachable () should be removed at the GIMPLE level - just not too early to preserve range info on the variables participating in the guarding condition. So yes, it sounds fragile but instead it's carefully architected. Heh. In particular it is designed so that early optimization leaves those unreachable () around (for later LTO consumption and inlining, etc. to be able to re-create the ranges) whilst VRP1 / DOM will end up eliminating them. I think we have testcases that verify said behavior, namely optimize out range checks based on the assertions - maybe missed the case where this only happens after inlining (important for your friendly C++ abstraction hell), and the unreachable()s gone. Please make sure to not break that. Thanks, Richard. > Tested on x86-64 Linux. > > OK? > > Aldy
On 6/2/21 7:52 AM, Richard Biener wrote: > On Wed, Jun 2, 2021 at 12:34 PM Aldy Hernandez via Gcc-patches > <gcc-patches@gcc.gnu.org> wrote: >> We've been having "issues" in our branch when exporting to the global >> space ranges that take into account previously known ranges >> (SSA_NAME_RANGE_INFO, etc). For the longest time we had the export >> feature turned off because it had the potential of removing >> __builtin_unreachable code early in the pipeline. This was causing one >> or two tests to fail. >> >> I finally got fed up, and investigated why. >> >> Take the following code: >> >> i_4 = somerandom (); >> if (i_4 < 0) >> goto <bb 3>; [INV] >> else >> goto <bb 4>; [INV] >> >> <bb 3> : >> __builtin_unreachable (); >> >> <bb 4> : >> >> It turns out that both legacy evrp and VRP have code that notices the >> above pattern and sets the *global* range for i_4 to [0,MAX]. That is, >> the range for i_4 is set, not at BB4, but at the definition site. See >> uses of assert_unreachable_fallthru_edge_p() for details. >> >> This global range causes subsequent passes (VRP1 in the testcase below), >> to remove the checks and the __builtin_unreachable code altogether. >> >> // pr80776-1.c >> int somerandom (void); >> void >> Foo (void) >> { >> int i = somerandom (); >> if (! (0 <= i)) >> __builtin_unreachable (); >> if (! (0 <= i && i <= 999999)) >> __builtin_unreachable (); >> sprintf (number, "%d", i); >> } >> >> This means that by the time the -Wformat-overflow warning runs, the >> above sprintf has been left unguarded, and a bogus warning is issued. >> >> Currently the above test does not warn, but that's because of an >> oversight in export_global_ranges(). This function is disregarding >> known global ranges (SSA_NAME_RANGE_INFO and SSA_NAME_PTR_INFO) and only >> setting ranges the ranger knows about. >> >> For the above test the IL is: >> >> <bb 2> : >> i_4 = somerandom (); >> if (i_4 < 0) >> goto <bb 3>; [INV] >> else >> goto <bb 4>; [INV] >> >> <bb 3> : >> __builtin_unreachable (); >> >> <bb 4> : >> i.0_1 = (unsigned int) i_4; >> if (i.0_1 > 999999) >> goto <bb 5>; [INV] >> else >> goto <bb 6>; [INV] >> >> <bb 5> : >> __builtin_unreachable (); >> >> <bb 6> : >> _7 = __builtin___sprintf_chk (&number, 1, 7, "%d", i_4); >> >> >> Legacy evrp has determined that the range for i_4 is [0,MAX] per my >> analysis above, but ranger has no known range for i_4 at the definition >> site. So at export_global_ranges time, ranger leaves the [0,MAX] alone. >> >> OTOH, evrp sets the global range at the definition for i.0_1 to >> [0,999999] per the same unreachable feature. However, ranger has >> correctly determined that the range for i.0_1 at the definition is >> [0,MAX], which it then proceeds to export. Since the current >> export_global_ranges (mistakenly) does not take into account previous >> global ranges, the ranges in the global tables end up like this: >> >> i_4: [0, MAX] >> i.0_1: [0, MAX] >> >> This causes the first unreachable block to be removed in VRP1, but the >> second one to remain. Later VRP can determine that i_4 in the sprintf >> call is [0,999999], and no warning is issued. >> >> But... the missing bogus warning is due to current export_global_ranges >> ignoring SSA_NAME_RANGE_INFO and friends, something which I'd like to >> fix. However, fixing this, gets us back to: >> >> i_4: [0, MAX] >> i.0_1: [0, 999999] >> >> Which means, we'll be back to removing the unreachable blocks and >> issuing a warning in pr80776-1.c (like we have been since the beginning >> of time). >> >> The attached patch fixes export_global_ranges to the expected behavior, >> and adds the previous XFAIL to pr80776-1.c, while documenting why this >> warning is issued in the first place. >> >> Once legacy evrp is removed, this won't be an issue, as ranges in the IL >> will tell the truth. However, this will mean that we will no longer >> remove the first __builtin_unreachable combo. But ISTM, that would be >> correct behavior ??. >> >> BTW, in addition to this patch we could explore removing the >> assert_unreachable_fallthru_edge_p() use in the evrp_analyzer, since it >> is no longer needed to get the warnings in the testcases in the original >> PR correctly (gcc.dg/pr80776-[12].c). > But the whole point of all this singing and dancing is not to make > warnings but to be able to implement assert (); or assume (); that > will result in no code but optimization based on the assumption. > > That means that all the checks guarding __builtin_unreachable () > should be removed at the GIMPLE level - just not too early > to preserve range info on the variables participating in the > guarding condition. > > So yes, it sounds fragile but instead it's carefully architected. Heh. > > In particular it is designed so that early optimization leaves those > unreachable () around (for later LTO consumption and inlining, etc. > to be able to re-create the ranges) whilst VRP1 / DOM will end up > eliminating them. I think we have testcases that verify said behavior, > namely optimize out range checks based on the assertions - maybe missed > the case where this only happens after inlining (important for your friendly > C++ abstraction hell), and the unreachable()s gone. > > Please make sure to not break that. Let me see if I understand... we want to leave builtin_unreachable around until a certain point in compilation, and then remove them? It seems to me that either A) a builtin_unreachable () provides useful information,( ie, information that isn't otherwise obvious, and would therefore stay in the IL and not be eliminated by the various optimizations until it is.. ). OR B )its telling us something is we can already figure out, in which case we will naturally eliminate the branches leading to it, and then it goes away on its own. By that standard, any builtin_unreachable that makes it late into the optimization cycle is useful... So can't we just leave those until whatever point it is we decide the information they provide is no longer needed, and then simply drop them? Rewrite any branch to an unreachable so that its truly unreachable, and then the next cfg cleanup makes them all go away? That could be part of a late/final VRP or a pass of its own. This whole checking to see if they are there seems fragile, because it doesn't tell us whether they are useful or not.. Andrew
On 6/2/21 1:52 PM, Richard Biener wrote: > On Wed, Jun 2, 2021 at 12:34 PM Aldy Hernandez via Gcc-patches > <gcc-patches@gcc.gnu.org> wrote: > But the whole point of all this singing and dancing is not to make > warnings but to be able to implement assert (); or assume (); that > will result in no code but optimization based on the assumption. > > That means that all the checks guarding __builtin_unreachable () > should be removed at the GIMPLE level - just not too early > to preserve range info on the variables participating in the > guarding condition. > > So yes, it sounds fragile but instead it's carefully architected. Heh. > > In particular it is designed so that early optimization leaves those > unreachable () around (for later LTO consumption and inlining, etc. > to be able to re-create the ranges) whilst VRP1 / DOM will end up > eliminating them. I think we have testcases that verify said behavior, > namely optimize out range checks based on the assertions - maybe missed Understood. I will note that my proposed patch does not remove any unreachables, and maintains current behavior. It just refines the ranges from the ranger with current global ranges. So I think the patch should go in, regardless of what is decided with __builtin_unreachables downthread. > the case where this only happens after inlining (important for your friendly > C++ abstraction hell), and the unreachable()s gone. I have pointed this out before, and will repeat it in case you missed it: "Richard, you have made it very clear that we disagree on core design issues, but that's no reason to continually make snide comments on every patch or PR. Can we keep the discussions focused on the technical bits?" https://gcc.gnu.org/pipermail/gcc-patches/2021-April/569072.html
On 6/2/21 6:32 AM, Aldy Hernandez wrote: > We've been having "issues" in our branch when exporting to the global > space ranges that take into account previously known ranges > (SSA_NAME_RANGE_INFO, etc). For the longest time we had the export > feature turned off because it had the potential of removing > __builtin_unreachable code early in the pipeline. This was causing > one or two tests to fail. > > I finally got fed up, and investigated why. > > Take the following code: > > i_4 = somerandom (); > if (i_4 < 0) > goto <bb 3>; [INV] > else > goto <bb 4>; [INV] > > <bb 3> : > __builtin_unreachable (); > > <bb 4> : > > It turns out that both legacy evrp and VRP have code that notices the > above pattern and sets the *global* range for i_4 to [0,MAX]. That is, > the range for i_4 is set, not at BB4, but at the definition site. See > uses of assert_unreachable_fallthru_edge_p() for details. > > This global range causes subsequent passes (VRP1 in the testcase > below), to remove the checks and the __builtin_unreachable code > altogether. > > // pr80776-1.c > int somerandom (void); > void > Foo (void) > { > int i = somerandom (); > if (! (0 <= i)) > __builtin_unreachable (); > if (! (0 <= i && i <= 999999)) > __builtin_unreachable (); > sprintf (number, "%d", i); > } > > This means that by the time the -Wformat-overflow warning runs, the > above sprintf has been left unguarded, and a bogus warning is issued. > > Currently the above test does not warn, but that's because of an > oversight in export_global_ranges(). This function is disregarding > known global ranges (SSA_NAME_RANGE_INFO and SSA_NAME_PTR_INFO) and > only setting ranges the ranger knows about. > > For the above test the IL is: > > <bb 2> : > i_4 = somerandom (); > if (i_4 < 0) > goto <bb 3>; [INV] > else > goto <bb 4>; [INV] > > <bb 3> : > __builtin_unreachable (); > > <bb 4> : > i.0_1 = (unsigned int) i_4; > if (i.0_1 > 999999) > goto <bb 5>; [INV] > else > goto <bb 6>; [INV] > > <bb 5> : > __builtin_unreachable (); > > <bb 6> : > _7 = __builtin___sprintf_chk (&number, 1, 7, "%d", i_4); > > > Legacy evrp has determined that the range for i_4 is [0,MAX] per my > analysis above, but ranger has no known range for i_4 at the > definition site. So at export_global_ranges time, ranger leaves the > [0,MAX] alone. > > OTOH, evrp sets the global range at the definition for i.0_1 to > [0,999999] per the same unreachable feature. However, ranger has > correctly determined that the range for i.0_1 at the definition is > [0,MAX], which it then proceeds to export. Since the current > export_global_ranges (mistakenly) does not take into account previous > global ranges, the ranges in the global tables end up like this: > > i_4: [0, MAX] > i.0_1: [0, MAX] > > This causes the first unreachable block to be removed in VRP1, but the > second one to remain. Later VRP can determine that i_4 in the sprintf > call is [0,999999], and no warning is issued. > > But... the missing bogus warning is due to current > export_global_ranges ignoring SSA_NAME_RANGE_INFO and friends, > something which I'd like to fix. However, fixing this, gets us back to: > > i_4: [0, MAX] > i.0_1: [0, 999999] > > Which means, we'll be back to removing the unreachable blocks and > issuing a warning in pr80776-1.c (like we have been since the > beginning of time). > > The attached patch fixes export_global_ranges to the expected > behavior, and adds the previous XFAIL to pr80776-1.c, while > documenting why this warning is issued in the first place. > > Once legacy evrp is removed, this won't be an issue, as ranges in the > IL will tell the truth. However, this will mean that we will no > longer remove the first __builtin_unreachable combo. But ISTM, that > would be correct behavior ??. > > > > Tested on x86-64 Linux. > > OK? > > If I understand correctly, we will have to ensure that __builtin_unreachable () and the branches to them are removed by the end of gimple one way or another. While legacy EVRP is still running, that isnt a problem. This patch merely changes the values we export from ranger to be more up to date... and some fallout you've encountered. This might get taken care of down the road.. there is some potential for identifying a range that dominates all uses and making that the global range.. that would also resolve the issue of builtin_unreachable(). Anyway, we can deal with this when we try to move to ranger-only mode OK.
On Wed, Jun 2, 2021 at 2:53 PM Andrew MacLeod <amacleod@redhat.com> wrote: > > On 6/2/21 7:52 AM, Richard Biener wrote: > > On Wed, Jun 2, 2021 at 12:34 PM Aldy Hernandez via Gcc-patches > > <gcc-patches@gcc.gnu.org> wrote: > >> We've been having "issues" in our branch when exporting to the global > >> space ranges that take into account previously known ranges > >> (SSA_NAME_RANGE_INFO, etc). For the longest time we had the export > >> feature turned off because it had the potential of removing > >> __builtin_unreachable code early in the pipeline. This was causing one > >> or two tests to fail. > >> > >> I finally got fed up, and investigated why. > >> > >> Take the following code: > >> > >> i_4 = somerandom (); > >> if (i_4 < 0) > >> goto <bb 3>; [INV] > >> else > >> goto <bb 4>; [INV] > >> > >> <bb 3> : > >> __builtin_unreachable (); > >> > >> <bb 4> : > >> > >> It turns out that both legacy evrp and VRP have code that notices the > >> above pattern and sets the *global* range for i_4 to [0,MAX]. That is, > >> the range for i_4 is set, not at BB4, but at the definition site. See > >> uses of assert_unreachable_fallthru_edge_p() for details. > >> > >> This global range causes subsequent passes (VRP1 in the testcase below), > >> to remove the checks and the __builtin_unreachable code altogether. > >> > >> // pr80776-1.c > >> int somerandom (void); > >> void > >> Foo (void) > >> { > >> int i = somerandom (); > >> if (! (0 <= i)) > >> __builtin_unreachable (); > >> if (! (0 <= i && i <= 999999)) > >> __builtin_unreachable (); > >> sprintf (number, "%d", i); > >> } > >> > >> This means that by the time the -Wformat-overflow warning runs, the > >> above sprintf has been left unguarded, and a bogus warning is issued. > >> > >> Currently the above test does not warn, but that's because of an > >> oversight in export_global_ranges(). This function is disregarding > >> known global ranges (SSA_NAME_RANGE_INFO and SSA_NAME_PTR_INFO) and only > >> setting ranges the ranger knows about. > >> > >> For the above test the IL is: > >> > >> <bb 2> : > >> i_4 = somerandom (); > >> if (i_4 < 0) > >> goto <bb 3>; [INV] > >> else > >> goto <bb 4>; [INV] > >> > >> <bb 3> : > >> __builtin_unreachable (); > >> > >> <bb 4> : > >> i.0_1 = (unsigned int) i_4; > >> if (i.0_1 > 999999) > >> goto <bb 5>; [INV] > >> else > >> goto <bb 6>; [INV] > >> > >> <bb 5> : > >> __builtin_unreachable (); > >> > >> <bb 6> : > >> _7 = __builtin___sprintf_chk (&number, 1, 7, "%d", i_4); > >> > >> > >> Legacy evrp has determined that the range for i_4 is [0,MAX] per my > >> analysis above, but ranger has no known range for i_4 at the definition > >> site. So at export_global_ranges time, ranger leaves the [0,MAX] alone. > >> > >> OTOH, evrp sets the global range at the definition for i.0_1 to > >> [0,999999] per the same unreachable feature. However, ranger has > >> correctly determined that the range for i.0_1 at the definition is > >> [0,MAX], which it then proceeds to export. Since the current > >> export_global_ranges (mistakenly) does not take into account previous > >> global ranges, the ranges in the global tables end up like this: > >> > >> i_4: [0, MAX] > >> i.0_1: [0, MAX] > >> > >> This causes the first unreachable block to be removed in VRP1, but the > >> second one to remain. Later VRP can determine that i_4 in the sprintf > >> call is [0,999999], and no warning is issued. > >> > >> But... the missing bogus warning is due to current export_global_ranges > >> ignoring SSA_NAME_RANGE_INFO and friends, something which I'd like to > >> fix. However, fixing this, gets us back to: > >> > >> i_4: [0, MAX] > >> i.0_1: [0, 999999] > >> > >> Which means, we'll be back to removing the unreachable blocks and > >> issuing a warning in pr80776-1.c (like we have been since the beginning > >> of time). > >> > >> The attached patch fixes export_global_ranges to the expected behavior, > >> and adds the previous XFAIL to pr80776-1.c, while documenting why this > >> warning is issued in the first place. > >> > >> Once legacy evrp is removed, this won't be an issue, as ranges in the IL > >> will tell the truth. However, this will mean that we will no longer > >> remove the first __builtin_unreachable combo. But ISTM, that would be > >> correct behavior ??. > >> > >> BTW, in addition to this patch we could explore removing the > >> assert_unreachable_fallthru_edge_p() use in the evrp_analyzer, since it > >> is no longer needed to get the warnings in the testcases in the original > >> PR correctly (gcc.dg/pr80776-[12].c). > > But the whole point of all this singing and dancing is not to make > > warnings but to be able to implement assert (); or assume (); that > > will result in no code but optimization based on the assumption. > > > > That means that all the checks guarding __builtin_unreachable () > > should be removed at the GIMPLE level - just not too early > > to preserve range info on the variables participating in the > > guarding condition. > > > > So yes, it sounds fragile but instead it's carefully architected. Heh. > > > > In particular it is designed so that early optimization leaves those > > unreachable () around (for later LTO consumption and inlining, etc. > > to be able to re-create the ranges) whilst VRP1 / DOM will end up > > eliminating them. I think we have testcases that verify said behavior, > > namely optimize out range checks based on the assertions - maybe missed > > the case where this only happens after inlining (important for your friendly > > C++ abstraction hell), and the unreachable()s gone. > > > > Please make sure to not break that. > > Let me see if I understand... we want to leave builtin_unreachable > around until a certain point in compilation, and then remove them? > > It seems to me that either > > A) a builtin_unreachable () provides useful information,( ie, > information that isn't otherwise obvious, and would therefore stay in > the IL and not be eliminated by the various optimizations until it is.. > ). OR > > B )its telling us something is we can already figure out, in which > case we will naturally eliminate the branches leading to it, and then it > goes away on its own. > > By that standard, any builtin_unreachable that makes it late into the > optimization cycle is useful... So can't we just leave those until > whatever point it is we decide the information they provide is no longer > needed, and then simply drop them? Rewrite any branch to an unreachable > so that its truly unreachable, and then the next cfg cleanup makes them > all go away? That could be part of a late/final VRP or a pass of its own. > > This whole checking to see if they are there seems fragile, because it > doesn't tell us whether they are useful or not.. It's a combination of A and B. It's A) until after IPA and after IPA the information is transitioned to range information on the SSA names which is then persistent (but it for example does not survive all IPA optimizations - definitely not LTO streaming for example). So we're transitioning from a if (a) __builtin_unreachable () representation of the useful information to representing it by on-the-side info (SSA_NAME_RANGE_INFO) on 'a'. That should work fine with ranger as well I think - now, what was fragile was that the way the if (a) __builtin_unreachable () IL was preserved was simply that there's a single EVRP pass before IPA only and the way it is (was) structured makes sure that once we reflect the IL on the range info of 'a' it is not used (in the same EVRP pass) to elide the condition and nothing does (did) that before VRP1 either. Richard. > Andrew > > > > > >
On Wed, Jun 2, 2021 at 4:53 PM Aldy Hernandez <aldyh@redhat.com> wrote: > > > > On 6/2/21 1:52 PM, Richard Biener wrote: > > On Wed, Jun 2, 2021 at 12:34 PM Aldy Hernandez via Gcc-patches > > <gcc-patches@gcc.gnu.org> wrote: > > > But the whole point of all this singing and dancing is not to make > > warnings but to be able to implement assert (); or assume (); that > > will result in no code but optimization based on the assumption. > > > > That means that all the checks guarding __builtin_unreachable () > > should be removed at the GIMPLE level - just not too early > > to preserve range info on the variables participating in the > > guarding condition. > > > > So yes, it sounds fragile but instead it's carefully architected. Heh. > > > > In particular it is designed so that early optimization leaves those > > unreachable () around (for later LTO consumption and inlining, etc. > > to be able to re-create the ranges) whilst VRP1 / DOM will end up > > eliminating them. I think we have testcases that verify said behavior, > > namely optimize out range checks based on the assertions - maybe missed > > Understood. > > I will note that my proposed patch does not remove any unreachables, and > maintains current behavior. It just refines the ranges from the ranger > with current global ranges. So I think the patch should go in, > regardless of what is decided with __builtin_unreachables downthread. > > > the case where this only happens after inlining (important for your friendly > > C++ abstraction hell), and the unreachable()s gone. > > I have pointed this out before, and will repeat it in case you missed it: > > "Richard, you have made it very clear that we disagree on core design > issues, but that's no reason to continually make snide comments on every > patch or PRs Can we keep the discussions focused on the technical bits?" You need to stop taking every sentence I write as personal insult. I was refering to C++ abstraction in general in the sense as that we should be prepared to handle index checking removal even across inline boundaries. Reading my comment I guess the "your" might mislead you - sorry for not being a native speaker and thus picking a wrong general term here. Richard. > https://gcc.gnu.org/pipermail/gcc-patches/2021-April/569072.html >
On Mon, Jun 7, 2021 at 9:30 AM Richard Biener <richard.guenther@gmail.com> wrote: > > On Wed, Jun 2, 2021 at 4:53 PM Aldy Hernandez <aldyh@redhat.com> wrote: > > > > > > > > On 6/2/21 1:52 PM, Richard Biener wrote: > > > On Wed, Jun 2, 2021 at 12:34 PM Aldy Hernandez via Gcc-patches > > > <gcc-patches@gcc.gnu.org> wrote: > > > > > the case where this only happens after inlining (important for your friendly > > > C++ abstraction hell), and the unreachable()s gone. > > > > I have pointed this out before, and will repeat it in case you missed it: > > > > "Richard, you have made it very clear that we disagree on core design > > issues, but that's no reason to continually make snide comments on every > > patch or PRs Can we keep the discussions focused on the technical bits?" > > You need to stop taking every sentence I write as personal insult. I was > refering to C++ abstraction in general in the sense as that we should be > prepared to handle index checking removal even across inline boundaries. > Reading my comment I guess the "your" might mislead you - sorry for > not being a native speaker and thus picking a wrong general term here. > > Richard. > > > https://gcc.gnu.org/pipermail/gcc-patches/2021-April/569072.html No, I am only addressing the thinly veiled insults and snide remarks you frequently make. And I will continue to do so if you steer off topic. These are not language or cultural issues so don't try to paint them as such. I am also not a native speaker and do not use it as an excuse for my behavior. Aldy
On 6/7/21 3:25 AM, Richard Biener wrote: > On Wed, Jun 2, 2021 at 2:53 PM Andrew MacLeod <amacleod@redhat.com> wrote: >> On 6/2/21 7:52 AM, Richard Biener wrote: >>> On Wed, Jun 2, 2021 at 12:34 PM Aldy Hernandez via Gcc-patches >>> <gcc-patches@gcc.gnu.org> wrote: >>>> We've been having "issues" in our branch when exporting to the global >>>> space ranges that take into account previously known ranges >>>> (SSA_NAME_RANGE_INFO, etc). For the longest time we had the export >>>> feature turned off because it had the potential of removing >>>> __builtin_unreachable code early in the pipeline. This was causing one >>>> or two tests to fail. >>>> >>>> I finally got fed up, and investigated why. >>>> >>>> Take the following code: >>>> >>>> i_4 = somerandom (); >>>> if (i_4 < 0) >>>> goto <bb 3>; [INV] >>>> else >>>> goto <bb 4>; [INV] >>>> >>>> <bb 3> : >>>> __builtin_unreachable (); >>>> >>>> <bb 4> : >>>> >>>> It turns out that both legacy evrp and VRP have code that notices the >>>> above pattern and sets the *global* range for i_4 to [0,MAX]. That is, >>>> the range for i_4 is set, not at BB4, but at the definition site. See >>>> uses of assert_unreachable_fallthru_edge_p() for details. >>>> >>>> This global range causes subsequent passes (VRP1 in the testcase below), >>>> to remove the checks and the __builtin_unreachable code altogether. >>>> >>>> // pr80776-1.c >>>> int somerandom (void); >>>> void >>>> Foo (void) >>>> { >>>> int i = somerandom (); >>>> if (! (0 <= i)) >>>> __builtin_unreachable (); >>>> if (! (0 <= i && i <= 999999)) >>>> __builtin_unreachable (); >>>> sprintf (number, "%d", i); >>>> } >>>> >>>> This means that by the time the -Wformat-overflow warning runs, the >>>> above sprintf has been left unguarded, and a bogus warning is issued. >>>> >>>> Currently the above test does not warn, but that's because of an >>>> oversight in export_global_ranges(). This function is disregarding >>>> known global ranges (SSA_NAME_RANGE_INFO and SSA_NAME_PTR_INFO) and only >>>> setting ranges the ranger knows about. >>>> >>>> For the above test the IL is: >>>> >>>> <bb 2> : >>>> i_4 = somerandom (); >>>> if (i_4 < 0) >>>> goto <bb 3>; [INV] >>>> else >>>> goto <bb 4>; [INV] >>>> >>>> <bb 3> : >>>> __builtin_unreachable (); >>>> >>>> <bb 4> : >>>> i.0_1 = (unsigned int) i_4; >>>> if (i.0_1 > 999999) >>>> goto <bb 5>; [INV] >>>> else >>>> goto <bb 6>; [INV] >>>> >>>> <bb 5> : >>>> __builtin_unreachable (); >>>> >>>> <bb 6> : >>>> _7 = __builtin___sprintf_chk (&number, 1, 7, "%d", i_4); >>>> >>>> >>>> Legacy evrp has determined that the range for i_4 is [0,MAX] per my >>>> analysis above, but ranger has no known range for i_4 at the definition >>>> site. So at export_global_ranges time, ranger leaves the [0,MAX] alone. >>>> >>>> OTOH, evrp sets the global range at the definition for i.0_1 to >>>> [0,999999] per the same unreachable feature. However, ranger has >>>> correctly determined that the range for i.0_1 at the definition is >>>> [0,MAX], which it then proceeds to export. Since the current >>>> export_global_ranges (mistakenly) does not take into account previous >>>> global ranges, the ranges in the global tables end up like this: >>>> >>>> i_4: [0, MAX] >>>> i.0_1: [0, MAX] >>>> >>>> This causes the first unreachable block to be removed in VRP1, but the >>>> second one to remain. Later VRP can determine that i_4 in the sprintf >>>> call is [0,999999], and no warning is issued. >>>> >>>> But... the missing bogus warning is due to current export_global_ranges >>>> ignoring SSA_NAME_RANGE_INFO and friends, something which I'd like to >>>> fix. However, fixing this, gets us back to: >>>> >>>> i_4: [0, MAX] >>>> i.0_1: [0, 999999] >>>> >>>> Which means, we'll be back to removing the unreachable blocks and >>>> issuing a warning in pr80776-1.c (like we have been since the beginning >>>> of time). >>>> >>>> The attached patch fixes export_global_ranges to the expected behavior, >>>> and adds the previous XFAIL to pr80776-1.c, while documenting why this >>>> warning is issued in the first place. >>>> >>>> Once legacy evrp is removed, this won't be an issue, as ranges in the IL >>>> will tell the truth. However, this will mean that we will no longer >>>> remove the first __builtin_unreachable combo. But ISTM, that would be >>>> correct behavior ??. >>>> >>>> BTW, in addition to this patch we could explore removing the >>>> assert_unreachable_fallthru_edge_p() use in the evrp_analyzer, since it >>>> is no longer needed to get the warnings in the testcases in the original >>>> PR correctly (gcc.dg/pr80776-[12].c). >>> But the whole point of all this singing and dancing is not to make >>> warnings but to be able to implement assert (); or assume (); that >>> will result in no code but optimization based on the assumption. >>> >>> That means that all the checks guarding __builtin_unreachable () >>> should be removed at the GIMPLE level - just not too early >>> to preserve range info on the variables participating in the >>> guarding condition. >>> >>> So yes, it sounds fragile but instead it's carefully architected. Heh. >>> >>> In particular it is designed so that early optimization leaves those >>> unreachable () around (for later LTO consumption and inlining, etc. >>> to be able to re-create the ranges) whilst VRP1 / DOM will end up >>> eliminating them. I think we have testcases that verify said behavior, >>> namely optimize out range checks based on the assertions - maybe missed >>> the case where this only happens after inlining (important for your friendly >>> C++ abstraction hell), and the unreachable()s gone. >>> >>> Please make sure to not break that. >> Let me see if I understand... we want to leave builtin_unreachable >> around until a certain point in compilation, and then remove them? >> >> It seems to me that either >> >> A) a builtin_unreachable () provides useful information,( ie, >> information that isn't otherwise obvious, and would therefore stay in >> the IL and not be eliminated by the various optimizations until it is.. >> ). OR >> >> B )its telling us something is we can already figure out, in which >> case we will naturally eliminate the branches leading to it, and then it >> goes away on its own. >> >> By that standard, any builtin_unreachable that makes it late into the >> optimization cycle is useful... So can't we just leave those until >> whatever point it is we decide the information they provide is no longer >> needed, and then simply drop them? Rewrite any branch to an unreachable >> so that its truly unreachable, and then the next cfg cleanup makes them >> all go away? That could be part of a late/final VRP or a pass of its own. >> >> This whole checking to see if they are there seems fragile, because it >> doesn't tell us whether they are useful or not.. > It's a combination of A and B. It's A) until after IPA and after IPA the > information is transitioned to range information on the SSA names > which is then persistent (but it for example does not survive all > IPA optimizations - definitely not LTO streaming for example). So > we're transitioning from a if (a) __builtin_unreachable () representation > of the useful information to representing it by on-the-side info > (SSA_NAME_RANGE_INFO) > on 'a'. > > That should work fine with ranger as well I think - now, what was fragile > was that the way the if (a) __builtin_unreachable () IL was preserved > was simply that there's a single EVRP pass before IPA only and the > way it is (was) structured makes sure that once we reflect the IL on > the range info of 'a' it is not used (in the same EVRP pass) to elide > the condition and nothing does (did) that before VRP1 either. > > Richard. OK, lets see if I follow. The problem is that if we do eliminate the if and __builtin_unreachable too early, LTO streaming is likely to/might lose the information? and maybe some of the other IPA passes will not maintain the ssa_name_range_info data and thus also lose the info. So once IPA is done, we'd be free to do eliminate at will when they aren't useful any morer? And if I continue to follow that logic, then ranger shouldn't start with global information from the SSA_NAME_RANGE_INFO until post-IPA... then its free to pick up that info and eliminate anything it can. At least until IPA and LTO are 100% range propagators :-) so in theory, we could have a flag for post-ipa that allows us to pick better starting global ranges when they are available. we could wrap that up with the enable_ranger() call.. checks to see what pass we're in and if post-ipa enables global access? or is there such a query already available? Andrew PS Ah, and now that I re-read, i think we're both saying the same thing? :-) so it boils down to how do we check post-ipa. Is there any movement to making LTO maintain any range info it currently loses? Maybe this is an opportunity :-) I know it maintains some, because it was part of the reason we dont use globals now
On Mon, Jun 7, 2021 at 3:37 PM Andrew MacLeod <amacleod@redhat.com> wrote: > > On 6/7/21 3:25 AM, Richard Biener wrote: > > On Wed, Jun 2, 2021 at 2:53 PM Andrew MacLeod <amacleod@redhat.com> wrote: > >> On 6/2/21 7:52 AM, Richard Biener wrote: > >>> On Wed, Jun 2, 2021 at 12:34 PM Aldy Hernandez via Gcc-patches > >>> <gcc-patches@gcc.gnu.org> wrote: > >>>> We've been having "issues" in our branch when exporting to the global > >>>> space ranges that take into account previously known ranges > >>>> (SSA_NAME_RANGE_INFO, etc). For the longest time we had the export > >>>> feature turned off because it had the potential of removing > >>>> __builtin_unreachable code early in the pipeline. This was causing one > >>>> or two tests to fail. > >>>> > >>>> I finally got fed up, and investigated why. > >>>> > >>>> Take the following code: > >>>> > >>>> i_4 = somerandom (); > >>>> if (i_4 < 0) > >>>> goto <bb 3>; [INV] > >>>> else > >>>> goto <bb 4>; [INV] > >>>> > >>>> <bb 3> : > >>>> __builtin_unreachable (); > >>>> > >>>> <bb 4> : > >>>> > >>>> It turns out that both legacy evrp and VRP have code that notices the > >>>> above pattern and sets the *global* range for i_4 to [0,MAX]. That is, > >>>> the range for i_4 is set, not at BB4, but at the definition site. See > >>>> uses of assert_unreachable_fallthru_edge_p() for details. > >>>> > >>>> This global range causes subsequent passes (VRP1 in the testcase below), > >>>> to remove the checks and the __builtin_unreachable code altogether. > >>>> > >>>> // pr80776-1.c > >>>> int somerandom (void); > >>>> void > >>>> Foo (void) > >>>> { > >>>> int i = somerandom (); > >>>> if (! (0 <= i)) > >>>> __builtin_unreachable (); > >>>> if (! (0 <= i && i <= 999999)) > >>>> __builtin_unreachable (); > >>>> sprintf (number, "%d", i); > >>>> } > >>>> > >>>> This means that by the time the -Wformat-overflow warning runs, the > >>>> above sprintf has been left unguarded, and a bogus warning is issued. > >>>> > >>>> Currently the above test does not warn, but that's because of an > >>>> oversight in export_global_ranges(). This function is disregarding > >>>> known global ranges (SSA_NAME_RANGE_INFO and SSA_NAME_PTR_INFO) and only > >>>> setting ranges the ranger knows about. > >>>> > >>>> For the above test the IL is: > >>>> > >>>> <bb 2> : > >>>> i_4 = somerandom (); > >>>> if (i_4 < 0) > >>>> goto <bb 3>; [INV] > >>>> else > >>>> goto <bb 4>; [INV] > >>>> > >>>> <bb 3> : > >>>> __builtin_unreachable (); > >>>> > >>>> <bb 4> : > >>>> i.0_1 = (unsigned int) i_4; > >>>> if (i.0_1 > 999999) > >>>> goto <bb 5>; [INV] > >>>> else > >>>> goto <bb 6>; [INV] > >>>> > >>>> <bb 5> : > >>>> __builtin_unreachable (); > >>>> > >>>> <bb 6> : > >>>> _7 = __builtin___sprintf_chk (&number, 1, 7, "%d", i_4); > >>>> > >>>> > >>>> Legacy evrp has determined that the range for i_4 is [0,MAX] per my > >>>> analysis above, but ranger has no known range for i_4 at the definition > >>>> site. So at export_global_ranges time, ranger leaves the [0,MAX] alone. > >>>> > >>>> OTOH, evrp sets the global range at the definition for i.0_1 to > >>>> [0,999999] per the same unreachable feature. However, ranger has > >>>> correctly determined that the range for i.0_1 at the definition is > >>>> [0,MAX], which it then proceeds to export. Since the current > >>>> export_global_ranges (mistakenly) does not take into account previous > >>>> global ranges, the ranges in the global tables end up like this: > >>>> > >>>> i_4: [0, MAX] > >>>> i.0_1: [0, MAX] > >>>> > >>>> This causes the first unreachable block to be removed in VRP1, but the > >>>> second one to remain. Later VRP can determine that i_4 in the sprintf > >>>> call is [0,999999], and no warning is issued. > >>>> > >>>> But... the missing bogus warning is due to current export_global_ranges > >>>> ignoring SSA_NAME_RANGE_INFO and friends, something which I'd like to > >>>> fix. However, fixing this, gets us back to: > >>>> > >>>> i_4: [0, MAX] > >>>> i.0_1: [0, 999999] > >>>> > >>>> Which means, we'll be back to removing the unreachable blocks and > >>>> issuing a warning in pr80776-1.c (like we have been since the beginning > >>>> of time). > >>>> > >>>> The attached patch fixes export_global_ranges to the expected behavior, > >>>> and adds the previous XFAIL to pr80776-1.c, while documenting why this > >>>> warning is issued in the first place. > >>>> > >>>> Once legacy evrp is removed, this won't be an issue, as ranges in the IL > >>>> will tell the truth. However, this will mean that we will no longer > >>>> remove the first __builtin_unreachable combo. But ISTM, that would be > >>>> correct behavior ??. > >>>> > >>>> BTW, in addition to this patch we could explore removing the > >>>> assert_unreachable_fallthru_edge_p() use in the evrp_analyzer, since it > >>>> is no longer needed to get the warnings in the testcases in the original > >>>> PR correctly (gcc.dg/pr80776-[12].c). > >>> But the whole point of all this singing and dancing is not to make > >>> warnings but to be able to implement assert (); or assume (); that > >>> will result in no code but optimization based on the assumption. > >>> > >>> That means that all the checks guarding __builtin_unreachable () > >>> should be removed at the GIMPLE level - just not too early > >>> to preserve range info on the variables participating in the > >>> guarding condition. > >>> > >>> So yes, it sounds fragile but instead it's carefully architected. Heh. > >>> > >>> In particular it is designed so that early optimization leaves those > >>> unreachable () around (for later LTO consumption and inlining, etc. > >>> to be able to re-create the ranges) whilst VRP1 / DOM will end up > >>> eliminating them. I think we have testcases that verify said behavior, > >>> namely optimize out range checks based on the assertions - maybe missed > >>> the case where this only happens after inlining (important for your friendly > >>> C++ abstraction hell), and the unreachable()s gone. > >>> > >>> Please make sure to not break that. > >> Let me see if I understand... we want to leave builtin_unreachable > >> around until a certain point in compilation, and then remove them? > >> > >> It seems to me that either > >> > >> A) a builtin_unreachable () provides useful information,( ie, > >> information that isn't otherwise obvious, and would therefore stay in > >> the IL and not be eliminated by the various optimizations until it is.. > >> ). OR > >> > >> B )its telling us something is we can already figure out, in which > >> case we will naturally eliminate the branches leading to it, and then it > >> goes away on its own. > >> > >> By that standard, any builtin_unreachable that makes it late into the > >> optimization cycle is useful... So can't we just leave those until > >> whatever point it is we decide the information they provide is no longer > >> needed, and then simply drop them? Rewrite any branch to an unreachable > >> so that its truly unreachable, and then the next cfg cleanup makes them > >> all go away? That could be part of a late/final VRP or a pass of its own. > >> > >> This whole checking to see if they are there seems fragile, because it > >> doesn't tell us whether they are useful or not.. > > It's a combination of A and B. It's A) until after IPA and after IPA the > > information is transitioned to range information on the SSA names > > which is then persistent (but it for example does not survive all > > IPA optimizations - definitely not LTO streaming for example). So > > we're transitioning from a if (a) __builtin_unreachable () representation > > of the useful information to representing it by on-the-side info > > (SSA_NAME_RANGE_INFO) > > on 'a'. > > > > That should work fine with ranger as well I think - now, what was fragile > > was that the way the if (a) __builtin_unreachable () IL was preserved > > was simply that there's a single EVRP pass before IPA only and the > > way it is (was) structured makes sure that once we reflect the IL on > > the range info of 'a' it is not used (in the same EVRP pass) to elide > > the condition and nothing does (did) that before VRP1 either. > > > > Richard. > > OK, lets see if I follow. The problem is that if we do eliminate the if > and __builtin_unreachable too early, LTO streaming is likely to/might > lose the information? and maybe some of the other IPA passes will not > maintain the ssa_name_range_info data and thus also lose the info. Yep. > So once IPA is done, we'd be free to do eliminate at will when they > aren't useful any morer? Yes, more like "their information is readily available elsewhere". > And if I continue to follow that logic, > then ranger shouldn't start with global information from the > SSA_NAME_RANGE_INFO until post-IPA... then its free to pick up that info > and eliminate anything it can. That sounds like one possible solution. > At least until IPA and LTO are 100% range propagators :-) so in theory, > we could have a flag for post-ipa that allows us to pick better > starting global ranges when they are available. we could wrap that up > with the enable_ranger() call.. checks to see what pass we're in and if > post-ipa enables global access? or is there such a query already available? There's cfun->after_inlining - note that with ranger what uses ranges and simplifies things is a bit muddy to me - we'd still need to make sure the info eventually reaches SSA_NAME_RANGE_INFO before it's deleted. > Andrew > > PS Ah, and now that I re-read, i think we're both saying the same thing? > :-) so it boils down to how do we check post-ipa. > > Is there any movement to making LTO maintain any range info it currently > loses? Maybe this is an opportunity :-) I know it maintains some, > because it was part of the reason we dont use globals now So historically inlining preserves almost none of the on-the-side data, but nowadays it transfers at least points-to and range-info. For LTO we simply do not stream that (one could do this in {output,input_ssa_names}) - I suppose because initially there wasn't any (there was no EVRP, first VRP was after IPA). But it's also that SSA_NAME_RANGE_INFO is prone to be "dropped" and thus re-computing things after final inlining and initial scalar cleanups after inlining tends to make it more readily available. Richard. >
On 6/7/21 9:45 AM, Richard Biener wrote: > On Mon, Jun 7, 2021 at 3:37 PM Andrew MacLeod <amacleod@redhat.com> wrote: >> On 6/7/21 3:25 AM, Richard Biener wrote: >>> On Wed, Jun 2, 2021 at 2:53 PM Andrew MacLeod <amacleod@redhat.com> wrote: >>>> On 6/2/21 7:52 AM, Richard Biener wrote: >>>>> On Wed, Jun 2, 2021 at 12:34 PM Aldy Hernandez via Gcc-patches >>>>> <gcc-patches@gcc.gnu.org> wrote: >>>>>> We've been having "issues" in our branch when exporting to the global >>>>>> space ranges that take into account previously known ranges >>>>>> (SSA_NAME_RANGE_INFO, etc). For the longest time we had the export >>>>>> feature turned off because it had the potential of removing >>>>>> __builtin_unreachable code early in the pipeline. This was causing one >>>>>> or two tests to fail. >>>>>> >>>>>> I finally got fed up, and investigated why. >>>>>> >>>>>> Take the following code: >>>>>> >>>>>> i_4 = somerandom (); >>>>>> if (i_4 < 0) >>>>>> goto <bb 3>; [INV] >>>>>> else >>>>>> goto <bb 4>; [INV] >>>>>> >>>>>> <bb 3> : >>>>>> __builtin_unreachable (); >>>>>> >>>>>> <bb 4> : >>>>>> >>>>>> It turns out that both legacy evrp and VRP have code that notices the >>>>>> above pattern and sets the *global* range for i_4 to [0,MAX]. That is, >>>>>> the range for i_4 is set, not at BB4, but at the definition site. See >>>>>> uses of assert_unreachable_fallthru_edge_p() for details. >>>>>> >>>>>> This global range causes subsequent passes (VRP1 in the testcase below), >>>>>> to remove the checks and the __builtin_unreachable code altogether. >>>>>> >>>>>> // pr80776-1.c >>>>>> int somerandom (void); >>>>>> void >>>>>> Foo (void) >>>>>> { >>>>>> int i = somerandom (); >>>>>> if (! (0 <= i)) >>>>>> __builtin_unreachable (); >>>>>> if (! (0 <= i && i <= 999999)) >>>>>> __builtin_unreachable (); >>>>>> sprintf (number, "%d", i); >>>>>> } >>>>>> >>>>>> This means that by the time the -Wformat-overflow warning runs, the >>>>>> above sprintf has been left unguarded, and a bogus warning is issued. >>>>>> >>>>>> Currently the above test does not warn, but that's because of an >>>>>> oversight in export_global_ranges(). This function is disregarding >>>>>> known global ranges (SSA_NAME_RANGE_INFO and SSA_NAME_PTR_INFO) and only >>>>>> setting ranges the ranger knows about. >>>>>> >>>>>> For the above test the IL is: >>>>>> >>>>>> <bb 2> : >>>>>> i_4 = somerandom (); >>>>>> if (i_4 < 0) >>>>>> goto <bb 3>; [INV] >>>>>> else >>>>>> goto <bb 4>; [INV] >>>>>> >>>>>> <bb 3> : >>>>>> __builtin_unreachable (); >>>>>> >>>>>> <bb 4> : >>>>>> i.0_1 = (unsigned int) i_4; >>>>>> if (i.0_1 > 999999) >>>>>> goto <bb 5>; [INV] >>>>>> else >>>>>> goto <bb 6>; [INV] >>>>>> >>>>>> <bb 5> : >>>>>> __builtin_unreachable (); >>>>>> >>>>>> <bb 6> : >>>>>> _7 = __builtin___sprintf_chk (&number, 1, 7, "%d", i_4); >>>>>> >>>>>> >>>>>> Legacy evrp has determined that the range for i_4 is [0,MAX] per my >>>>>> analysis above, but ranger has no known range for i_4 at the definition >>>>>> site. So at export_global_ranges time, ranger leaves the [0,MAX] alone. >>>>>> >>>>>> OTOH, evrp sets the global range at the definition for i.0_1 to >>>>>> [0,999999] per the same unreachable feature. However, ranger has >>>>>> correctly determined that the range for i.0_1 at the definition is >>>>>> [0,MAX], which it then proceeds to export. Since the current >>>>>> export_global_ranges (mistakenly) does not take into account previous >>>>>> global ranges, the ranges in the global tables end up like this: >>>>>> >>>>>> i_4: [0, MAX] >>>>>> i.0_1: [0, MAX] >>>>>> >>>>>> This causes the first unreachable block to be removed in VRP1, but the >>>>>> second one to remain. Later VRP can determine that i_4 in the sprintf >>>>>> call is [0,999999], and no warning is issued. >>>>>> >>>>>> But... the missing bogus warning is due to current export_global_ranges >>>>>> ignoring SSA_NAME_RANGE_INFO and friends, something which I'd like to >>>>>> fix. However, fixing this, gets us back to: >>>>>> >>>>>> i_4: [0, MAX] >>>>>> i.0_1: [0, 999999] >>>>>> >>>>>> Which means, we'll be back to removing the unreachable blocks and >>>>>> issuing a warning in pr80776-1.c (like we have been since the beginning >>>>>> of time). >>>>>> >>>>>> The attached patch fixes export_global_ranges to the expected behavior, >>>>>> and adds the previous XFAIL to pr80776-1.c, while documenting why this >>>>>> warning is issued in the first place. >>>>>> >>>>>> Once legacy evrp is removed, this won't be an issue, as ranges in the IL >>>>>> will tell the truth. However, this will mean that we will no longer >>>>>> remove the first __builtin_unreachable combo. But ISTM, that would be >>>>>> correct behavior ??. >>>>>> >>>>>> BTW, in addition to this patch we could explore removing the >>>>>> assert_unreachable_fallthru_edge_p() use in the evrp_analyzer, since it >>>>>> is no longer needed to get the warnings in the testcases in the original >>>>>> PR correctly (gcc.dg/pr80776-[12].c). >>>>> But the whole point of all this singing and dancing is not to make >>>>> warnings but to be able to implement assert (); or assume (); that >>>>> will result in no code but optimization based on the assumption. >>>>> >>>>> That means that all the checks guarding __builtin_unreachable () >>>>> should be removed at the GIMPLE level - just not too early >>>>> to preserve range info on the variables participating in the >>>>> guarding condition. >>>>> >>>>> So yes, it sounds fragile but instead it's carefully architected. Heh. >>>>> >>>>> In particular it is designed so that early optimization leaves those >>>>> unreachable () around (for later LTO consumption and inlining, etc. >>>>> to be able to re-create the ranges) whilst VRP1 / DOM will end up >>>>> eliminating them. I think we have testcases that verify said behavior, >>>>> namely optimize out range checks based on the assertions - maybe missed >>>>> the case where this only happens after inlining (important for your friendly >>>>> C++ abstraction hell), and the unreachable()s gone. >>>>> >>>>> Please make sure to not break that. >>>> Let me see if I understand... we want to leave builtin_unreachable >>>> around until a certain point in compilation, and then remove them? >>>> >>>> It seems to me that either >>>> >>>> A) a builtin_unreachable () provides useful information,( ie, >>>> information that isn't otherwise obvious, and would therefore stay in >>>> the IL and not be eliminated by the various optimizations until it is.. >>>> ). OR >>>> >>>> B )its telling us something is we can already figure out, in which >>>> case we will naturally eliminate the branches leading to it, and then it >>>> goes away on its own. >>>> >>>> By that standard, any builtin_unreachable that makes it late into the >>>> optimization cycle is useful... So can't we just leave those until >>>> whatever point it is we decide the information they provide is no longer >>>> needed, and then simply drop them? Rewrite any branch to an unreachable >>>> so that its truly unreachable, and then the next cfg cleanup makes them >>>> all go away? That could be part of a late/final VRP or a pass of its own. >>>> >>>> This whole checking to see if they are there seems fragile, because it >>>> doesn't tell us whether they are useful or not.. >>> It's a combination of A and B. It's A) until after IPA and after IPA the >>> information is transitioned to range information on the SSA names >>> which is then persistent (but it for example does not survive all >>> IPA optimizations - definitely not LTO streaming for example). So >>> we're transitioning from a if (a) __builtin_unreachable () representation >>> of the useful information to representing it by on-the-side info >>> (SSA_NAME_RANGE_INFO) >>> on 'a'. >>> >>> That should work fine with ranger as well I think - now, what was fragile >>> was that the way the if (a) __builtin_unreachable () IL was preserved >>> was simply that there's a single EVRP pass before IPA only and the >>> way it is (was) structured makes sure that once we reflect the IL on >>> the range info of 'a' it is not used (in the same EVRP pass) to elide >>> the condition and nothing does (did) that before VRP1 either. >>> >>> Richard. >> OK, lets see if I follow. The problem is that if we do eliminate the if >> and __builtin_unreachable too early, LTO streaming is likely to/might >> lose the information? and maybe some of the other IPA passes will not >> maintain the ssa_name_range_info data and thus also lose the info. > Yep. > >> So once IPA is done, we'd be free to do eliminate at will when they >> aren't useful any morer? > Yes, more like "their information is readily available elsewhere". > >> And if I continue to follow that logic, >> then ranger shouldn't start with global information from the >> SSA_NAME_RANGE_INFO until post-IPA... then its free to pick up that info >> and eliminate anything it can. > That sounds like one possible solution. > >> At least until IPA and LTO are 100% range propagators :-) so in theory, >> we could have a flag for post-ipa that allows us to pick better >> starting global ranges when they are available. we could wrap that up >> with the enable_ranger() call.. checks to see what pass we're in and if >> post-ipa enables global access? or is there such a query already available? > There's cfun->after_inlining - note that with ranger what uses ranges and > simplifies things is a bit muddy to me - we'd still need to make sure the > info eventually reaches SSA_NAME_RANGE_INFO before it's deleted. > well, Its not much different than EVRP really. ranger wouldn't be deleting anything unless available info is sufficient enough to fold away the condition leading to the builtin_unreachable. Thats the issue we've mostly had with picking up global ranges.. if (x <= 3) __builtin_unreachable() We don't do anything with that condition unless we have a known range for x leading into the condition. If thats the first use of x, and IPA has run (or even EVRP once already), the global range for x is set to [4, +INF] in SSA_NAME_RANGE_INFO.. If ranger were to pick that up, it then folds away the condition, and also the unreachable. if we DON'T pick up global information, then we have no info leading to that conclusion, and the condition will stay. and the range of x will be [4, +INF] throughout the function, but it will not set the global range because that first use of x is VARYING. its only set to [4,+INF] on the false edge, and [-INF, 3] on the true edge. The false edge dominates all the other uses in the IL, so we DTRT throughout the function. I've given some thought to setting global ranges to also include a range that dominates all uses of the name (which is effectively what EVRP is doing by recognizing this sequence) . But ranger doesn't do that yet. So we would not naturally eliminate that condition as of right now, and we'll never set the global range to [4, +INF]. We may have to to eliminate the unreachable properly down the road... >> Andrew >> >> PS Ah, and now that I re-read, i think we're both saying the same thing? >> :-) so it boils down to how do we check post-ipa. >> >> Is there any movement to making LTO maintain any range info it currently >> loses? Maybe this is an opportunity :-) I know it maintains some, >> because it was part of the reason we dont use globals now > So historically inlining preserves almost none of the on-the-side data, but > nowadays it transfers at least points-to and range-info. For LTO we simply > do not stream that (one could do this in {output,input_ssa_names}) - I suppose > because initially there wasn't any (there was no EVRP, first VRP was after IPA). > > But it's also that SSA_NAME_RANGE_INFO is prone to be "dropped" > and thus re-computing things after final inlining and initial scalar cleanups > after inlining tends to make it more readily available. > > Richard. > > Yeah, I have no issues with the modality for now. Recomputing stuff from scratch works well enough, and it was just the early elimination of some builtin_unreachables we were trying to figure out what was right and was was wrong. Aldy, I think this means we can use global information in the get_global query for ranger if "cfun->after_inlining" is true, otherwise do what we currently do.
On Mon, Jun 7, 2021 at 4:32 PM Andrew MacLeod <amacleod@redhat.com> wrote: > Aldy, I think this means we can use global information in the get_global > query for ranger if "cfun->after_inlining" is true, otherwise do what we > currently do. Tested on x86-64 Linux. OK for trunk? Aldy
On 6/13/2021 10:02 AM, Aldy Hernandez via Gcc-patches wrote: > On Mon, Jun 7, 2021 at 4:32 PM Andrew MacLeod <amacleod@redhat.com> wrote: > >> Aldy, I think this means we can use global information in the get_global >> query for ranger if "cfun->after_inlining" is true, otherwise do what we >> currently do. > Tested on x86-64 Linux. > > OK for trunk? > > Aldy > > 0001-Pick-up-global-ranges-in-ranger-after-inlining.patch > > From 914810565183ad2cdac82ed5babd1f182346a728 Mon Sep 17 00:00:00 2001 > From: Aldy Hernandez <aldyh@redhat.com> > Date: Sun, 13 Jun 2021 16:20:33 +0200 > Subject: [PATCH] Pick up global ranges in ranger after inlining. > > Ranger was not picking up global ranges because doing so could remove > __builtin_unreachable calls too early to the detriment of LTO. However, > we can safely remove these calls after inlining. This patch removes the > restriction and allows ranger to pick up global ranges under these > circumstances. > > Tested on x86-64 Linux. > > gcc/ChangeLog: > > * value-query.cc (gimple_range_global): Call get_range_global > if called after inlining. OK jeff
From 36684dde843a4c9556b97bf030cabef8b9430aa4 Mon Sep 17 00:00:00 2001 From: Aldy Hernandez <aldyh@redhat.com> Date: Tue, 1 Jun 2021 17:48:30 +0200 Subject: [PATCH 2/2] Use known global ranges in export_global_ranges This patch modifies export_global_ranges to take into account current global ranges. It also handles enhances said function to export pointer global ranges as well. gcc/ChangeLog: * gimple-range.cc (gimple_ranger::export_global_ranges): Call update_global_range. * value-query.cc (update_global_range): New. * value-query.h (update_global_range): New. gcc/testsuite/ChangeLog: * gcc.dg/pr80776-1.c: XFAIL and document the reason why. --- gcc/gimple-range.cc | 26 ++++++++------------- gcc/testsuite/gcc.dg/pr80776-1.c | 12 +++++++++- gcc/value-query.cc | 39 ++++++++++++++++++++++++++++++++ gcc/value-query.h | 1 + 4 files changed, 61 insertions(+), 17 deletions(-) diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc index ed0a0c9702b..af426207092 100644 --- a/gcc/gimple-range.cc +++ b/gcc/gimple-range.cc @@ -1115,7 +1115,7 @@ gimple_ranger::range_of_stmt (irange &r, gimple *s, tree name) } // This routine will export whatever global ranges are known to GCC -// SSA_RANGE_NAME_INFO fields. +// SSA_RANGE_NAME_INFO and SSA_NAME_PTR_INFO fields. void gimple_ranger::export_global_ranges () @@ -1136,24 +1136,18 @@ gimple_ranger::export_global_ranges () && m_cache.get_global_range (r, name) && !r.varying_p()) { - // Make sure the new range is a subset of the old range. - int_range_max old_range; - old_range = gimple_range_global (name); - old_range.intersect (r); - /* Disable this while we fix tree-ssa/pr61743-2.c. */ - //gcc_checking_assert (old_range == r); - - // WTF? Can't write non-null pointer ranges?? stupid set_range_info! - if (!POINTER_TYPE_P (TREE_TYPE (name)) && !r.undefined_p ()) + bool updated = update_global_range (r, name); + + if (updated && dump_file) { value_range vr = r; - set_range_info (name, vr); - if (dump_file) + print_generic_expr (dump_file, name , TDF_SLIM); + fprintf (dump_file, " --> "); + vr.dump (dump_file); + fprintf (dump_file, "\n"); + int_range_max same = vr; + if (same != r) { - print_generic_expr (dump_file, name , TDF_SLIM); - fprintf (dump_file, " --> "); - vr.dump (dump_file); - fprintf (dump_file, "\n"); fprintf (dump_file, " irange : "); r.dump (dump_file); fprintf (dump_file, "\n"); diff --git a/gcc/testsuite/gcc.dg/pr80776-1.c b/gcc/testsuite/gcc.dg/pr80776-1.c index f3a120b6744..eca5e805ae2 100644 --- a/gcc/testsuite/gcc.dg/pr80776-1.c +++ b/gcc/testsuite/gcc.dg/pr80776-1.c @@ -17,5 +17,15 @@ Foo (void) __builtin_unreachable (); if (! (0 <= i && i <= 999999)) __builtin_unreachable (); - sprintf (number, "%d", i); /* { dg-bogus "writing" "" } */ + + /* Legacy evrp sets the range of i to [0, MAX] *before* the first conditional, + and to [0,999999] *before* the second conditional. This is because both + evrp and VRP use trickery to set global ranges when this particular use of + a __builtin_unreachable is in play (see uses of + assert_unreachable_fallthru_edge_p). + + Setting these ranges at the definition site, causes VRP to remove the + unreachable code altogether, leaving the following sprintf unguarded. This + causes the bogus warning below. */ + sprintf (number, "%d", i); /* { dg-bogus "writing" "" { xfail *-*-* } } */ } diff --git a/gcc/value-query.cc b/gcc/value-query.cc index f8b457d362c..070d706166e 100644 --- a/gcc/value-query.cc +++ b/gcc/value-query.cc @@ -224,6 +224,45 @@ get_ssa_name_ptr_info_nonnull (const_tree name) return !pi->pt.null; } +// Update the global range for NAME into the SSA_RANGE_NAME_INFO and +// SSA_NAME_PTR_INFO fields. Return TRUE if the range for NAME was +// updated. + +bool +update_global_range (irange &r, tree name) +{ + tree type = TREE_TYPE (name); + + if (r.undefined_p () || r.varying_p ()) + return false; + + if (INTEGRAL_TYPE_P (type)) + { + // If a global range already exists, incorporate it. + if (SSA_NAME_RANGE_INFO (name)) + { + value_range glob; + get_ssa_name_range_info (glob, name); + r.intersect (glob); + } + if (r.undefined_p ()) + return false; + + value_range vr = r; + set_range_info (name, vr); + return true; + } + else if (POINTER_TYPE_P (type)) + { + if (r.nonzero_p ()) + { + set_ptr_nonnull (name); + return true; + } + } + return false; +} + // Return the legacy global range for NAME if it has one, otherwise // return VARYING. diff --git a/gcc/value-query.h b/gcc/value-query.h index 97da6637747..d0512e40c5a 100644 --- a/gcc/value-query.h +++ b/gcc/value-query.h @@ -115,5 +115,6 @@ public: extern global_range_query global_ranges; extern value_range gimple_range_global (tree name); +extern bool update_global_range (irange &r, tree name); #endif // GCC_QUERY_H -- 2.31.1
We've been having "issues" in our branch when exporting to the global space ranges that take into account previously known ranges (SSA_NAME_RANGE_INFO, etc). For the longest time we had the export feature turned off because it had the potential of removing __builtin_unreachable code early in the pipeline. This was causing one or two tests to fail. I finally got fed up, and investigated why. Take the following code: i_4 = somerandom (); if (i_4 < 0) goto <bb 3>; [INV] else goto <bb 4>; [INV] <bb 3> : __builtin_unreachable (); <bb 4> : It turns out that both legacy evrp and VRP have code that notices the above pattern and sets the *global* range for i_4 to [0,MAX]. That is, the range for i_4 is set, not at BB4, but at the definition site. See uses of assert_unreachable_fallthru_edge_p() for details. This global range causes subsequent passes (VRP1 in the testcase below), to remove the checks and the __builtin_unreachable code altogether. // pr80776-1.c int somerandom (void); void Foo (void) { int i = somerandom (); if (! (0 <= i)) __builtin_unreachable (); if (! (0 <= i && i <= 999999)) __builtin_unreachable (); sprintf (number, "%d", i); } This means that by the time the -Wformat-overflow warning runs, the above sprintf has been left unguarded, and a bogus warning is issued. Currently the above test does not warn, but that's because of an oversight in export_global_ranges(). This function is disregarding known global ranges (SSA_NAME_RANGE_INFO and SSA_NAME_PTR_INFO) and only setting ranges the ranger knows about. For the above test the IL is: <bb 2> : i_4 = somerandom (); if (i_4 < 0) goto <bb 3>; [INV] else goto <bb 4>; [INV] <bb 3> : __builtin_unreachable (); <bb 4> : i.0_1 = (unsigned int) i_4; if (i.0_1 > 999999) goto <bb 5>; [INV] else goto <bb 6>; [INV] <bb 5> : __builtin_unreachable (); <bb 6> : _7 = __builtin___sprintf_chk (&number, 1, 7, "%d", i_4); Legacy evrp has determined that the range for i_4 is [0,MAX] per my analysis above, but ranger has no known range for i_4 at the definition site. So at export_global_ranges time, ranger leaves the [0,MAX] alone. OTOH, evrp sets the global range at the definition for i.0_1 to [0,999999] per the same unreachable feature. However, ranger has correctly determined that the range for i.0_1 at the definition is [0,MAX], which it then proceeds to export. Since the current export_global_ranges (mistakenly) does not take into account previous global ranges, the ranges in the global tables end up like this: i_4: [0, MAX] i.0_1: [0, MAX] This causes the first unreachable block to be removed in VRP1, but the second one to remain. Later VRP can determine that i_4 in the sprintf call is [0,999999], and no warning is issued. But... the missing bogus warning is due to current export_global_ranges ignoring SSA_NAME_RANGE_INFO and friends, something which I'd like to fix. However, fixing this, gets us back to: i_4: [0, MAX] i.0_1: [0, 999999] Which means, we'll be back to removing the unreachable blocks and issuing a warning in pr80776-1.c (like we have been since the beginning of time). The attached patch fixes export_global_ranges to the expected behavior, and adds the previous XFAIL to pr80776-1.c, while documenting why this warning is issued in the first place. Once legacy evrp is removed, this won't be an issue, as ranges in the IL will tell the truth. However, this will mean that we will no longer remove the first __builtin_unreachable combo. But ISTM, that would be correct behavior ??. BTW, in addition to this patch we could explore removing the assert_unreachable_fallthru_edge_p() use in the evrp_analyzer, since it is no longer needed to get the warnings in the testcases in the original PR correctly (gcc.dg/pr80776-[12].c). Tested on x86-64 Linux. OK? Aldy