1 //===- ThreadSafetyCommon.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 for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // Implementation of the interfaces declared in ThreadSafetyCommon.h
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "clang/Analysis/Analyses/ThreadSafetyCommon.h"
15 #include "clang/AST/Attr.h"
16 #include "clang/AST/DeclCXX.h"
17 #include "clang/AST/ExprCXX.h"
18 #include "clang/AST/StmtCXX.h"
19 #include "clang/Analysis/Analyses/PostOrderCFGView.h"
20 #include "clang/Analysis/Analyses/ThreadSafetyTIL.h"
21 #include "clang/Analysis/Analyses/ThreadSafetyTraverse.h"
22 #include "clang/Analysis/AnalysisContext.h"
23 #include "clang/Analysis/CFG.h"
24 #include "clang/Basic/OperatorKinds.h"
25 #include "clang/Basic/SourceLocation.h"
26 #include "clang/Basic/SourceManager.h"
27 #include "llvm/ADT/DenseMap.h"
28 #include "llvm/ADT/SmallVector.h"
29 #include "llvm/ADT/StringRef.h"
30 
31 #include <vector>
32 
33 
34 namespace clang {
35 namespace threadSafety {
36 
37 typedef SExprBuilder::CallingContext CallingContext;
38 
39 
40 til::SExpr *SExprBuilder::lookupStmt(const Stmt *S) {
41   if (!SMap)
42     return nullptr;
43   auto It = SMap->find(S);
44   if (It != SMap->end())
45     return It->second;
46   return nullptr;
47 }
48 
49 void SExprBuilder::insertStmt(const Stmt *S, til::Variable *V) {
50   SMap->insert(std::make_pair(S, V));
51 }
52 
53 
54 // Translate a clang statement or expression to a TIL expression.
55 // Also performs substitution of variables; Ctx provides the context.
56 // Dispatches on the type of S.
57 til::SExpr *SExprBuilder::translate(const Stmt *S, CallingContext *Ctx) {
58   // Check if S has already been translated and cached.
59   // This handles the lookup of SSA names for DeclRefExprs here.
60   if (til::SExpr *E = lookupStmt(S))
61     return E;
62 
63   switch (S->getStmtClass()) {
64   case Stmt::DeclRefExprClass:
65     return translateDeclRefExpr(cast<DeclRefExpr>(S), Ctx);
66   case Stmt::CXXThisExprClass:
67     return translateCXXThisExpr(cast<CXXThisExpr>(S), Ctx);
68   case Stmt::MemberExprClass:
69     return translateMemberExpr(cast<MemberExpr>(S), Ctx);
70   case Stmt::CallExprClass:
71     return translateCallExpr(cast<CallExpr>(S), Ctx);
72   case Stmt::CXXMemberCallExprClass:
73     return translateCXXMemberCallExpr(cast<CXXMemberCallExpr>(S), Ctx);
74   case Stmt::CXXOperatorCallExprClass:
75     return translateCXXOperatorCallExpr(cast<CXXOperatorCallExpr>(S), Ctx);
76   case Stmt::UnaryOperatorClass:
77     return translateUnaryOperator(cast<UnaryOperator>(S), Ctx);
78   case Stmt::BinaryOperatorClass:
79     return translateBinaryOperator(cast<BinaryOperator>(S), Ctx);
80 
81   case Stmt::ArraySubscriptExprClass:
82     return translateArraySubscriptExpr(cast<ArraySubscriptExpr>(S), Ctx);
83   case Stmt::ConditionalOperatorClass:
84     return translateConditionalOperator(cast<ConditionalOperator>(S), Ctx);
85   case Stmt::BinaryConditionalOperatorClass:
86     return translateBinaryConditionalOperator(
87              cast<BinaryConditionalOperator>(S), Ctx);
88 
89   // We treat these as no-ops
90   case Stmt::ParenExprClass:
91     return translate(cast<ParenExpr>(S)->getSubExpr(), Ctx);
92   case Stmt::ExprWithCleanupsClass:
93     return translate(cast<ExprWithCleanups>(S)->getSubExpr(), Ctx);
94   case Stmt::CXXBindTemporaryExprClass:
95     return translate(cast<CXXBindTemporaryExpr>(S)->getSubExpr(), Ctx);
96 
97   // Collect all literals
98   case Stmt::CharacterLiteralClass:
99   case Stmt::CXXNullPtrLiteralExprClass:
100   case Stmt::GNUNullExprClass:
101   case Stmt::CXXBoolLiteralExprClass:
102   case Stmt::FloatingLiteralClass:
103   case Stmt::ImaginaryLiteralClass:
104   case Stmt::IntegerLiteralClass:
105   case Stmt::StringLiteralClass:
106   case Stmt::ObjCStringLiteralClass:
107     return new (Arena) til::Literal(cast<Expr>(S));
108   default:
109     break;
110   }
111   if (const CastExpr *CE = dyn_cast<CastExpr>(S))
112     return translateCastExpr(CE, Ctx);
113 
114   return new (Arena) til::Undefined(S);
115 }
116 
117 
118 til::SExpr *SExprBuilder::translateDeclRefExpr(const DeclRefExpr *DRE,
119                                                CallingContext *Ctx) {
120   const ValueDecl *VD = cast<ValueDecl>(DRE->getDecl()->getCanonicalDecl());
121 
122   // Function parameters require substitution and/or renaming.
123   if (const ParmVarDecl *PV = dyn_cast_or_null<ParmVarDecl>(VD)) {
124     const FunctionDecl *FD =
125         cast<FunctionDecl>(PV->getDeclContext())->getCanonicalDecl();
126     unsigned I = PV->getFunctionScopeIndex();
127 
128     if (Ctx && Ctx->FunArgs && FD == Ctx->AttrDecl->getCanonicalDecl()) {
129       // Substitute call arguments for references to function parameters
130       assert(I < Ctx->NumArgs);
131       return translate(Ctx->FunArgs[I], Ctx->Prev);
132     }
133     // Map the param back to the param of the original function declaration
134     // for consistent comparisons.
135     VD = FD->getParamDecl(I);
136   }
137 
138   // For non-local variables, treat it as a referenced to a named object.
139   return new (Arena) til::LiteralPtr(VD);
140 }
141 
142 
143 til::SExpr *SExprBuilder::translateCXXThisExpr(const CXXThisExpr *TE,
144                                                CallingContext *Ctx) {
145   // Substitute for 'this'
146   if (Ctx && Ctx->SelfArg)
147     return translate(Ctx->SelfArg, Ctx->Prev);
148   assert(SelfVar && "We have no variable for 'this'!");
149   return SelfVar;
150 }
151 
152 
153 til::SExpr *SExprBuilder::translateMemberExpr(const MemberExpr *ME,
154                                               CallingContext *Ctx) {
155   til::SExpr *E = translate(ME->getBase(), Ctx);
156   E = new (Arena) til::SApply(E);
157   return new (Arena) til::Project(E, ME->getMemberDecl());
158 }
159 
160 
161 til::SExpr *SExprBuilder::translateCallExpr(const CallExpr *CE,
162                                             CallingContext *Ctx) {
163   // TODO -- Lock returned
164   til::SExpr *E = translate(CE->getCallee(), Ctx);
165   for (const auto *Arg : CE->arguments()) {
166     til::SExpr *A = translate(Arg, Ctx);
167     E = new (Arena) til::Apply(E, A);
168   }
169   return new (Arena) til::Call(E, CE);
170 }
171 
172 
173 til::SExpr *SExprBuilder::translateCXXMemberCallExpr(
174     const CXXMemberCallExpr *ME, CallingContext *Ctx) {
175   return translateCallExpr(cast<CallExpr>(ME), Ctx);
176 }
177 
178 
179 til::SExpr *SExprBuilder::translateCXXOperatorCallExpr(
180     const CXXOperatorCallExpr *OCE, CallingContext *Ctx) {
181   return translateCallExpr(cast<CallExpr>(OCE), Ctx);
182 }
183 
184 
185 til::SExpr *SExprBuilder::translateUnaryOperator(const UnaryOperator *UO,
186                                                  CallingContext *Ctx) {
187   switch (UO->getOpcode()) {
188   case UO_PostInc:
189   case UO_PostDec:
190   case UO_PreInc:
191   case UO_PreDec:
192     return new (Arena) til::Undefined(UO);
193 
194   // We treat these as no-ops
195   case UO_AddrOf:
196   case UO_Deref:
197   case UO_Plus:
198     return translate(UO->getSubExpr(), Ctx);
199 
200   case UO_Minus:
201   case UO_Not:
202   case UO_LNot:
203   case UO_Real:
204   case UO_Imag:
205   case UO_Extension:
206     return new (Arena)
207         til::UnaryOp(UO->getOpcode(), translate(UO->getSubExpr(), Ctx));
208   }
209   return new (Arena) til::Undefined(UO);
210 }
211 
212 til::SExpr *SExprBuilder::translateBinaryOperator(const BinaryOperator *BO,
213                                                   CallingContext *Ctx) {
214   switch (BO->getOpcode()) {
215   case BO_PtrMemD:
216   case BO_PtrMemI:
217     return new (Arena) til::Undefined(BO);
218 
219   case BO_Mul:
220   case BO_Div:
221   case BO_Rem:
222   case BO_Add:
223   case BO_Sub:
224   case BO_Shl:
225   case BO_Shr:
226   case BO_LT:
227   case BO_GT:
228   case BO_LE:
229   case BO_GE:
230   case BO_EQ:
231   case BO_NE:
232   case BO_And:
233   case BO_Xor:
234   case BO_Or:
235   case BO_LAnd:
236   case BO_LOr:
237     return new (Arena)
238         til::BinaryOp(BO->getOpcode(), translate(BO->getLHS(), Ctx),
239                       translate(BO->getRHS(), Ctx));
240 
241   case BO_Assign:
242     return new (Arena)
243         til::Store(translate(BO->getLHS(), Ctx), translate(BO->getRHS(), Ctx));
244 
245   case BO_MulAssign:
246   case BO_DivAssign:
247   case BO_RemAssign:
248   case BO_AddAssign:
249   case BO_SubAssign:
250   case BO_ShlAssign:
251   case BO_ShrAssign:
252   case BO_AndAssign:
253   case BO_XorAssign:
254   case BO_OrAssign:
255     return new (Arena) til::Undefined(BO);
256 
257   case BO_Comma:
258     // TODO: handle LHS
259     return translate(BO->getRHS(), Ctx);
260   }
261 
262   return new (Arena) til::Undefined(BO);
263 }
264 
265 
266 til::SExpr *SExprBuilder::translateCastExpr(const CastExpr *CE,
267                                             CallingContext *Ctx) {
268   til::SExpr *E0 = translate(CE->getSubExpr(), Ctx);
269 
270   clang::CastKind K = CE->getCastKind();
271   switch (K) {
272   case CK_LValueToRValue:
273     return new (Arena) til::Load(E0);
274 
275   case CK_NoOp:
276   case CK_DerivedToBase:
277   case CK_UncheckedDerivedToBase:
278   case CK_ArrayToPointerDecay:
279   case CK_FunctionToPointerDecay:
280     return E0;
281 
282   default:
283     return new (Arena) til::Cast(K, E0);
284   }
285 }
286 
287 til::SExpr *
288 SExprBuilder::translateArraySubscriptExpr(const ArraySubscriptExpr *E,
289                                           CallingContext *Ctx) {
290   return new (Arena) til::Undefined(E);
291 }
292 
293 til::SExpr *
294 SExprBuilder::translateConditionalOperator(const ConditionalOperator *C,
295                                            CallingContext *Ctx) {
296   return new (Arena) til::Undefined(C);
297 }
298 
299 til::SExpr *SExprBuilder::translateBinaryConditionalOperator(
300     const BinaryConditionalOperator *C, CallingContext *Ctx) {
301   return new (Arena) til::Undefined(C);
302 }
303 
304 
305 
306 // Build a complete SCFG from a clang CFG.
307 class SCFGBuilder {
308   class BBInfo {
309 
310   };
311 
312   void addStatement(til::SExpr* E, const Stmt *S) {
313     if (!E)
314       return;
315     if (til::ThreadSafetyTIL::isTrivial(E))
316       return;
317 
318     til::Variable *V = new (Arena) til::Variable(til::Variable::VK_Let, E);
319     V->setID(CurrentBlockID, CurrentVarID++);
320     CurrentBB->addInstr(V);
321     if (S)
322       BuildEx.insertStmt(S, V);
323   }
324 
325 public:
326   // Enter the CFG for Decl D, and perform any initial setup operations.
327   void enterCFG(CFG *Cfg, const NamedDecl *D, const CFGBlock *First) {
328     Scfg = new (Arena) til::SCFG(Arena, Cfg->getNumBlockIDs());
329     CallCtx = new SExprBuilder::CallingContext(D);
330   }
331 
332   // Enter a CFGBlock.
333   void enterCFGBlock(const CFGBlock *B) {
334     CurrentBB = new (Arena) til::BasicBlock(Arena, 0, B->size());
335     CurrentBB->setBlockID(CurrentBlockID);
336     CurrentVarID = 0;
337     Scfg->add(CurrentBB);
338   }
339 
340   // Process an ordinary statement.
341   void handleStatement(const Stmt *S) {
342     til::SExpr *E = BuildEx.translate(S, CallCtx);
343     addStatement(E, S);
344   }
345 
346   // Process a destructor call
347   void handleDestructorCall(const VarDecl *VD, const CXXDestructorDecl *DD) {
348     til::SExpr *Sf = new (Arena) til::LiteralPtr(VD);
349     til::SExpr *Dr = new (Arena) til::LiteralPtr(DD);
350     til::SExpr *Ap = new (Arena) til::Apply(Dr, Sf);
351     til::SExpr *E = new (Arena) til::Call(Ap);
352     addStatement(E, nullptr);
353   }
354 
355   // Process a successor edge.
356   void handleSuccessor(const CFGBlock *Succ) {}
357 
358   // Process a successor back edge to a previously visited block.
359   void handleSuccessorBackEdge(const CFGBlock *Succ) {}
360 
361   // Leave a CFGBlock.
362   void exitCFGBlock(const CFGBlock *B) {
363     CurrentBlockID++;
364     CurrentBB = 0;
365   }
366 
367   // Leave the CFG, and perform any final cleanup operations.
368   void exitCFG(const CFGBlock *Last) {
369     delete CallCtx;
370     CallCtx = nullptr;
371   }
372 
373   SCFGBuilder(til::MemRegionRef A)
374       : Arena(A), Scfg(nullptr), CurrentBB(nullptr), CurrentBlockID(0),
375         CurrentVarID(0), CallCtx(nullptr),
376         SMap(new SExprBuilder::StatementMap()), BuildEx(A, SMap) {}
377   ~SCFGBuilder() { delete SMap; }
378 
379   til::SCFG *getCFG() const { return Scfg; }
380 
381 private:
382   til::MemRegionRef Arena;
383   til::SCFG *Scfg;
384   til::BasicBlock *CurrentBB;
385   unsigned CurrentBlockID;
386   unsigned CurrentVarID;
387 
388   SExprBuilder::CallingContext *CallCtx;
389   SExprBuilder::StatementMap *SMap;
390   SExprBuilder BuildEx;
391 };
392 
393 
394 
395 class LLVMPrinter :
396     public til::PrettyPrinter<LLVMPrinter, llvm::raw_ostream> {
397 };
398 
399 
400 void printSCFG(CFGWalker &walker) {
401   llvm::BumpPtrAllocator Bpa;
402   til::MemRegionRef Arena(&Bpa);
403   SCFGBuilder builder(Arena);
404   // CFGVisitor visitor;
405   walker.walk(builder);
406   LLVMPrinter::print(builder.getCFG(), llvm::errs());
407 }
408 
409 
410 
411 } // end namespace threadSafety
412 
413 } // end namespace clang
414