[cfo] where to find tree-ssa implementation / questions about rtl implementation.

[schaecsn <schaecsn at gmx dot net>]

Hello,

I'm interested in the code factoring optimization project http://gcc.gnu.org/projects/cfo.html

I checked out the code ( svn  checkout svn://gcc.gnu.org/svn/gcc/trunk cfo ) but I just find the RTL implementation in rtl-factoring.c . I just wonder in which file I can find the tree-ssa form implementation.


I started to read the RTL implementation and try to understand it. Literature builds suffix trees but the RTL implementation uses other data structures. Is there a particular reason not to follow well established algorithms?


That's how far I understand the algorithm:

1. fill_hash_bucket fills a hash table of hash tables with all statements (It can also happen that different statements end up in the same bucket, I guess).

2. collect_pattern_seq goes over each distinct combination of seq_candidates ( (cand1, cand2), (cand1, cand3), (cand1, cand4), ..., (cand2, cand1), (cand2, cand3), (cand2, cand4), ..., (cand3, cand1), (cand3, cand2), (cand3, cand4), ... etc) and calls match_seq(cand<x>, cand<y>):

for cand<x> and cand<y> the longest identical code sequences up to cand<x> and cand<y> are extracted. Next, lists of matching sequences pattern_seqs are build. Here I'm confused!  First time this function gets called with (cand1, cand2) and cand2 will be the first element in that list, then (cand1, cand3) get passed and cand3 will be the next element ... that goes on till(cand<n-1>, cand<n>).  As seen above, this function gets called with all possible combinations, so the the next combinations are (cand2, cand1), (cand1, cand3) etc. That means that an arbitrary cand<x> gets added n-times to that list. Is this true?

 Stefan