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