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