This is an archive of the discontinued LLVM Phabricator instance.

Speed up deferred diagnostic emitter
ClosedPublic

Authored by yaxunl on Mar 29 2020, 8:15 PM.

Details

Summary

Move function emitDeferredDiags from Sema to DeferredDiagsEmitter since it
is only used by DeferredDiagsEmitter.

Also skip visited functions to avoid exponential compile time.

Diff Detail

Event Timeline

yaxunl created this revision.Mar 29 2020, 8:15 PM

I made a suggestion in the other patch about restructuring things out of visitUsedDecl. I'll review this when that's done.

rjmccall added inline comments.Apr 1 2020, 10:12 PM
clang/lib/Sema/Sema.cpp
1508

It makes me a little uncomfortable to be holding an iterator this long while calling a fair amount of other stuff in the meantime.

Your use of DiagsCount is subtle enough that it really needs to be explained in some comments. You're doing stuff conditionally based on both whether the entry exists but also whether it's non-zero.

yaxunl updated this revision to Diff 254537.Apr 2 2020, 8:48 AM
yaxunl marked 2 inline comments as done.

added comments

yaxunl added inline comments.Apr 2 2020, 8:52 AM
clang/lib/Sema/Sema.cpp
1508

added comments

rjmccall added inline comments.Apr 2 2020, 9:29 AM
clang/lib/Sema/Sema.cpp
1508

Okay, thanks for that. Two points, then. First, it looks like the count is really just a boolean for whether the function recursively triggers any diagnostics. And second, can't it just be as simple as whether we've visited that function at all in a context that's forcing diagnostics to be emitted? The logic seems to be to try to emit the diagnostics for each use-path, but why would we want that?

1513

This becomes global state for the visitor; that doesn't seem like it can be right.

bader added a subscriber: bader.Apr 2 2020, 11:08 AM
yaxunl marked 4 inline comments as done.Apr 3 2020, 9:20 AM
yaxunl added inline comments.
clang/lib/Sema/Sema.cpp
1508

For the second comment, we need to visit a function again for each use-path because we need to report each use-path that triggers a diagnostic, otherwise users will see a new error after they fix one error, instead of seeing all the errors at once.

For the first comment, I will change the count to two flags: one for the case where the function is not in device context, the other is for the case where the function is in device context. This will allow us to avoid redundant visits whether or not we are in a device context.

1513

This state is for the root node of each traversal initiated from the items in DeclsToCheckForDeferredDiags. It only needs to be set once. Will rename it as ShouldEmitRootNode and move it to checkRecordedDecl.

yaxunl updated this revision to Diff 254840.Apr 3 2020, 9:25 AM
yaxunl marked 2 inline comments as done.

revised by John's comments

rjmccall added inline comments.Apr 3 2020, 10:13 AM
clang/lib/Sema/Sema.cpp
1508

For the second comment, we need to visit a function again for each use-path because we need to report each use-path that triggers a diagnostic, otherwise users will see a new error after they fix one error, instead of seeing all the errors at once.

This is not what we do in analogous cases where errors are triggered by a use, like in template instantiation. The bug might be that the device program is using a function that it shouldn't be using, or the bug might be that a function that's supposed to be usable from the device is written incorrectly. In the former case, yes, not reporting the errors for each use-path may force the programmer to build multiple times to find all the problematic uses. However, in the latter case you can easily end up emitting a massive number of errors that completely drowns out everything else. It's also non-linear: the number of different use-paths of a particular function can be combinatoric.

yaxunl marked 2 inline comments as done.Apr 3 2020, 12:58 PM
yaxunl added inline comments.
clang/lib/Sema/Sema.cpp
1508

The deferred diagnostics fall into the first case mostly.

Not all diagnostic messages happen in device host functions are deferred. Most of diagnostic messages are emitted immediately, disregarding whether the function is emitted or not.

Only a few special types of diagnostic messages e.g. inline assembly errors, exceptions, varags are deferred. This is because clang has to use pragmas to make all functions device and host in some system headers to be able to use them in device compilation, whereas some of these functions will cause error only if they are emitted in device compilation. Since we cannot change these headers, we have to defer such diagnostics to the point where they are actually triggered. Therefore we are mostly interested in "who is calling these functions" instead of the diagnostics themselves.

For normal programs containing no diagnostics, the current approach should sufficiently avoid all redundant visits and all functions will be visited once.

The functions may be visited multiple times when there are deferred diagnostics, however this should be limited by the maximum number of errors.

rjmccall added inline comments.Apr 3 2020, 2:37 PM
clang/lib/Sema/Sema.cpp
1508

Okay. I understand the point now about being mostly concerned about using functions in headers.

My concern about visiting things a combinatorial number of times is less about generating an excessive number of errors and more about taking an excessive amount of time to finish compilation. The compiler really should not be using any exponential algorithms; a simple visited set will ensure that, but I think what you're doing does not. Can you make a case for why that's not true?

yaxunl marked 3 inline comments as done.Apr 5 2020, 9:11 AM
yaxunl added inline comments.
clang/lib/Sema/Sema.cpp
1508

