dfg/DFGForAllKills.h

   1 /*
   2  * Copyright (C) 2015 Apple Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  * 1. Redistributions of source code must retain the above copyright
   8  *    notice, this list of conditions and the following disclaimer.
   9  * 2. Redistributions in binary form must reproduce the above copyright
  10  *    notice, this list of conditions and the following disclaimer in the
  11  *    documentation and/or other materials provided with the distribution.
  12  *
  13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
  14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
  17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
  21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  24  */
  25
  26 #ifndef DFGForAllKills_h
  27 #define DFGForAllKills_h
  28
  29 #include "DFGCombinedLiveness.h"
  30 #include "DFGGraph.h"
  31 #include "DFGOSRAvailabilityAnalysisPhase.h"
  32 #include "FullBytecodeLiveness.h"
  33
  34 namespace JSC { namespace DFG {
  35
  36 // Utilities for finding the last points where a node is live in DFG SSA. This accounts for liveness due
  37 // to OSR exit. This is usually used for enumerating over all of the program points where a node is live,
  38 // by exploring all blocks where the node is live at tail and then exploring all program points where the
  39 // node is killed. A prerequisite to using these utilities is having liveness and OSR availability
  40 // computed.
  41
  42 // This tells you those things that die on the boundary between nodeBefore and nodeAfter. It is
  43 // conservative in the sense that it might resort to telling you some things that are still live at
  44 // nodeAfter.
  45 template<typename Functor>
  46 void forAllKilledOperands(Graph& graph, Node* nodeBefore, Node* nodeAfter, const Functor& functor)
  47 {
  48     CodeOrigin before = nodeBefore->origin.forExit;
  49
  50     if (!nodeAfter) {
  51         graph.forAllLiveInBytecode(before, functor);
  52         return;
  53     }
  54
  55     CodeOrigin after = nodeAfter->origin.forExit;
  56
  57     VirtualRegister alreadyNoted;
  58     if (!!after) {
  59         // If we MovHint something that is live at the time, then we kill the old value.
  60         if (nodeAfter->containsMovHint()) {
  61             VirtualRegister reg = nodeAfter->unlinkedLocal();
  62             if (graph.isLiveInBytecode(reg, after)) {
  63                 functor(reg);
  64                 alreadyNoted = reg;
  65             }
  66         }
  67     }
  68
  69     if (!before) {
  70         if (!after)
  71             return;
  72         // The true before-origin is the origin at predecessors that jump to us. But there can be
  73         // many such predecessors and they will likely all have a different origin. So, it's better
  74         // to do the conservative thing.
  75         graph.forAllLocalsLiveInBytecode(after, functor);
  76         return;
  77     }
  78
  79     if (before == after)
  80         return;
  81
  82     // before could be unset even if after is, but the opposite cannot happen.
  83     ASSERT(!!after);
  84
  85     // It's easier to do this if the inline call frames are the same. This is way faster than the
  86     // other loop, below.
  87     if (before.inlineCallFrame == after.inlineCallFrame) {
  88         int stackOffset = before.inlineCallFrame ? before.inlineCallFrame->stackOffset : 0;
  89         CodeBlock* codeBlock = graph.baselineCodeBlockFor(before.inlineCallFrame);
  90         FullBytecodeLiveness& fullLiveness = graph.livenessFor(codeBlock);
  91         const FastBitVector& liveBefore = fullLiveness.getLiveness(before.bytecodeIndex);
  92         const FastBitVector& liveAfter = fullLiveness.getLiveness(after.bytecodeIndex);
  93
  94         for (unsigned relativeLocal = codeBlock->m_numCalleeRegisters; relativeLocal--;) {
  95             if (liveBefore.get(relativeLocal) && !liveAfter.get(relativeLocal))
  96                 functor(virtualRegisterForLocal(relativeLocal) + stackOffset);
  97         }
  98
  99         return;
 100     }
 101
 102     // Detect kills the super conservative way: it is killed if it was live before and dead after.
 103     BitVector liveAfter = graph.localsLiveInBytecode(after);
 104     graph.forAllLocalsLiveInBytecode(
 105         before,
 106         [&] (VirtualRegister reg) {
 107             if (reg == alreadyNoted)
 108                 return;
 109             if (liveAfter.get(reg.toLocal()))
 110                 return;
 111             functor(reg);
 112         });
 113 }
 114
 115 // Tells you all of the nodes that would no longer be live across the node at this nodeIndex.
 116 template<typename Functor>
 117 void forAllKilledNodesAtNodeIndex(
 118     Graph& graph, AvailabilityMap& availabilityMap, BasicBlock* block, unsigned nodeIndex,
 119     const Functor& functor)
 120 {
 121     static const unsigned seenInClosureFlag = 1;
 122     static const unsigned calledFunctorFlag = 2;
 123     HashMap<Node*, unsigned> flags;
 124
 125     Node* node = block->at(nodeIndex);
 126
 127     graph.doToChildren(
 128         node,
 129         [&] (Edge edge) {
 130             if (edge.doesKill()) {
 131                 auto& result = flags.add(edge.node(), 0).iterator->value;
 132                 if (!(result & calledFunctorFlag)) {
 133                     functor(edge.node());
 134                     result |= calledFunctorFlag;
 135                 }
 136             }
 137         });
 138
 139     Node* before = nullptr;
 140     if (nodeIndex)
 141         before = block->at(nodeIndex - 1);
 142
 143     forAllKilledOperands(
 144         graph, before, node,
 145         [&] (VirtualRegister reg) {
 146             availabilityMap.closeStartingWithLocal(
 147                 reg,
 148                 [&] (Node* node) -> bool {
 149                     return flags.get(node) & seenInClosureFlag;
 150                 },
 151                 [&] (Node* node) -> bool {
 152                     auto& resultFlags = flags.add(node, 0).iterator->value;
 153                     bool result = resultFlags & seenInClosureFlag;
 154                     if (!(resultFlags & calledFunctorFlag))
 155                         functor(node);
 156                     resultFlags |= seenInClosureFlag | calledFunctorFlag;
 157                     return result;
 158                 });
 159         });
 160 }
 161
 162 // Tells you all of the places to start searching from in a basic block. Gives you the node index at which
 163 // the value is either no longer live. This pretends that nodes are dead at the end of the block, so that
 164 // you can use this to do per-basic-block analyses.
 165 template<typename Functor>
 166 void forAllKillsInBlock(
 167     Graph& graph, const CombinedLiveness& combinedLiveness, BasicBlock* block,
 168     const Functor& functor)
 169 {
 170     for (Node* node : combinedLiveness.liveAtTail[block])
 171         functor(block->size(), node);
 172
 173     LocalOSRAvailabilityCalculator localAvailability;
 174     localAvailability.beginBlock(block);
 175     // Start at the second node, because the functor is expected to only inspect nodes from the start of
 176     // the block up to nodeIndex (exclusive), so if nodeIndex is zero then the functor has nothing to do.
 177     for (unsigned nodeIndex = 1; nodeIndex < block->size(); ++nodeIndex) {
 178         forAllKilledNodesAtNodeIndex(
 179             graph, localAvailability.m_availability, block, nodeIndex,
 180             [&] (Node* node) {
 181                 functor(nodeIndex, node);
 182             });
 183         localAvailability.executeNode(block->at(nodeIndex));
 184     }
 185 }
 186
 187 } } // namespace JSC::DFG
 188
 189 #endif // DFGForAllKills_h
 190