1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
|
/*
This file is part of cpp-ethereum.
cpp-ethereum is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
cpp-ethereum is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with cpp-ethereum. If not, see <http://www.gnu.org/licenses/>.
*/
/**
* @file BlockDeduplicator.cpp
* @author Christian <c@ethdev.com>
* @date 2015
* Unifies basic blocks that share content.
*/
#include <libevmasm/BlockDeduplicator.h>
#include <functional>
#include <libevmasm/AssemblyItem.h>
#include <libevmasm/SemanticInformation.h>
using namespace std;
using namespace dev;
using namespace dev::eth;
bool BlockDeduplicator::deduplicate()
{
// Compares indices based on the suffix that starts there, ignoring tags and stopping at
// opcodes that stop the control flow.
// Virtual tag that signifies "the current block" and which is used to optimise loops.
// We abort if this virtual tag actually exists.
AssemblyItem pushSelf(PushTag, u256(-4));
if (
std::count(m_items.cbegin(), m_items.cend(), pushSelf.tag()) ||
std::count(m_items.cbegin(), m_items.cend(), pushSelf.pushTag())
)
return false;
function<bool(size_t, size_t)> comparator = [&](size_t _i, size_t _j)
{
if (_i == _j)
return false;
// To compare recursive loops, we have to already unify PushTag opcodes of the
// block's own tag.
AssemblyItem pushFirstTag(pushSelf);
AssemblyItem pushSecondTag(pushSelf);
if (_i < m_items.size() && m_items.at(_i).type() == Tag)
pushFirstTag = m_items.at(_i).pushTag();
if (_j < m_items.size() && m_items.at(_j).type() == Tag)
pushSecondTag = m_items.at(_j).pushTag();
BlockIterator first(m_items.begin() + _i, m_items.end(), &pushFirstTag, &pushSelf);
BlockIterator second(m_items.begin() + _j, m_items.end(), &pushSecondTag, &pushSelf);
BlockIterator end(m_items.end(), m_items.end());
if (first != end && (*first).type() == Tag)
++first;
if (second != end && (*second).type() == Tag)
++second;
return std::lexicographical_compare(first, end, second, end);
};
size_t iterations = 0;
for (; ; ++iterations)
{
//@todo this should probably be optimized.
set<size_t, function<bool(size_t, size_t)>> blocksSeen(comparator);
for (size_t i = 0; i < m_items.size(); ++i)
{
if (m_items.at(i).type() != Tag)
continue;
auto it = blocksSeen.find(i);
if (it == blocksSeen.end())
blocksSeen.insert(i);
else
m_replacedTags[m_items.at(i).data()] = m_items.at(*it).data();
}
if (!applyTagReplacement(m_items, m_replacedTags))
break;
}
return iterations > 0;
}
bool BlockDeduplicator::applyTagReplacement(
AssemblyItems& _items,
map<u256, u256> const& _replacements,
size_t _subId
)
{
bool changed = false;
for (AssemblyItem& item: _items)
if (item.type() == PushTag)
{
size_t subId;
size_t tagId;
tie(subId, tagId) = item.splitForeignPushTag();
if (subId != _subId)
continue;
auto it = _replacements.find(tagId);
if (it != _replacements.end())
{
changed = true;
item.setPushTagSubIdAndTag(subId, size_t(it->second));
}
}
return changed;
}
BlockDeduplicator::BlockIterator& BlockDeduplicator::BlockIterator::operator++()
{
if (it == end)
return *this;
if (SemanticInformation::altersControlFlow(*it) && *it != AssemblyItem(Instruction::JUMPI))
it = end;
else
{
++it;
while (it != end && it->type() == Tag)
++it;
}
return *this;
}
AssemblyItem const& BlockDeduplicator::BlockIterator::operator*() const
{
if (replaceItem && replaceWith && *it == *replaceItem)
return *replaceWith;
else
return *it;
}
|
