ExprConstant.cpp 370 KB
Newer Older
1
//===--- ExprConstant.cpp - Expression Constant Evaluator -----------------===//
2
3
4
5
6
7
8
9
10
11
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements the Expr constant evaluator.
//
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// Constant expression evaluation produces four main results:
//
//  * A success/failure flag indicating whether constant folding was successful.
//    This is the 'bool' return value used by most of the code in this file. A
//    'false' return value indicates that constant folding has failed, and any
//    appropriate diagnostic has already been produced.
//
//  * An evaluated result, valid only if constant folding has not failed.
//
//  * A flag indicating if evaluation encountered (unevaluated) side-effects.
//    These arise in cases such as (sideEffect(), 0) and (sideEffect() || 1),
//    where it is possible to determine the evaluated result regardless.
//
//  * A set of notes indicating why the evaluation was not a constant expression
26
27
//    (under the C++11 / C++1y rules only, at the moment), or, if folding failed
//    too, why the expression could not be folded.
28
29
30
31
32
33
//
// If we are checking for a potential constant expression, failure to constant
// fold a potential constant sub-expression will be indicated by a 'false'
// return value (the expression could not be folded) and no diagnostic (the
// expression is not necessarily non-constant).
//
34
35
36
37
//===----------------------------------------------------------------------===//

#include "clang/AST/APValue.h"
#include "clang/AST/ASTContext.h"
38
#include "clang/AST/ASTDiagnostic.h"
39
#include "clang/AST/ASTLambda.h"
40
#include "clang/AST/CharUnits.h"
41
#include "clang/AST/Expr.h"
Anders Carlsson's avatar
Anders Carlsson committed
42
#include "clang/AST/RecordLayout.h"
Seo Sanghyeon's avatar
Seo Sanghyeon committed
43
#include "clang/AST/StmtVisitor.h"
44
#include "clang/AST/TypeLoc.h"
45
#include "clang/Basic/Builtins.h"
46
#include "clang/Basic/TargetInfo.h"
47
#include "llvm/Support/raw_ostream.h"
48
#include <cstring>
49
#include <functional>
50

51
using namespace clang;
52
using llvm::APSInt;
53
using llvm::APFloat;
54

55
56
static bool IsGlobalLValue(APValue::LValueBase B);

57
namespace {
58
  struct LValue;
59
  struct CallStackFrame;
60
  struct EvalInfo;
61

62
  static QualType getType(APValue::LValueBase B) {
63
64
65
    if (!B) return QualType();
    if (const ValueDecl *D = B.dyn_cast<const ValueDecl*>())
      return D->getType();
66
67
68
69
70
71
72
73
74
75
76
77
78

    const Expr *Base = B.get<const Expr*>();

    // For a materialized temporary, the type of the temporary we materialized
    // may not be the type of the expression.
    if (const MaterializeTemporaryExpr *MTE =
            dyn_cast<MaterializeTemporaryExpr>(Base)) {
      SmallVector<const Expr *, 2> CommaLHSs;
      SmallVector<SubobjectAdjustment, 2> Adjustments;
      const Expr *Temp = MTE->GetTemporaryExpr();
      const Expr *Inner = Temp->skipRValueSubobjectAdjustments(CommaLHSs,
                                                               Adjustments);
      // Keep any cv-qualifiers from the reference if we generated a temporary
79
80
      // for it directly. Otherwise use the type after adjustment.
      if (!Adjustments.empty())
81
82
83
84
        return Inner->getType();
    }

    return Base->getType();
85
86
  }

87
  /// Get an LValue path entry, which is known to not be an array index, as a
Richard Smith's avatar
Richard Smith committed
88
  /// field or base class.
89
  static
Richard Smith's avatar
Richard Smith committed
90
  APValue::BaseOrMemberType getAsBaseOrMember(APValue::LValuePathEntry E) {
91
92
    APValue::BaseOrMemberType Value;
    Value.setFromOpaqueValue(E.BaseOrMember);
Richard Smith's avatar
Richard Smith committed
93
94
95
96
97
    return Value;
  }

  /// Get an LValue path entry, which is known to not be an array index, as a
  /// field declaration.
98
  static const FieldDecl *getAsField(APValue::LValuePathEntry E) {
Richard Smith's avatar
Richard Smith committed
99
    return dyn_cast<FieldDecl>(getAsBaseOrMember(E).getPointer());
100
101
102
  }
  /// Get an LValue path entry, which is known to not be an array index, as a
  /// base class declaration.
103
  static const CXXRecordDecl *getAsBaseClass(APValue::LValuePathEntry E) {
Richard Smith's avatar
Richard Smith committed
104
    return dyn_cast<CXXRecordDecl>(getAsBaseOrMember(E).getPointer());
105
106
107
  }
  /// Determine whether this LValue path entry for a base class names a virtual
  /// base class.
108
  static bool isVirtualBaseClass(APValue::LValuePathEntry E) {
Richard Smith's avatar
Richard Smith committed
109
    return getAsBaseOrMember(E).getInt();
110
111
  }

112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
  /// Given a CallExpr, try to get the alloc_size attribute. May return null.
  static const AllocSizeAttr *getAllocSizeAttr(const CallExpr *CE) {
    const FunctionDecl *Callee = CE->getDirectCallee();
    return Callee ? Callee->getAttr<AllocSizeAttr>() : nullptr;
  }

