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