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   CFG::BuildOptions Options;
88   Options.PruneTriviallyFalseEdges = true;
89   Options.AddImplicitDtors = true;
90   Options.AddTemporaryDtors = true;
91   Options.AddInitializers = true;
92   Options.AddCXXDefaultInitExprInCtors = true;
93 
94   // Ensure that all sub-expressions in basic blocks are evaluated.
95   Options.setAllAlwaysAdd();
96 
97   auto Cfg = CFG::buildCFG(&D, &S, &C, Options);
98   if (Cfg == nullptr)
99     return llvm::createStringError(
100         std::make_error_code(std::errc::invalid_argument),
101         "CFG::buildCFG failed");
102 
103   llvm::DenseMap<const Stmt *, const CFGBlock *> StmtToBlock =
104       buildStmtToBasicBlockMap(*Cfg);
105 
106   llvm::BitVector BlockReachable = findReachableBlocks(*Cfg);
107 
108   return ControlFlowContext(&D, std::move(Cfg), std::move(StmtToBlock),
109                             std::move(BlockReachable));
110 }
111 
112 llvm::Expected<ControlFlowContext>
113 ControlFlowContext::build(const Decl *D, Stmt &S, ASTContext &C) {
114   if (D == nullptr)
115     return llvm::createStringError(
116         std::make_error_code(std::errc::invalid_argument),
117         "Declaration must not be null");
118 
119   return build(*D, S, C);
120 }
121 
122 } // namespace dataflow
123 } // namespace clang
124