Clang Project

clang_source_code/lib/Analysis/ThreadSafetyTIL.cpp
1//===- ThreadSafetyTIL.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#include "clang/Analysis/Analyses/ThreadSafetyTIL.h"
10#include "clang/Basic/LLVM.h"
11#include "llvm/Support/Casting.h"
12#include <cassert>
13#include <cstddef>
14
15using namespace clang;
16using namespace threadSafety;
17using namespace til;
18
19StringRef til::getUnaryOpcodeString(TIL_UnaryOpcode Op) {
20  switch (Op) {
21    case UOP_Minus:    return "-";
22    case UOP_BitNot:   return "~";
23    case UOP_LogicNot: return "!";
24  }
25  return {};
26}
27
28StringRef til::getBinaryOpcodeString(TIL_BinaryOpcode Op) {
29  switch (Op) {
30    case BOP_Mul:      return "*";
31    case BOP_Div:      return "/";
32    case BOP_Rem:      return "%";
33    case BOP_Add:      return "+";
34    case BOP_Sub:      return "-";
35    case BOP_Shl:      return "<<";
36    case BOP_Shr:      return ">>";
37    case BOP_BitAnd:   return "&";
38    case BOP_BitXor:   return "^";
39    case BOP_BitOr:    return "|";
40    case BOP_Eq:       return "==";
41    case BOP_Neq:      return "!=";
42    case BOP_Lt:       return "<";
43    case BOP_Leq:      return "<=";
44    case BOP_Cmp:      return "<=>";
45    case BOP_LogicAnd: return "&&";
46    case BOP_LogicOr:  return "||";
47  }
48  return {};
49}
50
51SExpr* Future::force() {
52  Status = FS_evaluating;
53  Result = compute();
54  Status = FS_done;
55  return Result;
56}
57
58unsigned BasicBlock::addPredecessor(BasicBlock *Pred) {
59  unsigned Idx = Predecessors.size();
60  Predecessors.reserveCheck(1, Arena);
61  Predecessors.push_back(Pred);
62  for (auto *E : Args) {
63    if (auto *Ph = dyn_cast<Phi>(E)) {
64      Ph->values().reserveCheck(1, Arena);
65      Ph->values().push_back(nullptr);
66    }
67  }
68  return Idx;
69}
70
71void BasicBlock::reservePredecessors(unsigned NumPreds) {
72  Predecessors.reserve(NumPreds, Arena);
73  for (auto *E : Args) {
74    if (auto *Ph = dyn_cast<Phi>(E)) {
75      Ph->values().reserve(NumPreds, Arena);
76    }
77  }
78}
79
80// If E is a variable, then trace back through any aliases or redundant
81// Phi nodes to find the canonical definition.
82const SExpr *til::getCanonicalVal(const SExpr *E) {
83  while (true) {
84    if (const auto *V = dyn_cast<Variable>(E)) {
85      if (V->kind() == Variable::VK_Let) {
86        E = V->definition();
87        continue;
88      }
89    }
90    if (const auto *Ph = dyn_cast<Phi>(E)) {
91      if (Ph->status() == Phi::PH_SingleVal) {
92        E = Ph->values()[0];
93        continue;
94      }
95    }
96    break;
97  }
98  return E;
99}
100
101// If E is a variable, then trace back through any aliases or redundant
102// Phi nodes to find the canonical definition.
103// The non-const version will simplify incomplete Phi nodes.
104SExpr *til::simplifyToCanonicalVal(SExpr *E) {
105  while (true) {
106    if (auto *V = dyn_cast<Variable>(E)) {
107      if (V->kind() != Variable::VK_Let)
108        return V;
109      // Eliminate redundant variables, e.g. x = y, or x = 5,
110      // but keep anything more complicated.
111      if (til::ThreadSafetyTIL::isTrivial(V->definition())) {
112        E = V->definition();
113        continue;
114      }
115      return V;
116    }
117    if (auto *Ph = dyn_cast<Phi>(E)) {
118      if (Ph->status() == Phi::PH_Incomplete)
119        simplifyIncompleteArg(Ph);
120      // Eliminate redundant Phi nodes.
121      if (Ph->status() == Phi::PH_SingleVal) {
122        E = Ph->values()[0];
123        continue;
124      }
125    }
126    return E;
127  }
128}
129
130// Trace the arguments of an incomplete Phi node to see if they have the same
131// canonical definition.  If so, mark the Phi node as redundant.
132// getCanonicalVal() will recursively call simplifyIncompletePhi().
133void til::simplifyIncompleteArg(til::Phi *Ph) {
134  status() == Phi..PH_Incomplete", "/home/seafit/code_projects/clang_source/clang/lib/Analysis/ThreadSafetyTIL.cpp", 134, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(Ph && Ph->status() == Phi::PH_Incomplete);
135
136  // eliminate infinite recursion -- assume that this node is not redundant.
137  Ph->setStatus(Phi::PH_MultiVal);
138
139  SExpr *E0 = simplifyToCanonicalVal(Ph->values()[0]);
140  for (unsigned i = 1, n = Ph->values().size(); i < n; ++i) {
141    SExpr *Ei = simplifyToCanonicalVal(Ph->values()[i]);
142    if (Ei == Ph)
143      continue;  // Recursive reference to itself.  Don't count.
144    if (Ei != E0) {
145      return;    // Status is already set to MultiVal.
146    }
147  }
148  Ph->setStatus(Phi::PH_SingleVal);
149}
150
151// Renumbers the arguments and instructions to have unique, sequential IDs.
152unsigned BasicBlock::renumberInstrs(unsigned ID) {
153  for (auto *Arg : Args)
154    Arg->setID(this, ID++);
155  for (auto *Instr : Instrs)
156    Instr->setID(this, ID++);
157  TermInstr->setID(this, ID++);
158  return ID;
159}
160
161// Sorts the CFGs blocks using a reverse post-order depth-first traversal.
162// Each block will be written into the Blocks array in order, and its BlockID
163// will be set to the index in the array.  Sorting should start from the entry
164// block, and ID should be the total number of blocks.
165unsigned BasicBlock::topologicalSort(SimpleArray<BasicBlock *> &Blocks,
166                                     unsigned ID) {
167  if (Visited) return ID;
168  Visited = true;
169  for (auto *Block : successors())
170    ID = Block->topologicalSort(Blocks, ID);
171  // set ID and update block array in place.
172  // We may lose pointers to unreachable blocks.
173   0", "/home/seafit/code_projects/clang_source/clang/lib/Analysis/ThreadSafetyTIL.cpp", 173, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(ID > 0);
174  BlockID = --ID;
175  Blocks[BlockID] = this;
176  return ID;
177}
178
179// Performs a reverse topological traversal, starting from the exit block and
180// following back-edges.  The dominator is serialized before any predecessors,
181// which guarantees that all blocks are serialized after their dominator and
182// before their post-dominator (because it's a reverse topological traversal).
183// ID should be initially set to 0.
184//
185// This sort assumes that (1) dominators have been computed, (2) there are no
186// critical edges, and (3) the entry block is reachable from the exit block
187// and no blocks are accessible via traversal of back-edges from the exit that
188// weren't accessible via forward edges from the entry.
189unsigned BasicBlock::topologicalFinalSort(SimpleArray<BasicBlock *> &Blocks,
190                                          unsigned ID) {
191  // Visited is assumed to have been set by the topologicalSort.  This pass
192  // assumes !Visited means that we've visited this node before.
193  if (!Visited) return ID;
194  Visited = false;
195  if (DominatorNode.Parent)
196    ID = DominatorNode.Parent->topologicalFinalSort(Blocks, ID);
197  for (auto *Pred : Predecessors)
198    ID = Pred->topologicalFinalSort(Blocks, ID);
199  (ID) < Blocks.size()", "/home/seafit/code_projects/clang_source/clang/lib/Analysis/ThreadSafetyTIL.cpp", 199, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(static_cast<size_t>(ID) < Blocks.size());
200  BlockID = ID++;
201  Blocks[BlockID] = this;
202  return ID;
203}
204
205// Computes the immediate dominator of the current block.  Assumes that all of
206// its predecessors have already computed their dominators.  This is achieved
207// by visiting the nodes in topological order.
208void BasicBlock::computeDominator() {
209  BasicBlock *Candidate = nullptr;
210  // Walk backwards from each predecessor to find the common dominator node.
211  for (auto *Pred : Predecessors) {
212    // Skip back-edges
213    if (Pred->BlockID >= BlockID) continue;
214    // If we don't yet have a candidate for dominator yet, take this one.
215    if (Candidate == nullptr) {
216      Candidate = Pred;
217      continue;
218    }
219    // Walk the alternate and current candidate back to find a common ancestor.
220    auto *Alternate = Pred;
221    while (Alternate != Candidate) {
222      if (Candidate->BlockID > Alternate->BlockID)
223        Candidate = Candidate->DominatorNode.Parent;
224      else
225        Alternate = Alternate->DominatorNode.Parent;
226    }
227  }
228  DominatorNode.Parent = Candidate;
229  DominatorNode.SizeOfSubTree = 1;
230}
231
232// Computes the immediate post-dominator of the current block.  Assumes that all
233// of its successors have already computed their post-dominators.  This is
234// achieved visiting the nodes in reverse topological order.
235void BasicBlock::computePostDominator() {
236  BasicBlock *Candidate = nullptr;
237  // Walk back from each predecessor to find the common post-dominator node.
238  for (auto *Succ : successors()) {
239    // Skip back-edges
240    if (Succ->BlockID <= BlockID) continue;
241    // If we don't yet have a candidate for post-dominator yet, take this one.
242    if (Candidate == nullptr) {
243      Candidate = Succ;
244      continue;
245    }
246    // Walk the alternate and current candidate back to find a common ancestor.
247    auto *Alternate = Succ;
248    while (Alternate != Candidate) {
249      if (Candidate->BlockID < Alternate->BlockID)
250        Candidate = Candidate->PostDominatorNode.Parent;
251      else
252        Alternate = Alternate->PostDominatorNode.Parent;
253    }
254  }
255  PostDominatorNode.Parent = Candidate;
256  PostDominatorNode.SizeOfSubTree = 1;
257}
258
259// Renumber instructions in all blocks
260void SCFG::renumberInstrs() {
261  unsigned InstrID = 0;
262  for (auto *Block : Blocks)
263    InstrID = Block->renumberInstrs(InstrID);
264}
265
266static inline void computeNodeSize(BasicBlock *B,
267                                   BasicBlock::TopologyNode BasicBlock::*TN) {
268  BasicBlock::TopologyNode *N = &(B->*TN);
269  if (N->Parent) {
270    BasicBlock::TopologyNode *P = &(N->Parent->*TN);
271    // Initially set ID relative to the (as yet uncomputed) parent ID
272    N->NodeID = P->SizeOfSubTree;
273    P->SizeOfSubTree += N->SizeOfSubTree;
274  }
275}
276
277static inline void computeNodeID(BasicBlock *B,
278                                 BasicBlock::TopologyNode BasicBlock::*TN) {
279  BasicBlock::TopologyNode *N = &(B->*TN);
280  if (N->Parent) {
281    BasicBlock::TopologyNode *P = &(N->Parent->*TN);
282    N->NodeID += P->NodeID;    // Fix NodeIDs relative to starting node.
283  }
284}
285
286// Normalizes a CFG.  Normalization has a few major components:
287// 1) Removing unreachable blocks.
288// 2) Computing dominators and post-dominators
289// 3) Topologically sorting the blocks into the "Blocks" array.
290void SCFG::computeNormalForm() {
291  // Topologically sort the blocks starting from the entry block.
292  unsigned NumUnreachableBlocks = Entry->topologicalSort(Blocks, Blocks.size());
293  if (NumUnreachableBlocks > 0) {
294    // If there were unreachable blocks shift everything down, and delete them.
295    for (unsigned I = NumUnreachableBlocks, E = Blocks.size(); I < E; ++I) {
296      unsigned NI = I - NumUnreachableBlocks;
297      Blocks[NI] = Blocks[I];
298      Blocks[NI]->BlockID = NI;
299      // FIXME: clean up predecessor pointers to unreachable blocks?
300    }
301    Blocks.drop(NumUnreachableBlocks);
302  }
303
304  // Compute dominators.
305  for (auto *Block : Blocks)
306    Block->computeDominator();
307
308  // Once dominators have been computed, the final sort may be performed.
309  unsigned NumBlocks = Exit->topologicalFinalSort(Blocks, 0);
310  (NumBlocks) == Blocks.size()", "/home/seafit/code_projects/clang_source/clang/lib/Analysis/ThreadSafetyTIL.cpp", 310, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(static_cast<size_t>(NumBlocks) == Blocks.size());
311  (void) NumBlocks;
312
313  // Renumber the instructions now that we have a final sort.
314  renumberInstrs();
315
316  // Compute post-dominators and compute the sizes of each node in the
317  // dominator tree.
318  for (auto *Block : Blocks.reverse()) {
319    Block->computePostDominator();
320    computeNodeSize(Block, &BasicBlock::DominatorNode);
321  }
322  // Compute the sizes of each node in the post-dominator tree and assign IDs in
323  // the dominator tree.
324  for (auto *Block : Blocks) {
325    computeNodeID(Block, &BasicBlock::DominatorNode);
326    computeNodeSize(Block, &BasicBlock::PostDominatorNode);
327  }
328  // Assign IDs in the post-dominator tree.
329  for (auto *Block : Blocks.reverse()) {
330    computeNodeID(Block, &BasicBlock::PostDominatorNode);
331  }
332}
333
clang::threadSafety::til::Future::force
clang::threadSafety::til::BasicBlock::addPredecessor
clang::threadSafety::til::BasicBlock::reservePredecessors
clang::threadSafety::til::BasicBlock::renumberInstrs
clang::threadSafety::til::BasicBlock::topologicalSort
clang::threadSafety::til::BasicBlock::topologicalFinalSort
clang::threadSafety::til::BasicBlock::computeDominator
clang::threadSafety::til::BasicBlock::computePostDominator
clang::threadSafety::til::SCFG::renumberInstrs
clang::threadSafety::til::SCFG::computeNormalForm
CodeThinker, Enjoy your reading code