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 
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 
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 
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 
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 
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 
83 void SCFG::renumberVars() {
84   for (BasicBlock *B : Blocks) {
85     B->renumberVars();
86   }
87 }
88 
89 
90 
91 // If E is a variable, then trace back through any aliases or redundant
92 // Phi nodes to find the canonical definition.
93 const SExpr *getCanonicalVal(const SExpr *E) {
94   while (auto *V = dyn_cast<Variable>(E)) {
95     const SExpr *D;
96     do {
97       if (V->kind() != Variable::VK_Let)
98         return V;
99       D = V->definition();
100       auto *V2 = dyn_cast<Variable>(D);
101       if (V2)
102         V = V2;
103       else
104         break;
105     } while (true);
106 
107     if (ThreadSafetyTIL::isTrivial(D))
108       return D;
109 
110     if (const Phi *Ph = dyn_cast<Phi>(D)) {
111       if (Ph->status() == Phi::PH_SingleVal) {
112         E = Ph->values()[0];
113         continue;
114       }
115     }
116     return V;
117   }
118   return E;
119 }
120 
121 
122 
123 // If E is a variable, then trace back through any aliases or redundant
124 // Phi nodes to find the canonical definition.
125 // The non-const version will simplify incomplete Phi nodes.
126 SExpr *simplifyToCanonicalVal(SExpr *E) {
127   while (auto *V = dyn_cast<Variable>(E)) {
128     SExpr *D;
129     do {
130       if (V->kind() != Variable::VK_Let)
131         return V;
132       D = V->definition();
133       auto *V2 = dyn_cast<Variable>(D);
134       if (V2)
135         V = V2;
136       else
137         break;
138     } while (true);
139 
140     if (ThreadSafetyTIL::isTrivial(D))
141       return D;
142 
143     if (Phi *Ph = dyn_cast<Phi>(D)) {
144       if (Ph->status() == Phi::PH_Incomplete)
145         simplifyIncompleteArg(V, Ph);
146 
147       if (Ph->status() == Phi::PH_SingleVal) {
148         E = Ph->values()[0];
149         continue;
150       }
151     }
152     return V;
153   }
154   return E;
155 }
156 
157 
158 
159 // Trace the arguments of an incomplete Phi node to see if they have the same
160 // canonical definition.  If so, mark the Phi node as redundant.
161 // getCanonicalVal() will recursively call simplifyIncompletePhi().
162 void simplifyIncompleteArg(Variable *V, til::Phi *Ph) {
163   assert(Ph && Ph->status() == Phi::PH_Incomplete);
164 
165   // eliminate infinite recursion -- assume that this node is not redundant.
166   Ph->setStatus(Phi::PH_MultiVal);
167 
168   SExpr *E0 = simplifyToCanonicalVal(Ph->values()[0]);
169   for (unsigned i=1, n=Ph->values().size(); i<n; ++i) {
170     SExpr *Ei = simplifyToCanonicalVal(Ph->values()[i]);
171     if (Ei == V)
172       continue;  // Recursive reference to itself.  Don't count.
173     if (Ei != E0) {
174       return;    // Status is already set to MultiVal.
175     }
176   }
177   Ph->setStatus(Phi::PH_SingleVal);
178   // Eliminate Redundant Phi node.
179   V->setDefinition(Ph->values()[0]);
180 }
181 
182 
183 }  // end namespace til
184 }  // end namespace threadSafety
185 }  // end namespace clang
186 
187