clang  10.0.0svn
ThreadSafetyTIL.cpp
Go to the documentation of this file.
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 
10 #include "clang/Basic/LLVM.h"
11 #include "llvm/Support/Casting.h"
12 #include <cassert>
13 #include <cstddef>
14 
15 using namespace clang;
16 using namespace threadSafety;
17 using namespace til;
18 
20  switch (Op) {
21  case UOP_Minus: return "-";
22  case UOP_BitNot: return "~";
23  case UOP_LogicNot: return "!";
24  }
25  return {};
26 }
27 
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 
51 SExpr* Future::force() {
52  Status = FS_evaluating;
53  Result = compute();
54  Status = FS_done;
55  return Result;
56 }
57 
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 
71 void 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.
82 const 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.
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)
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().
134  assert(Ph && Ph->status() == Phi::PH_Incomplete);
135 
136  // eliminate infinite recursion -- assume that this node is not redundant.
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  }
149 }
150 
151 // Renumbers the arguments and instructions to have unique, sequential IDs.
152 unsigned 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.
165 unsigned 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  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.
189 unsigned 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  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.
208 void 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.
235 void 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
260 void SCFG::renumberInstrs() {
261  unsigned InstrID = 0;
262  for (auto *Block : Blocks)
263  InstrID = Block->renumberInstrs(InstrID);
264 }
265 
266 static inline void computeNodeSize(BasicBlock *B,
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 
277 static inline void computeNodeID(BasicBlock *B,
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.
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  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 }
StringRef getBinaryOpcodeString(TIL_BinaryOpcode Op)
Return the name of a binary opcode.
StringRef P
SExpr * simplifyToCanonicalVal(SExpr *E)
unsigned addPredecessor(BasicBlock *Pred)
Forward-declares and imports various common LLVM datatypes that clang wants to use unqualified...
A basic block is part of an SCFG.
static void computeNodeSize(BasicBlock *B, BasicBlock::TopologyNode BasicBlock::*TN)
StringRef getUnaryOpcodeString(TIL_UnaryOpcode Op)
Return the name of a unary opcode.
#define V(N, I)
Definition: ASTContext.h:2921
TIL_BinaryOpcode
Opcode for binary arithmetic operations.
void reservePredecessors(unsigned NumPreds)
const ValArray & values() const
TIL_UnaryOpcode
Opcode for unary arithmetic operations.
const SExpr * getCanonicalVal(const SExpr *E)
Dataflow Directional Tag Classes.
Phi Node, for code in SSA form.
static void computeNodeID(BasicBlock *B, BasicBlock::TopologyNode BasicBlock::*TN)
void simplifyIncompleteArg(til::Phi *Ph)
Base class for AST nodes in the typed intermediate language.