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.doesThisDeclarationHaveABody())
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
122