Ton

1
/*
2
    This file is part of TON Blockchain Library.
3

4
    TON Blockchain Library is free software: you can redistribute it and/or modify
5
    it under the terms of the GNU Lesser General Public License as published by
6
    the Free Software Foundation, either version 2 of the License, or
7
    (at your option) any later version.
8

9
    TON Blockchain Library 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 Lesser General Public License for more details.
13

14
    You should have received a copy of the GNU Lesser General Public License
15
    along with TON Blockchain Library.  If not, see <http://www.gnu.org/licenses/>.
16

17
    Copyright 2017-2020 Telegram Systems LLP
18
*/
19
#include "func.h"
20

21
namespace funC {
22

23
/*
24
 * 
25
 *   PEEPHOLE OPTIMIZER
26
 * 
27
 */
28

29
void Optimizer::set_code(AsmOpConsList code) {
30
  code_ = std::move(code);
31
  unpack();
32
}
33

34
void Optimizer::unpack() {
35
  int i = 0, j = 0;
36
  for (AsmOpCons *p = code_.get(); p && i < n; p = p->cdr.get(), ++j) {
37
    if (p->car->is_very_custom()) {
38
      break;
39
    }
40
    if (p->car->is_comment()) {
41
      continue;
42
    }
43
    op_cons_[i] = p;
44
    op_[i] = std::move(p->car);
45
    offs_[i] = j;
46
    ++i;
47
  }
48
  l_ = i;
49
  indent_ = (i ? op_[0]->indent : 0);
50
}
51

52
void Optimizer::pack() {
53
  for (int i = 0; i < l_; i++) {
54
    op_cons_[i]->car = std::move(op_[i]);
55
    op_cons_[i] = nullptr;
56
  }
57
  l_ = 0;
58
}
59

60
void Optimizer::apply() {
61
  if (!p_ && !q_) {
62
    return;
63
  }
64
  func_assert(p_ > 0 && p_ <= l_ && q_ >= 0 && q_ <= n && l_ <= n);
65
  for (int i = p_; i < l_; i++) {
66
    func_assert(op_[i]);
67
    op_cons_[i]->car = std::move(op_[i]);
68
    op_cons_[i] = nullptr;
69
  }
70
  for (int c = offs_[p_ - 1]; c >= 0; --c) {
71
    code_ = std::move(code_->cdr);
72
  }
73
  for (int j = q_ - 1; j >= 0; j--) {
74
    func_assert(oq_[j]);
75
    oq_[j]->indent = indent_;
76
    code_ = AsmOpCons::cons(std::move(oq_[j]), std::move(code_));
77
  }
78
  l_ = 0;
79
}
80

81
AsmOpConsList Optimizer::extract_code() {
82
  pack();
83
  return std::move(code_);
84
}
85

86
void Optimizer::show_head() const {
87
  if (!debug_) {
88
    return;
89
  }
90
  std::cerr << "optimizing";
91
  for (int i = 0; i < l_; i++) {
92
    if (op_[i]) {
93
      std::cerr << ' ' << *op_[i] << ' ';
94
    } else {
95
      std::cerr << " (null) ";
96
    }
97
  }
98
  std::cerr << std::endl;
99
}
100

101
void Optimizer::show_left() const {
102
  if (!debug_) {
103
    return;
104
  }
105
  std::cerr << "// *** rewriting";
106
  for (int i = 0; i < p_; i++) {
107
    if (op_[i]) {
108
      std::cerr << ' ' << *op_[i] << ' ';
109
    } else {
110
      std::cerr << " (null) ";
111
    }
112
  }
113
}
114

115
void Optimizer::show_right() const {
116
  if (!debug_) {
117
    return;
118
  }
119
  std::cerr << "->";
120
  for (int i = 0; i < q_; i++) {
121
    if (oq_[i]) {
122
      std::cerr << ' ' << *oq_[i] << ' ';
123
    } else {
124
      std::cerr << " (null) ";
125
    }
126
  }
127
  std::cerr << std::endl;
128
}
129

130
bool Optimizer::say(std::string str) const {
131
  if (debug_) {
132
    std::cerr << str << std::endl;
133
  }
134
  return true;
135
}
136

137
bool Optimizer::find_const_op(int* op_idx, int cst) {
138
  for (int i = 0; i < l2_; i++) {
139
    if (op_[i]->is_gconst() && tr_[i].get(0) == cst) {
140
      *op_idx = i;
141
      return true;
142
    }
143
  }
144
  return false;
145
}
146

147
bool Optimizer::is_push_const(int* i, int* c) const {
148
  return pb_ >= 3 && pb_ <= l2_ && tr_[pb_ - 1].is_push_const(i, c);
149
}
150

151
// PUSHCONST c ; PUSH s(i+1) ; SWAP -> PUSH s(i) ; PUSHCONST c
152
bool Optimizer::rewrite_push_const(int i, int c) {
153
  p_ = pb_;
154
  q_ = 2;
155
  int idx = -1;
156
  if (!(p_ >= 2 && find_const_op(&idx, c) && idx < p_)) {
157
    return false;
158
  }
159
  show_left();
160
  oq_[1] = std::move(op_[idx]);
161
  oq_[0] = std::move(op_[!idx]);
162
  *oq_[0] = AsmOp::Push(i);
163
  show_right();
164
  return true;
165
}
166

167
bool Optimizer::is_const_rot(int* c) const {
168
  return pb_ >= 3 && pb_ <= l2_ && tr_[pb_ - 1].is_const_rot(c);
169
}
170

171
bool Optimizer::rewrite_const_rot(int c) {
172
  p_ = pb_;
173
  q_ = 2;
174
  int idx = -1;
175
  if (!(p_ >= 2 && find_const_op(&idx, c) && idx < p_)) {
176
    return false;
177
  }
178
  show_left();
179
  oq_[0] = std::move(op_[idx]);
180
  oq_[1] = std::move(op_[!idx]);
181
  *oq_[1] = AsmOp::Custom("ROT", 3, 3);
182
  show_right();
183
  return true;
184
}
185

186
bool Optimizer::is_const_pop(int* c, int* i) const {
187
  return pb_ >= 3 && pb_ <= l2_ && tr_[pb_ - 1].is_const_pop(c, i);
188
}
189

190
bool Optimizer::rewrite_const_pop(int c, int i) {
191
  p_ = pb_;
192
  q_ = 2;
193
  int idx = -1;
194
  if (!(p_ >= 2 && find_const_op(&idx, c) && idx < p_)) {
195
    return false;
196
  }
197
  show_left();
198
  oq_[0] = std::move(op_[idx]);
199
  oq_[1] = std::move(op_[!idx]);
200
  *oq_[1] = AsmOp::Pop(i);
201
  show_right();
202
  return true;
203
}
204

205
bool Optimizer::is_const_push_xchgs() {
206
  if (!(pb_ >= 2 && pb_ <= l2_ && op_[0]->is_gconst())) {
207
    return false;
208
  }
209
  StackTransform t;
210
  int pos = 0, i;
211
  for (i = 1; i < pb_; i++) {
212
    int a, b;
213
    if (op_[i]->is_xchg(&a, &b)) {
214
      if (pos == a) {
215
        pos = b;
216
      } else if (pos == b) {
217
        pos = a;
218
      } else {
219
        t.apply_xchg(a - (a > pos), b - (b > pos));
220
      }
221
    } else if (op_[i]->is_push(&a)) {
222
      if (pos == a) {
223
        return false;
224
      }
225
      t.apply_push(a - (a > pos));
226
      ++pos;
227
    } else {
228
      return false;
229
    }
230
  }
231
  if (pos) {
232
    return false;
233
  }
234
  t.apply_push_newconst();
235
  if (t <= tr_[i - 1]) {
236
    p_ = i;
237
    return true;
238
  } else {
239
    return false;
240
  }
241
}
242

243
bool Optimizer::rewrite_const_push_xchgs() {
244
  if (!p_) {
245
    return false;
246
  }
247
  show_left();
248
  auto c_op = std::move(op_[0]);
249
  func_assert(c_op->is_gconst());
250
  StackTransform t;
251
  q_ = 0;
252
  int pos = 0;
253
  for (int i = 1; i < p_; i++) {
254
    int a, b;
255
    if (op_[i]->is_xchg(&a, &b)) {
256
      if (a == pos) {
257
        pos = b;
258
      } else if (b == pos) {
259
        pos = a;
260
      } else {
261
        oq_[q_] = std::move(op_[i]);
262
        if (a > pos) {
263
          oq_[q_]->a = a - 1;
264
        }
265
        if (b > pos) {
266
          oq_[q_]->b = b - 1;
267
        }
268
        func_assert(apply_op(t, *oq_[q_]));
269
        ++q_;
270
      }
271
    } else {
272
      func_assert(op_[i]->is_push(&a));
273
      func_assert(a != pos);
274
      oq_[q_] = std::move(op_[i]);
275
      if (a > pos) {
276
        oq_[q_]->a = a - 1;
277
      }
278
      func_assert(apply_op(t, *oq_[q_]));
279
      ++q_;
280
      ++pos;
281
    }
282
  }
283
  func_assert(!pos);
284
  t.apply_push_newconst();
285
  func_assert(t <= tr_[p_ - 1]);
286
  oq_[q_++] = std::move(c_op);
287
  show_right();
288
  return true;
289
}
290

291
bool Optimizer::rewrite(int p, AsmOp&& new_op) {
292
  func_assert(p > 0 && p <= l_);
293
  p_ = p;
294
  q_ = 1;
295
  show_left();
296
  oq_[0] = std::move(op_[0]);
297
  *oq_[0] = new_op;
298
  show_right();
299
  return true;
300
}
301

302
bool Optimizer::rewrite(int p, AsmOp&& new_op1, AsmOp&& new_op2) {
303
  func_assert(p > 1 && p <= l_);
304
  p_ = p;
305
  q_ = 2;
306
  show_left();
307
  oq_[0] = std::move(op_[0]);
308
  *oq_[0] = new_op1;
309
  oq_[1] = std::move(op_[1]);
310
  *oq_[1] = new_op2;
311
  show_right();
312
  return true;
313
}
314

315
bool Optimizer::rewrite(int p, AsmOp&& new_op1, AsmOp&& new_op2, AsmOp&& new_op3) {
316
  func_assert(p > 2 && p <= l_);
317
  p_ = p;
318
  q_ = 3;
319
  show_left();
320
  oq_[0] = std::move(op_[0]);
321
  *oq_[0] = new_op1;
322
  oq_[1] = std::move(op_[1]);
323
  *oq_[1] = new_op2;
324
  oq_[2] = std::move(op_[2]);
325
  *oq_[2] = new_op3;
326
  show_right();
327
  return true;
328
}
329

330
bool Optimizer::rewrite_nop() {
331
  func_assert(p_ > 0 && p_ <= l_);
332
  q_ = 0;
333
  show_left();
334
  show_right();
335
  return true;
336
}
337

338
bool Optimizer::is_pred(const std::function<bool(const StackTransform&)>& pred, int min_p) {
339
  min_p = std::max(min_p, pb_);
340
  for (int p = l2_; p >= min_p; p--) {
341
    if (pred(tr_[p - 1])) {
342
      p_ = p;
343
      return true;
344
    }
345
  }
346
  return false;
347
}
348

349
bool Optimizer::is_same_as(const StackTransform& trans, int min_p) {
350
  return is_pred([&trans](const auto& t) { return t >= trans; }, min_p);
351
}
352

353
// s1 s3 XCHG ; s0 s2 XCHG -> 2SWAP
354
bool Optimizer::is_2swap() {
355
  static const StackTransform t_2swap{2, 3, 0, 1, 4};
356
  return is_same_as(t_2swap);
357
}
358

359
// s3 PUSH ; s3 PUSH -> 2OVER
360
bool Optimizer::is_2over() {
361
  static const StackTransform t_2over{2, 3, 0};
362
  return is_same_as(t_2over);
363
}
364

365
bool Optimizer::is_2dup() {
366
  static const StackTransform t_2dup{0, 1, 0};
367
  return is_same_as(t_2dup);
368
}
369

370
bool Optimizer::is_tuck() {
371
  static const StackTransform t_tuck{0, 1, 0, 2};
372
  return is_same_as(t_tuck);
373
}
374

375
bool Optimizer::is_2drop() {
376
  static const StackTransform t_2drop{2};
377
  return is_same_as(t_2drop);
378
}
379

380
bool Optimizer::is_rot() {
381
  return is_pred([](const auto& t) { return t.is_rot(); });
382
}
383

384
bool Optimizer::is_rotrev() {
385
  return is_pred([](const auto& t) { return t.is_rotrev(); });
386
}
387

388
bool Optimizer::is_nop() {
389
  return is_pred([](const auto& t) { return t.is_id(); }, 1);
390
}
391

392
bool Optimizer::is_xchg(int* i, int* j) {
393
  return is_pred([i, j](const auto& t) { return t.is_xchg(i, j) && ((*i < 16 && *j < 16) || (!*i && *j < 256)); });
394
}
395

396
bool Optimizer::is_xchg_xchg(int* i, int* j, int* k, int* l) {
397
  return is_pred([i, j, k, l](const auto& t) {
398
           return t.is_xchg_xchg(i, j, k, l) && (*i < 2 && *j < (*i ? 16 : 256) && *k < 2 && *l < (*k ? 16 : 256));
399
         }) &&
400
         (!(p_ == 2 && op_[0]->is_xchg(*i, *j) && op_[1]->is_xchg(*k, *l)));
401
}
402

403
bool Optimizer::is_push(int* i) {
404
  return is_pred([i](const auto& t) { return t.is_push(i) && *i < 256; });
405
}
406

407
bool Optimizer::is_pop(int* i) {
408
  return is_pred([i](const auto& t) { return t.is_pop(i) && *i < 256; });
409
}
410

411
bool Optimizer::is_pop_pop(int* i, int* j) {
412
  return is_pred([i, j](const auto& t) { return t.is_pop_pop(i, j) && *i < 256 && *j < 256; }, 3);
413
}
414

415
bool Optimizer::is_push_rot(int* i) {
416
  return is_pred([i](const auto& t) { return t.is_push_rot(i) && *i < 16; }, 3);
417
}
418

419
bool Optimizer::is_push_rotrev(int* i) {
420
  return is_pred([i](const auto& t) { return t.is_push_rotrev(i) && *i < 16; }, 3);
421
}
422

423
bool Optimizer::is_push_xchg(int* i, int* j, int* k) {
424
  return is_pred([i, j, k](const auto& t) { return t.is_push_xchg(i, j, k) && *i < 16 && *j < 16 && *k < 16; }) &&
425
         !(p_ == 2 && op_[0]->is_push() && op_[1]->is_xchg());
426
}
427

428
bool Optimizer::is_xchg2(int* i, int* j) {
429
  return is_pred([i, j](const auto& t) { return t.is_xchg2(i, j) && *i < 16 && *j < 16; });
430
}
431

432
bool Optimizer::is_xcpu(int* i, int* j) {
433
  return is_pred([i, j](const auto& t) { return t.is_xcpu(i, j) && *i < 16 && *j < 16; });
434
}
435

436
bool Optimizer::is_puxc(int* i, int* j) {
437
  return is_pred([i, j](const auto& t) { return t.is_puxc(i, j) && *i < 16 && *j < 15; });
438
}
439

440
bool Optimizer::is_push2(int* i, int* j) {
441
  return is_pred([i, j](const auto& t) { return t.is_push2(i, j) && *i < 16 && *j < 16; });
442
}
443

444
bool Optimizer::is_xchg3(int* i, int* j, int* k) {
445
  return is_pred([i, j, k](const auto& t) { return t.is_xchg3(i, j, k) && *i < 16 && *j < 16 && *k < 16; });
446
}
447

448
bool Optimizer::is_xc2pu(int* i, int* j, int* k) {
449
  return is_pred([i, j, k](const auto& t) { return t.is_xc2pu(i, j, k) && *i < 16 && *j < 16 && *k < 16; });
450
}
451

452
bool Optimizer::is_xcpuxc(int* i, int* j, int* k) {
453
  return is_pred([i, j, k](const auto& t) { return t.is_xcpuxc(i, j, k) && *i < 16 && *j < 16 && *k < 15; });
454
}
455

456
bool Optimizer::is_xcpu2(int* i, int* j, int* k) {
457
  return is_pred([i, j, k](const auto& t) { return t.is_xcpu2(i, j, k) && *i < 16 && *j < 16 && *k < 16; });
458
}
459

460
bool Optimizer::is_puxc2(int* i, int* j, int* k) {
461
  return is_pred(
462
      [i, j, k](const auto& t) { return t.is_puxc2(i, j, k) && *i < 16 && *j < 15 && *k < 15 && *j + *k != -1; });
463
}
464

465
bool Optimizer::is_puxcpu(int* i, int* j, int* k) {
466
  return is_pred([i, j, k](const auto& t) { return t.is_puxcpu(i, j, k) && *i < 16 && *j < 15 && *k < 15; });
467
}
468

469
bool Optimizer::is_pu2xc(int* i, int* j, int* k) {
470
  return is_pred([i, j, k](const auto& t) { return t.is_pu2xc(i, j, k) && *i < 16 && *j < 15 && *k < 14; });
471
}
472

473
bool Optimizer::is_push3(int* i, int* j, int* k) {
474
  return is_pred([i, j, k](const auto& t) { return t.is_push3(i, j, k) && *i < 16 && *j < 16 && *k < 16; });
475
}
476

477
bool Optimizer::is_blkswap(int* i, int* j) {
478
  return is_pred([i, j](const auto& t) { return t.is_blkswap(i, j) && *i > 0 && *j > 0 && *i <= 16 && *j <= 16; });
479
}
480

481
bool Optimizer::is_blkpush(int* i, int* j) {
482
  return is_pred([i, j](const auto& t) { return t.is_blkpush(i, j) && *i > 0 && *i < 16 && *j < 16; });
483
}
484

485
bool Optimizer::is_blkdrop(int* i) {
486
  return is_pred([i](const auto& t) { return t.is_blkdrop(i) && *i > 0 && *i < 16; });
487
}
488

489
bool Optimizer::is_blkdrop2(int* i, int* j) {
490
  return is_pred([i, j](const auto& t) { return t.is_blkdrop2(i, j) && *i > 0 && *i < 16 && *j > 0 && *j < 16; });
491
}
492

493
bool Optimizer::is_reverse(int* i, int* j) {
494
  return is_pred([i, j](const auto& t) { return t.is_reverse(i, j) && *i >= 2 && *i <= 17 && *j < 16; });
495
}
496

497
bool Optimizer::is_nip_seq(int* i, int* j) {
498
  return is_pred([i, j](const auto& t) { return t.is_nip_seq(i, j) && *i >= 3 && *i <= 15; });
499
}
500

501
bool Optimizer::is_pop_blkdrop(int* i, int* k) {
502
  return is_pred([i, k](const auto& t) { return t.is_pop_blkdrop(i, k) && *i >= *k && *k >= 2 && *k <= 15; }, 3);
503
}
504

505
bool Optimizer::is_2pop_blkdrop(int* i, int* j, int* k) {
506
  return is_pred(
507
      [i, j, k](const auto& t) { return t.is_2pop_blkdrop(i, j, k) && *i >= *k && *j >= *k && *k >= 2 && *k <= 15; },
508
      3);
509
}
510

511
bool Optimizer::compute_stack_transforms() {
512
  StackTransform trans;
513
  for (int i = 0; i < l_; i++) {
514
    if (!apply_op(trans, *op_[i])) {
515
      l2_ = i;
516
      return true;
517
    }
518
    tr_[i] = trans;
519
  }
520
  l2_ = l_;
521
  return true;
522
}
523

524
bool Optimizer::show_stack_transforms() const {
525
  show_head();
526
  // slow version
527
  /*
528
  StackTransform trans2;
529
  std::cerr << "id = " << trans2 << std::endl;
530
  for (int i = 0; i < l_; i++) {
531
    StackTransform op;
532
    if (!apply_op(op, *op_[i])) {
533
      std::cerr << "* (" << *op_[i] << " = invalid)\n";
534
      break;
535
    }
536
    trans2 *= op;
537
    std::cerr << "* " << *op_[i] << " = " << op << " -> " << trans2 << std::endl;
538
  }
539
  */
540
  // fast version
541
  StackTransform trans;
542
  for (int i = 0; i < l_; i++) {
543
    std::cerr << trans << std::endl << *op_[i] << " -> ";
544
    if (!apply_op(trans, *op_[i])) {
545
      std::cerr << " <not-applicable>" << std::endl;
546
      return true;
547
    }
548
  }
549
  std::cerr << trans << std::endl;
550
  return true;
551
}
552

553
bool Optimizer::find_at_least(int pb) {
554
  p_ = q_ = 0;
555
  pb_ = pb;
556
  // show_stack_transforms();
557
  int i, j, k, l, c;
558
  return (is_push_const(&i, &c) && rewrite_push_const(i, c)) || (is_nop() && rewrite_nop()) ||
559
         (!(mode_ & 1) && is_const_rot(&c) && rewrite_const_rot(c)) ||
560
         (is_const_push_xchgs() && rewrite_const_push_xchgs()) || (is_const_pop(&c, &i) && rewrite_const_pop(c, i)) ||
561
         (is_xchg(&i, &j) && rewrite(AsmOp::Xchg(i, j))) || (is_push(&i) && rewrite(AsmOp::Push(i))) ||
562
         (is_pop(&i) && rewrite(AsmOp::Pop(i))) || (is_pop_pop(&i, &j) && rewrite(AsmOp::Pop(i), AsmOp::Pop(j))) ||
563
         (is_xchg_xchg(&i, &j, &k, &l) && rewrite(AsmOp::Xchg(i, j), AsmOp::Xchg(k, l))) ||
564
         (!(mode_ & 1) &&
565
          ((is_rot() && rewrite(AsmOp::Custom("ROT", 3, 3))) || (is_rotrev() && rewrite(AsmOp::Custom("-ROT", 3, 3))) ||
566
           (is_2dup() && rewrite(AsmOp::Custom("2DUP", 2, 4))) ||
567
           (is_2swap() && rewrite(AsmOp::Custom("2SWAP", 2, 4))) ||
568
           (is_2over() && rewrite(AsmOp::Custom("2OVER", 2, 4))) ||
569
           (is_tuck() && rewrite(AsmOp::Custom("TUCK", 2, 3))) ||
570
           (is_2drop() && rewrite(AsmOp::Custom("2DROP", 2, 0))) || (is_xchg2(&i, &j) && rewrite(AsmOp::Xchg2(i, j))) ||
571
           (is_xcpu(&i, &j) && rewrite(AsmOp::XcPu(i, j))) || (is_puxc(&i, &j) && rewrite(AsmOp::PuXc(i, j))) ||
572
           (is_push2(&i, &j) && rewrite(AsmOp::Push2(i, j))) || (is_blkswap(&i, &j) && rewrite(AsmOp::BlkSwap(i, j))) ||
573
           (is_blkpush(&i, &j) && rewrite(AsmOp::BlkPush(i, j))) || (is_blkdrop(&i) && rewrite(AsmOp::BlkDrop(i))) ||
574
           (is_push_rot(&i) && rewrite(AsmOp::Push(i), AsmOp::Custom("ROT"))) ||
575
           (is_push_rotrev(&i) && rewrite(AsmOp::Push(i), AsmOp::Custom("-ROT"))) ||
576
           (is_push_xchg(&i, &j, &k) && rewrite(AsmOp::Push(i), AsmOp::Xchg(j, k))) ||
577
           (is_reverse(&i, &j) && rewrite(AsmOp::BlkReverse(i, j))) ||
578
           (is_blkdrop2(&i, &j) && rewrite(AsmOp::BlkDrop2(i, j))) ||
579
           (is_nip_seq(&i, &j) && rewrite(AsmOp::Xchg(i, j), AsmOp::BlkDrop(i))) ||
580
           (is_pop_blkdrop(&i, &k) && rewrite(AsmOp::Pop(i), AsmOp::BlkDrop(k))) ||
581
           (is_2pop_blkdrop(&i, &j, &k) && (k >= 3 && k <= 13 && i != j + 1 && i <= 15 && j <= 14
582
                                                ? rewrite(AsmOp::Xchg2(j + 1, i), AsmOp::BlkDrop(k + 2))
583
                                                : rewrite(AsmOp::Pop(i), AsmOp::Pop(j), AsmOp::BlkDrop(k)))) ||
584
           (is_xchg3(&i, &j, &k) && rewrite(AsmOp::Xchg3(i, j, k))) ||
585
           (is_xc2pu(&i, &j, &k) && rewrite(AsmOp::Xc2Pu(i, j, k))) ||
586
           (is_xcpuxc(&i, &j, &k) && rewrite(AsmOp::XcPuXc(i, j, k))) ||
587
           (is_xcpu2(&i, &j, &k) && rewrite(AsmOp::XcPu2(i, j, k))) ||
588
           (is_puxc2(&i, &j, &k) && rewrite(AsmOp::PuXc2(i, j, k))) ||
589
           (is_puxcpu(&i, &j, &k) && rewrite(AsmOp::PuXcPu(i, j, k))) ||
590
           (is_pu2xc(&i, &j, &k) && rewrite(AsmOp::Pu2Xc(i, j, k))) ||
591
           (is_push3(&i, &j, &k) && rewrite(AsmOp::Push3(i, j, k)))));
592
}
593

594
bool Optimizer::find() {
595
  if (!compute_stack_transforms()) {
596
    return false;
597
  }
598
  for (int pb = l_; pb > 0; --pb) {
599
    if (find_at_least(pb)) {
600
      return true;
601
    }
602
  }
603
  return false;
604
}
605

606
bool Optimizer::optimize() {
607
  bool f = false;
608
  while (find()) {
609
    f = true;
610
    apply();
611
    unpack();
612
  }
613
  return f;
614
}
615

616
AsmOpConsList optimize_code_head(AsmOpConsList op_list, int mode) {
617
  Optimizer opt(std::move(op_list), op_rewrite_comments, mode);
618
  opt.optimize();
619
  return opt.extract_code();
620
}
621

622
AsmOpConsList optimize_code(AsmOpConsList op_list, int mode) {
623
  std::vector<std::unique_ptr<AsmOp>> v;
624
  while (op_list) {
625
    if (!op_list->car->is_comment()) {
626
      op_list = optimize_code_head(std::move(op_list), mode);
627
    }
628
    if (op_list) {
629
      v.push_back(std::move(op_list->car));
630
      op_list = std::move(op_list->cdr);
631
    }
632
  }
633
  for (auto it = v.rbegin(); it < v.rend(); ++it) {
634
    op_list = AsmOpCons::cons(std::move(*it), std::move(op_list));
635
  }
636
  return std::move(op_list);
637
}
638

639
void optimize_code(AsmOpList& ops) {
640
  AsmOpConsList op_list;
641
  for (auto it = ops.list_.rbegin(); it < ops.list_.rend(); ++it) {
642
    op_list = AsmOpCons::cons(std::make_unique<AsmOp>(std::move(*it)), std::move(op_list));
643
  }
644
  for (int mode : {1, 1, 1, 1, 0, 0, 0, 0}) {
645
    op_list = optimize_code(std::move(op_list), mode);
646
  }
647
  ops.list_.clear();
648
  while (op_list) {
649
    ops.list_.push_back(std::move(*(op_list->car)));
650
    op_list = std::move(op_list->cdr);
651
  }
652
}
653

654
}  // namespace funC
655