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