Permalink
Fetching contributors…
Cannot retrieve contributors at this time
18048 lines (15859 sloc) 582 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.
/*XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XX XX
XX GenTree XX
XX XX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
*/
#include "jitpch.h"
#include "hwintrinsic.h"
#include "simd.h"
#ifdef _MSC_VER
#pragma hdrstop
#endif
/*****************************************************************************/
const unsigned short GenTree::gtOperKindTable[] = {
#define GTNODE(en, st, cm, ok) ok + GTK_COMMUTE *cm,
#include "gtlist.h"
};
/*****************************************************************************
*
* The types of different GenTree nodes
*/
#ifdef DEBUG
#define INDENT_SIZE 3
//--------------------------------------------
//
// IndentStack: This struct is used, along with its related enums and strings,
// to control both the indendtation and the printing of arcs.
//
// Notes:
// The mode of printing is set in the Constructor, using its 'compiler' argument.
// Currently it only prints arcs when fgOrder == fgOrderLinear.
// The type of arc to print is specified by the IndentInfo enum, and is controlled
// by the caller of the Push() method.
enum IndentChars
{
ICVertical,
ICBottom,
ICTop,
ICMiddle,
ICDash,
ICEmbedded,
ICTerminal,
ICError,
IndentCharCount
};
// clang-format off
// Sets of strings for different dumping options vert bot top mid dash embedded terminal error
static const char* emptyIndents[IndentCharCount] = { " ", " ", " ", " ", " ", "{", "", "?" };
static const char* asciiIndents[IndentCharCount] = { "|", "\\", "/", "+", "-", "{", "*", "?" };
static const char* unicodeIndents[IndentCharCount] = { "\xe2\x94\x82", "\xe2\x94\x94", "\xe2\x94\x8c", "\xe2\x94\x9c", "\xe2\x94\x80", "{", "\xe2\x96\x8c", "?" };
// clang-format on
typedef ArrayStack<Compiler::IndentInfo> IndentInfoStack;
struct IndentStack
{
IndentInfoStack stack;
const char** indents;
// Constructor for IndentStack. Uses 'compiler' to determine the mode of printing.
IndentStack(Compiler* compiler) : stack(compiler->getAllocator(CMK_DebugOnly))
{
if (compiler->asciiTrees)
{
indents = asciiIndents;
}
else
{
indents = unicodeIndents;
}
}
// Return the depth of the current indentation.
unsigned Depth()
{
return stack.Height();
}
// Push a new indentation onto the stack, of the given type.
void Push(Compiler::IndentInfo info)
{
stack.Push(info);
}
// Pop the most recent indentation type off the stack.
Compiler::IndentInfo Pop()
{
return stack.Pop();
}
// Print the current indentation and arcs.
void print()
{
unsigned indentCount = Depth();
for (unsigned i = 0; i < indentCount; i++)
{
unsigned index = indentCount - 1 - i;
switch (stack.Index(index))
{
case Compiler::IndentInfo::IINone:
printf(" ");
break;
case Compiler::IndentInfo::IIEmbedded:
printf("%s ", indents[ICEmbedded]);
break;
case Compiler::IndentInfo::IIArc:
if (index == 0)
{
printf("%s%s%s", indents[ICMiddle], indents[ICDash], indents[ICDash]);
}
else
{
printf("%s ", indents[ICVertical]);
}
break;
case Compiler::IndentInfo::IIArcBottom:
printf("%s%s%s", indents[ICBottom], indents[ICDash], indents[ICDash]);
break;
case Compiler::IndentInfo::IIArcTop:
printf("%s%s%s", indents[ICTop], indents[ICDash], indents[ICDash]);
break;
case Compiler::IndentInfo::IIError:
printf("%s%s%s", indents[ICError], indents[ICDash], indents[ICDash]);
break;
default:
unreached();
}
}
printf("%s", indents[ICTerminal]);
}
};
//------------------------------------------------------------------------
// printIndent: This is a static method which simply invokes the 'print'
// method on its 'indentStack' argument.
//
// Arguments:
// indentStack - specifies the information for the indentation & arcs to be printed
//
// Notes:
// This method exists to localize the checking for the case where indentStack is null.
static void printIndent(IndentStack* indentStack)
{
if (indentStack == nullptr)
{
return;
}
indentStack->print();
}
#endif
#if defined(DEBUG) || NODEBASH_STATS || MEASURE_NODE_SIZE || COUNT_AST_OPERS
static const char* opNames[] = {
#define GTNODE(en, st, cm, ok) #en,
#include "gtlist.h"
};
const char* GenTree::OpName(genTreeOps op)
{
assert((unsigned)op < _countof(opNames));
return opNames[op];
}
#endif
#if MEASURE_NODE_SIZE && SMALL_TREE_NODES
static const char* opStructNames[] = {
#define GTNODE(en, st, cm, ok) #st,
#include "gtlist.h"
};
const char* GenTree::OpStructName(genTreeOps op)
{
assert((unsigned)op < _countof(opStructNames));
return opStructNames[op];
}
#endif
/*****************************************************************************
*
* When 'SMALL_TREE_NODES' is enabled, we allocate tree nodes in 2 different
* sizes: 'TREE_NODE_SZ_SMALL' for most nodes and 'TREE_NODE_SZ_LARGE' for the
* few nodes (such as calls) that have more fields and take up a lot more space.
*/
#if SMALL_TREE_NODES
/* GT_COUNT'th oper is overloaded as 'undefined oper', so allocate storage for GT_COUNT'th oper also */
/* static */
unsigned char GenTree::s_gtNodeSizes[GT_COUNT + 1];
#if NODEBASH_STATS || MEASURE_NODE_SIZE || COUNT_AST_OPERS
unsigned char GenTree::s_gtTrueSizes[GT_COUNT + 1]{
#define GTNODE(en, st, cm, ok) sizeof(st),
#include "gtlist.h"
};
#endif // NODEBASH_STATS || MEASURE_NODE_SIZE || COUNT_AST_OPERS
#if COUNT_AST_OPERS
LONG GenTree::s_gtNodeCounts[GT_COUNT + 1] = {0};
#endif // COUNT_AST_OPERS
/* static */
void GenTree::InitNodeSize()
{
/* 'GT_LCL_VAR' often gets changed to 'GT_REG_VAR' */
assert(GenTree::s_gtNodeSizes[GT_LCL_VAR] >= GenTree::s_gtNodeSizes[GT_REG_VAR]);
/* Set all sizes to 'small' first */
for (unsigned op = 0; op <= GT_COUNT; op++)
{
GenTree::s_gtNodeSizes[op] = TREE_NODE_SZ_SMALL;
}
// Now set all of the appropriate entries to 'large'
CLANG_FORMAT_COMMENT_ANCHOR;
// clang-format off
#if defined(FEATURE_HFA) || defined(UNIX_AMD64_ABI)
// On ARM32, ARM64 and System V for struct returning
// there is code that does GT_ASG-tree.CopyObj call.
// CopyObj is a large node and the GT_ASG is small, which triggers an exception.
GenTree::s_gtNodeSizes[GT_ASG] = TREE_NODE_SZ_LARGE;
GenTree::s_gtNodeSizes[GT_RETURN] = TREE_NODE_SZ_LARGE;
#endif // defined(FEATURE_HFA) || defined(UNIX_AMD64_ABI)
GenTree::s_gtNodeSizes[GT_CALL] = TREE_NODE_SZ_LARGE;
GenTree::s_gtNodeSizes[GT_CAST] = TREE_NODE_SZ_LARGE;
GenTree::s_gtNodeSizes[GT_FTN_ADDR] = TREE_NODE_SZ_LARGE;
GenTree::s_gtNodeSizes[GT_BOX] = TREE_NODE_SZ_LARGE;
GenTree::s_gtNodeSizes[GT_INDEX] = TREE_NODE_SZ_LARGE;
GenTree::s_gtNodeSizes[GT_INDEX_ADDR] = TREE_NODE_SZ_LARGE;
GenTree::s_gtNodeSizes[GT_ARR_BOUNDS_CHECK] = TREE_NODE_SZ_LARGE;
#ifdef FEATURE_SIMD
GenTree::s_gtNodeSizes[GT_SIMD_CHK] = TREE_NODE_SZ_LARGE;
#endif // FEATURE_SIMD
#ifdef FEATURE_HW_INTRINSICS
GenTree::s_gtNodeSizes[GT_HW_INTRINSIC_CHK] = TREE_NODE_SZ_LARGE;
#endif // FEATURE_HW_INTRINSICS
GenTree::s_gtNodeSizes[GT_ARR_ELEM] = TREE_NODE_SZ_LARGE;
GenTree::s_gtNodeSizes[GT_ARR_INDEX] = TREE_NODE_SZ_LARGE;
GenTree::s_gtNodeSizes[GT_ARR_OFFSET] = TREE_NODE_SZ_LARGE;
GenTree::s_gtNodeSizes[GT_RET_EXPR] = TREE_NODE_SZ_LARGE;
GenTree::s_gtNodeSizes[GT_OBJ] = TREE_NODE_SZ_LARGE;
GenTree::s_gtNodeSizes[GT_FIELD] = TREE_NODE_SZ_LARGE;
GenTree::s_gtNodeSizes[GT_STMT] = TREE_NODE_SZ_LARGE;
GenTree::s_gtNodeSizes[GT_CMPXCHG] = TREE_NODE_SZ_LARGE;
GenTree::s_gtNodeSizes[GT_QMARK] = TREE_NODE_SZ_LARGE;
GenTree::s_gtNodeSizes[GT_LEA] = TREE_NODE_SZ_LARGE;
GenTree::s_gtNodeSizes[GT_STORE_OBJ] = TREE_NODE_SZ_LARGE;
GenTree::s_gtNodeSizes[GT_DYN_BLK] = TREE_NODE_SZ_LARGE;
GenTree::s_gtNodeSizes[GT_STORE_DYN_BLK] = TREE_NODE_SZ_LARGE;
GenTree::s_gtNodeSizes[GT_INTRINSIC] = TREE_NODE_SZ_LARGE;
GenTree::s_gtNodeSizes[GT_ALLOCOBJ] = TREE_NODE_SZ_LARGE;
#if USE_HELPERS_FOR_INT_DIV
GenTree::s_gtNodeSizes[GT_DIV] = TREE_NODE_SZ_LARGE;
GenTree::s_gtNodeSizes[GT_UDIV] = TREE_NODE_SZ_LARGE;
GenTree::s_gtNodeSizes[GT_MOD] = TREE_NODE_SZ_LARGE;
GenTree::s_gtNodeSizes[GT_UMOD] = TREE_NODE_SZ_LARGE;
#endif
#ifdef FEATURE_PUT_STRUCT_ARG_STK
// TODO-Throughput: This should not need to be a large node. The object info should be
// obtained from the child node.
GenTree::s_gtNodeSizes[GT_PUTARG_STK] = TREE_NODE_SZ_LARGE;
#if FEATURE_ARG_SPLIT
GenTree::s_gtNodeSizes[GT_PUTARG_SPLIT] = TREE_NODE_SZ_LARGE;
#endif // FEATURE_ARG_SPLIT
#endif // FEATURE_PUT_STRUCT_ARG_STK
assert(GenTree::s_gtNodeSizes[GT_RETURN] == GenTree::s_gtNodeSizes[GT_ASG]);
// This list of assertions should come to contain all GenTree subtypes that are declared
// "small".
assert(sizeof(GenTreeLclFld) <= GenTree::s_gtNodeSizes[GT_LCL_FLD]);
assert(sizeof(GenTreeLclVar) <= GenTree::s_gtNodeSizes[GT_LCL_VAR]);
static_assert_no_msg(sizeof(GenTree) <= TREE_NODE_SZ_SMALL);
static_assert_no_msg(sizeof(GenTreeUnOp) <= TREE_NODE_SZ_SMALL);
static_assert_no_msg(sizeof(GenTreeOp) <= TREE_NODE_SZ_SMALL);
static_assert_no_msg(sizeof(GenTreeVal) <= TREE_NODE_SZ_SMALL);
static_assert_no_msg(sizeof(GenTreeIntConCommon) <= TREE_NODE_SZ_SMALL);
static_assert_no_msg(sizeof(GenTreePhysReg) <= TREE_NODE_SZ_SMALL);
static_assert_no_msg(sizeof(GenTreeJumpTable) <= TREE_NODE_SZ_SMALL);
static_assert_no_msg(sizeof(GenTreeIntCon) <= TREE_NODE_SZ_SMALL);
static_assert_no_msg(sizeof(GenTreeLngCon) <= TREE_NODE_SZ_SMALL);
static_assert_no_msg(sizeof(GenTreeDblCon) <= TREE_NODE_SZ_SMALL);
static_assert_no_msg(sizeof(GenTreeStrCon) <= TREE_NODE_SZ_SMALL);
static_assert_no_msg(sizeof(GenTreeLclVarCommon) <= TREE_NODE_SZ_SMALL);
static_assert_no_msg(sizeof(GenTreeLclVar) <= TREE_NODE_SZ_SMALL);
static_assert_no_msg(sizeof(GenTreeLclFld) <= TREE_NODE_SZ_SMALL);
static_assert_no_msg(sizeof(GenTreeRegVar) <= TREE_NODE_SZ_SMALL);
static_assert_no_msg(sizeof(GenTreeCC) <= TREE_NODE_SZ_SMALL);
static_assert_no_msg(sizeof(GenTreeCast) <= TREE_NODE_SZ_LARGE); // *** large node
static_assert_no_msg(sizeof(GenTreeBox) <= TREE_NODE_SZ_LARGE); // *** large node
static_assert_no_msg(sizeof(GenTreeField) <= TREE_NODE_SZ_LARGE); // *** large node
static_assert_no_msg(sizeof(GenTreeArgList) <= TREE_NODE_SZ_SMALL);
static_assert_no_msg(sizeof(GenTreeFieldList) <= TREE_NODE_SZ_SMALL);
static_assert_no_msg(sizeof(GenTreeColon) <= TREE_NODE_SZ_SMALL);
static_assert_no_msg(sizeof(GenTreeCall) <= TREE_NODE_SZ_LARGE); // *** large node
static_assert_no_msg(sizeof(GenTreeCmpXchg) <= TREE_NODE_SZ_LARGE); // *** large node
static_assert_no_msg(sizeof(GenTreeFptrVal) <= TREE_NODE_SZ_LARGE); // *** large node
static_assert_no_msg(sizeof(GenTreeQmark) <= TREE_NODE_SZ_LARGE); // *** large node
static_assert_no_msg(sizeof(GenTreeIntrinsic) <= TREE_NODE_SZ_LARGE); // *** large node
static_assert_no_msg(sizeof(GenTreeIndex) <= TREE_NODE_SZ_LARGE); // *** large node
static_assert_no_msg(sizeof(GenTreeArrLen) <= TREE_NODE_SZ_LARGE); // *** large node
static_assert_no_msg(sizeof(GenTreeBoundsChk) <= TREE_NODE_SZ_LARGE); // *** large node
static_assert_no_msg(sizeof(GenTreeArrElem) <= TREE_NODE_SZ_LARGE); // *** large node
static_assert_no_msg(sizeof(GenTreeArrIndex) <= TREE_NODE_SZ_LARGE); // *** large node
static_assert_no_msg(sizeof(GenTreeArrOffs) <= TREE_NODE_SZ_LARGE); // *** large node
static_assert_no_msg(sizeof(GenTreeIndir) <= TREE_NODE_SZ_SMALL);
static_assert_no_msg(sizeof(GenTreeStoreInd) <= TREE_NODE_SZ_SMALL);
static_assert_no_msg(sizeof(GenTreeAddrMode) <= TREE_NODE_SZ_SMALL);
static_assert_no_msg(sizeof(GenTreeObj) <= TREE_NODE_SZ_LARGE); // *** large node
static_assert_no_msg(sizeof(GenTreeBlk) <= TREE_NODE_SZ_SMALL);
static_assert_no_msg(sizeof(GenTreeRetExpr) <= TREE_NODE_SZ_LARGE); // *** large node
static_assert_no_msg(sizeof(GenTreeStmt) <= TREE_NODE_SZ_LARGE); // *** large node
static_assert_no_msg(sizeof(GenTreeClsVar) <= TREE_NODE_SZ_SMALL);
static_assert_no_msg(sizeof(GenTreeArgPlace) <= TREE_NODE_SZ_SMALL);
static_assert_no_msg(sizeof(GenTreeLabel) <= TREE_NODE_SZ_SMALL);
static_assert_no_msg(sizeof(GenTreePhiArg) <= TREE_NODE_SZ_SMALL);
static_assert_no_msg(sizeof(GenTreeAllocObj) <= TREE_NODE_SZ_LARGE); // *** large node
#ifndef FEATURE_PUT_STRUCT_ARG_STK
static_assert_no_msg(sizeof(GenTreePutArgStk) <= TREE_NODE_SZ_SMALL);
#else // FEATURE_PUT_STRUCT_ARG_STK
// TODO-Throughput: This should not need to be a large node. The object info should be
// obtained from the child node.
static_assert_no_msg(sizeof(GenTreePutArgStk) <= TREE_NODE_SZ_LARGE);
#if FEATURE_ARG_SPLIT
static_assert_no_msg(sizeof(GenTreePutArgSplit) <= TREE_NODE_SZ_LARGE);
#endif // FEATURE_ARG_SPLIT
#endif // FEATURE_PUT_STRUCT_ARG_STK
#ifdef FEATURE_SIMD
static_assert_no_msg(sizeof(GenTreeSIMD) <= TREE_NODE_SZ_SMALL);
#endif // FEATURE_SIMD
#ifdef FEATURE_HW_INTRINSICS
static_assert_no_msg(sizeof(GenTreeHWIntrinsic) <= TREE_NODE_SZ_SMALL);
#endif // FEATURE_HW_INTRINSICS
// clang-format on
}
size_t GenTree::GetNodeSize() const
{
return GenTree::s_gtNodeSizes[gtOper];
}
#ifdef DEBUG
bool GenTree::IsNodeProperlySized() const
{
size_t size;
if (gtDebugFlags & GTF_DEBUG_NODE_SMALL)
{
size = TREE_NODE_SZ_SMALL;
}
else
{
assert(gtDebugFlags & GTF_DEBUG_NODE_LARGE);
size = TREE_NODE_SZ_LARGE;
}
return GenTree::s_gtNodeSizes[gtOper] <= size;
}
#endif
#if SMALL_TREE_NODES
//------------------------------------------------------------------------
// ReplaceWith: replace this with the src node. The source must be an isolated node
// and cannot be used after the replacement.
//
// Arguments:
// src - source tree, that replaces this.
// comp - the compiler instance to transfer annotations for arrays.
//
void GenTree::ReplaceWith(GenTree* src, Compiler* comp)
{
// The source may be big only if the target is also a big node
assert((gtDebugFlags & GTF_DEBUG_NODE_LARGE) || GenTree::s_gtNodeSizes[src->gtOper] == TREE_NODE_SZ_SMALL);
// The check is effective only if nodes have been already threaded.
assert((src->gtPrev == nullptr) && (src->gtNext == nullptr));
RecordOperBashing(OperGet(), src->OperGet()); // nop unless NODEBASH_STATS is enabled
GenTree* prev = gtPrev;
GenTree* next = gtNext;
// The VTable pointer is copied intentionally here
memcpy((void*)this, (void*)src, src->GetNodeSize());
this->gtPrev = prev;
this->gtNext = next;
#ifdef DEBUG
gtSeqNum = 0;
#endif
// Transfer any annotations.
if (src->OperGet() == GT_IND && src->gtFlags & GTF_IND_ARR_INDEX)
{
ArrayInfo arrInfo;
bool b = comp->GetArrayInfoMap()->Lookup(src, &arrInfo);
assert(b);
comp->GetArrayInfoMap()->Set(this, arrInfo);
}
DEBUG_DESTROY_NODE(src);
}
#endif
/*****************************************************************************
*
* When 'NODEBASH_STATS' is enabled in "jit.h" we record all instances of
* an existing GenTree node having its operator changed. This can be useful
* for two (related) things - to see what is being bashed (and what isn't),
* and to verify that the existing choices for what nodes are marked 'large'
* are reasonable (to minimize "wasted" space).
*
* And yes, the hash function / logic is simplistic, but it is conflict-free
* and transparent for what we need.
*/
#if NODEBASH_STATS
#define BASH_HASH_SIZE 211
inline unsigned hashme(genTreeOps op1, genTreeOps op2)
{
return ((op1 * 104729) ^ (op2 * 56569)) % BASH_HASH_SIZE;
}
struct BashHashDsc
{
unsigned __int32 bhFullHash; // the hash value (unique for all old->new pairs)
unsigned __int32 bhCount; // the same old->new bashings seen so far
unsigned __int8 bhOperOld; // original gtOper
unsigned __int8 bhOperNew; // new gtOper
};
static BashHashDsc BashHash[BASH_HASH_SIZE];
void GenTree::RecordOperBashing(genTreeOps operOld, genTreeOps operNew)
{
unsigned hash = hashme(operOld, operNew);
BashHashDsc* desc = BashHash + hash;
if (desc->bhFullHash != hash)
{
noway_assert(desc->bhCount == 0); // if this ever fires, need fix the hash fn
desc->bhFullHash = hash;
}
desc->bhCount += 1;
desc->bhOperOld = operOld;
desc->bhOperNew = operNew;
}
void GenTree::ReportOperBashing(FILE* f)
{
unsigned total = 0;
fflush(f);
fprintf(f, "\n");
fprintf(f, "Bashed gtOper stats:\n");
fprintf(f, "\n");
fprintf(f, " Old operator New operator #bytes old->new Count\n");
fprintf(f, " ---------------------------------------------------------------\n");
for (unsigned h = 0; h < BASH_HASH_SIZE; h++)
{
unsigned count = BashHash[h].bhCount;
if (count == 0)
continue;
unsigned opOld = BashHash[h].bhOperOld;
unsigned opNew = BashHash[h].bhOperNew;
fprintf(f, " GT_%-13s -> GT_%-13s [size: %3u->%3u] %c %7u\n", OpName((genTreeOps)opOld),
OpName((genTreeOps)opNew), s_gtTrueSizes[opOld], s_gtTrueSizes[opNew],
(s_gtTrueSizes[opOld] < s_gtTrueSizes[opNew]) ? 'X' : ' ', count);
total += count;
}
fprintf(f, "\n");
fprintf(f, "Total bashings: %u\n", total);
fprintf(f, "\n");
fflush(f);
}
#endif // NODEBASH_STATS
#else // SMALL_TREE_NODES
#ifdef DEBUG
bool GenTree::IsNodeProperlySized() const
{
return true;
}
#endif
#endif // SMALL_TREE_NODES
/*****************************************************************************/
#if MEASURE_NODE_SIZE
void GenTree::DumpNodeSizes(FILE* fp)
{
// Dump the sizes of the various GenTree flavors
#if SMALL_TREE_NODES
fprintf(fp, "Small tree node size = %3u bytes\n", TREE_NODE_SZ_SMALL);
#endif
fprintf(fp, "Large tree node size = %3u bytes\n", TREE_NODE_SZ_LARGE);
fprintf(fp, "\n");
#if SMALL_TREE_NODES
// Verify that node sizes are set kosherly and dump sizes
for (unsigned op = GT_NONE + 1; op < GT_COUNT; op++)
{
unsigned needSize = s_gtTrueSizes[op];
unsigned nodeSize = s_gtNodeSizes[op];
const char* structNm = OpStructName((genTreeOps)op);
const char* operName = OpName((genTreeOps)op);
bool repeated = false;
// Have we seen this struct flavor before?
for (unsigned mop = GT_NONE + 1; mop < op; mop++)
{
if (strcmp(structNm, OpStructName((genTreeOps)mop)) == 0)
{
repeated = true;
break;
}
}
// Don't repeat the same GenTree flavor unless we have an error
if (!repeated || needSize > nodeSize)
{
unsigned sizeChar = '?';
if (nodeSize == TREE_NODE_SZ_SMALL)
sizeChar = 'S';
else if (nodeSize == TREE_NODE_SZ_LARGE)
sizeChar = 'L';
fprintf(fp, "GT_%-16s ... %-19s = %3u bytes (%c)", operName, structNm, needSize, sizeChar);
if (needSize > nodeSize)
{
fprintf(fp, " -- ERROR -- allocation is only %u bytes!", nodeSize);
}
else if (needSize <= TREE_NODE_SZ_SMALL && nodeSize == TREE_NODE_SZ_LARGE)
{
fprintf(fp, " ... could be small");
}
fprintf(fp, "\n");
}
}
#endif
}
#endif // MEASURE_NODE_SIZE
/*****************************************************************************
*
* Walk all basic blocks and call the given function pointer for all tree
* nodes contained therein.
*/
void Compiler::fgWalkAllTreesPre(fgWalkPreFn* visitor, void* pCallBackData)
{
BasicBlock* block;
for (block = fgFirstBB; block; block = block->bbNext)
{
GenTree* tree;
for (tree = block->bbTreeList; tree; tree = tree->gtNext)
{
assert(tree->gtOper == GT_STMT);
fgWalkTreePre(&tree->gtStmt.gtStmtExpr, visitor, pCallBackData);
}
}
}
//-----------------------------------------------------------
// CopyReg: Copy the _gtRegNum/gtRegTag fields.
//
// Arguments:
// from - GenTree node from which to copy
//
// Return Value:
// None
void GenTree::CopyReg(GenTree* from)
{
_gtRegNum = from->_gtRegNum;
INDEBUG(gtRegTag = from->gtRegTag;)
// Also copy multi-reg state if this is a call node
if (IsCall())
{
assert(from->IsCall());
this->AsCall()->CopyOtherRegs(from->AsCall());
}
else if (IsCopyOrReload())
{
this->AsCopyOrReload()->CopyOtherRegs(from->AsCopyOrReload());
}
}
//------------------------------------------------------------------
// gtHasReg: Whether node beeen assigned a register by LSRA
//
// Arguments:
// None
//
// Return Value:
// Returns true if the node was assigned a register.
//
// In case of multi-reg call nodes, it is considered
// having a reg if regs are allocated for all its
// return values.
//
// In case of GT_COPY or GT_RELOAD of a multi-reg call,
// GT_COPY/GT_RELOAD is considered having a reg if it
// has a reg assigned to any of its positions.
//
// Assumption:
// In order for this to work properly, gtClearReg must be called
// prior to setting the register value.
//
bool GenTree::gtHasReg() const
{
bool hasReg;
if (IsMultiRegCall())
{
// Have to cast away const-ness because GetReturnTypeDesc() is a non-const method
GenTree* tree = const_cast<GenTree*>(this);
GenTreeCall* call = tree->AsCall();
unsigned regCount = call->GetReturnTypeDesc()->GetReturnRegCount();
hasReg = false;
// A Multi-reg call node is said to have regs, if it has
// reg assigned to each of its result registers.
for (unsigned i = 0; i < regCount; ++i)
{
hasReg = (call->GetRegNumByIdx(i) != REG_NA);
if (!hasReg)
{
break;
}
}
}
else if (IsCopyOrReloadOfMultiRegCall())
{
GenTree* tree = const_cast<GenTree*>(this);
GenTreeCopyOrReload* copyOrReload = tree->AsCopyOrReload();
GenTreeCall* call = copyOrReload->gtGetOp1()->AsCall();
unsigned regCount = call->GetReturnTypeDesc()->GetReturnRegCount();
hasReg = false;
// A Multi-reg copy or reload node is said to have regs,
// if it has valid regs in any of the positions.
for (unsigned i = 0; i < regCount; ++i)
{
hasReg = (copyOrReload->GetRegNumByIdx(i) != REG_NA);
if (hasReg)
{
break;
}
}
}
else
{
hasReg = (gtRegNum != REG_NA);
}
return hasReg;
}
//-----------------------------------------------------------------------------
// GetRegisterDstCount: Get the number of registers defined by the node.
//
// Arguments:
// None
//
// Return Value:
// The number of registers that this node defines.
//
// Notes:
// This should not be called on a contained node.
// This does not look at the actual register assignments, if any, and so
// is valid after Lowering.
//
int GenTree::GetRegisterDstCount() const
{
assert(!isContained());
if (!IsMultiRegNode())
{
return (IsValue()) ? 1 : 0;
}
else if (IsMultiRegCall())
{
// temporarily cast away const-ness as AsCall() method is not declared const
GenTree* temp = const_cast<GenTree*>(this);
return temp->AsCall()->GetReturnTypeDesc()->GetReturnRegCount();
}
else if (IsCopyOrReload())
{
return gtGetOp1()->GetRegisterDstCount();
}
#if FEATURE_ARG_SPLIT
else if (OperIsPutArgSplit())
{
return (const_cast<GenTree*>(this))->AsPutArgSplit()->gtNumRegs;
}
// A PUTARG_REG could be a MultiRegOp on ARM since we could move a double register to two int registers,
// either for all double parameters w/SoftFP or for varargs).
else
{
#ifdef _TARGET_ARM_
assert(OperIsMultiRegOp());
return (TypeGet() == TYP_LONG) ? 2 : 1;
#else
unreached();
#endif // _TARGET_ARM_
}
#endif // FEATURE_ARG_SPLIT
assert(!"Unexpected multi-reg node");
return 0;
}
//---------------------------------------------------------------
// gtGetRegMask: Get the reg mask of the node.
//
// Arguments:
// None
//
// Return Value:
// Reg Mask of GenTree node.
//
regMaskTP GenTree::gtGetRegMask() const
{
regMaskTP resultMask;
if (IsMultiRegCall())
{
// temporarily cast away const-ness as AsCall() method is not declared const
resultMask = genRegMask(gtRegNum);
GenTree* temp = const_cast<GenTree*>(this);
resultMask |= temp->AsCall()->GetOtherRegMask();
}
else if (IsCopyOrReloadOfMultiRegCall())
{
// A multi-reg copy or reload, will have valid regs for only those
// positions that need to be copied or reloaded. Hence we need
// to consider only those registers for computing reg mask.
GenTree* tree = const_cast<GenTree*>(this);
GenTreeCopyOrReload* copyOrReload = tree->AsCopyOrReload();
GenTreeCall* call = copyOrReload->gtGetOp1()->AsCall();
unsigned regCount = call->GetReturnTypeDesc()->GetReturnRegCount();
resultMask = RBM_NONE;
for (unsigned i = 0; i < regCount; ++i)
{
regNumber reg = copyOrReload->GetRegNumByIdx(i);
if (reg != REG_NA)
{
resultMask |= genRegMask(reg);
}
}
}
#if FEATURE_ARG_SPLIT
else if (OperIsPutArgSplit())
{
GenTree* tree = const_cast<GenTree*>(this);
GenTreePutArgSplit* splitArg = tree->AsPutArgSplit();
unsigned regCount = splitArg->gtNumRegs;
resultMask = RBM_NONE;
for (unsigned i = 0; i < regCount; ++i)
{
regNumber reg = splitArg->GetRegNumByIdx(i);
assert(reg != REG_NA);
resultMask |= genRegMask(reg);
}
}
#endif // FEATURE_ARG_SPLIT
else
{
resultMask = genRegMask(gtRegNum);
}
return resultMask;
}
//---------------------------------------------------------------
// GetOtherRegMask: Get the reg mask of gtOtherRegs of call node
//
// Arguments:
// None
//
// Return Value:
// Reg mask of gtOtherRegs of call node.
//
regMaskTP GenTreeCall::GetOtherRegMask() const
{
regMaskTP resultMask = RBM_NONE;
#if FEATURE_MULTIREG_RET
for (unsigned i = 0; i < MAX_RET_REG_COUNT - 1; ++i)
{
if (gtOtherRegs[i] != REG_NA)
{
resultMask |= genRegMask((regNumber)gtOtherRegs[i]);
continue;
}
break;
}
#endif
return resultMask;
}
//-------------------------------------------------------------------------
// IsPure:
// Returns true if this call is pure. For now, this uses the same
// definition of "pure" that is that used by HelperCallProperties: a
// pure call does not read or write any aliased (e.g. heap) memory or
// have other global side effects (e.g. class constructors, finalizers),
// but is allowed to throw an exception.
//
// NOTE: this call currently only returns true if the call target is a
// helper method that is known to be pure. No other analysis is
// performed.
//
// Arguments:
// Copiler - the compiler context.
//
// Returns:
// True if the call is pure; false otherwise.
//
bool GenTreeCall::IsPure(Compiler* compiler) const
{
return (gtCallType == CT_HELPER) &&
compiler->s_helperCallProperties.IsPure(compiler->eeGetHelperNum(gtCallMethHnd));
}
//-------------------------------------------------------------------------
// HasSideEffects:
// Returns true if this call has any side effects. All non-helpers are considered to have side-effects. Only helpers
// that do not mutate the heap, do not run constructors, may not throw, and are either a) pure or b) non-finalizing
// allocation functions are considered side-effect-free.
//
// Arguments:
// compiler - the compiler instance
// ignoreExceptions - when `true`, ignores exception side effects
// ignoreCctors - when `true`, ignores class constructor side effects
//
// Return Value:
// true if this call has any side-effects; false otherwise.
bool GenTreeCall::HasSideEffects(Compiler* compiler, bool ignoreExceptions, bool ignoreCctors) const
{
// Generally all GT_CALL nodes are considered to have side-effects, but we may have extra information about helper
// calls that can prove them side-effect-free.
if (gtCallType != CT_HELPER)
{
return true;
}
CorInfoHelpFunc helper = compiler->eeGetHelperNum(gtCallMethHnd);
HelperCallProperties& helperProperties = compiler->s_helperCallProperties;
// We definitely care about the side effects if MutatesHeap is true
if (helperProperties.MutatesHeap(helper))
{
return true;
}
// Unless we have been instructed to ignore cctors (CSE, for example, ignores cctors), consider them side effects.
if (!ignoreCctors && helperProperties.MayRunCctor(helper))
{
return true;
}
// If we also care about exceptions then check if the helper can throw
if (!ignoreExceptions && !helperProperties.NoThrow(helper))
{
return true;
}
// If this is not a Pure helper call or an allocator (that will not need to run a finalizer)
// then this call has side effects.
return !helperProperties.IsPure(helper) &&
(!helperProperties.IsAllocator(helper) || helperProperties.MayFinalize(helper));
}
//-------------------------------------------------------------------------
// HasNonStandardAddedArgs: Return true if the method has non-standard args added to the call
// argument list during argument morphing (fgMorphArgs), e.g., passed in R10 or R11 on AMD64.
// See also GetNonStandardAddedArgCount().
//
// Arguments:
// compiler - the compiler instance
//
// Return Value:
// true if there are any such args, false otherwise.
//
bool GenTreeCall::HasNonStandardAddedArgs(Compiler* compiler) const
{
return GetNonStandardAddedArgCount(compiler) != 0;
}
//-------------------------------------------------------------------------
// GetNonStandardAddedArgCount: Get the count of non-standard arguments that have been added
// during call argument morphing (fgMorphArgs). Do not count non-standard args that are already
// counted in the argument list prior to morphing.
//
// This function is used to help map the caller and callee arguments during tail call setup.
//
// Arguments:
// compiler - the compiler instance
//
// Return Value:
// The count of args, as described.
//
// Notes:
// It would be more general to have fgMorphArgs set a bit on the call node when such
// args are added to a call, and a bit on each such arg, and then have this code loop
// over the call args when the special call bit is set, counting the args with the special
// arg bit. This seems pretty heavyweight, though. Instead, this logic needs to be kept
// in sync with fgMorphArgs.
//
int GenTreeCall::GetNonStandardAddedArgCount(Compiler* compiler) const
{
if (IsUnmanaged() && !compiler->opts.ShouldUsePInvokeHelpers())
{
// R11 = PInvoke cookie param
return 1;
}
else if (IsVirtualStub())
{
// R11 = Virtual stub param
return 1;
}
else if ((gtCallType == CT_INDIRECT) && (gtCallCookie != nullptr))
{
// R10 = PInvoke target param
// R11 = PInvoke cookie param
return 2;
}
return 0;
}
//-------------------------------------------------------------------------
// TreatAsHasRetBufArg:
//
// Arguments:
// compiler, the compiler instance so that we can call eeGetHelperNum
//
// Return Value:
// Returns true if we treat the call as if it has a retBuf argument
// This method may actually have a retBuf argument
// or it could be a JIT helper that we are still transforming during
// the importer phase.
//
// Notes:
// On ARM64 marking the method with the GTF_CALL_M_RETBUFFARG flag
// will make HasRetBufArg() return true, but will also force the
// use of register x8 to pass the RetBuf argument.
//
// These two Jit Helpers that we handle here by returning true
// aren't actually defined to return a struct, so they don't expect
// their RetBuf to be passed in x8, instead they expect it in x0.
//
bool GenTreeCall::TreatAsHasRetBufArg(Compiler* compiler) const
{
if (HasRetBufArg())
{
return true;
}
else
{
// If we see a Jit helper call that returns a TYP_STRUCT we will
// transform it as if it has a Return Buffer Argument
//
if (IsHelperCall() && (gtReturnType == TYP_STRUCT))
{
// There are two possible helper calls that use this path:
// CORINFO_HELP_GETFIELDSTRUCT and CORINFO_HELP_UNBOX_NULLABLE
//
CorInfoHelpFunc helpFunc = compiler->eeGetHelperNum(gtCallMethHnd);
if (helpFunc == CORINFO_HELP_GETFIELDSTRUCT)
{
return true;
}
else if (helpFunc == CORINFO_HELP_UNBOX_NULLABLE)
{
return true;
}
else
{
assert(!"Unexpected JIT helper in TreatAsHasRetBufArg");
}
}
}
return false;
}
//-------------------------------------------------------------------------
// IsHelperCall: Determine if this GT_CALL node is a specific helper call.
//
// Arguments:
// compiler - the compiler instance so that we can call eeFindHelper
//
// Return Value:
// Returns true if this GT_CALL node is a call to the specified helper.
//
bool GenTreeCall::IsHelperCall(Compiler* compiler, unsigned helper) const
{
return IsHelperCall(compiler->eeFindHelper(helper));
}
//------------------------------------------------------------------------
// GenTreeCall::ReplaceCallOperand:
// Replaces a given operand to a call node and updates the call
// argument table if necessary.
//
// Arguments:
// useEdge - the use edge that points to the operand to be replaced.
// replacement - the replacement node.
//
void GenTreeCall::ReplaceCallOperand(GenTree** useEdge, GenTree* replacement)
{
assert(useEdge != nullptr);
assert(replacement != nullptr);
assert(TryGetUse(*useEdge, &useEdge));
GenTree* originalOperand = *useEdge;
*useEdge = replacement;
const bool isArgument =
(replacement != gtControlExpr) &&
((gtCallType != CT_INDIRECT) || ((replacement != gtCallCookie) && (replacement != gtCallAddr)));
if (isArgument)
{
if ((originalOperand->gtFlags & GTF_LATE_ARG) != 0)
{
replacement->gtFlags |= GTF_LATE_ARG;
}
else
{
assert((replacement->gtFlags & GTF_LATE_ARG) == 0);
fgArgTabEntry* fp = Compiler::gtArgEntryByNode(this, originalOperand);
assert(fp->node == originalOperand);
fp->node = replacement;
}
}
}
//-------------------------------------------------------------------------
// AreArgsComplete: Determine if this GT_CALL node's arguments have been processed.
//
// Return Value:
// Returns true if fgMorphArgs has processed the arguments.
//
bool GenTreeCall::AreArgsComplete() const
{
if (fgArgInfo == nullptr)
{
return false;
}
if (fgArgInfo->AreArgsComplete())
{
assert((gtCallLateArgs != nullptr) || !fgArgInfo->HasRegArgs());
return true;
}
assert(gtCallArgs == nullptr);
return false;
}
#if !defined(FEATURE_PUT_STRUCT_ARG_STK)
unsigned GenTreePutArgStk::getArgSize()
{
return genTypeSize(genActualType(gtOp1->gtType));
}
#endif // !defined(FEATURE_PUT_STRUCT_ARG_STK)
/*****************************************************************************
*
* Returns non-zero if the two trees are identical.
*/
bool GenTree::Compare(GenTree* op1, GenTree* op2, bool swapOK)
{
genTreeOps oper;
unsigned kind;
// printf("tree1:\n"); gtDispTree(op1);
// printf("tree2:\n"); gtDispTree(op2);
AGAIN:
if (op1 == nullptr)
{
return (op2 == nullptr);
}
if (op2 == nullptr)
{
return false;
}
if (op1 == op2)
{
return true;
}
assert(op1->gtOper != GT_STMT);
assert(op2->gtOper != GT_STMT);
oper = op1->OperGet();
/* The operators must be equal */
if (oper != op2->gtOper)
{
return false;
}
/* The types must be equal */
if (op1->gtType != op2->gtType)
{
return false;
}
/* Overflow must be equal */
if (op1->gtOverflowEx() != op2->gtOverflowEx())
{
return false;
}
/* Sensible flags must be equal */
if ((op1->gtFlags & (GTF_UNSIGNED)) != (op2->gtFlags & (GTF_UNSIGNED)))
{
return false;
}
/* Figure out what kind of nodes we're comparing */
kind = op1->OperKind();
/* Is this a constant node? */
if (kind & GTK_CONST)
{
switch (oper)
{
case GT_CNS_INT:
if (op1->gtIntCon.gtIconVal == op2->gtIntCon.gtIconVal)
{
return true;
}
break;
#if 0
// TODO-CQ: Enable this in the future
case GT_CNS_LNG:
if (op1->gtLngCon.gtLconVal == op2->gtLngCon.gtLconVal)
return true;
break;
case GT_CNS_DBL:
if (op1->gtDblCon.gtDconVal == op2->gtDblCon.gtDconVal)
return true;
break;
#endif
default:
break;
}
return false;
}
/* Is this a leaf node? */
if (kind & GTK_LEAF)
{
switch (oper)
{
case GT_LCL_VAR:
if (op1->gtLclVarCommon.gtLclNum != op2->gtLclVarCommon.gtLclNum)
{
break;
}
return true;
case GT_LCL_FLD:
if (op1->gtLclFld.gtLclNum != op2->gtLclFld.gtLclNum ||
op1->gtLclFld.gtLclOffs != op2->gtLclFld.gtLclOffs)
{
break;
}
return true;
case GT_CLS_VAR:
if (op1->gtClsVar.gtClsVarHnd != op2->gtClsVar.gtClsVarHnd)
{
break;
}
return true;
case GT_LABEL:
return true;
case GT_ARGPLACE:
if ((op1->gtType == TYP_STRUCT) &&
(op1->gtArgPlace.gtArgPlaceClsHnd != op2->gtArgPlace.gtArgPlaceClsHnd))
{
break;
}
return true;
default:
break;
}
return false;
}
/* Is it a 'simple' unary/binary operator? */
if (kind & GTK_UNOP)
{
if (IsExOp(kind))
{
// ExOp operators extend unary operator with extra, non-GenTree* members. In many cases,
// these should be included in the comparison.
switch (oper)
{
case GT_ARR_LENGTH:
if (op1->gtArrLen.ArrLenOffset() != op2->gtArrLen.ArrLenOffset())
{
return false;
}
break;
case GT_CAST:
if (op1->gtCast.gtCastType != op2->gtCast.gtCastType)
{
return false;
}
break;
case GT_OBJ:
if (op1->AsObj()->gtClass != op2->AsObj()->gtClass)
{
return false;
}
break;
// For the ones below no extra argument matters for comparison.
case GT_BOX:
break;
default:
assert(!"unexpected unary ExOp operator");
}
}
return Compare(op1->gtOp.gtOp1, op2->gtOp.gtOp1);
}
if (kind & GTK_BINOP)
{
if (IsExOp(kind))
{
// ExOp operators extend unary operator with extra, non-GenTree* members. In many cases,
// these should be included in the hash code.
switch (oper)
{
case GT_INTRINSIC:
if (op1->gtIntrinsic.gtIntrinsicId != op2->gtIntrinsic.gtIntrinsicId)
{
return false;
}
break;
case GT_LEA:
if (op1->gtAddrMode.gtScale != op2->gtAddrMode.gtScale)
{
return false;
}
if (op1->gtAddrMode.Offset() != op2->gtAddrMode.Offset())
{
return false;
}
break;
case GT_INDEX:
if (op1->gtIndex.gtIndElemSize != op2->gtIndex.gtIndElemSize)
{
return false;
}
break;
case GT_INDEX_ADDR:
if (op1->AsIndexAddr()->gtElemSize != op2->AsIndexAddr()->gtElemSize)
{
return false;
}
break;
#ifdef FEATURE_SIMD
case GT_SIMD:
if ((op1->AsSIMD()->gtSIMDIntrinsicID != op2->AsSIMD()->gtSIMDIntrinsicID) ||
(op1->AsSIMD()->gtSIMDBaseType != op2->AsSIMD()->gtSIMDBaseType) ||
(op1->AsSIMD()->gtSIMDSize != op2->AsSIMD()->gtSIMDSize))
{
return false;
}
break;
#endif // FEATURE_SIMD
#ifdef FEATURE_HW_INTRINSICS
case GT_HWIntrinsic:
if ((op1->AsHWIntrinsic()->gtHWIntrinsicId != op2->AsHWIntrinsic()->gtHWIntrinsicId) ||
(op1->AsHWIntrinsic()->gtSIMDBaseType != op2->AsHWIntrinsic()->gtSIMDBaseType) ||
(op1->AsHWIntrinsic()->gtSIMDSize != op2->AsHWIntrinsic()->gtSIMDSize))
{
return false;
}
break;
#endif
// For the ones below no extra argument matters for comparison.
case GT_QMARK:
break;
default:
assert(!"unexpected binary ExOp operator");
}
}
if (op1->gtOp.gtOp2)
{
if (!Compare(op1->gtOp.gtOp1, op2->gtOp.gtOp1, swapOK))
{
if (swapOK && OperIsCommutative(oper) &&
((op1->gtOp.gtOp1->gtFlags | op1->gtOp.gtOp2->gtFlags | op2->gtOp.gtOp1->gtFlags |
op2->gtOp.gtOp2->gtFlags) &
GTF_ALL_EFFECT) == 0)
{
if (Compare(op1->gtOp.gtOp1, op2->gtOp.gtOp2, swapOK))
{
op1 = op1->gtOp.gtOp2;
op2 = op2->gtOp.gtOp1;
goto AGAIN;
}
}
return false;
}
op1 = op1->gtOp.gtOp2;
op2 = op2->gtOp.gtOp2;
goto AGAIN;
}
else
{
op1 = op1->gtOp.gtOp1;
op2 = op2->gtOp.gtOp1;
if (!op1)
{
return (op2 == nullptr);
}
if (!op2)
{
return false;
}
goto AGAIN;
}
}
/* See what kind of a special operator we have here */
switch (oper)
{
case GT_FIELD:
if (op1->gtField.gtFldHnd != op2->gtField.gtFldHnd)
{
break;
}
op1 = op1->gtField.gtFldObj;
op2 = op2->gtField.gtFldObj;
if (op1 || op2)
{
if (op1 && op2)
{
goto AGAIN;
}
}
return true;
case GT_CALL:
if (op1->gtCall.gtCallType != op2->gtCall.gtCallType)
{
return false;
}
if (op1->gtCall.gtCallType != CT_INDIRECT)
{
if (op1->gtCall.gtCallMethHnd != op2->gtCall.gtCallMethHnd)
{
return false;
}
#ifdef FEATURE_READYTORUN_COMPILER
if (op1->gtCall.gtEntryPoint.addr != op2->gtCall.gtEntryPoint.addr)
{
return false;
}
#endif
}
else
{
if (!Compare(op1->gtCall.gtCallAddr, op2->gtCall.gtCallAddr))
{
return false;
}
}
if (Compare(op1->gtCall.gtCallLateArgs, op2->gtCall.gtCallLateArgs) &&
Compare(op1->gtCall.gtCallArgs, op2->gtCall.gtCallArgs) &&
Compare(op1->gtCall.gtControlExpr, op2->gtCall.gtControlExpr) &&
Compare(op1->gtCall.gtCallObjp, op2->gtCall.gtCallObjp))
{
return true;
}
break;
case GT_ARR_ELEM:
if (op1->gtArrElem.gtArrRank != op2->gtArrElem.gtArrRank)
{
return false;
}
// NOTE: gtArrElemSize may need to be handled
unsigned dim;
for (dim = 0; dim < op1->gtArrElem.gtArrRank; dim++)
{
if (!Compare(op1->gtArrElem.gtArrInds[dim], op2->gtArrElem.gtArrInds[dim]))
{
return false;
}
}
op1 = op1->gtArrElem.gtArrObj;
op2 = op2->gtArrElem.gtArrObj;
goto AGAIN;
case GT_ARR_OFFSET:
if (op1->gtArrOffs.gtCurrDim != op2->gtArrOffs.gtCurrDim ||
op1->gtArrOffs.gtArrRank != op2->gtArrOffs.gtArrRank)
{
return false;
}
return (Compare(op1->gtArrOffs.gtOffset, op2->gtArrOffs.gtOffset) &&
Compare(op1->gtArrOffs.gtIndex, op2->gtArrOffs.gtIndex) &&
Compare(op1->gtArrOffs.gtArrObj, op2->gtArrOffs.gtArrObj));
case GT_CMPXCHG:
return Compare(op1->gtCmpXchg.gtOpLocation, op2->gtCmpXchg.gtOpLocation) &&
Compare(op1->gtCmpXchg.gtOpValue, op2->gtCmpXchg.gtOpValue) &&
Compare(op1->gtCmpXchg.gtOpComparand, op2->gtCmpXchg.gtOpComparand);
case GT_ARR_BOUNDS_CHECK:
#ifdef FEATURE_SIMD
case GT_SIMD_CHK:
#endif // FEATURE_SIMD
#ifdef FEATURE_HW_INTRINSICS
case GT_HW_INTRINSIC_CHK:
#endif // FEATURE_HW_INTRINSICS
return Compare(op1->gtBoundsChk.gtIndex, op2->gtBoundsChk.gtIndex) &&
Compare(op1->gtBoundsChk.gtArrLen, op2->gtBoundsChk.gtArrLen) &&
(op1->gtBoundsChk.gtThrowKind == op2->gtBoundsChk.gtThrowKind);
case GT_STORE_DYN_BLK:
case GT_DYN_BLK:
return Compare(op1->gtDynBlk.Addr(), op2->gtDynBlk.Addr()) &&
Compare(op1->gtDynBlk.Data(), op2->gtDynBlk.Data()) &&
Compare(op1->gtDynBlk.gtDynamicSize, op2->gtDynBlk.gtDynamicSize);
default:
assert(!"unexpected operator");
}
return false;
}
/*****************************************************************************
*
* Returns non-zero if the given tree contains a use of a local #lclNum.
*/
bool Compiler::gtHasRef(GenTree* tree, ssize_t lclNum, bool defOnly)
{
genTreeOps oper;
unsigned kind;
AGAIN:
assert(tree);
oper = tree->OperGet();
kind = tree->OperKind();
assert(oper != GT_STMT);
/* Is this a constant node? */
if (kind & GTK_CONST)
{
return false;
}
/* Is this a leaf node? */
if (kind & GTK_LEAF)
{
if (oper == GT_LCL_VAR)
{
if (tree->gtLclVarCommon.gtLclNum == (unsigned)lclNum)
{
if (!defOnly)
{
return true;
}
}
}
else if (oper == GT_RET_EXPR)
{
return gtHasRef(tree->gtRetExpr.gtInlineCandidate, lclNum, defOnly);
}
return false;
}
/* Is it a 'simple' unary/binary operator? */
if (kind & GTK_SMPOP)
{
if (tree->gtGetOp2IfPresent())
{
if (gtHasRef(tree->gtOp.gtOp1, lclNum, defOnly))
{
return true;
}
tree = tree->gtOp.gtOp2;
goto AGAIN;
}
else
{
tree = tree->gtOp.gtOp1;
if (!tree)
{
return false;
}
if (GenTree::OperIsAssignment(oper))
{
// 'tree' is the gtOp1 of an assignment node. So we can handle
// the case where defOnly is either true or false.
if (tree->gtOper == GT_LCL_VAR && tree->gtLclVarCommon.gtLclNum == (unsigned)lclNum)
{
return true;
}
else if (tree->gtOper == GT_FIELD && lclNum == (ssize_t)tree->gtField.gtFldHnd)
{
return true;
}
}
goto AGAIN;
}
}
/* See what kind of a special operator we have here */
switch (oper)
{
case GT_FIELD:
if (lclNum == (ssize_t)tree->gtField.gtFldHnd)
{
if (!defOnly)
{
return true;
}
}
tree = tree->gtField.gtFldObj;
if (tree)
{
goto AGAIN;
}
break;
case GT_CALL:
if (tree->gtCall.gtCallObjp)
{
if (gtHasRef(tree->gtCall.gtCallObjp, lclNum, defOnly))
{
return true;
}
}
if (tree->gtCall.gtCallArgs)
{
if (gtHasRef(tree->gtCall.gtCallArgs, lclNum, defOnly))
{
return true;
}
}
if (tree->gtCall.gtCallLateArgs)
{
if (gtHasRef(tree->gtCall.gtCallLateArgs, lclNum, defOnly))
{
return true;
}
}
if (tree->gtCall.gtControlExpr)
{
if (gtHasRef(tree->gtCall.gtControlExpr, lclNum, defOnly))
{
return true;
}
}
if (tree->gtCall.gtCallType == CT_INDIRECT)
{
// pinvoke-calli cookie is a constant, or constant indirection
assert(tree->gtCall.gtCallCookie == nullptr || tree->gtCall.gtCallCookie->gtOper == GT_CNS_INT ||
tree->gtCall.gtCallCookie->gtOper == GT_IND);
tree = tree->gtCall.gtCallAddr;
}
else
{
tree = nullptr;
}
if (tree)
{
goto AGAIN;
}
break;
case GT_ARR_ELEM:
if (gtHasRef(tree->gtArrElem.gtArrObj, lclNum, defOnly))
{
return true;
}
unsigned dim;
for (dim = 0; dim < tree->gtArrElem.gtArrRank; dim++)
{
if (gtHasRef(tree->gtArrElem.gtArrInds[dim], lclNum, defOnly))
{
return true;
}
}
break;
case GT_ARR_OFFSET:
if (gtHasRef(tree->gtArrOffs.gtOffset, lclNum, defOnly) ||
gtHasRef(tree->gtArrOffs.gtIndex, lclNum, defOnly) ||
gtHasRef(tree->gtArrOffs.gtArrObj, lclNum, defOnly))
{
return true;
}
break;
case GT_CMPXCHG:
if (gtHasRef(tree->gtCmpXchg.gtOpLocation, lclNum, defOnly))
{
return true;
}
if (gtHasRef(tree->gtCmpXchg.gtOpValue, lclNum, defOnly))
{
return true;
}
if (gtHasRef(tree->gtCmpXchg.gtOpComparand, lclNum, defOnly))
{
return true;
}
break;
case GT_ARR_BOUNDS_CHECK:
#ifdef FEATURE_SIMD
case GT_SIMD_CHK:
#endif // FEATURE_SIMD
#ifdef FEATURE_HW_INTRINSICS
case GT_HW_INTRINSIC_CHK:
#endif // FEATURE_HW_INTRINSICS
if (gtHasRef(tree->gtBoundsChk.gtIndex, lclNum, defOnly))
{
return true;
}
if (gtHasRef(tree->gtBoundsChk.gtArrLen, lclNum, defOnly))
{
return true;
}
break;
case GT_STORE_DYN_BLK:
if (gtHasRef(tree->gtDynBlk.Data(), lclNum, defOnly))
{
return true;
}
__fallthrough;
case GT_DYN_BLK:
if (gtHasRef(tree->gtDynBlk.Addr(), lclNum, defOnly))
{
return true;
}
if (gtHasRef(tree->gtDynBlk.gtDynamicSize, lclNum, defOnly))
{
return true;
}
break;
default:
#ifdef DEBUG
gtDispTree(tree);
#endif
assert(!"unexpected operator");
}
return false;
}
struct AddrTakenDsc
{
Compiler* comp;
bool hasAddrTakenLcl;
};
/* static */
Compiler::fgWalkResult Compiler::gtHasLocalsWithAddrOpCB(GenTree** pTree, fgWalkData* data)
{
GenTree* tree = *pTree;
Compiler* comp = data->compiler;
if (tree->gtOper == GT_LCL_VAR)
{
unsigned lclNum = tree->gtLclVarCommon.gtLclNum;
LclVarDsc* varDsc = &comp->lvaTable[lclNum];
if (varDsc->lvHasLdAddrOp || varDsc->lvAddrExposed)
{
((AddrTakenDsc*)data->pCallbackData)->hasAddrTakenLcl = true;
return WALK_ABORT;
}
}
return WALK_CONTINUE;
}
/*****************************************************************************
*
* Return true if this tree contains locals with lvHasLdAddrOp or lvAddrExposed
* flag(s) set.
*/
bool Compiler::gtHasLocalsWithAddrOp(GenTree* tree)
{
AddrTakenDsc desc;
desc.comp = this;
desc.hasAddrTakenLcl = false;
fgWalkTreePre(&tree, gtHasLocalsWithAddrOpCB, &desc);
return desc.hasAddrTakenLcl;
}
#ifdef DEBUG
/*****************************************************************************
*
* Helper used to compute hash values for trees.
*/
inline unsigned genTreeHashAdd(unsigned old, unsigned add)
{
return (old + old / 2) ^ add;
}
inline unsigned genTreeHashAdd(unsigned old, void* add)
{
return genTreeHashAdd(old, (unsigned)(size_t)add);
}
/*****************************************************************************
*
* Given an arbitrary expression tree, compute a hash value for it.
*/
unsigned Compiler::gtHashValue(GenTree* tree)
{
genTreeOps oper;
unsigned kind;
unsigned hash = 0;
GenTree* temp;
AGAIN:
assert(tree);
assert(tree->gtOper != GT_STMT);
/* Figure out what kind of a node we have */
oper = tree->OperGet();
kind = tree->OperKind();
/* Include the operator value in the hash */
hash = genTreeHashAdd(hash, oper);
/* Is this a constant or leaf node? */
if (kind & (GTK_CONST | GTK_LEAF))
{
size_t add;
switch (oper)
{
UINT64 bits;
case GT_LCL_VAR:
add = tree->gtLclVar.gtLclNum;
break;
case GT_LCL_FLD:
hash = genTreeHashAdd(hash, tree->gtLclFld.gtLclNum);
add = tree->gtLclFld.gtLclOffs;
break;
case GT_CNS_INT:
add = tree->gtIntCon.gtIconVal;
break;
case GT_CNS_LNG:
bits = (UINT64)tree->gtLngCon.gtLconVal;
#ifdef _TARGET_64BIT_
add = bits;
#else // 32-bit target
add = genTreeHashAdd(uhi32(bits), ulo32(bits));
#endif
break;
case GT_CNS_DBL:
bits = *(UINT64*)(&tree->gtDblCon.gtDconVal);
#ifdef _TARGET_64BIT_
add = bits;
#else // 32-bit target
add = genTreeHashAdd(uhi32(bits), ulo32(bits));
#endif
break;
case GT_CNS_STR:
add = tree->gtStrCon.gtSconCPX;
break;
case GT_JMP:
add = tree->gtVal.gtVal1;
break;
default:
add = 0;
break;
}
// clang-format off
// narrow 'add' into a 32-bit 'val'
unsigned val;
#ifdef _TARGET_64BIT_
val = genTreeHashAdd(uhi32(add), ulo32(add));
#else // 32-bit target
val = add;
#endif
// clang-format on
hash = genTreeHashAdd(hash, val);
goto DONE;
}
/* Is it a 'simple' unary/binary operator? */
GenTree* op1;
if (kind & GTK_UNOP)
{
op1 = tree->gtOp.gtOp1;
/* Special case: no sub-operand at all */
if (GenTree::IsExOp(kind))
{
// ExOp operators extend operators with extra, non-GenTree* members. In many cases,
// these should be included in the hash code.
switch (oper)
{
case GT_ARR_LENGTH:
hash += tree->gtArrLen.ArrLenOffset();
break;
case GT_CAST:
hash ^= tree->gtCast.gtCastType;
break;
case GT_INDEX:
hash += tree->gtIndex.gtIndElemSize;
break;
case GT_INDEX_ADDR:
hash += tree->AsIndexAddr()->gtElemSize;
break;
case GT_ALLOCOBJ:
hash = genTreeHashAdd(hash, static_cast<unsigned>(
reinterpret_cast<uintptr_t>(tree->gtAllocObj.gtAllocObjClsHnd)));
hash = genTreeHashAdd(hash, tree->gtAllocObj.gtNewHelper);
break;
case GT_RUNTIMELOOKUP:
hash =
genTreeHashAdd(hash,
static_cast<unsigned>(reinterpret_cast<uintptr_t>(tree->gtRuntimeLookup.gtHnd)));
break;
case GT_OBJ:
hash =
genTreeHashAdd(hash, static_cast<unsigned>(reinterpret_cast<uintptr_t>(tree->gtObj.gtClass)));
break;
// For the ones below no extra argument matters for comparison.
case GT_BOX:
break;
default:
assert(!"unexpected unary ExOp operator");
}
}
if (!op1)
{
goto DONE;
}
tree = op1;
goto AGAIN;
}
if (kind & GTK_BINOP)
{
if (GenTree::IsExOp(kind))
{
// ExOp operators extend operators with extra, non-GenTree* members. In many cases,
// these should be included in the hash code.
switch (oper)
{
case GT_INTRINSIC:
hash += tree->gtIntrinsic.gtIntrinsicId;
break;
case GT_LEA:
hash += static_cast<unsigned>(tree->gtAddrMode.Offset() << 3) + tree->gtAddrMode.gtScale;
break;
case GT_BLK:
case GT_STORE_BLK:
hash += tree->gtBlk.gtBlkSize;
break;
case GT_OBJ:
case GT_STORE_OBJ:
hash ^= reinterpret_cast<unsigned>(tree->AsObj()->gtClass);
break;
case GT_DYN_BLK:
case GT_STORE_DYN_BLK:
hash += gtHashValue(tree->AsDynBlk()->gtDynamicSize);
break;
// For the ones below no extra argument matters for comparison.
case GT_ARR_INDEX:
case GT_QMARK:
case GT_INDEX:
case GT_INDEX_ADDR:
break;
#ifdef FEATURE_SIMD
case GT_SIMD:
hash += tree->gtSIMD.gtSIMDIntrinsicID;
hash += tree->gtSIMD.gtSIMDBaseType;
hash += tree->gtSIMD.gtSIMDSize;
break;
#endif // FEATURE_SIMD
#ifdef FEATURE_HW_INTRINSICS
case GT_HWIntrinsic:
hash += tree->gtHWIntrinsic.gtHWIntrinsicId;
hash += tree->gtHWIntrinsic.gtSIMDBaseType;
hash += tree->gtHWIntrinsic.gtSIMDSize;
break;
#endif // FEATURE_HW_INTRINSICS
default:
assert(!"unexpected binary ExOp operator");
}
}
op1 = tree->gtOp.gtOp1;
GenTree* op2 = tree->gtOp.gtOp2;
/* Is there a second sub-operand? */
if (!op2)
{
/* Special case: no sub-operands at all */
if (!op1)
{
goto DONE;
}
/* This is a unary operator */
tree = op1;
goto AGAIN;
}
/* This is a binary operator */
unsigned hsh1 = gtHashValue(op1);
/* Add op1's hash to the running value and continue with op2 */
hash = genTreeHashAdd(hash, hsh1);
tree = op2;
goto AGAIN;
}
/* See what kind of a special operator we have here */
switch (tree->gtOper)
{
case GT_FIELD:
if (tree->gtField.gtFldObj)
{
temp = tree->gtField.gtFldObj;
assert(temp);
hash = genTreeHashAdd(hash, gtHashValue(temp));
}
break;
case GT_STMT:
temp = tree->gtStmt.gtStmtExpr;
assert(temp);
hash = genTreeHashAdd(hash, gtHashValue(temp));
break;
case GT_ARR_ELEM:
hash = genTreeHashAdd(hash, gtHashValue(tree->gtArrElem.gtArrObj));
unsigned dim;
for (dim = 0; dim < tree->gtArrElem.gtArrRank; dim++)
{
hash = genTreeHashAdd(hash, gtHashValue(tree->gtArrElem.gtArrInds[dim]));
}
break;
case GT_ARR_OFFSET:
hash = genTreeHashAdd(hash, gtHashValue(tree->gtArrOffs.gtOffset));
hash = genTreeHashAdd(hash, gtHashValue(tree->gtArrOffs.gtIndex));
hash = genTreeHashAdd(hash, gtHashValue(tree->gtArrOffs.gtArrObj));
break;
case GT_CALL:
if (tree->gtCall.gtCallObjp && tree->gtCall.gtCallObjp->gtOper != GT_NOP)
{
temp = tree->gtCall.gtCallObjp;
assert(temp);
hash = genTreeHashAdd(hash, gtHashValue(temp));
}
if (tree->gtCall.gtCallArgs)
{
temp = tree->gtCall.gtCallArgs;
assert(temp);
hash = genTreeHashAdd(hash, gtHashValue(temp));
}
if (tree->gtCall.gtCallType == CT_INDIRECT)
{
temp = tree->gtCall.gtCallAddr;
assert(temp);
hash = genTreeHashAdd(hash, gtHashValue(temp));
}
else
{
hash = genTreeHashAdd(hash, tree->gtCall.gtCallMethHnd);
}
if (tree->gtCall.gtCallLateArgs)
{
temp = tree->gtCall.gtCallLateArgs;
assert(temp);
hash = genTreeHashAdd(hash, gtHashValue(temp));
}
break;
case GT_CMPXCHG:
hash = genTreeHashAdd(hash, gtHashValue(tree->gtCmpXchg.gtOpLocation));
hash = genTreeHashAdd(hash, gtHashValue(tree->gtCmpXchg.gtOpValue));
hash = genTreeHashAdd(hash, gtHashValue(tree->gtCmpXchg.gtOpComparand));
break;
case GT_ARR_BOUNDS_CHECK:
#ifdef FEATURE_SIMD
case GT_SIMD_CHK:
#endif // FEATURE_SIMD
#ifdef FEATURE_HW_INTRINSICS
case GT_HW_INTRINSIC_CHK:
#endif // FEATURE_HW_INTRINSICS
hash = genTreeHashAdd(hash, gtHashValue(tree->gtBoundsChk.gtIndex));
hash = genTreeHashAdd(hash, gtHashValue(tree->gtBoundsChk.gtArrLen));
hash = genTreeHashAdd(hash, tree->gtBoundsChk.gtThrowKind);
break;
case GT_STORE_DYN_BLK:
hash = genTreeHashAdd(hash, gtHashValue(tree->gtDynBlk.Data()));
__fallthrough;
case GT_DYN_BLK:
hash = genTreeHashAdd(hash, gtHashValue(tree->gtDynBlk.Addr()));
hash = genTreeHashAdd(hash, gtHashValue(tree->gtDynBlk.gtDynamicSize));
break;
default:
#ifdef DEBUG
gtDispTree(tree);
#endif
assert(!"unexpected operator");
break;
}
DONE:
return hash;
}
#endif // DEBUG
/*****************************************************************************
*
* Given an arbitrary expression tree, attempts to find the set of all local variables
* referenced by the tree, and return them as "*result".
* If "findPtr" is null, this is a tracked variable set;
* if it is non-null, this is an "all var set."
* The "*result" value is valid only if the call returns "true." It may return "false"
* for several reasons:
* If "findPtr" is NULL, and the expression contains an untracked variable.
* If "findPtr" is non-NULL, and the expression contains a variable that can't be represented
* in an "all var set."
* If the expression accesses address-exposed variables.
*
* If there
* are any indirections or global refs in the expression, the "*refsPtr" argument
* will be assigned the appropriate bit set based on the 'varRefKinds' type.
* It won't be assigned anything when there are no indirections or global
* references, though, so this value should be initialized before the call.
* If we encounter an expression that is equal to *findPtr we set *findPtr
* to NULL.
*/
bool Compiler::lvaLclVarRefs(GenTree* tree, GenTree** findPtr, varRefKinds* refsPtr, void* result)
{
genTreeOps oper;
unsigned kind;
varRefKinds refs = VR_NONE;
ALLVARSET_TP allVars(AllVarSetOps::UninitVal());
VARSET_TP trkdVars(VarSetOps::UninitVal());
if (findPtr)
{
AllVarSetOps::AssignNoCopy(this, allVars, AllVarSetOps::MakeEmpty(this));
}
else
{
VarSetOps::AssignNoCopy(this, trkdVars, VarSetOps::MakeEmpty(this));
}
AGAIN:
assert(tree);
assert(tree->gtOper != GT_STMT);
/* Remember whether we've come across the expression we're looking for */
if (findPtr && *findPtr == tree)
{
*findPtr = nullptr;
}
/* Figure out what kind of a node we have */
oper = tree->OperGet();
kind = tree->OperKind();
/* Is this a constant or leaf node? */
if (kind & (GTK_CONST | GTK_LEAF))
{
if (oper == GT_LCL_VAR)
{
unsigned lclNum = tree->gtLclVarCommon.gtLclNum;
/* Should we use the variable table? */
if (findPtr)
{
if (lclNum >= lclMAX_ALLSET_TRACKED)
{
return false;
}
AllVarSetOps::AddElemD(this, allVars, lclNum);
}
else
{
assert(lclNum < lvaCount);
LclVarDsc* varDsc = lvaTable + lclNum;
if (varDsc->lvTracked == false)
{
return false;
}
// Don't deal with expressions with address-exposed variables.
if (varDsc->lvAddrExposed)
{
return false;
}
VarSetOps::AddElemD(this, trkdVars, varDsc->lvVarIndex);
}
}
else if (oper == GT_LCL_FLD)
{
/* We can't track every field of every var. Moreover, indirections
may access different parts of the var as different (but
overlapping) fields. So just treat them as indirect accesses */
if (varTypeIsGC(tree->TypeGet()))
{
refs = VR_IND_REF;
}
else
{
refs = VR_IND_SCL;
}
}
else if (oper == GT_CLS_VAR)
{
refs = VR_GLB_VAR;
}
if (refs != VR_NONE)
{
/* Write it back to callers parameter using an 'or' */
*refsPtr = varRefKinds((*refsPtr) | refs);
}
lvaLclVarRefsAccumIntoRes(findPtr, result, allVars, trkdVars);
return true;
}
/* Is it a 'simple' unary/binary operator? */
if (kind & GTK_SMPOP)
{
if (oper == GT_IND)
{
assert(tree->gtOp.gtOp2 == nullptr);
/* Set the proper indirection bit */
if ((tree->gtFlags & GTF_IND_INVARIANT) == 0)
{
if (varTypeIsGC(tree->TypeGet()))
{
refs = VR_IND_REF;
}
else
{
refs = VR_IND_SCL;
}
// If the flag GTF_IND_TGTANYWHERE is set this indirection
// could also point at a global variable
if (tree->gtFlags & GTF_IND_TGTANYWHERE)
{
refs = varRefKinds(((int)refs) | ((int)VR_GLB_VAR));
}
}
/* Write it back to callers parameter using an 'or' */
*refsPtr = varRefKinds((*refsPtr) | refs);
// For IL volatile memory accesses we mark the GT_IND node
// with a GTF_DONT_CSE flag.
//
// This flag is also set for the left hand side of an assignment.
//
// If this flag is set then we return false
//
if (tree->gtFlags & GTF_DONT_CSE)
{
return false;
}
}
if (tree->gtGetOp2IfPresent())
{
/* It's a binary operator */
if (!lvaLclVarRefsAccum(tree->gtOp.gtOp1, findPtr, refsPtr, &allVars, &trkdVars))
{
return false;
}
// Otherwise...
tree = tree->gtOp.gtOp2;
assert(tree);
goto AGAIN;
}
else
{
/* It's a unary (or nilary) operator */
tree = tree->gtOp.gtOp1;
if (tree)
{
goto AGAIN;
}
lvaLclVarRefsAccumIntoRes(findPtr, result, allVars, trkdVars);
return true;
}
}
switch (oper)
{
case GT_ARR_ELEM:
if (!lvaLclVarRefsAccum(tree->gtArrElem.gtArrObj, findPtr, refsPtr, &allVars, &trkdVars))
{
return false;
}
unsigned dim;
for (dim = 0; dim < tree->gtArrElem.gtArrRank; dim++)
{
VARSET_TP tmpVs(VarSetOps::UninitVal());
if (!lvaLclVarRefsAccum(tree->gtArrElem.gtArrInds[dim], findPtr, refsPtr, &allVars, &trkdVars))
{
return false;
}
}
lvaLclVarRefsAccumIntoRes(findPtr, result, allVars, trkdVars);
return true;
case GT_ARR_OFFSET:
if (!lvaLclVarRefsAccum(tree->gtArrOffs.gtOffset, findPtr, refsPtr, &allVars, &trkdVars))
{
return false;
}
// Otherwise...
if (!lvaLclVarRefsAccum(tree->gtArrOffs.gtIndex, findPtr, refsPtr, &allVars, &trkdVars))
{
return false;
}
// Otherwise...
if (!lvaLclVarRefsAccum(tree->gtArrOffs.gtArrObj, findPtr, refsPtr, &allVars, &trkdVars))
{
return false;
}
// Otherwise...
lvaLclVarRefsAccumIntoRes(findPtr, result, allVars, trkdVars);
return true;
case GT_ARR_BOUNDS_CHECK:
#ifdef FEATURE_SIMD
case GT_SIMD_CHK:
#endif // FEATURE_SIMD
#ifdef FEATURE_HW_INTRINSICS
case GT_HW_INTRINSIC_CHK:
#endif // FEATURE_HW_INTRINSICS
{
if (!lvaLclVarRefsAccum(tree->gtBoundsChk.gtIndex, findPtr, refsPtr, &allVars, &trkdVars))
{
return false;
}
// Otherwise...
if (!lvaLclVarRefsAccum(tree->gtBoundsChk.gtArrLen, findPtr, refsPtr, &allVars, &trkdVars))
{
return false;
}
// Otherwise...
lvaLclVarRefsAccumIntoRes(findPtr, result, allVars, trkdVars);
return true;
}
case GT_STORE_DYN_BLK:
if (!lvaLclVarRefsAccum(tree->gtDynBlk.Data(), findPtr, refsPtr, &allVars, &trkdVars))
{
return false;
}
// Otherwise...
__fallthrough;
case GT_DYN_BLK:
if (!lvaLclVarRefsAccum(tree->gtDynBlk.Addr(), findPtr, refsPtr, &allVars, &trkdVars))
{
return false;
}
// Otherwise...
if (!lvaLclVarRefsAccum(tree->gtDynBlk.gtDynamicSize, findPtr, refsPtr, &allVars, &trkdVars))
{
return false;
}
// Otherwise...
lvaLclVarRefsAccumIntoRes(findPtr, result, allVars, trkdVars);
break;
case GT_CALL:
/* Allow calls to the Shared Static helper */
if (IsSharedStaticHelper(tree))
{
*refsPtr = varRefKinds((*refsPtr) | VR_INVARIANT);
lvaLclVarRefsAccumIntoRes(findPtr, result, allVars, trkdVars);
return true;
}
break;
default:
break;
} // end switch (oper)
return false;
}
bool Compiler::lvaLclVarRefsAccum(
GenTree* tree, GenTree** findPtr, varRefKinds* refsPtr, ALLVARSET_TP* allVars, VARSET_TP* trkdVars)
{
if (findPtr)
{
ALLVARSET_TP tmpVs(AllVarSetOps::UninitVal());
if (!lvaLclVarRefs(tree, findPtr, refsPtr, &tmpVs))
{
return false;
}
// Otherwise...
AllVarSetOps::UnionD(this, *allVars, tmpVs);
}
else
{
VARSET_TP tmpVs(VarSetOps::UninitVal());
if (!lvaLclVarRefs(tree, findPtr, refsPtr, &tmpVs))
{
return false;
}
// Otherwise...
VarSetOps::UnionD(this, *trkdVars, tmpVs);
}
return true;
}
void Compiler::lvaLclVarRefsAccumIntoRes(GenTree** findPtr,
void* result,
ALLVARSET_VALARG_TP allVars,
VARSET_VALARG_TP trkdVars)
{
if (findPtr)
{
ALLVARSET_TP* avsPtr = (ALLVARSET_TP*)result;
AllVarSetOps::AssignNoCopy(this, (*avsPtr), allVars);
}
else
{
VARSET_TP* vsPtr = (VARSET_TP*)result;
VarSetOps::AssignNoCopy(this, (*vsPtr), trkdVars);
}
}
/*****************************************************************************
*
* Return a relational operator that is the reverse of the given one.
*/
/* static */
genTreeOps GenTree::ReverseRelop(genTreeOps relop)
{
static const genTreeOps reverseOps[] = {
GT_NE, // GT_EQ
GT_EQ, // GT_NE
GT_GE, // GT_LT
GT_GT, // GT_LE
GT_LT, // GT_GE
GT_LE, // GT_GT
GT_TEST_NE, // GT_TEST_EQ
GT_TEST_EQ, // GT_TEST_NE
};
assert(reverseOps[GT_EQ - GT_EQ] == GT_NE);
assert(reverseOps[GT_NE - GT_EQ] == GT_EQ);
assert(reverseOps[GT_LT - GT_EQ] == GT_GE);
assert(reverseOps[GT_LE - GT_EQ] == GT_GT);
assert(reverseOps[GT_GE - GT_EQ] == GT_LT);
assert(reverseOps[GT_GT - GT_EQ] == GT_LE);
assert(reverseOps[GT_TEST_EQ - GT_EQ] == GT_TEST_NE);
assert(reverseOps[GT_TEST_NE - GT_EQ] == GT_TEST_EQ);
assert(OperIsCompare(relop));
assert(relop >= GT_EQ && (unsigned)(relop - GT_EQ) < sizeof(reverseOps));
return reverseOps[relop - GT_EQ];
}
/*****************************************************************************
*
* Return a relational operator that will work for swapped operands.
*/
/* static */
genTreeOps GenTree::SwapRelop(genTreeOps relop)
{
static const genTreeOps swapOps[] = {
GT_EQ, // GT_EQ
GT_NE, // GT_NE
GT_GT, // GT_LT
GT_GE, // GT_LE
GT_LE, // GT_GE
GT_LT, // GT_GT
GT_TEST_EQ, // GT_TEST_EQ
GT_TEST_NE, // GT_TEST_NE
};
assert(swapOps[GT_EQ - GT_EQ] == GT_EQ);
assert(swapOps[GT_NE - GT_EQ] == GT_NE);
assert(swapOps[GT_LT - GT_EQ] == GT_GT);
assert(swapOps[GT_LE - GT_EQ] == GT_GE);
assert(swapOps[GT_GE - GT_EQ] == GT_LE);
assert(swapOps[GT_GT - GT_EQ] == GT_LT);
assert(swapOps[GT_TEST_EQ - GT_EQ] == GT_TEST_EQ);
assert(swapOps[GT_TEST_NE - GT_EQ] == GT_TEST_NE);
assert(OperIsCompare(relop));
assert(relop >= GT_EQ && (unsigned)(relop - GT_EQ) < sizeof(swapOps));
return swapOps[relop - GT_EQ];
}
/*****************************************************************************
*
* Reverse the meaning of the given test condition.
*/
GenTree* Compiler::gtReverseCond(GenTree* tree)
{
if (tree->OperIsCompare())
{
tree->SetOper(GenTree::ReverseRelop(tree->OperGet()));
// Flip the GTF_RELOP_NAN_UN bit
// a ord b === (a != NaN && b != NaN)
// a unord b === (a == NaN || b == NaN)
// => !(a ord b) === (a unord b)
if (varTypeIsFloating(tree->gtOp.gtOp1->TypeGet()))
{
tree->gtFlags ^= GTF_RELOP_NAN_UN;
}
}
else if (tree->OperIs(GT_JCC, GT_SETCC))
{
GenTreeCC* cc = tree->AsCC();
cc->gtCondition = GenTree::ReverseRelop(cc->gtCondition);
}
else if (tree->OperIs(GT_JCMP))
{
// Flip the GTF_JCMP_EQ
//
// This causes switching
// cbz <=> cbnz
// tbz <=> tbnz
tree->gtFlags ^= GTF_JCMP_EQ;
}
else
{
tree = gtNewOperNode(GT_NOT, TYP_INT, tree);
}
return tree;
}
/*****************************************************************************/
#ifdef DEBUG
bool GenTree::gtIsValid64RsltMul()
{
if ((gtOper != GT_MUL) || !(gtFlags & GTF_MUL_64RSLT))
{
return false;
}
GenTree* op1 = gtOp.gtOp1;
GenTree* op2 = gtOp.gtOp2;
if (TypeGet() != TYP_LONG || op1->TypeGet() != TYP_LONG || op2->TypeGet() != TYP_LONG)
{
return false;
}
if (gtOverflow())
{
return false;
}
// op1 has to be conv.i8(i4Expr)
if ((op1->gtOper != GT_CAST) || (genActualType(op1->CastFromType()) != TYP_INT))
{
return false;
}
// op2 has to be conv.i8(i4Expr)
if ((op2->gtOper != GT_CAST) || (genActualType(op2->CastFromType()) != TYP_INT))
{
return false;
}
// The signedness of both casts must be the same
if (((op1->gtFlags & GTF_UNSIGNED) != 0) != ((op2->gtFlags & GTF_UNSIGNED) != 0))
{
return false;
}
// Do unsigned mul iff both the casts are unsigned
if (((op1->gtFlags & GTF_UNSIGNED) != 0) != ((gtFlags & GTF_UNSIGNED) != 0))
{
return false;
}
return true;
}
#endif // DEBUG
//------------------------------------------------------------------------------
// gtSetListOrder : Figure out the evaluation order for a list of values.
//
//
// Arguments:
// list - List to figure out the evaluation order for
// isListCallArgs - True iff the list is a list of call arguments
// callArgsInRegs - True iff the list is a list of call arguments and they are passed in registers
//
// Return Value:
// True if the operation can be a root of a bitwise rotation tree; false otherwise.
unsigned Compiler::gtSetListOrder(GenTree* list, bool isListCallArgs, bool callArgsInRegs)
{
assert((list != nullptr) && list->OperIsAnyList());
assert(!callArgsInRegs || isListCallArgs);
ArrayStack<GenTree*> listNodes(getAllocator(CMK_ArrayStack));
do
{
listNodes.Push(list);
list = list->gtOp.gtOp2;
} while ((list != nullptr) && (list->OperIsAnyList()));
unsigned nxtlvl = (list == nullptr) ? 0 : gtSetEvalOrder(list);
while (listNodes.Height() > 0)
{
list = listNodes.Pop();
assert(list && list->OperIsAnyList());
GenTree* next = list->gtOp.gtOp2;
unsigned level = 0;
unsigned ftreg = 0;
// TODO: Do we have to compute costs differently for argument lists and
// all other lists?
// https://github.com/dotnet/coreclr/issues/7095
unsigned costSz = (isListCallArgs || (next == nullptr)) ? 0 : 1;
unsigned costEx = (isListCallArgs || (next == nullptr)) ? 0 : 1;
if (next != nullptr)
{
ftreg |= next->gtRsvdRegs;
if (isListCallArgs)
{
if (level < nxtlvl)
{
level = nxtlvl;
}
}
costEx += next->gtCostEx;
costSz += next->gtCostSz;
}
GenTree* op1 = list->gtOp.gtOp1;
unsigned lvl = gtSetEvalOrder(op1);
list->gtRsvdRegs = (regMaskSmall)(ftreg | op1->gtRsvdRegs);
// Swap the level counts
if (list->gtFlags & GTF_REVERSE_OPS)
{
unsigned tmpl;
tmpl = lvl;
lvl = nxtlvl;
nxtlvl = tmpl;
}
// TODO: Do we have to compute levels differently for argument lists and
// all other lists?
// https://github.com/dotnet/coreclr/issues/7095
if (isListCallArgs)
{
if (level < lvl)
{
level = lvl;
}
}
else
{
if (lvl < 1)
{
level = nxtlvl;
}
else if (lvl == nxtlvl)
{
level = lvl + 1;
}
else
{
level = lvl;
}
}
if (op1->gtCostEx != 0)
{
costEx += op1->gtCostEx;
costEx += (callArgsInRegs || !isListCallArgs) ? 0 : IND_COST_EX;
}
if (op1->gtCostSz != 0)
{
costSz += op1->gtCostSz;
#ifdef _TARGET_XARCH_
if (callArgsInRegs) // push is smaller than mov to reg
#endif
{
costSz += 1;
}
}
list->SetCosts(costEx, costSz);
nxtlvl = level;
}
return nxtlvl;
}
//-----------------------------------------------------------------------------
// gtWalkOp: Traverse and mark an address expression
//
// Arguments:
// op1WB - An out parameter which is either the address expression, or one
// of its operands.
// op2WB - An out parameter which starts as either null or one of the operands
// of the address expression.
// base - The base address of the addressing mode, or null if 'constOnly' is false
// constOnly - True if we will only traverse into ADDs with constant op2.
//
// This routine is a helper routine for gtSetEvalOrder() and is used to identify the
// base and index nodes, which will be validated against those identified by
// genCreateAddrMode().
// It also marks the ADD nodes involved in the address expression with the
// GTF_ADDRMODE_NO_CSE flag which prevents them from being considered for CSE's.
//
// Its two output parameters are modified under the following conditions:
//
// It is called once with the original address expression as 'op1WB', and
// with 'constOnly' set to false. On this first invocation, *op1WB is always
// an ADD node, and it will consider the operands of the ADD even if its op2 is
// not a constant. However, when it encounters a non-constant or the base in the
// op2 position, it stops iterating. That operand is returned in the 'op2WB' out
// parameter, and will be considered on the third invocation of this method if
// it is an ADD.
//
// It is called the second time with the two operands of the original expression, in
// the original order, and the third time in reverse order. For these invocations
// 'constOnly' is true, so it will only traverse cascaded ADD nodes if they have a
// constant op2.
//
// The result, after three invocations, is that the values of the two out parameters
// correspond to the base and index in some fashion. This method doesn't attempt
// to determine or validate the scale or offset, if any.
//
// Assumptions (presumed to be ensured by genCreateAddrMode()):
// If an ADD has a constant operand, it is in the op2 position.
//
// Notes:
// This method, and its invocation sequence, are quite confusing, and since they
// were not originally well-documented, this specification is a possibly-imperfect
// reconstruction.
// The motivation for the handling of the NOP case is unclear.
// Note that 'op2WB' is only modified in the initial (!constOnly) case,
// or if a NOP is encountered in the op1 position.
//
void Compiler::gtWalkOp(GenTree** op1WB, GenTree** op2WB, GenTree* base, bool constOnly)
{
GenTree* op1 = *op1WB;
GenTree* op2 = *op2WB;
op1 = op1->gtEffectiveVal();
// Now we look for op1's with non-overflow GT_ADDs [of constants]
while ((op1->gtOper == GT_ADD) && (!op1->gtOverflow()) && (!constOnly || (op1->gtOp.gtOp2->IsCnsIntOrI())))
{
// mark it with GTF_ADDRMODE_NO_CSE
op1->gtFlags |= GTF_ADDRMODE_NO_CSE;
if (!constOnly)
{
op2 = op1->gtOp.gtOp2;
}
op1 = op1->gtOp.gtOp1;
// If op1 is a GT_NOP then swap op1 and op2.
// (Why? Also, presumably op2 is not a GT_NOP in this case?)
if (op1->gtOper == GT_NOP)
{
GenTree* tmp;
tmp = op1;
op1 = op2;
op2 = tmp;
}
if (!constOnly && ((op2 == base) || (!op2->IsCnsIntOrI())))
{
break;
}
op1 = op1->gtEffectiveVal();
}
*op1WB = op1;
*op2WB = op2;
}
#ifdef DEBUG
/*****************************************************************************
* This is a workaround. It is to help implement an assert in gtSetEvalOrder() that the values
* gtWalkOp() leaves in op1 and op2 correspond with the values of adr, idx, mul, and cns
* that are returned by genCreateAddrMode(). It's essentially impossible to determine
* what gtWalkOp() *should* return for all possible trees. This simply loosens one assert
* to handle the following case:
indir int
const(h) int 4 field
+ byref
lclVar byref V00 this <-- op2
comma byref <-- adr (base)
indir byte
lclVar byref V00 this
+ byref
const int 2 <-- mul == 4
<< int <-- op1
lclVar int V01 arg1 <-- idx
* Here, we are planning to generate the address mode [edx+4*eax], where eax = idx and edx = the GT_COMMA expression.
* To check adr equivalence with op2, we need to walk down the GT_ADD tree just like gtWalkOp() does.
*/
GenTree* Compiler::gtWalkOpEffectiveVal(GenTree* op)
{
for (;;)
{
op = op->gtEffectiveVal();
if ((op->gtOper != GT_ADD) || op->gtOverflow() || !op->gtOp.gtOp2->IsCnsIntOrI())
{
break;
}
op = op->gtOp.gtOp1;
}
return op;
}
#endif // DEBUG
/*****************************************************************************
*
* Given a tree, set the gtCostEx and gtCostSz fields which
* are used to measure the relative costs of the codegen of the tree
*
*/
void Compiler::gtPrepareCost(GenTree* tree)
{
gtSetEvalOrder(tree);
}
bool Compiler::gtIsLikelyRegVar(GenTree* tree)
{
if (tree->gtOper != GT_LCL_VAR)
{
return false;
}
assert(tree->gtLclVar.gtLclNum < lvaTableCnt);
LclVarDsc* varDsc = lvaTable + tree->gtLclVar.gtLclNum;
if (varDsc->lvDoNotEnregister)
{
return false;
}
// Be pessimistic if ref counts are not yet set up.
//
// Perhaps we should be optimistic though.
// See notes in GitHub issue 18969.
if (!lvaLocalVarRefCounted())
{
return false;
}
if (varDsc->lvRefCntWtd() < (BB_UNITY_WEIGHT * 3))
{
return false;
}
#ifdef _TARGET_X86_
if (varTypeIsFloating(tree->TypeGet()))
return false;
if (varTypeIsLong(tree->TypeGet()))
return false;
#endif
return true;
}
//------------------------------------------------------------------------
// gtCanSwapOrder: Returns true iff the secondNode can be swapped with firstNode.
//
// Arguments:
// firstNode - An operand of a tree that can have GTF_REVERSE_OPS set.
// secondNode - The other operand of the tree.
//
// Return Value:
// Returns a boolean indicating whether it is safe to reverse the execution
// order of the two trees, considering any exception, global effects, or
// ordering constraints.
//
bool Compiler::gtCanSwapOrder(GenTree* firstNode, GenTree* secondNode)
{
// Relative of order of global / side effects can't be swapped.
bool canSwap = true;
if (optValnumCSE_phase)
{
canSwap = optCSE_canSwap(firstNode, secondNode);
}
// We cannot swap in the presence of special side effects such as GT_CATCH_ARG.
if (canSwap && (firstNode->gtFlags & GTF_ORDER_SIDEEFF))
{
canSwap = false;
}
// When strict side effect order is disabled we allow GTF_REVERSE_OPS to be set
// when one or both sides contains a GTF_CALL or GTF_EXCEPT.
// Currently only the C and C++ languages allow non strict side effect order.
unsigned strictEffects = GTF_GLOB_EFFECT;
if (canSwap && (firstNode->gtFlags & strictEffects))
{
// op1 has side efects that can't be reordered.
// Check for some special cases where we still may be able to swap.
if (secondNode->gtFlags & strictEffects)
{
// op2 has also has non reorderable side effects - can't swap.
canSwap = false;
}
else
{
// No side effects in op2 - we can swap iff op1 has no way of modifying op2,
// i.e. through byref assignments or calls or op2 is a constant.
if (firstNode->gtFlags & strictEffects & GTF_PERSISTENT_SIDE_EFFECTS)
{
// We have to be conservative - can swap iff op2 is constant.
if (!secondNode->OperIsConst())
{
canSwap = false;
}
}
}
}
return canSwap;
}
/*****************************************************************************
*
* Given a tree, figure out the order in which its sub-operands should be
* evaluated. If the second operand of a binary operator is more expensive
* than the first operand, then try to swap the operand trees. Updates the
* GTF_REVERSE_OPS bit if necessary in this case.
*
* Returns the Sethi 'complexity' estimate for this tree (the higher
* the number, the higher is the tree's resources requirement).
*
* This function sets:
* 1. gtCostEx to the execution complexity estimate
* 2. gtCostSz to the code size estimate
* 3. gtRsvdRegs to the set of fixed registers trashed by the tree
* 4. gtFPlvl to the "floating point depth" value for node, i.e. the max. number
* of operands the tree will push on the x87 (coprocessor) stack. Also sets
* genFPstkLevel, tmpDoubleSpillMax, and possibly gtFPstLvlRedo.
* 5. Sometimes sets GTF_ADDRMODE_NO_CSE on nodes in the tree.
* 6. DEBUG-only: clears GTF_DEBUG_NODE_MORPHED.
*/
#ifdef _PREFAST_
#pragma warning(push)
#pragma warning(disable : 21000) // Suppress PREFast warning about overly large function
#endif
unsigned Compiler::gtSetEvalOrder(GenTree* tree)
{
assert(tree);
assert(tree->gtOper != GT_STMT);
#ifdef DEBUG
/* Clear the GTF_DEBUG_NODE_MORPHED flag as well */
tree->gtDebugFlags &= ~GTF_DEBUG_NODE_MORPHED;
#endif
/* Is this a FP value? */
bool isflt = varTypeIsFloating(tree->TypeGet());
/* Figure out what kind of a node we have */
const genTreeOps oper = tree->OperGet();
const unsigned kind = tree->OperKind();
/* Assume no fixed registers will be trashed */
regMaskTP ftreg = RBM_NONE; // Set of registers that will be used by the subtree
unsigned level;
int costEx;
int costSz;
#ifdef DEBUG
costEx = -1;
costSz = -1;
#endif
/* Is this a constant or a leaf node? */
if (kind & (GTK_LEAF | GTK_CONST))
{
switch (oper)
{
#ifdef _TARGET_ARM_
case GT_CNS_LNG:
costSz = 9;
costEx = 4;
goto COMMON_CNS;
case GT_CNS_STR:
// Uses movw/movt
costSz = 7;
costEx = 3;
goto COMMON_CNS;
case GT_CNS_INT:
{
// If the constant is a handle then it will need to have a relocation
// applied to it.
// Any constant that requires a reloc must use the movw/movt sequence
//
GenTreeIntConCommon* con = tree->AsIntConCommon();
if (con->ImmedValNeedsReloc(this) || !codeGen->validImmForInstr(INS_mov, tree->gtIntCon.gtIconVal))
{
// Uses movw/movt
costSz = 7;
costEx = 3;
}
else if (((unsigned)tree->gtIntCon.gtIconVal) <= 0x00ff)
{
// mov Rd, <const8>
costSz = 1;
costEx = 1;
}
else
{
// Uses movw/mvn
costSz = 3;
costEx = 1;
}
goto COMMON_CNS;
}
#elif defined _TARGET_XARCH_
case GT_CNS_LNG:
costSz = 10;
costEx = 3;
goto COMMON_CNS;
case GT_CNS_STR:
costSz = 4;
costEx = 1;
goto COMMON_CNS;
case GT_CNS_INT:
{
// If the constant is a handle then it will need to have a relocation
// applied to it.
//
GenTreeIntConCommon* con = tree->AsIntConCommon();
bool iconNeedsReloc = con->ImmedValNeedsReloc(this);
if (!iconNeedsReloc && con->FitsInI8())
{
costSz = 1;
costEx = 1;
}
#if defined(_TARGET_AMD64_)
else if (iconNeedsReloc || !con->FitsInI32())
{
costSz = 10;
costEx = 3;
}
#endif // _TARGET_AMD64_
else
{
costSz = 4;
costEx = 1;
}
goto COMMON_CNS;
}
#elif defined(_TARGET_ARM64_)
case GT_CNS_LNG:
case GT_CNS_STR:
case GT_CNS_INT:
// TODO-ARM64-NYI: Need cost estimates.
costSz = 1;
costEx = 1;
goto COMMON_CNS;
#else
case GT_CNS_LNG:
case GT_CNS_STR:
case GT_CNS_INT:
#error "Unknown _TARGET_"
#endif
COMMON_CNS:
/*
Note that some code below depends on constants always getting
moved to be the second operand of a binary operator. This is
easily accomplished by giving constants a level of 0, which
we do on the next line. If you ever decide to change this, be
aware that unless you make other arrangements for integer
constants to be moved, stuff will break.
*/
level = 0;
break;
case GT_CNS_DBL:
level = 0;
/* We use fldz and fld1 to load 0.0 and 1.0, but all other */
/* floating point constants are loaded using an indirection */
if ((*((__int64*)&(tree->gtDblCon.gtDconVal)) == 0) ||
(*((__int64*)&(tree->gtDblCon.gtDconVal)) == I64(0x3ff0000000000000)))
{
costEx = 1;
costSz = 1;
}
else
{
costEx = IND_COST_EX;
costSz = 4;
}
break;
case GT_LCL_VAR:
level = 1;
if (gtIsLikelyRegVar(tree))
{
costEx = 1;
costSz = 1;
/* Sign-extend and zero-extend are more expensive to load */
if (lvaTable[tree->gtLclVar.gtLclNum].lvNormalizeOnLoad())
{
costEx += 1;
costSz += 1;
}
}
else
{
costEx = IND_COST_EX;
costSz = 2;
/* Sign-extend and zero-extend are more expensive to load */
if (varTypeIsSmall(tree->TypeGet()))
{
costEx += 1;
costSz += 1;
}
}
#if defined(_TARGET_AMD64_)
// increase costSz for floating point locals
if (isflt)
{
costSz += 1;
if (!gtIsLikelyRegVar(tree))
{
costSz += 1;
}
}
#endif
break;
case GT_CLS_VAR:
#ifdef _TARGET_ARM_
// We generate movw/movt/ldr
level = 1;
costEx = 3 + IND_COST_EX; // 6
costSz = 4 + 4 + 2; // 10
break;
#endif
case GT_LCL_FLD:
level = 1;
costEx = IND_COST_EX;
costSz = 4;
if (varTypeIsSmall(tree->TypeGet()))
{
costEx += 1;
costSz += 1;
}
break;
case GT_PHI_ARG:
case GT_ARGPLACE:
level = 0;
costEx = 0;
costSz = 0;
break;
default:
level = 1;
costEx = 1;
costSz = 1;
break;
}
goto DONE;
}
/* Is it a 'simple' unary/binary operator? */
if (kind & GTK_SMPOP)
{
int lvlb; // preference for op2
unsigned lvl2; // scratch variable
GenTree* op1 = tree->gtOp.gtOp1;
GenTree* op2 = tree->gtGetOp2IfPresent();
costEx = 0;
costSz = 0;
if (tree->OperIsAddrMode())
{
if (op1 == nullptr)
{
op1 = op2;
op2 = nullptr;
}
}
/* Check for a nilary operator */
if (op1 == nullptr)
{
assert(op2 == nullptr);
level = 0;
goto DONE;
}
/* Is this a unary operator? */
if (op2 == nullptr)
{
/* Process the operand of the operator */
/* Most Unary ops have costEx of 1 */
costEx = 1;
costSz = 1;
level = gtSetEvalOrder(op1);
ftreg |= op1->gtRsvdRegs;
/* Special handling for some operators */
switch (oper)
{
case GT_JTRUE:
costEx = 2;
costSz = 2;
break;
case GT_SWITCH:
costEx = 10;
costSz = 5;
break;
case GT_CAST:
#if defined(_TARGET_ARM_)
costEx = 1;
costSz = 1;
if (isflt || varTypeIsFloating(op1->TypeGet()))
{
costEx = 3;
costSz = 4;
}
#elif defined(_TARGET_ARM64_)
costEx = 1;
costSz = 2;
if (isflt || varTypeIsFloating(op1->TypeGet()))
{
costEx = 2;
costSz = 4;
}
#elif defined(_TARGET_XARCH_)
costEx = 1;
costSz = 2;
if (isflt || varTypeIsFloating(op1->TypeGet()))
{
/* cast involving floats always go through memory */
costEx = IND_COST_EX * 2;
costSz = 6;
}
#else
#error "Unknown _TARGET_"
#endif
/* Overflow casts are a lot more expensive */
if (tree->gtOverflow())
{
costEx += 6;
costSz += 6;
}
break;
case GT_LIST:
case GT_FIELD_LIST:
case GT_NOP:
costEx = 0;
costSz = 0;
break;
case GT_INTRINSIC:
// GT_INTRINSIC intrinsics Sin, Cos, Sqrt, Abs ... have higher costs.
// TODO: tune these costs target specific as some of these are
// target intrinsics and would cost less to generate code.
switch (tree->gtIntrinsic.gtIntrinsicId)
{
default:
assert(!"missing case for gtIntrinsicId");
costEx = 12;
costSz = 12;
break;
case CORINFO_INTRINSIC_Sin:
case CORINFO_INTRINSIC_Cos:
case CORINFO_INTRINSIC_Sqrt:
case CORINFO_INTRINSIC_Cbrt:
case CORINFO_INTRINSIC_Cosh:
case CORINFO_INTRINSIC_Sinh:
case CORINFO_INTRINSIC_Tan:
case CORINFO_INTRINSIC_Tanh:
case CORINFO_INTRINSIC_Asin:
case CORINFO_INTRINSIC_Asinh:
case CORINFO_INTRINSIC_Acos:
case CORINFO_INTRINSIC_Acosh:
case CORINFO_INTRINSIC_Atan:
case CORINFO_INTRINSIC_Atanh:
case CORINFO_INTRINSIC_Atan2:
case CORINFO_INTRINSIC_Log10:
case CORINFO_INTRINSIC_Pow:
case CORINFO_INTRINSIC_Exp:
case CORINFO_INTRINSIC_Ceiling:
case CORINFO_INTRINSIC_Floor:
case CORINFO_INTRINSIC_Object_GetType:
// Giving intrinsics a large fixed execution cost is because we'd like to CSE
// them, even if they are implemented by calls. This is different from modeling
// user calls since we never CSE user calls.
costEx = 36;
costSz = 4;
break;
case CORINFO_INTRINSIC_Abs:
costEx = 5;
costSz = 15;
break;
case CORINFO_INTRINSIC_Round:
costEx = 3;
costSz = 4;
break;
}
level++;
break;
case GT_NOT:
case GT_NEG:
// We need to ensure that -x is evaluated before x or else
// we get burned while adjusting genFPstkLevel in x*-x where
// the rhs x is the last use of the enregistered x.
//
// Even in the integer case we want to prefer to
// evaluate the side without the GT_NEG node, all other things
// being equal. Also a GT_NOT requires a scratch register
level++;
break;
case GT_ADDR:
costEx = 0;
costSz = 1;
// If we have a GT_ADDR of an GT_IND we can just copy the costs from indOp1
if (op1->OperGet() == GT_IND)
{
GenTree* indOp1 = op1->gtOp.gtOp1;
costEx = indOp1->gtCostEx;
costSz = indOp1->gtCostSz;
}
break;
case GT_ARR_LENGTH:
level++;
/* Array Len should be the same as an indirections, which have a costEx of IND_COST_EX */
costEx = IND_COST_EX - 1;
costSz = 2;
break;
case GT_MKREFANY:
case GT_OBJ:
// We estimate the cost of a GT_OBJ or GT_MKREFANY to be two loads (GT_INDs)
costEx = 2 * IND_COST_EX;
costSz = 2 * 2;
break;
case GT_BOX:
// We estimate the cost of a GT_BOX to be two stores (GT_INDs)
costEx = 2 * IND_COST_EX;
costSz = 2 * 2;
break;
case GT_BLK:
case GT_IND:
/* An indirection should always have a non-zero level.
* Only constant leaf nodes have level 0.
*/
if (level == 0)
{
level = 1;
}
/* Indirections have a costEx of IND_COST_EX */
costEx = IND_COST_EX;
costSz = 2;
/* If we have to sign-extend or zero-extend, bump the cost */
if (varTypeIsSmall(tree->TypeGet()))
{
costEx += 1;
costSz += 1;
}
if (isflt)
{
if (tree->TypeGet() == TYP_DOUBLE)
{
costEx += 1;
}
#ifdef _TARGET_ARM_
costSz += 2;
#endif // _TARGET_ARM_
}
// Can we form an addressing mode with this indirection?
// TODO-CQ: Consider changing this to op1->gtEffectiveVal() to take into account
// addressing modes hidden under a comma node.
if (op1->gtOper == GT_ADD)
{
bool rev;
#if SCALED_ADDR_MODES
unsigned mul;
#endif // SCALED_ADDR_MODES
ssize_t cns;
GenTree* base;
GenTree* idx;
// See if we can form a complex addressing mode.
GenTree* addr = op1->gtEffectiveVal();
bool doAddrMode = true;
// See if we can form a complex addressing mode.
// Always use an addrMode for an array index indirection.
// TODO-1stClassStructs: Always do this, but first make sure it's
// done in Lowering as well.
if ((tree->gtFlags & GTF_IND_ARR_INDEX) == 0)
{
if (tree->TypeGet() == TYP_STRUCT)
{
doAddrMode = false;
}
else if (varTypeIsStruct(tree))
{
// This is a heuristic attempting to match prior behavior when indirections
// under a struct assignment would not be considered for addressing modes.
if (compCurStmt != nullptr)
{
GenTree* expr = compCurStmt->gtStmt.gtStmtExpr;
if ((expr->OperGet() == GT_ASG) &&
((expr->gtGetOp1() == tree) || (expr->gtGetOp2() == tree)))
{
doAddrMode = false;
}
}
}
}
if ((doAddrMode) &&
codeGen->genCreateAddrMode(addr, // address
false, // fold
&rev, // reverse ops
&base, // base addr
&idx, // index val
#if SCALED_ADDR_MODES
&mul, // scaling
#endif // SCALED_ADDR_MODES
&cns)) // displacement
{
// We can form a complex addressing mode, so mark each of the interior
// nodes with GTF_ADDRMODE_NO_CSE and calculate a more accurate cost.
addr->gtFlags |= GTF_ADDRMODE_NO_CSE;
#ifdef _TARGET_XARCH_
// addrmodeCount is the count of items that we used to form
// an addressing mode. The maximum value is 4 when we have
// all of these: { base, idx, cns, mul }
//
unsigned addrmodeCount = 0;
if (base)
{
costEx += base->gtCostEx;
costSz += base->gtCostSz;
addrmodeCount++;
}
if (idx)
{
costEx += idx->gtCostEx;
costSz += idx->gtCostSz;
addrmodeCount++;
}
if (cns)
{
if (((signed char)cns) == ((int)cns))
{
costSz += 1;
}
else
{
costSz += 4;
}
addrmodeCount++;
}
if (mul)
{
addrmodeCount++;
}
// When we form a complex addressing mode we can reduced the costs
// associated with the interior GT_ADD and GT_LSH nodes:
//
// GT_ADD -- reduce this interior GT_ADD by (-3,-3)
// / \ --
// GT_ADD 'cns' -- reduce this interior GT_ADD by (-2,-2)
// / \ --
// 'base' GT_LSL -- reduce this interior GT_LSL by (-1,-1)
// / \ --
// 'idx' 'mul'
//
if (addrmodeCount > 1)
{
// The number of interior GT_ADD and GT_LSL will always be one less than addrmodeCount
//
addrmodeCount--;
GenTree* tmp = addr;
while (addrmodeCount > 0)
{
// decrement the gtCosts for the interior GT_ADD or GT_LSH node by the remaining
// addrmodeCount
tmp->SetCosts(tmp->gtCostEx - addrmodeCount, tmp->gtCostSz - addrmodeCount);
addrmodeCount--;
if (addrmodeCount > 0)
{
GenTree* tmpOp1 = tmp->gtOp.gtOp1;
GenTree* tmpOp2 = tmp->gtGetOp2();
assert(tmpOp2 != nullptr);
if ((tmpOp1 != base) && (tmpOp1->OperGet() == GT_ADD))
{
tmp = tmpOp1;
}
else if (tmpOp2->OperGet() == GT_LSH)
{
tmp = tmpOp2;
}
else if (tmpOp1->OperGet() == GT_LSH)
{
tmp = tmpOp1;
}
else if (tmpOp2->OperGet() == GT_ADD)
{
tmp = tmpOp2;
}
else
{
// We can very rarely encounter a tree that has a GT_COMMA node
// that is difficult to walk, so we just early out without decrementing.
addrmodeCount = 0;
}
}
}
}
#elif defined _TARGET_ARM_
if (base)
{
costEx += base->gtCostEx;
costSz += base->gtCostSz;
if ((base->gtOper == GT_LCL_VAR) && ((idx == NULL) || (cns == 0)))
{
costSz -= 1;
}
}
if (idx)
{
costEx += idx->gtCostEx;
costSz += idx->gtCostSz;
if (mul > 0)
{
costSz += 2;
}
}
if (cns)
{
if (cns >= 128) // small offsets fits into a 16-bit instruction
{
if (cns < 4096) // medium offsets require a 32-bit instruction
{
if (!isflt)
costSz += 2;
}
else
{
costEx += 2; // Very large offsets require movw/movt instructions
costSz += 8;
}
}
}
#elif defined _TARGET_ARM64_
if (base)
{
costEx += base->gtCostEx;
costSz += base->gtCostSz;
}
if (idx)
{
costEx += idx->gtCostEx;
costSz += idx->gtCostSz;
}
if (cns != 0)
{
if (cns >= (4096 * genTypeSize(tree->TypeGet())))
{
costEx += 1;
costSz += 4;
}
}
#else
#error "Unknown _TARGET_"
#endif
assert(addr->gtOper == GT_ADD);
assert(!addr->gtOverflow());
assert(op2 == nullptr);
assert(mul != 1);
// If we have an addressing mode, we have one of:
// [base + cns]
// [ idx * mul ] // mul >= 2, else we would use base instead of idx
// [ idx * mul + cns] // mul >= 2, else we would use base instead of idx
// [base + idx * mul ] // mul can be 0, 2, 4, or 8
// [base + idx * mul + cns] // mul can be 0, 2, 4, or 8
// Note that mul == 0 is semantically equivalent to mul == 1.
// Note that cns can be zero.
CLANG_FORMAT_COMMENT_ANCHOR;
#if SCALED_ADDR_MODES
assert((base != nullptr) || (idx != nullptr && mul >= 2));
#else
assert(base != NULL);
#endif
INDEBUG(GenTree* op1Save = addr);
// Walk 'addr' identifying non-overflow ADDs that will be part of the address mode.
// Note that we will be modifying 'op1' and 'op2' so that eventually they should
// map to the base and index.
op1 = addr;
gtWalkOp(&op1, &op2, base, false);
// op1 and op2 are now descendents of the root GT_ADD of the addressing mode.
assert(op1 != op1Save);
assert(op2 != nullptr);
// Walk the operands again (the third operand is unused in this case).
// This time we will only consider adds with constant op2's, since
// we have already found either a non-ADD op1 or a non-constant op2.
gtWalkOp(&op1, &op2, nullptr, true);
#if defined(_TARGET_XARCH_)
// For XARCH we will fold GT_ADDs in the op2 position into the addressing mode, so we call
// gtWalkOp on both operands of the original GT_ADD.
// This is not done for ARMARCH. Though the stated reason is that we don't try to create a
// scaled index, in fact we actually do create them (even base + index*scale + offset).
// At this point, 'op2' may itself be an ADD of a constant that should be folded
// into the addressing mode.
// Walk op2 looking for non-overflow GT_ADDs of constants.
gtWalkOp(&op2, &op1, nullptr, true);
#endif // defined(_TARGET_XARCH_)
// OK we are done walking the tree
// Now assert that op1 and op2 correspond with base and idx
// in one of the several acceptable ways.
// Note that sometimes op1/op2 is equal to idx/base
// and other times op1/op2 is a GT_COMMA node with
// an effective value that is idx/base
if (mul > 1)
{
if ((op1 != base) && (op1->gtOper == GT_LSH))
{
op1->gtFlags |= GTF_ADDRMODE_NO_CSE;
if (op1->gtOp.gtOp1->gtOper == GT_MUL)
{
op1->gtOp.gtOp1->gtFlags |= GTF_ADDRMODE_NO_CSE;
}
assert((base == nullptr) || (op2 == base) ||
(op2->gtEffectiveVal() == base->gtEffectiveVal()) ||
(gtWalkOpEffectiveVal(op2) == gtWalkOpEffectiveVal(base)));
}
else
{
assert(op2);
assert(op2->gtOper == GT_LSH || op2->gtOper == GT_MUL);
op2->gtFlags |= GTF_ADDRMODE_NO_CSE;
// We may have eliminated multiple shifts and multiplies in the addressing mode,
// so navigate down through them to get to "idx".
GenTree* op2op1 = op2->gtOp.gtOp1;
while ((op2op1->gtOper == GT_LSH || op2op1->gtOper == GT_MUL) && op2op1 != idx)
{
op2op1->gtFlags |= GTF_ADDRMODE_NO_CSE;
op2op1 = op2op1->gtOp.gtOp1;
}
assert(op1->gtEffectiveVal() == base);
assert(op2op1 == idx);
}
}
else
{
assert(mul == 0);
if ((op1 == idx) || (op1->gtEffectiveVal() == idx))
{
if (idx != nullptr)
{
if ((op1->gtOper == GT_MUL) || (op1->gtOper == GT_LSH))
{
if ((op1->gtOp.gtOp1->gtOper == GT_NOP) ||
(op1->gtOp.gtOp1->gtOper == GT_MUL &&
op1->gtOp.gtOp1->gtOp.gtOp1->gtOper == GT_NOP))
{
op1->gtFlags |= GTF_ADDRMODE_NO_CSE;
if (op1->gtOp.gtOp1->gtOper == GT_MUL)
{
op1->gtOp.gtOp1->gtFlags |= GTF_ADDRMODE_NO_CSE;
}
}
}
}
assert((op2 == base) || (op2->gtEffectiveVal() == base));
}
else if ((op1 == base) || (op1->gtEffectiveVal() == base))
{
if (idx != nullptr)
{
assert(op2);
if ((op2->gtOper == GT_MUL) || (op2->gtOper == GT_LSH))
{
if ((op2->gtOp.gtOp1->gtOper == GT_NOP) ||
(op2->gtOp.gtOp1->gtOper == GT_MUL &&
op2->gtOp.gtOp1->gtOp.gtOp1->gtOper == GT_NOP))
{
op2->gtFlags |= GTF_ADDRMODE_NO_CSE;
if (op2->