contrib/llvm/tools/clang/lib/AST/ExprConstant.cpp

   1 //===--- ExprConstant.cpp - Expression Constant Evaluator -----------------===//
   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 the Expr constant evaluator.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "clang/AST/APValue.h"
  15 #include "clang/AST/ASTContext.h"
  16 #include "clang/AST/CharUnits.h"
  17 #include "clang/AST/RecordLayout.h"
  18 #include "clang/AST/StmtVisitor.h"
  19 #include "clang/AST/TypeLoc.h"
  20 #include "clang/AST/ASTDiagnostic.h"
  21 #include "clang/AST/Expr.h"
  22 #include "clang/Basic/Builtins.h"
  23 #include "clang/Basic/TargetInfo.h"
  24 #include "llvm/ADT/SmallString.h"
  25 #include <cstring>
  26
  27 using namespace clang;
  28 using llvm::APSInt;
  29 using llvm::APFloat;
  30
  31 /// EvalInfo - This is a private struct used by the evaluator to capture
  32 /// information about a subexpression as it is folded.  It retains information
  33 /// about the AST context, but also maintains information about the folded
  34 /// expression.
  35 ///
  36 /// If an expression could be evaluated, it is still possible it is not a C
  37 /// "integer constant expression" or constant expression.  If not, this struct
  38 /// captures information about how and why not.
  39 ///
  40 /// One bit of information passed *into* the request for constant folding
  41 /// indicates whether the subexpression is "evaluated" or not according to C
  42 /// rules.  For example, the RHS of (0 && foo()) is not evaluated.  We can
  43 /// evaluate the expression regardless of what the RHS is, but C only allows
  44 /// certain things in certain situations.
  45 namespace {
  46   struct EvalInfo {
  47     const ASTContext &Ctx;
  48
  49     /// EvalResult - Contains information about the evaluation.
  50     Expr::EvalResult &EvalResult;
  51
  52     typedef llvm::DenseMap<const OpaqueValueExpr*, APValue> MapTy;
  53     MapTy OpaqueValues;
  54     const APValue *getOpaqueValue(const OpaqueValueExpr *e) const {
  55       MapTy::const_iterator i = OpaqueValues.find(e);
  56       if (i == OpaqueValues.end()) return 0;
  57       return &i->second;
  58     }
  59
  60     EvalInfo(const ASTContext &ctx, Expr::EvalResult &evalresult)
  61       : Ctx(ctx), EvalResult(evalresult) {}
  62   };
  63
  64   struct ComplexValue {
  65   private:
  66     bool IsInt;
  67
  68   public:
  69     APSInt IntReal, IntImag;
  70     APFloat FloatReal, FloatImag;
  71
  72     ComplexValue() : FloatReal(APFloat::Bogus), FloatImag(APFloat::Bogus) {}
  73
  74     void makeComplexFloat() { IsInt = false; }
  75     bool isComplexFloat() const { return !IsInt; }
  76     APFloat &getComplexFloatReal() { return FloatReal; }
  77     APFloat &getComplexFloatImag() { return FloatImag; }
  78
  79     void makeComplexInt() { IsInt = true; }
  80     bool isComplexInt() const { return IsInt; }
  81     APSInt &getComplexIntReal() { return IntReal; }
  82     APSInt &getComplexIntImag() { return IntImag; }
  83
  84     void moveInto(APValue &v) const {
  85       if (isComplexFloat())
  86         v = APValue(FloatReal, FloatImag);
  87       else
  88         v = APValue(IntReal, IntImag);
  89     }
  90     void setFrom(const APValue &v) {
  91       assert(v.isComplexFloat() || v.isComplexInt());
  92       if (v.isComplexFloat()) {
  93         makeComplexFloat();
  94         FloatReal = v.getComplexFloatReal();
  95         FloatImag = v.getComplexFloatImag();
  96       } else {
  97         makeComplexInt();
  98         IntReal = v.getComplexIntReal();
  99         IntImag = v.getComplexIntImag();
 100       }
 101     }
 102   };
 103
 104   struct LValue {
 105     const Expr *Base;
 106     CharUnits Offset;
 107
 108     const Expr *getLValueBase() { return Base; }
 109     CharUnits getLValueOffset() { return Offset; }
 110
 111     void moveInto(APValue &v) const {
 112       v = APValue(Base, Offset);
 113     }
 114     void setFrom(const APValue &v) {
 115       assert(v.isLValue());
 116       Base = v.getLValueBase();
 117       Offset = v.getLValueOffset();
 118     }
 119   };
 120 }
 121
 122 static bool Evaluate(EvalInfo &info, const Expr *E);
 123 static bool EvaluateLValue(const Expr *E, LValue &Result, EvalInfo &Info);
 124 static bool EvaluatePointer(const Expr *E, LValue &Result, EvalInfo &Info);
 125 static bool EvaluateInteger(const Expr *E, APSInt  &Result, EvalInfo &Info);
 126 static bool EvaluateIntegerOrLValue(const Expr *E, APValue  &Result,
 127                                     EvalInfo &Info);
 128 static bool EvaluateFloat(const Expr *E, APFloat &Result, EvalInfo &Info);
 129 static bool EvaluateComplex(const Expr *E, ComplexValue &Res, EvalInfo &Info);
 130
 131 //===----------------------------------------------------------------------===//
 132 // Misc utilities
 133 //===----------------------------------------------------------------------===//
 134
 135 static bool IsGlobalLValue(const Expr* E) {
 136   if (!E) return true;
 137
 138   if (const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E)) {
 139     if (isa<FunctionDecl>(DRE->getDecl()))
 140       return true;
 141     if (const VarDecl *VD = dyn_cast<VarDecl>(DRE->getDecl()))
 142       return VD->hasGlobalStorage();
 143     return false;
 144   }
 145
 146   if (const CompoundLiteralExpr *CLE = dyn_cast<CompoundLiteralExpr>(E))
 147     return CLE->isFileScope();
 148
 149   return true;
 150 }
 151
 152 static bool EvalPointerValueAsBool(LValue& Value, bool& Result) {
 153   const Expr* Base = Value.Base;
 154
 155   // A null base expression indicates a null pointer.  These are always
 156   // evaluatable, and they are false unless the offset is zero.
 157   if (!Base) {
 158     Result = !Value.Offset.isZero();
 159     return true;
 160   }
 161
 162   // Require the base expression to be a global l-value.
 163   if (!IsGlobalLValue(Base)) return false;
 164
 165   // We have a non-null base expression.  These are generally known to
 166   // be true, but if it'a decl-ref to a weak symbol it can be null at
 167   // runtime.
 168   Result = true;
 169
 170   const DeclRefExpr* DeclRef = dyn_cast<DeclRefExpr>(Base);
 171   if (!DeclRef)
 172     return true;
 173
 174   // If it's a weak symbol, it isn't constant-evaluable.
 175   const ValueDecl* Decl = DeclRef->getDecl();
 176   if (Decl->hasAttr<WeakAttr>() ||
 177       Decl->hasAttr<WeakRefAttr>() ||
 178       Decl->isWeakImported())
 179     return false;
 180
 181   return true;
 182 }
 183
 184 static bool HandleConversionToBool(const Expr* E, bool& Result,
 185                                    EvalInfo &Info) {
 186   if (E->getType()->isIntegralOrEnumerationType()) {
 187     APSInt IntResult;
 188     if (!EvaluateInteger(E, IntResult, Info))
 189       return false;
 190     Result = IntResult != 0;
 191     return true;
 192   } else if (E->getType()->isRealFloatingType()) {
 193     APFloat FloatResult(0.0);
 194     if (!EvaluateFloat(E, FloatResult, Info))
 195       return false;
 196     Result = !FloatResult.isZero();
 197     return true;
 198   } else if (E->getType()->hasPointerRepresentation()) {
 199     LValue PointerResult;
 200     if (!EvaluatePointer(E, PointerResult, Info))
 201       return false;
 202     return EvalPointerValueAsBool(PointerResult, Result);
 203   } else if (E->getType()->isAnyComplexType()) {
 204     ComplexValue ComplexResult;
 205     if (!EvaluateComplex(E, ComplexResult, Info))
 206       return false;
 207     if (ComplexResult.isComplexFloat()) {
 208       Result = !ComplexResult.getComplexFloatReal().isZero() ||
 209                !ComplexResult.getComplexFloatImag().isZero();
 210     } else {
 211       Result = ComplexResult.getComplexIntReal().getBoolValue() ||
 212                ComplexResult.getComplexIntImag().getBoolValue();
 213     }
 214     return true;
 215   }
 216
 217   return false;
 218 }
 219
 220 static APSInt HandleFloatToIntCast(QualType DestType, QualType SrcType,
 221                                    APFloat &Value, const ASTContext &Ctx) {
 222   unsigned DestWidth = Ctx.getIntWidth(DestType);
 223   // Determine whether we are converting to unsigned or signed.
 224   bool DestSigned = DestType->isSignedIntegerOrEnumerationType();
 225
 226   // FIXME: Warning for overflow.
 227   APSInt Result(DestWidth, !DestSigned);
 228   bool ignored;
 229   (void)Value.convertToInteger(Result, llvm::APFloat::rmTowardZero, &ignored);
 230   return Result;
 231 }
 232
 233 static APFloat HandleFloatToFloatCast(QualType DestType, QualType SrcType,
 234                                       APFloat &Value, const ASTContext &Ctx) {
 235   bool ignored;
 236   APFloat Result = Value;
 237   Result.convert(Ctx.getFloatTypeSemantics(DestType),
 238                  APFloat::rmNearestTiesToEven, &ignored);
 239   return Result;
 240 }
 241
 242 static APSInt HandleIntToIntCast(QualType DestType, QualType SrcType,
 243                                  APSInt &Value, const ASTContext &Ctx) {
 244   unsigned DestWidth = Ctx.getIntWidth(DestType);
 245   APSInt Result = Value;
 246   // Figure out if this is a truncate, extend or noop cast.
 247   // If the input is signed, do a sign extend, noop, or truncate.
 248   Result = Result.extOrTrunc(DestWidth);
 249   Result.setIsUnsigned(DestType->isUnsignedIntegerOrEnumerationType());
 250   return Result;
 251 }
 252
 253 static APFloat HandleIntToFloatCast(QualType DestType, QualType SrcType,
 254                                     APSInt &Value, const ASTContext &Ctx) {
 255
 256   APFloat Result(Ctx.getFloatTypeSemantics(DestType), 1);
 257   Result.convertFromAPInt(Value, Value.isSigned(),
 258                           APFloat::rmNearestTiesToEven);
 259   return Result;
 260 }
 261
 262 namespace {
 263 class HasSideEffect
 264   : public ConstStmtVisitor<HasSideEffect, bool> {
 265   EvalInfo &Info;
 266 public:
 267
 268   HasSideEffect(EvalInfo &info) : Info(info) {}
 269
 270   // Unhandled nodes conservatively default to having side effects.
 271   bool VisitStmt(const Stmt *S) {
 272     return true;
 273   }
 274
 275   bool VisitParenExpr(const ParenExpr *E) { return Visit(E->getSubExpr()); }
 276   bool VisitGenericSelectionExpr(const GenericSelectionExpr *E) {
 277     return Visit(E->getResultExpr());
 278   }
 279   bool VisitDeclRefExpr(const DeclRefExpr *E) {
 280     if (Info.Ctx.getCanonicalType(E->getType()).isVolatileQualified())
 281       return true;
 282     return false;
 283   }
 284   bool VisitObjCIvarRefExpr(const ObjCIvarRefExpr *E) {
 285     if (Info.Ctx.getCanonicalType(E->getType()).isVolatileQualified())
 286       return true;
 287     return false;
 288   }
 289   bool VisitBlockDeclRefExpr (const BlockDeclRefExpr *E) {
 290     if (Info.Ctx.getCanonicalType(E->getType()).isVolatileQualified())
 291       return true;
 292     return false;
 293   }
 294
 295   // We don't want to evaluate BlockExprs multiple times, as they generate
 296   // a ton of code.
 297   bool VisitBlockExpr(const BlockExpr *E) { return true; }
 298   bool VisitPredefinedExpr(const PredefinedExpr *E) { return false; }
 299   bool VisitCompoundLiteralExpr(const CompoundLiteralExpr *E)
 300     { return Visit(E->getInitializer()); }
 301   bool VisitMemberExpr(const MemberExpr *E) { return Visit(E->getBase()); }
 302   bool VisitIntegerLiteral(const IntegerLiteral *E) { return false; }
 303   bool VisitFloatingLiteral(const FloatingLiteral *E) { return false; }
 304   bool VisitStringLiteral(const StringLiteral *E) { return false; }
 305   bool VisitCharacterLiteral(const CharacterLiteral *E) { return false; }
 306   bool VisitUnaryExprOrTypeTraitExpr(const UnaryExprOrTypeTraitExpr *E)
 307     { return false; }
 308   bool VisitArraySubscriptExpr(const ArraySubscriptExpr *E)
 309     { return Visit(E->getLHS()) || Visit(E->getRHS()); }
 310   bool VisitChooseExpr(const ChooseExpr *E)
 311     { return Visit(E->getChosenSubExpr(Info.Ctx)); }
 312   bool VisitCastExpr(const CastExpr *E) { return Visit(E->getSubExpr()); }
 313   bool VisitBinAssign(const BinaryOperator *E) { return true; }
 314   bool VisitCompoundAssignOperator(const BinaryOperator *E) { return true; }
 315   bool VisitBinaryOperator(const BinaryOperator *E)
 316   { return Visit(E->getLHS()) || Visit(E->getRHS()); }
 317   bool VisitUnaryPreInc(const UnaryOperator *E) { return true; }
 318   bool VisitUnaryPostInc(const UnaryOperator *E) { return true; }
 319   bool VisitUnaryPreDec(const UnaryOperator *E) { return true; }
 320   bool VisitUnaryPostDec(const UnaryOperator *E) { return true; }
 321   bool VisitUnaryDeref(const UnaryOperator *E) {
 322     if (Info.Ctx.getCanonicalType(E->getType()).isVolatileQualified())
 323       return true;
 324     return Visit(E->getSubExpr());
 325   }
 326   bool VisitUnaryOperator(const UnaryOperator *E) { return Visit(E->getSubExpr()); }
 327
 328   // Has side effects if any element does.
 329   bool VisitInitListExpr(const InitListExpr *E) {
 330     for (unsigned i = 0, e = E->getNumInits(); i != e; ++i)
 331       if (Visit(E->getInit(i))) return true;
 332     if (const Expr *filler = E->getArrayFiller())
 333       return Visit(filler);
 334     return false;
 335   }
 336
 337   bool VisitSizeOfPackExpr(const SizeOfPackExpr *) { return false; }
 338 };
 339
 340 class OpaqueValueEvaluation {
 341   EvalInfo &info;
 342   OpaqueValueExpr *opaqueValue;
 343
 344 public:
 345   OpaqueValueEvaluation(EvalInfo &info, OpaqueValueExpr *opaqueValue,
 346                         Expr *value)
 347     : info(info), opaqueValue(opaqueValue) {
 348
 349     // If evaluation fails, fail immediately.
 350     if (!Evaluate(info, value)) {
 351       this->opaqueValue = 0;
 352       return;
 353     }
 354     info.OpaqueValues[opaqueValue] = info.EvalResult.Val;
 355   }
 356
 357   bool hasError() const { return opaqueValue == 0; }
 358
 359   ~OpaqueValueEvaluation() {
 360     if (opaqueValue) info.OpaqueValues.erase(opaqueValue);
 361   }
 362 };
 363
 364 } // end anonymous namespace
 365
 366 //===----------------------------------------------------------------------===//
 367 // Generic Evaluation
 368 //===----------------------------------------------------------------------===//
 369 namespace {
 370
 371 template <class Derived, typename RetTy=void>
 372 class ExprEvaluatorBase
 373   : public ConstStmtVisitor<Derived, RetTy> {
 374 private:
 375   RetTy DerivedSuccess(const APValue &V, const Expr *E) {
 376     return static_cast<Derived*>(this)->Success(V, E);
 377   }
 378   RetTy DerivedError(const Expr *E) {
 379     return static_cast<Derived*>(this)->Error(E);
 380   }
 381
 382 protected:
 383   EvalInfo &Info;
 384   typedef ConstStmtVisitor<Derived, RetTy> StmtVisitorTy;
 385   typedef ExprEvaluatorBase ExprEvaluatorBaseTy;
 386
 387 public:
 388   ExprEvaluatorBase(EvalInfo &Info) : Info(Info) {}
 389
 390   RetTy VisitStmt(const Stmt *) {
 391     assert(0 && "Expression evaluator should not be called on stmts");
 392     return DerivedError(0);
 393   }
 394   RetTy VisitExpr(const Expr *E) {
 395     return DerivedError(E);
 396   }
 397
 398   RetTy VisitParenExpr(const ParenExpr *E)
 399     { return StmtVisitorTy::Visit(E->getSubExpr()); }
 400   RetTy VisitUnaryExtension(const UnaryOperator *E)
 401     { return StmtVisitorTy::Visit(E->getSubExpr()); }
 402   RetTy VisitUnaryPlus(const UnaryOperator *E)
 403     { return StmtVisitorTy::Visit(E->getSubExpr()); }
 404   RetTy VisitChooseExpr(const ChooseExpr *E)
 405     { return StmtVisitorTy::Visit(E->getChosenSubExpr(Info.Ctx)); }
 406   RetTy VisitGenericSelectionExpr(const GenericSelectionExpr *E)
 407     { return StmtVisitorTy::Visit(E->getResultExpr()); }
 408   RetTy VisitSubstNonTypeTemplateParmExpr(const SubstNonTypeTemplateParmExpr *E)
 409     { return StmtVisitorTy::Visit(E->getReplacement()); }
 410
 411   RetTy VisitBinaryConditionalOperator(const BinaryConditionalOperator *E) {
 412     OpaqueValueEvaluation opaque(Info, E->getOpaqueValue(), E->getCommon());
 413     if (opaque.hasError())
 414       return DerivedError(E);
 415
 416     bool cond;
 417     if (!HandleConversionToBool(E->getCond(), cond, Info))
 418       return DerivedError(E);
 419
 420     return StmtVisitorTy::Visit(cond ? E->getTrueExpr() : E->getFalseExpr());
 421   }
 422
 423   RetTy VisitConditionalOperator(const ConditionalOperator *E) {
 424     bool BoolResult;
 425     if (!HandleConversionToBool(E->getCond(), BoolResult, Info))
 426       return DerivedError(E);
 427
 428     Expr* EvalExpr = BoolResult ? E->getTrueExpr() : E->getFalseExpr();
 429     return StmtVisitorTy::Visit(EvalExpr);
 430   }
 431
 432   RetTy VisitOpaqueValueExpr(const OpaqueValueExpr *E) {
 433     const APValue *value = Info.getOpaqueValue(E);
 434     if (!value)
 435       return (E->getSourceExpr() ? StmtVisitorTy::Visit(E->getSourceExpr())
 436                                  : DerivedError(E));
 437     return DerivedSuccess(*value, E);
 438   }
 439 };
 440
 441 }
 442
 443 //===----------------------------------------------------------------------===//
 444 // LValue Evaluation
 445 //===----------------------------------------------------------------------===//
 446 namespace {
 447 class LValueExprEvaluator
 448   : public ExprEvaluatorBase<LValueExprEvaluator, bool> {
 449   LValue &Result;
 450
 451   bool Success(const Expr *E) {
 452     Result.Base = E;
 453     Result.Offset = CharUnits::Zero();
 454     return true;
 455   }
 456 public:
 457
 458   LValueExprEvaluator(EvalInfo &info, LValue &Result) :
 459     ExprEvaluatorBaseTy(info), Result(Result) {}
 460
 461   bool Success(const APValue &V, const Expr *E) {
 462     Result.setFrom(V);
 463     return true;
 464   }
 465   bool Error(const Expr *E) {
 466     return false;
 467   }
 468
 469   bool VisitDeclRefExpr(const DeclRefExpr *E);
 470   bool VisitPredefinedExpr(const PredefinedExpr *E) { return Success(E); }
 471   bool VisitCompoundLiteralExpr(const CompoundLiteralExpr *E);
 472   bool VisitMemberExpr(const MemberExpr *E);
 473   bool VisitStringLiteral(const StringLiteral *E) { return Success(E); }
 474   bool VisitObjCEncodeExpr(const ObjCEncodeExpr *E) { return Success(E); }
 475   bool VisitArraySubscriptExpr(const ArraySubscriptExpr *E);
 476   bool VisitUnaryDeref(const UnaryOperator *E);
 477
 478   bool VisitCastExpr(const CastExpr *E) {
 479     switch (E->getCastKind()) {
 480     default:
 481       return false;
 482
 483     case CK_NoOp:
 484       return Visit(E->getSubExpr());
 485     }
 486   }
 487   // FIXME: Missing: __real__, __imag__
 488
 489 };
 490 } // end anonymous namespace
 491
 492 static bool EvaluateLValue(const Expr* E, LValue& Result, EvalInfo &Info) {
 493   return LValueExprEvaluator(Info, Result).Visit(E);
 494 }
 495
 496 bool LValueExprEvaluator::VisitDeclRefExpr(const DeclRefExpr *E) {
 497   if (isa<FunctionDecl>(E->getDecl())) {
 498     return Success(E);
 499   } else if (const VarDecl* VD = dyn_cast<VarDecl>(E->getDecl())) {
 500     if (!VD->getType()->isReferenceType())
 501       return Success(E);
 502     // Reference parameters can refer to anything even if they have an
 503     // "initializer" in the form of a default argument.
 504     if (!isa<ParmVarDecl>(VD))
 505       // FIXME: Check whether VD might be overridden!
 506       if (const Expr *Init = VD->getAnyInitializer())
 507         return Visit(Init);
 508   }
 509
 510   return ExprEvaluatorBaseTy::VisitDeclRefExpr(E);
 511 }
 512
 513 bool
 514 LValueExprEvaluator::VisitCompoundLiteralExpr(const CompoundLiteralExpr *E) {
 515   return Success(E);
 516 }
 517
 518 bool LValueExprEvaluator::VisitMemberExpr(const MemberExpr *E) {
 519   QualType Ty;
 520   if (E->isArrow()) {
 521     if (!EvaluatePointer(E->getBase(), Result, Info))
 522       return false;
 523     Ty = E->getBase()->getType()->getAs<PointerType>()->getPointeeType();
 524   } else {
 525     if (!Visit(E->getBase()))
 526       return false;
 527     Ty = E->getBase()->getType();
 528   }
 529
 530   const RecordDecl *RD = Ty->getAs<RecordType>()->getDecl();
 531   const ASTRecordLayout &RL = Info.Ctx.getASTRecordLayout(RD);
 532
 533   const FieldDecl *FD = dyn_cast<FieldDecl>(E->getMemberDecl());
 534   if (!FD) // FIXME: deal with other kinds of member expressions
 535     return false;
 536
 537   if (FD->getType()->isReferenceType())
 538     return false;
 539
 540   unsigned i = FD->getFieldIndex();
 541   Result.Offset += Info.Ctx.toCharUnitsFromBits(RL.getFieldOffset(i));
 542   return true;
 543 }
 544
 545 bool LValueExprEvaluator::VisitArraySubscriptExpr(const ArraySubscriptExpr *E) {
 546   if (!EvaluatePointer(E->getBase(), Result, Info))
 547     return false;
 548
 549   APSInt Index;
 550   if (!EvaluateInteger(E->getIdx(), Index, Info))
 551     return false;
 552
 553   CharUnits ElementSize = Info.Ctx.getTypeSizeInChars(E->getType());
 554   Result.Offset += Index.getSExtValue() * ElementSize;
 555   return true;
 556 }
 557
 558 bool LValueExprEvaluator::VisitUnaryDeref(const UnaryOperator *E) {
 559   return EvaluatePointer(E->getSubExpr(), Result, Info);
 560 }
 561
 562 //===----------------------------------------------------------------------===//
 563 // Pointer Evaluation
 564 //===----------------------------------------------------------------------===//
 565
 566 namespace {
 567 class PointerExprEvaluator
 568   : public ExprEvaluatorBase<PointerExprEvaluator, bool> {
 569   LValue &Result;
 570
 571   bool Success(const Expr *E) {
 572     Result.Base = E;
 573     Result.Offset = CharUnits::Zero();
 574     return true;
 575   }
 576 public:
 577
 578   PointerExprEvaluator(EvalInfo &info, LValue &Result)
 579     : ExprEvaluatorBaseTy(info), Result(Result) {}
 580
 581   bool Success(const APValue &V, const Expr *E) {
 582     Result.setFrom(V);
 583     return true;
 584   }
 585   bool Error(const Stmt *S) {
 586     return false;
 587   }
 588
 589   bool VisitBinaryOperator(const BinaryOperator *E);
 590   bool VisitCastExpr(const CastExpr* E);
 591   bool VisitUnaryAddrOf(const UnaryOperator *E);
 592   bool VisitObjCStringLiteral(const ObjCStringLiteral *E)
 593       { return Success(E); }
 594   bool VisitAddrLabelExpr(const AddrLabelExpr *E)
 595       { return Success(E); }
 596   bool VisitCallExpr(const CallExpr *E);
 597   bool VisitBlockExpr(const BlockExpr *E) {
 598     if (!E->getBlockDecl()->hasCaptures())
 599       return Success(E);
 600     return false;
 601   }
 602   bool VisitImplicitValueInitExpr(const ImplicitValueInitExpr *E)
 603       { return Success((Expr*)0); }
 604   bool VisitCXXNullPtrLiteralExpr(const CXXNullPtrLiteralExpr *E)
 605       { return Success((Expr*)0); }
 606
 607   // FIXME: Missing: @protocol, @selector
 608 };
 609 } // end anonymous namespace
 610
 611 static bool EvaluatePointer(const Expr* E, LValue& Result, EvalInfo &Info) {
 612   assert(E->getType()->hasPointerRepresentation());
 613   return PointerExprEvaluator(Info, Result).Visit(E);
 614 }
 615
 616 bool PointerExprEvaluator::VisitBinaryOperator(const BinaryOperator *E) {
 617   if (E->getOpcode() != BO_Add &&
 618       E->getOpcode() != BO_Sub)
 619     return false;
 620
 621   const Expr *PExp = E->getLHS();
 622   const Expr *IExp = E->getRHS();
 623   if (IExp->getType()->isPointerType())
 624     std::swap(PExp, IExp);
 625
 626   if (!EvaluatePointer(PExp, Result, Info))
 627     return false;
 628
 629   llvm::APSInt Offset;
 630   if (!EvaluateInteger(IExp, Offset, Info))
 631     return false;
 632   int64_t AdditionalOffset
 633     = Offset.isSigned() ? Offset.getSExtValue()
 634                         : static_cast<int64_t>(Offset.getZExtValue());
 635
 636   // Compute the new offset in the appropriate width.
 637
 638   QualType PointeeType =
 639     PExp->getType()->getAs<PointerType>()->getPointeeType();
 640   CharUnits SizeOfPointee;
 641
 642   // Explicitly handle GNU void* and function pointer arithmetic extensions.
 643   if (PointeeType->isVoidType() || PointeeType->isFunctionType())
 644     SizeOfPointee = CharUnits::One();
 645   else
 646     SizeOfPointee = Info.Ctx.getTypeSizeInChars(PointeeType);
 647
 648   if (E->getOpcode() == BO_Add)
 649     Result.Offset += AdditionalOffset * SizeOfPointee;
 650   else
 651     Result.Offset -= AdditionalOffset * SizeOfPointee;
 652
 653   return true;
 654 }
 655
 656 bool PointerExprEvaluator::VisitUnaryAddrOf(const UnaryOperator *E) {
 657   return EvaluateLValue(E->getSubExpr(), Result, Info);
 658 }
 659
 660
 661 bool PointerExprEvaluator::VisitCastExpr(const CastExpr* E) {
 662   const Expr* SubExpr = E->getSubExpr();
 663
 664   switch (E->getCastKind()) {
 665   default:
 666     break;
 667
 668   case CK_NoOp:
 669   case CK_BitCast:
 670   case CK_AnyPointerToObjCPointerCast:
 671   case CK_AnyPointerToBlockPointerCast:
 672     return Visit(SubExpr);
 673
 674   case CK_DerivedToBase:
 675   case CK_UncheckedDerivedToBase: {
 676     LValue BaseLV;
 677     if (!EvaluatePointer(E->getSubExpr(), BaseLV, Info))
 678       return false;
 679
 680     // Now figure out the necessary offset to add to the baseLV to get from
 681     // the derived class to the base class.
 682     CharUnits Offset = CharUnits::Zero();
 683
 684     QualType Ty = E->getSubExpr()->getType();
 685     const CXXRecordDecl *DerivedDecl =
 686       Ty->getAs<PointerType>()->getPointeeType()->getAsCXXRecordDecl();
 687
 688     for (CastExpr::path_const_iterator PathI = E->path_begin(),
 689          PathE = E->path_end(); PathI != PathE; ++PathI) {
 690       const CXXBaseSpecifier *Base = *PathI;
 691
 692       // FIXME: If the base is virtual, we'd need to determine the type of the
 693       // most derived class and we don't support that right now.
 694       if (Base->isVirtual())
 695         return false;
 696
 697       const CXXRecordDecl *BaseDecl = Base->getType()->getAsCXXRecordDecl();
 698       const ASTRecordLayout &Layout = Info.Ctx.getASTRecordLayout(DerivedDecl);
 699
 700       Offset += Layout.getBaseClassOffset(BaseDecl);
 701       DerivedDecl = BaseDecl;
 702     }
 703
 704     Result.Base = BaseLV.getLValueBase();
 705     Result.Offset = BaseLV.getLValueOffset() + Offset;
 706     return true;
 707   }
 708
 709   case CK_NullToPointer: {
 710     Result.Base = 0;
 711     Result.Offset = CharUnits::Zero();
 712     return true;
 713   }
 714
 715   case CK_IntegralToPointer: {
 716     APValue Value;
 717     if (!EvaluateIntegerOrLValue(SubExpr, Value, Info))
 718       break;
 719
 720     if (Value.isInt()) {
 721       Value.getInt() = Value.getInt().extOrTrunc((unsigned)Info.Ctx.getTypeSize(E->getType()));
 722       Result.Base = 0;
 723       Result.Offset = CharUnits::fromQuantity(Value.getInt().getZExtValue());
 724       return true;
 725     } else {
 726       // Cast is of an lvalue, no need to change value.
 727       Result.Base = Value.getLValueBase();
 728       Result.Offset = Value.getLValueOffset();
 729       return true;
 730     }
 731   }
 732   case CK_ArrayToPointerDecay:
 733   case CK_FunctionToPointerDecay:
 734     return EvaluateLValue(SubExpr, Result, Info);
 735   }
 736
 737   return false;
 738 }
 739
 740 bool PointerExprEvaluator::VisitCallExpr(const CallExpr *E) {
 741   if (E->isBuiltinCall(Info.Ctx) ==
 742         Builtin::BI__builtin___CFStringMakeConstantString ||
 743       E->isBuiltinCall(Info.Ctx) ==
 744         Builtin::BI__builtin___NSStringMakeConstantString)
 745     return Success(E);
 746
 747   return ExprEvaluatorBaseTy::VisitCallExpr(E);
 748 }
 749
 750 //===----------------------------------------------------------------------===//
 751 // Vector Evaluation
 752 //===----------------------------------------------------------------------===//
 753
 754 namespace {
 755   class VectorExprEvaluator
 756   : public ExprEvaluatorBase<VectorExprEvaluator, APValue> {
 757     APValue GetZeroVector(QualType VecType);
 758   public:
 759
 760     VectorExprEvaluator(EvalInfo &info) : ExprEvaluatorBaseTy(info) {}
 761
 762     APValue Success(const APValue &V, const Expr *E) { return V; }
 763     APValue Error(const Expr *E) { return APValue(); }
 764
 765     APValue VisitUnaryReal(const UnaryOperator *E)
 766       { return Visit(E->getSubExpr()); }
 767     APValue VisitImplicitValueInitExpr(const ImplicitValueInitExpr *E)
 768       { return GetZeroVector(E->getType()); }
 769     APValue VisitCastExpr(const CastExpr* E);
 770     APValue VisitCompoundLiteralExpr(const CompoundLiteralExpr *E);
 771     APValue VisitInitListExpr(const InitListExpr *E);
 772     APValue VisitUnaryImag(const UnaryOperator *E);
 773     // FIXME: Missing: unary -, unary ~, binary add/sub/mul/div,
 774     //                 binary comparisons, binary and/or/xor,
 775     //                 shufflevector, ExtVectorElementExpr
 776     //        (Note that these require implementing conversions
 777     //         between vector types.)
 778   };
 779 } // end anonymous namespace
 780
 781 static bool EvaluateVector(const Expr* E, APValue& Result, EvalInfo &Info) {
 782   if (!E->getType()->isVectorType())
 783     return false;
 784   Result = VectorExprEvaluator(Info).Visit(E);
 785   return !Result.isUninit();
 786 }
 787
 788 APValue VectorExprEvaluator::VisitCastExpr(const CastExpr* E) {
 789   const VectorType *VTy = E->getType()->getAs<VectorType>();
 790   QualType EltTy = VTy->getElementType();
 791   unsigned NElts = VTy->getNumElements();
 792   unsigned EltWidth = Info.Ctx.getTypeSize(EltTy);
 793
 794   const Expr* SE = E->getSubExpr();
 795   QualType SETy = SE->getType();
 796
 797   switch (E->getCastKind()) {
 798   case CK_VectorSplat: {
 799     APValue Result = APValue();
 800     if (SETy->isIntegerType()) {
 801       APSInt IntResult;
 802       if (!EvaluateInteger(SE, IntResult, Info))
 803          return APValue();
 804       Result = APValue(IntResult);
 805     } else if (SETy->isRealFloatingType()) {
 806        APFloat F(0.0);
 807        if (!EvaluateFloat(SE, F, Info))
 808          return APValue();
 809        Result = APValue(F);
 810     } else {
 811       return APValue();
 812     }
 813
 814     // Splat and create vector APValue.
 815     llvm::SmallVector<APValue, 4> Elts(NElts, Result);
 816     return APValue(&Elts[0], Elts.size());
 817   }
 818   case CK_BitCast: {
 819     if (SETy->isVectorType())
 820       return Visit(SE);
 821
 822     if (!SETy->isIntegerType())
 823       return APValue();
 824
 825     APSInt Init;
 826     if (!EvaluateInteger(SE, Init, Info))
 827       return APValue();
 828
 829     assert((EltTy->isIntegerType() || EltTy->isRealFloatingType()) &&
 830            "Vectors must be composed of ints or floats");
 831
 832     llvm::SmallVector<APValue, 4> Elts;
 833     for (unsigned i = 0; i != NElts; ++i) {
 834       APSInt Tmp = Init.extOrTrunc(EltWidth);
 835
 836       if (EltTy->isIntegerType())
 837         Elts.push_back(APValue(Tmp));
 838       else
 839         Elts.push_back(APValue(APFloat(Tmp)));
 840
 841       Init >>= EltWidth;
 842     }
 843     return APValue(&Elts[0], Elts.size());
 844   }
 845   case CK_LValueToRValue:
 846   case CK_NoOp:
 847     return Visit(SE);
 848   default:
 849     return APValue();
 850   }
 851 }
 852
 853 APValue
 854 VectorExprEvaluator::VisitCompoundLiteralExpr(const CompoundLiteralExpr *E) {
 855   return this->Visit(E->getInitializer());
 856 }
 857
 858 APValue
 859 VectorExprEvaluator::VisitInitListExpr(const InitListExpr *E) {
 860   const VectorType *VT = E->getType()->getAs<VectorType>();
 861   unsigned NumInits = E->getNumInits();
 862   unsigned NumElements = VT->getNumElements();
 863
 864   QualType EltTy = VT->getElementType();
 865   llvm::SmallVector<APValue, 4> Elements;
 866
 867   // If a vector is initialized with a single element, that value
 868   // becomes every element of the vector, not just the first.
 869   // This is the behavior described in the IBM AltiVec documentation.
 870   if (NumInits == 1) {
 871
 872     // Handle the case where the vector is initialized by a another
 873     // vector (OpenCL 6.1.6).
 874     if (E->getInit(0)->getType()->isVectorType())
 875       return this->Visit(const_cast<Expr*>(E->getInit(0)));
 876
 877     APValue InitValue;
 878     if (EltTy->isIntegerType()) {
 879       llvm::APSInt sInt(32);
 880       if (!EvaluateInteger(E->getInit(0), sInt, Info))
 881         return APValue();
 882       InitValue = APValue(sInt);
 883     } else {
 884       llvm::APFloat f(0.0);
 885       if (!EvaluateFloat(E->getInit(0), f, Info))
 886         return APValue();
 887       InitValue = APValue(f);
 888     }
 889     for (unsigned i = 0; i < NumElements; i++) {
 890       Elements.push_back(InitValue);
 891     }
 892   } else {
 893     for (unsigned i = 0; i < NumElements; i++) {
 894       if (EltTy->isIntegerType()) {
 895         llvm::APSInt sInt(32);
 896         if (i < NumInits) {
 897           if (!EvaluateInteger(E->getInit(i), sInt, Info))
 898             return APValue();
 899         } else {
 900           sInt = Info.Ctx.MakeIntValue(0, EltTy);
 901         }
 902         Elements.push_back(APValue(sInt));
 903       } else {
 904         llvm::APFloat f(0.0);
 905         if (i < NumInits) {
 906           if (!EvaluateFloat(E->getInit(i), f, Info))
 907             return APValue();
 908         } else {
 909           f = APFloat::getZero(Info.Ctx.getFloatTypeSemantics(EltTy));
 910         }
 911         Elements.push_back(APValue(f));
 912       }
 913     }
 914   }
 915   return APValue(&Elements[0], Elements.size());
 916 }
 917
 918 APValue
 919 VectorExprEvaluator::GetZeroVector(QualType T) {
 920   const VectorType *VT = T->getAs<VectorType>();
 921   QualType EltTy = VT->getElementType();
 922   APValue ZeroElement;
 923   if (EltTy->isIntegerType())
 924     ZeroElement = APValue(Info.Ctx.MakeIntValue(0, EltTy));
 925   else
 926     ZeroElement =
 927         APValue(APFloat::getZero(Info.Ctx.getFloatTypeSemantics(EltTy)));
 928
 929   llvm::SmallVector<APValue, 4> Elements(VT->getNumElements(), ZeroElement);
 930   return APValue(&Elements[0], Elements.size());
 931 }
 932
 933 APValue VectorExprEvaluator::VisitUnaryImag(const UnaryOperator *E) {
 934   if (!E->getSubExpr()->isEvaluatable(Info.Ctx))
 935     Info.EvalResult.HasSideEffects = true;
 936   return GetZeroVector(E->getType());
 937 }
 938
 939 //===----------------------------------------------------------------------===//
 940 // Integer Evaluation
 941 //===----------------------------------------------------------------------===//
 942
 943 namespace {
 944 class IntExprEvaluator
 945   : public ExprEvaluatorBase<IntExprEvaluator, bool> {
 946   APValue &Result;
 947 public:
 948   IntExprEvaluator(EvalInfo &info, APValue &result)
 949     : ExprEvaluatorBaseTy(info), Result(result) {}
 950
 951   bool Success(const llvm::APSInt &SI, const Expr *E) {
 952     assert(E->getType()->isIntegralOrEnumerationType() &&
 953            "Invalid evaluation result.");
 954     assert(SI.isSigned() == E->getType()->isSignedIntegerOrEnumerationType() &&
 955            "Invalid evaluation result.");
 956     assert(SI.getBitWidth() == Info.Ctx.getIntWidth(E->getType()) &&
 957            "Invalid evaluation result.");
 958     Result = APValue(SI);
 959     return true;
 960   }
 961
 962   bool Success(const llvm::APInt &I, const Expr *E) {
 963     assert(E->getType()->isIntegralOrEnumerationType() &&
 964            "Invalid evaluation result.");
 965     assert(I.getBitWidth() == Info.Ctx.getIntWidth(E->getType()) &&
 966            "Invalid evaluation result.");
 967     Result = APValue(APSInt(I));
 968     Result.getInt().setIsUnsigned(
 969                             E->getType()->isUnsignedIntegerOrEnumerationType());
 970     return true;
 971   }
 972
 973   bool Success(uint64_t Value, const Expr *E) {
 974     assert(E->getType()->isIntegralOrEnumerationType() &&
 975            "Invalid evaluation result.");
 976     Result = APValue(Info.Ctx.MakeIntValue(Value, E->getType()));
 977     return true;
 978   }
 979
 980   bool Success(CharUnits Size, const Expr *E) {
 981     return Success(Size.getQuantity(), E);
 982   }
 983
 984
 985   bool Error(SourceLocation L, diag::kind D, const Expr *E) {
 986     // Take the first error.
 987     if (Info.EvalResult.Diag == 0) {
 988       Info.EvalResult.DiagLoc = L;
 989       Info.EvalResult.Diag = D;
 990       Info.EvalResult.DiagExpr = E;
 991     }
 992     return false;
 993   }
 994
 995   bool Success(const APValue &V, const Expr *E) {
 996     return Success(V.getInt(), E);
 997   }
 998   bool Error(const Expr *E) {
 999     return Error(E->getLocStart(), diag::note_invalid_subexpr_in_ice, E);
1000   }
1001
1002   //===--------------------------------------------------------------------===//
1003   //                            Visitor Methods
1004   //===--------------------------------------------------------------------===//
1005
1006   bool VisitIntegerLiteral(const IntegerLiteral *E) {
1007     return Success(E->getValue(), E);
1008   }
1009   bool VisitCharacterLiteral(const CharacterLiteral *E) {
1010     return Success(E->getValue(), E);
1011   }
1012
1013   bool CheckReferencedDecl(const Expr *E, const Decl *D);
1014   bool VisitDeclRefExpr(const DeclRefExpr *E) {
1015     if (CheckReferencedDecl(E, E->getDecl()))
1016       return true;
1017
1018     return ExprEvaluatorBaseTy::VisitDeclRefExpr(E);
1019   }
1020   bool VisitMemberExpr(const MemberExpr *E) {
1021     if (CheckReferencedDecl(E, E->getMemberDecl())) {
1022       // Conservatively assume a MemberExpr will have side-effects
1023       Info.EvalResult.HasSideEffects = true;
1024       return true;
1025     }
1026
1027     return ExprEvaluatorBaseTy::VisitMemberExpr(E);
1028   }
1029
1030   bool VisitCallExpr(const CallExpr *E);
1031   bool VisitBinaryOperator(const BinaryOperator *E);
1032   bool VisitOffsetOfExpr(const OffsetOfExpr *E);
1033   bool VisitUnaryOperator(const UnaryOperator *E);
1034
1035   bool VisitCastExpr(const CastExpr* E);
1036   bool VisitUnaryExprOrTypeTraitExpr(const UnaryExprOrTypeTraitExpr *E);
1037
1038   bool VisitCXXBoolLiteralExpr(const CXXBoolLiteralExpr *E) {
1039     return Success(E->getValue(), E);
1040   }
1041
1042   bool VisitGNUNullExpr(const GNUNullExpr *E) {
1043     return Success(0, E);
1044   }
1045
1046   bool VisitCXXScalarValueInitExpr(const CXXScalarValueInitExpr *E) {
1047     return Success(0, E);
1048   }
1049
1050   bool VisitImplicitValueInitExpr(const ImplicitValueInitExpr *E) {
1051     return Success(0, E);
1052   }
1053
1054   bool VisitUnaryTypeTraitExpr(const UnaryTypeTraitExpr *E) {
1055     return Success(E->getValue(), E);
1056   }
1057
1058   bool VisitBinaryTypeTraitExpr(const BinaryTypeTraitExpr *E) {
1059     return Success(E->getValue(), E);
1060   }
1061
1062   bool VisitArrayTypeTraitExpr(const ArrayTypeTraitExpr *E) {
1063     return Success(E->getValue(), E);
1064   }
1065
1066   bool VisitExpressionTraitExpr(const ExpressionTraitExpr *E) {
1067     return Success(E->getValue(), E);
1068   }
1069
1070   bool VisitUnaryReal(const UnaryOperator *E);
1071   bool VisitUnaryImag(const UnaryOperator *E);
1072
1073   bool VisitCXXNoexceptExpr(const CXXNoexceptExpr *E);
1074   bool VisitSizeOfPackExpr(const SizeOfPackExpr *E);
1075
1076 private:
1077   CharUnits GetAlignOfExpr(const Expr *E);
1078   CharUnits GetAlignOfType(QualType T);
1079   static QualType GetObjectType(const Expr *E);
1080   bool TryEvaluateBuiltinObjectSize(const CallExpr *E);
1081   // FIXME: Missing: array subscript of vector, member of vector
1082 };
1083 } // end anonymous namespace
1084
1085 static bool EvaluateIntegerOrLValue(const Expr* E, APValue &Result, EvalInfo &Info) {
1086   assert(E->getType()->isIntegralOrEnumerationType());
1087   return IntExprEvaluator(Info, Result).Visit(E);
1088 }
1089
1090 static bool EvaluateInteger(const Expr* E, APSInt &Result, EvalInfo &Info) {
1091   assert(E->getType()->isIntegralOrEnumerationType());
1092
1093   APValue Val;
1094   if (!EvaluateIntegerOrLValue(E, Val, Info) || !Val.isInt())
1095     return false;
1096   Result = Val.getInt();
1097   return true;
1098 }
1099
1100 bool IntExprEvaluator::CheckReferencedDecl(const Expr* E, const Decl* D) {
1101   // Enums are integer constant exprs.
1102   if (const EnumConstantDecl *ECD = dyn_cast<EnumConstantDecl>(D)) {
1103     // Check for signedness/width mismatches between E type and ECD value.
1104     bool SameSign = (ECD->getInitVal().isSigned()
1105                      == E->getType()->isSignedIntegerOrEnumerationType());
1106     bool SameWidth = (ECD->getInitVal().getBitWidth()
1107                       == Info.Ctx.getIntWidth(E->getType()));
1108     if (SameSign && SameWidth)
1109       return Success(ECD->getInitVal(), E);
1110     else {
1111       // Get rid of mismatch (otherwise Success assertions will fail)
1112       // by computing a new value matching the type of E.
1113       llvm::APSInt Val = ECD->getInitVal();
1114       if (!SameSign)
1115         Val.setIsSigned(!ECD->getInitVal().isSigned());
1116       if (!SameWidth)
1117         Val = Val.extOrTrunc(Info.Ctx.getIntWidth(E->getType()));
1118       return Success(Val, E);
1119     }
1120   }
1121
1122   // In C++, const, non-volatile integers initialized with ICEs are ICEs.
1123   // In C, they can also be folded, although they are not ICEs.
1124   if (Info.Ctx.getCanonicalType(E->getType()).getCVRQualifiers()
1125                                                         == Qualifiers::Const) {
1126
1127     if (isa<ParmVarDecl>(D))
1128       return false;
1129
1130     if (const VarDecl *VD = dyn_cast<VarDecl>(D)) {
1131       if (const Expr *Init = VD->getAnyInitializer()) {
1132         if (APValue *V = VD->getEvaluatedValue()) {
1133           if (V->isInt())
1134             return Success(V->getInt(), E);
1135           return false;
1136         }
1137
1138         if (VD->isEvaluatingValue())
1139           return false;
1140
1141         VD->setEvaluatingValue();
1142
1143         Expr::EvalResult EResult;
1144         if (Init->Evaluate(EResult, Info.Ctx) && !EResult.HasSideEffects &&
1145             EResult.Val.isInt()) {
1146           // Cache the evaluated value in the variable declaration.
1147           Result = EResult.Val;
1148           VD->setEvaluatedValue(Result);
1149           return true;
1150         }
1151
1152         VD->setEvaluatedValue(APValue());
1153       }
1154     }
1155   }
1156
1157   // Otherwise, random variable references are not constants.
1158   return false;
1159 }
1160
1161 /// EvaluateBuiltinClassifyType - Evaluate __builtin_classify_type the same way
1162 /// as GCC.
1163 static int EvaluateBuiltinClassifyType(const CallExpr *E) {
1164   // The following enum mimics the values returned by GCC.
1165   // FIXME: Does GCC differ between lvalue and rvalue references here?
1166   enum gcc_type_class {
1167     no_type_class = -1,
1168     void_type_class, integer_type_class, char_type_class,
1169     enumeral_type_class, boolean_type_class,
1170     pointer_type_class, reference_type_class, offset_type_class,
1171     real_type_class, complex_type_class,
1172     function_type_class, method_type_class,
1173     record_type_class, union_type_class,
1174     array_type_class, string_type_class,
1175     lang_type_class
1176   };
1177
1178   // If no argument was supplied, default to "no_type_class". This isn't
1179   // ideal, however it is what gcc does.
1180   if (E->getNumArgs() == 0)
1181     return no_type_class;
1182
1183   QualType ArgTy = E->getArg(0)->getType();
1184   if (ArgTy->isVoidType())
1185     return void_type_class;
1186   else if (ArgTy->isEnumeralType())
1187     return enumeral_type_class;
1188   else if (ArgTy->isBooleanType())
1189     return boolean_type_class;
1190   else if (ArgTy->isCharType())
1191     return string_type_class; // gcc doesn't appear to use char_type_class
1192   else if (ArgTy->isIntegerType())
1193     return integer_type_class;
1194   else if (ArgTy->isPointerType())
1195     return pointer_type_class;
1196   else if (ArgTy->isReferenceType())
1197     return reference_type_class;
1198   else if (ArgTy->isRealType())
1199     return real_type_class;
1200   else if (ArgTy->isComplexType())
1201     return complex_type_class;
1202   else if (ArgTy->isFunctionType())
1203     return function_type_class;
1204   else if (ArgTy->isStructureOrClassType())
1205     return record_type_class;
1206   else if (ArgTy->isUnionType())
1207     return union_type_class;
1208   else if (ArgTy->isArrayType())
1209     return array_type_class;
1210   else if (ArgTy->isUnionType())
1211     return union_type_class;
1212   else  // FIXME: offset_type_class, method_type_class, & lang_type_class?
1213     assert(0 && "CallExpr::isBuiltinClassifyType(): unimplemented type");
1214   return -1;
1215 }
1216
1217 /// Retrieves the "underlying object type" of the given expression,
1218 /// as used by __builtin_object_size.
1219 QualType IntExprEvaluator::GetObjectType(const Expr *E) {
1220   if (const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E)) {
1221     if (const VarDecl *VD = dyn_cast<VarDecl>(DRE->getDecl()))
1222       return VD->getType();
1223   } else if (isa<CompoundLiteralExpr>(E)) {
1224     return E->getType();
1225   }
1226
1227   return QualType();
1228 }
1229
1230 bool IntExprEvaluator::TryEvaluateBuiltinObjectSize(const CallExpr *E) {
1231   // TODO: Perhaps we should let LLVM lower this?
1232   LValue Base;
1233   if (!EvaluatePointer(E->getArg(0), Base, Info))
1234     return false;
1235
1236   // If we can prove the base is null, lower to zero now.
1237   const Expr *LVBase = Base.getLValueBase();
1238   if (!LVBase) return Success(0, E);
1239
1240   QualType T = GetObjectType(LVBase);
1241   if (T.isNull() ||
1242       T->isIncompleteType() ||
1243       T->isFunctionType() ||
1244       T->isVariablyModifiedType() ||
1245       T->isDependentType())
1246     return false;
1247
1248   CharUnits Size = Info.Ctx.getTypeSizeInChars(T);
1249   CharUnits Offset = Base.getLValueOffset();
1250
1251   if (!Offset.isNegative() && Offset <= Size)
1252     Size -= Offset;
1253   else
1254     Size = CharUnits::Zero();
1255   return Success(Size, E);
1256 }
1257
1258 bool IntExprEvaluator::VisitCallExpr(const CallExpr *E) {
1259   switch (E->isBuiltinCall(Info.Ctx)) {
1260   default:
1261     return ExprEvaluatorBaseTy::VisitCallExpr(E);
1262
1263   case Builtin::BI__builtin_object_size: {
1264     if (TryEvaluateBuiltinObjectSize(E))
1265       return true;
1266
1267     // If evaluating the argument has side-effects we can't determine
1268     // the size of the object and lower it to unknown now.
1269     if (E->getArg(0)->HasSideEffects(Info.Ctx)) {
1270       if (E->getArg(1)->EvaluateAsInt(Info.Ctx).getZExtValue() <= 1)
1271         return Success(-1ULL, E);
1272       return Success(0, E);
1273     }
1274
1275     return Error(E->getLocStart(), diag::note_invalid_subexpr_in_ice, E);
1276   }
1277
1278   case Builtin::BI__builtin_classify_type:
1279     return Success(EvaluateBuiltinClassifyType(E), E);
1280
1281   case Builtin::BI__builtin_constant_p:
1282     // __builtin_constant_p always has one operand: it returns true if that
1283     // operand can be folded, false otherwise.
1284     return Success(E->getArg(0)->isEvaluatable(Info.Ctx), E);
1285
1286   case Builtin::BI__builtin_eh_return_data_regno: {
1287     int Operand = E->getArg(0)->EvaluateAsInt(Info.Ctx).getZExtValue();
1288     Operand = Info.Ctx.Target.getEHDataRegisterNumber(Operand);
1289     return Success(Operand, E);
1290   }
1291
1292   case Builtin::BI__builtin_expect:
1293     return Visit(E->getArg(0));
1294
1295   case Builtin::BIstrlen:
1296   case Builtin::BI__builtin_strlen:
1297     // As an extension, we support strlen() and __builtin_strlen() as constant
1298     // expressions when the argument is a string literal.
1299     if (const StringLiteral *S
1300                = dyn_cast<StringLiteral>(E->getArg(0)->IgnoreParenImpCasts())) {
1301       // The string literal may have embedded null characters. Find the first
1302       // one and truncate there.
1303       llvm::StringRef Str = S->getString();
1304       llvm::StringRef::size_type Pos = Str.find(0);
1305       if (Pos != llvm::StringRef::npos)
1306         Str = Str.substr(0, Pos);
1307
1308       return Success(Str.size(), E);
1309     }
1310
1311     return Error(E->getLocStart(), diag::note_invalid_subexpr_in_ice, E);
1312   }
1313 }
1314
1315 bool IntExprEvaluator::VisitBinaryOperator(const BinaryOperator *E) {
1316   if (E->getOpcode() == BO_Comma) {
1317     if (!Visit(E->getRHS()))
1318       return false;
1319
1320     // If we can't evaluate the LHS, it might have side effects;
1321     // conservatively mark it.
1322     if (!E->getLHS()->isEvaluatable(Info.Ctx))
1323       Info.EvalResult.HasSideEffects = true;
1324
1325     return true;
1326   }
1327
1328   if (E->isLogicalOp()) {
1329     // These need to be handled specially because the operands aren't
1330     // necessarily integral
1331     bool lhsResult, rhsResult;
1332
1333     if (HandleConversionToBool(E->getLHS(), lhsResult, Info)) {
1334       // We were able to evaluate the LHS, see if we can get away with not
1335       // evaluating the RHS: 0 && X -> 0, 1 || X -> 1
1336       if (lhsResult == (E->getOpcode() == BO_LOr))
1337         return Success(lhsResult, E);
1338
1339       if (HandleConversionToBool(E->getRHS(), rhsResult, Info)) {
1340         if (E->getOpcode() == BO_LOr)
1341           return Success(lhsResult || rhsResult, E);
1342         else
1343           return Success(lhsResult && rhsResult, E);
1344       }
1345     } else {
1346       if (HandleConversionToBool(E->getRHS(), rhsResult, Info)) {
1347         // We can't evaluate the LHS; however, sometimes the result
1348         // is determined by the RHS: X && 0 -> 0, X || 1 -> 1.
1349         if (rhsResult == (E->getOpcode() == BO_LOr) ||
1350             !rhsResult == (E->getOpcode() == BO_LAnd)) {
1351           // Since we weren't able to evaluate the left hand side, it
1352           // must have had side effects.
1353           Info.EvalResult.HasSideEffects = true;
1354
1355           return Success(rhsResult, E);
1356         }
1357       }
1358     }
1359
1360     return false;
1361   }
1362
1363   QualType LHSTy = E->getLHS()->getType();
1364   QualType RHSTy = E->getRHS()->getType();
1365
1366   if (LHSTy->isAnyComplexType()) {
1367     assert(RHSTy->isAnyComplexType() && "Invalid comparison");
1368     ComplexValue LHS, RHS;
1369
1370     if (!EvaluateComplex(E->getLHS(), LHS, Info))
1371       return false;
1372
1373     if (!EvaluateComplex(E->getRHS(), RHS, Info))
1374       return false;
1375
1376     if (LHS.isComplexFloat()) {
1377       APFloat::cmpResult CR_r =
1378         LHS.getComplexFloatReal().compare(RHS.getComplexFloatReal());
1379       APFloat::cmpResult CR_i =
1380         LHS.getComplexFloatImag().compare(RHS.getComplexFloatImag());
1381
1382       if (E->getOpcode() == BO_EQ)
1383         return Success((CR_r == APFloat::cmpEqual &&
1384                         CR_i == APFloat::cmpEqual), E);
1385       else {
1386         assert(E->getOpcode() == BO_NE &&
1387                "Invalid complex comparison.");
1388         return Success(((CR_r == APFloat::cmpGreaterThan ||
1389                          CR_r == APFloat::cmpLessThan ||
1390                          CR_r == APFloat::cmpUnordered) ||
1391                         (CR_i == APFloat::cmpGreaterThan ||
1392                          CR_i == APFloat::cmpLessThan ||
1393                          CR_i == APFloat::cmpUnordered)), E);
1394       }
1395     } else {
1396       if (E->getOpcode() == BO_EQ)
1397         return Success((LHS.getComplexIntReal() == RHS.getComplexIntReal() &&
1398                         LHS.getComplexIntImag() == RHS.getComplexIntImag()), E);
1399       else {
1400         assert(E->getOpcode() == BO_NE &&
1401                "Invalid compex comparison.");
1402         return Success((LHS.getComplexIntReal() != RHS.getComplexIntReal() ||
1403                         LHS.getComplexIntImag() != RHS.getComplexIntImag()), E);
1404       }
1405     }
1406   }
1407
1408   if (LHSTy->isRealFloatingType() &&
1409       RHSTy->isRealFloatingType()) {
1410     APFloat RHS(0.0), LHS(0.0);
1411
1412     if (!EvaluateFloat(E->getRHS(), RHS, Info))
1413       return false;
1414
1415     if (!EvaluateFloat(E->getLHS(), LHS, Info))
1416       return false;
1417
1418     APFloat::cmpResult CR = LHS.compare(RHS);
1419
1420     switch (E->getOpcode()) {
1421     default:
1422       assert(0 && "Invalid binary operator!");
1423     case BO_LT:
1424       return Success(CR == APFloat::cmpLessThan, E);
1425     case BO_GT:
1426       return Success(CR == APFloat::cmpGreaterThan, E);
1427     case BO_LE:
1428       return Success(CR == APFloat::cmpLessThan || CR == APFloat::cmpEqual, E);
1429     case BO_GE:
1430       return Success(CR == APFloat::cmpGreaterThan || CR == APFloat::cmpEqual,
1431                      E);
1432     case BO_EQ:
1433       return Success(CR == APFloat::cmpEqual, E);
1434     case BO_NE:
1435       return Success(CR == APFloat::cmpGreaterThan
1436                      || CR == APFloat::cmpLessThan
1437                      || CR == APFloat::cmpUnordered, E);
1438     }
1439   }
1440
1441   if (LHSTy->isPointerType() && RHSTy->isPointerType()) {
1442     if (E->getOpcode() == BO_Sub || E->isEqualityOp()) {
1443       LValue LHSValue;
1444       if (!EvaluatePointer(E->getLHS(), LHSValue, Info))
1445         return false;
1446
1447       LValue RHSValue;
1448       if (!EvaluatePointer(E->getRHS(), RHSValue, Info))
1449         return false;
1450
1451       // Reject any bases from the normal codepath; we special-case comparisons
1452       // to null.
1453       if (LHSValue.getLValueBase()) {
1454         if (!E->isEqualityOp())
1455           return false;
1456         if (RHSValue.getLValueBase() || !RHSValue.getLValueOffset().isZero())
1457           return false;
1458         bool bres;
1459         if (!EvalPointerValueAsBool(LHSValue, bres))
1460           return false;
1461         return Success(bres ^ (E->getOpcode() == BO_EQ), E);
1462       } else if (RHSValue.getLValueBase()) {
1463         if (!E->isEqualityOp())
1464           return false;
1465         if (LHSValue.getLValueBase() || !LHSValue.getLValueOffset().isZero())
1466           return false;
1467         bool bres;
1468         if (!EvalPointerValueAsBool(RHSValue, bres))
1469           return false;
1470         return Success(bres ^ (E->getOpcode() == BO_EQ), E);
1471       }
1472
1473       if (E->getOpcode() == BO_Sub) {
1474         QualType Type = E->getLHS()->getType();
1475         QualType ElementType = Type->getAs<PointerType>()->getPointeeType();
1476
1477         CharUnits ElementSize = CharUnits::One();
1478         if (!ElementType->isVoidType() && !ElementType->isFunctionType())
1479           ElementSize = Info.Ctx.getTypeSizeInChars(ElementType);
1480
1481         CharUnits Diff = LHSValue.getLValueOffset() -
1482                              RHSValue.getLValueOffset();
1483         return Success(Diff / ElementSize, E);
1484       }
1485       bool Result;
1486       if (E->getOpcode() == BO_EQ) {
1487         Result = LHSValue.getLValueOffset() == RHSValue.getLValueOffset();
1488       } else {
1489         Result = LHSValue.getLValueOffset() != RHSValue.getLValueOffset();
1490       }
1491       return Success(Result, E);
1492     }
1493   }
1494   if (!LHSTy->isIntegralOrEnumerationType() ||
1495       !RHSTy->isIntegralOrEnumerationType()) {
1496     // We can't continue from here for non-integral types, and they
1497     // could potentially confuse the following operations.
1498     return false;
1499   }
1500
1501   // The LHS of a constant expr is always evaluated and needed.
1502   if (!Visit(E->getLHS()))
1503     return false; // error in subexpression.
1504
1505   APValue RHSVal;
1506   if (!EvaluateIntegerOrLValue(E->getRHS(), RHSVal, Info))
1507     return false;
1508
1509   // Handle cases like (unsigned long)&a + 4.
1510   if (E->isAdditiveOp() && Result.isLValue() && RHSVal.isInt()) {
1511     CharUnits Offset = Result.getLValueOffset();
1512     CharUnits AdditionalOffset = CharUnits::fromQuantity(
1513                                      RHSVal.getInt().getZExtValue());
1514     if (E->getOpcode() == BO_Add)
1515       Offset += AdditionalOffset;
1516     else
1517       Offset -= AdditionalOffset;
1518     Result = APValue(Result.getLValueBase(), Offset);
1519     return true;
1520   }
1521
1522   // Handle cases like 4 + (unsigned long)&a
1523   if (E->getOpcode() == BO_Add &&
1524         RHSVal.isLValue() && Result.isInt()) {
1525     CharUnits Offset = RHSVal.getLValueOffset();
1526     Offset += CharUnits::fromQuantity(Result.getInt().getZExtValue());
1527     Result = APValue(RHSVal.getLValueBase(), Offset);
1528     return true;
1529   }
1530
1531   // All the following cases expect both operands to be an integer
1532   if (!Result.isInt() || !RHSVal.isInt())
1533     return false;
1534
1535   APSInt& RHS = RHSVal.getInt();
1536
1537   switch (E->getOpcode()) {
1538   default:
1539     return Error(E->getOperatorLoc(), diag::note_invalid_subexpr_in_ice, E);
1540   case BO_Mul: return Success(Result.getInt() * RHS, E);
1541   case BO_Add: return Success(Result.getInt() + RHS, E);
1542   case BO_Sub: return Success(Result.getInt() - RHS, E);
1543   case BO_And: return Success(Result.getInt() & RHS, E);
1544   case BO_Xor: return Success(Result.getInt() ^ RHS, E);
1545   case BO_Or:  return Success(Result.getInt() | RHS, E);
1546   case BO_Div:
1547     if (RHS == 0)
1548       return Error(E->getOperatorLoc(), diag::note_expr_divide_by_zero, E);
1549     return Success(Result.getInt() / RHS, E);
1550   case BO_Rem:
1551     if (RHS == 0)
1552       return Error(E->getOperatorLoc(), diag::note_expr_divide_by_zero, E);
1553     return Success(Result.getInt() % RHS, E);
1554   case BO_Shl: {
1555     // During constant-folding, a negative shift is an opposite shift.
1556     if (RHS.isSigned() && RHS.isNegative()) {
1557       RHS = -RHS;
1558       goto shift_right;
1559     }
1560
1561   shift_left:
1562     unsigned SA
1563       = (unsigned) RHS.getLimitedValue(Result.getInt().getBitWidth()-1);
1564     return Success(Result.getInt() << SA, E);
1565   }
1566   case BO_Shr: {
1567     // During constant-folding, a negative shift is an opposite shift.
1568     if (RHS.isSigned() && RHS.isNegative()) {
1569       RHS = -RHS;
1570       goto shift_left;
1571     }
1572
1573   shift_right:
1574     unsigned SA =
1575       (unsigned) RHS.getLimitedValue(Result.getInt().getBitWidth()-1);
1576     return Success(Result.getInt() >> SA, E);
1577   }
1578
1579   case BO_LT: return Success(Result.getInt() < RHS, E);
1580   case BO_GT: return Success(Result.getInt() > RHS, E);
1581   case BO_LE: return Success(Result.getInt() <= RHS, E);
1582   case BO_GE: return Success(Result.getInt() >= RHS, E);
1583   case BO_EQ: return Success(Result.getInt() == RHS, E);
1584   case BO_NE: return Success(Result.getInt() != RHS, E);
1585   }
1586 }
1587
1588 CharUnits IntExprEvaluator::GetAlignOfType(QualType T) {
1589   // C++ [expr.sizeof]p2: "When applied to a reference or a reference type,
1590   //   the result is the size of the referenced type."
1591   // C++ [expr.alignof]p3: "When alignof is applied to a reference type, the
1592   //   result shall be the alignment of the referenced type."
1593   if (const ReferenceType *Ref = T->getAs<ReferenceType>())
1594     T = Ref->getPointeeType();
1595
1596   // __alignof is defined to return the preferred alignment.
1597   return Info.Ctx.toCharUnitsFromBits(
1598     Info.Ctx.getPreferredTypeAlign(T.getTypePtr()));
1599 }
1600
1601 CharUnits IntExprEvaluator::GetAlignOfExpr(const Expr *E) {
1602   E = E->IgnoreParens();
1603
1604   // alignof decl is always accepted, even if it doesn't make sense: we default
1605   // to 1 in those cases.
1606   if (const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E))
1607     return Info.Ctx.getDeclAlign(DRE->getDecl(),
1608                                  /*RefAsPointee*/true);
1609
1610   if (const MemberExpr *ME = dyn_cast<MemberExpr>(E))
1611     return Info.Ctx.getDeclAlign(ME->getMemberDecl(),
1612                                  /*RefAsPointee*/true);
1613
1614   return GetAlignOfType(E->getType());
1615 }
1616
1617
1618 /// VisitUnaryExprOrTypeTraitExpr - Evaluate a sizeof, alignof or vec_step with
1619 /// a result as the expression's type.
1620 bool IntExprEvaluator::VisitUnaryExprOrTypeTraitExpr(
1621                                     const UnaryExprOrTypeTraitExpr *E) {
1622   switch(E->getKind()) {
1623   case UETT_AlignOf: {
1624     if (E->isArgumentType())
1625       return Success(GetAlignOfType(E->getArgumentType()), E);
1626     else
1627       return Success(GetAlignOfExpr(E->getArgumentExpr()), E);
1628   }
1629
1630   case UETT_VecStep: {
1631     QualType Ty = E->getTypeOfArgument();
1632
1633     if (Ty->isVectorType()) {
1634       unsigned n = Ty->getAs<VectorType>()->getNumElements();
1635
1636       // The vec_step built-in functions that take a 3-component
1637       // vector return 4. (OpenCL 1.1 spec 6.11.12)
1638       if (n == 3)
1639         n = 4;
1640
1641       return Success(n, E);
1642     } else
1643       return Success(1, E);
1644   }
1645
1646   case UETT_SizeOf: {
1647     QualType SrcTy = E->getTypeOfArgument();
1648     // C++ [expr.sizeof]p2: "When applied to a reference or a reference type,
1649     //   the result is the size of the referenced type."
1650     // C++ [expr.alignof]p3: "When alignof is applied to a reference type, the
1651     //   result shall be the alignment of the referenced type."
1652     if (const ReferenceType *Ref = SrcTy->getAs<ReferenceType>())
1653       SrcTy = Ref->getPointeeType();
1654
1655     // sizeof(void), __alignof__(void), sizeof(function) = 1 as a gcc
1656     // extension.
1657     if (SrcTy->isVoidType() || SrcTy->isFunctionType())
1658       return Success(1, E);
1659
1660     // sizeof(vla) is not a constantexpr: C99 6.5.3.4p2.
1661     if (!SrcTy->isConstantSizeType())
1662       return false;
1663
1664     // Get information about the size.
1665     return Success(Info.Ctx.getTypeSizeInChars(SrcTy), E);
1666   }
1667   }
1668
1669   llvm_unreachable("unknown expr/type trait");
1670   return false;
1671 }
1672
1673 bool IntExprEvaluator::VisitOffsetOfExpr(const OffsetOfExpr *OOE) {
1674   CharUnits Result;
1675   unsigned n = OOE->getNumComponents();
1676   if (n == 0)
1677     return false;
1678   QualType CurrentType = OOE->getTypeSourceInfo()->getType();
1679   for (unsigned i = 0; i != n; ++i) {
1680     OffsetOfExpr::OffsetOfNode ON = OOE->getComponent(i);
1681     switch (ON.getKind()) {
1682     case OffsetOfExpr::OffsetOfNode::Array: {
1683       const Expr *Idx = OOE->getIndexExpr(ON.getArrayExprIndex());
1684       APSInt IdxResult;
1685       if (!EvaluateInteger(Idx, IdxResult, Info))
1686         return false;
1687       const ArrayType *AT = Info.Ctx.getAsArrayType(CurrentType);
1688       if (!AT)
1689         return false;
1690       CurrentType = AT->getElementType();
1691       CharUnits ElementSize = Info.Ctx.getTypeSizeInChars(CurrentType);
1692       Result += IdxResult.getSExtValue() * ElementSize;
1693         break;
1694     }
1695
1696     case OffsetOfExpr::OffsetOfNode::Field: {
1697       FieldDecl *MemberDecl = ON.getField();
1698       const RecordType *RT = CurrentType->getAs<RecordType>();
1699       if (!RT)
1700         return false;
1701       RecordDecl *RD = RT->getDecl();
1702       const ASTRecordLayout &RL = Info.Ctx.getASTRecordLayout(RD);
1703       unsigned i = MemberDecl->getFieldIndex();
1704       assert(i < RL.getFieldCount() && "offsetof field in wrong type");
1705       Result += Info.Ctx.toCharUnitsFromBits(RL.getFieldOffset(i));
1706       CurrentType = MemberDecl->getType().getNonReferenceType();
1707       break;
1708     }
1709
1710     case OffsetOfExpr::OffsetOfNode::Identifier:
1711       llvm_unreachable("dependent __builtin_offsetof");
1712       return false;
1713
1714     case OffsetOfExpr::OffsetOfNode::Base: {
1715       CXXBaseSpecifier *BaseSpec = ON.getBase();
1716       if (BaseSpec->isVirtual())
1717         return false;
1718
1719       // Find the layout of the class whose base we are looking into.
1720       const RecordType *RT = CurrentType->getAs<RecordType>();
1721       if (!RT)
1722         return false;
1723       RecordDecl *RD = RT->getDecl();
1724       const ASTRecordLayout &RL = Info.Ctx.getASTRecordLayout(RD);
1725
1726       // Find the base class itself.
1727       CurrentType = BaseSpec->getType();
1728       const RecordType *BaseRT = CurrentType->getAs<RecordType>();
1729       if (!BaseRT)
1730         return false;
1731
1732       // Add the offset to the base.
1733       Result += RL.getBaseClassOffset(cast<CXXRecordDecl>(BaseRT->getDecl()));
1734       break;
1735     }
1736     }
1737   }
1738   return Success(Result, OOE);
1739 }
1740
1741 bool IntExprEvaluator::VisitUnaryOperator(const UnaryOperator *E) {
1742   if (E->getOpcode() == UO_LNot) {
1743     // LNot's operand isn't necessarily an integer, so we handle it specially.
1744     bool bres;
1745     if (!HandleConversionToBool(E->getSubExpr(), bres, Info))
1746       return false;
1747     return Success(!bres, E);
1748   }
1749
1750   // Only handle integral operations...
1751   if (!E->getSubExpr()->getType()->isIntegralOrEnumerationType())
1752     return false;
1753
1754   // Get the operand value into 'Result'.
1755   if (!Visit(E->getSubExpr()))
1756     return false;
1757
1758   switch (E->getOpcode()) {
1759   default:
1760     // Address, indirect, pre/post inc/dec, etc are not valid constant exprs.
1761     // See C99 6.6p3.
1762     return Error(E->getOperatorLoc(), diag::note_invalid_subexpr_in_ice, E);
1763   case UO_Extension:
1764     // FIXME: Should extension allow i-c-e extension expressions in its scope?
1765     // If so, we could clear the diagnostic ID.
1766     return true;
1767   case UO_Plus:
1768     // The result is always just the subexpr.
1769     return true;
1770   case UO_Minus:
1771     if (!Result.isInt()) return false;
1772     return Success(-Result.getInt(), E);
1773   case UO_Not:
1774     if (!Result.isInt()) return false;
1775     return Success(~Result.getInt(), E);
1776   }
1777 }
1778
1779 /// HandleCast - This is used to evaluate implicit or explicit casts where the
1780 /// result type is integer.
1781 bool IntExprEvaluator::VisitCastExpr(const CastExpr *E) {
1782   const Expr *SubExpr = E->getSubExpr();
1783   QualType DestType = E->getType();
1784   QualType SrcType = SubExpr->getType();
1785
1786   switch (E->getCastKind()) {
1787   case CK_BaseToDerived:
1788   case CK_DerivedToBase:
1789   case CK_UncheckedDerivedToBase:
1790   case CK_Dynamic:
1791   case CK_ToUnion:
1792   case CK_ArrayToPointerDecay:
1793   case CK_FunctionToPointerDecay:
1794   case CK_NullToPointer:
1795   case CK_NullToMemberPointer:
1796   case CK_BaseToDerivedMemberPointer:
1797   case CK_DerivedToBaseMemberPointer:
1798   case CK_ConstructorConversion:
1799   case CK_IntegralToPointer:
1800   case CK_ToVoid:
1801   case CK_VectorSplat:
1802   case CK_IntegralToFloating:
1803   case CK_FloatingCast:
1804   case CK_AnyPointerToObjCPointerCast:
1805   case CK_AnyPointerToBlockPointerCast:
1806   case CK_ObjCObjectLValueCast:
1807   case CK_FloatingRealToComplex:
1808   case CK_FloatingComplexToReal:
1809   case CK_FloatingComplexCast:
1810   case CK_FloatingComplexToIntegralComplex:
1811   case CK_IntegralRealToComplex:
1812   case CK_IntegralComplexCast:
1813   case CK_IntegralComplexToFloatingComplex:
1814     llvm_unreachable("invalid cast kind for integral value");
1815
1816   case CK_BitCast:
1817   case CK_Dependent:
1818   case CK_GetObjCProperty:
1819   case CK_LValueBitCast:
1820   case CK_UserDefinedConversion:
1821   case CK_ObjCProduceObject:
1822   case CK_ObjCConsumeObject:
1823   case CK_ObjCReclaimReturnedObject:
1824     return false;
1825
1826   case CK_LValueToRValue:
1827   case CK_NoOp:
1828     return Visit(E->getSubExpr());
1829
1830   case CK_MemberPointerToBoolean:
1831   case CK_PointerToBoolean:
1832   case CK_IntegralToBoolean:
1833   case CK_FloatingToBoolean:
1834   case CK_FloatingComplexToBoolean:
1835   case CK_IntegralComplexToBoolean: {
1836     bool BoolResult;
1837     if (!HandleConversionToBool(SubExpr, BoolResult, Info))
1838       return false;
1839     return Success(BoolResult, E);
1840   }
1841
1842   case CK_IntegralCast: {
1843     if (!Visit(SubExpr))
1844       return false;
1845
1846     if (!Result.isInt()) {
1847       // Only allow casts of lvalues if they are lossless.
1848       return Info.Ctx.getTypeSize(DestType) == Info.Ctx.getTypeSize(SrcType);
1849     }
1850
1851     return Success(HandleIntToIntCast(DestType, SrcType,
1852                                       Result.getInt(), Info.Ctx), E);
1853   }
1854
1855   case CK_PointerToIntegral: {
1856     LValue LV;
1857     if (!EvaluatePointer(SubExpr, LV, Info))
1858       return false;
1859
1860     if (LV.getLValueBase()) {
1861       // Only allow based lvalue casts if they are lossless.
1862       if (Info.Ctx.getTypeSize(DestType) != Info.Ctx.getTypeSize(SrcType))
1863         return false;
1864
1865       LV.moveInto(Result);
1866       return true;
1867     }
1868
1869     APSInt AsInt = Info.Ctx.MakeIntValue(LV.getLValueOffset().getQuantity(),
1870                                          SrcType);
1871     return Success(HandleIntToIntCast(DestType, SrcType, AsInt, Info.Ctx), E);
1872   }
1873
1874   case CK_IntegralComplexToReal: {
1875     ComplexValue C;
1876     if (!EvaluateComplex(SubExpr, C, Info))
1877       return false;
1878     return Success(C.getComplexIntReal(), E);
1879   }
1880
1881   case CK_FloatingToIntegral: {
1882     APFloat F(0.0);
1883     if (!EvaluateFloat(SubExpr, F, Info))
1884       return false;
1885
1886     return Success(HandleFloatToIntCast(DestType, SrcType, F, Info.Ctx), E);
1887   }
1888   }
1889
1890   llvm_unreachable("unknown cast resulting in integral value");
1891   return false;
1892 }
1893
1894 bool IntExprEvaluator::VisitUnaryReal(const UnaryOperator *E) {
1895   if (E->getSubExpr()->getType()->isAnyComplexType()) {
1896     ComplexValue LV;
1897     if (!EvaluateComplex(E->getSubExpr(), LV, Info) || !LV.isComplexInt())
1898       return Error(E->getExprLoc(), diag::note_invalid_subexpr_in_ice, E);
1899     return Success(LV.getComplexIntReal(), E);
1900   }
1901
1902   return Visit(E->getSubExpr());
1903 }
1904
1905 bool IntExprEvaluator::VisitUnaryImag(const UnaryOperator *E) {
1906   if (E->getSubExpr()->getType()->isComplexIntegerType()) {
1907     ComplexValue LV;
1908     if (!EvaluateComplex(E->getSubExpr(), LV, Info) || !LV.isComplexInt())
1909       return Error(E->getExprLoc(), diag::note_invalid_subexpr_in_ice, E);
1910     return Success(LV.getComplexIntImag(), E);
1911   }
1912
1913   if (!E->getSubExpr()->isEvaluatable(Info.Ctx))
1914     Info.EvalResult.HasSideEffects = true;
1915   return Success(0, E);
1916 }
1917
1918 bool IntExprEvaluator::VisitSizeOfPackExpr(const SizeOfPackExpr *E) {
1919   return Success(E->getPackLength(), E);
1920 }
1921
1922 bool IntExprEvaluator::VisitCXXNoexceptExpr(const CXXNoexceptExpr *E) {
1923   return Success(E->getValue(), E);
1924 }
1925
1926 //===----------------------------------------------------------------------===//
1927 // Float Evaluation
1928 //===----------------------------------------------------------------------===//
1929
1930 namespace {
1931 class FloatExprEvaluator
1932   : public ExprEvaluatorBase<FloatExprEvaluator, bool> {
1933   APFloat &Result;
1934 public:
1935   FloatExprEvaluator(EvalInfo &info, APFloat &result)
1936     : ExprEvaluatorBaseTy(info), Result(result) {}
1937
1938   bool Success(const APValue &V, const Expr *e) {
1939     Result = V.getFloat();
1940     return true;
1941   }
1942   bool Error(const Stmt *S) {
1943     return false;
1944   }
1945
1946   bool VisitCallExpr(const CallExpr *E);
1947
1948   bool VisitUnaryOperator(const UnaryOperator *E);
1949   bool VisitBinaryOperator(const BinaryOperator *E);
1950   bool VisitFloatingLiteral(const FloatingLiteral *E);
1951   bool VisitCastExpr(const CastExpr *E);
1952   bool VisitCXXScalarValueInitExpr(const CXXScalarValueInitExpr *E);
1953
1954   bool VisitUnaryReal(const UnaryOperator *E);
1955   bool VisitUnaryImag(const UnaryOperator *E);
1956
1957   bool VisitDeclRefExpr(const DeclRefExpr *E);
1958
1959   // FIXME: Missing: array subscript of vector, member of vector,
1960   //                 ImplicitValueInitExpr
1961 };
1962 } // end anonymous namespace
1963
1964 static bool EvaluateFloat(const Expr* E, APFloat& Result, EvalInfo &Info) {
1965   assert(E->getType()->isRealFloatingType());
1966   return FloatExprEvaluator(Info, Result).Visit(E);
1967 }
1968
1969 static bool TryEvaluateBuiltinNaN(const ASTContext &Context,
1970                                   QualType ResultTy,
1971                                   const Expr *Arg,
1972                                   bool SNaN,
1973                                   llvm::APFloat &Result) {
1974   const StringLiteral *S = dyn_cast<StringLiteral>(Arg->IgnoreParenCasts());
1975   if (!S) return false;
1976
1977   const llvm::fltSemantics &Sem = Context.getFloatTypeSemantics(ResultTy);
1978
1979   llvm::APInt fill;
1980
1981   // Treat empty strings as if they were zero.
1982   if (S->getString().empty())
1983     fill = llvm::APInt(32, 0);
1984   else if (S->getString().getAsInteger(0, fill))
1985     return false;
1986
1987   if (SNaN)
1988     Result = llvm::APFloat::getSNaN(Sem, false, &fill);
1989   else
1990     Result = llvm::APFloat::getQNaN(Sem, false, &fill);
1991   return true;
1992 }
1993
1994 bool FloatExprEvaluator::VisitCallExpr(const CallExpr *E) {
1995   switch (E->isBuiltinCall(Info.Ctx)) {
1996   default:
1997     return ExprEvaluatorBaseTy::VisitCallExpr(E);
1998
1999   case Builtin::BI__builtin_huge_val:
2000   case Builtin::BI__builtin_huge_valf:
2001   case Builtin::BI__builtin_huge_vall:
2002   case Builtin::BI__builtin_inf:
2003   case Builtin::BI__builtin_inff:
2004   case Builtin::BI__builtin_infl: {
2005     const llvm::fltSemantics &Sem =
2006       Info.Ctx.getFloatTypeSemantics(E->getType());
2007     Result = llvm::APFloat::getInf(Sem);
2008     return true;
2009   }
2010
2011   case Builtin::BI__builtin_nans:
2012   case Builtin::BI__builtin_nansf:
2013   case Builtin::BI__builtin_nansl:
2014     return TryEvaluateBuiltinNaN(Info.Ctx, E->getType(), E->getArg(0),
2015                                  true, Result);
2016
2017   case Builtin::BI__builtin_nan:
2018   case Builtin::BI__builtin_nanf:
2019   case Builtin::BI__builtin_nanl:
2020     // If this is __builtin_nan() turn this into a nan, otherwise we
2021     // can't constant fold it.
2022     return TryEvaluateBuiltinNaN(Info.Ctx, E->getType(), E->getArg(0),
2023                                  false, Result);
2024
2025   case Builtin::BI__builtin_fabs:
2026   case Builtin::BI__builtin_fabsf:
2027   case Builtin::BI__builtin_fabsl:
2028     if (!EvaluateFloat(E->getArg(0), Result, Info))
2029       return false;
2030
2031     if (Result.isNegative())
2032       Result.changeSign();
2033     return true;
2034
2035   case Builtin::BI__builtin_copysign:
2036   case Builtin::BI__builtin_copysignf:
2037   case Builtin::BI__builtin_copysignl: {
2038     APFloat RHS(0.);
2039     if (!EvaluateFloat(E->getArg(0), Result, Info) ||
2040         !EvaluateFloat(E->getArg(1), RHS, Info))
2041       return false;
2042     Result.copySign(RHS);
2043     return true;
2044   }
2045   }
2046 }
2047
2048 bool FloatExprEvaluator::VisitDeclRefExpr(const DeclRefExpr *E) {
2049   if (ExprEvaluatorBaseTy::VisitDeclRefExpr(E))
2050     return true;
2051
2052   const Decl *D = E->getDecl();
2053   if (!isa<VarDecl>(D) || isa<ParmVarDecl>(D)) return false;
2054   const VarDecl *VD = cast<VarDecl>(D);
2055
2056   // Require the qualifiers to be const and not volatile.
2057   CanQualType T = Info.Ctx.getCanonicalType(E->getType());
2058   if (!T.isConstQualified() || T.isVolatileQualified())
2059     return false;
2060
2061   const Expr *Init = VD->getAnyInitializer();
2062   if (!Init) return false;
2063
2064   if (APValue *V = VD->getEvaluatedValue()) {
2065     if (V->isFloat()) {
2066       Result = V->getFloat();
2067       return true;
2068     }
2069     return false;
2070   }
2071
2072   if (VD->isEvaluatingValue())
2073     return false;
2074
2075   VD->setEvaluatingValue();
2076
2077   Expr::EvalResult InitResult;
2078   if (Init->Evaluate(InitResult, Info.Ctx) && !InitResult.HasSideEffects &&
2079       InitResult.Val.isFloat()) {
2080     // Cache the evaluated value in the variable declaration.
2081     Result = InitResult.Val.getFloat();
2082     VD->setEvaluatedValue(InitResult.Val);
2083     return true;
2084   }
2085
2086   VD->setEvaluatedValue(APValue());
2087   return false;
2088 }
2089
2090 bool FloatExprEvaluator::VisitUnaryReal(const UnaryOperator *E) {
2091   if (E->getSubExpr()->getType()->isAnyComplexType()) {
2092     ComplexValue CV;
2093     if (!EvaluateComplex(E->getSubExpr(), CV, Info))
2094       return false;
2095     Result = CV.FloatReal;
2096     return true;
2097   }
2098
2099   return Visit(E->getSubExpr());
2100 }
2101
2102 bool FloatExprEvaluator::VisitUnaryImag(const UnaryOperator *E) {
2103   if (E->getSubExpr()->getType()->isAnyComplexType()) {
2104     ComplexValue CV;
2105     if (!EvaluateComplex(E->getSubExpr(), CV, Info))
2106       return false;
2107     Result = CV.FloatImag;
2108     return true;
2109   }
2110
2111   if (!E->getSubExpr()->isEvaluatable(Info.Ctx))
2112     Info.EvalResult.HasSideEffects = true;
2113   const llvm::fltSemantics &Sem = Info.Ctx.getFloatTypeSemantics(E->getType());
2114   Result = llvm::APFloat::getZero(Sem);
2115   return true;
2116 }
2117
2118 bool FloatExprEvaluator::VisitUnaryOperator(const UnaryOperator *E) {
2119   if (E->getOpcode() == UO_Deref)
2120     return false;
2121
2122   if (!EvaluateFloat(E->getSubExpr(), Result, Info))
2123     return false;
2124
2125   switch (E->getOpcode()) {
2126   default: return false;
2127   case UO_Plus:
2128     return true;
2129   case UO_Minus:
2130     Result.changeSign();
2131     return true;
2132   }
2133 }
2134
2135 bool FloatExprEvaluator::VisitBinaryOperator(const BinaryOperator *E) {
2136   if (E->getOpcode() == BO_Comma) {
2137     if (!EvaluateFloat(E->getRHS(), Result, Info))
2138       return false;
2139
2140     // If we can't evaluate the LHS, it might have side effects;
2141     // conservatively mark it.
2142     if (!E->getLHS()->isEvaluatable(Info.Ctx))
2143       Info.EvalResult.HasSideEffects = true;
2144
2145     return true;
2146   }
2147
2148   // We can't evaluate pointer-to-member operations.
2149   if (E->isPtrMemOp())
2150     return false;
2151
2152   // FIXME: Diagnostics?  I really don't understand how the warnings
2153   // and errors are supposed to work.
2154   APFloat RHS(0.0);
2155   if (!EvaluateFloat(E->getLHS(), Result, Info))
2156     return false;
2157   if (!EvaluateFloat(E->getRHS(), RHS, Info))
2158     return false;
2159
2160   switch (E->getOpcode()) {
2161   default: return false;
2162   case BO_Mul:
2163     Result.multiply(RHS, APFloat::rmNearestTiesToEven);
2164     return true;
2165   case BO_Add:
2166     Result.add(RHS, APFloat::rmNearestTiesToEven);
2167     return true;
2168   case BO_Sub:
2169     Result.subtract(RHS, APFloat::rmNearestTiesToEven);
2170     return true;
2171   case BO_Div:
2172     Result.divide(RHS, APFloat::rmNearestTiesToEven);
2173     return true;
2174   }
2175 }
2176
2177 bool FloatExprEvaluator::VisitFloatingLiteral(const FloatingLiteral *E) {
2178   Result = E->getValue();
2179   return true;
2180 }
2181
2182 bool FloatExprEvaluator::VisitCastExpr(const CastExpr *E) {
2183   const Expr* SubExpr = E->getSubExpr();
2184
2185   switch (E->getCastKind()) {
2186   default:
2187     return false;
2188
2189   case CK_LValueToRValue:
2190   case CK_NoOp:
2191     return Visit(SubExpr);
2192
2193   case CK_IntegralToFloating: {
2194     APSInt IntResult;
2195     if (!EvaluateInteger(SubExpr, IntResult, Info))
2196       return false;
2197     Result = HandleIntToFloatCast(E->getType(), SubExpr->getType(),
2198                                   IntResult, Info.Ctx);
2199     return true;
2200   }
2201
2202   case CK_FloatingCast: {
2203     if (!Visit(SubExpr))
2204       return false;
2205     Result = HandleFloatToFloatCast(E->getType(), SubExpr->getType(),
2206                                     Result, Info.Ctx);
2207     return true;
2208   }
2209
2210   case CK_FloatingComplexToReal: {
2211     ComplexValue V;
2212     if (!EvaluateComplex(SubExpr, V, Info))
2213       return false;
2214     Result = V.getComplexFloatReal();
2215     return true;
2216   }
2217   }
2218
2219   return false;
2220 }
2221
2222 bool FloatExprEvaluator::VisitCXXScalarValueInitExpr(const CXXScalarValueInitExpr *E) {
2223   Result = APFloat::getZero(Info.Ctx.getFloatTypeSemantics(E->getType()));
2224   return true;
2225 }
2226
2227 //===----------------------------------------------------------------------===//
2228 // Complex Evaluation (for float and integer)
2229 //===----------------------------------------------------------------------===//
2230
2231 namespace {
2232 class ComplexExprEvaluator
2233   : public ExprEvaluatorBase<ComplexExprEvaluator, bool> {
2234   ComplexValue &Result;
2235
2236 public:
2237   ComplexExprEvaluator(EvalInfo &info, ComplexValue &Result)
2238     : ExprEvaluatorBaseTy(info), Result(Result) {}
2239
2240   bool Success(const APValue &V, const Expr *e) {
2241     Result.setFrom(V);
2242     return true;
2243   }
2244   bool Error(const Expr *E) {
2245     return false;
2246   }
2247
2248   //===--------------------------------------------------------------------===//
2249   //                            Visitor Methods
2250   //===--------------------------------------------------------------------===//
2251
2252   bool VisitImaginaryLiteral(const ImaginaryLiteral *E);
2253
2254   bool VisitCastExpr(const CastExpr *E);
2255
2256   bool VisitBinaryOperator(const BinaryOperator *E);
2257   bool VisitUnaryOperator(const UnaryOperator *E);
2258   // FIXME Missing: ImplicitValueInitExpr
2259 };
2260 } // end anonymous namespace
2261
2262 static bool EvaluateComplex(const Expr *E, ComplexValue &Result,
2263                             EvalInfo &Info) {
2264   assert(E->getType()->isAnyComplexType());
2265   return ComplexExprEvaluator(Info, Result).Visit(E);
2266 }
2267
2268 bool ComplexExprEvaluator::VisitImaginaryLiteral(const ImaginaryLiteral *E) {
2269   const Expr* SubExpr = E->getSubExpr();
2270
2271   if (SubExpr->getType()->isRealFloatingType()) {
2272     Result.makeComplexFloat();
2273     APFloat &Imag = Result.FloatImag;
2274     if (!EvaluateFloat(SubExpr, Imag, Info))
2275       return false;
2276
2277     Result.FloatReal = APFloat(Imag.getSemantics());
2278     return true;
2279   } else {
2280     assert(SubExpr->getType()->isIntegerType() &&
2281            "Unexpected imaginary literal.");
2282
2283     Result.makeComplexInt();
2284     APSInt &Imag = Result.IntImag;
2285     if (!EvaluateInteger(SubExpr, Imag, Info))
2286       return false;
2287
2288     Result.IntReal = APSInt(Imag.getBitWidth(), !Imag.isSigned());
2289     return true;
2290   }
2291 }
2292
2293 bool ComplexExprEvaluator::VisitCastExpr(const CastExpr *E) {
2294
2295   switch (E->getCastKind()) {
2296   case CK_BitCast:
2297   case CK_BaseToDerived:
2298   case CK_DerivedToBase:
2299   case CK_UncheckedDerivedToBase:
2300   case CK_Dynamic:
2301   case CK_ToUnion:
2302   case CK_ArrayToPointerDecay:
2303   case CK_FunctionToPointerDecay:
2304   case CK_NullToPointer:
2305   case CK_NullToMemberPointer:
2306   case CK_BaseToDerivedMemberPointer:
2307   case CK_DerivedToBaseMemberPointer:
2308   case CK_MemberPointerToBoolean:
2309   case CK_ConstructorConversion:
2310   case CK_IntegralToPointer:
2311   case CK_PointerToIntegral:
2312   case CK_PointerToBoolean:
2313   case CK_ToVoid:
2314   case CK_VectorSplat:
2315   case CK_IntegralCast:
2316   case CK_IntegralToBoolean:
2317   case CK_IntegralToFloating:
2318   case CK_FloatingToIntegral:
2319   case CK_FloatingToBoolean:
2320   case CK_FloatingCast:
2321   case CK_AnyPointerToObjCPointerCast:
2322   case CK_AnyPointerToBlockPointerCast:
2323   case CK_ObjCObjectLValueCast:
2324   case CK_FloatingComplexToReal:
2325   case CK_FloatingComplexToBoolean:
2326   case CK_IntegralComplexToReal:
2327   case CK_IntegralComplexToBoolean:
2328   case CK_ObjCProduceObject:
2329   case CK_ObjCConsumeObject:
2330   case CK_ObjCReclaimReturnedObject:
2331     llvm_unreachable("invalid cast kind for complex value");
2332
2333   case CK_LValueToRValue:
2334   case CK_NoOp:
2335     return Visit(E->getSubExpr());
2336
2337   case CK_Dependent:
2338   case CK_GetObjCProperty:
2339   case CK_LValueBitCast:
2340   case CK_UserDefinedConversion:
2341     return false;
2342
2343   case CK_FloatingRealToComplex: {
2344     APFloat &Real = Result.FloatReal;
2345     if (!EvaluateFloat(E->getSubExpr(), Real, Info))
2346       return false;
2347
2348     Result.makeComplexFloat();
2349     Result.FloatImag = APFloat(Real.getSemantics());
2350     return true;
2351   }
2352
2353   case CK_FloatingComplexCast: {
2354     if (!Visit(E->getSubExpr()))
2355       return false;
2356
2357     QualType To = E->getType()->getAs<ComplexType>()->getElementType();
2358     QualType From
2359       = E->getSubExpr()->getType()->getAs<ComplexType>()->getElementType();
2360
2361     Result.FloatReal
2362       = HandleFloatToFloatCast(To, From, Result.FloatReal, Info.Ctx);
2363     Result.FloatImag
2364       = HandleFloatToFloatCast(To, From, Result.FloatImag, Info.Ctx);
2365     return true;
2366   }
2367
2368   case CK_FloatingComplexToIntegralComplex: {
2369     if (!Visit(E->getSubExpr()))
2370       return false;
2371
2372     QualType To = E->getType()->getAs<ComplexType>()->getElementType();
2373     QualType From
2374       = E->getSubExpr()->getType()->getAs<ComplexType>()->getElementType();
2375     Result.makeComplexInt();
2376     Result.IntReal = HandleFloatToIntCast(To, From, Result.FloatReal, Info.Ctx);
2377     Result.IntImag = HandleFloatToIntCast(To, From, Result.FloatImag, Info.Ctx);
2378     return true;
2379   }
2380
2381   case CK_IntegralRealToComplex: {
2382     APSInt &Real = Result.IntReal;
2383     if (!EvaluateInteger(E->getSubExpr(), Real, Info))
2384       return false;
2385
2386     Result.makeComplexInt();
2387     Result.IntImag = APSInt(Real.getBitWidth(), !Real.isSigned());
2388     return true;
2389   }
2390
2391   case CK_IntegralComplexCast: {
2392     if (!Visit(E->getSubExpr()))
2393       return false;
2394
2395     QualType To = E->getType()->getAs<ComplexType>()->getElementType();
2396     QualType From
2397       = E->getSubExpr()->getType()->getAs<ComplexType>()->getElementType();
2398
2399     Result.IntReal = HandleIntToIntCast(To, From, Result.IntReal, Info.Ctx);
2400     Result.IntImag = HandleIntToIntCast(To, From, Result.IntImag, Info.Ctx);
2401     return true;
2402   }
2403
2404   case CK_IntegralComplexToFloatingComplex: {
2405     if (!Visit(E->getSubExpr()))
2406       return false;
2407
2408     QualType To = E->getType()->getAs<ComplexType>()->getElementType();
2409     QualType From
2410       = E->getSubExpr()->getType()->getAs<ComplexType>()->getElementType();
2411     Result.makeComplexFloat();
2412     Result.FloatReal = HandleIntToFloatCast(To, From, Result.IntReal, Info.Ctx);
2413     Result.FloatImag = HandleIntToFloatCast(To, From, Result.IntImag, Info.Ctx);
2414     return true;
2415   }
2416   }
2417
2418   llvm_unreachable("unknown cast resulting in complex value");
2419   return false;
2420 }
2421
2422 bool ComplexExprEvaluator::VisitBinaryOperator(const BinaryOperator *E) {
2423   if (E->getOpcode() == BO_Comma) {
2424     if (!Visit(E->getRHS()))
2425       return false;
2426
2427     // If we can't evaluate the LHS, it might have side effects;
2428     // conservatively mark it.
2429     if (!E->getLHS()->isEvaluatable(Info.Ctx))
2430       Info.EvalResult.HasSideEffects = true;
2431
2432     return true;
2433   }
2434   if (!Visit(E->getLHS()))
2435     return false;
2436
2437   ComplexValue RHS;
2438   if (!EvaluateComplex(E->getRHS(), RHS, Info))
2439     return false;
2440
2441   assert(Result.isComplexFloat() == RHS.isComplexFloat() &&
2442          "Invalid operands to binary operator.");
2443   switch (E->getOpcode()) {
2444   default: return false;
2445   case BO_Add:
2446     if (Result.isComplexFloat()) {
2447       Result.getComplexFloatReal().add(RHS.getComplexFloatReal(),
2448                                        APFloat::rmNearestTiesToEven);
2449       Result.getComplexFloatImag().add(RHS.getComplexFloatImag(),
2450                                        APFloat::rmNearestTiesToEven);
2451     } else {
2452       Result.getComplexIntReal() += RHS.getComplexIntReal();
2453       Result.getComplexIntImag() += RHS.getComplexIntImag();
2454     }
2455     break;
2456   case BO_Sub:
2457     if (Result.isComplexFloat()) {
2458       Result.getComplexFloatReal().subtract(RHS.getComplexFloatReal(),
2459                                             APFloat::rmNearestTiesToEven);
2460       Result.getComplexFloatImag().subtract(RHS.getComplexFloatImag(),
2461                                             APFloat::rmNearestTiesToEven);
2462     } else {
2463       Result.getComplexIntReal() -= RHS.getComplexIntReal();
2464       Result.getComplexIntImag() -= RHS.getComplexIntImag();
2465     }
2466     break;
2467   case BO_Mul:
2468     if (Result.isComplexFloat()) {
2469       ComplexValue LHS = Result;
2470       APFloat &LHS_r = LHS.getComplexFloatReal();
2471       APFloat &LHS_i = LHS.getComplexFloatImag();
2472       APFloat &RHS_r = RHS.getComplexFloatReal();
2473       APFloat &RHS_i = RHS.getComplexFloatImag();
2474
2475       APFloat Tmp = LHS_r;
2476       Tmp.multiply(RHS_r, APFloat::rmNearestTiesToEven);
2477       Result.getComplexFloatReal() = Tmp;
2478       Tmp = LHS_i;
2479       Tmp.multiply(RHS_i, APFloat::rmNearestTiesToEven);
2480       Result.getComplexFloatReal().subtract(Tmp, APFloat::rmNearestTiesToEven);
2481
2482       Tmp = LHS_r;
2483       Tmp.multiply(RHS_i, APFloat::rmNearestTiesToEven);
2484       Result.getComplexFloatImag() = Tmp;
2485       Tmp = LHS_i;
2486       Tmp.multiply(RHS_r, APFloat::rmNearestTiesToEven);
2487       Result.getComplexFloatImag().add(Tmp, APFloat::rmNearestTiesToEven);
2488     } else {
2489       ComplexValue LHS = Result;
2490       Result.getComplexIntReal() =
2491         (LHS.getComplexIntReal() * RHS.getComplexIntReal() -
2492          LHS.getComplexIntImag() * RHS.getComplexIntImag());
2493       Result.getComplexIntImag() =
2494         (LHS.getComplexIntReal() * RHS.getComplexIntImag() +
2495          LHS.getComplexIntImag() * RHS.getComplexIntReal());
2496     }
2497     break;
2498   case BO_Div:
2499     if (Result.isComplexFloat()) {
2500       ComplexValue LHS = Result;
2501       APFloat &LHS_r = LHS.getComplexFloatReal();
2502       APFloat &LHS_i = LHS.getComplexFloatImag();
2503       APFloat &RHS_r = RHS.getComplexFloatReal();
2504       APFloat &RHS_i = RHS.getComplexFloatImag();
2505       APFloat &Res_r = Result.getComplexFloatReal();
2506       APFloat &Res_i = Result.getComplexFloatImag();
2507
2508       APFloat Den = RHS_r;
2509       Den.multiply(RHS_r, APFloat::rmNearestTiesToEven);
2510       APFloat Tmp = RHS_i;
2511       Tmp.multiply(RHS_i, APFloat::rmNearestTiesToEven);
2512       Den.add(Tmp, APFloat::rmNearestTiesToEven);
2513
2514       Res_r = LHS_r;
2515       Res_r.multiply(RHS_r, APFloat::rmNearestTiesToEven);
2516       Tmp = LHS_i;
2517       Tmp.multiply(RHS_i, APFloat::rmNearestTiesToEven);
2518       Res_r.add(Tmp, APFloat::rmNearestTiesToEven);
2519       Res_r.divide(Den, APFloat::rmNearestTiesToEven);
2520
2521       Res_i = LHS_i;
2522       Res_i.multiply(RHS_r, APFloat::rmNearestTiesToEven);
2523       Tmp = LHS_r;
2524       Tmp.multiply(RHS_i, APFloat::rmNearestTiesToEven);
2525       Res_i.subtract(Tmp, APFloat::rmNearestTiesToEven);
2526       Res_i.divide(Den, APFloat::rmNearestTiesToEven);
2527     } else {
2528       if (RHS.getComplexIntReal() == 0 && RHS.getComplexIntImag() == 0) {
2529         // FIXME: what about diagnostics?
2530         return false;
2531       }
2532       ComplexValue LHS = Result;
2533       APSInt Den = RHS.getComplexIntReal() * RHS.getComplexIntReal() +
2534         RHS.getComplexIntImag() * RHS.getComplexIntImag();
2535       Result.getComplexIntReal() =
2536         (LHS.getComplexIntReal() * RHS.getComplexIntReal() +
2537          LHS.getComplexIntImag() * RHS.getComplexIntImag()) / Den;
2538       Result.getComplexIntImag() =
2539         (LHS.getComplexIntImag() * RHS.getComplexIntReal() -
2540          LHS.getComplexIntReal() * RHS.getComplexIntImag()) / Den;
2541     }
2542     break;
2543   }
2544
2545   return true;
2546 }
2547
2548 bool ComplexExprEvaluator::VisitUnaryOperator(const UnaryOperator *E) {
2549   // Get the operand value into 'Result'.
2550   if (!Visit(E->getSubExpr()))
2551     return false;
2552
2553   switch (E->getOpcode()) {
2554   default:
2555     // FIXME: what about diagnostics?
2556     return false;
2557   case UO_Extension:
2558     return true;
2559   case UO_Plus:
2560     // The result is always just the subexpr.
2561     return true;
2562   case UO_Minus:
2563     if (Result.isComplexFloat()) {
2564       Result.getComplexFloatReal().changeSign();
2565       Result.getComplexFloatImag().changeSign();
2566     }
2567     else {
2568       Result.getComplexIntReal() = -Result.getComplexIntReal();
2569       Result.getComplexIntImag() = -Result.getComplexIntImag();
2570     }
2571     return true;
2572   case UO_Not:
2573     if (Result.isComplexFloat())
2574       Result.getComplexFloatImag().changeSign();
2575     else
2576       Result.getComplexIntImag() = -Result.getComplexIntImag();
2577     return true;
2578   }
2579 }
2580
2581 //===----------------------------------------------------------------------===//
2582 // Top level Expr::Evaluate method.
2583 //===----------------------------------------------------------------------===//
2584
2585 static bool Evaluate(EvalInfo &Info, const Expr *E) {
2586   if (E->getType()->isVectorType()) {
2587     if (!EvaluateVector(E, Info.EvalResult.Val, Info))
2588       return false;
2589   } else if (E->getType()->isIntegralOrEnumerationType()) {
2590     if (!IntExprEvaluator(Info, Info.EvalResult.Val).Visit(E))
2591       return false;
2592     if (Info.EvalResult.Val.isLValue() &&
2593         !IsGlobalLValue(Info.EvalResult.Val.getLValueBase()))
2594       return false;
2595   } else if (E->getType()->hasPointerRepresentation()) {
2596     LValue LV;
2597     if (!EvaluatePointer(E, LV, Info))
2598       return false;
2599     if (!IsGlobalLValue(LV.Base))
2600       return false;
2601     LV.moveInto(Info.EvalResult.Val);
2602   } else if (E->getType()->isRealFloatingType()) {
2603     llvm::APFloat F(0.0);
2604     if (!EvaluateFloat(E, F, Info))
2605       return false;
2606
2607     Info.EvalResult.Val = APValue(F);
2608   } else if (E->getType()->isAnyComplexType()) {
2609     ComplexValue C;
2610     if (!EvaluateComplex(E, C, Info))
2611       return false;
2612     C.moveInto(Info.EvalResult.Val);
2613   } else
2614     return false;
2615
2616   return true;
2617 }
2618
2619 /// Evaluate - Return true if this is a constant which we can fold using
2620 /// any crazy technique (that has nothing to do with language standards) that
2621 /// we want to.  If this function returns true, it returns the folded constant
2622 /// in Result.
2623 bool Expr::Evaluate(EvalResult &Result, const ASTContext &Ctx) const {
2624   EvalInfo Info(Ctx, Result);
2625   return ::Evaluate(Info, this);
2626 }
2627
2628 bool Expr::EvaluateAsBooleanCondition(bool &Result,
2629                                       const ASTContext &Ctx) const {
2630   EvalResult Scratch;
2631   EvalInfo Info(Ctx, Scratch);
2632
2633   return HandleConversionToBool(this, Result, Info);
2634 }
2635
2636 bool Expr::EvaluateAsLValue(EvalResult &Result, const ASTContext &Ctx) const {
2637   EvalInfo Info(Ctx, Result);
2638
2639   LValue LV;
2640   if (EvaluateLValue(this, LV, Info) &&
2641       !Result.HasSideEffects &&
2642       IsGlobalLValue(LV.Base)) {
2643     LV.moveInto(Result.Val);
2644     return true;
2645   }
2646   return false;
2647 }
2648
2649 bool Expr::EvaluateAsAnyLValue(EvalResult &Result,
2650                                const ASTContext &Ctx) const {
2651   EvalInfo Info(Ctx, Result);
2652
2653   LValue LV;
2654   if (EvaluateLValue(this, LV, Info)) {
2655     LV.moveInto(Result.Val);
2656     return true;
2657   }
2658   return false;
2659 }
2660
2661 /// isEvaluatable - Call Evaluate to see if this expression can be constant
2662 /// folded, but discard the result.
2663 bool Expr::isEvaluatable(const ASTContext &Ctx) const {
2664   EvalResult Result;
2665   return Evaluate(Result, Ctx) && !Result.HasSideEffects;
2666 }
2667
2668 bool Expr::HasSideEffects(const ASTContext &Ctx) const {
2669   Expr::EvalResult Result;
2670   EvalInfo Info(Ctx, Result);
2671   return HasSideEffect(Info).Visit(this);
2672 }
2673
2674 APSInt Expr::EvaluateAsInt(const ASTContext &Ctx) const {
2675   EvalResult EvalResult;
2676   bool Result = Evaluate(EvalResult, Ctx);
2677   (void)Result;
2678   assert(Result && "Could not evaluate expression");
2679   assert(EvalResult.Val.isInt() && "Expression did not evaluate to integer");
2680
2681   return EvalResult.Val.getInt();
2682 }
2683
2684  bool Expr::EvalResult::isGlobalLValue() const {
2685    assert(Val.isLValue());
2686    return IsGlobalLValue(Val.getLValueBase());
2687  }
2688
2689
2690 /// isIntegerConstantExpr - this recursive routine will test if an expression is
2691 /// an integer constant expression.
2692
2693 /// FIXME: Pass up a reason why! Invalid operation in i-c-e, division by zero,
2694 /// comma, etc
2695 ///
2696 /// FIXME: Handle offsetof.  Two things to do:  Handle GCC's __builtin_offsetof
2697 /// to support gcc 4.0+  and handle the idiom GCC recognizes with a null pointer
2698 /// cast+dereference.
2699
2700 // CheckICE - This function does the fundamental ICE checking: the returned
2701 // ICEDiag contains a Val of 0, 1, or 2, and a possibly null SourceLocation.
2702 // Note that to reduce code duplication, this helper does no evaluation
2703 // itself; the caller checks whether the expression is evaluatable, and
2704 // in the rare cases where CheckICE actually cares about the evaluated
2705 // value, it calls into Evalute.
2706 //
2707 // Meanings of Val:
2708 // 0: This expression is an ICE if it can be evaluated by Evaluate.
2709 // 1: This expression is not an ICE, but if it isn't evaluated, it's
2710 //    a legal subexpression for an ICE. This return value is used to handle
2711 //    the comma operator in C99 mode.
2712 // 2: This expression is not an ICE, and is not a legal subexpression for one.
2713
2714 namespace {
2715
2716 struct ICEDiag {
2717   unsigned Val;
2718   SourceLocation Loc;
2719
2720   public:
2721   ICEDiag(unsigned v, SourceLocation l) : Val(v), Loc(l) {}
2722   ICEDiag() : Val(0) {}
2723 };
2724
2725 }
2726
2727 static ICEDiag NoDiag() { return ICEDiag(); }
2728
2729 static ICEDiag CheckEvalInICE(const Expr* E, ASTContext &Ctx) {
2730   Expr::EvalResult EVResult;
2731   if (!E->Evaluate(EVResult, Ctx) || EVResult.HasSideEffects ||
2732       !EVResult.Val.isInt()) {
2733     return ICEDiag(2, E->getLocStart());
2734   }
2735   return NoDiag();
2736 }
2737
2738 static ICEDiag CheckICE(const Expr* E, ASTContext &Ctx) {
2739   assert(!E->isValueDependent() && "Should not see value dependent exprs!");
2740   if (!E->getType()->isIntegralOrEnumerationType()) {
2741     return ICEDiag(2, E->getLocStart());
2742   }
2743
2744   switch (E->getStmtClass()) {
2745 #define ABSTRACT_STMT(Node)
2746 #define STMT(Node, Base) case Expr::Node##Class:
2747 #define EXPR(Node, Base)
2748 #include "clang/AST/StmtNodes.inc"
2749   case Expr::PredefinedExprClass:
2750   case Expr::FloatingLiteralClass:
2751   case Expr::ImaginaryLiteralClass:
2752   case Expr::StringLiteralClass:
2753   case Expr::ArraySubscriptExprClass:
2754   case Expr::MemberExprClass:
2755   case Expr::CompoundAssignOperatorClass:
2756   case Expr::CompoundLiteralExprClass:
2757   case Expr::ExtVectorElementExprClass:
2758   case Expr::InitListExprClass:
2759   case Expr::DesignatedInitExprClass:
2760   case Expr::ImplicitValueInitExprClass:
2761   case Expr::ParenListExprClass:
2762   case Expr::VAArgExprClass:
2763   case Expr::AddrLabelExprClass:
2764   case Expr::StmtExprClass:
2765   case Expr::CXXMemberCallExprClass:
2766   case Expr::CUDAKernelCallExprClass:
2767   case Expr::CXXDynamicCastExprClass:
2768   case Expr::CXXTypeidExprClass:
2769   case Expr::CXXUuidofExprClass:
2770   case Expr::CXXNullPtrLiteralExprClass:
2771   case Expr::CXXThisExprClass:
2772   case Expr::CXXThrowExprClass:
2773   case Expr::CXXNewExprClass:
2774   case Expr::CXXDeleteExprClass:
2775   case Expr::CXXPseudoDestructorExprClass:
2776   case Expr::UnresolvedLookupExprClass:
2777   case Expr::DependentScopeDeclRefExprClass:
2778   case Expr::CXXConstructExprClass:
2779   case Expr::CXXBindTemporaryExprClass:
2780   case Expr::ExprWithCleanupsClass:
2781   case Expr::CXXTemporaryObjectExprClass:
2782   case Expr::CXXUnresolvedConstructExprClass:
2783   case Expr::CXXDependentScopeMemberExprClass:
2784   case Expr::UnresolvedMemberExprClass:
2785   case Expr::ObjCStringLiteralClass:
2786   case Expr::ObjCEncodeExprClass:
2787   case Expr::ObjCMessageExprClass:
2788   case Expr::ObjCSelectorExprClass:
2789   case Expr::ObjCProtocolExprClass:
2790   case Expr::ObjCIvarRefExprClass:
2791   case Expr::ObjCPropertyRefExprClass:
2792   case Expr::ObjCIsaExprClass:
2793   case Expr::ShuffleVectorExprClass:
2794   case Expr::BlockExprClass:
2795   case Expr::BlockDeclRefExprClass:
2796   case Expr::NoStmtClass:
2797   case Expr::OpaqueValueExprClass:
2798   case Expr::PackExpansionExprClass:
2799   case Expr::SubstNonTypeTemplateParmPackExprClass:
2800   case Expr::AsTypeExprClass:
2801   case Expr::ObjCIndirectCopyRestoreExprClass:
2802   case Expr::MaterializeTemporaryExprClass:
2803     return ICEDiag(2, E->getLocStart());
2804
2805   case Expr::SizeOfPackExprClass:
2806   case Expr::GNUNullExprClass:
2807     // GCC considers the GNU __null value to be an integral constant expression.
2808     return NoDiag();
2809
2810   case Expr::SubstNonTypeTemplateParmExprClass:
2811     return
2812       CheckICE(cast<SubstNonTypeTemplateParmExpr>(E)->getReplacement(), Ctx);
2813
2814   case Expr::ParenExprClass:
2815     return CheckICE(cast<ParenExpr>(E)->getSubExpr(), Ctx);
2816   case Expr::GenericSelectionExprClass:
2817     return CheckICE(cast<GenericSelectionExpr>(E)->getResultExpr(), Ctx);
2818   case Expr::IntegerLiteralClass:
2819   case Expr::CharacterLiteralClass:
2820   case Expr::CXXBoolLiteralExprClass:
2821   case Expr::CXXScalarValueInitExprClass:
2822   case Expr::UnaryTypeTraitExprClass:
2823   case Expr::BinaryTypeTraitExprClass:
2824   case Expr::ArrayTypeTraitExprClass:
2825   case Expr::ExpressionTraitExprClass:
2826   case Expr::CXXNoexceptExprClass:
2827     return NoDiag();
2828   case Expr::CallExprClass:
2829   case Expr::CXXOperatorCallExprClass: {
2830     const CallExpr *CE = cast<CallExpr>(E);
2831     if (CE->isBuiltinCall(Ctx))
2832       return CheckEvalInICE(E, Ctx);
2833     return ICEDiag(2, E->getLocStart());
2834   }
2835   case Expr::DeclRefExprClass:
2836     if (isa<EnumConstantDecl>(cast<DeclRefExpr>(E)->getDecl()))
2837       return NoDiag();
2838     if (Ctx.getLangOptions().CPlusPlus &&
2839         E->getType().getCVRQualifiers() == Qualifiers::Const) {
2840       const NamedDecl *D = cast<DeclRefExpr>(E)->getDecl();
2841
2842       // Parameter variables are never constants.  Without this check,
2843       // getAnyInitializer() can find a default argument, which leads
2844       // to chaos.
2845       if (isa<ParmVarDecl>(D))
2846         return ICEDiag(2, cast<DeclRefExpr>(E)->getLocation());
2847
2848       // C++ 7.1.5.1p2
2849       //   A variable of non-volatile const-qualified integral or enumeration
2850       //   type initialized by an ICE can be used in ICEs.
2851       if (const VarDecl *Dcl = dyn_cast<VarDecl>(D)) {
2852         Qualifiers Quals = Ctx.getCanonicalType(Dcl->getType()).getQualifiers();
2853         if (Quals.hasVolatile() || !Quals.hasConst())
2854           return ICEDiag(2, cast<DeclRefExpr>(E)->getLocation());
2855
2856         // Look for a declaration of this variable that has an initializer.
2857         const VarDecl *ID = 0;
2858         const Expr *Init = Dcl->getAnyInitializer(ID);
2859         if (Init) {
2860           if (ID->isInitKnownICE()) {
2861             // We have already checked whether this subexpression is an
2862             // integral constant expression.
2863             if (ID->isInitICE())
2864               return NoDiag();
2865             else
2866               return ICEDiag(2, cast<DeclRefExpr>(E)->getLocation());
2867           }
2868
2869           // It's an ICE whether or not the definition we found is
2870           // out-of-line.  See DR 721 and the discussion in Clang PR
2871           // 6206 for details.
2872
2873           if (Dcl->isCheckingICE()) {
2874             return ICEDiag(2, cast<DeclRefExpr>(E)->getLocation());
2875           }
2876
2877           Dcl->setCheckingICE();
2878           ICEDiag Result = CheckICE(Init, Ctx);
2879           // Cache the result of the ICE test.
2880           Dcl->setInitKnownICE(Result.Val == 0);
2881           return Result;
2882         }
2883       }
2884     }
2885     return ICEDiag(2, E->getLocStart());
2886   case Expr::UnaryOperatorClass: {
2887     const UnaryOperator *Exp = cast<UnaryOperator>(E);
2888     switch (Exp->getOpcode()) {
2889     case UO_PostInc:
2890     case UO_PostDec:
2891     case UO_PreInc:
2892     case UO_PreDec:
2893     case UO_AddrOf:
2894     case UO_Deref:
2895       return ICEDiag(2, E->getLocStart());
2896     case UO_Extension:
2897     case UO_LNot:
2898     case UO_Plus:
2899     case UO_Minus:
2900     case UO_Not:
2901     case UO_Real:
2902     case UO_Imag:
2903       return CheckICE(Exp->getSubExpr(), Ctx);
2904     }
2905
2906     // OffsetOf falls through here.
2907   }
2908   case Expr::OffsetOfExprClass: {
2909       // Note that per C99, offsetof must be an ICE. And AFAIK, using
2910       // Evaluate matches the proposed gcc behavior for cases like
2911       // "offsetof(struct s{int x[4];}, x[!.0])".  This doesn't affect
2912       // compliance: we should warn earlier for offsetof expressions with
2913       // array subscripts that aren't ICEs, and if the array subscripts
2914       // are ICEs, the value of the offsetof must be an integer constant.
2915       return CheckEvalInICE(E, Ctx);
2916   }
2917   case Expr::UnaryExprOrTypeTraitExprClass: {
2918     const UnaryExprOrTypeTraitExpr *Exp = cast<UnaryExprOrTypeTraitExpr>(E);
2919     if ((Exp->getKind() ==  UETT_SizeOf) &&
2920         Exp->getTypeOfArgument()->isVariableArrayType())
2921       return ICEDiag(2, E->getLocStart());
2922     return NoDiag();
2923   }
2924   case Expr::BinaryOperatorClass: {
2925     const BinaryOperator *Exp = cast<BinaryOperator>(E);
2926     switch (Exp->getOpcode()) {
2927     case BO_PtrMemD:
2928     case BO_PtrMemI:
2929     case BO_Assign:
2930     case BO_MulAssign:
2931     case BO_DivAssign:
2932     case BO_RemAssign:
2933     case BO_AddAssign:
2934     case BO_SubAssign:
2935     case BO_ShlAssign:
2936     case BO_ShrAssign:
2937     case BO_AndAssign:
2938     case BO_XorAssign:
2939     case BO_OrAssign:
2940       return ICEDiag(2, E->getLocStart());
2941
2942     case BO_Mul:
2943     case BO_Div:
2944     case BO_Rem:
2945     case BO_Add:
2946     case BO_Sub:
2947     case BO_Shl:
2948     case BO_Shr:
2949     case BO_LT:
2950     case BO_GT:
2951     case BO_LE:
2952     case BO_GE:
2953     case BO_EQ:
2954     case BO_NE:
2955     case BO_And:
2956     case BO_Xor:
2957     case BO_Or:
2958     case BO_Comma: {
2959       ICEDiag LHSResult = CheckICE(Exp->getLHS(), Ctx);
2960       ICEDiag RHSResult = CheckICE(Exp->getRHS(), Ctx);
2961       if (Exp->getOpcode() == BO_Div ||
2962           Exp->getOpcode() == BO_Rem) {
2963         // Evaluate gives an error for undefined Div/Rem, so make sure
2964         // we don't evaluate one.
2965         if (LHSResult.Val == 0 && RHSResult.Val == 0) {
2966           llvm::APSInt REval = Exp->getRHS()->EvaluateAsInt(Ctx);
2967           if (REval == 0)
2968             return ICEDiag(1, E->getLocStart());
2969           if (REval.isSigned() && REval.isAllOnesValue()) {
2970             llvm::APSInt LEval = Exp->getLHS()->EvaluateAsInt(Ctx);
2971             if (LEval.isMinSignedValue())
2972               return ICEDiag(1, E->getLocStart());
2973           }
2974         }
2975       }
2976       if (Exp->getOpcode() == BO_Comma) {
2977         if (Ctx.getLangOptions().C99) {
2978           // C99 6.6p3 introduces a strange edge case: comma can be in an ICE
2979           // if it isn't evaluated.
2980           if (LHSResult.Val == 0 && RHSResult.Val == 0)
2981             return ICEDiag(1, E->getLocStart());
2982         } else {
2983           // In both C89 and C++, commas in ICEs are illegal.
2984           return ICEDiag(2, E->getLocStart());
2985         }
2986       }
2987       if (LHSResult.Val >= RHSResult.Val)
2988         return LHSResult;
2989       return RHSResult;
2990     }
2991     case BO_LAnd:
2992     case BO_LOr: {
2993       ICEDiag LHSResult = CheckICE(Exp->getLHS(), Ctx);
2994
2995       // C++0x [expr.const]p2:
2996       //   [...] subexpressions of logical AND (5.14), logical OR
2997       //   (5.15), and condi- tional (5.16) operations that are not
2998       //   evaluated are not considered.
2999       if (Ctx.getLangOptions().CPlusPlus0x && LHSResult.Val == 0) {
3000         if (Exp->getOpcode() == BO_LAnd &&
3001             Exp->getLHS()->EvaluateAsInt(Ctx) == 0)
3002           return LHSResult;
3003
3004         if (Exp->getOpcode() == BO_LOr &&
3005             Exp->getLHS()->EvaluateAsInt(Ctx) != 0)
3006           return LHSResult;
3007       }
3008
3009       ICEDiag RHSResult = CheckICE(Exp->getRHS(), Ctx);
3010       if (LHSResult.Val == 0 && RHSResult.Val == 1) {
3011         // Rare case where the RHS has a comma "side-effect"; we need
3012         // to actually check the condition to see whether the side
3013         // with the comma is evaluated.
3014         if ((Exp->getOpcode() == BO_LAnd) !=
3015             (Exp->getLHS()->EvaluateAsInt(Ctx) == 0))
3016           return RHSResult;
3017         return NoDiag();
3018       }
3019
3020       if (LHSResult.Val >= RHSResult.Val)
3021         return LHSResult;
3022       return RHSResult;
3023     }
3024     }
3025   }
3026   case Expr::ImplicitCastExprClass:
3027   case Expr::CStyleCastExprClass:
3028   case Expr::CXXFunctionalCastExprClass:
3029   case Expr::CXXStaticCastExprClass:
3030   case Expr::CXXReinterpretCastExprClass:
3031   case Expr::CXXConstCastExprClass:
3032   case Expr::ObjCBridgedCastExprClass: {
3033     const Expr *SubExpr = cast<CastExpr>(E)->getSubExpr();
3034     if (SubExpr->getType()->isIntegralOrEnumerationType())
3035       return CheckICE(SubExpr, Ctx);
3036     if (isa<FloatingLiteral>(SubExpr->IgnoreParens()))
3037       return NoDiag();
3038     return ICEDiag(2, E->getLocStart());
3039   }
3040   case Expr::BinaryConditionalOperatorClass: {
3041     const BinaryConditionalOperator *Exp = cast<BinaryConditionalOperator>(E);
3042     ICEDiag CommonResult = CheckICE(Exp->getCommon(), Ctx);
3043     if (CommonResult.Val == 2) return CommonResult;
3044     ICEDiag FalseResult = CheckICE(Exp->getFalseExpr(), Ctx);
3045     if (FalseResult.Val == 2) return FalseResult;
3046     if (CommonResult.Val == 1) return CommonResult;
3047     if (FalseResult.Val == 1 &&
3048         Exp->getCommon()->EvaluateAsInt(Ctx) == 0) return NoDiag();
3049     return FalseResult;
3050   }
3051   case Expr::ConditionalOperatorClass: {
3052     const ConditionalOperator *Exp = cast<ConditionalOperator>(E);
3053     // If the condition (ignoring parens) is a __builtin_constant_p call,
3054     // then only the true side is actually considered in an integer constant
3055     // expression, and it is fully evaluated.  This is an important GNU
3056     // extension.  See GCC PR38377 for discussion.
3057     if (const CallExpr *CallCE
3058         = dyn_cast<CallExpr>(Exp->getCond()->IgnoreParenCasts()))
3059       if (CallCE->isBuiltinCall(Ctx) == Builtin::BI__builtin_constant_p) {
3060         Expr::EvalResult EVResult;
3061         if (!E->Evaluate(EVResult, Ctx) || EVResult.HasSideEffects ||
3062             !EVResult.Val.isInt()) {
3063           return ICEDiag(2, E->getLocStart());
3064         }
3065         return NoDiag();
3066       }
3067     ICEDiag CondResult = CheckICE(Exp->getCond(), Ctx);
3068     if (CondResult.Val == 2)
3069       return CondResult;
3070
3071     // C++0x [expr.const]p2:
3072     //   subexpressions of [...] conditional (5.16) operations that
3073     //   are not evaluated are not considered
3074     bool TrueBranch = Ctx.getLangOptions().CPlusPlus0x
3075       ? Exp->getCond()->EvaluateAsInt(Ctx) != 0
3076       : false;
3077     ICEDiag TrueResult = NoDiag();
3078     if (!Ctx.getLangOptions().CPlusPlus0x || TrueBranch)
3079       TrueResult = CheckICE(Exp->getTrueExpr(), Ctx);
3080     ICEDiag FalseResult = NoDiag();
3081     if (!Ctx.getLangOptions().CPlusPlus0x || !TrueBranch)
3082       FalseResult = CheckICE(Exp->getFalseExpr(), Ctx);
3083
3084     if (TrueResult.Val == 2)
3085       return TrueResult;
3086     if (FalseResult.Val == 2)
3087       return FalseResult;
3088     if (CondResult.Val == 1)
3089       return CondResult;
3090     if (TrueResult.Val == 0 && FalseResult.Val == 0)
3091       return NoDiag();
3092     // Rare case where the diagnostics depend on which side is evaluated
3093     // Note that if we get here, CondResult is 0, and at least one of
3094     // TrueResult and FalseResult is non-zero.
3095     if (Exp->getCond()->EvaluateAsInt(Ctx) == 0) {
3096       return FalseResult;
3097     }
3098     return TrueResult;
3099   }
3100   case Expr::CXXDefaultArgExprClass:
3101     return CheckICE(cast<CXXDefaultArgExpr>(E)->getExpr(), Ctx);
3102   case Expr::ChooseExprClass: {
3103     return CheckICE(cast<ChooseExpr>(E)->getChosenSubExpr(Ctx), Ctx);
3104   }
3105   }
3106
3107   // Silence a GCC warning
3108   return ICEDiag(2, E->getLocStart());
3109 }
3110
3111 bool Expr::isIntegerConstantExpr(llvm::APSInt &Result, ASTContext &Ctx,
3112                                  SourceLocation *Loc, bool isEvaluated) const {
3113   ICEDiag d = CheckICE(this, Ctx);
3114   if (d.Val != 0) {
3115     if (Loc) *Loc = d.Loc;
3116     return false;
3117   }
3118   EvalResult EvalResult;
3119   if (!Evaluate(EvalResult, Ctx))
3120     llvm_unreachable("ICE cannot be evaluated!");
3121   assert(!EvalResult.HasSideEffects && "ICE with side effects!");
3122   assert(EvalResult.Val.isInt() && "ICE that isn't integer!");
3123   Result = EvalResult.Val.getInt();
3124   return true;
3125 }