| Message ID | 524B5353.1000509@arm.com |
|---|---|
| State | New |
| Headers | show |
On Tue, 2013-10-01 at 23:57 +0100, Yufeng Zhang wrote: > On 10/01/13 20:55, Bill Schmidt wrote: > > > > > > On Tue, 2013-10-01 at 11:56 -0500, Bill Schmidt wrote: > >> OK, thanks. The problem that you've encountered is that you are > >> attempting to do something illegal. ;) (Bin's original patch is > >> actually to blame for that, as well as me for not catching it then.) > >> > >> As your new test shows, it is unsafe to do the transformation in > >> backtrace_base_for_ref when widening from an unsigned type, because the > >> unsigned type has wrap semantics by default. (The actual test must be > >> done on TYPE_OVERFLOW_WRAPS since this wrap semantics can be added or > >> removed by compile option -- see the comments with legal_cast_p and > >> legal_cast_p_1 later in the module.) > >> > >> You cannot in general prove that the transformation is allowable for a > >> specific constant, because you don't know that what you're adding it to > >> won't cause an overflow that's handled incorrectly. > >> > >> I believe the correct fix for the unsigned-overflow case is to fail > >> backtrace_base_for_ref if legal_cast_p (in_type, out_type) returns > >> false, where in_type is the type of the new *PBASE, and out_type is the > >> widening type that you're looking through. So you can't just > >> STRIP_NOPS, you have to check the cast for legitimacy for this > >> transformation. > >> > >> This does not explain why backtrace_base_for_ref does not find all the > >> opportunities on slsr-39.c. I don't immediately see what's preventing > >> that. Note that the transformation is legal in that case because you > >> are widening from a signed int to an unsigned int, which won't cause > >> problems. You guys need to dig deeper into why those opportunities are > >> missed when sizetype is larger than int. Let me know if you need help > >> figuring it out. > > > > Sorry, I had to leave before and wanted to get this response back to you > > in case I didn't get back soon. I've looked at this some more, and your > > general approach should work ok once you get the legal_cast_p check in > > place where you do the get_unwidened call now. Once you know you have a > > legal widening, you don't have to worry about the safe_to_multiply_p > > stuff. I.e., you don't need the last two chunks in the patch to > > backtrace_base_for_ref, and you don't need the unwidened_p variable. It > > should all fall out properly by just restricting your unwidening to > > legal casts. > > Many thanks for looking into the issue so promptly. I've updated the > patch; I have to use legal_cast_p_1 instead as the gimple node is no > longer available by then. > > Does the new patch look sane? Yes, much better. I'm happy with this approach. However, please restore the correct whitespace before the { at -786,7 +795,7. Thanks for fixing this up! Bill > > The regtest on aarch64 and bootstrapping on x86-64 are still running. > > Thanks, > Yufeng > > > gcc/ > > * gimple-ssa-strength-reduction.c (legal_cast_p_1): Forward > declaration. > (backtrace_base_for_ref): Call get_unwidened with 'base_in' if > 'base_in' represent a conversion and legal_cast_p_1 holds; set > 'base_in' with the returned value from get_unwidened. > > gcc/testsuite/ > > * gcc.dg/tree-ssa/slsr-40.c: New test.
On Tue, 2013-10-01 at 20:21 -0500, Bill Schmidt wrote: > On Tue, 2013-10-01 at 23:57 +0100, Yufeng Zhang wrote: > > On 10/01/13 20:55, Bill Schmidt wrote: > > > > > > > > > On Tue, 2013-10-01 at 11:56 -0500, Bill Schmidt wrote: > > >> OK, thanks. The problem that you've encountered is that you are > > >> attempting to do something illegal. ;) (Bin's original patch is > > >> actually to blame for that, as well as me for not catching it then.) > > >> > > >> As your new test shows, it is unsafe to do the transformation in > > >> backtrace_base_for_ref when widening from an unsigned type, because the > > >> unsigned type has wrap semantics by default. (The actual test must be > > >> done on TYPE_OVERFLOW_WRAPS since this wrap semantics can be added or > > >> removed by compile option -- see the comments with legal_cast_p and > > >> legal_cast_p_1 later in the module.) > > >> > > >> You cannot in general prove that the transformation is allowable for a > > >> specific constant, because you don't know that what you're adding it to > > >> won't cause an overflow that's handled incorrectly. > > >> > > >> I believe the correct fix for the unsigned-overflow case is to fail > > >> backtrace_base_for_ref if legal_cast_p (in_type, out_type) returns > > >> false, where in_type is the type of the new *PBASE, and out_type is the > > >> widening type that you're looking through. So you can't just > > >> STRIP_NOPS, you have to check the cast for legitimacy for this > > >> transformation. > > >> > > >> This does not explain why backtrace_base_for_ref does not find all the > > >> opportunities on slsr-39.c. I don't immediately see what's preventing > > >> that. Note that the transformation is legal in that case because you > > >> are widening from a signed int to an unsigned int, which won't cause > > >> problems. You guys need to dig deeper into why those opportunities are > > >> missed when sizetype is larger than int. Let me know if you need help > > >> figuring it out. > > > > > > Sorry, I had to leave before and wanted to get this response back to you > > > in case I didn't get back soon. I've looked at this some more, and your > > > general approach should work ok once you get the legal_cast_p check in > > > place where you do the get_unwidened call now. Once you know you have a > > > legal widening, you don't have to worry about the safe_to_multiply_p > > > stuff. I.e., you don't need the last two chunks in the patch to > > > backtrace_base_for_ref, and you don't need the unwidened_p variable. It > > > should all fall out properly by just restricting your unwidening to > > > legal casts. > > > > Many thanks for looking into the issue so promptly. I've updated the > > patch; I have to use legal_cast_p_1 instead as the gimple node is no > > longer available by then. > > > > Does the new patch look sane? > > Yes, much better. I'm happy with this approach. However, please > restore the correct whitespace before the { at -786,7 +795,7. > > Thanks for fixing this up! > > Bill (Just a reminder that I can't approve your patch; you need a maintainer for that. But it looks good to me.) Sometime when I get a moment I'm probably going to change this to handle the casting when the candidates are added to the table. I think we should look through the casts and distribute the multiply at that time. But for now what you have here is good. Thanks, Bill > > > > > The regtest on aarch64 and bootstrapping on x86-64 are still running. > > > > Thanks, > > Yufeng > > > > > > gcc/ > > > > * gimple-ssa-strength-reduction.c (legal_cast_p_1): Forward > > declaration. > > (backtrace_base_for_ref): Call get_unwidened with 'base_in' if > > 'base_in' represent a conversion and legal_cast_p_1 holds; set > > 'base_in' with the returned value from get_unwidened. > > > > gcc/testsuite/ > > > > * gcc.dg/tree-ssa/slsr-40.c: New test. >
On 10/02/13 02:21, Bill Schmidt wrote: > On Tue, 2013-10-01 at 23:57 +0100, Yufeng Zhang wrote: >> On 10/01/13 20:55, Bill Schmidt wrote: >>> >>> >>> On Tue, 2013-10-01 at 11:56 -0500, Bill Schmidt wrote: >>>> OK, thanks. The problem that you've encountered is that you are >>>> attempting to do something illegal. ;) (Bin's original patch is >>>> actually to blame for that, as well as me for not catching it then.) >>>> >>>> As your new test shows, it is unsafe to do the transformation in >>>> backtrace_base_for_ref when widening from an unsigned type, because the >>>> unsigned type has wrap semantics by default. (The actual test must be >>>> done on TYPE_OVERFLOW_WRAPS since this wrap semantics can be added or >>>> removed by compile option -- see the comments with legal_cast_p and >>>> legal_cast_p_1 later in the module.) >>>> >>>> You cannot in general prove that the transformation is allowable for a >>>> specific constant, because you don't know that what you're adding it to >>>> won't cause an overflow that's handled incorrectly. >>>> >>>> I believe the correct fix for the unsigned-overflow case is to fail >>>> backtrace_base_for_ref if legal_cast_p (in_type, out_type) returns >>>> false, where in_type is the type of the new *PBASE, and out_type is the >>>> widening type that you're looking through. So you can't just >>>> STRIP_NOPS, you have to check the cast for legitimacy for this >>>> transformation. >>>> >>>> This does not explain why backtrace_base_for_ref does not find all the >>>> opportunities on slsr-39.c. I don't immediately see what's preventing >>>> that. Note that the transformation is legal in that case because you >>>> are widening from a signed int to an unsigned int, which won't cause >>>> problems. You guys need to dig deeper into why those opportunities are >>>> missed when sizetype is larger than int. Let me know if you need help >>>> figuring it out. >>> >>> Sorry, I had to leave before and wanted to get this response back to you >>> in case I didn't get back soon. I've looked at this some more, and your >>> general approach should work ok once you get the legal_cast_p check in >>> place where you do the get_unwidened call now. Once you know you have a >>> legal widening, you don't have to worry about the safe_to_multiply_p >>> stuff. I.e., you don't need the last two chunks in the patch to >>> backtrace_base_for_ref, and you don't need the unwidened_p variable. It >>> should all fall out properly by just restricting your unwidening to >>> legal casts. >> >> Many thanks for looking into the issue so promptly. I've updated the >> patch; I have to use legal_cast_p_1 instead as the gimple node is no >> longer available by then. >> >> Does the new patch look sane? > > Yes, much better. I'm happy with this approach. Great! The regtest and bootstrap all passed so I've committed the patch. > However, please > restore the correct whitespace before the { at -786,7 +795,7. This is actually a correction to the whitespace. I've split the patch and committed it separately. Thanks again for helping out! Regards, Yufeng
On 10/02/13 13:40, Bill Schmidt wrote: > On Tue, 2013-10-01 at 20:21 -0500, Bill Schmidt wrote: >> On Tue, 2013-10-01 at 23:57 +0100, Yufeng Zhang wrote: >>> On 10/01/13 20:55, Bill Schmidt wrote: >>>> >>>> >>>> On Tue, 2013-10-01 at 11:56 -0500, Bill Schmidt wrote: >>>>> OK, thanks. The problem that you've encountered is that you are >>>>> attempting to do something illegal. ;) (Bin's original patch is >>>>> actually to blame for that, as well as me for not catching it then.) >>>>> >>>>> As your new test shows, it is unsafe to do the transformation in >>>>> backtrace_base_for_ref when widening from an unsigned type, because the >>>>> unsigned type has wrap semantics by default. (The actual test must be >>>>> done on TYPE_OVERFLOW_WRAPS since this wrap semantics can be added or >>>>> removed by compile option -- see the comments with legal_cast_p and >>>>> legal_cast_p_1 later in the module.) >>>>> >>>>> You cannot in general prove that the transformation is allowable for a >>>>> specific constant, because you don't know that what you're adding it to >>>>> won't cause an overflow that's handled incorrectly. >>>>> >>>>> I believe the correct fix for the unsigned-overflow case is to fail >>>>> backtrace_base_for_ref if legal_cast_p (in_type, out_type) returns >>>>> false, where in_type is the type of the new *PBASE, and out_type is the >>>>> widening type that you're looking through. So you can't just >>>>> STRIP_NOPS, you have to check the cast for legitimacy for this >>>>> transformation. >>>>> >>>>> This does not explain why backtrace_base_for_ref does not find all the >>>>> opportunities on slsr-39.c. I don't immediately see what's preventing >>>>> that. Note that the transformation is legal in that case because you >>>>> are widening from a signed int to an unsigned int, which won't cause >>>>> problems. You guys need to dig deeper into why those opportunities are >>>>> missed when sizetype is larger than int. Let me know if you need help >>>>> figuring it out. >>>> >>>> Sorry, I had to leave before and wanted to get this response back to you >>>> in case I didn't get back soon. I've looked at this some more, and your >>>> general approach should work ok once you get the legal_cast_p check in >>>> place where you do the get_unwidened call now. Once you know you have a >>>> legal widening, you don't have to worry about the safe_to_multiply_p >>>> stuff. I.e., you don't need the last two chunks in the patch to >>>> backtrace_base_for_ref, and you don't need the unwidened_p variable. It >>>> should all fall out properly by just restricting your unwidening to >>>> legal casts. >>> >>> Many thanks for looking into the issue so promptly. I've updated the >>> patch; I have to use legal_cast_p_1 instead as the gimple node is no >>> longer available by then. >>> >>> Does the new patch look sane? >> >> Yes, much better. I'm happy with this approach. However, please >> restore the correct whitespace before the { at -786,7 +795,7. >> >> Thanks for fixing this up! >> >> Bill > > (Just a reminder that I can't approve your patch; you need a maintainer > for that. But it looks good to me.) Oops. I didn't realise that and I just saw your email. :( Sorry... Can Richard please do a retro-approval? > Sometime when I get a moment I'm probably going to change this to handle > the casting when the candidates are added to the table. Indeed, that will be a cleaner approach. Thanks, Yufeng
On Wed, 2013-10-02 at 07:40 -0500, Bill Schmidt wrote: > On Tue, 2013-10-01 at 20:21 -0500, Bill Schmidt wrote: > > On Tue, 2013-10-01 at 23:57 +0100, Yufeng Zhang wrote: > > > On 10/01/13 20:55, Bill Schmidt wrote: > > > > > > > > > > > > On Tue, 2013-10-01 at 11:56 -0500, Bill Schmidt wrote: > > > >> OK, thanks. The problem that you've encountered is that you are > > > >> attempting to do something illegal. ;) (Bin's original patch is > > > >> actually to blame for that, as well as me for not catching it then.) > > > >> > > > >> As your new test shows, it is unsafe to do the transformation in > > > >> backtrace_base_for_ref when widening from an unsigned type, because the > > > >> unsigned type has wrap semantics by default. (The actual test must be > > > >> done on TYPE_OVERFLOW_WRAPS since this wrap semantics can be added or > > > >> removed by compile option -- see the comments with legal_cast_p and > > > >> legal_cast_p_1 later in the module.) > > > >> > > > >> You cannot in general prove that the transformation is allowable for a > > > >> specific constant, because you don't know that what you're adding it to > > > >> won't cause an overflow that's handled incorrectly. > > > >> > > > >> I believe the correct fix for the unsigned-overflow case is to fail > > > >> backtrace_base_for_ref if legal_cast_p (in_type, out_type) returns > > > >> false, where in_type is the type of the new *PBASE, and out_type is the > > > >> widening type that you're looking through. So you can't just > > > >> STRIP_NOPS, you have to check the cast for legitimacy for this > > > >> transformation. > > > >> > > > >> This does not explain why backtrace_base_for_ref does not find all the > > > >> opportunities on slsr-39.c. I don't immediately see what's preventing > > > >> that. Note that the transformation is legal in that case because you > > > >> are widening from a signed int to an unsigned int, which won't cause > > > >> problems. You guys need to dig deeper into why those opportunities are > > > >> missed when sizetype is larger than int. Let me know if you need help > > > >> figuring it out. > > > > > > > > Sorry, I had to leave before and wanted to get this response back to you > > > > in case I didn't get back soon. I've looked at this some more, and your > > > > general approach should work ok once you get the legal_cast_p check in > > > > place where you do the get_unwidened call now. Once you know you have a > > > > legal widening, you don't have to worry about the safe_to_multiply_p > > > > stuff. I.e., you don't need the last two chunks in the patch to > > > > backtrace_base_for_ref, and you don't need the unwidened_p variable. It > > > > should all fall out properly by just restricting your unwidening to > > > > legal casts. > > > > > > Many thanks for looking into the issue so promptly. I've updated the > > > patch; I have to use legal_cast_p_1 instead as the gimple node is no > > > longer available by then. > > > > > > Does the new patch look sane? > > > > Yes, much better. I'm happy with this approach. However, please > > restore the correct whitespace before the { at -786,7 +795,7. > > > > Thanks for fixing this up! > > > > Bill > > (Just a reminder that I can't approve your patch; you need a maintainer > for that. But it looks good to me.) > > Sometime when I get a moment I'm probably going to change this to handle > the casting when the candidates are added to the table. I think we > should look through the casts and distribute the multiply at that time. > But for now what you have here is good. FYI, I looked at this a little more this afternoon, and convinced myself that your approach is the right one. This is already representing everything pertinent in the candidate table. Thanks again for adding these extensions. Bill > > Thanks, > Bill > > > > > > > > > The regtest on aarch64 and bootstrapping on x86-64 are still running. > > > > > > Thanks, > > > Yufeng > > > > > > > > > gcc/ > > > > > > * gimple-ssa-strength-reduction.c (legal_cast_p_1): Forward > > > declaration. > > > (backtrace_base_for_ref): Call get_unwidened with 'base_in' if > > > 'base_in' represent a conversion and legal_cast_p_1 holds; set > > > 'base_in' with the returned value from get_unwidened. > > > > > > gcc/testsuite/ > > > > > > * gcc.dg/tree-ssa/slsr-40.c: New test. > >
diff --git a/gcc/gimple-ssa-strength-reduction.c b/gcc/gimple-ssa-strength-reduction.c index 139a4a1..a558f34 100644 --- a/gcc/gimple-ssa-strength-reduction.c +++ b/gcc/gimple-ssa-strength-reduction.c @@ -379,6 +379,7 @@ static bool address_arithmetic_p; /* Forward function declarations. */ static slsr_cand_t base_cand_from_table (tree); static tree introduce_cast_before_cand (slsr_cand_t, tree, tree); +static bool legal_cast_p_1 (tree, tree); /* Produce a pointer to the IDX'th candidate in the candidate vector. */ @@ -768,6 +769,14 @@ backtrace_base_for_ref (tree *pbase) slsr_cand_t base_cand; STRIP_NOPS (base_in); + + /* Strip off widening conversion(s) to handle cases where + e.g. 'B' is widened from an 'int' in order to calculate + a 64-bit address. */ + if (CONVERT_EXPR_P (base_in) + && legal_cast_p_1 (base_in, TREE_OPERAND (base_in, 0))) + base_in = get_unwidened (base_in, NULL_TREE); + if (TREE_CODE (base_in) != SSA_NAME) return tree_to_double_int (integer_zero_node); @@ -786,7 +795,7 @@ backtrace_base_for_ref (tree *pbase) else if (base_cand->kind == CAND_ADD && TREE_CODE (base_cand->stride) == INTEGER_CST && integer_onep (base_cand->stride)) - { + { /* X = B + (i * S), S is integer one. */ *pbase = base_cand->base_expr; return base_cand->index; diff --git a/gcc/testsuite/gcc.dg/tree-ssa/slsr-40.c b/gcc/testsuite/gcc.dg/tree-ssa/slsr-40.c new file mode 100644 index 0000000..72726a3 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/slsr-40.c @@ -0,0 +1,27 @@ +/* Verify straight-line strength reduction for array + subscripting. + + elems[n-1] is reduced to elems + n * 4 + 0xffffffff * 4, only when + pointers are of the same size as that of int (assuming 4 bytes). */ + +/* { dg-do run } */ +/* { dg-options "-O2" } */ + +struct data +{ + unsigned long elms[1]; +} gData; + +void __attribute__((noinline)) +foo (struct data *dst, unsigned int n) +{ + dst->elms[n - 1] &= 1; +} + +int +main () +{ + foo (&gData, 1); + return 0; +} +