|Anonymous | Login | Signup for a new account||2020-02-28 02:47 CET|
|Main | My View | View Issues|
|Viewing Issue Simple Details|
|ID||Category||Severity||Reproducibility||Date Submitted||Last Update|
|0000147||[libFirm] optimisations||major||always||2014-09-01 17:17||2014-09-29 10:09|
|Summary||0000147: Serious load-store optimization performance degradation|
The current implementation has a quadratic worst-case complexity in the number of graphs in the program. The optimization does the following:
irg_walk_graph(irg, NULL, do_eliminate_dead_stores, &env);
assure_irp_globals_entity_usage_computed() requires a walk over all graphs in the program if the usage information is invalid. Since commit 220d57059a567e422c5adf11a5cd272957ca2d54, clearing IR_GRAPH_PROPERTY_CONSISTENT_ENTITY_USAGE also invalidates the global usage information (which is correct, I think). However, the next call to assure_irp_globals_entity_usage_computed() will now walk over all graphs again. As the load-store optimization is usually called on each graph in a program, this leads to quadratic complexity.
In the case of the X10 compiler, where we have a large number of graphs, this blows up the compile time by a factor of 10. The problem did not occur before, because both commit 220d57059a567e422c5adf11a5cd272957ca2d54 and commit 3d377d6bb8fe8769b7e187b2d0a186bbb4db0577 are needed (the latter removes an if statement; alias analysis was not enabled for the X10 compiler, not even for -O3).
|Tags||No tags attached.|
|There are no notes attached to this issue.|
|2014-09-01 17:17||mohr||New Issue|
|2014-09-01 17:18||mohr||Description Updated|
|2014-09-29 10:09||Matze||Status||new => confirmed|
|Mantis 1.1.5[^] Copyright © 2000 - 2008 Mantis Group|