0000147: Serious load-store optimization performance degradation

Viewing Issue Simple Details [ Jump to Notes ]

[ View Advanced ] [ Issue History ] [ Print ]

Category

Severity

Reproducibility

Date Submitted

Last Update

0000147

[libFirm] optimisations

major

always

2014-09-01 17:17

2014-09-29 10:09

Reporter

mohr

View Status

public

Assigned To

Priority

normal

Resolution

open

Status

confirmed

Product Version

development

Summary

0000147: Serious load-store optimization performance degradation

Description

The current implementation has a quadratic worst-case complexity in the number of graphs in the program. The optimization does the following:

...
assure_irp_globals_entity_usage_computed();
...
clear_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_ENTITY_USAGE);
assure_irg_entity_usage_computed(irg);
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).

Additional Information

Issue History
Date Modified	Username	Field	Change
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

Relationships