From 8052050c8ebfcfbbce8afed57fefc8c95fb9a333 Mon Sep 17 00:00:00 2001 From: Chandler Carruth Date: Fri, 8 Jul 2011 11:19:06 +0000 Subject: [PATCH] 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 | 26 +++++++++++++------------- 1 file changed, 13 insertions(+), 13 deletions(-) diff --git a/lib/Analysis/UninitializedValues.cpp b/lib/Analysis/UninitializedValues.cpp index 96cae9d1f4..1d6959d81b 100644 --- a/lib/Analysis/UninitializedValues.cpp +++ b/lib/Analysis/UninitializedValues.cpp @@ -288,28 +288,28 @@ class DataflowWorklist { public: DataflowWorklist(const CFG &cfg) : enqueuedBlocks(cfg.getNumBlockIDs()) {} - void enqueue(const CFGBlock *block); void enqueueSuccessors(const CFGBlock *block); const CFGBlock *dequeue(); - }; } -void DataflowWorklist::enqueue(const CFGBlock *block) { - if (!block) - return; - unsigned idx = block->getBlockID(); - if (enqueuedBlocks[idx]) - return; - worklist.push_back(block); - enqueuedBlocks[idx] = true; -} - void DataflowWorklist::enqueueSuccessors(const clang::CFGBlock *block) { + unsigned OldWorklistSize = worklist.size(); for (CFGBlock::const_succ_iterator I = block->succ_begin(), E = block->succ_end(); I != E; ++I) { - enqueue(*I); + const CFGBlock *Successor = *I; + if (!Successor || enqueuedBlocks[Successor->getBlockID()]) + continue; + worklist.push_back(Successor); + enqueuedBlocks[Successor->getBlockID()] = true; } + if (OldWorklistSize == 0 || OldWorklistSize == worklist.size()) + return; + + // Rotate the newly added blocks to the start of the worklist so that it forms + // a proper queue when we pop off the end of the worklist. + std::rotate(worklist.begin(), worklist.begin() + OldWorklistSize, + worklist.end()); } const CFGBlock *DataflowWorklist::dequeue() { -- 2.40.0