> On Jun 9, 2014, at 3:47 AM, Artyom Skrobov <[email protected]> wrote:
>
> Is it the right time now to look again at unifying the two DataflowWorklists?
>
> Last month, we’ve got as far as establishing that the DataflowWorklist in
> UninitializedValues may not have been intended to start with all blocks
> implicitly enqueued, since it gets some blocks enqueued onto it explicitly
> right after the creation; but we couldn’t decide without Ted whether the
> difference in implementation of the two DataflowWorklists was intentional or
> not.
Hi Artyom,
Not all blocks in the uninitialized values analysis are implicitly enqueued.
Marking them enqueued means that they cannot be added to the worklist. That's
not the same thing as being on the worklist. Notice that we have both
'previouslyVisited' and 'enqueuedBlocks'; the latter is what is used to prevent
blocks from being added to the worklist within DataflowWorklist, but it doesn't
control when the algorithm terminates.
The uninitialized values dataflow analysis alternates between essentially two
worklists. The first is a prioritization worklist that is consulted first, and
the second is to consult the reverse post-order traversal if the prioritization
worklist is empty. The prioritization worklist is used to prioritize analyzing
from the beginning, or to prioritize updates fed by back edges.
Some of the confusion comes from the naming of variables, which is likely
anachronistic with how the code evolved. The 'enqueuedBlocks' is initially set
to 'true' for all blocks not because everything is added initially to the
worklist, but to instead cause us to follow the reverse post order UNTIL we
enqueue something on the worklist. Typically what gets enqueued on the
worklist are back edges, which we want to prioritize analyzing first because
that causes dataflow facts to flow up the graph, which we then want to
propagate forward. In practice this can cause the analysis to converge much
faster. This optimization was done because -Wuninitialized has a real impact
on compile-time performance.
The dataflow analysis in LiveVariables.cpp, which does a reverse analysis, uses
logic fairly similar to what the dataflow analysis in UninitializedValues.cpp
used to be. That uses a simple re-sorting of the worklist to reprioritize the
worklist, but it's probably not as good as what we do in
UninitializedValues.cpp. I think I never bothered updated LiveVariables.cpp
because I ran out of time, and it isn't performance sensitive since it used by
the static analyzer and the static analyzer does far more work that just dwarfs
the work done by LiveVariables.cpp. You may notice that the DataflowWorklist
in UintializedValues.cpp doesn't have a "sortWorklist" method. That is
intentional.
Looking at your patch, you've used the data flow analysis in LiveVariables.cpp
as your baseline implementation for both of them, or you've merged the two
together. This will work, and produce correct results, but may be dramatically
slower for -Wuninitialized. We don't want to be resorting the entire worklist
after enqueueing successors.
Instead:
(1) We should use the reverse post order ONLY when we have no blocks on the
main worklist.
(2) We should consult the main worklist first, so we can get updates from back
edges.
Your new implementation collapses #1 and #2 into one worklist, by enqueing all
blocks and then sorting them in reverse-postorder order. It then relies on
resorting the entire worklist after adding successors every time we visit a
block. That is technically the ideal order, but that sorting and re-sorting is
not cheap in practice.
Instead, we should probably use the approach in UninitializedValues.cpp, which
uses the real worklist as a prioritization worklist, and then consults the
reverse post order second if the worklist is empty. Your tests are passing
because both implementations are correct, but possibly quite a bit slower
because it constantly resorts the worklist.
I think this change to UnintializedValues.cpp came with the following patch:
> Author: Ted Kremenek <[email protected]>
> Date: Sat Nov 17 02:00:00 2012 +0000
>
> Switch -Wuninitialized to use a reverse-post order traversal as
> an initial baseline for enqueued blocks, but use a simple DFS stack
> for propagating changes quickly up back edges.
>
> This provides a 3.5% reduction in -fsyntax-only time on sqlite3.c.
That should provide a good test case for you to determine if your patch
regresses performance.
I'm hoping I'm answering the right question, and I deeply apologize for taking
so long to wade into this discussion.
Ted
_______________________________________________
cfe-commits mailing list
[email protected]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
