This change is similar to http://gcc.gnu.org/PR90380.
This reduces the complexity from exponential to polynomial of the arcs.
Differential D93036
[llvm-cov][gcov] Optimize the cycle counting algorithm by skipping zero count cycles xinhaoyuan on Dec 10 2020, 8:21 AM. Authored by
Details This change is similar to http://gcc.gnu.org/PR90380. This reduces the complexity from exponential to polynomial of the arcs.
Diff Detail
Event TimelineComment Actions Hi, This is the first patch I submitted to LLVM. Please let me know if anything is missing. Thanks! Comment Actions Thanks for the patch! Probably worth mentioning that this is similar to http://gcc.gnu.org/PR90380 I believe this patch essentially uses David B Johnson's cycle enumeration algorithm to perform Klein's cycle cancelling method. I'll follow up and switch to Edmonds-Karp for simplicity. complex-line.gcno is too large (153KiB). If you name the source file a.c and use the relative filename when compiling, it can be smaller. Comment Actions Move the test to compiler-rt/test/profile, and get rid of the generated files. Also add a check to match the result count. |