using same awk script as in comment #2 to bug 18595 and -O1 -fno-ivopts one can show that pre is O(N^4):
Nloops Time, s 50 1.12 60 3.02 70 6.41 80 11.4 90 19.4 100 30.1 110 44.7 120 64.8 150 163.5 -- Summary: [4.0 Regression] PRE is O(N^4) Product: gcc Version: 4.0.0 Status: UNCONFIRMED Keywords: compile-time-hog Severity: normal Priority: P2 Component: tree-optimization AssignedTo: unassigned at gcc dot gnu dot org ReportedBy: belyshev at lubercy dot com CC: gcc-bugs at gcc dot gnu dot org http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18673