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