ExprConstant.cpp revision 204643 
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/ASTDiagnostic.h"
20#include "clang/Basic/Builtins.h"
21#include "clang/Basic/TargetInfo.h"
22#include "llvm/ADT/SmallString.h"
23#include <cstring>
24
25using namespace clang;
26using llvm::APSInt;
27using llvm::APFloat;
28
29/// EvalInfo - This is a private struct used by the evaluator to capture
30/// information about a subexpression as it is folded.  It retains information
31/// about the AST context, but also maintains information about the folded
32/// expression.
33///
34/// If an expression could be evaluated, it is still possible it is not a C
35/// "integer constant expression" or constant expression.  If not, this struct
36/// captures information about how and why not.
37///
38/// One bit of information passed *into* the request for constant folding
39/// indicates whether the subexpression is "evaluated" or not according to C
40/// rules.  For example, the RHS of (0 && foo()) is not evaluated.  We can
41/// evaluate the expression regardless of what the RHS is, but C only allows
42/// certain things in certain situations.
43struct EvalInfo {
44  ASTContext &Ctx;
45
46  /// EvalResult - Contains information about the evaluation.
47  Expr::EvalResult &EvalResult;
48
49  /// AnyLValue - Stack based LValue results are not discarded.
50  bool AnyLValue;
51
52  EvalInfo(ASTContext &ctx, Expr::EvalResult& evalresult,
53           bool anylvalue = false)
54    : Ctx(ctx), EvalResult(evalresult), AnyLValue(anylvalue) {}
55};
56
57
58static bool EvaluateLValue(const Expr *E, APValue &Result, EvalInfo &Info);
59static bool EvaluatePointer(const Expr *E, APValue &Result, EvalInfo &Info);
60static bool EvaluateInteger(const Expr *E, APSInt  &Result, EvalInfo &Info);
61static bool EvaluateIntegerOrLValue(const Expr *E, APValue  &Result,
62                                    EvalInfo &Info);
63static bool EvaluateFloat(const Expr *E, APFloat &Result, EvalInfo &Info);
64static bool EvaluateComplex(const Expr *E, APValue &Result, EvalInfo &Info);
65
66//===----------------------------------------------------------------------===//
67// Misc utilities
68//===----------------------------------------------------------------------===//
69
70static bool EvalPointerValueAsBool(APValue& Value, bool& Result) {
71  // FIXME: Is this accurate for all kinds of bases?  If not, what would
72  // the check look like?
73  Result = Value.getLValueBase() || !Value.getLValueOffset().isZero();
74  return true;
75}
76
77static bool HandleConversionToBool(const Expr* E, bool& Result,
78                                   EvalInfo &Info) {
79  if (E->getType()->isIntegralType()) {
80    APSInt IntResult;
81    if (!EvaluateInteger(E, IntResult, Info))
82      return false;
83    Result = IntResult != 0;
84    return true;
85  } else if (E->getType()->isRealFloatingType()) {
86    APFloat FloatResult(0.0);
87    if (!EvaluateFloat(E, FloatResult, Info))
88      return false;
89    Result = !FloatResult.isZero();
90    return true;
91  } else if (E->getType()->hasPointerRepresentation()) {
92    APValue PointerResult;
93    if (!EvaluatePointer(E, PointerResult, Info))
94      return false;
95    return EvalPointerValueAsBool(PointerResult, Result);
96  } else if (E->getType()->isAnyComplexType()) {
97    APValue ComplexResult;
98    if (!EvaluateComplex(E, ComplexResult, Info))
99      return false;
100    if (ComplexResult.isComplexFloat()) {
101      Result = !ComplexResult.getComplexFloatReal().isZero() ||
102               !ComplexResult.getComplexFloatImag().isZero();
103    } else {
104      Result = ComplexResult.getComplexIntReal().getBoolValue() ||
105               ComplexResult.getComplexIntImag().getBoolValue();
106    }
107    return true;
108  }
109
110  return false;
111}
112
113static APSInt HandleFloatToIntCast(QualType DestType, QualType SrcType,
114                                   APFloat &Value, ASTContext &Ctx) {
115  unsigned DestWidth = Ctx.getIntWidth(DestType);
116  // Determine whether we are converting to unsigned or signed.
117  bool DestSigned = DestType->isSignedIntegerType();
118
119  // FIXME: Warning for overflow.
120  uint64_t Space[4];
121  bool ignored;
122  (void)Value.convertToInteger(Space, DestWidth, DestSigned,
123                               llvm::APFloat::rmTowardZero, &ignored);
124  return APSInt(llvm::APInt(DestWidth, 4, Space), !DestSigned);
125}
126
127static APFloat HandleFloatToFloatCast(QualType DestType, QualType SrcType,
128                                      APFloat &Value, ASTContext &Ctx) {
129  bool ignored;
130  APFloat Result = Value;
131  Result.convert(Ctx.getFloatTypeSemantics(DestType),
132                 APFloat::rmNearestTiesToEven, &ignored);
133  return Result;
134}
135
136static APSInt HandleIntToIntCast(QualType DestType, QualType SrcType,
137                                 APSInt &Value, ASTContext &Ctx) {
138  unsigned DestWidth = Ctx.getIntWidth(DestType);
139  APSInt Result = Value;
140  // Figure out if this is a truncate, extend or noop cast.
141  // If the input is signed, do a sign extend, noop, or truncate.
142  Result.extOrTrunc(DestWidth);
143  Result.setIsUnsigned(DestType->isUnsignedIntegerType());
144  return Result;
145}
146
147static APFloat HandleIntToFloatCast(QualType DestType, QualType SrcType,
148                                    APSInt &Value, ASTContext &Ctx) {
149
150  APFloat Result(Ctx.getFloatTypeSemantics(DestType), 1);
151  Result.convertFromAPInt(Value, Value.isSigned(),
152                          APFloat::rmNearestTiesToEven);
153  return Result;
154}
155
156namespace {
157class HasSideEffect
158  : public StmtVisitor<HasSideEffect, bool> {
159  EvalInfo &Info;
160public:
161
162  HasSideEffect(EvalInfo &info) : Info(info) {}
163
164  // Unhandled nodes conservatively default to having side effects.
165  bool VisitStmt(Stmt *S) {
166    return true;
167  }
168
169  bool VisitParenExpr(ParenExpr *E) { return Visit(E->getSubExpr()); }
170  bool VisitDeclRefExpr(DeclRefExpr *E) {
171    if (Info.Ctx.getCanonicalType(E->getType()).isVolatileQualified())
172      return true;
173    return false;
174  }
175  // We don't want to evaluate BlockExprs multiple times, as they generate
176  // a ton of code.
177  bool VisitBlockExpr(BlockExpr *E) { return true; }
178  bool VisitPredefinedExpr(PredefinedExpr *E) { return false; }
179  bool VisitCompoundLiteralExpr(CompoundLiteralExpr *E)
180    { return Visit(E->getInitializer()); }
181  bool VisitMemberExpr(MemberExpr *E) { return Visit(E->getBase()); }
182  bool VisitIntegerLiteral(IntegerLiteral *E) { return false; }
183  bool VisitFloatingLiteral(FloatingLiteral *E) { return false; }
184  bool VisitStringLiteral(StringLiteral *E) { return false; }
185  bool VisitCharacterLiteral(CharacterLiteral *E) { return false; }
186  bool VisitSizeOfAlignOfExpr(SizeOfAlignOfExpr *E) { return false; }
187  bool VisitArraySubscriptExpr(ArraySubscriptExpr *E)
188    { return Visit(E->getLHS()) || Visit(E->getRHS()); }
189  bool VisitChooseExpr(ChooseExpr *E)
190    { return Visit(E->getChosenSubExpr(Info.Ctx)); }
191  bool VisitCastExpr(CastExpr *E) { return Visit(E->getSubExpr()); }
192  bool VisitBinAssign(BinaryOperator *E) { return true; }
193  bool VisitCompoundAssignOperator(BinaryOperator *E) { return true; }
194  bool VisitBinaryOperator(BinaryOperator *E)
195  { return Visit(E->getLHS()) || Visit(E->getRHS()); }
196  bool VisitUnaryPreInc(UnaryOperator *E) { return true; }
197  bool VisitUnaryPostInc(UnaryOperator *E) { return true; }
198  bool VisitUnaryPreDec(UnaryOperator *E) { return true; }
199  bool VisitUnaryPostDec(UnaryOperator *E) { return true; }
200  bool VisitUnaryDeref(UnaryOperator *E) {
201    if (Info.Ctx.getCanonicalType(E->getType()).isVolatileQualified())
202      return true;
203    return Visit(E->getSubExpr());
204  }
205  bool VisitUnaryOperator(UnaryOperator *E) { return Visit(E->getSubExpr()); }
206};
207
208} // end anonymous namespace
209
210//===----------------------------------------------------------------------===//
211// LValue Evaluation
212//===----------------------------------------------------------------------===//
213namespace {
214class LValueExprEvaluator
215  : public StmtVisitor<LValueExprEvaluator, APValue> {
216  EvalInfo &Info;
217public:
218
219  LValueExprEvaluator(EvalInfo &info) : Info(info) {}
220
221  APValue VisitStmt(Stmt *S) {
222    return APValue();
223  }
224
225  APValue VisitParenExpr(ParenExpr *E) { return Visit(E->getSubExpr()); }
226  APValue VisitDeclRefExpr(DeclRefExpr *E);
227  APValue VisitPredefinedExpr(PredefinedExpr *E) { return APValue(E); }
228  APValue VisitCompoundLiteralExpr(CompoundLiteralExpr *E);
229  APValue VisitMemberExpr(MemberExpr *E);
230  APValue VisitStringLiteral(StringLiteral *E) { return APValue(E); }
231  APValue VisitObjCEncodeExpr(ObjCEncodeExpr *E) { return APValue(E); }
232  APValue VisitArraySubscriptExpr(ArraySubscriptExpr *E);
233  APValue VisitUnaryDeref(UnaryOperator *E);
234  APValue VisitUnaryExtension(const UnaryOperator *E)
235    { return Visit(E->getSubExpr()); }
236  APValue VisitChooseExpr(const ChooseExpr *E)
237    { return Visit(E->getChosenSubExpr(Info.Ctx)); }
238
239  APValue VisitCastExpr(CastExpr *E) {
240    switch (E->getCastKind()) {
241    default:
242      return APValue();
243
244    case CastExpr::CK_NoOp:
245      return Visit(E->getSubExpr());
246    }
247  }
248  // FIXME: Missing: __real__, __imag__
249};
250} // end anonymous namespace
251
252static bool EvaluateLValue(const Expr* E, APValue& Result, EvalInfo &Info) {
253  Result = LValueExprEvaluator(Info).Visit(const_cast<Expr*>(E));
254  return Result.isLValue();
255}
256
257APValue LValueExprEvaluator::VisitDeclRefExpr(DeclRefExpr *E) {
258  if (isa<FunctionDecl>(E->getDecl())) {
259    return APValue(E);
260  } else if (VarDecl* VD = dyn_cast<VarDecl>(E->getDecl())) {
261    if (!Info.AnyLValue && !VD->hasGlobalStorage())
262      return APValue();
263    if (!VD->getType()->isReferenceType())
264      return APValue(E);
265    // FIXME: Check whether VD might be overridden!
266    if (const Expr *Init = VD->getAnyInitializer())
267      return Visit(const_cast<Expr *>(Init));
268  }
269
270  return APValue();
271}
272
273APValue LValueExprEvaluator::VisitCompoundLiteralExpr(CompoundLiteralExpr *E) {
274  if (!Info.AnyLValue && !E->isFileScope())
275    return APValue();
276  return APValue(E);
277}
278
279APValue LValueExprEvaluator::VisitMemberExpr(MemberExpr *E) {
280  APValue result;
281  QualType Ty;
282  if (E->isArrow()) {
283    if (!EvaluatePointer(E->getBase(), result, Info))
284      return APValue();
285    Ty = E->getBase()->getType()->getAs<PointerType>()->getPointeeType();
286  } else {
287    result = Visit(E->getBase());
288    if (result.isUninit())
289      return APValue();
290    Ty = E->getBase()->getType();
291  }
292
293  RecordDecl *RD = Ty->getAs<RecordType>()->getDecl();
294  const ASTRecordLayout &RL = Info.Ctx.getASTRecordLayout(RD);
295
296  FieldDecl *FD = dyn_cast<FieldDecl>(E->getMemberDecl());
297  if (!FD) // FIXME: deal with other kinds of member expressions
298    return APValue();
299
300  if (FD->getType()->isReferenceType())
301    return APValue();
302
303  // FIXME: This is linear time.
304  unsigned i = 0;
305  for (RecordDecl::field_iterator Field = RD->field_begin(),
306                               FieldEnd = RD->field_end();
307       Field != FieldEnd; (void)++Field, ++i) {
308    if (*Field == FD)
309      break;
310  }
311
312  result.setLValue(result.getLValueBase(),
313                   result.getLValueOffset() +
314                       CharUnits::fromQuantity(RL.getFieldOffset(i) / 8));
315
316  return result;
317}
318
319APValue LValueExprEvaluator::VisitArraySubscriptExpr(ArraySubscriptExpr *E) {
320  APValue Result;
321
322  if (!EvaluatePointer(E->getBase(), Result, Info))
323    return APValue();
324
325  APSInt Index;
326  if (!EvaluateInteger(E->getIdx(), Index, Info))
327    return APValue();
328
329  CharUnits ElementSize = Info.Ctx.getTypeSizeInChars(E->getType());
330
331  CharUnits Offset = Index.getSExtValue() * ElementSize;
332  Result.setLValue(Result.getLValueBase(),
333                   Result.getLValueOffset() + Offset);
334  return Result;
335}
336
337APValue LValueExprEvaluator::VisitUnaryDeref(UnaryOperator *E) {
338  APValue Result;
339  if (!EvaluatePointer(E->getSubExpr(), Result, Info))
340    return APValue();
341  return Result;
342}
343
344//===----------------------------------------------------------------------===//
345// Pointer Evaluation
346//===----------------------------------------------------------------------===//
347
348namespace {
349class PointerExprEvaluator
350  : public StmtVisitor<PointerExprEvaluator, APValue> {
351  EvalInfo &Info;
352public:
353
354  PointerExprEvaluator(EvalInfo &info) : Info(info) {}
355
356  APValue VisitStmt(Stmt *S) {
357    return APValue();
358  }
359
360  APValue VisitParenExpr(ParenExpr *E) { return Visit(E->getSubExpr()); }
361
362  APValue VisitBinaryOperator(const BinaryOperator *E);
363  APValue VisitCastExpr(CastExpr* E);
364  APValue VisitUnaryExtension(const UnaryOperator *E)
365      { return Visit(E->getSubExpr()); }
366  APValue VisitUnaryAddrOf(const UnaryOperator *E);
367  APValue VisitObjCStringLiteral(ObjCStringLiteral *E)
368      { return APValue(E); }
369  APValue VisitAddrLabelExpr(AddrLabelExpr *E)
370      { return APValue(E); }
371  APValue VisitCallExpr(CallExpr *E);
372  APValue VisitBlockExpr(BlockExpr *E) {
373    if (!E->hasBlockDeclRefExprs())
374      return APValue(E);
375    return APValue();
376  }
377  APValue VisitImplicitValueInitExpr(ImplicitValueInitExpr *E)
378      { return APValue((Expr*)0); }
379  APValue VisitConditionalOperator(ConditionalOperator *E);
380  APValue VisitChooseExpr(ChooseExpr *E)
381      { return Visit(E->getChosenSubExpr(Info.Ctx)); }
382  APValue VisitCXXNullPtrLiteralExpr(CXXNullPtrLiteralExpr *E)
383      { return APValue((Expr*)0); }
384  // FIXME: Missing: @protocol, @selector
385};
386} // end anonymous namespace
387
388static bool EvaluatePointer(const Expr* E, APValue& Result, EvalInfo &Info) {
389  if (!E->getType()->hasPointerRepresentation())
390    return false;
391  Result = PointerExprEvaluator(Info).Visit(const_cast<Expr*>(E));
392  return Result.isLValue();
393}
394
395APValue PointerExprEvaluator::VisitBinaryOperator(const BinaryOperator *E) {
396  if (E->getOpcode() != BinaryOperator::Add &&
397      E->getOpcode() != BinaryOperator::Sub)
398    return APValue();
399
400  const Expr *PExp = E->getLHS();
401  const Expr *IExp = E->getRHS();
402  if (IExp->getType()->isPointerType())
403    std::swap(PExp, IExp);
404
405  APValue ResultLValue;
406  if (!EvaluatePointer(PExp, ResultLValue, Info))
407    return APValue();
408
409  llvm::APSInt AdditionalOffset(32);
410  if (!EvaluateInteger(IExp, AdditionalOffset, Info))
411    return APValue();
412
413  QualType PointeeType = PExp->getType()->getAs<PointerType>()->getPointeeType();
414  CharUnits SizeOfPointee;
415
416  // Explicitly handle GNU void* and function pointer arithmetic extensions.
417  if (PointeeType->isVoidType() || PointeeType->isFunctionType())
418    SizeOfPointee = CharUnits::One();
419  else
420    SizeOfPointee = Info.Ctx.getTypeSizeInChars(PointeeType);
421
422  CharUnits Offset = ResultLValue.getLValueOffset();
423
424  if (E->getOpcode() == BinaryOperator::Add)
425    Offset += AdditionalOffset.getLimitedValue() * SizeOfPointee;
426  else
427    Offset -= AdditionalOffset.getLimitedValue() * SizeOfPointee;
428
429  return APValue(ResultLValue.getLValueBase(), Offset);
430}
431
432APValue PointerExprEvaluator::VisitUnaryAddrOf(const UnaryOperator *E) {
433  APValue result;
434  if (EvaluateLValue(E->getSubExpr(), result, Info))
435    return result;
436  return APValue();
437}
438
439
440APValue PointerExprEvaluator::VisitCastExpr(CastExpr* E) {
441  Expr* SubExpr = E->getSubExpr();
442
443  switch (E->getCastKind()) {
444  default:
445    break;
446
447  case CastExpr::CK_Unknown: {
448    // FIXME: The handling for CK_Unknown is ugly/shouldn't be necessary!
449
450    // Check for pointer->pointer cast
451    if (SubExpr->getType()->isPointerType() ||
452        SubExpr->getType()->isObjCObjectPointerType() ||
453        SubExpr->getType()->isNullPtrType() ||
454        SubExpr->getType()->isBlockPointerType())
455      return Visit(SubExpr);
456
457    if (SubExpr->getType()->isIntegralType()) {
458      APValue Result;
459      if (!EvaluateIntegerOrLValue(SubExpr, Result, Info))
460        break;
461
462      if (Result.isInt()) {
463        Result.getInt().extOrTrunc((unsigned)Info.Ctx.getTypeSize(E->getType()));
464        return APValue(0,
465                       CharUnits::fromQuantity(Result.getInt().getZExtValue()));
466      }
467
468      // Cast is of an lvalue, no need to change value.
469      return Result;
470    }
471    break;
472  }
473
474  case CastExpr::CK_NoOp:
475  case CastExpr::CK_BitCast:
476  case CastExpr::CK_AnyPointerToObjCPointerCast:
477  case CastExpr::CK_AnyPointerToBlockPointerCast:
478    return Visit(SubExpr);
479
480  case CastExpr::CK_IntegralToPointer: {
481    APValue Result;
482    if (!EvaluateIntegerOrLValue(SubExpr, Result, Info))
483      break;
484
485    if (Result.isInt()) {
486      Result.getInt().extOrTrunc((unsigned)Info.Ctx.getTypeSize(E->getType()));
487      return APValue(0,
488                     CharUnits::fromQuantity(Result.getInt().getZExtValue()));
489    }
490
491    // Cast is of an lvalue, no need to change value.
492    return Result;
493  }
494  case CastExpr::CK_ArrayToPointerDecay:
495  case CastExpr::CK_FunctionToPointerDecay: {
496    APValue Result;
497    if (EvaluateLValue(SubExpr, Result, Info))
498      return Result;
499    break;
500  }
501  }
502
503  return APValue();
504}
505
506APValue PointerExprEvaluator::VisitCallExpr(CallExpr *E) {
507  if (E->isBuiltinCall(Info.Ctx) ==
508        Builtin::BI__builtin___CFStringMakeConstantString ||
509      E->isBuiltinCall(Info.Ctx) ==
510        Builtin::BI__builtin___NSStringMakeConstantString)
511    return APValue(E);
512  return APValue();
513}
514
515APValue PointerExprEvaluator::VisitConditionalOperator(ConditionalOperator *E) {
516  bool BoolResult;
517  if (!HandleConversionToBool(E->getCond(), BoolResult, Info))
518    return APValue();
519
520  Expr* EvalExpr = BoolResult ? E->getTrueExpr() : E->getFalseExpr();
521
522  APValue Result;
523  if (EvaluatePointer(EvalExpr, Result, Info))
524    return Result;
525  return APValue();
526}
527
528//===----------------------------------------------------------------------===//
529// Vector Evaluation
530//===----------------------------------------------------------------------===//
531
532namespace {
533  class VectorExprEvaluator
534  : public StmtVisitor<VectorExprEvaluator, APValue> {
535    EvalInfo &Info;
536    APValue GetZeroVector(QualType VecType);
537  public:
538
539    VectorExprEvaluator(EvalInfo &info) : Info(info) {}
540
541    APValue VisitStmt(Stmt *S) {
542      return APValue();
543    }
544
545    APValue VisitParenExpr(ParenExpr *E)
546        { return Visit(E->getSubExpr()); }
547    APValue VisitUnaryExtension(const UnaryOperator *E)
548      { return Visit(E->getSubExpr()); }
549    APValue VisitUnaryPlus(const UnaryOperator *E)
550      { return Visit(E->getSubExpr()); }
551    APValue VisitUnaryReal(const UnaryOperator *E)
552      { return Visit(E->getSubExpr()); }
553    APValue VisitImplicitValueInitExpr(const ImplicitValueInitExpr *E)
554      { return GetZeroVector(E->getType()); }
555    APValue VisitCastExpr(const CastExpr* E);
556    APValue VisitCompoundLiteralExpr(const CompoundLiteralExpr *E);
557    APValue VisitInitListExpr(const InitListExpr *E);
558    APValue VisitConditionalOperator(const ConditionalOperator *E);
559    APValue VisitChooseExpr(const ChooseExpr *E)
560      { return Visit(E->getChosenSubExpr(Info.Ctx)); }
561    APValue VisitUnaryImag(const UnaryOperator *E);
562    // FIXME: Missing: unary -, unary ~, binary add/sub/mul/div,
563    //                 binary comparisons, binary and/or/xor,
564    //                 shufflevector, ExtVectorElementExpr
565    //        (Note that these require implementing conversions
566    //         between vector types.)
567  };
568} // end anonymous namespace
569
570static bool EvaluateVector(const Expr* E, APValue& Result, EvalInfo &Info) {
571  if (!E->getType()->isVectorType())
572    return false;
573  Result = VectorExprEvaluator(Info).Visit(const_cast<Expr*>(E));
574  return !Result.isUninit();
575}
576
577APValue VectorExprEvaluator::VisitCastExpr(const CastExpr* E) {
578  const VectorType *VTy = E->getType()->getAs<VectorType>();
579  QualType EltTy = VTy->getElementType();
580  unsigned NElts = VTy->getNumElements();
581  unsigned EltWidth = Info.Ctx.getTypeSize(EltTy);
582
583  const Expr* SE = E->getSubExpr();
584  QualType SETy = SE->getType();
585  APValue Result = APValue();
586
587  // Check for vector->vector bitcast and scalar->vector splat.
588  if (SETy->isVectorType()) {
589    return this->Visit(const_cast<Expr*>(SE));
590  } else if (SETy->isIntegerType()) {
591    APSInt IntResult;
592    if (!EvaluateInteger(SE, IntResult, Info))
593      return APValue();
594    Result = APValue(IntResult);
595  } else if (SETy->isRealFloatingType()) {
596    APFloat F(0.0);
597    if (!EvaluateFloat(SE, F, Info))
598      return APValue();
599    Result = APValue(F);
600  } else
601    return APValue();
602
603  // For casts of a scalar to ExtVector, convert the scalar to the element type
604  // and splat it to all elements.
605  if (E->getType()->isExtVectorType()) {
606    if (EltTy->isIntegerType() && Result.isInt())
607      Result = APValue(HandleIntToIntCast(EltTy, SETy, Result.getInt(),
608                                          Info.Ctx));
609    else if (EltTy->isIntegerType())
610      Result = APValue(HandleFloatToIntCast(EltTy, SETy, Result.getFloat(),
611                                            Info.Ctx));
612    else if (EltTy->isRealFloatingType() && Result.isInt())
613      Result = APValue(HandleIntToFloatCast(EltTy, SETy, Result.getInt(),
614                                            Info.Ctx));
615    else if (EltTy->isRealFloatingType())
616      Result = APValue(HandleFloatToFloatCast(EltTy, SETy, Result.getFloat(),
617                                              Info.Ctx));
618    else
619      return APValue();
620
621    // Splat and create vector APValue.
622    llvm::SmallVector<APValue, 4> Elts(NElts, Result);
623    return APValue(&Elts[0], Elts.size());
624  }
625
626  // For casts of a scalar to regular gcc-style vector type, bitcast the scalar
627  // to the vector. To construct the APValue vector initializer, bitcast the
628  // initializing value to an APInt, and shift out the bits pertaining to each
629  // element.
630  APSInt Init;
631  Init = Result.isInt() ? Result.getInt() : Result.getFloat().bitcastToAPInt();
632
633  llvm::SmallVector<APValue, 4> Elts;
634  for (unsigned i = 0; i != NElts; ++i) {
635    APSInt Tmp = Init;
636    Tmp.extOrTrunc(EltWidth);
637
638    if (EltTy->isIntegerType())
639      Elts.push_back(APValue(Tmp));
640    else if (EltTy->isRealFloatingType())
641      Elts.push_back(APValue(APFloat(Tmp)));
642    else
643      return APValue();
644
645    Init >>= EltWidth;
646  }
647  return APValue(&Elts[0], Elts.size());
648}
649
650APValue
651VectorExprEvaluator::VisitCompoundLiteralExpr(const CompoundLiteralExpr *E) {
652  return this->Visit(const_cast<Expr*>(E->getInitializer()));
653}
654
655APValue
656VectorExprEvaluator::VisitInitListExpr(const InitListExpr *E) {
657  const VectorType *VT = E->getType()->getAs<VectorType>();
658  unsigned NumInits = E->getNumInits();
659  unsigned NumElements = VT->getNumElements();
660
661  QualType EltTy = VT->getElementType();
662  llvm::SmallVector<APValue, 4> Elements;
663
664  for (unsigned i = 0; i < NumElements; i++) {
665    if (EltTy->isIntegerType()) {
666      llvm::APSInt sInt(32);
667      if (i < NumInits) {
668        if (!EvaluateInteger(E->getInit(i), sInt, Info))
669          return APValue();
670      } else {
671        sInt = Info.Ctx.MakeIntValue(0, EltTy);
672      }
673      Elements.push_back(APValue(sInt));
674    } else {
675      llvm::APFloat f(0.0);
676      if (i < NumInits) {
677        if (!EvaluateFloat(E->getInit(i), f, Info))
678          return APValue();
679      } else {
680        f = APFloat::getZero(Info.Ctx.getFloatTypeSemantics(EltTy));
681      }
682      Elements.push_back(APValue(f));
683    }
684  }
685  return APValue(&Elements[0], Elements.size());
686}
687
688APValue
689VectorExprEvaluator::GetZeroVector(QualType T) {
690  const VectorType *VT = T->getAs<VectorType>();
691  QualType EltTy = VT->getElementType();
692  APValue ZeroElement;
693  if (EltTy->isIntegerType())
694    ZeroElement = APValue(Info.Ctx.MakeIntValue(0, EltTy));
695  else
696    ZeroElement =
697        APValue(APFloat::getZero(Info.Ctx.getFloatTypeSemantics(EltTy)));
698
699  llvm::SmallVector<APValue, 4> Elements(VT->getNumElements(), ZeroElement);
700  return APValue(&Elements[0], Elements.size());
701}
702
703APValue VectorExprEvaluator::VisitConditionalOperator(const ConditionalOperator *E) {
704  bool BoolResult;
705  if (!HandleConversionToBool(E->getCond(), BoolResult, Info))
706    return APValue();
707
708  Expr* EvalExpr = BoolResult ? E->getTrueExpr() : E->getFalseExpr();
709
710  APValue Result;
711  if (EvaluateVector(EvalExpr, Result, Info))
712    return Result;
713  return APValue();
714}
715
716APValue VectorExprEvaluator::VisitUnaryImag(const UnaryOperator *E) {
717  if (!E->getSubExpr()->isEvaluatable(Info.Ctx))
718    Info.EvalResult.HasSideEffects = true;
719  return GetZeroVector(E->getType());
720}
721
722//===----------------------------------------------------------------------===//
723// Integer Evaluation
724//===----------------------------------------------------------------------===//
725
726namespace {
727class IntExprEvaluator
728  : public StmtVisitor<IntExprEvaluator, bool> {
729  EvalInfo &Info;
730  APValue &Result;
731public:
732  IntExprEvaluator(EvalInfo &info, APValue &result)
733    : Info(info), Result(result) {}
734
735  bool Success(const llvm::APSInt &SI, const Expr *E) {
736    assert(E->getType()->isIntegralType() && "Invalid evaluation result.");
737    assert(SI.isSigned() == E->getType()->isSignedIntegerType() &&
738           "Invalid evaluation result.");
739    assert(SI.getBitWidth() == Info.Ctx.getIntWidth(E->getType()) &&
740           "Invalid evaluation result.");
741    Result = APValue(SI);
742    return true;
743  }
744
745  bool Success(const llvm::APInt &I, const Expr *E) {
746    assert(E->getType()->isIntegralType() && "Invalid evaluation result.");
747    assert(I.getBitWidth() == Info.Ctx.getIntWidth(E->getType()) &&
748           "Invalid evaluation result.");
749    Result = APValue(APSInt(I));
750    Result.getInt().setIsUnsigned(E->getType()->isUnsignedIntegerType());
751    return true;
752  }
753
754  bool Success(uint64_t Value, const Expr *E) {
755    assert(E->getType()->isIntegralType() && "Invalid evaluation result.");
756    Result = APValue(Info.Ctx.MakeIntValue(Value, E->getType()));
757    return true;
758  }
759
760  bool Error(SourceLocation L, diag::kind D, const Expr *E) {
761    // Take the first error.
762    if (Info.EvalResult.Diag == 0) {
763      Info.EvalResult.DiagLoc = L;
764      Info.EvalResult.Diag = D;
765      Info.EvalResult.DiagExpr = E;
766    }
767    return false;
768  }
769
770  //===--------------------------------------------------------------------===//
771  //                            Visitor Methods
772  //===--------------------------------------------------------------------===//
773
774  bool VisitStmt(Stmt *) {
775    assert(0 && "This should be called on integers, stmts are not integers");
776    return false;
777  }
778
779  bool VisitExpr(Expr *E) {
780    return Error(E->getLocStart(), diag::note_invalid_subexpr_in_ice, E);
781  }
782
783  bool VisitParenExpr(ParenExpr *E) { return Visit(E->getSubExpr()); }
784
785  bool VisitIntegerLiteral(const IntegerLiteral *E) {
786    return Success(E->getValue(), E);
787  }
788  bool VisitCharacterLiteral(const CharacterLiteral *E) {
789    return Success(E->getValue(), E);
790  }
791  bool VisitTypesCompatibleExpr(const TypesCompatibleExpr *E) {
792    // Per gcc docs "this built-in function ignores top level
793    // qualifiers".  We need to use the canonical version to properly
794    // be able to strip CRV qualifiers from the type.
795    QualType T0 = Info.Ctx.getCanonicalType(E->getArgType1());
796    QualType T1 = Info.Ctx.getCanonicalType(E->getArgType2());
797    return Success(Info.Ctx.typesAreCompatible(T0.getUnqualifiedType(),
798                                               T1.getUnqualifiedType()),
799                   E);
800  }
801
802  bool CheckReferencedDecl(const Expr *E, const Decl *D);
803  bool VisitDeclRefExpr(const DeclRefExpr *E) {
804    return CheckReferencedDecl(E, E->getDecl());
805  }
806  bool VisitMemberExpr(const MemberExpr *E) {
807    if (CheckReferencedDecl(E, E->getMemberDecl())) {
808      // Conservatively assume a MemberExpr will have side-effects
809      Info.EvalResult.HasSideEffects = true;
810      return true;
811    }
812    return false;
813  }
814
815  bool VisitCallExpr(CallExpr *E);
816  bool VisitBinaryOperator(const BinaryOperator *E);
817  bool VisitUnaryOperator(const UnaryOperator *E);
818  bool VisitConditionalOperator(const ConditionalOperator *E);
819
820  bool VisitCastExpr(CastExpr* E);
821  bool VisitSizeOfAlignOfExpr(const SizeOfAlignOfExpr *E);
822
823  bool VisitCXXBoolLiteralExpr(const CXXBoolLiteralExpr *E) {
824    return Success(E->getValue(), E);
825  }
826
827  bool VisitGNUNullExpr(const GNUNullExpr *E) {
828    return Success(0, E);
829  }
830
831  bool VisitCXXZeroInitValueExpr(const CXXZeroInitValueExpr *E) {
832    return Success(0, E);
833  }
834
835  bool VisitImplicitValueInitExpr(const ImplicitValueInitExpr *E) {
836    return Success(0, E);
837  }
838
839  bool VisitUnaryTypeTraitExpr(const UnaryTypeTraitExpr *E) {
840    return Success(E->EvaluateTrait(Info.Ctx), E);
841  }
842
843  bool VisitChooseExpr(const ChooseExpr *E) {
844    return Visit(E->getChosenSubExpr(Info.Ctx));
845  }
846
847  bool VisitUnaryReal(const UnaryOperator *E);
848  bool VisitUnaryImag(const UnaryOperator *E);
849
850private:
851  CharUnits GetAlignOfExpr(const Expr *E);
852  CharUnits GetAlignOfType(QualType T);
853  // FIXME: Missing: array subscript of vector, member of vector
854};
855} // end anonymous namespace
856
857static bool EvaluateIntegerOrLValue(const Expr* E, APValue &Result, EvalInfo &Info) {
858  if (!E->getType()->isIntegralType())
859    return false;
860
861  return IntExprEvaluator(Info, Result).Visit(const_cast<Expr*>(E));
862}
863
864static bool EvaluateInteger(const Expr* E, APSInt &Result, EvalInfo &Info) {
865  APValue Val;
866  if (!EvaluateIntegerOrLValue(E, Val, Info) || !Val.isInt())
867    return false;
868  Result = Val.getInt();
869  return true;
870}
871
872bool IntExprEvaluator::CheckReferencedDecl(const Expr* E, const Decl* D) {
873  // Enums are integer constant exprs.
874  if (const EnumConstantDecl *ECD = dyn_cast<EnumConstantDecl>(D))
875    return Success(ECD->getInitVal(), E);
876
877  // In C++, const, non-volatile integers initialized with ICEs are ICEs.
878  // In C, they can also be folded, although they are not ICEs.
879  if (Info.Ctx.getCanonicalType(E->getType()).getCVRQualifiers()
880                                                        == Qualifiers::Const) {
881
882    if (isa<ParmVarDecl>(D))
883      return Error(E->getLocStart(), diag::note_invalid_subexpr_in_ice, E);
884
885    if (const VarDecl *VD = dyn_cast<VarDecl>(D)) {
886      if (const Expr *Init = VD->getAnyInitializer()) {
887        if (APValue *V = VD->getEvaluatedValue()) {
888          if (V->isInt())
889            return Success(V->getInt(), E);
890          return Error(E->getLocStart(), diag::note_invalid_subexpr_in_ice, E);
891        }
892
893        if (VD->isEvaluatingValue())
894          return Error(E->getLocStart(), diag::note_invalid_subexpr_in_ice, E);
895
896        VD->setEvaluatingValue();
897
898        if (Visit(const_cast<Expr*>(Init))) {
899          // Cache the evaluated value in the variable declaration.
900          VD->setEvaluatedValue(Result);
901          return true;
902        }
903
904        VD->setEvaluatedValue(APValue());
905        return false;
906      }
907    }
908  }
909
910  // Otherwise, random variable references are not constants.
911  return Error(E->getLocStart(), diag::note_invalid_subexpr_in_ice, E);
912}
913
914/// EvaluateBuiltinClassifyType - Evaluate __builtin_classify_type the same way
915/// as GCC.
916static int EvaluateBuiltinClassifyType(const CallExpr *E) {
917  // The following enum mimics the values returned by GCC.
918  // FIXME: Does GCC differ between lvalue and rvalue references here?
919  enum gcc_type_class {
920    no_type_class = -1,
921    void_type_class, integer_type_class, char_type_class,
922    enumeral_type_class, boolean_type_class,
923    pointer_type_class, reference_type_class, offset_type_class,
924    real_type_class, complex_type_class,
925    function_type_class, method_type_class,
926    record_type_class, union_type_class,
927    array_type_class, string_type_class,
928    lang_type_class
929  };
930
931  // If no argument was supplied, default to "no_type_class". This isn't
932  // ideal, however it is what gcc does.
933  if (E->getNumArgs() == 0)
934    return no_type_class;
935
936  QualType ArgTy = E->getArg(0)->getType();
937  if (ArgTy->isVoidType())
938    return void_type_class;
939  else if (ArgTy->isEnumeralType())
940    return enumeral_type_class;
941  else if (ArgTy->isBooleanType())
942    return boolean_type_class;
943  else if (ArgTy->isCharType())
944    return string_type_class; // gcc doesn't appear to use char_type_class
945  else if (ArgTy->isIntegerType())
946    return integer_type_class;
947  else if (ArgTy->isPointerType())
948    return pointer_type_class;
949  else if (ArgTy->isReferenceType())
950    return reference_type_class;
951  else if (ArgTy->isRealType())
952    return real_type_class;
953  else if (ArgTy->isComplexType())
954    return complex_type_class;
955  else if (ArgTy->isFunctionType())
956    return function_type_class;
957  else if (ArgTy->isStructureType())
958    return record_type_class;
959  else if (ArgTy->isUnionType())
960    return union_type_class;
961  else if (ArgTy->isArrayType())
962    return array_type_class;
963  else if (ArgTy->isUnionType())
964    return union_type_class;
965  else  // FIXME: offset_type_class, method_type_class, & lang_type_class?
966    assert(0 && "CallExpr::isBuiltinClassifyType(): unimplemented type");
967  return -1;
968}
969
970bool IntExprEvaluator::VisitCallExpr(CallExpr *E) {
971  switch (E->isBuiltinCall(Info.Ctx)) {
972  default:
973    return Error(E->getLocStart(), diag::note_invalid_subexpr_in_ice, E);
974
975  case Builtin::BI__builtin_object_size: {
976    const Expr *Arg = E->getArg(0)->IgnoreParens();
977    Expr::EvalResult Base;
978
979    // TODO: Perhaps we should let LLVM lower this?
980    if (Arg->EvaluateAsAny(Base, Info.Ctx)
981        && Base.Val.getKind() == APValue::LValue
982        && !Base.HasSideEffects)
983      if (const Expr *LVBase = Base.Val.getLValueBase())
984        if (const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(LVBase)) {
985          if (const VarDecl *VD = dyn_cast<VarDecl>(DRE->getDecl())) {
986            if (!VD->getType()->isIncompleteType()
987                && VD->getType()->isObjectType()
988                && !VD->getType()->isVariablyModifiedType()
989                && !VD->getType()->isDependentType()) {
990              CharUnits Size = Info.Ctx.getTypeSizeInChars(VD->getType());
991              CharUnits Offset = Base.Val.getLValueOffset();
992              if (!Offset.isNegative() && Offset <= Size)
993                Size -= Offset;
994              else
995                Size = CharUnits::Zero();
996              return Success(Size.getQuantity(), E);
997            }
998          }
999        }
1000
1001    // If evaluating the argument has side-effects we can't determine
1002    // the size of the object and lower it to unknown now.
1003    if (E->getArg(0)->HasSideEffects(Info.Ctx)) {
1004      if (E->getArg(1)->EvaluateAsInt(Info.Ctx).getZExtValue() <= 1)
1005        return Success(-1ULL, E);
1006      return Success(0, E);
1007    }
1008
1009    return Error(E->getLocStart(), diag::note_invalid_subexpr_in_ice, E);
1010  }
1011
1012  case Builtin::BI__builtin_classify_type:
1013    return Success(EvaluateBuiltinClassifyType(E), E);
1014
1015  case Builtin::BI__builtin_constant_p:
1016    // __builtin_constant_p always has one operand: it returns true if that
1017    // operand can be folded, false otherwise.
1018    return Success(E->getArg(0)->isEvaluatable(Info.Ctx), E);
1019
1020  case Builtin::BI__builtin_eh_return_data_regno: {
1021    int Operand = E->getArg(0)->EvaluateAsInt(Info.Ctx).getZExtValue();
1022    Operand = Info.Ctx.Target.getEHDataRegisterNumber(Operand);
1023    return Success(Operand, E);
1024  }
1025
1026  case Builtin::BI__builtin_expect:
1027    return Visit(E->getArg(0));
1028  }
1029}
1030
1031bool IntExprEvaluator::VisitBinaryOperator(const BinaryOperator *E) {
1032  if (E->getOpcode() == BinaryOperator::Comma) {
1033    if (!Visit(E->getRHS()))
1034      return false;
1035
1036    // If we can't evaluate the LHS, it might have side effects;
1037    // conservatively mark it.
1038    if (!E->getLHS()->isEvaluatable(Info.Ctx))
1039      Info.EvalResult.HasSideEffects = true;
1040
1041    return true;
1042  }
1043
1044  if (E->isLogicalOp()) {
1045    // These need to be handled specially because the operands aren't
1046    // necessarily integral
1047    bool lhsResult, rhsResult;
1048
1049    if (HandleConversionToBool(E->getLHS(), lhsResult, Info)) {
1050      // We were able to evaluate the LHS, see if we can get away with not
1051      // evaluating the RHS: 0 && X -> 0, 1 || X -> 1
1052      if (lhsResult == (E->getOpcode() == BinaryOperator::LOr))
1053        return Success(lhsResult, E);
1054
1055      if (HandleConversionToBool(E->getRHS(), rhsResult, Info)) {
1056        if (E->getOpcode() == BinaryOperator::LOr)
1057          return Success(lhsResult || rhsResult, E);
1058        else
1059          return Success(lhsResult && rhsResult, E);
1060      }
1061    } else {
1062      if (HandleConversionToBool(E->getRHS(), rhsResult, Info)) {
1063        // We can't evaluate the LHS; however, sometimes the result
1064        // is determined by the RHS: X && 0 -> 0, X || 1 -> 1.
1065        if (rhsResult == (E->getOpcode() == BinaryOperator::LOr) ||
1066            !rhsResult == (E->getOpcode() == BinaryOperator::LAnd)) {
1067          // Since we weren't able to evaluate the left hand side, it
1068          // must have had side effects.
1069          Info.EvalResult.HasSideEffects = true;
1070
1071          return Success(rhsResult, E);
1072        }
1073      }
1074    }
1075
1076    return false;
1077  }
1078
1079  QualType LHSTy = E->getLHS()->getType();
1080  QualType RHSTy = E->getRHS()->getType();
1081
1082  if (LHSTy->isAnyComplexType()) {
1083    assert(RHSTy->isAnyComplexType() && "Invalid comparison");
1084    APValue LHS, RHS;
1085
1086    if (!EvaluateComplex(E->getLHS(), LHS, Info))
1087      return false;
1088
1089    if (!EvaluateComplex(E->getRHS(), RHS, Info))
1090      return false;
1091
1092    if (LHS.isComplexFloat()) {
1093      APFloat::cmpResult CR_r =
1094        LHS.getComplexFloatReal().compare(RHS.getComplexFloatReal());
1095      APFloat::cmpResult CR_i =
1096        LHS.getComplexFloatImag().compare(RHS.getComplexFloatImag());
1097
1098      if (E->getOpcode() == BinaryOperator::EQ)
1099        return Success((CR_r == APFloat::cmpEqual &&
1100                        CR_i == APFloat::cmpEqual), E);
1101      else {
1102        assert(E->getOpcode() == BinaryOperator::NE &&
1103               "Invalid complex comparison.");
1104        return Success(((CR_r == APFloat::cmpGreaterThan ||
1105                         CR_r == APFloat::cmpLessThan) &&
1106                        (CR_i == APFloat::cmpGreaterThan ||
1107                         CR_i == APFloat::cmpLessThan)), E);
1108      }
1109    } else {
1110      if (E->getOpcode() == BinaryOperator::EQ)
1111        return Success((LHS.getComplexIntReal() == RHS.getComplexIntReal() &&
1112                        LHS.getComplexIntImag() == RHS.getComplexIntImag()), E);
1113      else {
1114        assert(E->getOpcode() == BinaryOperator::NE &&
1115               "Invalid compex comparison.");
1116        return Success((LHS.getComplexIntReal() != RHS.getComplexIntReal() ||
1117                        LHS.getComplexIntImag() != RHS.getComplexIntImag()), E);
1118      }
1119    }
1120  }
1121
1122  if (LHSTy->isRealFloatingType() &&
1123      RHSTy->isRealFloatingType()) {
1124    APFloat RHS(0.0), LHS(0.0);
1125
1126    if (!EvaluateFloat(E->getRHS(), RHS, Info))
1127      return false;
1128
1129    if (!EvaluateFloat(E->getLHS(), LHS, Info))
1130      return false;
1131
1132    APFloat::cmpResult CR = LHS.compare(RHS);
1133
1134    switch (E->getOpcode()) {
1135    default:
1136      assert(0 && "Invalid binary operator!");
1137    case BinaryOperator::LT:
1138      return Success(CR == APFloat::cmpLessThan, E);
1139    case BinaryOperator::GT:
1140      return Success(CR == APFloat::cmpGreaterThan, E);
1141    case BinaryOperator::LE:
1142      return Success(CR == APFloat::cmpLessThan || CR == APFloat::cmpEqual, E);
1143    case BinaryOperator::GE:
1144      return Success(CR == APFloat::cmpGreaterThan || CR == APFloat::cmpEqual,
1145                     E);
1146    case BinaryOperator::EQ:
1147      return Success(CR == APFloat::cmpEqual, E);
1148    case BinaryOperator::NE:
1149      return Success(CR == APFloat::cmpGreaterThan
1150                     || CR == APFloat::cmpLessThan, E);
1151    }
1152  }
1153
1154  if (LHSTy->isPointerType() && RHSTy->isPointerType()) {
1155    if (E->getOpcode() == BinaryOperator::Sub || E->isEqualityOp()) {
1156      APValue LHSValue;
1157      if (!EvaluatePointer(E->getLHS(), LHSValue, Info))
1158        return false;
1159
1160      APValue RHSValue;
1161      if (!EvaluatePointer(E->getRHS(), RHSValue, Info))
1162        return false;
1163
1164      // Reject any bases from the normal codepath; we special-case comparisons
1165      // to null.
1166      if (LHSValue.getLValueBase()) {
1167        if (!E->isEqualityOp())
1168          return false;
1169        if (RHSValue.getLValueBase() || !RHSValue.getLValueOffset().isZero())
1170          return false;
1171        bool bres;
1172        if (!EvalPointerValueAsBool(LHSValue, bres))
1173          return false;
1174        return Success(bres ^ (E->getOpcode() == BinaryOperator::EQ), E);
1175      } else if (RHSValue.getLValueBase()) {
1176        if (!E->isEqualityOp())
1177          return false;
1178        if (LHSValue.getLValueBase() || !LHSValue.getLValueOffset().isZero())
1179          return false;
1180        bool bres;
1181        if (!EvalPointerValueAsBool(RHSValue, bres))
1182          return false;
1183        return Success(bres ^ (E->getOpcode() == BinaryOperator::EQ), E);
1184      }
1185
1186      if (E->getOpcode() == BinaryOperator::Sub) {
1187        const QualType Type = E->getLHS()->getType();
1188        const QualType ElementType = Type->getAs<PointerType>()->getPointeeType();
1189
1190        CharUnits ElementSize = CharUnits::One();
1191        if (!ElementType->isVoidType() && !ElementType->isFunctionType())
1192          ElementSize = Info.Ctx.getTypeSizeInChars(ElementType);
1193
1194        CharUnits Diff = LHSValue.getLValueOffset() -
1195                             RHSValue.getLValueOffset();
1196        return Success(Diff / ElementSize, E);
1197      }
1198      bool Result;
1199      if (E->getOpcode() == BinaryOperator::EQ) {
1200        Result = LHSValue.getLValueOffset() == RHSValue.getLValueOffset();
1201      } else {
1202        Result = LHSValue.getLValueOffset() != RHSValue.getLValueOffset();
1203      }
1204      return Success(Result, E);
1205    }
1206  }
1207  if (!LHSTy->isIntegralType() ||
1208      !RHSTy->isIntegralType()) {
1209    // We can't continue from here for non-integral types, and they
1210    // could potentially confuse the following operations.
1211    return false;
1212  }
1213
1214  // The LHS of a constant expr is always evaluated and needed.
1215  if (!Visit(E->getLHS()))
1216    return false; // error in subexpression.
1217
1218  APValue RHSVal;
1219  if (!EvaluateIntegerOrLValue(E->getRHS(), RHSVal, Info))
1220    return false;
1221
1222  // Handle cases like (unsigned long)&a + 4.
1223  if (E->isAdditiveOp() && Result.isLValue() && RHSVal.isInt()) {
1224    CharUnits Offset = Result.getLValueOffset();
1225    CharUnits AdditionalOffset = CharUnits::fromQuantity(
1226                                     RHSVal.getInt().getZExtValue());
1227    if (E->getOpcode() == BinaryOperator::Add)
1228      Offset += AdditionalOffset;
1229    else
1230      Offset -= AdditionalOffset;
1231    Result = APValue(Result.getLValueBase(), Offset);
1232    return true;
1233  }
1234
1235  // Handle cases like 4 + (unsigned long)&a
1236  if (E->getOpcode() == BinaryOperator::Add &&
1237        RHSVal.isLValue() && Result.isInt()) {
1238    CharUnits Offset = RHSVal.getLValueOffset();
1239    Offset += CharUnits::fromQuantity(Result.getInt().getZExtValue());
1240    Result = APValue(RHSVal.getLValueBase(), Offset);
1241    return true;
1242  }
1243
1244  // All the following cases expect both operands to be an integer
1245  if (!Result.isInt() || !RHSVal.isInt())
1246    return false;
1247
1248  APSInt& RHS = RHSVal.getInt();
1249
1250  switch (E->getOpcode()) {
1251  default:
1252    return Error(E->getOperatorLoc(), diag::note_invalid_subexpr_in_ice, E);
1253  case BinaryOperator::Mul: return Success(Result.getInt() * RHS, E);
1254  case BinaryOperator::Add: return Success(Result.getInt() + RHS, E);
1255  case BinaryOperator::Sub: return Success(Result.getInt() - RHS, E);
1256  case BinaryOperator::And: return Success(Result.getInt() & RHS, E);
1257  case BinaryOperator::Xor: return Success(Result.getInt() ^ RHS, E);
1258  case BinaryOperator::Or:  return Success(Result.getInt() | RHS, E);
1259  case BinaryOperator::Div:
1260    if (RHS == 0)
1261      return Error(E->getOperatorLoc(), diag::note_expr_divide_by_zero, E);
1262    return Success(Result.getInt() / RHS, E);
1263  case BinaryOperator::Rem:
1264    if (RHS == 0)
1265      return Error(E->getOperatorLoc(), diag::note_expr_divide_by_zero, E);
1266    return Success(Result.getInt() % RHS, E);
1267  case BinaryOperator::Shl: {
1268    // FIXME: Warn about out of range shift amounts!
1269    unsigned SA =
1270      (unsigned) RHS.getLimitedValue(Result.getInt().getBitWidth()-1);
1271    return Success(Result.getInt() << SA, E);
1272  }
1273  case BinaryOperator::Shr: {
1274    unsigned SA =
1275      (unsigned) RHS.getLimitedValue(Result.getInt().getBitWidth()-1);
1276    return Success(Result.getInt() >> SA, E);
1277  }
1278
1279  case BinaryOperator::LT: return Success(Result.getInt() < RHS, E);
1280  case BinaryOperator::GT: return Success(Result.getInt() > RHS, E);
1281  case BinaryOperator::LE: return Success(Result.getInt() <= RHS, E);
1282  case BinaryOperator::GE: return Success(Result.getInt() >= RHS, E);
1283  case BinaryOperator::EQ: return Success(Result.getInt() == RHS, E);
1284  case BinaryOperator::NE: return Success(Result.getInt() != RHS, E);
1285  }
1286}
1287
1288bool IntExprEvaluator::VisitConditionalOperator(const ConditionalOperator *E) {
1289  bool Cond;
1290  if (!HandleConversionToBool(E->getCond(), Cond, Info))
1291    return false;
1292
1293  return Visit(Cond ? E->getTrueExpr() : E->getFalseExpr());
1294}
1295
1296CharUnits IntExprEvaluator::GetAlignOfType(QualType T) {
1297  // C++ [expr.sizeof]p2: "When applied to a reference or a reference type,
1298  //   the result is the size of the referenced type."
1299  // C++ [expr.alignof]p3: "When alignof is applied to a reference type, the
1300  //   result shall be the alignment of the referenced type."
1301  if (const ReferenceType *Ref = T->getAs<ReferenceType>())
1302    T = Ref->getPointeeType();
1303
1304  // Get information about the alignment.
1305  unsigned CharSize = Info.Ctx.Target.getCharWidth();
1306
1307  // __alignof is defined to return the preferred alignment.
1308  return CharUnits::fromQuantity(
1309      Info.Ctx.getPreferredTypeAlign(T.getTypePtr()) / CharSize);
1310}
1311
1312CharUnits IntExprEvaluator::GetAlignOfExpr(const Expr *E) {
1313  E = E->IgnoreParens();
1314
1315  // alignof decl is always accepted, even if it doesn't make sense: we default
1316  // to 1 in those cases.
1317  if (const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E))
1318    return Info.Ctx.getDeclAlign(DRE->getDecl(),
1319                                 /*RefAsPointee*/true);
1320
1321  if (const MemberExpr *ME = dyn_cast<MemberExpr>(E))
1322    return Info.Ctx.getDeclAlign(ME->getMemberDecl(),
1323                                 /*RefAsPointee*/true);
1324
1325  return GetAlignOfType(E->getType());
1326}
1327
1328
1329/// VisitSizeAlignOfExpr - Evaluate a sizeof or alignof with a result as the
1330/// expression's type.
1331bool IntExprEvaluator::VisitSizeOfAlignOfExpr(const SizeOfAlignOfExpr *E) {
1332  // Handle alignof separately.
1333  if (!E->isSizeOf()) {
1334    if (E->isArgumentType())
1335      return Success(GetAlignOfType(E->getArgumentType()).getQuantity(), E);
1336    else
1337      return Success(GetAlignOfExpr(E->getArgumentExpr()).getQuantity(), E);
1338  }
1339
1340  QualType SrcTy = E->getTypeOfArgument();
1341  // C++ [expr.sizeof]p2: "When applied to a reference or a reference type,
1342  //   the result is the size of the referenced type."
1343  // C++ [expr.alignof]p3: "When alignof is applied to a reference type, the
1344  //   result shall be the alignment of the referenced type."
1345  if (const ReferenceType *Ref = SrcTy->getAs<ReferenceType>())
1346    SrcTy = Ref->getPointeeType();
1347
1348  // sizeof(void), __alignof__(void), sizeof(function) = 1 as a gcc
1349  // extension.
1350  if (SrcTy->isVoidType() || SrcTy->isFunctionType())
1351    return Success(1, E);
1352
1353  // sizeof(vla) is not a constantexpr: C99 6.5.3.4p2.
1354  if (!SrcTy->isConstantSizeType())
1355    return false;
1356
1357  // Get information about the size.
1358  return Success(Info.Ctx.getTypeSizeInChars(SrcTy).getQuantity(), E);
1359}
1360
1361bool IntExprEvaluator::VisitUnaryOperator(const UnaryOperator *E) {
1362  // Special case unary operators that do not need their subexpression
1363  // evaluated.  offsetof/sizeof/alignof are all special.
1364  if (E->isOffsetOfOp()) {
1365    // The AST for offsetof is defined in such a way that we can just
1366    // directly Evaluate it as an l-value.
1367    APValue LV;
1368    if (!EvaluateLValue(E->getSubExpr(), LV, Info))
1369      return false;
1370    if (LV.getLValueBase())
1371      return false;
1372    return Success(LV.getLValueOffset().getQuantity(), E);
1373  }
1374
1375  if (E->getOpcode() == UnaryOperator::LNot) {
1376    // LNot's operand isn't necessarily an integer, so we handle it specially.
1377    bool bres;
1378    if (!HandleConversionToBool(E->getSubExpr(), bres, Info))
1379      return false;
1380    return Success(!bres, E);
1381  }
1382
1383  // Only handle integral operations...
1384  if (!E->getSubExpr()->getType()->isIntegralType())
1385    return false;
1386
1387  // Get the operand value into 'Result'.
1388  if (!Visit(E->getSubExpr()))
1389    return false;
1390
1391  switch (E->getOpcode()) {
1392  default:
1393    // Address, indirect, pre/post inc/dec, etc are not valid constant exprs.
1394    // See C99 6.6p3.
1395    return Error(E->getOperatorLoc(), diag::note_invalid_subexpr_in_ice, E);
1396  case UnaryOperator::Extension:
1397    // FIXME: Should extension allow i-c-e extension expressions in its scope?
1398    // If so, we could clear the diagnostic ID.
1399    return true;
1400  case UnaryOperator::Plus:
1401    // The result is always just the subexpr.
1402    return true;
1403  case UnaryOperator::Minus:
1404    if (!Result.isInt()) return false;
1405    return Success(-Result.getInt(), E);
1406  case UnaryOperator::Not:
1407    if (!Result.isInt()) return false;
1408    return Success(~Result.getInt(), E);
1409  }
1410}
1411
1412/// HandleCast - This is used to evaluate implicit or explicit casts where the
1413/// result type is integer.
1414bool IntExprEvaluator::VisitCastExpr(CastExpr *E) {
1415  Expr *SubExpr = E->getSubExpr();
1416  QualType DestType = E->getType();
1417  QualType SrcType = SubExpr->getType();
1418
1419  if (DestType->isBooleanType()) {
1420    bool BoolResult;
1421    if (!HandleConversionToBool(SubExpr, BoolResult, Info))
1422      return false;
1423    return Success(BoolResult, E);
1424  }
1425
1426  // Handle simple integer->integer casts.
1427  if (SrcType->isIntegralType()) {
1428    if (!Visit(SubExpr))
1429      return false;
1430
1431    if (!Result.isInt()) {
1432      // Only allow casts of lvalues if they are lossless.
1433      return Info.Ctx.getTypeSize(DestType) == Info.Ctx.getTypeSize(SrcType);
1434    }
1435
1436    return Success(HandleIntToIntCast(DestType, SrcType,
1437                                      Result.getInt(), Info.Ctx), E);
1438  }
1439
1440  // FIXME: Clean this up!
1441  if (SrcType->isPointerType()) {
1442    APValue LV;
1443    if (!EvaluatePointer(SubExpr, LV, Info))
1444      return false;
1445
1446    if (LV.getLValueBase()) {
1447      // Only allow based lvalue casts if they are lossless.
1448      if (Info.Ctx.getTypeSize(DestType) != Info.Ctx.getTypeSize(SrcType))
1449        return false;
1450
1451      Result = LV;
1452      return true;
1453    }
1454
1455    APSInt AsInt = Info.Ctx.MakeIntValue(LV.getLValueOffset().getQuantity(),
1456                                         SrcType);
1457    return Success(HandleIntToIntCast(DestType, SrcType, AsInt, Info.Ctx), E);
1458  }
1459
1460  if (SrcType->isArrayType() || SrcType->isFunctionType()) {
1461    // This handles double-conversion cases, where there's both
1462    // an l-value promotion and an implicit conversion to int.
1463    APValue LV;
1464    if (!EvaluateLValue(SubExpr, LV, Info))
1465      return false;
1466
1467    if (Info.Ctx.getTypeSize(DestType) != Info.Ctx.getTypeSize(Info.Ctx.VoidPtrTy))
1468      return false;
1469
1470    Result = LV;
1471    return true;
1472  }
1473
1474  if (SrcType->isAnyComplexType()) {
1475    APValue C;
1476    if (!EvaluateComplex(SubExpr, C, Info))
1477      return false;
1478    if (C.isComplexFloat())
1479      return Success(HandleFloatToIntCast(DestType, SrcType,
1480                                          C.getComplexFloatReal(), Info.Ctx),
1481                     E);
1482    else
1483      return Success(HandleIntToIntCast(DestType, SrcType,
1484                                        C.getComplexIntReal(), Info.Ctx), E);
1485  }
1486  // FIXME: Handle vectors
1487
1488  if (!SrcType->isRealFloatingType())
1489    return Error(E->getExprLoc(), diag::note_invalid_subexpr_in_ice, E);
1490
1491  APFloat F(0.0);
1492  if (!EvaluateFloat(SubExpr, F, Info))
1493    return Error(E->getExprLoc(), diag::note_invalid_subexpr_in_ice, E);
1494
1495  return Success(HandleFloatToIntCast(DestType, SrcType, F, Info.Ctx), E);
1496}
1497
1498bool IntExprEvaluator::VisitUnaryReal(const UnaryOperator *E) {
1499  if (E->getSubExpr()->getType()->isAnyComplexType()) {
1500    APValue LV;
1501    if (!EvaluateComplex(E->getSubExpr(), LV, Info) || !LV.isComplexInt())
1502      return Error(E->getExprLoc(), diag::note_invalid_subexpr_in_ice, E);
1503    return Success(LV.getComplexIntReal(), E);
1504  }
1505
1506  return Visit(E->getSubExpr());
1507}
1508
1509bool IntExprEvaluator::VisitUnaryImag(const UnaryOperator *E) {
1510  if (E->getSubExpr()->getType()->isComplexIntegerType()) {
1511    APValue LV;
1512    if (!EvaluateComplex(E->getSubExpr(), LV, Info) || !LV.isComplexInt())
1513      return Error(E->getExprLoc(), diag::note_invalid_subexpr_in_ice, E);
1514    return Success(LV.getComplexIntImag(), E);
1515  }
1516
1517  if (!E->getSubExpr()->isEvaluatable(Info.Ctx))
1518    Info.EvalResult.HasSideEffects = true;
1519  return Success(0, E);
1520}
1521
1522//===----------------------------------------------------------------------===//
1523// Float Evaluation
1524//===----------------------------------------------------------------------===//
1525
1526namespace {
1527class FloatExprEvaluator
1528  : public StmtVisitor<FloatExprEvaluator, bool> {
1529  EvalInfo &Info;
1530  APFloat &Result;
1531public:
1532  FloatExprEvaluator(EvalInfo &info, APFloat &result)
1533    : Info(info), Result(result) {}
1534
1535  bool VisitStmt(Stmt *S) {
1536    return false;
1537  }
1538
1539  bool VisitParenExpr(ParenExpr *E) { return Visit(E->getSubExpr()); }
1540  bool VisitCallExpr(const CallExpr *E);
1541
1542  bool VisitUnaryOperator(const UnaryOperator *E);
1543  bool VisitBinaryOperator(const BinaryOperator *E);
1544  bool VisitFloatingLiteral(const FloatingLiteral *E);
1545  bool VisitCastExpr(CastExpr *E);
1546  bool VisitCXXZeroInitValueExpr(CXXZeroInitValueExpr *E);
1547  bool VisitConditionalOperator(ConditionalOperator *E);
1548
1549  bool VisitChooseExpr(const ChooseExpr *E)
1550    { return Visit(E->getChosenSubExpr(Info.Ctx)); }
1551  bool VisitUnaryExtension(const UnaryOperator *E)
1552    { return Visit(E->getSubExpr()); }
1553
1554  // FIXME: Missing: __real__/__imag__, array subscript of vector,
1555  //                 member of vector, ImplicitValueInitExpr
1556};
1557} // end anonymous namespace
1558
1559static bool EvaluateFloat(const Expr* E, APFloat& Result, EvalInfo &Info) {
1560  return FloatExprEvaluator(Info, Result).Visit(const_cast<Expr*>(E));
1561}
1562
1563static bool TryEvaluateBuiltinNaN(ASTContext &Context,
1564                                  QualType ResultTy,
1565                                  const Expr *Arg,
1566                                  bool SNaN,
1567                                  llvm::APFloat &Result) {
1568  const StringLiteral *S = dyn_cast<StringLiteral>(Arg->IgnoreParenCasts());
1569  if (!S) return false;
1570
1571  const llvm::fltSemantics &Sem = Context.getFloatTypeSemantics(ResultTy);
1572
1573  llvm::APInt fill;
1574
1575  // Treat empty strings as if they were zero.
1576  if (S->getString().empty())
1577    fill = llvm::APInt(32, 0);
1578  else if (S->getString().getAsInteger(0, fill))
1579    return false;
1580
1581  if (SNaN)
1582    Result = llvm::APFloat::getSNaN(Sem, false, &fill);
1583  else
1584    Result = llvm::APFloat::getQNaN(Sem, false, &fill);
1585  return true;
1586}
1587
1588bool FloatExprEvaluator::VisitCallExpr(const CallExpr *E) {
1589  switch (E->isBuiltinCall(Info.Ctx)) {
1590  default: return false;
1591  case Builtin::BI__builtin_huge_val:
1592  case Builtin::BI__builtin_huge_valf:
1593  case Builtin::BI__builtin_huge_vall:
1594  case Builtin::BI__builtin_inf:
1595  case Builtin::BI__builtin_inff:
1596  case Builtin::BI__builtin_infl: {
1597    const llvm::fltSemantics &Sem =
1598      Info.Ctx.getFloatTypeSemantics(E->getType());
1599    Result = llvm::APFloat::getInf(Sem);
1600    return true;
1601  }
1602
1603  case Builtin::BI__builtin_nans:
1604  case Builtin::BI__builtin_nansf:
1605  case Builtin::BI__builtin_nansl:
1606    return TryEvaluateBuiltinNaN(Info.Ctx, E->getType(), E->getArg(0),
1607                                 true, Result);
1608
1609  case Builtin::BI__builtin_nan:
1610  case Builtin::BI__builtin_nanf:
1611  case Builtin::BI__builtin_nanl:
1612    // If this is __builtin_nan() turn this into a nan, otherwise we
1613    // can't constant fold it.
1614    return TryEvaluateBuiltinNaN(Info.Ctx, E->getType(), E->getArg(0),
1615                                 false, Result);
1616
1617  case Builtin::BI__builtin_fabs:
1618  case Builtin::BI__builtin_fabsf:
1619  case Builtin::BI__builtin_fabsl:
1620    if (!EvaluateFloat(E->getArg(0), Result, Info))
1621      return false;
1622
1623    if (Result.isNegative())
1624      Result.changeSign();
1625    return true;
1626
1627  case Builtin::BI__builtin_copysign:
1628  case Builtin::BI__builtin_copysignf:
1629  case Builtin::BI__builtin_copysignl: {
1630    APFloat RHS(0.);
1631    if (!EvaluateFloat(E->getArg(0), Result, Info) ||
1632        !EvaluateFloat(E->getArg(1), RHS, Info))
1633      return false;
1634    Result.copySign(RHS);
1635    return true;
1636  }
1637  }
1638}
1639
1640bool FloatExprEvaluator::VisitUnaryOperator(const UnaryOperator *E) {
1641  if (E->getOpcode() == UnaryOperator::Deref)
1642    return false;
1643
1644  if (!EvaluateFloat(E->getSubExpr(), Result, Info))
1645    return false;
1646
1647  switch (E->getOpcode()) {
1648  default: return false;
1649  case UnaryOperator::Plus:
1650    return true;
1651  case UnaryOperator::Minus:
1652    Result.changeSign();
1653    return true;
1654  }
1655}
1656
1657bool FloatExprEvaluator::VisitBinaryOperator(const BinaryOperator *E) {
1658  if (E->getOpcode() == BinaryOperator::Comma) {
1659    if (!EvaluateFloat(E->getRHS(), Result, Info))
1660      return false;
1661
1662    // If we can't evaluate the LHS, it might have side effects;
1663    // conservatively mark it.
1664    if (!E->getLHS()->isEvaluatable(Info.Ctx))
1665      Info.EvalResult.HasSideEffects = true;
1666
1667    return true;
1668  }
1669
1670  // FIXME: Diagnostics?  I really don't understand how the warnings
1671  // and errors are supposed to work.
1672  APFloat RHS(0.0);
1673  if (!EvaluateFloat(E->getLHS(), Result, Info))
1674    return false;
1675  if (!EvaluateFloat(E->getRHS(), RHS, Info))
1676    return false;
1677
1678  switch (E->getOpcode()) {
1679  default: return false;
1680  case BinaryOperator::Mul:
1681    Result.multiply(RHS, APFloat::rmNearestTiesToEven);
1682    return true;
1683  case BinaryOperator::Add:
1684    Result.add(RHS, APFloat::rmNearestTiesToEven);
1685    return true;
1686  case BinaryOperator::Sub:
1687    Result.subtract(RHS, APFloat::rmNearestTiesToEven);
1688    return true;
1689  case BinaryOperator::Div:
1690    Result.divide(RHS, APFloat::rmNearestTiesToEven);
1691    return true;
1692  }
1693}
1694
1695bool FloatExprEvaluator::VisitFloatingLiteral(const FloatingLiteral *E) {
1696  Result = E->getValue();
1697  return true;
1698}
1699
1700bool FloatExprEvaluator::VisitCastExpr(CastExpr *E) {
1701  Expr* SubExpr = E->getSubExpr();
1702
1703  if (SubExpr->getType()->isIntegralType()) {
1704    APSInt IntResult;
1705    if (!EvaluateInteger(SubExpr, IntResult, Info))
1706      return false;
1707    Result = HandleIntToFloatCast(E->getType(), SubExpr->getType(),
1708                                  IntResult, Info.Ctx);
1709    return true;
1710  }
1711  if (SubExpr->getType()->isRealFloatingType()) {
1712    if (!Visit(SubExpr))
1713      return false;
1714    Result = HandleFloatToFloatCast(E->getType(), SubExpr->getType(),
1715                                    Result, Info.Ctx);
1716    return true;
1717  }
1718  // FIXME: Handle complex types
1719
1720  return false;
1721}
1722
1723bool FloatExprEvaluator::VisitCXXZeroInitValueExpr(CXXZeroInitValueExpr *E) {
1724  Result = APFloat::getZero(Info.Ctx.getFloatTypeSemantics(E->getType()));
1725  return true;
1726}
1727
1728bool FloatExprEvaluator::VisitConditionalOperator(ConditionalOperator *E) {
1729  bool Cond;
1730  if (!HandleConversionToBool(E->getCond(), Cond, Info))
1731    return false;
1732
1733  return Visit(Cond ? E->getTrueExpr() : E->getFalseExpr());
1734}
1735
1736//===----------------------------------------------------------------------===//
1737// Complex Evaluation (for float and integer)
1738//===----------------------------------------------------------------------===//
1739
1740namespace {
1741class ComplexExprEvaluator
1742  : public StmtVisitor<ComplexExprEvaluator, APValue> {
1743  EvalInfo &Info;
1744
1745public:
1746  ComplexExprEvaluator(EvalInfo &info) : Info(info) {}
1747
1748  //===--------------------------------------------------------------------===//
1749  //                            Visitor Methods
1750  //===--------------------------------------------------------------------===//
1751
1752  APValue VisitStmt(Stmt *S) {
1753    return APValue();
1754  }
1755
1756  APValue VisitParenExpr(ParenExpr *E) { return Visit(E->getSubExpr()); }
1757
1758  APValue VisitImaginaryLiteral(ImaginaryLiteral *E) {
1759    Expr* SubExpr = E->getSubExpr();
1760
1761    if (SubExpr->getType()->isRealFloatingType()) {
1762      APFloat Result(0.0);
1763
1764      if (!EvaluateFloat(SubExpr, Result, Info))
1765        return APValue();
1766
1767      return APValue(APFloat(Result.getSemantics(), APFloat::fcZero, false),
1768                     Result);
1769    } else {
1770      assert(SubExpr->getType()->isIntegerType() &&
1771             "Unexpected imaginary literal.");
1772
1773      llvm::APSInt Result;
1774      if (!EvaluateInteger(SubExpr, Result, Info))
1775        return APValue();
1776
1777      llvm::APSInt Zero(Result.getBitWidth(), !Result.isSigned());
1778      Zero = 0;
1779      return APValue(Zero, Result);
1780    }
1781  }
1782
1783  APValue VisitCastExpr(CastExpr *E) {
1784    Expr* SubExpr = E->getSubExpr();
1785    QualType EltType = E->getType()->getAs<ComplexType>()->getElementType();
1786    QualType SubType = SubExpr->getType();
1787
1788    if (SubType->isRealFloatingType()) {
1789      APFloat Result(0.0);
1790
1791      if (!EvaluateFloat(SubExpr, Result, Info))
1792        return APValue();
1793
1794      if (EltType->isRealFloatingType()) {
1795        Result = HandleFloatToFloatCast(EltType, SubType, Result, Info.Ctx);
1796        return APValue(Result,
1797                       APFloat(Result.getSemantics(), APFloat::fcZero, false));
1798      } else {
1799        llvm::APSInt IResult;
1800        IResult = HandleFloatToIntCast(EltType, SubType, Result, Info.Ctx);
1801        llvm::APSInt Zero(IResult.getBitWidth(), !IResult.isSigned());
1802        Zero = 0;
1803        return APValue(IResult, Zero);
1804      }
1805    } else if (SubType->isIntegerType()) {
1806      APSInt Result;
1807
1808      if (!EvaluateInteger(SubExpr, Result, Info))
1809        return APValue();
1810
1811      if (EltType->isRealFloatingType()) {
1812        APFloat FResult =
1813            HandleIntToFloatCast(EltType, SubType, Result, Info.Ctx);
1814        return APValue(FResult,
1815                       APFloat(FResult.getSemantics(), APFloat::fcZero, false));
1816      } else {
1817        Result = HandleIntToIntCast(EltType, SubType, Result, Info.Ctx);
1818        llvm::APSInt Zero(Result.getBitWidth(), !Result.isSigned());
1819        Zero = 0;
1820        return APValue(Result, Zero);
1821      }
1822    } else if (const ComplexType *CT = SubType->getAs<ComplexType>()) {
1823      APValue Src;
1824
1825      if (!EvaluateComplex(SubExpr, Src, Info))
1826        return APValue();
1827
1828      QualType SrcType = CT->getElementType();
1829
1830      if (Src.isComplexFloat()) {
1831        if (EltType->isRealFloatingType()) {
1832          return APValue(HandleFloatToFloatCast(EltType, SrcType,
1833                                                Src.getComplexFloatReal(),
1834                                                Info.Ctx),
1835                         HandleFloatToFloatCast(EltType, SrcType,
1836                                                Src.getComplexFloatImag(),
1837                                                Info.Ctx));
1838        } else {
1839          return APValue(HandleFloatToIntCast(EltType, SrcType,
1840                                              Src.getComplexFloatReal(),
1841                                              Info.Ctx),
1842                         HandleFloatToIntCast(EltType, SrcType,
1843                                              Src.getComplexFloatImag(),
1844                                              Info.Ctx));
1845        }
1846      } else {
1847        assert(Src.isComplexInt() && "Invalid evaluate result.");
1848        if (EltType->isRealFloatingType()) {
1849          return APValue(HandleIntToFloatCast(EltType, SrcType,
1850                                              Src.getComplexIntReal(),
1851                                              Info.Ctx),
1852                         HandleIntToFloatCast(EltType, SrcType,
1853                                              Src.getComplexIntImag(),
1854                                              Info.Ctx));
1855        } else {
1856          return APValue(HandleIntToIntCast(EltType, SrcType,
1857                                            Src.getComplexIntReal(),
1858                                            Info.Ctx),
1859                         HandleIntToIntCast(EltType, SrcType,
1860                                            Src.getComplexIntImag(),
1861                                            Info.Ctx));
1862        }
1863      }
1864    }
1865
1866    // FIXME: Handle more casts.
1867    return APValue();
1868  }
1869
1870  APValue VisitBinaryOperator(const BinaryOperator *E);
1871  APValue VisitChooseExpr(const ChooseExpr *E)
1872    { return Visit(E->getChosenSubExpr(Info.Ctx)); }
1873  APValue VisitUnaryExtension(const UnaryOperator *E)
1874    { return Visit(E->getSubExpr()); }
1875  // FIXME Missing: unary +/-/~, binary div, ImplicitValueInitExpr,
1876  //                conditional ?:, comma
1877};
1878} // end anonymous namespace
1879
1880static bool EvaluateComplex(const Expr *E, APValue &Result, EvalInfo &Info) {
1881  Result = ComplexExprEvaluator(Info).Visit(const_cast<Expr*>(E));
1882  assert((!Result.isComplexFloat() ||
1883          (&Result.getComplexFloatReal().getSemantics() ==
1884           &Result.getComplexFloatImag().getSemantics())) &&
1885         "Invalid complex evaluation.");
1886  return Result.isComplexFloat() || Result.isComplexInt();
1887}
1888
1889APValue ComplexExprEvaluator::VisitBinaryOperator(const BinaryOperator *E) {
1890  APValue Result, RHS;
1891
1892  if (!EvaluateComplex(E->getLHS(), Result, Info))
1893    return APValue();
1894
1895  if (!EvaluateComplex(E->getRHS(), RHS, Info))
1896    return APValue();
1897
1898  assert(Result.isComplexFloat() == RHS.isComplexFloat() &&
1899         "Invalid operands to binary operator.");
1900  switch (E->getOpcode()) {
1901  default: return APValue();
1902  case BinaryOperator::Add:
1903    if (Result.isComplexFloat()) {
1904      Result.getComplexFloatReal().add(RHS.getComplexFloatReal(),
1905                                       APFloat::rmNearestTiesToEven);
1906      Result.getComplexFloatImag().add(RHS.getComplexFloatImag(),
1907                                       APFloat::rmNearestTiesToEven);
1908    } else {
1909      Result.getComplexIntReal() += RHS.getComplexIntReal();
1910      Result.getComplexIntImag() += RHS.getComplexIntImag();
1911    }
1912    break;
1913  case BinaryOperator::Sub:
1914    if (Result.isComplexFloat()) {
1915      Result.getComplexFloatReal().subtract(RHS.getComplexFloatReal(),
1916                                            APFloat::rmNearestTiesToEven);
1917      Result.getComplexFloatImag().subtract(RHS.getComplexFloatImag(),
1918                                            APFloat::rmNearestTiesToEven);
1919    } else {
1920      Result.getComplexIntReal() -= RHS.getComplexIntReal();
1921      Result.getComplexIntImag() -= RHS.getComplexIntImag();
1922    }
1923    break;
1924  case BinaryOperator::Mul:
1925    if (Result.isComplexFloat()) {
1926      APValue LHS = Result;
1927      APFloat &LHS_r = LHS.getComplexFloatReal();
1928      APFloat &LHS_i = LHS.getComplexFloatImag();
1929      APFloat &RHS_r = RHS.getComplexFloatReal();
1930      APFloat &RHS_i = RHS.getComplexFloatImag();
1931
1932      APFloat Tmp = LHS_r;
1933      Tmp.multiply(RHS_r, APFloat::rmNearestTiesToEven);
1934      Result.getComplexFloatReal() = Tmp;
1935      Tmp = LHS_i;
1936      Tmp.multiply(RHS_i, APFloat::rmNearestTiesToEven);
1937      Result.getComplexFloatReal().subtract(Tmp, APFloat::rmNearestTiesToEven);
1938
1939      Tmp = LHS_r;
1940      Tmp.multiply(RHS_i, APFloat::rmNearestTiesToEven);
1941      Result.getComplexFloatImag() = Tmp;
1942      Tmp = LHS_i;
1943      Tmp.multiply(RHS_r, APFloat::rmNearestTiesToEven);
1944      Result.getComplexFloatImag().add(Tmp, APFloat::rmNearestTiesToEven);
1945    } else {
1946      APValue LHS = Result;
1947      Result.getComplexIntReal() =
1948        (LHS.getComplexIntReal() * RHS.getComplexIntReal() -
1949         LHS.getComplexIntImag() * RHS.getComplexIntImag());
1950      Result.getComplexIntImag() =
1951        (LHS.getComplexIntReal() * RHS.getComplexIntImag() +
1952         LHS.getComplexIntImag() * RHS.getComplexIntReal());
1953    }
1954    break;
1955  }
1956
1957  return Result;
1958}
1959
1960//===----------------------------------------------------------------------===//
1961// Top level Expr::Evaluate method.
1962//===----------------------------------------------------------------------===//
1963
1964/// Evaluate - Return true if this is a constant which we can fold using
1965/// any crazy technique (that has nothing to do with language standards) that
1966/// we want to.  If this function returns true, it returns the folded constant
1967/// in Result.
1968bool Expr::Evaluate(EvalResult &Result, ASTContext &Ctx) const {
1969  EvalInfo Info(Ctx, Result);
1970
1971  if (getType()->isVectorType()) {
1972    if (!EvaluateVector(this, Result.Val, Info))
1973      return false;
1974  } else if (getType()->isIntegerType()) {
1975    if (!IntExprEvaluator(Info, Result.Val).Visit(const_cast<Expr*>(this)))
1976      return false;
1977  } else if (getType()->hasPointerRepresentation()) {
1978    if (!EvaluatePointer(this, Result.Val, Info))
1979      return false;
1980  } else if (getType()->isRealFloatingType()) {
1981    llvm::APFloat f(0.0);
1982    if (!EvaluateFloat(this, f, Info))
1983      return false;
1984
1985    Result.Val = APValue(f);
1986  } else if (getType()->isAnyComplexType()) {
1987    if (!EvaluateComplex(this, Result.Val, Info))
1988      return false;
1989  } else
1990    return false;
1991
1992  return true;
1993}
1994
1995bool Expr::EvaluateAsAny(EvalResult &Result, ASTContext &Ctx) const {
1996  EvalInfo Info(Ctx, Result, true);
1997
1998  if (getType()->isVectorType()) {
1999    if (!EvaluateVector(this, Result.Val, Info))
2000      return false;
2001  } else if (getType()->isIntegerType()) {
2002    if (!IntExprEvaluator(Info, Result.Val).Visit(const_cast<Expr*>(this)))
2003      return false;
2004  } else if (getType()->hasPointerRepresentation()) {
2005    if (!EvaluatePointer(this, Result.Val, Info))
2006      return false;
2007  } else if (getType()->isRealFloatingType()) {
2008    llvm::APFloat f(0.0);
2009    if (!EvaluateFloat(this, f, Info))
2010      return false;
2011
2012    Result.Val = APValue(f);
2013  } else if (getType()->isAnyComplexType()) {
2014    if (!EvaluateComplex(this, Result.Val, Info))
2015      return false;
2016  } else
2017    return false;
2018
2019  return true;
2020}
2021
2022bool Expr::EvaluateAsBooleanCondition(bool &Result, ASTContext &Ctx) const {
2023  EvalResult Scratch;
2024  EvalInfo Info(Ctx, Scratch);
2025
2026  return HandleConversionToBool(this, Result, Info);
2027}
2028
2029bool Expr::EvaluateAsLValue(EvalResult &Result, ASTContext &Ctx) const {
2030  EvalInfo Info(Ctx, Result);
2031
2032  return EvaluateLValue(this, Result.Val, Info) && !Result.HasSideEffects;
2033}
2034
2035bool Expr::EvaluateAsAnyLValue(EvalResult &Result, ASTContext &Ctx) const {
2036  EvalInfo Info(Ctx, Result, true);
2037
2038  return EvaluateLValue(this, Result.Val, Info) && !Result.HasSideEffects;
2039}
2040
2041/// isEvaluatable - Call Evaluate to see if this expression can be constant
2042/// folded, but discard the result.
2043bool Expr::isEvaluatable(ASTContext &Ctx) const {
2044  EvalResult Result;
2045  return Evaluate(Result, Ctx) && !Result.HasSideEffects;
2046}
2047
2048bool Expr::HasSideEffects(ASTContext &Ctx) const {
2049  Expr::EvalResult Result;
2050  EvalInfo Info(Ctx, Result);
2051  return HasSideEffect(Info).Visit(const_cast<Expr*>(this));
2052}
2053
2054APSInt Expr::EvaluateAsInt(ASTContext &Ctx) const {
2055  EvalResult EvalResult;
2056  bool Result = Evaluate(EvalResult, Ctx);
2057  Result = Result;
2058  assert(Result && "Could not evaluate expression");
2059  assert(EvalResult.Val.isInt() && "Expression did not evaluate to integer");
2060
2061  return EvalResult.Val.getInt();
2062}
2063