1 //===- ThreadSafetyTIL.cpp -------------------------------------*- C++ --*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT in the llvm repository for details.
7 //
8 //===----------------------------------------------------------------------===//
9
10 #include "clang/Analysis/Analyses/ThreadSafetyTIL.h"
11 #include "clang/Analysis/Analyses/ThreadSafetyTraverse.h"
12
13 namespace clang {
14 namespace threadSafety {
15 namespace til {
16
17
getUnaryOpcodeString(TIL_UnaryOpcode Op)18 StringRef getUnaryOpcodeString(TIL_UnaryOpcode Op) {
19 switch (Op) {
20 case UOP_Minus: return "-";
21 case UOP_BitNot: return "~";
22 case UOP_LogicNot: return "!";
23 }
24 return "";
25 }
26
27
getBinaryOpcodeString(TIL_BinaryOpcode Op)28 StringRef 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_LogicAnd: return "&&";
45 case BOP_LogicOr: return "||";
46 }
47 return "";
48 }
49
50
addPredecessor(BasicBlock * Pred)51 unsigned BasicBlock::addPredecessor(BasicBlock *Pred) {
52 unsigned Idx = Predecessors.size();
53 Predecessors.reserveCheck(1, Arena);
54 Predecessors.push_back(Pred);
55 for (Variable *V : Args) {
56 if (Phi* Ph = dyn_cast<Phi>(V->definition())) {
57 Ph->values().reserveCheck(1, Arena);
58 Ph->values().push_back(nullptr);
59 }
60 }
61 return Idx;
62 }
63
reservePredecessors(unsigned NumPreds)64 void BasicBlock::reservePredecessors(unsigned NumPreds) {
65 Predecessors.reserve(NumPreds, Arena);
66 for (Variable *V : Args) {
67 if (Phi* Ph = dyn_cast<Phi>(V->definition())) {
68 Ph->values().reserve(NumPreds, Arena);
69 }
70 }
71 }
72
renumberVars()73 void BasicBlock::renumberVars() {
74 unsigned VID = 0;
75 for (Variable *V : Args) {
76 V->setID(BlockID, VID++);
77 }
78 for (Variable *V : Instrs) {
79 V->setID(BlockID, VID++);
80 }
81 }
82
renumberVars()83 void SCFG::renumberVars() {
84 for (BasicBlock *B : Blocks) {
85 B->renumberVars();
86 }
87 }
88
89
90
91
92 // If E is a variable, then trace back through any aliases or redundant
93 // Phi nodes to find the canonical definition.
getCanonicalVal(SExpr * E)94 SExpr *getCanonicalVal(SExpr *E) {
95 while (auto *V = dyn_cast<Variable>(E)) {
96 SExpr *D;
97 do {
98 if (V->kind() != Variable::VK_Let)
99 return V;
100 D = V->definition();
101 auto *V2 = dyn_cast<Variable>(D);
102 if (V2)
103 V = V2;
104 else
105 break;
106 } while (true);
107
108 if (ThreadSafetyTIL::isTrivial(D))
109 return D;
110
111 if (Phi *Ph = dyn_cast<Phi>(D)) {
112 if (Ph->status() == Phi::PH_Incomplete)
113 simplifyIncompleteArg(V, Ph);
114
115 if (Ph->status() == Phi::PH_SingleVal) {
116 E = Ph->values()[0];
117 continue;
118 }
119 }
120 return V;
121 }
122 return E;
123 }
124
125
126 // Trace the arguments of an incomplete Phi node to see if they have the same
127 // canonical definition. If so, mark the Phi node as redundant.
128 // getCanonicalVal() will recursively call simplifyIncompletePhi().
simplifyIncompleteArg(Variable * V,til::Phi * Ph)129 void simplifyIncompleteArg(Variable *V, til::Phi *Ph) {
130 assert(Ph && Ph->status() == Phi::PH_Incomplete);
131
132 // eliminate infinite recursion -- assume that this node is not redundant.
133 Ph->setStatus(Phi::PH_MultiVal);
134
135 SExpr *E0 = getCanonicalVal(Ph->values()[0]);
136 for (unsigned i=1, n=Ph->values().size(); i<n; ++i) {
137 SExpr *Ei = getCanonicalVal(Ph->values()[i]);
138 if (Ei == V)
139 continue; // Recursive reference to itself. Don't count.
140 if (Ei != E0) {
141 return; // Status is already set to MultiVal.
142 }
143 }
144 Ph->setStatus(Phi::PH_SingleVal);
145 // Eliminate Redundant Phi node.
146 V->setDefinition(Ph->values()[0]);
147 }
148
149
150 } // end namespace til
151 } // end namespace threadSafety
152 } // end namespace clang
153
154