1 //== BodyFarm.cpp  - Factory for conjuring up fake bodies ----------*- 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 // BodyFarm is a factory for creating faux implementations for functions/methods
11 // for analysis purposes.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #include "clang/Analysis/BodyFarm.h"
16 #include "clang/AST/ASTContext.h"
17 #include "clang/AST/CXXInheritance.h"
18 #include "clang/AST/Decl.h"
19 #include "clang/AST/Expr.h"
20 #include "clang/AST/ExprCXX.h"
21 #include "clang/AST/ExprObjC.h"
22 #include "clang/AST/NestedNameSpecifier.h"
23 #include "clang/Analysis/CodeInjector.h"
24 #include "clang/Basic/OperatorKinds.h"
25 #include "llvm/ADT/StringSwitch.h"
26 #include "llvm/Support/Debug.h"
27 
28 #define DEBUG_TYPE "body-farm"
29 
30 using namespace clang;
31 
32 //===----------------------------------------------------------------------===//
33 // Helper creation functions for constructing faux ASTs.
34 //===----------------------------------------------------------------------===//
35 
36 static bool isDispatchBlock(QualType Ty) {
37   // Is it a block pointer?
38   const BlockPointerType *BPT = Ty->getAs<BlockPointerType>();
39   if (!BPT)
40     return false;
41 
42   // Check if the block pointer type takes no arguments and
43   // returns void.
44   const FunctionProtoType *FT =
45   BPT->getPointeeType()->getAs<FunctionProtoType>();
46   return FT && FT->getReturnType()->isVoidType() && FT->getNumParams() == 0;
47 }
48 
49 namespace {
50 class ASTMaker {
51 public:
52   ASTMaker(ASTContext &C) : C(C) {}
53 
54   /// Create a new BinaryOperator representing a simple assignment.
55   BinaryOperator *makeAssignment(const Expr *LHS, const Expr *RHS, QualType Ty);
56 
57   /// Create a new BinaryOperator representing a comparison.
58   BinaryOperator *makeComparison(const Expr *LHS, const Expr *RHS,
59                                  BinaryOperator::Opcode Op);
60 
61   /// Create a new compound stmt using the provided statements.
62   CompoundStmt *makeCompound(ArrayRef<Stmt*>);
63 
64   /// Create a new DeclRefExpr for the referenced variable.
65   DeclRefExpr *makeDeclRefExpr(const VarDecl *D,
66                                bool RefersToEnclosingVariableOrCapture = false);
67 
68   /// Create a new UnaryOperator representing a dereference.
69   UnaryOperator *makeDereference(const Expr *Arg, QualType Ty);
70 
71   /// Create an implicit cast for an integer conversion.
72   Expr *makeIntegralCast(const Expr *Arg, QualType Ty);
73 
74   /// Create an implicit cast to a builtin boolean type.
75   ImplicitCastExpr *makeIntegralCastToBoolean(const Expr *Arg);
76 
77   /// Create an implicit cast for lvalue-to-rvaluate conversions.
78   ImplicitCastExpr *makeLvalueToRvalue(const Expr *Arg, QualType Ty);
79 
80   /// Make RValue out of variable declaration, creating a temporary
81   /// DeclRefExpr in the process.
82   ImplicitCastExpr *
83   makeLvalueToRvalue(const VarDecl *Decl,
84                      bool RefersToEnclosingVariableOrCapture = false);
85 
86   /// Create an implicit cast of the given type.
87   ImplicitCastExpr *makeImplicitCast(const Expr *Arg, QualType Ty,
88                                      CastKind CK = CK_LValueToRValue);
89 
90   /// Create an Objective-C bool literal.
91   ObjCBoolLiteralExpr *makeObjCBool(bool Val);
92 
93   /// Create an Objective-C ivar reference.
94   ObjCIvarRefExpr *makeObjCIvarRef(const Expr *Base, const ObjCIvarDecl *IVar);
95 
96   /// Create a Return statement.
97   ReturnStmt *makeReturn(const Expr *RetVal);
98 
99   /// Create an integer literal expression of the given type.
100   IntegerLiteral *makeIntegerLiteral(uint64_t Value, QualType Ty);
101 
102   /// Create a member expression.
103   MemberExpr *makeMemberExpression(Expr *base, ValueDecl *MemberDecl,
104                                    bool IsArrow = false,
105                                    ExprValueKind ValueKind = VK_LValue);
106 
107   /// Returns a *first* member field of a record declaration with a given name.
108   /// \return an nullptr if no member with such a name exists.
109   ValueDecl *findMemberField(const RecordDecl *RD, StringRef Name);
110 
111 private:
112   ASTContext &C;
113 };
114 }
115 
116 BinaryOperator *ASTMaker::makeAssignment(const Expr *LHS, const Expr *RHS,
117                                          QualType Ty) {
118  return new (C) BinaryOperator(const_cast<Expr*>(LHS), const_cast<Expr*>(RHS),
119                                BO_Assign, Ty, VK_RValue,
120                                OK_Ordinary, SourceLocation(), FPOptions());
121 }
122 
123 BinaryOperator *ASTMaker::makeComparison(const Expr *LHS, const Expr *RHS,
124                                          BinaryOperator::Opcode Op) {
125   assert(BinaryOperator::isLogicalOp(Op) ||
126          BinaryOperator::isComparisonOp(Op));
127   return new (C) BinaryOperator(const_cast<Expr*>(LHS),
128                                 const_cast<Expr*>(RHS),
129                                 Op,
130                                 C.getLogicalOperationType(),
131                                 VK_RValue,
132                                 OK_Ordinary, SourceLocation(), FPOptions());
133 }
134 
135 CompoundStmt *ASTMaker::makeCompound(ArrayRef<Stmt *> Stmts) {
136   return CompoundStmt::Create(C, Stmts, SourceLocation(), SourceLocation());
137 }
138 
139 DeclRefExpr *ASTMaker::makeDeclRefExpr(
140     const VarDecl *D,
141     bool RefersToEnclosingVariableOrCapture) {
142   QualType Type = D->getType().getNonReferenceType();
143 
144   DeclRefExpr *DR = DeclRefExpr::Create(
145       C, NestedNameSpecifierLoc(), SourceLocation(), const_cast<VarDecl *>(D),
146       RefersToEnclosingVariableOrCapture, SourceLocation(), Type, VK_LValue);
147   return DR;
148 }
149 
150 UnaryOperator *ASTMaker::makeDereference(const Expr *Arg, QualType Ty) {
151   return new (C) UnaryOperator(const_cast<Expr*>(Arg), UO_Deref, Ty,
152                                VK_LValue, OK_Ordinary, SourceLocation(),
153                               /*CanOverflow*/ false);
154 }
155 
156 ImplicitCastExpr *ASTMaker::makeLvalueToRvalue(const Expr *Arg, QualType Ty) {
157   return makeImplicitCast(Arg, Ty, CK_LValueToRValue);
158 }
159 
160 ImplicitCastExpr *
161 ASTMaker::makeLvalueToRvalue(const VarDecl *Arg,
162                              bool RefersToEnclosingVariableOrCapture) {
163   QualType Type = Arg->getType().getNonReferenceType();
164   return makeLvalueToRvalue(makeDeclRefExpr(Arg,
165                                             RefersToEnclosingVariableOrCapture),
166                             Type);
167 }
168 
169 ImplicitCastExpr *ASTMaker::makeImplicitCast(const Expr *Arg, QualType Ty,
170                                              CastKind CK) {
171   return ImplicitCastExpr::Create(C, Ty,
172                                   /* CastKind=*/ CK,
173                                   /* Expr=*/ const_cast<Expr *>(Arg),
174                                   /* CXXCastPath=*/ nullptr,
175                                   /* ExprValueKind=*/ VK_RValue);
176 }
177 
178 Expr *ASTMaker::makeIntegralCast(const Expr *Arg, QualType Ty) {
179   if (Arg->getType() == Ty)
180     return const_cast<Expr*>(Arg);
181 
182   return ImplicitCastExpr::Create(C, Ty, CK_IntegralCast,
183                                   const_cast<Expr*>(Arg), nullptr, VK_RValue);
184 }
185 
186 ImplicitCastExpr *ASTMaker::makeIntegralCastToBoolean(const Expr *Arg) {
187   return ImplicitCastExpr::Create(C, C.BoolTy, CK_IntegralToBoolean,
188                                   const_cast<Expr*>(Arg), nullptr, VK_RValue);
189 }
190 
191 ObjCBoolLiteralExpr *ASTMaker::makeObjCBool(bool Val) {
192   QualType Ty = C.getBOOLDecl() ? C.getBOOLType() : C.ObjCBuiltinBoolTy;
193   return new (C) ObjCBoolLiteralExpr(Val, Ty, SourceLocation());
194 }
195 
196 ObjCIvarRefExpr *ASTMaker::makeObjCIvarRef(const Expr *Base,
197                                            const ObjCIvarDecl *IVar) {
198   return new (C) ObjCIvarRefExpr(const_cast<ObjCIvarDecl*>(IVar),
199                                  IVar->getType(), SourceLocation(),
200                                  SourceLocation(), const_cast<Expr*>(Base),
201                                  /*arrow=*/true, /*free=*/false);
202 }
203 
204 
205 ReturnStmt *ASTMaker::makeReturn(const Expr *RetVal) {
206   return new (C) ReturnStmt(SourceLocation(), const_cast<Expr*>(RetVal),
207                             nullptr);
208 }
209 
210 IntegerLiteral *ASTMaker::makeIntegerLiteral(uint64_t Value, QualType Ty) {
211   llvm::APInt APValue = llvm::APInt(C.getTypeSize(Ty), Value);
212   return IntegerLiteral::Create(C, APValue, Ty, SourceLocation());
213 }
214 
215 MemberExpr *ASTMaker::makeMemberExpression(Expr *base, ValueDecl *MemberDecl,
216                                            bool IsArrow,
217                                            ExprValueKind ValueKind) {
218 
219   DeclAccessPair FoundDecl = DeclAccessPair::make(MemberDecl, AS_public);
220   return MemberExpr::Create(
221       C, base, IsArrow, SourceLocation(), NestedNameSpecifierLoc(),
222       SourceLocation(), MemberDecl, FoundDecl,
223       DeclarationNameInfo(MemberDecl->getDeclName(), SourceLocation()),
224       /* TemplateArgumentListInfo=*/ nullptr, MemberDecl->getType(), ValueKind,
225       OK_Ordinary);
226 }
227 
228 ValueDecl *ASTMaker::findMemberField(const RecordDecl *RD, StringRef Name) {
229 
230   CXXBasePaths Paths(
231       /* FindAmbiguities=*/false,
232       /* RecordPaths=*/false,
233       /* DetectVirtual=*/ false);
234   const IdentifierInfo &II = C.Idents.get(Name);
235   DeclarationName DeclName = C.DeclarationNames.getIdentifier(&II);
236 
237   DeclContextLookupResult Decls = RD->lookup(DeclName);
238   for (NamedDecl *FoundDecl : Decls)
239     if (!FoundDecl->getDeclContext()->isFunctionOrMethod())
240       return cast<ValueDecl>(FoundDecl);
241 
242   return nullptr;
243 }
244 
245 //===----------------------------------------------------------------------===//
246 // Creation functions for faux ASTs.
247 //===----------------------------------------------------------------------===//
248 
249 typedef Stmt *(*FunctionFarmer)(ASTContext &C, const FunctionDecl *D);
250 
251 static CallExpr *create_call_once_funcptr_call(ASTContext &C, ASTMaker M,
252                                                const ParmVarDecl *Callback,
253                                                ArrayRef<Expr *> CallArgs) {
254 
255   QualType Ty = Callback->getType();
256   DeclRefExpr *Call = M.makeDeclRefExpr(Callback);
257   Expr *SubExpr;
258   if (Ty->isRValueReferenceType()) {
259     SubExpr = M.makeImplicitCast(
260         Call, Ty.getNonReferenceType(), CK_LValueToRValue);
261   } else if (Ty->isLValueReferenceType() &&
262              Call->getType()->isFunctionType()) {
263     Ty = C.getPointerType(Ty.getNonReferenceType());
264     SubExpr = M.makeImplicitCast(Call, Ty, CK_FunctionToPointerDecay);
265   } else if (Ty->isLValueReferenceType()
266              && Call->getType()->isPointerType()
267              && Call->getType()->getPointeeType()->isFunctionType()){
268     SubExpr = Call;
269   } else {
270     llvm_unreachable("Unexpected state");
271   }
272 
273   return new (C)
274       CallExpr(C, SubExpr, CallArgs, C.VoidTy, VK_RValue, SourceLocation());
275 }
276 
277 static CallExpr *create_call_once_lambda_call(ASTContext &C, ASTMaker M,
278                                               const ParmVarDecl *Callback,
279                                               CXXRecordDecl *CallbackDecl,
280                                               ArrayRef<Expr *> CallArgs) {
281   assert(CallbackDecl != nullptr);
282   assert(CallbackDecl->isLambda());
283   FunctionDecl *callOperatorDecl = CallbackDecl->getLambdaCallOperator();
284   assert(callOperatorDecl != nullptr);
285 
286   DeclRefExpr *callOperatorDeclRef =
287       DeclRefExpr::Create(/* Ctx =*/ C,
288                           /* QualifierLoc =*/ NestedNameSpecifierLoc(),
289                           /* TemplateKWLoc =*/ SourceLocation(),
290                           const_cast<FunctionDecl *>(callOperatorDecl),
291                           /* RefersToEnclosingVariableOrCapture=*/ false,
292                           /* NameLoc =*/ SourceLocation(),
293                           /* T =*/ callOperatorDecl->getType(),
294                           /* VK =*/ VK_LValue);
295 
296   return new (C)
297       CXXOperatorCallExpr(/*AstContext=*/C, OO_Call, callOperatorDeclRef,
298                           /*args=*/CallArgs,
299                           /*QualType=*/C.VoidTy,
300                           /*ExprValueType=*/VK_RValue,
301                           /*SourceLocation=*/SourceLocation(), FPOptions());
302 }
303 
304 /// Create a fake body for std::call_once.
305 /// Emulates the following function body:
306 ///
307 /// \code
308 /// typedef struct once_flag_s {
309 ///   unsigned long __state = 0;
310 /// } once_flag;
311 /// template<class Callable>
312 /// void call_once(once_flag& o, Callable func) {
313 ///   if (!o.__state) {
314 ///     func();
315 ///   }
316 ///   o.__state = 1;
317 /// }
318 /// \endcode
319 static Stmt *create_call_once(ASTContext &C, const FunctionDecl *D) {
320   LLVM_DEBUG(llvm::dbgs() << "Generating body for call_once\n");
321 
322   // We need at least two parameters.
323   if (D->param_size() < 2)
324     return nullptr;
325 
326   ASTMaker M(C);
327 
328   const ParmVarDecl *Flag = D->getParamDecl(0);
329   const ParmVarDecl *Callback = D->getParamDecl(1);
330 
331   if (!Callback->getType()->isReferenceType()) {
332     llvm::dbgs() << "libcxx03 std::call_once implementation, skipping.\n";
333     return nullptr;
334   }
335   if (!Flag->getType()->isReferenceType()) {
336     llvm::dbgs() << "unknown std::call_once implementation, skipping.\n";
337     return nullptr;
338   }
339 
340   QualType CallbackType = Callback->getType().getNonReferenceType();
341 
342   // Nullable pointer, non-null iff function is a CXXRecordDecl.
343   CXXRecordDecl *CallbackRecordDecl = CallbackType->getAsCXXRecordDecl();
344   QualType FlagType = Flag->getType().getNonReferenceType();
345   auto *FlagRecordDecl = FlagType->getAsRecordDecl();
346 
347   if (!FlagRecordDecl) {
348     LLVM_DEBUG(llvm::dbgs() << "Flag field is not a record: "
349                             << "unknown std::call_once implementation, "
350                             << "ignoring the call.\n");
351     return nullptr;
352   }
353 
354   // We initially assume libc++ implementation of call_once,
355   // where the once_flag struct has a field `__state_`.
356   ValueDecl *FlagFieldDecl = M.findMemberField(FlagRecordDecl, "__state_");
357 
358   // Otherwise, try libstdc++ implementation, with a field
359   // `_M_once`
360   if (!FlagFieldDecl) {
361     FlagFieldDecl = M.findMemberField(FlagRecordDecl, "_M_once");
362   }
363 
364   if (!FlagFieldDecl) {
365     LLVM_DEBUG(llvm::dbgs() << "No field _M_once or __state_ found on "
366                             << "std::once_flag struct: unknown std::call_once "
367                             << "implementation, ignoring the call.");
368     return nullptr;
369   }
370 
371   bool isLambdaCall = CallbackRecordDecl && CallbackRecordDecl->isLambda();
372   if (CallbackRecordDecl && !isLambdaCall) {
373     LLVM_DEBUG(llvm::dbgs()
374                << "Not supported: synthesizing body for functors when "
375                << "body farming std::call_once, ignoring the call.");
376     return nullptr;
377   }
378 
379   SmallVector<Expr *, 5> CallArgs;
380   const FunctionProtoType *CallbackFunctionType;
381   if (isLambdaCall) {
382 
383     // Lambda requires callback itself inserted as a first parameter.
384     CallArgs.push_back(
385         M.makeDeclRefExpr(Callback,
386                           /* RefersToEnclosingVariableOrCapture=*/ true));
387     CallbackFunctionType = CallbackRecordDecl->getLambdaCallOperator()
388                                ->getType()
389                                ->getAs<FunctionProtoType>();
390   } else if (!CallbackType->getPointeeType().isNull()) {
391     CallbackFunctionType =
392         CallbackType->getPointeeType()->getAs<FunctionProtoType>();
393   } else {
394     CallbackFunctionType = CallbackType->getAs<FunctionProtoType>();
395   }
396 
397   if (!CallbackFunctionType)
398     return nullptr;
399 
400   // First two arguments are used for the flag and for the callback.
401   if (D->getNumParams() != CallbackFunctionType->getNumParams() + 2) {
402     LLVM_DEBUG(llvm::dbgs() << "Types of params of the callback do not match "
403                             << "params passed to std::call_once, "
404                             << "ignoring the call\n");
405     return nullptr;
406   }
407 
408   // All arguments past first two ones are passed to the callback,
409   // and we turn lvalues into rvalues if the argument is not passed by
410   // reference.
411   for (unsigned int ParamIdx = 2; ParamIdx < D->getNumParams(); ParamIdx++) {
412     const ParmVarDecl *PDecl = D->getParamDecl(ParamIdx);
413     if (PDecl &&
414         CallbackFunctionType->getParamType(ParamIdx - 2)
415                 .getNonReferenceType()
416                 .getCanonicalType() !=
417             PDecl->getType().getNonReferenceType().getCanonicalType()) {
418       LLVM_DEBUG(llvm::dbgs() << "Types of params of the callback do not match "
419                               << "params passed to std::call_once, "
420                               << "ignoring the call\n");
421       return nullptr;
422     }
423     Expr *ParamExpr = M.makeDeclRefExpr(PDecl);
424     if (!CallbackFunctionType->getParamType(ParamIdx - 2)->isReferenceType()) {
425       QualType PTy = PDecl->getType().getNonReferenceType();
426       ParamExpr = M.makeLvalueToRvalue(ParamExpr, PTy);
427     }
428     CallArgs.push_back(ParamExpr);
429   }
430 
431   CallExpr *CallbackCall;
432   if (isLambdaCall) {
433 
434     CallbackCall = create_call_once_lambda_call(C, M, Callback,
435                                                 CallbackRecordDecl, CallArgs);
436   } else {
437 
438     // Function pointer case.
439     CallbackCall = create_call_once_funcptr_call(C, M, Callback, CallArgs);
440   }
441 
442   DeclRefExpr *FlagDecl =
443       M.makeDeclRefExpr(Flag,
444                         /* RefersToEnclosingVariableOrCapture=*/true);
445 
446 
447   MemberExpr *Deref = M.makeMemberExpression(FlagDecl, FlagFieldDecl);
448   assert(Deref->isLValue());
449   QualType DerefType = Deref->getType();
450 
451   // Negation predicate.
452   UnaryOperator *FlagCheck = new (C) UnaryOperator(
453       /* input=*/
454       M.makeImplicitCast(M.makeLvalueToRvalue(Deref, DerefType), DerefType,
455                          CK_IntegralToBoolean),
456       /* opc=*/ UO_LNot,
457       /* QualType=*/ C.IntTy,
458       /* ExprValueKind=*/ VK_RValue,
459       /* ExprObjectKind=*/ OK_Ordinary, SourceLocation(),
460       /* CanOverflow*/ false);
461 
462   // Create assignment.
463   BinaryOperator *FlagAssignment = M.makeAssignment(
464       Deref, M.makeIntegralCast(M.makeIntegerLiteral(1, C.IntTy), DerefType),
465       DerefType);
466 
467   auto *Out =
468       IfStmt::Create(C, SourceLocation(),
469                      /* IsConstexpr=*/false,
470                      /* init=*/nullptr,
471                      /* var=*/nullptr,
472                      /* cond=*/FlagCheck,
473                      /* then=*/M.makeCompound({CallbackCall, FlagAssignment}));
474 
475   return Out;
476 }
477 
478 /// Create a fake body for dispatch_once.
479 static Stmt *create_dispatch_once(ASTContext &C, const FunctionDecl *D) {
480   // Check if we have at least two parameters.
481   if (D->param_size() != 2)
482     return nullptr;
483 
484   // Check if the first parameter is a pointer to integer type.
485   const ParmVarDecl *Predicate = D->getParamDecl(0);
486   QualType PredicateQPtrTy = Predicate->getType();
487   const PointerType *PredicatePtrTy = PredicateQPtrTy->getAs<PointerType>();
488   if (!PredicatePtrTy)
489     return nullptr;
490   QualType PredicateTy = PredicatePtrTy->getPointeeType();
491   if (!PredicateTy->isIntegerType())
492     return nullptr;
493 
494   // Check if the second parameter is the proper block type.
495   const ParmVarDecl *Block = D->getParamDecl(1);
496   QualType Ty = Block->getType();
497   if (!isDispatchBlock(Ty))
498     return nullptr;
499 
500   // Everything checks out.  Create a fakse body that checks the predicate,
501   // sets it, and calls the block.  Basically, an AST dump of:
502   //
503   // void dispatch_once(dispatch_once_t *predicate, dispatch_block_t block) {
504   //  if (*predicate != ~0l) {
505   //    *predicate = ~0l;
506   //    block();
507   //  }
508   // }
509 
510   ASTMaker M(C);
511 
512   // (1) Create the call.
513   CallExpr *CE = new (C) CallExpr(
514       /*ASTContext=*/C,
515       /*StmtClass=*/M.makeLvalueToRvalue(/*Expr=*/Block),
516       /*args=*/None,
517       /*QualType=*/C.VoidTy,
518       /*ExprValueType=*/VK_RValue,
519       /*SourceLocation=*/SourceLocation());
520 
521   // (2) Create the assignment to the predicate.
522   Expr *DoneValue =
523       new (C) UnaryOperator(M.makeIntegerLiteral(0, C.LongTy), UO_Not, C.LongTy,
524                             VK_RValue, OK_Ordinary, SourceLocation(),
525                             /*CanOverflow*/false);
526 
527   BinaryOperator *B =
528     M.makeAssignment(
529        M.makeDereference(
530           M.makeLvalueToRvalue(
531             M.makeDeclRefExpr(Predicate), PredicateQPtrTy),
532             PredicateTy),
533        M.makeIntegralCast(DoneValue, PredicateTy),
534        PredicateTy);
535 
536   // (3) Create the compound statement.
537   Stmt *Stmts[] = { B, CE };
538   CompoundStmt *CS = M.makeCompound(Stmts);
539 
540   // (4) Create the 'if' condition.
541   ImplicitCastExpr *LValToRval =
542     M.makeLvalueToRvalue(
543       M.makeDereference(
544         M.makeLvalueToRvalue(
545           M.makeDeclRefExpr(Predicate),
546           PredicateQPtrTy),
547         PredicateTy),
548     PredicateTy);
549 
550   Expr *GuardCondition = M.makeComparison(LValToRval, DoneValue, BO_NE);
551   // (5) Create the 'if' statement.
552   auto *If = IfStmt::Create(C, SourceLocation(),
553                             /* IsConstexpr=*/false,
554                             /* init=*/nullptr,
555                             /* var=*/nullptr,
556                             /* cond=*/GuardCondition,
557                             /* then=*/CS);
558   return If;
559 }
560 
561 /// Create a fake body for dispatch_sync.
562 static Stmt *create_dispatch_sync(ASTContext &C, const FunctionDecl *D) {
563   // Check if we have at least two parameters.
564   if (D->param_size() != 2)
565     return nullptr;
566 
567   // Check if the second parameter is a block.
568   const ParmVarDecl *PV = D->getParamDecl(1);
569   QualType Ty = PV->getType();
570   if (!isDispatchBlock(Ty))
571     return nullptr;
572 
573   // Everything checks out.  Create a fake body that just calls the block.
574   // This is basically just an AST dump of:
575   //
576   // void dispatch_sync(dispatch_queue_t queue, void (^block)(void)) {
577   //   block();
578   // }
579   //
580   ASTMaker M(C);
581   DeclRefExpr *DR = M.makeDeclRefExpr(PV);
582   ImplicitCastExpr *ICE = M.makeLvalueToRvalue(DR, Ty);
583   CallExpr *CE = new (C) CallExpr(C, ICE, None, C.VoidTy, VK_RValue,
584                                   SourceLocation());
585   return CE;
586 }
587 
588 static Stmt *create_OSAtomicCompareAndSwap(ASTContext &C, const FunctionDecl *D)
589 {
590   // There are exactly 3 arguments.
591   if (D->param_size() != 3)
592     return nullptr;
593 
594   // Signature:
595   // _Bool OSAtomicCompareAndSwapPtr(void *__oldValue,
596   //                                 void *__newValue,
597   //                                 void * volatile *__theValue)
598   // Generate body:
599   //   if (oldValue == *theValue) {
600   //    *theValue = newValue;
601   //    return YES;
602   //   }
603   //   else return NO;
604 
605   QualType ResultTy = D->getReturnType();
606   bool isBoolean = ResultTy->isBooleanType();
607   if (!isBoolean && !ResultTy->isIntegralType(C))
608     return nullptr;
609 
610   const ParmVarDecl *OldValue = D->getParamDecl(0);
611   QualType OldValueTy = OldValue->getType();
612 
613   const ParmVarDecl *NewValue = D->getParamDecl(1);
614   QualType NewValueTy = NewValue->getType();
615 
616   assert(OldValueTy == NewValueTy);
617 
618   const ParmVarDecl *TheValue = D->getParamDecl(2);
619   QualType TheValueTy = TheValue->getType();
620   const PointerType *PT = TheValueTy->getAs<PointerType>();
621   if (!PT)
622     return nullptr;
623   QualType PointeeTy = PT->getPointeeType();
624 
625   ASTMaker M(C);
626   // Construct the comparison.
627   Expr *Comparison =
628     M.makeComparison(
629       M.makeLvalueToRvalue(M.makeDeclRefExpr(OldValue), OldValueTy),
630       M.makeLvalueToRvalue(
631         M.makeDereference(
632           M.makeLvalueToRvalue(M.makeDeclRefExpr(TheValue), TheValueTy),
633           PointeeTy),
634         PointeeTy),
635       BO_EQ);
636 
637   // Construct the body of the IfStmt.
638   Stmt *Stmts[2];
639   Stmts[0] =
640     M.makeAssignment(
641       M.makeDereference(
642         M.makeLvalueToRvalue(M.makeDeclRefExpr(TheValue), TheValueTy),
643         PointeeTy),
644       M.makeLvalueToRvalue(M.makeDeclRefExpr(NewValue), NewValueTy),
645       NewValueTy);
646 
647   Expr *BoolVal = M.makeObjCBool(true);
648   Expr *RetVal = isBoolean ? M.makeIntegralCastToBoolean(BoolVal)
649                            : M.makeIntegralCast(BoolVal, ResultTy);
650   Stmts[1] = M.makeReturn(RetVal);
651   CompoundStmt *Body = M.makeCompound(Stmts);
652 
653   // Construct the else clause.
654   BoolVal = M.makeObjCBool(false);
655   RetVal = isBoolean ? M.makeIntegralCastToBoolean(BoolVal)
656                      : M.makeIntegralCast(BoolVal, ResultTy);
657   Stmt *Else = M.makeReturn(RetVal);
658 
659   /// Construct the If.
660   auto *If = IfStmt::Create(C, SourceLocation(),
661                             /* IsConstexpr=*/false,
662                             /* init=*/nullptr,
663                             /* var=*/nullptr, Comparison, Body,
664                             SourceLocation(), Else);
665 
666   return If;
667 }
668 
669 Stmt *BodyFarm::getBody(const FunctionDecl *D) {
670   D = D->getCanonicalDecl();
671 
672   Optional<Stmt *> &Val = Bodies[D];
673   if (Val.hasValue())
674     return Val.getValue();
675 
676   Val = nullptr;
677 
678   if (D->getIdentifier() == nullptr)
679     return nullptr;
680 
681   StringRef Name = D->getName();
682   if (Name.empty())
683     return nullptr;
684 
685   FunctionFarmer FF;
686 
687   if (Name.startswith("OSAtomicCompareAndSwap") ||
688       Name.startswith("objc_atomicCompareAndSwap")) {
689     FF = create_OSAtomicCompareAndSwap;
690   } else if (Name == "call_once" && D->getDeclContext()->isStdNamespace()) {
691     FF = create_call_once;
692   } else {
693     FF = llvm::StringSwitch<FunctionFarmer>(Name)
694           .Case("dispatch_sync", create_dispatch_sync)
695           .Case("dispatch_once", create_dispatch_once)
696           .Default(nullptr);
697   }
698 
699   if (FF) { Val = FF(C, D); }
700   else if (Injector) { Val = Injector->getBody(D); }
701   return Val.getValue();
702 }
703 
704 static const ObjCIvarDecl *findBackingIvar(const ObjCPropertyDecl *Prop) {
705   const ObjCIvarDecl *IVar = Prop->getPropertyIvarDecl();
706 
707   if (IVar)
708     return IVar;
709 
710   // When a readonly property is shadowed in a class extensions with a
711   // a readwrite property, the instance variable belongs to the shadowing
712   // property rather than the shadowed property. If there is no instance
713   // variable on a readonly property, check to see whether the property is
714   // shadowed and if so try to get the instance variable from shadowing
715   // property.
716   if (!Prop->isReadOnly())
717     return nullptr;
718 
719   auto *Container = cast<ObjCContainerDecl>(Prop->getDeclContext());
720   const ObjCInterfaceDecl *PrimaryInterface = nullptr;
721   if (auto *InterfaceDecl = dyn_cast<ObjCInterfaceDecl>(Container)) {
722     PrimaryInterface = InterfaceDecl;
723   } else if (auto *CategoryDecl = dyn_cast<ObjCCategoryDecl>(Container)) {
724     PrimaryInterface = CategoryDecl->getClassInterface();
725   } else if (auto *ImplDecl = dyn_cast<ObjCImplDecl>(Container)) {
726     PrimaryInterface = ImplDecl->getClassInterface();
727   } else {
728     return nullptr;
729   }
730 
731   // FindPropertyVisibleInPrimaryClass() looks first in class extensions, so it
732   // is guaranteed to find the shadowing property, if it exists, rather than
733   // the shadowed property.
734   auto *ShadowingProp = PrimaryInterface->FindPropertyVisibleInPrimaryClass(
735       Prop->getIdentifier(), Prop->getQueryKind());
736   if (ShadowingProp && ShadowingProp != Prop) {
737     IVar = ShadowingProp->getPropertyIvarDecl();
738   }
739 
740   return IVar;
741 }
742 
743 static Stmt *createObjCPropertyGetter(ASTContext &Ctx,
744                                       const ObjCPropertyDecl *Prop) {
745   // First, find the backing ivar.
746   const ObjCIvarDecl *IVar = findBackingIvar(Prop);
747   if (!IVar)
748     return nullptr;
749 
750   // Ignore weak variables, which have special behavior.
751   if (Prop->getPropertyAttributes() & ObjCPropertyDecl::OBJC_PR_weak)
752     return nullptr;
753 
754   // Look to see if Sema has synthesized a body for us. This happens in
755   // Objective-C++ because the return value may be a C++ class type with a
756   // non-trivial copy constructor. We can only do this if we can find the
757   // @synthesize for this property, though (or if we know it's been auto-
758   // synthesized).
759   const ObjCImplementationDecl *ImplDecl =
760     IVar->getContainingInterface()->getImplementation();
761   if (ImplDecl) {
762     for (const auto *I : ImplDecl->property_impls()) {
763       if (I->getPropertyDecl() != Prop)
764         continue;
765 
766       if (I->getGetterCXXConstructor()) {
767         ASTMaker M(Ctx);
768         return M.makeReturn(I->getGetterCXXConstructor());
769       }
770     }
771   }
772 
773   // Sanity check that the property is the same type as the ivar, or a
774   // reference to it, and that it is either an object pointer or trivially
775   // copyable.
776   if (!Ctx.hasSameUnqualifiedType(IVar->getType(),
777                                   Prop->getType().getNonReferenceType()))
778     return nullptr;
779   if (!IVar->getType()->isObjCLifetimeType() &&
780       !IVar->getType().isTriviallyCopyableType(Ctx))
781     return nullptr;
782 
783   // Generate our body:
784   //   return self->_ivar;
785   ASTMaker M(Ctx);
786 
787   const VarDecl *selfVar = Prop->getGetterMethodDecl()->getSelfDecl();
788   if (!selfVar)
789     return nullptr;
790 
791   Expr *loadedIVar =
792     M.makeObjCIvarRef(
793       M.makeLvalueToRvalue(
794         M.makeDeclRefExpr(selfVar),
795         selfVar->getType()),
796       IVar);
797 
798   if (!Prop->getType()->isReferenceType())
799     loadedIVar = M.makeLvalueToRvalue(loadedIVar, IVar->getType());
800 
801   return M.makeReturn(loadedIVar);
802 }
803 
804 Stmt *BodyFarm::getBody(const ObjCMethodDecl *D) {
805   // We currently only know how to synthesize property accessors.
806   if (!D->isPropertyAccessor())
807     return nullptr;
808 
809   D = D->getCanonicalDecl();
810 
811   Optional<Stmt *> &Val = Bodies[D];
812   if (Val.hasValue())
813     return Val.getValue();
814   Val = nullptr;
815 
816   const ObjCPropertyDecl *Prop = D->findPropertyDecl();
817   if (!Prop)
818     return nullptr;
819 
820   // For now, we only synthesize getters.
821   // Synthesizing setters would cause false negatives in the
822   // RetainCountChecker because the method body would bind the parameter
823   // to an instance variable, causing it to escape. This would prevent
824   // warning in the following common scenario:
825   //
826   //  id foo = [[NSObject alloc] init];
827   //  self.foo = foo; // We should warn that foo leaks here.
828   //
829   if (D->param_size() != 0)
830     return nullptr;
831 
832   Val = createObjCPropertyGetter(C, Prop);
833 
834   return Val.getValue();
835 }
836