1/*
2 * Copyright (C) 2013 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 StaticPropertyAnalyzer_h
27#define StaticPropertyAnalyzer_h
28
29#include "StaticPropertyAnalysis.h"
30#include <wtf/HashMap.h>
31
32namespace JSC {
33
34// Used for flow-insensitive static analysis of the number of properties assigned to an object.
35// We use this analysis with other runtime data to produce an optimization guess. This analysis
36// is understood to be lossy, and it's OK if it turns out to be wrong sometimes.
37class StaticPropertyAnalyzer {
38public:
39    StaticPropertyAnalyzer(Vector<UnlinkedInstruction, 0, UnsafeVectorOverflow>*);
40
41    void createThis(int dst, unsigned offsetOfInlineCapacityOperand);
42    void newObject(int dst, unsigned offsetOfInlineCapacityOperand);
43    void putById(int dst, unsigned propertyIndex); // propertyIndex is an index into a uniqued set of strings.
44    void mov(int dst, int src);
45
46    void kill();
47    void kill(int dst);
48
49private:
50    void kill(StaticPropertyAnalysis*);
51
52    Vector<UnlinkedInstruction, 0, UnsafeVectorOverflow>* m_instructions;
53    typedef HashMap<int, RefPtr<StaticPropertyAnalysis>, WTF::IntHash<int>, WTF::UnsignedWithZeroKeyHashTraits<int>> AnalysisMap;
54    AnalysisMap m_analyses;
55};
56
57inline StaticPropertyAnalyzer::StaticPropertyAnalyzer(Vector<UnlinkedInstruction, 0, UnsafeVectorOverflow>* instructions)
58    : m_instructions(instructions)
59{
60}
61
62inline void StaticPropertyAnalyzer::createThis(int dst, unsigned offsetOfInlineCapacityOperand)
63{
64    AnalysisMap::AddResult addResult = m_analyses.add(
65        dst, StaticPropertyAnalysis::create(m_instructions, offsetOfInlineCapacityOperand));
66    ASSERT_UNUSED(addResult, addResult.isNewEntry); // Can't have two 'this' in the same constructor.
67}
68
69inline void StaticPropertyAnalyzer::newObject(int dst, unsigned offsetOfInlineCapacityOperand)
70{
71    RefPtr<StaticPropertyAnalysis> analysis = StaticPropertyAnalysis::create(m_instructions, offsetOfInlineCapacityOperand);
72    AnalysisMap::AddResult addResult = m_analyses.add(dst, analysis);
73    if (!addResult.isNewEntry) {
74        kill(addResult.iterator->value.get());
75        addResult.iterator->value = analysis.release();
76    }
77}
78
79inline void StaticPropertyAnalyzer::putById(int dst, unsigned propertyIndex)
80{
81    StaticPropertyAnalysis* analysis = m_analyses.get(dst);
82    if (!analysis)
83        return;
84    analysis->addPropertyIndex(propertyIndex);
85}
86
87inline void StaticPropertyAnalyzer::mov(int dst, int src)
88{
89    RefPtr<StaticPropertyAnalysis> analysis = m_analyses.get(src);
90    if (!analysis) {
91        kill(dst);
92        return;
93    }
94
95    AnalysisMap::AddResult addResult = m_analyses.add(dst, analysis);
96    if (!addResult.isNewEntry) {
97        kill(addResult.iterator->value.get());
98        addResult.iterator->value = analysis.release();
99    }
100}
101
102inline void StaticPropertyAnalyzer::kill(StaticPropertyAnalysis* analysis)
103{
104    if (!analysis)
105        return;
106    if (!analysis->hasOneRef()) // Aliases for this object still exist, so it might acquire more properties.
107        return;
108    analysis->record();
109}
110
111inline void StaticPropertyAnalyzer::kill(int dst)
112{
113    // We observe kills in order to avoid piling on properties to an object after
114    // its bytecode register has been recycled.
115
116    // Consider these cases:
117
118    // (1) Aliased temporary
119    // var o1 = { name: name };
120    // var o2 = { name: name };
121
122    // (2) Aliased local -- no control flow
123    // var local;
124    // local = new Object;
125    // local.name = name;
126    // ...
127
128    // local = lookup();
129    // local.didLookup = true;
130    // ...
131
132    // (3) Aliased local -- control flow
133    // var local;
134    // if (condition)
135    //     local = { };
136    // else {
137    //     local = new Object;
138    // }
139    // local.name = name;
140
141    // (Note: our default codegen for "new Object" looks like case (3).)
142
143    // Case (1) is easy because temporaries almost never survive across control flow.
144
145    // Cases (2) and (3) are hard. Case (2) should kill "local", while case (3) should
146    // not. There is no great way to solve these cases with simple static analysis.
147
148    // Since this is a simple static analysis, we just try to catch the simplest cases,
149    // so we accept kills to any registers except for registers that have no inferred
150    // properties yet.
151
152    AnalysisMap::iterator it = m_analyses.find(dst);
153    if (it == m_analyses.end())
154        return;
155    if (!it->value->propertyIndexCount())
156        return;
157
158    kill(it->value.get());
159    m_analyses.remove(it);
160}
161
162inline void StaticPropertyAnalyzer::kill()
163{
164    while (m_analyses.size())
165        kill(m_analyses.take(m_analyses.begin()->key).get());
166}
167
168} // namespace JSC
169
170#endif // StaticPropertyAnalyzer_h
171