Change gtExtractSideEffList to use GenTreeVisitor (#18257)

* Change gtExtractSideEffList to use GenTreeVisitor

The tree traversal logic in gtExtractSideEffList is basically an incomplete duplicate of GenTreeVisitor's traversal logic. It lacks handling for GT_ARR_ELEM and GT_ARR_OFFSET so if this are encountered any side effects their children may have are silently dropped.

In addition, side effect ordering was not always preserved. The comma list is built by prepending nodes to it so side effects have to be visited in reverse execution order. The old code did this only for simple opers, for special nodes such as GT_ARR_BOUNDS_CHECK normal execution order was used.

This actually complicates a bit the GenTreeVisitor implementation as side effects need to be first stored in an array. The number of side effects is usually small (<= 4) so this shouldn't be a problem.

* Use GTF_SIDE_EFFECT in optPrepareTreeForReplacement

Assertion propagation doesn't have any way to ensure that it is safe to remove class constructor calls so GTF_PERSISTENT_SIDE_EFFECTS_IN_CSE should not be used here.

Likewise, GTF_EXCEPT side effects must be preserved as well. VN doesn't always propagate exceptions so it's possible to end up with a tree that has a constant VN and contains exception side effects.

* Add tests for 18232

* CR feedback

3 files changed, 123 insertions, 125 deletions

diff --git a/src/jit/assertionprop.cpp b/src/jit/assertionprop.cpp
index 51b39470b1..d4153a287e 100644
--- a/src/jit/assertionprop.cpp
+++ b/src/jit/assertionprop.cpp
@@ -4605,18 +4605,40 @@ GenTree* Compiler::optPrepareTreeForReplacement(GenTree* oldTree, GenTree* newTr
 {
     // If we have side effects, extract them and append newTree to the list.
     GenTree* sideEffList = nullptr;
-    if (oldTree->gtFlags & GTF_PERSISTENT_SIDE_EFFECTS)
+    if ((oldTree->gtFlags & GTF_SIDE_EFFECT) != 0)
     {
-        gtExtractSideEffList(oldTree, &sideEffList, GTF_PERSISTENT_SIDE_EFFECTS_IN_CSE);
+        bool ignoreRoot = false;
+
+        if (oldTree == newTree)
+        {
+            // If the caller passed the same tree as both old and new then it means
+            // that it expects that the root of the tree has no side effects and it
+            // won't be extracted. Otherwise the resulting comma tree would be invalid,
+            // having both op1 and op2 point to the same tree.
+            //
+            // Do a sanity check to ensure persistent side effects aren't discarded and
+            // tell gtExtractSideEffList to ignore the root of the tree.
+            assert(!gtNodeHasSideEffects(oldTree, GTF_PERSISTENT_SIDE_EFFECTS));
+            //
+            // Exception side effects may be ignored if the root is known to be a constant
+            // (e.g. VN may evaluate a DIV/MOD node to a constant and the node may still
+            // have GTF_EXCEPT set, even if it does not actually throw any exceptions).
+            assert(!gtNodeHasSideEffects(oldTree, GTF_EXCEPT) ||
+                   vnStore->IsVNConstant(oldTree->gtVNPair.GetConservative()));
+
+            ignoreRoot = true;
+        }
+
+        gtExtractSideEffList(oldTree, &sideEffList, GTF_SIDE_EFFECT, ignoreRoot);
     }
-    if (sideEffList)
+    if (sideEffList != nullptr)
     {
-        noway_assert(sideEffList->gtFlags & GTF_SIDE_EFFECT);
+        noway_assert((sideEffList->gtFlags & GTF_SIDE_EFFECT) != 0);
 
         // Increment the ref counts as we want to keep the side effects.
         lvaRecursiveIncRefCounts(sideEffList);
 
-        if (newTree)
+        if (newTree != nullptr)
         {
             newTree = gtNewOperNode(GT_COMMA, newTree->TypeGet(), sideEffList, newTree);
         }
diff --git a/src/jit/compmemkind.h b/src/jit/compmemkind.h
index bd8483d13a..1dfa015f94 100644
--- a/src/jit/compmemkind.h
+++ b/src/jit/compmemkind.h
@@ -53,6 +53,7 @@ CompMemKindMacro(LoopHoist)
 CompMemKindMacro(Unknown)
 CompMemKindMacro(RangeCheck)
 CompMemKindMacro(CopyProp)
+CompMemKindMacro(SideEffects)
 //clang-format on
 
 #undef CompMemKindMacro
diff --git a/src/jit/gentree.cpp b/src/jit/gentree.cpp
index 946b52aec3..af59dfe000 100644
--- a/src/jit/gentree.cpp
+++ b/src/jit/gentree.cpp
@@ -14947,6 +14947,13 @@ bool Compiler::gtNodeHasSideEffects(GenTree* tree, unsigned flags)
 {
     if (flags & GTF_ASG)
     {
+        // TODO-Cleanup: This only checks for GT_ASG but according to OperRequiresAsgFlag there
+        // are many more opers that are considered to have an assignment side effect: atomic ops
+        // (GT_CMPXCHG & co.), GT_MEMORYBARRIER (not classified as an atomic op) and HW intrinsic
+        // memory stores. Atomic ops have special handling in gtExtractSideEffList but the others
+        // will simply be dropped is they are ever subject to an "extract side effects" operation.
+        // It is possible that the reason no bugs have yet been observed in this area is that the
+        // other nodes are likely to always be tree roots.
         if (tree->OperIsAssignment())
         {
             return true;
@@ -15113,157 +15120,125 @@ GenTree* Compiler::gtBuildCommaList(GenTree* list, GenTree* expr)
     }
 }
 
-/*****************************************************************************
- *
- *  Extracts side effects from the given expression
- *  and appends them to a given list (actually a GT_COMMA list)
- *  If ignore root is specified, the method doesn't treat the top
- *  level tree node as having side-effect.
- */
-
+//------------------------------------------------------------------------
+// gtExtractSideEffList: Extracts side effects from the given expression.
+//
+// Arguments:
+//    expr       - the expression tree to extract side effects from
+//    pList      - pointer to a (possibly null) GT_COMMA list that
+//                 will contain the extracted side effects
+//    flags      - side effect flags to be considered
+//    ignoreRoot - ignore side effects on the expression root node
+//
+// Notes:
+//    Side effects are prepended to the GT_COMMA list such that op1 of
+//    each comma node holds the side effect tree and op2 points to the
+//    next comma node. The original side effect execution order is preserved.
+//
 void Compiler::gtExtractSideEffList(GenTree*  expr,
                                     GenTree** pList,
                                     unsigned  flags /* = GTF_SIDE_EFFECT*/,
                                     bool      ignoreRoot /* = false */)
 {
-    assert(expr);
-    assert(expr->gtOper != GT_STMT);
-
-    /* If no side effect in the expression return */
-
-    if (!gtTreeHasSideEffects(expr, flags))
-    {
-        return;
-    }
-
-    genTreeOps oper = expr->OperGet();
-    unsigned   kind = expr->OperKind();
-
-    // Look for any side effects that we care about
-    //
-    if (!ignoreRoot && gtNodeHasSideEffects(expr, flags))
-    {
-        // Add the side effect to the list and return
-        //
-        *pList = gtBuildCommaList(*pList, expr);
-        return;
-    }
-
-    if (kind & GTK_LEAF)
-    {
-        return;
-    }
-
-    if (oper == GT_LOCKADD || oper == GT_XADD || oper == GT_XCHG || oper == GT_CMPXCHG)
-    {
-        // These operations are kind of important to keep
-        *pList = gtBuildCommaList(*pList, expr);
-        return;
-    }
-
-    if (kind & GTK_SMPOP)
+    class SideEffectExtractor final : public GenTreeVisitor<SideEffectExtractor>
     {
-        GenTree* op1 = expr->gtOp.gtOp1;
-        GenTree* op2 = expr->gtGetOp2IfPresent();
+    public:
+        const unsigned       m_flags;
+        ArrayStack<GenTree*> m_sideEffects;
 
-        if (flags & GTF_EXCEPT)
+        enum
         {
-            // Special case - GT_ADDR of GT_IND nodes of TYP_STRUCT
-            // have to be kept together
-
-            if (oper == GT_ADDR && op1->OperIsIndir() && op1->gtType == TYP_STRUCT)
-            {
-                *pList = gtBuildCommaList(*pList, expr);
+            DoPreOrder        = true,
+            UseExecutionOrder = true
+        };
 
-#ifdef DEBUG
-                if (verbose)
-                {
-                    printf("Keep the GT_ADDR and GT_IND together:\n");
-                }
-#endif
-                return;
-            }
+        SideEffectExtractor(Compiler* compiler, unsigned flags)
+            : GenTreeVisitor(compiler), m_flags(flags), m_sideEffects(compiler->getAllocator(CMK_SideEffects))
+        {
         }
 
-        /* Continue searching for side effects in the subtrees of the expression
-         * NOTE: Be careful to preserve the right ordering - side effects are prepended
-         * to the list */
-
-        /* Continue searching for side effects in the subtrees of the expression
-         * NOTE: Be careful to preserve the right ordering
-         * as side effects are prepended to the list */
-
-        if (expr->gtFlags & GTF_REVERSE_OPS)
+        fgWalkResult PreOrderVisit(GenTree** use, GenTree* user)
         {
-            assert(oper != GT_COMMA);
-            if (op1)
+            GenTree* node = *use;
+
+            if (!m_compiler->gtTreeHasSideEffects(node, m_flags))
             {
-                gtExtractSideEffList(op1, pList, flags);
+                return Compiler::WALK_SKIP_SUBTREES;
             }
-            if (op2)
+
+            if (m_compiler->gtNodeHasSideEffects(node, m_flags))
             {
-                gtExtractSideEffList(op2, pList, flags);
+                m_sideEffects.Push(node);
+                return Compiler::WALK_SKIP_SUBTREES;
             }
-        }
-        else
-        {
-            if (op2)
+
+            // TODO-Cleanup: These have GTF_ASG set but for some reason gtNodeHasSideEffects ignores
+            // them. See the related gtNodeHasSideEffects comment as well.
+            // Also, these nodes must always be preserved, no matter what side effect flags are passed
+            // in. But then it should never be the case that gtExtractSideEffList gets called without
+            // specifying GTF_ASG so there doesn't seem to be any reason to be inconsistent with
+            // gtNodeHasSideEffects and make this check unconditionally.
+            if (node->OperIsAtomicOp())
             {
-                gtExtractSideEffList(op2, pList, flags);
+                m_sideEffects.Push(node);
+                return Compiler::WALK_SKIP_SUBTREES;
             }
-            if (op1)
+
+            if ((m_flags & GTF_EXCEPT) != 0)
             {
-                gtExtractSideEffList(op1, pList, flags);
+                // Special case - GT_ADDR of GT_IND nodes of TYP_STRUCT have to be kept together.
+                if (node->OperIs(GT_ADDR) && node->gtGetOp1()->OperIsIndir() &&
+                    (node->gtGetOp1()->TypeGet() == TYP_STRUCT))
+                {
+#ifdef DEBUG
+                    if (m_compiler->verbose)
+                    {
+                        printf("Keep the GT_ADDR and GT_IND together:\n");
+                    }
+#endif
+                    m_sideEffects.Push(node);
+                    return Compiler::WALK_SKIP_SUBTREES;
+                }
             }
-        }
-    }
 
-    if (expr->OperGet() == GT_CALL)
-    {
-        // Generally all GT_CALL nodes are considered to have side-effects.
-        // So if we get here it must be a Helper call that we decided does
-        // not have side effects that we needed to keep
-        //
-        assert(expr->gtCall.gtCallType == CT_HELPER);
+            // Generally all GT_CALL nodes are considered to have side-effects.
+            // So if we get here it must be a helper call that we decided it does
+            // not have side effects that we needed to keep.
+            assert(!node->OperIs(GT_CALL) || (node->AsCall()->gtCallType == CT_HELPER));
 
-        // We can remove this Helper call, but there still could be
-        // side-effects in the arguments that we may need to keep
-        //
-        GenTree* args;
-        for (args = expr->gtCall.gtCallArgs; args; args = args->gtOp.gtOp2)
-        {
-            assert(args->OperIsList());
-            gtExtractSideEffList(args->Current(), pList, flags);
+            return Compiler::WALK_CONTINUE;
         }
-        for (args = expr->gtCall.gtCallLateArgs; args; args = args->gtOp.gtOp2)
+    };
+
+    assert(!expr->OperIs(GT_STMT));
+
+    SideEffectExtractor extractor(this, flags);
+
+    if (ignoreRoot)
+    {
+        for (GenTree* op : expr->Operands())
         {
-            assert(args->OperIsList());
-            gtExtractSideEffList(args->Current(), pList, flags);
+            extractor.WalkTree(&op, nullptr);
         }
     }
-
-    if (expr->OperGet() == GT_ARR_BOUNDS_CHECK
-#ifdef FEATURE_SIMD
-        || expr->OperGet() == GT_SIMD_CHK
-#endif // FEATURE_SIMD
-#ifdef FEATURE_HW_INTRINSICS
-        || expr->OperGet() == GT_HW_INTRINSIC_CHK
-#endif // FEATURE_HW_INTRINSICS
-        )
+    else
     {
-        gtExtractSideEffList(expr->AsBoundsChk()->gtIndex, pList, flags);
-        gtExtractSideEffList(expr->AsBoundsChk()->gtArrLen, pList, flags);
+        extractor.WalkTree(&expr, nullptr);
     }
 
-    if (expr->OperGet() == GT_DYN_BLK || expr->OperGet() == GT_STORE_DYN_BLK)
+    GenTree* list = *pList;
+
+    // The extractor returns side effects in execution order but gtBuildCommaList prepends
+    // to the comma-based side effect list so we have to build the list in reverse order.
+    // This is also why the list cannot be built while traversing the tree.
+    // The number of side effects is usually small (<= 4), less than the ArrayStack's
+    // built-in size, so memory allocation is avoided.
+    while (extractor.m_sideEffects.Height() > 0)
     {
-        if (expr->AsDynBlk()->Data() != nullptr)
-        {
-            gtExtractSideEffList(expr->AsDynBlk()->Data(), pList, flags);
-        }
-        gtExtractSideEffList(expr->AsDynBlk()->Addr(), pList, flags);
-        gtExtractSideEffList(expr->AsDynBlk()->gtDynamicSize, pList, flags);
+        list = gtBuildCommaList(list, extractor.m_sideEffects.Pop());
     }
+
+    *pList = list;
 }
 
 /*****************************************************************************