1//===- CFGBackEdges.cpp - Finds back edges in Clang CFGs ------------------===//
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#include <stack>
10#include <utility>
11#include <vector>
12
13#include "clang/Analysis/CFG.h"
14#include "clang/Analysis/CFGBackEdges.h"
15#include "llvm/ADT/DenseMap.h"
16
17namespace clang {
18
19namespace {
20struct VisitClockTimes {
21 // Timestamp for when the node was visited / discovered.
22 int Pre = -1;
23 // Timestamp for when we finished visiting a node's successors.
24 int Post = -1;
25};
26} // namespace
27
28// Returns true if the CFG contains any goto statements (direct or indirect).
29static bool hasGotoInCFG(const CFG &CFG) {
30 for (const CFGBlock *Block : CFG) {
31 const Stmt *Term = Block->getTerminatorStmt();
32 if (Term == nullptr)
33 continue;
34 if (isa<GotoStmt>(Val: Term) || isa<IndirectGotoStmt>(Val: Term))
35 return true;
36 }
37 return false;
38}
39
40llvm::DenseMap<const CFGBlock *, const CFGBlock *>
41findCFGBackEdges(const CFG &CFG) {
42 // Do a simple textbook DFS with pre and post numberings to find back edges.
43 llvm::DenseMap<const CFGBlock *, const CFGBlock *> BackEdges;
44
45 std::vector<VisitClockTimes> VisitState;
46 VisitState.resize(new_size: CFG.getNumBlockIDs());
47 std::stack<std::pair<const CFGBlock *, CFGBlock::const_succ_iterator>>
48 DFSStack;
49 int Clock = 0;
50 const CFGBlock &Entry = CFG.getEntry();
51 VisitState[Entry.getBlockID()].Pre = Clock++;
52 DFSStack.push(x: {&Entry, Entry.succ_begin()});
53
54 while (!DFSStack.empty()) {
55 auto &[Block, SuccIt] = DFSStack.top();
56 if (SuccIt == Block->succ_end()) {
57 VisitState[Block->getBlockID()].Post = Clock++;
58 DFSStack.pop();
59 continue;
60 }
61
62 const CFGBlock::AdjacentBlock &AdjacentSucc = *SuccIt++;
63 const CFGBlock *Succ = AdjacentSucc.getReachableBlock();
64 // Skip unreachable blocks.
65 if (Succ == nullptr)
66 continue;
67
68 VisitClockTimes &SuccVisitState = VisitState[Succ->getBlockID()];
69 if (SuccVisitState.Pre != -1) {
70 if (SuccVisitState.Post == -1)
71 BackEdges.insert(KV: {Block, Succ});
72 } else {
73 SuccVisitState.Pre = Clock++;
74 DFSStack.push(x: {Succ, Succ->succ_begin()});
75 }
76 }
77 return BackEdges;
78}
79
80// Returns a set of CFG blocks that is the source of a backedge and is not
81// tracked as part of a structured loop (with `CFGBlock::getLoopTarget`).
82llvm::SmallDenseSet<const CFGBlock *>
83findNonStructuredLoopBackedgeNodes(const CFG &CFG) {
84 llvm::SmallDenseSet<const CFGBlock *> NonStructLoopBackedgeNodes;
85 // We should only need this if the function has gotos.
86 if (!hasGotoInCFG(CFG))
87 return NonStructLoopBackedgeNodes;
88
89 llvm::DenseMap<const CFGBlock *, const CFGBlock *> Backedges =
90 findCFGBackEdges(CFG);
91 for (const auto &[From, To] : Backedges) {
92 if (From->getLoopTarget() == nullptr)
93 NonStructLoopBackedgeNodes.insert(V: From);
94 }
95 return NonStructLoopBackedgeNodes;
96}
97
98bool isBackedgeCFGNode(
99 const CFGBlock &B,
100 const llvm::SmallDenseSet<const CFGBlock *> &NonStructLoopBackedgeNodes) {
101 return B.getLoopTarget() != nullptr ||
102 NonStructLoopBackedgeNodes.contains(V: &B);
103}
104
105} // namespace clang
106