This is the mail archive of the gcc@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]

Re: Iterative dataflow function


Jan Hubicka <jh@suse.cz> writes:

>> So i got tired of seeing 8 million different implementations of
>> worklist algorithms, and made a function that performs iterative
>> bitvector dataflow for us.
>> 
> ...
>> Is something like this useful enough? It seriously cuts down on the
>> amount of code in most of our dataflow algorithms (LCM, etc).
> Yes, Yes, YES. (IMO:)
> Avoiding any code duplication in gcc is wonderfull IMO!
> We should be curefull to not introduce so much of it.
> 
> In this case the duplicated hunk is small, but yet usefull and may be
> optimized if dataflow turns out to be performance bottleneck in
> future.
There's also the nice feature that it makes it easier to convert your
dataflow from bitmaps to sbitmaps (or vice versa).  In fact, if people
don't mind writing two transfer functions (It's either that, or an
ugly union passed to one. Since tfuns are small, i'd rather see two
than waste memory and performance), we could probably make an
iterative_dataflow function that automatically decided what it should
be doing the actual analysis on, and does the right conversions.
Or whatever.
IMHO, it's a step in the right direction, but i'm biased.


> 
>> I've already got it doing iteration in reverse completion order, using a
>> fibheap based priority queue as the worklist (df_visit_next is, right
>> now, O(n)).
> 
> Adding fibheaps themselves to the libiberty can be wonderfull addition too.
> I have some other palces, where fibheap is best fitting datastructure, but
> my plan was to avoid using it, just as I am lazy to implement it and sorting
> woud work just "well enought".
I'll submit the fibheap stuff sometime today, while i see if i get
more comments on if anyone wants more features in the iterative
functions.


> 
> Thanks,
> Honza

-- 
"For my birthday I got a humidifier and a de-humidifier...  I put
them in the same room and let them fight it out.  Then I filled
my humidifier with wax, and now my room is all shiny.
"-Steven Wright


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