]> granicus.if.org Git - clang/commit
Make the worklist in the uninitialized values checker actually a queue.
authorChandler Carruth <chandlerc@gmail.com>
Fri, 8 Jul 2011 11:19:06 +0000 (11:19 +0000)
committerChandler Carruth <chandlerc@gmail.com>
Fri, 8 Jul 2011 11:19:06 +0000 (11:19 +0000)
commit8052050c8ebfcfbbce8afed57fefc8c95fb9a333
tree02abea80c8e02b350ffb4e4854d7cbf47e5c6a4e
parentf972b26368570e5fbbb23e1302b28bbf81c15c69
Make the worklist in the uninitialized values checker actually a queue.
Previously, despite the names 'enqueue' and 'dequeue', it behaved as
a stack and visited blocks in a LIFO fashion. This interacts badly with
extremely broad CFGs *inside* of a loop (such as a large switch inside
a state machine) where every block updates a different variable.

When encountering such a CFG, the checker visited blocks in essentially
a "depth first" order due to the stack-like behavior of the work list.
Combined with each block updating a different variable, the saturation
logic of the checker caused it to re-traverse blocks [1,N-1] of the
broad CFG inside the loop after traversing block N. These re-traversals
were to propagate the variable values derived from block N. Assuming
approximately the same number of variables as inner blocks exist, the
end result is O(N^2) updates. By making this a queue, we also make the
traversal essentially "breadth-first" across each of the N inner blocks
of the loop. Then all of this state is propagated around to all N inner
blocks of the loop. The result is O(N) updates.

The truth is in the numbers:
Before, gcc.c:   96409 block visits  (max: 61546,   avg: 591)
After,  gcc.c:   69958 block visits  (max: 33090,   avg: 429)
Before, PR10183: 2540494 block vists (max: 2536495, avg: 37360)
After,  PR10183: 137803 block visits (max: 134406,  avg: 2026)

The nearly 20x reduction in work for PR10183 corresponds to a roughly
100x speedup in compile time.

I've tested it on all the code I can get my hands on, and I've seen no
slowdowns due to this change. Where I've collected stats, the ammount of
work done is on average less. I'll also commit shortly some synthetic
test cases useful in analyzing the performance of CFG-based warnings.

Submitting this based on Doug's feedback that post-commit review should
be good. Ted, please review! Hopefully this helps compile times until
then.

git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@134697 91177308-0d34-0410-b5e6-96231b3b80d8
lib/Analysis/UninitializedValues.cpp