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