1// Licensed to the .NET Foundation under one or more agreements.
2// The .NET Foundation licenses this file to you under the MIT license.
3// See the LICENSE file in the project root for more information.
4
5// Defines the class "ValueNumStore", which maintains value numbers for a compilation.
6
7// Recall that "value numbering" assigns an integer value number to each expression. The "value
8// number property" is that two expressions with the same value number will evaluate to the same value
9// at runtime. Expressions with different value numbers may or may not be equivalent. This property
10// of value numbers has obvious applications in redundancy-elimination optimizations.
11//
12// Since value numbers give us a way of talking about the (immutable) values to which expressions
13// evaluate, they provide a good "handle" to use for attributing properties to values. For example,
14// we might note that some value number represents some particular integer constant -- which has obvious
15// application to constant propagation. Or that we know the exact type of some object reference,
16// which might be used in devirtualization.
17//
18// Finally, we will also use value numbers to express control-flow-dependent assertions. Some test may
19// imply that after the test, something new is known about a value: that an object reference is non-null
20// after a dereference (since control flow continued because no exception was thrown); that an integer value
21// is restricted to some subrange in after a comparison test; etc.
22
23/*****************************************************************************/
24#ifndef _VALUENUM_H_
25#define _VALUENUM_H_
26/*****************************************************************************/
27
28#include "vartype.h"
29// For "GT_COUNT"
30#include "gentree.h"
31// Defines the type ValueNum.
32#include "valuenumtype.h"
33// Defines the type SmallHashTable.
34#include "smallhash.h"
35
36// A "ValueNumStore" represents the "universe" of value numbers used in a single
37// compilation.
38
39// All members of the enumeration genTreeOps are also members of VNFunc.
40// (Though some of these may be labeled "illegal").
41enum VNFunc
42{
43 // Implicitly, elements of genTreeOps here.
44 VNF_Boundary = GT_COUNT,
45#define ValueNumFuncDef(nm, arity, commute, knownNonNull, sharedStatic) VNF_##nm,
46#include "valuenumfuncs.h"
47 VNF_COUNT
48};
49
50enum VNOperKind
51{
52 VOK_Default,
53 VOK_Unsigned,
54 VOK_OverflowCheck,
55 VOK_Unsigned_OverflowCheck
56};
57
58// Given the bool values isUnsigned and overflowCheck return the proper VNOperKInd enum
59//
60VNOperKind VNGetOperKind(bool isUnsigned, bool overflowCheck);
61
62// Given an "oper" and associated flags with it, transform the oper into a
63// more accurate oper that can be used in evaluation.
64// For example, (GT_ADD, true, false) transforms to GT_ADD_UN
65// and (GT_ADD, false, true) transforms to GT_ADD_OVF
66//
67VNFunc GetVNFuncForOper(genTreeOps oper, VNOperKind operKind);
68
69// Given a GenTree node return the VNFunc that shodul be used when value numbering
70//
71VNFunc GetVNFuncForNode(GenTree* node);
72
73// An instance of this struct represents an application of the function symbol
74// "m_func" to the first "m_arity" (<= 4) argument values in "m_args."
75struct VNFuncApp
76{
77 VNFunc m_func;
78 unsigned m_arity;
79 ValueNum m_args[4];
80
81 bool Equals(const VNFuncApp& funcApp)
82 {
83 if (m_func != funcApp.m_func)
84 {
85 return false;
86 }
87 if (m_arity != funcApp.m_arity)
88 {
89 return false;
90 }
91 for (unsigned i = 0; i < m_arity; i++)
92 {
93 if (m_args[i] != funcApp.m_args[i])
94 {
95 return false;
96 }
97 }
98 return true;
99 }
100};
101
102// We use a unique prefix character when printing value numbers in dumps: i.e. $1c0
103// This define is used with string concatenation to put this in printf format strings
104#define FMT_VN "$%x"
105
106class ValueNumStore
107{
108
109public:
110 // We will reserve "max unsigned" to represent "not a value number", for maps that might start uninitialized.
111 static const ValueNum NoVN = UINT32_MAX;
112 // A second special value, used to indicate that a function evaluation would cause infinite recursion.
113 static const ValueNum RecursiveVN = UINT32_MAX - 1;
114
115 // ==================================================================================================
116 // VNMap - map from something to ValueNum, where something is typically a constant value or a VNFunc
117 // This class has two purposes - to abstract the implementation and to validate the ValueNums
118 // being stored or retrieved.
119 template <class fromType, class keyfuncs = JitLargePrimitiveKeyFuncs<fromType>>
120 class VNMap : public JitHashTable<fromType, keyfuncs, ValueNum>
121 {
122 public:
123 VNMap(CompAllocator alloc) : JitHashTable<fromType, keyfuncs, ValueNum>(alloc)
124 {
125 }
126 ~VNMap()
127 {
128 ~VNMap<fromType, keyfuncs>::JitHashTable();
129 }
130
131 bool Set(fromType k, ValueNum val)
132 {
133 assert(val != RecursiveVN);
134 return JitHashTable<fromType, keyfuncs, ValueNum>::Set(k, val);
135 }
136 bool Lookup(fromType k, ValueNum* pVal = nullptr) const
137 {
138 bool result = JitHashTable<fromType, keyfuncs, ValueNum>::Lookup(k, pVal);
139 assert(!result || *pVal != RecursiveVN);
140 return result;
141 }
142 };
143
144private:
145 Compiler* m_pComp;
146
147 // For allocations. (Other things?)
148 CompAllocator m_alloc;
149
150 // TODO-Cleanup: should transform "attribs" into a struct with bit fields. That would be simpler...
151
152 enum VNFOpAttrib
153 {
154 VNFOA_IllegalGenTreeOp = 0x1, // corresponds to a genTreeOps value that is not a legal VN func.
155 VNFOA_Commutative = 0x2, // 1 iff the function is commutative.
156 VNFOA_Arity = 0x4, // Bits 2..3 encode the arity.
157 VNFOA_AfterArity = 0x20, // Makes it clear what value the next flag(s) after Arity should have.
158 VNFOA_KnownNonNull = 0x20, // 1 iff the result is known to be non-null.
159 VNFOA_SharedStatic = 0x40, // 1 iff this VNF is represent one of the shared static jit helpers
160 };
161
162 static const unsigned VNFOA_ArityShift = 2;
163 static const unsigned VNFOA_ArityBits = 3;
164 static const unsigned VNFOA_MaxArity = (1 << VNFOA_ArityBits) - 1; // Max arity we can represent.
165 static const unsigned VNFOA_ArityMask = VNFOA_AfterArity - VNFOA_Arity;
166
167 // These enum constants are used to encode the cast operation in the lowest bits by VNForCastOper
168 enum VNFCastAttrib
169 {
170 VCA_UnsignedSrc = 0x01,
171
172 VCA_BitCount = 1, // the number of reserved bits
173 VCA_ReservedBits = 0x01, // i.e. (VCA_UnsignedSrc)
174 };
175
176 // An array of length GT_COUNT, mapping genTreeOp values to their VNFOpAttrib.
177 static UINT8* s_vnfOpAttribs;
178
179 // Returns "true" iff gtOper is a legal value number function.
180 // (Requires InitValueNumStoreStatics to have been run.)
181 static bool GenTreeOpIsLegalVNFunc(genTreeOps gtOper);
182
183 // Returns "true" iff "vnf" is a commutative (and thus binary) operator.
184 // (Requires InitValueNumStoreStatics to have been run.)
185 static bool VNFuncIsCommutative(VNFunc vnf);
186
187 // Returns "true" iff "vnf" is a comparison (and thus binary) operator.
188 static bool VNFuncIsComparison(VNFunc vnf);
189
190 // Returns "true" iff "vnf" can be evaluated for constant arguments.
191 static bool CanEvalForConstantArgs(VNFunc vnf);
192
193 // Returns "true" iff "vnf" should be folded by evaluating the func with constant arguments.
194 bool VNEvalShouldFold(var_types typ, VNFunc func, ValueNum arg0VN, ValueNum arg1VN);
195
196 // return vnf(v0)
197 template <typename T>
198 static T EvalOp(VNFunc vnf, T v0);
199
200 // returns vnf(v0, v1).
201 template <typename T>
202 T EvalOp(VNFunc vnf, T v0, T v1);
203
204 // return vnf(v0) or vnf(v0, v1), respectively (must, of course be unary/binary ops, respectively.)
205 template <typename T>
206 static T EvalOpSpecialized(VNFunc vnf, T v0);
207 template <typename T>
208 T EvalOpSpecialized(VNFunc vnf, T v0, T v1);
209
210 template <typename T>
211 static int EvalComparison(VNFunc vnf, T v0, T v1);
212
213 // Should only instantiate (in a non-trivial way) for "int" and "INT64". Returns true iff dividing "v0" by "v1"
214 // would produce integer overflow (an ArithmeticException -- *not* division by zero, which is separate.)
215 template <typename T>
216 static bool IsOverflowIntDiv(T v0, T v1);
217
218 // Should only instantiate (in a non-trivial way) for integral types (signed/unsigned int32/int64).
219 // Returns true iff v is the zero of the appropriate type.
220 template <typename T>
221 static bool IsIntZero(T v);
222
223 // Given an constant value number return its value.
224 int GetConstantInt32(ValueNum argVN);
225 INT64 GetConstantInt64(ValueNum argVN);
226 double GetConstantDouble(ValueNum argVN);
227 float GetConstantSingle(ValueNum argVN);
228
229 // Assumes that all the ValueNum arguments of each of these functions have been shown to represent constants.
230 // Assumes that "vnf" is a operator of the appropriate arity (unary for the first, binary for the second).
231 // Assume that "CanEvalForConstantArgs(vnf)" is true.
232 // Returns the result of evaluating the function with those constant arguments.
233 ValueNum EvalFuncForConstantArgs(var_types typ, VNFunc vnf, ValueNum vn0);
234 ValueNum EvalFuncForConstantArgs(var_types typ, VNFunc vnf, ValueNum vn0, ValueNum vn1);
235 ValueNum EvalFuncForConstantFPArgs(var_types typ, VNFunc vnf, ValueNum vn0, ValueNum vn1);
236 ValueNum EvalCastForConstantArgs(var_types typ, VNFunc vnf, ValueNum vn0, ValueNum vn1);
237
238 ValueNum EvalUsingMathIdentity(var_types typ, VNFunc vnf, ValueNum vn0, ValueNum vn1);
239
240// This is the constant value used for the default value of m_mapSelectBudget
241#define DEFAULT_MAP_SELECT_BUDGET 100 // used by JitVNMapSelBudget
242
243 // This is the maximum number of MapSelect terms that can be "considered" as part of evaluation of a top-level
244 // MapSelect application.
245 int m_mapSelectBudget;
246
247public:
248 // Initializes any static variables of ValueNumStore.
249 static void InitValueNumStoreStatics();
250
251 // Initialize an empty ValueNumStore.
252 ValueNumStore(Compiler* comp, CompAllocator allocator);
253
254 // Returns "true" iff "vnf" (which may have been created by a cast from an integral value) represents
255 // a legal value number function.
256 // (Requires InitValueNumStoreStatics to have been run.)
257 static bool VNFuncIsLegal(VNFunc vnf)
258 {
259 return unsigned(vnf) > VNF_Boundary || GenTreeOpIsLegalVNFunc(static_cast<genTreeOps>(vnf));
260 }
261
262 // Returns the arity of "vnf".
263 static unsigned VNFuncArity(VNFunc vnf);
264
265 // Requires "gtOper" to be a genTreeOps legally representing a VNFunc, and returns that
266 // VNFunc.
267 // (Requires InitValueNumStoreStatics to have been run.)
268 static VNFunc GenTreeOpToVNFunc(genTreeOps gtOper)
269 {
270 assert(GenTreeOpIsLegalVNFunc(gtOper));
271 return static_cast<VNFunc>(gtOper);
272 }
273
274#ifdef DEBUG
275 static void RunTests(Compiler* comp);
276#endif // DEBUG
277
278 // This block of methods gets value numbers for constants of primitive types.
279
280 ValueNum VNForIntCon(INT32 cnsVal);
281 ValueNum VNForLongCon(INT64 cnsVal);
282 ValueNum VNForFloatCon(float cnsVal);
283 ValueNum VNForDoubleCon(double cnsVal);
284 ValueNum VNForByrefCon(INT64 byrefVal);
285
286#ifdef _TARGET_64BIT_
287 ValueNum VNForPtrSizeIntCon(INT64 cnsVal)
288 {
289 return VNForLongCon(cnsVal);
290 }
291#else
292 ValueNum VNForPtrSizeIntCon(INT32 cnsVal)
293 {
294 return VNForIntCon(cnsVal);
295 }
296#endif
297
298 ValueNum VNForCastOper(var_types castToType, bool srcIsUnsigned = false);
299
300 // We keep handle values in a separate pool, so we don't confuse a handle with an int constant
301 // that happens to be the same...
302 ValueNum VNForHandle(ssize_t cnsVal, unsigned iconFlags);
303
304 // And the single constant for an object reference type.
305 static ValueNum VNForNull()
306 {
307 // We reserve Chunk 0 for "special" VNs. SRC_Null (== 0) is the VN of "null".
308 return ValueNum(SRC_Null);
309 }
310
311 // The zero map is the map that returns a zero "for the appropriate type" when indexed at any index.
312 static ValueNum VNForZeroMap()
313 {
314 // We reserve Chunk 0 for "special" VNs. Let SRC_ZeroMap (== 1) be the zero map.
315 return ValueNum(SRC_ZeroMap);
316 }
317
318 // The ROH map is the map for the "read-only heap". We assume that this is never mutated, and always
319 // has the same value number.
320 static ValueNum VNForROH()
321 {
322 // We reserve Chunk 0 for "special" VNs. Let SRC_ReadOnlyHeap (== 3) be the read-only heap.
323 return ValueNum(SRC_ReadOnlyHeap);
324 }
325
326 // A special value number for "void" -- sometimes a type-void thing is an argument to a
327 // GT_LIST, and we want the args to be non-NoVN.
328 static ValueNum VNForVoid()
329 {
330 // We reserve Chunk 0 for "special" VNs. Let SRC_Void (== 4) be the value for "void".
331 return ValueNum(SRC_Void);
332 }
333 static ValueNumPair VNPForVoid()
334 {
335 return ValueNumPair(VNForVoid(), VNForVoid());
336 }
337
338 // A special value number for the empty set of exceptions.
339 static ValueNum VNForEmptyExcSet()
340 {
341 // We reserve Chunk 0 for "special" VNs. Let SRC_EmptyExcSet (== 5) be the value for the empty set of
342 // exceptions.
343 return ValueNum(SRC_EmptyExcSet);
344 }
345 static ValueNumPair VNPForEmptyExcSet()
346 {
347 return ValueNumPair(VNForEmptyExcSet(), VNForEmptyExcSet());
348 }
349
350 // Returns the value number for zero of the given "typ".
351 // It has an unreached() for a "typ" that has no zero value, such as TYP_BYREF.
352 ValueNum VNZeroForType(var_types typ);
353
354 // Returns the value number for one of the given "typ".
355 // It returns NoVN for a "typ" that has no one value, such as TYP_REF.
356 ValueNum VNOneForType(var_types typ);
357
358 // Create or return the existimg value number representing a singleton exception set
359 // for the the exception value "x".
360 ValueNum VNExcSetSingleton(ValueNum x);
361 ValueNumPair VNPExcSetSingleton(ValueNumPair x);
362
363 // Returns true if the current pair of items are in ascending order and they are not duplicates.
364 // Used to verify that exception sets are in ascending order when processing them.
365 bool VNCheckAscending(ValueNum item, ValueNum xs1);
366
367 // Returns the VN representing the union of the two exception sets "xs0" and "xs1".
368 // These must be VNForEmtpyExcSet() or applications of VNF_ExcSetCons, obeying
369 // the ascending order invariant. (which is preserved in the result)
370 ValueNum VNExcSetUnion(ValueNum xs0, ValueNum xs1);
371
372 ValueNumPair VNPExcSetUnion(ValueNumPair xs0vnp, ValueNumPair xs1vnp);
373
374 // Returns the VN representing the intersection of the two exception sets "xs0" and "xs1".
375 // These must be applications of VNF_ExcSetCons or the empty set. (i.e VNForEmptyExcSet())
376 // and also must be in ascending order.
377 ValueNum VNExcSetIntersection(ValueNum xs0, ValueNum xs1);
378
379 ValueNumPair VNPExcSetIntersection(ValueNumPair xs0vnp, ValueNumPair xs1vnp);
380
381 // Returns true if every exeception singleton in the vnCandidateSet is also present
382 // in the vnFullSet.
383 // Both arguments must be either VNForEmptyExcSet() or applications of VNF_ExcSetCons.
384 bool VNExcIsSubset(ValueNum vnFullSet, ValueNum vnCandidateSet);
385
386 // Returns "true" iff "vn" is an application of "VNF_ValWithExc".
387 bool VNHasExc(ValueNum vn)
388 {
389 VNFuncApp funcApp;
390 return GetVNFunc(vn, &funcApp) && funcApp.m_func == VNF_ValWithExc;
391 }
392
393 // If vn "excSet" is "VNForEmptyExcSet()" we just return "vn"
394 // otherwise we use VNExcSetUnion to combine the exception sets of both "vn" and "excSet"
395 // and return that ValueNum
396 ValueNum VNWithExc(ValueNum vn, ValueNum excSet);
397
398 ValueNumPair VNPWithExc(ValueNumPair vnp, ValueNumPair excSetVNP);
399
400 // This sets "*pvn" to the Normal value and sets "*pvnx" to Exception set value.
401 // "pvnx" represents the set of all exceptions that can happen for the expression
402 void VNUnpackExc(ValueNum vnWx, ValueNum* pvn, ValueNum* pvnx);
403
404 void VNPUnpackExc(ValueNumPair vnWx, ValueNumPair* pvn, ValueNumPair* pvnx);
405
406 // This returns the Union of exceptions from vnWx and vnExcSet
407 ValueNum VNUnionExcSet(ValueNum vnWx, ValueNum vnExcSet);
408
409 // This returns the Union of exceptions from vnpWx and vnpExcSet
410 ValueNumPair VNPUnionExcSet(ValueNumPair vnpWx, ValueNumPair vnpExcSet);
411
412 // Sets the normal value to a new unique ValueNum
413 // Keeps any Exception set values
414 ValueNum VNMakeNormalUnique(ValueNum vn);
415
416 // Sets the liberal & conservative
417 // Keeps any Exception set values
418 ValueNumPair VNPMakeNormalUniquePair(ValueNumPair vnp);
419
420 // If "vn" is a "VNF_ValWithExc(norm, excSet)" value, returns the "norm" argument; otherwise,
421 // just returns "vn".
422 // The Normal value is the value number of the expression when no exceptions occurred
423 ValueNum VNNormalValue(ValueNum vn);
424
425 // Given a "vnp", get the ValueNum kind based upon vnk,
426 // then call VNNormalValue on that ValueNum
427 // The Normal value is the value number of the expression when no exceptions occurred
428 ValueNum VNNormalValue(ValueNumPair vnp, ValueNumKind vnk);
429
430 // Given a "vnp", get the NormalValuew for the VNK_Liberal part of that ValueNum
431 // The Normal value is the value number of the expression when no exceptions occurred
432 inline ValueNum VNLiberalNormalValue(ValueNumPair vnp)
433 {
434 return VNNormalValue(vnp, VNK_Liberal);
435 }
436
437 // Given a "vnp", get the NormalValuew for the VNK_Conservative part of that ValueNum
438 // The Normal value is the value number of the expression when no exceptions occurred
439 inline ValueNum VNConservativeNormalValue(ValueNumPair vnp)
440 {
441 return VNNormalValue(vnp, VNK_Conservative);
442 }
443
444 // Given a "vnp", get the Normal values for both the liberal and conservative parts of "vnp"
445 // The Normal value is the value number of the expression when no exceptions occurred
446 ValueNumPair VNPNormalPair(ValueNumPair vnp);
447
448 // If "vn" is a "VNF_ValWithExc(norm, excSet)" value, returns the "excSet" argument; otherwise,
449 // we return a special Value Number representing the empty exception set.
450 // The exeception set value is the value number of the set of possible exceptions.
451 ValueNum VNExceptionSet(ValueNum vn);
452
453 ValueNumPair VNPExceptionSet(ValueNumPair vn);
454
455 // True "iff" vn is a value known to be non-null. (For example, the result of an allocation...)
456 bool IsKnownNonNull(ValueNum vn);
457
458 // True "iff" vn is a value returned by a call to a shared static helper.
459 bool IsSharedStatic(ValueNum vn);
460
461 // VNForFunc: We have five overloads, for arities 0, 1, 2, 3 and 4
462 ValueNum VNForFunc(var_types typ, VNFunc func);
463 ValueNum VNForFunc(var_types typ, VNFunc func, ValueNum opVNwx);
464 // This must not be used for VNF_MapSelect applications; instead use VNForMapSelect, below.
465 ValueNum VNForFunc(var_types typ, VNFunc func, ValueNum op1VNwx, ValueNum op2VNwx);
466 ValueNum VNForFunc(var_types typ, VNFunc func, ValueNum op1VNwx, ValueNum op2VNwx, ValueNum op3VNwx);
467
468 // The following four-op VNForFunc is used for VNF_PtrToArrElem, elemTypeEqVN, arrVN, inxVN, fldSeqVN
469 ValueNum VNForFunc(
470 var_types typ, VNFunc func, ValueNum op1VNwx, ValueNum op2VNwx, ValueNum op3VNwx, ValueNum op4VNwx);
471
472 // This requires a "ValueNumKind" because it will attempt, given "select(phi(m1, ..., mk), ind)", to evaluate
473 // "select(m1, ind)", ..., "select(mk, ind)" to see if they agree. It needs to know which kind of value number
474 // (liberal/conservative) to read from the SSA def referenced in the phi argument.
475 ValueNum VNForMapSelect(ValueNumKind vnk, var_types typ, ValueNum op1VN, ValueNum op2VN);
476
477 // A method that does the work for VNForMapSelect and may call itself recursively.
478 ValueNum VNForMapSelectWork(
479 ValueNumKind vnk, var_types typ, ValueNum op1VN, ValueNum op2VN, int* pBudget, bool* pUsedRecursiveVN);
480
481 // A specialized version of VNForFunc that is used for VNF_MapStore and provides some logging when verbose is set
482 ValueNum VNForMapStore(var_types typ, ValueNum arg0VN, ValueNum arg1VN, ValueNum arg2VN);
483
484 // These functions parallel the ones above, except that they take liberal/conservative VN pairs
485 // as arguments, and return such a pair (the pair of the function applied to the liberal args, and
486 // the function applied to the conservative args).
487 ValueNumPair VNPairForFunc(var_types typ, VNFunc func)
488 {
489 ValueNumPair res;
490 res.SetBoth(VNForFunc(typ, func));
491 return res;
492 }
493 ValueNumPair VNPairForFunc(var_types typ, VNFunc func, ValueNumPair opVN)
494 {
495 return ValueNumPair(VNForFunc(typ, func, opVN.GetLiberal()), VNForFunc(typ, func, opVN.GetConservative()));
496 }
497 ValueNumPair VNPairForFunc(var_types typ, VNFunc func, ValueNumPair op1VN, ValueNumPair op2VN)
498 {
499 return ValueNumPair(VNForFunc(typ, func, op1VN.GetLiberal(), op2VN.GetLiberal()),
500 VNForFunc(typ, func, op1VN.GetConservative(), op2VN.GetConservative()));
501 }
502 ValueNumPair VNPairForFunc(var_types typ, VNFunc func, ValueNumPair op1VN, ValueNumPair op2VN, ValueNumPair op3VN)
503 {
504 return ValueNumPair(VNForFunc(typ, func, op1VN.GetLiberal(), op2VN.GetLiberal(), op3VN.GetLiberal()),
505 VNForFunc(typ, func, op1VN.GetConservative(), op2VN.GetConservative(),
506 op3VN.GetConservative()));
507 }
508 ValueNumPair VNPairForFunc(
509 var_types typ, VNFunc func, ValueNumPair op1VN, ValueNumPair op2VN, ValueNumPair op3VN, ValueNumPair op4VN)
510 {
511 return ValueNumPair(VNForFunc(typ, func, op1VN.GetLiberal(), op2VN.GetLiberal(), op3VN.GetLiberal(),
512 op4VN.GetLiberal()),
513 VNForFunc(typ, func, op1VN.GetConservative(), op2VN.GetConservative(),
514 op3VN.GetConservative(), op4VN.GetConservative()));
515 }
516
517 // Get a new, unique value number for an expression that we're not equating to some function,
518 // which is the value of a tree in the given block.
519 ValueNum VNForExpr(BasicBlock* block, var_types typ = TYP_UNKNOWN);
520
521// This controls extra tracing of the "evaluation" of "VNF_MapSelect" functions.
522#define FEATURE_VN_TRACE_APPLY_SELECTORS 1
523
524 // Return the value number corresponding to constructing "MapSelect(map, f0)", where "f0" is the
525 // (value number of) the first field in "fieldSeq". (The type of this application will be the type of "f0".)
526 // If there are no remaining fields in "fieldSeq", return that value number; otherwise, return VNApplySelectors
527 // applied to that value number and the remainder of "fieldSeq". When the 'fieldSeq' specifies a TYP_STRUCT
528 // then the size of the struct is returned by 'wbFinalStructSize' (when it is non-null)
529 ValueNum VNApplySelectors(ValueNumKind vnk,
530 ValueNum map,
531 FieldSeqNode* fieldSeq,
532 size_t* wbFinalStructSize = nullptr);
533
534 // Used after VNApplySelectors has determined that "selectedVN" is contained in a Map using VNForMapSelect
535 // It determines whether the 'selectedVN' is of an appropriate type to be read using and indirection of 'indType'
536 // If it is appropriate type then 'selectedVN' is returned, otherwise it may insert a cast to indType
537 // or return a unique value number for an incompatible indType.
538 ValueNum VNApplySelectorsTypeCheck(ValueNum selectedVN, var_types indType, size_t structSize);
539
540 // Assumes that "map" represents a map that is addressable by the fields in "fieldSeq", to get
541 // to a value of the type of "rhs". Returns an expression for the RHS of an assignment, in the given "block",
542 // to a location containing value "map" that will change the field addressed by "fieldSeq" to "rhs", leaving
543 // all other indices in "map" the same.
544 ValueNum VNApplySelectorsAssign(
545 ValueNumKind vnk, ValueNum map, FieldSeqNode* fieldSeq, ValueNum rhs, var_types indType, BasicBlock* block);
546
547 // Used after VNApplySelectorsAssign has determined that "elem" is to be writen into a Map using VNForMapStore
548 // It determines whether the 'elem' is of an appropriate type to be writen using using an indirection of 'indType'
549 // It may insert a cast to indType or return a unique value number for an incompatible indType.
550 ValueNum VNApplySelectorsAssignTypeCoerce(ValueNum elem, var_types indType, BasicBlock* block);
551
552 ValueNumPair VNPairApplySelectors(ValueNumPair map, FieldSeqNode* fieldSeq, var_types indType);
553
554 ValueNumPair VNPairApplySelectorsAssign(
555 ValueNumPair map, FieldSeqNode* fieldSeq, ValueNumPair rhs, var_types indType, BasicBlock* block)
556 {
557 return ValueNumPair(VNApplySelectorsAssign(VNK_Liberal, map.GetLiberal(), fieldSeq, rhs.GetLiberal(), indType,
558 block),
559 VNApplySelectorsAssign(VNK_Conservative, map.GetConservative(), fieldSeq,
560 rhs.GetConservative(), indType, block));
561 }
562
563 // Compute the normal ValueNumber for a cast with no exceptions
564 ValueNum VNForCast(ValueNum srcVN, var_types castToType, var_types castFromType, bool srcIsUnsigned = false);
565
566 // Compute the ValueNumberPair for a cast
567 ValueNumPair VNPairForCast(ValueNumPair srcVNPair,
568 var_types castToType,
569 var_types castFromType,
570 bool srcIsUnsigned = false,
571 bool hasOverflowCheck = false);
572
573 // Returns true iff the VN represents an application of VNF_NotAField.
574 bool IsVNNotAField(ValueNum vn);
575
576 // PtrToLoc values need to express a field sequence as one of their arguments. VN for null represents
577 // empty sequence, otherwise, "FieldSeq(VN(FieldHandle), restOfSeq)".
578 ValueNum VNForFieldSeq(FieldSeqNode* fieldSeq);
579
580 // Requires that "vn" represents a field sequence, that is, is the result of a call to VNForFieldSeq.
581 // Returns the FieldSequence it represents.
582 FieldSeqNode* FieldSeqVNToFieldSeq(ValueNum vn);
583
584 // Both argument must represent field sequences; returns the value number representing the
585 // concatenation "fsVN1 || fsVN2".
586 ValueNum FieldSeqVNAppend(ValueNum fsVN1, ValueNum fsVN2);
587
588 // If "opA" has a PtrToLoc, PtrToArrElem, or PtrToStatic application as its value numbers, and "opB" is an integer
589 // with a "fieldSeq", returns the VN for the pointer form extended with the field sequence; or else NoVN.
590 ValueNum ExtendPtrVN(GenTree* opA, GenTree* opB);
591 // If "opA" has a PtrToLoc, PtrToArrElem, or PtrToStatic application as its value numbers, returns the VN for the
592 // pointer form extended with "fieldSeq"; or else NoVN.
593 ValueNum ExtendPtrVN(GenTree* opA, FieldSeqNode* fieldSeq);
594
595 // Queries on value numbers.
596 // All queries taking value numbers require that those value numbers are valid, that is, that
597 // they have been returned by previous "VNFor..." operations. They can assert false if this is
598 // not true.
599
600 // Returns TYP_UNKNOWN if the given value number has not been given a type.
601 var_types TypeOfVN(ValueNum vn);
602
603 // Returns MAX_LOOP_NUM if the given value number's loop nest is unknown or ill-defined.
604 BasicBlock::loopNumber LoopOfVN(ValueNum vn);
605
606 // Returns true iff the VN represents a (non-handle) constant.
607 bool IsVNConstant(ValueNum vn);
608
609 // Returns true iff the VN represents an integeral constant.
610 bool IsVNInt32Constant(ValueNum vn);
611
612 typedef SmallHashTable<ValueNum, bool, 8U> CheckedBoundVNSet;
613
614 // Returns true if the VN is known or likely to appear as the conservative value number
615 // of the length argument to a GT_ARR_BOUNDS_CHECK node.
616 bool IsVNCheckedBound(ValueNum vn);
617
618 // Record that a VN is known to appear as the conservative value number of the length
619 // argument to a GT_ARR_BOUNDS_CHECK node.
620 void SetVNIsCheckedBound(ValueNum vn);
621
622 // Information about the individual components of a value number representing an unsigned
623 // comparison of some value against a checked bound VN.
624 struct UnsignedCompareCheckedBoundInfo
625 {
626 unsigned cmpOper;
627 ValueNum vnIdx;
628 ValueNum vnBound;
629
630 UnsignedCompareCheckedBoundInfo() : cmpOper(GT_NONE), vnIdx(NoVN), vnBound(NoVN)
631 {
632 }
633 };
634
635 struct CompareCheckedBoundArithInfo
636 {
637 // (vnBound - 1) > vnOp
638 // (vnBound arrOper arrOp) cmpOper cmpOp
639 ValueNum vnBound;
640 unsigned arrOper;
641 ValueNum arrOp;
642 unsigned cmpOper;
643 ValueNum cmpOp;
644 CompareCheckedBoundArithInfo() : vnBound(NoVN), arrOper(GT_NONE), arrOp(NoVN), cmpOper(GT_NONE), cmpOp(NoVN)
645 {
646 }
647#ifdef DEBUG
648 void dump(ValueNumStore* vnStore)
649 {
650 vnStore->vnDump(vnStore->m_pComp, cmpOp);
651 printf(" ");
652 printf(vnStore->VNFuncName((VNFunc)cmpOper));
653 printf(" ");
654 vnStore->vnDump(vnStore->m_pComp, vnBound);
655 if (arrOper != GT_NONE)
656 {
657 printf(vnStore->VNFuncName((VNFunc)arrOper));
658 vnStore->vnDump(vnStore->m_pComp, arrOp);
659 }
660 }
661#endif
662 };
663
664 struct ConstantBoundInfo
665 {
666 // 100 > vnOp
667 int constVal;
668 unsigned cmpOper;
669 ValueNum cmpOpVN;
670
671 ConstantBoundInfo() : constVal(0), cmpOper(GT_NONE), cmpOpVN(NoVN)
672 {
673 }
674
675#ifdef DEBUG
676 void dump(ValueNumStore* vnStore)
677 {
678 vnStore->vnDump(vnStore->m_pComp, cmpOpVN);
679 printf(" ");
680 printf(vnStore->VNFuncName((VNFunc)cmpOper));
681 printf(" ");
682 printf("%d", constVal);
683 }
684#endif
685 };
686
687 // Check if "vn" is "new [] (type handle, size)"
688 bool IsVNNewArr(ValueNum vn, VNFuncApp* funcApp);
689
690 // Check if "vn" IsVNNewArr and return <= 0 if arr size cannot be determined, else array size.
691 int GetNewArrSize(ValueNum vn);
692
693 // Check if "vn" is "a.len"
694 bool IsVNArrLen(ValueNum vn);
695
696 // If "vn" is VN(a.len) then return VN(a); NoVN if VN(a) can't be determined.
697 ValueNum GetArrForLenVn(ValueNum vn);
698
699 // Return true with any Relop except for == and != and one operand has to be a 32-bit integer constant.
700 bool IsVNConstantBound(ValueNum vn);
701
702 // If "vn" is constant bound, then populate the "info" fields for constVal, cmpOp, cmpOper.
703 void GetConstantBoundInfo(ValueNum vn, ConstantBoundInfo* info);
704
705 // If "vn" is of the form "(uint)var < (uint)len" (or equivalent) return true.
706 bool IsVNUnsignedCompareCheckedBound(ValueNum vn, UnsignedCompareCheckedBoundInfo* info);
707
708 // If "vn" is of the form "var < len" or "len <= var" return true.
709 bool IsVNCompareCheckedBound(ValueNum vn);
710
711 // If "vn" is checked bound, then populate the "info" fields for the boundVn, cmpOp, cmpOper.
712 void GetCompareCheckedBound(ValueNum vn, CompareCheckedBoundArithInfo* info);
713
714 // If "vn" is of the form "len +/- var" return true.
715 bool IsVNCheckedBoundArith(ValueNum vn);
716
717 // If "vn" is checked bound arith, then populate the "info" fields for arrOper, arrVn, arrOp.
718 void GetCheckedBoundArithInfo(ValueNum vn, CompareCheckedBoundArithInfo* info);
719
720 // If "vn" is of the form "var < len +/- k" return true.
721 bool IsVNCompareCheckedBoundArith(ValueNum vn);
722
723 // If "vn" is checked bound arith, then populate the "info" fields for cmpOp, cmpOper.
724 void GetCompareCheckedBoundArithInfo(ValueNum vn, CompareCheckedBoundArithInfo* info);
725
726 // Returns the flags on the current handle. GTF_ICON_SCOPE_HDL for example.
727 unsigned GetHandleFlags(ValueNum vn);
728
729 // Returns true iff the VN represents a handle constant.
730 bool IsVNHandle(ValueNum vn);
731
732 // Convert a vartype_t to the value number's storage type for that vartype_t.
733 // For example, ValueNum of type TYP_LONG are stored in a map of INT64 variables.
734 // Lang is the language (C++) type for the corresponding vartype_t.
735 template <int N>
736 struct VarTypConv
737 {
738 };
739
740 // Return true if two value numbers would compare equal.
741 bool VNIsEqual(ValueNum vn1, ValueNum vn2)
742 {
743 return (vn1 == vn2) && (vn1 != NoVN) && !varTypeIsFloating(TypeOfVN(vn1));
744 }
745
746private:
747 struct Chunk;
748
749 template <typename T>
750 static T CoerceTypRefToT(Chunk* c, unsigned offset);
751
752 // Get the actual value and coerce the actual type c->m_typ to the wanted type T.
753 template <typename T>
754 FORCEINLINE T SafeGetConstantValue(Chunk* c, unsigned offset);
755
756 template <typename T>
757 T ConstantValueInternal(ValueNum vn DEBUGARG(bool coerce))
758 {
759 Chunk* c = m_chunks.GetNoExpand(GetChunkNum(vn));
760 assert(c->m_attribs == CEA_Const || c->m_attribs == CEA_Handle);
761
762 unsigned offset = ChunkOffset(vn);
763
764 switch (c->m_typ)
765 {
766 case TYP_REF:
767 assert(0 <= offset && offset <= 1); // Null or exception.
768 __fallthrough;
769
770 case TYP_BYREF:
771
772#ifdef _MSC_VER
773
774 assert(&typeid(T) == &typeid(size_t)); // We represent ref/byref constants as size_t's.
775
776#endif // _MSC_VER
777
778 __fallthrough;
779
780 case TYP_INT:
781 case TYP_LONG:
782 case TYP_FLOAT:
783 case TYP_DOUBLE:
784 if (c->m_attribs == CEA_Handle)
785 {
786 C_ASSERT(offsetof(VNHandle, m_cnsVal) == 0);
787 return (T) reinterpret_cast<VNHandle*>(c->m_defs)[offset].m_cnsVal;
788 }
789#ifdef DEBUG
790 if (!coerce)
791 {
792 T val1 = reinterpret_cast<T*>(c->m_defs)[offset];
793 T val2 = SafeGetConstantValue<T>(c, offset);
794
795 // Detect if there is a mismatch between the VN storage type and explicitly
796 // passed-in type T.
797 bool mismatch = false;
798 if (varTypeIsFloating(c->m_typ))
799 {
800 mismatch = (memcmp(&val1, &val2, sizeof(val1)) != 0);
801 }
802 else
803 {
804 mismatch = (val1 != val2);
805 }
806
807 if (mismatch)
808 {
809 assert(
810 !"Called ConstantValue<T>(vn), but type(T) != type(vn); Use CoercedConstantValue instead.");
811 }
812 }
813#endif
814 return SafeGetConstantValue<T>(c, offset);
815
816 default:
817 assert(false); // We do not record constants of this typ.
818 return (T)0;
819 }
820 }
821
822public:
823 // Requires that "vn" is a constant, and that its type is compatible with the explicitly passed
824 // type "T". Also, note that "T" has to have an accurate storage size of the TypeOfVN(vn).
825 template <typename T>
826 T ConstantValue(ValueNum vn)
827 {
828 return ConstantValueInternal<T>(vn DEBUGARG(false));
829 }
830
831 // Requires that "vn" is a constant, and that its type can be coerced to the explicitly passed
832 // type "T".
833 template <typename T>
834 T CoercedConstantValue(ValueNum vn)
835 {
836 return ConstantValueInternal<T>(vn DEBUGARG(true));
837 }
838
839 // Requires "mthFunc" to be an intrinsic math function (one of the allowable values for the "gtMath" field
840 // of a GenTreeMath node). For unary ops, return the value number for the application of this function to
841 // "arg0VN". For binary ops, return the value number for the application of this function to "arg0VN" and
842 // "arg1VN".
843
844 ValueNum EvalMathFuncUnary(var_types typ, CorInfoIntrinsics mthFunc, ValueNum arg0VN);
845
846 ValueNum EvalMathFuncBinary(var_types typ, CorInfoIntrinsics mthFunc, ValueNum arg0VN, ValueNum arg1VN);
847
848 ValueNumPair EvalMathFuncUnary(var_types typ, CorInfoIntrinsics mthFunc, ValueNumPair arg0VNP)
849 {
850 return ValueNumPair(EvalMathFuncUnary(typ, mthFunc, arg0VNP.GetLiberal()),
851 EvalMathFuncUnary(typ, mthFunc, arg0VNP.GetConservative()));
852 }
853
854 ValueNumPair EvalMathFuncBinary(var_types typ,
855 CorInfoIntrinsics mthFunc,
856 ValueNumPair arg0VNP,
857 ValueNumPair arg1VNP)
858 {
859 return ValueNumPair(EvalMathFuncBinary(typ, mthFunc, arg0VNP.GetLiberal(), arg1VNP.GetLiberal()),
860 EvalMathFuncBinary(typ, mthFunc, arg0VNP.GetConservative(), arg1VNP.GetConservative()));
861 }
862
863 // Returns "true" iff "vn" represents a function application.
864 bool IsVNFunc(ValueNum vn);
865
866 // If "vn" represents a function application, returns "true" and set "*funcApp" to
867 // the function application it represents; otherwise, return "false."
868 bool GetVNFunc(ValueNum vn, VNFuncApp* funcApp);
869
870 // Requires that "vn" represents a "GC heap address" the sum of a "TYP_REF" value and some integer
871 // value. Returns the TYP_REF value.
872 ValueNum VNForRefInAddr(ValueNum vn);
873
874 // Returns "true" iff "vn" is a valid value number -- one that has been previously returned.
875 bool VNIsValid(ValueNum vn);
876
877#ifdef DEBUG
878// This controls whether we recursively call vnDump on function arguments.
879#define FEATURE_VN_DUMP_FUNC_ARGS 0
880
881 // Prints, to standard out, a representation of "vn".
882 void vnDump(Compiler* comp, ValueNum vn, bool isPtr = false);
883
884 // Requires "fieldSeq" to be a field sequence VNFuncApp.
885 // Prints a representation (comma-separated list of field names) on standard out.
886 void vnDumpFieldSeq(Compiler* comp, VNFuncApp* fieldSeq, bool isHead);
887
888 // Requires "mapSelect" to be a map select VNFuncApp.
889 // Prints a representation of a MapSelect operation on standard out.
890 void vnDumpMapSelect(Compiler* comp, VNFuncApp* mapSelect);
891
892 // Requires "mapStore" to be a map store VNFuncApp.
893 // Prints a representation of a MapStore operation on standard out.
894 void vnDumpMapStore(Compiler* comp, VNFuncApp* mapStore);
895
896 // Requires "valWithExc" to be a value with an exeception set VNFuncApp.
897 // Prints a representation of the exeception set on standard out.
898 void vnDumpValWithExc(Compiler* comp, VNFuncApp* valWithExc);
899
900 // Requires "excSeq" to be a ExcSetCons sequence.
901 // Prints a representation of the set of exceptions on standard out.
902 void vnDumpExcSeq(Compiler* comp, VNFuncApp* excSeq, bool isHead);
903
904 // Returns the string name of "vnf".
905 static const char* VNFuncName(VNFunc vnf);
906 // Used in the implementation of the above.
907 static const char* VNFuncNameArr[];
908
909 // Returns the string name of "vn" when it is a reserved value number, nullptr otherwise
910 static const char* reservedName(ValueNum vn);
911
912#endif // DEBUG
913
914 // Returns true if "vn" is a reserved value number
915 static bool isReservedVN(ValueNum);
916
917private:
918 // We will allocate value numbers in "chunks". Each chunk will have the same type and "constness".
919 static const unsigned LogChunkSize = 6;
920 static const unsigned ChunkSize = 1 << LogChunkSize;
921 static const unsigned ChunkOffsetMask = ChunkSize - 1;
922
923 // A "ChunkNum" is a zero-based index naming a chunk in the Store, or else the special "NoChunk" value.
924 typedef UINT32 ChunkNum;
925 static const ChunkNum NoChunk = UINT32_MAX;
926
927 // Returns the ChunkNum of the Chunk that holds "vn" (which is required to be a valid
928 // value number, i.e., one returned by some VN-producing method of this class).
929 static ChunkNum GetChunkNum(ValueNum vn)
930 {
931 return vn >> LogChunkSize;
932 }
933
934 // Returns the offset of the given "vn" within its chunk.
935 static unsigned ChunkOffset(ValueNum vn)
936 {
937 return vn & ChunkOffsetMask;
938 }
939
940 // The base VN of the next chunk to be allocated. Should always be a multiple of ChunkSize.
941 ValueNum m_nextChunkBase;
942
943 enum ChunkExtraAttribs : BYTE
944 {
945 CEA_None, // No extra attributes.
946 CEA_Const, // This chunk contains constant values.
947 CEA_Handle, // This chunk contains handle constants.
948 CEA_NotAField, // This chunk contains "not a field" values.
949 CEA_Func0, // Represents functions of arity 0.
950 CEA_Func1, // ...arity 1.
951 CEA_Func2, // ...arity 2.
952 CEA_Func3, // ...arity 3.
953 CEA_Func4, // ...arity 4.
954 CEA_Count
955 };
956
957 // A "Chunk" holds "ChunkSize" value numbers, starting at "m_baseVN". All of these share the same
958 // "m_typ" and "m_attribs". These properties determine the interpretation of "m_defs", as discussed below.
959 struct Chunk
960 {
961 // If "m_defs" is non-null, it is an array of size ChunkSize, whose element type is determined by the other
962 // members. The "m_numUsed" field indicates the number of elements of "m_defs" that are already consumed (the
963 // next one to allocate).
964 void* m_defs;
965 unsigned m_numUsed;
966
967 // The value number of the first VN in the chunk.
968 ValueNum m_baseVN;
969
970 // The common attributes of this chunk.
971 var_types m_typ;
972 ChunkExtraAttribs m_attribs;
973 BasicBlock::loopNumber m_loopNum;
974
975 // Initialize a chunk, starting at "*baseVN", for the given "typ", "attribs", and "loopNum" (using "alloc" for
976 // allocations).
977 // (Increments "*baseVN" by ChunkSize.)
978 Chunk(CompAllocator alloc,
979 ValueNum* baseVN,
980 var_types typ,
981 ChunkExtraAttribs attribs,
982 BasicBlock::loopNumber loopNum);
983
984 // Requires that "m_numUsed < ChunkSize." Returns the offset of the allocated VN within the chunk; the
985 // actual VN is this added to the "m_baseVN" of the chunk.
986 unsigned AllocVN()
987 {
988 assert(m_numUsed < ChunkSize);
989 return m_numUsed++;
990 }
991
992 template <int N>
993 struct Alloc
994 {
995 typedef typename ValueNumStore::VarTypConv<N>::Type Type;
996 };
997 };
998
999 struct VNHandle : public JitKeyFuncsDefEquals<VNHandle>
1000 {
1001 ssize_t m_cnsVal;
1002 unsigned m_flags;
1003 // Don't use a constructor to use the default copy constructor for hashtable rehash.
1004 static void Initialize(VNHandle* handle, ssize_t m_cnsVal, unsigned m_flags)
1005 {
1006 handle->m_cnsVal = m_cnsVal;
1007 handle->m_flags = m_flags;
1008 }
1009 bool operator==(const VNHandle& y) const
1010 {
1011 return m_cnsVal == y.m_cnsVal && m_flags == y.m_flags;
1012 }
1013 static unsigned GetHashCode(const VNHandle& val)
1014 {
1015 return static_cast<unsigned>(val.m_cnsVal);
1016 }
1017 };
1018
1019 struct VNDefFunc0Arg
1020 {
1021 VNFunc m_func;
1022 VNDefFunc0Arg(VNFunc func) : m_func(func)
1023 {
1024 }
1025
1026 VNDefFunc0Arg() : m_func(VNF_COUNT)
1027 {
1028 }
1029
1030 bool operator==(const VNDefFunc0Arg& y) const
1031 {
1032 return m_func == y.m_func;
1033 }
1034 };
1035
1036 struct VNDefFunc1Arg : public VNDefFunc0Arg
1037 {
1038 ValueNum m_arg0;
1039 VNDefFunc1Arg(VNFunc func, ValueNum arg0) : VNDefFunc0Arg(func), m_arg0(arg0)
1040 {
1041 }
1042
1043 VNDefFunc1Arg() : VNDefFunc0Arg(), m_arg0(ValueNumStore::NoVN)
1044 {
1045 }
1046
1047 bool operator==(const VNDefFunc1Arg& y) const
1048 {
1049 return VNDefFunc0Arg::operator==(y) && m_arg0 == y.m_arg0;
1050 }
1051 };
1052
1053 struct VNDefFunc2Arg : public VNDefFunc1Arg
1054 {
1055 ValueNum m_arg1;
1056 VNDefFunc2Arg(VNFunc func, ValueNum arg0, ValueNum arg1) : VNDefFunc1Arg(func, arg0), m_arg1(arg1)
1057 {
1058 }
1059
1060 VNDefFunc2Arg() : m_arg1(ValueNumStore::NoVN)
1061 {
1062 }
1063
1064 bool operator==(const VNDefFunc2Arg& y) const
1065 {
1066 return VNDefFunc1Arg::operator==(y) && m_arg1 == y.m_arg1;
1067 }
1068 };
1069
1070 struct VNDefFunc3Arg : public VNDefFunc2Arg
1071 {
1072 ValueNum m_arg2;
1073 VNDefFunc3Arg(VNFunc func, ValueNum arg0, ValueNum arg1, ValueNum arg2)
1074 : VNDefFunc2Arg(func, arg0, arg1), m_arg2(arg2)
1075 {
1076 }
1077 VNDefFunc3Arg() : m_arg2(ValueNumStore::NoVN)
1078 {
1079 }
1080
1081 bool operator==(const VNDefFunc3Arg& y) const
1082 {
1083 return VNDefFunc2Arg::operator==(y) && m_arg2 == y.m_arg2;
1084 }
1085 };
1086
1087 struct VNDefFunc4Arg : public VNDefFunc3Arg
1088 {
1089 ValueNum m_arg3;
1090 VNDefFunc4Arg(VNFunc func, ValueNum arg0, ValueNum arg1, ValueNum arg2, ValueNum arg3)
1091 : VNDefFunc3Arg(func, arg0, arg1, arg2), m_arg3(arg3)
1092 {
1093 }
1094 VNDefFunc4Arg() : m_arg3(ValueNumStore::NoVN)
1095 {
1096 }
1097
1098 bool operator==(const VNDefFunc4Arg& y) const
1099 {
1100 return VNDefFunc3Arg::operator==(y) && m_arg3 == y.m_arg3;
1101 }
1102 };
1103
1104 // When we evaluate "select(m, i)", if "m" is a the value of a phi definition, we look at
1105 // all the values of the phi args, and see if doing the "select" on each of them yields identical
1106 // results. If so, that is the result of the entire "select" form. We have to be careful, however,
1107 // because phis may be recursive in the presence of loop structures -- the VN for the phi may be (or be
1108 // part of the definition of) the VN's of some of the arguments. But there will be at least one
1109 // argument that does *not* depend on the outer phi VN -- after all, we had to get into the loop somehow.
1110 // So we have to be careful about breaking infinite recursion. We can ignore "recursive" results -- if all the
1111 // non-recursive results are the same, the recursion indicates that the loop structure didn't alter the result.
1112 // This stack represents the set of outer phis such that select(phi, ind) is being evaluated.
1113 JitExpandArrayStack<VNDefFunc2Arg> m_fixedPointMapSels;
1114
1115#ifdef DEBUG
1116 // Returns "true" iff "m_fixedPointMapSels" is non-empty, and it's top element is
1117 // "select(map, index)".
1118 bool FixedPointMapSelsTopHasValue(ValueNum map, ValueNum index);
1119#endif
1120
1121 // Returns true if "sel(map, ind)" is a member of "m_fixedPointMapSels".
1122 bool SelectIsBeingEvaluatedRecursively(ValueNum map, ValueNum ind);
1123
1124 // This is the set of value numbers that have been flagged as arguments to bounds checks, in the length position.
1125 CheckedBoundVNSet m_checkedBoundVNs;
1126
1127 // This is a map from "chunk number" to the attributes of the chunk.
1128 JitExpandArrayStack<Chunk*> m_chunks;
1129
1130 // These entries indicate the current allocation chunk, if any, for each valid combination of <var_types,
1131 // ChunkExtraAttribute, loopNumber>. Valid combinations require attribs==CEA_None or loopNum==MAX_LOOP_NUM.
1132 // If the value is NoChunk, it indicates that there is no current allocation chunk for that pair, otherwise
1133 // it is the index in "m_chunks" of a chunk with the given attributes, in which the next allocation should
1134 // be attempted.
1135 ChunkNum m_curAllocChunk[TYP_COUNT][CEA_Count + MAX_LOOP_NUM + 1];
1136
1137 // Returns a (pointer to a) chunk in which a new value number may be allocated.
1138 Chunk* GetAllocChunk(var_types typ, ChunkExtraAttribs attribs, BasicBlock::loopNumber loopNum = MAX_LOOP_NUM);
1139
1140 // First, we need mechanisms for mapping from constants to value numbers.
1141 // For small integers, we'll use an array.
1142 static const int SmallIntConstMin = -1;
1143 static const int SmallIntConstMax = 10;
1144 static const unsigned SmallIntConstNum = SmallIntConstMax - SmallIntConstMin + 1;
1145 static bool IsSmallIntConst(int i)
1146 {
1147 return SmallIntConstMin <= i && i <= SmallIntConstMax;
1148 }
1149 ValueNum m_VNsForSmallIntConsts[SmallIntConstNum];
1150
1151 struct ValueNumList
1152 {
1153 ValueNum vn;
1154 ValueNumList* next;
1155 ValueNumList(const ValueNum& v, ValueNumList* n = nullptr) : vn(v), next(n)
1156 {
1157 }
1158 };
1159
1160 // Keeps track of value numbers that are integer constants and also handles (GTG_ICON_HDL_MASK.)
1161 ValueNumList* m_intConHandles;
1162
1163 typedef VNMap<INT32> IntToValueNumMap;
1164 IntToValueNumMap* m_intCnsMap;
1165 IntToValueNumMap* GetIntCnsMap()
1166 {
1167 if (m_intCnsMap == nullptr)
1168 {
1169 m_intCnsMap = new (m_alloc) IntToValueNumMap(m_alloc);
1170 }
1171 return m_intCnsMap;
1172 }
1173
1174 ValueNum GetVNForIntCon(INT32 cnsVal)
1175 {
1176 ValueNum res;
1177 if (GetIntCnsMap()->Lookup(cnsVal, &res))
1178 {
1179 return res;
1180 }
1181 else
1182 {
1183 Chunk* c = GetAllocChunk(TYP_INT, CEA_Const);
1184 unsigned offsetWithinChunk = c->AllocVN();
1185 res = c->m_baseVN + offsetWithinChunk;
1186 reinterpret_cast<INT32*>(c->m_defs)[offsetWithinChunk] = cnsVal;
1187 GetIntCnsMap()->Set(cnsVal, res);
1188 return res;
1189 }
1190 }
1191
1192 typedef VNMap<INT64> LongToValueNumMap;
1193 LongToValueNumMap* m_longCnsMap;
1194 LongToValueNumMap* GetLongCnsMap()
1195 {
1196 if (m_longCnsMap == nullptr)
1197 {
1198 m_longCnsMap = new (m_alloc) LongToValueNumMap(m_alloc);
1199 }
1200 return m_longCnsMap;
1201 }
1202
1203 typedef VNMap<VNHandle, VNHandle> HandleToValueNumMap;
1204 HandleToValueNumMap* m_handleMap;
1205 HandleToValueNumMap* GetHandleMap()
1206 {
1207 if (m_handleMap == nullptr)
1208 {
1209 m_handleMap = new (m_alloc) HandleToValueNumMap(m_alloc);
1210 }
1211 return m_handleMap;
1212 }
1213
1214 struct LargePrimitiveKeyFuncsFloat : public JitLargePrimitiveKeyFuncs<float>
1215 {
1216 static bool Equals(float x, float y)
1217 {
1218 return *(unsigned*)&x == *(unsigned*)&y;
1219 }
1220 };
1221
1222 typedef VNMap<float, LargePrimitiveKeyFuncsFloat> FloatToValueNumMap;
1223 FloatToValueNumMap* m_floatCnsMap;
1224 FloatToValueNumMap* GetFloatCnsMap()
1225 {
1226 if (m_floatCnsMap == nullptr)
1227 {
1228 m_floatCnsMap = new (m_alloc) FloatToValueNumMap(m_alloc);
1229 }
1230 return m_floatCnsMap;
1231 }
1232
1233 // In the JIT we need to distinguish -0.0 and 0.0 for optimizations.
1234 struct LargePrimitiveKeyFuncsDouble : public JitLargePrimitiveKeyFuncs<double>
1235 {
1236 static bool Equals(double x, double y)
1237 {
1238 return *(__int64*)&x == *(__int64*)&y;
1239 }
1240 };
1241
1242 typedef VNMap<double, LargePrimitiveKeyFuncsDouble> DoubleToValueNumMap;
1243 DoubleToValueNumMap* m_doubleCnsMap;
1244 DoubleToValueNumMap* GetDoubleCnsMap()
1245 {
1246 if (m_doubleCnsMap == nullptr)
1247 {
1248 m_doubleCnsMap = new (m_alloc) DoubleToValueNumMap(m_alloc);
1249 }
1250 return m_doubleCnsMap;
1251 }
1252
1253 LongToValueNumMap* m_byrefCnsMap;
1254 LongToValueNumMap* GetByrefCnsMap()
1255 {
1256 if (m_byrefCnsMap == nullptr)
1257 {
1258 m_byrefCnsMap = new (m_alloc) LongToValueNumMap(m_alloc);
1259 }
1260 return m_byrefCnsMap;
1261 }
1262
1263 struct VNDefFunc0ArgKeyFuncs : public JitKeyFuncsDefEquals<VNDefFunc1Arg>
1264 {
1265 static unsigned GetHashCode(VNDefFunc1Arg val)
1266 {
1267 return (val.m_func << 24) + val.m_arg0;
1268 }
1269 };
1270 typedef VNMap<VNFunc> VNFunc0ToValueNumMap;
1271 VNFunc0ToValueNumMap* m_VNFunc0Map;
1272 VNFunc0ToValueNumMap* GetVNFunc0Map()
1273 {
1274 if (m_VNFunc0Map == nullptr)
1275 {
1276 m_VNFunc0Map = new (m_alloc) VNFunc0ToValueNumMap(m_alloc);
1277 }
1278 return m_VNFunc0Map;
1279 }
1280
1281 struct VNDefFunc1ArgKeyFuncs : public JitKeyFuncsDefEquals<VNDefFunc1Arg>
1282 {
1283 static unsigned GetHashCode(VNDefFunc1Arg val)
1284 {
1285 return (val.m_func << 24) + val.m_arg0;
1286 }
1287 };
1288 typedef VNMap<VNDefFunc1Arg, VNDefFunc1ArgKeyFuncs> VNFunc1ToValueNumMap;
1289 VNFunc1ToValueNumMap* m_VNFunc1Map;
1290 VNFunc1ToValueNumMap* GetVNFunc1Map()
1291 {
1292 if (m_VNFunc1Map == nullptr)
1293 {
1294 m_VNFunc1Map = new (m_alloc) VNFunc1ToValueNumMap(m_alloc);
1295 }
1296 return m_VNFunc1Map;
1297 }
1298
1299 struct VNDefFunc2ArgKeyFuncs : public JitKeyFuncsDefEquals<VNDefFunc2Arg>
1300 {
1301 static unsigned GetHashCode(VNDefFunc2Arg val)
1302 {
1303 return (val.m_func << 24) + (val.m_arg0 << 8) + val.m_arg1;
1304 }
1305 };
1306 typedef VNMap<VNDefFunc2Arg, VNDefFunc2ArgKeyFuncs> VNFunc2ToValueNumMap;
1307 VNFunc2ToValueNumMap* m_VNFunc2Map;
1308 VNFunc2ToValueNumMap* GetVNFunc2Map()
1309 {
1310 if (m_VNFunc2Map == nullptr)
1311 {
1312 m_VNFunc2Map = new (m_alloc) VNFunc2ToValueNumMap(m_alloc);
1313 }
1314 return m_VNFunc2Map;
1315 }
1316
1317 struct VNDefFunc3ArgKeyFuncs : public JitKeyFuncsDefEquals<VNDefFunc3Arg>
1318 {
1319 static unsigned GetHashCode(VNDefFunc3Arg val)
1320 {
1321 return (val.m_func << 24) + (val.m_arg0 << 16) + (val.m_arg1 << 8) + val.m_arg2;
1322 }
1323 };
1324 typedef VNMap<VNDefFunc3Arg, VNDefFunc3ArgKeyFuncs> VNFunc3ToValueNumMap;
1325 VNFunc3ToValueNumMap* m_VNFunc3Map;
1326 VNFunc3ToValueNumMap* GetVNFunc3Map()
1327 {
1328 if (m_VNFunc3Map == nullptr)
1329 {
1330 m_VNFunc3Map = new (m_alloc) VNFunc3ToValueNumMap(m_alloc);
1331 }
1332 return m_VNFunc3Map;
1333 }
1334
1335 struct VNDefFunc4ArgKeyFuncs : public JitKeyFuncsDefEquals<VNDefFunc4Arg>
1336 {
1337 static unsigned GetHashCode(VNDefFunc4Arg val)
1338 {
1339 return (val.m_func << 24) + (val.m_arg0 << 16) + (val.m_arg1 << 8) + val.m_arg2 + (val.m_arg3 << 12);
1340 }
1341 };
1342 typedef VNMap<VNDefFunc4Arg, VNDefFunc4ArgKeyFuncs> VNFunc4ToValueNumMap;
1343 VNFunc4ToValueNumMap* m_VNFunc4Map;
1344 VNFunc4ToValueNumMap* GetVNFunc4Map()
1345 {
1346 if (m_VNFunc4Map == nullptr)
1347 {
1348 m_VNFunc4Map = new (m_alloc) VNFunc4ToValueNumMap(m_alloc);
1349 }
1350 return m_VNFunc4Map;
1351 }
1352
1353 enum SpecialRefConsts
1354 {
1355 SRC_Null,
1356 SRC_ZeroMap,
1357 SRC_ReadOnlyHeap,
1358 SRC_Void,
1359 SRC_EmptyExcSet,
1360
1361 SRC_NumSpecialRefConsts
1362 };
1363
1364 // The "values" of special ref consts will be all be "null" -- their differing meanings will
1365 // be carried by the distinct value numbers.
1366 static class Object* s_specialRefConsts[SRC_NumSpecialRefConsts];
1367 static class Object* s_nullConst;
1368
1369#ifdef DEBUG
1370 // This helps test some performance pathologies related to "evaluation" of VNF_MapSelect terms,
1371 // especially relating to GcHeap/ByrefExposed. We count the number of applications of such terms we consider,
1372 // and if this exceeds a limit, indicated by a COMPlus_ variable, we assert.
1373 unsigned m_numMapSels;
1374#endif
1375};
1376
1377template <>
1378struct ValueNumStore::VarTypConv<TYP_INT>
1379{
1380 typedef INT32 Type;
1381 typedef int Lang;
1382};
1383template <>
1384struct ValueNumStore::VarTypConv<TYP_FLOAT>
1385{
1386 typedef INT32 Type;
1387 typedef float Lang;
1388};
1389template <>
1390struct ValueNumStore::VarTypConv<TYP_LONG>
1391{
1392 typedef INT64 Type;
1393 typedef INT64 Lang;
1394};
1395template <>
1396struct ValueNumStore::VarTypConv<TYP_DOUBLE>
1397{
1398 typedef INT64 Type;
1399 typedef double Lang;
1400};
1401template <>
1402struct ValueNumStore::VarTypConv<TYP_BYREF>
1403{
1404 typedef INT64 Type;
1405 typedef void* Lang;
1406};
1407template <>
1408struct ValueNumStore::VarTypConv<TYP_REF>
1409{
1410 typedef class Object* Type;
1411 typedef class Object* Lang;
1412};
1413
1414// Get the actual value and coerce the actual type c->m_typ to the wanted type T.
1415template <typename T>
1416FORCEINLINE T ValueNumStore::SafeGetConstantValue(Chunk* c, unsigned offset)
1417{
1418 switch (c->m_typ)
1419 {
1420 case TYP_REF:
1421 return CoerceTypRefToT<T>(c, offset);
1422 case TYP_BYREF:
1423 return static_cast<T>(reinterpret_cast<VarTypConv<TYP_BYREF>::Type*>(c->m_defs)[offset]);
1424 case TYP_INT:
1425 return static_cast<T>(reinterpret_cast<VarTypConv<TYP_INT>::Type*>(c->m_defs)[offset]);
1426 case TYP_LONG:
1427 return static_cast<T>(reinterpret_cast<VarTypConv<TYP_LONG>::Type*>(c->m_defs)[offset]);
1428 case TYP_FLOAT:
1429 return static_cast<T>(reinterpret_cast<VarTypConv<TYP_FLOAT>::Lang*>(c->m_defs)[offset]);
1430 case TYP_DOUBLE:
1431 return static_cast<T>(reinterpret_cast<VarTypConv<TYP_DOUBLE>::Lang*>(c->m_defs)[offset]);
1432 default:
1433 assert(false);
1434 return (T)0;
1435 }
1436}
1437
1438// Inline functions.
1439
1440// static
1441inline bool ValueNumStore::GenTreeOpIsLegalVNFunc(genTreeOps gtOper)
1442{
1443 return (s_vnfOpAttribs[gtOper] & VNFOA_IllegalGenTreeOp) == 0;
1444}
1445
1446// static
1447inline bool ValueNumStore::VNFuncIsCommutative(VNFunc vnf)
1448{
1449 return (s_vnfOpAttribs[vnf] & VNFOA_Commutative) != 0;
1450}
1451
1452inline bool ValueNumStore::VNFuncIsComparison(VNFunc vnf)
1453{
1454 if (vnf >= VNF_Boundary)
1455 {
1456 // For integer types we have unsigned comparisions, and
1457 // for floating point types these are the unordered variants.
1458 //
1459 return ((vnf == VNF_LT_UN) || (vnf == VNF_LE_UN) || (vnf == VNF_GE_UN) || (vnf == VNF_GT_UN));
1460 }
1461 genTreeOps gtOp = genTreeOps(vnf);
1462 return GenTree::OperIsCompare(gtOp) != 0;
1463}
1464
1465template <>
1466inline size_t ValueNumStore::CoerceTypRefToT(Chunk* c, unsigned offset)
1467{
1468 return reinterpret_cast<size_t>(reinterpret_cast<VarTypConv<TYP_REF>::Type*>(c->m_defs)[offset]);
1469}
1470
1471template <typename T>
1472inline T ValueNumStore::CoerceTypRefToT(Chunk* c, unsigned offset)
1473{
1474 noway_assert(sizeof(T) >= sizeof(VarTypConv<TYP_REF>::Type));
1475 unreached();
1476}
1477
1478/*****************************************************************************/
1479#endif // _VALUENUM_H_
1480/*****************************************************************************/
1481