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//
6//
7// We take the following approach to range check analysis:
8//
9// Consider the following loop:
10// for (int i = 0; i < a.len; ++i) {
11// a[i] = 0;
12// }
13//
14// This would be represented as:
15// i_0 = 0; BB0
16// / ______ a[i_1] = 0; BB2
17// / / i_2 = i_1 + 1;
18// / / ^
19// i_1 = phi(i_0, i_2); BB1 |
20// i_1 < a.len -------------------+
21//
22// BB0 -> BB1
23// BB1 -> (i_1 < a.len) ? BB2 : BB3
24// BB2 -> BB1
25// BB3 -> return
26//
27// **Step 1. Walk the statements in the method checking if there is a bounds check.
28// If there is a bounds check, ask the range of the index variable.
29// In the above example i_1's range.
30//
31// **Step 2. Follow the defs and the dependency chain:
32// i_1 is a local, so go to its definition which is i_1 = phi(i_0, i_2).
33//
34// Since rhs is a phi, we ask the range for i_0 and i_2 in the hopes of merging
35// the resulting ranges for i_1.
36//
37// The range of i_0 follows immediately when going to its definition.
38// Ask for the range of i_2, which leads to i_1 + 1.
39// Ask for the range of i_1 and figure we are looping. Call the range of i_1 as
40// "dependent" and quit looping further. The range of "1" is just <1, 1>.
41//
42// Now we have exhausted all the variables for which the range can be determined.
43// The others are either "unknown" or "dependent."
44//
45// We also merge assertions from its pred block's edges for a phi argument otherwise
46// from the block's assertionIn. This gives us an upper bound for i_1 as a.len.
47//
48// **Step 3. Check if an overflow occurs in the dependency chain (loop.)
49// In the above case, we want to make sure there is no overflow in the definitions
50// involving i_1 and i_2. Merge assertions from the block's edges whenever possible.
51//
52// **Step 4. Check if the dependency chain is monotonic.
53//
54// **Step 5. If monotonic is true, then perform a widening step, where we assume, the
55// SSA variables that are "dependent" get their values from the definitions in the
56// dependency loop and their initial values must be the definitions that are not in
57// the dependency loop, in this case i_0's value which is 0.
58//
59
60#pragma once
61#include "compiler.h"
62
63static bool IntAddOverflows(int max1, int max2)
64{
65 if (max1 > 0 && max2 > 0 && INT_MAX - max1 < max2)
66 {
67 return true;
68 }
69 if (max1 < 0 && max2 < 0 && max1 < INT_MIN - max2)
70 {
71 return true;
72 }
73 return false;
74}
75
76struct Limit
77{
78 enum LimitType
79 {
80 keUndef, // The limit is yet to be computed.
81 keBinOpArray,
82 keConstant,
83 keDependent, // The limit is dependent on some other value.
84 keUnknown, // The limit could not be determined.
85 };
86
87 Limit() : type(keUndef)
88 {
89 }
90
91 Limit(LimitType type) : type(type)
92 {
93 }
94
95 Limit(LimitType type, int cns) : cns(cns), vn(ValueNumStore::NoVN), type(type)
96 {
97 assert(type == keConstant);
98 }
99
100 Limit(LimitType type, ValueNum vn, int cns) : cns(cns), vn(vn), type(type)
101 {
102 assert(type == keBinOpArray);
103 }
104
105 bool IsUndef()
106 {
107 return type == keUndef;
108 }
109 bool IsDependent()
110 {
111 return type == keDependent;
112 }
113 bool IsUnknown()
114 {
115 return type == keUnknown;
116 }
117 bool IsConstant()
118 {
119 return type == keConstant;
120 }
121 int GetConstant()
122 {
123 return cns;
124 }
125 bool IsBinOpArray()
126 {
127 return type == keBinOpArray;
128 }
129 bool AddConstant(int i)
130 {
131 switch (type)
132 {
133 case keDependent:
134 return true;
135 case keBinOpArray:
136 if (IntAddOverflows(cns, i))
137 {
138 return false;
139 }
140 cns += i;
141 return true;
142
143 case keConstant:
144 if (IntAddOverflows(cns, i))
145 {
146 return false;
147 }
148 cns += i;
149 return true;
150
151 case keUndef:
152 case keUnknown:
153 // For these values of 'type', conservatively return false
154 break;
155 }
156
157 return false;
158 }
159
160 bool Equals(Limit& l)
161 {
162 switch (type)
163 {
164 case keUndef:
165 case keUnknown:
166 case keDependent:
167 return l.type == type;
168
169 case keBinOpArray:
170 return l.type == type && l.vn == vn && l.cns == cns;
171
172 case keConstant:
173 return l.type == type && l.cns == cns;
174 }
175 return false;
176 }
177#ifdef DEBUG
178 const char* ToString(CompAllocator alloc)
179 {
180 unsigned size = 64;
181 char* buf = alloc.allocate<char>(size);
182 switch (type)
183 {
184 case keUndef:
185 return "Undef";
186
187 case keUnknown:
188 return "Unknown";
189
190 case keDependent:
191 return "Dependent";
192
193 case keBinOpArray:
194 sprintf_s(buf, size, FMT_VN " + %d", vn, cns);
195 return buf;
196
197 case keConstant:
198 sprintf_s(buf, size, "%d", cns);
199 return buf;
200 }
201 unreached();
202 }
203#endif
204 int cns;
205 ValueNum vn;
206 LimitType type;
207};
208
209// Range struct contains upper and lower limit.
210struct Range
211{
212 Limit uLimit;
213 Limit lLimit;
214
215 Range(const Limit& limit) : uLimit(limit), lLimit(limit)
216 {
217 }
218
219 Range(const Limit& lLimit, const Limit& uLimit) : uLimit(uLimit), lLimit(lLimit)
220 {
221 }
222
223 Limit& UpperLimit()
224 {
225 return uLimit;
226 }
227
228 Limit& LowerLimit()
229 {
230 return lLimit;
231 }
232
233#ifdef DEBUG
234 char* ToString(CompAllocator alloc)
235 {
236 size_t size = 64;
237 char* buf = alloc.allocate<char>(size);
238 sprintf_s(buf, size, "<%s, %s>", lLimit.ToString(alloc), uLimit.ToString(alloc));
239 return buf;
240 }
241#endif
242};
243
244// Helpers for operations performed on ranges
245struct RangeOps
246{
247 // Given a constant limit in "l1", add it to l2 and mutate "l2".
248 static Limit AddConstantLimit(Limit& l1, Limit& l2)
249 {
250 assert(l1.IsConstant());
251 Limit l = l2;
252 if (l.AddConstant(l1.GetConstant()))
253 {
254 return l;
255 }
256 else
257 {
258 return Limit(Limit::keUnknown);
259 }
260 }
261
262 // Given two ranges "r1" and "r2", perform an add operation on the
263 // ranges.
264 static Range Add(Range& r1, Range& r2)
265 {
266 Limit& r1lo = r1.LowerLimit();
267 Limit& r1hi = r1.UpperLimit();
268 Limit& r2lo = r2.LowerLimit();
269 Limit& r2hi = r2.UpperLimit();
270
271 Range result = Limit(Limit::keUnknown);
272
273 // Check lo ranges if they are dependent and not unknown.
274 if ((r1lo.IsDependent() && !r1lo.IsUnknown()) || (r2lo.IsDependent() && !r2lo.IsUnknown()))
275 {
276 result.lLimit = Limit(Limit::keDependent);
277 }
278 // Check hi ranges if they are dependent and not unknown.
279 if ((r1hi.IsDependent() && !r1hi.IsUnknown()) || (r2hi.IsDependent() && !r2hi.IsUnknown()))
280 {
281 result.uLimit = Limit(Limit::keDependent);
282 }
283
284 if (r1lo.IsConstant())
285 {
286 result.lLimit = AddConstantLimit(r1lo, r2lo);
287 }
288 if (r2lo.IsConstant())
289 {
290 result.lLimit = AddConstantLimit(r2lo, r1lo);
291 }
292 if (r1hi.IsConstant())
293 {
294 result.uLimit = AddConstantLimit(r1hi, r2hi);
295 }
296 if (r2hi.IsConstant())
297 {
298 result.uLimit = AddConstantLimit(r2hi, r1hi);
299 }
300 return result;
301 }
302
303 // Given two ranges "r1" and "r2", do a Phi merge. If "monotonic" is true,
304 // then ignore the dependent variables.
305 static Range Merge(Range& r1, Range& r2, bool monotonic)
306 {
307 Limit& r1lo = r1.LowerLimit();
308 Limit& r1hi = r1.UpperLimit();
309 Limit& r2lo = r2.LowerLimit();
310 Limit& r2hi = r2.UpperLimit();
311
312 // Take care of lo part.
313 Range result = Limit(Limit::keUnknown);
314 if (r1lo.IsUnknown() || r2lo.IsUnknown())
315 {
316 result.lLimit = Limit(Limit::keUnknown);
317 }
318 // Uninitialized, just copy.
319 else if (r1lo.IsUndef())
320 {
321 result.lLimit = r2lo;
322 }
323 else if (r1lo.IsDependent() || r2lo.IsDependent())
324 {
325 if (monotonic)
326 {
327 result.lLimit = r1lo.IsDependent() ? r2lo : r1lo;
328 }
329 else
330 {
331 result.lLimit = Limit(Limit::keDependent);
332 }
333 }
334
335 // Take care of hi part.
336 if (r1hi.IsUnknown() || r2hi.IsUnknown())
337 {
338 result.uLimit = Limit(Limit::keUnknown);
339 }
340 else if (r1hi.IsUndef())
341 {
342 result.uLimit = r2hi;
343 }
344 else if (r1hi.IsDependent() || r2hi.IsDependent())
345 {
346 if (monotonic)
347 {
348 result.uLimit = r1hi.IsDependent() ? r2hi : r1hi;
349 }
350 else
351 {
352 result.uLimit = Limit(Limit::keDependent);
353 }
354 }
355
356 if (r1lo.IsConstant() && r2lo.IsConstant())
357 {
358 result.lLimit = Limit(Limit::keConstant, min(r1lo.GetConstant(), r2lo.GetConstant()));
359 }
360 if (r1hi.IsConstant() && r2hi.IsConstant())
361 {
362 result.uLimit = Limit(Limit::keConstant, max(r1hi.GetConstant(), r2hi.GetConstant()));
363 }
364 if (r2hi.Equals(r1hi))
365 {
366 result.uLimit = r2hi;
367 }
368 if (r2lo.Equals(r1lo))
369 {
370 result.lLimit = r1lo;
371 }
372 // Widen Upper Limit => Max(k, (a.len + n)) yields (a.len + n),
373 // This is correct if k >= 0 and n >= k, since a.len always >= 0
374 // (a.len + n) could overflow, but the result (a.len + n) also
375 // preserves the overflow.
376 if (r1hi.IsConstant() && r1hi.GetConstant() >= 0 && r2hi.IsBinOpArray() &&
377 r2hi.GetConstant() >= r1hi.GetConstant())
378 {
379 result.uLimit = r2hi;
380 }
381 if (r2hi.IsConstant() && r2hi.GetConstant() >= 0 && r1hi.IsBinOpArray() &&
382 r1hi.GetConstant() >= r2hi.GetConstant())
383 {
384 result.uLimit = r1hi;
385 }
386 if (r1hi.IsBinOpArray() && r2hi.IsBinOpArray() && r1hi.vn == r2hi.vn)
387 {
388 result.uLimit = r1hi;
389 // Widen the upper bound if the other constant is greater.
390 if (r2hi.GetConstant() > r1hi.GetConstant())
391 {
392 result.uLimit = r2hi;
393 }
394 }
395 return result;
396 }
397};
398
399class RangeCheck
400{
401public:
402 // Constructor
403 RangeCheck(Compiler* pCompiler);
404
405 typedef JitHashTable<GenTree*, JitPtrKeyFuncs<GenTree>, bool> OverflowMap;
406 typedef JitHashTable<GenTree*, JitPtrKeyFuncs<GenTree>, Range*> RangeMap;
407 typedef JitHashTable<GenTree*, JitPtrKeyFuncs<GenTree>, BasicBlock*> SearchPath;
408
409#ifdef DEBUG
410 // TODO-Cleanup: This code has been kept around just to ensure that the SSA data is still
411 // valid when RangeCheck runs. It should be removed at some point (and perhaps replaced
412 // by a proper SSA validity checker).
413
414 // Location information is used to map where the defs occur in the method.
415 struct Location
416 {
417 BasicBlock* block;
418 GenTree* stmt;
419 GenTreeLclVarCommon* tree;
420 GenTree* parent;
421 Location(BasicBlock* block, GenTree* stmt, GenTreeLclVarCommon* tree, GenTree* parent)
422 : block(block), stmt(stmt), tree(tree), parent(parent)
423 {
424 }
425
426 private:
427 Location();
428 };
429
430 typedef JitHashTable<INT64, JitLargePrimitiveKeyFuncs<INT64>, Location*> VarToLocMap;
431
432 // Generate a hashcode unique for this ssa var.
433 UINT64 HashCode(unsigned lclNum, unsigned ssaNum);
434
435 // Add a location of the definition of ssa var to the location map.
436 // Requires "hash" to be computed using HashCode.
437 // Requires "location" to be the local definition.
438 void SetDef(UINT64 hash, Location* loc);
439
440 // Given a tree node that is a local, return the Location defining the local.
441 Location* GetDef(GenTreeLclVarCommon* lcl);
442 Location* GetDef(unsigned lclNum, unsigned ssaNum);
443
444 // Given a statement, check if it is a def and add its locations in a map.
445 void MapStmtDefs(const Location& loc);
446
447 // Given the CFG, check if it has defs and add their locations in a map.
448 void MapMethodDefs();
449#endif
450
451 int GetArrLength(ValueNum vn);
452
453 // Check whether the computed range is within lower and upper bounds. This function
454 // assumes that the lower range is resolved and upper range is symbolic as in an
455 // increasing loop.
456 // TODO-CQ: This is not general enough.
457 bool BetweenBounds(Range& range, int lower, GenTree* upper);
458
459 // Entry point to optimize range checks in the block. Assumes value numbering
460 // and assertion prop phases are completed.
461 void OptimizeRangeChecks();
462
463 // Given a "tree" node, check if it contains array bounds check node and
464 // optimize to remove it, if possible. Requires "stmt" and "block" that
465 // contain the tree.
466 void OptimizeRangeCheck(BasicBlock* block, GenTree* stmt, GenTree* tree);
467
468 // Given the index expression try to find its range.
469 // The range of a variable depends on its rhs which in turn depends on its constituent variables.
470 // The "path" is the path taken in the search for the rhs' range and its constituents' range.
471 // If "monotonic" is true, the calculations are made more liberally assuming initial values
472 // at phi definitions.
473 Range GetRange(BasicBlock* block, GenTree* expr, bool monotonic DEBUGARG(int indent));
474
475 // Given the local variable, first find the definition of the local and find the range of the rhs.
476 // Helper for GetRange.
477 Range ComputeRangeForLocalDef(BasicBlock* block, GenTreeLclVarCommon* lcl, bool monotonic DEBUGARG(int indent));
478
479 // Compute the range, rather than retrieve a cached value. Helper for GetRange.
480 Range ComputeRange(BasicBlock* block, GenTree* expr, bool monotonic DEBUGARG(int indent));
481
482 // Compute the range for the op1 and op2 for the given binary operator.
483 Range ComputeRangeForBinOp(BasicBlock* block, GenTreeOp* binop, bool monotonic DEBUGARG(int indent));
484
485 // Merge assertions from AssertionProp's flags, for the corresponding "phiArg."
486 // Requires "pRange" to contain range that is computed partially.
487 void MergeAssertion(BasicBlock* block, GenTree* phiArg, Range* pRange DEBUGARG(int indent));
488
489 // Inspect the "assertions" and extract assertions about the given "phiArg" and
490 // refine the "pRange" value.
491 void MergeEdgeAssertions(GenTreeLclVarCommon* lcl, ASSERT_VALARG_TP assertions, Range* pRange);
492
493 // The maximum possible value of the given "limit." If such a value could not be determined
494 // return "false." For example: ARRLEN_MAX for array length.
495 bool GetLimitMax(Limit& limit, int* pMax);
496
497 // Does the addition of the two limits overflow?
498 bool AddOverflows(Limit& limit1, Limit& limit2);
499
500 // Does the binary operation between the operands overflow? Check recursively.
501 bool DoesBinOpOverflow(BasicBlock* block, GenTreeOp* binop);
502
503 // Does the phi operands involve an assignment that could overflow?
504 bool DoesPhiOverflow(BasicBlock* block, GenTree* expr);
505
506 // Find the def of the "expr" local and recurse on the arguments if any of them involve a
507 // calculation that overflows.
508 bool DoesVarDefOverflow(GenTreeLclVarCommon* lcl);
509
510 bool ComputeDoesOverflow(BasicBlock* block, GenTree* expr);
511
512 // Does the current "expr" which is a use involve a definition, that overflows.
513 bool DoesOverflow(BasicBlock* block, GenTree* tree);
514
515 // Widen the range by first checking if the induction variable is monotonic. Requires "pRange"
516 // to be partially computed.
517 void Widen(BasicBlock* block, GenTree* tree, Range* pRange);
518
519 // Is the binary operation increasing the value.
520 bool IsBinOpMonotonicallyIncreasing(GenTreeOp* binop);
521
522 // Given an "expr" trace its rhs and their definitions to check if all the assignments
523 // are monotonically increasing.
524 //
525 bool IsMonotonicallyIncreasing(GenTree* tree, bool rejectNegativeConst);
526
527 // We allocate a budget to avoid walking long UD chains. When traversing each link in the UD
528 // chain, we decrement the budget. When the budget hits 0, then no more range check optimization
529 // will be applied for the currently compiled method.
530 bool IsOverBudget();
531
532private:
533 // Given a lclvar use, try to find the lclvar's defining assignment and its containing block.
534 GenTreeOp* GetSsaDefAsg(GenTreeLclVarCommon* lclUse, BasicBlock** asgBlock);
535
536 GenTreeBoundsChk* m_pCurBndsChk;
537
538 // Get the cached overflow values.
539 OverflowMap* GetOverflowMap();
540 OverflowMap* m_pOverflowMap;
541
542 // Get the cached range values.
543 RangeMap* GetRangeMap();
544 RangeMap* m_pRangeMap;
545
546 SearchPath* m_pSearchPath;
547
548#ifdef DEBUG
549 bool m_fMappedDefs;
550 VarToLocMap* m_pDefTable;
551#endif
552
553 Compiler* m_pCompiler;
554 CompAllocator m_alloc;
555
556 // The number of nodes for which range is computed throughout the current method.
557 // When this limit is zero, we have exhausted all the budget to walk the ud-chain.
558 int m_nVisitBudget;
559};
560