diff options
Diffstat (limited to 'lib/Analysis')
| -rw-r--r-- | lib/Analysis/CFG.cpp | 1357 |
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* LoopSuccessor = NULL; - + if (Block) { if (!FinishBlock(Block)) return 0; LoopSuccessor = Block; - } - else LoopSuccessor = Succ; - - // Because of short-circuit evaluation, the condition of the loop - // can span multiple basic blocks. Thus we need the "Entry" and "Exit" - // blocks that evaluate the condition. + } else LoopSuccessor = Succ; + + // Because of short-circuit evaluation, the condition of the loop can span + // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that + // evaluate the condition. CFGBlock* ExitConditionBlock = createBlock(false); CFGBlock* EntryConditionBlock = ExitConditionBlock; - + // Set the terminator for the "exit" condition block. - ExitConditionBlock->setTerminator(F); - - // Now add the actual condition to the condition block. Because the - // condition itself may contain control-flow, new blocks may be created. + ExitConditionBlock->setTerminator(F); + + // Now add the actual condition to the condition block. Because the condition + // itself may contain control-flow, new blocks may be created. if (Stmt* C = F->getCond()) { Block = ExitConditionBlock; Entry |