-
Notifications
You must be signed in to change notification settings - Fork 12.4k
/
Copy pathExprConstant.cpp
17844 lines (15735 loc) · 639 KB
/
ExprConstant.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
//===--- ExprConstant.cpp - Expression Constant Evaluator -----------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file implements the Expr constant evaluator.
//
// 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
// (under the C++11 / C++1y rules only, at the moment), or, if folding failed
// too, why the expression could not be folded.
//
// 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).
//
//===----------------------------------------------------------------------===//
#include "ByteCode/Context.h"
#include "ByteCode/Frame.h"
#include "ByteCode/State.h"
#include "ExprConstShared.h"
#include "clang/AST/APValue.h"
#include "clang/AST/ASTContext.h"
#include "clang/AST/ASTLambda.h"
#include "clang/AST/Attr.h"
#include "clang/AST/CXXInheritance.h"
#include "clang/AST/CharUnits.h"
#include "clang/AST/CurrentSourceLocExprScope.h"
#include "clang/AST/Expr.h"
#include "clang/AST/OSLog.h"
#include "clang/AST/OptionalDiagnostic.h"
#include "clang/AST/RecordLayout.h"
#include "clang/AST/StmtVisitor.h"
#include "clang/AST/TypeLoc.h"
#include "clang/Basic/Builtins.h"
#include "clang/Basic/DiagnosticSema.h"
#include "clang/Basic/TargetBuiltins.h"
#include "clang/Basic/TargetInfo.h"
#include "llvm/ADT/APFixedPoint.h"
#include "llvm/ADT/Sequence.h"
#include "llvm/ADT/SmallBitVector.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/SaveAndRestore.h"
#include "llvm/Support/SipHash.h"
#include "llvm/Support/TimeProfiler.h"
#include "llvm/Support/raw_ostream.h"
#include <cstring>
#include <functional>
#include <optional>
#define DEBUG_TYPE "exprconstant"
using namespace clang;
using llvm::APFixedPoint;
using llvm::APInt;
using llvm::APSInt;
using llvm::APFloat;
using llvm::FixedPointSemantics;
namespace {
struct LValue;
class CallStackFrame;
class EvalInfo;
using SourceLocExprScopeGuard =
CurrentSourceLocExprScope::SourceLocExprScopeGuard;
static QualType getType(APValue::LValueBase B) {
return B.getType();
}
/// Get an LValue path entry, which is known to not be an array index, as a
/// field declaration.
static const FieldDecl *getAsField(APValue::LValuePathEntry E) {
return dyn_cast_or_null<FieldDecl>(E.getAsBaseOrMember().getPointer());
}
/// Get an LValue path entry, which is known to not be an array index, as a
/// base class declaration.
static const CXXRecordDecl *getAsBaseClass(APValue::LValuePathEntry E) {
return dyn_cast_or_null<CXXRecordDecl>(E.getAsBaseOrMember().getPointer());
}
/// Determine whether this LValue path entry for a base class names a virtual
/// base class.
static bool isVirtualBaseClass(APValue::LValuePathEntry E) {
return E.getAsBaseOrMember().getInt();
}
/// Given an expression, determine the type used to store the result of
/// evaluating that expression.
static QualType getStorageType(const ASTContext &Ctx, const Expr *E) {
if (E->isPRValue())
return E->getType();
return Ctx.getLValueReferenceType(E->getType());
}
/// Given a CallExpr, try to get the alloc_size attribute. May return null.
static const AllocSizeAttr *getAllocSizeAttr(const CallExpr *CE) {
if (const FunctionDecl *DirectCallee = CE->getDirectCallee())
return DirectCallee->getAttr<AllocSizeAttr>();
if (const Decl *IndirectCallee = CE->getCalleeDecl())
return IndirectCallee->getAttr<AllocSizeAttr>();
return 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. In exotic cases, we might also see a
// top-level ExprWithCleanups. Ignore them either way.
if (const auto *FE = dyn_cast<FullExpr>(E))
E = FE->getSubExpr()->IgnoreParens();
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 whether the given kind of constant expression is only ever
/// used for name mangling. If so, it's permitted to reference things that we
/// can't generate code for (in particular, dllimported functions).
static bool isForManglingOnly(ConstantExprKind Kind) {
switch (Kind) {
case ConstantExprKind::Normal:
case ConstantExprKind::ClassTemplateArgument:
case ConstantExprKind::ImmediateInvocation:
// Note that non-type template arguments of class type are emitted as
// template parameter objects.
return false;
case ConstantExprKind::NonClassTemplateArgument:
return true;
}
llvm_unreachable("unknown ConstantExprKind");
}
static bool isTemplateArgument(ConstantExprKind Kind) {
switch (Kind) {
case ConstantExprKind::Normal:
case ConstantExprKind::ImmediateInvocation:
return false;
case ConstantExprKind::ClassTemplateArgument:
case ConstantExprKind::NonClassTemplateArgument:
return true;
}
llvm_unreachable("unknown ConstantExprKind");
}
/// The bound to claim that an array of unknown bound has.
/// 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.
static const uint64_t AssumedSizeForUnsizedArray =
std::numeric_limits<uint64_t>::max() / 2;
/// Determines if an LValue with the given LValueBase will have an unsized
/// array in its designator.
/// 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.
static unsigned
findMostDerivedSubobject(ASTContext &Ctx, APValue::LValueBase Base,
ArrayRef<APValue::LValuePathEntry> Path,
uint64_t &ArraySize, QualType &Type, bool &IsArray,
bool &FirstEntryIsUnsizedArray) {
// 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");
unsigned MostDerivedLength = 0;
Type = getType(Base);
for (unsigned I = 0, N = Path.size(); I != N; ++I) {
if (Type->isArrayType()) {
const ArrayType *AT = Ctx.getAsArrayType(Type);
Type = AT->getElementType();
MostDerivedLength = I + 1;
IsArray = true;
if (auto *CAT = dyn_cast<ConstantArrayType>(AT)) {
ArraySize = CAT->getZExtSize();
} else {
assert(I == 0 && "unexpected unsized array designator");
FirstEntryIsUnsizedArray = true;
ArraySize = AssumedSizeForUnsizedArray;
}
} else if (Type->isAnyComplexType()) {
const ComplexType *CT = Type->castAs<ComplexType>();
Type = CT->getElementType();
ArraySize = 2;
MostDerivedLength = I + 1;
IsArray = true;
} else if (const auto *VT = Type->getAs<VectorType>()) {
Type = VT->getElementType();
ArraySize = VT->getNumElements();
MostDerivedLength = I + 1;
IsArray = true;
} else if (const FieldDecl *FD = getAsField(Path[I])) {
Type = FD->getType();
ArraySize = 0;
MostDerivedLength = I + 1;
IsArray = false;
} else {
// Path[I] describes a base class.
ArraySize = 0;
IsArray = false;
}
}
return MostDerivedLength;
}
/// 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.
LLVM_PREFERRED_TYPE(bool)
unsigned Invalid : 1;
/// Is this a pointer one past the end of an object?
LLVM_PREFERRED_TYPE(bool)
unsigned IsOnePastTheEnd : 1;
/// Indicator of whether the first entry is an unsized array.
LLVM_PREFERRED_TYPE(bool)
unsigned FirstEntryIsAnUnsizedArray : 1;
/// Indicator of whether the most-derived object is an array element.
LLVM_PREFERRED_TYPE(bool)
unsigned MostDerivedIsArrayElement : 1;
/// The length of the path to the most-derived object of which this is a
/// subobject.
unsigned MostDerivedPathLength : 28;
/// 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.
///
/// If the current array is an unsized array, the value of this is
/// undefined.
uint64_t MostDerivedArraySize;
/// The type of the most derived object referred to by this address.
QualType MostDerivedType;
typedef APValue::LValuePathEntry PathEntry;
/// The entries on the path from the glvalue to the designated subobject.
SmallVector<PathEntry, 8> Entries;
SubobjectDesignator() : Invalid(true) {}
explicit SubobjectDesignator(QualType T)
: Invalid(false), IsOnePastTheEnd(false),
FirstEntryIsAnUnsizedArray(false), MostDerivedIsArrayElement(false),
MostDerivedPathLength(0), MostDerivedArraySize(0),
MostDerivedType(T) {}
SubobjectDesignator(ASTContext &Ctx, const APValue &V)
: Invalid(!V.isLValue() || !V.hasLValuePath()), IsOnePastTheEnd(false),
FirstEntryIsAnUnsizedArray(false), MostDerivedIsArrayElement(false),
MostDerivedPathLength(0), MostDerivedArraySize(0) {
assert(V.isLValue() && "Non-LValue used to make an LValue designator?");
if (!Invalid) {
IsOnePastTheEnd = V.isLValueOnePastTheEnd();
ArrayRef<PathEntry> VEntries = V.getLValuePath();
Entries.insert(Entries.end(), VEntries.begin(), VEntries.end());
if (V.getLValueBase()) {
bool IsArray = false;
bool FirstIsUnsizedArray = false;
MostDerivedPathLength = findMostDerivedSubobject(
Ctx, V.getLValueBase(), V.getLValuePath(), MostDerivedArraySize,
MostDerivedType, IsArray, FirstIsUnsizedArray);
MostDerivedIsArrayElement = IsArray;
FirstEntryIsAnUnsizedArray = FirstIsUnsizedArray;
}
}
}
void truncate(ASTContext &Ctx, APValue::LValueBase Base,
unsigned NewLength) {
if (Invalid)
return;
assert(Base && "cannot truncate path for null pointer");
assert(NewLength <= Entries.size() && "not a truncation");
if (NewLength == Entries.size())
return;
Entries.resize(NewLength);
bool IsArray = false;
bool FirstIsUnsizedArray = false;
MostDerivedPathLength = findMostDerivedSubobject(
Ctx, Base, Entries, MostDerivedArraySize, MostDerivedType, IsArray,
FirstIsUnsizedArray);
MostDerivedIsArrayElement = IsArray;
FirstEntryIsAnUnsizedArray = FirstIsUnsizedArray;
}
void setInvalid() {
Invalid = true;
Entries.clear();
}
/// 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;
}
/// Determine whether this is a one-past-the-end pointer.
bool isOnePastTheEnd() const {
assert(!Invalid);
if (IsOnePastTheEnd)
return true;
if (!isMostDerivedAnUnsizedArray() && MostDerivedIsArrayElement &&
Entries[MostDerivedPathLength - 1].getAsArrayIndex() ==
MostDerivedArraySize)
return true;
return false;
}
/// Get the range of valid index adjustments in the form
/// {maximum value that can be subtracted from this pointer,
/// maximum value that can be added to this pointer}
std::pair<uint64_t, uint64_t> validIndexAdjustments() {
if (Invalid || isMostDerivedAnUnsizedArray())
return {0, 0};
// [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.
bool IsArray = MostDerivedPathLength == Entries.size() &&
MostDerivedIsArrayElement;
uint64_t ArrayIndex = IsArray ? Entries.back().getAsArrayIndex()
: (uint64_t)IsOnePastTheEnd;
uint64_t ArraySize =
IsArray ? getMostDerivedArraySize() : (uint64_t)1;
return {ArrayIndex, ArraySize - ArrayIndex};
}
/// 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);
/// Get the type of the designated object.
QualType getType(ASTContext &Ctx) const {
assert(!Invalid && "invalid designator has no subobject type");
return MostDerivedPathLength == Entries.size()
? MostDerivedType
: Ctx.getRecordType(getAsBaseClass(Entries.back()));
}
/// Update this designator to refer to the first element within this array.
void addArrayUnchecked(const ConstantArrayType *CAT) {
Entries.push_back(PathEntry::ArrayIndex(0));
// This is a most-derived object.
MostDerivedType = CAT->getElementType();
MostDerivedIsArrayElement = true;
MostDerivedArraySize = CAT->getZExtSize();
MostDerivedPathLength = Entries.size();
}
/// 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) {
Entries.push_back(PathEntry::ArrayIndex(0));
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 = AssumedSizeForUnsizedArray;
MostDerivedPathLength = Entries.size();
}
/// Update this designator to refer to the given base or member of this
/// object.
void addDeclUnchecked(const Decl *D, bool Virtual = false) {
Entries.push_back(APValue::BaseOrMemberType(D, Virtual));
// 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();
MostDerivedIsArrayElement = false;
MostDerivedArraySize = 0;
MostDerivedPathLength = Entries.size();
}
}
/// Update this designator to refer to the given complex component.
void addComplexUnchecked(QualType EltTy, bool Imag) {
Entries.push_back(PathEntry::ArrayIndex(Imag));
// This is technically a most-derived object, though in practice this
// is unlikely to matter.
MostDerivedType = EltTy;
MostDerivedIsArrayElement = true;
MostDerivedArraySize = 2;
MostDerivedPathLength = Entries.size();
}
void addVectorElementUnchecked(QualType EltTy, uint64_t Size,
uint64_t Idx) {
Entries.push_back(PathEntry::ArrayIndex(Idx));
MostDerivedType = EltTy;
MostDerivedPathLength = Entries.size();
MostDerivedArraySize = 0;
MostDerivedIsArrayElement = false;
}
void diagnoseUnsizedArrayPointerArithmetic(EvalInfo &Info, const Expr *E);
void diagnosePointerArithmetic(EvalInfo &Info, const Expr *E,
const APSInt &N);
/// Add N to the address of this subobject.
void adjustIndex(EvalInfo &Info, const Expr *E, APSInt N) {
if (Invalid || !N) return;
uint64_t TruncatedN = N.extOrTrunc(64).getZExtValue();
if (isMostDerivedAnUnsizedArray()) {
diagnoseUnsizedArrayPointerArithmetic(Info, E);
// Can't verify -- trust that the user is doing the right thing (or if
// not, trust that the caller will catch the bad behavior).
// FIXME: Should we reject if this overflows, at least?
Entries.back() = PathEntry::ArrayIndex(
Entries.back().getAsArrayIndex() + TruncatedN);
return;
}
// [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.
bool IsArray = MostDerivedPathLength == Entries.size() &&
MostDerivedIsArrayElement;
uint64_t ArrayIndex = IsArray ? Entries.back().getAsArrayIndex()
: (uint64_t)IsOnePastTheEnd;
uint64_t ArraySize =
IsArray ? getMostDerivedArraySize() : (uint64_t)1;
if (N < -(int64_t)ArrayIndex || N > ArraySize - ArrayIndex) {
// Calculate the actual index in a wide enough type, so we can include
// it in the note.
N = N.extend(std::max<unsigned>(N.getBitWidth() + 1, 65));
(llvm::APInt&)N += ArrayIndex;
assert(N.ugt(ArraySize) && "bounds check failed for in-bounds index");
diagnosePointerArithmetic(Info, E, N);
setInvalid();
return;
}
ArrayIndex += TruncatedN;
assert(ArrayIndex <= ArraySize &&
"bounds check succeeded for out-of-bounds index");
if (IsArray)
Entries.back() = PathEntry::ArrayIndex(ArrayIndex);
else
IsOnePastTheEnd = (ArrayIndex != 0);
}
};
/// A scope at the end of which an object can need to be destroyed.
enum class ScopeKind {
Block,
FullExpression,
Call
};
/// A reference to a particular call and its arguments.
struct CallRef {
CallRef() : OrigCallee(), CallIndex(0), Version() {}
CallRef(const FunctionDecl *Callee, unsigned CallIndex, unsigned Version)
: OrigCallee(Callee), CallIndex(CallIndex), Version(Version) {}
explicit operator bool() const { return OrigCallee; }
/// Get the parameter that the caller initialized, corresponding to the
/// given parameter in the callee.
const ParmVarDecl *getOrigParam(const ParmVarDecl *PVD) const {
return OrigCallee ? OrigCallee->getParamDecl(PVD->getFunctionScopeIndex())
: PVD;
}
/// The callee at the point where the arguments were evaluated. This might
/// be different from the actual callee (a different redeclaration, or a
/// virtual override), but this function's parameters are the ones that
/// appear in the parameter map.
const FunctionDecl *OrigCallee;
/// The call index of the frame that holds the argument values.
unsigned CallIndex;
/// The version of the parameters corresponding to this call.
unsigned Version;
};
/// A stack frame in the constexpr call stack.
class CallStackFrame : public interp::Frame {
public:
EvalInfo &Info;
/// Parent - The caller of this stack frame.
CallStackFrame *Caller;
/// Callee - The function which was called.
const FunctionDecl *Callee;
/// This - The binding for the this pointer in this call, if any.
const LValue *This;
/// CallExpr - The syntactical structure of member function calls
const Expr *CallExpr;
/// Information on how to find the arguments to this call. Our arguments
/// are stored in our parent's CallStackFrame, using the ParmVarDecl* as a
/// key and this value as the version.
CallRef Arguments;
/// Source location information about the default argument or default
/// initializer expression we're evaluating, if any.
CurrentSourceLocExprScope CurSourceLocExprScope;
// Note that we intentionally use std::map here so that references to
// values are stable.
typedef std::pair<const void *, unsigned> MapKeyTy;
typedef std::map<MapKeyTy, APValue> MapTy;
/// Temporaries - Temporary lvalues materialized within this stack frame.
MapTy Temporaries;
/// CallRange - The source range of the call expression for this call.
SourceRange CallRange;
/// Index - The call index of this call.
unsigned Index;
/// The stack of integers for tracking version numbers for temporaries.
SmallVector<unsigned, 2> TempVersionStack = {1};
unsigned CurTempVersion = TempVersionStack.back();
unsigned getTempVersion() const { return TempVersionStack.back(); }
void pushTempVersion() {
TempVersionStack.push_back(++CurTempVersion);
}
void popTempVersion() {
TempVersionStack.pop_back();
}
CallRef createCall(const FunctionDecl *Callee) {
return {Callee, Index, ++CurTempVersion};
}
// FIXME: Adding this to every 'CallStackFrame' may have a nontrivial impact
// on the overall stack usage of deeply-recursing constexpr evaluations.
// (We should cache this map rather than recomputing it repeatedly.)
// But let's try this and see how it goes; we can look into caching the map
// as a later change.
/// LambdaCaptureFields - Mapping from captured variables/this to
/// corresponding data members in the closure class.
llvm::DenseMap<const ValueDecl *, FieldDecl *> LambdaCaptureFields;
FieldDecl *LambdaThisCaptureField = nullptr;
CallStackFrame(EvalInfo &Info, SourceRange CallRange,
const FunctionDecl *Callee, const LValue *This,
const Expr *CallExpr, CallRef Arguments);
~CallStackFrame();
// Return the temporary for Key whose version number is Version.
APValue *getTemporary(const void *Key, unsigned Version) {
MapKeyTy KV(Key, Version);
auto LB = Temporaries.lower_bound(KV);
if (LB != Temporaries.end() && LB->first == KV)
return &LB->second;
return nullptr;
}
// Return the current temporary for Key in the map.
APValue *getCurrentTemporary(const void *Key) {
auto UB = Temporaries.upper_bound(MapKeyTy(Key, UINT_MAX));
if (UB != Temporaries.begin() && std::prev(UB)->first.first == Key)
return &std::prev(UB)->second;
return nullptr;
}
// Return the version number of the current temporary for Key.
unsigned getCurrentTemporaryVersion(const void *Key) const {
auto UB = Temporaries.upper_bound(MapKeyTy(Key, UINT_MAX));
if (UB != Temporaries.begin() && std::prev(UB)->first.first == Key)
return std::prev(UB)->first.second;
return 0;
}
/// Allocate storage for an object of type T in this stack frame.
/// Populates LV with a handle to the created object. Key identifies
/// the temporary within the stack frame, and must not be reused without
/// bumping the temporary version number.
template<typename KeyT>
APValue &createTemporary(const KeyT *Key, QualType T,
ScopeKind Scope, LValue &LV);
/// Allocate storage for a parameter of a function call made in this frame.
APValue &createParam(CallRef Args, const ParmVarDecl *PVD, LValue &LV);
void describe(llvm::raw_ostream &OS) const override;
Frame *getCaller() const override { return Caller; }
SourceRange getCallRange() const override { return CallRange; }
const FunctionDecl *getCallee() const override { return Callee; }
bool isStdFunction() const {
for (const DeclContext *DC = Callee; DC; DC = DC->getParent())
if (DC->isStdNamespace())
return true;
return false;
}
/// Whether we're in a context where [[msvc::constexpr]] evaluation is
/// permitted. See MSConstexprDocs for description of permitted contexts.
bool CanEvalMSConstexpr = false;
private:
APValue &createLocal(APValue::LValueBase Base, const void *Key, QualType T,
ScopeKind Scope);
};
/// 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;
};
// A shorthand time trace scope struct, prints source range, for example
// {"name":"EvaluateAsRValue","args":{"detail":"<test.cc:8:21, col:25>"}}}
class ExprTimeTraceScope {
public:
ExprTimeTraceScope(const Expr *E, const ASTContext &Ctx, StringRef Name)
: TimeScope(Name, [E, &Ctx] {
return E->getSourceRange().printToString(Ctx.getSourceManager());
}) {}
private:
llvm::TimeTraceScope TimeScope;
};
/// RAII object used to change the current ability of
/// [[msvc::constexpr]] evaulation.
struct MSConstexprContextRAII {
CallStackFrame &Frame;
bool OldValue;
explicit MSConstexprContextRAII(CallStackFrame &Frame, bool Value)
: Frame(Frame), OldValue(Frame.CanEvalMSConstexpr) {
Frame.CanEvalMSConstexpr = Value;
}
~MSConstexprContextRAII() { Frame.CanEvalMSConstexpr = OldValue; }
};
}
static bool HandleDestruction(EvalInfo &Info, const Expr *E,
const LValue &This, QualType ThisType);
static bool HandleDestruction(EvalInfo &Info, SourceLocation Loc,
APValue::LValueBase LVBase, APValue &Value,
QualType T);
namespace {
/// A cleanup, and a flag indicating whether it is lifetime-extended.
class Cleanup {
llvm::PointerIntPair<APValue*, 2, ScopeKind> Value;
APValue::LValueBase Base;
QualType T;
public:
Cleanup(APValue *Val, APValue::LValueBase Base, QualType T,
ScopeKind Scope)
: Value(Val, Scope), Base(Base), T(T) {}
/// Determine whether this cleanup should be performed at the end of the
/// given kind of scope.
bool isDestroyedAtEndOf(ScopeKind K) const {
return (int)Value.getInt() >= (int)K;
}
bool endLifetime(EvalInfo &Info, bool RunDestructors) {
if (RunDestructors) {
SourceLocation Loc;
if (const ValueDecl *VD = Base.dyn_cast<const ValueDecl*>())
Loc = VD->getLocation();
else if (const Expr *E = Base.dyn_cast<const Expr*>())
Loc = E->getExprLoc();
return HandleDestruction(Info, Loc, Base, *Value.getPointer(), T);
}
*Value.getPointer() = APValue();
return true;
}
bool hasSideEffect() {
return T.isDestructedType();
}
};
/// A reference to an object whose construction we are currently evaluating.
struct ObjectUnderConstruction {
APValue::LValueBase Base;
ArrayRef<APValue::LValuePathEntry> Path;
friend bool operator==(const ObjectUnderConstruction &LHS,
const ObjectUnderConstruction &RHS) {
return LHS.Base == RHS.Base && LHS.Path == RHS.Path;
}
friend llvm::hash_code hash_value(const ObjectUnderConstruction &Obj) {
return llvm::hash_combine(Obj.Base, Obj.Path);
}
};
enum class ConstructionPhase {
None,
Bases,
AfterBases,
AfterFields,
Destroying,
DestroyingBases
};
}
namespace llvm {
template<> struct DenseMapInfo<ObjectUnderConstruction> {
using Base = DenseMapInfo<APValue::LValueBase>;
static ObjectUnderConstruction getEmptyKey() {
return {Base::getEmptyKey(), {}}; }
static ObjectUnderConstruction getTombstoneKey() {
return {Base::getTombstoneKey(), {}};
}
static unsigned getHashValue(const ObjectUnderConstruction &Object) {
return hash_value(Object);
}
static bool isEqual(const ObjectUnderConstruction &LHS,
const ObjectUnderConstruction &RHS) {
return LHS == RHS;
}
};
}
namespace {
/// A dynamically-allocated heap object.
struct DynAlloc {
/// The value of this heap-allocated object.
APValue Value;
/// The allocating expression; used for diagnostics. Either a CXXNewExpr
/// or a CallExpr (the latter is for direct calls to operator new inside
/// std::allocator<T>::allocate).
const Expr *AllocExpr = nullptr;
enum Kind {
New,
ArrayNew,
StdAllocator
};
/// Get the kind of the allocation. This must match between allocation
/// and deallocation.
Kind getKind() const {
if (auto *NE = dyn_cast<CXXNewExpr>(AllocExpr))
return NE->isArray() ? ArrayNew : New;
assert(isa<CallExpr>(AllocExpr));
return StdAllocator;
}
};
struct DynAllocOrder {
bool operator()(DynamicAllocLValue L, DynamicAllocLValue R) const {
return L.getIndex() < R.getIndex();
}
};
/// 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.
class EvalInfo : public interp::State {
public:
ASTContext &Ctx;
/// EvalStatus - Contains information about the evaluation.
Expr::EvalStatus &EvalStatus;
/// CurrentCall - The top of the constexpr call stack.
CallStackFrame *CurrentCall;
/// CallStackDepth - The number of calls in the call stack right now.
unsigned CallStackDepth;
/// NextCallIndex - The next call index to assign.
unsigned NextCallIndex;
/// 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;
/// Enable the experimental new constant interpreter. If an expression is
/// not supported by the interpreter, an error is triggered.
bool EnableNewConstInterp;
/// BottomFrame - The frame in which evaluation started. This must be
/// initialized after CurrentCall and CallStackDepth.
CallStackFrame BottomFrame;
/// A stack of values whose lifetimes end at the end of some surrounding
/// evaluation frame.
llvm::SmallVector<Cleanup, 16> CleanupStack;
/// EvaluatingDecl - This is the declaration whose initializer is being
/// evaluated, if any.
APValue::LValueBase EvaluatingDecl;
enum class EvaluatingDeclKind {
None,
/// We're evaluating the construction of EvaluatingDecl.
Ctor,
/// We're evaluating the destruction of EvaluatingDecl.
Dtor,
};
EvaluatingDeclKind IsEvaluatingDecl = EvaluatingDeclKind::None;
/// EvaluatingDeclValue - This is the value being constructed for the
/// declaration whose initializer is being evaluated, if any.
APValue *EvaluatingDeclValue;
/// Set of objects that are currently being constructed.
llvm::DenseMap<ObjectUnderConstruction, ConstructionPhase>
ObjectsUnderConstruction;
/// Current heap allocations, along with the location where each was
/// allocated. We use std::map here because we need stable addresses
/// for the stored APValues.
std::map<DynamicAllocLValue, DynAlloc, DynAllocOrder> HeapAllocs;
/// The number of heap allocations performed so far in this evaluation.
unsigned NumHeapAllocs = 0;
struct EvaluatingConstructorRAII {
EvalInfo &EI;
ObjectUnderConstruction Object;
bool DidInsert;
EvaluatingConstructorRAII(EvalInfo &EI, ObjectUnderConstruction Object,
bool HasBases)
: EI(EI), Object(Object) {
DidInsert =
EI.ObjectsUnderConstruction
.insert({Object, HasBases ? ConstructionPhase::Bases
: ConstructionPhase::AfterBases})
.second;
}
void finishedConstructingBases() {
EI.ObjectsUnderConstruction[Object] = ConstructionPhase::AfterBases;
}
void finishedConstructingFields() {
EI.ObjectsUnderConstruction[Object] = ConstructionPhase::AfterFields;
}
~EvaluatingConstructorRAII() {
if (DidInsert) EI.ObjectsUnderConstruction.erase(Object);
}
};
struct EvaluatingDestructorRAII {
EvalInfo &EI;
ObjectUnderConstruction Object;
bool DidInsert;
EvaluatingDestructorRAII(EvalInfo &EI, ObjectUnderConstruction Object)
: EI(EI), Object(Object) {
DidInsert = EI.ObjectsUnderConstruction
.insert({Object, ConstructionPhase::Destroying})
.second;
}
void startedDestroyingBases() {
EI.ObjectsUnderConstruction[Object] =
ConstructionPhase::DestroyingBases;
}
~EvaluatingDestructorRAII() {
if (DidInsert)
EI.ObjectsUnderConstruction.erase(Object);
}
};
ConstructionPhase
isEvaluatingCtorDtor(APValue::LValueBase Base,
ArrayRef<APValue::LValuePathEntry> Path) {
return ObjectsUnderConstruction.lookup({Base, Path});
}
/// If we're currently speculatively evaluating, the outermost call stack
/// depth at which we can mutate state, otherwise 0.
unsigned SpeculativeEvaluationDepth = 0;
/// The current array initialization index, if we're performing array
/// initialization.
uint64_t ArrayInitIndex = -1;
/// HasActiveDiagnostic - Was the previous diagnostic stored? If so, further
/// notes attached to it will also be stored, otherwise they will not be.
bool HasActiveDiagnostic;
/// Have we emitted a diagnostic explaining why we couldn't constant
/// fold (not just why it's not strictly a constant expression)?
bool HasFoldFailureDiagnostic;
/// Whether we're checking that an expression is a potential constant
/// expression. If so, do not fail on constructs that could become constant
/// later on (such as a use of an undefined global).
bool CheckingPotentialConstantExpression = false;
/// Whether we're checking for an expression that has undefined behavior.
/// If so, we will produce warnings if we encounter an operation that is
/// always undefined.
///
/// Note that we still need to evaluate the expression normally when this
/// is set; this is used when evaluating ICEs in C.
bool CheckingForUndefinedBehavior = false;
enum EvaluationMode {
/// Evaluate as a constant expression. Stop if we find that the expression
/// is not a constant expression.
EM_ConstantExpression,
/// 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,
/// Fold the expression to a constant. Stop if we hit a side-effect that
/// we can't model.
EM_ConstantFold,