  /// Attempts to unwrap a CallExpr (with an alloc_size attribute) from an Expr.
  /// This will look through a single cast.
  ///
  /// Returns null if we couldn't unwrap a function with alloc_size.
  static const CallExpr *tryUnwrapAllocSizeCall(const Expr *E) {
    if (!E->getType()->isPointerType())
      return nullptr;

    E = E->IgnoreParens();
    // If we're doing a variable assignment from e.g. malloc(N), there will
    // probably be a cast of some kind. Ignore it.
    if (const auto *Cast = dyn_cast<CastExpr>(E))
      E = Cast->getSubExpr()->IgnoreParens();

    if (const auto *CE = dyn_cast<CallExpr>(E))
      return getAllocSizeAttr(CE) ? CE : nullptr;
    return nullptr;
  }

  /// Determines whether or not the given Base contains a call to a function
  /// with the alloc_size attribute.
  static bool isBaseAnAllocSizeCall(APValue::LValueBase Base) {
    const auto *E = Base.dyn_cast<const Expr *>();
    return E && E->getType()->isPointerType() && tryUnwrapAllocSizeCall(E);
  }

  /// Determines if an LValue with the given LValueBase will have an unsized
  /// array in its designator.
146
147
  /// Find the path length and type of the most-derived subobject in the given
  /// path, and find the size of the containing array, if any.
148
149
150
151
152
153
154
155
  static unsigned
  findMostDerivedSubobject(ASTContext &Ctx, APValue::LValueBase Base,
                           ArrayRef<APValue::LValuePathEntry> Path,
                           uint64_t &ArraySize, QualType &Type, bool &IsArray) {
    // This only accepts LValueBases from APValues, and APValues don't support
    // arrays that lack size info.
    assert(!isBaseAnAllocSizeCall(Base) &&
           "Unsized arrays shouldn't appear here");
156
    unsigned MostDerivedLength = 0;
157
158
    Type = getType(Base);

159
    for (unsigned I = 0, N = Path.size(); I != N; ++I) {
160
161
      if (Type->isArrayType()) {
        const ConstantArrayType *CAT =
162
            cast<ConstantArrayType>(Ctx.getAsArrayType(Type));
163
164
165
        Type = CAT->getElementType();
        ArraySize = CAT->getSize().getZExtValue();
        MostDerivedLength = I + 1;
166
        IsArray = true;
167
168
169
170
171
      } else if (Type->isAnyComplexType()) {
        const ComplexType *CT = Type->castAs<ComplexType>();
        Type = CT->getElementType();
        ArraySize = 2;
        MostDerivedLength = I + 1;
172
        IsArray = true;
173
174
175
176
      } else if (const FieldDecl *FD = getAsField(Path[I])) {
        Type = FD->getType();
        ArraySize = 0;
        MostDerivedLength = I + 1;
177
        IsArray = false;
178
      } else {
179
        // Path[I] describes a base class.
180
        ArraySize = 0;
181
        IsArray = false;
182
      }
183
    }
184
    return MostDerivedLength;
185
186
  }

187
188
  // The order of this enum is important for diagnostics.
  enum CheckSubobjectKind {
189
    CSK_Base, CSK_Derived, CSK_Field, CSK_ArrayToPointer, CSK_ArrayIndex,
190
    CSK_This, CSK_Real, CSK_Imag
191
192
  };

193
194
195
196
197
  /// A path from a glvalue to a subobject of that glvalue.
  struct SubobjectDesignator {
    /// True if the subobject was named in a manner not supported by C++11. Such
    /// lvalues can still be folded, but they are not core constant expressions
    /// and we cannot perform lvalue-to-rvalue conversions on them.
198
    unsigned Invalid : 1;
199

200
    /// Is this a pointer one past the end of an object?
201
    unsigned IsOnePastTheEnd : 1;
202

203
204
205
    /// Indicator of whether the first entry is an unsized array.
    unsigned FirstEntryIsAnUnsizedArray : 1;

206
    /// Indicator of whether the most-derived object is an array element.
207
    unsigned MostDerivedIsArrayElement : 1;
208

209
210
    /// The length of the path to the most-derived object of which this is a
    /// subobject.
211
    unsigned MostDerivedPathLength : 28;
212

213
214
215
216
    /// The size of the array of which the most-derived object is an element.
    /// This will always be 0 if the most-derived object is not an array
    /// element. 0 is not an indicator of whether or not the most-derived object
    /// is an array, however, because 0-length arrays are allowed.
217
218
219
    ///
    /// If the current array is an unsized array, the value of this is
    /// undefined.
220
    uint64_t MostDerivedArraySize;
221

222
223
    /// The type of the most derived object referred to by this address.
    QualType MostDerivedType;
224

225
226
    typedef APValue::LValuePathEntry PathEntry;

227
228
229
    /// The entries on the path from the glvalue to the designated subobject.
    SmallVector<PathEntry, 8> Entries;

230
    SubobjectDesignator() : Invalid(true) {}
231

232
    explicit SubobjectDesignator(QualType T)
233
        : Invalid(false), IsOnePastTheEnd(false),
234
235
236
          FirstEntryIsAnUnsizedArray(false), MostDerivedIsArrayElement(false),
          MostDerivedPathLength(0), MostDerivedArraySize(0),
          MostDerivedType(T) {}
237
238

