diff options
Diffstat (limited to 'lib/Analysis/CFG.cpp')
| -rw-r--r-- | lib/Analysis/CFG.cpp | 1924 |
1 files changed, 1924 insertions, 0 deletions
diff --git a/lib/Analysis/CFG.cpp b/lib/Analysis/CFG.cpp new file mode 100644 index 0000000000..d423716c20 --- /dev/null +++ b/lib/Analysis/CFG.cpp @@ -0,0 +1,1924 @@ +//===--- CFG.cpp - Classes for representing and building CFGs----*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines the CFG and CFGBuilder classes for representing and +// building Control-Flow Graphs (CFGs) from ASTs. +// +//===----------------------------------------------------------------------===// + +#include "clang/Analysis/CFG.h" +#include "clang/AST/StmtVisitor.h" +#include "clang/AST/PrettyPrinter.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/Support/GraphWriter.h" +#include "llvm/Support/Streams.h" +#include "llvm/Support/Compiler.h" +#include <llvm/Support/Allocator.h> +#include <llvm/Support/Format.h> + +using namespace clang; + +namespace { + +// SaveAndRestore - A utility class that uses RIIA to save and restore +// the value of a variable. +template<typename T> +struct VISIBILITY_HIDDEN SaveAndRestore { + SaveAndRestore(T& x) : X(x), old_value(x) {} + ~SaveAndRestore() { X = old_value; } + T get() { return old_value; } + + 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(); +} + +/// 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. +/// +/// Example usage: +/// +/// 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. +/// +class VISIBILITY_HIDDEN CFGBuilder : public StmtVisitor<CFGBuilder,CFGBlock*> { + CFG* cfg; + CFGBlock* Block; + CFGBlock* Succ; + CFGBlock* ContinueTargetBlock; + 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. + 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: + explicit CFGBuilder() : cfg(NULL), Block(NULL), Succ(NULL), + ContinueTargetBlock(NULL), BreakTargetBlock(NULL), + SwitchTerminatedBlock(NULL), DefaultCaseBlock(NULL) { + // Create an empty 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! + + CFGBlock* VisitBreakStmt(BreakStmt* B); + CFGBlock* VisitCaseStmt(CaseStmt* Terminator); + CFGBlock* VisitCompoundStmt(CompoundStmt* C); + CFGBlock* VisitContinueStmt(ContinueStmt* C); + CFGBlock* VisitDefaultStmt(DefaultStmt* D); + CFGBlock* VisitDoStmt(DoStmt* D); + CFGBlock* VisitForStmt(ForStmt* F); + CFGBlock* VisitGotoStmt(GotoStmt* G); + CFGBlock* VisitIfStmt(IfStmt* I); + CFGBlock* VisitIndirectGotoStmt(IndirectGotoStmt* I); + CFGBlock* VisitLabelStmt(LabelStmt* L); + CFGBlock* VisitNullStmt(NullStmt* Statement); + CFGBlock* VisitObjCForCollectionStmt(ObjCForCollectionStmt* S); + CFGBlock* VisitReturnStmt(ReturnStmt* R); + CFGBlock* VisitStmt(Stmt* Statement); + CFGBlock* VisitSwitchStmt(SwitchStmt* Terminator); + CFGBlock* VisitWhileStmt(WhileStmt* W); + + // FIXME: Add support for ObjC-specific control-flow structures. + + // NYS == Not Yet Supported + CFGBlock* NYS() { + 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. + return Block; + } + + // 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(); } + +private: + CFGBlock* createBlock(bool add_successor = true); + CFGBlock* addStmt(Stmt* Terminator); + CFGBlock* WalkAST(Stmt* Terminator, bool AlwaysAddStmt); + CFGBlock* WalkAST_VisitChildren(Stmt* Terminator); + 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) { + while (ArrayType* vt = dyn_cast<ArrayType>(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. +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. + 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. + 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(), + E = BackpatchBlocks.end(); I != E; ++I ) { + + CFGBlock* B = *I; + GotoStmt* G = cast<GotoStmt>(B->getTerminator()); + LabelMapTy::iterator LI = LabelMap.find(G->getLabel()); + + // 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); + } + + // Add successors to the Indirect Goto Dispatch block (if we have one). + if (CFGBlock* B = cfg->getIndirectGotoBlock()) + for (LabelSetTy::iterator I = AddressTakenLabels.begin(), + E = AddressTakenLabels.end(); I != E; ++I ) { + + // Lookup the target block. + LabelMapTy::iterator LI = LabelMap.find(*I); + + // 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); + } + + Succ = B; + } + + // 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. + 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* 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. +bool CFGBuilder::FinishBlock(CFGBlock* B) { + if (badCFG) + return false; + + assert (B); + B->reverseStmts(); + return true; +} + +/// 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. +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). +CFGBlock* CFGBuilder::WalkAST(Stmt* Terminator, bool AlwaysAddStmt = false) { + switch (Terminator->getStmtClass()) { + 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 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()); + } + + 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()); + } + + 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; + + // 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; + } + + // Blocks: No support for blocks ... yet + case Stmt::BlockExprClass: + case Stmt::BlockDeclRefExprClass: + return NYS(); + + case Stmt::ParenExprClass: + return WalkAST(cast<ParenExpr>(Terminator)->getSubExpr(), AlwaysAddStmt); + + default: + break; + }; + + if (AlwaysAddStmt) Block->appendStmt(Terminator); + return WalkAST_VisitChildren(Terminator); +} + +/// 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()) { + case Stmt::IntegerLiteralClass: + case Stmt::CharacterLiteralClass: + case Stmt::StringLiteralClass: + break; + default: + 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()); + + return Block; +} + +/// 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; +} + +/// WalkAST_VisitStmtExpr - Utility method to handle (nested) statement +/// expressions (a GCC extension). +CFGBlock* CFGBuilder::WalkAST_VisitStmtExpr(StmtExpr* Terminator) { + Block->appendStmt(Terminator); + 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. + 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. + addStmt(Statement); + + return Block; +} + +CFGBlock* CFGBuilder::VisitNullStmt(NullStmt* Statement) { + return Block; +} + +CFGBlock* CFGBuilder::VisitCompoundStmt(CompoundStmt* C) { + + CFGBlock* LastBlock = Block; + + for (CompoundStmt::reverse_body_iterator I=C->body_rbegin(), E=C->body_rend(); + I != E; ++I ) { + LastBlock = Visit(*I); + } + + return LastBlock; +} + +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) { + 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. + // 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. + Block = NULL; + ElseBlock = Visit(Else); + + if (!ElseBlock) // Can occur when the Else body has all NullStmts. + ElseBlock = sv.get(); + else if (Block) { + if (!FinishBlock(ElseBlock)) + return 0; + } + } + + // 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; + 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) { + if (!FinishBlock(ThenBlock)) + return 0; + } + } + + // 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". + 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. + // + // 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). + return addStmt(R); +} + +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. + LabelBlock->setLabel(L); + if (!FinishBlock(LabelBlock)) + return 0; + + // 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. + if (Block) FinishBlock(Block); + Block = createBlock(false); + Block->setTerminator(G); + + // 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; +} + +CFGBlock* CFGBuilder::VisitForStmt(ForStmt* F) { + // "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. + 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. + if (Stmt* C = F->getCond()) { + Block = ExitConditionBlock; + EntryConditionBlock = addStmt(C); + if (Block) { + if (!FinishBlock(EntryConditionBlock)) + return 0; + } + } + + // The condition block is the implicit successor for the loop body as + // well as any code above the loop. + Succ = EntryConditionBlock; + + // Now create the loop body. + { + assert (F->getBody()); + + // Save the current values for Block, Succ, and continue and break targets + SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ), + save_continue(ContinueTargetBlock), + save_break(BreakTargetBlock); + + // Create a new block to contain the (bottom) of the loop body. + Block = NULL; + + if (Stmt* I = F->getInc()) { + // Generate increment code in its own basic block. This is the target + // of continue statements. + Succ = Visit(I); + } + else { + // No increment code. Create a special, empty, block that is used as + // the target block for "looping back" to the start of the loop. + assert(Succ == EntryConditionBlock); + Succ = createBlock(); + } + + // Finish up the increment (or empty) block if it hasn't been already. + if (Block) { + assert(Block == Succ); + if (!FinishBlock(Block)) + return 0; + Block = 0; + } + + ContinueTargetBlock = Succ; + + // The starting block for the loop increment is the block that should + // represent the 'loop target' for looping back to the start of the loop. + ContinueTargetBlock->setLoopTarget(F); + + // All breaks should go to the code following the loop. + BreakTargetBlock = LoopSuccessor; + + // Now populate the body block, and in the process create new blocks + // as we walk the body of the loop. + CFGBlock* BodyBlock = Visit(F->getBody()); + + if (!BodyBlock) + BodyBlock = EntryConditionBlock; // can happen for "for (...;...; ) ;" + else if (Block) { + if (!FinishBlock(BodyBlock)) + return 0; + } + + // This new body block is a successor to our "exit" condition block. + ExitConditionBlock->addSuccessor(BodyBlock); + } + + // Link up the condition block with the code that follows the loop. + // (the false branch). + ExitConditionBlock->addSuccessor(LoopSuccessor); + + // If the loop contains initialization, create a new block for those + // statements. This block can also contain statements that precede + // the loop. + if (Stmt* I = F->getInit()) { + Block = createBlock(); + return addStmt(I); + } + else { + // There is no loop initialization. We are thus basically a while + // loop. NULL out Block to force lazy block construction. + Block = NULL; + Succ = EntryConditionBlock; + return EntryConditionBlock; + } +} + +CFGBlock* CFGBuilder::VisitObjCForCollectionStmt(ObjCForCollectionStmt* S) { + // Objective-C fast enumeration 'for' statements: + // http://developer.apple.com/documentation/Cocoa/Conceptual/ObjectiveC + // + // for ( Type newVariable in collection_expression ) { statements } + // + // becomes: + // + // prologue: + // 1. collection_expression + // T. jump to loop_entry + // loop_entry: + // 1. side-effects of element expression + // 1. ObjCForCollectionStmt [performs binding to newVariable] + // T. ObjCForCollectionStmt TB, FB [jumps to TB if newVariable != nil] + // TB: + // statements + // T. jump to loop_entry + // FB: + // what comes after + // + // and + // + // Type existingItem; + // for ( existingItem in expression ) { statements } + // + // becomes: + // + // the same with newVariable replaced with existingItem; the binding + // works the same except that for one ObjCForCollectionStmt::getElement() + // returns a DeclStmt and the other returns a DeclRefExpr. + // + + CFGBlock* LoopSuccessor = 0; + + if (Block) { + if (!FinishBlock(Block)) + return 0; + LoopSuccessor = Block; + Block = 0; + } + else LoopSuccessor = Succ; + + // Build the condition blocks. + CFGBlock* ExitConditionBlock = createBlock(false); + CFGBlock* EntryConditionBlock = ExitConditionBlock; + + // Set the terminator for the "exit" condition block. + ExitConditionBlock->setTerminator(S); + + // The last statement in the block should be the ObjCForCollectionStmt, + // which performs the actual binding to 'element' and determines if there + // are any more items in the collection. + ExitConditionBlock->appendStmt(S); + Block = ExitConditionBlock; + + // Walk the 'element' expression to see if there are any side-effects. We + // generate new blocks as necesary. We DON'T add the statement by default + // to the CFG unless it contains control-flow. + EntryConditionBlock = WalkAST(S->getElement(), false); + if (Block) { + if (!FinishBlock(EntryConditionBlock)) + return 0; + Block = 0; + } + + // The condition block is the implicit successor for the loop body as + // well as any code above the loop. + Succ = EntryConditionBlock; + + // Now create the true branch. + { + // Save the current values for Succ, continue and break targets. + SaveAndRestore<CFGBlock*> save_Succ(Succ), + save_continue(ContinueTargetBlock), save_break(BreakTargetBlock); + + BreakTargetBlock = LoopSuccessor; + ContinueTargetBlock = EntryConditionBlock; + + CFGBlock* BodyBlock = Visit(S->getBody()); + + if (!BodyBlock) + BodyBlock = EntryConditionBlock; // can happen for "for (X in Y) ;" + else if (Block) { + if (!FinishBlock(BodyBlock)) + return 0; + } + + // This new body block is a successor to our "exit" condition block. + ExitConditionBlock->addSuccessor(BodyBlock); + } + + // Link up the condition block with the code that follows the loop. + // (the false branch). + ExitConditionBlock->addSuccessor(LoopSuccessor); + + // Now create a prologue block to contain the collection expression. + Block = createBlock(); + return addStmt(S->getCollection()); +} + +CFGBlock* CFGBuilder::VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt* S) { + // FIXME: Add locking 'primitives' to CFG for @synchronized. + + // Inline the body. + CFGBlock *SyncBlock = Visit(S->getSynchBody()); + + // The sync body starts its own basic block. This makes it a little easier + // for diagnostic clients. + if (SyncBlock) { + if (!FinishBlock(SyncBlock)) + return 0; + + Block = 0; + } + + Succ = SyncBlock; + + // Inline the sync expression. + return Visit(S->getSynchExpr()); +} + +CFGBlock* CFGBuilder::VisitObjCAtTryStmt(ObjCAtTryStmt* S) { + return NYS(); +} + +CFGBlock* CFGBuilder::VisitWhileStmt(WhileStmt* W) { + // "while" 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. + CFGBlock* ExitConditionBlock = createBlock(false); + CFGBlock* EntryConditionBlock = ExitConditionBlock; + + // Set the terminator for the "exit" condition block. + ExitConditionBlock->setTerminator(W); + + // Now add the actual condition to the condition block. Because the + // condition itself may contain control-flow, new blocks may be created. + // Thus we update "Succ" after adding the condition. + if (Stmt* C = W->getCond()) { + Block = ExitConditionBlock; + EntryConditionBlock = addStmt(C); + assert(Block == EntryConditionBlock); + if (Block) { + if (!FinishBlock(EntryConditionBlock)) + return 0; + } + } + + // The condition block is the implicit successor for the loop body as + // well as any code above the loop. + Succ = EntryConditionBlock; + + // Process the loop body. + { + assert(W->getBody()); + + // Save the current values for Block, Succ, and continue and break targets + SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ), + save_continue(ContinueTargetBlock), + save_break(BreakTargetBlock); + + // Create an empty block to represent the transition block for looping + // back to the head of the loop. + Block = 0; + assert(Succ == EntryConditionBlock); + Succ = createBlock(); + Succ->setLoopTarget(W); + ContinueTargetBlock = Succ; + + // All breaks should go to the code following the loop. + BreakTargetBlock = LoopSuccessor; + + // NULL out Block to force lazy instantiation of blocks for the body. + Block = NULL; + + // Create the body. The returned block is the entry to the loop body. + CFGBlock* BodyBlock = Visit(W->getBody()); + + if (!BodyBlock) + BodyBlock = EntryConditionBlock; // can happen for "while(...) ;" + else if (Block) { + if (!FinishBlock(BodyBlock)) + return 0; + } + + // Add the loop body entry as a successor to the condition. + ExitConditionBlock->addSuccessor(BodyBlock); + } + + // Link up the condition block with the code that follows the loop. + // (the false branch). + ExitConditionBlock->addSuccessor(LoopSuccessor); + + // There can be no more statements in the condition block + // since we loop back to this block. NULL out Block to force + // lazy creation of another block. + Block = NULL; + + // Return the condition block, which is the dominating block for the loop. + Succ = EntryConditionBlock; + return EntryConditionBlock; +} + +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 (Block) { + if (!FinishBlock(Block)) + return 0; + } + + // Create the new block. |