On 7/1/19 7:47 PM, Martin Sebor wrote: > > Jeff, I looked into your question/suggestion for me last week > when we spoke, to introduce some sort of a recursion limit for > get_range_strlen_dynamic. It's easily doable but before we go > down that path I did some testing to see how bad it can get and > to compare it with get_range_strlen. Here are the results for > a few packages. The dept is the maximum recursion depth, success > and fail are the numbers of successful and failed calls to > the function: > > binutils-gdb: > depth success fail > get_range_strlen: 319 8302 21621 > get_range_strlen_dynamic: 41 1503 161 > gcc: > get_range_strlen: 46 7211 11365 > get_range_strlen_dynamic: 23 10272 12 > glibc: > get_range_strlen: 76 2840 11422 > get_range_strlen_dynamic: 51 1186 46 > elfutils: > get_range_strlen: 33 1198 2516 > get_range_strlen_dynamic: 31 685 36 > kernel: > get_range_strlen: 25 5299 11698 > get_range_strlen_dynamic: 31 9911 122 > > Except the first case of get_range_strlen (I haven't looked into > it yet), it doesn't seem too bad, and with just one exception it's > better than get_range_strlen. Let me know if you think it's worth > adding a parameter (I assume we'd use it for both functions) and > what to set it to. So I know you've added a limiter, but just to close on this topic. I generally agree with Richi on this -- we've regularly seen instances where these pathological cases occur in the wild. For the most part I wouldn't consider any of the codebases above to be good at finding those pathological cases. They are reasonably good for finding the inflection point for diminishing gains though.
For codes which walk PHI nodes Bradly Lucier's testcases are often useful (there's many in BZ in various states). His testcases tend to have both lots of PHI nodes and PHI nodes with many arguments. I don't recall if the depth of any given use-def chain in those tests are terribly long though. One could ponder going through the old compile-time hogs in the BZ database and using that to build some kind of testsuite for these kinds of issues. I question if we could reliably run them from the dejagnu suite without significant cost, but they might be useful when trying to evaluate stuff like if we've got reasonable clamps on recursive walks, absurd loop nests, etc. jeff
