Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commite907ed1

Browse files
committed
JIT: Make strength reduced IV updates amenable to post-indexed addressing
On arm64 have strength reduction try to insert IV updates after the lastuse if that last use is a legal insertion point. This often allows thebackend to use post-indexed addressing to combine the use with the IVupdate.
1 parentb084c08 commite907ed1

File tree

1 file changed

+156
-9
lines changed

1 file changed

+156
-9
lines changed

‎src/coreclr/jit/inductionvariableopts.cpp‎

Lines changed: 156 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -1341,7 +1341,11 @@ class StrengthReductionContext
13411341
boolCheckAdvancedCursors(ArrayStack<CursorInfo>* cursors, ScevAddRec** nextIV);
13421342
boolStaysWithinManagedObject(ArrayStack<CursorInfo>* cursors, ScevAddRec* addRec);
13431343
boolTryReplaceUsesWithNewPrimaryIV(ArrayStack<CursorInfo>* cursors, ScevAddRec* iv);
1344-
BasicBlock*FindUpdateInsertionPoint(ArrayStack<CursorInfo>* cursors);
1344+
BasicBlock*FindUpdateInsertionPoint(ArrayStack<CursorInfo>* cursors, Statement** afterStmt);
1345+
BasicBlock*FindPostUseUpdateInsertionPoint(ArrayStack<CursorInfo>* cursors,
1346+
BasicBlock* backEdgeDominator,
1347+
Statement** afterStmt);
1348+
boolInsertionPointPostDominatesUses(BasicBlock* insertionPoint, ArrayStack<CursorInfo>* cursors);
13451349

