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
tree-pre or rtl-pre aka gcse?
Confirmed. 60% of the time is in bitmap_value_replace_in_set 26% is in bitmap_bit_p
Actually, Tree-PRE is provably O(n^2). We just have a larger constant than we'd like. On all the branches i have checked out (tcb, mainline) 150 loops takes 30 seconds, not 160. THis includes the constification patch i had posted, however, on these branches. I can solve this problem once and for all by using a scoped bitmap set representation instead of copying the sets around.
I have a patch that brings the time on 150 loops to 1.40 seconds, but i haven't decided whether to apply it or not. I have to do more testing on real code. I could make it nothing if i scoped the other bitmap tables, but tihs would probably slow down real code slightly.
Of course it's not very useful to claim that some algorithm is O(N^x) when you don't say what N is...
Subject: Bug 18673 CVSROOT: /cvs/gcc Module name: gcc Changes by: dberlin@gcc.gnu.org 2004-11-30 14:49:39 Modified files: gcc : ChangeLog tree-ssa-pre.c Log message: 2004-11-29 Daniel Berlin <dberlin@dberlin.org> Fix PR tree-optimization/18673 * tree-ssa-pre.c: Remove splay-tree.h include. (bitmap_value_replace_in_set): Fix to add if it does not exist. (find_or_generate_expression): Remove now-wrong condition. (create_expression_by_pieces): Fix condition and comment reason for it. (insert_aux): Fix condition and comment reasons for it. Factor insertion code from here. (insert_into_preds_of_block): To here. Fix conditions in factored function and comment reasons for them. Patches: http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.diff?cvsroot=gcc&r1=2.6647&r2=2.6648 http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/tree-ssa-pre.c.diff?cvsroot=gcc&r1=2.57&r2=2.58
Fixed