The current approach is linear for the number of visits to functions.

Let's assume the number of functions is N.

The current approach already restricted revisiting a node that's already in the current use-path to prevent infinite recursion, therefore a use-path has maximum length N.

The functions can be classified as two categories:

Those who trigger deferred diags directly or indirectly, which we call trigger nodes.

Those who do not trigger deferred diags directly or indirectly, which we call non-trigger nodes.

Non-trigger nodes can be identified at most with two visits. All other visits are skipped. Therefore the total number of visits of non-trigger nodes is less than 2*N.

We can also classify the use-paths as trigger paths and non-trigger paths. Each trigger path causes at least one diagnostic emitted. Each non-trigger path does not cause any diagnostics emitted.

Due to limit of maximum diagnostics allowed, the algorithm will stop after a finite number of use-paths visited. Let's say it is M. (In reality, M could be much smaller than the maximum diagnostic allowed.) Then the number of trigger paths is at most M.

Let's list all the use-paths visited and count all the nodes visited in these use-paths.

First we consider all the use-paths that containing only non-trigger nodes, since each non-trigger nodes can only be visited twice. The total number of visits of nodes is less than 2*N.

Then we consider all the trigger paths. Since the maximum path length is N, the total number of nodes visited is less than N*M.

Now we only need to consider the non-trigger paths that starts with trigger nodes and end with a non-trigger node. For example, ABCD, where A, B, C, D denote nodes (functions) visited in the path. We can prove that A, B, C must be trigger nodes, since if any of A, B, C is a non-trigger node, the path will ends earlier, not reaching D. We can also prove that the sub-path ABC must be shared with a trigger path e.g. ABCEF, since otherwise C will be a non-trigger node. Then we do not need to count visit of A, B, and C, since they have already been counted when we count the visited nodes by trigger paths.

Therefore, the total number of visits for functions is less than (2+M)*N, where M is actual number of diagnostics emitted.

rjmccall added inline comments.Apr 5 2020, 10:10 AM
clang/lib/Sema/Sema.cpp
1508

Due to limit of maximum diagnostics allowed, the algorithm will stop after a finite number of use-paths visited.

Why do you think this is true? I don't see anything in your actual code which asks whether the error limit has been reached; it just does all the work and trusts the diagnostics engine to stop emitting diagnostics eventually.

Try turning the error limit off (which will tell you how much work you're doing, since you're not short-circuiting when it's reached) and seeing how many diagnostics you get if you have a chain of functions like this:

// All of these functions should be emitted on demand.
void hasInvalid() { /* this function should trigger a deferred diagnostic of some sort */ }
void use0() { hasInvalid(); hasInvalid(); }
void use1() { use0(); use0(); }
void use2() { use1(); use1(); }
void use3() { use2(); use2(); }
void use4() { use3(); use3(); }
//  The final function should be a kernel or something like that.

Also, in general, since the error limit can be disabled, I don't think it's a good idea for it to be the only thing stopping you from doing an exponential amount of work.

yaxunl marked 3 inline comments as done.Apr 5 2020, 8:35 PM
yaxunl added inline comments.
clang/lib/Sema/Sema.cpp
1508

It seems not practical to emit diagnostic for each triggering use-path since this will cause exponential time and also exponential diagnostics.

I will make change so that each function is visited at most twice.

yaxunl updated this revision to Diff 255315.Apr 6 2020, 6:41 AM
yaxunl marked an inline comment as done.
yaxunl retitled this revision from [NFC] Refactor DeferredDiagsEmitter and skip redundant visit to Speed up deferred diagnostic emitter.
yaxunl edited the summary of this revision. (Show Details)

Revised by John's comments. Skip visited functions and check error limit.

rjmccall accepted this revision.Apr 6 2020, 8:13 AM

Thank you. Minor request, but feel free to commit with that change.

clang/lib/Sema/Sema.cpp
1537

insert returns whether it changed the set, so you can combine this check with the insertion unless the exact ordering is important.

This revision is now accepted and ready to land.Apr 6 2020, 8:13 AM
yaxunl marked 2 inline comments as done.Apr 6 2020, 9:23 AM
yaxunl added inline comments.
clang/lib/Sema/Sema.cpp
1537

The order is important here. We cannot inert until the body of the function has been traversed.

rjmccall added inline comments.Apr 6 2020, 9:52 AM
clang/lib/Sema/Sema.cpp
1537

Why? It only matters if we encounter FD again while recursing into its body, during which time InUsePath.count(FD) will be true and so we'll have bailed out above.

This revision was automatically updated to reflect the committed changes.
yaxunl marked an inline comment as done.
Herald added a project: Restricted Project. · View Herald TranscriptApr 6 2020, 10:20 AM
yaxunl marked 2 inline comments as done.Apr 6 2020, 10:56 AM
yaxunl added inline comments.
clang/lib/Sema/Sema.cpp
1537

You are right. I forgot InUsePath. Will fix this. Thanks.