src/jit/sideeffects.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 #include "jitpch.h"
   6 #ifdef _MSC_VER
   7 #pragma hdrstop
   8 #endif
   9
  10 #include "sideeffects.h"
  11
  12 LclVarSet::LclVarSet() : m_bitVector(nullptr), m_hasAnyLcl(false), m_hasBitVector(false)
  13 {
  14 }
  15
  16 //------------------------------------------------------------------------
  17 // LclVarSet::Add:
  18 //    Adds the given lclNum to the LclVarSet.
  19 //
  20 // Arguments:
  21 //    compiler - The compiler context
  22 //    lclNum - The lclNum to add.
  23 //
  24 void LclVarSet::Add(Compiler* compiler, unsigned lclNum)
  25 {
  26     if (!m_hasAnyLcl)
  27     {
  28         m_lclNum    = lclNum;
  29         m_hasAnyLcl = true;
  30     }
  31     else
  32     {
  33         if (!m_hasBitVector)
  34         {
  35             unsigned singleLclNum = m_lclNum;
  36             m_bitVector           = hashBv::Create(compiler);
  37             m_bitVector->setBit(singleLclNum);
  38             m_hasBitVector = true;
  39         }
  40
  41         m_bitVector->setBit(lclNum);
  42     }
  43 }
  44
  45 //------------------------------------------------------------------------
  46 // LclVarSet::Intersects:
  47 //    Returns true if this LclVarSet intersects with the given LclVarSet.
  48 //
  49 // Arguments:
  50 //    other - The other lclVarSet.
  51 //
  52 bool LclVarSet::Intersects(const LclVarSet& other) const
  53 {
  54     // If neither set has ever contained anything, the sets do not intersect.
  55     if (!m_hasAnyLcl || !other.m_hasAnyLcl)
  56     {
  57         return false;
  58     }
  59
  60     // If this set is not represented by a bit vector, see if the single lclNum is contained in the other set.
  61     if (!m_hasBitVector)
  62     {
  63         if (!other.m_hasBitVector)
  64         {
  65             return m_lclNum == other.m_lclNum;
  66         }
  67
  68         return other.m_bitVector->testBit(m_lclNum);
  69     }
  70
  71     // If this set is represented by a bit vector but the other set is not, see if the single lclNum in the other
  72     // set is contained in this set.
  73     if (!other.m_hasBitVector)
  74     {
  75         return m_bitVector->testBit(other.m_lclNum);
  76     }
  77
  78     // Both sets are represented by bit vectors. Check to see if they intersect.
  79     return m_bitVector->Intersects(other.m_bitVector);
  80 }
  81
  82 //------------------------------------------------------------------------
  83 // LclVarSet::Contains:
  84 //    Returns true if this LclVarSet contains the given lclNum.
  85 //
  86 // Arguments:
  87 //    lclNum - The lclNum in question.
  88 //
  89 bool LclVarSet::Contains(unsigned lclNum) const
  90 {
  91     // If this set has never contained anything, it does not contain the lclNum.
  92     if (!m_hasAnyLcl)
  93     {
  94         return false;
  95     }
  96
  97     // If this set is not represented by a bit vector, see if its single lclNum is the same as the given lclNum.
  98     if (!m_hasBitVector)
  99     {
 100         return m_lclNum == lclNum;
 101     }
 102
 103     // This set is represented by a bit vector. See if the bit vector contains the given lclNum.
 104     return m_bitVector->testBit(lclNum);
 105 }
 106
 107 //------------------------------------------------------------------------
 108 // LclVarSet::Clear:
 109 //    Clears the contents of this LclVarSet.
 110 //
 111 void LclVarSet::Clear()
 112 {
 113     if (m_hasBitVector)
 114     {
 115         assert(m_hasAnyLcl);
 116         m_bitVector->ZeroAll();
 117     }
 118     else if (m_hasAnyLcl)
 119     {
 120         m_hasAnyLcl = false;
 121     }
 122 }
 123
 124 AliasSet::AliasSet()
 125     : m_lclVarReads(), m_lclVarWrites(), m_readsAddressableLocation(false), m_writesAddressableLocation(false)
 126 {
 127 }
 128
 129 //------------------------------------------------------------------------
 130 // AliasSet::NodeInfo::NodeInfo:
 131 //    Computes the alias info for a given node. Note that this does not
 132 //    include the set of lclVar accesses for a node unless the node is
 133 //    itself a lclVar access (e.g. a GT_LCL_VAR, GT_STORE_LCL_VAR, etc.).
 134 //
 135 // Arguments:
 136 //    compiler - The compiler context.
 137 //    node - The node in question.
 138 //
 139 AliasSet::NodeInfo::NodeInfo(Compiler* compiler, GenTree* node)
 140     : m_compiler(compiler), m_node(node), m_flags(0), m_lclNum(0)
 141 {
 142     if (node->IsCall())
 143     {
 144         // Calls are treated as reads and writes of addressable locations unless they are known to be pure.
 145         if (node->AsCall()->IsPure(compiler))
 146         {
 147             m_flags = ALIAS_NONE;
 148             return;
 149         }
 150
 151         m_flags = ALIAS_READS_ADDRESSABLE_LOCATION | ALIAS_WRITES_ADDRESSABLE_LOCATION;
 152         return;
 153     }
 154     else if (node->OperIsAtomicOp())
 155     {
 156         // Atomic operations both read and write addressable locations.
 157         m_flags = ALIAS_READS_ADDRESSABLE_LOCATION | ALIAS_WRITES_ADDRESSABLE_LOCATION;
 158         return;
 159     }
 160
 161     // Is the operation a write? If so, set `node` to the location that is being written to.
 162     bool isWrite = false;
 163     if (node->OperIsAssignment())
 164     {
 165         isWrite = true;
 166         node    = node->gtGetOp1();
 167     }
 168     else if (node->OperIsStore() || node->OperIsAtomicOp())
 169     {
 170         isWrite = true;
 171     }
 172
 173     // `node` is the location being accessed. Determine whether or not it is a memory or local variable access, and if
 174     // it is the latter, get the number of the lclVar.
 175     bool     isMemoryAccess = false;
 176     bool     isLclVarAccess = false;
 177     unsigned lclNum         = 0;
 178     if (node->OperIsIndir())
 179     {
 180         // If the indirection targets a lclVar, we can be more precise with regards to aliasing by treating the
 181         // indirection as a lclVar access.
 182         GenTree* address = node->AsIndir()->Addr();
 183         if (address->OperIsLocalAddr())
 184         {
 185             isLclVarAccess = true;
 186             lclNum         = address->AsLclVarCommon()->GetLclNum();
 187         }
 188         else
 189         {
 190             isMemoryAccess = true;
 191         }
 192     }
 193     else if (node->OperIsImplicitIndir())
 194     {
 195         isMemoryAccess = true;
 196     }
 197     else if (node->OperIsLocal())
 198     {
 199         isLclVarAccess = true;
 200         lclNum         = node->AsLclVarCommon()->GetLclNum();
 201     }
 202     else
 203     {
 204         // This is neither a memory nor a local var access.
 205         m_flags = ALIAS_NONE;
 206         return;
 207     }
 208
 209     assert(isMemoryAccess || isLclVarAccess);
 210
 211     // Now that we've determined whether or not this access is a read or a write and whether the accessed location is
 212     // memory or a lclVar, determine whther or not the location is addressable and udpate the alias set.
 213     const bool isAddressableLocation = isMemoryAccess || compiler->lvaTable[lclNum].lvAddrExposed;
 214
 215     if (!isWrite)
 216     {
 217         if (isAddressableLocation)
 218         {
 219             m_flags |= ALIAS_READS_ADDRESSABLE_LOCATION;
 220         }
 221
 222         if (isLclVarAccess)
 223         {
 224             m_flags |= ALIAS_READS_LCL_VAR;
 225             m_lclNum = lclNum;
 226         }
 227     }
 228     else
 229     {
 230         if (isAddressableLocation)
 231         {
 232             m_flags |= ALIAS_WRITES_ADDRESSABLE_LOCATION;
 233         }
 234
 235         if (isLclVarAccess)
 236         {
 237             m_flags |= ALIAS_WRITES_LCL_VAR;
 238             m_lclNum = lclNum;
 239         }
 240     }
 241 }
 242
 243 //------------------------------------------------------------------------
 244 // AliasSet::AddNode:
 245 //    Adds the given node's accesses to this AliasSet.
 246 //
 247 // Arguments:
 248 //    compiler - The compiler context.
 249 //    node - The node to add to the set.
 250 //
 251 void AliasSet::AddNode(Compiler* compiler, GenTree* node)
 252 {
 253     // First, add all lclVar uses associated with the node to the set. This is necessary because the lclVar reads occur
 254     // at the position of the user, not at the position of the GenTreeLclVar node.
 255     node->VisitOperands([compiler, this](GenTree* operand) -> GenTree::VisitResult {
 256         if (operand->OperIsLocalRead())
 257         {
 258             const unsigned lclNum = operand->AsLclVarCommon()->GetLclNum();
 259             if (compiler->lvaTable[lclNum].lvAddrExposed)
 260             {
 261                 m_readsAddressableLocation = true;
 262             }
 263
 264             m_lclVarReads.Add(compiler, lclNum);
 265         }
 266         if (!operand->IsArgPlaceHolderNode() && operand->isContained())
 267         {
 268             AddNode(compiler, operand);
 269         }
 270         return GenTree::VisitResult::Continue;
 271     });
 272
 273     NodeInfo nodeInfo(compiler, node);
 274     if (nodeInfo.ReadsAddressableLocation())
 275     {
 276         m_readsAddressableLocation = true;
 277     }
 278     if (nodeInfo.WritesAddressableLocation())
 279     {
 280         m_writesAddressableLocation = true;
 281     }
 282     if (nodeInfo.IsLclVarRead())
 283     {
 284         m_lclVarReads.Add(compiler, nodeInfo.LclNum());
 285     }
 286     if (nodeInfo.IsLclVarWrite())
 287     {
 288         m_lclVarWrites.Add(compiler, nodeInfo.LclNum());
 289     }
 290 }
 291
 292 //------------------------------------------------------------------------
 293 // AliasSet::InterferesWith:
 294 //    Returns true if the reads and writes in this alias set interfere
 295 //    with the given alias set.
 296 //
 297 //    Two alias sets interfere under any of the following conditions:
 298 //    - Both sets write to any addressable location (e.g. the heap,
 299 //      address-exposed locals)
 300 //    - One set reads any addressable location and the other set writes
 301 //      any addressable location
 302 //    - Both sets write to the same lclVar
 303 //    - One set writes to a lclVar that is read by the other set
 304 //
 305 // Arguments:
 306 //    other - The other alias set.
 307 //
 308 bool AliasSet::InterferesWith(const AliasSet& other) const
 309 {
 310     // If both sets write any addressable location, the sets interfere.
 311     if (m_writesAddressableLocation && other.m_writesAddressableLocation)
 312     {
 313         return true;
 314     }
 315
 316     // If one set writes any addressable location and the other reads any addressable location, the sets interfere.
 317     if ((m_readsAddressableLocation && other.m_writesAddressableLocation) ||
 318         (m_writesAddressableLocation && other.m_readsAddressableLocation))
 319     {
 320         return true;
 321     }
 322
 323     // If the set of lclVars written by this alias set intersects with the set of lclVars accessed by the other alias
 324     // set, the alias sets interfere.
 325     if (m_lclVarWrites.Intersects(other.m_lclVarReads) || m_lclVarWrites.Intersects(other.m_lclVarWrites))
 326     {
 327         return true;
 328     }
 329
 330     // If the set of lclVars read by this alias set intersects with the set of lclVars written by the other alias set,
 331     // the alias sets interfere. Otherwise, the alias sets do not interfere.
 332     return m_lclVarReads.Intersects(other.m_lclVarWrites);
 333 }
 334
 335 //------------------------------------------------------------------------
 336 // AliasSet::InterferesWith:
 337 //    Returns true if the reads and writes in this alias set interfere
 338 //    with those for the given node.
 339 //
 340 //    An alias set interferes with a given node iff it interferes with the
 341 //    alias set for that node.
 342 //
 343 // Arguments:
 344 //    other - The info for the node in question.
 345 //
 346 bool AliasSet::InterferesWith(const NodeInfo& other) const
 347 {
 348     // First check whether or not this set interferes with the lclVar uses associated with the given node.
 349     if (m_writesAddressableLocation || !m_lclVarWrites.IsEmpty())
 350     {
 351         Compiler* compiler = other.TheCompiler();
 352         for (GenTree* operand : other.Node()->Operands())
 353         {
 354             if (operand->OperIsLocalRead())
 355             {
 356                 // If this set writes any addressable location and the node uses an address-exposed lclVar,
 357                 // the set interferes with the node.
 358                 const unsigned lclNum = operand->AsLclVarCommon()->GetLclNum();
 359                 if (compiler->lvaTable[lclNum].lvAddrExposed && m_writesAddressableLocation)
 360                 {
 361                     return true;
 362                 }
 363
 364                 // If this set writes to a lclVar used by the node, the set interferes with the node.
 365                 if (m_lclVarWrites.Contains(lclNum))
 366                 {
 367                     return true;
 368                 }
 369             }
 370         }
 371     }
 372
 373     // If the node and the set both write to any addressable location, they interfere.
 374     if (m_writesAddressableLocation && other.WritesAddressableLocation())
 375     {
 376         return true;
 377     }
 378
 379     // If the node or the set writes any addressable location and the other reads any addressable location,
 380     // they interfere.
 381     if ((m_readsAddressableLocation && other.WritesAddressableLocation()) ||
 382         (m_writesAddressableLocation && other.ReadsAddressableLocation()))
 383     {
 384         return true;
 385     }
 386
 387     // If the set writes a local var accessed by the node, they interfere.
 388     if ((other.IsLclVarRead() || other.IsLclVarWrite()) && m_lclVarWrites.Contains(other.LclNum()))
 389     {
 390         return true;
 391     }
 392
 393     // If the set reads a local var written by the node, they interfere.
 394     return other.IsLclVarWrite() && m_lclVarReads.Contains(other.LclNum());
 395 }
 396
 397 //------------------------------------------------------------------------
 398 // AliasSet::Clear:
 399 //    Clears the current alias set.
 400 //
 401 void AliasSet::Clear()
 402 {
 403     m_readsAddressableLocation  = false;
 404     m_writesAddressableLocation = false;
 405
 406     m_lclVarReads.Clear();
 407     m_lclVarWrites.Clear();
 408 }
 409
 410 SideEffectSet::SideEffectSet() : m_sideEffectFlags(0), m_aliasSet()
 411 {
 412 }
 413
 414 //------------------------------------------------------------------------
 415 // SideEffectSet::SideEffectSet:
 416 //    Constructs a side effect set initialized using the given node.
 417 //    Equivalent to the following;
 418 //
 419 //       SideEffectSet sideEffectSet;
 420 //       sideEffectSet.AddNode(compiler, node);
 421 //
 422 // Arguments:
 423 //    compiler - The compiler context.
 424 //    node - The node to use for initialization.
 425 //
 426 SideEffectSet::SideEffectSet(Compiler* compiler, GenTree* node) : m_sideEffectFlags(0), m_aliasSet()
 427 {
 428     AddNode(compiler, node);
 429 }
 430
 431 //------------------------------------------------------------------------
 432 // SideEffectSet::AddNode:
 433 //    Adds the given node's accesses to this SideEffectSet.
 434 //
 435 // Arguments:
 436 //    compiler - The compiler context.
 437 //    node - The node to add to the set.
 438 //
 439 void SideEffectSet::AddNode(Compiler* compiler, GenTree* node)
 440 {
 441     m_sideEffectFlags |= (node->gtFlags & GTF_ALL_EFFECT);
 442     m_aliasSet.AddNode(compiler, node);
 443 }
 444
 445 //------------------------------------------------------------------------
 446 // SideEffectSet::InterferesWith:
 447 //    Returns true if the side effects in this set interfere with the
 448 //    given side effect flags and alias information.
 449 //
 450 //    Two side effect sets interfere under any of the following
 451 //    conditions:
 452 //    - If the analysis is strict, and:
 453 //        - Either set contains a compiler barrier, or
 454 //        - Both sets produce an exception
 455 //    - Whether or not the analysis is strict:
 456 //        - One set produces an exception and the other set contains a
 457 //          write
 458 //        - One set's reads and writes interfere with the other set's
 459 //          reads and writes
 460 //
 461 // Arguments:
 462 //    otherSideEffectFlags - The side effect flags for the other side
 463 //                           effect set.
 464 //    otherAliasInfo - The alias information for the other side effect
 465 //                     set.
 466 //    strict - True if the analysis should be strict as described above.
 467 //
 468 template <typename TOtherAliasInfo>
 469 bool SideEffectSet::InterferesWith(unsigned               otherSideEffectFlags,
 470                                    const TOtherAliasInfo& otherAliasInfo,
 471                                    bool                   strict) const
 472 {
 473     const bool thisProducesException  = (m_sideEffectFlags & GTF_EXCEPT) != 0;
 474     const bool otherProducesException = (otherSideEffectFlags & GTF_EXCEPT) != 0;
 475
 476     if (strict)
 477     {
 478         // If either set contains a compiler barrier, the sets interfere.
 479         if (((m_sideEffectFlags | otherSideEffectFlags) & GTF_ORDER_SIDEEFF) != 0)
 480         {
 481             return true;
 482         }
 483
 484         // If both sets produce an exception, the sets interfere.
 485         if (thisProducesException && otherProducesException)
 486         {
 487             return true;
 488         }
 489     }
 490
 491     // If one set produces an exception and the other set writes to any location, the sets interfere.
 492     if ((thisProducesException && otherAliasInfo.WritesAnyLocation()) ||
 493         (otherProducesException && m_aliasSet.WritesAnyLocation()))
 494     {
 495         return true;
 496     }
 497
 498     // At this point, the only interference between the sets will arise from their alias sets.
 499     return m_aliasSet.InterferesWith(otherAliasInfo);
 500 }
 501
 502 //------------------------------------------------------------------------
 503 // SideEffectSet::InterferesWith:
 504 //    Returns true if the side effects in this set interfere with the side
 505 //    effects in the given side effect set.
 506 //
 507 //    Two side effect sets interfere under any of the following
 508 //    conditions:
 509 //    - If the analysis is strict, and:
 510 //        - Either set contains a compiler barrier, or
 511 //        - Both sets produce an exception
 512 //    - Whether or not the analysis is strict:
 513 //        - One set produces an exception and the other set contains a
 514 //          write
 515 //        - One set's reads and writes interfere with the other set's
 516 //          reads and writes
 517 //
 518 // Arguments:
 519 //    other - The other side effect set.
 520 //    strict - True if the analysis should be strict as described above.
 521 //
 522 bool SideEffectSet::InterferesWith(const SideEffectSet& other, bool strict) const
 523 {
 524     return InterferesWith(other.m_sideEffectFlags, other.m_aliasSet, strict);
 525 }
 526
 527 //------------------------------------------------------------------------
 528 // SideEffectSet::InterferesWith:
 529 //    Returns true if the side effects in this set interfere with the side
 530 //    effects for the given node.
 531 //
 532 //    A side effect set interferes with a given node iff it interferes
 533 //    with the side effect set of the node.
 534 //
 535 // Arguments:
 536 //    compiler - The compiler context.
 537 //    node - The node in question.
 538 //    strict - True if the analysis should be strict as described above.
 539 //
 540 bool SideEffectSet::InterferesWith(Compiler* compiler, GenTree* node, bool strict) const
 541 {
 542     return InterferesWith((node->gtFlags & GTF_ALL_EFFECT), AliasSet::NodeInfo(compiler, node), strict);
 543 }
 544
 545 //------------------------------------------------------------------------
 546 // SideEffectSet::Clear:
 547 //    Clears the current side effect set.
 548 //
 549 void SideEffectSet::Clear()
 550 {
 551     m_sideEffectFlags = 0;
 552     m_aliasSet.Clear();
 553 }