Static size inference for JavaScript objects
[WebKit-https.git] / Source / JavaScriptCore / bytecompiler / StaticPropertyAnalyzer.h
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
32 namespace 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.
37 class StaticPropertyAnalyzer {
38 public:
39     StaticPropertyAnalyzer(Vector<UnlinkedInstruction>*);
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
49 private:
50     void kill(StaticPropertyAnalysis*);
51
52     Vector<UnlinkedInstruction>* m_instructions;
53     typedef HashMap<int, RefPtr<StaticPropertyAnalysis>, WTF::IntHash<int>, WTF::UnsignedWithZeroKeyHashTraits<int> > AnalysisMap;
54     AnalysisMap m_analyses;
55 };
56
57 inline StaticPropertyAnalyzer::StaticPropertyAnalyzer(Vector<UnlinkedInstruction>* instructions)
58     : m_instructions(instructions)
59 {
60 }
61
62 inline 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
69 inline 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
79 inline void StaticPropertyAnalyzer::putById(int dst, unsigned propertyIndex)
80 {
81     StaticPropertyAnalysis* analysis = m_analyses.get(dst).get();
82     if (!analysis)
83         return;
84     analysis->addPropertyIndex(propertyIndex);
85 }
86
87 inline 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
102 inline 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
111 inline 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
162 inline 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