Message ID | HE1PR0801MB17558AE1835B0D1AC56A54E6E7010@HE1PR0801MB1755.eurprd08.prod.outlook.com |
---|---|
State | New |
Headers | show |
On 07/29/2016 09:35 AM, Bin Cheng wrote: > Hi, > This is prerequisite patch for fixing PR34114 which reveals a weakness of GCC in analyzing niter for loop with NE_EXPR exit condition. For such loops, we quite often need to check if delta (final - start) of loop range is multiple of IV's step. This patch proves multiple_of_p (top, bottom) for more cases: > 1) Handle (X + 4294967293) as (X - 3) if the expression is of unsigned int type. At the moment it's not recognized because (4294967293 % 3 != 0) > 2) Handle top var if it's defined as: > top = (X & ~(bottom - 1) ; bottom is power of 2 > 3) Handle top var if it's defined as: > Y = X % bottom > top = X - Y > > Bootstrap and test on x86_64 and AArch64 along with next patch. Is it OK? > > Thanks, > bin > > 2016-07-27 Bin Cheng <bin.cheng@arm.com> > > * fold-const.c (multiple_of_p): Improve MULT_EXPR, PLUS_EXPR, > PLUS_EXPR case. Handle SSA_NAME case. > OK. Note that it would seem that this is an ideal kind of behaviorial change to test in the new unit testing framework. See the code inside the #if CHECKING_P at the bottom of fold-const.c. Essentially you can build up the appropriate tree nodes and pass them to multiple_of_p, then test the result -- without having to find/create C code that will trigger your code. I'm not requiring it for this change, but I might start for this kind of change in the future :-) In the mean time, consider adding the tests, you may find that they're a great way to verify behavior of these low level folders and similar routines. Jeff
On Fri, Jul 29, 2016 at 4:50 PM, Jeff Law <law@redhat.com> wrote: > On 07/29/2016 09:35 AM, Bin Cheng wrote: >> >> Hi, >> This is prerequisite patch for fixing PR34114 which reveals a weakness of >> GCC in analyzing niter for loop with NE_EXPR exit condition. For such >> loops, we quite often need to check if delta (final - start) of loop range >> is multiple of IV's step. This patch proves multiple_of_p (top, bottom) for >> more cases: >> 1) Handle (X + 4294967293) as (X - 3) if the expression is of unsigned >> int type. At the moment it's not recognized because (4294967293 % 3 != 0) >> 2) Handle top var if it's defined as: >> top = (X & ~(bottom - 1) ; bottom is power of 2 >> 3) Handle top var if it's defined as: >> Y = X % bottom >> top = X - Y >> >> Bootstrap and test on x86_64 and AArch64 along with next patch. Is it OK? >> >> Thanks, >> bin >> >> 2016-07-27 Bin Cheng <bin.cheng@arm.com> >> >> * fold-const.c (multiple_of_p): Improve MULT_EXPR, PLUS_EXPR, >> PLUS_EXPR case. Handle SSA_NAME case. >> > OK. > > Note that it would seem that this is an ideal kind of behaviorial change to > test in the new unit testing framework. See the code inside the #if > CHECKING_P at the bottom of fold-const.c. > > Essentially you can build up the appropriate tree nodes and pass them to > multiple_of_p, then test the result -- without having to find/create C code > that will trigger your code. > > I'm not requiring it for this change, but I might start for this kind of > change in the future :-) In the mean time, consider adding the tests, you > may find that they're a great way to verify behavior of these low level > folders and similar routines. Hi Jeff, Thanks very much for pointing me to this, I will study it and try to add test for this patch. Thanks, bin > > Jeff
diff --git a/gcc/fold-const.c b/gcc/fold-const.c index c5d9a79..c6c2bff 100644 --- a/gcc/fold-const.c +++ b/gcc/fold-const.c @@ -12538,6 +12538,9 @@ fold_build_call_array_initializer_loc (location_t loc, tree type, tree fn, int multiple_of_p (tree type, const_tree top, const_tree bottom) { + gimple *stmt; + tree t1, op1, op2; + if (operand_equal_p (top, bottom, 0)) return 1; @@ -12554,19 +12557,31 @@ multiple_of_p (tree type, const_tree top, const_tree bottom) /* FALLTHRU */ case MULT_EXPR: - return (multiple_of_p (type, TREE_OPERAND (top, 0), bottom) - || multiple_of_p (type, TREE_OPERAND (top, 1), bottom)); + return (multiple_of_p (type, TREE_OPERAND (top, 1), bottom) + || multiple_of_p (type, TREE_OPERAND (top, 0), bottom)); - case PLUS_EXPR: case MINUS_EXPR: - return (multiple_of_p (type, TREE_OPERAND (top, 0), bottom) - && multiple_of_p (type, TREE_OPERAND (top, 1), bottom)); + /* It is impossible to prove if op0 - op1 is multiple of bottom + precisely, so be conservative here checking if both op0 and op1 + are multiple of bottom. Note we check the second operand first + since it's usually simpler. */ + return (multiple_of_p (type, TREE_OPERAND (top, 1), bottom) + && multiple_of_p (type, TREE_OPERAND (top, 0), bottom)); + + case PLUS_EXPR: + /* The same as MINUS_EXPR, but handle cases like op0 + 0xfffffffd + as op0 - 3 if the expression has unsigned type. For example, + (X / 3) + 0xfffffffd is multiple of 3, but 0xfffffffd is not. */ + op1 = TREE_OPERAND (top, 1); + if (TYPE_UNSIGNED (type) + && TREE_CODE (op1) == INTEGER_CST && tree_int_cst_sign_bit (op1)) + op1 = fold_build1 (NEGATE_EXPR, type, op1); + return (multiple_of_p (type, op1, bottom) + && multiple_of_p (type, TREE_OPERAND (top, 0), bottom)); case LSHIFT_EXPR: if (TREE_CODE (TREE_OPERAND (top, 1)) == INTEGER_CST) { - tree op1, t1; - op1 = TREE_OPERAND (top, 1); /* const_binop may not detect overflow correctly, so check for it explicitly here. */ @@ -12606,6 +12621,44 @@ multiple_of_p (tree type, const_tree top, const_tree bottom) return wi::multiple_of_p (wi::to_widest (top), wi::to_widest (bottom), SIGNED); + case SSA_NAME: + if (TREE_CODE (bottom) == INTEGER_CST + && (stmt = SSA_NAME_DEF_STMT (top)) != NULL + && gimple_code (stmt) == GIMPLE_ASSIGN) + { + enum tree_code code = gimple_assign_rhs_code (stmt); + + /* Check for special cases to see if top is defined as multiple + of bottom: + + top = (X & ~(bottom - 1) ; bottom is power of 2 + + or + + Y = X % bottom + top = X - Y. */ + if (code == BIT_AND_EXPR + && (op2 = gimple_assign_rhs2 (stmt)) != NULL_TREE + && TREE_CODE (op2) == INTEGER_CST + && integer_pow2p (bottom) + && wi::multiple_of_p (wi::to_widest (op2), + wi::to_widest (bottom), UNSIGNED)) + return 1; + + op1 = gimple_assign_rhs1 (stmt); + if (code == MINUS_EXPR + && (op2 = gimple_assign_rhs2 (stmt)) != NULL_TREE + && TREE_CODE (op2) == SSA_NAME + && (stmt = SSA_NAME_DEF_STMT (op2)) != NULL + && gimple_code (stmt) == GIMPLE_ASSIGN + && (code = gimple_assign_rhs_code (stmt)) == TRUNC_MOD_EXPR + && operand_equal_p (op1, gimple_assign_rhs1 (stmt), 0) + && operand_equal_p (bottom, gimple_assign_rhs2 (stmt), 0)) + return 1; + } + + /* .. fall through ... */ + default: return 0; }