deps/lightning/lib/lightning.c

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