Repository: dotnet/runtime
File: src/coreclr/jit/lowerwasm.cpp (C++)

Code before:
                        prev = StackifyTree(prev);
                        continue;
                    }

                    // At this point, we'll have to modify the IR in some way. In general, these cases should be quite
                    // rare, introduced in lowering only. All HIR-induced cases (such as from "gtSetEvalOrder") should
                    // instead be ifdef-ed out for WASM.
                    m_anyChanges = true;

                    // Invariant nodes can be safely moved by the stackifier with no side effects.
                    // For other nodes, the side effects would require us to turn them into a temporary local, but this
                    //  is not possible for contained nodes like an IND inside a STORE_BLK. However, the few types of
                    //  contained nodes we have in Wasm should be safe to move freely since the lack of 'dup' or
                    //  persistent registers in Wasm means that the actual codegen will trigger the side effect(s) and
                    //  store the result into a Wasm local for any later uses during the containing node's execution,
                    //  i.e. cpobj where the src and dest get stashed at the start and then used as add operands
                    //  repeatedly.
                    // Locals can also be safely moved as long as they aren't address-exposed due to local var nodes
                    // being
                    //  implicitly pseudo-contained.
                    // TODO-WASM: Verify that it is actually safe to do this for all contained nodes.
                    if (
                        m_lower->IsInvariantInRange(node, prev->gtNext) ||
                        node->isContained() ||
                        (node->OperIs(GT_LCL_VAR) &&
                         !m_lower->m_compiler->lvaGetDesc(node->AsLclVarCommon())->IsAddressExposed()))
                    {
                        JITDUMP("Stackifier moving node [%06u] after [%06u]\n", Compiler::dspTreeID(node),
                                Compiler::dspTreeID(prev));
                        m_lower->BlockRange().Remove(node);
                        m_lower->BlockRange().InsertAfter(prev, node);
                        break;
                    }

                    /*
                    else
                    {
                        // To resolve this scenario we have two options:
                        // 1. We try moving the whole tree rooted at `node`.
                        //    To avoid quadratic behavior, we first stackify it and collect all the side effects
                        //    from it. Then we check for interference of those side effects with nodes between
                        //    'node' and 'prev'.
                        // 2. Failing that, we insert a temporary ('ReplaceWithLclVar') for 'node'.
                        //    To avoid explosion of temporaries, we maintain a busy/free set of them.
                        // For now, for simplicity we are implementing #2 only.

                        LIR::Use nodeUse;
                        // FIXME-WASM: TryGetUse is inefficient here, replace it with something more optimal
                        if (!m_lower->BlockRange().TryGetUse(node, &nodeUse))
                        {
                            JITDUMP("node==[%06u] prev==[%06u]\n", Compiler::dspTreeID(node),

Review comment (suggestion):
```suggestion
                    if (CanMove(node))
```
Let's move into its own method so that the top-level algorithm doesn't get cluttered.

Also `IsInvariantInRange` is NOT needed for these hand-picked special case conditions. That's kind of the point, to avoid the checking of `IsInvariantInRange`.

The general version of this could indeed be built on top of `IsInvariantInRange`, but it would be quadratic (this is what `...avoid quadratic behavior...` refers to).

Code after:

            // Simple greedy algorithm working backwards. The invariant is that the stack top must be placed right next
            // to (in normal linear order - before) the node we last stackified.
            stack->Push(root);
            GenTree* current = root->gtNext;
            while (stack->Height() != initialDepth)
            {
                GenTree* node = stack->Pop();
                GenTree* prev = (current != nullptr) ? current->gtPrev : root;
                while (node != prev)
                {
                    // Maybe this is an intervening void-equivalent node that we can also just stackify.
                    if (IsDataFlowRoot(prev))
                    {
                        prev = StackifyTree(prev);
                        continue;
                    }

                    // At this point, we'll have to modify the IR in some way. In general, these cases should be quite
                    // rare, introduced in lowering only. All HIR-induced cases (such as from "gtSetEvalOrder") should
                    // instead be ifdef-ed out for WASM.
                    m_anyChanges = true;

                    // Invariant nodes can be safely moved by the stackifier with no side effects.
                    // For other nodes, the side effects would require us to turn them into a temporary local, but this
                    //  is not possible for contained nodes like an IND inside a STORE_BLK. However, the few types of
                    //  contained nodes we have in Wasm should be safe to move freely since the lack of 'dup' or
                    //  persistent registers in Wasm means that the actual codegen will trigger the side effect(s) and
                    //  store the result into a Wasm local for any later uses during the containing node's execution,
                    //  i.e. cpobj where the src and dest get stashed at the start and then used as add operands
                    //  repeatedly.
                    // Locals can also be safely moved as long as they aren't address-exposed due to local var nodes
                    //  being implicitly pseudo-contained.
                    // TODO-WASM: Verify that it is actually safe to do this for all contained nodes.
                    if (CanMoveNodePast(node, prev->gtNext))
                    {
                        JITDUMP("Stackifier moving node [%06u] after [%06u]\n", Compiler::dspTreeID(node),
                                Compiler::dspTreeID(prev));
                        m_lower->BlockRange().Remove(node);
                        m_lower->BlockRange().InsertAfter(prev, node);
                        break;
                    }

                    JITDUMP("node==[%06u] prev==[%06u]\n", Compiler::dspTreeID(node), Compiler::dspTreeID(prev));
                    NYI_WASM("IR not in a stackified form");
                }

                // In stack order, the last operand is closest to its parent, thus put on top here.
                node->VisitOperands([stack](GenTree* operand) {
                    stack->Push(operand);
                    return GenTree::VisitResult::Continue;