------- Comment #3 from hutchinsonandy at aim dot com 2008-03-10 22:24 ------- Subject: Re: COMBINE repeating same matches and can SEG fault
The quadratic nature does not seem to be particularly problem with the data involved. The log_links is build up incrementally. (with duplicates at present). The patch does a "do over" to check that a potential link is not one already recorded. So initially the list is 0 and grows (hence quadratic) However, it is only truely quadratic if there are no duplicates. Duplicates are grouped together, and if I understand correctly, the last element added will always be checked first - so then inner loop will terminate after 1 iteration if a duplicate is present. The final list is quite small (typically 2-3 elements in length) - directly reflecting the number of links between RTL instruction. If instead the list is created - then pruned afterwards, we have a longer list. So the quadratic nature of the loop is now replaced by check/sorting. This could be better- but only if the final list is of a significant size that can exploit non-quadratic searching Given the overhead of adding/removing linked items, and the small length of list, I believe the patch is better. If, however, the number of RTL operands could be much larger than I have assumed, then perhaps a change is needed. Personally I can't think of many insn that refer to more than 3 other instructions. But I could be wrong. Andy steven at gcc dot gnu dot org wrote: > ------- Comment #2 from steven at gcc dot gnu dot org 2008-03-10 20:04 > ------- > The patch makes adding log use an algorithm quadratic in the number of log > links per insn. It is probably better to: > 1. build the log links. > 2. filter out the duplicates as a post pass (and maybe sort them while at it?) > > > -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35519
