Permalink
Fetching contributors…
Cannot retrieve contributors at this time
560 lines (485 sloc) 17.3 KB
// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
// See the LICENSE file in the project root for more information.
//
//
// We take the following approach to range check analysis:
//
// Consider the following loop:
// for (int i = 0; i < a.len; ++i) {
// a[i] = 0;
// }
//
// This would be represented as:
// i_0 = 0; BB0
// / ______ a[i_1] = 0; BB2
// / / i_2 = i_1 + 1;
// / / ^
// i_1 = phi(i_0, i_2); BB1 |
// i_1 < a.len -------------------+
//
// BB0 -> BB1
// BB1 -> (i_1 < a.len) ? BB2 : BB3
// BB2 -> BB1
// BB3 -> return
//
// **Step 1. Walk the statements in the method checking if there is a bounds check.
// If there is a bounds check, ask the range of the index variable.
// In the above example i_1's range.
//
// **Step 2. Follow the defs and the dependency chain:
// i_1 is a local, so go to its definition which is i_1 = phi(i_0, i_2).
//
// Since rhs is a phi, we ask the range for i_0 and i_2 in the hopes of merging
// the resulting ranges for i_1.
//
// The range of i_0 follows immediately when going to its definition.
// Ask for the range of i_2, which leads to i_1 + 1.
// Ask for the range of i_1 and figure we are looping. Call the range of i_1 as
// "dependent" and quit looping further. The range of "1" is just <1, 1>.
//
// Now we have exhausted all the variables for which the range can be determined.
// The others are either "unknown" or "dependent."
//
// We also merge assertions from its pred block's edges for a phi argument otherwise
// from the block's assertionIn. This gives us an upper bound for i_1 as a.len.
//
// **Step 3. Check if an overflow occurs in the dependency chain (loop.)
// In the above case, we want to make sure there is no overflow in the definitions
// involving i_1 and i_2. Merge assertions from the block's edges whenever possible.
//
// **Step 4. Check if the dependency chain is monotonic.
//
// **Step 5. If monotonic is true, then perform a widening step, where we assume, the
// SSA variables that are "dependent" get their values from the definitions in the
// dependency loop and their initial values must be the definitions that are not in
// the dependency loop, in this case i_0's value which is 0.
//
#pragma once
#include "compiler.h"
static bool IntAddOverflows(int max1, int max2)
{
if (max1 > 0 && max2 > 0 && INT_MAX - max1 < max2)
{
return true;
}
if (max1 < 0 && max2 < 0 && max1 < INT_MIN - max2)
{
return true;
}
return false;
}
struct Limit
{
enum LimitType
{
keUndef, // The limit is yet to be computed.
keBinOpArray,
keConstant,
keDependent, // The limit is dependent on some other value.
keUnknown, // The limit could not be determined.
};
Limit() : type(keUndef)
{
}
Limit(LimitType type) : type(type)
{
}
Limit(LimitType type, int cns) : cns(cns), vn(ValueNumStore::NoVN), type(type)
{
assert(type == keConstant);
}
Limit(LimitType type, ValueNum vn, int cns) : cns(cns), vn(vn), type(type)
{
assert(type == keBinOpArray);
}
bool IsUndef()
{
return type == keUndef;
}
bool IsDependent()
{
return type == keDependent;
}
bool IsUnknown()
{
return type == keUnknown;
}
bool IsConstant()
{
return type == keConstant;
}
int GetConstant()
{
return cns;
}
bool IsBinOpArray()
{
return type == keBinOpArray;
}
bool AddConstant(int i)
{
switch (type)
{
case keDependent:
return true;
case keBinOpArray:
if (IntAddOverflows(cns, i))
{
return false;
}
cns += i;
return true;
case keConstant:
if (IntAddOverflows(cns, i))
{
return false;
}
cns += i;
return true;
case keUndef:
case keUnknown:
// For these values of 'type', conservatively return false
break;
}
return false;
}
bool Equals(Limit& l)
{
switch (type)
{
case keUndef:
case keUnknown:
case keDependent:
return l.type == type;
case keBinOpArray:
return l.type == type && l.vn == vn && l.cns == cns;
case keConstant:
return l.type == type && l.cns == cns;
}
return false;
}
#ifdef DEBUG
const char* ToString(CompAllocator alloc)
{
unsigned size = 64;
char* buf = alloc.allocate<char>(size);
switch (type)
{
case keUndef:
return "Undef";
case keUnknown:
return "Unknown";
case keDependent:
return "Dependent";
case keBinOpArray:
sprintf_s(buf, size, "VN%04X + %d", vn, cns);
return buf;
case keConstant:
sprintf_s(buf, size, "%d", cns);
return buf;
}
unreached();
}
#endif
int cns;
ValueNum vn;
LimitType type;
};
// Range struct contains upper and lower limit.
struct Range
{
Limit uLimit;
Limit lLimit;
Range(const Limit& limit) : uLimit(limit), lLimit(limit)
{
}
Range(const Limit& lLimit, const Limit& uLimit) : uLimit(uLimit), lLimit(lLimit)
{
}
Limit& UpperLimit()
{
return uLimit;
}
Limit& LowerLimit()
{
return lLimit;
}
#ifdef DEBUG
char* ToString(CompAllocator alloc)
{
size_t size = 64;
char* buf = alloc.allocate<char>(size);
sprintf_s(buf, size, "<%s, %s>", lLimit.ToString(alloc), uLimit.ToString(alloc));
return buf;
}
#endif
};
// Helpers for operations performed on ranges
struct RangeOps
{
// Given a constant limit in "l1", add it to l2 and mutate "l2".
static Limit AddConstantLimit(Limit& l1, Limit& l2)
{
assert(l1.IsConstant());
Limit l = l2;
if (l.AddConstant(l1.GetConstant()))
{
return l;
}
else
{
return Limit(Limit::keUnknown);
}
}
// Given two ranges "r1" and "r2", perform an add operation on the
// ranges.
static Range Add(Range& r1, Range& r2)
{
Limit& r1lo = r1.LowerLimit();
Limit& r1hi = r1.UpperLimit();
Limit& r2lo = r2.LowerLimit();
Limit& r2hi = r2.UpperLimit();
Range result = Limit(Limit::keUnknown);
// Check lo ranges if they are dependent and not unknown.
if ((r1lo.IsDependent() && !r1lo.IsUnknown()) || (r2lo.IsDependent() && !r2lo.IsUnknown()))
{
result.lLimit = Limit(Limit::keDependent);
}
// Check hi ranges if they are dependent and not unknown.
if ((r1hi.IsDependent() && !r1hi.IsUnknown()) || (r2hi.IsDependent() && !r2hi.IsUnknown()))
{
result.uLimit = Limit(Limit::keDependent);
}
if (r1lo.IsConstant())
{
result.lLimit = AddConstantLimit(r1lo, r2lo);
}
if (r2lo.IsConstant())
{
result.lLimit = AddConstantLimit(r2lo, r1lo);
}
if (r1hi.IsConstant())
{
result.uLimit = AddConstantLimit(r1hi, r2hi);
}
if (r2hi.IsConstant())
{
result.uLimit = AddConstantLimit(r2hi, r1hi);
}
return result;
}
// Given two ranges "r1" and "r2", do a Phi merge. If "monotonic" is true,
// then ignore the dependent variables.
static Range Merge(Range& r1, Range& r2, bool monotonic)
{
Limit& r1lo = r1.LowerLimit();
Limit& r1hi = r1.UpperLimit();
Limit& r2lo = r2.LowerLimit();
Limit& r2hi = r2.UpperLimit();
// Take care of lo part.
Range result = Limit(Limit::keUnknown);
if (r1lo.IsUnknown() || r2lo.IsUnknown())
{
result.lLimit = Limit(Limit::keUnknown);
}
// Uninitialized, just copy.
else if (r1lo.IsUndef())
{
result.lLimit = r2lo;
}
else if (r1lo.IsDependent() || r2lo.IsDependent())
{
if (monotonic)
{
result.lLimit = r1lo.IsDependent() ? r2lo : r1lo;
}
else
{
result.lLimit = Limit(Limit::keDependent);
}
}
// Take care of hi part.
if (r1hi.IsUnknown() || r2hi.IsUnknown())
{
result.uLimit = Limit(Limit::keUnknown);
}
else if (r1hi.IsUndef())
{
result.uLimit = r2hi;
}
else if (r1hi.IsDependent() || r2hi.IsDependent())
{
if (monotonic)
{
result.uLimit = r1hi.IsDependent() ? r2hi : r1hi;
}
else
{
result.uLimit = Limit(Limit::keDependent);
}
}
if (r1lo.IsConstant() && r2lo.IsConstant())
{
result.lLimit = Limit(Limit::keConstant, min(r1lo.GetConstant(), r2lo.GetConstant()));
}
if (r1hi.IsConstant() && r2hi.IsConstant())
{
result.uLimit = Limit(Limit::keConstant, max(r1hi.GetConstant(), r2hi.GetConstant()));
}
if (r2hi.Equals(r1hi))
{
result.uLimit = r2hi;
}
if (r2lo.Equals(r1lo))
{
result.lLimit = r1lo;
}
// Widen Upper Limit => Max(k, (a.len + n)) yields (a.len + n),
// This is correct if k >= 0 and n >= k, since a.len always >= 0
// (a.len + n) could overflow, but the result (a.len + n) also
// preserves the overflow.
if (r1hi.IsConstant() && r1hi.GetConstant() >= 0 && r2hi.IsBinOpArray() &&
r2hi.GetConstant() >= r1hi.GetConstant())
{
result.uLimit = r2hi;
}
if (r2hi.IsConstant() && r2hi.GetConstant() >= 0 && r1hi.IsBinOpArray() &&
r1hi.GetConstant() >= r2hi.GetConstant())
{
result.uLimit = r1hi;
}
if (r1hi.IsBinOpArray() && r2hi.IsBinOpArray() && r1hi.vn == r2hi.vn)
{
result.uLimit = r1hi;
// Widen the upper bound if the other constant is greater.
if (r2hi.GetConstant() > r1hi.GetConstant())
{
result.uLimit = r2hi;
}
}
return result;
}
};
class RangeCheck
{
public:
// Constructor
RangeCheck(Compiler* pCompiler);
typedef JitHashTable<GenTree*, JitPtrKeyFuncs<GenTree>, bool> OverflowMap;
typedef JitHashTable<GenTree*, JitPtrKeyFuncs<GenTree>, Range*> RangeMap;
typedef JitHashTable<GenTree*, JitPtrKeyFuncs<GenTree>, BasicBlock*> SearchPath;
#ifdef DEBUG
// TODO-Cleanup: This code has been kept around just to ensure that the SSA data is still
// valid when RangeCheck runs. It should be removed at some point (and perhaps replaced
// by a proper SSA validity checker).
// Location information is used to map where the defs occur in the method.
struct Location
{
BasicBlock* block;
GenTree* stmt;
GenTreeLclVarCommon* tree;
GenTree* parent;
Location(BasicBlock* block, GenTree* stmt, GenTreeLclVarCommon* tree, GenTree* parent)
: block(block), stmt(stmt), tree(tree), parent(parent)
{
}
private:
Location();
};
typedef JitHashTable<INT64, JitLargePrimitiveKeyFuncs<INT64>, Location*> VarToLocMap;
// Generate a hashcode unique for this ssa var.
UINT64 HashCode(unsigned lclNum, unsigned ssaNum);
// Add a location of the definition of ssa var to the location map.
// Requires "hash" to be computed using HashCode.
// Requires "location" to be the local definition.
void SetDef(UINT64 hash, Location* loc);
// Given a tree node that is a local, return the Location defining the local.
Location* GetDef(GenTreeLclVarCommon* lcl);
Location* GetDef(unsigned lclNum, unsigned ssaNum);
// Given a statement, check if it is a def and add its locations in a map.
void MapStmtDefs(const Location& loc);
// Given the CFG, check if it has defs and add their locations in a map.
void MapMethodDefs();
#endif
int GetArrLength(ValueNum vn);
// Check whether the computed range is within lower and upper bounds. This function
// assumes that the lower range is resolved and upper range is symbolic as in an
// increasing loop.
// TODO-CQ: This is not general enough.
bool BetweenBounds(Range& range, int lower, GenTree* upper);
// Entry point to optimize range checks in the block. Assumes value numbering
// and assertion prop phases are completed.
void OptimizeRangeChecks();
// Given a "tree" node, check if it contains array bounds check node and
// optimize to remove it, if possible. Requires "stmt" and "block" that
// contain the tree.
void OptimizeRangeCheck(BasicBlock* block, GenTree* stmt, GenTree* tree);
// Given the index expression try to find its range.
// The range of a variable depends on its rhs which in turn depends on its constituent variables.
// The "path" is the path taken in the search for the rhs' range and its constituents' range.
// If "monotonic" is true, the calculations are made more liberally assuming initial values
// at phi definitions.
Range GetRange(BasicBlock* block, GenTree* expr, bool monotonic DEBUGARG(int indent));
// Given the local variable, first find the definition of the local and find the range of the rhs.
// Helper for GetRange.
Range ComputeRangeForLocalDef(BasicBlock* block, GenTreeLclVarCommon* lcl, bool monotonic DEBUGARG(int indent));
// Compute the range, rather than retrieve a cached value. Helper for GetRange.
Range ComputeRange(BasicBlock* block, GenTree* expr, bool monotonic DEBUGARG(int indent));
// Compute the range for the op1 and op2 for the given binary operator.
Range ComputeRangeForBinOp(BasicBlock* block, GenTreeOp* binop, bool monotonic DEBUGARG(int indent));
// Merge assertions from AssertionProp's flags, for the corresponding "phiArg."
// Requires "pRange" to contain range that is computed partially.
void MergeAssertion(BasicBlock* block, GenTree* phiArg, Range* pRange DEBUGARG(int indent));
// Inspect the "assertions" and extract assertions about the given "phiArg" and
// refine the "pRange" value.
void MergeEdgeAssertions(GenTreeLclVarCommon* lcl, ASSERT_VALARG_TP assertions, Range* pRange);
// The maximum possible value of the given "limit." If such a value could not be determined
// return "false." For example: ARRLEN_MAX for array length.
bool GetLimitMax(Limit& limit, int* pMax);
// Does the addition of the two limits overflow?
bool AddOverflows(Limit& limit1, Limit& limit2);
// Does the binary operation between the operands overflow? Check recursively.
bool DoesBinOpOverflow(BasicBlock* block, GenTreeOp* binop);
// Does the phi operands involve an assignment that could overflow?
bool DoesPhiOverflow(BasicBlock* block, GenTree* expr);
// Find the def of the "expr" local and recurse on the arguments if any of them involve a
// calculation that overflows.
bool DoesVarDefOverflow(GenTreeLclVarCommon* lcl);
bool ComputeDoesOverflow(BasicBlock* block, GenTree* expr);
// Does the current "expr" which is a use involve a definition, that overflows.
bool DoesOverflow(BasicBlock* block, GenTree* tree);
// Widen the range by first checking if the induction variable is monotonic. Requires "pRange"
// to be partially computed.
void Widen(BasicBlock* block, GenTree* tree, Range* pRange);
// Is the binary operation increasing the value.
bool IsBinOpMonotonicallyIncreasing(GenTreeOp* binop);
// Given an "expr" trace its rhs and their definitions to check if all the assignments
// are monotonically increasing.
//
bool IsMonotonicallyIncreasing(GenTree* tree, bool rejectNegativeConst);
// We allocate a budget to avoid walking long UD chains. When traversing each link in the UD
// chain, we decrement the budget. When the budget hits 0, then no more range check optimization
// will be applied for the currently compiled method.
bool IsOverBudget();
private:
// Given a lclvar use, try to find the lclvar's defining assignment and its containing block.
GenTreeOp* GetSsaDefAsg(GenTreeLclVarCommon* lclUse, BasicBlock** asgBlock);
GenTreeBoundsChk* m_pCurBndsChk;
// Get the cached overflow values.
OverflowMap* GetOverflowMap();
OverflowMap* m_pOverflowMap;
// Get the cached range values.
RangeMap* GetRangeMap();
RangeMap* m_pRangeMap;
SearchPath* m_pSearchPath;
#ifdef DEBUG
bool m_fMappedDefs;
VarToLocMap* m_pDefTable;
#endif
Compiler* m_pCompiler;
CompAllocator m_alloc;
// The number of nodes for which range is computed throughout the current method.
// When this limit is zero, we have exhausted all the budget to walk the ud-chain.
int m_nVisitBudget;
};