lib/Sema/SemaChecking.cpp

   1 //===--- SemaChecking.cpp - Extra Semantic Checking -----------------------===//
   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 //  This file implements extra semantic analysis beyond what is enforced
  11 //  by the C type system.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "Sema.h"
  16 #include "clang/Analysis/CFG.h"
  17 #include "clang/Analysis/PathSensitive/AnalysisContext.h"
  18 #include "clang/AST/ASTContext.h"
  19 #include "clang/AST/CharUnits.h"
  20 #include "clang/AST/DeclObjC.h"
  21 #include "clang/AST/ExprCXX.h"
  22 #include "clang/AST/ExprObjC.h"
  23 #include "clang/AST/DeclObjC.h"
  24 #include "clang/AST/StmtCXX.h"
  25 #include "clang/AST/StmtObjC.h"
  26 #include "clang/Lex/LiteralSupport.h"
  27 #include "clang/Lex/Preprocessor.h"
  28 #include "llvm/ADT/BitVector.h"
  29 #include "llvm/ADT/STLExtras.h"
  30 #include <limits>
  31 #include <queue>
  32 using namespace clang;
  33
  34 /// getLocationOfStringLiteralByte - Return a source location that points to the
  35 /// specified byte of the specified string literal.
  36 ///
  37 /// Strings are amazingly complex.  They can be formed from multiple tokens and
  38 /// can have escape sequences in them in addition to the usual trigraph and
  39 /// escaped newline business.  This routine handles this complexity.
  40 ///
  41 SourceLocation Sema::getLocationOfStringLiteralByte(const StringLiteral *SL,
  42                                                     unsigned ByteNo) const {
  43   assert(!SL->isWide() && "This doesn't work for wide strings yet");
  44
  45   // Loop over all of the tokens in this string until we find the one that
  46   // contains the byte we're looking for.
  47   unsigned TokNo = 0;
  48   while (1) {
  49     assert(TokNo < SL->getNumConcatenated() && "Invalid byte number!");
  50     SourceLocation StrTokLoc = SL->getStrTokenLoc(TokNo);
  51
  52     // Get the spelling of the string so that we can get the data that makes up
  53     // the string literal, not the identifier for the macro it is potentially
  54     // expanded through.
  55     SourceLocation StrTokSpellingLoc = SourceMgr.getSpellingLoc(StrTokLoc);
  56
  57     // Re-lex the token to get its length and original spelling.
  58     std::pair<FileID, unsigned> LocInfo =
  59       SourceMgr.getDecomposedLoc(StrTokSpellingLoc);
  60     std::pair<const char *,const char *> Buffer =
  61       SourceMgr.getBufferData(LocInfo.first);
  62     const char *StrData = Buffer.first+LocInfo.second;
  63
  64     // Create a langops struct and enable trigraphs.  This is sufficient for
  65     // relexing tokens.
  66     LangOptions LangOpts;
  67     LangOpts.Trigraphs = true;
  68
  69     // Create a lexer starting at the beginning of this token.
  70     Lexer TheLexer(StrTokSpellingLoc, LangOpts, Buffer.first, StrData,
  71                    Buffer.second);
  72     Token TheTok;
  73     TheLexer.LexFromRawLexer(TheTok);
  74
  75     // Use the StringLiteralParser to compute the length of the string in bytes.
  76     StringLiteralParser SLP(&TheTok, 1, PP);
  77     unsigned TokNumBytes = SLP.GetStringLength();
  78
  79     // If the byte is in this token, return the location of the byte.
  80     if (ByteNo < TokNumBytes ||
  81         (ByteNo == TokNumBytes && TokNo == SL->getNumConcatenated())) {
  82       unsigned Offset =
  83         StringLiteralParser::getOffsetOfStringByte(TheTok, ByteNo, PP);
  84
  85       // Now that we know the offset of the token in the spelling, use the
  86       // preprocessor to get the offset in the original source.
  87       return PP.AdvanceToTokenCharacter(StrTokLoc, Offset);
  88     }
  89
  90     // Move to the next string token.
  91     ++TokNo;
  92     ByteNo -= TokNumBytes;
  93   }
  94 }
  95
  96 /// CheckablePrintfAttr - does a function call have a "printf" attribute
  97 /// and arguments that merit checking?
  98 bool Sema::CheckablePrintfAttr(const FormatAttr *Format, CallExpr *TheCall) {
  99   if (Format->getType() == "printf") return true;
 100   if (Format->getType() == "printf0") {
 101     // printf0 allows null "format" string; if so don't check format/args
 102     unsigned format_idx = Format->getFormatIdx() - 1;
 103     // Does the index refer to the implicit object argument?
 104     if (isa<CXXMemberCallExpr>(TheCall)) {
 105       if (format_idx == 0)
 106         return false;
 107       --format_idx;
 108     }
 109     if (format_idx < TheCall->getNumArgs()) {
 110       Expr *Format = TheCall->getArg(format_idx)->IgnoreParenCasts();
 111       if (!Format->isNullPointerConstant(Context, Expr::NPC_ValueDependentIsNull))
 112         return true;
 113     }
 114   }
 115   return false;
 116 }
 117
 118 Action::OwningExprResult
 119 Sema::CheckBuiltinFunctionCall(unsigned BuiltinID, CallExpr *TheCall) {
 120   OwningExprResult TheCallResult(Owned(TheCall));
 121
 122   switch (BuiltinID) {
 123   case Builtin::BI__builtin___CFStringMakeConstantString:
 124     assert(TheCall->getNumArgs() == 1 &&
 125            "Wrong # arguments to builtin CFStringMakeConstantString");
 126     if (CheckObjCString(TheCall->getArg(0)))
 127       return ExprError();
 128     break;
 129   case Builtin::BI__builtin_stdarg_start:
 130   case Builtin::BI__builtin_va_start:
 131     if (SemaBuiltinVAStart(TheCall))
 132       return ExprError();
 133     break;
 134   case Builtin::BI__builtin_isgreater:
 135   case Builtin::BI__builtin_isgreaterequal:
 136   case Builtin::BI__builtin_isless:
 137   case Builtin::BI__builtin_islessequal:
 138   case Builtin::BI__builtin_islessgreater:
 139   case Builtin::BI__builtin_isunordered:
 140     if (SemaBuiltinUnorderedCompare(TheCall))
 141       return ExprError();
 142     break;
 143   case Builtin::BI__builtin_isfinite:
 144   case Builtin::BI__builtin_isinf:
 145   case Builtin::BI__builtin_isinf_sign:
 146   case Builtin::BI__builtin_isnan:
 147   case Builtin::BI__builtin_isnormal:
 148     if (SemaBuiltinUnaryFP(TheCall))
 149       return ExprError();
 150     break;
 151   case Builtin::BI__builtin_return_address:
 152   case Builtin::BI__builtin_frame_address:
 153     if (SemaBuiltinStackAddress(TheCall))
 154       return ExprError();
 155     break;
 156   case Builtin::BI__builtin_eh_return_data_regno:
 157     if (SemaBuiltinEHReturnDataRegNo(TheCall))
 158       return ExprError();
 159     break;
 160   case Builtin::BI__builtin_shufflevector:
 161     return SemaBuiltinShuffleVector(TheCall);
 162     // TheCall will be freed by the smart pointer here, but that's fine, since
 163     // SemaBuiltinShuffleVector guts it, but then doesn't release it.
 164   case Builtin::BI__builtin_prefetch:
 165     if (SemaBuiltinPrefetch(TheCall))
 166       return ExprError();
 167     break;
 168   case Builtin::BI__builtin_object_size:
 169     if (SemaBuiltinObjectSize(TheCall))
 170       return ExprError();
 171     break;
 172   case Builtin::BI__builtin_longjmp:
 173     if (SemaBuiltinLongjmp(TheCall))
 174       return ExprError();
 175     break;
 176   case Builtin::BI__sync_fetch_and_add:
 177   case Builtin::BI__sync_fetch_and_sub:
 178   case Builtin::BI__sync_fetch_and_or:
 179   case Builtin::BI__sync_fetch_and_and:
 180   case Builtin::BI__sync_fetch_and_xor:
 181   case Builtin::BI__sync_fetch_and_nand:
 182   case Builtin::BI__sync_add_and_fetch:
 183   case Builtin::BI__sync_sub_and_fetch:
 184   case Builtin::BI__sync_and_and_fetch:
 185   case Builtin::BI__sync_or_and_fetch:
 186   case Builtin::BI__sync_xor_and_fetch:
 187   case Builtin::BI__sync_nand_and_fetch:
 188   case Builtin::BI__sync_val_compare_and_swap:
 189   case Builtin::BI__sync_bool_compare_and_swap:
 190   case Builtin::BI__sync_lock_test_and_set:
 191   case Builtin::BI__sync_lock_release:
 192     if (SemaBuiltinAtomicOverloaded(TheCall))
 193       return ExprError();
 194     break;
 195   }
 196
 197   return move(TheCallResult);
 198 }
 199
 200 /// CheckFunctionCall - Check a direct function call for various correctness
 201 /// and safety properties not strictly enforced by the C type system.
 202 bool Sema::CheckFunctionCall(FunctionDecl *FDecl, CallExpr *TheCall) {
 203   // Get the IdentifierInfo* for the called function.
 204   IdentifierInfo *FnInfo = FDecl->getIdentifier();
 205
 206   // None of the checks below are needed for functions that don't have
 207   // simple names (e.g., C++ conversion functions).
 208   if (!FnInfo)
 209     return false;
 210
 211   // FIXME: This mechanism should be abstracted to be less fragile and
 212   // more efficient. For example, just map function ids to custom
 213   // handlers.
 214
 215   // Printf checking.
 216   if (const FormatAttr *Format = FDecl->getAttr<FormatAttr>()) {
 217     if (CheckablePrintfAttr(Format, TheCall)) {
 218       bool HasVAListArg = Format->getFirstArg() == 0;
 219       if (!HasVAListArg) {
 220         if (const FunctionProtoType *Proto
 221             = FDecl->getType()->getAs<FunctionProtoType>())
 222           HasVAListArg = !Proto->isVariadic();
 223       }
 224       CheckPrintfArguments(TheCall, HasVAListArg, Format->getFormatIdx() - 1,
 225                            HasVAListArg ? 0 : Format->getFirstArg() - 1);
 226     }
 227   }
 228
 229   for (const NonNullAttr *NonNull = FDecl->getAttr<NonNullAttr>(); NonNull;
 230        NonNull = NonNull->getNext<NonNullAttr>())
 231     CheckNonNullArguments(NonNull, TheCall);
 232
 233   return false;
 234 }
 235
 236 bool Sema::CheckBlockCall(NamedDecl *NDecl, CallExpr *TheCall) {
 237   // Printf checking.
 238   const FormatAttr *Format = NDecl->getAttr<FormatAttr>();
 239   if (!Format)
 240     return false;
 241
 242   const VarDecl *V = dyn_cast<VarDecl>(NDecl);
 243   if (!V)
 244     return false;
 245
 246   QualType Ty = V->getType();
 247   if (!Ty->isBlockPointerType())
 248     return false;
 249
 250   if (!CheckablePrintfAttr(Format, TheCall))
 251     return false;
 252
 253   bool HasVAListArg = Format->getFirstArg() == 0;
 254   if (!HasVAListArg) {
 255     const FunctionType *FT =
 256       Ty->getAs<BlockPointerType>()->getPointeeType()->getAs<FunctionType>();
 257     if (const FunctionProtoType *Proto = dyn_cast<FunctionProtoType>(FT))
 258       HasVAListArg = !Proto->isVariadic();
 259   }
 260   CheckPrintfArguments(TheCall, HasVAListArg, Format->getFormatIdx() - 1,
 261                        HasVAListArg ? 0 : Format->getFirstArg() - 1);
 262
 263   return false;
 264 }
 265
 266 /// SemaBuiltinAtomicOverloaded - We have a call to a function like
 267 /// __sync_fetch_and_add, which is an overloaded function based on the pointer
 268 /// type of its first argument.  The main ActOnCallExpr routines have already
 269 /// promoted the types of arguments because all of these calls are prototyped as
 270 /// void(...).
 271 ///
 272 /// This function goes through and does final semantic checking for these
 273 /// builtins,
 274 bool Sema::SemaBuiltinAtomicOverloaded(CallExpr *TheCall) {
 275   DeclRefExpr *DRE =cast<DeclRefExpr>(TheCall->getCallee()->IgnoreParenCasts());
 276   FunctionDecl *FDecl = cast<FunctionDecl>(DRE->getDecl());
 277
 278   // Ensure that we have at least one argument to do type inference from.
 279   if (TheCall->getNumArgs() < 1)
 280     return Diag(TheCall->getLocEnd(), diag::err_typecheck_call_too_few_args)
 281               << 0 << TheCall->getCallee()->getSourceRange();
 282
 283   // Inspect the first argument of the atomic builtin.  This should always be
 284   // a pointer type, whose element is an integral scalar or pointer type.
 285   // Because it is a pointer type, we don't have to worry about any implicit
 286   // casts here.
 287   Expr *FirstArg = TheCall->getArg(0);
 288   if (!FirstArg->getType()->isPointerType())
 289     return Diag(DRE->getLocStart(), diag::err_atomic_builtin_must_be_pointer)
 290              << FirstArg->getType() << FirstArg->getSourceRange();
 291
 292   QualType ValType = FirstArg->getType()->getAs<PointerType>()->getPointeeType();
 293   if (!ValType->isIntegerType() && !ValType->isPointerType() &&
 294       !ValType->isBlockPointerType())
 295     return Diag(DRE->getLocStart(),
 296                 diag::err_atomic_builtin_must_be_pointer_intptr)
 297              << FirstArg->getType() << FirstArg->getSourceRange();
 298
 299   // We need to figure out which concrete builtin this maps onto.  For example,
 300   // __sync_fetch_and_add with a 2 byte object turns into
 301   // __sync_fetch_and_add_2.
 302 #define BUILTIN_ROW(x) \
 303   { Builtin::BI##x##_1, Builtin::BI##x##_2, Builtin::BI##x##_4, \
 304     Builtin::BI##x##_8, Builtin::BI##x##_16 }
 305
 306   static const unsigned BuiltinIndices[][5] = {
 307     BUILTIN_ROW(__sync_fetch_and_add),
 308     BUILTIN_ROW(__sync_fetch_and_sub),
 309     BUILTIN_ROW(__sync_fetch_and_or),
 310     BUILTIN_ROW(__sync_fetch_and_and),
 311     BUILTIN_ROW(__sync_fetch_and_xor),
 312     BUILTIN_ROW(__sync_fetch_and_nand),
 313
 314     BUILTIN_ROW(__sync_add_and_fetch),
 315     BUILTIN_ROW(__sync_sub_and_fetch),
 316     BUILTIN_ROW(__sync_and_and_fetch),
 317     BUILTIN_ROW(__sync_or_and_fetch),
 318     BUILTIN_ROW(__sync_xor_and_fetch),
 319     BUILTIN_ROW(__sync_nand_and_fetch),
 320
 321     BUILTIN_ROW(__sync_val_compare_and_swap),
 322     BUILTIN_ROW(__sync_bool_compare_and_swap),
 323     BUILTIN_ROW(__sync_lock_test_and_set),
 324     BUILTIN_ROW(__sync_lock_release)
 325   };
 326 #undef BUILTIN_ROW
 327
 328   // Determine the index of the size.
 329   unsigned SizeIndex;
 330   switch (Context.getTypeSizeInChars(ValType).getQuantity()) {
 331   case 1: SizeIndex = 0; break;
 332   case 2: SizeIndex = 1; break;
 333   case 4: SizeIndex = 2; break;
 334   case 8: SizeIndex = 3; break;
 335   case 16: SizeIndex = 4; break;
 336   default:
 337     return Diag(DRE->getLocStart(), diag::err_atomic_builtin_pointer_size)
 338              << FirstArg->getType() << FirstArg->getSourceRange();
 339   }
 340
 341   // Each of these builtins has one pointer argument, followed by some number of
 342   // values (0, 1 or 2) followed by a potentially empty varags list of stuff
 343   // that we ignore.  Find out which row of BuiltinIndices to read from as well
 344   // as the number of fixed args.
 345   unsigned BuiltinID = FDecl->getBuiltinID();
 346   unsigned BuiltinIndex, NumFixed = 1;
 347   switch (BuiltinID) {
 348   default: assert(0 && "Unknown overloaded atomic builtin!");
 349   case Builtin::BI__sync_fetch_and_add: BuiltinIndex = 0; break;
 350   case Builtin::BI__sync_fetch_and_sub: BuiltinIndex = 1; break;
 351   case Builtin::BI__sync_fetch_and_or:  BuiltinIndex = 2; break;
 352   case Builtin::BI__sync_fetch_and_and: BuiltinIndex = 3; break;
 353   case Builtin::BI__sync_fetch_and_xor: BuiltinIndex = 4; break;
 354   case Builtin::BI__sync_fetch_and_nand:BuiltinIndex = 5; break;
 355
 356   case Builtin::BI__sync_add_and_fetch: BuiltinIndex = 6; break;
 357   case Builtin::BI__sync_sub_and_fetch: BuiltinIndex = 7; break;
 358   case Builtin::BI__sync_and_and_fetch: BuiltinIndex = 8; break;
 359   case Builtin::BI__sync_or_and_fetch:  BuiltinIndex = 9; break;
 360   case Builtin::BI__sync_xor_and_fetch: BuiltinIndex =10; break;
 361   case Builtin::BI__sync_nand_and_fetch:BuiltinIndex =11; break;
 362
 363   case Builtin::BI__sync_val_compare_and_swap:
 364     BuiltinIndex = 12;
 365     NumFixed = 2;
 366     break;
 367   case Builtin::BI__sync_bool_compare_and_swap:
 368     BuiltinIndex = 13;
 369     NumFixed = 2;
 370     break;
 371   case Builtin::BI__sync_lock_test_and_set: BuiltinIndex = 14; break;
 372   case Builtin::BI__sync_lock_release:
 373     BuiltinIndex = 15;
 374     NumFixed = 0;
 375     break;
 376   }
 377
 378   // Now that we know how many fixed arguments we expect, first check that we
 379   // have at least that many.
 380   if (TheCall->getNumArgs() < 1+NumFixed)
 381     return Diag(TheCall->getLocEnd(), diag::err_typecheck_call_too_few_args)
 382             << 0 << TheCall->getCallee()->getSourceRange();
 383
 384
 385   // Get the decl for the concrete builtin from this, we can tell what the
 386   // concrete integer type we should convert to is.
 387   unsigned NewBuiltinID = BuiltinIndices[BuiltinIndex][SizeIndex];
 388   const char *NewBuiltinName = Context.BuiltinInfo.GetName(NewBuiltinID);
 389   IdentifierInfo *NewBuiltinII = PP.getIdentifierInfo(NewBuiltinName);
 390   FunctionDecl *NewBuiltinDecl =
 391     cast<FunctionDecl>(LazilyCreateBuiltin(NewBuiltinII, NewBuiltinID,
 392                                            TUScope, false, DRE->getLocStart()));
 393   const FunctionProtoType *BuiltinFT =
 394     NewBuiltinDecl->getType()->getAs<FunctionProtoType>();
 395   ValType = BuiltinFT->getArgType(0)->getAs<PointerType>()->getPointeeType();
 396
 397   // If the first type needs to be converted (e.g. void** -> int*), do it now.
 398   if (BuiltinFT->getArgType(0) != FirstArg->getType()) {
 399     ImpCastExprToType(FirstArg, BuiltinFT->getArgType(0), CastExpr::CK_BitCast);
 400     TheCall->setArg(0, FirstArg);
 401   }
 402
 403   // Next, walk the valid ones promoting to the right type.
 404   for (unsigned i = 0; i != NumFixed; ++i) {
 405     Expr *Arg = TheCall->getArg(i+1);
 406
 407     // If the argument is an implicit cast, then there was a promotion due to
 408     // "...", just remove it now.
 409     if (ImplicitCastExpr *ICE = dyn_cast<ImplicitCastExpr>(Arg)) {
 410       Arg = ICE->getSubExpr();
 411       ICE->setSubExpr(0);
 412       ICE->Destroy(Context);
 413       TheCall->setArg(i+1, Arg);
 414     }
 415
 416     // GCC does an implicit conversion to the pointer or integer ValType.  This
 417     // can fail in some cases (1i -> int**), check for this error case now.
 418     CastExpr::CastKind Kind = CastExpr::CK_Unknown;
 419     CXXMethodDecl *ConversionDecl = 0;
 420     if (CheckCastTypes(Arg->getSourceRange(), ValType, Arg, Kind,
 421                        ConversionDecl))
 422       return true;
 423
 424     // Okay, we have something that *can* be converted to the right type.  Check
 425     // to see if there is a potentially weird extension going on here.  This can
 426     // happen when you do an atomic operation on something like an char* and
 427     // pass in 42.  The 42 gets converted to char.  This is even more strange
 428     // for things like 45.123 -> char, etc.
 429     // FIXME: Do this check.
 430     ImpCastExprToType(Arg, ValType, Kind, /*isLvalue=*/false);
 431     TheCall->setArg(i+1, Arg);
 432   }
 433
 434   // Switch the DeclRefExpr to refer to the new decl.
 435   DRE->setDecl(NewBuiltinDecl);
 436   DRE->setType(NewBuiltinDecl->getType());
 437
 438   // Set the callee in the CallExpr.
 439   // FIXME: This leaks the original parens and implicit casts.
 440   Expr *PromotedCall = DRE;
 441   UsualUnaryConversions(PromotedCall);
 442   TheCall->setCallee(PromotedCall);
 443
 444
 445   // Change the result type of the call to match the result type of the decl.
 446   TheCall->setType(NewBuiltinDecl->getResultType());
 447   return false;
 448 }
 449
 450
 451 /// CheckObjCString - Checks that the argument to the builtin
 452 /// CFString constructor is correct
 453 /// FIXME: GCC currently emits the following warning:
 454 /// "warning: input conversion stopped due to an input byte that does not
 455 ///           belong to the input codeset UTF-8"
 456 /// Note: It might also make sense to do the UTF-16 conversion here (would
 457 /// simplify the backend).
 458 bool Sema::CheckObjCString(Expr *Arg) {
 459   Arg = Arg->IgnoreParenCasts();
 460   StringLiteral *Literal = dyn_cast<StringLiteral>(Arg);
 461
 462   if (!Literal || Literal->isWide()) {
 463     Diag(Arg->getLocStart(), diag::err_cfstring_literal_not_string_constant)
 464       << Arg->getSourceRange();
 465     return true;
 466   }
 467
 468   const char *Data = Literal->getStrData();
 469   unsigned Length = Literal->getByteLength();
 470
 471   for (unsigned i = 0; i < Length; ++i) {
 472     if (!Data[i]) {
 473       Diag(getLocationOfStringLiteralByte(Literal, i),
 474            diag::warn_cfstring_literal_contains_nul_character)
 475         << Arg->getSourceRange();
 476       break;
 477     }
 478   }
 479
 480   return false;
 481 }
 482
 483 /// SemaBuiltinVAStart - Check the arguments to __builtin_va_start for validity.
 484 /// Emit an error and return true on failure, return false on success.
 485 bool Sema::SemaBuiltinVAStart(CallExpr *TheCall) {
 486   Expr *Fn = TheCall->getCallee();
 487   if (TheCall->getNumArgs() > 2) {
 488     Diag(TheCall->getArg(2)->getLocStart(),
 489          diag::err_typecheck_call_too_many_args)
 490       << 0 /*function call*/ << Fn->getSourceRange()
 491       << SourceRange(TheCall->getArg(2)->getLocStart(),
 492                      (*(TheCall->arg_end()-1))->getLocEnd());
 493     return true;
 494   }
 495
 496   if (TheCall->getNumArgs() < 2) {
 497     return Diag(TheCall->getLocEnd(), diag::err_typecheck_call_too_few_args)
 498       << 0 /*function call*/;
 499   }
 500
 501   // Determine whether the current function is variadic or not.
 502   bool isVariadic;
 503   if (CurBlock)
 504     isVariadic = CurBlock->isVariadic;
 505   else if (getCurFunctionDecl()) {
 506     if (FunctionProtoType* FTP =
 507             dyn_cast<FunctionProtoType>(getCurFunctionDecl()->getType()))
 508       isVariadic = FTP->isVariadic();
 509     else
 510       isVariadic = false;
 511   } else {
 512     isVariadic = getCurMethodDecl()->isVariadic();
 513   }
 514
 515   if (!isVariadic) {
 516     Diag(Fn->getLocStart(), diag::err_va_start_used_in_non_variadic_function);
 517     return true;
 518   }
 519
 520   // Verify that the second argument to the builtin is the last argument of the
 521   // current function or method.
 522   bool SecondArgIsLastNamedArgument = false;
 523   const Expr *Arg = TheCall->getArg(1)->IgnoreParenCasts();
 524
 525   if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Arg)) {
 526     if (const ParmVarDecl *PV = dyn_cast<ParmVarDecl>(DR->getDecl())) {
 527       // FIXME: This isn't correct for methods (results in bogus warning).
 528       // Get the last formal in the current function.
 529       const ParmVarDecl *LastArg;
 530       if (CurBlock)
 531         LastArg = *(CurBlock->TheDecl->param_end()-1);
 532       else if (FunctionDecl *FD = getCurFunctionDecl())
 533         LastArg = *(FD->param_end()-1);
 534       else
 535         LastArg = *(getCurMethodDecl()->param_end()-1);
 536       SecondArgIsLastNamedArgument = PV == LastArg;
 537     }
 538   }
 539
 540   if (!SecondArgIsLastNamedArgument)
 541     Diag(TheCall->getArg(1)->getLocStart(),
 542          diag::warn_second_parameter_of_va_start_not_last_named_argument);
 543   return false;
 544 }
 545
 546 /// SemaBuiltinUnorderedCompare - Handle functions like __builtin_isgreater and
 547 /// friends.  This is declared to take (...), so we have to check everything.
 548 bool Sema::SemaBuiltinUnorderedCompare(CallExpr *TheCall) {
 549   if (TheCall->getNumArgs() < 2)
 550     return Diag(TheCall->getLocEnd(), diag::err_typecheck_call_too_few_args)
 551       << 0 /*function call*/;
 552   if (TheCall->getNumArgs() > 2)
 553     return Diag(TheCall->getArg(2)->getLocStart(),
 554                 diag::err_typecheck_call_too_many_args)
 555       << 0 /*function call*/
 556       << SourceRange(TheCall->getArg(2)->getLocStart(),
 557                      (*(TheCall->arg_end()-1))->getLocEnd());
 558
 559   Expr *OrigArg0 = TheCall->getArg(0);
 560   Expr *OrigArg1 = TheCall->getArg(1);
 561
 562   // Do standard promotions between the two arguments, returning their common
 563   // type.
 564   QualType Res = UsualArithmeticConversions(OrigArg0, OrigArg1, false);
 565
 566   // Make sure any conversions are pushed back into the call; this is
 567   // type safe since unordered compare builtins are declared as "_Bool
 568   // foo(...)".
 569   TheCall->setArg(0, OrigArg0);
 570   TheCall->setArg(1, OrigArg1);
 571
 572   if (OrigArg0->isTypeDependent() || OrigArg1->isTypeDependent())
 573     return false;
 574
 575   // If the common type isn't a real floating type, then the arguments were
 576   // invalid for this operation.
 577   if (!Res->isRealFloatingType())
 578     return Diag(OrigArg0->getLocStart(),
 579                 diag::err_typecheck_call_invalid_ordered_compare)
 580       << OrigArg0->getType() << OrigArg1->getType()
 581       << SourceRange(OrigArg0->getLocStart(), OrigArg1->getLocEnd());
 582
 583   return false;
 584 }
 585
 586 /// SemaBuiltinUnorderedCompare - Handle functions like __builtin_isnan and
 587 /// friends.  This is declared to take (...), so we have to check everything.
 588 bool Sema::SemaBuiltinUnaryFP(CallExpr *TheCall) {
 589   if (TheCall->getNumArgs() < 1)
 590     return Diag(TheCall->getLocEnd(), diag::err_typecheck_call_too_few_args)
 591       << 0 /*function call*/;
 592   if (TheCall->getNumArgs() > 1)
 593     return Diag(TheCall->getArg(1)->getLocStart(),
 594                 diag::err_typecheck_call_too_many_args)
 595       << 0 /*function call*/
 596       << SourceRange(TheCall->getArg(1)->getLocStart(),
 597                      (*(TheCall->arg_end()-1))->getLocEnd());
 598
 599   Expr *OrigArg = TheCall->getArg(0);
 600
 601   if (OrigArg->isTypeDependent())
 602     return false;
 603
 604   // This operation requires a floating-point number
 605   if (!OrigArg->getType()->isRealFloatingType())
 606     return Diag(OrigArg->getLocStart(),
 607                 diag::err_typecheck_call_invalid_unary_fp)
 608       << OrigArg->getType() << OrigArg->getSourceRange();
 609
 610   return false;
 611 }
 612
 613 bool Sema::SemaBuiltinStackAddress(CallExpr *TheCall) {
 614   // The signature for these builtins is exact; the only thing we need
 615   // to check is that the argument is a constant.
 616   SourceLocation Loc;
 617   if (!TheCall->getArg(0)->isTypeDependent() &&
 618       !TheCall->getArg(0)->isValueDependent() &&
 619       !TheCall->getArg(0)->isIntegerConstantExpr(Context, &Loc))
 620     return Diag(Loc, diag::err_stack_const_level) << TheCall->getSourceRange();
 621
 622   return false;
 623 }
 624
 625 /// SemaBuiltinShuffleVector - Handle __builtin_shufflevector.
 626 // This is declared to take (...), so we have to check everything.
 627 Action::OwningExprResult Sema::SemaBuiltinShuffleVector(CallExpr *TheCall) {
 628   if (TheCall->getNumArgs() < 3)
 629     return ExprError(Diag(TheCall->getLocEnd(),
 630                           diag::err_typecheck_call_too_few_args)
 631       << 0 /*function call*/ << TheCall->getSourceRange());
 632
 633   unsigned numElements = std::numeric_limits<unsigned>::max();
 634   if (!TheCall->getArg(0)->isTypeDependent() &&
 635       !TheCall->getArg(1)->isTypeDependent()) {
 636     QualType FAType = TheCall->getArg(0)->getType();
 637     QualType SAType = TheCall->getArg(1)->getType();
 638
 639     if (!FAType->isVectorType() || !SAType->isVectorType()) {
 640       Diag(TheCall->getLocStart(), diag::err_shufflevector_non_vector)
 641         << SourceRange(TheCall->getArg(0)->getLocStart(),
 642                        TheCall->getArg(1)->getLocEnd());
 643       return ExprError();
 644     }
 645
 646     if (!Context.hasSameUnqualifiedType(FAType, SAType)) {
 647       Diag(TheCall->getLocStart(), diag::err_shufflevector_incompatible_vector)
 648         << SourceRange(TheCall->getArg(0)->getLocStart(),
 649                        TheCall->getArg(1)->getLocEnd());
 650       return ExprError();
 651     }
 652
 653     numElements = FAType->getAs<VectorType>()->getNumElements();
 654     if (TheCall->getNumArgs() != numElements+2) {
 655       if (TheCall->getNumArgs() < numElements+2)
 656         return ExprError(Diag(TheCall->getLocEnd(),
 657                               diag::err_typecheck_call_too_few_args)
 658                  << 0 /*function call*/ << TheCall->getSourceRange());
 659       return ExprError(Diag(TheCall->getLocEnd(),
 660                             diag::err_typecheck_call_too_many_args)
 661                  << 0 /*function call*/ << TheCall->getSourceRange());
 662     }
 663   }
 664
 665   for (unsigned i = 2; i < TheCall->getNumArgs(); i++) {
 666     if (TheCall->getArg(i)->isTypeDependent() ||
 667         TheCall->getArg(i)->isValueDependent())
 668       continue;
 669
 670     llvm::APSInt Result(32);
 671     if (!TheCall->getArg(i)->isIntegerConstantExpr(Result, Context))
 672       return ExprError(Diag(TheCall->getLocStart(),
 673                   diag::err_shufflevector_nonconstant_argument)
 674                 << TheCall->getArg(i)->getSourceRange());
 675
 676     if (Result.getActiveBits() > 64 || Result.getZExtValue() >= numElements*2)
 677       return ExprError(Diag(TheCall->getLocStart(),
 678                   diag::err_shufflevector_argument_too_large)
 679                << TheCall->getArg(i)->getSourceRange());
 680   }
 681
 682   llvm::SmallVector<Expr*, 32> exprs;
 683
 684   for (unsigned i = 0, e = TheCall->getNumArgs(); i != e; i++) {
 685     exprs.push_back(TheCall->getArg(i));
 686     TheCall->setArg(i, 0);
 687   }
 688
 689   return Owned(new (Context) ShuffleVectorExpr(Context, exprs.begin(),
 690                                             exprs.size(), exprs[0]->getType(),
 691                                             TheCall->getCallee()->getLocStart(),
 692                                             TheCall->getRParenLoc()));
 693 }
 694
 695 /// SemaBuiltinPrefetch - Handle __builtin_prefetch.
 696 // This is declared to take (const void*, ...) and can take two
 697 // optional constant int args.
 698 bool Sema::SemaBuiltinPrefetch(CallExpr *TheCall) {
 699   unsigned NumArgs = TheCall->getNumArgs();
 700
 701   if (NumArgs > 3)
 702     return Diag(TheCall->getLocEnd(), diag::err_typecheck_call_too_many_args)
 703              << 0 /*function call*/ << TheCall->getSourceRange();
 704
 705   // Argument 0 is checked for us and the remaining arguments must be
 706   // constant integers.
 707   for (unsigned i = 1; i != NumArgs; ++i) {
 708     Expr *Arg = TheCall->getArg(i);
 709     if (Arg->isTypeDependent())
 710       continue;
 711
 712     if (!Arg->getType()->isIntegralType())
 713       return Diag(TheCall->getLocStart(), diag::err_prefetch_invalid_arg_type)
 714               << Arg->getSourceRange();
 715
 716     ImpCastExprToType(Arg, Context.IntTy, CastExpr::CK_IntegralCast);
 717     TheCall->setArg(i, Arg);
 718
 719     if (Arg->isValueDependent())
 720       continue;
 721
 722     llvm::APSInt Result;
 723     if (!Arg->isIntegerConstantExpr(Result, Context))
 724       return Diag(TheCall->getLocStart(), diag::err_prefetch_invalid_arg_ice)
 725         << SourceRange(Arg->getLocStart(), Arg->getLocEnd());
 726
 727     // FIXME: gcc issues a warning and rewrites these to 0. These
 728     // seems especially odd for the third argument since the default
 729     // is 3.
 730     if (i == 1) {
 731       if (Result.getLimitedValue() > 1)
 732         return Diag(TheCall->getLocStart(), diag::err_argument_invalid_range)
 733              << "0" << "1" << Arg->getSourceRange();
 734     } else {
 735       if (Result.getLimitedValue() > 3)
 736         return Diag(TheCall->getLocStart(), diag::err_argument_invalid_range)
 737             << "0" << "3" << Arg->getSourceRange();
 738     }
 739   }
 740
 741   return false;
 742 }
 743
 744 /// SemaBuiltinEHReturnDataRegNo - Handle __builtin_eh_return_data_regno, the
 745 /// operand must be an integer constant.
 746 bool Sema::SemaBuiltinEHReturnDataRegNo(CallExpr *TheCall) {
 747   llvm::APSInt Result;
 748   if (!TheCall->getArg(0)->isIntegerConstantExpr(Result, Context))
 749     return Diag(TheCall->getLocStart(), diag::err_expr_not_ice)
 750       << TheCall->getArg(0)->getSourceRange();
 751
 752   return false;
 753 }
 754
 755
 756 /// SemaBuiltinObjectSize - Handle __builtin_object_size(void *ptr,
 757 /// int type). This simply type checks that type is one of the defined
 758 /// constants (0-3).
 759 // For compatability check 0-3, llvm only handles 0 and 2.
 760 bool Sema::SemaBuiltinObjectSize(CallExpr *TheCall) {
 761   Expr *Arg = TheCall->getArg(1);
 762   if (Arg->isTypeDependent())
 763     return false;
 764
 765   QualType ArgType = Arg->getType();
 766   const BuiltinType *BT = ArgType->getAs<BuiltinType>();
 767   llvm::APSInt Result(32);
 768   if (!BT || BT->getKind() != BuiltinType::Int)
 769     return Diag(TheCall->getLocStart(), diag::err_object_size_invalid_argument)
 770              << SourceRange(Arg->getLocStart(), Arg->getLocEnd());
 771
 772   if (Arg->isValueDependent())
 773     return false;
 774
 775   if (!Arg->isIntegerConstantExpr(Result, Context)) {
 776     return Diag(TheCall->getLocStart(), diag::err_object_size_invalid_argument)
 777              << SourceRange(Arg->getLocStart(), Arg->getLocEnd());
 778   }
 779
 780   if (Result.getSExtValue() < 0 || Result.getSExtValue() > 3) {
 781     return Diag(TheCall->getLocStart(), diag::err_argument_invalid_range)
 782              << "0" << "3" << SourceRange(Arg->getLocStart(), Arg->getLocEnd());
 783   }
 784
 785   return false;
 786 }
 787
 788 /// SemaBuiltinLongjmp - Handle __builtin_longjmp(void *env[5], int val).
 789 /// This checks that val is a constant 1.
 790 bool Sema::SemaBuiltinLongjmp(CallExpr *TheCall) {
 791   Expr *Arg = TheCall->getArg(1);
 792   if (Arg->isTypeDependent() || Arg->isValueDependent())
 793     return false;
 794
 795   llvm::APSInt Result(32);
 796   if (!Arg->isIntegerConstantExpr(Result, Context) || Result != 1)
 797     return Diag(TheCall->getLocStart(), diag::err_builtin_longjmp_invalid_val)
 798              << SourceRange(Arg->getLocStart(), Arg->getLocEnd());
 799
 800   return false;
 801 }
 802
 803 // Handle i > 1 ? "x" : "y", recursivelly
 804 bool Sema::SemaCheckStringLiteral(const Expr *E, const CallExpr *TheCall,
 805                                   bool HasVAListArg,
 806                                   unsigned format_idx, unsigned firstDataArg) {
 807   if (E->isTypeDependent() || E->isValueDependent())
 808     return false;
 809
 810   switch (E->getStmtClass()) {
 811   case Stmt::ConditionalOperatorClass: {
 812     const ConditionalOperator *C = cast<ConditionalOperator>(E);
 813     return SemaCheckStringLiteral(C->getTrueExpr(), TheCall,
 814                                   HasVAListArg, format_idx, firstDataArg)
 815         && SemaCheckStringLiteral(C->getRHS(), TheCall,
 816                                   HasVAListArg, format_idx, firstDataArg);
 817   }
 818
 819   case Stmt::ImplicitCastExprClass: {
 820     const ImplicitCastExpr *Expr = cast<ImplicitCastExpr>(E);
 821     return SemaCheckStringLiteral(Expr->getSubExpr(), TheCall, HasVAListArg,
 822                                   format_idx, firstDataArg);
 823   }
 824
 825   case Stmt::ParenExprClass: {
 826     const ParenExpr *Expr = cast<ParenExpr>(E);
 827     return SemaCheckStringLiteral(Expr->getSubExpr(), TheCall, HasVAListArg,
 828                                   format_idx, firstDataArg);
 829   }
 830
 831   case Stmt::DeclRefExprClass: {
 832     const DeclRefExpr *DR = cast<DeclRefExpr>(E);
 833
 834     // As an exception, do not flag errors for variables binding to
 835     // const string literals.
 836     if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) {
 837       bool isConstant = false;
 838       QualType T = DR->getType();
 839
 840       if (const ArrayType *AT = Context.getAsArrayType(T)) {
 841         isConstant = AT->getElementType().isConstant(Context);
 842       } else if (const PointerType *PT = T->getAs<PointerType>()) {
 843         isConstant = T.isConstant(Context) &&
 844                      PT->getPointeeType().isConstant(Context);
 845       }
 846
 847       if (isConstant) {
 848         const VarDecl *Def = 0;
 849         if (const Expr *Init = VD->getDefinition(Def))
 850           return SemaCheckStringLiteral(Init, TheCall,
 851                                         HasVAListArg, format_idx, firstDataArg);
 852       }
 853
 854       // For vprintf* functions (i.e., HasVAListArg==true), we add a
 855       // special check to see if the format string is a function parameter
 856       // of the function calling the printf function.  If the function
 857       // has an attribute indicating it is a printf-like function, then we
 858       // should suppress warnings concerning non-literals being used in a call
 859       // to a vprintf function.  For example:
 860       //
 861       // void
 862       // logmessage(char const *fmt __attribute__ (format (printf, 1, 2)), ...){
 863       //      va_list ap;
 864       //      va_start(ap, fmt);
 865       //      vprintf(fmt, ap);  // Do NOT emit a warning about "fmt".
 866       //      ...
 867       //
 868       //
 869       //  FIXME: We don't have full attribute support yet, so just check to see
 870       //    if the argument is a DeclRefExpr that references a parameter.  We'll
 871       //    add proper support for checking the attribute later.
 872       if (HasVAListArg)
 873         if (isa<ParmVarDecl>(VD))
 874           return true;
 875     }
 876
 877     return false;
 878   }
 879
 880   case Stmt::CallExprClass: {
 881     const CallExpr *CE = cast<CallExpr>(E);
 882     if (const ImplicitCastExpr *ICE
 883           = dyn_cast<ImplicitCastExpr>(CE->getCallee())) {
 884       if (const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(ICE->getSubExpr())) {
 885         if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(DRE->getDecl())) {
 886           if (const FormatArgAttr *FA = FD->getAttr<FormatArgAttr>()) {
 887             unsigned ArgIndex = FA->getFormatIdx();
 888             const Expr *Arg = CE->getArg(ArgIndex - 1);
 889
 890             return SemaCheckStringLiteral(Arg, TheCall, HasVAListArg,
 891                                           format_idx, firstDataArg);
 892           }
 893         }
 894       }
 895     }
 896
 897     return false;
 898   }
 899   case Stmt::ObjCStringLiteralClass:
 900   case Stmt::StringLiteralClass: {
 901     const StringLiteral *StrE = NULL;
 902
 903     if (const ObjCStringLiteral *ObjCFExpr = dyn_cast<ObjCStringLiteral>(E))
 904       StrE = ObjCFExpr->getString();
 905     else
 906       StrE = cast<StringLiteral>(E);
 907
 908     if (StrE) {
 909       CheckPrintfString(StrE, E, TheCall, HasVAListArg, format_idx,
 910                         firstDataArg);
 911       return true;
 912     }
 913
 914     return false;
 915   }
 916
 917   default:
 918     return false;
 919   }
 920 }
 921
 922 void
 923 Sema::CheckNonNullArguments(const NonNullAttr *NonNull,
 924                             const CallExpr *TheCall) {
 925   for (NonNullAttr::iterator i = NonNull->begin(), e = NonNull->end();
 926        i != e; ++i) {
 927     const Expr *ArgExpr = TheCall->getArg(*i);
 928     if (ArgExpr->isNullPointerConstant(Context,
 929                                        Expr::NPC_ValueDependentIsNotNull))
 930       Diag(TheCall->getCallee()->getLocStart(), diag::warn_null_arg)
 931         << ArgExpr->getSourceRange();
 932   }
 933 }
 934
 935 /// CheckPrintfArguments - Check calls to printf (and similar functions) for
 936 /// correct use of format strings.
 937 ///
 938 ///  HasVAListArg - A predicate indicating whether the printf-like
 939 ///    function is passed an explicit va_arg argument (e.g., vprintf)
 940 ///
 941 ///  format_idx - The index into Args for the format string.
 942 ///
 943 /// Improper format strings to functions in the printf family can be
 944 /// the source of bizarre bugs and very serious security holes.  A
 945 /// good source of information is available in the following paper
 946 /// (which includes additional references):
 947 ///
 948 ///  FormatGuard: Automatic Protection From printf Format String
 949 ///  Vulnerabilities, Proceedings of the 10th USENIX Security Symposium, 2001.
 950 ///
 951 /// Functionality implemented:
 952 ///
 953 ///  We can statically check the following properties for string
 954 ///  literal format strings for non v.*printf functions (where the
 955 ///  arguments are passed directly):
 956 //
 957 ///  (1) Are the number of format conversions equal to the number of
 958 ///      data arguments?
 959 ///
 960 ///  (2) Does each format conversion correctly match the type of the
 961 ///      corresponding data argument?  (TODO)
 962 ///
 963 /// Moreover, for all printf functions we can:
 964 ///
 965 ///  (3) Check for a missing format string (when not caught by type checking).
 966 ///
 967 ///  (4) Check for no-operation flags; e.g. using "#" with format
 968 ///      conversion 'c'  (TODO)
 969 ///
 970 ///  (5) Check the use of '%n', a major source of security holes.
 971 ///
 972 ///  (6) Check for malformed format conversions that don't specify anything.
 973 ///
 974 ///  (7) Check for empty format strings.  e.g: printf("");
 975 ///
 976 ///  (8) Check that the format string is a wide literal.
 977 ///
 978 /// All of these checks can be done by parsing the format string.
 979 ///
 980 /// For now, we ONLY do (1), (3), (5), (6), (7), and (8).
 981 void
 982 Sema::CheckPrintfArguments(const CallExpr *TheCall, bool HasVAListArg,
 983                            unsigned format_idx, unsigned firstDataArg) {
 984   const Expr *Fn = TheCall->getCallee();
 985
 986   // The way the format attribute works in GCC, the implicit this argument
 987   // of member functions is counted. However, it doesn't appear in our own
 988   // lists, so decrement format_idx in that case.
 989   if (isa<CXXMemberCallExpr>(TheCall)) {
 990     // Catch a format attribute mistakenly referring to the object argument.
 991     if (format_idx == 0)
 992       return;
 993     --format_idx;
 994     if(firstDataArg != 0)
 995       --firstDataArg;
 996   }
 997
 998   // CHECK: printf-like function is called with no format string.
 999   if (format_idx >= TheCall->getNumArgs()) {
1000     Diag(TheCall->getRParenLoc(), diag::warn_printf_missing_format_string)
1001       << Fn->getSourceRange();
1002     return;
1003   }
1004
1005   const Expr *OrigFormatExpr = TheCall->getArg(format_idx)->IgnoreParenCasts();
1006
1007   // CHECK: format string is not a string literal.
1008   //
1009   // Dynamically generated format strings are difficult to
1010   // automatically vet at compile time.  Requiring that format strings
1011   // are string literals: (1) permits the checking of format strings by
1012   // the compiler and thereby (2) can practically remove the source of
1013   // many format string exploits.
1014
1015   // Format string can be either ObjC string (e.g. @"%d") or
1016   // C string (e.g. "%d")
1017   // ObjC string uses the same format specifiers as C string, so we can use
1018   // the same format string checking logic for both ObjC and C strings.
1019   if (SemaCheckStringLiteral(OrigFormatExpr, TheCall, HasVAListArg, format_idx,
1020                              firstDataArg))
1021     return;  // Literal format string found, check done!
1022
1023   // If there are no arguments specified, warn with -Wformat-security, otherwise
1024   // warn only with -Wformat-nonliteral.
1025   if (TheCall->getNumArgs() == format_idx+1)
1026     Diag(TheCall->getArg(format_idx)->getLocStart(),
1027          diag::warn_printf_nonliteral_noargs)
1028       << OrigFormatExpr->getSourceRange();
1029   else
1030     Diag(TheCall->getArg(format_idx)->getLocStart(),
1031          diag::warn_printf_nonliteral)
1032            << OrigFormatExpr->getSourceRange();
1033 }
1034
1035 void Sema::CheckPrintfString(const StringLiteral *FExpr,
1036                              const Expr *OrigFormatExpr,
1037                              const CallExpr *TheCall, bool HasVAListArg,
1038                              unsigned format_idx, unsigned firstDataArg) {
1039
1040   const ObjCStringLiteral *ObjCFExpr =
1041     dyn_cast<ObjCStringLiteral>(OrigFormatExpr);
1042
1043   // CHECK: is the format string a wide literal?
1044   if (FExpr->isWide()) {
1045     Diag(FExpr->getLocStart(),
1046          diag::warn_printf_format_string_is_wide_literal)
1047       << OrigFormatExpr->getSourceRange();
1048     return;
1049   }
1050
1051   // Str - The format string.  NOTE: this is NOT null-terminated!
1052   const char *Str = FExpr->getStrData();
1053
1054   // CHECK: empty format string?
1055   unsigned StrLen = FExpr->getByteLength();
1056
1057   if (StrLen == 0) {
1058     Diag(FExpr->getLocStart(), diag::warn_printf_empty_format_string)
1059       << OrigFormatExpr->getSourceRange();
1060     return;
1061   }
1062
1063   // We process the format string using a binary state machine.  The
1064   // current state is stored in CurrentState.
1065   enum {
1066     state_OrdChr,
1067     state_Conversion
1068   } CurrentState = state_OrdChr;
1069
1070   // numConversions - The number of conversions seen so far.  This is
1071   //  incremented as we traverse the format string.
1072   unsigned numConversions = 0;
1073
1074   // numDataArgs - The number of data arguments after the format
1075   //  string.  This can only be determined for non vprintf-like
1076   //  functions.  For those functions, this value is 1 (the sole
1077   //  va_arg argument).
1078   unsigned numDataArgs = TheCall->getNumArgs()-firstDataArg;
1079
1080   // Inspect the format string.
1081   unsigned StrIdx = 0;
1082
1083   // LastConversionIdx - Index within the format string where we last saw
1084   //  a '%' character that starts a new format conversion.
1085   unsigned LastConversionIdx = 0;
1086
1087   for (; StrIdx < StrLen; ++StrIdx) {
1088
1089     // Is the number of detected conversion conversions greater than
1090     // the number of matching data arguments?  If so, stop.
1091     if (!HasVAListArg && numConversions > numDataArgs) break;
1092
1093     // Handle "\0"
1094     if (Str[StrIdx] == '\0') {
1095       // The string returned by getStrData() is not null-terminated,
1096       // so the presence of a null character is likely an error.
1097       Diag(getLocationOfStringLiteralByte(FExpr, StrIdx),
1098            diag::warn_printf_format_string_contains_null_char)
1099         <<  OrigFormatExpr->getSourceRange();
1100       return;
1101     }
1102
1103     // Ordinary characters (not processing a format conversion).
1104     if (CurrentState == state_OrdChr) {
1105       if (Str[StrIdx] == '%') {
1106         CurrentState = state_Conversion;
1107         LastConversionIdx = StrIdx;
1108       }
1109       continue;
1110     }
1111
1112     // Seen '%'.  Now processing a format conversion.
1113     switch (Str[StrIdx]) {
1114     // Handle dynamic precision or width specifier.
1115     case '*': {
1116       ++numConversions;
1117
1118       if (!HasVAListArg) {
1119         if (numConversions > numDataArgs) {
1120           SourceLocation Loc = getLocationOfStringLiteralByte(FExpr, StrIdx);
1121
1122           if (Str[StrIdx-1] == '.')
1123             Diag(Loc, diag::warn_printf_asterisk_precision_missing_arg)
1124               << OrigFormatExpr->getSourceRange();
1125           else
1126             Diag(Loc, diag::warn_printf_asterisk_width_missing_arg)
1127               << OrigFormatExpr->getSourceRange();
1128
1129           // Don't do any more checking.  We'll just emit spurious errors.
1130           return;
1131         }
1132
1133         // Perform type checking on width/precision specifier.
1134         const Expr *E = TheCall->getArg(format_idx+numConversions);
1135         if (const BuiltinType *BT = E->getType()->getAs<BuiltinType>())
1136           if (BT->getKind() == BuiltinType::Int)
1137             break;
1138
1139         SourceLocation Loc = getLocationOfStringLiteralByte(FExpr, StrIdx);
1140
1141         if (Str[StrIdx-1] == '.')
1142           Diag(Loc, diag::warn_printf_asterisk_precision_wrong_type)
1143           << E->getType() << E->getSourceRange();
1144         else
1145           Diag(Loc, diag::warn_printf_asterisk_width_wrong_type)
1146           << E->getType() << E->getSourceRange();
1147
1148         break;
1149       }
1150     }
1151
1152     // Characters which can terminate a format conversion
1153     // (e.g. "%d").  Characters that specify length modifiers or
1154     // other flags are handled by the default case below.
1155     //
1156     // FIXME: additional checks will go into the following cases.
1157     case 'i':
1158     case 'd':
1159     case 'o':
1160     case 'u':
1161     case 'x':
1162     case 'X':
1163     case 'D':
1164     case 'O':
1165     case 'U':
1166     case 'e':
1167     case 'E':
1168     case 'f':
1169     case 'F':
1170     case 'g':
1171     case 'G':
1172     case 'a':
1173     case 'A':
1174     case 'c':
1175     case 'C':
1176     case 'S':
1177     case 's':
1178     case 'p':
1179       ++numConversions;
1180       CurrentState = state_OrdChr;
1181       break;
1182
1183     case 'm':
1184       // FIXME: Warn in situations where this isn't supported!
1185       CurrentState = state_OrdChr;
1186       break;
1187
1188     // CHECK: Are we using "%n"?  Issue a warning.
1189     case 'n': {
1190       ++numConversions;
1191       CurrentState = state_OrdChr;
1192       SourceLocation Loc = getLocationOfStringLiteralByte(FExpr,
1193                                                           LastConversionIdx);
1194
1195       Diag(Loc, diag::warn_printf_write_back)<<OrigFormatExpr->getSourceRange();
1196       break;
1197     }
1198
1199     // Handle "%@"
1200     case '@':
1201       // %@ is allowed in ObjC format strings only.
1202       if (ObjCFExpr != NULL)
1203         CurrentState = state_OrdChr;
1204       else {
1205         // Issue a warning: invalid format conversion.
1206         SourceLocation Loc =
1207           getLocationOfStringLiteralByte(FExpr, LastConversionIdx);
1208
1209         Diag(Loc, diag::warn_printf_invalid_conversion)
1210           <<  std::string(Str+LastConversionIdx,
1211                           Str+std::min(LastConversionIdx+2, StrLen))
1212           << OrigFormatExpr->getSourceRange();
1213       }
1214       ++numConversions;
1215       break;
1216
1217     // Handle "%%"
1218     case '%':
1219       // Sanity check: Was the first "%" character the previous one?
1220       // If not, we will assume that we have a malformed format
1221       // conversion, and that the current "%" character is the start
1222       // of a new conversion.
1223       if (StrIdx - LastConversionIdx == 1)
1224         CurrentState = state_OrdChr;
1225       else {
1226         // Issue a warning: invalid format conversion.
1227         SourceLocation Loc =
1228           getLocationOfStringLiteralByte(FExpr, LastConversionIdx);
1229
1230         Diag(Loc, diag::warn_printf_invalid_conversion)
1231           << std::string(Str+LastConversionIdx, Str+StrIdx)
1232           << OrigFormatExpr->getSourceRange();
1233
1234         // This conversion is broken.  Advance to the next format
1235         // conversion.
1236         LastConversionIdx = StrIdx;
1237         ++numConversions;
1238       }
1239       break;
1240
1241     default:
1242       // This case catches all other characters: flags, widths, etc.
1243       // We should eventually process those as well.
1244       break;
1245     }
1246   }
1247
1248   if (CurrentState == state_Conversion) {
1249     // Issue a warning: invalid format conversion.
1250     SourceLocation Loc =
1251       getLocationOfStringLiteralByte(FExpr, LastConversionIdx);
1252
1253     Diag(Loc, diag::warn_printf_invalid_conversion)
1254       << std::string(Str+LastConversionIdx,
1255                      Str+std::min(LastConversionIdx+2, StrLen))
1256       << OrigFormatExpr->getSourceRange();
1257     return;
1258   }
1259
1260   if (!HasVAListArg) {
1261     // CHECK: Does the number of format conversions exceed the number
1262     //        of data arguments?
1263     if (numConversions > numDataArgs) {
1264       SourceLocation Loc =
1265         getLocationOfStringLiteralByte(FExpr, LastConversionIdx);
1266
1267       Diag(Loc, diag::warn_printf_insufficient_data_args)
1268         << OrigFormatExpr->getSourceRange();
1269     }
1270     // CHECK: Does the number of data arguments exceed the number of
1271     //        format conversions in the format string?
1272     else if (numConversions < numDataArgs)
1273       Diag(TheCall->getArg(format_idx+numConversions+1)->getLocStart(),
1274            diag::warn_printf_too_many_data_args)
1275         << OrigFormatExpr->getSourceRange();
1276   }
1277 }
1278
1279 //===--- CHECK: Return Address of Stack Variable --------------------------===//
1280
1281 static DeclRefExpr* EvalVal(Expr *E);
1282 static DeclRefExpr* EvalAddr(Expr* E);
1283
1284 /// CheckReturnStackAddr - Check if a return statement returns the address
1285 ///   of a stack variable.
1286 void
1287 Sema::CheckReturnStackAddr(Expr *RetValExp, QualType lhsType,
1288                            SourceLocation ReturnLoc) {
1289
1290   // Perform checking for returned stack addresses.
1291   if (lhsType->isPointerType() || lhsType->isBlockPointerType()) {
1292     if (DeclRefExpr *DR = EvalAddr(RetValExp))
1293       Diag(DR->getLocStart(), diag::warn_ret_stack_addr)
1294        << DR->getDecl()->getDeclName() << RetValExp->getSourceRange();
1295
1296     // Skip over implicit cast expressions when checking for block expressions.
1297     RetValExp = RetValExp->IgnoreParenCasts();
1298
1299     if (BlockExpr *C = dyn_cast<BlockExpr>(RetValExp))
1300       if (C->hasBlockDeclRefExprs())
1301         Diag(C->getLocStart(), diag::err_ret_local_block)
1302           << C->getSourceRange();
1303
1304     if (AddrLabelExpr *ALE = dyn_cast<AddrLabelExpr>(RetValExp))
1305       Diag(ALE->getLocStart(), diag::warn_ret_addr_label)
1306         << ALE->getSourceRange();
1307
1308   } else if (lhsType->isReferenceType()) {
1309     // Perform checking for stack values returned by reference.
1310     // Check for a reference to the stack
1311     if (DeclRefExpr *DR = EvalVal(RetValExp))
1312       Diag(DR->getLocStart(), diag::warn_ret_stack_ref)
1313         << DR->getDecl()->getDeclName() << RetValExp->getSourceRange();
1314   }
1315 }
1316
1317 /// EvalAddr - EvalAddr and EvalVal are mutually recursive functions that
1318 ///  check if the expression in a return statement evaluates to an address
1319 ///  to a location on the stack.  The recursion is used to traverse the
1320 ///  AST of the return expression, with recursion backtracking when we
1321 ///  encounter a subexpression that (1) clearly does not lead to the address
1322 ///  of a stack variable or (2) is something we cannot determine leads to
1323 ///  the address of a stack variable based on such local checking.
1324 ///
1325 ///  EvalAddr processes expressions that are pointers that are used as
1326 ///  references (and not L-values).  EvalVal handles all other values.
1327 ///  At the base case of the recursion is a check for a DeclRefExpr* in
1328 ///  the refers to a stack variable.
1329 ///
1330 ///  This implementation handles:
1331 ///
1332 ///   * pointer-to-pointer casts
1333 ///   * implicit conversions from array references to pointers
1334 ///   * taking the address of fields
1335 ///   * arbitrary interplay between "&" and "*" operators
1336 ///   * pointer arithmetic from an address of a stack variable
1337 ///   * taking the address of an array element where the array is on the stack
1338 static DeclRefExpr* EvalAddr(Expr *E) {
1339   // We should only be called for evaluating pointer expressions.
1340   assert((E->getType()->isAnyPointerType() ||
1341           E->getType()->isBlockPointerType() ||
1342           E->getType()->isObjCQualifiedIdType()) &&
1343          "EvalAddr only works on pointers");
1344
1345   // Our "symbolic interpreter" is just a dispatch off the currently
1346   // viewed AST node.  We then recursively traverse the AST by calling
1347   // EvalAddr and EvalVal appropriately.
1348   switch (E->getStmtClass()) {
1349   case Stmt::ParenExprClass:
1350     // Ignore parentheses.
1351     return EvalAddr(cast<ParenExpr>(E)->getSubExpr());
1352
1353   case Stmt::UnaryOperatorClass: {
1354     // The only unary operator that make sense to handle here
1355     // is AddrOf.  All others don't make sense as pointers.
1356     UnaryOperator *U = cast<UnaryOperator>(E);
1357
1358     if (U->getOpcode() == UnaryOperator::AddrOf)
1359       return EvalVal(U->getSubExpr());
1360     else
1361       return NULL;
1362   }
1363
1364   case Stmt::BinaryOperatorClass: {
1365     // Handle pointer arithmetic.  All other binary operators are not valid
1366     // in this context.
1367     BinaryOperator *B = cast<BinaryOperator>(E);
1368     BinaryOperator::Opcode op = B->getOpcode();
1369
1370     if (op != BinaryOperator::Add && op != BinaryOperator::Sub)
1371       return NULL;
1372
1373     Expr *Base = B->getLHS();
1374
1375     // Determine which argument is the real pointer base.  It could be
1376     // the RHS argument instead of the LHS.
1377     if (!Base->getType()->isPointerType()) Base = B->getRHS();
1378
1379     assert (Base->getType()->isPointerType());
1380     return EvalAddr(Base);
1381   }
1382
1383   // For conditional operators we need to see if either the LHS or RHS are
1384   // valid DeclRefExpr*s.  If one of them is valid, we return it.
1385   case Stmt::ConditionalOperatorClass: {
1386     ConditionalOperator *C = cast<ConditionalOperator>(E);
1387
1388     // Handle the GNU extension for missing LHS.
1389     if (Expr *lhsExpr = C->getLHS())
1390       if (DeclRefExpr* LHS = EvalAddr(lhsExpr))
1391         return LHS;
1392
1393      return EvalAddr(C->getRHS());
1394   }
1395
1396   // For casts, we need to handle conversions from arrays to
1397   // pointer values, and pointer-to-pointer conversions.
1398   case Stmt::ImplicitCastExprClass:
1399   case Stmt::CStyleCastExprClass:
1400   case Stmt::CXXFunctionalCastExprClass: {
1401     Expr* SubExpr = cast<CastExpr>(E)->getSubExpr();
1402     QualType T = SubExpr->getType();
1403
1404     if (SubExpr->getType()->isPointerType() ||
1405         SubExpr->getType()->isBlockPointerType() ||
1406         SubExpr->getType()->isObjCQualifiedIdType())
1407       return EvalAddr(SubExpr);
1408     else if (T->isArrayType())
1409       return EvalVal(SubExpr);
1410     else
1411       return 0;
1412   }
1413
1414   // C++ casts.  For dynamic casts, static casts, and const casts, we
1415   // are always converting from a pointer-to-pointer, so we just blow
1416   // through the cast.  In the case the dynamic cast doesn't fail (and
1417   // return NULL), we take the conservative route and report cases
1418   // where we return the address of a stack variable.  For Reinterpre
1419   // FIXME: The comment about is wrong; we're not always converting
1420   // from pointer to pointer. I'm guessing that this code should also
1421   // handle references to objects.
1422   case Stmt::CXXStaticCastExprClass:
1423   case Stmt::CXXDynamicCastExprClass:
1424   case Stmt::CXXConstCastExprClass:
1425   case Stmt::CXXReinterpretCastExprClass: {
1426       Expr *S = cast<CXXNamedCastExpr>(E)->getSubExpr();
1427       if (S->getType()->isPointerType() || S->getType()->isBlockPointerType())
1428         return EvalAddr(S);
1429       else
1430         return NULL;
1431   }
1432
1433   // Everything else: we simply don't reason about them.
1434   default:
1435     return NULL;
1436   }
1437 }
1438
1439
1440 ///  EvalVal - This function is complements EvalAddr in the mutual recursion.
1441 ///   See the comments for EvalAddr for more details.
1442 static DeclRefExpr* EvalVal(Expr *E) {
1443
1444   // We should only be called for evaluating non-pointer expressions, or
1445   // expressions with a pointer type that are not used as references but instead
1446   // are l-values (e.g., DeclRefExpr with a pointer type).
1447
1448   // Our "symbolic interpreter" is just a dispatch off the currently
1449   // viewed AST node.  We then recursively traverse the AST by calling
1450   // EvalAddr and EvalVal appropriately.
1451   switch (E->getStmtClass()) {
1452   case Stmt::DeclRefExprClass: {
1453     // DeclRefExpr: the base case.  When we hit a DeclRefExpr we are looking
1454     //  at code that refers to a variable's name.  We check if it has local
1455     //  storage within the function, and if so, return the expression.
1456     DeclRefExpr *DR = cast<DeclRefExpr>(E);
1457
1458     if (VarDecl *V = dyn_cast<VarDecl>(DR->getDecl()))
1459       if (V->hasLocalStorage() && !V->getType()->isReferenceType()) return DR;
1460
1461     return NULL;
1462   }
1463
1464   case Stmt::ParenExprClass:
1465     // Ignore parentheses.
1466     return EvalVal(cast<ParenExpr>(E)->getSubExpr());
1467
1468   case Stmt::UnaryOperatorClass: {
1469     // The only unary operator that make sense to handle here
1470     // is Deref.  All others don't resolve to a "name."  This includes
1471     // handling all sorts of rvalues passed to a unary operator.
1472     UnaryOperator *U = cast<UnaryOperator>(E);
1473
1474     if (U->getOpcode() == UnaryOperator::Deref)
1475       return EvalAddr(U->getSubExpr());
1476
1477     return NULL;
1478   }
1479
1480   case Stmt::ArraySubscriptExprClass: {
1481     // Array subscripts are potential references to data on the stack.  We
1482     // retrieve the DeclRefExpr* for the array variable if it indeed
1483     // has local storage.
1484     return EvalAddr(cast<ArraySubscriptExpr>(E)->getBase());
1485   }
1486
1487   case Stmt::ConditionalOperatorClass: {
1488     // For conditional operators we need to see if either the LHS or RHS are
1489     // non-NULL DeclRefExpr's.  If one is non-NULL, we return it.
1490     ConditionalOperator *C = cast<ConditionalOperator>(E);
1491
1492     // Handle the GNU extension for missing LHS.
1493     if (Expr *lhsExpr = C->getLHS())
1494       if (DeclRefExpr *LHS = EvalVal(lhsExpr))
1495         return LHS;
1496
1497     return EvalVal(C->getRHS());
1498   }
1499
1500   // Accesses to members are potential references to data on the stack.
1501   case Stmt::MemberExprClass: {
1502     MemberExpr *M = cast<MemberExpr>(E);
1503
1504     // Check for indirect access.  We only want direct field accesses.
1505     if (!M->isArrow())
1506       return EvalVal(M->getBase());
1507     else
1508       return NULL;
1509   }
1510
1511   // Everything else: we simply don't reason about them.
1512   default:
1513     return NULL;
1514   }
1515 }
1516
1517 //===--- CHECK: Floating-Point comparisons (-Wfloat-equal) ---------------===//
1518
1519 /// Check for comparisons of floating point operands using != and ==.
1520 /// Issue a warning if these are no self-comparisons, as they are not likely
1521 /// to do what the programmer intended.
1522 void Sema::CheckFloatComparison(SourceLocation loc, Expr* lex, Expr *rex) {
1523   bool EmitWarning = true;
1524
1525   Expr* LeftExprSansParen = lex->IgnoreParens();
1526   Expr* RightExprSansParen = rex->IgnoreParens();
1527
1528   // Special case: check for x == x (which is OK).
1529   // Do not emit warnings for such cases.
1530   if (DeclRefExpr* DRL = dyn_cast<DeclRefExpr>(LeftExprSansParen))
1531     if (DeclRefExpr* DRR = dyn_cast<DeclRefExpr>(RightExprSansParen))
1532       if (DRL->getDecl() == DRR->getDecl())
1533         EmitWarning = false;
1534
1535
1536   // Special case: check for comparisons against literals that can be exactly
1537   //  represented by APFloat.  In such cases, do not emit a warning.  This
1538   //  is a heuristic: often comparison against such literals are used to
1539   //  detect if a value in a variable has not changed.  This clearly can
1540   //  lead to false negatives.
1541   if (EmitWarning) {
1542     if (FloatingLiteral* FLL = dyn_cast<FloatingLiteral>(LeftExprSansParen)) {
1543       if (FLL->isExact())
1544         EmitWarning = false;
1545     } else
1546       if (FloatingLiteral* FLR = dyn_cast<FloatingLiteral>(RightExprSansParen)){
1547         if (FLR->isExact())
1548           EmitWarning = false;
1549     }
1550   }
1551
1552   // Check for comparisons with builtin types.
1553   if (EmitWarning)
1554     if (CallExpr* CL = dyn_cast<CallExpr>(LeftExprSansParen))
1555       if (CL->isBuiltinCall(Context))
1556         EmitWarning = false;
1557
1558   if (EmitWarning)
1559     if (CallExpr* CR = dyn_cast<CallExpr>(RightExprSansParen))
1560       if (CR->isBuiltinCall(Context))
1561         EmitWarning = false;
1562
1563   // Emit the diagnostic.
1564   if (EmitWarning)
1565     Diag(loc, diag::warn_floatingpoint_eq)
1566       << lex->getSourceRange() << rex->getSourceRange();
1567 }
1568
1569 //===--- CHECK: Integer mixed-sign comparisons (-Wsign-compare) --------===//
1570 //===--- CHECK: Lossy implicit conversions (-Wconversion) --------------===//
1571
1572 namespace {
1573
1574 /// Structure recording the 'active' range of an integer-valued
1575 /// expression.
1576 struct IntRange {
1577   /// The number of bits active in the int.
1578   unsigned Width;
1579
1580   /// True if the int is known not to have negative values.
1581   bool NonNegative;
1582
1583   IntRange() {}
1584   IntRange(unsigned Width, bool NonNegative)
1585     : Width(Width), NonNegative(NonNegative)
1586   {}
1587
1588   // Returns the range of the bool type.
1589   static IntRange forBoolType() {
1590     return IntRange(1, true);
1591   }
1592
1593   // Returns the range of an integral type.
1594   static IntRange forType(ASTContext &C, QualType T) {
1595     return forCanonicalType(C, T->getCanonicalTypeInternal().getTypePtr());
1596   }
1597
1598   // Returns the range of an integeral type based on its canonical
1599   // representation.
1600   static IntRange forCanonicalType(ASTContext &C, const Type *T) {
1601     assert(T->isCanonicalUnqualified());
1602
1603     if (const VectorType *VT = dyn_cast<VectorType>(T))
1604       T = VT->getElementType().getTypePtr();
1605     if (const ComplexType *CT = dyn_cast<ComplexType>(T))
1606       T = CT->getElementType().getTypePtr();
1607     if (const EnumType *ET = dyn_cast<EnumType>(T))
1608       T = ET->getDecl()->getIntegerType().getTypePtr();
1609
1610     const BuiltinType *BT = cast<BuiltinType>(T);
1611     assert(BT->isInteger());
1612
1613     return IntRange(C.getIntWidth(QualType(T, 0)), BT->isUnsignedInteger());
1614   }
1615
1616   // Returns the supremum of two ranges: i.e. their conservative merge.
1617   static IntRange join(const IntRange &L, const IntRange &R) {
1618     return IntRange(std::max(L.Width, R.Width),
1619                     L.NonNegative && R.NonNegative);
1620   }
1621
1622   // Returns the infinum of two ranges: i.e. their aggressive merge.
1623   static IntRange meet(const IntRange &L, const IntRange &R) {
1624     return IntRange(std::min(L.Width, R.Width),
1625                     L.NonNegative || R.NonNegative);
1626   }
1627 };
1628
1629 IntRange GetValueRange(ASTContext &C, llvm::APSInt &value, unsigned MaxWidth) {
1630   if (value.isSigned() && value.isNegative())
1631     return IntRange(value.getMinSignedBits(), false);
1632
1633   if (value.getBitWidth() > MaxWidth)
1634     value.trunc(MaxWidth);
1635
1636   // isNonNegative() just checks the sign bit without considering
1637   // signedness.
1638   return IntRange(value.getActiveBits(), true);
1639 }
1640
1641 IntRange GetValueRange(ASTContext &C, APValue &result, QualType Ty,
1642                        unsigned MaxWidth) {
1643   if (result.isInt())
1644     return GetValueRange(C, result.getInt(), MaxWidth);
1645
1646   if (result.isVector()) {
1647     IntRange R = GetValueRange(C, result.getVectorElt(0), Ty, MaxWidth);
1648     for (unsigned i = 1, e = result.getVectorLength(); i != e; ++i) {
1649       IntRange El = GetValueRange(C, result.getVectorElt(i), Ty, MaxWidth);
1650       R = IntRange::join(R, El);
1651     }
1652     return R;
1653   }
1654
1655   if (result.isComplexInt()) {
1656     IntRange R = GetValueRange(C, result.getComplexIntReal(), MaxWidth);
1657     IntRange I = GetValueRange(C, result.getComplexIntImag(), MaxWidth);
1658     return IntRange::join(R, I);
1659   }
1660
1661   // This can happen with lossless casts to intptr_t of "based" lvalues.
1662   // Assume it might use arbitrary bits.
1663   // FIXME: The only reason we need to pass the type in here is to get
1664   // the sign right on this one case.  It would be nice if APValue
1665   // preserved this.
1666   assert(result.isLValue());
1667   return IntRange(MaxWidth, Ty->isUnsignedIntegerType());
1668 }
1669
1670 /// Pseudo-evaluate the given integer expression, estimating the
1671 /// range of values it might take.
1672 ///
1673 /// \param MaxWidth - the width to which the value will be truncated
1674 IntRange GetExprRange(ASTContext &C, Expr *E, unsigned MaxWidth) {
1675   E = E->IgnoreParens();
1676
1677   // Try a full evaluation first.
1678   Expr::EvalResult result;
1679   if (E->Evaluate(result, C))
1680     return GetValueRange(C, result.Val, E->getType(), MaxWidth);
1681
1682   // I think we only want to look through implicit casts here; if the
1683   // user has an explicit widening cast, we should treat the value as
1684   // being of the new, wider type.
1685   if (ImplicitCastExpr *CE = dyn_cast<ImplicitCastExpr>(E)) {
1686     if (CE->getCastKind() == CastExpr::CK_NoOp)
1687       return GetExprRange(C, CE->getSubExpr(), MaxWidth);
1688
1689     IntRange OutputTypeRange = IntRange::forType(C, CE->getType());
1690
1691     bool isIntegerCast = (CE->getCastKind() == CastExpr::CK_IntegralCast);
1692     if (!isIntegerCast && CE->getCastKind() == CastExpr::CK_Unknown)
1693       isIntegerCast = CE->getSubExpr()->getType()->isIntegerType();
1694
1695     // Assume that non-integer casts can span the full range of the type.
1696     if (!isIntegerCast)
1697       return OutputTypeRange;
1698
1699     IntRange SubRange
1700       = GetExprRange(C, CE->getSubExpr(),
1701                      std::min(MaxWidth, OutputTypeRange.Width));
1702
1703     // Bail out if the subexpr's range is as wide as the cast type.
1704     if (SubRange.Width >= OutputTypeRange.Width)
1705       return OutputTypeRange;
1706
1707     // Otherwise, we take the smaller width, and we're non-negative if
1708     // either the output type or the subexpr is.
1709     return IntRange(SubRange.Width,
1710                     SubRange.NonNegative || OutputTypeRange.NonNegative);
1711   }
1712
1713   if (ConditionalOperator *CO = dyn_cast<ConditionalOperator>(E)) {
1714     // If we can fold the condition, just take that operand.
1715     bool CondResult;
1716     if (CO->getCond()->EvaluateAsBooleanCondition(CondResult, C))
1717       return GetExprRange(C, CondResult ? CO->getTrueExpr()
1718                                         : CO->getFalseExpr(),
1719                           MaxWidth);
1720
1721     // Otherwise, conservatively merge.
1722     IntRange L = GetExprRange(C, CO->getTrueExpr(), MaxWidth);
1723     IntRange R = GetExprRange(C, CO->getFalseExpr(), MaxWidth);
1724     return IntRange::join(L, R);
1725   }
1726
1727   if (BinaryOperator *BO = dyn_cast<BinaryOperator>(E)) {
1728     switch (BO->getOpcode()) {
1729
1730     // Boolean-valued operations are single-bit and positive.
1731     case BinaryOperator::LAnd:
1732     case BinaryOperator::LOr:
1733     case BinaryOperator::LT:
1734     case BinaryOperator::GT:
1735     case BinaryOperator::LE:
1736     case BinaryOperator::GE:
1737     case BinaryOperator::EQ:
1738     case BinaryOperator::NE:
1739       return IntRange::forBoolType();
1740
1741     // Operations with opaque sources are black-listed.
1742     case BinaryOperator::PtrMemD:
1743     case BinaryOperator::PtrMemI:
1744       return IntRange::forType(C, E->getType());
1745
1746     // Bitwise-and uses the *infinum* of the two source ranges.
1747     case BinaryOperator::And:
1748       return IntRange::meet(GetExprRange(C, BO->getLHS(), MaxWidth),
1749                             GetExprRange(C, BO->getRHS(), MaxWidth));
1750
1751     // Left shift gets black-listed based on a judgement call.
1752     case BinaryOperator::Shl:
1753       return IntRange::forType(C, E->getType());
1754
1755     // Right shift by a constant can narrow its left argument.
1756     case BinaryOperator::Shr: {
1757       IntRange L = GetExprRange(C, BO->getLHS(), MaxWidth);
1758
1759       // If the shift amount is a positive constant, drop the width by
1760       // that much.
1761       llvm::APSInt shift;
1762       if (BO->getRHS()->isIntegerConstantExpr(shift, C) &&
1763           shift.isNonNegative()) {
1764         unsigned zext = shift.getZExtValue();
1765         if (zext >= L.Width)
1766           L.Width = (L.NonNegative ? 0 : 1);
1767         else
1768           L.Width -= zext;
1769       }
1770
1771       return L;
1772     }
1773
1774     // Comma acts as its right operand.
1775     case BinaryOperator::Comma:
1776       return GetExprRange(C, BO->getRHS(), MaxWidth);
1777
1778     // Black-list pointer subtractions.
1779     case BinaryOperator::Sub:
1780       if (BO->getLHS()->getType()->isPointerType())
1781         return IntRange::forType(C, E->getType());
1782       // fallthrough
1783
1784     default:
1785       break;
1786     }
1787
1788     // Treat every other operator as if it were closed on the
1789     // narrowest type that encompasses both operands.
1790     IntRange L = GetExprRange(C, BO->getLHS(), MaxWidth);
1791     IntRange R = GetExprRange(C, BO->getRHS(), MaxWidth);
1792     return IntRange::join(L, R);
1793   }
1794
1795   if (UnaryOperator *UO = dyn_cast<UnaryOperator>(E)) {
1796     switch (UO->getOpcode()) {
1797     // Boolean-valued operations are white-listed.
1798     case UnaryOperator::LNot:
1799       return IntRange::forBoolType();
1800
1801     // Operations with opaque sources are black-listed.
1802     case UnaryOperator::Deref:
1803     case UnaryOperator::AddrOf: // should be impossible
1804     case UnaryOperator::OffsetOf:
1805       return IntRange::forType(C, E->getType());
1806
1807     default:
1808       return GetExprRange(C, UO->getSubExpr(), MaxWidth);
1809     }
1810   }
1811
1812   FieldDecl *BitField = E->getBitField();
1813   if (BitField) {
1814     llvm::APSInt BitWidthAP = BitField->getBitWidth()->EvaluateAsInt(C);
1815     unsigned BitWidth = BitWidthAP.getZExtValue();
1816
1817     return IntRange(BitWidth, BitField->getType()->isUnsignedIntegerType());
1818   }
1819
1820   return IntRange::forType(C, E->getType());
1821 }
1822
1823 /// Checks whether the given value, which currently has the given
1824 /// source semantics, has the same value when coerced through the
1825 /// target semantics.
1826 bool IsSameFloatAfterCast(const llvm::APFloat &value,
1827                           const llvm::fltSemantics &Src,
1828                           const llvm::fltSemantics &Tgt) {
1829   llvm::APFloat truncated = value;
1830
1831   bool ignored;
1832   truncated.convert(Src, llvm::APFloat::rmNearestTiesToEven, &ignored);
1833   truncated.convert(Tgt, llvm::APFloat::rmNearestTiesToEven, &ignored);
1834
1835   return truncated.bitwiseIsEqual(value);
1836 }
1837
1838 /// Checks whether the given value, which currently has the given
1839 /// source semantics, has the same value when coerced through the
1840 /// target semantics.
1841 ///
1842 /// The value might be a vector of floats (or a complex number).
1843 bool IsSameFloatAfterCast(const APValue &value,
1844                           const llvm::fltSemantics &Src,
1845                           const llvm::fltSemantics &Tgt) {
1846   if (value.isFloat())
1847     return IsSameFloatAfterCast(value.getFloat(), Src, Tgt);
1848
1849   if (value.isVector()) {
1850     for (unsigned i = 0, e = value.getVectorLength(); i != e; ++i)
1851       if (!IsSameFloatAfterCast(value.getVectorElt(i), Src, Tgt))
1852         return false;
1853     return true;
1854   }
1855
1856   assert(value.isComplexFloat());
1857   return (IsSameFloatAfterCast(value.getComplexFloatReal(), Src, Tgt) &&
1858           IsSameFloatAfterCast(value.getComplexFloatImag(), Src, Tgt));
1859 }
1860
1861 } // end anonymous namespace
1862
1863 /// \brief Implements -Wsign-compare.
1864 ///
1865 /// \param lex the left-hand expression
1866 /// \param rex the right-hand expression
1867 /// \param OpLoc the location of the joining operator
1868 /// \param Equality whether this is an "equality-like" join, which
1869 ///   suppresses the warning in some cases
1870 void Sema::CheckSignCompare(Expr *lex, Expr *rex, SourceLocation OpLoc,
1871                             const PartialDiagnostic &PD, bool Equality) {
1872   // Don't warn if we're in an unevaluated context.
1873   if (ExprEvalContexts.back().Context == Unevaluated)
1874     return;
1875
1876   // If either expression is value-dependent, don't warn. We'll get another
1877   // chance at instantiation time.
1878   if (lex->isValueDependent() || rex->isValueDependent())
1879     return;
1880
1881   QualType lt = lex->getType(), rt = rex->getType();
1882
1883   // Only warn if both operands are integral.
1884   if (!lt->isIntegerType() || !rt->isIntegerType())
1885     return;
1886
1887   // In C, the width of a bitfield determines its type, and the
1888   // declared type only contributes the signedness.  This duplicates
1889   // the work that will later be done by UsualUnaryConversions.
1890   // Eventually, this check will be reorganized in a way that avoids
1891   // this duplication.
1892   if (!getLangOptions().CPlusPlus) {
1893     QualType tmp;
1894     tmp = Context.isPromotableBitField(lex);
1895     if (!tmp.isNull()) lt = tmp;
1896     tmp = Context.isPromotableBitField(rex);
1897     if (!tmp.isNull()) rt = tmp;
1898   }
1899
1900   // The rule is that the signed operand becomes unsigned, so isolate the
1901   // signed operand.
1902   Expr *signedOperand = lex, *unsignedOperand = rex;
1903   QualType signedType = lt, unsignedType = rt;
1904   if (lt->isSignedIntegerType()) {
1905     if (rt->isSignedIntegerType()) return;
1906   } else {
1907     if (!rt->isSignedIntegerType()) return;
1908     std::swap(signedOperand, unsignedOperand);
1909     std::swap(signedType, unsignedType);
1910   }
1911
1912   unsigned unsignedWidth = Context.getIntWidth(unsignedType);
1913   unsigned signedWidth = Context.getIntWidth(signedType);
1914
1915   // If the unsigned type is strictly smaller than the signed type,
1916   // then (1) the result type will be signed and (2) the unsigned
1917   // value will fit fully within the signed type, and thus the result
1918   // of the comparison will be exact.
1919   if (signedWidth > unsignedWidth)
1920     return;
1921
1922   // Otherwise, calculate the effective ranges.
1923   IntRange signedRange = GetExprRange(Context, signedOperand, signedWidth);
1924   IntRange unsignedRange = GetExprRange(Context, unsignedOperand, unsignedWidth);
1925
1926   // We should never be unable to prove that the unsigned operand is
1927   // non-negative.
1928   assert(unsignedRange.NonNegative && "unsigned range includes negative?");
1929
1930   // If the signed operand is non-negative, then the signed->unsigned
1931   // conversion won't change it.
1932   if (signedRange.NonNegative)
1933     return;
1934
1935   // For (in)equality comparisons, if the unsigned operand is a
1936   // constant which cannot collide with a overflowed signed operand,
1937   // then reinterpreting the signed operand as unsigned will not
1938   // change the result of the comparison.
1939   if (Equality && unsignedRange.Width < unsignedWidth)
1940     return;
1941
1942   Diag(OpLoc, PD)
1943     << lt << rt << lex->getSourceRange() << rex->getSourceRange();
1944 }
1945
1946 /// Diagnose an implicit cast;  purely a helper for CheckImplicitConversion.
1947 static void DiagnoseImpCast(Sema &S, Expr *E, QualType T, unsigned diag) {
1948   S.Diag(E->getExprLoc(), diag) << E->getType() << T << E->getSourceRange();
1949 }
1950
1951 /// Implements -Wconversion.
1952 void Sema::CheckImplicitConversion(Expr *E, QualType T) {
1953   // Don't diagnose in unevaluated contexts.
1954   if (ExprEvalContexts.back().Context == Sema::Unevaluated)
1955     return;
1956
1957   // Don't diagnose for value-dependent expressions.
1958   if (E->isValueDependent())
1959     return;
1960
1961   const Type *Source = Context.getCanonicalType(E->getType()).getTypePtr();
1962   const Type *Target = Context.getCanonicalType(T).getTypePtr();
1963
1964   // Never diagnose implicit casts to bool.
1965   if (Target->isSpecificBuiltinType(BuiltinType::Bool))
1966     return;
1967
1968   // Strip vector types.
1969   if (isa<VectorType>(Source)) {
1970     if (!isa<VectorType>(Target))
1971       return DiagnoseImpCast(*this, E, T, diag::warn_impcast_vector_scalar);
1972
1973     Source = cast<VectorType>(Source)->getElementType().getTypePtr();
1974     Target = cast<VectorType>(Target)->getElementType().getTypePtr();
1975   }
1976
1977   // Strip complex types.
1978   if (isa<ComplexType>(Source)) {
1979     if (!isa<ComplexType>(Target))
1980       return DiagnoseImpCast(*this, E, T, diag::warn_impcast_complex_scalar);
1981
1982     Source = cast<ComplexType>(Source)->getElementType().getTypePtr();
1983     Target = cast<ComplexType>(Target)->getElementType().getTypePtr();
1984   }
1985
1986   const BuiltinType *SourceBT = dyn_cast<BuiltinType>(Source);
1987   const BuiltinType *TargetBT = dyn_cast<BuiltinType>(Target);
1988
1989   // If the source is floating point...
1990   if (SourceBT && SourceBT->isFloatingPoint()) {
1991     // ...and the target is floating point...
1992     if (TargetBT && TargetBT->isFloatingPoint()) {
1993       // ...then warn if we're dropping FP rank.
1994
1995       // Builtin FP kinds are ordered by increasing FP rank.
1996       if (SourceBT->getKind() > TargetBT->getKind()) {
1997         // Don't warn about float constants that are precisely
1998         // representable in the target type.
1999         Expr::EvalResult result;
2000         if (E->Evaluate(result, Context)) {
2001           // Value might be a float, a float vector, or a float complex.
2002           if (IsSameFloatAfterCast(result.Val,
2003                      Context.getFloatTypeSemantics(QualType(TargetBT, 0)),
2004                      Context.getFloatTypeSemantics(QualType(SourceBT, 0))))
2005             return;
2006         }
2007
2008         DiagnoseImpCast(*this, E, T, diag::warn_impcast_float_precision);
2009       }
2010       return;
2011     }
2012
2013     // If the target is integral, always warn.
2014     if ((TargetBT && TargetBT->isInteger()))
2015       // TODO: don't warn for integer values?
2016       return DiagnoseImpCast(*this, E, T, diag::warn_impcast_float_integer);
2017
2018     return;
2019   }
2020
2021   if (!Source->isIntegerType() || !Target->isIntegerType())
2022     return;
2023
2024   IntRange SourceRange = GetExprRange(Context, E, Context.getIntWidth(E->getType()));
2025   IntRange TargetRange = IntRange::forCanonicalType(Context, Target);
2026
2027   // FIXME: also signed<->unsigned?
2028
2029   if (SourceRange.Width > TargetRange.Width) {
2030     // People want to build with -Wshorten-64-to-32 and not -Wconversion
2031     // and by god we'll let them.
2032     if (SourceRange.Width == 64 && TargetRange.Width == 32)
2033       return DiagnoseImpCast(*this, E, T, diag::warn_impcast_integer_64_32);
2034     return DiagnoseImpCast(*this, E, T, diag::warn_impcast_integer_precision);
2035   }
2036
2037   return;
2038 }
2039
2040 // MarkLive - Mark all the blocks reachable from e as live.  Returns the total
2041 // number of blocks just marked live.
2042 static unsigned MarkLive(CFGBlock *e, llvm::BitVector &live) {
2043   unsigned count = 0;
2044   std::queue<CFGBlock*> workq;
2045   // Prep work queue
2046   live.set(e->getBlockID());
2047   ++count;
2048   workq.push(e);
2049   // Solve
2050   while (!workq.empty()) {
2051     CFGBlock *item = workq.front();
2052     workq.pop();
2053     for (CFGBlock::succ_iterator I=item->succ_begin(),
2054            E=item->succ_end();
2055          I != E;
2056          ++I) {
2057       if ((*I) && !live[(*I)->getBlockID()]) {
2058         live.set((*I)->getBlockID());
2059         ++count;
2060         workq.push(*I);
2061       }
2062     }
2063   }
2064   return count;
2065 }
2066
2067 static SourceLocation GetUnreachableLoc(CFGBlock &b, SourceRange &R1,
2068                                         SourceRange &R2) {
2069   Stmt *S;
2070   unsigned sn = 0;
2071   R1 = R2 = SourceRange();
2072
2073   top:
2074   if (sn < b.size())
2075     S = b[sn].getStmt();
2076   else if (b.getTerminator())
2077     S = b.getTerminator();
2078   else
2079     return SourceLocation();
2080
2081   switch (S->getStmtClass()) {
2082   case Expr::BinaryOperatorClass: {
2083     BinaryOperator *BO = cast<BinaryOperator>(S);
2084     if (BO->getOpcode() == BinaryOperator::Comma) {
2085       if (sn+1 < b.size())
2086         return b[sn+1].getStmt()->getLocStart();
2087       CFGBlock *n = &b;
2088       while (1) {
2089         if (n->getTerminator())
2090           return n->getTerminator()->getLocStart();
2091         if (n->succ_size() != 1)
2092           return SourceLocation();
2093         n = n[0].succ_begin()[0];
2094         if (n->pred_size() != 1)
2095           return SourceLocation();
2096         if (!n->empty())
2097           return n[0][0].getStmt()->getLocStart();
2098       }
2099     }
2100     R1 = BO->getLHS()->getSourceRange();
2101     R2 = BO->getRHS()->getSourceRange();
2102     return BO->getOperatorLoc();
2103   }
2104   case Expr::UnaryOperatorClass: {
2105     const UnaryOperator *UO = cast<UnaryOperator>(S);
2106     R1 = UO->getSubExpr()->getSourceRange();
2107     return UO->getOperatorLoc();
2108   }
2109   case Expr::CompoundAssignOperatorClass: {
2110     const CompoundAssignOperator *CAO = cast<CompoundAssignOperator>(S);
2111     R1 = CAO->getLHS()->getSourceRange();
2112     R2 = CAO->getRHS()->getSourceRange();
2113     return CAO->getOperatorLoc();
2114   }
2115   case Expr::ConditionalOperatorClass: {
2116     const ConditionalOperator *CO = cast<ConditionalOperator>(S);
2117     return CO->getQuestionLoc();
2118   }
2119   case Expr::MemberExprClass: {
2120     const MemberExpr *ME = cast<MemberExpr>(S);
2121     R1 = ME->getSourceRange();
2122     return ME->getMemberLoc();
2123   }
2124   case Expr::ArraySubscriptExprClass: {
2125     const ArraySubscriptExpr *ASE = cast<ArraySubscriptExpr>(S);
2126     R1 = ASE->getLHS()->getSourceRange();
2127     R2 = ASE->getRHS()->getSourceRange();
2128     return ASE->getRBracketLoc();
2129   }
2130   case Expr::CStyleCastExprClass: {
2131     const CStyleCastExpr *CSC = cast<CStyleCastExpr>(S);
2132     R1 = CSC->getSubExpr()->getSourceRange();
2133     return CSC->getLParenLoc();
2134   }
2135   case Expr::CXXFunctionalCastExprClass: {
2136     const CXXFunctionalCastExpr *CE = cast <CXXFunctionalCastExpr>(S);
2137     R1 = CE->getSubExpr()->getSourceRange();
2138     return CE->getTypeBeginLoc();
2139   }
2140   case Expr::ImplicitCastExprClass:
2141     ++sn;
2142     goto top;
2143   case Stmt::CXXTryStmtClass: {
2144     return cast<CXXTryStmt>(S)->getHandler(0)->getCatchLoc();
2145   }
2146   default: ;
2147   }
2148   R1 = S->getSourceRange();
2149   return S->getLocStart();
2150 }
2151
2152 static SourceLocation MarkLiveTop(CFGBlock *e, llvm::BitVector &live,
2153                                SourceManager &SM) {
2154   std::queue<CFGBlock*> workq;
2155   // Prep work queue
2156   workq.push(e);
2157   SourceRange R1, R2;
2158   SourceLocation top = GetUnreachableLoc(*e, R1, R2);
2159   bool FromMainFile = false;
2160   bool FromSystemHeader = false;
2161   bool TopValid = false;
2162   if (top.isValid()) {
2163     FromMainFile = SM.isFromMainFile(top);
2164     FromSystemHeader = SM.isInSystemHeader(top);
2165     TopValid = true;
2166   }
2167   // Solve
2168   while (!workq.empty()) {
2169     CFGBlock *item = workq.front();
2170     workq.pop();
2171     SourceLocation c = GetUnreachableLoc(*item, R1, R2);
2172     if (c.isValid()
2173         && (!TopValid
2174             || (SM.isFromMainFile(c) && !FromMainFile)
2175             || (FromSystemHeader && !SM.isInSystemHeader(c))
2176             || SM.isBeforeInTranslationUnit(c, top))) {
2177       top = c;
2178       FromMainFile = SM.isFromMainFile(top);
2179       FromSystemHeader = SM.isInSystemHeader(top);
2180     }
2181     live.set(item->getBlockID());
2182     for (CFGBlock::succ_iterator I=item->succ_begin(),
2183            E=item->succ_end();
2184          I != E;
2185          ++I) {
2186       if ((*I) && !live[(*I)->getBlockID()]) {
2187         live.set((*I)->getBlockID());
2188         workq.push(*I);
2189       }
2190     }
2191   }
2192   return top;
2193 }
2194
2195 static int LineCmp(const void *p1, const void *p2) {
2196   SourceLocation *Line1 = (SourceLocation *)p1;
2197   SourceLocation *Line2 = (SourceLocation *)p2;
2198   return !(*Line1 < *Line2);
2199 }
2200
2201 namespace {
2202   struct ErrLoc {
2203     SourceLocation Loc;
2204     SourceRange R1;
2205     SourceRange R2;
2206     ErrLoc(SourceLocation l, SourceRange r1, SourceRange r2)
2207       : Loc(l), R1(r1), R2(r2) { }
2208   };
2209 }
2210
2211 /// CheckUnreachable - Check for unreachable code.
2212 void Sema::CheckUnreachable(AnalysisContext &AC) {
2213   unsigned count;
2214   // We avoid checking when there are errors, as the CFG won't faithfully match
2215   // the user's code.
2216   if (getDiagnostics().hasErrorOccurred())
2217     return;
2218   if (Diags.getDiagnosticLevel(diag::warn_unreachable) == Diagnostic::Ignored)
2219     return;
2220
2221   CFG *cfg = AC.getCFG();
2222   if (cfg == 0)
2223     return;
2224
2225   llvm::BitVector live(cfg->getNumBlockIDs());
2226   // Mark all live things first.
2227   count = MarkLive(&cfg->getEntry(), live);
2228
2229   if (count == cfg->getNumBlockIDs())
2230     // If there are no dead blocks, we're done.
2231     return;
2232
2233   SourceRange R1, R2;
2234
2235   llvm::SmallVector<ErrLoc, 24> lines;
2236   bool AddEHEdges = AC.getAddEHEdges();
2237   // First, give warnings for blocks with no predecessors, as they
2238   // can't be part of a loop.
2239   for (CFG::iterator I = cfg->begin(), E = cfg->end(); I != E; ++I) {
2240     CFGBlock &b = **I;
2241     if (!live[b.getBlockID()]) {
2242       if (b.pred_begin() == b.pred_end()) {
2243         if (!AddEHEdges && b.getTerminator()
2244             && isa<CXXTryStmt>(b.getTerminator())) {
2245           // When not adding EH edges from calls, catch clauses
2246           // can otherwise seem dead.  Avoid noting them as dead.
2247           count += MarkLive(&b, live);
2248           continue;
2249         }
2250         SourceLocation c = GetUnreachableLoc(b, R1, R2);
2251         if (!c.isValid()) {
2252           // Blocks without a location can't produce a warning, so don't mark
2253           // reachable blocks from here as live.
2254           live.set(b.getBlockID());
2255           ++count;
2256           continue;
2257         }
2258         lines.push_back(ErrLoc(c, R1, R2));
2259         // Avoid excessive errors by marking everything reachable from here
2260         count += MarkLive(&b, live);
2261       }
2262     }
2263   }
2264
2265   if (count < cfg->getNumBlockIDs()) {
2266     // And then give warnings for the tops of loops.
2267     for (CFG::iterator I = cfg->begin(), E = cfg->end(); I != E; ++I) {
2268       CFGBlock &b = **I;
2269       if (!live[b.getBlockID()])
2270         // Avoid excessive errors by marking everything reachable from here
2271         lines.push_back(ErrLoc(MarkLiveTop(&b, live, Context.getSourceManager()), SourceRange(), SourceRange()));
2272     }
2273   }
2274
2275   llvm::array_pod_sort(lines.begin(), lines.end(), LineCmp);
2276   for (llvm::SmallVector<ErrLoc, 24>::iterator I = lines.begin(),
2277          E = lines.end();
2278        I != E;
2279        ++I)
2280     if (I->Loc.isValid())
2281       Diag(I->Loc, diag::warn_unreachable) << I->R1 << I->R2;
2282 }
2283
2284 /// CheckFallThrough - Check that we don't fall off the end of a
2285 /// Statement that should return a value.
2286 ///
2287 /// \returns AlwaysFallThrough iff we always fall off the end of the statement,
2288 /// MaybeFallThrough iff we might or might not fall off the end,
2289 /// NeverFallThroughOrReturn iff we never fall off the end of the statement or
2290 /// return.  We assume NeverFallThrough iff we never fall off the end of the
2291 /// statement but we may return.  We assume that functions not marked noreturn
2292 /// will return.
2293 Sema::ControlFlowKind Sema::CheckFallThrough(AnalysisContext &AC) {
2294   CFG *cfg = AC.getCFG();
2295   if (cfg == 0)
2296     // FIXME: This should be NeverFallThrough
2297     return NeverFallThroughOrReturn;
2298
2299   // The CFG leaves in dead things, and we don't want the dead code paths to
2300   // confuse us, so we mark all live things first.
2301   std::queue<CFGBlock*> workq;
2302   llvm::BitVector live(cfg->getNumBlockIDs());
2303   unsigned count = MarkLive(&cfg->getEntry(), live);
2304
2305   bool AddEHEdges = AC.getAddEHEdges();
2306   if (!AddEHEdges && count != cfg->getNumBlockIDs())
2307     // When there are things remaining dead, and we didn't add EH edges
2308     // from CallExprs to the catch clauses, we have to go back and
2309     // mark them as live.
2310     for (CFG::iterator I = cfg->begin(), E = cfg->end(); I != E; ++I) {
2311       CFGBlock &b = **I;
2312       if (!live[b.getBlockID()]) {
2313         if (b.pred_begin() == b.pred_end()) {
2314           if (b.getTerminator() && isa<CXXTryStmt>(b.getTerminator()))
2315             // When not adding EH edges from calls, catch clauses
2316             // can otherwise seem dead.  Avoid noting them as dead.
2317             count += MarkLive(&b, live);
2318           continue;
2319         }
2320       }
2321     }
2322
2323   // Now we know what is live, we check the live precessors of the exit block
2324   // and look for fall through paths, being careful to ignore normal returns,
2325   // and exceptional paths.
2326   bool HasLiveReturn = false;
2327   bool HasFakeEdge = false;
2328   bool HasPlainEdge = false;
2329   bool HasAbnormalEdge = false;
2330   for (CFGBlock::pred_iterator I=cfg->getExit().pred_begin(),
2331          E = cfg->getExit().pred_end();
2332        I != E;
2333        ++I) {
2334     CFGBlock& B = **I;
2335     if (!live[B.getBlockID()])
2336       continue;
2337     if (B.size() == 0) {
2338       if (B.getTerminator() && isa<CXXTryStmt>(B.getTerminator())) {
2339         HasAbnormalEdge = true;
2340         continue;
2341       }
2342
2343       // A labeled empty statement, or the entry block...
2344       HasPlainEdge = true;
2345       continue;
2346     }
2347     Stmt *S = B[B.size()-1];
2348     if (isa<ReturnStmt>(S)) {
2349       HasLiveReturn = true;
2350       continue;
2351     }
2352     if (isa<ObjCAtThrowStmt>(S)) {
2353       HasFakeEdge = true;
2354       continue;
2355     }
2356     if (isa<CXXThrowExpr>(S)) {
2357       HasFakeEdge = true;
2358       continue;
2359     }
2360     if (const AsmStmt *AS = dyn_cast<AsmStmt>(S)) {
2361       if (AS->isMSAsm()) {
2362         HasFakeEdge = true;
2363         HasLiveReturn = true;
2364         continue;
2365       }
2366     }
2367     if (isa<CXXTryStmt>(S)) {
2368       HasAbnormalEdge = true;
2369       continue;
2370     }
2371
2372     bool NoReturnEdge = false;
2373     if (CallExpr *C = dyn_cast<CallExpr>(S)) {
2374       if (B.succ_begin()[0] != &cfg->getExit()) {
2375         HasAbnormalEdge = true;
2376         continue;
2377       }
2378       Expr *CEE = C->getCallee()->IgnoreParenCasts();
2379       if (CEE->getType().getNoReturnAttr()) {
2380         NoReturnEdge = true;
2381         HasFakeEdge = true;
2382       } else if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(CEE)) {
2383         ValueDecl *VD = DRE->getDecl();
2384         if (VD->hasAttr<NoReturnAttr>()) {
2385           NoReturnEdge = true;
2386           HasFakeEdge = true;
2387         }
2388       }
2389     }
2390     // FIXME: Add noreturn message sends.
2391     if (NoReturnEdge == false)
2392       HasPlainEdge = true;
2393   }
2394   if (!HasPlainEdge) {
2395     if (HasLiveReturn)
2396       return NeverFallThrough;
2397     return NeverFallThroughOrReturn;
2398   }
2399   if (HasAbnormalEdge || HasFakeEdge || HasLiveReturn)
2400     return MaybeFallThrough;
2401   // This says AlwaysFallThrough for calls to functions that are not marked
2402   // noreturn, that don't return.  If people would like this warning to be more
2403   // accurate, such functions should be marked as noreturn.
2404   return AlwaysFallThrough;
2405 }
2406
2407 /// CheckFallThroughForFunctionDef - Check that we don't fall off the end of a
2408 /// function that should return a value.  Check that we don't fall off the end
2409 /// of a noreturn function.  We assume that functions and blocks not marked
2410 /// noreturn will return.
2411 void Sema::CheckFallThroughForFunctionDef(Decl *D, Stmt *Body,
2412                                           AnalysisContext &AC) {
2413   // FIXME: Would be nice if we had a better way to control cascading errors,
2414   // but for now, avoid them.  The problem is that when Parse sees:
2415   //   int foo() { return a; }
2416   // The return is eaten and the Sema code sees just:
2417   //   int foo() { }
2418   // which this code would then warn about.
2419   if (getDiagnostics().hasErrorOccurred())
2420     return;
2421
2422   bool ReturnsVoid = false;
2423   bool HasNoReturn = false;
2424   if (FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
2425     // If the result type of the function is a dependent type, we don't know
2426     // whether it will be void or not, so don't
2427     if (FD->getResultType()->isDependentType())
2428       return;
2429     if (FD->getResultType()->isVoidType())
2430       ReturnsVoid = true;
2431     if (FD->hasAttr<NoReturnAttr>())
2432       HasNoReturn = true;
2433   } else if (ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D)) {
2434     if (MD->getResultType()->isVoidType())
2435       ReturnsVoid = true;
2436     if (MD->hasAttr<NoReturnAttr>())
2437       HasNoReturn = true;
2438   }
2439
2440   // Short circuit for compilation speed.
2441   if ((Diags.getDiagnosticLevel(diag::warn_maybe_falloff_nonvoid_function)
2442        == Diagnostic::Ignored || ReturnsVoid)
2443       && (Diags.getDiagnosticLevel(diag::warn_noreturn_function_has_return_expr)
2444           == Diagnostic::Ignored || !HasNoReturn)
2445       && (Diags.getDiagnosticLevel(diag::warn_suggest_noreturn_block)
2446           == Diagnostic::Ignored || !ReturnsVoid))
2447     return;
2448   // FIXME: Function try block
2449   if (CompoundStmt *Compound = dyn_cast<CompoundStmt>(Body)) {
2450     switch (CheckFallThrough(AC)) {
2451     case MaybeFallThrough:
2452       if (HasNoReturn)
2453         Diag(Compound->getRBracLoc(), diag::warn_falloff_noreturn_function);
2454       else if (!ReturnsVoid)
2455         Diag(Compound->getRBracLoc(),diag::warn_maybe_falloff_nonvoid_function);
2456       break;
2457     case AlwaysFallThrough:
2458       if (HasNoReturn)
2459         Diag(Compound->getRBracLoc(), diag::warn_falloff_noreturn_function);
2460       else if (!ReturnsVoid)
2461         Diag(Compound->getRBracLoc(), diag::warn_falloff_nonvoid_function);
2462       break;
2463     case NeverFallThroughOrReturn:
2464       if (ReturnsVoid && !HasNoReturn)
2465         Diag(Compound->getLBracLoc(), diag::warn_suggest_noreturn_function);
2466       break;
2467     case NeverFallThrough:
2468       break;
2469     }
2470   }
2471 }
2472
2473 /// CheckFallThroughForBlock - Check that we don't fall off the end of a block
2474 /// that should return a value.  Check that we don't fall off the end of a
2475 /// noreturn block.  We assume that functions and blocks not marked noreturn
2476 /// will return.
2477 void Sema::CheckFallThroughForBlock(QualType BlockTy, Stmt *Body,
2478                                     AnalysisContext &AC) {
2479   // FIXME: Would be nice if we had a better way to control cascading errors,
2480   // but for now, avoid them.  The problem is that when Parse sees:
2481   //   int foo() { return a; }
2482   // The return is eaten and the Sema code sees just:
2483   //   int foo() { }
2484   // which this code would then warn about.
2485   if (getDiagnostics().hasErrorOccurred())
2486     return;
2487   bool ReturnsVoid = false;
2488   bool HasNoReturn = false;
2489   if (const FunctionType *FT =BlockTy->getPointeeType()->getAs<FunctionType>()){
2490     if (FT->getResultType()->isVoidType())
2491       ReturnsVoid = true;
2492     if (FT->getNoReturnAttr())
2493       HasNoReturn = true;
2494   }
2495
2496   // Short circuit for compilation speed.
2497   if (ReturnsVoid
2498       && !HasNoReturn
2499       && (Diags.getDiagnosticLevel(diag::warn_suggest_noreturn_block)
2500           == Diagnostic::Ignored || !ReturnsVoid))
2501     return;
2502   // FIXME: Funtion try block
2503   if (CompoundStmt *Compound = dyn_cast<CompoundStmt>(Body)) {
2504     switch (CheckFallThrough(AC)) {
2505     case MaybeFallThrough:
2506       if (HasNoReturn)
2507         Diag(Compound->getRBracLoc(), diag::err_noreturn_block_has_return_expr);
2508       else if (!ReturnsVoid)
2509         Diag(Compound->getRBracLoc(), diag::err_maybe_falloff_nonvoid_block);
2510       break;
2511     case AlwaysFallThrough:
2512       if (HasNoReturn)
2513         Diag(Compound->getRBracLoc(), diag::err_noreturn_block_has_return_expr);
2514       else if (!ReturnsVoid)
2515         Diag(Compound->getRBracLoc(), diag::err_falloff_nonvoid_block);
2516       break;
2517     case NeverFallThroughOrReturn:
2518       if (ReturnsVoid)
2519         Diag(Compound->getLBracLoc(), diag::warn_suggest_noreturn_block);
2520       break;
2521     case NeverFallThrough:
2522       break;
2523     }
2524   }
2525 }
2526
2527 /// CheckParmsForFunctionDef - Check that the parameters of the given
2528 /// function are appropriate for the definition of a function. This
2529 /// takes care of any checks that cannot be performed on the
2530 /// declaration itself, e.g., that the types of each of the function
2531 /// parameters are complete.
2532 bool Sema::CheckParmsForFunctionDef(FunctionDecl *FD) {
2533   bool HasInvalidParm = false;
2534   for (unsigned p = 0, NumParams = FD->getNumParams(); p < NumParams; ++p) {
2535     ParmVarDecl *Param = FD->getParamDecl(p);
2536
2537     // C99 6.7.5.3p4: the parameters in a parameter type list in a
2538     // function declarator that is part of a function definition of
2539     // that function shall not have incomplete type.
2540     //
2541     // This is also C++ [dcl.fct]p6.
2542     if (!Param->isInvalidDecl() &&
2543         RequireCompleteType(Param->getLocation(), Param->getType(),
2544                                diag::err_typecheck_decl_incomplete_type)) {
2545       Param->setInvalidDecl();
2546       HasInvalidParm = true;
2547     }
2548
2549     // C99 6.9.1p5: If the declarator includes a parameter type list, the
2550     // declaration of each parameter shall include an identifier.
2551     if (Param->getIdentifier() == 0 &&
2552         !Param->isImplicit() &&
2553         !getLangOptions().CPlusPlus)
2554       Diag(Param->getLocation(), diag::err_parameter_name_omitted);
2555   }
2556
2557   return HasInvalidParm;
2558 }