ExprConstant.cpp revision 4fdfb0965b396f2778091f7e6c051d17ff9791ba 
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/Basic/Diagnostic.h"
19#include "clang/Basic/TargetInfo.h"
20#include "llvm/Support/Compiler.h"
21using namespace clang;
22using llvm::APSInt;
23using llvm::APFloat;
24
25/// EvalInfo - This is a private struct used by the evaluator to capture
26/// information about a subexpression as it is folded.  It retains information
27/// about the AST context, but also maintains information about the folded
28/// expression.
29///
30/// If an expression could be evaluated, it is still possible it is not a C
31/// "integer constant expression" or constant expression.  If not, this struct
32/// captures information about how and why not.
33///
34/// One bit of information passed *into* the request for constant folding
35/// indicates whether the subexpression is "evaluated" or not according to C
36/// rules.  For example, the RHS of (0 && foo()) is not evaluated.  We can
37/// evaluate the expression regardless of what the RHS is, but C only allows
38/// certain things in certain situations.
39struct EvalInfo {
40  ASTContext &Ctx;
41
42  /// EvalResult - Contains information about the evaluation.
43  Expr::EvalResult &EvalResult;
44
45  /// ShortCircuit - will be greater than zero if the current subexpression has
46  /// will not be evaluated because it's short-circuited (according to C rules).
47  unsigned ShortCircuit;
48
49  EvalInfo(ASTContext &ctx, Expr::EvalResult& evalresult) : Ctx(ctx),
50           EvalResult(evalresult), ShortCircuit(0) {}
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 EvaluateFloat(const Expr *E, APFloat &Result, EvalInfo &Info);
58static bool EvaluateComplexFloat(const Expr *E, APValue &Result,
59                                 EvalInfo &Info);
60
61//===----------------------------------------------------------------------===//
62// Misc utilities
63//===----------------------------------------------------------------------===//
64
65static bool HandleConversionToBool(Expr* E, bool& Result, EvalInfo &Info) {
66  if (E->getType()->isIntegralType()) {
67    APSInt IntResult;
68    if (!EvaluateInteger(E, IntResult, Info))
69      return false;
70    Result = IntResult != 0;
71    return true;
72  } else if (E->getType()->isRealFloatingType()) {
73    APFloat FloatResult(0.0);
74    if (!EvaluateFloat(E, FloatResult, Info))
75      return false;
76    Result = !FloatResult.isZero();
77    return true;
78  } else if (E->getType()->isPointerType()) {
79    APValue PointerResult;
80    if (!EvaluatePointer(E, PointerResult, Info))
81      return false;
82    // FIXME: Is this accurate for all kinds of bases?  If not, what would
83    // the check look like?
84    Result = PointerResult.getLValueBase() || PointerResult.getLValueOffset();
85    return true;
86  }
87
88  return false;
89}
90
91//===----------------------------------------------------------------------===//
92// LValue Evaluation
93//===----------------------------------------------------------------------===//
94namespace {
95class VISIBILITY_HIDDEN LValueExprEvaluator
96  : public StmtVisitor<LValueExprEvaluator, APValue> {
97  EvalInfo &Info;
98public:
99
100  LValueExprEvaluator(EvalInfo &info) : Info(info) {}
101
102  APValue VisitStmt(Stmt *S) {
103#if 0
104    // FIXME: Remove this when we support more expressions.
105    printf("Unhandled pointer statement\n");
106    S->dump();
107#endif
108    return APValue();
109  }
110
111  APValue VisitParenExpr(ParenExpr *E) { return Visit(E->getSubExpr()); }
112  APValue VisitDeclRefExpr(DeclRefExpr *E);
113  APValue VisitPredefinedExpr(PredefinedExpr *E) { return APValue(E, 0); }
114  APValue VisitCompoundLiteralExpr(CompoundLiteralExpr *E);
115  APValue VisitMemberExpr(MemberExpr *E);
116  APValue VisitStringLiteral(StringLiteral *E) { return APValue(E, 0); }
117  APValue VisitArraySubscriptExpr(ArraySubscriptExpr *E);
118};
119} // end anonymous namespace
120
121static bool EvaluateLValue(const Expr* E, APValue& Result, EvalInfo &Info) {
122  Result = LValueExprEvaluator(Info).Visit(const_cast<Expr*>(E));
123  return Result.isLValue();
124}
125
126APValue LValueExprEvaluator::VisitDeclRefExpr(DeclRefExpr *E)
127{
128  if (!E->hasGlobalStorage())
129    return APValue();
130
131  return APValue(E, 0);
132}
133
134APValue LValueExprEvaluator::VisitCompoundLiteralExpr(CompoundLiteralExpr *E) {
135  if (E->isFileScope())
136    return APValue(E, 0);
137  return APValue();
138}
139
140APValue LValueExprEvaluator::VisitMemberExpr(MemberExpr *E) {
141  APValue result;
142  QualType Ty;
143  if (E->isArrow()) {
144    if (!EvaluatePointer(E->getBase(), result, Info))
145      return APValue();
146    Ty = E->getBase()->getType()->getAsPointerType()->getPointeeType();
147  } else {
148    result = Visit(E->getBase());
149    if (result.isUninit())
150      return APValue();
151    Ty = E->getBase()->getType();
152  }
153
154  RecordDecl *RD = Ty->getAsRecordType()->getDecl();
155  const ASTRecordLayout &RL = Info.Ctx.getASTRecordLayout(RD);
156  FieldDecl *FD = E->getMemberDecl();
157
158  // FIXME: This is linear time.
159  unsigned i = 0, e = 0;
160  for (i = 0, e = RD->getNumMembers(); i != e; i++) {
161    if (RD->getMember(i) == FD)
162      break;
163  }
164
165  result.setLValue(result.getLValueBase(),
166                   result.getLValueOffset() + RL.getFieldOffset(i) / 8);
167
168  return result;
169}
170
171APValue LValueExprEvaluator::VisitArraySubscriptExpr(ArraySubscriptExpr *E)
172{
173  APValue Result;
174
175  if (!EvaluatePointer(E->getBase(), Result, Info))
176    return APValue();
177
178  APSInt Index;
179  if (!EvaluateInteger(E->getIdx(), Index, Info))
180    return APValue();
181
182  uint64_t ElementSize = Info.Ctx.getTypeSize(E->getType()) / 8;
183
184  uint64_t Offset = Index.getSExtValue() * ElementSize;
185  Result.setLValue(Result.getLValueBase(),
186                   Result.getLValueOffset() + Offset);
187  return Result;
188}
189
190//===----------------------------------------------------------------------===//
191// Pointer Evaluation
192//===----------------------------------------------------------------------===//
193
194namespace {
195class VISIBILITY_HIDDEN PointerExprEvaluator
196  : public StmtVisitor<PointerExprEvaluator, APValue> {
197  EvalInfo &Info;
198public:
199
200  PointerExprEvaluator(EvalInfo &info) : Info(info) {}
201
202  APValue VisitStmt(Stmt *S) {
203    return APValue();
204  }
205
206  APValue VisitParenExpr(ParenExpr *E) { return Visit(E->getSubExpr()); }
207
208  APValue VisitBinaryOperator(const BinaryOperator *E);
209  APValue VisitCastExpr(const CastExpr* E);
210  APValue VisitUnaryOperator(const UnaryOperator *E);
211  APValue VisitObjCStringLiteral(ObjCStringLiteral *E)
212      { return APValue(E, 0); }
213  APValue VisitConditionalOperator(ConditionalOperator *E);
214};
215} // end anonymous namespace
216
217static bool EvaluatePointer(const Expr* E, APValue& Result, EvalInfo &Info) {
218  if (!E->getType()->isPointerType())
219    return false;
220  Result = PointerExprEvaluator(Info).Visit(const_cast<Expr*>(E));
221  return Result.isLValue();
222}
223
224APValue PointerExprEvaluator::VisitBinaryOperator(const BinaryOperator *E) {
225  if (E->getOpcode() != BinaryOperator::Add &&
226      E->getOpcode() != BinaryOperator::Sub)
227    return APValue();
228
229  const Expr *PExp = E->getLHS();
230  const Expr *IExp = E->getRHS();
231  if (IExp->getType()->isPointerType())
232    std::swap(PExp, IExp);
233
234  APValue ResultLValue;
235  if (!EvaluatePointer(PExp, ResultLValue, Info))
236    return APValue();
237
238  llvm::APSInt AdditionalOffset(32);
239  if (!EvaluateInteger(IExp, AdditionalOffset, Info))
240    return APValue();
241
242  QualType PointeeType = PExp->getType()->getAsPointerType()->getPointeeType();
243  uint64_t SizeOfPointee = Info.Ctx.getTypeSize(PointeeType) / 8;
244
245  uint64_t Offset = ResultLValue.getLValueOffset();
246
247  if (E->getOpcode() == BinaryOperator::Add)
248    Offset += AdditionalOffset.getLimitedValue() * SizeOfPointee;
249  else
250    Offset -= AdditionalOffset.getLimitedValue() * SizeOfPointee;
251
252  return APValue(ResultLValue.getLValueBase(), Offset);
253}
254
255APValue PointerExprEvaluator::VisitUnaryOperator(const UnaryOperator *E) {
256  if (E->getOpcode() == UnaryOperator::Extension) {
257    // FIXME: Deal with warnings?
258    return Visit(E->getSubExpr());
259  }
260
261  if (E->getOpcode() == UnaryOperator::AddrOf) {
262    APValue result;
263    if (EvaluateLValue(E->getSubExpr(), result, Info))
264      return result;
265  }
266
267  return APValue();
268}
269
270
271APValue PointerExprEvaluator::VisitCastExpr(const CastExpr* E) {
272  const Expr* SubExpr = E->getSubExpr();
273
274   // Check for pointer->pointer cast
275  if (SubExpr->getType()->isPointerType()) {
276    APValue Result;
277    if (EvaluatePointer(SubExpr, Result, Info))
278      return Result;
279    return APValue();
280  }
281
282  if (SubExpr->getType()->isIntegralType()) {
283    llvm::APSInt Result(32);
284    if (EvaluateInteger(SubExpr, Result, Info)) {
285      Result.extOrTrunc((unsigned)Info.Ctx.getTypeSize(E->getType()));
286      return APValue(0, Result.getZExtValue());
287    }
288  }
289
290  if (SubExpr->getType()->isFunctionType() ||
291      SubExpr->getType()->isArrayType()) {
292    APValue Result;
293    if (EvaluateLValue(SubExpr, Result, Info))
294      return Result;
295    return APValue();
296  }
297
298  //assert(0 && "Unhandled cast");
299  return APValue();
300}
301
302APValue PointerExprEvaluator::VisitConditionalOperator(ConditionalOperator *E) {
303  bool BoolResult;
304  if (!HandleConversionToBool(E->getCond(), BoolResult, Info))
305    return APValue();
306
307  Expr* EvalExpr = BoolResult ? E->getTrueExpr() : E->getFalseExpr();
308
309  APValue Result;
310  if (EvaluatePointer(EvalExpr, Result, Info))
311    return Result;
312  return APValue();
313}
314
315//===----------------------------------------------------------------------===//
316// Integer Evaluation
317//===----------------------------------------------------------------------===//
318
319namespace {
320class VISIBILITY_HIDDEN IntExprEvaluator
321  : public StmtVisitor<IntExprEvaluator, bool> {
322  EvalInfo &Info;
323  APSInt &Result;
324public:
325  IntExprEvaluator(EvalInfo &info, APSInt &result)
326    : Info(info), Result(result) {}
327
328  unsigned getIntTypeSizeInBits(QualType T) const {
329    return (unsigned)Info.Ctx.getIntWidth(T);
330  }
331
332  bool Extension(SourceLocation L, diag::kind D, const Expr *E) {
333    Info.EvalResult.DiagLoc = L;
334    Info.EvalResult.Diag = D;
335    Info.EvalResult.DiagExpr = E;
336    return true;  // still a constant.
337  }
338
339  bool Error(SourceLocation L, diag::kind D, const Expr *E) {
340    // If this is in an unevaluated portion of the subexpression, ignore the
341    // error.
342    if (Info.ShortCircuit) {
343      // If error is ignored because the value isn't evaluated, get the real
344      // type at least to prevent errors downstream.
345      Result.zextOrTrunc(getIntTypeSizeInBits(E->getType()));
346      Result.setIsUnsigned(E->getType()->isUnsignedIntegerType());
347      return true;
348    }
349
350    // Take the first error.
351    if (Info.EvalResult.Diag == 0) {
352      Info.EvalResult.DiagLoc = L;
353      Info.EvalResult.Diag = D;
354      Info.EvalResult.DiagExpr = E;
355    }
356    return false;
357  }
358
359  //===--------------------------------------------------------------------===//
360  //                            Visitor Methods
361  //===--------------------------------------------------------------------===//
362
363  bool VisitStmt(Stmt *) {
364    assert(0 && "This should be called on integers, stmts are not integers");
365    return false;
366  }
367
368  bool VisitExpr(Expr *E) {
369    return Error(E->getLocStart(), diag::note_invalid_subexpr_in_ice, E);
370  }
371
372  bool VisitParenExpr(ParenExpr *E) { return Visit(E->getSubExpr()); }
373
374  bool VisitIntegerLiteral(const IntegerLiteral *E) {
375    Result = E->getValue();
376    Result.setIsUnsigned(E->getType()->isUnsignedIntegerType());
377    return true;
378  }
379  bool VisitCharacterLiteral(const CharacterLiteral *E) {
380    Result.zextOrTrunc(getIntTypeSizeInBits(E->getType()));
381    Result = E->getValue();
382    Result.setIsUnsigned(E->getType()->isUnsignedIntegerType());
383    return true;
384  }
385  bool VisitTypesCompatibleExpr(const TypesCompatibleExpr *E) {
386    Result.zextOrTrunc(getIntTypeSizeInBits(E->getType()));
387    // Per gcc docs "this built-in function ignores top level
388    // qualifiers".  We need to use the canonical version to properly
389    // be able to strip CRV qualifiers from the type.
390    QualType T0 = Info.Ctx.getCanonicalType(E->getArgType1());
391    QualType T1 = Info.Ctx.getCanonicalType(E->getArgType2());
392    Result = Info.Ctx.typesAreCompatible(T0.getUnqualifiedType(),
393                                         T1.getUnqualifiedType());
394    return true;
395  }
396  bool VisitDeclRefExpr(const DeclRefExpr *E);
397  bool VisitCallExpr(const CallExpr *E);
398  bool VisitBinaryOperator(const BinaryOperator *E);
399  bool VisitUnaryOperator(const UnaryOperator *E);
400  bool VisitConditionalOperator(const ConditionalOperator *E);
401
402  bool VisitCastExpr(CastExpr* E) {
403    return HandleCast(E);
404  }
405  bool VisitSizeOfAlignOfExpr(const SizeOfAlignOfExpr *E);
406
407  bool VisitCXXBoolLiteralExpr(const CXXBoolLiteralExpr *E) {
408    Result.zextOrTrunc(getIntTypeSizeInBits(E->getType()));
409    Result = E->getValue();
410    Result.setIsUnsigned(E->getType()->isUnsignedIntegerType());
411    return true;
412  }
413
414  bool VisitCXXZeroInitValueExpr(const CXXZeroInitValueExpr *E) {
415    Result = APSInt::getNullValue(getIntTypeSizeInBits(E->getType()));
416    Result.setIsUnsigned(E->getType()->isUnsignedIntegerType());
417    return true;
418  }
419
420private:
421  bool HandleCast(CastExpr* E);
422};
423} // end anonymous namespace
424
425static bool EvaluateInteger(const Expr* E, APSInt &Result, EvalInfo &Info) {
426  return IntExprEvaluator(Info, Result).Visit(const_cast<Expr*>(E));
427}
428
429bool IntExprEvaluator::VisitDeclRefExpr(const DeclRefExpr *E) {
430  // Enums are integer constant exprs.
431  if (const EnumConstantDecl *D = dyn_cast<EnumConstantDecl>(E->getDecl())) {
432    Result = D->getInitVal();
433    return true;
434  }
435
436  // Otherwise, random variable references are not constants.
437  return Error(E->getLocStart(), diag::note_invalid_subexpr_in_ice, E);
438}
439
440/// EvaluateBuiltinClassifyType - Evaluate __builtin_classify_type the same way
441/// as GCC.
442static int EvaluateBuiltinClassifyType(const CallExpr *E) {
443  // The following enum mimics the values returned by GCC.
444  enum gcc_type_class {
445    no_type_class = -1,
446    void_type_class, integer_type_class, char_type_class,
447    enumeral_type_class, boolean_type_class,
448    pointer_type_class, reference_type_class, offset_type_class,
449    real_type_class, complex_type_class,
450    function_type_class, method_type_class,
451    record_type_class, union_type_class,
452    array_type_class, string_type_class,
453    lang_type_class
454  };
455
456  // If no argument was supplied, default to "no_type_class". This isn't
457  // ideal, however it is what gcc does.
458  if (E->getNumArgs() == 0)
459    return no_type_class;
460
461  QualType ArgTy = E->getArg(0)->getType();
462  if (ArgTy->isVoidType())
463    return void_type_class;
464  else if (ArgTy->isEnumeralType())
465    return enumeral_type_class;
466  else if (ArgTy->isBooleanType())
467    return boolean_type_class;
468  else if (ArgTy->isCharType())
469    return string_type_class; // gcc doesn't appear to use char_type_class
470  else if (ArgTy->isIntegerType())
471    return integer_type_class;
472  else if (ArgTy->isPointerType())
473    return pointer_type_class;
474  else if (ArgTy->isReferenceType())
475    return reference_type_class;
476  else if (ArgTy->isRealType())
477    return real_type_class;
478  else if (ArgTy->isComplexType())
479    return complex_type_class;
480  else if (ArgTy->isFunctionType())
481    return function_type_class;
482  else if (ArgTy->isStructureType())
483    return record_type_class;
484  else if (ArgTy->isUnionType())
485    return union_type_class;
486  else if (ArgTy->isArrayType())
487    return array_type_class;
488  else if (ArgTy->isUnionType())
489    return union_type_class;
490  else  // FIXME: offset_type_class, method_type_class, & lang_type_class?
491    assert(0 && "CallExpr::isBuiltinClassifyType(): unimplemented type");
492  return -1;
493}
494
495bool IntExprEvaluator::VisitCallExpr(const CallExpr *E) {
496  Result.zextOrTrunc(getIntTypeSizeInBits(E->getType()));
497
498  switch (E->isBuiltinCall()) {
499  default:
500    return Error(E->getLocStart(), diag::note_invalid_subexpr_in_ice, E);
501  case Builtin::BI__builtin_classify_type:
502    Result.setIsSigned(true);
503    Result = EvaluateBuiltinClassifyType(E);
504    return true;
505
506  case Builtin::BI__builtin_constant_p:
507    // __builtin_constant_p always has one operand: it returns true if that
508    // operand can be folded, false otherwise.
509    Result = E->getArg(0)->isEvaluatable(Info.Ctx);
510    return true;
511  }
512}
513
514bool IntExprEvaluator::VisitBinaryOperator(const BinaryOperator *E) {
515  if (E->getOpcode() == BinaryOperator::Comma) {
516    if (!Visit(E->getRHS()))
517      return false;
518
519    if (!Info.ShortCircuit) {
520      // If we can't evaluate the LHS, it must be because it has
521      // side effects.
522      if (!E->getLHS()->isEvaluatable(Info.Ctx))
523        Info.EvalResult.HasSideEffects = true;
524
525      return Extension(E->getOperatorLoc(), diag::note_comma_in_ice, E);
526    }
527
528    return true;
529  }
530
531  if (E->isLogicalOp()) {
532    // These need to be handled specially because the operands aren't
533    // necessarily integral
534    bool lhsResult, rhsResult;
535
536    if (HandleConversionToBool(E->getLHS(), lhsResult, Info)) {
537      // We were able to evaluate the LHS, see if we can get away with not
538      // evaluating the RHS: 0 && X -> 0, 1 || X -> 1
539      if (lhsResult == (E->getOpcode() == BinaryOperator::LOr) ||
540          !lhsResult == (E->getOpcode() == BinaryOperator::LAnd)) {
541        Result.zextOrTrunc(getIntTypeSizeInBits(E->getType()));
542        Result.setIsUnsigned(E->getType()->isUnsignedIntegerType());
543        Result = lhsResult;
544
545        Info.ShortCircuit++;
546        bool rhsEvaluated = HandleConversionToBool(E->getRHS(), rhsResult, Info);
547        Info.ShortCircuit--;
548
549        if (rhsEvaluated)
550          return true;
551
552        // FIXME: Return an extension warning saying that the RHS could not be
553        // evaluated.
554        return true;
555      }
556
557      if (HandleConversionToBool(E->getRHS(), rhsResult, Info)) {
558        Result.zextOrTrunc(getIntTypeSizeInBits(E->getType()));
559        Result.setIsUnsigned(E->getType()->isUnsignedIntegerType());
560        if (E->getOpcode() == BinaryOperator::LOr)
561          Result = lhsResult || rhsResult;
562        else
563          Result = lhsResult && rhsResult;
564        return true;
565      }
566    } else {
567      if (HandleConversionToBool(E->getRHS(), rhsResult, Info)) {
568        // We can't evaluate the LHS; however, sometimes the result
569        // is determined by the RHS: X && 0 -> 0, X || 1 -> 1.
570        if (rhsResult == (E->getOpcode() == BinaryOperator::LOr) ||
571            !rhsResult == (E->getOpcode() == BinaryOperator::LAnd)) {
572          Result.zextOrTrunc(getIntTypeSizeInBits(E->getType()));
573          Result.setIsUnsigned(E->getType()->isUnsignedIntegerType());
574          Result = rhsResult;
575
576          // Since we werent able to evaluate the left hand side, it
577          // must have had side effects.
578          Info.EvalResult.HasSideEffects = true;
579
580          return true;
581        }
582      }
583    }
584
585    return false;
586  }
587
588  QualType LHSTy = E->getLHS()->getType();
589  QualType RHSTy = E->getRHS()->getType();
590
591  if (LHSTy->isRealFloatingType() &&
592      RHSTy->isRealFloatingType()) {
593    APFloat RHS(0.0), LHS(0.0);
594
595    if (!EvaluateFloat(E->getRHS(), RHS, Info))
596      return false;
597
598    if (!EvaluateFloat(E->getLHS(), LHS, Info))
599      return false;
600
601    APFloat::cmpResult CR = LHS.compare(RHS);
602
603    Result.zextOrTrunc(getIntTypeSizeInBits(E->getType()));
604
605    switch (E->getOpcode()) {
606    default:
607      assert(0 && "Invalid binary operator!");
608    case BinaryOperator::LT:
609      Result = CR == APFloat::cmpLessThan;
610      break;
611    case BinaryOperator::GT:
612      Result = CR == APFloat::cmpGreaterThan;
613      break;
614    case BinaryOperator::LE:
615      Result = CR == APFloat::cmpLessThan || CR == APFloat::cmpEqual;
616      break;
617    case BinaryOperator::GE:
618      Result = CR == APFloat::cmpGreaterThan || CR == APFloat::cmpEqual;
619      break;
620    case BinaryOperator::EQ:
621      Result = CR == APFloat::cmpEqual;
622      break;
623    case BinaryOperator::NE:
624      Result = CR == APFloat::cmpGreaterThan || CR == APFloat::cmpLessThan;
625      break;
626    }
627
628    Result.setIsUnsigned(E->getType()->isUnsignedIntegerType());
629    return true;
630  }
631
632  if (E->getOpcode() == BinaryOperator::Sub) {
633    if (LHSTy->isPointerType() && RHSTy->isPointerType()) {
634      APValue LHSValue;
635      if (!EvaluatePointer(E->getLHS(), LHSValue, Info))
636        return false;
637
638      APValue RHSValue;
639      if (!EvaluatePointer(E->getRHS(), RHSValue, Info))
640        return false;
641
642      // FIXME: Is this correct? What if only one of the operands has a base?
643      if (LHSValue.getLValueBase() || RHSValue.getLValueBase())
644        return false;
645
646      const QualType Type = E->getLHS()->getType();
647      const QualType ElementType = Type->getAsPointerType()->getPointeeType();
648
649      uint64_t D = LHSValue.getLValueOffset() - RHSValue.getLValueOffset();
650      D /= Info.Ctx.getTypeSize(ElementType) / 8;
651
652      Result.zextOrTrunc(getIntTypeSizeInBits(E->getType()));
653      Result = D;
654      Result.setIsUnsigned(E->getType()->isUnsignedIntegerType());
655
656      return true;
657    }
658  }
659  if (!LHSTy->isIntegralType() ||
660      !RHSTy->isIntegralType()) {
661    // We can't continue from here for non-integral types, and they
662    // could potentially confuse the following operations.
663    // FIXME: Deal with EQ and friends.
664    return false;
665  }
666
667  // The LHS of a constant expr is always evaluated and needed.
668  llvm::APSInt RHS(32);
669  if (!Visit(E->getLHS())) {
670    return false; // error in subexpression.
671  }
672
673
674  // FIXME Maybe we want to succeed even where we can't evaluate the
675  // right side of LAnd/LOr?
676  // For example, see http://llvm.org/bugs/show_bug.cgi?id=2525
677  if (!EvaluateInteger(E->getRHS(), RHS, Info))
678    return false;
679
680  switch (E->getOpcode()) {
681  default:
682    return Error(E->getOperatorLoc(), diag::note_invalid_subexpr_in_ice, E);
683  case BinaryOperator::Mul: Result *= RHS; return true;
684  case BinaryOperator::Add: Result += RHS; return true;
685  case BinaryOperator::Sub: Result -= RHS; return true;
686  case BinaryOperator::And: Result &= RHS; return true;
687  case BinaryOperator::Xor: Result ^= RHS; return true;
688  case BinaryOperator::Or:  Result |= RHS; return true;
689  case BinaryOperator::Div:
690    if (RHS == 0)
691      return Error(E->getOperatorLoc(), diag::note_expr_divide_by_zero, E);
692    Result /= RHS;
693    break;
694  case BinaryOperator::Rem:
695    if (RHS == 0)
696      return Error(E->getOperatorLoc(), diag::note_expr_divide_by_zero, E);
697    Result %= RHS;
698    break;
699  case BinaryOperator::Shl:
700    // FIXME: Warn about out of range shift amounts!
701    Result <<= (unsigned)RHS.getLimitedValue(Result.getBitWidth()-1);
702    break;
703  case BinaryOperator::Shr:
704    Result >>= (unsigned)RHS.getLimitedValue(Result.getBitWidth()-1);
705    break;
706
707  case BinaryOperator::LT:
708    Result = Result < RHS;
709    Result.zextOrTrunc(getIntTypeSizeInBits(E->getType()));
710    break;
711  case BinaryOperator::GT:
712    Result = Result > RHS;
713    Result.zextOrTrunc(getIntTypeSizeInBits(E->getType()));
714    break;
715  case BinaryOperator::LE:
716    Result = Result <= RHS;
717    Result.zextOrTrunc(getIntTypeSizeInBits(E->getType()));
718    break;
719  case BinaryOperator::GE:
720    Result = Result >= RHS;
721    Result.zextOrTrunc(getIntTypeSizeInBits(E->getType()));
722    break;
723  case BinaryOperator::EQ:
724    Result = Result == RHS;
725    Result.zextOrTrunc(getIntTypeSizeInBits(E->getType()));
726    break;
727  case BinaryOperator::NE:
728    Result = Result != RHS;
729    Result.zextOrTrunc(getIntTypeSizeInBits(E->getType()));
730    break;
731  case BinaryOperator::LAnd:
732    Result = Result != 0 && RHS != 0;
733    Result.zextOrTrunc(getIntTypeSizeInBits(E->getType()));
734    break;
735  case BinaryOperator::LOr:
736    Result = Result != 0 || RHS != 0;
737    Result.zextOrTrunc(getIntTypeSizeInBits(E->getType()));
738    break;
739  }
740
741  Result.setIsUnsigned(E->getType()->isUnsignedIntegerType());
742  return true;
743}
744
745bool IntExprEvaluator::VisitConditionalOperator(const ConditionalOperator *E) {
746  bool Cond;
747  if (!HandleConversionToBool(E->getCond(), Cond, Info))
748    return false;
749
750  return Visit(Cond ? E->getTrueExpr() : E->getFalseExpr());
751}
752
753/// VisitSizeAlignOfExpr - Evaluate a sizeof or alignof with a result as the
754/// expression's type.
755bool IntExprEvaluator::VisitSizeOfAlignOfExpr(const SizeOfAlignOfExpr *E) {
756  QualType DstTy = E->getType();
757  // Return the result in the right width.
758  Result.zextOrTrunc(getIntTypeSizeInBits(DstTy));
759  Result.setIsUnsigned(DstTy->isUnsignedIntegerType());
760
761  QualType SrcTy = E->getTypeOfArgument();
762
763  // sizeof(void) and __alignof__(void) = 1 as a gcc extension.
764  if (SrcTy->isVoidType()) {
765    Result = 1;
766    return true;
767  }
768
769  // sizeof(vla) is not a constantexpr: C99 6.5.3.4p2.
770  // FIXME: But alignof(vla) is!
771  if (!SrcTy->isConstantSizeType()) {
772    // FIXME: Should we attempt to evaluate this?
773    return false;
774  }
775
776  bool isSizeOf = E->isSizeOf();
777
778  // GCC extension: sizeof(function) = 1.
779  if (SrcTy->isFunctionType()) {
780    // FIXME: AlignOf shouldn't be unconditionally 4!
781    Result = isSizeOf ? 1 : 4;
782    return true;
783  }
784
785  // Get information about the size or align.
786  unsigned CharSize = Info.Ctx.Target.getCharWidth();
787  if (isSizeOf)
788    Result = Info.Ctx.getTypeSize(SrcTy) / CharSize;
789  else
790    Result = Info.Ctx.getTypeAlign(SrcTy) / CharSize;
791  return true;
792}
793
794bool IntExprEvaluator::VisitUnaryOperator(const UnaryOperator *E) {
795  // Special case unary operators that do not need their subexpression
796  // evaluated.  offsetof/sizeof/alignof are all special.
797  if (E->isOffsetOfOp()) {
798    Result.zextOrTrunc(getIntTypeSizeInBits(E->getType()));
799    Result = E->evaluateOffsetOf(Info.Ctx);
800    Result.setIsUnsigned(E->getType()->isUnsignedIntegerType());
801    return true;
802  }
803
804  if (E->getOpcode() == UnaryOperator::LNot) {
805    // LNot's operand isn't necessarily an integer, so we handle it specially.
806    bool bres;
807    if (!HandleConversionToBool(E->getSubExpr(), bres, Info))
808      return false;
809    Result.zextOrTrunc(getIntTypeSizeInBits(E->getType()));
810    Result.setIsUnsigned(E->getType()->isUnsignedIntegerType());
811    Result = !bres;
812    return true;
813  }
814
815  // Get the operand value into 'Result'.
816  if (!Visit(E->getSubExpr()))
817    return false;
818
819  switch (E->getOpcode()) {
820  default:
821    // Address, indirect, pre/post inc/dec, etc are not valid constant exprs.
822    // See C99 6.6p3.
823    return Error(E->getOperatorLoc(), diag::note_invalid_subexpr_in_ice, E);
824  case UnaryOperator::Extension:
825    // FIXME: Should extension allow i-c-e extension expressions in its scope?
826    // If so, we could clear the diagnostic ID.
827  case UnaryOperator::Plus:
828    // The result is always just the subexpr.
829    break;
830  case UnaryOperator::Minus:
831    Result = -Result;
832    break;
833  case UnaryOperator::Not:
834    Result = ~Result;
835    break;
836  }
837
838  Result.setIsUnsigned(E->getType()->isUnsignedIntegerType());
839  return true;
840}
841
842/// HandleCast - This is used to evaluate implicit or explicit casts where the
843/// result type is integer.
844bool IntExprEvaluator::HandleCast(CastExpr *E) {
845  Expr *SubExpr = E->getSubExpr();
846  QualType DestType = E->getType();
847
848  unsigned DestWidth = getIntTypeSizeInBits(DestType);
849
850  if (DestType->isBooleanType()) {
851    bool BoolResult;
852    if (!HandleConversionToBool(SubExpr, BoolResult, Info))
853      return false;
854    Result.zextOrTrunc(DestWidth);
855    Result.setIsUnsigned(DestType->isUnsignedIntegerType());
856    Result = BoolResult;
857    return true;
858  }
859
860  // Handle simple integer->integer casts.
861  if (SubExpr->getType()->isIntegralType()) {
862    if (!Visit(SubExpr))
863      return false;
864
865    // Figure out if this is a truncate, extend or noop cast.
866    // If the input is signed, do a sign extend, noop, or truncate.
867    Result.extOrTrunc(DestWidth);
868    Result.setIsUnsigned(DestType->isUnsignedIntegerType());
869    return true;
870  }
871
872  // FIXME: Clean this up!
873  if (SubExpr->getType()->isPointerType()) {
874    APValue LV;
875    if (!EvaluatePointer(SubExpr, LV, Info))
876      return false;
877
878    if (LV.getLValueBase())
879      return false;
880
881    Result.extOrTrunc(DestWidth);
882    Result = LV.getLValueOffset();
883    Result.setIsUnsigned(DestType->isUnsignedIntegerType());
884    return true;
885  }
886
887  if (!SubExpr->getType()->isRealFloatingType())
888    return Error(E->getExprLoc(), diag::note_invalid_subexpr_in_ice, E);
889
890  APFloat F(0.0);
891  if (!EvaluateFloat(SubExpr, F, Info))
892    return Error(E->getExprLoc(), diag::note_invalid_subexpr_in_ice, E);
893
894  // Determine whether we are converting to unsigned or signed.
895  bool DestSigned = DestType->isSignedIntegerType();
896
897  // FIXME: Warning for overflow.
898  uint64_t Space[4];
899  bool ignored;
900  (void)F.convertToInteger(Space, DestWidth, DestSigned,
901                           llvm::APFloat::rmTowardZero, &ignored);
902  Result = llvm::APInt(DestWidth, 4, Space);
903  Result.setIsUnsigned(!DestSigned);
904  return true;
905}
906
907//===----------------------------------------------------------------------===//
908// Float Evaluation
909//===----------------------------------------------------------------------===//
910
911namespace {
912class VISIBILITY_HIDDEN FloatExprEvaluator
913  : public StmtVisitor<FloatExprEvaluator, bool> {
914  EvalInfo &Info;
915  APFloat &Result;
916public:
917  FloatExprEvaluator(EvalInfo &info, APFloat &result)
918    : Info(info), Result(result) {}
919
920  bool VisitStmt(Stmt *S) {
921    return false;
922  }
923
924  bool VisitParenExpr(ParenExpr *E) { return Visit(E->getSubExpr()); }
925  bool VisitCallExpr(const CallExpr *E);
926
927  bool VisitUnaryOperator(const UnaryOperator *E);
928  bool VisitBinaryOperator(const BinaryOperator *E);
929  bool VisitFloatingLiteral(const FloatingLiteral *E);
930  bool VisitCastExpr(CastExpr *E);
931  bool VisitCXXZeroInitValueExpr(CXXZeroInitValueExpr *E);
932};
933} // end anonymous namespace
934
935static bool EvaluateFloat(const Expr* E, APFloat& Result, EvalInfo &Info) {
936  return FloatExprEvaluator(Info, Result).Visit(const_cast<Expr*>(E));
937}
938
939bool FloatExprEvaluator::VisitCallExpr(const CallExpr *E) {
940  switch (E->isBuiltinCall()) {
941  default: return false;
942  case Builtin::BI__builtin_huge_val:
943  case Builtin::BI__builtin_huge_valf:
944  case Builtin::BI__builtin_huge_vall:
945  case Builtin::BI__builtin_inf:
946  case Builtin::BI__builtin_inff:
947  case Builtin::BI__builtin_infl: {
948    const llvm::fltSemantics &Sem =
949      Info.Ctx.getFloatTypeSemantics(E->getType());
950    Result = llvm::APFloat::getInf(Sem);
951    return true;
952  }
953
954  case Builtin::BI__builtin_nan:
955  case Builtin::BI__builtin_nanf:
956  case Builtin::BI__builtin_nanl:
957    // If this is __builtin_nan("") turn this into a simple nan, otherwise we
958    // can't constant fold it.
959    if (const StringLiteral *S =
960        dyn_cast<StringLiteral>(E->getArg(0)->IgnoreParenCasts())) {
961      if (!S->isWide() && S->getByteLength() == 0) { // empty string.
962        const llvm::fltSemantics &Sem =
963          Info.Ctx.getFloatTypeSemantics(E->getType());
964        Result = llvm::APFloat::getNaN(Sem);
965        return true;
966      }
967    }
968    return false;
969
970  case Builtin::BI__builtin_fabs:
971  case Builtin::BI__builtin_fabsf:
972  case Builtin::BI__builtin_fabsl:
973    if (!EvaluateFloat(E->getArg(0), Result, Info))
974      return false;
975
976    if (Result.isNegative())
977      Result.changeSign();
978    return true;
979
980  case Builtin::BI__builtin_copysign:
981  case Builtin::BI__builtin_copysignf:
982  case Builtin::BI__builtin_copysignl: {
983    APFloat RHS(0.);
984    if (!EvaluateFloat(E->getArg(0), Result, Info) ||
985        !EvaluateFloat(E->getArg(1), RHS, Info))
986      return false;
987    Result.copySign(RHS);
988    return true;
989  }
990  }
991}
992
993bool FloatExprEvaluator::VisitUnaryOperator(const UnaryOperator *E) {
994  if (E->getOpcode() == UnaryOperator::Deref)
995    return false;
996
997  if (!EvaluateFloat(E->getSubExpr(), Result, Info))
998    return false;
999
1000  switch (E->getOpcode()) {
1001  default: return false;
1002  case UnaryOperator::Plus:
1003    return true;
1004  case UnaryOperator::Minus:
1005    Result.changeSign();
1006    return true;
1007  }
1008}
1009
1010bool FloatExprEvaluator::VisitBinaryOperator(const BinaryOperator *E) {
1011  // FIXME: Diagnostics?  I really don't understand how the warnings
1012  // and errors are supposed to work.
1013  APFloat RHS(0.0);
1014  if (!EvaluateFloat(E->getLHS(), Result, Info))
1015    return false;
1016  if (!EvaluateFloat(E->getRHS(), RHS, Info))
1017    return false;
1018
1019  switch (E->getOpcode()) {
1020  default: return false;
1021  case BinaryOperator::Mul:
1022    Result.multiply(RHS, APFloat::rmNearestTiesToEven);
1023    return true;
1024  case BinaryOperator::Add:
1025    Result.add(RHS, APFloat::rmNearestTiesToEven);
1026    return true;
1027  case BinaryOperator::Sub:
1028    Result.subtract(RHS, APFloat::rmNearestTiesToEven);
1029    return true;
1030  case BinaryOperator::Div:
1031    Result.divide(RHS, APFloat::rmNearestTiesToEven);
1032    return true;
1033  case BinaryOperator::Rem:
1034    Result.mod(RHS, APFloat::rmNearestTiesToEven);
1035    return true;
1036  }
1037}
1038
1039bool FloatExprEvaluator::VisitFloatingLiteral(const FloatingLiteral *E) {
1040  Result = E->getValue();
1041  return true;
1042}
1043
1044bool FloatExprEvaluator::VisitCastExpr(CastExpr *E) {
1045  Expr* SubExpr = E->getSubExpr();
1046  const llvm::fltSemantics& destSemantics =
1047      Info.Ctx.getFloatTypeSemantics(E->getType());
1048  if (SubExpr->getType()->isIntegralType()) {
1049    APSInt IntResult;
1050    if (!EvaluateInteger(E, IntResult, Info))
1051      return false;
1052    Result = APFloat(destSemantics, 1);
1053    Result.convertFromAPInt(IntResult, IntResult.isSigned(),
1054                            APFloat::rmNearestTiesToEven);
1055    return true;
1056  }
1057  if (SubExpr->getType()->isRealFloatingType()) {
1058    if (!Visit(SubExpr))
1059      return false;
1060    bool ignored;
1061    Result.convert(destSemantics, APFloat::rmNearestTiesToEven, &ignored);
1062    return true;
1063  }
1064
1065  return false;
1066}
1067
1068bool FloatExprEvaluator::VisitCXXZeroInitValueExpr(CXXZeroInitValueExpr *E) {
1069  Result = APFloat::getZero(Info.Ctx.getFloatTypeSemantics(E->getType()));
1070  return true;
1071}
1072
1073//===----------------------------------------------------------------------===//
1074// Complex Float Evaluation
1075//===----------------------------------------------------------------------===//
1076
1077namespace {
1078class VISIBILITY_HIDDEN ComplexFloatExprEvaluator
1079  : public StmtVisitor<ComplexFloatExprEvaluator, APValue> {
1080  EvalInfo &Info;
1081
1082public:
1083  ComplexFloatExprEvaluator(EvalInfo &info) : Info(info) {}
1084
1085  //===--------------------------------------------------------------------===//
1086  //                            Visitor Methods
1087  //===--------------------------------------------------------------------===//
1088
1089  APValue VisitStmt(Stmt *S) {
1090    return APValue();
1091  }
1092
1093  APValue VisitParenExpr(ParenExpr *E) { return Visit(E->getSubExpr()); }
1094
1095  APValue VisitImaginaryLiteral(ImaginaryLiteral *E) {
1096    APFloat Result(0.0);
1097    if (!EvaluateFloat(E->getSubExpr(), Result, Info))
1098      return APValue();
1099
1100    return APValue(APFloat(0.0), Result);
1101  }
1102
1103  APValue VisitCastExpr(CastExpr *E) {
1104    Expr* SubExpr = E->getSubExpr();
1105
1106    if (SubExpr->getType()->isRealFloatingType()) {
1107      APFloat Result(0.0);
1108
1109      if (!EvaluateFloat(SubExpr, Result, Info))
1110        return APValue();
1111
1112      return APValue(Result, APFloat(0.0));
1113    }
1114
1115    // FIXME: Handle more casts.
1116    return APValue();
1117  }
1118
1119  APValue VisitBinaryOperator(const BinaryOperator *E);
1120
1121};
1122} // end anonymous namespace
1123
1124static bool EvaluateComplexFloat(const Expr *E, APValue &Result, EvalInfo &Info)
1125{
1126  Result = ComplexFloatExprEvaluator(Info).Visit(const_cast<Expr*>(E));
1127  return Result.isComplexFloat();
1128}
1129
1130APValue ComplexFloatExprEvaluator::VisitBinaryOperator(const BinaryOperator *E)
1131{
1132  APValue Result, RHS;
1133
1134  if (!EvaluateComplexFloat(E->getLHS(), Result, Info))
1135    return APValue();
1136
1137  if (!EvaluateComplexFloat(E->getRHS(), RHS, Info))
1138    return APValue();
1139
1140  switch (E->getOpcode()) {
1141  default: return APValue();
1142  case BinaryOperator::Add:
1143    Result.getComplexFloatReal().add(RHS.getComplexFloatReal(),
1144                                     APFloat::rmNearestTiesToEven);
1145    Result.getComplexFloatImag().add(RHS.getComplexFloatImag(),
1146                                     APFloat::rmNearestTiesToEven);
1147  case BinaryOperator::Sub:
1148    Result.getComplexFloatReal().subtract(RHS.getComplexFloatReal(),
1149                                          APFloat::rmNearestTiesToEven);
1150    Result.getComplexFloatImag().subtract(RHS.getComplexFloatImag(),
1151                                          APFloat::rmNearestTiesToEven);
1152  }
1153
1154  return Result;
1155}
1156
1157//===----------------------------------------------------------------------===//
1158// Top level Expr::Evaluate method.
1159//===----------------------------------------------------------------------===//
1160
1161/// Evaluate - Return true if this is a constant which we can fold using
1162/// any crazy technique (that has nothing to do with language standards) that
1163/// we want to.  If this function returns true, it returns the folded constant
1164/// in Result.
1165bool Expr::Evaluate(EvalResult &Result, ASTContext &Ctx) const {
1166  EvalInfo Info(Ctx, Result);
1167
1168  if (getType()->isIntegerType()) {
1169    llvm::APSInt sInt(32);
1170    if (!EvaluateInteger(this, sInt, Info))
1171      return false;
1172
1173    Result.Val = APValue(sInt);
1174  } else if (getType()->isPointerType()) {
1175    if (!EvaluatePointer(this, Result.Val, Info))
1176      return false;
1177  } else if (getType()->isRealFloatingType()) {
1178    llvm::APFloat f(0.0);
1179    if (!EvaluateFloat(this, f, Info))
1180      return false;
1181
1182    Result.Val = APValue(f);
1183  } else if (getType()->isComplexType()) {
1184    if (!EvaluateComplexFloat(this, Result.Val, Info))
1185      return false;
1186  }  else
1187    return false;
1188
1189  return true;
1190}
1191
1192bool Expr::Evaluate(APValue &Result, ASTContext &Ctx, bool *isEvaluated) const {
1193  EvalResult EvalResult;
1194
1195  if (!Evaluate(EvalResult, Ctx))
1196    return false;
1197
1198  Result = EvalResult.Val;
1199  if (isEvaluated)
1200    *isEvaluated = !EvalResult.HasSideEffects;
1201
1202  return true;
1203}
1204
1205/// isEvaluatable - Call Evaluate to see if this expression can be constant
1206/// folded, but discard the result.
1207bool Expr::isEvaluatable(ASTContext &Ctx) const {
1208  EvalResult Result;
1209  return Evaluate(Result, Ctx) && !Result.HasSideEffects;
1210}
1211
1212APSInt Expr::EvaluateAsInt(ASTContext &Ctx) const {
1213  APValue V;
1214  bool Result = Evaluate(V, Ctx);
1215  assert(Result && "Could not evaluate expression");
1216  assert(V.isInt() && "Expression did not evaluate to integer");
1217
1218  return V.getInt();
1219}
1220