1/*
2 * Copyright (C) 2016 Yusuke Suzuki <[email protected]>
3 * Copyright (C) 2016 Apple Inc. All rights reserved.
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. AND ITS CONTRIBUTORS ``AS IS''
15 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
16 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
17 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
18 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
19 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
20 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
21 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
22 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
23 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
24 * THE POSSIBILITY OF SUCH DAMAGE.
25 */
26
27#pragma once
28
29#include "BytecodeBasicBlock.h"
30#include <wtf/IndexedContainerIterator.h>
31#include <wtf/IteratorRange.h>
32#include <wtf/Vector.h>
33
34namespace JSC {
35
36class BytecodeBasicBlock;
37
38class BytecodeGraph {
39 WTF_MAKE_FAST_ALLOCATED;
40 WTF_MAKE_NONCOPYABLE(BytecodeGraph);
41public:
42 typedef Vector<std::unique_ptr<BytecodeBasicBlock>> BasicBlocksVector;
43
44 typedef WTF::IndexedContainerIterator<BytecodeGraph> iterator;
45
46 template <typename CodeBlockType>
47 inline BytecodeGraph(CodeBlockType*, const InstructionStream&);
48
49 WTF::IteratorRange<BasicBlocksVector::reverse_iterator> basicBlocksInReverseOrder()
50 {
51 return WTF::makeIteratorRange(m_basicBlocks.rbegin(), m_basicBlocks.rend());
52 }
53
54 static bool blockContainsBytecodeOffset(BytecodeBasicBlock* block, InstructionStream::Offset bytecodeOffset)
55 {
56 unsigned leaderOffset = block->leaderOffset();
57 return bytecodeOffset >= leaderOffset && bytecodeOffset < leaderOffset + block->totalLength();
58 }
59
60 BytecodeBasicBlock* findBasicBlockForBytecodeOffset(InstructionStream::Offset bytecodeOffset)
61 {
62 /*
63 for (unsigned i = 0; i < m_basicBlocks.size(); i++) {
64 if (blockContainsBytecodeOffset(m_basicBlocks[i].get(), bytecodeOffset))
65 return m_basicBlocks[i].get();
66 }
67 return 0;
68 */
69
70 std::unique_ptr<BytecodeBasicBlock>* basicBlock = approximateBinarySearch<std::unique_ptr<BytecodeBasicBlock>, unsigned>(m_basicBlocks, m_basicBlocks.size(), bytecodeOffset, [] (std::unique_ptr<BytecodeBasicBlock>* basicBlock) { return (*basicBlock)->leaderOffset(); });
71 // We found the block we were looking for.
72 if (blockContainsBytecodeOffset((*basicBlock).get(), bytecodeOffset))
73 return (*basicBlock).get();
74
75 // Basic block is to the left of the returned block.
76 if (bytecodeOffset < (*basicBlock)->leaderOffset()) {
77 ASSERT(basicBlock - 1 >= m_basicBlocks.data());
78 ASSERT(blockContainsBytecodeOffset(basicBlock[-1].get(), bytecodeOffset));
79 return basicBlock[-1].get();
80 }
81
82 // Basic block is to the right of the returned block.
83 ASSERT(&basicBlock[1] <= &m_basicBlocks.last());
84 ASSERT(blockContainsBytecodeOffset(basicBlock[1].get(), bytecodeOffset));
85 return basicBlock[1].get();
86 }
87
88 BytecodeBasicBlock* findBasicBlockWithLeaderOffset(InstructionStream::Offset leaderOffset)
89 {
90 return (*tryBinarySearch<std::unique_ptr<BytecodeBasicBlock>, unsigned>(m_basicBlocks, m_basicBlocks.size(), leaderOffset, [] (std::unique_ptr<BytecodeBasicBlock>* basicBlock) { return (*basicBlock)->leaderOffset(); })).get();
91 }
92
93 unsigned size() const { return m_basicBlocks.size(); }
94 BytecodeBasicBlock* at(unsigned index) const { return m_basicBlocks[index].get(); }
95 BytecodeBasicBlock* operator[](unsigned index) const { return at(index); }
96
97 iterator begin() const { return iterator(*this, 0); }
98 iterator end() const { return iterator(*this, size()); }
99 BytecodeBasicBlock* first() { return at(0); }
100 BytecodeBasicBlock* last() { return at(size() - 1); }
101
102private:
103 BasicBlocksVector m_basicBlocks;
104};
105
106
107template<typename CodeBlockType>
108BytecodeGraph::BytecodeGraph(CodeBlockType* codeBlock, const InstructionStream& instructions)
109{
110 BytecodeBasicBlock::compute(codeBlock, instructions, m_basicBlocks);
111 ASSERT(m_basicBlocks.size());
112}
113
114} // namespace JSC
115