[Bug tree-optimization/89134] A missing optimization opportunity for a simple branch in loop
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=89134 Andrew Pinski changed: What|Removed |Added Resolution|--- |FIXED Status|UNCONFIRMED |RESOLVED Target Milestone|--- |10.0 --- Comment #15 from Andrew Pinski --- Fixed.
[Bug tree-optimization/89134] A missing optimization opportunity for a simple branch in loop
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=89134 --- Comment #14 from fxue at gcc dot gnu.org --- Author: fxue Date: Thu Nov 7 15:43:01 2019 New Revision: 277923 URL: https://gcc.gnu.org/viewcvs?rev=277923=gcc=rev Log: Loop split on semi-invariant conditional statement 2019-11-07 Feng Xue PR tree-optimization/89134 * doc/invoke.texi (min-loop-cond-split-prob): Document new --params. * params.def: Add min-loop-cond-split-prob. * tree-ssa-loop-split.c (split_loop): Remove niter parameter, move some outside checks on loop into the function. (split_info): New class. (find_vdef_in_loop, get_control_equiv_head_block): New functions. (find_control_dep_blocks, vuse_semi_invariant_p): Likewise. (ssa_semi_invariant_p, loop_iter_phi_semi_invariant_p): Likewise. (control_dep_semi_invariant_p, stmt_semi_invariant_p_1): Likewise. (stmt_semi_invariant_p, branch_removable_p): Likewise. (get_cond_invariant_branch, compute_added_num_insns): Likewise. (get_cond_branch_to_split_loop, do_split_loop_on_cond): Likewise. (split_loop_on_cond): Likewise. (tree_ssa_split_loops): Add loop split on conditional statement. 2019-11-07 Feng Xue PR tree-optimization/89134 * gcc.dg/tree-ssa/loop-cond-split-1.c: New test. * g++.dg/tree-ssa/loop-cond-split-1.C: New test. * gcc.dg/torture/pr55107.c: Add -fno-split-loops. Added: trunk/gcc/testsuite/g++.dg/tree-ssa/loop-cond-split-1.C trunk/gcc/testsuite/gcc.dg/tree-ssa/loop-cond-split-1.c Modified: trunk/gcc/ChangeLog trunk/gcc/doc/invoke.texi trunk/gcc/params.def trunk/gcc/testsuite/ChangeLog trunk/gcc/testsuite/gcc.dg/torture/pr55107.c trunk/gcc/tree-ssa-loop-split.c
[Bug tree-optimization/89134] A missing optimization opportunity for a simple branch in loop
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=89134 --- Comment #13 from Jiangning Liu --- Feng already sent out the 1st patch at https://gcc.gnu.org/ml/gcc-patches/2019-03/msg00541.html . But the 2nd one is related to https://gcc.gnu.org/bugzilla/show_bug.cgi?id=89713 .
[Bug tree-optimization/89134] A missing optimization opportunity for a simple branch in loop
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=89134 --- Comment #12 from joey.ye.cc at gmail dot com --- Feng, Have you made any progress on these problems? If advice is still needed, I would suggest you share more details about these problems, and people like Bin and Richi and Richard Sandiford may provide you some advice. Thanks, Joey On Sat, Feb 2, 2019 at 4:23 AM fxue at os dot amperecomputing.com wrote: > > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=89134 > > --- Comment #11 from Feng Xue --- > Actually, I am working on adding optimizations to enable this opportunity, > which can be discomposed to two sub-problems: breaking-loop transformation > mentioned above, and empty-loop elimination. I have worked out several > patches, > but for the second thing, since it seems to be more aggressive than gcc > currently implemented, I need advices and feedbacks from the community.
[Bug tree-optimization/89134] A missing optimization opportunity for a simple branch in loop
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=89134 --- Comment #11 from Feng Xue --- Actually, I am working on adding optimizations to enable this opportunity, which can be discomposed to two sub-problems: breaking-loop transformation mentioned above, and empty-loop elimination. I have worked out several patches, but for the second thing, since it seems to be more aggressive than gcc currently implemented, I need advices and feedbacks from the community.
[Bug tree-optimization/89134] A missing optimization opportunity for a simple branch in loop
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=89134 --- Comment #10 from Jiangning Liu --- (In reply to Martin Sebor from comment #9) > But since GCC emits infinite loops regardless of whether or not > they have any side-effects, whether inc() is pure or not may not matter. I think "for (; it != m.end (); ++it); /* get an empty loop */" is a finite loop.
[Bug tree-optimization/89134] A missing optimization opportunity for a simple branch in loop
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=89134 Martin Sebor changed: What|Removed |Added Status|NEW |UNCONFIRMED Ever confirmed|1 |0 --- Comment #9 from Martin Sebor --- Let me actually retract the confirmation. I acknowledged this for the pure attribute apparently not being taken into consideration when determining whether the loop terminates, on the basis of the minimum the standard requires. But since GCC emits infinite loops regardless of whether or not they have any side-effects, whether inc() is pure or not may not matter. Richard is the expert on loops so I should defer to him, especially since this request seems to be about more than just finite loops.
[Bug tree-optimization/89134] A missing optimization opportunity for a simple branch in loop
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=89134
--- Comment #8 from Feng Xue ---
My mistake, transformation should be:
void f (std::map m)
{
for (auto it = m.begin (); it != m.end (); ++it) {
if (b) {
b = do_something();
} else {
++it;
break;
}
}
for (; it != m.end (); ++it); /* get an empty loop */
}
(In reply to Feng Xue from comment #7)
> Even loop contains calls with side effects, but only in one condition branch
> path, we can still do some kind of optimization.
>
> Suppose a loop as:
>
> void f (std::map m)
> {
> for (auto it = m.begin (); it != m.end (); ++it) {
> if (b) {
> b = do_something();/* Has effect on b */
> } else {
>/* No effect on b */
> }
> }
> }
>
> We can transform it to:
>
> void f (std::map m)
> {
> for (auto it = m.begin (); it != m.end (); ++it) {
> if (b) {
> b = do_something();
> ++it;
> break;
> }
> }
>
> for (; it != m.end (); ++it); /* get an empty loop */
> }
>
> This code takes less computation, especially when 'b' is always evaluated to
> be false.
[Bug tree-optimization/89134] A missing optimization opportunity for a simple branch in loop
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=89134
Feng Xue changed:
What|Removed |Added
CC||innat_xue at hotmail dot com
--- Comment #7 from Feng Xue ---
Even loop contains calls with side effects, but only in one condition branch
path, we can still do some kind of optimization.
Suppose a loop as:
void f (std::map m)
{
for (auto it = m.begin (); it != m.end (); ++it) {
if (b) {
b = do_something();/* Has effect on b */
} else {
/* No effect on b */
}
}
}
We can transform it to:
void f (std::map m)
{
for (auto it = m.begin (); it != m.end (); ++it) {
if (b) {
b = do_something();
++it;
break;
}
}
for (; it != m.end (); ++it); /* get an empty loop */
}
This code takes less computation, especially when 'b' is always evaluated to be
false.
[Bug tree-optimization/89134] A missing optimization opportunity for a simple branch in loop
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=89134
Martin Sebor changed:
What|Removed |Added
Status|UNCONFIRMED |NEW
Last reconfirmed||2019-02-01
Ever confirmed|0 |1
--- Comment #6 from Martin Sebor ---
The optimized dump of the following function:
void f (std::map m)
{
for (auto it = m.begin (); it != m.end (); ++it);
}
shows the following loop:
[local count: 955630224]:
# it_14 = PHI <_4(2), _7(3)>
_7 = std::_Rb_tree_increment (it_14);
if (_7 != _11)
goto ; [89.00%]
else
goto ; [11.00%]
The _Rb_tree_increment() function that implements the iterator increment is
declared pure in libstdc++-v3/include/bits/stl_tree.h:
__attribute__ ((__pure__)) _Rb_tree_node_base*
_Rb_tree_increment(_Rb_tree_node_base* __x) throw ();
and defined in libstdc++-v3/src/c++98/tree.cc, so GCC should be able to make
use of the pure attribute to eliminate the loop since pure functions cannot
change the observable state of the program. (This works when
_Rb_tree_increment() is defined in the test case above so that GCC sees that
its definition does, in fact, meet the requirements of a pure function.)
So I can confirm that GCC doesn't eliminate the empty loop. Once the loop
contains calls to functions that aren't pure (like do_something() in comment
#0) the same optimization would no longer be valid.
[Bug tree-optimization/89134] A missing optimization opportunity for a simple branch in loop
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=89134
--- Comment #5 from Jiangning Liu ---
The loop below should be treated as a finite loop,
for (iter = booktable.begin(); iter!=booktable.end(); ++iter) {
...
}
so there is a chance to optimize away the empty loop, in which do_something
doesn't exist at all.
[Bug tree-optimization/89134] A missing optimization opportunity for a simple branch in loop
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=89134
Martin Sebor changed:
What|Removed |Added
CC||msebor at gcc dot gnu.org
--- Comment #4 from Martin Sebor ---
Right, the problem is that do_something() could do one of the things that the
standard says permit loops to iterate infinitely:
An iteration statement whose controlling expression is not a constant
expression, that performs no input/output operations, does not access volatile
objects, and performs no synchronization or atomic operations in its body,
controlling expression, or (in the case of for statement) its expression-3,
may be assumed by the implementation to terminate.
If do_something() were declared pure like inc() it couldn't do any of those
things either and GCC should be able to assume the loop terminates. It
doesn't, and in fact, it doesn't even in its absence. For example, GCC doesn't
think the following loop necessarily terminates either:
void test (int n)
{
for (int i = 0; i < n; i = inc (i));
}
Not even when inc() is declared const.
[Bug tree-optimization/89134] A missing optimization opportunity for a simple branch in loop
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=89134
David Malcolm changed:
What|Removed |Added
CC||dmalcolm at gcc dot gnu.org
--- Comment #3 from David Malcolm ---
"inc" may be pure, but "do_something" isn't, so I don't see how it's valid to
optimize away the loop.
Consider e.g. this implementation in another TU:
int call_count;
int do_something(void)
{
call_count++;
return 1;
}
...or somesuch.
(also "b" is global, so presumably there could be another thread touching it,
or observing the changes made by the loop)
[Bug tree-optimization/89134] A missing optimization opportunity for a simple branch in loop
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=89134
Jiangning Liu changed:
What|Removed |Added
Status|RESOLVED|UNCONFIRMED
Resolution|INVALID |---
--- Comment #2 from Jiangning Liu ---
The original case is only a simple example, and what if GCC can figure out it
is NOT an infinite loop? For example,
std::map BookTable;
BookTable::iterator iter;
BookTable booktable;
for (iter = booktable.begin(); iter!=booktable.end(); ++iter) {
if (b) {
b = do_something();
}
}
Then GCC should be able to figure out this loop is a finite loop due to using
standard C++ STL std::map. The cost of iterating std::map might be high, so
we'd better consider optimize away the empty loop.
[Bug tree-optimization/89134] A missing optimization opportunity for a simple branch in loop
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=89134 Richard Biener changed: What|Removed |Added Keywords||missed-optimization Status|UNCONFIRMED |RESOLVED Resolution|--- |INVALID --- Comment #1 from Richard Biener --- The issue is that GCC cannot prove finiteness of the loop since inc(i) could just return i itself. So I can't see how this optimization would be correct. Note the loop isn't unswitched but only path-splitting exposes it. And cddce then rightfully complains: cannot prove finiteness of loop 2 Marking useful stmt: if (n_7(D) > i_10) cannot prove finiteness of loop 1 Marking useful stmt: if (n_7(D) > i_16)
