After r297695, massive compile time increases on large functions

[DimitryAndric]

Bugzilla Link	34326
Resolution	FIXED
Resolved on	Aug 29, 2017 14:39
Version	unspecified
OS	All
Blocks	#33196
Attachments	Tests case that takes more than an hour to compile after r296476
CC	@chandlerc,@emaste,@zmodem

Extended Description

I received a report from the maintainer of the FreeBSD cad/stepcode port (see also http://stepcode.org/), that clang 5.0.0 took so long to build it, that the job was killed after 2 hours. However, with clang 4.0.0, it took about 10 minutes.

Bisection shows that this has regressed with https://reviews.llvm.org/rL296476 ("In visitSTORE, always use FindBetterChain, rather than only when UseAA is enabled").

It took a look, and it turns out that stepcode generates large C++ files, consisting of one function body, sometimes having tens of thousands of lines, similar to:

[...]
node = new OrList;
((MultList *)node)->appendList( child );
next[2]->prev = node;
node->next = next[2];
next[2] = node;
node = new SimpleList( "component_path_shape_aspect" );
next[2]->prev = node;
node->next = next[2];
next[2] = node;
node = new SimpleList( "connection_zone_interface_plane_relationship" );
next[2]->prev = node;
node->next = next[2];
next[2] = node;
node = new SimpleList( "device_terminal_map" );
next[2]->prev = node;
node->next = next[2];
next[2] = node;
node = new SimpleList( "modified_pattern" );
next[2]->prev = node;
node->next = next[2];
next[2] = node;
node = new SimpleList( "make_from_functional_unit_terminal_definition_relationship" );
next[2]->prev = node;
node->next = next[2];
next[2] = node;

For some reason, this type of construct makes clang 5.0.0 spend enormous amounts of time optimizing it. However, that only applies to i386, e.g. 32-bit x86! When targeting x86_64, the effect is much less drastic.

Compile times (in seconds) of clang 5.0.0 when targeting i386, and building the various files of the stepcode port, together with the number of lines in the (usually generated) source file:

time lines filename
======= ===== ============================================================================================
4809.23 28345 schemas/sdai_wip210e3/compstructs.cc
2164.37 19658 schemas/sdai_cd209/compstructs.cc
2056.54 15806 schemas/sdai_ap210e2/compstructs.cc
1545.19 16679 schemas/sdai_cd242/compstructs.cc
446.49 7667 schemas/sdai_ap203e2/compstructs.cc
273.96 6297 schemas/sdai_ap214e3/compstructs.cc
187.16 103 schemas/sdai_ap239/SdaiAP239_PRODUCT_LIFE_CYCLE_SUPPORT_ARM_LF_unity_types.cc
163.39 440 schemas/sdai_cd209/SdaiAP209_MULTIDISCIPLINARY_ANALYSIS_AND_DESIGN_MIM_LF_unity_types.cc
130.02 2232 schemas/sdai_cd209/SdaiAP209_MULTIDISCIPLINARY_ANALYSIS_AND_DESIGN_MIM_LF_unity_entities.cc
122.15 290 schemas/sdai_cd242/SdaiAP242_MANAGED_MODEL_BASED_3D_ENGINEERING_MIM_LF_unity_types.cc

E.g. the top file takes more than an hour to compile! The same results, but then targeting x86_64:

time lines filename
======= ===== ============================================================================================
184.90 28345 schemas/sdai_wip210e3/compstructs.cc
115.08 103 schemas/sdai_ap239/SdaiAP239_PRODUCT_LIFE_CYCLE_SUPPORT_ARM_LF_unity_types.cc
110.00 440 schemas/sdai_cd209/SdaiAP209_MULTIDISCIPLINARY_ANALYSIS_AND_DESIGN_MIM_LF_unity_types.cc
106.70 292 schemas/sdai_wip210e3/SdaiAP210_ELECTRONIC_ASSEMBLY_INTERCONNECT_AND_PACKAGING_DESIGN_MIM_LF_unity_types.cc
90.73 290 schemas/sdai_cd242/SdaiAP242_MANAGED_MODEL_BASED_3D_ENGINEERING_MIM_LF_unity_types.cc
88.77 2232 schemas/sdai_cd209/SdaiAP209_MULTIDISCIPLINARY_ANALYSIS_AND_DESIGN_MIM_LF_unity_entities.cc
81.87 2174 schemas/sdai_wip210e3/SdaiAP210_ELECTRONIC_ASSEMBLY_INTERCONNECT_AND_PACKAGING_DESIGN_MIM_LF_unity_entities.cc
73.92 19658 schemas/sdai_cd209/compstructs.cc
64.82 1734 schemas/sdai_cd242/SdaiAP242_MANAGED_MODEL_BASED_3D_ENGINEERING_MIM_LF_unity_entities.cc
61.42 189 schemas/sdai_ap210e2/SdaiAP210_ELECTRONIC_ASSEMBLY_INTERCONNECT_AND_PACKAGING_DESIGN_MIM_LF_unity_types.cc

I have attached the top file from the i386 build as a test case, which is ~69000 lines, of which ~28000 lines are in the main gencomplex() function. There is also a shell script to show the exact compile options.

Since r296476 is already saying something about a "fixup of 32-bit aliasing sign offset bug in DAGCombiner", I am assuming there is still another 32-bit bug lurking in there somewhere, with rather disastrous consequences.

[DimitryAndric]

Now that I've posted this bug, I see that Chandler had reverted this in r296862, because of (indeed) massive compile time increases. But I still see those massive compile time increases in 5.0.0 rc2, so this was reapplied again later on, it seems.

[zmodem]

Looks like it's been reverted at least 7 times:

$ git log --oneline | grep 'In visitSTORE, always use FindBetterChain'
3bbf394 In visitSTORE, always use FindBetterChain, rather than only when UseAA is enabled.
bfdb3f2 In visitSTORE, always use FindBetterChain, rather than only when UseAA is enabled.
b89cc7e Revert "In visitSTORE, always use FindBetterChain, rather than only when UseAA is enabled."
32147ce In visitSTORE, always use FindBetterChain, rather than only when UseAA is enabled.
529986a Revert "In visitSTORE, always use FindBetterChain, rather than only when UseAA is enabled."
99b0642 In visitSTORE, always use FindBetterChain, rather than only when UseAA is enabled.
d9031ef Revert "In visitSTORE, always use FindBetterChain, rather than only when UseAA is enabled."
dbb7a65 In visitSTORE, always use FindBetterChain, rather than only when UseAA is enabled.
e461ebb Revert "In visitSTORE, always use FindBetterChain, rather than only when UseAA is enabled."
ee001a5 In visitSTORE, always use FindBetterChain, rather than only when UseAA is enabled.
2c96583 Revert "In visitSTORE, always use FindBetterChain, rather than only when UseAA is enabled."
615f3cc In visitSTORE, always use FindBetterChain, rather than only when UseAA is enabled.
080559c Revert "In visitSTORE, always use FindBetterChain, rather than only when UseAA is enabled."
19dc709 In visitSTORE, always use FindBetterChain, rather than only when UseAA is enabled.
bb15ebf Revert "In visitSTORE, always use FindBetterChain, rather than only when UseAA is enabled."
a6d3e00 In visitSTORE, always use FindBetterChain, rather than only when UseAA is enabled.

It was last committed in r297695. There's some follow-up on the commit thread, but it never seems to have gone anywhere.

[DimitryAndric]

...

It was last committed in r297695. There's some follow-up on the commit
thread, but it never seems to have gone anywhere.

Indeed, I re-tested with r297694 and r297695: the former works OK, the latter has the massive compile time.

[llvmbot]

I'm not in a place to check this myself, but it should be much better upstream where I've made a bunch of followup improvements. We should probably apply r309830 to 5.0 as it makes a significant order reduction in the worst-case (large basic blocks of containing 1 or more large sequences of almost but not mergeable stores).

[DimitryAndric]

I'm not in a place to check this myself, but it should be much better
upstream where I've made a bunch of followup improvements. We should
probably apply r309830 to 5.0 as it makes a significant order reduction in
the worst-case (large basic blocks of containing 1 or more large sequences
of almost but not mergeable stores).

Not for me, unfortunately; trunk r296476 takes ~1534s to compile my test case on a quiescent machine, but trunk r311836 (the latest as of 2017-07-26) takes ~2311s. (trunk r296475 takes ~102s.)

[llvmbot]

A quick patch that resolves this https://reviews.llvm.org/D37220 at the potential cost of losing store merges in some large basic blocks. This should take the time back to pre-r296476 speeds.

I've detailed a faster non-conservative check as well in the comments but I won't have time to write it for a bit.

[chandlerc]

FWIW, given that there is already some work on trunk and more work planned to improve this, it seems like the right approach for 5.0 is to back out the functionality to go back to well known state. Then trunk can continue to iterate toward a solid long-term solution.

[zmodem]

FWIW, given that there is already some work on trunk and more work planned
to improve this, it seems like the right approach for 5.0 is to back out the
functionality to go back to well known state. Then trunk can continue to
iterate toward a solid long-term solution.

I'm not sure reverting r297695 is practical.

The revert in itself is difficult because there are lots of merge conflicts.

But my main concern is that it landed way back in March, so reverting it on the branch puts us in a state that isn't well tested, and so close to the release that makes me nervous.

I think we may have to accept this regression in 5.0.0, should work to fix it in trunk and if possible port the fix to 5.0.1.

[llvmbot]

FWIW, given that there is already some work on trunk and more work planned
to improve this, it seems like the right approach for 5.0 is to back out the
functionality to go back to well known state. Then trunk can continue to
iterate toward a solid long-term solution.

I'm not sure reverting r297695 is practical.

The revert in itself is difficult because there are lots of merge conflicts.

But my main concern is that it landed way back in March, so reverting it on
the branch puts us in a state that isn't well tested, and so close to the
release that makes me nervous.

I think we may have to accept this regression in 5.0.0, should work to fix
it in trunk and if possible port the fix to 5.0.1.

Not my call, and I won't argue further, but I'd like to point out that a 10-20x in compile time slowdown is, in some ways, equivalent if not worse than a correctness bug. Basically we're forcing the author of that software to use an old version of clang (or, switch to a different compiler).

Looking at Nirav's bugfix, it seems it's just adding yet another cutoff. This is, of course, not ideal, but seems much better than the superlinear compile time FreeBSD is experiencing right now. If revert is not on the table, I think we might want to consider it.

[zmodem]

FWIW, given that there is already some work on trunk and more work planned
to improve this, it seems like the right approach for 5.0 is to back out the
functionality to go back to well known state. Then trunk can continue to
iterate toward a solid long-term solution.

I'm not sure reverting r297695 is practical.

The revert in itself is difficult because there are lots of merge conflicts.

But my main concern is that it landed way back in March, so reverting it on
the branch puts us in a state that isn't well tested, and so close to the
release that makes me nervous.

I think we may have to accept this regression in 5.0.0, should work to fix
it in trunk and if possible port the fix to 5.0.1.

Not my call, and I won't argue further, but I'd like to point out that a
10-20x in compile time slowdown is, in some ways, equivalent if not worse
than a correctness bug. Basically we're forcing the author of that software
to use an old version of clang (or, switch to a different compiler).

Looking at Nirav's bugfix, it seems it's just adding yet another cutoff.
This is, of course, not ideal, but seems much better than the superlinear
compile time FreeBSD is experiencing right now. If revert is not on the
table, I think we might want to consider it.

Does Nirav's patch fix your specific case? I think revert would be difficult, but taking a cut-off like this seems OK to me.

[llvmbot]

FWIW, given that there is already some work on trunk and more work planned
to improve this, it seems like the right approach for 5.0 is to back out the
functionality to go back to well known state. Then trunk can continue to
iterate toward a solid long-term solution.

I'm not sure reverting r297695 is practical.

The revert in itself is difficult because there are lots of merge conflicts.

But my main concern is that it landed way back in March, so reverting it on
the branch puts us in a state that isn't well tested, and so close to the
release that makes me nervous.

I think we may have to accept this regression in 5.0.0, should work to fix
it in trunk and if possible port the fix to 5.0.1.

Not my call, and I won't argue further, but I'd like to point out that a
10-20x in compile time slowdown is, in some ways, equivalent if not worse
than a correctness bug. Basically we're forcing the author of that software
to use an old version of clang (or, switch to a different compiler).

Looking at Nirav's bugfix, it seems it's just adding yet another cutoff.
This is, of course, not ideal, but seems much better than the superlinear
compile time FreeBSD is experiencing right now. If revert is not on the
table, I think we might want to consider it.

Does Nirav's patch fix your specific case? I think revert would be
difficult, but taking a cut-off like this seems OK to me.

I have a case where Nirav's patch fixes, but I'll wait for Dimitry to confirm this also fixes the FreeBSD stepcode build.

[zmodem]

Let's put this on the blockers list to make sure we don't lose it.

[DimitryAndric]

A quick patch that resolves this https://reviews.llvm.org/D37220 at the
potential cost of losing store merges in some large basic blocks. This
should take the time back to pre-r296476 speeds.

Thanks Nirav, I've tried this out with my test case, and the results look pretty nice! Build times with different versions, targeting i386:

r296475-stock: 117.51 real 116.73 user 0.76 sys
r296476-stock: 1569.20 real 1566.69 user 2.25 sys
r311991-stock: 2387.90 real 2382.04 user 5.43 sys
r311991-D37220: 140.66 real 139.80 user 0.84 sys

And targeting x86_64:

r296475-stock: 147.63 real 146.75 user 0.85 sys
r296476-stock: 156.21 real 153.78 user 0.89 sys
r311991-stock: 210.07 real 209.05 user 0.76 sys
r311991-D37220: 137.13 real 136.24 user 0.86 sys

So with D37220, i386 performance almost gets back to the r296475 level, while on x86_64, the performance is even slightly better. Additionally, the i386 and x86_64 timings are now approximately similar, which I would initially have expected.

[zmodem]

Nirav's patch was committed in r312022.

I'll merge it after it's been in trunk a few hours.

[zmodem]

Nirav's patch was committed in r312022.

I'll merge it after it's been in trunk a few hours.

Merged to 5.0 in r312041.