    SubobjectDesignator(ASTContext &Ctx, const APValue &V)
239
        : Invalid(!V.isLValue() || !V.hasLValuePath()), IsOnePastTheEnd(false),
240
241
242
          FirstEntryIsAnUnsizedArray(false), MostDerivedIsArrayElement(false),
          MostDerivedPathLength(0), MostDerivedArraySize(0) {
      assert(V.isLValue() && "Non-LValue used to make an LValue designator?");
243
      if (!Invalid) {
244
        IsOnePastTheEnd = V.isLValueOnePastTheEnd();
245
246
        ArrayRef<PathEntry> VEntries = V.getLValuePath();
        Entries.insert(Entries.end(), VEntries.begin(), VEntries.end());
247
248
        if (V.getLValueBase()) {
          bool IsArray = false;
249
250
251
          MostDerivedPathLength = findMostDerivedSubobject(
              Ctx, V.getLValueBase(), V.getLValuePath(), MostDerivedArraySize,
              MostDerivedType, IsArray);
252
253
          MostDerivedIsArrayElement = IsArray;
        }
254
255
256
      }
    }

257
258
259
260
    void setInvalid() {
      Invalid = true;
      Entries.clear();
    }
261

262
263
264
265
266
267
268
269
270
271
272
273
274
275
    /// Determine whether the most derived subobject is an array without a
    /// known bound.
    bool isMostDerivedAnUnsizedArray() const {
      assert(!Invalid && "Calling this makes no sense on invalid designators");
      return Entries.size() == 1 && FirstEntryIsAnUnsizedArray;
    }

    /// Determine what the most derived array's size is. Results in an assertion
    /// failure if the most derived array lacks a size.
    uint64_t getMostDerivedArraySize() const {
      assert(!isMostDerivedAnUnsizedArray() && "Unsized array has no size");
      return MostDerivedArraySize;
    }

276
277
    /// Determine whether this is a one-past-the-end pointer.
    bool isOnePastTheEnd() const {
278
      assert(!Invalid);
279
280
      if (IsOnePastTheEnd)
        return true;
281
      if (!isMostDerivedAnUnsizedArray() && MostDerivedIsArrayElement &&
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
          Entries[MostDerivedPathLength - 1].ArrayIndex == MostDerivedArraySize)
        return true;
      return false;
    }

    /// Check that this refers to a valid subobject.
    bool isValidSubobject() const {
      if (Invalid)
        return false;
      return !isOnePastTheEnd();
    }
    /// Check that this refers to a valid subobject, and if not, produce a
    /// relevant diagnostic and set the designator as invalid.
    bool checkSubobject(EvalInfo &Info, const Expr *E, CheckSubobjectKind CSK);

    /// Update this designator to refer to the first element within this array.
    void addArrayUnchecked(const ConstantArrayType *CAT) {
299
      PathEntry Entry;
300
      Entry.ArrayIndex = 0;
301
      Entries.push_back(Entry);
302
303
304

      // This is a most-derived object.
      MostDerivedType = CAT->getElementType();
305
      MostDerivedIsArrayElement = true;
306
307
      MostDerivedArraySize = CAT->getSize().getZExtValue();
      MostDerivedPathLength = Entries.size();
308
    }
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
    /// Update this designator to refer to the first element within the array of
    /// elements of type T. This is an array of unknown size.
    void addUnsizedArrayUnchecked(QualType ElemTy) {
      PathEntry Entry;
      Entry.ArrayIndex = 0;
      Entries.push_back(Entry);

      MostDerivedType = ElemTy;
      MostDerivedIsArrayElement = true;
      // The value in MostDerivedArraySize is undefined in this case. So, set it
      // to an arbitrary value that's likely to loudly break things if it's
      // used.
      MostDerivedArraySize = std::numeric_limits<uint64_t>::max() / 2;
      MostDerivedPathLength = Entries.size();
    }
324
325
    /// Update this designator to refer to the given base or member of this
    /// object.
326
    void addDeclUnchecked(const Decl *D, bool Virtual = false) {
327
      PathEntry Entry;
328
329
      APValue::BaseOrMemberType Value(D, Virtual);
      Entry.BaseOrMember = Value.getOpaqueValue();
330
      Entries.push_back(Entry);
331
332
333
334

      // If this isn't a base class, it's a new most-derived object.
      if (const FieldDecl *FD = dyn_cast<FieldDecl>(D)) {
        MostDerivedType = FD->getType();
335
        MostDerivedIsArrayElement = false;
336
337
338
        MostDerivedArraySize = 0;
        MostDerivedPathLength = Entries.size();
      }
339
    }
340
341
342
343
344
345
346
347
348
    /// Update this designator to refer to the given complex component.
    void addComplexUnchecked(QualType EltTy, bool Imag) {
      PathEntry Entry;
      Entry.ArrayIndex = Imag;
      Entries.push_back(Entry);

      // This is technically a most-derived object, though in practice this
      // is unlikely to matter.
      MostDerivedType = EltTy;
349
      MostDerivedIsArrayElement = true;
350
351
352
      MostDerivedArraySize = 2;
      MostDerivedPathLength = Entries.size();
    }
353
    void diagnosePointerArithmetic(EvalInfo &Info, const Expr *E, uint64_t N);
354
    /// Add N to the address of this subobject.
355
    void adjustIndex(EvalInfo &Info, const Expr *E, uint64_t N) {
356
      if (Invalid) return;
357
358
359
360
361
362
      if (isMostDerivedAnUnsizedArray()) {
        // Can't verify -- trust that the user is doing the right thing (or if
        // not, trust that the caller will catch the bad behavior).
        Entries.back().ArrayIndex += N;
        return;
      }
363
364
      if (MostDerivedPathLength == Entries.size() &&
          MostDerivedIsArrayElement) {
365
        Entries.back().ArrayIndex += N;
366
        if (Entries.back().ArrayIndex > getMostDerivedArraySize()) {
367
368
369
          diagnosePointerArithmetic(Info, E, Entries.back().ArrayIndex);
          setInvalid();
        }
370
371
        return;
      }
372
373
374
375
376
377
378
379
380
      // [expr.add]p4: For the purposes of these operators, a pointer to a
      // nonarray object behaves the same as a pointer to the first element of
      // an array of length one with the type of the object as its element type.
      if (IsOnePastTheEnd && N == (uint64_t)-1)
        IsOnePastTheEnd = false;
      else if (!IsOnePastTheEnd && N == 1)
        IsOnePastTheEnd = true;
      else if (N != 0) {
        diagnosePointerArithmetic(Info, E, uint64_t(IsOnePastTheEnd) + N);
381
        setInvalid();
382
      }
383
384
385
    }
  };

386
387
388
389
390
391
392
  /// A stack frame in the constexpr call stack.
  struct CallStackFrame {
    EvalInfo &Info;

