Page MenuHomePhabricator

[llvm-cov][gcov] Optimize the cycle counting algorithm by skipping zero count cycles
ClosedPublic

Authored by xinhaoyuan on Dec 10 2020, 8:21 AM.

Details

Summary

This change is similar to http://gcc.gnu.org/PR90380.

This reduces the complexity from exponential to polynomial of the arcs.

Diff Detail

Unit TestsFailed

TimeTest
50 msx64 windows > LLVM.CodeGen/XCore::threads.ll
Script: -- : 'RUN: at line 1'; c:\ws\w16c2-1\llvm-project\premerge-checks\build\bin\llc.exe -march=xcore < C:\ws\w16c2-1\llvm-project\premerge-checks\llvm\test\CodeGen\XCore\threads.ll | c:\ws\w16c2-1\llvm-project\premerge-checks\build\bin\filecheck.exe C:\ws\w16c2-1\llvm-project\premerge-checks\llvm\test\CodeGen\XCore\threads.ll

Event Timeline

xinhaoyuan created this revision.Dec 10 2020, 8:21 AM

Update by running git clang-format.

Add a reviewer.

xinhaoyuan published this revision for review.Dec 10 2020, 8:45 AM
xinhaoyuan added a reviewer: MaskRay.

Hi,

This is the first patch I submitted to LLVM. Please let me know if anything is missing. Thanks!

Herald added a project: Restricted Project. · View Herald TranscriptDec 10 2020, 8:46 AM

Correct the test after clang-format.

lebedev.ri retitled this revision from Optimize the cycle counting algorithm by skipping zero count cycles. This reduces the complexity from exponential to polynomial of the arcs. to [llvm-cov][gcov] Optimize the cycle counting algorithm by skipping zero count cycles. This reduces the complexity from exponential to polynomial of the arcs..Dec 10 2020, 8:57 AM
MaskRay retitled this revision from [llvm-cov][gcov] Optimize the cycle counting algorithm by skipping zero count cycles. This reduces the complexity from exponential to polynomial of the arcs. to [llvm-cov][gcov] Optimize the cycle counting algorithm by skipping zero count cycles.Dec 10 2020, 9:52 AM
MaskRay edited the summary of this revision. (Show Details)

Non-functional change to make clang-tidy happy.

Harbormaster completed remote builds in B81857: Diff 310920.

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.
But I think this probably should be a runtime test: compiler-rt/test/profile/gcov-complex-line.c

Move the test to compiler-rt/test/profile, and get rid of the generated files.

Also add a check to match the result count.

Herald added a project: Restricted Project. · View Herald TranscriptDec 10 2020, 2:39 PM
Herald added a subscriber: Restricted Project. · View Herald Transcript
xinhaoyuan edited the summary of this revision. (Show Details)Dec 10 2020, 2:40 PM

Minor comment change.

I've revised the patch according to the suggestions. Please take another look.

MaskRay accepted this revision.Dec 10 2020, 2:46 PM

Thanks!

compiler-rt/test/profile/gcov-complex-line.c
6 ↗(On Diff #311028)

This line can be deleted since checking the existence of .gcno is out of the scope of this patch.

55 ↗(On Diff #311028)

[[@LINE]] is a deprecated FileCheck syntax. Use [[#@LINE]]

This revision is now accepted and ready to land.Dec 10 2020, 2:46 PM

Revision before submitting.

xinhaoyuan marked 2 inline comments as done.Dec 10 2020, 2:55 PM
This revision was landed with ongoing or failed builds.Dec 10 2020, 3:22 PM
This revision was automatically updated to reflect the committed changes.
Harbormaster completed remote builds in B81919: Diff 311034.