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