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/ASTDiagnostic.h"
  20 #include "clang/Basic/Builtins.h"
  21 #include "clang/Basic/TargetInfo.h"
  22 #include "llvm/ADT/SmallString.h"
  23 #include <cstring>
  24
  25 using namespace clang;
  26 using llvm::APSInt;
  27 using llvm::APFloat;
  28
  29 /// EvalInfo - This is a private struct used by the evaluator to capture
  30 /// information about a subexpression as it is folded.  It retains information
  31 /// about the AST context, but also maintains information about the folded
  32 /// expression.
  33 ///
  34 /// If an expression could be evaluated, it is still possible it is not a C
  35 /// "integer constant expression" or constant expression.  If not, this struct
  36 /// captures information about how and why not.
  37 ///
  38 /// One bit of information passed *into* the request for constant folding
  39 /// indicates whether the subexpression is "evaluated" or not according to C
  40 /// rules.  For example, the RHS of (0 && foo()) is not evaluated.  We can
  41 /// evaluate the expression regardless of what the RHS is, but C only allows
  42 /// certain things in certain situations.
  43 struct EvalInfo {
  44   ASTContext &Ctx;
  45
  46   /// EvalResult - Contains information about the evaluation.
  47   Expr::EvalResult &EvalResult;
  48
  49   /// AnyLValue - Stack based LValue results are not discarded.
  50   bool AnyLValue;
  51
  52   EvalInfo(ASTContext &ctx, Expr::EvalResult& evalresult,
  53            bool anylvalue = false)
  54     : Ctx(ctx), EvalResult(evalresult), AnyLValue(anylvalue) {}
  55 };
  56
  57
  58 static bool EvaluateLValue(const Expr *E, APValue &Result, EvalInfo &Info);
  59 static bool EvaluatePointer(const Expr *E, APValue &Result, EvalInfo &Info);
  60 static bool EvaluateInteger(const Expr *E, APSInt  &Result, EvalInfo &Info);
  61 static bool EvaluateIntegerOrLValue(const Expr *E, APValue  &Result,
  62                                     EvalInfo &Info);
  63 static bool EvaluateFloat(const Expr *E, APFloat &Result, EvalInfo &Info);
  64 static bool EvaluateComplex(const Expr *E, APValue &Result, EvalInfo &Info);
  65
  66 //===----------------------------------------------------------------------===//
  67 // Misc utilities
  68 //===----------------------------------------------------------------------===//
  69
  70 static bool EvalPointerValueAsBool(APValue& Value, bool& Result) {
  71   // FIXME: Is this accurate for all kinds of bases?  If not, what would
  72   // the check look like?
  73   Result = Value.getLValueBase() || !Value.getLValueOffset().isZero();
  74   return true;
  75 }
  76
  77 static bool HandleConversionToBool(const Expr* E, bool& Result,
  78                                    EvalInfo &Info) {
  79   if (E->getType()->isIntegralType()) {
  80     APSInt IntResult;
  81     if (!EvaluateInteger(E, IntResult, Info))
  82       return false;
  83     Result = IntResult != 0;
  84     return true;
  85   } else if (E->getType()->isRealFloatingType()) {
  86     APFloat FloatResult(0.0);
  87     if (!EvaluateFloat(E, FloatResult, Info))
  88       return false;
  89     Result = !FloatResult.isZero();
  90     return true;
  91   } else if (E->getType()->hasPointerRepresentation()) {
  92     APValue PointerResult;
  93     if (!EvaluatePointer(E, PointerResult, Info))
  94       return false;
  95     return EvalPointerValueAsBool(PointerResult, Result);
  96   } else if (E->getType()->isAnyComplexType()) {
  97     APValue ComplexResult;
  98     if (!EvaluateComplex(E, ComplexResult, Info))
  99       return false;
 100     if (ComplexResult.isComplexFloat()) {
 101       Result = !ComplexResult.getComplexFloatReal().isZero() ||
 102                !ComplexResult.getComplexFloatImag().isZero();
 103     } else {
 104       Result = ComplexResult.getComplexIntReal().getBoolValue() ||
 105                ComplexResult.getComplexIntImag().getBoolValue();
 106     }
 107     return true;
 108   }
 109
 110   return false;
 111 }
 112
 113 static APSInt HandleFloatToIntCast(QualType DestType, QualType SrcType,
 114                                    APFloat &Value, ASTContext &Ctx) {
 115   unsigned DestWidth = Ctx.getIntWidth(DestType);
 116   // Determine whether we are converting to unsigned or signed.
 117   bool DestSigned = DestType->isSignedIntegerType();
 118
 119   // FIXME: Warning for overflow.
 120   uint64_t Space[4];
 121   bool ignored;
 122   (void)Value.convertToInteger(Space, DestWidth, DestSigned,
 123                                llvm::APFloat::rmTowardZero, &ignored);
 124   return APSInt(llvm::APInt(DestWidth, 4, Space), !DestSigned);
 125 }
 126
 127 static APFloat HandleFloatToFloatCast(QualType DestType, QualType SrcType,
 128                                       APFloat &Value, ASTContext &Ctx) {
 129   bool ignored;
 130   APFloat Result = Value;
 131   Result.convert(Ctx.getFloatTypeSemantics(DestType),
 132                  APFloat::rmNearestTiesToEven, &ignored);
 133   return Result;
 134 }
 135
 136 static APSInt HandleIntToIntCast(QualType DestType, QualType SrcType,
 137                                  APSInt &Value, ASTContext &Ctx) {
 138   unsigned DestWidth = Ctx.getIntWidth(DestType);
 139   APSInt Result = Value;
 140   // Figure out if this is a truncate, extend or noop cast.
 141   // If the input is signed, do a sign extend, noop, or truncate.
 142   Result.extOrTrunc(DestWidth);
 143   Result.setIsUnsigned(DestType->isUnsignedIntegerType());
 144   return Result;
 145 }
 146
 147 static APFloat HandleIntToFloatCast(QualType DestType, QualType SrcType,
 148                                     APSInt &Value, ASTContext &Ctx) {
 149
 150   APFloat Result(Ctx.getFloatTypeSemantics(DestType), 1);
 151   Result.convertFromAPInt(Value, Value.isSigned(),
 152                           APFloat::rmNearestTiesToEven);
 153   return Result;
 154 }
 155
 156 namespace {
 157 class HasSideEffect
 158   : public StmtVisitor<HasSideEffect, bool> {
 159   EvalInfo &Info;
 160 public:
 161
 162   HasSideEffect(EvalInfo &info) : Info(info) {}
 163
 164   // Unhandled nodes conservatively default to having side effects.
 165   bool VisitStmt(Stmt *S) {
 166     return true;
 167   }
 168
 169   bool VisitParenExpr(ParenExpr *E) { return Visit(E->getSubExpr()); }
 170   bool VisitDeclRefExpr(DeclRefExpr *E) {
 171     if (Info.Ctx.getCanonicalType(E->getType()).isVolatileQualified())
 172       return true;
 173     return false;
 174   }
 175   // We don't want to evaluate BlockExprs multiple times, as they generate
 176   // a ton of code.
 177   bool VisitBlockExpr(BlockExpr *E) { return true; }
 178   bool VisitPredefinedExpr(PredefinedExpr *E) { return false; }
 179   bool VisitCompoundLiteralExpr(CompoundLiteralExpr *E)
 180     { return Visit(E->getInitializer()); }
 181   bool VisitMemberExpr(MemberExpr *E) { return Visit(E->getBase()); }
 182   bool VisitIntegerLiteral(IntegerLiteral *E) { return false; }
 183   bool VisitFloatingLiteral(FloatingLiteral *E) { return false; }
 184   bool VisitStringLiteral(StringLiteral *E) { return false; }
 185   bool VisitCharacterLiteral(CharacterLiteral *E) { return false; }
 186   bool VisitSizeOfAlignOfExpr(SizeOfAlignOfExpr *E) { return false; }
 187   bool VisitArraySubscriptExpr(ArraySubscriptExpr *E)
 188     { return Visit(E->getLHS()) || Visit(E->getRHS()); }
 189   bool VisitChooseExpr(ChooseExpr *E)
 190     { return Visit(E->getChosenSubExpr(Info.Ctx)); }
 191   bool VisitCastExpr(CastExpr *E) { return Visit(E->getSubExpr()); }
 192   bool VisitBinAssign(BinaryOperator *E) { return true; }
 193   bool VisitCompoundAssignOperator(BinaryOperator *E) { return true; }
 194   bool VisitBinaryOperator(BinaryOperator *E)
 195   { return Visit(E->getLHS()) || Visit(E->getRHS()); }
 196   bool VisitUnaryPreInc(UnaryOperator *E) { return true; }
 197   bool VisitUnaryPostInc(UnaryOperator *E) { return true; }
 198   bool VisitUnaryPreDec(UnaryOperator *E) { return true; }
 199   bool VisitUnaryPostDec(UnaryOperator *E) { return true; }
 200   bool VisitUnaryDeref(UnaryOperator *E) {
 201     if (Info.Ctx.getCanonicalType(E->getType()).isVolatileQualified())
 202       return true;
 203     return Visit(E->getSubExpr());
 204   }
 205   bool VisitUnaryOperator(UnaryOperator *E) { return Visit(E->getSubExpr()); }
 206 };
 207
 208 } // end anonymous namespace
 209
 210 //===----------------------------------------------------------------------===//
 211 // LValue Evaluation
 212 //===----------------------------------------------------------------------===//
 213 namespace {
 214 class LValueExprEvaluator
 215   : public StmtVisitor<LValueExprEvaluator, APValue> {
 216   EvalInfo &Info;
 217 public:
 218
 219   LValueExprEvaluator(EvalInfo &info) : Info(info) {}
 220
 221   APValue VisitStmt(Stmt *S) {
 222     return APValue();
 223   }
 224
 225   APValue VisitParenExpr(ParenExpr *E) { return Visit(E->getSubExpr()); }
 226   APValue VisitDeclRefExpr(DeclRefExpr *E);
 227   APValue VisitPredefinedExpr(PredefinedExpr *E) { return APValue(E); }
 228   APValue VisitCompoundLiteralExpr(CompoundLiteralExpr *E);
 229   APValue VisitMemberExpr(MemberExpr *E);
 230   APValue VisitStringLiteral(StringLiteral *E) { return APValue(E); }
 231   APValue VisitObjCEncodeExpr(ObjCEncodeExpr *E) { return APValue(E); }
 232   APValue VisitArraySubscriptExpr(ArraySubscriptExpr *E);
 233   APValue VisitUnaryDeref(UnaryOperator *E);
 234   APValue VisitUnaryExtension(const UnaryOperator *E)
 235     { return Visit(E->getSubExpr()); }
 236   APValue VisitChooseExpr(const ChooseExpr *E)
 237     { return Visit(E->getChosenSubExpr(Info.Ctx)); }
 238
 239   APValue VisitCastExpr(CastExpr *E) {
 240     switch (E->getCastKind()) {
 241     default:
 242       return APValue();
 243
 244     case CastExpr::CK_NoOp:
 245       return Visit(E->getSubExpr());
 246     }
 247   }
 248   // FIXME: Missing: __real__, __imag__
 249 };
 250 } // end anonymous namespace
 251
 252 static bool EvaluateLValue(const Expr* E, APValue& Result, EvalInfo &Info) {
 253   Result = LValueExprEvaluator(Info).Visit(const_cast<Expr*>(E));
 254   return Result.isLValue();
 255 }
 256
 257 APValue LValueExprEvaluator::VisitDeclRefExpr(DeclRefExpr *E) {
 258   if (isa<FunctionDecl>(E->getDecl())) {
 259     return APValue(E);
 260   } else if (VarDecl* VD = dyn_cast<VarDecl>(E->getDecl())) {
 261     if (!Info.AnyLValue && !VD->hasGlobalStorage())
 262       return APValue();
 263     if (!VD->getType()->isReferenceType())
 264       return APValue(E);
 265     // FIXME: Check whether VD might be overridden!
 266     if (const Expr *Init = VD->getAnyInitializer())
 267       return Visit(const_cast<Expr *>(Init));
 268   }
 269
 270   return APValue();
 271 }
 272
 273 APValue LValueExprEvaluator::VisitCompoundLiteralExpr(CompoundLiteralExpr *E) {
 274   if (!Info.AnyLValue && !E->isFileScope())
 275     return APValue();
 276   return APValue(E);
 277 }
 278
 279 APValue LValueExprEvaluator::VisitMemberExpr(MemberExpr *E) {
 280   APValue result;
 281   QualType Ty;
 282   if (E->isArrow()) {
 283     if (!EvaluatePointer(E->getBase(), result, Info))
 284       return APValue();
 285     Ty = E->getBase()->getType()->getAs<PointerType>()->getPointeeType();
 286   } else {
 287     result = Visit(E->getBase());
 288     if (result.isUninit())
 289       return APValue();
 290     Ty = E->getBase()->getType();
 291   }
 292
 293   RecordDecl *RD = Ty->getAs<RecordType>()->getDecl();
 294   const ASTRecordLayout &RL = Info.Ctx.getASTRecordLayout(RD);
 295
 296   FieldDecl *FD = dyn_cast<FieldDecl>(E->getMemberDecl());
 297   if (!FD) // FIXME: deal with other kinds of member expressions
 298     return APValue();
 299
 300   if (FD->getType()->isReferenceType())
 301     return APValue();
 302
 303   // FIXME: This is linear time.
 304   unsigned i = 0;
 305   for (RecordDecl::field_iterator Field = RD->field_begin(),
 306                                FieldEnd = RD->field_end();
 307        Field != FieldEnd; (void)++Field, ++i) {
 308     if (*Field == FD)
 309       break;
 310   }
 311
 312   result.setLValue(result.getLValueBase(),
 313                    result.getLValueOffset() +
 314                        CharUnits::fromQuantity(RL.getFieldOffset(i) / 8));
 315
 316   return result;
 317 }
 318
 319 APValue LValueExprEvaluator::VisitArraySubscriptExpr(ArraySubscriptExpr *E) {
 320   APValue Result;
 321
 322   if (!EvaluatePointer(E->getBase(), Result, Info))
 323     return APValue();
 324
 325   APSInt Index;
 326   if (!EvaluateInteger(E->getIdx(), Index, Info))
 327     return APValue();
 328
 329   CharUnits ElementSize = Info.Ctx.getTypeSizeInChars(E->getType());
 330
 331   CharUnits Offset = Index.getSExtValue() * ElementSize;
 332   Result.setLValue(Result.getLValueBase(),
 333                    Result.getLValueOffset() + Offset);
 334   return Result;
 335 }
 336
 337 APValue LValueExprEvaluator::VisitUnaryDeref(UnaryOperator *E) {
 338   APValue Result;
 339   if (!EvaluatePointer(E->getSubExpr(), Result, Info))
 340     return APValue();
 341   return Result;
 342 }
 343
 344 //===----------------------------------------------------------------------===//
 345 // Pointer Evaluation
 346 //===----------------------------------------------------------------------===//
 347
 348 namespace {
 349 class PointerExprEvaluator
 350   : public StmtVisitor<PointerExprEvaluator, APValue> {
 351   EvalInfo &Info;
 352 public:
 353
 354   PointerExprEvaluator(EvalInfo &info) : Info(info) {}
 355
 356   APValue VisitStmt(Stmt *S) {
 357     return APValue();
 358   }
 359
 360   APValue VisitParenExpr(ParenExpr *E) { return Visit(E->getSubExpr()); }
 361
 362   APValue VisitBinaryOperator(const BinaryOperator *E);
 363   APValue VisitCastExpr(CastExpr* E);
 364   APValue VisitUnaryExtension(const UnaryOperator *E)
 365       { return Visit(E->getSubExpr()); }
 366   APValue VisitUnaryAddrOf(const UnaryOperator *E);
 367   APValue VisitObjCStringLiteral(ObjCStringLiteral *E)
 368       { return APValue(E); }
 369   APValue VisitAddrLabelExpr(AddrLabelExpr *E)
 370       { return APValue(E); }
 371   APValue VisitCallExpr(CallExpr *E);
 372   APValue VisitBlockExpr(BlockExpr *E) {
 373     if (!E->hasBlockDeclRefExprs())
 374       return APValue(E);
 375     return APValue();
 376   }
 377   APValue VisitImplicitValueInitExpr(ImplicitValueInitExpr *E)
 378       { return APValue((Expr*)0); }
 379   APValue VisitConditionalOperator(ConditionalOperator *E);
 380   APValue VisitChooseExpr(ChooseExpr *E)
 381       { return Visit(E->getChosenSubExpr(Info.Ctx)); }
 382   APValue VisitCXXNullPtrLiteralExpr(CXXNullPtrLiteralExpr *E)
 383       { return APValue((Expr*)0); }
 384   // FIXME: Missing: @protocol, @selector
 385 };
 386 } // end anonymous namespace
 387
 388 static bool EvaluatePointer(const Expr* E, APValue& Result, EvalInfo &Info) {
 389   if (!E->getType()->hasPointerRepresentation())
 390     return false;
 391   Result = PointerExprEvaluator(Info).Visit(const_cast<Expr*>(E));
 392   return Result.isLValue();
 393 }
 394
 395 APValue PointerExprEvaluator::VisitBinaryOperator(const BinaryOperator *E) {
 396   if (E->getOpcode() != BinaryOperator::Add &&
 397       E->getOpcode() != BinaryOperator::Sub)
 398     return APValue();
 399
 400   const Expr *PExp = E->getLHS();
 401   const Expr *IExp = E->getRHS();
 402   if (IExp->getType()->isPointerType())
 403     std::swap(PExp, IExp);
 404
 405   APValue ResultLValue;
 406   if (!EvaluatePointer(PExp, ResultLValue, Info))
 407     return APValue();
 408
 409   llvm::APSInt AdditionalOffset(32);
 410   if (!EvaluateInteger(IExp, AdditionalOffset, Info))
 411     return APValue();
 412
 413   QualType PointeeType = PExp->getType()->getAs<PointerType>()->getPointeeType();
 414   CharUnits SizeOfPointee;
 415
 416   // Explicitly handle GNU void* and function pointer arithmetic extensions.
 417   if (PointeeType->isVoidType() || PointeeType->isFunctionType())
 418     SizeOfPointee = CharUnits::One();
 419   else
 420     SizeOfPointee = Info.Ctx.getTypeSizeInChars(PointeeType);
 421
 422   CharUnits Offset = ResultLValue.getLValueOffset();
 423
 424   if (E->getOpcode() == BinaryOperator::Add)
 425     Offset += AdditionalOffset.getLimitedValue() * SizeOfPointee;
 426   else
 427     Offset -= AdditionalOffset.getLimitedValue() * SizeOfPointee;
 428
 429   return APValue(ResultLValue.getLValueBase(), Offset);
 430 }
 431
 432 APValue PointerExprEvaluator::VisitUnaryAddrOf(const UnaryOperator *E) {
 433   APValue result;
 434   if (EvaluateLValue(E->getSubExpr(), result, Info))
 435     return result;
 436   return APValue();
 437 }
 438
 439
 440 APValue PointerExprEvaluator::VisitCastExpr(CastExpr* E) {
 441   Expr* SubExpr = E->getSubExpr();
 442
 443   switch (E->getCastKind()) {
 444   default:
 445     break;
 446
 447   case CastExpr::CK_Unknown: {
 448     // FIXME: The handling for CK_Unknown is ugly/shouldn't be necessary!
 449
 450     // Check for pointer->pointer cast
 451     if (SubExpr->getType()->isPointerType() ||
 452         SubExpr->getType()->isObjCObjectPointerType() ||
 453         SubExpr->getType()->isNullPtrType() ||
 454         SubExpr->getType()->isBlockPointerType())
 455       return Visit(SubExpr);
 456
 457     if (SubExpr->getType()->isIntegralType()) {
 458       APValue Result;
 459       if (!EvaluateIntegerOrLValue(SubExpr, Result, Info))
 460         break;
 461
 462       if (Result.isInt()) {
 463         Result.getInt().extOrTrunc((unsigned)Info.Ctx.getTypeSize(E->getType()));
 464         return APValue(0,
 465                        CharUnits::fromQuantity(Result.getInt().getZExtValue()));
 466       }
 467
 468       // Cast is of an lvalue, no need to change value.
 469       return Result;
 470     }
 471     break;
 472   }
 473
 474   case CastExpr::CK_NoOp:
 475   case CastExpr::CK_BitCast:
 476   case CastExpr::CK_AnyPointerToObjCPointerCast:
 477   case CastExpr::CK_AnyPointerToBlockPointerCast:
 478     return Visit(SubExpr);
 479
 480   case CastExpr::CK_IntegralToPointer: {
 481     APValue Result;
 482     if (!EvaluateIntegerOrLValue(SubExpr, Result, Info))
 483       break;
 484
 485     if (Result.isInt()) {
 486       Result.getInt().extOrTrunc((unsigned)Info.Ctx.getTypeSize(E->getType()));
 487       return APValue(0,
 488                      CharUnits::fromQuantity(Result.getInt().getZExtValue()));
 489     }
 490
 491     // Cast is of an lvalue, no need to change value.
 492     return Result;
 493   }
 494   case CastExpr::CK_ArrayToPointerDecay:
 495   case CastExpr::CK_FunctionToPointerDecay: {
 496     APValue Result;
 497     if (EvaluateLValue(SubExpr, Result, Info))
 498       return Result;
 499     break;
 500   }
 501   }
 502
 503   return APValue();
 504 }
 505
 506 APValue PointerExprEvaluator::VisitCallExpr(CallExpr *E) {
 507   if (E->isBuiltinCall(Info.Ctx) ==
 508         Builtin::BI__builtin___CFStringMakeConstantString ||
 509       E->isBuiltinCall(Info.Ctx) ==
 510         Builtin::BI__builtin___NSStringMakeConstantString)
 511     return APValue(E);
 512   return APValue();
 513 }
 514
 515 APValue PointerExprEvaluator::VisitConditionalOperator(ConditionalOperator *E) {
 516   bool BoolResult;
 517   if (!HandleConversionToBool(E->getCond(), BoolResult, Info))
 518     return APValue();
 519
 520   Expr* EvalExpr = BoolResult ? E->getTrueExpr() : E->getFalseExpr();
 521
 522   APValue Result;
 523   if (EvaluatePointer(EvalExpr, Result, Info))
 524     return Result;
 525   return APValue();
 526 }
 527
 528 //===----------------------------------------------------------------------===//
 529 // Vector Evaluation
 530 //===----------------------------------------------------------------------===//
 531
 532 namespace {
 533   class VectorExprEvaluator
 534   : public StmtVisitor<VectorExprEvaluator, APValue> {
 535     EvalInfo &Info;
 536     APValue GetZeroVector(QualType VecType);
 537   public:
 538
 539     VectorExprEvaluator(EvalInfo &info) : Info(info) {}
 540
 541     APValue VisitStmt(Stmt *S) {
 542       return APValue();
 543     }
 544
 545     APValue VisitParenExpr(ParenExpr *E)
 546         { return Visit(E->getSubExpr()); }
 547     APValue VisitUnaryExtension(const UnaryOperator *E)
 548       { return Visit(E->getSubExpr()); }
 549     APValue VisitUnaryPlus(const UnaryOperator *E)
 550       { return Visit(E->getSubExpr()); }
 551     APValue VisitUnaryReal(const UnaryOperator *E)
 552       { return Visit(E->getSubExpr()); }
 553     APValue VisitImplicitValueInitExpr(const ImplicitValueInitExpr *E)
 554       { return GetZeroVector(E->getType()); }
 555     APValue VisitCastExpr(const CastExpr* E);
 556     APValue VisitCompoundLiteralExpr(const CompoundLiteralExpr *E);
 557     APValue VisitInitListExpr(const InitListExpr *E);
 558     APValue VisitConditionalOperator(const ConditionalOperator *E);
 559     APValue VisitChooseExpr(const ChooseExpr *E)
 560       { return Visit(E->getChosenSubExpr(Info.Ctx)); }
 561     APValue VisitUnaryImag(const UnaryOperator *E);
 562     // FIXME: Missing: unary -, unary ~, binary add/sub/mul/div,
 563     //                 binary comparisons, binary and/or/xor,
 564     //                 shufflevector, ExtVectorElementExpr
 565     //        (Note that these require implementing conversions
 566     //         between vector types.)
 567   };
 568 } // end anonymous namespace
 569
 570 static bool EvaluateVector(const Expr* E, APValue& Result, EvalInfo &Info) {
 571   if (!E->getType()->isVectorType())
 572     return false;
 573   Result = VectorExprEvaluator(Info).Visit(const_cast<Expr*>(E));
 574   return !Result.isUninit();
 575 }
 576
 577 APValue VectorExprEvaluator::VisitCastExpr(const CastExpr* E) {
 578   const VectorType *VTy = E->getType()->getAs<VectorType>();
 579   QualType EltTy = VTy->getElementType();
 580   unsigned NElts = VTy->getNumElements();
 581   unsigned EltWidth = Info.Ctx.getTypeSize(EltTy);
 582
 583   const Expr* SE = E->getSubExpr();
 584   QualType SETy = SE->getType();
 585   APValue Result = APValue();
 586
 587   // Check for vector->vector bitcast and scalar->vector splat.
 588   if (SETy->isVectorType()) {
 589     return this->Visit(const_cast<Expr*>(SE));
 590   } else if (SETy->isIntegerType()) {
 591     APSInt IntResult;
 592     if (!EvaluateInteger(SE, IntResult, Info))
 593       return APValue();
 594     Result = APValue(IntResult);
 595   } else if (SETy->isRealFloatingType()) {
 596     APFloat F(0.0);
 597     if (!EvaluateFloat(SE, F, Info))
 598       return APValue();
 599     Result = APValue(F);
 600   } else
 601     return APValue();
 602
 603   // For casts of a scalar to ExtVector, convert the scalar to the element type
 604   // and splat it to all elements.
 605   if (E->getType()->isExtVectorType()) {
 606     if (EltTy->isIntegerType() && Result.isInt())
 607       Result = APValue(HandleIntToIntCast(EltTy, SETy, Result.getInt(),
 608                                           Info.Ctx));
 609     else if (EltTy->isIntegerType())
 610       Result = APValue(HandleFloatToIntCast(EltTy, SETy, Result.getFloat(),
 611                                             Info.Ctx));
 612     else if (EltTy->isRealFloatingType() && Result.isInt())
 613       Result = APValue(HandleIntToFloatCast(EltTy, SETy, Result.getInt(),
 614                                             Info.Ctx));
 615     else if (EltTy->isRealFloatingType())
 616       Result = APValue(HandleFloatToFloatCast(EltTy, SETy, Result.getFloat(),
 617                                               Info.Ctx));
 618     else
 619       return APValue();
 620
 621     // Splat and create vector APValue.
 622     llvm::SmallVector<APValue, 4> Elts(NElts, Result);
 623     return APValue(&Elts[0], Elts.size());
 624   }
 625
 626   // For casts of a scalar to regular gcc-style vector type, bitcast the scalar
 627   // to the vector. To construct the APValue vector initializer, bitcast the
 628   // initializing value to an APInt, and shift out the bits pertaining to each
 629   // element.
 630   APSInt Init;
 631   Init = Result.isInt() ? Result.getInt() : Result.getFloat().bitcastToAPInt();
 632
 633   llvm::SmallVector<APValue, 4> Elts;
 634   for (unsigned i = 0; i != NElts; ++i) {
 635     APSInt Tmp = Init;
 636     Tmp.extOrTrunc(EltWidth);
 637
 638     if (EltTy->isIntegerType())
 639       Elts.push_back(APValue(Tmp));
 640     else if (EltTy->isRealFloatingType())
 641       Elts.push_back(APValue(APFloat(Tmp)));
 642     else
 643       return APValue();
 644
 645     Init >>= EltWidth;
 646   }
 647   return APValue(&Elts[0], Elts.size());
 648 }
 649
 650 APValue
 651 VectorExprEvaluator::VisitCompoundLiteralExpr(const CompoundLiteralExpr *E) {
 652   return this->Visit(const_cast<Expr*>(E->getInitializer()));
 653 }
 654
 655 APValue
 656 VectorExprEvaluator::VisitInitListExpr(const InitListExpr *E) {
 657   const VectorType *VT = E->getType()->getAs<VectorType>();
 658   unsigned NumInits = E->getNumInits();
 659   unsigned NumElements = VT->getNumElements();
 660
 661   QualType EltTy = VT->getElementType();
 662   llvm::SmallVector<APValue, 4> Elements;
 663
 664   for (unsigned i = 0; i < NumElements; i++) {
 665     if (EltTy->isIntegerType()) {
 666       llvm::APSInt sInt(32);
 667       if (i < NumInits) {
 668         if (!EvaluateInteger(E->getInit(i), sInt, Info))
 669           return APValue();
 670       } else {
 671         sInt = Info.Ctx.MakeIntValue(0, EltTy);
 672       }
 673       Elements.push_back(APValue(sInt));
 674     } else {
 675       llvm::APFloat f(0.0);
 676       if (i < NumInits) {
 677         if (!EvaluateFloat(E->getInit(i), f, Info))
 678           return APValue();
 679       } else {
 680         f = APFloat::getZero(Info.Ctx.getFloatTypeSemantics(EltTy));
 681       }
 682       Elements.push_back(APValue(f));
 683     }
 684   }
 685   return APValue(&Elements[0], Elements.size());
 686 }
 687
 688 APValue
 689 VectorExprEvaluator::GetZeroVector(QualType T) {
 690   const VectorType *VT = T->getAs<VectorType>();
 691   QualType EltTy = VT->getElementType();
 692   APValue ZeroElement;
 693   if (EltTy->isIntegerType())
 694     ZeroElement = APValue(Info.Ctx.MakeIntValue(0, EltTy));
 695   else
 696     ZeroElement =
 697         APValue(APFloat::getZero(Info.Ctx.getFloatTypeSemantics(EltTy)));
 698
 699   llvm::SmallVector<APValue, 4> Elements(VT->getNumElements(), ZeroElement);
 700   return APValue(&Elements[0], Elements.size());
 701 }
 702
 703 APValue VectorExprEvaluator::VisitConditionalOperator(const ConditionalOperator *E) {
 704   bool BoolResult;
 705   if (!HandleConversionToBool(E->getCond(), BoolResult, Info))
 706     return APValue();
 707
 708   Expr* EvalExpr = BoolResult ? E->getTrueExpr() : E->getFalseExpr();
 709
 710   APValue Result;
 711   if (EvaluateVector(EvalExpr, Result, Info))
 712     return Result;
 713   return APValue();
 714 }
 715
 716 APValue VectorExprEvaluator::VisitUnaryImag(const UnaryOperator *E) {
 717   if (!E->getSubExpr()->isEvaluatable(Info.Ctx))
 718     Info.EvalResult.HasSideEffects = true;
 719   return GetZeroVector(E->getType());
 720 }
 721
 722 //===----------------------------------------------------------------------===//
 723 // Integer Evaluation
 724 //===----------------------------------------------------------------------===//
 725
 726 namespace {
 727 class IntExprEvaluator
 728   : public StmtVisitor<IntExprEvaluator, bool> {
 729   EvalInfo &Info;
 730   APValue &Result;
 731 public:
 732   IntExprEvaluator(EvalInfo &info, APValue &result)
 733     : Info(info), Result(result) {}
 734
 735   bool Success(const llvm::APSInt &SI, const Expr *E) {
 736     assert(E->getType()->isIntegralType() && "Invalid evaluation result.");
 737     assert(SI.isSigned() == E->getType()->isSignedIntegerType() &&
 738            "Invalid evaluation result.");
 739     assert(SI.getBitWidth() == Info.Ctx.getIntWidth(E->getType()) &&
 740            "Invalid evaluation result.");
 741     Result = APValue(SI);
 742     return true;
 743   }
 744
 745   bool Success(const llvm::APInt &I, const Expr *E) {
 746     assert(E->getType()->isIntegralType() && "Invalid evaluation result.");
 747     assert(I.getBitWidth() == Info.Ctx.getIntWidth(E->getType()) &&
 748            "Invalid evaluation result.");
 749     Result = APValue(APSInt(I));
 750     Result.getInt().setIsUnsigned(E->getType()->isUnsignedIntegerType());
 751     return true;
 752   }
 753
 754   bool Success(uint64_t Value, const Expr *E) {
 755     assert(E->getType()->isIntegralType() && "Invalid evaluation result.");
 756     Result = APValue(Info.Ctx.MakeIntValue(Value, E->getType()));
 757     return true;
 758   }
 759
 760   bool Error(SourceLocation L, diag::kind D, const Expr *E) {
 761     // Take the first error.
 762     if (Info.EvalResult.Diag == 0) {
 763       Info.EvalResult.DiagLoc = L;
 764       Info.EvalResult.Diag = D;
 765       Info.EvalResult.DiagExpr = E;
 766     }
 767     return false;
 768   }
 769
 770   //===--------------------------------------------------------------------===//
 771   //                            Visitor Methods
 772   //===--------------------------------------------------------------------===//
 773
 774   bool VisitStmt(Stmt *) {
 775     assert(0 && "This should be called on integers, stmts are not integers");
 776     return false;
 777   }
 778
 779   bool VisitExpr(Expr *E) {
 780     return Error(E->getLocStart(), diag::note_invalid_subexpr_in_ice, E);
 781   }
 782
 783   bool VisitParenExpr(ParenExpr *E) { return Visit(E->getSubExpr()); }
 784
 785   bool VisitIntegerLiteral(const IntegerLiteral *E) {
 786     return Success(E->getValue(), E);
 787   }
 788   bool VisitCharacterLiteral(const CharacterLiteral *E) {
 789     return Success(E->getValue(), E);
 790   }
 791   bool VisitTypesCompatibleExpr(const TypesCompatibleExpr *E) {
 792     // Per gcc docs "this built-in function ignores top level
 793     // qualifiers".  We need to use the canonical version to properly
 794     // be able to strip CRV qualifiers from the type.
 795     QualType T0 = Info.Ctx.getCanonicalType(E->getArgType1());
 796     QualType T1 = Info.Ctx.getCanonicalType(E->getArgType2());
 797     return Success(Info.Ctx.typesAreCompatible(T0.getUnqualifiedType(),
 798                                                T1.getUnqualifiedType()),
 799                    E);
 800   }
 801
 802   bool CheckReferencedDecl(const Expr *E, const Decl *D);
 803   bool VisitDeclRefExpr(const DeclRefExpr *E) {
 804     return CheckReferencedDecl(E, E->getDecl());
 805   }
 806   bool VisitMemberExpr(const MemberExpr *E) {
 807     if (CheckReferencedDecl(E, E->getMemberDecl())) {
 808       // Conservatively assume a MemberExpr will have side-effects
 809       Info.EvalResult.HasSideEffects = true;
 810       return true;
 811     }
 812     return false;
 813   }
 814
 815   bool VisitCallExpr(CallExpr *E);
 816   bool VisitBinaryOperator(const BinaryOperator *E);
 817   bool VisitUnaryOperator(const UnaryOperator *E);
 818   bool VisitConditionalOperator(const ConditionalOperator *E);
 819
 820   bool VisitCastExpr(CastExpr* E);
 821   bool VisitSizeOfAlignOfExpr(const SizeOfAlignOfExpr *E);
 822
 823   bool VisitCXXBoolLiteralExpr(const CXXBoolLiteralExpr *E) {
 824     return Success(E->getValue(), E);
 825   }
 826
 827   bool VisitGNUNullExpr(const GNUNullExpr *E) {
 828     return Success(0, E);
 829   }
 830
 831   bool VisitCXXZeroInitValueExpr(const CXXZeroInitValueExpr *E) {
 832     return Success(0, E);
 833   }
 834
 835   bool VisitImplicitValueInitExpr(const ImplicitValueInitExpr *E) {
 836     return Success(0, E);
 837   }
 838
 839   bool VisitUnaryTypeTraitExpr(const UnaryTypeTraitExpr *E) {
 840     return Success(E->EvaluateTrait(Info.Ctx), E);
 841   }
 842
 843   bool VisitChooseExpr(const ChooseExpr *E) {
 844     return Visit(E->getChosenSubExpr(Info.Ctx));
 845   }
 846
 847   bool VisitUnaryReal(const UnaryOperator *E);
 848   bool VisitUnaryImag(const UnaryOperator *E);
 849
 850 private:
 851   CharUnits GetAlignOfExpr(const Expr *E);
 852   CharUnits GetAlignOfType(QualType T);
 853   // FIXME: Missing: array subscript of vector, member of vector
 854 };
 855 } // end anonymous namespace
 856
 857 static bool EvaluateIntegerOrLValue(const Expr* E, APValue &Result, EvalInfo &Info) {
 858   if (!E->getType()->isIntegralType())
 859     return false;
 860
 861   return IntExprEvaluator(Info, Result).Visit(const_cast<Expr*>(E));
 862 }
 863
 864 static bool EvaluateInteger(const Expr* E, APSInt &Result, EvalInfo &Info) {
 865   APValue Val;
 866   if (!EvaluateIntegerOrLValue(E, Val, Info) || !Val.isInt())
 867     return false;
 868   Result = Val.getInt();
 869   return true;
 870 }
 871
 872 bool IntExprEvaluator::CheckReferencedDecl(const Expr* E, const Decl* D) {
 873   // Enums are integer constant exprs.
 874   if (const EnumConstantDecl *ECD = dyn_cast<EnumConstantDecl>(D))
 875     return Success(ECD->getInitVal(), E);
 876
 877   // In C++, const, non-volatile integers initialized with ICEs are ICEs.
 878   // In C, they can also be folded, although they are not ICEs.
 879   if (Info.Ctx.getCanonicalType(E->getType()).getCVRQualifiers()
 880                                                         == Qualifiers::Const) {
 881
 882     if (isa<ParmVarDecl>(D))
 883       return Error(E->getLocStart(), diag::note_invalid_subexpr_in_ice, E);
 884
 885     if (const VarDecl *VD = dyn_cast<VarDecl>(D)) {
 886       if (const Expr *Init = VD->getAnyInitializer()) {
 887         if (APValue *V = VD->getEvaluatedValue()) {
 888           if (V->isInt())
 889             return Success(V->getInt(), E);
 890           return Error(E->getLocStart(), diag::note_invalid_subexpr_in_ice, E);
 891         }
 892
 893         if (VD->isEvaluatingValue())
 894           return Error(E->getLocStart(), diag::note_invalid_subexpr_in_ice, E);
 895
 896         VD->setEvaluatingValue();
 897
 898         if (Visit(const_cast<Expr*>(Init))) {
 899           // Cache the evaluated value in the variable declaration.
 900           VD->setEvaluatedValue(Result);
 901           return true;
 902         }
 903
 904         VD->setEvaluatedValue(APValue());
 905         return false;
 906       }
 907     }
 908   }
 909
 910   // Otherwise, random variable references are not constants.
 911   return Error(E->getLocStart(), diag::note_invalid_subexpr_in_ice, E);
 912 }
 913
 914 /// EvaluateBuiltinClassifyType - Evaluate __builtin_classify_type the same way
 915 /// as GCC.
 916 static int EvaluateBuiltinClassifyType(const CallExpr *E) {
 917   // The following enum mimics the values returned by GCC.
 918   // FIXME: Does GCC differ between lvalue and rvalue references here?
 919   enum gcc_type_class {
 920     no_type_class = -1,
 921     void_type_class, integer_type_class, char_type_class,
 922     enumeral_type_class, boolean_type_class,
 923     pointer_type_class, reference_type_class, offset_type_class,
 924     real_type_class, complex_type_class,
 925     function_type_class, method_type_class,
 926     record_type_class, union_type_class,
 927     array_type_class, string_type_class,
 928     lang_type_class
 929   };
 930
 931   // If no argument was supplied, default to "no_type_class". This isn't
 932   // ideal, however it is what gcc does.
 933   if (E->getNumArgs() == 0)
 934     return no_type_class;
 935
 936   QualType ArgTy = E->getArg(0)->getType();
 937   if (ArgTy->isVoidType())
 938     return void_type_class;
 939   else if (ArgTy->isEnumeralType())
 940     return enumeral_type_class;
 941   else if (ArgTy->isBooleanType())
 942     return boolean_type_class;
 943   else if (ArgTy->isCharType())
 944     return string_type_class; // gcc doesn't appear to use char_type_class
 945   else if (ArgTy->isIntegerType())
 946     return integer_type_class;
 947   else if (ArgTy->isPointerType())
 948     return pointer_type_class;
 949   else if (ArgTy->isReferenceType())
 950     return reference_type_class;
 951   else if (ArgTy->isRealType())
 952     return real_type_class;
 953   else if (ArgTy->isComplexType())
 954     return complex_type_class;
 955   else if (ArgTy->isFunctionType())
 956     return function_type_class;
 957   else if (ArgTy->isStructureType())
 958     return record_type_class;
 959   else if (ArgTy->isUnionType())
 960     return union_type_class;
 961   else if (ArgTy->isArrayType())
 962     return array_type_class;
 963   else if (ArgTy->isUnionType())
 964     return union_type_class;
 965   else  // FIXME: offset_type_class, method_type_class, & lang_type_class?
 966     assert(0 && "CallExpr::isBuiltinClassifyType(): unimplemented type");
 967   return -1;
 968 }
 969
 970 bool IntExprEvaluator::VisitCallExpr(CallExpr *E) {
 971   switch (E->isBuiltinCall(Info.Ctx)) {
 972   default:
 973     return Error(E->getLocStart(), diag::note_invalid_subexpr_in_ice, E);
 974
 975   case Builtin::BI__builtin_object_size: {
 976     const Expr *Arg = E->getArg(0)->IgnoreParens();
 977     Expr::EvalResult Base;
 978
 979     // TODO: Perhaps we should let LLVM lower this?
 980     if (Arg->EvaluateAsAny(Base, Info.Ctx)
 981         && Base.Val.getKind() == APValue::LValue
 982         && !Base.HasSideEffects)
 983       if (const Expr *LVBase = Base.Val.getLValueBase())
 984         if (const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(LVBase)) {
 985           if (const VarDecl *VD = dyn_cast<VarDecl>(DRE->getDecl())) {
 986             if (!VD->getType()->isIncompleteType()
 987                 && VD->getType()->isObjectType()
 988                 && !VD->getType()->isVariablyModifiedType()
 989                 && !VD->getType()->isDependentType()) {
 990               CharUnits Size = Info.Ctx.getTypeSizeInChars(VD->getType());
 991               CharUnits Offset = Base.Val.getLValueOffset();
 992               if (!Offset.isNegative() && Offset <= Size)
 993                 Size -= Offset;
 994               else
 995                 Size = CharUnits::Zero();
 996               return Success(Size.getQuantity(), E);
 997             }
 998           }
 999         }
1000
1001     // If evaluating the argument has side-effects we can't determine
1002     // the size of the object and lower it to unknown now.
1003     if (E->getArg(0)->HasSideEffects(Info.Ctx)) {
1004       if (E->getArg(1)->EvaluateAsInt(Info.Ctx).getZExtValue() <= 1)
1005         return Success(-1ULL, E);
1006       return Success(0, E);
1007     }
1008
1009     return Error(E->getLocStart(), diag::note_invalid_subexpr_in_ice, E);
1010   }
1011
1012   case Builtin::BI__builtin_classify_type:
1013     return Success(EvaluateBuiltinClassifyType(E), E);
1014
1015   case Builtin::BI__builtin_constant_p:
1016     // __builtin_constant_p always has one operand: it returns true if that
1017     // operand can be folded, false otherwise.
1018     return Success(E->getArg(0)->isEvaluatable(Info.Ctx), E);
1019
1020   case Builtin::BI__builtin_eh_return_data_regno: {
1021     int Operand = E->getArg(0)->EvaluateAsInt(Info.Ctx).getZExtValue();
1022     Operand = Info.Ctx.Target.getEHDataRegisterNumber(Operand);
1023     return Success(Operand, E);
1024   }
1025
1026   case Builtin::BI__builtin_expect:
1027     return Visit(E->getArg(0));
1028   }
1029 }
1030
1031 bool IntExprEvaluator::VisitBinaryOperator(const BinaryOperator *E) {
1032   if (E->getOpcode() == BinaryOperator::Comma) {
1033     if (!Visit(E->getRHS()))
1034       return false;
1035
1036     // If we can't evaluate the LHS, it might have side effects;
1037     // conservatively mark it.
1038     if (!E->getLHS()->isEvaluatable(Info.Ctx))
1039       Info.EvalResult.HasSideEffects = true;
1040
1041     return true;
1042   }
1043
1044   if (E->isLogicalOp()) {
1045     // These need to be handled specially because the operands aren't
1046     // necessarily integral
1047     bool lhsResult, rhsResult;
1048
1049     if (HandleConversionToBool(E->getLHS(), lhsResult, Info)) {
1050       // We were able to evaluate the LHS, see if we can get away with not
1051       // evaluating the RHS: 0 && X -> 0, 1 || X -> 1
1052       if (lhsResult == (E->getOpcode() == BinaryOperator::LOr))
1053         return Success(lhsResult, E);
1054
1055       if (HandleConversionToBool(E->getRHS(), rhsResult, Info)) {
1056         if (E->getOpcode() == BinaryOperator::LOr)
1057           return Success(lhsResult || rhsResult, E);
1058         else
1059           return Success(lhsResult && rhsResult, E);
1060       }
1061     } else {
1062       if (HandleConversionToBool(E->getRHS(), rhsResult, Info)) {
1063         // We can't evaluate the LHS; however, sometimes the result
1064         // is determined by the RHS: X && 0 -> 0, X || 1 -> 1.
1065         if (rhsResult == (E->getOpcode() == BinaryOperator::LOr) ||
1066             !rhsResult == (E->getOpcode() == BinaryOperator::LAnd)) {
1067           // Since we weren't able to evaluate the left hand side, it
1068           // must have had side effects.
1069           Info.EvalResult.HasSideEffects = true;
1070
1071           return Success(rhsResult, E);
1072         }
1073       }
1074     }
1075
1076     return false;
1077   }
1078
1079   QualType LHSTy = E->getLHS()->getType();
1080   QualType RHSTy = E->getRHS()->getType();
1081
1082   if (LHSTy->isAnyComplexType()) {
1083     assert(RHSTy->isAnyComplexType() && "Invalid comparison");
1084     APValue LHS, RHS;
1085
1086     if (!EvaluateComplex(E->getLHS(), LHS, Info))
1087       return false;
1088
1089     if (!EvaluateComplex(E->getRHS(), RHS, Info))
1090       return false;
1091
1092     if (LHS.isComplexFloat()) {
1093       APFloat::cmpResult CR_r =
1094         LHS.getComplexFloatReal().compare(RHS.getComplexFloatReal());
1095       APFloat::cmpResult CR_i =
1096         LHS.getComplexFloatImag().compare(RHS.getComplexFloatImag());
1097
1098       if (E->getOpcode() == BinaryOperator::EQ)
1099         return Success((CR_r == APFloat::cmpEqual &&
1100                         CR_i == APFloat::cmpEqual), E);
1101       else {
1102         assert(E->getOpcode() == BinaryOperator::NE &&
1103                "Invalid complex comparison.");
1104         return Success(((CR_r == APFloat::cmpGreaterThan ||
1105                          CR_r == APFloat::cmpLessThan) &&
1106                         (CR_i == APFloat::cmpGreaterThan ||
1107                          CR_i == APFloat::cmpLessThan)), E);
1108       }
1109     } else {
1110       if (E->getOpcode() == BinaryOperator::EQ)
1111         return Success((LHS.getComplexIntReal() == RHS.getComplexIntReal() &&
1112                         LHS.getComplexIntImag() == RHS.getComplexIntImag()), E);
1113       else {
1114         assert(E->getOpcode() == BinaryOperator::NE &&
1115                "Invalid compex comparison.");
1116         return Success((LHS.getComplexIntReal() != RHS.getComplexIntReal() ||
1117                         LHS.getComplexIntImag() != RHS.getComplexIntImag()), E);
1118       }
1119     }
1120   }
1121
1122   if (LHSTy->isRealFloatingType() &&
1123       RHSTy->isRealFloatingType()) {
1124     APFloat RHS(0.0), LHS(0.0);
1125
1126     if (!EvaluateFloat(E->getRHS(), RHS, Info))
1127       return false;
1128
1129     if (!EvaluateFloat(E->getLHS(), LHS, Info))
1130       return false;
1131
1132     APFloat::cmpResult CR = LHS.compare(RHS);
1133
1134     switch (E->getOpcode()) {
1135     default:
1136       assert(0 && "Invalid binary operator!");
1137     case BinaryOperator::LT:
1138       return Success(CR == APFloat::cmpLessThan, E);
1139     case BinaryOperator::GT:
1140       return Success(CR == APFloat::cmpGreaterThan, E);
1141     case BinaryOperator::LE:
1142       return Success(CR == APFloat::cmpLessThan || CR == APFloat::cmpEqual, E);
1143     case BinaryOperator::GE:
1144       return Success(CR == APFloat::cmpGreaterThan || CR == APFloat::cmpEqual,
1145                      E);
1146     case BinaryOperator::EQ:
1147       return Success(CR == APFloat::cmpEqual, E);
1148     case BinaryOperator::NE:
1149       return Success(CR == APFloat::cmpGreaterThan
1150                      || CR == APFloat::cmpLessThan, E);
1151     }
1152   }
1153
1154   if (LHSTy->isPointerType() && RHSTy->isPointerType()) {
1155     if (E->getOpcode() == BinaryOperator::Sub || E->isEqualityOp()) {
1156       APValue LHSValue;
1157       if (!EvaluatePointer(E->getLHS(), LHSValue, Info))
1158         return false;
1159
1160       APValue RHSValue;
1161       if (!EvaluatePointer(E->getRHS(), RHSValue, Info))
1162         return false;
1163
1164       // Reject any bases from the normal codepath; we special-case comparisons
1165       // to null.
1166       if (LHSValue.getLValueBase()) {
1167         if (!E->isEqualityOp())
1168           return false;
1169         if (RHSValue.getLValueBase() || !RHSValue.getLValueOffset().isZero())
1170           return false;
1171         bool bres;
1172         if (!EvalPointerValueAsBool(LHSValue, bres))
1173           return false;
1174         return Success(bres ^ (E->getOpcode() == BinaryOperator::EQ), E);
1175       } else if (RHSValue.getLValueBase()) {
1176         if (!E->isEqualityOp())
1177           return false;
1178         if (LHSValue.getLValueBase() || !LHSValue.getLValueOffset().isZero())
1179           return false;
1180         bool bres;
1181         if (!EvalPointerValueAsBool(RHSValue, bres))
1182           return false;
1183         return Success(bres ^ (E->getOpcode() == BinaryOperator::EQ), E);
1184       }
1185
1186       if (E->getOpcode() == BinaryOperator::Sub) {
1187         const QualType Type = E->getLHS()->getType();
1188         const QualType ElementType = Type->getAs<PointerType>()->getPointeeType();
1189
1190         CharUnits ElementSize = CharUnits::One();
1191         if (!ElementType->isVoidType() && !ElementType->isFunctionType())
1192           ElementSize = Info.Ctx.getTypeSizeInChars(ElementType);
1193
1194         CharUnits Diff = LHSValue.getLValueOffset() -
1195                              RHSValue.getLValueOffset();
1196         return Success(Diff / ElementSize, E);
1197       }
1198       bool Result;
1199       if (E->getOpcode() == BinaryOperator::EQ) {
1200         Result = LHSValue.getLValueOffset() == RHSValue.getLValueOffset();
1201       } else {
1202         Result = LHSValue.getLValueOffset() != RHSValue.getLValueOffset();
1203       }
1204       return Success(Result, E);
1205     }
1206   }
1207   if (!LHSTy->isIntegralType() ||
1208       !RHSTy->isIntegralType()) {
1209     // We can't continue from here for non-integral types, and they
1210     // could potentially confuse the following operations.
1211     return false;
1212   }
1213
1214   // The LHS of a constant expr is always evaluated and needed.
1215   if (!Visit(E->getLHS()))
1216     return false; // error in subexpression.
1217
1218   APValue RHSVal;
1219   if (!EvaluateIntegerOrLValue(E->getRHS(), RHSVal, Info))
1220     return false;
1221
1222   // Handle cases like (unsigned long)&a + 4.
1223   if (E->isAdditiveOp() && Result.isLValue() && RHSVal.isInt()) {
1224     CharUnits Offset = Result.getLValueOffset();
1225     CharUnits AdditionalOffset = CharUnits::fromQuantity(
1226                                      RHSVal.getInt().getZExtValue());
1227     if (E->getOpcode() == BinaryOperator::Add)
1228       Offset += AdditionalOffset;
1229     else
1230       Offset -= AdditionalOffset;
1231     Result = APValue(Result.getLValueBase(), Offset);
1232     return true;
1233   }
1234
1235   // Handle cases like 4 + (unsigned long)&a
1236   if (E->getOpcode() == BinaryOperator::Add &&
1237         RHSVal.isLValue() && Result.isInt()) {
1238     CharUnits Offset = RHSVal.getLValueOffset();
1239     Offset += CharUnits::fromQuantity(Result.getInt().getZExtValue());
1240     Result = APValue(RHSVal.getLValueBase(), Offset);
1241     return true;
1242   }
1243
1244   // All the following cases expect both operands to be an integer
1245   if (!Result.isInt() || !RHSVal.isInt())
1246     return false;
1247
1248   APSInt& RHS = RHSVal.getInt();
1249
1250   switch (E->getOpcode()) {
1251   default:
1252     return Error(E->getOperatorLoc(), diag::note_invalid_subexpr_in_ice, E);
1253   case BinaryOperator::Mul: return Success(Result.getInt() * RHS, E);
1254   case BinaryOperator::Add: return Success(Result.getInt() + RHS, E);
1255   case BinaryOperator::Sub: return Success(Result.getInt() - RHS, E);
1256   case BinaryOperator::And: return Success(Result.getInt() & RHS, E);
1257   case BinaryOperator::Xor: return Success(Result.getInt() ^ RHS, E);
1258   case BinaryOperator::Or:  return Success(Result.getInt() | RHS, E);
1259   case BinaryOperator::Div:
1260     if (RHS == 0)
1261       return Error(E->getOperatorLoc(), diag::note_expr_divide_by_zero, E);
1262     return Success(Result.getInt() / RHS, E);
1263   case BinaryOperator::Rem:
1264     if (RHS == 0)
1265       return Error(E->getOperatorLoc(), diag::note_expr_divide_by_zero, E);
1266     return Success(Result.getInt() % RHS, E);
1267   case BinaryOperator::Shl: {
1268     // FIXME: Warn about out of range shift amounts!
1269     unsigned SA =
1270       (unsigned) RHS.getLimitedValue(Result.getInt().getBitWidth()-1);
1271     return Success(Result.getInt() << SA, E);
1272   }
1273   case BinaryOperator::Shr: {
1274     unsigned SA =
1275       (unsigned) RHS.getLimitedValue(Result.getInt().getBitWidth()-1);
1276     return Success(Result.getInt() >> SA, E);
1277   }
1278
1279   case BinaryOperator::LT: return Success(Result.getInt() < RHS, E);
1280   case BinaryOperator::GT: return Success(Result.getInt() > RHS, E);
1281   case BinaryOperator::LE: return Success(Result.getInt() <= RHS, E);
1282   case BinaryOperator::GE: return Success(Result.getInt() >= RHS, E);
1283   case BinaryOperator::EQ: return Success(Result.getInt() == RHS, E);
1284   case BinaryOperator::NE: return Success(Result.getInt() != RHS, E);
1285   }
1286 }
1287
1288 bool IntExprEvaluator::VisitConditionalOperator(const ConditionalOperator *E) {
1289   bool Cond;
1290   if (!HandleConversionToBool(E->getCond(), Cond, Info))
1291     return false;
1292
1293   return Visit(Cond ? E->getTrueExpr() : E->getFalseExpr());
1294 }
1295
1296 CharUnits IntExprEvaluator::GetAlignOfType(QualType T) {
1297   // C++ [expr.sizeof]p2: "When applied to a reference or a reference type,
1298   //   the result is the size of the referenced type."
1299   // C++ [expr.alignof]p3: "When alignof is applied to a reference type, the
1300   //   result shall be the alignment of the referenced type."
1301   if (const ReferenceType *Ref = T->getAs<ReferenceType>())
1302     T = Ref->getPointeeType();
1303
1304   // Get information about the alignment.
1305   unsigned CharSize = Info.Ctx.Target.getCharWidth();
1306
1307   // __alignof is defined to return the preferred alignment.
1308   return CharUnits::fromQuantity(
1309       Info.Ctx.getPreferredTypeAlign(T.getTypePtr()) / CharSize);
1310 }
1311
1312 CharUnits IntExprEvaluator::GetAlignOfExpr(const Expr *E) {
1313   E = E->IgnoreParens();
1314
1315   // alignof decl is always accepted, even if it doesn't make sense: we default
1316   // to 1 in those cases.
1317   if (const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E))
1318     return Info.Ctx.getDeclAlign(DRE->getDecl(),
1319                                  /*RefAsPointee*/true);
1320
1321   if (const MemberExpr *ME = dyn_cast<MemberExpr>(E))
1322     return Info.Ctx.getDeclAlign(ME->getMemberDecl(),
1323                                  /*RefAsPointee*/true);
1324
1325   return GetAlignOfType(E->getType());
1326 }
1327
1328
1329 /// VisitSizeAlignOfExpr - Evaluate a sizeof or alignof with a result as the
1330 /// expression's type.
1331 bool IntExprEvaluator::VisitSizeOfAlignOfExpr(const SizeOfAlignOfExpr *E) {
1332   // Handle alignof separately.
1333   if (!E->isSizeOf()) {
1334     if (E->isArgumentType())
1335       return Success(GetAlignOfType(E->getArgumentType()).getQuantity(), E);
1336     else
1337       return Success(GetAlignOfExpr(E->getArgumentExpr()).getQuantity(), E);
1338   }
1339
1340   QualType SrcTy = E->getTypeOfArgument();
1341   // C++ [expr.sizeof]p2: "When applied to a reference or a reference type,
1342   //   the result is the size of the referenced type."
1343   // C++ [expr.alignof]p3: "When alignof is applied to a reference type, the
1344   //   result shall be the alignment of the referenced type."
1345   if (const ReferenceType *Ref = SrcTy->getAs<ReferenceType>())
1346     SrcTy = Ref->getPointeeType();
1347
1348   // sizeof(void), __alignof__(void), sizeof(function) = 1 as a gcc
1349   // extension.
1350   if (SrcTy->isVoidType() || SrcTy->isFunctionType())
1351     return Success(1, E);
1352
1353   // sizeof(vla) is not a constantexpr: C99 6.5.3.4p2.
1354   if (!SrcTy->isConstantSizeType())
1355     return false;
1356
1357   // Get information about the size.
1358   return Success(Info.Ctx.getTypeSizeInChars(SrcTy).getQuantity(), E);
1359 }
1360
1361 bool IntExprEvaluator::VisitUnaryOperator(const UnaryOperator *E) {
1362   // Special case unary operators that do not need their subexpression
1363   // evaluated.  offsetof/sizeof/alignof are all special.
1364   if (E->isOffsetOfOp()) {
1365     // The AST for offsetof is defined in such a way that we can just
1366     // directly Evaluate it as an l-value.
1367     APValue LV;
1368     if (!EvaluateLValue(E->getSubExpr(), LV, Info))
1369       return false;
1370     if (LV.getLValueBase())
1371       return false;
1372     return Success(LV.getLValueOffset().getQuantity(), E);
1373   }
1374
1375   if (E->getOpcode() == UnaryOperator::LNot) {
1376     // LNot's operand isn't necessarily an integer, so we handle it specially.
1377     bool bres;
1378     if (!HandleConversionToBool(E->getSubExpr(), bres, Info))
1379       return false;
1380     return Success(!bres, E);
1381   }
1382
1383   // Only handle integral operations...
1384   if (!E->getSubExpr()->getType()->isIntegralType())
1385     return false;
1386
1387   // Get the operand value into 'Result'.
1388   if (!Visit(E->getSubExpr()))
1389     return false;
1390
1391   switch (E->getOpcode()) {
1392   default:
1393     // Address, indirect, pre/post inc/dec, etc are not valid constant exprs.
1394     // See C99 6.6p3.
1395     return Error(E->getOperatorLoc(), diag::note_invalid_subexpr_in_ice, E);
1396   case UnaryOperator::Extension:
1397     // FIXME: Should extension allow i-c-e extension expressions in its scope?
1398     // If so, we could clear the diagnostic ID.
1399     return true;
1400   case UnaryOperator::Plus:
1401     // The result is always just the subexpr.
1402     return true;
1403   case UnaryOperator::Minus:
1404     if (!Result.isInt()) return false;
1405     return Success(-Result.getInt(), E);
1406   case UnaryOperator::Not:
1407     if (!Result.isInt()) return false;
1408     return Success(~Result.getInt(), E);
1409   }
1410 }
1411
1412 /// HandleCast - This is used to evaluate implicit or explicit casts where the
1413 /// result type is integer.
1414 bool IntExprEvaluator::VisitCastExpr(CastExpr *E) {
1415   Expr *SubExpr = E->getSubExpr();
1416   QualType DestType = E->getType();
1417   QualType SrcType = SubExpr->getType();
1418
1419   if (DestType->isBooleanType()) {
1420     bool BoolResult;
1421     if (!HandleConversionToBool(SubExpr, BoolResult, Info))
1422       return false;
1423     return Success(BoolResult, E);
1424   }
1425
1426   // Handle simple integer->integer casts.
1427   if (SrcType->isIntegralType()) {
1428     if (!Visit(SubExpr))
1429       return false;
1430
1431     if (!Result.isInt()) {
1432       // Only allow casts of lvalues if they are lossless.
1433       return Info.Ctx.getTypeSize(DestType) == Info.Ctx.getTypeSize(SrcType);
1434     }
1435
1436     return Success(HandleIntToIntCast(DestType, SrcType,
1437                                       Result.getInt(), Info.Ctx), E);
1438   }
1439
1440   // FIXME: Clean this up!
1441   if (SrcType->isPointerType()) {
1442     APValue LV;
1443     if (!EvaluatePointer(SubExpr, LV, Info))
1444       return false;
1445
1446     if (LV.getLValueBase()) {
1447       // Only allow based lvalue casts if they are lossless.
1448       if (Info.Ctx.getTypeSize(DestType) != Info.Ctx.getTypeSize(SrcType))
1449         return false;
1450
1451       Result = LV;
1452       return true;
1453     }
1454
1455     APSInt AsInt = Info.Ctx.MakeIntValue(LV.getLValueOffset().getQuantity(),
1456                                          SrcType);
1457     return Success(HandleIntToIntCast(DestType, SrcType, AsInt, Info.Ctx), E);
1458   }
1459
1460   if (SrcType->isArrayType() || SrcType->isFunctionType()) {
1461     // This handles double-conversion cases, where there's both
1462     // an l-value promotion and an implicit conversion to int.
1463     APValue LV;
1464     if (!EvaluateLValue(SubExpr, LV, Info))
1465       return false;
1466
1467     if (Info.Ctx.getTypeSize(DestType) != Info.Ctx.getTypeSize(Info.Ctx.VoidPtrTy))
1468       return false;
1469
1470     Result = LV;
1471     return true;
1472   }
1473
1474   if (SrcType->isAnyComplexType()) {
1475     APValue C;
1476     if (!EvaluateComplex(SubExpr, C, Info))
1477       return false;
1478     if (C.isComplexFloat())
1479       return Success(HandleFloatToIntCast(DestType, SrcType,
1480                                           C.getComplexFloatReal(), Info.Ctx),
1481                      E);
1482     else
1483       return Success(HandleIntToIntCast(DestType, SrcType,
1484                                         C.getComplexIntReal(), Info.Ctx), E);
1485   }
1486   // FIXME: Handle vectors
1487
1488   if (!SrcType->isRealFloatingType())
1489     return Error(E->getExprLoc(), diag::note_invalid_subexpr_in_ice, E);
1490
1491   APFloat F(0.0);
1492   if (!EvaluateFloat(SubExpr, F, Info))
1493     return Error(E->getExprLoc(), diag::note_invalid_subexpr_in_ice, E);
1494
1495   return Success(HandleFloatToIntCast(DestType, SrcType, F, Info.Ctx), E);
1496 }
1497
1498 bool IntExprEvaluator::VisitUnaryReal(const UnaryOperator *E) {
1499   if (E->getSubExpr()->getType()->isAnyComplexType()) {
1500     APValue LV;
1501     if (!EvaluateComplex(E->getSubExpr(), LV, Info) || !LV.isComplexInt())
1502       return Error(E->getExprLoc(), diag::note_invalid_subexpr_in_ice, E);
1503     return Success(LV.getComplexIntReal(), E);
1504   }
1505
1506   return Visit(E->getSubExpr());
1507 }
1508
1509 bool IntExprEvaluator::VisitUnaryImag(const UnaryOperator *E) {
1510   if (E->getSubExpr()->getType()->isComplexIntegerType()) {
1511     APValue LV;
1512     if (!EvaluateComplex(E->getSubExpr(), LV, Info) || !LV.isComplexInt())
1513       return Error(E->getExprLoc(), diag::note_invalid_subexpr_in_ice, E);
1514     return Success(LV.getComplexIntImag(), E);
1515   }
1516
1517   if (!E->getSubExpr()->isEvaluatable(Info.Ctx))
1518     Info.EvalResult.HasSideEffects = true;
1519   return Success(0, E);
1520 }
1521
1522 //===----------------------------------------------------------------------===//
1523 // Float Evaluation
1524 //===----------------------------------------------------------------------===//
1525
1526 namespace {
1527 class FloatExprEvaluator
1528   : public StmtVisitor<FloatExprEvaluator, bool> {
1529   EvalInfo &Info;
1530   APFloat &Result;
1531 public:
1532   FloatExprEvaluator(EvalInfo &info, APFloat &result)
1533     : Info(info), Result(result) {}
1534
1535   bool VisitStmt(Stmt *S) {
1536     return false;
1537   }
1538
1539   bool VisitParenExpr(ParenExpr *E) { return Visit(E->getSubExpr()); }
1540   bool VisitCallExpr(const CallExpr *E);
1541
1542   bool VisitUnaryOperator(const UnaryOperator *E);
1543   bool VisitBinaryOperator(const BinaryOperator *E);
1544   bool VisitFloatingLiteral(const FloatingLiteral *E);
1545   bool VisitCastExpr(CastExpr *E);
1546   bool VisitCXXZeroInitValueExpr(CXXZeroInitValueExpr *E);
1547   bool VisitConditionalOperator(ConditionalOperator *E);
1548
1549   bool VisitChooseExpr(const ChooseExpr *E)
1550     { return Visit(E->getChosenSubExpr(Info.Ctx)); }
1551   bool VisitUnaryExtension(const UnaryOperator *E)
1552     { return Visit(E->getSubExpr()); }
1553
1554   // FIXME: Missing: __real__/__imag__, array subscript of vector,
1555   //                 member of vector, ImplicitValueInitExpr
1556 };
1557 } // end anonymous namespace
1558
1559 static bool EvaluateFloat(const Expr* E, APFloat& Result, EvalInfo &Info) {
1560   return FloatExprEvaluator(Info, Result).Visit(const_cast<Expr*>(E));
1561 }
1562
1563 static bool TryEvaluateBuiltinNaN(ASTContext &Context,
1564                                   QualType ResultTy,
1565                                   const Expr *Arg,
1566                                   bool SNaN,
1567                                   llvm::APFloat &Result) {
1568   const StringLiteral *S = dyn_cast<StringLiteral>(Arg->IgnoreParenCasts());
1569   if (!S) return false;
1570
1571   const llvm::fltSemantics &Sem = Context.getFloatTypeSemantics(ResultTy);
1572
1573   llvm::APInt fill;
1574
1575   // Treat empty strings as if they were zero.
1576   if (S->getString().empty())
1577     fill = llvm::APInt(32, 0);
1578   else if (S->getString().getAsInteger(0, fill))
1579     return false;
1580
1581   if (SNaN)
1582     Result = llvm::APFloat::getSNaN(Sem, false, &fill);
1583   else
1584     Result = llvm::APFloat::getQNaN(Sem, false, &fill);
1585   return true;
1586 }
1587
1588 bool FloatExprEvaluator::VisitCallExpr(const CallExpr *E) {
1589   switch (E->isBuiltinCall(Info.Ctx)) {
1590   default: return false;
1591   case Builtin::BI__builtin_huge_val:
1592   case Builtin::BI__builtin_huge_valf:
1593   case Builtin::BI__builtin_huge_vall:
1594   case Builtin::BI__builtin_inf:
1595   case Builtin::BI__builtin_inff:
1596   case Builtin::BI__builtin_infl: {
1597     const llvm::fltSemantics &Sem =
1598       Info.Ctx.getFloatTypeSemantics(E->getType());
1599     Result = llvm::APFloat::getInf(Sem);
1600     return true;
1601   }
1602
1603   case Builtin::BI__builtin_nans:
1604   case Builtin::BI__builtin_nansf:
1605   case Builtin::BI__builtin_nansl:
1606     return TryEvaluateBuiltinNaN(Info.Ctx, E->getType(), E->getArg(0),
1607                                  true, Result);
1608
1609   case Builtin::BI__builtin_nan:
1610   case Builtin::BI__builtin_nanf:
1611   case Builtin::BI__builtin_nanl:
1612     // If this is __builtin_nan() turn this into a nan, otherwise we
1613     // can't constant fold it.
1614     return TryEvaluateBuiltinNaN(Info.Ctx, E->getType(), E->getArg(0),
1615                                  false, Result);
1616
1617   case Builtin::BI__builtin_fabs:
1618   case Builtin::BI__builtin_fabsf:
1619   case Builtin::BI__builtin_fabsl:
1620     if (!EvaluateFloat(E->getArg(0), Result, Info))
1621       return false;
1622
1623     if (Result.isNegative())
1624       Result.changeSign();
1625     return true;
1626
1627   case Builtin::BI__builtin_copysign:
1628   case Builtin::BI__builtin_copysignf:
1629   case Builtin::BI__builtin_copysignl: {
1630     APFloat RHS(0.);
1631     if (!EvaluateFloat(E->getArg(0), Result, Info) ||
1632         !EvaluateFloat(E->getArg(1), RHS, Info))
1633       return false;
1634     Result.copySign(RHS);
1635     return true;
1636   }
1637   }
1638 }
1639
1640 bool FloatExprEvaluator::VisitUnaryOperator(const UnaryOperator *E) {
1641   if (E->getOpcode() == UnaryOperator::Deref)
1642     return false;
1643
1644   if (!EvaluateFloat(E->getSubExpr(), Result, Info))
1645     return false;
1646
1647   switch (E->getOpcode()) {
1648   default: return false;
1649   case UnaryOperator::Plus:
1650     return true;
1651   case UnaryOperator::Minus:
1652     Result.changeSign();
1653     return true;
1654   }
1655 }
1656
1657 bool FloatExprEvaluator::VisitBinaryOperator(const BinaryOperator *E) {
1658   if (E->getOpcode() == BinaryOperator::Comma) {
1659     if (!EvaluateFloat(E->getRHS(), Result, Info))
1660       return false;
1661
1662     // If we can't evaluate the LHS, it might have side effects;
1663     // conservatively mark it.
1664     if (!E->getLHS()->isEvaluatable(Info.Ctx))
1665       Info.EvalResult.HasSideEffects = true;
1666
1667     return true;
1668   }
1669
1670   // FIXME: Diagnostics?  I really don't understand how the warnings
1671   // and errors are supposed to work.
1672   APFloat RHS(0.0);
1673   if (!EvaluateFloat(E->getLHS(), Result, Info))
1674     return false;
1675   if (!EvaluateFloat(E->getRHS(), RHS, Info))
1676     return false;
1677
1678   switch (E->getOpcode()) {
1679   default: return false;
1680   case BinaryOperator::Mul:
1681     Result.multiply(RHS, APFloat::rmNearestTiesToEven);
1682     return true;
1683   case BinaryOperator::Add:
1684     Result.add(RHS, APFloat::rmNearestTiesToEven);
1685     return true;
1686   case BinaryOperator::Sub:
1687     Result.subtract(RHS, APFloat::rmNearestTiesToEven);
1688     return true;
1689   case BinaryOperator::Div:
1690     Result.divide(RHS, APFloat::rmNearestTiesToEven);
1691     return true;
1692   }
1693 }
1694
1695 bool FloatExprEvaluator::VisitFloatingLiteral(const FloatingLiteral *E) {
1696   Result = E->getValue();
1697   return true;
1698 }
1699
1700 bool FloatExprEvaluator::VisitCastExpr(CastExpr *E) {
1701   Expr* SubExpr = E->getSubExpr();
1702
1703   if (SubExpr->getType()->isIntegralType()) {
1704     APSInt IntResult;
1705     if (!EvaluateInteger(SubExpr, IntResult, Info))
1706       return false;
1707     Result = HandleIntToFloatCast(E->getType(), SubExpr->getType(),
1708                                   IntResult, Info.Ctx);
1709     return true;
1710   }
1711   if (SubExpr->getType()->isRealFloatingType()) {
1712     if (!Visit(SubExpr))
1713       return false;
1714     Result = HandleFloatToFloatCast(E->getType(), SubExpr->getType(),
1715                                     Result, Info.Ctx);
1716     return true;
1717   }
1718   // FIXME: Handle complex types
1719
1720   return false;
1721 }
1722
1723 bool FloatExprEvaluator::VisitCXXZeroInitValueExpr(CXXZeroInitValueExpr *E) {
1724   Result = APFloat::getZero(Info.Ctx.getFloatTypeSemantics(E->getType()));
1725   return true;
1726 }
1727
1728 bool FloatExprEvaluator::VisitConditionalOperator(ConditionalOperator *E) {
1729   bool Cond;
1730   if (!HandleConversionToBool(E->getCond(), Cond, Info))
1731     return false;
1732
1733   return Visit(Cond ? E->getTrueExpr() : E->getFalseExpr());
1734 }
1735
1736 //===----------------------------------------------------------------------===//
1737 // Complex Evaluation (for float and integer)
1738 //===----------------------------------------------------------------------===//
1739
1740 namespace {
1741 class ComplexExprEvaluator
1742   : public StmtVisitor<ComplexExprEvaluator, APValue> {
1743   EvalInfo &Info;
1744
1745 public:
1746   ComplexExprEvaluator(EvalInfo &info) : Info(info) {}
1747
1748   //===--------------------------------------------------------------------===//
1749   //                            Visitor Methods
1750   //===--------------------------------------------------------------------===//
1751
1752   APValue VisitStmt(Stmt *S) {
1753     return APValue();
1754   }
1755
1756   APValue VisitParenExpr(ParenExpr *E) { return Visit(E->getSubExpr()); }
1757
1758   APValue VisitImaginaryLiteral(ImaginaryLiteral *E) {
1759     Expr* SubExpr = E->getSubExpr();
1760
1761     if (SubExpr->getType()->isRealFloatingType()) {
1762       APFloat Result(0.0);
1763
1764       if (!EvaluateFloat(SubExpr, Result, Info))
1765         return APValue();
1766
1767       return APValue(APFloat(Result.getSemantics(), APFloat::fcZero, false),
1768                      Result);
1769     } else {
1770       assert(SubExpr->getType()->isIntegerType() &&
1771              "Unexpected imaginary literal.");
1772
1773       llvm::APSInt Result;
1774       if (!EvaluateInteger(SubExpr, Result, Info))
1775         return APValue();
1776
1777       llvm::APSInt Zero(Result.getBitWidth(), !Result.isSigned());
1778       Zero = 0;
1779       return APValue(Zero, Result);
1780     }
1781   }
1782
1783   APValue VisitCastExpr(CastExpr *E) {
1784     Expr* SubExpr = E->getSubExpr();
1785     QualType EltType = E->getType()->getAs<ComplexType>()->getElementType();
1786     QualType SubType = SubExpr->getType();
1787
1788     if (SubType->isRealFloatingType()) {
1789       APFloat Result(0.0);
1790
1791       if (!EvaluateFloat(SubExpr, Result, Info))
1792         return APValue();
1793
1794       if (EltType->isRealFloatingType()) {
1795         Result = HandleFloatToFloatCast(EltType, SubType, Result, Info.Ctx);
1796         return APValue(Result,
1797                        APFloat(Result.getSemantics(), APFloat::fcZero, false));
1798       } else {
1799         llvm::APSInt IResult;
1800         IResult = HandleFloatToIntCast(EltType, SubType, Result, Info.Ctx);
1801         llvm::APSInt Zero(IResult.getBitWidth(), !IResult.isSigned());
1802         Zero = 0;
1803         return APValue(IResult, Zero);
1804       }
1805     } else if (SubType->isIntegerType()) {
1806       APSInt Result;
1807
1808       if (!EvaluateInteger(SubExpr, Result, Info))
1809         return APValue();
1810
1811       if (EltType->isRealFloatingType()) {
1812         APFloat FResult =
1813             HandleIntToFloatCast(EltType, SubType, Result, Info.Ctx);
1814         return APValue(FResult,
1815                        APFloat(FResult.getSemantics(), APFloat::fcZero, false));
1816       } else {
1817         Result = HandleIntToIntCast(EltType, SubType, Result, Info.Ctx);
1818         llvm::APSInt Zero(Result.getBitWidth(), !Result.isSigned());
1819         Zero = 0;
1820         return APValue(Result, Zero);
1821       }
1822     } else if (const ComplexType *CT = SubType->getAs<ComplexType>()) {
1823       APValue Src;
1824
1825       if (!EvaluateComplex(SubExpr, Src, Info))
1826         return APValue();
1827
1828       QualType SrcType = CT->getElementType();
1829
1830       if (Src.isComplexFloat()) {
1831         if (EltType->isRealFloatingType()) {
1832           return APValue(HandleFloatToFloatCast(EltType, SrcType,
1833                                                 Src.getComplexFloatReal(),
1834                                                 Info.Ctx),
1835                          HandleFloatToFloatCast(EltType, SrcType,
1836                                                 Src.getComplexFloatImag(),
1837                                                 Info.Ctx));
1838         } else {
1839           return APValue(HandleFloatToIntCast(EltType, SrcType,
1840                                               Src.getComplexFloatReal(),
1841                                               Info.Ctx),
1842                          HandleFloatToIntCast(EltType, SrcType,
1843                                               Src.getComplexFloatImag(),
1844                                               Info.Ctx));
1845         }
1846       } else {
1847         assert(Src.isComplexInt() && "Invalid evaluate result.");
1848         if (EltType->isRealFloatingType()) {
1849           return APValue(HandleIntToFloatCast(EltType, SrcType,
1850                                               Src.getComplexIntReal(),
1851                                               Info.Ctx),
1852                          HandleIntToFloatCast(EltType, SrcType,
1853                                               Src.getComplexIntImag(),
1854                                               Info.Ctx));
1855         } else {
1856           return APValue(HandleIntToIntCast(EltType, SrcType,
1857                                             Src.getComplexIntReal(),
1858                                             Info.Ctx),
1859                          HandleIntToIntCast(EltType, SrcType,
1860                                             Src.getComplexIntImag(),
1861                                             Info.Ctx));
1862         }
1863       }
1864     }
1865
1866     // FIXME: Handle more casts.
1867     return APValue();
1868   }
1869
1870   APValue VisitBinaryOperator(const BinaryOperator *E);
1871   APValue VisitChooseExpr(const ChooseExpr *E)
1872     { return Visit(E->getChosenSubExpr(Info.Ctx)); }
1873   APValue VisitUnaryExtension(const UnaryOperator *E)
1874     { return Visit(E->getSubExpr()); }
1875   // FIXME Missing: unary +/-/~, binary div, ImplicitValueInitExpr,
1876   //                conditional ?:, comma
1877 };
1878 } // end anonymous namespace
1879
1880 static bool EvaluateComplex(const Expr *E, APValue &Result, EvalInfo &Info) {
1881   Result = ComplexExprEvaluator(Info).Visit(const_cast<Expr*>(E));
1882   assert((!Result.isComplexFloat() ||
1883           (&Result.getComplexFloatReal().getSemantics() ==
1884            &Result.getComplexFloatImag().getSemantics())) &&
1885          "Invalid complex evaluation.");
1886   return Result.isComplexFloat() || Result.isComplexInt();
1887 }
1888
1889 APValue ComplexExprEvaluator::VisitBinaryOperator(const BinaryOperator *E) {
1890   APValue Result, RHS;
1891
1892   if (!EvaluateComplex(E->getLHS(), Result, Info))
1893     return APValue();
1894
1895   if (!EvaluateComplex(E->getRHS(), RHS, Info))
1896     return APValue();
1897
1898   assert(Result.isComplexFloat() == RHS.isComplexFloat() &&
1899          "Invalid operands to binary operator.");
1900   switch (E->getOpcode()) {
1901   default: return APValue();
1902   case BinaryOperator::Add:
1903     if (Result.isComplexFloat()) {
1904       Result.getComplexFloatReal().add(RHS.getComplexFloatReal(),
1905                                        APFloat::rmNearestTiesToEven);
1906       Result.getComplexFloatImag().add(RHS.getComplexFloatImag(),
1907                                        APFloat::rmNearestTiesToEven);
1908     } else {
1909       Result.getComplexIntReal() += RHS.getComplexIntReal();
1910       Result.getComplexIntImag() += RHS.getComplexIntImag();
1911     }
1912     break;
1913   case BinaryOperator::Sub:
1914     if (Result.isComplexFloat()) {
1915       Result.getComplexFloatReal().subtract(RHS.getComplexFloatReal(),
1916                                             APFloat::rmNearestTiesToEven);
1917       Result.getComplexFloatImag().subtract(RHS.getComplexFloatImag(),
1918                                             APFloat::rmNearestTiesToEven);
1919     } else {
1920       Result.getComplexIntReal() -= RHS.getComplexIntReal();
1921       Result.getComplexIntImag() -= RHS.getComplexIntImag();
1922     }
1923     break;
1924   case BinaryOperator::Mul:
1925     if (Result.isComplexFloat()) {
1926       APValue LHS = Result;
1927       APFloat &LHS_r = LHS.getComplexFloatReal();
1928       APFloat &LHS_i = LHS.getComplexFloatImag();
1929       APFloat &RHS_r = RHS.getComplexFloatReal();
1930       APFloat &RHS_i = RHS.getComplexFloatImag();
1931
1932       APFloat Tmp = LHS_r;
1933       Tmp.multiply(RHS_r, APFloat::rmNearestTiesToEven);
1934       Result.getComplexFloatReal() = Tmp;
1935       Tmp = LHS_i;
1936       Tmp.multiply(RHS_i, APFloat::rmNearestTiesToEven);
1937       Result.getComplexFloatReal().subtract(Tmp, APFloat::rmNearestTiesToEven);
1938
1939       Tmp = LHS_r;
1940       Tmp.multiply(RHS_i, APFloat::rmNearestTiesToEven);
1941       Result.getComplexFloatImag() = Tmp;
1942       Tmp = LHS_i;
1943       Tmp.multiply(RHS_r, APFloat::rmNearestTiesToEven);
1944       Result.getComplexFloatImag().add(Tmp, APFloat::rmNearestTiesToEven);
1945     } else {
1946       APValue LHS = Result;
1947       Result.getComplexIntReal() =
1948         (LHS.getComplexIntReal() * RHS.getComplexIntReal() -
1949          LHS.getComplexIntImag() * RHS.getComplexIntImag());
1950       Result.getComplexIntImag() =
1951         (LHS.getComplexIntReal() * RHS.getComplexIntImag() +
1952          LHS.getComplexIntImag() * RHS.getComplexIntReal());
1953     }
1954     break;
1955   }
1956
1957   return Result;
1958 }
1959
1960 //===----------------------------------------------------------------------===//
1961 // Top level Expr::Evaluate method.
1962 //===----------------------------------------------------------------------===//
1963
1964 /// Evaluate - Return true if this is a constant which we can fold using
1965 /// any crazy technique (that has nothing to do with language standards) that
1966 /// we want to.  If this function returns true, it returns the folded constant
1967 /// in Result.
1968 bool Expr::Evaluate(EvalResult &Result, ASTContext &Ctx) const {
1969   EvalInfo Info(Ctx, Result);
1970
1971   if (getType()->isVectorType()) {
1972     if (!EvaluateVector(this, Result.Val, Info))
1973       return false;
1974   } else if (getType()->isIntegerType()) {
1975     if (!IntExprEvaluator(Info, Result.Val).Visit(const_cast<Expr*>(this)))
1976       return false;
1977   } else if (getType()->hasPointerRepresentation()) {
1978     if (!EvaluatePointer(this, Result.Val, Info))
1979       return false;
1980   } else if (getType()->isRealFloatingType()) {
1981     llvm::APFloat f(0.0);
1982     if (!EvaluateFloat(this, f, Info))
1983       return false;
1984
1985     Result.Val = APValue(f);
1986   } else if (getType()->isAnyComplexType()) {
1987     if (!EvaluateComplex(this, Result.Val, Info))
1988       return false;
1989   } else
1990     return false;
1991
1992   return true;
1993 }
1994
1995 bool Expr::EvaluateAsAny(EvalResult &Result, ASTContext &Ctx) const {
1996   EvalInfo Info(Ctx, Result, true);
1997
1998   if (getType()->isVectorType()) {
1999     if (!EvaluateVector(this, Result.Val, Info))
2000       return false;
2001   } else if (getType()->isIntegerType()) {
2002     if (!IntExprEvaluator(Info, Result.Val).Visit(const_cast<Expr*>(this)))
2003       return false;
2004   } else if (getType()->hasPointerRepresentation()) {
2005     if (!EvaluatePointer(this, Result.Val, Info))
2006       return false;
2007   } else if (getType()->isRealFloatingType()) {
2008     llvm::APFloat f(0.0);
2009     if (!EvaluateFloat(this, f, Info))
2010       return false;
2011
2012     Result.Val = APValue(f);
2013   } else if (getType()->isAnyComplexType()) {
2014     if (!EvaluateComplex(this, Result.Val, Info))
2015       return false;
2016   } else
2017     return false;
2018
2019   return true;
2020 }
2021
2022 bool Expr::EvaluateAsBooleanCondition(bool &Result, ASTContext &Ctx) const {
2023   EvalResult Scratch;
2024   EvalInfo Info(Ctx, Scratch);
2025
2026   return HandleConversionToBool(this, Result, Info);
2027 }
2028
2029 bool Expr::EvaluateAsLValue(EvalResult &Result, ASTContext &Ctx) const {
2030   EvalInfo Info(Ctx, Result);
2031
2032   return EvaluateLValue(this, Result.Val, Info) && !Result.HasSideEffects;
2033 }
2034
2035 bool Expr::EvaluateAsAnyLValue(EvalResult &Result, ASTContext &Ctx) const {
2036   EvalInfo Info(Ctx, Result, true);
2037
2038   return EvaluateLValue(this, Result.Val, Info) && !Result.HasSideEffects;
2039 }
2040
2041 /// isEvaluatable - Call Evaluate to see if this expression can be constant
2042 /// folded, but discard the result.
2043 bool Expr::isEvaluatable(ASTContext &Ctx) const {
2044   EvalResult Result;
2045   return Evaluate(Result, Ctx) && !Result.HasSideEffects;
2046 }
2047
2048 bool Expr::HasSideEffects(ASTContext &Ctx) const {
2049   Expr::EvalResult Result;
2050   EvalInfo Info(Ctx, Result);
2051   return HasSideEffect(Info).Visit(const_cast<Expr*>(this));
2052 }
2053
2054 APSInt Expr::EvaluateAsInt(ASTContext &Ctx) const {
2055   EvalResult EvalResult;
2056   bool Result = Evaluate(EvalResult, Ctx);
2057   Result = Result;
2058   assert(Result && "Could not evaluate expression");
2059   assert(EvalResult.Val.isInt() && "Expression did not evaluate to integer");
2060
2061   return EvalResult.Val.getInt();
2062 }