    /// Parent - The caller of this stack frame.
    CallStackFrame *Caller;

393
394
395
    /// Callee - The function which was called.
    const FunctionDecl *Callee;

396
397
398
    /// This - The binding for the this pointer in this call, if any.
    const LValue *This;

399
    /// Arguments - Parameter bindings for this function call, indexed by
400
    /// parameters' function scope indices.
401
    APValue *Arguments;
402

403
404
    // Note that we intentionally use std::map here so that references to
    // values are stable.
405
    typedef std::map<const void*, APValue> MapTy;
406
407
408
409
    typedef MapTy::const_iterator temp_iterator;
    /// Temporaries - Temporary lvalues materialized within this stack frame.
    MapTy Temporaries;

410
411
412
413
414
415
    /// CallLoc - The location of the call expression for this call.
    SourceLocation CallLoc;

    /// Index - The call index of this call.
    unsigned Index;

416
417
    CallStackFrame(EvalInfo &Info, SourceLocation CallLoc,
                   const FunctionDecl *Callee, const LValue *This,
418
                   APValue *Arguments);
419
    ~CallStackFrame();
420
421
422

    APValue *getTemporary(const void *Key) {
      MapTy::iterator I = Temporaries.find(Key);
423
      return I == Temporaries.end() ? nullptr : &I->second;
424
425
    }
    APValue &createTemporary(const void *Key, bool IsLifetimeExtended);
426
427
  };

428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
  /// Temporarily override 'this'.
  class ThisOverrideRAII {
  public:
    ThisOverrideRAII(CallStackFrame &Frame, const LValue *NewThis, bool Enable)
        : Frame(Frame), OldThis(Frame.This) {
      if (Enable)
        Frame.This = NewThis;
    }
    ~ThisOverrideRAII() {
      Frame.This = OldThis;
    }
  private:
    CallStackFrame &Frame;
    const LValue *OldThis;
  };

444
445
446
447
448
449
  /// A partial diagnostic which we might know in advance that we are not going
  /// to emit.
  class OptionalDiagnostic {
    PartialDiagnostic *Diag;

  public:
450
451
    explicit OptionalDiagnostic(PartialDiagnostic *Diag = nullptr)
      : Diag(Diag) {}
452
453
454
455
456
457
458

    template<typename T>
    OptionalDiagnostic &operator<<(const T &v) {
      if (Diag)
        *Diag << v;
      return *this;
    }
459
460
461

    OptionalDiagnostic &operator<<(const APSInt &I) {
      if (Diag) {
462
        SmallVector<char, 32> Buffer;
463
464
465
466
467
468
469
470
        I.toString(Buffer);
        *Diag << StringRef(Buffer.data(), Buffer.size());
      }
      return *this;
    }

    OptionalDiagnostic &operator<<(const APFloat &F) {
      if (Diag) {
471
472
473
474
475
476
477
478
479
        // FIXME: Force the precision of the source value down so we don't
        // print digits which are usually useless (we don't really care here if
        // we truncate a digit by accident in edge cases).  Ideally,
        // APFloat::toString would automatically print the shortest 
        // representation which rounds to the correct value, but it's a bit
        // tricky to implement.
        unsigned precision =
            llvm::APFloat::semanticsPrecision(F.getSemantics());
        precision = (precision * 59 + 195) / 196;
480
        SmallVector<char, 32> Buffer;
481
        F.toString(Buffer, precision);
482
483
484
485
        *Diag << StringRef(Buffer.data(), Buffer.size());
      }
      return *this;
    }
486
487
  };

488
489
490
491
492
493
494
495
496
497
498
499
500
501
  /// A cleanup, and a flag indicating whether it is lifetime-extended.
  class Cleanup {
    llvm::PointerIntPair<APValue*, 1, bool> Value;

  public:
    Cleanup(APValue *Val, bool IsLifetimeExtended)
        : Value(Val, IsLifetimeExtended) {}

    bool isLifetimeExtended() const { return Value.getInt(); }
    void endLifetime() {
      *Value.getPointer() = APValue();
    }
  };

502
503
504
505
506
507
508
509
510
511
512
513
514
515
  /// EvalInfo - This is a private struct used by the evaluator to capture
  /// information about a subexpression as it is folded.  It retains information
  /// about the AST context, but also maintains information about the folded
  /// expression.
  ///
  /// If an expression could be evaluated, it is still possible it is not a C
  /// "integer constant expression" or constant expression.  If not, this struct
  /// captures information about how and why not.
  ///
  /// One bit of information passed *into* the request for constant folding
  /// indicates whether the subexpression is "evaluated" or not according to C
  /// rules.  For example, the RHS of (0 && foo()) is not evaluated.  We can
  /// evaluate the expression regardless of what the RHS is, but C only allows
  /// certain things in certain situations.
516
  struct LLVM_ALIGNAS(/*alignof(uint64_t)*/ 8) EvalInfo {
517
    ASTContext &Ctx;
518

519
520
    /// EvalStatus - Contains information about the evaluation.
    Expr::EvalStatus &EvalStatus;
521

522
    /// CurrentCall - The top of the constexpr call stack.
523
    CallStackFrame *CurrentCall;
524
525
526
527

