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