1  /*
  2   * Copyright (C) 2014 Apple Inc. All rights reserved.
  3   * Copyright (C) 2014 Saam Barati. <saambarati1@gmail.com>
  4   *
  5   * Redistribution and use in source and binary forms, with or without
  6   * modification, are permitted provided that the following conditions
  7   * are met:
  8   * 1. Redistributions of source code must retain the above copyright
  9   *    notice, this list of conditions and the following disclaimer.
 10   * 2. Redistributions in binary form must reproduce the above copyright
 11   *    notice, this list of conditions and the following disclaimer in the
 12   *    documentation and/or other materials provided with the distribution.
 13   *
 14   * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
 15   * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 16   * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 17   * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
 18   * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 19   * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 20   * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 21   * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
 22   * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 23   * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 24   * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
 25   */
 26  
 27  #include "config.h"
 28  #include "ControlFlowProfiler.h"
 29  
 30  #include "VM.h"
 31  
 32  namespace JSC {
 33  
 34  ControlFlowProfiler::ControlFlowProfiler()
 35      : m_dummyBasicBlock(BasicBlockLocation(-1, -1))
 36  {
 37  }
 38  
 39  ControlFlowProfiler::~ControlFlowProfiler()
 40  {
 41      for (const BlockLocationCache& cache : m_sourceIDBuckets.values()) {
 42          for (BasicBlockLocation* block : cache.values())
 43              delete block;
 44      }
 45  }
 46  
 47  BasicBlockLocation* ControlFlowProfiler::getBasicBlockLocation(intptr_t sourceID, int startOffset, int endOffset)
 48  {
 49      auto addResult = m_sourceIDBuckets.add(sourceID, BlockLocationCache());
 50      BlockLocationCache& blockLocationCache = addResult.iterator->value;
 51      BasicBlockKey key(startOffset, endOffset);
 52      auto addResultForBasicBlock = blockLocationCache.add(key, nullptr);
 53      if (addResultForBasicBlock.isNewEntry)
 54          addResultForBasicBlock.iterator->value = new BasicBlockLocation(startOffset, endOffset);
 55      return addResultForBasicBlock.iterator->value;
 56  }
 57  
 58  void ControlFlowProfiler::dumpData() const
 59  {
 60      auto iter = m_sourceIDBuckets.begin();
 61      auto end = m_sourceIDBuckets.end();
 62      for (; iter != end; ++iter) {
 63          dataLog("SourceID: ", iter->key, "\n");
 64          for (const BasicBlockLocation* block : iter->value.values())
 65              block->dumpData();
 66      }
 67  }
 68  
 69  Vector<BasicBlockRange> ControlFlowProfiler::getBasicBlocksForSourceID(intptr_t sourceID, VM& vm) const 
 70  {
 71      Vector<BasicBlockRange> result(0);
 72      auto bucketFindResult = m_sourceIDBuckets.find(sourceID);
 73      if (bucketFindResult == m_sourceIDBuckets.end())
 74          return result;
 75  
 76      const BlockLocationCache& cache = bucketFindResult->value;
 77      for (const BasicBlockLocation* block : cache.values()) {
 78          bool hasExecuted = block->hasExecuted();
 79          size_t executionCount = block->executionCount();
 80          const Vector<BasicBlockLocation::Gap>& blockRanges = block->getExecutedRanges();
 81          for (BasicBlockLocation::Gap gap : blockRanges) {
 82              BasicBlockRange range;
 83              range.m_hasExecuted = hasExecuted;
 84              range.m_executionCount = executionCount;
 85              range.m_startOffset = gap.first;
 86              range.m_endOffset = gap.second;
 87              result.append(range);
 88          }
 89      }
 90  
 91      const Vector<std::tuple<bool, unsigned, unsigned>>& functionRanges = vm.functionHasExecutedCache()->getFunctionRanges(sourceID);
 92      for (const auto& functionRange : functionRanges) {
 93          BasicBlockRange range;
 94          range.m_hasExecuted = std::get<0>(functionRange);
 95          range.m_startOffset = static_cast<int>(std::get<1>(functionRange));
 96          range.m_endOffset = static_cast<int>(std::get<2>(functionRange));
 97          range.m_executionCount = range.m_hasExecuted ? 1 : 0; // This is a hack. We don't actually count this.
 98          result.append(range);
 99      }
100  
101      return result;
102  }
103  
104  static BasicBlockRange findBasicBlockAtTextOffset(int offset, const Vector<BasicBlockRange>& blocks)
105  {
106      int bestDistance = INT_MAX;
107      BasicBlockRange bestRange;
108      bestRange.m_startOffset = bestRange.m_endOffset = -1;
109      bestRange.m_hasExecuted = false; // Suppress MSVC warning.
110      // Because some ranges may overlap because of function boundaries, make sure to find the smallest range enclosing the offset.
111      for (BasicBlockRange range : blocks) {
112          if (range.m_startOffset <= offset && offset <= range.m_endOffset && (range.m_endOffset - range.m_startOffset) < bestDistance) {
113              RELEASE_ASSERT(range.m_endOffset - range.m_startOffset >= 0);
114              bestDistance = range.m_endOffset - range.m_startOffset;
115              bestRange = range;
116          }
117      }
118  
119      RELEASE_ASSERT(bestRange.m_startOffset != -1 && bestRange.m_endOffset != -1);
120      return bestRange;
121  }
122  
123  bool ControlFlowProfiler::hasBasicBlockAtTextOffsetBeenExecuted(int offset, intptr_t sourceID, VM& vm)
124  {
125      const Vector<BasicBlockRange>& blocks = getBasicBlocksForSourceID(sourceID, vm);
126      BasicBlockRange range = findBasicBlockAtTextOffset(offset, blocks);
127      return range.m_hasExecuted;
128  }
129  
130  size_t ControlFlowProfiler::basicBlockExecutionCountAtTextOffset(int offset, intptr_t sourceID, VM& vm)
131  {
132      const Vector<BasicBlockRange>& blocks = getBasicBlocksForSourceID(sourceID, vm);
133      BasicBlockRange range = findBasicBlockAtTextOffset(offset, blocks);
134      return range.m_executionCount;
135  }
136  
137  } // namespace JSC