1/*
2 * Copyright (C) 2015-2019 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#pragma once
27
28#include "DFGCombinedLiveness.h"
29#include "DFGGraph.h"
30#include "DFGOSRAvailabilityAnalysisPhase.h"
31#include "FullBytecodeLiveness.h"
32
33namespace JSC { namespace DFG {
34
35// Utilities for finding the last points where a node is live in DFG SSA. This accounts for liveness due
36// to OSR exit. This is usually used for enumerating over all of the program points where a node is live,
37// by exploring all blocks where the node is live at tail and then exploring all program points where the
38// node is killed. A prerequisite to using these utilities is having liveness and OSR availability
39// computed.
40
41// This tells you those things that die on the boundary between nodeBefore and nodeAfter. It is
42// conservative in the sense that it might resort to telling you some things that are still live at
43// nodeAfter.
44template<typename Functor>
45void forAllKilledOperands(Graph& graph, Node* nodeBefore, Node* nodeAfter, const Functor& functor)
46{
47 CodeOrigin before = nodeBefore->origin.forExit;
48
49 if (!nodeAfter) {
50 graph.forAllLiveInBytecode(before, functor);
51 return;
52 }
53
54 CodeOrigin after = nodeAfter->origin.forExit;
55
56 VirtualRegister alreadyNoted;
57 // If we MovHint something that is live at the time, then we kill the old value.
58 if (nodeAfter->containsMovHint()) {
59 VirtualRegister reg = nodeAfter->unlinkedLocal();
60 if (graph.isLiveInBytecode(reg, after)) {
61 functor(reg);
62 alreadyNoted = reg;
63 }
64 }
65
66 if (before == after)
67 return;
68
69 // It's easier to do this if the inline call frames are the same. This is way faster than the
70 // other loop, below.
71 auto* beforeInlineCallFrame = before.inlineCallFrame();
72 if (beforeInlineCallFrame == after.inlineCallFrame()) {
73 int stackOffset = beforeInlineCallFrame ? beforeInlineCallFrame->stackOffset : 0;
74 CodeBlock* codeBlock = graph.baselineCodeBlockFor(beforeInlineCallFrame);
75 FullBytecodeLiveness& fullLiveness = graph.livenessFor(codeBlock);
76 const FastBitVector& liveBefore = fullLiveness.getLiveness(before.bytecodeIndex());
77 const FastBitVector& liveAfter = fullLiveness.getLiveness(after.bytecodeIndex());
78
79 (liveBefore & ~liveAfter).forEachSetBit(
80 [&] (size_t relativeLocal) {
81 functor(virtualRegisterForLocal(relativeLocal) + stackOffset);
82 });
83 return;
84 }
85
86 // Detect kills the super conservative way: it is killed if it was live before and dead after.
87 BitVector liveAfter = graph.localsLiveInBytecode(after);
88 graph.forAllLocalsLiveInBytecode(
89 before,
90 [&] (VirtualRegister reg) {
91 if (reg == alreadyNoted)
92 return;
93 if (liveAfter.get(reg.toLocal()))
94 return;
95 functor(reg);
96 });
97}
98
99// Tells you all of the nodes that would no longer be live across the node at this nodeIndex.
100template<typename Functor>
101void forAllKilledNodesAtNodeIndex(
102 Graph& graph, AvailabilityMap& availabilityMap, BasicBlock* block, unsigned nodeIndex,
103 const Functor& functor)
104{
105 static constexpr unsigned seenInClosureFlag = 1;
106 static constexpr unsigned calledFunctorFlag = 2;
107 HashMap<Node*, unsigned> flags;
108
109 Node* node = block->at(nodeIndex);
110
111 graph.doToChildren(
112 node,
113 [&] (Edge edge) {
114 if (edge.doesKill()) {
115 auto& result = flags.add(edge.node(), 0).iterator->value;
116 if (!(result & calledFunctorFlag)) {
117 functor(edge.node());
118 result |= calledFunctorFlag;
119 }
120 }
121 });
122
123 Node* before = nullptr;
124 if (nodeIndex)
125 before = block->at(nodeIndex - 1);
126
127 forAllKilledOperands(
128 graph, before, node,
129 [&] (VirtualRegister reg) {
130 availabilityMap.closeStartingWithLocal(
131 reg,
132 [&] (Node* node) -> bool {
133 return flags.get(node) & seenInClosureFlag;
134 },
135 [&] (Node* node) -> bool {
136 auto& resultFlags = flags.add(node, 0).iterator->value;
137 bool result = resultFlags & seenInClosureFlag;
138 if (!(resultFlags & calledFunctorFlag))
139 functor(node);
140 resultFlags |= seenInClosureFlag | calledFunctorFlag;
141 return result;
142 });
143 });
144}
145
146// Tells you all of the places to start searching from in a basic block. Gives you the node index at which
147// the value is either no longer live. This pretends that nodes are dead at the end of the block, so that
148// you can use this to do per-basic-block analyses.
149template<typename Functor>
150void forAllKillsInBlock(
151 Graph& graph, const CombinedLiveness& combinedLiveness, BasicBlock* block,
152 const Functor& functor)
153{
154 for (Node* node : combinedLiveness.liveAtTail[block])
155 functor(block->size(), node);
156
157 LocalOSRAvailabilityCalculator localAvailability(graph);
158 localAvailability.beginBlock(block);
159 // Start at the second node, because the functor is expected to only inspect nodes from the start of
160 // the block up to nodeIndex (exclusive), so if nodeIndex is zero then the functor has nothing to do.
161 for (unsigned nodeIndex = 1; nodeIndex < block->size(); ++nodeIndex) {
162 forAllKilledNodesAtNodeIndex(
163 graph, localAvailability.m_availability, block, nodeIndex,
164 [&] (Node* node) {
165 functor(nodeIndex, node);
166 });
167 localAvailability.executeNode(block->at(nodeIndex));
168 }
169}
170
171} } // namespace JSC::DFG
172