clang/lib/Analysis/FlowSensitive/ControlFlowContext.cpp

   1 //===- ControlFlowContext.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-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 //  This file defines a ControlFlowContext class that is used by dataflow
  10 //  analyses that run over Control-Flow Graphs (CFGs).
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "clang/Analysis/FlowSensitive/ControlFlowContext.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
  24 namespace clang {
  25 namespace dataflow {
  26
  27 /// Returns a map from statements to basic blocks that contain them.
  28 static llvm::DenseMap<const Stmt *, const CFGBlock *>
  29 buildStmtToBasicBlockMap(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     if (const Stmt *TerminatorStmt = Block->getTerminatorStmt())
  43       StmtToBlock[TerminatorStmt] = Block;
  44   }
  45   return StmtToBlock;
  46 }
  47
  48 static llvm::BitVector findReachableBlocks(const CFG &Cfg) {
  49   llvm::BitVector BlockReachable(Cfg.getNumBlockIDs(), false);
  50
  51   llvm::SmallVector<const CFGBlock *> BlocksToVisit;
  52   BlocksToVisit.push_back(&Cfg.getEntry());
  53   while (!BlocksToVisit.empty()) {
  54     const CFGBlock *Block = BlocksToVisit.back();
  55     BlocksToVisit.pop_back();
  56
  57     if (BlockReachable[Block->getBlockID()])
  58       continue;
  59
  60     BlockReachable[Block->getBlockID()] = true;
  61
  62     for (const CFGBlock *Succ : Block->succs())
  63       if (Succ)
  64         BlocksToVisit.push_back(Succ);
  65   }
  66
  67   return BlockReachable;
  68 }
  69
  70 llvm::Expected<ControlFlowContext>
  71 ControlFlowContext::build(const FunctionDecl &Func) {
  72   if (!Func.hasBody())
  73     return llvm::createStringError(
  74         std::make_error_code(std::errc::invalid_argument),
  75         "Cannot analyze function without a body");
  76
  77   return build(Func, *Func.getBody(), Func.getASTContext());
  78 }
  79
  80 llvm::Expected<ControlFlowContext>
  81 ControlFlowContext::build(const Decl &D, Stmt &S, ASTContext &C) {
  82   if (D.isTemplated())
  83     return llvm::createStringError(
  84         std::make_error_code(std::errc::invalid_argument),
  85         "Cannot analyze templated declarations");
  86
  87   // The shape of certain elements of the AST can vary depending on the
  88   // language. We currently only support C++.
  89   if (!C.getLangOpts().CPlusPlus)
  90     return llvm::createStringError(
  91         std::make_error_code(std::errc::invalid_argument),
  92         "Can only analyze C++");
  93
  94   CFG::BuildOptions Options;
  95   Options.PruneTriviallyFalseEdges = true;
  96   Options.AddImplicitDtors = true;
  97   Options.AddTemporaryDtors = true;
  98   Options.AddInitializers = true;
  99   Options.AddCXXDefaultInitExprInCtors = true;
 100   Options.AddLifetime = true;
 101
 102   // Ensure that all sub-expressions in basic blocks are evaluated.
 103   Options.setAllAlwaysAdd();
 104
 105   auto Cfg = CFG::buildCFG(&D, &S, &C, Options);
 106   if (Cfg == nullptr)
 107     return llvm::createStringError(
 108         std::make_error_code(std::errc::invalid_argument),
 109         "CFG::buildCFG failed");
 110
 111   llvm::DenseMap<const Stmt *, const CFGBlock *> StmtToBlock =
 112       buildStmtToBasicBlockMap(*Cfg);
 113
 114   llvm::BitVector BlockReachable = findReachableBlocks(*Cfg);
 115
 116   return ControlFlowContext(D, std::move(Cfg), std::move(StmtToBlock),
 117                             std::move(BlockReachable));
 118 }
 119
 120 } // namespace dataflow
 121 } // namespace clang