    /// CallStackDepth - The number of calls in the call stack right now.
    unsigned CallStackDepth;

528
529
530
    /// NextCallIndex - The next call index to assign.
    unsigned NextCallIndex;

531
532
533
534
535
    /// StepsLeft - The remaining number of evaluation steps we're permitted
    /// to perform. This is essentially a limit for the number of statements
    /// we will evaluate.
    unsigned StepsLeft;

536
    /// BottomFrame - The frame in which evaluation started. This must be
537
    /// initialized after CurrentCall and CallStackDepth.
538
539
    CallStackFrame BottomFrame;

540
541
542
543
    /// A stack of values whose lifetimes end at the end of some surrounding
    /// evaluation frame.
    llvm::SmallVector<Cleanup, 16> CleanupStack;

544
545
    /// EvaluatingDecl - This is the declaration whose initializer is being
    /// evaluated, if any.
546
    APValue::LValueBase EvaluatingDecl;
547
548
549
550
551

    /// EvaluatingDeclValue - This is the value being constructed for the
    /// declaration whose initializer is being evaluated, if any.
    APValue *EvaluatingDeclValue;

552
553
554
555
    /// The current array initialization index, if we're performing array
    /// initialization.
    uint64_t ArrayInitIndex = -1;

556
557
558
559
    /// HasActiveDiagnostic - Was the previous diagnostic stored? If so, further
    /// notes attached to it will also be stored, otherwise they will not be.
    bool HasActiveDiagnostic;

560
561
562
563
    /// \brief Have we emitted a diagnostic explaining why we couldn't constant
    /// fold (not just why it's not strictly a constant expression)?
    bool HasFoldFailureDiagnostic;

564
565
566
    /// \brief Whether or not we're currently speculatively evaluating.
    bool IsSpeculativelyEvaluating;

567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
    enum EvaluationMode {
      /// Evaluate as a constant expression. Stop if we find that the expression
      /// is not a constant expression.
      EM_ConstantExpression,

      /// Evaluate as a potential constant expression. Keep going if we hit a
      /// construct that we can't evaluate yet (because we don't yet know the
      /// value of something) but stop if we hit something that could never be
      /// a constant expression.
      EM_PotentialConstantExpression,

      /// Fold the expression to a constant. Stop if we hit a side-effect that
      /// we can't model.
      EM_ConstantFold,

      /// Evaluate the expression looking for integer overflow and similar
      /// issues. Don't worry about side-effects, and try to visit all
      /// subexpressions.
      EM_EvaluateForOverflow,

      /// Evaluate in any way we know how. Don't worry about side-effects that
      /// can't be modeled.
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
      EM_IgnoreSideEffects,

      /// Evaluate as a constant expression. Stop if we find that the expression
      /// is not a constant expression. Some expressions can be retried in the
      /// optimizer if we don't constant fold them here, but in an unevaluated
      /// context we try to fold them immediately since the optimizer never
      /// gets a chance to look at it.
      EM_ConstantExpressionUnevaluated,

      /// Evaluate as a potential constant expression. Keep going if we hit a
      /// construct that we can't evaluate yet (because we don't yet know the
      /// value of something) but stop if we hit something that could never be
      /// a constant expression. Some expressions can be retried in the
      /// optimizer if we don't constant fold them here, but in an unevaluated
      /// context we try to fold them immediately since the optimizer never
      /// gets a chance to look at it.
605
606
      EM_PotentialConstantExpressionUnevaluated,

607
608
609
610
611
612
613
614
615
      /// Evaluate as a constant expression. Continue evaluating if either:
      /// - We find a MemberExpr with a base that can't be evaluated.
      /// - We find a variable initialized with a call to a function that has
      ///   the alloc_size attribute on it.
      /// In either case, the LValue returned shall have an invalid base; in the
      /// former, the base will be the invalid MemberExpr, in the latter, the
      /// base will be either the alloc_size CallExpr or a CastExpr wrapping
      /// said CallExpr.
      EM_OffsetFold,
616
617
618
619
620
    } EvalMode;

    /// Are we checking whether the expression is a potential constant
    /// expression?
    bool checkingPotentialConstantExpression() const {
621
622
      return EvalMode == EM_PotentialConstantExpression ||
             EvalMode == EM_PotentialConstantExpressionUnevaluated;
623
624
625
626
627
628
629
630
    }

    /// Are we checking an expression for overflow?
    // FIXME: We should check for any kind of undefined or suspicious behavior
    // in such constructs, not just overflow.
    bool checkingForOverflow() { return EvalMode == EM_EvaluateForOverflow; }

