1// Licensed to the .NET Foundation under one or more agreements.
2// The .NET Foundation licenses this file to you under the MIT license.
3// See the LICENSE file in the project root for more information.
4
5//
6//
7// CopyProp
8//
9// This stage performs value numbering based copy propagation. Since copy propagation
10// is about data flow, we cannot find them in assertion prop phase. In assertion prop
11// we can identify copies, like so: if (a == b) else, i.e., control flow assertions.
12//
13// To identify data flow copies, we'll follow a similar approach to SSA renaming.
14// We would walk each path in the graph keeping track of every live definition. Thus
15// when we see a variable that shares the VN with a live definition, we'd replace this
16// variable with the variable in the live definition, if suitable.
17//
18///////////////////////////////////////////////////////////////////////////////////////
19
20#include "jitpch.h"
21#include "ssabuilder.h"
22#include "treelifeupdater.h"
23
24/**************************************************************************************
25 *
26 * Corresponding to the live definition pushes, pop the stack as we finish a sub-paths
27 * of the graph originating from the block. Refer SSA renaming for any additional info.
28 * "curSsaName" tracks the currently live definitions.
29 */
30void Compiler::optBlockCopyPropPopStacks(BasicBlock* block, LclNumToGenTreePtrStack* curSsaName)
31{
32 for (GenTree* stmt = block->bbTreeList; stmt; stmt = stmt->gtNext)
33 {
34 for (GenTree* tree = stmt->gtStmt.gtStmtList; tree; tree = tree->gtNext)
35 {
36 if (!tree->IsLocal())
37 {
38 continue;
39 }
40 unsigned lclNum = tree->gtLclVarCommon.gtLclNum;
41 if (!lvaInSsa(lclNum))
42 {
43 continue;
44 }
45 if (tree->gtFlags & GTF_VAR_DEF)
46 {
47 GenTreePtrStack* stack = nullptr;
48 curSsaName->Lookup(lclNum, &stack);
49 stack->Pop();
50 if (stack->Empty())
51 {
52 curSsaName->Remove(lclNum);
53 }
54 }
55 }
56 }
57}
58
59#ifdef DEBUG
60void Compiler::optDumpCopyPropStack(LclNumToGenTreePtrStack* curSsaName)
61{
62 JITDUMP("{ ");
63 for (LclNumToGenTreePtrStack::KeyIterator iter = curSsaName->Begin(); !iter.Equal(curSsaName->End()); ++iter)
64 {
65 GenTree* node = iter.GetValue()->Index(0);
66 JITDUMP("%d-[%06d]:V%02u ", iter.Get(), dspTreeID(node), node->AsLclVarCommon()->gtLclNum);
67 }
68 JITDUMP("}\n\n");
69}
70#endif
71/*******************************************************************************************************
72 *
73 * Given the "lclVar" and "copyVar" compute if the copy prop will be beneficial.
74 *
75 */
76int Compiler::optCopyProp_LclVarScore(LclVarDsc* lclVarDsc, LclVarDsc* copyVarDsc, bool preferOp2)
77{
78 int score = 0;
79
80 if (lclVarDsc->lvVolatileHint)
81 {
82 score += 4;
83 }
84
85 if (copyVarDsc->lvVolatileHint)
86 {
87 score -= 4;
88 }
89
90 if (lclVarDsc->lvDoNotEnregister)
91 {
92 score += 4;
93 }
94
95 if (copyVarDsc->lvDoNotEnregister)
96 {
97 score -= 4;
98 }
99
100#ifdef _TARGET_X86_
101 // For doubles we also prefer to change parameters into non-parameter local variables
102 if (lclVarDsc->lvType == TYP_DOUBLE)
103 {
104 if (lclVarDsc->lvIsParam)
105 {
106 score += 2;
107 }
108
109 if (copyVarDsc->lvIsParam)
110 {
111 score -= 2;
112 }
113 }
114#endif
115
116 // Otherwise we prefer to use the op2LclNum
117 return score + ((preferOp2) ? 1 : -1);
118}
119
120//------------------------------------------------------------------------------
121// optCopyProp : Perform copy propagation on a given tree as we walk the graph and if it is a local
122// variable, then look up all currently live definitions and check if any of those
123// definitions share the same value number. If so, then we can make the replacement.
124//
125// Arguments:
126// block - Block the tree belongs to
127// stmt - Statement the tree belongs to
128// tree - The tree to perform copy propagation on
129// curSsaName - The map from lclNum to its recently live definitions as a stack
130
131void Compiler::optCopyProp(BasicBlock* block, GenTree* stmt, GenTree* tree, LclNumToGenTreePtrStack* curSsaName)
132{
133 // TODO-Review: EH successor/predecessor iteration seems broken.
134 if (block->bbCatchTyp == BBCT_FINALLY || block->bbCatchTyp == BBCT_FAULT)
135 {
136 return;
137 }
138
139 // If not local nothing to do.
140 if (!tree->IsLocal())
141 {
142 return;
143 }
144 if (tree->OperGet() == GT_PHI_ARG || tree->OperGet() == GT_LCL_FLD)
145 {
146 return;
147 }
148
149 // Propagate only on uses.
150 if (tree->gtFlags & GTF_VAR_DEF)
151 {
152 return;
153 }
154 unsigned lclNum = tree->AsLclVarCommon()->GetLclNum();
155
156 // Skip non-SSA variables.
157 if (!lvaInSsa(lclNum))
158 {
159 return;
160 }
161
162 assert(tree->gtVNPair.GetConservative() != ValueNumStore::NoVN);
163
164 for (LclNumToGenTreePtrStack::KeyIterator iter = curSsaName->Begin(); !iter.Equal(curSsaName->End()); ++iter)
165 {
166 unsigned newLclNum = iter.Get();
167
168 GenTree* op = iter.GetValue()->Index(0);
169
170 // Nothing to do if same.
171 if (lclNum == newLclNum)
172 {
173 continue;
174 }
175
176 // Skip variables with assignments embedded in the statement (i.e., with a comma). Because we
177 // are not currently updating their SSA names as live in the copy-prop pass of the stmt.
178 if (VarSetOps::IsMember(this, optCopyPropKillSet, lvaTable[newLclNum].lvVarIndex))
179 {
180 continue;
181 }
182
183 if (op->gtFlags & GTF_VAR_CAST)
184 {
185 continue;
186 }
187 if (gsShadowVarInfo != nullptr && lvaTable[newLclNum].lvIsParam &&
188 gsShadowVarInfo[newLclNum].shadowCopy == lclNum)
189 {
190 continue;
191 }
192 ValueNum opVN = GetUseAsgDefVNOrTreeVN(op);
193 if (opVN == ValueNumStore::NoVN)
194 {
195 continue;
196 }
197 if (op->TypeGet() != tree->TypeGet())
198 {
199 continue;
200 }
201 if (opVN != tree->gtVNPair.GetConservative())
202 {
203 continue;
204 }
205 if (optCopyProp_LclVarScore(&lvaTable[lclNum], &lvaTable[newLclNum], true) <= 0)
206 {
207 continue;
208 }
209 // Check whether the newLclNum is live before being substituted. Otherwise, we could end
210 // up in a situation where there must've been a phi node that got pruned because the variable
211 // is not live anymore. For example,
212 // if
213 // x0 = 1
214 // else
215 // x1 = 2
216 // print(c) <-- x is not live here. Let's say 'c' shares the value number with "x0."
217 //
218 // If we simply substituted 'c' with "x0", we would be wrong. Ideally, there would be a phi
219 // node x2 = phi(x0, x1) which can then be used to substitute 'c' with. But because of pruning
220 // there would be no such phi node. To solve this we'll check if 'x' is live, before replacing
221 // 'c' with 'x.'
222 if (!lvaTable[newLclNum].lvVerTypeInfo.IsThisPtr())
223 {
224 if (lvaTable[newLclNum].lvAddrExposed)
225 {
226 continue;
227 }
228
229 // We compute liveness only on tracked variables. So skip untracked locals.
230 if (!lvaTable[newLclNum].lvTracked)
231 {
232 continue;
233 }
234
235 // Because of this dependence on live variable analysis, CopyProp phase is immediately
236 // after Liveness, SSA and VN.
237 if (!VarSetOps::IsMember(this, compCurLife, lvaTable[newLclNum].lvVarIndex))
238 {
239 continue;
240 }
241 }
242 unsigned newSsaNum = SsaConfig::RESERVED_SSA_NUM;
243 if (op->gtFlags & GTF_VAR_DEF)
244 {
245 newSsaNum = GetSsaNumForLocalVarDef(op);
246 }
247 else // parameters, this pointer etc.
248 {
249 newSsaNum = op->AsLclVarCommon()->GetSsaNum();
250 }
251
252 if (newSsaNum == SsaConfig::RESERVED_SSA_NUM)
253 {
254 continue;
255 }
256
257#ifdef DEBUG
258 if (verbose)
259 {
260 JITDUMP("VN based copy assertion for ");
261 printTreeID(tree);
262 printf(" V%02d @%08X by ", lclNum, tree->GetVN(VNK_Conservative));
263 printTreeID(op);
264 printf(" V%02d @%08X.\n", newLclNum, op->GetVN(VNK_Conservative));
265 gtDispTree(tree, nullptr, nullptr, true);
266 }
267#endif
268
269 tree->gtLclVarCommon.SetLclNum(newLclNum);
270 tree->AsLclVarCommon()->SetSsaNum(newSsaNum);
271 gtUpdateSideEffects(stmt, tree);
272#ifdef DEBUG
273 if (verbose)
274 {
275 printf("copy propagated to:\n");
276 gtDispTree(tree, nullptr, nullptr, true);
277 }
278#endif
279 break;
280 }
281 return;
282}
283
284/**************************************************************************************
285 *
286 * Helper to check if tree is a local that participates in SSA numbering.
287 */
288bool Compiler::optIsSsaLocal(GenTree* tree)
289{
290 return tree->IsLocal() && lvaInSsa(tree->AsLclVarCommon()->GetLclNum());
291}
292
293//------------------------------------------------------------------------------
294// optBlockCopyProp : Perform copy propagation using currently live definitions on the current block's
295// variables. Also as new definitions are encountered update the "curSsaName" which
296// tracks the currently live definitions.
297//
298// Arguments:
299// block - Block the tree belongs to
300// curSsaName - The map from lclNum to its recently live definitions as a stack
301
302void Compiler::optBlockCopyProp(BasicBlock* block, LclNumToGenTreePtrStack* curSsaName)
303{
304#ifdef DEBUG
305 JITDUMP("Copy Assertion for " FMT_BB "\n", block->bbNum);
306 if (verbose)
307 {
308 printf(" curSsaName stack: ");
309 optDumpCopyPropStack(curSsaName);
310 }
311#endif
312
313 TreeLifeUpdater<false> treeLifeUpdater(this);
314
315 // There are no definitions at the start of the block. So clear it.
316 compCurLifeTree = nullptr;
317 VarSetOps::Assign(this, compCurLife, block->bbLiveIn);
318 for (GenTree* stmt = block->bbTreeList; stmt; stmt = stmt->gtNext)
319 {
320 VarSetOps::ClearD(this, optCopyPropKillSet);
321
322 // Walk the tree to find if any local variable can be replaced with current live definitions.
323 for (GenTree* tree = stmt->gtStmt.gtStmtList; tree; tree = tree->gtNext)
324 {
325 treeLifeUpdater.UpdateLife(tree);
326
327 optCopyProp(block, stmt, tree, curSsaName);
328
329 // TODO-Review: Merge this loop with the following loop to correctly update the
330 // live SSA num while also propagating copies.
331 //
332 // 1. This loop performs copy prop with currently live (on-top-of-stack) SSA num.
333 // 2. The subsequent loop maintains a stack for each lclNum with
334 // currently active SSA numbers when definitions are encountered.
335 //
336 // If there is an embedded definition using a "comma" in a stmt, then the currently
337 // live SSA number will get updated only in the next loop (2). However, this new
338 // definition is now supposed to be live (on tos). If we did not update the stacks
339 // using (2), copy prop (1) will use a SSA num defined outside the stmt ignoring the
340 // embedded update. Killing the variable is a simplification to produce 0 ASM diffs
341 // for an update release.
342 //
343 if (optIsSsaLocal(tree) && (tree->gtFlags & GTF_VAR_DEF))
344 {
345 VarSetOps::AddElemD(this, optCopyPropKillSet, lvaTable[tree->gtLclVarCommon.gtLclNum].lvVarIndex);
346 }
347 }
348
349 // This logic must be in sync with SSA renaming process.
350 for (GenTree* tree = stmt->gtStmt.gtStmtList; tree; tree = tree->gtNext)
351 {
352 if (!optIsSsaLocal(tree))
353 {
354 continue;
355 }
356
357 unsigned lclNum = tree->gtLclVarCommon.gtLclNum;
358
359 // As we encounter a definition add it to the stack as a live definition.
360 if (tree->gtFlags & GTF_VAR_DEF)
361 {
362 GenTreePtrStack* stack;
363 if (!curSsaName->Lookup(lclNum, &stack))
364 {
365 stack = new (curSsaName->GetAllocator()) GenTreePtrStack(curSsaName->GetAllocator());
366 }
367 stack->Push(tree);
368 curSsaName->Set(lclNum, stack);
369 }
370 // If we encounter first use of a param or this pointer add it as a live definition.
371 // Since they are always live, do it only once.
372 else if ((tree->gtOper == GT_LCL_VAR) && !(tree->gtFlags & GTF_VAR_USEASG) &&
373 (lvaTable[lclNum].lvIsParam || lvaTable[lclNum].lvVerTypeInfo.IsThisPtr()))
374 {
375 GenTreePtrStack* stack;
376 if (!curSsaName->Lookup(lclNum, &stack))
377 {
378 stack = new (curSsaName->GetAllocator()) GenTreePtrStack(curSsaName->GetAllocator());
379 stack->Push(tree);
380 curSsaName->Set(lclNum, stack);
381 }
382 }
383 }
384 }
385}
386
387/**************************************************************************************
388 *
389 * This stage performs value numbering based copy propagation. Since copy propagation
390 * is about data flow, we cannot find them in assertion prop phase. In assertion prop
391 * we can identify copies that like so: if (a == b) else, i.e., control flow assertions.
392 *
393 * To identify data flow copies, we follow a similar approach to SSA renaming. We walk
394 * each path in the graph keeping track of every live definition. Thus when we see a
395 * variable that shares the VN with a live definition, we'd replace this variable with
396 * the variable in the live definition.
397 *
398 * We do this to be in conventional SSA form. This can very well be changed later.
399 *
400 * For example, on some path in the graph:
401 * a0 = x0
402 * : <- other blocks
403 * :
404 * a1 = y0
405 * :
406 * : <- other blocks
407 * b0 = x0, we cannot substitute x0 with a0, because currently our backend doesn't
408 * treat lclNum and ssaNum together as a variable, but just looks at lclNum. If we
409 * substituted x0 with a0, then we'd be in general SSA form.
410 *
411 */
412void Compiler::optVnCopyProp()
413{
414#ifdef DEBUG
415 if (verbose)
416 {
417 printf("*************** In optVnCopyProp()\n");
418 }
419#endif
420
421 if (fgSsaPassesCompleted == 0)
422 {
423 return;
424 }
425
426 CompAllocator allocator(getAllocator(CMK_CopyProp));
427
428 // Compute the domTree to use.
429 BlkToBlkVectorMap* domTree = new (allocator) BlkToBlkVectorMap(allocator);
430 domTree->Reallocate(fgBBcount * 3 / 2); // Prime the allocation
431 SsaBuilder::ComputeDominators(this, domTree);
432
433 struct BlockWork
434 {
435 BasicBlock* m_blk;
436 bool m_processed;
437
438 BlockWork(BasicBlock* blk, bool processed = false) : m_blk(blk), m_processed(processed)
439 {
440 }
441 };
442 typedef jitstd::vector<BlockWork> BlockWorkStack;
443
444 VarSetOps::AssignNoCopy(this, compCurLife, VarSetOps::MakeEmpty(this));
445 VarSetOps::AssignNoCopy(this, optCopyPropKillSet, VarSetOps::MakeEmpty(this));
446
447 // The map from lclNum to its recently live definitions as a stack.
448 LclNumToGenTreePtrStack curSsaName(allocator);
449
450 BlockWorkStack* worklist = new (allocator) BlockWorkStack(allocator);
451
452 worklist->push_back(BlockWork(fgFirstBB));
453 while (!worklist->empty())
454 {
455 BlockWork work = worklist->back();
456 worklist->pop_back();
457
458 BasicBlock* block = work.m_blk;
459 if (work.m_processed)
460 {
461 // Pop all the live definitions for this block.
462 optBlockCopyPropPopStacks(block, &curSsaName);
463 continue;
464 }
465
466 // Generate copy assertions in this block, and keeping curSsaName variable up to date.
467 worklist->push_back(BlockWork(block, true));
468
469 optBlockCopyProp(block, &curSsaName);
470
471 // Add dom children to work on.
472 BlkVector* domChildren = domTree->LookupPointer(block);
473 if (domChildren != nullptr)
474 {
475 for (BasicBlock* child : *domChildren)
476 {
477 worklist->push_back(BlockWork(child));
478 }
479 }
480 }
481
482 // Tracked variable count increases after CopyProp, so don't keep a shorter array around.
483 // Destroy (release) the varset.
484 VarSetOps::AssignNoCopy(this, compCurLife, VarSetOps::UninitVal());
485}
486