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, 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
  49 private:
  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
  57 inline StaticPropertyAnalyzer::StaticPropertyAnalyzer(Vector<UnlinkedInstruction, 0, UnsafeVectorOverflow>* 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);
  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