    EvalInfo(const ASTContext &C, Expr::EvalStatus &S, EvaluationMode Mode)
631
      : Ctx(const_cast<ASTContext &>(C)), EvalStatus(S), CurrentCall(nullptr),
632
        CallStackDepth(0), NextCallIndex(1),
633
        StepsLeft(getLangOpts().ConstexprStepLimit),
634
635
636
        BottomFrame(*this, SourceLocation(), nullptr, nullptr, nullptr),
        EvaluatingDecl((const ValueDecl *)nullptr),
        EvaluatingDeclValue(nullptr), HasActiveDiagnostic(false),
637
638
        HasFoldFailureDiagnostic(false), IsSpeculativelyEvaluating(false),
        EvalMode(Mode) {}
639

640
641
    void setEvaluatingDecl(APValue::LValueBase Base, APValue &Value) {
      EvaluatingDecl = Base;
642
643
644
      EvaluatingDeclValue = &Value;
    }

645
    const LangOptions &getLangOpts() const { return Ctx.getLangOpts(); }
646

647
    bool CheckCallLimit(SourceLocation Loc) {
648
649
      // Don't perform any constexpr calls (other than the call we're checking)
      // when checking a potential constant expression.
650
      if (checkingPotentialConstantExpression() && CallStackDepth > 1)
651
        return false;
652
653
      if (NextCallIndex == 0) {
        // NextCallIndex has wrapped around.
654
        FFDiag(Loc, diag::note_constexpr_call_limit_exceeded);
655
656
        return false;
      }
657
658
      if (CallStackDepth <= getLangOpts().ConstexprCallDepth)
        return true;
659
      FFDiag(Loc, diag::note_constexpr_depth_limit_exceeded)
660
661
        << getLangOpts().ConstexprCallDepth;
      return false;
662
    }
663

664
665
666
667
668
669
670
    CallStackFrame *getCallFrame(unsigned CallIndex) {
      assert(CallIndex && "no call index in getCallFrame");
      // We will eventually hit BottomFrame, which has Index 1, so Frame can't
      // be null in this loop.
      CallStackFrame *Frame = CurrentCall;
      while (Frame->Index > CallIndex)
        Frame = Frame->Caller;
671
      return (Frame->Index == CallIndex) ? Frame : nullptr;
672
673
    }

674
675
    bool nextStep(const Stmt *S) {
      if (!StepsLeft) {
676
        FFDiag(S->getLocStart(), diag::note_constexpr_step_limit_exceeded);
677
678
679
680
681
682
        return false;
      }
      --StepsLeft;
      return true;
    }

683
684
685
686
687
688
689
690
  private:
    /// Add a diagnostic to the diagnostics list.
    PartialDiagnostic &addDiag(SourceLocation Loc, diag::kind DiagId) {
      PartialDiagnostic PD(DiagId, Ctx.getDiagAllocator());
      EvalStatus.Diag->push_back(std::make_pair(Loc, PD));
      return EvalStatus.Diag->back().second;
    }

691
692
693
    /// Add notes containing a call stack to the current point of evaluation.
    void addCallStack(unsigned Limit);

694
695
696
697
  private:
    OptionalDiagnostic Diag(SourceLocation Loc, diag::kind DiagId,
                            unsigned ExtraNotes, bool IsCCEDiag) {
    
698
      if (EvalStatus.Diag) {
699
700
701
702
703
704
705
706
        // If we have a prior diagnostic, it will be noting that the expression
        // isn't a constant expression. This diagnostic is more important,
        // unless we require this evaluation to produce a constant expression.
        //
        // FIXME: We might want to show both diagnostics to the user in
        // EM_ConstantFold mode.
        if (!EvalStatus.Diag->empty()) {
          switch (EvalMode) {
707
708
709
          case EM_ConstantFold:
          case EM_IgnoreSideEffects:
          case EM_EvaluateForOverflow:
710
            if (!HasFoldFailureDiagnostic)
711
              break;
712
            // We've already failed to fold something. Keep that diagnostic.
713
714
          case EM_ConstantExpression:
          case EM_PotentialConstantExpression:
715
716
          case EM_ConstantExpressionUnevaluated:
          case EM_PotentialConstantExpressionUnevaluated:
717
          case EM_OffsetFold:
718
719
720
721
722
            HasActiveDiagnostic = false;
            return OptionalDiagnostic();
          }
        }

723
724
725
726
        unsigned CallStackNotes = CallStackDepth - 1;
        unsigned Limit = Ctx.getDiagnostics().getConstexprBacktraceLimit();
        if (Limit)
          CallStackNotes = std::min(CallStackNotes, Limit + 1);
727
        if (checkingPotentialConstantExpression())
728
          CallStackNotes = 0;
729

730
        HasActiveDiagnostic = true;
731
        HasFoldFailureDiagnostic = !IsCCEDiag;
732
        EvalStatus.Diag->clear();
733
734
        EvalStatus.Diag->reserve(1 + ExtraNotes + CallStackNotes);
        addDiag(Loc, DiagId);
735
        if (!checkingPotentialConstantExpression())
736
          addCallStack(Limit);
737
        return OptionalDiagnostic(&(*EvalStatus.Diag)[0].second);
738
      }
739
      HasActiveDiagnostic = false;
740
741
      return OptionalDiagnostic();
    }
742
743
744
745
746
747
748
749
750
751
  public:
    // Diagnose that the evaluation could not be folded (FF => FoldFailure)
    OptionalDiagnostic
    FFDiag(SourceLocation Loc,
          diag::kind DiagId = diag::note_invalid_subexpr_in_const_expr,
          unsigned ExtraNotes = 0) {
      return Diag(Loc, DiagId, ExtraNotes, false);
    }
    
