deps/lightning/lib/lightning.c

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