1 /*
2 This file is part of solidity.
3
4 solidity is free software: you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation, either version 3 of the License, or
7 (at your option) any later version.
8
9 solidity is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License
15 along with solidity. If not, see <http://www.gnu.org/licenses/>.
16 */
17 // SPDX-License-Identifier: GPL-3.0
18 /**
19 * @author Christian <c@ethdev.com>
20 * @date 2014
21 * Tests for the Solidity optimizer.
22 */
23
24 #include <test/Common.h>
25
26 #include <libevmasm/CommonSubexpressionEliminator.h>
27 #include <libevmasm/PeepholeOptimiser.h>
28 #include <libevmasm/Inliner.h>
29 #include <libevmasm/JumpdestRemover.h>
30 #include <libevmasm/ControlFlowGraph.h>
31 #include <libevmasm/BlockDeduplicator.h>
32 #include <libevmasm/Assembly.h>
33
34 #include <boost/test/unit_test.hpp>
35
36 #include <range/v3/algorithm/any_of.hpp>
37
38 #include <string>
39 #include <tuple>
40 #include <memory>
41
42 using namespace std;
43 using namespace solidity::langutil;
44 using namespace solidity::evmasm;
45
46 namespace solidity::frontend::test
47 {
48
49 namespace
50 {
addDummyLocations(AssemblyItems const & _input)51 AssemblyItems addDummyLocations(AssemblyItems const& _input)
52 {
53 // add dummy locations to each item so that we can check that they are not deleted
54 AssemblyItems input = _input;
55 for (AssemblyItem& item: input)
56 item.setLocation({1, 3, nullptr});
57 return input;
58 }
59
createInitialState(AssemblyItems const & _input)60 evmasm::KnownState createInitialState(AssemblyItems const& _input)
61 {
62 evmasm::KnownState state;
63 for (auto const& item: addDummyLocations(_input))
64 state.feedItem(item, true);
65 return state;
66 }
67
CSE(AssemblyItems const & _input,evmasm::KnownState const & _state=evmasm::KnownState ())68 AssemblyItems CSE(AssemblyItems const& _input, evmasm::KnownState const& _state = evmasm::KnownState())
69 {
70 AssemblyItems input = addDummyLocations(_input);
71
72 bool usesMsize = ranges::any_of(_input, [](AssemblyItem const& _i) {
73 return _i == AssemblyItem{Instruction::MSIZE} || _i.type() == VerbatimBytecode;
74 });
75 evmasm::CommonSubexpressionEliminator cse(_state);
76 BOOST_REQUIRE(cse.feedItems(input.begin(), input.end(), usesMsize) == input.end());
77 AssemblyItems output = cse.getOptimizedItems();
78
79 for (AssemblyItem const& item: output)
80 {
81 BOOST_CHECK(item == Instruction::POP || item.location().isValid());
82 }
83 return output;
84 }
85
checkCSE(AssemblyItems const & _input,AssemblyItems const & _expectation,KnownState const & _state=evmasm::KnownState ())86 void checkCSE(
87 AssemblyItems const& _input,
88 AssemblyItems const& _expectation,
89 KnownState const& _state = evmasm::KnownState()
90 )
91 {
92 AssemblyItems output = CSE(_input, _state);
93 BOOST_CHECK_EQUAL_COLLECTIONS(_expectation.begin(), _expectation.end(), output.begin(), output.end());
94 }
95
96 /// In contrast to the function `CSE`, this function doesn't finish the CSE optimization on an
97 /// instruction that breaks CSE Analysis block. Copied from Assembly.cpp
fullCSE(AssemblyItems const & _input)98 AssemblyItems fullCSE(AssemblyItems const& _input)
99 {
100 AssemblyItems optimisedItems;
101
102 bool usesMSize = ranges::any_of(_input, [](AssemblyItem const& _i) {
103 return _i == AssemblyItem{Instruction::MSIZE} || _i.type() == VerbatimBytecode;
104 });
105
106 auto iter = _input.begin();
107 while (iter != _input.end())
108 {
109 KnownState emptyState;
110 CommonSubexpressionEliminator eliminator{emptyState};
111 auto orig = iter;
112 iter = eliminator.feedItems(iter, _input.end(), usesMSize);
113 bool shouldReplace = false;
114 AssemblyItems optimisedChunk;
115 optimisedChunk = eliminator.getOptimizedItems();
116 shouldReplace = (optimisedChunk.size() < static_cast<size_t>(iter - orig));
117 if (shouldReplace)
118 optimisedItems += optimisedChunk;
119 else
120 copy(orig, iter, back_inserter(optimisedItems));
121 }
122
123 return optimisedItems;
124 }
125
checkFullCSE(AssemblyItems const & _input,AssemblyItems const & _expectation)126 void checkFullCSE(
127 AssemblyItems const& _input,
128 AssemblyItems const& _expectation
129 )
130 {
131 AssemblyItems output = fullCSE(_input);
132 BOOST_CHECK_EQUAL_COLLECTIONS(_expectation.begin(), _expectation.end(), output.begin(), output.end());
133 }
134
CFG(AssemblyItems const & _input)135 AssemblyItems CFG(AssemblyItems const& _input)
136 {
137 AssemblyItems output = _input;
138 // Running it four times should be enough for these tests.
139 for (unsigned i = 0; i < 4; ++i)
140 {
141 ControlFlowGraph cfg(output);
142 AssemblyItems optItems;
143 for (BasicBlock const& block: cfg.optimisedBlocks())
144 copy(output.begin() + block.begin, output.begin() + block.end,
145 back_inserter(optItems));
146 output = move(optItems);
147 }
148 return output;
149 }
150
checkCFG(AssemblyItems const & _input,AssemblyItems const & _expectation)151 void checkCFG(AssemblyItems const& _input, AssemblyItems const& _expectation)
152 {
153 AssemblyItems output = CFG(_input);
154 BOOST_CHECK_EQUAL_COLLECTIONS(_expectation.begin(), _expectation.end(), output.begin(), output.end());
155 }
156 }
157
158 BOOST_AUTO_TEST_SUITE(Optimiser)
159
BOOST_AUTO_TEST_CASE(cse_push_immutable_same)160 BOOST_AUTO_TEST_CASE(cse_push_immutable_same)
161 {
162 AssemblyItem pushImmutable{PushImmutable, 0x1234};
163 checkCSE({pushImmutable, pushImmutable}, {pushImmutable, Instruction::DUP1});
164 }
165
BOOST_AUTO_TEST_CASE(cse_push_immutable_different)166 BOOST_AUTO_TEST_CASE(cse_push_immutable_different)
167 {
168 AssemblyItems input{{PushImmutable, 0x1234},{PushImmutable, 0xABCD}};
169 checkCSE(input, input);
170 }
171
BOOST_AUTO_TEST_CASE(cse_assign_immutable)172 BOOST_AUTO_TEST_CASE(cse_assign_immutable)
173 {
174 {
175 AssemblyItems input{u256(0x42), {AssignImmutable, 0x1234}};
176 checkCSE(input, input);
177 }
178 {
179 AssemblyItems input{{AssignImmutable, 0x1234}};
180 checkCSE(input, input);
181 }
182 }
183
184
BOOST_AUTO_TEST_CASE(cse_assign_immutable_breaks)185 BOOST_AUTO_TEST_CASE(cse_assign_immutable_breaks)
186 {
187 AssemblyItems input = addDummyLocations(AssemblyItems{
188 u256(0x42),
189 {AssignImmutable, 0x1234},
190 Instruction::ORIGIN
191 });
192
193 evmasm::CommonSubexpressionEliminator cse{evmasm::KnownState()};
194 // Make sure CSE breaks after AssignImmutable.
195 BOOST_REQUIRE(cse.feedItems(input.begin(), input.end(), false) == input.begin() + 2);
196 }
197
BOOST_AUTO_TEST_CASE(cse_intermediate_swap)198 BOOST_AUTO_TEST_CASE(cse_intermediate_swap)
199 {
200 evmasm::KnownState state;
201 evmasm::CommonSubexpressionEliminator cse(state);
202 AssemblyItems input{
203 Instruction::SWAP1, Instruction::POP, Instruction::ADD, u256(0), Instruction::SWAP1,
204 Instruction::SLOAD, Instruction::SWAP1, u256(100), Instruction::EXP, Instruction::SWAP1,
205 Instruction::DIV, u256(0xff), Instruction::AND
206 };
207 BOOST_REQUIRE(cse.feedItems(input.begin(), input.end(), false) == input.end());
208 AssemblyItems output = cse.getOptimizedItems();
209 BOOST_CHECK(!output.empty());
210 }
211
BOOST_AUTO_TEST_CASE(cse_negative_stack_access)212 BOOST_AUTO_TEST_CASE(cse_negative_stack_access)
213 {
214 AssemblyItems input{Instruction::DUP2, u256(0)};
215 checkCSE(input, input);
216 }
217
BOOST_AUTO_TEST_CASE(cse_negative_stack_end)218 BOOST_AUTO_TEST_CASE(cse_negative_stack_end)
219 {
220 AssemblyItems input{Instruction::ADD};
221 checkCSE(input, input);
222 }
223
BOOST_AUTO_TEST_CASE(cse_intermediate_negative_stack)224 BOOST_AUTO_TEST_CASE(cse_intermediate_negative_stack)
225 {
226 AssemblyItems input{Instruction::ADD, u256(1), Instruction::DUP1};
227 checkCSE(input, input);
228 }
229
BOOST_AUTO_TEST_CASE(cse_pop)230 BOOST_AUTO_TEST_CASE(cse_pop)
231 {
232 checkCSE({Instruction::POP}, {Instruction::POP});
233 }
234
BOOST_AUTO_TEST_CASE(cse_unneeded_items)235 BOOST_AUTO_TEST_CASE(cse_unneeded_items)
236 {
237 AssemblyItems input{
238 Instruction::ADD,
239 Instruction::SWAP1,
240 Instruction::POP,
241 u256(7),
242 u256(8),
243 };
244 checkCSE(input, input);
245 }
246
BOOST_AUTO_TEST_CASE(cse_constant_addition)247 BOOST_AUTO_TEST_CASE(cse_constant_addition)
248 {
249 AssemblyItems input{u256(7), u256(8), Instruction::ADD};
250 checkCSE(input, {u256(7 + 8)});
251 }
252
BOOST_AUTO_TEST_CASE(cse_invariants)253 BOOST_AUTO_TEST_CASE(cse_invariants)
254 {
255 AssemblyItems input{
256 Instruction::DUP1,
257 Instruction::DUP1,
258 u256(0),
259 Instruction::OR,
260 Instruction::OR
261 };
262 checkCSE(input, {Instruction::DUP1});
263 }
264
BOOST_AUTO_TEST_CASE(cse_subself)265 BOOST_AUTO_TEST_CASE(cse_subself)
266 {
267 checkCSE({Instruction::DUP1, Instruction::SUB}, {Instruction::POP, u256(0)});
268 }
269
BOOST_AUTO_TEST_CASE(cse_subother)270 BOOST_AUTO_TEST_CASE(cse_subother)
271 {
272 checkCSE({Instruction::SUB}, {Instruction::SUB});
273 }
274
BOOST_AUTO_TEST_CASE(cse_double_negation)275 BOOST_AUTO_TEST_CASE(cse_double_negation)
276 {
277 checkCSE({Instruction::DUP5, Instruction::NOT, Instruction::NOT}, {Instruction::DUP5});
278 }
279
BOOST_AUTO_TEST_CASE(cse_double_iszero)280 BOOST_AUTO_TEST_CASE(cse_double_iszero)
281 {
282 checkCSE({Instruction::GT, Instruction::ISZERO, Instruction::ISZERO}, {Instruction::GT});
283 checkCSE({Instruction::GT, Instruction::ISZERO}, {Instruction::GT, Instruction::ISZERO});
284 checkCSE(
285 {Instruction::ISZERO, Instruction::ISZERO, Instruction::ISZERO},
286 {Instruction::ISZERO}
287 );
288 }
289
BOOST_AUTO_TEST_CASE(cse_associativity)290 BOOST_AUTO_TEST_CASE(cse_associativity)
291 {
292 AssemblyItems input{
293 Instruction::DUP1,
294 Instruction::DUP1,
295 u256(0),
296 Instruction::OR,
297 Instruction::OR
298 };
299 checkCSE(input, {Instruction::DUP1});
300 }
301
BOOST_AUTO_TEST_CASE(cse_associativity2)302 BOOST_AUTO_TEST_CASE(cse_associativity2)
303 {
304 AssemblyItems input{
305 u256(0),
306 Instruction::DUP2,
307 u256(2),
308 u256(1),
309 Instruction::DUP6,
310 Instruction::ADD,
311 u256(2),
312 Instruction::ADD,
313 Instruction::ADD,
314 Instruction::ADD,
315 Instruction::ADD
316 };
317 checkCSE(input, {Instruction::DUP2, Instruction::DUP2, Instruction::ADD, u256(5), Instruction::ADD});
318 }
319
BOOST_AUTO_TEST_CASE(cse_double_shift_right_overflow)320 BOOST_AUTO_TEST_CASE(cse_double_shift_right_overflow)
321 {
322 if (solidity::test::CommonOptions::get().evmVersion().hasBitwiseShifting())
323 {
324 AssemblyItems input{
325 Instruction::CALLVALUE,
326 u256(2),
327 Instruction::SHR,
328 u256(-1),
329 Instruction::SHR
330 };
331 checkCSE(input, {u256(0)});
332 }
333 }
334
BOOST_AUTO_TEST_CASE(cse_double_shift_left_overflow)335 BOOST_AUTO_TEST_CASE(cse_double_shift_left_overflow)
336 {
337 if (solidity::test::CommonOptions::get().evmVersion().hasBitwiseShifting())
338 {
339 AssemblyItems input{
340 Instruction::DUP1,
341 u256(2),
342 Instruction::SHL,
343 u256(-1),
344 Instruction::SHL
345 };
346 checkCSE(input, {u256(0)});
347 }
348 }
349
BOOST_AUTO_TEST_CASE(cse_byte_ordering_bug)350 BOOST_AUTO_TEST_CASE(cse_byte_ordering_bug)
351 {
352 AssemblyItems input{
353 u256(31),
354 Instruction::CALLVALUE,
355 Instruction::BYTE
356 };
357 checkCSE(input, {u256(31), Instruction::CALLVALUE, Instruction::BYTE});
358 }
359
BOOST_AUTO_TEST_CASE(cse_byte_ordering_fix)360 BOOST_AUTO_TEST_CASE(cse_byte_ordering_fix)
361 {
362 AssemblyItems input{
363 Instruction::CALLVALUE,
364 u256(31),
365 Instruction::BYTE
366 };
367 checkCSE(input, {u256(0xff), Instruction::CALLVALUE, Instruction::AND});
368 }
369
BOOST_AUTO_TEST_CASE(cse_storage)370 BOOST_AUTO_TEST_CASE(cse_storage)
371 {
372 AssemblyItems input{
373 u256(0),
374 Instruction::SLOAD,
375 u256(0),
376 Instruction::SLOAD,
377 Instruction::ADD,
378 u256(0),
379 Instruction::SSTORE
380 };
381 checkCSE(input, {
382 u256(0),
383 Instruction::DUP1,
384 Instruction::SLOAD,
385 Instruction::DUP1,
386 Instruction::ADD,
387 Instruction::SWAP1,
388 Instruction::SSTORE
389 });
390 }
391
BOOST_AUTO_TEST_CASE(cse_noninterleaved_storage)392 BOOST_AUTO_TEST_CASE(cse_noninterleaved_storage)
393 {
394 // two stores to the same location should be replaced by only one store, even if we
395 // read in the meantime
396 AssemblyItems input{
397 u256(7),
398 Instruction::DUP2,
399 Instruction::SSTORE,
400 Instruction::DUP1,
401 Instruction::SLOAD,
402 u256(8),
403 Instruction::DUP3,
404 Instruction::SSTORE
405 };
406 checkCSE(input, {
407 u256(8),
408 Instruction::DUP2,
409 Instruction::SSTORE,
410 u256(7)
411 });
412 }
413
BOOST_AUTO_TEST_CASE(cse_interleaved_storage)414 BOOST_AUTO_TEST_CASE(cse_interleaved_storage)
415 {
416 // stores and reads to/from two unknown locations, should not optimize away the first store
417 AssemblyItems input{
418 u256(7),
419 Instruction::DUP2,
420 Instruction::SSTORE, // store to "DUP1"
421 Instruction::DUP2,
422 Instruction::SLOAD, // read from "DUP2", might be equal to "DUP1"
423 u256(0),
424 Instruction::DUP3,
425 Instruction::SSTORE // store different value to "DUP1"
426 };
427 checkCSE(input, input);
428 }
429
BOOST_AUTO_TEST_CASE(cse_interleaved_storage_same_value)430 BOOST_AUTO_TEST_CASE(cse_interleaved_storage_same_value)
431 {
432 // stores and reads to/from two unknown locations, should not optimize away the first store
433 // but it should optimize away the second, since we already know the value will be the same
434 AssemblyItems input{
435 u256(7),
436 Instruction::DUP2,
437 Instruction::SSTORE, // store to "DUP1"
438 Instruction::DUP2,
439 Instruction::SLOAD, // read from "DUP2", might be equal to "DUP1"
440 u256(6),
441 u256(1),
442 Instruction::ADD,
443 Instruction::DUP3,
444 Instruction::SSTORE // store same value to "DUP1"
445 };
446 checkCSE(input, {
447 u256(7),
448 Instruction::DUP2,
449 Instruction::SSTORE,
450 Instruction::DUP2,
451 Instruction::SLOAD
452 });
453 }
454
BOOST_AUTO_TEST_CASE(cse_interleaved_storage_at_known_location)455 BOOST_AUTO_TEST_CASE(cse_interleaved_storage_at_known_location)
456 {
457 // stores and reads to/from two known locations, should optimize away the first store,
458 // because we know that the location is different
459 AssemblyItems input{
460 u256(0x70),
461 u256(1),
462 Instruction::SSTORE, // store to 1
463 u256(2),
464 Instruction::SLOAD, // read from 2, is different from 1
465 u256(0x90),
466 u256(1),
467 Instruction::SSTORE // store different value at 1
468 };
469 checkCSE(input, {
470 u256(2),
471 Instruction::SLOAD,
472 u256(0x90),
473 u256(1),
474 Instruction::SSTORE
475 });
476 }
477
BOOST_AUTO_TEST_CASE(cse_interleaved_storage_at_known_location_offset)478 BOOST_AUTO_TEST_CASE(cse_interleaved_storage_at_known_location_offset)
479 {
480 // stores and reads to/from two locations which are known to be different,
481 // should optimize away the first store, because we know that the location is different
482 AssemblyItems input{
483 u256(0x70),
484 Instruction::DUP2,
485 u256(1),
486 Instruction::ADD,
487 Instruction::SSTORE, // store to "DUP1"+1
488 Instruction::DUP1,
489 u256(2),
490 Instruction::ADD,
491 Instruction::SLOAD, // read from "DUP1"+2, is different from "DUP1"+1
492 u256(0x90),
493 Instruction::DUP3,
494 u256(1),
495 Instruction::ADD,
496 Instruction::SSTORE // store different value at "DUP1"+1
497 };
498 checkCSE(input, {
499 u256(2),
500 Instruction::DUP2,
501 Instruction::ADD,
502 Instruction::SLOAD,
503 u256(0x90),
504 u256(1),
505 Instruction::DUP4,
506 Instruction::ADD,
507 Instruction::SSTORE
508 });
509 }
510
BOOST_AUTO_TEST_CASE(cse_deep_stack)511 BOOST_AUTO_TEST_CASE(cse_deep_stack)
512 {
513 AssemblyItems input{
514 Instruction::ADD,
515 Instruction::SWAP1,
516 Instruction::POP,
517 Instruction::SWAP8,
518 Instruction::POP,
519 Instruction::SWAP8,
520 Instruction::POP,
521 Instruction::SWAP8,
522 Instruction::SWAP5,
523 Instruction::POP,
524 Instruction::POP,
525 Instruction::POP,
526 Instruction::POP,
527 Instruction::POP,
528 };
529 checkCSE(input, {
530 Instruction::SWAP4,
531 Instruction::SWAP12,
532 Instruction::SWAP3,
533 Instruction::SWAP11,
534 Instruction::POP,
535 Instruction::SWAP1,
536 Instruction::SWAP3,
537 Instruction::ADD,
538 Instruction::SWAP8,
539 Instruction::POP,
540 Instruction::SWAP6,
541 Instruction::POP,
542 Instruction::POP,
543 Instruction::POP,
544 Instruction::POP,
545 Instruction::POP,
546 Instruction::POP,
547 });
548 }
549
BOOST_AUTO_TEST_CASE(cse_jumpi_no_jump)550 BOOST_AUTO_TEST_CASE(cse_jumpi_no_jump)
551 {
552 AssemblyItems input{
553 u256(0),
554 u256(1),
555 Instruction::DUP2,
556 AssemblyItem(PushTag, 1),
557 Instruction::JUMPI
558 };
559 checkCSE(input, {
560 u256(0),
561 u256(1)
562 });
563 }
564
BOOST_AUTO_TEST_CASE(cse_jumpi_jump)565 BOOST_AUTO_TEST_CASE(cse_jumpi_jump)
566 {
567 AssemblyItems input{
568 u256(1),
569 u256(1),
570 Instruction::DUP2,
571 AssemblyItem(PushTag, 1),
572 Instruction::JUMPI
573 };
574 checkCSE(input, {
575 u256(1),
576 Instruction::DUP1,
577 AssemblyItem(PushTag, 1),
578 Instruction::JUMP
579 });
580 }
581
BOOST_AUTO_TEST_CASE(cse_empty_keccak256)582 BOOST_AUTO_TEST_CASE(cse_empty_keccak256)
583 {
584 AssemblyItems input{
585 u256(0),
586 Instruction::DUP2,
587 Instruction::KECCAK256
588 };
589 checkCSE(input, {
590 u256(util::keccak256(bytesConstRef()))
591 });
592 }
593
BOOST_AUTO_TEST_CASE(cse_partial_keccak256)594 BOOST_AUTO_TEST_CASE(cse_partial_keccak256)
595 {
596 AssemblyItems input{
597 u256(0xabcd) << (256 - 16),
598 u256(0),
599 Instruction::MSTORE,
600 u256(2),
601 u256(0),
602 Instruction::KECCAK256
603 };
604 checkCSE(input, {
605 u256(0xabcd) << (256 - 16),
606 u256(0),
607 Instruction::MSTORE,
608 u256(util::keccak256(bytes{0xab, 0xcd}))
609 });
610 }
611
BOOST_AUTO_TEST_CASE(cse_keccak256_twice_same_location)612 BOOST_AUTO_TEST_CASE(cse_keccak256_twice_same_location)
613 {
614 // Keccak-256 twice from same dynamic location
615 AssemblyItems input{
616 Instruction::DUP2,
617 Instruction::DUP1,
618 Instruction::MSTORE,
619 u256(64),
620 Instruction::DUP2,
621 Instruction::KECCAK256,
622 u256(64),
623 Instruction::DUP3,
624 Instruction::KECCAK256
625 };
626 checkCSE(input, {
627 Instruction::DUP2,
628 Instruction::DUP1,
629 Instruction::MSTORE,
630 u256(64),
631 Instruction::DUP2,
632 Instruction::KECCAK256,
633 Instruction::DUP1
634 });
635 }
636
BOOST_AUTO_TEST_CASE(cse_keccak256_twice_same_content)637 BOOST_AUTO_TEST_CASE(cse_keccak256_twice_same_content)
638 {
639 // Keccak-256 twice from different dynamic location but with same content
640 AssemblyItems input{
641 Instruction::DUP1,
642 u256(0x80),
643 Instruction::MSTORE, // m[128] = DUP1
644 u256(0x20),
645 u256(0x80),
646 Instruction::KECCAK256, // keccak256(m[128..(128+32)])
647 Instruction::DUP2,
648 u256(12),
649 Instruction::MSTORE, // m[12] = DUP1
650 u256(0x20),
651 u256(12),
652 Instruction::KECCAK256 // keccak256(m[12..(12+32)])
653 };
654 checkCSE(input, {
655 u256(0x80),
656 Instruction::DUP2,
657 Instruction::DUP2,
658 Instruction::MSTORE,
659 u256(0x20),
660 Instruction::SWAP1,
661 Instruction::KECCAK256,
662 u256(12),
663 Instruction::DUP3,
664 Instruction::SWAP1,
665 Instruction::MSTORE,
666 Instruction::DUP1
667 });
668 }
669
BOOST_AUTO_TEST_CASE(cse_keccak256_twice_same_content_dynamic_store_in_between)670 BOOST_AUTO_TEST_CASE(cse_keccak256_twice_same_content_dynamic_store_in_between)
671 {
672 // Keccak-256 twice from different dynamic location but with same content,
673 // dynamic mstore in between, which forces us to re-calculate the hash
674 AssemblyItems input{
675 u256(0x80),
676 Instruction::DUP2,
677 Instruction::DUP2,
678 Instruction::MSTORE, // m[128] = DUP1
679 u256(0x20),
680 Instruction::DUP1,
681 Instruction::DUP3,
682 Instruction::KECCAK256, // keccak256(m[128..(128+32)])
683 u256(12),
684 Instruction::DUP5,
685 Instruction::DUP2,
686 Instruction::MSTORE, // m[12] = DUP1
687 Instruction::DUP12,
688 Instruction::DUP14,
689 Instruction::MSTORE, // destroys memory knowledge
690 Instruction::SWAP2,
691 Instruction::SWAP1,
692 Instruction::SWAP2,
693 Instruction::KECCAK256 // keccak256(m[12..(12+32)])
694 };
695 checkCSE(input, input);
696 }
697
BOOST_AUTO_TEST_CASE(cse_keccak256_twice_same_content_noninterfering_store_in_between)698 BOOST_AUTO_TEST_CASE(cse_keccak256_twice_same_content_noninterfering_store_in_between)
699 {
700 // Keccak-256 twice from different dynamic location but with same content,
701 // dynamic mstore in between, but does not force us to re-calculate the hash
702 AssemblyItems input{
703 u256(0x80),
704 Instruction::DUP2,
705 Instruction::DUP2,
706 Instruction::MSTORE, // m[128] = DUP1
707 u256(0x20),
708 Instruction::DUP1,
709 Instruction::DUP3,
710 Instruction::KECCAK256, // keccak256(m[128..(128+32)])
711 u256(12),
712 Instruction::DUP5,
713 Instruction::DUP2,
714 Instruction::MSTORE, // m[12] = DUP1
715 Instruction::DUP12,
716 u256(12 + 32),
717 Instruction::MSTORE, // does not destoy memory knowledge
718 Instruction::DUP13,
719 u256(128 - 32),
720 Instruction::MSTORE, // does not destoy memory knowledge
721 u256(0x20),
722 u256(12),
723 Instruction::KECCAK256 // keccak256(m[12..(12+32)])
724 };
725 // if this changes too often, only count the number of SHA3 and MSTORE instructions
726 AssemblyItems output = CSE(input);
727 BOOST_CHECK_EQUAL(4, count(output.begin(), output.end(), AssemblyItem(Instruction::MSTORE)));
728 BOOST_CHECK_EQUAL(1, count(output.begin(), output.end(), AssemblyItem(Instruction::KECCAK256)));
729 }
730
BOOST_AUTO_TEST_CASE(cse_with_initially_known_stack)731 BOOST_AUTO_TEST_CASE(cse_with_initially_known_stack)
732 {
733 evmasm::KnownState state = createInitialState(AssemblyItems{
734 u256(0x12),
735 u256(0x20),
736 Instruction::ADD
737 });
738 AssemblyItems input{
739 u256(0x12 + 0x20)
740 };
741 checkCSE(input, AssemblyItems{Instruction::DUP1}, state);
742 }
743
BOOST_AUTO_TEST_CASE(cse_equality_on_initially_known_stack)744 BOOST_AUTO_TEST_CASE(cse_equality_on_initially_known_stack)
745 {
746 evmasm::KnownState state = createInitialState(AssemblyItems{Instruction::DUP1});
747 AssemblyItems input{
748 Instruction::EQ
749 };
750 AssemblyItems output = CSE(input, state);
751 // check that it directly pushes 1 (true)
752 BOOST_CHECK(find(output.begin(), output.end(), AssemblyItem(u256(1))) != output.end());
753 }
754
BOOST_AUTO_TEST_CASE(cse_access_previous_sequence)755 BOOST_AUTO_TEST_CASE(cse_access_previous_sequence)
756 {
757 // Tests that the code generator detects whether it tries to access SLOAD instructions
758 // from a sequenced expression which is not in its scope.
759 evmasm::KnownState state = createInitialState(AssemblyItems{
760 u256(0),
761 Instruction::SLOAD,
762 u256(1),
763 Instruction::ADD,
764 u256(0),
765 Instruction::SSTORE
766 });
767 // now stored: val_1 + 1 (value at sequence 1)
768 // if in the following instructions, the SLOAD cresolves to "val_1 + 1",
769 // this cannot be generated because we cannot load from sequence 1 anymore.
770 AssemblyItems input{
771 u256(0),
772 Instruction::SLOAD,
773 };
774 BOOST_CHECK_THROW(CSE(input, state), StackTooDeepException);
775 // @todo for now, this throws an exception, but it should recover to the following
776 // (or an even better version) at some point:
777 // 0, SLOAD, 1, ADD, SSTORE, 0 SLOAD
778 }
779
BOOST_AUTO_TEST_CASE(cse_optimise_return)780 BOOST_AUTO_TEST_CASE(cse_optimise_return)
781 {
782 checkCSE(
783 AssemblyItems{u256(0), u256(7), Instruction::RETURN},
784 AssemblyItems{Instruction::STOP}
785 );
786 }
787
BOOST_AUTO_TEST_CASE(control_flow_graph_remove_unused)788 BOOST_AUTO_TEST_CASE(control_flow_graph_remove_unused)
789 {
790 // remove parts of the code that are unused
791 AssemblyItems input{
792 AssemblyItem(PushTag, 1),
793 Instruction::JUMP,
794 u256(7),
795 AssemblyItem(Tag, 1),
796 };
797 checkCFG(input, {});
798 }
799
BOOST_AUTO_TEST_CASE(control_flow_graph_remove_unused_loop)800 BOOST_AUTO_TEST_CASE(control_flow_graph_remove_unused_loop)
801 {
802 AssemblyItems input{
803 AssemblyItem(PushTag, 3),
804 Instruction::JUMP,
805 AssemblyItem(Tag, 1),
806 u256(7),
807 AssemblyItem(PushTag, 2),
808 Instruction::JUMP,
809 AssemblyItem(Tag, 2),
810 u256(8),
811 AssemblyItem(PushTag, 1),
812 Instruction::JUMP,
813 AssemblyItem(Tag, 3),
814 u256(11)
815 };
816 checkCFG(input, {u256(11)});
817 }
818
BOOST_AUTO_TEST_CASE(control_flow_graph_reconnect_single_jump_source)819 BOOST_AUTO_TEST_CASE(control_flow_graph_reconnect_single_jump_source)
820 {
821 // move code that has only one unconditional jump source
822 AssemblyItems input{
823 u256(1),
824 AssemblyItem(PushTag, 1),
825 Instruction::JUMP,
826 AssemblyItem(Tag, 2),
827 u256(2),
828 AssemblyItem(PushTag, 3),
829 Instruction::JUMP,
830 AssemblyItem(Tag, 1),
831 u256(3),
832 AssemblyItem(PushTag, 2),
833 Instruction::JUMP,
834 AssemblyItem(Tag, 3),
835 u256(4),
836 };
837 checkCFG(input, {u256(1), u256(3), u256(2), u256(4)});
838 }
839
BOOST_AUTO_TEST_CASE(control_flow_graph_do_not_remove_returned_to)840 BOOST_AUTO_TEST_CASE(control_flow_graph_do_not_remove_returned_to)
841 {
842 // do not remove parts that are "returned to"
843 AssemblyItems input{
844 AssemblyItem(PushTag, 1),
845 AssemblyItem(PushTag, 2),
846 Instruction::JUMP,
847 AssemblyItem(Tag, 2),
848 Instruction::JUMP,
849 AssemblyItem(Tag, 1),
850 u256(2)
851 };
852 checkCFG(input, {u256(2)});
853 }
854
BOOST_AUTO_TEST_CASE(block_deduplicator)855 BOOST_AUTO_TEST_CASE(block_deduplicator)
856 {
857 AssemblyItems input{
858 AssemblyItem(PushTag, 2),
859 AssemblyItem(PushTag, 1),
860 AssemblyItem(PushTag, 3),
861 u256(6),
862 Instruction::SWAP3,
863 Instruction::JUMP,
864 AssemblyItem(Tag, 1),
865 u256(6),
866 Instruction::SWAP3,
867 Instruction::JUMP,
868 AssemblyItem(Tag, 2),
869 u256(6),
870 Instruction::SWAP3,
871 Instruction::JUMP,
872 AssemblyItem(Tag, 3)
873 };
874 BlockDeduplicator deduplicator(input);
875 deduplicator.deduplicate();
876
877 set<u256> pushTags;
878 for (AssemblyItem const& item: input)
879 if (item.type() == PushTag)
880 pushTags.insert(item.data());
881 BOOST_CHECK_EQUAL(pushTags.size(), 2);
882 }
883
BOOST_AUTO_TEST_CASE(block_deduplicator_assign_immutable_same)884 BOOST_AUTO_TEST_CASE(block_deduplicator_assign_immutable_same)
885 {
886 AssemblyItems blocks{
887 AssemblyItem(Tag, 1),
888 u256(42),
889 AssemblyItem{AssignImmutable, 0x1234},
890 Instruction::JUMP,
891 AssemblyItem(Tag, 2),
892 u256(42),
893 AssemblyItem{AssignImmutable, 0x1234},
894 Instruction::JUMP
895 };
896
897 AssemblyItems input = AssemblyItems{
898 AssemblyItem(PushTag, 2),
899 AssemblyItem(PushTag, 1),
900 } + blocks;
901 AssemblyItems output = AssemblyItems{
902 AssemblyItem(PushTag, 1),
903 AssemblyItem(PushTag, 1),
904 } + blocks;
905 BlockDeduplicator deduplicator(input);
906 deduplicator.deduplicate();
907 BOOST_CHECK_EQUAL_COLLECTIONS(input.begin(), input.end(), output.begin(), output.end());
908 }
909
BOOST_AUTO_TEST_CASE(block_deduplicator_assign_immutable_different_value)910 BOOST_AUTO_TEST_CASE(block_deduplicator_assign_immutable_different_value)
911 {
912 AssemblyItems input{
913 AssemblyItem(PushTag, 2),
914 AssemblyItem(PushTag, 1),
915 AssemblyItem(Tag, 1),
916 u256(42),
917 AssemblyItem{AssignImmutable, 0x1234},
918 Instruction::JUMP,
919 AssemblyItem(Tag, 2),
920 u256(23),
921 AssemblyItem{AssignImmutable, 0x1234},
922 Instruction::JUMP
923 };
924 BlockDeduplicator deduplicator(input);
925 BOOST_CHECK(!deduplicator.deduplicate());
926 }
927
BOOST_AUTO_TEST_CASE(block_deduplicator_assign_immutable_different_hash)928 BOOST_AUTO_TEST_CASE(block_deduplicator_assign_immutable_different_hash)
929 {
930 AssemblyItems input{
931 AssemblyItem(PushTag, 2),
932 AssemblyItem(PushTag, 1),
933 AssemblyItem(Tag, 1),
934 u256(42),
935 AssemblyItem{AssignImmutable, 0x1234},
936 Instruction::JUMP,
937 AssemblyItem(Tag, 2),
938 u256(42),
939 AssemblyItem{AssignImmutable, 0xABCD},
940 Instruction::JUMP
941 };
942 BlockDeduplicator deduplicator(input);
943 BOOST_CHECK(!deduplicator.deduplicate());
944 }
945
BOOST_AUTO_TEST_CASE(block_deduplicator_loops)946 BOOST_AUTO_TEST_CASE(block_deduplicator_loops)
947 {
948 AssemblyItems input{
949 u256(0),
950 Instruction::SLOAD,
951 AssemblyItem(PushTag, 1),
952 AssemblyItem(PushTag, 2),
953 Instruction::JUMPI,
954 Instruction::JUMP,
955 AssemblyItem(Tag, 1),
956 u256(5),
957 u256(6),
958 Instruction::SSTORE,
959 AssemblyItem(PushTag, 1),
960 Instruction::JUMP,
961 AssemblyItem(Tag, 2),
962 u256(5),
963 u256(6),
964 Instruction::SSTORE,
965 AssemblyItem(PushTag, 2),
966 Instruction::JUMP,
967 };
968 BlockDeduplicator deduplicator(input);
969 deduplicator.deduplicate();
970
971 set<u256> pushTags;
972 for (AssemblyItem const& item: input)
973 if (item.type() == PushTag)
974 pushTags.insert(item.data());
975 BOOST_CHECK_EQUAL(pushTags.size(), 1);
976 }
977
BOOST_AUTO_TEST_CASE(clear_unreachable_code)978 BOOST_AUTO_TEST_CASE(clear_unreachable_code)
979 {
980 AssemblyItems items{
981 AssemblyItem(PushTag, 1),
982 Instruction::JUMP,
983 u256(0),
984 Instruction::SLOAD,
985 AssemblyItem(Tag, 2),
986 u256(5),
987 u256(6),
988 Instruction::SSTORE,
989 AssemblyItem(PushTag, 1),
990 Instruction::JUMP,
991 u256(5),
992 u256(6)
993 };
994 AssemblyItems expectation{
995 AssemblyItem(PushTag, 1),
996 Instruction::JUMP,
997 AssemblyItem(Tag, 2),
998 u256(5),
999 u256(6),
1000 Instruction::SSTORE,
1001 AssemblyItem(PushTag, 1),
1002 Instruction::JUMP
1003 };
1004 PeepholeOptimiser peepOpt(items);
1005 BOOST_REQUIRE(peepOpt.optimise());
1006 BOOST_CHECK_EQUAL_COLLECTIONS(
1007 items.begin(), items.end(),
1008 expectation.begin(), expectation.end()
1009 );
1010 }
1011
BOOST_AUTO_TEST_CASE(peephole_double_push)1012 BOOST_AUTO_TEST_CASE(peephole_double_push)
1013 {
1014 AssemblyItems items{
1015 u256(0),
1016 u256(0),
1017 u256(5),
1018 u256(5),
1019 u256(4),
1020 u256(5)
1021 };
1022 AssemblyItems expectation{
1023 u256(0),
1024 Instruction::DUP1,
1025 u256(5),
1026 Instruction::DUP1,
1027 u256(4),
1028 u256(5)
1029 };
1030 PeepholeOptimiser peepOpt(items);
1031 BOOST_REQUIRE(peepOpt.optimise());
1032 BOOST_CHECK_EQUAL_COLLECTIONS(
1033 items.begin(), items.end(),
1034 expectation.begin(), expectation.end()
1035 );
1036 }
1037
BOOST_AUTO_TEST_CASE(peephole_pop_calldatasize)1038 BOOST_AUTO_TEST_CASE(peephole_pop_calldatasize)
1039 {
1040 AssemblyItems items{
1041 u256(4),
1042 Instruction::CALLDATASIZE,
1043 Instruction::LT,
1044 Instruction::POP
1045 };
1046 PeepholeOptimiser peepOpt(items);
1047 for (size_t i = 0; i < 3; i++)
1048 BOOST_CHECK(peepOpt.optimise());
1049 BOOST_CHECK(items.empty());
1050 }
1051
BOOST_AUTO_TEST_CASE(peephole_commutative_swap1)1052 BOOST_AUTO_TEST_CASE(peephole_commutative_swap1)
1053 {
1054 vector<Instruction> ops{
1055 Instruction::ADD,
1056 Instruction::MUL,
1057 Instruction::EQ,
1058 Instruction::AND,
1059 Instruction::OR,
1060 Instruction::XOR
1061 };
1062 for (Instruction const op: ops)
1063 {
1064 AssemblyItems items{
1065 u256(1),
1066 u256(2),
1067 Instruction::SWAP1,
1068 op,
1069 u256(4),
1070 u256(5)
1071 };
1072 AssemblyItems expectation{
1073 u256(1),
1074 u256(2),
1075 op,
1076 u256(4),
1077 u256(5)
1078 };
1079 PeepholeOptimiser peepOpt(items);
1080 BOOST_REQUIRE(peepOpt.optimise());
1081 BOOST_CHECK_EQUAL_COLLECTIONS(
1082 items.begin(), items.end(),
1083 expectation.begin(), expectation.end()
1084 );
1085 }
1086 }
1087
BOOST_AUTO_TEST_CASE(peephole_noncommutative_swap1)1088 BOOST_AUTO_TEST_CASE(peephole_noncommutative_swap1)
1089 {
1090 // NOTE: not comprehensive
1091 vector<Instruction> ops{
1092 Instruction::SUB,
1093 Instruction::DIV,
1094 Instruction::SDIV,
1095 Instruction::MOD,
1096 Instruction::SMOD,
1097 Instruction::EXP
1098 };
1099 for (Instruction const op: ops)
1100 {
1101 AssemblyItems items{
1102 u256(1),
1103 u256(2),
1104 Instruction::SWAP1,
1105 op,
1106 u256(4),
1107 u256(5)
1108 };
1109 AssemblyItems expectation{
1110 u256(1),
1111 u256(2),
1112 Instruction::SWAP1,
1113 op,
1114 u256(4),
1115 u256(5)
1116 };
1117 PeepholeOptimiser peepOpt(items);
1118 BOOST_REQUIRE(!peepOpt.optimise());
1119 BOOST_CHECK_EQUAL_COLLECTIONS(
1120 items.begin(), items.end(),
1121 expectation.begin(), expectation.end()
1122 );
1123 }
1124 }
1125
BOOST_AUTO_TEST_CASE(peephole_swap_comparison)1126 BOOST_AUTO_TEST_CASE(peephole_swap_comparison)
1127 {
1128 map<Instruction, Instruction> swappableOps{
1129 { Instruction::LT, Instruction::GT },
1130 { Instruction::GT, Instruction::LT },
1131 { Instruction::SLT, Instruction::SGT },
1132 { Instruction::SGT, Instruction::SLT }
1133 };
1134
1135 for (auto const& op: swappableOps)
1136 {
1137 AssemblyItems items{
1138 u256(1),
1139 u256(2),
1140 Instruction::SWAP1,
1141 op.first,
1142 u256(4),
1143 u256(5)
1144 };
1145 AssemblyItems expectation{
1146 u256(1),
1147 u256(2),
1148 op.second,
1149 u256(4),
1150 u256(5)
1151 };
1152 PeepholeOptimiser peepOpt(items);
1153 BOOST_REQUIRE(peepOpt.optimise());
1154 BOOST_CHECK_EQUAL_COLLECTIONS(
1155 items.begin(), items.end(),
1156 expectation.begin(), expectation.end()
1157 );
1158 }
1159 }
1160
BOOST_AUTO_TEST_CASE(peephole_truthy_and)1161 BOOST_AUTO_TEST_CASE(peephole_truthy_and)
1162 {
1163 AssemblyItems items{
1164 AssemblyItem(Tag, 1),
1165 Instruction::BALANCE,
1166 u256(0),
1167 Instruction::NOT,
1168 Instruction::AND,
1169 AssemblyItem(PushTag, 1),
1170 Instruction::JUMPI
1171 };
1172 AssemblyItems expectation{
1173 AssemblyItem(Tag, 1),
1174 Instruction::BALANCE,
1175 AssemblyItem(PushTag, 1),
1176 Instruction::JUMPI
1177 };
1178 PeepholeOptimiser peepOpt(items);
1179 BOOST_REQUIRE(peepOpt.optimise());
1180 BOOST_CHECK_EQUAL_COLLECTIONS(
1181 items.begin(), items.end(),
1182 expectation.begin(), expectation.end()
1183 );
1184 }
1185
1186
BOOST_AUTO_TEST_CASE(peephole_iszero_iszero_jumpi)1187 BOOST_AUTO_TEST_CASE(peephole_iszero_iszero_jumpi)
1188 {
1189 AssemblyItems items{
1190 AssemblyItem(Tag, 1),
1191 u256(0),
1192 Instruction::CALLDATALOAD,
1193 Instruction::ISZERO,
1194 Instruction::ISZERO,
1195 AssemblyItem(PushTag, 1),
1196 Instruction::JUMPI,
1197 u256(0),
1198 u256(0x20),
1199 Instruction::RETURN
1200 };
1201 AssemblyItems expectation{
1202 AssemblyItem(Tag, 1),
1203 u256(0),
1204 Instruction::CALLDATALOAD,
1205 AssemblyItem(PushTag, 1),
1206 Instruction::JUMPI,
1207 u256(0),
1208 u256(0x20),
1209 Instruction::RETURN
1210 };
1211 PeepholeOptimiser peepOpt(items);
1212 BOOST_REQUIRE(peepOpt.optimise());
1213 BOOST_CHECK_EQUAL_COLLECTIONS(
1214 items.begin(), items.end(),
1215 expectation.begin(), expectation.end()
1216 );
1217 }
1218
BOOST_AUTO_TEST_CASE(jumpdest_removal)1219 BOOST_AUTO_TEST_CASE(jumpdest_removal)
1220 {
1221 AssemblyItems items{
1222 AssemblyItem(Tag, 2),
1223 AssemblyItem(PushTag, 1),
1224 u256(5),
1225 AssemblyItem(Tag, 10),
1226 AssemblyItem(Tag, 3),
1227 u256(6),
1228 AssemblyItem(Tag, 1),
1229 Instruction::JUMP,
1230 };
1231 AssemblyItems expectation{
1232 AssemblyItem(PushTag, 1),
1233 u256(5),
1234 u256(6),
1235 AssemblyItem(Tag, 1),
1236 Instruction::JUMP
1237 };
1238 JumpdestRemover jdr(items);
1239 BOOST_REQUIRE(jdr.optimise({}));
1240 BOOST_CHECK_EQUAL_COLLECTIONS(
1241 items.begin(), items.end(),
1242 expectation.begin(), expectation.end()
1243 );
1244 }
1245
BOOST_AUTO_TEST_CASE(jumpdest_removal_subassemblies)1246 BOOST_AUTO_TEST_CASE(jumpdest_removal_subassemblies)
1247 {
1248 // This tests that tags from subassemblies are not removed
1249 // if they are referenced by a super-assembly. Furthermore,
1250 // tag unifications (due to block deduplication) is also
1251 // visible at the super-assembly.
1252
1253 Assembly main;
1254 AssemblyPointer sub = make_shared<Assembly>();
1255
1256 sub->append(u256(1));
1257 auto t1 = sub->newTag();
1258 sub->append(t1);
1259 sub->append(u256(2));
1260 sub->append(Instruction::JUMP);
1261 auto t2 = sub->newTag();
1262 sub->append(t2); // Identical to T1, will be unified
1263 sub->append(u256(2));
1264 sub->append(Instruction::JUMP);
1265 auto t3 = sub->newTag();
1266 sub->append(t3);
1267 auto t4 = sub->newTag();
1268 sub->append(t4);
1269 auto t5 = sub->newTag();
1270 sub->append(t5); // This will be removed
1271 sub->append(u256(7));
1272 sub->append(t4.pushTag());
1273 sub->append(Instruction::JUMP);
1274
1275 size_t subId = static_cast<size_t>(main.appendSubroutine(sub).data());
1276 main.append(t1.toSubAssemblyTag(subId));
1277 main.append(t1.toSubAssemblyTag(subId));
1278 main.append(u256(8));
1279
1280 Assembly::OptimiserSettings settings;
1281 settings.isCreation = false;
1282 settings.runInliner = false;
1283 settings.runJumpdestRemover = true;
1284 settings.runPeephole = true;
1285 settings.runDeduplicate = true;
1286 settings.runCSE = true;
1287 settings.runConstantOptimiser = true;
1288 settings.evmVersion = solidity::test::CommonOptions::get().evmVersion();
1289 settings.expectedExecutionsPerDeployment = OptimiserSettings{}.expectedExecutionsPerDeployment;
1290 ;
1291 main.optimise(settings);
1292
1293 AssemblyItems expectationMain{
1294 AssemblyItem(PushSubSize, 0),
1295 t1.toSubAssemblyTag(subId).pushTag(),
1296 t1.toSubAssemblyTag(subId).pushTag(),
1297 u256(8)
1298 };
1299 BOOST_CHECK_EQUAL_COLLECTIONS(
1300 main.items().begin(), main.items().end(),
1301 expectationMain.begin(), expectationMain.end()
1302 );
1303
1304 AssemblyItems expectationSub{
1305 u256(1), t1.tag(), u256(2), Instruction::JUMP, t4.tag(), u256(7), t4.pushTag(), Instruction::JUMP
1306 };
1307 BOOST_CHECK_EQUAL_COLLECTIONS(
1308 sub->items().begin(), sub->items().end(),
1309 expectationSub.begin(), expectationSub.end()
1310 );
1311 }
1312
BOOST_AUTO_TEST_CASE(cse_sub_zero)1313 BOOST_AUTO_TEST_CASE(cse_sub_zero)
1314 {
1315 checkCSE({
1316 u256(0),
1317 Instruction::DUP2,
1318 Instruction::SUB
1319 }, {
1320 Instruction::DUP1
1321 });
1322
1323 checkCSE({
1324 Instruction::DUP1,
1325 u256(0),
1326 Instruction::SUB
1327 }, {
1328 u256(0),
1329 Instruction::DUP2,
1330 Instruction::SWAP1,
1331 Instruction::SUB
1332 });
1333 }
1334
BOOST_AUTO_TEST_CASE(cse_simple_verbatim)1335 BOOST_AUTO_TEST_CASE(cse_simple_verbatim)
1336 {
1337 auto verbatim = AssemblyItem{bytes{1, 2, 3, 4, 5}, 0, 0};
1338 AssemblyItems input{verbatim};
1339 checkCSE(input, input);
1340 checkFullCSE(input, input);
1341 }
1342
BOOST_AUTO_TEST_CASE(cse_mload_pop)1343 BOOST_AUTO_TEST_CASE(cse_mload_pop)
1344 {
1345 AssemblyItems input{
1346 u256(1000),
1347 Instruction::MLOAD,
1348 Instruction::POP,
1349 };
1350
1351 AssemblyItems output{
1352 };
1353
1354 checkCSE(input, output);
1355 checkFullCSE(input, output);
1356 }
1357
BOOST_AUTO_TEST_CASE(cse_verbatim_mload)1358 BOOST_AUTO_TEST_CASE(cse_verbatim_mload)
1359 {
1360 auto verbatim = AssemblyItem{bytes{1, 2, 3, 4, 5}, 0, 0};
1361 AssemblyItems input{
1362 u256(1000),
1363 Instruction::MLOAD, // Should not be removed
1364 Instruction::POP,
1365 verbatim,
1366 u256(1000),
1367 Instruction::MLOAD, // Should not be removed
1368 Instruction::POP,
1369 };
1370
1371 checkFullCSE(input, input);
1372 }
1373
BOOST_AUTO_TEST_CASE(cse_sload_verbatim_dup)1374 BOOST_AUTO_TEST_CASE(cse_sload_verbatim_dup)
1375 {
1376 auto verbatim = AssemblyItem{bytes{1, 2, 3, 4, 5}, 0, 0};
1377 AssemblyItems input{
1378 u256(0),
1379 Instruction::SLOAD,
1380 u256(0),
1381 Instruction::SLOAD,
1382 verbatim
1383 };
1384
1385 AssemblyItems output{
1386 u256(0),
1387 Instruction::SLOAD,
1388 Instruction::DUP1,
1389 verbatim
1390 };
1391
1392 checkCSE(input, output);
1393 checkFullCSE(input, output);
1394 }
1395
BOOST_AUTO_TEST_CASE(cse_verbatim_sload_sideeffect)1396 BOOST_AUTO_TEST_CASE(cse_verbatim_sload_sideeffect)
1397 {
1398 auto verbatim = AssemblyItem{bytes{1, 2, 3, 4, 5}, 0, 0};
1399 AssemblyItems input{
1400 u256(0),
1401 Instruction::SLOAD,
1402 verbatim,
1403 u256(0),
1404 Instruction::SLOAD,
1405 };
1406
1407 checkFullCSE(input, input);
1408 }
1409
BOOST_AUTO_TEST_CASE(cse_verbatim_eq)1410 BOOST_AUTO_TEST_CASE(cse_verbatim_eq)
1411 {
1412 auto verbatim = AssemblyItem{bytes{1, 2, 3, 4, 5}, 0, 0};
1413 AssemblyItems input{
1414 u256(0),
1415 Instruction::SLOAD,
1416 verbatim,
1417 Instruction::DUP1,
1418 Instruction::EQ
1419 };
1420
1421 checkFullCSE(input, input);
1422 }
1423
BOOST_AUTO_TEST_CASE(verbatim_knownstate)1424 BOOST_AUTO_TEST_CASE(verbatim_knownstate)
1425 {
1426 KnownState state = createInitialState(AssemblyItems{
1427 Instruction::DUP1,
1428 Instruction::DUP2,
1429 Instruction::DUP3,
1430 Instruction::DUP4
1431 });
1432 map<int, unsigned> const& stackElements = state.stackElements();
1433
1434 BOOST_CHECK(state.stackHeight() == 4);
1435 // One more than stack height because of the initial unknown element.
1436 BOOST_CHECK(stackElements.size() == 5);
1437 BOOST_CHECK(stackElements.count(0));
1438 unsigned initialElement = stackElements.at(0);
1439 // Check if all the DUPs were correctly matched to the same class.
1440 for (auto const& height: {1, 2, 3, 4})
1441 BOOST_CHECK(stackElements.at(height) == initialElement);
1442
1443 auto verbatim2i5o = AssemblyItem{bytes{1, 2, 3, 4, 5}, 2, 5};
1444 state.feedItem(verbatim2i5o);
1445
1446 BOOST_CHECK(state.stackHeight() == 7);
1447 // Stack elements
1448 // Before verbatim: {{0, x}, {1, x}, {2, x}, {3, x}, {4, x}}
1449 // After verbatim: {{0, x}, {1, x}, {2, x}, {3, a}, {4, b}, {5, c}, {6, d}, {7, e}}
1450 BOOST_CHECK(stackElements.size() == 8);
1451
1452 for (auto const& height: {1, 2})
1453 BOOST_CHECK(stackElements.at(height) == initialElement);
1454
1455 for (auto const& height: {3, 4, 5, 6, 7})
1456 BOOST_CHECK(stackElements.at(height) != initialElement);
1457
1458 for (auto const& height1: {3, 4, 5, 6, 7})
1459 for (auto const& height2: {3, 4, 5, 6, 7})
1460 if (height1 < height2)
1461 BOOST_CHECK(stackElements.at(height1) != stackElements.at(height2));
1462 }
1463
BOOST_AUTO_TEST_CASE(cse_remove_redundant_shift_masking)1464 BOOST_AUTO_TEST_CASE(cse_remove_redundant_shift_masking)
1465 {
1466 if (!solidity::test::CommonOptions::get().evmVersion().hasBitwiseShifting())
1467 return;
1468
1469 for (unsigned i = 1; i < 256; i++)
1470 {
1471 checkCSE({
1472 u256(boost::multiprecision::pow(u256(2), i) - 1),
1473 Instruction::CALLVALUE,
1474 u256(256-i),
1475 Instruction::SHR,
1476 Instruction::AND
1477 }, {
1478 Instruction::CALLVALUE,
1479 u256(256-i),
1480 Instruction::SHR,
1481 });
1482
1483 checkCSE({
1484 Instruction::CALLVALUE,
1485 u256(256-i),
1486 Instruction::SHR,
1487 u256(boost::multiprecision::pow(u256(2), i)-1),
1488 Instruction::AND
1489 }, {
1490 Instruction::CALLVALUE,
1491 u256(256-i),
1492 Instruction::SHR,
1493 });
1494 }
1495
1496 // Check that opt. does NOT trigger
1497 for (unsigned i = 1; i < 255; i++)
1498 {
1499 checkCSE({
1500 u256(boost::multiprecision::pow(u256(2), i) - 1),
1501 Instruction::CALLVALUE,
1502 u256(255-i),
1503 Instruction::SHR,
1504 Instruction::AND
1505 }, { // Opt. did some reordering
1506 Instruction::CALLVALUE,
1507 u256(255-i),
1508 Instruction::SHR,
1509 u256(boost::multiprecision::pow(u256(2), i)-1),
1510 Instruction::AND
1511 });
1512
1513 checkCSE({
1514 Instruction::CALLVALUE,
1515 u256(255-i),
1516 Instruction::SHR,
1517 u256(boost::multiprecision::pow(u256(2), i)-1),
1518 Instruction::AND
1519 }, { // Opt. did some reordering
1520 u256(boost::multiprecision::pow(u256(2), i)-1),
1521 Instruction::CALLVALUE,
1522 u256(255-i),
1523 Instruction::SHR,
1524 Instruction::AND
1525 });
1526 }
1527
1528 //(x >> (31*8)) & 0xffffffff
1529 checkCSE({
1530 Instruction::CALLVALUE,
1531 u256(31*8),
1532 Instruction::SHR,
1533 u256(0xffffffff),
1534 Instruction::AND
1535 }, {
1536 Instruction::CALLVALUE,
1537 u256(31*8),
1538 Instruction::SHR
1539 });
1540 }
1541
BOOST_AUTO_TEST_CASE(cse_remove_unwanted_masking_of_address)1542 BOOST_AUTO_TEST_CASE(cse_remove_unwanted_masking_of_address)
1543 {
1544 vector<Instruction> ops{
1545 Instruction::ADDRESS,
1546 Instruction::CALLER,
1547 Instruction::ORIGIN,
1548 Instruction::COINBASE
1549 };
1550 for (auto const& op: ops)
1551 {
1552 checkCSE({
1553 u256("0xffffffffffffffffffffffffffffffffffffffff"),
1554 op,
1555 Instruction::AND
1556 }, {
1557 op
1558 });
1559
1560 checkCSE({
1561 op,
1562 u256("0xffffffffffffffffffffffffffffffffffffffff"),
1563 Instruction::AND
1564 }, {
1565 op
1566 });
1567
1568 // do not remove mask for other masking
1569 checkCSE({
1570 u256(1234),
1571 op,
1572 Instruction::AND
1573 }, {
1574 op,
1575 u256(1234),
1576 Instruction::AND
1577 });
1578
1579 checkCSE({
1580 op,
1581 u256(1234),
1582 Instruction::AND
1583 }, {
1584 u256(1234),
1585 op,
1586 Instruction::AND
1587 });
1588 }
1589
1590 // leave other opcodes untouched
1591 checkCSE({
1592 u256("0xffffffffffffffffffffffffffffffffffffffff"),
1593 Instruction::CALLVALUE,
1594 Instruction::AND
1595 }, {
1596 Instruction::CALLVALUE,
1597 u256("0xffffffffffffffffffffffffffffffffffffffff"),
1598 Instruction::AND
1599 });
1600
1601 checkCSE({
1602 Instruction::CALLVALUE,
1603 u256("0xffffffffffffffffffffffffffffffffffffffff"),
1604 Instruction::AND
1605 }, {
1606 u256("0xffffffffffffffffffffffffffffffffffffffff"),
1607 Instruction::CALLVALUE,
1608 Instruction::AND
1609 });
1610 }
1611
BOOST_AUTO_TEST_CASE(cse_replace_too_large_shift)1612 BOOST_AUTO_TEST_CASE(cse_replace_too_large_shift)
1613 {
1614 if (!solidity::test::CommonOptions::get().evmVersion().hasBitwiseShifting())
1615 return;
1616
1617 checkCSE({
1618 Instruction::CALLVALUE,
1619 u256(299),
1620 Instruction::SHL
1621 }, {
1622 u256(0)
1623 });
1624
1625 checkCSE({
1626 Instruction::CALLVALUE,
1627 u256(299),
1628 Instruction::SHR
1629 }, {
1630 u256(0)
1631 });
1632
1633 checkCSE({
1634 Instruction::CALLVALUE,
1635 u256(255),
1636 Instruction::SHL
1637 }, {
1638 Instruction::CALLVALUE,
1639 u256(255),
1640 Instruction::SHL
1641 });
1642
1643 checkCSE({
1644 Instruction::CALLVALUE,
1645 u256(255),
1646 Instruction::SHR
1647 }, {
1648 Instruction::CALLVALUE,
1649 u256(255),
1650 Instruction::SHR
1651 });
1652 }
1653
BOOST_AUTO_TEST_CASE(inliner)1654 BOOST_AUTO_TEST_CASE(inliner)
1655 {
1656 AssemblyItem jumpInto{Instruction::JUMP};
1657 jumpInto.setJumpType(AssemblyItem::JumpType::IntoFunction);
1658 AssemblyItem jumpOutOf{Instruction::JUMP};
1659 jumpOutOf.setJumpType(AssemblyItem::JumpType::OutOfFunction);
1660 AssemblyItems items{
1661 AssemblyItem(PushTag, 1),
1662 AssemblyItem(PushTag, 2),
1663 jumpInto,
1664 AssemblyItem(Tag, 1),
1665 Instruction::STOP,
1666 AssemblyItem(Tag, 2),
1667 Instruction::CALLVALUE,
1668 Instruction::SWAP1,
1669 jumpOutOf,
1670 };
1671 AssemblyItems expectation{
1672 AssemblyItem(PushTag, 1),
1673 Instruction::CALLVALUE,
1674 Instruction::SWAP1,
1675 Instruction::JUMP,
1676 AssemblyItem(Tag, 1),
1677 Instruction::STOP,
1678 AssemblyItem(Tag, 2),
1679 Instruction::CALLVALUE,
1680 Instruction::SWAP1,
1681 jumpOutOf,
1682 };
1683 Inliner{items, {}, Assembly::OptimiserSettings{}.expectedExecutionsPerDeployment, false, {}}.optimise();
1684 BOOST_CHECK_EQUAL_COLLECTIONS(
1685 items.begin(), items.end(),
1686 expectation.begin(), expectation.end()
1687 );
1688 }
1689
1690
BOOST_AUTO_TEST_CASE(inliner_no_inline_type)1691 BOOST_AUTO_TEST_CASE(inliner_no_inline_type)
1692 {
1693 // Will not inline due to jump types.
1694 AssemblyItems items{
1695 AssemblyItem(PushTag, 1),
1696 AssemblyItem(PushTag, 2),
1697 Instruction::JUMP,
1698 AssemblyItem(Tag, 1),
1699 Instruction::STOP,
1700 AssemblyItem(Tag, 2),
1701 Instruction::CALLVALUE,
1702 Instruction::SWAP1,
1703 Instruction::JUMP,
1704 };
1705 Inliner{items, {}, Assembly::OptimiserSettings{}.expectedExecutionsPerDeployment, false, {}}.optimise();
1706 BOOST_CHECK_EQUAL_COLLECTIONS(
1707 items.begin(), items.end(),
1708 items.begin(), items.end()
1709 );
1710 }
1711
BOOST_AUTO_TEST_CASE(inliner_no_inline)1712 BOOST_AUTO_TEST_CASE(inliner_no_inline)
1713 {
1714 AssemblyItems items{
1715 AssemblyItem(PushTag, 1),
1716 Instruction::JUMP,
1717 AssemblyItem(Tag, 1),
1718 Instruction::CALLVALUE,
1719 Instruction::JUMPI,
1720 Instruction::JUMP,
1721 };
1722 AssemblyItems expectation{
1723 AssemblyItem(PushTag, 1),
1724 Instruction::JUMP,
1725 AssemblyItem(Tag, 1),
1726 Instruction::CALLVALUE,
1727 Instruction::JUMPI,
1728 Instruction::JUMP,
1729 };
1730 Inliner{items, {}, Assembly::OptimiserSettings{}.expectedExecutionsPerDeployment, false, {}}.optimise();
1731 BOOST_CHECK_EQUAL_COLLECTIONS(
1732 items.begin(), items.end(),
1733 expectation.begin(), expectation.end()
1734 );
1735 }
1736
1737
BOOST_AUTO_TEST_CASE(inliner_single_jump)1738 BOOST_AUTO_TEST_CASE(inliner_single_jump)
1739 {
1740 AssemblyItem jumpInto{Instruction::JUMP};
1741 jumpInto.setJumpType(AssemblyItem::JumpType::IntoFunction);
1742 AssemblyItem jumpOutOf{Instruction::JUMP};
1743 jumpOutOf.setJumpType(AssemblyItem::JumpType::OutOfFunction);
1744 AssemblyItems items{
1745 AssemblyItem(PushTag, 1),
1746 AssemblyItem(PushTag, 2),
1747 jumpInto,
1748 AssemblyItem(Tag, 1),
1749 Instruction::STOP,
1750 AssemblyItem(Tag, 2),
1751 jumpOutOf,
1752 };
1753 AssemblyItems expectation{
1754 AssemblyItem(PushTag, 1),
1755 Instruction::JUMP,
1756 AssemblyItem(Tag, 1),
1757 Instruction::STOP,
1758 AssemblyItem(Tag, 2),
1759 jumpOutOf,
1760 };
1761 Inliner{items, {}, Assembly::OptimiserSettings{}.expectedExecutionsPerDeployment, false, {}}.optimise();
1762 BOOST_CHECK_EQUAL_COLLECTIONS(
1763 items.begin(), items.end(),
1764 expectation.begin(), expectation.end()
1765 );
1766 }
1767
BOOST_AUTO_TEST_CASE(inliner_end_of_bytecode)1768 BOOST_AUTO_TEST_CASE(inliner_end_of_bytecode)
1769 {
1770 AssemblyItem jumpInto{Instruction::JUMP};
1771 jumpInto.setJumpType(AssemblyItem::JumpType::IntoFunction);
1772 // Cannot inline, since the block at Tag_2 does not end in a jump.
1773 AssemblyItems items{
1774 AssemblyItem(PushTag, 1),
1775 AssemblyItem(PushTag, 2),
1776 jumpInto,
1777 AssemblyItem(Tag, 1),
1778 Instruction::STOP,
1779 AssemblyItem(Tag, 2),
1780 };
1781 Inliner{items, {}, Assembly::OptimiserSettings{}.expectedExecutionsPerDeployment, false, {}}.optimise();
1782 BOOST_CHECK_EQUAL_COLLECTIONS(
1783 items.begin(), items.end(),
1784 items.begin(), items.end()
1785 );
1786 }
1787
1788
BOOST_AUTO_TEST_CASE(inliner_cse_break)1789 BOOST_AUTO_TEST_CASE(inliner_cse_break)
1790 {
1791 AssemblyItem jumpInto{Instruction::JUMP};
1792 jumpInto.setJumpType(AssemblyItem::JumpType::IntoFunction);
1793 AssemblyItem jumpOutOf{Instruction::JUMP};
1794 jumpOutOf.setJumpType(AssemblyItem::JumpType::OutOfFunction);
1795 // Could be inlined, but we only consider non-CSE-breaking blocks ending in JUMP so far.
1796 AssemblyItems items{
1797 AssemblyItem(PushTag, 1),
1798 AssemblyItem(PushTag, 2),
1799 jumpInto,
1800 AssemblyItem(Tag, 1),
1801 Instruction::STOP,
1802 AssemblyItem(Tag, 2),
1803 Instruction::STOP, // CSE breaking instruction
1804 jumpOutOf
1805 };
1806 Inliner{items, {}, Assembly::OptimiserSettings{}.expectedExecutionsPerDeployment, false, {}}.optimise();
1807 BOOST_CHECK_EQUAL_COLLECTIONS(
1808 items.begin(), items.end(),
1809 items.begin(), items.end()
1810 );
1811 }
1812
BOOST_AUTO_TEST_CASE(inliner_stop)1813 BOOST_AUTO_TEST_CASE(inliner_stop)
1814 {
1815 AssemblyItems items{
1816 AssemblyItem(PushTag, 1),
1817 Instruction::JUMP,
1818 AssemblyItem(Tag, 1),
1819 Instruction::STOP
1820 };
1821 AssemblyItems expectation{
1822 Instruction::STOP,
1823 AssemblyItem(Tag, 1),
1824 Instruction::STOP
1825 };
1826 Inliner{items, {}, Assembly::OptimiserSettings{}.expectedExecutionsPerDeployment, false, {}}.optimise();
1827 BOOST_CHECK_EQUAL_COLLECTIONS(
1828 items.begin(), items.end(),
1829 expectation.begin(), expectation.end()
1830 );
1831 }
1832
BOOST_AUTO_TEST_CASE(inliner_stop_jumpi)1833 BOOST_AUTO_TEST_CASE(inliner_stop_jumpi)
1834 {
1835 // Because of `jumpi`, will not be inlined.
1836 AssemblyItems items{
1837 u256(1),
1838 AssemblyItem(PushTag, 1),
1839 Instruction::JUMPI,
1840 AssemblyItem(Tag, 1),
1841 Instruction::STOP
1842 };
1843 AssemblyItems expectation = items;
1844 Inliner{items, {}, Assembly::OptimiserSettings{}.expectedExecutionsPerDeployment, false, {}}.optimise();
1845 BOOST_CHECK_EQUAL_COLLECTIONS(
1846 items.begin(), items.end(),
1847 expectation.begin(), expectation.end()
1848 );
1849 }
1850
BOOST_AUTO_TEST_CASE(inliner_revert)1851 BOOST_AUTO_TEST_CASE(inliner_revert)
1852 {
1853 AssemblyItems items{
1854 AssemblyItem(PushTag, 1),
1855 Instruction::JUMP,
1856 AssemblyItem(Tag, 1),
1857 u256(0),
1858 Instruction::DUP1,
1859 Instruction::REVERT
1860 };
1861 AssemblyItems expectation{
1862 u256(0),
1863 Instruction::DUP1,
1864 Instruction::REVERT,
1865 AssemblyItem(Tag, 1),
1866 u256(0),
1867 Instruction::DUP1,
1868 Instruction::REVERT
1869 };
1870
1871 Inliner{items, {}, Assembly::OptimiserSettings{}.expectedExecutionsPerDeployment, false, {}}.optimise();
1872 BOOST_CHECK_EQUAL_COLLECTIONS(
1873 items.begin(), items.end(),
1874 expectation.begin(), expectation.end()
1875 );
1876 }
1877
BOOST_AUTO_TEST_CASE(inliner_revert_increased_datagas)1878 BOOST_AUTO_TEST_CASE(inliner_revert_increased_datagas)
1879 {
1880 // Inlining this would increase data gas (5 bytes v/s 4 bytes), therefore, skipped.
1881 AssemblyItems items{
1882 AssemblyItem(PushTag, 1),
1883 Instruction::JUMP,
1884 AssemblyItem(Tag, 1),
1885 u256(0),
1886 u256(0),
1887 Instruction::REVERT
1888 };
1889
1890 AssemblyItems expectation = items;
1891 Inliner{items, {}, Assembly::OptimiserSettings{}.expectedExecutionsPerDeployment, false, {}}.optimise();
1892 BOOST_CHECK_EQUAL_COLLECTIONS(
1893 items.begin(), items.end(),
1894 expectation.begin(), expectation.end()
1895 );
1896 }
1897
BOOST_AUTO_TEST_CASE(inliner_invalid)1898 BOOST_AUTO_TEST_CASE(inliner_invalid)
1899 {
1900 AssemblyItems items{
1901 AssemblyItem(PushTag, 1),
1902 Instruction::JUMP,
1903 AssemblyItem(Tag, 1),
1904 Instruction::INVALID
1905 };
1906
1907 AssemblyItems expectation = {
1908 Instruction::INVALID,
1909 AssemblyItem(Tag, 1),
1910 Instruction::INVALID
1911 };
1912 Inliner{items, {}, Assembly::OptimiserSettings{}.expectedExecutionsPerDeployment, false, {}}.optimise();
1913 BOOST_CHECK_EQUAL_COLLECTIONS(
1914 items.begin(), items.end(),
1915 expectation.begin(), expectation.end()
1916 );
1917 }
1918
1919
1920 BOOST_AUTO_TEST_SUITE_END()
1921
1922 } // end namespaces
1923