BodyFarm.cpp revision dc84cd5efdd3430efb22546b4ac656aa0540b210 
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 "BodyFarm.h"
16#include "clang/AST/ASTContext.h"
17#include "clang/AST/Decl.h"
18#include "clang/AST/Expr.h"
19#include "clang/AST/ExprObjC.h"
20#include "llvm/ADT/StringSwitch.h"
21
22using namespace clang;
23
24//===----------------------------------------------------------------------===//
25// Helper creation functions for constructing faux ASTs.
26//===----------------------------------------------------------------------===//
27
28static bool isDispatchBlock(QualType Ty) {
29  // Is it a block pointer?
30  const BlockPointerType *BPT = Ty->getAs<BlockPointerType>();
31  if (!BPT)
32    return false;
33
34  // Check if the block pointer type takes no arguments and
35  // returns void.
36  const FunctionProtoType *FT =
37  BPT->getPointeeType()->getAs<FunctionProtoType>();
38  if (!FT || !FT->getResultType()->isVoidType()  ||
39      FT->getNumArgs() != 0)
40    return false;
41
42  return true;
43}
44
45namespace {
46class ASTMaker {
47public:
48  ASTMaker(ASTContext &C) : C(C) {}
49
50  /// Create a new BinaryOperator representing a simple assignment.
51  BinaryOperator *makeAssignment(const Expr *LHS, const Expr *RHS, QualType Ty);
52
53  /// Create a new BinaryOperator representing a comparison.
54  BinaryOperator *makeComparison(const Expr *LHS, const Expr *RHS,
55                                 BinaryOperator::Opcode Op);
56
57  /// Create a new compound stmt using the provided statements.
58  CompoundStmt *makeCompound(ArrayRef<Stmt*>);
59
60  /// Create a new DeclRefExpr for the referenced variable.
61  DeclRefExpr *makeDeclRefExpr(const VarDecl *D);
62
63  /// Create a new UnaryOperator representing a dereference.
64  UnaryOperator *makeDereference(const Expr *Arg, QualType Ty);
65
66  /// Create an implicit cast for an integer conversion.
67  Expr *makeIntegralCast(const Expr *Arg, QualType Ty);
68
69  /// Create an implicit cast to a builtin boolean type.
70  ImplicitCastExpr *makeIntegralCastToBoolean(const Expr *Arg);
71
72  // Create an implicit cast for lvalue-to-rvaluate conversions.
73  ImplicitCastExpr *makeLvalueToRvalue(const Expr *Arg, QualType Ty);
74
75  /// Create an Objective-C bool literal.
76  ObjCBoolLiteralExpr *makeObjCBool(bool Val);
77
78  /// Create a Return statement.
79  ReturnStmt *makeReturn(const Expr *RetVal);
80
81private:
82  ASTContext &C;
83};
84}
85
86BinaryOperator *ASTMaker::makeAssignment(const Expr *LHS, const Expr *RHS,
87                                         QualType Ty) {
88 return new (C) BinaryOperator(const_cast<Expr*>(LHS), const_cast<Expr*>(RHS),
89                               BO_Assign, Ty, VK_RValue,
90                               OK_Ordinary, SourceLocation(), false);
91}
92
93BinaryOperator *ASTMaker::makeComparison(const Expr *LHS, const Expr *RHS,
94                                         BinaryOperator::Opcode Op) {
95  assert(BinaryOperator::isLogicalOp(Op) ||
96         BinaryOperator::isComparisonOp(Op));
97  return new (C) BinaryOperator(const_cast<Expr*>(LHS),
98                                const_cast<Expr*>(RHS),
99                                Op,
100                                C.getLogicalOperationType(),
101                                VK_RValue,
102                                OK_Ordinary, SourceLocation(), false);
103}
104
105CompoundStmt *ASTMaker::makeCompound(ArrayRef<Stmt *> Stmts) {
106  return new (C) CompoundStmt(C, Stmts, SourceLocation(), SourceLocation());
107}
108
109DeclRefExpr *ASTMaker::makeDeclRefExpr(const VarDecl *D) {
110  DeclRefExpr *DR =
111    DeclRefExpr::Create(/* Ctx = */ C,
112                        /* QualifierLoc = */ NestedNameSpecifierLoc(),
113                        /* TemplateKWLoc = */ SourceLocation(),
114                        /* D = */ const_cast<VarDecl*>(D),
115                        /* isEnclosingLocal = */ false,
116                        /* NameLoc = */ SourceLocation(),
117                        /* T = */ D->getType(),
118                        /* VK = */ VK_LValue);
119  return DR;
120}
121
122UnaryOperator *ASTMaker::makeDereference(const Expr *Arg, QualType Ty) {
123  return new (C) UnaryOperator(const_cast<Expr*>(Arg), UO_Deref, Ty,
124                               VK_LValue, OK_Ordinary, SourceLocation());
125}
126
127ImplicitCastExpr *ASTMaker::makeLvalueToRvalue(const Expr *Arg, QualType Ty) {
128  return ImplicitCastExpr::Create(C, Ty, CK_LValueToRValue,
129                                  const_cast<Expr*>(Arg), 0, VK_RValue);
130}
131
132Expr *ASTMaker::makeIntegralCast(const Expr *Arg, QualType Ty) {
133  if (Arg->getType() == Ty)
134    return const_cast<Expr*>(Arg);
135
136  return ImplicitCastExpr::Create(C, Ty, CK_IntegralCast,
137                                  const_cast<Expr*>(Arg), 0, VK_RValue);
138}
139
140ImplicitCastExpr *ASTMaker::makeIntegralCastToBoolean(const Expr *Arg) {
141  return ImplicitCastExpr::Create(C, C.BoolTy, CK_IntegralToBoolean,
142                                  const_cast<Expr*>(Arg), 0, VK_RValue);
143}
144
145ObjCBoolLiteralExpr *ASTMaker::makeObjCBool(bool Val) {
146  QualType Ty = C.getBOOLDecl() ? C.getBOOLType() : C.ObjCBuiltinBoolTy;
147  return new (C) ObjCBoolLiteralExpr(Val, Ty, SourceLocation());
148}
149
150ReturnStmt *ASTMaker::makeReturn(const Expr *RetVal) {
151  return new (C) ReturnStmt(SourceLocation(), const_cast<Expr*>(RetVal), 0);
152}
153
154//===----------------------------------------------------------------------===//
155// Creation functions for faux ASTs.
156//===----------------------------------------------------------------------===//
157
158typedef Stmt *(*FunctionFarmer)(ASTContext &C, const FunctionDecl *D);
159
160/// Create a fake body for dispatch_once.
161static Stmt *create_dispatch_once(ASTContext &C, const FunctionDecl *D) {
162  // Check if we have at least two parameters.
163  if (D->param_size() != 2)
164    return 0;
165
166  // Check if the first parameter is a pointer to integer type.
167  const ParmVarDecl *Predicate = D->getParamDecl(0);
168  QualType PredicateQPtrTy = Predicate->getType();
169  const PointerType *PredicatePtrTy = PredicateQPtrTy->getAs<PointerType>();
170  if (!PredicatePtrTy)
171    return 0;
172  QualType PredicateTy = PredicatePtrTy->getPointeeType();
173  if (!PredicateTy->isIntegerType())
174    return 0;
175
176  // Check if the second parameter is the proper block type.
177  const ParmVarDecl *Block = D->getParamDecl(1);
178  QualType Ty = Block->getType();
179  if (!isDispatchBlock(Ty))
180    return 0;
181
182  // Everything checks out.  Create a fakse body that checks the predicate,
183  // sets it, and calls the block.  Basically, an AST dump of:
184  //
185  // void dispatch_once(dispatch_once_t *predicate, dispatch_block_t block) {
186  //  if (!*predicate) {
187  //    *predicate = 1;
188  //    block();
189  //  }
190  // }
191
192  ASTMaker M(C);
193
194  // (1) Create the call.
195  DeclRefExpr *DR = M.makeDeclRefExpr(Block);
196  ImplicitCastExpr *ICE = M.makeLvalueToRvalue(DR, Ty);
197  CallExpr *CE = new (C) CallExpr(C, ICE, ArrayRef<Expr*>(), C.VoidTy,
198                                  VK_RValue, SourceLocation());
199
200  // (2) Create the assignment to the predicate.
201  IntegerLiteral *IL =
202    IntegerLiteral::Create(C, llvm::APInt(C.getTypeSize(C.IntTy), (uint64_t) 1),
203                           C.IntTy, SourceLocation());
204  BinaryOperator *B =
205    M.makeAssignment(
206       M.makeDereference(
207          M.makeLvalueToRvalue(
208            M.makeDeclRefExpr(Predicate), PredicateQPtrTy),
209            PredicateTy),
210       M.makeIntegralCast(IL, PredicateTy),
211       PredicateTy);
212
213  // (3) Create the compound statement.
214  Stmt *Stmts[2];
215  Stmts[0] = B;
216  Stmts[1] = CE;
217  CompoundStmt *CS = M.makeCompound(ArrayRef<Stmt*>(Stmts, 2));
218
219  // (4) Create the 'if' condition.
220  ImplicitCastExpr *LValToRval =
221    M.makeLvalueToRvalue(
222      M.makeDereference(
223        M.makeLvalueToRvalue(
224          M.makeDeclRefExpr(Predicate),
225          PredicateQPtrTy),
226        PredicateTy),
227    PredicateTy);
228
229  UnaryOperator *UO = new (C) UnaryOperator(LValToRval, UO_LNot, C.IntTy,
230                                           VK_RValue, OK_Ordinary,
231                                           SourceLocation());
232
233  // (5) Create the 'if' statement.
234  IfStmt *If = new (C) IfStmt(C, SourceLocation(), 0, UO, CS);
235  return If;
236}
237
238/// Create a fake body for dispatch_sync.
239static Stmt *create_dispatch_sync(ASTContext &C, const FunctionDecl *D) {
240  // Check if we have at least two parameters.
241  if (D->param_size() != 2)
242    return 0;
243
244  // Check if the second parameter is a block.
245  const ParmVarDecl *PV = D->getParamDecl(1);
246  QualType Ty = PV->getType();
247  if (!isDispatchBlock(Ty))
248    return 0;
249
250  // Everything checks out.  Create a fake body that just calls the block.
251  // This is basically just an AST dump of:
252  //
253  // void dispatch_sync(dispatch_queue_t queue, void (^block)(void)) {
254  //   block();
255  // }
256  //
257  ASTMaker M(C);
258  DeclRefExpr *DR = M.makeDeclRefExpr(PV);
259  ImplicitCastExpr *ICE = M.makeLvalueToRvalue(DR, Ty);
260  CallExpr *CE = new (C) CallExpr(C, ICE, ArrayRef<Expr*>(), C.VoidTy,
261                                  VK_RValue, SourceLocation());
262  return CE;
263}
264
265static Stmt *create_OSAtomicCompareAndSwap(ASTContext &C, const FunctionDecl *D)
266{
267  // There are exactly 3 arguments.
268  if (D->param_size() != 3)
269    return 0;
270
271  // Signature:
272  // _Bool OSAtomicCompareAndSwapPtr(void *__oldValue,
273  //                                 void *__newValue,
274  //                                 void * volatile *__theValue)
275  // Generate body:
276  //   if (oldValue == *theValue) {
277  //    *theValue = newValue;
278  //    return YES;
279  //   }
280  //   else return NO;
281
282  QualType ResultTy = D->getResultType();
283  bool isBoolean = ResultTy->isBooleanType();
284  if (!isBoolean && !ResultTy->isIntegralType(C))
285    return 0;
286
287  const ParmVarDecl *OldValue = D->getParamDecl(0);
288  QualType OldValueTy = OldValue->getType();
289
290  const ParmVarDecl *NewValue = D->getParamDecl(1);
291  QualType NewValueTy = NewValue->getType();
292
293  assert(OldValueTy == NewValueTy);
294
295  const ParmVarDecl *TheValue = D->getParamDecl(2);
296  QualType TheValueTy = TheValue->getType();
297  const PointerType *PT = TheValueTy->getAs<PointerType>();
298  if (!PT)
299    return 0;
300  QualType PointeeTy = PT->getPointeeType();
301
302  ASTMaker M(C);
303  // Construct the comparison.
304  Expr *Comparison =
305    M.makeComparison(
306      M.makeLvalueToRvalue(M.makeDeclRefExpr(OldValue), OldValueTy),
307      M.makeLvalueToRvalue(
308        M.makeDereference(
309          M.makeLvalueToRvalue(M.makeDeclRefExpr(TheValue), TheValueTy),
310          PointeeTy),
311        PointeeTy),
312      BO_EQ);
313
314  // Construct the body of the IfStmt.
315  Stmt *Stmts[2];
316  Stmts[0] =
317    M.makeAssignment(
318      M.makeDereference(
319        M.makeLvalueToRvalue(M.makeDeclRefExpr(TheValue), TheValueTy),
320        PointeeTy),
321      M.makeLvalueToRvalue(M.makeDeclRefExpr(NewValue), NewValueTy),
322      NewValueTy);
323
324  Expr *BoolVal = M.makeObjCBool(true);
325  Expr *RetVal = isBoolean ? M.makeIntegralCastToBoolean(BoolVal)
326                           : M.makeIntegralCast(BoolVal, ResultTy);
327  Stmts[1] = M.makeReturn(RetVal);
328  CompoundStmt *Body = M.makeCompound(ArrayRef<Stmt*>(Stmts, 2));
329
330  // Construct the else clause.
331  BoolVal = M.makeObjCBool(false);
332  RetVal = isBoolean ? M.makeIntegralCastToBoolean(BoolVal)
333                     : M.makeIntegralCast(BoolVal, ResultTy);
334  Stmt *Else = M.makeReturn(RetVal);
335
336  /// Construct the If.
337  Stmt *If =
338    new (C) IfStmt(C, SourceLocation(), 0, Comparison, Body,
339                   SourceLocation(), Else);
340
341  return If;
342}
343
344Stmt *BodyFarm::getBody(const FunctionDecl *D) {
345  D = D->getCanonicalDecl();
346
347  Optional<Stmt *> &Val = Bodies[D];
348  if (Val.hasValue())
349    return Val.getValue();
350
351  Val = 0;
352
353  if (D->getIdentifier() == 0)
354    return 0;
355
356  StringRef Name = D->getName();
357  if (Name.empty())
358    return 0;
359
360  FunctionFarmer FF;
361
362  if (Name.startswith("OSAtomicCompareAndSwap") ||
363      Name.startswith("objc_atomicCompareAndSwap")) {
364    FF = create_OSAtomicCompareAndSwap;
365  }
366  else {
367    FF = llvm::StringSwitch<FunctionFarmer>(Name)
368          .Case("dispatch_sync", create_dispatch_sync)
369          .Case("dispatch_once", create_dispatch_once)
370        .Default(NULL);
371  }
372
373  if (FF) { Val = FF(C, D); }
374  return Val.getValue();
375}
376
377