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