https://gcc.gnu.org/bugzilla/show_bug.cgi?id=89713
Bug ID: 89713
Summary: Optimize away an empty loop whose finiteness can not
be analytically determined
Product: gcc
Version: unknown
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: tree-optimization
Assignee: unassigned at gcc dot gnu.org
Reporter: fxue at os dot amperecomputing.com
Target Milestone: ---
C++ stl container-based loop is very common, but its low representation looks
like irregular, not standard form of [index, step], there is no way to estimate
iteration, or even check whether it is finite or infinite only via static
analysis. Current gcc can not optimize away an empty stl loop as the following
(case in bug 89134,comment 6), although we know a vector/map must be a finite
set.
void f (std::map<int, int> m)
{
for (auto it = m.begin (); it != m.end (); ++it);
}
Gimple dump is:
<bb 2> [local count: 118111600]:
# VUSE <.MEM_2(D)>
_4 = MEM[(struct _Rb_tree_node_base * *)m_3(D) + 24B];
_11 = &MEM[(struct _Rb_tree *)m_3(D)]._M_impl.D.34825._M_header;
if (_4 != _11)
goto <bb 3>; [89.00%]
else
goto <bb 4>; [11.00%]
<bb 3> [local count: 955630224]:
# it_14 = PHI <_4(2), _7(3)>
# VUSE <.MEM_2(D)>
_7 = std::_Rb_tree_increment (it_14);
if (_7 != _11)
goto <bb 3>; [89.00%]
else
goto <bb 4>; [11.00%]
<bb 4> [local count: 118111601]:
The iteration variable is re-assigned by std::_Rb_tree_increment(), a pure
function, more than a simple add/dec instruction.
As mentioned in bug 82776, comment 8, we might assume it is a finite empty loop
covered by implementation suggestion of C++ spec.
"[intro.progress]
The implementation may assume that any thread will eventually do one of the
following:
(1.1) — terminate,
(1.2) — make a call to a library I/O function,
(1.3) — perform an access through a volatile glvalue, or
(1.4) — perform a synchronization operation or an atomic operation.
[ Note: This is intended to allow compiler transformations such as removal of
empty loops, even when termination cannot be proven. — end note ]"
We may do something on this. A rough thought is to introduce a flag(such as
-fno-infinite-loop, or whatever name) to tell gcc characteristic of being
compiled source, like -fstrict-aliasing. This flag is disabled by default,
enabled explicitly, and could be correlated with
-faggressive-loop-optimization. And invoke a dce optimization dedicated to
this, late in gcc passes, in hope of not impacting true infinite loop.
