------- Comment #28 from steven at gcc dot gnu dot org 2007-12-16 12:01 ------- Created an attachment (id=14778) --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=14778&action=view) Change worklist solver to double queue algorithm
I re-read Cooper, Harvey and Kennedy, who wrote a nice paper about various work list based dataflow solvers. The attached patch modifies df_worklist_dataflow to a double queue algorithm, while retaining the property that basic blocks are added to the queue in RPO order. This approach gives me a speedup comparable to (but slightly less than) the hybrid search algorithm. This is not really surprising because the double queue work list algorithm also completes full iterations over the CFG before considering the second queue. Seongbae, what are your ideas about the double queue approach (or maybe other algorithms suggested by Harvey)? -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=34400
