From 6c2497248bc4f7fd8e5fb0a206d20abbf0e16645 Mon Sep 17 00:00:00 2001 From: Ted Kremenek Date: Thu, 24 Sep 2009 18:45:41 +0000 Subject: [PATCH] When building CFGs, no longer reverse the statements in the CFGBlock. Instead have the iterators and operator[] handle the traversal of statements, as they are stored in reverse order. Tests show this has no real performance impact, but it does simply the CFG construction logic and will make it slightly easier to change the allocation strategy for CFGBlocks (as we have fewer copies). git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@82702 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/clang/Analysis/CFG.h | 45 ++++++++++++++++++++++++++++++------ lib/Analysis/CFG.cpp | 24 +++++++------------ 2 files changed, 46 insertions(+), 23 deletions(-) diff --git a/include/clang/Analysis/CFG.h b/include/clang/Analysis/CFG.h index dab718cbac..8b4e191776 100644 --- a/include/clang/Analysis/CFG.h +++ b/include/clang/Analysis/CFG.h @@ -57,9 +57,39 @@ namespace clang { /// &&, || expression that uses result of && or ||, RHS /// class CFGBlock { - typedef std::vector StatementListTy; + class StatementList { + typedef std::vector ImplTy; + ImplTy Impl; + public: + typedef std::reverse_iterator iterator; + typedef std::reverse_iterator const_iterator; + typedef ImplTy::iterator reverse_iterator; + typedef ImplTy::const_iterator const_reverse_iterator; + + void push_back(Stmt *s) { Impl.push_back(s); } + Stmt *front() const { return Impl.back(); } + Stmt *back() const { return Impl.front(); } + + iterator begin() { return Impl.rbegin(); } + iterator end() { return Impl.rend(); } + const_iterator begin() const { return Impl.rbegin(); } + const_iterator end() const { return Impl.rend(); } + reverse_iterator rbegin() { return Impl.begin(); } + reverse_iterator rend() { return Impl.end(); } + const_reverse_iterator rbegin() const { return Impl.begin(); } + const_reverse_iterator rend() const { return Impl.end(); } + + Stmt* operator[](size_t i) const { + assert(i < Impl.size()); + return Impl[Impl.size() - 1 - i]; + } + + size_t size() const { return Impl.size(); } + bool empty() const { return Impl.empty(); } + }; + /// Stmts - The set of statements in the basic block. - StatementListTy Stmts; + StatementList Stmts; /// Label - An (optional) label that prefixes the executable /// statements in the block. When this variable is non-NULL, it is @@ -92,10 +122,10 @@ public: ~CFGBlock() {}; // Statement iterators - typedef StatementListTy::iterator iterator; - typedef StatementListTy::const_iterator const_iterator; - typedef std::reverse_iterator const_reverse_iterator; - typedef std::reverse_iterator reverse_iterator; + typedef StatementList::iterator iterator; + typedef StatementList::const_iterator const_iterator; + typedef StatementList::reverse_iterator reverse_iterator; + typedef StatementList::const_reverse_iterator const_reverse_iterator; Stmt* front() const { return Stmts.front(); } Stmt* back() const { return Stmts.back(); } @@ -113,7 +143,8 @@ public: unsigned size() const { return Stmts.size(); } bool empty() const { return Stmts.empty(); } - Stmt* operator[](size_t i) const { assert (i < size()); return Stmts[i]; } + Stmt* operator[](size_t i) const { return Stmts[i]; } + // CFG iterators typedef AdjacentBlocks::iterator pred_iterator; diff --git a/lib/Analysis/CFG.cpp b/lib/Analysis/CFG.cpp index d5fde0a819..82472338ae 100644 --- a/lib/Analysis/CFG.cpp +++ b/lib/Analysis/CFG.cpp @@ -270,14 +270,12 @@ CFGBlock* CFGBuilder::createBlock(bool add_successor) { return B; } -/// FinishBlock - When the last statement has been added to the block, we must -/// reverse the statements because they have been inserted in reverse order. +/// FinishBlock - "Finalize" the block by checking if we have a bad CFG. bool CFGBuilder::FinishBlock(CFGBlock* B) { if (badCFG) return false; assert(B); - B->reverseStmts(); return true; } @@ -699,9 +697,8 @@ CFGBlock* CFGBuilder::VisitIfStmt(IfStmt* I) { // first statement we are processing. In either case, we create a new basic // block. First, we create the blocks for the then...else statements, and // then we create the block containing the if statement. If we were in the - // middle of a block, we stop processing that block and reverse its - // statements. That block is then the implicit successor for the "then" and - // "else" clauses. + // middle of a block, we stop processing that block. That block is then the + // implicit successor for the "then" and "else" clauses. // The block we were proccessing is now finished. Make it the successor // block. @@ -772,14 +769,14 @@ CFGBlock* CFGBuilder::VisitIfStmt(IfStmt* I) { CFGBlock* CFGBuilder::VisitReturnStmt(ReturnStmt* R) { - // If we were in the middle of a block we stop processing that block and - // reverse its statements. + // If we were in the middle of a block we stop processing that block. // // NOTE: If a "return" appears in the middle of a block, this means that the // code afterwards is DEAD (unreachable). We still keep a basic block // for that code; a simple "mark-and-sweep" from the entry block will be // able to report such dead blocks. - if (Block) FinishBlock(Block); + if (Block) + FinishBlock(Block); // Create the new block. Block = createBlock(false); @@ -1183,8 +1180,7 @@ CFGBlock* CFGBuilder::VisitObjCAtThrowStmt(ObjCAtThrowStmt* S) { // FIXME: This isn't complete. We basically treat @throw like a return // statement. - // If we were in the middle of a block we stop processing that block and - // reverse its statements. + // If we were in the middle of a block we stop processing that block. if (Block && !FinishBlock(Block)) return 0; @@ -1200,8 +1196,7 @@ CFGBlock* CFGBuilder::VisitObjCAtThrowStmt(ObjCAtThrowStmt* S) { } CFGBlock* CFGBuilder::VisitCXXThrowExpr(CXXThrowExpr* T) { - // If we were in the middle of a block we stop processing that block and - // reverse its statements. + // If we were in the middle of a block we stop processing that block. if (Block && !FinishBlock(Block)) return 0; @@ -1518,9 +1513,6 @@ CFG* CFG::buildCFG(Stmt* Statement, ASTContext *C) { return Builder.buildCFG(Statement, C); } -/// reverseStmts - Reverses the orders of statements within a CFGBlock. -void CFGBlock::reverseStmts() { std::reverse(Stmts.begin(),Stmts.end()); } - //===----------------------------------------------------------------------===// // CFG: Queries for BlkExprs. //===----------------------------------------------------------------------===// -- 2.40.0