    OptionalDiagnostic FFDiag(const Expr *E, diag::kind DiagId
752
                              = diag::note_invalid_subexpr_in_const_expr,
753
                            unsigned ExtraNotes = 0) {
754
      if (EvalStatus.Diag)
755
        return Diag(E->getExprLoc(), DiagId, ExtraNotes, /*IsCCEDiag*/false);
756
757
758
759
      HasActiveDiagnostic = false;
      return OptionalDiagnostic();
    }

760
761
    /// Diagnose that the evaluation does not produce a C++11 core constant
    /// expression.
762
763
764
    ///
    /// FIXME: Stop evaluating if we're in EM_ConstantExpression or
    /// EM_PotentialConstantExpression mode and we produce one of these.
765
    OptionalDiagnostic CCEDiag(SourceLocation Loc, diag::kind DiagId
766
                                 = diag::note_invalid_subexpr_in_const_expr,
767
                               unsigned ExtraNotes = 0) {
768
769
      // Don't override a previous diagnostic. Don't bother collecting
      // diagnostics if we're evaluating for overflow.
770
      if (!EvalStatus.Diag || !EvalStatus.Diag->empty()) {
771
        HasActiveDiagnostic = false;
772
        return OptionalDiagnostic();
773
      }
774
      return Diag(Loc, DiagId, ExtraNotes, true);
775
    }
776
777
778
779
780
    OptionalDiagnostic CCEDiag(const Expr *E, diag::kind DiagId
                                 = diag::note_invalid_subexpr_in_const_expr,
                               unsigned ExtraNotes = 0) {
      return CCEDiag(E->getExprLoc(), DiagId, ExtraNotes);
    }
781
782
783
784
785
    /// Add a note to a prior diagnostic.
    OptionalDiagnostic Note(SourceLocation Loc, diag::kind DiagId) {
      if (!HasActiveDiagnostic)
        return OptionalDiagnostic();
      return OptionalDiagnostic(&addDiag(Loc, DiagId));
786
    }
787
788
789
790
791
792
793
794

    /// Add a stack of notes to a prior diagnostic.
    void addNotes(ArrayRef<PartialDiagnosticAt> Diags) {
      if (HasActiveDiagnostic) {
        EvalStatus.Diag->insert(EvalStatus.Diag->end(),
                                Diags.begin(), Diags.end());
      }
    }
795

796
797
798
799
    /// Should we continue evaluation after encountering a side-effect that we
    /// couldn't model?
    bool keepEvaluatingAfterSideEffect() {
      switch (EvalMode) {
800
      case EM_PotentialConstantExpression:
801
      case EM_PotentialConstantExpressionUnevaluated:
802
803
804
805
806
      case EM_EvaluateForOverflow:
      case EM_IgnoreSideEffects:
        return true;

      case EM_ConstantExpression:
807
      case EM_ConstantExpressionUnevaluated:
808
      case EM_ConstantFold:
809
      case EM_OffsetFold:
810
811
        return false;
      }
812
      llvm_unreachable("Missed EvalMode case");
813
814
815
816
817
818
819
820
821
    }

    /// Note that we have had a side-effect, and determine whether we should
    /// keep evaluating.
    bool noteSideEffect() {
      EvalStatus.HasSideEffects = true;
      return keepEvaluatingAfterSideEffect();
    }

822
823
824
825
826
827
    /// Should we continue evaluation after encountering undefined behavior?
    bool keepEvaluatingAfterUndefinedBehavior() {
      switch (EvalMode) {
      case EM_EvaluateForOverflow:
      case EM_IgnoreSideEffects:
      case EM_ConstantFold:
828
      case EM_OffsetFold:
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
        return true;

      case EM_PotentialConstantExpression:
      case EM_PotentialConstantExpressionUnevaluated:
      case EM_ConstantExpression:
      case EM_ConstantExpressionUnevaluated:
        return false;
      }
      llvm_unreachable("Missed EvalMode case");
    }

    /// Note that we hit something that was technically undefined behavior, but
    /// that we can evaluate past it (such as signed overflow or floating-point
    /// division by zero.)
    bool noteUndefinedBehavior() {
      EvalStatus.HasUndefinedBehavior = true;
      return keepEvaluatingAfterUndefinedBehavior();
    }

848
    /// Should we continue evaluation as much as possible after encountering a
849
    /// construct which can't be reduced to a value?
850
    bool keepEvaluatingAfterFailure() {
851
852
853
854
855
      if (!StepsLeft)
        return false;

      switch (EvalMode) {
      case EM_PotentialConstantExpression:
856
      case EM_PotentialConstantExpressionUnevaluated:
857
858
859
860
      case EM_EvaluateForOverflow:
        return true;

      case EM_ConstantExpression:
861
      case EM_ConstantExpressionUnevaluated:
862
863
      case EM_ConstantFold:
      case EM_IgnoreSideEffects:
864
      case EM_OffsetFold:
865
866
        return false;
      }
867
      llvm_unreachable("Missed EvalMode case");
868
    }
869

870
871
872
873
874
875
876
877
878
879
    /// Notes that we failed to evaluate an expression that other expressions
    /// directly depend on, and determine if we should keep evaluating. This
    /// should only be called if we actually intend to keep evaluating.
    ///
    /// Call noteSideEffect() instead if we may be able to ignore the value that
    /// we failed to evaluate, e.g. if we failed to evaluate Foo() in:
    ///
    /// (Foo(), 1)      // use noteSideEffect
    /// (Foo() || true) // use noteSideEffect
    /// Foo() + 1       // use noteFailure
880
    LLVM_NODISCARD bool noteFailure() {
881
882
883
884
885
886
887
888
889
890
891
892
      // Failure when evaluating some expression often means there is some
      // subexpression whose evaluation was skipped. Therefore, (because we
      // don't track whether we skipped an expression when unwinding after an
      // evaluation failure) every evaluation failure that bubbles up from a
      // subexpression implies that a side-effect has potentially happened. We
      // skip setting the HasSideEffects flag to true until we decide to
      // continue evaluating after that point, which happens here.
      bool KeepGoing = keepEvaluatingAfterFailure();
      EvalStatus.HasSideEffects |= KeepGoing;
      return KeepGoing;
    }

893
    bool allowInvalidBaseExpr() const {
894
      return EvalMode == EM_OffsetFold;
895
    }
896
897
898
899
900
901
902
903
904
905
906
907
908
909

