deps/lightning/lib/lightning.c

   1 /*
   2  * Copyright (C) 2012-2022  Free Software Foundation, Inc.
   3  *
   4  * This file is part of GNU lightning.
   5  *
   6  * GNU lightning is free software; you can redistribute it and/or modify it
   7  * under the terms of the GNU Lesser General Public License as published
   8  * by the Free Software Foundation; either version 3, or (at your option)
   9  * any later version.
  10  *
  11  * GNU lightning is distributed in the hope that it will be useful, but
  12  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  13  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  14  * License for more details.
  15  *
  16  * Authors:
  17  *      Paulo Cesar Pereira de Andrade
  18  */
  19
  20 #include <lightning.h>
  21 #include <lightning/jit_private.h>
  22 #if HAVE_MMAP
  23 #  include <sys/mman.h>
  24 #endif
  25 #if defined(__sgi)
  26 #  include <fcntl.h>
  27 #endif
  28
  29 #ifndef MAP_ANON
  30 #  define MAP_ANON                      MAP_ANONYMOUS
  31 #  ifndef MAP_ANONYMOUS
  32 #    define MAP_ANONYMOUS               0
  33 #  endif
  34 #endif
  35
  36 #define jit_regload_reload              0       /* convert to reload */
  37 #define jit_regload_delete              1       /* just remove node */
  38 #define jit_regload_isdead              2       /* delete and unset live bit */
  39
  40 /*
  41  * Prototypes
  42  */
  43 static jit_word_t hash_data(const void*, jit_word_t);
  44
  45 #define new_pool()                      _new_pool(_jit)
  46 static void _new_pool(jit_state_t*);
  47
  48 #define new_node(u)                     _new_node(_jit, u)
  49 static jit_node_t *_new_node(jit_state_t*, jit_code_t);
  50
  51 #define link_node(u)                    _link_node(_jit, u)
  52 static inline jit_node_t *_link_node(jit_state_t*, jit_node_t*);
  53
  54 #define del_node(u, v)                  _del_node(_jit, u, v)
  55 static inline void _del_node(jit_state_t*, jit_node_t*, jit_node_t*);
  56
  57 #define free_node(u)                    _free_node(_jit, u)
  58 static inline void _free_node(jit_state_t*, jit_node_t*);
  59
  60 #define del_label(u, v)                 _del_label(_jit, u, v)
  61 static void _del_label(jit_state_t*, jit_node_t*, jit_node_t*);
  62
  63 #define jit_dataset()                   _jit_dataset(_jit)
  64 static void
  65 _jit_dataset(jit_state_t *_jit);
  66
  67 #define block_update_set(block, target) _block_update_set(_jit, block, target)
  68 static jit_bool_t _block_update_set(jit_state_t*, jit_block_t*, jit_block_t*);
  69
  70 #define check_block_again()             _check_block_again(_jit)
  71 static jit_bool_t _check_block_again(jit_state_t*);
  72
  73 #define do_setup()                      _do_setup(_jit)
  74 static void _do_setup(jit_state_t*);
  75
  76 #define jit_setup(block)                _jit_setup(_jit, block)
  77 static void
  78 _jit_setup(jit_state_t *_jit, jit_block_t *block);
  79
  80 #define do_follow(always)               _do_follow(_jit, always)
  81 static void _do_follow(jit_state_t*, jit_bool_t);
  82
  83 #define jit_follow(block)               _jit_follow(_jit, block)
  84 static void
  85 _jit_follow(jit_state_t *_jit, jit_block_t *block);
  86
  87 #define jit_update(node, live, mask)    _jit_update(_jit, node, live, mask)
  88 static void
  89 _jit_update(jit_state_t *_jit, jit_node_t *node,
  90             jit_regset_t *live, jit_regset_t *mask);
  91
  92 #define thread_jumps()                  _thread_jumps(_jit)
  93 static void
  94 _thread_jumps(jit_state_t *_jit);
  95
  96 #define sequential_labels()             _sequential_labels(_jit)
  97 static void
  98 _sequential_labels(jit_state_t *_jit);
  99
 100 #define split_branches()                _split_branches(_jit)
 101 static void
 102 _split_branches(jit_state_t *_jit);
 103
 104 #define shortcut_jump(prev, node)       _shortcut_jump(_jit, prev, node)
 105 static jit_bool_t
 106 _shortcut_jump(jit_state_t *_jit, jit_node_t *prev, jit_node_t *node);
 107
 108 #define redundant_jump(prev, node)      _redundant_jump(_jit, prev, node)
 109 static jit_bool_t
 110 _redundant_jump(jit_state_t *_jit, jit_node_t *prev, jit_node_t *node);
 111
 112 static jit_code_t
 113 reverse_jump_code(jit_code_t code);
 114
 115 #define reverse_jump(prev, node)        _reverse_jump(_jit, prev, node)
 116 static jit_bool_t
 117 _reverse_jump(jit_state_t *_jit, jit_node_t *prev, jit_node_t *node);
 118
 119 #define redundant_store(node, jump)     _redundant_store(_jit, node, jump)
 120 static jit_bool_t
 121 _redundant_store(jit_state_t *_jit, jit_node_t *node, jit_bool_t jump);
 122
 123 #define simplify_movr(p, n, k, s)       _simplify_movr(_jit, p, n, k, s)
 124 static jit_bool_t
 125 _simplify_movr(jit_state_t *_jit, jit_node_t *prev, jit_node_t *node,
 126                jit_int32_t kind, jit_int32_t size);
 127
 128 #define simplify_movi(p, n, k, s)       _simplify_movi(_jit, p, n, k, s)
 129 static jit_bool_t
 130 _simplify_movi(jit_state_t *_jit, jit_node_t *prev, jit_node_t *node,
 131                jit_int32_t kind, jit_int32_t size);
 132
 133 #define simplify_ldxi(prev, node)       _simplify_ldxi(_jit, prev, node)
 134 static jit_bool_t
 135 _simplify_ldxi(jit_state_t *_jit, jit_node_t *prev, jit_node_t *node);
 136
 137 #define simplify_stxi(prev, node)       _simplify_stxi(_jit, prev, node)
 138 static jit_bool_t
 139 _simplify_stxi(jit_state_t *_jit, jit_node_t *prev, jit_node_t *node);
 140
 141 #define simplify_spill(node, regno)     _simplify_spill(_jit, node, regno)
 142 static void
 143 _simplify_spill(jit_state_t *_jit, jit_node_t *node, jit_int32_t regno);
 144
 145 #define simplify()                      _simplify(_jit)
 146 static jit_bool_t
 147 _simplify(jit_state_t *_jit);
 148
 149 #define jit_reg_undef                   -1
 150 #define jit_reg_static                   0
 151 #define jit_reg_change                   1
 152 #define register_change_p(n, l, r)      _register_change_p(_jit, n, l, r)
 153 static jit_int32_t
 154 _register_change_p(jit_state_t *_jit, jit_node_t *node, jit_node_t *link,
 155                    jit_int32_t regno);
 156
 157 #define spill_reglive_p(node, regno)    _spill_reglive_p(_jit, node, regno)
 158 static jit_bool_t
 159 _spill_reglive_p(jit_state_t *_jit, jit_node_t *node, jit_int32_t regno);
 160
 161 #define patch_registers()               _patch_registers(_jit)
 162 static void
 163 _patch_registers(jit_state_t *_jit);
 164
 165 #define patch_register(n,l,r,p)         _patch_register(_jit,n,l,r,p)
 166 static void
 167 _patch_register(jit_state_t *jit, jit_node_t *node, jit_node_t *link,
 168                 jit_int32_t regno, jit_int32_t patch);
 169
 170 /*
 171  * Initialization
 172  */
 173 #if !defined(__sgi)
 174 #define  mmap_fd                        -1
 175 #endif
 176
 177 /*
 178  * Implementation
 179  */
 180 void
 181 init_jit(const char *progname)
 182 {
 183     jit_get_cpu();
 184     jit_init_debug(progname);
 185     jit_init_size();
 186 }
 187
 188 void
 189 finish_jit(void)
 190 {
 191     jit_finish_debug();
 192     jit_finish_size();
 193 }
 194
 195 jit_int32_t
 196 _jit_get_reg(jit_state_t *_jit, jit_int32_t regspec)
 197 {
 198     jit_int32_t         spec;
 199     jit_int32_t         regno;
 200
 201     spec = regspec & ~(jit_class_chk|jit_class_nospill);
 202     if (spec & jit_class_named) {
 203         regno = jit_regno(spec);
 204         if (jit_regset_tstbit(&_jitc->regsav, regno))
 205             /* fail if register is spilled */
 206             goto fail;
 207         if (jit_regset_tstbit(&_jitc->regarg, regno))
 208             /* fail if register is an argument to current instruction */
 209             goto fail;
 210         if (jit_regset_tstbit(&_jitc->reglive, regno)) {
 211             if (regspec & jit_class_nospill)
 212                 /* fail if register is live and should not spill/reload */
 213                 goto fail;
 214             goto spill;
 215         }
 216         jit_regset_setbit(&_jitc->regarg, regno);
 217         return (regno);
 218     }
 219     else
 220         assert(jit_class(spec) != 0);
 221
 222     if (_jitc->emit) {
 223         /* search for a free register matching spec */
 224         for (regno = 0; regno < _jitc->reglen; regno++) {
 225             if ((jit_class(_rvs[regno].spec) & spec) == spec &&
 226                 !jit_regset_tstbit(&_jitc->regarg, regno) &&
 227                 !jit_regset_tstbit(&_jitc->reglive, regno))
 228                 goto regarg;
 229         }
 230
 231         /* search for a register matching spec that is not an argument
 232          * for the current instruction */
 233         for (regno = 0; regno < _jitc->reglen; regno++) {
 234             if ((jit_class(_rvs[regno].spec) & spec) == spec &&
 235                 !jit_regset_tstbit(&_jitc->regsav, regno) &&
 236                 !jit_regset_tstbit(&_jitc->regarg, regno) &&
 237                 !(regspec & jit_class_nospill)) {
 238             spill:
 239                 assert(_jitc->function != NULL);
 240                 if (spec & jit_class_gpr) {
 241                     if (!_jitc->function->regoff[regno]) {
 242                         _jitc->function->regoff[regno] =
 243                             jit_allocai(sizeof(jit_word_t));
 244                         _jitc->again = 1;
 245                     }
 246 #if DEBUG
 247                     /* emit_stxi must not need temporary registers */
 248                     assert(!_jitc->getreg);
 249                     _jitc->getreg = 1;
 250 #endif
 251                     emit_stxi(_jitc->function->regoff[regno], JIT_FP, regno);
 252 #if DEBUG
 253                     _jitc->getreg = 0;
 254 #endif
 255                 }
 256                 else {
 257                     if (!_jitc->function->regoff[regno]) {
 258                         _jitc->function->regoff[regno] =
 259                             jit_allocai(sizeof(jit_float64_t));
 260                         _jitc->again = 1;
 261                     }
 262 #if DEBUG
 263                     /* emit_stxi must not need temporary registers */
 264                     assert(!_jitc->getreg);
 265                     _jitc->getreg = 1;
 266 #endif
 267                     emit_stxi_d(_jitc->function->regoff[regno], JIT_FP, regno);
 268 #if DEBUG
 269                     _jitc->getreg = 0;
 270 #endif
 271                 }
 272                 jit_regset_setbit(&_jitc->regsav, regno);
 273             regarg:
 274                 jit_regset_setbit(&_jitc->regarg, regno);
 275                 if (jit_class(_rvs[regno].spec) & jit_class_sav) {
 276                     /* if will modify callee save registers without a
 277                      * function prolog, better patch this assertion */
 278                     assert(_jitc->function != NULL);
 279                     if (!jit_regset_tstbit(&_jitc->function->regset, regno)) {
 280                         jit_regset_setbit(&_jitc->function->regset, regno);
 281                         _jitc->again = 1;
 282                     }
 283                 }
 284                 return (regno);
 285             }
 286         }
 287     }
 288     else {
 289         /* nospill hint only valid during emit" */
 290         assert(!(regspec & jit_class_nospill));
 291         for (regno = 0; regno < _jitc->reglen; regno++) {
 292             if ((jit_class(_rvs[regno].spec) & spec) == spec &&
 293                 !jit_regset_tstbit(&_jitc->regsav, regno) &&
 294                 !jit_regset_tstbit(&_jitc->regarg, regno)) {
 295                 jit_regset_setbit(&_jitc->regarg, regno);
 296                 jit_regset_setbit(&_jitc->regsav, regno);
 297                 jit_save(regno);
 298                 return (jit_regno_patch|regno);
 299             }
 300         }
 301     }
 302
 303     /* Out of hardware registers */
 304 fail:
 305     assert(regspec & jit_class_chk);
 306     return (JIT_NOREG);
 307 }
 308
 309 void
 310 _jit_unget_reg(jit_state_t *_jit, jit_int32_t regno)
 311 {
 312     regno = jit_regno(regno);
 313     if (jit_regset_tstbit(&_jitc->regsav, regno)) {
 314         if (_jitc->emit) {
 315 #if DEBUG
 316             /* emit_ldxi must not need a temporary register */
 317             assert(!_jitc->getreg);
 318             _jitc->getreg = 1;
 319 #endif
 320             if (jit_class(_rvs[regno].spec) & jit_class_gpr)
 321                 emit_ldxi(regno, JIT_FP, _jitc->function->regoff[regno]);
 322             else
 323                 emit_ldxi_d(regno, JIT_FP, _jitc->function->regoff[regno]);
 324 #if DEBUG
 325             /* emit_ldxi must not need a temporary register */
 326             _jitc->getreg = 0;
 327 #endif
 328         }
 329         else
 330             jit_load(regno);
 331         jit_regset_clrbit(&_jitc->regsav, regno);
 332     }
 333 #if defined(jit_carry)
 334     assert((regno == jit_carry /*&& _NOREG != jit_carry*/) ||
 335            jit_regset_tstbit(&_jitc->regarg, regno) != 0);
 336 #else
 337     assert(jit_regset_tstbit(&_jitc->regarg, regno) != 0);
 338 #endif
 339     jit_regset_clrbit(&_jitc->regarg, regno);
 340 }
 341
 342 jit_bool_t
 343 _jit_callee_save_p(jit_state_t *_jit, jit_int32_t regno)
 344 {
 345     assert(regno >= 0 && regno < JIT_NOREG);
 346     return (!!(_rvs[regno].spec & jit_class_sav));
 347 }
 348
 349 extern jit_bool_t
 350 _jit_pointer_p(jit_state_t *_jit, jit_pointer_t address)
 351 {
 352     return ((jit_uint8_t *)address >= _jit->code.ptr &&
 353             (jit_word_t)address < _jit->pc.w);
 354 }
 355
 356 #if __ia64__
 357 void
 358 jit_regset_com(jit_regset_t *u, jit_regset_t *v)
 359 {
 360     u->rl = ~v->rl;             u->rh = ~v->rh;
 361     u->fl = ~v->fl;             u->fh = ~v->fh;
 362 }
 363
 364 void
 365 jit_regset_and(jit_regset_t *u, jit_regset_t *v, jit_regset_t *w)
 366 {
 367     u->rl = v->rl & w->rl;      u->rh = v->rh & w->rh;
 368     u->fl = v->fl & w->fl;      u->fh = v->fh & w->fh;
 369 }
 370
 371 void
 372 jit_regset_ior(jit_regset_t *u, jit_regset_t *v, jit_regset_t *w)
 373 {
 374     u->rl = v->rl | w->rl;      u->rh = v->rh | w->rh;
 375     u->fl = v->fl | w->fl;      u->fh = v->fh | w->fh;
 376 }
 377
 378 void
 379 jit_regset_xor(jit_regset_t *u, jit_regset_t *v, jit_regset_t *w)
 380 {
 381     u->rl = v->rl ^ w->rl;      u->rh = v->rh ^ w->rh;
 382     u->fl = v->fl ^ w->fl;      u->fh = v->fh ^ w->fh;
 383 }
 384
 385 void
 386 jit_regset_set(jit_regset_t *u, jit_regset_t *v)
 387 {
 388     u->rl = v->rl;              u->rh = v->rh;
 389     u->fl = v->fl;              u->fh = v->fh;
 390 }
 391
 392 void
 393 jit_regset_set_mask(jit_regset_t *u, jit_int32_t v)
 394 {
 395     jit_bool_t          w = !!(v & (v - 1));
 396
 397     assert(v >= 0 && v <= 256);
 398     if (v == 0)
 399         u->rl = u->rh = u->fl = u->fh = -1LL;
 400     else if (v <= 64) {
 401         u->rl = w ? (1LL << v) - 1 : -1LL;
 402         u->rh = u->fl = u->fh = 0;
 403     }
 404     else if (v <= 128) {
 405         u->rl = -1LL;
 406         u->rh = w ? (1LL << (v - 64)) - 1 : -1LL;
 407         u->fl = u->fh = 0;
 408     }
 409     else if (v <= 192) {
 410         u->rl = u->rh = -1LL;
 411         u->fl = w ? (1LL << (v - 128)) - 1 : -1LL;
 412         u->fh = 0;
 413     }
 414     else {
 415         u->rl = u->rh = u->fl = -1LL;
 416         u->fh = w ? (1LL << (v - 128)) - 1 : -1LL;
 417     }
 418 }
 419
 420 jit_bool_t
 421 jit_regset_cmp_ui(jit_regset_t *u, jit_word_t v)
 422 {
 423     return !((u->rl == v && u->rh == 0 && u->fl == 0 && u->fh == 0));
 424 }
 425
 426 void
 427 jit_regset_set_ui(jit_regset_t *u, jit_word_t v)
 428 {
 429     u->rl = v;
 430     u->rh = u->fl = u->fh = 0;
 431 }
 432
 433 jit_bool_t
 434 jit_regset_set_p(jit_regset_t *u)
 435 {
 436     return (u->rl || u->rh || u->fl || u->fh);
 437 }
 438
 439 void
 440 jit_regset_clrbit(jit_regset_t *set, jit_int32_t bit)
 441 {
 442     assert(bit >= 0 && bit <= 255);
 443     if (bit < 64)
 444         set->rl &= ~(1LL << bit);
 445     else if (bit < 128)
 446         set->rh &= ~(1LL << (bit - 64));
 447     else if (bit < 192)
 448         set->fl &= ~(1LL << (bit - 128));
 449     else
 450         set->fh &= ~(1LL << (bit - 192));
 451 }
 452
 453 void
 454 jit_regset_setbit(jit_regset_t *set, jit_int32_t bit)
 455 {
 456     assert(bit >= 0 && bit <= 255);
 457     if (bit < 64)
 458         set->rl |= 1LL << bit;
 459     else if (bit < 128)
 460         set->rh |= 1LL << (bit - 64);
 461     else if (bit < 192)
 462         set->fl |= 1LL << (bit - 128);
 463     else
 464         set->fh |= 1LL << (bit - 192);
 465 }
 466
 467 jit_bool_t
 468 jit_regset_tstbit(jit_regset_t *set, jit_int32_t bit)
 469 {
 470     assert(bit >= 0 && bit <= 255);
 471     if (bit < 64)
 472         return (!!(set->rl & (1LL << bit)));
 473     else if (bit < 128)
 474         return (!!(set->rh & (1LL << (bit - 64))));
 475     else if (bit < 192)
 476         return (!!(set->fl & (1LL << (bit - 128))));
 477     return (!!(set->fh & (1LL << (bit - 192))));
 478 }
 479
 480 unsigned long
 481 jit_regset_scan1(jit_regset_t *set, jit_int32_t offset)
 482 {
 483     assert(offset >= 0 && offset <= 255);
 484     for (; offset < 64; offset++) {
 485         if (set->rl & (1LL << offset))
 486             return (offset);
 487     }
 488     for (; offset < 128; offset++) {
 489         if (set->rh & (1LL << (offset - 64)))
 490             return (offset);
 491     }
 492     for (; offset < 192; offset++) {
 493         if (set->fl & (1LL << (offset - 128)))
 494             return (offset);
 495     }
 496     for (; offset < 256; offset++) {
 497         if (set->fh & (1LL << (offset - 192)))
 498             return (offset);
 499     }
 500     return (ULONG_MAX);
 501 }
 502
 503 #elif __sparc__ && __WORDSIZE == 64
 504 void
 505 jit_regset_com(jit_regset_t *u, jit_regset_t *v)
 506 {
 507     u->rl = ~v->rl;             u->rh = ~v->rh;
 508 }
 509
 510 void
 511 jit_regset_and(jit_regset_t *u, jit_regset_t *v, jit_regset_t *w)
 512 {
 513     u->rl = v->rl & w->rl;      u->rh = v->rh & w->rh;
 514 }
 515
 516 void
 517 jit_regset_ior(jit_regset_t *u, jit_regset_t *v, jit_regset_t *w)
 518 {
 519     u->rl = v->rl | w->rl;      u->rh = v->rh | w->rh;
 520 }
 521
 522 void
 523 jit_regset_xor(jit_regset_t *u, jit_regset_t *v, jit_regset_t *w)
 524 {
 525     u->rl = v->rl ^ w->rl;      u->rh = v->rh ^ w->rh;
 526 }
 527
 528 void
 529 jit_regset_set(jit_regset_t *u, jit_regset_t *v)
 530 {
 531     u->rl = v->rl;              u->rh = v->rh;
 532 }
 533
 534 void
 535 jit_regset_set_mask(jit_regset_t *u, jit_int32_t v)
 536 {
 537     jit_bool_t          w = !!(v & (v - 1));
 538
 539     assert(v >= 0 && v <= 128);
 540     if (v == 0)
 541         u->rl = u->rh = -1LL;
 542     else if (v <= 64) {
 543         u->rl = w ? (1LL << v) - 1 : -1LL;
 544         u->rh = 0;
 545     }
 546     else {
 547         u->rl = -1LL;
 548         u->rh = w ? (1LL << (v - 64)) - 1 : -1LL;
 549     }
 550 }
 551
 552 jit_bool_t
 553 jit_regset_cmp_ui(jit_regset_t *u, jit_word_t v)
 554 {
 555     return !((u->rl == v && u->rh == 0));
 556 }
 557
 558 void
 559 jit_regset_set_ui(jit_regset_t *u, jit_word_t v)
 560 {
 561     u->rl = v;
 562     u->rh = 0;
 563 }
 564
 565 jit_bool_t
 566 jit_regset_set_p(jit_regset_t *u)
 567 {
 568     return (u->rl || u->rh);
 569 }
 570
 571 void
 572 jit_regset_clrbit(jit_regset_t *set, jit_int32_t bit)
 573 {
 574     assert(bit >= 0 && bit <= 128);
 575     if (bit < 64)
 576         set->rl &= ~(1LL << bit);
 577     else
 578         set->rh &= ~(1LL << (bit - 64));
 579 }
 580
 581 void
 582 jit_regset_setbit(jit_regset_t *set, jit_int32_t bit)
 583 {
 584     assert(bit >= 0 && bit <= 127);
 585     if (bit < 64)
 586         set->rl |= 1LL << bit;
 587     else
 588         set->rh |= 1LL << (bit - 64);
 589 }
 590
 591 jit_bool_t
 592 jit_regset_tstbit(jit_regset_t *set, jit_int32_t bit)
 593 {
 594     assert(bit >= 0 && bit <= 127);
 595     if (bit < 64)
 596         return (!!(set->rl & (1LL << bit)));
 597     else
 598         return (!!(set->rh & (1LL << (bit - 64))));
 599 }
 600
 601 unsigned long
 602 jit_regset_scan1(jit_regset_t *set, jit_int32_t offset)
 603 {
 604     assert(offset >= 0 && offset <= 127);
 605     for (; offset < 64; offset++) {
 606         if (set->rl & (1LL << offset))
 607             return (offset);
 608     }
 609     for (; offset < 128; offset++) {
 610         if (set->rh & (1LL << (offset - 64)))
 611             return (offset);
 612     }
 613     return (ULONG_MAX);
 614 }
 615
 616 #else
 617 unsigned long
 618 jit_regset_scan1(jit_regset_t *set, jit_int32_t offset)
 619 {
 620     jit_regset_t       mask;
 621     assert(offset >= 0 && offset <= 63);
 622     if ((mask = *set >> offset)) {
 623         for (;;) {
 624             if (mask & 1)
 625                 return (offset);
 626             mask >>= 1;
 627             ++offset;
 628         }
 629     }
 630     return (ULONG_MAX);
 631 }
 632 #endif
 633
 634 void
 635 _jit_save(jit_state_t *_jit, jit_int32_t reg)
 636 {
 637     reg = jit_regno(reg);
 638     assert(!_jitc->realize);
 639     _jitc->spill[reg] = jit_new_node_w(jit_code_save, reg);
 640 }
 641
 642 void
 643 _jit_load(jit_state_t *_jit, jit_int32_t reg)
 644 {
 645     jit_node_t          *node;
 646
 647     reg = jit_regno(reg);
 648     assert(!_jitc->realize);
 649     assert(_jitc->spill[reg] != NULL);
 650     node = jit_new_node_w(jit_code_load, reg);
 651     /* create a path to flag the save/load is not required */
 652     node->link = _jitc->spill[reg];
 653     node->link->link = node;
 654     _jitc->spill[reg] = NULL;
 655 }
 656
 657 static jit_word_t
 658 hash_data(const void *data, jit_word_t length)
 659 {
 660     const jit_uint8_t           *ptr;
 661     jit_word_t           i, key;
 662     for (i = key = 0, ptr = data; i < length; i++)
 663         key = (key << (key & 1)) ^ ptr[i];
 664     return (key);
 665 }
 666
 667 jit_pointer_t
 668 _jit_address(jit_state_t *_jit, jit_node_t *node)
 669 {
 670     assert(_jitc->done);
 671     assert(node != NULL &&
 672            /* If a node type that is documented to be a fixed marker */
 673            (node->code == jit_code_note || node->code == jit_code_name ||
 674             /* If another special fixed marker, returned by jit_indirect() */
 675             (node->code == jit_code_label && (node->flag & jit_flag_use) != 0)));
 676     return ((jit_pointer_t)node->u.w);
 677 }
 678
 679 jit_node_t *
 680 _jit_data(jit_state_t *_jit, const void *data,
 681           jit_word_t length, jit_int32_t align)
 682 {
 683     jit_word_t           key;
 684     jit_node_t          *node;
 685
 686     assert(!_jitc->realize);
 687
 688     /* Ensure there is space even if asking for a duplicate */
 689     if (((_jitc->data.offset + 7) & -8) + length > _jit->data.length) {
 690         jit_word_t       size;
 691
 692         size = (_jit->data.length + length + 4096) & - 4095;
 693         assert(size >= _jit->data.length);
 694         if (_jitc->data.ptr == NULL)
 695             jit_alloc((jit_pointer_t *)&_jitc->data.ptr, size);
 696         else
 697             jit_realloc((jit_pointer_t *)&_jitc->data.ptr,
 698                         _jit->data.length, size);
 699         _jit->data.length = size;
 700     }
 701     if (_jitc->data.table == NULL)
 702         jit_alloc((jit_pointer_t *)&_jitc->data.table,
 703                   (_jitc->data.size = 16) * sizeof(jit_node_t*));
 704
 705     key = hash_data(data, length) & (_jitc->data.size - 1);
 706     node = _jitc->data.table[key];
 707     for (; node; node = node->next) {
 708         if (node->v.w == length &&
 709             memcmp(_jitc->data.ptr + node->u.w, data, length) == 0)
 710             break;
 711     }
 712
 713     if (!node) {
 714         node = jit_new_node_no_link(jit_code_data);
 715         if (!align)
 716             align = length;
 717         switch (align) {
 718             case 0:     case 1:
 719                 break;
 720             case 2:
 721                 _jitc->data.offset = (_jitc->data.offset + 1) & -2;
 722                 break;
 723             case 3:     case 4:
 724                 _jitc->data.offset = (_jitc->data.offset + 3) & -4;
 725                 break;
 726             default:
 727                 _jitc->data.offset = (_jitc->data.offset + 7) & -8;
 728                 break;
 729         }
 730         node->u.w = _jitc->data.offset;
 731         node->v.w = length;
 732         jit_memcpy(_jitc->data.ptr + _jitc->data.offset, data, length);
 733         _jitc->data.offset += length;
 734
 735         node->next = _jitc->data.table[key];
 736         _jitc->data.table[key] = node;
 737         ++_jitc->data.count;
 738
 739         /* Rehash if more than 75% used table */
 740         if (_jitc->data.count >
 741             (_jitc->data.size >> 1) + (_jitc->data.size >> 2) &&
 742             (_jitc->data.size << 1) > _jitc->data.size) {
 743             jit_word_t    i;
 744             jit_node_t  **hash;
 745             jit_node_t   *next;
 746             jit_node_t   *temp;
 747
 748             jit_alloc((jit_pointer_t *)&hash,
 749                       (_jitc->data.size << 1) * sizeof(jit_node_t*));
 750             for (i = 0; i < _jitc->data.size; i++) {
 751                 temp = _jitc->data.table[i];
 752                 for (; temp; temp = next) {
 753                     next = temp->next;
 754                     key = hash_data(_jitc->data.ptr + temp->u.w, temp->v.w) &
 755                           ((_jitc->data.size << 1) - 1);
 756                     temp->next = hash[key];
 757                     hash[key] = temp;
 758                 }
 759             }
 760             jit_free((jit_pointer_t *)&_jitc->data.table);
 761             _jitc->data.table = hash;
 762             _jitc->data.size <<= 1;
 763         }
 764     }
 765
 766     return (node);
 767 }
 768
 769 static void
 770 _new_pool(jit_state_t *_jit)
 771 {
 772     jit_node_t          *list;
 773     jit_int32_t          offset;
 774
 775     if (_jitc->pool.offset >= _jitc->pool.length) {
 776         jit_int32_t      length;
 777
 778         length = _jitc->pool.length + 16;
 779         jit_realloc((jit_pointer_t *)&_jitc->pool.ptr,
 780                     _jitc->pool.length * sizeof(jit_node_t *),
 781                     length * sizeof(jit_node_t *));
 782         _jitc->pool.length = length;
 783     }
 784     jit_alloc((jit_pointer_t *)(_jitc->pool.ptr + _jitc->pool.offset),
 785               sizeof(jit_node_t) * 1024);
 786     list = _jitc->pool.ptr[_jitc->pool.offset];
 787     for (offset = 1; offset < 1024; offset++, list++)
 788         list->next = list + 1;
 789     list->next = _jitc->list;
 790     _jitc->list = _jitc->pool.ptr[_jitc->pool.offset];
 791     ++_jitc->pool.offset;
 792 }
 793
 794 static jit_node_t *
 795 _new_node(jit_state_t *_jit, jit_code_t code)
 796 {
 797     jit_node_t          *node;
 798
 799     if (_jitc->list == NULL)
 800         new_pool();
 801     node = _jitc->list;
 802     _jitc->list = node->next;
 803     if (_jitc->synth)
 804         node->flag |= jit_flag_synth;
 805     node->next = NULL;
 806     node->code = code;
 807
 808     return (node);
 809 }
 810
 811 static inline jit_node_t *
 812 _link_node(jit_state_t *_jit, jit_node_t *node)
 813 {
 814     if (_jitc->tail)
 815         _jitc->tail->next = node;
 816     else
 817         _jitc->head = node;
 818     return (_jitc->tail = node);
 819 }
 820
 821 static inline void
 822 _del_node(jit_state_t *_jit, jit_node_t *prev, jit_node_t *node)
 823 {
 824     if (prev == node) {
 825         assert(prev == _jitc->head);
 826         _jitc->head = node->next;
 827     }
 828     else
 829         prev->next = node->next;
 830     memset(node, 0, sizeof(jit_node_t));
 831     node->next = _jitc->list;
 832     _jitc->list = node;
 833 }
 834
 835 static inline void
 836 _free_node(jit_state_t *_jit, jit_node_t *node)
 837 {
 838     memset(node, 0, sizeof(jit_node_t));
 839     node->next = _jitc->list;
 840     _jitc->list = node;
 841 }
 842
 843 static void
 844 _del_label(jit_state_t *_jit, jit_node_t *prev, jit_node_t *node)
 845 {
 846     jit_block_t         *block;
 847
 848     /* only allow call to del_label on linked labels */
 849     block = _jitc->blocks.ptr + node->v.w;
 850     assert(block->label == node);
 851
 852     /* del_label() should only be called when optimizing.
 853      * This will leave an empty block index */
 854     jit_regset_del(&block->reglive);
 855     jit_regset_del(&block->regmask);
 856     block->label = NULL;
 857
 858     /* redundant, should be already true */
 859     assert(node->link == NULL);
 860     del_node(prev, node);
 861 }
 862
 863 jit_state_t *
 864 jit_new_state(void)
 865 {
 866     jit_state_t         *_jit;
 867
 868     jit_alloc((jit_pointer_t *)&_jit, sizeof(jit_state_t));
 869     jit_alloc((jit_pointer_t *)&_jitc, sizeof(jit_compiler_t));
 870     jit_regset_new(&_jitc->regarg);
 871     jit_regset_new(&_jitc->regsav);
 872     jit_regset_new(&_jitc->reglive);
 873     jit_regset_new(&_jitc->regmask);
 874
 875     jit_init();
 876
 877     jit_alloc((jit_pointer_t *)&_jitc->spill,
 878               _jitc->reglen * sizeof(jit_node_t*));
 879     jit_alloc((jit_pointer_t *)&_jitc->gen,
 880               _jitc->reglen * sizeof(jit_int32_t));
 881     jit_alloc((jit_pointer_t *)&_jitc->values,
 882               _jitc->reglen * sizeof(jit_value_t));
 883
 884     jit_alloc((jit_pointer_t *)&_jitc->patches.ptr,
 885               (_jitc->patches.length = 1024) * sizeof(jit_patch_t));
 886     jit_alloc((jit_pointer_t *)&_jitc->functions.ptr,
 887               (_jitc->functions.length = 16) * sizeof(jit_function_t));
 888     jit_alloc((jit_pointer_t *)&_jitc->pool.ptr,
 889               (_jitc->pool.length = 16) * sizeof(jit_node_t*));
 890     jit_alloc((jit_pointer_t *)&_jitc->blocks.ptr,
 891               (_jitc->blocks.length = 16) * sizeof(jit_block_t));
 892 #if __arm__ && DISASSEMBLER
 893     jit_alloc((jit_pointer_t *)&_jitc->data_info.ptr,
 894               (_jitc->data_info.length = 1024) * sizeof(jit_data_info_t));
 895 #endif
 896
 897     /* allocate at most one extra note in case jit_name() is
 898      * never called, or called after adding at least one note */
 899     _jit->note.length = 1;
 900     _jitc->note.size = sizeof(jit_note_t);
 901
 902     return (_jit);
 903 }
 904
 905 void
 906 _jit_clear_state(jit_state_t *_jit)
 907 {
 908 #if DEVEL_DISASSEMBLER
 909 #  define jit_really_clear_state()      _jit_really_clear_state(_jit)
 910 }
 911
 912 void _jit_really_clear_state(jit_state_t *_jit)
 913 {
 914 #endif
 915     jit_word_t           offset;
 916     jit_function_t      *function;
 917
 918     /* release memory not required at jit execution time and set
 919      * pointers to NULL to explicitly know they are released */
 920     _jitc->head = _jitc->tail = NULL;
 921
 922     jit_free((jit_pointer_t *)&_jitc->data.table);
 923     _jitc->data.size = _jitc->data.count = 0;
 924
 925     jit_free((jit_pointer_t *)&_jitc->spill);
 926     jit_free((jit_pointer_t *)&_jitc->gen);
 927     jit_free((jit_pointer_t *)&_jitc->values);
 928
 929     jit_free((jit_pointer_t *)&_jitc->blocks.ptr);
 930
 931     jit_free((jit_pointer_t *)&_jitc->patches.ptr);
 932     _jitc->patches.offset = _jitc->patches.length = 0;
 933
 934     for (offset = 0; offset < _jitc->functions.offset; offset++) {
 935         function = _jitc->functions.ptr + offset;
 936         jit_free((jit_pointer_t *)&function->regoff);
 937     }
 938     jit_free((jit_pointer_t *)&_jitc->functions.ptr);
 939     _jitc->functions.offset = _jitc->functions.length = 0;
 940     _jitc->function = NULL;
 941
 942     for (offset = 0; offset < _jitc->pool.offset; offset++)
 943         jit_free((jit_pointer_t *)(_jitc->pool.ptr + offset));
 944     jit_free((jit_pointer_t *)&_jitc->pool.ptr);
 945     _jitc->pool.offset = _jitc->pool.length = 0;
 946     _jitc->list = NULL;
 947
 948     _jitc->note.head = _jitc->note.tail =
 949         _jitc->note.name = _jitc->note.note = NULL;
 950     _jitc->note.base = NULL;
 951
 952 #if __arm__ && DISASSEMBLER
 953     jit_free((jit_pointer_t *)&_jitc->data_info.ptr);
 954 #endif
 955
 956 #if (__powerpc__ && _CALL_AIXDESC) || __ia64__
 957     jit_free((jit_pointer_t *)&_jitc->prolog.ptr);
 958 #endif
 959
 960 #if __ia64__
 961     jit_regset_del(&_jitc->regs);
 962 #endif
 963
 964     jit_free((jit_pointer_t *)&_jitc);
 965 }
 966
 967 void
 968 _jit_destroy_state(jit_state_t *_jit)
 969 {
 970 #if DEVEL_DISASSEMBLER
 971     jit_really_clear_state();
 972 #endif
 973 #if HAVE_MMAP
 974     if (!_jit->user_code)
 975         munmap(_jit->code.ptr, _jit->code.length);
 976     if (!_jit->user_data)
 977         munmap(_jit->data.ptr, _jit->data.length);
 978 #endif
 979     jit_free((jit_pointer_t *)&_jit);
 980 }
 981
 982 void
 983 _jit_synth_inc(jit_state_t *_jit)
 984 {
 985     assert(_jitc->synth < 8);
 986     ++_jitc->synth;
 987 }
 988
 989 jit_node_t *
 990 _jit_new_node(jit_state_t *_jit, jit_code_t code)
 991 {
 992     assert(!_jitc->realize);
 993     return (link_node(new_node(code)));
 994 }
 995
 996 jit_node_t *
 997 _jit_new_node_no_link(jit_state_t *_jit, jit_code_t code)
 998 {
 999     assert(!_jitc->realize);
1000     return (new_node(code));
1001 }
1002
1003 void
1004 _jit_link_node(jit_state_t *_jit, jit_node_t *node)
1005 {
1006     assert(!_jitc->realize);
1007     link_node(node);
1008 }
1009
1010 void
1011 _jit_synth_dec(jit_state_t *_jit)
1012 {
1013     assert(_jitc->synth > 0);
1014     --_jitc->synth;
1015 }
1016
1017 jit_node_t *
1018 _jit_new_node_w(jit_state_t *_jit, jit_code_t code,
1019                 jit_word_t u)
1020 {
1021     jit_node_t          *node = new_node(code);
1022     assert(!_jitc->realize);
1023     node->u.w = u;
1024     return (link_node(node));
1025 }
1026
1027 jit_node_t *
1028 _jit_new_node_f(jit_state_t *_jit, jit_code_t code,
1029                 jit_float32_t u)
1030 {
1031     jit_node_t          *node = new_node(code);
1032     assert(!_jitc->realize);
1033     node->u.f = u;
1034     return (link_node(node));
1035 }
1036
1037 jit_node_t *
1038 _jit_new_node_d(jit_state_t *_jit, jit_code_t code,
1039                 jit_float64_t u)
1040 {
1041     jit_node_t          *node = new_node(code);
1042     assert(!_jitc->realize);
1043     node->u.d = u;
1044     return (link_node(node));
1045 }
1046
1047 jit_node_t *
1048 _jit_new_node_p(jit_state_t *_jit, jit_code_t code,
1049                 jit_pointer_t u)
1050 {
1051     jit_node_t          *node = new_node(code);
1052     assert(!_jitc->realize);
1053     node->u.p = u;
1054     return (link_node(node));
1055 }
1056
1057 jit_node_t *
1058 _jit_new_node_ww(jit_state_t *_jit, jit_code_t code,
1059                  jit_word_t u, jit_word_t v)
1060 {
1061     jit_node_t          *node = new_node(code);
1062     assert(!_jitc->realize);
1063     node->u.w = u;
1064     node->v.w = v;
1065     return (link_node(node));
1066 }
1067
1068 jit_node_t *
1069 _jit_new_node_wp(jit_state_t *_jit, jit_code_t code,
1070                  jit_word_t u, jit_pointer_t v)
1071 {
1072     return (jit_new_node_ww(code, u, (jit_word_t)v));
1073 }
1074
1075 jit_node_t *
1076 _jit_new_node_fp(jit_state_t *_jit, jit_code_t code,
1077                  jit_float32_t u, jit_pointer_t v)
1078 {
1079     jit_node_t          *node = new_node(code);
1080     assert(!_jitc->realize);
1081     node->u.f = u;
1082     node->v.w = (jit_word_t)v;
1083     return (link_node(node));
1084 }
1085
1086 jit_node_t *
1087 _jit_new_node_dp(jit_state_t *_jit, jit_code_t code,
1088                  jit_float64_t u, jit_pointer_t v)
1089 {
1090     jit_node_t          *node = new_node(code);
1091     assert(!_jitc->realize);
1092     node->u.d = u;
1093     node->v.w = (jit_word_t)v;
1094     return (link_node(node));
1095 }
1096
1097 jit_node_t *
1098 _jit_new_node_pw(jit_state_t *_jit, jit_code_t code,
1099                  jit_pointer_t u, jit_word_t v)
1100 {
1101     return (jit_new_node_ww(code, (jit_word_t)u, v));
1102 }
1103
1104 jit_node_t *
1105 _jit_new_node_wf(jit_state_t *_jit, jit_code_t code,
1106                  jit_word_t u, jit_float32_t v)
1107 {
1108     jit_node_t          *node = new_node(code);
1109     assert(!_jitc->realize);
1110     node->u.w = u;
1111     node->v.f = v;
1112     return (link_node(node));
1113 }
1114
1115 jit_node_t *
1116 _jit_new_node_wd(jit_state_t *_jit, jit_code_t code,
1117                  jit_word_t u, jit_float64_t v)
1118 {
1119     jit_node_t          *node = new_node(code);
1120     assert(!_jitc->realize);
1121     node->u.w = u;
1122     node->v.d = v;
1123     return (link_node(node));
1124 }
1125
1126 jit_node_t *
1127 _jit_new_node_www(jit_state_t *_jit, jit_code_t code,
1128                   jit_word_t u, jit_word_t v, jit_word_t w)
1129 {
1130     jit_node_t          *node = new_node(code);
1131     assert(!_jitc->realize);
1132     node->u.w = u;
1133     node->v.w = v;
1134     node->w.w = w;
1135     return (link_node(node));
1136 }
1137
1138 jit_node_t *
1139 _jit_new_node_qww(jit_state_t *_jit, jit_code_t code,
1140                   jit_int32_t l, jit_int32_t h,
1141                   jit_word_t v, jit_word_t w)
1142 {
1143     jit_node_t          *node = new_node(code);
1144     assert(!_jitc->realize);
1145     assert(l != h);
1146     node->u.q.l = l;
1147     node->u.q.h = h;
1148     node->v.w = v;
1149     node->w.w = w;
1150     return (link_node(node));
1151 }
1152
1153 jit_node_t *
1154 _jit_new_node_wwq(jit_state_t *_jit, jit_code_t code,
1155                   jit_word_t u, jit_word_t v,
1156                   jit_int32_t l, jit_int32_t h)
1157 {
1158     jit_node_t          *node = new_node(code);
1159     assert(!_jitc->realize);
1160     node->u.w = u;
1161     node->v.w = v;
1162     node->w.q.l = l;
1163     node->w.q.h = h;
1164     return (link_node(node));
1165 }
1166
1167 jit_node_t *
1168 _jit_new_node_wwf(jit_state_t *_jit, jit_code_t code,
1169                   jit_word_t u, jit_word_t v, jit_float32_t w)
1170 {
1171     jit_node_t          *node = new_node(code);
1172     assert(!_jitc->realize);
1173     node->u.w = u;
1174     node->v.w = v;
1175     node->w.f = w;
1176     return (link_node(node));
1177 }
1178
1179 jit_node_t *
1180 _jit_new_node_wwd(jit_state_t *_jit, jit_code_t code,
1181                   jit_word_t u, jit_word_t v, jit_float64_t w)
1182 {
1183     jit_node_t          *node = new_node(code);
1184     assert(!_jitc->realize);
1185     node->u.w = u;
1186     node->v.w = v;
1187     node->w.d = w;
1188     return (link_node(node));
1189 }
1190
1191 jit_node_t *
1192 _jit_new_node_pww(jit_state_t *_jit, jit_code_t code,
1193                   jit_pointer_t u, jit_word_t v, jit_word_t w)
1194 {
1195     jit_node_t          *node = new_node(code);
1196     assert(!_jitc->realize);
1197     node->u.p = u;
1198     node->v.w = v;
1199     node->w.w = w;
1200     return (link_node(node));
1201 }
1202
1203 jit_node_t *
1204 _jit_new_node_pwf(jit_state_t *_jit, jit_code_t code,
1205                   jit_pointer_t u, jit_word_t v, jit_float32_t w)
1206 {
1207     jit_node_t          *node = new_node(code);
1208     assert(!_jitc->realize);
1209     node->u.p = u;
1210     node->v.w = v;
1211     node->w.f = w;
1212     return (link_node(node));
1213 }
1214
1215 jit_node_t *
1216 _jit_new_node_pwd(jit_state_t *_jit, jit_code_t code,
1217                   jit_pointer_t u, jit_word_t v, jit_float64_t w)
1218 {
1219     jit_node_t          *node = new_node(code);
1220     assert(!_jitc->realize);
1221     node->u.p = u;
1222     node->v.w = v;
1223     node->w.d = w;
1224     return (link_node(node));
1225 }
1226
1227 jit_node_t *
1228 _jit_label(jit_state_t *_jit)
1229 {
1230     jit_node_t          *node;
1231
1232     if (!(node = _jitc->tail) || node->code != jit_code_label) {
1233         node = jit_forward();
1234         jit_link(node);
1235     }
1236
1237     return (node);
1238 }
1239
1240 jit_node_t *
1241 _jit_forward(jit_state_t *_jit)
1242 {
1243     return (jit_new_node_no_link(jit_code_label));
1244 }
1245
1246 jit_node_t *
1247 _jit_indirect(jit_state_t *_jit)
1248 {
1249     jit_node_t          *node;
1250
1251     node = jit_label();
1252     node->flag |= jit_flag_use;
1253
1254     return (node);
1255 }
1256
1257 void
1258 _jit_link(jit_state_t *_jit, jit_node_t *node)
1259 {
1260     jit_block_t         *block;
1261
1262     assert((node->code == jit_code_label ||
1263             node->code == jit_code_prolog ||
1264             node->code == jit_code_epilog) && !node->next);
1265     jit_link_node(node);
1266     if (_jitc->blocks.offset >= _jitc->blocks.length) {
1267         jit_word_t        length;
1268
1269         length = _jitc->blocks.length + 16;
1270         jit_realloc((jit_pointer_t *)&_jitc->blocks.ptr,
1271                     _jitc->blocks.length * sizeof(jit_block_t),
1272                     length * sizeof(jit_block_t));
1273         _jitc->blocks.length = length;
1274     }
1275     block = _jitc->blocks.ptr + _jitc->blocks.offset;
1276     block->label = node;
1277     node->v.w = _jitc->blocks.offset;
1278     jit_regset_new(&block->reglive);
1279     jit_regset_new(&block->regmask);
1280     ++_jitc->blocks.offset;
1281 }
1282
1283 jit_bool_t
1284 _jit_forward_p(jit_state_t *_jit, jit_node_t *node)
1285 {
1286     return (node->code == jit_code_label && !node->next && node != _jitc->tail);
1287 }
1288
1289 jit_bool_t
1290 _jit_indirect_p(jit_state_t *_jit, jit_node_t *node)
1291 {
1292     return (node->code == jit_code_label && !!(node->flag & jit_flag_use));
1293 }
1294
1295 jit_bool_t
1296 _jit_target_p(jit_state_t *_jit, jit_node_t *node)
1297 {
1298     return (node->code == jit_code_label && !!node->link);
1299 }
1300
1301 void
1302 _jit_prepare(jit_state_t *_jit)
1303 {
1304     assert(_jitc->function != NULL);
1305     _jitc->function->call.call = jit_call_default;
1306     _jitc->function->call.argi =
1307         _jitc->function->call.argf =
1308         _jitc->function->call.size = 0;
1309     _jitc->prepare = jit_new_node(jit_code_prepare);
1310 }
1311
1312 void
1313 _jit_patch(jit_state_t* _jit, jit_node_t *instr)
1314 {
1315     jit_node_t          *label;
1316
1317     if (!(label = _jitc->tail) || label->code != jit_code_label)
1318         label = jit_label();
1319     jit_patch_at(instr, label);
1320 }
1321
1322 jit_int32_t
1323 _jit_classify(jit_state_t *_jit, jit_code_t code)
1324 {
1325     jit_int32_t         mask;
1326
1327     switch (code) {
1328         case jit_code_data:     case jit_code_save:     case jit_code_load:
1329         case jit_code_name:     case jit_code_label:    case jit_code_note:
1330         case jit_code_prolog:   case jit_code_ellipsis: case jit_code_va_push:
1331         case jit_code_epilog:   case jit_code_ret:      case jit_code_prepare:
1332             mask = 0;
1333             break;
1334         case jit_code_live:     case jit_code_va_end:
1335         case jit_code_retr:     case jit_code_retr_f:   case jit_code_retr_d:
1336         case jit_code_pushargr: case jit_code_pushargr_f:
1337         case jit_code_pushargr_d:
1338         case jit_code_finishr:  /* synthesized will set jit_cc_a0_jmp */
1339             mask = jit_cc_a0_reg;
1340             break;
1341         case jit_code_align:    case jit_code_reti:     case jit_code_pushargi:
1342         case jit_code_finishi:  /* synthesized will set jit_cc_a0_jmp */
1343             mask = jit_cc_a0_int;
1344             break;
1345         case jit_code_reti_f:   case jit_code_pushargi_f:
1346             mask = jit_cc_a0_flt;
1347             break;
1348         case jit_code_reti_d:   case jit_code_pushargi_d:
1349             mask = jit_cc_a0_dbl;
1350             break;
1351         case jit_code_allocai:
1352             mask = jit_cc_a0_int|jit_cc_a1_int;
1353             break;
1354         case jit_code_arg:      case jit_code_arg_f:    case jit_code_arg_d:
1355             mask = jit_cc_a0_int|jit_cc_a0_arg;
1356             break;
1357         case jit_code_calli:    case jit_code_jmpi:
1358             mask = jit_cc_a0_jmp;
1359             break;
1360         case jit_code_callr:    case jit_code_jmpr:
1361             mask = jit_cc_a0_reg|jit_cc_a0_jmp;
1362             break;
1363         case jit_code_retval_c: case jit_code_retval_uc:
1364         case jit_code_retval_s: case jit_code_retval_us:
1365         case jit_code_retval_i: case jit_code_retval_ui:
1366         case jit_code_retval_l:
1367         case jit_code_retval_f: case jit_code_retval_d:
1368         case jit_code_va_start:
1369             mask = jit_cc_a0_reg|jit_cc_a0_chg;
1370             break;
1371         case jit_code_getarg_c: case jit_code_getarg_uc:
1372         case jit_code_getarg_s: case jit_code_getarg_us:
1373         case jit_code_getarg_i: case jit_code_getarg_ui:
1374         case jit_code_getarg_l:
1375         case jit_code_getarg_f: case jit_code_getarg_d:
1376             mask = jit_cc_a0_reg|jit_cc_a0_chg|jit_cc_a1_arg;
1377             break;
1378         case jit_code_putargr:  case jit_code_putargr_f:
1379         case jit_code_putargr_d:
1380             mask = jit_cc_a0_reg|jit_cc_a1_arg;
1381             break;
1382         case jit_code_putargi:
1383             mask = jit_cc_a0_int|jit_cc_a1_arg;
1384             break;
1385         case jit_code_putargi_f:
1386             mask = jit_cc_a0_flt|jit_cc_a1_arg;
1387             break;
1388         case jit_code_putargi_d:
1389             mask = jit_cc_a0_dbl|jit_cc_a1_arg;
1390             break;
1391         case jit_code_movi:     case jit_code_ldi_c:    case jit_code_ldi_uc:
1392         case jit_code_ldi_s:    case jit_code_ldi_us:   case jit_code_ldi_i:
1393         case jit_code_ldi_ui:   case jit_code_ldi_l:    case jit_code_ldi_f:
1394         case jit_code_ldi_d:
1395             mask = jit_cc_a0_reg|jit_cc_a0_chg|jit_cc_a1_int;
1396             break;
1397         case jit_code_movi_f:   case jit_code_movi_f_w:
1398             mask = jit_cc_a0_reg|jit_cc_a0_chg|jit_cc_a1_flt;
1399             break;
1400         case jit_code_movi_d:   case jit_code_movi_d_w:
1401             mask = jit_cc_a0_reg|jit_cc_a0_chg|jit_cc_a1_dbl;
1402             break;
1403         case jit_code_movi_d_ww:
1404             mask = jit_cc_a0_reg|jit_cc_a0_chg|jit_cc_a1_reg|jit_cc_a1_chg|
1405                    jit_cc_a2_dbl;
1406             break;
1407         case jit_code_negr:     case jit_code_comr:     case jit_code_movr:
1408         case jit_code_extr_c:   case jit_code_extr_uc:  case jit_code_extr_s:
1409         case jit_code_extr_us:  case jit_code_extr_i:   case jit_code_extr_ui:
1410         case jit_code_truncr_f_i:                       case jit_code_truncr_f_l:
1411         case jit_code_truncr_d_i:                       case jit_code_truncr_d_l:
1412         case jit_code_htonr_us: case jit_code_htonr_ui: case jit_code_htonr_ul:
1413         case jit_code_bswapr_us:        case jit_code_bswapr_ui:        case jit_code_bswapr_ul:
1414         case jit_code_ldr_c:    case jit_code_ldr_uc:
1415         case jit_code_ldr_s:    case jit_code_ldr_us:   case jit_code_ldr_i:
1416         case jit_code_ldr_ui:   case jit_code_ldr_l:    case jit_code_negr_f:
1417         case jit_code_absr_f:   case jit_code_sqrtr_f:  case jit_code_movr_f:
1418         case jit_code_extr_f:   case jit_code_extr_d_f: case jit_code_ldr_f:
1419         case jit_code_negr_d:   case jit_code_absr_d:   case jit_code_sqrtr_d:
1420         case jit_code_movr_d:   case jit_code_extr_d:   case jit_code_extr_f_d:
1421         case jit_code_ldr_d:
1422         case jit_code_movr_w_f: case jit_code_movr_f_w:
1423         case jit_code_movr_w_d: case jit_code_movr_d_w:
1424         case jit_code_va_arg:   case jit_code_va_arg_d:
1425             mask = jit_cc_a0_reg|jit_cc_a0_chg|jit_cc_a1_reg;
1426             break;
1427         case jit_code_movr_d_ww:
1428             mask = jit_cc_a0_reg|jit_cc_a0_chg|jit_cc_a1_reg|jit_cc_a1_chg|
1429                    jit_cc_a2_reg;
1430             break;
1431         case jit_code_addi:     case jit_code_addxi:    case jit_code_addci:
1432         case jit_code_subi:     case jit_code_subxi:    case jit_code_subci:
1433         case jit_code_rsbi:
1434         case jit_code_muli:     case jit_code_divi:     case jit_code_divi_u:
1435         case jit_code_remi:     case jit_code_remi_u:   case jit_code_andi:
1436         case jit_code_ori:      case jit_code_xori:     case jit_code_lshi:
1437         case jit_code_rshi:     case jit_code_rshi_u:   case jit_code_lti:
1438         case jit_code_lti_u:    case jit_code_lei:      case jit_code_lei_u:
1439         case jit_code_eqi:      case jit_code_gei:      case jit_code_gei_u:
1440         case jit_code_gti:      case jit_code_gti_u:    case jit_code_nei:
1441         case jit_code_ldxi_c:   case jit_code_ldxi_uc:  case jit_code_ldxi_s:
1442         case jit_code_ldxi_us:  case jit_code_ldxi_i:   case jit_code_ldxi_ui:
1443         case jit_code_ldxi_l:   case jit_code_ldxi_f:   case jit_code_ldxi_d:
1444             mask = jit_cc_a0_reg|jit_cc_a0_chg|jit_cc_a1_reg|jit_cc_a2_int;
1445             break;
1446         case jit_code_qmuli:    case jit_code_qmuli_u:
1447         case jit_code_qdivi:    case jit_code_qdivi_u:
1448             mask = jit_cc_a0_reg|jit_cc_a0_rlh|jit_cc_a0_chg|
1449                    jit_cc_a1_reg|jit_cc_a2_int;
1450             break;
1451         case jit_code_addi_f:   case jit_code_subi_f:   case jit_code_rsbi_f:
1452         case jit_code_muli_f:   case jit_code_divi_f:   case jit_code_lti_f:
1453         case jit_code_lei_f:    case jit_code_eqi_f:    case jit_code_gei_f:
1454         case jit_code_gti_f:    case jit_code_nei_f:    case jit_code_unlti_f:
1455         case jit_code_unlei_f:  case jit_code_uneqi_f:  case jit_code_ungei_f:
1456         case jit_code_ungti_f:  case jit_code_ltgti_f:  case jit_code_ordi_f:
1457         case jit_code_unordi_f:
1458             mask = jit_cc_a0_reg|jit_cc_a0_chg|jit_cc_a1_reg|jit_cc_a2_flt;
1459             break;
1460         case jit_code_addi_d:   case jit_code_subi_d:   case jit_code_rsbi_d:
1461         case jit_code_muli_d:   case jit_code_divi_d:   case jit_code_lti_d:
1462         case jit_code_lei_d:    case jit_code_eqi_d:    case jit_code_gei_d:
1463         case jit_code_gti_d:    case jit_code_nei_d:    case jit_code_unlti_d:
1464         case jit_code_unlei_d:  case jit_code_uneqi_d:  case jit_code_ungei_d:
1465         case jit_code_ungti_d:  case jit_code_ltgti_d:  case jit_code_ordi_d:
1466         case jit_code_unordi_d:
1467             mask = jit_cc_a0_reg|jit_cc_a0_chg|jit_cc_a1_reg|jit_cc_a2_dbl;
1468             break;
1469         case jit_code_addr:     case jit_code_addxr:    case jit_code_addcr:
1470         case jit_code_subr:     case jit_code_subxr:    case jit_code_subcr:
1471         case jit_code_mulr:     case jit_code_divr:     case jit_code_divr_u:
1472         case jit_code_remr:     case jit_code_remr_u:   case jit_code_andr:
1473         case jit_code_orr:      case jit_code_xorr:     case jit_code_lshr:
1474         case jit_code_rshr:     case jit_code_rshr_u:   case jit_code_ltr:
1475         case jit_code_ltr_u:    case jit_code_ler:      case jit_code_ler_u:
1476         case jit_code_eqr:      case jit_code_ger:      case jit_code_ger_u:
1477         case jit_code_gtr:      case jit_code_gtr_u:    case jit_code_ner:
1478         case jit_code_ldxr_c:   case jit_code_ldxr_uc:  case jit_code_ldxr_s:
1479         case jit_code_ldxr_us:  case jit_code_ldxr_i:   case jit_code_ldxr_ui:
1480         case jit_code_ldxr_l:   case jit_code_addr_f:   case jit_code_subr_f:
1481         case jit_code_mulr_f:   case jit_code_divr_f:   case jit_code_ltr_f:
1482         case jit_code_ler_f:    case jit_code_eqr_f:    case jit_code_ger_f:
1483         case jit_code_gtr_f:    case jit_code_ner_f:    case jit_code_unltr_f:
1484         case jit_code_unler_f:  case jit_code_uneqr_f:  case jit_code_unger_f:
1485         case jit_code_ungtr_f:  case jit_code_ltgtr_f:  case jit_code_ordr_f:
1486         case jit_code_unordr_f: case jit_code_ldxr_f:   case jit_code_addr_d:
1487         case jit_code_subr_d:   case jit_code_mulr_d:   case jit_code_divr_d:
1488         case jit_code_ltr_d:    case jit_code_ler_d:    case jit_code_eqr_d:
1489         case jit_code_ger_d:    case jit_code_gtr_d:    case jit_code_ner_d:
1490         case jit_code_unltr_d:  case jit_code_unler_d:  case jit_code_uneqr_d:
1491         case jit_code_unger_d:  case jit_code_ungtr_d:  case jit_code_ltgtr_d:
1492         case jit_code_ordr_d:   case jit_code_unordr_d: case jit_code_ldxr_d:
1493         case jit_code_movr_ww_d:
1494             mask = jit_cc_a0_reg|jit_cc_a0_chg|jit_cc_a1_reg|jit_cc_a2_reg;
1495             break;
1496         case jit_code_qmulr:    case jit_code_qmulr_u:
1497         case jit_code_qdivr:    case jit_code_qdivr_u:
1498             mask = jit_cc_a0_reg|jit_cc_a0_rlh|jit_cc_a0_chg|
1499                    jit_cc_a1_reg|jit_cc_a2_reg;
1500             break;
1501         case jit_code_sti_c:    case jit_code_sti_s:    case jit_code_sti_i:
1502         case jit_code_sti_l:    case jit_code_sti_f:    case jit_code_sti_d:
1503             mask = jit_cc_a0_int|jit_cc_a1_reg;
1504             break;
1505         case jit_code_blti:     case jit_code_blti_u:   case jit_code_blei:
1506         case jit_code_blei_u:   case jit_code_beqi:     case jit_code_bgei:
1507         case jit_code_bgei_u:   case jit_code_bgti:     case jit_code_bgti_u:
1508         case jit_code_bnei:     case jit_code_bmsi:     case jit_code_bmci:
1509             mask = jit_cc_a0_jmp|jit_cc_a1_reg|jit_cc_a2_int;
1510             break;
1511         case jit_code_blti_f:   case jit_code_blei_f:   case jit_code_beqi_f:
1512         case jit_code_bgei_f:   case jit_code_bgti_f:   case jit_code_bnei_f:
1513         case jit_code_bunlti_f: case jit_code_bunlei_f: case jit_code_buneqi_f:
1514         case jit_code_bungei_f: case jit_code_bungti_f: case jit_code_bltgti_f:
1515         case jit_code_bordi_f:  case jit_code_bunordi_f:
1516             mask = jit_cc_a0_jmp|jit_cc_a1_reg|jit_cc_a2_flt;
1517             break;
1518         case jit_code_blti_d:   case jit_code_blei_d:   case jit_code_beqi_d:
1519         case jit_code_bgei_d:   case jit_code_bgti_d:   case jit_code_bnei_d:
1520         case jit_code_bunlti_d: case jit_code_bunlei_d: case jit_code_buneqi_d:
1521         case jit_code_bungei_d: case jit_code_bungti_d: case jit_code_bltgti_d:
1522         case jit_code_bordi_d:  case jit_code_bunordi_d:
1523             mask = jit_cc_a0_jmp|jit_cc_a1_reg|jit_cc_a2_dbl;
1524             break;
1525         case jit_code_allocar:  /* synthesized instructions make it
1526                                  * equivalent to jit_cc_a0_chg */
1527         case jit_code_str_c:    case jit_code_str_s:    case jit_code_str_i:
1528         case jit_code_str_l:    case jit_code_str_f:    case jit_code_str_d:
1529             mask = jit_cc_a0_reg|jit_cc_a1_reg;
1530             break;
1531         case jit_code_stxi_c:   case jit_code_stxi_s:   case jit_code_stxi_i:
1532         case jit_code_stxi_l:   case jit_code_stxi_f:   case jit_code_stxi_d:
1533             mask = jit_cc_a0_int|jit_cc_a1_reg|jit_cc_a2_reg;
1534             break;
1535         case jit_code_bltr:     case jit_code_bltr_u:   case jit_code_bler:
1536         case jit_code_bler_u:   case jit_code_beqr:     case jit_code_bger:
1537         case jit_code_bger_u:   case jit_code_bgtr:     case jit_code_bgtr_u:
1538         case jit_code_bner:     case jit_code_bmsr:     case jit_code_bmcr:
1539         case jit_code_bltr_f:   case jit_code_bler_f:   case jit_code_beqr_f:
1540         case jit_code_bger_f:   case jit_code_bgtr_f:   case jit_code_bner_f:
1541         case jit_code_bunltr_f: case jit_code_bunler_f: case jit_code_buneqr_f:
1542         case jit_code_bunger_f: case jit_code_bungtr_f: case jit_code_bltgtr_f:
1543         case jit_code_bordr_f:  case jit_code_bunordr_f:case jit_code_bltr_d:
1544         case jit_code_bler_d:   case jit_code_beqr_d:   case jit_code_bger_d:
1545         case jit_code_bgtr_d:   case jit_code_bner_d:   case jit_code_bunltr_d:
1546         case jit_code_bunler_d: case jit_code_buneqr_d: case jit_code_bunger_d:
1547         case jit_code_bungtr_d: case jit_code_bltgtr_d: case jit_code_bordr_d:
1548         case jit_code_bunordr_d:
1549             mask = jit_cc_a0_jmp|jit_cc_a1_reg|jit_cc_a2_reg;
1550             break;
1551         case jit_code_boaddi:   case jit_code_boaddi_u: case jit_code_bxaddi:
1552         case jit_code_bxaddi_u: case jit_code_bosubi:   case jit_code_bosubi_u:
1553         case jit_code_bxsubi:   case jit_code_bxsubi_u:
1554             mask = jit_cc_a0_jmp|jit_cc_a1_reg|jit_cc_a1_chg|jit_cc_a2_int;
1555             break;
1556         case jit_code_stxr_c:   case jit_code_stxr_s:   case jit_code_stxr_i:
1557         case jit_code_stxr_l:   case jit_code_stxr_f:   case jit_code_stxr_d:
1558             mask = jit_cc_a0_reg|jit_cc_a1_reg|jit_cc_a2_reg;
1559             break;
1560         case jit_code_boaddr:   case jit_code_boaddr_u: case jit_code_bxaddr:
1561         case jit_code_bxaddr_u: case jit_code_bosubr:   case jit_code_bosubr_u:
1562         case jit_code_bxsubr:   case jit_code_bxsubr_u:
1563             mask = jit_cc_a0_jmp|jit_cc_a1_reg|jit_cc_a1_chg|jit_cc_a2_reg;
1564             break;
1565         case jit_code_movnr:    case jit_code_movzr:
1566             mask = jit_cc_a0_reg|jit_cc_a0_cnd|jit_cc_a1_reg|jit_cc_a2_reg;
1567             break;
1568         case jit_code_casr:
1569             mask = jit_cc_a0_reg|jit_cc_a0_chg|jit_cc_a1_reg|
1570                    jit_cc_a2_reg|jit_cc_a2_rlh;
1571             break;
1572         case jit_code_casi:
1573             mask = jit_cc_a0_reg|jit_cc_a0_chg|jit_cc_a1_int|
1574                    jit_cc_a2_reg|jit_cc_a2_rlh;
1575             break;
1576         default:
1577             abort();
1578     }
1579
1580     return (mask);
1581 }
1582
1583 void
1584 _jit_patch_abs(jit_state_t *_jit, jit_node_t *instr, jit_pointer_t address)
1585 {
1586     jit_int32_t         mask;
1587
1588     switch (instr->code) {
1589         case jit_code_movi:     case jit_code_ldi_c:    case jit_code_ldi_uc:
1590         case jit_code_ldi_s:    case jit_code_ldi_us:   case jit_code_ldi_i:
1591         case jit_code_ldi_ui:   case jit_code_ldi_l:    case jit_code_ldi_f:
1592         case jit_code_ldi_d:
1593             instr->v.p = address;
1594             break;
1595         case jit_code_sti_c:    case jit_code_sti_s:    case jit_code_sti_i:
1596         case jit_code_sti_l:    case jit_code_sti_f:    case jit_code_sti_d:
1597             instr->u.p = address;
1598             break;
1599         default:
1600             mask = jit_classify(instr->code);
1601             assert((mask & (jit_cc_a0_reg|jit_cc_a0_jmp)) == jit_cc_a0_jmp);
1602             instr->u.p = address;
1603     }
1604 }
1605
1606 void
1607 _jit_patch_at(jit_state_t *_jit, jit_node_t *instr, jit_node_t *label)
1608 {
1609     jit_int32_t         mask;
1610
1611     assert(!(instr->flag & jit_flag_node));
1612     instr->flag |= jit_flag_node;
1613     switch (instr->code) {
1614         case jit_code_movi:
1615             assert(label->code == jit_code_label ||
1616                    label->code == jit_code_data);
1617             instr->v.n = label;
1618             if (label->code == jit_code_data)
1619                 instr->flag |= jit_flag_data;
1620             break;
1621         case jit_code_jmpi:
1622             assert(label->code == jit_code_label ||
1623                    label->code == jit_code_epilog);
1624             instr->u.n = label;
1625             break;
1626         default:
1627             mask = jit_classify(instr->code);
1628             assert((mask & (jit_cc_a0_reg|jit_cc_a0_jmp)) == jit_cc_a0_jmp);
1629             assert(label->code == jit_code_label);
1630             instr->u.n = label;
1631             break;
1632     }
1633     /* link field is used as list of nodes associated with a given label */
1634     instr->link = label->link;
1635     label->link = instr;
1636 }
1637
1638 static void
1639 _do_setup(jit_state_t *_jit)
1640 {
1641     jit_block_t         *block;
1642     jit_word_t           offset;
1643
1644     /* create initial mapping of live register values
1645      * at the start of a basic block */
1646     for (offset = 0; offset < _jitc->blocks.offset; offset++) {
1647         block = _jitc->blocks.ptr + offset;
1648         if (!block->label || block->label->code == jit_code_epilog)
1649             continue;
1650         jit_setup(block);
1651     }
1652 }
1653
1654 static jit_bool_t
1655 _block_update_set(jit_state_t *_jit,
1656                   jit_block_t *block, jit_block_t *target)
1657 {
1658     jit_regset_t        regmask;
1659
1660     jit_regset_ior(&regmask, &block->reglive, &target->reglive);
1661     jit_regset_and(&regmask,  &regmask, &block->regmask);
1662     if (jit_regset_set_p(&regmask)) {
1663         jit_regset_ior(&block->reglive, &block->reglive, &regmask);
1664         jit_regset_and(&regmask, &block->reglive, &block->regmask);
1665         jit_regset_com(&regmask, &regmask);
1666         jit_regset_and(&block->regmask, &block->regmask, &regmask);
1667         block->again = 1;
1668         return (1);
1669     }
1670     return (0);
1671 }
1672
1673 static jit_bool_t
1674 _check_block_again(jit_state_t *_jit)
1675 {
1676     jit_int32_t          todo;
1677     jit_word_t           offset;
1678     jit_node_t          *node, *label;
1679     jit_block_t         *block, *target;
1680
1681     todo = 0;
1682     for (offset = 0; offset < _jitc->blocks.offset; offset++) {
1683         block = _jitc->blocks.ptr + offset;
1684         if (block->again) {
1685             todo = 1;
1686             break;
1687         }
1688     }
1689     /* If no block changed state */
1690     if (!todo)
1691         return (0);
1692
1693     do {
1694         todo = 0;
1695         block = NULL;
1696         for (node = _jitc->head; node; node = node->next) {
1697             /* Special jumps that match jit_cc_a0_jmp */
1698             if (node->code == jit_code_calli || node->code == jit_code_callr)
1699                 continue;
1700
1701             /* Remember current label */
1702             if (node->code == jit_code_label ||
1703                 node->code == jit_code_prolog ||
1704                 node->code == jit_code_epilog) {
1705
1706                 /* If previous block does not pass through */
1707                 if (!(node->flag & jit_flag_head))
1708                     block = NULL;
1709
1710                 target = _jitc->blocks.ptr + node->v.w;
1711                 /* Update if previous block pass through */
1712                 if (block && block->again && block_update_set(target, block))
1713                     todo = 1;
1714                 block = target;
1715                 if (!block->again)
1716                     continue;
1717             }
1718             /* If not the first jmpi */
1719             else if (block) {
1720                 /* If a jump to dynamic address or if a jump to raw address */
1721                 if (!(jit_classify(node->code) & jit_cc_a0_jmp) ||
1722                     !(node->flag & jit_flag_node))
1723                     continue;
1724                 label = node->u.n;
1725                 /* Mark predecessor needs updating due to target change */
1726                 target = _jitc->blocks.ptr + label->v.w;
1727                 if (target->again && block_update_set(block, target))
1728                     todo = 1;
1729             }
1730         }
1731     }
1732     while (todo);
1733
1734     return (1);
1735 }
1736
1737 static void
1738 _do_follow(jit_state_t *_jit, jit_bool_t always)
1739 {
1740     jit_block_t         *block;
1741     jit_word_t           offset;
1742
1743     /* set live state of registers not referenced in a block, but
1744      * referenced in a jump target or normal flow */
1745     for (offset = 0; offset < _jitc->blocks.offset; offset++) {
1746         block = _jitc->blocks.ptr + offset;
1747         if (!block->label || block->label->code == jit_code_epilog)
1748             continue;
1749         if (always || block->again) {
1750             block->again = 0;
1751             jit_follow(block);
1752         }
1753     }
1754 }
1755
1756 void
1757 _jit_optimize(jit_state_t *_jit)
1758 {
1759     jit_bool_t           jump;
1760     jit_bool_t           todo;
1761     jit_int32_t          mask;
1762     jit_node_t          *node;
1763     jit_block_t         *block;
1764     jit_word_t           offset;
1765
1766     todo = 0;
1767     _jitc->function = NULL;
1768
1769     thread_jumps();
1770     sequential_labels();
1771     split_branches();
1772     do_setup();
1773     do_follow(1);
1774
1775     patch_registers();
1776     if (simplify())
1777         todo = 1;
1778
1779     /* Figure out labels that are only reached with a jump
1780      * and is required to do a simple redundant_store removal
1781      * on jit_beqi below */
1782     jump = 1;
1783     for (node = _jitc->head; node; node = node->next) {
1784         switch (node->code) {
1785             case jit_code_label:
1786                 if (!jump)
1787                     node->flag |= jit_flag_head;
1788                 break;
1789             case jit_code_jmpi:         case jit_code_jmpr:
1790             case jit_code_epilog:
1791                 jump = 1;
1792                 break;
1793             case jit_code_data:         case jit_code_note:
1794                 break;
1795             default:
1796                 jump = 0;
1797                 break;
1798         }
1799     }
1800
1801     for (node = _jitc->head; node; node = node->next) {
1802         mask = jit_classify(node->code);
1803         if (mask & jit_cc_a0_reg)
1804             node->u.w &= ~jit_regno_patch;
1805         if (mask & jit_cc_a1_reg)
1806             node->v.w &= ~jit_regno_patch;
1807         if (mask & jit_cc_a2_reg)
1808             node->w.w &= ~jit_regno_patch;
1809         if (node->code == jit_code_beqi) {
1810             if (redundant_store(node, 1)) {
1811                 block = _jitc->blocks.ptr + ((jit_node_t *)node->u.n)->v.w;
1812                 block->again = 1;
1813                 todo = 1;
1814             }
1815         }
1816         else if (node->code == jit_code_bnei) {
1817             if (redundant_store(node, 0)) {
1818                 block = _jitc->blocks.ptr + ((jit_node_t *)node->u.n)->v.w;
1819                 block->again = 1;
1820                 todo = 1;
1821             }
1822         }
1823     }
1824
1825     if (!todo)
1826         todo = check_block_again();
1827
1828     /* If instructions were removed or first pass did modify the entry
1829      * state of any block */
1830     if (todo) {
1831         do_setup();
1832         todo = 0;
1833         do {
1834             do_follow(0);
1835             /* If any block again has the entry state modified. */
1836             todo = check_block_again();
1837         } while (todo);
1838     }
1839
1840     for (node = _jitc->head; node; node = node->next) {
1841         mask = jit_classify(node->code);
1842         if (mask & jit_cc_a0_reg)
1843             node->u.w &= ~jit_regno_patch;
1844         if (mask & jit_cc_a1_reg)
1845             node->v.w &= ~jit_regno_patch;
1846         if (mask & jit_cc_a2_reg)
1847             node->w.w &= ~jit_regno_patch;
1848         if  (node->code == jit_code_prolog)
1849             _jitc->function = _jitc->functions.ptr + node->w.w;
1850         else if(node->code == jit_code_epilog)
1851             _jitc->function = NULL;
1852         else {
1853 #if JIT_HASH_CONSTS
1854             if (mask & jit_cc_a0_flt) {
1855                 node->u.p = jit_data(&node->u.f, sizeof(jit_float32_t), 4);
1856                 node->flag |= jit_flag_node | jit_flag_data;
1857             }
1858             else if (mask & jit_cc_a0_dbl) {
1859                 node->u.p = jit_data(&node->u.d, sizeof(jit_float64_t), 8);
1860                 node->flag |= jit_flag_node | jit_flag_data;
1861             }
1862             else if (mask & jit_cc_a1_flt) {
1863                 node->v.p = jit_data(&node->v.f, sizeof(jit_float32_t), 4);
1864                 node->flag |= jit_flag_node | jit_flag_data;
1865             }
1866             else if (mask & jit_cc_a1_dbl) {
1867                 node->v.p = jit_data(&node->v.d, sizeof(jit_float64_t), 8);
1868                 node->flag |= jit_flag_node | jit_flag_data;
1869             }
1870             else if (mask & jit_cc_a2_flt) {
1871                 node->w.p = jit_data(&node->w.f, sizeof(jit_float32_t), 4);
1872                 node->flag |= jit_flag_node | jit_flag_data;
1873             }
1874             else if (mask & jit_cc_a2_dbl) {
1875                 node->w.p = jit_data(&node->w.d, sizeof(jit_float64_t), 8);
1876                 node->flag |= jit_flag_node | jit_flag_data;
1877             }
1878 #endif
1879             if (_jitc->function) {
1880                 if ((mask & (jit_cc_a0_reg|jit_cc_a0_chg)) ==
1881                     (jit_cc_a0_reg|jit_cc_a0_chg)) {
1882                     if (mask & jit_cc_a0_rlh) {
1883                         jit_regset_setbit(&_jitc->function->regset,
1884                                           jit_regno(node->u.q.l));
1885                         jit_regset_setbit(&_jitc->function->regset,
1886                                           jit_regno(node->u.q.h));
1887                     }
1888                     else
1889                         jit_regset_setbit(&_jitc->function->regset,
1890                                           jit_regno(node->u.w));
1891                 }
1892                 if ((mask & (jit_cc_a1_reg|jit_cc_a1_chg)) ==
1893                     (jit_cc_a1_reg|jit_cc_a1_chg))
1894                     jit_regset_setbit(&_jitc->function->regset,
1895                                       jit_regno(node->v.w));
1896                 if ((mask & (jit_cc_a2_reg|jit_cc_a2_chg)) ==
1897                     (jit_cc_a2_reg|jit_cc_a2_chg))
1898                     jit_regset_setbit(&_jitc->function->regset,
1899                                       jit_regno(node->w.w));
1900             }
1901         }
1902     }
1903 }
1904
1905 void
1906 _jit_reglive(jit_state_t *_jit, jit_node_t *node)
1907 {
1908     jit_int32_t          spec;
1909     jit_int32_t          value;
1910     jit_block_t         *block;
1911
1912     switch (node->code) {
1913         case jit_code_label:    case jit_code_prolog:   case jit_code_epilog:
1914             block = _jitc->blocks.ptr + node->v.w;
1915             jit_regset_set(&_jitc->reglive, &block->reglive);
1916             break;
1917         case jit_code_callr:
1918             value = jit_regno(node->u.w);
1919             if (!(node->u.w & jit_regno_patch)) {
1920                 jit_regset_setbit(&_jitc->reglive, value);
1921             }
1922         case jit_code_calli:
1923             for (value = 0; value < _jitc->reglen; value++) {
1924                 spec = jit_class(_rvs[value].spec);
1925                 if ((spec & jit_class_arg) && jit_regarg_p(node, value))
1926                     jit_regset_setbit(&_jitc->reglive, value);
1927                 else if (!(spec & jit_class_sav))
1928                     jit_regset_clrbit(&_jitc->reglive, value);
1929             }
1930             break;
1931         default:
1932             value = jit_classify(node->code);
1933             if (value & jit_cc_a0_reg) {
1934                 if (value & jit_cc_a0_rlh) {
1935                     if (!(node->u.q.l & jit_regno_patch)) {
1936                         if (value & jit_cc_a0_chg) {
1937                             jit_regset_clrbit(&_jitc->reglive, node->u.q.l);
1938                             jit_regset_setbit(&_jitc->regmask, node->u.q.l);
1939                         }
1940                         else
1941                             jit_regset_setbit(&_jitc->reglive, node->u.q.l);
1942                     }
1943                     if (!(node->u.q.h & jit_regno_patch)) {
1944                         if (value & jit_cc_a0_chg) {
1945                             jit_regset_clrbit(&_jitc->reglive, node->u.q.h);
1946                             jit_regset_setbit(&_jitc->regmask, node->u.q.h);
1947                         }
1948                         else
1949                             jit_regset_setbit(&_jitc->reglive, node->u.q.h);
1950                     }
1951                 }
1952                 else {
1953                     if (!(node->u.w & jit_regno_patch)) {
1954                         if (value & jit_cc_a0_chg) {
1955                             jit_regset_clrbit(&_jitc->reglive, node->u.w);
1956                             jit_regset_setbit(&_jitc->regmask, node->u.w);
1957                         }
1958                         else
1959                             jit_regset_setbit(&_jitc->reglive, node->u.w);
1960                     }
1961                 }
1962             }
1963             if ((value & jit_cc_a1_reg) && !(node->v.w & jit_regno_patch)) {
1964                 if (value & jit_cc_a1_chg) {
1965                     jit_regset_clrbit(&_jitc->reglive, node->v.w);
1966                     jit_regset_setbit(&_jitc->regmask, node->v.w);
1967                 }
1968                 else
1969                     jit_regset_setbit(&_jitc->reglive, node->v.w);
1970             }
1971             if (value & jit_cc_a2_reg) {
1972                 if (value & jit_cc_a2_rlh) {
1973                     /* Assume registers are not changed */
1974                     if (!(node->w.q.l & jit_regno_patch))
1975                         jit_regset_setbit(&_jitc->reglive, node->w.q.l);
1976                     if (!(node->w.q.h & jit_regno_patch))
1977                         jit_regset_setbit(&_jitc->reglive, node->w.q.h);
1978                 }
1979                 else {
1980                     if (!(node->w.w & jit_regno_patch)) {
1981                         if (value & jit_cc_a2_chg) {
1982                             jit_regset_clrbit(&_jitc->reglive, node->w.w);
1983                             jit_regset_setbit(&_jitc->regmask, node->w.w);
1984                         }
1985                         else
1986                             jit_regset_setbit(&_jitc->reglive, node->w.w);
1987                     }
1988                 }
1989             }
1990             if (jit_regset_set_p(&_jitc->regmask)) {
1991                 jit_update(node->next, &_jitc->reglive, &_jitc->regmask);
1992                 if (jit_regset_set_p(&_jitc->regmask)) {
1993                     /* any unresolved live state is considered as live */
1994                     jit_regset_ior(&_jitc->reglive,
1995                                    &_jitc->reglive, &_jitc->regmask);
1996                     jit_regset_set_ui(&_jitc->regmask, 0);
1997                 }
1998             }
1999             break;
2000     }
2001 }
2002
2003 void
2004 _jit_regarg_set(jit_state_t *_jit, jit_node_t *node, jit_int32_t value)
2005 {
2006 #if GET_JIT_SIZE
2007     jit_size_prepare();
2008 #endif
2009     if (value & jit_cc_a0_reg) {
2010         if (value & jit_cc_a0_rlh) {
2011             jit_regset_setbit(&_jitc->regarg, jit_regno(node->u.q.l));
2012             jit_regset_setbit(&_jitc->regarg, jit_regno(node->u.q.h));
2013         }
2014         else
2015             jit_regset_setbit(&_jitc->regarg, jit_regno(node->u.w));
2016     }
2017     if (value & jit_cc_a1_reg)
2018         jit_regset_setbit(&_jitc->regarg, jit_regno(node->v.w));
2019     if (value & jit_cc_a2_reg) {
2020         if (value & jit_cc_a2_rlh) {
2021             jit_regset_setbit(&_jitc->regarg, jit_regno(node->w.q.l));
2022             jit_regset_setbit(&_jitc->regarg, jit_regno(node->w.q.h));
2023         }
2024         else
2025             jit_regset_setbit(&_jitc->regarg, jit_regno(node->w.w));
2026     }
2027 }
2028
2029 void
2030 _jit_regarg_clr(jit_state_t *_jit, jit_node_t *node, jit_int32_t value)
2031 {
2032 #if GET_JIT_SIZE
2033     jit_size_collect(node);
2034 #endif
2035     if (value & jit_cc_a0_reg) {
2036         if (value & jit_cc_a0_rlh) {
2037             jit_regset_clrbit(&_jitc->regarg, jit_regno(node->u.q.l));
2038             jit_regset_clrbit(&_jitc->regarg, jit_regno(node->u.q.h));
2039         }
2040         else
2041             jit_regset_clrbit(&_jitc->regarg, jit_regno(node->u.w));
2042     }
2043     if (value & jit_cc_a1_reg)
2044         jit_regset_clrbit(&_jitc->regarg, jit_regno(node->v.w));
2045     if (value & jit_cc_a2_reg) {
2046         if (value & jit_cc_a2_rlh) {
2047             jit_regset_clrbit(&_jitc->regarg, jit_regno(node->w.q.l));
2048             jit_regset_clrbit(&_jitc->regarg, jit_regno(node->w.q.h));
2049         }
2050         else
2051             jit_regset_clrbit(&_jitc->regarg, jit_regno(node->w.w));
2052     }
2053 }
2054
2055 void
2056 _jit_realize(jit_state_t *_jit)
2057 {
2058     assert(!_jitc->realize);
2059     if (_jitc->function)
2060         jit_epilog();
2061     jit_optimize();
2062     _jitc->realize = 1;
2063
2064     /* ensure it is aligned */
2065     _jitc->data.offset = (_jitc->data.offset + 7) & -8;
2066
2067 #if GET_JIT_SIZE
2068     /* Heuristic to guess code buffer size */
2069     _jitc->mult = 4;
2070     _jit->code.length = _jitc->pool.length * 1024 * _jitc->mult;
2071 #else
2072     _jit->code.length = jit_get_size();
2073 #endif
2074 }
2075
2076 void
2077 _jit_dataset(jit_state_t *_jit)
2078 {
2079     jit_uint8_t         *ptr;
2080     jit_node_t          *node;
2081     jit_word_t           offset;
2082 #if defined(__sgi)
2083     int                  mmap_fd;
2084 #endif
2085
2086     assert(!_jitc->dataset);
2087 #if !HAVE_MMAP
2088     assert(_jit->user_data);
2089 #else
2090     if (!_jit->user_data) {
2091
2092         /* create read only data buffer */
2093         _jit->data.length = (_jitc->data.offset +
2094                              /* reserve space for annotations */
2095                              _jitc->note.size + 4095) & -4096;
2096 #if defined(__sgi)
2097         mmap_fd = open("/dev/zero", O_RDWR);
2098 #endif
2099         _jit->data.ptr = mmap(NULL, _jit->data.length,
2100                               PROT_READ | PROT_WRITE,
2101                               MAP_PRIVATE | MAP_ANON, mmap_fd, 0);
2102         assert(_jit->data.ptr != MAP_FAILED);
2103 #if defined(__sgi)
2104         close(mmap_fd);
2105 #endif
2106     }
2107 #endif /* !HAVE_MMAP */
2108
2109     if (!_jitc->no_data)
2110         jit_memcpy(_jit->data.ptr, _jitc->data.ptr, _jitc->data.offset);
2111
2112     if (_jitc->no_note) {
2113         /* Space for one note is always allocated, so revert it here
2114          * if after jit_new_state was called, it is also requested to
2115          * not generate annotation information */
2116         _jit->note.length = 0;
2117         _jitc->note.size = 0;
2118     }
2119     else {
2120         _jitc->note.base = _jit->data.ptr;
2121         if (!_jitc->no_data)
2122             _jitc->note.base += _jitc->data.offset;
2123         memset(_jitc->note.base, 0, _jitc->note.size);
2124     }
2125
2126     if (_jit->user_data)
2127         /* Need the temporary hashed data until jit_emit is finished */
2128         ptr = _jitc->no_data ? _jitc->data.ptr : _jit->data.ptr;
2129     else {
2130         ptr = _jit->data.ptr;
2131         /* Temporary hashed data no longer required */
2132         jit_free((jit_pointer_t *)&_jitc->data.ptr);
2133     }
2134
2135     for (offset = 0; offset < _jitc->data.size; offset++) {
2136         for (node = _jitc->data.table[offset]; node; node = node->next) {
2137             node->flag |= jit_flag_patch;
2138             node->u.w = (jit_word_t)(ptr + node->u.w);
2139         }
2140     }
2141
2142     _jitc->dataset = 1;
2143 }
2144
2145 jit_pointer_t
2146 _jit_get_code(jit_state_t *_jit, jit_word_t *length)
2147 {
2148     assert(_jitc->realize);
2149     if (length) {
2150         if (_jitc->done)
2151             /* If code already generated, return exact size of code */
2152             *length = _jit->pc.uc - _jit->code.ptr;
2153         else
2154             /* Else return current size of the code buffer */
2155             *length = _jit->code.length;
2156     }
2157
2158     return (_jit->code.ptr);
2159 }
2160
2161 void
2162 _jit_set_code(jit_state_t *_jit, jit_pointer_t ptr, jit_word_t length)
2163 {
2164     assert(_jitc->realize);
2165     _jit->code.ptr = ptr;
2166     _jit->code.length = length;
2167     _jit->user_code = 1;
2168 }
2169
2170 jit_pointer_t
2171 _jit_get_data(jit_state_t *_jit, jit_word_t *data_size, jit_word_t *note_size)
2172 {
2173     assert(_jitc->realize);
2174     if (data_size)
2175         *data_size = _jitc->data.offset;
2176     if (note_size)
2177         *note_size = _jitc->note.size;
2178     return (_jit->data.ptr);
2179 }
2180
2181 void
2182 _jit_set_data(jit_state_t *_jit, jit_pointer_t ptr,
2183               jit_word_t length, jit_word_t flags)
2184 {
2185     assert(_jitc->realize);
2186     if (flags & JIT_DISABLE_DATA)
2187         _jitc->no_data = 1;
2188     else
2189         assert(length >= _jitc->data.offset);
2190     if (flags & JIT_DISABLE_NOTE)
2191         _jitc->no_note = 1;
2192     else {
2193         if (flags & JIT_DISABLE_DATA)
2194             assert(length >= _jitc->note.size);
2195         else
2196             assert(length >= _jitc->data.offset + _jitc->note.size);
2197     }
2198     _jit->data.ptr = ptr;
2199     _jit->data.length = length;
2200     _jit->user_data = 1;
2201 }
2202
2203 jit_pointer_t
2204 _jit_emit(jit_state_t *_jit)
2205 {
2206     jit_pointer_t        code;
2207     jit_node_t          *node;
2208     size_t               length;
2209     int                  result;
2210 #if defined(__sgi)
2211     int                  mmap_fd;
2212 #endif
2213     int                  mmap_prot, mmap_flags;
2214
2215     if (!_jitc->realize)
2216         jit_realize();
2217
2218     if (!_jitc->dataset)
2219         jit_dataset();
2220
2221     _jitc->emit = 1;
2222
2223 #if !HAVE_MMAP
2224     assert(_jit->user_code);
2225 #else
2226     if (!_jit->user_code) {
2227         mmap_prot = PROT_READ | PROT_WRITE;
2228 #if !__OpenBSD__
2229         mmap_prot |= PROT_EXEC;
2230 #endif
2231 #if __NetBSD__
2232         mmap_prot = PROT_MPROTECT(mmap_prot);
2233         mmap_flags = 0;
2234 #else
2235         mmap_flags = MAP_PRIVATE;
2236 #endif
2237         mmap_flags |= MAP_ANON;
2238 #if defined(__sgi)
2239         mmap_fd = open("/dev/zero", O_RDWR);
2240 #endif
2241         _jit->code.ptr = mmap(NULL, _jit->code.length,
2242                               mmap_prot, mmap_flags, mmap_fd, 0);
2243         assert(_jit->code.ptr != MAP_FAILED);
2244     }
2245 #endif /* !HAVE_MMAP */
2246     _jitc->code.end = _jit->code.ptr + _jit->code.length -
2247         jit_get_max_instr();
2248     _jit->pc.uc = _jit->code.ptr;
2249
2250     for (;;) {
2251 #if __NetBSD__
2252         result = mprotect(_jit->code.ptr, _jit->code.length,
2253                           PROT_READ | PROT_WRITE);
2254         assert(result == 0);
2255 #endif
2256         if ((code = emit_code()) == NULL) {
2257             _jitc->patches.offset = 0;
2258             for (node = _jitc->head; node; node = node->next) {
2259                 if (node->link &&
2260                     (node->code == jit_code_label ||
2261                      node->code == jit_code_epilog))
2262                     node->flag &= ~jit_flag_patch;
2263             }
2264 #if !HAVE_MMAP
2265             assert(_jit->user_code);
2266 #else
2267             if (_jit->user_code)
2268                 goto fail;
2269 #if GET_JIT_SIZE
2270             ++_jitc->mult;
2271             length = _jitc->pool.length * 1024 * _jitc->mult;
2272 #else
2273             /* Should only happen on very special cases */
2274             length = _jit->code.length + 4096;
2275 #endif
2276
2277 #if !HAVE_MREMAP
2278             munmap(_jit->code.ptr, _jit->code.length);
2279 #endif
2280
2281 #if HAVE_MREMAP
2282 #  if __NetBSD__
2283             _jit->code.ptr = mremap(_jit->code.ptr, _jit->code.length,
2284                                     _jit->code.ptr, length, 0);
2285 #  else
2286             _jit->code.ptr = mremap(_jit->code.ptr, _jit->code.length,
2287                                     length, MREMAP_MAYMOVE, NULL);
2288 #  endif
2289 #else
2290             _jit->code.ptr = mmap(NULL, length,
2291                                   PROT_EXEC | PROT_READ | PROT_WRITE,
2292                                   MAP_PRIVATE | MAP_ANON, mmap_fd, 0);
2293 #endif
2294
2295             assert(_jit->code.ptr != MAP_FAILED);
2296             _jit->code.length = length;
2297             _jitc->code.end = _jit->code.ptr + _jit->code.length -
2298                 jit_get_max_instr();
2299             _jit->pc.uc = _jit->code.ptr;
2300 #endif /* !HAVE_MMAP */
2301         }
2302         else
2303             break;
2304     }
2305
2306 #if defined(__sgi)
2307     if (!_jit->user_code)
2308         close(mmap_fd);
2309 #endif
2310
2311     _jitc->done = 1;
2312     if (!_jitc->no_note)
2313         jit_annotate();
2314
2315     if (_jit->user_data)
2316         jit_free((jit_pointer_t *)&_jitc->data.ptr);
2317 #if HAVE_MMAP
2318     else {
2319         result = mprotect(_jit->data.ptr,
2320                           _jit->data.length, PROT_READ);
2321         assert(result == 0);
2322     }
2323     if (!_jit->user_code) {
2324         length = _jit->pc.uc - _jit->code.ptr;
2325 #  if __riscv && __WORDSIZE == 64
2326         /* FIXME should start adding consts at a page boundary */
2327         length -= _jitc->consts.hash.count * sizeof(jit_word_t);
2328 #  endif
2329         result = mprotect(_jit->code.ptr, length, PROT_READ | PROT_EXEC);
2330         assert(result == 0);
2331     }
2332 #endif /* HAVE_MMAP */
2333
2334     return (_jit->code.ptr);
2335 fail:
2336     return (NULL);
2337 }
2338
2339 void
2340 _jit_frame(jit_state_t *_jit, jit_int32_t frame)
2341 {
2342     jit_trampoline(frame, 1);
2343 }
2344
2345 void
2346 _jit_tramp(jit_state_t *_jit, jit_int32_t frame)
2347 {
2348     jit_trampoline(frame, 0);
2349 }
2350
2351 void
2352 _jit_trampoline(jit_state_t *_jit, jit_int32_t frame, jit_bool_t prolog)
2353 {
2354     jit_int32_t         regno;
2355
2356     /* Must be called after prolog, actually, just to simplify
2357      * tests and know there is a current function and that
2358      * _jitc->function->self.aoff is at the before any alloca value */
2359     assert(_jitc->tail && _jitc->tail->code == jit_code_prolog);
2360
2361     /* + 24 for 3 possible spilled temporaries (that could be a double) */
2362     frame += 24;
2363 #if defined(__hppa__)
2364     frame += _jitc->function->self.aoff;
2365 #else
2366     frame -= _jitc->function->self.aoff;
2367 #endif
2368     _jitc->function->frame = frame;
2369     if (prolog)
2370         _jitc->function->define_frame = 1;
2371     else
2372         _jitc->function->assume_frame = 1;
2373     for (regno = 0; regno < _jitc->reglen; regno++)
2374         if (jit_class(_rvs[regno].spec) & jit_class_sav)
2375             jit_regset_setbit(&_jitc->function->regset, regno);
2376 }
2377
2378 /*   Compute initial reglive and regmask set values of a basic block.
2379  * reglive is the set of known live registers
2380  * regmask is the set of registers not referenced in the block
2381  *   Registers in regmask might be live.
2382  */
2383 static void
2384 _jit_setup(jit_state_t *_jit, jit_block_t *block)
2385 {
2386     jit_node_t          *node;
2387     jit_bool_t           live;
2388     unsigned long        value;
2389
2390     jit_regset_set_mask(&block->regmask, _jitc->reglen);
2391     for (value = 0; value < _jitc->reglen; ++value)
2392         if (!(jit_class(_rvs[value].spec) & (jit_class_gpr|jit_class_fpr)))
2393             jit_regset_clrbit(&block->regmask, value);
2394
2395     for (node = block->label->next; node; node = node->next) {
2396         switch (node->code) {
2397             case jit_code_label:        case jit_code_prolog:
2398             case jit_code_epilog:
2399                 return;
2400             default:
2401                 /* Check argument registers in reverse order to properly
2402                  * handle registers that are both, argument and result */
2403                 value = jit_classify(node->code);
2404                 if ((value & jit_cc_a2_reg) &&
2405                     !(node->w.w & jit_regno_patch) &&
2406                     jit_regset_tstbit(&block->regmask, node->w.w)) {
2407                     live = !(value & jit_cc_a2_chg);
2408                     jit_regset_clrbit(&block->regmask, node->w.w);
2409                     if (live)
2410                         jit_regset_setbit(&block->reglive, node->w.w);
2411                 }
2412                 if ((value & jit_cc_a1_reg) &&
2413                     !(node->v.w & jit_regno_patch) &&
2414                     jit_regset_tstbit(&block->regmask, node->v.w)) {
2415                     live = !(value & jit_cc_a1_chg);
2416                     jit_regset_clrbit(&block->regmask, node->v.w);
2417                     if (live)
2418                         jit_regset_setbit(&block->reglive, node->v.w);
2419                 }
2420                 if (value & jit_cc_a0_reg) {
2421                     live = !(value & jit_cc_a0_chg);
2422                     if (value & jit_cc_a0_rlh) {
2423                         if (!(node->u.q.l & jit_regno_patch) &&
2424                             jit_regset_tstbit(&block->regmask, node->u.q.l)) {
2425                             jit_regset_clrbit(&block->regmask, node->u.q.l);
2426                             if (live)
2427                                 jit_regset_setbit(&block->reglive, node->u.q.l);
2428                         }
2429                         if (!(node->u.q.h & jit_regno_patch) &&
2430                             jit_regset_tstbit(&block->regmask, node->u.q.h)) {
2431                             jit_regset_clrbit(&block->regmask, node->u.q.h);
2432                             if (live)
2433                                 jit_regset_setbit(&block->reglive, node->u.q.h);
2434                         }
2435                     }
2436                     else {
2437                         if (!(node->u.w & jit_regno_patch) &&
2438                             jit_regset_tstbit(&block->regmask, node->u.w)) {
2439                             jit_regset_clrbit(&block->regmask, node->u.w);
2440                             if (live)
2441                                 jit_regset_setbit(&block->reglive, node->u.w);
2442                         }
2443                     }
2444                 }
2445                 break;
2446         }
2447     }
2448 }
2449
2450 /*  Update regmask and reglive of blocks at entry point of branch targets
2451  * or normal flow that have a live register not used in this block.
2452  */
2453 static void
2454 _jit_follow(jit_state_t *_jit, jit_block_t *block)
2455 {
2456     jit_node_t          *node;
2457     jit_block_t         *next;
2458     jit_int32_t          spec;
2459     jit_int32_t          regno;
2460     unsigned long        value;
2461     jit_node_t          *label;
2462     jit_regset_t         reglive;
2463     jit_regset_t         regmask;
2464     jit_regset_t         regtemp;
2465
2466     jit_regset_set(&reglive, &block->reglive);
2467     jit_regset_set(&regmask, &block->regmask);
2468     for (node = block->label->next; node; node = node->next) {
2469         switch (node->code) {
2470             case jit_code_label:
2471                 /*  Do not consider jmpi and jmpr cannot jump to the
2472                  * next instruction. */
2473                 next = _jitc->blocks.ptr + node->v.w;
2474                 /*  Set of live registers in next block that are at unknown
2475                  * state in this block. */
2476                 jit_regset_and(&regtemp, &regmask, &next->reglive);
2477                 if (jit_regset_set_p(&regtemp)) {
2478                     /*  Add live state of next block to current block. */
2479                     jit_regset_ior(&block->reglive, &block->reglive, &regtemp);
2480                     /*  Remove from unknown state bitmask. */
2481                     jit_regset_com(&regtemp, &regtemp);
2482                     jit_regset_and(&block->regmask, &block->regmask, &regtemp);
2483                     block->again = 1;
2484                 }
2485             case jit_code_prolog:
2486             case jit_code_epilog:
2487                 return;
2488             case jit_code_callr:
2489                 value = jit_regno(node->u.w);
2490                 if (!(node->u.w & jit_regno_patch)) {
2491                     if (jit_regset_tstbit(&regmask, value)) {
2492                         jit_regset_clrbit(&regmask, value);
2493                         jit_regset_setbit(&reglive, value);
2494                     }
2495                 }
2496             case jit_code_calli:
2497                 for (value = 0; value < _jitc->reglen; ++value) {
2498                     value = jit_regset_scan1(&regmask, value);
2499                     if (value >= _jitc->reglen)
2500                         break;
2501                     spec = jit_class(_rvs[value].spec);
2502                     if (!(spec & jit_class_sav))
2503                         jit_regset_clrbit(&regmask, value);
2504                     if ((spec & jit_class_arg) && jit_regarg_p(node, value))
2505                         jit_regset_setbit(&reglive, value);
2506                 }
2507                 break;
2508             default:
2509                 value = jit_classify(node->code);
2510                 if (value & jit_cc_a2_reg) {
2511                     if (value & jit_cc_a2_rlh) {
2512                         if (!(node->w.q.l & jit_regno_patch)) {
2513                             /* Assume register is not changed */
2514                             if (jit_regset_tstbit(&regmask, node->w.q.l))
2515                                 jit_regset_clrbit(&regmask, node->w.q.l);
2516                         }
2517                         if (!(node->w.q.h & jit_regno_patch)) {
2518                             if (jit_regset_tstbit(&regmask, node->w.q.h))
2519                                 jit_regset_clrbit(&regmask, node->w.q.h);
2520                         }
2521                     }
2522                     else {
2523                         if (value & jit_cc_a2_reg) {
2524                             if (!(node->w.w & jit_regno_patch)) {
2525                                 if (jit_regset_tstbit(&regmask, node->w.w)) {
2526                                     jit_regset_clrbit(&regmask, node->w.w);
2527                                     if (!(value & jit_cc_a2_chg))
2528                                         jit_regset_setbit(&reglive, node->w.w);
2529                                 }
2530                             }
2531                         }
2532                     }
2533                 }
2534                 if (value & jit_cc_a1_reg) {
2535                     if (!(node->v.w & jit_regno_patch)) {
2536                         if (jit_regset_tstbit(&regmask, node->v.w)) {
2537                             jit_regset_clrbit(&regmask, node->v.w);
2538                             if (!(value & jit_cc_a1_chg))
2539                                 jit_regset_setbit(&reglive, node->v.w);
2540                         }
2541                     }
2542                 }
2543                 if (value & jit_cc_a0_reg) {
2544                     if (value & jit_cc_a0_rlh) {
2545                         if (!(node->u.q.l & jit_regno_patch)) {
2546                             if (jit_regset_tstbit(&regmask, node->u.q.l)) {
2547                                 jit_regset_clrbit(&regmask, node->u.q.l);
2548                                 if (!(value & jit_cc_a0_chg))
2549                                     jit_regset_setbit(&reglive, node->u.q.l);
2550                             }
2551                         }
2552                         if (!(node->u.q.h & jit_regno_patch)) {
2553                             if (jit_regset_tstbit(&regmask, node->u.q.h)) {
2554                                 jit_regset_clrbit(&regmask, node->u.q.h);
2555                                 if (!(value & jit_cc_a0_chg))
2556                                     jit_regset_setbit(&reglive, node->u.q.h);
2557                             }
2558                         }
2559                     }
2560                     else {
2561                         if (!(node->u.w & jit_regno_patch)) {
2562                             if (jit_regset_tstbit(&regmask, node->u.w)) {
2563                                 jit_regset_clrbit(&regmask, node->u.w);
2564                                 if (!(value & jit_cc_a0_chg))
2565                                     jit_regset_setbit(&reglive, node->u.w);
2566                             }
2567                         }
2568                     }
2569                 }
2570                 if (value & jit_cc_a0_jmp) {
2571                     if (node->flag & jit_flag_node) {
2572                         label = node->u.n;
2573                         /*  Do not consider jmpi and jmpr cannot jump to the
2574                          * next instruction. */
2575                         next = _jitc->blocks.ptr + label->v.w;
2576                         jit_regset_and(&regtemp, &regmask, &next->reglive);
2577                         if (jit_regset_set_p(&regtemp)) {
2578                             /* Add live state. */
2579                             jit_regset_ior(&block->reglive,
2580                                            &block->reglive, &regtemp);
2581                             /*  Remove from unknown state bitmask. */
2582                             jit_regset_com(&regtemp, &regtemp);
2583                             jit_regset_and(&block->regmask,
2584                                            &block->regmask, &regtemp);
2585                             block->again = 1;
2586                         }
2587                     }
2588                     else {
2589                         /*   Jump to unknown location.
2590                          *   This is a pitfall of the implementation.
2591                          *   Only jmpi to not a jit code should reach here,
2592                          * or a jmpr of a computed address.
2593                          *   Because the implementation needs jit_class_nospill
2594                          * registers, must treat jmpr as a function call. This
2595                          * means that only JIT_Vn registers can be trusted on
2596                          * arrival of jmpr.
2597                          */
2598                         jit_regset_set_ui(&regmask, 0);
2599                         for (regno = 0; regno < _jitc->reglen; regno++) {
2600                             spec = jit_class(_rvs[regno].spec);
2601                             if ((spec & (jit_class_gpr|jit_class_fpr)) &&
2602                                 (spec & jit_class_sav))
2603                                 jit_regset_setbit(&regmask, regno);
2604                         }
2605                         /*   Assume non callee save registers are live due
2606                          * to jump to unknown location. */
2607                         /* Treat all callee save as live. */
2608                         jit_regset_ior(&block->reglive, &reglive, &regmask);
2609                         /* Treat anything else as dead. */
2610                         return;
2611                     }
2612                 }
2613                 break;
2614         }
2615     }
2616 }
2617
2618 /*  Follow code generation up to finding a label or end of code.
2619  *  When finding a label, update the set of live registers.
2620  *  On branches, update based on taken branch or normal flow.
2621  */
2622 static void
2623 _jit_update(jit_state_t *_jit, jit_node_t *node,
2624             jit_regset_t *live, jit_regset_t *mask)
2625 {
2626     jit_int32_t          spec;
2627     jit_int32_t          regno;
2628     unsigned long        value;
2629     jit_block_t         *block;
2630     jit_node_t          *label;
2631     jit_regset_t         regtemp;
2632
2633     for (; node; node = node->next) {
2634         if (jit_regset_set_p(mask) == 0)
2635             break;
2636         switch (node->code) {
2637             case jit_code_label:
2638                 block = _jitc->blocks.ptr + node->v.w;
2639                 jit_regset_and(&regtemp, mask, &block->reglive);
2640                 if (jit_regset_set_p(&regtemp)) {
2641                     /* Add live state. */
2642                     jit_regset_ior(live, live, &regtemp);
2643                     /*  Remove from unknown state bitmask. */
2644                     jit_regset_com(&regtemp, &regtemp);
2645                     jit_regset_and(mask, mask, &regtemp);
2646                 }
2647                 return;
2648             case jit_code_prolog:
2649                 jit_regset_set_ui(mask, 0);
2650                 return;
2651             case jit_code_epilog:
2652                 jit_regset_set_ui(mask, 0);
2653                 return;
2654             case jit_code_callr:
2655                 value = jit_regno(node->u.w);
2656                 if (!(node->u.w & jit_regno_patch)) {
2657                     if (jit_regset_tstbit(mask, value)) {
2658                         jit_regset_clrbit(mask, value);
2659                         jit_regset_setbit(live, value);
2660                     }
2661                 }
2662             case jit_code_calli:
2663                 for (value = 0; value < _jitc->reglen; ++value) {
2664                     value = jit_regset_scan1(mask, value);
2665                     if (value >= _jitc->reglen)
2666                         break;
2667                     spec = jit_class(_rvs[value].spec);
2668                     if (!(spec & jit_class_sav))
2669                         jit_regset_clrbit(mask, value);
2670                     if ((spec & jit_class_arg) && jit_regarg_p(node, value))
2671                         jit_regset_setbit(live, value);
2672                 }
2673                 break;
2674             default:
2675                 value = jit_classify(node->code);
2676                 if (value & jit_cc_a2_reg) {
2677                     if (value & jit_cc_a2_rlh) {
2678                         if (!(node->w.q.l & jit_regno_patch)) {
2679                             /* Assume register is not changed */
2680                             if (jit_regset_tstbit(mask, node->w.q.l))
2681                                 jit_regset_clrbit(mask, node->w.q.l);
2682                         }
2683                         if (!(node->w.q.h & jit_regno_patch)) {
2684                             if (jit_regset_tstbit(mask, node->w.q.h))
2685                                 jit_regset_clrbit(mask, node->w.q.h);
2686                         }
2687                     }
2688                     else {
2689                         if (!(node->w.w & jit_regno_patch)) {
2690                             if (jit_regset_tstbit(mask, node->w.w)) {
2691                                 jit_regset_clrbit(mask, node->w.w);
2692                                 if (!(value & jit_cc_a2_chg))
2693                                     jit_regset_setbit(live, node->w.w);
2694                             }
2695                         }
2696                     }
2697                 }
2698                 if (value & jit_cc_a1_reg) {
2699                     if (!(node->v.w & jit_regno_patch)) {
2700                         if (jit_regset_tstbit(mask, node->v.w)) {
2701                             jit_regset_clrbit(mask, node->v.w);
2702                             if (!(value & jit_cc_a1_chg))
2703                                 jit_regset_setbit(live, node->v.w);
2704                         }
2705                     }
2706                 }
2707                 if (value & jit_cc_a0_reg) {
2708                     if (value & jit_cc_a0_rlh) {
2709                         if (!(node->u.q.l & jit_regno_patch)) {
2710                             if (jit_regset_tstbit(mask, node->u.q.l)) {
2711                                 jit_regset_clrbit(mask, node->u.q.l);
2712                                 if (!(value & jit_cc_a0_chg))
2713                                     jit_regset_setbit(live, node->u.q.l);
2714                             }
2715                         }
2716                         if (!(node->u.q.h & jit_regno_patch)) {
2717                             if (jit_regset_tstbit(mask, node->u.q.h)) {
2718                                 jit_regset_clrbit(mask, node->u.q.h);
2719                                 if (!(value & jit_cc_a0_chg))
2720                                     jit_regset_setbit(live, node->u.q.h);
2721                             }
2722                         }
2723                     }
2724                     else {
2725                         if (!(node->u.w & jit_regno_patch)) {
2726                             if (jit_regset_tstbit(mask, node->u.w)) {
2727                                 jit_regset_clrbit(mask, node->u.w);
2728                                 if (!(value & jit_cc_a0_chg))
2729                                     jit_regset_setbit(live, node->u.w);
2730                             }
2731                         }
2732                     }
2733                 }
2734                 if (value & jit_cc_a0_jmp) {
2735                     if (node->flag & jit_flag_node) {
2736                         label = node->u.n;
2737                         /*  Do not consider jmpi and jmpr cannot jump to the
2738                          * next instruction. */
2739                         block = _jitc->blocks.ptr + label->v.w;
2740                         jit_regset_and(&regtemp, mask, &block->reglive);
2741                         if (jit_regset_set_p(&regtemp)) {
2742                             /* Add live state. */
2743                             jit_regset_ior(live, live, &regtemp);
2744                             /*  Remove from unknown state bitmask. */
2745                             jit_regset_com(&regtemp, &regtemp);
2746                             jit_regset_and(mask, mask, &regtemp);
2747                         }
2748                     }
2749                     else {
2750                         /*   Jump to unknown location.
2751                          *   This is a pitfall of the implementation.
2752                          *   Only jmpi to not a jit code should reach here,
2753                          * or a jmpr of a computed address.
2754                          *   Because the implementation needs jit_class_nospill
2755                          * registers, must treat jmpr as a function call. This
2756                          * means that only JIT_Vn registers can be trusted on
2757                          * arrival of jmpr.
2758                          */
2759                         jit_regset_set_ui(mask, 0);
2760                         for (regno = 0; regno < _jitc->reglen; regno++) {
2761                             spec = jit_class(_rvs[regno].spec);
2762                             if ((spec & (jit_class_gpr|jit_class_fpr)) &&
2763                                 (spec & jit_class_sav))
2764                                 jit_regset_setbit(mask, regno);
2765                         }
2766                         /*   Assume non callee save registers are live due
2767                          * to jump to unknown location. */
2768                         /* Treat all callee save as live. */
2769                         jit_regset_ior(live, live, mask);
2770                         /* Treat anything else as dead. */
2771                         return;
2772                     }
2773                 }
2774                 break;
2775         }
2776     }
2777 }
2778
2779 static void
2780 _thread_jumps(jit_state_t *_jit)
2781 {
2782     jit_node_t          *prev;
2783     jit_node_t          *node;
2784     jit_node_t          *next;
2785     jit_int32_t          mask;
2786
2787     for (prev = node = _jitc->head; node;) {
2788         next = node->next;
2789         switch (node->code) {
2790             case jit_code_jmpi:
2791                 if (redundant_jump(prev, node)) {
2792                     node = prev;
2793                     continue;
2794                 }
2795                 if (shortcut_jump(prev, node))
2796                     continue;
2797                 break;
2798             case jit_code_jmpr:
2799             case jit_code_callr:        case jit_code_calli:
2800                 /* non optimizable jump like code */
2801                 break;
2802             default:
2803                 mask = jit_classify(node->code);
2804                 if (mask & jit_cc_a0_jmp) {
2805                     if (reverse_jump(prev, node) ||
2806                         shortcut_jump(prev, node))
2807                         continue;
2808                 }
2809                 break;
2810         }
2811         prev = node;
2812         node = next;
2813     }
2814 }
2815
2816 static void
2817 _sequential_labels(jit_state_t *_jit)
2818 {
2819     jit_node_t          *jump;
2820     jit_node_t          *link;
2821     jit_node_t          *prev;
2822     jit_node_t          *next;
2823     jit_node_t          *node;
2824
2825     for (prev = node = _jitc->head; node; node = next) {
2826         next = node->next;
2827         if (node->code == jit_code_label) {
2828             if (!node->flag) {
2829                 if (!node->link) {
2830                     del_label(prev, node);
2831                     continue;
2832                 }
2833                 if (prev != node && prev->code == jit_code_label) {
2834                     if ((jump = node->link)) {
2835                         for (; jump; jump = link) {
2836                             link = jump->link;
2837                             jump->u.n = prev;
2838                             jump->link = prev->link;
2839                             prev->link = jump;
2840                         }
2841                         node->link = NULL;
2842                     }
2843                     del_label(prev, node);
2844                     continue;
2845                 }
2846             }
2847             if (next && next->code == jit_code_label && !next->flag) {
2848                 if ((jump = next->link)) {
2849                     for (; jump; jump = link) {
2850                         link = jump->link;
2851                         jump->u.n = node;
2852                         jump->link = node->link;
2853                         node->link = jump;
2854                     }
2855                     next->link = NULL;
2856                 }
2857                 del_label(node, next);
2858                 next = node->next;
2859                 continue;
2860             }
2861         }
2862         prev = node;
2863     }
2864 }
2865
2866 static void
2867 _split_branches(jit_state_t *_jit)
2868 {
2869     jit_node_t          *node;
2870     jit_node_t          *next;
2871     jit_node_t          *label;
2872     jit_block_t         *block;
2873
2874     for (node = _jitc->head; node; node = next) {
2875         if ((next = node->next)) {
2876             if (next->code == jit_code_label ||
2877                 next->code == jit_code_prolog ||
2878                 next->code == jit_code_epilog)
2879                 continue;
2880             /* split block on branches */
2881             if (jit_classify(node->code) & jit_cc_a0_jmp) {
2882                 label = new_node(jit_code_label);
2883                 label->next = next;
2884                 node->next = label;
2885                 if (_jitc->blocks.offset >= _jitc->blocks.length) {
2886                     jit_word_t    length;
2887
2888                     length = _jitc->blocks.length + 16;
2889                     jit_realloc((jit_pointer_t *)&_jitc->blocks.ptr,
2890                                 _jitc->blocks.length * sizeof(jit_block_t),
2891                                 length * sizeof(jit_block_t));
2892                     _jitc->blocks.length = length;
2893                 }
2894                 block = _jitc->blocks.ptr + _jitc->blocks.offset;
2895                 block->label = label;
2896                 label->v.w = _jitc->blocks.offset;
2897                 jit_regset_new(&block->reglive);
2898                 jit_regset_new(&block->regmask);
2899                 ++_jitc->blocks.offset;
2900             }
2901         }
2902     }
2903 }
2904
2905 static jit_bool_t
2906 _shortcut_jump(jit_state_t *_jit, jit_node_t *prev, jit_node_t *node)
2907 {
2908     jit_bool_t           cond;
2909     jit_node_t          *jump;
2910     jit_node_t          *next;
2911     jit_node_t          *temp;
2912
2913     if (!(node->flag & jit_flag_node))
2914         return (0);
2915     assert(node->code != jit_code_jmpr);
2916     cond = node->code != jit_code_jmpi;
2917     jump = node->u.n;
2918     for (next = jump->next; next; next = next->next) {
2919         switch (next->code) {
2920             case jit_code_jmpi:
2921                 if (!(next->flag & jit_flag_node))
2922                     return (0);
2923                 if (jump->link == node)
2924                     jump->link = node->link;
2925                 else {
2926                     for (temp = jump->link;
2927                          temp->link != node;
2928                          temp = temp->link)
2929                         assert(temp != NULL);
2930                     temp->link = node->link;
2931                 }
2932                 jump = next->u.n;
2933                 node->u.n = jump;
2934                 node->link = jump->link;
2935                 jump->link = node;
2936                 return (1);
2937             case jit_code_jmpr:
2938                 if (cond)
2939                     return (0);
2940                 node->code = jit_code_jmpr;
2941                 node->u.w = next->u.w;
2942                 node->link = NULL;
2943                 node->flag &= ~jit_flag_node;
2944                 return (1);
2945             case jit_code_note:         case jit_code_label:
2946                 break;
2947             default:
2948                 return (0);
2949         }
2950     }
2951     return (0);
2952 }
2953
2954 static jit_bool_t
2955 _redundant_jump(jit_state_t *_jit, jit_node_t *prev, jit_node_t *node)
2956 {
2957     jit_node_t          *local_prev;
2958     jit_node_t          *local_next;
2959
2960     if (!(node->flag & jit_flag_node))
2961         return (0);
2962     for (local_prev = node, local_next = node->next;
2963          local_next;
2964          local_prev = local_next, local_next = local_next->next) {
2965
2966         switch (local_next->code) {
2967             case jit_code_label:        case jit_code_epilog:
2968                 if (node->u.n == local_next) {
2969                     if (local_next->link == node)
2970                         local_next->link = node->link;
2971                     else {
2972                         for (local_prev = local_next->link;
2973                              local_prev->link != node;
2974                              local_prev = local_prev->link)
2975                             assert(local_prev != NULL);
2976                         local_prev->link = node->link;
2977                     }
2978                     del_node(prev, node);
2979                     return (1);
2980                 }
2981                 break;
2982             case jit_code_name:         case jit_code_note:
2983             case jit_code_align:
2984                 break;
2985             default:
2986                 return (0);
2987         }
2988     }
2989     return (0);
2990 }
2991
2992 static jit_code_t
2993 reverse_jump_code(jit_code_t code)
2994 {
2995     switch (code) {
2996         case jit_code_bltr:     return (jit_code_bger);
2997         case jit_code_blti:     return (jit_code_bgei);
2998         case jit_code_bltr_u:   return (jit_code_bger_u);
2999         case jit_code_blti_u:   return (jit_code_bgei_u);
3000         case jit_code_bler:     return (jit_code_bgtr);
3001         case jit_code_blei:     return (jit_code_bgti);
3002         case jit_code_bler_u:   return (jit_code_bgtr_u);
3003         case jit_code_blei_u:   return (jit_code_bgti_u);
3004         case jit_code_beqr:     return (jit_code_bner);
3005         case jit_code_beqi:     return (jit_code_bnei);
3006         case jit_code_bger:     return (jit_code_bltr);
3007         case jit_code_bgei:     return (jit_code_blti);
3008         case jit_code_bger_u:   return (jit_code_bltr_u);
3009         case jit_code_bgei_u:   return (jit_code_blti_u);
3010         case jit_code_bgtr:     return (jit_code_bler);
3011         case jit_code_bgti:     return (jit_code_blei);
3012         case jit_code_bgtr_u:   return (jit_code_bler_u);
3013         case jit_code_bgti_u:   return (jit_code_blei_u);
3014         case jit_code_bner:     return (jit_code_beqr);
3015         case jit_code_bnei:     return (jit_code_beqi);
3016         case jit_code_bmsr:     return (jit_code_bmcr);
3017         case jit_code_bmsi:     return (jit_code_bmci);
3018         case jit_code_bmcr:     return (jit_code_bmsr);
3019         case jit_code_bmci:     return (jit_code_bmsi);
3020         case jit_code_bltr_f:   return (jit_code_bunger_f);
3021         case jit_code_blti_f:   return (jit_code_bungei_f);
3022         case jit_code_bler_f:   return (jit_code_bungtr_f);
3023         case jit_code_blei_f:   return (jit_code_bungti_f);
3024
3025         case jit_code_beqr_f:   return (jit_code_bner_f);
3026         case jit_code_beqi_f:   return (jit_code_bnei_f);
3027
3028         case jit_code_bger_f:   return (jit_code_bunltr_f);
3029         case jit_code_bgei_f:   return (jit_code_bunlti_f);
3030         case jit_code_bgtr_f:   return (jit_code_bunler_f);
3031         case jit_code_bgti_f:   return (jit_code_bunlei_f);
3032
3033         case jit_code_bner_f:   return (jit_code_beqr_f);
3034         case jit_code_bnei_f:   return (jit_code_beqr_f);
3035
3036         case jit_code_bunltr_f: return (jit_code_bger_f);
3037         case jit_code_bunlti_f: return (jit_code_bgei_f);
3038         case jit_code_bunler_f: return (jit_code_bgtr_f);
3039         case jit_code_bunlei_f: return (jit_code_bgti_f);
3040
3041         case jit_code_buneqr_f: return (jit_code_bltgtr_f);
3042         case jit_code_buneqi_f: return (jit_code_bltgti_f);
3043
3044         case jit_code_bunger_f: return (jit_code_bltr_f);
3045         case jit_code_bungei_f: return (jit_code_blti_f);
3046         case jit_code_bungtr_f: return (jit_code_bler_f);
3047         case jit_code_bungti_f: return (jit_code_blei_f);
3048
3049         case jit_code_bltgtr_f: return (jit_code_buneqr_f);
3050         case jit_code_bltgti_f: return (jit_code_buneqi_f);
3051
3052         case jit_code_bordr_f:  return (jit_code_bunordr_f);
3053         case jit_code_bordi_f:  return (jit_code_bunordi_f);
3054         case jit_code_bunordr_f:return (jit_code_bordr_f);
3055         case jit_code_bunordi_f:return (jit_code_bordi_f);
3056         case jit_code_bltr_d:   return (jit_code_bunger_d);
3057         case jit_code_blti_d:   return (jit_code_bungei_d);
3058         case jit_code_bler_d:   return (jit_code_bungtr_d);
3059         case jit_code_blei_d:   return (jit_code_bungti_d);
3060
3061         case jit_code_beqr_d:   return (jit_code_bner_d);
3062         case jit_code_beqi_d:   return (jit_code_bnei_d);
3063
3064         case jit_code_bger_d:   return (jit_code_bunltr_d);
3065         case jit_code_bgei_d:   return (jit_code_bunlti_d);
3066         case jit_code_bgtr_d:   return (jit_code_bunler_d);
3067         case jit_code_bgti_d:   return (jit_code_bunlei_d);
3068
3069         case jit_code_bner_d:   return (jit_code_beqr_d);
3070         case jit_code_bnei_d:   return (jit_code_beqi_d);
3071
3072         case jit_code_bunltr_d: return (jit_code_bger_d);
3073         case jit_code_bunlti_d: return (jit_code_bgei_d);
3074         case jit_code_bunler_d: return (jit_code_bgtr_d);
3075         case jit_code_bunlei_d: return (jit_code_bgti_d);
3076
3077         case jit_code_buneqr_d: return (jit_code_bltgtr_d);
3078         case jit_code_buneqi_d: return (jit_code_bltgti_d);
3079
3080         case jit_code_bunger_d: return (jit_code_bltr_d);
3081         case jit_code_bungei_d: return (jit_code_blti_d);
3082         case jit_code_bungtr_d: return (jit_code_bler_d);
3083         case jit_code_bungti_d: return (jit_code_blei_d);
3084
3085         case jit_code_bltgtr_d: return (jit_code_buneqr_d);
3086         case jit_code_bltgti_d: return (jit_code_buneqi_d);
3087
3088         case jit_code_bordr_d:  return (jit_code_bunordr_d);
3089         case jit_code_bordi_d:  return (jit_code_bunordi_d);
3090         case jit_code_bunordr_d:return (jit_code_bordr_d);
3091         case jit_code_bunordi_d:return (jit_code_bordi_d);
3092         case jit_code_boaddr:   return (jit_code_bxaddr);
3093         case jit_code_boaddi:   return (jit_code_bxaddi);
3094         case jit_code_boaddr_u: return (jit_code_bxaddr_u);
3095         case jit_code_boaddi_u: return (jit_code_bxaddi_u);
3096         case jit_code_bxaddr:   return (jit_code_boaddr);
3097         case jit_code_bxaddi:   return (jit_code_boaddi);
3098         case jit_code_bxaddr_u: return (jit_code_boaddr_u);
3099         case jit_code_bxaddi_u: return (jit_code_boaddi_u);
3100         case jit_code_bosubr:   return (jit_code_bxsubr);
3101         case jit_code_bosubi:   return (jit_code_bxsubi);
3102         case jit_code_bosubr_u: return (jit_code_bxsubr_u);
3103         case jit_code_bosubi_u: return (jit_code_bxsubi_u);
3104         case jit_code_bxsubr:   return (jit_code_bosubr);
3105         case jit_code_bxsubi:   return (jit_code_bosubi);
3106         case jit_code_bxsubr_u: return (jit_code_bosubr_u);
3107         case jit_code_bxsubi_u: return (jit_code_bosubi_u);
3108         default:                abort();        /* invalid jump code */
3109     }
3110 }
3111
3112 /*
3113  * change common pattern:
3114  *      <cond_jump L0> <jump L1> <label L0>
3115  * into
3116  *      <reverse_cond_jump L1>
3117  */
3118 static jit_bool_t
3119 _reverse_jump(jit_state_t *_jit, jit_node_t *prev, jit_node_t *node)
3120 {
3121     jit_node_t          *local_prev;
3122     jit_node_t          *local_next;
3123     jit_node_t          *local_jump;
3124
3125     if (!(node->flag & jit_flag_node))
3126         return (0);
3127     /* =><cond_jump L0> <jump L1> <label L0> */
3128     local_next = node->next;
3129     if (local_next->code != jit_code_jmpi ||
3130         !(local_next->flag & jit_flag_node))
3131         return (0);
3132     /* <cond_jump L0> =><jump L1> <label L0> */
3133
3134     local_jump = local_next->u.n;
3135     for (local_prev = local_next, local_next = local_next->next;
3136          local_next;
3137          local_prev = local_next, local_next = local_next->next) {
3138         switch (local_next->code) {
3139             case jit_code_label:        case jit_code_epilog:
3140                 if (node->u.n == local_next) {
3141                     if (local_next->link == node)
3142                         local_next->link = node->link;
3143                     else {
3144                         for (local_prev = local_next->link;
3145                              local_prev->link != node;
3146                              local_prev = local_prev->link)
3147                             assert(local_prev != NULL);
3148                         local_prev->link = node->link;
3149                     }
3150                     del_node(node, node->next);
3151                     node->code = reverse_jump_code(node->code);
3152                     node->u.n = local_jump;
3153                     node->link = local_jump->link;
3154                     local_jump->link = node;
3155                     return (1);
3156                 }
3157                 break;
3158             case jit_code_note:
3159                 break;
3160             default:
3161                 return (0);
3162         }
3163     }
3164     return (0);
3165 }
3166
3167 static jit_bool_t
3168 _redundant_store(jit_state_t *_jit, jit_node_t *node, jit_bool_t jump)
3169 {
3170     jit_node_t          *iter;
3171     jit_node_t          *prev;
3172     jit_word_t           word;
3173     jit_int32_t          spec;
3174     jit_int32_t          regno;
3175     jit_bool_t           result;
3176
3177     if (jump) {
3178         prev = node->u.n;
3179         if (prev->code == jit_code_epilog)
3180             return (0);
3181         assert(prev->code == jit_code_label);
3182         if ((prev->flag & jit_flag_head) || node->link || prev->link != node)
3183             /* multiple sources */
3184             return (0);
3185         /* if there are sequential labels it will return below */
3186     }
3187     else
3188         prev = node;
3189     result = 0;
3190     word = node->w.w;
3191     regno = jit_regno(node->v.w);
3192     for (iter = prev->next; iter; prev = iter, iter = iter->next) {
3193         switch (iter->code) {
3194             case jit_code_label:        case jit_code_prolog:
3195             case jit_code_epilog:
3196                 return (result);
3197             case jit_code_movi:
3198                 if (regno == jit_regno(iter->u.w)) {
3199                     if (iter->flag || iter->v.w != word)
3200                         return (result);
3201                     result = 1;
3202                     del_node(prev, iter);
3203                     iter = prev;
3204                 }
3205                 break;
3206             default:
3207                 spec = jit_classify(iter->code);
3208                 if (spec & jit_cc_a0_jmp)
3209                     return (result);
3210                 if ((spec & (jit_cc_a0_reg|jit_cc_a0_chg)) ==
3211                     (jit_cc_a0_reg|jit_cc_a0_chg)) {
3212                     if (spec & jit_cc_a0_rlh) {
3213                         if (regno == jit_regno(iter->u.q.l) ||
3214                             regno == jit_regno(iter->u.q.h))
3215                             return (result);
3216                     }
3217                     else {
3218                         if (regno == jit_regno(iter->u.w))
3219                             return (result);
3220                     }
3221                 }
3222                 if ((spec & (jit_cc_a1_reg|jit_cc_a1_chg)) ==
3223                     (jit_cc_a1_reg|jit_cc_a1_chg)) {
3224                     if (regno == jit_regno(iter->v.w))
3225                         return (result);
3226                 }
3227                 if ((spec & (jit_cc_a2_reg|jit_cc_a2_chg)) ==
3228                     (jit_cc_a2_reg|jit_cc_a2_chg)) {
3229                     if (regno == jit_regno(iter->w.w))
3230                         return (result);
3231                 }
3232                 break;
3233         }
3234     }
3235
3236     return (result);
3237 }
3238
3239 static jit_bool_t
3240 _simplify_movr(jit_state_t *_jit, jit_node_t *prev, jit_node_t *node,
3241                jit_int32_t kind, jit_int32_t size)
3242 {
3243     jit_int32_t          regno;
3244     jit_int32_t          right;
3245     jit_value_t         *value;
3246
3247     regno = jit_regno(node->u.w);
3248     right = jit_regno(node->v.w);
3249     value = _jitc->values + regno;
3250     if ((value->kind == jit_kind_register &&
3251          jit_regno(value->base.q.l) == right &&
3252          value->base.q.h == _jitc->gen[right]) ||
3253         (value->kind == kind && _jitc->values[right].kind == kind &&
3254          memcmp(&value->base.w, &_jitc->values[right].base.w, size) == 0)) {
3255         del_node(prev, node);
3256         return (1);
3257     }
3258     if (_jitc->values[right].kind == jit_kind_word)
3259         jit_memcpy(value, _jitc->values + right, sizeof(jit_value_t));
3260     else {
3261         value->kind = jit_kind_register;
3262         value->base.q.l = right;
3263         value->base.q.h = _jitc->gen[right];
3264     }
3265     ++_jitc->gen[regno];
3266
3267     return (0);
3268 }
3269
3270 static jit_bool_t
3271 _simplify_movi(jit_state_t *_jit, jit_node_t *prev, jit_node_t *node,
3272                jit_int32_t kind, jit_int32_t size)
3273 {
3274     jit_value_t         *value;
3275     jit_int32_t          spec;
3276     jit_int32_t          regno;
3277     jit_int32_t          offset;
3278
3279     regno = jit_regno(node->u.w);
3280     value = _jitc->values + regno;
3281     if (node->flag & jit_flag_node) {
3282         /* set to undefined if value will be patched */
3283         value->kind = 0;
3284         ++_jitc->gen[regno];
3285         return (0);
3286     }
3287     if (value->kind == kind) {
3288         if (memcmp(&node->v.w, &value->base.w, size) == 0) {
3289             del_node(prev, node);
3290             return (1);
3291         }
3292         spec = jit_class(_rvs[regno].spec);
3293         if (kind == jit_kind_word)
3294             spec &= jit_class_gpr;
3295         else
3296             spec &= (jit_class_xpr | jit_class_fpr);
3297         for (offset = 0; offset < _jitc->reglen; offset++) {
3298             if (_jitc->values[offset].kind == kind &&
3299                 memcmp(&node->v.w, &_jitc->values[offset].base.w, size) == 0 &&
3300                 (jit_class(_rvs[offset].spec) & spec) == spec) {
3301                 if (kind == jit_kind_word)
3302                     node->code = jit_code_movr;
3303                 else if (kind == jit_kind_float32)
3304                     node->code = jit_code_movr_f;
3305                 else
3306                     node->code = jit_code_movr_d;
3307                 node->v.w = offset;
3308                 jit_memcpy(value, _jitc->values + offset, sizeof(jit_value_t));
3309                 ++_jitc->gen[regno];
3310                 return (0);
3311             }
3312         }
3313     }
3314     value->kind = kind;
3315     jit_memcpy(&value->base.w, &node->v.w, size);
3316     ++_jitc->gen[regno];
3317
3318     return (0);
3319 }
3320
3321 /* simple/safe redundandy test not checking if another register
3322  * holds the same value
3323  */
3324 static jit_bool_t
3325 _simplify_ldxi(jit_state_t *_jit, jit_node_t *prev, jit_node_t *node)
3326 {
3327     jit_value_t         *value;
3328     jit_int32_t          regno;
3329     jit_int32_t          right;
3330
3331     regno = jit_regno(node->u.w);
3332     right = jit_regno(node->v.w);
3333     value = _jitc->values + regno;
3334     if (regno != right &&
3335         value->kind == jit_kind_code && value->code == node->code &&
3336         value->base.q.l == right && value->base.q.h == _jitc->gen[right] &&
3337         node->w.w == value->disp.w) {
3338         del_node(prev, node);
3339         return (1);
3340     }
3341     value->kind = jit_kind_code;
3342     value->code = node->code;
3343     value->base.q.l = right;
3344     value->base.q.h = _jitc->gen[right];
3345     value->disp.w = node->w.w;
3346     ++_jitc->gen[regno];
3347
3348     return (0);
3349 }
3350
3351 static jit_bool_t
3352 _simplify_stxi(jit_state_t *_jit, jit_node_t *prev, jit_node_t *node)
3353 {
3354     jit_value_t         *value;
3355     jit_int32_t          regno;
3356     jit_int32_t          right;
3357     jit_int32_t          offset;
3358
3359     regno = jit_regno(node->w.w);
3360     right = jit_regno(node->v.w);
3361     value = _jitc->values + regno;
3362
3363     /* check for redundant store after load */
3364     if (regno != right &&
3365         value->kind == jit_kind_code && value->code == node->code &&
3366         value->base.q.l == right && value->base.q.h == _jitc->gen[right] &&
3367         node->u.w == value->disp.w) {
3368         del_node(prev, node);
3369         return (1);
3370     }
3371
3372     /* assume anything can alias, and invalidate tracked values */
3373     for (offset = 0; offset < _jitc->reglen; offset++) {
3374         if (_jitc->values[offset].kind == jit_kind_code) {
3375             _jitc->values[offset].kind = 0;
3376             ++_jitc->gen[offset];
3377         }
3378     }
3379
3380     /* no multiple information, so, if set to a constant,
3381      * prefer to keep that information */
3382     if (value->kind == 0) {
3383         value->kind = jit_kind_code;
3384         switch (node->code) {
3385             /* no information about signed/unsigned either */
3386             case jit_code_stxi_c:       value->code = jit_code_ldxi_c;  break;
3387             case jit_code_stxi_s:       value->code = jit_code_ldxi_s;  break;
3388             case jit_code_stxi_i:       value->code = jit_code_ldxi_i;  break;
3389             case jit_code_stxi_l:       value->code = jit_code_ldxi_l;  break;
3390             case jit_code_stxi_f:       value->code = jit_code_ldxi_f;  break;
3391             case jit_code_stxi_d:       value->code = jit_code_ldxi_d;  break;
3392             default:                    abort();
3393         }
3394         value->kind = jit_kind_code;
3395         value->base.q.l = right;
3396         value->base.q.h = _jitc->gen[right];
3397         value->disp.w = node->u.w;
3398     }
3399
3400     return (0);
3401 }
3402
3403 /* usually there should be only one store in the
3404  * jit_get_reg/jit_unget_reg, but properly handle
3405  * multiple ones by moving the save node */
3406 static void
3407 _simplify_spill(jit_state_t *_jit, jit_node_t *node, jit_int32_t regno)
3408 {
3409     jit_node_t          *save;
3410     jit_node_t          *temp;
3411
3412     if ((temp = _jitc->spill[regno]) && (save = temp->next) != node) {
3413         temp->next = save->next;
3414         save->next = node->next;
3415         node->next = save;
3416         _jitc->spill[regno] = node;
3417     }
3418 }
3419
3420 /* checks for simple cases where a register is set more than
3421  * once to the same value, and is a common pattern of calls
3422  * to jit_pushargi and jit_pushargr
3423  */
3424 static jit_bool_t
3425 _simplify(jit_state_t *_jit)
3426 {
3427     jit_node_t          *prev;
3428     jit_node_t          *node;
3429     jit_node_t          *next;
3430     jit_int32_t          info;
3431     jit_int32_t          regno;
3432     jit_bool_t           result;
3433
3434     result = 0;
3435     for (prev = NULL, node = _jitc->head; node; prev = node, node = next) {
3436         next = node->next;
3437         switch (node->code) {
3438             case jit_code_label:        case jit_code_prolog:
3439             case jit_code_callr:        case jit_code_calli:
3440             reset:
3441                 memset(_jitc->gen, 0, sizeof(jit_int32_t) * _jitc->reglen);
3442                 memset(_jitc->values, 0, sizeof(jit_value_t) * _jitc->reglen);
3443                 break;
3444             case jit_code_save:
3445                 _jitc->spill[jit_regno(node->u.w)] = prev;
3446                 break;
3447             case jit_code_load:
3448                 regno = jit_regno(node->u.w);
3449                 if (register_change_p(node->link->next, node, regno) !=
3450                     jit_reg_change) {
3451                     /* spill not required due to optimizing common
3452                      * redundancy case of calling jit_get_reg/jit_unget_reg
3453                      * and then setting the register to the value it is
3454                      * already holding */
3455                     patch_register(node->link->next, node,
3456                                    jit_regno_patch|regno, regno);
3457                     result = 1;
3458                     del_node(_jitc->spill[regno], node->link);
3459                     del_node(prev, node);
3460                     node = prev;
3461                 }
3462                 _jitc->spill[regno] = NULL;
3463                 break;
3464             case jit_code_movr:
3465                 regno = jit_regno(node->u.w);
3466                 if (simplify_movr(prev, node,
3467                                   jit_kind_word, sizeof(jit_word_t))) {
3468                     result = 1;
3469                     simplify_spill(node = prev, regno);
3470                 }
3471                 break;
3472             case jit_code_movi:
3473                 regno = jit_regno(node->u.w);
3474                 if (simplify_movi(prev, node,
3475                                   jit_kind_word, sizeof(jit_word_t))) {
3476                     result = 1;
3477                     simplify_spill(node = prev, regno);
3478                 }
3479                 break;
3480             case jit_code_movr_f:
3481                 regno = jit_regno(node->u.w);
3482                 if (simplify_movr(prev, node,
3483                                   jit_kind_float32, sizeof(jit_float32_t))) {
3484                     result = 1;
3485                     simplify_spill(node = prev, regno);
3486                 }
3487                 break;
3488             case jit_code_movi_f:
3489                 regno = jit_regno(node->u.w);
3490                 if (simplify_movi(prev, node,
3491                                   jit_kind_float32, sizeof(jit_float32_t))) {
3492                     result = 1;
3493                     simplify_spill(node = prev, regno);
3494                 }
3495                 break;
3496             case jit_code_movr_d:
3497                 regno = jit_regno(node->u.w);
3498                 if (simplify_movr(prev, node,
3499                                   jit_kind_float64, sizeof(jit_float64_t))) {
3500                     result = 1;
3501                     simplify_spill(node = prev, regno);
3502                 }
3503                 break;
3504             case jit_code_movi_d:
3505                 regno = jit_regno(node->u.w);
3506                 if (simplify_movi(prev, node,
3507                                   jit_kind_float64, sizeof(jit_float64_t))) {
3508                     result = 1;
3509                     simplify_spill(node = prev, regno);
3510                 }
3511                 break;
3512             case jit_code_ldxi_c:       case jit_code_ldxi_uc:
3513             case jit_code_ldxi_s:       case jit_code_ldxi_us:
3514             case jit_code_ldxi_i:       case jit_code_ldxi_ui:
3515             case jit_code_ldxi_l:
3516             case jit_code_ldxi_f:       case jit_code_ldxi_d:
3517                 regno = jit_regno(node->u.w);
3518                 if (simplify_ldxi(prev, node)) {
3519                     result = 1;
3520                     simplify_spill(node = prev, regno);
3521                 }
3522                 break;
3523             case jit_code_stxi_c:       case jit_code_stxi_s:
3524             case jit_code_stxi_i:       case jit_code_stxi_l:
3525             case jit_code_stxi_f:       case jit_code_stxi_d:
3526                 regno = jit_regno(node->u.w);
3527                 if (simplify_stxi(prev, node)) {
3528                     result = 1;
3529                     simplify_spill(node = prev, regno);
3530                 }
3531                 break;
3532             default:
3533                 info = jit_classify(node->code);
3534                 if (info & jit_cc_a0_jmp)
3535                     /* labels are not implicitly added when not taking
3536                      * a conditional branch */
3537                     goto reset;
3538                 if (info & jit_cc_a0_chg) {
3539                     if (info & jit_cc_a0_rlh) {
3540                         regno = jit_regno(node->u.q.l);
3541                         _jitc->values[regno].kind = 0;
3542                         ++_jitc->gen[regno];
3543                         regno = jit_regno(node->u.q.h);
3544                         _jitc->values[regno].kind = 0;
3545                         ++_jitc->gen[regno];
3546                     }
3547                     else {
3548                         regno = jit_regno(node->u.w);
3549                         _jitc->values[regno].kind = 0;
3550                         ++_jitc->gen[regno];
3551                     }
3552                 }
3553                 if (info & jit_cc_a1_chg) {
3554                     regno = jit_regno(node->v.w);
3555                     _jitc->values[regno].kind = 0;
3556                     ++_jitc->gen[regno];
3557                 }
3558                 if (info & jit_cc_a2_chg) {
3559 #if 0
3560                     /* Assume registers are not changed */
3561                     if (info & jit_cc_a2_rlh) {
3562                         regno = jit_regno(node->w.q.l);
3563                         _jitc->values[regno].kind = 0;
3564                         ++_jitc->gen[regno];
3565                         regno = jit_regno(node->w.q.h);
3566                         _jitc->values[regno].kind = 0;
3567                         ++_jitc->gen[regno];
3568                     }
3569                     else {
3570 #endif
3571                         regno = jit_regno(node->w.w);
3572                         _jitc->values[regno].kind = 0;
3573                         ++_jitc->gen[regno];
3574 #if 0
3575                     }
3576 #endif
3577                 }
3578                 break;
3579         }
3580     }
3581     return (result);
3582 }
3583
3584 static jit_int32_t
3585 _register_change_p(jit_state_t *_jit, jit_node_t *node, jit_node_t *link,
3586                    jit_int32_t regno)
3587 {
3588     jit_int32_t         value;
3589
3590     for (; node != link; node = node->next) {
3591         switch (node->code) {
3592             case jit_code_label:        case jit_code_prolog:
3593                 /* lack of extra information so cannot say it is undefined */
3594                 return (jit_reg_change);
3595             case jit_code_callr:        case jit_code_calli:
3596                 if (!(jit_class(_rvs[regno].spec) & jit_class_sav))
3597                     return (jit_reg_undef);
3598                 break;
3599             default:
3600                 value = jit_classify(node->code);
3601                 /* lack of extra information */
3602                 if (value & (jit_cc_a0_jmp|jit_cc_a0_cnd))
3603                     return (jit_reg_change);
3604                 else if ((value & (jit_cc_a0_reg|jit_cc_a0_chg)) ==
3605                          (jit_cc_a0_reg|jit_cc_a0_chg) &&
3606                          (((value & jit_cc_a0_rlh) &&
3607                            (node->u.q.l == regno || node->u.q.h == regno)) ||
3608                           (!(value & jit_cc_a0_rlh) &&
3609                            node->u.w == regno)))
3610                     return (jit_reg_change);
3611                 else if ((value & jit_cc_a1_reg) && node->v.w == regno &&
3612                          (value & jit_cc_a1_chg))
3613                     return (jit_reg_change);
3614                 else if ((value & jit_cc_a2_reg) && node->w.w == regno &&
3615                          (value & jit_cc_a2_chg))
3616                     return (jit_reg_change);
3617         }
3618     }
3619
3620     return (jit_reg_static);
3621 }
3622
3623 /* most of this could be done at the same time as generating jit, but
3624  * avoid complications on different cpu backends and patch spill/loads
3625  * here, by simulating jit generation */
3626 static jit_bool_t
3627 _spill_reglive_p(jit_state_t *_jit, jit_node_t *node, jit_int32_t regno)
3628 {
3629     if (!jit_regset_tstbit(&_jitc->reglive, regno)) {
3630         jit_regset_setbit(&_jitc->regmask, regno);
3631         jit_update(node->next, &_jitc->reglive, &_jitc->regmask);
3632         if (!jit_regset_tstbit(&_jitc->reglive, regno) &&
3633             register_change_p(node->next, node->link, regno) != jit_reg_change)
3634             return (0);
3635     }
3636
3637     return (1);
3638 }
3639
3640 static void
3641 _patch_registers(jit_state_t *_jit)
3642 {
3643     jit_node_t          *prev;
3644     jit_node_t          *node;
3645     jit_node_t          *next;
3646     jit_int32_t          info;
3647     jit_int32_t          spec;
3648     jit_int32_t          regno;
3649     jit_int32_t          value;
3650
3651     _jitc->function = NULL;
3652
3653     jit_reglive_setup();
3654     for (prev = NULL, node = _jitc->head; node; node = next) {
3655         next = node->next;
3656
3657         info = jit_classify(node->code);
3658         jit_regarg_set(node, info);
3659
3660         switch (node->code) {
3661             case jit_code_save:
3662                 regno = jit_regno(node->u.w);
3663                 if (!spill_reglive_p(node, regno)) {
3664                     /* register is not live, just remove spill/reload */
3665                     jit_regarg_clr(node, info);
3666                     node->link->v.w = jit_regload_delete;
3667                     del_node(prev, node);
3668                     continue;
3669                 }
3670                 else {
3671                     /* try to find a free register of the same class */
3672                     spec = jit_class(_rvs[regno].spec) & ~jit_class_arg;
3673                     for (value = 0; value < _jitc->reglen; value++) {
3674                         if (value != regno &&
3675                             ((jit_class(_rvs[value].spec) & spec) &
3676                              ~jit_class_arg) == spec &&
3677                             !jit_regset_tstbit(&_jitc->regarg, value) &&
3678                             !spill_reglive_p(node, value))
3679                             break;
3680                     }
3681                     if (value < _jitc->reglen) {
3682                         jit_regarg_clr(node, info);
3683                         patch_register(node->next, node->link,
3684                                        jit_regno_patch|node->u.w,
3685                                        jit_regno_patch|value);
3686                         /* mark as live just in case there are nested
3687                          * register patches, so that next patch will
3688                          * not want to use the same register */
3689                         jit_regset_setbit(&_jitc->reglive, value);
3690                         /* register is not live, just remove spill/reload */
3691                         node->link->v.w = jit_regload_isdead;
3692                         del_node(prev, node);
3693                         continue;
3694                     }
3695                     else {
3696                         /* failed to find a free register */
3697                         if (spec & jit_class_gpr) {
3698                             if (!_jitc->function->regoff[regno])
3699                                 _jitc->function->regoff[regno] =
3700                                     jit_allocai(sizeof(jit_word_t));
3701 #if __WORDSIZE == 32
3702                             node->code = jit_code_stxi_i;
3703 #else
3704                             node->code = jit_code_stxi_l;
3705 #endif
3706                         }
3707                         else {
3708                             node->code = jit_code_stxi_d;
3709                             if (!_jitc->function->regoff[regno])
3710                                 _jitc->function->regoff[regno] =
3711                                     jit_allocai(sizeof(jit_float64_t));
3712                         }
3713                         node->u.w = _jitc->function->regoff[regno];
3714                         node->v.w = JIT_FP;
3715                         node->w.w = regno;
3716                         node->link = NULL;
3717                     }
3718                 }
3719                 break;
3720             case jit_code_load:
3721                 regno = jit_regno(node->u.w);
3722                 if (node->v.w) {
3723                     if (node->v.w == jit_regload_isdead)
3724                         jit_regset_clrbit(&_jitc->reglive, regno);
3725                     del_node(prev, node);
3726                     continue;
3727                 }
3728                 spec = jit_class(_rvs[regno].spec);
3729                 if (spec & jit_class_gpr) {
3730 #if __WORDSIZE == 32
3731                     node->code = jit_code_ldxi_i;
3732 #else
3733                     node->code = jit_code_ldxi_l;
3734 #endif
3735                 }
3736                 else
3737                     node->code = jit_code_ldxi_d;
3738                 node->v.w = regno;
3739                 node->v.w = JIT_FP;
3740                 node->w.w = _jitc->function->regoff[regno];
3741                 node->link = NULL;
3742                 break;
3743             case jit_code_prolog:
3744                 _jitc->function = _jitc->functions.ptr + node->w.w;
3745                 break;
3746             case jit_code_epilog:
3747                 _jitc->function = NULL;
3748                 break;
3749             default:
3750                 break;
3751         }
3752
3753         jit_regarg_clr(node, info);
3754         /* update register live state */
3755         jit_reglive(node);
3756         prev = node;
3757     }
3758 }
3759
3760 static void
3761 _patch_register(jit_state_t *_jit, jit_node_t *node, jit_node_t *link,
3762                 jit_int32_t regno, jit_int32_t patch)
3763 {
3764     jit_int32_t         value;
3765
3766     for (; node != link; node = node->next) {
3767         value = jit_classify(node->code);
3768         if (value & jit_cc_a0_reg) {
3769             if (value & jit_cc_a0_rlh) {
3770                 if (node->u.q.l == regno)
3771                     node->u.q.l = patch;
3772                 if (node->u.q.h == regno)
3773                     node->u.q.h = patch;
3774             }
3775             else {
3776                 if (node->u.w == regno)
3777                     node->u.w = patch;
3778             }
3779         }
3780         if ((value & jit_cc_a1_reg) && node->v.w == regno)
3781             node->v.w = patch;
3782         if (value & jit_cc_a2_reg) {
3783             if (value & jit_cc_a2_rlh) {
3784                 if (node->w.q.l == regno)
3785                     node->w.q.l = patch;
3786                 if (node->w.q.h == regno)
3787                     node->w.q.h = patch;
3788             }
3789             else {
3790                 if (node->w.w == regno)
3791                     node->w.w = patch;
3792             }
3793         }
3794     }
3795 }
3796
3797 #if __BYTE_ORDER == __LITTLE_ENDIAN
3798 #  define htonr_us(r0,r1)               bswapr_us(r0,r1)
3799 #  define htonr_ui(r0,r1)               bswapr_ui(r0,r1)
3800 #  if __WORDSIZE == 64
3801 #    define htonr_ul(r0,r1)             bswapr_ul(r0,r1)
3802 #  endif
3803 #else
3804 #  define htonr_us(r0,r1)               extr_us(r0,r1)
3805 #  if __WORDSIZE == 32
3806 #    define htonr_ui(r0,r1)             movr(r0,r1)
3807 #  else
3808 #    define htonr_ui(r0,r1)             extr_ui(r0,r1)
3809 #    define htonr_ul(r0,r1)             movr(r0,r1)
3810 #  endif
3811 #endif
3812
3813 static maybe_unused void
3814 generic_bswapr_us(jit_state_t *_jit, jit_int32_t r0, jit_int32_t r1);
3815 static maybe_unused void
3816 generic_bswapr_ui(jit_state_t *_jit, jit_int32_t r0, jit_int32_t r1);
3817 #if __WORDSIZE == 64
3818 static maybe_unused void
3819 generic_bswapr_ul(jit_state_t *_jit, jit_int32_t r0, jit_int32_t r1);
3820 #endif
3821
3822 #if defined(__i386__) || defined(__x86_64__)
3823 #  include "jit_x86.c"
3824 #elif defined(__mips__)
3825 #  include "jit_mips.c"
3826 #elif defined(__arm__)
3827 #  include "jit_arm.c"
3828 #elif defined(__powerpc__)
3829 #  include "jit_ppc.c"
3830 #elif defined(__sparc__)
3831 #  include "jit_sparc.c"
3832 #elif defined(__ia64__)
3833 #  include "jit_ia64.c"
3834 #elif defined(__hppa__)
3835 #  include "jit_hppa.c"
3836 #elif defined(__aarch64__)
3837 #  include "jit_aarch64.c"
3838 #elif defined(__s390__) || defined(__s390x__)
3839 #  include "jit_s390.c"
3840 #elif defined(__alpha__)
3841 #  include "jit_alpha.c"
3842 #elif defined(__riscv)
3843 #  include "jit_riscv.c"
3844 #endif
3845
3846 static maybe_unused void
3847 generic_bswapr_us(jit_state_t *_jit, jit_int32_t r0, jit_int32_t r1)
3848 {
3849     jit_int32_t reg = jit_get_reg(jit_class_gpr);
3850
3851     rshi(rn(reg), r1, 8);
3852     andi(r0, r1, 0xff);
3853     andi(rn(reg), rn(reg), 0xff);
3854     lshi(r0, r0, 8);
3855     orr(r0, r0, rn(reg));
3856
3857     jit_unget_reg(reg);
3858 }
3859
3860 static maybe_unused void
3861 generic_bswapr_ui(jit_state_t *_jit, jit_int32_t r0, jit_int32_t r1)
3862 {
3863     jit_int32_t reg = jit_get_reg(jit_class_gpr);
3864
3865         rshi(rn(reg), r1, 16);
3866         bswapr_us(r0, r1);
3867         bswapr_us(rn(reg), rn(reg));
3868         lshi(r0, r0, 16);
3869         orr(r0, r0, rn(reg));
3870
3871     jit_unget_reg(reg);
3872 }
3873
3874 #if __WORDSIZE == 64
3875 static maybe_unused void
3876 generic_bswapr_ul(jit_state_t *_jit, jit_int32_t r0, jit_int32_t r1)
3877 {
3878     jit_int32_t reg = jit_get_reg(jit_class_gpr);
3879
3880     rshi_u(rn(reg), r1, 32);
3881     bswapr_ui(r0, r1);
3882     bswapr_ui(rn(reg), rn(reg));
3883     lshi(r0, r0, 32);
3884     orr(r0, r0, rn(reg));
3885
3886     jit_unget_reg(reg);
3887 }
3888 #endif