On 2021-06-08 18:13, Richard Biener wrote:
On Fri, 4 Jun 2021, Jiufu Guo wrote:
cut...
+ gcond *cond = as_a<gcond *> (last);
+ enum tree_code code = gimple_cond_code (cond);
+ if (!(code == NE_EXPR
+ || (code == EQ_EXPR && (e->flags & EDGE_TRUE_VALUE))))
The NE_EXPR check misses a corresponding && (e->flags &
EDGE_FALSE_VALUE)
check.
Thanks, check (e->flags & EDGE_FALSE_VALUE) would be safer.
+ continue;
+
+ /* Check if bound is invarant. */
+ tree idx = gimple_cond_lhs (cond);
+ tree bnd = gimple_cond_rhs (cond);
+ if (expr_invariant_in_loop_p (loop, idx))
+ std::swap (idx, bnd);
+ else if (!expr_invariant_in_loop_p (loop, bnd))
+ continue;
+
+ /* Only unsigned type conversion could cause wrap. */
+ tree type = TREE_TYPE (idx);
+ if (!INTEGRAL_TYPE_P (type) || TREE_CODE (idx) != SSA_NAME
+ || !TYPE_UNSIGNED (type))
+ continue;
+
+ /* Avoid to split if bound is MAX/MIN val. */
+ tree bound_type = TREE_TYPE (bnd);
+ if (TREE_CODE (bnd) == INTEGER_CST && INTEGRAL_TYPE_P
(bound_type)
+ && (tree_int_cst_equal (bnd, TYPE_MAX_VALUE (bound_type))
+ || tree_int_cst_equal (bnd, TYPE_MIN_VALUE (bound_type))))
+ continue;
Note you do not require 'bnd' to be constant and thus at runtime those
cases still need to be handled correctly.
Yes, bnd is not required to be constant. The above code is filtering
the case
where bnd is const max/min value of the type. So, the code could be
updated as:
if (tree_int_cst_equal (bnd, TYPE_MAX_VALUE (bound_type))
|| tree_int_cst_equal (bnd, TYPE_MIN_VALUE (bound_type)))
+ /* Check if there is possible wrap. */
+ class tree_niter_desc niter;
+ if (!number_of_iterations_exit (loop, e, &niter, false, false))
cut...
+
+ /* Change if (i != n) to LOOP1:if (i > n) and LOOP2:if (i < n) */
It now occurs to me that we nowhere check the evolution of IDX
(split_at_bb_p uses simple_iv for this for example). The transform
assumes that we will actually hit i == n and that i increments, but
while you check the control IV from number_of_iterations_exit
for NE_EXPR that does not guarantee a positive evolution.
If I do not correctly reply your question, please point out:
number_of_iterations_exit is similar with simple_iv to invoke
simple_iv_with_niters
which check the evolution, and number_of_iterations_exit check
number_of_iterations_cond
which check no_overflow more accurate, this is one reason I use this
function.
This transform assumes that the last run hits i==n.
Otherwise, the loop may run infinitely wrap after wrap.
For safe, if the step is 1 or -1, this assumption would be true. I
would add this check.
Thanks so much for pointing out I missed the negative step!
Your testcases do not include any negative step examples, but I guess
the conditions need to be swapped in this case?
I would add cases and code to support step 1/-1.
I think you also have to consider the order we split, say with
for (i = start; i != end; ++i)
{
push (i);
if (a[i] != b[i])
break;
}
push (i) calls need to be in the same order for all cases of
start < end, start == end and start > end (and also cover
runtime testcases with end == 0 or end == UINT_MAX, likewise
for start).
I add tests for the above cases. If missing sth, please point out,
thanks!
+ bool inv = expr_invariant_in_loop_p (loop, gimple_cond_lhs (gc));
+ enum tree_code up_code = inv ? LT_EXPR : GT_EXPR;
+ enum tree_code down_code = inv ? GT_EXPR : LT_EXPR;
cut....
Thanks again for the very helpful review!
BR,
Jiufu Guo.
