Skip to content

Commit e0e21fd

Browse files
chrisethchriseth
committed
Merge pull request ethereum#1813 from chriseth/sol_knowledgeEngine
Static Analysis Engine.
2 parents 420ac9c + 3653727 commit e0e21fd

12 files changed

Lines changed: 796 additions & 354 deletions

‎libevmasm/Assembly.cpp‎

Lines changed: 11 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -304,20 +304,24 @@ Assembly& Assembly::optimise(bool _enable)
304304
{
305305
if (!_enable)
306306
return *this;
307-
std::vector<pair<AssemblyItems, function<AssemblyItems(AssemblyItemsConstRef)>>> rules;
308-
// jump to next instruction
309-
rules.push_back({ { PushTag, Instruction::JUMP, Tag }, [](AssemblyItemsConstRef m) -> AssemblyItems { if (m[0].data() == m[2].data()) return {m[2]}; else return m.toVector(); }});
310307

311308
unsigned total = 0;
312309
for (unsigned count = 1; count > 0; total += count)
313310
{
314311
copt << toString(*this);
315312
count = 0;
316313

314+
//@todo CFG interface should be a generator, that returns an item and a pointer to a
315+
// knownstate, which has to replace the current state if it is not null.
316+
// Feed these items to the CSE, but also store them and replace the stored version
317+
// if the items generated by the CSE are shorter. (or even use less gas?)
317318
copt << "Performing control flow analysis...";
318319
{
319320
ControlFlowGraph cfg(m_items);
320-
AssemblyItems optItems = cfg.optimisedItems();
321+
AssemblyItems optItems;
322+
for (BasicBlock const& block: cfg.optimisedBlocks())
323+
copy(m_items.begin() + block.begin, m_items.begin() + block.end,
324+
back_inserter(optItems));
321325
if (optItems.size() < m_items.size())
322326
{
323327
copt << "Old size: " << m_items.size() << ", new size: " << optItems.size();
@@ -329,7 +333,9 @@ Assembly& Assembly::optimise(bool _enable)
329333
copt << "Performing common subexpression elimination...";
330334
for (auto iter = m_items.begin(); iter != m_items.end();)
331335
{
332-
CommonSubexpressionEliminator eliminator;
336+
//@todo use only a single state / expression classes instance.
337+
KnownState state(make_shared<ExpressionClasses>());
338+
CommonSubexpressionEliminator eliminator(state);
333339
auto orig = iter;
334340
iter = eliminator.feedItems(iter, m_items.end());
335341
AssemblyItems optItems;

‎libevmasm/CommonSubexpressionEliminator.cpp‎

Lines changed: 20 additions & 251 deletions
Original file line numberDiff line numberDiff line change
@@ -37,18 +37,19 @@ vector<AssemblyItem> CommonSubexpressionEliminator::getOptimizedItems()
3737

3838
map<int, Id> initialStackContents;
3939
map<int, Id> targetStackContents;
40-
int minHeight = m_stackHeight + 1;
41-
if (!m_stackElements.empty())
42-
minHeight = min(minHeight, m_stackElements.begin()->first);
43-
for (int height = minHeight; height <= 0; ++height)
44-
initialStackContents[height] = initialStackElement(height, SourceLocation());
45-
for (int height = minHeight; height <= m_stackHeight; ++height)
46-
targetStackContents[height] = stackElement(height, SourceLocation());
40+
int minHeight = m_state.stackHeight() + 1;
41+
if (!m_state.stackElements().empty())
42+
minHeight = min(minHeight, m_state.stackElements().begin()->first);
43+
for (int height = minHeight; height <= m_initialState.stackHeight(); ++height)
44+
initialStackContents[height] = m_initialState.stackElement(height, SourceLocation());
45+
for (int height = minHeight; height <= m_state.stackHeight(); ++height)
46+
targetStackContents[height] = m_state.stackElement(height, SourceLocation());
4747

4848
// Debug info:
4949
//stream(cout, initialStackContents, targetStackContents);
5050

51-
AssemblyItems items = CSECodeGenerator(m_expressionClasses, m_storeOperations).generateCode(
51+
AssemblyItems items = CSECodeGenerator(m_state.expressionClasses(), m_storeOperations).generateCode(
52+
m_initialState.stackHeight(),
5253
initialStackContents,
5354
targetStackContents
5455
);
@@ -57,103 +58,11 @@ vector<AssemblyItem> CommonSubexpressionEliminator::getOptimizedItems()
5758
return items;
5859
}
5960

60-
ostream& CommonSubexpressionEliminator::stream(
61-
ostream& _out,
62-
map<int, Id> _initialStack,
63-
map<int, Id> _targetStack
64-
) const
65-
{
66-
auto streamExpressionClass = [this](ostream& _out, Id _id)
67-
{
68-
auto const& expr = m_expressionClasses.representative(_id);
69-
_out << " " << dec << _id << ": " << *expr.item;
70-
if (expr.sequenceNumber)
71-
_out << "@" << dec << expr.sequenceNumber;
72-
_out << "(";
73-
for (Id arg: expr.arguments)
74-
_out << dec << arg << ",";
75-
_out << ")" << endl;
76-
};
77-
78-
_out << "Optimizer analysis:" << endl;
79-
_out << "Final stack height: " << dec << m_stackHeight << endl;
80-
_out << "Equivalence classes: " << endl;
81-
for (Id eqClass = 0; eqClass < m_expressionClasses.size(); ++eqClass)
82-
streamExpressionClass(_out, eqClass);
83-
84-
_out << "Initial stack: " << endl;
85-
for (auto const& it: _initialStack)
86-
{
87-
_out << " " << dec << it.first << ": ";
88-
streamExpressionClass(_out, it.second);
89-
}
90-
_out << "Target stack: " << endl;
91-
for (auto const& it: _targetStack)
92-
{
93-
_out << " " << dec << it.first << ": ";
94-
streamExpressionClass(_out, it.second);
95-
}
96-
97-
return _out;
98-
}
99-
10061
void CommonSubexpressionEliminator::feedItem(AssemblyItem const& _item, bool _copyItem)
10162
{
102-
if (_item.type() != Operation)
103-
{
104-
assertThrow(_item.deposit() == 1, InvalidDeposit, "");
105-
setStackElement(++m_stackHeight, m_expressionClasses.find(_item, {}, _copyItem));
106-
}
107-
else
108-
{
109-
Instruction instruction = _item.instruction();
110-
InstructionInfo info = instructionInfo(instruction);
111-
if (SemanticInformation::isDupInstruction(_item))
112-
setStackElement(
113-
m_stackHeight + 1,
114-
stackElement(
115-
m_stackHeight - int(instruction) + int(Instruction::DUP1),
116-
_item.getLocation()
117-
)
118-
);
119-
else if (SemanticInformation::isSwapInstruction(_item))
120-
swapStackElements(
121-
m_stackHeight,
122-
m_stackHeight - 1 - int(instruction) + int(Instruction::SWAP1),
123-
_item.getLocation()
124-
);
125-
else if (instruction != Instruction::POP)
126-
{
127-
vector<Id> arguments(info.args);
128-
for (int i = 0; i < info.args; ++i)
129-
arguments[i] = stackElement(m_stackHeight - i, _item.getLocation());
130-
if (_item.instruction() == Instruction::SSTORE)
131-
storeInStorage(arguments[0], arguments[1], _item.getLocation());
132-
else if (_item.instruction() == Instruction::SLOAD)
133-
setStackElement(
134-
m_stackHeight + _item.deposit(),
135-
loadFromStorage(arguments[0], _item.getLocation())
136-
);
137-
else if (_item.instruction() == Instruction::MSTORE)
138-
storeInMemory(arguments[0], arguments[1], _item.getLocation());
139-
else if (_item.instruction() == Instruction::MLOAD)
140-
setStackElement(
141-
m_stackHeight + _item.deposit(),
142-
loadFromMemory(arguments[0], _item.getLocation())
143-
);
144-
else if (_item.instruction() == Instruction::SHA3)
145-
setStackElement(
146-
m_stackHeight + _item.deposit(),
147-
applySha3(arguments.at(0), arguments.at(1), _item.getLocation())
148-
);
149-
else
150-
setStackElement(
151-
m_stackHeight + _item.deposit(),
152-
m_expressionClasses.find(_item, arguments, _copyItem)
153-
);
154-
}
155-
m_stackHeight += _item.deposit();
156-
}
63+
StoreOperation op = m_state.feedItem(_item, _copyItem);
64+
if (op.isValid())
65+
m_storeOperations.push_back(op);
15766
}
15867

15968
void CommonSubexpressionEliminator::optimizeBreakingItem()
@@ -164,20 +73,20 @@ void CommonSubexpressionEliminator::optimizeBreakingItem()
16473
SourceLocation const& location = m_breakingItem->getLocation();
16574
AssemblyItem::JumpType jumpType = m_breakingItem->getJumpType();
16675

167-
Id condition = stackElement(m_stackHeight - 1, location);
168-
Id zero = m_expressionClasses.find(u256(0));
169-
if (m_expressionClasses.knownToBeDifferent(condition, zero))
76+
Id condition = m_state.stackElement(m_state.stackHeight() - 1, location);
77+
Id zero = m_state.expressionClasses().find(u256(0));
78+
if (m_state.expressionClasses().knownToBeDifferent(condition, zero))
17079
{
17180
feedItem(AssemblyItem(Instruction::SWAP1, location), true);
17281
feedItem(AssemblyItem(Instruction::POP, location), true);
17382

17483
AssemblyItem item(Instruction::JUMP, location);
17584
item.setJumpType(jumpType);
176-
m_breakingItem = m_expressionClasses.storeItem(item);
85+
m_breakingItem = m_state.expressionClasses().storeItem(item);
17786
return;
17887
}
179-
Id negatedCondition = m_expressionClasses.find(Instruction::ISZERO, {condition});
180-
if (m_expressionClasses.knownToBeDifferent(negatedCondition, zero))
88+
Id negatedCondition = m_state.expressionClasses().find(Instruction::ISZERO, {condition});
89+
if (m_state.expressionClasses().knownToBeDifferent(negatedCondition, zero))
18190
{
18291
AssemblyItem it(Instruction::POP, location);
18392
feedItem(it, true);
@@ -186,148 +95,6 @@ void CommonSubexpressionEliminator::optimizeBreakingItem()
18695
}
18796
}
18897

189-
void CommonSubexpressionEliminator::setStackElement(int _stackHeight, Id _class)
190-
{
191-
m_stackElements[_stackHeight] = _class;
192-
}
193-
194-
void CommonSubexpressionEliminator::swapStackElements(
195-
int _stackHeightA,
196-
int _stackHeightB,
197-
SourceLocation const& _location
198-
)
199-
{
200-
assertThrow(_stackHeightA != _stackHeightB, OptimizerException, "Swap on same stack elements.");
201-
// ensure they are created
202-
stackElement(_stackHeightA, _location);
203-
stackElement(_stackHeightB, _location);
204-
205-
swap(m_stackElements[_stackHeightA], m_stackElements[_stackHeightB]);
206-
}
207-
208-
ExpressionClasses::Id CommonSubexpressionEliminator::stackElement(
209-
int _stackHeight,
210-
SourceLocation const& _location
211-
)
212-
{
213-
if (m_stackElements.count(_stackHeight))
214-
return m_stackElements.at(_stackHeight);
215-
// Stack element not found (not assigned yet), create new equivalence class.
216-
return m_stackElements[_stackHeight] = initialStackElement(_stackHeight, _location);
217-
}
218-
219-
ExpressionClasses::Id CommonSubexpressionEliminator::initialStackElement(
220-
int _stackHeight,
221-
SourceLocation const& _location
222-
)
223-
{
224-
assertThrow(_stackHeight <= 0, OptimizerException, "Initial stack element of positive height requested.");
225-
assertThrow(_stackHeight > -16, StackTooDeepException, "");
226-
// This is a special assembly item that refers to elements pre-existing on the initial stack.
227-
return m_expressionClasses.find(AssemblyItem(dupInstruction(1 - _stackHeight), _location));
228-
}
229-
230-
void CommonSubexpressionEliminator::storeInStorage(Id _slot, Id _value, SourceLocation const& _location)
231-
{
232-
if (m_storageContent.count(_slot) && m_storageContent[_slot] == _value)
233-
// do not execute the storage if we know that the value is already there
234-
return;
235-
m_sequenceNumber++;
236-
decltype(m_storageContent) storageContents;
237-
// Copy over all values (i.e. retain knowledge about them) where we know that this store
238-
// operation will not destroy the knowledge. Specifically, we copy storage locations we know
239-
// are different from _slot or locations where we know that the stored value is equal to _value.
240-
for (auto const& storageItem: m_storageContent)
241-
if (m_expressionClasses.knownToBeDifferent(storageItem.first, _slot) || storageItem.second == _value)
242-
storageContents.insert(storageItem);
243-
m_storageContent = move(storageContents);
244-
245-
AssemblyItem item(Instruction::SSTORE, _location);
246-
Id id = m_expressionClasses.find(item, {_slot, _value}, true, m_sequenceNumber);
247-
m_storeOperations.push_back(StoreOperation(StoreOperation::Storage, _slot, m_sequenceNumber, id));
248-
m_storageContent[_slot] = _value;
249-
// increment a second time so that we get unique sequence numbers for writes
250-
m_sequenceNumber++;
251-
}
252-
253-
ExpressionClasses::Id CommonSubexpressionEliminator::loadFromStorage(Id _slot, SourceLocation const& _location)
254-
{
255-
if (m_storageContent.count(_slot))
256-
return m_storageContent.at(_slot);
257-
258-
AssemblyItem item(Instruction::SLOAD, _location);
259-
return m_storageContent[_slot] = m_expressionClasses.find(item, {_slot}, true, m_sequenceNumber);
260-
}
261-
262-
void CommonSubexpressionEliminator::storeInMemory(Id _slot, Id _value, SourceLocation const& _location)
263-
{
264-
if (m_memoryContent.count(_slot) && m_memoryContent[_slot] == _value)
265-
// do not execute the store if we know that the value is already there
266-
return;
267-
m_sequenceNumber++;
268-
decltype(m_memoryContent) memoryContents;
269-
// copy over values at points where we know that they are different from _slot by at least 32
270-
for (auto const& memoryItem: m_memoryContent)
271-
if (m_expressionClasses.knownToBeDifferentBy32(memoryItem.first, _slot))
272-
memoryContents.insert(memoryItem);
273-
m_memoryContent = move(memoryContents);
274-
275-
AssemblyItem item(Instruction::MSTORE, _location);
276-
Id id = m_expressionClasses.find(item, {_slot, _value}, true, m_sequenceNumber);
277-
m_storeOperations.push_back(StoreOperation(StoreOperation::Memory, _slot, m_sequenceNumber, id));
278-
m_memoryContent[_slot] = _value;
279-
// increment a second time so that we get unique sequence numbers for writes
280-
m_sequenceNumber++;
281-
}
282-
283-
ExpressionClasses::Id CommonSubexpressionEliminator::loadFromMemory(Id _slot, SourceLocation const& _location)
284-
{
285-
if (m_memoryContent.count(_slot))
286-
return m_memoryContent.at(_slot);
287-
288-
AssemblyItem item(Instruction::MLOAD, _location);
289-
return m_memoryContent[_slot] = m_expressionClasses.find(item, {_slot}, true, m_sequenceNumber);
290-
}
291-
292-
CommonSubexpressionEliminator::Id CommonSubexpressionEliminator::applySha3(
293-
Id _start,
294-
Id _length,
295-
SourceLocation const& _location
296-
)
297-
{
298-
AssemblyItem sha3Item(Instruction::SHA3, _location);
299-
// Special logic if length is a short constant, otherwise we cannot tell.
300-
u256 const* l = m_expressionClasses.knownConstant(_length);
301-
// unknown or too large length
302-
if (!l || *l > 128)
303-
return m_expressionClasses.find(sha3Item, {_start, _length}, true, m_sequenceNumber);
304-
305-
vector<Id> arguments;
306-
for (u256 i = 0; i < *l; i += 32)
307-
{
308-
Id slot = m_expressionClasses.find(
309-
AssemblyItem(Instruction::ADD, _location),
310-
{_start, m_expressionClasses.find(i)}
311-
);
312-
arguments.push_back(loadFromMemory(slot, _location));
313-
}
314-
if (m_knownSha3Hashes.count(arguments))
315-
return m_knownSha3Hashes.at(arguments);
316-
Id v;
317-
// If all arguments are known constants, compute the sha3 here
318-
if (all_of(arguments.begin(), arguments.end(), [this](Id _a) { return !!m_expressionClasses.knownConstant(_a); }))
319-
{
320-
bytes data;
321-
for (Id a: arguments)
322-
data += toBigEndian(*m_expressionClasses.knownConstant(a));
323-
data.resize(size_t(*l));
324-
v = m_expressionClasses.find(AssemblyItem(u256(sha3(data)), _location));
325-
}
326-
else
327-
v = m_expressionClasses.find(sha3Item, {_start, _length}, true, m_sequenceNumber);
328-
return m_knownSha3Hashes[arguments] = v;
329-
}
330-
33198
CSECodeGenerator::CSECodeGenerator(
33299
ExpressionClasses& _expressionClasses,
333100
vector<CSECodeGenerator::StoreOperation> const& _storeOperations
@@ -339,10 +106,12 @@ CSECodeGenerator::CSECodeGenerator(
339106
}
340107

341108
AssemblyItems CSECodeGenerator::generateCode(
109+
int _initialStackHeight,
342110
map<int, Id> const& _initialStack,
343111
map<int, Id> const& _targetStackContents
344112
)
345113
{
114+
m_stackHeight = _initialStackHeight;
346115
m_stack = _initialStack;
347116
for (auto const& item: m_stack)
348117
if (!m_classPositions.count(item.second))

0 commit comments

Comments
 (0)