[Bug tree-optimization/18587] [4.1 Regression] build_v_may_defs and build_vuses can be improved when adding

["amacleod at redhat dot com" <gcc-bugzilla at gcc dot gnu dot org>]

------- Comment #11 from amacleod at redhat dot com  2005-10-04 12:46 -------
Created an attachment (id=9868)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=9868&action=view)
patch to replace the operand build vectors

Virtual operands are maintained in a sorted order, and the scanner was
keeping them sorted as they were inserted. When there were a lot of
operands, this could result in a lot of time searching for the right
place to insert them.

Part of the original reason for sorting them was to be able to detect
duplicates and reject them. The original patch for this bug detects duplicate
faster, so there is no longer a pressing need to have them sorted early.  They
still need to be sorted as there are passes which depend on the order being
predictable.  

This patch removes all the opbuild_* routines to maintain the operand
list as sorted, and simply replaces it with a VEC of operands. This VEC is
then sorted if necessary by a call to qsort.

This results in some good improvements in cases where there are a
lot of virtual operands.

on an x86-64 machine:

mainline tree operand scan      13.67 secs
         total time             65.00 secs

patched  tree operands scan      4.20 secs
         total time             50.09 secs

Same testcase on a 3.0Ghz p4:

mainline tree operand scan      18.61 secs
         total time             69.19 secs

patched  tree operands scan      3.85 secs
         total time             49.86 secs

overall effect to the cc1-i collection of files appears to be pretty
neutral..  tree optimizers and operands scan appear slightly faster,
overall time similar or a hair slower (1 second on 204 seconds). Couldnt
tell you why. maybe measurement noise.  C tends not to have nearly as
many virtual operands, so I don't expect the same kind of speedups
there.

bootstrapped and no new test failures on  i686-pc-linux-gnu.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18587