189 lines · cpp
1//===- AdornedCFG.cpp ---------------------------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This file defines an `AdornedCFG` class that is used by dataflow analyses10// that run over Control-Flow Graphs (CFGs).11//12//===----------------------------------------------------------------------===//13 14#include "clang/Analysis/FlowSensitive/AdornedCFG.h"15#include "clang/AST/ASTContext.h"16#include "clang/AST/Decl.h"17#include "clang/AST/Stmt.h"18#include "clang/Analysis/CFG.h"19#include "llvm/ADT/BitVector.h"20#include "llvm/ADT/DenseMap.h"21#include "llvm/Support/Error.h"22#include <utility>23 24namespace clang {25namespace dataflow {26 27/// Returns a map from statements to basic blocks that contain them.28static llvm::DenseMap<const Stmt *, const CFGBlock *>29buildStmtToBasicBlockMap(const CFG &Cfg) {30 llvm::DenseMap<const Stmt *, const CFGBlock *> StmtToBlock;31 for (const CFGBlock *Block : Cfg) {32 if (Block == nullptr)33 continue;34 35 for (const CFGElement &Element : *Block) {36 auto Stmt = Element.getAs<CFGStmt>();37 if (!Stmt)38 continue;39 40 StmtToBlock[Stmt->getStmt()] = Block;41 }42 }43 // Some terminator conditions don't appear as a `CFGElement` anywhere else -44 // for example, this is true if the terminator condition is a `&&` or `||`45 // operator.46 // We associate these conditions with the block the terminator appears in,47 // but only if the condition has not already appeared as a regular48 // `CFGElement`. (The `insert()` below does nothing if the key already exists49 // in the map.)50 for (const CFGBlock *Block : Cfg) {51 if (Block != nullptr)52 if (const Stmt *TerminatorCond = Block->getTerminatorCondition())53 StmtToBlock.insert({TerminatorCond, Block});54 }55 // Terminator statements typically don't appear as a `CFGElement` anywhere56 // else, so we want to associate them with the block that they terminate.57 // However, there are some important special cases:58 // - The conditional operator is a type of terminator, but it also appears59 // as a regular `CFGElement`, and we want to associate it with the block60 // in which it appears as a `CFGElement`.61 // - The `&&` and `||` operators are types of terminators, but like the62 // conditional operator, they can appear as a regular `CFGElement` or63 // as a terminator condition (see above).64 // We process terminators last to make sure that we only associate them with65 // the block they terminate if they haven't previously occurred as a regular66 // `CFGElement` or as a terminator condition.67 for (const CFGBlock *Block : Cfg) {68 if (Block != nullptr)69 if (const Stmt *TerminatorStmt = Block->getTerminatorStmt())70 StmtToBlock.insert({TerminatorStmt, Block});71 }72 return StmtToBlock;73}74 75static llvm::BitVector findReachableBlocks(const CFG &Cfg) {76 llvm::BitVector BlockReachable(Cfg.getNumBlockIDs(), false);77 78 llvm::SmallVector<const CFGBlock *> BlocksToVisit;79 BlocksToVisit.push_back(&Cfg.getEntry());80 while (!BlocksToVisit.empty()) {81 const CFGBlock *Block = BlocksToVisit.back();82 BlocksToVisit.pop_back();83 84 if (BlockReachable[Block->getBlockID()])85 continue;86 87 BlockReachable[Block->getBlockID()] = true;88 89 for (const CFGBlock *Succ : Block->succs())90 if (Succ)91 BlocksToVisit.push_back(Succ);92 }93 94 return BlockReachable;95}96 97static llvm::DenseSet<const CFGBlock *>98buildContainsExprConsumedInDifferentBlock(99 const CFG &Cfg, const internal::StmtToBlockMap &StmtToBlock) {100 llvm::DenseSet<const CFGBlock *> Result;101 102 auto CheckChildExprs = [&Result, &StmtToBlock](const Stmt *S,103 const CFGBlock *Block) {104 for (const Stmt *Child : S->children()) {105 if (!isa_and_nonnull<Expr>(Child))106 continue;107 const CFGBlock *ChildBlock = StmtToBlock.lookup(*Child);108 if (ChildBlock != Block)109 Result.insert(ChildBlock);110 }111 };112 113 for (const CFGBlock *Block : Cfg) {114 if (Block == nullptr)115 continue;116 117 for (const CFGElement &Element : *Block)118 if (auto S = Element.getAs<CFGStmt>())119 CheckChildExprs(S->getStmt(), Block);120 121 if (const Stmt *TerminatorCond = Block->getTerminatorCondition())122 CheckChildExprs(TerminatorCond, Block);123 }124 125 return Result;126}127 128namespace internal {129 130StmtToBlockMap::StmtToBlockMap(const CFG &Cfg)131 : StmtToBlock(buildStmtToBasicBlockMap(Cfg)) {}132 133} // namespace internal134 135llvm::Expected<AdornedCFG> AdornedCFG::build(const FunctionDecl &Func) {136 if (!Func.doesThisDeclarationHaveABody())137 return llvm::createStringError(138 std::make_error_code(std::errc::invalid_argument),139 "Cannot analyze function without a body");140 141 return build(Func, *Func.getBody(), Func.getASTContext());142}143 144llvm::Expected<AdornedCFG> AdornedCFG::build(const Decl &D, Stmt &S,145 ASTContext &C) {146 if (D.isTemplated())147 return llvm::createStringError(148 std::make_error_code(std::errc::invalid_argument),149 "Cannot analyze templated declarations");150 151 // The shape of certain elements of the AST can vary depending on the152 // language. We currently only support C++.153 if (!C.getLangOpts().CPlusPlus || C.getLangOpts().ObjC)154 return llvm::createStringError(155 std::make_error_code(std::errc::invalid_argument),156 "Can only analyze C++");157 158 CFG::BuildOptions Options;159 Options.PruneTriviallyFalseEdges = true;160 Options.AddImplicitDtors = true;161 Options.AddTemporaryDtors = true;162 Options.AddInitializers = true;163 Options.AddCXXDefaultInitExprInCtors = true;164 Options.AddLifetime = true;165 166 // Ensure that all sub-expressions in basic blocks are evaluated.167 Options.setAllAlwaysAdd();168 169 auto Cfg = CFG::buildCFG(&D, &S, &C, Options);170 if (Cfg == nullptr)171 return llvm::createStringError(172 std::make_error_code(std::errc::invalid_argument),173 "CFG::buildCFG failed");174 175 internal::StmtToBlockMap StmtToBlock(*Cfg);176 177 llvm::BitVector BlockReachable = findReachableBlocks(*Cfg);178 179 llvm::DenseSet<const CFGBlock *> ContainsExprConsumedInDifferentBlock =180 buildContainsExprConsumedInDifferentBlock(*Cfg, StmtToBlock);181 182 return AdornedCFG(D, std::move(Cfg), std::move(StmtToBlock),183 std::move(BlockReachable),184 std::move(ContainsExprConsumedInDifferentBlock));185}186 187} // namespace dataflow188} // namespace clang189