src/jit/copyprop.cpp

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