13461350
boolStressProfitability()
13471351
{
@@ -2000,7 +2004,8 @@ bool StrengthReductionContext::TryReplaceUsesWithNewPrimaryIV(ArrayStack<CursorI
20002004
returnfalse;
20012005
}
20022006

2003-
BasicBlock* insertionPoint =FindUpdateInsertionPoint(cursors);
2007+
Statement* afterStmt;
2008+
BasicBlock* insertionPoint =FindUpdateInsertionPoint(cursors, &afterStmt);
20042009
if (insertionPoint ==nullptr)
20052010
{
20062011
JITDUMP(" Skipping: could not find a legal insertion point for the new IV update\n");
@@ -2032,7 +2037,14 @@ bool StrengthReductionContext::TryReplaceUsesWithNewPrimaryIV(ArrayStack<CursorI
20322037
m_comp->gtNewOperNode(GT_ADD, iv->Type, m_comp->gtNewLclVarNode(newPrimaryIV, iv->Type), stepValue);
20332038
GenTree* stepStore = m_comp->gtNewTempStore(newPrimaryIV, nextValue);
20342039
Statement* stepStmt = m_comp->fgNewStmtFromTree(stepStore);
2035-
m_comp->fgInsertStmtNearEnd(insertionPoint, stepStmt);
2040+
if (afterStmt !=nullptr)
2041+
{
2042+
m_comp->fgInsertStmtAfter(insertionPoint, afterStmt, stepStmt);
2043+
}
2044+
else
2045+
{
2046+
m_comp->fgInsertStmtNearEnd(insertionPoint, stepStmt);
2047+
}
20362048

20372049
JITDUMP(" Inserting step statement in" FMT_BB"\n", insertionPoint->bbNum);
20382050
DISPSTMT(stepStmt);
@@ -2084,22 +2096,27 @@ bool StrengthReductionContext::TryReplaceUsesWithNewPrimaryIV(ArrayStack<CursorI
20842096
// of a new primary IV introduced by strength reduction.
20852097
//
20862098
// Parameters:
2087-
// cursors - The list of cursors pointing to uses that are being replaced by
2088-
// the new IV
2099+
// cursors - The list of cursors pointing to uses that are being replaced by
2100+
// the new IV
2101+
// afterStmt - [out] Statement to insert the update after. Set to nullptr if
2102+
// update should be inserted near the end of the block.
20892103
//
20902104
// Returns:
20912105
// Basic block; the insertion point is the end (before a potential
20922106
// terminator) of this basic block. May return null if no insertion point
20932107
// could be found.
20942108
//
2095-
BasicBlock*StrengthReductionContext::FindUpdateInsertionPoint(ArrayStack<CursorInfo>* cursors)
2109+
BasicBlock*StrengthReductionContext::FindUpdateInsertionPoint(ArrayStack<CursorInfo>* cursors, Statement** afterStmt)
20962110
{
2111+
*afterStmt =nullptr;
2112+
20972113
// Find insertion point. It needs to post-dominate all uses we are going to
20982114
// replace and it needs to dominate all backedges.
20992115
// TODO-CQ: Canonicalizing backedges would make this simpler and work in
21002116
// more cases.
21012117

21022118
BasicBlock* insertionPoint =nullptr;
2119+
21032120
for (FlowEdge* backEdge : m_loop->BackEdges())
21042121
{
21052122
if (insertionPoint ==nullptr)
@@ -2112,6 +2129,18 @@ BasicBlock* StrengthReductionContext::FindUpdateInsertionPoint(ArrayStack<Cursor
21122129
}
21132130
}
21142131

2132+
#ifdef TARGET_ARM64
2133+
// For arm64 we try to place the IV update after a use if possible. This
2134+
// sets the backend up for post-indexed addressing mode.
2135+
BasicBlock* postUseInsertionPoint =FindPostUseUpdateInsertionPoint(cursors, insertionPoint, afterStmt);
2136+
if (postUseInsertionPoint !=nullptr)
2137+
{
2138+
JITDUMP(" Found a legal insertion point after a last use of the IV in" FMT_BB" after" FMT_STMT"\n",
2139+
postUseInsertionPoint->bbNum, (*afterStmt)->GetID());
2140+
return postUseInsertionPoint;
2141+
}
2142+
#endif
2143+
21152144
while ((insertionPoint !=nullptr) && m_loop->ContainsBlock(insertionPoint) &&
21162145
m_loop->MayExecuteBlockMultipleTimesPerIteration(insertionPoint))
21172146
{
@@ -2123,6 +2152,124 @@ BasicBlock* StrengthReductionContext::FindUpdateInsertionPoint(ArrayStack<Cursor
21232152
returnnullptr;
21242153
}
21252154

2155+
if (!InsertionPointPostDominatesUses(insertionPoint, cursors))
2156+
{
2157+
returnnullptr;
2158+
}
2159+
2160+
JITDUMP(" Found a legal insertion point in" FMT_BB"\n", insertionPoint->bbNum);
2161+
return insertionPoint;
2162+
}
2163+
2164+
//------------------------------------------------------------------------
2165+
// FindPostUseUpdateInsertionPoint: Try finding an insertion point for the IV
2166+
// update that is right after one of the uses of it.
2167+
//
2168+
// Parameters:
2169+
// cursors - The list of cursors pointing to uses that are being replaced by
2170+
// the new IV
2171+
// backEdgeDominator - A basic block that dominates all backedges
2172+
// afterStmt - [out] Statement to insert the update after, if the
2173+
// return value is non-null.
2174+
//
2175+
// Returns:
2176+
// nullptr if no such insertion point could be found. Otherwise returns the
2177+
// basic block and statement after which the update can be inserted.
2178+
//
2179+
BasicBlock*StrengthReductionContext::FindPostUseUpdateInsertionPoint(ArrayStack<CursorInfo>* cursors,
2180+
BasicBlock* backEdgeDominator,
2181+
Statement** afterStmt)
2182+
{
2183+
BitVecTraits poTraits = m_loop->GetDfsTree()->PostOrderTraits();
2184+
2185+
#ifdef DEBUG
2186+
// We will be relying on the fact that the cursors are ordered in a useful
2187+
// way here: loop locals are visited in post order within each basic block,
2188+
// meaning that "cursors" has the last uses first for each basic block.
2189+
// Assert that here.
2190+
2191+
BitVecseenBlocks(BitVecOps::MakeEmpty(&poTraits));
2192+
for (int i =1; i < cursors->Height(); i++)
2193+
{
2194+
CursorInfo& prevCursor = cursors->BottomRef(i -1);
2195+
CursorInfo& cursor = cursors->BottomRef(i);
2196+
2197+
if (cursor.Block != prevCursor.Block)
2198+
{
2199+
assert(BitVecOps::TryAddElemD(&poTraits, seenBlocks, prevCursor.Block->bbPostorderNum));
2200+
continue;
2201+
}
2202+
2203+
Statement* curStmt = cursor.Stmt;
2204+
while ((curStmt !=nullptr) && (curStmt != prevCursor.Stmt))
2205+
{
2206+
curStmt = curStmt->GetNextStmt();
2207+
}
2208+
2209+
assert(curStmt == prevCursor.Stmt);
2210+
}
2211+
#endif
2212+
2213+
BitVecblocksWithUses(BitVecOps::MakeEmpty(&poTraits));
2214+
for (int i =0; i < cursors->Height(); i++)
2215+
{
2216+
CursorInfo& cursor = cursors->BottomRef(i);
2217+
BitVecOps::AddElemD(&poTraits, blocksWithUses, cursor.Block->bbPostorderNum);
2218+
}
2219+
2220+
while ((backEdgeDominator !=nullptr) && m_loop->ContainsBlock(backEdgeDominator))
2221+
{
2222+
if (!BitVecOps::IsMember(&poTraits, blocksWithUses, backEdgeDominator->bbPostorderNum))
2223+
{
2224+
backEdgeDominator = backEdgeDominator->bbIDom;
2225+
continue;
2226+
}
2227+
2228+
if (m_loop->MayExecuteBlockMultipleTimesPerIteration(backEdgeDominator))
2229+
{
2230+
returnnullptr;
2231+
}
2232+
2233+
for (int i =0; i < cursors->Height(); i++)
2234+
{
2235+
CursorInfo& cursor = cursors->BottomRef(i);
2236+
if (cursor.Block != backEdgeDominator)
2237+
{
2238+
continue;
2239+
}
2240+
2241+
if (!InsertionPointPostDominatesUses(cursor.Block, cursors))
2242+
{
2243+
returnnullptr;
2244+
}
2245+
2246+
*afterStmt = cursor.Stmt;
2247+
return cursor.Block;
2248+
}
2249+
}
2250+
2251+
returnnullptr;
2252+
}
2253+
2254+
//------------------------------------------------------------------------
2255+
// InsertionPointPostDominatesUses: Check if a basic block post-dominates all
2256+
// locations specified by the cursors.
2257+
//
2258+
// Parameters:
2259+
// insertionPoint - The insertion point
2260+
// cursors - Cursors specifying locations
2261+
//
2262+
// Returns:
2263+
// True if so.
2264+
//
2265+
// Remarks:
2266+
// For cursors inside "insertionPoint", the function expects that the
2267+
// insertion point is _after_ the use, except if the use is in a terminator
2268+
// statement.
2269+
//
2270+
boolStrengthReductionContext::InsertionPointPostDominatesUses(BasicBlock* insertionPoint,
2271+
ArrayStack<CursorInfo>* cursors)
2272+
{
21262273
for (int i =0; i < cursors->Height(); i++)
21272274
{
21282275
CursorInfo& cursor = cursors->BottomRef(i);
@@ -2131,19 +2278,19 @@ BasicBlock* StrengthReductionContext::FindUpdateInsertionPoint(ArrayStack<Cursor
21312278
{
21322279
if (insertionPoint->HasTerminator() && (cursor.Stmt == insertionPoint->lastStmt()))
21332280
{
2134-
returnnullptr;
2281+
returnfalse;
21352282
}
21362283
}
21372284
else
21382285
{
21392286
if (!m_loop->IsPostDominatedOnLoopIteration(cursor.Block, insertionPoint))
21402287
{
2141-
returnnullptr;
2288+
returnfalse;
21422289
}
21432290
}
21442291
}
21452292

2146-
returninsertionPoint;
2293+
returntrue;
21472294
}
21482295

21492296
//------------------------------------------------------------------------

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp