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