Home | History | Annotate | Download | only in Analysis 
      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 
    377