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