aboutsummaryrefslogtreecommitdiff
path: root/lib/Analysis/CFG.cpp
diff options
context:
space:
mode:
authorMike Stump <mrs@apple.com>2009-07-17 01:31:16 +0000
committerMike Stump <mrs@apple.com>2009-07-17 01:31:16 +0000
commit6d9828c82c9321f042ab416fd2ffaa3034347d45 (patch)
treef47c3b0d2546fa938c3536aba37f8f6b9eb6f998 /lib/Analysis/CFG.cpp
parent5cad1f74469d4d8b4fc51fe53a7837778aeb6107 (diff)
Fixup indentation of rest of switch statement to match llvm coding
conventions. Also reflowed comments and removed spaces at end of lines and fixed up 80 col violations. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@76140 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib/Analysis/CFG.cpp')
-rw-r--r--lib/Analysis/CFG.cpp1357
1 files changed, 667 insertions, 690 deletions
diff --git a/lib/Analysis/CFG.cpp b/lib/Analysis/CFG.cpp
index c77f8cebda..884bc177fd 100644
--- a/lib/Analysis/CFG.cpp
+++ b/lib/Analysis/CFG.cpp
@@ -38,15 +38,15 @@ struct VISIBILITY_HIDDEN SaveAndRestore {
T& X;
T old_value;
};
-
+
static SourceLocation GetEndLoc(Decl* D) {
if (VarDecl* VD = dyn_cast<VarDecl>(D))
if (Expr* Ex = VD->getInit())
return Ex->getSourceRange().getEnd();
-
- return D->getLocation();
+
+ return D->getLocation();
}
-
+
/// CFGBuilder - This class implements CFG construction from an AST.
/// The builder is stateful: an instance of the builder should be used to only
/// construct a single CFG.
@@ -56,13 +56,12 @@ static SourceLocation GetEndLoc(Decl* D) {
/// CFGBuilder builder;
/// CFG* cfg = builder.BuildAST(stmt1);
///
-/// CFG construction is done via a recursive walk of an AST.
-/// We actually parse the AST in reverse order so that the successor
-/// of a basic block is constructed prior to its predecessor. This
-/// allows us to nicely capture implicit fall-throughs without extra
-/// basic blocks.
+/// CFG construction is done via a recursive walk of an AST. We actually parse
+/// the AST in reverse order so that the successor of a basic block is
+/// constructed prior to its predecessor. This allows us to nicely capture
+/// implicit fall-throughs without extra basic blocks.
///
-class VISIBILITY_HIDDEN CFGBuilder : public StmtVisitor<CFGBuilder,CFGBlock*> {
+class VISIBILITY_HIDDEN CFGBuilder : public StmtVisitor<CFGBuilder,CFGBlock*> {
CFG* cfg;
CFGBlock* Block;
CFGBlock* Succ;
@@ -70,36 +69,36 @@ class VISIBILITY_HIDDEN CFGBuilder : public StmtVisitor<CFGBuilder,CFGBlock*> {
CFGBlock* BreakTargetBlock;
CFGBlock* SwitchTerminatedBlock;
CFGBlock* DefaultCaseBlock;
-
+
// LabelMap records the mapping from Label expressions to their blocks.
typedef llvm::DenseMap<LabelStmt*,CFGBlock*> LabelMapTy;
LabelMapTy LabelMap;
-
- // A list of blocks that end with a "goto" that must be backpatched to
- // their resolved targets upon completion of CFG construction.
+
+ // A list of blocks that end with a "goto" that must be backpatched to their
+ // resolved targets upon completion of CFG construction.
typedef std::vector<CFGBlock*> BackpatchBlocksTy;
BackpatchBlocksTy BackpatchBlocks;
-
+
// A list of labels whose address has been taken (for indirect gotos).
typedef llvm::SmallPtrSet<LabelStmt*,5> LabelSetTy;
LabelSetTy AddressTakenLabels;
-
-public:
+
+public:
explicit CFGBuilder() : cfg(NULL), Block(NULL), Succ(NULL),
ContinueTargetBlock(NULL), BreakTargetBlock(NULL),
SwitchTerminatedBlock(NULL), DefaultCaseBlock(NULL) {
// Create an empty CFG.
- cfg = new CFG();
+ cfg = new CFG();
}
-
+
~CFGBuilder() { delete cfg; }
-
+
// buildCFG - Used by external clients to construct the CFG.
CFG* buildCFG(Stmt* Statement);
-
- // Visitors to walk an AST and construct the CFG. Called by
- // buildCFG. Do not call directly!
-
+
+ // Visitors to walk an AST and construct the CFG. Called by buildCFG. Do not
+ // call directly!
+
CFGBlock* VisitBreakStmt(BreakStmt* B);
CFGBlock* VisitCaseStmt(CaseStmt* Terminator);
CFGBlock* VisitCompoundStmt(CompoundStmt* C);
@@ -125,24 +124,24 @@ public:
badCFG = true;
return Block;
}
-
+
CFGBlock* VisitObjCAtTryStmt(ObjCAtTryStmt* S);
- CFGBlock* VisitObjCAtCatchStmt(ObjCAtCatchStmt* S) {
- // FIXME: For now we pretend that @catch and the code it contains
- // does not exit.
+ CFGBlock* VisitObjCAtCatchStmt(ObjCAtCatchStmt* S) {
+ // FIXME: For now we pretend that @catch and the code it contains does not
+ // exit.
return Block;
}
- // FIXME: This is not completely supported. We basically @throw like
- // a 'return'.
+ // FIXME: This is not completely supported. We basically @throw like a
+ // 'return'.
CFGBlock* VisitObjCAtThrowStmt(ObjCAtThrowStmt* S);
CFGBlock* VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt* S);
-
+
// Blocks.
CFGBlock* VisitBlockExpr(BlockExpr* E) { return NYS(); }
- CFGBlock* VisitBlockDeclRefExpr(BlockDeclRefExpr* E) { return NYS(); }
-
+ CFGBlock* VisitBlockDeclRefExpr(BlockDeclRefExpr* E) { return NYS(); }
+
private:
CFGBlock* createBlock(bool add_successor = true);
CFGBlock* addStmt(Stmt* Terminator);
@@ -151,10 +150,10 @@ private:
CFGBlock* WalkAST_VisitDeclSubExpr(Decl* D);
CFGBlock* WalkAST_VisitStmtExpr(StmtExpr* Terminator);
bool FinishBlock(CFGBlock* B);
-
+
bool badCFG;
};
-
+
// FIXME: Add support for dependent-sized array types in C++?
// Does it even make sense to build a CFG for an uninstantiated template?
static VariableArrayType* FindVA(Type* t) {
@@ -162,45 +161,45 @@ static VariableArrayType* FindVA(Type* t) {
if (VariableArrayType* vat = dyn_cast<VariableArrayType>(vt))
if (vat->getSizeExpr())
return vat;
-
+
t = vt->getElementType().getTypePtr();
}
-
+
return 0;
}
-
-/// BuildCFG - Constructs a CFG from an AST (a Stmt*). The AST can
-/// represent an arbitrary statement. Examples include a single expression
-/// or a function body (compound statement). The ownership of the returned
-/// CFG is transferred to the caller. If CFG construction fails, this method
-/// returns NULL.
+
+/// BuildCFG - Constructs a CFG from an AST (a Stmt*). The AST can represent an
+/// arbitrary statement. Examples include a single expression or a function
+/// body (compound statement). The ownership of the returned CFG is
+/// transferred to the caller. If CFG construction fails, this method returns
+/// NULL.
CFG* CFGBuilder::buildCFG(Stmt* Statement) {
assert (cfg);
if (!Statement) return NULL;
badCFG = false;
-
- // Create an empty block that will serve as the exit block for the CFG.
- // Since this is the first block added to the CFG, it will be implicitly
- // registered as the exit block.
+
+ // Create an empty block that will serve as the exit block for the CFG. Since
+ // this is the first block added to the CFG, it will be implicitly registered
+ // as the exit block.
Succ = createBlock();
assert (Succ == &cfg->getExit());
Block = NULL; // the EXIT block is empty. Create all other blocks lazily.
-
+
// Visit the statements and create the CFG.
CFGBlock* B = Visit(Statement);
if (!B) B = Succ;
-
+
if (B) {
- // Finalize the last constructed block. This usually involves
- // reversing the order of the statements in the block.
+ // Finalize the last constructed block. This usually involves reversing the
+ // order of the statements in the block.
if (Block) FinishBlock(B);
-
- // Backpatch the gotos whose label -> block mappings we didn't know
- // when we encountered them.
- for (BackpatchBlocksTy::iterator I = BackpatchBlocks.begin(),
+
+ // Backpatch the gotos whose label -> block mappings we didn't know when we
+ // encountered them.
+ for (BackpatchBlocksTy::iterator I = BackpatchBlocks.begin(),
E = BackpatchBlocks.end(); I != E; ++I ) {
-
+
CFGBlock* B = *I;
GotoStmt* G = cast<GotoStmt>(B->getTerminator());
LabelMapTy::iterator LI = LabelMap.find(G->getLabel());
@@ -208,10 +207,10 @@ CFG* CFGBuilder::buildCFG(Stmt* Statement) {
// If there is no target for the goto, then we are looking at an
// incomplete AST. Handle this by not registering a successor.
if (LI == LabelMap.end()) continue;
-
- B->addSuccessor(LI->second);
+
+ B->addSuccessor(LI->second);
}
-
+
// Add successors to the Indirect Goto Dispatch block (if we have one).
if (CFGBlock* B = cfg->getIndirectGotoBlock())
for (LabelSetTy::iterator I = AddressTakenLabels.begin(),
@@ -223,40 +222,39 @@ CFG* CFGBuilder::buildCFG(Stmt* Statement) {
// If there is no target block that contains label, then we are looking
// at an incomplete AST. Handle this by not registering a successor.
if (LI == LabelMap.end()) continue;
-
- B->addSuccessor(LI->second);
+
+ B->addSuccessor(LI->second);
}
-
+
Succ = B;
}
-
- // Create an empty entry block that has no predecessors.
+
+ // Create an empty entry block that has no predecessors.
cfg->setEntry(createBlock());
-
+
if (badCFG) {
delete cfg;
cfg = NULL;
return NULL;
}
-
- // NULL out cfg so that repeated calls to the builder will fail and that
- // the ownership of the constructed CFG is passed to the caller.
+
+ // NULL out cfg so that repeated calls to the builder will fail and that the
+ // ownership of the constructed CFG is passed to the caller.
CFG* t = cfg;
cfg = NULL;
return t;
}
-
+
/// createBlock - Used to lazily create blocks that are connected
/// to the current (global) succcessor.
-CFGBlock* CFGBuilder::createBlock(bool add_successor) {
+CFGBlock* CFGBuilder::createBlock(bool add_successor) {
CFGBlock* B = cfg->createBlock();
if (add_successor && Succ) B->addSuccessor(Succ);
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 - When the last statement has been added to the block, we must
+/// reverse the statements because they have been inserted in reverse order.
bool CFGBuilder::FinishBlock(CFGBlock* B) {
if (badCFG)
return false;
@@ -266,218 +264,214 @@ bool CFGBuilder::FinishBlock(CFGBlock* B) {
return true;
}
-/// addStmt - Used to add statements/expressions to the current CFGBlock
+/// addStmt - Used to add statements/expressions to the current CFGBlock
/// "Block". This method calls WalkAST on the passed statement to see if it
-/// contains any short-circuit expressions. If so, it recursively creates
-/// the necessary blocks for such expressions. It returns the "topmost" block
-/// of the created blocks, or the original value of "Block" when this method
-/// was called if no additional blocks are created.
+/// contains any short-circuit expressions. If so, it recursively creates the
+/// necessary blocks for such expressions. It returns the "topmost" block of
+/// the created blocks, or the original value of "Block" when this method was
+/// called if no additional blocks are created.
CFGBlock* CFGBuilder::addStmt(Stmt* Terminator) {
if (!Block) Block = createBlock();
return WalkAST(Terminator,true);
}
-/// WalkAST - Used by addStmt to walk the subtree of a statement and
-/// add extra blocks for ternary operators, &&, and ||. We also
-/// process "," and DeclStmts (which may contain nested control-flow).
+/// WalkAST - Used by addStmt to walk the subtree of a statement and add extra
+/// blocks for ternary operators, &&, and ||. We also process "," and
+/// DeclStmts (which may contain nested control-flow).
CFGBlock* CFGBuilder::WalkAST(Stmt* Terminator, bool AlwaysAddStmt = false) {
switch (Terminator->getStmtClass()) {
- case Stmt::ConditionalOperatorClass: {
- ConditionalOperator* C = cast<ConditionalOperator>(Terminator);
+ case Stmt::ConditionalOperatorClass: {
+ ConditionalOperator* C = cast<ConditionalOperator>(Terminator);
+
+ // Create the confluence block that will "merge" the results of the ternary
+ // expression.
+ CFGBlock* ConfluenceBlock = (Block) ? Block : createBlock();
+ ConfluenceBlock->appendStmt(C);
+ if (!FinishBlock(ConfluenceBlock))
+ return 0;
- // Create the confluence block that will "merge" the results
- // of the ternary expression.
- CFGBlock* ConfluenceBlock = (Block) ? Block : createBlock();
- ConfluenceBlock->appendStmt(C);
- if (!FinishBlock(ConfluenceBlock))
+ // Create a block for the LHS expression if there is an LHS expression. A
+ // GCC extension allows LHS to be NULL, causing the condition to be the
+ // value that is returned instead.
+ // e.g: x ?: y is shorthand for: x ? x : y;
+ Succ = ConfluenceBlock;
+ Block = NULL;
+ CFGBlock* LHSBlock = NULL;
+ if (C->getLHS()) {
+ LHSBlock = Visit(C->getLHS());
+ if (!FinishBlock(LHSBlock))
return 0;
-
- // Create a block for the LHS expression if there is an LHS expression.
- // A GCC extension allows LHS to be NULL, causing the condition to
- // be the value that is returned instead.
- // e.g: x ?: y is shorthand for: x ? x : y;
- Succ = ConfluenceBlock;
Block = NULL;
- CFGBlock* LHSBlock = NULL;
- if (C->getLHS()) {
- LHSBlock = Visit(C->getLHS());
- if (!FinishBlock(LHSBlock))
- return 0;
- Block = NULL;
- }
-
- // Create the block for the RHS expression.
- Succ = ConfluenceBlock;
- CFGBlock* RHSBlock = Visit(C->getRHS());
- if (!FinishBlock(RHSBlock))
- return 0;
+ }
- // Create the block that will contain the condition.
- Block = createBlock(false);
-
- if (LHSBlock)
- Block->addSuccessor(LHSBlock);
- else {
- // If we have no LHS expression, add the ConfluenceBlock as a direct
- // successor for the block containing the condition. Moreover,
- // we need to reverse the order of the predecessors in the
- // ConfluenceBlock because the RHSBlock will have been added to
- // the succcessors already, and we want the first predecessor to the
- // the block containing the expression for the case when the ternary
- // expression evaluates to true.
- Block->addSuccessor(ConfluenceBlock);
- assert (ConfluenceBlock->pred_size() == 2);
- std::reverse(ConfluenceBlock->pred_begin(),
- ConfluenceBlock->pred_end());
- }
-
- Block->addSuccessor(RHSBlock);
-
- Block->setTerminator(C);
- return addStmt(C->getCond());
+ // Create the block for the RHS expression.
+ Succ = ConfluenceBlock;
+ CFGBlock* RHSBlock = Visit(C->getRHS());
+ if (!FinishBlock(RHSBlock))
+ return 0;
+
+ // Create the block that will contain the condition.
+ Block = createBlock(false);
+
+ if (LHSBlock)
+ Block->addSuccessor(LHSBlock);
+ else {
+ // If we have no LHS expression, add the ConfluenceBlock as a direct
+ // successor for the block containing the condition. Moreover, we need to
+ // reverse the order of the predecessors in the ConfluenceBlock because
+ // the RHSBlock will have been added to the succcessors already, and we
+ // want the first predecessor to the the block containing the expression
+ // for the case when the ternary expression evaluates to true.
+ Block->addSuccessor(ConfluenceBlock);
+ assert (ConfluenceBlock->pred_size() == 2);
+ std::reverse(ConfluenceBlock->pred_begin(),
+ ConfluenceBlock->pred_end());
+ }
+
+ Block->addSuccessor(RHSBlock);
+
+ Block->setTerminator(C);
+ return addStmt(C->getCond());
+ }
+
+ case Stmt::ChooseExprClass: {
+ ChooseExpr* C = cast<ChooseExpr>(Terminator);
+
+ CFGBlock* ConfluenceBlock = Block ? Block : createBlock();
+ ConfluenceBlock->appendStmt(C);
+ if (!FinishBlock(ConfluenceBlock))
+ return 0;
+
+ Succ = ConfluenceBlock;
+ Block = NULL;
+ CFGBlock* LHSBlock = Visit(C->getLHS());
+ if (!FinishBlock(LHSBlock))
+ return 0;
+
+ Succ = ConfluenceBlock;
+ Block = NULL;
+ CFGBlock* RHSBlock = Visit(C->getRHS());
+ if (!FinishBlock(RHSBlock))
+ return 0;
+
+ Block = createBlock(false);
+ Block->addSuccessor(LHSBlock);
+ Block->addSuccessor(RHSBlock);
+ Block->setTerminator(C);
+ return addStmt(C->getCond());
+ }
+
+ case Stmt::DeclStmtClass: {
+ DeclStmt *DS = cast<DeclStmt>(Terminator);
+ if (DS->isSingleDecl()) {
+ Block->appendStmt(Terminator);
+ return WalkAST_VisitDeclSubExpr(DS->getSingleDecl());
}
-
- case Stmt::ChooseExprClass: {
- ChooseExpr* C = cast<ChooseExpr>(Terminator);
-
- CFGBlock* ConfluenceBlock = Block ? Block : createBlock();
- ConfluenceBlock->appendStmt(C);
+
+ CFGBlock* B = 0;
+
+ // FIXME: Add a reverse iterator for DeclStmt to avoid this extra copy.
+ typedef llvm::SmallVector<Decl*,10> BufTy;
+ BufTy Buf(DS->decl_begin(), DS->decl_end());
+
+ for (BufTy::reverse_iterator I=Buf.rbegin(), E=Buf.rend(); I!=E; ++I) {
+ // Get the alignment of the new DeclStmt, padding out to >=8 bytes.
+ unsigned A = llvm::AlignOf<DeclStmt>::Alignment < 8
+ ? 8 : llvm::AlignOf<DeclStmt>::Alignment;
+
+ // Allocate the DeclStmt using the BumpPtrAllocator. It will get
+ // automatically freed with the CFG.
+ DeclGroupRef DG(*I);
+ Decl* D = *I;
+ void* Mem = cfg->getAllocator().Allocate(sizeof(DeclStmt), A);
+
+ DeclStmt* DS = new (Mem) DeclStmt(DG, D->getLocation(), GetEndLoc(D));
+
+ // Append the fake DeclStmt to block.
+ Block->appendStmt(DS);
+ B = WalkAST_VisitDeclSubExpr(D);
+ }
+ return B;
+ }
+
+ case Stmt::AddrLabelExprClass: {
+ AddrLabelExpr* A = cast<AddrLabelExpr>(Terminator);
+ AddressTakenLabels.insert(A->getLabel());
+
+ if (AlwaysAddStmt) Block->appendStmt(Terminator);
+ return Block;
+ }
+
+ case Stmt::StmtExprClass:
+ return WalkAST_VisitStmtExpr(cast<StmtExpr>(Terminator));
+
+ case Stmt::SizeOfAlignOfExprClass: {
+ SizeOfAlignOfExpr* E = cast<SizeOfAlignOfExpr>(Terminator);
+
+ // VLA types have expressions that must be evaluated.
+ if (E->isArgumentType()) {
+ for (VariableArrayType* VA = FindVA(E->getArgumentType().getTypePtr());
+ VA != 0; VA = FindVA(VA->getElementType().getTypePtr()))
+ addStmt(VA->getSizeExpr());
+ }
+ // Expressions in sizeof/alignof are not evaluated and thus have no
+ // control flow.
+ else
+ Block->appendStmt(Terminator);
+
+ return Block;
+ }
+
+ case Stmt::BinaryOperatorClass: {
+ BinaryOperator* B = cast<BinaryOperator>(Terminator);
+
+ if (B->isLogicalOp()) { // && or ||
+ CFGBlock* ConfluenceBlock = (Block) ? Block : createBlock();
+ ConfluenceBlock->appendStmt(B);
if (!FinishBlock(ConfluenceBlock))
return 0;
-
- Succ = ConfluenceBlock;
- Block = NULL;
- CFGBlock* LHSBlock = Visit(C->getLHS());
- if (!FinishBlock(LHSBlock))
- return 0;
+ // create the block evaluating the LHS
+ CFGBlock* LHSBlock = createBlock(false);
+ LHSBlock->setTerminator(B);
+
+ // create the block evaluating the RHS
Succ = ConfluenceBlock;
Block = NULL;
- CFGBlock* RHSBlock = Visit(C->getRHS());
+ CFGBlock* RHSBlock = Visit(B->getRHS());
if (!FinishBlock(RHSBlock))
return 0;
-
- Block = createBlock(false);
- Block->addSuccessor(LHSBlock);
- Block->addSuccessor(RHSBlock);
- Block->setTerminator(C);
- return addStmt(C->getCond());
- }
- case Stmt::DeclStmtClass: {
- DeclStmt *DS = cast<DeclStmt>(Terminator);
- if (DS->isSingleDecl()) {
- Block->appendStmt(Terminator);
- return WalkAST_VisitDeclSubExpr(DS->getSingleDecl());
+ // Now link the LHSBlock with RHSBlock.
+ if (B->getOpcode() == BinaryOperator::LOr) {
+ LHSBlock->addSuccessor(ConfluenceBlock);
+ LHSBlock->addSuccessor(RHSBlock);
+ } else {
+ assert (B->getOpcode() == BinaryOperator::LAnd);
+ LHSBlock->addSuccessor(RHSBlock);
+ LHSBlock->addSuccessor(ConfluenceBlock);
}
-
- CFGBlock* B = 0;
-
- // FIXME: Add a reverse iterator for DeclStmt to avoid this
- // extra copy.
- typedef llvm::SmallVector<Decl*,10> BufTy;
- BufTy Buf(DS->decl_begin(), DS->decl_end());
-
- for (BufTy::reverse_iterator I=Buf.rbegin(), E=Buf.rend(); I!=E; ++I) {
- // Get the alignment of the new DeclStmt, padding out to >=8 bytes.
- unsigned A = llvm::AlignOf<DeclStmt>::Alignment < 8
- ? 8 : llvm::AlignOf<DeclStmt>::Alignment;
-
- // Allocate the DeclStmt using the BumpPtrAllocator. It will
- // get automatically freed with the CFG.
- DeclGroupRef DG(*I);
- Decl* D = *I;
- void* Mem = cfg->getAllocator().Allocate(sizeof(DeclStmt), A);
-
- DeclStmt* DS = new (Mem) DeclStmt(DG, D->getLocation(), GetEndLoc(D));
-
- // Append the fake DeclStmt to block.
- Block->appendStmt(DS);
- B = WalkAST_VisitDeclSubExpr(D);
- }
- return B;
- }
- case Stmt::AddrLabelExprClass: {
- AddrLabelExpr* A = cast<AddrLabelExpr>(Terminator);
- AddressTakenLabels.insert(A->getLabel());
-
- if (AlwaysAddStmt) Block->appendStmt(Terminator);
- return Block;
+ // Generate the blocks for evaluating the LHS.
+ Block = LHSBlock;
+ return addStmt(B->getLHS());
+ } else if (B->getOpcode() == BinaryOperator::Comma) { // ,
+ Block->appendStmt(B);
+ addStmt(B->getRHS());
+ return addStmt(B->getLHS());
}
-
- case Stmt::StmtExprClass:
- return WalkAST_VisitStmtExpr(cast<StmtExpr>(Terminator));
-
- case Stmt::SizeOfAlignOfExprClass: {
- SizeOfAlignOfExpr* E = cast<SizeOfAlignOfExpr>(Terminator);
-
- // VLA types have expressions that must be evaluated.
- if (E->isArgumentType()) {
- for (VariableArrayType* VA = FindVA(E->getArgumentType().getTypePtr());
- VA != 0; VA = FindVA(VA->getElementType().getTypePtr()))
- addStmt(VA->getSizeExpr());
- }
- // Expressions in sizeof/alignof are not evaluated and thus have no
- // control flow.
- else
- Block->appendStmt(Terminator);
- return Block;
- }
-
- case Stmt::BinaryOperatorClass: {
- BinaryOperator* B = cast<BinaryOperator>(Terminator);
-
- if (B->isLogicalOp()) { // && or ||
- CFGBlock* ConfluenceBlock = (Block) ? Block : createBlock();
- ConfluenceBlock->appendStmt(B);
- if (!FinishBlock(ConfluenceBlock))
- return 0;
-
- // create the block evaluating the LHS
- CFGBlock* LHSBlock = createBlock(false);
- LHSBlock->setTerminator(B);
-
- // create the block evaluating the RHS
- Succ = ConfluenceBlock;
- Block = NULL;
- CFGBlock* RHSBlock = Visit(B->getRHS());
- if (!FinishBlock(RHSBlock))
- return 0;
-
- // Now link the LHSBlock with RHSBlock.
- if (B->getOpcode() == BinaryOperator::LOr) {
- LHSBlock->addSuccessor(ConfluenceBlock);
- LHSBlock->addSuccessor(RHSBlock);
- }
- else {
- assert (B->getOpcode() == BinaryOperator::LAnd);
- LHSBlock->addSuccessor(RHSBlock);
- LHSBlock->addSuccessor(ConfluenceBlock);
- }
-
- // Generate the blocks for evaluating the LHS.
- Block = LHSBlock;
- return addStmt(B->getLHS());
- }
- else if (B->getOpcode() == BinaryOperator::Comma) { // ,
- Block->appendStmt(B);
- addStmt(B->getRHS());
- return addStmt(B->getLHS());
- }
-
- break;
- }
-
+ break;
+ }
+
// Blocks: No support for blocks ... yet
- case Stmt::BlockExprClass:
- case Stmt::BlockDeclRefExprClass:
- return NYS();
-
- case Stmt::ParenExprClass:
- return WalkAST(cast<ParenExpr>(Terminator)->getSubExpr(), AlwaysAddStmt);
-
+ case Stmt::BlockExprClass:
+ case Stmt::BlockDeclRefExprClass:
+ return NYS();
+
+ case Stmt::ParenExprClass:
+ return WalkAST(cast<ParenExpr>(Terminator)->getSubExpr(), AlwaysAddStmt);
+
case Stmt::CallExprClass: {
bool NoReturn = false;
CallExpr *C = cast<CallExpr>(Terminator);
@@ -508,24 +502,24 @@ CFGBlock* CFGBuilder::WalkAST(Stmt* Terminator, bool AlwaysAddStmt = false) {
return WalkAST_VisitChildren(Terminator);
}
- default:
- break;
+ default:
+ break;
};
-
+
if (AlwaysAddStmt) Block->appendStmt(Terminator);
return WalkAST_VisitChildren(Terminator);
}
-
-/// WalkAST_VisitDeclSubExpr - Utility method to add block-level expressions
-/// for initializers in Decls.
+
+/// WalkAST_VisitDeclSubExpr - Utility method to add block-level expressions for
+/// initializers in Decls.
CFGBlock* CFGBuilder::WalkAST_VisitDeclSubExpr(Decl* D) {
VarDecl* VD = dyn_cast<VarDecl>(D);
if (!VD)
return Block;
-
+
Expr* Init = VD->getInit();
-
+
if (Init) {
// Optimization: Don't create separate block-level statements for literals.
switch (Init->getStmtClass()) {
@@ -537,24 +531,24 @@ CFGBlock* CFGBuilder::WalkAST_VisitDeclSubExpr(Decl* D) {
Block = addStmt(Init);
}
}
-
+
// If the type of VD is a VLA, then we must process its size expressions.
for (VariableArrayType* VA = FindVA(VD->getType().getTypePtr()); VA != 0;
VA = FindVA(VA->getElementType().getTypePtr()))
- Block = addStmt(VA->getSizeExpr());
-
+ Block = addStmt(VA->getSizeExpr());
+
return Block;
}
-/// WalkAST_VisitChildren - Utility method to call WalkAST on the
-/// children of a Stmt.
+/// WalkAST_VisitChildren - Utility method to call WalkAST on the children of a
+/// Stmt.
CFGBlock* CFGBuilder::WalkAST_VisitChildren(Stmt* Terminator) {
CFGBlock* B = Block;
for (Stmt::child_iterator I = Terminator->child_begin(),
E = Terminator->child_end();
I != E; ++I)
if (*I) B = WalkAST(*I);
-
+
return B;
}
@@ -562,19 +556,19 @@ CFGBlock* CFGBuilder::WalkAST_VisitChildren(Stmt* Terminator) {
/// expressions (a GCC extension).
CFGBlock* CFGBuilder::WalkAST_VisitStmtExpr(StmtExpr* Terminator) {
Block->appendStmt(Terminator);
- return VisitCompoundStmt(Terminator->getSubStmt());
+ return VisitCompoundStmt(Terminator->getSubStmt());
}
/// VisitStmt - Handle statements with no branching control flow.
CFGBlock* CFGBuilder::VisitStmt(Stmt* Statement) {
- // We cannot assume that we are in the middle of a basic block, since
- // the CFG might only be constructed for this single statement. If
- // we have no current basic block, just create one lazily.
+ // We cannot assume that we are in the middle of a basic block, since the CFG
+ // might only be constructed for this single statement. If we have no current
+ // basic block, just create one lazily.
if (!Block) Block = createBlock();
-
- // Simply add the statement to the current block. We actually
- // insert statements in reverse order; this order is reversed later
- // when processing the containing element in the AST.
+
+ // Simply add the statement to the current block. We actually insert
+ // statements in reverse order; this order is reversed later when processing
+ // the containing element in the AST.
addStmt(Statement);
return Block;
@@ -585,7 +579,7 @@ CFGBlock* CFGBuilder::VisitNullStmt(NullStmt* Statement) {
}
CFGBlock* CFGBuilder::VisitCompoundStmt(CompoundStmt* C) {
-
+
CFGBlock* LastBlock = Block;
for (CompoundStmt::reverse_body_iterator I=C->body_rbegin(), E=C->body_rend();
@@ -597,35 +591,35 @@ CFGBlock* CFGBuilder::VisitCompoundStmt(CompoundStmt* C) {
}
CFGBlock* CFGBuilder::VisitIfStmt(IfStmt* I) {
- // We may see an if statement in the middle of a basic block, or
- // it may be the 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.
-
- // The block we were proccessing is now finished. Make it the
- // successor block.
- if (Block) {
+ // We may see an if statement in the middle of a basic block, or it may be the
+ // 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.
+
+ // The block we were proccessing is now finished. Make it the successor
+ // block.
+ if (Block) {
Succ = Block;
if (!FinishBlock(Block))
return 0;
}
-
- // Process the false branch. NULL out Block so that the recursive
- // call to Visit will create a new basic block.
+
+ // Process the false branch. NULL out Block so that the recursive call to
+ // Visit will create a new basic block.
// Null out Block so that all successor
CFGBlock* ElseBlock = Succ;
-
+
if (Stmt* Else = I->getElse()) {
SaveAndRestore<CFGBlock*> sv(Succ);
-
+
// NULL out Block so that the recursive call to Visit will
- // create a new basic block.
+ // create a new basic block.
Block = NULL;
ElseBlock = Visit(Else);
-
+
if (!ElseBlock) // Can occur when the Else body has all NullStmts.
ElseBlock = sv.get();
else if (Block) {
@@ -633,67 +627,65 @@ CFGBlock* CFGBuilder::VisitIfStmt(IfStmt* I) {
return 0;
}
}
-
- // Process the true branch. NULL out Block so that the recursive
- // call to Visit will create a new basic block.
+
+ // Process the true branch. NULL out Block so that the recursive call to
+ // Visit will create a new basic block.
// Null out Block so that all successor
CFGBlock* ThenBlock;
{
Stmt* Then = I->getThen();
assert (Then);
SaveAndRestore<CFGBlock*> sv(Succ);
- Block = NULL;
+ Block = NULL;
ThenBlock = Visit(Then);
-
+
if (!ThenBlock) {
// We can reach here if the "then" body has all NullStmts.
// Create an empty block so we can distinguish between true and false
// branches in path-sensitive analyses.
ThenBlock = createBlock(false);
ThenBlock->addSuccessor(sv.get());
- }
- else if (Block) {
+ } else if (Block) {
if (!FinishBlock(ThenBlock))
return 0;
- }
+ }
}
- // Now create a new block containing the if statement.
+ // Now create a new block containing the if statement.
Block = createBlock(false);
-
+
// Set the terminator of the new block to the If statement.
Block->setTerminator(I);
-
+
// Now add the successors.
Block->addSuccessor(ThenBlock);
Block->addSuccessor(ElseBlock);
-
- // Add the condition as the last statement in the new block. This
- // may create new blocks as the condition may contain control-flow. Any
- // newly created blocks will be pointed to be "Block".
+
+ // Add the condition as the last statement in the new block. This may create
+ // new blocks as the condition may contain control-flow. Any newly created
+ // blocks will be pointed to be "Block".
return addStmt(I->getCond()->IgnoreParens());
}
-
-
+
+
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 and
+ // reverse its statements.
//
- // 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.
+ // 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);
// Create the new block.
Block = createBlock(false);
-
+
// The Exit block is the only successor.
Block->addSuccessor(&cfg->getExit());
-
- // Add the return statement to the block. This may create new blocks
- // if R contains control-flow (short-circuit operations).
+
+ // Add the return statement to the block. This may create new blocks if R
+ // contains control-flow (short-circuit operations).
return addStmt(R);
}
@@ -701,75 +693,72 @@ CFGBlock* CFGBuilder::VisitLabelStmt(LabelStmt* L) {
// Get the block of the labeled statement. Add it to our map.
Visit(L->getSubStmt());
CFGBlock* LabelBlock = Block;
-
+
if (!LabelBlock) // This can happen when the body is empty, i.e.
LabelBlock=createBlock(); // scopes that only contains NullStmts.
-
+
assert (LabelMap.find(L) == LabelMap.end() && "label already in map");
LabelMap[ L ] = LabelBlock;
-
- // Labels partition blocks, so this is the end of the basic block
- // we were processing (L is the block's label). Because this is
- // label (and we have already processed the substatement) there is no
- // extra control-flow to worry about.
+
+ // Labels partition blocks, so this is the end of the basic block we were
+ // processing (L is the block's label). Because this is label (and we have
+ // already processed the substatement) there is no extra control-flow to worry
+ // about.
LabelBlock->setLabel(L);
if (!FinishBlock(LabelBlock))
return 0;
-
- // We set Block to NULL to allow lazy creation of a new block
- // (if necessary);
+
+ // We set Block to NULL to allow lazy creation of a new block (if necessary);
Block = NULL;
-
+
// This block is now the implicit successor of other blocks.
Succ = LabelBlock;
-
+
return LabelBlock;
}
CFGBlock* CFGBuilder::VisitGotoStmt(GotoStmt* G) {
- // Goto is a control-flow statement. Thus we stop processing the
- // current block and create a new one.
+ // Goto is a control-flow statement. Thus we stop processing the current
+ // block and create a new one.
if (Block) FinishBlock(Block);
Block = createBlock(false);
Block->setTerminator(G);
-
- // If we already know the mapping to the label block add the
- // successor now.
+
+ // If we already know the mapping to the label block add the successor now.
LabelMapTy::iterator I = LabelMap.find(G->getLabel());
-
+
if (I == LabelMap.end())
// We will need to backpatch this block later.
BackpatchBlocks.push_back(Block);
else
Block->addSuccessor(I->second);
- return Block;
+ return Block;
}
CFGBlock* CFGBuilder::VisitForStmt(ForStmt* F) {
- // "for" is a control-flow statement. Thus we stop processing the
- // current block.
-
+ // "for" is a control-flow statement. Thus we stop processing the current
+ // block.
+
CFGBlock* LoopSucce