    class ArrayInitLoopIndex {
      EvalInfo &Info;
      uint64_t OuterIndex;

    public:
      ArrayInitLoopIndex(EvalInfo &Info)
          : Info(Info), OuterIndex(Info.ArrayInitIndex) {
        Info.ArrayInitIndex = 0;
      }
      ~ArrayInitLoopIndex() { Info.ArrayInitIndex = OuterIndex; }

      operator uint64_t&() { return Info.ArrayInitIndex; }
    };
910
  };
Richard Smith's avatar
Richard Smith committed
911
912
913

  /// Object used to treat all foldable expressions as constant expressions.
  struct FoldConstant {
914
    EvalInfo &Info;
Richard Smith's avatar
Richard Smith committed
915
    bool Enabled;
916
917
918
919
920
921
922
923
924
925
    bool HadNoPriorDiags;
    EvalInfo::EvaluationMode OldMode;

    explicit FoldConstant(EvalInfo &Info, bool Enabled)
      : Info(Info),
        Enabled(Enabled),
        HadNoPriorDiags(Info.EvalStatus.Diag &&
                        Info.EvalStatus.Diag->empty() &&
                        !Info.EvalStatus.HasSideEffects),
        OldMode(Info.EvalMode) {
926
927
928
      if (Enabled &&
          (Info.EvalMode == EvalInfo::EM_ConstantExpression ||
           Info.EvalMode == EvalInfo::EM_ConstantExpressionUnevaluated))
929
930
931
932
933
        Info.EvalMode = EvalInfo::EM_ConstantFold;
    }
    void keepDiagnostics() { Enabled = false; }
    ~FoldConstant() {
      if (Enabled && HadNoPriorDiags && !Info.EvalStatus.Diag->empty() &&
Richard Smith's avatar
Richard Smith committed
934
935
          !Info.EvalStatus.HasSideEffects)
        Info.EvalStatus.Diag->clear();
936
      Info.EvalMode = OldMode;
Richard Smith's avatar
Richard Smith committed
937
938
    }
  };
Richard Smith's avatar
Richard Smith committed
939

940
941
942
943
944
  /// RAII object used to treat the current evaluation as the correct pointer
  /// offset fold for the current EvalMode
  struct FoldOffsetRAII {
    EvalInfo &Info;
    EvalInfo::EvaluationMode OldMode;
945
    explicit FoldOffsetRAII(EvalInfo &Info)
946
947
        : Info(Info), OldMode(Info.EvalMode) {
      if (!Info.checkingPotentialConstantExpression())
948
        Info.EvalMode = EvalInfo::EM_OffsetFold;
949
950
951
952
953
    }

    ~FoldOffsetRAII() { Info.EvalMode = OldMode; }
  };

954
955
  /// RAII object used to optionally suppress diagnostics and side-effects from
  /// a speculative evaluation.
Richard Smith's avatar
Richard Smith committed
956
  class SpeculativeEvaluationRAII {
957
958
959
    /// Pair of EvalInfo, and a bit that stores whether or not we were
    /// speculatively evaluating when we created this RAII.
    llvm::PointerIntPair<EvalInfo *, 1, bool> InfoAndOldSpecEval;
Richard Smith's avatar
Richard Smith committed
960
961
    Expr::EvalStatus Old;

962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
    void moveFromAndCancel(SpeculativeEvaluationRAII &&Other) {
      InfoAndOldSpecEval = Other.InfoAndOldSpecEval;
      Old = Other.Old;
      Other.InfoAndOldSpecEval.setPointer(nullptr);
    }

    void maybeRestoreState() {
      EvalInfo *Info = InfoAndOldSpecEval.getPointer();
      if (!Info)
        return;

      Info->EvalStatus = Old;
      Info->IsSpeculativelyEvaluating = InfoAndOldSpecEval.getInt();
    }

Richard Smith's avatar
Richard Smith committed
977
  public:
978
979
980
981
982
983
    SpeculativeEvaluationRAII() = default;

    SpeculativeEvaluationRAII(
        EvalInfo &Info, SmallVectorImpl<PartialDiagnosticAt> *NewDiag = nullptr)
        : InfoAndOldSpecEval(&Info, Info.IsSpeculativelyEvaluating),
          Old(Info.EvalStatus) {
Richard Smith's avatar
Richard Smith committed
984
      Info.EvalStatus.Diag = NewDiag;
985
      Info.IsSpeculativelyEvaluating = true;
Richard Smith's avatar
Richard Smith committed
986
    }
987
988
989
990

    SpeculativeEvaluationRAII(const SpeculativeEvaluationRAII &Other) = delete;
    SpeculativeEvaluationRAII(SpeculativeEvaluationRAII &&Other) {
      moveFromAndCancel(std::move(Other));
Richard Smith's avatar
Richard Smith committed
991
    }
992
993
994
995
996
997
998
999

    SpeculativeEvaluationRAII &operator=(SpeculativeEvaluationRAII &&Other) {
      maybeRestoreState();
      moveFromAndCancel(std::move(Other));
      return *this;
    }

    ~SpeculativeEvaluationRAII() { maybeRestoreState(); }
Richard Smith's avatar
Richard Smith committed
1000
  };
For faster browsing, not all history is shown. View entire blame