Viewing Issue Simple Details Jump to Notes ] View Advanced ] Issue History ] Print ]
ID 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:

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
Tags No tags attached.
Attached Files

- Relationships

There are no notes attached to this issue.

- 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

Mantis 1.1.5[^]
Copyright © 2000 - 2008 Mantis Group
Powered by Mantis Bugtracker