On 4/16/19 6:05 AM, Roman Zhuykov wrote: > Current algorithm which finds recurrence_length for all DDG strongly > connected components works in like O(N^6) time, where N in the number of > nodes in DDG. The time is so bad mostly for graphs with lots of edges, > like almost N^2 edges. My proposed algorithm works in O(N^3). > Algorithm of finding SCCs itself is also not optimal (maybe up to > O(N^4)), but here it left untouched. > > For some situations, when amount of edges is smaller (like equal to N), > new algorithm can be unfortunately slower than old one. But I think > it's better here to add some bail-out when we got more than 1000 nodes > for example. > > Before creating this patch, I tested special version of it, where both > approaches were in action and asserts were inserted to check that > algorithms results (longest_simple_path values) are absolutely the same. > I can publish this special version if needed. > > I’ve described patch testing in cover letter. Ok for trunk? > > gcc/ChangeLog: > > 2019-04-08 Roman Zhuykov <zhr...@ispras.ru> > > PR rtl-optimization/90001 > * ddg.c (create_ddg): Init max_dist array for each node. > (free_ddg): Free max_dist array. > (create_ddg_edge): Use bool field instead of aux union. > (set_recurrence_length): Use prepared max_dist information instead > of calling longest_simple_path. > (create_scc): Remove graph argument, fill node's aux.count with > SCC id, and move set_recurrence_length call to... > (create_ddg_all_sccs): ...here, after filling all max_dist arrays > using Floyd–Warshall-like algorithm. > (update_dist_to_successors): Remove the whole function. > (longest_simple_path): Likewise. > * ddg.h (struct ddg_node): Add max_dist pointer. > (struct ddg_edge): Use bool field instead of unused aux union. So just an FYI. If ddg.c is only used by the modulo scheduler, then it falls under your maintainership and you can decide when to install this patch.
We generally try to avoid major changes right after the branch is cut, but I doubt we'll be doing a lot of backporting in this code, so I think you can go whenever you're ready. jeff >
