https://gcc.gnu.org/bugzilla/show_bug.cgi?id=119099
Bug ID: 119099
Summary: Compile-time hang in DCE
Product: gcc
Version: 15.0
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: rtl-optimization
Assignee: unassigned at gcc dot gnu.org
Reporter: alexey.merzlyakov at samsung dot com
Target Milestone: ---
Created attachment 60644
--> https://gcc.gnu.org/bugzilla/attachment.cgi?id=60644&action=edit
Reduced test-case
The following code c-reduced from csmith generated testcase, causes GCC to hang
at -O2 during the compile-time:
int a, b;
void func2(short);
void func1() {
while (1) {
int loc = 8;
while (1) {
func2(loc);
if (a)
loc = 3;
else if (b)
break;
loc |= a;
}
}
}
The hang appears on trunk and affects at least RISC-V 64/32, ARM 64/32,
powerpc64, MRISC32 targets.
Here is the example link on godbolt for RV64: https://godbolt.org/z/eWxfW3q1K
GCC hangs in ext-dce pass, where the "df_worklist_dataflow_doublequeue()" loops
forwever on the following basic blocks taken from double-worklists queue:
BB7->BB6->BB4->BB3->BB5->worklists swap->BB7->BB6->BB4->BB3->BB5->worklists
swap ...
Dataflow solver algorithm will serve each BB node while BB sets are still
changing. The key point for solver in deciding whether to continue or not - is
"changed" variable state, which is set by "con_fun_n" function. This function
takes a pointer to "ext_dce_rd_transfer_n()" for ext-dce case. It initializes
"livenow" variables bitmap by "livein[]" states, processes it and finally emits
back "livenow" to the "livein[current BB]". For the selected basic block,
"livein" state flip-flops each time when loop returns back to this BB
processing. E.g. in the example above for the BB=4:
Breakpoint 1, ext_dce_rd_transfer_n (bb_index=4) at ext-dce.cc:980
980 return true;
(gdb) p/x (&livein[bb_index])->first->next->bits
$8 = {0xf000030f0000000, 0xff0}
Continuing...
worklist <-> pedning swap
Breakpoint 2, df_worklist_dataflow_doublequeue (...) at df-core.cc:1097
1097 std::swap (pending, worklist);
Continuing...
(gdb) p/x (&livein[bb_index])->first->next->bits
$11 = {0xf000070f0000000, 0xff0}
Continuing...
So livein[4] bits flip 0xf000030f0000000 -> 0xf000070f0000000 ->
0xf000030f0000000 -> ... states forever.
In other words, ext-dce + df-core could be treated as finite-state machine,
whose states acting on "livenow" and "livein" bitmaps. On the given testcase
machine loops forever, flipping/flopping or widening/narrowing "livein" states
with "livenow". Dataflow solver algorith will never come to the null-worklist
state in this case.
The cornerstone place for all of the described above seems to be "livein"
state, which could be changed in two directions (widen or narrowed) and thus
allowing machine to loop forever. If so, the solution could be to allow
changing of "livein" bitmap state only in one direction: in our case - to
expand. It will cause "ext_dce_rd_transfer_n()" function to also guarantee the
dataflow solver algorithm to converge to its final state.
The proposed solution could be as follows below:
@@ -1094,8 +1094,13 @@ ext_dce_rd_transfer_n (int bb_index)
the generic dataflow code that something changed. */
if (!bitmap_equal_p (&livein[bb_index], livenow))
{
- bitmap_copy (&livein[bb_index], livenow);
- return true;
+ bitmap tmp = BITMAP_ALLOC (NULL);
+ bitmap_and (tmp, &livein[bb_index], livenow);
+ if (!bitmap_equal_p (tmp, livenow))
+ {
+ bitmap_ior_into (&livein[bb_index], livenow);
+ return true;
+ }
}
return false;
It allows "livein[bb_index]" to be only widened and returns true only if it is
being really changed.
The patch works for me locally, and passed simple internal GCC testing. But if
this idea to be considered positively to accept, I will to go with more serious
testing on different targets and prepare its final version ready for mail-list.
