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
32namespace JSC {
33
34ControlFlowProfiler::ControlFlowProfiler()
35 : m_dummyBasicBlock(BasicBlockLocation(-1, -1))
36{
37}
38
39ControlFlowProfiler::~ControlFlowProfiler()
40{
41 for (const BlockLocationCache& cache : m_sourceIDBuckets.values()) {
42 for (BasicBlockLocation* block : cache.values())
43 delete block;
44 }
45}
46
47BasicBlockLocation* 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
58void 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
69Vector<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
104static 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
123bool 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
130size_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
138