This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [ssaupdate] Local dominance info


no; the algorithm is quite ad-hoc and I believe that it behaves
quite badly from the theoretic point of view.  It should (and seems to)
behave well under "normal" workload (i.e. relatively few insertions on
single place), but it of course would be better to have here something
for that some upper bound could be proved (I am fairly sure it would be
possible, and probably the solution would not be much more complicated
than the current one).

I'm thinking about some kind of local algorithm that only looks at a few neighbors and spaces them irregularly, such as



S1:10 S1:10 S1:10 S1: 5 S8:11 S2:20 S2:18 S2:18 S2:18 S3:30 S3:24 S3:23 S3:23 => S6:30 => S6:28 => S6:28 S7:33 S7:33 S4:40 S4:36 S4:42 S4:42 S5:50 S5:50 S5:50 S5:50

The algorithm could iterate until it guarantees a spacing of at least a few units between two instructions (2 is enough of course, but I think it gives bad behavior).

Graph layout algorithms usually work by simulating spring forces between nodes. Something similar can probably be done in this case quite efficiently.

Paolo


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]