From 19bb356317952445b03ee341c02f6147083c9eea Mon Sep 17 00:00:00 2001 From: Ted Kremenek Date: Tue, 28 Aug 2007 19:26:49 +0000 Subject: [PATCH] Added support for indirect-gotos (GCC extension) in source-level CFGs. This involves the construction of a specialized "dispatch" block that all basic blocks containing indirect gotos unconditionally transfer control-flow to. The successors of the dispatch block has as its successors all of the blocks containing labels whose address was taken somewhere in the function. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@41554 91177308-0d34-0410-b5e6-96231b3b80d8 --- AST/CFG.cpp | 67 ++++++++++++++++++++++++++++++++++++++--- include/clang/AST/CFG.h | 32 +++++++++++--------- 2 files changed, 81 insertions(+), 18 deletions(-) diff --git a/AST/CFG.cpp b/AST/CFG.cpp index fb50462660..79195a3850 100644 --- a/AST/CFG.cpp +++ b/AST/CFG.cpp @@ -16,6 +16,7 @@ #include "clang/AST/Expr.h" #include "clang/AST/StmtVisitor.h" #include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SmallPtrSet.h" #include #include #include @@ -58,12 +59,19 @@ class CFGBuilder : public StmtVisitor { CFGBlock* SwitchTerminatedBlock; unsigned NumBlocks; + // LabelMap records the mapping from Label expressions to their blocks. typedef llvm::DenseMap 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 BackpatchBlocksTy; BackpatchBlocksTy BackpatchBlocks; + // A list of labels whose address has been taken (for indirect gotos). + typedef llvm::SmallPtrSet LabelSetTy; + LabelSetTy AddressTakenLabels; + public: explicit CFGBuilder() : cfg(NULL), Block(NULL), Succ(NULL), ContinueTargetBlock(NULL), BreakTargetBlock(NULL), @@ -95,6 +103,7 @@ public: CFGBlock* VisitBreakStmt(BreakStmt* B); CFGBlock* VisitSwitchStmt(SwitchStmt* S); CFGBlock* VisitSwitchCase(SwitchCase* S); + CFGBlock* VisitIndirectGotoStmt(IndirectGotoStmt* I); private: CFGBlock* createBlock(bool add_successor = true); @@ -113,6 +122,7 @@ private: /// 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; // Create an empty block that will serve as the exit block for the CFG. @@ -142,16 +152,32 @@ CFG* CFGBuilder::buildCFG(Stmt* Statement) { 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); + } + + // Create an empty entry block that has no predecessors. if (B->pred_size() > 0) { - // create an empty entry block that has no predecessors. Succ = B; cfg->setEntry(createBlock()); } else cfg->setEntry(B); - // NULL out cfg so that repeated calls + // 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; @@ -220,6 +246,14 @@ CFGBlock* CFGBuilder::WalkAST(Stmt* S, bool AlwaysAddStmt = false) { } else return Block; + case Stmt::AddrLabelExprClass: { + AddrLabelExpr* A = cast(S); + AddressTakenLabels.insert(A->getLabel()); + + if (AlwaysAddStmt) Block->appendStmt(S); + return Block; + } + case Stmt::StmtExprClass: return WalkAST_VisitStmtExpr(cast(S)); @@ -788,6 +822,25 @@ CFGBlock* CFGBuilder::VisitSwitchCase(SwitchCase* S) { return CaseBlock; } +CFGBlock* CFGBuilder::VisitIndirectGotoStmt(IndirectGotoStmt* I) { + // Lazily create the indirect-goto dispatch block if there isn't one + // already. + CFGBlock* IBlock = cfg->getIndirectGotoBlock(); + + if (!IBlock) { + IBlock = createBlock(false); + cfg->setIndirectGotoBlock(IBlock); + } + + // IndirectGoto 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(I); + Block->addSuccessor(IBlock); + return addStmt(I->getTarget()); +} + } // end anonymous namespace @@ -835,7 +888,13 @@ void CFG::print(std::ostream& OS) { // Skip the entry block, because we already printed it. if (&(*I) == &getEntry() || &(*I) == &getExit()) continue; - OS << "\n [ B" << I->getBlockID() << " ]\n"; + OS << "\n [ B" << I->getBlockID(); + + if (&(*I) == getIndirectGotoBlock()) + OS << " (INDIRECT GOTO DISPATCH) ]\n"; + else + OS << " ]\n"; + I->print(OS); } diff --git a/include/clang/AST/CFG.h b/include/clang/AST/CFG.h index 4d222b890e..80009d841d 100644 --- a/include/clang/AST/CFG.h +++ b/include/clang/AST/CFG.h @@ -155,10 +155,12 @@ class CFG { typedef std::list CFGBlockListTy; CFGBlock* Entry; CFGBlock* Exit; + CFGBlock* IndirectGotoBlock; // Special block to contain collective dispatch + // for indirect gotos CFGBlockListTy Blocks; public: - CFG() : Entry(NULL), Exit(NULL) {}; + CFG() : Entry(NULL), Exit(NULL), IndirectGotoBlock(NULL) {}; ~CFG() {}; // Block iterators @@ -167,21 +169,22 @@ public: typedef std::reverse_iterator reverse_iterator; typedef std::reverse_iterator const_reverse_iterator; - CFGBlock& front() { return Blocks.front(); } - CFGBlock& back() { return Blocks.back(); } + CFGBlock& front() { return Blocks.front(); } + CFGBlock& back() { return Blocks.back(); } - iterator begin() { return Blocks.begin(); } - iterator end() { return Blocks.end(); } - const_iterator begin() const { return Blocks.begin(); } - const_iterator end() const { return Blocks.end(); } + iterator begin() { return Blocks.begin(); } + iterator end() { return Blocks.end(); } + const_iterator begin() const { return Blocks.begin(); } + const_iterator end() const { return Blocks.end(); } - reverse_iterator rbegin() { return Blocks.rbegin(); } - reverse_iterator rend() { return Blocks.rend(); } - const_reverse_iterator rbegin() const { return Blocks.rbegin(); } - const_reverse_iterator rend() const { return Blocks.rend(); } + reverse_iterator rbegin() { return Blocks.rbegin(); } + reverse_iterator rend() { return Blocks.rend(); } + const_reverse_iterator rbegin() const { return Blocks.rbegin(); } + const_reverse_iterator rend() const { return Blocks.rend(); } - CFGBlock& getEntry() { return *Entry; } - CFGBlock& getExit() { return *Exit; } + CFGBlock& getEntry() { return *Entry; } + CFGBlock& getExit() { return *Exit; } + CFGBlock* getIndirectGotoBlock() { return IndirectGotoBlock; } // Utility @@ -189,7 +192,8 @@ public: static CFG* buildCFG(Stmt* AST); void print(std::ostream& OS); void dump(); - void setEntry(CFGBlock *B) { Entry = B; } + void setEntry(CFGBlock *B) { Entry = B; } + void setIndirectGotoBlock(CFGBlock* B) { IndirectGotoBlock = B; } }; } // end namespace clang -- 2.40.0