We now update pred lists during loop unrolling, rather than recomputing
them from scratch.

There are several parts to the fix: first, `optRedirectBlock' now has
a new ability to add pred references for the flow from a newly cloned
block, be it either to a remapped successor or a non-remapped successor.
Along with this we no longer copy over the block ref count in `CloneBlockState`.
These changes allow us to create the right pred links and ref counts in the
interior of a cloned subgraph.

Second, we now scrub block references from the original loop body blocks
instead of just setting their ref counts to zero.

Finally, we fix up references for exterior flow into and out of the unroll
complex.

Addresses one of the cases mentioned in #49030.

* Remove quirks

* Early prop fix for call asgs

* Include all tracked locals in SSA

* Remove a (now incorrect) comment

* Fix a typo

* Encoding fixes

 1) The definition of SIMPLE_NUM_COUNT was wrong.
 2) SsaNumInfo::Composite, in the compact case, did not clear the old value.
 3) SsaNumInfo::Composite, in the outlined case, did not copy the already
    (compactly) encoded simple names.

* Fix store numbering

The load path needs to use the offset relative to
the store's target location.

* Clarify 'fieldValueOffset' calculations

Record some information about each SSA def and try and keep it conservatively
correct through the first few optimization phases.

We note:
* total number of uses
* whether all uses are in the same block as the def
* whether there are any phi uses

Subsequent phases that introduce new uses must now call `optRecordSsaUses` on
the new trees they create to update these accounts.

This information is cross-checked versus the IR in post phase checking.
Because we don't have a well-defined mechanism to track when nodes are deleted
the recorded counts may end up being overestimates in subsequent phases. This is
ok, but underestimates are flagged as errors.

* Change how we track use SSA numbers for partial defs

Store them in the SSA descriptor instead of a map.

Memory (x64): +0.18%
PIN    (x64): -0.04%

The memory regression is not small...

* SsaNumInfo support

* Support in SSA, VN and CopyProp

For now, just the "CanBeReplacedWithItsField" case.
This enables some nice simplifications, even as the
general case gets more complex.

Two quirks have been added to attain zero diffs.

* Support in dumping

* TP tuning

Gets us back 0.05% on the PIN counter. Hard to believe but true.

* More TP tuning

Another 0.025%.

We used to exclude locals with the flag set from SSA; this should no longer be necessary.

Add loop table checking to the post-phase list, conditional on whether the
table is expected to be valid.

Declare that the table is valid from the end of the find loops phase to the
end of the optimization phases.

Add checks that sibling loops are fully disjoint, no child shares top with its
parent, and all top-entry loops have at most one non-loop backedge.

Expand set of phases that opt into the "common" poost phase checks
to include all those between find loops and hoisting.

Closes #71084.
Closes #71071.

* Do not add casts on top of CLS_VAR

ApplySelectorsTypeCheck already adds the cast in case it
is necessary, and VN does support small-typed operands.

* Stop generating CLS_VAR

* Delete CLS_VAR

* Preliminary changes

* Add the missing push of ssadef

* Fix an issue for call tree cloning

* formatting

* minor review comments incorporation

* Make GT_CALL as full-def

* Merge RenameCall into RenameDef

* Fix DefinesLocalAddr and lateuse arg

* Minor comments

* fix the recently added code to account that GT_CALL can also have defintion:

* clone the return buffer arg

* Another round of review comments

* Handle return buffer calls in optIsVarAssgCB

* Update locals defined by calls in NodeInfo

* Fix a case where arg can be putarg

* Restructure the cases in GetLclRetBufArgNode()

* move ivaMaskCall outside the condition

* Add back to call for DoNotEnregister which was missed for Release builds

* Retrieve the appropriate node in case of copyReload

* Added an assert

* remove assert and add comment

* Import GT_STORE_DYN_BLK directly

* Delete GT_DYN_BLK

* DynBlk -> StoreDynBlk

* Add some tests

* Mark tests Pri-1

* Rebase and fix build

* Bring back the odd early return

* Generalize loop pre-header creation and loop hoisting

A loop pre-header is a block that flows directly (and only) to the loop entry
block. The loop pre-header is the only non-loop predecessor of the entry block.
Loop invariant code can be hoisted to the loop pre-header where it is
guaranteed to be executed just once (per loop entry).

Currently, a loop pre-header has a number of restrictions:
- it is only created for a "do-while" (top entry) loop, not for a mid-loop entry.
- it isn't created if the current loop head and the loop entry block are in
different EH try regions

Additionally, partially due those restrictions, loop hoisting has restrictions:
- it requires a "do-while" (top entry) loop
- it requires the existing `head` block to dominate the loop entry block
- it requires the existing `head` block to be in the same EH region as the entry block
- it won't hoist if the `entry` block is the first block of a handler

This change removes all these restrictions.

Previously, even if we did create a pre-header, the definition of a pre-header
was a little weaker: an entry predecessor could be a non-loop block and also
not the pre-header, if the predecessor was dominated by the entry block. This
is more complicated to reason about, so I change the pre-header creation to
force entry block non-loop predecessors to branch to the pre-header instead.
This case only rarely occurs, when we have what looks like an outer loop back
edge but the natural loop recognition package doesn't recognize it as an outer loop.

I added a "stress mode" to always create a loop pre-header immediately after
loop recognition. This is disabled currently because loop cloning doesn't
respect the special status and invariants of a pre-header, and so inserts
all the cloning conditions and copied blocks after the pre-header, triggering
new loop structure asserts. This should be improved in the future.

A lot more checking of the loop table and loop annotations on blocks has been
added. This revealed a number of problems with loop unrolling leaving things
in a bad state for downstream phases. Loop unrolling has been updated to fix
this, in particular, the loop table is rebuilt if it is detected that we unroll
a loop that contains nested loops, since there will now be multiple copies of
those nested loops. This is the first case where we might rebuild the loop
table, so it lays the groundwork for potentially rebuilding the loop table in
other cases, such as after loop cloning where we don't add the "slow path"
loops to the table.

There is some code refactoring to simplify the "find loops" code as well.

Some change details:
- `optSetBlockWeights` is elevated to a "phase" that runs prior to loop recognition.
- LoopFlags is simplified:
	- LPFLG_DO_WHILE is removed; call `lpIsTopEntry` instead
	- LPFLG_ONE_EXIT is removed; check `lpExitCnt == 1` instead
	- LPFLG_HOISTABLE is removed (there are no restrictions anymore)
	- LPFLG_CONST is removed: check `lpFlags & (LPFLG_CONST_INIT | LPFLG_CONST_LIMIT) == (LPFLG_CONST_INIT | LPFLG_CONST_LIMIT)` instead (only used in one place
	- bool lpContainsCall is removed and replaced by LPFLG_CONTAINS_CALL
- Added a `lpInitBlock` field to the loop table. For constant and variable
initialization loops, code assumed that these expressions existed in the
`head` block. This isn't true anymore if we insert a pre-header block.
So, capture the block where these actually exist when we determine that
they do exist, and explicitly use this block pointer where needed.
- Added `fgComputeReturnBlocks()` to extract this code out of `fgComputeReachability` into a function
- Added `optFindAndScaleGeneralLoopBlocks()` to extract this out of loop recognition to its own function.
- Added `optResetLoopInfo()` to reset the loop table and block annotations related to loops
- Added `fgDebugCheckBBNumIncreasing()` to allow asserting that the bbNum
order of blocks is increasing. This should be used in phases that depend
on this order to do bbNum comparisons.
- Add a lot more loop table validation in `fgDebugCheckLoopTable()`

* Inline fgBuildBlockNumMap to allow using _alloca

* Fix BBJ_SWITCH output

1. Change `dspSuccs()` to not call code that will call `GetDescriptorForSwitch()`
2. Change `GetDescriptorForSwitch()` to use the correct max block number while
inlining. We probably don't or shouldn't call GetDescriptorForSwitch while inlining,
especially after (1), but this change doesn't hurt.

* Remove incorrect assertion

There was an assertion when considering an existing `head` block as
a potential pre-header, that the `entry` block have the `head`
block as a predecessor. However, we early exit if we find a non-head,
non-loop edge. This could happen before we encounter the `head` block,
making the assert incorrect. We don't want to run the entire loop just
for the purpose of the assert (at least not here), so just remove the
assert.

* Formatting

* Use `_alloca` instead of `alloca` name

* Convert fgBBNumMax usage

Change:
```
compIsForInlining() ? impInlineInfo->InlinerCompiler->fgBBNumMax : fgBBNumMax
```
to:
```
impInlineRoot()->fgBBNumMax
```

* Code review feedback

1. Added loop epoch concept. Currently set but never checked.
2. Added disabled assert about return blocks always being moved
out of line of loop body.
3. Fixed bug checking `totalIter` after it was decremented to zero
as a loop variable
4. Added more comments on incremental loop block `bbNatLoopNum`
setting.

* Add EH condition when converting head to pre-header

When considering converting an existing loop `head` block to a pre-header,
verify that the block has the same EH try region that we would create
for a new pre-header. If not, we go ahead and create the new pre-header.

Including the version with a `GenTreeLclVarCommon*` overload.

I mostly replaced `&lvaTable[varNum]` and `lvaTable + varNum`
expressions, leaving `lvaTable[varNum].xxx`.

Made many resulting `varDsc*` const.

Removed unused `lvaRefCount`.

Simplifies code, and centralizes assert checking.

Added new `lvaGetLclNum(LclVarDsc*)` function to map back to a varNum.

This deletes many `noway_assert` in favor of the lvaGetDesc `assert`;
I'm not worried about removing asserts from the Release build.

* Add `JitEnregStats` complus.

* review response.

* response review 2.

* add a space

* fix printing/sorting

* fix merge conflicts

* format
Co-authored-by: NSergey <seandree@microsoft.com>

Add more iterators compatible with range-based `for` syntax for various data structures. These iterators all assume (and some check) that the underlying data structures determining the iteration are not changed during the iteration. For example, don't use these to iterate over the predecessor edges if you are changing the order or contents of the predecessor edge list.

- BasicBlock: iterate over all blocks in the function, a subset starting not at the first block, or a specified range of blocks. Removed uses of the `foreach_block` macro. E.g.:
```
for (BasicBlock* const block : Blocks()) // all blocks in function
for (BasicBlock* const block : BasicBlockSimpleList(fgFirstBB->bbNext)) // all blocks starting at fgFirstBB->bbNext
for (BasicBlock* const testBlock : BasicBlockRangeList(firstNonLoopBlock, lastNonLoopBlock)) // all blocks in range (inclusive)
```

- block predecessors: iterate over all predecessor edges, or all predecessor blocks, e.g.:
```
for (flowList* const edge : block->PredEdges())
for (BasicBlock* const predBlock : block->PredBlocks())
```

- block successors: iterate over all block successors using the `NumSucc()/GetSucc()`, or `NumSucc(Compiler*)/GetSucc(Compiler*)` pairs, e.g.:
```
for (BasicBlock* const succ : Succs())
for (BasicBlock* const succ : Succs(compiler))
```
Note that there already exists the "AllSuccessorsIter" which iterates over block successors including possible EH successors, e.g.:
```
for (BasicBlock* succ : block->GetAllSuccs(m_pCompiler))
```

- switch targets, (namely, the successors of `BBJ_SWITCH` blocks), e.g.:
```
for (BasicBlock* const bTarget : block->SwitchTargets())
```

- loops blocks: iterate over all the blocks in a loop, e.g.:
```
for (BasicBlock* const blk : optLoopTable[loopInd].LoopBlocks())
```

- Statements: added an iterator shortcut for the non-phi statements, e.g.:
```
for (Statement* const stmt : block->NonPhiStatements())
```
Note that there already exists an iterator over all statements, e.g.:
```
for (Statement* const stmt : block->Statements())
```

- EH clauses, e.g.:
```
for (EHblkDsc* const HBtab : EHClauses(this))
```

- GenTree in linear order (but not LIR, which already has an iterator), namely, using the `gtNext` links, e.g.:
```
for (GenTree* const call : stmt->TreeList())
```

This is a no-diff change.

Whenever blocks are renumbered or a block is swapped into an existing
pred list entry, ensure the pred list remains properly ordered.

Closes #8720.

December infra rollout - remove duplicated 'src' from coreclr subrepo (src/coreclr/src becomes src/coreclr) (#44973)

* Move src/coreclr/src/Directory.Build.targets to src/coreclr
Merge src/coreclr/src/CMakeLists.txt into src/coreclr/CMakeLists.txt

* Mechanical move of src/coreclr/src to src/coreclr

* Scripts adjustments to reflect the changed paths

* s/MscorlibBinder/CoreLibBinder/

* s/g_Mscorlib/g_CoreLib/

* Remaining mscorlib->corelib renames

* Delete unreachable FNV NGen string

* Disable retyping by default.

* Keep block init/copy as baseline.

Total bytes of diff: -21971 (-0.07% of base)
3075 total methods with Code Size differences (1589 improved, 1486 regressed), 184523 unchanged.

Note: it improves code with retyping as well:
808 total methods with Code Size differences (808 improved, 0 regressed), 186790 unchanged.
Found 55 files with textual diffs.
Crossgen CodeSize Diffs for System.Private.CoreLib.dll, framework assemblies for  default jit
Summary of Code Size diffs:
(Lower is better)
Total bytes of diff: -22923 (-0.07% of base)

* Don't mark LCL_VAR that is used in RETURN(IND(ADDR(LCL_VAR)) as address taken when possible.

Protect against a promoted struct with a hole like struct<8> {hole 4; int a;};

* Replace 1-field structs with the field for returns.

* Add SSA support.

* Review response.

* isOpaqueSIMDLclVar fix

* Add tests for structs with independently promoted SIMD fields.

* Old retyping fix.

* Don't try to replace SIMD fields.

1. Don't mark fields of dependently promoted structs as untracked.

2. Remove some stores whose lhs local has a ref count of 1 when running
late liveness. We can rely on ref counts since they are calculated right
before the late liveness pass.

3. Remove dead GT_STORE_BLK in addition to GT_STOREIND in the late
liveness pass.

4. Remove dead stores to untracked locals in the late liveness pass.

5. Allow optRemoveRedundantZeroInits to remove some redundant initializations
of tracked locals. Move the phase to right after liveness so that SSA is correct
after removing assignments to tracked locals.

This is a zero-diff set of mostly refactoring changes in preparation for supporting multireg locals:
- Move `genRegCopy()` and `genStructReturn()` to codegencommon.cpp, making a new method for `genSIMDSplitReturn` which is target-specific.
- Factor out a new `genUnspillLocal` method from `genUnspillRegIfNeeded()`.
- Similarly factor out `genSpillLocal()`
- Rename `genMultiRegCallStoreToLocal()` and more generally support multireg local stores.
- Fix a bug in the order and shift amount for last-use bits on `GenTreeLclVar`
- Some additional cleanup and preparatory changes

And if so, remove `GTF_VAR_USEASG`.

Fixes #31615.

* Delete unused SsaBuilder code

* Delete BasicBlock::bbDfsNum

bbPostOrderNum serves the same purpose

* Improve dominator tree building & walking
- Change the dominator tree data structure to a simple array of nodes
- Adapt fgBuildDomTree so it can be used by SsaBuilder
- Add a dominator tree visitor class
- Reuse the dominator tree built by SsaBuilder for copy propagation

* Move bbNatLoopNum to fill a padding hole


Commit migrated from https://github.com/dotnet/coreclr/commit/9251ceff0395f989253b7874862feb396b7bddd3

SSA defs used to point at LHS of GT_ASG. Many clients immediately needed to walk up the tree to the parent to find the GT_ASG. So revise the SSA def to just be the GT_ASG.

Also, reject non-LCL_VAR definitions in RangeCheck. This matches the previous behavior that rejected LHS nodes that weren't the direct descendant of the ASG node - basically cases like ASG(IND(ADDR(LCL_VAR)), x). RangeCheck doesn't have the ability to follow such definitions.

This also happens to reject LCL_FLD nodes as LHS. The machinery required to follow definition chains involving struct copies and field access is quite a bit more complicated and RangeCheck certainly doesn't have it.


Commit migrated from https://github.com/dotnet/coreclr/commit/1b12053ffffc36ad73ad83f7ce111c891c4cf457

Remove gcc nonnull-compare suppression and impossible conditions.

> error: nonnull argument 'this' compared to NULL
> [-Werror=nonnull-compare]

Commit migrated from https://github.com/dotnet/coreclr/commit/4afbe3a43814803bcdc1cefb1e2f2792257cf02f

* find src/jit -type f -exec sed -i -e 's/gtLclVarCommon\./AsLclVarCommon()\./g' {} \;

gtLclVarCommon

* Format patch

* Format patch

* Format patch dotnet/coreclr#3

* Remove redundant /


Commit migrated from https://github.com/dotnet/coreclr/commit/5e231b5b5bced3e3548159fd79c4036fde4f135f

* find src/jit -type f -exec sed -i -e 's/gtLclVar\./AsLclVar()\./g' {} \;

AsClsVar and AsArrElem

* Format patch


Commit migrated from https://github.com/dotnet/coreclr/commit/9fff11771055eec97c4f9769d1a2f97ff796ac6a

* Replace gt## with Get##

* Format patch

* minor cleanups


Commit migrated from https://github.com/dotnet/coreclr/commit/fd0ca99c4214538de6f821db6a38c9b6aca5ee62

* Delete a leftover for STMT and update dump examples.

* Prepare `GetNextStmt` and `GetPrevStmt` to be used as main read accesors.

* Rename `Statement->gtNext` to `m_nextStmt` and make private.

* Rename `Statement->gtPrev` to `m_prev` and make private.

* Rename `gtStmtLastILoffs` to `m_lastILOffset` and make it private.

* Rename `gtStmtILoffsx` to `m_ILOffsetX` and make it private.

* Rename `compilerAdded` to `m_compilerAdded` and make it private.

* Rename `gtInlineContext` to `m_inlineContext` and make it private.

* Rename `gtStmtList` to `m_treeList` and make it private.

* Rename `gtStmtExpr` to `m_rootTree` and make it private.

* Update the class layout acording to our spec.

* Update the docs.

* Delete another forgotten line.

* Rename `m_rootTree` to `m_TreeRoot`.

Keep it consistent with `m_treeList` .

* Rename `m_TreeRoot` to `m_rootNode`.

* Add comments.


Commit migrated from https://github.com/dotnet/coreclr/commit/e0f4a6477f1656648f3469adf4a1d0bbc1c1e60d

* find src/jit -type f -exec sed -i -e 's/->gtLclNum/->GetLclNum()/g' {} \;

GetLclNum

GetLclNum

compile fixes

* Format patch


Commit migrated from https://github.com/dotnet/coreclr/commit/c8ad76dd8169238c085ee6e3f03d074aed4b76b2

* find ./ -type f -exec sed -i -e 's/\<gtSsaNum\>/GetSsaNum()/g' {} \;

* format patch


Commit migrated from https://github.com/dotnet/coreclr/commit/eeea730d09d5a7eeaf8c5bb036319ebec85819ea

* Rename `GenTreeStmt` to `Statement`.

* Move `Statements::IsPhiDefnStmt` implementation to the header.

* Add iterators for statements.

So we have less places where we access Statement's fields.

* Add a header for `fgInsertStmtListAfter`,

# Conflicts:
#	src/jit/flowgraph.cpp

* Change `fgInsertStmtAtBeg` not to return a value.

and add headers for `fgInsertStmtAtBeg` and `fgNewStmtAtBeg`.

* Change `fgInsertStmtBefore` and `fgInsertStmtAfter` not to return.

* Change `fgInsertStmtNearEnd` not to return.

* Change `fgInsertStmtAtEnd` not to return.

# Conflicts:
#	src/jit/flowgraph.cpp

* Fix comments.

* Add a header for `gtDispBlockStmts`.


Commit migrated from https://github.com/dotnet/coreclr/commit/ef585a4658a830945f24d635b234f44bd0c81e84

* Add tracked variable accessor functions

* Delete bogus lvaSortByRefCount call

There's no need to sort at the end of lvaMarkLocalVars. Tracked variables aren't needed until liveness and that does its own sort call.

* Replace qsort with (jit)std::sort

qsort is rather cumbersome to use and inefficient. It's not a template
so it operates with void pointers that can make swapping problematic.
The comparison callback is unnecessarily complex because it has to return
-1,0,+1 when "less" style comparison functions only return true/false.
It's also impossible to inline the callback, even if it's a trivial
"return a < b;" function.

* Get rid of lvaRefSorted

While it could be slightly faster than lvaTrackedToVarNum because it stores
pointers rather than indices, it also uses more memory and it's not safe to
use beyond sorting. If new variables are added the variable table may have
to be resized and that invalidates the stored pointers.

At the same time, stop sorting untracked variables, nothing in the JIT needs
that. Collect only tracked variables in lvaTrackedToVarNum, sort them and
then "untrack" the ones that exceed the lclMAX_TRACKED limit.

* Remove bogus lvRegister checks

Variables are not sorted after LSRA has ran so these checks are not needed.

* Turn RefCntCmp/WtdRefCntCmp into real "less"

* Use functors rather than lambdas

It's too much code to put it all in the lambda so we might as well go the other way and get rid of the lambda.

* Add some comments to sort functions

* Fix comments

* Change to the real insertion sort

* Fix comments


Commit migrated from https://github.com/dotnet/coreclr/commit/42e810630af30672b000f03f9d265fc683d46f97

* Stop using LIST nodes for PHI operand lists

* Speed up PHI creation

Calling gtSetStmtInfo/fgSetStmtSeq every time an arg is added is rather expensive and not really needed. Costs are always 0 and the shape of the PHI tree is always the same.

Removal of GT_LIST nodes makes it easier to update the linear order incrementally when a GT_PHI_ARG node is added.

* Cleanup PHI value numbering

This replaces the manual traversal of PHI's list of uses with a range-based for loop and cleans up a bunch of convoluted code.

* Remove redundant AsPhi

* Remove list pointer union

* Update PHI equality check

* Add GenTreePhi comment

* Rename op to node


Commit migrated from https://github.com/dotnet/coreclr/commit/501c1e3629bbe89cbcec2ee8057ec111a88bdbc8

Separate GenTreeStmt and GenTree.

* Separate fgInsertStmt* and fgInsertTree*.

* Add unreached for GT_STMT in TryGetUse, GenTreeUseEdgeIterator, GetChild.

* Do not call gtDispTree for statements.

Call it for gtStmtExpr instead.

* Separate bbTreeList and bbStmtList.

bbTreeList is used for LIR, bbStmtList for the previous phases.
They can't be both set at the same time.

* Create gtDispStmtList.

To make it obvious that we expect statements.

* Fix another forgotten case of tree instead of stmt.

* Fix rationalize.

Because now bbStmtList and bbTreeList, GT_STMT and GT_IL_OFFSET are separated
we can simplify logic when switch to LIR.

* Delete leftovers.

* Separate Stmt and Tree.

Do not inherit GenTreeStmt from GenTree.

* Update GetIndirSize to handle no user case.

This doesn't change behaviour for the Stmt case because user that was GT_STMT was not able to be GT_ASG at the same time.

* BasicBlock::Contains uses LIR::Range iterator and can't be used for non-LIR case.

* Response review, part 1.

* Response review, part 2.

* Response review, part 3.


Commit migrated from https://github.com/dotnet/coreclr/commit/c7b55aab9ee80734e00894a4391dff51b285a4d0

* Fix some leftovers where we used GenTree instead of GenTreeStmt.

* Separate GT_IL_OFFSET and GT_STMT.

* Add unreached to gtHashValue for GT_STMT.

it has an assert that tree is not GT_STMT: https://github.com/dotnet/coreclr/blob/dotnet/coreclr@65a50887b9a460d7833f0ab476fab9027f1e8166/src/jit/gentree.cpp#L1837 the assert was added before 2010.

* Do not use gtCloneExpr for stms.

* Fix optUnrollLoops.

The was a wrong change in cbf3704a8421ef0b093d68a93d867c9a768dc9d.


Commit migrated from https://github.com/dotnet/coreclr/commit/86fd1ea08c3d05855992df64fbb09929cb47e068