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 <algorithm>
32 #include <climits>
33 #include <vector>
34 
35 
36 namespace clang {
37 namespace threadSafety {
38 
39 typedef SExprBuilder::CallingContext CallingContext;
40 
41 
42 til::SExpr *SExprBuilder::lookupStmt(const Stmt *S) {
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 til::SCFG *SExprBuilder::buildCFG(CFGWalker &Walker) {
55   Walker.walk(*this);
56   return Scfg;
57 }
58 
59 
60 // Translate a clang statement or expression to a TIL expression.
61 // Also performs substitution of variables; Ctx provides the context.
62 // Dispatches on the type of S.
63 til::SExpr *SExprBuilder::translate(const Stmt *S, CallingContext *Ctx) {
64   if (!S)
65     return nullptr;
66 
67   // Check if S has already been translated and cached.
68   // This handles the lookup of SSA names for DeclRefExprs here.
69   if (til::SExpr *E = lookupStmt(S))
70     return E;
71 
72   switch (S->getStmtClass()) {
73   case Stmt::DeclRefExprClass:
74     return translateDeclRefExpr(cast<DeclRefExpr>(S), Ctx);
75   case Stmt::CXXThisExprClass:
76     return translateCXXThisExpr(cast<CXXThisExpr>(S), Ctx);
77   case Stmt::MemberExprClass:
78     return translateMemberExpr(cast<MemberExpr>(S), Ctx);
79   case Stmt::CallExprClass:
80     return translateCallExpr(cast<CallExpr>(S), Ctx);
81   case Stmt::CXXMemberCallExprClass:
82     return translateCXXMemberCallExpr(cast<CXXMemberCallExpr>(S), Ctx);
83   case Stmt::CXXOperatorCallExprClass:
84     return translateCXXOperatorCallExpr(cast<CXXOperatorCallExpr>(S), Ctx);
85   case Stmt::UnaryOperatorClass:
86     return translateUnaryOperator(cast<UnaryOperator>(S), Ctx);
87   case Stmt::BinaryOperatorClass:
88     return translateBinaryOperator(cast<BinaryOperator>(S), Ctx);
89 
90   case Stmt::ArraySubscriptExprClass:
91     return translateArraySubscriptExpr(cast<ArraySubscriptExpr>(S), Ctx);
92   case Stmt::ConditionalOperatorClass:
93     return translateConditionalOperator(cast<ConditionalOperator>(S), Ctx);
94   case Stmt::BinaryConditionalOperatorClass:
95     return translateBinaryConditionalOperator(
96              cast<BinaryConditionalOperator>(S), Ctx);
97 
98   // We treat these as no-ops
99   case Stmt::ParenExprClass:
100     return translate(cast<ParenExpr>(S)->getSubExpr(), Ctx);
101   case Stmt::ExprWithCleanupsClass:
102     return translate(cast<ExprWithCleanups>(S)->getSubExpr(), Ctx);
103   case Stmt::CXXBindTemporaryExprClass:
104     return translate(cast<CXXBindTemporaryExpr>(S)->getSubExpr(), Ctx);
105 
106   // Collect all literals
107   case Stmt::CharacterLiteralClass:
108   case Stmt::CXXNullPtrLiteralExprClass:
109   case Stmt::GNUNullExprClass:
110   case Stmt::CXXBoolLiteralExprClass:
111   case Stmt::FloatingLiteralClass:
112   case Stmt::ImaginaryLiteralClass:
113   case Stmt::IntegerLiteralClass:
114   case Stmt::StringLiteralClass:
115   case Stmt::ObjCStringLiteralClass:
116     return new (Arena) til::Literal(cast<Expr>(S));
117 
118   case Stmt::DeclStmtClass:
119     return translateDeclStmt(cast<DeclStmt>(S), Ctx);
120   default:
121     break;
122   }
123   if (const CastExpr *CE = dyn_cast<CastExpr>(S))
124     return translateCastExpr(CE, Ctx);
125 
126   return new (Arena) til::Undefined(S);
127 }
128 
129 
130 til::SExpr *SExprBuilder::translateDeclRefExpr(const DeclRefExpr *DRE,
131                                                CallingContext *Ctx) {
132   const ValueDecl *VD = cast<ValueDecl>(DRE->getDecl()->getCanonicalDecl());
133 
134   // Function parameters require substitution and/or renaming.
135   if (const ParmVarDecl *PV = dyn_cast_or_null<ParmVarDecl>(VD)) {
136     const FunctionDecl *FD =
137         cast<FunctionDecl>(PV->getDeclContext())->getCanonicalDecl();
138     unsigned I = PV->getFunctionScopeIndex();
139 
140     if (Ctx && Ctx->FunArgs && FD == Ctx->AttrDecl->getCanonicalDecl()) {
141       // Substitute call arguments for references to function parameters
142       assert(I < Ctx->NumArgs);
143       return translate(Ctx->FunArgs[I], Ctx->Prev);
144     }
145     // Map the param back to the param of the original function declaration
146     // for consistent comparisons.
147     VD = FD->getParamDecl(I);
148   }
149 
150   // For non-local variables, treat it as a referenced to a named object.
151   return new (Arena) til::LiteralPtr(VD);
152 }
153 
154 
155 til::SExpr *SExprBuilder::translateCXXThisExpr(const CXXThisExpr *TE,
156                                                CallingContext *Ctx) {
157   // Substitute for 'this'
158   if (Ctx && Ctx->SelfArg)
159     return translate(Ctx->SelfArg, Ctx->Prev);
160   assert(SelfVar && "We have no variable for 'this'!");
161   return SelfVar;
162 }
163 
164 
165 til::SExpr *SExprBuilder::translateMemberExpr(const MemberExpr *ME,
166                                               CallingContext *Ctx) {
167   til::SExpr *E = translate(ME->getBase(), Ctx);
168   E = new (Arena) til::SApply(E);
169   return new (Arena) til::Project(E, ME->getMemberDecl());
170 }
171 
172 
173 til::SExpr *SExprBuilder::translateCallExpr(const CallExpr *CE,
174                                             CallingContext *Ctx) {
175   // TODO -- Lock returned
176   til::SExpr *E = translate(CE->getCallee(), Ctx);
177   for (const auto *Arg : CE->arguments()) {
178     til::SExpr *A = translate(Arg, Ctx);
179     E = new (Arena) til::Apply(E, A);
180   }
181   return new (Arena) til::Call(E, CE);
182 }
183 
184 
185 til::SExpr *SExprBuilder::translateCXXMemberCallExpr(
186     const CXXMemberCallExpr *ME, CallingContext *Ctx) {
187   return translateCallExpr(cast<CallExpr>(ME), Ctx);
188 }
189 
190 
191 til::SExpr *SExprBuilder::translateCXXOperatorCallExpr(
192     const CXXOperatorCallExpr *OCE, CallingContext *Ctx) {
193   return translateCallExpr(cast<CallExpr>(OCE), Ctx);
194 }
195 
196 
197 til::SExpr *SExprBuilder::translateUnaryOperator(const UnaryOperator *UO,
198                                                  CallingContext *Ctx) {
199   switch (UO->getOpcode()) {
200   case UO_PostInc:
201   case UO_PostDec:
202   case UO_PreInc:
203   case UO_PreDec:
204     return new (Arena) til::Undefined(UO);
205 
206   // We treat these as no-ops
207   case UO_AddrOf:
208   case UO_Deref:
209   case UO_Plus:
210     return translate(UO->getSubExpr(), Ctx);
211 
212   case UO_Minus:
213   case UO_Not:
214   case UO_LNot:
215   case UO_Real:
216   case UO_Imag:
217   case UO_Extension:
218     return new (Arena)
219         til::UnaryOp(UO->getOpcode(), translate(UO->getSubExpr(), Ctx));
220   }
221   return new (Arena) til::Undefined(UO);
222 }
223 
224 
225 til::SExpr *SExprBuilder::translateBinaryOperator(const BinaryOperator *BO,
226                                                   CallingContext *Ctx) {
227   switch (BO->getOpcode()) {
228   case BO_PtrMemD:
229   case BO_PtrMemI:
230     return new (Arena) til::Undefined(BO);
231 
232   case BO_Mul:
233   case BO_Div:
234   case BO_Rem:
235   case BO_Add:
236   case BO_Sub:
237   case BO_Shl:
238   case BO_Shr:
239   case BO_LT:
240   case BO_GT:
241   case BO_LE:
242   case BO_GE:
243   case BO_EQ:
244   case BO_NE:
245   case BO_And:
246   case BO_Xor:
247   case BO_Or:
248   case BO_LAnd:
249   case BO_LOr:
250     return new (Arena)
251         til::BinaryOp(BO->getOpcode(), translate(BO->getLHS(), Ctx),
252                       translate(BO->getRHS(), Ctx));
253 
254   case BO_Assign: {
255     const Expr *LHS = BO->getLHS();
256     if (const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(LHS)) {
257       const Expr *RHS = BO->getRHS();
258       til::SExpr *E1 = translate(RHS, Ctx);
259       return updateVarDecl(DRE->getDecl(), E1);
260     }
261     til::SExpr *E0 = translate(LHS, Ctx);
262     til::SExpr *E1 = translate(BO->getRHS(), Ctx);
263     return new (Arena) til::Store(E0, E1);
264   }
265   case BO_MulAssign:
266   case BO_DivAssign:
267   case BO_RemAssign:
268   case BO_AddAssign:
269   case BO_SubAssign:
270   case BO_ShlAssign:
271   case BO_ShrAssign:
272   case BO_AndAssign:
273   case BO_XorAssign:
274   case BO_OrAssign:
275     return new (Arena) til::Undefined(BO);
276 
277   case BO_Comma:
278     // TODO: handle LHS
279     return translate(BO->getRHS(), Ctx);
280   }
281 
282   return new (Arena) til::Undefined(BO);
283 }
284 
285 
286 til::SExpr *SExprBuilder::translateCastExpr(const CastExpr *CE,
287                                             CallingContext *Ctx) {
288   clang::CastKind K = CE->getCastKind();
289   switch (K) {
290   case CK_LValueToRValue: {
291     if (const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(CE->getSubExpr())) {
292       til::SExpr *E0 = lookupVarDecl(DRE->getDecl());
293       if (E0)
294         return E0;
295     }
296     til::SExpr *E0 = translate(CE->getSubExpr(), Ctx);
297     return new (Arena) til::Load(E0);
298   }
299   case CK_NoOp:
300   case CK_DerivedToBase:
301   case CK_UncheckedDerivedToBase:
302   case CK_ArrayToPointerDecay:
303   case CK_FunctionToPointerDecay: {
304     til::SExpr *E0 = translate(CE->getSubExpr(), Ctx);
305     return E0;
306   }
307   default: {
308     til::SExpr *E0 = translate(CE->getSubExpr(), Ctx);
309     return new (Arena) til::Cast(K, E0);
310   }
311   }
312 }
313 
314 
315 til::SExpr *
316 SExprBuilder::translateArraySubscriptExpr(const ArraySubscriptExpr *E,
317                                           CallingContext *Ctx) {
318   return new (Arena) til::Undefined(E);
319 }
320 
321 
322 til::SExpr *
323 SExprBuilder::translateConditionalOperator(const ConditionalOperator *C,
324                                            CallingContext *Ctx) {
325   return new (Arena) til::Undefined(C);
326 }
327 
328 
329 til::SExpr *SExprBuilder::translateBinaryConditionalOperator(
330     const BinaryConditionalOperator *C, CallingContext *Ctx) {
331   return new (Arena) til::Undefined(C);
332 }
333 
334 
335 til::SExpr *
336 SExprBuilder::translateDeclStmt(const DeclStmt *S, CallingContext *Ctx) {
337   DeclGroupRef DGrp = S->getDeclGroup();
338   for (DeclGroupRef::iterator I = DGrp.begin(), E = DGrp.end(); I != E; ++I) {
339     if (VarDecl *VD = dyn_cast_or_null<VarDecl>(*I)) {
340       Expr *E = VD->getInit();
341       til::SExpr* SE = translate(E, Ctx);
342 
343       // Add local variables with trivial type to the variable map
344       QualType T = VD->getType();
345       if (T.isTrivialType(VD->getASTContext())) {
346         return addVarDecl(VD, SE);
347       }
348       else {
349         // TODO: add alloca
350       }
351     }
352   }
353   return nullptr;
354 }
355 
356 
357 // If (E) is non-trivial, then add it to the current basic block, and
358 // update the statement map so that S refers to E.  Returns a new variable
359 // that refers to E.
360 // If E is trivial returns E.
361 til::SExpr *SExprBuilder::addStatement(til::SExpr* E, const Stmt *S,
362                                        const ValueDecl *VD) {
363   if (!E)
364     return nullptr;
365   if (til::ThreadSafetyTIL::isTrivial(E))
366     return E;
367 
368   til::Variable *V = new (Arena) til::Variable(E, VD);
369   V->setID(CurrentBlockID, CurrentVarID++);
370   CurrentBB->addInstr(V);
371   if (S)
372     insertStmt(S, V);
373   return V;
374 }
375 
376 
377 // Returns the current value of VD, if known, and nullptr otherwise.
378 til::SExpr *SExprBuilder::lookupVarDecl(const ValueDecl *VD) {
379   auto It = IdxMap.find(VD);
380   if (It != IdxMap.end())
381     return CurrentNameMap[It->second].second;
382   return nullptr;
383 }
384 
385 
386 // if E is a til::Variable, update its clangDecl.
387 inline void maybeUpdateVD(til::SExpr *E, const ValueDecl *VD) {
388   if (!E)
389     return;
390   if (til::Variable *V = dyn_cast<til::Variable>(E)) {
391     if (!V->clangDecl())
392       V->setClangDecl(VD);
393   }
394 }
395 
396 // Adds a new variable declaration.
397 til::SExpr *SExprBuilder::addVarDecl(const ValueDecl *VD, til::SExpr *E) {
398   maybeUpdateVD(E, VD);
399   IdxMap.insert(std::make_pair(VD, CurrentNameMap.size()));
400   CurrentNameMap.makeWritable();
401   CurrentNameMap.push_back(std::make_pair(VD, E));
402   return E;
403 }
404 
405 
406 // Updates a current variable declaration.  (E.g. by assignment)
407 til::SExpr *SExprBuilder::updateVarDecl(const ValueDecl *VD, til::SExpr *E) {
408   maybeUpdateVD(E, VD);
409   auto It = IdxMap.find(VD);
410   if (It == IdxMap.end()) {
411     til::SExpr *Ptr = new (Arena) til::LiteralPtr(VD);
412     til::SExpr *St  = new (Arena) til::Store(Ptr, E);
413     return St;
414   }
415   CurrentNameMap.makeWritable();
416   CurrentNameMap.elem(It->second).second = E;
417   return E;
418 }
419 
420 
421 // Merge values from Map into the current entry map.
422 void SExprBuilder::mergeEntryMap(NameVarMap Map) {
423   assert(CurrentBlockInfo && "Not processing a block!");
424 
425   if (!CurrentNameMap.valid()) {
426     // Steal Map, using copy-on-write.
427     CurrentNameMap = std::move(Map);
428     return;
429   }
430   if (CurrentNameMap.sameAs(Map))
431     return;  // Easy merge: maps from different predecessors are unchanged.
432 
433   unsigned ESz = CurrentNameMap.size();
434   unsigned MSz = Map.size();
435   unsigned Sz = std::max(ESz, MSz);
436   bool W = CurrentNameMap.writable();
437   for (unsigned i=0; i<Sz; ++i) {
438     if (CurrentNameMap[i].first != Map[i].first) {
439       if (!W)
440         CurrentNameMap.makeWritable();
441       CurrentNameMap.downsize(i);
442       break;
443     }
444     if (CurrentNameMap[i].second != Map[i].second) {
445       til::Variable *V =
446         dyn_cast<til::Variable>(CurrentNameMap[i].second);
447       if (V && V->getBlockID() == CurrentBB->blockID()) {
448         // We already have a Phi node, so add the new variable.
449         til::Phi *Ph = dyn_cast<til::Phi>(V->definition());
450         assert(Ph && "Expecting Phi node.");
451         Ph->values()[CurrentArgIndex] = Map[i].second;
452       }
453       else {
454         if (!W)
455           CurrentNameMap.makeWritable();
456         unsigned NPreds = CurrentBB->numPredecessors();
457         assert(CurrentArgIndex > 0 && CurrentArgIndex < NPreds);
458 
459         // Make a new phi node.  All phi args up to the current index must
460         // be the same, and equal to the current NameMap value.
461         auto *Ph = new (Arena) til::Phi(Arena, NPreds);
462         Ph->values().setValues(NPreds, nullptr);
463         for (unsigned PIdx = 0; PIdx < CurrentArgIndex; ++PIdx)
464           Ph->values()[PIdx] = CurrentNameMap[i].second;
465         Ph->values()[CurrentArgIndex] = Map[i].second;
466 
467         // Add phi node to current basic block.
468         auto *Var = new (Arena) til::Variable(Ph, CurrentNameMap[i].first);
469         Var->setID(CurrentBlockID, CurrentVarID++);
470         CurrentBB->addArgument(Var);
471         CurrentNameMap.elem(i).second = Var;
472       }
473     }
474   }
475   if (ESz > MSz) {
476     if (!W)
477       CurrentNameMap.makeWritable();
478     CurrentNameMap.downsize(Map.size());
479   }
480 }
481 
482 
483 
484 void SExprBuilder::enterCFG(CFG *Cfg, const NamedDecl *D,
485                             const CFGBlock *First) {
486   // Perform initial setup operations.
487   unsigned NBlocks = Cfg->getNumBlockIDs();
488   Scfg = new (Arena) til::SCFG(Arena, NBlocks);
489 
490   // allocate all basic blocks immediately, to handle forward references.
491   BlockMap.reserve(NBlocks);
492   BBInfo.resize(NBlocks);
493   for (auto *B : *Cfg) {
494     auto *BB = new (Arena) til::BasicBlock(Arena, 0, B->size());
495     BlockMap.push_back(BB);
496   }
497   CallCtx = new SExprBuilder::CallingContext(D);
498 }
499 
500 
501 
502 void SExprBuilder::enterCFGBlock(const CFGBlock *B) {
503   // Intialize TIL basic block and add it to the CFG.
504   CurrentBB = BlockMap[B->getBlockID()];
505   CurrentBB->setBlockID(CurrentBlockID);
506   CurrentBB->setNumPredecessors(B->pred_size());
507   Scfg->add(CurrentBB);
508 
509   CurrentBlockInfo = &BBInfo[B->getBlockID()];
510   CurrentVarID = 0;
511   CurrentArgIndex = 0;
512 
513   assert(!CurrentNameMap.valid() && "CurrentNameMap already initialized.");
514 }
515 
516 
517 void SExprBuilder::handlePredecessor(const CFGBlock *Pred) {
518   // Compute CurrentNameMap on entry from ExitMaps of predecessors
519 
520   BlockInfo *PredInfo = &BBInfo[Pred->getBlockID()];
521   assert(PredInfo->SuccessorsToProcess > 0);
522 
523   if (--PredInfo->SuccessorsToProcess == 0)
524     mergeEntryMap(std::move(PredInfo->ExitMap));
525   else
526     mergeEntryMap(PredInfo->ExitMap.clone());
527 
528   ++CurrentArgIndex;
529 }
530 
531 
532 void SExprBuilder::handlePredecessorBackEdge(const CFGBlock *Pred) {
533   CurrentBlockInfo->HasBackEdges = true;
534 }
535 
536 
537 void SExprBuilder::enterCFGBlockBody(const CFGBlock *B) { }
538 
539 
540 void SExprBuilder::handleStatement(const Stmt *S) {
541   til::SExpr *E = translate(S, CallCtx);
542   addStatement(E, S);
543 }
544 
545 
546 void SExprBuilder::handleDestructorCall(const VarDecl *VD,
547                                         const CXXDestructorDecl *DD) {
548   til::SExpr *Sf = new (Arena) til::LiteralPtr(VD);
549   til::SExpr *Dr = new (Arena) til::LiteralPtr(DD);
550   til::SExpr *Ap = new (Arena) til::Apply(Dr, Sf);
551   til::SExpr *E = new (Arena) til::Call(Ap);
552   addStatement(E, nullptr);
553 }
554 
555 
556 
557 void SExprBuilder::exitCFGBlockBody(const CFGBlock *B) {
558   unsigned N = B->succ_size();
559   auto It = B->succ_begin();
560   if (N == 1) {
561     til::BasicBlock *BB = *It ? BlockMap[(*It)->getBlockID()] : nullptr;
562     // TODO: set index
563     til::SExpr *Tm = new (Arena) til::Goto(BB, 0);
564     CurrentBB->setTerminator(Tm);
565   }
566   else if (N == 2) {
567     til::SExpr *C = translate(B->getTerminatorCondition(true), CallCtx);
568     til::BasicBlock *BB1 = *It ? BlockMap[(*It)->getBlockID()] : nullptr;
569     ++It;
570     til::BasicBlock *BB2 = *It ? BlockMap[(*It)->getBlockID()] : nullptr;
571     // TODO: set conditional, set index
572     til::SExpr *Tm = new (Arena) til::Branch(C, BB1, BB2);
573     CurrentBB->setTerminator(Tm);
574   }
575 }
576 
577 
578 void SExprBuilder::handleSuccessor(const CFGBlock *Succ) {
579   ++CurrentBlockInfo->SuccessorsToProcess;
580 }
581 
582 
583 void SExprBuilder::handleSuccessorBackEdge(const CFGBlock *Succ) {
584 
585 }
586 
587 
588 void SExprBuilder::exitCFGBlock(const CFGBlock *B) {
589   CurrentBlockInfo->ExitMap = std::move(CurrentNameMap);
590   CurrentBlockID++;
591   CurrentBB = nullptr;
592   CurrentBlockInfo = nullptr;
593 }
594 
595 
596 void SExprBuilder::exitCFG(const CFGBlock *Last) {
597   CurrentBlockID = 0;
598   CurrentVarID = 0;
599   CurrentArgIndex = 0;
600   delete CallCtx;
601 }
602 
603 
604 
605 class LLVMPrinter : public til::PrettyPrinter<LLVMPrinter, llvm::raw_ostream> {
606 };
607 
608 
609 void printSCFG(CFGWalker &Walker) {
610   llvm::BumpPtrAllocator Bpa;
611   til::MemRegionRef Arena(&Bpa);
612   SExprBuilder builder(Arena);
613   til::SCFG *Cfg = builder.buildCFG(Walker);
614   LLVMPrinter::print(Cfg, llvm::errs());
615 }
616 
617 
618 
619 } // end namespace threadSafety
620 
621 } // end namespace clang
622