head 1.1; branch 1.1.1; access; symbols netbsd-11-0-RC4:1.1.1.2 netbsd-11-0-RC3:1.1.1.2 netbsd-11-0-RC2:1.1.1.2 netbsd-11-0-RC1:1.1.1.2 perseant-exfatfs-base-20250801:1.1.1.2 netbsd-11:1.1.1.2.0.24 netbsd-11-base:1.1.1.2 netbsd-10-1-RELEASE:1.1.1.2 perseant-exfatfs-base-20240630:1.1.1.2 perseant-exfatfs:1.1.1.2.0.22 perseant-exfatfs-base:1.1.1.2 netbsd-8-3-RELEASE:1.1.1.2 netbsd-9-4-RELEASE:1.1.1.2 netbsd-10-0-RELEASE:1.1.1.2 netbsd-10-0-RC6:1.1.1.2 netbsd-10-0-RC5:1.1.1.2 netbsd-10-0-RC4:1.1.1.2 netbsd-10-0-RC3:1.1.1.2 netbsd-10-0-RC2:1.1.1.2 netbsd-10-0-RC1:1.1.1.2 netbsd-10:1.1.1.2.0.20 netbsd-10-base:1.1.1.2 netbsd-9-3-RELEASE:1.1.1.2 cjep_sun2x:1.1.1.2.0.18 cjep_sun2x-base:1.1.1.2 cjep_staticlib_x-base1:1.1.1.2 netbsd-9-2-RELEASE:1.1.1.2 cjep_staticlib_x:1.1.1.2.0.16 cjep_staticlib_x-base:1.1.1.2 netbsd-9-1-RELEASE:1.1.1.2 phil-wifi-20200421:1.1.1.2 phil-wifi-20200411:1.1.1.2 phil-wifi-20200406:1.1.1.2 netbsd-8-2-RELEASE:1.1.1.2 netbsd-9-0-RELEASE:1.1.1.2 netbsd-9-0-RC2:1.1.1.2 netbsd-9-0-RC1:1.1.1.2 netbsd-9:1.1.1.2.0.14 netbsd-9-base:1.1.1.2 netbsd-8-1-RELEASE:1.1.1.2 netbsd-8-1-RC1:1.1.1.2 pgoyette-compat-merge-20190127:1.1.1.2 pgoyette-compat-20190127:1.1.1.2 pgoyette-compat-20190118:1.1.1.2 pgoyette-compat-1226:1.1.1.2 pgoyette-compat-1126:1.1.1.2 pgoyette-compat-1020:1.1.1.2 pgoyette-compat-0930:1.1.1.2 pgoyette-compat-0906:1.1.1.2 netbsd-7-2-RELEASE:1.1.1.1.2.1 pgoyette-compat-0728:1.1.1.2 netbsd-8-0-RELEASE:1.1.1.2 pgoyette-compat-0625:1.1.1.2 netbsd-8-0-RC2:1.1.1.2 pgoyette-compat-0521:1.1.1.2 pgoyette-compat-0502:1.1.1.2 pgoyette-compat-0422:1.1.1.2 netbsd-8-0-RC1:1.1.1.2 pgoyette-compat-0415:1.1.1.2 pgoyette-compat-0407:1.1.1.2 pgoyette-compat-0330:1.1.1.2 pgoyette-compat-0322:1.1.1.2 pgoyette-compat-0315:1.1.1.2 netbsd-7-1-2-RELEASE:1.1.1.1.2.1 pgoyette-compat:1.1.1.2.0.12 pgoyette-compat-base:1.1.1.2 netbsd-7-1-1-RELEASE:1.1.1.1.2.1 perseant-stdc-iso10646:1.1.1.2.0.10 perseant-stdc-iso10646-base:1.1.1.2 netbsd-8:1.1.1.2.0.8 netbsd-8-base:1.1.1.2 prg-localcount2-base3:1.1.1.2 prg-localcount2-base2:1.1.1.2 prg-localcount2-base1:1.1.1.2 prg-localcount2:1.1.1.2.0.6 prg-localcount2-base:1.1.1.2 pgoyette-localcount-20170426:1.1.1.2 bouyer-socketcan-base1:1.1.1.2 pgoyette-localcount-20170320:1.1.1.2 netbsd-7-1:1.1.1.1.2.1.0.4 netbsd-7-1-RELEASE:1.1.1.1.2.1 netbsd-7-1-RC2:1.1.1.1.2.1 bouyer-socketcan:1.1.1.2.0.4 bouyer-socketcan-base:1.1.1.2 pgoyette-localcount-20170107:1.1.1.2 netbsd-7-1-RC1:1.1.1.1.2.1 pgoyette-localcount-20161104:1.1.1.2 netbsd-7-0-2-RELEASE:1.1.1.1.2.1 localcount-20160914:1.1.1.2 pgoyette-localcount-20160806:1.1.1.2 pgoyette-localcount-20160726:1.1.1.2 pgoyette-localcount:1.1.1.2.0.2 pgoyette-localcount-base:1.1.1.2 netbsd-7-0-1-RELEASE:1.1.1.1.2.1 netbsd-7-0:1.1.1.1.2.1.0.2 netbsd-7-0-RELEASE:1.1.1.1.2.1 netbsd-7-0-RC3:1.1.1.1.2.1 netbsd-7-0-RC2:1.1.1.1.2.1 netbsd-7-0-RC1:1.1.1.1.2.1 tls-maxphys-base:1.1.1.1 tls-maxphys:1.1.1.1.0.4 netbsd-7:1.1.1.1.0.2 netbsd-7-base:1.1.1.1 clang-215315:1.1.1.1 LLVM:1.1.1; locks; strict; comment @// @; 1.1 date 2014.08.10.17.08.27; author joerg; state Exp; branches 1.1.1.1; next ; commitid N85tXAN6Ex9VZPLx; 1.1.1.1 date 2014.08.10.17.08.27; author joerg; state Exp; branches 1.1.1.1.2.1 1.1.1.1.4.1; next 1.1.1.2; commitid N85tXAN6Ex9VZPLx; 1.1.1.2 date 2015.01.29.21.04.26; author joerg; state dead; branches; next ; commitid 0Rh4yhuivi2sMX7y; 1.1.1.1.2.1 date 2015.06.04.20.04.27; author snj; state dead; branches; next ; commitid yRnjq9fueSo6n9oy; 1.1.1.1.4.1 date 2014.08.10.17.08.27; author tls; state dead; branches; next 1.1.1.1.4.2; commitid jTnpym9Qu0o4R1Nx; 1.1.1.1.4.2 date 2014.08.19.23.47.26; author tls; state Exp; branches; next ; commitid jTnpym9Qu0o4R1Nx; desc @@ 1.1 log @Initial revision @ text @//===- DataflowWorklist.cpp - worklist for dataflow analysis ------*- C++ --*-// // // The LLVM Compiler Infrastructure // // This file is distributed under the University of Illinois Open Source // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // // DataflowWorklist is used in LiveVariables and UninitializedValues analyses // //===----------------------------------------------------------------------===// #include "clang/Analysis/Analyses/DataflowWorklist.h" using namespace clang; // Marking a block as enqueued means that it cannot be re-added to the worklist, // but it doesn't control when the algorithm terminates. // Initially, enqueuedBlocks is set to true for all blocks; // that's not because everything is added initially to the worklist, // but instead, to cause the forward analysis to follow the reverse post order // until we enqueue something on the worklist. void DataflowWorklist::enqueueBlock(const clang::CFGBlock *block) { if (block && !enqueuedBlocks[block->getBlockID()]) { enqueuedBlocks[block->getBlockID()] = true; worklist.push_back(block); } } // The forward analysis alternates between essentially two worklists. // A prioritization worklist (SmallVector worklist) // is consulted first, and if it's empty, we consult the reverse // post-order traversal (PostOrderCFGView::iterator PO_I). // The prioritization worklist is used to prioritize analyzing from // the beginning, or to prioritize updates fed by back edges. // 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. void DataflowWorklist::enqueueSuccessors(const clang::CFGBlock *block) { for (CFGBlock::const_succ_iterator I = block->succ_begin(), E = block->succ_end(); I != E; ++I) { enqueueBlock(*I); } } // The reverse analysis uses a simple re-sorting of the worklist to // reprioritize it. It's not as efficient as the two-worklists approach, // but it isn't performance sensitive since it's used by the static analyzer, // and the static analyzer does far more work that dwarfs the work done here. // TODO: It would still be nice to use the same approach for both analyses. void DataflowWorklist::enqueuePredecessors(const clang::CFGBlock *block) { const unsigned OldWorklistSize = worklist.size(); for (CFGBlock::const_pred_iterator I = block->pred_begin(), E = block->pred_end(); I != E; ++I) { enqueueBlock(*I); } if (OldWorklistSize == 0 || OldWorklistSize == worklist.size()) return; sortWorklist(); } const CFGBlock *DataflowWorklist::dequeue() { const CFGBlock *B = nullptr; // First dequeue from the worklist. This can represent // updates along backedges that we want propagated as quickly as possible. if (!worklist.empty()) B = worklist.pop_back_val(); // Next dequeue from the initial reverse post order. This is the // theoretical ideal in the presence of no back edges. else if (PO_I != PO_E) { B = *PO_I; ++PO_I; } else { return nullptr; } assert(enqueuedBlocks[B->getBlockID()] == true); enqueuedBlocks[B->getBlockID()] = false; return B; } void DataflowWorklist::sortWorklist() { std::sort(worklist.begin(), worklist.end(), comparator); } @ 1.1.1.1 log @Import clang 3.6svn r215315. @ text @@ 1.1.1.1.2.1 log @Update LLVM to 3.6.1, requested by joerg in ticket 824. @ text @@ 1.1.1.2 log @Remove files no longer present with clang-227398/llvm-227398. @ text @@ 1.1.1.1.4.1 log @file DataflowWorklist.cpp was added on branch tls-maxphys on 2014-08-19 23:47:26 +0000 @ text @d1 92 @ 1.1.1.1.4.2 log @Rebase to HEAD as of a few days ago. @ text @a0 92 //===- DataflowWorklist.cpp - worklist for dataflow analysis ------*- C++ --*-// // // The LLVM Compiler Infrastructure // // This file is distributed under the University of Illinois Open Source // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // // DataflowWorklist is used in LiveVariables and UninitializedValues analyses // //===----------------------------------------------------------------------===// #include "clang/Analysis/Analyses/DataflowWorklist.h" using namespace clang; // Marking a block as enqueued means that it cannot be re-added to the worklist, // but it doesn't control when the algorithm terminates. // Initially, enqueuedBlocks is set to true for all blocks; // that's not because everything is added initially to the worklist, // but instead, to cause the forward analysis to follow the reverse post order // until we enqueue something on the worklist. void DataflowWorklist::enqueueBlock(const clang::CFGBlock *block) { if (block && !enqueuedBlocks[block->getBlockID()]) { enqueuedBlocks[block->getBlockID()] = true; worklist.push_back(block); } } // The forward analysis alternates between essentially two worklists. // A prioritization worklist (SmallVector worklist) // is consulted first, and if it's empty, we consult the reverse // post-order traversal (PostOrderCFGView::iterator PO_I). // The prioritization worklist is used to prioritize analyzing from // the beginning, or to prioritize updates fed by back edges. // 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. void DataflowWorklist::enqueueSuccessors(const clang::CFGBlock *block) { for (CFGBlock::const_succ_iterator I = block->succ_begin(), E = block->succ_end(); I != E; ++I) { enqueueBlock(*I); } } // The reverse analysis uses a simple re-sorting of the worklist to // reprioritize it. It's not as efficient as the two-worklists approach, // but it isn't performance sensitive since it's used by the static analyzer, // and the static analyzer does far more work that dwarfs the work done here. // TODO: It would still be nice to use the same approach for both analyses. void DataflowWorklist::enqueuePredecessors(const clang::CFGBlock *block) { const unsigned OldWorklistSize = worklist.size(); for (CFGBlock::const_pred_iterator I = block->pred_begin(), E = block->pred_end(); I != E; ++I) { enqueueBlock(*I); } if (OldWorklistSize == 0 || OldWorklistSize == worklist.size()) return; sortWorklist(); } const CFGBlock *DataflowWorklist::dequeue() { const CFGBlock *B = nullptr; // First dequeue from the worklist. This can represent // updates along backedges that we want propagated as quickly as possible. if (!worklist.empty()) B = worklist.pop_back_val(); // Next dequeue from the initial reverse post order. This is the // theoretical ideal in the presence of no back edges. else if (PO_I != PO_E) { B = *PO_I; ++PO_I; } else { return nullptr; } assert(enqueuedBlocks[B->getBlockID()] == true); enqueuedBlocks[B->getBlockID()] = false; return B; } void DataflowWorklist::sortWorklist() { std::sort(worklist.begin(), worklist.end(), comparator); } @