2 * Copyright (C) 2013 Apple Inc. All rights reserved.
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
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.
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.
27 #include "DFGBackwardsPropagationPhase.h"
31 #include "DFGBasicBlockInlines.h"
34 #include "Operations.h"
36 namespace JSC
{ namespace DFG
{
38 class BackwardsPropagationPhase
: public Phase
{
40 BackwardsPropagationPhase(Graph
& graph
)
41 : Phase(graph
, "backwards propagation")
47 for (BlockIndex blockIndex
= 0; blockIndex
< m_graph
.m_blocks
.size(); ++blockIndex
) {
48 BasicBlock
* block
= m_graph
.m_blocks
[blockIndex
].get();
52 // Prevent a tower of overflowing additions from creating a value that is out of the
54 m_allowNestedOverflowingAdditions
= block
->size() < (1 << 16);
56 for (unsigned indexInBlock
= block
->size(); indexInBlock
--;)
57 propagate(block
->at(indexInBlock
));
64 bool isNotNegZero(Node
* node
)
66 if (!m_graph
.isNumberConstant(node
))
68 double value
= m_graph
.valueOfNumberConstant(node
);
69 return (value
|| 1.0 / value
> 0.0);
72 bool isNotPosZero(Node
* node
)
74 if (!m_graph
.isNumberConstant(node
))
76 double value
= m_graph
.valueOfNumberConstant(node
);
77 return (value
|| 1.0 / value
< 0.0);
80 // Tests if the absolute value is strictly less than the power of two.
82 bool isWithinPowerOfTwoForConstant(Node
* node
)
84 JSValue immediateValue
= node
->valueOfJSConstant(codeBlock());
85 if (!immediateValue
.isNumber())
87 double immediate
= immediateValue
.asNumber();
88 return immediate
> -(static_cast<int64_t>(1) << power
) && immediate
< (static_cast<int64_t>(1) << power
);
92 bool isWithinPowerOfTwoNonRecursive(Node
* node
)
94 if (node
->op() != JSConstant
)
96 return isWithinPowerOfTwoForConstant
<power
>(node
);
100 bool isWithinPowerOfTwo(Node
* node
)
102 switch (node
->op()) {
104 return isWithinPowerOfTwoForConstant
<power
>(node
);
111 return isWithinPowerOfTwoNonRecursive
<power
>(node
->child1().node())
112 || isWithinPowerOfTwoNonRecursive
<power
>(node
->child2().node());
127 Node
* shiftAmount
= node
->child2().node();
128 if (shiftAmount
->op() != JSConstant
)
130 JSValue immediateValue
= shiftAmount
->valueOfJSConstant(codeBlock());
131 if (!immediateValue
.isInt32())
133 return immediateValue
.asInt32() > 32 - power
;
142 bool isWithinPowerOfTwo(Edge edge
)
144 return isWithinPowerOfTwo
<power
>(edge
.node());
147 bool mergeDefaultFlags(Node
* node
)
149 bool changed
= false;
150 if (node
->flags() & NodeHasVarArgs
) {
151 for (unsigned childIdx
= node
->firstChild();
152 childIdx
< node
->firstChild() + node
->numChildren();
154 if (!!m_graph
.m_varArgChildren
[childIdx
])
155 changed
|= m_graph
.m_varArgChildren
[childIdx
]->mergeFlags(NodeUsedAsValue
);
160 changed
|= node
->child1()->mergeFlags(NodeUsedAsValue
);
163 changed
|= node
->child2()->mergeFlags(NodeUsedAsValue
);
166 changed
|= node
->child3()->mergeFlags(NodeUsedAsValue
);
171 void propagate(Node
* node
)
173 NodeFlags flags
= node
->flags() & NodeBackPropMask
;
175 switch (node
->op()) {
177 VariableAccessData
* variableAccessData
= node
->variableAccessData();
178 variableAccessData
->mergeFlags(flags
);
183 VariableAccessData
* variableAccessData
= node
->variableAccessData();
184 if (!variableAccessData
->isLoadedFrom())
186 node
->child1()->mergeFlags(NodeUsedAsValue
);
197 flags
|= NodeUsedAsInt
;
198 flags
&= ~(NodeUsedAsNumber
| NodeNeedsNegZero
| NodeUsedAsOther
);
199 node
->child1()->mergeFlags(flags
);
200 node
->child2()->mergeFlags(flags
);
205 flags
|= NodeUsedAsInt
;
206 flags
&= ~(NodeUsedAsNumber
| NodeNeedsNegZero
| NodeUsedAsOther
);
207 node
->child1()->mergeFlags(flags
);
211 case StringCharCodeAt
: {
212 node
->child1()->mergeFlags(NodeUsedAsValue
);
213 node
->child2()->mergeFlags(NodeUsedAsValue
| NodeUsedAsInt
);
218 case UInt32ToNumber
: {
219 node
->child1()->mergeFlags(flags
);
224 if (isNotNegZero(node
->child1().node()) || isNotNegZero(node
->child2().node()))
225 flags
&= ~NodeNeedsNegZero
;
226 if (node
->child1()->hasNumberResult() || node
->child2()->hasNumberResult())
227 flags
&= ~NodeUsedAsOther
;
228 if (!isWithinPowerOfTwo
<32>(node
->child1()) && !isWithinPowerOfTwo
<32>(node
->child2()))
229 flags
|= NodeUsedAsNumber
;
230 if (!m_allowNestedOverflowingAdditions
)
231 flags
|= NodeUsedAsNumber
;
233 node
->child1()->mergeFlags(flags
);
234 node
->child2()->mergeFlags(flags
);
239 if (isNotNegZero(node
->child1().node()) || isNotNegZero(node
->child2().node()))
240 flags
&= ~NodeNeedsNegZero
;
241 if (!isWithinPowerOfTwo
<32>(node
->child1()) && !isWithinPowerOfTwo
<32>(node
->child2()))
242 flags
|= NodeUsedAsNumber
;
243 if (!m_allowNestedOverflowingAdditions
)
244 flags
|= NodeUsedAsNumber
;
246 node
->child1()->mergeFlags(flags
);
247 node
->child2()->mergeFlags(flags
);
252 if (isNotNegZero(node
->child1().node()) || isNotPosZero(node
->child2().node()))
253 flags
&= ~NodeNeedsNegZero
;
254 if (!isWithinPowerOfTwo
<32>(node
->child1()) && !isWithinPowerOfTwo
<32>(node
->child2()))
255 flags
|= NodeUsedAsNumber
;
256 if (!m_allowNestedOverflowingAdditions
)
257 flags
|= NodeUsedAsNumber
;
259 node
->child1()->mergeFlags(flags
);
260 node
->child2()->mergeFlags(flags
);
265 flags
&= ~NodeUsedAsOther
;
267 node
->child1()->mergeFlags(flags
);
272 // As soon as a multiply happens, we can easily end up in the part
273 // of the double domain where the point at which you do truncation
274 // can change the outcome. So, ArithMul always forces its inputs to
275 // check for overflow. Additionally, it will have to check for overflow
276 // itself unless we can prove that there is no way for the values
277 // produced to cause double rounding.
279 if (!isWithinPowerOfTwo
<22>(node
->child1().node())
280 && !isWithinPowerOfTwo
<22>(node
->child2().node()))
281 flags
|= NodeUsedAsNumber
;
283 node
->mergeFlags(flags
);
285 flags
|= NodeUsedAsNumber
| NodeNeedsNegZero
;
286 flags
&= ~NodeUsedAsOther
;
288 node
->child1()->mergeFlags(flags
);
289 node
->child2()->mergeFlags(flags
);
294 flags
|= NodeUsedAsNumber
| NodeNeedsNegZero
;
295 flags
&= ~NodeUsedAsOther
;
297 node
->child1()->mergeFlags(flags
);
298 node
->child2()->mergeFlags(flags
);
303 flags
|= NodeUsedAsNumber
| NodeNeedsNegZero
;
304 flags
&= ~NodeUsedAsOther
;
306 node
->child1()->mergeFlags(flags
);
307 node
->child2()->mergeFlags(flags
);
312 node
->child1()->mergeFlags(NodeUsedAsValue
);
313 node
->child2()->mergeFlags(NodeUsedAsNumber
| NodeUsedAsOther
| NodeUsedAsInt
);
317 case GetMyArgumentByValSafe
: {
318 node
->child1()->mergeFlags(NodeUsedAsNumber
| NodeUsedAsOther
| NodeUsedAsInt
);
322 case NewArrayWithSize
: {
323 node
->child1()->mergeFlags(NodeUsedAsValue
| NodeUsedAsInt
);
328 node
->child1()->mergeFlags(NodeUsedAsValue
);
329 node
->child2()->mergeFlags(NodeUsedAsValue
| NodeUsedAsInt
);
334 node
->child1()->mergeFlags(NodeUsedAsNumber
| NodeUsedAsOther
);
339 node
->child1()->mergeFlags(flags
);
344 m_graph
.varArgChild(node
, 0)->mergeFlags(NodeUsedAsValue
);
345 m_graph
.varArgChild(node
, 1)->mergeFlags(NodeUsedAsNumber
| NodeUsedAsOther
| NodeUsedAsInt
);
346 m_graph
.varArgChild(node
, 2)->mergeFlags(NodeUsedAsValue
);
351 mergeDefaultFlags(node
);
356 bool m_allowNestedOverflowingAdditions
;
359 bool performBackwardsPropagation(Graph
& graph
)
361 SamplingRegion
samplingRegion("DFG Backwards Propagation Phase");
362 return runPhase
<BackwardsPropagationPhase
>(graph
);
365 } } // namespace JSC::DFG
367 #endif // ENABLE(DFG_JIT)