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_movnr:    case jit_code_movzr:
1439         case jit_code_addr:     case jit_code_addxr:    case jit_code_addcr:
1440         case jit_code_subr:     case jit_code_subxr:    case jit_code_subcr:
1441         case jit_code_mulr:     case jit_code_divr:     case jit_code_divr_u:
1442         case jit_code_remr:     case jit_code_remr_u:   case jit_code_andr:
1443         case jit_code_orr:      case jit_code_xorr:     case jit_code_lshr:
1444         case jit_code_rshr:     case jit_code_rshr_u:   case jit_code_ltr:
1445         case jit_code_ltr_u:    case jit_code_ler:      case jit_code_ler_u:
1446         case jit_code_eqr:      case jit_code_ger:      case jit_code_ger_u:
1447         case jit_code_gtr:      case jit_code_gtr_u:    case jit_code_ner:
1448         case jit_code_ldxr_c:   case jit_code_ldxr_uc:  case jit_code_ldxr_s:
1449         case jit_code_ldxr_us:  case jit_code_ldxr_i:   case jit_code_ldxr_ui:
1450         case jit_code_ldxr_l:   case jit_code_addr_f:   case jit_code_subr_f:
1451         case jit_code_mulr_f:   case jit_code_divr_f:   case jit_code_ltr_f:
1452         case jit_code_ler_f:    case jit_code_eqr_f:    case jit_code_ger_f:
1453         case jit_code_gtr_f:    case jit_code_ner_f:    case jit_code_unltr_f:
1454         case jit_code_unler_f:  case jit_code_uneqr_f:  case jit_code_unger_f:
1455         case jit_code_ungtr_f:  case jit_code_ltgtr_f:  case jit_code_ordr_f:
1456         case jit_code_unordr_f: case jit_code_ldxr_f:   case jit_code_addr_d:
1457         case jit_code_subr_d:   case jit_code_mulr_d:   case jit_code_divr_d:
1458         case jit_code_ltr_d:    case jit_code_ler_d:    case jit_code_eqr_d:
1459         case jit_code_ger_d:    case jit_code_gtr_d:    case jit_code_ner_d:
1460         case jit_code_unltr_d:  case jit_code_unler_d:  case jit_code_uneqr_d:
1461         case jit_code_unger_d:  case jit_code_ungtr_d:  case jit_code_ltgtr_d:
1462         case jit_code_ordr_d:   case jit_code_unordr_d: case jit_code_ldxr_d:
1463         case jit_code_movr_ww_d:
1464             mask = jit_cc_a0_reg|jit_cc_a0_chg|jit_cc_a1_reg|jit_cc_a2_reg;
1465             break;
1466         case jit_code_qmulr:    case jit_code_qmulr_u:
1467         case jit_code_qdivr:    case jit_code_qdivr_u:
1468             mask = jit_cc_a0_reg|jit_cc_a0_rlh|jit_cc_a0_chg|
1469                    jit_cc_a1_reg|jit_cc_a2_reg;
1470             break;
1471         case jit_code_sti_c:    case jit_code_sti_s:    case jit_code_sti_i:
1472         case jit_code_sti_l:    case jit_code_sti_f:    case jit_code_sti_d:
1473             mask = jit_cc_a0_int|jit_cc_a1_reg;
1474             break;
1475         case jit_code_blti:     case jit_code_blti_u:   case jit_code_blei:
1476         case jit_code_blei_u:   case jit_code_beqi:     case jit_code_bgei:
1477         case jit_code_bgei_u:   case jit_code_bgti:     case jit_code_bgti_u:
1478         case jit_code_bnei:     case jit_code_bmsi:     case jit_code_bmci:
1479             mask = jit_cc_a0_jmp|jit_cc_a1_reg|jit_cc_a2_int;
1480             break;
1481         case jit_code_blti_f:   case jit_code_blei_f:   case jit_code_beqi_f:
1482         case jit_code_bgei_f:   case jit_code_bgti_f:   case jit_code_bnei_f:
1483         case jit_code_bunlti_f: case jit_code_bunlei_f: case jit_code_buneqi_f:
1484         case jit_code_bungei_f: case jit_code_bungti_f: case jit_code_bltgti_f:
1485         case jit_code_bordi_f:  case jit_code_bunordi_f:
1486             mask = jit_cc_a0_jmp|jit_cc_a1_reg|jit_cc_a2_flt;
1487             break;
1488         case jit_code_blti_d:   case jit_code_blei_d:   case jit_code_beqi_d:
1489         case jit_code_bgei_d:   case jit_code_bgti_d:   case jit_code_bnei_d:
1490         case jit_code_bunlti_d: case jit_code_bunlei_d: case jit_code_buneqi_d:
1491         case jit_code_bungei_d: case jit_code_bungti_d: case jit_code_bltgti_d:
1492         case jit_code_bordi_d:  case jit_code_bunordi_d:
1493             mask = jit_cc_a0_jmp|jit_cc_a1_reg|jit_cc_a2_dbl;
1494             break;
1495         case jit_code_allocar:  /* synthesized instructions make it
1496                                  * equivalent to jit_cc_a0_chg */
1497         case jit_code_str_c:    case jit_code_str_s:    case jit_code_str_i:
1498         case jit_code_str_l:    case jit_code_str_f:    case jit_code_str_d:
1499             mask = jit_cc_a0_reg|jit_cc_a1_reg;
1500             break;
1501         case jit_code_stxi_c:   case jit_code_stxi_s:   case jit_code_stxi_i:
1502         case jit_code_stxi_l:   case jit_code_stxi_f:   case jit_code_stxi_d:
1503             mask = jit_cc_a0_int|jit_cc_a1_reg|jit_cc_a2_reg;
1504             break;
1505         case jit_code_bltr:     case jit_code_bltr_u:   case jit_code_bler:
1506         case jit_code_bler_u:   case jit_code_beqr:     case jit_code_bger:
1507         case jit_code_bger_u:   case jit_code_bgtr:     case jit_code_bgtr_u:
1508         case jit_code_bner:     case jit_code_bmsr:     case jit_code_bmcr:
1509         case jit_code_bltr_f:   case jit_code_bler_f:   case jit_code_beqr_f:
1510         case jit_code_bger_f:   case jit_code_bgtr_f:   case jit_code_bner_f:
1511         case jit_code_bunltr_f: case jit_code_bunler_f: case jit_code_buneqr_f:
1512         case jit_code_bunger_f: case jit_code_bungtr_f: case jit_code_bltgtr_f:
1513         case jit_code_bordr_f:  case jit_code_bunordr_f:case jit_code_bltr_d:
1514         case jit_code_bler_d:   case jit_code_beqr_d:   case jit_code_bger_d:
1515         case jit_code_bgtr_d:   case jit_code_bner_d:   case jit_code_bunltr_d:
1516         case jit_code_bunler_d: case jit_code_buneqr_d: case jit_code_bunger_d:
1517         case jit_code_bungtr_d: case jit_code_bltgtr_d: case jit_code_bordr_d:
1518         case jit_code_bunordr_d:
1519             mask = jit_cc_a0_jmp|jit_cc_a1_reg|jit_cc_a2_reg;
1520             break;
1521         case jit_code_boaddi:   case jit_code_boaddi_u: case jit_code_bxaddi:
1522         case jit_code_bxaddi_u: case jit_code_bosubi:   case jit_code_bosubi_u:
1523         case jit_code_bxsubi:   case jit_code_bxsubi_u:
1524             mask = jit_cc_a0_jmp|jit_cc_a1_reg|jit_cc_a1_chg|jit_cc_a2_int;
1525             break;
1526         case jit_code_stxr_c:   case jit_code_stxr_s:   case jit_code_stxr_i:
1527         case jit_code_stxr_l:   case jit_code_stxr_f:   case jit_code_stxr_d:
1528             mask = jit_cc_a0_reg|jit_cc_a1_reg|jit_cc_a2_reg;
1529             break;
1530         case jit_code_boaddr:   case jit_code_boaddr_u: case jit_code_bxaddr:
1531         case jit_code_bxaddr_u: case jit_code_bosubr:   case jit_code_bosubr_u:
1532         case jit_code_bxsubr:   case jit_code_bxsubr_u:
1533             mask = jit_cc_a0_jmp|jit_cc_a1_reg|jit_cc_a1_chg|jit_cc_a2_reg;
1534             break;
1535         default:
1536             abort();
1537     }
1538
1539     return (mask);
1540 }
1541
1542 void
1543 _jit_patch_abs(jit_state_t *_jit, jit_node_t *instr, jit_pointer_t address)
1544 {
1545     jit_int32_t         mask;
1546
1547     switch (instr->code) {
1548         case jit_code_movi:     case jit_code_ldi_c:    case jit_code_ldi_uc:
1549         case jit_code_ldi_s:    case jit_code_ldi_us:   case jit_code_ldi_i:
1550         case jit_code_ldi_ui:   case jit_code_ldi_l:    case jit_code_ldi_f:
1551         case jit_code_ldi_d:
1552             instr->v.p = address;
1553             break;
1554         case jit_code_sti_c:    case jit_code_sti_s:    case jit_code_sti_i:
1555         case jit_code_sti_l:    case jit_code_sti_f:    case jit_code_sti_d:
1556             instr->u.p = address;
1557             break;
1558         default:
1559             mask = jit_classify(instr->code);
1560             assert((mask & (jit_cc_a0_reg|jit_cc_a0_jmp)) == jit_cc_a0_jmp);
1561             instr->u.p = address;
1562     }
1563 }
1564
1565 void
1566 _jit_patch_at(jit_state_t *_jit, jit_node_t *instr, jit_node_t *label)
1567 {
1568     jit_int32_t         mask;
1569
1570     assert(!(instr->flag & jit_flag_node));
1571     instr->flag |= jit_flag_node;
1572     switch (instr->code) {
1573         case jit_code_movi:
1574             assert(label->code == jit_code_label ||
1575                    label->code == jit_code_data);
1576             instr->v.n = label;
1577             if (label->code == jit_code_data)
1578                 instr->flag |= jit_flag_data;
1579             break;
1580         case jit_code_jmpi:
1581             assert(label->code == jit_code_label ||
1582                    label->code == jit_code_epilog);
1583             instr->u.n = label;
1584             break;
1585         default:
1586             mask = jit_classify(instr->code);
1587             assert((mask & (jit_cc_a0_reg|jit_cc_a0_jmp)) == jit_cc_a0_jmp);
1588             assert(label->code == jit_code_label);
1589             instr->u.n = label;
1590             break;
1591     }
1592     /* link field is used as list of nodes associated with a given label */
1593     instr->link = label->link;
1594     label->link = instr;
1595 }
1596
1597 void
1598 _jit_optimize(jit_state_t *_jit)
1599 {
1600     jit_bool_t           jump;
1601     jit_bool_t           todo;
1602     jit_int32_t          mask;
1603     jit_node_t          *node;
1604     jit_block_t         *block;
1605     jit_word_t           offset;
1606
1607     _jitc->function = NULL;
1608
1609     thread_jumps();
1610     sequential_labels();
1611     split_branches();
1612
1613     /* create initial mapping of live register values
1614      * at the start of a basic block */
1615     for (offset = 0; offset < _jitc->blocks.offset; offset++) {
1616         block = _jitc->blocks.ptr + offset;
1617         if (!block->label)
1618             continue;
1619         if (block->label->code != jit_code_epilog)
1620             jit_setup(block);
1621     }
1622
1623     /* set live state of registers not referenced in a block, but
1624      * referenced in a jump target or normal flow */
1625     do {
1626         todo = 0;
1627         for (offset = 0; offset < _jitc->blocks.offset; offset++) {
1628             block = _jitc->blocks.ptr + offset;
1629             if (!block->label)
1630                 continue;
1631             if (block->label->code != jit_code_epilog)
1632                 jit_follow(block, &todo);
1633         }
1634     } while (todo);
1635
1636     patch_registers();
1637     simplify();
1638
1639     /* figure out labels that are only reached with a jump
1640      * and is required to do a simple redundant_store removal
1641      * on jit_beqi below */
1642     jump = 1;
1643     for (node = _jitc->head; node; node = node->next) {
1644         switch (node->code) {
1645             case jit_code_label:
1646                 if (!jump)
1647                     node->flag |= jit_flag_head;
1648                 break;
1649             case jit_code_jmpi:         case jit_code_jmpr:
1650             case jit_code_epilog:
1651                 jump = 1;
1652                 break;
1653             case jit_code_data:         case jit_code_note:
1654                 break;
1655             default:
1656                 jump = 0;
1657                 break;
1658         }
1659     }
1660
1661     for (node = _jitc->head; node; node = node->next) {
1662         mask = jit_classify(node->code);
1663         if (mask & jit_cc_a0_reg)
1664             node->u.w &= ~jit_regno_patch;
1665         if (mask & jit_cc_a1_reg)
1666             node->v.w &= ~jit_regno_patch;
1667         if (mask & jit_cc_a2_reg)
1668             node->w.w &= ~jit_regno_patch;
1669         switch (node->code) {
1670             case jit_code_prolog:
1671                 _jitc->function = _jitc->functions.ptr + node->w.w;
1672                 break;
1673             case jit_code_epilog:
1674                 _jitc->function = NULL;
1675                 break;
1676             case jit_code_beqi:
1677                 redundant_store(node, 1);
1678                 break;
1679             case jit_code_bnei:
1680                 redundant_store(node, 0);
1681                 break;
1682             default:
1683 #if JIT_HASH_CONSTS
1684                 if (mask & jit_cc_a0_flt) {
1685                     node->u.p = jit_data(&node->u.f, sizeof(jit_float32_t), 4);
1686                     node->flag |= jit_flag_node | jit_flag_data;
1687                 }
1688                 else if (mask & jit_cc_a0_dbl) {
1689                     node->u.p = jit_data(&node->u.d, sizeof(jit_float64_t), 8);
1690                     node->flag |= jit_flag_node | jit_flag_data;
1691                 }
1692                 else if (mask & jit_cc_a1_flt) {
1693                     node->v.p = jit_data(&node->v.f, sizeof(jit_float32_t), 4);
1694                     node->flag |= jit_flag_node | jit_flag_data;
1695                 }
1696                 else if (mask & jit_cc_a1_dbl) {
1697                     node->v.p = jit_data(&node->v.d, sizeof(jit_float64_t), 8);
1698                     node->flag |= jit_flag_node | jit_flag_data;
1699                 }
1700                 else if (mask & jit_cc_a2_flt) {
1701                     node->w.p = jit_data(&node->w.f, sizeof(jit_float32_t), 4);
1702                     node->flag |= jit_flag_node | jit_flag_data;
1703                 }
1704                 else if (mask & jit_cc_a2_dbl) {
1705                     node->w.p = jit_data(&node->w.d, sizeof(jit_float64_t), 8);
1706                     node->flag |= jit_flag_node | jit_flag_data;
1707                 }
1708 #endif
1709                 if (_jitc->function) {
1710                     if ((mask & (jit_cc_a0_reg|jit_cc_a0_chg)) ==
1711                         (jit_cc_a0_reg|jit_cc_a0_chg)) {
1712                         if (mask & jit_cc_a0_rlh) {
1713                             jit_regset_setbit(&_jitc->function->regset,
1714                                               jit_regno(node->u.q.l));
1715                             jit_regset_setbit(&_jitc->function->regset,
1716                                               jit_regno(node->u.q.h));
1717                         }
1718                         else
1719                             jit_regset_setbit(&_jitc->function->regset,
1720                                               jit_regno(node->u.w));
1721                     }
1722                     if ((mask & (jit_cc_a1_reg|jit_cc_a1_chg)) ==
1723                         (jit_cc_a1_reg|jit_cc_a1_chg))
1724                         jit_regset_setbit(&_jitc->function->regset,
1725                                           jit_regno(node->v.w));
1726                     if ((mask & (jit_cc_a2_reg|jit_cc_a2_chg)) ==
1727                         (jit_cc_a2_reg|jit_cc_a2_chg))
1728                         jit_regset_setbit(&_jitc->function->regset,
1729                                           jit_regno(node->w.w));
1730                 }
1731                 break;
1732         }
1733     }
1734 }
1735
1736 void
1737 _jit_reglive(jit_state_t *_jit, jit_node_t *node)
1738 {
1739     jit_int32_t          spec;
1740     jit_int32_t          value;
1741     jit_block_t         *block;
1742
1743     switch (node->code) {
1744         case jit_code_label:    case jit_code_prolog:   case jit_code_epilog:
1745             block = _jitc->blocks.ptr + node->v.w;
1746             jit_regset_set(&_jitc->reglive, &block->reglive);
1747             break;
1748         case jit_code_callr:
1749             value = jit_regno(node->u.w);
1750             if (!(node->u.w & jit_regno_patch)) {
1751                 jit_regset_setbit(&_jitc->reglive, value);
1752             }
1753         case jit_code_calli:
1754             for (value = 0; value < _jitc->reglen; value++) {
1755                 spec = jit_class(_rvs[value].spec);
1756                 if ((spec & jit_class_arg) && jit_regarg_p(node, value))
1757                     jit_regset_setbit(&_jitc->reglive, value);
1758                 else if (!(spec & jit_class_sav))
1759                     jit_regset_clrbit(&_jitc->reglive, value);
1760             }
1761             break;
1762         default:
1763             value = jit_classify(node->code);
1764             if (value & jit_cc_a0_reg) {
1765                 if (value & jit_cc_a0_rlh) {
1766                     if (!(node->u.q.l & jit_regno_patch)) {
1767                         if (value & jit_cc_a0_chg) {
1768                             jit_regset_clrbit(&_jitc->reglive, node->u.q.l);
1769                             jit_regset_setbit(&_jitc->regmask, node->u.q.l);
1770                         }
1771                         else
1772                             jit_regset_setbit(&_jitc->reglive, node->u.q.l);
1773                     }
1774                     if (!(node->u.q.h & jit_regno_patch)) {
1775                         if (value & jit_cc_a0_chg) {
1776                             jit_regset_clrbit(&_jitc->reglive, node->u.q.h);
1777                             jit_regset_setbit(&_jitc->regmask, node->u.q.h);
1778                         }
1779                         else
1780                             jit_regset_setbit(&_jitc->reglive, node->u.q.h);
1781                     }
1782                 }
1783                 else {
1784                     if (!(node->u.w & jit_regno_patch)) {
1785                         if (value & jit_cc_a0_chg) {
1786                             jit_regset_clrbit(&_jitc->reglive, node->u.w);
1787                             jit_regset_setbit(&_jitc->regmask, node->u.w);
1788                         }
1789                         else
1790                             jit_regset_setbit(&_jitc->reglive, node->u.w);
1791                     }
1792                 }
1793             }
1794             if ((value & jit_cc_a1_reg) && !(node->v.w & jit_regno_patch)) {
1795                 if (value & jit_cc_a1_chg) {
1796                     jit_regset_clrbit(&_jitc->reglive, node->v.w);
1797                     jit_regset_setbit(&_jitc->regmask, node->v.w);
1798                 }
1799                 else
1800                     jit_regset_setbit(&_jitc->reglive, node->v.w);
1801             }
1802             if ((value & jit_cc_a2_reg) && !(node->w.w & jit_regno_patch)) {
1803                 if (value & jit_cc_a2_chg) {
1804                     jit_regset_clrbit(&_jitc->reglive, node->w.w);
1805                     jit_regset_setbit(&_jitc->regmask, node->w.w);
1806                 }
1807                 else
1808                     jit_regset_setbit(&_jitc->reglive, node->w.w);
1809             }
1810             if (jit_regset_set_p(&_jitc->regmask)) {
1811                 jit_update(node->next, &_jitc->reglive, &_jitc->regmask);
1812                 if (jit_regset_set_p(&_jitc->regmask)) {
1813                     /* any unresolved live state is considered as live */
1814                     jit_regset_ior(&_jitc->reglive,
1815                                    &_jitc->reglive, &_jitc->regmask);
1816                     jit_regset_set_ui(&_jitc->regmask, 0);
1817                 }
1818             }
1819             break;
1820     }
1821 }
1822
1823 void
1824 _jit_regarg_set(jit_state_t *_jit, jit_node_t *node, jit_int32_t value)
1825 {
1826 #if GET_JIT_SIZE
1827     jit_size_prepare();
1828 #endif
1829     if (value & jit_cc_a0_reg) {
1830         if (value & jit_cc_a0_rlh) {
1831             jit_regset_setbit(&_jitc->regarg, jit_regno(node->u.q.l));
1832             jit_regset_setbit(&_jitc->regarg, jit_regno(node->u.q.h));
1833         }
1834         else
1835             jit_regset_setbit(&_jitc->regarg, jit_regno(node->u.w));
1836     }
1837     if (value & jit_cc_a1_reg)
1838         jit_regset_setbit(&_jitc->regarg, jit_regno(node->v.w));
1839     if (value & jit_cc_a2_reg)
1840         jit_regset_setbit(&_jitc->regarg, jit_regno(node->w.w));
1841 }
1842
1843 void
1844 _jit_regarg_clr(jit_state_t *_jit, jit_node_t *node, jit_int32_t value)
1845 {
1846 #if GET_JIT_SIZE
1847     jit_size_collect(node);
1848 #endif
1849     if (value & jit_cc_a0_reg) {
1850         if (value & jit_cc_a0_rlh) {
1851             jit_regset_clrbit(&_jitc->regarg, jit_regno(node->u.q.l));
1852             jit_regset_clrbit(&_jitc->regarg, jit_regno(node->u.q.h));
1853         }
1854         else
1855             jit_regset_clrbit(&_jitc->regarg, jit_regno(node->u.w));
1856     }
1857     if (value & jit_cc_a1_reg)
1858         jit_regset_clrbit(&_jitc->regarg, jit_regno(node->v.w));
1859     if (value & jit_cc_a2_reg)
1860         jit_regset_clrbit(&_jitc->regarg, jit_regno(node->w.w));
1861 }
1862
1863 void
1864 _jit_realize(jit_state_t *_jit)
1865 {
1866     assert(!_jitc->realize);
1867     if (_jitc->function)
1868         jit_epilog();
1869     jit_optimize();
1870     _jitc->realize = 1;
1871
1872     /* ensure it is aligned */
1873     _jitc->data.offset = (_jitc->data.offset + 7) & -8;
1874
1875 #if GET_JIT_SIZE
1876     /* Heuristic to guess code buffer size */
1877     _jitc->mult = 4;
1878     _jit->code.length = _jitc->pool.length * 1024 * _jitc->mult;
1879 #else
1880     _jit->code.length = jit_get_size();
1881 #endif
1882 }
1883
1884 void
1885 _jit_dataset(jit_state_t *_jit)
1886 {
1887     jit_uint8_t         *ptr;
1888     jit_node_t          *node;
1889     jit_word_t           offset;
1890 #if defined(__sgi)
1891     int                  mmap_fd;
1892 #endif
1893
1894     assert(!_jitc->dataset);
1895     if (!_jit->user_data) {
1896
1897         /* create read only data buffer */
1898         _jit->data.length = (_jitc->data.offset +
1899                              /* reserve space for annotations */
1900                              _jitc->note.size + 4095) & -4096;
1901 #if defined(__sgi)
1902         mmap_fd = open("/dev/zero", O_RDWR);
1903 #endif
1904         _jit->data.ptr = mmap(NULL, _jit->data.length,
1905                               PROT_READ | PROT_WRITE,
1906                               MAP_PRIVATE | MAP_ANON, mmap_fd, 0);
1907         assert(_jit->data.ptr != MAP_FAILED);
1908 #if defined(__sgi)
1909         close(mmap_fd);
1910 #endif
1911     }
1912
1913     if (!_jitc->no_data)
1914         jit_memcpy(_jit->data.ptr, _jitc->data.ptr, _jitc->data.offset);
1915
1916     if (_jitc->no_note) {
1917         /* Space for one note is always allocated, so revert it here
1918          * if after jit_new_state was called, it is also requested to
1919          * not generate annotation information */
1920         _jit->note.length = 0;
1921         _jitc->note.size = 0;
1922     }
1923     else {
1924         _jitc->note.base = _jit->data.ptr;
1925         if (!_jitc->no_data)
1926             _jitc->note.base += _jitc->data.offset;
1927         memset(_jitc->note.base, 0, _jitc->note.size);
1928     }
1929
1930     if (_jit->user_data)
1931         /* Need the temporary hashed data until jit_emit is finished */
1932         ptr = _jitc->no_data ? _jitc->data.ptr : _jit->data.ptr;
1933     else {
1934         ptr = _jit->data.ptr;
1935         /* Temporary hashed data no longer required */
1936         jit_free((jit_pointer_t *)&_jitc->data.ptr);
1937     }
1938
1939     for (offset = 0; offset < _jitc->data.size; offset++) {
1940         for (node = _jitc->data.table[offset]; node; node = node->next) {
1941             node->flag |= jit_flag_patch;
1942             node->u.w = (jit_word_t)(ptr + node->u.w);
1943         }
1944     }
1945
1946     _jitc->dataset = 1;
1947 }
1948
1949 jit_pointer_t
1950 _jit_get_code(jit_state_t *_jit, jit_word_t *length)
1951 {
1952     assert(_jitc->realize);
1953     if (length) {
1954         if (_jitc->done)
1955             /* If code already generated, return exact size of code */
1956             *length = _jit->pc.uc - _jit->code.ptr;
1957         else
1958             /* Else return current size of the code buffer */
1959             *length = _jit->code.length;
1960     }
1961
1962     return (_jit->code.ptr);
1963 }
1964
1965 void
1966 _jit_set_code(jit_state_t *_jit, jit_pointer_t ptr, jit_word_t length)
1967 {
1968     assert(_jitc->realize);
1969     _jit->code.ptr = ptr;
1970     _jit->code.length = length;
1971     _jit->user_code = 1;
1972 }
1973
1974 jit_pointer_t
1975 _jit_get_data(jit_state_t *_jit, jit_word_t *data_size, jit_word_t *note_size)
1976 {
1977     assert(_jitc->realize);
1978     if (data_size)
1979         *data_size = _jitc->data.offset;
1980     if (note_size)
1981         *note_size = _jitc->note.size;
1982     return (_jit->data.ptr);
1983 }
1984
1985 void
1986 _jit_set_data(jit_state_t *_jit, jit_pointer_t ptr,
1987               jit_word_t length, jit_word_t flags)
1988 {
1989     assert(_jitc->realize);
1990     if (flags & JIT_DISABLE_DATA)
1991         _jitc->no_data = 1;
1992     else
1993         assert(length >= _jitc->data.offset);
1994     if (flags & JIT_DISABLE_NOTE)
1995         _jitc->no_note = 1;
1996     else {
1997         if (flags & JIT_DISABLE_DATA)
1998             assert(length >= _jitc->note.size);
1999         else
2000             assert(length >= _jitc->data.offset + _jitc->note.size);
2001     }
2002     _jit->data.ptr = ptr;
2003     _jit->data.length = length;
2004     _jit->user_data = 1;
2005 }
2006
2007 jit_pointer_t
2008 _jit_emit(jit_state_t *_jit)
2009 {
2010     jit_pointer_t        code;
2011     jit_node_t          *node;
2012     size_t               length;
2013     int                  result;
2014 #if defined(__sgi)
2015     int                  mmap_fd;
2016 #endif
2017
2018     if (!_jitc->realize)
2019         jit_realize();
2020
2021     if (!_jitc->dataset)
2022         jit_dataset();
2023
2024     _jitc->emit = 1;
2025
2026     if (!_jit->user_code) {
2027 #if defined(__sgi)
2028         mmap_fd = open("/dev/zero", O_RDWR);
2029 #endif
2030         _jit->code.ptr = mmap(NULL, _jit->code.length,
2031                               PROT_EXEC | PROT_READ | PROT_WRITE,
2032                               MAP_PRIVATE | MAP_ANON, mmap_fd, 0);
2033         assert(_jit->code.ptr != MAP_FAILED);
2034     }
2035     _jitc->code.end = _jit->code.ptr + _jit->code.length -
2036         jit_get_max_instr();
2037     _jit->pc.uc = _jit->code.ptr;
2038
2039     for (;;) {
2040         if ((code = emit_code()) == NULL) {
2041             _jitc->patches.offset = 0;
2042             for (node = _jitc->head; node; node = node->next) {
2043                 if (node->link &&
2044                     (node->code == jit_code_label ||
2045                      node->code == jit_code_epilog))
2046                     node->flag &= ~jit_flag_patch;
2047             }
2048             if (_jit->user_code)
2049                 goto fail;
2050 #if GET_JIT_SIZE
2051             ++_jitc->mult;
2052             length = _jitc->pool.length * 1024 * _jitc->mult;
2053 #else
2054             /* Should only happen on very special cases */
2055             length = _jit->code.length + 4096;
2056 #endif
2057
2058 #if !HAVE_MREMAP
2059             munmap(_jit->code.ptr, _jit->code.length);
2060 #endif
2061
2062 #if HAVE_MREMAP
2063 #  if __NetBSD__
2064             _jit->code.ptr = mremap(_jit->code.ptr, _jit->code.length,
2065                                     _jit->code.ptr, length, 0);
2066 #  else
2067             _jit->code.ptr = mremap(_jit->code.ptr, _jit->code.length,
2068                                     length, MREMAP_MAYMOVE, NULL);
2069 #  endif
2070 #else
2071             _jit->code.ptr = mmap(NULL, length,
2072                                   PROT_EXEC | PROT_READ | PROT_WRITE,
2073                                   MAP_PRIVATE | MAP_ANON, mmap_fd, 0);
2074 #endif
2075
2076             assert(_jit->code.ptr != MAP_FAILED);
2077             _jit->code.length = length;
2078             _jitc->code.end = _jit->code.ptr + _jit->code.length -
2079                 jit_get_max_instr();
2080             _jit->pc.uc = _jit->code.ptr;
2081         }
2082         else
2083             break;
2084     }
2085
2086 #if defined(__sgi)
2087     if (!_jit->user_code)
2088         close(mmap_fd);
2089 #endif
2090
2091     _jitc->done = 1;
2092     if (!_jitc->no_note)
2093         jit_annotate();
2094
2095     if (_jit->user_data)
2096         jit_free((jit_pointer_t *)&_jitc->data.ptr);
2097     else {
2098         result = mprotect(_jit->data.ptr, _jit->data.length, PROT_READ);
2099         assert(result == 0);
2100     }
2101     if (!_jit->user_code) {
2102         result = mprotect(_jit->code.ptr, _jit->code.length,
2103                           PROT_READ | PROT_EXEC);
2104         assert(result == 0);
2105     }
2106
2107     return (_jit->code.ptr);
2108 fail:
2109     return (NULL);
2110 }
2111
2112 void
2113 _jit_frame(jit_state_t *_jit, jit_int32_t frame)
2114 {
2115     jit_trampoline(frame, 1);
2116 }
2117
2118 void
2119 _jit_tramp(jit_state_t *_jit, jit_int32_t frame)
2120 {
2121     jit_trampoline(frame, 0);
2122 }
2123
2124 void
2125 _jit_trampoline(jit_state_t *_jit, jit_int32_t frame, jit_bool_t prolog)
2126 {
2127     jit_int32_t         regno;
2128
2129     /* Must be called after prolog, actually, just to simplify
2130      * tests and know there is a current function and that
2131      * _jitc->function->self.aoff is at the before any alloca value */
2132     assert(_jitc->tail && _jitc->tail->code == jit_code_prolog);
2133
2134     /* + 24 for 3 possible spilled temporaries (that could be a double) */
2135     frame += 24;
2136 #if defined(__hppa__)
2137     frame += _jitc->function->self.aoff;
2138 #else
2139     frame -= _jitc->function->self.aoff;
2140 #endif
2141     _jitc->function->frame = frame;
2142     if (prolog)
2143         _jitc->function->define_frame = 1;
2144     else
2145         _jitc->function->assume_frame = 1;
2146     for (regno = 0; regno < _jitc->reglen; regno++)
2147         if (jit_class(_rvs[regno].spec) & jit_class_sav)
2148             jit_regset_setbit(&_jitc->function->regset, regno);
2149 }
2150
2151 /*   Compute initial reglive and regmask set values of a basic block.
2152  * reglive is the set of known live registers
2153  * regmask is the set of registers not referenced in the block
2154  *   Registers in regmask might be live.
2155  */
2156 static void
2157 _jit_setup(jit_state_t *_jit, jit_block_t *block)
2158 {
2159     jit_node_t          *node;
2160     jit_bool_t           live;
2161     unsigned long        value;
2162
2163     jit_regset_set_mask(&block->regmask, _jitc->reglen);
2164     for (value = 0; value < _jitc->reglen; ++value)
2165         if (!(jit_class(_rvs[value].spec) & (jit_class_gpr|jit_class_fpr)))
2166             jit_regset_clrbit(&block->regmask, value);
2167
2168     for (node = block->label->next; node; node = node->next) {
2169         switch (node->code) {
2170             case jit_code_label:        case jit_code_prolog:
2171             case jit_code_epilog:
2172                 return;
2173             default:
2174                 /* Check argument registers in reverse order to properly
2175                  * handle registers that are both, argument and result */
2176                 value = jit_classify(node->code);
2177                 if ((value & jit_cc_a2_reg) &&
2178                     !(node->w.w & jit_regno_patch) &&
2179                     jit_regset_tstbit(&block->regmask, node->w.w)) {
2180                     live = !(value & jit_cc_a2_chg);
2181                     jit_regset_clrbit(&block->regmask, node->w.w);
2182                     if (live)
2183                         jit_regset_setbit(&block->reglive, node->w.w);
2184                 }
2185                 if ((value & jit_cc_a1_reg) &&
2186                     !(node->v.w & jit_regno_patch) &&
2187                     jit_regset_tstbit(&block->regmask, node->v.w)) {
2188                     live = !(value & jit_cc_a1_chg);
2189                     jit_regset_clrbit(&block->regmask, node->v.w);
2190                     if (live)
2191                         jit_regset_setbit(&block->reglive, node->v.w);
2192                 }
2193                 if (value & jit_cc_a0_reg) {
2194                     live = !(value & jit_cc_a0_chg);
2195                     if (value & jit_cc_a0_rlh) {
2196                         if (!(node->u.q.l & jit_regno_patch) &&
2197                             jit_regset_tstbit(&block->regmask, node->u.q.l)) {
2198                             jit_regset_clrbit(&block->regmask, node->u.q.l);
2199                             if (live)
2200                                 jit_regset_setbit(&block->reglive, node->u.q.l);
2201                         }
2202                         if (!(node->u.q.h & jit_regno_patch) &&
2203                             jit_regset_tstbit(&block->regmask, node->u.q.h)) {
2204                             jit_regset_clrbit(&block->regmask, node->u.q.h);
2205                             if (live)
2206                                 jit_regset_setbit(&block->reglive, node->u.q.h);
2207                         }
2208                     }
2209                     else {
2210                         if (!(node->u.w & jit_regno_patch) &&
2211                             jit_regset_tstbit(&block->regmask, node->u.w)) {
2212                             jit_regset_clrbit(&block->regmask, node->u.w);
2213                             if (live)
2214                                 jit_regset_setbit(&block->reglive, node->u.w);
2215                         }
2216                     }
2217                 }
2218                 break;
2219         }
2220     }
2221 }
2222
2223 /*  Update regmask and reglive of blocks at entry point of branch targets
2224  * or normal flow that have a live register not used in this block.
2225  */
2226 static void
2227 _jit_follow(jit_state_t *_jit, jit_block_t *block, jit_bool_t *todo)
2228 {
2229     jit_node_t          *node;
2230     jit_block_t         *next;
2231     jit_int32_t          spec;
2232     jit_int32_t          regno;
2233     unsigned long        value;
2234     jit_node_t          *label;
2235     jit_regset_t         reglive;
2236     jit_regset_t         regmask;
2237     jit_regset_t         regtemp;
2238
2239     jit_regset_set(&reglive, &block->reglive);
2240     jit_regset_set(&regmask, &block->regmask);
2241     for (node = block->label->next; node; node = node->next) {
2242         switch (node->code) {
2243             case jit_code_label:
2244                 /*  Do not consider jmpi and jmpr cannot jump to the
2245                  * next instruction. */
2246                 next = _jitc->blocks.ptr + node->v.w;
2247                 /*  Set of live registers in next block that are at unknown
2248                  * state in this block. */
2249                 jit_regset_and(&regtemp, &regmask, &next->reglive);
2250                 if (jit_regset_set_p(&regtemp)) {
2251                     /*  Add live state of next block to current block. */
2252                     jit_regset_ior(&block->reglive, &block->reglive, &regtemp);
2253                     /*  Remove from unknown state bitmask. */
2254                     jit_regset_com(&regtemp, &regtemp);
2255                     jit_regset_and(&block->regmask, &block->regmask, &regtemp);
2256                     *todo = 1;
2257                 }
2258             case jit_code_prolog:
2259             case jit_code_epilog:
2260                 return;
2261             case jit_code_callr:
2262                 value = jit_regno(node->u.w);
2263                 if (!(node->u.w & jit_regno_patch)) {
2264                     if (jit_regset_tstbit(&regmask, value)) {
2265                         jit_regset_clrbit(&regmask, value);
2266                         jit_regset_setbit(&reglive, value);
2267                     }
2268                 }
2269             case jit_code_calli:
2270                 for (value = 0; value < _jitc->reglen; ++value) {
2271                     value = jit_regset_scan1(&regmask, value);
2272                     if (value >= _jitc->reglen)
2273                         break;
2274                     spec = jit_class(_rvs[value].spec);
2275                     if (!(spec & jit_class_sav))
2276                         jit_regset_clrbit(&regmask, value);
2277                     if ((spec & jit_class_arg) && jit_regarg_p(node, value))
2278                         jit_regset_setbit(&reglive, value);
2279                 }
2280                 break;
2281             default:
2282                 value = jit_classify(node->code);
2283                 if (value & jit_cc_a2_reg) {
2284                     if (!(node->w.w & jit_regno_patch)) {
2285                         if (jit_regset_tstbit(&regmask, node->w.w)) {
2286                             jit_regset_clrbit(&regmask, node->w.w);
2287                             if (!(value & jit_cc_a2_chg))
2288                                 jit_regset_setbit(&reglive, node->w.w);
2289                         }
2290                     }
2291                 }
2292                 if (value & jit_cc_a1_reg) {
2293                     if (!(node->v.w & jit_regno_patch)) {
2294                         if (jit_regset_tstbit(&regmask, node->v.w)) {
2295                             jit_regset_clrbit(&regmask, node->v.w);
2296                             if (!(value & jit_cc_a1_chg))
2297                                 jit_regset_setbit(&reglive, node->v.w);
2298                         }
2299                     }
2300                 }
2301                 if (value & jit_cc_a0_reg) {
2302                     if (value & jit_cc_a0_rlh) {
2303                         if (!(node->u.q.l & jit_regno_patch)) {
2304                             if (jit_regset_tstbit(&regmask, node->u.q.l)) {
2305                                 jit_regset_clrbit(&regmask, node->u.q.l);
2306                                 if (!(value & jit_cc_a0_chg))
2307                                     jit_regset_setbit(&reglive, node->u.q.l);
2308                             }
2309                         }
2310                         if (!(node->u.q.h & jit_regno_patch)) {
2311                             if (jit_regset_tstbit(&regmask, node->u.q.h)) {
2312                                 jit_regset_clrbit(&regmask, node->u.q.h);
2313                                 if (!(value & jit_cc_a0_chg))
2314                                     jit_regset_setbit(&reglive, node->u.q.h);
2315                             }
2316                         }
2317                     }
2318                     else {
2319                         if (!(node->u.w & jit_regno_patch)) {
2320                             if (jit_regset_tstbit(&regmask, node->u.w)) {
2321                                 jit_regset_clrbit(&regmask, node->u.w);
2322                                 if (!(value & jit_cc_a0_chg))
2323                                     jit_regset_setbit(&reglive, node->u.w);
2324                             }
2325                         }
2326                     }
2327                 }
2328                 if (value & jit_cc_a0_jmp) {
2329                     if (node->flag & jit_flag_node) {
2330                         label = node->u.n;
2331                         /*  Do not consider jmpi and jmpr cannot jump to the
2332                          * next instruction. */
2333                         next = _jitc->blocks.ptr + label->v.w;
2334                         jit_regset_and(&regtemp, &regmask, &next->reglive);
2335                         if (jit_regset_set_p(&regtemp)) {
2336                             /* Add live state. */
2337                             jit_regset_ior(&block->reglive,
2338                                            &block->reglive, &regtemp);
2339                             /*  Remove from unknown state bitmask. */
2340                             jit_regset_com(&regtemp, &regtemp);
2341                             jit_regset_and(&block->regmask,
2342                                            &block->regmask, &regtemp);
2343                             *todo = 1;
2344                         }
2345                     }
2346                     else {
2347                         /*   Jump to unknown location.
2348                          *   This is a pitfall of the implementation.
2349                          *   Only jmpi to not a jit code should reach here,
2350                          * or a jmpr of a computed address.
2351                          *   Because the implementation needs jit_class_nospill
2352                          * registers, must treat jmpr as a function call. This
2353                          * means that only JIT_Vn registers can be trusted on
2354                          * arrival of jmpr.
2355                          */
2356                         for (regno = 0; regno < _jitc->reglen; regno++) {
2357                             spec = jit_class(_rvs[regno].spec);
2358                             if (jit_regset_tstbit(&regmask, regno) &&
2359                                 (spec & (jit_class_gpr|jit_class_fpr)) &&
2360                                 !(spec & jit_class_sav))
2361                                 jit_regset_clrbit(&regmask, regno);
2362                         }
2363                         /*   Assume non callee save registers are live due
2364                          * to jump to unknown location. */
2365                         /* Treat all callee save as live. */
2366                         jit_regset_ior(&reglive, &reglive, &regmask);
2367                         /* Treat anything else as dead. */
2368                         jit_regset_set_ui(&regmask, 0);
2369                     }
2370                 }
2371                 break;
2372         }
2373     }
2374 }
2375
2376 /*  Follow code generation up to finding a label or end of code.
2377  *  When finding a label, update the set of live registers.
2378  *  On branches, update based on taken branch or normal flow.
2379  */
2380 static void
2381 _jit_update(jit_state_t *_jit, jit_node_t *node,
2382             jit_regset_t *live, jit_regset_t *mask)
2383 {
2384     jit_int32_t          spec;
2385     jit_int32_t          regno;
2386     unsigned long        value;
2387     jit_block_t         *block;
2388     jit_node_t          *label;
2389     jit_regset_t         regtemp;
2390
2391     for (; node; node = node->next) {
2392         if (jit_regset_set_p(mask) == 0)
2393             break;
2394         switch (node->code) {
2395             case jit_code_label:
2396                 block = _jitc->blocks.ptr + node->v.w;
2397                 jit_regset_and(&regtemp, mask, &block->reglive);
2398                 if (jit_regset_set_p(&regtemp)) {
2399                     /* Add live state. */
2400                     jit_regset_ior(live, live, &regtemp);
2401                     /*  Remove from unknown state bitmask. */
2402                     jit_regset_com(&regtemp, &regtemp);
2403                     jit_regset_and(mask, mask, &regtemp);
2404                 }
2405                 return;
2406             case jit_code_prolog:
2407                 jit_regset_set_ui(mask, 0);
2408                 return;
2409             case jit_code_epilog:
2410                 jit_regset_set_ui(mask, 0);
2411                 return;
2412             case jit_code_callr:
2413                 value = jit_regno(node->u.w);
2414                 if (!(node->u.w & jit_regno_patch)) {
2415                     if (jit_regset_tstbit(mask, value)) {
2416                         jit_regset_clrbit(mask, value);
2417                         jit_regset_setbit(live, value);
2418                     }
2419                 }
2420             case jit_code_calli:
2421                 for (value = 0; value < _jitc->reglen; ++value) {
2422                     value = jit_regset_scan1(mask, value);
2423                     if (value >= _jitc->reglen)
2424                         break;
2425                     spec = jit_class(_rvs[value].spec);
2426                     if (!(spec & jit_class_sav))
2427                         jit_regset_clrbit(mask, value);
2428                     if ((spec & jit_class_arg) && jit_regarg_p(node, value))
2429                         jit_regset_setbit(live, value);
2430                 }
2431                 break;
2432             default:
2433                 value = jit_classify(node->code);
2434                 if (value & jit_cc_a2_reg) {
2435                     if (!(node->w.w & jit_regno_patch)) {
2436                         if (jit_regset_tstbit(mask, node->w.w)) {
2437                             jit_regset_clrbit(mask, node->w.w);
2438                             if (!(value & jit_cc_a2_chg))
2439                                 jit_regset_setbit(live, node->w.w);
2440                         }
2441                     }
2442                 }
2443                 if (value & jit_cc_a1_reg) {
2444                     if (!(node->v.w & jit_regno_patch)) {
2445                         if (jit_regset_tstbit(mask, node->v.w)) {
2446                             jit_regset_clrbit(mask, node->v.w);
2447                             if (!(value & jit_cc_a1_chg))
2448                                 jit_regset_setbit(live, node->v.w);
2449                         }
2450                     }
2451                 }
2452                 if (value & jit_cc_a0_reg) {
2453                     if (value & jit_cc_a0_rlh) {
2454                         if (!(node->u.q.l & jit_regno_patch)) {
2455                             if (jit_regset_tstbit(mask, node->u.q.l)) {
2456                                 jit_regset_clrbit(mask, node->u.q.l);
2457                                 if (!(value & jit_cc_a0_chg))
2458                                     jit_regset_setbit(live, node->u.q.l);
2459                             }
2460                         }
2461                         if (!(node->u.q.h & jit_regno_patch)) {
2462                             if (jit_regset_tstbit(mask, node->u.q.h)) {
2463                                 jit_regset_clrbit(mask, node->u.q.h);
2464                                 if (!(value & jit_cc_a0_chg))
2465                                     jit_regset_setbit(live, node->u.q.h);
2466                             }
2467                         }
2468                     }
2469                     else {
2470                         if (!(node->u.w & jit_regno_patch)) {
2471                             if (jit_regset_tstbit(mask, node->u.w)) {
2472                                 jit_regset_clrbit(mask, node->u.w);
2473                                 if (!(value & jit_cc_a0_chg))
2474                                     jit_regset_setbit(live, node->u.w);
2475                             }
2476                         }
2477                     }
2478                 }
2479                 if (value & jit_cc_a0_jmp) {
2480                     if (node->flag & jit_flag_node) {
2481                         label = node->u.n;
2482                         /*  Do not consider jmpi and jmpr cannot jump to the
2483                          * next instruction. */
2484                         block = _jitc->blocks.ptr + label->v.w;
2485                         jit_regset_and(&regtemp, mask, &block->reglive);
2486                         if (jit_regset_set_p(&regtemp)) {
2487                             /* Add live state. */
2488                             jit_regset_ior(live, live, &regtemp);
2489                             /*  Remove from unknown state bitmask. */
2490                             jit_regset_com(&regtemp, &regtemp);
2491                             jit_regset_and(mask, mask, &regtemp);
2492                         }
2493                     }
2494                     else {
2495                         /*   Jump to unknown location.
2496                          *   This is a pitfall of the implementation.
2497                          *   Only jmpi to not a jit code should reach here,
2498                          * or a jmpr of a computed address.
2499                          *   Because the implementation needs jit_class_nospill
2500                          * registers, must treat jmpr as a function call. This
2501                          * means that only JIT_Vn registers can be trusted on
2502                          * arrival of jmpr.
2503                          */
2504                         for (regno = 0; regno < _jitc->reglen; regno++) {
2505                             spec = jit_class(_rvs[regno].spec);
2506                             if (jit_regset_tstbit(mask, regno) &&
2507                                 (spec & (jit_class_gpr|jit_class_fpr)) &&
2508                                 !(spec & jit_class_sav))
2509                                 jit_regset_clrbit(mask, regno);
2510                         }
2511                         /*   Assume non callee save registers are live due
2512                          * to jump to unknown location. */
2513                         /* Treat all callee save as live. */
2514                         jit_regset_ior(live, live, mask);
2515                         /* Treat anything else as dead. */
2516                         jit_regset_set_ui(mask, 0);
2517                     }
2518                 }
2519                 break;
2520         }
2521     }
2522 }
2523
2524 static void
2525 _thread_jumps(jit_state_t *_jit)
2526 {
2527     jit_node_t          *prev;
2528     jit_node_t          *node;
2529     jit_node_t          *next;
2530     jit_int32_t          mask;
2531
2532     for (prev = node = _jitc->head; node;) {
2533         next = node->next;
2534         switch (node->code) {
2535             case jit_code_jmpi:
2536                 if (redundant_jump(prev, node)) {
2537                     node = prev;
2538                     continue;
2539                 }
2540                 if (shortcut_jump(prev, node))
2541                     continue;
2542                 break;
2543             case jit_code_jmpr:
2544             case jit_code_callr:        case jit_code_calli:
2545                 /* non optimizable jump like code */
2546                 break;
2547             default:
2548                 mask = jit_classify(node->code);
2549                 if (mask & jit_cc_a0_jmp) {
2550                     if (reverse_jump(prev, node) ||
2551                         shortcut_jump(prev, node))
2552                         continue;
2553                 }
2554                 break;
2555         }
2556         prev = node;
2557         node = next;
2558     }
2559 }
2560
2561 static void
2562 _sequential_labels(jit_state_t *_jit)
2563 {
2564     jit_node_t          *jump;
2565     jit_node_t          *link;
2566     jit_node_t          *prev;
2567     jit_node_t          *next;
2568     jit_node_t          *node;
2569
2570     for (prev = node = _jitc->head; node; node = next) {
2571         next = node->next;
2572         if (node->code == jit_code_label) {
2573             if (!node->flag) {
2574                 if (!node->link) {
2575                     del_label(prev, node);
2576                     continue;
2577                 }
2578                 if (prev != node && prev->code == jit_code_label) {
2579                     if ((jump = node->link)) {
2580                         for (; jump; jump = link) {
2581                             link = jump->link;
2582                             jump->u.n = prev;
2583                             jump->link = prev->link;
2584                             prev->link = jump;
2585                         }
2586                         node->link = NULL;
2587                     }
2588                     del_label(prev, node);
2589                     continue;
2590                 }
2591             }
2592             if (next && next->code == jit_code_label && !next->flag) {
2593                 if ((jump = next->link)) {
2594                     for (; jump; jump = link) {
2595                         link = jump->link;
2596                         jump->u.n = node;
2597                         jump->link = node->link;
2598                         node->link = jump;
2599                     }
2600                     next->link = NULL;
2601                 }
2602                 del_label(node, next);
2603                 next = node->next;
2604                 continue;
2605             }
2606         }
2607         prev = node;
2608     }
2609 }
2610
2611 static void
2612 _split_branches(jit_state_t *_jit)
2613 {
2614     jit_node_t          *node;
2615     jit_node_t          *next;
2616     jit_node_t          *label;
2617     jit_block_t         *block;
2618
2619     for (node = _jitc->head; node; node = next) {
2620         if ((next = node->next)) {
2621             if (next->code == jit_code_label ||
2622                 next->code == jit_code_prolog ||
2623                 next->code == jit_code_epilog)
2624                 continue;
2625             /* split block on branches */
2626             if (jit_classify(node->code) & jit_cc_a0_jmp) {
2627                 label = new_node(jit_code_label);
2628                 label->next = next;
2629                 node->next = label;
2630                 if (_jitc->blocks.offset >= _jitc->blocks.length) {
2631                     jit_word_t    length;
2632
2633                     length = _jitc->blocks.length + 16;
2634                     jit_realloc((jit_pointer_t *)&_jitc->blocks.ptr,
2635                                 _jitc->blocks.length * sizeof(jit_block_t),
2636                                 length * sizeof(jit_block_t));
2637                     _jitc->blocks.length = length;
2638                 }
2639                 block = _jitc->blocks.ptr + _jitc->blocks.offset;
2640                 block->label = label;
2641                 label->v.w = _jitc->blocks.offset;
2642                 jit_regset_new(&block->reglive);
2643                 jit_regset_new(&block->regmask);
2644                 ++_jitc->blocks.offset;
2645             }
2646         }
2647     }
2648 }
2649
2650 static jit_bool_t
2651 _shortcut_jump(jit_state_t *_jit, jit_node_t *prev, jit_node_t *node)
2652 {
2653     jit_bool_t           cond;
2654     jit_node_t          *jump;
2655     jit_node_t          *next;
2656     jit_node_t          *temp;
2657
2658     if (!(node->flag & jit_flag_node))
2659         return (0);
2660     assert(node->code != jit_code_jmpr);
2661     cond = node->code != jit_code_jmpi;
2662     jump = node->u.n;
2663     for (next = jump->next; next; next = next->next) {
2664         switch (next->code) {
2665             case jit_code_jmpi:
2666                 if (!(next->flag & jit_flag_node))
2667                     return (0);
2668                 if (jump->link == node)
2669                     jump->link = node->link;
2670                 else {
2671                     for (temp = jump->link;
2672                          temp->link != node;
2673                          temp = temp->link)
2674                         assert(temp != NULL);
2675                     temp->link = node->link;
2676                 }
2677                 jump = next->u.n;
2678                 node->u.n = jump;
2679                 node->link = jump->link;
2680                 jump->link = node;
2681                 return (1);
2682             case jit_code_jmpr:
2683                 if (cond)
2684                     return (0);
2685                 node->code = jit_code_jmpr;
2686                 node->u.w = next->u.w;
2687                 node->link = NULL;
2688                 node->flag &= ~jit_flag_node;
2689                 return (1);
2690             case jit_code_note:         case jit_code_label:
2691                 break;
2692             default:
2693                 return (0);
2694         }
2695     }
2696     return (0);
2697 }
2698
2699 static jit_bool_t
2700 _redundant_jump(jit_state_t *_jit, jit_node_t *prev, jit_node_t *node)
2701 {
2702     jit_node_t          *local_prev;
2703     jit_node_t          *local_next;
2704
2705     if (!(node->flag & jit_flag_node))
2706         return (0);
2707     for (local_prev = node, local_next = node->next;
2708          local_next;
2709          local_prev = local_next, local_next = local_next->next) {
2710
2711         switch (local_next->code) {
2712             case jit_code_label:        case jit_code_epilog:
2713                 if (node->u.n == local_next) {
2714                     if (local_next->link == node)
2715                         local_next->link = node->link;
2716                     else {
2717                         for (local_prev = local_next->link;
2718                              local_prev->link != node;
2719                              local_prev = local_prev->link)
2720                             assert(local_prev != NULL);
2721                         local_prev->link = node->link;
2722                     }
2723                     del_node(prev, node);
2724                     return (1);
2725                 }
2726                 break;
2727             case jit_code_name:         case jit_code_note:
2728             case jit_code_align:
2729                 break;
2730             default:
2731                 return (0);
2732         }
2733     }
2734     return (0);
2735 }
2736
2737 static jit_code_t
2738 reverse_jump_code(jit_code_t code)
2739 {
2740     switch (code) {
2741         case jit_code_bltr:     return (jit_code_bger);
2742         case jit_code_blti:     return (jit_code_bgei);
2743         case jit_code_bltr_u:   return (jit_code_bger_u);
2744         case jit_code_blti_u:   return (jit_code_bgei_u);
2745         case jit_code_bler:     return (jit_code_bgtr);
2746         case jit_code_blei:     return (jit_code_bgti);
2747         case jit_code_bler_u:   return (jit_code_bgtr_u);
2748         case jit_code_blei_u:   return (jit_code_bgti_u);
2749         case jit_code_beqr:     return (jit_code_bner);
2750         case jit_code_beqi:     return (jit_code_bnei);
2751         case jit_code_bger:     return (jit_code_bltr);
2752         case jit_code_bgei:     return (jit_code_blti);
2753         case jit_code_bger_u:   return (jit_code_bltr_u);
2754         case jit_code_bgei_u:   return (jit_code_blti_u);
2755         case jit_code_bgtr:     return (jit_code_bler);
2756         case jit_code_bgti:     return (jit_code_blei);
2757         case jit_code_bgtr_u:   return (jit_code_bler_u);
2758         case jit_code_bgti_u:   return (jit_code_blei_u);
2759         case jit_code_bner:     return (jit_code_beqr);
2760         case jit_code_bnei:     return (jit_code_beqi);
2761         case jit_code_bmsr:     return (jit_code_bmcr);
2762         case jit_code_bmsi:     return (jit_code_bmci);
2763         case jit_code_bmcr:     return (jit_code_bmsr);
2764         case jit_code_bmci:     return (jit_code_bmsi);
2765         case jit_code_bltr_f:   return (jit_code_bunger_f);
2766         case jit_code_blti_f:   return (jit_code_bungei_f);
2767         case jit_code_bler_f:   return (jit_code_bungtr_f);
2768         case jit_code_blei_f:   return (jit_code_bungti_f);
2769
2770         case jit_code_beqr_f:   return (jit_code_bner_f);
2771         case jit_code_beqi_f:   return (jit_code_bnei_f);
2772
2773         case jit_code_bger_f:   return (jit_code_bunltr_f);
2774         case jit_code_bgei_f:   return (jit_code_bunlti_f);
2775         case jit_code_bgtr_f:   return (jit_code_bunler_f);
2776         case jit_code_bgti_f:   return (jit_code_bunlei_f);
2777
2778         case jit_code_bner_f:   return (jit_code_beqr_f);
2779         case jit_code_bnei_f:   return (jit_code_beqr_f);
2780
2781         case jit_code_bunltr_f: return (jit_code_bger_f);
2782         case jit_code_bunlti_f: return (jit_code_bgei_f);
2783         case jit_code_bunler_f: return (jit_code_bgtr_f);
2784         case jit_code_bunlei_f: return (jit_code_bgti_f);
2785
2786         case jit_code_buneqr_f: return (jit_code_bltgtr_f);
2787         case jit_code_buneqi_f: return (jit_code_bltgti_f);
2788
2789         case jit_code_bunger_f: return (jit_code_bltr_f);
2790         case jit_code_bungei_f: return (jit_code_blti_f);
2791         case jit_code_bungtr_f: return (jit_code_bler_f);
2792         case jit_code_bungti_f: return (jit_code_blei_f);
2793
2794         case jit_code_bltgtr_f: return (jit_code_buneqr_f);
2795         case jit_code_bltgti_f: return (jit_code_buneqi_f);
2796
2797         case jit_code_bordr_f:  return (jit_code_bunordr_f);
2798         case jit_code_bordi_f:  return (jit_code_bunordi_f);
2799         case jit_code_bunordr_f:return (jit_code_bordr_f);
2800         case jit_code_bunordi_f:return (jit_code_bordi_f);
2801         case jit_code_bltr_d:   return (jit_code_bunger_d);
2802         case jit_code_blti_d:   return (jit_code_bungei_d);
2803         case jit_code_bler_d:   return (jit_code_bungtr_d);
2804         case jit_code_blei_d:   return (jit_code_bungti_d);
2805
2806         case jit_code_beqr_d:   return (jit_code_bner_d);
2807         case jit_code_beqi_d:   return (jit_code_bnei_d);
2808
2809         case jit_code_bger_d:   return (jit_code_bunltr_d);
2810         case jit_code_bgei_d:   return (jit_code_bunlti_d);
2811         case jit_code_bgtr_d:   return (jit_code_bunler_d);
2812         case jit_code_bgti_d:   return (jit_code_bunlei_d);
2813
2814         case jit_code_bner_d:   return (jit_code_beqr_d);
2815         case jit_code_bnei_d:   return (jit_code_beqi_d);
2816
2817         case jit_code_bunltr_d: return (jit_code_bger_d);
2818         case jit_code_bunlti_d: return (jit_code_bgei_d);
2819         case jit_code_bunler_d: return (jit_code_bgtr_d);
2820         case jit_code_bunlei_d: return (jit_code_bgti_d);
2821
2822         case jit_code_buneqr_d: return (jit_code_bltgtr_d);
2823         case jit_code_buneqi_d: return (jit_code_bltgti_d);
2824
2825         case jit_code_bunger_d: return (jit_code_bltr_d);
2826         case jit_code_bungei_d: return (jit_code_blti_d);
2827         case jit_code_bungtr_d: return (jit_code_bler_d);
2828         case jit_code_bungti_d: return (jit_code_blei_d);
2829
2830         case jit_code_bltgtr_d: return (jit_code_buneqr_d);
2831         case jit_code_bltgti_d: return (jit_code_buneqi_d);
2832
2833         case jit_code_bordr_d:  return (jit_code_bunordr_d);
2834         case jit_code_bordi_d:  return (jit_code_bunordi_d);
2835         case jit_code_bunordr_d:return (jit_code_bordr_d);
2836         case jit_code_bunordi_d:return (jit_code_bordi_d);
2837         case jit_code_boaddr:   return (jit_code_bxaddr);
2838         case jit_code_boaddi:   return (jit_code_bxaddi);
2839         case jit_code_boaddr_u: return (jit_code_bxaddr_u);
2840         case jit_code_boaddi_u: return (jit_code_bxaddi_u);
2841         case jit_code_bxaddr:   return (jit_code_boaddr);
2842         case jit_code_bxaddi:   return (jit_code_boaddi);
2843         case jit_code_bxaddr_u: return (jit_code_boaddr_u);
2844         case jit_code_bxaddi_u: return (jit_code_boaddi_u);
2845         case jit_code_bosubr:   return (jit_code_bxsubr);
2846         case jit_code_bosubi:   return (jit_code_bxsubi);
2847         case jit_code_bosubr_u: return (jit_code_bxsubr_u);
2848         case jit_code_bosubi_u: return (jit_code_bxsubi_u);
2849         case jit_code_bxsubr:   return (jit_code_bosubr);
2850         case jit_code_bxsubi:   return (jit_code_bosubi);
2851         case jit_code_bxsubr_u: return (jit_code_bosubr_u);
2852         case jit_code_bxsubi_u: return (jit_code_bosubi_u);
2853         default:                abort();        /* invalid jump code */
2854     }
2855 }
2856
2857 /*
2858  * change common pattern:
2859  *      <cond_jump L0> <jump L1> <label L0>
2860  * into
2861  *      <reverse_cond_jump L1>
2862  */
2863 static jit_bool_t
2864 _reverse_jump(jit_state_t *_jit, jit_node_t *prev, jit_node_t *node)
2865 {
2866     jit_node_t          *local_prev;
2867     jit_node_t          *local_next;
2868     jit_node_t          *local_jump;
2869
2870     if (!(node->flag & jit_flag_node))
2871         return (0);
2872     /* =><cond_jump L0> <jump L1> <label L0> */
2873     local_next = node->next;
2874     if (local_next->code != jit_code_jmpi ||
2875         !(local_next->flag & jit_flag_node))
2876         return (0);
2877     /* <cond_jump L0> =><jump L1> <label L0> */
2878
2879     local_jump = local_next->u.n;
2880     for (local_prev = local_next, local_next = local_next->next;
2881          local_next;
2882          local_prev = local_next, local_next = local_next->next) {
2883         switch (local_next->code) {
2884             case jit_code_label:        case jit_code_epilog:
2885                 if (node->u.n == local_next) {
2886                     if (local_next->link == node)
2887                         local_next->link = node->link;
2888                     else {
2889                         for (local_prev = local_next->link;
2890                              local_prev->link != node;
2891                              local_prev = local_prev->link)
2892                             assert(local_prev != NULL);
2893                         local_prev->link = node->link;
2894                     }
2895                     del_node(node, node->next);
2896                     node->code = reverse_jump_code(node->code);
2897                     node->u.n = local_jump;
2898                     node->link = local_jump->link;
2899                     local_jump->link = node;
2900                     return (1);
2901                 }
2902                 break;
2903             case jit_code_note:
2904                 break;
2905             default:
2906                 return (0);
2907         }
2908     }
2909     return (0);
2910 }
2911
2912 static void
2913 _redundant_store(jit_state_t *_jit, jit_node_t *node, jit_bool_t jump)
2914 {
2915     jit_node_t          *iter;
2916     jit_node_t          *prev;
2917     jit_word_t           word;
2918     jit_int32_t          spec;
2919     jit_int32_t          regno;
2920
2921     if (jump) {
2922         prev = node->u.n;
2923         if (prev->code == jit_code_epilog)
2924             return;
2925         assert(prev->code == jit_code_label);
2926         if ((prev->flag & jit_flag_head) || node->link || prev->link != node)
2927             /* multiple sources */
2928             return;
2929         /* if there are sequential labels it will return below */
2930     }
2931     else
2932         prev = node;
2933     word = node->w.w;
2934     regno = jit_regno(node->v.w);
2935     for (iter = prev->next; iter; prev = iter, iter = iter->next) {
2936         switch (iter->code) {
2937             case jit_code_label:        case jit_code_prolog:
2938             case jit_code_epilog:
2939                 return;
2940             case jit_code_movi:
2941                 if (regno == jit_regno(iter->u.w)) {
2942                     if (iter->flag || iter->v.w != word)
2943                         return;
2944                     del_node(prev, iter);
2945                     iter = prev;
2946                 }
2947                 break;
2948             default:
2949                 spec = jit_classify(iter->code);
2950                 if (spec & jit_cc_a0_jmp)
2951                     return;
2952                 if ((spec & (jit_cc_a0_reg|jit_cc_a0_chg)) ==
2953                     (jit_cc_a0_reg|jit_cc_a0_chg)) {
2954                     if (spec & jit_cc_a0_rlh) {
2955                         if (regno == jit_regno(iter->u.q.l) ||
2956                             regno == jit_regno(iter->u.q.h))
2957                             return;
2958                     }
2959                     else {
2960                         if (regno == jit_regno(iter->u.w))
2961                             return;
2962                     }
2963                 }
2964                 if ((spec & (jit_cc_a1_reg|jit_cc_a1_chg)) ==
2965                     (jit_cc_a1_reg|jit_cc_a1_chg)) {
2966                     if (regno == jit_regno(iter->v.w))
2967                         return;
2968                 }
2969                 if ((spec & (jit_cc_a2_reg|jit_cc_a2_chg)) ==
2970                     (jit_cc_a2_reg|jit_cc_a2_chg)) {
2971                     if (regno == jit_regno(iter->w.w))
2972                         return;
2973                 }
2974                 break;
2975         }
2976     }
2977 }
2978
2979 static jit_bool_t
2980 _simplify_movr(jit_state_t *_jit, jit_node_t *prev, jit_node_t *node,
2981                jit_int32_t kind, jit_int32_t size)
2982 {
2983     jit_int32_t          regno;
2984     jit_int32_t          right;
2985     jit_value_t         *value;
2986
2987     regno = jit_regno(node->u.w);
2988     right = jit_regno(node->v.w);
2989     value = _jitc->values + regno;
2990     if ((value->kind == jit_kind_register &&
2991          jit_regno(value->base.q.l) == right &&
2992          value->base.q.h == _jitc->gen[right]) ||
2993         (value->kind == kind && _jitc->values[right].kind == kind &&
2994          memcmp(&value->base.w, &_jitc->values[right].base.w, size) == 0)) {
2995         del_node(prev, node);
2996         return (1);
2997     }
2998     if (_jitc->values[right].kind == jit_kind_word)
2999         jit_memcpy(value, _jitc->values + right, sizeof(jit_value_t));
3000     else {
3001         value->kind = jit_kind_register;
3002         value->base.q.l = right;
3003         value->base.q.h = _jitc->gen[right];
3004     }
3005     ++_jitc->gen[regno];
3006
3007     return (0);
3008 }
3009
3010 static jit_bool_t
3011 _simplify_movi(jit_state_t *_jit, jit_node_t *prev, jit_node_t *node,
3012                jit_int32_t kind, jit_int32_t size)
3013 {
3014     jit_value_t         *value;
3015     jit_int32_t          spec;
3016     jit_int32_t          regno;
3017     jit_int32_t          offset;
3018
3019     regno = jit_regno(node->u.w);
3020     value = _jitc->values + regno;
3021     if (node->flag & jit_flag_node) {
3022         /* set to undefined if value will be patched */
3023         value->kind = 0;
3024         ++_jitc->gen[regno];
3025         return (0);
3026     }
3027     if (value->kind == kind) {
3028         if (memcmp(&node->v.w, &value->base.w, size) == 0) {
3029             del_node(prev, node);
3030             return (1);
3031         }
3032         spec = jit_class(_rvs[regno].spec);
3033         if (kind == jit_kind_word)
3034             spec &= jit_class_gpr;
3035         else
3036             spec &= (jit_class_xpr | jit_class_fpr);
3037         for (offset = 0; offset < _jitc->reglen; offset++) {
3038             if (_jitc->values[offset].kind == kind &&
3039                 memcmp(&node->v.w, &_jitc->values[offset].base.w, size) == 0 &&
3040                 (jit_class(_rvs[offset].spec) & spec) == spec) {
3041                 if (kind == jit_kind_word)
3042                     node->code = jit_code_movr;
3043                 else if (kind == jit_kind_float32)
3044                     node->code = jit_code_movr_f;
3045                 else
3046                     node->code = jit_code_movr_d;
3047                 node->v.w = offset;
3048                 jit_memcpy(value, _jitc->values + offset, sizeof(jit_value_t));
3049                 ++_jitc->gen[regno];
3050                 return (0);
3051             }
3052         }
3053     }
3054     value->kind = kind;
3055     jit_memcpy(&value->base.w, &node->v.w, size);
3056     ++_jitc->gen[regno];
3057
3058     return (0);
3059 }
3060
3061 /* simple/safe redundandy test not checking if another register
3062  * holds the same value
3063  */
3064 static jit_bool_t
3065 _simplify_ldxi(jit_state_t *_jit, jit_node_t *prev, jit_node_t *node)
3066 {
3067     jit_value_t         *value;
3068     jit_int32_t          regno;
3069     jit_int32_t          right;
3070
3071     regno = jit_regno(node->u.w);
3072     right = jit_regno(node->v.w);
3073     value = _jitc->values + regno;
3074     if (regno != right &&
3075         value->kind == jit_kind_code && value->code == node->code &&
3076         value->base.q.l == right && value->base.q.h == _jitc->gen[right] &&
3077         node->w.w == value->disp.w) {
3078         del_node(prev, node);
3079         return (1);
3080     }
3081     value->kind = jit_kind_code;
3082     value->code = node->code;
3083     value->base.q.l = right;
3084     value->base.q.h = _jitc->gen[right];
3085     value->disp.w = node->w.w;
3086     ++_jitc->gen[regno];
3087
3088     return (0);
3089 }
3090
3091 static jit_bool_t
3092 _simplify_stxi(jit_state_t *_jit, jit_node_t *prev, jit_node_t *node)
3093 {
3094     jit_value_t         *value;
3095     jit_int32_t          regno;
3096     jit_int32_t          right;
3097     jit_int32_t          offset;
3098
3099     regno = jit_regno(node->w.w);
3100     right = jit_regno(node->v.w);
3101     value = _jitc->values + regno;
3102
3103     /* check for redundant store after load */
3104     if (regno != right &&
3105         value->kind == jit_kind_code && value->code == node->code &&
3106         value->base.q.l == right && value->base.q.h == _jitc->gen[right] &&
3107         node->u.w == value->disp.w) {
3108         del_node(prev, node);
3109         return (1);
3110     }
3111
3112     /* assume anything can alias, and invalidate tracked values */
3113     for (offset = 0; offset < _jitc->reglen; offset++) {
3114         if (_jitc->values[offset].kind == jit_kind_code) {
3115             _jitc->values[offset].kind = 0;
3116             ++_jitc->gen[offset];
3117         }
3118     }
3119
3120     /* no multiple information, so, if set to a constant,
3121      * prefer to keep that information */
3122     if (value->kind == 0) {
3123         value->kind = jit_kind_code;
3124         switch (node->code) {
3125             /* no information about signed/unsigned either */
3126             case jit_code_stxi_c:       value->code = jit_code_ldxi_c;  break;
3127             case jit_code_stxi_s:       value->code = jit_code_ldxi_s;  break;
3128             case jit_code_stxi_i:       value->code = jit_code_ldxi_i;  break;
3129             case jit_code_stxi_l:       value->code = jit_code_ldxi_l;  break;
3130             case jit_code_stxi_f:       value->code = jit_code_ldxi_f;  break;
3131             case jit_code_stxi_d:       value->code = jit_code_ldxi_d;  break;
3132             default:                    abort();
3133         }
3134         value->kind = jit_kind_code;
3135         value->base.q.l = right;
3136         value->base.q.h = _jitc->gen[right];
3137         value->disp.w = node->u.w;
3138     }
3139
3140     return (0);
3141 }
3142
3143 /* usually there should be only one store in the
3144  * jit_get_reg/jit_unget_reg, but properly handle
3145  * multiple ones by moving the save node */
3146 static void
3147 _simplify_spill(jit_state_t *_jit, jit_node_t *node, jit_int32_t regno)
3148 {
3149     jit_node_t          *save;
3150     jit_node_t          *temp;
3151
3152     if ((temp = _jitc->spill[regno]) && (save = temp->next) != node) {
3153         temp->next = save->next;
3154         save->next = node->next;
3155         node->next = save;
3156         _jitc->spill[regno] = node;
3157     }
3158 }
3159
3160 /* checks for simple cases where a register is set more than
3161  * once to the same value, and is a common pattern of calls
3162  * to jit_pushargi and jit_pushargr
3163  */
3164 static void
3165 _simplify(jit_state_t *_jit)
3166 {
3167     jit_node_t          *prev;
3168     jit_node_t          *node;
3169     jit_node_t          *next;
3170     jit_int32_t          info;
3171     jit_int32_t          regno;
3172
3173     for (prev = NULL, node = _jitc->head; node; prev = node, node = next) {
3174         next = node->next;
3175         switch (node->code) {
3176             case jit_code_label:        case jit_code_prolog:
3177             case jit_code_callr:        case jit_code_calli:
3178             reset:
3179                 memset(_jitc->gen, 0, sizeof(jit_int32_t) * _jitc->reglen);
3180                 memset(_jitc->values, 0, sizeof(jit_value_t) * _jitc->reglen);
3181                 break;
3182             case jit_code_save:
3183                 _jitc->spill[jit_regno(node->u.w)] = prev;
3184                 break;
3185             case jit_code_load:
3186                 regno = jit_regno(node->u.w);
3187                 if (register_change_p(node->link->next, node, regno) !=
3188                     jit_reg_change) {
3189                     /* spill not required due to optimizing common
3190                      * redundancy case of calling jit_get_reg/jit_unget_reg
3191                      * and then setting the register to the value it is
3192                      * already holding */
3193                     patch_register(node->link->next, node,
3194                                    jit_regno_patch|regno, regno);
3195                     del_node(_jitc->spill[regno], node->link);
3196                     del_node(prev, node);
3197                     node = prev;
3198                 }
3199                 _jitc->spill[regno] = NULL;
3200                 break;
3201             case jit_code_movr:
3202                 regno = jit_regno(node->u.w);
3203                 if (simplify_movr(prev, node,
3204                                   jit_kind_word, sizeof(jit_word_t)))
3205                     simplify_spill(node = prev, regno);
3206                 break;
3207             case jit_code_movi:
3208                 regno = jit_regno(node->u.w);
3209                 if (simplify_movi(prev, node,
3210                                   jit_kind_word, sizeof(jit_word_t)))
3211                     simplify_spill(node = prev, regno);
3212                 break;
3213             case jit_code_movr_f:
3214                 regno = jit_regno(node->u.w);
3215                 if (simplify_movr(prev, node,
3216                                   jit_kind_float32, sizeof(jit_float32_t)))
3217                     simplify_spill(node = prev, regno);
3218                 break;
3219             case jit_code_movi_f:
3220                 regno = jit_regno(node->u.w);
3221                 if (simplify_movi(prev, node,
3222                                   jit_kind_float32, sizeof(jit_float32_t)))
3223                     simplify_spill(node = prev, regno);
3224                 break;
3225             case jit_code_movr_d:
3226                 regno = jit_regno(node->u.w);
3227                 if (simplify_movr(prev, node,
3228                                   jit_kind_float64, sizeof(jit_float64_t)))
3229                     simplify_spill(node = prev, regno);
3230                 break;
3231             case jit_code_movi_d:
3232                 regno = jit_regno(node->u.w);
3233                 if (simplify_movi(prev, node,
3234                                   jit_kind_float64, sizeof(jit_float64_t)))
3235                     simplify_spill(node = prev, regno);
3236                 break;
3237             case jit_code_ldxi_c:       case jit_code_ldxi_uc:
3238             case jit_code_ldxi_s:       case jit_code_ldxi_us:
3239             case jit_code_ldxi_i:       case jit_code_ldxi_ui:
3240             case jit_code_ldxi_l:
3241             case jit_code_ldxi_f:       case jit_code_ldxi_d:
3242                 regno = jit_regno(node->u.w);
3243                 if (simplify_ldxi(prev, node))
3244                     simplify_spill(node = prev, regno);
3245                 break;
3246             case jit_code_stxi_c:       case jit_code_stxi_s:
3247             case jit_code_stxi_i:       case jit_code_stxi_l:
3248             case jit_code_stxi_f:       case jit_code_stxi_d:
3249                 regno = jit_regno(node->u.w);
3250                 if (simplify_stxi(prev, node))
3251                     simplify_spill(node = prev, regno);
3252                 break;
3253             default:
3254                 info = jit_classify(node->code);
3255                 if (info & jit_cc_a0_jmp)
3256                     /* labels are not implicitly added when not taking
3257                      * a conditional branch */
3258                     goto reset;
3259                 if (info & jit_cc_a0_chg) {
3260                     if (info & jit_cc_a0_rlh) {
3261                         regno = jit_regno(node->u.q.l);
3262                         _jitc->values[regno].kind = 0;
3263                         ++_jitc->gen[regno];
3264                         regno = jit_regno(node->u.q.h);
3265                         _jitc->values[regno].kind = 0;
3266                         ++_jitc->gen[regno];
3267                     }
3268                     else {
3269                         regno = jit_regno(node->u.w);
3270                         _jitc->values[regno].kind = 0;
3271                         ++_jitc->gen[regno];
3272                     }
3273                 }
3274                 if (info & jit_cc_a1_chg) {
3275                     regno = jit_regno(node->v.w);
3276                     _jitc->values[regno].kind = 0;
3277                     ++_jitc->gen[regno];
3278                 }
3279                 if (info & jit_cc_a2_chg) {
3280                     regno = jit_regno(node->w.w);
3281                     _jitc->values[regno].kind = 0;
3282                     ++_jitc->gen[regno];
3283                 }
3284                 break;
3285         }
3286     }
3287 }
3288
3289 static jit_int32_t
3290 _register_change_p(jit_state_t *_jit, jit_node_t *node, jit_node_t *link,
3291                    jit_int32_t regno)
3292 {
3293     jit_int32_t         value;
3294
3295     for (; node != link; node = node->next) {
3296         switch (node->code) {
3297             case jit_code_label:        case jit_code_prolog:
3298                 /* lack of extra information so cannot say it is undefined */
3299                 return (jit_reg_change);
3300             case jit_code_callr:        case jit_code_calli:
3301                 if (!(jit_class(_rvs[regno].spec) & jit_class_sav))
3302                     return (jit_reg_undef);
3303                 break;
3304             default:
3305                 value = jit_classify(node->code);
3306                 /* lack of extra information */
3307                 if (value & jit_cc_a0_jmp)
3308                     return (jit_reg_change);
3309                 else if ((value & (jit_cc_a0_reg|jit_cc_a0_chg)) ==
3310                          (jit_cc_a0_reg|jit_cc_a0_chg) &&
3311                          (((value & jit_cc_a0_rlh) &&
3312                            (node->u.q.l == regno || node->u.q.h == regno)) ||
3313                           (!(value & jit_cc_a0_rlh) &&
3314                            node->u.w == regno)))
3315                     return (jit_reg_change);
3316                 else if ((value & jit_cc_a1_reg) && node->v.w == regno &&
3317                          (value & jit_cc_a1_chg))
3318                     return (jit_reg_change);
3319                 else if ((value & jit_cc_a2_reg) && node->w.w == regno &&
3320                          (value & jit_cc_a2_chg))
3321                     return (jit_reg_change);
3322         }
3323     }
3324
3325     return (jit_reg_static);
3326 }
3327
3328 /* most of this could be done at the same time as generating jit, but
3329  * avoid complications on different cpu backends and patch spill/loads
3330  * here, by simulating jit generation */
3331 static jit_bool_t
3332 _spill_reglive_p(jit_state_t *_jit, jit_node_t *node, jit_int32_t regno)
3333 {
3334     if (!jit_regset_tstbit(&_jitc->reglive, regno)) {
3335         jit_regset_setbit(&_jitc->regmask, regno);
3336         jit_update(node->next, &_jitc->reglive, &_jitc->regmask);
3337         if (!jit_regset_tstbit(&_jitc->reglive, regno) &&
3338             register_change_p(node->next, node->link, regno) != jit_reg_change)
3339             return (0);
3340     }
3341
3342     return (1);
3343 }
3344
3345 static void
3346 _patch_registers(jit_state_t *_jit)
3347 {
3348     jit_node_t          *prev;
3349     jit_node_t          *node;
3350     jit_node_t          *next;
3351     jit_int32_t          info;
3352     jit_int32_t          spec;
3353     jit_int32_t          regno;
3354     jit_int32_t          value;
3355
3356     _jitc->function = NULL;
3357
3358     jit_reglive_setup();
3359     for (prev = NULL, node = _jitc->head; node; node = next) {
3360         next = node->next;
3361
3362         info = jit_classify(node->code);
3363         jit_regarg_set(node, info);
3364
3365         switch (node->code) {
3366             case jit_code_save:
3367                 regno = jit_regno(node->u.w);
3368                 if (!spill_reglive_p(node, regno)) {
3369                     /* register is not live, just remove spill/reload */
3370                     jit_regarg_clr(node, info);
3371                     node->link->v.w = jit_regload_delete;
3372                     del_node(prev, node);
3373                     continue;
3374                 }
3375                 else {
3376                     /* try to find a free register of the same class */
3377                     spec = jit_class(_rvs[regno].spec) & ~jit_class_arg;
3378                     for (value = 0; value < _jitc->reglen; value++) {
3379                         if (value != regno &&
3380                             ((jit_class(_rvs[value].spec) & spec) &
3381                              ~jit_class_arg) == spec &&
3382                             !jit_regset_tstbit(&_jitc->regarg, value) &&
3383                             !spill_reglive_p(node, value))
3384                             break;
3385                     }
3386                     if (value < _jitc->reglen) {
3387                         jit_regarg_clr(node, info);
3388                         patch_register(node->next, node->link,
3389                                        jit_regno_patch|node->u.w,
3390                                        jit_regno_patch|value);
3391                         /* mark as live just in case there are nested
3392                          * register patches, so that next patch will
3393                          * not want to use the same register */
3394                         jit_regset_setbit(&_jitc->reglive, value);
3395                         /* register is not live, just remove spill/reload */
3396                         node->link->v.w = jit_regload_isdead;
3397                         del_node(prev, node);
3398                         continue;
3399                     }
3400                     else {
3401                         /* failed to find a free register */
3402                         if (spec & jit_class_gpr) {
3403                             if (!_jitc->function->regoff[regno])
3404                                 _jitc->function->regoff[regno] =
3405                                     jit_allocai(sizeof(jit_word_t));
3406 #if __WORDSIZE == 32
3407                             node->code = jit_code_stxi_i;
3408 #else
3409                             node->code = jit_code_stxi_l;
3410 #endif
3411                         }
3412                         else {
3413                             node->code = jit_code_stxi_d;
3414                             if (!_jitc->function->regoff[regno])
3415                                 _jitc->function->regoff[regno] =
3416                                     jit_allocai(sizeof(jit_float64_t));
3417                         }
3418                         node->u.w = _jitc->function->regoff[regno];
3419                         node->v.w = JIT_FP;
3420                         node->w.w = regno;
3421                         node->link = NULL;
3422                     }
3423                 }
3424                 break;
3425             case jit_code_load:
3426                 regno = jit_regno(node->u.w);
3427                 if (node->v.w) {
3428                     if (node->v.w == jit_regload_isdead)
3429                         jit_regset_clrbit(&_jitc->reglive, regno);
3430                     del_node(prev, node);
3431                     continue;
3432                 }
3433                 spec = jit_class(_rvs[regno].spec);
3434                 if (spec & jit_class_gpr) {
3435 #if __WORDSIZE == 32
3436                     node->code = jit_code_ldxi_i;
3437 #else
3438                     node->code = jit_code_ldxi_l;
3439 #endif
3440                 }
3441                 else
3442                     node->code = jit_code_ldxi_d;
3443                 node->v.w = regno;
3444                 node->v.w = JIT_FP;
3445                 node->w.w = _jitc->function->regoff[regno];
3446                 node->link = NULL;
3447                 break;
3448             case jit_code_prolog:
3449                 _jitc->function = _jitc->functions.ptr + node->w.w;
3450                 break;
3451             case jit_code_epilog:
3452                 _jitc->function = NULL;
3453                 break;
3454             default:
3455                 break;
3456         }
3457
3458         jit_regarg_clr(node, info);
3459         /* update register live state */
3460         jit_reglive(node);
3461         prev = node;
3462     }
3463 }
3464
3465 static void
3466 _patch_register(jit_state_t *_jit, jit_node_t *node, jit_node_t *link,
3467                 jit_int32_t regno, jit_int32_t patch)
3468 {
3469     jit_int32_t         value;
3470
3471     for (; node != link; node = node->next) {
3472         value = jit_classify(node->code);
3473         if (value & jit_cc_a0_reg) {
3474             if (value & jit_cc_a0_rlh) {
3475                 if (node->u.q.l == regno)
3476                     node->u.q.l = patch;
3477                 if (node->u.q.h == regno)
3478                     node->u.q.h = patch;
3479             }
3480             else {
3481                 if (node->u.w == regno)
3482                     node->u.w = patch;
3483             }
3484         }
3485         if ((value & jit_cc_a1_reg) && node->v.w == regno)
3486             node->v.w = patch;
3487         if ((value & jit_cc_a2_reg) && node->w.w == regno)
3488             node->w.w = patch;
3489     }
3490 }
3491
3492 #if defined(__i386__) || defined(__x86_64__)
3493 #  include "jit_x86.c"
3494 #elif defined(__mips__)
3495 #  include "jit_mips.c"
3496 #elif defined(__arm__)
3497 #  include "jit_arm.c"
3498 #elif defined(__powerpc__)
3499 #  include "jit_ppc.c"
3500 #elif defined(__sparc__)
3501 #  include "jit_sparc.c"
3502 #elif defined(__ia64__)
3503 #  include "jit_ia64.c"
3504 #elif defined(__hppa__)
3505 #  include "jit_hppa.c"
3506 #elif defined(__aarch64__)
3507 #  include "jit_aarch64.c"
3508 #elif defined(__s390__) || defined(__s390x__)
3509 #  include "jit_s390.c"
3510 #elif defined(__alpha__)
3511 #  include "jit_alpha.c"
3512 #elif defined(__riscv)
3513 #  include "jit_riscv.c"
3514 #endif