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