ExprConstant.cpp revision 2eb0ddc1baaee173ea0dccf2a4edef48638b902d
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/Expr.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; 23 24#define USE_NEW_EVALUATOR 1 25 26static bool CalcFakeICEVal(const Expr *Expr, 27 llvm::APSInt &Result, 28 ASTContext &Context) { 29 // Calculate the value of an expression that has a calculatable 30 // value, but isn't an ICE. Currently, this only supports 31 // a very narrow set of extensions, but it can be expanded if needed. 32 if (const ParenExpr *PE = dyn_cast<ParenExpr>(Expr)) 33 return CalcFakeICEVal(PE->getSubExpr(), Result, Context); 34 35 if (const CastExpr *CE = dyn_cast<CastExpr>(Expr)) { 36 QualType CETy = CE->getType(); 37 if ((CETy->isIntegralType() && !CETy->isBooleanType()) || 38 CETy->isPointerType()) { 39 if (CalcFakeICEVal(CE->getSubExpr(), Result, Context)) { 40 Result.extOrTrunc(Context.getTypeSize(CETy)); 41 // FIXME: This assumes pointers are signed. 42 Result.setIsSigned(CETy->isSignedIntegerType() || 43 CETy->isPointerType()); 44 return true; 45 } 46 } 47 } 48 49 if (Expr->getType()->isIntegralType()) 50 return Expr->isIntegerConstantExpr(Result, Context); 51 52 return false; 53} 54 55/// EvalInfo - This is a private struct used by the evaluator to capture 56/// information about a subexpression as it is folded. It retains information 57/// about the AST context, but also maintains information about the folded 58/// expression. 59/// 60/// If an expression could be evaluated, it is still possible it is not a C 61/// "integer constant expression" or constant expression. If not, this struct 62/// captures information about how and why not. 63/// 64/// One bit of information passed *into* the request for constant folding 65/// indicates whether the subexpression is "evaluated" or not according to C 66/// rules. For example, the RHS of (0 && foo()) is not evaluated. We can 67/// evaluate the expression regardless of what the RHS is, but C only allows 68/// certain things in certain situations. 69struct EvalInfo { 70 ASTContext &Ctx; 71 72 /// isEvaluated - True if the subexpression is required to be evaluated, false 73 /// if it is short-circuited (according to C rules). 74 bool isEvaluated; 75 76 /// ICEDiag - If the expression is unfoldable, then ICEDiag contains the 77 /// error diagnostic indicating why it is not foldable and DiagLoc indicates a 78 /// caret position for the error. If it is foldable, but the expression is 79 /// not an integer constant expression, ICEDiag contains the extension 80 /// diagnostic to emit which describes why it isn't an integer constant 81 /// expression. If this expression *is* an integer-constant-expr, then 82 /// ICEDiag is zero. 83 /// 84 /// The caller can choose to emit this diagnostic or not, depending on whether 85 /// they require an i-c-e or a constant or not. DiagLoc indicates the caret 86 /// position for the report. 87 /// 88 /// If ICEDiag is zero, then this expression is an i-c-e. 89 unsigned ICEDiag; 90 SourceLocation DiagLoc; 91 92 EvalInfo(ASTContext &ctx) : Ctx(ctx), isEvaluated(true), ICEDiag(0) {} 93}; 94 95 96static bool EvaluatePointer(const Expr *E, APValue &Result, EvalInfo &Info); 97static bool EvaluateInteger(const Expr *E, APSInt &Result, EvalInfo &Info); 98 99 100//===----------------------------------------------------------------------===// 101// Pointer Evaluation 102//===----------------------------------------------------------------------===// 103 104namespace { 105class VISIBILITY_HIDDEN PointerExprEvaluator 106 : public StmtVisitor<PointerExprEvaluator, APValue> { 107 EvalInfo &Info; 108public: 109 110 PointerExprEvaluator(EvalInfo &info) : Info(info) {} 111 112 APValue VisitStmt(Stmt *S) { 113 // FIXME: Remove this when we support more expressions. 114 printf("Unhandled pointer statement\n"); 115 S->dump(); 116 return APValue(); 117 } 118 119 APValue VisitParenExpr(ParenExpr *E) { return Visit(E->getSubExpr()); } 120 121 APValue VisitBinaryOperator(const BinaryOperator *E); 122 APValue VisitCastExpr(const CastExpr* E); 123}; 124} // end anonymous namespace 125 126static bool EvaluatePointer(const Expr* E, APValue& Result, EvalInfo &Info) { 127 if (!E->getType()->isPointerType()) 128 return false; 129 Result = PointerExprEvaluator(Info).Visit(const_cast<Expr*>(E)); 130 return Result.isLValue(); 131} 132 133APValue PointerExprEvaluator::VisitBinaryOperator(const BinaryOperator *E) { 134 if (E->getOpcode() != BinaryOperator::Add && 135 E->getOpcode() != BinaryOperator::Sub) 136 return APValue(); 137 138 const Expr *PExp = E->getLHS(); 139 const Expr *IExp = E->getRHS(); 140 if (IExp->getType()->isPointerType()) 141 std::swap(PExp, IExp); 142 143 APValue ResultLValue; 144 if (!EvaluatePointer(PExp, ResultLValue, Info)) 145 return APValue(); 146 147 llvm::APSInt AdditionalOffset(32); 148 if (!EvaluateInteger(IExp, AdditionalOffset, Info)) 149 return APValue(); 150 151 uint64_t Offset = ResultLValue.getLValueOffset(); 152 if (E->getOpcode() == BinaryOperator::Add) 153 Offset += AdditionalOffset.getZExtValue(); 154 else 155 Offset -= AdditionalOffset.getZExtValue(); 156 157 return APValue(ResultLValue.getLValueBase(), Offset); 158} 159 160 161APValue PointerExprEvaluator::VisitCastExpr(const CastExpr* E) { 162 const Expr* SubExpr = E->getSubExpr(); 163 164 // Check for pointer->pointer cast 165 if (SubExpr->getType()->isPointerType()) { 166 APValue Result; 167 if (EvaluatePointer(SubExpr, Result, Info)) 168 return Result; 169 return APValue(); 170 } 171 172 if (SubExpr->getType()->isIntegralType()) { 173 llvm::APSInt Result(32); 174 if (EvaluateInteger(SubExpr, Result, Info)) { 175 Result.extOrTrunc((unsigned)Info.Ctx.getTypeSize(E->getType())); 176 return APValue(0, Result.getZExtValue()); 177 } 178 } 179 180 assert(0 && "Unhandled cast"); 181 return APValue(); 182} 183 184 185//===----------------------------------------------------------------------===// 186// Integer Evaluation 187//===----------------------------------------------------------------------===// 188 189namespace { 190class VISIBILITY_HIDDEN IntExprEvaluator 191 : public StmtVisitor<IntExprEvaluator, bool> { 192 EvalInfo &Info; 193 APSInt &Result; 194public: 195 IntExprEvaluator(EvalInfo &info, APSInt &result) 196 : Info(info), Result(result) {} 197 198 unsigned getIntTypeSizeInBits(QualType T) const { 199 return (unsigned)Info.Ctx.getIntWidth(T); 200 } 201 202 bool Extension(SourceLocation L, diag::kind D) { 203 Info.DiagLoc = L; 204 Info.ICEDiag = D; 205 return true; // still a constant. 206 } 207 208 bool Error(SourceLocation L, diag::kind D) { 209 // If this is in an unevaluated portion of the subexpression, ignore the 210 // error. 211 if (!Info.isEvaluated) 212 return true; 213 214 Info.DiagLoc = L; 215 Info.ICEDiag = D; 216 return false; 217 } 218 219 //===--------------------------------------------------------------------===// 220 // Visitor Methods 221 //===--------------------------------------------------------------------===// 222 223 bool VisitStmt(Stmt *S) { 224 return Error(S->getLocStart(), diag::err_expr_not_constant); 225 } 226 227 bool VisitParenExpr(ParenExpr *E) { return Visit(E->getSubExpr()); } 228 229 bool VisitIntegerLiteral(const IntegerLiteral *E) { 230 Result = E->getValue(); 231 Result.setIsUnsigned(E->getType()->isUnsignedIntegerType()); 232 return true; 233 } 234 bool VisitCharacterLiteral(const CharacterLiteral *E) { 235 Result.zextOrTrunc(getIntTypeSizeInBits(E->getType())); 236 Result = E->getValue(); 237 Result.setIsUnsigned(E->getType()->isUnsignedIntegerType()); 238 return true; 239 } 240 bool VisitTypesCompatibleExpr(const TypesCompatibleExpr *E) { 241 Result.zextOrTrunc(getIntTypeSizeInBits(E->getType())); 242 Result = Info.Ctx.typesAreCompatible(E->getArgType1(), E->getArgType2()); 243 return true; 244 } 245 bool VisitDeclRefExpr(const DeclRefExpr *E); 246 bool VisitCallExpr(const CallExpr *E); 247 bool VisitBinaryOperator(const BinaryOperator *E); 248 bool VisitUnaryOperator(const UnaryOperator *E); 249 250 bool VisitCastExpr(CastExpr* E) { 251 return HandleCast(E->getLParenLoc(), E->getSubExpr(), E->getType()); 252 } 253 bool VisitImplicitCastExpr(ImplicitCastExpr* E) { 254 return HandleCast(E->getLocStart(), E->getSubExpr(), E->getType()); 255 } 256 bool VisitSizeOfAlignOfTypeExpr(const SizeOfAlignOfTypeExpr *E) { 257 return EvaluateSizeAlignOf(E->isSizeOf(), E->getArgumentType(), 258 E->getType()); 259 } 260 261private: 262 bool HandleCast(SourceLocation CastLoc, Expr *SubExpr, QualType DestType); 263 bool EvaluateSizeAlignOf(bool isSizeOf, QualType SrcTy, QualType DstTy); 264}; 265} // end anonymous namespace 266 267static bool EvaluateInteger(const Expr* E, APSInt &Result, EvalInfo &Info) { 268 return IntExprEvaluator(Info, Result).Visit(const_cast<Expr*>(E)); 269} 270 271bool IntExprEvaluator::VisitDeclRefExpr(const DeclRefExpr *E) { 272 // Enums are integer constant exprs. 273 if (const EnumConstantDecl *D = dyn_cast<EnumConstantDecl>(E->getDecl())) { 274 Result = D->getInitVal(); 275 return true; 276 } 277 278 // Otherwise, random variable references are not constants. 279 return Error(E->getLocStart(), diag::err_expr_not_constant); 280} 281 282 283bool IntExprEvaluator::VisitCallExpr(const CallExpr *E) { 284 Result.zextOrTrunc(getIntTypeSizeInBits(E->getType())); 285 // __builtin_type_compatible_p is a constant. 286 if (E->isBuiltinClassifyType(Result)) 287 return true; 288 289 return Error(E->getLocStart(), diag::err_expr_not_constant); 290} 291 292bool IntExprEvaluator::VisitBinaryOperator(const BinaryOperator *E) { 293 // The LHS of a constant expr is always evaluated and needed. 294 llvm::APSInt RHS(32); 295 if (!Visit(E->getLHS())) 296 return false; // error in subexpression. 297 298 bool OldEval = Info.isEvaluated; 299 300 // The short-circuiting &&/|| operators don't necessarily evaluate their 301 // RHS. Make sure to pass isEvaluated down correctly. 302 if ((E->getOpcode() == BinaryOperator::LAnd && Result == 0) || 303 (E->getOpcode() == BinaryOperator::LOr && Result != 0)) 304 Info.isEvaluated = false; 305 306 // FIXME: Handle pointer subtraction 307 308 // FIXME Maybe we want to succeed even where we can't evaluate the 309 // right side of LAnd/LOr? 310 // For example, see http://llvm.org/bugs/show_bug.cgi?id=2525 311 if (!EvaluateInteger(E->getRHS(), RHS, Info)) 312 return false; 313 Info.isEvaluated = OldEval; 314 315 switch (E->getOpcode()) { 316 default: return Error(E->getOperatorLoc(), diag::err_expr_not_constant); 317 case BinaryOperator::Mul: Result *= RHS; return true; 318 case BinaryOperator::Add: Result += RHS; return true; 319 case BinaryOperator::Sub: Result -= RHS; return true; 320 case BinaryOperator::And: Result &= RHS; return true; 321 case BinaryOperator::Xor: Result ^= RHS; return true; 322 case BinaryOperator::Or: Result |= RHS; return true; 323 case BinaryOperator::Div: 324 if (RHS == 0) 325 return Error(E->getOperatorLoc(), diag::err_expr_divide_by_zero); 326 Result /= RHS; 327 return true; 328 case BinaryOperator::Rem: 329 if (RHS == 0) 330 return Error(E->getOperatorLoc(), diag::err_expr_divide_by_zero); 331 Result %= RHS; 332 return true; 333 case BinaryOperator::Shl: 334 // FIXME: Warn about out of range shift amounts! 335 Result <<= (unsigned)RHS.getLimitedValue(Result.getBitWidth()-1); 336 break; 337 case BinaryOperator::Shr: 338 Result >>= (unsigned)RHS.getLimitedValue(Result.getBitWidth()-1); 339 break; 340 341 case BinaryOperator::LT: 342 Result = Result < RHS; 343 Result.zextOrTrunc(getIntTypeSizeInBits(E->getType())); 344 break; 345 case BinaryOperator::GT: 346 Result = Result > RHS; 347 Result.zextOrTrunc(getIntTypeSizeInBits(E->getType())); 348 break; 349 case BinaryOperator::LE: 350 Result = Result <= RHS; 351 Result.zextOrTrunc(getIntTypeSizeInBits(E->getType())); 352 break; 353 case BinaryOperator::GE: 354 Result = Result >= RHS; 355 Result.zextOrTrunc(getIntTypeSizeInBits(E->getType())); 356 break; 357 case BinaryOperator::EQ: 358 Result = Result == RHS; 359 Result.zextOrTrunc(getIntTypeSizeInBits(E->getType())); 360 break; 361 case BinaryOperator::NE: 362 Result = Result != RHS; 363 Result.zextOrTrunc(getIntTypeSizeInBits(E->getType())); 364 break; 365 case BinaryOperator::LAnd: 366 Result = Result != 0 && RHS != 0; 367 Result.zextOrTrunc(getIntTypeSizeInBits(E->getType())); 368 break; 369 case BinaryOperator::LOr: 370 Result = Result != 0 || RHS != 0; 371 Result.zextOrTrunc(getIntTypeSizeInBits(E->getType())); 372 break; 373 374 375 case BinaryOperator::Comma: 376 // Result of the comma is just the result of the RHS. 377 Result = RHS; 378 379 // C99 6.6p3: "shall not contain assignment, ..., or comma operators, 380 // *except* when they are contained within a subexpression that is not 381 // evaluated". Note that Assignment can never happen due to constraints 382 // on the LHS subexpr, so we don't need to check it here. 383 if (!Info.isEvaluated) 384 return true; 385 386 // If the value is evaluated, we can accept it as an extension. 387 return Extension(E->getOperatorLoc(), diag::ext_comma_in_constant_expr); 388 } 389 390 Result.setIsUnsigned(E->getType()->isUnsignedIntegerType()); 391 return true; 392} 393 394/// EvaluateSizeAlignOf - Evaluate sizeof(SrcTy) or alignof(SrcTy) with a result 395/// as a DstTy type. 396bool IntExprEvaluator::EvaluateSizeAlignOf(bool isSizeOf, QualType SrcTy, 397 QualType DstTy) { 398 // Return the result in the right width. 399 Result.zextOrTrunc(getIntTypeSizeInBits(DstTy)); 400 Result.setIsUnsigned(DstTy->isUnsignedIntegerType()); 401 402 // sizeof(void) and __alignof__(void) = 1 as a gcc extension. 403 if (SrcTy->isVoidType()) 404 Result = 1; 405 406 // sizeof(vla) is not a constantexpr: C99 6.5.3.4p2. 407 if (!SrcTy->isConstantSizeType()) { 408 // FIXME: Should we attempt to evaluate this? 409 return false; 410 } 411 412 // GCC extension: sizeof(function) = 1. 413 if (SrcTy->isFunctionType()) { 414 // FIXME: AlignOf shouldn't be unconditionally 4! 415 Result = isSizeOf ? 1 : 4; 416 return true; 417 } 418 419 // Get information about the size or align. 420 unsigned CharSize = Info.Ctx.Target.getCharWidth(); 421 if (isSizeOf) 422 Result = getIntTypeSizeInBits(SrcTy) / CharSize; 423 else 424 Result = Info.Ctx.getTypeAlign(SrcTy) / CharSize; 425 return true; 426} 427 428bool IntExprEvaluator::VisitUnaryOperator(const UnaryOperator *E) { 429 // Special case unary operators that do not need their subexpression 430 // evaluated. offsetof/sizeof/alignof are all special. 431 if (E->isOffsetOfOp()) { 432 Result.zextOrTrunc(getIntTypeSizeInBits(E->getType())); 433 Result = E->evaluateOffsetOf(Info.Ctx); 434 Result.setIsUnsigned(E->getType()->isUnsignedIntegerType()); 435 return true; 436 } 437 438 if (E->isSizeOfAlignOfOp()) 439 return EvaluateSizeAlignOf(E->getOpcode() == UnaryOperator::SizeOf, 440 E->getSubExpr()->getType(), E->getType()); 441 442 // Get the operand value into 'Result'. 443 if (!Visit(E->getSubExpr())) 444 return false; 445 446 switch (E->getOpcode()) { 447 default: 448 // Address, indirect, pre/post inc/dec, etc are not valid constant exprs. 449 // See C99 6.6p3. 450 return Error(E->getOperatorLoc(), diag::err_expr_not_constant); 451 case UnaryOperator::LNot: { 452 bool Val = Result == 0; 453 Result.zextOrTrunc(getIntTypeSizeInBits(E->getType())); 454 Result = Val; 455 break; 456 } 457 case UnaryOperator::Extension: 458 // FIXME: Should extension allow i-c-e extension expressions in its scope? 459 // If so, we could clear the diagnostic ID. 460 case UnaryOperator::Plus: 461 // The result is always just the subexpr. 462 break; 463 case UnaryOperator::Minus: 464 Result = -Result; 465 break; 466 case UnaryOperator::Not: 467 Result = ~Result; 468 break; 469 } 470 471 Result.setIsUnsigned(E->getType()->isUnsignedIntegerType()); 472 return true; 473} 474 475/// HandleCast - This is used to evaluate implicit or explicit casts where the 476/// result type is integer. 477bool IntExprEvaluator::HandleCast(SourceLocation CastLoc, 478 Expr *SubExpr, QualType DestType) { 479 unsigned DestWidth = getIntTypeSizeInBits(DestType); 480 481 // Handle simple integer->integer casts. 482 if (SubExpr->getType()->isIntegerType()) { 483 if (!Visit(SubExpr)) 484 return false; 485 486 // Figure out if this is a truncate, extend or noop cast. 487 // If the input is signed, do a sign extend, noop, or truncate. 488 if (DestType->isBooleanType()) { 489 // Conversion to bool compares against zero. 490 Result = Result != 0; 491 Result.zextOrTrunc(DestWidth); 492 } else 493 Result.extOrTrunc(DestWidth); 494 Result.setIsUnsigned(DestType->isUnsignedIntegerType()); 495 return true; 496 } 497 498 // FIXME: Clean this up! 499 if (SubExpr->getType()->isPointerType()) { 500 APValue LV; 501 if (!EvaluatePointer(SubExpr, LV, Info)) 502 return false; 503 if (LV.getLValueBase()) 504 return false; 505 506 Result.extOrTrunc(DestWidth); 507 Result = LV.getLValueOffset(); 508 Result.setIsUnsigned(DestType->isUnsignedIntegerType()); 509 return true; 510 } 511 512 if (!SubExpr->getType()->isRealFloatingType()) 513 return Error(CastLoc, diag::err_expr_not_constant); 514 515 // FIXME: Generalize floating point constant folding! For now we just permit 516 // which is allowed by integer constant expressions. 517 518 // Allow floating constants that are the immediate operands of casts or that 519 // are parenthesized. 520 const Expr *Operand = SubExpr; 521 while (const ParenExpr *PE = dyn_cast<ParenExpr>(Operand)) 522 Operand = PE->getSubExpr(); 523 524 // If this isn't a floating literal, we can't handle it. 525 const FloatingLiteral *FL = dyn_cast<FloatingLiteral>(Operand); 526 if (!FL) 527 return Error(CastLoc, diag::err_expr_not_constant); 528 529 // If the destination is boolean, compare against zero. 530 if (DestType->isBooleanType()) { 531 Result = !FL->getValue().isZero(); 532 Result.zextOrTrunc(DestWidth); 533 Result.setIsUnsigned(DestType->isUnsignedIntegerType()); 534 return true; 535 } 536 537 // Determine whether we are converting to unsigned or signed. 538 bool DestSigned = DestType->isSignedIntegerType(); 539 540 // FIXME: Warning for overflow. 541 uint64_t Space[4]; 542 (void)FL->getValue().convertToInteger(Space, DestWidth, DestSigned, 543 llvm::APFloat::rmTowardZero); 544 Result = llvm::APInt(DestWidth, 4, Space); 545 Result.setIsUnsigned(!DestSigned); 546 return true; 547} 548 549//===----------------------------------------------------------------------===// 550// Top level TryEvaluate. 551//===----------------------------------------------------------------------===// 552 553bool Expr::tryEvaluate(APValue &Result, ASTContext &Ctx) const { 554 llvm::APSInt sInt(32); 555#if USE_NEW_EVALUATOR 556 EvalInfo Info(Ctx); 557 if (getType()->isIntegerType()) { 558 if (EvaluateInteger(this, sInt, Info)) { 559 Result = APValue(sInt); 560 return true; 561 } 562 } else 563 return false; 564 565#else 566 if (CalcFakeICEVal(this, sInt, Ctx)) { 567 Result = APValue(sInt); 568 return true; 569 } 570#endif 571 572 return false; 573} 574