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