Details

Reviewers

MaskRay

Commits

rG97260ab4786f: [llvm-cov][gcov] Optimize the cycle counting algorithm by skipping zero count…

Summary

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

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

Diff Detail

Repository: rG LLVM Github Monorepo

Unit TestsFailed
View All

	Time	Test
	50 ms	x64 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

Herald added a subscriber: hiraditya. · View Herald TranscriptDec 10 2020, 8:21 AM

Update by running git clang-format.

Add a reviewer.

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

Herald added a subscriber: llvm-commits. · View Herald Transcript

Harbormaster completed remote builds in B81846: Diff 310900.Dec 10 2020, 8:51 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

Harbormaster completed remote builds in B81849: Diff 310907.Dec 10 2020, 9:18 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 B81855: Diff 310918.Dec 10 2020, 10:00 AM

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

Harbormaster completed remote builds in B81875: Diff 310950.Dec 10 2020, 11:45 AM

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.

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]]`