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