contrib/llvm/tools/clang/lib/Analysis/BodyFarm.cpp

   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
  22 using namespace clang;
  23
  24 //===----------------------------------------------------------------------===//
  25 // Helper creation functions for constructing faux ASTs.
  26 //===----------------------------------------------------------------------===//
  27
  28 static 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
  45 namespace {
  46 class ASTMaker {
  47 public:
  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
  81 private:
  82   ASTContext &C;
  83 };
  84 }
  85
  86 BinaryOperator *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
  93 BinaryOperator *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
 105 CompoundStmt *ASTMaker::makeCompound(ArrayRef<Stmt *> Stmts) {
 106   return new (C) CompoundStmt(C, Stmts, SourceLocation(), SourceLocation());
 107 }
 108
 109 DeclRefExpr *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
 122 UnaryOperator *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
 127 ImplicitCastExpr *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
 132 Expr *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
 140 ImplicitCastExpr *ASTMaker::makeIntegralCastToBoolean(const Expr *Arg) {
 141   return ImplicitCastExpr::Create(C, C.BoolTy, CK_IntegralToBoolean,
 142                                   const_cast<Expr*>(Arg), 0, VK_RValue);
 143 }
 144
 145 ObjCBoolLiteralExpr *ASTMaker::makeObjCBool(bool Val) {
 146   QualType Ty = C.getBOOLDecl() ? C.getBOOLType() : C.ObjCBuiltinBoolTy;
 147   return new (C) ObjCBoolLiteralExpr(Val, Ty, SourceLocation());
 148 }
 149
 150 ReturnStmt *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
 158 typedef Stmt *(*FunctionFarmer)(ASTContext &C, const FunctionDecl *D);
 159
 160 /// Create a fake body for dispatch_once.
 161 static 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, None, C.VoidTy, VK_RValue,
 198                                   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.
 239 static 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, None, C.VoidTy, VK_RValue,
 261                                   SourceLocation());
 262   return CE;
 263 }
 264
 265 static 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
 344 Stmt *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